Как Houdini вдохновил меня на процедурную генерацию мешей в Unity

Вступление

Я весьма редко пишу статьи по 3д графике, т.к. мне кажется что все это уже сто раз сказано и написано. Но на собеседованиях, особенно при поиске младших разработчиков, я обратил внимание, что 9 из 10 кандидатов этот вопрос ставил в тупик: “сколько необходимо вершин, чтобы нарисовать на GPU кубик (допустим, в Unity) с корректным освещением?”. Под корректным освещением подразумевается равномерное затенение граней (это важная подсказка). Для особо хитрых любителей экономить на треугольниках дополнительное условие — transparency и discard использовать нельзя. Остановимся на условности, что мы будем использовать по 2 треугольника на грань.

Итак, сколько вершин нам понадобится?

Если вы ответили 8 — погнали читать первую часть. Если 24 — переходите сразу ко второй, где я делюсь идеями реализации своего очередного пет-проекта процедурных мешей с кастомными атрибутами и Houdini-подобным разделением доменов. В рамках описанного выше стандартного представления это корректный ответ. Будем рассматривать стандартный случай realtime-рендера в Unity: indexed mesh, где шейдинг задаётся через vertex-атрибуты (в частности нормали), а грани куба должны оставаться жёсткими (без сглаживания между ними).

Часть 1. Про меши в реалтайме (на примере Unity)

В Unity и других realtime-движках меш задаётся через vertex buffer и index buffer. Вокруг этого есть CPU-абстракции (в Unity — Jobs-friendly MeshData и более старый managed Mesh).

Vertex buffer — массив вершин с их данными. Вершина — запись фиксированного формата с набором атрибутов: позиция, нормаль, tangent, UV, цвет и т.д. Эти атрибуты не обязаны использоваться «по назначению» в шейдерах. Все вершины логически имеют одинаковую структуру и адресуются по индексу (хотя на практике атрибуты могут храниться в нескольких vertex streams).

Index buffer — массив индексов, определяющий, как вершины соединяются в поверхность. При треугольной топологии каждые три индекса образуют один треугольник.

Итого: меш — это набор вершин с атрибутами и массив индексов, задающий их связность.

Важно различать геометрическую точку и вершину. Геометрическая точка — просто позиция в пространстве. Вершина — элемент меша, где позиция хранится вместе с атрибутами, например нормалью. Если вы пришли в realtime-графику из Blender или 3ds Max, возможно вы привыкли думать о нормали как о свойстве полигона. Но здесь это не так. Полигон в итоге на GPU всё равно сводится к треугольникам, нормаль обычно хранится в вершине, передаётся из вершинного шейдера и интерполируется по поверхности треугольника на этапе растеризации. Во фрагментный шейдер она уже приходит интерполированной.

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

Иллюстрация. Для наглядности - сам куб.

В каждом углу сходятся три грани. Если использовать одну вершину на угол, она будет шариться между несколькими гранями и иметь только одну нормаль — в результате при интерполяции значений по треугольникам освещение начнёт сглаживаться между гранями. Куб будет выглядеть «скруглённым», а на треугольниках появятся артефакты интерполяции нормалей.

Важно отметить, что дублирование вершин необходимо не только из-за нормалей. Любое различие в атрибутах (например UV, tangent, цвет или веса скиннинга) требует отдельной вершины, даже если позиции совпадают. Фактически вершина — это уникальная комбинация всех её атрибутов, и если хотя бы один из них отличается, необходима новая вершина.

Пример 1. Мы попытались уложиться в 8 вершин и 12 треугольников (36 индексов). Нам явно не хватает нормалей чтобы корректно посчитать освещение. Хотя для физического бокса для проверки пересечений этого было бы достаточно.

Чтобы этого не происходило, один и тот же угол используется тремя гранями, поэтому он представлен тремя разными вершинами: у них одинаковая позиция, но разные нормали — по одной для каждой грани. Это позволяет считать освещение для каждой грани независимо и сохранять чёткие рёбра.

