Пересечение лучей и треугольников

Question

Как я могу проверить луч пересечения и треугольник, и если он существует, как получить расстояние от начала луча до точки пересечения ?? Какую оптимизацию я могу использовать, если в моей программе мне нужно проверить 1 луч до ~ 10000 треугольников ??

Answer 1

Один тест пересечения многоугольных лучей является тривиальным и просто включает в себя проверку того, что луч пересекает хотя бы одну его сторону (проверьте их по отдельности) или поперек плоскости, определяемой треугольником между сторонами. Оптимизация заключается в том, чтобы не проверять полигоны, что у луча нет шансов на пересечение. В зависимости от размера измерения, в котором вы работаете, размера области и количества полигонов, с которыми вы работаете, наиболее типичные оптимизации: quadtree , octrees и KD-деревья . Это также примерно порядок сложности реализации (хотя quad и ottree очень похожи).

Answer 2

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

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm

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

if (dot(V, N) >= 0)     // no intersection - ray points away from the triangle face
if (dot(P0, N) + d < 0) // no intersection - ray origin is behind the triangle face

Еще одна мысль, которую я использовал, когда я нахожу точку пересечения луча и лица. Я использовал для проверки точки внутри треугольника в 2D, когда я обнулял ось с максимальным абсолютным значением нормали ... если abs (Nx)> abs (Ny)> abs (Nz), я сделаю проверку в Самолет YZ.

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

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld012.htm

Не решайте весь многочлен, вам не нужна точка пересечения луча / сферы, просто проверьте наличие корней.

Есть много других оптимизаций, которые вы можете сделать, например: Если ваши вершины и нормали могут быть расположены в более дружественной структуре SSE, вы можете делать 4 проверки за раз. Что примерно может увеличиться примерно в 2,5 раза.