Введение
Когда пишется графическая система трехмерной графики реального времени вначале вы должны решить, какие функции должна выполнять эта система, особенно, если эта система для игры. Далее вы должны подумать - "как избежать этого? ". Когда я познакомился с оригинальным алгоритмом вывода ландшафтов, я тут же отметил, что камера не требует сильных наклонов. Характер ландшафта, очевидно, позволяет ввести много упрощений в управление сценой, которые невозможны с более универсальной системой управления сцены. При визуализации ландшафта мы всегда знаем, что мы имеем дело с непрерывной поверхностью, которая простирается за экран во всех направлениях. В этой статье не содержит все, что нужно для создания полноценной трехмерной графической системы, всегда есть специфические случаи, с которыми приходится сталкиваться. В этой статье сосредоточимся только на ландшафтах.
Ограничения
Вот список всех ограничений, которые я счел приемлемым наложить на структуру уровней и работу камеры в графической системе. Конечно, это не все, но важно знать то, с чем Вы можете, или не может избежать неприятностей. Если Вы работаете в фирме на кого-то, сверьте этот список с вашим заданием.
- Нет крутых склонов, так как данные для создания сцены включают в себя сетку из равномерно расположенных точек называемых картой высот, это делает управление сценой невероятно простым.
- Нет необходимости наклонять камеру.
- Камера управляется пользователем через графическую систему, поэтому можно избежать придвижения камеры слишком близко к ландшафту.
Последний пункт очень важен, если камера никогда не может находиться очень близко от поверхности, мы можем полностью уйти от коррекции перспективы, которая требует много вычислений.
Прежде, чем я начну описывать, как фактически рисуется ландшафт, возможно, лучше всего, если я опишу основы линейного наложения текстур. Треугольник состоит из 3 вершин и 3 граней. Для каждой из вершин необходимо задать U и V координаты на текстуре. Пары координат U и V по существу описывают треугольную область на карте текстуры, которая будет отображена на треугольник, который затем отображается на экран. Мы отображаем текстуру по шагам вниз с левого до правого края треугольника, вычисляя соответствующее значение для U и V в каждой точке. Затем, следуя вдоль горизонтальной строки, используем возникающие в результате значения U и V, чтобы получить цвет из карты текстуры, который мы должны записать в буфер изображения. Освещение или другие эффекты обычно применяются перед записью в буфер изображения.
Так как ландшафт непрерывная поверхность, состоящая из треугольников, то любые два треугольника будут иметь смежную грань (кроме тех треугольников, что на краю сетки). Поэтому, если не предпринять некоторой оптимизации, то придется дважды выполнять сканирование и интерполяцию одного края, что вызовет много лишних вычислений.
Мое решение
Алгоритм, который представлен здесь, я выдумал летом 95 после окончания университета и началом работы в SCI. В то время я работал над игровой системой с моим хорошим приятелем Ричардом Маттиасом. Игровая система должна была быть переделанной версией системы, которую я описал как часть моей диссертации.
Вначале надо определить, какая ось на карте высот больше всего совпадает с горизонтальной осью экрана. Это можно сделать очень просто, проверив компоненты вектора направления камеры, т.е. какая из компонент X и Z имеет наибольшее значении (в левосторонней системе координат, где положительная ось Y направлена вверх). Следующий отрывок кода иллюстрирует это:
if ((abs(cam_look_x)>abs(cam_look_z)) {
// компонента X камеры больше
// тогда Y лучший выбор
} else {
// Y ось доминирует
// тогда X лучше
}
Каждую точку на карте высот надо преобразовать в 3-х мерную позицию во всемирных координатах. Мы делаем это при помощи умножения U и V координат точки карты на коэффициент масштабирования заданный для X и Z компонентов, затем мы используем соответствующую позицию поля высоты как Y компоненту.
На следующем шаге надо определить точки сетки, которые составляют видимую поверхность. Есть разные способы выполнения этого. В моем подходе (я уверен, что он не самом эффективном) надо найти точку на сетке, которая является видимой и затем шагать вдоль строки, лучше всего совпадающей с осью X на экране, проверяя каждую точку сетки при помощи трансформации ее в пространство экрана, пока не дойдем до края области просмотра. Затем шагаем по другой оси карты, пока не построим два массива, содержащие точки сетки, которые являются крайними для экрана на каждой стороне.
Каждая пара элементов массива представляет линию, от левой стороны края просмотра до правой, это ключ к алгоритму, мы можем использовать это, чтобы устранить избыточное сканирование краев. Мы будем визуализировать ландшафт, используя вертикальные полосы вместо горизонтальных, которые чаще всего применяются при визуализации полигонов. Теперь мы создаем таблицу, содержащую один элемент для каждой вертикальной строки на экране. Каждый элемент таблицы будет содержать информацию относительно того, что было нарисовано и где это было нарисовано. Мы инициализируем таблицу некоторыми соответствующими координатами. Следующий пример показывает возможное объявление для таблицы, также и пример функции инициализации.
#define screenwidth 320 // ширина экрана (в пикселях)
#define screenheight 200 // высота экрана (в пикселях)
typedef struct {
int disp_height;
int last_height;
char *disp_pos;
int U,V;
} ytab_struct;
ytab_struct ytab[screenwidth];
void initialise_ytab()
{
ytab_struct *ytptr;
int ind;
ytptr = &ytab;
for (ind=0;ind<screenwidth;ind++) {
ytptr->disp_height=screenheight;
ytptr->last_height=screenheight;
ytptr->U=ytptr->V=0;
ytptr->disp_pos=адрес_на_память_экрана + ind + (screenwidth*screenheight);
ytptr++;
}
}
Для каждой пары элементов в массиве точек мы должны просканировать пиксель за пикселем слева направо. Мы должны рассматривать по одной точке на вертикальную линию. Между преобразованными точками сетки, мы должны интерполировать вертикальную позицию на экран. Также необходимо интерполировать значения U и V для точек сетки. Этот процесс очень похож на сканирование краев треугольника или многоугольника, хотя мы должны отделить 'край' для каждой точки сетки, который находится внутри экрана для соответствующей линии на карте высот. Если мы нарисуем график вертикальной позиции каждой точки, после того как мы выполнили интерполяцию, то мы должны получить в результате что-то навроде следующего изображения. Изображение имеет невидимые линии, удаленные для ясности.
Отрисовка ландшафта сканированием
Теперь мы можем рассмотреть наложение текстуры. Чтобы текстурировать ландшафт, мы просто берем новые интерполируемые значения для Y, U и V, и используем их, чтобы рисовать вертикальную линию между уровнем соответствующего значения для disp_height и новой интерполируемой позиции Y. Если новое значение Y - меньше чем соответствующие значение disp_height, тогда мы знаем, что линейный сегмент закрыт частью ландшафта перед ним (или началом экрана). После того, как мы нарисовали вертикальную линию таким же способом как сканирование внутренней строки треугольника, мы сохраняем новую позицию Y, U и V обратно в таблицу, мы также модифицируем значение для disp_pos. Фактически весь процесс интерполяции вдоль и вверх экрана может быть выполнен в одной ассемблерной функции для улучшения эффективности. Для демонстрации приведу следующий Си псевдо код, который описывает функцию, в которую передается вертикальная позиция линии (как 'ind'), новая интерполируемая позиция Y (как 'new_y') и U и V координаты.
