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

Revision 10764, 63.4 kB (checked in by robert, 4 years ago)

<iterator>, <stdlib.h> and <ctype.h> includes required for QNX compiler

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