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

Revision 13502, 35.5 kB (checked in by robert, 6 hours ago)

From Alberto Luaces,"the current code uses the preprocessor for generating the plugin path in
a way that when CMAKE_INSTALL_PREFIX contains something along the lines
of

/usr/x86_64-linux-gnu/

it gets substituted as

/usr/x86_64-1-gnu/

that is, the string is preprocessed again, thereby making changes to
anything that matches any defined symbol, as "linux" in this example
(https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=763816).

Quoting that path directly in CMake scripts solves that problem.
"

  • Property svn:eol-style set to native
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 * Copyright (C) 2010 Tim Moore
3 *
4 * This library is open source and may be redistributed and/or modified under
5 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
6 * (at your option) any later version.  The full license is in LICENSE file
7 * included with this distribution, and on the openscenegraph.org website.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 * OpenSceneGraph Public License for more details.
13*/
14
15#include <cassert>
16#include <limits>
17
18#include <algorithm>
19#include <utility>
20#include <vector>
21
22#include <iostream>
23
24#include <osg/Geometry>
25#include <osg/Math>
26#include <osg/PrimitiveSet>
27#include <osg/TriangleIndexFunctor>
28
29#include <osgUtil/MeshOptimizers>
30
31using namespace std;
32using namespace osg;
33
34namespace osgUtil
35{
36
37void GeometryCollector::reset()
38{
39    _geometryList.clear();
40}
41
42void GeometryCollector::apply(Geode& geode)
43{
44    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
45    {
46        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
47        if (geom) _geometryList.insert(geom);
48    }
49}
50
51namespace
52{
53typedef std::vector<unsigned int> IndexList;
54
55// A helper class that gathers up all the attribute arrays of an
56// osg::Geometry object that are BIND_PER_VERTEX and runs an
57// ArrayVisitor on them.
58struct GeometryArrayGatherer
59{
60    typedef std::vector<osg::Array*> ArrayList;
61
62    GeometryArrayGatherer(osg::Geometry& geometry)
63        : _useDrawElements(true)
64    {
65        add(geometry.getVertexArray(),osg::Geometry::BIND_PER_VERTEX);
66        add(geometry.getNormalArray(),geometry.getNormalBinding());
67        add(geometry.getColorArray(),geometry.getColorBinding());
68        add(geometry.getSecondaryColorArray(),geometry.getSecondaryColorBinding());
69        add(geometry.getFogCoordArray(),geometry.getFogCoordBinding());
70        unsigned int i;
71        for(i=0;i<geometry.getNumTexCoordArrays();++i)
72        {
73            add(geometry.getTexCoordArray(i),osg::Geometry::BIND_PER_VERTEX);
74        }
75        for(i=0;i<geometry.getNumVertexAttribArrays();++i)
76        {
77            add(geometry.getVertexAttribArray(i),geometry.getVertexAttribBinding(i));
78        }
79    }
80
81    void add(osg::Array* array, osg::Geometry::AttributeBinding binding)
82    {
83        if (binding == osg::Geometry::BIND_PER_VERTEX)
84        {
85            if (array)
86                _arrayList.push_back(array);
87        }
88    }
89
90    void accept(osg::ArrayVisitor& av)
91    {
92        for(ArrayList::iterator itr=_arrayList.begin();
93            itr!=_arrayList.end();
94            ++itr)
95        {
96            (*itr)->accept(av);
97        }
98    }
99
100    ArrayList _arrayList;
101    // True if geometry contains bindings that are compatible with
102    // DrawElements.
103    bool _useDrawElements;
104};
105
106// Compare vertices in a mesh using all their attributes. The vertices
107// are identified by their index. Extracted from TriStripVisitor.cpp
108struct VertexAttribComparitor : public GeometryArrayGatherer
109{
110    VertexAttribComparitor(osg::Geometry& geometry)
111        : GeometryArrayGatherer(geometry)
112    {
113    }
114
115    bool operator() (unsigned int lhs, unsigned int rhs) const
116    {
117        for(ArrayList::const_iterator itr=_arrayList.begin();
118            itr!=_arrayList.end();
119            ++itr)
120        {
121            int compare = (*itr)->compare(lhs,rhs);
122            if (compare==-1) return true;
123            if (compare==1) return false;
124        }
125        return false;
126    }
127
128    int compare(unsigned int lhs, unsigned int rhs)
129    {
130        for(ArrayList::iterator itr=_arrayList.begin();
131            itr!=_arrayList.end();
132            ++itr)
133        {
134            int compare = (*itr)->compare(lhs,rhs);
135            if (compare==-1) return -1;
136            if (compare==1) return 1;
137        }
138        return 0;
139    }
140
141protected:
142    VertexAttribComparitor& operator = (const VertexAttribComparitor&) { return *this; }
143
144};
145
146// Compact the vertex attribute arrays. Also stolen from TriStripVisitor
147class RemapArray : public osg::ArrayVisitor
148{
149    public:
150        RemapArray(const IndexList& remapping):_remapping(remapping) {}
151
152        const IndexList& _remapping;
153
154        template<class T>
155        inline void remap(T& array)
156        {
157            for(unsigned int i=0;i<_remapping.size();++i)
158            {
159                if (i!=_remapping[i])
160                {
161                    array[i] = array[_remapping[i]];
162                }
163            }
164            array.erase(array.begin()+_remapping.size(),array.end());
165        }
166
167        virtual void apply(osg::Array&) {}
168        virtual void apply(osg::ByteArray& array) { remap(array); }
169        virtual void apply(osg::ShortArray& array) { remap(array); }
170        virtual void apply(osg::IntArray& array) { remap(array); }
171        virtual void apply(osg::UByteArray& array) { remap(array); }
172        virtual void apply(osg::UShortArray& array) { remap(array); }
173        virtual void apply(osg::UIntArray& array) { remap(array); }
174        virtual void apply(osg::FloatArray& array) { remap(array); }
175        virtual void apply(osg::DoubleArray& array) { remap(array); }
176
177        virtual void apply(osg::Vec2Array& array) { remap(array); }
178        virtual void apply(osg::Vec3Array& array) { remap(array); }
179        virtual void apply(osg::Vec4Array& array) { remap(array); }
180
181        virtual void apply(osg::Vec4ubArray& array) { remap(array); }
182
183        virtual void apply(osg::Vec2bArray& array) { remap(array); }
184        virtual void apply(osg::Vec3bArray& array) { remap(array); }
185        virtual void apply(osg::Vec4bArray& array) { remap(array); }
186
187        virtual void apply(osg::Vec2sArray& array) { remap(array); }
188        virtual void apply(osg::Vec3sArray& array) { remap(array); }
189        virtual void apply(osg::Vec4sArray& array) { remap(array); }
190
191        virtual void apply(osg::Vec2dArray& array) { remap(array); }
192        virtual void apply(osg::Vec3dArray& array) { remap(array); }
193        virtual void apply(osg::Vec4dArray& array) { remap(array); }
194
195        virtual void apply(osg::MatrixfArray& array) { remap(array); }
196protected:
197
198        RemapArray& operator = (const RemapArray&) { return *this; }
199};
200
201
202// Construct an index list of triangles for DrawElements for any input
203// primitives.
204struct MyTriangleOperator
205{
206
207    IndexList _remapIndices;
208    IndexList _in_indices;
209
210    inline void operator()(unsigned int p1, unsigned int p2, unsigned int p3)
211    {
212        if (_remapIndices.empty())
213        {
214            _in_indices.push_back(p1);
215            _in_indices.push_back(p2);
216            _in_indices.push_back(p3);
217        }
218        else
219        {
220            _in_indices.push_back(_remapIndices[p1]);
221            _in_indices.push_back(_remapIndices[p2]);
222            _in_indices.push_back(_remapIndices[p3]);
223        }
224    }
225
226};
227typedef osg::TriangleIndexFunctor<MyTriangleOperator> MyTriangleIndexFunctor;
228}
229
230void IndexMeshVisitor::makeMesh(Geometry& geom)
231{
232    if (geom.containsDeprecatedData()) geom.fixDeprecatedData();
233
234    if (geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
235
236    if (geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
237
238    if (geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
239
240    if (geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
241
242    // no point optimizing if we don't have enough vertices.
243    if (!geom.getVertexArray() || geom.getVertexArray()->getNumElements()<3) return;
244
245    // check for the existence of surface primitives
246    unsigned int numSurfacePrimitives = 0;
247    unsigned int numNonIndexedPrimitives = 0;
248    Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList();
249    Geometry::PrimitiveSetList::iterator itr;
250    for(itr=primitives.begin();
251        itr!=primitives.end();
252        ++itr)
253    {
254        switch((*itr)->getMode())
255        {
256            case(PrimitiveSet::TRIANGLES):
257            case(PrimitiveSet::TRIANGLE_STRIP):
258            case(PrimitiveSet::TRIANGLE_FAN):
259            case(PrimitiveSet::QUADS):
260            case(PrimitiveSet::QUAD_STRIP):
261            case(PrimitiveSet::POLYGON):
262                ++numSurfacePrimitives;
263                break;
264            default:
265                // For now, only deal with polygons
266                return;
267        }
268        PrimitiveSet::Type type = (*itr)->getType();
269        if (!(type == PrimitiveSet::DrawElementsUBytePrimitiveType
270              || type == PrimitiveSet::DrawElementsUShortPrimitiveType
271              || type == PrimitiveSet::DrawElementsUIntPrimitiveType))
272            numNonIndexedPrimitives++;
273    }
274
275    // nothing to index
276    if (!numSurfacePrimitives || !numNonIndexedPrimitives) return;
277
278    // compute duplicate vertices
279    typedef std::vector<unsigned int> IndexList;
280    unsigned int numVertices = geom.getVertexArray()->getNumElements();
281    IndexList indices(numVertices);
282    unsigned int i,j;
283    for(i=0;i<numVertices;++i)
284    {
285        indices[i] = i;
286    }
287
288    VertexAttribComparitor arrayComparitor(geom);
289    std::sort(indices.begin(),indices.end(),arrayComparitor);
290
291    unsigned int lastUnique = 0;
292    unsigned int numUnique = 1;
293    for(i=1;i<numVertices;++i)
294    {
295        if (arrayComparitor.compare(indices[lastUnique],indices[i]) != 0)
296        {
297            lastUnique = i;
298            ++numUnique;
299        }
300
301    }
302    IndexList remapDuplicatesToOrignals(numVertices);
303    lastUnique = 0;
304    for(i=1;i<numVertices;++i)
305    {
306        if (arrayComparitor.compare(indices[lastUnique],indices[i])!=0)
307        {
308            // found a new vertex entry, so previous run of duplicates needs
309            // to be put together.
310            unsigned int min_index = indices[lastUnique];
311            for(j=lastUnique+1;j<i;++j)
312            {
313                min_index = osg::minimum(min_index,indices[j]);
314            }
315            for(j=lastUnique;j<i;++j)
316            {
317                remapDuplicatesToOrignals[indices[j]]=min_index;
318            }
319            lastUnique = i;
320        }
321
322    }
323    unsigned int min_index = indices[lastUnique];
324    for(j=lastUnique+1;j<i;++j)
325    {
326        min_index = osg::minimum(min_index,indices[j]);
327    }
328    for(j=lastUnique;j<i;++j)
329    {
330        remapDuplicatesToOrignals[indices[j]]=min_index;
331    }
332
333
334    // copy the arrays.
335    IndexList finalMapping(numVertices);
336    IndexList copyMapping;
337    copyMapping.reserve(numUnique);
338    unsigned int currentIndex=0;
339    for(i=0;i<numVertices;++i)
340    {
341        if (remapDuplicatesToOrignals[i]==i)
342        {
343            finalMapping[i] = currentIndex;
344            copyMapping.push_back(i);
345            currentIndex++;
346        }
347    }
348
349    for(i=0;i<numVertices;++i)
350    {
351        if (remapDuplicatesToOrignals[i]!=i)
352        {
353            finalMapping[i] = finalMapping[remapDuplicatesToOrignals[i]];
354        }
355    }
356
357
358    MyTriangleIndexFunctor taf;
359    taf._remapIndices.swap(finalMapping);
360
361    Geometry::PrimitiveSetList new_primitives;
362    new_primitives.reserve(primitives.size());
363
364    for(itr=primitives.begin();
365        itr!=primitives.end();
366        ++itr)
367    {
368        // For now we only have primitive sets that play nicely with
369        // the TriangleIndexFunctor.
370        (*itr)->accept(taf);
371    }
372
373    // remap any shared vertex attributes
374    RemapArray ra(copyMapping);
375    arrayComparitor.accept(ra);
376    if (taf._in_indices.size() < 65536)
377    {
378        osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES);
379        for (IndexList::iterator itr = taf._in_indices.begin(),
380                 end = taf._in_indices.end();
381             itr != end;
382            ++itr)
383        {
384            elements->push_back((GLushort)(*itr));
385        }
386        new_primitives.push_back(elements);
387    }
388    else
389    {
390        osg::DrawElementsUInt* elements
391            = new DrawElementsUInt(GL_TRIANGLES, taf._in_indices.begin(),
392                                   taf._in_indices.end());
393        new_primitives.push_back(elements);
394    }
395    geom.setPrimitiveSetList(new_primitives);
396}
397
398void IndexMeshVisitor::makeMesh()
399{
400    for(GeometryList::iterator itr=_geometryList.begin();
401        itr!=_geometryList.end();
402        ++itr)
403    {
404        makeMesh(*(*itr));
405    }
406}
407
408namespace
409{
410// A simulation of a Least Recently Used cache. Position in the cache
411// corresponds to when the vertex was used i.e., 0 is the most
412// recently used.
413struct LRUCache
414{
415    LRUCache(size_t maxSize_) : maxSize(maxSize_)
416    {
417        entries.reserve(maxSize_ + 3);
418    }
419    vector<unsigned> entries;
420    size_t maxSize;
421
422    // Add a list of values to the cache
423    void addEntries(unsigned* begin, unsigned* end)
424    {
425        // If any of the new vertices are already in the cache, remove
426        // them, leaving some room at the front of the cache.
427        vector<unsigned>::reverse_iterator validEnd = entries.rend();
428        for (unsigned* pent = begin; pent != end; ++pent)
429        {
430            validEnd = remove(entries.rbegin(), validEnd, *pent);
431        }
432        // Now make room still needed for new cache entries
433        size_t newEnts = end - begin;
434        int spaceNeeded = newEnts - (entries.rend() - validEnd);
435        if (spaceNeeded > 0)
436        {
437            if (maxSize - entries.size() >= static_cast<unsigned>(spaceNeeded))
438                entries.resize(entries.size() + spaceNeeded);
439            else if (entries.size() < maxSize)
440                entries.resize(maxSize);
441            copy_backward(entries.begin() + newEnts - spaceNeeded,
442                          entries.end() - spaceNeeded, entries.end());
443        }
444        copy(begin, end, entries.begin());
445    }
446
447    bool empty()
448    {
449        return entries.empty();
450    }
451};
452
453// A list of triangles that use a vertex is associated with the Vertex
454// structure in another array.
455struct Vertex
456{
457    int cachePosition;
458    float score;
459    int trisUsing;
460    int numActiveTris;          // triangles left to process
461    size_t triList;             // index to start of triangle storage
462    Vertex()
463        : cachePosition(-1), score(0.0f), trisUsing(0), numActiveTris(0), triList(0)
464    {
465    }
466};
467
468// Code from Tom Forsyth's article. The algorithm is described in
469// detail at
470// http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html.
471// In summary, vertices are assigned a score based on the number of
472// triangles that use it (valence) and the vertex's position in the
473// model of the vertex cache, if any. Triangles are also given a
474// score, which is the sum of the scores of its vertices. The triangle
475// with the best score is added to the draw list, its vertices are
476// added and / or moved in the cache, the scores of vertices in the
477// cache and ejected from the cache are updated. Then the scores of
478// triangles that use those vertices are updated.
479//
480// Unless the cache is empty, the "best" triangle is found by
481// searching triangles that use vertices in the cache, not the whole
482// mesh. This keeps the algorithm running in time proportional to the
483// size of the mesh.
484
485// The "magic" scoring functions are described in the paper.
486const float cacheDecayPower = 1.5f;
487const float lastTriScore = 0.75f;
488const float valenceBoostScale = 2.0f;
489const float valenceBoostPower = 0.5f;
490
491const int maxCacheSize = 32;
492
493float findVertexScore (Vertex& vert)
494{
495
496    if (vert.numActiveTris == 0)
497    {
498        // No tri needs this vertex!
499        return -1.0f;
500    }
501    float score = 0.0f;
502    int cachePosition = vert.cachePosition;
503
504    if (cachePosition < 0)
505    {
506        // Vertex is not in FIFO cache - no score.
507    }
508    else
509    {
510        if (cachePosition < 3)
511        {
512            // This vertex was used in the last triangle,
513            // so it has a fixed score, whichever of the three
514            // it's in. Otherwise, you can get very different
515            // answers depending on whether you add
516            // the triangle 1,2,3 or 3,1,2 - which is silly.
517            score = lastTriScore;
518        }
519        else
520        {
521            assert (cachePosition < maxCacheSize);
522            // Points for being high in the cache.
523            const float scaler = 1.0f / (maxCacheSize - 3);
524            score = 1.0f - (cachePosition - 3 ) * scaler;
525            score = powf(score, cacheDecayPower);
526        }
527    }
528    // Bonus points for having a low number of tris still to
529    // use the vert, so we get rid of lone verts quickly.
530    float valenceBoost = powf(vert.numActiveTris, -valenceBoostPower);
531    score += valenceBoostScale * valenceBoost;
532    return score;
533}
534
535
536typedef vector<Vertex> VertexList;
537
538struct Triangle
539{
540    float score;
541    unsigned verts[3];
542};
543
544typedef vector<Triangle> TriangleList;
545
546inline float findTriangleScore(Triangle& tri, const VertexList& vertices)
547{
548    float result = 0.0f;
549    for (int i = 0; i < 3; ++i)
550        result += vertices[tri.verts[i]].score;
551    return result;
552}
553
554typedef std::pair<unsigned, float> TriangleScore;
555
556TriangleScore computeTriScores(Vertex& vert, const VertexList& vertices,
557                               TriangleList& triangles, vector<unsigned>& triStore)
558{
559    float bestScore = 0.0;
560    unsigned bestTri = 0;
561    for (size_t i = vert.triList;
562         i < vert.triList + vert.numActiveTris;
563         ++i)
564    {
565        unsigned tri = triStore[i];
566        float score = triangles[tri].score = findTriangleScore(triangles[tri],
567                                                               vertices);
568        if (score > bestScore)
569        {
570            bestScore = score;
571            bestTri = tri;
572        }
573    }
574    return make_pair(bestTri, bestScore);
575}
576
577typedef vector<Triangle> TriangleList;
578
579struct TriangleCounterOperator
580{
581    VertexList* vertices;
582    int triangleCount;
583    TriangleCounterOperator() : vertices(0), triangleCount(0) {}
584
585    void doVertex(unsigned p)
586    {
587        if (vertices->size() <= p)
588            vertices->resize(p + 1);
589        (*vertices)[p].trisUsing++;
590    }
591
592    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
593    {
594        if (p1 == p2 || p2 == p3 || p1 == p3)
595            return;
596        doVertex(p1);
597        doVertex(p2);
598        doVertex(p3);
599        triangleCount++;
600    }
601};
602
603struct TriangleCounter : public TriangleIndexFunctor<TriangleCounterOperator>
604{
605    TriangleCounter(vector<Vertex>* vertices_)
606    {
607        vertices = vertices_;
608    }
609};
610
611// Initialize the vertex triangle lists and the triangle data structures
612struct TriangleAddOperator
613{
614    VertexList* vertices;
615    vector<unsigned>* vertexTris;
616    TriangleList* triangles;
617    int triIdx;
618    TriangleAddOperator() : vertices(0), triIdx(0) {}
619
620    void doVertex(unsigned p)
621    {
622        (*vertexTris)[(*vertices)[p].triList + (*vertices)[p].numActiveTris++]
623            = triIdx;
624    }
625
626    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
627    {
628        if (p1 == p2 || p2 == p3 || p1 == p3)
629            return;
630        doVertex(p1);
631        doVertex(p2);
632        doVertex(p3);
633    (*triangles)[triIdx].verts[0] = p1;
634    (*triangles)[triIdx].verts[1] = p2;
635    (*triangles)[triIdx].verts[2] = p3;
636    triIdx++;
637    }
638};
639
640struct TriangleAdder : public TriangleIndexFunctor<TriangleAddOperator>
641{
642    TriangleAdder(VertexList* vertices_, vector<unsigned>* vertexTris_,
643                  TriangleList* triangles_)
644    {
645        vertices = vertices_;
646        vertexTris = vertexTris_;
647        triangles = triangles_;
648    }
649};
650
651struct CompareTriangle
652{
653    bool operator()(const Triangle& lhs, const Triangle& rhs)
654    {
655        return lhs.score < rhs.score;
656    }
657};
658}
659
660void VertexCacheVisitor::optimizeVertices(Geometry& geom)
661{
662    Array* vertArray = geom.getVertexArray();
663    if (!vertArray)
664        return;
665    unsigned vertArraySize = vertArray->getNumElements();
666    // If all the vertices fit in the cache, there's no point in
667    // doing this optimization.
668    if (vertArraySize <= 16)
669        return;
670    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
671    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
672             end = primSets.end();
673         itr != end;
674         ++itr)
675    {
676        // Can only deal with polygons.
677        switch ((*itr)->getMode())
678        {
679        case(PrimitiveSet::TRIANGLES):
680        case(PrimitiveSet::TRIANGLE_STRIP):
681        case(PrimitiveSet::TRIANGLE_FAN):
682        case(PrimitiveSet::QUADS):
683        case(PrimitiveSet::QUAD_STRIP):
684        case(PrimitiveSet::POLYGON):
685            break;
686        default:
687            return;
688        }
689        PrimitiveSet::Type type = (*itr)->getType();
690        if (type != PrimitiveSet::DrawElementsUBytePrimitiveType
691            && type != PrimitiveSet::DrawElementsUShortPrimitiveType
692            && type != PrimitiveSet::DrawElementsUIntPrimitiveType)
693            return;
694    }
695#if 0
696    VertexCacheMissVisitor missv;
697    missv.doGeometry(geom);
698    cout << "Before optimization: misses: " << missv.misses
699         << " triangles: " << missv.triangles << " acmr: ";
700    if (missv.triangles > 0.0)
701        cout << (double)missv.misses / (double)missv.triangles << "\n";
702    else
703        cout << "0.0\n";
704    missv.reset();
705#endif
706    vector<unsigned> newVertList;
707    doVertexOptimization(geom, newVertList);
708    Geometry::PrimitiveSetList newPrims;
709    if (vertArraySize < 65536)
710    {
711        osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES);
712        elements->reserve(newVertList.size());
713        for (vector<unsigned>::iterator itr = newVertList.begin(),
714                 end = newVertList.end();
715             itr != end;
716             ++itr)
717            elements->push_back((GLushort)*itr);
718        if (geom.getUseVertexBufferObjects())
719        {
720            elements->setElementBufferObject(new ElementBufferObject);
721        }
722        newPrims.push_back(elements);
723    }
724    else
725    {
726        osg::DrawElementsUInt* elements
727            = new DrawElementsUInt(GL_TRIANGLES, newVertList.begin(),
728                                   newVertList.end());
729        if (geom.getUseVertexBufferObjects())
730        {
731            elements->setElementBufferObject(new ElementBufferObject);
732        }
733        newPrims.push_back(elements);
734    }
735
736    geom.setPrimitiveSetList(newPrims);
737#if 0
738    missv.doGeometry(geom);
739    cout << "After optimization: misses: " << missv.misses
740         << " triangles: " << missv.triangles << " acmr: ";
741    if (missv.triangles > 0.0)
742        cout << (double)missv.misses / (double)missv.triangles << "\n";
743    else
744        cout << "0.0\n";
745#endif
746    geom.dirtyDisplayList();
747}
748
749// The main optimization loop
750void VertexCacheVisitor::doVertexOptimization(Geometry& geom,
751                                              vector<unsigned>& vertDrawList)
752{
753    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
754    // lists for all the vertices and triangles
755    VertexList vertices;
756    TriangleList triangles;
757    TriangleCounter triCounter(&vertices);
758    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
759             end = primSets.end();
760         itr != end;
761         ++itr)
762        (*itr)->accept(triCounter);
763    triangles.resize(triCounter.triangleCount);
764    // Get total of triangles used by all the vertices
765    size_t vertTrisSize = 0;
766    for (VertexList::iterator itr = vertices.begin(), end = vertices.end();
767         itr != end;
768         ++itr)
769    {
770        itr->triList = vertTrisSize;
771        vertTrisSize += itr->trisUsing;
772    }
773    // Store for lists of triangles (indices) used by the vertices
774    vector<unsigned> vertTriListStore(vertTrisSize);
775    TriangleAdder triAdder(&vertices, &vertTriListStore, &triangles);
776    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
777             end = primSets.end();
778         itr != end;
779         ++itr)
780        (*itr)->accept(triAdder);
781    // Set up initial scores for vertices and triangles
782    for (VertexList::iterator itr = vertices.begin(), end = vertices.end();
783         itr != end;
784         ++itr)
785        itr->score = findVertexScore(*itr);
786    for (TriangleList::iterator itr = triangles.begin(), end = triangles.end();
787         itr != end;
788         ++itr)
789    {
790        itr->score = 0.0f;
791        for (int i = 0; i < 3; ++i)
792            itr->score += vertices[itr->verts[i]].score;
793    }
794    // Add Triangles to the draw list until there are no more.
795    unsigned trisLeft = triangles.size();
796    vertDrawList.reserve(trisLeft * 3);
797    LRUCache cache(maxCacheSize);
798    while (trisLeft-- > 0)
799    {
800        Triangle* triToAdd = 0;
801        float bestScore = 0.0;
802        for (vector<unsigned>::const_iterator itr = cache.entries.begin(),
803                 end = cache.entries.end();
804             itr != end;
805             ++itr)
806        {
807            TriangleScore tscore =  computeTriScores(vertices[*itr], vertices,
808                                                     triangles, vertTriListStore);
809            if (tscore.second > bestScore)
810            {
811                bestScore = tscore.second;
812                triToAdd = &triangles[tscore.first];
813            }
814        }
815        if (!triToAdd)
816        {
817            // The cache was empty, or all the triangles that use
818            // vertices in the cache have already been added.
819            OSG_DEBUG << "VertexCacheVisitor searching all triangles" << std::endl;
820            TriangleList::iterator maxItr
821                = max_element(triangles.begin(), triangles.end(),
822                              CompareTriangle());
823            triToAdd = &(*maxItr);
824        }
825        assert(triToAdd != 0 && triToAdd->score > 0.0);
826        // Add triangle vertices, and remove triangle from the
827        // vertices that use it.
828        triToAdd->score = -1.0f;
829        unsigned triToAddIdx = triToAdd - &triangles[0];
830        for (unsigned i = 0; i < 3; ++i)
831        {
832            unsigned vertIdx = triToAdd->verts[i];
833            Vertex* vert = &vertices[vertIdx];
834            vertDrawList.push_back(vertIdx);
835            remove(vertTriListStore.begin() + vert->triList,
836                   vertTriListStore.begin() + vert->triList
837                   + vert->numActiveTris,
838                   triToAddIdx);
839            vert->numActiveTris--;
840        }
841        // Assume that the three oldest cache entries will get kicked
842        // out, so reset their scores and those of their
843        // triangles. Otherwise we'll "lose" them and not be able to
844        // change their scores.
845        if (cache.maxSize - cache.entries.size() < 3)
846        {
847            for (vector<unsigned>::iterator itr = cache.entries.end() - 3,
848                     end = cache.entries.end();
849                 itr != end;
850                ++itr)
851            {
852                vertices[*itr].cachePosition = -1;
853                vertices[*itr].score = findVertexScore(vertices[*itr]);
854            }
855            for (vector<unsigned>::iterator itr = cache.entries.end() - 3,
856                     end = cache.entries.end();
857                 itr != end;
858                ++itr)
859                computeTriScores(vertices[*itr], vertices, triangles,
860                                 vertTriListStore);
861        }
862        cache.addEntries(&triToAdd->verts[0], &triToAdd->verts[3]);
863        for (vector<unsigned>::const_iterator itr = cache.entries.begin(),
864                 end = cache.entries.end();
865             itr != end;
866             ++itr)
867        {
868            unsigned vertIdx = *itr;
869            vertices[vertIdx].cachePosition = itr - cache.entries.begin();
870            vertices[vertIdx].score = findVertexScore(vertices[vertIdx]);
871        }
872     }
873}
874
875void VertexCacheVisitor::optimizeVertices()
876{
877    for(GeometryList::iterator itr=_geometryList.begin();
878        itr!=_geometryList.end();
879        ++itr)
880    {
881        optimizeVertices(*(*itr));
882    }
883}
884
885VertexCacheMissVisitor::VertexCacheMissVisitor(unsigned cacheSize)
886    : osg::NodeVisitor(NodeVisitor::TRAVERSE_ALL_CHILDREN), misses(0),
887      triangles(0), _cacheSize(cacheSize)
888{
889}
890
891void VertexCacheMissVisitor::reset()
892{
893    misses = 0;
894    triangles = 0;
895}
896
897void VertexCacheMissVisitor::apply(Geode& geode)
898{
899    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
900    {
901        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
902        if (geom)
903            doGeometry(*geom);
904    }
905}
906
907namespace
908{
909// The cache miss algorithm models an LRU cache because it results in an
910// order that is insensitive to the actual cache size of the GPU. Real
911// GPUs use a FIFO cache, so the statistics gatherer simulates that.
912struct FIFOCache
913{
914    FIFOCache(size_t maxSize_) : maxSize(maxSize_)
915    {
916        entries.reserve(maxSize_);
917    }
918    vector<unsigned> entries;
919    size_t maxSize;
920
921    // Add a list of values to the cache
922    void addEntries(unsigned* begin, unsigned* end)
923    {
924        // Make room for new cache entries
925        size_t newEnts = end - begin;
926        if (entries.size() < maxSize)
927            entries.resize(osg::minimum(entries.size() + newEnts, maxSize));
928        vector<unsigned>::iterator copyEnd = entries.end() - newEnts;
929        copy_backward(entries.begin(), copyEnd, entries.end());
930        copy(begin, end, entries.begin());
931    }
932
933    bool empty()
934    {
935        return entries.empty();
936    }
937};
938
939// Insert vertices in a cache and record cache misses
940struct CacheRecordOperator
941{
942    CacheRecordOperator() : cache(0), misses(0), triangles(0) {}
943    FIFOCache* cache;
944    unsigned misses;
945    unsigned triangles;
946    void operator()(unsigned p1, unsigned p2, unsigned p3)
947    {
948        unsigned verts[3];
949        verts[0] = p1;
950        verts[1] = p2;
951        verts[2] = p3;
952        triangles++;
953        for (int i = 0; i < 3; ++i)
954        {
955            if (find(cache->entries.begin(), cache->entries.end(), verts[i])
956                == cache->entries.end())
957                misses++;
958        }
959        cache->addEntries(&verts[0], &verts[3]);
960    }
961};
962
963struct CacheRecorder : public TriangleIndexFunctor<CacheRecordOperator>
964{
965    CacheRecorder(unsigned cacheSize)
966    {
967        cache = new FIFOCache(cacheSize);
968    }
969
970    ~CacheRecorder()
971    {
972        delete cache;
973    }
974};
975}
976
977void VertexCacheMissVisitor::doGeometry(Geometry& geom)
978{
979    Array* vertArray = geom.getVertexArray();
980    if (!vertArray)
981        return;
982    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
983    CacheRecorder recorder(_cacheSize);
984    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
985             end = primSets.end();
986         itr != end;
987         ++itr)
988    {
989        (*itr)->accept(recorder);
990    }
991    misses += recorder.misses;
992    triangles += recorder.triangles;
993}
994
995namespace
996{
997// Move the values in an array to new positions, based on the
998// remapping table. remapping[i] contains element i's new position, if
999// any.  Unlike RemapArray in TriStripVisitor, this code doesn't
1000// assume that elements only move downward in the array.
1001class Remapper : public osg::ArrayVisitor
1002{
1003public:
1004    static const unsigned invalidIndex;
1005    Remapper(const vector<unsigned>& remapping)
1006        : _remapping(remapping), _newsize(0)
1007    {
1008        for (vector<unsigned>::const_iterator itr = _remapping.begin(),
1009                 end = _remapping.end();
1010             itr != end;
1011             ++itr)
1012            if (*itr != invalidIndex)
1013                ++_newsize;
1014    }
1015
1016    const vector<unsigned>& _remapping;
1017    size_t _newsize;
1018
1019    template<class T>
1020    inline void remap(T& array)
1021    {
1022        ref_ptr<T> newarray = new T(_newsize);
1023        T* newptr = newarray.get();
1024        for (size_t i = 0; i < array.size(); ++i)
1025            if (_remapping[i] != invalidIndex)
1026                (*newptr)[_remapping[i]] = array[i];
1027        array.swap(*newptr);
1028
1029    }
1030
1031    virtual void apply(osg::Array&) {}
1032    virtual void apply(osg::ByteArray& array) { remap(array); }
1033    virtual void apply(osg::ShortArray& array) { remap(array); }
1034    virtual void apply(osg::IntArray& array) { remap(array); }
1035    virtual void apply(osg::UByteArray& array) { remap(array); }
1036    virtual void apply(osg::UShortArray& array) { remap(array); }
1037    virtual void apply(osg::UIntArray& array) { remap(array); }
1038    virtual void apply(osg::FloatArray& array) { remap(array); }
1039    virtual void apply(osg::DoubleArray& array) { remap(array); }
1040
1041    virtual void apply(osg::Vec2Array& array) { remap(array); }
1042    virtual void apply(osg::Vec3Array& array) { remap(array); }
1043    virtual void apply(osg::Vec4Array& array) { remap(array); }
1044
1045    virtual void apply(osg::Vec4ubArray& array) { remap(array); }
1046
1047    virtual void apply(osg::Vec2bArray& array) { remap(array); }
1048    virtual void apply(osg::Vec3bArray& array) { remap(array); }
1049    virtual void apply(osg::Vec4bArray& array) { remap(array); }
1050
1051    virtual void apply(osg::Vec2sArray& array) { remap(array); }
1052    virtual void apply(osg::Vec3sArray& array) { remap(array); }
1053    virtual void apply(osg::Vec4sArray& array) { remap(array); }
1054
1055    virtual void apply(osg::Vec2dArray& array) { remap(array); }
1056    virtual void apply(osg::Vec3dArray& array) { remap(array); }
1057    virtual void apply(osg::Vec4dArray& array) { remap(array); }
1058
1059    virtual void apply(osg::MatrixfArray& array) { remap(array); }
1060};
1061
1062const unsigned Remapper::invalidIndex = std::numeric_limits<unsigned>::max();
1063
1064// Record the order in which vertices in a Geometry are used.
1065struct VertexReorderOperator
1066{
1067    unsigned seq;
1068    vector<unsigned> remap;
1069
1070    VertexReorderOperator() : seq(0)
1071    {
1072    }
1073
1074    void inline doVertex(unsigned v)
1075    {
1076        if (remap[v] == Remapper::invalidIndex)
1077            remap[v] = seq++;
1078    }
1079    void operator()(unsigned p1, unsigned p2, unsigned p3)
1080    {
1081        doVertex(p1);
1082        doVertex(p2);
1083        doVertex(p3);
1084    }
1085};
1086
1087struct VertexReorder : public TriangleIndexFunctor<VertexReorderOperator>
1088{
1089    VertexReorder(unsigned numVerts)
1090    {
1091        remap.resize(numVerts, Remapper::invalidIndex);
1092    }
1093
1094};
1095}
1096
1097void VertexAccessOrderVisitor::optimizeOrder()
1098{
1099    for (GeometryList::iterator itr = _geometryList.begin(), end = _geometryList.end();
1100         itr != end;
1101         ++itr)
1102    {
1103        optimizeOrder(*(*itr));
1104    }
1105}
1106
1107template<typename DE>
1108inline void reorderDrawElements(DE& drawElements,
1109                                const vector<unsigned>& reorder)
1110{
1111    for (typename DE::iterator itr = drawElements.begin(), end = drawElements.end();
1112         itr != end;
1113         ++itr)
1114    {
1115        *itr = static_cast<typename DE::value_type>(reorder[*itr]);
1116    }
1117}
1118
1119void VertexAccessOrderVisitor::optimizeOrder(Geometry& geom)
1120{
1121    Array* vertArray = geom.getVertexArray();
1122    if (!vertArray)
1123        return;
1124    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
1125    GeometryArrayGatherer gatherer(geom);
1126    if (!gatherer._useDrawElements)
1127        return;
1128    VertexReorder vr(vertArray->getNumElements());
1129    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
1130             end = primSets.end();
1131         itr != end;
1132         ++itr)
1133    {
1134        PrimitiveSet* ps = itr->get();
1135        PrimitiveSet::Type type = ps->getType();
1136        if (type != PrimitiveSet::DrawElementsUBytePrimitiveType
1137            && type != PrimitiveSet::DrawElementsUShortPrimitiveType
1138            && type != PrimitiveSet::DrawElementsUIntPrimitiveType)
1139            return;
1140        ps->accept(vr);
1141    }
1142    Remapper remapper(vr.remap);
1143    gatherer.accept(remapper);
1144    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
1145             end = primSets.end();
1146         itr != end;
1147         ++itr)
1148    {
1149        PrimitiveSet* ps = itr->get();
1150        switch (ps->getType())
1151        {
1152        case PrimitiveSet::DrawElementsUBytePrimitiveType:
1153            reorderDrawElements(*static_cast<DrawElementsUByte*>(ps), vr.remap);
1154            break;
1155        case PrimitiveSet::DrawElementsUShortPrimitiveType:
1156            reorderDrawElements(*static_cast<DrawElementsUShort*>(ps), vr.remap);
1157            break;
1158        case PrimitiveSet::DrawElementsUIntPrimitiveType:
1159            reorderDrawElements(*static_cast<DrawElementsUInt*>(ps), vr.remap);
1160            break;
1161        default:
1162            break;
1163        }
1164    }
1165    geom.dirtyDisplayList();
1166}
1167}
Note: See TracBrowser for help on using the browser.