Представляем четвертую статью нашего цикла о работе с 3D-моделями в Unity. Предшествующие статьи: «Особенности работы с Mesh в Unity», «Unity: процедурное редактирование Mesh», «Импорт 3D-моделей в Unity и подводные камни».
В предыдущей статье мы упомянули о проверке текстурной развертки на достаточность пиксельного отступа при заданном разрешении текстуры. В этой публикации мы опишем суть проблемы с соблюдением пиксельного отступа и алгоритм ее отслеживания. Рассмотрен будет не код, а именно принцип, который можно реализовать на любом языке и в любой среде разработки.
Заказ на 3D-модель, как правило, сопровождается требованием к разрешению текстуры. В связи с дискретностью растрового изображения 3D-художник должен соблюдать отступ в пикселях между частями текстурной развертки. Отсутствие необходимого отступа приводит к тому, что один и тот же пиксель отображается на модели в совершенно разных местах, когда это не нужно.
Особенно важно отслеживать достаточный отступ на ранних этапах работы. Чаще всего созданием геометрии, включающей в себя текстурную развертку, занимаются одни люди, а рисованием текстуры — другие. Ошибка, выявленная 3D-художником, доставит меньше хлопот, чем та, которую обнаружит текстурщик. В последнем случае ситуация еще больше усложняется, если используемый 3D-пакет не предоставляет инструментов для рисования поверх геометрии (например, кисть).
Также следует учитывать два нюанса, из-за которых между элементами развертки может понадобиться больше пространства. Первый — уменьшение разрешения текстуры при мипмаппинге. Второй — использование dilation-фильтра при формировании карты освещения. Во время выполнения задачи по созданию UV-развертки 3D-художнику необходимо ориентироваться на требования к разрешению текстуры, а также учитывать перечисленные нюансы. Тем не менее многие недочеты просто не заметить без автоматизированной проверки.
Пример появления артефактов при снижении детализации
Для простых моделей текстурная развертка может формироваться с использованием автоматических инструментов. Однако они основаны на внутренних метриках и не учитывают пиксельный отступ, поэтому разделяемые пиксели часто располагаются вдоль диагональных границ. Проверка текстурами-чекерами не показывает всех ошибок, вдобавок эти текстуры зачастую имеют большее разрешение, чем те, что будут использоваться в проекте.
Разделяемые пиксели
Проблема недостаточного пиксельного отступа в UV-развертке похожа на проблему с наложениями. В обоих случаях может происходить так называемое затекание (bleeding) — в предыдущей статье мы описали, какие артефакты это порождает.
Однако проблема с пиксельным отступом зависит от требования к минимальному разрешению текстуры. Для определения наложений достаточно разовой проверки, тогда как требования к разрешению текстуры могут поменяться на очередном этапе разработки. Осложняется ситуация тем, что в используемых нами 3D-пакетах нет инструментов для автоматического обнаружения ошибок, связанных с близостью частей UV-развертки. И не стоит забывать, что после работы автоматического формирователя в Unity нужно еще проверять UV2.
Мы решили создать инструмент, который сможет выполнять проверку на отступы в пикселях и помечать места потенциальных недочетов на модели. Требования к отступу будем определять исходя из следующих параметров:
Поскольку размеры используемых нами текстур равны степеням двойки, формула подсчета необходимого отступа при базовом разрешении довольно проста: (базовоеРазрешение / минимальноеРазрешение) * отступНаМинТекстуре.
Очевидно, что решение этой задачи тесно связано с растеризацией. Для более четкой формулировки требований и разработки алгоритма мы введем несколько понятий.
Рассмотрим UV-пространство и равномерную сетку размерностью NxM в диапазоне 0.0–1.0. Ячейки шириной 1/N и высотой 1/M образуют разбиение UV-пространства.
NxM разбиение UV-пространства
Возьмем две произвольные точки и обозначим Dn как количество пикселей, занимаемое проекцией на ось U отрезка, соединяющего заданные точки. Аналогично — Dm для оси V. Тогда определим пиксельное расстояние как максимум между Dn и Dm.
Пиксельное расстояние
Стоить отметить, что в евклидовом пространстве такие операции движения, как параллельный перенос и поворот, не являются движениями для сетки разбиения, если за метрику принято пиксельное расстояние. Этот нюанс немного усложнил разработку нашего решения.
Назовем квадрат со стороной в K пикселей ядром величины K. Тогда любые две точки, пиксельное расстояние между которыми меньше K, можно покрыть ядром величины K.
Примеры ядер разной величины
Два ребра многоугольника образуют вогнутость контура, если их средняя точка (центр масс по четырем вершинам) лежит слева от этих ребер при обходе контура по часовой стрелке. Для обхода против часовой стрелки условием будет нахождение точки справа от ребер.
Пара ребер, образующая вогнутость контура
Теперь поговорим непосредственно о проверке пиксельного отступа. Чтобы реализовать ее, мы придумали алгоритм, состоящий из трех независимых фрагментов. Порядок выполнения не важен. Итогом работы каждого из фрагментов является матрица NxM, представляющая собой буфер ячеек разбиения, где некоторые ячейки помечены. Сложение всех трех буферов и есть общий результат.
Первым рассмотрим самый простой фрагмент. Он сводится к поиску ячеек, которые пересекаются с близкими к вырожденным треугольниками и ребрами, чья длина меньше стороны ядра заданной величины. Все такие ячейки помечаются в буфере.
Результат проверки на размеры элементов
Прежде чем описывать остальные два фрагмента, рассмотрим общую логику их работы. Оба связаны с обработкой кластеров из треугольников, называемых шеллами (shells) или островами (islands). Шелл для 3D-художника — это связный набор полигонов, то есть у каждого полигона в этом наборе имеется сосед, с которым он делит общие вершины. Также шеллом является независимый полигон. Далее под шеллом, островом и кластером будем понимать одно и то же.
Чтобы найти все шеллы, используем алгоритм поиска всех компонент связности графа, где вершина графа представлена полигоном, а ребро — наличием общих вершин у пары многоугольников. Поскольку единственным полигоном в Unity является треугольник, определяемый индексами вершин, считаем треугольники соседними, если хотя бы один индекс вершины первого совпадает с индексом любой вершины второго. Из аналогии с графом и способа определения ребер следует, что множество индексов вершин одного кластера не пересекается со множеством вершин другого.
С общей частью закончили. Второй фрагмент, который мы рассмотрим, определяет места потенциальных ошибок, связанных с близостью или наложением разных кластеров.
На вход подается множество кластеров в виде наборов треугольников на UV-пространстве, размерность разбиения UV, соответствующая разрешению текстуры (NxM), и величина отступа P как количество пикселей. Для заданного разбиения необходимо найти те области, в которых расстояние в пикселях между кластерами меньше требуемого отступа. Ячейка в матрице-результате помечается, если она входит хотя бы в одно ядро величины K = P + 1, которое пересекает два разных кластера.
Суть работы фрагмента почти изложена в описании результата. Необходимо найти все ядра величины K, которые пересекаются с треугольниками из разных шеллов, и затем пометить ячейки этих ядер в буфере-результате.
В нашей реализации поочередно рассматриваются все пары кластеров. Для каждой пары определяется область пересечения множеств ядер величины K, покрываемых этими кластерами. Выберем некоторую пару и обозначим такое множество как Q.
Затем все элементы Q нужно проверить по следующему критерию: пересекает ли данное ядро хотя бы по одному треугольнику в каждом из кластеров выбранной пары. Если это так, то помечаются все ячейки проверяемого ядра.
Буфер с помеченными ячейками для всех пар кластеров и составляет результат.
Результат проверки отступа между кластерами
Теперь разберемся с последним фрагментом. Здесь необходимо обработать один кластер. На вход подается набор треугольников на UV-пространстве, размерность разбиения UV, соответствующая разрешению текстуры (NxM), и величина отступа P как количество пикселей. Ячейка может быть помечена в двух случаях: либо кластер невалидный или имеет дыры, либо расстояние в пикселях между ребрами вогнутостей меньше требуемого отступа.
Внутренняя часть кластера нас не интересует — для начала получим его контур, представленный связным списком ребер. Соседние треугольники дублируют индексы вершин, поэтому ребро принадлежит контуру, если пара индексов его вершин уникальна для множества ребер кластера. Выяснив, какие ребра образуют контур, необходимо скомпоновать их так, чтобы получился связный список.
Если после этого шага не все ребра контура попадают в список, то либо кластер имеет дыры, либо есть ошибка в данных меша. В таком случае необходимо соответствующим образом пометить все ячейки ядер, пересекаемых кластером.
Если же контур найден, то обработка продолжается. Мы сформулировали следующее требование к результату. Пусть пара ребер, образующих вогнутость контура, пересекает ядро величины K = P + 1. Тогда ячейки ядра необходимо пометить, если обе части контура между ребрами выходят за пределы этого ядра.
Результат проверки особенностей кластера
Реализовать это требование мы решили через попарное сравнение ребер контура. Начинаем с условия вогнутости, затем для каждой пары проверяются все ядра, которые пересекают оба ребра. Для проверки ядра выполняются обходы каждой из частей контура между парой ребер. Если каждая часть содержит хотя бы по одной точке за границами ядра, то все ячейки ядра помечаются.
Условие, при котором помечаются ячейки проверяемого ядра
Приведенный алгоритм очень хорошо подходит для реализации с использованием параллельных вычислений. Обработка каждой пары кластеров и ребер происходит независимо. Поскольку проверки основаны на растеризации, если начинать обработку не с пар ребер, а с ядер, то целесообразно использовать возможности GPU.
Результат работы алгоритма мы преобразуем в текстуру. Для заданного разрешения это позволяет графически показать места потенциальных недочетов в UV-развертке. Также полученную текстуру можно наложить на модель, чтобы увидеть пометки прямо на геометрии.
На примерах ниже мы специально разрезали кролика и Сюзанну автоматическим инструментом Blender так, чтобы получить побольше артефактов. Проверяемое разрешение текстуры — 256х256, необходимый отступ — 1.
Ячейки, помеченные синим, покрывают кластеры с дырами, а также слишком мелкие треугольники и ребра. Зеленым обозначены ячейки ядер с особенностями каждого кластера в отдельности. Красным помечены ядра, в которых не соблюдается отступ между кластерами.
В следующей статье мы рассмотрим алгоритм оптимизации 3D-моделей в сцене за счет удаления невидимой геометрии. Оставайтесь с нами!
В предыдущей статье мы упомянули о проверке текстурной развертки на достаточность пиксельного отступа при заданном разрешении текстуры. В этой публикации мы опишем суть проблемы с соблюдением пиксельного отступа и алгоритм ее отслеживания. Рассмотрен будет не код, а именно принцип, который можно реализовать на любом языке и в любой среде разработки.
Проблематика
Заказ на 3D-модель, как правило, сопровождается требованием к разрешению текстуры. В связи с дискретностью растрового изображения 3D-художник должен соблюдать отступ в пикселях между частями текстурной развертки. Отсутствие необходимого отступа приводит к тому, что один и тот же пиксель отображается на модели в совершенно разных местах, когда это не нужно.
Особенно важно отслеживать достаточный отступ на ранних этапах работы. Чаще всего созданием геометрии, включающей в себя текстурную развертку, занимаются одни люди, а рисованием текстуры — другие. Ошибка, выявленная 3D-художником, доставит меньше хлопот, чем та, которую обнаружит текстурщик. В последнем случае ситуация еще больше усложняется, если используемый 3D-пакет не предоставляет инструментов для рисования поверх геометрии (например, кисть).
Также следует учитывать два нюанса, из-за которых между элементами развертки может понадобиться больше пространства. Первый — уменьшение разрешения текстуры при мипмаппинге. Второй — использование dilation-фильтра при формировании карты освещения. Во время выполнения задачи по созданию UV-развертки 3D-художнику необходимо ориентироваться на требования к разрешению текстуры, а также учитывать перечисленные нюансы. Тем не менее многие недочеты просто не заметить без автоматизированной проверки.
Пример появления артефактов при снижении детализации
Для простых моделей текстурная развертка может формироваться с использованием автоматических инструментов. Однако они основаны на внутренних метриках и не учитывают пиксельный отступ, поэтому разделяемые пиксели часто располагаются вдоль диагональных границ. Проверка текстурами-чекерами не показывает всех ошибок, вдобавок эти текстуры зачастую имеют большее разрешение, чем те, что будут использоваться в проекте.
Разделяемые пиксели
Проблема недостаточного пиксельного отступа в UV-развертке похожа на проблему с наложениями. В обоих случаях может происходить так называемое затекание (bleeding) — в предыдущей статье мы описали, какие артефакты это порождает.
Однако проблема с пиксельным отступом зависит от требования к минимальному разрешению текстуры. Для определения наложений достаточно разовой проверки, тогда как требования к разрешению текстуры могут поменяться на очередном этапе разработки. Осложняется ситуация тем, что в используемых нами 3D-пакетах нет инструментов для автоматического обнаружения ошибок, связанных с близостью частей UV-развертки. И не стоит забывать, что после работы автоматического формирователя в Unity нужно еще проверять UV2.
Мы решили создать инструмент, который сможет выполнять проверку на отступы в пикселях и помечать места потенциальных недочетов на модели. Требования к отступу будем определять исходя из следующих параметров:
- Базовое разрешение текстуры.
- Минимальное разрешение текстуры, при котором не допускаются затекания.
- Необходимая величина отступа на минимальной текстуре.
Поскольку размеры используемых нами текстур равны степеням двойки, формула подсчета необходимого отступа при базовом разрешении довольно проста: (базовоеРазрешение / минимальноеРазрешение) * отступНаМинТекстуре.
Очевидно, что решение этой задачи тесно связано с растеризацией. Для более четкой формулировки требований и разработки алгоритма мы введем несколько понятий.
Ключевые понятия
Рассмотрим UV-пространство и равномерную сетку размерностью NxM в диапазоне 0.0–1.0. Ячейки шириной 1/N и высотой 1/M образуют разбиение UV-пространства.
NxM разбиение UV-пространства
Возьмем две произвольные точки и обозначим Dn как количество пикселей, занимаемое проекцией на ось U отрезка, соединяющего заданные точки. Аналогично — Dm для оси V. Тогда определим пиксельное расстояние как максимум между Dn и Dm.
Пиксельное расстояние
Стоить отметить, что в евклидовом пространстве такие операции движения, как параллельный перенос и поворот, не являются движениями для сетки разбиения, если за метрику принято пиксельное расстояние. Этот нюанс немного усложнил разработку нашего решения.
Назовем квадрат со стороной в K пикселей ядром величины K. Тогда любые две точки, пиксельное расстояние между которыми меньше K, можно покрыть ядром величины K.
Примеры ядер разной величины
Два ребра многоугольника образуют вогнутость контура, если их средняя точка (центр масс по четырем вершинам) лежит слева от этих ребер при обходе контура по часовой стрелке. Для обхода против часовой стрелки условием будет нахождение точки справа от ребер.
Пара ребер, образующая вогнутость контура
Решение
Теперь поговорим непосредственно о проверке пиксельного отступа. Чтобы реализовать ее, мы придумали алгоритм, состоящий из трех независимых фрагментов. Порядок выполнения не важен. Итогом работы каждого из фрагментов является матрица NxM, представляющая собой буфер ячеек разбиения, где некоторые ячейки помечены. Сложение всех трех буферов и есть общий результат.
Первым рассмотрим самый простой фрагмент. Он сводится к поиску ячеек, которые пересекаются с близкими к вырожденным треугольниками и ребрами, чья длина меньше стороны ядра заданной величины. Все такие ячейки помечаются в буфере.
Результат проверки на размеры элементов
Прежде чем описывать остальные два фрагмента, рассмотрим общую логику их работы. Оба связаны с обработкой кластеров из треугольников, называемых шеллами (shells) или островами (islands). Шелл для 3D-художника — это связный набор полигонов, то есть у каждого полигона в этом наборе имеется сосед, с которым он делит общие вершины. Также шеллом является независимый полигон. Далее под шеллом, островом и кластером будем понимать одно и то же.
Чтобы найти все шеллы, используем алгоритм поиска всех компонент связности графа, где вершина графа представлена полигоном, а ребро — наличием общих вершин у пары многоугольников. Поскольку единственным полигоном в Unity является треугольник, определяемый индексами вершин, считаем треугольники соседними, если хотя бы один индекс вершины первого совпадает с индексом любой вершины второго. Из аналогии с графом и способа определения ребер следует, что множество индексов вершин одного кластера не пересекается со множеством вершин другого.
С общей частью закончили. Второй фрагмент, который мы рассмотрим, определяет места потенциальных ошибок, связанных с близостью или наложением разных кластеров.
На вход подается множество кластеров в виде наборов треугольников на UV-пространстве, размерность разбиения UV, соответствующая разрешению текстуры (NxM), и величина отступа P как количество пикселей. Для заданного разбиения необходимо найти те области, в которых расстояние в пикселях между кластерами меньше требуемого отступа. Ячейка в матрице-результате помечается, если она входит хотя бы в одно ядро величины K = P + 1, которое пересекает два разных кластера.
Суть работы фрагмента почти изложена в описании результата. Необходимо найти все ядра величины K, которые пересекаются с треугольниками из разных шеллов, и затем пометить ячейки этих ядер в буфере-результате.
В нашей реализации поочередно рассматриваются все пары кластеров. Для каждой пары определяется область пересечения множеств ядер величины K, покрываемых этими кластерами. Выберем некоторую пару и обозначим такое множество как Q.
Затем все элементы Q нужно проверить по следующему критерию: пересекает ли данное ядро хотя бы по одному треугольнику в каждом из кластеров выбранной пары. Если это так, то помечаются все ячейки проверяемого ядра.
Буфер с помеченными ячейками для всех пар кластеров и составляет результат.
Результат проверки отступа между кластерами
Теперь разберемся с последним фрагментом. Здесь необходимо обработать один кластер. На вход подается набор треугольников на UV-пространстве, размерность разбиения UV, соответствующая разрешению текстуры (NxM), и величина отступа P как количество пикселей. Ячейка может быть помечена в двух случаях: либо кластер невалидный или имеет дыры, либо расстояние в пикселях между ребрами вогнутостей меньше требуемого отступа.
Внутренняя часть кластера нас не интересует — для начала получим его контур, представленный связным списком ребер. Соседние треугольники дублируют индексы вершин, поэтому ребро принадлежит контуру, если пара индексов его вершин уникальна для множества ребер кластера. Выяснив, какие ребра образуют контур, необходимо скомпоновать их так, чтобы получился связный список.
Если после этого шага не все ребра контура попадают в список, то либо кластер имеет дыры, либо есть ошибка в данных меша. В таком случае необходимо соответствующим образом пометить все ячейки ядер, пересекаемых кластером.
Если же контур найден, то обработка продолжается. Мы сформулировали следующее требование к результату. Пусть пара ребер, образующих вогнутость контура, пересекает ядро величины K = P + 1. Тогда ячейки ядра необходимо пометить, если обе части контура между ребрами выходят за пределы этого ядра.
Результат проверки особенностей кластера
Реализовать это требование мы решили через попарное сравнение ребер контура. Начинаем с условия вогнутости, затем для каждой пары проверяются все ядра, которые пересекают оба ребра. Для проверки ядра выполняются обходы каждой из частей контура между парой ребер. Если каждая часть содержит хотя бы по одной точке за границами ядра, то все ячейки ядра помечаются.
Условие, при котором помечаются ячейки проверяемого ядра
Итоги
Приведенный алгоритм очень хорошо подходит для реализации с использованием параллельных вычислений. Обработка каждой пары кластеров и ребер происходит независимо. Поскольку проверки основаны на растеризации, если начинать обработку не с пар ребер, а с ядер, то целесообразно использовать возможности GPU.
Результат работы алгоритма мы преобразуем в текстуру. Для заданного разрешения это позволяет графически показать места потенциальных недочетов в UV-развертке. Также полученную текстуру можно наложить на модель, чтобы увидеть пометки прямо на геометрии.
На примерах ниже мы специально разрезали кролика и Сюзанну автоматическим инструментом Blender так, чтобы получить побольше артефактов. Проверяемое разрешение текстуры — 256х256, необходимый отступ — 1.
Ячейки, помеченные синим, покрывают кластеры с дырами, а также слишком мелкие треугольники и ребра. Зеленым обозначены ячейки ядер с особенностями каждого кластера в отдельности. Красным помечены ядра, в которых не соблюдается отступ между кластерами.
Примеры
В следующей статье мы рассмотрим алгоритм оптимизации 3D-моделей в сцене за счет удаления невидимой геометрии. Оставайтесь с нами!