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

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