?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fixed: auto_ptr -> unique_ptr
[opensg.git] / Source / System / NodeCores / Drawables / Geometry / Util / OSGGeoOptimization.cpp
blob61d4da9bfaae58be12d65327c2304ffc40cc60da
1 /*---------------------------------------------------------------------------*\
2 * OpenSG *
3 * *
4 * *
5 * Copyright (C) 2011 by the OpenSG Forum *
6 * *
7 * contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de *
8 * *
9 \*---------------------------------------------------------------------------*/
10 /*---------------------------------------------------------------------------*\
11 * License *
12 * *
13 * This library is free software; you can redistribute it and/or modify it *
14 * under the terms of the GNU Library General Public License as published *
15 * by the Free Software Foundation, version 2. *
16 * *
17 * This library is distributed in the hope that it will be useful, but *
18 * WITHOUT ANY WARRANTY; without even the implied warranty of *
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
20 * Library General Public License for more details. *
21 * *
22 * You should have received a copy of the GNU Library General Public *
23 * License along with this library; if not, write to the Free Software *
24 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
25 * *
26 \*---------------------------------------------------------------------------*/
27
28 #include "OSGConfig.h"
29 #include "OSGGeoOptimization.h"
30 #include "OSGGeometry.h"
31 #include "OSGTypedGeoIntegralProperty.h"
32 #include "OSGTypedGeoVectorProperty.h"
33
34 #include <set>
35
36 // #include <boost/functional/hash/hash.hpp>
37 // #include <tr1/unordered_set>
38
39 #define OSG_GEOOPT_VERBOSE 1
40 #undef OSG_GEOOPT_VERBOSE
41
42 #define OSG_GEOOPT_STATISTICS 1
43 #undef OSG_GEOOPT_STATISTICS
44
45 OSG_BEGIN_NAMESPACE
46
47 #if __GNUC__ >= 4 || __GNUC_MINOR__ >=3
48 #pragma GCC diagnostic push
49 #pragma GCC diagnostic ignored "-Wunused-function"
50 #endif
51
52 namespace
53 {
54 // Index Tuple (IT) comparison function objects.
55 // There are ITLess, ITHash, ITEqual to allow using
56 // std::set<> or std::tr1::unordered_set<>
57
58 struct ITLess
59 {
60 typedef std::vector<GeoIntegralProperty *> IndexStore;
61
62 explicit ITLess(Geometry *geo);
63 ITLess(const ITLess &other);
64
65 bool operator()(UInt32 lhs, UInt32 rhs) const;
66
67 std::ostream &print(std::ostream &os, UInt32 idx);
68
69 Geometry *_geo;
70 IndexStore _istore;
71
72 private:
73
74 void operator =(const ITLess &rhs);
75 };
76
77 /* explicit */
78 ITLess::ITLess(Geometry *geo)
79 : _geo (geo),
80 _istore()
81 {
82 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
83 {
84 GeoIntegralProperty *idx = _geo->getIndex(i);
85 bool add = true;
86
87 if(idx != NULL)
88 {
89 for(UInt32 j = 0; add == true && j < _istore.size(); ++j)
90 {
91 if(idx == _istore[j])
92 add = false;
93 }
94
95 if(add == true)
96 _istore.push_back(idx);
97 }
98 }
99 }
100
101 ITLess::ITLess(const ITLess &other)
102 : _geo (other._geo),
103 _istore(other._istore)
104 {
105
106 }
107
108 bool
109 ITLess::operator()(UInt32 lhs, UInt32 rhs) const
110 {
111 bool retVal = false;
112
113 IndexStore::const_iterator isIt = _istore.begin();
114 IndexStore::const_iterator isEnd = _istore.end ();
115
116 for(; isIt != isEnd; ++isIt)
117 {
118 UInt32 valL;
119 UInt32 valR;
120 (*isIt)->getValue(valL, lhs);
121 (*isIt)->getValue(valR, rhs);
122
123 if(valL == valR)
124 continue;
125
126 retVal = valL < valR;
127 break;
128 }
129
130 return retVal;
131 }
132
133 std::ostream&
134 ITLess::print(std::ostream &os, UInt32 idx)
135 {
136 IndexStore::const_iterator isIt = _istore.begin();
137 IndexStore::const_iterator isEnd = _istore.end ();
138
139 os << "(";
140 for(; isIt != isEnd; ++isIt)
141 {
142 UInt32 val;
143 (*isIt)->getValue(val, idx);
144 os << val << ", ";
145 }
146 os << ")";
147
148 return os;
149 }
150
151 /* ==================================================================== */
152
153 #if 0 // disabled for now
154 struct ITHash
155 {
156 typedef std::vector<GeoIntegralProperty *> IndexStore;
157
158 explicit ITHash(Geometry *geo);
159
160 std::size_t operator()(UInt32 idx) const;
161
162 Geometry *_geo;
163 IndexStore _istore;
164 };
165
166 /* explicit */
167 ITHash::ITHash(Geometry *geo)
168 : _geo (geo),
169 _istore()
170 {
171 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
172 {
173 GeoIntegralProperty *idx = _geo->getIndex(i);
174 bool add = true;
175
176 if(idx != NULL)
177 {
178 for(UInt32 j = 0; add == true && j < _istore.size(); ++j)
179 {
180 if(idx == _istore[j])
181 add = false;
182 }
183
184 if(add == true)
185 _istore.push_back(idx);
186 }
187 }
188 }
189
190 std::size_t
191 ITHash::operator()(UInt32 idx) const
192 {
193 std::size_t retVal = 0;
194
195 IndexStore::const_iterator isIt = _istore.begin();
196 IndexStore::const_iterator isEnd = _istore.end ();
197
198 for(; isIt != isEnd; ++isIt)
199 {
200 UInt32 val;
201 (*isIt)->getValue(val, idx);
202
203 boost::hash_combine(retVal, val);
204 }
205
206 return retVal;
207 }
208
209 /* ==================================================================== */
210
211 struct ITEqual
212 {
213 typedef std::vector<GeoIntegralProperty *> IndexStore;
214
215 explicit ITEqual(Geometry *geo);
216
217 bool operator()(UInt32 lhs, UInt32 rhs) const;
218
219 Geometry *_geo;
220 IndexStore _istore;
221 };
222
223 /* explicit */
224 ITEqual::ITEqual(Geometry *geo)
225 : _geo (geo),
226 _istore()
227 {
228 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
229 {
230 GeoIntegralProperty *idx = _geo->getIndex(i);
231 bool add = true;
232
233 if(idx != NULL)
234 {
235 for(UInt32 j = 0; add == true && j < _istore.size(); ++j)
236 {
237 if(idx == _istore[j])
238 add = false;
239 }
240
241 if(add == true)
242 _istore.push_back(idx);
243 }
244 }
245 }
246
247 bool
248 ITEqual::operator()(UInt32 lhs, UInt32 rhs) const
249 {
250 bool retVal = true;
251
252 IndexStore::const_iterator isIt = _istore.begin();
253 IndexStore::const_iterator isEnd = _istore.end ();
254
255 for(; isIt != isEnd; ++isIt)
256 {
257 UInt32 valL;
258 UInt32 valR;
259 (*isIt)->getValue(valL, lhs);
260 (*isIt)->getValue(valR, rhs);
261
262 if(valL != valR)
263 {
264 retVal = false;
265 break;
266 }
267 }
268
269 return retVal;
270 }
271 #endif // disabled for now
272
273 typedef std::set<UInt32, ITLess> ITSet;
274 //typedef std::tr1::unordered_set<UInt32, ITHash, ITEqual> ITSet;
275
276 /* ==================================================================== */
277
278 typedef std::vector<OSG::GeoVectorPropertyUnrecPtr > PropertyStore;
279 typedef std::vector<OSG::GeoIntegralPropertyUnrecPtr> PropIndexStore;
280 typedef std::vector<std::pair<UInt32, UInt32> > IndexVec;
281
282 void copyIndices(const PropIndexStore &srcIdx,
283 UInt32 srcOffset,
284 const PropIndexStore &dstIdx,
285 UInt32 dstOffset,
286 UInt32 count = 1 )
287 {
288 OSG_ASSERT(srcIdx.size() == dstIdx.size());
289
290 for(UInt32 i = 0; i < srcIdx.size(); ++i)
291 {
292 if(dstIdx[i]->size() < (dstOffset + count))
293 dstIdx[i]->resize(dstOffset + count);
294
295 for(UInt32 j = 0; j < count; ++j)
296 {
297 GeoIntegralProperty::MaxTypeT val;
298 srcIdx[i]->getValue(val, srcOffset + j);
299 dstIdx[i]->setValue(val, dstOffset + j);
300 }
301 }
302 }
303
304 void copyIndexSet(const PropIndexStore &srcIdx,
305 const std::vector<UInt32> &srcIndices,
306 const PropIndexStore &dstIdx,
307 UInt32 dstOffset)
308 {
309 OSG_ASSERT(srcIdx.size() == dstIdx.size());
310
311 UInt32 count = srcIndices.size();
312
313 for(UInt32 i = 0; i < srcIdx.size(); ++i)
314 {
315 if(dstIdx[i]->size() < (dstOffset + count))
316 dstIdx[i]->resize(dstOffset + count);
317
318 for(UInt32 j = 0; j < count; ++j)
319 {
320 GeoIntegralProperty::MaxTypeT val;
321
322 srcIdx[i]->getValue(val, srcIndices[j]);
323 dstIdx[i]->setValue(val, dstOffset + j);
324 }
325 }
326 }
327
328 Real32 polyArea(GeoVectorProperty *pPos,
329 IndexVec &vPolyIndex,
330 Int32 len,
331 UInt32 uiXIdx,
332 UInt32 uiYIdx )
333 {
334 float A = 0.0f;
335
336 Pnt3f oPntP;
337 Pnt3f oPntQ;
338
339 for(Int32 p = len - 1, q = 0; q < len; p = q++)
340 {
341 pPos->getValue(oPntP, vPolyIndex[p].first);
342 pPos->getValue(oPntQ, vPolyIndex[q].first);
343
344 A += oPntP[uiXIdx] * oPntQ[uiYIdx] - oPntQ[uiXIdx] * oPntP[uiYIdx];
345 }
346
347 return A*0.5f;
348 }
349
350 /* InsideTriangle decides if a point P is Inside of the triangle
351 defined by A, B, C.
352 */
353
354 bool InsideTriangle(Real32 Ax, Real32 Ay,
355 Real32 Bx, Real32 By,
356 Real32 Cx, Real32 Cy,
357 Real32 Px, Real32 Py)
358
359 {
360 Real32 ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
361 Real32 cCROSSap, bCROSScp, aCROSSbp;
362
363 ax = Cx - Bx; ay = Cy - By;
364 bx = Ax - Cx; by = Ay - Cy;
365 cx = Bx - Ax; cy = By - Ay;
366 apx= Px - Ax; apy= Py - Ay;
367 bpx= Px - Bx; bpy= Py - By;
368 cpx= Px - Cx; cpy= Py - Cy;
369
370 aCROSSbp = ax * bpy - ay * bpx;
371 cCROSSap = cx * apy - cy * apx;
372 bCROSScp = bx * cpy - by * cpx;
373
374 return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
375 }
376
377 static const float EPSILON = 0.0000000001f;
378
379 bool Snip(GeoVectorProperty *pPos,
380 IndexVec &vPolyIndex,
381 Int32 u,
382 Int32 v,
383 Int32 w,
384 Int32 n,
385 UInt32 uiXIdx,
386 UInt32 uiYIdx )
387 {
388 Int32 p;
389 Real32 Ax, Ay, Bx, By, Cx, Cy, Px, Py;
390
391 Pnt3f oPnt;
392
393 pPos->getValue(oPnt, vPolyIndex[u].first);
394
395 Ax = oPnt[uiXIdx];
396 Ay = oPnt[uiYIdx];
397
398 pPos->getValue(oPnt, vPolyIndex[v].first);
399
400 Bx = oPnt[uiXIdx];
401 By = oPnt[uiYIdx];
402
403 pPos->getValue(oPnt, vPolyIndex[w].first);
404
405 Cx = oPnt[uiXIdx];
406 Cy = oPnt[uiYIdx];
407
408 if(EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax))))
409 return false;
410
411 for(p = 0; p < n; ++p)
412 {
413 if((p == u) || (p == v) || (p == w))
414 continue;
415
416 pPos->getValue(oPnt, vPolyIndex[p].first);
417
418 Px = oPnt[uiXIdx];
419 Py = oPnt[uiYIdx];
420
421 if(InsideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py))
422 return false;
423 }
424
425 return true;
426 }
427
428 // Simple polygon triangulation, base on
429 // http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
430 // from John W. Ratcliff
431
432 UInt32 triangulatePoly( IndexVec &vPolyIndex,
433 const PropIndexStore &srcIdx,
434 const PropIndexStore &dstIdx,
435 UInt32 &dstOffset,
436 UInt32 len,
437 Geometry *pGeo )
438 {
439 OSG_ASSERT(len >= 3 && pGeo != NULL);
440
441 GeoVectorProperty *pPos = pGeo->getProperty(Geometry::PositionsIndex);
442
443 // figure out the coordinate plane to use:
444
445 Pnt3f oP0;
446 Pnt3f oP1;
447 Pnt3f oP2;
448
449 pPos->getValue(oP0, vPolyIndex[0].first);
450 pPos->getValue(oP1, vPolyIndex[1].first);
451 pPos->getValue(oP2, vPolyIndex[2].first);
452
453 Vec3f oE0 = oP1 - oP0;
454 Vec3f oE1 = oP2 - oP0;
455
456 Vec3f oN = oE0.cross(oE1);
457 UInt32 uiMaxIdx = oN.maxDimAbs();
458
459 UInt32 uiXIdx = 0;
460 UInt32 uiYIdx = 1;
461
462 if(uiMaxIdx == 0)
463 {
464 uiXIdx = 1;
465 uiYIdx = 2;
466 }
467 else if(uiMaxIdx == 1)
468 {
469 uiYIdx = 2;
470 }
471
472 Real32 fArea = polyArea(pPos,
473 vPolyIndex,
474 len,
475 uiXIdx,
476 uiYIdx);
477
478 bool bReversed = false;
479
480 if(fArea < 0.f)
481 {
482 std::reverse(vPolyIndex.begin(), vPolyIndex.end());
483
484 bReversed = true;
485 }
486
487 Int32 nv = len;
488
489 /* remove nv-2 Vertices, creating 1 triangle every time */
490 Int32 count = 2 * nv; /* error detection */
491
492 std::vector<UInt32> vTriIndices;
493
494 vTriIndices.resize(3);
495
496 UInt32 returnValue = 0;
497
498 for(Int32 m = 0, v = nv - 1; nv > 2;)
499 {
500
501 /* if we loop, it is probably a non-simple polygon */
502 if(0 >= (count--))
503 {
504 //** Triangulate: ERROR - probable bad polygon!
505 return 0;
506 }
507
508 /* three consecutive vertices in current polygon, <u,v,w> */
509 Int32 u = v;
510
511 if (nv <= u)
512 u = 0; /* previous */
513
514 v = u + 1;
515
516 if (nv <= v)
517 v = 0; /* new v */
518
519 Int32 w = v + 1;
520
521 if(nv <= w)
522 w = 0; /* next */
523
524 if(Snip(pPos,
525 vPolyIndex,
526 u, v, w,
527 nv,
528 uiXIdx,
529 uiYIdx) )
530 {
531 vTriIndices[0] = vPolyIndex[u].second;
532
533 if(bReversed == false)
534 {
535 vTriIndices[1] = vPolyIndex[v].second;
536 vTriIndices[2] = vPolyIndex[w].second;
537 }
538 else
539 {
540 vTriIndices[1] = vPolyIndex[w].second;
541 vTriIndices[2] = vPolyIndex[v].second;
542 }
543
544 copyIndexSet(srcIdx,
545 vTriIndices,
546 dstIdx,
547 dstOffset );
548
549 dstOffset += 3;
550
551 ++returnValue;
552 ++m;
553
554 /* remove v from remaining polygon */
555 for(Int32 s = v, t = v + 1; t < nv; ++s, ++t)
556 vPolyIndex[s] = vPolyIndex[t];
557
558 --nv;
559
560 /* resest error detection counter */
561 count = 2 * nv;
562 }
563 }
564
565 return returnValue;
566 }
567
568 } // namespace
569
570
571 /* ======================================================================== */
572
573 /*! Modifies the Geometry \a geo to use a single index for all
574 properties.
575
576 This creates new GeoVectorProperties (of the same type) for all
577 properties and creates a new index. The geometry must be (multi) indexed.
578 */
579
580 void
581 makeSingleIndexed(Geometry *geo)
582 {
583 if(geo->isSingleIndex() == true)
584 {
585 SINFO << "Geometry is already single indexed, nothing to do."
586 << std::endl;
587 return;
588 }
589
590 bool hasIndex = false;
591
592 for(UInt32 i = 0; i <= Geometry::LastIndex; ++i)
593 {
594 if(geo->getIndex(i) != NULL)
595 {
596 hasIndex = true;
597 break;
598 }
599 }
600
601 if(hasIndex == false)
602 {
603 SWARNING << "No index found, aborting."
604 << std::endl;
605 return;
606 }
607
608 // 1) compute the set of unique index tuples
609 // itSet contains the offset into the geo's indices
610 // for unique index tuples
611 // index contains the new offset for a index tuple
612 //
613 // 0* 1* 2* 3 4 5* 6 7 8* *'ed elements are in itSet
614 //
615 // x x x x x x x x x idx for prop 0
616 // 0 1 2 2 1 3 2 3 4 idx for prop 1
617 // x x x x x x x x x idx for prop 2
618 //
619 // 0 1 2 2 1 3 2 3 4 contents of index
620 //
621 // the comparison function object used for itSet is what
622 // enables the detection of duplicate index tuples
623
624 #if defined(OSG_GEOOPT_STATISTICS)
625 Time start1 = getSystemTime();
626 #endif
627
628 typedef std::vector<UInt32> IndexUI32;
629
630 ITSet itSet((ITLess(geo)));
631 //ITSet itSet(10, ITHash(geo), ITEqual(geo));
632 IndexUI32 index;
633
634 GeoIntegralProperty *lengths = geo->getLengths();
635 UInt32 lengthsN = lengths->size32();
636 UInt32 k = 0;
637
638 for(UInt32 i = 0; i < lengthsN; ++i)
639 {
640 UInt32 len;
641 lengths->getValue(len, i);
642
643 for(UInt32 j = 0; j < len; ++j)
644 {
645 ITSet::const_iterator isIt = itSet.find(k);
646
647 if(isIt != itSet.end())
648 {
649 // already encountered index tuple
650 index.push_back(index[*isIt]);
651 }
652 else
653 {
654 // new unique index tuple
655 index.push_back(UInt32(itSet.size()));
656 itSet.insert(k);
657 }
658
659 ++k;
660 }
661 }
662
663 #if defined(OSG_GEOOPT_STATISTICS)
664 SLOG << "time to compute unique index tuples: " << (getSystemTime() - start1)
665 << std::endl;
666
667 Time start2 = getSystemTime();
668 #endif
669
670 // 2) rewrite properties
671 //
672 // For existing propery propN and its index propNIdx we
673 // fill the new proprty newPropN.
674 // index[*isIt] is the unique index tuple number for *isIt
675 //
676 // newPropN[index[*isIt]] = propN[propNIdx[*isIt]]
677
678 PropertyStore prop;
679 PropertyStore newProp;
680 PropIndexStore propIdx;
681
682 // create new properties
683 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
684 {
685 if(geo->getProperty(i) != NULL)
686 {
687 bool add = true;
688
689 for(UInt32 j = 0; add == true && j < prop.size(); ++j)
690 {
691 if(prop[j] == geo->getProperty(i))
692 add = false;
693 }
694
695 if(add == true)
696 {
697 // property present, but no index?
698 OSG_ASSERT(geo->getIndex(i) != NULL);
699
700 prop .push_back(geo->getProperty(i));
701 propIdx.push_back(geo->getIndex (i));
702
703 // create new propery of same type
704 GeoVectorPropertyUnrecPtr np =
705 dynamic_pointer_cast<GeoVectorProperty>(
706 geo->getProperty(i)->getType().createContainer());
707 np->resize(itSet.size());
708
709 newProp.push_back(np);
710 }
711 }
712 }
713
714 // fill new properties
715 UInt32 propCount = UInt32(prop.size());
716
717 ITSet::const_iterator isIt = itSet.begin();
718 ITSet::const_iterator isEnd = itSet.end ();
719
720 for(; isIt != isEnd; ++isIt)
721 {
722 for(UInt32 i = 0; i < propCount; ++i)
723 {
724 GeoIntegralProperty::MaxTypeT idx;
725 GeoVectorProperty ::MaxTypeT val;
726
727 propIdx[i]->getValue(idx, *isIt);
728 prop[i] ->getValue(val, idx );
729
730 newProp[i]->setValue(val, index[*isIt]);
731 }
732 }
733
734 // create new index
735 GeoUInt32PropertyUnrecPtr newIdx = GeoUInt32Property::create();
736 newIdx->editFieldPtr()->insert(
737 newIdx->editFieldPtr()->begin(),
738 index.begin(), index.end() );
739
740 // set new properties and index on geometry
741 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
742 {
743 if(geo->getProperty(i) != NULL)
744 {
745 for(UInt32 j = 0; j < prop.size(); ++j)
746 {
747 if(prop[j] == geo->getProperty(i))
748 {
749 geo->setProperty(newProp[j], i);
750 break;
751 }
752 }
753
754 geo->setIndex(newIdx, i);
755 }
756 else
757 {
758 geo->setIndex(NULL, i);
759 }
760 }
761
762 #if defined(OSG_GEOOPT_STATISTICS)
763 SLOG << "time to rewrite properties: " << (getSystemTime() - start2)
764 << std::endl;
765 #endif
766 }
767
768 /* ======================================================================== */
769
770 /*! Converts all "face" primitives (triangles strips/fans, quads, quad strips,
771 polygons) to triangle lists.
772
773 This modifies the types and lengths of the geometry and replaces indices
774 with new ones.
775
776 Assumes valid OpenGL conforming convex primitives
777 */
778
779 void makeIndexedTriangles(Geometry *geo,
780 bool bKeepLowerDimPrimitives)
781 {
782 #if defined(OSG_GEOOPT_STATISTICS)
783 Time start = getSystemTime();
784 #endif
785
786 // 1) find unique index properties used by the geometry and create
787 // new ones of the same size (if necessary the new indices are
788 // grown by the copyIndices() helper function)
789
790 PropIndexStore oldIdx;
791 PropIndexStore newIdx;
792
793 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
794 {
795 if(geo->getIndex(i) != NULL)
796 {
797 bool add = true;
798
799 for(UInt32 j = 0; add == true && j < oldIdx.size(); ++j)
800 {
801 if(geo->getIndex(i) == oldIdx[j])
802 add = false;
803 }
804
805 if(add == true)
806 {
807 oldIdx.push_back(geo->getIndex(i));
808
809 newIdx.push_back(GeoUInt32Property::create());
810 newIdx.back()->resize(oldIdx.back()->size());
811 }
812 }
813 }
814
815 GeoIntegralProperty *oldTypes = geo->getTypes ();
816 GeoIntegralProperty *oldLengths = geo->getLengths();
817
818 if(oldTypes->size() != oldLengths->size())
819 {
820 SWARNING << "Types and Lengths have inconsistent size, aborting."
821 << std::endl;
822 return;
823 }
824
825 // 2a) loop over all primitives first copying those that can
826 // not be converted to GL_TRIANGLES (e.g. lines, points,
827 // unknown primitives).
828 // This allows group all primitives that can be converted
829 // to be grouped into one GL_TRIANGLES primitive at
830 // the end.
831
832 GeoIntegralPropertyUnrecPtr newTypes =
833 dynamic_pointer_cast<GeoIntegralProperty>(
834 oldTypes->getType().createContainer());
835 GeoIntegralPropertyUnrecPtr newLengths =
836 dynamic_pointer_cast<GeoIntegralProperty>(
837 oldLengths->getType().createContainer());
838
839 bool doSecondPass = false;
840 UInt32 primCount = oldTypes->size32();
841 UInt32 srcOffset = 0;
842 UInt32 dstOffset = 0;
843
844 if(bKeepLowerDimPrimitives == true)
845 {
846 for(UInt32 i = 0; i < primCount; ++i)
847 {
848 UInt32 type = oldTypes ->getValue(i);
849 UInt32 len = oldLengths->getValue(i);
850
851 switch(type)
852 {
853 case GL_POINTS:
854 case GL_LINES:
855 case GL_LINE_LOOP:
856 case GL_LINE_STRIP:
857 {
858 // not a "face" primitive, copy indices unchanged
859 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, len);
860 srcOffset += len;
861 dstOffset += len;
862
863 newTypes ->push_back(type);
864 newLengths->push_back(len );
865 }
866 break;
867
868 case GL_TRIANGLES:
869 case GL_TRIANGLE_STRIP:
870 case GL_TRIANGLE_FAN:
871 case GL_POLYGON:
872 case GL_QUADS:
873 case GL_QUAD_STRIP:
874 {
875 // these can be converted, we handle them later
876 doSecondPass = true;
877 }
878 break;
879
880 default:
881 {
882 // unknown primitive, copy indices unchanged
883 SWARNING << "Unknown primitive type " << type
884 << " copying indices unchanged." << std::endl;
885 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, len);
886 srcOffset += len;
887 dstOffset += len;
888
889 newTypes ->push_back(type);
890 newLengths->push_back(len );
891 }
892 break;
893 }
894 }
895 }
896 else
897 {
898 doSecondPass = true;
899 }
900
901 // 2b) if we encountered any primitive that can be converted,
902 // do a second pass over all primitives handling only the
903 // ones that can be converted.
904
905 if(doSecondPass == true)
906 {
907 GLenum lastPrim = GL_NONE;
908
909 for(UInt32 i = 0; i < primCount; ++i)
910 {
911 UInt32 lengthsCount = newLengths->size32();
912 UInt32 type = oldTypes ->getValue(i);
913 UInt32 len = oldLengths->getValue(i);
914
915 switch(type)
916 {
917 case GL_TRIANGLES:
918 {
919 // already tris, copy indices unchanged
920 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, len);
921 srcOffset += len;
922 dstOffset += len;
923
924 if(lastPrim == GL_TRIANGLES)
925 {
926 newLengths->setValue(
927 newLengths->getValue(lengthsCount - 1) + len,
928 lengthsCount - 1);
929 }
930 else
931 {
932 newTypes ->push_back(GL_TRIANGLES);
933 newLengths->push_back(len);
934 lastPrim = GL_TRIANGLES;
935 }
936 }
937 break;
938 case GL_TRIANGLE_STRIP:
939 {
940 if(len < 3)
941 {
942 SWARNING << "Encountered degenerate TRIANGLE_STRIP,"
943 << " aborting."
944 << std::endl;
945 return;
946 }
947 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, 3);
948 srcOffset += 3;
949 dstOffset += 3;
950
951 for(UInt32 j = 3; j < len; ++j)
952 {
953 if(j % 2 == 0)
954 {
955 copyIndices(oldIdx, srcOffset-2, newIdx, dstOffset );
956 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset+1);
957 copyIndices(oldIdx, srcOffset, newIdx, dstOffset+2);
958 }
959 else
960 {
961 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset );
962 copyIndices(oldIdx, srcOffset-2, newIdx, dstOffset+1);
963 copyIndices(oldIdx, srcOffset, newIdx, dstOffset+2);
964 }
965
966 srcOffset += 1;
967 dstOffset += 3;
968 }
969
970 if(lastPrim == GL_TRIANGLES)
971 {
972 newLengths->setValue(
973 newLengths->getValue(lengthsCount - 1) + 3 * (len - 2),
974 lengthsCount - 1);
975 }
976 else
977 {
978 newTypes ->push_back(GL_TRIANGLES);
979 newLengths->push_back(3 * (len - 2));
980 lastPrim = GL_TRIANGLES;
981 }
982 }
983 break;
984 case GL_TRIANGLE_FAN:
985 case GL_POLYGON:
986 {
987 if(len < 3)
988 {
989 SWARNING << "Encountered degenerate TRIANGLE_FAN "
990 << "or POLYGON, aborting."
991 << std::endl;
992 return;
993 }
994 UInt32 firstSrcOffset = srcOffset;
995 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, 3);
996 srcOffset += 3;
997 dstOffset += 3;
998
999 for(UInt32 j = 3; j < len; ++j)
1000 {
1001 copyIndices(oldIdx, firstSrcOffset, newIdx, dstOffset );
1002 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset+1);
1003 copyIndices(oldIdx, srcOffset, newIdx, dstOffset+2);
1004
1005 srcOffset += 1;
1006 dstOffset += 3;
1007 }
1008
1009 if(lastPrim == GL_TRIANGLES)
1010 {
1011 newLengths->setValue(
1012 newLengths->getValue(lengthsCount - 1) + 3 * (len - 2),
1013 lengthsCount - 1);
1014 }
1015 else
1016 {
1017 newTypes ->push_back(GL_TRIANGLES);
1018 newLengths->push_back(3 * (len - 2));
1019 lastPrim = GL_TRIANGLES;
1020 }
1021 }
1022 break;
1023 case GL_QUADS:
1024 {
1025 if(len < 4 || len % 4 != 0)
1026 {
1027 SWARNING << "Encountered degenerate QUADS, aborting."
1028 << std::endl;
1029 return;
1030 }
1031 for(UInt32 j = 0; j < len / 4; ++j)
1032 {
1033 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, 3);
1034 srcOffset += 3;
1035 dstOffset += 3;
1036 copyIndices(oldIdx, srcOffset-3, newIdx, dstOffset );
1037 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset+1);
1038 copyIndices(oldIdx, srcOffset, newIdx, dstOffset+2);
1039 srcOffset += 1;
1040 dstOffset += 3;
1041 }
1042
1043 if(lastPrim == GL_TRIANGLES)
1044 {
1045 newLengths->setValue(
1046 newLengths->getValue(lengthsCount - 1) + 3 * (len / 2),
1047 lengthsCount - 1);
1048 }
1049 else
1050 {
1051 newTypes ->push_back(GL_TRIANGLES);
1052 newLengths->push_back(3 * (len / 2));
1053 lastPrim = GL_TRIANGLES;
1054 }
1055 }
1056 break;
1057 case GL_QUAD_STRIP:
1058 {
1059 if(len < 4 || len % 2 != 0)
1060 {
1061 SWARNING << "Encountered degenerate QUAD_STRIP, aborting."
1062 << std::endl;
1063 return;
1064 }
1065 copyIndices(oldIdx, srcOffset, newIdx, dstOffset );
1066 copyIndices(oldIdx, srcOffset+2, newIdx, dstOffset+1);
1067 copyIndices(oldIdx, srcOffset+1, newIdx, dstOffset+2);
1068 srcOffset += 1;
1069 dstOffset += 3;
1070 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, 3);
1071 srcOffset += 3;
1072 dstOffset += 3;
1073
1074 for(UInt32 j = 4; j < len; j += 2)
1075 {
1076 copyIndices(oldIdx, srcOffset-2, newIdx, dstOffset );
1077 copyIndices(oldIdx, srcOffset, newIdx, dstOffset+1);
1078 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset+2);
1079 dstOffset += 3;
1080 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset, 3);
1081 srcOffset += 2;
1082 dstOffset += 3;
1083 }
1084
1085 if(lastPrim == GL_TRIANGLES)
1086 {
1087 newLengths->setValue(
1088 newLengths->getValue(lengthsCount - 1) + 3 * (len - 2),
1089 lengthsCount - 1);
1090 }
1091 else
1092 {
1093 newTypes ->push_back(GL_TRIANGLES);
1094 newLengths->push_back(3 * (len - 2));
1095 lastPrim = GL_TRIANGLES;
1096 }
1097 }
1098 break;
1099 }
1100 }
1101 }
1102
1103 geo->setTypes (newTypes );
1104 geo->setLengths(newLengths);
1105
1106 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
1107 {
1108 if(geo->getIndex(i) != NULL)
1109 {
1110 for(UInt32 j = 0; j < oldIdx.size(); ++j)
1111 {
1112 if(geo->getIndex(i) == oldIdx[j])
1113 {
1114 geo->setIndex(newIdx[j], i);
1115 break;
1116 }
1117 }
1118 }
1119 }
1120
1121 #if defined(OSG_GEOOPT_STATISTICS)
1122 SLOG << "time to rewrite types/len/indices: " << (getSystemTime() - start)
1123 << std::endl;
1124 #endif
1125 }
1126
1127 /* checks and creates explicit index properties if not present */
1128
1129 void createExplicitIndex(Geometry *geo)
1130 {
1131 bool hasIndex = false;
1132
1133 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
1134 {
1135 if(geo->getIndex(i) != NULL)
1136 {
1137 hasIndex = true;
1138 break;
1139 }
1140 }
1141
1142 if(hasIndex == false)
1143 {
1144 GeoVectorProperty *pPos = geo->getProperty(Geometry::PositionsIndex);
1145
1146 if(pPos == NULL)
1147 {
1148 fprintf(stderr, "no positions, abort\n");
1149 return;
1150 }
1151
1152 GeoUInt32PropertyUnrecPtr pNewIdx = GeoUInt32Property::create();
1153
1154 pNewIdx->editField().reserve(pPos->size());
1155
1156 for(SizeT i = 0; i < pPos->size(); ++i)
1157 {
1158 pNewIdx->push_back(i);
1159 }
1160
1161 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
1162 {
1163 if(geo->getProperty(i) != NULL)
1164 {
1165 if(geo->getProperty(i)->size() != pPos->size())
1166 {
1167 SWARNING << "inconsitent property sizes, interesting "
1168 << "things might happen ;)"
1169 << std::endl;
1170 }
1171
1172 geo->setIndex(pNewIdx, i);
1173 }
1174 }
1175 }
1176
1177 }
1178
1179 /*! Converts all "face" primitives (triangles strips/fans, quads, quad strips,
1180 polygons) to triangle lists.
1181
1182 This modifies the types and lengths of the geometry and replaces indices
1183 with new ones.
1184
1185 Does not assume valid, OpenGL conforming convex GL_POLYGON and GL_QUADS
1186 primitives.
1187
1188 GL_QUAD_STRIPs are assumed to contain convex primitives.
1189 */
1190
1191 void makeIndexedTrianglesConcave(Geometry *geo,
1192 bool bKeepLowerDimPrimitives)
1193 {
1194 #if defined(OSG_GEOOPT_STATISTICS)
1195 Time start = getSystemTime();
1196 #endif
1197
1198 // 1) find unique index properties used by the geometry and create
1199 // new ones of the same size (if necessary the new indices are
1200 // grown by the copyIndices() helper function)
1201
1202 PropIndexStore oldIdx;
1203 PropIndexStore newIdx;
1204
1205 createExplicitIndex(geo);
1206
1207 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
1208 {
1209 if(geo->getIndex(i) != NULL)
1210 {
1211 bool add = true;
1212
1213 for(UInt32 j = 0; add == true && j < oldIdx.size(); ++j)
1214 {
1215 if(geo->getIndex(i) == oldIdx[j])
1216 add = false;
1217 }
1218
1219 if(add == true)
1220 {
1221 oldIdx.push_back(geo->getIndex(i));
1222
1223 newIdx.push_back(GeoUInt32Property::create());
1224 newIdx.back()->resize(oldIdx.back()->size());
1225 }
1226 }
1227 }
1228
1229 GeoIntegralProperty *oldTypes = geo->getTypes ();
1230 GeoIntegralProperty *oldLengths = geo->getLengths();
1231
1232 if(oldTypes == NULL || oldLengths == NULL)
1233 {
1234 SWARNING << "Either no Types and Lengths, aborting."
1235 << std::endl;
1236 return;
1237 }
1238
1239 if(oldTypes->size() != oldLengths->size())
1240 {
1241 SWARNING << "Types and Lengths have inconsistent size, aborting."
1242 << std::endl;
1243 return;
1244 }
1245
1246 // 2a) loop over all primitives first copying those that can
1247 // not be converted to GL_TRIANGLES (e.g. lines, points,
1248 // unknown primitives).
1249 // This allows group all primitives that can be converted
1250 // to be grouped into one GL_TRIANGLES primitive at
1251 // the end.
1252
1253 GeoIntegralPropertyUnrecPtr newTypes =
1254 dynamic_pointer_cast<GeoIntegralProperty>(
1255 oldTypes->getType().createContainer());
1256 GeoIntegralPropertyUnrecPtr newLengths =
1257 dynamic_pointer_cast<GeoIntegralProperty>(
1258 oldLengths->getType().createContainer());
1259
1260 bool doSecondPass = false;
1261 UInt32 primCount = oldTypes->size32();
1262 UInt32 srcOffset = 0;
1263 UInt32 dstOffset = 0;
1264
1265 if(bKeepLowerDimPrimitives == true)
1266 {
1267 for(UInt32 i = 0; i < primCount; ++i)
1268 {
1269 UInt32 type = oldTypes ->getValue(i);
1270 UInt32 len = oldLengths->getValue(i);
1271
1272 switch(type)
1273 {
1274 case GL_POINTS:
1275 case GL_LINES:
1276 case GL_LINE_LOOP:
1277 case GL_LINE_STRIP:
1278 {
1279 // not a "face" primitive, copy indices unchanged
1280 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, len);
1281 srcOffset += len;
1282 dstOffset += len;
1283
1284 newTypes ->push_back(type);
1285 newLengths->push_back(len );
1286 }
1287 break;
1288
1289 case GL_TRIANGLES:
1290 case GL_TRIANGLE_STRIP:
1291 case GL_TRIANGLE_FAN:
1292 case GL_POLYGON:
1293 case GL_QUADS:
1294 case GL_QUAD_STRIP:
1295 {
1296 // these can be converted, we handle them later
1297 doSecondPass = true;
1298 }
1299 break;
1300
1301 default:
1302 {
1303 // unknown primitive, copy indices unchanged
1304 SWARNING << "Unknown primitive type " << type
1305 << " copying indices unchanged." << std::endl;
1306 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, len);
1307 srcOffset += len;
1308 dstOffset += len;
1309
1310 newTypes ->push_back(type);
1311 newLengths->push_back(len );
1312 }
1313 break;
1314 }
1315 }
1316 }
1317 else
1318 {
1319 doSecondPass = true;
1320 }
1321
1322 // 2b) if we encountered any primitive that can be converted,
1323 // do a second pass over all primitives handling only the
1324 // ones that can be converted.
1325
1326 if(doSecondPass == true)
1327 {
1328 GLenum lastPrim = GL_NONE;
1329
1330 IndexVec vPolyIndex;
1331
1332 for(UInt32 i = 0; i < primCount; ++i)
1333 {
1334 UInt32 lengthsCount = newLengths->size32();
1335 UInt32 type = oldTypes ->getValue(i);
1336 UInt32 len = oldLengths->getValue(i);
1337
1338 switch(type)
1339 {
1340 case GL_TRIANGLES:
1341 {
1342 // already tris, copy indices unchanged
1343 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, len);
1344 srcOffset += len;
1345 dstOffset += len;
1346
1347 if(lastPrim == GL_TRIANGLES)
1348 {
1349 newLengths->setValue(
1350 newLengths->getValue(lengthsCount - 1) + len,
1351 lengthsCount - 1);
1352 }
1353 else
1354 {
1355 newTypes ->push_back(GL_TRIANGLES);
1356 newLengths->push_back(len);
1357 lastPrim = GL_TRIANGLES;
1358 }
1359 }
1360 break;
1361
1362 case GL_TRIANGLE_STRIP:
1363 {
1364 if(len < 3)
1365 {
1366 SWARNING << "Encountered degenerate TRIANGLE_STRIP,"
1367 << " aborting."
1368 << std::endl;
1369 return;
1370 }
1371 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, 3);
1372 srcOffset += 3;
1373 dstOffset += 3;
1374
1375 for(UInt32 j = 3; j < len; ++j)
1376 {
1377 if(j % 2 == 0)
1378 {
1379 copyIndices(oldIdx, srcOffset-2,
1380 newIdx, dstOffset );
1381 copyIndices(oldIdx, srcOffset-1,
1382 newIdx, dstOffset+1);
1383 copyIndices(oldIdx, srcOffset,
1384 newIdx, dstOffset+2);
1385 }
1386 else
1387 {
1388 copyIndices(oldIdx, srcOffset-1,
1389 newIdx, dstOffset );
1390 copyIndices(oldIdx, srcOffset-2,
1391 newIdx, dstOffset+1);
1392 copyIndices(oldIdx, srcOffset,
1393 newIdx, dstOffset+2);
1394 }
1395
1396 srcOffset += 1;
1397 dstOffset += 3;
1398 }
1399
1400 if(lastPrim == GL_TRIANGLES)
1401 {
1402 newLengths->setValue(
1403 newLengths->getValue(
1404 lengthsCount - 1) + 3 * (len - 2),
1405 lengthsCount - 1);
1406 }
1407 else
1408 {
1409 newTypes ->push_back(GL_TRIANGLES);
1410 newLengths->push_back(3 * (len - 2));
1411 lastPrim = GL_TRIANGLES;
1412 }
1413 }
1414 break;
1415
1416 case GL_TRIANGLE_FAN:
1417 {
1418 if(len < 3)
1419 {
1420 SWARNING << "Encountered degenerate TRIANGLE_FAN, "
1421 << "aborting."
1422 << std::endl;
1423 return;
1424 }
1425
1426 UInt32 firstSrcOffset = srcOffset;
1427 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, 3);
1428 srcOffset += 3;
1429 dstOffset += 3;
1430
1431 for(UInt32 j = 3; j < len; ++j)
1432 {
1433 copyIndices(oldIdx, firstSrcOffset,
1434 newIdx, dstOffset );
1435 copyIndices(oldIdx, srcOffset-1,
1436 newIdx, dstOffset+1);
1437 copyIndices(oldIdx, srcOffset,
1438 newIdx, dstOffset+2);
1439
1440 srcOffset += 1;
1441 dstOffset += 3;
1442 }
1443
1444 if(lastPrim == GL_TRIANGLES)
1445 {
1446 newLengths->setValue(
1447 newLengths->getValue(
1448 lengthsCount - 1) + 3 * (len - 2),
1449 lengthsCount - 1);
1450 }
1451 else
1452 {
1453 newTypes ->push_back(GL_TRIANGLES);
1454 newLengths->push_back(3 * (len - 2));
1455 lastPrim = GL_TRIANGLES;
1456 }
1457 }
1458 break;
1459
1460 case GL_POLYGON:
1461 {
1462 if(len < 3)
1463 {
1464 SWARNING << "Encountered degenerate "
1465 << "POLYGON, aborting."
1466 << std::endl;
1467 return;
1468 }
1469
1470 vPolyIndex.resize(len);
1471
1472 for(UInt32 j = 0; j < len; ++j)
1473 {
1474 oldIdx[0]->getValue(vPolyIndex[j].first, srcOffset + j);
1475
1476 vPolyIndex[j].second = srcOffset + j;
1477 }
1478
1479 UInt32 res = triangulatePoly(vPolyIndex,
1480
1481 oldIdx,
1482
1483 newIdx,
1484 dstOffset,
1485
1486 len,
1487 geo );
1488
1489 srcOffset += len;
1490
1491 if(lastPrim == GL_TRIANGLES)
1492 {
1493 newLengths->setValue(
1494 newLengths->getValue(
1495 lengthsCount - 1) + 3 * res,
1496 lengthsCount - 1);
1497 }
1498 else
1499 {
1500 newTypes ->push_back(GL_TRIANGLES);
1501 newLengths->push_back(3 * res);
1502 lastPrim = GL_TRIANGLES;
1503 }
1504 }
1505 break;
1506
1507 case GL_QUADS:
1508 {
1509 if((len < 4 || len % 4 != 0))
1510 {
1511 SWARNING << "Encountered degenerate QUADS, aborting."
1512 << std::endl;
1513 return;
1514 }
1515
1516 vPolyIndex.resize(4);
1517
1518 for(UInt32 k = 0; k < len; k += 4)
1519 {
1520 for(UInt32 j = 0; j < 4; ++j)
1521 {
1522 oldIdx[0]->getValue(vPolyIndex[j].first,
1523 srcOffset + j);
1524
1525 vPolyIndex[j].second = srcOffset + j;
1526 }
1527
1528 UInt32 res = triangulatePoly(vPolyIndex,
1529
1530 oldIdx,
1531
1532 newIdx,
1533 dstOffset,
1534
1535 4,
1536 geo );
1537
1538 srcOffset += 4;
1539
1540 if(lastPrim == GL_TRIANGLES)
1541 {
1542 newLengths->setValue(
1543 newLengths->getValue(
1544 lengthsCount - 1) + 3 * res,
1545 lengthsCount - 1);
1546 }
1547 else
1548 {
1549 newTypes ->push_back(GL_TRIANGLES);
1550 newLengths->push_back(3 * res);
1551 lastPrim = GL_TRIANGLES;
1552 }
1553
1554 lengthsCount = newLengths->size32();
1555 }
1556 }
1557 break;
1558
1559 case GL_QUAD_STRIP:
1560 {
1561 if(len < 4 || len % 2 != 0)
1562 {
1563 SWARNING << "Encountered degenerate QUAD_STRIP, "
1564 << "aborting."
1565 << std::endl;
1566 return;
1567 }
1568
1569 copyIndices(oldIdx, srcOffset, newIdx, dstOffset );
1570 copyIndices(oldIdx, srcOffset+2, newIdx, dstOffset+1);
1571 copyIndices(oldIdx, srcOffset+1, newIdx, dstOffset+2);
1572 srcOffset += 1;
1573 dstOffset += 3;
1574 copyIndices(oldIdx, srcOffset, newIdx, dstOffset, 3);
1575 srcOffset += 3;
1576 dstOffset += 3;
1577
1578 for(UInt32 j = 4; j < len; j += 2)
1579 {
1580 copyIndices(oldIdx, srcOffset-2, newIdx, dstOffset );
1581 copyIndices(oldIdx, srcOffset, newIdx, dstOffset+1);
1582 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset+2);
1583 dstOffset += 3;
1584 copyIndices(oldIdx, srcOffset-1, newIdx, dstOffset, 3);
1585 srcOffset += 2;
1586 dstOffset += 3;
1587 }
1588
1589 if(lastPrim == GL_TRIANGLES)
1590 {
1591 newLengths->setValue(
1592 newLengths->getValue(
1593 lengthsCount - 1) + 3 * (len - 2),
1594 lengthsCount - 1);
1595 }
1596 else
1597 {
1598 newTypes ->push_back(GL_TRIANGLES);
1599 newLengths->push_back(3 * (len - 2));
1600 lastPrim = GL_TRIANGLES;
1601 }
1602 }
1603 break;
1604 }
1605 }
1606 }
1607
1608 geo->setTypes (newTypes );
1609 geo->setLengths(newLengths);
1610
1611 for(UInt16 i = 0; i <= Geometry::LastIndex; ++i)
1612 {
1613 if(geo->getIndex(i) != NULL)
1614 {
1615 for(UInt32 j = 0; j < oldIdx.size(); ++j)
1616 {
1617 if(geo->getIndex(i) == oldIdx[j])
1618 {
1619 geo->setIndex(newIdx[j], i);
1620 break;
1621 }
1622 }
1623 }
1624 }
1625
1626 #if defined(OSG_GEOOPT_STATISTICS)
1627 SLOG << "time to rewrite types/len/indices: " << (getSystemTime() - start)
1628 << std::endl;
1629 #endif
1630 }
1631
1632 /* ======================================================================== */
1633
1634 namespace
1635 {
1636 // Helper types and functions for makeOptimizedIndex().
1637
1638 const UInt32 ModelledVertexCacheSize = 32;
1639 const Real32 CachePosScorePower = 1.5f;
1640 const Real32 ValenceScoreScale = 2.0f;
1641 const Real32 ValenceScorePower = -0.5f;
1642
1643 struct VertexInfo
1644 {
1645 typedef std::vector<UInt32> IndexStore;
1646
1647 VertexInfo(void);
1648
1649 UInt32 _cachePos;
1650 Real32 _score;
1651 UInt32 _totalValence;
1652 UInt32 _remValence;
1653 IndexStore _triIndices;
1654 };
1655
1656 VertexInfo::VertexInfo(void)
1657 : _cachePos (TypeTraits<UInt32>::getMax()),
1658 _score (0.f),
1659 _totalValence(0),
1660 _remValence (0),
1661 _triIndices ()
1662 {
1663 }
1664
1665 typedef std::vector<VertexInfo> VertexInfoStore;
1666
1667 /* ==================================================================== */
1668
1669 struct TriangleInfo
1670 {
1671 TriangleInfo(void);
1672
1673 Real32 _score;
1674 UInt32 _vertIndices[3];
1675 bool _added;
1676 };
1677
1678 TriangleInfo::TriangleInfo(void)
1679 : _score (0.f),
1680 _vertIndices(),
1681 _added (false)
1682 {
1683 }
1684
1685 typedef std::vector<TriangleInfo> TriangleInfoStore;
1686
1687 /* ==================================================================== */
1688
1689 // Calculate a vertex' score, based on _remValence
1690 // and _cachePos.
1691 // Then update triangles that use the vertex, by adding
1692 // the change in score to their score and keeping track
1693 // of the one with the highest score.
1694 void
1695 updateVertexScore(VertexInfo &vi,
1696 TriangleInfoStore &tis,
1697 Real32 &bestTriScore,
1698 UInt32 &bestTriIndex )
1699 {
1700 Real32 oldScore = vi._score;
1701
1702 if(vi._remValence > 0)
1703 {
1704 // base score based on position in cache
1705 if(vi._cachePos == TypeTraits<UInt32>::getMax())
1706 {
1707 vi._score = 0.f;
1708 }
1709 else if(vi._cachePos < 3)
1710 {
1711 vi._score = 0.75f;
1712 }
1713 else
1714 {
1715 const Real32 scale = 1.f / (ModelledVertexCacheSize - 3);
1716 vi._score = scale * (vi._cachePos - 3);
1717 vi._score = std::pow(1.f - vi._score, CachePosScorePower);
1718 }
1719
1720 // boost for having low valence
1721 vi._score += ValenceScoreScale * std::pow(vi._remValence,
1722 ValenceScorePower);
1723 }
1724 else
1725 {
1726 vi._score = 0.f;
1727 }
1728
1729 Real32 deltaScore = vi._score - oldScore;
1730
1731 #if defined(OSG_GEOOPT_VERBOSE)
1732 SLOG << "update score: score " << vi._score
1733 << " cache pos " << vi._cachePos
1734 << " totalValence " << vi._totalValence
1735 << " remValence " << vi._remValence
1736 << std::endl;
1737 #endif
1738
1739 // update triangles
1740 for(UInt32 i = 0; i < vi._remValence; ++i)
1741 {
1742 UInt32 triIdx = vi._triIndices[i];
1743
1744 tis[triIdx]._score += deltaScore;
1745
1746 #if defined(OSG_GEOOPT_VERBOSE)
1747 SLOG << " updating tri " << triIdx
1748 << " score " << tis[triIdx]._score;
1749 #endif
1750
1751 // we don't need to check tis[triIdx]._added
1752 // because the vertex we are updating has
1753 // it among the first _remValence ones,
1754 // so it was not added yet.
1755 if(tis[triIdx]._score > bestTriScore)
1756 {
1757 #if defined(OSG_GEOOPT_VERBOSE)
1758 PLOG << " new best";
1759 #endif
1760
1761 bestTriScore = tis[triIdx]._score;
1762 bestTriIndex = triIdx;
1763 }
1764
1765 #if defined(OSG_GEOOPT_VERBOSE)
1766 PLOG << std::endl;
1767 #endif
1768 }
1769 }
1770
1771 /* ==================================================================== */
1772
1773 // updates vertex info when triangle usedTriIndex is
1774 // added - reduces _remValence by one and shuffles
1775 // _triIndices around to ensure the ones belonging
1776 // to not-yet-added triangles come first
1777 void
1778 updateUsedVertex(VertexInfo &vi, UInt32 usedTriIndex)
1779 {
1780 for(UInt32 j = 0; j < vi._remValence; ++j)
1781 {
1782 if(vi._triIndices[j] == usedTriIndex)
1783 {
1784 // move tri index back, so first vi._remValence many
1785 // are the ones that still need to be added
1786 std::swap(vi._triIndices[j ],
1787 vi._triIndices[vi._remValence-1] );
1788 break;
1789 }
1790 }
1791
1792 vi._remValence -= 1;
1793 }
1794
1795 /* ==================================================================== */
1796
1797 // Comparison function object for the LRU cache,
1798 // sorts VertexInfos by making NULL less than every non-NULL
1799 // one, and sort non-NULL ones by their _cachePos.
1800 // This ensures we move the 3 NULL slots for the current
1801 // triangles vertices to the front.
1802 struct LRULess
1803 {
1804 bool operator()(VertexInfo *lhs, VertexInfo *rhs);
1805 };
1806
1807 bool
1808 LRULess::operator()(VertexInfo *lhs, VertexInfo *rhs)
1809 {
1810 bool retVal = false;
1811
1812 if(lhs == rhs)
1813 {
1814 retVal = false;
1815 }
1816 else if(lhs == NULL)
1817 {
1818 retVal = true;
1819 }
1820 else if(rhs == NULL)
1821 {
1822 retVal = false;
1823 }
1824 else
1825 {
1826 retVal = lhs->_cachePos < rhs->_cachePos;
1827 }
1828
1829 return retVal;
1830 }
1831
1832 /* ==================================================================== */
1833
1834 #if defined(OSG_GEOOPT_STATISTICS)
1835 void
1836 calcCacheMissCount(Geometry *geo, UInt32 &missCount, UInt32 &hitCount)
1837 {
1838 typedef std::list<UInt32> LRUCache;
1839
1840 GeoIntegralProperty *types = geo->getTypes ();
1841 GeoIntegralProperty *lengths = geo->getLengths();
1842 GeoIntegralProperty *propIdx0 = geo->getIndex(0);
1843
1844 UInt32 k = 0;
1845 UInt32 lruSize = 0;
1846 LRUCache lru;
1847
1848 for(UInt32 i = 0; i < types->size(); ++i)
1849 {
1850 GLenum type = types ->getValue(i);
1851 UInt32 len = lengths->getValue(i);
1852
1853 if(type != GL_TRIANGLES)
1854 {
1855 k += len;
1856 continue;
1857 }
1858
1859 for(UInt32 j = 0; j < len; ++j, ++k)
1860 {
1861 UInt32 idx = propIdx0->getValue(k);
1862
1863 LRUCache::iterator lruIt = std::find(lru.begin(), lru.end(), idx);
1864
1865 if(lruIt != lru.end())
1866 {
1867 ++hitCount;
1868 lru.erase(lruIt);
1869 }
1870 else
1871 {
1872 ++missCount;
1873 ++lruSize;
1874 }
1875
1876 lru.push_front(idx);
1877
1878 while(lruSize > ModelledVertexCacheSize)
1879 {
1880 lru.pop_back();
1881 --lruSize;
1882 }
1883 }
1884 }
1885 }
1886 #endif
1887 } // namespace
1888
1889 /*! Optimize the index of triangle lists for the post-transform
1890 vertex cache.
1891 Based on "Post-Transform Cache Optimization for Indexed Triangle
1892 Lists" by Tom Forsyth, see
1893 http://home.comcast.net/~tom_forsyth/papers/fast_vertex_cache_opt.html
1894
1895 Only works on GL_TRIANGLES primitives in the geometry and requires
1896 the geometry to be single indexed.
1897 */
1898
1899 void
1900 makeOptimizedIndex(Geometry *geo)
1901 {
1902 if(geo->isSingleIndex() == false)
1903 {
1904 SWARNING << "Only single indexed geometries can be optimized."
1905 << std::endl;
1906 return;
1907 }
1908
1909 GeoIntegralProperty *types = geo->getTypes ();
1910 GeoIntegralProperty *lengths = geo->getLengths();
1911
1912 if(types->size() != lengths->size())
1913 {
1914 SWARNING << "Types and Lengths have inconsistent size, aborting."
1915 << std::endl;
1916 return;
1917 }
1918
1919 VertexInfoStore vis;
1920 TriangleInfoStore tis;
1921
1922 GeoVectorProperty *prop0 = geo->getProperty(0);
1923 GeoIntegralPropertyUnrecPtr propIdx0 = geo->getIndex (0);
1924 GeoIntegralPropertyUnrecPtr newPropIdx = GeoUInt32Property::create();
1925
1926 if(prop0 == NULL || propIdx0 == NULL)
1927 {
1928 SWARNING << "No property 0 (positions) or index on geometry, "
1929 << "aborting."
1930 << std::endl;
1931 return;
1932 }
1933
1934 newPropIdx->resize(propIdx0->size());
1935
1936 // 1a) Initialize VertexInfos and TriangleInfos
1937 // First go over geometry and find all GL_TRIANGLES primitives.
1938 // For each triangle store the 3 vertices it uses,
1939 // increment the valence counters of the vertices and
1940 // add the triangle to the list of triangles the vertex belongs to
1941
1942 vis.resize(prop0->size());
1943
1944 UInt32 triCount = 0;
1945 UInt32 k = 0;
1946
1947 // loop over all primitives
1948 for(UInt32 i = 0; i < types->size(); ++i)
1949 {
1950 UInt32 type = types ->getValue(i);
1951 UInt32 len = lengths->getValue(i);
1952
1953 // skip non triangles
1954 if(type != GL_TRIANGLES)
1955 {
1956 k += len;
1957 continue;
1958 }
1959
1960 if(len % 3 != 0)
1961 {
1962 SWARNING << "Encountered degenerate GL_TRIANGLES, aborting."
1963 << std::endl;
1964 return;
1965 }
1966
1967 // loop over triangles
1968 tis.resize(triCount + len / 3);
1969
1970 for(UInt32 j = 0; j < len; j += 3)
1971 {
1972 // update vertices used by triangle
1973 UInt32 idx0 = propIdx0->getValue(k++);
1974 UInt32 idx1 = propIdx0->getValue(k++);
1975 UInt32 idx2 = propIdx0->getValue(k++);
1976
1977 if(idx0 == idx1 || idx0 == idx2 || idx1 == idx2)
1978 continue;
1979
1980 vis[idx0]._totalValence += 1;
1981 vis[idx0]._remValence += 1;
1982 vis[idx0]._triIndices.push_back(triCount);
1983
1984 vis[idx1]._totalValence += 1;
1985 vis[idx1]._remValence += 1;
1986 vis[idx1]._triIndices.push_back(triCount);
1987
1988 vis[idx2]._totalValence += 1;
1989 vis[idx2]._remValence += 1;
1990 vis[idx2]._triIndices.push_back(triCount);
1991
1992 // record vertices used by triangle
1993 tis[triCount]._vertIndices[0] = idx0;
1994 tis[triCount]._vertIndices[1] = idx1;
1995 tis[triCount]._vertIndices[2] = idx2;
1996
1997 triCount += 1;
1998 }
1999 }
2000
2001 if(triCount == 0)
2002 {
2003 SINFO << "Geometry does not contain any GL_TRIANGLES, ignoring."
2004 << std::endl;
2005 return;
2006 }
2007
2008 #if defined(OSG_GEOOPT_STATISTICS)
2009 UInt32 preMissCount = 0;
2010 UInt32 preHitCount = 0;
2011 calcCacheMissCount(geo, preMissCount, preHitCount);
2012 #endif
2013
2014 // 1b) Complete initialization by going over VertexInfos
2015 // calculating the initial score and update triangles scores
2016 // on the way.
2017 // Also keep track of the triangle with the highest score
2018 // to have a starting point for the main loop.
2019
2020 Real32 bestTriScore = 0.f;
2021 UInt32 bestTriIndex = 0;
2022
2023 VertexInfoStore::iterator viIt = vis.begin();
2024 VertexInfoStore::iterator viEnd = vis.end ();
2025
2026 for(; viIt != viEnd; ++viIt)
2027 {
2028 updateVertexScore(*viIt, tis, bestTriScore, bestTriIndex);
2029 }
2030
2031 #if defined(OSG_GEOOPT_VERBOSE)
2032 SLOG << "post init: bestTriScore " << bestTriScore
2033 << " bestTriIndex " << bestTriIndex
2034 << std::endl;
2035 #endif
2036
2037 // 2) Main loop.
2038 // Add triangles to index based on their score, update
2039 // the LRU cache and affected scores after each step
2040 // while keeping track of the triangle with the highest score.
2041 // The triangle with highest score is only an approximation,
2042 // because only tris with vertices in the LRU are considered.
2043 // See the paper for more info.
2044
2045 typedef std::vector<VertexInfo *> LRUType;
2046 LRUType lru(ModelledVertexCacheSize + 3, NULL);
2047 UInt32 lruSize = 0;
2048
2049 for(UInt32 i = 0; i < triCount; ++i)
2050 {
2051 #if defined(OSG_GEOOPT_VERBOSE)
2052 SLOG << "=== tri i " << i << " of " << triCount << " ==="
2053 << std::endl;
2054 #endif
2055
2056 // it's possible that all vertices in the cache belong
2057 // to triangles that are already added (very rare case).
2058 // Scan all triangles to find the best.
2059 if(bestTriScore == 0.f ||
2060 tis[bestTriIndex]._added == true )
2061 {
2062 #if defined(OSG_GEOOPT_VERBOSE)
2063 SLOG << " no valid triangle with vertices in cache"
2064 << " performing full search." << std::endl;
2065 #endif
2066
2067 bestTriScore = 0.f;
2068 bestTriIndex = 0;
2069
2070 for(UInt32 j = 0; j < triCount; ++j)
2071 {
2072 if(tis[j]._added == false &&
2073 tis[j]._score > bestTriScore )
2074 {
2075 bestTriScore = tis[j]._score;
2076 bestTriIndex = j;
2077 }
2078 }
2079 }
2080
2081 // Pick the triangle with the highest score and add it to the index
2082 TriangleInfo &bestTri = tis[bestTriIndex];
2083
2084 newPropIdx->setValue(bestTri._vertIndices[0], i * 3 );
2085 newPropIdx->setValue(bestTri._vertIndices[1], i * 3 + 1);
2086 newPropIdx->setValue(bestTri._vertIndices[2], i * 3 + 2);
2087
2088 VertexInfo &v0 = vis[bestTri._vertIndices[0]];
2089 VertexInfo &v1 = vis[bestTri._vertIndices[1]];
2090 VertexInfo &v2 = vis[bestTri._vertIndices[2]];
2091
2092 updateUsedVertex(v0, bestTriIndex);
2093 updateUsedVertex(v1, bestTriIndex);
2094 updateUsedVertex(v2, bestTriIndex);
2095
2096 bestTri._added = true;
2097
2098 #if defined(OSG_GEOOPT_VERBOSE)
2099 SLOG << " adding best tri " << bestTriIndex
2100 << " with score " << bestTriScore;
2101 #endif
2102
2103 // if vertices of the added triangle are already
2104 // in the cache we clear out their entries and
2105 // keep track of how much the cache grows
2106 UInt32 lruGrow = 3;
2107
2108 if(v0._cachePos != TypeTraits<UInt32>::getMax())
2109 {
2110 #if defined(OSG_GEOOPT_VERBOSE)
2111 PLOG << " v0 " << bestTri._vertIndices[0]
2112 << " in cache (" << v0._cachePos << ")";
2113 #endif
2114 lru[v0._cachePos] = NULL;
2115 lruGrow -= 1;
2116 }
2117 else
2118 {
2119 #if defined(OSG_GEOOPT_VERBOSE)
2120 PLOG << " v0 " << bestTri._vertIndices[0];
2121 #endif
2122 }
2123
2124 if(v1._cachePos != TypeTraits<UInt32>::getMax())
2125 {
2126 #if defined(OSG_GEOOPT_VERBOSE)
2127 PLOG << " v1 " << bestTri._vertIndices[1]
2128 << " in cache (" << v1._cachePos << ")";
2129 #endif
2130 lru[v1._cachePos] = NULL;
2131 lruGrow -= 1;
2132 }
2133 else
2134 {
2135 #if defined(OSG_GEOOPT_VERBOSE)
2136 PLOG << " v1 " << bestTri._vertIndices[1];
2137 #endif
2138 }
2139
2140 if(v2._cachePos != TypeTraits<UInt32>::getMax())
2141 {
2142 #if defined(OSG_GEOOPT_VERBOSE)
2143 PLOG << " v2 " << bestTri._vertIndices[2]
2144 << " in cache (" << v2._cachePos << ")";
2145 #endif
2146 lru[v2._cachePos] = NULL;
2147 lruGrow -= 1;
2148 }
2149 else
2150 {
2151 #if defined(OSG_GEOOPT_VERBOSE)
2152 PLOG << " v2 " << bestTri._vertIndices[2];
2153 #endif
2154 }
2155
2156 #if defined(OSG_GEOOPT_VERBOSE)
2157 PLOG << std::endl;
2158 #endif
2159
2160 // make sure there are lruGrow NULL entries after the
2161 // current size
2162 for(UInt32 j = lruSize; j < lruSize + lruGrow; ++j)
2163 lru[j] = NULL;
2164
2165 // sort cache entries, moving NULL entries to the front,
2166 // other entries remain sorted by their _cachePos.
2167 std::sort(lru.begin(), lru.begin() + lruSize + lruGrow,
2168 LRULess() );
2169
2170 OSG_ASSERT(lru[0] == NULL && lru[1] == NULL && lru[2] == NULL);
2171
2172 // put the three used vertices at front of cache
2173 lru[2] = &v0;
2174 lru[1] = &v1;
2175 lru[0] = &v2;
2176
2177 // update cache, setting correct position for entries
2178 // and recalculate score, keeping track of best triangle
2179 bestTriScore = 0.f;
2180 bestTriIndex = 0;
2181
2182 for(UInt32 j = 0; j < lruSize + lruGrow; ++j)
2183 {
2184 if(j < ModelledVertexCacheSize)
2185 {
2186 #if defined(OSG_GEOOPT_VERBOSE)
2187 SLOG << " update cache j " << j << std::endl;
2188 #endif
2189
2190 lru[j]->_cachePos = j;
2191 }
2192 else
2193 {
2194 #if defined(OSG_GEOOPT_VERBOSE)
2195 SLOG << " update cache j " << j
2196 << " -> evicted" << std::endl;
2197 #endif
2198
2199 lru[j]->_cachePos = TypeTraits<UInt32>::getMax();
2200 }
2201
2202 updateVertexScore(*lru[j], tis, bestTriScore, bestTriIndex);
2203 }
2204
2205 lruSize = osgMin(lruSize + lruGrow, ModelledVertexCacheSize);
2206
2207 #if defined(OSG_GEOOPT_VERBOSE)
2208 SLOG << " new cache size " << lruSize
2209 << " lruGrow " << lruGrow
2210 << std::endl;
2211 #endif
2212 }
2213
2214 // set the new index on the geometry
2215 for(UInt32 i = 0; i <= Geometry::LastIndex; ++i)
2216 {
2217 if(geo->getIndex(i) == propIdx0)
2218 {
2219 geo->setIndex(newPropIdx, i);
2220 }
2221 }
2222
2223 #if defined(OSG_GEOOPT_STATISTICS)
2224 UInt32 postMissCount = 0;
2225 UInt32 postHitCount = 0;
2226 calcCacheMissCount(geo, postMissCount, postHitCount);
2227
2228 SLOG << "preMissCount " << preMissCount
2229 << " preHitCount " << preHitCount
2230 << " pre ACMR " << (Real32(preMissCount) / triCount)
2231 << " triCount " << triCount
2232 << std::endl;
2233 SLOG << "postMissCount " << postMissCount
2234 << " postHitCount " << postHitCount
2235 << " post ACMR " << (Real32(postMissCount) / triCount)
2236 << " triCount " << triCount
2237 << std::endl;
2238 SLOG << "old idx size " << propIdx0->size()
2239 << " new idx size " << newPropIdx->size()
2240 << std::endl;
2241 #endif
2242 }
2243
2244 /* ======================================================================== */
2245
2246 namespace
2247 {
2248 // Helper types and functions for makeOptimizedProperties().
2249
2250 // A pair of indices. Used to record a change from oldIdx to newIdx.
2251 struct IndexRemap
2252 {
2253 explicit IndexRemap(UInt32 oldIdx, UInt32 newIdx);
2254
2255 UInt32 _oldIdx;
2256 UInt32 _newIdx;
2257 };
2258
2259 /* explicit */
2260 IndexRemap::IndexRemap(UInt32 oldIdx, UInt32 newIdx)
2261 : _oldIdx(oldIdx),
2262 _newIdx(newIdx)
2263 {
2264 }
2265
2266 // Comparison function object for IndexRemap, allows them to be used in
2267 // associative containers (std::set, std::map).
2268 // Only the old index is used for comparison.
2269 struct IndexRemapLess
2270 {
2271 bool operator()(const IndexRemap &lhs, const IndexRemap &rhs) const;
2272 };
2273
2274 bool
2275 IndexRemapLess::operator()(const IndexRemap &lhs,
2276 const IndexRemap &rhs ) const
2277 {
2278 return (lhs._oldIdx < rhs._oldIdx);
2279 }
2280
2281 typedef std::set<IndexRemap, IndexRemapLess> IndexRemapSet;
2282
2283 // Copies property values from srcOffset in srcProps to destOffset
2284 // in the corresponding dstProps.
2285 void
2286 copyProperties(const PropertyStore &srcProps,
2287 UInt32 srcOffset,
2288 const PropertyStore &dstProps,
2289 UInt32 dstOffset )
2290 {
2291 OSG_ASSERT(srcProps.size() == dstProps.size());
2292
2293 for(UInt32 i = 0; i < srcProps.size(); ++i)
2294 {
2295 GeoVectorProperty::MaxTypeT val;
2296 srcProps[i]->getValue(val, srcOffset);
2297 dstProps[i]->setValue(val, dstOffset);
2298 }
2299 }
2300
2301 } // namespace
2302
2303 /*! Optimize properties of the geometry for the pre-transform vertex
2304 cache.
2305 Creates new properties that store values in the order referenced
2306 by the index (without duplicates) and creates a new index for
2307 the reordered properties. This does not change the order
2308 primitives are drawn in, so previos post-transform vertex cache
2309 optimizations are preserved.
2310
2311 Requires the geometry to be single indexed.
2312 */
2313
2314 void
2315 makeOptimizedProperties(Geometry *geo)
2316 {
2317 if(geo->isSingleIndex() == false)
2318 {
2319 SWARNING << "Only single indexed geometries can be optimized."
2320 << std::endl;
2321 return;
2322 }
2323
2324 GeoIntegralProperty *types = geo->getTypes ();
2325 GeoIntegralProperty *lengths = geo->getLengths();
2326
2327 if(types->size() != lengths->size())
2328 {
2329 SWARNING << "Types and Lengths have inconsistent size, aborting."
2330 << std::endl;
2331 return;
2332 }
2333
2334 GeoIntegralPropertyUnrecPtr propIdx0 = geo->getIndex(0);
2335
2336 if(propIdx0 == NULL)
2337 {
2338 SWARNING << "No index for property 0 (positions), aborting."
2339 << std::endl;
2340 return;
2341 }
2342
2343 // create new properties of the same type as existing ones
2344
2345 PropertyStore prop;
2346 PropertyStore newProp;
2347 GeoIntegralPropertyUnrecPtr newPropIdx = GeoUInt32Property::create();
2348
2349 newPropIdx->resize(propIdx0->size());
2350
2351 for(UInt32 i = 0; i <= Geometry::LastIndex; ++i)
2352 {
2353 if(geo->getProperty(i) != NULL)
2354 {
2355 bool add = true;
2356
2357 for(UInt32 j = 0; add == true && j < prop.size(); ++j)
2358 {
2359 if(prop[j] == geo->getProperty(i))
2360 add = false;
2361 }
2362
2363 if(add == true)
2364 {
2365 // create new propery of same type
2366 GeoVectorPropertyUnrecPtr np =
2367 dynamic_pointer_cast<GeoVectorProperty>(
2368 geo->getProperty(i)->getType().createContainer());
2369 np->resize(geo->getProperty(i)->size());
2370
2371 prop .push_back(geo->getProperty(i));
2372 newProp.push_back(np);
2373 }
2374 }
2375 }
2376
2377 // reorder properties
2378 // go through the index, filling the properties in the order
2379 // of access through the index.
2380 // idxSet is used to keep track of already added properties
2381 // and the new value to be stored in the index for accessing it.
2382
2383 IndexRemapSet idxSet;
2384
2385 UInt32 idxOffset = 0;
2386 UInt32 propOffset = 0;
2387
2388 for(UInt32 i = 0; i < lengths->size(); ++i)
2389 {
2390 UInt32 len = lengths->getValue(i);
2391
2392 for(UInt32 j = 0; j < len; ++j, ++idxOffset)
2393 {
2394 UInt32 idx = propIdx0->getValue(idxOffset);
2395
2396 IndexRemap ir(idx, propOffset);
2397 IndexRemapSet::const_iterator isIt = idxSet.find(ir);
2398
2399 if(isIt == idxSet.end())
2400 {
2401 // first use of this idx
2402 idxSet.insert(ir);
2403
2404 // copy properties to new position
2405 copyProperties(prop, idx, newProp, propOffset);
2406
2407 // write new position to index
2408 newPropIdx->setValue(propOffset, idxOffset);
2409
2410 ++propOffset;
2411 }
2412 else
2413 {
2414 // idx occured previously, only record
2415 // new position in index
2416 newPropIdx->setValue((*isIt)._newIdx, idxOffset);
2417 }
2418 }
2419 }
2420
2421 // set new properties and index on geometry
2422
2423 for(UInt32 i = 0; i <= Geometry::LastIndex; ++i)
2424 {
2425 if(geo->getProperty(i) != NULL)
2426 {
2427 for(UInt32 j = 0; j < prop.size(); ++j)
2428 {
2429 if(geo->getProperty(i) == prop[j])
2430 {
2431 geo->setProperty(newProp[j], i);
2432 geo->setIndex (newPropIdx, i);
2433 }
2434 }
2435 }
2436 }
2437 }
2438
2439 #if __GNUC__ >= 4 || __GNUC_MINOR__ >=3
2440 #pragma GCC diagnostic pop
2441 #endif
2442
2443 OSG_END_NAMESPACE