Загрузка...
 
Печать
Кодим 3D FPS DX9

1.17 Создаём менеджер сцены


Содержание



Добавляем SceneManager.h (Проект Engine)1

  • Стартуй MSVC++ 2010 и открывай Решение GameProject01 (если не сделал этого раньше).
  • В "Обозревателе решений" главного окна MSVC++2010 щёлкни правой кнопкой мыши по папке (в терминологии Майкрософт это не папки, а фильтры!) "Заголовочные файлы" Проекта Engine.
  • Во всплывающем меню Добавить->Создать элемент... (Add->New Item...)
  • В появившемся окне выбери "Заголовочный файл (.h)" и в поле "Имя" введи "SceneManager.h".
Image
Добавленный файл сразу откроется в правой части MSVC++2010.
  • В только что созданном и открытом файле SceneManager.h набираем следующий код:
SceneManager.h
//-----------------------------------------------------------------------------
// File: SceneManager.h
// Manages and renders a scene and the objects in it using frustum and
// occlusion culling, and performing collision detection.
// Управляет и рендерит сцену и объекты в ней, используя отсечения методом
// усечённой пирамиды и на основе перекрытия. Выполняет определение столкновений.
//
// Original SourcrCode:
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#ifndef SCENE_MANAGER_H
#define SCENE_MANAGER_H

//-----------------------------------------------------------------------------
// Scene Occluder Structure
// Структура данных заслоняющего объекта сцены
//-----------------------------------------------------------------------------
struct SceneOccluder : public BoundingVolume
{
	unsigned long visibleStamp; // Stamp indicating if the occluder is visible in the current frame.
			// Шатмп, указывающий, видим ли перекрывающий объект (оклюдер) в данном фрейме.
	D3DXVECTOR3 translation; // Translation of the occluder.
			// Трансляция оклюдера.
	unsigned long totalFaces; // Total number of faces in the occluder's mesh.
			// Общее число граней в меше оклюдера.
	Vertex *vertices; // Array containing the occluder's vertices transformed into world space.
			// Массив, содержащий вершины оклюдера, трансформированные в мировое пространство.
	unsigned short *indices; // Array of indices into the vertex array.
			// Массив индексов массива вершин.
	LinkedList< D3DXPLANE > *planes; // List of planes that define the occluded volume.
			// Список плоскостей, которые определяют перекрывающий объём (occluding volume).
	float distance; // Distance between the viewer and the occluder.
			// Расстояние между наблюдателем и оклюдером.

	//-------------------------------------------------------------------------
	// The scene occluder structure constructor.
	//-------------------------------------------------------------------------
	SceneOccluder( D3DXVECTOR3 t, ID3DXMesh *mesh, D3DXMATRIX *world )
	{
		// Clear the visible stamp.
		// Очищаем штамп видимости.
		visibleStamp = -1;

		// Set the translation.
		// Устанавливаем трансляцию.
		translation = t;

		// Set the total faces and create the vertx and idex arrays.
		// Устанавливаем общее число граней и создаём массивы вершин и индеков.
		totalFaces = mesh->GetNumFaces();
		vertices = new Vertex[mesh->GetNumVertices()];
		indices = new unsigned short[totalFaces * 3];

		// Lock the given mesh's vertex and index buffers.
		// Блокируем (lock) буферы вершин и индексов данного меша.
		Vertex* verticesPtr;
		mesh->LockVertexBuffer( 0, (void**)&verticesPtr );
		unsigned short *indicesPtr;
		mesh->LockIndexBuffer( 0, (void**)&indicesPtr );

		// Copy the vertices and the indices.
		// Копируем вершины и индексы.
		memcpy( vertices, verticesPtr, VERTEX_FVF_SIZE * mesh->GetNumVertices() );
		memcpy( indices, indicesPtr, sizeof( unsigned short ) * totalFaces * 3 );

		// Unlock the vertex and index buffers.
		// Разблокируем (unlock) буферы вершин и индексов данного меша.
		mesh->UnlockVertexBuffer();
		mesh->UnlockIndexBuffer();

		// Transform the vertices into world space.
		// Трансформируем вершины в мировое пространство.
		for( unsigned long v = 0; v < mesh->GetNumVertices(); v++ )
			D3DXVec3TransformCoord( &vertices[v].translation, &vertices[v].translation, world );

		// Create a list of planes for building the occlusion volume.
		// Создаём список плоскостей для построения перекрывающего объёма (occlusion volume).
		planes = new LinkedList< D3DXPLANE >;

		// Create a bounding volume from the occluder's mesh.
		// Создаём ограничивающий объём из меша оклюдера.
		BoundingVolumeFromMesh( mesh );

		// Resposition the bounding volume into world space.
		// Репозиционируем ограничивающий объём в мировое пространство.
		D3DXMATRIX location;
		D3DXMatrixTranslation( &location, t.x, t.y, t.z );
		RepositionBoundingVolume( &location );
	}

	//-------------------------------------------------------------------------
	// The scene occluder structure destructor.
	//-------------------------------------------------------------------------
	virtual ~SceneOccluder()
	{
		SAFE_DELETE_ARRAY( vertices );
		SAFE_DELETE_ARRAY( indices );

		SAFE_DELETE( planes );
	}
};

//-----------------------------------------------------------------------------
// Scene Leaf Structure
// Структура данных листка (leaf) сцены
//-----------------------------------------------------------------------------
struct SceneLeaf : public BoundingVolume
{
	SceneLeaf *children[8]; // Array of child scene leaf pointers.
				// Массив указателей на дочерние листки сцены
	unsigned long visibleStamp; // Indicates if the scene leaf is visible in the current frame.
				// Указывает, видим ли листок сцены в данном фрейме.
	LinkedList< SceneOccluder > *occluders; // list of scene occluders in the scene leaf.
				// Список оклюдеров сцены в листке сцены.
	unsigned long totalFaces; // Total number of faces in the scene leaf.
				// Общее число граней в листке сцены.
	unsigned long *faces; // Array of indices pointing to the faces in the scene leaf.
				// Массив индексов, указывающих на грани листка сцены.

	//-------------------------------------------------------------------------
	// The scene leaf structure constructor.
	//-------------------------------------------------------------------------
	SceneLeaf()
	{
		for( char l = 0; l < 8; l++ )
			children[l] = NULL;
		occluders = new LinkedList< SceneOccluder >;
		totalFaces = 0;
		faces = NULL;
	}

	//-------------------------------------------------------------------------
	// The scene leaf structure destructor.
	//-------------------------------------------------------------------------
	virtual ~SceneLeaf()
	{
		for( char l = 0; l < 8; l++ )
			SAFE_DELETE( children[l] );
		occluders->ClearPointers();
		SAFE_DELETE( occluders );
		SAFE_DELETE_ARRAY( faces );
	}
};

//-----------------------------------------------------------------------------
// Scene Face Structure
// Структура данных грани сцены
//-----------------------------------------------------------------------------
struct SceneFace : public IndexedFace
{
	RenderCache *renderCache; // Pointer to the render cache this face belongs to.
				// Указатель на рендер-кэш, которому принадлежит данная грань.
	unsigned long renderStamp; // Indicates when the face was last rendered.
				// Указывает, когда грань рендерилась последний раз.
};

//-----------------------------------------------------------------------------
// Ray Intersection Result Struction
// Структура данных пересечения лучей
//-----------------------------------------------------------------------------
struct RayIntersectionResult
{
	Material *material; // Pointer to the material of the intersected face.
			// Указатель на материал пересекаемой грани.
	float distance; // Distance the ray can travel until intersection occurs.
			// Расстояние, которое луч может преодолеть до наступления пересечения.
	D3DXVECTOR3 point; // Intersection point in 3D space.
			// Точка пересечения в ЗD-пространстве.
	SceneObject *hitObject; // Pointer to the hit scene object (if one was hit).
			// Указатель на удар по объекту сцены (если объект был ударен).

	//-------------------------------------------------------------------------
	// The ray intersection result structure constructor.
	//-------------------------------------------------------------------------
	RayIntersectionResult()
	{
		material = NULL;
		distance = 0.0f;
		point = D3DXVECTOR3( 0.0f, 0.0f, 0.0f );
		hitObject = NULL;
	}
};

//-----------------------------------------------------------------------------
// Scene Manager Class
//-----------------------------------------------------------------------------
class SceneManager
{
public:
	SceneManager( float scale, char *spawnerPath );
	virtual ~SceneManager();

	void LoadScene( char *name, char *path = "./" );
	void DestroyScene();
	bool IsLoaded();

	void Update( float elapsed, D3DXMATRIX *view = NULL );
	void Render( float elapsed, D3DXVECTOR3 viewer );

	SceneObject *AddObject( SceneObject *object );
	void RemoveObject( SceneObject **object );

	SceneObject *GetRandomPlayerSpawnPoint();
	SceneObject *GetSpawnPointByID( long id );
	long GetSpawnPointID( SceneObject *point );

	LinkedList< SpawnerObject > *GetSpawnerObjectList();

	bool RayIntersectScene( RayIntersectionResult *result, D3DXVECTOR3 rayPosition,
		D3DXVECTOR3 rayDirection, bool checkScene = true, SceneObject *thisObject = NULL,
		bool checkObjects = false );

private:
	void BuildOcclusionVolume( SceneOccluder *occluder, D3DXVECTOR3 viewer );

	void RecursiveSceneBuild( SceneLeaf *leaf, D3DXVECTOR3 translation, float halfSize );
	bool RecursiveSceneFrustumCheck( SceneLeaf *leaf, D3DXVECTOR3 viewer );
	void RecursiveSceneOcclusionCheck( SceneLeaf *leaf );

private:
	char *m_name; // Name of the scene.
			// Имя сцены.
	float m_scale; // Scene scale in meters/unit.
			// Масштаб (scale) сцены в метрах или юнитах.
	ViewFrustum m_viewFrustum; // View frustum for visiblity culling.
			// Усечённая пирамида вида для отсечения невидимые граней.
	D3DXVECTOR3 m_gravity; // Constant gravity pull.
			// Постоянная сила притяжения.
	bool m_loaded; // Indicates if the scene has been loaded or not.
			// Указывает, была сцена загружена или нет.
	Mesh *m_mesh; // Mesh for the scene.
			// Меш сцены.
	unsigned long m_maxFaces; // Maximum number of faces per scene leaf.
			// Макс, число граней в каждом листке сцены.
	float m_maxHalfSize; // Maximum half size of a scene leaf.
			// Макс, размер половины листка сцены.
	unsigned long m_frameStamp; // Current frame time stamp.
			// Текущий штамп времени кадра.

	LinkedList< SceneObject > *m_dynamicObjects; // Linked list of dynamic objects.
			// Связный список динамических объектов.
	LinkedList< SceneOccluder > *m_occludingObjects; // Linked list of occluding objects.
			// Связный список перекрывающие объектов.
	LinkedList< SceneOccluder > *m_visibleOccluders; // Linked list of visible occluders each frame.
			// Связный список оклюдеров, видимых в каждом кадре.
	LinkedList< SceneObject > *m_playerSpawnPoints; // Linked list of player spawn points.
			// Связный список точек респауна игрока.
	LinkedList< SpawnerObject > *m_objectSpawners; // Linked list of object spawners.
			// Связный список спаунер-объектов.
	char *m_spawnerPath; // Path used for loading the spawner object scripts.
			// Путь, используемый для загрузки скриптов спаунер-объектов.

	SceneLeaf *m_firstLeaf; // The first scene leaf in the scene hierarchy.
			// Первый листок сцены в иерархии сцены.

	IDirect3DVertexBuffer9 *m_sceneVertexBuffer; // Vertex buffer for all the vertices in the scene.
			// Вершинный буфер для всей вершин сцены.
	Vertex *m_vertices; // Pointer for accessing the vertices in the vertex buffer.
			// Указатель для доступа к вершинам в вершинном буфере.
	unsigned long m_totalVertices; // Total number of vertices in the scene.
			// Общее число вершин в сцене.

	LinkedList< RenderCache > *m_renderCaches; // Linked list of render caches.
			// Связный список рендер-кэшей.

	unsigned long m_totalFaces; // Total number of faces in the scene.
			// Общее число граней в сцене.
	SceneFace *m_faces; // Array of faces in the scene.
			// Указатель на грани в сцене.
};

#endif

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

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


Структура SceneFace ("грань сцены")

Ты, должно быть, обратил внимание на то, что в одном из вводных параметров функции PerformCollisionDetection присутствует указатель на массив структур SceneFace:
Прототип функции PerformCollisionDetection
inline void PerformCollisionDetection( CollisionData *data, Vertex *vertices, SceneFace *faces,
unsigned long totalFaces, LinkedListcSceneObject> *dynamicObjects )

Так выглядит определение структуры SceneFace в заголовочном файле SceneManager.h:
Фрагмент SceneManager.h (Проект Engine)
...
//-----------------------------------------------------------------------------
// Scene Face Structure
// Структура данных грани сцены
//-----------------------------------------------------------------------------
struct SceneFace : public IndexedFace
{
	RenderCache *renderCache; // Pointer to the render cache this face belongs to.
				// Указатель на рендер-кэш, которому принадлежит данная грань.
	unsigned long renderStamp; // Indicates when the face was last rendered.
				// Указывает, когда грань рендерилась последний раз.
};
...

Как видишь, она совсем небольшая. Она ветвится от структуры IndexedFace, определённой в Geometry.h . Структура SceneFace позволяет нам отслеживать любую грань сцены. Её член renderCache хранит указатель на рендер-кэш, которому данная грань принадлежит. Член renderStamp представляет собой обычный штамп кадра. Единственная разница состоит в том, что вместо того, чтобы инкрементироваться (увеличиваться на 1) в каждом кадре, данный штамп кадра соответствует текущему штампу кадра, в котором данная грань рендерится. Отслеживая (по штампу) кадр, в котором данная грань рендерилась последний раз, мы дополнительно проверяем, чтобы каждая грань была отрендерена не более одного раза в одном и том же кадре.
Закрыть
noteОбрати внимание

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


Структура SceneLeaf ("листок сцены")

Как ты уже знаешь, все грани нашей сцены будут поделены по принципу "дерева октантов". Это позволяет группировать грани в логические ограничивающие объёмы (logical bounding volumes), чтобы затем уже эти самые ограничивающие объёмы (а не отдельные грани) проверялись на отсечение невидимых граней. Каждый такой логический ограничивающий объём мы будем называть "листком" сцены (Scene leaf; от англ. "leaf" - лист дерева). В каком-то смысле они и являются своеобразными "листьями" нашего дерева октантов. Определение структуры SceneLeaf представлено в заголовочном файле SceneManager.h и выглядит так:
Фргамент SceneManager.h (Проект Engine)
...
//-----------------------------------------------------------------------------
// Scene Leaf Structure
// Структура данных листка (leaf) сцены
//-----------------------------------------------------------------------------
struct SceneLeaf : public BoundingVolume
{
	SceneLeaf *children[8]; // Array of child scene leaf pointers.
				// Массив указателей на дочерние листки сцены
	unsigned long visibleStamp; // Indicates if the scene leaf is visible in the current frame.
				// Указывает, видим ли листок сцены в данном кадре.
	LinkedList< SceneOccluder > *occluders; // list of scene occluders in the scene leaf.
				// Список оклюдеров сцены в листке сцены.
	unsigned long totalFaces; // Total number of faces in the scene leaf.
				// Общее число граней в листке сцены.
	unsigned long *faces; // Array of indices pointing to the faces in the scene leaf.
				// Массив индексов, указывающих на грани листка сцены.

	//-------------------------------------------------------------------------
	// The scene leaf structure constructor.
	//-------------------------------------------------------------------------
	SceneLeaf()
	{
		for( char l = 0; l < 8; l++ )
			children[l] = NULL;
		occluders = new LinkedList< SceneOccluder >;
		totalFaces = 0;
		faces = NULL;
	}

	//-------------------------------------------------------------------------
	// The scene leaf structure destructor.
	//-------------------------------------------------------------------------
	virtual ~SceneLeaf()
	{
		for( char l = 0; l < 8; l++ )
			SAFE_DELETE( children[l] );
		occluders->ClearPointers();
		SAFE_DELETE( occluders );
		SAFE_DELETE_ARRAY( faces );
	}
};
...

Структура SceneLeaf ветвится от класса BoundingVolume т.к. в широком смысле представляет собой всё тот же ограничивающий объём (если точнее - куб или бокс, который класс BoundingVolume также поддерживает). Структура "укомплектована" стандартным конструктором и деструктором для инициализации и уничтожения всего необходимого. Из кода видно, что структура объявляет массив указателей, содержащий сведения о её "потомках" (children). Это позволяет организовать создание, трассировку и уничтожение иерархии ограничивающих объёмов, на которые сцена будет поделена. Также видим штамп видимости (visibleStamp), который работает аналогично рендер-штампу (renderStamp) в структуре SceneFace. В данном случае штамп видимости отмечает, когда данный экземпляр структуры SceneLeaf был виден последний раз.
Чуть ниже создаётся связный список (linked list) оклюдеров (перекрывающих объектов) сцены, а также объявляются переменные для работы с гранями сцены. Другими словами, сама структура включает в себя данные о том, какие оклюдеры и какие именно грани сцены фактически расположены внутри данного листка.
Вот и вся информация о данной структуре.) По началу она может показаться бесполезной, но это временно, до тех пор, пока за дело не возьмётся наш менеджер сцены. Именно тогда раскроется вся мощь структуры SceneLeaf. Она применяется в качестве строительных блоков иерархии сцены, которые делят сцену для эффективного рендеринга. Но прежде чем испытать менеджер сцены в действии, рассмотрим ещё одну фундаментальную структуру SceneOccluder, которую также использует менеджер сцены. Вообще, структура SceneLeaf использует её тоже. Как видим, все компоненты менеджера сцены тесно взаимосвязаны.

Структура SceneOccluder ("перекрывающий объект сцены")

  • Самая большая и сложная из трёх структур менеджера сцены.
Чуть выше мы уже говорили о перекрывающих объектах сцены (т.н. "оклюдерах"), т.е. об объектах, частично или полностью прячущие фрагменты сцены за собой. Структура SceneOccluder будет использоваться для отслеживания одного перекрывающего объекта, а также для управления им. Другими словами, для каждого перекрывающего объекта сцены нам необходим один инстанс данной структуры.
Определение структуры SceneOccluder представлено в заголовочном файле SceneManager.h и выглядит так:
Фрагмент SceneManager.h (Проект Engine)
...
//-----------------------------------------------------------------------------
// Scene Occluder Structure
// Структура данных заслоняющего объекта сцены
//-----------------------------------------------------------------------------
struct SceneOccluder : public BoundingVolume
{
	unsigned long visibleStamp; // Stamp indicating if the occluder is visible in the current frame.
			// Шатмп, указывающий, видим ли перекрывающий объект (оклюдер) в данном кадре.
	D3DXVECTOR3 translation; // Translation of the occluder.
			// Трансляция оклюдера.
	unsigned long totalFaces; // Total number of faces in the occluder's mesh.
			// Общее число граней в меше оклюдера.
	Vertex *vertices; // Array containing the occluder's vertices transformed into world space.
			// Массив, содержащий вершины оклюдера, трансформированные в мировое пространство.
	unsigned short *indices; // Array of indices into the vertex array.
			// Массив индексов массива вершин.
	LinkedList< D3DXPLANE > *planes; // List of planes that define the occluded volume.
			// Список плоскостей, которые определяют перекрывающий объём (occluding volume).
	float distance; // Distance between the viewer and the occluder.
			// Расстояние между наблюдателем и оклюдером.

	//-------------------------------------------------------------------------
	// The scene occluder structure constructor.
	//-------------------------------------------------------------------------
	SceneOccluder( D3DXVECTOR3 t, ID3DXMesh *mesh, D3DXMATRIX *world )
	{
		// Clear the visible stamp.
		// Очищаем штамп видимости.
		visibleStamp = -1;

		// Set the translation.
		// Устанавливаем трансляцию.
		translation = t;

		// Set the total faces and create the vertx and idex arrays.
		// Устанавливаем общее число граней и создаём массивы вершин и индеков.
		totalFaces = mesh->GetNumFaces();
		vertices = new Vertex[mesh->GetNumVertices()];
		indices = new unsigned short[totalFaces * 3];

		// Lock the given mesh's vertex and index buffers.
		// Блокируем (lock) буферы вершин и индексов данного меша.
		Vertex* verticesPtr;
		mesh->LockVertexBuffer( 0, (void**)&verticesPtr );
		unsigned short *indicesPtr;
		mesh->LockIndexBuffer( 0, (void**)&indicesPtr );

		// Copy the vertices and the indices.
		// Копируем вершины и индексы.
		memcpy( vertices, verticesPtr, VERTEX_FVF_SIZE * mesh->GetNumVertices() );
		memcpy( indices, indicesPtr, sizeof( unsigned short ) * totalFaces * 3 );

		// Unlock the vertex and index buffers.
		// Разблокируем (unlock) буферы вершин и индексов данного меша.
		mesh->UnlockVertexBuffer();
		mesh->UnlockIndexBuffer();

		// Transform the vertices into world space.
		// Трансформируем вершины в мировое пространство.
		for( unsigned long v = 0; v < mesh->GetNumVertices(); v++ )
			D3DXVec3TransformCoord( &vertices[v].translation, &vertices[v].translation, world );

		// Create a list of planes for building the occlusion volume.
		// Создаём список плоскостей для построения перекрывающего объёма (occlusion volume).
		planes = new LinkedList< D3DXPLANE >;

		// Create a bounding volume from the occluder's mesh.
		// Создаём ограничивающий объём из меша оклюдера.
		BoundingVolumeFromMesh( mesh );

		// Resposition the bounding volume into world space.
		// Репозиционируем ограничивающий объём в мировое пространство.
		D3DXMATRIX location;
		D3DXMatrixTranslation( &location, t.x, t.y, t.z );
		RepositionBoundingVolume( &location );
	}

