Нахождение близнецов при реализации подразделения Catmull-Clark с использованием сетки Half-Edge

Question

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

---

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

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

---

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

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

Для простоты предположим, что каждое лицо является четырехугольником. Фактическая сетка - это список Вершин, HalfEdges и Faces. Новая сетка будет состоять из 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 тоже. Face также известен (так как это новое лицо, которое вы создаете!). Только Twin HalfEdge неизвестно, откуда мне это знать?

Кстати, при прохождении по вершинам новой грани присвойте вершинам Outgoing_HalfEdge . Это, вероятно, место, чтобы узнать, какой HalfEdge является близнецом.

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

---

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

---

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

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

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

Answer 1

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

Чтобы реализовать (один проход) алгоритм, я буду пометить каждый из элементов модели с помощью "недавносоздан флаг, который указывает, был ли элемент создан в результате алгоритма.Цикл верхнего уровня должен повторяться на неизмененных гранях.

1. Сначала убедитесь, что каждый из исходных ребер грани был разделен.При этом создайте список каждой «новой» вершины, указывающей на грань;это середины.- а.Чтобы разбить ребро, мы сначала находим соответствующее пол ребра.Создайте новую вершину.Мы вставляем новую пару половин в каждый связанный список, настраивая конечные точки для новой вершины.Пометьте все четыре полукруга как новую, а также новую вершину.

2. Первая остановка деления грани отличается от других.Создайте новую вершину V, которая будет в середине старого лица, и выберите новую вершину W, падающую на лицо.Мы подключим их следующим образом.Предположим, что связанный список ребер рядом с W выглядит как ..aWb...Создайте новую пару половин ребер c и d.Замените W в связанном списке на WcVdW, чтобы создать список '..aWcVdWb ..'.Это создает «плавающий край» в середине лица.Однако структура данных гарантирует, что у нас есть связанный список пол ребер, которые представляют внутренний периметр многоугольника.Пометить вершину W и половину ребер c и d как новую.

3. Теперь для каждой оставшейся новой вершины мы создадим новую пару пол ребер,но на этот раз каждая пара также создаст новое лицо.Выберите предыдущую ..cVdWb.. последовательность связанного списка.Поскольку все исходное ребро было подразделено, этот список расширяется до ..cVdWbXeYf...X - старая вершина, а Y - новая.Создайте новую пару пол ребер g и g, которые будут соединять вершины V и Y.Извлеките последовательность VdWbXeY из связанного списка и добавьте к ней g, чтобы создать новое лицо [VdWbXeYg].Добавьте половину ребра h, чтобы соединить V и Y на старой грани, чтобы получить ..cVhYf...Пометьте новое лицо как новое.Если новых вершин больше нет, мы закончили.Если нет, сопоставьте имена ..cVhYf.. с ..cVdWb.. для итерации.

Обозначение является довольно неприятным, но концептуально это довольно просто.Каждый из трех шагов добавляет пол ребра в парах;на шаге 1, разделив ребро, на шагах 2 и 3, добавив их.Каждое из этих дополнений сохраняет инварианты инцидентности представления многогранника без изменений, что означает, что вы получаете улучшенную локальность изменений в коде.