Richard Boegli's CnC_Generals_Zero_Hour Fork WIP
This is documentation of Richard Boegil's Zero Hour Fork
 
Loading...
Searching...
No Matches
aabtree.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 : WW3D *
24 * *
25 * $Archive:: /Commando/Code/ww3d2/aabtree.cpp $*
26 * *
27 * Author:: Greg Hjelstrom *
28 * *
29 * $Modtime:: 11/24/01 5:34p $*
30 * *
31 * $Revision:: 4 $*
32 * *
33 *---------------------------------------------------------------------------------------------*
34 * Functions: *
35 * AABTreeClass::AABTreeClass -- Constructor *
36 * AABTreeClass::AABTreeClass -- Constructor *
37 * AABTreeClass::AABTreeClass -- copy constructor *
38 * AABTreeClass::~AABTreeClass -- Destructor *
39 * AABTreeClass::operator = -- assignment operator *
40 * AABTreeClass::Reset -- reset this tree, releases all allocated resources *
41 * AABTreeClass::Build_Tree_Recursive -- Initializes this tree from the given builder *
42 * AABTreeClass::Set_Mesh -- set the mesh pointer *
43 * AABTreeClass::Generate_APT -- Generate an active poly table for the mesh *
44 * AABTreeClass::Generate_OBBox_APT_Recursive -- recursively generate the apt *
45 * AABTreeClass::Cast_Ray_Recursive -- Internal implementation of Cast_Ray *
46 * AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive -- Internal implementation *
47 * AABTreeClass::Cast_AABox_Recursive -- internal implementation of Cast_AABox *
48 * AABTreeClass::Cast_OBBox_Recursive -- Internal implementation of Cast_OBBox *
49 * AABTreeClass::Intersect_OBBox_Recursive -- internal implementation of Intersect_OBBox *
50 * AABTreeClass::Cast_Ray_To_Polys -- cast the ray to polys in the given node *
51 * AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys -- cast ray to polys in the nod*
52 * AABTreeClass::Cast_AABox_To_Polys -- cast aabox to polys in the given node *
53 * AABTreeClass::Cast_OBBox_To_Polys -- cast obbox to polys in the given node *
54 * AABTreeClass::Intersect_OBBox_With_Polys -- Test polys for intersection *
55 * AABTreeClass::Update_Bounding_Boxes_Recursive -- recompute the bounding boxes *
56 * AABTreeClass::Update_Min_Max -- updates min and max given a polygon index *
57 * AABTreeClass::Load_W3D -- Load a W3D description of an AABTree *
58 * AABTreeClass::Read_Poly_Indices -- load the polygon index array *
59 * AABTreeClass::Read_Nodes -- Load the node array *
60 * AABTreeClass::Generate_APT -- generate an apt from a box and viewdir *
61 * AABTreeClass::Generate_OBBox_APT_Recursive -- recurse, generate the apt for a box and vie *
62 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
63
64
65#include "aabtree.h"
66#include "aabtreebuilder.h"
67#include "wwdebug.h"
68#include "tri.h"
69#include "meshgeometry.h"
70#include "coltest.h"
71#include "inttest.h"
72#include "colmathinlines.h"
73#include "w3d_file.h"
74#include "chunkio.h"
75
76
77
78/***********************************************************************************************
79 * AABTreeClass::AABTreeClass -- Constructor *
80 * *
81 * INPUT: *
82 * *
83 * OUTPUT: *
84 * *
85 * WARNINGS: *
86 * *
87 * HISTORY: *
88 *=============================================================================================*/
89AABTreeClass::AABTreeClass(void) :
90 NodeCount(0),
91 Nodes(NULL),
92 PolyCount(0),
93 PolyIndices(NULL),
94 Mesh(NULL)
95{
96}
97
98/***********************************************************************************************
99 * AABTreeClass::AABTreeClass -- Constructor *
100 * *
101 * Builds an AABTree from the contents of an AABTreeBuilderClass. *
102 * *
103 * INPUT: *
104 * *
105 * OUTPUT: *
106 * *
107 * WARNINGS: *
108 * *
109 * HISTORY: *
110 * 6/19/98 GTH : Created. *
111 * 5/23/2000 gth : Created. *
112 *=============================================================================================*/
113AABTreeClass::AABTreeClass(AABTreeBuilderClass * builder)
114{
115 NodeCount = builder->Node_Count();
116 Nodes = W3DNEWARRAY AABTreeClass::CullNodeStruct[NodeCount];
117
118 PolyCount = builder->Poly_Count();
119 PolyIndices = W3DNEWARRAY uint32[PolyCount];
120
121 int curpolyindex = 0;
122 Build_Tree_Recursive(builder->Root,curpolyindex);
123}
124
125
126/***********************************************************************************************
127 * AABTreeClass::AABTreeClass -- copy constructor *
128 * *
129 * INPUT: *
130 * *
131 * OUTPUT: *
132 * *
133 * WARNINGS: *
134 * *
135 * HISTORY: *
136 * 6/22/99 GTH : Created. *
137 *=============================================================================================*/
138AABTreeClass::AABTreeClass(const AABTreeClass & that) :
139 NodeCount(0),
140 Nodes(NULL),
141 PolyCount(0),
142 PolyIndices(0),
143 Mesh(NULL)
144{
145 *this = that;
146}
147
148/***********************************************************************************************
149 * AABTreeClass::~AABTreeClass -- Destructor *
150 * *
151 * INPUT: *
152 * *
153 * OUTPUT: *
154 * *
155 * WARNINGS: *
156 * *
157 * HISTORY: *
158 * 6/19/98 GTH : Created. *
159 *=============================================================================================*/
160AABTreeClass::~AABTreeClass(void)
161{
162 Reset();
163}
164
165/***********************************************************************************************
166 * AABTreeClass::operator = -- assignment operator *
167 * *
168 * INPUT: *
169 * *
170 * OUTPUT: *
171 * *
172 * WARNINGS: *
173 * *
174 * HISTORY: *
175 * 6/22/99 GTH : Created. *
176 *=============================================================================================*/
177AABTreeClass & AABTreeClass::operator = (const AABTreeClass & that)
178{
179 Reset();
180
181 NodeCount = that.NodeCount;
182 if (NodeCount > 0) {
183 Nodes = W3DNEWARRAY CullNodeStruct[NodeCount];
184 memcpy(Nodes,that.Nodes,NodeCount * sizeof(CullNodeStruct));
185 }
186
187 PolyCount = that.PolyCount;
188 if (PolyCount > 0) {
189 PolyIndices = W3DNEWARRAY uint32[PolyCount];
190 memcpy(PolyIndices,that.PolyIndices,PolyCount * sizeof(uint32));
191 }
192
193 Mesh = that.Mesh;
194
195 return *this;
196}
197
198
199/***********************************************************************************************
200 * AABTreeClass::Reset -- reset this tree, releases all allocated resources *
201 * *
202 * INPUT: *
203 * *
204 * OUTPUT: *
205 * *
206 * WARNINGS: *
207 * *
208 * HISTORY: *
209 * 6/22/99 GTH : Created. *
210 *=============================================================================================*/
211void AABTreeClass::Reset(void)
212{
213 NodeCount = 0;
214 if (Nodes) {
215 delete[] Nodes;
216 Nodes = NULL;
217 }
218 PolyCount = 0;
219 if (PolyIndices) {
220 delete[] PolyIndices;
221 PolyIndices = NULL;
222 }
223 if (Mesh) {
224 Mesh = NULL;
225 }
226}
227
228/***********************************************************************************************
229 * AABTreeClass::Scale - uniform scale *
230 * *
231 * INPUT: *
232 * *
233 * OUTPUT: *
234 * *
235 * WARNINGS: *
236 * *
237 * HISTORY: *
238 * 6/17/02 Jani : Created. *
239 *=============================================================================================*/
240void AABTreeClass::Scale(float f)
241{
242 for (int i=0;i<NodeCount;++i) {
243 Nodes[i].Min*=f;
244 Nodes[i].Max*=f;
245 }
246}
247
248
249/***********************************************************************************************
250 * AABTreeClass::Build_Tree_Recursive -- Initializes this tree from the given builder *
251 * *
252 * INPUT: *
253 * *
254 * OUTPUT: *
255 * *
256 * WARNINGS: *
257 * *
258 * HISTORY: *
259 * 5/19/2000 gth : Created. *
260 *=============================================================================================*/
261void AABTreeClass::Build_Tree_Recursive(AABTreeBuilderClass::CullNodeStruct * node,int & curpolyindex)
262{
263 /*
264 ** Copy data from the builder's node into our node
265 */
266 CullNodeStruct * newnode = &(Nodes[node->Index]);
267
268 newnode->Min = node->Min;
269 newnode->Max = node->Max;
270
271 /*
272 ** If this is a non-leaf node, set up the child indices, otherwise set up the polygon indices
273 */
274 if (node->Front != NULL) {
275
276 WWASSERT(node->Back != NULL); // if we have one child, we better have both!
277 newnode->Set_Front_Child(node->Front->Index);
278 newnode->Set_Back_Child(node->Back->Index);
279
280 } else {
281
282 newnode->Set_Poly0(curpolyindex);
283 newnode->Set_Poly_Count(node->PolyCount);
284
285 }
286
287 /*
288 ** Copy the polygon indices for this node into our array
289 */
290 for (int pcounter = 0; pcounter < node->PolyCount; pcounter++) {
291 PolyIndices[curpolyindex++] = node->PolyIndices[pcounter];
292 }
293
294 /*
295 ** Install the children
296 */
297 if (node->Front) {
298 Build_Tree_Recursive(node->Front,curpolyindex);
299 }
300 if (node->Back) {
301 Build_Tree_Recursive(node->Back,curpolyindex);
302 }
303}
304
305
306/***********************************************************************************************
307 * AABTreeClass::Set_Mesh -- set the mesh pointer *
308 * *
309 * INPUT: *
310 * *
311 * OUTPUT: *
312 * *
313 * WARNINGS: *
314 * *
315 * HISTORY: *
316 * 6/22/99 GTH : Created. *
317 *=============================================================================================*/
318void AABTreeClass::Set_Mesh(MeshGeometryClass * mesh)
319{
320 Mesh = mesh;
321}
322
323
324/***********************************************************************************************
325 * AABTreeClass::Generate_APT -- Generate an active poly table for the mesh *
326 * *
327 * INPUT: *
328 * box - oriented box to cull the mesh against (in the mesh's coordinate system!!!) *
329 * apt - vector of ints to fill the apt into *
330 * *
331 * OUTPUT: *
332 * *
333 * WARNINGS: *
334 * *
335 * HISTORY: *
336 *=============================================================================================*/
337void AABTreeClass::Generate_APT(const OBBoxClass & box,SimpleDynVecClass<uint32> & apt)
338{
339 OBBoxAPTContextStruct context(box,apt);
340 Generate_OBBox_APT_Recursive(&(Nodes[0]),context);
341}
342
343
344
345/***********************************************************************************************
346 * AABTreeClass::Generate_OBBox_APT_Recursive -- recursively generate the apt *
347 * *
348 * INPUT: *
349 * node - current node in the recursion *
350 * context - structure containing the results/current state *
351 * *
352 * OUTPUT: *
353 * *
354 * WARNINGS: *
355 * *
356 * HISTORY: *
357 * 1/25/00 gth : Created. *
358 *=============================================================================================*/
359void AABTreeClass::Generate_OBBox_APT_Recursive(CullNodeStruct * node,OBBoxAPTContextStruct & context)
360{
361 /*
362 ** Test the volume against the bounding volume of this node
363 ** If it is outside, stop descending the tree.
364 */
365 AABoxClass nodebox;
366 nodebox.Init_Min_Max(node->Min,node->Max); // NOTE: too bad we have to compute the nodebox!!!
367
368 if (!CollisionMath::Intersection_Test(context.Box,nodebox)) {
369 return;
370 }
371
372 /*
373 ** If this is a leaf, test its polygons, otherwise recurse into the children
374 */
375 if (node->Is_Leaf()) {
376
377 int polycount = node->Get_Poly_Count();
378 int poly0 = node->Get_Poly0();
379
380 if (polycount > 0) {
381 TriClass tri;
382 const Vector3 * loc = Mesh->Get_Vertex_Array();
383 const TriIndex * polys = Mesh->Get_Polygon_Array();
384#if (!OPTIMIZE_PLANEEQ_RAM)
385 const Vector4 * norms = Mesh->Get_Plane_Array();
386#endif
387 for (int poly_counter=0; poly_counter<polycount; poly_counter++) {
388
389 int poly_index = PolyIndices[poly0 + poly_counter];
390
391 tri.V[0] = &(loc[ polys[poly_index][0] ]);
392 tri.V[1] = &(loc[ polys[poly_index][1] ]);
393 tri.V[2] = &(loc[ polys[poly_index][2] ]);
394#if (!OPTIMIZE_PLANEEQ_RAM)
395 tri.N = (Vector3*)&(norms[poly_index]);
396#else
397 Vector3 normal;
398 tri.N = &normal;
399 tri.Compute_Normal();
400#endif
401 if (CollisionMath::Intersection_Test(context.Box,tri)) {;
402 context.APT.Add(poly_index);
403 }
404 }
405 }
406
407 } else {
408
409 Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Front_Child()]),context);
410 Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Back_Child()]),context);
411 }
412}
413
414
415/***********************************************************************************************
416 * AABTreeClass::Generate_APT -- generate an apt from a box and viewdir *
417 * *
418 * Indices of the polys which intersect the box and are not backfacing to the given viewdir *
419 * will be added to the passed in apt. *
420 * *
421 * INPUT: *
422 * *
423 * OUTPUT: *
424 * *
425 * WARNINGS: *
426 * *
427 * HISTORY: *
428 * 5/10/2001 gth : Created. *
429 *=============================================================================================*/
430void AABTreeClass::Generate_APT
431(
432 const OBBoxClass & box,
433 const Vector3 & viewdir,
434 SimpleDynVecClass<uint32> & apt
435)
436{
437 OBBoxRayAPTContextStruct context(box,viewdir,apt);
438 Generate_OBBox_APT_Recursive(&(Nodes[0]),context);
439}
440
441
442/***********************************************************************************************
443 * AABTreeClass::Generate_OBBox_APT_Recursive -- recurse, generate the apt for a box and viewd *
444 * *
445 * INPUT: *
446 * *
447 * OUTPUT: *
448 * *
449 * WARNINGS: *
450 * *
451 * HISTORY: *
452 * 5/10/2001 gth : Created. *
453 *=============================================================================================*/
454void AABTreeClass::Generate_OBBox_APT_Recursive(CullNodeStruct * node, OBBoxRayAPTContextStruct & context)
455{
456 /*
457 ** Test the volume against the bounding volume of this node
458 ** If it is outside, stop descending the tree.
459 */
460 AABoxClass nodebox;
461 nodebox.Init_Min_Max(node->Min,node->Max); // NOTE: too bad we have to compute the nodebox!!!
462
463 if (!CollisionMath::Intersection_Test(context.Box,nodebox)) {
464 return;
465 }
466
467 /*
468 ** If this is a leaf, test its polygons, otherwise recurse into the children
469 */
470 if (node->Is_Leaf()) {
471
472 int polycount = node->Get_Poly_Count();
473 int poly0 = node->Get_Poly0();
474
475 if (polycount > 0) {
476 TriClass tri;
477 const Vector3 * loc = Mesh->Get_Vertex_Array();
478 const TriIndex * polys = Mesh->Get_Polygon_Array();
479#if (!OPTIMIZE_PLANEEQ_RAM)
480 const Vector4 * norms = Mesh->Get_Plane_Array();
481#endif
482
483 for (int poly_counter=0; poly_counter<polycount; poly_counter++) {
484
485 int poly_index = PolyIndices[poly0 + poly_counter];
486
487 tri.V[0] = &(loc[ polys[poly_index][0] ]);
488 tri.V[1] = &(loc[ polys[poly_index][1] ]);
489 tri.V[2] = &(loc[ polys[poly_index][2] ]);
490#if (!OPTIMIZE_PLANEEQ_RAM)
491 tri.N = (Vector3*)&(norms[poly_index]);
492#else
493 Vector3 normal;
494 tri.N = &normal;
495 tri.Compute_Normal();
496#endif
497 if (Vector3::Dot_Product(*tri.N,context.ViewVector) < 0.0f) {
498 if (CollisionMath::Intersection_Test(context.Box,tri)) {
499 context.APT.Add(poly_index);
500 }
501 }
502 }
503 }
504
505 } else {
506
507 Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Front_Child()]),context);
508 Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Back_Child()]),context);
509 }
510}
511
512
513/***********************************************************************************************
514 * AABTreeClass::Cast_Ray_Recursive -- Internal implementation of Cast_Ray *
515 * *
516 * INPUT: *
517 * raytest - contains all of the ray test information *
518 * node - current cull node being processed *
519 * *
520 * OUTPUT: *
521 * *
522 * WARNINGS: *
523 * *
524 * HISTORY: *
525 * 6/19/98 GTH : Created. *
526 *=============================================================================================*/
527bool AABTreeClass::Cast_Ray_Recursive(CullNodeStruct * node,RayCollisionTestClass & raytest)
528{
529 /*
530 ** Cull the collision test against the bounding volume of this node
531 ** If it is culled, stop descending the tree.
532 */
533 if (raytest.Cull(node->Min,node->Max)) {
534 return false;
535 }
536
537 bool res = false;
538 if (node->Is_Leaf()) {
539
540 return Cast_Ray_To_Polys(node,raytest);
541
542 } else {
543
544 res = res | Cast_Ray_Recursive(&(Nodes[node->Get_Front_Child()]),raytest);
545 res = res | Cast_Ray_Recursive(&(Nodes[node->Get_Back_Child()]),raytest);
546
547 }
548
549 return res;
550}
551
552
553/***********************************************************************************************
554 * AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive -- Internal implementation *
555 * *
556 * INPUT: *
557 * node - current cull node being processed *
558 * start_point - starting point *
559 * axis_r - the axis along which the ray is projected *
560 * axis_1, axis_2 - the other two axes *
561 * direction - 0 means the ray goes toward the negative axis, 1 means positive. *
562 * flags - reference bitfield for result flags (ray hit edge, start point embedded in tri, etc)*
563 * *
564 * OUTPUT: *
565 * *
566 * WARNINGS: *
567 * *
568 * HISTORY: *
569 * 8/30/00 NH : Created. *
570 *=============================================================================================*/
571int AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(CullNodeStruct * node,
572 const Vector3 & start_point, int axis_r, int axis_1, int axis_2, int direction,
573 unsigned char & flags)
574{
575 /*
576 ** Cull the ray against the bounding volume of this node
577 ** If it is culled, stop descending the tree.
578 ** We do two main tests: a 2D test against axis1 and axis2 to see if the starting point (and
579 ** hence the ray) falls within the 2D projection of the bbox, and a 1D test to see if the ray
580 ** is completely above or below the bbox. The second test checks (start > max) or (start < min)
581 ** depending on the direction of the ray - we do this in a branchless fashion by turning
582 ** (start < min) into (-start > -min). Then we can use tables to perform the correct check.
583 */
584 static const float sign[2] = { -1.0f, 1.0f };
585 float bounds[2], start[2];
586 bounds[0] = -node->Min[axis_r];
587 bounds[1] = node->Max[axis_r];
588 start[0] = -start_point[axis_r];
589 start[1] = start_point[axis_r];
590 if ( start_point[axis_1] < node->Min[axis_1] || start_point[axis_2] < node->Min[axis_2] ||
591 start_point[axis_1] > node->Max[axis_1] || start_point[axis_2] > node->Max[axis_2] ||
592 start[direction] > bounds[direction] ) {
593 return 0;
594 }
595
596 int count = 0;
597 if (node->Is_Leaf()) {
598
599 return Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys(node, start_point, axis_r, axis_1,
600 axis_2, direction, flags);
601
602 } else {
603
604 count += Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(&(Nodes[node->Get_Front_Child()]),
605 start_point, axis_r, axis_1, axis_2, direction, flags);
606 count += Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(&(Nodes[node->Get_Back_Child()]),
607 start_point, axis_r, axis_1, axis_2, direction, flags);
608
609 }
610
611 return count;
612}
613
614
615/***********************************************************************************************
616 * AABTreeClass::Cast_AABox_Recursive -- internal implementation of Cast_AABox *
617 * *
618 * INPUT: *
619 * boxtest - contains description of the collision operation to be performed *
620 * node - current cull node being processed *
621 * *
622 * OUTPUT: *
623 * *
624 * WARNINGS: *
625 * *
626 * HISTORY: *
627 * 6/19/98 GTH : Created. *
628 *=============================================================================================*/
629bool AABTreeClass::Cast_AABox_Recursive(CullNodeStruct * node,AABoxCollisionTestClass & boxtest)
630{
631 /*
632 ** First, check the bounding box of the move against the bounding box
633 ** of this tree, if they don't intersect, bail out
634 */
635 if (boxtest.Cull(node->Min,node->Max)) {
636 return false;
637 }
638
639 bool res = false;
640 if (node->Is_Leaf()) {
641
642 return Cast_AABox_To_Polys(node,boxtest);
643
644 } else {
645
646 res = res | Cast_AABox_Recursive(&(Nodes[node->Get_Front_Child()]),boxtest);
647 res = res | Cast_AABox_Recursive(&(Nodes[node->Get_Back_Child()]),boxtest);
648
649 }
650
651 return res;
652}
653
654
655/***********************************************************************************************
656 * AABTreeClass::Cast_OBBox_Recursive -- Internal implementation of Cast_OBBox *
657 * *
658 * INPUT: *
659 * boxtest - contains description of the collision test to be performed *
660 * node - current cull node being processed *
661 * *
662 * OUTPUT: *
663 * *
664 * WARNINGS: *
665 * *
666 * HISTORY: *
667 * 6/19/98 GTH : Created. *
668 *=============================================================================================*/
669bool AABTreeClass::Cast_OBBox_Recursive(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest)
670{
671 /*
672 ** First, check the bounding box of the move against the bounding box
673 ** of this tree, if they don't intersect, bail out
674 */
675 if (boxtest.Cull(node->Min,node->Max)) {
676 return false;
677 }
678
679 bool res = false;
680 if (node->Is_Leaf()) {
681
682 return Cast_OBBox_To_Polys(node,boxtest);
683
684 } else {
685
686 res = res | Cast_OBBox_Recursive(&(Nodes[node->Get_Front_Child()]),boxtest);
687 res = res | Cast_OBBox_Recursive(&(Nodes[node->Get_Back_Child()]),boxtest);
688
689 }
690
691 return res;
692}
693
694
695/***********************************************************************************************
696 * AABTreeClass::Intersect_OBBox_Recursive -- internal implementation of Intersect_OBBox *
697 * *
698 * INPUT: *
699 * *
700 * OUTPUT: *
701 * *
702 * WARNINGS: *
703 * *
704 * HISTORY: *
705 * 1/20/00 gth : Created. *
706 *=============================================================================================*/
707bool AABTreeClass::Intersect_OBBox_Recursive(AABTreeClass::CullNodeStruct * node,OBBoxIntersectionTestClass & test)
708{
709 /*
710 ** Cull the collision test against the bounding volume of this node
711 ** If it is culled, stop descending the tree.
712 */
713 if (test.Cull(node->Min,node->Max)) {
714 return false;
715 }
716
717 bool res = false;
718 if (node->Is_Leaf()) {
719
720 return Intersect_OBBox_With_Polys(node,test);
721
722 } else {
723
724 res = res | Intersect_OBBox_Recursive(&(Nodes[node->Get_Front_Child()]),test);
725 res = res | Intersect_OBBox_Recursive(&(Nodes[node->Get_Back_Child()]),test);
726 }
727
728 return res;
729}
730
731#ifdef _DEBUG
732#pragma optimize("", off) // We get an odd error when using optimized in the debug.
733// All optimized seems to work. jba.
734#endif
735/***********************************************************************************************
736 * AABTreeClass::Cast_Ray_To_Polys -- cast the ray to polys in the given node *
737 * *
738 * INPUT: *
739 * *
740 * OUTPUT: *
741 * *
742 * WARNINGS: *
743 * *
744 * HISTORY: *
745 * 6/19/98 GTH : Created. *
746 *=============================================================================================*/
747bool AABTreeClass::Cast_Ray_To_Polys(CullNodeStruct * node,RayCollisionTestClass & raytest)
748{
749 if (node->Get_Poly_Count() > 0) {
750 /*
751 ** Simply loop through the polys in this node, checking each for collision
752 */
753 TriClass tri;
754
755 const Vector3 * loc = Mesh->Get_Vertex_Array();
756 const TriIndex * polyverts = Mesh->Get_Polygon_Array();
757#if (!OPTIMIZE_PLANEEQ_RAM)
758 const Vector4 * norms = Mesh->Get_Plane_Array();
759#endif
760
761 int polyhit = -1;
762 int poly0 = node->Get_Poly0();
763 int polycount = node->Get_Poly_Count();
764
765 for (int poly_counter=0; poly_counter<polycount; poly_counter++) {
766
767 int poly_index = PolyIndices[poly0 + poly_counter];
768
769 tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
770 tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
771 tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
772#if (!OPTIMIZE_PLANEEQ_RAM)
773 tri.N = (Vector3*)&(norms[poly_index]);
774#else
775 Vector3 normal;
776 tri.N = &normal;
777 tri.Compute_Normal();
778#endif
779 if (CollisionMath::Collide(raytest.Ray,tri,raytest.Result)) {;
780 polyhit = poly_index;
781 }
782
783 if (raytest.Result->StartBad) {
784 return true;
785 }
786 }
787 if (polyhit != -1) {
788 raytest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
789 return true;
790 }
791 }
792 return false;
793}
794#ifdef _DEBUG
795#pragma optimize("", on)
796#endif
797
798
799/***********************************************************************************************
800 * AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys -- cast ray to polys in the node *
801 * *
802 * INPUT: *
803 * node - current cull node being processed *
804 * start_point - starting point *
805 * axis_r - the axis along which the ray is projected *
806 * axis_1, axis_2 - the other two axes *
807 * direction - 0 means the ray goes toward the negative axis, 1 means positive. *
808 * flags - reference bitfield for result flags (ray hit edge, start point embedded in tri, etc)*
809 * *
810 * OUTPUT: *
811 * *
812 * WARNINGS: *
813 * *
814 * HISTORY: *
815 * 8/30/00 NH : Created. *
816 *=============================================================================================*/
817int AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys(CullNodeStruct * node,
818 const Vector3 & start_point, int axis_r, int axis_1, int axis_2, int direction,
819 unsigned char & flags)
820{
821 int count = 0;
822
823 if (node->Get_Poly_Count() > 0) {
824
825 /*
826 ** Simply loop through the polys in this node, checking each for collision
827 */
828
829 const Vector3 * loc = Mesh->Get_Vertex_Array();
830 const TriIndex * polyverts = Mesh->Get_Polygon_Array();
831 const Vector4 * plane = Mesh->Get_Plane_Array();
832 int poly0 = node->Get_Poly0();
833 int polycount = node->Get_Poly_Count();
834
835 for (int poly_counter=0; poly_counter < polycount; poly_counter++) {
836
837 int poly_index = PolyIndices[poly0 + poly_counter];
838
839 const Vector3 &v0 = loc[ polyverts[poly_index][0] ];
840 const Vector3 &v1 = loc[ polyverts[poly_index][1] ];
841 const Vector3 &v2 = loc[ polyverts[poly_index][2] ];
842 const Vector4 &tri_plane = plane[poly_index];
843
844 // Since (int)true is defined as 1, and (int)false as 0:
845 count += (unsigned int)Cast_Semi_Infinite_Axis_Aligned_Ray_To_Triangle(v0, v1, v2,
846 tri_plane, start_point, axis_r, axis_1, axis_2, direction, flags);
847 }
848 }
849
850 return count;
851}
852
853
854/***********************************************************************************************
855 * AABTreeClass::Cast_AABox_To_Polys -- cast aabox to polys in the given node *
856 * *
857 * INPUT: *
858 * *
859 * OUTPUT: *
860 * *
861 * WARNINGS: *
862 * *
863 * HISTORY: *
864 * 6/19/98 GTH : Created. *
865 *=============================================================================================*/
866bool AABTreeClass::Cast_AABox_To_Polys(CullNodeStruct * node,AABoxCollisionTestClass & boxtest)
867{
868 if (node->Get_Poly_Count() > 0) {
869 /*
870 ** Simply loop through the polys in this node, checking each for collision
871 */
872 TriClass tri;
873
874 const Vector3 * loc = Mesh->Get_Vertex_Array();
875 const TriIndex * polyverts = Mesh->Get_Polygon_Array();
876#if (!OPTIMIZE_PLANEEQ_RAM)
877 const Vector4 * norms = Mesh->Get_Plane_Array();
878#endif
879
880 int polyhit = -1;
881 int poly0 = node->Get_Poly0();
882 int polycount = node->Get_Poly_Count();
883
884 for (int poly_counter=0; poly_counter<polycount; poly_counter++) {
885
886 int poly_index = PolyIndices[poly0 + poly_counter];
887
888 tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
889 tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
890 tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
891#if (!OPTIMIZE_PLANEEQ_RAM)
892 tri.N = (Vector3*)&(norms[poly_index]);
893#else
894 Vector3 normal;
895 tri.N = &normal;
896 tri.Compute_Normal();
897#endif
898 if (CollisionMath::Collide(boxtest.Box,boxtest.Move,tri,boxtest.Result)) {
899 polyhit = poly_index;
900 }
901
902 if (boxtest.Result->StartBad) {
903 return true;
904 }
905 }
906 if (polyhit != -1) {
907 boxtest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
908 return true;
909 }
910 }
911 return false;
912}
913
914
915/***********************************************************************************************
916 * AABTreeClass::Cast_OBBox_To_Polys -- cast obbox to polys in the given node *
917 * *
918 * INPUT: *
919 * *
920 * OUTPUT: *
921 * *
922 * WARNINGS: *
923 * *
924 * HISTORY: *
925 * 6/19/98 GTH : Created. *
926 *=============================================================================================*/
927bool AABTreeClass::Cast_OBBox_To_Polys(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest)
928{
929 int polycount = node->Get_Poly_Count();
930 int poly0 = node->Get_Poly0();
931
932 if (polycount > 0) {
933 /*
934 ** Simply loop through the polys in this node, checking each for collision
935 */
936 TriClass tri;
937
938 const Vector3 * loc = Mesh->Get_Vertex_Array();
939 const TriIndex * polyverts = Mesh->Get_Polygon_Array();
940#if (!OPTIMIZE_PLANEEQ_RAM)
941 const Vector4 * norms = Mesh->Get_Plane_Array();
942#endif
943
944 int polyhit = -1;
945
946 for (int poly_counter=0; poly_counter<polycount; poly_counter++) {
947
948 int poly_index = PolyIndices[poly0 + poly_counter];
949
950 tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
951 tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
952 tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
953#if (!OPTIMIZE_PLANEEQ_RAM)
954 tri.N = (Vector3*)&(norms[poly_index]);
955#else
956 Vector3 normal;
957 tri.N = &normal;
958 tri.Compute_Normal();
959#endif
960
961 if (CollisionMath::Collide(boxtest.Box,boxtest.Move,tri,Vector3(0,0,0),boxtest.Result)) {
962 polyhit = poly_index;
963 }
964
965 if (boxtest.Result->StartBad) {
966 return true;
967 }
968 }
969 if (polyhit != -1) {
970 boxtest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
971 return true;
972 }
973 }
974 return false;
975
976}
977
978
979/***********************************************************************************************
980 * AABTreeClass::Intersect_OBBox_With_Polys -- Test polys for intersection *
981 * *
982 * INPUT: *
983 * *
984 * OUTPUT: *
985 * *
986 * WARNINGS: *
987 * *
988 * HISTORY: *
989 * 1/20/00 gth : Created. *
990 *=============================================================================================*/
991bool AABTreeClass::Intersect_OBBox_With_Polys
992(
993 CullNodeStruct * node,
994 OBBoxIntersectionTestClass & test
995)
996{
997 int poly0 = node->Get_Poly0();
998 int polycount = node->Get_Poly_Count();
999
1000 if (polycount > 0) {
1001 /*
1002 ** Simply loop through the polys in this node, checking each for collision
1003 */
1004 TriClass tri;
1005
1006 const Vector3 * loc = Mesh->Get_Vertex_Array();
1007 const TriIndex * polyverts = Mesh->Get_Polygon_Array();
1008#if (!OPTIMIZE_PLANEEQ_RAM)
1009 const Vector4 * norms = Mesh->Get_Plane_Array();
1010#endif
1011
1012 for (int poly_counter=0; poly_counter<polycount; poly_counter++) {
1013
1014 int poly_index = PolyIndices[poly0 + poly_counter];
1015
1016 tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
1017 tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
1018 tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
1019#if (!OPTIMIZE_PLANEEQ_RAM)
1020 tri.N = (Vector3*)&(norms[poly_index]);
1021#else
1022 Vector3 normal;
1023 tri.N = &normal;
1024 tri.Compute_Normal();
1025#endif
1026
1027 if (CollisionMath::Intersection_Test(test.Box,tri)) {
1028 return true;
1029 }
1030 }
1031 }
1032 return false;
1033}
1034
1035
1036/***********************************************************************************************
1037 * AABTreeClass::Update_Bounding_Boxes_Recursive -- recompute the bounding boxes *
1038 * *
1039 * Typically this function will be used when you have modified the mesh slightly and you need *
1040 * to update the bounding boxes but you want to keep the structure of the tree. *
1041 * *
1042 * INPUT: *
1043 * *
1044 * OUTPUT: *
1045 * *
1046 * WARNINGS: *
1047 * *
1048 * HISTORY: *
1049 * 6/22/99 GTH : Created. *
1050 *=============================================================================================*/
1051void AABTreeClass::Update_Bounding_Boxes_Recursive(CullNodeStruct * node)
1052{
1053 node->Min.Set(100000.0f,100000.0f,100000.0f);
1054 node->Max.Set(-100000.0f,-100000.0f,-100000.0f);
1055
1056 /*
1057 ** Recurse to the children first
1058 */
1059 if (node->Is_Leaf() == false) {
1060
1061 Update_Bounding_Boxes_Recursive(&(Nodes[node->Get_Front_Child()]));
1062 Update_Bounding_Boxes_Recursive(&(Nodes[node->Get_Back_Child()]));
1063
1064 /*
1065 ** Bound our children
1066 */
1067 int front = node->Get_Front_Child();
1068 int back = node->Get_Back_Child();
1069
1070 if (Nodes[front].Min.X < node->Min.X) node->Min.X = Nodes[front].Min.X;
1071 if (Nodes[front].Max.X > node->Max.X) node->Max.X = Nodes[front].Max.X;
1072
1073 if (Nodes[front].Min.Y < node->Min.Y) node->Min.Y = Nodes[front].Min.Y;
1074 if (Nodes[front].Max.Y > node->Max.Y) node->Max.Y = Nodes[front].Max.Y;
1075
1076 if (Nodes[front].Min.Z < node->Min.Z) node->Min.Z = Nodes[front].Min.Z;
1077 if (Nodes[front].Max.Z > node->Max.Z) node->Max.Z = Nodes[front].Max.Z;
1078
1079 if (Nodes[back].Min.X < node->Min.X) node->Min.X = Nodes[back].Min.X;
1080 if (Nodes[back].Max.X > node->Max.X) node->Max.X = Nodes[back].Max.X;
1081
1082 if (Nodes[back].Min.Y < node->Min.Y) node->Min.Y = Nodes[back].Min.Y;
1083 if (Nodes[back].Max.Y > node->Max.Y) node->Max.Y = Nodes[back].Max.Y;
1084
1085 if (Nodes[back].Min.Z < node->Min.Z) node->Min.Z = Nodes[back].Min.Z;
1086 if (Nodes[back].Max.Z > node->Max.Z) node->Max.Z = Nodes[back].Max.Z;
1087
1088 } else {
1089
1090 /*
1091 ** Bound our polygons
1092 */
1093 int poly0 = node->Get_Poly0();
1094 int polycount = node->Get_Poly_Count();
1095
1096 for (int poly_index = 0; poly_index < polycount; poly_index++) {
1097 int pi = PolyIndices[poly0 + poly_index];
1098 Update_Min_Max(pi,node->Min,node->Max );
1099 }
1100
1101 }
1102
1103 WWASSERT(node->Min.X != 100000.0f);
1104 WWASSERT(node->Min.Y != 100000.0f);
1105 WWASSERT(node->Min.Z != 100000.0f);
1106 WWASSERT(node->Max.X != -100000.0f);
1107 WWASSERT(node->Max.Y != -100000.0f);
1108 WWASSERT(node->Max.Z != -100000.0f);
1109}
1110
1111
1112/***********************************************************************************************
1113 * AABTreeClass::Update_Min_Max -- updates min and max given a polygon index *
1114 * *
1115 * INPUT: *
1116 * *
1117 * OUTPUT: *
1118 * *
1119 * WARNINGS: *
1120 * *
1121 * HISTORY: *
1122 * 6/22/99 GTH : Created. *
1123 *=============================================================================================*/
1124void AABTreeClass::Update_Min_Max(int poly_index,Vector3 & min,Vector3 & max)
1125{
1126 for (int vert_index = 0; vert_index < 3; vert_index++) {
1127
1128 const TriIndex * polyverts = Mesh->Get_Polygon_Array() + poly_index;
1129 const Vector3 * point = Mesh->Get_Vertex_Array() + (*polyverts)[vert_index];
1130
1131 if (point->X < min.X) min.X = point->X;
1132 if (point->Y < min.Y) min.Y = point->Y;
1133 if (point->Z < min.Z) min.Z = point->Z;
1134
1135 if (point->X > max.X) max.X = point->X;
1136 if (point->Y > max.Y) max.Y = point->Y;
1137 if (point->Z > max.Z) max.Z = point->Z;
1138 }
1139}
1140
1141
1142/***********************************************************************************************
1143 * AABTreeClass::Load_W3D -- Load a W3D description of an AABTree *
1144 * *
1145 * INPUT: *
1146 * *
1147 * OUTPUT: *
1148 * *
1149 * WARNINGS: *
1150 * *
1151 * HISTORY: *
1152 * 5/22/2000 gth : Created. *
1153 *=============================================================================================*/
1154void AABTreeClass::Load_W3D(ChunkLoadClass & cload)
1155{
1156 Reset();
1157
1158 W3dMeshAABTreeHeader header;
1159 cload.Open_Chunk();
1160 WWASSERT(cload.Cur_Chunk_ID() == W3D_CHUNK_AABTREE_HEADER);
1161 cload.Read(&header,sizeof(header));
1162 cload.Close_Chunk();
1163
1164 NodeCount = header.NodeCount;
1165 PolyCount = header.PolyCount;
1166 Nodes = W3DNEWARRAY CullNodeStruct[NodeCount];
1167 PolyIndices = W3DNEWARRAY uint32[PolyCount];
1168
1169 while (cload.Open_Chunk()) {
1170 switch (cload.Cur_Chunk_ID())
1171 {
1172 case W3D_CHUNK_AABTREE_POLYINDICES:
1173 Read_Poly_Indices(cload);
1174 break;
1175
1176 case W3D_CHUNK_AABTREE_NODES:
1177 Read_Nodes(cload);
1178 break;
1179 }
1180 cload.Close_Chunk();
1181 }
1182}
1183
1184
1185/***********************************************************************************************
1186 * AABTreeClass::Read_Poly_Indices -- load the polygon index array *
1187 * *
1188 * INPUT: *
1189 * *
1190 * OUTPUT: *
1191 * *
1192 * WARNINGS: *
1193 * *
1194 * HISTORY: *
1195 * 5/22/2000 gth : Created. *
1196 *=============================================================================================*/
1197void AABTreeClass::Read_Poly_Indices(ChunkLoadClass & cload)
1198{
1199 cload.Read(PolyIndices,sizeof(uint32) * PolyCount);
1200}
1201
1202
1203/***********************************************************************************************
1204 * AABTreeClass::Read_Nodes -- Load the node array *
1205 * *
1206 * INPUT: *
1207 * *
1208 * OUTPUT: *
1209 * *
1210 * WARNINGS: *
1211 * *
1212 * HISTORY: *
1213 * 5/22/2000 gth : Created. *
1214 *=============================================================================================*/
1215void AABTreeClass::Read_Nodes(ChunkLoadClass & cload)
1216{
1217 W3dMeshAABTreeNode w3dnode;
1218
1219 for (int i=0; i<NodeCount; i++) {
1220 cload.Read(&w3dnode,sizeof(w3dnode));
1221
1222 Nodes[i].Min.X = w3dnode.Min.X;
1223 Nodes[i].Min.Y = w3dnode.Min.Y;
1224 Nodes[i].Min.Z = w3dnode.Min.Z;
1225
1226 Nodes[i].Max.X = w3dnode.Max.X;
1227 Nodes[i].Max.Y = w3dnode.Max.Y;
1228 Nodes[i].Max.Z = w3dnode.Max.Z;
1229
1230 Nodes[i].FrontOrPoly0 = w3dnode.FrontOrPoly0;
1231 Nodes[i].BackOrPolyCount = w3dnode.BackOrPolyCount;
1232 }
1233}
1234
1235
1236
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
sign
int sign(NUM x)
Definition BaseType.h:158
WWASSERT
#define WWASSERT
Definition aabtreebuilder.cpp:68
w3d_file.h
W3D_CHUNK_AABTREE_HEADER
@ W3D_CHUNK_AABTREE_HEADER
Definition w3d_file.h:392
W3D_CHUNK_AABTREE_POLYINDICES
@ W3D_CHUNK_AABTREE_POLYINDICES
Definition w3d_file.h:393
W3D_CHUNK_AABTREE_NODES
@ W3D_CHUNK_AABTREE_NODES
Definition w3d_file.h:394
W3DNEWARRAY
#define W3DNEWARRAY
Definition always.h:110
uint32
unsigned long uint32
Definition bittype.h:46
AABTreeClass::Set_Mesh
void Set_Mesh(MeshGeometryClass *mesh)
Definition aabtree.cpp:318
AABTreeClass::MeshGeometryClass
friend class MeshGeometryClass
Definition aabtree.h:218
AABTreeClass::Load_W3D
void Load_W3D(ChunkLoadClass &cload)
Definition aabtree.cpp:1154
AABTreeClass::AABTreeClass
AABTreeClass(void)
Definition aabtree.cpp:89
AABTreeClass::~AABTreeClass
~AABTreeClass(void)
Definition aabtree.cpp:160
AABTreeClass::Generate_APT
void Generate_APT(const OBBoxClass &box, SimpleDynVecClass< uint32 > &apt)
Definition aabtree.cpp:337
AABTreeClass::Scale
void Scale(float scale)
Definition aabtree.cpp:240
AABTreeClass::AABTreeBuilderClass
friend class AABTreeBuilderClass
Definition aabtree.h:220
AABoxClass::Init_Min_Max
void Init_Min_Max(const Vector3 &min, const Vector3 &max)
Definition aabox.h:339
AABoxCollisionTestClass::Cull
bool Cull(const Vector3 &min, const Vector3 &max)
Definition coltest.h:239
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
CollisionMath::Collide
static bool Collide(const LineSegClass &line, const AAPlaneClass &plane, CastResultStruct *result)
Definition colmathline.cpp:114
CollisionMath::Intersection_Test
static bool Intersection_Test(const AABoxClass &box, const TriClass &tri)
Definition colmathaabtri.cpp:1041
CollisionTestClass::Result
CastResultStruct * Result
Definition coltest.h:98
OBBoxCollisionTestClass::Cull
bool Cull(const Vector3 &min, const Vector3 &max)
Definition coltest.h:295
RayCollisionTestClass::Ray
LineSegClass Ray
Definition coltest.h:139
RayCollisionTestClass::Cull
bool Cull(const Vector3 &min, const Vector3 &max)
Definition coltest.h:168
TriClass::N
const Vector3 * N
Definition tri.h:64
TriClass::Compute_Normal
void Compute_Normal()
Definition tri.h:67
TriClass::V
const Vector3 * V[3]
Definition tri.h:65
Vector3::Dot_Product
static WWINLINE float Dot_Product(const Vector3 &a, const Vector3 &b)
Definition vector3.h:293
Vector3::X
float X
Definition vector3.h:90
Vector3::Z
float Z
Definition vector3.h:92
Vector3::Y
float Y
Definition vector3.h:91
Vector3::Set
WWINLINE void Set(float x, float y, float z)
Definition vector3.h:103
TriIndex
Vector3i16 TriIndex
Definition meshgeometry.h:66
CastResultStruct::SurfaceType
uint32 SurfaceType
Definition castres.h:67
W3dMeshAABTreeNode::Max
W3dVectorStruct Max
Definition w3d_file.h:1311
W3dMeshAABTreeNode::Min
W3dVectorStruct Min
Definition w3d_file.h:1310
test
int test
Definition test6.cpp:32
Cast_Semi_Infinite_Axis_Aligned_Ray_To_Triangle
bool Cast_Semi_Infinite_Axis_Aligned_Ray_To_Triangle(const Vector3 &tri_point0, const Vector3 &tri_point1, const Vector3 &tri_point2, const Vector4 &tri_plane, const Vector3 &ray_start, int axis_r, int axis_1, int axis_2, int direction, unsigned char &flags)
Definition tri.h:219