?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
changed: gcc8 base update
[opensg.git] / Source / System / NodeCores / Drawables / Geometry / Util / OSGStriperHalfEdgeGraph.cpp
blob48bc8b367390d5a6ca1a2a3358b1df241497aa69
1 /*---------------------------------------------------------------------------*\
2 * OpenSG *
3 * *
4 * *
5 * Copyright (C) 2000-2002 by the OpenSG Forum *
6 * *
7 * www.opensg.org *
8 * *
9 * contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de *
10 * *
11 \*---------------------------------------------------------------------------*/
12 /*---------------------------------------------------------------------------*\
13 * License *
14 * *
15 * This library is free software; you can redistribute it and/or modify it *
16 * under the terms of the GNU Library General Public License as published *
17 * by the Free Software Foundation, version 2. *
18 * *
19 * This library is distributed in the hope that it will be useful, but *
20 * WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
22 * Library General Public License for more details. *
23 * *
24 * You should have received a copy of the GNU Library General Public *
25 * License along with this library; if not, write to the Free Software *
26 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
27 * *
28 \*---------------------------------------------------------------------------*/
29 /*---------------------------------------------------------------------------*\
30 * Changes *
31 * *
32 * *
33 * *
34 * *
35 * *
36 * *
37 \*---------------------------------------------------------------------------*/
38
39 // System declarations
40 #include <iostream>
41 #include <stdlib.h>
42 #include <math.h>
43
44 #include <map>
45
46 #include "OSGGL.h"
47
48 // Application declarations
49
50
51 // Class declarations
52 #include "OSGStriperHalfEdgeGraph.h"
53
54
55 using namespace std;
56
57 OSG_USING_NAMESPACE
58
59 #if !defined(OSG_DO_DOC) || defined(OSG_DOC_DEV)
60
61 // Static Class Varible implementations:
62
63 //----------------------------------------------------------------------
64 // Method: HalfEdgeGraph
65 // Author: jbehr
66 // Date: Tue Feb 15 18:16:59 2000
67 // Description:
68 // Default Constructor
69 //----------------------------------------------------------------------
70 StriperHalfEdgeGraph::StriperHalfEdgeGraph (void) :
71 _edgeLinkVec (),
72 _trianglePool (),
73
74 _validTriangleBag (),
75 _invalidTriangleBag(),
76
77 _stripBag (),
78 _fanBag (),
79 _triBag ()
80 {
81 }
82
83 //----------------------------------------------------------------------
84 // Method: HalfEdgeGraph
85 // Author: jbehr
86 // Date: Tue Feb 15 18:16:59 2000
87 // Description:
88 // Copy Constructor
89 //----------------------------------------------------------------------
90 #if 0
91 StriperHalfEdgeGraph::StriperHalfEdgeGraph(
92 const StriperHalfEdgeGraph &OSG_CHECK_ARG(obj))
93 {
94 SWARNING << "Run HalfEdgeGraph copy constructor; not impl.\n" << endl;
95 }
96 #endif
97
98 //----------------------------------------------------------------------
99 // Method: ~HalfEdgeGraph
100 // Author: jbehr
101 // Date: Tue Feb 15 18:16:59 2000
102 // Description:
103 // Destructor
104 //----------------------------------------------------------------------
105 StriperHalfEdgeGraph::~StriperHalfEdgeGraph (void )
106 {
107 clear();
108 }
109
110 //----------------------------------------------------------------------
111 // Method: ~HalfEdgeGraph
112 // Author: jbehr
113 // Date: Tue Feb 15 18:16:59 2000
114 // Description:
115 // Destructor
116 //----------------------------------------------------------------------
117 bool StriperHalfEdgeGraph::Triangle::verify (void)
118 {
119 bool retCode = true;
120 Triangle *neighbor[3];
121
122 neighbor[0] = halfEdgeVec[0].twin ? halfEdgeVec[0].twin->triangle : 0;
123 neighbor[1] = halfEdgeVec[1].twin ? halfEdgeVec[1].twin->triangle : 0;
124 neighbor[2] = halfEdgeVec[2].twin ? halfEdgeVec[2].twin->triangle : 0;
125
126 if ( ( neighbor[0] &&
127 ( (neighbor[0] == neighbor[1] ) ||
128 (neighbor[0] == neighbor[2] )
129 )
130 ) ||
131 ( neighbor[1] &&
132 ( (neighbor[1] == neighbor[0] ) ||
133 (neighbor[1] == neighbor[2] ) )
134 ) ||
135 ( neighbor[2] &&
136 ( (neighbor[2] == neighbor[0] ) ||
137 (neighbor[2] == neighbor[1] ) )
138 )
139 )
140 {
141 FINFO(("StriperHalfEdgeGraph::Triangle::verify: Neighbor linked more "
142 "than once: %p/%p/%p\n", static_cast<void *>(neighbor[0]),
143 static_cast<void *>(neighbor[1]),
144 static_cast<void *>(neighbor[2])));
145 retCode = false;
146 }
147
148 if((halfEdgeVec[0].vertexStart() == halfEdgeVec[1].vertexStart()) ||
149 (halfEdgeVec[0].vertexStart() == halfEdgeVec[2].vertexStart()) ||
150 (halfEdgeVec[1].vertexStart() == halfEdgeVec[2].vertexStart()))
151 {
152 SINFO << "StriperHalfEdgeGraph::Triangle::verify: "
153 << "Invalid collapsed Triangle"
154 << endl;
155 retCode = false;
156 }
157
158 if((halfEdgeVec[0].triangle != this) ||
159 (halfEdgeVec[1].triangle != this) ||
160 (halfEdgeVec[2].triangle != this))
161 {
162 SINFO << "StriperHalfEdgeGraph::Triangle::verify: Invalid halfEdge->"
163 << "triangle pointer" << endl;
164 retCode = false;
165 }
166
167 if((halfEdgeVec[0].next != &halfEdgeVec[1]) ||
168 (halfEdgeVec[1].next != &halfEdgeVec[2]) ||
169 (halfEdgeVec[2].next != &halfEdgeVec[0]))
170 {
171 SINFO << "StriperHalfEdgeGraph::Triangle::verify: Edge next link error"
172 << endl;
173 retCode = false;
174 }
175
176 return retCode;
177 }
178
179 //----------------------------------------------------------------------
180 // Method: reserve
181 // Author: jbehr
182 // Date: Tue Feb 15 18:16:59 2000
183 // Description:
184 //
185 //----------------------------------------------------------------------
186 void StriperHalfEdgeGraph::reserve(UInt32 vertexNum, UInt32 triangleNum,
187 UInt32 reserveEdges )
188 {
189 UInt32 i;
190
191 _trianglePool.setChunkSize(triangleNum);
192 _edgeLinkVec.resize(vertexNum);
193
194 if(reserveEdges > 0)
195 {
196 for(i = 0; i < vertexNum; ++i)
197 _edgeLinkVec[i].reserve(reserveEdges);
198 }
199 }
200
201 //----------------------------------------------------------------------
202 // Method: verify
203 // Author: jbehr
204 // Date: Tue Feb 15 18:16:59 2000
205 // Description:
206 //
207 //----------------------------------------------------------------------
208 bool StriperHalfEdgeGraph::verify (bool verbose)
209 {
210 bool retCode = true;
211 UInt32 i, n;
212 Triangle *triangle, *nt0, *nt1, *nt2;
213 Int32 triangleState[4];
214 Int32 invalidTriangles = 0;
215 Int32 halfEdgeCount = 0;
216 map< Int32, Int32 > connectionMap;
217 map< Int32, Int32 >::iterator connectionI;
218 Int32 connectionCount;
219 bool validTri = false;
220
221 for(i = 0; i < 4; ++i)
222 triangleState[i] = 0;
223
224 for( i = 0, triangle = _validTriangleBag.first;
225 triangle;
226 i++, triangle = triangle->next)
227 {
228 // Looks strange (GV)
229 if((triangle->verify() && (triangle->state >= 0)) ||
230 (triangle->state <= 3))
231 {
232 triangleState[triangle->state]++;
233 validTri = true;
234 }
235 else
236 {
237 ++invalidTriangles;
238 validTri = false;
239 }
240
241 if ( verbose )
242 {
243 nt0 = triangle->halfEdgeVec[0].twin ?
244 triangle->halfEdgeVec[0].twin->triangle : 0;
245 nt1 = triangle->halfEdgeVec[1].twin ?
246 triangle->halfEdgeVec[1].twin->triangle : 0;
247 nt2 = triangle->halfEdgeVec[2].twin ?
248 triangle->halfEdgeVec[2].twin->triangle : 0;
249
250 FINFO ( ( "HEG: Triangle %p: %d %d %d, %p %p %p: %s\n",
251 static_cast<void *>(triangle),
252 triangle->halfEdgeVec[0].vertexStart(),
253 triangle->halfEdgeVec[1].vertexStart(),
254 triangle->halfEdgeVec[2].vertexStart(),
255 static_cast<void *>(nt0),
256 static_cast<void *>(nt1),
257 static_cast<void *>(nt2),
258 (validTri ? "VALID" : "INVALID" ) ) );
259 }
260 }
261
262 SINFO << "HEG: linked triangle count " << _validTriangleBag.countElem()
263 << endl;
264 SINFO << "HEG: invalid triangle " << invalidTriangles
265 << endl;
266 SINFO << "HEG: nonmanifold split: " << _invalidTriangleBag.countElem()
267 << endl;
268
269 SINFO << "HEG: triangle state: "
270 << triangleState[0]
271 << "/"
272 << triangleState[1]
273 << "/"
274 << triangleState[2]
275 << "/"
276 << triangleState[3]
277 << endl;
278
279 n = UInt32(_edgeLinkVec.size());
280 halfEdgeCount = 0;
281 for (i = 0; i < n; ++i)
282 {
283 connectionCount = UInt32(_edgeLinkVec[i].size());
284
285 halfEdgeCount += connectionCount;
286 if (connectionMap.find(connectionCount) == connectionMap.end())
287 connectionMap[connectionCount] = 1;
288 else
289 connectionMap[connectionCount]++;
290
291 if (verbose)
292 {
293 HalfEdgeLink::iterator lI;
294 for ( lI = _edgeLinkVec[i].begin();
295 lI != _edgeLinkVec[i].end(); ++lI )
296 {
297 FINFO (( "HEG: HalfEdge %p: %d to %d, twin: %p\n",
298 static_cast<void *>(lI->second),
299 lI->second->vertexStart(),
300 lI->second->vertexEnd(),
301 static_cast<void *>(lI->second->twin)));
302 }
303 }
304 }
305 for(connectionI = connectionMap.begin();
306 connectionI != connectionMap.end(); ++connectionI)
307 {
308 SINFO << "HEG: Connection: " << connectionI->first << '/'
309 << connectionI->second << ' ' << std::endl;
310 }
311
312 SINFO << "HEG: HalfEdgeCount: " << halfEdgeCount << endl;
313
314 return retCode;
315 }
316
317 //----------------------------------------------------------------------
318 // Method: calcOptPrim
319 // Author: jbehr
320 // Date: Tue Feb 15 18:16:59 2000
321 // Description:
322 //
323 //----------------------------------------------------------------------
324 UInt32 StriperHalfEdgeGraph::calcOptPrim(UInt32 extIteration,
325 bool doStrip, bool doFan,
326 UInt32 minFanTriangles)
327 {
328 Int32 iteration = extIteration;
329 bool sample = iteration > 1 ? true : false;
330 bool checkRevOrder = sample;
331 TriangleList degreeBag[4];
332 TriangleList *fList = 0;
333 Int32 cost = 0, sampleCost = 0;
334 Int32 stripCost = 0, revCost = 0, fanCost = 0, triCost = 0;
335 Int32 bestCost = 0, worstCost = 0, lowDegree;
336 UInt32 i, n;
337 WalkCase walkCase = START;
338 Triangle *triangle, *next;
339 HalfEdge *twin = 0, *gateEdge = 0, *halfEdge = 0;
340 bool doMainLoop = true;
341 UInt32 seed = 1, bestSeed = 1;
342 Int32 mostDegree = 3;
343 UInt32 triangleLeft = _trianglePool.countElem();
344 srand(1);
345
346 if(doFan)
347 {
348 n = UInt32(_edgeLinkVec.size());
349 fanCost = 0;
350
351 // find fans
352 for(i = 0; i < n; ++i)
353 {
354 if((_edgeLinkVec[i].size() >= minFanTriangles) &&
355 (gateEdge = _edgeLinkVec[i][0].second) &&
356 (gateEdge->triangle->valid()))
357 {
358 for(halfEdge = gateEdge->next->next->twin;
359 (halfEdge && halfEdge->triangle->valid() &&
360 (halfEdge != gateEdge));
361 halfEdge = halfEdge->next->next->twin)
362 ;
363 if(halfEdge == gateEdge)
364 {
365 // fan is closed; mark every triangle
366 triangle = 0;
367 fList = new TriangleList;
368 for(halfEdge = gateEdge;
369 !triangle || (halfEdge != gateEdge);
370 halfEdge = halfEdge->next->next->twin)
371 {
372 triangle = halfEdge->triangle;
373 _validTriangleBag.release(*triangle);
374 triangle->drop();
375 triangle->state = FAN_PART;
376 fList->add(*triangle);
377 }
378 _fanBag.push_back(Primitive(i,fList));
379 fanCost += (UInt32(_edgeLinkVec[i].size()) + 2);
380 triangleLeft -= UInt32(_edgeLinkVec[i].size());
381 }
382 }
383 }
384 }
385
386 if(doStrip && iteration)
387 {
388 // push every triangle into the according degree bag
389 degreeBag[mostDegree].paste(_validTriangleBag);
390 for(triangle = degreeBag[mostDegree].first; triangle; triangle = next)
391 {
392 next = triangle->next;
393 if(triangle->valid())
394 {
395 if(triangle->state != mostDegree)
396 {
397 degreeBag[mostDegree].release(*triangle);
398 _validTriangleBag.release(*triangle);
399 degreeBag[triangle->state].add( *triangle);
400 }
401 }
402 else
403 {
404 SWARNING << "INVALID TRIANGLE IN VALID TRIANGLE BAG\n" << endl;
405 }
406 }
407
408 for(iteration--; iteration >= 0; iteration--)
409 {
410 seed = iteration ? rand() : bestSeed;
411 srand (seed);
412
413 fList = 0;
414 cost = 0;
415 doMainLoop = true;
416 walkCase = START;
417
418 // run the main loop
419 while(doMainLoop)
420 {
421 switch(walkCase)
422 {
423 case START:
424 stripCost = 0;
425 triangle = 0;
426
427 for(lowDegree = 1; lowDegree < 4; ++lowDegree)
428 {
429 if((degreeBag[lowDegree].empty() == false))
430 {
431 if(sample)
432 {
433 // pick a random triangle
434 n = degreeBag[lowDegree].countElem() - 1;
435 i = Int32(float(n)*rand()/float(RAND_MAX));
436 triangle = degreeBag[lowDegree].first;
437 while (i--)
438 triangle = triangle->next;
439 }
440 else
441 {
442 // pick the first triangle
443 triangle = degreeBag[lowDegree].first;
444 }
445 break;
446 }
447 }
448
449 if(triangle)
450 {
451 // create the new list
452 fList = new TriangleList;
453
454 // find the best neighbour
455 gateEdge = 0;
456 for (i = 0; i < 3; ++i)
457 {
458 if((twin = triangle->halfEdgeVec[i].twin) &&
459 (twin->triangle->state > 0))
460 {
461 if(twin->next->next->twin &&
462 (twin->next->next->twin->triangle->state > 0))
463 {
464 gateEdge = &triangle->halfEdgeVec[i];
465 break;
466 }
467 else
468 {
469 if(twin->next->twin &&
470 (twin->next->twin->triangle->state > 0))
471 {
472 gateEdge = &triangle->halfEdgeVec[i];
473 }
474 else
475 {
476 if((twin->triangle->state > 0))
477 gateEdge = &triangle->halfEdgeVec[i];
478 }
479 }
480 }
481 }
482
483 // release and store the first triangle
484 dropOutTriangle (*triangle,degreeBag);
485 fList->add(*triangle);
486 stripCost += 3;
487
488 // set the next step
489 if(gateEdge)
490 {
491 walkCase = LEFT;
492 ++stripCost;
493 }
494 else
495 {
496 walkCase = FINISH;
497 }
498 }
499 else
500 {
501 doMainLoop = false;
502 }
503 break;
504
505 case LEFT:
506 gateEdge = gateEdge->twin;
507 triangle = gateEdge->triangle;
508
509 // find the next gate
510 if(triangle->state == DEGREE_0)
511 {
512 gateEdge = 0;
513 walkCase = FINISH;
514 }
515 else
516 {
517 if((twin = gateEdge->next->next->twin) &&
518 (twin->triangle->state > 0))
519 {
520 gateEdge = gateEdge->next->next;
521 ++stripCost;
522 walkCase = RIGHT;
523 }
524 else
525 {
526 gateEdge = gateEdge->next;
527 stripCost += 2;
528 walkCase = LEFT;
529 }
530 }
531 // store the current triangle
532 dropOutTriangle (*triangle,degreeBag);
533 fList->add(*triangle);
534 break;
535
536 case RIGHT:
537 gateEdge = gateEdge->twin;
538 triangle = gateEdge->triangle;
539
540 // find the next gate
541 if(triangle->state == DEGREE_0)
542 {
543 gateEdge = 0;
544 walkCase = FINISH;
545 }
546 else
547 {
548 if((twin = gateEdge->next->twin) &&
549 (twin->triangle->state > 0))
550 {
551 gateEdge = gateEdge->next;
552 ++stripCost;
553 walkCase = LEFT;
554 }
555 else
556 {
557 gateEdge = gateEdge->next->next;
558 stripCost += 2;
559 walkCase = RIGHT;
560 }
561 }
562 // store the current triangle
563 dropOutTriangle (*triangle,degreeBag);
564 fList->add(*triangle);
565 break;
566
567 case FINISH:
568 // try to reverse the strip
569 if(checkRevOrder &&
570 (revCost = calcStripCost(*fList,true)) &&
571 (revCost < stripCost))
572 {
573 _stripBag.push_back(Primitive(1,fList));
574 cost += revCost;
575 }
576 else
577 {
578 _stripBag.push_back(Primitive(0,fList));
579 cost += stripCost;
580 }
581 walkCase = START;
582 fList = 0;
583 break;
584 }
585 }
586
587 if(sample)
588 {
589 sampleCost = cost + (degreeBag[0].countElem() * 3) + fanCost;
590 if(!bestCost || (sampleCost < bestCost))
591 {
592 bestCost = sampleCost;
593 bestSeed = seed;
594 }
595 if(sampleCost > worstCost)
596 worstCost = sampleCost;
597
598 SINFO << " cost/best/worst: "
599 << sampleCost << '/' << bestCost << '/' << worstCost
600 << endl;
601 }
602
603 if(iteration)
604 {
605 // reinit the four degree bags
606 degreeBag[mostDegree].paste(degreeBag[0]);
607 n = UInt32(_stripBag.size());
608 for(i = 0; i < n; ++i)
609 {
610 degreeBag[mostDegree].paste(*_stripBag[i].second);
611 delete _stripBag[i].second;
612 }
613 _stripBag.clear();
614 for(triangle = degreeBag[mostDegree].first; triangle;
615 triangle = next)
616 {
617 next = triangle->next;
618 triangle->resetDegreeState(STRIP_PART);
619 if (triangle->valid())
620 {
621 if(triangle->state != mostDegree)
622 {
623 degreeBag[mostDegree].release(*triangle);
624 degreeBag[triangle->state].add(*triangle);
625 }
626 }
627 else
628 {
629 SWARNING << "INVALID TRIANGLE IN REINIT\n" << endl;
630 SWARNING << triangle->state << endl;
631 }
632 }
633 }
634 }
635 }
636 else
637 {
638 // push every valid triangle in degree 0; we don't strip anything
639 degreeBag[0].paste(_validTriangleBag);
640 }
641
642 if(sample)
643 {
644 SWARNING << "range: "
645 << bestCost << '/' << worstCost << ' '
646 << float(100 * (worstCost-bestCost))/float(bestCost) << '%'
647 << endl;
648 }
649
650 // collect isolated triangles
651 degreeBag[0].paste(_invalidTriangleBag);
652 triCost = degreeBag[0].countElem() * 3;
653 if(triCost)
654 {
655 fList = new TriangleList;
656 fList->paste(degreeBag[0]);
657 _triBag.push_back(Primitive(0,fList));
658 }
659
660 return (cost + fanCost + triCost);
661 }
662
663 //----------------------------------------------------------------------
664 // Method: calcStripCost
665 // Author: jbehr
666 // Date: Tue Feb 15 18:16:59 2000
667 // Description:
668 //
669 //----------------------------------------------------------------------
670 Int32 StriperHalfEdgeGraph::calcStripCost(TriangleList &strip, bool rev)
671 {
672 Triangle *triangle = rev ? strip.last : strip.first, *nextTriangle;
673 HalfEdge /* *firstEdge, */ *halfEdge, *gate;
674 WalkCase walkCase;
675 Int32 cost = 0;
676
677 if (triangle)
678 {
679 cost = 3;
680 if ((nextTriangle = rev ? triangle->prev : triangle->next))
681 {
682 gate = findGateEdge(triangle,nextTriangle);
683 //firstEdge = gate->next->next;
684 ++cost;
685 walkCase = LEFT;
686 for(triangle = nextTriangle;
687 (nextTriangle = (rev ? triangle->prev : triangle->next));
688 triangle = nextTriangle)
689 {
690 halfEdge = gate->twin;
691 gate = findGateEdge(triangle,nextTriangle);
692 if (walkCase == RIGHT)
693 {
694 // RIGHT
695 if(halfEdge->next == gate)
696 {
697 ++cost;
698 walkCase = LEFT;
699 }
700 else
701 {
702 // swap; walkCase stays RIGHT;
703 cost += 2;
704 }
705 }
706 else
707 {
708 // LEFT
709 if(halfEdge->next->next == gate)
710 {
711 ++cost;
712 walkCase = RIGHT;
713 }
714 else
715 {
716 // swap; walkCase stays LEFT;
717 cost += 2;
718 }
719 }
720 }
721 }
722 }
723
724 return cost;
725 }
726
727 //----------------------------------------------------------------------
728 // Method: fillPrimFromStrip
729 // Author: jbehr
730 // Date: Tue Feb 15 18:16:59 2000
731 // Description:
732 //
733 //----------------------------------------------------------------------
734 Int32 StriperHalfEdgeGraph::fillIndexFromStrip(
735 std::vector<StriperHalfEdgeGraph::IndexT> &indexVec,
736 TriangleList &strip, bool rev)
737 {
738 Triangle *triangle = rev ? strip.last : strip.first, *nextTriangle;
739 HalfEdge *firstEdge, *halfEdge, *gate;
740 WalkCase walkCase;
741 StriperHalfEdgeGraph::IndexT vertex;
742 Int32 cost = 0;
743
744 if (triangle)
745 {
746 cost = 3;
747 indexVec.reserve(32); // find better value
748 indexVec.resize(3);
749 if((nextTriangle = (rev ? triangle->prev : triangle->next)))
750 {
751 ++cost;
752 gate = findGateEdge(triangle,nextTriangle);
753 firstEdge = gate->next->next;
754 indexVec.push_back(vertex = gate->twin->next->vertexEnd());
755
756 walkCase = LEFT;
757 for(triangle = nextTriangle;
758 (nextTriangle = (rev ? triangle->prev : triangle->next));
759 triangle = nextTriangle)
760 {
761 halfEdge = gate->twin;
762 gate = findGateEdge(triangle,nextTriangle);
763 if(walkCase == RIGHT)
764 {
765 // RIGHT
766 if(halfEdge->next == gate)
767 {
768 indexVec.push_back(vertex = gate->twin->next->vertexEnd());
769 walkCase = LEFT;
770 ++cost;
771 }
772 else
773 {
774 // swap; walkCase stays RIGHT;
775 indexVec.back() = gate->vertexEnd();
776 indexVec.push_back(gate->vertexStart());
777 indexVec.push_back(vertex = gate->twin->next->vertexEnd());
778 cost += 2;
779 }
780 }
781 else
782 {
783 // LEFT
784 if (halfEdge->next->next == gate)
785 {
786 indexVec.push_back(vertex = gate->twin->next->vertexEnd());
787 walkCase = RIGHT;
788 ++cost;
789 }
790 else
791 {
792 // swap; walkCase stays LEFT;
793 indexVec.back() = gate->vertexStart();
794 indexVec.push_back(gate->vertexEnd());
795 indexVec.push_back(vertex = gate->twin->next->vertexEnd());
796 cost += 2;
797 }
798 }
799 }
800 }
801 else
802 {
803 firstEdge = &triangle->halfEdgeVec[0];
804 }
805
806 indexVec[0] = vertex = firstEdge->vertexStart();
807 indexVec[1] = vertex = firstEdge->next->vertexStart();
808 indexVec[2] = vertex = firstEdge->next->next->vertexStart();
809 }
810
811 return cost;
812 }
813
814 //----------------------------------------------------------------------
815 // Method: fillPrimFromFan
816 // Author: jbehr
817 // Date: Tue Feb 15 18:16:59 2000
818 // Description:
819 //
820 //----------------------------------------------------------------------
821 Int32 StriperHalfEdgeGraph::fillIndexFromFan(
822 std::vector<StriperHalfEdgeGraph::IndexT> &indexVec,
823 HalfEdge &firstEdge )
824 {
825 Int32 count = 0;
826 HalfEdge *halfEdge(&firstEdge);
827 HalfEdge *gateEdge = 0;
828
829 if(halfEdge)
830 {
831 count = 3;
832 indexVec.resize(2);
833 indexVec[0] = halfEdge->vertexStart();
834 indexVec[1] = halfEdge->vertexEnd();
835 for(gateEdge = halfEdge->next->next->twin;
836 gateEdge != halfEdge;
837 gateEdge = gateEdge->next->next->twin)
838 {
839 indexVec.push_back(gateEdge->vertexEnd());
840 ++count;
841 }
842 indexVec.push_back(halfEdge->vertexEnd());
843 }
844 else
845 {
846 SWARNING << "Invalid fac in fillIndexFromFan()" << endl;
847 }
848 return count;
849 }
850
851 //----------------------------------------------------------------------
852 // Method: calcEdgeLines
853 // Author: jbehr
854 // Date: Tue Feb 15 18:16:59 2000
855 // Description:
856 //
857 //----------------------------------------------------------------------
858 Int32 StriperHalfEdgeGraph::getPrimitive(
859 vector<StriperHalfEdgeGraph::IndexT> &indexVec,
860 Int32 type)
861 {
862 UInt32 i = 0, n = 0;
863 Triangle *triangle;
864 std::vector<Primitive> *bag = 0;
865
866 indexVec.clear();
867
868 // fan
869 if(!bag && (n = UInt32(_fanBag.size())) &&
870 ((type == GL_TRIANGLE_FAN) || !type))
871 {
872 i = n - 1;
873 bag = &_fanBag;
874 fillIndexFromFan(indexVec,
875 *_edgeLinkVec[_fanBag[i].first][0].second);
876 type = GL_TRIANGLE_FAN;
877 }
878
879 // strip
880 if(!bag && (n = UInt32(_stripBag.size())) &&
881 ((type == GL_TRIANGLE_STRIP) || !type))
882 {
883 i = n - 1;
884 bag = &_stripBag;
885 fillIndexFromStrip(indexVec, *_stripBag[i].second,
886 _stripBag[i].first ? true : false );
887 type = GL_TRIANGLE_STRIP;
888 }
889
890 // tri
891 if(!bag && (n = UInt32(_triBag.size())) &&
892 ((type == GL_TRIANGLES) || !type))
893 {
894 bag = &_triBag;
895 if (_triBag[0].second->empty() == false)
896 {
897 n = _triBag[0].second->countElem() * 3;
898 indexVec.resize(n);
899 i = 0;
900 for(triangle = _triBag[0].second->first; triangle;
901 triangle = triangle->next )
902 {
903 indexVec[i++] = triangle->halfEdgeVec[0].vertexStart();
904 indexVec[i++] = triangle->halfEdgeVec[1].vertexStart();
905 indexVec[i++] = triangle->halfEdgeVec[2].vertexStart();
906 }
907 }
908 type = GL_TRIANGLES;
909 i = 0;
910 }
911
912 if(bag)
913 {
914 _invalidTriangleBag.paste(*((*bag)[i].second));
915 delete (*bag)[i].second;
916 if (i)
917 bag->resize(i);
918 else
919 bag->clear();
920 }
921 else
922 {
923 type = 0;
924 }
925 return type;
926 }
927
928 //----------------------------------------------------------------------
929 // Method: calcEdgeLines
930 // Author: jbehr
931 // Date: Tue Feb 15 18:16:59 2000
932 // Description:
933 //
934 //----------------------------------------------------------------------
935 Int32 StriperHalfEdgeGraph::calcEgdeLines(
936 vector<StriperHalfEdgeGraph::IndexT> & indexVec,
937 bool codeBorder )
938 {
939 UInt32 i, nN, j, nE, halfEdgeCount = 0;
940 StriperHalfEdgeGraph::IndexT startVertexIndex, endVertexIndex;
941 HalfEdge *halfEdge;
942 bool isBorder;
943
944 indexVec.clear();
945 nN = UInt32(_edgeLinkVec.size());
946 for (i = 0; i < nN; ++i)
947 {
948 nE = UInt32(_edgeLinkVec[i].size());
949 for ( j = 0; j < nE; ++j)
950 {
951 halfEdge = _edgeLinkVec[i][j].second;
952 startVertexIndex = halfEdge->vertexStart();
953 endVertexIndex = halfEdge->vertexEnd();
954
955 if ((isBorder = (halfEdge->twin == 0)) || (startVertexIndex <
956 endVertexIndex))
957 {
958 indexVec.push_back(startVertexIndex);
959 indexVec.push_back(endVertexIndex);
960 if(codeBorder)
961 indexVec.push_back(isBorder ? 0 : 1);
962 ++halfEdgeCount;
963 }
964 }
965 }
966 return halfEdgeCount;
967 }
968
969 //----------------------------------------------------------------------
970 // Method:
971 // Author: jbehr
972 // Date: Tue Feb 15 18:16:59 2000
973 // Description:
974 //
975 //----------------------------------------------------------------------
976 void StriperHalfEdgeGraph::clear(void)
977 {
978 UInt32 i,n;
979
980 _edgeLinkVec.clear();
981 _trianglePool.clear();
982
983 n = UInt32(_stripBag.size());
984 for(i = 0; i < n; ++i)
985 delete _stripBag[i].second;
986 _stripBag.clear();
987
988 n = UInt32(_fanBag.size());
989 for(i = 0; i < n; ++i)
990 delete _fanBag[i].second;
991 _fanBag.clear();
992
993 n = UInt32(_triBag.size());
994 for(i = 0; i < n; ++i)
995 delete _triBag[i].second;
996 _triBag.clear();
997 }
998
999 #endif // remove from all but dev docs