Загрузка...
 
Программируем 3D-шутер от первого лица (FPS) (Win32, C++, DirectX9)

1.16 Управление сценой (Scene Management)


В этой Главе:

  • Изучим различные виды отсечения (culling): усечённая пирамида вида (view frustum) и отсечение при перекрытии (occlusion culling).
  • Рассмотрим темы определения столкновений (collision detection), реакции на них (response) и гравитации (gravity) в игре.
  • Создадим эффективную систему рендеринга с использованием т.н. дерева октантов (октодерева, octree(external link)).


Наш движок почти закончен и скоро будет готов к действию. В этой Главе мы сфокусируемся на разработке т.н. системы управления сценой (scene management system) и её последующей интеграции в движок.1

Что из себя представляет управление игровой сценой?

Ты, должно быть, уловил основную идею управления сценой ещё в Главе 1.1. Если помнишь, игровая сцена представляет собой игровой уровень или карту (map, мапу) в игре. Она полностью определяет 3D-окружение, ограниченное каким-либо способом и отделённое от других сцен игры (вспомним экраны загрузки с надписью "Loading" в классическом Half-Life), прямо как сцены в кино.
Термин "управление сценой" включает в себя все аспекты, связанные с управлением сценой в игре. Задачи по управлению сценой могут сильно отличаться в разных играх. Тем не менее существуют несколько общих элементов, присущих всем играм:

  • Возможность корректной загрузки и уничтожения сцены.
  • Управление данными сцены, как например игровые объекты.
  • Показ сцены игроку, который в большинстве случаев происходит путём рендеринга её 3D-геометрии.

Список далеко не полный. Мы можем разбить его на несколько более специфичных задач. Вообще необходимо заранее определить задачи, которые потребуются для выполнения в ходе создания движка и игры. Ведь управление сценой в одной игре может сильно отличаться от оного в другой по своим методам. Кроме того нам необходимо определить, что должно управляться движком, а какие задачи оставить для выполнения непосредственно игрой. К счастью мы знаем, что наш движок разработан специально для игр жанра FPS (First Person Shooter) поэтому мы можем сделать массу предположений и разработать управление сценой, "заточенное" именно под игры данного типа. Это вовсе не значит, что наш движок будет совершенно неприменим для игр других жанров. Просто в этом сучае он будет не настолько хорош и потребует соответствующего модифицирования.
А теперь более подробно остановимся на задачах, которые должен выполнять наш движок для управления сценой в FPS-игре. Во-первых, нам необходимо чтобы наш движок обладал возможностью загружать сцену с использованием простого скрипта. Скрипт будет определять такие свойства, как например какой 3D-меш для этого использовать, как будет выглядеть освещение и т.д. Движок также должен уметь считывать иерархию фреймов из файла меша сцены а также идентифицировать определённые типы фреймов, которые в него входят. Это позволит нам хранить прямо в файле меша сцены такие данные, как точка спауна (появление на игровой сцена) объекта игрока и координаты спавн-объектов. Также не забываем о том, что наш движок долен уметь корректно уничтожать сцену при завершении работы игрового приложения с целью не допустить утечек памяти.
Когда дело касается управления данными игровой сцены, мы хотим чтобы движок контролировал все объекты сцены и вовремя их обновлял. Помимо этого он должен уметь определять столкновения объектов друг с другом и со сценой а также давать возможность объектам взаимодействовать друг с другом. Мы также хотим, чтобы движок рендерил сцену и все объекты на ней. Движок также должен уметь разбивать сцену на составляющие и эффективно рендерить те из них, которые видны игроку в данном кадре.
Как только мы реализуем все эти фичи в движке, это снимет с нас основной груз связанных с этим забот при разработке непосредственно игры. Часть материала в этой Главе считается наиболее хардкорной для изучения. Но без этого никуда. Читаем медленно и вникаем в суть написанного.

Отсечение (Culling)

