Проецирование на 2D-плоскость для барицентрических расчетов

Question

У меня есть три вершины, которые составляют плоскость / многоугольник в 3D-пространстве, v0, v1 и v2.

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

После траления в сети я хорошо понимаю, как рассчитать барицентрические координаты в 2D-пространстве, но я застрял в поиске лучшего способа проецировать мои 3D-точки в подходящую 2D-плоскость.

Мне было предложено, что лучший способ добиться этого - "опустить ось с наименьшей проекцией" . Без проверки площади многоугольника, образованного при проецировании на каждую мировую ось (xy, yz, xz), как я могу определить, какая проекция является лучшей (имеет наибольшую площадь), и, следовательно, наиболее подходит для расчета наиболее точной барицентрической координаты

Answer 1

ПРЕДУПРЕЖДЕНИЕ - Почти все, что я знаю об использовании барицентрических координат и использовании матриц для решения линейных уравнений, было изучено вчера вечером, потому что я нашел этот вопрос настолько интересным.Таким образом, следующее может быть неправильным, неправильным, неправильным - , но некоторые введенные мной тестовые значения, похоже, работают .Парни и девушки, пожалуйста, не стесняйтесь разорвать это на части, если я облажался полностью - но здесь все.

Поиск барицентрических координат в трехмерном пространстве (с небольшой помощью из Википедии)

Дано:

v0 = (x0, y0, z0)
v1 = (x1, y1, z1)
v2 = (x2, y2, z2)

p = (xp, yp, zp)

Найти барицентрические координаты: b0, b1, b2 точки p относительно треугольника, определенного v0, v1 и v2

Зная, что:

xp = b0*x0 + b1*x1 + b2*x2
yp = b0*y0 + b1*y1 + b2*y2
zp = b0*z0 + b1*z1 + b2*z2

Который может быть записан как

[xp]      [x0]      [x1]      [x2]
[yp] = b0*[y0] + b1*[y1] + b2*[y2]
[zp]      [z0]      [z1]      [z2]

или

[xp]   [x0  x1  x2]   [b0]
[yp] = [y0  y1  y2] . [b1]
[zp]   [z0  z1  z2]   [b2]

, переставленный как

                   -1
[b0]   [x0  x1  x2]     [xp]
[b1] = [y0  y1  y2]   . [yp]
[b2]   [z0  z1  z2]     [zp]

, определяющим фактором матрицы 3x3 является:

det = x0(y1*z2 - y2*z1) + x1(y2*z0 - z2*y0) + x2(y0*z1 - y1*z0)

его присоединение равно

[y1*z2-y2*z1  x2*z1-x1*z2  x1*y2-x2*y1]
[y2*z0-y0*z2  x0*z2-x2*z0  x2*y0-x0*y2]
[y0*z1-y1*z0  x1*z0-x0*z1  x0*y1-x1*y0]

, давая:

[b0]     [y1*z2-y2*z1  x2*z1-x1*z2  x1*y2-x2*y1]   [xp]
[b1] = ( [y2*z0-y0*z2  x0*z2-x2*z0  x2*y0-x0*y2] . [yp] ) / det
[b2]     [y0*z1-y1*z0  x1*z0-x0*z1  x0*y1-x1*y0]   [zp]

Если вам нужно проверить количество точек на треугольнике, остановитесь здесь.Вычислите вышеупомянутую матрицу 3x3 один раз для треугольника (также разделив ее на определитель), а затем поставьте точечное произведение, которое получается в каждой точке, чтобы получить барицентрические координаты для каждой точки.

Если вы делаете это только один раздля каждого треугольника приведено умноженное выше (любезно предоставлено Maxima):

b0 = ((x1*y2-x2*y1)*zp+xp*(y1*z2-y2*z1)+yp*(x2*z1-x1*z2)) / det
b1 = ((x2*y0-x0*y2)*zp+xp*(y2*z0-y0*z2)+yp*(x0*z2-x2*z0)) / det
b2 = ((x0*y1-x1*y0)*zp+xp*(y0*z1-y1*z0)+yp*(x1*z0-x0*z1)) / det

Это довольно много сложений, вычитаний и умножений - три деления - но без функций sqrts или trig.Очевидно, это займет больше времени, чем чистые 2D-кальки, но в зависимости от сложности эвристики проекции и кальков, это может оказаться самым быстрым маршрутом.

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

Answer 2

Пример вычисления барицентрических координат в трехмерном пространстве по запросу ОП. Дано:

• 3D точки v0, v1, v2, которые определяют треугольник
• 3D-точка p, которая лежит на плоскости, определяемой v0, v1 и v2, и внутри треугольника, натянутого на те же точки.

«х» обозначает перекрестное произведение между двумя трехмерными векторами.
«len» обозначает длину трехмерного вектора.
«u», «v», «w» - это барицентрические координаты, принадлежащие v0, v1 и v2 соответственно.

triArea =   len((v1 - v0) x (v2 - v0)) * 0.5
u =       ( len((v1 - p ) x (v2 - p )) * 0.5 ) / triArea
v =       ( len((v0 - p ) x (v2 - p )) * 0.5 ) / triArea
w =       ( len((v0 - p ) x (v1 - p )) * 0.5 ) / triArea