	//-------------------------------------------------------------------------
	// The scene occluder structure destructor.
	//-------------------------------------------------------------------------
	virtual ~SceneOccluder()
	{
		SAFE_DELETE_ARRAY( vertices );
		SAFE_DELETE_ARRAY( indices );

		SAFE_DELETE( planes );
	}
};
...

В начале видим, что структура SceneOccluder ветвится от класса BoundingVolume. А всё из-за того, что наши оклюдеры окружены ограничивающими объёмами, которые используются для определения, к какому листку октодерева он принадлежит. Это позволяет нам определить, видим ли оклюдер в каждом кадре, и, следовательно, предотвратить процессинг тех, которые в данном кадре не видны.
В структуре также можно видеть штамп видимости (visibleStamp). Он в точности повторяет аналогичный штамп в структуре SceneLeaf и служит для отслеживания видимости оклюдера.
Следующим в списке переменных членов идёт translation, который хранит текущее положение оклюдера в ЗD-пространстве. Далее идут массивы вершин и их индексов, а также переменная, содержащая общее число граней (totalFaces), образующих оклюдер. Нам необходимо сохранять вершины и их индексы, т.к. наши оклюдеры могут иметь в принципе любую геометрическую форму. Другими словами, мы можем, допустим, иметь один оклюдер в виде дома, а другой - в виде большого грузовика. Оба этих объекта будут иметь разный набор граней, из которых они состоят. Кроме того, оклюдер легко может иметь форму обычного бокса. При определении оклюдеров важно соблюдать осторожность, т.к. если оклюдеры имеют чересчур много граней, их расчёт может занимать значительные ресурсы компьютера. Лучшие оклюдеры - это большие объекты, состоящие из небольшого числа граней, как например большой прямоугольный бокс (как вариант им может быть многоэтажный дом). Мы ещё вернёмся к этой теме чуть позднее.

Image
Рис.1 Перекрывающий объём, построенный по контуру 3D-формы


В коде также видно, что структура SceneOccluder содержит связный список плоскостей (planes) и переменный член distance. Если помнишь, наши оклюдеры действуют по тому же принципу, что и усечённая пирамида отсечения невидимых граней (frustum for culling). Стой лишь разницей, что вместо того, чтобы отсекать всё, что за её пределами, мы отсекаем только то, что находится внутри неё. Для выполнения подобной задачи, мы, очевидно, должны построить усечённую пирамиду, каждая сторона которой продолжается (extends) в направлении взгляда наблюдателя (см. Рис.1). Точно также как и с усечённой пирамидой вида (view frustum), мы используем плоскости для определения сторон усечённой пирамиды оклюдера. В тоже время, в отличие от усечённой пирамиды вида (которая имеет максимум б сторон), мы заранее никогда не знаем, сколько плоскостей понадобится для нашей усечённой пирамиды перекрытия (occluding frustum). А всё из-за того, что в качестве оклюдеров могут выступать объекты со "свободной" формой, со множеством граней, поверх которых будут продолжаться плоскости.
Так для чего же нужен переменный член distance? Он создан для отслеживания расстояния от оклюдера до наблюдателя в каждом кадре. Для чего это нужно? Представь, что у нас есть несколько оклюдеров, видимых в каждом кадре, и нам необходимо убедиться в том, что мы обрабатываем их как можно меньше из них. Для этого необходимо учесть, когда один оклюдер полностью заслоняет (conceals) собой другой, спрятанный за ним. Например, у нас есть большое здание, расположенное перед наблюдателем, и второе здание поменьше, спрятанное за ним. Если большое здание полностью заслоняет малое, то последнее вообще нет смысла обрабатывать. Ведь всё, что заслоняет малое здание, гарантированно заслонено большим. Поэтому достаточно в качестве оклюдера обработать только его. Лучший способ организовать такую процедуру обработки - это обрабатывать оклюдеры в порядке от ближайшего (к наблюдателю) до самого дальнего. Таким образом мы сначала обрабатываем, оклюдер, расположенный ближе всего к наблюдателю, затем следующий, ближайший к нему и т.д. Так мы проверяем наличие каких-либо удалённых оклюдеров, которые удалены от наблюдателя и, вместе с тем, полностью перекрыты другими оклюдерами. Если таковые имеются, то мы можем просто игнорировать их.
Последними в структуре идут её конструктор и деструктор. Деструктор предельно ясен, в то время как конструктор выполняет массу всевозможных действий. Он сохраняет вершины и их индексы меша, который в него передаётся. Эти вершины и их индексы затем трансформируются на основе мировой матрицы, указатель на которую также передаётся в качестве вводного параметра конструктора. Данная операция перемещает вершины из пространства объекта (model space) в мировое пространство (world space) чтобы таким образом они были готовы к размещению в ЗD-пространстве игровой сцены. В финале конструктора мы создаём (и позиционируем) ограничивающий объём, основываясь на меше оклюдера.

Добавляем SceneManager.cpp (Проект Engine)

В файле исходного кода SceneManager.cpp будут размещаться реализации функций, объявленных в SceneManager.h .
  • В "Обозревателе решений" главного окна MSVC++2010 щёлкни правой кнопкой мыши по папке (в терминологии Майкрософт это не папки, а фильтры!) "Файлы исходного кода" Проекта Engine.
  • Во всплывающем меню Добавить->Создать элемент...
  • В появившемся окне выбери "Файл С++ (.cpp)" и в поле "Имя" введи "SceneManager.cpp".
  • Жмём "Добавить".
Добавленный файл сразу откроется в правой части MSVC++2010.
  • В только что созданном и открытом файле SceneManager.cpp набираем следующий код:
SceneManager.cpp (Проект Engine)
//-----------------------------------------------------------------------------
// File: SceneManager.h
// SceneManager.h implementation.
// Реализация функций, объявленных в SceneManager.h .
// Refer to the SceneManager.h interface for more details.
//
// Original SourceCode:
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#include "Engine.h"

//-----------------------------------------------------------------------------
// The scene manager class constructor.
//-----------------------------------------------------------------------------
SceneManager::SceneManager( float scale, char *spawnerPath )
{
	m_name = NULL;
	m_scale = scale;
	m_gravity = D3DXVECTOR3( 0.0f, 0.0f, 0.0f );
	m_loaded = false;
	m_mesh = NULL;
	m_maxFaces = 0;
	m_maxHalfSize = 0.0f;
	m_frameStamp = 0;

	m_dynamicObjects = new LinkedList< SceneObject >;
	m_occludingObjects = NULL;
	m_visibleOccluders = NULL;
	m_playerSpawnPoints = NULL;
	m_objectSpawners = NULL;
	m_spawnerPath = spawnerPath;

	m_firstLeaf = NULL;

	m_sceneVertexBuffer = NULL;
	m_vertices = NULL;
	m_totalVertices = 0;

	m_renderCaches = NULL;

	m_totalFaces = 0;
	m_faces = NULL;
}

//-----------------------------------------------------------------------------
// The scene manager class destructor.
//-----------------------------------------------------------------------------
SceneManager::~SceneManager()
{
	DestroyScene();

	// Destroy the dynamic objects list as it was created in the constructor.
	// Уничтожает связный список динамических объектов, созданный конструктором.
	SAFE_DELETE( m_dynamicObjects );
}

//-----------------------------------------------------------------------------
// Loads a new scene from the given scene file.
// Загружает новую сцену из данного файла скрипта сцены.
//-----------------------------------------------------------------------------
void SceneManager::LoadScene( char *name, char *path )
{
	// Create the lists of objects used in the scene. The dynamic object list
	// is persistent across scene changes so it doesn't need to be created.
	// Создаём связные списки объектов сцены (по типам).
	m_occludingObjects = new LinkedList< SceneOccluder >;
	m_visibleOccluders = new LinkedList< SceneOccluder >;
	m_playerSpawnPoints = new LinkedList< SceneObject >;
	m_objectSpawners = new LinkedList< SpawnerObject >;

	// Load the script for the scene.
	// Загружаем скрипт сцены.
	Script *script = new Script( name, path );

	// Store the name of the scene.
	// Сохраняем имя сцены.
	m_name = new char[strlen( script->GetStringData( "name" ) ) + 1];
	memcpy( m_name, script->GetStringData( "name" ), ( strlen( script->GetStringData( "name" ) ) + 1 ) * sizeof( char ) );

	// Store the scene's gravity vector.
	// Сохраняем вектор гравитации сцены.
	m_gravity = *script->GetVectorData( "gravity" ) / m_scale;

	// Create the sun light source.
	// Создаём источник солнечного света.
	D3DLIGHT9 sun;
	sun.Type = D3DLIGHT_DIRECTIONAL;
	sun.Diffuse.r = 1.0f;
	sun.Diffuse.g = 1.0f;
	sun.Diffuse.b = 1.0f;
	sun.Diffuse.a = 1.0f;
	sun.Specular = sun.Diffuse;
	sun.Ambient.r = script->GetColourData( "ambient_light" )->r;
	sun.Ambient.g = script->GetColourData( "ambient_light" )->g;
	sun.Ambient.b = script->GetColourData( "ambient_light" )->b;
	sun.Ambient.a = script->GetColourData( "ambient_light" )->a;
	sun.Direction = D3DXVECTOR3( script->GetVectorData( "sun_direction" )->x,
		script->GetVectorData( "sun_direction" )->y,
		script->GetVectorData( "sun_direction" )->z );
	sun.Range = 0.0f;

	// Switch lighting on, enable the sun light, and specular highlights.
	// Включаем созданный выше источник света. Активируем блики.
	g_engine->GetDevice()->SetRenderState( D3DRS_LIGHTING, true );
	g_engine->GetDevice()->SetLight( 0, &sun );
	g_engine->GetDevice()->LightEnable( 0, true );
	g_engine->GetDevice()->SetRenderState( D3DRS_SPECULARENABLE, true );

	// Set up the fog.
	// Настраиваем туман.
	float density = *script->GetFloatData( "fog_density" ) * m_scale;
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGENABLE, true );
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGCOLOR, D3DCOLOR_COLORVALUE(
		script->GetColourData( "fog_colour" )->r,
		script->GetColourData( "fog_colour" )->g,
		script->GetColourData( "fog_colour" )->b,
		script->GetColourData( "fog_colour" )->a ) );
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGVERTEXMODE, D3DFOG_EXP );
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGDENSITY, *(unsigned long*)&density );

	// Store the constraints used for creating the scene.
	// Получаем из скрипта сцены параметры листков и сохраняем их в переменные.
	m_maxFaces = *script->GetNumberData( "max_faces" );
	m_maxHalfSize = *script->GetFloatData( "max_half_size" );

	// Load the scene's mesh.
	// Загружаем меш сцены (прописан в скрипте меша).
	m_mesh = g_engine->GetMeshManager()->Add( script->GetStringData( "mesh" ), script->GetStringData( "mesh_path" ) );

	// Destory the scene's script as it is no longer needed.
	// Уничтожаем скрипт сцены, т.к. он болвше не нужен.
	SAFE_DELETE( script );

	// Set a new projection matrix so the view frustum will fit the scene.
	// Устанавливаем новую матрицу проекции такм образом, чтобы усечённая пирамида вида вмещала в себя сцену.
	D3DDISPLAYMODE *display;
	display = g_engine->GetDisplayMode();
	D3DXMATRIX projection;
	D3DXMatrixPerspectiveFovLH( &projection, D3DX_PI / 4, (float)display->Width / (float)display->Height,
		0.1f / m_scale, m_mesh->GetBoundingSphere()->radius * 2.0f );
	g_engine->GetDevice()->SetTransform( D3DTS_PROJECTION, &projection );

	// Set the view frustum's projection matrix.
	// Назначаем усечённой пирамиде вида рассчитанную выше матрицу проекции. 
	m_viewFrustum.SetProjectionMatrix( projection );

	// Create the list of render caches.
	// Создаём связный список рендер-кэшей.
	m_renderCaches = new LinkedList< RenderCache >;

	// Search the mesh for unique materials.
	// Ищем в меше уникальные материалы.
	for( unsigned long m = 0; m < m_mesh->GetStaticMesh()->NumMaterials; m++ )
	{
		// Flag to determine if the material has been found already.
		// Флаг, определяющий, найден ли материал ранее.
		bool found = false;

		// Ensure the new material is valid.
		// Проверяем, валиден ли новый материал.
		if( m_mesh->GetStaticMesh()->materials[m] == NULL )
			continue;

		// Iterate through the already existing render caches.
		// Итерируем через существующие рендер-кэши.
		m_renderCaches->Iterate( true );
		while( m_renderCaches->Iterate() )
		{
			// Check if the new material already exists.
			// Проверяем случай, когда найденный материал уже есть в списке.
			if( m_renderCaches->GetCurrent()->GetMaterial() == m_mesh->GetStaticMesh()->materials[m] )
			{
				found = true;
				break;
			}
		}

		// Add the material if it wasn't found and not set to ignore faces.
		// Добавляем материал в связный список материалов, если он ранее не был найден в списке
		// и у него не стоит опция "игнорировать грани".
		if( found == false && m_mesh->GetStaticMesh()->materials[m]->GetIgnoreFace() == false )
			m_renderCaches->Add( new RenderCache( g_engine->GetDevice(), m_mesh->GetStaticMesh()->materials[m] ) );
	}

	// Get a pointer to the mesh's frame list.
	// Получаем указатель на список фреймов меша.
	LinkedList< Frame > *frames = m_mesh->GetFrameList();

	// Iterate through the frame list.
	// Итерируем через связный список фреймов.
	frames->Iterate( true );
	while( frames->Iterate() != NULL )
	{
		// Check if this frame contains an occluder.
		// Проверяем, содержит ли данный фрейм оклюдер (объект, перекрывающий другие объекты).
		if( strncmp( "oc_", frames->GetCurrent()->Name, 3 ) == 0 )
		{
			// If so, load the occluder, and continue to the next frame.
			// Если да, то загружаем оклюдер и переходим к следующему кадру.
			m_occludingObjects->Add( new SceneOccluder( frames->GetCurrent()->GetTranslation(),
				( (MeshContainer*)frames->GetCurrent()->pMeshContainer )->originalMesh,
				&frames->GetCurrent()->finalTransformationMatrix ) );
			continue;
		}

		// Check if this frame is a spawn point.
		// Проверяем, является ли данный фрейм точкой спауна.
		if( strncmp( "sp_", frames->GetCurrent()->Name, 3 ) == 0 )
		{
			// Get the actual name of the spawner object at this spawn point.
			// Получаем актуальное имя спавнер-объекта в данной точке.
			char *firstDash = strpbrk( frames->GetCurrent()->Name, "_" );
			firstDash++;
			char *lastDash = strrchr( firstDash, '_' );
			unsigned long length = lastDash - firstDash;
			char *name = new char[length + 5];
			ZeroMemory( name, sizeof( char ) * ( length + 5 ) );
			strncpy( name, firstDash, length );
			strcat( name, ".txt" );

			// Check if it is a player spawn point.
			// Проверяем, содержит ли фрейм точку спауна игрока.
			if( _stricmp( name, "player.txt" ) == 0 )
			{
				// Get the name of the player spawn point's radius frame.
				// Получаем имя фрейма спаун-радиуса точки спауна игрока.
				char *radiusName = new char[strlen( firstDash ) + 8];
				ZeroMemory( radiusName, sizeof( char ) * ( strlen( firstDash ) + 8 ) );
				strncpy( radiusName, firstDash, strlen( firstDash ) );
				strcat( radiusName, "_radius" );

				// Find the player spawn point's radius frame.
				// Ищем спаун-радиус точки спауна игрока.
				Frame *radiusFrame = frames->GetFirst();
				while( radiusFrame != NULL )
				{
					if( _stricmp( radiusFrame->Name, radiusName ) == 0 )
						break;

					radiusFrame = frames->GetNext( radiusFrame );
				}

				// Destroy the string buffer for the radius frame's name.
				// Уничтожаем строковый буфер, содержащий имя фрейма спаун-радиуса.
				SAFE_DELETE_ARRAY( radiusName );

				// Find the distance between the two points (the radius).
				// Находим расстояние между двумя точками (=радиус).
				float radius = 0.0f;
				if( radiusFrame != NULL )
					radius = D3DXVec3Length( &( radiusFrame->GetTranslation() - frames->GetCurrent()->GetTranslation() ) );

				// Create the player spawn point.
				// Создаём точку спауна игрока.
				SceneObject *point = new SceneObject( NULL, NULL );
				point->SetTranslation( frames->GetCurrent()->GetTranslation() );
				point->SetBoundingSphere( D3DXVECTOR3( 0.0f, 0.0f, 0.0f ), radius );
				point->SetVisible( false );
				point->SetGhost( true );
				point->Update( 0.0f );
				m_dynamicObjects->Add( m_playerSpawnPoints->Add( point ) );
			}
			else
			{
				// Create the application specific spawner object.
				// Создаём спаунер-объект, специфичный для приложения.
				SpawnerObject *spawner = new SpawnerObject( name, m_spawnerPath );
				spawner->SetTranslation( frames->GetCurrent()->GetTranslation() );
				spawner->Update( 0.0f );
				m_dynamicObjects->Add( m_objectSpawners->Add( spawner ) );
			}

			// Destroy the string buffer used to create the spawner's name.
			// Уничтожаем строковый буфер, содержащий имя спаун-объекта.
			SAFE_DELETE_ARRAY( name );
		}
	}

	// A list of valid faces (those with a valid material).
	// Список валидных (= допущенных к рендерингу) граней (т.е. те, которые имеют валидные материалы)
	bool *validFaces = new bool[m_mesh->GetStaticMesh()->originalMesh->GetNumFaces()];
	ZeroMemory( validFaces, sizeof( bool ) * m_mesh->GetStaticMesh()->originalMesh->GetNumFaces() );

	// These are used for locking the vertex, index, and attribute buffers of
	// the meshes. They act as pointers into the data returned by the locks.
	// Эти переменные применяются для блокировки вершин, индексов и буферов атрибутов мешей.
	// Они выступают в роли указателей, куда будут передаваться данные для блокировки.
	Vertex *vertices = NULL;
	unsigned short *indices = NULL;
	unsigned long *attributes = NULL;

	// Lock the mesh's vertex, index, and attribute buffers.
	// Лочим все 3 буфера.
	m_mesh->GetStaticMesh()->originalMesh->LockVertexBuffer( D3DLOCK_READONLY, (void**)&vertices );
	m_mesh->GetStaticMesh()->originalMesh->LockIndexBuffer( D3DLOCK_READONLY, (void**)&indices );
	m_mesh->GetStaticMesh()->originalMesh->LockAttributeBuffer( D3DLOCK_READONLY, &attributes );

	// Count the faces in the scene that have a valid material.
	// Подсчитываем число граней сцены с валидными материалами.
	for( unsigned long f = 0; f < m_mesh->GetStaticMesh()->originalMesh->GetNumFaces(); f++ )
	{
		m_renderCaches->Iterate( true );
		while( m_renderCaches->Iterate() )
		{
			if( m_renderCaches->GetCurrent()->GetMaterial() == m_mesh->GetStaticMesh()->materials[attributes[f]] )
			{
				m_totalFaces++;
				validFaces[f] = true;
				break;
			}
		}
	}

	// Create the array of faces.
	// Создаём массив граней.
	m_faces = new SceneFace[m_totalFaces];

	// Set the number of vertices.
	// Считаем общее кол-во вершин сцены.
	m_totalVertices = m_totalFaces * 3;

	// Create the vertex buffer that will hold all the vertices in the scene.
	// Создаём вершинный буфер, в котором будут храниться все вершины сцены.
	g_engine->GetDevice()->CreateVertexBuffer( m_totalVertices * VERTEX_FVF_SIZE,
		D3DUSAGE_WRITEONLY, VERTEX_FVF, D3DPOOL_MANAGED, &m_sceneVertexBuffer, NULL );

	// Used for temporary storage of the final vertices that make the scene.
	// Применяем временное хранилище для конечного набора вершин, формирующих сцену.
	Vertex *tempVertices = new Vertex[m_totalVertices];

	// Lock the scene's vertex buffer
	// Лочим (=блокируем) вершинный буфер) сцены.
	m_sceneVertexBuffer->Lock( 0, 0, (void**)&m_vertices, 0 );

	// Go through all of the valid faces in the mesh and store their details.
	// Итерируем через все валидные грани меша и сохраняем их детали.
	for( unsigned long f = 0; f < m_totalFaces; f++ )
	{
		// Ensure this face is valid.
		// Проверяем, валидна ли грань.
		if( validFaces[f] == false )
		{
			// Advance the indices pointer to skip this face.
			// Увеличиваем число индексов, припустив данную грань.
			indices += 3;
			continue;
		}

		// Store the index pointer for each vertex in the face.
		// Инкрементируем кол-во указателей на каждый из индексов после размещения
		// в индексном буфере каждой вершины
		m_faces[f].vertex0 = *indices++;
		m_faces[f].vertex1 = *indices++;
		m_faces[f].vertex2 = *indices++;

		// Find the render cache this face belongs to.
		// Находим рендер-кэш, которому принадлежит данная грань.
		m_renderCaches->Iterate( true );
		while( m_renderCaches->Iterate() )
		{
			if( m_renderCaches->GetCurrent()->GetMaterial() == m_mesh->GetStaticMesh()->materials[attributes[f]] )
			{
				m_faces[f].renderCache = m_renderCaches->GetCurrent();
				m_renderCaches->GetCurrent()->AddFace();
				break;
			}
		}

		// Take of temporary copy of these vertices.
		// Делаем временную копию этих вершин.
		tempVertices[m_faces[f].vertex0] = vertices[m_faces[f].vertex0];
		tempVertices[m_faces[f].vertex1] = vertices[m_faces[f].vertex1];
		tempVertices[m_faces[f].vertex2] = vertices[m_faces[f].vertex2];
	}

	// Copy the final vertices (that make up the scene) into the vertex buffer.
	// Копируем конечный список вершин (которые сформируют сцену) в вершинный буфер.
	memcpy( m_vertices, tempVertices, m_totalVertices * VERTEX_FVF_SIZE );

	// Unlock the scene's vertex buffer.
	// Разблокируем вершинный буфер сцены.
	m_sceneVertexBuffer->Unlock();

	// Destroy the temporary vertices array.
	// Уничтожаем временный массив вершин.
	SAFE_DELETE_ARRAY( tempVertices );

	// Unlock the mesh's vertex, index, and attribute buffers.
	// Разблокируем все 3 буфера.
	m_mesh->GetStaticMesh()->originalMesh->UnlockAttributeBuffer();
	m_mesh->GetStaticMesh()->originalMesh->UnlockIndexBuffer();
	m_mesh->GetStaticMesh()->originalMesh->UnlockVertexBuffer();

	// Destroy the array of valid faces.
	// Уничтожаем массив валидных граней.
	SAFE_DELETE_ARRAY( validFaces );

	// Create the first scene leaf (the largest leaf that encloses the scene).
	// Создаём первый лист октодерева (самый большой, заключающий в себе всю сцену целиком).
	m_firstLeaf = new SceneLeaf();

	// Recursively build the scene, starting with the first leaf.
	// Рекурсивно строим сцену, начиная с первого листа октодерева.
	RecursiveSceneBuild( m_firstLeaf, m_mesh->GetBoundingSphere()->centre, m_mesh->GetBoundingBox()->halfSize );

	// Allow the render caches to prepare themselves.
	// Готовим рендер-кэши.
	m_renderCaches->Iterate( true );
	while( m_renderCaches->Iterate() )
		m_renderCaches->GetCurrent()->Prepare( m_totalVertices );

	// Indicate that the scene is now loaded.
	// Ставим отметку о том, что сцена загружена.
	m_loaded = true;
}