Один из наиболее важных аспектов управления сценой это её рендеринг. В данный момент мы не будем говорить конкретно о рендеринге. Вместо этого мы обсудим, как этого самого рендеринга избежать... Да, всё верно. Мы рассмотрим методы, которые позволят нашему движку избежать ренедринга как можно большей части сцены, которая, как правило, остаётся за кадром. Это делается с целью снизить нагрузку на видеокарту и таким образом сделать рендеринг максимально эффективным, в том числе для снижения системных требований игры.
Производительность игры (game's perfomance) часто измеряется по числу кадров в секунду (fps), которое она может выдать в данной ситуации. Подобные замеры называют бенчмарком (benchmark). Они производятся для изучения того, насколько хорошо движок проделывает свою работу по управлению сценой. В ситуации когда движок должен обрабатывать и рендерить множество различных объектов, нередки случаи "проседания" показателя fps. Когда движок обрабатывает и рендерит малое количество данных, fps, как правило, повышается. Таким образом имеет смысл изучить специальные техники, позволяющие минимизировать объём данных, которые движок будет обрабатывать и рендерить в каждом кадре.

Закрыть
noteОбрати внимание

Вообще одно лишь измерение частоты кадров (фреймрейта, fps) считается технически неточным методом. Причиной этого является тот факт, что падение фреймрейта со 100 до 90 fps это совсем не одно и то же что падение с 40 до 30 fps. В этом случае лучше взять процентное соотношение падения. В этом случае падение фреймрейта со 100 до 90 fps образует снижение производительности в 10%, в то время как падение фреймрейта с 40 до 30 fps составит снижение производительности в 25%, что гораздо хуже.

Одним из самых распространённых методов увеличить производительность работы видеокарты является т.н. отсечение (culling). Иногда эту технику называют удалением скрытых поверхностей (hidden surface removal). Отсечение является общим термином, означающим фильтрацию граней, которые не требуется рендерить в данном кадре. Это означает, что любая поверхность игровой сцены которая не подлежит рендерингу в данном кадре, не должна отправляться на конвейер Direct 3D. Это совсем не означает, что данные грани не существуют или удалены из сцены. Это просто означает, что движок не отправит их в DirectX-конвейер для последующего рендеринга. Вопрос лишь в том, как определить какие из граней должны быть отсечены?

Рис.1 Соотношение между аккуратностью отсечения невидимых граней и производительностью
Рис.1 Соотношение между аккуратностью отсечения невидимых граней и производительностью

Существует несколько общих методов, которые мы можем применить для выполнения отсечения. Одни из них простые, другие - сложные. Наиболее эффективным решением, как правило, является комбинирование двух или более методов для достижения наиболее аккуратного отсечения. Причиной этого является тот факт, что каждый метод имеет свои сильные и слабые стороны. Одни методы быстры и нетребовательны к ресурсам компьютера, но как правило неаккуратны. Другие - наоборот, работают медленнее, но более точны. Чаще всего внедряют быстрый и грубый метод отсечения для отсечения большей части невидимых граней (т.е. граней, которые не могут быть видимы игроком в данном кадре). Затем в дело вступает более медленный, но аккуратный метод, который дополнительно удаляет грани, которые не были удалены быстрым методом.
Разработка эффективного алгоритма отсечения невидимых граней являет собой некий компромисс, сбалансированное решение. В современном компьютере есть как минимум 2 основных вычислительных модуля: центральный процессор (CPU) и графический чип видеокарты (GPU). При этом они не должны простаивать на протяжении всего процесса работы игрового приложения. В то же время не следует перегружать какой-либо из них, чтобы не создавать эффекта "бутылочного горла" (bottleneck). Чем больше методов отсечения применяется в данном приложении, тем большая нагрузка идёт на CPU. С другой стороны, чем меньше методов отсечения применяется, тем большая нагрузка идёт на GPU (см. Рис.1). На Рис.1 можно видеть, что чем больше алгоритмов отсечения мы применяем, тем выше производительность. Это справдливо, пока кривая на графике не достигнет точки максимума. После этого производительность начнёт снижаться. Это происходит от того, что CPU образует эффект "бутылочного горла" в тех случаях, когда объём вычислений алгоритмов отсечения достигнет определённого предела вычислительных возможностей процессора. Также на этом графике видно, что чем больше алгоритмов отсечения ты применяешь, тем меньший прирост производительности это даёт. Суть в том, чтобы найти идеальный баланс между объёмом вычислений отсечения, который выполняет CPU, и объёмом геометрии, которую рендерит GPU. Ну и объёмом работы, которую необходимо проделать для достижения удовлетворительных результатов, конечно же.
Как мы до этого упомянули, сегодня в игрокодинге существует несколько общепринятых методов отсечения. Вот самые популярные из них:

Метод отсечения Достоинства Недостатки
Удаление граней, на невидимой наблюдателю стороне объектов (Back Face Culling) DirectX выполняет это автоматически. Достаточно только включить его в настройках. Практически нет. Прирост производительности с лихвой окупает включение этого метода отсечения в графический конвейер.
Усечёная пирамида (Frustum) Относительно легко реализовать. Может быть достаточно нетребовательным к ресурсам компьютера. Откровенно неаккуратен. Многие грани, оказавшиеся слишком близко к наблюдателю (перед т.н. Far Plane) будут отрендерены.
Отсечение скрытых поверхностей (Occlusion Culling) Отлично подходит для удаления поверхностей в поле зрения игрока, заслонённых чем-либо. Может значительно нагружать CPU в сложных сценах.

Для нашей системы отсечения мы будем использовать все 3 метода, представленных выше. Мы уже говорили об отсечении граней со стороны, противоположной направлению взгляда наблюдателя (Back Face Culling) в Главе 1.5. К счастью в DirectX этот метод встроен по умолчанию и для того, чтобы его применить, достаточно просто активировать его. Более того, по умолчанию он всегда включен.
Оставшиеся два метода пока нам незнакомы. Поэтому рассмотрим их более подробно.

Отсечение методом усечёной пирамиды (Frustum Culling)

В предыдущей Главе мы говорили о матрицах вида и проекции. Мы знаем, что матрица вида (view matrix) определяет виртуальную камеру, используемую для просмотра игровой сцены. А матрица проекции (projection matrix) действует подобно линзам этой камеры, контролируя проекцию 3D-сцены на плоский экран монитора. При комбинировании этих двух матриц (читай, перемножении) образуется новая матрица, контролирующая т.н. поле видимости (Field of View, FOV). FOV просто определяет, что именно будет видно в виртуальной камере вида. Для лучшего понимания данного понятия лучше всего обратиться к полю зрения твоих глаз. В то время как твоя голова и глаза остаются неподвижными, смотри прямо перед собой, вытяни свою правую руку перед собой, а затем отведи в сторону так, чтобы ты не мог её видеть даже периферийным зрением. Это означает, что твоя рука при этом находится за пределами твоего поля видимости (FOV). Если ты вернёшь руку и она вновь окажется вытянутой перед твоим лицом, то таким образом она вернётся в твоё поле видимости и ты вновь будешь видеть её.

Рис.2 Усечённая пирамида видимого пространства (View Frustum)
Рис.2 Усечённая пирамида видимого пространства (View Frustum)
Рис.3 Верхняя и фронтальная (передняя) стороны усечённой пирамиды вида, образованные пересечением бесконечно продолжающихся плоскостей
Рис.3 Верхняя и фронтальная (передняя) стороны усечённой пирамиды вида, образованные пересечением бесконечно продолжающихся плоскостей
Рис.4 Сцена частично перекрыта объектами на ней
Рис.4 Сцена частично перекрыта объектами на ней
Рис.5 Использование усечённых пирамид (frustum) для отсечения на основе перекрытия (occlusion culling)
Рис.5 Использование усечённых пирамид (frustum) для отсечения на основе перекрытия (occlusion culling)
Рис.6 Эффективность методов отсечения, выбранных нами
Рис.6 Эффективность методов отсечения, выбранных нами
Рис.7 Отсечение групп граней вместо отдельных граней
Рис.7 Отсечение групп граней вместо отдельных граней
Рис.8 Сцена, разделённая методом дерева октантов (octree)
Рис.8 Сцена, разделённая методом дерева октантов (octree)

Тот же самый принцип мы будем использовать для отсечения граней, который не входят в поле видимости виртуальной камеры вьюера (camera's FOV). Для этого мы создадим т.н. усечённую пирамиду видимого пространства(external link) (view frustum), образованную из матрицы поля видимости камеры (camera's FOV matrix). Ты можешь представить себе усечённую пирамиду в виде обычной пирамиды, чья центральная вершина (apex) расположена близко перед камерой (но не касается её "линз"), а основание удалено в направлении, совпадающем с направлением камеры. (См. Рис.2).
Исходный код реализации усечённой пирамиды вида мы рассмотрим чуть позднее в данной Главе. А сейчас рассмотрим как именно усечённая пирамида вида применяется для отсечения невидимых граней. Как только усечённая пирамида вида вычислена, мы можем определить т.н. набор плоскостей (set of planes). Плоскость (plane, реализованная в библиотеке D3DX в виде структуры D3DXPLANE) представляет собой плоскую двухмерную поверхность (surface), которая неограниченно простирается в 3D-пространстве. Она (условно) не имеет толщины и границ. У плоскости 2 стороны (иногда их называют позитивная (лицевая) сторона и негативная (изнанка)). И любая вершина в 3D-пространстве расположена либо на данной плоскости, либо по обе стороны от неё. Наша усечённая пирамида вида может быть определена шестью такими плоскостями (в то же время ты можешь обойтись лишь пятью, если проигнорируешь ближнюю плоскость, что мы и сделаем в рамках данного курса).
Плоскости не заключают в себе какой-либо конкретной формы, т.к. они бесконечно продолжаются вдоль своих осей. Форма усечённой пирамиды образуется только при пересечении этих плоскостей друг с другом, когда они таким образом создают усечённую пирамиду в 3D-пространстве (См. Рис.3).
Теперь, когда ты понял как работает отсечение на основе усечённой пирамиды вида, у тебя не должно возникнуть затруднений при рассмотрении принципа работы отсечения на основе перекрытия.

Отсечение на основе перекрытия (Occlusion Culling)

  • грубо говоря, означает отсечение фрагментов сцены, которые спрятаны за т.н. оклюдерами (от англ. occluder - закрывающий объект, укрытие).

Так что же собой представляет оклюдер? В качестве оклюдера может выступать любой объект, который обладает возможностью скрывать части сцены от глаз игрока. Типичный пример - большое здание или твёрдая стена. Если игрок видит сцену и большая твёрдая стена заслоняет приличную часть игровой сцены, то имеет смысл отсечь всё, что находится за этой стеной (См. Рис.4).
Но как же определить, что тот или иной объект спрятан за стеной? Здесь применяется тот же принцип, что и при отсечении с помощью усечённой пирамиды видимости (view frustum). В этом случае достаточно лишь создать усечённую пирамиду, продолжив линии от оклюдера, направленные от наблюдателя. Теперь, вместо того, чтобы отсечь все объекты, расположенные за пределами этих усечённых пирамид, мы наоборот, отсекаем всё, что находится внутри них (См.Рис.5).

Вооружившись тремя вышеперечисленными методами отсечения, мы можем отсечь (cull) значительную часть игровой сцены и предотвратить отправку на обработку в конвейер DirectX множества невидимых граней. Учти, что данная комбинация далеко не идеальна. Даже при её использовании тем не менее остаются некоторые грани, которые рендерятся в каждом кадре, хотя в них нет необходимости. В любом случае мы не задаёмся целью создать идеальную систему отсечения невидимых граней. Нам лишь необходимо придерживаться некоего баланса, дабы не создавать в процессоре эффекта "бутылочного горлышка", связанного с чрезмерными расчётами алгоритмов отсечения. На Рис.6 представлена диаграмма, отображающая степень "отдачи" от использования каждого из методов отсечения. Как видим, чем больше применяем различных методов отсечения, тем меньше эффекта получаем от этого.
Эффективность наших методов отсечения также сильно зависит от наборов данных, которые мы отправляем на расчёт. Другими словами от того, какая из систем данных подвергается отсечению (отдельные грани, группы граней либо целые объекты). Пока мы этого не касались, но обязательно рассмотрим данную тему чуть позднее в данной Главе.

Рендеринг сцены

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

  • Как организована геометрия сцены (наборы данных).
  • Как именно мы планируем ренедерить видимые части сцены после выполнения отсечения.

Организация геометрии сцены (наборы данных)

Наша сцена заключает в себе огромное количество статичной геометрии. Например, в нашей сцене может быть здание, некоторая мебель в нём, припаркованный автомобиль, несколько деревьев, и собственно сама земная поверхность, на которой всё это размещено. Несмотря на то, что по идее это всё отдельные объекты, все вместе они составляют единую геометрию нашей игровой сцены. Игровые сцены, как правило, создаются в пакетах для 3D-моделирования (3D modeling package) и сохраняются как один большой меш-файл, который затем экспортируется в .x формат. Затем данный меш-файл достаточно загрузить средствами движка и мы получим доступ ко всей статичной геометрии сцены разом. Проблема здесь кроется в том, что вся геометрия сцены в этом случае будет сохранена в один большой вершинный буфер (vertex buffer), с ещё одним большим буфером индексов (index buffer) для более быстрого доступа. В результате образуется то, что на профессиональном жаргоне называют "полигональный суп" (polygon soup). Проще говоря, все грани нашей сцены будут при этом перемешаны без разбора и иерархии. Не смотря на это, мы всё же сможем отрендерить их благодаря буферу индексов. Но как же мы теперь произведём отсечение в этом большом полигональном супе?
Ответ прост - мы не будем этого делать. Единственный способ осуществить отсечение в чём либо похожим на эту кучу-малу - это проверять каждую грань на видимость в каждом кадре, что для нас абсолютно неприемлемо. Конечно, это даст великолепные результаты, но нагрузка на CPU для расчёта столь аккуратного отсечения будет несоразмерной. Так вот, для снижения нагрузки на CPU, вместо того, чтобы проверять на видимость каждую грань по отдельности, мы объединим их в группы и будем проверять на видимость уже сами группы. Может это будет не так аккуратно, зато куда практичнее. Допустим у нас есть такая группа, насчитывающая десятки граней. Если половина данной группы будет определена как видимая, а другая - нет, то вся группа считается видимой и отправляется на рендеринг. Снижение производительности GPU при рендеринге нескольких лишних граней совсем не значительно по сравнению с нагрузкой на CPU в случае аккуратного расчёта их отсечения.
Объединив грани в логические группы, мы также можем обрисовать некоторую фигуру вокруг каждой из них, т.е. заключить их в ограничивающий объём (bounding volume). После этого нам достаточно лишь проверить каждый из ограничивающих объёмов на видимость, вместо того, чтобы проверять отдельные 3D-фигуры и грани, и выполнить отсечение тех ограничивающих объёмов, которые не видны в данном кадре. Снижение аккуратности расчётов отсечения в этом случае будет совсем не значительным по сравнению с выигрышем в производительности, полученным при выполнении отсечения данным способом. Причина этого вполне очевидна. Ведь нам достаточно проверить на видимость простые боксы или сферы, сопоставив их позицию с позицией усечённой пирамиды вида (view frustum) и усечённых пирамид перекрывающих объектов (occlusion frustums), вместо того, чтобы проводить аналогичные проверки со сложными 3D-фигурами, созданными из плотно прилегающих друг к другу граней (см. Рис.7).
Остаётся решить всего один вопрос: по какому принципу объединять грани в группы? Здесь мы применим т.н. дерево октантов (октодерево, octree(external link)). Данный термин более подробно мы рассмотрим чуть ниже, в данной Главе, непосредственно при разработке системы управления сценой. В общих чертах дерево октантов можно мысленно представить в виде обычного дерева, перевёрнутого вверх ногами либо как корневую систему дерева.
На первом уровне вся сцена заключена в один большой ограничивающий объём, который, в свою очередь, делится на 8 других, одинаковых по размеру, ограничивающих объёмов (отсюда и название, т.к. "octo" в переводе с латыни "восемь"). Каждый из этих восьми ограничивающих объёмов снова делится на 8 ещё более малых, но также равных по размеру, ограничивающих объёма. Как только дерево октантов создано, каждая грань назначается определённому ограничивающему объёму, в котором она заключена (иногда особо крупные грани заключаются сразу в два ограничивающих объёма). Данный процесс длится определённое количество времени, которое обычно зависит от "глубины" вложенности корневой системы дерева октантов, размера ограничивающих объёмов а также числа граней, заключённых в каждом из них. По завершении мы получаем готовую иерархию ограничивающих объёмов (точно такая же иерархия используется в .X файлах), группирующую все грани игровой сцены. Теперь остаётся лишь трассировать (traversing) эту иерархию в каждом кадре (точно так же, как мы трассируем иерархию фреймов .X-файла) и отсечь невидимые группы. Преимущество такого подхода заключается в том, что если один ограничивающий объём определён как спрятанный (невидимый), то остальные ограничивающие объёмы, расположенные с ним на одной ветви, но ниже по иерархии, также невидимы. Это означает, что их даже не требуется проверять на видимость (см. Рис.8). Чуть позже мы ещё вернёмся к этой теме при написании её реализации в реальном исходном коде.

Методы рендеринга видимых граней сцены, оставшихся после выполнения отсечения

В Главе 1.10 мы разработали класс RenderCache, единственным назначением которого является рендеринг группы граней. При этом рендерятся только те грани, которые принадлежат к определённому типу материала. На самом деле это так же просто как звучит. Вся наша сцена целиком содержится в одном вершинном буфере (vertex buffer), что в общем-то нас устраивает при условии, что наши сцены не слишком большие по объёму. После этого мы создаём рендер-кэш (render cache) для каждого типа материала, используемого в данной сцене. В каждом кадре мы производим отсечение (culling) невидимых граней сцены, исходя из текущего положения камеры вида (view camera). Когда грань определена как видимая, мы информируем рендер-кэш, которому она принадлежит (основываясь на материале, используемом данной гранью) о том, что её необходимо отрендерить. Это примерно как проинформировать официанта о блюдах, выбранных в меню ресторана. Рендер-кэши отслеживают индексы граней, отправляемые на рендеринг в текущем кадре. Как только было выполнено отсечение невидимых граней сцены мы даём команду рендер-кэшам отправить их буферы индексов в DirectX для рендеринга граней из вершинного буфера сцены. Данный процесс повторяется в каждом кадре.

Всё это звучит дико запутанно. Но к счастью у нас уж есть вся готовая инфраструктура для организации подобных методов. И когда заработает система отсечения невидимых граней, всё встанет на свои места. Описанный выше процесс рендеринга станет намного понятнее чуть ниже, когда мы рассмотрим непосредственную реализацию системы управления сценой. А пока рассмотрим последний важный аспект управления сценой - определение столкновений (collision detection).

Определение столкновений (collision detection)

Если ты хоть раз пытался писать даже самый простой код системы определения столкновений, то наверняка приходил к выводу, что это сама по себе уже целая наука и ошибок здесь можно допустить очень много. Вообще, даже чтобы заставить простые объекты (например боксы и сферы) сталкиваться в 3D-пространстве и корректно реагировать на столкновение, надо изрядно потрудиться. Для нашей типичной игры жанра 3D FPS нам нужно нечто большее, чем простая система определения столкновений. Нам необходима система, которая позволит игрокам плавно передвигаться в 3D-пространстве. Система также должна поддерживать определение столкновений между объектами различных типов, например между игроками и спавнер-объектами.
Тема оч. непростая, а её конечная реализация сложна и запутанна. Её изложение заняло бы ещё как минимум две большие Главы, весьма трудные для понимания (особенно если ты не силён в математике). У нас без сомнения будет система определения столкновений и реакции на них, но мы не будем вдаваться в детали её реализации. Это приводит нас к основной концепции всей индустрии игрокодинга: "Не делай того, в чём нет необходимости" или попросту не изобретай велосипед.
Реалии современной действительности таковы, что ты не можешь заниматься всем на свете. Немногие люди способны одновременно быть блестящими артистами, профессиональными программерами и гуру-дизайнерами. Возьмём, к примеру, программирование. Чаще всего они являются узкими специалистами в 1-2 темах (например программирование звука, поддержки сети или искусственного интеллекта). Они специализируются лишь в той области, которая им действительно интересна. Ты тоже наверняка специализируешься (либо будешь специализироваться) в той области, которая тебе интересна. Допустим, ты решил специализироваться на программировании сетевой поддержки в приложениях и уже разработал великолепную систему поддержки сети для своей будущей игры. А теперь представь, что тебе также понадобится профессиональная система поддержки звука, к примеру. В этом случае ты, конечно, будешь несколько растерян. Ты можешь потратить ещё несколько месяцев на разработку системы поддержки звука, которая лишь наполовину функциональна по сравнению с твоими ожиданиями, либо обратишься к специалисту саунд-программинга. Ты можешь вовсе найти готовую недорогую (либо вовсе бесплатную) систему поддержки звука, которая соответствует твоим требованиям, и просто использовать её в своей игре, соблюдая все необходимые лицензионные процедуры.
С широким распространением Интернета появилась возможность найти ответ практически на любой вопрос. Ты можешь без труда найти множество бесплатных ресурсов для своих проектов. Примечательно, что бесплатные ресурсы, конечно, не годятся для профессиональных коммерческих проектов, но для небольших начинаний это отличное подспорье. Всякий раз начиная новый проект, необходимо тщательно обдумать, что для него потребуется. Затем реши, что ты сможешь сделать самостоятельно и сколько времени для этого понадобится. Для всего остального, что ты не можешь делать сам, ищи альтернативные решения. И они почти всегда есть. При использовании в своих проектах ресурсов от сторонних разработчиков, принято указывать ссылку на его создателя или правообладателя (указывать т.н. credits). При создании коммерческих проектов необходимо получить письменное разрешение на используемые в них ресурсы от сторонних разработчиков. Так к чему все эти рассуждения об использовании чужих наработок?
Для нашей системы определения столкновений (collision detection system), которая будет интегрирована в систему управления игровой сценой (scene management system) мы будем использовать алгоритм, представленный в статье "Улучшенное определение столкновений и реакция на них" ("Improved Collision Detection and Response"(external link)), написанной Каспером Фоерби (Kasper Fauerby). Рекомендуется к прочтению. Представленный в ней алгоритм сложен, поэтому мы не рассматриваем его в данном курсе. Вместо этого мы возьмём готовый рабочий код модифицированной версии его алгоритма, специально написанного для нашего движка и потому прекрасно подходящий к нашей системе управления сценой.
Алгоритм разработан специально для того, чтобы позволить любому апроксимированному (т.е. заключённому в ограничивающий объём) 3D-мешу плавно перемещаться в 3D-пространстве. В самом деле, крайне сложно заставить 3D-персонажа гулять в 3D-окружении, обеспечив при этом отличное определение столкновений. А всё из-за того, что типичный персонаж в игре состоит из нескольких сотен полигонов. Для упрощения определения столкновений мы просто размещаем фигуру персонажа внутри ограничивающего объёма и затем уже ограничивающий объём проверяем на столкновения. Это позволяет фигуре персонажа перемещаться в 3D-пространстве с плавным и почти прозрачным для игрока определением столкновений, обеспечивая таким образом полную имитацию законов физики реального мира.

Рис.9 Эллипс, бокс и сфера в качестве ограничивающих объёмов
Рис.9 Эллипс, бокс и сфера в качестве ограничивающих объёмов

У нас уже есть класс BoundingVolume, который используется для создания вокруг игровых объектов ограничивающих объёмов. Кроме того выбранный нами алгоритм определения столкновений работает с применением именно эллипсов, которые также поддерживаются классом BoundingVolume. Причиной этого является тот факт, что эллипсы гораздо лучше подходят для заключения внутри себя комплексных мешей, чем другие виды ограничивающих объёмов (бокс и сфера). Возьмём, к примеру, персонаж в виде человека, который стоит вертикально. Сфера, вытянутая вдоль оси Y (что, собственно, и делает её эллипсом) лучше всего подходит для размещения внутри него фигуры человека (см. Рис.9). Обрати внимание, что эллипс заключает в себе наименьший объём неиспользуемого пространства между своей границей и объектом, который в него заключён.

Создаём CollisionDetection.h (Проект Engine)

ОК, приступаем.

  • Стартуй MSVC++ 2010 и открывай Решение GameProject01 (если не сделал это раньше).
  • В "Обозревателе решений" главного окна MSVC++2010 щёлкни правой кнопкой мыши по папке (в терминологии Майкрософт это не папки, а фильтры!) "Заголовочные файлы" (Header Files) Проекта Engine.
  • Во всплывающем меню Добавить->Создать элемент...
  • В появившемся окне выбери "Заголовочный файл (.h)" и в поле "Имя" введи "CollisionDetection.h".
  • Жмём "Добавить".

Добавленный файл сразу откроется в правой части MSVC++2010.

  • В только что созданном и открытом файле CollisionDetection.h набираем следующий код:

CollisionDetection.h (Проект Engine)
//-----------------------------------------------------------------------------
// Обеспечивает базовое определение столкновений в 3D-пространстве, включающем в себя как
// статичную геометрию, так и динамические объекты.
//
// Note: В данном файле использована адаптированная версия алгоритма из статьи "Improved Collision
//       Detection and Response" автора Kasper Fauerby.
//
// Original SourceCode:
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#ifndef COLLISION_H
#define COLLISION_H

//-----------------------------------------------------------------------------
// Collision Data Structure
//-----------------------------------------------------------------------------
struct CollisionData
{
	float scale; // Масштаб, используемый при вызове менеджера сцены (scene manager).
	float elapsed; // Затраченное время на текущий кадр.
	unsigned long frameStamp; // Текущий штамп кадра (frame stamp) согласно менеджеру сцены.

	SceneObject *object; // Указатель на объект, с которым будет выполняться определение столкновения.

	D3DXVECTOR3 translation; // Трансляция в пространство эллипса.
	D3DXVECTOR3 velocity; // Скорость в пространстве эллипса.
	D3DXVECTOR3 normalizedVelocity; // Нормализованная скорость в пространстве эллипса.

	D3DXVECTOR3 gravity; // Вектор гравитации (Gravity vector), который будет сконвертирован в пространство эллипса.

	bool collisionFound; // Сигнализирует, когда обнаружено столкновение.
	float distance; // Расстояние до точки столкновения.
	D3DXVECTOR3 intersection; // Текущая точка пересечения, где произошло столкновение.
};

//-----------------------------------------------------------------------------
// Возвращает наименьший корень квадратного уравнения.
//-----------------------------------------------------------------------------
inline float GetLowestRoot( float a, float b, float c, float max )
{
	// Вычисляем детерминант, затем извлекаем его квадратный корень (если он не меньше ноля).
	float determinant = b * b - a * c;
	if( determinant < 0.0f )
		return 0.0f;
	determinant = (float)sqrt( determinant );

	// Вычисляем первый корень и проверяем, что он находится в нужном интервале.
	float root1 = ( b + determinant ) / a;
	if( root1 <= 0.0f || root1 > max )
		root1 = max + 1.0f;

	// Вычисляем второй корень и проверяем, что он находится в нужном интервале.
	float root2 = ( b - determinant ) / a;
	if( root2 <= 0.0f || root2 > max )
		root2 = max + 1.0f;

	// Определяем минимальный из двух корней.
	float root = min( root1, root2 );

	// Проверяем корень на валидность.
	if( root == max + 1.0f )
		return 0.0f;

	return root;
}

//-----------------------------------------------------------------------------
// Проверяем отдельную грань на пересечение.
//-----------------------------------------------------------------------------
inline void CheckFace( CollisionData *data, D3DXVECTOR3 vertex0, D3DXVECTOR3 vertex1, D3DXVECTOR3 vertex2 )
{
	// Создаём плоскость из вершин грани.
	D3DXPLANE plane;
	D3DXPlaneFromPoints( &plane, &vertex0, &vertex1, &vertex2 );

	// Получаем угол между нормалью плоскости и вектора скорости.
	float angle = D3DXPlaneDotNormal( &plane, &data->normalizedVelocity );

	// Проверяем, что плоскость обращена к вектору скорости (т.е. игнорируем обратные поверхности грани).
	if( angle > 0.0f )
		return;

	// Получаем вектор нормали плоскости.
	D3DXVECTOR3 planeNormal;
	D3DXVec3Cross( &planeNormal, &( vertex0 - vertex1 ), &( vertex1 - vertex2 ) );
	D3DXVec3Normalize( &planeNormal, &planeNormal );

	// Вычисляем расстояние от трансляции сферы до плоскости.
	float signedPlaneDistance = D3DXVec3Dot( &data->translation, &planeNormal ) + plane.d;

	// Получаем интервал пересечения с плоскостью.
	float time0, time1;
	bool embedded = false;

	// Кэшируем это т.к. мы собираемся использвать эти данные несколько раз (см. ниже)
	float normalDotVelocity = D3DXVec3Dot( &planeNormal, &data->velocity );

	// Проверяем, путешествует ли сфера параллельно плоскости.
	if( normalDotVelocity == 0.0f )
	{
		// Если сфера не имеет с плоскостью общих точек, то они не могут столкнуться.
		if( fabs( signedPlaneDistance ) >= 1.0f )
			return;
		else
		{
			// Сфера пересекает плоскость, значит они столкнулись
			// в текущем временном фрейме (time frame).
			embedded = true;
			time0 = 0.0f;
			time1 = 1.0f;
		}
	}
	else
	{
		// Вычисляем временной фрейм (time frame) пересечения.
		time0 = ( -1.0f - signedPlaneDistance ) / normalDotVelocity;
		time1 = ( 1.0f - signedPlaneDistance ) / normalDotVelocity;

		// Проверяем, что переменная time0 меньше чем переменная time1.
		if( time0 > time1 )
		{
			float swap = time1;
			time1 = time0;
			time0 = swap;
		}

		// Если временной фрейм (time frame) пересечения выходит за пределы допустимого интервала, то сфера и плоскость не могут столкнуться.
		if( time0 > 1.0f || time1 < 0.0f )
			return;

		// Нормализуем временной фрейм (time frame).
		if( time0 < 0.0f ) time0 = 0.0f;
		if( time1 < 0.0f ) time1 = 0.0f;
		if( time0 > 1.0f ) time0 = 1.0f;
		if( time1 > 1.0f ) time1 = 1.0f;
	}

	// Переменные используются для отслеживания случаев пересечения. В них отражены место и время пересечения.
	bool intersectFound = false;
	D3DXVECTOR3 intersection;
	float intersectTime = 1.0f;

	// Проверяем, не пересекает ли сфера плоскость.
	if( embedded == false )
	{
		// Получаем точку пересечения с плоскостью в момент времени time0.
		D3DXVECTOR3 planeIntersectionPoint = ( data->translation - planeNormal ) + data->velocity * time0;

		// Получаем векторы двух рёбер грани.
		D3DXVECTOR3 edge0 = vertex1 - vertex0;
		D3DXVECTOR3 edge1 = vertex2 - vertex0;

		// Получаем углы рёбер и комбинируем их.
		float angle0 = D3DXVec3Dot( &edge0, &edge0 );
		float angle1 = D3DXVec3Dot( &edge0, &edge1 );
		float angle2 = D3DXVec3Dot( &edge1, &edge1 );
		float combined = ( angle0 * angle2 ) - ( angle1 * angle1 );

		// Получаем углы разбиения (split angles) между двумя рёбрами.
		D3DXVECTOR3 split = planeIntersectionPoint - vertex0;
		float splitAngle0 = D3DXVec3Dot( &split, &edge0 );
		float splitAngle1 = D3DXVec3Dot( &split, &edge1 );

		float x = ( splitAngle0 * angle2 ) - ( splitAngle1 * angle1 );
		float y = ( splitAngle1 * angle0 ) - ( splitAngle0 * angle1 );
		float z = x + y - combined;

		// Берём двоичное AND (И) оси z и complement включительное ИЛИ осей x и y,
		// затем двоичное AND (И) приводим к результату 0x80000000 и возвращаем его. Двоичный результат
		// равный нулю представляет собой булево значение false, в то время как любое другое значение
		// соответствует булеву значению true.
		if( ( ( (unsigned int&)z & ~( (unsigned int&)x | (unsigned int&)y ) ) & 0x80000000 ) != 0 )
		{
			intersectFound = true;
			intersection = planeIntersectionPoint;
			intersectTime = time0;
		}
	}

	// Проверяем, когда столкновение не обнаружено.
	if( intersectFound == false )
	{
		// Получаем квадрат длины вектора скорости.
		float squaredVelocityLength = D3DXVec3LengthSq( &data->velocity );

		// Квадратное уравнение должно быть решено для каждой вершины и ребра грани.
		// Следующие переменные используются для построения квадратного уравнения.
		float a, b, c;

		// Используется для сохранения результата каждого квадратного уравнения.
		float newTime;

		// Сперва посчитаем для вершин.
		a = squaredVelocityLength;

		// Проверяем вершину 0.
		b = 2.0f * D3DXVec3Dot( &data->velocity, &( data->translation - vertex0 ) );
		c = D3DXVec3LengthSq( &( vertex0 - data->translation ) ) - 1.0f;
		if( newTime = GetLowestRoot( a, b, c, intersectTime ) > 0.0f )
		{
			intersectFound = true;
			intersection = vertex0;
			intersectTime = newTime;
		}

		// Проверяем вершину 1.
		b = 2.0f * D3DXVec3Dot( &data->velocity, &( data->translation - vertex1 ) );
		c = D3DXVec3LengthSq( &( vertex1 - data->translation ) ) - 1.0f;
		if( newTime = GetLowestRoot( a, b, c, intersectTime ) > 0.0f )
		{
			intersectFound = true;
			intersection = vertex1;
			intersectTime = newTime;
		}

		// Проверяем вершину 2.
		b = 2.0f * D3DXVec3Dot( &data->velocity, &( data->translation - vertex2 ) );
		c = D3DXVec3LengthSq( &( vertex2 - data->translation ) ) - 1.0f;
		if( newTime = GetLowestRoot( a, b, c, intersectTime ) > 0.0f )
		{
			intersectFound = true;
			intersection = vertex2;
			intersectTime = newTime;
		}

		// Проверяем ребро от вершины vertex0 до вершины vertex1.
		D3DXVECTOR3 edge = vertex1 - vertex0;
		D3DXVECTOR3 vectorSphereVertex = vertex0 - data->translation;
		float squaredEdgeLength = D3DXVec3LengthSq( &edge );
		float angleEdgeVelocity = D3DXVec3Dot( &edge, &data->velocity );
		float angleEdgeSphereVertex = D3DXVec3Dot( &edge, &vectorSphereVertex );

		// Получаем параметры для квадратного уравнения.
		a = squaredEdgeLength * -squaredVelocityLength + angleEdgeVelocity * angleEdgeVelocity;
		b = squaredEdgeLength * ( 2.0f * D3DXVec3Dot( &data->velocity, &vectorSphereVertex ) ) - 2.0f * angleEdgeVelocity * angleEdgeSphereVertex;
		c = squaredEdgeLength * ( 1.0f - D3DXVec3LengthSq( &vectorSphereVertex ) ) + angleEdgeSphereVertex * angleEdgeSphereVertex;

		// Проверяем, пересекает ли сфера ребро.
		if( newTime = GetLowestRoot( a, b, c, intersectTime ) > 0.0f )
		{
			// Проверяем, что пересечение произошло в пределах границ граней.
			float point = ( angleEdgeVelocity * newTime - angleEdgeSphereVertex ) / squaredEdgeLength;
			if( point >= 0.0f && point <= 1.0f )
			{
				intersectFound = true;
				intersection = vertex0 + edge * point;
				intersectTime = newTime;
			}
		}

		// Проверяем ребор от вершины vertex1 до вершины vertex2.
		edge = vertex2 - vertex1;
		vectorSphereVertex = vertex1 - data->translation;
		squaredEdgeLength = D3DXVec3LengthSq( &edge );
		angleEdgeVelocity = D3DXVec3Dot( &edge, &data->velocity );
		angleEdgeSphereVertex = D3DXVec3Dot( &edge, &vectorSphereVertex );

		// Получаем параметры для квадратного уравнения.
		a = squaredEdgeLength * -squaredVelocityLength + angleEdgeVelocity * angleEdgeVelocity;
		b = squaredEdgeLength * ( 2.0f * D3DXVec3Dot( &data->velocity, &vectorSphereVertex ) ) - 2.0f * angleEdgeVelocity * angleEdgeSphereVertex;
		c = squaredEdgeLength * ( 1.0f - D3DXVec3LengthSq( &vectorSphereVertex ) ) + angleEdgeSphereVertex * angleEdgeSphereVertex;

		// Проверяем, пересекает ли сфера ребро.
		if( newTime = GetLowestRoot( a, b, c, intersectTime ) > 0.0f )
		{
			// Проверяем, что пересечение произошло в пределах границ граней.
			float point = ( angleEdgeVelocity * newTime - angleEdgeSphereVertex ) / squaredEdgeLength;
			if( point >= 0.0f && point <= 1.0f )
			{
				intersectFound = true;
				intersection = vertex1 + edge * point;
				intersectTime = newTime;
			}
		}

		// Проверяем ребро от вершины vertex2 до вершины vertex0.
		edge = vertex0 - vertex2;
		vectorSphereVertex = vertex2 - data->translation;
		squaredEdgeLength = D3DXVec3LengthSq( &edge );
		angleEdgeVelocity = D3DXVec3Dot( &edge, &data->velocity );
		angleEdgeSphereVertex = D3DXVec3Dot( &edge, &vectorSphereVertex );

		// Получаем параметры для квадратного уравнения.
		a = squaredEdgeLength * -squaredVelocityLength + angleEdgeVelocity * angleEdgeVelocity;
		b = squaredEdgeLength * ( 2.0f * D3DXVec3Dot( &data->velocity, &vectorSphereVertex ) ) - 2.0f * angleEdgeVelocity * angleEdgeSphereVertex;
		c = squaredEdgeLength * ( 1.0f - D3DXVec3LengthSq( &vectorSphereVertex ) ) + angleEdgeSphereVertex * angleEdgeSphereVertex;

		// Проверяем, пересекает ли сфера ребро.
		if( newTime = GetLowestRoot( a, b, c, intersectTime ) > 0.0f )
		{
			// Проверяем, что пересечение произошло в пределах границ граней.
			float point = ( angleEdgeVelocity * newTime - angleEdgeSphereVertex ) / squaredEdgeLength;
			if( point >= 0.0f && point <= 1.0f )
			{
				intersectFound = true;
				intersection = vertex2 + edge * point;
				intersectTime = newTime;
			}
		}
	}

	// Проверяем случай, когда столкновение произошло.
	if( intersectFound == true )
	{
		// Получаем расстояние до столкновения (т.е. время по вектору скорости).
		float collisionDistance = intersectTime * D3DXVec3Length( &data->velocity );

		// Сохраняем данные столкновения, при необходимости.
		if( data->collisionFound == false || collisionDistance < data->distance )
		{
			data->distance = collisionDistance;
			data->intersection = intersection;
			data->collisionFound = true;
		}
	}
}

//-----------------------------------------------------------------------------
// Выполняем определение столкновений между данным объектом и сценой.
//-----------------------------------------------------------------------------
inline void CollideWithScene( CollisionData *data, Vertex *vertices, SceneFace *faces, unsigned long totalFaces, LinkedList< SceneObject > *objects, unsigned long recursion = 5 )
{
	// Вычисляем минимальное расстояние (epsilon distance), с учётом масштаба.
	// Минимальным расстоянием (epsilon distance) считается настолько малое расстояние, которым в расчётах можно пренебречь.
	float epsilon = 0.5f * data->scale;

	// Указываем, что столкновение не обнаружено.
	data->collisionFound = false;

	// Получаем нормализованный вектор скорости.
	D3DXVec3Normalize( &data->normalizedVelocity, &data->velocity );

	// Проходим через все грани.
	D3DXVECTOR3 vertex0, vertex1, vertex2;
	for( unsigned long f = 0; f < totalFaces; f++ )
	{
		// Пропускаем эту грань, если в материале установлен флаг игнорировать лучи (IgnoreRay).
		if( faces[f].renderCache->GetMaterial()->GetIgnoreRay() == true )
			continue;

		// Получаем копию вершин данной грани в пространстве эллипса.
		vertex0.x = vertices[faces[f].vertex0].translation.x / data->object->GetEllipsoidRadius().x;
		vertex0.y = vertices[faces[f].vertex0].translation.y / data->object->GetEllipsoidRadius().y;
		vertex0.z = vertices[faces[f].vertex0].translation.z / data->object->GetEllipsoidRadius().z;
		vertex1.x = vertices[faces[f].vertex1].translation.x / data->object->GetEllipsoidRadius().x;
		vertex1.y = vertices[faces[f].vertex1].translation.y / data->object->GetEllipsoidRadius().y;
		vertex1.z = vertices[faces[f].vertex1].translation.z / data->object->GetEllipsoidRadius().z;
		vertex2.x = vertices[faces[f].vertex2].translation.x / data->object->GetEllipsoidRadius().x;
		vertex2.y = vertices[faces[f].vertex2].translation.y / data->object->GetEllipsoidRadius().y;
		vertex2.z = vertices[faces[f].vertex2].translation.z / data->object->GetEllipsoidRadius().z;

		// Проверяем на столкновение с данной гранью.
		CheckFace( data, vertex0, vertex1, vertex2 );
	}

	// Создаём список столкновений с объектами-призраками (ghost objects) и список расстояний до них.
	LinkedList< SceneObject > *ghostHits = new LinkedList< SceneObject >;
	LinkedList< float > *ghostDistances = new LinkedList< float >;

	// Данные переменные используются для проверки столкновения текущего объекта.
	D3DXVECTOR3 translation, velocity, vectorColliderObject, vectorObjectCollider, vectorObjectRadius;
	float distToCollision, colliderRadius, objectRadius;

	// Проходим (итерируем) через список объектов.
	SceneObject *hitObject = NULL;
	SceneObject *nextObject = objects->GetFirst();
	while( nextObject != NULL )
	{
		// Пропускаем объект, если он является сталкивающимся объектом (collider). Он не может проверяться сам с собой.
		if( nextObject != data->object )
		{
			// Получаем трансляцию и скорость этого объекта в пространстве эллипса.
			translation.x = nextObject->GetTranslation().x / data->object->GetEllipsoidRadius().x;
			translation.y = nextObject->GetTranslation().y / data->object->GetEllipsoidRadius().y;
			translation.z = nextObject->GetTranslation().z / data->object->GetEllipsoidRadius().z;
			velocity.x = nextObject->GetVelocity().x / data->object->GetEllipsoidRadius().x;
			velocity.y = nextObject->GetVelocity().y / data->object->GetEllipsoidRadius().y;
			velocity.z = nextObject->GetVelocity().z / data->object->GetEllipsoidRadius().z;
			velocity *= data->elapsed;

			// Получаем нормализованные векторы от сталкивающегося объекта (collider) до данного объекта и всё в таком духе.
			D3DXVec3Normalize( &vectorColliderObject, &( translation - data->translation ) );
			D3DXVec3Normalize( &vectorObjectCollider, &( data->translation - translation ) );

			// Вычисляем радиус каждого эллипса в направлении друг к другу.
			colliderRadius = D3DXVec3Length( &vectorColliderObject );
			vectorObjectRadius.x = vectorObjectCollider.x * nextObject->GetEllipsoidRadius().x / data->object->GetEllipsoidRadius().x;
			vectorObjectRadius.y = vectorObjectCollider.y * nextObject->GetEllipsoidRadius().y / data->object->GetEllipsoidRadius().y;
			vectorObjectRadius.z = vectorObjectCollider.z * nextObject->GetEllipsoidRadius().z / data->object->GetEllipsoidRadius().z;
			objectRadius = D3DXVec3Length( &vectorObjectRadius );

			// Проверяем столкновение между двумя сферами.
			if( IsSphereCollidingWithSphere( &distToCollision, data->translation, translation, velocity - data->velocity, colliderRadius + objectRadius ) == true )
			{
				// Проверяем, не является ли объект столкновения объектом-призраком (ghost).
				if( nextObject->GetGhost() == true )
				{
					// Если оба объекта допущены к регистрации столкновений (т.е. не являются призраками), то сохраняем указатель на объект столкновения и расстояние до столкновения.
					if( nextObject->GetIgnoreCollisions() == false && data->object->GetIgnoreCollisions() == false )
					{
						ghostHits->Add( nextObject );
						ghostDistances->Add( &distToCollision );
					}
				}
				else
				{
					// Сохраняем данные столкновения, при необходимости.
					if( data->collisionFound == false || distToCollision < data->distance )
					{
						data->distance = distToCollision;
						data->intersection = data->normalizedVelocity * distToCollision;
						data->collisionFound = true;

						// Сохраняем указатель на объект столкновения.
						hitObject = nextObject;
					}
				}
			}
		}

		// Переходим к следующему объекту.
		nextObject = objects->GetNext( nextObject );
	}

	// Итерируем через список объектов столкновения, являющихся призраками (ghost objects) и расстояния до них.
	ghostHits->Iterate( true );
	ghostDistances->Iterate( true );
	while( ghostHits->Iterate() != NULL && ghostDistances->Iterate() != NULL )
	{
		// Если расстояние до столкновения с объектом-призраком меньше чем расстояние до ближайшего реального столкновения, то регистрируем столкновение с объектом-призраком.
		if( *ghostDistances->GetCurrent() < data->distance )
		{
			// Регистрируем столкновение между двумя объектами.
			ghostHits->GetCurrent()->CollisionOccurred( data->object, data->frameStamp );
			data->object->CollisionOccurred( ghostHits->GetCurrent(), data->frameStamp );
		}
	}

	// Уничтожаем столкновения-призраки (ghost hits) и списки расстояний.
	ghostHits->ClearPointers();
	SAFE_DELETE( ghostHits );
	ghostDistances->ClearPointers();
	SAFE_DELETE( ghostDistances );

	// Если столкновение не произошло, тогда просто перемещаем на полный вектор скорости.
	if( data->collisionFound == false )
	{
		data->translation = data->translation + data->velocity;
		return;
	}

	// Вычисляем конечный пункт (destination) (т.е. точку объекта, в которой предположительно будет столкновение).
	D3DXVECTOR3 destination = data->translation + data->velocity;

	// Новая трансляция будет представлять собой точку, где заканчивается граница объекта.
	D3DXVECTOR3 newTranslation = data->translation;

	// Игнорируем движение, если объект уже очень близок к конечному пункту (destination).
	if( data->distance >= epsilon )
	{
		// Вычисляем новую скорость, необходимую для преодоления расстояния.
		D3DXVECTOR3 newVelocity = data->normalizedVelocity * ( data->distance - epsilon );

		// Находим новую трансляцию.
		newTranslation = data->translation + newVelocity;

		// Тонко настраиваем (adjust) точку пересечения полигонов, учитывая тот факт, что
		// не движется прямо (right up) к рассчитанной точке пересечения.
		D3DXVec3Normalize( &newVelocity, &newVelocity );
		data->intersection = data->intersection - newVelocity * epsilon;
	}

	// Проверяем, если произошло столкновение с объектом.
	if( hitObject != NULL )
	{
		// Устанавливаем новую трансляцию для объекта.
		data->translation = newTranslation;

		// Вычисляем и применяем скороть толчка (push velocity) чтобы объекты могли оттолкнуть друг друга при столкновении.
		D3DXVECTOR3 push = ( hitObject->GetVelocity() + data->object->GetVelocity() ) / 10.0f;
		hitObject->SetVelocity( push );
		data->object->SetVelocity( push );

		// Регистрируем столкновение между обоими объектами, если они могут сталкиваться.
		if( hitObject->GetIgnoreCollisions() == false && data->object->GetIgnoreCollisions() == false )
		{
			hitObject->CollisionOccurred( data->object, data->frameStamp );
			data->object->CollisionOccurred( hitObject, data->frameStamp );
		}

		return;
	}

	// Создаём плоскость, которая будет выполнять роль рассекающей плоскости (sliding plane).
	D3DXVECTOR3 slidePlaneOrigin = data->intersection;
	D3DXVECTOR3 slidePlaneNormal;
	D3DXVec3Normalize( &slidePlaneNormal, &( newTranslation - data->intersection ) );
	D3DXPLANE slidingPlane;
	D3DXPlaneFromPointNormal( &slidingPlane, &slidePlaneOrigin, &slidePlaneNormal );

	// Рассчитываем новую конечную точку, с учётом рассечения (sliding) полоскостью.
	D3DXVECTOR3 newDestination = destination - slidePlaneNormal * ( D3DXVec3Dot( &destination, &slidePlaneNormal ) + slidingPlane.d );
	newDestination += slidePlaneNormal * epsilon;

	// Рассчитываем новую сорость, в роли которой выступает вектор рассечения (vector of the slide).
	D3DXVECTOR3 newVelocity = newDestination - data->intersection;

	// Проверяем, если новый вектор скорости слишком короткий.
	if( D3DXVec3Length( &newVelocity ) <= epsilon )
	{
		// Раз вектор скорости слишком мал, то нет необходимости продолжать
		// выполнять определение столкновения. Поэтому просто назначим новые
		// трансляцию и скорость, а затем вернём управление программе.
		data->translation = newTranslation;
		data->velocity = D3DXVECTOR3( 0.0f, 0.0f, 0.0f );

		return;
	}

	// Устанавливаем новую трансляцию и скорость.
	data->translation = newTranslation;
	data->velocity = newVelocity;

	// Выполняем другое определение столкновения по принципу рекурсии, если это возможно.
	recursion--;
	if( recursion > 0 )
		CollideWithScene( data, vertices, faces, totalFaces, objects, recursion );
}

//-----------------------------------------------------------------------------
// Точка входа в процедуру определения столкновения и расчёта ответной реакции.
//-----------------------------------------------------------------------------
inline void PerformCollisionDetection( CollisionData *data, Vertex *vertices, SceneFace *faces, unsigned long totalFaces, LinkedList< SceneObject > *dynamicObjects )
{
	// Вычисляем трансляцию объекта в пространстве эллипса.
	data->translation.x = data->object->GetTranslation().x / data->object->GetEllipsoidRadius().x;
	data->translation.y = data->object->GetTranslation().y / data->object->GetEllipsoidRadius().y;
	data->translation.z = data->object->GetTranslation().z / data->object->GetEllipsoidRadius().z;

	// Вычисляем скорость объекта в пространстве эллипса.
	data->velocity = data->object->GetVelocity() * data->elapsed;
	data->velocity.x /= data->object->GetEllipsoidRadius().x;
	data->velocity.y /= data->object->GetEllipsoidRadius().y;
	data->velocity.z /= data->object->GetEllipsoidRadius().z;

	// Начинаем рекурсивное определение столкновения.
	CollideWithScene( data, vertices, faces, totalFaces, dynamicObjects );

	// Установим вектор гравитации (gravity vector) на основе вектора скорости (в пространстве эллипса).
	data->velocity.x = data->gravity.x / data->object->GetEllipsoidRadius().x;
	data->velocity.y = data->gravity.y / data->object->GetEllipsoidRadius().y;
	data->velocity.z = data->gravity.z / data->object->GetEllipsoidRadius().z;

	// Выполняем другое рекурсивное определение столкновения для применения гравитации.
	CollideWithScene( data, vertices, faces, totalFaces, dynamicObjects );

	// Вычисляем новую трансляцию объекта на другом конце (выходе с противоположной стороны) пространства эллипса.
	data->translation.x = data->translation.x * data->object->GetEllipsoidRadius().x;
	data->translation.y = data->translation.y * data->object->GetEllipsoidRadius().y;
	data->translation.z = data->translation.z * data->object->GetEllipsoidRadius().z;

	// Проходим через все грани сцены, проверяем пересечение.
	float hitDistance = -1.0f;
	for( unsigned long f = 0; f < totalFaces; f++ )
	{
		// Пропускаем эту грань если её материал настроен на игнорирование лучей (IgnoreRays).
		if( faces[f].renderCache->GetMaterial()->GetIgnoreRay() == true )
			continue;

		// Выполняем тест на пересечение лучей, чтобы увидеть не оказалась ли грань под объектом.
		float distance;
		if( D3DXIntersectTri( (D3DXVECTOR3*)&vertices[faces[f].vertex0], (D3DXVECTOR3*)&vertices[faces[f].vertex1], (D3DXVECTOR3*)&vertices[faces[f].vertex2], &data->translation, &D3DXVECTOR3( 0.0f, -1.0f, 0.0f ), NULL, NULL, &distance ) == TRUE )
			if( distance < hitDistance || hitDistance == -1.0f )
				hitDistance = distance;
	}

	// Если расстояние до пересечения лучей меньше чем радиус
	// объекта по оси y, то данный объект "врыт" в землю/пол.
	// Поэтому просто вытолкнем объект из земли/пола.
	if( hitDistance < data->object->GetEllipsoidRadius().y )
		data->translation.y += data->object->GetEllipsoidRadius().y - hitDistance;

	// Проверяем случай, когда объект касается земли/пола.
	if( hitDistance < data->object->GetEllipsoidRadius().y + 0.1f / data->scale )
		data->object->SetTouchingGroundFlag( true );
	else
		data->object->SetTouchingGroundFlag( false );

	// Обновляем трансляцию (положение) объекта после определения столкновения.
	data->object->SetTranslation( data->translation );
}

#endif

  • Сохрани Решение (Файл->Сохранить все).

Исследуем код CollisionDetection.h (Проект Engine)

В нашу реализацию алгоритма столкновений мы внесли ряд изменений призванных обеспечить его наилучшую совместимость с нашей системой управления сценой. Но самое главное то, что теперь он может регистрировать столкновения между игровыми объектами, позволяя игрокам подбирать (collect) предметы из объектов-спавнеров. Всякий раз, когда объекты сталкиваются друг с другом, алгоритм вызывает функцию CollisionOccured. Это позволяет столкнувшимся объектам выполнить определённые действия в ответ на столкновение, в зависимости от того, с чем именно они столкнулись. Вся прелесть такой системы заключается в том, что она будет работать с любым объектом, который ей "скормят". По крайней мере до тех пор, пока он является потомком базового класса SceneObject. То есть ты можешь создать свои объекты в игре и даже обработать по-своему ответ (реакцию) на столкновение с ними, просто переопределив (override) функцию CollisionOccured для данного объекта.
Система определения столкновений (Collision Detection System) будет полностью интегрирована в нашу систему управления сценой (Scene Management System). Таким образом, когда мы полностью доделаем систему управления сценой, тебе больше не придётся волноваться об исходном коде системы определения столкновений. Но перед этим рассмотрим принцип действия системы определения столкновений, весь исходный код которой содержится всего в одном файле CollisionDetection.h .
Начинается код с объявления структуры CollisionData:

Фрагмент CollisionDetection.h (Проект Engine)
...
//-----------------------------------------------------------------------------
// Collision Data Structure
//-----------------------------------------------------------------------------
struct CollisionData
{
	float scale; // Масштаб, используемый при вызове менеджера сцены (scene manager).
	float elapsed; // Затраченное время на текущий кадр.
	unsigned long frameStamp; // Текущий штамп кадра (frame stamp) согласно менеджеру сцены.

	SceneObject *object; // Указатель на объект, с которым будет выполняться определение столкновения.

	D3DXVECTOR3 translation; // Трансляция в пространство эллипса.
	D3DXVECTOR3 velocity; // Скорость в пространстве эллипса.
	D3DXVECTOR3 normalizedVelocity; // Нормализованная скорость в пространстве эллипса.

	D3DXVECTOR3 gravity; // Вектор гравитации (Gravity vector), который будет сконвертирован в пространство эллипса.

	bool collisionFound; // Сигнализирует, когда обнаружено столкновение.
	float distance; // Расстояние до точки столкновения.
	D3DXVECTOR3 intersection; // Текущая точка пересечения, где произошло столкновение.
};
...

Первые несколько членов данной структуры заполняются нашей системой управления сценой. Они соответствуют масштабу, используемому системой управления сценой, текущий показатель затраченного (elapsed) времени, и текущее состояние параметра frameStamp (штамп кадра), представляющего собой обычное числовое значение, увеличивающееся на единицу в каждом кадре.
Также видим, что структура принимает указатель на объект, который проверяется на столкновение, а также несколько вспомогательных векторов.
Остальные члены данной структуры созданы для использования внутри системы определения столкновений, поэтому мы не будем останавливаться на них подробно. Исключением здесь является вектор gravity, который необходимо установить вручную. Он позволяет ввести в систему столкновений фактор гравитации, действующий на объект. В двух словах для этого необходимо лишь передать в расчёты вектор, направленный в направлении отрицательного луча оси Y.

Закрыть
noteОбрати внимание

Вектор гравитации установленный как (0.0, -9.81, 0.0) даст гравитацию, приблизительно равную земной.

Вся суть использования структуры CollisionData состоит в том, чтобы итерировать через все игровые объекты сцены в каждом фрейме и построить отдельный экземпляр структуры CollisionData с данными для каждого из них. Затем уже заполненная структура (с данными сталкивающегося объекта) передаётся в систему определения столкновений путём вызова функции PerformCollisionDetection. Система определения столкновений сделает всё остальное. Вот прототип функции PerformCollisionDetection:

Прототип функции PerformCollisionDetection
inline void PerformCollisionDetection( CollisionData *data, Vertex *vertices, SceneFace *faces, unsigned long totalFaces, LinkedList<SceneObject> *dynamicObjects )

Видно, что функция получает в качестве вводных параметров структуру CollisionData, а также указатели на 2 массива:

  • Vertex *vertices, содержащий все вершины нашей сцены;
  • SceneFace *faces, содержащий все грани нашей сцены, построенные из данных вершин (обсудим чуть ниже в данной Главе).

Функция также принимает переменную totalFaces, содержащую в себе общее число граней в сцене, а также связный список всех объектов сцены. Все эти данные используются для определения столкновений и ответной реакции на него для одного объекта в текущем кадре.
Как только функция PerformCollisionDetection завершит свою работу, переданный в неё объект (через структуру CollisionData) будет соответствующим образом двигаться в данном кадре, с учётом векторов движения и любых столкновений, которые могут произойти опять же в данном кадре.
Сразу после этого вызываем на данном объекте функцию Update. Во втором её параметре важно указать в параметре addVelocity значение false для того, чтобы убедиться, что объект не движется сам по себе с использованием своего собственного вектора скорости. Ведь система определения столкновений уже переместила объект в данном кадре!
Весь процесс обновления объекта показан в это сниппете (код представлен для примера):

...
void FrameUpdate( float elapsed )
{
 static unsigned long frameStamp = 0;
 frameStamp++;
 
 m_objects->Iterate( true );
 while( m_objects->Iterate() )
  {
   static CollisionData collisionData;
   collisionData.scale = 1.0f;
   collisionData.elapsed = elapsed;
   collisionData.frameStamp = frameStamp;
   collisionData.object = m_objects->GetCurrent();
   collisionData.gravity = D3DXVECTOR3( 0.0f, -9.81f, 0.0f ) * elapsed;
   PerformCollisionDetection( &collisionData, (Vertex*)m_vertices, m_faces, m_totalFaces, m_objects);

   m_objects->GetCurrent()->Update( elapsed, false );
  }
}
...

Просто представь себе функцию FrameUpdate как часть более большой системы и она имеет доступ к членам, которые уже заранее определены (например m_objects и m_vertices).

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

Усечённая пирамида вида (View Frustum)

Как ты помнишь, в начале данной Главы мы говорили об отсечении невидимых граней и рассматривали метод отсечения с применением усечённой пирамиды (frustum culling) или, если быть точнее, усечённой пирамиды вида (view frustum culling). Мы уже знаем, что в каждом кадре усечённая пирамида вида (view frustum) вычисляется с помощью матрицы вида и матрицы проекции. Для обеспечения управления динамической пирамидой вида (dynamic view frustum; т.е. та, которая меняет своё положение в каждом кадре вместе с движениями игрока), мы применим специальный класс ViewFrustum и разместим его в отдельном заголовочном файле ViewFrustum.h.

Создаём ViewFrustum.h (Проект Engine)

ОК, приступаем.

  • Стартуй MSVC++ 2010 и открывай Решение GameProject01 (если не сделал это раньше).
  • В "Обозревателе решений" главного окна MSVC++2010 щёлкни правой кнопкой мыши по папке (в терминологии Майкрософт это не папки, а фильтры!) "Заголовочные файлы" (Header Files) Проекта Engine.
  • Во всплывающем меню Добавить->Создать элемент...
  • В появившемся окне выбери "Заголовочный файл (.h)" и в поле "Имя" введи "ViewFrustum.h".
  • Жмём "Добавить".

Добавленный файл сразу откроется в правой части MSVC++2010.

  • В только что созданном и открытом файле ViewFrustum.h набираем следующий код:

ViewFrustum.h (Проект Engine)
//-----------------------------------------------------------------------------
// Применяется для установки усечённой пирамиды вида (view frustum) из соответст-
// вующей матрицы вида (view matrix).
//
// Original SourceCode:
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#ifndef VIEW_FRUSTUM_H
#define VIEW_FRUSTUM_H

//-----------------------------------------------------------------------------
// View Frustum Class
//-----------------------------------------------------------------------------
class ViewFrustum
{
public:
	void Update( D3DXMATRIX *view );

	void SetProjectionMatrix( D3DXMATRIX projection );

	bool IsBoxInside( D3DXVECTOR3 min, D3DXVECTOR3 max );
	bool IsBoxInside( D3DXVECTOR3 translation, D3DXVECTOR3 min, D3DXVECTOR3 max );
	bool IsSphereInside( D3DXVECTOR3 translation, float radius );

private:
	D3DXMATRIX m_projection; // Указатель на матрицу проекции.
	D3DXPLANE m_planes[5]; // Пять плоскостей, образующих усечённую пирамиду вида (view frustum) (плоскость ближнего плана игнорируется).
};

#endif

  • Сохрани Решение (Файл->Сохранить все).

Исследуем код ViewFrustum.h (Проект Engine)

Класс содержит функцию Update для обновления усечённой пирамиды вида (view frustum) в каждом кадре. Функция SetProjectionMatrix должна вызываться всякий раз при изменении матрицы проекции (projection matrix) для обеспечения корректного расчёта усечённой пирамиды вида. Так как матрица проекции обычно вычисляется лишь однажды, при загрузке сцены, то и функцию SetProjectionMatrix тоже достаточно вызвать всего один раз.
Последние 3 функции используются для проверки, находится ли ограничивающий куб или сфера внутри усечённой пирамиды вида. Ты должно быть заметил, что функция IsBoxInside объявлена дважды. Они выполняют одни и те же операции, но имеют разные вводные параметры.
Чуть ниже видим два переменных члена:

  • m_projection для сохранения матрицы проекции;
  • m_planes для сохранения пяти плоскостей, образующих усечённую пирамиду вида.

Ближняя плоскость, напомним, в нашем случае игнорируется. Поэтому в переменной m_planes будут храниться лишь 5 плоскостей, в то время как усечённая пирамида вида имеет 6 сторон. Раз ближняя плоскость расположена очень близко к наблюдателю (и апексу усечённой пирамиды), то нет необходимости создавать и отслеживать шестую ближнюю плоскость (near plane), которая включает в себя очень небольшую сторону (грань) усечённой пирамиды.

Создаём ViewFrustum.cpp (Проект Engine)

ОК, приступаем.

  • Стартуй MSVC++ 2010 и открывай Решение GameProject01 (если не сделал это раньше).
  • В "Обозревателе решений" главного окна MSVC++2010 щёлкни правой кнопкой мыши по папке (в терминологии Майкрософт это не папки, а фильтры!) "Файлы исходного кода" (Source Files) Проекта Engine.
  • Во всплывающем меню Добавить->Создать элемент...
  • В появившемся окне выбери "Файл C++ (.cpp)" и в поле "Имя" введи "ViewFrustum.cpp".
  • Жмём "Добавить".

Добавленный файл сразу откроется в правой части MSVC++2010.

  • В только что созданном и открытом файле ViewFrustum.cpp набираем следующий код:

ViewFrustum.cpp (Проект Engine)
//-----------------------------------------------------------------------------
// Реализация функций, объявленных в заголовочном файле ViewFrustum.h.
//
// Original SourceCode:
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#include "Engine.h"

//-----------------------------------------------------------------------------
// Создаём усечённую пирамиду вида (view frustum) на основе данной матрицы вида.
//-----------------------------------------------------------------------------
void ViewFrustum::Update( D3DXMATRIX *view )
{
	// Рассчитываем поле видимости (field of view).
	D3DXMATRIX fov;
	D3DXMatrixMultiply( &fov, view, &m_projection );

	// Рассчитываем правую плоскость (right plane).
	m_planes[0].a = fov._14 - fov._11;
	m_planes[0].b = fov._24 - fov._21;
	m_planes[0].c = fov._34 - fov._31;
	m_planes[0].d = fov._44 - fov._41;

	// Рассчитываем левую плоскость (left plane).
	m_planes[1].a = fov._14 + fov._11;
	m_planes[1].b = fov._24 + fov._21;
	m_planes[1].c = fov._34 + fov._31;
	m_planes[1].d = fov._44 + fov._41;

	// Рассчитываем верхнюю плоскость (top plane).
	m_planes[2].a = fov._14 - fov._12;
	m_planes[2].b = fov._24 - fov._22;
	m_planes[2].c = fov._34 - fov._32;
	m_planes[2].d = fov._44 - fov._42;

	// Рассчитываем нижнюю плоскость (bottom plane).
	m_planes[3].a = fov._14 + fov._12;
	m_planes[3].b = fov._24 + fov._22;
	m_planes[3].c = fov._34 + fov._32;
	m_planes[3].d = fov._44 + fov._42;

	// Рассчитываем дальнюю плоскость (дальний план; far plane).
	m_planes[4].a = fov._14 - fov._13;
	m_planes[4].b = fov._24 - fov._23;
	m_planes[4].c = fov._34 - fov._33;
	m_planes[4].d = fov._44 - fov._43;

	// Нормализуем плоскости.
	D3DXPlaneNormalize( &m_planes[0], &m_planes[0] );
	D3DXPlaneNormalize( &m_planes[1], &m_planes[1] );
	D3DXPlaneNormalize( &m_planes[2], &m_planes[2] );
	D3DXPlaneNormalize( &m_planes[3], &m_planes[3] );
	D3DXPlaneNormalize( &m_planes[4], &m_planes[4] );
}

//-----------------------------------------------------------------------------
// Устанавливаем внутреннюю матрицу проекции усечённой пирамиды вида (view frustum's internal projection matrix).
//-----------------------------------------------------------------------------
void ViewFrustum::SetProjectionMatrix( D3DXMATRIX projection )
{
	m_projection = projection;
}

//-----------------------------------------------------------------------------
// Возвращаем true, если данный бокс находится внутри усечённой пирамиды вида.
//-----------------------------------------------------------------------------
bool ViewFrustum::IsBoxInside( D3DXVECTOR3 min, D3DXVECTOR3 max )
{
	for( char p = 0; p < 5; p++ )
	{
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( min.x, min.y, min.z ) ) >= 0.0f )
			continue;
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( max.x, min.y, min.z ) ) >= 0.0f )
			continue;
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( min.x, max.y, min.z ) ) >= 0.0f )
			continue;
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( max.x, max.y, min.z ) ) >= 0.0f )
			continue;
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( min.x, min.y, max.z ) ) >= 0.0f )
			continue;
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( max.x, min.y, max.z ) ) >= 0.0f )
			continue;
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( min.x, max.y, max.z ) ) >= 0.0f )
			continue;
		if( D3DXPlaneDotCoord( &m_planes[p], &D3DXVECTOR3( max.x, max.y, max.z ) ) >= 0.0f )
			continue;

		return false;
	}

	return true;
}

