root/OpenSceneGraph/trunk/src/osgUtil/Simplifier.cpp @ 13041

Revision 13041, 61.2 kB (checked in by robert, 3 years ago)

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
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
27using namespace osgUtil;
28
29struct dereference_less
30{
31    template<class T, class U>
32    inline bool operator() (const T& lhs,const U& rhs) const
33    {
34        return *lhs < *rhs;
35    }
36};
37
38template<class T>
39bool 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
47struct dereference_clear
48{
49    template<class T>
50    inline void operator() (const T& t)
51    {
52        T& non_const_t = const_cast<T&>(t);
53        non_const_t->clear();
54    }
55};
56
57class EdgeCollapse
58{
59public:
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
73    EdgeCollapse():
74        _geometry(0),
75        _computeErrorMetricUsingLength(false)  {}
76
77    ~EdgeCollapse();
78
79    void setGeometry(osg::Geometry* geometry, const Simplifier::IndexList& protectedPoints);
80    osg::Geometry* getGeometry() { return _geometry; }
81
82    void setComputeErrorMetricUsingLength(bool flag) { _computeErrorMetricUsingLength = flag; }
83    bool getComputeErrorMetricUsingLength() const { return _computeErrorMetricUsingLength; }
84
85    unsigned int getNumOfTriangles() { return _triangleSet.size(); }
86
87    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
110    Point* computeOptimalPoint(Edge* edge) const
111    {
112        return computeInterpolatedPoint(edge,0.5f);
113    }
114
115    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
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
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
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
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    {
273        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
283        void clear()
284        {
285            _attributes.clear();
286            _triangles.clear();
287        }
288
289        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
297        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    {
319        Edge(): _errorMetric(0.0), _maximumDeviation(1.0) {}
320
321        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
338        void setErrorMetric(error_type errorMetric) { _errorMetric = errorMetric; }
339        error_type getErrorMetric() const { return _errorMetric; }
340
341        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
353        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
361        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
369        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
375        bool isBoundaryEdge() const
376        {
377            return _triangles.size()<=1;
378        }
379
380        bool isAdjacentToBoundary() const
381        {
382            return isBoundaryEdge() || _p1->isBoundaryPoint() || _p2->isBoundaryPoint();
383        }
384
385
386        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
410        error_type getMaxNormalDeviationOnEdgeCollapse() const { return _maximumDeviation; }
411
412    };
413
414    struct Triangle : public osg::Referenced
415    {
416        Triangle() {}
417
418        void clear()
419        {
420            _p1 = 0;
421            _p2 = 0;
422            _p3 = 0;
423
424            _e1 = 0;
425            _e2 = 0;
426            _e3 = 0;
427        }
428
429        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
448        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
465        void update()
466        {
467            _plane.set(_p1->_vertex,_p2->_vertex,_p3->_vertex);
468
469        }
470
471        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.
481        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
494        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
502        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
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
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
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
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
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
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
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
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
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 ammended
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
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
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
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
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
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
1154    Point* addPoint(Triangle* triangle, unsigned int p1)
1155    {
1156        return addPoint(triangle,_originalPointList[p1].get());
1157    }
1158
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
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
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
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
1243struct CollectTriangleOperator
1244{
1245
1246    CollectTriangleOperator():_ec(0) {}
1247
1248    void setEdgeCollapse(EdgeCollapse* ec) { _ec = ec; }
1249
1250    EdgeCollapse* _ec;
1251
1252    // for use  in the triangle functor.
1253    inline void operator()(unsigned int p1, unsigned int p2, unsigned int p3)
1254    {
1255        _ec->addTriangle(p1,p2,p3);
1256    }
1257
1258};
1259
1260EdgeCollapse::~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
1270typedef osg::TriangleIndexFunctor<CollectTriangleOperator> CollectTriangleIndexFunctor;
1271
1272class CopyArrayToPointsVisitor : public osg::ArrayVisitor
1273{
1274    public:
1275        CopyArrayToPointsVisitor(EdgeCollapse::PointList& pointList):
1276            _pointList(pointList) {}
1277
1278        template<class T>
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
1287        virtual void apply(osg::Array&) {}
1288        virtual void apply(osg::ByteArray& array) { copy(array); }
1289        virtual void apply(osg::ShortArray& array) { copy(array); }
1290        virtual void apply(osg::IntArray& array) { copy(array); }
1291        virtual void apply(osg::UByteArray& array) { copy(array); }
1292        virtual void apply(osg::UShortArray& array) { copy(array); }
1293        virtual void apply(osg::UIntArray& array) { copy(array); }
1294        virtual void apply(osg::FloatArray& array) { copy(array); }
1295
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
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
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
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
1358        CopyArrayToPointsVisitor& operator = (const CopyArrayToPointsVisitor&) { return *this; }
1359};
1360
1361class CopyVertexArrayToPointsVisitor : public osg::ArrayVisitor
1362{
1363    public:
1364        CopyVertexArrayToPointsVisitor(EdgeCollapse::PointList& pointList):
1365            _pointList(pointList) {}
1366
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
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
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
1414        CopyVertexArrayToPointsVisitor& operator = (const CopyVertexArrayToPointsVisitor&) { return *this; }
1415
1416};
1417
1418void 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->suitableForOptimization())
1424    {
1425        // removing coord indices
1426        OSG_INFO<<"EdgeCollapse::setGeometry(..): Removing attribute indices"<<std::endl;
1427        _geometry->copyToAndOptimize(*_geometry);
1428    }
1429
1430    // check to see if vertex attributes indices exists, if so expand them to remove them
1431    if (_geometry->containsSharedArrays())
1432    {
1433        // removing coord indices
1434        OSG_INFO<<"EdgeCollapse::setGeometry(..): Duplicate shared arrays"<<std::endl;
1435        _geometry->duplicateSharedArrays();
1436    }
1437
1438    unsigned int numVertices = geometry->getVertexArray()->getNumElements();
1439
1440    _originalPointList.resize(numVertices);
1441
1442    // copy vertices across to local point list
1443    CopyVertexArrayToPointsVisitor copyVertexArrayToPoints(_originalPointList);
1444    _geometry->getVertexArray()->accept(copyVertexArrayToPoints);
1445
1446    // copy other per vertex attributes across to local point list.
1447    CopyArrayToPointsVisitor        copyArrayToPoints(_originalPointList);
1448
1449    for(unsigned int ti=0;ti<_geometry->getNumTexCoordArrays();++ti)
1450    {
1451        if (_geometry->getTexCoordArray(ti))
1452            geometry->getTexCoordArray(ti)->accept(copyArrayToPoints);
1453    }
1454
1455    if (_geometry->getNormalArray() && _geometry->getNormalBinding()==osg::Geometry::BIND_PER_VERTEX)
1456        geometry->getNormalArray()->accept(copyArrayToPoints);
1457
1458    if (_geometry->getColorArray() && _geometry->getColorBinding()==osg::Geometry::BIND_PER_VERTEX)
1459        geometry->getColorArray()->accept(copyArrayToPoints);
1460
1461    if (_geometry->getSecondaryColorArray() && _geometry->getSecondaryColorBinding()==osg::Geometry::BIND_PER_VERTEX)
1462        geometry->getSecondaryColorArray()->accept(copyArrayToPoints);
1463
1464    if (_geometry->getFogCoordArray() && _geometry->getFogCoordBinding()==osg::Geometry::BIND_PER_VERTEX)
1465        geometry->getFogCoordArray()->accept(copyArrayToPoints);
1466
1467    for(unsigned int vi=0;vi<_geometry->getNumVertexAttribArrays();++vi)
1468    {
1469        if (_geometry->getVertexAttribArray(vi) &&  _geometry->getVertexAttribBinding(vi)==osg::Geometry::BIND_PER_VERTEX)
1470            geometry->getVertexAttribArray(vi)->accept(copyArrayToPoints);
1471    }
1472
1473    // now set the protected points up.
1474    for(Simplifier::IndexList::const_iterator pitr=protectedPoints.begin();
1475        pitr!=protectedPoints.end();
1476        ++pitr)
1477    {
1478        _originalPointList[*pitr]->_protected = true;
1479    }
1480
1481
1482    CollectTriangleIndexFunctor collectTriangles;
1483    collectTriangles.setEdgeCollapse(this);
1484
1485    _geometry->accept(collectTriangles);
1486
1487}
1488
1489
1490
1491class CopyPointsToArrayVisitor : public osg::ArrayVisitor
1492{
1493    public:
1494        CopyPointsToArrayVisitor(EdgeCollapse::PointList& pointList):
1495            _pointList(pointList),
1496            _index(0) {}
1497
1498
1499        template<typename T,typename R>
1500        void copy(T& array, R /*dummy*/)
1501        {
1502            array.resize(_pointList.size());
1503
1504            for(unsigned int i=0;i<_pointList.size();++i)
1505            {
1506                if (_index<_pointList[i]->_attributes.size())
1507                {
1508                    float val = (_pointList[i]->_attributes[_index]);
1509                    array[i] = R (val);
1510                }
1511            }
1512
1513            ++_index;
1514        }
1515
1516        // use local typedefs if usinged char,short and int to get round gcc 3.3.1 problem with defining unsigned short()
1517        typedef unsigned char dummy_uchar;
1518        typedef unsigned short dummy_ushort;
1519        typedef unsigned int dummy_uint;
1520
1521        virtual void apply(osg::Array&) {}
1522        virtual void apply(osg::ByteArray& array) { copy(array, char());}
1523        virtual void apply(osg::ShortArray& array) { copy(array, short()); }
1524        virtual void apply(osg::IntArray& array) { copy(array, int()); }
1525        virtual void apply(osg::UByteArray& array) { copy(array, dummy_uchar()); }
1526        virtual void apply(osg::UShortArray& array) { copy(array,dummy_ushort()); }
1527        virtual void apply(osg::UIntArray& array) { copy(array, dummy_uint()); }
1528        virtual void apply(osg::FloatArray& array) { copy(array, float()); }
1529
1530        virtual void apply(osg::Vec4ubArray& array)
1531        {
1532            array.resize(_pointList.size());
1533
1534            for(unsigned int i=0;i<_pointList.size();++i)
1535            {
1536                EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1537                array[i].set((unsigned char)attributes[_index],
1538                             (unsigned char)attributes[_index+1],
1539                             (unsigned char)attributes[_index+2],
1540                             (unsigned char)attributes[_index+3]);
1541            }
1542            _index += 4;
1543        }
1544
1545        virtual void apply(osg::Vec2Array& array)
1546        {
1547            array.resize(_pointList.size());
1548
1549            for(unsigned int i=0;i<_pointList.size();++i)
1550            {
1551                EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1552                if (_index+1<attributes.size()) array[i].set(attributes[_index],attributes[_index+1]);
1553            }
1554            _index += 2;
1555        }
1556
1557        virtual void apply(osg::Vec3Array& array)
1558        {
1559            array.resize(_pointList.size());
1560
1561            for(unsigned int i=0;i<_pointList.size();++i)
1562            {
1563                EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1564                if (_index+2<attributes.size()) array[i].set(attributes[_index],attributes[_index+1],attributes[_index+2]);
1565            }
1566            _index += 3;
1567        }
1568
1569        virtual void apply(osg::Vec4Array& array)
1570        {
1571            array.resize(_pointList.size());
1572
1573            for(unsigned int i=0;i<_pointList.size();++i)
1574            {
1575                EdgeCollapse::FloatList& attributes = _pointList[i]->_attributes;
1576                if (_index+3<attributes.size()) array[i].set(attributes[_index],attributes[_index+1],attributes[_index+2],attributes[_index+3]);
1577            }
1578            _index += 4;
1579        }
1580
1581        EdgeCollapse::PointList& _pointList;
1582        unsigned int _index;
1583
1584    protected:
1585
1586        CopyPointsToArrayVisitor& operator = (CopyPointsToArrayVisitor&) { return *this; }
1587};
1588
1589class NormalizeArrayVisitor : public osg::ArrayVisitor
1590{
1591    public:
1592        NormalizeArrayVisitor() {}
1593
1594        template<typename Itr>
1595        void normalize(Itr begin, Itr end)
1596        {
1597            for(Itr itr = begin;
1598                itr != end;
1599                ++itr)
1600            {
1601                itr->normalize();
1602            }
1603        }
1604
1605        virtual void apply(osg::Vec2Array& array) { normalize(array.begin(),array.end()); }
1606        virtual void apply(osg::Vec3Array& array) { normalize(array.begin(),array.end()); }
1607        virtual void apply(osg::Vec4Array& array) { normalize(array.begin(),array.end()); }
1608
1609};
1610
1611class CopyPointsToVertexArrayVisitor : public osg::ArrayVisitor
1612{
1613    public:
1614        CopyPointsToVertexArrayVisitor(EdgeCollapse::PointList& pointList):
1615            _pointList(pointList) {}
1616
1617        virtual void apply(osg::Vec2Array& array)
1618        {
1619            array.resize(_pointList.size());
1620
1621            for(unsigned int i=0;i<_pointList.size();++i)
1622            {
1623                _pointList[i]->_index = i;
1624                osg::Vec3& vertex = _pointList[i]->_vertex;
1625                array[i].set(vertex.x(),vertex.y());
1626            }
1627        }
1628
1629        virtual void apply(osg::Vec3Array& array)
1630        {
1631            array.resize(_pointList.size());
1632
1633            for(unsigned int i=0;i<_pointList.size();++i)
1634            {
1635                _pointList[i]->_index = i;
1636                array[i] = _pointList[i]->_vertex;
1637            }
1638        }
1639
1640        virtual void apply(osg::Vec4Array& array)
1641        {
1642            array.resize(_pointList.size());
1643
1644            for(unsigned int i=0;i<_pointList.size();++i)
1645            {
1646                _pointList[i]->_index = i;
1647                osg::Vec3& vertex = _pointList[i]->_vertex;
1648                array[i].set(vertex.x(),vertex.y(),vertex.z(),1.0f);
1649            }
1650        }
1651
1652        EdgeCollapse::PointList& _pointList;
1653
1654    protected:
1655
1656        CopyPointsToVertexArrayVisitor& operator = (const CopyPointsToVertexArrayVisitor&) { return *this; }
1657};
1658
1659
1660void EdgeCollapse::copyBackToGeometry()
1661{
1662
1663    // rebuild the _pointList from the _pointSet
1664    _originalPointList.clear();
1665    std::copy(_pointSet.begin(),_pointSet.end(),std::back_inserter(_originalPointList));
1666
1667    // copy vertices across to local point list
1668    CopyPointsToVertexArrayVisitor copyVertexArrayToPoints(_originalPointList);
1669    _geometry->getVertexArray()->accept(copyVertexArrayToPoints);
1670
1671    // copy other per vertex attributes across to local point list.
1672    CopyPointsToArrayVisitor  copyArrayToPoints(_originalPointList);
1673
1674    for(unsigned int ti=0;ti<_geometry->getNumTexCoordArrays();++ti)
1675    {
1676        if (_geometry->getTexCoordArray(ti))
1677            _geometry->getTexCoordArray(ti)->accept(copyArrayToPoints);
1678    }
1679
1680    if (_geometry->getNormalArray() && _geometry->getNormalBinding()==osg::Geometry::BIND_PER_VERTEX)
1681    {
1682        _geometry->getNormalArray()->accept(copyArrayToPoints);
1683
1684        // now normalize the normals.
1685        NormalizeArrayVisitor nav;
1686        _geometry->getNormalArray()->accept(nav);
1687    }
1688
1689    if (_geometry->getColorArray() && _geometry->getColorBinding()==osg::Geometry::BIND_PER_VERTEX)
1690        _geometry->getColorArray()->accept(copyArrayToPoints);
1691
1692    if (_geometry->getSecondaryColorArray() && _geometry->getSecondaryColorBinding()==osg::Geometry::BIND_PER_VERTEX)
1693        _geometry->getSecondaryColorArray()->accept(copyArrayToPoints);
1694
1695    if (_geometry->getFogCoordArray() && _geometry->getFogCoordBinding()==osg::Geometry::BIND_PER_VERTEX)
1696        _geometry->getFogCoordArray()->accept(copyArrayToPoints);
1697
1698    for(unsigned int vi=0;vi<_geometry->getNumVertexAttribArrays();++vi)
1699    {
1700        if (_geometry->getVertexAttribArray(vi) &&  _geometry->getVertexAttribBinding(vi)==osg::Geometry::BIND_PER_VERTEX)
1701            _geometry->getVertexAttribArray(vi)->accept(copyArrayToPoints);
1702    }
1703
1704    typedef std::set< osg::ref_ptr<Triangle>, dereference_less >    TrianglesSorted;
1705    TrianglesSorted trianglesSorted;
1706    for(TriangleSet::iterator itr = _triangleSet.begin();
1707        itr != _triangleSet.end();
1708        ++itr)
1709    {
1710        trianglesSorted.insert(*itr);
1711    }
1712
1713    osg::DrawElementsUInt* primitives = new osg::DrawElementsUInt(GL_TRIANGLES,trianglesSorted.size()*3);
1714    unsigned int pos = 0;
1715    for(TrianglesSorted::iterator titr=trianglesSorted.begin();
1716        titr!=trianglesSorted.end();
1717        ++titr)
1718    {
1719        const Triangle* triangle = (*titr).get();
1720        (*primitives)[pos++] = triangle->_p1->_index;
1721        (*primitives)[pos++] = triangle->_p2->_index;
1722        (*primitives)[pos++] = triangle->_p3->_index;
1723    }
1724
1725    _geometry->getPrimitiveSetList().clear();
1726    _geometry->addPrimitiveSet(primitives);
1727
1728}
1729
1730
1731Simplifier::Simplifier(double sampleRatio, double maximumError, double maximumLength):
1732            osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN),
1733            _sampleRatio(sampleRatio),
1734            _maximumError(maximumError),
1735            _maximumLength(maximumLength),
1736            _triStrip(true),
1737            _smoothing(true)
1738
1739{
1740}
1741
1742void Simplifier::simplify(osg::Geometry& geometry)
1743{
1744    // pass an empty list of indices to simply(Geometry,IndexList)
1745    // so that this one method handle both cases of non protected indices
1746    // and specified indices.
1747    IndexList emptyList;
1748    simplify(geometry,emptyList);
1749}
1750
1751void Simplifier::simplify(osg::Geometry& geometry, const IndexList& protectedPoints)
1752{
1753    OSG_INFO<<"++++++++++++++simplifier************"<<std::endl;
1754
1755    EdgeCollapse ec;
1756    ec.setComputeErrorMetricUsingLength(getSampleRatio()>=1.0);
1757    ec.setGeometry(&geometry, protectedPoints);
1758    ec.updateErrorMetricForAllEdges();
1759
1760    unsigned int numOriginalPrimitives = ec._triangleSet.size();
1761
1762    if (getSampleRatio()<1.0)
1763    {
1764        while (!ec._edgeSet.empty() &&
1765               continueSimplification((*ec._edgeSet.begin())->getErrorMetric() , numOriginalPrimitives, ec._triangleSet.size()) &&
1766               ec.collapseMinimumErrorEdge())
1767        {
1768           //OSG_INFO<<"   Collapsed edge ec._triangleSet.size()="<<ec._triangleSet.size()<<" error="<<(*ec._edgeSet.begin())->getErrorMetric()<<" vs "<<getMaximumError()<<std::endl;
1769        }
1770
1771        OSG_INFO<<"******* AFTER EDGE COLLAPSE *********"<<ec._triangleSet.size()<<std::endl;
1772    }
1773    else
1774    {
1775
1776        // up sampling...
1777        while (!ec._edgeSet.empty() &&
1778               continueSimplification((*ec._edgeSet.rbegin())->getErrorMetric() , numOriginalPrimitives, ec._triangleSet.size()) &&
1779//               ec._triangleSet.size() < targetNumTriangles  &&
1780               ec.divideLongestEdge())
1781        {
1782           //OSG_INFO<<"   Edge divided ec._triangleSet.size()="<<ec._triangleSet.size()<<" error="<<(*ec._edgeSet.rbegin())->getErrorMetric()<<" vs "<<getMaximumError()<<std::endl;
1783        }
1784        OSG_INFO<<"******* AFTER EDGE DIVIDE *********"<<ec._triangleSet.size()<<std::endl;
1785    }
1786
1787    OSG_INFO<<"Number of triangle errors after edge collapse= "<<ec.testAllTriangles()<<std::endl;
1788    OSG_INFO<<"Number of edge errors before edge collapse= "<<ec.testAllEdges()<<std::endl;
1789    OSG_INFO<<"Number of point errors after edge collapse= "<<ec.testAllPoints()<<std::endl;
1790    OSG_INFO<<"Number of triangles= "<<ec._triangleSet.size()<<std::endl;
1791    OSG_INFO<<"Number of points= "<<ec._pointSet.size()<<std::endl;
1792    OSG_INFO<<"Number of edges= "<<ec._edgeSet.size()<<std::endl;
1793    OSG_INFO<<"Number of boundary edges= "<<ec.computeNumBoundaryEdges()<<std::endl;
1794
1795    if (!ec._edgeSet.empty())
1796    {
1797        OSG_INFO<<std::endl<<"Simplifier, in = "<<numOriginalPrimitives<<"\tout = "<<ec._triangleSet.size()<<"\terror="<<(*ec._edgeSet.begin())->getErrorMetric()<<"\tvs "<<getMaximumError()<<std::endl<<std::endl;
1798        OSG_INFO<<           "        !ec._edgeSet.empty()  = "<<!ec._edgeSet.empty()<<std::endl;
1799        OSG_INFO<<           "        continueSimplification(,,)  = "<<continueSimplification((*ec._edgeSet.begin())->getErrorMetric() , numOriginalPrimitives, ec._triangleSet.size())<<std::endl;
1800    }
1801
1802    ec.copyBackToGeometry();
1803
1804    if (_smoothing)
1805    {
1806        osgUtil::SmoothingVisitor::smooth(geometry);
1807    }
1808
1809    if (_triStrip)
1810    {
1811        osgUtil::TriStripVisitor stripper;
1812        stripper.stripify(geometry);
1813    }
1814
1815}
Note: See TracBrowser for help on using the browser.