root/OpenSceneGraph/trunk/src/osgUtil/TriStripVisitor.cpp @ 10755

Revision 10755, 20.1 kB (checked in by robert, 5 years ago)

Removed usaged of throw and catch to enable better compatibility with embedded systems that don't support C++ exceptions efficiently.

  • 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
[1529]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*/
[196]13#include <osg/Notify>
[2733]14#include <osg/TriangleIndexFunctor>
[3988]15#include <osg/io_utils>
[10]16
17#include <osgUtil/TriStripVisitor>
[2491]18#include <osgUtil/SmoothingVisitor>
[10]19
[794]20#include <stdio.h>
[2299]21#include <algorithm>
[2518]22#include <map>
[794]23
[1474]24#include "TriStrip_tri_stripper.h"
[10]25
26using namespace osg;
27using namespace osgUtil;
28
[2491]29typedef std::vector<unsigned int> IndexList;
30
31class WriteValue : public osg::ConstValueVisitor
32{
33    public:
34        WriteValue(std::ostream& o):_o(o) {}
35       
36        std::ostream& _o;
37               
38        virtual void apply(const GLbyte& v) { _o << v; }
39        virtual void apply(const GLshort& v) { _o << v; }
40        virtual void apply(const GLint& v) { _o << v; }
41        virtual void apply(const GLushort& v) { _o << v; }
42        virtual void apply(const GLubyte& v) { _o << v; }
43        virtual void apply(const GLuint& v) { _o << v; }
44        virtual void apply(const GLfloat& v) { _o << v; }
[4390]45        virtual void apply(const Vec4ub& v) { _o << v; }
[2491]46        virtual void apply(const Vec2& v) { _o << v; }
47        virtual void apply(const Vec3& v) { _o << v; }
48        virtual void apply(const Vec4& v) { _o << v; }
[9630]49
50    protected:
51   
52        WriteValue& operator = (const WriteValue&) { return *this; }
[2491]53};
54
55
56struct VertexAttribComparitor
57{
58    VertexAttribComparitor(osg::Geometry& geometry)
59    {
60        add(geometry.getVertexArray(),osg::Geometry::BIND_PER_VERTEX);
61        add(geometry.getNormalArray(),geometry.getNormalBinding());
62        add(geometry.getColorArray(),geometry.getColorBinding());
63        add(geometry.getSecondaryColorArray(),geometry.getSecondaryColorBinding());
64        add(geometry.getFogCoordArray(),geometry.getFogCoordBinding());
65        unsigned int i;
66        for(i=0;i<geometry.getNumTexCoordArrays();++i)
67        {
68            add(geometry.getTexCoordArray(i),osg::Geometry::BIND_PER_VERTEX);
69        }
70        for(i=0;i<geometry.getNumVertexAttribArrays();++i)
71        {
72            add(geometry.getVertexAttribArray(i),geometry.getVertexAttribBinding(i));
73        }
74    }
75   
76    void add(osg::Array* array, osg::Geometry::AttributeBinding binding)
77    {
78        if (binding==osg::Geometry::BIND_PER_VERTEX && array)
79            _arrayList.push_back(array);
80    }
81   
82    typedef std::vector<osg::Array*> ArrayList;
83   
84    ArrayList _arrayList;
85   
86    bool operator() (unsigned int lhs, unsigned int rhs) const
87    {
88        for(ArrayList::const_iterator itr=_arrayList.begin();
89            itr!=_arrayList.end();
90            ++itr)
91        {
92            int compare = (*itr)->compare(lhs,rhs);
93            if (compare==-1) return true;
94            if (compare==1) return false;
95        }
96        return false;
97    }   
98
99    int compare(unsigned int lhs, unsigned int rhs)
100    {
101        for(ArrayList::iterator itr=_arrayList.begin();
102            itr!=_arrayList.end();
103            ++itr)
104        {
105            int compare = (*itr)->compare(lhs,rhs);
106            if (compare==-1) return -1;
107            if (compare==1) return 1;
108        }
109//         
110//         WriteValue wv(std::cout);
111//         
112//         std::cout<<"Values equal"<<std::endl;
113//         for(ArrayList::iterator itr=_arrayList.begin();
114//             itr!=_arrayList.end();
115//             ++itr)
116//         {
117//             std::cout<<"   lhs["<<lhs<<"]="; (*itr)->accept(lhs,wv);
118//             std::cout<<"   rhs["<<rhs<<"]="; (*itr)->accept(rhs,wv);
119//             std::cout<<std::endl;
120//         }
121       
122
123        return 0;
124    }
125   
126    void accept(osg::ArrayVisitor& av)
127    {
128        for(ArrayList::iterator itr=_arrayList.begin();
129            itr!=_arrayList.end();
130            ++itr)
131        {
132            (*itr)->accept(av);
133        }
134    }
135
[9630]136protected:
137
138    VertexAttribComparitor& operator = (const VertexAttribComparitor&) { return *this; }   
139
[2491]140};
141
142class RemapArray : public osg::ArrayVisitor
143{
144    public:
145        RemapArray(const IndexList& remapping):_remapping(remapping) {}
146       
147        const IndexList& _remapping;
148       
149        template<class T>
150        inline void remap(T& array)
151        {
152            for(unsigned int i=0;i<_remapping.size();++i)
153            {
154                if (i!=_remapping[i])
155                {
156                    array[i] = array[_remapping[i]];
157                }
158            }
159            array.erase(array.begin()+_remapping.size(),array.end());
160        }
161       
162        virtual void apply(osg::Array&) {}
163        virtual void apply(osg::ByteArray& array) { remap(array); }
164        virtual void apply(osg::ShortArray& array) { remap(array); }
165        virtual void apply(osg::IntArray& array) { remap(array); }
166        virtual void apply(osg::UByteArray& array) { remap(array); }
167        virtual void apply(osg::UShortArray& array) { remap(array); }
168        virtual void apply(osg::UIntArray& array) { remap(array); }
[4390]169        virtual void apply(osg::Vec4ubArray& array) { remap(array); }
[2491]170        virtual void apply(osg::FloatArray& array) { remap(array); }
171        virtual void apply(osg::Vec2Array& array) { remap(array); }
172        virtual void apply(osg::Vec3Array& array) { remap(array); }
173        virtual void apply(osg::Vec4Array& array) { remap(array); }
[9630]174
175protected:
176
177        RemapArray& operator = (const RemapArray&) { return *this; }
[2491]178};
179
[2733]180struct MyTriangleOperator
[2491]181{
182
183    IndexList                                _remapIndices;
184    triangle_stripper::tri_stripper::indices _in_indices;
185
[2733]186    inline void operator()(unsigned int p1, unsigned int p2, unsigned int p3)
[2491]187    {
188        if (_remapIndices.empty())
189        {
190            _in_indices.push_back(p1);
191            _in_indices.push_back(p2);
192            _in_indices.push_back(p3);
193        }
194        else
195        {
196            _in_indices.push_back(_remapIndices[p1]);
197            _in_indices.push_back(_remapIndices[p2]);
198            _in_indices.push_back(_remapIndices[p3]);
199        }
200    }
201
202};
[2733]203typedef osg::TriangleIndexFunctor<MyTriangleOperator> MyTriangleIndexFunctor;
[2491]204
[794]205void TriStripVisitor::stripify(Geometry& geom)
[10]206{
207
[1481]208    if (geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
209        geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
210
211    if (geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
212        geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
213   
214    if (geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
215        geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
216
217    if (geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
218        geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
219
[2501]220    // no point tri stripping if we don't have enough vertices.
[2843]221    if (!geom.getVertexArray() || geom.getVertexArray()->getNumElements()<3) return;
[2501]222
223    // check to see if vertex attributes indices exists, if so expand them to remove them
[2493]224    if (geom.suitableForOptimization())
225    {
226        // removing coord indices
[2525]227        osg::notify(osg::INFO)<<"TriStripVisitor::stripify(Geometry&): Removing attribute indices"<<std::endl;
[2493]228        geom.copyToAndOptimize(geom);
229    }
[1481]230
[7648]231    // check for the existence of surface primitives
[794]232    unsigned int numSurfacePrimitives = 0;
233    unsigned int numNonSurfacePrimitives = 0;
[1186]234    Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList();
235    Geometry::PrimitiveSetList::iterator itr;
[794]236    for(itr=primitives.begin();
237        itr!=primitives.end();
238        ++itr)
[10]239    {
[794]240        switch((*itr)->getMode())
241        {
[1166]242            case(PrimitiveSet::TRIANGLES):
243            case(PrimitiveSet::TRIANGLE_STRIP):
244            case(PrimitiveSet::TRIANGLE_FAN):
245            case(PrimitiveSet::QUADS):
246            case(PrimitiveSet::QUAD_STRIP):
247            case(PrimitiveSet::POLYGON):
[794]248                ++numSurfacePrimitives;
249                break;
250            default:
251                ++numNonSurfacePrimitives;
252                break;
253               
254        }
[10]255    }
[794]256   
[2501]257    // nothitng to tri strip leave.
[794]258    if (!numSurfacePrimitives) return;
259   
[2491]260    // compute duplicate vertices
261   
262    typedef std::vector<unsigned int> IndexList;
263    unsigned int numVertices = geom.getVertexArray()->getNumElements();
264    IndexList indices(numVertices);
265    unsigned int i,j;
266    for(i=0;i<numVertices;++i)
267    {
268        indices[i] = i;
269    }
270   
271    VertexAttribComparitor arrayComparitor(geom);
272    std::sort(indices.begin(),indices.end(),arrayComparitor);
[10]273
[2491]274    unsigned int lastUnique = 0;
275    unsigned int numUnique = 1;
276    unsigned int numDuplicate = 0;
277    for(i=1;i<numVertices;++i)
278    {
279        if (arrayComparitor.compare(indices[lastUnique],indices[i])==0)
280        {
281            //std::cout<<"  found duplicate "<<indices[lastUnique]<<" and "<<indices[i]<<std::endl;
282            ++numDuplicate;
283        }
284        else 
285        {
286            //std::cout<<"  unique "<<indices[i]<<std::endl;
287            lastUnique = i;
288            ++numUnique;
289        }
290       
291    }
292//     std::cout<<"  Number of duplicates "<<numDuplicate<<std::endl;
293//     std::cout<<"  Number of unique "<<numUnique<<std::endl;
294//     std::cout<<"  Total number of vertices required "<<numUnique<<" vs original "<<numVertices<<std::endl;
295//     std::cout<<"  % size "<<(float)numUnique/(float)numVertices*100.0f<<std::endl;
296   
297    IndexList remapDuplicatesToOrignals(numVertices);
298    lastUnique = 0;
299    for(i=1;i<numVertices;++i)
300    {
301        if (arrayComparitor.compare(indices[lastUnique],indices[i])!=0)
302        {
303            // found a new vertex entry, so previous run of duplicates needs
304            // to be put together.
305            unsigned int min_index = indices[lastUnique];
306            for(j=lastUnique+1;j<i;++j)
307            {
308                min_index = osg::minimum(min_index,indices[j]);
309            }
310            for(j=lastUnique;j<i;++j)
311            {
312                remapDuplicatesToOrignals[indices[j]]=min_index;
313            }
314            lastUnique = i;
315        }
316       
317    }
318    unsigned int min_index = indices[lastUnique];
319    for(j=lastUnique+1;j<i;++j)
320    {
321        min_index = osg::minimum(min_index,indices[j]);
322    }
323    for(j=lastUnique;j<i;++j)
324    {
325        remapDuplicatesToOrignals[indices[j]]=min_index;
326    }
327
328
329    // copy the arrays.   
330    IndexList finalMapping(numVertices);
331    IndexList copyMapping;
332    copyMapping.reserve(numUnique);
333    unsigned int currentIndex=0;
334    for(i=0;i<numVertices;++i)
335    {
336        if (remapDuplicatesToOrignals[i]==i)
337        {
338            finalMapping[i] = currentIndex;
339            copyMapping.push_back(i);
340            currentIndex++;
341        }
342    }
343   
344    for(i=0;i<numVertices;++i)
345    {
346        if (remapDuplicatesToOrignals[i]!=i)
347        {
348            finalMapping[i] = finalMapping[remapDuplicatesToOrignals[i]];
349        }
350    }
351   
352   
[2733]353    MyTriangleIndexFunctor taf;
[2491]354    taf._remapIndices.swap(finalMapping);
355
[1186]356    Geometry::PrimitiveSetList new_primitives;
[794]357    new_primitives.reserve(primitives.size());
[10]358
[794]359    for(itr=primitives.begin();
360        itr!=primitives.end();
361        ++itr)
362    {
363        switch((*itr)->getMode())
364        {
[1166]365            case(PrimitiveSet::TRIANGLES):
366            case(PrimitiveSet::TRIANGLE_STRIP):
367            case(PrimitiveSet::TRIANGLE_FAN):
368            case(PrimitiveSet::QUADS):
369            case(PrimitiveSet::QUAD_STRIP):
370            case(PrimitiveSet::POLYGON):
[927]371                (*itr)->accept(taf);
[794]372                break;
373            default:
374                new_primitives.push_back(*itr);
375                break;
[10]376
[794]377        }
378    }
379   
[2519]380    float minimum_ratio_of_indices_to_unique_vertices = 1;
[2501]381    float ratio_of_indices_to_unique_vertices = ((float)taf._in_indices.size()/(float)numUnique);
382
[2525]383    osg::notify(osg::INFO)<<"TriStripVisitor::stripify(Geometry&): Number of indices"<<taf._in_indices.size()<<" numUnique"<< numUnique << std::endl;
384    osg::notify(osg::INFO)<<"TriStripVisitor::stripify(Geometry&):     ratio indices/numUnique"<< ratio_of_indices_to_unique_vertices << std::endl;
[2501]385   
386    // only tri strip if there is point in doing so.
387    if (!taf._in_indices.empty() && ratio_of_indices_to_unique_vertices>=minimum_ratio_of_indices_to_unique_vertices)
[10]388    {
[2525]389        osg::notify(osg::INFO)<<"TriStripVisitor::stripify(Geometry&):     doing tri strip"<< std::endl;
[2501]390
391        unsigned int in_numVertices = 0;
[2491]392        for(triangle_stripper::tri_stripper::indices::iterator itr=taf._in_indices.begin();
393            itr!=taf._in_indices.end();
[794]394            ++itr)
395        {
[2501]396            if (*itr>in_numVertices) in_numVertices=*itr;
[794]397        }
398        // the largest indice is in_numVertices, but indices start at 0
399        // so increment to give to the corrent number of verticies.
[2501]400        ++in_numVertices;
401       
402        // remap any shared vertex attributes
403        RemapArray ra(copyMapping);
404        arrayComparitor.accept(ra);
[10]405
[10755]406        triangle_stripper::tri_stripper stripifier(taf._in_indices);
407        stripifier.SetCacheSize(_cacheSize);
408        stripifier.SetMinStripSize(_minStripSize);
409
410        triangle_stripper::tri_stripper::primitives_vector outPrimitives;
411        if (!stripifier.Strip(&outPrimitives))
[1474]412        {
[10755]413            osg::notify(osg::WARN)<<"Error: TriStripVisitor::stripify(Geometry& geom) failed."<<std::endl;
414            return;
415        }
[2518]416
[10755]417        triangle_stripper::tri_stripper::primitives_vector::iterator pitr;
418        if (_generateFourPointPrimitivesQuads)
419        {
420            osg::notify(osg::INFO)<<"Collecting all quads"<<std::endl;
[2932]421
[10755]422            typedef triangle_stripper::tri_stripper::primitives_vector::iterator prim_iterator;
423            typedef std::multimap<unsigned int,prim_iterator> QuadMap;
424            QuadMap quadMap;
[3390]425
[10755]426            // pick out quads and place them in the quadMap, and also look for the max
427            for(pitr=outPrimitives.begin();
428                pitr!=outPrimitives.end();
429                ++pitr)
430            {
431                if (pitr->m_Indices.size()==4)
[2518]432                {
[10755]433                    std::swap(pitr->m_Indices[2],pitr->m_Indices[3]);
434                    unsigned int minValue = *(std::max_element(pitr->m_Indices.begin(),pitr->m_Indices.end()));
435                    quadMap.insert(QuadMap::value_type(minValue,pitr));
[2518]436                }
[10755]437            }
[2932]438
439
[10755]440            // handle the quads
441            if (!quadMap.empty())
442            {
443                IndexList indices;
444                indices.reserve(4*quadMap.size());
445
446                // adds all the quads into the quad primitive, in ascending order
447                // and the QuadMap stores the quad's in ascending order.
448                for(QuadMap::iterator qitr=quadMap.begin();
449                    qitr!=quadMap.end();
450                    ++qitr)
[2518]451                {
[10755]452                    pitr = qitr->second;
[2932]453
[10755]454                    unsigned int min_pos = 0;
455                    for(i=1;i<4;++i)
[2932]456                    {
[10755]457                        if (pitr->m_Indices[min_pos]>pitr->m_Indices[i])
458                            min_pos = i;
459                    }
460                    indices.push_back(pitr->m_Indices[min_pos]);
461                    indices.push_back(pitr->m_Indices[(min_pos+1)%4]);
462                    indices.push_back(pitr->m_Indices[(min_pos+2)%4]);
463                    indices.push_back(pitr->m_Indices[(min_pos+3)%4]);
464                }           
[2932]465
[10755]466                bool inOrder = true;
467                unsigned int previousValue = indices.front();
468                for(IndexList::iterator qi_itr=indices.begin()+1;
469                    qi_itr!=indices.end() && inOrder;
470                    ++qi_itr)
471                {
472                    inOrder = (previousValue+1)==*qi_itr;
473                    previousValue = *qi_itr;
474                }
[2932]475
476
[10755]477                if (inOrder)
478                {
479                    new_primitives.push_back(new osg::DrawArrays(GL_QUADS,indices.front(),indices.size()));
480                }
481                else
482                {
483                    unsigned int maxValue = *(std::max_element(indices.begin(),indices.end()));
[2932]484
[10755]485                    if (maxValue>=65536)
[2932]486                    {
[10755]487                        osg::DrawElementsUInt* elements = new osg::DrawElementsUInt(GL_QUADS);
488                        std::copy(indices.begin(),indices.end(),std::back_inserter(*elements));
489                        new_primitives.push_back(elements);
[2932]490                    }
[3101]491                    else
[2932]492                    {
[10755]493                        osg::DrawElementsUShort* elements = new osg::DrawElementsUShort(GL_QUADS);
494                        std::copy(indices.begin(),indices.end(),std::back_inserter(*elements));
495                        new_primitives.push_back(elements);
[2932]496                    }
[10755]497                }
498            }   
499        }       
[3390]500
[10755]501        // handle non quad primitives   
502        for(pitr=outPrimitives.begin();
503            pitr!=outPrimitives.end();
504            ++pitr)
505        {
506            if (!_generateFourPointPrimitivesQuads || pitr->m_Indices.size()!=4)
[2518]507            {
[10755]508                bool inOrder = true;
509                unsigned int previousValue = pitr->m_Indices.front();
510                for(triangle_stripper::tri_stripper::indices::iterator qi_itr=pitr->m_Indices.begin()+1;
511                    qi_itr!=pitr->m_Indices.end() && inOrder;
512                    ++qi_itr)
[2518]513                {
[10755]514                    inOrder = (previousValue+1)==*qi_itr;
515                    previousValue = *qi_itr;
516                }
[2519]517
[10755]518                if (inOrder)
519                {
520                    new_primitives.push_back(new osg::DrawArrays(pitr->m_Type,pitr->m_Indices.front(),pitr->m_Indices.size()));
521                }
522                else
523                {
524                    unsigned int maxValue = *(std::max_element(pitr->m_Indices.begin(),pitr->m_Indices.end()));
525                    if (maxValue>=65536)
[2519]526                    {
[10755]527                        osg::DrawElementsUInt* elements = new osg::DrawElementsUInt(pitr->m_Type);
528                        elements->reserve(pitr->m_Indices.size());
529                        std::copy(pitr->m_Indices.begin(),pitr->m_Indices.end(),std::back_inserter(*elements));
530                        new_primitives.push_back(elements);
[2519]531                    }
[3101]532                    else
[2519]533                    {
[10755]534                        osg::DrawElementsUShort* elements = new osg::DrawElementsUShort(pitr->m_Type);
535                        elements->reserve(pitr->m_Indices.size());
536                        std::copy(pitr->m_Indices.begin(),pitr->m_Indices.end(),std::back_inserter(*elements));
537                        new_primitives.push_back(elements);
[2519]538                    }
[2518]539                }
540            }
[10]541        }
[2501]542
[10755]543        geom.setPrimitiveSetList(new_primitives);
544
545        #if 0
546        // debugging code for indentifying the tri-strips.       
547                osg::Vec4Array* colors = new osg::Vec4Array(new_primitives.size());
548                for(i=0;i<colors->size();++i)
549                {
550                    (*colors)[i].set(((float)rand()/(float)RAND_MAX),
551                                     ((float)rand()/(float)RAND_MAX),
552                                     ((float)rand()/(float)RAND_MAX),
553                                     1.0f);
554                }
555                geom.setColorArray(colors);
556                geom.setColorBinding(osg::Geometry::BIND_PER_PRIMITIVE_SET);
557        #endif       
[10]558    }
[2501]559    else
560    {
[2525]561        osg::notify(osg::INFO)<<"TriStripVisitor::stripify(Geometry&):     not doing tri strip *****************"<< std::endl;
[2501]562    }
563
[10]564}
565
[2491]566void TriStripVisitor::stripify()
567{
568    for(GeometryList::iterator itr=_geometryList.begin();
569        itr!=_geometryList.end();
570        ++itr)
571    {
572        stripify(*(*itr));
573       
574        // osgUtil::SmoothingVisitor sv;
575        // sv.smooth(*(*itr));
576    }
577}
[10]578
579void TriStripVisitor::apply(Geode& geode)
580{
[918]581    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
[10]582    {
[794]583        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
[2491]584        if (geom) _geometryList.insert(geom);
[10]585    }
586}
Note: See TracBrowser for help on using the browser.