/*
** 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 .
*/
/***********************************************************************************************
*** 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 : WW3D *
* *
* $Archive:: /Commando/Code/ww3d2/aabtree.cpp $*
* *
* Author:: Greg Hjelstrom *
* *
* $Modtime:: 11/24/01 5:34p $*
* *
* $Revision:: 4 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* AABTreeClass::AABTreeClass -- Constructor *
* AABTreeClass::AABTreeClass -- Constructor *
* AABTreeClass::AABTreeClass -- copy constructor *
* AABTreeClass::~AABTreeClass -- Destructor *
* AABTreeClass::operator = -- assignment operator *
* AABTreeClass::Reset -- reset this tree, releases all allocated resources *
* AABTreeClass::Build_Tree_Recursive -- Initializes this tree from the given builder *
* AABTreeClass::Set_Mesh -- set the mesh pointer *
* AABTreeClass::Generate_APT -- Generate an active poly table for the mesh *
* AABTreeClass::Generate_OBBox_APT_Recursive -- recursively generate the apt *
* AABTreeClass::Cast_Ray_Recursive -- Internal implementation of Cast_Ray *
* AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive -- Internal implementation *
* AABTreeClass::Cast_AABox_Recursive -- internal implementation of Cast_AABox *
* AABTreeClass::Cast_OBBox_Recursive -- Internal implementation of Cast_OBBox *
* AABTreeClass::Intersect_OBBox_Recursive -- internal implementation of Intersect_OBBox *
* AABTreeClass::Cast_Ray_To_Polys -- cast the ray to polys in the given node *
* AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys -- cast ray to polys in the nod*
* AABTreeClass::Cast_AABox_To_Polys -- cast aabox to polys in the given node *
* AABTreeClass::Cast_OBBox_To_Polys -- cast obbox to polys in the given node *
* AABTreeClass::Intersect_OBBox_With_Polys -- Test polys for intersection *
* AABTreeClass::Update_Bounding_Boxes_Recursive -- recompute the bounding boxes *
* AABTreeClass::Update_Min_Max -- updates min and max given a polygon index *
* AABTreeClass::Load_W3D -- Load a W3D description of an AABTree *
* AABTreeClass::Read_Poly_Indices -- load the polygon index array *
* AABTreeClass::Read_Nodes -- Load the node array *
* AABTreeClass::Generate_APT -- generate an apt from a box and viewdir *
* AABTreeClass::Generate_OBBox_APT_Recursive -- recurse, generate the apt for a box and vie *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#include "aabtree.h"
#include "aabtreebuilder.h"
#include "wwdebug.h"
#include "tri.h"
#include "meshgeometry.h"
#include "camera.h"
#include "coltest.h"
#include "inttest.h"
#include "colmathinlines.h"
#include "w3d_file.h"
#include "chunkio.h"
/***********************************************************************************************
* AABTreeClass::AABTreeClass -- Constructor *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
*=============================================================================================*/
AABTreeClass::AABTreeClass(void) :
NodeCount(0),
Nodes(NULL),
PolyCount(0),
PolyIndices(NULL),
Mesh(NULL)
{
}
/***********************************************************************************************
* AABTreeClass::AABTreeClass -- Constructor *
* *
* Builds an AABTree from the contents of an AABTreeBuilderClass. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
* 5/23/2000 gth : Created. *
*=============================================================================================*/
AABTreeClass::AABTreeClass(AABTreeBuilderClass * builder)
{
NodeCount = builder->Node_Count();
Nodes = new AABTreeClass::CullNodeStruct[NodeCount];
PolyCount = builder->Poly_Count();
PolyIndices = new uint32[PolyCount];
int curpolyindex = 0;
Build_Tree_Recursive(builder->Root,curpolyindex);
}
/***********************************************************************************************
* AABTreeClass::AABTreeClass -- copy constructor *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/22/99 GTH : Created. *
*=============================================================================================*/
AABTreeClass::AABTreeClass(const AABTreeClass & that) :
NodeCount(0),
Nodes(NULL),
PolyCount(0),
PolyIndices(0),
Mesh(NULL)
{
*this = that;
}
/***********************************************************************************************
* AABTreeClass::~AABTreeClass -- Destructor *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
*=============================================================================================*/
AABTreeClass::~AABTreeClass(void)
{
Reset();
}
/***********************************************************************************************
* AABTreeClass::operator = -- assignment operator *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/22/99 GTH : Created. *
*=============================================================================================*/
AABTreeClass & AABTreeClass::operator = (const AABTreeClass & that)
{
Reset();
NodeCount = that.NodeCount;
if (NodeCount > 0) {
Nodes = new CullNodeStruct[NodeCount];
memcpy(Nodes,that.Nodes,NodeCount * sizeof(CullNodeStruct));
}
PolyCount = that.PolyCount;
if (PolyCount > 0) {
PolyIndices = new uint32[PolyCount];
memcpy(PolyIndices,that.PolyIndices,PolyCount * sizeof(uint32));
}
Mesh = that.Mesh;
return *this;
}
/***********************************************************************************************
* AABTreeClass::Reset -- reset this tree, releases all allocated resources *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/22/99 GTH : Created. *
*=============================================================================================*/
void AABTreeClass::Reset(void)
{
NodeCount = 0;
if (Nodes) {
delete[] Nodes;
Nodes = NULL;
}
PolyCount = 0;
if (PolyIndices) {
delete[] PolyIndices;
PolyIndices = NULL;
}
if (Mesh) {
Mesh = NULL;
}
}
/***********************************************************************************************
* AABTreeClass::Build_Tree_Recursive -- Initializes this tree from the given builder *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/19/2000 gth : Created. *
*=============================================================================================*/
void AABTreeClass::Build_Tree_Recursive(AABTreeBuilderClass::CullNodeStruct * node,int & curpolyindex)
{
/*
** Copy data from the builder's node into our node
*/
CullNodeStruct * newnode = &(Nodes[node->Index]);
newnode->Min = node->Min;
newnode->Max = node->Max;
/*
** If this is a non-leaf node, set up the child indices, otherwise set up the polygon indices
*/
if (node->Front != NULL) {
WWASSERT(node->Back != NULL); // if we have one child, we better have both!
newnode->Set_Front_Child(node->Front->Index);
newnode->Set_Back_Child(node->Back->Index);
} else {
newnode->Set_Poly0(curpolyindex);
newnode->Set_Poly_Count(node->PolyCount);
}
/*
** Copy the polygon indices for this node into our array
*/
for (int pcounter = 0; pcounter < node->PolyCount; pcounter++) {
PolyIndices[curpolyindex++] = node->PolyIndices[pcounter];
}
/*
** Install the children
*/
if (node->Front) {
Build_Tree_Recursive(node->Front,curpolyindex);
}
if (node->Back) {
Build_Tree_Recursive(node->Back,curpolyindex);
}
}
/***********************************************************************************************
* AABTreeClass::Set_Mesh -- set the mesh pointer *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/22/99 GTH : Created. *
*=============================================================================================*/
void AABTreeClass::Set_Mesh(MeshGeometryClass * mesh)
{
Mesh = mesh;
}
/***********************************************************************************************
* AABTreeClass::Generate_APT -- Generate an active poly table for the mesh *
* *
* INPUT: *
* box - oriented box to cull the mesh against (in the mesh's coordinate system!!!) *
* apt - vector of ints to fill the apt into *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
*=============================================================================================*/
void AABTreeClass::Generate_APT(const OBBoxClass & box,SimpleDynVecClass & apt)
{
OBBoxAPTContextStruct context(box,apt);
Generate_OBBox_APT_Recursive(&(Nodes[0]),context);
}
/***********************************************************************************************
* AABTreeClass::Generate_OBBox_APT_Recursive -- recursively generate the apt *
* *
* INPUT: *
* node - current node in the recursion *
* context - structure containing the results/current state *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 1/25/00 gth : Created. *
*=============================================================================================*/
void AABTreeClass::Generate_OBBox_APT_Recursive(CullNodeStruct * node,OBBoxAPTContextStruct & context)
{
/*
** Test the volume against the bounding volume of this node
** If it is outside, stop descending the tree.
*/
AABoxClass nodebox;
nodebox.Init_Min_Max(node->Min,node->Max); // NOTE: too bad we have to compute the nodebox!!!
if (!CollisionMath::Intersection_Test(context.Box,nodebox)) {
return;
}
/*
** If this is a leaf, test its polygons, otherwise recurse into the children
*/
if (node->Is_Leaf()) {
int polycount = node->Get_Poly_Count();
int poly0 = node->Get_Poly0();
if (polycount > 0) {
TriClass tri;
const Vector3 * loc = Mesh->Get_Vertex_Array();
const TriIndex * polys = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
const Vector4 * norms = Mesh->Get_Plane_Array();
#endif
for (int poly_counter=0; poly_counterGet_Front_Child()]),context);
Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Back_Child()]),context);
}
}
/***********************************************************************************************
* AABTreeClass::Generate_APT -- generate an apt from a box and viewdir *
* *
* Indices of the polys which intersect the box and are not backfacing to the given viewdir *
* will be added to the passed in apt. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/10/2001 gth : Created. *
*=============================================================================================*/
void AABTreeClass::Generate_APT
(
const OBBoxClass & box,
const Vector3 & viewdir,
SimpleDynVecClass & apt
)
{
OBBoxRayAPTContextStruct context(box,viewdir,apt);
Generate_OBBox_APT_Recursive(&(Nodes[0]),context);
}
/***********************************************************************************************
* AABTreeClass::Generate_OBBox_APT_Recursive -- recurse, generate the apt for a box and viewd *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/10/2001 gth : Created. *
*=============================================================================================*/
void AABTreeClass::Generate_OBBox_APT_Recursive(CullNodeStruct * node, OBBoxRayAPTContextStruct & context)
{
/*
** Test the volume against the bounding volume of this node
** If it is outside, stop descending the tree.
*/
AABoxClass nodebox;
nodebox.Init_Min_Max(node->Min,node->Max); // NOTE: too bad we have to compute the nodebox!!!
if (!CollisionMath::Intersection_Test(context.Box,nodebox)) {
return;
}
/*
** If this is a leaf, test its polygons, otherwise recurse into the children
*/
if (node->Is_Leaf()) {
int polycount = node->Get_Poly_Count();
int poly0 = node->Get_Poly0();
if (polycount > 0) {
TriClass tri;
const Vector3 * loc = Mesh->Get_Vertex_Array();
const TriIndex * polys = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
const Vector4 * norms = Mesh->Get_Plane_Array();
#endif
for (int poly_counter=0; poly_counterGet_Front_Child()]),context);
Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Back_Child()]),context);
}
}
/***********************************************************************************************
* AABTreeClass::Cast_Ray_Recursive -- Internal implementation of Cast_Ray *
* *
* INPUT: *
* raytest - contains all of the ray test information *
* node - current cull node being processed *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
*=============================================================================================*/
bool AABTreeClass::Cast_Ray_Recursive(CullNodeStruct * node,RayCollisionTestClass & raytest)
{
/*
** Cull the collision test against the bounding volume of this node
** If it is culled, stop descending the tree.
*/
if (raytest.Cull(node->Min,node->Max)) {
return false;
}
bool res = false;
if (node->Is_Leaf()) {
return Cast_Ray_To_Polys(node,raytest);
} else {
res = res | Cast_Ray_Recursive(&(Nodes[node->Get_Front_Child()]),raytest);
res = res | Cast_Ray_Recursive(&(Nodes[node->Get_Back_Child()]),raytest);
}
return res;
}
/***********************************************************************************************
* AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive -- Internal implementation *
* *
* INPUT: *
* node - current cull node being processed *
* start_point - starting point *
* axis_r - the axis along which the ray is projected *
* axis_1, axis_2 - the other two axes *
* direction - 0 means the ray goes toward the negative axis, 1 means positive. *
* flags - reference bitfield for result flags (ray hit edge, start point embedded in tri, etc)*
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/30/00 NH : Created. *
*=============================================================================================*/
int AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(CullNodeStruct * node,
const Vector3 & start_point, int axis_r, int axis_1, int axis_2, int direction,
unsigned char & flags)
{
/*
** Cull the ray against the bounding volume of this node
** If it is culled, stop descending the tree.
** We do two main tests: a 2D test against axis1 and axis2 to see if the starting point (and
** hence the ray) falls within the 2D projection of the bbox, and a 1D test to see if the ray
** is completely above or below the bbox. The second test checks (start > max) or (start < min)
** depending on the direction of the ray - we do this in a branchless fashion by turning
** (start < min) into (-start > -min). Then we can use tables to perform the correct check.
*/
static const float sign[2] = { -1.0f, 1.0f };
float bounds[2], start[2];
bounds[0] = -node->Min[axis_r];
bounds[1] = node->Max[axis_r];
start[0] = -start_point[axis_r];
start[1] = start_point[axis_r];
if ( start_point[axis_1] < node->Min[axis_1] || start_point[axis_2] < node->Min[axis_2] ||
start_point[axis_1] > node->Max[axis_1] || start_point[axis_2] > node->Max[axis_2] ||
start[direction] > bounds[direction] ) {
return 0;
}
int count = 0;
if (node->Is_Leaf()) {
return Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys(node, start_point, axis_r, axis_1,
axis_2, direction, flags);
} else {
count += Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(&(Nodes[node->Get_Front_Child()]),
start_point, axis_r, axis_1, axis_2, direction, flags);
count += Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(&(Nodes[node->Get_Back_Child()]),
start_point, axis_r, axis_1, axis_2, direction, flags);
}
return count;
}
/***********************************************************************************************
* AABTreeClass::Cast_AABox_Recursive -- internal implementation of Cast_AABox *
* *
* INPUT: *
* boxtest - contains description of the collision operation to be performed *
* node - current cull node being processed *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
*=============================================================================================*/
bool AABTreeClass::Cast_AABox_Recursive(CullNodeStruct * node,AABoxCollisionTestClass & boxtest)
{
/*
** First, check the bounding box of the move against the bounding box
** of this tree, if they don't intersect, bail out
*/
if (boxtest.Cull(node->Min,node->Max)) {
return false;
}
bool res = false;
if (node->Is_Leaf()) {
return Cast_AABox_To_Polys(node,boxtest);
} else {
res = res | Cast_AABox_Recursive(&(Nodes[node->Get_Front_Child()]),boxtest);
res = res | Cast_AABox_Recursive(&(Nodes[node->Get_Back_Child()]),boxtest);
}
return res;
}
/***********************************************************************************************
* AABTreeClass::Cast_OBBox_Recursive -- Internal implementation of Cast_OBBox *
* *
* INPUT: *
* boxtest - contains description of the collision test to be performed *
* node - current cull node being processed *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
*=============================================================================================*/
bool AABTreeClass::Cast_OBBox_Recursive(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest)
{
/*
** First, check the bounding box of the move against the bounding box
** of this tree, if they don't intersect, bail out
*/
if (boxtest.Cull(node->Min,node->Max)) {
return false;
}
bool res = false;
if (node->Is_Leaf()) {
return Cast_OBBox_To_Polys(node,boxtest);
} else {
res = res | Cast_OBBox_Recursive(&(Nodes[node->Get_Front_Child()]),boxtest);
res = res | Cast_OBBox_Recursive(&(Nodes[node->Get_Back_Child()]),boxtest);
}
return res;
}
/***********************************************************************************************
* AABTreeClass::Intersect_OBBox_Recursive -- internal implementation of Intersect_OBBox *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 1/20/00 gth : Created. *
*=============================================================================================*/
bool AABTreeClass::Intersect_OBBox_Recursive(AABTreeClass::CullNodeStruct * node,OBBoxIntersectionTestClass & test)
{
/*
** Cull the collision test against the bounding volume of this node
** If it is culled, stop descending the tree.
*/
if (test.Cull(node->Min,node->Max)) {
return false;
}
bool res = false;
if (node->Is_Leaf()) {
return Intersect_OBBox_With_Polys(node,test);
} else {
res = res | Intersect_OBBox_Recursive(&(Nodes[node->Get_Front_Child()]),test);
res = res | Intersect_OBBox_Recursive(&(Nodes[node->Get_Back_Child()]),test);
}
return res;
}
/***********************************************************************************************
* AABTreeClass::Cast_Ray_To_Polys -- cast the ray to polys in the given node *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
*=============================================================================================*/
bool AABTreeClass::Cast_Ray_To_Polys(CullNodeStruct * node,RayCollisionTestClass & raytest)
{
if (node->Get_Poly_Count() > 0) {
/*
** Simply loop through the polys in this node, checking each for collision
*/
TriClass tri;
const Vector3 * loc = Mesh->Get_Vertex_Array();
const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
const Vector4 * norms = Mesh->Get_Plane_Array();
#endif
int polyhit = -1;
int poly0 = node->Get_Poly0();
int polycount = node->Get_Poly_Count();
for (int poly_counter=0; poly_counterStartBad) {
return true;
}
}
if (polyhit != -1) {
raytest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
return true;
}
}
return false;
}
/***********************************************************************************************
* AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys -- cast ray to polys in the node *
* *
* INPUT: *
* node - current cull node being processed *
* start_point - starting point *
* axis_r - the axis along which the ray is projected *
* axis_1, axis_2 - the other two axes *
* direction - 0 means the ray goes toward the negative axis, 1 means positive. *
* flags - reference bitfield for result flags (ray hit edge, start point embedded in tri, etc)*
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/30/00 NH : Created. *
*=============================================================================================*/
int AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys(CullNodeStruct * node,
const Vector3 & start_point, int axis_r, int axis_1, int axis_2, int direction,
unsigned char & flags)
{
int count = 0;
if (node->Get_Poly_Count() > 0) {
/*
** Simply loop through the polys in this node, checking each for collision
*/
const Vector3 * loc = Mesh->Get_Vertex_Array();
const TriIndex * polyverts = Mesh->Get_Polygon_Array();
const Vector4 * plane = Mesh->Get_Plane_Array();
int poly0 = node->Get_Poly0();
int polycount = node->Get_Poly_Count();
for (int poly_counter=0; poly_counter < polycount; poly_counter++) {
int poly_index = PolyIndices[poly0 + poly_counter];
const Vector3 &v0 = loc[ polyverts[poly_index][0] ];
const Vector3 &v1 = loc[ polyverts[poly_index][1] ];
const Vector3 &v2 = loc[ polyverts[poly_index][2] ];
const Vector4 &tri_plane = plane[poly_index];
// Since (int)true is defined as 1, and (int)false as 0:
count += (unsigned int)Cast_Semi_Infinite_Axis_Aligned_Ray_To_Triangle(v0, v1, v2,
tri_plane, start_point, axis_r, axis_1, axis_2, direction, flags);
}
}
return count;
}
/***********************************************************************************************
* AABTreeClass::Cast_AABox_To_Polys -- cast aabox to polys in the given node *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
*=============================================================================================*/
bool AABTreeClass::Cast_AABox_To_Polys(CullNodeStruct * node,AABoxCollisionTestClass & boxtest)
{
if (node->Get_Poly_Count() > 0) {
/*
** Simply loop through the polys in this node, checking each for collision
*/
TriClass tri;
const Vector3 * loc = Mesh->Get_Vertex_Array();
const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
const Vector4 * norms = Mesh->Get_Plane_Array();
#endif
int polyhit = -1;
int poly0 = node->Get_Poly0();
int polycount = node->Get_Poly_Count();
for (int poly_counter=0; poly_counterStartBad) {
return true;
}
}
if (polyhit != -1) {
boxtest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
return true;
}
}
return false;
}
/***********************************************************************************************
* AABTreeClass::Cast_OBBox_To_Polys -- cast obbox to polys in the given node *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/19/98 GTH : Created. *
*=============================================================================================*/
bool AABTreeClass::Cast_OBBox_To_Polys(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest)
{
int polycount = node->Get_Poly_Count();
int poly0 = node->Get_Poly0();
if (polycount > 0) {
/*
** Simply loop through the polys in this node, checking each for collision
*/
TriClass tri;
const Vector3 * loc = Mesh->Get_Vertex_Array();
const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
const Vector4 * norms = Mesh->Get_Plane_Array();
#endif
int polyhit = -1;
for (int poly_counter=0; poly_counterStartBad) {
return true;
}
}
if (polyhit != -1) {
boxtest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
return true;
}
}
return false;
}
/***********************************************************************************************
* AABTreeClass::Intersect_OBBox_With_Polys -- Test polys for intersection *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 1/20/00 gth : Created. *
*=============================================================================================*/
bool AABTreeClass::Intersect_OBBox_With_Polys
(
CullNodeStruct * node,
OBBoxIntersectionTestClass & test
)
{
int poly0 = node->Get_Poly0();
int polycount = node->Get_Poly_Count();
if (polycount > 0) {
/*
** Simply loop through the polys in this node, checking each for collision
*/
TriClass tri;
const Vector3 * loc = Mesh->Get_Vertex_Array();
const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
const Vector4 * norms = Mesh->Get_Plane_Array();
#endif
for (int poly_counter=0; poly_counterMin.Set(100000.0f,100000.0f,100000.0f);
node->Max.Set(-100000.0f,-100000.0f,-100000.0f);
/*
** Recurse to the children first
*/
if (node->Is_Leaf() == false) {
Update_Bounding_Boxes_Recursive(&(Nodes[node->Get_Front_Child()]));
Update_Bounding_Boxes_Recursive(&(Nodes[node->Get_Back_Child()]));
/*
** Bound our children
*/
int front = node->Get_Front_Child();
int back = node->Get_Back_Child();
if (Nodes[front].Min.X < node->Min.X) node->Min.X = Nodes[front].Min.X;
if (Nodes[front].Max.X > node->Max.X) node->Max.X = Nodes[front].Max.X;
if (Nodes[front].Min.Y < node->Min.Y) node->Min.Y = Nodes[front].Min.Y;
if (Nodes[front].Max.Y > node->Max.Y) node->Max.Y = Nodes[front].Max.Y;
if (Nodes[front].Min.Z < node->Min.Z) node->Min.Z = Nodes[front].Min.Z;
if (Nodes[front].Max.Z > node->Max.Z) node->Max.Z = Nodes[front].Max.Z;
if (Nodes[back].Min.X < node->Min.X) node->Min.X = Nodes[back].Min.X;
if (Nodes[back].Max.X > node->Max.X) node->Max.X = Nodes[back].Max.X;
if (Nodes[back].Min.Y < node->Min.Y) node->Min.Y = Nodes[back].Min.Y;
if (Nodes[back].Max.Y > node->Max.Y) node->Max.Y = Nodes[back].Max.Y;
if (Nodes[back].Min.Z < node->Min.Z) node->Min.Z = Nodes[back].Min.Z;
if (Nodes[back].Max.Z > node->Max.Z) node->Max.Z = Nodes[back].Max.Z;
} else {
/*
** Bound our polygons
*/
int poly0 = node->Get_Poly0();
int polycount = node->Get_Poly_Count();
for (int poly_index = 0; poly_index < polycount; poly_index++) {
int pi = PolyIndices[poly0 + poly_index];
Update_Min_Max(pi,node->Min,node->Max );
}
}
WWASSERT(node->Min.X != 100000.0f);
WWASSERT(node->Min.Y != 100000.0f);
WWASSERT(node->Min.Z != 100000.0f);
WWASSERT(node->Max.X != -100000.0f);
WWASSERT(node->Max.Y != -100000.0f);
WWASSERT(node->Max.Z != -100000.0f);
}
/***********************************************************************************************
* AABTreeClass::Update_Min_Max -- updates min and max given a polygon index *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 6/22/99 GTH : Created. *
*=============================================================================================*/
void AABTreeClass::Update_Min_Max(int poly_index,Vector3 & min,Vector3 & max)
{
for (int vert_index = 0; vert_index < 3; vert_index++) {
const TriIndex * polyverts = Mesh->Get_Polygon_Array() + poly_index;
const Vector3 * point = Mesh->Get_Vertex_Array() + (*polyverts)[vert_index];
if (point->X < min.X) min.X = point->X;
if (point->Y < min.Y) min.Y = point->Y;
if (point->Z < min.Z) min.Z = point->Z;
if (point->X > max.X) max.X = point->X;
if (point->Y > max.Y) max.Y = point->Y;
if (point->Z > max.Z) max.Z = point->Z;
}
}
/***********************************************************************************************
* AABTreeClass::Load_W3D -- Load a W3D description of an AABTree *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/22/2000 gth : Created. *
*=============================================================================================*/
void AABTreeClass::Load_W3D(ChunkLoadClass & cload)
{
Reset();
W3dMeshAABTreeHeader header;
cload.Open_Chunk();
WWASSERT(cload.Cur_Chunk_ID() == W3D_CHUNK_AABTREE_HEADER);
cload.Read(&header,sizeof(header));
cload.Close_Chunk();
NodeCount = header.NodeCount;
PolyCount = header.PolyCount;
Nodes = new CullNodeStruct[NodeCount];
PolyIndices = new uint32[PolyCount];
while (cload.Open_Chunk()) {
switch (cload.Cur_Chunk_ID())
{
case W3D_CHUNK_AABTREE_POLYINDICES:
Read_Poly_Indices(cload);
break;
case W3D_CHUNK_AABTREE_NODES:
Read_Nodes(cload);
break;
}
cload.Close_Chunk();
}
}
/***********************************************************************************************
* AABTreeClass::Read_Poly_Indices -- load the polygon index array *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/22/2000 gth : Created. *
*=============================================================================================*/
void AABTreeClass::Read_Poly_Indices(ChunkLoadClass & cload)
{
cload.Read(PolyIndices,sizeof(uint32) * PolyCount);
}
/***********************************************************************************************
* AABTreeClass::Read_Nodes -- Load the node array *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 5/22/2000 gth : Created. *
*=============================================================================================*/
void AABTreeClass::Read_Nodes(ChunkLoadClass & cload)
{
W3dMeshAABTreeNode w3dnode;
for (int i=0; i