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

//-----------------------------------------------------------------------------
// File: CollisionDetection.h
// Provides basic collision detection in a 3D environment that includes both
// static geometry and dynamic objects.
// Обеспечивает простое определение столкновений в 3D-пространстве для статичных
// и динамических объектов.
//
// Note: This uses an adaptation of the algorithm from the Improved Collision
//       Detection and Response article written by Kasper Fauerby.
// Здесь применяется адаптированный алгоритм из статьи Kasper Fauerby
// "Улучшенное определение столкновений и ответная реакция"
//
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#ifndef COLLISION_H
#define COLLISION_H

//-----------------------------------------------------------------------------
// Collision Data Structure
//-----------------------------------------------------------------------------
struct CollisionData
{
	float scale; // Scale used by the calling scene manager.
				// Масштаб, используемый при вызове менеджера сцены
	float elapsed; // Elapsed time for the current frame.
				// Время, в течение которого текущий кадр выводился на экран
	unsigned long frameStamp; // Current frame stamp according to the scene manager.
					// Штамп текущего кадра (согласно менеджеру сцены)

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

	D3DXVECTOR3 translation; // Translation in ellipsoid space.
					// Трансляция (=текущая позиция) пространства эллипсоида
	D3DXVECTOR3 velocity; // Velocity in ellipsoid space.
					// Скорость пространства эллипсоида
	D3DXVECTOR3 normalizedVelocity; // Normalized velocity in ellipsoid space.
				// Нормализованный вектор скорости пространства эллипсоида

	D3DXVECTOR3 gravity; // Gravity vector, which will be converted to ellipsoid space.
				// Вектор гравитации, который будет преобразован в пространство эллипсоида

	bool collisionFound; // Indicates if a collision has been found.
			// Флаг детектирования столкновения
	float distance; // Distance to the point of collision.
			// Расстояние до точки столкновения
	D3DXVECTOR3 intersection; // Actual intersection point where the collision occured.
			// Точка, в которой произошло столкновение
};

//-----------------------------------------------------------------------------
// Returns the lowest root of a quadratic equation.
// Возвращает наименьший корень квадратичного уравнения
//-----------------------------------------------------------------------------
inline float GetLowestRoot( float a, float b, float c, float max )
{
	// Calculate the determinant, then get the square root of it if it's valid.
	// Вычисляем детерминант, затем, если он валиден, извлекаем из него квадратный корень
	float determinant = b * b - a * c;
	if( determinant < 0.0f )
		return 0.0f;
	determinant = (float)sqrt( determinant );

	// Calculate the first root and ensure it is within the bounds.
	// Вычисляем первый корень и проверяем, что он находится в корректных пределах
	float root1 = ( b + determinant ) / a;
	if( root1 <= 0.0f || root1 > max )
		root1 = max + 1.0f;

	// Calculate the second root and ensure it is within the bounds.
	// Вычисляем второй корень и проверяем, что он находится в корректных пределах
	float root2 = ( b - determinant ) / a;
	if( root2 <= 0.0f || root2 > max )
		root2 = max + 1.0f;

	// Get the lowest of the two roots.
	// Определяем наименьший из двух корней
	float root = min( root1, root2 );

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

	return root;
}

