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

Revision 13488, 19.6 kB (checked in by robert, 2 days 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
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 for the existence of surface primitives
234    unsigned int numSurfacePrimitives = 0;
235    unsigned int numNonSurfacePrimitives = 0;
236    Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList();
237    Geometry::PrimitiveSetList::iterator itr;
238    for(itr=primitives.begin();
239        itr!=primitives.end();
240        ++itr)
241    {
242        switch((*itr)->getMode())
243        {
244            case(PrimitiveSet::TRIANGLES):
245            case(PrimitiveSet::TRIANGLE_STRIP):
246            case(PrimitiveSet::TRIANGLE_FAN):
247            case(PrimitiveSet::QUADS):
248            case(PrimitiveSet::QUAD_STRIP):
249            case(PrimitiveSet::POLYGON):
250                ++numSurfacePrimitives;
251                break;
252            default:
253                ++numNonSurfacePrimitives;
254                break;
255
256        }
257    }
258
259    // nothitng to tri strip leave.
260    if (!numSurfacePrimitives) return;
261
262    // compute duplicate vertices
263
264    typedef std::vector<unsigned int> IndexList;
265    unsigned int numVertices = geom.getVertexArray()->getNumElements();
266    IndexList indices(numVertices);
267    unsigned int i,j;
268    for(i=0;i<numVertices;++i)
269    {
270        indices[i] = i;
271    }
272
273    VertexAttribComparitor arrayComparitor(geom);
274    std::sort(indices.begin(),indices.end(),arrayComparitor);
275
276    unsigned int lastUnique = 0;
277    unsigned int numUnique = 1;
278    unsigned int numDuplicate = 0;
279    for(i=1;i<numVertices;++i)
280    {
281        if (arrayComparitor.compare(indices[lastUnique],indices[i])==0)
282        {
283            //std::cout<<"  found duplicate "<<indices[lastUnique]<<" and "<<indices[i]<<std::endl;
284            ++numDuplicate;
285        }
286        else
287        {
288            //std::cout<<"  unique "<<indices[i]<<std::endl;
289            lastUnique = i;
290            ++numUnique;
291        }
292
293    }
294//     std::cout<<"  Number of duplicates "<<numDuplicate<<std::endl;
295//     std::cout<<"  Number of unique "<<numUnique<<std::endl;
296//     std::cout<<"  Total number of vertices required "<<numUnique<<" vs original "<<numVertices<<std::endl;
297//     std::cout<<"  % size "<<(float)numUnique/(float)numVertices*100.0f<<std::endl;
298
299    IndexList remapDuplicatesToOrignals(numVertices);
300    lastUnique = 0;
301    for(i=1;i<numVertices;++i)
302    {
303        if (arrayComparitor.compare(indices[lastUnique],indices[i])!=0)
304        {
305            // found a new vertex entry, so previous run of duplicates needs
306            // to be put together.
307            unsigned int min_index = indices[lastUnique];
308            for(j=lastUnique+1;j<i;++j)
309            {
310                min_index = osg::minimum(min_index,indices[j]);
311            }
312            for(j=lastUnique;j<i;++j)
313            {
314                remapDuplicatesToOrignals[indices[j]]=min_index;
315            }
316            lastUnique = i;
317        }
318
319    }
320    unsigned int min_index = indices[lastUnique];
321    for(j=lastUnique+1;j<i;++j)
322    {
323        min_index = osg::minimum(min_index,indices[j]);
324    }
325    for(j=lastUnique;j<i;++j)
326    {
327        remapDuplicatesToOrignals[indices[j]]=min_index;
328    }
329
330
331    // copy the arrays.
332    IndexList finalMapping(numVertices);
333    IndexList copyMapping;
334    copyMapping.reserve(numUnique);
335    unsigned int currentIndex=0;
336    for(i=0;i<numVertices;++i)
337    {
338        if (remapDuplicatesToOrignals[i]==i)
339        {
340            finalMapping[i] = currentIndex;
341            copyMapping.push_back(i);
342            currentIndex++;
343        }
344    }
345
346    for(i=0;i<numVertices;++i)
347    {
348        if (remapDuplicatesToOrignals[i]!=i)
349        {
350            finalMapping[i] = finalMapping[remapDuplicatesToOrignals[i]];
351        }
352    }
353
354
355    MyTriangleIndexFunctor taf;
356    taf._remapIndices.swap(finalMapping);
357
358    Geometry::PrimitiveSetList new_primitives;
359    new_primitives.reserve(primitives.size());
360
361    for(itr=primitives.begin();
362        itr!=primitives.end();
363        ++itr)
364    {
365        switch((*itr)->getMode())
366        {
367            case(PrimitiveSet::TRIANGLES):
368            case(PrimitiveSet::TRIANGLE_STRIP):
369            case(PrimitiveSet::TRIANGLE_FAN):
370            case(PrimitiveSet::QUADS):
371            case(PrimitiveSet::QUAD_STRIP):
372            case(PrimitiveSet::POLYGON):
373                (*itr)->accept(taf);
374                break;
375            default:
376                new_primitives.push_back(*itr);
377                break;
378
379        }
380    }
381
382    float minimum_ratio_of_indices_to_unique_vertices = 1;
383    float ratio_of_indices_to_unique_vertices = ((float)taf._in_indices.size()/(float)numUnique);
384
385    OSG_INFO<<"TriStripVisitor::stripify(Geometry&): Number of indices"<<taf._in_indices.size()<<" numUnique"<< numUnique << std::endl;
386    OSG_INFO<<"TriStripVisitor::stripify(Geometry&):     ratio indices/numUnique"<< ratio_of_indices_to_unique_vertices << std::endl;
387
388    // only tri strip if there is point in doing so.
389    if (!taf._in_indices.empty() && ratio_of_indices_to_unique_vertices>=minimum_ratio_of_indices_to_unique_vertices)
390    {
391        OSG_INFO<<"TriStripVisitor::stripify(Geometry&):     doing tri strip"<< std::endl;
392
393        unsigned int in_numVertices = 0;
394        for(triangle_stripper::indices::iterator itr=taf._in_indices.begin();
395            itr!=taf._in_indices.end();
396            ++itr)
397        {
398            if (*itr>in_numVertices) in_numVertices=*itr;
399        }
400        // the largest indice is in_numVertices, but indices start at 0
401        // so increment to give to the corrent number of verticies.
402        ++in_numVertices;
403
404        // remap any shared vertex attributes
405        RemapArray ra(copyMapping);
406        arrayComparitor.accept(ra);
407
408        triangle_stripper::tri_stripper stripifier(taf._in_indices);
409        stripifier.SetCacheSize(_cacheSize);
410        stripifier.SetMinStripSize(_minStripSize);
411
412        triangle_stripper::primitive_vector outPrimitives;
413        stripifier.Strip(&outPrimitives);
414        if (outPrimitives.empty())
415        {
416            OSG_WARN<<"Error: TriStripVisitor::stripify(Geometry& geom) failed."<<std::endl;
417            return;
418        }
419
420        triangle_stripper::primitive_vector::iterator pitr;
421        if (_generateFourPointPrimitivesQuads)
422        {
423            OSG_INFO<<"Collecting all quads"<<std::endl;
424
425            typedef triangle_stripper::primitive_vector::iterator prim_iterator;
426            typedef std::multimap<unsigned int,prim_iterator> QuadMap;
427            QuadMap quadMap;
428
429            // pick out quads and place them in the quadMap, and also look for the max
430            for(pitr=outPrimitives.begin();
431                pitr!=outPrimitives.end();
432                ++pitr)
433            {
434                if (pitr->Indices.size()==4)
435                {
436                    std::swap(pitr->Indices[2],pitr->Indices[3]);
437                    unsigned int minValue = *(std::max_element(pitr->Indices.begin(),pitr->Indices.end()));
438                    quadMap.insert(QuadMap::value_type(minValue,pitr));
439                }
440            }
441
442
443            // handle the quads
444            if (!quadMap.empty())
445            {
446                IndexList indices;
447                indices.reserve(4*quadMap.size());
448
449                // adds all the quads into the quad primitive, in ascending order
450                // and the QuadMap stores the quad's in ascending order.
451                for(QuadMap::iterator qitr=quadMap.begin();
452                    qitr!=quadMap.end();
453                    ++qitr)
454                {
455                    pitr = qitr->second;
456
457                    unsigned int min_pos = 0;
458                    for(i=1;i<4;++i)
459                    {
460                        if (pitr->Indices[min_pos]>pitr->Indices[i])
461                            min_pos = i;
462                    }
463                    indices.push_back(pitr->Indices[min_pos]);
464                    indices.push_back(pitr->Indices[(min_pos+1)%4]);
465                    indices.push_back(pitr->Indices[(min_pos+2)%4]);
466                    indices.push_back(pitr->Indices[(min_pos+3)%4]);
467                }
468
469                bool inOrder = true;
470                unsigned int previousValue = indices.front();
471                for(IndexList::iterator qi_itr=indices.begin()+1;
472                    qi_itr!=indices.end() && inOrder;
473                    ++qi_itr)
474                {
475                    inOrder = (previousValue+1)==*qi_itr;
476                    previousValue = *qi_itr;
477                }
478
479
480                if (inOrder)
481                {
482                    new_primitives.push_back(new osg::DrawArrays(GL_QUADS,indices.front(),indices.size()));
483                }
484                else
485                {
486                    unsigned int maxValue = *(std::max_element(indices.begin(),indices.end()));
487
488                    if (maxValue>=65536)
489                    {
490                        osg::DrawElementsUInt* elements = new osg::DrawElementsUInt(GL_QUADS);
491                        std::copy(indices.begin(),indices.end(),std::back_inserter(*elements));
492                        new_primitives.push_back(elements);
493                    }
494                    else
495                    {
496                        osg::DrawElementsUShort* elements = new osg::DrawElementsUShort(GL_QUADS);
497                        std::copy(indices.begin(),indices.end(),std::back_inserter(*elements));
498                        new_primitives.push_back(elements);
499                    }
500                }
501            }
502        }
503
504        // handle non quad primitives
505        for(pitr=outPrimitives.begin();
506            pitr!=outPrimitives.end();
507            ++pitr)
508        {
509            if (!_generateFourPointPrimitivesQuads || pitr->Indices.size()!=4)
510            {
511                bool inOrder = true;
512                unsigned int previousValue = pitr->Indices.front();
513                for(triangle_stripper::indices::iterator qi_itr=pitr->Indices.begin()+1;
514                    qi_itr!=pitr->Indices.end() && inOrder;
515                    ++qi_itr)
516                {
517                    inOrder = (previousValue+1)==*qi_itr;
518                    previousValue = *qi_itr;
519                }
520
521                if (inOrder)
522                {
523                    new_primitives.push_back(new osg::DrawArrays(pitr->Type,pitr->Indices.front(),pitr->Indices.size()));
524                }
525                else
526                {
527                    unsigned int maxValue = *(std::max_element(pitr->Indices.begin(),pitr->Indices.end()));
528                    if (maxValue>=65536)
529                    {
530                        osg::DrawElementsUInt* elements = new osg::DrawElementsUInt(pitr->Type);
531                        elements->reserve(pitr->Indices.size());
532                        std::copy(pitr->Indices.begin(),pitr->Indices.end(),std::back_inserter(*elements));
533                        new_primitives.push_back(elements);
534                    }
535                    else
536                    {
537                        osg::DrawElementsUShort* elements = new osg::DrawElementsUShort(pitr->Type);
538                        elements->reserve(pitr->Indices.size());
539                        std::copy(pitr->Indices.begin(),pitr->Indices.end(),std::back_inserter(*elements));
540                        new_primitives.push_back(elements);
541                    }
542                }
543            }
544        }
545
546        geom.setPrimitiveSetList(new_primitives);
547
548        #if 0
549        // debugging code for indentifying the tri-strips.
550                osg::Vec4Array* colors = new osg::Vec4Array(new_primitives.size());
551                for(i=0;i<colors->size();++i)
552                {
553                    (*colors)[i].set(((float)rand()/(float)RAND_MAX),
554                                     ((float)rand()/(float)RAND_MAX),
555                                     ((float)rand()/(float)RAND_MAX),
556                                     1.0f);
557                }
558                geom.setColorArray(colors);
559                geom.setColorBinding(osg::Geometry::BIND_PER_PRIMITIVE_SET);
560        #endif
561    }
562    else
563    {
564        OSG_INFO<<"TriStripVisitor::stripify(Geometry&):     not doing tri strip *****************"<< std::endl;
565    }
566
567}
568
569void TriStripVisitor::stripify()
570{
571    for(GeometryList::iterator itr=_geometryList.begin();
572        itr!=_geometryList.end();
573        ++itr)
574    {
575        stripify(*(*itr));
576
577        // osgUtil::SmoothingVisitor sv;
578        // sv.smooth(*(*itr));
579    }
580}
581
582void TriStripVisitor::apply(Geode& geode)
583{
584    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
585    {
586        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
587        if (geom) _geometryList.insert(geom);
588    }
589}
Note: See TracBrowser for help on using the browser.