//-----------------------------------------------------------------------------
// Destroys the currently loaded scene.
// Уничтожает ранее загруженную сцену.
//-----------------------------------------------------------------------------
void SceneManager::DestroyScene()
{
	// Destroy the array of polygons.
	// Уничтожаем массив полигонов (=граней).
	SAFE_DELETE_ARRAY( m_faces );
	m_totalFaces = 0;

	// Destroy the list of render caches.
	// Уничтожаем список рендер-кэшей.
	SAFE_DELETE( m_renderCaches );

	// Release the scene's vertex buffer.
	// Освобождаем память вершинного буфера сцены.
	SAFE_RELEASE( m_sceneVertexBuffer );
	m_vertices = NULL;
	m_totalVertices = 0;

	// Destroy the scene leaf hierarchy.
	// Уничтожаем иерархию октодерева сцены.
	SAFE_DELETE( m_firstLeaf );

	// Destroy the object spawner list.
	if( m_objectSpawners != NULL )
		m_objectSpawners->ClearPointers();
	SAFE_DELETE( m_objectSpawners );

	// Destroy the list of player spawn points.
	// Уничтожаем список объектов-спавунеров.
	if( m_playerSpawnPoints != NULL )
		m_playerSpawnPoints->ClearPointers();
	SAFE_DELETE( m_playerSpawnPoints );

	// Destroy the lists of occluding objects.
	// Уничтожаем список оклюдерюв.
	if( m_visibleOccluders != NULL )
		m_visibleOccluders->ClearPointers();
	SAFE_DELETE( m_visibleOccluders );
	SAFE_DELETE( m_occludingObjects );

	// Empty the list of dynamic objects.
	// Уничтожаем спсисок динамических объектов.
	m_dynamicObjects->Empty();

	// Destroy the scene's mesh.
	// Уничтожаем меш сцены.
	g_engine->GetMeshManager()->Remove( &m_mesh );

	// Destroy the scene name.
	// Уничтожаем имя сцены.
	SAFE_DELETE_ARRAY( m_name );

	// Indicate that the scene is no longer loaded.
	// Сигналим, о том что сцена более не загружена.
	m_loaded = false;
}

//-----------------------------------------------------------------------------
// Returns true if the scene is loaded and ready for use.
// Возвращает TRUE, если сцена загружена и готова к использованию.
//-----------------------------------------------------------------------------
bool SceneManager::IsLoaded()
{
	return m_loaded;
}

//-----------------------------------------------------------------------------
// Updates the scene and all the objects in it.
// Обновляет сцену и все объекты на ней.
//-----------------------------------------------------------------------------
void SceneManager::Update( float elapsed, D3DXMATRIX *view )
{
	// Ensure a scene is loaded.
	// Убеждаемся, что сцена загружена.
	if( m_firstLeaf == NULL )
		return;

	// Increment the frame stamp. Indicating the start of a new frame.
	// Инкрементируем (увеличиваем на 1) штамп фрейма.
	m_frameStamp++;

	// Update the view frustum.
	// Обновляем усечённую пирамиду вида.
	m_viewFrustum.Update( view );

	// Go through all the dynamic object's and update them.
	// Итерируем все динамические объекты и обновляем их.
	m_dynamicObjects->Iterate( true );
	while( m_dynamicObjects->Iterate() )
	{
		// Ignore the object if it is not enabled.
		// Игнорируем отключенные объекты.
		if( m_dynamicObjects->GetCurrent()->GetEnabled() == false )
			continue;

		// If this object is a ghost, then it cannot collided with anything.
		// However, it still needs to be updated. Since objects receive their
		// movement through the collision system, ghost objects will have to be
		// allowed to update their movement manually.
		// Если объект является призраком, то он не может сталкиваться с чем-либо.
		// Но в любом случае он тоже должен быть обновлён.
		// В свете того, что объекты получают своё движение через систему столкновений,
		// объекты-призраки должны быть допущены к обновлению своих положений вручную.
		if( m_dynamicObjects->GetCurrent()->GetGhost() == true )
		{
			m_dynamicObjects->GetCurrent()->Update( elapsed );
			continue;
		}

		// Objects without an ellipsoid radius cannot collide with anything.
		// Объекты без радиуса эллипсоида не могут сталкиваться с чем-либо.
		if( m_dynamicObjects->GetCurrent()->GetEllipsoidRadius().x + m_dynamicObjects->GetCurrent()->GetEllipsoidRadius().y,
			m_dynamicObjects->GetCurrent()->GetEllipsoidRadius().z <= 0.0f )
		{
			m_dynamicObjects->GetCurrent()->Update( elapsed );
			continue;
		}

		// Build the collision data for this object.
		// Заполняем данные столкновения по данном объекту.
		static CollisionData collisionData;
		collisionData.scale = m_scale;
		collisionData.elapsed = elapsed;
		collisionData.frameStamp = m_frameStamp;
		collisionData.object = m_dynamicObjects->GetCurrent();
		collisionData.gravity = m_gravity * elapsed;

		// Perform collision detection for this object.
		// Выполняем определение столкновения для данного объекта.
		PerformCollisionDetection( &collisionData, (Vertex*)m_vertices, m_faces, m_totalFaces, m_dynamicObjects );

		// Allow the object to update itself.
		// Позволяем объекту обновить самого себя.
		m_dynamicObjects->GetCurrent()->Update( elapsed, false );
	}
}

//-----------------------------------------------------------------------------
// Renders the scene and all the objects in it.
// Рендерпт сцену и все объекты на ней.
//-----------------------------------------------------------------------------
void SceneManager::Render( float elapsed, D3DXVECTOR3 viewer )
{
	// Ensure a scene is loaded.
	// Убеждаемся, что сцена загружена.
	if( m_firstLeaf == NULL )
		return;

	// Clear the list of visible occluders.
	// Очищаем список видимых оклюдеров.
	m_visibleOccluders->ClearPointers();

	// Begin the process of determining the visible leaves in the scene. The
	// first step involves checking the scene leaves against the view frustum.
	// Начинаем процесс определения видимых листьев октодерева сцены.
	// Первым делом проверяем листья, расположенные напротив усечённой пирамиды вида.
	RecursiveSceneFrustumCheck( m_firstLeaf, viewer );

	// A list of potentially visible leaves and occluders has been determined
	// after check against the view frustum. The next step is to go through and
	// further refine the list of visible occluders through occlusion culling.
	// Далее итерируем список видимых оклюдеров для определения отсечений объектов,
	// заслонённых ими.
	m_visibleOccluders->Iterate( true );
	while( m_visibleOccluders->Iterate() )
	{
		// If the occluder's visible stamp does not not equal the current frame
		// stamp then the occluder has been hidden somehow, so ignore it.
		// Если штамп видимости оклюдера не соответствует штампу текущего фрейма,
		// значит этот оклюдер спрятан. Поэтому игнорируем его.
		if( m_visibleOccluders->GetCurrent()->visibleStamp != m_frameStamp )
			continue;

		// Build the occluder's occlusion volume.
		// Создаем ограничивающий объём вокруг оклюдера.
		BuildOcclusionVolume( m_visibleOccluders->GetCurrent(), viewer );

		// Iterate through the rest of the visible occluder's.
		// Итерируем оставшиеся видимые оклюдеры.
		SceneOccluder *occludee = m_visibleOccluders->GetNext( m_visibleOccluders->GetCurrent() );
		while( occludee != NULL )
		{
			// If the occludee's bounding sphere is overlapping the occluder's
			// volume and the occludee's bounding box is completely enclosed by
			// the occluder's volume, then the occludee is hidden.
			// Если ограничивающая сфера заслоняемого объекта перекрывает
			// ограничивающий объём оклюдера, а ограничивающий куб заслоняемого объекта
			// полностью заключён внутри огарипчивающего объёма оклюдера (лучи, касающиеся
			// краёв оклюдера уходят бесконечно вдаль), то заслоняемый объект не виден
			// наблюдателю. => Его можно не рендерпть.
			if( IsSphereOverlappingVolume( m_visibleOccluders->GetCurrent()->planes,
				occludee->translation,
				occludee->GetBoundingSphere()->radius ) == true )
				if( IsBoxEnclosedByVolume( m_visibleOccluders->GetCurrent()->planes,
					occludee->GetBoundingBox()->min,
					occludee->GetBoundingBox()->max ) == true )
					occludee->visibleStamp--;

			occludee = m_visibleOccluders->GetNext( occludee );
		}
	}

	// Tell all the render caches to prepare for rendering.
	// Командуем всем рендер-кэшам приготовиться к рендерингу.
	m_renderCaches->Iterate( true );
	while( m_renderCaches->Iterate() )
		m_renderCaches->GetCurrent()->Begin();

	// Finally, check the scene's leaves against the visible occluders.
	// Проверяем листья октодерева сцены на предмет заслонённости оклюдерами.
	RecursiveSceneOcclusionCheck( m_firstLeaf );

	// Set an identity world transformation matrix to render around the origin.
	// Устанавливаем мировую матрицу идентичности для рендеринга относительно
	// начала координат.
	D3DXMATRIX world;
	D3DXMatrixIdentity( &world );
	g_engine->GetDevice()->SetTransform( D3DTS_WORLD, &world );

	// Set the scene vertex buffer as the current device data stream.
	// Назначаем вершинный буфер сцены в качестве потока данных объекта устройства Direct3D.
	g_engine->GetDevice()->SetStreamSource( 0, m_sceneVertexBuffer, 0, VERTEX_FVF_SIZE );
	g_engine->GetDevice()->SetFVF( VERTEX_FVF );

	// Tell all the render caches to end rendering. This will cause them to
	// send their faces to be render to the video card.
	// Командуем всем рендер-кэшам заканчивать рендеринг. Это приведёт к отправке ими всех
	// граней в видеокарту, на рендеринг.
	m_renderCaches->Iterate( true );
	while( m_renderCaches->Iterate() )
		m_renderCaches->GetCurrent()->End();

	// Iterate through the list of dynamic objects.
	// Итерируем через список динамических объектов.
	m_dynamicObjects->Iterate( true );
	while( m_dynamicObjects->Iterate() )
	{
		// Check if the object is visible.
		// Проверяем, видим ли объект.
		if( m_dynamicObjects->GetCurrent()->GetVisible() == false )
			continue;

		// Check if the object's bounding sphere is inside the view frustum.
		// Проверяем, расположена ли ограничивающая сфера объекта внутри
		// усечённой пирамиды вида.
		if( m_viewFrustum.IsSphereInside( m_dynamicObjects->GetCurrent()->GetBoundingSphere()->centre,
			m_dynamicObjects->GetCurrent()->GetBoundingSphere()->radius ) == false )
			continue;

		// Iterate through the list of visible occluders.
		// Итерируем список видимых оклюдеров.
		bool occluded = false;
		m_visibleOccluders->Iterate( true );
		while( m_visibleOccluders->Iterate() )
		{
			// Ignore hidden occluders.
			// Игнориуем спрятанные оклюдеры.
			if( m_visibleOccluders->GetCurrent()->visibleStamp != m_frameStamp )
				continue;

			occluded = true;

			// Check the object's bounding sphere against the occlusion volume.
			// Проверяем ограничивающую сферу объекта на предмет попадания внутрь
			// перекрывающего объёма.
			m_visibleOccluders->GetCurrent()->planes->Iterate( true );
			while( m_visibleOccluders->GetCurrent()->planes->Iterate() )
			{
				if( D3DXPlaneDotCoord( m_visibleOccluders->GetCurrent()->planes->GetCurrent(),
					&m_dynamicObjects->GetCurrent()->GetBoundingSphere()->centre )
					< m_dynamicObjects->GetCurrent()->GetBoundingSphere()->radius )
				{
					occluded = false;
					break;
				}
			}

			// Break if the object is completely hidden by this occluder.
			// Прерываем, если объект полностью заслонён данным оклюдером.
			if( occluded == true )
				break;
		}

		// Ignore this object if it is occluded.
		// Игнорируем полностью заслонённый объект и продолжаем итерацию дальше.
		if( occluded == true )
			continue;

		// Render the object.
		// Рендерпм объект.
		m_dynamicObjects->GetCurrent()->Render();
	}
}

//-----------------------------------------------------------------------------
// Adds the given object to the scene.
// Добавляет данный объект в сцену.
//-----------------------------------------------------------------------------
SceneObject *SceneManager::AddObject( SceneObject *object )
{
	return m_dynamicObjects->Add( object );
}

//-----------------------------------------------------------------------------
// Removes the given object from the scene.
// Убирает данный объект из сцены.
//-----------------------------------------------------------------------------
void SceneManager::RemoveObject( SceneObject **object )
{
	m_dynamicObjects->ClearPointer( object );
}

//-----------------------------------------------------------------------------
// Returns a random player spawnpoint.
// Возвращает случайным образом одну из точек спауна игрока.
//-----------------------------------------------------------------------------
SceneObject *SceneManager::GetRandomPlayerSpawnPoint()
{
	// Get a random spawn point.
	// Получаем случайную точку спауна игрока.
	SceneObject *point = m_playerSpawnPoints->GetRandom();

	// If the spawner's collision stamp equals the current frame stamp, then
	// something has collided with the spawner. Alternatively this spawner may
	// not be enabled. In either case, return NULL to indicate that a vacent
	// spawn point was not found. The caller will have to try again later.
	// Если штамп столкновения спаунера равен штампу текущего кадра, значит
	// что-то столкнулось со спаунером и он не может быть включён.
	// Значение NULL указывает на то, что точка спауна не найдена и нужно поискать её
	// ещё раз.
	if( point->GetCollisionStamp() != m_frameStamp && point->GetEnabled() == true )
		return point;
	else
		return NULL;
}

//-----------------------------------------------------------------------------
// Returns the spawn point with the given ID (position in the linked list).
// Возвращает точку спауна с данным ID) (порядковым номером в связном списке)
//-----------------------------------------------------------------------------
SceneObject *SceneManager::GetSpawnPointByID( long id )
{
	SceneObject *point = NULL;

	// Ensure the ID is in range.
	// Проверяем, входит ли ID в даннй диапазон.
	if( id < (long)m_playerSpawnPoints->GetTotalElements() )
	{
		// Loop through the player spawn point list until the id is reached.
		point = m_playerSpawnPoints->GetFirst();
		for( long i = 0; i < id; i++ )
			point = m_playerSpawnPoints->GetNext( point );
	}

	return point;
}

//-----------------------------------------------------------------------------
// Returns the ID (position in the linked list) of the given spawn point.
// Возвращает ID (позицию в связном списке) данной точки спауна.
//-----------------------------------------------------------------------------
long SceneManager::GetSpawnPointID( SceneObject *point )
{
	// Ensure the given spawn point is valid.
	// Проверяем, валидна ли данная точка спауна.
	if( point == NULL )
		return -1;

	long id = 0;

	// Iterate the player spawn point list looking for the given spawn point.
	// Итерируем список спаун-точек игрока в поисках данной спаун-точки.
	m_playerSpawnPoints->Iterate( true );
	while( m_playerSpawnPoints->Iterate() != NULL )
	{
		if( m_playerSpawnPoints->GetCurrent() == point )
			break;

		id++;
	}

	// If the ID equals the total elements, then the spawn point was not found.
	// Если ID точки равен кол-ву элементов в связном списке, то данная
	// спаун-точка не найдена.
	if( id == (long)m_playerSpawnPoints->GetTotalElements() )
		id = -1;

	return id;
}

//-----------------------------------------------------------------------------
// Returns the list of object spawners in the scene.
// Возвращает список спаун-объектов сцены.
//-----------------------------------------------------------------------------
LinkedList< SpawnerObject > *SceneManager::GetSpawnerObjectList()
{
	return m_objectSpawners;
}

