CodeNet / Приложения / Графика / 2D / Воксели [Voxel]
Воксели [Voxel]
Недостатки воксельной технологии
Стоит начать с самого главного - это неторопливость. Для каждого объема приходится выполнять как минимум одно деление.
Значительный расход памяти: на каждый воксель, вне зависимости от его размера, требуется
6*sizeof(RGB)/*цвет*/+
3*sizeof(byte)/*прозрачность*/+
8*sizeof(pointer)/*потомки*/+sizeof(byte)/*флаги*/.
При заполнении мира расход памяти стремится к 8/7*L**3, где L=max_size/min_size. Однако, если имеется возможность создавать детали "на лету", то можно сохранять только необходимые уровни деталей, и тогда фактический расход памяти снизится.
Невысокая точность.
В конкретной тестовой реализации неправильно работает отображение прозрачных вокселей - накапливается существенная ошибка. Запустив следующую программу, вы можете сами убедится в значительном расхождении результатов:
#include <stdio.h> #define TRANSPBITS 7 #define TRANSPONE (1 << TRANSPBITS) #define POW 40 #define X (TRANSPONE-3) long tmul(long a,long b) { a*=b; return a>>TRANSPBITS; } /* tmul */ /* Способ, применяемый при отображении: */ long straight_power(long a,int power) { int i; long r=TRANSPONE; for(i=0;i<power;i++) { r=tmul(r,a); } return r; } /* straight_power */ /* Способ, применяемый при подсчете усредненных параметров: */ long fast_correct_power(long a,int power) { unsigned int mask=0x8000U; long r=TRANSPONE; while(mask) { r=tmul(r,r); if(power&mask) r=tmul(r,a); mask>>=1; } return r; } /* fast_correct_power */ int main(void) { printf("Straight %ld, correct %ld\n", straight_power(X,POW), fast_correct_power(X,POW) ); return 0; } /* main */
Этот недостаток можно исправить (за счет использования частично сбалансированного двоичного дерева), однако исправление, скорее всего, повлечет за собой снижение быстродействия. Если быть совсем точным, то здесь требуется дополнительная работа.
Достоинства использования octree
Быстрое отсечение невидимых деталей - если больший куб полностью невидим, значит делить его на меньшие кубы не надо.
Возьмем отрезок 2**N*Focus_len..2**(N+!)*Focus_len. На этом расстоянии будет O(Focus_len) вокселей размером 2**(N+1). Если мир, описываемый восьмидеревом, имеет максимальный линейный размер L, то количество таких отрезков будет log2(L/Focus_len). На экране отображается M=Width*Height лучей. Значит, общая сложность отображения с использование восьмидерева - O(M*log(L))
Встроенный контроль детализации - деление на меньшие объемы прекращается для объема, экранный размер которого составляет от одного до двух пикселов. Если ввести аппроксимацию цвета большего объема, то получится Contionuous Level Of Detail - непрерывность уровня детализации.
Упрощена реализация "молочного тумана" - размывающей свет среды - воксели надо отрисовывать с уменьшенным уровнем детализации. (NB: в тумане предметы кажутся больше, чем они есть на самом деле)
Направление работ
Стоит подумать о более быстром и более правильном механизме отображения.
Восьмидерево, описывающее занимаемый объектами мира объем, позволит описывать любые уровни детализации. При этом более мелкие детали будут создаваться по требованию на основе координат, линейного размера и процедур генерации деталей данного объекта. В этом случае ничего не стоит создавать приближение сферы настолько точно, насколько это нужно.
Восьмидерево освещенности - разумная идея, по-моему.
Как в воксельные картины можно добавить отражение (и преломление)?
Необходимо подумать о более быстром отсечении невидимых деталей. С использованием иерархического z-буфера и(или) карты заслоняющих предметов, a-la мистер Zhang ( здесь ).
Ссылки
www.novalogic.com . Сайт
создателей Команчей. Просто так. ;)
Страница Поля Хекберта . На
этой странице есть подборка ссылок и
библиография по упрощению поверхностей, в том
числе и ландшафтов, и моделированию с
использованием изменения разрешения модели. Еще
есть несколько статей, в которых можно
посмотреть создание Level OF Detail для полигональных
моделей.
Tech
Report: HPL-95-73: Fourier Volume Rendering . Использование
преобразования Фурье для отображения объемов.
Visibility
Culling using Hierarchical Occlusion Maps , Zhang et al. Интересная
статья о сокращении отображаемых деталей,
применимая к любому представлению модели.
Рендеринг объемов в
реальном времени . Обзорная статья в Open Systems.
A Wavelet-based
Multiresolution Polyhedral Object Representation (technical sketch). . Эта
статья подвигла меня на размышления, вылившиеся
в эту статью.
Подборка скриншотов, иллюстрирующих статью:
Из темноты появляются четыре квадратика вокселей, постепенно приобретая свой "естественный" цвет.
Здесь хорошо видно, что квадраты вокселей частично закрывают друг друга. Это сделано для сохранения топологии модели - между элементами поверхности не должно быть просветов.
Проверка "встроенной" фильтрации изображения.
Еще одна.
И еще одна.
Прозрачный шар диаметром 40 вокселов на контрастном
Тот же шар и тот же фон, только после оптимизации дерева (объединения одинаковых элементов в большие).
Двор с травой. Вместо дров - яркий шарик.
Та же сцена, только на разном удалении. Яркая деталь проявляется на расстоянии, когда заслонявшие ее мелкие детали слились в полупрозрачный фон.