Хабрахабр

[Перевод] Создание разрушаемых мешей

image

Часть 1. Знакомство с Marching cubes

Как создать меш из любого хаоса
В Minecraft мы можем копать в любом направлении, убирая за раз по одному блоку с чётко заданными краями. Но в других играх разработчикам удаётся разрушать рельеф плавно, без кубичности Minecraft.

Вот пример из No Man’s Sky: видео.

Аналогичная техника применяется для отображения изображений с МРТ, metaball-ов и для вокселизации рельефа.

В этой статье мы начнём с рассмотрения двухмерной техники, затем трёхмерной, а в третьей части рассмотрим Dual Contouring. В этой части я расскажу о технике создания разрушаемого рельефа Marching Cubes, а в более общем применении — для создания плавного граничного меша твёрдого объекта. Dual Contouring — это более совершенная техника, создающая тот же эффект.

Наша цель

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

но она не помогает нам отрисовать её. Функция — это отличный способ описания произвольной фигуры.

Алгоритм Marching Cubes берёт такую функцию и создаёт полигональную аппроксимацию её границы, которую можно использовать для рендеринга. Для отрисовки нам нужно знать её границу, например, точки между положительными и отрицательными значениями, где функция пересекает ноль. При переходе в 3d она становится мешем. В 2d эта граница будет непрерывной линией.

Реализация двухмерных Marching Cubes

Примечание: в этом туториале больше рассматриваются концепции и идеи, чем методы реализации и код. Если вам больше интересна реализация, то изучите код на python, в котором содержится откомментированный код со всем необходимым.

Я буду называть алгоритмы в 2d и в 3d «Marching Cubes», потому что по сути они являются одним алгоритмом. Для простоты давайте начнём с 2d, а позже перейдём к 3d.

Шаг 1

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

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

Шаг 2

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

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

Все сочетания двухмерных marching cubes

Шаг 3

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

Отлично! Думаю, это в целом походит на исходный круг, описанный формулой. Но как видите, он весь изломан, а отрезки расположены под углами в 45 градусов. Так получилось, потому что мы решили выбрать вершины границ (красные квадраты), равноудалённые от точек ячейки.

Адаптивность

Лучшим способом избавиться от углов в 45 градусов будет адаптивный алгоритм marching cubes. Вместо простого задания всех вершин границ из центральных точек ячеек их можно расположить так, чтобы они лучше всего соответствовали сплошной области. Для этого нам нужно не только знать, находится ли точка внутри или снаружи; нам требуется также знать, насколько она глубоко расположена.

Она не обязана быть точной, потому что мы используем её только для аппроксимаций. Это значит, что нам нужна какая-то функция, дающая нам меру того, насколько глубоко точка находится внутри/снаружи. В случае нашего идеального круга, имеющего радиус в 2,5 единиц, мы применим следующую функцию.

5 – \sqrt$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/ff9/5b1/cd3/ff95b1cd39b430017a6ed48f91fcd812.svg" alt="$f(x, y) = 2.

В которой положительные значения находятся внутри, а отрицательные — снаружи.

Тогда мы можем использовать численные значения $f$ на любой стороне грани, чтобы определить, насколько далеко вдоль грани нужно расположить точку.

Если соединить всё вместе, то это будет выглядеть так:

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

Часть 2. Трёхмерные Marching Cubes

Итак, в 2D мы разбиваем пространство на сетку, а затем для каждой вершины ячейки вычисляем, где находится эта точка — внутри или снаружи сплошной области. В 2d-сетке у каждого квадрата по 4 угла, и для каждого из них есть два варианта, то есть у каждой ячейки существует $2 \times 2 \times 2 \times 2 = 2^4 = 16$ возможных комбинаций состояний углов.

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

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

И некоторые из этих случаев гораздо более сложны, чем в 2D. Плохая новость заключается в том, что у куба 8 углов, то есть существует $2^{8} = 256$ рассматриваемых возможных случаев.

Вы можете просто скопировать собранные мной случаи и перейти сразу к разделу с результатами («Соединяем всё вместе»), не задумываясь обо всех сложностях. Очень хорошая новость заключается в том, что нам совершенно не нужно в этом разбираться. А потом начать читать о dual contouring, если вам нужна более мощная техника.

Все сложности

Примечание: в этом туториале больше рассматриваются концепции и идеи, чем методы реализации и код. Если вам больше интересна реализация, то изучите реализацию в 3D на python, в которой содержится откомментированный код со всем необходимым.

Отлично, мне это нравится. Вы всё ещё читаете?

Многие из них являются зеркальными отражениями или поворотами друг друга. Секрет заключается в том, что мы на самом деле не обязаны собирать все 256 различных случаев.

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

Остальные два случая можно найти простым поворотом первого случая.

Мы можем использовать ещё один трюк:

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

С учётом всего этого на самом деле нам понадобится рассмотреть всего 18 случаев, из которых мы сможем сгенерировать все остальные.

Единственный разумный человек

