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

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

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

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

Ответ 1

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

Ответ 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

Ответ 3

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

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