Воксели [Voxel]

Octree для хранения данных об объеме

Два способа хранения таких данных я уже упомянул выше: массив N*N*N и карта высот. Хочется добавить еще один способ, а именно octree (восьмидерево;). От двоичного дерева его отличает способ деления пространства - сразу на восемь равных частей, с линейными размерами вдвое меньше, чем у предка.

Чем интересен такой способ хранения данных? Тем, что при добавлении в восьмидерево единичного объема автоматически обходятся пустые участки. Вот часть кода обработки восьмидерева в качестве иллюстрации:

// _subdivide отыскивает необходимый элемент восьмидерева,
// создавая отсутствующие элементы дерева по необходимости
   static hnode* _subdivide(hnode*p,livec3*center,longint x,
                             longint y,longint z,int step) {
   longint hs=p->size;
   int index=0;
   hnode *child;
   livec3 ncenter;  // новые координаты центра
   if(x>=(*center)[X_DIM]) index|=X_SUB; // Вычисление индекса потомка
   if(y>=(*center)[Y_DIM]) index|=Y_SUB; // двоичным делением по трем
   if(z>=(*center)[Z_DIM]) index|=Z_SUB; // координатам
   child=p->childs[index];
   if(!child) { // Нет необходимого потомка на этом уровне
      child=new_node(); if(!child) return 0; // создать потомка в случае отсутствия
      init_pointers(child,p);
      p->childs[index]=child; child->parent=p; child->size=hs/2;
   }
   if(hs<2) return child; // Если деление дальше не нужно
                          // (потомок, содержащий (x,y,z) наименьшего размера найден)
   ncenter[X_DIM]=(*center)[X_DIM];
   ncenter[Y_DIM]=(*center)[Y_DIM];
   ncenter[Z_DIM]=(*center)[Z_DIM];
   hs/=2;
// Следует добавить, что центром корневого элемента является точка (0,0,0)
   if(index&X_SUB) ncenter[X_DIM]+=hs; else ncenter[X_DIM]-=hs;
   if(index&Y_SUB) ncenter[Y_DIM]+=hs; else ncenter[Y_DIM]-=hs;
   if(index&Z_SUB) ncenter[Z_DIM]+=hs; else ncenter[Z_DIM]-=hs;
   return _subdivide(child,&ncenter,x,y,z,step+1);
} /* _subdivide */

Если некоторый объем "пуст" - то есть, имеет стандартные параметры - то ссылка на него просто не появляется.

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

Перспективная проекция восьмидерева

При перспективной проекции на разных расстояниях от камеры частота выборки элементов изображения различна.

Например, на расстоянии (z координата пространства камеры) в диапазоне 0.25..0.5 фокусного расстояния единичный объем будет выбран четыре раза. (x_scr=x_cam*z_focus/z_cam, z_cam/z_focus=C=0.25..0.5, отсюда x_cam(x_scr)=x_scr*C, x_cam(x_scr+1)-x_cam(x_scr)=C=0.25..0.5, то есть, элемент единичного линейного размера будет отображен размером в два-четыре пиксела)

На расстоянии от одного до двух фокусных расстояний элементы единичного объема будут отображены в экранные объекты менее, чем в один пиксел размером. То есть, в одном пикселе будут смешаны до четырех вокселей. На расстоянии от 16 до 32 фокусных в одном пикселе смешаются до 1024 (32*32) вокселей. И чем дальше, тем больше.

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

Объединение визуальных параметров потомков

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

Для правильного понимания процесса стоит взглянуть на интеграл отображения от Jim Kajiya:

Суммарная интенсивность вдоль луча равна сумме интенсивностей в точке луча (I(x)), умноженных на полное затухание вдоль луча (exp(sum(alpha(x)dx))).

Сперва разберемся с прозрачностью, как с более простым случаем.

Действительно, с прозрачностью все лежит на поверхности: общая прозрачность не меняется при изменении знака обхода с 0->x на x->0, поскольку от перемены мест слагаемых сумма не изменяется. Если использовать не логарифмические alpha(x), а a(x)=exp(-alpha(x)), то сумма просто заменяется на умножение. (От перемены мест сомножителей результат не изменяется;)

Итак, вдоль каждой оси координат (отдельно Ox, Oy и Oz) я считаю среднюю прозрачность для стороны кубика:

T(dir)=(T(dir,upleft,forward)*T(dir,upleft,backward)+
T(dir,downleft,forward)*T(dir,downleft,backward)+
T(dir,upright,forward)*T(dir,upright,backward)+
T(dir,downright,forward)*T(dir,downright,backward) )/4;

forward и backward, left и right, up и down - координаты вокселей-потомков. Обе эти переменные зависят от направления dir. Например, для оси Oy forward будет (0,+0,0), backward - (0,-1,0), upleft - (+0,0,+0), downright - (-1,0,-1).

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

Теперь стоит перейти к цвету.

В общем случае, для всех шести сторон кубика-воксела цвет будет различен (как пример - Кубик Рубика). Более того, это же видно из интеграла Kajiya - для разных направлений у интенсивностей I(x) разные множители. Поэтому в структуре, хранящей визуальные параметры воксела присутствует шесть (число измерений * 2) не связанных между собой записей о цвете.

Цвет для определенной стороны (side) считается как взвешенная сумма цветов (для сторон side) четырех пар вокселей, с учетом заслонения прозрачными вокселами. Пример кода (на этот раз псевдокод):

component=0;
traspsum=0;
for(i in (upleft,upright,downleft,downright)) { // перебираем четыре пары
   transparency t=child[i,forward].transparency[side/2],
                tb=child[i,backward].transparency[side/2];
   component+=(child[i,forward].components[side]*t+ // учет заслонения
               child[i,backward].components[side]*(1-t)
              )*(1-t)*(1-tb); // вес - общая непрозрачность
   transpsum+=(1-t)*(1-tb);
}
if(transpsum<1) transpsum=1; // Жизнь без divide by zero
current.components[side]=component/transpsum;

Я еще не рассказал, как во время отображения вычислять прозрачность и цвет разноцветного вокселя. Это чрезвычайно просто: если вектор воксель-камера равен (A,B,C), то прозрачность считается так:

transp=voxel->trnsparency[X_DIR]*abs(A)+
       voxel->trnsparency[Y_DIR]*abs(B)+
       voxel->trnsparency[Z_DIR]*abs(C);
transp/=abs(A)+abs(B)+abs(C);

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

Цвет считается похожим образом, только в игру вступает направление взгляда (знак):

comp=voxel->component[X_SIDE+(A<0)]*abs(A)+
     voxel->component[Y_SIDE+(B<0)]*abs(B)+
     voxel->component[Z_SIDE+(C<0)]*abs(C);
comp/=abs(A)+abs(B)+abs(C);