Триангуляция неплоских многоугольников

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

Моими первоначальными идеями были:

  • NURBS
  • Генерация дополнительных точек «внутри полигона» и применение 3D-триангуляции Делоне.
  • Просто поместив одну (или несколько) еще вершин «посередине» и соединив их с вершинами контура.

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

Подробнее. Несмотря на то, что точек на контурах сотни, их можно сгруппировать в 3–10 подмножеств, так что каждое подмножество близко соответствует линии. Однако сгенерированные таким образом линии по-прежнему не лежат в одной плоскости. Можно представить это как стаю птиц, которые летают по многоугольнику, но не точно на одной и той же высоте по вертикали.


3d mesh polygon triangulation
person Violin Yanev    schedule 13.09.2012    source источник
comment
Следующий документ описывает такой алгоритм: Peter Liepa, «Filling Holes in Meshes», SGP 2003.   -  person sloriot    schedule 13.09.2012
comment
Как бы мне не нравилось читать технические статьи, мне нужно готовое к использованию решение в данный момент (библиотека или псевдокод), и я не могу позволить себе реализовать его самостоятельно... Я посмотрю на чтение как как только у меня будет больше времени :) Спасибо!   -  person Violin Yanev    schedule 14.09.2012

Ответы (2)


arrow_upward
0
arrow_downward

Вы можете ознакомиться с библиотекой Point Cloud. Среди прочего, он может выполнять реконструкцию поверхности.

person angainor    schedule 17.09.2012

arrow_upward
9
arrow_downward

В итоге я сделал следующее:

  1. Подгонка плоскости к точкам.
  2. Спроецируйте точки на плоскость.
  3. Преобразуйте точки в систему координат плоскости, чтобы каждая точка имела 2D-координату (x, y) и глубину z.
  4. Вычислите границу облака точек.
  5. Создайте дополнительные 2D-точки внутри границы (можно использовать равноудаленные точки или искаженные точки с любой плотностью).
  6. Запустите двумерную триангуляцию Делоне по всем точкам (граница + сгенерированные точки).
  7. Интерполируйте значения глубины сгенерированных внутренних точек на основе граничных значений глубины. Можно использовать любой вид интерполяции - я использовал triscatteredinterp() MATLAB, который работал достаточно хорошо.
  8. Переведите все точки обратно, используя обратное преобразование из (3)
  9. Используйте триангуляцию из (6) и точки, полученные в (8).

Результат можно увидеть здесь: http://www.youtube.com/watch?v=4AqHxKsM7Iw&feature=g-upl

person Violin Yanev    schedule 21.10.2012
comment
+1 Действительно очень круто! Можете ли вы «выдавить» или сделать трехмерными, или как вы это называете, более сложные структуры? Как бы вы сделали это с конусом? - person angainor; 21.10.2012
comment
Ну, я еще не реализовал кривые. С полигонами уже крайне сложно. Но я думаю, что должно быть возможно заставить его работать и с гладкими объектами. Он работает с довольно сложными структурами. - person Violin Yanev; 22.10.2012