что такое меши в играх

Особенности работы с Mesh в Unity

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

Борьба с подобными трудностями навела нас на мысли об автоматизации и написании статей на эту тему. Большая часть материала коснется работы с Unity 3D, поскольку это основное средство разработки в Plarium Krasnodar. Здесь и далее в качестве графического контента будут рассматриваться 3D-модели и текстуры.

В этой статье мы поговорим об особенностях доступа к данным представления 3D-объектов в Unity. Материал будет полезен в первую очередь новичкам, а также тем разработчикам, которые нечасто взаимодействуют с внутренним представлением таких моделей.

О 3D-моделях в Unity — для самых маленьких

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

Снаружи меш как объект предоставляет доступ к следующим наборам данных:

Ядро движка (UnityEngine (native)) изолировано от скриптов разработчика, и обращение к его функционалу реализовано через библиотеку UnityEngine (C#). Фактически она является адаптером, поскольку большинство методов служат прослойкой для получения данных от ядра. При этом ядро и вся остальная часть, в том числе ваши скрипты, крутятся под разными процессами и скриптовая часть знает только список команд. Таким образом, прямой доступ к используемой ядром памяти из скрипта отсутствует.

О доступе к внутренним данным, или Насколько все может быть плохо

Для демонстрации того, насколько все может быть плохо, проанализируем объем очищаемой памяти Garbage Collector’ом на примере из документации. Для простоты профилирования завернем аналогичный код в Update метод.

Мы прогнали данный скрипт со стандартным примитивом — сферой (515 вершин). При помощи инструмента Profiler, во вкладке Memory можно посмотреть, сколько памяти было помечено для очистки сборщиком мусора в каждом из кадров. На нашей рабочей машине это значение составило

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

Важно упомянуть об особенности компилятора .Net и об оптимизации кода. Пройдясь по цепочке вызовов, можно обнаружить, что обращение к Mesh.vertices влечет за собой вызов extern метода движка. Это не позволяет компилятору оптимизировать код внутри нашего Update() метода, несмотря на то, что DoSomething() пустой и переменные x, y, z по этой причине являются неиспользуемыми.

Теперь закешируем массив позиций на старте.

В среднем 6 Кб. Другое дело!

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

Как это делаем мы

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

Изначально эта структура выглядела так:

Здесь класс CustomMesh представляет, собственно, меш. Отдельно в виде Utility мы реализовали конвертацию из UntiyEngine.Mesh и обратно. Меш определяется своим массивом треугольников. Каждый треугольник содержит ровно три ребра, которые в свою очередь определены двумя вершинами. Мы решили добавить в вершины только ту информацию, которая нам необходима для анализа, а именно: позицию, нормаль, два канала текстурной развертки (uv0 для основной текстуры, uv2 для освещения) и цвет.

Спустя некоторое время возникла необходимость обращения вверх по иерархии. Например, чтобы узнать у треугольника, какому мешу он принадлежит. Помимо этого, обращение вниз из CustomMesh в Vertex выглядело вычурно, а необоснованный и значительный объем дублированных значений действовал на нервы. По этим причинам структуру пришлось переработать.

В CustomMeshPool реализованы методы для удобного управления и доступа ко всем обрабатываемым CustomMesh. За счет поля MeshId в каждой из сущностей имеется доступ к информации всего меша. Такая структура данных удовлетворяет требованиям к первоначальным задачам. Ее несложно расширить, добавив соответствующий набор данных в CustomMesh и необходимые методы — в Vertex.

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

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

Источник

Что такое service mesh и почему он мне нужен [для облачного приложения с микросервисами]?

Предисловие от переводчика: Эта неделя ознаменовалась выходом Linkerd 1.0, что является отличным поводом рассказать не только об этом продукте, но и о самой категории такого программного обеспечения — service mesh (дословно переводится как «сетка для сервисов» или «сервисная сетка»). Тем более, что авторы Linkerd как раз опубликовали соответствующую статью.

tl;dr: Service mesh — это выделенный слой инфраструктуры для обеспечения безопасного, быстрого и надёжного взаимодействия между сервисами. Если вы создаёте приложение для запуска в облаке (т.е. cloud native), вам нужен service mesh.

За прошедший год service mesh стал критически важным компонентом в облачном стеке. Компании с большим трафиком, такие как PayPal, Lyft, Ticketmaster и Credit Karma, уже добавили service mesh в свои приложения в production, а в январе Linkerd — Open Source-реализация service mesh для облачных приложений — стал официальным проектом фонда Cloud Native Computing Foundation (в этот же фонд недавно передали containerd и rkt, а ещё он известен как минимум по Kubernetes и Prometheus — прим. перев.). Но чем же является service mesh? И почему он стал внезапно необходим?

Что такое service mesh?

Service mesh — это выделенный слой инфраструктуры для обеспечения взаимодействия между сервисами. Он отвечает за надёжную доставку запросов через сложную топологию сервисов, составляющих современное приложение, созданное для работы в облаке. На практике service mesh обычно реализуется как массив легковесных сетевых прокси, которые деплоятся вместе с кодом приложения, без необходимости приложению знать об этом. (Но мы увидим, что у этой идеи есть разные вариации.)

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

Является ли service mesh сетевой моделью?

Да, service mesh — это сетевая модель, находящаяся на уровне абстракции выше TCP/IP. Подразумевается, что нижележащая сеть L3/L4 представлена и способна передавать байты от точки до точки. (Также подразумевается, что эта сеть, как и все другие аспекты окружения, не является надёжной; service mesh должен обеспечивать обработку сетевых отказов.)

В некоторых смыслах service mesh аналогичен TCP/IP. Как TCP-стек абстрагирует от механики надёжной передачи байтов между конечными сетевыми точками, так и service mesh абстрагирует от механики передачи запросов между сервисами. Как и TCP, service mesh не придаёт значения действующей нагрузке и тому, как она закодирована. У приложения есть задача высокого уровня («отправить что-то из A в B»), и работа service mesh, как и в случае TCP — решить эту задачу, обрабатывая любые встречающиеся по пути проблемы.

В отличие от TCP, у service mesh есть значительная цель помимо «просто заставить что-то работать» — предоставить унифицированную точку входа для всего приложения, обеспечив видимость и контроль его исполняемой среде. Прямая цель service mesh — вынести взаимодействие между сервисами из области невидимой, предполагаемой инфраструктуры, предложив ему роль полноценного участника экосистемы, где всё подлежит мониторингу, управлению, контролю.

Что же service mesh делает?

Надёжная передача запросов в приложении для облачной инфраструктуры может быть очень сложной. И service mesh вроде Linkerd разбирается с этой сложностью с помощью набора действенных техник: предохранения от проблем в работе сети, балансировки нагрузки с учётом задержек, обнаружения сервисов (по модели согласованности в конечном счёте), повторных попыток и дедлайнов. Все эти возможности должны работать совместно, а взаимодействия между ними и среда, в которой они оперируют, могут быть весьма непростыми.

Например, когда делается запрос в сервисе через Linkerd, очень упрощённая последовательность событий выглядит следующим образом:

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

Почему service mesh нужен?

Service mesh — это, конечно, не предоставление новой функциональности, а скорее сдвиг в том, куда это функциональность помещена. Веб-приложения всегда были вынуждены тянуть ношу взаимодействия между сервисами. Происхождение модели service mesh можно проследить в эволюции этих приложений на протяжении последних 15 лет.

Представьте типичную архитектуру веб-приложения средних размеров в 2000-х: это 3 уровня. В такой модели логика приложения, логика отдачи контента и логика хранилища — отдельные слои. Взаимодействие между этими уровнями является сложным, но ограничено в масштабах — ведь тут всего два транзитных участка. Нет никакой «сетки» (т.е. mesh) — только взаимодействие логики между транзитными участками, осуществляемое в коде каждого слоя.

Когда этот архитектурный подход достиг очень большого масштаба, он начал ломаться. Компании вроде Google, Netflix и Twitter столкнулись с необходимостью обслуживания большого трафика, реализация которой стала предшественником облачного (cloud native) подхода: слой приложения был разбит на множество сервисов (иногда называемых микросервисами), и уровни стали топологией. В этих системах обобщённый слой для взаимодействия быстро стал необходимостью, но обычно принимал форму библиотеки «толстого клиента»: Finagle у Twitter, Hystrix у Netflix, Stubby у Google.

Во многих смыслах эти библиотеки (Finagle, Stubby, Hystrix) стали первыми «сетками для сервисов». Пусть они были заточены для работы в своей специфичной среде и требовали использования конкретных языков и фреймворков, однако уже представляли собой выделенную инфраструктуру для управления взаимодействием между сервисами и (в случае Open Source-библиотек Finagle и Hystrix) применялись не только в компаниях, которые их разработали.

Последовало быстрое движение навстречу современным приложениям, создаваемых для запуска в облаках. Модель cloud native сочетает микросервисный подход из множества маленьких сервисов с двумя дополнительными факторами:

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

Будущее service mesh

Пока идёт быстрый рост адаптации service mesh в облачной экосистеме, обширную и захватывающую дорожную карту [дальнейшего развития этой концепции и её реализаций — прим. перев.] ещё только предстоит открыть. Требования, предъявляемые к вычислениям без серверов (например, Amazon Lambda), отлично укладываются в модель service mesh по наименованию и связыванию [компонентов], что формирует естественное расширение его применения в облачной экосистеме. Роли удостоверения служб и политик доступа всё ещё очень молоды в облачных окружениях, и здесь service mesh хорошо подойдёт, чтобы стать фундаментальной составляющей такой потребности. Наконец, service mesh, как и TCP/IP раньше, продолжит своё проникновение в нижележащую инфраструктуру. Как Linkerd эволюционировал из систем вроде Finagle, продолжит свою эволюцию и текущая реализация service mesh как отдельного прокси в пользовательском пространстве, которая может быть добавлена в облачный стек.

Вывод

Service mesh — критически важный компонент стека категории cloud native. Linkerd, появившись чуть более 1 года назад, является частью Cloud Native Computing Foundation и получил растущее сообщество контрибьюторов и пользователей. Его пользователи разнообразны: от стартапов вроде Monzo, разрушающих банковскую индустрию Великобритании [это полностью цифровой банк, предлагающий разработчикам API для доступа к финансовым данным, — прим. перев.], до интернет-компаний больших масштабов вроде PayPal, Ticketmaster и Credit Karma, а также компаний с бизнес-историей в сотни лет вроде Houghton Mifflin Harcourt.

Open Source-сообщество пользователей и контрибьюторов Linkerd ежедневно демонстрируют ценность модели service mesh. Мы преданы созданию отличного продукта и продолжающемуся росту нашего сообщества.

P.S. Автор статьи — William Morgan, один из создателей Linkerd в 2015 году, учредитель и CEO в Buoyant Inc (компания-разработчик, передавшая Linkerd в CNCF).

ОБНОВЛЕНО (20.02.2018): читайте также в нашем блоге обзор нового продукта Buoyant — «Conduit — легковесный service mesh для Kubernetes».

Источник

Скрываем воду внутри лодки

При разработке игр про лодки, да и любых других игр с обширными водными поверхностями, существует проблема сокрытия поверхности воды, когда на ней что-то плавает. Я расскажу о решении, используемом в моей игре Sail Forth на движке Unity, но эта методика применима для любого другого движка.

Та самая проблема. Тащите ведро!

Так как в большинстве игр вода — это просто большая плоскость, логично, что плавающие на ней объекты будут пересекаться с её поверхностью!

Как же нам устранить эту проблему? Мне известны две основные методики: одна основана на деформировании меша воды вокруг корпуса судна, вторая заключается в маскировании поверхности воды внутри судна. Я знаю, как использовать вторую методику, поэтому мы реализуем её.

Решение состоит из трёх компонентов:

Меш маски

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

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

Шейдер маски

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

Шейдер для меша маски воды

Пока таким будет весь шейдер для маски воды! Краткое описание: он выполняет рендеринг после всей непрозрачной (opaque) геометрии (например, лодки) и до воды, и не записывает никаких цветов, зато выполняет запись глубин. Последнее означает, что мы не сможем его увидеть, но он перекрывает объекты за собой. Он не перекрывает саму лодку, потому что отрисовывается после лодки.

Включение и отключение меша маски

Если мы применим этот шейдер к мешу маски, при условии, что очередь рендеринга воды находится после очереди рендеринга маски, то вы увидите, что это уже работает!

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

Это вполне может быть достаточным решением для вашей игры, как и для меня в течение первых нескольких лет разработки. Однако возникает одна проблема:

Что здесь происходит? Лодка качается на волнах, и иногда часть волн поднимается над верхней частью лодки. Это означает, что вода ближе к камере, чем маска, поэтому проходит Z-тест и рендерится.

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

Стенсил-буфер

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

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

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

Stencil — это просто означает, что на данном проходе шейдера мы будем выполнять операцию со стенсилом

Ref 1 — значение стенсила, на которое мы будем ссылаться, равно 1

Comp always — когда мы смотрим на текущее значение стенсила, шейдер всегда должен отрисовывать пиксель вне зависимости от значения стенсила.

Pass replace — при отрисовке пикселя мы должны заменять текущее значение стенсила нашим значением, то есть 1.

Итак, результатом выполнения этого шейдера станет то, что стенсил-буфер будет содержать 1 в каждом пикселе, в котором отрисовывается объект.

Теперь нам нужно использовать эту информацию стенсила в шейдере воды.

Маскирование в шейдере воды

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

Это очень похоже на код стенсила, который мы писали в шейдере маскировки, но немного с другими параметрами.

Мы по-прежнему ссылаемся на значение 1, но здесь наша задача — не рендерить воду, если стенсил-буфер равен 1, потому что мы знаем, что 1 записана там, где находится наш маскирующий объект.

Поэтому мы делаем параметр Comp равным «notequal», то есть сравнение будет выполняться на неравенство. Если значение стенсила не равно 1, то тест стенсила оказывается пройденным.

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

Вода, вода повсюду, но ни капли в нашей лодке!

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

При этом возникает ещё одна проблема: что если лодка потонет? Я решил отключать рендерер маски воды, как только лодка начинает тонуть. Во всех остальных случаях я предполагаю, что нет никаких причин отрисовывать воду поверх внутренностей лодки.

Ещё одна проблема, похожая на ситуацию с потоплением, рассмотрена в этой замечательной статье: https://simonschreibt.de/gat/black-flag-waterplane/. Высокая волна может встать между лодкой и камерой, которая в таком случае неправильно создаст стенсил-буфер, что приведёт к некрасивому артефакту. Конкретно в вашей игре такая ситуация может и не возникнуть, или наоборот, будет очень заметной.

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

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

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

Источник

Создание разрушаемых мешей

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

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

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

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

Наша цель

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

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

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

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

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

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

Шаг 1

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

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

Шаг 2

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

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

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

Шаг 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Часть 3. Dual Contouring

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Переходим в 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-поверхность. В большинстве случаев на это не обращают внимания, так что я не решал эту проблему.

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

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

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

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

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

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

Источник