tiberium/CnC_Renegade
Archived
2
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
This repository has been archived on 2025-02-27. You can view files and clone it, but cannot push or open issues or pull requests.
CnC_Renegade/Code/wwphys/bpt.cpp

2439 lines
69 KiB
C++
Raw Permalink Blame History

/*
** Command & Conquer Renegade(tm)
** Copyright 2025 Electronic Arts Inc.
**
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation, either version 3 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
/***********************************************************************************************
*** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S ***
***********************************************************************************************
* *
* Project Name : WWPhys *
* *
* $Archive:: /Commando/Code/wwphys/bpt.cpp $*
* *
* Author:: Greg_h *
* *
* $Modtime:: 9/09/99 11:29a $*
* *
* $Revision:: 15 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* BptClass::BptClass -- constructor *
* BptClass::~BptClass -- destructor *
* BptClass::Free -- releases all assets in use *
* BptClass::Build -- build a bpt from the given mesh (generates a new mesh) *
* BptClass::Load -- Initialize this Bpt object from contents of a W3D file *
* BptClass::Save -- Save this Bpt object into a W3D file *
* BptClass::Render -- submit this object for rendering *
* BptClass::Cast_Ray -- Intersect a ray with this Bpt Object *
* BptClass::Cast_AABox -- Intersect a swept axis-aligned box. *
* BptClass::Cast_OBBox -- Intersect a swept oriented box with this bpt object *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#if 0 // OBSOLETE!!!
#ifdef PORT140
#include "bpt.h"
#include "vector.h"
#include "uarray.h"
#include "mesh.h"
#include "material.h"
#include "chunkio.h"
#include "vector3.h"
#include "tri.h"
#include "wwdebug.h"
#include "meshbuild.h"
#include "camera.h"
#include "sr.hpp"
#define BPT_FRONT 0x01
#define BPT_BACK 0x02
#define BPT_ON 0x04
#define BPT_BOTH 0x08
#define BPT_EPSILON 0.0001f
#define BPT_COINCIDENCE_EPSILON 0.000001f
class BptVertexClass;
class BptPolyClass;
class BptNodeClass;
class BptBuilderClass;
class BptImpNodeClass;
class BptImpClass;
class BptImpBuilderClass;
/*
** NormalHasherClass, used by the code which builds the
** table of unique Normal vectors.
*/
class NormalHasherClass : public HashCalculatorClass<Vector3>
{
public:
virtual bool Items_Match(const Vector3 & a, const Vector3 & b)
{
// looking for an exact match for normals...
return ((a.X == b.X) && (a.Y == b.Y) && (a.Z == b.Z));
}
virtual void Compute_Hash(const Vector3 & item)
{
HashVal = (int)(item.X*12345.6f + item.Y*1714.38484f + item.Z*27561.3f)&1023;
}
virtual int Num_Hash_Bits(void)
{
return 10; // 10bit hash value.
}
virtual int Num_Hash_Values(void)
{
return 1; // only one hash value for normals, require *exact* match
}
virtual int Get_Hash_Value(int index)
{
return HashVal;
}
private:
int HashVal;
};
/*
** DistanceHasherClass, used by the code which builds the
** table of unique distance values.
*/
class DistanceHasherClass : public HashCalculatorClass<float>
{
virtual bool Items_Match(const float & a, const float & b)
{
// looking for an exact match for distances
return (a == b);
}
virtual void Compute_Hash(const float & item)
{
HashVal = (int)(item)&1023;
}
virtual int Num_Hash_Bits(void)
{
return 12; // 12bit hash value.
}
virtual int Num_Hash_Values(void)
{
return 1; // only one hash value for normals, require *exact* match
}
virtual int Get_Hash_Value(int index)
{
return HashVal;
}
private:
int HashVal;
};
/*
** BPT Notes
**
** - Probably need to build the initial tree in a big straightforward recursive datastructure
** with no indirection or anything. Then, when the whole thing is being built correctly,
** process the tree down so that everything that can be shared (e.g. plane equations) are
** shared.
**
** - Hide most of the implementation details even from the bpt header file by using a
** BptImpClass. This class will contain the final "optimized" bpt information.
**
** - Maybe need a BptBuilder class that builds the initial "straightforward" tree structure
** and then compresses it into a BptImp.
**
** - Extend PlaneClass to know about special case planes such as x-y, y-z, x-z. Optimize
** the culling and clipping functions to take advantage of them.
**
** - Separate the normal from the distance in the plane equation? Many many planes will
** probably share the same normal but different distances. This probably should be a
** very late optimization.
*/
/*
** BptVertexClass
** This is the vertex representation used in building the BPT
*/
class BptVertexClass
{
public:
BptVertexClass(void);
BptVertexClass(const BptVertexClass & that);
BptVertexClass & operator = (const BptVertexClass & that);
int Which_Side(const PlaneClass & plane) const;
Vector3 Position;
Vector3 Normal;
Vector3 Color;
Vector3 TexCoord;
static BptVertexClass Lerp(const BptVertexClass & v0,const BptVertexClass & v1,double lerp);
static BptVertexClass Intersect_Plane(const BptVertexClass & v0,const BptVertexClass & v1,const PlaneClass & plane);
};
/*
** BptPolyClass
** This is the polygon representation used in building the BPT
*/
class BptPolyClass
{
public:
enum { BPT_POLY_MAX_VERTS = 16 };
BptPolyClass(void);
BptPolyClass(const BptPolyClass & that);
BptPolyClass(const BptVertexClass * points, int num);
BptPolyClass & operator = (const BptPolyClass & that);
const BptVertexClass & operator[] (int i) const { return Verts[i]; }
BptVertexClass & operator[] (int i) { return Verts[i]; }
void Compute_Plane(void);
int Which_Side(const PlaneClass & plane) const;
void Split(const PlaneClass & plane,BptPolyClass & front,BptPolyClass & back) const;
bool Is_Degenerate(void);
bool Salvage_Degenerate(void);
int MaterialId;
int NumVerts;
BptVertexClass Verts[BPT_POLY_MAX_VERTS];
PlaneClass Plane;
};
/*
** BptNodeClass
** This is the node representation used in building the BPT
*/
class BptNodeClass
{
public:
BptNodeClass(void) : NumPolys(0),Polys(NULL),Front(NULL),Back(NULL),ArrayIndex(-1) { }
~BptNodeClass(void) { if (Front) delete Front; if (Back) delete Back; if (Polys) delete[] Polys; }
void Build(int numpolys,BptPolyClass * polys);
int Num_Polys(void) const;
int Num_Tris(void) const;
int Num_Nodes(void) const;
int Max_Depth(void) const;
void Submit_Polys(MeshBuilderClass & builder) const;
void Compute_Bounding_Box(void);
int Assign_Array_Indices(int index);
void Submit_Nodes(BptImpBuilderClass & impbuilder) const;
private:
PlaneClass Plane; // splitting plane
uint32 NumPolys; // num polys on plane
BptPolyClass * Polys; // array of polys
BptNodeClass * Front; // pointer to front tree
BptNodeClass * Back; // pointer to back tree
int ArrayIndex; // used in building the tree into array form.
Vector3 Min; // bounding box for this tree.
Vector3 Max;
/*
** SplitChoiceStruct. Whenever a plane is tested to see if it is a suitable splitting
** plane, we'll cache all of the values it computes so we do not duplicate the effort elsewhere.
*/
struct SplitChoiceStruct
{
SplitChoiceStruct(void) : Score(0.0f),FrontCount(0),BackCount(0),OnCount(0),SplitCount(0),Plane(0,0,0,0) {}
float Score; // 0.0 is worst, 1.0 is "perfect"
int FrontCount; // number of polys in front of the plane
int BackCount; // number of polys behind the plane
int OnCount; // number of polys on the plane
int SplitCount; // number of polys split by the plane
PlaneClass Plane; // plane equation
};
/*
** SplitArrayStruct. This struct simply stores the result of a split operation. The
** arrays for the front, back and "on" polygons will be allocated and filled in.
*/
struct SplitArraysStruct
{
SplitArraysStruct(void) : FrontCount(0),BackCount(0),OnCount(0),FrontPolys(NULL),BackPolys(NULL),OnPolys(NULL) {}
int FrontCount;
int BackCount;
int OnCount;
BptPolyClass * FrontPolys;
BptPolyClass * BackPolys;
BptPolyClass * OnPolys;
};
SplitChoiceStruct Compute_Plane_Score(int numpolys,BptPolyClass * polys,const PlaneClass & plane);
SplitChoiceStruct Select_Splitting_Plane(int numpolys,BptPolyClass * polys);
void Split_Polys(const int num_polys,
const BptPolyClass * polys,
const SplitChoiceStruct & sc,
SplitArraysStruct * arrays);
void Max_Depth_Internal(int cur_depth, int & max_depth) const;
friend class BptImpBuilderClass;
};
/*
** BptBuilderClass
** This class builds the initial straightforward binary tree representation of
** the mesh given to it. It then "optimizes" the tree into a BptImpClass to
** save ram.
*/
class BptBuilderClass
{
public:
BptBuilderClass(void);
~BptBuilderClass(void);
BptImpClass * Build(MeshClass * mesh);
BptImpClass * Build(int numpolys,BptPolyClass * polyarray,MaterialInfoClass * matinfo);
private:
void unwind_mesh(MeshClass * mesh,int & set_numpolys,BptPolyClass * & set_polyarray);
BptImpClass * build_imp(void);
BptNodeClass * Root;
MaterialInfoClass * MatInfo;
int InputPolyCount;
int OutputPolyCount;
int InputTriCount;
int OutputTriCount;
int NodeCount;
int MaxDepth;
};
/*
** BptImpNodeClass
** This is the node representation in the final BPT implementation.
** It allows for sharing of plane equations, indirection to the polygons, etc
*/
class BptImpNodeClass
{
public:
float MinX,MinY,MinZ;
float MaxX,MaxY,MaxZ;
BptImpNodeClass * Front;
BptImpNodeClass * Back;
uint16 FirstPoly;
uint16 PolyCount;
uint16 NormalIndex;
uint16 DistanceIndex;
bool Is_Visible(const CameraClass & camera);
bool Cast_AABox_To_Polys(PhysAABoxCollisionTestClass & coltest);
};
/*
** BptImpClass
** This class contains the actual run-time binary partition tree information
** and the code for building a bpt out of an arbitrary list of polygons.
*/
class BptImpClass
{
public:
~BptImpClass(void);
void Free(void);
void Build_Apt(const CameraClass & camera);
bool Cast_Ray(PhysRayCollisionTestClass & raytest) const;
bool Cast_AABox(PhysAABoxCollisionTestClass & boxtest) const;
bool Cast_OBBox(PhysOBBoxCollisionTestClass & boxtest) const;
private:
// These functions are used by the BptImpBuilder to construct
// the BptImp...
BptImpClass(void);
void Set_Mesh(MeshClass * mesh);
void Set_Node_Array(int numnodes, BptImpNodeClass * nodes);
void Set_Normal_Array(const UniqueArrayClass<Vector3> & normals);
void Set_Distance_Array(const UniqueArrayClass<float> & distances);
void Set_Poly_Index_Array(int numremaps,int * polyremaps);
void Begin_Apt(void);
void Add_Polys_To_Apt(BptImpNodeClass * node);
void End_Apt(void);
void Build_Apt_Recursive(BptImpNodeClass * node,const CameraClass & cam);
bool Cast_Ray_Recursive(BptImpNodeClass * node,PhysRayCollisionTestClass & boxtest) const;
bool Cast_AABox_Recursive(BptImpNodeClass * node,PhysAABoxCollisionTestClass & boxtest) const;
bool Cast_OBBox_Recursive(BptImpNodeClass * node,PhysOBBoxCollisionTestClass & boxtest) const;
bool Cast_Ray_To_Polys(BptImpNodeClass * node,PhysAABoxCollisionTestClass & boxtest) const { assert(0); return false; }
bool Cast_AABox_To_Polys(BptImpNodeClass * node,PhysAABoxCollisionTestClass & boxtest) const;
bool Cast_OBBox_To_Polys(BptImpNodeClass * node,PhysAABoxCollisionTestClass & boxtest) const { assert(0); return false; }
void Verify_Node_Bounding_Volume(BptImpNodeClass * node,const Vector3 & min,const Vector3 & max) const;
// Polygon Mesh in w3d-friendly form
MeshClass * Mesh;
// Binary partition nodes
int NodeCount;
BptImpNodeClass * Nodes;
// Node Polygon remap arrays
int PolyIndexCount;
int * PolyIndices;
// Plane equation normals, these are stored separate from the distances
// because many many of the planes will share the same normal but not dist.
int NormalCount;
Vector3 * Normals;
// Plane equation distances, again, stored separately from the normals
int DistanceCount;
float * Distances;
// Active Poly Table support. These variables are used internally by
// the culling code. The ActivePolyTable pointer is set to point into
// the surrender mesh's apt.
int ActivePolyCount;
SRDWORD * ActivePolyTable;
friend class BptClass;
friend class BptImpBuilderClass;
};
/*
** BptImpBuilderClass
** This guy takes a completed bpt tree (given as a pointer to the root node)
** and churns through the thing, generating a BptImpClass.
*/
class BptImpBuilderClass
{
public:
BptImpBuilderClass(void);
~BptImpBuilderClass(void);
void Free(void);
BptImpClass * Build_Bpt_Imp(BptNodeClass * root,MaterialInfoClass * matinfo);
void Add_Bpt_Node(const BptNodeClass * node);
private:
void Remap_Triangle_Indices(void);
MeshBuilderClass MeshBuilder; // accumulate the polygons
NormalHasherClass NormalHasher; // computes hash values for the normals
DistanceHasherClass DistanceHasher; // computes hash values for the distances
UniqueArrayClass<Vector3> * UniqueNormals; // accumulates the unique normals
UniqueArrayClass<float> * UniqueDistances; // accumulates the unique distances
int NodeCount; // number of nodes in the tree
BptImpNodeClass * Nodes; // array of all of the nodes
int TriCount; // number of triangles in the tree
int CurTriIndex; // current remap index
int * TriIndexArray; // array of triangle remap indices
};
/***********************************************************************************************
* BptClass::BptClass -- constructor *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
BptClass::BptClass(void) :
BptImp(NULL)
{
}
/***********************************************************************************************
* BptClass::~BptClass -- destructor *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
BptClass::~BptClass(void)
{
Free();
}
/***********************************************************************************************
* BptClass::Free -- releases all assets in use *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
void BptClass::Free(void)
{
if (BptImp) {
delete BptImp;
BptImp = NULL;
}
}
/***********************************************************************************************
* BptClass::Build -- build a bpt from the given mesh (generates a new mesh) *
* *
* This function will process the given mesh into a binary partition tree. It has to generate *
* a new mesh due to the fact that some polygons may be split in the partioning process. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
void BptClass::Build(MeshClass * mesh)
{
assert(mesh);
/*
** First, release everything that we have!
*/
Free();
/*
** Create a new BptImp object using the given mesh
*/
BptBuilderClass builder;
BptImp = builder.Build(mesh);
}
/***********************************************************************************************
* BptClass::Load -- Initialize this Bpt object from contents of a W3D file *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
int BptClass::Load(ChunkLoadClass & cload)
{
assert(0);
return 0;
}
/***********************************************************************************************
* BptClass::Save -- Save this Bpt object into a W3D file *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
int BptClass::Save(ChunkSaveClass & csave)
{
assert(0);
return 0;
}
/***********************************************************************************************
* BptClass::Render -- submit this object for rendering *
* *
* This function sets the active polygon table for the mesh based on the camera frustum. The *
* bpt is used to cull out portions of the level which are not inside the frustum. Then the *
* mesh is added to the given surrender scene. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
* 5/29/98 GTH : Created. *
*=============================================================================================*/
void BptClass::Render( srScene * scene, const CameraClass &camera )
{
/*
** Do our APT stuff
*/
BptImp->Build_Apt(camera);
/*
** Then let Mesh render itself
*/
BptImp->Mesh->Render(scene,camera);
}
void BptClass::Update_Cached_Bounding_Volumes(void) const
{
CachedBoundingSphere = BptImp->Mesh->Get_Bounding_Sphere();
CachedBoundingBox = BptImp->Mesh->Get_Bounding_Box();
Validate_Cached_Bounding_Volumes();
}
#if 0
MeshClass * BptClass::Get_Mesh(void)
{
if (BptImp) {
if (BptImp->Mesh) BptImp->Mesh->Add_Ref();
return BptImp->Mesh;
} else {
return NULL;
}
}
#endif
/***********************************************************************************************
* BptClass::Cast_Ray -- Intersect a ray with this Bpt Object *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
bool BptClass::Cast_Ray(PhysRayCollisionTestClass & raytest) const
{
assert(BptImp);
return BptImp->Cast_Ray(raytest);
}
/***********************************************************************************************
* BptClass::Cast_AABox -- Intersect a swept axis-aligned box. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
bool BptClass::Cast_AABox(PhysAABoxCollisionTestClass & aaboxtest) const
{
assert(BptImp);
return BptImp->Cast_AABox(aaboxtest);
}
/***********************************************************************************************
* BptClass::Cast_OBBox -- Intersect a swept oriented box with this bpt object *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/6/98 GTH : Created. *
*=============================================================================================*/
bool BptClass::Cast_OBBox(PhysOBBoxCollisionTestClass & obboxtest) const
{
assert(BptImp);
return BptImp->Cast_OBBox(obboxtest);
}
/**************************************************************
BptVertexClass Implementation
**************************************************************/
BptVertexClass::BptVertexClass(void) :
Position(0,0,0),
Normal(0,0,0),
Color(0,0,0),
TexCoord(0,0,0)
{
}
BptVertexClass::BptVertexClass(const BptVertexClass & that)
{
Position = that.Position;
Normal = that.Normal;
Color = that.Color;
TexCoord = that.TexCoord;
}
BptVertexClass & BptVertexClass::operator = (const BptVertexClass & that)
{
if (this != &that) {
Position = that.Position;
Normal = that.Normal;
Color = that.Color;
TexCoord = that.TexCoord;
}
return *this;
}
BptVertexClass BptVertexClass::Lerp(const BptVertexClass & v0,const BptVertexClass & v1,double lerp)
{
assert(lerp >= -BPT_EPSILON);
assert(lerp <= 1.0 + BPT_EPSILON);
// interpolate position
BptVertexClass res;
res.Position = ::Lerp(v0.Position,v1.Position,lerp);
// interpolate normal, renormalize
res.Normal = ::Lerp(v0.Normal,v1.Normal,lerp);
res.Normal.Normalize();
// interpolate color
res.Color = ::Lerp(v0.Color,v1.Color,lerp);
// interpolate texture coordinates
res.TexCoord = ::Lerp(v0.TexCoord,v1.TexCoord,lerp);
return res;
}
int BptVertexClass::Which_Side(const PlaneClass & plane) const
{
float d = Vector3::Dot_Product(plane.N,Position);
d -= plane.D;
if (d > BPT_EPSILON) {
return BPT_FRONT;
}
if (d < -BPT_EPSILON) {
return BPT_BACK;
}
return BPT_ON;
}
BptVertexClass BptVertexClass::Intersect_Plane
(
const BptVertexClass & p0,
const BptVertexClass & p1,
const PlaneClass & plane
)
{
double alpha = 0.0f;
plane.Compute_Intersection(p0.Position,p1.Position,&alpha);
return BptVertexClass::Lerp(p0,p1,alpha);
}
/**************************************************************
BptPolyClass Implementation
**************************************************************/
BptPolyClass::BptPolyClass(void) :
NumVerts(0)
{
}
BptPolyClass::BptPolyClass(const BptPolyClass & that)
{
NumVerts = that.NumVerts;
for (int i=0;i<NumVerts;i++) {
Verts[i] = that.Verts[i];
}
}
BptPolyClass::BptPolyClass(const BptVertexClass * points, int num)
{
NumVerts = num;
for (int i=0; i<NumVerts; i++) {
Verts[i] = points[i];
}
}
BptPolyClass & BptPolyClass::operator = (const BptPolyClass & that)
{
if (this != &that) {
MaterialId = that.MaterialId;
NumVerts = that.NumVerts;
Plane = that.Plane;
for (int i=0;i<NumVerts;i++) {
Verts[i] = that.Verts[i];
}
}
return * this;
}
void BptPolyClass::Compute_Plane(void)
{
double nx = 0;
double ny = 0;
double nz = 0;
double ax = 0;
double ay = 0;
double az = 0;
int i,j;
for (i=0; i<NumVerts; i++) {
j = (i+1) % NumVerts;
nx += (double)(Verts[i].Position.Y - Verts[j].Position.Y) * (double)(Verts[i].Position.Z + Verts[j].Position.Z);
ny += (double)(Verts[i].Position.Z - Verts[j].Position.Z) * (double)(Verts[i].Position.X + Verts[j].Position.X);
nz += (double)(Verts[i].Position.X - Verts[j].Position.X) * (double)(Verts[i].Position.Y + Verts[j].Position.Y);
ax += (double)Verts[i].Position.X;
ay += (double)Verts[i].Position.Y;
az += (double)Verts[i].Position.Z;
}
ax /= (double)NumVerts;
ay /= (double)NumVerts;
az /= (double)NumVerts;
double len = sqrt(nx*nx + ny*ny + nz*nz);
nx /= len;
ny /= len;
nz /= len;
Plane.Set(Vector3(nx,ny,nz),Vector3(ax,ay,az));
}
int BptPolyClass::Which_Side(const PlaneClass & plane) const
{
int side_mask = 0;
for (int i=0; i<NumVerts;i++) {
side_mask |= Verts[i].Which_Side(plane);
}
// check if all verts are "ON"
if (side_mask == BPT_ON) {
return BPT_ON;
}
// check if all verts are either "ON" or "FRONT"
if ((side_mask & ~(BPT_FRONT | BPT_ON)) == 0) {
return BPT_FRONT;
}
// check if all verts are either "ON" or "BACK"
if ((side_mask & ~(BPT_BACK | BPT_ON)) == 0) {
return BPT_BACK;
}
// otherwise, poly spans the plane.
return BPT_BOTH;
}
void BptPolyClass::Split(const PlaneClass & plane,BptPolyClass & front,BptPolyClass & back) const
{
front = *this;
back = *this;
front.NumVerts = back.NumVerts = 0;
assert(Which_Side(plane) == BPT_BOTH);
BptVertexClass point;
front.NumVerts = 0;
back.NumVerts = 0;
// find a vertex on one side or the other
int side = BPT_ON;
int i;
for (i = 0; (i < NumVerts) && ((side = Verts[i].Which_Side(plane)) == BPT_ON); i++);
// perform clipping
int iprev = i;
int sideprev = side;
int sidelastdefinite = 0;
i = (i+1) % NumVerts;
for (int j=0; j<NumVerts; j++) {
side = Verts[i].Which_Side(plane);
if (sideprev == BPT_FRONT) {
if (side == BPT_FRONT) {
// Previous vertex was in front of plane and this vertex is in
// front of the plane so we emit this vertex in the front poly
front.Verts[(front.NumVerts)++] = Verts[i];
} else if (side == BPT_ON) {
// Previous vert was in front, this vert is "on" so emit
// the vertex into the front poly.
sidelastdefinite = BPT_FRONT;
front.Verts[(front.NumVerts)++] = Verts[i];
} else { // side == BPT_BACK
// Previous vert was in front, this vert is behind, compute
// the intersection and emit the point in both the front
// and back polys. Then continue the edge into the back halfspace
point = BptVertexClass::Intersect_Plane(Verts[iprev],Verts[i],plane);
front.Verts[(front.NumVerts)++] = point;
back.Verts[(back.NumVerts)++] = point;
back.Verts[(back.NumVerts)++] = Verts[i];
}
} else if (sideprev == BPT_BACK) {
if (side == BPT_FRONT) {
// segment is going from the back halfspace to the front halfspace
// compute the intersection and emit it in both polys, then continue
// the edge into the front halfspace.
point = BptVertexClass::Intersect_Plane(Verts[iprev],Verts[i],plane);
back.Verts[(back.NumVerts)++] = point;
front.Verts[(front.NumVerts)++] = point;
front.Verts[(front.NumVerts)++] = Verts[i];
} else if (side == BPT_ON) {
// segment went from back halfspace to "on" the plane. Emit
// the vertex into the back poly and remember that we came
// from the back halfspace.
sidelastdefinite = BPT_BACK;
back.Verts[(back.NumVerts)++] = Verts[i];
} else { // side == BPT_BACK
// segment is completely in the back halfspace, just emit the
// vertex into the back poly
back.Verts[(back.NumVerts)++] = Verts[i];
}
} else if (sideprev == BPT_ON) {
if (side == BPT_FRONT) {
// segment is on the plane
if (sidelastdefinite == BPT_BACK) {
front.Verts[(front.NumVerts)++] = Verts[iprev];
}
front.Verts[(front.NumVerts)++] = Verts[i];
} else if (side == BPT_ON) {
if (sidelastdefinite == BPT_FRONT) {
front.Verts[(front.NumVerts)++] = Verts[i];
} else {
back.Verts[(back.NumVerts)++] = Verts[i];
}
} else { // side == BPT_BACK
if (sidelastdefinite == BPT_FRONT) {
back.Verts[(back.NumVerts)++] = Verts[iprev];
}
back.Verts[(back.NumVerts)++] = Verts[i];
}
} else {
WWASSERT_PRINT(0,"BptPolyClass::Split : invalid side\n");
}
sideprev = side;
iprev = i;
i = (i+1)%NumVerts;
}
front.Compute_Plane();
back.Compute_Plane();
// check the two polygons
if (front.Is_Degenerate()) {
front.Salvage_Degenerate();
}
if (back.Is_Degenerate()) {
back.Salvage_Degenerate();
}
}
bool BptPolyClass::Is_Degenerate(void)
{
int i,j;
if (NumVerts == 2) {
WWDEBUG_SAY(("Degenerate Poly - fewer than 3 vertices\r\n"));
return true;
}
for (i=0; i<NumVerts; i++) {
for (j = i+1; j < NumVerts; j++) {
float delta = (Verts[i].Position - Verts[j].Position).Length();
if (delta < BPT_COINCIDENCE_EPSILON) {
WWDEBUG_SAY(("Degenerate Poly - coincident vertices!\r\n"));
return true;
}
}
}
for (i=0; i<NumVerts; i++) {
int side = Verts[i].Which_Side(Plane);
if (side != BPT_ON) {
// hmmm, try to recalculate the plane, if it is still bad, then give up
Compute_Plane();
if (Verts[i].Which_Side(Plane) != BPT_ON) {
WWDEBUG_SAY(("Degenerate Poly - invalid plane!\r\n"));
return true;
}
}
}
return false;
}
bool BptPolyClass::Salvage_Degenerate(void)
{
/*
** About all we can do is combine sequential vertices which are co-incident
*/
int i = 0;
while (i < NumVerts) {
float delta = (Verts[i].Position - Verts[i+1].Position).Length();
if (delta < BPT_COINCIDENCE_EPSILON) {
for (int j=i+1; j<NumVerts-1; j++) {
Verts[j] = Verts[j+1];
}
NumVerts--;
} else {
i++;
}
}
return !Is_Degenerate();
}
/**************************************************************
BptBuilderClass Implementation
**************************************************************/
BptBuilderClass::BptBuilderClass(void) :
Root(NULL),
MatInfo(NULL),
InputPolyCount(0),
OutputPolyCount(0),
NodeCount(0),
MaxDepth(0)
{
}
BptBuilderClass::~BptBuilderClass(void)
{
if (Root) delete Root;
if (MatInfo) MatInfo->Release_Ref();
}
BptImpClass * BptBuilderClass::Build(MeshClass * mesh)
{
/*
** Here we go, unwind the mesh into BptVerts and BptPolys
*/
int numpolys;
BptPolyClass * polys;
unwind_mesh(mesh,numpolys,polys);
assert(numpolys > 0);
/*
** Jump into the generalized build method
*/
MaterialInfoClass * matinfo = mesh->Get_Material_Info();
BptImpClass * result = Build(numpolys,polys,matinfo);
matinfo->Release_Ref();
/*
** Build function deletes the poly array...
*/
polys = NULL;
return result;
}
BptImpClass * BptBuilderClass::Build(int numpolys,BptPolyClass * polys,MaterialInfoClass * matinfo)
{
/*
** Create a copy of all of the materials
*/
MatInfo = (MaterialInfoClass *)matinfo->Clone();
/*
** Store the input counts
*/
InputPolyCount = numpolys;
InputTriCount = 0;
for (int i=0; i<numpolys; i++) {
InputTriCount += polys[i].NumVerts-2;
}
WWDEBUG_SAY(("Building Binary Tree\r\n"));
/*
** Build the fat tree
*/
assert(Root == NULL);
Root = new BptNodeClass;
Root->Build(numpolys,polys);
/*
** Compile some statistics about the tree
*/
OutputPolyCount = Root->Num_Polys();
OutputTriCount = Root->Num_Tris();
NodeCount = Root->Num_Nodes();
MaxDepth = Root->Max_Depth();
WWDEBUG_SAY(("Binary Tree Generated!\r\n"));
WWDEBUG_SAY(("Node Count: %d\r\n",NodeCount));
WWDEBUG_SAY(("Max Depth: %d\r\n",MaxDepth));
WWDEBUG_SAY(("Input Poly Count: %d\r\n",InputPolyCount));
WWDEBUG_SAY(("Output Poly Count: %d\r\n",OutputPolyCount));
WWDEBUG_SAY(("Input Tri Count: %d\r\n",InputTriCount));
WWDEBUG_SAY(("Output Tri Count: %d\r\n",OutputTriCount));
WWDEBUG_SAY(("Out/In Poly Ratio: %f\r\n",(float)OutputPolyCount / (float)InputPolyCount));
WWDEBUG_SAY(("Out/In Tri Ratio: %f\r\n",(float)OutputTriCount / (float)InputTriCount));
WWDEBUG_SAY(("\r\n"));
/*
** Build the optimized BptImp and return it.
*/
return build_imp();
}
void BptBuilderClass::unwind_mesh(MeshClass * mesh,int & set_numpolys,BptPolyClass * & set_polyarray)
{
srMeshModel * srmesh = mesh->Get_Surrender_Mesh();
// get pointers to the interesting stuff in the mesh
srVector3 * loc = srmesh->getVertexLoc();
srVector3 * norm = srmesh->getVertexNormal();
srVector3 * uv = srmesh->getVertexUVW(srMaterial::DIFFUSE_COLOR,false);
srVector3 * dcg = srmesh->getVertexDCG(false);
srVector3i * polyvert = srmesh->getPolyVertex();
srMaterial ** polymtl = srmesh->getPolyMaterial(false);
// allocate a bunch of BptPolygons
set_numpolys = srmesh->getPolygonCount();
set_polyarray = new BptPolyClass[set_numpolys];
int src_idx = 0;
int dst_idx = 0;
for (src_idx = 0; src_idx<set_numpolys; src_idx++) {
set_polyarray[dst_idx].NumVerts = 3;
for (int vrt_idx=0; vrt_idx<3; vrt_idx++) {
// copy the three positions
set_polyarray[dst_idx][vrt_idx].Position.X = loc[polyvert[src_idx][vrt_idx]].x;
set_polyarray[dst_idx][vrt_idx].Position.Y = loc[polyvert[src_idx][vrt_idx]].y;
set_polyarray[dst_idx][vrt_idx].Position.Z = loc[polyvert[src_idx][vrt_idx]].z;
// copy the three normals
if (norm) {
set_polyarray[dst_idx][vrt_idx].Normal.X = norm[polyvert[src_idx][vrt_idx]].x;
set_polyarray[dst_idx][vrt_idx].Normal.Y = norm[polyvert[src_idx][vrt_idx]].y;
set_polyarray[dst_idx][vrt_idx].Normal.Z = norm[polyvert[src_idx][vrt_idx]].z;
}
// copy the three u-v's
if (uv) {
set_polyarray[dst_idx][vrt_idx].TexCoord.X = uv[polyvert[src_idx][vrt_idx]].x;
set_polyarray[dst_idx][vrt_idx].TexCoord.Y = uv[polyvert[src_idx][vrt_idx]].y;
set_polyarray[dst_idx][vrt_idx].TexCoord.Z = uv[polyvert[src_idx][vrt_idx]].z;
}
// copy the three colors
if (dcg) {
set_polyarray[dst_idx][vrt_idx].Color.X = dcg[polyvert[src_idx][vrt_idx]].x;
set_polyarray[dst_idx][vrt_idx].Color.Y = dcg[polyvert[src_idx][vrt_idx]].y;
set_polyarray[dst_idx][vrt_idx].Color.Z = dcg[polyvert[src_idx][vrt_idx]].z;
}
// store the material ID
if (polymtl) {
set_polyarray[dst_idx].MaterialId = ((MaterialClass *)(polymtl[src_idx]))->Get_Mat_Info_Index();
} else {
set_polyarray[dst_idx].MaterialId = 0;
}
}
set_polyarray[dst_idx].Compute_Plane();
// if the triangle is not degenerate, accept it; increment the counter
if (!set_polyarray[dst_idx].Is_Degenerate()) {
dst_idx++;
}
}
// set the number of polys to the actual number kept
set_numpolys = dst_idx;
assert(set_numpolys <= srmesh->getPolygonCount());
WWDEBUG_SAY(("Unwinding Input Mesh\r\n"));
WWDEBUG_SAY(("Input poly count: %d\r\n",srmesh->getPolygonCount()));
WWDEBUG_SAY(("Count after removing degenerates: %d\r\n",set_numpolys));
WWDEBUG_SAY(("\r\n"));
}
BptImpClass * BptBuilderClass::build_imp(void)
{
BptImpBuilderClass impbuilder;
BptImpClass * imp = impbuilder.Build_Bpt_Imp(Root,MatInfo);
return imp;
}
/**************************************************************
BptNodeClass Implementation
**************************************************************/
int BptNodeClass::Num_Polys(void) const
{
int count = NumPolys;
if (Front) count += Front->Num_Polys();
if (Back) count += Back->Num_Polys();
return count;
}
int BptNodeClass::Num_Tris(void) const
{
int count = 0;
for (unsigned int i=0; i<NumPolys; i++) {
count += Polys[i].NumVerts - 2;
}
if (Front) count += Front->Num_Tris();
if (Back) count += Back->Num_Tris();
return count;
}
int BptNodeClass::Num_Nodes(void) const
{
int count = 1;
if (Front) count += Front->Num_Nodes();
if (Back) count += Back->Num_Nodes();
return count;
}
int BptNodeClass::Max_Depth(void) const
{
int max_depth = 0;
Max_Depth_Internal(0,max_depth);
return max_depth;
}
void BptNodeClass::Max_Depth_Internal(int cur_depth,int & max_depth) const
{
cur_depth++;
if (cur_depth > max_depth) {
max_depth = cur_depth;
}
if (Front) {
Front->Max_Depth_Internal(cur_depth,max_depth);
}
if (Back) {
Back->Max_Depth_Internal(cur_depth,max_depth);
}
}
void BptNodeClass::Build(int numpolys,BptPolyClass * polys)
{
/*
** Select and assign the splitting plane
*/
SplitChoiceStruct sc = Select_Splitting_Plane(numpolys,polys);
Plane = sc.Plane;
/*
** Split the polygons
*/
SplitArraysStruct arrays;
Split_Polys(numpolys,polys,sc,&arrays);
/*
** Free the memory in use by polys!
*/
delete[] polys;
/*
** Store the "on" polys in this node
*/
NumPolys = arrays.OnCount;
Polys = arrays.OnPolys;
arrays.OnPolys = NULL;
/*
** Build a front tree if necessary. Remember that the Build function
** deletes the poly array.
*/
if (arrays.FrontCount) {
assert(arrays.FrontPolys != NULL);
Front = new BptNodeClass;
Front->Build(arrays.FrontCount,arrays.FrontPolys);
arrays.FrontPolys = NULL;
}
/*
** Build a back tree if necessary. Remember that the build function
** deletes the poly array.
*/
if (arrays.BackCount) {
assert(arrays.BackPolys != NULL);
Back = new BptNodeClass;
Back->Build(arrays.BackCount,arrays.BackPolys);
arrays.BackPolys = NULL;
}
}
BptNodeClass::SplitChoiceStruct
BptNodeClass::Compute_Plane_Score(int numpolys,BptPolyClass * polys,const PlaneClass & plane)
{
/*
** Suitability of a plane as a partition plane is based on the following factors:
** - How many polygons will be split
** - How many polygons end up on each side of the tree
** - How many polygons end up on the plane (do NOT want many on the plane)
** - How evenly the volume of space is divided.
** The following weights will determine how much influence each factor
** has on the final score.
*/
const float POLY_SPLIT_WEIGHT = 5.0f;
const float POLY_COUNT_BALANCE_WEIGHT = 1.0f;
const float POLYS_ON_PLANE_WEIGHT = 1.0f;
const float TOTAL_WEIGHT = POLY_SPLIT_WEIGHT + POLY_COUNT_BALANCE_WEIGHT + POLYS_ON_PLANE_WEIGHT;
const int MAX_POLYS_ON_PLANE = 10;
const int MAX_SPLITS = 10;
/*
** Count up the cases
*/
SplitChoiceStruct sc;
sc.Plane = plane;
for (int i=0; i<numpolys; i++) {
switch(polys[i].Which_Side(plane)) {
case BPT_FRONT: sc.FrontCount++; break;
case BPT_BACK: sc.BackCount++; break;
case BPT_ON: sc.OnCount++; break;
case BPT_BOTH: sc.SplitCount++; break;
}
}
/*
** Compute the score
*/
float max_splits = min(MAX_SPLITS,numpolys);
float max_on = min(MAX_POLYS_ON_PLANE,numpolys);
float split_score = (float)(max_splits - sc.SplitCount) / max_splits;
if (split_score < 0.0f) split_score = 0.0f;
float on_score = 1.0f - (float)sc.OnCount / max_on;
if (on_score < 0.0f) on_score = 0.0f;
float balance_score = 1.0f - (fabs(sc.FrontCount - sc.BackCount) / ((float)numpolys / 2.0f));
sc.Score = 0.0f;
sc.Score += split_score * POLY_SPLIT_WEIGHT;
sc.Score += balance_score * POLY_COUNT_BALANCE_WEIGHT;
sc.Score += on_score * POLYS_ON_PLANE_WEIGHT;
sc.Score /= TOTAL_WEIGHT;
/*
** Reject the plane if any of the following conditions are true:
** - plane does not reduce the tree! (all polys in front or behind)
** - more than MAX_POLYS_ON_PLANE polygons on the splitting plane
*/
if ((abs(sc.FrontCount-sc.BackCount) == numpolys) && (sc.OnCount == 0)) {
sc.Score = 0.0f;
}
if (sc.OnCount > MAX_POLYS_ON_PLANE) {
sc.Score *= 0.4f;
}
return sc;
}
BptNodeClass::SplitChoiceStruct
BptNodeClass::Select_Splitting_Plane(int numpolys,BptPolyClass * polys)
{
doitagain:
const int NUM_VERTEX_TRYS = 30;
const int NUM_POLY_TRYS = 30;
SplitChoiceStruct best_plane_stats;
SplitChoiceStruct considered_plane_stats;
PlaneClass plane;
/*
** Try putting axis-aligned planes through some random vertices
*/
for (int vertex_trys = 0; vertex_trys < min(NUM_VERTEX_TRYS,3*numpolys); vertex_trys++) {
int poly_index = rand() % numpolys;
int vert_index = rand() % polys[poly_index].NumVerts;;
Vector3 pos = polys[poly_index].Verts[vert_index].Position;
/*
** Try the x-axis
*/
plane.Set(Vector3(1,0,0),pos);
considered_plane_stats = Compute_Plane_Score(numpolys,polys,plane);
if (considered_plane_stats.Score > best_plane_stats.Score) {
best_plane_stats = considered_plane_stats;
}
/*
** Try the y-axis
*/
plane.Set(Vector3(0,1,0),pos);
considered_plane_stats = Compute_Plane_Score(numpolys,polys,plane);
if (considered_plane_stats.Score > best_plane_stats.Score) {
best_plane_stats = considered_plane_stats;
}
}
/*
** Now try "autopartition" planes which come from the input polygons
*/
for (int poly_trys=0; poly_trys<min(NUM_POLY_TRYS,numpolys); poly_trys++) {
int poly_index = rand() % numpolys;
assert(
(polys[poly_index][0].Which_Side(polys[poly_index].Plane) == BPT_ON) &&
(polys[poly_index][1].Which_Side(polys[poly_index].Plane) == BPT_ON) &&
(polys[poly_index][2].Which_Side(polys[poly_index].Plane) == BPT_ON)
);
considered_plane_stats = Compute_Plane_Score(numpolys,polys,polys[poly_index].Plane);
if (considered_plane_stats.Score > best_plane_stats.Score) {
best_plane_stats = considered_plane_stats;
}
}
if (best_plane_stats.Score <= 0.0f) {
_asm int 0x03;
goto doitagain;
}
//assert(best_plane_stats.Score > 0.0f);
return best_plane_stats;
}
void BptNodeClass::Split_Polys
(
const int num_polys,
const BptPolyClass * polys,
const SplitChoiceStruct & sc,
SplitArraysStruct * arrays
)
{
// Note that this routine allocates three arrays of polygons, an array of polys in
// front of the plane, an array of polys behind the plane, and an array of polys on the plane.
// The caller is then responsible for keeping track of the memory this routine allocates.
if (sc.FrontCount + sc.SplitCount > 0) {
arrays->FrontPolys = new BptPolyClass[sc.FrontCount + sc.SplitCount];
}
if (sc.BackCount + sc.SplitCount > 0) {
arrays->BackPolys = new BptPolyClass[sc.BackCount + sc.SplitCount];
}
if (sc.OnCount > 0) {
arrays->OnPolys = new BptPolyClass[sc.OnCount];
}
arrays->FrontCount = 0;
arrays->BackCount = 0;
arrays->OnCount = 0;
for (int i=0; i<num_polys; i++) {
switch(polys[i].Which_Side(sc.Plane)) {
case BPT_FRONT:
arrays->FrontPolys[arrays->FrontCount++] = polys[i];
break;
case BPT_BACK:
arrays->BackPolys[arrays->BackCount++] = polys[i];
break;
case BPT_ON:
arrays->OnPolys[arrays->OnCount++] = polys[i];
break;
case BPT_BOTH:
polys[i].Split(sc.Plane,arrays->FrontPolys[arrays->FrontCount],arrays->BackPolys[arrays->BackCount]);
if (!arrays->FrontPolys[arrays->FrontCount].Is_Degenerate()) {
arrays->FrontCount++;
}
if (!arrays->BackPolys[arrays->BackCount].Is_Degenerate()) {
arrays->BackCount++;
}
break;
}
}
// when we are all done, the counts should match.
assert(arrays->FrontCount <= sc.FrontCount + sc.SplitCount);
assert(arrays->BackCount <= sc.BackCount + sc.SplitCount);
assert(arrays->OnCount == sc.OnCount);
/*
** Check if we threw away all of the polys
** (this can only happen if all of them were degenerate...)
*/
if ((arrays->OnCount == 0) && (arrays->OnPolys != NULL)) {
delete[] arrays->OnPolys;
arrays->OnPolys = NULL;
}
if ((arrays->BackCount == 0) && (arrays->BackPolys != NULL)) {
delete[] arrays->BackPolys;
arrays->BackPolys = NULL;
}
if ((arrays->FrontCount == 0) && (arrays->FrontPolys != NULL)) {
delete[] arrays->FrontPolys;
arrays->FrontPolys = NULL;
}
}
void BptNodeClass::Submit_Polys(MeshBuilderClass & builder) const
{
/*
** Submit the back tree
*/
if (Back) {
Back->Submit_Polys(builder);
}
/*
** Triangulate each poly and submit it to the mesh builder
*/
MeshBuilderClass::FaceClass face;
for (unsigned int fi=0; fi<NumPolys; fi++) {
BptPolyClass * poly = &(Polys[fi]);
for (int ti = 2;ti < poly->NumVerts; ti++) {
face.MaterialIdx = poly->MaterialId;
face.SmGroup = 1; //TODO: get the correct smooth group???
face.Index = 0; //TODO: do we have an actual index?
face.Attributes = 0;
face.Verts[0].Position = poly->Verts[0].Position;
face.Verts[0].TexCoord = poly->Verts[0].TexCoord;
face.Verts[0].Color = poly->Verts[0].Color;
face.Verts[1].Position = poly->Verts[ti-1].Position;
face.Verts[1].TexCoord = poly->Verts[ti-1].TexCoord;
face.Verts[1].Color = poly->Verts[ti-1].Color;
face.Verts[2].Position = poly->Verts[ti].Position;
face.Verts[2].TexCoord = poly->Verts[ti].TexCoord;
face.Verts[2].Color = poly->Verts[ti].Color;
builder.Add_Face(face);
}
}
/*
** Submit the front tree
*/
if (Front) {
Front->Submit_Polys(builder);
}
}
void BptNodeClass::Compute_Bounding_Box(void)
{
/*
** make the children update their boxes first
*/
if (Front) {
Front->Compute_Bounding_Box();
}
if (Back) {
Back->Compute_Bounding_Box();
}
Min.Set(10000.0f,10000.0f,10000.0f);
Max.Set(-10000.0f,-10000.0f,-10000.0f);
/*
** Bound the polys in this node
*/
for (unsigned int poly_index = 0; poly_index < NumPolys; poly_index++) {
for (int vert_index = 0; vert_index < Polys[poly_index].NumVerts; vert_index++) {
Vector3 & point = Polys[poly_index].Verts[vert_index].Position;
if (point.X - BPT_EPSILON < Min.X) Min.X = point.X - BPT_EPSILON;
if (point.X + BPT_EPSILON > Max.X) Max.X = point.X + BPT_EPSILON;
if (point.Y - BPT_EPSILON < Min.Y) Min.Y = point.Y - BPT_EPSILON;
if (point.Y + BPT_EPSILON > Max.Y) Max.Y = point.Y + BPT_EPSILON;
if (point.Z - BPT_EPSILON < Min.Z) Min.Z = point.Z - BPT_EPSILON;
if (point.Z + BPT_EPSILON > Max.Z) Max.Z = point.Z + BPT_EPSILON;
}
}
/*
** bound the polys in the front child node
*/
if (Front) {
if (Front->Min.X < Min.X) Min.X = Front->Min.X;
if (Front->Max.X > Max.X) Max.X = Front->Max.X;
if (Front->Min.Y < Min.Y) Min.Y = Front->Min.Y;
if (Front->Max.Y > Max.Y) Max.Y = Front->Max.Y;
if (Front->Min.Z < Min.Z) Min.Z = Front->Min.Z;
if (Front->Max.Z > Max.Z) Max.Z = Front->Max.Z;
}
/*
** bound the polys in the back child node
*/
if (Back) {
if (Back->Min.X < Min.X) Min.X = Back->Min.X;
if (Back->Max.X > Max.X) Max.X = Back->Max.X;
if (Back->Min.Y < Min.Y) Min.Y = Back->Min.Y;
if (Back->Max.Y > Max.Y) Max.Y = Back->Max.Y;
if (Back->Min.Z < Min.Z) Min.Z = Back->Min.Z;
if (Back->Max.Z > Max.Z) Max.Z = Back->Max.Z;
}
assert(Min.X != 10000.0f);
assert(Min.Y != 10000.0f);
assert(Min.Z != 10000.0f);
assert(Max.X != -10000.0f);
assert(Max.Y != -10000.0f);
assert(Max.Z != -10000.0f);
}
int BptNodeClass::Assign_Array_Indices(int index)
{
/*
** This function is used to assign a sequential index to
** each node in the tree. The BptImp stores its nodes in
** an array so this index is used to determine which slot
** in the array to put each node into.
*/
ArrayIndex = index;
index++;
if (Front) {
index = Front->Assign_Array_Indices(index);
}
if (Back) {
index = Back->Assign_Array_Indices(index);
}
return index;
}
void BptNodeClass::Submit_Nodes(BptImpBuilderClass & imp_builder) const
{
imp_builder.Add_Bpt_Node(this);
if (Front) {
Front->Submit_Nodes(imp_builder);
}
if (Back) {
Back->Submit_Nodes(imp_builder);
}
}
/**************************************************************
BptImpClass Implementation
**************************************************************/
inline bool BptImpNodeClass::Is_Visible(const CameraClass & camera)
{
return !camera.Cull_Box(Vector3(MinX,MinY,MinZ),Vector3(MaxX,MaxY,MaxZ));
}
/**************************************************************
BptImpClass Implementation
**************************************************************/
BptImpClass::BptImpClass(void) :
Mesh(NULL),
NodeCount(0),
Nodes(NULL),
PolyIndexCount(0),
PolyIndices(NULL),
NormalCount(0),
Normals(NULL),
DistanceCount(0),
Distances(NULL),
ActivePolyCount(0),
ActivePolyTable(NULL)
{
}
BptImpClass::~BptImpClass(void)
{
Free();
}
void BptImpClass::Free(void)
{
if (Mesh!=NULL) {
Mesh->Release_Ref();
Mesh = NULL;
}
NodeCount = 0;
if (Nodes != NULL) {
delete[] Nodes;
Nodes = NULL;
}
PolyIndexCount = 0;
if (PolyIndices != NULL) {
delete[] PolyIndices;
PolyIndices = NULL;
}
NormalCount = 0;
if (Normals != NULL) {
delete[] Normals;
Normals = NULL;
}
DistanceCount = 0;
if (Distances != NULL) {
delete[] Distances;
Distances = NULL;
}
}
void BptImpClass::Set_Mesh(MeshClass * mesh)
{
if (Mesh) Mesh->Release_Ref();
Mesh = mesh;
if (Mesh) Mesh->Add_Ref();
}
void BptImpClass::Set_Node_Array(int numnodes, BptImpNodeClass * nodes)
{
if (Nodes) delete[] Nodes;
Nodes = nodes;
NodeCount = numnodes;
}
void BptImpClass::Set_Normal_Array(const UniqueArrayClass<Vector3> & normals)
{
if (normals.Count() != NormalCount) {
if (Normals) delete[] Normals;
Normals = new Vector3[normals.Count()];
}
NormalCount = normals.Count();
for (int i=0; i<NormalCount; i++) {
Normals[i] = normals.Get(i);
}
}
void BptImpClass::Set_Distance_Array(const UniqueArrayClass<float> & distances)
{
if (distances.Count() != DistanceCount) {
if (Distances) delete[] Distances;
Distances = new float[distances.Count()];
}
DistanceCount = distances.Count();
for (int i=0; i<DistanceCount; i++) {
Distances[i] = distances.Get(i);
}
}
void BptImpClass::Set_Poly_Index_Array(int numremaps,int * polyremaps)
{
if (PolyIndices) delete[] PolyIndices;
PolyIndices = polyremaps;
PolyIndexCount = numremaps;
}
void BptImpClass::Build_Apt(const CameraClass & camera)
{
WWDEBUG_PROFILE_START("BPT::Build_Apt");
Begin_Apt();
Build_Apt_Recursive(&(Nodes[0]),camera);
End_Apt();
WWDEBUG_PROFILE_STOP("BPT::Build_Apt");
}
void BptImpClass::Begin_Apt(void)
{
ActivePolyCount = 0;
ActivePolyTable = Mesh->Get_Surrender_Mesh()->getActivePolygonTable();
}
void BptImpClass::Add_Polys_To_Apt(BptImpNodeClass * node)
{
assert(node != NULL);
#if 0
memcpy(&(ActivePolyTable[ActivePolyCount]),&(PolyIndices[node->FirstPoly]),node->PolyCount);
ActivePolyCount += node->PolyCount;
#else
for (int poly_index=0; poly_index<node->PolyCount; poly_index++) {
ActivePolyTable[ActivePolyCount++] = PolyIndices[node->FirstPoly + poly_index];
}
#endif
}
void BptImpClass::End_Apt(void)
{
Mesh->Get_Surrender_Mesh()->setActivePolygonCount(ActivePolyCount);
// WWDEBUG_SAY(("Active Polys: %d\r\n",ActivePolyCount));
}
void BptImpClass::Build_Apt_Recursive(BptImpNodeClass * node,const CameraClass & cam)
{
/*
** Check the camera's frustum against this node's
** bounding volume
*/
if (!node->Is_Visible(cam)) {
Verify_Node_Bounding_Volume(node,Vector3(node->MinX,node->MinY,node->MinZ),Vector3(node->MaxX,node->MaxY,node->MaxZ));
return;
}
/*
** Ok part of this tree may be visible, compute
** which side of the splitting plane the camera is on
*/
float dist = Vector3::Dot_Product(Normals[node->NormalIndex],cam.Get_Position());
if (dist > Distances[node->DistanceIndex]) {
/*
** FRONT:
** We are in front of the plane so proceed in the following order:
** Visit the 'Back' node
** Add our polys to the APT
** Visit the 'Front' node
*/
if (node->Back) Build_Apt_Recursive(node->Back,cam);
Add_Polys_To_Apt(node);
if (node->Front) Build_Apt_Recursive(node->Front,cam);
} else {
/*
** BACK:
** We are in back of the plane so proceed in the following order:
** Visit the 'Front' node
** Add our polys to the APT
** Visit the 'Back' node
*/
if (node->Front) Build_Apt_Recursive(node->Front,cam);
Add_Polys_To_Apt(node);
if (node->Back) Build_Apt_Recursive(node->Back,cam);
}
}
bool BptImpClass::Cast_Ray(PhysRayCollisionTestClass & raytest) const
{
return Cast_Ray_Recursive(&(Nodes[0]),raytest);
}
bool BptImpClass::Cast_AABox(PhysAABoxCollisionTestClass & boxtest) const
{
/*
** Test the sweeping AABox against the BPT recursively!
*/
WWDEBUG_PROFILE_START("BPT::Cast_AABox");
bool res = Cast_AABox_Recursive(&(Nodes[0]),boxtest);
WWDEBUG_PROFILE_STOP("BPT::Cast_AABox");
return res;
}
bool BptImpClass::Cast_OBBox(PhysOBBoxCollisionTestClass & boxtest) const
{
return Cast_OBBox_Recursive(&(Nodes[0]),boxtest);
}
bool BptImpClass::Cast_Ray_Recursive
(
BptImpNodeClass * node,
PhysRayCollisionTestClass & raytest
) const
{
return false;
}
bool BptImpClass::Cast_AABox_Recursive
(
BptImpNodeClass * node,
PhysAABoxCollisionTestClass & boxtest
) const
{
/*
** First, check the bounding box of the move against the bounding box
** of this tree, if they don't intersect, bail out
*/
if ((boxtest.SweepMin.X > node->MaxX) || (boxtest.SweepMax.X < node->MinX)) {
return false;
}
if ((boxtest.SweepMin.Y > node->MaxY) || (boxtest.SweepMax.Y < node->MinY)) {
return false;
}
if ((boxtest.SweepMin.Z > node->MaxZ) || (boxtest.SweepMax.Z < node->MinZ)) {
return false;
}
if (node->Front) {
Cast_AABox_Recursive(node->Front,boxtest);
}
Cast_AABox_To_Polys(node,boxtest);
if (node->Back) {
Cast_AABox_Recursive(node->Back,boxtest);
}
return false;
}
bool BptImpClass::Cast_OBBox_Recursive
(
BptImpNodeClass * node,
PhysOBBoxCollisionTestClass & boxtest
) const
{
return false;
}
bool BptImpClass::Cast_AABox_To_Polys(BptImpNodeClass * node,PhysAABoxCollisionTestClass & boxtest) const
{
/*
** Simply loop through the polys in this node, checking each for collision
*/
TriClass tri;
srMeshModel * srmesh = Mesh->Get_Surrender_Mesh();
srVector3 * loc = srmesh->getVertexLoc();
srVector4 * norms = srmesh->getPolyEq();
srVector3i * polyverts = srmesh->getPolyVertex();
int polyhit = -1;
for (int poly_counter=0; poly_counter<node->PolyCount; poly_counter++) {
int poly_index = PolyIndices[node->FirstPoly + poly_counter];
tri.V[0] = As_Vector3(&(loc[ polyverts[poly_index][0] ]));
tri.V[1] = As_Vector3(&(loc[ polyverts[poly_index][1] ]));
tri.V[2] = As_Vector3(&(loc[ polyverts[poly_index][2] ]));
tri.N = (Vector3 *)&(norms[poly_index]);
if ( boxtest.Box.Cast_To_Tri(boxtest.Move,tri,boxtest.Result) ) {;
polyhit = poly_index;
}
if (boxtest.Result->StartBad) {
return true;
}
}
if (polyhit != -1) {
return true;
}
return false;
}
void BptImpClass::Verify_Node_Bounding_Volume(BptImpNodeClass * node,const Vector3 & min,const Vector3 & max) const
{
srMeshModel * srmesh = Mesh->Get_Surrender_Mesh();
srVector3 * loc = srmesh->getVertexLoc();
srVector3i * polyverts = srmesh->getPolyVertex();
Vector3 * v;
for (int remap_index = node->FirstPoly; remap_index < node->FirstPoly + node->PolyCount; remap_index++) {
int poly_index = PolyIndices[remap_index];
v = As_Vector3(&loc[ polyverts[poly_index][0] ]);
assert(v->X >= min.X);
assert(v->Y >= min.Y);
assert(v->Z >= min.Z);
assert(v->X <= max.X);
assert(v->Y <= max.Y);
assert(v->Z <= max.Z);
v = As_Vector3(&loc[ polyverts[poly_index][1] ]);
assert(v->X >= min.X);
assert(v->Y >= min.Y);
assert(v->Z >= min.Z);
assert(v->X <= max.X);
assert(v->Y <= max.Y);
assert(v->Z <= max.Z);
v = As_Vector3(&loc[ polyverts[poly_index][2] ]);
assert(v->X >= min.X);
assert(v->Y >= min.Y);
assert(v->Z >= min.Z);
assert(v->X <= max.X);
assert(v->Y <= max.Y);
assert(v->Z <= max.Z);
}
if (node->Back) {
Verify_Node_Bounding_Volume(node->Back,min,max);
}
if (node->Front) {
Verify_Node_Bounding_Volume(node->Front,min,max);
}
}
/**************************************************************
BptImpBuilderClass Implementation
**************************************************************/
BptImpBuilderClass::BptImpBuilderClass(void) :
MeshBuilder(true,10000,5000), // TODO: should move this to Build_Bpt_Imp so it is dynamically initialzed
UniqueNormals(NULL),
UniqueDistances(NULL),
NodeCount(0),
Nodes(NULL),
TriCount(0),
CurTriIndex(0),
TriIndexArray(NULL)
{
}
BptImpBuilderClass::~BptImpBuilderClass(void)
{
Free();
}
void BptImpBuilderClass::Free(void)
{
if (UniqueNormals != NULL) {
delete UniqueNormals;
UniqueNormals = NULL;
}
if (UniqueDistances != NULL) {
delete UniqueDistances;
UniqueDistances = NULL;
}
NodeCount = 0;
if (Nodes != NULL) {
delete[] Nodes;
Nodes = NULL;
}
TriCount = 0;
CurTriIndex = 0;
if (TriIndexArray != NULL) {
delete[] TriIndexArray;
TriIndexArray = NULL;
}
}
BptImpClass * BptImpBuilderClass::Build_Bpt_Imp(BptNodeClass * root,MaterialInfoClass * matinfo)
{
Free();
WWDEBUG_SAY(("Building the Run-Time Bpt\r\n"));
TriCount = root->Num_Tris();
/*
** Allocate the UniqueNormals and UniqueDistances objects
*/
int size = TriCount;
int growth = TriCount / 3;
if (growth < 5) growth = 5;
UniqueNormals = new UniqueArrayClass<Vector3>(size,growth,&NormalHasher);
UniqueDistances = new UniqueArrayClass<float>(size,growth,&DistanceHasher);
/*
** Set up the mesh builder
*/
MeshBuilder.Reset(true,TriCount,growth);
MeshBuilder.Disable_All_Vertex_Channels();
MeshBuilder.Enable_Vertex_Channel(MeshBuilderClass::VERTEX_CHANNEL_NORMAL);
// MeshBuilder.Enable_Vertex_Channel(MeshBuilderClass::VERTEX_CHANNEL_COLOR);
MeshBuilder.Enable_Vertex_Channel(MeshBuilderClass::VERTEX_CHANNEL_TEXCOORD);
/*
** Allocate the array of triangle indices, set
** CurTriIndex to point to the top.
*/
TriIndexArray = new int[TriCount];
CurTriIndex = 0;
/*
** Allocate the array of nodes
*/
NodeCount = root->Num_Nodes();
Nodes = new BptImpNodeClass[NodeCount];
/*
** Compute the hierarchical bounding boxes
*/
WWDEBUG_SAY(("Computing Hierarchical Bounding Volumes.\r\n"));
root->Compute_Bounding_Box();
WWDEBUG_SAY(("Hierarchical Bounding Volumes Done.\r\n"));
/*
** Have the tree "unwind" itself into our arrays
*/
root->Assign_Array_Indices(0);
root->Submit_Nodes(*this);
/*
** Process the mesh
*/
MeshBuilder.Build_Mesh(true);
/*
** Remap all of the polygon indices (account for the
** mesh builder re-ording polygons)
*/
Remap_Triangle_Indices();
/*
** Create the BptImpClass
*/
MeshClass * mesh = new MeshClass();
mesh->Init(MeshBuilder,matinfo,"BspMesh","");
BptImpClass * bptimp = new BptImpClass();
bptimp->Set_Mesh(mesh);
bptimp->Set_Node_Array(NodeCount,Nodes);
bptimp->Set_Poly_Index_Array(TriCount,TriIndexArray);
bptimp->Set_Normal_Array(*UniqueNormals);
bptimp->Set_Distance_Array(*UniqueDistances);
// the "imp" assumed ownership of this stuff
mesh->Release_Ref();
mesh = NULL;
Nodes = NULL;
TriIndexArray = NULL;
Free();
WWDEBUG_SAY(("Run-Time Bpt Done\r\n"));
WWDEBUG_SAY(("\r\n"));
return bptimp;
}
void BptImpBuilderClass::Add_Bpt_Node(const BptNodeClass * node)
{
BptImpNodeClass newnode;
/*
** initialize the front pointer
*/
if (node->Front) {
assert(node->Front->ArrayIndex >= 0);
assert(node->Front->ArrayIndex < NodeCount);
newnode.Front = &(Nodes[node->Front->ArrayIndex]);
} else {
newnode.Front = NULL; //BptImpNodeClass::NULL_NODE_INDEX;
}
/*
** initialize the back pointer
*/
if (node->Back) {
assert(node->Back->ArrayIndex >= 0);
assert(node->Back->ArrayIndex < NodeCount);
newnode.Back = &(Nodes[node->Back->ArrayIndex]);
} else {
newnode.Back = NULL; //BptImpNodeClass::NULL_NODE_INDEX;
}
/*
** Triangulate each poly and submit it to the mesh builder
** install the Triangle Remap Indices as we go
*/
newnode.FirstPoly = CurTriIndex;
newnode.PolyCount = 0;
MeshBuilderClass::FaceClass face;
for (unsigned int fi=0; fi<node->NumPolys; fi++) {
BptPolyClass * poly = &(node->Polys[fi]);
for (int ti = 2;ti < poly->NumVerts; ti++) {
face.MaterialIdx = poly->MaterialId;
face.SmGroup = 1; //TODO: get the correct smooth group???
face.Index = 0; //TODO: do we have an actual index?
face.Attributes = 0;
face.Verts[0].Position = poly->Verts[0].Position;
face.Verts[0].TexCoord = poly->Verts[0].TexCoord;
face.Verts[0].Color = poly->Verts[0].Color;
face.Verts[1].Position = poly->Verts[ti-1].Position;
face.Verts[1].TexCoord = poly->Verts[ti-1].TexCoord;
face.Verts[1].Color = poly->Verts[ti-1].Color;
face.Verts[2].Position = poly->Verts[ti].Position;
face.Verts[2].TexCoord = poly->Verts[ti].TexCoord;
face.Verts[2].Color = poly->Verts[ti].Color;
TriIndexArray[CurTriIndex] = MeshBuilder.Add_Face(face);
CurTriIndex++;
newnode.PolyCount++;
/*
** just verifying that all verts are inside the bounding box
*/
assert(face.Verts[0].Position.X >= node->Min.X);
assert(face.Verts[0].Position.Y >= node->Min.Y);
assert(face.Verts[0].Position.Z >= node->Min.Z);
assert(face.Verts[1].Position.X >= node->Min.X);
assert(face.Verts[1].Position.Y >= node->Min.Y);
assert(face.Verts[1].Position.Z >= node->Min.Z);
assert(face.Verts[2].Position.X >= node->Min.X);
assert(face.Verts[2].Position.Y >= node->Min.Y);
assert(face.Verts[2].Position.Z >= node->Min.Z);
assert(face.Verts[0].Position.X <= node->Max.X);
assert(face.Verts[0].Position.Y <= node->Max.Y);
assert(face.Verts[0].Position.Z <= node->Max.Z);
assert(face.Verts[1].Position.X <= node->Max.X);
assert(face.Verts[1].Position.Y <= node->Max.Y);
assert(face.Verts[1].Position.Z <= node->Max.Z);
assert(face.Verts[2].Position.X <= node->Max.X);
assert(face.Verts[2].Position.Y <= node->Max.Y);
assert(face.Verts[2].Position.Z <= node->Max.Z);
}
}
/*
** Bounding box
*/
newnode.MinX = node->Min.X;
newnode.MinY = node->Min.Y;
newnode.MinZ = node->Min.Z;
newnode.MaxX = node->Max.X;
newnode.MaxY = node->Max.Y;
newnode.MaxZ = node->Max.Z;
assert(newnode.MinX <= newnode.MaxX);
assert(newnode.MinY <= newnode.MaxY);
assert(newnode.MinZ <= newnode.MaxZ);
/*
** Plane Equation
*/
assert(UniqueNormals);
assert(UniqueDistances);
newnode.NormalIndex = UniqueNormals->Add(node->Plane.N);
newnode.DistanceIndex = UniqueDistances->Add(node->Plane.D);
/*
** install the node!
*/
Nodes[node->ArrayIndex] = newnode;
}
void BptImpBuilderClass::Remap_Triangle_Indices(void)
{
int pi;
int * index_remap = new int[MeshBuilder.Get_Face_Count()];
assert(MeshBuilder.Get_Face_Count() == TriCount);
for (pi=0; pi < MeshBuilder.Get_Face_Count(); pi++) {
const MeshBuilderClass::FaceClass & face = MeshBuilder.Get_Face(pi);
assert(face.AddIndex >= 0);
assert(face.AddIndex < TriCount);
index_remap[ face.AddIndex ] = pi;
}
for (pi=0; pi < TriCount; pi++) {
TriIndexArray[pi] = index_remap[TriIndexArray[pi]];
}
delete[] index_remap;
}
#endif // PORT140
#endif // OBSOLETE!
Reference in a new issue View git blame Copy permalink