Обнаружить точку столкновения между сеткой и сферой?

Question

Я пишу симулятор физики, используя Огр и МОС .

У меня есть сфера, которую я снимаю из положения камеры, и она перемещается в направлении, в котором она находится, используя вектор вперед камеры.

Я хотел бы знать, как я могу обнаружить точку столкновения между моей сферой и другой сеткой.

Как бы я мог проверить точку столкновения между двумя сетками, используя MOC или OGRE?

Обновление: следовало упомянуть об этом ранее. Я не могу использовать стороннюю библиотеку физики, так как мне нужно разработать ее самостоятельно (проект uni).

Answer 1

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

Это действительно нужно сделать при столкновении с каждым полигоном. Вы должны быть в состоянии проверить пересечение многоугольника и сферы (и, кроме того, цилиндра, если хотите избежать туннелирования, как упоминалось выше). Существует немало ресурсов для этого в Интернете и в виде книги, но http://www.realtimerendering.com/intersections.html может быть полезной отправной точкой.

Хорошие комментарии по оптимизации. Возможности раннего выхода (возможно, быстрая проверка на ограничивающую сферу или ограничивающий объем для сетки). Даже если вы определили, что находитесь внутри ограничивающего тома, возможно, было бы неплохо отсеять неожиданные полигоны (слишком далеко, лицом в неправильном направлении и т. Д.) Из списка потенциальных кандидатов.

Answer 2

Я думаю, что лучше всего было бы использовать специализированную физическую библиотеку.

Это сказал. Если бы я подумал об этой проблеме, я бы заподозрил, что это не так сложно:

Сфера имеет среднюю точку и радиус. Для каждой точки сетки сделайте следующее:

1. проверьте, находится ли точка внутри сферы.
2. если он проверяет, находится ли он ближе к центру, чем ранее найденная точка (если есть)
3. если это так ... сохранить эту точку как точку столкновения

Конечно, эта процедура будет довольно медленной. Несколько вещей, чтобы ускорить это:

1. для первого тривиального отклонения, сначала посмотрите, сталкивается ли ограничивающая сфера сетки
2. не вычисляйте квадратные корни при проверке расстояний ... вместо этого используйте квадраты длины (намного быстрее)
3. Вместо сравнения каждой точки сетки используйте алгоритм пространственного деления пространства (квадри / BSP) для сетки, чтобы быстро исключить группы точек

Ах ... и эта процедура работает, только если сфера движется не слишком быстро (относительно сетки). Если он будет перемещаться очень быстро, и вы будете пробовать его X раз в секунду, скорее всего, сфера пролетит прямо через сетку без всякого столкновения. Чтобы преодолеть это, вы должны использовать «развернутые объемы», которые в основном превращают вашу сферу в трубу. Делать математику экспоненциально сложно.