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

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