Поиск близнецов при реализации подразделения Катмулла-Кларка с использованием сетки Half-Edge

Этот вопрос был перенесен из Software Engineering Stack Exchange, потому что на него можно ответить в Stack Overflow. Мигрировал 8 лет назад .

Примечание: описание стало немного длиннее, чем ожидалось. Вы знаете читаемую реализацию этого алгоритма, использующую эту сетку? Пожалуйста, дай мне знать!

Я пытаюсь реализовать подразделение Catmull-Clark с помощью Matlab, потому что позже результаты придется сравнивать с некоторыми другими вещами, уже реализованными в Matlab. Первая попытка была с сеткой Vertex-Face, алгоритм работает, но не очень эффективен, так как вам нужна информация о соседстве для ребер и граней. Поэтому сейчас я использую сетку с половинными краями . Смотрите также Разработка структуры данных для многогранных поверхностей , Лутц Кеттнер (ссылка в формате PDF на этой странице).

Моя проблема заключается в том, чтобы найти Twin HalfEdges , я просто не знаю, как это сделать. Ниже я описываю свои мысли по поводу реализации, стараясь сделать их краткими.

Half-Edge mesh (с использованием индексов для Vertices / HalfEdges / Faces):

Vertex (x,y,z,Outgoing_HalfEdge)
HalfEdge (HeadVertex (or TailVertex, which one should I use), Next, Face, Twin).
Face (HalfEdge)

Чтобы не усложнять, предположим, что каждая грань является четырехугольником. Фактическая сетка - это список вершин, полуребрений и граней.Новая сетка будет состоять из NewVertices, NewHalfEdges и NewFaces, например (примечание: Number _... - это номер ... ):

NumberNewVertices: Number_Faces + Number_HalfEdges/2 + Number_Vertices
NumberNewHalfEdges: 4 * 4 * NumberFaces
NumberNewfaces: 4 * NumberFaces

Catmull-Clark:

Find the FacePoint (centroid) of each Face:
--> Just average the x,y,z values of the vertices, save as a NewVertex. 
Find the EdgePoint of each HalfEdge:
--> To prevent duplicates (each HalfEdge has a Twin which would result in the same HalfEdge)
--> Only calculate EdgePoints of the HalfEdge which has the lowest index of the Pair.
Update old Vertices

Хорошо, теперь все новые вершины вычисляются (однако их Outgoing_HalfEdge пока неизвестен). Следующий шаг, чтобы сохранить новые HalfEdges и Faces. Эта деталь вызывает у меня проблемы!

Loop through each old Face, there are 4 new Faces to be created
  (because of the quadrilateral assumption)
First create the 4 new HalfEdges per New Face, starting at the FacePoint to the Edgepoint
Next a new HalfEdge from the EdgePoint to an Updated Vertex
Another new one from the Updated Vertex to the next EdgePoint
Finally the fourth new HalfEdge from the EdgePoint back to the FacePoint.

HeadVertex каждого нового HalfEdge известен, Next HalfEdge тоже. Лицо также известно (поскольку это новое лицо, которое вы создаете!). Неизвестен только Twin HalfEdge , откуда мне это знать?

Между прочим, во время цикла по вершинам новой грани назначьте Outgoing_HalfEdge вершинам. Вероятно, это то место, где можно узнать, какой HalfEdge является Близнецом.

Наконец, после создания 4 новых HalfEdges, сохраните Face с индексом HalfVertex последнего вновь созданного HalfVertex.

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

Редактировать : Спасибо за перемещение моей темы. Я разместил ссылку на исходный код в комментарии, обратите внимание, что эта реализация рассматривает общие полигональные сетки, а не только четырехугольные.

Кроме того, близнецов новых HalfEdges 1 и 4 (красные числа на каждой новой грани) довольно легко найти, если вы рассмотрите старое четырехугольное лицо, разделенное на 4 новых грани (зеленые числа):

enter image description here

Итак, как найти Twins 2- и 3 HalfEdges?

задан eh9 8 November 2012 в 22:56

0 ответов

Другие вопросы по тегам:

algorithm matlab graphics 3d polygon

Поиск близнецов при реализации подразделения Катмулла-Кларка с использованием сетки Half-Edge

0 ответов

Похожие вопросы: