^

Уравнение плоскости

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

Дано: Точка (х,у) и вектор нормали к многоугольнику


Nz

Z = ---------------------------

1- Nx * X – Ny * Y

^

Использование уравнения плоскости для вершин многоугольника

А каким образом мы можем составить уравнение плоскости, зная только вершины многоугольника? Очень просто: так как все вершины прямоугольника принадлежат одной плоскости, мы можем взять две смежные вершины и построить к ним вектор нормали. Рисунок 6.18 показывает, как это сделать.

Вектор нормали может быть использован в уравнении плоскости для вычисления Z-компонента.



Имея вектор нормали к многоугольнику, уравнение плоскости находит Z-компонент для любой точки (х,у). При этом заданы: искомая точка (х,у) и вектор нормали к многоугольнику
Nz

Z = ---------------------------

1- Nx * X – Ny * Y
:


^

Соотношение пространства образов и пространства объектов

Алгоритм Z-буфера хорошо работает и может быть легко реализован. Единственная проблема состоит в том, что он работает на уровне пикселей и является алгоритмом обработки образа. Это значит, что он не рассматривает геометрических свойств объекта. Это требует наличия некоторого гибридного алгоритма для использования в специальных случаях. Такой алгоритм должен учитывать геометрические свойства объекта перед простым удалением невидимых поверхностей. Теперь давайте поговорим о том, как придать поверхности наших трехмерных объектов большую реалистичность.
^

Трассировка лучей

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

• 
  Удаление невидимых поверхностей;
  
• 
  Перемещение;
  
• 
  Отражение;
  
• 
  Рассеяние;
  
• 
  Окружающее освещение;
  
• 
  Точечное освещение;
  
• 
  Наложение теней.
  

Изначально этот алгоритм разрабатывался для решения проблемы удаления невидимых поверхностей. Трассировка лучей создает образ, исходя из тех же законов, что и наше зрение. На рисунке 6.19 изображено некоторое пространство, которое может быть просчитано с помощью алгоритма трассировки лучей. Вы видите несколько объектов: источник света, наблюдателя и план наблюдения.

Чтобы воспользоваться трассировкой лучей для создания натуральных образов, нам придется использовать миллиарды световых лучей из источника света, и затем рассматривать каждый из них, надеясь, что он попадет в план наблюдения и примет участие в создании образа. Возникает вопрос - а зачем трассировать каждый возможный луч? На самом деле, нас интересуют только те лучи, которые достигают плана просмотра.

Запомнив это, давайте попробуем трассировать лучи в обратном направлении. Проследим движение лучей для каждого из пикселей на экране, а затем посмотрим, где эти лучи пересекаются с планом просмотра. Отметив пересечение, мы останавливаемся и окрашиваем соответствующий пиксель в нужный цвет. Это называется первичной трассировкой лучей.



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

Трассировка лучей - это один из наиболее насыщенных вычислениями методов расчета трехмерных изображений, но зато и результаты получаются впечатляющими. Есть только одна проблема: для решения этой задачи в реальном времени не хватает мощности даже самого быстродействующего компьютера. Потому нам придется учесть данное обстоятельство и применить идею трассировки лучей для создания другого метода. Он будет более ограничен, но позволит нормально работать с трехмерными мирами на обычном ПК. Исходя из этого, мы попробуем реализовать упрощенный вариант трассировки лучей, используя только первичные лучи для генерации изображения. С последующими оптимизациями возможно достижение достаточно высокой производительности. Если вам интересно узнать, как это можно сделать, то стоит продолжить чтение нашей книги.
^

Отсечение лучей

Для создания реалистичного трехмерного изображения в играх используется техника, называемая отсечением лучей. Применяя эту технику, надо придерживаться некоторых правил, связанных с тем, что алгоритм отсечения лучей — это, в сущности, упрощение алгоритма трассировки, в котором все же осталось множество вычислительных проблем. Поэтому данный алгоритм применим только для наиболее простой геометрии создаваемых миров. В общем случае, отсечение лучей не будет работать, если вы решите сделать трехмерный имитатор полетов или попытаетесь смоделировать реальное пространство. Но в играх, где действие происходит в мире, нарисованном с помощью перпендикулярных линий, этот алгоритм работает изумительно. Для создания DOOM-образных миров применяется несколько иная техника, но и она базируется на этом же алгоритме.

Я написал маленькую демонстрационную программку, в основе которой лежит алгоритм отсечения лучей-. Она позволит вам «погулять» по трехмерному миру, состоящему из кубов. Весь этот мир на самом деле является двухмерной матрицей, считываемой из обычного ASCII-файла.

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

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

Поскольку здесь я использовал библиотеки поддержки математических операций с плавающей запятой, то программа работает довольно медленно. Когда вы ее оттранслируете и запустите, то увидите три окна вывода. Они показаны на рисунке 6.20. Изображение в левом углу экрана представляет собой плоскую карту Трехмерного мира, который является матрицей размером 64х64х64.

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



Идею алгоритма отсечения лучей можно представить так: вообразите, что вы стоите в пустой комнате и смотрите вперед. Все, что вы наблюдаете, это стены впереди и по обе стороны от вас. Образ, который вы видите, складывается из лучей, отразившихся от стен и попавших в ваши глаза. Но при отсечении лучей происходит не отражение от стен, а просто отсечение лишних лучей. На рисунке 6.21 показан образ, полученный таким методом.

