Пересечение тысяч лучей с треугольниками в трехмерном пространстве
Есть тысячи лучей и треугольников. Нам нужно получить все точки пересечения. Если мы используем обычные двухуровневые циклы, нам понадобится O (mn) временная сложность. Есть ли способ уменьшить временную сложность от O (m n) до O(m* logn) или O(logm*n)?
С уважением,
6 ответов
То, на что вы, вероятно, хотите взглянуть, это какая-то техника разделения пространства. Это позволяет быстро исключить наборы треугольников.
Я, вероятно, рассмотрю некоторый подход, использующий сферические иерархии ограничивающих объемов. Но другие методы, которые вы, возможно, захотите изучить, это деревья BSP (Binary Space Partitioning)/ деревья KD или использование Octree
Классическое решение этой проблемы - построить дерево KD на основе треугольников и запросить его для каждого луча. Вы можете оптимизировать дерево для ожидаемых запросов; если ваши лучи распределены случайным образом, вероятность попадания пропорциональна рассматриваемой площади поверхности.
Даже если вы на самом деле не выполняете трассировку лучей, эта проблема в настоящее время является основным узким местом производительности для трассировки лучей, поэтому вам, вероятно, следует ознакомиться с соответствующей литературой.
Нет. Причина проста: на самом деле могут быть точки пересечения O(m * n). просто создать их список - O(n * m).
В 2D есть алгоритм SweepLine. Мне кажется, это можно обобщить для 3D.
Вы можете сгруппировать треугольники близко друг к другу в кубы. Затем для каждого луча: если он не попадает в куб, вы уверены, что он не попадет ни в один из треугольников внутри куба, поэтому вы можете пропустить все вычисления пересечения с этими треугольниками для этого конкретного луча.
Очевидно, что если вы должны выполнить итерацию и вычислить пересечение между лучом и каждым треугольником, то сложность O(mn). Однако, если вас интересуют только те треугольники, которые потенциально могут пересекаться с конкретным лучом, вы можете попробовать вариант решетки разделения пространства, например, иерархическую сетку четырех деревьев ( http://graphics.stanford.edu/courses/cs468-06-fall/Slides/steve.pdf).