Оптимизация вычисления расстояния до треугольника с использованием барицентрических координат

Question

Опираясь на обсуждения здесь и здесь . Я пытаюсь вычислить кратчайшее расстояние между 3D-линией и 3D-треугольником.

Я использую барицентрические координаты, чтобы определить, находится ли точка внутри треугольника . Поэтому, учитывая треугольник, определенный вершинами UVW, и линию, определенную точкой AB, я сначала вычисляю пересечение линии AB с плоскостью, определенной как UVW. Давайте назовем это пересечение P и предположим, что я уже выполнил проверки, чтобы проверить, действительно ли точка действительно пересекает плоскость.

Затем я вычисляю барицентрические координаты (S,T), так что S определяется вдоль края UV, а T определяется вдоль края UW. Естественно, если 0≤S и 0≤T и S+T≤1, тогда P находится на треугольнике (или его ребре), и мое расстояние до треугольника, очевидно, равно нулю.

Если это не так, тогда P находится за пределами треугольника, и мне нужно вычислить расстояние. Руководство из первой ссылки говорит, чтобы проецировать точку P на все три ребра, чтобы получить три балла-кандидата. Добавив эти точки к вершинам трех треугольников, вы получите шесть точек для проверки.

Разве это не проще? Если T<0, то разве вы не знаете, что UV является ближайшим краем, и вам нужно только проверить проекцию P на эту линию? Аналогично, если S<0, то UW будет ближайшим краем. Если T>0 и S>0, то VW является ближайшим краем.

Таким образом, основываясь на знаках S и T, вы уже знаете ближайший край и вам нужно только вычислить расстояние от P до его проекции на этот край. Если проекция не находится внутри треугольника, то ближайшей точкой является либо вершина. Таким образом, ваши расчеты составляют около 1/3 предложенных методов.

Я что-то здесь упускаю или это действительная оптимизация? Я довольно плохо знаком с барицентрическими координатами и их атрибутами.

Answer 1

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

Расстояние от точки

Пифагор, квадрат расстояния от точки до точки треугольника - это сумма квадрата расстояния до плоскости опоры треугольника и квадрата расстояния проекции точки на эту плоскость.

последнее расстояние - это как раз расстояние от нормальной линии до треугольника.

расстояние от линии

Глядя в направлении линии, вы видите спроецированный треугольник, и линия уменьшается доодна точка.Запрашиваемое 3D-расстояние равно 2D-расстоянию, видимому в проекции.

Чтобы получить нужные координаты, вы используете вспомогательную систему координат, такую, что Z находится в направлении линии (а XY - перпендикулярная плоскость);для удобства выберите начало строки нового кадра.Тогда, просто игнорируя Z, вы получаете плоскую проблему в XY.Изменение координат является аффинным преобразованием.

Точка против треугольника

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

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

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

Общая работа

• вычисление аффинного фрейма;
• преобразовать координаты 3 или 4 точек;
• вычислить три области со знаком;
• , если внутри, все готово;
• в противном случае, если в краевой области,вычислить расстояние до линии и два расстояния до точек;
• в противном случае вы находитесь в области вершин, вычислите два расстояния до линий и одно расстояние до вершины.