//-----------------------------------------------------------------------------
// Возвращаем true, если данный бокс находится внутри усечённой пирамиды вида.
//-----------------------------------------------------------------------------
bool ViewFrustum::IsBoxInside( D3DXVECTOR3 translation, D3DXVECTOR3 min, D3DXVECTOR3 max )
{
	return IsBoxInside( min + translation, max + translation );
}

//-----------------------------------------------------------------------------
// Возвращаем true, если данная сфера находится внутри усечённой пирамиды вида.
//-----------------------------------------------------------------------------
bool ViewFrustum::IsSphereInside( D3DXVECTOR3 translation, float radius )
{
	for( char p = 0; p < 5; p++ )
		if( D3DXPlaneDotCoord( &m_planes[p], &translation ) < -radius )
			return false;

	return true;
}

  • Сохрани Решение (Файл->Сохранить все).

Исследуем код ViewFrustum.cpp (Проект Engine)

Функция Update по праву считается самой важной во всём классе ViewFrustum. Сначала она может показаться чересчур длинной, но при ближайшем рассмотрении она выполняет лишь самые необходимые операции. Во-первых, она создаёт матрицу поля видимости (FOV matrix) на основе переданной в неё матрицы вида (view matrix) и сохраняет матрицу проекции (projection matrix). Затем она создаёт каждую из пяти плоскостей, образующих вместе усечённую пирамиду вида (view frustum), и в самом конце нормализует их. В Главе 1.10 мы обсуждали, что из себя представляет матрица вида 4х4. В исходном коде функции Update видно, что для того, чтобы создать каждую из плоскостей, достаточно получить доступ к необходимым компонентам матрицы поля видимости. Плоскость представлена в виде точки в 3D-пространстве, которая определена членами (a, b, c) структуры D3DXPLANE. Член d определяет расстояние плоскости до точки начала координат мира (world origin).
Последние несколько функций очень просты.

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

