Алгоритм определения, находится ли точка внутри трехмерной сетки

Question

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

Что я знаю до сих пор, так это то, что одним из популярных способов определения того, пересек ли луч сетку, является подсчет количества пересечений лучей и треугольников. Это должно быть быстро, потому что я использую это для тактильной медицинской симуляции. Поэтому я не могу проверить все треугольники на предмет пересечения лучей. Мне нужно что-то вроде хеширования или древовидной структуры данных для хранения треугольников, чтобы помочь определить, какие треугольники актуальны.

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

Answer 1

Я решил свою проблему. По сути, я беру произвольную 2D-проекцию (отбрасываю одну из координат) и хеширую AABB (ограничивающие оси ограничивающие рамки) треугольников в 2D-массив. (Набор трехмерных кубов, как упомянуто Titus, является излишним, поскольку он дает вам только постоянное ускорение.) Используйте 2D-массив и 2D-проекцию точки, которую вы тестируете, чтобы получить небольшой набор треугольников, который вы делаете Включите тест пересечения трехмерных лучей / треугольников (см. Пересечения лучей, сегментов, плоскостей и треугольников в 3D ) и подсчитайте количество треугольников пересечения лучей, где координата z (выброшенная координата) больше, чем Z-координата точки. Четное число пересечений означает, что оно находится за пределами сетки. Нечетное количество пересечений означает, что оно находится внутри сетки. Этот метод не только быстрый, но и очень простой в реализации (именно это я и искал).

Answer 2

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

Разделите пространство на кубы одинакового размера (размер выясним позже). Для каждого куба известно, какие треугольники имеют хотя бы точку в нем. Откажитесь от кубов, которые ничего не содержат. Выполните алгоритм наведения лучей, как представлено в википедии, но вместо этого проверьте, пересекает ли линия каждый треугольник, получите все кубы, которые пересекаются с линией, а затем выполните наведение лучей только с треугольниками в этих кубах. Не проверяйте один и тот же треугольник более одного раза, поскольку он присутствует в двух кубах.
Найти правильный размер куба сложно, он не должен быть ни большим, ни слишком маленьким. Его можно найти только методом проб и ошибок. Допустим, number of cubes это c и number of triangles это t.
Среднее количество треугольников в кубе составляет t/c
k - среднее число кубов, пересекающих луч
пересечения куба с линией + пересечение линии с треугольником в этих кубах должно быть минимальным
c+k*t/c=minimal => c=sqrt(t*k)
Вам придется проверять значения размера кубиков, пока c=sqrt(t*k) не станет истинным
Хорошее начальное предположение для размера куба будет sqrt(mesh width)
Чтобы иметь некоторую перспективу, для 1M треугольников вы протестируете порядок пересечений 1k

Answer 3

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

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