Введение
HSR есть основа любого 3D Engine , сильно влияющая на скорость самого движка . Существует множество вариантов (indoor, outdoor, space).
Но эта статья будет посвящена удалению невидимых ОБЬЕКТОВ , а не удалению невидимых ПОВЕРХНОСТЕЙ . Т.е. сначала удаляются невидимые обьекты , а уж потом выполняется обычное HSR .
Будет сформулировано понятие ВИДИМОГО ОБЬЕКТА , которое позволит полностью исключить для него такую операцию , как клипинг .
Что есть обьект ?
Основными компонентами обьекта можно назвать массив вершин полигонов и массив индексов , а также их число ; еще может быть включена позиция в мировом пространстве , ориентация и т.д.
БАЗОВЫЕ КЛАССЫ
VECTOR Class
class
VECTOR{ public:// CONSTRUCTORS
VECTOR();VECTOR(
float _X, float _Y, float _Z);// DESTRUCTOR
~VECTOR()
// METHODS
float CalculateMagnetude();
// DATA
float X; // X Координата.
float Y; // Y Координата.
float Z; // Z Координата.
};
VECTOR::VECTOR()
{
X = 0.0f;
Y = 0.0f;
Z = 0.0f;
}
VECTOR::VECTOR(
float _X, float _Y, float _Z){
X = _X;
Y = _Y;
Z = _Z;
}
VECTOR::~VECTOR()
{
}
float
VECTOR::CalculateMagnetude(){
return (float)sqrt(((X * X) + (Y * Y) + (Z * Z)));
}
VERTEX
ClassКласс VERTEX инициализирует вершины , которые формируют полигоны , входящие в обьект .
class
VERTEX{
public:
// CONSTRUCTORS
VERTEX();
VERTEX(
const float&,const float&,
const float&,
const float&,
const float&,
const VECTOR&);
// DESTRUCTOR
~VERTEX();
// DATA
float
X; // X Coordinate.float
Y; // Y Coordinate.float
Z; // Z Coordinate.float
U; // U Texture Coordinate.float
V; // V Texture Coordinate.
VECTOR Normal;
// Vertex Normal.};
VERTEX::VERTEX()
{
X = 0.0f;
Y = 0.0f;
Z = 0.0f;
U = 0.0f;
V = 0.0f;
}
VERTEX::VERTEX(
const float& _X,const float& _Y,
const float& _Z,
const float& _U,
const float& _V,
const VECTOR& _Normal)
{
X = _X;
Y = _Y;
Z = _Z;
U = _U;
V = _V;
Normal = _Normal;
}
VERTEX::~VERTEX()
{
}
MATRIX
ClassКласс MATRIX инициализирует матрицу 4x4 , которая будет использоваться для Transformations. В этой статье все преобразования будут выполнены именно этим стандартным способом .
class
MATRIX{
public:
// CONSTRUCTORS
MATRIX();
// DESTRUCTOR
~MATRIX();
// METHODS
void
SetToIdentity();void
Translate( const float&,const float&,
const float&);
// DATA
float
Data[4][4]; // Данные Matrix.};
MATRIX::MATRIX()
{
memset(Data, 0, (
sizeof(float) * 16));}
MATRIX::~MATRIX()
{
}
void
MATRIX::SetToIdentity(){
memset(Data, 0, (
sizeof(float) * 16));
Data[0][0] = 1.0f;
Data[1][1] = 1.0f;
Data[2][2] = 1.0f;
Data[3][3] = 1.0f;
}
void
MATRIX::Translate( const float& X,const float& Y,
const float& Z)
{
SetToIdentity();
Data[3][0] = X;
Data[3][1] = Y;
Data[3][2] = Z;
}
SPHERE
ClassПростой класс , определяющий сферу . Основными элементами сферы являются позиция в мировом пространстве и радиус .
class
SPHERE{
public:
// CONSTRUCTORS
SPHERE();
SPHERE(const VECTOR&, cosnt float&);
// DESTRUCTOR
~SPHERE()
// DATA
VECTOR Position; // Позиция .
float Radius; // Радиус Sphere.
};
SPHERE::SPHERE()
{
Radius = 0.0f;
}
SPHERE::SPHERE(
cosnt VECTOR& _Position, const float& _Radius){
Position = _Position,
Radius = _Radius;
}
SPHERE::~SPHERE()
{
}
PLANE
ClassКласс PLANE определяет плоскость , которая находится в области видимости - View Frustum .
class
PLANE{
public:
// CONSTRUCTORS
PLANE();
PLANE(const VECTOR&, const float&);
// DESTRUCTOR
// DATA
VECTOR Normal;
// Plane Normal.float
Distance; // Plane Distance.};
PLANE::PLANE()
{
Distance = 0.0f;
}
PLANE::PLANE(
const VECTOR& _Normal, const float& _Distance){
Normal = _Normal;
Distance = _Distance;
}
FRUSTUM
ClassКласс FRUSTUM состоит из 6 плоскостей .
class
FRUSTUM{
public:
// CONSTRUCTORS
FRUSTUM();
// DESTRUCTORS
~FRUSTUM();
// DATA
PLANE NearPlane;
// Ближняя Clipping Plane.PLANE FarPlane;
// Дальняя Clipping Plane.PLANE LeftPlane;
// Левая Clipping Plane.PLANE RightPlane;
// Правая Clipping Plane.PLANE TopPlane;
// Верхняя Clipping Plane.PLANE BottomPlane;
// Нижняя Clipping Plane.};
FRUSTUM::FRUSTUM()
{
}
FRUSTUM::~FRUSTUM()
{
}
OBJECT
ClassЭто самый важный класс . В него входит указатель на класс вершин (VERTEX* Vertices). Также в классе хранится общее число вершин (int NumberOfVertices). Имеется указатель на массив индексов (unsigned short* Indices) , который будет формировать полигоны . Хранится общее число таких индексов (int NumberOfIndices). Хранится позиция обьекта в мировом пространстве . Имеется предварительно вычисленная сфера ограничений . В класс входят 2 метода :
void OBJECT::Load(const char* Filename) - Это загрузка вершин и индексов из файла . ComputeBoundingSphere() - вычисление сферы ограничений . Этот метод нужно вызывать всякий раз , как меняется положение обьекта . Вычисляется расстояние от центра сферы до каждой вершины , и наибольшее значение становится радиусом . Локальная координата сферы - (0, 0, 0) .
class
OBJECT{
public:
// CONSTRUCTORS
OBJECT();
// DESTRUCTORS
~OBJECT();
// METHODS
void Load(const char*);
void ComputeBoundingSphere();
// DATA
VERTEX* Vertices; // Array Of Vertices.
int NumberOfVertices; // Number Of Vertices.
unsigned short* // Array of Indices.
int NumberOfIndices; // Number Of Indices.
VECTOR Position; // Object’s Position.
SPHERE BoundingSphere; // Bounding Sphere.
};
OBJECT::OBJECT()
{
Vertices = NULL;
NumberOfVertices = 0;
Indices = NULL;
NumberOfIndices = 0;
}
OBJECT::~OBJECT()
{
if (Vertices != NULL)
{
delete
[] Vertices;Vertices = NULL;
}
if (Indices != NULL)
{
delete [] Indices;
Indices = NULL;
}
}
void
OBJECT::Load(const char* Filename){
// Выделяется память для загрузки файла
ComputeBoundingSphere(); // Вычисление сферы
}
void
OBJECT::ComputeBoundingSphere(){
for ( int VertexNo = 0;
VertexNo < NumberOfVertices;
VertexNo++)
{
VECTOR DistanceVector( Vertices[I_VertexNumber].x,
Vertices[I_VertexNumber].y,
Vertices[I_VertexNumber].z);
float Distance = DistanceVector.CalculateMagnetude();
if
(Distance > BoundingSphere.Radius){
BoundingSphere->Radius = Distance;
}
}
}
View Frustum
View Frustum - это видимая часть мирового пространства . По сути , это инициализация все того же клиппинга .
void
SetupViewFrustum(FRUSTUM* ViewFrustum){
ViewFrustum->LeftPlane.Distance = 0.0f;
ViewFrustum->LeftPlane.Normal = VECTOR( 0.7071067811865f,
0.0f,
0.7071067811865f);
ViewFrustum->RightPlane.Distance = 0.0f;
ViewFrustum->RightPlane.Normal = VECTOR( -0.7071067811865f,
0.0f,
0.7071067811865f);
ViewFrustum->TopPlane.Distance = 0.0f;
ViewFrustum->TopPlane.Normal = VECTOR( 0.0f,
-0.7071067811865f,
0.7071067811865f);
ViewFrustum->BottomPlane.Distance = 0.0f;
ViewFrustum->BottomPlane.Normal = VECTOR( 0.0f,
0.7071067811865f,
0.7071067811865f);
ViewFrustum->NearPlane.Distance = 0.1f;
ViewFrustum->NearPlane.Normal = VECTOR( 0.0f,
0.0f,
1.0f);
ViewFrustum->FarPlane.Distance = 500.0f;
ViewFrustum->FarPlane.Normal = VECTOR( 0.0f,
0.0f,
-1.0f);
}
Уравнение плоскости
Зададим функцию , которая определяет положение точки относительно плоскости . Функция важна для того , чтобы определить , находится ли сфера внутря view frustum .
Данная функция вертает 1 , если точка находится ПЕРЕД плоскостью (т.е. там , куда показывает нормаль к плоскости) , и 0 , если позади :
Расстояние до плоскости = ax + by + cz + d.
Если число > 0 , то точка ПЕРЕД плоскостью .
bool
IsPointInFrontOfPlane(const VECTOR& Point, const PLANE& Plane){
if (((Plane.Normal.X * Point.X) +
(Plane.Normal.Y * Point.Y) +
(Plane.Normal.Z * Point.Z) +
Plane.Distance) > 0)
{
return TRUE; // Point is in front of Plane.
}
else
{
return FALSE; // Point is behind Plane.
}
}
Frustum тест
Алгоритм определения попадания точки во внутрь View Frustum прост - надо по очереди проверить все 6 базовых плоскостей .
Следующая функция определяет переменный для определения полного или частичного попадания сферы в View Frustum :
enum
VISIBILITY_STATE{
OBJECT_INVISIBLE = 0x00,
// Object totally outside View Frustum.OBJECT_TOTALLY_VISIBLE = 0x01,
// Object totally inside View Frustum.OBJECT_PARTIALLY_VISIBLE = 0x02
// Object partially inside View Frustum.};
VISIBILITY_STATE CheckIfBoundingSphereIsVisible(
const SPHERE& Sphere,&nb sp;
const FRUSTUM& ViewFrustum){
float
DistanceFromPlane = 0.0f;int
NumberOfPlaneTestsPassed = 0;int
NumberOfPlanesIntersected = 0;
// Test the Sphere with the Near Plane.
DistanceFromPlane = ( (ViewFrustum.NearPlane.Normal.X * Sphere.Position.X) +
(ViewFrustum.NearPlane.Normal.Y * Sphere.Position.Y) +
(ViewFrustum.NearPlane.Normal.Z * Sphere.Position.Z) +
ViewFrustum.NearPlane.Distance);
if
(DistanceFromPlane > Sphere.Radius){
NumberOfPlaneTestsPassed++;
}
else if
(DistanceFromPlane > -Sphere.Radius){
NumberOfPlanesIntersected++;
}
// Test the Sphere with the Far Plane.
DistanceFromPlane = ( (ViewFrustum.FarPlane.Normal.X * Sphere.Position.X) +
(ViewFrustum.FarPlane.Normal.Y * Sphere.Position.Y) +
(ViewFrustum.FarPlane.Normal.Z * Sphere.Position.Z) +
ViewFrustum.FarPlane.Distance);
if
(DistanceFromPlane > Sphere.Radius){
NumberOfPlaneTestsPassed++;
}
else if
(DistanceFromPlane > -Sphere.Radius){
NumberOfPlanesIntersected++;
}
// Test the Sphere with the Left Plane.
DistanceFromPlane = (
(ViewFrustum.LeftPlane.Normal.X * Sphere.Position.X) +(ViewFrustum.LeftPlane.Normal.Y * Sphere.Position.Y) +
(ViewFrustum.LeftPlane.Normal.Z * Sphere.Position.Z) +
ViewFrustum.eftPlane.Distance);
if
(DistanceFromPlane > Sphere.Radius){
NumberOfPlaneTestsPassed++;
}
else if
(DistanceFromPlane > -Sphere.P_Radius){
NumberOfPlanesIntersected++;
}
// Test the Sphere with the Right Plane.
DistanceFromPlane = ( (ViewFrustum.RightPlane.Normal.X * Sphere.Position.X) +
(ViewFrustum.RightPlane.Normal.Y * Sphere.Position.Y) +
(ViewFrustum.RightPlane.Normal.Z * Sphere.Position.Z) +
ViewFrustum.RightPlane.Distance);
if
(DistanceFromPlane > Sphere.Radius){
NumberOfPlaneTestsPassed++;
}
else if
(DistanceFromPlane > -Sphere.Radius){
NumberOfPlanesIntersected++;
}
// Test the Sphere with the Top Plane.
DistanceFromPlane = ( (ViewFrustum.TopPlane.Normal.X * Sphere.Position.X) +
(ViewFrustum.TopPlane.Normal.Y * Sphere.Position.Y) +
(ViewFrustum.TopPlane.Normal.Z * Sphere.Position.Z) +
ViewFrustum.TopPlane.Distance);
if
(DistanceFromPlane > Sphere.Radius){
NumberOfPlaneTestsPassed++;
}
else if
(DistanceFromPlane > -Sphere.Radius){
NumberOfPlanesIntersected++;
}
// Test the Sphere with the Bottom Plane.
DistanceFromPlane = ( (ViewFrustum.BottomPlane.Normal.X * Sphere.Position.X) +
(ViewFrustum.BottomPlane.Normal.Y * Sphere.Position.Y) +
(ViewFrustum.BottomPlane.Normal.Z * Sphere.Position.Z) +
ViewFrustum.BottomPlane.Distance);
if
(DistanceFromPlane > Sphere.Radius){
NumberOfPlaneTestsPassed++;
}
else if
(DistanceFromPlane > -Sphere.Radius){
NumberOfPlanesIntersected++;
}
// Check how many tests passed and how many intersected.
if
(NumberOfPlaneTestsPassed == 6){ &n bsp;
// The Sphere is in front of all Planesreturn
OBJECT_TOTALLY_VISIBLE;}
else if
(NumberOfPlanesIntersected > 0){ &n bsp;
// The Sphere is not in front of allreturn
OBJECT_PARTIALLY_VISIBLE; // Planes, but some Planes intersected.}
else
{ &n bsp;
// The Sphere is not in front of allreturn OBJECT_INVISIBLE; // Planes, and not of the Planes
}
// intersected.}
Теперь у нас есть нужные функции . В дальнейшем нам нужно будет перевести локальные координаты сферы в пространственные . Следующая функция показывает , как выполняется Hiddden Object Removal
void
RenderObject( const OBJECT& Object,const MATRIX& ProjectionMatrix,
const MATRIX& ViewMatrix,
const FRUSTUM& ViewFrustum)
{
SPHERE TransformedBoundingSphere;
MATRIX TransformationMatrix
VISIBILITY_STATE VisiblityState;
TransformationMatrix.SetToIdentity();
TransformationMatrix.Translate( Object.Position.M_X,
Obj ect.Position.M_Y,
Obj ect.Position.M_Z);
TransformationMatrix = ( ProjectionMatrix *
ViewMatrix *
TransformationMatrix);
TransformedBoundingSphere.Radius = Object.BoundingSphere.Radius;
TransformedBoundingSphere.Position = VECTOR( TrasformationMatrix.Data[3][0],
&nb sp; TrasformationMatrix.Data[3][1],
&nb sp; TrasformationMatrix.Data[3][2]);
VisiblityState = CheckIfBoundingSphereIsVisible( TransformedBoundingSphere,
&nb sp;
ViewFrustum);
if
(VisiblitiyState == OBJECT_TOTALLY_VISIBLE){
// 1. Transform the Object.
// 2. Render the Transformed Object.
}
else if (VisibilityState == OBJECT_PARTIALLY_VISIBLE)
{
// 1. Transform the Object.
// 2. Clip all Polygons of the Transformed Object with the View Frustum.
// 3. Render the Clipped Object.
}
}
