Воксельные пейзажи

Цель работы и её краткое содержание

Вероятно, многие видели игру Comanche Maximum Overkill, где игрок управляет вертолетом RAH-66. Эта игра не является "нормальным" симулятором - в ней используются несколько иные подходы, чем в других играх подобного типа. Это приводит к тому, что многие считают, что этой игрой Nova Logic хотела продемонстрировать миру не хорошо сделанный симулятор, а, скорее, свои достижения в 3d графике.

Вскоре после выхода Comanche появилась маленькая (меньше 4 Кбайт) программа Mars выводящая ландшафты почти идеального на вид качества со скоростью, позволяющей перемещаться по виртуальному ландшафту без рывков на компьютере с 386 процессором. Справа вы видите кадр из этой программы. Другим ярким примером использования воксельной технологии является игра Magic Carpet.

Целью данной работы является ознакомление с использованным в этих программах алгоритмом, с одной стороны простым и быстрым, а с другой стороны представляющем собой пример воксельной технологии. Технологии, которой пророчат будущее одного из основных методов вывода 3-х мерной графики в играх в начале 2000 годов.

Общие сведения

Воксел (voxel, volume pixel) - элемент пространства, объемный пиксель. Воксельная технология подразумевает разбиение пространства на отдельные элементы (обычно плоскостями параллельными OXY, OXZ, OYZ) и рассматривание этих элементов как неделимых на более мелкие.

В простом алгоритме для построения ландшафта принимаются следующие допущения:

В результате получается примерно следующая картина:

Прорисовка поверхности производится не, как это обычно бывает, построчно, а по столбцам. В основе лежит следующий алгоритм:

для каждого скан-столбца найти ближайший параллелепипед верхняя_граница := 0; повторять найти высоту проекции параллелепипеда заполнить точки от верхняя_граница до высоты проекции цветом параллелепипеда найти следующий видимый параллелепипед пока (верхняя_граница ниже верхней границы экрана) и (параллелепипед не дальше горизонта) конец для

Поиск следующего параллелепипеда осуществляется перебором проекций, обычно методом Берзенхема. Просматриваются все вокселы, лежащие вдоль луча, проходящего из глаза через скан-столбец. Для получения направления луча можно воспользоваться стандартной формулой:

где

- расстояние от наблюдателя до экрана
- расстояние скан-cтолбца от центра экрана
- угол поворота наблюдателя

Для вычисления высоты параллелепипеда используется следующая формула:

Дополнительные сведения

Недостаток данного метода в том, что даже при использовании карт максимально допустимого размера (ограничения накладываются среднестатистическими техническими характеристиками ЭВМ) хорошо заметны отдельные воксели.

При работе с дискретной информацией во многих случаях удаётся улучшить качество её обработки при помощи использования аппроксимации. Самая простая, ступенчатая аппроксимация, как указывалось выше, в рассматриваемом случае не даёт хорошего качества. Воспользуемся линейной аппроксимацией.

В Mars'е аппроксимация используется сразу в двух местах. Во-первых, она применяется при выводе "столбиков" - они имеют не постоянный цвет, а плавно переходящий из начального - в предыдущем столбике - в конечный - в текущем столбике. А во-вторых, для определения высоты на карте ландшафта, если координаты точки нецелые. То есть при вычислении высоты очередного столбика берется не высота ближайшего параллелепипеда, а среднее от двух соседних по формуле:

Пример реализации алгоритма

Ниже представлен пример реализации алгоритма на языке Паскаль:

type TPoint = record x,y: integer; end; procedure DrawVoxelLandscape; var Scan: integer; // номер скан-столбца cmPosition: TPoint;// координаты текущего вокселя на карте csPosition: integer; // верхняя_граница cvHeight: integer; // высота текущего вокселя b_d,b_dx,b_dy,b_sy,b_ai,b_bi: integer; // переменные для алгоритма Берзенхема i: integer; begin for Scan := 0 to ScreenWidth-1 do begin cmPosition.x := MapMinDepth; cmPosition.y := Scan-(ScreenWidth div 2); csPosition := 1; // инициализация алгоритма Брезенхема b_dx := ViewerPosition; b_dy := Scan - (ScreenWidth div 2); if b_dy > 0 then begin b_ai := (b_dy - b_dx) * 2; b_bi := b_dy * 2; b_d := b_bi - b_dx; b_sy := +1; end else begin b_ai :=-(b_dy + b_dx) * 2; b_bi := -b_dy * 2; b_d := -b_bi - b_dx; b_sy := -1; end; // прорисовка скан-столбца repeat // поиск следующего параллелепипеда repeat inc(cmPosition.x); if (b_d >= 0) then begin inc (cmPosition.y,b_sy); inc (b_d, b_ai); end else inc (b_d, b_bi); // определение высоты проекции cvHeight := Round((LandMap[cmPosition.x,cmPosition.y] - ViewerHeight) (ViewerPosition - cmPosition.x) * ViewerPosition) + 100; until (cmPosition.x = MapHorizon) or (cvHeight > csPosition); // ограничить проекцию верхним краем экрана if cvHeight >= ScreenHeight then cvHeight := ScreenHeight; // отобразить проекцию for i := csPosition+1 to cvHeight do ScreenBuffer[ScreenHeight-i,Scan] := LandMap[cmPosition.x,cmPosition.y]; csPosition := cvHeight; until (cmPosition.x = MapHorizon) or (csPosition = ScreenHeight); // "небо" for i := csPosition+1 to ScreenHeight do ScreenBuffer[ScreenHeight-i,Scan] := 255; end;

В результате получается подобное изображение:

Задания на лабораторную работу

Простые задания:

1. Построить ландшафт:
   1. вулкана (уравнение поверхности , где )
   2. скалы с обрывом
      
   3. волн ( )
   4. холмистой местности
   5. горного озера (строится аналогично вулкану, но с ограничением высоты столбиков не ниже нуля и вывод их синим или голубым цветом).
   6. любой другой поверхности
2. Отобразить на экране пещеру (когда одновременно выводится ландшафт сверху и снизу с соединением справа и слева).
3. Добавить в алгоритм выбор высоты положения наблюдателя
4. Добавить фон (небо).

Сложные задания

1. Добавить управление с клавиатуры
2. Отобразить ландшафт с использованием интерполяции
3. Добавить объекты (спрайты, модели), выводимые над ландшафтом и закрываемые элементами ландшафта
4. Добавить эффекты (туман, дымка и т.п.)
5. Добавить фон (солнце, звезды).
6. Использовать полупрозрачные вокселы.
7. Использовать вокселы с текстурой.

Литература

1. "Часто задаваемые вопросы эхо-конференции DEMO.DESIGN", сост. Петр Соболев. Скачать архив можно по ссылке.

Список ссылок

Исполняемый (exe) файл примера Mars. Если у вас есть исходные коды (C++, Delphi) данного примера под Windows, прошу скинуть на email
Volcano. Игра имитирующая движение лавы в горном поселке. Вам нужно спасти от разрушения жилые дома. Воксельный движок, с широкими возможностями настройки качества отображения.
Voxel. Воксельный движок. Такую технологию применяли такие игры как: Commanche, DeltaForce. Ранее этот пример существовал в версии для TP, но вот теперь и для Delphi.