Быстрый алгоритим заполнения half-edge структуры (WIP)

Общее описание

Алгоритм расчитан на применение с полигональными сетками с индексной адресацией, т.е. не с указателями.

Индексация в описании ниже начинается с 0. Под ссылкой обычно понимается индекс, если не сказано иного.

Основные этапы:

1. Создание геометрии меша. Установка вершин для всех граней. Рёбра, полурёбра и все ссылки на них заполняются заведомо не правильным индексом, чтобы потом можно было проверить заполнена ссылка или нет.
2. Проход по всем граням заполняя данные рёбер и полурёбер, вычисляя индексы (подробный алгоритм показан ниже).

Вычисление индексов рёбер и полурёбер

Пусть индексы полурёбер ребра будут ei*2 и ei*2+1, где ei индекс ребра. Тогда зная индекс ребра мы можем узнать индексы его полурёбер, и наоборот, зная один из индексов полурёбер можно узнать индекс ребра и парного полуребра.

Нахождение индексов полурёбер по индексу ребра:

hei1 = ei*2
hei2 = ei*2+1

Найти индекс ребра для обоих полурёбер можно просто разделив их индексы на 2:

ei = hei1 / 2
ei = hei2 / 2

Нахождение парного полуребра:

pair = (hei&1) ? hei-1 : hei+1

Таким образом ссылку на пару в полуребе можно не хранить, т.к. она быстро вычисляется. А также ссылку на ребро из полуребра, и ссылку на полуребро из ребра.

Заполнение граней

Структура полигональной сетки с данными half-edge ограничена возможностью иметь максимум две грани вокруг ребра, таким образом проходя по рёбрам мы можем иметь дело с рёбрами трёх видов: которые ещё не были использованы, которые были использованы один раз, и с рёбрами, которые были использованы два раза. Дважды использованные рёбра можно исключать из расмотрения, т.к. известно, что вокруг них больше не будет граней, требующих обработки. Т.е. нужно хранить только те рёбра, которые были использованы один раз. Если ребра нет в этом списке, то либо оно ещё не создано, либо для него уже создано всё что можно и про него можно забыть. Для экономии памяти для хранения единожды использованных рёбер эффективно использовать двусвязный список, т.к. массив будет потреблять гораздо больше памяти (нужно будет хранить элемент для каждого ребра) и что более страшно, для поиска ребра по вершинам нужно будет просматривать весь массив, а в случае со списком только единожды использованные рёбра храняться в списке, а это число по крайней мере на порядок меньше общего числа рёбер.

Таким образом проходя по вершинам грани мы знаем только индексы текущей и следующей вершин.

vi = i
nvi = ((v_num-1) == i) ? 0 : i + 1

Всё остальное мы можем либо вычислить либо создать.

Проверяем использовалась ли вершина nvi в других гранях. Для этого получаем ссылку на полуребро вершины v_data[nvi].half_edge.

Если индекс корректный, то вершина использовалась и какое-нибудь ребро с этой вершиной уже лежит в списке (или уже удалено) и нам нужно его найти пройдя список и сравнив индексы vi и nvi с индексами начала и конца каждого ребра в списке. Если ничего не найдено создаём новое ребро, заполняем данные для нового ребра и его полурёбер и создаём элемент в списке для нового ребра. Если найдено, то заполняем оставшиеся данные и удаляем ребро из списка.

А если индекс полуребра вершины nvi не корректный, то это значит, что вокруг вершины ещё не было заполнено ни одной грани, и нужно просто создать ребро и элемент списка.

В структуре half-edge грани не хранят прямых ссылок на рёбра, доступ к ним возможен только через полурёбра. Грань должна иметь одну ссылку на любое своё полуребро.

Для каждой грани мы проходим по всем её вершинами заполняя данные ребёр между ними.

Реализация

В своей реализации я пойду ещё дальше и удалю ссылку на вершину из данных полуребра, т.к. в моём случае индекс вершины доступен из массива e_verts, где индексы вершин по понятным причинам совпадают с индексами полуребра.

Посмотреть можно тут: moto-mesh.c

Это реализовано в функции moto_mesh_update_he_data, заполнение меша недействительными индексами происходит в функции moto_mesh_new.

Код только что написан и ещё не причёсан. =)

Ограничения

Те же, что и для классической half-edge структуры, в смысле возможных для представления сеток, за исключением висячих рёбер, которые не имеют ни одной прилежашей грани.

P.S.

У меня есть ещё некоторые идеи как можно ускорить этот алгоритм, но они требуют проверки. О прогрессе в этом направлении я напишу.

Для хранения уже задействованных вершин я пробовал использовать матрицу смежности, это конечно на небольших мешах позволяет быстро находить ребро, однако требует памяти как минимум v_num*(v_num+1)/2*sizeof(index_type), что делает новозможным использование этого способа на больших мешах.