=> p == u * v0 + v * v1 + w * v2

Кросс-произведение определяется следующим образом:

v0 x v1 := { v0.y * v1.z - v0.z * v1.y,
             v0.z * v1.x - v0.x * v1.z,
             v0.x * v1.y - v0.y * v1.x }

Answer 3

Чтобы спроецировать точку p на плоскость, определенную вершинами v0, v1 и v2, вы должны вычислить матрицу вращения. Назовем спроецированную точку pd

e1 = v1-v0
e2 = v2-v0

r = normalise(e1)
n = normalise(cross(e1,e2))
u = normalise(n X r)

temp = p-v0

pd.x = dot(temp, r)
pd.y = dot(temp, u)
pd.z = dot(temp, n)

Теперь pd можно спроецировать на плоскость, установив pd.z = 0 Также pd.z - расстояние между точкой и плоскостью, определяемой 3 треугольниками. т.е. если проецируемая точка находится в треугольнике, pd.z - это расстояние до треугольника.

Еще один момент, на который следует обратить внимание, заключается в том, что после поворота и проецирования на эту плоскость вершина v0 лежит в начале координат, а v1 лежит вдоль оси x.

НТН

Answer 4

После долгих обсуждений на самом деле есть довольно простой способ решить исходную проблему - узнать, какую ось отбрасывать при проецировании в 2D-пространство.Ответ описан в 3D Math Primer для графики и разработки игр следующим образом ...

"Решение этой дилеммы состоит в том, чтобы выбрать плоскость проекции, чтобы максимизироватьплощадь спроецированного треугольника. Это можно сделать, изучив нормаль плоскости; координата, имеющая наибольшее абсолютное значение, - это координата, которую мы будем отбрасывать. Например, если нормаль равна [–1, 0, 0], томы бы отбросили значения x вершин и p, проецируя на плоскость yz. "

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

Использование нормали плоскости столкновения (которую можно предварительно рассчитать для эффективности) для определения, какую ось отбрасывать при проецировании в 2D, поэтому является наилучшим подходом.

Answer 5

Обновление: не учитывать, этот подход работает не во всех случаях

Я думаю, что нашел правильное решение этой проблемы.

NB. Мне нужна проекция в 2D-пространство, а не работа с 3D-барицентрическими координатами, так как передо мной стоит задача создать максимально эффективный алгоритм. Дополнительные издержки, возникающие при поиске подходящей плоскости проекции, должны быть меньше накладных расходов, возникающих при использовании более сложных операций, таких как функции sqrt или sin () cos () (я думаю, я мог бы использовать таблицы поиска для sin / cos, но это увеличило бы след памяти и побеждает цель этого назначения).

Мои первые попытки нашли дельту между значениями min / max на каждой оси многоугольника, затем удалили ось с наименьшей дельтой. Однако, как предполагает @PeterTaylor, в некоторых случаях падение оси с наименьшей дельтой может привести к прямой линии, а не к треугольнику при проецировании в 2D-пространство. ЭТО ПЛОХО .

Поэтому мое пересмотренное решение выглядит следующим образом ...

1. Найдите каждую субдельту на каждой оси для многоугольника {abs (v1.x-v0.x), abs (v2.x-v1.x), abs (v0.x-v2.x)}, это приводит к в 3 скалярных значениях на ось.
2. Затем, умножьте эти значения масштабера, чтобы вычислить оценку. Повторите это, вычисляя оценку для каждой оси. (Таким образом, любые 0 дельт приводят к нулю, автоматически удаляя эту ось, избегая вырождения треугольника)
3. Удалите ось с наименьшей оценкой, чтобы сформировать проекцию, например, Если наименьшее значение получено по оси x, спроецируйте на плоскость y-z.

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

Answer 6

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

Строго не нужно вообще искать «лучшую» проекцию, только ту, которая достаточно хороша и не вырождается в линию при проецировании в 2D.

EDIT - алгоритм удален из-за вырожденного случая, о котором я не думал

Answer 7

Я не уверен, что это предложение на самом деле лучшее.Нетрудно проецироваться на плоскость, содержащую треугольник.Здесь я предполагаю, что p фактически находится в этой плоскости.

Пусть d1 = sqrt ((v1-v0). (V1-v0)) - то есть расстояние v0-v1.Аналогично, пусть d2 = sqrt ((v2-v0). (V2-v0))

v0 -> (0,0)v1 -> (d1, 0)

А как насчет v2?Ну, вы знаете расстояние v0-v2 = d2.Все, что вам нужно, это угол v1-v0-v2.(v1-v0). (v2-v0) = d1 d2 cos (тета).Wlog Вы можете принять v2 как положительный y.

Затем примените аналогичный процесс к p, с одним исключением: вы не можете обязательно считать его положительным y.Вместо этого вы можете проверить, имеет ли он тот же знак y, что и v2, взяв знак (v1-v0) x (v2-v0).(V1-V0) х (р-у0).

В качестве альтернативного решения вы можете использовать решатель линейной алгебры в матричном уравнении для тетраэдрического случая, взяв в качестве четвертой вершины тетраэдра v0 + (v1-v0) x (v2-v0).) и нормализует при необходимости.