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

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

J>>Есть задача для игры сделать проверку пересечений. Игровые объекты — повернутые в пространстве прямоугольники.
WH>В смысле прямоугольные паралелепипеды?
Прямоугольники. У меня плоская задача.

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

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

Это я обдумаю. С поправкой на двумерную задачу может и получится более-менее быстро.

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

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

Да это понятно, но сферы никак не подходят, нужна точность.