Если прочитать статью в Википедии или большинство туториалов по Marching Cubes, то в них говорится, что необходимо всего 15 случаев. Как же так? Ну, на самом деле это правда — три нижних случая с моей схемы не обязательно нужны. Вот снова три этих случая в сравнении с противоположными им другими случаями, дающими схожую поверхность.

И второй, и третий столбцы правильно отделяют сплошные углы от пустых. Но только когда мы рассматривает один куб в отдельности. Если посмотреть на рёбра каждой грани ячейки, то можно увидеть, что они различаются для второго и третьего столбцов. Инвертированные не будут правильно соединяться с соседними клетками, оставляя отверстия в поверхности. После добавления лишних трёх случаев все ячейки правильно соединяются.

Соединяем всё вместе

Как и в двухмерном случае, мы можем просто обработать все ячейки независимо. Вот сферический меш, созданных из Marching Cubes.

Как видите, форма сферы в целом сделана правильно, но в отдельных частях есть хаос из узких сгенерированных треугольников. Можно решить эту проблему с помощью алгоритма Dual Contouring, который является более совершенным, чем Marching Cubes.

Часть 3. Dual Contouring

Marching Cubes просты в реализации, поэтому часто используются. Но у алгоритма есть множество проблем:

  1. Сложность. Даже несмотря на то, что нам нужно обрабатывать всего по одному кубу за раз, Marching Cubes в результате оказывается довольно сложным, потому что необходимо рассматривать множество разных случаев.

  2. Неопределённость. Некоторые случае в Marching Cubes невозможно очевидным образом разрешить тем или иным способом. Если в 2d у нас есть два противоположных угла, то невозможно сказать, должны они соединяться или нет.

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

  3. Marching Cubes не могут создавать резкие рёбра и углы. Вот квадрат, аппроксимированный с помощью Marching Cubes.

    Углы оказались срезанными. Адаптивность здесь не может помочь — Marching Squares всегда создают прямые отрезки внутри любой ячейки, в которой оказывается угол целевого квадрата.

Что же нам делать?

На сцене появляется Dual Contouring

Примечание: в этом туториале больше рассматриваются концепции и идеи, чем методы реализации и код. Если вам больше интересна реализация, то изучите реализацию на python, в которой содержится откомментированный код со всем необходимым (2d и 3d).

Его недостаток заключается в том, что нам потребуется ещё больше информации об $f(x)$, то есть о функции, определяющей, что является сплошным и пустым. Dual Contouring решает эти проблемы и при этом гораздо более расширяем. Эта дополнительная информация улучшит адаптивность по сравнению с marching cubes. Нам нужно знать не только значение $f(x)$, но и градиент $f'(x)$.

Точки соединяются вдоль каждого ребра, имеющего смену знака, как и в marching cubes. Dual Contouring помещает в каждую ячейку по одной вершине, а затем «соединяет точки», создавая полный меш.

Примечание: слово «dual» («двойственный») в названии появилось потому, что ячейки в сетки становятся вершинами меша, что связывает нас с двойственным графом.

Чтобы «соединять точки» и найти полный меш, мы должны рассматривать соседние ячейки. В отличие от Marching Cubes, мы не можем вычислять ячейки по отдельности. Мы просто находим каждое ребро со сменой знака и соединяем вершины ячеек, соседних с этим ребром. Но на самом деле это намного более простой алгоритм, чем Marching Cubes, потому что здесь нет множества отдельных случаев.

Получение градиента

В нашем простом примере с 2d-кругом радиуса 2,5 $f$ задаётся следующим образом:

5 – \sqrt{x^2 + y^2}$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/ff9/5b1/cd3/ff95b1cd39b430017a6ed48f91fcd812.svg" alt="$f(x, y) = 2.

(другими словами, 2,5 минус расстояние от центральной точки)

Воспользовавшись дифференциальным исчислением, мы можем вычислить градиент:

$f'(x, y) = \text{Vec2}\left(\frac{-x}{\sqrt{x^2 + y^2}}, \frac{-y}{\sqrt{x^2 + y^2}} \right)$

Градиент — это пара чисел для каждой точки, обозначающих, насколько изменяется функция при движении по оси x или y.

Мы просто можем измерить изменение $f$, когда $x$ и $y$ отклоняются на небольшую величину $d$. Но для получения функции градиента нам не потребуются сложные вычисления.

$f'(x, y) \approx \text{Vec2}\left(\frac{f(x+d, y) – f(x-d, y)}{2d}, \frac{f(x, y+d) – f(x, y-d)}{2d} \right)$

Это сработает для любой гладкой $f$, если выбранное $d$ достаточно мало. На практике оказывается, что достаточно гладкими оказываются даже функции с острыми точками, потому что для того, чтобы это работало, необязательно вычислять градиент рядом с острыми участками. Ссылка на код.

Адаптивность

Пока мы получили такой же ступенчатый вид, который был и у Marching Cubes. Нам нужно добавить адаптивности. В алгоритме Marching Cubes мы выбирали, где вдоль ребра будет находиться вершина. Теперь мы можем свободно выбирать любую точку внутренностей ячейки.