Скрипт сцены (Scene script)

Ты должно быть заметил, что мы кое-что упустили из виду при обсуждении менеджера сцены. Мы так и не затронули тему ассетов (assets; файловых ресурсов), которые представляют собой необходимые ресурсы, которые менеджер сцены использует для рендеринга игровой сцены. Помимо текстур, спавнер-объектов и звуковых эффектов есть ещё два основных вида ресурсов, которые мы должны рассмотреть:

  • скрипты сцены (scene scripts);
  • меш сцены (scene mesh).

Начнём со скриптов. Да, каждый меш игровой сцены (scene mesh) будет сопровождаться файлом скрипта с расширением .txt. Забегая вперёд, скажем, что в конце этой Главы мы создадим игровое тестовое приложение, которое загружает и рендерит на экране файл сцены city.x. К вопросу создания самой сцены (меша) мы ещё вернёмся. А пока рассмотрим сопутствующий её скрипт city.txt, который можно создать в любом текстовом редакторе и взять за образец при создании других скриптов сцен. Напомним, файлы ресурсов расположены в подкаталоге Assets каталога с исполняемым файлом тестового приложения. Именно там он и будет их искать.
ОК, открой Блокнот Windows и набери в нём следующий текст:

city.txt
name = Имя сцены.
gravity = 3D-вектор, определяющий силу притяжения.

