Обнаружение столкновения треугольника и треугольника в 3D

Question

Я понимаю треугольное обнаружение столкновения треугольника между двумя треугольниками. Может кто-нибудь объяснить, как я могу использовать это с 3D-объектом, состоящим из 1000s вершин? Как создать список треугольников для каждой сетки? Должен ли я взять каждую перестановку вершин? Это привело бы к O (n^3), который я считаю очень плохим.

Как это можно обобщить?

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

Большое спасибо.

Answer 1

http://en.wikipedia.org/wiki/Binary_space_partitioning

BSP дерево является очень эффективным способом проверки столкновения статических сеток, но это требует некоторой предварительной обработки сетки, чтобы удостовериться, что никакие треугольников не пересекаются. Он работает, разбивая сетку на полупространства. Это упрощает проверку столкновений и физику.

EDIT:

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

http://en.wikipedia.org/wiki/Octree

В ответ на ваш второй вопрос, что-то вроде формат файла .obj может быть то, что вы ищете.

http://en.wikipedia.org/wiki/Wavefront_.obj_file

Answer 2

Есть много оптимизаций, которые можно применять для обнаружения столкновений между сетками:

• разбиения пространства, как описано Джеймсом.

• Раннее отклонение с использованием bounding volumes. Например, сфера-сферическое столкновение дешево, поэтому перед тестированием столкновения A и B вы можете увидеть, сталкивается ли сфера, окружающая A, с сферой, окружающей B. Если сферы отсутствуют, очевидно, что сетки не могут столкнуться, поэтому нет необходимо проверить их. Для разных видов объектов могут потребоваться различные типы ограничивающих объемов: общие по окружности кубики и цилиндры.

• Кэширование свидетелей. В некоторых тестах на столкновение вы заканчиваете вычисление «свидетеля» для столкновения, например, когда вы применяете separating axis test, вы вычисляете разделительную ось. Если ось отделяет два объекта в момент времени t, вполне вероятно, что он продолжает разделять их по времени t + δ, поэтому он может заплатить за кеш оси, которую вы нашли, и попробовать ее в следующий раз (см. Rabbitz, «Fast Обнаружение столкновений движущихся выпуклых многогранников "в Графика Gems IV).