Как и в системах лазерного сканирования, мы также как бы сканируем область вокруг нас и строим образ на основе полученных результатов. То, что мы в итоге получим, будет зависеть от поля просмотра. Это поле является той «порцией» информации, которую мы можем увидеть за один раз. Если мы способны обозреть пространство под углом 45° вправо и влево по отношению к направлению просмотра (рис. 6.22), то наше поле просмотра составит 90°.



Вообще, поле просмотра - это одно из ключевых понятий в технологии отсечения лучей. Поэтому мы должны определить, какое поле просмотра нам необходимо. Большинство животных имеет очень большое поле просмотра - 90 и более градусов. Правда, для нашего случая я выбрал его равным 60°. Просто мне нравится то, что получается при этом на экране. Вы сами можете задать любой другой угол, но постарайтесь, чтобы он попадал в диапазон между 60 и 90 градусами.

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



На рисунке 6.23 игрок находится в мире размерностью 8х8. Поскольку мы установили угол зрения игрока в 60°, то нам надо начать отсекать все лучи до угла 30° и все лучи после 120°. Как видите, я изобразил результат отсечения лучей на рисунке 6.23.

Первым вопросом обычно бывает: «А сколько лучей нам необходимо отсечь?». Ответ прост; количество отсекаемых лучей численно равно горизонтальному разрешению экрана, на который мы собираемся спроецировать образ. В нашем случае это 320 лучей, поскольку мы работаем в режиме 13h. Интуиция должна подсказать вам, что угол в 60° требуется разделить на 320 частей и для каждой из них произвести отсечение.

Поскольку мир, в котором мы отсекаем лучи, является двухмерным, то задача вычисления пересечений становится довольно простой. Более того, наш мир имеет регулярную структуру. Это значит, что количество вычислений резко уменьшается. Впоследствии я покажу множество маленьких хитростей, которые заставят работать этот алгоритм с фантастической скоростью (мы это сделаем чуть позже).

Мы имеем набор лучей, распределенных в диапазоне от -30 до +30 градусов к лучу зрения. Как мы уже говорили, поле просмотра у нас равно 60°. Давайте смоделируем на экране поле просмотра. Для этого нам нужно:

1. 
   Отсечь 320 лучей (один для каждого вертикального столбца на экране) и вычислить пересечение каждого луча с блоками, из которых состоит наша двухмерная карта мира;
   
2. 
   Используя эту информацию, вычислим дистанцию между игроком и точкой пересечения;
   
3. 
   Затем используем эту дистанцию для масштабирования вертикальной полосы. Горизонтальная позиция при этом соответствует координате текущего луча (0..319).
   

Алгоритм 6.1 показывает последовательность действий при отсечении лучей.

Алгоритм 6.1. Алгоритм отсечения лучей.

// Пусть игрок находится в позиции (хр,ур) и его взгляд

// Направлен под углом view_angle

// Инициализируем переменные

// Начальный угол -30 градусов относительно направления взгляда

стартовый угол = угол просмотра - 30;

// необходимо отсечь 320 лучей, по одному на каждый экранный столбец

