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

Вид материала

Документы

Содержание Уравнение плоскости Использование уравнения плоскости для вершин многоугольника Формула 6.1. Подсчет количества элементов в таблице значений наклонов.

Подобный материал:

• План Введение. 3 Основная часть. 4 Что такое «компьютерная революция»? 4 Этапы революции., 90.65kb.
• Великий Мастер всю свою жизнь был счастливым, улыбка всегда озаряла его лицо. Вся его, 279.3kb.
• Аннотация Об, 2459.27kb.
• Марина Шарыпкина Ю. Солуянова Нина Богатырева Оксана Бобкова, 2907.61kb.
• Наполеон Хилл "Думай и богатей", 4434.97kb.
• Иерархия 1931 сознание, 2255.88kb.
• Урок литературы, 6 класс, учителя русского языка и литературы Румянцевой И. А. Создание, 100.1kb.
• Making Biblical Decisions Lecture: (6) The Situational Perspective: Pursuing our Goal, 424.8kb.
• Высшее мастерство состоит в том, чтобы выиграть поединок с обыденностью играя, 1240.66kb.
• Самарский Государственный Архитектурно-Строительный Университет Факультет информационных, 88.76kb.

^

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

Я говорил, что мы можем использовать уравнение плоскости для многоугольника, для нахождения значения 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ау<320; 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.