В результате куб в рамках такого представления описывается 24 вершинами: по четыре на каждую из шести граней. Index buffer задаёт 12 треугольников — по два на грань — используя эти вершины.

Пример 2. Чёткие грани за счёт того, что вершины не шарятся между треугольниками. Те же 36 индексов, но вершин больше - 24, по 3 на угол.

А что в итоге-то?

Такая структура напрямую соответствует тому, как данные обрабатываются на GPU, поэтому она максимально удобна для рендера. Лёгкая адресация через индексы, компактное хранение, хорошая кэш-локальность и возможность массово обрабатывать вершины делают её также эффективной для линейных преобразований: вращения, масштабирования, перемещения, а также для различных деформаций вроде bend или squeeze. Вся модель легко прогоняется через шейдерный пайплайн без лишних преобразований.

Но все удобство заканчивается когда нам требуется редактирование меша. Связность здесь задана только индексами, а различия в атрибутах (например нормалях или текстурных координатах) приводят к дублированию вершин. По сути это месиво из треугольников. Явная топология здесь не представлена напрямую — она закодирована только через индексы, и её приходится восстанавливать по мере необходимости. Сложно понять, какие грани соседние, где проходят рёбра и как устроена поверхность как единое целое. В результате такие меши неудобны для геометрических операций и решения топологических задач — булевых операций, триангуляции контуров, фасок, разрезов и выдавливания полигонов и других процедурных изменений, где важны именно топологические связи, а не просто набор треугольников. И здесь есть много подходов, которые комбинируются по-разному: Half-Edge, DCEL, face adjacency и т.д., а также сотни их вариаций и комбинаций.

И тут мы переходим ко второй части.

Часть 2. Geometry Attributes + topology

Обожаю процедурное 3D-моделирование, где вся геометрия описывается через набор правил и зависимостей между различными параметрами и свойствами. Такой подход делает объекты и сцены удобными для генерации и модификации. Я много работал с различными 3D-редакторами ещё со времён 3ds max, когда он был не Autodesk, а Discreet, и изучал исходный код разных 3D-библиотек; мне были интересны различные способы представления геометрии на уровне данных. И вот я в очередной раз пришёл к идее реализовать у себя структуру меша и алгоритмов работы с ним, на этот раз ближе к тому, как это сделано в Houdini.

В Houdini геометрия представлена следующим образом: она разбита на 4 уровня: detail, points, vertices и primitives.

Points — это точки в пространстве, которые обязательно содержат позицию (P), но также могут хранить и другие атрибуты. Они не знают ни о каких полигонах или связях — это независимые элементы, используемые примитивами через vertices.

Primitives — это сами элементы геометрии: полигоны, кривые, объёмы. Они определяют форму, но не хранят координаты напрямую, а ссылаются на points через vertices.

Vertices — связующий слой. Это «углы» примитивов: каждый vertex ссылается на point, а primitive хранит список своих vertices. Благодаря этому один point может использоваться в разных примитивах, но с разными атрибутами (например нормалями или UV, то, с чего я собственно начинал эту статью).

Detail — это уровень всей геометрии целиком. Здесь хранятся глобальные атрибуты, общие для всего меша (например цвет или материал).

Итого связь такая: primitive → vertices → points

И это делает меш очень удобным для редактирования и хорошо подходящим для процедурной обработки.

Да что я рассказываю, просто посмотрите

Иллюстрация. В этом примере primitive треугольный, но это не обязательное условие.

Один point может участвовать в нескольких примитивах, а каждый случай использования представлен отдельным vertex.

На кубе это выглядит так. Восемь points задают координаты углов. Шесть primitives задают грани. Для каждой грани создаётся четыре vertices, которые ссылаются на соответствующие points. В сумме получается 24 vertices — по одному на каждое использование точки в гранях.

И вот какие бенефиты мы получаем из этой модели по умолчанию:

