Введение

[[Файл:Polygon Mesh Processing Book Cover. jpg|thumb|right| «Обработка полигональных сеток» Марио Ботша и др. – это учебник по геометрии. Геометрическая обработка является распространенной темой исследований на SIGGRAPH, ведущей академической конференции по компьютерной графике, и основной темой ежегодного симпозиума по обработке геометрии.

Обработка геометрии как жизненный цикл

thumb|Сетка кактуса, показывающая гауссову кривизну в каждой вершине, с использованием метода углового дефекта. Обработка геометрии подразумевает работу с формой, обычно в 2D или 3D, хотя форма может существовать в пространстве произвольной размерности. Обработка формы включает три этапа, известные как её жизненный цикл. При "рождении" форма может быть создана одним из трех способов: на основе модели, математического представления или сканирования. После создания форма может многократно анализироваться и редактироваться в цикле. Обычно это включает получение различных измерений, таких как расстояния между точками формы, её гладкость или эйлерова характеристика. Редактирование может включать шумоподавление, деформацию или выполнение жестких преобразований. На заключительном этапе "жизни" формы она используется. Это может означать, что она отображается как отрендеренный объект в игре или фильме, например. Конец жизненного цикла формы также может быть определен решением относительно её соответствия определенным критериям. Или же она может быть физически изготовлена в реальном мире, например, с помощью 3D-печати или лазерной резки.

Дискретное изображение формы

Как и любая другая форма, формы, используемые в геометрической обработке, обладают свойствами, относящимися к их геометрии и топологии. Геометрия формы касается положения точек формы в пространстве, касательных, нормалей и кривизны. Она также включает в себя размерность пространства, в котором существует форма (например, или ). Топология формы – это набор свойств, которые не изменяются даже после применения к форме гладких преобразований. Она описывает такие характеристики, как количество отверстий и границ, а также ориентируемость формы. Примером неориентируемой формы является лента Мёбиуса. В компьютерах всё должно быть дискретизировано. Формы в геометрической обработке обычно представляются в виде треугольных сеток, которые можно рассматривать как граф. Каждый узел в графе – это вершина (обычно в ), имеющая координаты. Это кодирует геометрию формы. Направленные ребра соединяют эти вершины в треугольники, которые, согласно правилу правой руки, имеют направление, называемое нормалью. Каждый треугольник образует грань сетки. Они носят комбинаторный характер и кодируют топологию формы. Помимо треугольников, для представления формы можно использовать и более общий класс многоугольных сеток. Более продвинутые представления, такие как прогрессивные сетки, кодируют упрощенное представление вместе с последовательностью преобразований, которые после применения создают детализированное или высокоразрешенное представление формы. Такие сетки полезны в различных приложениях, включая геоморфы, прогрессивную передачу, сжатие сеток и селективное уточнение. |thumb|274x274px|Сетка знаменитого Стэнфордского кролика. Формы обычно представляются в виде сетки – набора многоугольников, определяющих контуры формы.

Характерность Эйлера

Одним из особенно важных свойств 3D-формы является ее характеристика Эйлера, которая может быть определена также через ее род. Формула для этого в непрерывном смысле — , где — число связных компонент, — число отверстий (например, как в бублике, см. тор), и — число связных компонент границы поверхности. Конкретным примером является сетка брюк. У нее одна связная компонента, 0 отверстий и 3 связные компоненты границы (пояс и два отверстия для ног). Таким образом, в этом случае характеристика Эйлера равна 1. Для перехода в дискретный мир характеристика Эйлера сетки вычисляется на основе ее вершин, ребер и граней. На этом изображении показана сетка брюк с характеристикой Эйлера 1. Это объясняется уравнением для вычисления характеристики: 2c – 2h + b. Сетка имеет 1 связную компоненту, 0 топологических отверстий и 3 границы (отверстие для пояса и каждое отверстие для ноги): 2 – 0 + 3 = 1.

Реконструкция Пуассона от поверхностных точек до сетки

thumb 339x339px Треугольная сетка строится на основе облака точек. Иногда формы инициализируются исключительно как "облака точек" – набор выборочных точек с поверхности формы. Зачастую эти облака точек необходимо преобразовать в сетки. В зависимости от способа инициализации или "создания" формы, она может существовать лишь как скопление выборочных точек, представляющих её поверхность в пространстве. Для преобразования поверхностных точек в сетку можно использовать стратегию реконструкции Пуассона. Этот метод утверждает, что индикаторная функция – функция, определяющая, какие точки в пространстве принадлежат поверхности формы – может быть вычислена непосредственно на основе выборочных точек. Ключевая идея заключается в том, что градиент индикаторной функции равен нулю везде, кроме выборочных точек, где он равен внутренней нормали к поверхности. Более формально, пусть набор выборочных точек с поверхности обозначен как , каждая точка в пространстве – как , а соответствующая нормаль в этой точке – как . Тогда градиент индикаторной функции определяется следующим образом:

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

Параметризация

Иногда возникает необходимость спроецировать 3D-поверхность на плоскую плоскость. Этот процесс известен как параметризация. Цель состоит в том, чтобы найти координаты u и v, на которые можно отобразить поверхность так, чтобы минимизировать искажения. Таким образом, параметризацию можно рассматривать как задачу оптимизации. Одно из основных применений параметризации сетки — текстурирование.

Метод массовых пружин

thumb|378x378px|Вложение Тутте демонстрирует негладкие параметризации на боковой стороне жука. Один из способов измерения искажений, возникающих в процессе отображения, — это измерение разницы между длиной ребер на 2D-отображении и их длиной на исходной 3D-поверхности. В более формальном виде целевая функция может быть записана как:

Где — множество ребер сетки, а — множество вершин. Однако оптимизация этой целевой функции приведет к решению, отображающему все вершины в одну вершину в UV-координатах. Заимствуя идею из теории графов, мы применяем отображение Тутте и ограничиваем граничные вершины сетки единичной окружностью или другим выпуклым многоугольником. Это предотвращает схлопывание вершин в одну точку при применении отображения. Неграничные вершины затем позиционируются посредством барицентрической интерполяции их соседей. Однако отображение Тутте по-прежнему страдает от значительных искажений, поскольку стремится уравнять длины ребер и, следовательно, некорректно учитывает размеры треугольников на фактической поверхности сетки.

Деформация

Рисунок 394x394px – пример максимально жесткой деформации. Деформация подразумевает преобразование исходной формы в новую. Как правило, эти преобразования непрерывны и не изменяют топологию формы. Современные методы деформации формы на основе сетки учитывают ограничения деформации, заданные пользователем на управляющих точках (выбранных вершинах или областях сетки), и распространяют эти деформации на остальную часть формы плавно, без удаления или искажения деталей. Некоторые распространенные формы интерактивной деформации – точечная, скелетная и деформация с использованием ограничивающей рамки. При точечной деформации пользователь может применять преобразования к небольшому набору точек, называемых управляющими точками, на форме. Скелетная деформация определяет скелет для формы, позволяя пользователю перемещать кости и вращать суставы. Деформация с использованием ограничивающей рамки требует создания рамки вокруг всей или части формы, так что при манипулировании точками на рамке объем, который она охватывает, изменяется соответствующим образом.

Точечная деформация

Ручки обеспечивают ограниченный набор ограничений для деформации: когда пользователь перемещает одну точку, остальные должны оставаться неподвижными. Поверхность покоя, погруженная в пространство, может быть описана отображением , где – двумерная параметрическая область. Аналогично, преобразованную поверхность можно описать другим отображением . В идеале, преобразованная форма должна вносить минимальные искажения в исходную форму. Один из способов моделирования этих искажений – через смещения с использованием энергии, основанной на лапласиане. Применение оператора Лапласа к этим отображениям позволяет измерить изменение положения точки относительно её окрестности, что обеспечивает гладкость ручек. Таким образом, энергия, которую мы хотим минимизировать, может быть записана как:

Хотя этот метод инвариантен к сдвигам, он не учитывает вращения. Схема деформации "Как можно более жестко" применяет жесткое преобразование к каждой ручке i, где – матрица вращения, а – вектор сдвига. К сожалению, вращения невозможно определить заранее, поэтому мы выбираем "наилучшее" вращение, минимизирующее смещения. Однако для достижения локальной инвариантности к вращениям требуется функция , которая определяет наилучшее вращение для каждой точки на поверхности. Соответственно, результирующая энергия должна быть оптимизирована по обоим параметрам и :

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

Сегментация внутри-вне

Хотя это может показаться тривиальным, во многих случаях определение внутренней стороны треугольной сетки от внешней – не простая задача. В общем случае, для заданной поверхности мы формулируем эту проблему как определение функции, которая возвращает 1, если точка находится внутри , и 0 в противном случае. В самом простом случае форма замкнута. В этом случае, чтобы определить, находится ли точка внутри или снаружи поверхности, мы можем провести луч в любом направлении из точки запроса и подсчитать количество раз, когда он пересекает поверхность. Если точка находится снаружи , то луч либо не должен пересекать (в этом случае 0), либо каждый раз, входя в , он должен пересекать дважды, поскольку ограничена, и любой луч, входящий в нее, должен выйти. Таким образом, если точка снаружи, количество пересечений будет четным. Аналогично, если точка внутри, применяется та же логика, но луч должен пересечь на один раз больше при первом выходе. Итак:

Зачастую мы не можем гарантировать, что замкнута. В качестве примера можно привести пару брюк, упомянутых в начале статьи. Эта сетка явно имеет семантическое разделение на внутреннюю и внешнюю стороны, несмотря на наличие отверстий в талии и штанинах. Приближенное определение внутренней и внешней сегментации достигается путем проведения лучей из точки запроса в различных направлениях. Наивная попытка решить эту проблему – провести множество лучей в случайных направлениях и классифицировать точку как находящуюся внутри, если и только если большинство лучей пересекают нечетное количество раз. Чтобы количественно оценить это, предположим, что мы проводим лучей. Мы связываем с этим число , которое является средним значением результатов пересечения лучей. Следовательно:

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

Для замкнутой сетки эквивалентно характеристической функции для объема, представленного . Таким образом, мы говорим:

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