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

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

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13#include <osg/TriangleFunctor>
14#include <osg/TriangleIndexFunctor>
15#include <osg/io_utils>
16
17#include <osgUtil/SmoothingVisitor>
18
19#include <stdio.h>
20#include <list>
21#include <set>
22
23
24using namespace osg;
25using namespace osgUtil;
26
27namespace Smoother
28{
29
30struct LessPtr
31{
32    inline bool operator() (const osg::Vec3* lhs,const osg::Vec3* rhs) const
33    {
34        return *lhs<*rhs;
35    }
36};
37
38// triangle functor.
39struct SmoothTriangleFunctor
40{
41
42    osg::Vec3* _coordBase;
43    osg::Vec3* _normalBase;
44
45    typedef std::multiset<const osg::Vec3*,LessPtr> CoordinateSet;
46    CoordinateSet _coordSet;
47
48    SmoothTriangleFunctor():
49         _coordBase(0),
50         _normalBase(0) {}
51
52    void set(osg::Vec3 *cb,int noVertices, osg::Vec3 *nb)
53    {
54        _coordBase=cb;
55        _normalBase=nb;
56
57        osg::Vec3* vptr = cb;
58        for(int i=0;i<noVertices;++i)
59        {
60            _coordSet.insert(vptr++);
61        }
62    }
63
64    inline void updateNormal(const osg::Vec3& normal,const osg::Vec3* vptr)
65    {
66        std::pair<CoordinateSet::iterator,CoordinateSet::iterator> p =
67            _coordSet.equal_range(vptr);
68
69        for(CoordinateSet::iterator itr=p.first;
70            itr!=p.second;
71            ++itr)
72        {
73            osg::Vec3* nptr = _normalBase + (*itr-_coordBase);
74            (*nptr) += normal;
75        }
76    }
77
78    inline void operator() ( const osg::Vec3 &v1, const osg::Vec3 &v2, const osg::Vec3 &v3, bool treatVertexDataAsTemporary )
79    {
80        if (!treatVertexDataAsTemporary)
81        {
82            // calc orientation of triangle.
83            osg::Vec3 normal = (v2-v1)^(v3-v1);
84            // normal.normalize();
85
86            updateNormal(normal,&v1);
87            updateNormal(normal,&v2);
88            updateNormal(normal,&v3);
89        }
90
91    }
92};
93
94static void smooth_old(osg::Geometry& geom)
95{
96    OSG_INFO<<"smooth_old("<<&geom<<")"<<std::endl;
97    Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList();
98    Geometry::PrimitiveSetList::iterator itr;
99    unsigned int numSurfacePrimitives=0;
100    for(itr=primitives.begin();
101        itr!=primitives.end();
102        ++itr)
103    {
104        switch((*itr)->getMode())
105        {
106            case(PrimitiveSet::TRIANGLES):
107            case(PrimitiveSet::TRIANGLE_STRIP):
108            case(PrimitiveSet::TRIANGLE_FAN):
109            case(PrimitiveSet::QUADS):
110            case(PrimitiveSet::QUAD_STRIP):
111            case(PrimitiveSet::POLYGON):
112                ++numSurfacePrimitives;
113                break;
114            default:
115                break;
116        }
117    }
118
119    if (!numSurfacePrimitives) return;
120
121    osg::Vec3Array *coords = dynamic_cast<osg::Vec3Array*>(geom.getVertexArray());
122    if (!coords || !coords->size()) return;
123
124    osg::Vec3Array *normals = new osg::Vec3Array(coords->size());
125
126    osg::Vec3Array::iterator nitr;
127    for(nitr = normals->begin();
128        nitr!=normals->end();
129        ++nitr)
130    {
131        nitr->set(0.0f,0.0f,0.0f);
132    }
133
134    TriangleFunctor<SmoothTriangleFunctor> stf;
135    stf.set(&(coords->front()),coords->size(),&(normals->front()));
136
137    geom.accept(stf);
138
139    for(nitr= normals->begin();
140        nitr!=normals->end();
141        ++nitr)
142    {
143        nitr->normalize();
144    }
145    geom.setNormalArray( normals );
146    geom.setNormalIndices( geom.getVertexIndices() );
147    geom.setNormalBinding(osg::Geometry::BIND_PER_VERTEX);
148
149
150    geom.dirtyDisplayList();
151}
152
153
154struct SmoothTriangleIndexFunctor
155{
156    SmoothTriangleIndexFunctor():
157        _vertices(0),
158        _normals(0)
159    {
160    }
161
162    bool set(osg::Vec3Array* vertices, osg::Vec3Array* normals)
163    {
164        _vertices = vertices;
165        _normals = normals;
166
167        if (!_vertices)
168        {
169            OSG_NOTICE<<"Warning: SmoothTriangleIndexFunctor::set(..) requires a valid vertex arrays."<<std::endl;
170            return false;
171        }
172
173        if (!_normals)
174        {
175            OSG_NOTICE<<"Warning: SmoothTriangleIndexFunctor::set(..) requires a valid normal arrays."<<std::endl;
176            return false;
177        }
178
179        for(osg::Vec3Array::iterator itr = _normals->begin();
180            itr != _normals->end();
181            ++itr)
182        {
183            (*itr).set(0.0f,0.0f,0.0f);
184        }
185
186        return true;
187    }
188
189    void normalize()
190    {
191        if (!_normals) return;
192
193        for(osg::Vec3Array::iterator itr = _normals->begin();
194            itr != _normals->end();
195            ++itr)
196        {
197            (*itr).normalize();
198        }
199    }
200
201    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
202    {
203        if (p1==p2 || p2==p3 || p1==p3)
204        {
205            return;
206        }
207
208        const osg::Vec3& v1 = (*_vertices)[p1];
209        const osg::Vec3& v2 = (*_vertices)[p2];
210        const osg::Vec3& v3 = (*_vertices)[p3];
211        osg::Vec3 normal( (v2-v1)^(v3-v1) );
212
213        normal.normalize();
214
215        (*_normals)[p1] += normal;
216        (*_normals)[p2] += normal;
217        (*_normals)[p3] += normal;
218    }
219
220    osg::Vec3Array*     _vertices;
221    osg::Vec3Array*     _normals;
222};
223
224
225
226struct FindSharpEdgesFunctor
227{
228    FindSharpEdgesFunctor():
229        _vertices(0),
230        _normals(0),
231        _maxDeviationDotProduct(0.0f),
232        _currentPrimitiveSetIndex(0)
233    {
234    }
235
236    struct Triangle : public osg::Referenced
237    {
238        Triangle(unsigned int primitiveSetIndex, unsigned int p1, unsigned int p2, unsigned int p3):
239            _primitiveSetIndex(primitiveSetIndex), _p1(p1), _p2(p2), _p3(p3) {}
240
241        Triangle(const Triangle& tri):
242            _primitiveSetIndex(tri._primitiveSetIndex), _p1(tri._p1), _p2(tri._p2), _p3(tri._p3) {}
243
244        Triangle& operator = (const Triangle& tri)
245        {
246            _primitiveSetIndex = tri._primitiveSetIndex;
247            _p1 = tri._p1;
248            _p2 = tri._p2;
249            _p3 = tri._p3;
250            return *this;
251        }
252
253        unsigned int _primitiveSetIndex;
254        unsigned int _p1;
255        unsigned int _p2;
256        unsigned int _p3;
257    };
258
259    typedef std::list< osg::ref_ptr<Triangle> > Triangles;
260
261    struct ProblemVertex : public osg::Referenced
262    {
263        ProblemVertex(unsigned int p):
264            _point(p) {}
265
266        unsigned int _point;
267        Triangles _triangles;
268    };
269
270    typedef std::vector< osg::ref_ptr<ProblemVertex> > ProblemVertexVector;
271    typedef std::list< osg::ref_ptr<ProblemVertex> > ProblemVertexList;
272    typedef std::list< osg::ref_ptr<osg::Array> > ArrayList;
273
274    bool set(osg::Geometry* geom, float creaseAngle)
275    {
276        _geometry = geom;
277        _creaseAngle = creaseAngle;
278
279        if (!_geometry)
280        {
281            OSG_NOTICE<<"Warning: SmoothTriangleIndexFunctor::set(..) requires a geometry."<<std::endl;
282            return false;
283        }
284
285        _vertices = dynamic_cast<osg::Vec3Array*>(_geometry->getVertexArray());
286        _normals = dynamic_cast<osg::Vec3Array*>(_geometry->getNormalArray());
287        _maxDeviationDotProduct = cos(_creaseAngle*0.5);
288
289        if (!_vertices)
290        {
291            OSG_NOTICE<<"Warning: SmoothTriangleIndexFunctor::set(..) requires a valid vertex arrays."<<std::endl;
292            return false;
293        }
294
295        if (!_normals)
296        {
297            OSG_NOTICE<<"Warning: SmoothTriangleIndexFunctor::set(..) requires a valid normal arrays."<<std::endl;
298            return false;
299        }
300
301        _problemVertexVector.resize(_vertices->size());
302
303        addArray(geom->getVertexArray(), osg::Geometry::BIND_PER_VERTEX);
304        addArray(geom->getNormalArray(), geom->getNormalBinding());
305        addArray(geom->getColorArray(), geom->getColorBinding());
306        addArray(geom->getSecondaryColorArray(), geom->getSecondaryColorBinding());
307        addArray(geom->getFogCoordArray(), geom->getFogCoordBinding());
308
309        for(unsigned int i=0; i<geom->getNumTexCoordArrays(); ++i)
310        {
311            addArray(geom->getTexCoordArray(i), osg::Geometry::BIND_PER_VERTEX);
312        }
313
314        return true;
315    }
316
317    void addArray(osg::Array* array, osg::Geometry::AttributeBinding binding)
318    {
319        if (array && binding==osg::Geometry::BIND_PER_VERTEX)
320        {
321            _arrays.push_back(array);
322        }
323    }
324
325    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
326    {
327        osg::Vec3 normal( computeNormal(p1, p2, p3) );
328
329        if (p1==p2 || p2==p3 || p1==p3)
330        {
331            // OSG_NOTICE<<"NULL triangle ("<<p1<<", "<<p2<<", "<<p3<<")"<<std::endl;
332            return;
333        }
334
335        Triangle* tri = new Triangle(_currentPrimitiveSetIndex, p1, p2, p3);
336        _triangles.push_back(tri);
337
338        if (checkDeviation(p1, normal)) markProblemVertex(p1);
339        if (checkDeviation(p2, normal)) markProblemVertex(p2);
340        if (checkDeviation(p3, normal)) markProblemVertex(p3);
341    }
342
343    void markProblemVertex(unsigned int p)
344    {
345        if (!_problemVertexVector[p])
346        {
347            _problemVertexVector[p] = new ProblemVertex(p);
348            _problemVertexList.push_back(_problemVertexVector[p]);
349        }
350    }
351
352    void checkTrianglesForProblemVertices()
353    {
354        for(Triangles::iterator itr = _triangles.begin();
355            itr != _triangles.end();
356            ++itr)
357        {
358            Triangle* tri = itr->get();
359            insertTriangleIfProblemVertex(tri->_p1, tri);
360            insertTriangleIfProblemVertex(tri->_p2, tri);
361            insertTriangleIfProblemVertex(tri->_p3, tri);
362        }
363    }
364
365    void insertTriangleIfProblemVertex(unsigned int p, Triangle* tri)
366    {
367        if (_problemVertexVector[p]) _problemVertexVector[p]->_triangles.push_back(tri);
368    }
369
370    bool checkDeviation(unsigned int p, osg::Vec3& normal)
371    {
372        float deviation = normal * (*_normals)[p];
373        return (deviation < _maxDeviationDotProduct);
374    }
375
376    osg::Vec3 computeNormal(unsigned int p1, unsigned int p2, unsigned int p3)
377    {
378        const osg::Vec3& v1 = (*_vertices)[p1];
379        const osg::Vec3& v2 = (*_vertices)[p2];
380        const osg::Vec3& v3 = (*_vertices)[p3];
381        osg::Vec3 normal( (v2-v1)^(v3-v1) );
382        normal.normalize();
383        return normal;
384    }
385
386    void listProblemVertices()
387    {
388        OSG_NOTICE<<"listProblemVertices() "<<_problemVertexList.size()<<std::endl;
389        for(ProblemVertexList::iterator itr = _problemVertexList.begin();
390            itr != _problemVertexList.end();
391            ++itr)
392        {
393            ProblemVertex* pv = itr->get();
394            OSG_NOTICE<<"  pv._point = "<<pv->_point<<" triangles "<<pv->_triangles.size()<<std::endl;
395            for(Triangles::iterator titr = pv->_triangles.begin();
396                titr != pv->_triangles.end();
397                ++titr)
398            {
399                Triangle* tri = titr->get();
400                OSG_NOTICE<<"    triangle("<<tri->_p1<<", "<<tri->_p2<<", "<<tri->_p3<<")"<<std::endl;
401                osg::Vec3 normal( computeNormal(tri->_p1, tri->_p2, tri->_p3) );
402                float deviation = normal * (*_normals)[pv->_point];
403                OSG_NOTICE<<"    deviation "<<deviation<<std::endl;
404            }
405
406        }
407    }
408
409    class DuplicateVertex : public osg::ArrayVisitor
410    {
411        public:
412
413            unsigned int _i;
414            unsigned int _end;
415
416            DuplicateVertex(unsigned int i):
417                                _i(i),
418                                _end(i) {}
419
420            template <class ARRAY>
421            void apply_imp(ARRAY& array)
422            {
423                _end = array.size();
424                array.push_back(array[_i]);
425            }
426
427            virtual void apply(osg::ByteArray& ba) { apply_imp(ba); }
428            virtual void apply(osg::ShortArray& ba) { apply_imp(ba); }
429            virtual void apply(osg::IntArray& ba) { apply_imp(ba); }
430            virtual void apply(osg::UByteArray& ba) { apply_imp(ba); }
431            virtual void apply(osg::UShortArray& ba) { apply_imp(ba); }
432            virtual void apply(osg::UIntArray& ba) { apply_imp(ba); }
433            virtual void apply(osg::Vec4ubArray& ba) { apply_imp(ba); }
434            virtual void apply(osg::FloatArray& ba) { apply_imp(ba); }
435            virtual void apply(osg::Vec2Array& ba) { apply_imp(ba); }
436            virtual void apply(osg::Vec3Array& ba) { apply_imp(ba); }
437            virtual void apply(osg::Vec4Array& ba) { apply_imp(ba); }
438
439    };
440
441    unsigned int duplicateVertex(unsigned int i)
442    {
443        DuplicateVertex duplicate(i);
444        for(ArrayList::iterator aItr = _arrays.begin();
445            aItr != _arrays.end();
446            ++aItr)
447        {
448            (*aItr)->accept(duplicate);
449        }
450        return duplicate._end;
451    }
452
453    void duplicateProblemVertexAll(ProblemVertex* pv)
454    {
455        unsigned int p = pv->_point;
456        Triangles::iterator titr = pv->_triangles.begin();
457        ++titr;
458        for(;
459            titr != pv->_triangles.end();
460            ++titr)
461        {
462            Triangle* tri = titr->get();
463            unsigned int duplicated_p = duplicateVertex(p);
464            if (tri->_p1==p) tri->_p1 = duplicated_p;
465            if (tri->_p2==p) tri->_p2 = duplicated_p;
466            if (tri->_p3==p) tri->_p3 = duplicated_p;
467        }
468    }
469
470    void duplicateProblemVertex(ProblemVertex* pv)
471    {
472        if (pv->_triangles.size()<=2)
473        {
474            duplicateProblemVertexAll(pv);
475        }
476        else
477        {
478            // implement a form of greedy association based on similar orientation
479            // rather than iterating through all the various permutation of triangles that might
480            // provide the best fit.
481            unsigned int p = pv->_point;
482            Triangles::iterator titr = pv->_triangles.begin();
483            while(titr != pv->_triangles.end())
484            {
485                Triangle* tri = titr->get();
486                osg::Vec3 normal = computeNormal(tri->_p1, tri->_p2, tri->_p3);
487
488                Triangles associatedTriangles;
489                associatedTriangles.push_back(tri);
490
491                // remove triangle for list
492                pv->_triangles.erase(titr);
493
494                // reset iterator
495                titr = pv->_triangles.begin();
496                while(titr != pv->_triangles.end())
497                {
498                    Triangle* tri2 = titr->get();
499                    osg::Vec3 normal2 = computeNormal(tri2->_p1, tri2->_p2, tri2->_p3);
500                    float deviation = normal * normal2;
501                    if (deviation >= _maxDeviationDotProduct)
502                    {
503                        // Tri and tri2 are close enough together to associate.
504                        associatedTriangles.push_back(tri2);
505
506                        Triangles::iterator titr_to_erase = titr;
507
508                        ++titr;
509                        pv->_triangles.erase(titr_to_erase);
510                    }
511                    else
512                    {
513                        ++titr;
514                    }
515                }
516
517                // create duplicate vertex to set of associated triangles
518                unsigned int duplicated_p = duplicateVertex(p);
519
520                // now rest the index on th triangles of the point that was duplicated
521                for(Triangles::iterator aitr = associatedTriangles.begin();
522                    aitr != associatedTriangles.end();
523                    ++aitr)
524                {
525                    Triangle* tri = aitr->get();
526                    if (tri->_p1==p) tri->_p1 = duplicated_p;
527                    if (tri->_p2==p) tri->_p2 = duplicated_p;
528                    if (tri->_p3==p) tri->_p3 = duplicated_p;
529                }
530
531                // reset iterator to beginning
532                titr = pv->_triangles.begin();
533            }
534
535        }
536    }
537
538    void duplicateProblemVertices()
539    {
540        checkTrianglesForProblemVertices();
541
542        for(ProblemVertexList::iterator itr = _problemVertexList.begin();
543            itr != _problemVertexList.end();
544            ++itr)
545        {
546            ProblemVertex* pv = itr->get();
547            if (pv->_triangles.size()>1)
548            {
549                duplicateProblemVertex(itr->get());
550            }
551        }
552    }
553
554    osg::PrimitiveSet* createPrimitiveSet(Triangles& triangles)
555    {
556        osg::ref_ptr<osg::DrawElements> elements = (_vertices->size()<16384) ?
557            static_cast<osg::DrawElements*>(new osg::DrawElementsUShort(GL_TRIANGLES)) :
558            static_cast<osg::DrawElements*>(new osg::DrawElementsUInt(GL_TRIANGLES));
559
560        elements->reserveElements(triangles.size()*3);
561
562        for(Triangles::iterator itr = triangles.begin();
563            itr != triangles.end();
564            ++itr)
565        {
566            Triangle* tri = itr->get();
567            elements->addElement(tri->_p1);
568            elements->addElement(tri->_p2);
569            elements->addElement(tri->_p3);
570        }
571
572        return elements.release();
573    }
574
575    void updateGeometry()
576    {
577        duplicateProblemVertices();
578
579
580        typedef std::map<unsigned int, Triangles> TriangleMap;
581        TriangleMap triangleMap;
582        for(Triangles::iterator itr = _triangles.begin();
583            itr != _triangles.end();
584            ++itr)
585        {
586            Triangle* tri = itr->get();
587            triangleMap[tri->_primitiveSetIndex].push_back(tri);
588        }
589
590        for(TriangleMap::iterator itr = triangleMap.begin();
591            itr != triangleMap.end();
592            ++itr)
593        {
594            osg::PrimitiveSet* originalPrimitiveSet = _geometry->getPrimitiveSet(itr->first);
595            osg::PrimitiveSet* newPrimitiveSet = createPrimitiveSet(itr->second);
596            newPrimitiveSet->setName(originalPrimitiveSet->getName());
597            _geometry->setPrimitiveSet(itr->first, newPrimitiveSet);
598        }
599    }
600
601
602    osg::Geometry*      _geometry;
603    osg::Vec3Array*     _vertices;
604    osg::Vec3Array*     _normals;
605    ArrayList           _arrays;
606    float               _creaseAngle;
607    float               _maxDeviationDotProduct;
608    ProblemVertexVector _problemVertexVector;
609    ProblemVertexList   _problemVertexList;
610    Triangles           _triangles;
611    unsigned int        _currentPrimitiveSetIndex;
612};
613
614
615static void smooth_new(osg::Geometry& geom, double creaseAngle)
616{
617    OSG_INFO<<"smooth_new("<<&geom<<", "<<osg::RadiansToDegrees(creaseAngle)<<")"<<std::endl;
618
619    osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(geom.getVertexArray());
620    if (!vertices) return;
621
622    osg::Vec3Array* normals = dynamic_cast<osg::Vec3Array*>(geom.getNormalArray());
623    if (!normals || (normals && normals->size() != vertices->size()))
624    {
625        normals = new osg::Vec3Array(vertices->size());
626        geom.setNormalArray(normals);
627        geom.setNormalBinding(osg::Geometry::BIND_PER_VERTEX);
628    }
629
630    osg::TriangleIndexFunctor<SmoothTriangleIndexFunctor> stif;
631    if (stif.set(vertices, normals))
632    {
633        // accumulate all the normals
634        geom.accept(stif);
635
636        // normalize the normals
637        stif.normalize();
638    }
639
640    osg::TriangleIndexFunctor<FindSharpEdgesFunctor> fsef;
641    if (fsef.set(&geom, creaseAngle))
642    {
643        // look for normals that deviate too far
644
645        fsef.setVertexArray(vertices->getNumElements(), static_cast<const Vec3*>(vertices->getDataPointer()));
646        for(unsigned int i = 0; i < geom.getNumPrimitiveSets(); ++i)
647        {
648            fsef._currentPrimitiveSetIndex = i;
649            geom.getPrimitiveSet(i)->accept(fsef);
650        }
651
652        // fsef.listProblemVertices();
653        fsef.updateGeometry();
654
655        osg::TriangleIndexFunctor<SmoothTriangleIndexFunctor> stif2;
656        if (stif2.set(vertices, normals))
657        {
658            // accumulate all the normals
659            geom.accept(stif);
660
661            // normalize the normals
662            stif.normalize();
663        }
664
665    }
666}
667
668}
669
670
671SmoothingVisitor::SmoothingVisitor():
672    _creaseAngle(osg::PI)
673{
674    setTraversalMode(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN);
675}
676
677SmoothingVisitor::~SmoothingVisitor()
678{
679}
680
681void SmoothingVisitor::smooth(osg::Geometry& geom, double creaseAngle)
682{
683    if (creaseAngle==osg::PI)
684    {
685        Smoother::smooth_old(geom);
686    }
687    else
688    {
689        Smoother::smooth_new(geom, creaseAngle);
690    }
691}
692
693
694void SmoothingVisitor::apply(osg::Geode& geode)
695{
696    for(unsigned int i = 0; i < geode.getNumDrawables(); i++ )
697    {
698        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
699        if (geom) smooth(*geom, _creaseAngle);
700    }
701}
Note: See TracBrowser for help on using the browser.