• Primitive является полигоном, это несколько упрощает часть операций над геометрией. Например - чуть проще сделать inset и потом extrude.
• UV можно хранить на уровне vertices. Это позволяет задавать разные значения для разных граней, не дублируя сами points — ровно то, что нужно для швов и UV-островов.
• Когда нужно двигать геометрию, мы работаем на уровне points. Меняя позицию point, мы автоматически влияем на все примитивы, которые его используют.
• С нормалями есть выбор по уровню. Как геометрическую величину их можно рассматривать на уровне primitive, но для рендера обычно используются vertex-нормали. Это даёт контроль: можно реализовать smooth groups или hard/soft edges, просто задавая разные нормали на vertices одного и того же point.
• Материалы и любые глобальные параметры удобно задавать на уровне detail — один раз на всю геометрию.

Отдельно важен сам дизайн системы атрибутов. В Houdini есть базовый набор стандартных атрибутов (например @P, @N, @Cd и т.д.), но этим он не ограничен — пользователь может создавать собственные атрибуты на любом уровне: detail, point, vertex или primitive. Это могут быть любые данные: id, маски, веса, параметры генерации или произвольные пользовательские значения с произвольными именами. Такая модель отлично ложится на процедурный подход.

В итоге структура хорошо подходит для процедурного моделирования. Связность описана явно, а данные можно хранить там, где им логически место, не смешивая роли. Нужно подвинуть угол куба — двигаем point. Нужно контролировать шейдинг — работаем с vertex-нормалями. Нужно задать что-то глобальное — используем detail.

Что собственно я и пытаюсь воспроизвести, и вот что у меня получилось:

Итоги

Визуально результат не отличается от стандартного Unity-меша, однако гораздо удобнее в использовании.

Это zero-GC меш (в смысле отсутствия managed-аллоцирований на hot-path), который хранится в модели Point/Vertex/Primitive: 8 points, 6 primitives и 24 vertices. Изначально он не триангулирован: примитивы остаются полигонами (N-gons). У меша два состояния:

• NativeDetail: редактируемое топологическое представление со sparse-структурой (alive-флаги, free-list’ы) и типизированными атрибутами по доменам Point/Vertex/Primitive, включая пользовательские. В нём доступны базовые операции редактирования (добавление/удаление points, vertices, primitives), а нормали можно хранить как на point-, так и на vertex-домене.
• NativeCompiledDetail: плотный read-only snapshot. На этом шаге в contiguous-массивы упаковываются только «живые» элементы, выполняется ремап индексов, а также компилируются атрибуты и ресурсы.

Триангуляция выполняется либо явно (через отдельный NativeDetailTriangulator), либо при конвертации в Unity Mesh (ear clipping + fan fallback), либо локально для точных запросов по конкретному полигону.

Примечание. Обратите внимание: сфера сглажена, шейдинг плавный, при этом прямоугольник остаётся закрашенным без «просачивания» на соседние грани. Это достигается за счёт того, что нормали заданы на уровне points, а цвет — на уровне primitive. При конвертации в Unity Mesh вершины автоматически дублируются только там, где это необходимо; в остальных случаях они переиспользуются.

В качестве примера — динамическое окрашивание сферы через рейкаст. Пайплайн такой: генерируется UV-сфера, добавляются атрибуты цвета, строится BVH по bounds примитивов, по BVH отбираются кандидаты на рейкаст, затем для кандидатов выполняется точный hit-test (для N-gons с локальной триангуляцией), и попавший полигон окрашивается в красный. После этого цвет разворачивается в vertex color и меш запекается в Unity Mesh.

Из приятного: благодаря Burst и Job System часть операций, которые планируется упаковать в нодовый workflow, уже сейчас в тестах работает в 5–10 раз быстрее аналогов в Houdini. При этом не всё рассчитано на realtime, поэтому часть инструментария остаётся оффлайн-ориентированной.

На текущий момент уже перенесены BVH, KD- и Octree-структуры, а также триангулятор LibTessDotNet, переписанный под Native Collections.

порт Libtessdotnet в мою библиотеку https://github.com/speps/LibTessDotNet

Работы ещё много. Есть потенциал для оптимизации, в частности хочется хранить часть изменений аддитивно, по аналогии с модификаторами. Кроме того, логичным следующим шагом выглядит интеграция с нодовой системой из Unity 6.4.