Ранее публиковалась полная картина прославления нового вида вычислительной геометрии — геометрическая алгебра.
Ссылка: Кратко про GA/PGA
В геометрическую алгебру довольно долгий вход из-за сложности теории, на которой она базируется.
Но чтобы немного ощутить, как она работает — можно посмотреть, как в ней решается какая-нибудь простая модельная задача. Например, построение веера прямых, равномерно распределённых между двумя скрещивающимися прямыми в 3D-пространстве.
Результат, который мы ходит увидеть
Содержание:
Минимум теории
Для работы в 3D-пространстве будем использовать проективную геометрическую алгебру (коротко PGA3D).
Все объекты PGA3D (точки, прямые, плоскости, точки на бесконечности, трансформации и пр.) описываются мультивектором, состоящим из 16 чисел.
Здесь мы эти 16 чисел будем записывать в виде вложенного списка:
mv = {s,{nx,ny,nz,d},{vx,vy,vz,mx,my,mz},{px,py,pz,pw},ps}
Примеры мультивекторов:
{0,{1,2,3,4},{0,0,0,0,0,0},{0,0,0,0},0}— плоскость с уравнениемx + 2y + 3z + 4 == 0{0,{0,0,0,0},{0,1,2,3,0,0},{0,0,0,0},0}— прямая в виде Plucker coordinatees{0,{0,0,0,0},{0,0,0,0,0,0},{1,2,3,1},0}— точка с координатами{1,2,3}{0,{0,0,0,0},{0,0,0,0,0,0},{1,2,3,0},0}— вектор в направлении{1,2,3}
Строим веер прямых
Построим прямые La и Lb, и веер из прямых L1..L9 между ними.
1) Строим прямую La
Возьмём в 3D-пространстве точку {0, -4, 2} и вектор {4, 1, 1}. В алегебру PGA3D они загоняются следующим образом:
p1 = {0, {0,0,0,0}, {0,0,0,0,0,0}, {0, -4, 2, 1}, 0}
v1 = {0, {0,0,0,0}, {0,0,0,0,0,0}, {4, 1, 1, 0}, 0}В качестве прямой La зададим прямую, проходящую через p1 в направлении v1. Такая прямая находится по формуле:
$L_A = p_1 \lor v_1$
(здесь «V» — т.н. Regressive product, см. ниже)
Вычисленная прямая:
La = {0, {0,0,0,0}, {0, 8, -1, -12, 0, 0}, {0,0,0,0}, 0}
Например, в языке Haskell код для Regressive Product выглядит так:
Код для вычисления RP на языке Haskell
Формулы для других преобразований далее не будут приводиться. Здесь просто показывается, как в целом выглядят формулы преобразований в PGA.
2) Строим прямую Lb
Возьмём две точки: {1, 2, 3} и {-1, 0, 5}
p2 = {0, {0,0,0,0}, {0,0,0,0,0,0}, {1, 2, 3, 1}, 0}
p3 = {0, {0,0,0,0}, {0,0,0,0,0,0}, {-1, 0, 5, 1}, 0}и выберем Lb такой, чтобы она проходила через них. Такая Lb находится по той же формуле:
$L_B = p_2 \lor p_3$
Вычисленная прямая:
Lb = {0, {0,0,0,0}, {-2, -2, 2, 10, -8, 2}, {0,0,0,0}, 0}
Наши построенные прямые La и Lb (кстати, в мультивекторах прямых также хранится информация об их направлении, оно показано стрелочками):
Прямая La
Прямая Lb
3) Строим трансформацию, переводящую прямую La в прямую Lb
Трансформации (или моторы) — специальные мультивектора PGA, хранящие информацию о том, насколько и куда надо сдвинуть/повернуть что-либо.
$T_0 = \sqrt{L_A/L_B}$
(в GA можно делить мультивектор на мультивектор; также в GA из трансформаций можно извлекать корень — по сути это делает трансформацию ровно в 2 раза меньше)Применив эту формулу, получим:
T0 = {0.42, {0,0,0,0}, {-0.59, -0.08, -0.67, -1.60, -0.77, 0.94}, {0,0,0,0}, 0.89}
4) Создадим из трансформации T0 отмасштабированные трансформации:
$T_1 = ScaleMotor[T_1, 0.1]$
$T_2 = ScaleMotor[T_1, 0.2]$
$T_3 = …$
$T_9 = ScaleMotor[T_1, 0.9]$Например, для T1 получится:
T1 = {0.99, {0,0,0,0}, {-0.07, -0.01, -0.08, -0.23, -0.10, 0.08}, {0,0,0,0}, 0.01}
Полная формула для ScaleMotor (её обычно называют логарифмом от мотора) — сильно сложнее приводимой выше для Regressive Product.
Вычисление выглядит примерно так:
- Мотор сначала разбирается на составляющие (ось движения, угол поворота, длина перемещения)
- Затем мотор собирается обратно на базе той же оси, но с другими углом поворота и длиной перемещения
5) Строим веер прямых:
Чтобы построить первую прямую из веера — применяем к прямой La трансформацию T1.
Чтобы построить вторую прямую из веера — применяем к прямой La трансформацию T2.
И т.д.
Например, 5я прямая из веера находится применением Т5 к La по формуле:
$L_5 = T_5 * L_A * \tilde{T_5}$
(здесь под умножением подразумевается т.н. Geometric Product между 3-мя мультивекторами, а значок тильды означает операцию Reverse над мультивектором)
Применив эту формулу, в числах мы получим:
L5 = {0, {0,0,0,0}, {-5.52, 3.96, 4.33, 1.69, -13.69, 14.69}, {0,0,0,0}, 0}
Получив таким образом все прямые веера (от L1 до L9) и построив их в 3D-пространстве, мы и получаем картинку из начала статьи.
При использовании уже готового PGA движка пользователю не надо знать как численно высчитываются сами формулы (Regressive Product, Motor Scaling, Reverse и т.д.). Надо только знать, что «в таком-то случае используется Regressive Product, в таком-то Reverse» и т.п.
Исходные прямые La и Lb и веер прямых L1..L9 между ними
А теперь самое главное
Если мы захотим, например, построить такой же веер, но теперь не прямых, а плоскостей — формулы будут по сути те же самые!
Построение:
Прямая по 2м точкам: $p_1 \lor p_2$
Плоскость по 3м точкам: $p_1 \lor p_2 \lor p_3$
Трансформация:
Перевод прямой 1 в прямую 2:
$T = \sqrt{line_1/line_2}$
$line_2 = T * line_1 * \tilde{T}$
Перевод плоскости 1 в плоскость 2:
$T = \sqrt{plane_1/plane_2}$
$plane_2 = T * plane_1 * \tilde{T}$
Веер плоскостей
(стрелочки показывают ориентацию, т.е. направление нормалей плоскостей)
Кстати, если вдруг наши прямые или плоскости будут оказываться параллельными/прямыми/совпадающими — формулы всё так же будут работать.
Обобщаем полученный Experience
Формулы всяких разных построений и трансформаций — одинаковы для плоскостей и прямых (кстати, для точек тоже).
В других аспектах картина схожая:
- Формула проекций — одинаковая для точек/прямых/плоскостей
- Формулы построения плоскости по 3м точкам, либо по одной точке и 2м векторам, либо по прямой и точке — практически одинаковы
- Формулы автоматически учитывают вырожденные случаи (параллельные прямые и т.п.)
- Формулы из параграфа «а теперь самое главное» для PGA2D — такие же, как и для PGA3D