Программирование игр для Windows. Советы профессионала

       

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


Для создания реалистичного трехмерного изображения в играх используется техника, называемая отсечением лучей. Применяя эту технику, надо придерживаться некоторых правил, связанных с тем, что алгоритм отсечения лучей — это, в сущности, упрощение алгоритма трассировки, в котором все же осталось множество вычислительных проблем. Поэтому данный алгоритм применим только для наиболее простой геометрии создаваемых миров. В общем случае, отсечение лучей не будет работать, если вы решите сделать трехмерный имитатор полетов или попытаетесь смоделировать реальное пространство. Но в играх, где действие происходит в мире, нарисованном с помощью перпендикулярных линий, этот алгоритм работает изумительно. Для создания 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ау<320; rау++)

{

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

while

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

{

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

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

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

{

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

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

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

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

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

{

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

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

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

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

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

{

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

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

}

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

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

{

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

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

} // конец

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

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

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


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

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

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

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


Содержание раздела