for (ray=0; rау
{

вычислить наклон текущего луча

while (луч не отсечен)

{

// проверить на вертикальное пересечение

if (не пересекается с вертикальной стеной)

if (луч отсек блок по вертикали)

{

вычислить дистанцию от (хр,ур) до точки пересечения

сохранить дистанцию

} //конец проверки на вертикальное пересечение

if (не было пересечения с горизонтальной стеной)

if (луч отсек блок по горизонтали)

{

вычислить дистанцию от (хр,ур) до точки пересечения

сохранить дистанцию

} // конец проверки по горизонтали

} // конец цикла while

if (горизонтальное пересечение ближе вертикального)

{

вычислить масштаб по горизонтали

нарисовать полосу изображения

}

// конец оператора if

else // вертикальное пересечение ближе горизонтального

{

вычислить масштаб по вертикали нарисовать полосу изображения

} // конец оператора else

} // конец

Конечно, мы опустили множество деталей, но при этом четко формализовали основную идею алгоритма.

Единственный вопрос, который может смутить: «А почему это всегда работает?». Просто мы смоделировали процесс прорисовки образа частицами света. Правда, проделали мы это в обратную сторону, но главное — такой метод работает. Он удаляет невидимые поверхности, создает перспективу и содержит всю необходимую информацию для создания теней, освещения и текстур. Именно поэтому алгоритм отсечения лучей является очень мощным средством для программиста. Мы можем создавать в играх окружение, которое было бы невозможно получить, используя стандартную технику работы с многоугольниками.

Вы можете сказать, что мир, построенный из одинаковых блоков, выглядит весьма скучно. Да, это так, но если вы добавите тени и разукрасите стены всевозможной фактурой, все сказочно преобразится. Вы сможете создать восхитительное окружение для ваших игр. Впоследствии вы сможете уменьшить размер блоков для создания более сложных сцен. Кроме того, вы научитесь изображать поверхности с углом наклона в 45°. Все в ваших руках.

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

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

Правда, надо помнить вот о чем. Я написал программу отсечения лучей так, чтобы она легко читалась и была понятна. Это не значит, что с точки зрения скорости она идеальна. Нет, скорее наоборот. Но зато вы без особых усилий поймете принципы работы алгоритмов.
^

Математические основы отсечения лучей

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

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

• 
  рисование лучей;
  
• 
  вычисление координат первого пересечения;
  
• 
  вычисление координат следующего пересечения;
  
• 
  вычисление расстояния;
  
• 
  масштабирование;
  
• 
  уменьшение проекционного искажения;
  
• 
  рисование полос.
  

^

Рисование лучей

Очевидно, что лучи, которые мы отсекаем, на самом деле представляют собой линии. Они начинаются в точке зрения игрока, совпадающей с его позицией на двухмерной карте. Мы решили иметь поле просмотра равным 60°. Таким образом, нам нужно составить таблицу соответствия для всех возможных лучей, которые можно отсечь с любого угла просмотра. Эта таблица должна содержать значения наклонов всех возможных лучей по отношению к плану просмотра. Исходя из значения наклона, мы сможем произвести отсечение луча из точки наблюдения игрока.

^ Формула 6.1. Подсчет количества элементов в таблице значений наклонов.

Перед нами стоит вопрос — сколько элементов должно быть в таблице наклонов и как эти наклоны рассчитать? Для составления таблицы требуется знать, сколько в ней будет элементов. Когда игрок смотрит на мир, построенный отсечением лучей, то 320 лучей (количество горизонтальных точек экрана) вместе составят дугу в 60°. Таким образом, мы должны иметь таблицу с 1920 элементами или значениями наклонов. Это вычисляется по следующей формуле:

размер таблицы = ширина_экрана х 360 / поле_просмотра

В нашем случае ширина экрана составляет 320 пикселей, а поле просмотра - 60 градусов, поэтому результат будет равен 320х360/60 = 1920.
^

Определение значения наклона

Теперь нам надо вычислить каждый из элементов таблицы наклонов. Это должны быть действительные значения наклонов всех возможных линий, отсекаемых от точки наблюдения игрока. Поскольку мы разбили окружность на 1920 секторов, то каждый из них будет по 360/1920 = 0.1875 градусов. Таким образом, мы нашли способ вычисления наклона для всех линий окружности с шагом в 0.1875 градуса. Все это выглядит довольно сложным для вычисления. К счастью, проблему поможет решить функция tg (). Если вы забыли определение тангенса, то напомним, что для прямоугольного треугольника он равен отношению синуса к косинусу угла:


SinQ противоположная_сторона

TgQ = -------- = ------------------------------------

CosQ прилегающая_сторона



Если это так, то

М = tg q

Создав таблицу значений наклонов из 1920 элементов, где каждый наклон равен tg q, все остальные расчеты значительно упрощаются. Мы используем эти наклоны для построения лучей. Но есть несколько проблем:

• 
  Только в первом квадранте значения тангенса будут корректны. В других квадрантах он может быть как отрицательным, так и положительным, но вы не сможете узнать знак наклона, поскольку сама функция является частным. Таким образом, при программировании надо на это обратить внимание и выполнять вычисления в условном операторе;
  
• 
  Функция tg() имеет вертикальные асимптоты при углах в 90 и 270 градусов. Поэтому надо быть внимательным, чтобы избежать в этих точках деления на ноль или ошибок с плавающей запятой.
  

^

Вычисление линий для генерации

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

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

Помните, что игрок находится на плоской карте, которая используется для создания трехмерного образа. В нашем случае площадь мира составляет 16х16 ячеек, и каждая ячейка имеет размер 64х64 пикселя. Таким образом, мир имеет 1024х1024 виртуальных единиц измерения. Вне зависимости от позиции, игрок будет занимать несколько ячеек игрового пространства, поскольку «размер» самого игрока равен размеру ячейки. Эта позиция вычисляется простым делением глобальной позиции игрока, которая меняется от 0 до 1023 для Х и Y, на 64,или

ячейка_х = х_размерность / 64

ячейка_у = у_размерность / 64

где х_размерность и у_размерность находится в пределах от 0 до 1023.

Когда координаты текущей игровой ячейки будут вычислены, мы сможем найти ее пересечение с текущим лучом. Давайте рассмотрим математику для выполнения этих действий.
^

Вычисление точки первого пересечения

Существует множество способов описания прямой: от параметрического до функционального. Мы будем рассчитывать нашу прямую с помощью функции, описывающей линию.

формула 6.2. Вычисление первой Y-координаты пересечения.


(Yi – Yp)

------------- = M

(Xi – Xp)

где (Xi,Yi) - точки пересечения линии и (Xp,Yp) — позиция игрока. После некоторых алгебраических преобразований получаем:


Yi = M * (Xi – Xp) + Yp

^ Формула 6.3. Вычисление первой Х-координаты пересечения.


Xi = M-1 * (Yi – Yp) + Xp

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

Единственное, что может нас расстроить в этих преобразованиях, это их рекурсивность: каждое преобразование требует предварительного вычисления Другого. Это несколько затруднительно. Но вы можете заметить, что Xi в первом равенстве на самом деле означает «первая граничная вертикальная линия», a Yi во втором выражении означает «первая граничная горизонтальная линия». В этом и заключена изюминка метода отсечения лучей для квадратных матриц. Далее, мы знаем, что луч пересекается с каждой из ячеек в вертикальном и горизонтальном столбце. Рисунок 6.24 поясняет это, Если мы однажды вычислим первое пересечение, то сможем найти и все остальные пересечения с лучом, а также конец его траектории.

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

Некоторые, программисты любят это делать за два прохода: в первом вычисляются все возможные горизонтальные пересечения, а во втором — все вертикальные пересечения. Рисунок 6.25 демонстрирует эту идею.

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



^

Вычисление оставшихся пересечений

После того как мы нашли первое пересечение для вертикальной и горизонтальной стены, можно найти следующую точку возможного пересечения — достаточно прибавить константы к текущей точке пересечения. Например, если координата Yi пересечения равна 100, то следующая точка Yi может быть рассчитана простым прибавлением числа 100.

В нашем случае каждая ячейка имеет размеры 64х64, и чтобы найти следующее пересечение мы используем следующие формулы:

Формула 6.4. Вычисление Х-координаты следующего возможного пересечения.

Следующее Xi = Xi + М х (ширина ячейки)

Формула 6.5. Вычисление Y-координаты следующего возможного пересечения.

Следующее Yi = Yi + М х (высота ячейки)

где высота и ширина ячейки равна 64.

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

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

Вычисление расстояния

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

• 
  Чтобы узнать тип пересечения (вертикальное или горизонтальное);
  
• 
  Чтобы выяснить масштаб стен.
  

Формула 6.6. Теорема Пифагора.

Мы можем использовать для этого теорему Пифагора;

Н =sqrt (х2 + у2)

Это прекрасная формула, но ужасно сложная для ПК, поскольку вычисление квадратного корня — процесс весьма медленный и долгий. Мы, конечно, можем использовать табличное представление функции квадратного корня, но и в этом нет ничего хорошего. Есть другой, более простой способ найти удаление точки пересечения от игрока, если вычислить координаты точек и найти sin © и cos ©.

Давайте посмотрим на рисунок 6.26.

Поскольку мы уже вычислили точки вертикального и горизонтального пересечения, мы можем воспользоваться известным правилом, чтобы найти синус и косинус угла наклона:

• 
  Угол наклона луча (он у нас есть);
  
• 
  Длина гипотенузы (мы ее хотим найти);
  
• 
  Длина сторон треугольника (который мы имеем).
  

Назвав переменные так же, как они обозначены на рисунке 6.26, напишем формулы для вычисления длины- гипотенузы (или, что-то же самое - искомого расстояния).




Формула 6.7. Вычисление расстояния до точки Х-пересечения.

расстояние = (Xi - Хр) х cos-1 A

Формула 6.8. Вычисление расстояния до точки Y-пересечения.

расстояние = (Yi - Yp) x sin-1 A

где А - это угол луча, который рассматривается в настоящее время. В программе это просто индекс от 0 до 1920 для таблицы вычисленных значений sin-1 и cos-1.

Это может показаться громоздким, но если это правильно написать и оптимизировать, то процесс будет занимать несколько миллисекунд. После того как расстояние будет вычислено, встает вопрос, что ближе, а что дальше на экране.
^

Вычисление масштаба

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

Для вычисления масштаба мы применяем сравнение между Х- и Y-пересечениями. Масштаб или высота вычисляется на основе ближайшего пересечения. Когда мы вычисляем масштаб битовой карты, мы можем использовать само расстояние:

масштаб = расстояние до пересечения

Это не всегда срабатывает: приближаясь, объекты становятся больше, но не уменьшаются при удалении. Тогда можно применить такую формулу:

масштаб = 1 / расстояние до пересечения

Это работает. Но результат надо умножить на некоторый коэффициент расстояния (или правдоподобия — как вам больше нравится).

масштаб = К / расстояние до_пересечения

где К стоит подобрать самостоятельно.
^

Уменьшение проекционных искажений

Проблема, о которой нам надо поговорить, заключается в проекционном искажении. Как вы знаете, для реализации отсечения лучей мы нарушили правило и использовали одновременно полярные и декартовы системы координат. Это привело к эффекту «рыбьего глаза» (то же самое возникает, когда вы смотрите сквозь сильную линзу).

Это сферическое искажение возникает вследствие использования нами при трассировке лучей радиального метода. Мы рассчитываем все лучи, выходящие из одной точки (позиции игрока). Сферические искажения возникают потому, что все объекты, с которыми пересекаются лучи, определены в «прямоугольном» пространстве. Расчет же лучей проводится в «сферическом» или «полярном» пространстве. Пример такого пространства представлен на рисунке 6.27.



Теперь посмотрим на рисунок 6.28. Мы увидим, что наблюдает игрок, когда смотрит прямо на стену. Он видит прямоугольник. Но так как расстояния до точек пересечения различны, изображение получается искаженным. Рисунок 6.29 показывает два результата отсечения лучей. Первый построен с учетом компенсационных искажений, а второй — без их учета. Все это очень интересно, но как это реализовать? Ответ прост: нужно умножить функцию масштаба на инверсную функцию. Синусоидальное искажение может быть компенсировано умножением масштаба на cos-1 текущего угла по отношению к полю наблюдателя (60 градусов). То есть мы должны умножить каждое значение угла от -30 до +30 на cos-1 того же угла. Это исключит искажение.



^

Отрисовка фрагментов стен

Наконец, мы должны нарисовать фрагмент битовой карты, который представляет одну вертикальную полосу окончательно сформированного экрана. Как я уже говорил, размер вертикальных фрагментов рассчитывается относительно средней линии, делящей экран на две горизонтальные плоскости. Таким образом, после того как мы рассчитали окончательный масштаб изображения, верхняя и нижняя границы фрагмента могут быть определены по формуле:

top = 100 - scale/2 // верхняя граница

bottom = top + scale // нижняя граница

где scale — окончательные вертикальные размеры фрагмента.
^

Реализация отсекателя лучей

Я написал совершенно полную реализацию алгоритма отсечения лучей. Он закомментирован и даже содержит какую-то логику. Эта программа включена в комплекте поставки на дискете в файле RAY. С. Демонстрационная программа загружает двухмерную карту мира в виде ASCII-файла. На рисунке 6.30 приведена подобная карта. Она создается с помощью обычного текстового редактора.

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



1111111111111111

1 1

1 11111 1

1 1 1 1 1 1

1 1 1 1

1 1 11 1

1 1

1 1

1 1

1 11 111111 1

1 1 1 1

1 111 1 1

1 1 1 1

1 11111111 1 1

1 1

1111111111111111



Листинг 6.4. Процедура отсечения лучей (RAYLIST.C)

void Ray_Caster(long x, long y,long view_angle)

{

// эта функция выполняет расчет 320 лучей и строит игровой

// экран на основе их пересечений со стенами. Расчет производится

// таким образом, что все лучи отображаются на поле просмотра

// с углом 60 градусов

// после расчета траекторий лучей, рассчитываются координаты

// их пересечений со стенами. Координаты первой точки пересечения

// запоминаются. Ближайшие к игроку точки используются для

// построения битового образа изображения. Расстояния используются

// для определения высоты текстурных фрагментов и вертикальных линий

// Примечание: эта процедура использует функции стандартной

// библиотеки компилятора для работы с плавающей точкой

// (это работает медленно). Код не оптимизирован (еще медленнее),

// и в довершение всего обращается к функциям графической

// библиотеки компилятора фирмы Microsoft (что уж вовсе

// никуда не годится!) // Однако все это имеет определенную цель - легкость

// для понимания того, как работает процедура

int rcolor;

long xray=0, // счетчик вертикальных пересечений

yray=0, // счетчик горизонтальных пересечений

next у cell, // используются для вычисления

next_x cell, // номера следующей ячейки по ходу луча

cell_x, // координаты текущей ячейки

се11_у, // луча

x_bound, // следующие вертикальная

у_bound, // и горизонтальная точки пересечения

xb_save, // в этих переменных запоминаются

yb_save, // координаты точек пересечения

x_delta, // эти переменные показывают, на сколько

y_delta, // надо сместиться для перехода к следующей ячейке

ray, // текущий луч для отсечения

casting=2, // показывает компоненты Х и Y луча

x_hit_type, // координаты блока, с которым пересекся луч

y_hit_type, // используются при отрисовке

top, // верхняя и нижняя координаты области,

bottom; // отрисовываемой как стена (с помощью текстуры)

float xi, // используется для определения х- и у-пересечений

yi,

xi_save, // используется для сохранения

// точек пересечения Х и У

yi_save,

dist_x, // расстояние до х- и у-пересечениЙ

dist_у, // от точки просмотра scale;

// масштаб

//СЕКЦИЯ 1 ////////////////////////////////////////

// инициализация

// вычисляет начальный угол от игрока. Поле просмотра 60 градусов.

// Таким образом, рассматриваем только половину - 30 градусов

if ( (view_angle-=ANGLE_360)
// разворачиваем вектор направления взгляда

view_angle=ANGLE_360 + view_angle;

} // конец оператора if

// выбираем цвет для луча

rсо1оr=1 + rand()%14;


//СЕКЦИЯ 2 ////////////////////////////////////////

// цикл для всех 320 лучей

for (ray=0; ray
// вычислить первое х-пересечение

if (view_angle >= ANGLE_0 && view_angle
{

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

// Примечание: эта линия должна быть выше (впереди

// на игровом поле) игрока.

y_bound = CELL_Y_SIZE + CELL_Y_Sf2E * (у / CELL_Y_SI2E);

// вычислить смещение для перехода к следующей

// горизонтальной линии

y_delta = CELL_Y_SIZE; // размер ячейки по вертикали (ред.)

// основываясь на первой возможной горизонтальной линии отсечения,

// вычислить Х-пересечение и начать расчет

xi = inv_tan_table[view_angle] * (y_bound - у) + х;

// установить смещение

next_у_cell = 0;

} // конец обработки верхней половины плана

else

{ // вычислить первую горизонтальную линию, которая может

// пересекаться с лучом. Это будет позади игрока

y_bound = CELL_Y_SI2E * (у / CELL_Y_SIZE);

// вычислить смещение для следующей горизонтальной линии

y_delta = -CELL_Y_SIZE;

// основываясь на первой возможной горизонтальной линии отсечения,

// вычислить Х-пересечение и начать расчет

xi = inv_tan_table[view_angle] * (y_bound - у) + х;

next_y_cell = -1;

} // конец обработки нижней половины плана

//СЕКЦИЯ 3 ////////////////////////////////////////

// вычислить первое х-пересечение

if (view_angle = ANGLE_270) {

// вычислить первую вертикальную линию, которая будет

// пересекаться с лучом. Она должна быть справа от игрока

x_bound = CELL_X_SIZE + CELL_X_SIZE * (х / CELL_X__SIZE);

// вычислить смещение

x_delta = CELL_X_SIZE;

// основываясь на первой возможной вертикальной линии отсечения,

// вычислить Y-пересечение и начать расчет

yi = tan_table[view_angle] * (x_bound - х) + у;

next_x_cell = 0;

} // конец обработки правой половины плана

else

{

// вычисляем первую вертикальную линию, которая может быть

// пересечена лучом. Она должна быть слева от игрока

x_bound = CELL_X_SIZE * (х / CELL_X_SIZE);

// вычислить расстояние до следующей вертикальной линии

x_delta = -CELL_X_SIZE;

// основываясь на первой возможной вертикальной линии отсечения,

// вычислить Y-пересечение

yi = tan_table[view_angle] * (x__bound - x) + у;

next_x_cell = -1;

}

// начать отсечение

casting = 2; // два луча для одновременного отсечения

хrау = уrау = 0; // сбросить флаги пересечения

//СЕКЦИЯ 4 ////////////////////////////////////////

while(casting)

{

// продолжить отсечение лучей

if (xray!=INTERSECTION_FOUND)

{

// тест на совпадение луча с асимптотой

if (fabs (y_step[view_angle])==0)

xrау = INTERSECTION_FOUND;

casting--;

dist_x = 1e+8;

} // конец проверки на совпадение с асимптотой

// вычислить текущую позицию карты для проверки

сеll_х = ( (x_bound+next_x_cell) / CELL_X_SIZE);

cell_y = (long)(yi / CELL_Y_SIZE) ;

// проверить, есть ли в этом месте блок

if ((x_hit_type = world[(WORLD_ROWS-1) - cell_y][cell_x])!=0)

{

// вычислить расстояние

dist_x = (yi - y) * inv_sin__table[view angle];

yi_save == yi;

xb_save = x_bound;

// закончить х-отсечение

хrау = INTERSECTION_FOUND;

casting--;

} // конец проверки попадания луча на стену блока

else

{

// вычислить следующее Y-пересечение

yi += y_step[view_angle];

} //конец оператора else

} // конец проверки на отсечение по оси Х

//СЕКЦИЯ 5 ////////////////////////////////////////

if (yray!=INTERSECTION_FOUND)

{

// тест на попадание луча на асимптоту

if (fabs(x_step[view_angle])==0)

{

уrау = INTERSECTION_FOUND;

casting--;

dist_y=1e+8;

}

// вычислить позицию карты

ceil_x = (long)(xi / CELL_X_SI2E);

cell_y = ( (y_bound + next_y_cell) / CELL_Y_SIZE) ;

// проверить, находится ли в этом месте блок

if ((y_hit_type = world[(WORLD_ROWS-1) - cell_y] [cell_x] ) !=0)

{

// вычислить расстояние

dist_y = (xi - х) * inv_cos_table[view angle];

xi_save = xi;

yb_save = y_bound;

// закончить вычисление Y-пересечения

yray = INTERSECTION_FOUND;

casting--;

} // конец обработки попадания луча на блок

else

{

// вычислить следующее Х-пересечение

xi += x_step,[view_angle];

} // конец оператора

else

} // конец проверки на отсечение по оси У

// перейти к следующей точке пересечения

x_bound += x__delta;

y_bound += y_delta;

}

//СЕКЦИЯ 6 ////////////////////////////////////////

// выяснить, какая из стен ближе - вертикальная или горизонтальная

// и затем нарисовать ее

// Примечание: в дальнейшем мы заменим вертикальную линию на

// текстурный блок, пока же достаточно того, что есть

if (dist_x
{

sline(x,y,(long)xb_save,(long)yi_save, rcolor);

// вертикальная стена ближе горизонтальной

// вычислить масштаб и умножить на поправочный коэффициент

// для устранения сферических искажений

scale = cos_table[ray]*15000/(1e-10 + dist_x);

// вычислить координаты верха и низа

if ( (top = 100 - scale/2)
if ( (bottom = top+scale) > 200) bottom=200;

// нарисовать фрагмент стены

if ( ((long)yi_save) % CELL_Y_SIZE
else

_setcolor(10);

_moveto((int)(638-ray),(int)top);

_lineto((int)(638-ray),(int)bottom);

}

else // сначала надо нарисовать горизонтальную стену

{

sline(x,y,(long)xi_save,(long)yb_save,rcolor) ;

// вычислить масштаб

scale = cos_table[ray]*15000/(le-10 + dist_y);

// вычислить координаты верха и низа

if ( (top = 100 - scale/2)
if ( (bottom = top+scale) > 200) bottom=200;

// нарисовать фрагмент стены

if (((long)xi_save) % CELL_X_SIZE
else

_setcolor(2);

_moveto((int)(638-ray),(int)top);

_lineto((int)(638-ray),(int)bottom) ;

} //конец оператора else

//СЕКЦИЯ 7 //////////////////////////////////////

//отсечь следующий луч

if (++view_angle>=ANGLE_360)

{

// установить угол в 0

view_angle=0;

} // конец оператора if

} // конец цикла for по лучам

} // конец функции

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

• 
  Первая часть произведет инициализацию всех массивов и внутренних переменных. В этой части определяется направление взгляда игрока и на его основании вычисляется стартовый угол. Также в этой секции выбирается случайное число, задающее цвет трассируемого луча;
  
• 
  Вторая и третья части вычисляют Х- и Y-пересечения текущего луча с периметром ячейки, в которой находится игрок. После того как найдено первое пересечение как с осью X, так и с осью Y, устанавливается значение нескольких переменных для определения траектории луча по отношению к осям координат. Информация, полученная в этих частях, используется в четвертой и пятой части;
  
• 
  Четвертая и пятая части продолжают проверку пересечений. Каждое из пересечений с координатной осью проверяется на пересечение с объектом. Если это происходит, то вычисляется дистанция и запоминается для дальнейшего использования. Эта информация может быть использована для текстурирования объектов. Хотя рассмотренный нами трассировщик лучей и не делает этого, он предоставляет достаточно информации для текстурирования. Например, если луч пересекает середину стены блока, это означает, что мы должны вывести на экран 32-ю вертикальную полосу соответствующей текстуры. Более подробно этот вопрос будет рассмотрен позднее, в главе, посвященной описанию игры Warlock;
  
• 
  В шестой части заканчивается обработка луча. К этому моменту мы уже вычислили горизонтальные и вертикальные пересечения и запомнили расстояния до них. Следовательно, мы готовы нарисовать на экране соответствующую лучу вертикальную полосу. Для этого мы определяем, которое из пересечений находится ближе всего. Горизонтальная позиция для отрисовки соответствует номеру текущего луча и меняется в диапазоне от 0 до 319. Высота рисуемого фрагмента вычисляется на основании расстояния до игрока и с некоторыми корректировками для улучшения впечатления;
  
• 
  Седьмая часть увеличивает текущий угол и осуществляет переход к первой части. Цикл выполняется до тех пор, пока все 320 лучей не будут отсечены.
  

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

Оптимизация отсекателя лучей

Отсекатель лучей, который мы написали, сложно назвать законченной программой. Она не делает множества вещей, но, несмотря на это, давайте поговорим как можно заставить ее работать быстрее.

• 
  Первое и обязательное условие — это использование целочисленной арифметики вместо операций с плавающей запятой. Это позволит увеличить скорость примерно в 2-4 раза;
  
• 
  Во-вторых, мы можем многое оптимизировать в самом тексте программы на Си. Это поднимет быстродействие примерно на 20-50 процентов;
  
• 
  Далее, мы можем разбить Х- и Y-отсечения на две независимые программы. Это позволит производить вычисления параллельно;
  
• 
  И, наконец, никакая нормальная программа не станет использовать графическую библиотеку Microsoft или разрешение 640х480.
  

Если использовать уже написанные функции для режима 13Ь, то выполнение программы ускорится в 10 раз и она начнет работать со скоростью 30 кадров в секунду. Но даже если скорость окажется около 15 кадров в секунду, то я буду рад.
^

Отрисовка дверей и прозрачных областей

Я надеюсь, вы видели, как открываются двери в Wolfenstein'e и DOOM'e. Когда они открыты, вы можете заглянуть в соседнюю комнату. С точки зрения трассировки лучей, при этом возникает множество проблем. С одной стороны, Дверь должна быть нарисована. С другой — должно быть нарисовано и то, что находится позади нее. Для решения этой проблемы луч трассируется до пересечения с дверью и затем проходит сквозь нее.

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

Это достигается следующим образом:

1. 
   В процессе трассировки луч достигает сплошной стены.
   
2. 
   Если стена содержит отверстия, пересечение все равно засчитывается и запоминается расстояние до игрока. Но трассировка луча продолжается дальше, до пересечения со следующей стеной.
   
3. 
   Запоминается полученное пересечение.
   

Этот процесс может продолжаться до бесконечности, но сейчас давайте предположим, что он прекращается после пересечения второй стены. Как показано на рисунке 6.31, мы получаем два пересечения.



Первое пересечение позволит отрисовать соответствующую вертикальную полосу. Однако второе пересечение тоже даст вертикальную полосу. Корректная отрисовка обоих вертикальных фрагментов осуществляется в соответствии с Алгоритмом Художника. Таким образом, вначале на основе полученных от второго пересечения данных будет отрисован более удаленный фрагмент стены, который затем будет частично перекрыт ближним фрагментом. Полученное таким образом изображение и будет выглядеть так, как если бы мы заглядывали в соседнюю комнату через окно.

Аналогично обрабатывается и открывание двери. Если дверь открывается вправо или влево, она частично уходит внутрь косяка. Таким образом, часть изображения физически исчезает с переднего плана. Для создания такого эффекта мы должны продолжить трассировку луча после пересечения с дверью. Однако в отличие от окон, убранная часть двери является полностью прозрачной, поэтому нам не надо запоминать оба пересечения. Мы вполне можем ограничиться отрисовкой изображения, полученного на основе пересечения луча с удаленной стеной. В общем, все эффекты типа окон, открывающихся дверей и т. п. создаются тем же способом, что и рассмотренные примеры — сочетанием трассировки луча через прозрачные области и простого механизма Z-буферизации.
^

Освещение, тени и палитра

Я хочу вам рассказать, каким образом выполнены световые эффекты в DOOM и как это можно реализовать. Более подробно об этом можно будет прочитать в седьмой главе.

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

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

Рассеянное освещение

Рассеянное освещение создает находящийся в комнате источник света. Например, если у вас есть регулируемая лампа, то вы можете изменять уровень рассеянного освещения. Рисунок 6.32 показывает комнату при двух разных уровнях рассеянного освещения.



Естественно, чем большим количеством источников света вы располагаете, тем больше у вас возможностей воздействовать на рассеянную освещенность. Самый хороший пример общей освещенности - солнечный свет. Солнце находится от нас на столь большом, расстоянии, что падающие на землю лучи можно считать параллельными. Это создает некоторую среднюю или рассеянную освещенность, интенсивность которой зависит от высоты солнца над горизонтом.
^

Локальное освещение

Локальное освещение представляет собой концентрацию интенсивности света в определенном направлении с целью освещения ограниченной части помещения. Например, если, лежа в кровати, вы включите фонарик и направите его на стену, то увидите световое пятно (рис. 6.33). Если же вы включите свет, то, даже, несмотря на рассеянное освещение, увидите, что область, освещаемая фонариком, сохранится до тех пор, пока интенсивность локального и рассеянного освещения не станут равны.



^

Закон Ламберта

Давайте поговорим об отражении и интенсивности. Если источник света направлен на поверхность под некоторым углом и наблюдатель смотрит на поверхность параллельно нормали, то интенсивность света изменяется в соответствии с законом Ламберта:

Id= Ii Kd cosQ 0
где:

• 
  • Id - результирующая интенсивность;
  
• 
  • Ii - интенсивность источника;
  
• 
  • Kd — коэффициент отражения материала;
  
• 
  • Q - угол между нормалью и направлением освещения.
  

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

Закон обратных квадратов

Интенсивность света уменьшается обратно пропорционально квадрату расстояния до источника. То есть чем дальше вы находитесь от источника, тем меньше его интенсивность. Кстати, все это звучит очень правдоподобно.
^

Создание модели освещения

Сейчас мы уже изучили всю физику, которую надо знать для формирования хорошо выглядящей модели освещения. Мы знаем, что:

• 
  Чем дальше находится источник, тем меньше света он дает;
  
• 
  Если поверхность расположена под углом к источнику света, она отражает меньше света;
  
• 
  Если изменяется уровень рассеянного освещения, это сказывается на всех объектах в комнате. Все эти три фактора, взятые в совокупности, и формируют модель освещения.
  

Нам известны: угол, под которым виден источник света, уровень рассеянного освещения и расстояние до каждой из стен. Возникает вопрос: все ли это нам нужно? Может быть все, а может быть и нет. Это зависит от того, что называть реалистичным. Наша главная задача - сформировать затенение стен так, чтобы они выглядели реальными, но, в то же время, изображение стены формируется с помощью текстуры.

Существует два пути устранения этого противоречия.

Мы могли бы рассчитывать интенсивность каждого пикселя "на лету" и окрашивать его в соответствующий цвет. Единственная, возникающая при этом проблема, - недостаточное количество одновременно отображаемых цветов. Мы располагаем только 256 регистрами цвета, следовательно, одновременно на экране не может присутствовать больше 256 цветов. Это заставляет нас использовать цвет с большой осторожностью.

Тем не менее, это вполне работоспособный метод, дающий хорошие результаты. Я оставляю целиком на ваше усмотрение применимость к получающимся изображениям термина «реалистичные», но они достаточно хороши для видеоигр на ПК. Мы знаем, что должны изменять оттенок цвета стен в зависимости от угла, под которым они видны, и от их расстояния до игрока. Мы также знаем, что интенсивность окраски стен зависит от уровня рассеянного света. Теперь давайте сконцентрируемся на эффектах, связанных с углом обзора поверхности и расстоянием до нее.

Выполняя трассировку лучей, мы выводим на экран фрагмент текстуры. Ее вид определяется содержимым регистров RGB в таблице цветов (см. пятую главу). Для выполнения операции затенения мы должны знать угол, образуемый поверхностью с направлением взгляда, и расстояние до нее. К счастью, нам известно и то и другое. Теперь осталось только выяснить, как использовать имеющуюся информацию для формирования затенения.

На практике нам нет необходимости использовать оба параметра в алгоритме затенения. Мы можем использовать или расстояние от стены до игрока или угол между направлением взгляда и поверхностью стены для получения вполне реалистичного изображения. Единственная проблема состоит в том, как получить все возможные эффекты затенения с помощью только 256 цветов?

Для решения этой проблемы мы можем создать палитру со следующими свойствами:

• 
  Первые 16 цветов - стандартные цвета EGA;
  
• 
  Дополнительные цвета помещаются в следующие 56 ячеек палитры. Это те цвета, с которыми мы будем работать, и единственные цвета, присутствующие в игре. Эти 56 цветов должны быть выбраны так, чтобы их хватило в качестве базовых для изображения всех игровых объектов. Более того, эти цвета будут самыми яркими в игре и они должны создаваться с учетом этого факта;
  
• 
  Теперь некоторая хитрость. Оставшиеся 184 цвета разбиваются на 3 банка по 56 цветов в каждом и банк из 16 цветов в конце палитры.
  

Три дополнительных банка по 56 цветов будут заполняться в процессе работы программы и использоваться механизмом формирования затенения. Дополнительный банк из 16 цветов используется для анимации палитры. Таким образом, палитра будет выглядеть как Представлено в таблице.

Таблица 6.1. Цветовая палитра для формирования затенения.

^ Регистры цвета

Функция

0 - 15

Базовые цвета EGA

16 - 71

Первичные цвета

72 - 127

Вторичные затененные производные первичных цв