Пересечение тысяч лучей с треугольниками в трехмерном пространстве

Question

Есть тысячи лучей и треугольников. Нам нужно получить все точки пересечения. Если мы используем обычные двухуровневые циклы, нам понадобится O (m n) временная сложность. Есть ли способ уменьшить временную сложность от O (m n) до O (m * logn) или O ( logm * п)

С наилучшими пожеланиями,

Answer 1

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

Я бы, вероятно, рассмотрел некоторый подход с использованием сферических Иерархий ограничивающего объема . Но другие методы, которые вы также можете рассмотреть, это деревья BSP (Binary Space Partitioning) / KD Trees или использование Octree

Answer 2

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

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

Answer 3

Нет. Причина проста: на самом деле может быть O (m * n) точек пересечения. просто создать их список - O (n * m).

Answer 4

Очевидно, что если вам необходимо выполнить итерацию и вычислить пересечение между лучом и каждым треугольником, то сложность равна O (mn). Однако, если вас интересуют только те треугольники, которые потенциально могут пересекаться с конкретным лучом, вы можете попробовать вариант сетки разделения пространства, например, иерархическую сетку четырех деревьев (http://graphics.stanford.edu/courses/cs468-06-fall/Slides/steve.pdf).

Answer 5

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

Answer 6

В 2D есть SweepLine алгоритм. Мне кажется, это можно обобщить для 3D.