//-----------------------------------------------------------------------------
// Checks a single face for intersection.
// Проверяем грань на пересечение
//-----------------------------------------------------------------------------
inline void CheckFace( CollisionData *data, D3DXVECTOR3 vertex0, D3DXVECTOR3 vertex1, D3DXVECTOR3 vertex2 )
{
	// Create a plane from the face's vertices.
	// Создаём плоскость на основе трёх вершин грани
	D3DXPLANE plane;
	D3DXPlaneFromPoints( &plane, &vertex0, &vertex1, &vertex2 );

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

	// Ensure the plane is facing the velocity vector (i.e. ignore back faces).
	// Убеждаемся, что плоскость обращена "лицевой" стороной к вектору скорости
	// (то есть игнорируем обратные (=изнаночные) поверхности)
	if( angle > 0.0f )
		return;

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

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

	// Get interval of plane intersection
	// Получаем временной интервал пересечения плоскости
	float time0, time1;
	bool embedded = false;

	// Cache this as we're going to use it a few times below
	// Кэшируем, т.к. будем всё это юзать повторно (см. код ниже)
	float normalDotVelocity = D3DXVec3Dot( &planeNormal, &data->velocity );

	// Check if the sphere is travelling parallel to the plane.
	// Проверяем случай, когда сфера движется параллельно плоскости
	if( normalDotVelocity == 0.0f )
	{
		// If the sphere is not embedded in the plane, then it cannot collide.
		// Если сфера нигде не пересекает плоскость, то данные объекты нигде не сталкиваются
		if( fabs( signedPlaneDistance ) >= 1.0f )
			return;
		else
		{
			// The sphere is embedded in plane, therefore it will collide
			// for the entire time frame.
			// Сфера пересекает плоскость. Значит в данном кадре они столкнулись
			embedded = true;
			time0 = 0.0f;
			time1 = 1.0f;
		}
	}
	else
	{
		// Calculate the time frame of intersection.
		// Вычисляем время длительности кадра со столкновением
		time0 = ( -1.0f - signedPlaneDistance ) / normalDotVelocity;
		time1 = ( 1.0f - signedPlaneDistance ) / normalDotVelocity;

		// Ensure time0 is less than time1.
		// Проверяем, что время 0 меньше, чем время 1
		if( time0 > time1 )
		{
			float swap = time1;
			time1 = time0;
			time0 = swap;
		}

		// If the intersection time frame is out of range, then it cannot collide.
		// Если время кадра пересечения выходит за пределы нужного интервала,
		// то данные объекты не могут сталкиваться.
		if( time0 > 1.0f || time1 < 0.0f )
			return;

		// Normalize the time frame.
		// Нормализуем время кадра
		if( time0 < 0.0f ) time0 = 0.0f;
		if( time1 < 0.0f ) time1 = 0.0f;
		if( time0 > 1.0f ) time0 = 1.0f;
		if( time1 > 1.0f ) time1 = 1.0f;
	}

	// Variables used for tracking if an intersection occured, where it happened, and when.
	// Переменные, применяемые для отслеживания пересечений, определения места и времени
	bool intersectFound = false;
	D3DXVECTOR3 intersection;
	float intersectTime = 1.0f;

	// Check if the sphere is embedded in the plane.
	// Проверяем случай, когда сфера пересекает плоскость.
	if( embedded == false )
	{
		// Get the plane intersection point at time0.
		// Получаем точку пересечения во временной отметке time0
		D3DXVECTOR3 planeIntersectionPoint = ( data->translation - planeNormal ) + data->velocity * time0;

		// Get the vectors of two of the face's edges.
		// Получаем векторы обоих углов рёбер грани
		D3DXVECTOR3 edge0 = vertex1 - vertex0;
		D3DXVECTOR3 edge1 = vertex2 - vertex0;

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

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

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

		// Take the bitwise AND of z and the complement of the inclusive OR of x and y,
		// then bitwise AND the result with 0x80000000 and return it. A bitwise result
		// of zero equals false, while any other value equals true.
		// Получаем битовое И z-координаты и дополнительно включаем ИЛИ x и y координат.
		// Затем объединяем результат битовым И с 0x80000000 и возвращаем его.
		// Двоичный 0 означает FALSE. Любое другое значение - TRUE.
		if( ( ( (unsigned int&)z & ~( (unsigned int&)x | (unsigned int&)y ) ) & 0x80000000 ) != 0 )
		{
			intersectFound = true;
			intersection = planeIntersectionPoint;
			intersectTime = time0;
		}
	}

	// Check if a collision has been found yet.
	// Проверяем, не было ли найдено столкновение ранее
	if( intersectFound == false )
	{
		// Get the squared length of the velocity vector.
		// Получаем квадрат длины вектора скорости
		float squaredVelocityLength = D3DXVec3LengthSq( &data->velocity );

		// A quadratic equation has to be solved for each vertex and edge in the face.
		// The following variables are used to build each quadratic equation.
		// Квадратичное уравнение было решено для каждой вершины и ребра грани.
		// Следующие переменные применяются для построения квадратичных уравнений.
		float a, b, c;

		// Used for storing the result of each quadratic equation.
		// Используется для сохранения результата каждого квадратичного уравнения
		float newTime;

		// First check againts the vertices.
		// Сперва проверяем для вершин.
		a = squaredVelocityLength;

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

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

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

		// Check the edge from vertex0 to vertex1.
		// Проверяем ребро между вершинами 0 и 1
		D3DXVECTOR3 edge = vertex1 - vertex0;
		D3DXVECTOR3 vectorSphereVertex = vertex0 - data->translation;
		float squaredEdgeLength = D3DXVec3LengthSq( &edge );
		float angleEdgeVelocity = D3DXVec3Dot( &edge, &data->velocity );
		float angleEdgeSphereVertex = D3DXVec3Dot( &edge, &vectorSphereVertex );

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

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

		// Check the edge from vertex1 to vertex2.
		// Проверяем ребро между вершинами 1 и 2
		edge = vertex2 - vertex1;
		vectorSphereVertex = vertex1 - data->translation;
		squaredEdgeLength = D3DXVec3LengthSq( &edge );
		angleEdgeVelocity = D3DXVec3Dot( &edge, &data->velocity );
		angleEdgeSphereVertex = D3DXVec3Dot( &edge, &vectorSphereVertex );

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

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

		// Check the edge from vertex2 to vertex0.
		// Проверяем ребро между вершинами 2 и 0
		edge = vertex0 - vertex2;
		vectorSphereVertex = vertex2 - data->translation;
		squaredEdgeLength = D3DXVec3LengthSq( &edge );
		angleEdgeVelocity = D3DXVec3Dot( &edge, &data->velocity );
		angleEdgeSphereVertex = D3DXVec3Dot( &edge, &vectorSphereVertex );

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

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

	// Check if an intersection occured.
	// Если пересечение произошло...
	if( intersectFound == true )
	{
		// Get the distance to the collision (i.e. time along the velocity vector).
		// Получаем расстояние до столкновения (например, примени в вычислениях
		// время движения вдоль вектора скорости)
		float collisionDistance = intersectTime * D3DXVec3Length( &data->velocity );

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

//-----------------------------------------------------------------------------
// Perfrom collision detection between the give object and the scene.
// Выполняет определение столкновений между данным объектом и сценой
//-----------------------------------------------------------------------------
inline void CollideWithScene( CollisionData *data, Vertex *vertices, SceneFace *faces,
	unsigned long totalFaces, LinkedList< SceneObject > *objects, unsigned long recursion = 5 )
{
	// Calculate the epsilon distance (taking scale into account).
	// The epsilon distance is a very short distance that is considered negligable.
	// Вычисляем расстояние с учётом масштаба
	float epsilon = 0.5f * data->scale;

	// Indicate that a collision has not been found.
	// Ставим флаг определения столкновения в FALSE
	data->collisionFound = false;

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

	// Go through all of the faces.
	// Проходим через все грани
	D3DXVECTOR3 vertex0, vertex1, vertex2;
	for( unsigned long f = 0; f < totalFaces; f++ )
	{
		// Skip this face if its material is set to ignore rays.
		// Пропускаем грани, у которых материал игнорирует лучи
		if( faces[f].renderCache->GetMaterial()->GetIgnoreRay() == true )
			continue;

		// Get a copy of this face's vertices in ellipsoid space.
		// Создаём копии вершин грани в пространстве эллипсоида
		vertex0.x = vertices[faces[f].vertex0].translation.x / data->object->GetEllipsoidRadius().x;
		vertex0.y = vertices[faces[f].vertex0].translation.y / data->object->GetEllipsoidRadius().y;
		vertex0.z = vertices[faces[f].vertex0].translation.z / data->object->GetEllipsoidRadius().z;
		vertex1.x = vertices[faces[f].vertex1].translation.x / data->object->GetEllipsoidRadius().x;
		vertex1.y = vertices[faces[f].vertex1].translation.y / data->object->GetEllipsoidRadius().y;
		vertex1.z = vertices[faces[f].vertex1].translation.z / data->object->GetEllipsoidRadius().z;
		vertex2.x = vertices[faces[f].vertex2].translation.x / data->object->GetEllipsoidRadius().x;
		vertex2.y = vertices[faces[f].vertex2].translation.y / data->object->GetEllipsoidRadius().y;
		vertex2.z = vertices[faces[f].vertex2].translation.z / data->object->GetEllipsoidRadius().z;

		// Check for collision with this face.
		// Проверяем данную грань на столкновение
		CheckFace( data, vertex0, vertex1, vertex2 );
	}

	// Create a list of hit ghost objects and a list of the distances to them.
	// Создаём список объектов-призраков (у которых столкновения не определяем)
	// и список расстояний до них
	LinkedList< SceneObject > *ghostHits = new LinkedList< SceneObject >;
	LinkedList< float > *ghostDistances = new LinkedList< float >;

	// Variables used for the following object collision check.
	// Переменные, используемые данным объектом для определения столкновений
	D3DXVECTOR3 translation, velocity, vectorColliderObject, vectorObjectCollider, vectorObjectRadius;
	float distToCollision, colliderRadius, objectRadius;

	// Go through the list of objects.
	// Проходим через список объектов
	SceneObject *hitObject = NULL;
	SceneObject *nextObject = objects->GetFirst();
	while( nextObject != NULL )
	{
		// Skip this object if it is the collider. It can't check against itself.
		// Проверяем, не является ли данный объект тем, что проверяется на столкновение.
		// Объект незачем проверять на столкновение с самим собой
		if( nextObject != data->object )
		{
			// Get the translation and velocity of this object in ellipsoid space.
			// Получаем трансляцию и скорость данного объекта в пространстве эллипсоида
			translation.x = nextObject->GetTranslation().x / data->object->GetEllipsoidRadius().x;
			translation.y = nextObject->GetTranslation().y / data->object->GetEllipsoidRadius().y;
			translation.z = nextObject->GetTranslation().z / data->object->GetEllipsoidRadius().z;
			velocity.x = nextObject->GetVelocity().x / data->object->GetEllipsoidRadius().x;
			velocity.y = nextObject->GetVelocity().y / data->object->GetEllipsoidRadius().y;
			velocity.z = nextObject->GetVelocity().z / data->object->GetEllipsoidRadius().z;
			velocity *= data->elapsed;

			// Get the normalized vectors from the collider to this object and vice versa.
			// Получаем нориализованные векторы от сталкиваемого до проверямого объектов
			D3DXVec3Normalize( &vectorColliderObject, &( translation - data->translation ) );
			D3DXVec3Normalize( &vectorObjectCollider, &( data->translation - translation ) );

			// Calculate the radius of each ellipsoid in the direction to the other.
			// Вычисляем радиусы каждого эллипсоида, каждый из которых обращён друг к другу
			colliderRadius = D3DXVec3Length( &vectorColliderObject );
			vectorObjectRadius.x = vectorObjectCollider.x * nextObject->GetEllipsoidRadius().x / data->object->GetEllipsoidRadius().x;
			vectorObjectRadius.y = vectorObjectCollider.y * nextObject->GetEllipsoidRadius().y / data->object->GetEllipsoidRadius().y;
			vectorObjectRadius.z = vectorObjectCollider.z * nextObject->GetEllipsoidRadius().z / data->object->GetEllipsoidRadius().z;
			objectRadius = D3DXVec3Length( &vectorObjectRadius );

			// Check for collision between the two spheres.
			// Проверяем на столкновение две сферы
			if( IsSphereCollidingWithSphere( &distToCollision, data->translation, translation, velocity - data->velocity,
				colliderRadius + objectRadius ) == true )
			{
				// Check if the hit object is a ghost.
				// Проверяем, не является ли объект, с которым сталкиваемся, призраком
				if( nextObject->GetGhost() == true )
				{
					// If both object's are allowed to register collisions, then store a pointer to the hit object and the distance to hit it.
					// Если оба объекта допущены к определению столкновений, то сохраняем указатели на объект, с которым сталкиваемся
					// и расстояние до него
					if( nextObject->GetIgnoreCollisions() == false && data->object->GetIgnoreCollisions() == false )
					{
						ghostHits->Add( nextObject );
						ghostDistances->Add( &distToCollision );
					}
				}
				else
				{
					// Store the collision details, if necessary.
					// Сохраняем инфу по столкновению (при необходимости)
					if( data->collisionFound == false || distToCollision < data->distance )
					{
						data->distance = distToCollision;
						data->intersection = data->normalizedVelocity * distToCollision;
						data->collisionFound = true;

						// Store a pointer to the hit object.
						// Сохраняем указатель на объект
						hitObject = nextObject;
					}
				}
			}
		}

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

	// Iterate through the list of hit ghost objects and their collision distances.
	// Итерируем через список объектов-призраков и их расстояний опред. столкновений
	ghostHits->Iterate( true );
	ghostDistances->Iterate( true );
	while( ghostHits->Iterate() != NULL && ghostDistances->Iterate() != NULL )
	{
		// If the distance to hit the ghost object is less than the distance to the closets
		// real collision, then the ghost object has been hit.
		// Если расстояние опред. столкновения объекта-призрака меньше, чем расстояние до
		// ближайшего реального столкновения, то с объектом-призраком произошло столкновение.
		if( *ghostDistances->GetCurrent() < data->distance )
		{
			// Register the collision between both objects.
			ghostHits->GetCurrent()->CollisionOccurred( data->object, data->frameStamp );
			data->object->CollisionOccurred( ghostHits->GetCurrent(), data->frameStamp );
		}
	}

	// Destroy the ghost hits and distances lists.
	// Уничтожаем списки столкновений с объектами-призраками и их расстояниями
	// опред. столкновений
	ghostHits->ClearPointers();
	SAFE_DELETE( ghostHits );
	ghostDistances->ClearPointers();
	SAFE_DELETE( ghostDistances );

	// If no collision occured, then just move the full velocity vector.
	// Если столкновения не было, то двигаемся на полной скорости
	if( data->collisionFound == false )
	{
		data->translation = data->translation + data->velocity;
		return;
	}

	// Calculate the destination (i.e. the point the object was trying to get to).
	// Вычисляем пункт назначения (например точка объекта, которой пытаемся достичь)
	D3DXVECTOR3 destination = data->translation + data->velocity;

	// The new translation will be the point where the object actually ends up.
	// Новой трансляцией (=точкой назначения) будет точка, где объет заканчивается
	D3DXVECTOR3 newTranslation = data->translation;

	// Ignore the movement if the object is already very close to its destination.
	// Игнорируем движение, если объект находится слишком близко к точке назначения
	if( data->distance >= epsilon )
	{
		// Calculate the new velocity required to move the distance.
		// Вычисляем новую скорость, необходимую для прохождения расстояния
		D3DXVECTOR3 newVelocity = data->normalizedVelocity * ( data->distance - epsilon );

		// Find the new translation.
		// Находим новую трансляцию (=точку в пространстве)
		newTranslation = data->translation + newVelocity;

		// Adjust the polygon intersection point to taking into account that fact that
		// the object does not move right up to the actual intersection point.
		// Корректируем точку пересечения полигона, учитывая тот факт, что объект
		// движется не напрямую к точке пересечения
		D3DXVec3Normalize( &newVelocity, &newVelocity );
		data->intersection = data->intersection - newVelocity * epsilon;
	}

	// Check if the collision occured with an object.
	// Проверяем, произошло ли столкновение с объектом
	if( hitObject != NULL )
	{
		// Set the new translation of the object.
		// Назначаем объекту новую трансляцию
		data->translation = newTranslation;

		// Calculate and apply a push velocity so objects can push one another.
		// Вычисляем и применяем т.н. "скорость толкания", чтобы объекты могли толкать друг друга
		D3DXVECTOR3 push = ( hitObject->GetVelocity() + data->object->GetVelocity() ) / 10.0f;
		hitObject->SetVelocity( push );
		data->object->SetVelocity( push );

		// Register the collision between both objects, if they are allowed.
		// Регистрируем столкновение между обоими объектами, если это разрешено
		if( hitObject->GetIgnoreCollisions() == false && data->object->GetIgnoreCollisions() == false )
		{
			hitObject->CollisionOccurred( data->object, data->frameStamp );
			data->object->CollisionOccurred( hitObject, data->frameStamp );
		}

		return;
	}

	// Create a plane that wil act as the sliding plane.
	// Создаём плоскость, служащую в качестве плоскости отсечения
	D3DXVECTOR3 slidePlaneOrigin = data->intersection;
	D3DXVECTOR3 slidePlaneNormal;
	D3DXVec3Normalize( &slidePlaneNormal, &( newTranslation - data->intersection ) );
	D3DXPLANE slidingPlane;
	D3DXPlaneFromPointNormal( &slidingPlane, &slidePlaneOrigin, &slidePlaneNormal );

	// Calculate the new destination accouting for sliding.
	// Вычисляем новое расстояние, с учётом отсечения
	D3DXVECTOR3 newDestination = destination - slidePlaneNormal * ( D3DXVec3Dot( &destination, &slidePlaneNormal ) + slidingPlane.d );
	newDestination += slidePlaneNormal * epsilon;

	// Calculate the new velocity which is the vector of the slide.
	// Вычисляем новую скорость, представляющую собой вектор отсечения
	D3DXVECTOR3 newVelocity = newDestination - data->intersection;

	// Check if the new velocity is too short.
	// Проверяем случай, котда новый вектор скорости слишком короток
	if( D3DXVec3Length( &newVelocity ) <= epsilon )
	{
		// Since the velocity is too short, there is no need to continue
		// performing collision detection. So just set the new translation
		// and velocity, then return.
		// Раз скорость слишком мала, то нет смысла продолжать определение
		// столкновений. Поэтому просто назначим новые векторы трансляции
		// и скорости.
		data->translation = newTranslation;
		data->velocity = D3DXVECTOR3( 0.0f, 0.0f, 0.0f );

		return;
	}

	// Set the new translation and velocity.
	// Устанавливаем новые значения трансляции и скорости
	data->translation = newTranslation;
	data->velocity = newVelocity;

	// Perform another collision detection recurison if allowed.
	// Выполняем другие рекурсивные определения столкновений (если это разрешено)
	recursion--;
	if( recursion > 0 )
		CollideWithScene( data, vertices, faces, totalFaces, objects, recursion );
}

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

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

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

	// Now set the velocity to the gravity vector (in ellipsoid space).
	// Устанавливаем скорость вектора гравитации (в пространстве эллипсоида)
	data->velocity.x = data->gravity.x / data->object->GetEllipsoidRadius().x;
	data->velocity.y = data->gravity.y / data->object->GetEllipsoidRadius().y;
	data->velocity.z = data->gravity.z / data->object->GetEllipsoidRadius().z;

	// Perform another recursive collision detection to apply gravity.
	// Выполняем другое рекурсивное определение столкновений для применения вектора
	// гравитации
	CollideWithScene( data, vertices, faces, totalFaces, dynamicObjects );

	// Convert the object's new translation back out of ellipsoid space.
	// Конвертируем новую трансляцию объекта за пределами пространства эллипсоида
	data->translation.x = data->translation.x * data->object->GetEllipsoidRadius().x;
	data->translation.y = data->translation.y * data->object->GetEllipsoidRadius().y;
	data->translation.z = data->translation.z * data->object->GetEllipsoidRadius().z;

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

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

	// If the distance to the ray intersection is less than the radius
	// of the object along the y axis, then the object is embedded in
	// the ground. So just push the object up out of the ground.
	// Если расстояние до точки пересечения лучом меньше, чем радиус
	// объекта по оси y, то объект находится в земле или под землёй.
	// Поэтому вытолкнем объект на поверхность земли
	if( hitDistance < data->object->GetEllipsoidRadius().y )
		data->translation.y += data->object->GetEllipsoidRadius().y - hitDistance;

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

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

#endif

...
//-----------------------------------------------------------------------------
// Collision Data Structure
//-----------------------------------------------------------------------------
struct CollisionData
{
	float scale; // Scale used by the calling scene manager.
				// Масштаб, используемый при вызове менеджера сцены
	float elapsed; // Elapsed time for the current frame.
				// Время, в течение которого текущий кадр выводился на экран
	unsigned long frameStamp; // Current frame stamp according to the scene manager.
					// Штамп текущего кадра (согласно менеджеру сцены)

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

	D3DXVECTOR3 translation; // Translation in ellipsoid space.
					// Трансляция (=текущая позиция) пространства эллипсоида
	D3DXVECTOR3 velocity; // Velocity in ellipsoid space.
					// Скорость пространства эллипсоида
	D3DXVECTOR3 normalizedVelocity; // Normalized velocity in ellipsoid space.
				// Нормализованный вектор скорости пространства эллипсоида

	D3DXVECTOR3 gravity; // Gravity vector, which will be converted to ellipsoid space.
				// Вектор гравитации, который будет преобразован в пространство эллипсоида

	bool collisionFound; // Indicates if a collision has been found.
			// Флаг детектирования столкновения
	float distance; // Distance to the point of collision.
			// Расстояние до точки столкновения
	D3DXVECTOR3 intersection; // Actual intersection point where the collision occured.
			// Точка, в которой произошло столкновение
};
...

...
inline void PerformCollisionDetection( CollisionData *data, Vertex *vertices, SceneFace *faces, unsigned long totalFaces, LinkedList< SceneObject > *dynamicObjects )
...

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

#include "CollisionDetection.h"

...
//-----------------------------------------------------------------------------
// 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 "RenderCache.h"
#include "CollisionDetection.h"
#include "State.h"
...

//-----------------------------------------------------------------------------
// File: ViewFrustum.h
// Used to maintain a view frustum from the supplied view matrix.
// Обеспечивает усечённую пирамиду видимого пространства для
// данной матрицы вида.
//
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#ifndef VIEW_FRUSTUM_H
#define VIEW_FRUSTUM_H

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

	void SetProjectionMatrix( D3DXMATRIX projection );

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

private:
	D3DXMATRIX m_projection; // Pointer to a projection matrix.
				// Указатель на матрицу проекции.
	D3DXPLANE m_planes[5]; // Five planes of the view frustum (near plane is ignored).
			// 5 плоскостей усечённой пирамиды вида (ближнюю плоскость игнорируем).
};

#endif

//-----------------------------------------------------------------------------
// File: ViewFrustum.cpp
//	Реализация функций, объявленных в заголовочном файле ViewFrustum.h.
// Refer to the ViewFrustum.h interface for more details.
//
// Programming a Multiplayer First Person Shooter in DirectX
// Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#include "Engine.h"

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

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

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

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

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

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

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

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

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

		return false;
	}

	return true;
}

//-----------------------------------------------------------------------------
// Returns true if the given box is inside the view frustum.
// Возвращает TRUE, когда данный бокс находится внутри пирамиды вида.
//-----------------------------------------------------------------------------
bool ViewFrustum::IsBoxInside( D3DXVECTOR3 translation, D3DXVECTOR3 min, D3DXVECTOR3 max )
{
	return IsBoxInside( min + translation, max + translation );
}

//-----------------------------------------------------------------------------
// Returns true if the given sphere is inside the view frustum.
// Возвращает TRUE, когда данная сфера находится внутри пирамиды вида.
//-----------------------------------------------------------------------------
bool ViewFrustum::IsSphereInside( D3DXVECTOR3 translation, float radius )
{
	for( char p = 0; p < 5; p++ )
		if( D3DXPlaneDotCoord( &m_planes[p], &translation ) < -radius )
			return false;

	return true;
}

#include "ViewFrustum.h"

...
//-----------------------------------------------------------------------------
// 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 "CollisionDetection.h"
#include "State.h"
...

name = The name of the scene. 
Имя сцены.
gravity = A 3D vector defining the force of gravity.
3D-вектор, определяющий силу притяжения.

ambient_light = Ambient light level in the scene.
Уровень рассеянного света (Ambient light) в сцене.
sun_direction = Direction of the sun's light.
Направление солнечного света.

fog_colour = Colour of the fog in the scene.
Цвет тумана в сцене. При желании можно повсюду распылить зелёный хлор...
fog_density = How dense (thick) the fog is. High values indicate thicker fog.
Насколько плотен туман. Чем больше значение, тем плотнее туман.

mesh = Name of the mesh file for the scene.
Имя файла меша игровой сцены.
mesh_path = Path to locate the scene's mesh file.
Путь до файла меша игровой сцены.

max_faces = Maximum number of faces that any given scene leaf can contain.
Максимальное число граней, которое может содержать листок сцены.
max_half_size = Maximum half size that any given scene leaf can be.
Макс. половинный размер (half size), который может иметь каждый из листков сцены.

Note: A scene leaf will be divided if the total number of faces in the leaf is greater
than max_faces and the size of the leaf divided by two (i.e. the leaf's "half size")
is greater than max_half_size. Both conditions must evaluate to true for division to occur.
Примечание: Листок сцены (scene leaf) будет далее разделён, если общее число граней в листке
больше, чем параметр max_faces, а также размер листка, поделённый надвое (т.е. половинный
размер листка) больше, чем параметр max_half_size. Для проведения разделения должны выполняться
оба условия одновременно.

#begin

name          string "city"
gravity       vector 0.0 -9.81 0.0

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

fog_colour    colour 0.8 0.8 0.8 1.0
fog_density   float  0.02

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

max_faces     number 32
max_half_size float  16.0

#end