Всем привет! Меня зовут Евгений, я backend‑разработчик в компании Bimeister. Сегодня я хотел бы продолжить рассказ о нашем 3D движке Spatium. В статье речь пойдет еще об одном из алгоритмов оптимизации - поиске и удалении избыточных вершин из 3D моделей.
Материал может представлять интерес для инженеров, связанных с проектированием и разработкой в области 3D.
Контекст
В компьютерной графике геометрия может задаваться различными способами - списком граней, таблицей углов, вершинным или "крылатым" представлениями и т.д. Поэтому для работы с различными форматами моделей в едином пространстве сперва следует привести геометрии разных представлений к некоторому унифицированному описанию. Такое описание в общем виде представляет собой набор позиций вершин (точек в пространстве с тремя координатами x, y, z) и нормалей вершин (векторов с тремя компонентами x, y, z), сопоставленных с этими позициями. Если соединить три вершины отрезками, то получится треугольник. Этот треугольник графический процессор может либо закрасить каким-либо цветом, либо "натянуть" на него текстуру. А нормали нужны для правильного расчета отражений и теней при использовании света (без света мы ничего не увидим). Совокупность таких треугольников образует так называемый "меш" - фигуру, которая определяет форму многогранного объекта в пространстве.
Чем сложнее и детализированнее форма фигуры, тем больше вершин и треугольников, ее описывающих, она содержит. Дополнительное увеличение числа треугольников может быть вызвано тесселяцией или экспортом во внешний для среды моделирования формат. Во всех этих случаях может произойти так, что число треугольников в геометрии превысит минимальное количество, необходимое и достаточное для корректной отрисовки геометрии видеокартой. Это значит, что использование памяти на хранение информации будет увеличено, но данная информация никакой практической пользы нести не будет - на форму геометрии лишние треугольники, образованные избыточными вершинами, влияния не оказывают. Возникает желание эти избыточные вершины удалить, чтобы уменьшить потребление памяти на хранение, передачу и обработку этой геометрии. Для краткости такую оптимизацию будем называть "фильтрацией геометрии". Сразу сделаем оговорку о принципиальной разнице с другой оптимизацией, при которой из геометрии тоже удаляются вершины - упрощением. При упрощении форма геометрии меняется, а при фильтрации - нет.
Итак, под избыточными будем понимать такие вершины, удаление которых из геометрии не приведет к потере ее формы.
Кроме того, есть несколько ограничений:
Геометрия для нас - это два массива: массив координат вершин (позиций) и массив нормалей вершин. Поэтому работу ведем не просто с координатами, а с парами координата-нормаль. Если у нескольких вершин одинаковая координата (позиция), но нормали отличаются - для нас это разные вершины.
Вершины имеют матрицу трансформации. Нас будет интересовать компонент этой матрицы, отвечающий за масштаб.
В полигонах могут быть отверстия.
В результате оптимизации форма исходной геометрии должна сохраниться.
Наша оптимизация будет состоять из нескольких этапов. Далее рассмотрим каждый из них подробнее.
Этап 1 - Поиск и удаление вырожденных треугольников
Под вырожденными треугольниками будем понимать такие треугольники, у которых:
Две или более вершины совпадают.
Все три вершины расположены на одной прямой.
Зачем их искать? Вырожденные треугольники не определяют никакой формы, а память используют. Поэтому очищать геометрию начнем именно с них.
Вспоминаем про ограничения 1 и 2. Решим для себя, с какой приемлемой точностью позиционирования мы будем работать: для этого определим порядок характерных расстояний (мм, см, м, км). Если ваша предметная область - это заводы с размерами в сотни метров, то отрисовка треугольников с микронной точностью - явно избыточная (разница в 7-9 порядков).
Поэтому округляем до установленной величины с учетом масштаба, проверяем признаки вырождения, лишнее удаляем.
Этап 2 - Получение топологии геометрии
Топология геометрии понадобится для поиска различных участков, таких как границы полигонов, группы смежных треугольников и т.п.
Строим треугольники из пар позиция-нормаль. Затем для каждого треугольника:
Вычисляем по правилу правой руки нормаль, уточняем ориентацию этой нормали по нормалям вершин.
Строим ребра (нам важен хэш центра каждого ребра), запоминаем их.
После того, как все треугольники построены, наполняем словари "Вершина - Треугольники с этой вершиной" и "Треугольник - Смежные с ним треугольники". Они как раз пригодятся для разделения полигонов-кандидатов по областям смежности и определения их границ (ограничение 3).
Этап 3 - Поиск полигонов с потенциально избыточными вершинами
Поскольку форму геометрии изменять нельзя (ограничение 4), то будем работать с избыточными вершинами в рамках полигона. Полигоном будем считать набор треугольников, лежащих в одной плоскости.
Но сперва нужно найти подходящий полигон. Как это сделать? Вспоминаем, что у каждой вершины есть нормаль. Для любой точки плоскости нормаль будет одинаковой. Значит, нам нужно сгруппировать вершины по нормалям. Затем нужно проверить несколько условий:
Количество точек в группе должно быть больше трех (больше одного треугольника в плоскости).
Количество точек в группе должно быть кратно трем (геометрия в "сыром" виде, индексация вершин отсутствует).
Все точки в группе не должны принадлежать одной прямой.
Все точки в группе должны принадлежать одной плоскости - вершины могут иметь одинаковые нормали, но лежать в нескольких параллельных плоскостях с одинаковой ориентацией в пространстве.
Кроме того, даже располагаясь в одной плоскости, вершины с одинаковыми нормалями могут принадлежать разным полигонам. Поэтому нужно их разделить по "областям связности" - треугольникам со смежными ребрами.
Предварительно можно сгруппировать по нормалям сами треугольники, а группировку вершин по нормалям проводить уже внутри группы треугольников.
Те группы вершин, которые удовлетворяют всем перечисленным условиям, становятся полигонами-кандидатами на прохождение фильтрации. Отправляемся дальше.
Этап 4 - Поиск и удаление избыточных вершин
Для каждого полигона-кандидата нужно найти вершины, которые образуют границы полигона: внешнюю (оболочку) и внутренние (отверстия).
Вершины, которые не попали в список граничных, считаем избыточными - они расположены в "теле" полигона и не несут полезной информации о его форме.
А для граничных вершин строим отрезки, которые проверяем на принадлежность прямой. Если таких позиций больше двух, то избыточными будут позиции "внутри" отрезка - они тоже ничего не говорят о форме полигона.
Этап 5 - Ретриангуляция очищенных полигонов
Поскольку видеокарта работает с треугольниками, после удаления вершин полигон нужно снова превратить в набор треугольников, т.е. - триангулировать.
Поскольку мы имеем дело с полигонами, у которых могут быть отверстия, то нужно не забыть это учесть. Подходящим для нас алгоритмом будет триангуляция Делоне в ограничениях - граничные ребра будут учтены и не потеряются (неплохой визуальный пример здесь).
Ура! Полигон очищен, заново триангулирован и готов отправиться в видеокарту. Осталось только удалить все вхождения найденных избыточных вершин из исходной геометрии, после чего добавить в нее новые данные из триангуляции. Готово, можем сохранять меш и использовать вместо исходного.
Заключение
Удаление избыточных вершин с сохранением формы - это алгоритм, который может быть полезен, если ваша система работает с большим количеством неоптимизированных геометрий, которые нельзя упрощать.
Мы проводили исследования его эффективности на моделях нашей предметной области, спроектированных в САПР. Согласно результатам, для таких моделей данная оптимизация может быть весьма затратной по мощностям и времени (особенно для больших геометрий в несколько миллионов вершин), а итоговый эффект достаточно низкий - избыточными определяются менее 0.5% от всех вершин. Как правило, это центр круга (рисунок 5, сверху).
Возможно, что для моделей, полученных другими способами (сканирование, художественное моделирование, многоэтапная конвертация и т.п.) эффект будет более выраженным, но такие исследования мы не проводили.
Поэтому принимать решение о том, использовать данный алгоритм или нет - нужно индивидуально для каждого проекта, ориентируясь на предварительную оценку количества "пустых" данных в моделях конкретной предметной области.