//-----------------------------------------------------------------------------
// Returns the result of a ray intersection with the scene and all its objects.
// Возвращает результат пересечения луча со сценой и всеми её объектами.
//-----------------------------------------------------------------------------
bool SceneManager::RayIntersectScene( RayIntersectionResult *result, D3DXVECTOR3 rayPosition,
	D3DXVECTOR3 rayDirection, bool checkScene, SceneObject *thisObject, bool checkObjects )
{
	float hitDistance = 0.0f;

	// Check if the ray needs to check for intersection with the scene.
	// Проверяем, надо ли проверять луч на пересечение со сценой.
	if( checkScene == true )
	{
		// Go through all the faces in the scene, check for intersection.
		// Проходим через все грани сцены, проверяя на пересечение с лучом.
		for( unsigned long f = 0; f < m_totalFaces; f++ )
		{
			// Skip this face if its material is set to ignore rays.
			// Пропускаем грань, если в скрипте её материала указано игнорировать лучи.
			if( m_faces[f].renderCache->GetMaterial()->GetIgnoreRay() == true )
				continue;

			// Check the ray against this face.
			// Проверяем луч на пересечненпе с данной гранью.
			if( D3DXIntersectTri( (D3DXVECTOR3*)&m_vertices[m_faces[f].vertex0],
				(D3DXVECTOR3*)&m_vertices[m_faces[f].vertex1],
				(D3DXVECTOR3*)&m_vertices[m_faces[f].vertex2],
				&rayPosition, &rayDirection, NULL, NULL, &hitDistance ) == TRUE )
			{
				if( hitDistance < result->distance || result->material == NULL )
				{
					( *result ).distance = hitDistance;
					( *result ).material = m_faces[f].renderCache->GetMaterial();
				}
			}
		}
	}

	// Check if the ray needs to check for intersection with the objects.
	// Проверяем, надо ли проверять луч на пересечение с объектами.
	if( checkObjects == true )
	{
		// Stores the ray in model space.
		// Сохраняем луч в пространстве модели.
		D3DXVECTOR3 rp, rd;

		// Iterate all the objects in the scene, check for intersection.
		// Итерируем все объекты сцены, проверяя на пересечение.
		SceneObject *object = m_dynamicObjects->GetFirst();
		while( object != NULL )
		{
			// Only check this object if it is enabled, has a mesh and is not
			// the calling object.
			// Проверяем только те объекты, которые включены, имеют меш и
			// не являются объектами, спаунящими другие объекты.
			if( object->GetEnabled() == true && object->GetMesh() != NULL && object != thisObject )
			{
				// Transform the ray into model space.
				// Трансформируем луч в пространство модели.
				D3DXMATRIX inverse;
				D3DXMatrixInverse( &inverse, NULL, object->GetWorldMatrix() );
				D3DXVec3TransformCoord( &rp, &rayPosition, &inverse );
				D3DXVec3TransformNormal( &rd, &rayDirection, &inverse );

				// Go through the list of frames in the object's mesh.
				// Проходим через список фреймов меша объекта.
				LinkedList< Frame > *frames = object->GetMesh()->GetFrameList();
				frames->Iterate( true );
				while( frames->Iterate() != NULL )
				{
					// Ignore this frame if it has no mesh.
					// Пропускаем фрейм без меша.
					if( frames->GetCurrent()->pMeshContainer == NULL )
						continue;

					// Check the ray against this frame's mesh.
					// Проверяем луч на пересечение с мешем фрейма.
					BOOL hit;
					D3DXIntersect( frames->GetCurrent()->pMeshContainer->MeshData.pMesh, &rp, &rd,
						&hit, NULL, NULL, NULL, &hitDistance, NULL, NULL );
					if( hit == TRUE && ( hitDistance < result->distance || result->material == NULL ) )
					{
						( *result ).distance = hitDistance;
						( *result ).material = object->GetMesh()->GetStaticMesh()->materials[0];
						( *result ).hitObject = object;
					}
				}
			}

			// Go to the next object.
			// Переходим к следующему объекту.
			object = m_dynamicObjects->GetNext( object );
		}
	}

	// Return false if no intersection occured.
	// Возвращаем FALSE, если пересечение не найдено.
	if( result->material == NULL )
		return false;

	// Calculate the point of intersection.
	// Вычисляем точку пересечения.
	( *result ).point = rayPosition + rayDirection * result->distance;

	return true;
}

//-----------------------------------------------------------------------------
// Builds an occlusion volume for the given occluder.
// Строим перекрывающий объём для данного оклюдера.
//-----------------------------------------------------------------------------
void SceneManager::BuildOcclusionVolume( SceneOccluder *occluder, D3DXVECTOR3 viewer )
{
	// Create a list of edges for the occluder's silhouette.
	// Создаём список рёбер силуэта оклюдера.
	LinkedList< Edge > *edges = new LinkedList< Edge >;

	// Go through all the faces in the occluder's mesh.
	for( unsigned long f = 0; f < occluder->totalFaces; f++ )
	{
		// Get the indices of this face.
		// Получаем индексы вершин грани.
		unsigned short index0 = occluder->indices[3 * f + 0];
		unsigned short index1 = occluder->indices[3 * f + 1];
		unsigned short index2 = occluder->indices[3 * f + 2];

		// Find the angle between the face's normal and the vector point from
		// viewer's position to the face's position. If the angle is less than
		// 0, then the face is visible to the viewer.
		// Вычисляем угол между нормалью грани и вектором, направленным от вьюера
		// к грани. Если данный угол меньше 0, то данная грань вьюеру (=игроку) не видна.
		if( D3DXVec3Dot( &occluder->vertices[index0].normal, &( occluder->vertices[index0].translation - viewer ) ) < 0.0f )
		{
			// Check if the list of edges is empty.
			// Если список граней пуст...
			if( edges->GetTotalElements() == 0 )
			{
				// Add all the edges for this face.
				// Добавляем в список 3 ребра данной грани.
				edges->Add( new Edge( &occluder->vertices[index0], &occluder->vertices[index1] ) );
				edges->Add( new Edge( &occluder->vertices[index1], &occluder->vertices[index2] ) );
				edges->Add( new Edge( &occluder->vertices[index2], &occluder->vertices[index0] ) );
			}
			else
			{
				Edge *found0 = NULL;
				Edge *found1 = NULL;
				Edge *found2 = NULL;

				// Iterate through the list of edges.
				// Итерируем список рёбер.
				edges->Iterate( true );
				while( edges->Iterate() != NULL )
				{
					// Check if the first edge of this face already exists.
					// Проверяем случай, когда первое ребро данной грани уже существует.
					if( ( edges->GetCurrent()->vertex0->translation == occluder->vertices[index0].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index1].translation ) ||
						( edges->GetCurrent()->vertex0->translation == occluder->vertices[index1].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index0].translation ) )
						found0 = edges->GetCurrent();

					// Check if the second edge of this face already exists.
					// Проверяем случай, когда второе ребро данной грани уже существует.
					if( ( edges->GetCurrent()->vertex0->translation == occluder->vertices[index1].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index2].translation ) ||
						( edges->GetCurrent()->vertex0->translation == occluder->vertices[index2].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index1].translation ) )
						found1 = edges->GetCurrent();

					// Check if the third edge of this face already exists.
					// Проверяем случай, когда третье ребро данной грани уже существует.
					if( ( edges->GetCurrent()->vertex0->translation == occluder->vertices[index2].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index0].translation ) ||
						( edges->GetCurrent()->vertex0->translation == occluder->vertices[index0].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index2].translation ) )
						found2 = edges->GetCurrent();
				}

				// If the first edge was found, remove it. Otherwise add it.
				// Если первое ребро найдено, удалим его. В противном случае - добавим в список рёбер.
				if( found0 != NULL )
					edges->Remove( &found0 );
				else
					edges->Add( new Edge( &occluder->vertices[index0], &occluder->vertices[index1] ) );

				// If the second edge was found, remove it. Otherwise add it.
				// Если второе ребро найдено, удалим его. В противном случае - добавим в список рёбер.
				if( found1 != NULL )
					edges->Remove( &found1 );
				else
					edges->Add( new Edge( &occluder->vertices[index1], &occluder->vertices[index2] ) );

				// If the thrid edge was found, remove it. Otherwise add it.
				// Если третье ребро найдено, удалим его. В противном случае - добавим в список рёбер.
				if( found2 != NULL )
					edges->Remove( &found2 );
				else
					edges->Add( new Edge( &occluder->vertices[index2], &occluder->vertices[index0] ) );
			}
		}
	}

	// Empty the occluder's list of planes.
	// Опустошаем список плоскостей оклюдера.
	occluder->planes->Empty();

	// Create the front cap plane.
	// Создаём плоскость верхнего сечения. 
	D3DXPLANE *plane = new D3DXPLANE;
	D3DXPlaneFromPointNormal( plane, &occluder->translation, &( occluder->translation - viewer ) );
	occluder->planes->Add( plane );

	// Iterate through the list of edges.
	// Итерируем список рёбер. 
	edges->Iterate( true );
	while( edges->Iterate() != NULL )
	{
		// Get the position of the vertices in the edge.
		// Получаем позицию вершин ребра.
		D3DXVECTOR3 vertex1 = edges->GetCurrent()->vertex0->translation;
		D3DXVECTOR3 vertex2 = edges->GetCurrent()->vertex1->translation;

		// Calculate the position of the thrid vertex for creating the plane.
		// Вычисляем положение третьей вершины для создания плоскости.
		D3DXVECTOR3 dir = vertex1 - viewer;
		D3DXVec3Normalize( &dir, &dir );
		D3DXVECTOR3 vertex3 = vertex1 + dir;

		// Create a plane from this edge.
		// Создаём плоскость на основе данной грани.
		plane = new D3DXPLANE;
		D3DXPlaneFromPoints( plane, &vertex1, &vertex2, &vertex3 );
		occluder->planes->Add( plane );
	}

	// Destroy the list of edges.
	// Уничтожаем список рёбер.
	SAFE_DELETE( edges );
}

//-----------------------------------------------------------------------------
// Recursively builds the scene.
// Рекурсивно строим сцену.
//-----------------------------------------------------------------------------
void SceneManager::RecursiveSceneBuild( SceneLeaf *leaf, D3DXVECTOR3 translation, float halfSize )
{
	// Build a bounding volume around this leaf.
	// Строим ограничивающие объёмы вокруг данного листа октодерева.
	leaf->SetBoundingBox( D3DXVECTOR3( translation.x - halfSize, translation.y - halfSize, translation.z - halfSize ),
		D3DXVECTOR3( translation.x + halfSize, translation.y + halfSize, translation.z + halfSize ) );
	leaf->SetBoundingSphere( translation, (float)sqrt( halfSize * halfSize + halfSize * halfSize + halfSize * halfSize ) );

	// Count the number of face in this leaf.
	// Считаем число граней в данном листе.
	unsigned long totalFaces = 0;
	for( unsigned long f = 0; f < m_totalFaces; f++ )
		if( IsFaceInBox( &m_vertices[m_faces[f].vertex0], &m_vertices[m_faces[f].vertex1],
			&m_vertices[m_faces[f].vertex2], leaf->GetBoundingBox()->min, leaf->GetBoundingBox()->max ) == true )
			totalFaces++;

	// Only divide the leaf up if it is too big and contains too many faces.
	// Делим лист только если он чересчур большой и содержит слишком много граней.
	if( halfSize > m_maxHalfSize && totalFaces > m_maxFaces )
	{
		// Go through all the child leaves.
		for( char c = 0; c < 8; c++ )
		{
			D3DXVECTOR3 newTranslation, newMin, newMax;
			float newHalfSize = halfSize / 2.0f;
			float mod;

			// Calculate the translation of the new leaf on the x axis.
			// Вычисляем трансляцию нового листа по оси х.
			mod = 1.0f;
			if( c % 2 < 1 )
				mod = -1.0f;
			newTranslation.x = translation.x + newHalfSize * mod;

			// Calculate the translation of the new leaf on the y axis.
			// Вычисляем трансляцию нового листа по оси y.
			mod = 1.0f;
			if( c % 4 < 2 )
				mod = -1.0f;
			newTranslation.y = translation.y + newHalfSize * mod;

			// Calculate the translation of the new leaf on the z axis.
			// Вычисляем трансляцию нового листа по оси z.
			mod = 1.0f;
			if( c % 8 < 4 )
				mod = -1.0f;
			newTranslation.z = translation.z + newHalfSize * mod;

			// Calculate the bounding box around the new leaf.
			// Подсчитываем размер ограничивающего объёма нового листа.
			newMin = D3DXVECTOR3( newTranslation.x - newHalfSize, newTranslation.y - newHalfSize,
				newTranslation.z - newHalfSize );
			newMax = D3DXVECTOR3( newTranslation.x + newHalfSize, newTranslation.y + newHalfSize,
				newTranslation.z + newHalfSize );

			// Check if the new scene leaf will have at least one face in it.
			// Проверяем, содержит ли новый лист хотя бы одну грань.
			for( unsigned long f = 0; f < m_totalFaces; f++ )
			{
				if( IsFaceInBox( &m_vertices[m_faces[f].vertex0], &m_vertices[m_faces[f].vertex1],
					&m_vertices[m_faces[f].vertex2], newMin, newMax ) == true )
				{
					// A face has been found that is inside the new child scene
					// leaf, so create the scene leaf. Then recurse through the
					// scene leaf's branch of the scene hierarchy.
					// В случае, когда грань/грани найдена внутри нового листа,
					// создаём его (лист). Затем рекурсивно проходим через
					// другие листья сцены, расположенные ниже по иерархии.
					leaf->children[c] = new SceneLeaf;
					RecursiveSceneBuild( leaf->children[c], newTranslation, halfSize / 2.0f );

					break;
				}
			}
		}

		return;
	}

	// Create the leaf's array of face indices.
	// Создаём массив индексов вершин граней листа.
	leaf->totalFaces = totalFaces;
	leaf->faces = new unsigned long[totalFaces];
	// If any face is contained in the leaf's bounding box, then store
	// the index of the face in the leaf's face index array.
	// Если грань расположена внутри ограничивающего бокса листа,
	// сохраняем индекс этой грани в массиве индексов вершин граней листа.
	totalFaces = 0;
	for( unsigned long f = 0; f < m_totalFaces; f++ )
		if( IsFaceInBox( &m_vertices[m_faces[f].vertex0], &m_vertices[m_faces[f].vertex1],
			&m_vertices[m_faces[f].vertex2], leaf->GetBoundingBox()->min, leaf->GetBoundingBox()->max ) == true )
			leaf->faces[totalFaces++] = f;

	// Store pointers to any occluding objects in the leaf.
	// Сохраняем указатели на любые перекрываемые объекты листа.
	m_occludingObjects->Iterate( true );
	while( m_occludingObjects->Iterate() )
		if( IsBoxInBox( m_occludingObjects->GetCurrent()->GetBoundingBox()->min,
			m_occludingObjects->GetCurrent()->GetBoundingBox()->max, leaf->GetBoundingBox()->min,
			leaf->GetBoundingBox()->max ) == true )
			leaf->occluders->Add( m_occludingObjects->GetCurrent() );
}

//-----------------------------------------------------------------------------
// Recursively checks the scene's leaves against the view frustum.
// Рекурсивно проверяет листья сцены относительно усечённой пирамиды вида.
//-----------------------------------------------------------------------------
bool SceneManager::RecursiveSceneFrustumCheck( SceneLeaf *leaf, D3DXVECTOR3 viewer )
{
	// Check if the leaf's bounding sphere is inside the view frustum.
	// Проверяем случай, когда ограничивающая сфера листа расположена внутри
	// усечённой пирамиды вида.
	if( m_viewFrustum.IsSphereInside( leaf->GetBoundingSphere()->centre,
		leaf->GetBoundingSphere()->radius ) == false )
		return false;

	// Check if the leaf's bounding box is inside the view frustum.
	// Проверяем случай, когда ограничивающий бокс листа расположен внутри
	// усечённой пирамиды вида.
	if( m_viewFrustum.IsBoxInside( leaf->GetBoundingBox()->min,
		leaf->GetBoundingBox()->max ) == false )
		return false;

	// Set the visible stamp on this leaf to the current frame stamp. This will
	// indicate that the leaf may be visible this frame and may need rendering.
	// Присваиваем штамп видимости данного листа штампу текущего кадра.
	// Это будет сигналом, что данный лист виден в текущем кадре и (возможно)
	// будет рендерится.
	leaf->visibleStamp = m_frameStamp;

	// Check if any of this leaf's children are visible.
	// Проверяем, видимы ли все дочерние листья (=потомки) данного листа.
	char visibleChildren = 0;
	for( char c = 0; c < 8; c++ )
		if( leaf->children[c] != NULL )
			if( RecursiveSceneFrustumCheck( leaf->children[c], viewer ) )
				visibleChildren++;

	// If this leaf has visible children then this branch of the scene can go
	// deeper. So ignore this leaf.
	// Если данный лист имеет видимые потомки, то можно спуститься ниже
	// по иерархии. В этом случае игнорируем его.
	if( visibleChildren > 0 )
		return false;

	// Iterate through all the occluders in this leaf.
	// Итерируем все оклюдеры данного листа.
	leaf->occluders->Iterate( true );
	while( leaf->occluders->Iterate() )
	{
		// Check if the occluder's bounding sphere is inside the view frustum.
		// Проверяем случай, когда ограничивающая сфера оклюдера расположена
		// внутри усечённой пирамиды вида.
		if( m_viewFrustum.IsSphereInside( leaf->occluders->GetCurrent()->translation,
			leaf->occluders->GetCurrent()->GetBoundingSphere()->radius ) == false )
			continue;

		// Check if the occluder's bounding box is inside the view frustum.
		// Проверяем случай, когда ограничивающий куб оклюдера расположен
		// внутри усечённой пирамиды вида.
		if( m_viewFrustum.IsBoxInside( leaf->occluders->GetCurrent()->GetBoundingBox()->min,
			leaf->occluders->GetCurrent()->GetBoundingBox()->max ) == false )
			continue;

		// Calculate the distance between the occluder and the viewer.
		// Вычисляем расстояние между оклюдером и вьюером.
		leaf->occluders->GetCurrent()->distance = D3DXVec3Length( &( leaf->occluders->GetCurrent()->translation - viewer ) );

		// Iterate through the list of visible occluders.
		// Итерируем список видимых оклюдеров.
		m_visibleOccluders->Iterate( true );
		while( m_visibleOccluders->Iterate() )
		{
			// If the new occluder is already in the list, don't add it agian.
			// Если новый оклюдер уже в списке, не надо его снова добавлять.
			if( leaf->occluders->GetCurrent() == m_visibleOccluders->GetCurrent() )
				break;

			// If the new occluder is closer to the viewer than this occluder,
			// then add it to the list before this occluder.
			// Если новый оклюдер расположен к вьюеру ближе, чем текущий оклюдер,
			// то добавляем его в список ДО данного оклюдера.
			if( leaf->occluders->GetCurrent()->distance < m_visibleOccluders->GetCurrent()->distance )
			{
				m_visibleOccluders->InsertBefore( leaf->occluders->GetCurrent(),
					m_visibleOccluders->GetCompleteElement( m_visibleOccluders->GetCurrent() ) );
				leaf->occluders->GetCurrent()->visibleStamp = m_frameStamp;
				break;
			}
		}

		// If the occluder wasn't in the list or not added then add it now.
		// Если оклюдер не был добавлен в список, то сделаем это сейчас.
		if( leaf->occluders->GetCurrent()->visibleStamp != m_frameStamp )
		{
			m_visibleOccluders->Add( leaf->occluders->GetCurrent() );
			leaf->occluders->GetCurrent()->visibleStamp = m_frameStamp;
		}
	}

	return true;
}

//-----------------------------------------------------------------------------
// Recursively checks the scene's leaves against the occlusion volumes.
// Рекурсивно проверяем положение листьев сцены относительно перекрывающих объёмов.
//-----------------------------------------------------------------------------
void SceneManager::RecursiveSceneOcclusionCheck( SceneLeaf *leaf )
{
	// Ignore the leaf if it is not visible this frame.
	// Пропускаем лист, если он не видим в данном кадре.
	if( leaf->visibleStamp != m_frameStamp )
		return;

	// Iterate through the list of visible occluders.
	// Итерируем список видимых оклюдеров.
	m_visibleOccluders->Iterate( true );
	while( m_visibleOccluders->Iterate() )
	{
		// Ignore hidden occluders.
		// Пропускаем скрытые оклюдеры.
		if( m_visibleOccluders->GetCurrent()->visibleStamp != m_frameStamp )
			continue;

		// If the leaf's bounding sphere is overlapping the occluder's volume
		// and the leaf's bounding box is completely enclosed by the occluder's
		// volume, then the leaf is hidden, so ignore it.
		// Если ограничивающая сфера листа пересекает перекрывающий объём
		// а ограничивающий куб листа полностью входит в перекрывающий объём,
		// то данный лист скрыт от вьюера.
		if( IsSphereOverlappingVolume( m_visibleOccluders->GetCurrent()->planes,
			leaf->GetBoundingSphere()->centre, leaf->GetBoundingSphere()->radius ) == true )
			if( IsBoxEnclosedByVolume( m_visibleOccluders->GetCurrent()->planes,
				leaf->GetBoundingBox()->min, leaf->GetBoundingBox()->max ) == true )
				return;
	}

	// Check if any of this leaf's children are visible.
	// Проверяем листы-потомки на видимость.
	for( char c = 0; c < 8; c++ )
		if( leaf->children[c] != NULL )
			RecursiveSceneOcclusionCheck( leaf->children[c] );

	// Go through all the faces in the leaf.
	for( unsigned long f = 0; f < leaf->totalFaces; f++ )
	{
		// Check this face's render stamp. If it is equal to the current frame
		// stamp, then the face has already been rendered this frame.
		// Проверяем штамп рендеринга данной грани. Если он равен штампу
		// текущего кадра, то грань уже отрендерена в этом кадре.
		if( m_faces[leaf->faces[f]].renderStamp == m_frameStamp )
			continue;

		// Set the face's render stamp to indicate that it has been rendered.
		// Устанавливаем рендер-штамп грани, чтобы показать, что она отрендерена.
		m_faces[leaf->faces[f]].renderStamp = m_frameStamp;

		// Tell the face's render cache to render this face.
		// Командуем рендер-кэшу грани рендерить данную грань.
		m_faces[leaf->faces[f]].renderCache->RenderFace( m_faces[leaf->faces[f]].vertex0,
			m_faces[leaf->faces[f]].vertex1, m_faces[leaf->faces[f]].vertex2 );
	}
}

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

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