ambient_light = Уровень рассеянного света (Ambient light) в сцене.
sun_direction = Направление солнечного света.

fog_colour = Цвет тумана в сцене. При желании можно повсюду распылить зелёный хлор...
fog_density = Насколько плотен туман. Чем больше значение, тем плотнее туман.

mesh = Имя файла меша игровой сцены.
mesh_path = Путь до файла меша игровой сцены.

max_faces = Максимальное число граней, которое может содержать листо сцены.
max_half_size = Макс. половинный размер (half size), который может иметь каждый из листков сцены.

Примечание: Листок сцены (scene leaf) будет далее разделён, если общее число граней в листке больше, чем параметр max_faces, а также размер листка, поделённый надвое (т.е. половинный размер листка) больше, чем параметр max_half_size. Для проведения разделения должны выполняться оба условия одновременно.

#begin

name          string "city"
gravity       vector 0.0 -9.81 0.0

ambient_light colour 0.5 0.5 0.5 1.0
sun_direction vector -0.6 -0.3 0.4

fog_colour    colour 0.8 0.8 0.8 1.0
fog_density   float  0.02

mesh          string "city.x"
mesh_path     string ./Assets/

max_faces     number 32
max_half_size float  16.0

#end
  • Сохрани документ как city.txt в подкаталоге Assets.

