Mesh Processing

Каждый персонаж в Pixar фильме - это полигональная сетка, прошедшая через subdivision, ремешинг и параметризацию. Модель героя может иметь 10 миллионов полигонов при создании и 500 тысяч при рендеринге. Алгоритм QEM был опубликован в 1997 году и до сих пор используется в Blender, Maya и игровых движках без принципиальных изменений. Понимание mesh processing - это понимание того, как работают 3D-редакторы, игровые движки и системы компьютерного зрения.

• **Игровые движки (Unreal, Unity):** LOD (Level of Detail) системы используют QEM для автоматической генерации упрощённых версий моделей при удалении от камеры
• **OpenSubdiv (Pixar):** открытая библиотека Catmull-Clark subdivision, используемая в Maya, Houdini, Blender для создания гладких персонажей из грубых cage-моделей
• **3D-сканирование (медицина, архив):** ремешинг преобразует неравномерные скан-сетки в структурированные сетки, пригодные для симуляции и анализа

Упрощение сеток: QEM и иерархии деталей

3D-модель персонажа для игры AAA-класса может содержать 10 миллионов полигонов. На расстоянии 50 метров от камеры визуально различимы только 500. Упрощение сетки (mesh simplification) сокращает число треугольников, сохраняя форму. Алгоритм Quadric Error Metrics (QEM) Гарланда-Хекберта (1997) решает эту задачу итеративным схлопыванием рёбер: на каждом шаге удаляется ребро, схлопывание которого вносит минимальную ошибку формы. Ошибка измеряется как сумма квадратов расстояний от новой вершины до смежных плоскостей.

QEM хранит для каждой вершины матрицу Q (4x4 симметричная), накапливающую квадратичные ошибки смежных граней. При схлопывании ребра (v1, v2) новая вершина v* минимизирует v^T * (Q1 + Q2) * v. Сложность: O(n log n) при использовании heap по стоимости рёбер.

Сабдивизия: Loop и Catmull-Clark

Сабдивизия - операция, обратная упрощению: каждый треугольник разбивается на несколько, а вершины перемещаются по правилам схем сглаживания. Pixar использует Catmull-Clark (1978) для квадратичных сеток - именно его применяли при создании Toy Story, Monsters Inc и всех последующих фильмов. Loop subdivision (1987) работает с треугольными сетками. После k итераций сетка приближается к гладкой поверхности C2-непрерывности (почти везде). Ключевое свойство: лимитная поверхность определена аналитически - не нужно бесконечно итерировать.

Loop subdivision: новая вершина ребра (v1, v2) со смежными v3, v4: v_edge = 3/8*(v1+v2) + 1/8*(v3+v4). Старая вершина с n соседями: v_new = (1-n*beta)*v + beta*sum(neighbors), где beta = 1/n*(5/8 - (3/8 + 1/4*cos(2pi/n))^2).

Ремешинг: изотропный и адаптивный

Исходные 3D-сканы имеют неравномерное распределение треугольников: плотные там, где сканер был близко, разреженные - там, где далеко. Ремешинг перестраивает топологию сетки для достижения нужного качества: изотропный ремешинг стремится к равносторонним треугольникам равного размера, адаптивный - к мелким треугольникам в зонах высокой кривизны и крупным - на плоских участках. Алгоритм Botsch-Kobbelt (2004) итеративно применяет: разбиение длинных рёбер, схлопывание коротких, flip рёбер для улучшения валентности, сглаживание Лапласа.

Целевая длина ребра h определяет качество: ребро длиннее 4/3*h разбивается, короче 4/5*h схлопывается. Для адаптивного ремешинга h масштабируется по кривизне: h = h_min в зонах max curvature, h = h_max на плоских участках.

Параметризация: UV-развертка без искажений

Параметризация сетки - отображение 3D-поверхности на 2D-плоскость (UV-пространство). Это нужно для нанесения текстур, запекания карт нормалей, UV-развертки. Задача принципиально не решается без искажений: теорема Гаусса Egregium запрещает изометрическое развёртывание поверхностей с ненулевой гауссовой кривизной. Все алгоритмы балансируют между углом (conformal - сохраняет углы, но меняет площади) и площадью (authalic - сохраняет площади, но меняет углы). LSCM (Least Squares Conformal Maps) - отраслевой стандарт.

LSCM минимизирует конформную энергию: E = sum_triangles |du/dx - dv/dy|^2 + |du/dy + dv/dx|^2 * area. Это разреженная система линейных уравнений, решаемая за O(n) итераций (conjugate gradient). Используется в Blender, Maya, 3ds Max.

Ключевые идеи

• **QEM упрощение:** итеративное схлопывание рёбер по квадратичной ошибке. O(n log n), индустриальный стандарт. Используется в Blender, Maya, Unreal LOD.
• **Subdivision (Loop, Catmull-Clark):** увеличение детализации с гарантией гладкости лимитной поверхности. Pixar использует Catmull-Clark с 1979 года.
• **Изотропный ремешинг:** перестройка топологии для равномерного распределения треугольников. Алгоритм: split/collapse/flip/smooth итерации.
• **UV-параметризация:** отображение 3D -> 2D неизбежно вносит искажения (теорема Гаусса). LSCM минимизирует угловые искажения.

Связанные темы

Обработка сеток связана с базовыми структурами данных и алгоритмами триангуляции.

• 3D Вычислительная геометрия — Базовые структуры данных (half-edge, DCEL) для хранения и обхода сеток
• Триангуляция Делоне — Алгоритмы ремешинга используют критерий Делоне для flip рёбер

Вопросы для размышления

• QEM и subdivision - противоположные операции, но оба сохраняют 'форму'. Что именно значит 'сохранить форму'? Какая метрика используется и почему квадратичная ошибка лучше евклидового расстояния?
• Параметризация поверхности - это всегда компромисс между конформностью и ауталичностью. В каких задачах важнее сохранение углов, а в каких - площадей? Как это влияет на выбор алгоритма?
• Нейронные сети для 3D (PointNet, MeshCNN) работают напрямую с сетками. Нужен ли ремешинг как preprocessing, или сети могут работать с произвольными сетками? Что теряется при пропуске этого шага?

Связанные уроки

• alg-01-big-o