Обнаружение столкновений с полигонами

Question

Мне было интересно, может ли кто-нибудь дать мне представление о том, как реализовать сначала класс для определения многоугольника, а во-вторых, как обнаружить столкновения между двумя многоугольниками, используя этот класс. Я работаю в Java на Android, чтобы быть более конкретным, хотя я также могу использовать NDK для C / C ++. Я думаю, что для определения моего многоугольника мне просто понадобится массив вершин, верно?

Когда я выполняю обнаружение столкновений, я читаю кое-что о теореме об отделении и алгоритме GJK. Это правильный путь, или я делаю это слишком сложным. Просто пытаюсь начать в правильном направлении. Спасибо!

Answer 1

Похоже, вы довольно плохо знакомы с подобными вещами, и, возможно, это более сложный вопрос, который вы осознаете.

Я думаю, что вы приложите все усилия, чтобы сначала определить проблему, которую вы пытаетесь решить, а затем найдите решение, которое решает эту проблему.

Позвольте мне задать вам несколько уточняющих вопросов:

Вы говорите о 2d или 3d?

Это для физикисистема?

вам нужно знать, где они пересекаются или просто они пересекаются?

вам нужно сделать логическую операцию с фигурами (например, получить пересечение или объединение или что-то еще)?

Answer 2

Зависит от типа полигона.

Если ваши многоугольники выпуклые, то упорядоченный список вершин будет описывать одну и обе разделяющие оси и GJK будут применимыми алгоритмами.

Если ваши многоугольники вогнуты, но просты (т. Е. Ребра никогда не пересекаются), тогда упорядоченный список вершин все еще достаточен, но ни подходящая разделяющая ось, ни GJK не подходят.

Если ваши полигоны сложны (т. Е. Ребра могут пересекаться), тогда вам понадобится список вершин и правило заполнения. Правило установило, какие части плоскости считаются находящимися внутри многоугольника, а какие - внешними.

Например, представьте многоугольник как пентаграмму:

Разница в правилах заполнения заключается в том, является ли пятистороннее отверстие в середине частью многоугольника или просто отверстием.

Все более сложные типы многоугольников можно разбить на несколько экземпляров более простых типов многоугольников, поэтому вполне нормально просто поставить флаг на землю и объявить, что тебя интересуют только выпуклые многоугольники - это точно например, что делают графические процессоры.

Предполагая, что вы определяете столкновения как простое перекрытие двух полигонов или нет, теорема о разделении осей очень проста и определенно поможет. Если вы планируете создать сцену с большим количеством полигонов, то вам, вероятно, также понадобится широкая фаза, которая является быстрым способом пометить целую группу полигонов как определенно не перекрывающихся перед тем, как выполнить дорогостоящий тест, чтобы выяснить, какие из остальных все еще есть.

Очевидным примером является сортировка бина - предположим, что вы разбили экран на 16-пиксельные вертикальные полосы, а затем для каждого многоугольника вы можете (i) определить, какие ячейки касаются его; (ii) проверить его на наличие всех полигонов, уже находящихся в этих корзинах; (iii) добавить его в контейнеры. Это, вероятно, означало бы, что вы даже не рассматриваете возможность применения теста довольно много времени. Эта конкретная схема имеет некоторые очевидные проблемы, в зависимости от вашей сцены, но существуют более умные алгоритмы.