Первые 6 переменных используются для настройки сцены. Их названия говорят сами за себя. Кроме того, до начала тега #begin размещены подробные комментарии.
Переменные mesh и mesh_path позволяют указать файл, с расширением .x, который будет использоваться для загрузки и рендеринга геометрии сцены. Последние две переменные используются для определения граней сцены в те или иные листки (scene's leafs). Они определяют макс. число граней, допустимое в одном листке и макс. половинчатый размер (half size) каждого листка сцены. Половинчатый размер это просто его размер по любой из осей (раз уж этот один и тот же размер по всем трём осям, создающим квадратный бокс), поделённый на два. Если листок сцены содержит слишком много граней или слишком большой, то он будет далее поделён на 8 равных по размеру частей.
Конечно же любой из данных параметров скрипта можно изменять (для того скрипты и созданы). Когда получим готовое тестовое приложение, "поиграй" с различными параметрами скрипта сцены и оцени изменения во время реального рендеринга сцены после запуска приложения.

Меш сцены (Scene mesh)

Создать меш сцены на самом деле не так трудно, если имеешь хотя бы начальные навыки работы с программными пакетами по созданию 3D графики, например с 3DS Max. О том, где взять его триальную версию, как начать с ним работать и настроить в нём экспорт .x-файлов, читай статью 3D Studio Max 7 Установка и настройка экспорта .X-файлов. Существуют также другие программы для создания модели сцены. Одна из популярных - Milkshape3D, различные версии которой нетрудно найти в Яндексе. Вообще, ты можешь использовать любой 3D-моделер, который пожелаешь, при условии, что он "умеет" сохранять модели в файл формата .X и в нём можно присваивать имя каждому фрейму в общей иерархии фреймов меша. Скоро ты увидишь, почему это так важно.

Источники:


1. Young V. Programming a Multiplayer FPS in DirectX 9.0. - Charles River Media. 2005


Contributors to this page: slymentat .
Последнее изменение страницы Воскресенье 16 / Январь, 2022 02:36:57 MSK автор slymentat.

Помочь проекту

yoomoney.ru (бывший Яндекс-деньги): 410011791055108