Настоящий хардкор. SceneManager.cpp - самый большой исходник в этом курсе (1281 строка). Но при ближайшем его рассмотрении видно, что он почти целиком состоит из ранее изученных элементов.

Функция LoadScene

  • Загружает сцену.
  • Вызывается сразу после создания инстанса класса SceneManager.
  • В качестве вводных параметров передаются имя скрипта загружаемой сцены (scene script) и полный путь к нему.

Создаём связные списки

В самом начале реализации LoadScene видим:
Фрагмент SceneManager.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Loads a new scene from the given scene file.
// Загружает новую сцену из данного файла скрипта сцены.
//-----------------------------------------------------------------------------
void SceneManager::LoadScene( char *name, char *path )
{
	// Create the lists of objects used in the scene. The dynamic object list
	// is persistent across scene changes so it doesn't need to be created.
	// Создаём связные списки объектов сцены (по типам).
	m_occludingObjects = new LinkedList< SceneOccluder >;
	m_visibleOccluders = new LinkedList< SceneOccluder >;
	m_playerSpawnPoints = new LinkedList< SceneObject >;
	m_objectSpawners = new LinkedList< SpawnerObject >;
...

В классе SceneManager объявлены 4 связных списка для управления различными объектами сцены:
  • m_occludingObjects хранит объекты-оклюдеры (т.е. те, что перекрывают дугие видимые объекты);
  • m_visibleOccluders хранит оклюдеры, видимые в данном кадре;
  • m_playerSpawnPoints хранит точки спауна игрока;
  • m_objectSpawners хранит спаунеры объектов сцены.
Здесь мы просто создаём их инстансы, полностью готовые к размещению в них новых элементов.

Загружаем скрипт сцены

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Load the script for the scene.
	// Загружаем скрипт сцены.
	Script *script = new Script( name, path );

	// Store the name of the scene.
	// Сохраняем имя сцены.
	m_name = new char[strlen( script->GetStringData( "name" ) ) + 1];
	memcpy( m_name, script->GetStringData( "name" ), ( strlen( script->GetStringData( "name" ) ) + 1 ) * sizeof( char ) );

	// Store the scene's gravity vector.
	// Сохраняем вектор гравитации сцены.
	m_gravity = *script->GetVectorData( "gravity" ) / m_scale;
...

Здесь загружаем скрипт сцены, применив его имя и полный путь, указанные в водных параметрах функции LoadScene. Имя сцены копируется в буфер m_name типа char.
Создаём локальную переменную m_gravity типа D3DXVECTOR3. Она объявлена в секции private объявления класса SceneManager (SceneManager.h). Присваиваем ей значение гравитации из скрипта сцены, поделённое на масштаб (m_scale).

Создаём источник света и активируем его

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Create the sun light source.
	// Создаём источник солнечного света.
	D3DLIGHT9 sun;
	sun.Type = D3DLIGHT_DIRECTIONAL;
	sun.Diffuse.r = 1.0f;
	sun.Diffuse.g = 1.0f;
	sun.Diffuse.b = 1.0f;
	sun.Diffuse.a = 1.0f;
	sun.Specular = sun.Diffuse;
	sun.Ambient.r = script->GetColourData( "ambient_light" )->r;
	sun.Ambient.g = script->GetColourData( "ambient_light" )->g;
	sun.Ambient.b = script->GetColourData( "ambient_light" )->b;
	sun.Ambient.a = script->GetColourData( "ambient_light" )->a;
	sun.Direction = D3DXVECTOR3( script->GetVectorData( "sun_direction" )->x,
		script->GetVectorData( "sun_direction" )->y,
		script->GetVectorData( "sun_direction" )->z );
	sun.Range = 0.0f;

	// Switch lighting on, enable the sun light, and specular highlights.
	// Включаем созданный выше источник света. Активируем блики.
	g_engine->GetDevice()->SetRenderState( D3DRS_LIGHTING, true );
	g_engine->GetDevice()->SetLight( 0, &sun );
	g_engine->GetDevice()->LightEnable( 0, true );
	g_engine->GetDevice()->SetRenderState( D3DRS_SPECULARENABLE, true );
...

Следующий шаг - настроить освещение сцены. Применим стандартные DirectX-функцииХ для расчёта освещённости вершин. У нас будет всего один источник света - Солнце (или Луна в ночное время). Перед созданием источника света сперва заполняем структуру D3DLIGHT9 (в случае работы с DirectX 9). Вот её определение:
Шаблон структуры D3DLIGHT9
typedef struct D3DLIGHT9 {
  D3DLIGHTTYPE  Type;	// Тип источника света. Возможные значения: D3DLIGHT9_POINT,
			// D3DLIGHT9_SPOT, D3DLIGHT9_DIRECTIONAL.
  D3DCOLORVALUE Diffuse;	// Цвет рассеянного (diffuse) света.
  D3DCOLORVALUE Specular;	// Цвет бликового (specular) света.
  D3DCOLORVALUE Ambient;	// Цвет приглушённого (ambient) света (цвет тени).
  D3DVECTOR     Position;	// Положение в пространстве источника света.
  D3DVECTOR     Direction;	// Направление источника света.
  float         Range;		// Указывает на то, как далеко светит источник.
  float         Falloff;	// Спад по мере увеличения растояния от источника.
  // Затухание по мере увеличения расстояния от источника.
  float         Attenuation0;	
  float         Attenuation1;
  float         Attenuation2;
  // Мутные параметры конусов освещённости. Только для точечных источников (D3DLIGHT9_SPOT).
  float         Theta;	// Угол в радианах внутреннего конуса точечного источника света.
			// В его зоне интенсивность света максимальна. Возможные значения:
			// от 0 до значения параметра Phi.
  float         Phi;	// Угол в радианах, опредеяющий внешний край внешнего конуса
			// точечного источника (край абажура светильника). Все объекты за пределами
			// данного края не освещаются данным источником.
} D3DLIGHT9, *LPD3DLIGHT;

Для нашего источника солнечного света мы выбрали направленный источник (D3DLIGHT9_DIRECTIONAL). Это означает, что у него нет определённого положения в 3D-пространстве. Есть только направление (direction). Таким образом свет освещает все объекты сцены. При регулировке цветов компонентов света мы выставили значения diffuse и specular на максимум. В скрипте сцены, рассмотренном выше, также есть параметр выбора цвета компонентов света:
Фрагмент city.txt
ambient_light colour 0.5 0.5 0.5 1.0

В нашем случае мы установили цвет приглушённого (ambient) света, взяв значения четырёх цветовых компонентов (rgba) из этого фрагмента скрипта сцены city.txt . Далее устанавливаем направление света, также основываясь на данных их скрипта. Оставшиеся элементы структуры D3DLIGHT9 смело пропускаем, т.к. для направленного источника света они, как правило, не применяются.
Ниже выставляем два рендер-стейта в TRUE: D3DRS_LIGHTING и D3DRS_SPECULARENABLE. Первый из них включает источник. Второй - активирует блики (specular highlights).
Далее применяем созданный источник света к сцене путём вызова функции SetLight, и вновь включаем его функцией LightEnable. Обе функции экспонированы объектом устройства Direct3D.
Закрыть
noteОбрати внимание

В функциях SetLight и LightEnable в качестве первого параметра передаётся 0. Это означает, что мы сохраняем наш источник света в первом индексе. Если вдруг создадим второй источник света, то в обеих функциях в первом параметре передадим 1. Макс, число одновременно работающих источников света зависит от видеокарты. Но обычно в игровых сценах применяют не больше 8 источников.


Настраиваем туман

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Set up the fog.
	// Настраиваем туман.
	float density = *script->GetFloatData( "fog_density" ) * m_scale;
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGENABLE, true );
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGCOLOR, D3DCOLOR_COLORVALUE(
		script->GetColourData( "fog_colour" )->r,
		script->GetColourData( "fog_colour" )->g,
		script->GetColourData( "fog_colour" )->b,
		script->GetColourData( "fog_colour" )->a ) );
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGVERTEXMODE, D3DFOG_EXP );
	g_engine->GetDevice()->SetRenderState( D3DRS_FOGDENSITY, *(unsigned long*)&density );
...

Туман так же настраивается на основе настроек скрипта сцены. В частности, оттуда берётся плотность тумана (density) и перемножается на масштаб (scale). Включаем туман вызовом рендер-стейта D3DRS_FOGENABLE. Настраиваем цвет тумана (тоже берём из скрипта сцены) вызовом рендер-стейта D3DRS_FOGCOLOR.
Рендер-стейт D3DRS_FOGVERTEXMODE указывает способ генерации тумана. Его возможные значения указаны в таблице:
ЗНАЧЕНИЕ ОПИСАНИЕ
D3DFOG_NONE Без тумана.
D3DFOG_EXP Туман становится плотнее экспоненциально, с увеличением расстояния от наблюдателя.
D3DFOG_EXP2 Туман становится плотнее экспоненциально, с увеличением квадрата значения расстояния от наблюдателя.
D3DFOG_LINEAR Туман становится плотнее линейно, с увеличением расстояния от наблюдателя.

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

В случае применения значения D3DFOG_LINEAR, необходимо вызывать рендер-стейт D3DRS_FOGEND для указания точки окончания видимости.


Загружаем меш сцены

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Store the constraints used for creating the scene.
	// Получаем из скрипта сцены параметры листков и сохраняем их в переменные.
	m_maxFaces = *script->GetNumberData( "max_faces" );
	m_maxHalfSize = *script->GetFloatData( "max_half_size" );

	// Load the scene's mesh.
	// Загружаем меш сцены (прописан в скрипте меша).
	m_mesh = g_engine->GetMeshManager()->Add( script->GetStringData( "mesh" ), script->GetStringData( "mesh_path" ) );

	// Destory the scene's script as it is no longer needed.
	// Уничтожаем скрипт сцены, т.к. он болвше не нужен.
	SAFE_DELETE( script );
...

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

Готовим рендер-кэши к рендерингу граней сцены

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Set a new projection matrix so the view frustum will fit the scene.
	// Устанавливаем новую матрицу проекции такм образом, чтобы усечённая пирамида вида вмещала в себя сцену.
	D3DDISPLAYMODE *display;
	display = g_engine->GetDisplayMode();
	D3DXMATRIX projection;
	D3DXMatrixPerspectiveFovLH( &projection, D3DX_PI / 4, (float)display->Width / (float)display->Height,
		0.1f / m_scale, m_mesh->GetBoundingSphere()->radius * 2.0f );
	g_engine->GetDevice()->SetTransform( D3DTS_PROJECTION, &projection );

	// Set the view frustum's projection matrix.
	// Назначаем усечённой пирамиде вида рассчитанную выше матрицу проекции. 
	m_viewFrustum.SetProjectionMatrix( projection );

	// Create the list of render caches.
	// Создаём связный список рендер-кэшей.
	m_renderCaches = new LinkedList< RenderCache >;

	// Search the mesh for unique materials.
	// Ищем в меше уникальные материалы.
	for( unsigned long m = 0; m < m_mesh->GetStaticMesh()->NumMaterials; m++ )
	{
		// Flag to determine if the material has been found already.
		// Флаг, определяющий, найден ли материал ранее.
		bool found = false;

		// Ensure the new material is valid.
		// Проверяем, валиден ли новый материал.
		if( m_mesh->GetStaticMesh()->materials[m] == NULL )
			continue;

		// Iterate through the already existing render caches.
		// Итерируем через существующие рендер-кэши.
		m_renderCaches->Iterate( true );
		while( m_renderCaches->Iterate() )
		{
			// Check if the new material already exists.
			// Проверяем случай, когда найденный материал уже есть в списке.
			if( m_renderCaches->GetCurrent()->GetMaterial() == m_mesh->GetStaticMesh()->materials[m] )
			{
				found = true;
				break;
			}
		}

		// Add the material if it wasn't found and not set to ignore faces.
		// Добавляем материал в связный список материалов, если он ранее не был найден в списке
		// и у него не стоит опция "игнорировать грани".
		if( found == false && m_mesh->GetStaticMesh()->materials[m]->GetIgnoreFace() == false )
			m_renderCaches->Add( new RenderCache( g_engine->GetDevice(), m_mesh->GetStaticMesh()->materials[m] ) );
	}
...

Создаём связный список (LinkedList) рендер-кэшей, которые рендерят только грани с (валидными) материалами. Ищем материалы в загруженном меше, проверяем их на валидность. Для каждого найденного материала создаётся рендер-кэш, который тут же добавляется в связный список рендер-кэшей.
Проверяем каждый материал на предмет активной опции "игнорировать грани" (ignore faces) путём вызова функции GetlgnoreFace. Данный флаг устанавливается в скрипте материала. Если он установлен в TRUE, то мы не создаём рендер-кэша для данного материала, т.к. его грани не предполагают рендеринга.

Проверяем фреймы меша сцены

Напомним, нас интересуют фреймы, содержащие:
  • оклюдеры,
  • спаунеры объектов,
  • точки спауна игрока (player spawn points).
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Get a pointer to the mesh's frame list.
	// Получаем указатель на список фреймов меша.
	LinkedList< Frame > *frames = m_mesh->GetFrameList();

	// Iterate through the frame list.
	// Итерируем через связный список фреймов.
	frames->Iterate( true );
	while( frames->Iterate() != NULL )
	{
		// Check if this frame contains an occluder.
		// Проверяем, содержит ли данный фрейм оклюдер (объект, перекрывающий другие объекты).
		if( strncmp( "oc_", frames->GetCurrent()->Name, 3 ) == 0 )
		{
			// If so, load the occluder, and continue to the next frame.
			// Если да, то загружаем оклюдер и переходим к следующему кадру.
			m_occludingObjects->Add( new SceneOccluder( frames->GetCurrent()->GetTranslation(),
				( (MeshContainer*)frames->GetCurrent()->pMeshContainer )->originalMesh,
				&frames->GetCurrent()->finalTransformationMatrix ) );
			continue;
		}

		// Check if this frame is a spawn point.
		// Проверяем, является ли данный фрейм точкой спауна.
		if( strncmp( "sp_", frames->GetCurrent()->Name, 3 ) == 0 )
		{
			// Get the actual name of the spawner object at this spawn point.
			// Получаем актуальное имя спавнер-объекта в данной точке.
			char *firstDash = strpbrk( frames->GetCurrent()->Name, "_" );
			firstDash++;
			char *lastDash = strrchr( firstDash, '_' );
			unsigned long length = lastDash - firstDash;
			char *name = new char[length + 5];
			ZeroMemory( name, sizeof( char ) * ( length + 5 ) );
			strncpy( name, firstDash, length );
			strcat( name, ".txt" );

			// Check if it is a player spawn point.
			// Проверяем, содержит ли фрейм точку спауна игрока.
			if( _stricmp( name, "player.txt" ) == 0 )
			{
				// Get the name of the player spawn point's radius frame.
				// Получаем имя фрейма спаун-радиуса точки спауна игрока.
				char *radiusName = new char[strlen( firstDash ) + 8];
				ZeroMemory( radiusName, sizeof( char ) * ( strlen( firstDash ) + 8 ) );
				strncpy( radiusName, firstDash, strlen( firstDash ) );
				strcat( radiusName, "_radius" );

				// Find the player spawn point's radius frame.
				// Ищем спаун-радиус точки спауна игрока.
				Frame *radiusFrame = frames->GetFirst();
				while( radiusFrame != NULL )
				{
					if( _stricmp( radiusFrame->Name, radiusName ) == 0 )
						break;

					radiusFrame = frames->GetNext( radiusFrame );
				}

				// Destroy the string buffer for the radius frame's name.
				// Уничтожаем строковый буфер, содержащий имя фрейма спаун-радиуса.
				SAFE_DELETE_ARRAY( radiusName );

				// Find the distance between the two points (the radius).
				// Находим расстояние между двумя точками (=радиус).
				float radius = 0.0f;
				if( radiusFrame != NULL )
					radius = D3DXVec3Length( &( radiusFrame->GetTranslation() - frames->GetCurrent()->GetTranslation() ) );

				// Create the player spawn point.
				// Создаём точку спауна игрока.
				SceneObject *point = new SceneObject( NULL, NULL );
				point->SetTranslation( frames->GetCurrent()->GetTranslation() );
				point->SetBoundingSphere( D3DXVECTOR3( 0.0f, 0.0f, 0.0f ), radius );
				point->SetVisible( false );
				point->SetGhost( true );
				point->Update( 0.0f );
				m_dynamicObjects->Add( m_playerSpawnPoints->Add( point ) );
			}
			else
			{
				// Create the application specific spawner object.
				// Создаём спаунер-объект, специфичный для приложения.
				SpawnerObject *spawner = new SpawnerObject( name, m_spawnerPath );
				spawner->SetTranslation( frames->GetCurrent()->GetTranslation() );
				spawner->Update( 0.0f );
				m_dynamicObjects->Add( m_objectSpawners->Add( spawner ) );
			}

			// Destroy the string buffer used to create the spawner's name.
			// Уничтожаем строковый буфер, содержащий имя спаун-объекта.
			SAFE_DELETE_ARRAY( name );
		}
	}
...

Сперва получаем указатель на связный список фреймов, сохранённый в меше сцены. Вообще иерархия фрейма внутри .х-файла хранится не в связном списке. Но наш класс Mesh (Mesh.cpp) создаёт его, позволяя легко трассировать (traverse) иерархию фреймов, не взирая на очерёдность.
Сперва проверяем, есть ли у имени фрейма префикс "ос_" (occluder). Если да, то добавляем найденный оклюдер в связный список оклюдеров. В нём все элементы хранятся в виде структуры SceneOccluder. И каждый новый оклюдер создаётся путём вызова конструктора данной структуры. Здесь надо лишь передать в него нужные параметры:
  • меш, содержащийся в даном фрейме,
  • матрицу трансляции фрейма,
  • матрицу трансформации фрейма.
