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

Revision 9638, 63.4 kB (checked in by robert, 6 years ago)

Fixed warning

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