Здравствуйте, jaguard, Вы писали:

J>Есть задача для игры сделать проверку пересечений. Игровые объекты — повернутые в пространстве прямоугольники.
В смысле прямоугольные паралелепипеды?
J>Проблема в том, что надо все сделать очень быстро. У меня есть реализованный алгоритм попадания точки в прямоугольник, но он слишком медленный. Отбрасывание слишком далеких объектов я тоже применяю — не очень помогает.
А чем тебе поможет попадание точки в паралелепипед? Тебе надо пересечение паралелепипедов ибо они могут пересечся так что ни одна из вершин одного не окажется в другом.
J>Есть ли алгоритмы попадания точки в четырехугольник или может специальные алгоритмы для повернутых прямоугольников, использующие минимум операций умножения(лучше вообще без них), без деления и тригонометрии?
Единственное что приходит в голову это смена системы координат одного из паралелепипедов.
Просто берешь одну из вершин паралелепипеда за начало координат и смежные ребра за базисные вектора далие один раз считаешь матрицу преобразования.
Тперь при помощи этой матрици переводишь в новую систему координат все паралелепипеды которые хочешь проверить на столкновение с текущем и проверяешь столкновение с кубиком находящимся в начале координат.

ЗЫ А на сферы перейти не хочешь? Всеравно ничего быстрее не придумаешь.

dx=x1-x2;
dy=y1-y2;
dz=z1-z2;
r=r1+r2;
d=dx*dx+dy*dy+dz*dz;
if(d<=r*r)
    //столкнулись.