Если фрейм оказался не оклюдером, проверяем дальше. В этот раз ищем в имени префикс "sp_" (spawner). Если таковой обнаружен, то это спаунер объектов (object spawner) и начинаем выяснять его имя, которое заключено между двумя символами подчёркивания (_) в имени фрейма. Добавив к имени фрейма расширение .txt, мы выясним имя скрипта, используемого данным спаунером. Если имя скрипта вдруг окажется player.txt, то это скрипт точек спауна игрока, что прописано в движке. В этом случае настраиваем точку спауна игрока. Единственный любопытный момент здесь - метод поиска в связном списке фреймов (frame list) фрейма, содержащего точку радиуса точки спауна игрока (player spawn point's radius point). Это значение затем использутся для расчёта ограничивающей сферы вокруг точки спауна игрока. В случае, если найденный спаунер не является точкой спауна игрока, он автоматически определяется как спаунер объектов (object spawner), обязательно сопровождаемый скриптом. Здесь создаём новый объект SpawnerObject и добавляем его в связный список динамических объектов. При создании нового объекта SpawnerObject передаём в функцию имя скрипта спаунера объектов + полный (глобальный) путь к нему (обычно он передаётся движку через структуру EngineSetup). Спаунер объектов при этом настраивает сам себя, основываясь на своём скрипте.
Закрыть
noteОбрати внимание

Спаунеры объектов, помимо списка динамических объектов, также добавляются в локальный связный список m_objectSpawners. Спаунер игрока (player spawner point) - в локальный связный список m_playerSpawnPoints. Это позволяет итерировать только через соответствующие специализированные связные списки. Для поиска по всем объектам (независимо от их типа) можно просто итерировать через связный список динамических объектов.


Готовим вершины и грани сцены к рендерингу

Фрагмент SceneManager.cpp (Проект Engine)
...
	// A list of valid faces (those with a valid material).
	// Список валидных (= допущенных к рендерингу) граней (т.е. те, которые имеют валидные материалы)
	bool *validFaces = new bool[m_mesh->GetStaticMesh()->originalMesh->GetNumFaces()];
	ZeroMemory( validFaces, sizeof( bool ) * m_mesh->GetStaticMesh()->originalMesh->GetNumFaces() );

	// These are used for locking the vertex, index, and attribute buffers of
	// the meshes. They act as pointers into the data returned by the locks.
	// Эти переменные применяются для блокировки вершин, индексов и буферов атрибутов мешей.
	// Они выступают в роли указателей, куда будут передаваться данные для блокировки.
	Vertex *vertices = NULL;
	unsigned short *indices = NULL;
	unsigned long *attributes = NULL;

	// Lock the mesh's vertex, index, and attribute buffers.
	// Лочим все 3 буфера.
	m_mesh->GetStaticMesh()->originalMesh->LockVertexBuffer( D3DLOCK_READONLY, (void**)&vertices );
	m_mesh->GetStaticMesh()->originalMesh->LockIndexBuffer( D3DLOCK_READONLY, (void**)&indices );
	m_mesh->GetStaticMesh()->originalMesh->LockAttributeBuffer( D3DLOCK_READONLY, &attributes );
...

Сперва блокируем (lock) буферы вершин, индексов и атрибутов меша сцены. Это необходимо для корректного доступа к ним.
Видим создание нового массива validFaces. Он применяется для отмечания каждой грани сцены на валидность (валидна/невалидна). Грань считается валидной, если она использует материал, поддерживаемый одним из рендер-кэшей. Если помнишь, мы создаём рендер-кэши для каждого материала, кроме тех, у которых стоит отметка "игноривать грани" (ignore faces). Таким образом, любая грань, которая использует материал с пометкой "игнорировать грани" не будет принадлежать ни одному из рендер-кэшей, а значит не будет рендериться. Проверка на валидность представлена в следющем фрагменте:
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Count the faces in the scene that have a valid material.
	// Подсчитываем число граней сцены с валидными материалами.
	for( unsigned long f = 0; f < m_mesh->GetStaticMesh()->originalMesh->GetNumFaces(); f++ )
	{
		m_renderCaches->Iterate( true );
		while( m_renderCaches->Iterate() )
		{
			if( m_renderCaches->GetCurrent()->GetMaterial() == m_mesh->GetStaticMesh()->materials[attributes[f]] )
			{
				m_totalFaces++;
				validFaces[f] = true;
				break;
			}
		}
	}

	// Create the array of faces.
	// Создаём массив граней.
	m_faces = new SceneFace[m_totalFaces];

	// Set the number of vertices.
	// Считаем общее кол-во вершин сцены.
	m_totalVertices = m_totalFaces * 3;

	// Create the vertex buffer that will hold all the vertices in the scene.
	// Создаём вершинный буфер, в котором будут храниться все вершины сцены.
	g_engine->GetDevice()->CreateVertexBuffer( m_totalVertices * VERTEX_FVF_SIZE,
		D3DUSAGE_WRITEONLY, VERTEX_FVF, D3DPOOL_MANAGED, &m_sceneVertexBuffer, NULL );

	// Used for temporary storage of the final vertices that make the scene.
	// Применяем временное хранилище для конечного набора вершин, формирующих сцену.
	Vertex *tempVertices = new Vertex[m_totalVertices];
...

После проверки всех граней следующий шаг - создание одного большого вершинного буфера, в котором будут храниться вершины всех граней, которые отмечены как валидные.
Создали массив m_faces, в который отфильтруем только валидные грани.
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Lock the scene's vertex buffer
	// Лочим (=блокируем) вершинный буфер) сцены.
	m_sceneVertexBuffer->Lock( 0, 0, (void**)&m_vertices, 0 );

	// Go through all of the valid faces in the mesh and store their details.
	// Итерируем через все валидные грани меша и сохраняем их детали.
	for( unsigned long f = 0; f < m_totalFaces; f++ )
	{
		// Ensure this face is valid.
		// Проверяем, валидна ли грань.
		if( validFaces[f] == false )
		{
			// Advance the indices pointer to skip this face.
			// Увеличиваем число индексов, припустив данную грань.
			indices += 3;
			continue;
		}

		// Store the index pointer for each vertex in the face.
		// Инкрементируем кол-во указателей на каждый из индексов после размещения
		// в индексном буфере каждой вершины
		m_faces[f].vertex0 = *indices++;
		m_faces[f].vertex1 = *indices++;
		m_faces[f].vertex2 = *indices++;

		// Find the render cache this face belongs to.
		// Находим рендер-кэш, которому принадлежит данная грань.
		m_renderCaches->Iterate( true );
		while( m_renderCaches->Iterate() )
		{
			if( m_renderCaches->GetCurrent()->GetMaterial() == m_mesh->GetStaticMesh()->materials[attributes[f]] )
			{
				m_faces[f].renderCache = m_renderCaches->GetCurrent();
				m_renderCaches->GetCurrent()->AddFace();
				break;
			}
		}

		// Take of temporary copy of these vertices.
		// Делаем временную копию этих вершин.
		tempVertices[m_faces[f].vertex0] = vertices[m_faces[f].vertex0];
		tempVertices[m_faces[f].vertex1] = vertices[m_faces[f].vertex1];
		tempVertices[m_faces[f].vertex2] = vertices[m_faces[f].vertex2];
	}
...

Блокируем ("лочим") вершинный буфер, после чего начинаем проверять каждую грань меша. Если грань невалидна, то просто пропускаем её. Если валидна...
  • сохраняем её индексы (indices),
  • добавляем в рендер-кэш, который "обслуживает" её материал,
  • сохраняем её вершины.
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Copy the final vertices (that make up the scene) into the vertex buffer.
	// Копируем конечный список вершин (которые сформируют сцену) в вершинный буфер.
	memcpy( m_vertices, tempVertices, m_totalVertices * VERTEX_FVF_SIZE );

	// Unlock the scene's vertex buffer.
	// Разблокируем вершинный буфер сцены.
	m_sceneVertexBuffer->Unlock();

	// Destroy the temporary vertices array.
	// Уничтожаем временный массив вершин.
	SAFE_DELETE_ARRAY( tempVertices );

	// Unlock the mesh's vertex, index, and attribute buffers.
	// Разблокируем все 3 буфера.
	m_mesh->GetStaticMesh()->originalMesh->UnlockAttributeBuffer();
	m_mesh->GetStaticMesh()->originalMesh->UnlockIndexBuffer();
	m_mesh->GetStaticMesh()->originalMesh->UnlockVertexBuffer();

	// Destroy the array of valid faces.
	// Уничтожаем массив валидных граней.
	SAFE_DELETE_ARRAY( validFaces );
...

Как только все валидные грани корректно сохранены, копируем все вершины в вершинный буфер путём вызова функции memcpy. Напомним, что копируются только вершины, принадлежащие валидным граням, т.к. перед сохранением мы их тщательно отбирали.
Разблокируем ("разлочим"; unlock) вершинный буфер (после копирования вершин), удаляем массивы вершин (tempVertices) и последовательно разблокируем все 3 буфера меша сцены. В конце удаляем массив валидных граней validFaces, т.к. он больше не нужен.
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Create the first scene leaf (the largest leaf that encloses the scene).
	// Создаём первый лист октодерева (самый большой, заключающий в себе всю сцену целиком).
	m_firstLeaf = new SceneLeaf();

	// Recursively build the scene, starting with the first leaf.
	// Рекурсивно строим сцену, начиная с первого листа октодерева.
	RecursiveSceneBuild( m_firstLeaf, m_mesh->GetBoundingSphere()->centre, m_mesh->GetBoundingBox()->halfSize );

	// Allow the render caches to prepare themselves.
	// Готовим рендер-кэши.
	m_renderCaches->Iterate( true );
	while( m_renderCaches->Iterate() )
		m_renderCaches->GetCurrent()->Prepare( m_totalVertices );

	// Indicate that the scene is now loaded.
	// Ставим отметку о том, что сцена загружена.
	m_loaded = true;
}
...

Финальный шаг - разделить нашу сцену на листья октодерева с целью оптимизации рендеринга. Эту задачу выполняет функция RecursiveSceneBuild, куда в качестве вводного параметра передаётся указатель на первый лист, который создан строкой выше и заключает в себе всю сцену целиком. Здесь листья делятся на более мелкие, составляя иерархию ограничивающих объёмов. Каждый такой объём содержит набор граней, допущеных к рендерингу, в то время как остальные секции сцены будут эффективно отсекаться в каждом фрейме. Реализация функции RecursiveSceneBuild также представлена в SceneManager.cpp:
Фрагмент SceneManager.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Recursively builds the scene.
// Рекурсивно строим сцену.
//-----------------------------------------------------------------------------
void SceneManager::RecursiveSceneBuild( SceneLeaf *leaf, D3DXVECTOR3 translation, float halfSize )
{
	// Build a bounding volume around this leaf.
	// Строим ограничивающие объёмы вокруг данного листа октодерева.
	leaf->SetBoundingBox( D3DXVECTOR3( translation.x - halfSize, translation.y - halfSize, translation.z - halfSize ),
		D3DXVECTOR3( translation.x + halfSize, translation.y + halfSize, translation.z + halfSize ) );
	leaf->SetBoundingSphere( translation, (float)sqrt( halfSize * halfSize + halfSize * halfSize + halfSize * halfSize ) );

	// Count the number of face in this leaf.
	// Считаем число граней в данном листе.
	unsigned long totalFaces = 0;
	for( unsigned long f = 0; f < m_totalFaces; f++ )
		if( IsFaceInBox( &m_vertices[m_faces[f].vertex0], &m_vertices[m_faces[f].vertex1],
			&m_vertices[m_faces[f].vertex2], leaf->GetBoundingBox()->min, leaf->GetBoundingBox()->max ) == true )
			totalFaces++;

	// Only divide the leaf up if it is too big and contains too many faces.
	// Делим лист только если он чересчур большой и содержит слишком много граней.
	if( halfSize > m_maxHalfSize && totalFaces > m_maxFaces )
	{
		// Go through all the child leaves.
		for( char c = 0; c < 8; c++ )
		{
			D3DXVECTOR3 newTranslation, newMin, newMax;
			float newHalfSize = halfSize / 2.0f;
			float mod;

			// Calculate the translation of the new leaf on the x axis.
			// Вычисляем трансляцию нового листа по оси х.
			mod = 1.0f;
			if( c % 2 < 1 )
				mod = -1.0f;
			newTranslation.x = translation.x + newHalfSize * mod;

			// Calculate the translation of the new leaf on the y axis.
			// Вычисляем трансляцию нового листа по оси y.
			mod = 1.0f;
			if( c % 4 < 2 )
				mod = -1.0f;
			newTranslation.y = translation.y + newHalfSize * mod;

			// Calculate the translation of the new leaf on the z axis.
			// Вычисляем трансляцию нового листа по оси z.
			mod = 1.0f;
			if( c % 8 < 4 )
				mod = -1.0f;
			newTranslation.z = translation.z + newHalfSize * mod;

			// Calculate the bounding box around the new leaf.
			// Подсчитываем размер ограничивающего объёма нового листа.
			newMin = D3DXVECTOR3( newTranslation.x - newHalfSize, newTranslation.y - newHalfSize,
				newTranslation.z - newHalfSize );
			newMax = D3DXVECTOR3( newTranslation.x + newHalfSize, newTranslation.y + newHalfSize,
				newTranslation.z + newHalfSize );

			// Check if the new scene leaf will have at least one face in it.
			// Проверяем, содержит ли новый лист хотя бы одну грань.
			for( unsigned long f = 0; f < m_totalFaces; f++ )
			{
				if( IsFaceInBox( &m_vertices[m_faces[f].vertex0], &m_vertices[m_faces[f].vertex1],
					&m_vertices[m_faces[f].vertex2], newMin, newMax ) == true )
				{
					// A face has been found that is inside the new child scene
					// leaf, so create the scene leaf. Then recurse through the
					// scene leaf's branch of the scene hierarchy.
					// В случае, когда грань/грани найдена внутри нового листа,
					// создаём его (лист). Затем рекурсивно проходим через
					// другие листья сцены, расположенные ниже по иерархии.
					leaf->children[c] = new SceneLeaf;
					RecursiveSceneBuild( leaf->children[c], newTranslation, halfSize / 2.0f );

					break;
				}
			}
		}

		return;
	}

	// Create the leaf's array of face indices.
	// Создаём массив индексов вершин граней листа.
	leaf->totalFaces = totalFaces;
	leaf->faces = new unsigned long[totalFaces];

	// If any face is contained in the leaf's bounding box, then store
	// the index of the face in the leaf's face index array.
	// Если грань расположена внутри ограничивающего бокса листа,
	// сохраняем индекс этой грани в массиве индексов вершин граней листа.
	totalFaces = 0;
	for( unsigned long f = 0; f < m_totalFaces; f++ )
		if( IsFaceInBox( &m_vertices[m_faces[f].vertex0], &m_vertices[m_faces[f].vertex1],
			&m_vertices[m_faces[f].vertex2], leaf->GetBoundingBox()->min, leaf->GetBoundingBox()->max ) == true )
			leaf->faces[totalFaces++] = f;

	// Store pointers to any occluding objects in the leaf.
	// Сохраняем указатели на любые перекрываемые объекты листа.
	m_occludingObjects->Iterate( true );
	while( m_occludingObjects->Iterate() )
		if( IsBoxInBox( m_occludingObjects->GetCurrent()->GetBoundingBox()->min,
			m_occludingObjects->GetCurrent()->GetBoundingBox()->max, leaf->GetBoundingBox()->min,
			leaf->GetBoundingBox()->max ) == true )
			leaf->occluders->Add( m_occludingObjects->GetCurrent() );
}
...

Если кратко, сначала создаём вокруг листа ограничивающие объёмы (бокс и эллипс). Затем при необходимости создаём листы-потомки. Далее указатели на грани и оклюдеры сохраняются в данных листа, внутри которых они заключены. Здесь активно применяются функции базовой геометрии из Geometry.h .
Но вернёмся к окончанию функции LoadScene.
После завершении создания листьев октодерева готовим рендер-кэши к рендерингу путём вызова функции Prepare на каждом из них.

Функция Update

Фрагмент SceneManager.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Updates the scene and all the objects in it.
// Обновляет сцену и все объекты на ней.
//-----------------------------------------------------------------------------
void SceneManager::Update( float elapsed, D3DXMATRIX *view )
{
	// Ensure a scene is loaded.
	// Убеждаемся, что сцена загружена.
	if( m_firstLeaf == NULL )
		return;

	// Increment the frame stamp. Indicating the start of a new frame.
	// Инкрементируем (увеличиваем на 1) штамп фрейма.
	m_frameStamp++;

	// Update the view frustum.
	// Обновляем усечённую пирамиду вида.
	m_viewFrustum.Update( view );

	// Go through all the dynamic object's and update them.
	// Итерируем все динамические объекты и обновляем их.
	m_dynamicObjects->Iterate( true );
	while( m_dynamicObjects->Iterate() )
	{
		// Ignore the object if it is not enabled.
		// Игнорируем отключенные объекты.
		if( m_dynamicObjects->GetCurrent()->GetEnabled() == false )
			continue;

		// If this object is a ghost, then it cannot collided with anything.
		// However, it still needs to be updated. Since objects receive their
		// movement through the collision system, ghost objects will have to be
		// allowed to update their movement manually.
		// Если объект является призраком, то он не может сталкиваться с чем-либо.
		// Но в любом случае он тоже должен быть обновлён.
		// В свете того, что объекты получают своё движение через систему столкновений,
		// объекты-призраки должны быть допущены к обновлению своих положений вручную.
		if( m_dynamicObjects->GetCurrent()->GetGhost() == true )
		{
			m_dynamicObjects->GetCurrent()->Update( elapsed );
			continue;
		}

		// Objects without an ellipsoid radius cannot collide with anything.
		// Объекты без радиуса эллипсоида не могут сталкиваться с чем-либо.
		if( m_dynamicObjects->GetCurrent()->GetEllipsoidRadius().x + m_dynamicObjects->GetCurrent()->GetEllipsoidRadius().y,
			m_dynamicObjects->GetCurrent()->GetEllipsoidRadius().z <= 0.0f )
		{
			m_dynamicObjects->GetCurrent()->Update( elapsed );
			continue;
		}

		// Build the collision data for this object.
		// Заполняем данные столкновения по данном объекту.
		static CollisionData collisionData;
		collisionData.scale = m_scale;
		collisionData.elapsed = elapsed;
		collisionData.frameStamp = m_frameStamp;
		collisionData.object = m_dynamicObjects->GetCurrent();
		collisionData.gravity = m_gravity * elapsed;

		// Perform collision detection for this object.
		// Выполняем определение столкновения для данного объекта.
		PerformCollisionDetection( &collisionData, (Vertex*)m_vertices, m_faces, m_totalFaces, m_dynamicObjects );

		// Allow the object to update itself.
		// Позволяем объекту обновить самого себя.
		m_dynamicObjects->GetCurrent()->Update( elapsed, false );
	}
}
...

В данном коде видим, что в каждом кадре происходит...
  • инкрементирование (=увеличение на единицу) рендер-штампа,
  • обновление усечённой пирамиды вида (view frustum).
Далее выполняем обновление всех динамических объектов путём итерирования через связный список m_dynamicObjects и выполнении на каждом объекте определения столкновений (где это возможно). Проверяем следующие случаи:
  • Выключеные объекты (у которых параметр enabled выставлен в FALSE) просто пропускаются.
  • Объекты с параметром ghost=TRUE обновляются, но не проверяются на столкновения.
  • Мы также избегаем проверки на столкновения у объектов, не имеющих ограничивающий эллипс.
Очевидно, что, не имея ограничивающего объёма, объекты не могут сталкиваться с чем либо.

Функция Render

