1 /* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2  *
3  * This library is open source and may be redistributed and/or modified under
4  * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5  * (at your option) any later version.  The full license is in LICENSE file
6  * included with this distribution, and on the openscenegraph.org website.
7  *
8  * This library is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11  * OpenSceneGraph Public License for more details.
12 */
13 
14 #include <osg/TriangleIndexFunctor>
15 
16 #include <osgUtil/Simplifier>
17 
18 #include <osgUtil/SmoothingVisitor>
19 #include <osgUtil/TriStripVisitor>
20 
21 #include <set>
22 #include <list>
23 #include <algorithm>
24 
25 #include <iterator>
26 
27 using namespace osgUtil;
28 
29 struct dereference_less
30 {
31     template<class T, class U>
operator ()dereference_less32     inline bool operator() (const T& lhs,const U& rhs) const
33     {
34         return *lhs < *rhs;
35     }
36 };
37 
38 template<class T>
dereference_check_less(const T & lhs,const T & rhs)39 bool dereference_check_less(const T& lhs,const T& rhs)
40 {
41     if (lhs==rhs) return false;
42     if (!lhs) return true;
43     if (!rhs) return false;
44     return *lhs < *rhs;
45 }
46 
47 struct dereference_clear
48 {
49     template<class T>
operator ()dereference_clear50     inline void operator() (const T& t)
51     {
52         T& non_const_t = const_cast<T&>(t);
53         non_const_t->clear();
54     }
55 };
56 
57 class EdgeCollapse
58 {
59 public:
60 
61 
62 #if 1
63     typedef float error_type;
64 #else
65     typedef double error_type;
66 #endif
67 
68     struct Triangle;
69     struct Edge;
70     struct Point;
71 
72 
EdgeCollapse()73     EdgeCollapse():
74         _geometry(0),
75         _computeErrorMetricUsingLength(false)  {}
76 
77     ~EdgeCollapse();
78 
79     void setGeometry(osg::Geometry* geometry, const Simplifier::IndexList& protectedPoints);
getGeometry()80     osg::Geometry* getGeometry() { return _geometry; }
81 
setComputeErrorMetricUsingLength(bool flag)82     void setComputeErrorMetricUsingLength(bool flag) { _computeErrorMetricUsingLength = flag; }
getComputeErrorMetricUsingLength() const83     bool getComputeErrorMetricUsingLength() const { return _computeErrorMetricUsingLength; }
84 
getNumOfTriangles()85     unsigned int getNumOfTriangles() { return _triangleSet.size(); }
86 
computeInterpolatedPoint(Edge * edge,float r) const87     Point* computeInterpolatedPoint(Edge* edge,float r) const
88     {
89         Point* point = new Point;
90         float r1 = 1.0f-r;
91         float r2 = r;
92         Point* p1 = edge->_p1.get();
93         Point* p2 = edge->_p2.get();
94 
95         if (p1==0 || p2==0)
96         {
97             OSG_NOTICE<<"Error computeInterpolatedPoint("<<edge<<",r) p1 and/or p2==0"<<std::endl;
98             return 0;
99         }
100 
101         point->_vertex = p1->_vertex * r1 + p2->_vertex * r2;
102         unsigned int s = osg::minimum(p1->_attributes.size(),p2->_attributes.size());
103         for(unsigned int i=0;i<s;++i)
104         {
105             point->_attributes.push_back(p1->_attributes[i]*r1 + p2->_attributes[i]*r2);
106         }
107         return point;
108     }
109 
computeOptimalPoint(Edge * edge) const110     Point* computeOptimalPoint(Edge* edge) const
111     {
112         return computeInterpolatedPoint(edge,0.5f);
113     }
114 
computeErrorMetric(Edge * edge,Point * point) const115     error_type computeErrorMetric(Edge* edge,Point* point) const
116     {
117         if (_computeErrorMetricUsingLength)
118         {
119             error_type dx = error_type(edge->_p1->_vertex.x()) - error_type(edge->_p2->_vertex.x());
120             error_type dy = error_type(edge->_p1->_vertex.y()) - error_type(edge->_p2->_vertex.y());
121             error_type dz = error_type(edge->_p1->_vertex.z()) - error_type(edge->_p2->_vertex.z());
122             return sqrt(dx*dx + dy*dy + dz*dz);
123         }
124         else if (point)
125         {
126             typedef std::set< osg::ref_ptr<Triangle> > LocalTriangleSet ;
127             LocalTriangleSet triangles;
128             std::copy( edge->_p1->_triangles.begin(), edge->_p1->_triangles.end(), std::inserter(triangles,triangles.begin()));
129             std::copy( edge->_p2->_triangles.begin(), edge->_p2->_triangles.end(), std::inserter(triangles,triangles.begin()));
130 
131             const osg::Vec3& vertex = point->_vertex;
132             error_type error = 0.0;
133 
134             if (triangles.empty()) return 0.0;
135 
136             for(LocalTriangleSet::iterator itr=triangles.begin();
137                 itr!=triangles.end();
138                 ++itr)
139             {
140                 error += fabs( (*itr)->distance(vertex) );
141             }
142 
143             // use average of error
144             error /= error_type(triangles.size());
145 
146             return error;
147         }
148         else
149         {
150             return 0;
151         }
152     }
153 
updateErrorMetricForEdge(Edge * edge)154     void updateErrorMetricForEdge(Edge* edge)
155     {
156         if (!edge->_p1 || !edge->_p2)
157         {
158             OSG_NOTICE<<"Error updateErrorMetricForEdge("<<edge<<") p1 and/or p2==0"<<std::endl;
159             return;
160         }
161 
162 
163         osg::ref_ptr<Edge> keep_local_reference_to_edge(edge);
164 
165         if (_edgeSet.count(keep_local_reference_to_edge)!=0)
166         {
167             _edgeSet.erase(keep_local_reference_to_edge);
168         }
169 
170         edge->_proposedPoint = computeOptimalPoint(edge);
171 
172         if (_computeErrorMetricUsingLength)
173         {
174             edge->setErrorMetric( computeErrorMetric( edge, edge->_proposedPoint.get()));
175         }
176         else
177         {
178             edge->updateMaxNormalDeviationOnEdgeCollapse();
179 
180             if (edge->getMaxNormalDeviationOnEdgeCollapse()<=1.0 && !edge->isAdjacentToBoundary())
181                 edge->setErrorMetric( computeErrorMetric( edge, edge->_proposedPoint.get()));
182             else
183                 edge->setErrorMetric( FLT_MAX );
184          }
185 
186         _edgeSet.insert(keep_local_reference_to_edge);
187     }
188 
updateErrorMetricForAllEdges()189     void updateErrorMetricForAllEdges()
190     {
191         typedef std::vector< osg::ref_ptr<Edge> > LocalEdgeList ;
192         LocalEdgeList edges;
193         std::copy( _edgeSet.begin(), _edgeSet.end(), std::back_inserter(edges));
194 
195         _edgeSet.clear();
196 
197         for(LocalEdgeList::iterator itr=edges.begin();
198             itr!=edges.end();
199             ++itr)
200         {
201             Edge* edge = itr->get();
202 
203             if (_computeErrorMetricUsingLength)
204             {
205                 edge->setErrorMetric( computeErrorMetric( edge, edge->_proposedPoint.get()));
206             }
207             else
208             {
209                 edge->_proposedPoint = computeOptimalPoint(edge);
210                 edge->updateMaxNormalDeviationOnEdgeCollapse();
211 
212                 if (edge->getMaxNormalDeviationOnEdgeCollapse()<=1.0 && !edge->isAdjacentToBoundary())
213                     edge->setErrorMetric( computeErrorMetric( edge, edge->_proposedPoint.get()));
214                 else
215                     edge->setErrorMetric( FLT_MAX );
216 
217             }
218             _edgeSet.insert(edge);
219         }
220     }
221 
collapseMinimumErrorEdge()222     bool collapseMinimumErrorEdge()
223     {
224         if (!_edgeSet.empty())
225         {
226             Edge* edge = const_cast<Edge*>(_edgeSet.begin()->get());
227 
228             if (edge->getErrorMetric()==FLT_MAX)
229             {
230                 OSG_INFO<<"collapseMinimumErrorEdge() return false due to edge->getErrorMetric()==FLT_MAX"<<std::endl;
231                 return false;
232             }
233 
234             osg::ref_ptr<Point> pNew = edge->_proposedPoint.valid()? edge->_proposedPoint.get() : computeInterpolatedPoint(edge,0.5f);
235             return (collapseEdge(edge,pNew.get()));
236         }
237         OSG_INFO<<"collapseMinimumErrorEdge() return false due to _edgeSet.empty()"<<std::endl;
238         return false;
239     }
240 
241 
divideLongestEdge()242     bool divideLongestEdge()
243     {
244         if (!_edgeSet.empty())
245         {
246             Edge* edge = const_cast<Edge*>(_edgeSet.rbegin()->get());
247 
248             if (edge->getErrorMetric()==FLT_MAX)
249             {
250                 OSG_INFO<<"divideLongestEdge() return false due to edge->getErrorMetric()==FLT_MAX"<<std::endl;
251                 return false;
252             }
253 
254             osg::ref_ptr<Point> pNew = edge->_proposedPoint.valid()? edge->_proposedPoint.get() : computeInterpolatedPoint(edge,0.5f);
255             return (divideEdge(edge,pNew.get()));
256         }
257         OSG_INFO<<"divideLongestEdge() return false due to _edgeSet.empty()"<<std::endl;
258         return false;
259     }
260 
261     void copyBackToGeometry();
262 
263     typedef std::vector<float>                                                  FloatList;
264     typedef std::set<osg::ref_ptr<Edge>,dereference_less >                      EdgeSet;
265     typedef std::set< osg::ref_ptr<Point>,dereference_less >                    PointSet;
266     typedef std::vector< osg::ref_ptr<Point> >                                  PointList;
267     typedef std::list< osg::ref_ptr<Triangle> >                                 TriangleList;
268     typedef std::set< osg::ref_ptr<Triangle> >                                  TriangleSet;
269     typedef std::map< osg::ref_ptr<Triangle>, unsigned int, dereference_less >  TriangleMap;
270 
271     struct Point : public osg::Referenced
272     {
PointEdgeCollapse::Point273         Point(): _protected(false), _index(0) {}
274 
275         bool _protected;
276 
277         unsigned int _index;
278 
279         osg::Vec3           _vertex;
280         FloatList           _attributes;
281         TriangleSet         _triangles;
282 
clearEdgeCollapse::Point283         void clear()
284         {
285             _attributes.clear();
286             _triangles.clear();
287         }
288 
operator <EdgeCollapse::Point289         bool operator < ( const Point& rhs) const
290         {
291             if (_vertex < rhs._vertex) return true;
292             if (rhs._vertex < _vertex) return false;
293 
294             return _attributes < rhs._attributes;
295         }
296 
isBoundaryPointEdgeCollapse::Point297         bool isBoundaryPoint() const
298         {
299             if (_protected) return true;
300 
301             for(TriangleSet::const_iterator itr=_triangles.begin();
302                 itr!=_triangles.end();
303                 ++itr)
304             {
305                 const Triangle* triangle = itr->get();
306                 if ((triangle->_e1->_p1==this || triangle->_e1->_p2==this) && triangle->_e1->isBoundaryEdge()) return true;
307                 if ((triangle->_e2->_p1==this || triangle->_e2->_p2==this) && triangle->_e2->isBoundaryEdge()) return true;
308                 if ((triangle->_e3->_p1==this || triangle->_e3->_p2==this) && triangle->_e3->isBoundaryEdge()) return true;
309 
310                 //if ((*itr)->isBoundaryTriangle()) return true;
311             }
312             return false;
313         }
314 
315     };
316 
317     struct Edge : public osg::Referenced
318     {
EdgeEdgeCollapse::Edge319         Edge(): _errorMetric(0.0), _maximumDeviation(1.0) {}
320 
clearEdgeCollapse::Edge321         void clear()
322         {
323             _p1 = 0;
324             _p2 = 0;
325             _triangles.clear();
326         }
327 
328         osg::ref_ptr<Point> _p1;
329         osg::ref_ptr<Point> _p2;
330 
331         TriangleSet _triangles;
332 
333         error_type _errorMetric;
334         error_type _maximumDeviation;
335 
336         osg::ref_ptr<Point> _proposedPoint;
337 
setErrorMetricEdgeCollapse::Edge338         void setErrorMetric(error_type errorMetric) { _errorMetric = errorMetric; }
getErrorMetricEdgeCollapse::Edge339         error_type getErrorMetric() const { return _errorMetric; }
340 
operator <EdgeCollapse::Edge341         bool operator < ( const Edge& rhs) const
342         {
343             // both error metrics are computed
344             if (getErrorMetric()<rhs.getErrorMetric()) return true;
345             else if (rhs.getErrorMetric()<getErrorMetric()) return false;
346 
347             if (dereference_check_less(_p1,rhs._p1)) return true;
348             if (dereference_check_less(rhs._p1,_p1)) return false;
349 
350             return dereference_check_less(_p2,rhs._p2);
351         }
352 
operator ==EdgeCollapse::Edge353         bool operator == ( const Edge& rhs) const
354         {
355             if (&rhs==this) return true;
356             if (*this<rhs) return false;
357             if (rhs<*this) return false;
358             return true;
359         }
360 
operator !=EdgeCollapse::Edge361         bool operator != ( const Edge& rhs) const
362         {
363             if (&rhs==this) return false;
364             if (*this<rhs) return true;
365             if (rhs<*this) return true;
366             return false;
367         }
368 
addTriangleEdgeCollapse::Edge369         void addTriangle(Triangle* triangle)
370         {
371             _triangles.insert(triangle);
372             // if (_triangles.size()>2) OSG_NOTICE<<"Warning too many triangles ("<<_triangles.size()<<") sharing edge "<<std::endl;
373         }
374 
isBoundaryEdgeEdgeCollapse::Edge375         bool isBoundaryEdge() const
376         {
377             return _triangles.size()<=1;
378         }
379 
isAdjacentToBoundaryEdgeCollapse::Edge380         bool isAdjacentToBoundary() const
381         {
382             return isBoundaryEdge() || _p1->isBoundaryPoint() || _p2->isBoundaryPoint();
383         }
384 
385 
updateMaxNormalDeviationOnEdgeCollapseEdgeCollapse::Edge386         void updateMaxNormalDeviationOnEdgeCollapse()
387         {
388             //OSG_NOTICE<<"updateMaxNormalDeviationOnEdgeCollapse()"<<std::endl;
389             _maximumDeviation = 0.0f;
390             for(TriangleSet::iterator itr1=_p1->_triangles.begin();
391                 itr1!=_p1->_triangles.end();
392                 ++itr1)
393             {
394                 if (_triangles.count(*itr1)==0)
395                 {
396                     _maximumDeviation = osg::maximum(_maximumDeviation, (*itr1)->computeNormalDeviationOnEdgeCollapse(this,_proposedPoint.get()));
397                 }
398             }
399             for(TriangleSet::iterator itr2=_p2->_triangles.begin();
400                 itr2!=_p2->_triangles.end();
401                 ++itr2)
402             {
403                 if (_triangles.count(*itr2)==0)
404                 {
405                     _maximumDeviation = osg::maximum(_maximumDeviation, (*itr2)->computeNormalDeviationOnEdgeCollapse(this,_proposedPoint.get()));
406                 }
407             }
408         }
409 
getMaxNormalDeviationOnEdgeCollapseEdgeCollapse::Edge410         error_type getMaxNormalDeviationOnEdgeCollapse() const { return _maximumDeviation; }
411 
412     };
413 
414     struct Triangle : public osg::Referenced
415     {
TriangleEdgeCollapse::Triangle416         Triangle() {}
417 
clearEdgeCollapse::Triangle418         void clear()
419         {
420             _p1 = 0;
421             _p2 = 0;
422             _p3 = 0;
423 
424             _e1 = 0;
425             _e2 = 0;
426             _e3 = 0;
427         }
428 
operator <EdgeCollapse::Triangle429         inline bool operator < (const Triangle& rhs) const
430         {
431             if (dereference_check_less(_p1,rhs._p1)) return true;
432             if (dereference_check_less(rhs._p1,_p1)) return false;
433 
434 
435             const Point* lhs_lower = dereference_check_less(_p2,_p3) ? _p2.get() : _p3.get();
436             const Point* rhs_lower = dereference_check_less(rhs._p2,rhs._p3) ? rhs._p2.get() : rhs._p3.get();
437 
438             if (dereference_check_less(lhs_lower,rhs_lower)) return true;
439             if (dereference_check_less(rhs_lower,lhs_lower)) return false;
440 
441             const Point* lhs_upper = dereference_check_less(_p2,_p3) ? _p3.get() : _p2.get();
442             const Point* rhs_upper = dereference_check_less(rhs._p2,rhs._p3) ? rhs._p3.get() : rhs._p2.get();
443 
444             return dereference_check_less(lhs_upper,rhs_upper);
445         }
446 
447 
setOrderedPointsEdgeCollapse::Triangle448         void setOrderedPoints(Point* p1, Point* p2, Point* p3)
449         {
450             Point* points[3];
451             points[0] = p1;
452             points[1] = p2;
453             points[2] = p3;
454 
455             // find the lowest value point in the list.
456             unsigned int lowest = 0;
457             if (dereference_check_less(points[1],points[lowest])) lowest = 1;
458             if (dereference_check_less(points[2],points[lowest])) lowest = 2;
459 
460             _p1 = points[lowest];
461             _p2 = points[(lowest+1)%3];
462             _p3 = points[(lowest+2)%3];
463         }
464 
updateEdgeCollapse::Triangle465         void update()
466         {
467             _plane.set(_p1->_vertex,_p2->_vertex,_p3->_vertex);
468 
469         }
470 
computeNewPlaneOnEdgeCollapseEdgeCollapse::Triangle471         osg::Plane computeNewPlaneOnEdgeCollapse(Edge* edge,Point* pNew) const
472         {
473             const Point* p1 = (_p1==edge->_p1 || _p1==edge->_p2) ? pNew : _p1.get();
474             const Point* p2 = (_p2==edge->_p1 || _p2==edge->_p2) ? pNew : _p2.get();
475             const Point* p3 = (_p3==edge->_p1 || _p3==edge->_p2) ? pNew : _p3.get();
476 
477             return osg::Plane(p1->_vertex,p2->_vertex,p3->_vertex);
478         }
479 
480         // note return 1 - dotproduct, so that deviation is in the range of 0.0 to 2.0, where 0 is coincident, 1.0 is 90 degrees, and 2.0 is 180 degrees.
computeNormalDeviationOnEdgeCollapseEdgeCollapse::Triangle481         error_type computeNormalDeviationOnEdgeCollapse(Edge* edge,Point* pNew) const
482         {
483             const Point* p1 = (_p1==edge->_p1 || _p1==edge->_p2) ? pNew : _p1.get();
484             const Point* p2 = (_p2==edge->_p1 || _p2==edge->_p2) ? pNew : _p2.get();
485             const Point* p3 = (_p3==edge->_p1 || _p3==edge->_p2) ? pNew : _p3.get();
486 
487             osg::Vec3 new_normal = (p2->_vertex - p1->_vertex) ^ (p3->_vertex - p2->_vertex);
488             new_normal.normalize();
489 
490             error_type result = 1.0 - (new_normal.x() * _plane[0] + new_normal.y() * _plane[1] + new_normal.z() * _plane[2]);
491             return result;
492         }
493 
distanceEdgeCollapse::Triangle494         error_type distance(const osg::Vec3& vertex) const
495         {
496             return error_type(_plane[0])*error_type(vertex.x())+
497                    error_type(_plane[1])*error_type(vertex.y())+
498                    error_type(_plane[2])*error_type(vertex.z())+
499                    error_type(_plane[3]);
500         }
501 
isBoundaryTriangleEdgeCollapse::Triangle502         bool isBoundaryTriangle() const
503         {
504             return (_e1->isBoundaryEdge() || _e2->isBoundaryEdge() ||  _e3->isBoundaryEdge());
505         }
506 
507 
508         osg::ref_ptr<Point> _p1;
509         osg::ref_ptr<Point> _p2;
510         osg::ref_ptr<Point> _p3;
511 
512         osg::ref_ptr<Edge> _e1;
513         osg::ref_ptr<Edge> _e2;
514         osg::ref_ptr<Edge> _e3;
515 
516         osg::Plane _plane;
517 
518     };
519 
520 
addTriangle(unsigned int p1,unsigned int p2,unsigned int p3)521     Triangle* addTriangle(unsigned int p1, unsigned int p2, unsigned int p3)
522     {
523         //OSG_NOTICE<<"addTriangle("<<p1<<","<<p2<<","<<p3<<")"<<std::endl;
524 
525         // detect if triangle is degenerate.
526         if (p1==p2 || p2==p3 || p1==p3) return 0;
527 
528         Triangle* triangle = new Triangle;
529 
530         Point* points[3];
531         points[0] = addPoint(triangle, p1);
532         points[1] = addPoint(triangle, p2);
533         points[2] = addPoint(triangle, p3);
534 
535         // find the lowest value point in the list.
536         unsigned int lowest = 0;
537         if (dereference_check_less(points[1],points[lowest])) lowest = 1;
538         if (dereference_check_less(points[2],points[lowest])) lowest = 2;
539 
540         triangle->_p1 = points[lowest];
541         triangle->_p2 = points[(lowest+1)%3];
542         triangle->_p3 = points[(lowest+2)%3];
543 
544         triangle->_e1 = addEdge(triangle, triangle->_p1.get(), triangle->_p2.get());
545         triangle->_e2 = addEdge(triangle, triangle->_p2.get(), triangle->_p3.get());
546         triangle->_e3 = addEdge(triangle, triangle->_p3.get(), triangle->_p1.get());
547 
548         triangle->update();
549 
550         _triangleSet.insert(triangle);
551 
552         return triangle;
553     }
554 
addTriangle(Point * p1,Point * p2,Point * p3)555     Triangle* addTriangle(Point* p1, Point* p2, Point* p3)
556     {
557         // OSG_NOTICE<<"      addTriangle("<<p1<<","<<p2<<","<<p3<<")"<<std::endl;
558 
559         // detect if triangle is degenerate.
560         if (p1==p2 || p2==p3 || p1==p3)
561         {
562             // OSG_NOTICE<<"    **** addTriangle failed - p1==p2 || p2==p3 || p1==p3"<<std::endl;
563             return 0;
564         }
565 
566         Triangle* triangle = new Triangle;
567 
568         Point* points[3];
569         points[0] = addPoint(triangle, p1);
570         points[1] = addPoint(triangle, p2);
571         points[2] = addPoint(triangle, p3);
572 
573         // find the lowest value point in the list.
574         unsigned int lowest = 0;
575         if (dereference_check_less(points[1],points[lowest])) lowest = 1;
576         if (dereference_check_less(points[2],points[lowest])) lowest = 2;
577 
578         triangle->_p1 = points[lowest];
579         triangle->_p2 = points[(lowest+1)%3];
580         triangle->_p3 = points[(lowest+2)%3];
581 
582         triangle->_e1 = addEdge(triangle, triangle->_p1.get(), triangle->_p2.get());
583         triangle->_e2 = addEdge(triangle, triangle->_p2.get(), triangle->_p3.get());
584         triangle->_e3 = addEdge(triangle, triangle->_p3.get(), triangle->_p1.get());
585 
586         triangle->update();
587 
588         _triangleSet.insert(triangle);
589 
590         return triangle;
591     }
592 
removeTriangle(Triangle * triangle)593     void removeTriangle(Triangle* triangle)
594     {
595         if (triangle->_p1.valid()) removePoint(triangle,triangle->_p1.get());
596         if (triangle->_p2.valid()) removePoint(triangle,triangle->_p2.get());
597         if (triangle->_p3.valid()) removePoint(triangle,triangle->_p3.get());
598 
599         if (triangle->_e1.valid()) removeEdge(triangle,triangle->_e1.get());
600         if (triangle->_e2.valid()) removeEdge(triangle,triangle->_e2.get());
601         if (triangle->_e3.valid()) removeEdge(triangle,triangle->_e3.get());
602 
603         _triangleSet.erase(triangle);
604     }
605 
replaceTrianglePoint(Triangle * triangle,Point * pOriginal,Point * pNew)606     void replaceTrianglePoint(Triangle* triangle, Point* pOriginal, Point* pNew)
607     {
608         if (triangle->_p1==pOriginal || triangle->_p2==pOriginal || triangle->_p3==pOriginal)
609         {
610             // fix the corner points to use the new point
611             if (triangle->_p1==pOriginal) triangle->_p1=pNew;
612             if (triangle->_p2==pOriginal) triangle->_p2=pNew;
613             if (triangle->_p3==pOriginal) triangle->_p3=pNew;
614 
615             // fixes the edges so they point to use the new point
616             triangle->_e1 = replaceEdgePoint(triangle->_e1.get(),pOriginal,pNew);
617             triangle->_e2 = replaceEdgePoint(triangle->_e2.get(),pOriginal,pNew);
618             triangle->_e3 = replaceEdgePoint(triangle->_e3.get(),pOriginal,pNew);
619 
620             // remove the triangle form the original point, and possibly the point if its the last triangle to use it
621             removePoint(triangle, pOriginal);
622 
623             // add the triangle to that point
624             addPoint(triangle,pNew);
625         }
626 
627     }
628 
testTriangle(Triangle * triangle)629     unsigned int testTriangle(Triangle* triangle)
630     {
631         unsigned int result = 0;
632         if (!(triangle->_p1))
633         {
634             OSG_NOTICE<<"testTriangle("<<triangle<<") _p1==NULL"<<std::endl;
635             ++result;
636         }
637         else if (triangle->_p1->_triangles.count(triangle)==0)
638         {
639             OSG_NOTICE<<"testTriangle("<<triangle<<") _p1->_triangles does not contain triangle"<<std::endl;
640             ++result;
641         }
642 
643         if (!(triangle->_p2))
644         {
645             OSG_NOTICE<<"testTriangle("<<triangle<<") _p2==NULL"<<std::endl;
646             ++result;
647         }
648         else if (triangle->_p2->_triangles.count(triangle)==0)
649         {
650             OSG_NOTICE<<"testTriangle("<<triangle<<") _p2->_triangles does not contain triangle"<<std::endl;
651             ++result;
652         }
653 
654         if (!(triangle->_p3))
655         {
656             OSG_NOTICE<<"testTriangle("<<triangle<<") _p3==NULL"<<std::endl;
657             ++result;
658         }
659         else if (triangle->_p3->_triangles.count(triangle)==0)
660         {
661             OSG_NOTICE<<"testTriangle("<<triangle<<") _p3->_triangles does not contain triangle"<<std::endl;
662             ++result;
663         }
664 
665         if (testEdge(triangle->_e1.get()))
666         {
667             ++result;
668             OSG_NOTICE<<"testTriangle("<<triangle<<") _e1 test failed"<<std::endl;
669         }
670 
671         if (testEdge(triangle->_e2.get()))
672         {
673             ++result;
674             OSG_NOTICE<<"testTriangle("<<triangle<<") _e2 test failed"<<std::endl;
675         }
676 
677         if (testEdge(triangle->_e3.get()))
678         {
679             OSG_NOTICE<<"testTriangle("<<triangle<<") _e3 test failed"<<std::endl;
680             ++result;
681         }
682 
683         return result;
684     }
685 
testAllTriangles()686     unsigned int testAllTriangles()
687     {
688         unsigned int numErrors = 0;
689         for(TriangleSet::iterator itr=_triangleSet.begin();
690             itr!=_triangleSet.end();
691             ++itr)
692         {
693             numErrors += testTriangle(const_cast<Triangle*>(itr->get()));
694         }
695         return numErrors;
696     }
697 
addEdge(Triangle * triangle,Point * p1,Point * p2)698     Edge* addEdge(Triangle* triangle, Point* p1, Point* p2)
699     {
700         // OSG_NOTICE<<"        addEdge("<<p1<<","<<p2<<")"<<std::endl;
701         osg::ref_ptr<Edge> edge = new Edge;
702         if (dereference_check_less(p1, p2))
703         {
704             edge->_p1 = p1;
705             edge->_p2 = p2;
706         }
707         else
708         {
709             edge->_p1 = p2;
710             edge->_p2 = p1;
711         }
712 
713         edge->setErrorMetric( computeErrorMetric( edge.get(), edge->_proposedPoint.get()));
714 
715         EdgeSet::iterator itr = _edgeSet.find(edge);
716         if (itr==_edgeSet.end())
717         {
718             // OSG_NOTICE<<"          addEdge("<<edge.get()<<") edge->_p1="<<edge->_p1.get()<<" _p2="<<edge->_p2.get()<<std::endl;
719             _edgeSet.insert(edge);
720         }
721         else
722         {
723             // OSG_NOTICE<<"          reuseEdge("<<edge.get()<<") edge->_p1="<<edge->_p1.get()<<" _p2="<<edge->_p2.get()<<std::endl;
724             edge = *itr;
725         }
726 
727         edge->addTriangle(triangle);
728 
729         return edge.get();
730     }
731 
removeEdge(Triangle * triangle,Edge * edge)732     void removeEdge(Triangle* triangle, Edge* edge)
733     {
734         EdgeSet::iterator itr = _edgeSet.find(edge);
735         if (itr!=_edgeSet.end())
736         {
737             edge->_triangles.erase(triangle);
738             if (edge->_triangles.empty())
739             {
740                 edge->_p1 = 0;
741                 edge->_p2 = 0;
742 
743                 // edge no longer in use, so need to delete.
744                 _edgeSet.erase(itr);
745             }
746         }
747     }
748 
replaceEdgePoint(Edge * edge,Point * pOriginal,Point * pNew)749     Edge* replaceEdgePoint(Edge* edge, Point* pOriginal, Point* pNew)
750     {
751         if (edge->_p1==pOriginal || edge->_p2==pOriginal)
752         {
753             EdgeSet::iterator itr = _edgeSet.find(edge);
754             if (itr!=_edgeSet.end())
755             {
756                 // remove the edge from the list, as its positoin in the list
757                 // may need to change once its values have been amended
758                 _edgeSet.erase(itr);
759             }
760 
761             // modify its values
762             if (edge->_p1==pOriginal) edge->_p1=pNew;
763             if (edge->_p2==pOriginal) edge->_p2=pNew;
764 
765             if (dereference_check_less(edge->_p2,edge->_p1))
766             {
767                 edge->_p1.swap(edge->_p2);
768             }
769 
770             itr = _edgeSet.find(edge);
771             if (itr!=_edgeSet.end())
772             {
773                 // reuse existing edge.
774                 edge = const_cast<Edge*>(itr->get());
775             }
776             else
777             {
778                 // put it back in.
779                 _edgeSet.insert(edge);
780             }
781             return edge;
782         }
783         else
784         {
785             return edge;
786         }
787 
788     }
789 
790 
collapseEdge(Edge * edge,Point * pNew)791     bool collapseEdge(Edge* edge, Point* pNew)
792     {
793         //if (edge->_triangles.size()<2) return false;
794         //if (edge->_triangles.size()>2) return false;
795 
796 #ifdef ORIGIANAL_CODE
797         if (edge->getMaxNormalDeviationOnEdgeCollapse()>1.0)
798         {
799             OSG_NOTICE<<"collapseEdge("<<edge<<") refused due to edge->getMaxNormalDeviationOnEdgeCollapse() = "<<edge->getMaxNormalDeviationOnEdgeCollapse()<<std::endl;
800            return false;
801         }
802         else
803         {
804             //OSG_NOTICE<<"collapseEdge("<<edge<<") edge->getMaxNormalDeviationOnEdgeCollapse() = "<<edge->getMaxNormalDeviationOnEdgeCollapse()<<std::endl;
805         }
806 #endif
807 
808         typedef std::set< osg::ref_ptr<Edge> > LocalEdgeList;
809 
810         osg::ref_ptr<Edge> keep_edge_locally_referenced_to_prevent_premature_deletion = edge;
811         osg::ref_ptr<Point> keep_point_locally_referenced_to_prevent_premature_deletion = pNew;
812         osg::ref_ptr<Point> edge_p1 = edge->_p1;
813         osg::ref_ptr<Point> edge_p2 = edge->_p2;
814 
815         TriangleMap  triangleMap;
816         TriangleList triangles_p1;
817         TriangleList triangles_p2;
818         LocalEdgeList oldEdges;
819 
820 
821         if (edge_p1 != pNew)
822         {
823             for(TriangleSet::iterator itr=edge_p1->_triangles.begin();
824                 itr!=edge_p1->_triangles.end();
825                 ++itr)
826             {
827                 if (edge->_triangles.count(*itr)==0)
828                 {
829                     Triangle* triangle = const_cast<Triangle*>(itr->get());
830                     triangles_p1.push_back(triangle);
831                     oldEdges.insert(triangle->_e1);
832                     oldEdges.insert(triangle->_e2);
833                     oldEdges.insert(triangle->_e3);
834                 }
835             }
836 
837             //triangles_p1 = edge_p1->_triangles;
838         }
839 
840         if (edge_p2 != pNew)
841         {
842             for(TriangleSet::iterator itr=edge_p2->_triangles.begin();
843                 itr!=edge_p2->_triangles.end();
844                 ++itr)
845             {
846                 if (edge->_triangles.count(*itr)==0)
847                 {
848                     Triangle* triangle = const_cast<Triangle*>(itr->get());
849                     triangles_p2.push_back(triangle);
850                     oldEdges.insert(triangle->_e1);
851                     oldEdges.insert(triangle->_e2);
852                     oldEdges.insert(triangle->_e3);
853                 }
854             }
855             //triangles_p2 = edge_p2->_triangles;
856         }
857 
858         for(LocalEdgeList::iterator oeitr=oldEdges.begin();
859             oeitr!=oldEdges.end();
860             ++oeitr)
861         {
862             _edgeSet.erase(*oeitr);
863 
864             const_cast<Edge*>(oeitr->get())->setErrorMetric(0.0f);
865 
866             _edgeSet.insert(*oeitr);
867         }
868 
869         TriangleList::iterator titr_p1, titr_p2;
870 
871         for(titr_p1 = triangles_p1.begin();
872             titr_p1 != triangles_p1.end();
873             ++titr_p1)
874         {
875             removeTriangle(const_cast<Triangle*>(titr_p1->get()));
876         }
877 
878         for(titr_p2 = triangles_p2.begin();
879             titr_p2 != triangles_p2.end();
880             ++titr_p2)
881         {
882             removeTriangle(const_cast<Triangle*>(titr_p2->get()));
883         }
884 
885         //OSG_NOTICE<<"  pNew="<<pNew<<"\tedge_p1"<<edge_p1.get()<<"\tedge_p2"<<edge_p2.get()<<std::endl;
886 
887         // we copy the edge's _triangles and interate the copy of the triangle set to avoid invalidating iterators.
888         TriangleSet trianglesToRemove = edge->_triangles;
889         for(TriangleSet::iterator teitr=trianglesToRemove.begin();
890             teitr!=trianglesToRemove.end();
891             ++teitr)
892         {
893             Triangle* triangle = const_cast<Triangle*>(teitr->get());
894             removeTriangle(triangle);
895         }
896 
897         LocalEdgeList newEdges;
898 
899 
900         for(titr_p1 = triangles_p1.begin();
901             titr_p1 != triangles_p1.end();
902             ++titr_p1)
903         {
904             Triangle* triangle = const_cast<Triangle*>(titr_p1->get());
905 
906             Point* p1 = (triangle->_p1==edge_p1 || triangle->_p1==edge_p2)? pNew : triangle->_p1.get();
907             Point* p2 = (triangle->_p2==edge_p1 || triangle->_p2==edge_p2)? pNew : triangle->_p2.get();
908             Point* p3 = (triangle->_p3==edge_p1 || triangle->_p3==edge_p2)? pNew : triangle->_p3.get();
909 
910             Triangle* newTri = addTriangle(p1,p2,p3);
911 
912             if (newTri)
913             {
914                 newEdges.insert(newTri->_e1);
915                 newEdges.insert(newTri->_e2);
916                 newEdges.insert(newTri->_e3);
917             }
918         }
919 
920 
921         for(titr_p2 = triangles_p2.begin();
922             titr_p2 != triangles_p2.end();
923             ++titr_p2)
924         {
925             Triangle* triangle = const_cast<Triangle*>(titr_p2->get());
926 
927             Point* p1 = (triangle->_p1==edge_p1 || triangle->_p1==edge_p2)? pNew : triangle->_p1.get();
928             Point* p2 = (triangle->_p2==edge_p1 || triangle->_p2==edge_p2)? pNew : triangle->_p2.get();
929             Point* p3 = (triangle->_p3==edge_p1 || triangle->_p3==edge_p2)? pNew : triangle->_p3.get();
930 
931             Triangle* newTri = addTriangle(p1,p2,p3);
932 
933             if (newTri)
934             {
935                 newEdges.insert(newTri->_e1);
936                 newEdges.insert(newTri->_e2);
937                 newEdges.insert(newTri->_e3);
938             }
939         }
940 
941         LocalEdgeList edges2UpdateErrorMetric;
942 
943         LocalEdgeList::const_iterator newEdgeIt(newEdges.begin());
944         while (newEdgeIt != newEdges.end())
945         {
946             const Point* p = 0;
947             if (newEdgeIt->get()->_p1.get() != pNew)
948                 p = newEdgeIt->get()->_p1.get();
949             else
950                 p = newEdgeIt->get()->_p2.get();
951 
952             TriangleSet::const_iterator triangleIt(p->_triangles.begin());
953             while (triangleIt != p->_triangles.end())
954             {
955                 const Triangle* triangle = triangleIt->get();
956                 if (triangle->_e1->_p1 == p || triangle->_e1->_p2 == p)
957                     edges2UpdateErrorMetric.insert(triangle->_e1);
958                 if (triangle->_e2->_p1 == p || triangle->_e2->_p2 == p)
959                     edges2UpdateErrorMetric.insert(triangle->_e2);
960                 if (triangle->_e3->_p1 == p || triangle->_e3->_p2 == p)
961                     edges2UpdateErrorMetric.insert(triangle->_e3);
962 
963                 ++triangleIt;
964             }
965 
966             ++newEdgeIt;
967         }
968 
969         edges2UpdateErrorMetric.insert(newEdges.begin(), newEdges.end());
970 
971         // OSG_NOTICE<<"Edges to recalibarate "<<edges2UpdateErrorMetric.size()<<std::endl;
972 
973         for(LocalEdgeList::iterator itr=edges2UpdateErrorMetric.begin();
974             itr!=edges2UpdateErrorMetric.end();
975             ++itr)
976         {
977             //OSG_NOTICE<<"updateErrorMetricForEdge("<<itr->get()<<")"<<std::endl;
978             updateErrorMetricForEdge(const_cast<Edge*>(itr->get()));
979         }
980 
981         return true;
982     }
983 
984 
divideEdge(Edge * edge,Point * pNew)985     bool divideEdge(Edge* edge, Point* pNew)
986     {
987          // OSG_NOTICE<<"divideEdge("<<edge<<") before _edgeSet.size()="<<_edgeSet.size()<<" _triangleSet.size()="<<_triangleSet.size()<<std::endl;
988 
989         // first collect the triangles associaged with edges that need deleting
990         osg::ref_ptr<Edge> keep_edge_locally_referenced_to_prevent_premature_deletion = edge;
991         TriangleSet triangles = edge->_triangles;
992 
993         // OSG_NOTICE<<"   numTriangles on edges "<<triangles.size()<<std::endl;
994 
995         // unsigned int numTriangles1 = _triangleSet.size();
996         // unsigned int numBoundaryEdges1 = computeNumBoundaryEdges();
997         // unsigned int numEdges1 = _edgeSet.size();
998 
999         typedef std::set< osg::ref_ptr<Edge> > LocalEdgeList;
1000         LocalEdgeList edges2UpdateErrorMetric;
1001         TriangleSet::iterator titr;
1002 
1003 
1004         // for each deleted triangle insert two new triangles
1005         for(titr = triangles.begin();
1006             titr != triangles.end();
1007             ++titr)
1008         {
1009             Triangle* tri = const_cast<Triangle*>(titr->get());
1010             int edgeToReplace = 0;
1011             if (edge->_p1 == tri->_p1)
1012             {
1013                 if (edge->_p2 == tri->_p2.get()) edgeToReplace = 1; // edge p1,p2
1014                 else if (edge->_p2 == tri->_p3.get()) edgeToReplace = 3; // edge p3, p1
1015             }
1016             else if (edge->_p1 == tri->_p2.get())
1017             {
1018                 if (edge->_p2 == tri->_p3.get()) edgeToReplace = 2; // edge p2,p3
1019                 else if (edge->_p2 == tri->_p1.get()) edgeToReplace = 1; // edge p1, p2
1020             }
1021             else if (edge->_p1 == tri->_p3.get())
1022             {
1023                 if (edge->_p2 == tri->_p1.get()) edgeToReplace = 3; // edge p3,p1
1024                 else if (edge->_p2 == tri->_p2.get()) edgeToReplace = 2; // edge p2, p3
1025             }
1026 
1027             Triangle* newTri1 = 0;
1028             Triangle* newTri2 = 0;
1029             switch(edgeToReplace)
1030             {
1031                 case(0): // error, shouldn't get here.
1032                     OSG_NOTICE<<"Error EdgeCollapse::divideEdge(Edge*,Point*) passed invalid edge."<<std::endl;
1033                     return false;
1034                 case(1): // p1, p2
1035                     // OSG_NOTICE<<"   // p1, p2 "<<std::endl;
1036                     // OSG_NOTICE<<"   newTri1 = addTriangle(tri->_p1.get(), pNew, tri->_p3.get());"<<std::endl;
1037                     newTri1 = addTriangle(tri->_p1.get(), pNew, tri->_p3.get());
1038                     // OSG_NOTICE<<"   newTri2 = addTriangle(pNew, tri->_p2.get(), tri->_p3.get());"<<std::endl;
1039                     newTri2 = addTriangle(pNew, tri->_p2.get(), tri->_p3.get());
1040                     break;
1041                 case(2): // p2, p3
1042                     // OSG_NOTICE<<"   // p2, p3"<<std::endl;
1043                     // OSG_NOTICE<<"   newTri1 = addTriangle(tri->_p1.get(), tri->_p2.get(), pNew);"<<std::endl;
1044                     newTri1 = addTriangle(tri->_p1.get(), tri->_p2.get(), pNew);
1045                     //OSG_NOTICE<<"   newTri2 = addTriangle(tri->_p1.get(), pNew, tri->_p3.get());"<<std::endl;
1046                     newTri2 = addTriangle(tri->_p1.get(), pNew, tri->_p3.get());
1047                     break;
1048                 case(3): // p3, p1
1049                     // OSG_NOTICE<<"   // p3, p1"<<std::endl;
1050                     // OSG_NOTICE<<"   newTri1 = addTriangle(tri->_p1.get(), tri->_p2.get(), pNew);"<<std::endl;
1051                     newTri1 = addTriangle(tri->_p1.get(), tri->_p2.get(), pNew);
1052                     // OSG_NOTICE<<"   newTri2 = addTriangle(pNew, tri->_p2.get(), tri->_p3.get());"<<std::endl;
1053                     newTri2 = addTriangle(pNew, tri->_p2.get(), tri->_p3.get());
1054                     break;
1055             }
1056 
1057             if (newTri1)
1058             {
1059                 edges2UpdateErrorMetric.insert(newTri1->_e1.get());
1060                 edges2UpdateErrorMetric.insert(newTri1->_e2.get());
1061                 edges2UpdateErrorMetric.insert(newTri1->_e3.get());
1062             }
1063             if (newTri2)
1064             {
1065                 edges2UpdateErrorMetric.insert(newTri2->_e1.get());
1066                 edges2UpdateErrorMetric.insert(newTri2->_e2.get());
1067                 edges2UpdateErrorMetric.insert(newTri2->_e3.get());
1068             }
1069         }
1070 
1071         // unsigned int numTriangles2 = _triangleSet.size();
1072         // unsigned int numEdges2 = _edgeSet.size();
1073         // unsigned int numBoundaryEdges2 = computeNumBoundaryEdges();
1074 
1075         // remove all the triangles associated with edge
1076         for(titr = triangles.begin();
1077             titr != triangles.end();
1078             ++titr)
1079         {
1080             removeTriangle(const_cast<Triangle*>(titr->get()));
1081         }
1082 
1083         for(LocalEdgeList::iterator itr=edges2UpdateErrorMetric.begin();
1084             itr!=edges2UpdateErrorMetric.end();
1085             ++itr)
1086         {
1087             //OSG_NOTICE<<"updateErrorMetricForEdge("<<itr->get()<<")"<<std::endl;
1088             if (itr->valid()) updateErrorMetricForEdge(const_cast<Edge*>(itr->get()));
1089         }
1090 
1091         // unsigned int numBoundaryEdges3 = computeNumBoundaryEdges();
1092         // unsigned int numEdges3 = _edgeSet.size();
1093         // unsigned int numTriangles3 = _triangleSet.size();
1094 
1095         // OSG_NOTICE<<"   numTriangles1="<<numTriangles1<<"   numTriangles2="<<numTriangles2<<"   numTriangles3="<<numTriangles3<<std::endl;
1096         // OSG_NOTICE<<"   numEdges1="<<numEdges1<<"   numEdges2="<<numEdges2<<"   numEdges3="<<numEdges3<<std::endl;
1097         // OSG_NOTICE<<"   numBoundaryEdges1="<<numBoundaryEdges1<<"   numBoundaryEdges2="<<numBoundaryEdges2<<"   numBoundaryEdges3="<<numBoundaryEdges3<<std::endl;
1098         // OSG_NOTICE<<"divideEdge("<<edge<<") after _edgeSet.size()="<<_edgeSet.size()<<" _triangleSet.size()="<<_triangleSet.size()<<std::endl;
1099 
1100         return true;
1101     }
1102 
testEdge(Edge * edge)1103     unsigned int testEdge(Edge* edge)
1104     {
1105         unsigned int numErrors = 0;
1106         for(TriangleSet::iterator teitr=edge->_triangles.begin();
1107             teitr!=edge->_triangles.end();
1108             ++teitr)
1109         {
1110             Triangle* triangle = const_cast<Triangle*>(teitr->get());
1111             if (!(triangle->_e1 == edge || triangle->_e2 == edge || triangle->_e3 == edge))
1112             {
1113                 OSG_NOTICE<<"testEdge("<<edge<<"). triangle != point back to this edge"<<std::endl;
1114                 OSG_NOTICE<<"                     triangle->_e1=="<<triangle->_e1.get()<<std::endl;
1115                 OSG_NOTICE<<"                     triangle->_e2=="<<triangle->_e2.get()<<std::endl;
1116                 OSG_NOTICE<<"                     triangle->_e3=="<<triangle->_e3.get()<<std::endl;
1117                 ++numErrors;
1118             }
1119         }
1120 
1121         if (edge->_triangles.empty())
1122         {
1123             OSG_NOTICE<<"testEdge("<<edge<<")._triangles is empty"<<std::endl;
1124             ++numErrors;
1125         }
1126         return numErrors;
1127     }
1128 
testAllEdges()1129     unsigned int testAllEdges()
1130     {
1131         unsigned int numErrors = 0;
1132         for(EdgeSet::iterator itr = _edgeSet.begin();
1133             itr!=_edgeSet.end();
1134             ++itr)
1135         {
1136             numErrors += testEdge(const_cast<Edge*>(itr->get()));
1137         }
1138         return numErrors;
1139     }
1140 
computeNumBoundaryEdges()1141     unsigned int computeNumBoundaryEdges()
1142     {
1143         unsigned int numBoundaryEdges = 0;
1144         for(EdgeSet::iterator itr = _edgeSet.begin();
1145             itr!=_edgeSet.end();
1146             ++itr)
1147         {
1148             if ((*itr)->isBoundaryEdge()) ++numBoundaryEdges;
1149         }
1150         return numBoundaryEdges;
1151     }
1152 
1153 
addPoint(Triangle * triangle,unsigned int p1)1154     Point* addPoint(Triangle* triangle, unsigned int p1)
1155     {
1156         return addPoint(triangle,_originalPointList[p1].get());
1157     }
1158 
addPoint(Triangle * triangle,Point * point)1159     Point* addPoint(Triangle* triangle, Point* point)
1160     {
1161 
1162         PointSet::iterator itr = _pointSet.find(point);
1163         if (itr==_pointSet.end())
1164         {
1165             //OSG_NOTICE<<"  addPoint("<<point.get()<<")"<<std::endl;
1166             _pointSet.insert(point);
1167         }
1168         else
1169         {
1170             point = const_cast<Point*>(itr->get());
1171             //OSG_NOTICE<<"  reusePoint("<<point.get()<<")"<<std::endl;
1172         }
1173 
1174         point->_triangles.insert(triangle);
1175 
1176         return point;
1177     }
1178 
removePoint(Triangle * triangle,Point * point)1179     void removePoint(Triangle* triangle, Point* point)
1180     {
1181         PointSet::iterator itr = _pointSet.find(point);
1182         if (itr!=_pointSet.end())
1183         {
1184             point->_triangles.erase(triangle);
1185 
1186             if (point->_triangles.empty())
1187             {
1188                 // point no longer in use, so need to delete.
1189                 _pointSet.erase(itr);
1190             }
1191         }
1192 
1193     }
1194 
testPoint(Point * point)1195     unsigned int testPoint(Point* point)
1196     {
1197         unsigned int numErrors = 0;
1198 
1199         for(TriangleSet::iterator itr=point->_triangles.begin();
1200             itr!=point->_triangles.end();
1201             ++itr)
1202         {
1203             Triangle* triangle = const_cast<Triangle*>(itr->get());
1204             if (!(triangle->_p1 == point || triangle->_p2 == point || triangle->_p3 == point))
1205             {
1206                 OSG_NOTICE<<"testPoint("<<point<<") error, triangle "<<triangle<<" does not point back to this point"<<std::endl;
1207                 OSG_NOTICE<<"             triangle->_p1 "<<triangle->_p1.get()<<std::endl;
1208                 OSG_NOTICE<<"             triangle->_p2 "<<triangle->_p2.get()<<std::endl;
1209                 OSG_NOTICE<<"             triangle->_p3 "<<triangle->_p3.get()<<std::endl;
1210                 ++numErrors;
1211             }
1212         }
1213 
1214         return numErrors;
1215     }
1216 
testAllPoints()1217     unsigned int testAllPoints()
1218     {
1219         unsigned int numErrors = 0;
1220         for(PointSet::iterator itr = _pointSet.begin();
1221             itr!=_pointSet.end();
1222             ++itr)
1223         {
1224             numErrors += testPoint(const_cast<Point*>(itr->get()));
1225         }
1226         return numErrors;
1227     }
1228 
1229 //protected:
1230 
1231     typedef std::vector< osg::ref_ptr<osg::Array> > ArrayList;
1232 
1233     osg::Geometry*                  _geometry;
1234 
1235     bool                            _computeErrorMetricUsingLength;
1236     EdgeSet                         _edgeSet;
1237     TriangleSet                     _triangleSet;
1238     PointSet                        _pointSet;
1239     PointList                       _originalPointList;
1240 
1241 };
1242 
1243 struct CollectTriangleOperator
1244 {
1245 
CollectTriangleOperatorCollectTriangleOperator1246     CollectTriangleOperator():_ec(0) {}
1247 
setEdgeCollapseCollectTriangleOperator1248     void setEdgeCollapse(EdgeCollapse* ec) { _ec = ec; }
1249 
1250     EdgeCollapse* _ec;
1251 
1252     // for use  in the triangle functor.
operator ()CollectTriangleOperator1253     inline void operator()(unsigned int p1, unsigned int p2, unsigned int p3)
1254     {
1255         _ec->addTriangle(p1,p2,p3);
1256     }
1257 
1258 };
1259 
~EdgeCollapse()1260 EdgeCollapse::~EdgeCollapse()
1261 {
1262     std::for_each(_edgeSet.begin(),_edgeSet.end(),dereference_clear());
1263 
1264     std::for_each(_triangleSet.begin(),_triangleSet.end(),dereference_clear());
1265     std::for_each(_pointSet.begin(),_pointSet.end(),dereference_clear());
1266     std::for_each(_originalPointList.begin(),_originalPointList.end(),dereference_clear());
1267 }
1268 
1269 
1270 typedef osg::TriangleIndexFunctor<CollectTriangleOperator> CollectTriangleIndexFunctor;
1271 
1272 class CopyArrayToPointsVisitor : public osg::ArrayVisitor
1273 {
1274     public:
CopyArrayToPointsVisitor(EdgeCollapse::PointList & pointList)1275         CopyArrayToPointsVisitor(EdgeCollapse::PointList& pointList):
1276             _pointList(pointList) {}
1277 
1278         template<class T>
copy(T & array)1279         void copy(T& array)
1280         {
1281             if (_pointList.size()!=array.size()) return;
1282 
1283             for(unsigned int i=0;i<_pointList.size();++i)
1284                 _pointList[i]->_attributes.push_back((float)array[i]);
1285         }
1286 
apply(osg::Array &)1287         virtual void apply(osg::Array&) {}
apply(osg::ByteArray & array)1288         virtual void apply(osg::ByteArray& array) { copy(array); }
apply(osg::ShortArray & array)1289         virtual void apply(osg::ShortArray& array) { copy(array); }
apply(osg::IntArray & array)1290         virtual void apply(osg::IntArray& array) { copy(array); }
apply(osg::UByteArray & array)1291         virtual void apply(osg::UByteArray& array) { copy(array); }
apply(osg::UShortArray & array)1292         virtual void apply(osg::UShortArray& array) { copy(array); }
apply(osg::UIntArray & array)1293         virtual void apply(osg::UIntArray& array) { copy(array); }
apply(osg::FloatArray & array)1294         virtual void apply(osg::FloatArray& array) { copy(array); }
1295 
apply(osg::Vec4ubArray & array)1296         virtual void apply(osg::Vec4ubArray& array)
1297         {
1298             if (_pointList.size()!=array.size()) return;
1299 
1300             for(unsigned int i=0;i<_pointList.size();++i)
1301             {
1302                 osg::Vec4ub& value = array[i];
1303                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1304                 attributes.push_back((float)value.r());
1305                 attributes.push_back((float)value.g());
1306                 attributes.push_back((float)value.b());
1307                 attributes.push_back((float)value.a());
1308             }
1309         }
1310 
apply(osg::Vec2Array & array)1311         virtual void apply(osg::Vec2Array& array)
1312         {
1313             if (_pointList.size()!=array.size()) return;
1314 
1315             for(unsigned int i=0;i<_pointList.size();++i)
1316             {
1317                 osg::Vec2& value = array[i];
1318                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1319                 attributes.push_back(value.x());
1320                 attributes.push_back(value.y());
1321             }
1322         }
1323 
apply(osg::Vec3Array & array)1324         virtual void apply(osg::Vec3Array& array)
1325         {
1326             if (_pointList.size()!=array.size()) return;
1327 
1328             for(unsigned int i=0;i<_pointList.size();++i)
1329             {
1330                 osg::Vec3& value = array[i];
1331                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1332                 attributes.push_back(value.x());
1333                 attributes.push_back(value.y());
1334                 attributes.push_back(value.z());
1335             }
1336         }
1337 
apply(osg::Vec4Array & array)1338         virtual void apply(osg::Vec4Array& array)
1339         {
1340             if (_pointList.size()!=array.size()) return;
1341 
1342             for(unsigned int i=0;i<_pointList.size();++i)
1343             {
1344                 osg::Vec4& value = array[i];
1345                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1346                 attributes.push_back(value.x());
1347                 attributes.push_back(value.y());
1348                 attributes.push_back(value.z());
1349                 attributes.push_back(value.w());
1350             }
1351         }
1352 
1353         EdgeCollapse::PointList& _pointList;
1354 
1355 
1356     protected:
1357 
operator =(const CopyArrayToPointsVisitor &)1358         CopyArrayToPointsVisitor& operator = (const CopyArrayToPointsVisitor&) { return *this; }
1359 };
1360 
1361 class CopyVertexArrayToPointsVisitor : public osg::ArrayVisitor
1362 {
1363     public:
CopyVertexArrayToPointsVisitor(EdgeCollapse::PointList & pointList)1364         CopyVertexArrayToPointsVisitor(EdgeCollapse::PointList& pointList):
1365             _pointList(pointList) {}
1366 
apply(osg::Vec2Array & array)1367         virtual void apply(osg::Vec2Array& array)
1368         {
1369             if (_pointList.size()!=array.size()) return;
1370 
1371             for(unsigned int i=0;i<_pointList.size();++i)
1372             {
1373                 _pointList[i] = new EdgeCollapse::Point;
1374                 _pointList[i]->_index = i;
1375 
1376                 osg::Vec2& value = array[i];
1377                 osg::Vec3& vertex = _pointList[i]->_vertex;
1378                 vertex.set(value.x(),value.y(),0.0f);
1379             }
1380         }
1381 
apply(osg::Vec3Array & array)1382         virtual void apply(osg::Vec3Array& array)
1383         {
1384             if (_pointList.size()!=array.size()) return;
1385 
1386             for(unsigned int i=0;i<_pointList.size();++i)
1387             {
1388                 _pointList[i] = new EdgeCollapse::Point;
1389                 _pointList[i]->_index = i;
1390 
1391                 _pointList[i]->_vertex = array[i];
1392             }
1393         }
1394 
apply(osg::Vec4Array & array)1395         virtual void apply(osg::Vec4Array& array)
1396         {
1397             if (_pointList.size()!=array.size()) return;
1398 
1399             for(unsigned int i=0;i<_pointList.size();++i)
1400             {
1401                 _pointList[i] = new EdgeCollapse::Point;
1402                 _pointList[i]->_index = i;
1403 
1404                 osg::Vec4& value = array[i];
1405                 osg::Vec3& vertex = _pointList[i]->_vertex;
1406                 vertex.set(value.x()/value.w(),value.y()/value.w(),value.z()/value.w());
1407             }
1408         }
1409 
1410         EdgeCollapse::PointList& _pointList;
1411 
1412     protected:
1413 
operator =(const CopyVertexArrayToPointsVisitor &)1414         CopyVertexArrayToPointsVisitor& operator = (const CopyVertexArrayToPointsVisitor&) { return *this; }
1415 
1416 };
1417 
setGeometry(osg::Geometry * geometry,const Simplifier::IndexList & protectedPoints)1418 void EdgeCollapse::setGeometry(osg::Geometry* geometry, const Simplifier::IndexList& protectedPoints)
1419 {
1420     _geometry = geometry;
1421 
1422     // check to see if vertex attributes indices exists, if so expand them to remove them
1423     if (_geometry->containsSharedArrays())
1424     {
1425         // removing coord indices
1426         OSG_INFO<<"EdgeCollapse::setGeometry(..): Duplicate shared arrays"<<std::endl;
1427         _geometry->duplicateSharedArrays();
1428     }
1429 
1430     unsigned int numVertices = geometry->getVertexArray()->getNumElements();
1431 
1432     _originalPointList.resize(numVertices);
1433 
1434     // copy vertices across to local point list
1435     CopyVertexArrayToPointsVisitor copyVertexArrayToPoints(_originalPointList);
1436     _geometry->getVertexArray()->accept(copyVertexArrayToPoints);
1437 
1438     // copy other per vertex attributes across to local point list.
1439     CopyArrayToPointsVisitor        copyArrayToPoints(_originalPointList);
1440 
1441     for(unsigned int ti=0;ti<_geometry->getNumTexCoordArrays();++ti)
1442     {
1443         if (_geometry->getTexCoordArray(ti))
1444             geometry->getTexCoordArray(ti)->accept(copyArrayToPoints);
1445     }
1446 
1447     if (_geometry->getNormalArray() && _geometry->getNormalArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1448         geometry->getNormalArray()->accept(copyArrayToPoints);
1449 
1450     if (_geometry->getColorArray() && _geometry->getColorArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1451         geometry->getColorArray()->accept(copyArrayToPoints);
1452 
1453     if (_geometry->getSecondaryColorArray() && _geometry->getSecondaryColorArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1454         geometry->getSecondaryColorArray()->accept(copyArrayToPoints);
1455 
1456     if (_geometry->getFogCoordArray() && _geometry->getFogCoordArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1457         geometry->getFogCoordArray()->accept(copyArrayToPoints);
1458 
1459     for(unsigned int vi=0;vi<_geometry->getNumVertexAttribArrays();++vi)
1460     {
1461         if (_geometry->getVertexAttribArray(vi) &&  _geometry->getVertexAttribArray(vi)->getBinding()==osg::Array::BIND_PER_VERTEX)
1462             geometry->getVertexAttribArray(vi)->accept(copyArrayToPoints);
1463     }
1464 
1465     // now set the protected points up.
1466     for(Simplifier::IndexList::const_iterator pitr=protectedPoints.begin();
1467         pitr!=protectedPoints.end();
1468         ++pitr)
1469     {
1470         _originalPointList[*pitr]->_protected = true;
1471     }
1472 
1473 
1474     CollectTriangleIndexFunctor collectTriangles;
1475     collectTriangles.setEdgeCollapse(this);
1476 
1477     _geometry->accept(collectTriangles);
1478 
1479 }
1480 
1481 
1482 
1483 class CopyPointsToArrayVisitor : public osg::ArrayVisitor
1484 {
1485     public:
CopyPointsToArrayVisitor(EdgeCollapse::PointList & pointList)1486         CopyPointsToArrayVisitor(EdgeCollapse::PointList& pointList):
1487             _pointList(pointList),
1488             _index(0) {}
1489 
1490 
1491         template<typename T,typename R>
copy(T & array,R)1492         void copy(T& array, R /*dummy*/)
1493         {
1494             array.resize(_pointList.size());
1495 
1496             for(unsigned int i=0;i<_pointList.size();++i)
1497             {
1498                 if (_index<_pointList[i]->_attributes.size())
1499                 {
1500                     float val = (_pointList[i]->_attributes[_index]);
1501                     array[i] = R (val);
1502                 }
1503             }
1504 
1505             ++_index;
1506         }
1507 
1508         // use local typedefs if usinged char,short and int to get round gcc 3.3.1 problem with defining unsigned short()
1509         typedef unsigned char dummy_uchar;
1510         typedef unsigned short dummy_ushort;
1511         typedef unsigned int dummy_uint;
1512 
apply(osg::Array &)1513         virtual void apply(osg::Array&) {}
apply(osg::ByteArray & array)1514         virtual void apply(osg::ByteArray& array) { copy(array, char());}
apply(osg::ShortArray & array)1515         virtual void apply(osg::ShortArray& array) { copy(array, short()); }
apply(osg::IntArray & array)1516         virtual void apply(osg::IntArray& array) { copy(array, int()); }
apply(osg::UByteArray & array)1517         virtual void apply(osg::UByteArray& array) { copy(array, dummy_uchar()); }
apply(osg::UShortArray & array)1518         virtual void apply(osg::UShortArray& array) { copy(array,dummy_ushort()); }
apply(osg::UIntArray & array)1519         virtual void apply(osg::UIntArray& array) { copy(array, dummy_uint()); }
apply(osg::FloatArray & array)1520         virtual void apply(osg::FloatArray& array) { copy(array, float()); }
1521 
apply(osg::Vec4ubArray & array)1522         virtual void apply(osg::Vec4ubArray& array)
1523         {
1524             array.resize(_pointList.size());
1525 
1526             for(unsigned int i=0;i<_pointList.size();++i)
1527             {
1528                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1529                 array[i].set((unsigned char)attributes[_index],
1530                              (unsigned char)attributes[_index+1],
1531                              (unsigned char)attributes[_index+2],
1532                              (unsigned char)attributes[_index+3]);
1533             }
1534             _index += 4;
1535         }
1536 
apply(osg::Vec2Array & array)1537         virtual void apply(osg::Vec2Array& array)
1538         {
1539             array.resize(_pointList.size());
1540 
1541             for(unsigned int i=0;i<_pointList.size();++i)
1542             {
1543                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1544                 if (_index+1<attributes.size()) array[i].set(attributes[_index],attributes[_index+1]);
1545             }
1546             _index += 2;
1547         }
1548 
apply(osg::Vec3Array & array)1549         virtual void apply(osg::Vec3Array& array)
1550         {
1551             array.resize(_pointList.size());
1552 
1553             for(unsigned int i=0;i<_pointList.size();++i)
1554             {
1555                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1556                 if (_index+2<attributes.size()) array[i].set(attributes[_index],attributes[_index+1],attributes[_index+2]);
1557             }
1558             _index += 3;
1559         }
1560 
apply(osg::Vec4Array & array)1561         virtual void apply(osg::Vec4Array& array)
1562         {
1563             array.resize(_pointList.size());
1564 
1565             for(unsigned int i=0;i<_pointList.size();++i)
1566             {
1567                 EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1568                 if (_index+3<attributes.size()) array[i].set(attributes[_index],attributes[_index+1],attributes[_index+2],attributes[_index+3]);
1569             }
1570             _index += 4;
1571         }
1572 
1573         EdgeCollapse::PointList& _pointList;
1574         unsigned int _index;
1575 
1576     protected:
1577 
operator =(CopyPointsToArrayVisitor &)1578         CopyPointsToArrayVisitor& operator = (CopyPointsToArrayVisitor&) { return *this; }
1579 };
1580 
1581 class NormalizeArrayVisitor : public osg::ArrayVisitor
1582 {
1583     public:
NormalizeArrayVisitor()1584         NormalizeArrayVisitor() {}
1585 
1586         template<typename Itr>
normalize(Itr begin,Itr end)1587         void normalize(Itr begin, Itr end)
1588         {
1589             for(Itr itr = begin;
1590                 itr != end;
1591                 ++itr)
1592             {
1593                 itr->normalize();
1594             }
1595         }
1596 
apply(osg::Vec2Array & array)1597         virtual void apply(osg::Vec2Array& array) { normalize(array.begin(),array.end()); }
apply(osg::Vec3Array & array)1598         virtual void apply(osg::Vec3Array& array) { normalize(array.begin(),array.end()); }
apply(osg::Vec4Array & array)1599         virtual void apply(osg::Vec4Array& array) { normalize(array.begin(),array.end()); }
1600 
1601 };
1602 
1603 class CopyPointsToVertexArrayVisitor : public osg::ArrayVisitor
1604 {
1605     public:
CopyPointsToVertexArrayVisitor(EdgeCollapse::PointList & pointList)1606         CopyPointsToVertexArrayVisitor(EdgeCollapse::PointList& pointList):
1607             _pointList(pointList) {}
1608 
apply(osg::Vec2Array & array)1609         virtual void apply(osg::Vec2Array& array)
1610         {
1611             array.resize(_pointList.size());
1612 
1613             for(unsigned int i=0;i<_pointList.size();++i)
1614             {
1615                 _pointList[i]->_index = i;
1616                 osg::Vec3& vertex = _pointList[i]->_vertex;
1617                 array[i].set(vertex.x(),vertex.y());
1618             }
1619         }
1620 
apply(osg::Vec3Array & array)1621         virtual void apply(osg::Vec3Array& array)
1622         {
1623             array.resize(_pointList.size());
1624 
1625             for(unsigned int i=0;i<_pointList.size();++i)
1626             {
1627                 _pointList[i]->_index = i;
1628                 array[i] = _pointList[i]->_vertex;
1629             }
1630         }
1631 
apply(osg::Vec4Array & array)1632         virtual void apply(osg::Vec4Array& array)
1633         {
1634             array.resize(_pointList.size());
1635 
1636             for(unsigned int i=0;i<_pointList.size();++i)
1637             {
1638                 _pointList[i]->_index = i;
1639                 osg::Vec3& vertex = _pointList[i]->_vertex;
1640                 array[i].set(vertex.x(),vertex.y(),vertex.z(),1.0f);
1641             }
1642         }
1643 
1644         EdgeCollapse::PointList& _pointList;
1645 
1646     protected:
1647 
operator =(const CopyPointsToVertexArrayVisitor &)1648         CopyPointsToVertexArrayVisitor& operator = (const CopyPointsToVertexArrayVisitor&) { return *this; }
1649 };
1650 
1651 
copyBackToGeometry()1652 void EdgeCollapse::copyBackToGeometry()
1653 {
1654 
1655     // rebuild the _pointList from the _pointSet
1656     _originalPointList.clear();
1657     std::copy(_pointSet.begin(),_pointSet.end(),std::back_inserter(_originalPointList));
1658 
1659     // copy vertices across to local point list
1660     CopyPointsToVertexArrayVisitor copyVertexArrayToPoints(_originalPointList);
1661     _geometry->getVertexArray()->accept(copyVertexArrayToPoints);
1662 
1663     // copy other per vertex attributes across to local point list.
1664     CopyPointsToArrayVisitor  copyArrayToPoints(_originalPointList);
1665 
1666     for(unsigned int ti=0;ti<_geometry->getNumTexCoordArrays();++ti)
1667     {
1668         if (_geometry->getTexCoordArray(ti))
1669             _geometry->getTexCoordArray(ti)->accept(copyArrayToPoints);
1670     }
1671 
1672     if (_geometry->getNormalArray() && _geometry->getNormalArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1673     {
1674         _geometry->getNormalArray()->accept(copyArrayToPoints);
1675 
1676         // now normalize the normals.
1677         NormalizeArrayVisitor nav;
1678         _geometry->getNormalArray()->accept(nav);
1679     }
1680 
1681     if (_geometry->getColorArray() && _geometry->getColorArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1682         _geometry->getColorArray()->accept(copyArrayToPoints);
1683 
1684     if (_geometry->getSecondaryColorArray() && _geometry->getSecondaryColorArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1685         _geometry->getSecondaryColorArray()->accept(copyArrayToPoints);
1686 
1687     if (_geometry->getFogCoordArray() && _geometry->getFogCoordArray()->getBinding()==osg::Array::BIND_PER_VERTEX)
1688         _geometry->getFogCoordArray()->accept(copyArrayToPoints);
1689 
1690     for(unsigned int vi=0;vi<_geometry->getNumVertexAttribArrays();++vi)
1691     {
1692         if (_geometry->getVertexAttribArray(vi) &&  _geometry->getVertexAttribArray(vi)->getBinding()==osg::Array::BIND_PER_VERTEX)
1693             _geometry->getVertexAttribArray(vi)->accept(copyArrayToPoints);
1694     }
1695 
1696     typedef std::set< osg::ref_ptr<Triangle>, dereference_less >    TrianglesSorted;
1697     TrianglesSorted trianglesSorted;
1698     for(TriangleSet::iterator itr = _triangleSet.begin();
1699         itr != _triangleSet.end();
1700         ++itr)
1701     {
1702         trianglesSorted.insert(*itr);
1703     }
1704 
1705     osg::DrawElementsUInt* primitives = new osg::DrawElementsUInt(GL_TRIANGLES,trianglesSorted.size()*3);
1706     unsigned int pos = 0;
1707     for(TrianglesSorted::iterator titr=trianglesSorted.begin();
1708         titr!=trianglesSorted.end();
1709         ++titr)
1710     {
1711         const Triangle* triangle = (*titr).get();
1712         (*primitives)[pos++] = triangle->_p1->_index;
1713         (*primitives)[pos++] = triangle->_p2->_index;
1714         (*primitives)[pos++] = triangle->_p3->_index;
1715     }
1716 
1717     _geometry->getPrimitiveSetList().clear();
1718     _geometry->addPrimitiveSet(primitives);
1719 
1720 }
1721 
1722 
Simplifier(double sampleRatio,double maximumError,double maximumLength)1723 Simplifier::Simplifier(double sampleRatio, double maximumError, double maximumLength):
1724             osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN),
1725             _sampleRatio(sampleRatio),
1726             _maximumError(maximumError),
1727             _maximumLength(maximumLength),
1728             _triStrip(true),
1729             _smoothing(true)
1730 
1731 {
1732 }
1733 
simplify(osg::Geometry & geometry)1734 void Simplifier::simplify(osg::Geometry& geometry)
1735 {
1736     // pass an empty list of indices to simply(Geometry,IndexList)
1737     // so that this one method handle both cases of non protected indices
1738     // and specified indices.
1739     IndexList emptyList;
1740     simplify(geometry,emptyList);
1741 }
1742 
simplify(osg::Geometry & geometry,const IndexList & protectedPoints)1743 void Simplifier::simplify(osg::Geometry& geometry, const IndexList& protectedPoints)
1744 {
1745     OSG_INFO<<"++++++++++++++simplifier************"<<std::endl;
1746 
1747     EdgeCollapse ec;
1748     ec.setComputeErrorMetricUsingLength(getSampleRatio()>=1.0);
1749     ec.setGeometry(&geometry, protectedPoints);
1750     ec.updateErrorMetricForAllEdges();
1751 
1752     unsigned int numOriginalPrimitives = ec._triangleSet.size();
1753 
1754     if (getSampleRatio()<1.0)
1755     {
1756         while (!ec._edgeSet.empty() &&
1757                continueSimplification((*ec._edgeSet.begin())->getErrorMetric() , numOriginalPrimitives, ec._triangleSet.size()) &&
1758                ec.collapseMinimumErrorEdge())
1759         {
1760            //OSG_INFO<<"   Collapsed edge ec._triangleSet.size()="<<ec._triangleSet.size()<<" error="<<(*ec._edgeSet.begin())->getErrorMetric()<<" vs "<<getMaximumError()<<std::endl;
1761         }
1762 
1763         OSG_INFO<<"******* AFTER EDGE COLLAPSE *********"<<ec._triangleSet.size()<<std::endl;
1764     }
1765     else
1766     {
1767 
1768         // up sampling...
1769         while (!ec._edgeSet.empty() &&
1770                continueSimplification((*ec._edgeSet.rbegin())->getErrorMetric() , numOriginalPrimitives, ec._triangleSet.size()) &&
1771 //               ec._triangleSet.size() < targetNumTriangles  &&
1772                ec.divideLongestEdge())
1773         {
1774            //OSG_INFO<<"   Edge divided ec._triangleSet.size()="<<ec._triangleSet.size()<<" error="<<(*ec._edgeSet.rbegin())->getErrorMetric()<<" vs "<<getMaximumError()<<std::endl;
1775         }
1776         OSG_INFO<<"******* AFTER EDGE DIVIDE *********"<<ec._triangleSet.size()<<std::endl;
1777     }
1778 
1779     OSG_INFO<<"Number of triangle errors after edge collapse= "<<ec.testAllTriangles()<<std::endl;
1780     OSG_INFO<<"Number of edge errors before edge collapse= "<<ec.testAllEdges()<<std::endl;
1781     OSG_INFO<<"Number of point errors after edge collapse= "<<ec.testAllPoints()<<std::endl;
1782     OSG_INFO<<"Number of triangles= "<<ec._triangleSet.size()<<std::endl;
1783     OSG_INFO<<"Number of points= "<<ec._pointSet.size()<<std::endl;
1784     OSG_INFO<<"Number of edges= "<<ec._edgeSet.size()<<std::endl;
1785     OSG_INFO<<"Number of boundary edges= "<<ec.computeNumBoundaryEdges()<<std::endl;
1786 
1787     if (!ec._edgeSet.empty())
1788     {
1789         OSG_INFO<<std::endl<<"Simplifier, in = "<<numOriginalPrimitives<<"\tout = "<<ec._triangleSet.size()<<"\terror="<<(*ec._edgeSet.begin())->getErrorMetric()<<"\tvs "<<getMaximumError()<<std::endl<<std::endl;
1790         OSG_INFO<<           "        !ec._edgeSet.empty()  = "<<!ec._edgeSet.empty()<<std::endl;
1791         OSG_INFO<<           "        continueSimplification(,,)  = "<<continueSimplification((*ec._edgeSet.begin())->getErrorMetric() , numOriginalPrimitives, ec._triangleSet.size())<<std::endl;
1792     }
1793 
1794     ec.copyBackToGeometry();
1795 
1796     if (_smoothing)
1797     {
1798         osgUtil::SmoothingVisitor::smooth(geometry);
1799     }
1800 
1801     if (_triStrip)
1802     {
1803         osgUtil::TriStripVisitor stripper;
1804         stripper.stripify(geometry);
1805     }
1806 
1807 }
1808