Решение для оптимального выравнивания 3d полигональной сетки - PullRequest
Новая
       18

Решение для оптимального выравнивания 3d полигональной сетки

3 голосов
/ 17 ноября 2009

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

Таким образом, проблема заключается в следующем: учитывая положение точек в 3d для некоторых (возможно, всех) вершин в многоугольной сетке, найдите масштабированное вращение, которое минимизирует разницу между преобразованными вершинами и заданными точками. У меня также есть центральная точка, которая может оставаться неизменной, если это поможет. Соответствие между вертами и 3d локациями фиксировано.

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

Примером этого является куб. Прототипом будет единичный куб с центром в начале координат с индексами вершин: 

4----5
|\    \
| 6----7
| |    |
0 |  1 |
 \|    |
  2----3

Пример расположения вертов для подгонки:

  • v0: 1,243,2,163, -3,426
  • v1: 4,190, -0,408, -0,485
  • v2: -1,974, -1,525, -3,426
  • v3: 0,974, -4,096, -0,485
  • v5: 1,974,1,525,3,426
  • v7: -1,243, -2,163,3,426

Итак, учитывая этот прототип и эти точки, как мне найти единичный масштабный коэффициент и вращение вокруг x, y и z, которое минимизирует расстояние между вершинами и этими позициями? Лучше всего, чтобы метод был обобщен для произвольной сетки, а не только для куба.

Ответы [ 2 ]

6 голосов
/ 17 ноября 2009

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

minimize Norm(T*V-M)

, где T - матрица преобразования, которую вы ищете, V - вершины для подгонки, а M - вершины прототипа. Норма относится к норме Фробениуса. M и V являются матрицами 3xN, где каждый столбец является 3-вектором вершины прототипа и соответствующей вершины в подходящем множестве вершин. T - матрица преобразования 3x3. Тогда матрица преобразования, которая минимизирует среднеквадратичную ошибку, равна inverse(V*transpose(V))*V*transpose(M). Результирующая матрица, как правило, не будет ортогональной (вам нужна матрица без сдвига), поэтому вы можете решить матричную задачу Прокруста, чтобы найти ближайшую ортогональную матрицу с SVD.

Теперь, , если вы не знаете, какие заданные точки будут соответствовать каким точкам прототипа, проблема, которую вы хотите решить, называется регистрацией поверхности. Это активная область исследований. См., Например, этот документ , который также охватывает жесткую регистрацию, а это то, что вам нужно.

0 голосов
/ 18 ноября 2009

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

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

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

...