Фрагмент SceneManager.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Renders the scene and all the objects in it.
// Рендерпт сцену и все объекты на ней.
//-----------------------------------------------------------------------------
void SceneManager::Render( float elapsed, D3DXVECTOR3 viewer )
{
	// Ensure a scene is loaded.
	// Убеждаемся, что сцена загружена.
	if( m_firstLeaf == NULL )
		return;

	// Clear the list of visible occluders.
	// Очищаем список видимых оклюдеров.
	m_visibleOccluders->ClearPointers();

	// Begin the process of determining the visible leaves in the scene. The
	// first step involves checking the scene leaves against the view frustum.
	// Начинаем процесс определения видимых листьев октодерева сцены.
	// Первым делом проверяем листья, расположенные напротив усечённой пирамиды вида.
	RecursiveSceneFrustumCheck( m_firstLeaf, viewer );
...

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

Функция RecursiveSceneFrustumCheck

Сразу после этого приступаем к первому этапу отсечения - отсечение невидимых объектов сцены методом усечённой пирамиды вида (view frustum culling). Вызываем функцию RecursiveSceneFrustumCheck, которая рекурсивно проходит через иерархию листьев сцены, отсекая все листья, оказавшиеся за пределами усечённой пирамиды вида. Её реализация размещена в конце SceneManager.cpp:
Фрагмент SceneManager.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Recursively checks the scene's leaves against the view frustum.
// Рекурсивно проверяет листья сцены относительно усечённой пирамиды вида.
//-----------------------------------------------------------------------------
bool SceneManager::RecursiveSceneFrustumCheck( SceneLeaf *leaf, D3DXVECTOR3 viewer )
{
	// Check if the leaf's bounding sphere is inside the view frustum.
	// Проверяем случай, когда ограничивающая сфера листа расположена внутри
	// усечённой пирамиды вида.
	if( m_viewFrustum.IsSphereInside( leaf->GetBoundingSphere()->centre,
		leaf->GetBoundingSphere()->radius ) == false )
		return false;

	// Check if the leaf's bounding box is inside the view frustum.
	// Проверяем случай, когда ограничивающий бокс листа расположен внутри
	// усечённой пирамиды вида.
	if( m_viewFrustum.IsBoxInside( leaf->GetBoundingBox()->min,
		leaf->GetBoundingBox()->max ) == false )
		return false;

	// Set the visible stamp on this leaf to the current frame stamp. This will
	// indicate that the leaf may be visible this frame and may need rendering.
	// Присваиваем штамп видимости данного листа штампу текущего кадра.
	// Это будет сигналом, что данный лист виден в текущем кадре и (возможно)
	// будет рендерится.
	leaf->visibleStamp = m_frameStamp;

	// Check if any of this leaf's children are visible.
	// Проверяем, видимы ли все дочерние листья (=потомки) данного листа.
	char visibleChildren = 0;
	for( char c = 0; c < 8; c++ )
		if( leaf->children[c] != NULL )
			if( RecursiveSceneFrustumCheck( leaf->children[c], viewer ) )
				visibleChildren++;

	// If this leaf has visible children then this branch of the scene can go
	// deeper. So ignore this leaf.
	// Если данный лист имеет видимые потомки, то можно спуститься ниже
	// по иерархии. В этом случае игнорируем его.
	if( visibleChildren > 0 )
		return false;

	// Iterate through all the occluders in this leaf.
	// Итерируем все оклюдеры данного листа.
	leaf->occluders->Iterate( true );
	while( leaf->occluders->Iterate() )
	{
		// Check if the occluder's bounding sphere is inside the view frustum.
		// Проверяем случай, когда ограничивающая сфера оклюдера расположена
		// внутри усечённой пирамиды вида.
		if( m_viewFrustum.IsSphereInside( leaf->occluders->GetCurrent()->translation,
			leaf->occluders->GetCurrent()->GetBoundingSphere()->radius ) == false )
			continue;

		// Check if the occluder's bounding box is inside the view frustum.
		// Проверяем случай, когда ограничивающий куб оклюдера расположен
		// внутри усечённой пирамиды вида.
		if( m_viewFrustum.IsBoxInside( leaf->occluders->GetCurrent()->GetBoundingBox()->min,
			leaf->occluders->GetCurrent()->GetBoundingBox()->max ) == false )
			continue;

		// Calculate the distance between the occluder and the viewer.
		// Вычисляем расстояние между оклюдером и вьюером.
		leaf->occluders->GetCurrent()->distance = D3DXVec3Length( &( leaf->occluders->GetCurrent()->translation - viewer ) );

		// Iterate through the list of visible occluders.
		// Итерируем список видимых оклюдеров.
		m_visibleOccluders->Iterate( true );
		while( m_visibleOccluders->Iterate() )
		{
			// If the new occluder is already in the list, don't add it agian.
			// Если новый оклюдер уже в списке, не надо его снова добавлять.
			if( leaf->occluders->GetCurrent() == m_visibleOccluders->GetCurrent() )
				break;

			// If the new occluder is closer to the viewer than this occluder,
			// then add it to the list before this occluder.
			// Если новый оклюдер расположен к вьюеру ближе, чем текущий оклюдер,
			// то добавляем его в список ДО данного оклюдера.
			if( leaf->occluders->GetCurrent()->distance < m_visibleOccluders->GetCurrent()->distance )
			{
				m_visibleOccluders->InsertBefore( leaf->occluders->GetCurrent(),
					m_visibleOccluders->GetCompleteElement( m_visibleOccluders->GetCurrent() ) );
				leaf->occluders->GetCurrent()->visibleStamp = m_frameStamp;
				break;
			}
		}

		// If the occluder wasn't in the list or not added then add it now.
		// Если оклюдер не был добавлен в список, то сделаем это сейчас.
		if( leaf->occluders->GetCurrent()->visibleStamp != m_frameStamp )
		{
			m_visibleOccluders->Add( leaf->occluders->GetCurrent() );
			leaf->occluders->GetCurrent()->visibleStamp = m_frameStamp;
		}
	}

	return true;
}
...

  • Проверяем на видимость методом усечённой пирамиды вида
Первым делом выполняем проверку методом усечённой пирамиды вида (frustum check) для первого листа октодерева, заключающего в себе всю сцену целиком. Сначала проверяем ограничивающую сферу листа (указатель на который передаётся в качестве вводного параметра), затем - ограничивающий куб. Если лист проходит оба теста, присваиваем штамп видимости листа к штампу видимости кадра (по сути выставляем в TRUE для данного кадра).
  • Проверяем на видимость листья
Далее проверяем на видимоть листья-потомки (child leaf). Именно здесь функция RecursiveSceneFrustumCheck вызывает саму себя, то есть выполняется рекурсивно. Такой подход позволяет, в случае, когда лист проверки не прошёл (т.е. оказался невидимым), пропустить проверку его листов-потомков. Таким образом, проверив на видимость всего один лист, мы эффективно отсекаем всю ветвь дерева, даже не проверяя листья, расположенные ниже по иерархии.
Рекурсивный процесс проверки останавливается, когда достигнут конец ветки, либо когда обнаружен невидимый лист (и как следстве - его потомки). Затем функция переходит к следующему листу, с непроверенной ветвью потомков. Весь процесс продолжается, пока не будут проверены все листья в иерархии.
  • Проверяем на видимость оклюдеры в листе
Сразу по окончании проверки ветки (branch) начинаем проверять на видимость оклюдеры, расположенные внутри конечного листа ветки. Ведь наш алгоритм устроен так, что листья, содержащие листья-потомки (формально) не содержат оклюдеров! Мы итерируем через каждый оклюдер листа, проверяя его (оклюдер) на видимость. И снова проверяем не сам оклюдер, а (последовательно) его ограничивающие сферу и куб. В сучае успешного прохождения проверки (= данный окюдер видим) вычисляем расстояние отданного оклюдера до вьюера для последующей сортировки (по мере удалённости от вьюера).
Далее ещё раз итерируем через связный список видимых оклюдеров, проверяя, нет ли в нём только что проверенного оклюдера. Если нет, то добавяем его в этот список сразу перед оклюдером, расположенным за ближайшим к вьюеру. Так как наш список видимых оклюдеров отсортирован, мы гарантированно найдём нужный окюдер в списке (если тот уже есть) ещё до того, как добавим его туда. Это предотвратит случаи добавления одного и того же оклюдера дважды.
  • Проверяем оклюдеры в списке
Проверяем случай, когда оклюдер не был добавлен в связный список (например по причине того, что он расположен дальше всех оклюдеров в списке относительно вьюера). В этом случае просто добавляем оклюдер в конец связного списка.
Напомним, что все листья сцены, определённые как видимые, будут иметь штамп видимости приравненный к штампу видимости текущего фрейма. Эта информация понадобится при выполнении функции RecursiveSceneOcclusionCheck, также размещённой в SceneManager.cpp.

Создание перекрывающих объёмов (occlusion volumes)

Итак, после применения к сцене отсечения методом усечённой пирамиды вида внутри этой самой пирамиды остались объекты-оклюдеры, вокруг которых надо создать перекрывающие объёмы. Это выполняется в следующем фрагменте реализаци функции Render (SceneManager.cpp):
Фрагмент SceneManager.cpp (Проект Engine)
...
	// A list of potentially visible leaves and occluders has been determined
	// after check against the view frustum. The next step is to go through and
	// further refine the list of visible occluders through occlusion culling.
	// Далее итерируем список видимых оклюдеров для определения отсечений объектов,
	// заслонённых ими.
	m_visibleOccluders->Iterate( true );
	while( m_visibleOccluders->Iterate() )
	{
		// If the occluder's visible stamp does not not equal the current frame
		// stamp then the occluder has been hidden somehow, so ignore it.
		// Если штамп видимости оклюдера не соответствует штампу текущего фрейма,
		// значит этот оклюдер спрятан. Поэтому игнорируем его.
		if( m_visibleOccluders->GetCurrent()->visibleStamp != m_frameStamp )
			continue;

		// Build the occluder's occlusion volume.
		// Создаем ограничивающий объём вокруг оклюдера.
		BuildOcclusionVolume( m_visibleOccluders->GetCurrent(), viewer );

		// Iterate through the rest of the visible occluder's.
		// Итерируем оставшиеся видимые оклюдеры.
		SceneOccluder *occludee = m_visibleOccluders->GetNext( m_visibleOccluders->GetCurrent() );
		while( occludee != NULL )
		{
			// If the occludee's bounding sphere is overlapping the occluder's
			// volume and the occludee's bounding box is completely enclosed by
			// the occluder's volume, then the occludee is hidden.
			// Если ограничивающая сфера заслоняемого объекта перекрывает
			// ограничивающий объём оклюдера, а ограничивающий куб заслоняемого объекта
			// полностью заключён внутри огарипчивающего объёма оклюдера (лучи, касающиеся
			// краёв оклюдера уходят бесконечно вдаль), то заслоняемый объект не виден
			// наблюдателю. => Его можно не рендерпть.
			if( IsSphereOverlappingVolume( m_visibleOccluders->GetCurrent()->planes,
				occludee->translation,
				occludee->GetBoundingSphere()->radius ) == true )
				if( IsBoxEnclosedByVolume( m_visibleOccluders->GetCurrent()->planes,
					occludee->GetBoundingBox()->min,
					occludee->GetBoundingBox()->max ) == true )
					occludee->visibleStamp--;

			occludee = m_visibleOccluders->GetNext( occludee );
		}
	}
...

По окончании выполнения функции RecursiveSceneFrustumCheck связный список m_visibleOccluders заполнен указателями на все объекты-оклюдеры, видимые в данном кадре. Итерируем через него, строя перекрывающие объёмы для каждого объекта-оклюдера путём вызова функции BuildOcclusionVolume.

Функция BuildOcclusionVolume

  • Применяется для пстроения перекрывающего объёма (occlusion volume) путём продолжения лучей зрения, направленных от вьюера и касающихся граней оклюдера. Соответственно зависит от текущего положения вьюера в 3D-пространстве.
Реализация функции BuildOcclusionVolume представлена в SceneManager.cpp:
Фрагмент SceneManager.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Builds an occlusion volume for the given occluder.
// Строим перекрывающий объём для данного оклюдера.
//-----------------------------------------------------------------------------
void SceneManager::BuildOcclusionVolume( SceneOccluder *occluder, D3DXVECTOR3 viewer )
{
	// Create a list of edges for the occluder's silhouette.
	// Создаём список рёбер силуэта оклюдера.
	LinkedList< Edge > *edges = new LinkedList< Edge >;

	// Go through all the faces in the occluder's mesh.
	for( unsigned long f = 0; f < occluder->totalFaces; f++ )
	{
		// Get the indices of this face.
		// Получаем индексы вершин грани.
		unsigned short index0 = occluder->indices[3 * f + 0];
		unsigned short index1 = occluder->indices[3 * f + 1];
		unsigned short index2 = occluder->indices[3 * f + 2];

		// Find the angle between the face's normal and the vector point from
		// viewer's position to the face's position. If the angle is less than
		// 0, then the face is visible to the viewer.
		// Вычисляем угол между нормалью грани и вектором, направленным от вьюера
		// к грани. Если данный угол меньше 0, то данная грань вьюеру (=игроку) не видна.
		if( D3DXVec3Dot( &occluder->vertices[index0].normal, &( occluder->vertices[index0].translation - viewer ) ) < 0.0f )
		{
			// Check if the list of edges is empty.
			// Если список граней пуст...
			if( edges->GetTotalElements() == 0 )
			{
				// Add all the edges for this face.
				// Добавляем в список 3 ребра данной грани.
				edges->Add( new Edge( &occluder->vertices[index0], &occluder->vertices[index1] ) );
				edges->Add( new Edge( &occluder->vertices[index1], &occluder->vertices[index2] ) );
				edges->Add( new Edge( &occluder->vertices[index2], &occluder->vertices[index0] ) );
			}
			else
			{
				Edge *found0 = NULL;
				Edge *found1 = NULL;
				Edge *found2 = NULL;

				// Iterate through the list of edges.
				// Итерируем список рёбер.
				edges->Iterate( true );
				while( edges->Iterate() != NULL )
				{
					// Check if the first edge of this face already exists.
					// Проверяем случай, когда первое ребро данной грани уже существует.
					if( ( edges->GetCurrent()->vertex0->translation == occluder->vertices[index0].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index1].translation ) ||
						( edges->GetCurrent()->vertex0->translation == occluder->vertices[index1].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index0].translation ) )
						found0 = edges->GetCurrent();

					// Check if the second edge of this face already exists.
					// Проверяем случай, когда второе ребро данной грани уже существует.
					if( ( edges->GetCurrent()->vertex0->translation == occluder->vertices[index1].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index2].translation ) ||
						( edges->GetCurrent()->vertex0->translation == occluder->vertices[index2].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index1].translation ) )
						found1 = edges->GetCurrent();

					// Check if the third edge of this face already exists.
					// Проверяем случай, когда третье ребро данной грани уже существует.
					if( ( edges->GetCurrent()->vertex0->translation == occluder->vertices[index2].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index0].translation ) ||
						( edges->GetCurrent()->vertex0->translation == occluder->vertices[index0].translation &&
						edges->GetCurrent()->vertex1->translation == occluder->vertices[index2].translation ) )
						found2 = edges->GetCurrent();
				}

				// If the first edge was found, remove it. Otherwise add it.
				// Если первое ребро найдено, удалим его. В противном случае - добавим в список рёбер.
				if( found0 != NULL )
					edges->Remove( &found0 );
				else
					edges->Add( new Edge( &occluder->vertices[index0], &occluder->vertices[index1] ) );

				// If the second edge was found, remove it. Otherwise add it.
				// Если второе ребро найдено, удалим его. В противном случае - добавим в список рёбер.
				if( found1 != NULL )
					edges->Remove( &found1 );
				else
					edges->Add( new Edge( &occluder->vertices[index1], &occluder->vertices[index2] ) );

				// If the thrid edge was found, remove it. Otherwise add it.
				// Если третье ребро найдено, удалим его. В противном случае - добавим в список рёбер.
				if( found2 != NULL )
					edges->Remove( &found2 );
				else
					edges->Add( new Edge( &occluder->vertices[index2], &occluder->vertices[index0] ) );
			}
		}
	}

	// Empty the occluder's list of planes.
	// Опустошаем список плоскостей оклюдера.
	occluder->planes->Empty();

	// Create the front cap plane.
	// Создаём плоскость верхнего сечения. 
	D3DXPLANE *plane = new D3DXPLANE;
	D3DXPlaneFromPointNormal( plane, &occluder->translation, &( occluder->translation - viewer ) );
	occluder->planes->Add( plane );

	// Iterate through the list of edges.
	// Итерируем список рёбер. 
	edges->Iterate( true );
	while( edges->Iterate() != NULL )
	{
		// Get the position of the vertices in the edge.
		// Получаем позицию вершин ребра.
		D3DXVECTOR3 vertex1 = edges->GetCurrent()->vertex0->translation;
		D3DXVECTOR3 vertex2 = edges->GetCurrent()->vertex1->translation;

		// Calculate the position of the thrid vertex for creating the plane.
		// Вычисляем положение третьей вершины для создания плоскости.
		D3DXVECTOR3 dir = vertex1 - viewer;
		D3DXVec3Normalize( &dir, &dir );
		D3DXVECTOR3 vertex3 = vertex1 + dir;

		// Create a plane from this edge.
		// Создаём плоскость на основе данной грани.
		plane = new D3DXPLANE;
		D3DXPlaneFromPoints( plane, &vertex1, &vertex2, &vertex3 );
		occluder->planes->Add( plane );
	}

	// Destroy the list of edges.
	// Уничтожаем список рёбер.
	SAFE_DELETE( edges );
}
...


Image
Рис.2 Рёбра контурные (по внешней границе) и внутренние


В качестве вводных параметров функция BuildOcclusionVolume принимает указатель на оклюдер, вокруг которого будем строить перекрывающий объём, и вектор положения вьюера (или виртуальной камеры) в 3D-пространстве. Первым делом создаём связный список Edge (англ. "ребро") для хранения рёбер оклюдера, образующих его контур (если смотреть на него со стороны наблюдателя; см Рис. 1).
Далее итерируем через каждое ребро оклюдера, проверяя, повёрнута ли грань, которой принадлежит данное ребро, к вьюеру. Грани оклюдера с обратной стороны от наблюдателя рассматриваются как невидимые, и потому пропускаются. Всякий раз, когда обнаруживается вмдммая грань, добавляем её рёбра в связный список Edges. Также проверяются рёбра в самом связном списке, чтобы новодобавленные рёбра не повторяли имеющиеся. Если повторяют, то удаляем дубликаты. Только уникальные рёбра могут сформировать контур объекта. В свете того, что неконтурное ребро обычно принадлежит сразу двум граням, которые при проверке тоже окажутся видимыми и таким образом ребро будет зарегистрировано в списке дважды (см. Рис. 2).
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Empty the occluder's list of planes.
	// Опустошаем список плоскостей оклюдера.
	occluder->planes->Empty();

	// Create the front cap plane.
	// Создаём плоскость верхнего сечения. 
	D3DXPLANE *plane = new D3DXPLANE;
	D3DXPlaneFromPointNormal( plane, &occluder->translation, &( occluder->translation - viewer ) );
	occluder->planes->Add( plane );
...

В данном фрагменте опустошаем связный список плоскостей (plane) т.к. содержащиеся в нём указатели на плоскости относятся к предыдущему кадру и более невалидны.
Создаём переднюю (фронтальную) плоскость (front plane) перекрывающего объёма. Эта воображаемая плоскость расположена на месте оклюдера и "наложена" на его видимую поверхность. Она служит для предотвращения отсечения объектов, расположенных ближе к вьюеру, чем данный оклюдер (т.е. между вьюером и оклюдером). Для создания данной плоскости вызываем функцию D3DXPIaneFromPointNormal, предоставляемую вспомогательной библиотекой D3DX. Как упоминалось выше, для позиционирования плоскости применяем вектор текущей позиции оклюдера. Для ориентации плоскости относительно вьюера нормализуем этот вектор.
Закрыть
noteПримечание

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

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Iterate through the list of edges.
	// Итерируем список рёбер. 
	edges->Iterate( true );
	while( edges->Iterate() != NULL )
	{
		// Get the position of the vertices in the edge.
		// Получаем позицию вершин ребра.
		D3DXVECTOR3 vertex1 = edges->GetCurrent()->vertex0->translation;
		D3DXVECTOR3 vertex2 = edges->GetCurrent()->vertex1->translation;

		// Calculate the position of the thrid vertex for creating the plane.
		// Вычисляем положение третьей вершины для создания плоскости.
		D3DXVECTOR3 dir = vertex1 - viewer;
		D3DXVec3Normalize( &dir, &dir );
		D3DXVECTOR3 vertex3 = vertex1 + dir;

		// Create a plane from this edge.
		// Создаём плоскость на основе данной грани.
		plane = new D3DXPLANE;
		D3DXPlaneFromPoints( plane, &vertex1, &vertex2, &vertex3 );
		occluder->planes->Add( plane );
	}

	// Destroy the list of edges.
	// Уничтожаем список рёбер.
	SAFE_DELETE( edges );
}
...

