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

Revision 13502, 19.4 kB (checked in by robert, 19 hours ago)

Added shaders to support experimental shader based displacement mapping technique osgTerrain::ShaderTerrain?.

  • 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    if (geom.containsDeprecatedData()) geom.fixDeprecatedData();
218
219    if (geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
220
221    if (geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
222
223    if (geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
224
225    if (geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
226
227    // no point tri stripping if we don't have enough vertices.
228    if (!geom.getVertexArray() || geom.getVertexArray()->getNumElements()<3) return;
229
230    // check for the existence of surface primitives
231    unsigned int numSurfacePrimitives = 0;
232    unsigned int numNonSurfacePrimitives = 0;
233    Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList();
234    Geometry::PrimitiveSetList::iterator itr;
235    for(itr=primitives.begin();
236        itr!=primitives.end();
237        ++itr)
238    {
239        switch((*itr)->getMode())
240        {
241            case(PrimitiveSet::TRIANGLES):
242            case(PrimitiveSet::TRIANGLE_STRIP):
243            case(PrimitiveSet::TRIANGLE_FAN):
244            case(PrimitiveSet::QUADS):
245            case(PrimitiveSet::QUAD_STRIP):
246            case(PrimitiveSet::POLYGON):
247                ++numSurfacePrimitives;
248                break;
249            default:
250                ++numNonSurfacePrimitives;
251                break;
252
253        }
254    }
255
256    // nothitng to tri strip leave.
257    if (!numSurfacePrimitives) return;
258
259    // compute duplicate vertices
260
261    typedef std::vector<unsigned int> IndexList;
262    unsigned int numVertices = geom.getVertexArray()->getNumElements();
263    IndexList indices(numVertices);
264    unsigned int i,j;
265    for(i=0;i<numVertices;++i)
266    {
267        indices[i] = i;
268    }
269
270    VertexAttribComparitor arrayComparitor(geom);
271    std::sort(indices.begin(),indices.end(),arrayComparitor);
272
273    unsigned int lastUnique = 0;
274    unsigned int numUnique = 1;
275    unsigned int numDuplicate = 0;
276    for(i=1;i<numVertices;++i)
277    {
278        if (arrayComparitor.compare(indices[lastUnique],indices[i])==0)
279        {
280            //std::cout<<"  found duplicate "<<indices[lastUnique]<<" and "<<indices[i]<<std::endl;
281            ++numDuplicate;
282        }
283        else
284        {
285            //std::cout<<"  unique "<<indices[i]<<std::endl;
286            lastUnique = i;
287            ++numUnique;
288        }
289
290    }
291//     std::cout<<"  Number of duplicates "<<numDuplicate<<std::endl;
292//     std::cout<<"  Number of unique "<<numUnique<<std::endl;
293//     std::cout<<"  Total number of vertices required "<<numUnique<<" vs original "<<numVertices<<std::endl;
294//     std::cout<<"  % size "<<(float)numUnique/(float)numVertices*100.0f<<std::endl;
295
296    IndexList remapDuplicatesToOrignals(numVertices);
297    lastUnique = 0;
298    for(i=1;i<numVertices;++i)
299    {
300        if (arrayComparitor.compare(indices[lastUnique],indices[i])!=0)
301        {
302            // found a new vertex entry, so previous run of duplicates needs
303            // to be put together.
304            unsigned int min_index = indices[lastUnique];
305            for(j=lastUnique+1;j<i;++j)
306            {
307                min_index = osg::minimum(min_index,indices[j]);
308            }
309            for(j=lastUnique;j<i;++j)
310            {
311                remapDuplicatesToOrignals[indices[j]]=min_index;
312            }
313            lastUnique = i;
314        }
315
316    }
317    unsigned int min_index = indices[lastUnique];
318    for(j=lastUnique+1;j<i;++j)
319    {
320        min_index = osg::minimum(min_index,indices[j]);
321    }
322    for(j=lastUnique;j<i;++j)
323    {
324        remapDuplicatesToOrignals[indices[j]]=min_index;
325    }
326
327
328    // copy the arrays.
329    IndexList finalMapping(numVertices);
330    IndexList copyMapping;
331    copyMapping.reserve(numUnique);
332    unsigned int currentIndex=0;
333    for(i=0;i<numVertices;++i)
334    {
335        if (remapDuplicatesToOrignals[i]==i)
336        {
337            finalMapping[i] = currentIndex;
338            copyMapping.push_back(i);
339            currentIndex++;
340        }
341    }
342
343    for(i=0;i<numVertices;++i)
344    {
345        if (remapDuplicatesToOrignals[i]!=i)
346        {
347            finalMapping[i] = finalMapping[remapDuplicatesToOrignals[i]];
348        }
349    }
350
351
352    MyTriangleIndexFunctor taf;
353    taf._remapIndices.swap(finalMapping);
354
355    Geometry::PrimitiveSetList new_primitives;
356    new_primitives.reserve(primitives.size());
357
358    for(itr=primitives.begin();
359        itr!=primitives.end();
360        ++itr)
361    {
362        switch((*itr)->getMode())
363        {
364            case(PrimitiveSet::TRIANGLES):
365            case(PrimitiveSet::TRIANGLE_STRIP):
366            case(PrimitiveSet::TRIANGLE_FAN):
367            case(PrimitiveSet::QUADS):
368            case(PrimitiveSet::QUAD_STRIP):
369            case(PrimitiveSet::POLYGON):
370                (*itr)->accept(taf);
371                break;
372            default:
373                new_primitives.push_back(*itr);
374                break;
375
376        }
377    }
378
379    float minimum_ratio_of_indices_to_unique_vertices = 1;
380    float ratio_of_indices_to_unique_vertices = ((float)taf._in_indices.size()/(float)numUnique);
381
382    OSG_INFO<<"TriStripVisitor::stripify(Geometry&): Number of indices"<<taf._in_indices.size()<<" numUnique"<< numUnique << std::endl;
383    OSG_INFO<<"TriStripVisitor::stripify(Geometry&):     ratio indices/numUnique"<< ratio_of_indices_to_unique_vertices << std::endl;
384
385    // only tri strip if there is point in doing so.
386    if (!taf._in_indices.empty() && ratio_of_indices_to_unique_vertices>=minimum_ratio_of_indices_to_unique_vertices)
387    {
388        OSG_INFO<<"TriStripVisitor::stripify(Geometry&):     doing tri strip"<< std::endl;
389
390        unsigned int in_numVertices = 0;
391        for(triangle_stripper::indices::iterator itr=taf._in_indices.begin();
392            itr!=taf._in_indices.end();
393            ++itr)
394        {
395            if (*itr>in_numVertices) in_numVertices=*itr;
396        }
397        // the largest indice is in_numVertices, but indices start at 0
398        // so increment to give to the corrent number of verticies.
399        ++in_numVertices;
400
401        // remap any shared vertex attributes
402        RemapArray ra(copyMapping);
403        arrayComparitor.accept(ra);
404
405        triangle_stripper::tri_stripper stripifier(taf._in_indices);
406        stripifier.SetCacheSize(_cacheSize);
407        stripifier.SetMinStripSize(_minStripSize);
408
409        triangle_stripper::primitive_vector outPrimitives;
410        stripifier.Strip(&outPrimitives);
411        if (outPrimitives.empty())
412        {
413            OSG_WARN<<"Error: TriStripVisitor::stripify(Geometry& geom) failed."<<std::endl;
414            return;
415        }
416
417        triangle_stripper::primitive_vector::iterator pitr;
418        if (_generateFourPointPrimitivesQuads)
419        {
420            OSG_INFO<<"Collecting all quads"<<std::endl;
421
422            typedef triangle_stripper::primitive_vector::iterator prim_iterator;
423            typedef std::multimap<unsigned int,prim_iterator> QuadMap;
424            QuadMap quadMap;
425
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->Indices.size()==4)
432                {
433                    std::swap(pitr->Indices[2],pitr->Indices[3]);
434                    unsigned int minValue = *(std::max_element(pitr->Indices.begin(),pitr->Indices.end()));
435                    quadMap.insert(QuadMap::value_type(minValue,pitr));
436                }
437            }
438
439
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)
451                {
452                    pitr = qitr->second;
453
454                    unsigned int min_pos = 0;
455                    for(i=1;i<4;++i)
456                    {
457                        if (pitr->Indices[min_pos]>pitr->Indices[i])
458                            min_pos = i;
459                    }
460                    indices.push_back(pitr->Indices[min_pos]);
461                    indices.push_back(pitr->Indices[(min_pos+1)%4]);
462                    indices.push_back(pitr->Indices[(min_pos+2)%4]);
463                    indices.push_back(pitr->Indices[(min_pos+3)%4]);
464                }
465
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                }
475
476
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()));
484
485                    if (maxValue>=65536)
486                    {
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);
490                    }
491                    else
492                    {
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);
496                    }
497                }
498            }
499        }
500
501        // handle non quad primitives
502        for(pitr=outPrimitives.begin();
503            pitr!=outPrimitives.end();
504            ++pitr)
505        {
506            if (!_generateFourPointPrimitivesQuads || pitr->Indices.size()!=4)
507            {
508                bool inOrder = true;
509                unsigned int previousValue = pitr->Indices.front();
510                for(triangle_stripper::indices::iterator qi_itr=pitr->Indices.begin()+1;
511                    qi_itr!=pitr->Indices.end() && inOrder;
512                    ++qi_itr)
513                {
514                    inOrder = (previousValue+1)==*qi_itr;
515                    previousValue = *qi_itr;
516                }
517
518                if (inOrder)
519                {
520                    new_primitives.push_back(new osg::DrawArrays(pitr->Type,pitr->Indices.front(),pitr->Indices.size()));
521                }
522                else
523                {
524                    unsigned int maxValue = *(std::max_element(pitr->Indices.begin(),pitr->Indices.end()));
525                    if (maxValue>=65536)
526                    {
527                        osg::DrawElementsUInt* elements = new osg::DrawElementsUInt(pitr->Type);
528                        elements->reserve(pitr->Indices.size());
529                        std::copy(pitr->Indices.begin(),pitr->Indices.end(),std::back_inserter(*elements));
530                        new_primitives.push_back(elements);
531                    }
532                    else
533                    {
534                        osg::DrawElementsUShort* elements = new osg::DrawElementsUShort(pitr->Type);
535                        elements->reserve(pitr->Indices.size());
536                        std::copy(pitr->Indices.begin(),pitr->Indices.end(),std::back_inserter(*elements));
537                        new_primitives.push_back(elements);
538                    }
539                }
540            }
541        }
542
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
558    }
559    else
560    {
561        OSG_INFO<<"TriStripVisitor::stripify(Geometry&):     not doing tri strip *****************"<< std::endl;
562    }
563
564}
565
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}
578
579void TriStripVisitor::apply(Geode& geode)
580{
581    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
582    {
583        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
584        if (geom) _geometryList.insert(geom);
585    }
586}
Note: See TracBrowser for help on using the browser.