вычисленному значению Мы хотим выбрать точку, наиболее близко соответствующую полученной нами информации, т.е.

$f(x)$

и градиенту. Заметьте, что мы сэмплировали градиент вдоль рёбер, а не в углах.

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

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

Переходим в 3d

Случаи в 2d и в 3d на самом деле не очень отличаются. Ячейка теперь является кубом, а не квадратом. Мы выводим грани, а не рёбра. Но на этом различия заканчиваются. Процедура выбора одной точки в ячейке выглядит так же. И мы по-прежнему находим рёбра со сменой знака, а затем соединяем точки соседних ячеек, но теперь уже четырёх ячеек, что даёт нам четырёхсторонний полигон:

Грань, связанная с отдельным ребром. У неё есть точки в каждой соседней ячейке.

Результаты

Dual contouring создаёт гораздо более естественные формы, чем marching cubes, что можно увидеть на примере созданной с его помощью сферы:

В 3d эта процедура достаточно надёжна, чтобы выбирать точки, находящиеся вдоль ребра острого участка и выбора углов при их возникновении.

Выбор местоположения вершины

Серьёзная проблема, которую я раньше игнорировал, заключается в выборе местоположения точки в случае, когда нормали не указывают в одинаковое место.

В 3d проблема ещё более усугубляется, потому что здесь становится больше нормалей.

Способом решения является выбор точки, которая оказывается взаимно наилучшей для всех нормалей.

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

С математической точки зрения отдельные штрафные функции являются квадратом расстояния от идеальной линии для текущей нормали. Сумма всех квадратных членов является квадратичной функцией, поэтому общая штрафная функция называется QEF (quadratic error function, функцией квадратичной ошибки). Нахождение минимальной точки квадратичной функции — это стандартная процедура, имеющаяся в большинстве библиотек работы с матрицами.

В своей реализации на python я использовал функцию lstsq из numpy.

Проблемы

Колинеарные нормали

Большинство туториалов останавливается на этом, но у алгоритма есть небольшой грязный секрет — решение QEF в соответствии с описанием в оригинальной статье про Dual Contouring на самом деле работает не очень хорошо.

Но на самом деле нет никаких гарантий, что получившаяся точка находится внутри ячейки. Решив QEF, мы можем найти точку, наиболее соответствующую нормалям функции.

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

Я видел много советов по решению этой проблемы. Некоторые люди сдавались, отказываясь от информации градиента и используя вместо него центр ячейки или среднее позиций границ. Это называется Surface Nets, и в таком решении, по крайней мере, есть простота.

Но исходя из своего опыта я рекомендую использовать сочетание двух техник.

Техника 1: решение QEF с ограничениями

Не забывайте, что мы находили точку ячейки, находя точку, минимизирующую значение заданнйой функции, называемой QEF. Внеся небольшие изменения, мы можем найти минимизирующую точку внутри ячейки.

Техника 2: смещение QEF

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

Благодаря этому решение всего QEF стягивается к центру.

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

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

Подробнее обе техники показаны в коде.

Самопересечения

Ещё одна проблема dual contouring заключается в том, что иногда он может генерировать самопересекающуюся 3d-поверхность. В большинстве случаев на это не обращают внимания, так что я не решал эту проблему.

Существует статья, в которой рассказывается о её решении: «Intersection-free Contouring on An Octree Grid», Ju and Udeshi, 2006

Однородность

Хотя получаемый dual contouring меш всегда герметичен, поверхность не всегда является хорошо заданной. Так как на ячейку приходится всего одна точка, при прохождении через ячейку двух поверхностей она будет общей для них. Это называется «однородным» мешем и может вызывать проблемы у некоторых алгоритмов текстурирования. Проблема часто возникает, когда сплошные объекты тоньше, чем размер ячейки или несколько объектов почти касаются друг друга.

Обработка таких случаев является значительным расширением функционала базового Dual Contouring. Если вам нужна эта функция, то рекомендую изучить эту реализацию Dual Contouring или эту статью

Расширение алгоритма

Благодаря относительной простоте создания мешей Dual Contouring гораздо проще расширить до работы со схемами ячеек, отличающихся от рассмотренных выше стандартных сеток. Как правило, алгоритм можно выполнять для октодеревьев, чтобы получить различные размеры ячеек ровно там, где нужны подробности. В целом идея аналогична — выбираем по точке на ячейку с помощью сэмплированных нормалей, затем для каждого ребра со сменой знака находим соседние 4 ячейки и комбинируем их вершины в грань. В октодереве для нахождения этих рёбер и соседних ячеек можно использовать рекурсию. У Мэтта Китера есть подробный туториал об этом.

Хотя я говорил, что у нас для этого есть функция, мы можем извлечь ту же самую информацию из другого меша. Другое интересное расширение заключается в том, что для Dual Contouring нам необходимы всего лишь определение того, что находится внутри/снаружи, и соответствующие нормали. сгенерировать чистое множество вершин и граней, очищающих исходный меш. Это позволяет нам выполнить «ремеш», т.е. В качестве примера можно привести модификатор remesh из Blender.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть