Каков быстрый алгоритм определения, находится ли точка внутри трехмерной сетки? Для простоты вы можете предположить, что сетка состоит из треугольников и не имеет отверстий.
До сих пор я знал, что один из популярных способов определения того, пересек ли луч сетку, - это подсчитать количество пересечений луча / треугольника. Он должен быть быстрым, потому что я использую его для тактильной медицинской симуляции. Поэтому я не могу проверить все треугольники на пересечение лучей. Мне нужно какое-то хеширование или древовидная структура данных для хранения треугольников, чтобы помочь определить, какой треугольник имеет отношение к делу.
Кроме того, я знаю, что если у меня есть произвольная 2D-проекция вершин, простой тест пересечения точки / треугольника будет все необходимое. Однако мне все равно нужно знать, какие треугольники релевантны и, кроме того, какие треугольники лежат перед точкой, и проверять только эти треугольники.