Richard Boegli's CnC_Generals_Zero_Hour Fork WIP
This is documentation of Richard Boegil's Zero Hour Fork
 
Loading...
Searching...
No Matches
gridcull.cpp
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.cpp $*
26 * *
27 * Author:: Greg Hjelstrom *
28 * *
29 * $Modtime:: 4/27/00 7:00p $*
30 * *
31 * $Revision:: 18 $*
32 * *
33 *---------------------------------------------------------------------------------------------*
34 * Functions: *
35 * GridCullSystemClass::GridCullSystemClass -- Constructor *
36 * GridCullSystemClass::~GridCullSystemClass -- Destructor *
37 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given point *
38 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given AABox *
39 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given OBBox *
40 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given Frustum *
41 * GridCullSystemClass::Re_Partition -- re-compute grid parameters for the given volume *
42 * GridCullSystemClass::Collect_And_Unlink_All -- collects all objects and removes them from *
43 * GridCullSystemClass::Update_Culling -- updates an objects position in the grid *
44 * GridCullSystemClass::Load -- load function *
45 * GridCullSystemClass::Save -- Save function *
46 * GridCullSystemClass::Reset_Statistics -- reset debugging stats *
47 * GridCullSystemClass::Get_Statistics -- returns reference to the statistics structure *
48 * GridCullSystemClass::Add_Object_Internal -- links an object into the system *
49 * GridCullSystemClass::Remove_Object_Internal -- unlinks an object from the system *
50 * GridCullSystemClass::link_object -- figures out which cell the object is in and links it *
51 * GridCullSystemClass::unlink_object -- unlinks the object from the cell it is in *
52 * GridCullSystemClass::link_object_to_list -- grid list link function *
53 * GridCullSystemClass::unlink_object_from_list -- grid list unlink function *
54 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
55
56
57#include "gridcull.h"
58#include "chunkio.h"
59#include "iostruct.h"
60#include "colmath.h"
61#include "colmathinlines.h"
62
63
64
65/*
66** Declare the pool for GridLinks
67*/
68DEFINE_AUTO_POOL(GridLinkClass,256);
69
70
71/*
72** Current version of the file format
73*/
74const uint32 GRID_CURRENT_VERSION = 0x00010000;
75
76
77/*
78** Chunk Id's used by the aabtree code to save itself into a file
79*/
80enum
81{
82 GRID_CHUNK_VERSION = 0x00000001, // version wrapper, contains 32bit version #
83 GRID_CHUNK_PARAMETERS = 0x00000100, // parameters for the grid cull system
84};
85
86
87/*
88** IOGridParametersStruct
89** Data structure for the contents of a node in the AAB-Tree
90*/
99
100
101/*************************************************************************
102**
103** Utility functions for walking the object list in an AABTree Node
104**
105*************************************************************************/
106static inline CullableClass * get_next_object(CullableClass * obj)
107{
108 return ((GridLinkClass *)obj->Get_Cull_Link())->Next;
109}
110
111/*************************************************************************
112**
113** GridLinkClass Implementation
114**
115*************************************************************************/
116GridLinkClass::GridLinkClass(GridCullSystemClass * system) :
117 CullLinkClass(system),
118 GridAddress(-1),
119 Prev(NULL),
120 Next(NULL)
121{
122}
123
127
128
129
130
131
132/*************************************************************************
133**
134** GridCullSystemClass Implementation
135**
136*************************************************************************/
137
138
139/***********************************************************************************************
140 * GridCullSystemClass::GridCullSystemClass -- Constructor *
141 * *
142 * INPUT: *
143 * *
144 * OUTPUT: *
145 * *
146 * WARNINGS: *
147 * *
148 * HISTORY: *
149 * 4/27/2000 gth : Created. *
150 *=============================================================================================*/
151GridCullSystemClass::GridCullSystemClass(void) :
152 MinCellSize(10,10,10),
153 MaxObjExtent(15),
154 Origin(-100,-100,-100),
155 CellDim(10,10,10),
156 Cells(NULL),
157 NoGridList(NULL),
158 ObjCount(0),
159 TerminationCellCount(TERMINATION_CELL_COUNT)
160{
161 CellCount[0] = CellCount[1] = CellCount[2] = 0;
162 Re_Partition(Vector3(-100,-100,-100),Vector3(100,100,100),15);
163 Reset_Statistics();
164}
165
166
167/***********************************************************************************************
168 * GridCullSystemClass::~GridCullSystemClass -- Destructor *
169 * *
170 * INPUT: *
171 * *
172 * OUTPUT: *
173 * *
174 * WARNINGS: *
175 * *
176 * HISTORY: *
177 * 4/27/2000 gth : Created. *
178 *=============================================================================================*/
179GridCullSystemClass::~GridCullSystemClass(void)
180{
181 if (Cells != NULL) {
182 delete Cells;
183 Cells = NULL;
184 }
185}
186
187
188/***********************************************************************************************
189 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given point *
190 * *
191 * INPUT: *
192 * *
193 * OUTPUT: *
194 * *
195 * WARNINGS: *
196 * *
197 * HISTORY: *
198 * 4/27/2000 gth : Created. *
199 *=============================================================================================*/
200void GridCullSystemClass::Collect_Objects(const Vector3 & point)
201{
202 /*
203 ** Collect the objects in the grid
204 */
205 VolumeStruct vol;
206 init_volume(point,point,&vol);
207 if (!vol.Is_Empty()) {
208
209 int delta_x = vol.Max[0] - vol.Min[0];
210 int i,j,k;
211 int address = map_indices_to_address(vol.Min[0],vol.Min[1],vol.Min[2]);
212
213 for (k=vol.Min[2]; k<vol.Max[2]; k++) {
214 for (j=vol.Min[1]; j<vol.Max[1]; j++) {
215 for (i=vol.Min[0]; i<vol.Max[0]; i++) {
216 GRIDCULL_NODE_TRIVIALLY_ACCEPTED;
217 collect_objects_in_leaf(point,Cells[address]);
218 address++;
219 }
220 address -= delta_x;
221 address += CellCount[0];
222 }
223 address = map_indices_to_address(vol.Min[0],vol.Min[1],k+1);
224 }
225 }
226
227 /*
228 ** Collect the objects in the no-grid-list
229 */
230 collect_objects_in_leaf(point,NoGridList);
231}
232
233
234/***********************************************************************************************
235 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given AABox *
236 * *
237 * INPUT: *
238 * *
239 * OUTPUT: *
240 * *
241 * WARNINGS: *
242 * *
243 * HISTORY: *
244 * 4/27/2000 gth : Created. *
245 *=============================================================================================*/
246void GridCullSystemClass::Collect_Objects(const AABoxClass & box)
247{
248 /*
249 ** Collect the objects in the grid
250 */
251 VolumeStruct vol;
252 init_volume(box,&vol);
253
254 if (!vol.Is_Empty()) {
255
256 int delta_x = vol.Max[0] - vol.Min[0];
257 int i,j,k;
258 int address = map_indices_to_address(vol.Min[0],vol.Min[1],vol.Min[2]);
259
260 for (k=vol.Min[2]; k<vol.Max[2]; k++) {
261 for (j=vol.Min[1]; j<vol.Max[1]; j++) {
262 for (i=vol.Min[0]; i<vol.Max[0]; i++) {
263 GRIDCULL_NODE_TRIVIALLY_ACCEPTED;
264 collect_objects_in_leaf(box,Cells[address]);
265 address++;
266 }
267 address -= delta_x;
268 address += CellCount[0];
269 }
270 address = map_indices_to_address(vol.Min[0],vol.Min[1],k+1);
271 }
272 }
273
274 /*
275 ** Collect the objects in the no-grid-list
276 */
277 collect_objects_in_leaf(box,NoGridList);
278}
279
280
281/***********************************************************************************************
282 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given OBBox *
283 * *
284 * INPUT: *
285 * *
286 * OUTPUT: *
287 * *
288 * WARNINGS: *
289 * *
290 * HISTORY: *
291 * 4/27/2000 gth : Created. *
292 *=============================================================================================*/
293void GridCullSystemClass::Collect_Objects(const OBBoxClass & box)
294{
295 /*
296 ** Collect the objects in the grid
297 */
298 VolumeStruct vol;
299 init_volume(box,&vol);
300
301 if (!vol.Is_Empty()) {
302
303 int delta_x = vol.Max[0] - vol.Min[0];
304 int i,j,k;
305 int address = map_indices_to_address(vol.Min[0],vol.Min[1],vol.Min[2]);
306
307 for (k=vol.Min[2]; k<vol.Max[2]; k++) {
308 for (j=vol.Min[1]; j<vol.Max[1]; j++) {
309 for (i=vol.Min[0]; i<vol.Max[0]; i++) {
310 GRIDCULL_NODE_TRIVIALLY_ACCEPTED;
311 collect_objects_in_leaf(box,Cells[address]);
312 address++;
313 }
314 address -= delta_x;
315 address += CellCount[0];
316 }
317 address = map_indices_to_address(vol.Min[0],vol.Min[1],k+1);
318 }
319 }
320
321 /*
322 ** Collect the objects in the no-grid-list
323 */
324 collect_objects_in_leaf(box,NoGridList);
325}
326
327
328/***********************************************************************************************
329 * GridCullSystemClass::Collect_Objects -- Collect all objects touching the given Frustum *
330 * *
331 * INPUT: *
332 * *
333 * OUTPUT: *
334 * *
335 * WARNINGS: *
336 * *
337 * HISTORY: *
338 * 4/27/2000 gth : Created. *
339 *=============================================================================================*/
340void GridCullSystemClass::Collect_Objects(const FrustumClass & frustum)
341{
342 /*
343 ** Collect the objects in the grid
344 */
345 VolumeStruct vol;
346 init_volume(frustum,&vol);
347
348 if (!vol.Is_Empty()) {
349
350 int delta_x = vol.Max[0] - vol.Min[0];
351 int i,j,k;
352 int address = map_indices_to_address(vol.Min[0],vol.Min[1],vol.Min[2]);
353
354 for (k=vol.Min[2]; k<vol.Max[2]; k++) {
355 for (j=vol.Min[1]; j<vol.Max[1]; j++) {
356 for (i=vol.Min[0]; i<vol.Max[0]; i++) {
357 GRIDCULL_NODE_TRIVIALLY_ACCEPTED;
358 collect_objects_in_leaf(frustum,Cells[address]);
359 address++;
360 }
361 address -= delta_x;
362 address += CellCount[0];
363 }
364 address = map_indices_to_address(vol.Min[0],vol.Min[1],k+1);
365 }
366 }
367
368 /*
369 ** Collect the objects in the no-grid-list
370 */
371 collect_objects_in_leaf(frustum,NoGridList);
372}
373
374
375/***********************************************************************************************
376 * GridCullSystemClass::Re_Partition -- re-compute grid parameters for the given volume *
377 * *
378 * *
379 * *
380 * *
381 * INPUT: *
382 * input_min - 'min' corner of the world *
383 * input_max - 'max' corner of the world *
384 * objdim - largest object dimesion that will be allowed in the grid *
385 * *
386 * OUTPUT: *
387 * *
388 * WARNINGS: *
389 * *
390 * HISTORY: *
391 * 4/27/2000 gth : Created. *
392 *=============================================================================================*/
393void GridCullSystemClass::Re_Partition(const Vector3 & input_min,const Vector3 & input_max,float objdim)
394{
395 /*
396 ** grab all objects into the collection list and unlink them from the grid
397 */
398 Reset_Collection();
399 Collect_And_Unlink_All();
400
401 /*
402 ** Do a sanity check on the input parameters
403 */
404 Vector3 min = input_min;
405 Vector3 max = input_max;
406
407 if (max.X - min.X < 1.0f) {
408 max.X += MinCellSize.X;
409 min.X -= MinCellSize.X;
410 }
411 if (max.Y - min.Y < 1.0f) {
412 max.Y += MinCellSize.Y;
413 min.Y -= MinCellSize.Y;
414 }
415 if (max.Z - min.Z < 1.0f) {
416 max.Z += MinCellSize.Z;
417 min.Z -= MinCellSize.Z;
418 }
419
420 /*
421 ** Compute the grid parameters
422 */
423 Origin = min;
424 Vector3 world_dim = max - min;
425 MaxObjExtent = objdim;
426
427 WWASSERT(world_dim.X > 0.0f);
428 WWASSERT(world_dim.Y > 0.0f);
429 WWASSERT(world_dim.Z > 0.0f);
430
431 /*
432 ** how many cells should we use on each dimension?
433 */
434 CellCount[0] = CellCount[1] = CellCount[2] = 1;
435 CellDim = world_dim;
436 bool done = false;
437
438 while (!done) {
439
440 /*
441 ** find biggest dimension
442 */
443 int bigdim = 0;
444 if (CellDim[1]/MinCellSize[1] > CellDim[bigdim]/MinCellSize[bigdim]) bigdim = 1;
445 if (CellDim[2]/MinCellSize[2] > CellDim[bigdim]/MinCellSize[bigdim]) bigdim = 2;
446
447 /*
448 ** split dimension in two if possible
449 */
450 if (CellDim[bigdim] >= 2.0f * MinCellSize[bigdim]) {
451 CellDim[bigdim] /= 2.0f;
452 CellCount[bigdim] *= 2;
453 }
454
455 /*
456 ** check termination conditions
457 */
458 if (total_cell_count() >= TerminationCellCount) {
459 done = true;
460 }
461
462 if ( (CellDim[0] < 2.0*MinCellSize[0]) &&
463 (CellDim[1] < 2.0*MinCellSize[1]) &&
464 (CellDim[2] < 2.0*MinCellSize[2]) ) {
465 done = true;
466 }
467 }
468
469 OOCellDim.X = 1.0f / CellDim.X;
470 OOCellDim.Y = 1.0f / CellDim.Y;
471 OOCellDim.Z = 1.0f / CellDim.Z;
472
473 if (Cells != NULL) {
474 delete[] Cells;
475 }
476 Cells = W3DNEWARRAY CullableClass * [total_cell_count()];
477 memset(&(Cells[0]),0,total_cell_count() * sizeof(CullableClass *));
478
479 /*
480 ** iterate the collection list and re-insert all objects into the grid
481 */
482 CullableClass * obj;
483 for ( obj = Get_First_Collected_Object_Internal();
484 obj != NULL;
485 obj = Get_Next_Collected_Object_Internal(obj))
486 {
487 link_object(obj);
488 }
489}
490
491
492/***********************************************************************************************
493 * GridCullSystemClass::Collect_And_Unlink_All -- collects all objects and removes them from t *
494 * *
495 * This is used when re-partitioning the grid. All objects are pulled out and linked into *
496 * the collection list. When the grid has been re-initialized, the objects are put back in. *
497 * *
498 * INPUT: *
499 * *
500 * OUTPUT: *
501 * *
502 * WARNINGS: *
503 * *
504 * HISTORY: *
505 * 4/27/2000 gth : Created. *
506 *=============================================================================================*/
507void GridCullSystemClass::Collect_And_Unlink_All(void)
508{
509 Reset_Collection();
510
511 /*
512 ** pull all objects out of the grid
513 */
514 for (int k=0; k<CellCount[2]; k++) {
515 for (int j=0; j<CellCount[1]; j++) {
516 for (int i=0; i<CellCount[0]; i++) {
517
518 /*
519 ** collect and unlink all objects in cell(i,j,k)
520 */
521 CullableClass * obj = Cells[map_indices_to_address(i,j,k)];
522 while (obj) {
523 CullableClass * nextobj = get_next_object(obj);
524
525 unlink_object(obj);
526 Add_To_Collection(obj);
527
528 obj = nextobj;
529 }
530
531 }
532 }
533 }
534
535 /*
536 ** pull all objects out of the "no-grid" list
537 */
538 CullableClass * obj = NoGridList;
539 while (obj) {
540 CullableClass * nextobj = get_next_object(obj);
541
542 unlink_object(obj);
543 Add_To_Collection(obj);
544
545 obj = nextobj;
546 }
547}
548
549
550/***********************************************************************************************
551 * GridCullSystemClass::Update_Culling -- updates an objects position in the grid *
552 * *
553 * INPUT: *
554 * *
555 * OUTPUT: *
556 * *
557 * WARNINGS: *
558 * *
559 * HISTORY: *
560 * 4/27/2000 gth : Created. *
561 *=============================================================================================*/
562void GridCullSystemClass::Update_Culling(CullableClass * obj)
563{
564 WWASSERT(obj);
565 WWASSERT(obj->Get_Culling_System() == this);
566
567 int address;
568 GridLinkClass * link = (GridLinkClass *)obj->Get_Cull_Link();
569 map_point_to_address(obj->Get_Cull_Box().Center,address);
570
571 if (address != link->GridAddress) {
572 unlink_object(obj);
573 link_object(obj,address);
574 }
575}
576
577
578/***********************************************************************************************
579 * GridCullSystemClass::Load -- load function *
580 * *
581 * INPUT: *
582 * *
583 * OUTPUT: *
584 * *
585 * WARNINGS: *
586 * *
587 * HISTORY: *
588 * 4/27/2000 gth : Created. *
589 *=============================================================================================*/
590void GridCullSystemClass::Load(ChunkLoadClass & cload)
591{
592 /*
593 ** read the version chunk
594 */
595 uint32 version;
596 cload.Open_Chunk();
597 WWASSERT(cload.Cur_Chunk_ID() == GRID_CHUNK_VERSION);
598 cload.Read(&version,sizeof(version));
599 cload.Close_Chunk();
600
601 /*
602 ** read the parameters chunk
603 */
604 IOGridParametersStruct params;
605 memset(&params,0,sizeof(params));
606 cload.Open_Chunk();
607 WWASSERT(cload.Cur_Chunk_ID() == GRID_CHUNK_PARAMETERS);
608 cload.Read(&params,sizeof(params));
609 cload.Close_Chunk();
610
611 /*
612 ** unlink all objects
613 */
614 Collect_And_Unlink_All();
615
616 /*
617 ** partition the grid according to the loaded parameters
618 */
619 CellCount[0] = params.CellCount[0];
620 CellCount[1] = params.CellCount[1];
621 CellCount[2] = params.CellCount[2];
622 CellDim.X = params.CellDim.X;
623 CellDim.Y = params.CellDim.Y;
624 CellDim.Z = params.CellDim.Z;
625 MaxObjExtent = params.MaxObjExtent;
626 MinCellSize.X = params.MinCellSize.X;
627 MinCellSize.Y = params.MinCellSize.Y;
628 MinCellSize.Z = params.MinCellSize.Z;
629 Origin.X = params.Origin.X;
630 Origin.Y = params.Origin.Y;
631 Origin.Z = params.Origin.Z;
632
633 OOCellDim.X = 1.0f / CellDim.X;
634 OOCellDim.Y = 1.0f / CellDim.Y;
635 OOCellDim.Z = 1.0f / CellDim.Z;
636
637 if (Cells != NULL) {
638 delete [] Cells;
639 Cells = NULL;
640 }
641
642 Cells = W3DNEWARRAY CullableClass * [total_cell_count()];
643 memset(&(Cells[0]),0,total_cell_count() * sizeof(CullableClass *));
644
645 /*
646 ** re-link the objects in
647 */
648 CullableClass * obj;
649 for ( obj = Get_First_Collected_Object_Internal();
650 obj != NULL;
651 obj = Get_Next_Collected_Object_Internal(obj))
652 {
653 link_object(obj);
654 }
655}
656
657
658/***********************************************************************************************
659 * GridCullSystemClass::Save -- Save function *
660 * *
661 * INPUT: *
662 * *
663 * OUTPUT: *
664 * *
665 * WARNINGS: *
666 * *
667 * HISTORY: *
668 * 4/27/2000 gth : Created. *
669 *=============================================================================================*/
670void GridCullSystemClass::Save(ChunkSaveClass & csave)
671{
672 /*
673 ** write the version chunk
674 */
675 uint32 version = GRID_CURRENT_VERSION;
676 csave.Begin_Chunk(GRID_CHUNK_VERSION);
677 csave.Write(&version,sizeof(version));
678 csave.End_Chunk();
679
680 /*
681 ** write the grid parameters
682 */
683 IOGridParametersStruct params;
684 memset(&params,0,sizeof(params));
685 params.CellCount[0] = CellCount[0];
686 params.CellCount[1] = CellCount[1];
687 params.CellCount[2] = CellCount[2];
688 params.CellDim.X = CellDim.X;
689 params.CellDim.Y = CellDim.Y;
690 params.CellDim.Z = CellDim.Z;
691 params.MaxObjExtent = MaxObjExtent;
692 params.MinCellSize.X = MinCellSize.X;
693 params.MinCellSize.Y = MinCellSize.Y;
694 params.MinCellSize.Z = MinCellSize.Z;
695 params.Origin.X = Origin.X;
696 params.Origin.Y = Origin.Y;
697 params.Origin.Z = Origin.Z;
698
699 csave.Begin_Chunk(GRID_CHUNK_PARAMETERS);
700 csave.Write(&params,sizeof(params));
701 csave.End_Chunk();
702}
703
704
705/***********************************************************************************************
706 * GridCullSystemClass::Reset_Statistics -- reset debugging stats *
707 * *
708 * INPUT: *
709 * *
710 * OUTPUT: *
711 * *
712 * WARNINGS: *
713 * *
714 * HISTORY: *
715 * 4/27/2000 gth : Created. *
716 *=============================================================================================*/
717void GridCullSystemClass::Reset_Statistics(void)
718{
719 // number of (virtual) nodes = 2n-1
720 Stats.NodeCount = 2 * (CellCount[0] * CellCount[1] * CellCount[2]) - 1;
721 Stats.NodesAccepted = 0;
722 Stats.NodesTriviallyAccepted = 0;
723 Stats.NodesRejected = 0;
724}
725
726
727/***********************************************************************************************
728 * GridCullSystemClass::Get_Statistics -- returns reference to the statistics structure *
729 * *
730 * INPUT: *
731 * *
732 * OUTPUT: *
733 * *
734 * WARNINGS: *
735 * *
736 * HISTORY: *
737 * 4/27/2000 gth : Created. *
738 *=============================================================================================*/
743
744
745/***********************************************************************************************
746 * GridCullSystemClass::Add_Object_Internal -- links an object into the system *
747 * *
748 * INPUT: *
749 * *
750 * OUTPUT: *
751 * *
752 * WARNINGS: *
753 * *
754 * HISTORY: *
755 * 4/27/2000 gth : Created. *
756 *=============================================================================================*/
757void GridCullSystemClass::Add_Object_Internal(CullableClass * obj)
758{
759 WWASSERT(obj);
760 WWASSERT(obj->Get_Culling_System() == NULL);
761
762 GridLinkClass * link = new GridLinkClass(this);
763 obj->Set_Cull_Link(link);
764 link_object(obj);
765
766 ObjCount++;
767 obj->Add_Ref();
768}
769
770
771/***********************************************************************************************
772 * GridCullSystemClass::Remove_Object_Internal -- unlinks an object from the system *
773 * *
774 * INPUT: *
775 * *
776 * OUTPUT: *
777 * *
778 * WARNINGS: *
779 * *
780 * HISTORY: *
781 * 4/27/2000 gth : Created. *
782 *=============================================================================================*/
783void GridCullSystemClass::Remove_Object_Internal(CullableClass * obj)
784{
785 WWASSERT(obj);
786 WWASSERT(obj->Get_Culling_System() == this);
787 GridLinkClass * link = (GridLinkClass *)obj->Get_Cull_Link();
788
789 unlink_object(obj);
790 link->Set_Culling_System(NULL);
791 delete link;
792 obj->Set_Cull_Link(NULL);
793
794 ObjCount--;
795 obj->Release_Ref();
796}
797
798
799/***********************************************************************************************
800 * GridCullSystemClass::link_object -- figures out which cell the object is in and links it *
801 * *
802 * INPUT: *
803 * *
804 * OUTPUT: *
805 * *
806 * WARNINGS: *
807 * *
808 * HISTORY: *
809 * 4/27/2000 gth : Created. *
810 *=============================================================================================*/
811void GridCullSystemClass::link_object(CullableClass * obj)
812{
813 WWASSERT(obj);
814 WWASSERT(obj->Get_Culling_System() == this);
815
816 int address;
817 map_point_to_address(obj->Get_Cull_Box().Center,address);
818
819 link_object(obj,address);
820}
821
822void GridCullSystemClass::link_object(CullableClass * obj,int address)
823{
824 WWASSERT(obj);
825 WWASSERT(obj->Get_Culling_System() == this);
826 GridLinkClass * link = (GridLinkClass *)obj->Get_Cull_Link();
827 WWASSERT(link != NULL);
828
829 /*
830 ** if obj cannot be inserted into the grid, add it to the NoGridList
831 ** otherwise, insert it into the cell
832 */
833 const AABoxClass & box = obj->Get_Cull_Box();
834 if (
835 (box.Extent.X > MaxObjExtent) ||
836 (box.Extent.Y > MaxObjExtent) ||
837 (box.Extent.Z > MaxObjExtent) ||
838 (address == UNGRIDDED_ADDRESS)
839 )
840 {
841 link->GridAddress = UNGRIDDED_ADDRESS;
842 link_object_to_list(&NoGridList,obj);
843 } else {
844 link->GridAddress = address;
845 link_object_to_list(&(Cells[address]),obj);
846 }
847}
848
849/***********************************************************************************************
850 * GridCullSystemClass::unlink_object -- unlinks the object from the cell it is in *
851 * *
852 * INPUT: *
853 * *
854 * OUTPUT: *
855 * *
856 * WARNINGS: *
857 * *
858 * HISTORY: *
859 * 4/27/2000 gth : Created. *
860 *=============================================================================================*/
861void GridCullSystemClass::unlink_object(CullableClass * obj)
862{
863 WWASSERT(obj);
864 WWASSERT(obj->Get_Culling_System() == this);
865 GridLinkClass * link = (GridLinkClass *)obj->Get_Cull_Link();
866
867 if (link->GridAddress == UNGRIDDED_ADDRESS) {
868 unlink_object_from_list(&NoGridList,obj);
869 } else {
870 unlink_object_from_list(&(Cells[link->GridAddress]),obj);
871 }
872}
873
874
875/***********************************************************************************************
876 * GridCullSystemClass::link_object_to_list -- grid list link function *
877 * *
878 * INPUT: *
879 * *
880 * OUTPUT: *
881 * *
882 * WARNINGS: *
883 * *
884 * HISTORY: *
885 * 4/27/2000 gth : Created. *
886 *=============================================================================================*/
887void GridCullSystemClass::link_object_to_list(CullableClass ** head,CullableClass * obj)
888{
889 WWASSERT(obj);
890 WWASSERT(obj->Get_Culling_System() == this);
891 GridLinkClass * link = (GridLinkClass *)obj->Get_Cull_Link();
892
893 /*
894 ** Insert this object as the new head of the list.
895 */
896 link->Next = *head;
897 link->Prev = NULL;
898
899 if (link->Next != NULL) {
900 GridLinkClass * next_link = (GridLinkClass *)link->Next->Get_Cull_Link();
901 WWASSERT(next_link != NULL);
902 next_link->Prev = obj;
903 }
904
905 *head = obj;
906}
907
908
909/***********************************************************************************************
910 * GridCullSystemClass::unlink_object_from_list -- grid list unlink function *
911 * *
912 * INPUT: *
913 * *
914 * OUTPUT: *
915 * *
916 * WARNINGS: *
917 * *
918 * HISTORY: *
919 * 4/27/2000 gth : Created. *
920 *=============================================================================================*/
921void GridCullSystemClass::unlink_object_from_list(CullableClass ** head,CullableClass * obj)
922{
923 WWASSERT(obj);
924 WWASSERT(obj->Get_Culling_System() == this);
925 GridLinkClass * link = (GridLinkClass *)obj->Get_Cull_Link();
926
927 /*
928 ** check to see that the object is actually in this list
929 */
930#ifdef WWDEBUG
931 CullableClass * tmp = *head;
932 bool found = false;
933 while (tmp && !found) {
934 if (tmp == obj) found = true;
935 tmp = ((GridLinkClass *)(tmp->Get_Cull_Link()))->Next;
936 }
937 WWASSERT(found);
938#endif
939
940 /*
941 ** If we were the head of the list, make the head point to the next object
942 */
943 if (obj == *head) {
944 *head = link->Next;
945 }
946
947 /*
948 ** Link the object previous to us to our next...
949 */
950 if (link->Prev) {
951 GridLinkClass * prev_link = (GridLinkClass *)link->Prev->Get_Cull_Link();
952 prev_link->Next = link->Next;
953 }
954
955 /*
956 ** Link the objects after us to our previous...
957 */
958 if (link->Next) {
959 GridLinkClass * next_link = (GridLinkClass *)link->Next->Get_Cull_Link();
960 next_link->Prev = link->Prev;
961 }
962
963 link->Prev = NULL;
964 link->Next = NULL;
965}
966
967
968
969/*************************************************************************
970**
971** GridCullSystem Internal Leaf-iterating collection functions
972**
973*************************************************************************/
974void GridCullSystemClass::collect_objects_in_leaf(const Vector3 & point,CullableClass * head)
975{
976 if (head != NULL) {
977 GridListIterator it(head);
978 for (;!it.Is_Done(); it.Next()) {
979 CullableClass * obj = it.Peek_Obj();
980 if (obj->Get_Cull_Box ().Contains (point) == true) {
981 Add_To_Collection(obj);
982 }
983 }
984 }
985}
986
987void GridCullSystemClass::collect_objects_in_leaf(const AABoxClass & box,CullableClass * head)
988{
989 if (head != NULL) {
990 GridListIterator it(head);
991 for (;!it.Is_Done(); it.Next()) {
992 CullableClass * obj = it.Peek_Obj();
993 if (CollisionMath::Overlap_Test(box,obj->Get_Cull_Box()) != CollisionMath::OUTSIDE) {
994 Add_To_Collection(obj);
995 }
996 }
997 }
998}
999
1000void GridCullSystemClass::collect_objects_in_leaf(const OBBoxClass & obbox,CullableClass * head)
1001{
1002 if (head != NULL) {
1003 GridListIterator it(head);
1004 for (;!it.Is_Done(); it.Next()) {
1005 CullableClass * obj = it.Peek_Obj();
1006 if (CollisionMath::Overlap_Test(obbox,obj->Get_Cull_Box()) != CollisionMath::OUTSIDE) {
1007 Add_To_Collection(obj);
1008 }
1009 }
1010 }
1011}
1012
1013void GridCullSystemClass::collect_objects_in_leaf(const FrustumClass & frustum,CullableClass * head)
1014{
1015 if (head != NULL) {
1016 GridListIterator it(head);
1017 for (;!it.Is_Done(); it.Next()) {
1018 CullableClass * obj = it.Peek_Obj();
1019 if (CollisionMath::Overlap_Test(frustum,obj->Get_Cull_Box()) != CollisionMath::OUTSIDE) {
1020 Add_To_Collection(obj);
1021 }
1022 }
1023 }
1024}
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
W3DNEWARRAY
#define W3DNEWARRAY
Definition always.h:110
uint32
unsigned long uint32
Definition bittype.h:46
float32
float float32
Definition bittype.h:54
AABoxClass::Center
Vector3 Center
Definition aabox.h:123
AABoxClass::Extent
Vector3 Extent
Definition aabox.h:124
AABoxClass::Contains
WWINLINE bool Contains(const Vector3 &point) const
Definition aabox.h:504
ChunkLoadClass::Close_Chunk
bool Close_Chunk()
Definition chunkio.cpp:448
ChunkLoadClass::Cur_Chunk_ID
uint32 Cur_Chunk_ID()
Definition chunkio.cpp:484
ChunkLoadClass::Read
uint32 Read(void *buf, uint32 nbytes)
Definition chunkio.cpp:692
ChunkLoadClass::Open_Chunk
bool Open_Chunk()
Definition chunkio.cpp:412
ChunkSaveClass::Write
uint32 Write(const void *buf, uint32 nbytes)
Definition chunkio.cpp:264
ChunkSaveClass::Begin_Chunk
bool Begin_Chunk(uint32 id)
Definition chunkio.cpp:108
ChunkSaveClass::End_Chunk
bool End_Chunk()
Definition chunkio.cpp:148
CollisionMath::Overlap_Test
static OverlapType Overlap_Test(const AAPlaneClass &plane, const Vector3 &point)
Definition colmathplane.cpp:55
CullSystemClass::Get_Next_Collected_Object_Internal
CullableClass * Get_Next_Collected_Object_Internal(CullableClass *obj)
Definition cullsys.cpp:119
CullSystemClass::Reset_Collection
void Reset_Collection(void)
Definition cullsys.cpp:140
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::Add_To_Collection
void Add_To_Collection(CullableClass *obj)
Definition cullsys.cpp:145
CullableClass::Get_Cull_Link
WWINLINE CullLinkClass * Get_Cull_Link(void) const
Definition cullsys.h:104
CullableClass::Get_Cull_Box
WWINLINE const AABoxClass & Get_Cull_Box(void) const
Definition cullsys.h:94
CullableClass::Set_Cull_Link
WWINLINE void Set_Cull_Link(CullLinkClass *c)
Definition cullsys.h:103
CullableClass::Get_Culling_System
CullSystemClass * Get_Culling_System(void) const
Definition cullsys.cpp:86
GridCullSystemClass::unlink_object_from_list
void unlink_object_from_list(CullableClass **head, CullableClass *obj)
Definition gridcull.cpp:921
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::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::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::Update_Culling
virtual void Update_Culling(CullableClass *obj)
Definition gridcull.cpp:562
GridListIterator::Next
void Next(void)
Definition gridcull.h:274
GridListIterator::Is_Done
bool Is_Done(void)
Definition gridcull.h:276
GridListIterator::Peek_Obj
CullableClass * Peek_Obj(void)
Definition gridcull.h:279
RefCountClass::Release_Ref
WWINLINE void Release_Ref(void) const
Definition refcount.h:146
RefCountClass::Add_Ref
void Add_Ref(void) const
Definition refcount.cpp:171
Vector3::X
float X
Definition vector3.h:90
Vector3::Z
float Z
Definition vector3.h:92
Vector3::Y
float Y
Definition vector3.h:91
GRID_CURRENT_VERSION
const uint32 GRID_CURRENT_VERSION
Definition gridcull.cpp:74
GRID_CHUNK_VERSION
@ GRID_CHUNK_VERSION
Definition gridcull.cpp:82
GRID_CHUNK_PARAMETERS
@ GRID_CHUNK_PARAMETERS
Definition gridcull.cpp:83
GRIDCULL_NODE_TRIVIALLY_ACCEPTED
#define GRIDCULL_NODE_TRIVIALLY_ACCEPTED
Definition gridcull.h:216
DEFINE_AUTO_POOL
#define DEFINE_AUTO_POOL(T, BLOCKSIZE)
Definition mempool.h:160
IOGridParametersStruct::MinCellSize
IOVector3Struct MinCellSize
Definition gridcull.cpp:93
IOGridParametersStruct::Origin
IOVector3Struct Origin
Definition gridcull.cpp:94
IOGridParametersStruct::CellDim
IOVector3Struct CellDim
Definition gridcull.cpp:95