Richard Boegli's CnC_Generals_Zero_Hour Fork WIP
This is documentation of Richard Boegil's Zero Hour Fork
 
Loading...
Searching...
No Matches
gridcull.h
Go to the documentation of this file.
1/*
2** Command & Conquer Generals Zero Hour(tm)
3** Copyright 2025 Electronic Arts Inc.
4**
5** This program is free software: you can redistribute it and/or modify
6** it under the terms of the GNU General Public License as published by
7** the Free Software Foundation, either version 3 of the License, or
8** (at your option) any later version.
9**
10** This program is distributed in the hope that it will be useful,
11** but WITHOUT ANY WARRANTY; without even the implied warranty of
12** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13** GNU General Public License for more details.
14**
15** You should have received a copy of the GNU General Public License
16** along with this program. If not, see <http://www.gnu.org/licenses/>.
17*/
18
19/***********************************************************************************************
20 *** 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 ***
21 ***********************************************************************************************
22 * *
23 * Project Name : WWMath *
24 * *
25 * $Archive:: /Commando/Code/wwmath/gridcull.h $*
26 * *
27 * Author:: Greg Hjelstrom *
28 * *
29 * $Modtime:: 5/10/01 10:42a $*
30 * *
31 * $Revision:: 14 $*
32 * *
33 *---------------------------------------------------------------------------------------------*
34 * Functions: *
35 * GridCullSystemClass::clamp_indices_to_grid -- constrains indices to be a valid location *
36 * GridCullSystemClass::map_point_to_cell -- determines which cell the point is in *
37 * GridCullSystemClass::map_point_to_address -- determines the address of a point in the gri *
38 * GridCullSystemClass::map_indices_to_address -- computes the address for given index tripl *
39 * GridCullSystemClass::total_cell_count -- returns the total number of cells in the grid *
40 * GridCullSystemClass::compute_box -- computes the bounding box for a grid cell *
41 * GridCullSystemClass::compute_box -- computes bounding box for a range of grid cells *
42 * GridCullSystemClass::init_volume -- inits volume to contain the given range *
43 * GridCullSystemClass::init_volume -- inits volume to contain the given line segment *
44 * GridCullSystemClass::init_volume -- inits volume to contain the given box *
45 * GridCullSystemClass::init_volume -- inits volume to contain the given oriented box *
46 * GridCullSystemClass::init_volume -- inits volume to contain the given frustum *
47 * GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
48 * GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
49 * GridCullSystemClass::VolumeStruct::Is_Leaf -- check if volume is a leaf *
50 * GridCullSystemClass::VolumeStruct::Is_Empty -- check if volume is empty (or invalid) *
51 * GridCullSystemClass::VolumeStruct::Split -- split this volume *
52 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
53
54#if defined(_MSC_VER)
55#pragma once
56#endif
57
58#include "cullsys.h"
59#include "mempool.h"
60#include "frustum.h"
61#include "aabox.h"
62#include "lineseg.h"
63#include "obbox.h"
64#include <string.h>
65
66class ChunkLoadClass;
67class ChunkSaveClass;
68
69/*
70** GridCullSystemClass
71** This is a culling system designed for dynamic objects (objects which are moving or
72** changing bounding box size). It features O(1) insertion as opposed to
73** the AABTree, QuadTree, or Octree insertion times which are O(logn). It's disadvantages
74** compared to the above mentioned systems are that it must uniformly divide space. The
75** AABTree conforms to the geometry placed in it and can therefore cull things more
76** efficiently. In actual use, this system is like an AAB-tree which is uniformly subdivided,
77** its just that we can jump straight to the leaves of the tree for insertion...
78**
79** The bounding volume for each grid cell is considered to be the volume of the cell, expanded
80** by the maximum object size. Inserting an object into the grid is a matter of determining
81** which cell its center point is in. Objects which are larger than the maximum size are
82** allowed but they are simply put into a linked list which is iterated with each call to
83** the culling system (linearly culled rather than logarithmic...)
84*/
85class GridCullSystemClass : public CullSystemClass
86{
87
88public:
89
90 GridCullSystemClass(void);
91 ~GridCullSystemClass(void);
92
93 virtual void Collect_Objects(const Vector3 & point);
94 virtual void Collect_Objects(const AABoxClass & box);
95 virtual void Collect_Objects(const OBBoxClass & box);
96 virtual void Collect_Objects(const FrustumClass & frustum);
97
98 virtual void Re_Partition(const Vector3 & min,const Vector3 & max,float objdim);
99 virtual void Update_Culling(CullableClass * obj);
100
101 virtual void Load(ChunkLoadClass & cload);
102 virtual void Save(ChunkSaveClass & csave);
103
104 virtual int Get_Object_Count (void) const { return ObjCount; }
105
106 /*
107 ** Statistics
108 */
116
117 void Reset_Statistics(void);
118 const StatsStruct & Get_Statistics(void);
119
120 void Get_Min_Cell_Size (Vector3 &size) const { size = MinCellSize; }
121 void Set_Min_Cell_Size (const Vector3 &size) { MinCellSize = size; }
122
123 int Get_Termination_Count (void) const { return TerminationCellCount; }
124 void Set_Termination_Count (int count) { TerminationCellCount = count; }
125
126protected:
127
128 void Collect_And_Unlink_All(void);
129 void Add_Object_Internal(CullableClass * obj);
130 void Remove_Object_Internal(CullableClass * obj);
131
132 enum
133 {
134 TERMINATION_CELL_COUNT = 16384, // algorithm terminates if we ever have more than this many cells.
135 UNGRIDDED_ADDRESS = 0xFFFFFFFF // address given to objs that didn't fit in grid
136 };
137
138 // Constants which control the division of space:
139 Vector3 MinCellSize; // min dimensions for a cell (don't go below this...)
140 float MaxObjExtent; // max extent/radius (objects bigger than this are just put in a list)
141 int TerminationCellCount;
142
143 // Constants that define the division of space
144 Vector3 Origin;
145 Vector3 CellDim;
146 Vector3 OOCellDim;
147 int CellCount[3];
148
149 // 3D array of pointers to objects in each cell
150 CullableClass ** Cells;
151
152 // list of objs that were outside or too big for the grid.
153 CullableClass * NoGridList;
154
155 // number of objects in the system
156 int ObjCount;
157
158 // statistics
159 StatsStruct Stats;
160
161 // Structure used to define a volume in the grid. The volume spans from the cell indexed
162 // by Min[0],Min[1],Min[2] to the cell indexed by Max[0]-1,Max[1]-1,Max[2]-1.
163 struct VolumeStruct
164 {
165 VolumeStruct(void);
166 VolumeStruct(int i0,int j0,int k0,int i1,int j1,int k1);
167 bool Is_Leaf(void) const;
168 bool Is_Empty(void) const;
169 void Split(VolumeStruct & v0,VolumeStruct & v1) const;
170
171 int Min[3];
172 int Max[3];
173 };
174
175 void link_object(CullableClass * obj);
176 void link_object(CullableClass * obj,int address);
177 void unlink_object(CullableClass * obj);
178 void link_object_to_list(CullableClass ** head,CullableClass * obj);
179 void unlink_object_from_list(CullableClass ** head,CullableClass * obj);
180
181 bool map_point_to_cell(const Vector3 & pt,int & set_i,int & set_j,int & set_k);
182 bool map_point_to_address(const Vector3 & pt,int & set_address);
183 WWINLINE int map_indices_to_address(int i,int j,int k);
184 void clamp_indices_to_grid(int * i,int * j,int * k);
185
186 int total_cell_count(void);
187 void compute_box(int i,int j,int k,AABoxClass * set_box);
188 void compute_box(const VolumeStruct & area, AABoxClass * set_box);
189
190 void init_volume(const Vector3 & bound_min,const Vector3 & bound_max,VolumeStruct * set_volume);
191 void init_volume(const Vector3 & point,VolumeStruct * set_volume);
192 void init_volume(const LineSegClass & line,VolumeStruct * set_volume);
193 void init_volume(const AABoxClass & box,VolumeStruct * set_volume);
194 void init_volume(const OBBoxClass & box,VolumeStruct * set_volume);
195 void init_volume(const FrustumClass & frustum,VolumeStruct * set_volume);
196
197 void collect_objects_in_leaf(const Vector3 & point,CullableClass * head);
198 void collect_objects_in_leaf(const AABoxClass & aabox,CullableClass * head);
199 void collect_objects_in_leaf(const OBBoxClass & obbox,CullableClass * head);
200 void collect_objects_in_leaf(const FrustumClass & frustum,CullableClass * head);
201};
202
203/*
204** Macros for gathering statistics. Placed here in the header file so that
205** derived classes can use them as well.
206*/
207#ifdef WWDEBUG
208
209#define GRIDCULL_NODE_ACCEPTED Stats.NodesAccepted ++;
210#define GRIDCULL_NODE_TRIVIALLY_ACCEPTED Stats.NodesTriviallyAccepted ++;
211#define GRIDCULL_NODE_REJECTED Stats.NodesRejected ++;
212
213#else
214
215#define GRIDCULL_NODE_ACCEPTED
216#define GRIDCULL_NODE_TRIVIALLY_ACCEPTED
217#define GRIDCULL_NODE_REJECTED
218
219#endif
220
221
222/*
223** TypedGridCullSystemClass
224** This class simply enforces that a certain type of object is inserted into the grid cull system.
225** It exposes the add, remove, and collection iterating functions and is intended to be the class
226** actually used by the end user.
227*/
228template <class T> class TypedGridCullSystemClass : public GridCullSystemClass
229{
230public:
231
232 virtual void Add_Object(T * obj) { Add_Object_Internal(obj); }
233 virtual void Remove_Object(T * obj) { Remove_Object_Internal(obj); }
234
235 T * Get_First_Collected_Object(void) { return (T*)Get_First_Collected_Object_Internal(); }
236 T * Get_Next_Collected_Object(T * obj) { return (T*)Get_Next_Collected_Object_Internal(obj); }
237
238};
239
240
241/*
242** GridLinkClass
243** This structure is used to link cullable objects into a Grid culling system
244** This class is should only be used by classes which derive from GridCullSystemClass
245** not normal users.
246*/
247class GridLinkClass : public CullLinkClass, public AutoPoolClass<GridLinkClass,256>
248{
249public:
250 GridLinkClass(GridCullSystemClass * system);
251 virtual ~GridLinkClass(void);
252
253 int GridAddress; // address in the grid.
254 CullableClass * Prev; // prev object in this cell
255 CullableClass * Next; // next object in this cell
256};
257
258
259/*
260** GridListIterator
261** This is just a simple iterator that contains the code for traversing the
262** list of objects either in a cell in the grid or in the NoGridList...
263** This class should only be used by classes which derive from GridCullSystemClass
264** not normal users.
265*/
266class GridListIterator
267{
268public:
269
270 GridListIterator(CullableClass * head) { First(head); }
271
272 void First(CullableClass * head) { Head = head; CurObj = head; }
273 void First(void) { CurObj = Head; }
274 void Next(void) { if (CurObj) { CurObj = ((GridLinkClass *)CurObj->Get_Cull_Link())->Next; } }
275 void Prev(void) { if (CurObj) { CurObj = ((GridLinkClass *)CurObj->Get_Cull_Link())->Prev; } }
276 bool Is_Done(void) { return (CurObj == NULL); }
277
278 CullableClass * Get_Obj(void) { if (CurObj) { CurObj->Add_Ref(); } return CurObj; }
279 CullableClass * Peek_Obj(void) { return CurObj; }
280
281private:
282
283 CullableClass * Head; // head of the list we're working in
284 CullableClass * CurObj; // node we're currently at.
285
286};
287
288
289
290/***********************************************************************************************
291 * GridCullSystemClass::clamp_indices_to_grid -- constrains indices to be a valid location *
292 * *
293 * INPUT: *
294 * *
295 * OUTPUT: *
296 * *
297 * WARNINGS: *
298 * *
299 * HISTORY: *
300 * 3/30/2000 gth : Created. *
301 *=============================================================================================*/
302WWINLINE void GridCullSystemClass::clamp_indices_to_grid(int * i,int * j,int * k)
303{
304 if (*i < 0) *i = 0;
305 if (*i >= CellCount[0]) *i = CellCount[0] - 1;
306 if (*j < 0) *j = 0;
307 if (*j >= CellCount[1]) *j = CellCount[1] - 1;
308 if (*k < 0) *k = 0;
309 if (*k >= CellCount[2]) *k = CellCount[2] - 1;
310}
311
312
313/***********************************************************************************************
314 * GridCullSystemClass::map_point_to_cell -- determines which cell the point is in *
315 * *
316 * INPUT: *
317 * *
318 * OUTPUT: *
319 * *
320 * WARNINGS: *
321 * *
322 * HISTORY: *
323 * 3/30/2000 gth : Created. *
324 *=============================================================================================*/
325WWINLINE bool GridCullSystemClass::map_point_to_cell(const Vector3 & pt,int & set_i,int & set_j,int & set_k)
326{
327 Vector3 dp = pt - Origin;
328 set_i = floor(dp.X * OOCellDim.X);
329 set_j = floor(dp.Y * OOCellDim.Y);
330 set_k = floor(dp.Z * OOCellDim.Z);
331
332 if ( (set_i >= 0) && (set_j >= 0) && (set_k >= 0) &&
333 (set_i < CellCount[0]) && (set_j < CellCount[1]) && (set_k < CellCount[2]) )
334 {
335 return true;
336 }
337 return false;
338}
339
340
341/***********************************************************************************************
342 * GridCullSystemClass::map_point_to_address -- determines the address of a point in the grid *
343 * *
344 * INPUT: *
345 * *
346 * OUTPUT: *
347 * *
348 * WARNINGS: *
349 * *
350 * HISTORY: *
351 * 3/30/2000 gth : Created. *
352 *=============================================================================================*/
353WWINLINE bool GridCullSystemClass::map_point_to_address(const Vector3 & pt,int &set_address)
354{
355 int i,j,k;
356 bool res = map_point_to_cell(pt,i,j,k);
357
358 if (res) {
359 set_address = map_indices_to_address(i,j,k);
360 return true;
361 } else {
362 set_address = UNGRIDDED_ADDRESS;
363 return false;
364 }
365}
366
367
368/***********************************************************************************************
369 * GridCullSystemClass::map_indices_to_address -- computes the address for given index triplet *
370 * *
371 * INPUT: *
372 * *
373 * OUTPUT: *
374 * *
375 * WARNINGS: *
376 * *
377 * HISTORY: *
378 * 3/30/2000 gth : Created. *
379 *=============================================================================================*/
380WWINLINE int GridCullSystemClass::map_indices_to_address(int i,int j,int k)
381{
382 return i + j*CellCount[0] + k*CellCount[0]*CellCount[1];
383}
384
385
386/***********************************************************************************************
387 * GridCullSystemClass::total_cell_count -- returns the total number of cells in the grid *
388 * *
389 * INPUT: *
390 * *
391 * OUTPUT: *
392 * *
393 * WARNINGS: *
394 * *
395 * HISTORY: *
396 * 3/30/2000 gth : Created. *
397 *=============================================================================================*/
402
403
404/***********************************************************************************************
405 * GridCullSystemClass::compute_box -- computes the bounding box for a grid cell *
406 * *
407 * INPUT: *
408 * *
409 * OUTPUT: *
410 * *
411 * WARNINGS: *
412 * *
413 * HISTORY: *
414 * 3/30/2000 gth : Created. *
415 *=============================================================================================*/
416WWINLINE void GridCullSystemClass::compute_box(int i,int j,int k,AABoxClass * set_box)
417{
418 WWASSERT(set_box != NULL);
419 WWASSERT((i >= 0) && (j >= 0) && (k >= 0));
420 WWASSERT((i < CellCount[0]) && (j < CellCount[1]) && (k < CellCount[2]));
421
422 Vector3 min,max;
423
424 min.X = Origin.X + i * CellDim.X - MaxObjExtent;
425 min.Y = Origin.Y + j * CellDim.Y - MaxObjExtent;
426 min.Z = Origin.Z + k * CellDim.Z - MaxObjExtent;
427
428 max.X = min.X + CellDim.X + 2.0f*MaxObjExtent;
429 max.Y = min.Y + CellDim.Y + 2.0f*MaxObjExtent;
430 max.Z = min.Z + CellDim.Z + 2.0f*MaxObjExtent;
431
432 set_box->Init((min+max)*0.5f, (min-max)*0.5f);
433}
434
435
436/***********************************************************************************************
437 * GridCullSystemClass::compute_box -- computes bounding box for a range of grid cells *
438 * *
439 * INPUT: *
440 * *
441 * OUTPUT: *
442 * *
443 * WARNINGS: *
444 * *
445 * HISTORY: *
446 * 3/30/2000 gth : Created. *
447 *=============================================================================================*/
448WWINLINE void GridCullSystemClass::compute_box(const GridCullSystemClass::VolumeStruct & vol, AABoxClass * set_box)
449{
450 WWASSERT(set_box != NULL);
451 WWASSERT((vol.Min[0] >= 0) && (vol.Min[1] >= 0) && (vol.Min[2] >= 0));
452 WWASSERT((vol.Max[0] <= CellCount[0]) && (vol.Max[1] <= CellCount[1]) && (vol.Max[2] <= CellCount[2]));
453
454 Vector3 min,max;
455
456 min.X = Origin.X + vol.Min[0] * CellDim.X - MaxObjExtent;
457 min.Y = Origin.Y + vol.Min[1] * CellDim.Y - MaxObjExtent;
458 min.Z = Origin.Z + vol.Min[2] * CellDim.Z - MaxObjExtent;
459
460 max.X = Origin.X + vol.Max[0] * CellDim.X + MaxObjExtent;
461 max.Y = Origin.Y + vol.Max[1] * CellDim.Y + MaxObjExtent;
462 max.Z = Origin.Z + vol.Max[2] * CellDim.Z + MaxObjExtent;
463
464 Vector3 center((max.X+min.X)*0.5f,(max.Y+min.Y)*0.5f,(max.Z+min.Z)*0.5f);
465 Vector3 extent((max.X-min.X)*0.5f,(max.Y-min.Y)*0.5f,(max.Z-min.Z)*0.5f);
466 set_box->Init(center,extent);
467}
468
469
470/***********************************************************************************************
471 * GridCullSystemClass::init_volume -- inits volume to contain the given range *
472 * *
473 * INPUT: *
474 * *
475 * OUTPUT: *
476 * *
477 * WARNINGS: *
478 * *
479 * HISTORY: *
480 * 3/30/2000 gth : Created. *
481 *=============================================================================================*/
482WWINLINE void GridCullSystemClass::init_volume
483(
484 const Vector3 & bound_min,
485 const Vector3 & bound_max,
486 VolumeStruct * set_vol
487)
488{
489 // expand the box by the maximum size of any object
490 Vector3 grid_min = bound_min;
491 grid_min.X -= MaxObjExtent;
492 grid_min.Y -= MaxObjExtent;
493 grid_min.Z -= MaxObjExtent;
494
495 Vector3 grid_max = bound_max;
496 grid_max.X += MaxObjExtent;
497 grid_max.Y += MaxObjExtent;
498 grid_max.Z += MaxObjExtent;
499
500 // now compute the grid coordinates of the corners of the box
501 GridCullSystemClass::map_point_to_cell(grid_min,set_vol->Min[0],set_vol->Min[1],set_vol->Min[2]);
502 GridCullSystemClass::map_point_to_cell(grid_max,set_vol->Max[0],set_vol->Max[1],set_vol->Max[2]);
503
504 // now clamp the volume to the actual grid
505 clamp_indices_to_grid(&(set_vol->Min[0]),&(set_vol->Min[1]),&(set_vol->Min[2]));
506 clamp_indices_to_grid(&(set_vol->Max[0]),&(set_vol->Max[1]),&(set_vol->Max[2]));
507
508 // increment the outer edge of the box due to the way we traverse the grid...
509 set_vol->Max[0] ++;
510 set_vol->Max[1] ++;
511 set_vol->Max[2] ++;
512}
513
514
515/***********************************************************************************************
516 * GridCullSystemClass::init_volume -- inits volume to contain the given line segment *
517 * *
518 * INPUT: *
519 * *
520 * OUTPUT: *
521 * *
522 * WARNINGS: *
523 * *
524 * HISTORY: *
525 * 3/30/2000 gth : Created. *
526 *=============================================================================================*/
527WWINLINE void GridCullSystemClass::init_volume(const LineSegClass & line,VolumeStruct * set_volume)
528{
529 Vector3 min_pt,max_pt;
530 min_pt.X = WWMath::Min(line.Get_P0().X,line.Get_P1().X);
531 max_pt.X = WWMath::Max(line.Get_P0().X,line.Get_P1().X);
532 min_pt.Y = WWMath::Min(line.Get_P0().Y,line.Get_P1().Y);
533 max_pt.Y = WWMath::Max(line.Get_P0().Y,line.Get_P1().Y);
534 min_pt.Z = WWMath::Min(line.Get_P0().Z,line.Get_P1().Z);
535 max_pt.Z = WWMath::Max(line.Get_P0().Z,line.Get_P1().Z);
536 init_volume(min_pt,max_pt,set_volume);
537}
538
539
540/***********************************************************************************************
541 * GridCullSystemClass::init_volume -- inits volume to contain the given box *
542 * *
543 * INPUT: *
544 * *
545 * OUTPUT: *
546 * *
547 * WARNINGS: *
548 * *
549 * HISTORY: *
550 * 3/30/2000 gth : Created. *
551 *=============================================================================================*/
552WWINLINE void GridCullSystemClass::init_volume(const AABoxClass & box,VolumeStruct * set_volume)
553{
554 init_volume(box.Center - box.Extent,box.Center + box.Extent,set_volume);
555}
556
557
558/***********************************************************************************************
559 * GridCullSystemClass::init_volume -- inits volume to contain the given oriented box *
560 * *
561 * INPUT: *
562 * *
563 * OUTPUT: *
564 * *
565 * WARNINGS: *
566 * *
567 * HISTORY: *
568 * 3/30/2000 gth : Created. *
569 *=============================================================================================*/
570WWINLINE void GridCullSystemClass::init_volume(const OBBoxClass & box,VolumeStruct * set_volume)
571{
572 Vector3 aaextent;
573 box.Compute_Axis_Aligned_Extent(&aaextent);
574 init_volume(box.Center - aaextent,box.Center + aaextent,set_volume);
575}
576
577
578/***********************************************************************************************
579 * GridCullSystemClass::init_volume -- inits volume to contain the given frustum *
580 * *
581 * INPUT: *
582 * *
583 * OUTPUT: *
584 * *
585 * WARNINGS: *
586 * *
587 * HISTORY: *
588 * 3/30/2000 gth : Created. *
589 *=============================================================================================*/
590WWINLINE void GridCullSystemClass::init_volume(const FrustumClass & frustum,VolumeStruct * set_volume)
591{
592 init_volume(frustum.Get_Bound_Min(),frustum.Get_Bound_Max(),set_volume);
593}
594
595
596/***********************************************************************************************
597 * GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
598 * *
599 * INPUT: *
600 * *
601 * OUTPUT: *
602 * *
603 * WARNINGS: *
604 * *
605 * HISTORY: *
606 *=============================================================================================*/
610
611
612/***********************************************************************************************
613 * GridCullSystemClass::VolumeStruct::VolumeStruct -- constructor *
614 * *
615 * INPUT: *
616 * *
617 * OUTPUT: *
618 * *
619 * WARNINGS: *
620 * *
621 * HISTORY: *
622 * 3/30/2000 gth : Created. *
623 *=============================================================================================*/
624WWINLINE GridCullSystemClass::VolumeStruct::VolumeStruct(int i0,int j0,int k0,int i1,int j1,int k1)
625{
626 Min[0] = i0;
627 Min[1] = j0;
628 Min[2] = k0;
629 Max[0] = i1;
630 Max[1] = j1;
631 Max[2] = k1;
632 WWASSERT(Max[0] > Min[0]);
633 WWASSERT(Max[1] > Min[1]);
634 WWASSERT(Max[2] > Min[2]);
635}
636
637
638/***********************************************************************************************
639 * GridCullSystemClass::VolumeStruct::Is_Leaf -- check if volume is a leaf *
640 * *
641 * INPUT: *
642 * *
643 * OUTPUT: *
644 * *
645 * WARNINGS: *
646 * *
647 * HISTORY: *
648 * 3/30/2000 gth : Created. *
649 *=============================================================================================*/
650WWINLINE bool GridCullSystemClass::VolumeStruct::Is_Leaf(void) const
651{
652 return ((Max[0]-Min[0] == 1) && (Max[1]-Min[1] == 1) && (Max[2]-Min[2] == 1));
653}
654
655
656/***********************************************************************************************
657 * GridCullSystemClass::VolumeStruct::Is_Empty -- check if volume is empty (or invalid) *
658 * *
659 * INPUT: *
660 * *
661 * OUTPUT: *
662 * *
663 * WARNINGS: *
664 * *
665 * HISTORY: *
666 * 3/30/2000 gth : Created. *
667 *=============================================================================================*/
668WWINLINE bool GridCullSystemClass::VolumeStruct::Is_Empty(void) const
669{
670 return ((Max[0]-Min[0] <= 0) || (Max[1]-Min[1] <= 0) || (Max[2]-Min[2] <= 0));
671}
672
673
674/***********************************************************************************************
675 * GridCullSystemClass::VolumeStruct::Split -- split this volume *
676 * *
677 * INPUT: *
678 * *
679 * OUTPUT: *
680 * *
681 * WARNINGS: *
682 * *
683 * HISTORY: *
684 * 3/30/2000 gth : Created. *
685 *=============================================================================================*/
686WWINLINE void GridCullSystemClass::VolumeStruct::Split(VolumeStruct & v0,VolumeStruct & v1) const
687{
688 // find the longest dimension
689 int split_axis = 0;
690 int delta[3];
691
692 delta[0] = Max[0] - Min[0];
693 delta[1] = Max[1] - Min[1];
694 delta[2] = Max[2] - Min[2];
695
696 if (delta[1] > delta[split_axis]) split_axis = 1;
697 if (delta[2] > delta[split_axis]) split_axis = 2;
698
699 WWASSERT(delta[split_axis] > 0);
700
701 // split the volume perpendicularly to that dimension
702 memcpy(&v0,this,sizeof(VolumeStruct));
703 memcpy(&v1,this,sizeof(VolumeStruct));
704
705 v0.Max[split_axis] = v1.Min[split_axis] = Min[split_axis] + (delta[split_axis] >> 1);
706}
NULL
#define NULL
Definition BaseType.h:92
min
#define min(x, y)
Definition BaseType.h:101
max
#define max(x, y)
Definition BaseType.h:105
WWASSERT
#define WWASSERT
Definition aabtreebuilder.cpp:68
WWINLINE
#define WWINLINE
Definition always.h:172
AABoxClass::Init
WWINLINE void Init(const Vector3 &center, const Vector3 &extent)
Definition aabox.h:101
AABoxClass::Center
Vector3 Center
Definition aabox.h:123
AABoxClass::Extent
Vector3 Extent
Definition aabox.h:124
CullSystemClass::Get_Next_Collected_Object_Internal
CullableClass * Get_Next_Collected_Object_Internal(CullableClass *obj)
Definition cullsys.cpp:119
CullSystemClass::Get_First_Collected_Object_Internal
CullableClass * Get_First_Collected_Object_Internal(void)
Definition cullsys.cpp:114
CullSystemClass::CullableClass
friend class CullableClass
Definition cullsys.h:197
CullSystemClass::CullSystemClass
CullSystemClass(void)
Definition cullsys.cpp:103
FrustumClass::Get_Bound_Min
const Vector3 & Get_Bound_Min(void) const
Definition frustum.h:58
FrustumClass::Get_Bound_Max
const Vector3 & Get_Bound_Max(void) const
Definition frustum.h:59
GridCullSystemClass::unlink_object_from_list
void unlink_object_from_list(CullableClass **head, CullableClass *obj)
Definition gridcull.cpp:921
GridCullSystemClass::compute_box
void compute_box(int i, int j, int k, AABoxClass *set_box)
Definition gridcull.h:416
GridCullSystemClass::Reset_Statistics
void Reset_Statistics(void)
Definition gridcull.cpp:717
GridCullSystemClass::Cells
CullableClass ** Cells
Definition gridcull.h:150
GridCullSystemClass::link_object_to_list
void link_object_to_list(CullableClass **head, CullableClass *obj)
Definition gridcull.cpp:887
GridCullSystemClass::link_object
void link_object(CullableClass *obj)
Definition gridcull.cpp:811
GridCullSystemClass::Stats
StatsStruct Stats
Definition gridcull.h:159
GridCullSystemClass::map_point_to_address
bool map_point_to_address(const Vector3 &pt, int &set_address)
Definition gridcull.h:353
GridCullSystemClass::Add_Object_Internal
void Add_Object_Internal(CullableClass *obj)
Definition gridcull.cpp:757
GridCullSystemClass::NoGridList
CullableClass * NoGridList
Definition gridcull.h:153
GridCullSystemClass::Collect_And_Unlink_All
void Collect_And_Unlink_All(void)
Definition gridcull.cpp:507
GridCullSystemClass::collect_objects_in_leaf
void collect_objects_in_leaf(const Vector3 &point, CullableClass *head)
Definition gridcull.cpp:974
GridCullSystemClass::clamp_indices_to_grid
void clamp_indices_to_grid(int *i, int *j, int *k)
Definition gridcull.h:302
GridCullSystemClass::Set_Termination_Count
void Set_Termination_Count(int count)
Definition gridcull.h:124
GridCullSystemClass::Save
virtual void Save(ChunkSaveClass &csave)
Definition gridcull.cpp:670
GridCullSystemClass::Remove_Object_Internal
void Remove_Object_Internal(CullableClass *obj)
Definition gridcull.cpp:783
GridCullSystemClass::Get_Statistics
const StatsStruct & Get_Statistics(void)
Definition gridcull.cpp:739
GridCullSystemClass::total_cell_count
int total_cell_count(void)
Definition gridcull.h:398
GridCullSystemClass::init_volume
void init_volume(const Vector3 &bound_min, const Vector3 &bound_max, VolumeStruct *set_volume)
Definition gridcull.h:483
GridCullSystemClass::unlink_object
void unlink_object(CullableClass *obj)
Definition gridcull.cpp:861
GridCullSystemClass::Load
virtual void Load(ChunkLoadClass &cload)
Definition gridcull.cpp:590
GridCullSystemClass::init_volume
void init_volume(const Vector3 &point, VolumeStruct *set_volume)
GridCullSystemClass::Collect_Objects
virtual void Collect_Objects(const Vector3 &point)
Definition gridcull.cpp:200
GridCullSystemClass::map_indices_to_address
WWINLINE int map_indices_to_address(int i, int j, int k)
Definition gridcull.h:380
GridCullSystemClass::Re_Partition
virtual void Re_Partition(const Vector3 &min, const Vector3 &max, float objdim)
Definition gridcull.cpp:393
GridCullSystemClass::Set_Min_Cell_Size
void Set_Min_Cell_Size(const Vector3 &size)
Definition gridcull.h:121
GridCullSystemClass::Get_Min_Cell_Size
void Get_Min_Cell_Size(Vector3 &size) const
Definition gridcull.h:120
GridCullSystemClass::Get_Termination_Count
int Get_Termination_Count(void) const
Definition gridcull.h:123
GridCullSystemClass::Update_Culling
virtual void Update_Culling(CullableClass *obj)
Definition gridcull.cpp:562
GridCullSystemClass::Get_Object_Count
virtual int Get_Object_Count(void) const
Definition gridcull.h:104
GridCullSystemClass::map_point_to_cell
bool map_point_to_cell(const Vector3 &pt, int &set_i, int &set_j, int &set_k)
Definition gridcull.h:325
GridListIterator::First
void First(void)
Definition gridcull.h:273
GridListIterator::GridListIterator
GridListIterator(CullableClass *head)
Definition gridcull.h:270
GridListIterator::Get_Obj
CullableClass * Get_Obj(void)
Definition gridcull.h:278
GridListIterator::Next
void Next(void)
Definition gridcull.h:274
GridListIterator::Prev
void Prev(void)
Definition gridcull.h:275
GridListIterator::Is_Done
bool Is_Done(void)
Definition gridcull.h:276
GridListIterator::First
void First(CullableClass *head)
Definition gridcull.h:272
GridListIterator::Peek_Obj
CullableClass * Peek_Obj(void)
Definition gridcull.h:279
LineSegClass::Get_P1
const Vector3 & Get_P1() const
Definition lineseg.h:71
LineSegClass::Get_P0
const Vector3 & Get_P0() const
Definition lineseg.h:70
OBBoxClass::Compute_Axis_Aligned_Extent
void Compute_Axis_Aligned_Extent(Vector3 *set_extent) const
Definition obbox.h:217
OBBoxClass::Center
Vector3 Center
Definition obbox.h:113
TypedGridCullSystemClass::Add_Object
virtual void Add_Object(T *obj)
Definition gridcull.h:232
TypedGridCullSystemClass::Get_Next_Collected_Object
T * Get_Next_Collected_Object(T *obj)
Definition gridcull.h:236
TypedGridCullSystemClass::Remove_Object
virtual void Remove_Object(T *obj)
Definition gridcull.h:233
TypedGridCullSystemClass::Get_First_Collected_Object
T * Get_First_Collected_Object(void)
Definition gridcull.h:235
Vector3::X
float X
Definition vector3.h:90
Vector3::Z
float Z
Definition vector3.h:92
Vector3::Y
float Y
Definition vector3.h:91
WWMath::Max
static float Max(float a, float b)
Definition wwmath.h:264
WWMath::Min
static float Min(float a, float b)
Definition wwmath.h:258
GridCullSystemClass::VolumeStruct::Split
void Split(VolumeStruct &v0, VolumeStruct &v1) const
Definition gridcull.h:686