На завершающем этапе выполнения функции BuildOcclusionVolume (когда фронтальная плоскость успешно создана) итерируем через связный список рёбер (edges), который, напомним, содержит только рёбра внешнего контура оклюдера (boundary edges) сточки вида вьюера (from viewer's pint of view). Для каждого ребра создаём плоскость, на которой данное ребро лежит и имеющее с ним общую ориентацию в пространстве. Вместе с фронтальной плоскостью плоскости рёбер они образуют замкнутый объём (enclosed volume), который бесконечно удлаяется от оклюдера (см. Рис.1). Это и есть перекрывающий объём. В отличие от усечённой пирамиды вида у него отсутствует дальнаяя плоскость (far plane).

Проверка на наличие оклюдеров, спрятанных за перекрывающими объёмами

ОК, увсех видимых оклюдеров построены перекрывающие объёмы. Проверяем каждый из перекрывающих объёмов на содержание внутри них оклюдеров.
Если помнишь, мы отслеживаем расстояние от наблюдателя (viewer) до каждого из оклюдеров. Это необходимо для сортировки видимых оклюдеров, начиная от ближней плоскости видимости (near plane) до дальней (far plane). Всё это выполняется в функции RecursiveSceneFrustumCheck, которая сортирует связный список m_visibleOccluders по вышеуказанному принципу. Это значит, что мы итерируем через его оставшиеся элементы (начиная с текущего видимого оклюдера) и проверяем, заслонены ли (concealed) более удалённые оклюдеры или нет. Из фрагмента кода выше видно, что здесь задействуются служебные функции из заголовка Geometry.h . В частности, сперва вызывается функция IsSphereOverlappingVolume, затем - IsBoxEnclosedByVolume. Такой порядок связан с тем, что, с точки зрения процессора, проверить ограничивающую сферу (bounding sphere) проще, чем ограничивающий куб (bounding box). В свете того, что ограничивающая сфера эффективно детектирует большую часть спрятанных (=перекрытых перекрывающим объёмом) оклюдеров, нет необходимости часто вызывать проверку ограничивающих кубов, что позволяет сохранить нужный уровень производительности.

Проверяем остальные листья сцены относительно перекрывающих объёмов видимых оклюдеров

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Tell all the render caches to prepare for rendering.
	// Командуем всем рендер-кэшам приготовиться к рендерингу.
	m_renderCaches->Iterate( true );
	while( m_renderCaches->Iterate() )
		m_renderCaches->GetCurrent()->Begin();

	// Finally, check the scene's leaves against the visible occluders.
	// Проверяем листья октодерева сцены на предмет заслонённости оклюдерами.
	RecursiveSceneOcclusionCheck( m_firstLeaf );
...

Сначала командуем каждому рендер-кэшу приготовиться к рендерингу путём вызова Begin (аналога DX-функции BeginScene). Это позволяет рендер-кэшам принять индексы граней, которые в данном (готовящемся к рендерингу) кадре помечены как видимые (visible).
Выше мы определили, какие именно оклюдеры будут видимы. Теперь проверяем остальные листья сцены (оставшиеся после проверки на отсечение методом усечённой пирамиды вида) на предмет их вхождения в перекрывающие объёмы (occluding volumes) видимых оклюдеров. Это выполняет функция RecursiveSceneOcclusionCheck.

Функция RecursiveSceneOcclusionCheck

  • Выполняет последнюю проверку видимости граней в данном кадре.
То есть все оставшиеся грани, прошедшие её успешно, точно отправятся на рендеринг. Реализация RecursiveSceneOcclusionCheck размещена в самом конце SceneManager.cpp:
Фрагмент SceneManager.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Recursively checks the scene's leaves against the occlusion volumes.
// Рекурсивно проверяем положение листьев сцены относительно перекрывающих объёмов.
//-----------------------------------------------------------------------------
void SceneManager::RecursiveSceneOcclusionCheck( SceneLeaf *leaf )
{
	// Ignore the leaf if it is not visible this frame.
	// Пропускаем лист, если он не видим в данном кадре.
	if( leaf->visibleStamp != m_frameStamp )
		return;

	// Iterate through the list of visible occluders.
	// Итерируем список видимых оклюдеров.
	m_visibleOccluders->Iterate( true );
	while( m_visibleOccluders->Iterate() )
	{
		// Ignore hidden occluders.
		// Пропускаем скрытые оклюдеры.
		if( m_visibleOccluders->GetCurrent()->visibleStamp != m_frameStamp )
			continue;

		// If the leaf's bounding sphere is overlapping the occluder's volume
		// and the leaf's bounding box is completely enclosed by the occluder's
		// volume, then the leaf is hidden, so ignore it.
		// Если ограничивающая сфера листа пересекает перекрывающий объём
		// а ограничивающий куб листа полностью входит в перекрывающий объём,
		// то данный лист скрыт от вьюера.
		if( IsSphereOverlappingVolume( m_visibleOccluders->GetCurrent()->planes,
			leaf->GetBoundingSphere()->centre, leaf->GetBoundingSphere()->radius ) == true )
			if( IsBoxEnclosedByVolume( m_visibleOccluders->GetCurrent()->planes,
				leaf->GetBoundingBox()->min, leaf->GetBoundingBox()->max ) == true )
				return;
	}

	// Check if any of this leaf's children are visible.
	// Проверяем листы-потомки на видимость.
	for( char c = 0; c < 8; c++ )
		if( leaf->children[c] != NULL )
			RecursiveSceneOcclusionCheck( leaf->children[c] );

	// Go through all the faces in the leaf.
	for( unsigned long f = 0; f < leaf->totalFaces; f++ )
	{
		// Check this face's render stamp. If it is equal to the current frame
		// stamp, then the face has already been rendered this frame.
		// Проверяем штамп рендеринга данной грани. Если он равен штампу
		// текущего кадра, то грань уже отрендерена в этом кадре.
		if( m_faces[leaf->faces[f]].renderStamp == m_frameStamp )
			continue;

		// Set the face's render stamp to indicate that it has been rendered.
		// Устанавливаем рендер-штамп грани, чтобы показать, что она отрендерена.
		m_faces[leaf->faces[f]].renderStamp = m_frameStamp;

		// Tell the face's render cache to render this face.
		// Командуем рендер-кэшу грани рендерить данную грань.
		m_faces[leaf->faces[f]].renderCache->RenderFace( m_faces[leaf->faces[f]].vertex0,
			m_faces[leaf->faces[f]].vertex1, m_faces[leaf->faces[f]].vertex2 );
	}
}
...

Как только вошли в тело функции, проверяем, чтобы штамп видимости листа из вводного параметра был установлен как штамп текущего кадра. Если это не так, то данный лист не прошёл предыдущие проверки и потому не проверяем его здесь, т.к. он уже (по каким-то причинам) в данном кадре не видим.
Итак, если лист к настоящему моменту видим, итерируем через список его оклюдеров для проверки вхождения листа в зону перекрывающих объёмов. Как и везде, проверяем не сам лист, а его ограничивающие сферу и куб. В случае провала этого теста, лист заслонён и потому пропускаем его.
Если тест пройден, проверяем каждый из его потомков путём рекурсивного вызова функции RecursiveSceneOcclusionCheck:
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Check if any of this leaf's children are visible.
	// Проверяем, видимы ли все дочерние листья (=потомки) данного листа.
	char visibleChildren = 0;
	for( char c = 0; c < 8; c++ )
		if( leaf->children[c] != NULL )
			if( RecursiveSceneFrustumCheck( leaf->children[c], viewer ) )
				visibleChildren++;
...


Image
Рис.3 Недостаток отсечения методом перекрывающих объёмов


Здесь проверяется вся иерархия листьев октодерева.
Далее регистрируем все грани данного листа для рендеринга. В цикле for каждая грань листа проверяется на зарегистрированность для рендеринга. Грань может входить в несколько листьев одновременно. Таким образом нам необходимо избежать рендеринга грани несколько раз (в случае когда все листы с гранью видимы). Здесь нам поможет рендер-штамп (render-stamp), который устанавливается в качестве штампа текущего кадра (frame stamp) при регистрации грани в её рендер-кэше. Здесь мы просто пропускаем грани, у которых их рендер-штамп установлен в качестве штампа текущего кадра.
Для регистрации грани на рендеринг вызыввем функцию RenderFace на рендер-кэше, которому данная грань принадлежит. Данный рендер-кэш содержит материал, который будет применён к данной грани. В качестве вводных параметров передаются 3 индекса (indices) вершин, образующих грань. Таким образом даём знать DirectX, какие вершины из вершинного буфера будут использованы для рендеринга данной грани.
Закрыть
noteПримечание

Данная проверка на отсечение не даёт 100% эффективного осечения невидимых граней. В ряде случаев объекты и грани могут частично перекрываться двумя и более перекрывающими объёмами, и, по логике движка, тем не менее оказаться видимыми (см. Рис.3).


Готовим сцену к рендерингу

Фрагмент SceneManager.cpp (Проект Engine)
...
	// Set an identity world transformation matrix to render around the origin.
	// Устанавливаем мировую матрицу идентичности для рендеринга относительно
	// начала координат.
	D3DXMATRIX world;
	D3DXMatrixIdentity( &world );
	g_engine->GetDevice()->SetTransform( D3DTS_WORLD, &world );

	// Set the scene vertex buffer as the current device data stream.
	// Назначаем вершинный буфер сцены в качестве потока данных объекта устройства Direct3D.
	g_engine->GetDevice()->SetStreamSource( 0, m_sceneVertexBuffer, 0, VERTEX_FVF_SIZE );
	g_engine->GetDevice()->SetFVF( VERTEX_FVF );

	// Tell all the render caches to end rendering. This will cause them to
	// send their faces to be render to the video card.
	// Командуем всем рендер-кэшам заканчивать рендеринг. Это приведёт к отправке ими всех
	// граней в видеокарту, на рендеринг.
	m_renderCaches->Iterate( true );
	while( m_renderCaches->Iterate() )
		m_renderCaches->GetCurrent()->End();
...

Прежде чем рендерить сцену, необходимо сперва установить единичную матрицу (identity matrix) в качестве мировой, что обеспечит рендеринг сцены в точке начала координат 30-пространства (0, 0, 0).
Далее назначаем вершинам источник потока данных (stream source, он же device data stream, он же вершинный поток (англ. "vertex stream"). Тем самым указываем DirectX, откуда брать вершины для рендеринга. В нашем случае назначаем в качестве источника потока данных вершинный буфер нашей сцены путём вызова функции SetStreamSource. Это даёт DirectX доступ к вершинам, используемым валидными гранями меша нашей сцены.
Строкой ниже назначаем в качестве гибкого формата вершин (FVF) наш авторский формат вершин VERTEX_FVF, созданный в одной из предыдущих глав.
Для выполнения рендеринга вызываем функцию End на каждом рендер-кэше. Здесь каждому рендер-кэшу назначается материал и текстура. Затем его индексы отправляются в DirectX на рендеринг. DirectX, в свою очередь, использует эти индексы для вызова вершин из вершинного буфера (который мы только что прописали в качестве вершинного потока). В теории, как только это произойдёт, все грани, помеченные как видимые в данном кадре, готовы к рендерингу в выбранный render-target (DirectX-сущность, чаще всего представляющая собой экранный бэк-буфер).

Рендерим сцену

Пробил час отрендерить все динамические объекты сцены, помеченные как видимые. Выполняем уже знакомую итерацию через связный список m_dynamicObjects, проверяя каждый его элемент на видимость (уже в который раз). Логика всё та же: если объект успешно прошёл все проверки на собственную видимость, он отправляется на рендеринг.
Фрагмент SceneManager.cpp (Проект Engine)
...
	// Iterate through the list of dynamic objects.
	// Итерируем через список динамических объектов.
	m_dynamicObjects->Iterate( true );
	while( m_dynamicObjects->Iterate() )
	{
		// Check if the object is visible.
		// Проверяем, видим ли объект.
		if( m_dynamicObjects->GetCurrent()->GetVisible() == false )
			continue;

		// Check if the object's bounding sphere is inside the view frustum.
		// Проверяем, расположена ли ограничивающая сфера объекта внутри
		// усечённой пирамиды вида.
		if( m_viewFrustum.IsSphereInside( m_dynamicObjects->GetCurrent()->GetBoundingSphere()->centre,
			m_dynamicObjects->GetCurrent()->GetBoundingSphere()->radius ) == false )
			continue;

		// Iterate through the list of visible occluders.
		// Итерируем список видимых оклюдеров.
		bool occluded = false;
		m_visibleOccluders->Iterate( true );
		while( m_visibleOccluders->Iterate() )
		{
			// Ignore hidden occluders.
			// Игнориуем спрятанные оклюдеры.
			if( m_visibleOccluders->GetCurrent()->visibleStamp != m_frameStamp )
				continue;

			occluded = true;

			// Check the object's bounding sphere against the occlusion volume.
			// Проверяем ограничивающую сферу объекта на предмет попадания внутрь
			// перекрывающего объёма.
			m_visibleOccluders->GetCurrent()->planes->Iterate( true );
			while( m_visibleOccluders->GetCurrent()->planes->Iterate() )
			{
				if( D3DXPlaneDotCoord( m_visibleOccluders->GetCurrent()->planes->GetCurrent(),
					&m_dynamicObjects->GetCurrent()->GetBoundingSphere()->centre )
					< m_dynamicObjects->GetCurrent()->GetBoundingSphere()->radius )
				{
					occluded = false;
					break;
				}
			}

			// Break if the object is completely hidden by this occluder.
			// Прерываем, если объект полностью заслонён данным оклюдером.
			if( occluded == true )
				break;
		}

		// Ignore this object if it is occluded.
		// Игнорируем полностью заслонённый объект и продолжаем итерацию дальше.
		if( occluded == true )
			continue;

		// Render the object.
		// Рендерпм объект.
		m_dynamicObjects->GetCurrent()->Render();
	}
}
...

Как видим, сперва проверяем, заключена ли ограничивающая сфера объекта внутри усечённой пирамиды вида (view frustum). Если да, переходим к следующей проверке.
В этот раз в проверке участвуют оклюдеры и их перекрывающие объёмы (occluding volumes). Проверяем, находится ли ограничивающая сфера объекта за пределами перекрывающего объёма оклюдера (occluder's occlusion volume). Если да, то объект не заслонён оклюдером и допущен к рендерингу. Объекты, полностью заслонённые оклюдерами, пропускаем.

Интегрируем систему игровых объектов в движок

Принцип тот же, что и при интегрировании других систем.

Изменения в SceneObject.срр (Проект Engine)

  • Добавь инструкцию #include "Engine.h" в самом начале файла SceneObject.срр (проверь её наличие).

Изменения в Engine.h (Проект Engine)

  • Добавь строку
#include "SceneManager.h"

сразу после строки #include "RenderCache.h":
Фрагмент Engine.h (Проект Engine)
...
//-----------------------------------------------------------------------------
// Engine Includes
//-----------------------------------------------------------------------------
#include "Resource.h"
#include "LinkedList.h"
#include "ResourceManagement.h"
#include "Geometry.h"
#include "Font.h"
#include "Scripting.h"
#include "DeviceEnumeration.h"
#include "Input.h"
#include "Network.h"
#include "SoundSystem.h"
#include "BoundingVolume.h"
#include "Material.h"
#include "Mesh.h"
#include "SceneObject.h"
#include "AnimatedObject.h"
#include "SpawnerObject.h"
#include "ViewFrustum.h"
#include "RenderCache.h"
#include "SceneManager.h"
#include "CollisionDetection.h"
#include "State.h"
...


  • Добавь новый член
SceneManager *m_sceneManager;// Scene manager.

в секцию private класса Engine, сразу после строки
SoundSystem *m_soundSystem; // Sound system.
Фрагмент Engine.h (Проект Engine)
...
private:
	bool m_loaded; // Indicates if the engine is loading.
					// Флаг показывает, загружен ли движок
	HWND m_window; // Main window handle.
					// Дескриптор главного окна приложения
	bool m_deactive; // Indicates if the application is active or not.
					// Флаг активности приложения

	EngineSetup *m_setup; // Copy of the engine setup structure.
					// Копия структуры EngineSetup
	IDirect3DDevice9 *m_device;
	D3DDISPLAYMODE m_displayMode;
	ID3DXSprite *m_sprite;
	unsigned char m_currentBackBuffer;

	LinkedList< State > *m_states; // Связный список (Linked list) стейтов.
	State *m_currentState; // Указатель на текущий стейт.
	bool m_stateChanged; // Флаг показывает, изменён ли стейт в текущем кадре.
	ResourceManager< Script > *m_scriptManager; // Менеджер скриптов.
	ResourceManager< Material > *m_materialManager;
	ResourceManager< Mesh > *m_meshManager;

	Input *m_input;
	Network *m_network; // Объект класса Network.
	SoundSystem *m_soundSystem; // Объект класса SoundSystem.
	SceneManager *m_sceneManager; // Scene manager.
};
...


  • Добавь новый член
SceneManager *GetSceneManager();

в секцию public класса Engine, сразу после строки
SoundSystem *GetSoundSystem();
Фрагмент Engine.h (Проект Engine)
...
//-----------------------------------------------------------------------------
// Engine Class
//-----------------------------------------------------------------------------
class Engine
{
public:
	Engine( EngineSetup *setup = NULL );
	virtual ~Engine();

	void Run();

	HWND GetWindow();
	void SetDeactiveFlag( bool deactive );
	float GetScale();
	IDirect3DDevice9 *GetDevice();
	D3DDISPLAYMODE *GetDisplayMode();
	ID3DXSprite *GetSprite();

	void AddState( State *state, bool change = true );
	void RemoveState ( State *state );
	void ChangeState( unsigned long id );
	State *GetCurrentState();
	ResourceManager< Script > *GetScriptManager();
	ResourceManager< Material > *GetMaterialManager();
	ResourceManager< Mesh > *GetMeshManager();
	Input *GetInput();
	Network *GetNetwork();
	SoundSystem *GetSoundSystem();
	SceneManager *GetSceneManager();
...

Функция GetSceneManager предоставляет глобальный доступ к приватному члену m_sceneManager класса Engine.

Изменения в Engine.срр (Проект Engine)

  • В конструкторе класса Engine добавь строки
// Create the scene manager.
	m_sceneManager = new SceneManager( m_setup->scale, m_setup->spawnerPath );

в конец реализации конструктора класса Engine, сразу после строки
m_soundSystem = new SoundSystem( m_setup->scale );
Фрагмент Engine.cpp (Проект Engine)
...
	// Создаём экземпляр класса Input.
	m_input = new Input( m_window );

	// Создаём экземпляр класса Network.
	m_network = new Network( m_setup->guid, m_setup->HandleNetworkMessage );

	m_soundSystem = new SoundSystem( m_setup->scale );

	// Create the scene manager.
	m_sceneManager = new SceneManager( m_setup->scale, m_setup->spawnerPath );

	// Seed the random number generator with the current time.
	// Стартуем генератор сулчайных чисел на основе текущего времени.
	srand( timeGetTime() );
...

При создании менеджера сцены в новый инстанс класса SceneManager передаём масштаб (scale), с которым работаем, и указатель на связный список скриптов спаунеров игровых объектов.

  • В деструкторе класса Engine добавь строку
SAFE_DELETE( m_sceneManager );

в начало списка уничтожаемых объектов.
Фрагмент Engine.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// The engine class destructor.
//-----------------------------------------------------------------------------
Engine::~Engine()
{
	// Ensure the engine is loaded.
	// Проверяем, загружен ли движок.
	if( m_loaded == true )
	{
		// Everything will be destroyed here (such as the DirectX components).
		// Здесь всё уничтожаем.
		if( m_currentState != NULL )
		{
			m_currentState->Close();
		}

		// Уничтожаем связные списки со стейтами.
		SAFE_DELETE( m_states );

		SAFE_DELETE( m_sceneManager );
		SAFE_DELETE( m_soundSystem );
		SAFE_DELETE( m_network );
		SAFE_DELETE( m_input );
		SAFE_DELETE( m_meshManager);
		SAFE_DELETE( m_materialManager);
...


  • В функции Run добавь строки
// Update the scene.
m_sceneManager->Update( elapsed, viewer.viewer->GetViewMatrix() );

в цикле проверки текущего вьюера на валидность:
Фрагмент Engine.cpp (Проект Engine)
...
				// Запрос вьюера текущего стейта (если таковой имеется).
				if( m_currentState != NULL )
				{
					m_currentState->RequestViewer( &viewer );
				}

				if( viewer.viewer != NULL ) // Проверяем, валиден ли вьюер.
				{
					// Update the scene.
					m_sceneManager->Update( elapsed, viewer.viewer->GetViewMatrix() );

					// Устанавливаем трансформацию вида (view transformation).
					m_device->SetTransform( D3DTS_VIEW, viewer.viewer->GetViewMatrix() );

					// Обновляем объект 3D-слушателя (3D sound listener).
					m_soundSystem->UpdateListener( viewer.viewer->GetForwardVector(),
						viewer.viewer->GetTranslation(), viewer.viewer->GetVelocity() );
				}
...


  • В функции Run добавь строки
// Render the scene, if there is a valid viewer.
					if( viewer.viewer != NULL )
						m_sceneManager->Render( elapsed, viewer.viewer->GetTranslation() );

между тегами BeginScene и EndScene:
Фрагмент Engine.cpp (Проект Engine)
...
				// Подготавливаем сцену.
				m_device->Clear( 0, NULL, viewer.viewClearFlags, 0, 1.0f, 0 );
				if( SUCCEEDED( m_device->BeginScene() ) )
				{
					// Render the scene, if there is a valid viewer.
					if( viewer.viewer != NULL )
						m_sceneManager->Render( elapsed, viewer.viewer->GetTranslation() );

					// Рендерим текущий стейт, если таковой имеется.
					if( m_currentState != NULL )
						m_currentState->Render();

					// Заканчиваем готовить сцену и показываем её.
					m_device->EndScene();
					m_device->Present( NULL, NULL, NULL, NULL );
...


  • Добавь реализацию функции (метода) GetSceneManager в конец Engine.cpp:

Фрагмент Engine.cpp (Проект Engine)
...
//-----------------------------------------------------------------------------
// Returns a pointer to the scene manager.
//-----------------------------------------------------------------------------
SceneManager *Engine::GetSceneManager()
{
	return m_sceneManager;
}

Готово! Теперь менеджер сцены полностью интегрирован в движок и готов к загрузке сцен.

Тестовая перекомпиляция Engine.lib

Для проверки работосопособности исходного кода, добавленного в этой Главе, перекомпилируем исходный код Проекта Engine:
  • В Обозревателе решений щёлкаем правой кнопкой мыши по значку Проекта Engine. Во всплывающем меню выбираем "Перестроить".
По окончании компиляции в панели "Вывод" (в нижней части главного окна IDE) будет представлен отчёт (лог) об успешной (либо неуспешной) компиляции. В нашем случае компиляция прошла успешно.
Полученная в результате компиляции двоичная библиотека Engine.lib перезаписывается по тому же пути (там же её будет искать тестовое приложение из Проекта Test).

Итоги

Воу! Удивительно, но это компилируется (в Главе 1.18 дадим ссылку на исходники Проекта). В принципе, движок готов. Осталось его потестить. Для это нам требуется тестовое приложение и меш сцены. Читай об этом уже в следующей Главе.

Источники


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


ДАЛЕЕ ==> Кодим 3D FPS DX9. 1.18 Создаём меш сцены

Последние изменения страницы Среда 12 / Октябрь, 2022 13:07:27 MSK

Последние комментарии wiki

No records to display

Search Wiki Page

Точное совпадение

Категории

|--> C#
|--> C++