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/WWMath/gridcull.h

707 lines
37 KiB
C
Raw Permalink Normal View History

Initial commit of Command & Conquer Renegade source code.
2025-02-27 16:39:46 +00:00
/*
** 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 : WWMath *
* *
* $Archive:: /Commando/Code/wwmath/gridcull.h $*
* *
* Author:: Greg Hjelstrom *
* *
* $Modtime:: 5/10/01 10:42a $*
* *
* $Revision:: 14 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* GridCullSystemClass::clamp_indices_to_grid -- constrains indices to be a valid location *
* GridCullSystemClass::map_point_to_cell -- determines which cell the point is in *
* GridCullSystemClass::map_point_to_address -- determines the address of a point in the gri *
* GridCullSystemClass::map_indices_to_address -- computes the address for given index tripl *
* GridCullSystemClass::total_cell_count -- returns the total number of cells in the grid *
* GridCullSystemClass::compute_box -- computes the bounding box for a grid cell *
* GridCullSystemClass::compute_box -- computes bounding box for a range of grid cells *
* GridCullSystemClass::init_volume -- inits volume to contain the given range *
* GridCullSystemClass::init_volume -- inits volume to contain the given line segment *
* GridCullSystemClass::init_volume -- inits volume to contain the given box *
* GridCullSystemClass::init_volume -- inits volume to contain the given oriented box *
* GridCullSystemClass::init_volume -- inits volume to contain the given frustum *
* GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
* GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
* GridCullSystemClass::VolumeStruct::Is_Leaf -- check if volume is a leaf *
* GridCullSystemClass::VolumeStruct::Is_Empty -- check if volume is empty (or invalid) *
* GridCullSystemClass::VolumeStruct::Split -- split this volume *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#if defined(_MSC_VER)
#pragma once
#endif
#include "cullsys.h"
#include "mempool.h"
#include "frustum.h"
#include "aabox.h"
#include "lineseg.h"
#include "obbox.h"
#include <string.h>
class ChunkLoadClass;
class ChunkSaveClass;
/*
** GridCullSystemClass
** This is a culling system designed for dynamic objects (objects which are moving or
** changing bounding box size). It features O(1) insertion as opposed to
** the AABTree, QuadTree, or Octree insertion times which are O(logn). It's disadvantages
** compared to the above mentioned systems are that it must uniformly divide space. The
** AABTree conforms to the geometry placed in it and can therefore cull things more
** efficiently. In actual use, this system is like an AAB-tree which is uniformly subdivided,
** its just that we can jump straight to the leaves of the tree for insertion...
**
** The bounding volume for each grid cell is considered to be the volume of the cell, expanded
** by the maximum object size. Inserting an object into the grid is a matter of determining
** which cell its center point is in. Objects which are larger than the maximum size are
** allowed but they are simply put into a linked list which is iterated with each call to
** the culling system (linearly culled rather than logarithmic...)
*/
class GridCullSystemClass : public CullSystemClass
{
public:
GridCullSystemClass(void);
~GridCullSystemClass(void);
virtual void Collect_Objects(const Vector3 & point);
virtual void Collect_Objects(const AABoxClass & box);
virtual void Collect_Objects(const OBBoxClass & box);
virtual void Collect_Objects(const FrustumClass & frustum);
virtual void Re_Partition(const Vector3 & min,const Vector3 & max,float objdim);
virtual void Update_Culling(CullableClass * obj);
virtual void Load(ChunkLoadClass & cload);
virtual void Save(ChunkSaveClass & csave);
virtual int Get_Object_Count (void) const { return ObjCount; }
/*
** Statistics
*/
struct StatsStruct
{
int NodeCount;
int NodesAccepted;
int NodesTriviallyAccepted;
int NodesRejected;
};
void Reset_Statistics(void);
const StatsStruct & Get_Statistics(void);
void Get_Min_Cell_Size (Vector3 &size) const { size = MinCellSize; }
void Set_Min_Cell_Size (const Vector3 &size) { MinCellSize = size; }
int Get_Termination_Count (void) const { return TerminationCellCount; }
void Set_Termination_Count (int count) { TerminationCellCount = count; }
protected:
void Collect_And_Unlink_All(void);
void Add_Object_Internal(CullableClass * obj);
void Remove_Object_Internal(CullableClass * obj);
enum
{
TERMINATION_CELL_COUNT = 16384, // algorithm terminates if we ever have more than this many cells.
UNGRIDDED_ADDRESS = 0xFFFFFFFF // address given to objs that didn't fit in grid
};
// Constants which control the division of space:
Vector3 MinCellSize; // min dimensions for a cell (don't go below this...)
float MaxObjExtent; // max extent/radius (objects bigger than this are just put in a list)
int TerminationCellCount;
// Constants that define the division of space
Vector3 Origin;
Vector3 CellDim;
Vector3 OOCellDim;
int CellCount[3];
// 3D array of pointers to objects in each cell
CullableClass ** Cells;
// list of objs that were outside or too big for the grid.
CullableClass * NoGridList;
// number of objects in the system
int ObjCount;
// statistics
StatsStruct Stats;
// Structure used to define a volume in the grid. The volume spans from the cell indexed
// by Min[0],Min[1],Min[2] to the cell indexed by Max[0]-1,Max[1]-1,Max[2]-1.
struct VolumeStruct
{
VolumeStruct(void);
VolumeStruct(int i0,int j0,int k0,int i1,int j1,int k1);
bool Is_Leaf(void) const;
bool Is_Empty(void) const;
void Split(VolumeStruct & v0,VolumeStruct & v1) const;
int Min[3];
int Max[3];
};
void link_object(CullableClass * obj);
void link_object(CullableClass * obj,int address);
void unlink_object(CullableClass * obj);
void link_object_to_list(CullableClass ** head,CullableClass * obj);
void unlink_object_from_list(CullableClass ** head,CullableClass * obj);
bool map_point_to_cell(const Vector3 & pt,int & set_i,int & set_j,int & set_k);
bool map_point_to_address(const Vector3 & pt,int & set_address);
WWINLINE int map_indices_to_address(int i,int j,int k);
void clamp_indices_to_grid(int * i,int * j,int * k);
int total_cell_count(void);
void compute_box(int i,int j,int k,AABoxClass * set_box);
void compute_box(const VolumeStruct & area, AABoxClass * set_box);
void init_volume(const Vector3 & bound_min,const Vector3 & bound_max,VolumeStruct * set_volume);
void init_volume(const Vector3 & point,VolumeStruct * set_volume);
void init_volume(const LineSegClass & line,VolumeStruct * set_volume);
void init_volume(const AABoxClass & box,VolumeStruct * set_volume);
void init_volume(const OBBoxClass & box,VolumeStruct * set_volume);
void init_volume(const FrustumClass & frustum,VolumeStruct * set_volume);
void collect_objects_in_leaf(const Vector3 & point,CullableClass * head);
void collect_objects_in_leaf(const AABoxClass & aabox,CullableClass * head);
void collect_objects_in_leaf(const OBBoxClass & obbox,CullableClass * head);
void collect_objects_in_leaf(const FrustumClass & frustum,CullableClass * head);
};
/*
** Macros for gathering statistics. Placed here in the header file so that
** derived classes can use them as well.
*/
#ifdef WWDEBUG
#define GRIDCULL_NODE_ACCEPTED Stats.NodesAccepted ++;
#define GRIDCULL_NODE_TRIVIALLY_ACCEPTED Stats.NodesTriviallyAccepted ++;
#define GRIDCULL_NODE_REJECTED Stats.NodesRejected ++;
#else
#define GRIDCULL_NODE_ACCEPTED
#define GRIDCULL_NODE_TRIVIALLY_ACCEPTED
#define GRIDCULL_NODE_REJECTED
#endif
/*
** TypedGridCullSystemClass
** This class simply enforces that a certain type of object is inserted into the grid cull system.
** It exposes the add, remove, and collection iterating functions and is intended to be the class
** actually used by the end user.
*/
template <class T> class TypedGridCullSystemClass : public GridCullSystemClass
{
public:
virtual void Add_Object(T * obj) { Add_Object_Internal(obj); }
virtual void Remove_Object(T * obj) { Remove_Object_Internal(obj); }
T * Get_First_Collected_Object(void) { return (T*)Get_First_Collected_Object_Internal(); }
T * Get_Next_Collected_Object(T * obj) { return (T*)Get_Next_Collected_Object_Internal(obj); }
};
/*
** GridLinkClass
** This structure is used to link cullable objects into a Grid culling system
** This class is should only be used by classes which derive from GridCullSystemClass
** not normal users.
*/
class GridLinkClass : public CullLinkClass, public AutoPoolClass<GridLinkClass,256>
{
public:
GridLinkClass(GridCullSystemClass * system);
virtual ~GridLinkClass(void);
int GridAddress; // address in the grid.
CullableClass * Prev; // prev object in this cell
CullableClass * Next; // next object in this cell
};
/*
** GridListIterator
** This is just a simple iterator that contains the code for traversing the
** list of objects either in a cell in the grid or in the NoGridList...
** This class should only be used by classes which derive from GridCullSystemClass
** not normal users.
*/
class GridListIterator
{
public:
GridListIterator(CullableClass * head) { First(head); }
void First(CullableClass * head) { Head = head; CurObj = head; }
void First(void) { CurObj = Head; }
void Next(void) { if (CurObj) { CurObj = ((GridLinkClass *)CurObj->Get_Cull_Link())->Next; } }
void Prev(void) { if (CurObj) { CurObj = ((GridLinkClass *)CurObj->Get_Cull_Link())->Prev; } }
bool Is_Done(void) { return (CurObj == NULL); }
CullableClass * Get_Obj(void) { if (CurObj) { CurObj->Add_Ref(); } return CurObj; }
CullableClass * Peek_Obj(void) { return CurObj; }
private:
CullableClass * Head; // head of the list we're working in
CullableClass * CurObj; // node we're currently at.
};
/***********************************************************************************************
* GridCullSystemClass::clamp_indices_to_grid -- constrains indices to be a valid location *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::clamp_indices_to_grid(int * i,int * j,int * k)
{
if (*i < 0) *i = 0;
if (*i >= CellCount[0]) *i = CellCount[0] - 1;
if (*j < 0) *j = 0;
if (*j >= CellCount[1]) *j = CellCount[1] - 1;
if (*k < 0) *k = 0;
if (*k >= CellCount[2]) *k = CellCount[2] - 1;
}
/***********************************************************************************************
* GridCullSystemClass::map_point_to_cell -- determines which cell the point is in *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE bool GridCullSystemClass::map_point_to_cell(const Vector3 & pt,int & set_i,int & set_j,int & set_k)
{
Vector3 dp = pt - Origin;
set_i = floor(dp.X * OOCellDim.X);
set_j = floor(dp.Y * OOCellDim.Y);
set_k = floor(dp.Z * OOCellDim.Z);
if ( (set_i >= 0) && (set_j >= 0) && (set_k >= 0) &&
(set_i < CellCount[0]) && (set_j < CellCount[1]) && (set_k < CellCount[2]) )
{
return true;
}
return false;
}
/***********************************************************************************************
* GridCullSystemClass::map_point_to_address -- determines the address of a point in the grid *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE bool GridCullSystemClass::map_point_to_address(const Vector3 & pt,int &set_address)
{
int i,j,k;
bool res = map_point_to_cell(pt,i,j,k);
if (res) {
set_address = map_indices_to_address(i,j,k);
return true;
} else {
set_address = UNGRIDDED_ADDRESS;
return false;
}
}
/***********************************************************************************************
* GridCullSystemClass::map_indices_to_address -- computes the address for given index triplet *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE int GridCullSystemClass::map_indices_to_address(int i,int j,int k)
{
return i + j*CellCount[0] + k*CellCount[0]*CellCount[1];
}
/***********************************************************************************************
* GridCullSystemClass::total_cell_count -- returns the total number of cells in the grid *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE int GridCullSystemClass::total_cell_count(void)
{
return CellCount[0] * CellCount[1] * CellCount[2];
}
/***********************************************************************************************
* GridCullSystemClass::compute_box -- computes the bounding box for a grid cell *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::compute_box(int i,int j,int k,AABoxClass * set_box)
{
WWASSERT(set_box != NULL);
WWASSERT((i >= 0) && (j >= 0) && (k >= 0));
WWASSERT((i < CellCount[0]) && (j < CellCount[1]) && (k < CellCount[2]));
Vector3 min,max;
min.X = Origin.X + i * CellDim.X - MaxObjExtent;
min.Y = Origin.Y + j * CellDim.Y - MaxObjExtent;
min.Z = Origin.Z + k * CellDim.Z - MaxObjExtent;
max.X = min.X + CellDim.X + 2.0f*MaxObjExtent;
max.Y = min.Y + CellDim.Y + 2.0f*MaxObjExtent;
max.Z = min.Z + CellDim.Z + 2.0f*MaxObjExtent;
set_box->Init((min+max)*0.5f, (min-max)*0.5f);
}
/***********************************************************************************************
* GridCullSystemClass::compute_box -- computes bounding box for a range of grid cells *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::compute_box(const GridCullSystemClass::VolumeStruct & vol, AABoxClass * set_box)
{
WWASSERT(set_box != NULL);
WWASSERT((vol.Min[0] >= 0) && (vol.Min[1] >= 0) && (vol.Min[2] >= 0));
WWASSERT((vol.Max[0] <= CellCount[0]) && (vol.Max[1] <= CellCount[1]) && (vol.Max[2] <= CellCount[2]));
Vector3 min,max;
min.X = Origin.X + vol.Min[0] * CellDim.X - MaxObjExtent;
min.Y = Origin.Y + vol.Min[1] * CellDim.Y - MaxObjExtent;
min.Z = Origin.Z + vol.Min[2] * CellDim.Z - MaxObjExtent;
max.X = Origin.X + vol.Max[0] * CellDim.X + MaxObjExtent;
max.Y = Origin.Y + vol.Max[1] * CellDim.Y + MaxObjExtent;
max.Z = Origin.Z + vol.Max[2] * CellDim.Z + MaxObjExtent;
Vector3 center((max.X+min.X)*0.5f,(max.Y+min.Y)*0.5f,(max.Z+min.Z)*0.5f);
Vector3 extent((max.X-min.X)*0.5f,(max.Y-min.Y)*0.5f,(max.Z-min.Z)*0.5f);
set_box->Init(center,extent);
}
/***********************************************************************************************
* GridCullSystemClass::init_volume -- inits volume to contain the given range *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::init_volume
(
const Vector3 & bound_min,
const Vector3 & bound_max,
VolumeStruct * set_vol
)
{
// expand the box by the maximum size of any object
Vector3 grid_min = bound_min;
grid_min.X -= MaxObjExtent;
grid_min.Y -= MaxObjExtent;
grid_min.Z -= MaxObjExtent;
Vector3 grid_max = bound_max;
grid_max.X += MaxObjExtent;
grid_max.Y += MaxObjExtent;
grid_max.Z += MaxObjExtent;
// now compute the grid coordinates of the corners of the box
GridCullSystemClass::map_point_to_cell(grid_min,set_vol->Min[0],set_vol->Min[1],set_vol->Min[2]);
GridCullSystemClass::map_point_to_cell(grid_max,set_vol->Max[0],set_vol->Max[1],set_vol->Max[2]);
// now clamp the volume to the actual grid
clamp_indices_to_grid(&(set_vol->Min[0]),&(set_vol->Min[1]),&(set_vol->Min[2]));
clamp_indices_to_grid(&(set_vol->Max[0]),&(set_vol->Max[1]),&(set_vol->Max[2]));
// increment the outer edge of the box due to the way we traverse the grid...
set_vol->Max[0] ++;
set_vol->Max[1] ++;
set_vol->Max[2] ++;
}
/***********************************************************************************************
* GridCullSystemClass::init_volume -- inits volume to contain the given line segment *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::init_volume(const LineSegClass & line,VolumeStruct * set_volume)
{
Vector3 min_pt,max_pt;
min_pt.X = WWMath::Min(line.Get_P0().X,line.Get_P1().X);
max_pt.X = WWMath::Max(line.Get_P0().X,line.Get_P1().X);
min_pt.Y = WWMath::Min(line.Get_P0().Y,line.Get_P1().Y);
max_pt.Y = WWMath::Max(line.Get_P0().Y,line.Get_P1().Y);
min_pt.Z = WWMath::Min(line.Get_P0().Z,line.Get_P1().Z);
max_pt.Z = WWMath::Max(line.Get_P0().Z,line.Get_P1().Z);
init_volume(min_pt,max_pt,set_volume);
}
/***********************************************************************************************
* GridCullSystemClass::init_volume -- inits volume to contain the given box *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::init_volume(const AABoxClass & box,VolumeStruct * set_volume)
{
init_volume(box.Center - box.Extent,box.Center + box.Extent,set_volume);
}
/***********************************************************************************************
* GridCullSystemClass::init_volume -- inits volume to contain the given oriented box *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::init_volume(const OBBoxClass & box,VolumeStruct * set_volume)
{
Vector3 aaextent;
box.Compute_Axis_Aligned_Extent(&aaextent);
init_volume(box.Center - aaextent,box.Center + aaextent,set_volume);
}
/***********************************************************************************************
* GridCullSystemClass::init_volume -- inits volume to contain the given frustum *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::init_volume(const FrustumClass & frustum,VolumeStruct * set_volume)
{
init_volume(frustum.Get_Bound_Min(),frustum.Get_Bound_Max(),set_volume);
}
/***********************************************************************************************
* GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
*=============================================================================================*/
WWINLINE GridCullSystemClass::VolumeStruct::VolumeStruct(void)
{
}
/***********************************************************************************************
* GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE GridCullSystemClass::VolumeStruct::VolumeStruct(int i0,int j0,int k0,int i1,int j1,int k1)
{
Min[0] = i0;
Min[1] = j0;
Min[2] = k0;
Max[0] = i1;
Max[1] = j1;
Max[2] = k1;
WWASSERT(Max[0] > Min[0]);
WWASSERT(Max[1] > Min[1]);
WWASSERT(Max[2] > Min[2]);
}
/***********************************************************************************************
* GridCullSystemClass::VolumeStruct::Is_Leaf -- check if volume is a leaf *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE bool GridCullSystemClass::VolumeStruct::Is_Leaf(void) const
{
return ((Max[0]-Min[0] == 1) && (Max[1]-Min[1] == 1) && (Max[2]-Min[2] == 1));
}
/***********************************************************************************************
* GridCullSystemClass::VolumeStruct::Is_Empty -- check if volume is empty (or invalid) *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE bool GridCullSystemClass::VolumeStruct::Is_Empty(void) const
{
return ((Max[0]-Min[0] <= 0) || (Max[1]-Min[1] <= 0) || (Max[2]-Min[2] <= 0));
}
/***********************************************************************************************
* GridCullSystemClass::VolumeStruct::Split -- split this volume *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 3/30/2000 gth : Created. *
*=============================================================================================*/
WWINLINE void GridCullSystemClass::VolumeStruct::Split(VolumeStruct & v0,VolumeStruct & v1) const
{
// find the longest dimension
int split_axis = 0;
int delta[3];
delta[0] = Max[0] - Min[0];
delta[1] = Max[1] - Min[1];
delta[2] = Max[2] - Min[2];
if (delta[1] > delta[split_axis]) split_axis = 1;
if (delta[2] > delta[split_axis]) split_axis = 2;
WWASSERT(delta[split_axis] > 0);
// split the volume perpendicularly to that dimension
memcpy(&v0,this,sizeof(VolumeStruct));
memcpy(&v1,this,sizeof(VolumeStruct));
v0.Max[split_axis] = v1.Min[split_axis] = Min[split_axis] + (delta[split_axis] >> 1);
}
Reference in a new issue Copy permalink