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

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

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

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

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

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

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

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

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

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

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