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

Здравствуйте, 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)
    //столкнулись.

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

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

Тормозит именно пересечение прямоугольников? По идее, это не очень ресурсоемкая операция...
А как в целом организован collision? Может обращение к проверке на пересечение происходит слишком часто?

Здравствуйте, 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>

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

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

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

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

FM>Тормозит именно пересечение прямоугольников? По идее, это не очень ресурсоемкая операция...
Да.

FM>А как в целом организован collision? Может обращение к проверке на пересечение происходит слишком часто?
В целом применяется мысль, что если точка входит в полигон, сумма углов получается равной 2Pi. Алгоритм хороший, да только использует деление и арктангенс .
Хотел еще попробовать сделать на основе проверки пересечения линий, но решил сначала написать сюда .

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

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

ИМХО:
Я бы посмотрел не на ускорение самой операции пересечения прямоугольников (ведь она и так, скорее всего, быстрая), а на то, как выбираются прямоугольники для пересечения. Может здесь стоит применить 2d-дерево или четверичное дерево, чтобы сократить множество прямоугольников, с которыми заданный потенциально может пересекаться.

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

FM>>А как в целом организован collision? Может обращение к проверке на пересечение происходит слишком часто?
J>В целом применяется мысль, что если точка входит в полигон, сумма углов получается равной 2Pi. Алгоритм хороший, да только использует деление и арктангенс .
J>Хотел еще попробовать сделать на основе проверки пересечения линий, но решил сначала написать сюда .

Если хочется именно проверки попадания точки в 4-хугольник, тогда лови:

namespace geo
{
   struct DOT
     {
        int x, y;
     };
}
...
// ======================================================================================
//             WHETHER POINT <a> IS INSIDE THE POLYGON [poly1, polyEnd)
bool geo::PointInPoly(geo::DOT a, const geo::DOT* poly1, const geo::DOT* polyEnd)
{
   unsigned val = 0;
   for ( const DOT* pnt = poly1 + 1; pnt != polyEnd; ++pnt )
   {
      DOT ap = *(pnt - 1) - a,
          pp = *pnt - *(pnt - 1);
      double p = (double)pp.x * (double)ap.y - (double)ap.x * (double)pp.y;
      if ( p < 0 )
         val |= 0x1;
      else if ( p > 0 )
         val |= 0x2;

      if ( val == 0x3 )   // no doubt the point is outside the polygon
         return false;
   }

   return true; //val != 0x3;
}
// ======================================================================================

Проверяем — с какой стороны от ребра полигона находится точка.
Если для всех ребер точка лежит с одной стороны — значит внутри полигона.
Работает, понятное дело, только для выпуклых полигонов.
Да, последняя вершина полигона должна совпадать с 1-й.

А вообще-то, тебе в книжный магазин.
1. Э.Эйнджел "Интерактивная компьютерная графика. Вводный курс на базе OpenGL". Вильямс 2001.
2. Ф.Хилл (серия "Для профессионалов") "OpenGL. Программирование компьютерной графики". Питер 2002.
3. М.Ласло Что-то про вычислительную геометрию. Издавалась году эдак в 1997.
4. Препарата, Шеймос. Есть в нете.
5. А.А. Рывкин, А.З. Рывкин, Л.С. Хренов "Справочник по математике" Высшая школа, 1964. Наверняка есть на книжной полке.

Увидишь книжку Никулина Е.А. "Компьютерная геометрия и алгоритмы машинной графики" — НЕ БЕРИ.
За такое изложение элементарных вещей автору нужно оторвать все, что торчит. и не подпускать его к ВУЗу, в котором он преподает.
Даже знающий не разберет.

Здравствуйте, jaguard,
Хорошая задача.
Можно посмотреть

Fast Software for Box Intersections
Afra Zomorodian and Herbert Edelsbrunner

здесь описание алгоритма, a здесь
можно взять реализацию — текст программы на C.


Константин

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

FM>>А как в целом организован collision? Может обращение к проверке на пересечение происходит слишком часто?
J>В целом применяется мысль, что если точка входит в полигон, сумма углов получается равной 2Pi. Алгоритм хороший, да только использует деление и арктангенс .
Тут вопрос немного в другом — сколько объектов одновременно проверяются на пересечение друг с другом? Возможно ли уменьшить их количество, сделав хеш — дерево или сетку в игровом пространстве?

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

Также можно посмотреть

SOLID is a free library for collision detection здесь

с описаниями алгоритмов и текстами:

FreeSOLID is available at SourceForge здесь.

Константин

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ> return true; //val != 0x3;
SVZ>}
SVZ>// ======================================================================================
SVZ>[/ccode]

SVZ>Проверяем — с какой стороны от ребра полигона находится точка.
SVZ>Если для всех ребер точка лежит с одной стороны — значит внутри полигона.
SVZ>Работает, понятное дело, только для выпуклых полигонов.
SVZ>Да, последняя вершина полигона должна совпадать с 1-й.
Судя по всему, вариант алгоритма http://mathforum.org/library/drmath/view/54386.html, который мне посоветовали буржуи только более простой и оптимальный. Если он действительно работает, остановлюсь на нем, спасибо .


SVZ>А вообще-то, тебе в книжный магазин.
SVZ>1. Э.Эйнджел "Интерактивная компьютерная графика. Вводный курс на базе OpenGL". Вильямс 2001.
SVZ>2. Ф.Хилл (серия "Для профессионалов") "OpenGL. Программирование компьютерной графики". Питер 2002.
SVZ>3. М.Ласло Что-то про вычислительную геометрию. Издавалась году эдак в 1997.
SVZ>4. Препарата, Шеймос. Есть в нете.
SVZ>5. А.А. Рывкин, А.З. Рывкин, Л.С. Хренов "Справочник по математике" Высшая школа, 1964. Наверняка есть на книжной полке.

О, это любимое занятие русского человека — советовать то, о чем их не спрашивали . Про геометрию я действительно бы почитал, но зачем мне openGL? . Я разве упоминал, что пользуюсь openGL, directX, и вообще использую 3д графику? . Математические справочники у меня тоже есть, но от них толку довольно мало, тамошние алгоритмы хоть и правильные, да уж больно неоптимальные .

2ВсеОстальные: Я слишком далекие объекты и так отсекаю по дальности, так что деревья в любом случае дадут мизерный прирост производительности. А максимум объектов у меня сотни две, причем каждый потенциально достает до 9 соседей(эдакий тетрис .

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

J>Судя по всему, вариант алгоритма http://mathforum.org/library/drmath/view/54386.html, который мне посоветовали буржуи только более простой и оптимальный. Если он действительно работает, остановлюсь на нем, спасибо .

В этой "волшебной функции" используется банальное векторное произведение, вернее одно из его свойств
Подробнее читать в [5].

J>О, это любимое занятие русского человека — советовать то, о чем их не спрашивали . Про геометрию я действительно бы почитал, но зачем мне openGL? . Я разве упоминал, что пользуюсь openGL, directX, и вообще использую 3д графику? . Математические справочники у меня тоже есть, но от них толку довольно мало, тамошние алгоритмы хоть и правильные, да уж больно неоптимальные .

Я разве где-то упомянул, что нужно читать про "...openGL, directX, и вообще 3д графику?"
В этих книгах самым подробным образом разжеваны алгоритмы, о которых здесь спрашивают каждую неделю. Вот именно их-то и надо читать.

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

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

Не так давно я на IXBT создавал ветку — и там расписывал алгоритм collision detection — без арктангенсов, и другой тригонометрии. И для любых многоугольников. Я в игре своей юзаю — работает на ура:

Вот тут эта ветка