1 /*
2 PLIB - A Suite of Portable Game Libraries
3 Copyright (C) 1998,2002 Steve Baker
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Library General Public
7 License as published by the Free Software Foundation; either
8 version 2 of the License, or (at your option) any later version.
9
10 This library 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 GNU
13 Library General Public License for more details.
14
15 You should have received a copy of the GNU Library General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19 For further information visit http://plib.sourceforge.net
20
21 $Id: ssgBranch.cxx 1860 2004-02-16 20:51:12Z stromberg $
22 */
23
24
25 #include "ssgLocal.h"
26
copy_from(ssgBranch * src,int clone_flags)27 void ssgBranch::copy_from ( ssgBranch *src, int clone_flags )
28 {
29 ssgEntity::copy_from ( src, clone_flags ) ;
30
31 for ( int i = 0 ; i < src -> getNumKids () ; i++ )
32 {
33 ssgEntity *k = src -> getKid ( i ) ;
34
35 if ( k != NULL && ( clone_flags & SSG_CLONE_RECURSIVE ) )
36 addKid ( (ssgEntity *)( k -> clone ( clone_flags )) ) ;
37 else
38 addKid ( k ) ;
39 }
40 }
41
clone(int clone_flags)42 ssgBase *ssgBranch::clone ( int clone_flags )
43 {
44 ssgBranch *b = new ssgBranch ;
45 b -> copy_from ( this, clone_flags ) ;
46 return b ;
47 }
48
49
50
ssgBranch(void)51 ssgBranch::ssgBranch (void)
52 {
53 type = ssgTypeBranch () ;
54 }
55
56
~ssgBranch(void)57 ssgBranch::~ssgBranch (void)
58 {
59 removeAllKids () ;
60 }
61
62
zeroSpareRecursive()63 void ssgBranch::zeroSpareRecursive ()
64 {
65 zeroSpare () ;
66
67 for ( ssgEntity *k = getKid ( 0 ) ; k != NULL ; k = getNextKid () )
68 k -> zeroSpareRecursive () ;
69 }
70
71
recalcBSphere(void)72 void ssgBranch::recalcBSphere (void)
73 {
74 emptyBSphere () ;
75
76 for ( ssgEntity *k = getKid ( 0 ) ; k != NULL ; k = getNextKid () )
77 extendBSphere ( k -> getBSphere () ) ;
78
79 bsphere_is_invalid = FALSE ;
80 }
81
82
addKid(ssgEntity * entity)83 void ssgBranch::addKid ( ssgEntity *entity )
84 {
85 kids. addEntity ( entity ) ;
86 entity -> addParent ( this ) ;
87 dirtyBSphere () ;
88 }
89
90
removeKid(int n)91 void ssgBranch::removeKid ( int n )
92 {
93 ssgEntity *k = kids.getEntity ( n ) ;
94
95 if ( k != NULL ) {
96 k -> removeParent ( this ) ;
97 kids.removeEntity ( n ) ;
98 dirtyBSphere () ;
99 }
100 }
101
102
removeKid(ssgEntity * entity)103 void ssgBranch::removeKid ( ssgEntity *entity )
104 {
105 removeKid( searchForKid( entity ) );
106 }
107
108
removeAllKids(void)109 void ssgBranch::removeAllKids (void)
110 {
111 for ( int k = getNumKids() - 1; k >= 0; --k ) {
112 removeKid ( k ) ;
113 }
114 }
115
116
replaceKid(int n,ssgEntity * new_entity)117 void ssgBranch::replaceKid ( int n, ssgEntity *new_entity )
118 {
119 if ( n >= 0 && n < getNumKids () )
120 {
121 getKid ( n ) -> removeParent ( this ) ;
122 kids.replaceEntity ( n, new_entity ) ;
123 new_entity -> addParent ( this ) ;
124 dirtyBSphere () ;
125 }
126 }
127
replaceKid(ssgEntity * old_entity,ssgEntity * new_entity)128 void ssgBranch::replaceKid ( ssgEntity *old_entity, ssgEntity *new_entity )
129 {
130 replaceKid ( searchForKid( old_entity ), new_entity ) ;
131 }
132
133
print(FILE * fd,char * indent,int how_much)134 void ssgBranch::print ( FILE *fd, char *indent, int how_much )
135 {
136 ssgEntity::print ( fd, indent, how_much ) ;
137 fprintf ( fd, "%s Num Kids=%d\n", indent, getNumKids() ) ;
138
139 if ( getNumParents() != getRef() )
140 ulSetError ( UL_WARNING, "Ref count doesn't tally with parent count" ) ;
141
142 if ( how_much > 1 )
143 { if ( bsphere.isEmpty() )
144 fprintf ( fd, "%s BSphere is Empty.\n", indent ) ;
145 else
146 fprintf ( fd, "%s BSphere R=%g, C=(%g,%g,%g)\n", indent,
147 bsphere.getRadius(), bsphere.getCenter()[0], bsphere.getCenter()[1], bsphere.getCenter()[2] ) ;
148 }
149
150 char in [ 100 ] ;
151 sprintf ( in, "%s ", indent ) ;
152
153 for ( ssgEntity *e = getKid ( 0 ) ; e != NULL ; e = getNextKid() )
154 e -> print ( fd, in, how_much ) ;
155 }
156
157
getStats(int * num_branches,int * num_leaves,int * num_tris,int * num_verts)158 void ssgBranch::getStats ( int *num_branches, int *num_leaves, int *num_tris, int *num_verts )
159 {
160 int nb, nl, nt, nv ;
161
162 *num_branches = 1 ; /* this! */
163 *num_leaves = 0 ;
164 *num_tris = 0 ;
165 *num_verts = 0 ;
166
167 for ( int i = 0 ; i < getNumKids () ; i++ )
168 {
169 ssgEntity *e = getKid ( i ) ;
170
171 e -> getStats ( & nb, & nl, & nt, & nv ) ;
172 *num_branches += nb ;
173 *num_leaves += nl ;
174 *num_tris += nt ;
175 *num_verts += nv ;
176 }
177 }
178
179
getByName(char * match)180 ssgEntity *ssgBranch::getByName ( char *match )
181 {
182 if ( getName() != NULL && strcmp ( getName(), match ) == 0 )
183 return this ;
184
185 /* Otherwise check the kids for a match */
186
187 for ( ssgEntity* k = getKid ( 0 ) ; k != NULL ; k = getNextKid() )
188 {
189 ssgEntity *e = k -> getByName ( match ) ;
190
191 if ( e != NULL )
192 return e ;
193 }
194
195 return NULL ;
196 }
197
198
getByPath(char * path)199 ssgEntity *ssgBranch::getByPath ( char *path )
200 {
201 /* Ignore leading '/' */
202
203 if ( *path == '/' )
204 ++path ;
205
206 char *n = getName () ;
207
208 /*
209 If this node has no name then pass the request down the tree
210 */
211
212 if ( n == NULL )
213 {
214 for ( ssgEntity* k = getKid ( 0 ) ; k != NULL ; k = getNextKid () )
215 {
216 ssgEntity *e = k -> getByPath ( path ) ;
217
218 if ( e != NULL )
219 return e ;
220 }
221
222 return NULL ;
223 }
224
225 /*
226 If this node does have a name - but it doesn't match the
227 next part of the path then punt.
228 */
229
230 unsigned int l = strlen ( n ) ;
231
232 if ( strlen ( path ) < l || strncmp ( n, path, l ) != 0 )
233 return NULL ;
234
235 /*
236 If the first part of the path is this ssgBranch, we
237 may have a winner.
238 */
239
240 char c = path [ l ] ;
241
242 /* If we reached the end of the path - we win! */
243
244 if ( c == '\0' )
245 return this ;
246
247 if ( c == '/' )
248 {
249 /* If the path continues, try to follow the path to the kids */
250
251 for ( ssgEntity* k = getKid ( 0 ) ; k != NULL ; k = getNextKid () )
252 {
253 ssgEntity *e = k -> getByPath ( path + l ) ;
254
255 if ( e != NULL )
256 return e ;
257 }
258 }
259
260 return NULL ;
261 }
262
263
264
cull(sgFrustum * f,sgMat4 m,int test_needed)265 void ssgBranch::cull ( sgFrustum *f, sgMat4 m, int test_needed )
266 {
267 if ( ! preTravTests ( &test_needed, SSGTRAV_CULL ) )
268 return ;
269
270 int cull_result = cull_test ( f, m, test_needed ) ;
271
272 if ( cull_result == SSG_OUTSIDE )
273 return ;
274
275 for ( ssgEntity *e = getKid ( 0 ) ; e != NULL ; e = getNextKid() )
276 e -> cull ( f, m, cull_result != SSG_INSIDE ) ;
277
278 postTravTests ( SSGTRAV_CULL ) ;
279 }
280
281
282
hot(sgVec3 s,sgMat4 m,int test_needed)283 void ssgBranch::hot ( sgVec3 s, sgMat4 m, int test_needed )
284 {
285 if ( ! preTravTests ( &test_needed, SSGTRAV_HOT ) )
286 return ;
287
288 int hot_result = hot_test ( s, m, test_needed ) ;
289
290 if ( hot_result == SSG_OUTSIDE )
291 return ;
292
293 _ssgPushPath ( this ) ;
294
295 for ( ssgEntity *e = getKid ( 0 ) ; e != NULL ; e = getNextKid() )
296 e -> hot ( s, m, hot_result != SSG_INSIDE ) ;
297
298 _ssgPopPath () ;
299
300 postTravTests ( SSGTRAV_HOT ) ;
301 }
302
303
304
los(sgVec3 s,sgMat4 m,int test_needed)305 void ssgBranch::los ( sgVec3 s, sgMat4 m, int test_needed )
306 {
307 if ( ! preTravTests ( &test_needed, SSGTRAV_LOS ) )
308 return ;
309
310 int los_result = los_test ( s, m, test_needed ) ;
311
312 if ( los_result == SSG_OUTSIDE )
313 return ;
314
315 _ssgPushPath ( this ) ;
316
317 for ( ssgEntity *e = getKid ( 0 ) ; e != NULL ; e = getNextKid() )
318 e -> los ( s, m, los_result != SSG_INSIDE ) ;
319
320 _ssgPopPath () ;
321
322 postTravTests ( SSGTRAV_LOS) ;
323 }
324
325
isect(sgSphere * s,sgMat4 m,int test_needed)326 void ssgBranch::isect ( sgSphere *s, sgMat4 m, int test_needed )
327 {
328 if ( ! preTravTests ( &test_needed, SSGTRAV_ISECT ) )
329 return ;
330
331 int isect_result = isect_test ( s, m, test_needed ) ;
332
333 if ( isect_result == SSG_OUTSIDE )
334 return ;
335
336 _ssgPushPath ( this ) ;
337
338 for ( ssgEntity *e = getKid ( 0 ) ; e != NULL ; e = getNextKid() )
339 e -> isect ( s, m, isect_result != SSG_INSIDE ) ;
340
341 _ssgPopPath () ;
342
343 postTravTests ( SSGTRAV_ISECT ) ;
344 }
345
346
load(FILE * fd)347 int ssgBranch::load ( FILE *fd )
348 {
349 int nkids ;
350
351 _ssgReadInt ( fd, & nkids ) ;
352
353 if ( ! ssgEntity::load ( fd ) )
354 return FALSE ;
355
356 for ( int i = 0 ; i < nkids ; i++ )
357 {
358 ssgEntity *kid ;
359
360 if ( ! _ssgLoadObject ( fd, (ssgBase **) &kid, ssgTypeEntity () ) )
361 return FALSE ;
362
363 addKid ( kid ) ;
364 }
365
366 return TRUE ;
367 }
368
369
save(FILE * fd)370 int ssgBranch::save ( FILE *fd )
371 {
372 _ssgWriteInt ( fd, getNumKids() ) ;
373
374 if ( ! ssgEntity::save ( fd ) )
375 return FALSE ;
376
377 for ( int i = 0 ; i < getNumKids() ; i++ )
378 {
379 if ( ! _ssgSaveObject ( fd, getKid ( i ) ) )
380 return FALSE ;
381 }
382
383 return TRUE ;
384 }
385
386 // ----------------------- code by W.K for merging hierarchy nodes ------------------------------
387
388
389 // #define VERBOSE
390 int maxTriangles = 100; // Thats a nice value for handling MDL files for BoB.
391 // You might want to assign another value, possibly -1 before calling mergeHNodes
392 int maxVertices = 195; // see maxTriangles
393
394
395
396 static int noOfMergedNodes; // number of merged nodes
397
AddLeafToTriangles(ssgVtxArray * pSrc,ssgVtxArray * pDest)398 void AddLeafToTriangles(ssgVtxArray *pSrc , ssgVtxArray *pDest)
399 // pDest must be of type GL_TRIANGLES
400 // So, this function adds the contents of a leaf to a GL_TRIANGLES node.
401 {
402 // Add vertices and keep track of old to new indexes
403 if(pSrc->getNumTriangles()==0) return; // wk 14.7.2002
404 int * aiOld2NewIndex = new int[pSrc->getNumVertices()];
405 int iSrc; // iDest;
406 for(iSrc = 0; iSrc < pSrc->getNumVertices(); iSrc++)
407 { float * pfSrc = pSrc->getVertex(iSrc);
408 int bFound = FALSE;
409 /* test
410 for(iDest = 0; iDest < pDest->getNumVertices(); iDest++)
411 { float * pfDest = pDest->getVertex(iDest);
412 #define MYABS(x) ((x>0)?(x):(-(x)))
413 if (MYABS(pfSrc[0]-pfDest[0])+MYABS(pfSrc[1]-pfDest[1])+
414 MYABS(pfSrc[2]-pfDest[2]) < 0.0001)
415 { bFound = TRUE;
416 aiOld2NewIndex[iSrc] = iDest;
417 }
418 }*/
419 if(!bFound)
420 { aiOld2NewIndex[iSrc] = pDest->getNumVertices();
421 pDest->vertices->add(pfSrc);
422 float * f = pSrc->getNormal(iSrc);
423 if (f)
424 pDest->normals->add(f);
425 else
426 {
427 pDest->normals->add(_ssgNormalUp);
428 }
429 f = pSrc->getTexCoord(iSrc);
430 if (f)
431 pDest->texcoords->add(f);
432 else
433 {
434 pDest->texcoords->add(_ssgTexCoord00);
435 }
436 // assert(pSrc->colours->getNum()==0);
437 }
438
439 }
440 // Add faces
441 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(0)]);
442 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(1)]);
443 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(2)]);
444 if(pSrc->getGLtype()==GL_TRIANGLE_FAN)
445 {
446 for(iSrc=1;iSrc<pSrc->getNumTriangles();iSrc++)
447 { // add 0, i+1, i+2
448 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(0)]);
449 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(iSrc+1)]);
450 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(iSrc+2)]);
451
452 }
453 }
454 else
455 { assert(pSrc->getGLtype()==GL_TRIANGLES);
456 for(iSrc=1;iSrc<pSrc->getNumTriangles();iSrc++)
457 { // add 0, i+1, i+2
458 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(iSrc*3)]);
459 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(iSrc*3+1)]);
460 pDest->addIndex(aiOld2NewIndex[*pSrc->getIndex(iSrc*3+2)]);
461
462 }
463 }
464
465 // State
466 pDest->setState(pSrc ->getState());
467 delete aiOld2NewIndex ;
468 }
469
470
471
recursiveMergeHNodes(ssgEntity * root,int delta)472 void recursiveMergeHNodes ( ssgEntity *root, int delta )
473 // This is the recursive part of "mergeHNodes".
474 // Walks the scene graph and looks for nodes to merge.
475 // Uses AddLeafToTriangles for the actual merging
476 {
477 if ( root == NULL )
478 return ;
479
480 if ( root -> isAKindOf ( ssgTypeBranch() ) )
481 { // see whether we can merge some of the kids
482 ssgBranch *b = (ssgBranch *) root ;
483
484 int i1, // loop var.
485 oldnk=b -> getNumKids (), oldi1=-1 ; // for debug purpose only
486 i1 = 0 ;
487 while(i1 < b -> getNumKids () )
488 {
489 // check that each loop increases i1 or decreases b -> getNumKids ()
490 if(!((i1>oldi1) || (oldnk>b ->getNumKids ())))
491 break;
492 assert((i1>oldi1) || (oldnk>b ->getNumKids ()));
493 oldi1=i1;
494 oldnk=b ->getNumKids ();
495
496 ssgEntity * pThis = b -> getKid ( i1 ) ;
497 if ( pThis -> isAKindOf ( ssgTypeBranch() ) )
498 { recursiveMergeHNodes ( pThis, delta ); // recursively go deeper into the scene graph
499 i1++;
500 }
501 else if(( pThis -> isAKindOf ( ssgTypeLeaf() ) ) && (i1+delta < b -> getNumKids ()))
502 { ssgEntity * pOther = b -> getKid ( i1+delta );
503 if( pOther -> isAKindOf ( ssgTypeLeaf() ) )
504 { ssgLeaf *l1 = (ssgLeaf *)pThis, *l2 = (ssgLeaf *)pOther;
505 // now: l1 = kid at i1, l2 = kid at i1+delta
506 if ( (l1->getState() == l2->getState()) &&
507 ((maxTriangles < 0) || (l1->getNumTriangles()+l2->getNumTriangles()<maxTriangles )) &&
508 ((maxVertices < 0) || (l1->getNumVertices()+l2->getNumVertices()<maxVertices )) &&
509 (0 == strcmp(l1->getPrintableName(), l2->getPrintableName()))
510 )
511 {
512 if (((l1->getGLtype() == GL_TRIANGLE_FAN) || (l1->getGLtype() == GL_TRIANGLES)) &&
513 ((l2->getGLtype() == GL_TRIANGLE_FAN) || (l2->getGLtype() == GL_TRIANGLES)))
514 { // For using MDL files, these are all the types that we need ...
515
516 if (l1->isA(ssgTypeVtxTable()))
517 { l1 = ((ssgVtxTable *)l1)->getAs_ssgVtxArray(); // Kludge: mem leak
518 b->replaceKid ( i1, l1 ) ;
519 }
520 if (l2->isA(ssgTypeVtxTable()))
521 { l2 = ((ssgVtxTable *)l2)->getAs_ssgVtxArray(); // Kludge: mem leak
522 b->replaceKid ( i1+delta, l2 ) ;
523 }
524 assert(l1 -> isAKindOf ( ssgTypeVtxArray() ));
525 assert(l2 -> isAKindOf ( ssgTypeVtxArray() ));
526 if((l1->getNumTriangles()+l2->getNumTriangles())<1300) // ??? wk kludge
527 {
528 #ifdef VERBOSE
529 printf("I do sthg :-) %d\n", noOfMergedNodes++);
530 #else
531 noOfMergedNodes++;
532 #endif
533 if(l1->getGLtype() == GL_TRIANGLE_FAN) // convert to GL_TRIANGLES
534 { ssgVtxArray * pNewArray = new ssgVtxArray(GL_TRIANGLES,
535 new ssgVertexArray(),
536 new ssgNormalArray(), new ssgTexCoordArray(),
537 new ssgColourArray(), new ssgIndexArray());
538 AddLeafToTriangles((ssgVtxArray *)l1, pNewArray);
539 pNewArray->setName(l1->getPrintableName());
540 assert(l1==b->getKid(i1));
541 b->removeKid(i1);
542 b->addKid(pNewArray);
543 pNewArray->dirtyBSphere ();
544 l1 = pNewArray;
545 }
546 // l1 is of type GL_TRIANGLES now.
547 { //ssgEntity *t= b->getKid(i1+delta);
548 //assert(l2==t);
549 }
550 AddLeafToTriangles((ssgVtxArray *)l2, (ssgVtxArray *)l1);
551 l1->dirtyBSphere ();
552 l2->dirtyBSphere (); // unnessesary ?
553 b->removeKid(l2); // kid(i1+delta) changed because of remove!?! i1+delta);
554 }
555 }
556 else
557 { i1++;
558 printf("wrong types: %ld, %ld, num Trias: %ld, %ld\n",
559 (long)l1->getGLtype(), (long)l1->getGLtype(),
560 (long)l1->getNumTriangles(), (long)l2->getNumTriangles());
561 }
562 }
563 else
564 i1++;
565 }
566 else
567 i1++;
568 }
569 else
570 i1++;
571 }
572
573
574
575 /*
576 int i1=0;
577 for ( i = 0 ; i < b -> getNumKids () ; i++ )
578 { ssgEntity * pThis = b -> getKid ( i1 ) ;
579 if ( pThis -> isAKindOf ( ssgTypeBranch() ) )
580 { recursiveMergeHNodes ( pThis );
581 i1++;
582 }
583 else
584 { assert( pThis -> isAKindOf ( ssgTypeLeaf() ) );
585 ssgLeaf *l1 = (ssgLeaf *)pThis;
586 assert(l1 -> isAKindOf ( ssgTypeVtxArray() ));
587 static int noOfMergedNodes=0;
588 printf("I could do sthg :-) %d\n", noOfMergedNodes++);
589 assert(l1->getGLtype() == GL_TRIANGLE_FAN); // convert to GL_TRIANGLES
590 ssgVtxArray * pNewArray = new ssgVtxArray(GL_TRIANGLES,
591 new ssgVertexArray(), new ssgNormalArray(),
592 new ssgTexCoordArray(), new ssgColourArray(),
593 new ssgIndexArray());
594 AddLeafToTriangles((ssgVtxArray *)l1, pNewArray);
595 b->removeKid(i1);
596 pNewArray->dirtyBSphere ();
597 b->addKid(pNewArray);
598
599 pNewArray->setName("meins!");
600 }
601
602 }
603 */
604 }
605 }
606
607
mergeHNodes()608 void ssgBranch::mergeHNodes()
609 // merges hierarchy nodes if (not iff :-/):
610 // a) Both have the same state
611 // b) the same name
612 // c) the result would not have more than maxTriangles triangles (if maxTriangles is negative, this is not checked).
613 // d) the result would not have more than maxVertices vertices (if maxVertices is negative, this is not checked).
614 // e) both are of type GL_TRIANGLE_FAN or GL_TRIANGLES
615 {
616
617
618 int deltas[] = { 1 ,2 ,1 ,3 ,2 ,1 ,2 ,4 ,2 ,1 ,5 ,1 ,2 ,6 ,2 ,1 ,2 ,7 ,2 ,1 ,2 ,1 ,8 ,1 ,2 ,1 ,2 ,9 ,2 ,1 ,2 ,1,
619 10 ,1 ,2 ,1 ,2 ,11 ,1 ,12 ,1 ,2 ,13 ,1 ,2 ,14 ,2 ,1 ,1 ,15 ,1 ,16 ,1 ,17 ,2 ,1 ,18 ,1 ,22 ,2 ,25 ,
620 2 ,1 ,30 ,2 ,1 ,2 ,1 ,13 ,2 ,1 ,2 ,1 };
621 noOfMergedNodes = 0;
622 for(unsigned i=0; i < sizeof(deltas)/sizeof(int); i++)
623 {
624 recursiveMergeHNodes ( this, deltas[i] );
625 #ifdef VERBOSE
626 printf("############################################### ^%d\n". deltas[i]);
627 #endif
628 }
629 printf("%d nodes were merged!\n", noOfMergedNodes);
630 }
631
632