Воксели [Voxel]

Слово воксель - voxel - образовано от слова VOlume и аббревиатуры piXEL (pixel, расшифровывается как PICture'S ELement, элемент картины). То есть, переводится как "элемент объемного изображения" или "элемент объема изображения".. Обычно это шар или куб.

Не стоит приписывать пикселу и вокселю равносторонность. Это удобно, не более того. Иногда даже удобнее считать воксель неким параллепипедом - например, в карте высот.

Применения вокселей

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

Второе, более наглядное, применение вокселей - компьютерные игры. В Shadow Warrior с помощью трехмерного массива задается форма оружия, а во всем известных Команчах - ландшафт. И если в Shadow Warrior воксели квадратные, а массив трехмерный, то в Команчах воксели представляют собой параллепипед 1*1*высота_местности, а массив двумерный. Поэтому в Команчах не видно нависающих над берегом моря утесов - такое вот ограничение на представление пространства.

Способы отображения

Двумерные массивы высот отображаются методом плавающего горизонта в комбинации с методом отслеживания лучей (raycasting, не путать с reytracing). Способ чрезвычайно прост:

void cast_ray(int scrx,real x,real y,real dx,real dy) {
   max_height=0;
   for(dist=0;dist<view_depth;dist++) { // ограничение по дальности
      h=fetch_height(x,y);           // взять высоту из карты высот
      scrh=height_to_screen(h,dist); // преобразовать высоту в экранную
      if(scrh>max_height){        // текущий столбец "выше"
                                     // самого высокого отрисованого
         color=fetch_color(x,y);
         draw_column(scrx,max_height,height,color); // отрисовать видимую часть
         max_height=height;
      }
      x=x+dx;                         // единичный шаг вперед, вдоль луча
      y=y+dy;
   }
}

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

Что касается трехмерных массивов, то здесь все зависит от специфики приложения, поэтому методов их отображения существует несколько:

• Честная трассировка лучей.
  Традиционный "лобовой" метод, с которым все борются.
• Построение изоповерхности.
  Перед отображением объем переводится в набор плоскостей, описывающих "поверхности" объема.
  Один из методов пакета VolVis.
  Не очень хорош (с моей точки зрения) при отображении объемов с полупрозрачными участками.
• Отображение через преобразование Фурье.
  Метод основан на теореме об обратном преобразовании двумерного среза преобразования Фурье. Вкратце смысл ее таков: если вычислить прямое преобразование Фурье для объема N*N*N, затем взять его срез плоскостью P, проходящей через центр объема, затем произвести обратное преобразование Фурье, то результат будет представлять собой двумерный массив, с элементами, содержащими сумму элементов, соответствующих трассировке объема лучами, перпендикулярными P.
  Требует N**3 памяти под комплексные числа, сложность оценивается как O(N**2*log(N)).
  Существенным недостатком является отсутствие отсечения скрытых деталей - результаты работы алгоритма очень похожи на рентгеновские снимки.
• "Пропуск пространства" - Space Leaping
  Предобработкой производится выделение и объединение пустых участков пространства, и во время трассировки лучей такие участки просто пропускаются.
  Включает в себя трассировку лучей.
• Отображение с помощью фильтра
  Для каждого отображаемого вокселя определяется экранная координата его центра, а затем параметры вокселя "разбрасываются" по соседним пикселам с ипользованием некоторого фильтра. Коэффициенты фильтра зависит только от желаемого качества.
  Чаще всего используемый фильтр - считать проекцию воксела квадратом с однородными параметрами (Shadow Warrior).