Оптимальная триангуляция и многое другое…
Предположим, мы хотим визуализировать изображение, подобное показанному выше. Это воксельная модель от @ephtracy (известности MagicaVoxel), состоящая из 226 036 вокселей. Каждый воксель имеет интегральные координаты X, Y, Z и цвет из палитры.
Наивно, мы можем триангулировать все шесть граней каждого воксельного куба. Это 12 треугольников на воксель, или 2 712 432 треугольника! Это работает, но кажется ужасным для такой простой модели.
Многие из этих лиц вокселей даже не видны. Мы можем отслеживать, какие ячейки вокселей заняты, с помощью трехмерного массива или хеш-таблицы. Затем мы создаем треугольники только для открытых лиц. То есть у них нет соседнего вокселя. В этой модели это число сокращается до 138 260 треугольников, или всего 5% от исходного!
Это простая оптимизация. Но наша сетка по-прежнему выглядит так (немного увеличено)…
Это много маленьких треугольников. Мы можем лучше. Мы хотим найти большие прямоугольные области такого же цвета. Лучший способ сделать это - работать в 2D. Первый шаг - выделить грани, которые находятся в одной плоскости и имеют одинаковый цвет. Вот пример, показывающий верхние грани (нормаль = 0,0,1) всех бежевых вокселей при Z = 6 (пол).
Теперь это выглядит как двухмерная двоичная сетка (0 = без вокселя, 1 = воксель). Мы хотим найти самый большой прямоугольник (по площади) из единиц. Это можно сделать с помощью алгоритма динамического программирования. Я использовал эту реализацию от Stack Overflow. После определения самого большого прямоугольника эти грани удаляются, и мы повторяем, пока не будут учтены все грани в этой цветовой плоскости.
Конечно, каждый прямоугольник может быть визуализирован как два треугольника. Когда мы применяем это ко всем 577 цветовым плоскостям, вся модель использует только 2 966 треугольников или 1483 прямоугольных грани, что в тысячу раз лучше по сравнению с наивным подходом и всего 2% подхода с использованием видимых лиц. .
Одна из проблем заключается в том, что сетка теперь содержит Т-образные переходы, что может быть проблематичным. У меня не было проблем в этом конкретном случае, возможно, потому, что все выровнено по осям, но я все еще был заинтересован в удалении Т-образных переходов после того, как кто-то указал на это как на потенциальную проблему на Reddit. Немного поработав, мы можем удалить стыки. Здесь я использовал два разных подхода. Мой последний подход работает так. Каждая прямоугольная грань начинается с четырех ребер. Эти края сначала сегментируются там, где встречаются Т-образные переходы. У нас все еще есть четырехугольник, но эти точки указывают, где нам нужны вершины треугольника, когда мы триангулируем четырехугольник. Я использую рекурсивное решение, многократно разбивая многоугольник на два многоугольника. Базовый случай рекурсии - когда у нас есть 3 точки, мы можем просто вернуть треугольник. В противном случае мы выбираем разделение, которое дает нам соотношение сторон, максимально приближенное к 1, чтобы избежать длинных и узких треугольников. Теперь сетка содержит 4 408 треугольников.
У меня была другая идея, которую я еще не пробовал. При прямоугольной форме каждой плоскости у нас может быть третье значение, которое означает, что лицо скрыто. Другими словами, нам все равно, закрывает ли прямоугольник это лицо или нет. Итак, 0 = без лица, 1 = лицо, 2 = все равно. Это может позволить нам расширить прямоугольники в скрытые области, если это позволит уменьшить общее количество необходимых прямоугольников. Интересная идея, но, возможно, ее не стоит реализовывать… хотя она может уменьшить размер сетки, но увеличит нагрузку на растеризатор.
Когда я дошел до этого, мне очень понравился внешний вид контуров (они рисуются толстыми линиями на отдельном этапе рендеринга), но я хотел рисовать только линии в местах стыков. Для этого нам нужно изучить 12 краев каждого вокселя и посмотреть, должны ли они быть нарисованы на основе присутствия и цвета нескольких соседних вокселей. Или мы? Фактически, мы можем сделать эту часть с теми же двумерными цветовыми плоскостями, которые мы уже используем. Мы просто создаем линии по периметру и дыры, вот так…
Одна небольшая проблема заключается в том, что при этом будут генерироваться повторяющиеся отрезки линии (я думаю, ровно в 2 раза), которые я пока не удосужился отфильтровать, потому что это не имеет большого значения.
Собрав все это вместе, мы теперь можем визуализировать красивую воксельную модель. В основном мы смотрели на ортогональные проекции, но перспективная проекция показана ниже. При рендеринге черных линий я добавляю небольшое смещение буфера глубины, чтобы избежать z-борьбы и чтобы линии отображались полностью.
Эти изображения были визуализированы с помощью FauxGL, нового программного средства визуализации, которое я пишу на Go. Я делаю это в основном для развлечения и для обучения, и я подумал, что некоторые воксельные модели подойдут для хороших тестовых примеров.
Код для триангуляции и выделения вокселей можно найти на voxel.go.
Вот разбивка времени, затраченного на каждую часть кода, для выходных данных размером 1600 пикселей с суперсэмплингом 4x4 (фактически визуализированных с разрешением 6400 пикселей)…
loading vox file... 223.133263ms generating mesh... 259.45309ms 226036 voxels 2966 triangles 4682 lines rendering triangles... 740.274697ms rendering lines... 145.852892ms downsampling image... 264.575909ms writing output... 133.878484ms 2.058766649s
Спасибо за прочтение! Вы можете подписаться на меня в Twitter: @FogleBird
