Самый быстрый способ вычислить точку к треугольному расстоянию в 3D?
Один очевидный метод для вычислений минимального расстояния от точки до 3D треугольника должен спроектировать точку на плоскость треугольника, определить барицентрические координаты получающейся точки и использовать их, чтобы определить, находится ли спроектированная точка в треугольнике. В противном случае зажим, это - барицентрические координаты, чтобы быть в диапазоне [0,1], и это дает Вам самую близкую точку, которая находится в треугольнике.
Существует ли способ ускорить это или упростить его так или иначе?
2 ответа
Существуют разные подходы к нахождению расстояния от точки P0 до треугольника P1, P2, P3.
3D-метод. Спроецируйте точку на плоскость треугольника и используйте барицентрические координаты или другие средства поиска ближайшей точки в треугольнике. Расстояние находится обычным способом.
2D-метод. Примените сдвиг / поворот к точкам так, чтобы P1 находился в начале координат, P2 - на оси z, P3 - в плоскости yz. Проекция точки P0 тривиальна (координатой x пренебречь). Это приводит к двумерной проблеме. Используя уравнение ребра, можно определить ближайшую вершину или край треугольника. Тогда вычислить расстояние очень просто.
В этой статье сравнивается эффективность обоих методов с выигрышем в 2D-методе.
Предполагая, что вы используете один из известных быстрых алгоритмов, единственный способ ускорить его - это когда вы выполняете много измерений на большом количестве треугольников. В этом случае вы можете хранить множество величин, предварительно вычисленных в структурах "edge" или "winding". Вместо хранения 3 точек, вы храните сетки, состоящие из краевых структур. Проекция тогда становится очень быстрой, а барицентрические тесты могут быть закодированы так, чтобы они были предсказуемы по ветвям.
Настоящий ключ - просто хранить все в кэше. Процессоры могут выполнять MUL и DIV почти за 1 тактовый цикл, поэтому память обычно является узким местом.
Также рассмотрите возможность написания алгоритма на SSE3 или чем-то подобном (например, поддержка SIMD в Mono). Это работа, но обычно вы можете делать пару треугольников за раз, если достаточно хорошо подумаете об этом.
Я постараюсь найти несколько статей на эту тему, но вы можете поискать в Google "Ray Mesh Intersection". Это поможет найти все замечательные работы 80-х и 90-х годов, когда люди упорно работали над оптимизацией этих вещей.