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

Revision 13041, 169.0 kB (checked in by robert, 3 years 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 <stdlib.h>
14#include <string.h>
15
16#include <osgUtil/Optimizer>
17
18#include <osg/ApplicationUsage>
19#include <osg/Transform>
20#include <osg/MatrixTransform>
21#include <osg/PositionAttitudeTransform>
22#include <osg/LOD>
23#include <osg/Billboard>
24#include <osg/CameraView>
25#include <osg/Geometry>
26#include <osg/Notify>
27#include <osg/OccluderNode>
28#include <osg/Sequence>
29#include <osg/Switch>
30#include <osg/Texture>
31#include <osg/PagedLOD>
32#include <osg/ProxyNode>
33#include <osg/ImageStream>
34#include <osg/Timer>
35#include <osg/TexMat>
36#include <osg/io_utils>
37
38#include <osgUtil/TransformAttributeFunctor>
39#include <osgUtil/TriStripVisitor>
40#include <osgUtil/Tessellator>
41#include <osgUtil/Statistics>
42#include <osgUtil/MeshOptimizers>
43
44#include <typeinfo>
45#include <algorithm>
46#include <numeric>
47#include <sstream>
48
49#include <iterator>
50
51using namespace osgUtil;
52
53
54void Optimizer::reset()
55{
56}
57
58static osg::ApplicationUsageProxy Optimizer_e0(osg::ApplicationUsage::ENVIRONMENTAL_VARIABLE,"OSG_OPTIMIZER \"<type> [<type>]\"","OFF | DEFAULT | FLATTEN_STATIC_TRANSFORMS | FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS | REMOVE_REDUNDANT_NODES | COMBINE_ADJACENT_LODS | SHARE_DUPLICATE_STATE | MERGE_GEOMETRY | MERGE_GEODES | SPATIALIZE_GROUPS  | COPY_SHARED_NODES  | TRISTRIP_GEOMETRY | OPTIMIZE_TEXTURE_SETTINGS | REMOVE_LOADED_PROXY_NODES | TESSELLATE_GEOMETRY | CHECK_GEOMETRY |  FLATTEN_BILLBOARDS | TEXTURE_ATLAS_BUILDER | STATIC_OBJECT_DETECTION | INDEX_MESH | VERTEX_POSTTRANSFORM | VERTEX_PRETRANSFORM");
59
60void Optimizer::optimize(osg::Node* node)
61{
62    unsigned int options = 0;
63
64
65    const char* env = getenv("OSG_OPTIMIZER");
66    if (env)
67    {
68        std::string str(env);
69
70        if(str.find("OFF")!=std::string::npos) options = 0;
71
72        if(str.find("~DEFAULT")!=std::string::npos) options ^= DEFAULT_OPTIMIZATIONS;
73        else if(str.find("DEFAULT")!=std::string::npos) options |= DEFAULT_OPTIMIZATIONS;
74
75        if(str.find("~FLATTEN_STATIC_TRANSFORMS")!=std::string::npos) options ^= FLATTEN_STATIC_TRANSFORMS;
76        else if(str.find("FLATTEN_STATIC_TRANSFORMS")!=std::string::npos) options |= FLATTEN_STATIC_TRANSFORMS;
77
78        if(str.find("~FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS")!=std::string::npos) options ^= FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS;
79        else if(str.find("FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS")!=std::string::npos) options |= FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS;
80
81        if(str.find("~REMOVE_REDUNDANT_NODES")!=std::string::npos) options ^= REMOVE_REDUNDANT_NODES;
82        else if(str.find("REMOVE_REDUNDANT_NODES")!=std::string::npos) options |= REMOVE_REDUNDANT_NODES;
83
84        if(str.find("~REMOVE_LOADED_PROXY_NODES")!=std::string::npos) options ^= REMOVE_LOADED_PROXY_NODES;
85        else if(str.find("REMOVE_LOADED_PROXY_NODES")!=std::string::npos) options |= REMOVE_LOADED_PROXY_NODES;
86
87        if(str.find("~COMBINE_ADJACENT_LODS")!=std::string::npos) options ^= COMBINE_ADJACENT_LODS;
88        else if(str.find("COMBINE_ADJACENT_LODS")!=std::string::npos) options |= COMBINE_ADJACENT_LODS;
89
90        if(str.find("~SHARE_DUPLICATE_STATE")!=std::string::npos) options ^= SHARE_DUPLICATE_STATE;
91        else if(str.find("SHARE_DUPLICATE_STATE")!=std::string::npos) options |= SHARE_DUPLICATE_STATE;
92
93        if(str.find("~MERGE_GEODES")!=std::string::npos) options ^= MERGE_GEODES;
94        else if(str.find("MERGE_GEODES")!=std::string::npos) options |= MERGE_GEODES;
95
96        if(str.find("~MERGE_GEOMETRY")!=std::string::npos) options ^= MERGE_GEOMETRY;
97        else if(str.find("MERGE_GEOMETRY")!=std::string::npos) options |= MERGE_GEOMETRY;
98
99        if(str.find("~SPATIALIZE_GROUPS")!=std::string::npos) options ^= SPATIALIZE_GROUPS;
100        else if(str.find("SPATIALIZE_GROUPS")!=std::string::npos) options |= SPATIALIZE_GROUPS;
101
102        if(str.find("~COPY_SHARED_NODES")!=std::string::npos) options ^= COPY_SHARED_NODES;
103        else if(str.find("COPY_SHARED_NODES")!=std::string::npos) options |= COPY_SHARED_NODES;
104
105        if(str.find("~TESSELLATE_GEOMETRY")!=std::string::npos) options ^= TESSELLATE_GEOMETRY;
106        else if(str.find("TESSELLATE_GEOMETRY")!=std::string::npos) options |= TESSELLATE_GEOMETRY;
107
108        if(str.find("~TRISTRIP_GEOMETRY")!=std::string::npos) options ^= TRISTRIP_GEOMETRY;
109        else if(str.find("TRISTRIP_GEOMETRY")!=std::string::npos) options |= TRISTRIP_GEOMETRY;
110
111        if(str.find("~OPTIMIZE_TEXTURE_SETTINGS")!=std::string::npos) options ^= OPTIMIZE_TEXTURE_SETTINGS;
112        else if(str.find("OPTIMIZE_TEXTURE_SETTINGS")!=std::string::npos) options |= OPTIMIZE_TEXTURE_SETTINGS;
113
114        if(str.find("~CHECK_GEOMETRY")!=std::string::npos) options ^= CHECK_GEOMETRY;
115        else if(str.find("CHECK_GEOMETRY")!=std::string::npos) options |= CHECK_GEOMETRY;
116
117        if(str.find("~MAKE_FAST_GEOMETRY")!=std::string::npos) options ^= MAKE_FAST_GEOMETRY;
118        else if(str.find("MAKE_FAST_GEOMETRY")!=std::string::npos) options |= MAKE_FAST_GEOMETRY;
119
120        if(str.find("~FLATTEN_BILLBOARDS")!=std::string::npos) options ^= FLATTEN_BILLBOARDS;
121        else if(str.find("FLATTEN_BILLBOARDS")!=std::string::npos) options |= FLATTEN_BILLBOARDS;
122
123        if(str.find("~TEXTURE_ATLAS_BUILDER")!=std::string::npos) options ^= TEXTURE_ATLAS_BUILDER;
124        else if(str.find("TEXTURE_ATLAS_BUILDER")!=std::string::npos) options |= TEXTURE_ATLAS_BUILDER;
125
126        if(str.find("~STATIC_OBJECT_DETECTION")!=std::string::npos) options ^= STATIC_OBJECT_DETECTION;
127        else if(str.find("STATIC_OBJECT_DETECTION")!=std::string::npos) options |= STATIC_OBJECT_DETECTION;
128
129        if(str.find("~INDEX_MESH")!=std::string::npos) options ^= INDEX_MESH;
130        else if(str.find("INDEX_MESH")!=std::string::npos) options |= INDEX_MESH;
131
132        if(str.find("~VERTEX_POSTTRANSFORM")!=std::string::npos) options ^= VERTEX_POSTTRANSFORM;
133        else if(str.find("VERTEX_POSTTRANSFORM")!=std::string::npos) options |= VERTEX_POSTTRANSFORM;
134
135        if(str.find("~VERTEX_PRETRANSFORM")!=std::string::npos) options ^= VERTEX_PRETRANSFORM;
136        else if(str.find("VERTEX_PRETRANSFORM")!=std::string::npos) options |= VERTEX_PRETRANSFORM;
137
138    }
139    else
140    {
141        options = DEFAULT_OPTIMIZATIONS;
142    }
143
144    optimize(node,options);
145
146}
147
148void Optimizer::optimize(osg::Node* node, unsigned int options)
149{
150    StatsVisitor stats;
151
152    if (osg::getNotifyLevel()>=osg::INFO)
153    {
154        node->accept(stats);
155        stats.totalUpStats();
156        OSG_NOTICE<<std::endl<<"Stats before:"<<std::endl;
157        stats.print(osg::notify(osg::NOTICE));
158    }
159
160    if (options & STATIC_OBJECT_DETECTION)
161    {
162        StaticObjectDetectionVisitor sodv;
163        node->accept(sodv);
164    }
165
166    if (options & TESSELLATE_GEOMETRY)
167    {
168        OSG_INFO<<"Optimizer::optimize() doing TESSELLATE_GEOMETRY"<<std::endl;
169
170        TessellateVisitor tsv;
171        node->accept(tsv);
172    }
173
174    if (options & REMOVE_LOADED_PROXY_NODES)
175    {
176        OSG_INFO<<"Optimizer::optimize() doing REMOVE_LOADED_PROXY_NODES"<<std::endl;
177
178        RemoveLoadedProxyNodesVisitor rlpnv(this);
179        node->accept(rlpnv);
180        rlpnv.removeRedundantNodes();
181
182    }
183
184    if (options & COMBINE_ADJACENT_LODS)
185    {
186        OSG_INFO<<"Optimizer::optimize() doing COMBINE_ADJACENT_LODS"<<std::endl;
187
188        CombineLODsVisitor clv(this);
189        node->accept(clv);
190        clv.combineLODs();
191    }
192
193    if (options & OPTIMIZE_TEXTURE_SETTINGS)
194    {
195        OSG_INFO<<"Optimizer::optimize() doing OPTIMIZE_TEXTURE_SETTINGS"<<std::endl;
196
197        TextureVisitor tv(true,true, // unref image
198                          false,false, // client storage
199                          false,1.0, // anisotropic filtering
200                          this );
201        node->accept(tv);
202    }
203
204    if (options & SHARE_DUPLICATE_STATE)
205    {
206        OSG_INFO<<"Optimizer::optimize() doing SHARE_DUPLICATE_STATE"<<std::endl;
207
208        bool combineDynamicState = false;
209        bool combineStaticState = true;
210        bool combineUnspecifiedState = true;
211
212        StateVisitor osv(combineDynamicState, combineStaticState, combineUnspecifiedState, this);
213        node->accept(osv);
214        osv.optimize();
215    }
216
217    if (options & TEXTURE_ATLAS_BUILDER)
218    {
219        OSG_INFO<<"Optimizer::optimize() doing TEXTURE_ATLAS_BUILDER"<<std::endl;
220
221        // traverse the scene collecting textures into texture atlas.
222        TextureAtlasVisitor tav(this);
223        node->accept(tav);
224        tav.optimize();
225
226        // now merge duplicate state, that may have been introduced by merge textures into texture atlas'
227        bool combineDynamicState = false;
228        bool combineStaticState = true;
229        bool combineUnspecifiedState = true;
230
231        StateVisitor osv(combineDynamicState, combineStaticState, combineUnspecifiedState, this);
232        node->accept(osv);
233        osv.optimize();
234    }
235
236    if (options & COPY_SHARED_NODES)
237    {
238        OSG_INFO<<"Optimizer::optimize() doing COPY_SHARED_NODES"<<std::endl;
239
240        CopySharedSubgraphsVisitor cssv(this);
241        node->accept(cssv);
242        cssv.copySharedNodes();
243    }
244
245    if (options & FLATTEN_STATIC_TRANSFORMS)
246    {
247        OSG_INFO<<"Optimizer::optimize() doing FLATTEN_STATIC_TRANSFORMS"<<std::endl;
248
249        int i=0;
250        bool result = false;
251        do
252        {
253            OSG_DEBUG << "** RemoveStaticTransformsVisitor *** Pass "<<i<<std::endl;
254            FlattenStaticTransformsVisitor fstv(this);
255            node->accept(fstv);
256            result = fstv.removeTransforms(node);
257            ++i;
258        } while (result);
259
260        // no combine any adjacent static transforms.
261        CombineStaticTransformsVisitor cstv(this);
262        node->accept(cstv);
263        cstv.removeTransforms(node);
264    }
265
266    if (options & FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS)
267    {
268        OSG_INFO<<"Optimizer::optimize() doing FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS"<<std::endl;
269
270        // no combine any adjacent static transforms.
271        FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor fstdssv(this);
272        node->accept(fstdssv);
273
274    }
275
276    if (options & MERGE_GEODES)
277    {
278        OSG_INFO<<"Optimizer::optimize() doing MERGE_GEODES"<<std::endl;
279
280        osg::Timer_t startTick = osg::Timer::instance()->tick();
281
282        MergeGeodesVisitor visitor;
283        node->accept(visitor);
284
285        osg::Timer_t endTick = osg::Timer::instance()->tick();
286
287        OSG_INFO<<"MERGE_GEODES took "<<osg::Timer::instance()->delta_s(startTick,endTick)<<std::endl;
288    }
289
290    if (options & CHECK_GEOMETRY)
291    {
292        OSG_INFO<<"Optimizer::optimize() doing CHECK_GEOMETRY"<<std::endl;
293
294        CheckGeometryVisitor mgv(this);
295        node->accept(mgv);
296    }
297
298    if (options & MAKE_FAST_GEOMETRY)
299    {
300        OSG_INFO<<"Optimizer::optimize() doing MAKE_FAST_GEOMETRY"<<std::endl;
301
302        MakeFastGeometryVisitor mgv(this);
303        node->accept(mgv);
304    }
305
306    if (options & MERGE_GEOMETRY)
307    {
308        OSG_INFO<<"Optimizer::optimize() doing MERGE_GEOMETRY"<<std::endl;
309
310        osg::Timer_t startTick = osg::Timer::instance()->tick();
311
312        MergeGeometryVisitor mgv(this);
313        mgv.setTargetMaximumNumberOfVertices(10000);
314        node->accept(mgv);
315
316        osg::Timer_t endTick = osg::Timer::instance()->tick();
317
318        OSG_INFO<<"MERGE_GEOMETRY took "<<osg::Timer::instance()->delta_s(startTick,endTick)<<std::endl;
319    }
320
321    if (options & TRISTRIP_GEOMETRY)
322    {
323        OSG_INFO<<"Optimizer::optimize() doing TRISTRIP_GEOMETRY"<<std::endl;
324
325        TriStripVisitor tsv(this);
326        node->accept(tsv);
327        tsv.stripify();
328    }
329
330    if (options & REMOVE_REDUNDANT_NODES)
331    {
332        OSG_INFO<<"Optimizer::optimize() doing REMOVE_REDUNDANT_NODES"<<std::endl;
333
334        RemoveEmptyNodesVisitor renv(this);
335        node->accept(renv);
336        renv.removeEmptyNodes();
337
338        RemoveRedundantNodesVisitor rrnv(this);
339        node->accept(rrnv);
340        rrnv.removeRedundantNodes();
341
342    }
343
344    if (options & FLATTEN_BILLBOARDS)
345    {
346        FlattenBillboardVisitor fbv(this);
347        node->accept(fbv);
348        fbv.process();
349    }
350
351    if (options & SPATIALIZE_GROUPS)
352    {
353        OSG_INFO<<"Optimizer::optimize() doing SPATIALIZE_GROUPS"<<std::endl;
354
355        SpatializeGroupsVisitor sv(this);
356        node->accept(sv);
357        sv.divide();
358    }
359
360    if (options & INDEX_MESH)
361    {
362        OSG_INFO<<"Optimizer::optimize() doing INDEX_MESH"<<std::endl;
363        IndexMeshVisitor imv(this);
364        node->accept(imv);
365        imv.makeMesh();
366    }
367
368    if (options & VERTEX_POSTTRANSFORM)
369    {
370        OSG_INFO<<"Optimizer::optimize() doing VERTEX_POSTTRANSFORM"<<std::endl;
371        VertexCacheVisitor vcv;
372        node->accept(vcv);
373        vcv.optimizeVertices();
374    }
375
376    if (options & VERTEX_PRETRANSFORM)
377    {
378        OSG_INFO<<"Optimizer::optimize() doing VERTEX_PRETRANSFORM"<<std::endl;
379        VertexAccessOrderVisitor vaov;
380        node->accept(vaov);
381        vaov.optimizeOrder();
382    }
383
384    if (osg::getNotifyLevel()>=osg::INFO)
385    {
386        stats.reset();
387        node->accept(stats);
388        stats.totalUpStats();
389        OSG_NOTICE<<std::endl<<"Stats after:"<<std::endl;
390        stats.print(osg::notify(osg::NOTICE));
391    }
392}
393
394
395////////////////////////////////////////////////////////////////////////////
396// Tessellate geometry - eg break complex POLYGONS into triangles, strips, fans..
397////////////////////////////////////////////////////////////////////////////
398void Optimizer::TessellateVisitor::apply(osg::Geode& geode)
399{
400    for(unsigned int i=0;i<geode.getNumDrawables();++i)
401    {
402        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
403        if (geom) {
404            osgUtil::Tessellator Tessellator;
405            Tessellator.retessellatePolygons(*geom);
406        }
407    }
408    traverse(geode);
409}
410
411
412////////////////////////////////////////////////////////////////////////////
413// Optimize State Visitor
414////////////////////////////////////////////////////////////////////////////
415
416template<typename T>
417struct LessDerefFunctor
418{
419    bool operator () (const T* lhs,const T* rhs) const
420    {
421        return (*lhs<*rhs);
422    }
423};
424
425struct LessStateSetFunctor
426{
427    bool operator () (const osg::StateSet* lhs,const osg::StateSet* rhs) const
428    {
429        return (*lhs<*rhs);
430    }
431};
432
433
434
435void Optimizer::StateVisitor::reset()
436{
437    _statesets.clear();
438}
439
440void Optimizer::StateVisitor::addStateSet(osg::StateSet* stateset,osg::Object* obj)
441{
442    _statesets[stateset].insert(obj);
443}
444
445void Optimizer::StateVisitor::apply(osg::Node& node)
446{
447
448    osg::StateSet* ss = node.getStateSet();
449    if (ss && ss->getDataVariance()==osg::Object::STATIC)
450    {
451        if (isOperationPermissibleForObject(&node) &&
452            isOperationPermissibleForObject(ss))
453        {
454            addStateSet(ss,&node);
455        }
456    }
457
458    traverse(node);
459}
460
461void Optimizer::StateVisitor::apply(osg::Geode& geode)
462{
463    if (!isOperationPermissibleForObject(&geode)) return;
464
465    osg::StateSet* ss = geode.getStateSet();
466
467
468    if (ss && ss->getDataVariance()==osg::Object::STATIC)
469    {
470        if (isOperationPermissibleForObject(ss))
471        {
472            addStateSet(ss,&geode);
473        }
474    }
475    for(unsigned int i=0;i<geode.getNumDrawables();++i)
476    {
477        osg::Drawable* drawable = geode.getDrawable(i);
478        if (drawable)
479        {
480            ss = drawable->getStateSet();
481            if (ss && ss->getDataVariance()==osg::Object::STATIC)
482            {
483                if (isOperationPermissibleForObject(drawable) &&
484                    isOperationPermissibleForObject(ss))
485                {
486                    addStateSet(ss,drawable);
487                }
488            }
489        }
490    }
491}
492
493void Optimizer::StateVisitor::optimize()
494{
495    OSG_INFO << "Num of StateSet="<<_statesets.size()<< std::endl;
496
497    {
498        // create map from state attributes to stateset which contain them.
499        typedef std::pair<osg::StateSet*,unsigned int>      StateSetUnitPair;
500        typedef std::set<StateSetUnitPair>                  StateSetList;
501        typedef std::map<osg::StateAttribute*,StateSetList> AttributeToStateSetMap;
502        AttributeToStateSetMap attributeToStateSetMap;
503
504        // create map from uniforms to stateset when contain them.
505        typedef std::set<osg::StateSet*>                    StateSetSet;
506        typedef std::map<osg::Uniform*,StateSetSet>         UniformToStateSetMap;
507
508        const unsigned int NON_TEXTURE_ATTRIBUTE = 0xffffffff;
509
510        UniformToStateSetMap  uniformToStateSetMap;
511
512        // NOTE - TODO will need to track state attribute override value too.
513
514        for(StateSetMap::iterator sitr=_statesets.begin();
515            sitr!=_statesets.end();
516            ++sitr)
517        {
518            osg::StateSet::AttributeList& attributes = sitr->first->getAttributeList();
519            for(osg::StateSet::AttributeList::iterator aitr= attributes.begin();
520                aitr!=attributes.end();
521                ++aitr)
522            {
523                if (optimize(aitr->second.first->getDataVariance()))
524                {
525                    attributeToStateSetMap[aitr->second.first.get()].insert(StateSetUnitPair(sitr->first,NON_TEXTURE_ATTRIBUTE));
526                }
527            }
528
529
530            osg::StateSet::TextureAttributeList& texAttributes = sitr->first->getTextureAttributeList();
531            for(unsigned int unit=0;unit<texAttributes.size();++unit)
532            {
533                osg::StateSet::AttributeList& attributes = texAttributes[unit];
534                for(osg::StateSet::AttributeList::iterator aitr= attributes.begin();
535                    aitr!=attributes.end();
536                    ++aitr)
537                {
538                    if (optimize(aitr->second.first->getDataVariance()))
539                    {
540                        attributeToStateSetMap[aitr->second.first.get()].insert(StateSetUnitPair(sitr->first,unit));
541                    }
542                }
543            }
544
545
546            osg::StateSet::UniformList& uniforms = sitr->first->getUniformList();
547            for(osg::StateSet::UniformList::iterator uitr= uniforms.begin();
548                uitr!=uniforms.end();
549                ++uitr)
550            {
551                if (optimize(uitr->second.first->getDataVariance()))
552                {
553                    uniformToStateSetMap[uitr->second.first.get()].insert(sitr->first);
554                }
555            }
556
557        }
558
559        if (attributeToStateSetMap.size()>=2)
560        {
561            // create unique set of state attribute pointers.
562            typedef std::vector<osg::StateAttribute*> AttributeList;
563            AttributeList attributeList;
564
565            for(AttributeToStateSetMap::iterator aitr=attributeToStateSetMap.begin();
566                aitr!=attributeToStateSetMap.end();
567                ++aitr)
568            {
569                attributeList.push_back(aitr->first);
570            }
571
572            // sort the attributes so that equal attributes sit along side each
573            // other.
574            std::sort(attributeList.begin(),attributeList.end(),LessDerefFunctor<osg::StateAttribute>());
575
576            OSG_INFO << "state attribute list"<< std::endl;
577            for(AttributeList::iterator aaitr = attributeList.begin();
578                aaitr!=attributeList.end();
579                ++aaitr)
580            {
581                OSG_INFO << "    "<<*aaitr << "  "<<(*aaitr)->className()<< std::endl;
582            }
583
584            OSG_INFO << "searching for duplicate attributes"<< std::endl;
585            // find the duplicates.
586            AttributeList::iterator first_unique = attributeList.begin();
587            AttributeList::iterator current = first_unique;
588            ++current;
589            for(; current!=attributeList.end();++current)
590            {
591                if (**current==**first_unique)
592                {
593                    OSG_INFO << "    found duplicate "<<(*current)->className()<<"  first="<<*first_unique<<"  current="<<*current<< std::endl;
594                    StateSetList& statesetlist = attributeToStateSetMap[*current];
595                    for(StateSetList::iterator sitr=statesetlist.begin();
596                        sitr!=statesetlist.end();
597                        ++sitr)
598                    {
599                        OSG_INFO << "       replace duplicate "<<*current<<" with "<<*first_unique<< std::endl;
600                        osg::StateSet* stateset = sitr->first;
601                        unsigned int unit = sitr->second;
602                        if (unit==NON_TEXTURE_ATTRIBUTE) stateset->setAttribute(*first_unique);
603                        else stateset->setTextureAttribute(unit,*first_unique);
604                    }
605                }
606                else first_unique = current;
607            }
608        }
609
610
611        if (uniformToStateSetMap.size()>=2)
612        {
613            // create unique set of uniform pointers.
614            typedef std::vector<osg::Uniform*> UniformList;
615            UniformList uniformList;
616
617            for(UniformToStateSetMap::iterator aitr=uniformToStateSetMap.begin();
618                aitr!=uniformToStateSetMap.end();
619                ++aitr)
620            {
621                uniformList.push_back(aitr->first);
622            }
623
624            // sort the uniforms so that equal uniforms sit along side each
625            // other.
626            std::sort(uniformList.begin(),uniformList.end(),LessDerefFunctor<osg::Uniform>());
627
628            OSG_INFO << "state uniform list"<< std::endl;
629            for(UniformList::iterator uuitr = uniformList.begin();
630                uuitr!=uniformList.end();
631                ++uuitr)
632            {
633                OSG_INFO << "    "<<*uuitr << "  "<<(*uuitr)->getName()<< std::endl;
634            }
635
636            OSG_INFO << "searching for duplicate uniforms"<< std::endl;
637            // find the duplicates.
638            UniformList::iterator first_unique_uniform = uniformList.begin();
639            UniformList::iterator current_uniform = first_unique_uniform;
640            ++current_uniform;
641            for(; current_uniform!=uniformList.end();++current_uniform)
642            {
643                if ((**current_uniform)==(**first_unique_uniform))
644                {
645                    OSG_INFO << "    found duplicate uniform "<<(*current_uniform)->getName()<<"  first_unique_uniform="<<*first_unique_uniform<<"  current_uniform="<<*current_uniform<< std::endl;
646                    StateSetSet& statesetset = uniformToStateSetMap[*current_uniform];
647                    for(StateSetSet::iterator sitr=statesetset.begin();
648                        sitr!=statesetset.end();
649                        ++sitr)
650                    {
651                        OSG_INFO << "       replace duplicate "<<*current_uniform<<" with "<<*first_unique_uniform<< std::endl;
652                        osg::StateSet* stateset = *sitr;
653                        stateset->addUniform(*first_unique_uniform);
654                    }
655                }
656                else first_unique_uniform = current_uniform;
657            }
658        }
659
660    }
661
662    // duplicate state attributes removed.
663    // now need to look at duplicate state sets.
664    if (_statesets.size()>=2)
665    {
666        // create the list of stateset's.
667        typedef std::vector<osg::StateSet*> StateSetSortList;
668        StateSetSortList statesetSortList;
669        for(StateSetMap::iterator ssitr=_statesets.begin();
670            ssitr!=_statesets.end();
671            ++ssitr)
672        {
673            statesetSortList.push_back(ssitr->first);
674        }
675
676
677        // sort the StateSet's so that equal StateSet's sit along side each
678        // other.
679        std::sort(statesetSortList.begin(),statesetSortList.end(),LessDerefFunctor<osg::StateSet>());
680
681        OSG_INFO << "searching for duplicate attributes"<< std::endl;
682        // find the duplicates.
683        StateSetSortList::iterator first_unique = statesetSortList.begin();
684        StateSetSortList::iterator current = first_unique; ++current;
685        for(; current!=statesetSortList.end();++current)
686        {
687            if (**current==**first_unique)
688            {
689                OSG_INFO << "    found duplicate "<<(*current)->className()<<"  first="<<*first_unique<<"  current="<<*current<< std::endl;
690                ObjectSet& objSet = _statesets[*current];
691                for(ObjectSet::iterator sitr=objSet.begin();
692                    sitr!=objSet.end();
693                    ++sitr)
694                {
695                    OSG_INFO << "       replace duplicate "<<*current<<" with "<<*first_unique<< std::endl;
696                    osg::Object* obj = *sitr;
697                    osg::Drawable* drawable = dynamic_cast<osg::Drawable*>(obj);
698                    if (drawable)
699                    {
700                        drawable->setStateSet(*first_unique);
701                    }
702                    else
703                    {
704                        osg::Node* node = dynamic_cast<osg::Node*>(obj);
705                        if (node)
706                        {
707                            node->setStateSet(*first_unique);
708                        }
709                    }
710                }
711            }
712            else first_unique = current;
713        }
714    }
715
716}
717
718////////////////////////////////////////////////////////////////////////////
719// Flatten static transforms
720////////////////////////////////////////////////////////////////////////////
721
722class CollectLowestTransformsVisitor : public BaseOptimizerVisitor
723{
724    public:
725
726
727        CollectLowestTransformsVisitor(Optimizer* optimizer=0):
728                    BaseOptimizerVisitor(optimizer,Optimizer::FLATTEN_STATIC_TRANSFORMS),
729                    _transformFunctor(osg::Matrix())
730        {
731            setTraversalMode(osg::NodeVisitor::TRAVERSE_PARENTS);
732        }
733
734        virtual void apply(osg::Node& node)
735        {
736            if (node.getNumParents())
737            {
738                traverse(node);
739            }
740            else
741            {
742                // for all current objects mark a NULL transform for them.
743                registerWithCurrentObjects(0);
744            }
745        }
746
747        virtual void apply(osg::LOD& lod)
748        {
749            _currentObjectList.push_back(&lod);
750
751            traverse(lod);
752
753            _currentObjectList.pop_back();
754        }
755
756        virtual void apply(osg::Transform& transform)
757        {
758            // for all current objects associated this transform with them.
759            registerWithCurrentObjects(&transform);
760        }
761
762        virtual void apply(osg::Geode& geode)
763        {
764            traverse(geode);
765        }
766
767        virtual void apply(osg::Billboard& geode)
768        {
769            traverse(geode);
770        }
771
772
773        void collectDataFor(osg::Node* node)
774        {
775            _currentObjectList.push_back(node);
776
777            node->accept(*this);
778
779            _currentObjectList.pop_back();
780        }
781
782        void collectDataFor(osg::Billboard* billboard)
783        {
784            _currentObjectList.push_back(billboard);
785
786            billboard->accept(*this);
787
788            _currentObjectList.pop_back();
789        }
790
791        void collectDataFor(osg::Drawable* drawable)
792        {
793            _currentObjectList.push_back(drawable);
794
795            const osg::Drawable::ParentList& parents = drawable->getParents();
796            for(osg::Drawable::ParentList::const_iterator itr=parents.begin();
797                itr!=parents.end();
798                ++itr)
799            {
800                (*itr)->accept(*this);
801            }
802
803            _currentObjectList.pop_back();
804        }
805
806        void setUpMaps();
807        void disableTransform(osg::Transform* transform);
808        bool removeTransforms(osg::Node* nodeWeCannotRemove);
809
810        inline bool isOperationPermissibleForObject(const osg::Object* object) const
811        {
812            const osg::Drawable* drawable = dynamic_cast<const osg::Drawable*>(object);
813            if (drawable) return isOperationPermissibleForObject(drawable);
814
815            const osg::Node* node = dynamic_cast<const osg::Node*>(object);
816            if (node) return isOperationPermissibleForObject(node);
817
818            return true;
819        }
820
821        inline bool isOperationPermissibleForObject(const osg::Drawable* drawable) const
822        {
823            // disable if cannot apply transform functor.
824            if (drawable && !drawable->supports(_transformFunctor)) return false;
825            return BaseOptimizerVisitor::isOperationPermissibleForObject(drawable);
826        }
827
828        inline bool isOperationPermissibleForObject(const osg::Node* node) const
829        {
830            // disable if object is a light point node.
831            if (strcmp(node->className(),"LightPointNode")==0) return false;
832            if (dynamic_cast<const osg::ProxyNode*>(node)) return false;
833            if (dynamic_cast<const osg::PagedLOD*>(node)) return false;
834            return BaseOptimizerVisitor::isOperationPermissibleForObject(node);
835        }
836
837    protected:
838
839        struct TransformStruct
840        {
841            typedef std::set<osg::Object*> ObjectSet;
842
843            TransformStruct():_canBeApplied(true) {}
844
845            void add(osg::Object* obj)
846            {
847                _objectSet.insert(obj);
848            }
849
850            bool        _canBeApplied;
851            ObjectSet   _objectSet;
852        };
853
854        struct ObjectStruct
855        {
856            typedef std::set<osg::Transform*> TransformSet;
857
858            ObjectStruct():_canBeApplied(true),_moreThanOneMatrixRequired(false) {}
859
860            void add(osg::Transform* transform)
861            {
862                if (transform)
863                {
864                    if (transform->getDataVariance()!=osg::Transform::STATIC) _moreThanOneMatrixRequired=true;
865                    else if (transform->getReferenceFrame()!=osg::Transform::RELATIVE_RF) _moreThanOneMatrixRequired=true;
866                    else
867                    {
868                        if (_transformSet.empty()) transform->computeLocalToWorldMatrix(_firstMatrix,0);
869                        else
870                        {
871                            osg::Matrix matrix;
872                            transform->computeLocalToWorldMatrix(matrix,0);
873                            if (_firstMatrix!=matrix) _moreThanOneMatrixRequired=true;
874                        }
875                    }
876                }
877                else
878                {
879                    if (!_transformSet.empty())
880                    {
881                        if (!_firstMatrix.isIdentity()) _moreThanOneMatrixRequired=true;
882                    }
883
884                }
885                _transformSet.insert(transform);
886            }
887
888            bool            _canBeApplied;
889            bool            _moreThanOneMatrixRequired;
890            osg::Matrix     _firstMatrix;
891            TransformSet    _transformSet;
892        };
893
894
895        void registerWithCurrentObjects(osg::Transform* transform)
896        {
897            for(ObjectList::iterator itr=_currentObjectList.begin();
898                itr!=_currentObjectList.end();
899                ++itr)
900            {
901                _objectMap[*itr].add(transform);
902            }
903        }
904
905        typedef std::map<osg::Transform*,TransformStruct>   TransformMap;
906        typedef std::map<osg::Object*,ObjectStruct>         ObjectMap;
907        typedef std::vector<osg::Object*>                   ObjectList;
908
909        void disableObject(osg::Object* object)
910        {
911            disableObject(_objectMap.find(object));
912        }
913
914        void disableObject(ObjectMap::iterator itr);
915        void doTransform(osg::Object* obj,osg::Matrix& matrix);
916
917        osgUtil::TransformAttributeFunctor _transformFunctor;
918        TransformMap    _transformMap;
919        ObjectMap       _objectMap;
920        ObjectList      _currentObjectList;
921
922};
923
924
925void CollectLowestTransformsVisitor::doTransform(osg::Object* obj,osg::Matrix& matrix)
926{
927    osg::Drawable* drawable = dynamic_cast<osg::Drawable*>(obj);
928    if (drawable)
929    {
930        osgUtil::TransformAttributeFunctor tf(matrix);
931        drawable->accept(tf);
932        drawable->dirtyBound();
933        drawable->dirtyDisplayList();
934
935        return;
936    }
937
938    osg::LOD* lod = dynamic_cast<osg::LOD*>(obj);
939    if (lod)
940    {
941        osg::Matrix matrix_no_trans = matrix;
942        matrix_no_trans.setTrans(0.0f,0.0f,0.0f);
943
944        osg::Vec3 v111(1.0f,1.0f,1.0f);
945        osg::Vec3 new_v111 = v111*matrix_no_trans;
946        float ratio = new_v111.length()/v111.length();
947
948        // move center point.
949        lod->setCenter(lod->getCenter()*matrix);
950
951        // adjust ranges to new scale.
952        for(unsigned int i=0;i<lod->getNumRanges();++i)
953        {
954            lod->setRange(i,lod->getMinRange(i)*ratio,lod->getMaxRange(i)*ratio);
955        }
956
957        lod->dirtyBound();
958        return;
959    }
960
961    osg::Billboard* billboard = dynamic_cast<osg::Billboard*>(obj);
962    if (billboard)
963    {
964        osg::Matrix matrix_no_trans = matrix;
965        matrix_no_trans.setTrans(0.0f,0.0f,0.0f);
966
967        osgUtil::TransformAttributeFunctor tf(matrix_no_trans);
968
969        osg::Vec3 axis = osg::Matrix::transform3x3(tf._im,billboard->getAxis());
970        axis.normalize();
971        billboard->setAxis(axis);
972
973        osg::Vec3 normal = osg::Matrix::transform3x3(tf._im,billboard->getNormal());
974        normal.normalize();
975        billboard->setNormal(normal);
976
977
978        for(unsigned int i=0;i<billboard->getNumDrawables();++i)
979        {
980            billboard->setPosition(i,billboard->getPosition(i)*matrix);
981            billboard->getDrawable(i)->accept(tf);
982            billboard->getDrawable(i)->dirtyBound();
983        }
984
985        billboard->dirtyBound();
986
987        return;
988    }
989}
990
991void CollectLowestTransformsVisitor::disableObject(ObjectMap::iterator itr)
992{
993    if (itr==_objectMap.end())
994    {
995        return;
996    }
997
998    if (itr->second._canBeApplied)
999    {
1000        // we havn't been disabled yet so we need to disable,
1001        itr->second._canBeApplied = false;
1002
1003        // and then inform everybody we have been disabled.
1004        for(ObjectStruct::TransformSet::iterator titr = itr->second._transformSet.begin();
1005            titr != itr->second._transformSet.end();
1006            ++titr)
1007        {
1008            disableTransform(*titr);
1009        }
1010    }
1011}
1012
1013void CollectLowestTransformsVisitor::disableTransform(osg::Transform* transform)
1014{
1015    TransformMap::iterator itr=_transformMap.find(transform);
1016    if (itr==_transformMap.end())
1017    {
1018        return;
1019    }
1020
1021    if (itr->second._canBeApplied)
1022    {
1023
1024        // we havn't been disabled yet so we need to disable,
1025        itr->second._canBeApplied = false;
1026        // and then inform everybody we have been disabled.
1027        for(TransformStruct::ObjectSet::iterator oitr = itr->second._objectSet.begin();
1028            oitr != itr->second._objectSet.end();
1029            ++oitr)
1030        {
1031            disableObject(*oitr);
1032        }
1033    }
1034}
1035
1036void CollectLowestTransformsVisitor::setUpMaps()
1037{
1038    // create the TransformMap from the ObjectMap
1039    ObjectMap::iterator oitr;
1040    for(oitr=_objectMap.begin();
1041        oitr!=_objectMap.end();
1042        ++oitr)
1043    {
1044        osg::Object* object = oitr->first;
1045        ObjectStruct& os = oitr->second;
1046
1047        for(ObjectStruct::TransformSet::iterator titr = os._transformSet.begin();
1048            titr != os._transformSet.end();
1049            ++titr)
1050        {
1051            _transformMap[*titr].add(object);
1052        }
1053    }
1054
1055    // disable all the objects which have more than one matrix associated
1056    // with them, and then disable all transforms which have an object associated
1057    // them that can't be applied, and then disable all objects which have
1058    // disabled transforms associated, recursing until all disabled
1059    // associativity.
1060    // and disable all objects that the operation is not permisable for)
1061    for(oitr=_objectMap.begin();
1062        oitr!=_objectMap.end();
1063        ++oitr)
1064    {
1065        osg::Object* object = oitr->first;
1066        ObjectStruct& os = oitr->second;
1067        if (os._canBeApplied)
1068        {
1069            if (os._moreThanOneMatrixRequired || !isOperationPermissibleForObject(object))
1070            {
1071                disableObject(oitr);
1072            }
1073        }
1074    }
1075
1076}
1077
1078bool CollectLowestTransformsVisitor::removeTransforms(osg::Node* nodeWeCannotRemove)
1079{
1080    // transform the objects that can be applied.
1081    for(ObjectMap::iterator oitr=_objectMap.begin();
1082        oitr!=_objectMap.end();
1083        ++oitr)
1084    {
1085        osg::Object* object = oitr->first;
1086        ObjectStruct& os = oitr->second;
1087        if (os._canBeApplied)
1088        {
1089            doTransform(object,os._firstMatrix);
1090        }
1091    }
1092
1093
1094    bool transformRemoved = false;
1095
1096    // clean up the transforms.
1097    for(TransformMap::iterator titr=_transformMap.begin();
1098        titr!=_transformMap.end();
1099        ++titr)
1100    {
1101        if (titr->second._canBeApplied)
1102        {
1103            if (titr->first!=nodeWeCannotRemove)
1104            {
1105                transformRemoved = true;
1106
1107                osg::ref_ptr<osg::Transform> transform = titr->first;
1108                osg::ref_ptr<osg::Group>     group = new osg::Group;
1109                group->setName( transform->getName() );
1110                group->setDataVariance(osg::Object::STATIC);
1111                group->setNodeMask(transform->getNodeMask());
1112                group->setStateSet(transform->getStateSet());
1113                group->setUserData(transform->getUserData());
1114                group->setDescriptions(transform->getDescriptions());
1115                for(unsigned int i=0;i<transform->getNumChildren();++i)
1116                {
1117                    group->addChild(transform->getChild(i));
1118                }
1119
1120                for(int i2=transform->getNumParents()-1;i2>=0;--i2)
1121                {
1122                    transform->getParent(i2)->replaceChild(transform.get(),group.get());
1123                }
1124            }
1125            else
1126            {
1127                osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(titr->first);
1128                if (mt) mt->setMatrix(osg::Matrix::identity());
1129                else
1130                {
1131                    osg::PositionAttitudeTransform* pat = dynamic_cast<osg::PositionAttitudeTransform*>(titr->first);
1132                    if (pat)
1133                    {
1134                        pat->setPosition(osg::Vec3(0.0f,0.0f,0.0f));
1135                        pat->setAttitude(osg::Quat());
1136                        pat->setPivotPoint(osg::Vec3(0.0f,0.0f,0.0f));
1137                    }
1138                    else
1139                    {
1140                        OSG_WARN<<"Warning:: during Optimize::CollectLowestTransformsVisitor::removeTransforms(Node*)"<<std::endl;
1141                        OSG_WARN<<"          unhandled of setting of indentity matrix on "<< titr->first->className()<<std::endl;
1142                        OSG_WARN<<"          model will appear in the incorrect position."<<std::endl;
1143                    }
1144                }
1145
1146            }
1147        }
1148    }
1149    _objectMap.clear();
1150    _transformMap.clear();
1151
1152    return transformRemoved;
1153}
1154
1155void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Node& node)
1156{
1157    if (strcmp(node.className(),"LightPointNode")==0)
1158    {
1159        _excludedNodeSet.insert(&node);
1160    }
1161    traverse(node);
1162}
1163
1164
1165void Optimizer::FlattenStaticTransformsVisitor::apply(osg::ProxyNode& node)
1166{
1167    _excludedNodeSet.insert(&node);
1168
1169    traverse(node);
1170}
1171
1172void Optimizer::FlattenStaticTransformsVisitor::apply(osg::PagedLOD& node)
1173{
1174    _excludedNodeSet.insert(&node);
1175
1176    traverse(node);
1177}
1178
1179
1180void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Geode& geode)
1181{
1182    if (!_transformStack.empty())
1183    {
1184        for(unsigned int i=0;i<geode.getNumDrawables();++i)
1185        {
1186            osg::Geometry *geometry = geode.getDrawable(i)->asGeometry();
1187            if((geometry) && (isOperationPermissibleForObject(&geode)) && (isOperationPermissibleForObject(geometry)))
1188            {
1189                if(geometry->getVertexArray() && geometry->getVertexArray()->referenceCount() > 1) {
1190                    geometry->setVertexArray(dynamic_cast<osg::Array*>(geometry->getVertexArray()->clone(osg::CopyOp::DEEP_COPY_ALL)));
1191                }
1192                if(geometry->getNormalArray() && geometry->getNormalArray()->referenceCount() > 1) {
1193                    geometry->setNormalArray(dynamic_cast<osg::Array*>(geometry->getNormalArray()->clone(osg::CopyOp::DEEP_COPY_ALL)));
1194                }
1195            }
1196            _drawableSet.insert(geode.getDrawable(i));
1197        }
1198    }
1199}
1200
1201void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Billboard& billboard)
1202{
1203    if (!_transformStack.empty())
1204    {
1205        _billboardSet.insert(&billboard);
1206    }
1207}
1208
1209void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Transform& transform)
1210{
1211    if (!_transformStack.empty())
1212    {
1213        // we need to disable any transform higher in the list.
1214        _transformSet.insert(_transformStack.back());
1215    }
1216
1217    _transformStack.push_back(&transform);
1218
1219    // simple traverse the children as if this Transform didn't exist.
1220    traverse(transform);
1221
1222    _transformStack.pop_back();
1223}
1224
1225bool Optimizer::FlattenStaticTransformsVisitor::removeTransforms(osg::Node* nodeWeCannotRemove)
1226{
1227    CollectLowestTransformsVisitor cltv(_optimizer);
1228
1229    for(NodeSet::iterator nitr=_excludedNodeSet.begin();
1230        nitr!=_excludedNodeSet.end();
1231        ++nitr)
1232    {
1233        cltv.collectDataFor(*nitr);
1234    }
1235
1236    for(DrawableSet::iterator ditr=_drawableSet.begin();
1237        ditr!=_drawableSet.end();
1238        ++ditr)
1239    {
1240        cltv.collectDataFor(*ditr);
1241    }
1242
1243    for(BillboardSet::iterator bitr=_billboardSet.begin();
1244        bitr!=_billboardSet.end();
1245        ++bitr)
1246    {
1247        cltv.collectDataFor(*bitr);
1248    }
1249
1250    cltv.setUpMaps();
1251
1252    for(TransformSet::iterator titr=_transformSet.begin();
1253        titr!=_transformSet.end();
1254        ++titr)
1255    {
1256        cltv.disableTransform(*titr);
1257    }
1258
1259
1260    return cltv.removeTransforms(nodeWeCannotRemove);
1261}
1262
1263////////////////////////////////////////////////////////////////////////////
1264// CombineStaticTransforms
1265////////////////////////////////////////////////////////////////////////////
1266
1267void Optimizer::CombineStaticTransformsVisitor::apply(osg::MatrixTransform& transform)
1268{
1269    if (transform.getDataVariance()==osg::Object::STATIC &&
1270        transform.getNumChildren()==1 &&
1271        transform.getChild(0)->asTransform()!=0 &&
1272        transform.getChild(0)->asTransform()->asMatrixTransform()!=0 &&
1273        transform.getChild(0)->asTransform()->getDataVariance()==osg::Object::STATIC &&
1274        isOperationPermissibleForObject(&transform) && isOperationPermissibleForObject(transform.getChild(0)))
1275    {
1276        _transformSet.insert(&transform);
1277    }
1278
1279    traverse(transform);
1280}
1281
1282bool Optimizer::CombineStaticTransformsVisitor::removeTransforms(osg::Node* nodeWeCannotRemove)
1283{
1284    if (nodeWeCannotRemove && nodeWeCannotRemove->asTransform()!=0 && nodeWeCannotRemove->asTransform()->asMatrixTransform()!=0)
1285    {
1286        // remove topmost node if it exists in the transform set.
1287        TransformSet::iterator itr = _transformSet.find(nodeWeCannotRemove->asTransform()->asMatrixTransform());
1288        if (itr!=_transformSet.end()) _transformSet.erase(itr);
1289    }
1290
1291    bool transformRemoved = false;
1292
1293    while (!_transformSet.empty())
1294    {
1295        // get the first available transform to combine.
1296        osg::ref_ptr<osg::MatrixTransform> transform = *_transformSet.begin();
1297        _transformSet.erase(_transformSet.begin());
1298
1299        if (transform->getNumChildren()==1 &&
1300            transform->getChild(0)->asTransform()!=0 &&
1301            transform->getChild(0)->asTransform()->asMatrixTransform()!=0 &&
1302            transform->getChild(0)->asTransform()->getDataVariance()==osg::Object::STATIC)
1303        {
1304            // now combine with its child.
1305            osg::MatrixTransform* child = transform->getChild(0)->asTransform()->asMatrixTransform();
1306
1307            osg::Matrix newMatrix = child->getMatrix()*transform->getMatrix();
1308            child->setMatrix(newMatrix);
1309            if (transform->getStateSet())
1310            {
1311                if(child->getStateSet()) child->getStateSet()->merge(*transform->getStateSet());
1312                else child->setStateSet(transform->getStateSet());
1313            }
1314
1315            transformRemoved = true;
1316
1317            osg::Node::ParentList parents = transform->getParents();
1318            for(osg::Node::ParentList::iterator pitr=parents.begin();
1319                pitr!=parents.end();
1320                ++pitr)
1321            {
1322                (*pitr)->replaceChild(transform.get(),child);
1323            }
1324
1325        }
1326
1327    }
1328    return transformRemoved;
1329}
1330
1331////////////////////////////////////////////////////////////////////////////
1332// RemoveEmptyNodes.
1333////////////////////////////////////////////////////////////////////////////
1334
1335void Optimizer::RemoveEmptyNodesVisitor::apply(osg::Geode& geode)
1336{
1337    for(int i=geode.getNumDrawables()-1;i>=0;--i)
1338    {
1339        osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1340        if (geom && geom->empty() && isOperationPermissibleForObject(geom))
1341        {
1342           geode.removeDrawables(i,1);
1343        }
1344    }
1345
1346    if (geode.getNumParents()>0)
1347    {
1348        if (geode.getNumDrawables()==0 && isOperationPermissibleForObject(&geode)) _redundantNodeList.insert(&geode);
1349    }
1350}
1351
1352void Optimizer::RemoveEmptyNodesVisitor::apply(osg::Group& group)
1353{
1354    if (group.getNumParents()>0)
1355    {
1356        // only remove empty groups, but not empty occluders.
1357        if (group.getNumChildren()==0 && isOperationPermissibleForObject(&group) &&
1358            (typeid(group)==typeid(osg::Group) || (dynamic_cast<osg::Transform*>(&group) && !dynamic_cast<osg::CameraView*>(&group))))
1359        {
1360            _redundantNodeList.insert(&group);
1361        }
1362    }
1363    traverse(group);
1364}
1365
1366void Optimizer::RemoveEmptyNodesVisitor::removeEmptyNodes()
1367{
1368
1369    NodeList newEmptyGroups;
1370
1371    // keep iterator through until scene graph is cleaned of empty nodes.
1372    while (!_redundantNodeList.empty())
1373    {
1374        for(NodeList::iterator itr=_redundantNodeList.begin();
1375            itr!=_redundantNodeList.end();
1376            ++itr)
1377        {
1378
1379            osg::ref_ptr<osg::Node> nodeToRemove = (*itr);
1380
1381            // take a copy of parents list since subsequent removes will modify the original one.
1382            osg::Node::ParentList parents = nodeToRemove->getParents();
1383
1384            for(osg::Node::ParentList::iterator pitr=parents.begin();
1385                pitr!=parents.end();
1386                ++pitr)
1387            {
1388                osg::Group* parent = *pitr;
1389                if (!dynamic_cast<osg::Sequence*>(parent) &&
1390                    !dynamic_cast<osg::Switch*>(parent) &&
1391                    strcmp(parent->className(),"MultiSwitch")!=0)
1392                {
1393                    parent->removeChild(nodeToRemove.get());
1394                    if (parent->getNumChildren()==0) newEmptyGroups.insert(*pitr);
1395                }
1396            }
1397        }
1398
1399        _redundantNodeList.clear();
1400        _redundantNodeList.swap(newEmptyGroups);
1401    }
1402}
1403
1404
1405////////////////////////////////////////////////////////////////////////////
1406// RemoveRedundantNodes.
1407////////////////////////////////////////////////////////////////////////////
1408
1409bool Optimizer::RemoveRedundantNodesVisitor::isOperationPermissible(osg::Node& node)
1410{
1411    return node.getNumParents()>0 &&
1412           !node.getStateSet() &&
1413           !node.getUserData() &&
1414           !node.getCullCallback() &&
1415           !node.getEventCallback() &&
1416           !node.getUpdateCallback() &&
1417           node.getDescriptions().empty() &&
1418           isOperationPermissibleForObject(&node);
1419}
1420
1421void Optimizer::RemoveRedundantNodesVisitor::apply(osg::Group& group)
1422{
1423    if (group.getNumChildren()==1 &&
1424        typeid(group)==typeid(osg::Group) &&
1425        isOperationPermissible(group))
1426    {
1427        _redundantNodeList.insert(&group);
1428    }
1429
1430    traverse(group);
1431}
1432
1433
1434
1435void Optimizer::RemoveRedundantNodesVisitor::apply(osg::Transform& transform)
1436{
1437    if (transform.getDataVariance()==osg::Object::STATIC &&
1438        isOperationPermissible(transform))
1439    {
1440        osg::Matrix matrix;
1441        transform.computeWorldToLocalMatrix(matrix,NULL);
1442        if (matrix.isIdentity())
1443        {
1444            _redundantNodeList.insert(&transform);
1445        }
1446    }
1447    traverse(transform);
1448}
1449
1450
1451void Optimizer::RemoveRedundantNodesVisitor::removeRedundantNodes()
1452{
1453
1454    for(NodeList::iterator itr=_redundantNodeList.begin();
1455        itr!=_redundantNodeList.end();
1456        ++itr)
1457    {
1458        osg::ref_ptr<osg::Group> group = dynamic_cast<osg::Group*>(*itr);
1459        if (group.valid())
1460        {
1461            // take a copy of parents list since subsequent removes will modify the original one.
1462            osg::Node::ParentList parents = group->getParents();
1463
1464            if (group->getNumChildren()==1)
1465            {
1466                osg::Node* child = group->getChild(0);
1467                for(osg::Node::ParentList::iterator pitr=parents.begin();
1468                    pitr!=parents.end();
1469                    ++pitr)
1470                {
1471                    (*pitr)->replaceChild(group.get(),child);
1472                }
1473
1474            }
1475
1476        }
1477        else
1478        {
1479            OSG_WARN<<"Optimizer::RemoveRedundantNodesVisitor::removeRedundantNodes() - failed dynamic_cast"<<std::endl;
1480        }
1481    }
1482    _redundantNodeList.clear();
1483}
1484
1485
1486////////////////////////////////////////////////////////////////////////////
1487// RemoveLoadedProxyNodesVisitor.
1488////////////////////////////////////////////////////////////////////////////
1489
1490void Optimizer::RemoveLoadedProxyNodesVisitor::apply(osg::ProxyNode& proxyNode)
1491{
1492    if (proxyNode.getNumParents()>0 && proxyNode.getNumFileNames()==proxyNode.getNumChildren())
1493    {
1494        if (isOperationPermissibleForObject(&proxyNode))
1495        {
1496            _redundantNodeList.insert(&proxyNode);
1497        }
1498    }
1499    traverse(proxyNode);
1500}
1501
1502void Optimizer::RemoveLoadedProxyNodesVisitor::removeRedundantNodes()
1503{
1504
1505    for(NodeList::iterator itr=_redundantNodeList.begin();
1506        itr!=_redundantNodeList.end();
1507        ++itr)
1508    {
1509        osg::ref_ptr<osg::Group> group = dynamic_cast<osg::Group*>(*itr);
1510        if (group.valid())
1511        {
1512
1513            // first check to see if data was attached to the ProxyNode that we need to keep.
1514            bool keepData = false;
1515            if (!group->getName().empty()) keepData = true;
1516            if (!group->getDescriptions().empty()) keepData = true;
1517            if (group->getNodeMask()) keepData = true;
1518            if (group->getUpdateCallback()) keepData = true;
1519            if (group->getEventCallback()) keepData = true;
1520            if (group->getCullCallback()) keepData = true;
1521
1522            if (keepData)
1523            {
1524                // create a group to store all proxy's children and data.
1525                osg::ref_ptr<osg::Group> newGroup = new osg::Group(*group,osg::CopyOp::SHALLOW_COPY);
1526
1527
1528                // take a copy of parents list since subsequent removes will modify the original one.
1529                osg::Node::ParentList parents = group->getParents();
1530
1531                for(osg::Node::ParentList::iterator pitr=parents.begin();
1532                    pitr!=parents.end();
1533                    ++pitr)
1534                {
1535                    (*pitr)->replaceChild(group.get(),newGroup.get());
1536                }
1537
1538            }
1539            else
1540            {
1541                // take a copy of parents list since subsequent removes will modify the original one.
1542                osg::Node::ParentList parents = group->getParents();
1543
1544                for(osg::Node::ParentList::iterator pitr=parents.begin();
1545                    pitr!=parents.end();
1546                    ++pitr)
1547                {
1548                    (*pitr)->removeChild(group.get());
1549                    for(unsigned int i=0;i<group->getNumChildren();++i)
1550                    {
1551                        osg::Node* child = group->getChild(i);
1552                        (*pitr)->addChild(child);
1553                    }
1554
1555                }
1556            }
1557        }
1558        else
1559        {
1560            OSG_WARN<<"Optimizer::RemoveLoadedProxyNodesVisitor::removeRedundantNodes() - failed dynamic_cast"<<std::endl;
1561        }
1562    }
1563    _redundantNodeList.clear();
1564}
1565
1566
1567
1568////////////////////////////////////////////////////////////////////////////
1569// combine LOD's.
1570////////////////////////////////////////////////////////////////////////////
1571void Optimizer::CombineLODsVisitor::apply(osg::LOD& lod)
1572{
1573    if (dynamic_cast<osg::PagedLOD*>(&lod)==0)
1574    {
1575        for(unsigned int i=0;i<lod.getNumParents();++i)
1576        {
1577            if (typeid(*lod.getParent(i))==typeid(osg::Group))
1578            {
1579                if (isOperationPermissibleForObject(&lod))
1580                {
1581                    _groupList.insert(lod.getParent(i));
1582                }
1583            }
1584        }
1585    }
1586    traverse(lod);
1587}
1588
1589
1590void Optimizer::CombineLODsVisitor::combineLODs()
1591{
1592    for(GroupList::iterator itr=_groupList.begin();
1593        itr!=_groupList.end();
1594        ++itr)
1595    {
1596        osg::Group* group = *itr;
1597
1598        typedef std::set<osg::LOD*>  LODSet;
1599
1600        LODSet    lodChildren;
1601
1602        for(unsigned int i=0;i<group->getNumChildren();++i)
1603        {
1604            osg::Node* child = group->getChild(i);
1605            osg::LOD* lod = dynamic_cast<osg::LOD*>(child);
1606            if (lod)
1607            {
1608                lodChildren.insert(lod);
1609            }
1610        }
1611
1612        if (lodChildren.size()>=2)
1613        {
1614            osg::BoundingBox bb;
1615            LODSet::iterator lod_itr;
1616            float smallestRadius=FLT_MAX;
1617            for(lod_itr=lodChildren.begin();
1618                lod_itr!=lodChildren.end();
1619                ++lod_itr)
1620            {
1621                float r = (*lod_itr)->getBound().radius();
1622                if (r>=0 && r<smallestRadius) smallestRadius = r;
1623                bb.expandBy((*lod_itr)->getCenter());
1624            }
1625            if (bb.radius()<smallestRadius*0.1f)
1626            {
1627                typedef std::pair<float,float> RangePair;
1628                typedef std::multimap<RangePair,osg::Node*> RangeMap;
1629                RangeMap rangeMap;
1630                for(lod_itr=lodChildren.begin();
1631                    lod_itr!=lodChildren.end();
1632                    ++lod_itr)
1633                {
1634
1635                    osg::LOD* lod = *lod_itr;
1636                    for(unsigned int i=0;i<lod->getNumRanges();++i)
1637                    {
1638                        rangeMap.insert(RangeMap::value_type(RangePair(lod->getMinRange(i),lod->getMaxRange(i)),lod->getChild(i)));
1639                    }
1640
1641                }
1642
1643                // create new LOD containing all other LOD's children.
1644                osg::LOD* newLOD = new osg::LOD;
1645                newLOD->setName("newLOD");
1646                newLOD->setCenter(bb.center());
1647
1648                int i=0;
1649                for(RangeMap::iterator c_itr=rangeMap.begin();
1650                    c_itr!=rangeMap.end();
1651                    ++c_itr,++i)
1652                {
1653                    newLOD->setRange(i,c_itr->first.first,c_itr->first.second);
1654                    newLOD->addChild(c_itr->second);
1655                }
1656
1657                // add LOD into parent.
1658                group->addChild(newLOD);
1659
1660                // remove all the old LOD's from group.
1661                for(lod_itr=lodChildren.begin();
1662                    lod_itr!=lodChildren.end();
1663                    ++lod_itr)
1664                {
1665                    group->removeChild(*lod_itr);
1666                }
1667
1668            }
1669
1670        }
1671    }
1672    _groupList.clear();
1673}
1674
1675////////////////////////////////////////////////////////////////////////////
1676// code to merge geometry object which share, state, and attribute bindings.
1677////////////////////////////////////////////////////////////////////////////
1678
1679struct LessGeometry
1680{
1681    bool operator() (const osg::Geometry* lhs,const osg::Geometry* rhs) const
1682    {
1683        if (lhs->getStateSet()<rhs->getStateSet()) return true;
1684        if (rhs->getStateSet()<lhs->getStateSet()) return false;
1685
1686        if (rhs->getVertexIndices()) { if (!lhs->getVertexIndices()) return true; }
1687        else if (lhs->getVertexIndices()) return false;
1688
1689        if (lhs->getNormalBinding()<rhs->getNormalBinding()) return true;
1690        if (rhs->getNormalBinding()<lhs->getNormalBinding()) return false;
1691
1692        if (rhs->getNormalIndices()) { if (!lhs->getNormalIndices()) return true; }
1693        else if (lhs->getNormalIndices()) return false;
1694
1695        if (lhs->getColorBinding()<rhs->getColorBinding()) return true;
1696        if (rhs->getColorBinding()<lhs->getColorBinding()) return false;
1697
1698        if (rhs->getColorIndices()) { if (!lhs->getColorIndices()) return true; }
1699        else if (lhs->getColorIndices()) return false;
1700
1701        if (lhs->getSecondaryColorBinding()<rhs->getSecondaryColorBinding()) return true;
1702        if (rhs->getSecondaryColorBinding()<lhs->getSecondaryColorBinding()) return false;
1703
1704        if (rhs->getSecondaryColorIndices()) { if (!lhs->getSecondaryColorIndices()) return true; }
1705        else if (lhs->getSecondaryColorIndices()) return false;
1706
1707        if (lhs->getFogCoordBinding()<rhs->getFogCoordBinding()) return true;
1708        if (rhs->getFogCoordBinding()<lhs->getFogCoordBinding()) return false;
1709
1710        if (rhs->getFogCoordIndices()) { if (!lhs->getFogCoordIndices()) return true; }
1711        else if (lhs->getFogCoordIndices()) return false;
1712
1713        if (lhs->getNumTexCoordArrays()<rhs->getNumTexCoordArrays()) return true;
1714        if (rhs->getNumTexCoordArrays()<lhs->getNumTexCoordArrays()) return false;
1715
1716        // therefore lhs->getNumTexCoordArrays()==rhs->getNumTexCoordArrays()
1717
1718        unsigned int i;
1719        for(i=0;i<lhs->getNumTexCoordArrays();++i)
1720        {
1721            if (rhs->getTexCoordArray(i))
1722            {
1723                if (!lhs->getTexCoordArray(i)) return true;
1724            }
1725            else if (lhs->getTexCoordArray(i)) return false;
1726
1727            if (rhs->getTexCoordIndices(i)) { if (!lhs->getTexCoordIndices(i)) return true; }
1728            else if (lhs->getTexCoordIndices(i)) return false;
1729        }
1730
1731        for(i=0;i<lhs->getNumVertexAttribArrays();++i)
1732        {
1733            if (rhs->getVertexAttribArray(i))
1734            {
1735                if (!lhs->getVertexAttribArray(i)) return true;
1736            }
1737            else if (lhs->getVertexAttribArray(i)) return false;
1738
1739            if (rhs->getVertexAttribIndices(i)) { if (!lhs->getVertexAttribIndices(i)) return true; }
1740            else if (lhs->getVertexAttribIndices(i)) return false;
1741        }
1742
1743
1744        if (lhs->getNormalBinding()==osg::Geometry::BIND_OVERALL)
1745        {
1746            // assumes that the bindings and arrays are set up correctly, this
1747            // should be the case after running computeCorrectBindingsAndArraySizes();
1748            const osg::Array* lhs_normalArray = lhs->getNormalArray();
1749            const osg::Array* rhs_normalArray = rhs->getNormalArray();
1750            if (lhs_normalArray->getType()<rhs_normalArray->getType()) return true;
1751            if (rhs_normalArray->getType()<lhs_normalArray->getType()) return false;
1752            switch(lhs_normalArray->getType())
1753            {
1754            case(osg::Array::Vec3bArrayType):
1755                if ((*static_cast<const osg::Vec3bArray*>(lhs_normalArray))[0]<(*static_cast<const osg::Vec3bArray*>(rhs_normalArray))[0]) return true;
1756                if ((*static_cast<const osg::Vec3bArray*>(rhs_normalArray))[0]<(*static_cast<const osg::Vec3bArray*>(lhs_normalArray))[0]) return false;
1757                break;
1758            case(osg::Array::Vec3sArrayType):
1759                if ((*static_cast<const osg::Vec3sArray*>(lhs_normalArray))[0]<(*static_cast<const osg::Vec3sArray*>(rhs_normalArray))[0]) return true;
1760                if ((*static_cast<const osg::Vec3sArray*>(rhs_normalArray))[0]<(*static_cast<const osg::Vec3sArray*>(lhs_normalArray))[0]) return false;
1761                break;
1762            case(osg::Array::Vec3ArrayType):
1763                if ((*static_cast<const osg::Vec3Array*>(lhs_normalArray))[0]<(*static_cast<const osg::Vec3Array*>(rhs_normalArray))[0]) return true;
1764                if ((*static_cast<const osg::Vec3Array*>(rhs_normalArray))[0]<(*static_cast<const osg::Vec3Array*>(lhs_normalArray))[0]) return false;
1765                break;
1766            default:
1767                break;
1768            }
1769        }
1770
1771        if (lhs->getColorBinding()==osg::Geometry::BIND_OVERALL)
1772        {
1773            const osg::Array* lhs_colorArray = lhs->getColorArray();
1774            const osg::Array* rhs_colorArray = rhs->getColorArray();
1775            if (lhs_colorArray->getType()<rhs_colorArray->getType()) return true;
1776            if (rhs_colorArray->getType()<lhs_colorArray->getType()) return false;
1777            switch(lhs_colorArray->getType())
1778            {
1779                case(osg::Array::Vec4ubArrayType):
1780                    if ((*static_cast<const osg::Vec4ubArray*>(lhs_colorArray))[0]<(*static_cast<const osg::Vec4ubArray*>(rhs_colorArray))[0]) return true;
1781                    if ((*static_cast<const osg::Vec4ubArray*>(rhs_colorArray))[0]<(*static_cast<const osg::Vec4ubArray*>(lhs_colorArray))[0]) return false;
1782                    break;
1783                case(osg::Array::Vec3ArrayType):
1784                    if ((*static_cast<const osg::Vec3Array*>(lhs_colorArray))[0]<(*static_cast<const osg::Vec3Array*>(rhs_colorArray))[0]) return true;
1785                    if ((*static_cast<const osg::Vec3Array*>(rhs_colorArray))[0]<(*static_cast<const osg::Vec3Array*>(lhs_colorArray))[0]) return false;
1786                    break;
1787                case(osg::Array::Vec4ArrayType):
1788                    if ((*static_cast<const osg::Vec4Array*>(lhs_colorArray))[0]<(*static_cast<const osg::Vec4Array*>(rhs_colorArray))[0]) return true;
1789                    if ((*static_cast<const osg::Vec4Array*>(rhs_colorArray))[0]<(*static_cast<const osg::Vec4Array*>(lhs_colorArray))[0]) return false;
1790                    break;
1791                default:
1792                    break;
1793            }
1794
1795        }
1796
1797        return false;
1798
1799    }
1800};
1801
1802struct LessGeometryPrimitiveType
1803{
1804    bool operator() (const osg::Geometry* lhs,const osg::Geometry* rhs) const
1805    {
1806        for(unsigned int i=0;
1807            i<lhs->getNumPrimitiveSets() && i<rhs->getNumPrimitiveSets();
1808            ++i)
1809        {
1810            if (lhs->getPrimitiveSet(i)->getType()<rhs->getPrimitiveSet(i)->getType()) return true;
1811            else if (rhs->getPrimitiveSet(i)->getType()<lhs->getPrimitiveSet(i)->getType()) return false;
1812
1813            if (lhs->getPrimitiveSet(i)->getMode()<rhs->getPrimitiveSet(i)->getMode()) return true;
1814            else if (rhs->getPrimitiveSet(i)->getMode()<lhs->getPrimitiveSet(i)->getMode()) return false;
1815
1816        }
1817        return lhs->getNumPrimitiveSets()<rhs->getNumPrimitiveSets();
1818    }
1819};
1820
1821void Optimizer::CheckGeometryVisitor::checkGeode(osg::Geode& geode)
1822{
1823    if (isOperationPermissibleForObject(&geode))
1824    {
1825        for(unsigned int i=0;i<geode.getNumDrawables();++i)
1826        {
1827            osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1828            if (geom && isOperationPermissibleForObject(geom))
1829            {
1830                geom->computeCorrectBindingsAndArraySizes();
1831            }
1832        }
1833    }
1834}
1835
1836void Optimizer::MakeFastGeometryVisitor::checkGeode(osg::Geode& geode)
1837{
1838    if (isOperationPermissibleForObject(&geode))
1839    {
1840        for(unsigned int i=0;i<geode.getNumDrawables();++i)
1841        {
1842            osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1843            if (geom && isOperationPermissibleForObject(geom))
1844            {
1845                if (!geom->areFastPathsUsed() && !geom->getInternalOptimizedGeometry())
1846                {
1847                    geom->computeInternalOptimizedGeometry();
1848                }
1849            }
1850        }
1851    }
1852}
1853
1854/// Shortcut to get size of an array, even if pointer is NULL.
1855inline unsigned int getSize(const osg::Array * a) { return a ? a->getNumElements() : 0; }
1856
1857/// When merging geometries, tests if two arrays can be merged, regarding to their number of components, and the number of vertices.
1858bool isArrayCompatible(unsigned int numVertice1, unsigned int numVertice2, const osg::Array* compare1, const osg::Array* compare2)
1859{
1860    // Sumed up truth table:
1861    //  If array (1 or 2) not empty and vertices empty => error, should not happen (allows simplification in formulae below)
1862    //  If one side has both vertices and array, and the other side has only vertices => then arrays cannot be merged
1863    //  Else, arrays can be merged
1864    //assert(numVertice1 || !getSize(compare1));
1865    //assert(numVertice2 || !getSize(compare2));
1866    return !(   (numVertice1 && !getSize(compare1) && getSize(compare2))
1867             || (numVertice2 && !getSize(compare2) && getSize(compare1)) );
1868}
1869
1870/// Return true only if both geometries have same array type and if arrays (such as TexCoords) are compatible (i.e. both empty or both filled)
1871bool isAbleToMerge(const osg::Geometry& g1, const osg::Geometry& g2)
1872{
1873    unsigned int numVertice1( getSize(g1.getVertexArray()) );
1874    unsigned int numVertice2( getSize(g2.getVertexArray()) );
1875
1876    // first verify arrays size
1877    if (!isArrayCompatible(numVertice1,numVertice2,g1.getNormalArray(),g2.getNormalArray()) ||
1878        !isArrayCompatible(numVertice1,numVertice2,g1.getColorArray(),g2.getColorArray()) ||
1879        !isArrayCompatible(numVertice1,numVertice2,g1.getSecondaryColorArray(),g2.getSecondaryColorArray()) ||
1880        !isArrayCompatible(numVertice1,numVertice2,g1.getFogCoordArray(),g2.getFogCoordArray()) ||
1881        g1.getNumTexCoordArrays()!=g2.getNumTexCoordArrays()) return false;
1882
1883    for (unsigned int eachTexCoordArray=0;eachTexCoordArray<g1.getNumTexCoordArrays();++eachTexCoordArray)
1884    {
1885        if (!isArrayCompatible(numVertice1,numVertice2,g1.getTexCoordArray(eachTexCoordArray),g2.getTexCoordArray(eachTexCoordArray))) return false;
1886    }
1887
1888    // then verify data type compatibility
1889    if (g1.getVertexArray() && g2.getVertexArray() && g1.getVertexArray()->getDataType()!=g2.getVertexArray()->getDataType()) return false;
1890    if (g1.getNormalArray() && g2.getNormalArray() && g1.getNormalArray()->getDataType()!=g2.getNormalArray()->getDataType()) return false;
1891    if (g1.getColorArray() && g2.getColorArray() && g1.getColorArray()->getDataType()!=g2.getColorArray()->getDataType()) return false;
1892    if (g1.getSecondaryColorArray() && g2.getSecondaryColorArray() && g1.getSecondaryColorArray()->getDataType()!=g2.getSecondaryColorArray()->getDataType()) return false;
1893    if (g1.getFogCoordArray() && g2.getNormalArray() && g1.getFogCoordArray()->getDataType()!=g2.getFogCoordArray()->getDataType()) return false;
1894    return true;
1895}
1896
1897bool Optimizer::MergeGeometryVisitor::mergeGeode(osg::Geode& geode)
1898{
1899    if (!isOperationPermissibleForObject(&geode)) return false;
1900
1901    if (geode.getNumDrawables()>=2)
1902    {
1903
1904        // OSG_NOTICE<<"Before "<<geode.getNumDrawables()<<std::endl;
1905
1906        typedef std::vector<osg::Geometry*>                         DuplicateList;
1907        typedef std::map<osg::Geometry*,DuplicateList,LessGeometry> GeometryDuplicateMap;
1908
1909        typedef std::vector<DuplicateList> MergeList;
1910
1911        GeometryDuplicateMap geometryDuplicateMap;
1912        osg::Geode::DrawableList standardDrawables;
1913
1914        unsigned int i;
1915        for(i=0;i<geode.getNumDrawables();++i)
1916        {
1917            osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1918            if (geom)
1919            {
1920                //geom->computeCorrectBindingsAndArraySizes();
1921
1922                if (!geometryContainsSharedArrays(*geom) &&
1923                      geom->getDataVariance()!=osg::Object::DYNAMIC &&
1924                      isOperationPermissibleForObject(geom))
1925                {
1926                    geometryDuplicateMap[geom].push_back(geom);
1927                }
1928                else
1929                {
1930                    standardDrawables.push_back(geode.getDrawable(i));
1931                }
1932            }
1933            else
1934            {
1935                standardDrawables.push_back(geode.getDrawable(i));
1936            }
1937        }
1938
1939#if 1
1940        // first try to group geometries with the same properties
1941        // (i.e. array types) to avoid loss of data during merging
1942        MergeList mergeListChecked;        // List of drawables just before merging, grouped by "compatibility" and vertex limit
1943        MergeList mergeList;            // Intermediate list of drawables, grouped ony by "compatibility"
1944        for(GeometryDuplicateMap::iterator itr=geometryDuplicateMap.begin();
1945            itr!=geometryDuplicateMap.end();
1946            ++itr)
1947        {
1948            if (itr->second.empty()) continue;
1949            if (itr->second.size()==1)
1950            {
1951                mergeList.push_back(DuplicateList());
1952                DuplicateList* duplicateList = &mergeList.back();
1953                duplicateList->push_back(itr->second[0]);
1954                continue;
1955            }
1956
1957            std::sort(itr->second.begin(),itr->second.end(),LessGeometryPrimitiveType());
1958
1959            // initialize the temporary list by pushing the first geometry
1960            MergeList mergeListTmp;
1961            mergeListTmp.push_back(DuplicateList());
1962            DuplicateList* duplicateList = &mergeListTmp.back();
1963            duplicateList->push_back(itr->second[0]);
1964
1965            for(DuplicateList::iterator dupItr=itr->second.begin()+1;
1966                dupItr!=itr->second.end();
1967                ++dupItr)
1968            {
1969                osg::Geometry* geomToPush = *dupItr;
1970
1971                // try to group geomToPush with another geometry
1972                MergeList::iterator eachMergeList=mergeListTmp.begin();
1973                for(;eachMergeList!=mergeListTmp.end();++eachMergeList)
1974                {
1975                    if (!eachMergeList->empty() && eachMergeList->front()!=NULL
1976                        && isAbleToMerge(*eachMergeList->front(),*geomToPush))
1977                    {
1978                        eachMergeList->push_back(geomToPush);
1979                        break;
1980                    }
1981                }
1982
1983                // if no suitable group was found, then a new one is created
1984                if (eachMergeList==mergeListTmp.end())
1985                {
1986                    mergeListTmp.push_back(DuplicateList());
1987                    duplicateList = &mergeListTmp.back();
1988                    duplicateList->push_back(geomToPush);
1989                }
1990            }
1991
1992            // copy the group in the mergeListChecked
1993            for(MergeList::iterator eachMergeList=mergeListTmp.begin();eachMergeList!=mergeListTmp.end();++eachMergeList)
1994            {
1995                mergeListChecked.push_back(*eachMergeList);
1996            }
1997        }
1998
1999        // then build merge list using _targetMaximumNumberOfVertices
2000        bool needToDoMerge = false;
2001        // dequeue each DuplicateList when vertices limit is reached or when all elements has been checked
2002        for(;!mergeListChecked.empty();)
2003        {
2004            MergeList::iterator itr=mergeListChecked.begin();
2005            DuplicateList& duplicateList(*itr);
2006            if (duplicateList.size()==0)
2007            {
2008                mergeListChecked.erase(itr);
2009                continue;
2010            }
2011
2012            if (duplicateList.size()==1)
2013            {
2014                mergeList.push_back(duplicateList);
2015                mergeListChecked.erase(itr);
2016                continue;
2017            }
2018
2019            unsigned int numVertices(duplicateList.front()->getVertexArray() ? duplicateList.front()->getVertexArray()->getNumElements() : 0);
2020            DuplicateList::iterator eachGeom(duplicateList.begin()+1);
2021            // until all geometries have been checked or _targetMaximumNumberOfVertices is reached
2022            for (;eachGeom!=duplicateList.end(); ++eachGeom)
2023            {
2024                unsigned int numAddVertices((*eachGeom)->getVertexArray() ? (*eachGeom)->getVertexArray()->getNumElements() : 0);
2025                if (numVertices+numAddVertices<_targetMaximumNumberOfVertices)
2026                {
2027                    break;
2028                }
2029                else
2030                {
2031                    numVertices += numAddVertices;
2032                }
2033            }
2034
2035            // push back if bellow the limit
2036            if (numVertices<_targetMaximumNumberOfVertices)
2037            {
2038                if (duplicateList.size()>1) needToDoMerge = true;
2039                mergeList.push_back(duplicateList);
2040                mergeListChecked.erase(itr);
2041            }
2042            // else split the list to store what is below the limit and retry on what is above
2043            else
2044            {
2045                mergeList.push_back(DuplicateList());
2046                DuplicateList* duplicateListResult = &mergeList.back();
2047                duplicateListResult->insert(duplicateListResult->end(),duplicateList.begin(),eachGeom);
2048                duplicateList.erase(duplicateList.begin(),eachGeom);
2049                if (duplicateListResult->size()>1) needToDoMerge = true;
2050            }
2051        }
2052
2053        if (needToDoMerge)
2054        {
2055            // first take a reference to all the drawables to prevent them being deleted prematurely
2056            osg::Geode::DrawableList keepDrawables;
2057            keepDrawables.resize(geode.getNumDrawables());
2058            for(i=0; i<geode.getNumDrawables(); ++i)
2059            {
2060                keepDrawables[i] = geode.getDrawable(i);
2061            }
2062
2063            // now clear the drawable list of the Geode so we don't have to remove items one by one (which is slow)
2064            geode.removeDrawables(0, geode.getNumDrawables());
2065
2066            // add back in the standard drawables which arn't possible to merge.
2067            for(osg::Geode::DrawableList::iterator sitr = standardDrawables.begin();
2068                sitr != standardDrawables.end();
2069                ++sitr)
2070            {
2071                geode.addDrawable(sitr->get());
2072            }
2073
2074            // now do the merging of geometries
2075            for(MergeList::iterator mitr = mergeList.begin();
2076                mitr != mergeList.end();
2077                ++mitr)
2078            {
2079                DuplicateList& duplicateList = *mitr;
2080                if (duplicateList.size()>1)
2081                {
2082                    osg::Geometry* lhs = duplicateList.front();
2083                    geode.addDrawable(lhs);
2084                    for(DuplicateList::iterator ditr = duplicateList.begin()+1;
2085                        ditr != duplicateList.end();
2086                        ++ditr)
2087                    {
2088                        mergeGeometry(*lhs,**ditr);
2089                    }
2090                }
2091                else if (duplicateList.size()>0)
2092                {
2093                    geode.addDrawable(duplicateList.front());
2094                }
2095            }
2096        }
2097
2098#else
2099        // don't merge geometry if its above a maximum number of vertices.
2100        for(GeometryDuplicateMap::iterator itr=geometryDuplicateMap.begin();
2101            itr!=geometryDuplicateMap.end();
2102            ++itr)
2103        {
2104            if (itr->second.size()>1)
2105            {
2106                std::sort(itr->second.begin(),itr->second.end(),LessGeometryPrimitiveType());
2107                osg::Geometry* lhs = itr->second[0];
2108                for(DuplicateList::iterator dupItr=itr->second.begin()+1;
2109                    dupItr!=itr->second.end();
2110                    ++dupItr)
2111                {
2112
2113                    osg::Geometry* rhs = *dupItr;
2114
2115                    if (lhs->getVertexArray() && lhs->getVertexArray()->getNumElements()>=_targetMaximumNumberOfVertices)
2116                    {
2117                        lhs = rhs;
2118                        continue;
2119                    }
2120
2121                    if (rhs->getVertexArray() && rhs->getVertexArray()->getNumElements()>=_targetMaximumNumberOfVertices)
2122                    {
2123                        continue;
2124                    }
2125
2126                    if (lhs->getVertexArray() && rhs->getVertexArray() &&
2127                        (lhs->getVertexArray()->getNumElements()+rhs->getVertexArray()->getNumElements())>=_targetMaximumNumberOfVertices)
2128                    {
2129                        continue;
2130                    }
2131
2132                    if (mergeGeometry(*lhs,*rhs))
2133                    {
2134                        geode.removeDrawable(rhs);
2135
2136                        static int co = 0;
2137                        OSG_INFO<<"merged and removed Geometry "<<++co<<std::endl;
2138                    }
2139                }
2140            }
2141        }
2142#endif
2143
2144        // OSG_NOTICE<<"After "<<geode.getNumDrawables()<<std::endl;
2145
2146    }
2147
2148
2149    // convert all polygon primitives which has 3 indices into TRIANGLES, 4 indices into QUADS.
2150    unsigned int i;
2151    for(i=0;i<geode.getNumDrawables();++i)
2152    {
2153        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
2154        if (geom)
2155        {
2156            osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2157            for(osg::Geometry::PrimitiveSetList::iterator itr=primitives.begin();
2158                itr!=primitives.end();
2159                ++itr)
2160            {
2161                osg::PrimitiveSet* prim = itr->get();
2162                if (prim->getMode()==osg::PrimitiveSet::POLYGON)
2163                {
2164                    if (prim->getNumIndices()==3)
2165                    {
2166                        prim->setMode(osg::PrimitiveSet::TRIANGLES);
2167                    }
2168                    else if (prim->getNumIndices()==4)
2169                    {
2170                        prim->setMode(osg::PrimitiveSet::QUADS);
2171                    }
2172                }
2173            }
2174        }
2175    }
2176
2177    // now merge any compatible primitives.
2178    for(i=0;i<geode.getNumDrawables();++i)
2179    {
2180        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
2181        if (geom)
2182        {
2183            if (geom->getNumPrimitiveSets()>0 &&
2184                geom->getNormalBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2185                geom->getColorBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2186                geom->getSecondaryColorBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2187                geom->getFogCoordBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET)
2188            {
2189
2190#if 1
2191                bool doneCombine = false;
2192
2193                osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2194                unsigned int lhsNo=0;
2195                unsigned int rhsNo=1;
2196                while(rhsNo<primitives.size())
2197                {
2198                    osg::PrimitiveSet* lhs = primitives[lhsNo].get();
2199                    osg::PrimitiveSet* rhs = primitives[rhsNo].get();
2200
2201                    bool combine = false;
2202
2203                    if (lhs->getType()==rhs->getType() &&
2204                        lhs->getMode()==rhs->getMode())
2205                    {
2206
2207                        switch(lhs->getMode())
2208                        {
2209                        case(osg::PrimitiveSet::POINTS):
2210                        case(osg::PrimitiveSet::LINES):
2211                        case(osg::PrimitiveSet::TRIANGLES):
2212                        case(osg::PrimitiveSet::QUADS):
2213                            combine = true;
2214                            break;
2215                        }
2216
2217                    }
2218
2219                    if (combine)
2220                    {
2221
2222                        switch(lhs->getType())
2223                        {
2224                        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2225                            combine = mergePrimitive(*(static_cast<osg::DrawArrays*>(lhs)),*(static_cast<osg::DrawArrays*>(rhs)));
2226                            break;
2227                        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2228                            combine = mergePrimitive(*(static_cast<osg::DrawArrayLengths*>(lhs)),*(static_cast<osg::DrawArrayLengths*>(rhs)));
2229                            break;
2230                        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2231                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUByte*>(lhs)),*(static_cast<osg::DrawElementsUByte*>(rhs)));
2232                            break;
2233                        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2234                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUShort*>(lhs)),*(static_cast<osg::DrawElementsUShort*>(rhs)));
2235                            break;
2236                        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2237                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUInt*>(lhs)),*(static_cast<osg::DrawElementsUInt*>(rhs)));
2238                            break;
2239                        default:
2240                            combine = false;
2241                            break;
2242                        }
2243                    }
2244
2245                    if (combine)
2246                    {
2247                        // make this primitive set as invalid and needing cleaning up.
2248                        rhs->setMode(0xffffff);
2249                        doneCombine = true;
2250                        ++rhsNo;
2251                    }
2252                    else
2253                    {
2254                        lhsNo = rhsNo;
2255                        ++rhsNo;
2256                    }
2257                }
2258
2259    #if 1
2260                if (doneCombine)
2261                {
2262                    // now need to clean up primitiveset so it no longer contains the rhs combined primitives.
2263
2264                    // first swap with a empty primitiveSet to empty it completely.
2265                    osg::Geometry::PrimitiveSetList oldPrimitives;
2266                    primitives.swap(oldPrimitives);
2267
2268                    // now add the active primitive sets
2269                    for(osg::Geometry::PrimitiveSetList::iterator pitr = oldPrimitives.begin();
2270                        pitr != oldPrimitives.end();
2271                        ++pitr)
2272                    {
2273                        if ((*pitr)->getMode()!=0xffffff) primitives.push_back(*pitr);
2274                    }
2275                }
2276    #endif
2277
2278#else
2279
2280                osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2281                unsigned int primNo=0;
2282                while(primNo+1<primitives.size())
2283                {
2284                    osg::PrimitiveSet* lhs = primitives[primNo].get();
2285                    osg::PrimitiveSet* rhs = primitives[primNo+1].get();
2286
2287                    bool combine = false;
2288
2289                    if (lhs->getType()==rhs->getType() &&
2290                        lhs->getMode()==rhs->getMode())
2291                    {
2292
2293                        switch(lhs->getMode())
2294                        {
2295                        case(osg::PrimitiveSet::POINTS):
2296                        case(osg::PrimitiveSet::LINES):
2297                        case(osg::PrimitiveSet::TRIANGLES):
2298                        case(osg::PrimitiveSet::QUADS):
2299                            combine = true;
2300                            break;
2301                        }
2302
2303                    }
2304
2305                    if (combine)
2306                    {
2307
2308                        switch(lhs->getType())
2309                        {
2310                        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2311                            combine = mergePrimitive(*(static_cast<osg::DrawArrays*>(lhs)),*(static_cast<osg::DrawArrays*>(rhs)));
2312                            break;
2313                        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2314                            combine = mergePrimitive(*(static_cast<osg::DrawArrayLengths*>(lhs)),*(static_cast<osg::DrawArrayLengths*>(rhs)));
2315                            break;
2316                        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2317                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUByte*>(lhs)),*(static_cast<osg::DrawElementsUByte*>(rhs)));
2318                            break;
2319                        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2320                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUShort*>(lhs)),*(static_cast<osg::DrawElementsUShort*>(rhs)));
2321                            break;
2322                        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2323                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUInt*>(lhs)),*(static_cast<osg::DrawElementsUInt*>(rhs)));
2324                            break;
2325                        default:
2326                            break;
2327                        }
2328                    }
2329                    if (combine)
2330                    {
2331                        primitives.erase(primitives.begin()+primNo+1);
2332                    }
2333
2334                    if (!combine)
2335                    {
2336                        primNo++;
2337                    }
2338                }
2339#endif
2340            }
2341        }
2342
2343
2344    }
2345
2346//    geode.dirtyBound();
2347
2348
2349    return false;
2350}
2351
2352bool Optimizer::MergeGeometryVisitor::geometryContainsSharedArrays(osg::Geometry& geom)
2353{
2354    if (geom.getVertexArray() && geom.getVertexArray()->referenceCount()>1) return true;
2355    if (geom.getNormalArray() && geom.getNormalArray()->referenceCount()>1) return true;
2356    if (geom.getColorArray() && geom.getColorArray()->referenceCount()>1) return true;
2357    if (geom.getSecondaryColorArray() && geom.getSecondaryColorArray()->referenceCount()>1) return true;
2358    if (geom.getFogCoordArray() && geom.getFogCoordArray()->referenceCount()>1) return true;
2359
2360
2361    for(unsigned int unit=0;unit<geom.getNumTexCoordArrays();++unit)
2362    {
2363        osg::Array* tex = geom.getTexCoordArray(unit);
2364        if (tex && tex->referenceCount()>1) return true;
2365    }
2366
2367    // shift the indices of the incoming primitives to account for the pre existing geometry.
2368    for(osg::Geometry::PrimitiveSetList::iterator primItr=geom.getPrimitiveSetList().begin();
2369        primItr!=geom.getPrimitiveSetList().end();
2370        ++primItr)
2371    {
2372        if ((*primItr)->referenceCount()>1) return true;
2373    }
2374
2375
2376    return false;
2377}
2378
2379
2380class MergeArrayVisitor : public osg::ArrayVisitor
2381{
2382    protected:
2383        osg::Array* _lhs;
2384        int         _offset;
2385    public:
2386        MergeArrayVisitor() :
2387            _lhs(0),
2388            _offset(0) {}
2389
2390
2391        /// try to merge the content of two arrays.
2392        bool merge(osg::Array* lhs,osg::Array* rhs, int offset=0)
2393        {
2394            if (lhs==0 || rhs==0) return true;
2395            if (lhs->getType()!=rhs->getType()) return false;
2396
2397            _lhs = lhs;
2398            _offset = offset;
2399
2400            rhs->accept(*this);
2401            return true;
2402        }
2403
2404        template<typename T>
2405        void _merge(T& rhs)
2406        {
2407            T* lhs = static_cast<T*>(_lhs);
2408            lhs->insert(lhs->end(),rhs.begin(),rhs.end());
2409        }
2410
2411        template<typename T>
2412        void _mergeAndOffset(T& rhs)
2413        {
2414            T* lhs = static_cast<T*>(_lhs);
2415
2416            typename T::iterator itr;
2417            for(itr = rhs.begin();
2418                itr != rhs.end();
2419                ++itr)
2420            {
2421                lhs->push_back(*itr + _offset);
2422            }
2423        }
2424
2425        virtual void apply(osg::Array&) { OSG_WARN << "Warning: Optimizer's MergeArrayVisitor cannot merge Array type." << std::endl; }
2426
2427        virtual void apply(osg::ByteArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2428        virtual void apply(osg::ShortArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2429        virtual void apply(osg::IntArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2430        virtual void apply(osg::UByteArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2431        virtual void apply(osg::UShortArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2432        virtual void apply(osg::UIntArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2433
2434        virtual void apply(osg::Vec4ubArray& rhs) { _merge(rhs); }
2435        virtual void apply(osg::FloatArray& rhs) { _merge(rhs); }
2436        virtual void apply(osg::Vec2Array& rhs) { _merge(rhs); }
2437        virtual void apply(osg::Vec3Array& rhs) { _merge(rhs); }
2438        virtual void apply(osg::Vec4Array& rhs) { _merge(rhs); }
2439
2440        virtual void apply(osg::DoubleArray& rhs) { _merge(rhs); }
2441        virtual void apply(osg::Vec2dArray& rhs) { _merge(rhs); }
2442        virtual void apply(osg::Vec3dArray& rhs) { _merge(rhs); }
2443        virtual void apply(osg::Vec4dArray& rhs) { _merge(rhs); }
2444
2445        virtual void apply(osg::Vec2bArray&  rhs) { _merge(rhs); }
2446        virtual void apply(osg::Vec3bArray&  rhs) { _merge(rhs); }
2447        virtual void apply(osg::Vec4bArray&  rhs) { _merge(rhs); }
2448        virtual void apply(osg::Vec2sArray& rhs) { _merge(rhs); }
2449        virtual void apply(osg::Vec3sArray& rhs) { _merge(rhs); }
2450        virtual void apply(osg::Vec4sArray& rhs) { _merge(rhs); }
2451};
2452
2453bool Optimizer::MergeGeometryVisitor::mergeGeometry(osg::Geometry& lhs,osg::Geometry& rhs)
2454{
2455
2456    MergeArrayVisitor merger;
2457
2458    unsigned int base = 0;
2459    unsigned int vbase = lhs.getVertexArray() ? lhs.getVertexArray()->getNumElements() : 0;
2460    if (lhs.getVertexArray() && rhs.getVertexArray())
2461    {
2462
2463        base = lhs.getVertexArray()->getNumElements();
2464        if (!merger.merge(lhs.getVertexArray(),rhs.getVertexArray()))
2465        {
2466            OSG_DEBUG << "MergeGeometry: vertex array not merged. Some data may be lost." <<std::endl;
2467        }
2468    }
2469    else if (rhs.getVertexArray())
2470    {
2471        base = 0;
2472        lhs.setVertexArray(rhs.getVertexArray());
2473    }
2474
2475    if (lhs.getVertexIndices() && rhs.getVertexIndices())
2476    {
2477
2478        base = lhs.getVertexIndices()->getNumElements();
2479        if (!merger.merge(lhs.getVertexIndices(),rhs.getVertexIndices(),vbase))
2480        {
2481            OSG_DEBUG << "MergeGeometry: vertex indices not merged. Some data may be lost." <<std::endl;
2482        }
2483    }
2484    else if (rhs.getVertexIndices())
2485    {
2486        base = 0;
2487        lhs.setVertexIndices(rhs.getVertexIndices());
2488    }
2489
2490
2491    unsigned int nbase = lhs.getNormalArray() ? lhs.getNormalArray()->getNumElements() : 0;
2492    if (lhs.getNormalArray() && rhs.getNormalArray() && lhs.getNormalBinding()!=osg::Geometry::BIND_OVERALL)
2493    {
2494        if (!merger.merge(lhs.getNormalArray(),rhs.getNormalArray()))
2495        {
2496            OSG_DEBUG << "MergeGeometry: normal array not merged. Some data may be lost." <<std::endl;
2497        }
2498    }
2499    else if (rhs.getNormalArray())
2500    {
2501        lhs.setNormalArray(rhs.getNormalArray());
2502    }
2503
2504    if (lhs.getNormalIndices() && rhs.getNormalIndices() && lhs.getNormalBinding()!=osg::Geometry::BIND_OVERALL)
2505    {
2506        if (!merger.merge(lhs.getNormalIndices(),rhs.getNormalIndices(),nbase))
2507        {
2508            OSG_DEBUG << "MergeGeometry: Vertex Array not merged. Some data may be lost." <<std::endl;
2509        }
2510    }
2511    else if (rhs.getNormalIndices())
2512    {
2513        // this assignment makes the assumption that lhs.NormalArray is empty as well and NormalIndices
2514        lhs.setNormalIndices(rhs.getNormalIndices());
2515    }
2516
2517
2518    unsigned int cbase = lhs.getColorArray() ? lhs.getColorArray()->getNumElements() : 0;
2519    if (lhs.getColorArray() && rhs.getColorArray() && lhs.getColorBinding()!=osg::Geometry::BIND_OVERALL)
2520    {
2521        if (!merger.merge(lhs.getColorArray(),rhs.getColorArray()))
2522        {
2523            OSG_DEBUG << "MergeGeometry: color array not merged. Some data may be lost." <<std::endl;
2524        }
2525    }
2526    else if (rhs.getColorArray())
2527    {
2528        lhs.setColorArray(rhs.getColorArray());
2529    }
2530
2531    if (lhs.getColorIndices() && rhs.getColorIndices() && lhs.getColorBinding()!=osg::Geometry::BIND_OVERALL)
2532    {
2533        if (!merger.merge(lhs.getColorIndices(),rhs.getColorIndices(),cbase))
2534        {
2535            OSG_DEBUG << "MergeGeometry: color indices not merged. Some data may be lost." <<std::endl;
2536        }
2537    }
2538    else if (rhs.getColorIndices())
2539    {
2540        // this assignment makes the assumption that lhs.ColorArray is empty as well and ColorIndices
2541        lhs.setColorIndices(rhs.getColorIndices());
2542    }
2543
2544    unsigned int scbase = lhs.getSecondaryColorArray() ? lhs.getSecondaryColorArray()->getNumElements() : 0;
2545    if (lhs.getSecondaryColorArray() && rhs.getSecondaryColorArray() && lhs.getSecondaryColorBinding()!=osg::Geometry::BIND_OVERALL)
2546    {
2547        if (!merger.merge(lhs.getSecondaryColorArray(),rhs.getSecondaryColorArray()))
2548        {
2549            OSG_DEBUG << "MergeGeometry: secondary color array not merged. Some data may be lost." <<std::endl;
2550        }
2551    }
2552    else if (rhs.getSecondaryColorArray())
2553    {
2554        lhs.setSecondaryColorArray(rhs.getSecondaryColorArray());
2555    }
2556
2557    if (lhs.getSecondaryColorIndices() && rhs.getSecondaryColorIndices() && lhs.getSecondaryColorBinding()!=osg::Geometry::BIND_OVERALL)
2558    {
2559        if (!merger.merge(lhs.getSecondaryColorIndices(),rhs.getSecondaryColorIndices(),scbase))
2560        {
2561            OSG_DEBUG << "MergeGeometry: secondary color indices not merged. Some data may be lost." <<std::endl;
2562        }
2563    }
2564    else if (rhs.getSecondaryColorIndices())
2565    {
2566        // this assignment makes the assumption that lhs.SecondaryColorArray is empty as well and SecondaryColorIndices
2567        lhs.setSecondaryColorIndices(rhs.getSecondaryColorIndices());
2568    }
2569
2570    unsigned int fcbase = lhs.getFogCoordArray() ? lhs.getFogCoordArray()->getNumElements() : 0;
2571    if (lhs.getFogCoordArray() && rhs.getFogCoordArray() && lhs.getFogCoordBinding()!=osg::Geometry::BIND_OVERALL)
2572    {
2573        if (!merger.merge(lhs.getFogCoordArray(),rhs.getFogCoordArray()))
2574        {
2575            OSG_DEBUG << "MergeGeometry: fog coord array not merged. Some data may be lost." <<std::endl;
2576        }
2577    }
2578    else if (rhs.getFogCoordArray())
2579    {
2580        lhs.setFogCoordArray(rhs.getFogCoordArray());
2581    }
2582
2583    if (lhs.getFogCoordIndices() && rhs.getFogCoordIndices() && lhs.getFogCoordBinding()!=osg::Geometry::BIND_OVERALL)
2584    {
2585        if (!merger.merge(lhs.getFogCoordIndices(),rhs.getFogCoordIndices(),fcbase))
2586        {
2587            OSG_DEBUG << "MergeGeometry: fog coord indices not merged. Some data may be lost." <<std::endl;
2588        }
2589    }
2590    else if (rhs.getFogCoordIndices())
2591    {
2592        // this assignment makes the assumption that lhs.FogCoordArray is empty as well and FogCoordIndices
2593        lhs.setFogCoordIndices(rhs.getFogCoordIndices());
2594    }
2595
2596
2597    unsigned int unit;
2598    for(unit=0;unit<lhs.getNumTexCoordArrays();++unit)
2599    {
2600        unsigned int tcbase = lhs.getTexCoordArray(unit) ? lhs.getTexCoordArray(unit)->getNumElements() : 0;
2601        if (!merger.merge(lhs.getTexCoordArray(unit),rhs.getTexCoordArray(unit)))
2602        {
2603            OSG_DEBUG << "MergeGeometry: tex coord array not merged. Some data may be lost." <<std::endl;
2604        }
2605
2606        if (lhs.getTexCoordIndices(unit) && rhs.getTexCoordIndices(unit))
2607        {
2608            if (!merger.merge(lhs.getTexCoordIndices(unit),rhs.getTexCoordIndices(unit),tcbase))
2609            {
2610                OSG_DEBUG << "MergeGeometry: tex coord indices not merged. Some data may be lost." <<std::endl;
2611            }
2612        }
2613    }
2614
2615    for(unit=0;unit<lhs.getNumVertexAttribArrays();++unit)
2616    {
2617        unsigned int vabase = lhs.getVertexAttribArray(unit) ? lhs.getVertexAttribArray(unit)->getNumElements() : 0;
2618        if (!merger.merge(lhs.getVertexAttribArray(unit),rhs.getVertexAttribArray(unit)))
2619        {
2620            OSG_DEBUG << "MergeGeometry: vertex attrib array not merged. Some data may be lost." <<std::endl;
2621        }
2622
2623        if (lhs.getVertexAttribIndices(unit) && rhs.getVertexAttribIndices(unit))
2624        {
2625            if (!merger.merge(lhs.getVertexAttribIndices(unit),rhs.getVertexAttribIndices(unit),vabase))
2626            {
2627                OSG_DEBUG << "MergeGeometry: vertex attrib indices not merged. Some data may be lost." <<std::endl;
2628            }
2629        }
2630    }
2631
2632
2633    // shift the indices of the incoming primitives to account for the pre existing geometry.
2634    osg::Geometry::PrimitiveSetList::iterator primItr;
2635    for(primItr=rhs.getPrimitiveSetList().begin(); primItr!=rhs.getPrimitiveSetList().end(); ++primItr)
2636    {
2637        osg::PrimitiveSet* primitive = primItr->get();
2638
2639        switch(primitive->getType())
2640        {
2641        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2642            {
2643                osg::DrawElementsUByte* primitiveUByte = static_cast<osg::DrawElementsUByte*>(primitive);
2644                unsigned int currentMaximum = 0;
2645                for(osg::DrawElementsUByte::iterator eitr=primitiveUByte->begin();
2646                    eitr!=primitiveUByte->end();
2647                    ++eitr)
2648                {
2649                    currentMaximum = osg::maximum(currentMaximum,(unsigned int)*eitr);
2650                }
2651                if ((base+currentMaximum)>=65536)
2652                {
2653                    // must promote to a DrawElementsUInt
2654                    osg::DrawElementsUInt* new_primitive = new osg::DrawElementsUInt(primitive->getMode());
2655                    std::copy(primitiveUByte->begin(),primitiveUByte->end(),std::back_inserter(*new_primitive));
2656                    new_primitive->offsetIndices(base);
2657                    (*primItr) = new_primitive;
2658                } else if ((base+currentMaximum)>=256)
2659                {
2660                    // must promote to a DrawElementsUShort
2661                    osg::DrawElementsUShort* new_primitive = new osg::DrawElementsUShort(primitive->getMode());
2662                    std::copy(primitiveUByte->begin(),primitiveUByte->end(),std::back_inserter(*new_primitive));
2663                    new_primitive->offsetIndices(base);
2664                    (*primItr) = new_primitive;
2665                }
2666                else
2667                {
2668                    primitive->offsetIndices(base);
2669                }
2670            }
2671            break;
2672
2673        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2674            {
2675                osg::DrawElementsUShort* primitiveUShort = static_cast<osg::DrawElementsUShort*>(primitive);
2676                unsigned int currentMaximum = 0;
2677                for(osg::DrawElementsUShort::iterator eitr=primitiveUShort->begin();
2678                    eitr!=primitiveUShort->end();
2679                    ++eitr)
2680                {
2681                    currentMaximum = osg::maximum(currentMaximum,(unsigned int)*eitr);
2682                }
2683                if ((base+currentMaximum)>=65536)
2684                {
2685                    // must promote to a DrawElementsUInt
2686                    osg::DrawElementsUInt* new_primitive = new osg::DrawElementsUInt(primitive->getMode());
2687                    std::copy(primitiveUShort->begin(),primitiveUShort->end(),std::back_inserter(*new_primitive));
2688                    new_primitive->offsetIndices(base);
2689                    (*primItr) = new_primitive;
2690                }
2691                else
2692                {
2693                    primitive->offsetIndices(base);
2694                }
2695            }
2696            break;
2697
2698        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2699        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2700        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2701        default:
2702            primitive->offsetIndices(base);
2703            break;
2704        }
2705    }
2706
2707    for(primItr=rhs.getPrimitiveSetList().begin(); primItr!=rhs.getPrimitiveSetList().end(); ++primItr)
2708    {
2709        lhs.addPrimitiveSet(primItr->get());
2710    }
2711
2712    lhs.dirtyBound();
2713    lhs.dirtyDisplayList();
2714
2715    return true;
2716}
2717
2718bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawArrays& lhs,osg::DrawArrays& rhs)
2719{
2720    if (lhs.getFirst()+lhs.getCount()==rhs.getFirst())
2721    {
2722        lhs.setCount(lhs.getCount()+rhs.getCount());
2723        return true;
2724    }
2725    return false;
2726}
2727
2728bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawArrayLengths& lhs,osg::DrawArrayLengths& rhs)
2729{
2730    int lhs_count = std::accumulate(lhs.begin(),lhs.end(),0);
2731
2732    if (lhs.getFirst()+lhs_count==rhs.getFirst())
2733    {
2734        lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2735        return true;
2736    }
2737    return false;
2738}
2739
2740bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUByte& lhs,osg::DrawElementsUByte& rhs)
2741{
2742    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2743    return true;
2744}
2745
2746bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUShort& lhs,osg::DrawElementsUShort& rhs)
2747{
2748    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2749    return true;
2750}
2751
2752bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUInt& lhs,osg::DrawElementsUInt& rhs)
2753{
2754    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2755    return true;
2756}
2757
2758
2759////////////////////////////////////////////////////////////////////////////////////////////
2760//
2761//  Spatialize the scene to accelerate culling
2762//
2763
2764void Optimizer::SpatializeGroupsVisitor::apply(osg::Group& group)
2765{
2766    if (typeid(group)==typeid(osg::Group) || group.asTransform())
2767    {
2768        if (isOperationPermissibleForObject(&group))
2769        {
2770            _groupsToDivideList.insert(&group);
2771        }
2772    }
2773    traverse(group);
2774}
2775
2776void Optimizer::SpatializeGroupsVisitor::apply(osg::Geode& geode)
2777{
2778    if (typeid(geode)==typeid(osg::Geode))
2779    {
2780        if (isOperationPermissibleForObject(&geode))
2781        {
2782            _geodesToDivideList.insert(&geode);
2783        }
2784    }
2785    traverse(geode);
2786}
2787
2788bool Optimizer::SpatializeGroupsVisitor::divide(unsigned int maxNumTreesPerCell)
2789{
2790    bool divided = false;
2791    for(GroupsToDivideList::iterator itr=_groupsToDivideList.begin();
2792        itr!=_groupsToDivideList.end();
2793        ++itr)
2794    {
2795        if (divide(*itr,maxNumTreesPerCell)) divided = true;
2796    }
2797
2798    for(GeodesToDivideList::iterator geode_itr=_geodesToDivideList.begin();
2799        geode_itr!=_geodesToDivideList.end();
2800        ++geode_itr)
2801    {
2802        if (divide(*geode_itr,maxNumTreesPerCell)) divided = true;
2803    }
2804
2805    return divided;
2806}
2807
2808bool Optimizer::SpatializeGroupsVisitor::divide(osg::Group* group, unsigned int maxNumTreesPerCell)
2809{
2810    if (group->getNumChildren()<=maxNumTreesPerCell) return false;
2811
2812    // create the original box.
2813    osg::BoundingBox bb;
2814    unsigned int i;
2815    for(i=0;i<group->getNumChildren();++i)
2816    {
2817        bb.expandBy(group->getChild(i)->getBound().center());
2818    }
2819
2820    float radius = bb.radius();
2821    float divide_distance = radius*0.7f;
2822    bool xAxis = (bb.xMax()-bb.xMin())>divide_distance;
2823    bool yAxis = (bb.yMax()-bb.yMin())>divide_distance;
2824    bool zAxis = (bb.zMax()-bb.zMin())>divide_distance;
2825
2826    OSG_INFO<<"Dividing "<<group->className()<<"  num children = "<<group->getNumChildren()<<"  xAxis="<<xAxis<<"  yAxis="<<yAxis<<"   zAxis="<<zAxis<<std::endl;
2827
2828    if (!xAxis && !yAxis && !zAxis)
2829    {
2830        OSG_INFO<<"  No axis to divide, stopping division."<<std::endl;
2831        return false;
2832    }
2833
2834    unsigned int numChildrenOnEntry = group->getNumChildren();
2835
2836    typedef std::pair< osg::BoundingBox, osg::ref_ptr<osg::Group> > BoxGroupPair;
2837    typedef std::vector< BoxGroupPair > Boxes;
2838    Boxes boxes;
2839    boxes.push_back( BoxGroupPair(bb,new osg::Group) );
2840
2841    // divide up on each axis
2842    if (xAxis)
2843    {
2844        unsigned int numCellsToDivide=boxes.size();
2845        for(unsigned int i=0;i<numCellsToDivide;++i)
2846        {
2847            osg::BoundingBox& orig_cell = boxes[i].first;
2848            osg::BoundingBox new_cell = orig_cell;
2849
2850            float xCenter = (orig_cell.xMin()+orig_cell.xMax())*0.5f;
2851            orig_cell.xMax() = xCenter;
2852            new_cell.xMin() = xCenter;
2853
2854            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2855        }
2856    }
2857
2858    if (yAxis)
2859    {
2860        unsigned int numCellsToDivide=boxes.size();
2861        for(unsigned int i=0;i<numCellsToDivide;++i)
2862        {
2863            osg::BoundingBox& orig_cell = boxes[i].first;
2864            osg::BoundingBox new_cell = orig_cell;
2865
2866            float yCenter = (orig_cell.yMin()+orig_cell.yMax())*0.5f;
2867            orig_cell.yMax() = yCenter;
2868            new_cell.yMin() = yCenter;
2869
2870            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2871        }
2872    }
2873
2874    if (zAxis)
2875    {
2876        unsigned int numCellsToDivide=boxes.size();
2877        for(unsigned int i=0;i<numCellsToDivide;++i)
2878        {
2879            osg::BoundingBox& orig_cell = boxes[i].first;
2880            osg::BoundingBox new_cell = orig_cell;
2881
2882            float zCenter = (orig_cell.zMin()+orig_cell.zMax())*0.5f;
2883            orig_cell.zMax() = zCenter;
2884            new_cell.zMin() = zCenter;
2885
2886            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2887        }
2888    }
2889
2890
2891    // create the groups to drop the children into
2892
2893
2894    // bin each child into associated bb group
2895    typedef std::vector< osg::ref_ptr<osg::Node> > NodeList;
2896    NodeList unassignedList;
2897    for(i=0;i<group->getNumChildren();++i)
2898    {
2899        bool assigned = false;
2900        osg::Vec3 center = group->getChild(i)->getBound().center();
2901        for(Boxes::iterator itr=boxes.begin();
2902            itr!=boxes.end() && !assigned;
2903            ++itr)
2904        {
2905            if (itr->first.contains(center))
2906            {
2907                // move child from main group into bb group.
2908                (itr->second)->addChild(group->getChild(i));
2909                assigned = true;
2910            }
2911        }
2912        if (!assigned)
2913        {
2914            unassignedList.push_back(group->getChild(i));
2915        }
2916    }
2917
2918
2919    // now transfer nodes across, by :
2920    //      first removing from the original group,
2921    //      add in the bb groups
2922    //      add then the unassigned children.
2923
2924
2925    // first removing from the original group,
2926    group->removeChildren(0,group->getNumChildren());
2927
2928    // add in the bb groups
2929    typedef std::vector< osg::ref_ptr<osg::Group> > GroupList;
2930    GroupList groupsToDivideList;
2931    for(Boxes::iterator itr=boxes.begin();
2932        itr!=boxes.end();
2933        ++itr)
2934    {
2935        // move child from main group into bb group.
2936        osg::Group* bb_group = (itr->second).get();
2937        if (bb_group->getNumChildren()>0)
2938        {
2939            if (bb_group->getNumChildren()==1)
2940            {
2941                group->addChild(bb_group->getChild(0));
2942            }
2943            else
2944            {
2945                group->addChild(bb_group);
2946                if (bb_group->getNumChildren()>maxNumTreesPerCell)
2947                {
2948                    groupsToDivideList.push_back(bb_group);
2949                }
2950            }
2951        }
2952    }
2953
2954
2955    // add then the unassigned children.
2956    for(NodeList::iterator nitr=unassignedList.begin();
2957        nitr!=unassignedList.end();
2958        ++nitr)
2959    {
2960        group->addChild(nitr->get());
2961    }
2962
2963    // now call divide on all groups that require it.
2964    for(GroupList::iterator gitr=groupsToDivideList.begin();
2965        gitr!=groupsToDivideList.end();
2966        ++gitr)
2967    {
2968        divide(gitr->get(),maxNumTreesPerCell);
2969    }
2970
2971    return (numChildrenOnEntry<group->getNumChildren());
2972
2973}
2974
2975bool Optimizer::SpatializeGroupsVisitor::divide(osg::Geode* geode, unsigned int maxNumTreesPerCell)
2976{
2977
2978    if (geode->getNumDrawables()<=maxNumTreesPerCell) return false;
2979
2980    // create the original box.
2981    osg::BoundingBox bb;
2982    unsigned int i;
2983    for(i=0; i<geode->getNumDrawables(); ++i)
2984    {
2985        bb.expandBy(geode->getDrawable(i)->getBound().center());
2986    }
2987
2988    float radius = bb.radius();
2989    float divide_distance = radius*0.7f;
2990    bool xAxis = (bb.xMax()-bb.xMin())>divide_distance;
2991    bool yAxis = (bb.yMax()-bb.yMin())>divide_distance;
2992    bool zAxis = (bb.zMax()-bb.zMin())>divide_distance;
2993
2994    OSG_INFO<<"INFO "<<geode->className()<<"  num drawables = "<<geode->getNumDrawables()<<"  xAxis="<<xAxis<<"  yAxis="<<yAxis<<"   zAxis="<<zAxis<<std::endl;
2995
2996    if (!xAxis && !yAxis && !zAxis)
2997    {
2998        OSG_INFO<<"  No axis to divide, stopping division."<<std::endl;
2999        return false;
3000    }
3001
3002    osg::Node::ParentList parents = geode->getParents();
3003    if (parents.empty())
3004    {
3005        OSG_INFO<<"  Cannot perform spatialize on root Geode, add a Group above it to allow subdivision."<<std::endl;
3006        return false;
3007    }
3008
3009    osg::ref_ptr<osg::Group> group = new osg::Group;
3010    group->setName(geode->getName());
3011    group->setStateSet(geode->getStateSet());
3012    for(i=0; i<geode->getNumDrawables(); ++i)
3013    {
3014        osg::Geode* newGeode = new osg::Geode;
3015        newGeode->addDrawable(geode->getDrawable(i));
3016        group->addChild(newGeode);
3017    }
3018
3019    divide(group.get(), maxNumTreesPerCell);
3020
3021    // keep reference around to prevent it being deleted.
3022    osg::ref_ptr<osg::Geode> keepRefGeode = geode;
3023
3024    for(osg::Node::ParentList::iterator itr = parents.begin();
3025        itr != parents.end();
3026        ++itr)
3027    {
3028        (*itr)->replaceChild(geode, group.get());
3029    }
3030
3031    return true;
3032}
3033
3034////////////////////////////////////////////////////////////////////////////////////////////
3035//
3036//  Duplicated subgraphs which are shared
3037//
3038
3039void Optimizer::CopySharedSubgraphsVisitor::apply(osg::Node& node)
3040{
3041    if (node.getNumParents()>1 && isOperationPermissibleForObject(&node))
3042    {
3043        _sharedNodeList.insert(&node);
3044    }
3045    traverse(node);
3046}
3047
3048void Optimizer::CopySharedSubgraphsVisitor::copySharedNodes()
3049{
3050    OSG_INFO<<"Shared node "<<_sharedNodeList.size()<<std::endl;
3051    for(SharedNodeList::iterator itr=_sharedNodeList.begin();
3052        itr!=_sharedNodeList.end();
3053        ++itr)
3054    {
3055        OSG_INFO<<"   No parents "<<(*itr)->getNumParents()<<std::endl;
3056        osg::Node* node = *itr;
3057        for(unsigned int i=node->getNumParents()-1;i>0;--i)
3058        {
3059            // create a clone.
3060            osg::ref_ptr<osg::Object> new_object = node->clone(osg::CopyOp::DEEP_COPY_NODES |
3061                                                          osg::CopyOp::DEEP_COPY_DRAWABLES);
3062            // cast it to node.
3063            osg::Node* new_node = dynamic_cast<osg::Node*>(new_object.get());
3064
3065            // replace the node by new_new
3066            if (new_node) node->getParent(i)->replaceChild(node,new_node);
3067        }
3068    }
3069}
3070
3071
3072////////////////////////////////////////////////////////////////////////////////////////////
3073//
3074//  Set the attributes of textures up.
3075//
3076
3077
3078void Optimizer::TextureVisitor::apply(osg::Node& node)
3079{
3080
3081    osg::StateSet* ss = node.getStateSet();
3082    if (ss &&
3083        isOperationPermissibleForObject(&node) &&
3084        isOperationPermissibleForObject(ss))
3085    {
3086        apply(*ss);
3087    }
3088
3089    traverse(node);
3090}
3091
3092void Optimizer::TextureVisitor::apply(osg::Geode& geode)
3093{
3094    if (!isOperationPermissibleForObject(&geode)) return;
3095
3096    osg::StateSet* ss = geode.getStateSet();
3097
3098    if (ss && isOperationPermissibleForObject(ss))
3099    {
3100        apply(*ss);
3101    }
3102
3103    for(unsigned int i=0;i<geode.getNumDrawables();++i)
3104    {
3105        osg::Drawable* drawable = geode.getDrawable(i);
3106        if (drawable)
3107        {
3108            ss = drawable->getStateSet();
3109            if (ss &&
3110               isOperationPermissibleForObject(drawable) &&
3111               isOperationPermissibleForObject(ss))
3112            {
3113                apply(*ss);
3114            }
3115        }
3116    }
3117}
3118
3119void Optimizer::TextureVisitor::apply(osg::StateSet& stateset)
3120{
3121    for(unsigned int i=0;i<stateset.getTextureAttributeList().size();++i)
3122    {
3123        osg::StateAttribute* sa = stateset.getTextureAttribute(i,osg::StateAttribute::TEXTURE);
3124        osg::Texture* texture = dynamic_cast<osg::Texture*>(sa);
3125        if (texture && isOperationPermissibleForObject(texture))
3126        {
3127            apply(*texture);
3128        }
3129    }
3130}
3131
3132void Optimizer::TextureVisitor::apply(osg::Texture& texture)
3133{
3134    if (_changeAutoUnRef)
3135    {
3136        unsigned numImageStreams = 0;
3137        for (unsigned int i=0; i<texture.getNumImages(); ++i)
3138        {
3139            osg::ImageStream* is = dynamic_cast<osg::ImageStream*>(texture.getImage(i));
3140            if (is) ++numImageStreams;
3141        }
3142
3143        if (numImageStreams==0)
3144        {
3145            texture.setUnRefImageDataAfterApply(_valueAutoUnRef);
3146        }
3147    }
3148
3149    if (_changeClientImageStorage)
3150    {
3151        texture.setClientStorageHint(_valueClientImageStorage);
3152    }
3153
3154    if (_changeAnisotropy)
3155    {
3156        texture.setMaxAnisotropy(_valueAnisotropy);
3157    }
3158
3159}
3160
3161////////////////////////////////////////////////////////////////////////////
3162// Merge geodes
3163////////////////////////////////////////////////////////////////////////////
3164
3165void Optimizer::MergeGeodesVisitor::apply(osg::Group& group)
3166{
3167    if (typeid(group)==typeid(osg::Group)) mergeGeodes(group);
3168    traverse(group);
3169}
3170
3171struct LessGeode
3172{
3173    bool operator() (const osg::Geode* lhs,const osg::Geode* rhs) const
3174    {
3175        if (lhs->getNodeMask()<rhs->getNodeMask()) return true;
3176        if (lhs->getNodeMask()>rhs->getNodeMask()) return false;
3177
3178        return (lhs->getStateSet()<rhs->getStateSet());
3179    }
3180};
3181
3182bool Optimizer::MergeGeodesVisitor::mergeGeodes(osg::Group& group)
3183{
3184    if (!isOperationPermissibleForObject(&group)) return false;
3185
3186    typedef std::vector< osg::Geode* >                      DuplicateList;
3187    typedef std::map<osg::Geode*,DuplicateList,LessGeode>   GeodeDuplicateMap;
3188
3189    unsigned int i;
3190    osg::NodeList children;
3191    children.resize(group.getNumChildren());
3192    for (i=0; i<group.getNumChildren(); ++i)
3193    {
3194        // keep a reference to this child so we can safely clear the group of all children
3195        // this is done so we don't have to do a search and remove from the list later on.
3196        children[i] = group.getChild(i);
3197    }
3198
3199    // remove all children
3200    group.removeChildren(0,group.getNumChildren());
3201
3202    GeodeDuplicateMap geodeDuplicateMap;
3203    for (i=0; i<children.size(); ++i)
3204    {
3205        osg::Node* child = children[i].get();
3206
3207        if (typeid(*child)==typeid(osg::Geode))
3208        {
3209            osg::Geode* geode = static_cast<osg::Geode*>(child);
3210            geodeDuplicateMap[geode].push_back(geode);
3211        }
3212        else
3213        {
3214            // not a geode so just add back into group as its a normal child
3215            group.addChild(child);
3216        }
3217    }
3218
3219    // if no geodes then just return.
3220    if (geodeDuplicateMap.empty()) return false;
3221
3222    OSG_INFO<<"mergeGeodes in group '"<<group.getName()<<"' "<<geodeDuplicateMap.size()<<std::endl;
3223
3224    // merge
3225    for(GeodeDuplicateMap::iterator itr=geodeDuplicateMap.begin();
3226        itr!=geodeDuplicateMap.end();
3227        ++itr)
3228    {
3229        if (itr->second.size()>1)
3230        {
3231            osg::Geode* lhs = itr->second[0];
3232
3233            // add geode back into group
3234            group.addChild(lhs);
3235
3236            for(DuplicateList::iterator dupItr=itr->second.begin()+1;
3237                dupItr!=itr->second.end();
3238                ++dupItr)
3239            {
3240                osg::Geode* rhs = *dupItr;
3241                mergeGeode(*lhs,*rhs);
3242            }
3243        }
3244        else
3245        {
3246            osg::Geode* lhs = itr->second[0];
3247
3248            // add geode back into group
3249            group.addChild(lhs);
3250        }
3251    }
3252
3253    return true;
3254}
3255
3256bool Optimizer::MergeGeodesVisitor::mergeGeode(osg::Geode& lhs, osg::Geode& rhs)
3257{
3258    for (unsigned int i=0; i<rhs.getNumDrawables(); ++i)
3259    {
3260        lhs.addDrawable(rhs.getDrawable(i));
3261    }
3262
3263    return true;
3264}
3265
3266
3267
3268////////////////////////////////////////////////////////////////////////////
3269// FlattenBillboardVisitor
3270////////////////////////////////////////////////////////////////////////////
3271void Optimizer::FlattenBillboardVisitor::reset()
3272{
3273    _billboards.clear();
3274}
3275
3276void Optimizer::FlattenBillboardVisitor::apply(osg::Billboard& billboard)
3277{
3278    _billboards[&billboard].push_back(getNodePath());
3279}
3280
3281void Optimizer::FlattenBillboardVisitor::process()
3282{
3283    for(BillboardNodePathMap::iterator itr = _billboards.begin();
3284        itr != _billboards.end();
3285        ++itr)
3286    {
3287        bool mergeAcceptable = true;
3288
3289        osg::ref_ptr<osg::Billboard> billboard = itr->first;
3290
3291        NodePathList& npl = itr->second;
3292        osg::Group* mainGroup = 0;
3293        if (npl.size()>1)
3294        {
3295            for(NodePathList::iterator nitr = npl.begin();
3296                nitr != npl.end();
3297                ++nitr)
3298            {
3299                osg::NodePath& np = *nitr;
3300                if (np.size()>=3)
3301                {
3302                    osg::Group* group = dynamic_cast<osg::Group*>(np[np.size()-3]);
3303                    if (mainGroup==0) mainGroup = group;
3304
3305                    osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(np[np.size()-2]);
3306
3307                    if (group == mainGroup &&
3308                        np[np.size()-1]==billboard.get() &&
3309                        mt && mt->getDataVariance()==osg::Object::STATIC &&
3310                        mt->getNumChildren()==1)
3311                    {
3312                        const osg::Matrix& m = mt->getMatrix();
3313                        mergeAcceptable = (m(0,0)==1.0 && m(0,1)==0.0 && m(0,2)==0.0 && m(0,3)==0.0 &&
3314                                           m(1,0)==0.0 && m(1,1)==1.0 && m(1,2)==0.0 && m(1,3)==0.0 &&
3315                                           m(2,0)==0.0 && m(2,1)==0.0 && m(2,2)==1.0 && m(2,3)==0.0 &&
3316                                           m(3,3)==1.0);
3317                    }
3318                    else
3319                    {
3320                       mergeAcceptable = false;
3321                    }
3322                }
3323                else
3324                {
3325                    mergeAcceptable = false;
3326                }
3327            }
3328        }
3329        else
3330        {
3331            mergeAcceptable = false;
3332        }
3333
3334        if (mergeAcceptable)
3335        {
3336            osg::Billboard* new_billboard = new osg::Billboard;
3337            new_billboard->setMode(billboard->getMode());
3338            new_billboard->setAxis(billboard->getAxis());
3339            new_billboard->setStateSet(billboard->getStateSet());
3340            new_billboard->setName(billboard->getName());
3341
3342            mainGroup->addChild(new_billboard);
3343
3344            typedef std::set<osg::MatrixTransform*> MatrixTransformSet;
3345            MatrixTransformSet mts;
3346
3347            for(NodePathList::iterator nitr = npl.begin();
3348                nitr != npl.end();
3349                ++nitr)
3350            {
3351                osg::NodePath& np = *nitr;
3352                osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(np[np.size()-2]);
3353                mts.insert(mt);
3354            }
3355
3356            for(MatrixTransformSet::iterator mitr = mts.begin();
3357                mitr != mts.end();
3358                ++mitr)
3359            {
3360                osg::MatrixTransform* mt = *mitr;
3361                for(unsigned int i=0; i<billboard->getNumDrawables(); ++i)
3362                {
3363                    new_billboard->addDrawable(billboard->getDrawable(i),
3364                                               billboard->getPosition(i)*mt->getMatrix());
3365                }
3366                mainGroup->removeChild(mt);
3367            }
3368        }
3369    }
3370
3371}
3372
3373
3374
3375////////////////////////////////////////////////////////////////////////////
3376// TextureAtlasBuilder
3377////////////////////////////////////////////////////////////////////////////
3378
3379Optimizer::TextureAtlasBuilder::TextureAtlasBuilder():
3380    _maximumAtlasWidth(2048),
3381    _maximumAtlasHeight(2048),
3382    _margin(8)
3383{
3384}
3385
3386void Optimizer::TextureAtlasBuilder::reset()
3387{
3388    _sourceList.clear();
3389    _atlasList.clear();
3390}
3391
3392void Optimizer::TextureAtlasBuilder::setMaximumAtlasSize(int width, int height)
3393{
3394    _maximumAtlasWidth = width;
3395    _maximumAtlasHeight = height;
3396}
3397
3398void Optimizer::TextureAtlasBuilder::setMargin(int margin)
3399{
3400    _margin = margin;
3401}
3402
3403void Optimizer::TextureAtlasBuilder::addSource(const osg::Image* image)
3404{
3405    if (!getSource(image)) _sourceList.push_back(new Source(image));
3406}
3407
3408void Optimizer::TextureAtlasBuilder::addSource(const osg::Texture2D* texture)
3409{
3410    if (!getSource(texture)) _sourceList.push_back(new Source(texture));
3411}
3412
3413
3414void Optimizer::TextureAtlasBuilder::completeRow(unsigned int indexAtlas)
3415{
3416    AtlasList::iterator aitr = _atlasList.begin() + indexAtlas;
3417    //SourceList::iterator sitr = _sourceList.begin() + indexSource;
3418    Atlas * atlas = aitr->get();
3419    if(atlas->_indexFirstOfRow < atlas->_sourceList.size())
3420    {
3421        //Try to fill the row with smaller images.
3422        int x_max = atlas->_width  - _margin;
3423        int y_max = atlas->_height - _margin;
3424        //int x_max = atlas->_maximumAtlasWidth  - _margin;
3425        //int y_max = atlas->_maximumAtlasHeight - _margin;
3426
3427        // Fill last Row
3428        for(SourceList::iterator sitr3 = _sourceList.begin(); sitr3 != _sourceList.end(); ++sitr3)
3429        {
3430            int x_min = atlas->_x + _margin;
3431            int y_min = atlas->_y + _margin;
3432            if (y_min >= y_max || x_min >= x_max) continue;
3433
3434            Source * source = sitr3->get();
3435            if (source->_atlas || atlas->_image->getPixelFormat() != source->_image->getPixelFormat() ||
3436                atlas->_image->getDataType() != source->_image->getDataType())
3437            {
3438                continue;
3439            }
3440
3441            int image_s = source->_image->s();
3442            int image_t = source->_image->t();
3443            if (x_min + image_s <= x_max && y_min + image_t <= y_max)        // Test if the image can fit in the empty space.
3444            {
3445                source->_x = x_min;
3446                source->_y = y_min;
3447                //assert(source->_x + source->_image->s()+_margin <= atlas->_maximumAtlasWidth );        // "+_margin" and not "+2*_margin" because _x already takes the margin into account
3448                //assert(source->_y + source->_image->t()+_margin <= atlas->_maximumAtlasHeight);
3449                //assert(source->_x >= _margin);
3450                //assert(source->_y >= _margin);
3451                atlas->_x += image_s + 2*_margin;
3452                //assert(atlas->_x <= atlas->_maximumAtlasWidth);
3453                source->_atlas = atlas;
3454                atlas->_sourceList.push_back(source);
3455            }
3456        }
3457
3458        // Fill the last column
3459        SourceList srcListTmp;
3460        for(SourceList::iterator sitr4 = atlas->_sourceList.begin() + atlas->_indexFirstOfRow;
3461            sitr4 != atlas->_sourceList.end(); ++sitr4)
3462        {
3463            Source * srcAdded = sitr4->get();
3464            int y_min = srcAdded->_y + srcAdded->_image->t() + 2 * _margin;
3465            int x_min = srcAdded->_x;
3466            int x_max = x_min + srcAdded->_image->s();        // Hides upper block's x_max
3467            if (y_min >= y_max || x_min >= x_max) continue;
3468
3469            Source * maxWidthSource = NULL;
3470            for(SourceList::iterator sitr2 = _sourceList.begin(); sitr2 != _sourceList.end(); ++sitr2)
3471            {
3472                Source * source = sitr2->get();
3473                if (source->_atlas || atlas->_image->getPixelFormat() != source->_image->getPixelFormat() ||
3474                    atlas->_image->getDataType() != source->_image->getDataType())
3475                {
3476                    continue;
3477                }
3478                int image_s = source->_image->s();
3479                int image_t = source->_image->t();
3480                if(x_min + image_s <= x_max && y_min + image_t <= y_max)        // Test if the image can fit in the empty space.
3481                {
3482                    if (maxWidthSource == NULL || maxWidthSource->_image->s() < source->_image->s())
3483                    {
3484                        maxWidthSource = source; //Keep the maximum width for source.
3485                    }
3486                }
3487            }
3488            if (maxWidthSource)
3489            {
3490                // Add the source with the max width to the atlas
3491                maxWidthSource->_x = x_min;
3492                maxWidthSource->_y = y_min;
3493                maxWidthSource->_atlas = atlas;
3494                srcListTmp.push_back(maxWidthSource); //Store the mawWidth source in the temporary vector.
3495            }
3496        }
3497        for(SourceList::iterator itTmp = srcListTmp.begin(); itTmp != srcListTmp.end(); ++itTmp)
3498        {
3499            //Add the sources to the general list (wasn't possible in the loop using the iterator on the same list)
3500            atlas->_sourceList.push_back(*itTmp);
3501        }
3502        atlas->_indexFirstOfRow = atlas->_sourceList.size();
3503    }
3504}
3505
3506void Optimizer::TextureAtlasBuilder::buildAtlas()
3507{
3508    std::sort(_sourceList.begin(), _sourceList.end(), CompareSrc());        // Sort using the height of images
3509    _atlasList.clear();
3510    for(SourceList::iterator sitr = _sourceList.begin();
3511        sitr != _sourceList.end();
3512        ++sitr)
3513    {
3514        Source * source = sitr->get();
3515        if (!source->_atlas && source->suitableForAtlas(_maximumAtlasWidth,_maximumAtlasHeight,_margin))
3516        {
3517            bool addedSourceToAtlas = false;
3518            for(AtlasList::iterator aitr = _atlasList.begin();
3519                aitr != _atlasList.end() && !addedSourceToAtlas;
3520                ++aitr)
3521            {
3522                if(!(*aitr)->_image ||
3523                    ((*aitr)->_image->getPixelFormat() == (*sitr)->_image->getPixelFormat() &&
3524                    (*aitr)->_image->getPacking() == (*sitr)->_image->getPacking()))
3525                {
3526                    OSG_INFO<<"checking source "<<source->_image->getFileName()<<" to see it it'll fit in atlas "<<aitr->get()<<std::endl;
3527                    Optimizer::TextureAtlasBuilder::Atlas::FitsIn fitsIn = (*aitr)->doesSourceFit(source);
3528                    if (fitsIn == Optimizer::TextureAtlasBuilder::Atlas::FITS_IN_CURRENT_ROW)
3529                    {
3530                        addedSourceToAtlas = true;
3531                        (*aitr)->addSource(source); // Add in the currentRow.
3532                    }
3533                    else if(fitsIn == Optimizer::TextureAtlasBuilder::Atlas::IN_NEXT_ROW)
3534                    {
3535                        completeRow(aitr - _atlasList.begin()); //Fill Empty spaces.
3536                        addedSourceToAtlas = true;
3537                        (*aitr)->addSource(source); // Add the source in the new row.
3538                    }
3539                    else
3540                    {
3541                        completeRow(aitr - _atlasList.begin()); //Fill Empty spaces before creating a new atlas.
3542                    }
3543                }
3544            }
3545
3546            if (!addedSourceToAtlas)
3547            {
3548                OSG_INFO<<"creating new Atlas for "<<source->_image->getFileName()<<std::endl;
3549
3550                osg::ref_ptr<Atlas> atlas = new Atlas(_maximumAtlasWidth,_maximumAtlasHeight,_margin);
3551                _atlasList.push_back(atlas);
3552                if (!source->_atlas) atlas->addSource(source);
3553            }
3554        }
3555    }
3556
3557    // build the atlas which are suitable for use, and discard the rest.
3558    AtlasList activeAtlasList;
3559    for(AtlasList::iterator aitr = _atlasList.begin();
3560        aitr != _atlasList.end();
3561        ++aitr)
3562    {
3563        osg::ref_ptr<Atlas> atlas = *aitr;
3564
3565        if (atlas->_sourceList.size()==1)
3566        {
3567            // no point building an atlas with only one entry
3568            // so disconnect the source.
3569            Source * source = atlas->_sourceList[0].get();
3570            source->_atlas = 0;
3571            atlas->_sourceList.clear();
3572        }
3573
3574        if (!(atlas->_sourceList.empty()))
3575        {
3576            std::stringstream ostr;
3577            ostr<<"atlas_"<<activeAtlasList.size()<<".rgb";
3578            atlas->_image->setFileName(ostr.str());
3579            activeAtlasList.push_back(atlas);
3580            atlas->clampToNearestPowerOfTwoSize();
3581            atlas->copySources();
3582        }
3583    }
3584    // keep only the active atlas'
3585    _atlasList.swap(activeAtlasList);
3586
3587}
3588
3589osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(unsigned int i)
3590{
3591    Source* source = _sourceList[i].get();
3592    Atlas* atlas = source ? source->_atlas : 0;
3593    return atlas ? atlas->_image.get() : 0;
3594}
3595
3596osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(unsigned int i)
3597{
3598    Source* source = _sourceList[i].get();
3599    Atlas* atlas = source ? source->_atlas : 0;
3600    return atlas ? atlas->_texture.get() : 0;
3601}
3602
3603osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(unsigned int i)
3604{
3605    Source* source = _sourceList[i].get();
3606    return source ? source->computeTextureMatrix() : osg::Matrix();
3607}
3608
3609osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(const osg::Image* image)
3610{
3611    Source* source = getSource(image);
3612    Atlas* atlas = source ? source->_atlas : 0;
3613    return atlas ? atlas->_image.get() : 0;
3614}
3615
3616osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(const osg::Image* image)
3617{
3618    Source* source = getSource(image);
3619    Atlas* atlas = source ? source->_atlas : 0;
3620    return atlas ? atlas->_texture.get() : 0;
3621}
3622
3623osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(const osg::Image* image)
3624{
3625    Source* source = getSource(image);
3626    return source ? source->computeTextureMatrix() : osg::Matrix();
3627}
3628
3629osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(const osg::Texture2D* texture)
3630{
3631    Source* source = getSource(texture);
3632    Atlas* atlas = source ? source->_atlas : 0;
3633    return atlas ? atlas->_image.get() : 0;
3634}
3635
3636osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(const osg::Texture2D* texture)
3637{
3638    Source* source = getSource(texture);
3639    Atlas* atlas = source ? source->_atlas : 0;
3640    return atlas ? atlas->_texture.get() : 0;
3641}
3642
3643osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(const osg::Texture2D* texture)
3644{
3645    Source* source = getSource(texture);
3646    return source ? source->computeTextureMatrix() : osg::Matrix();
3647}
3648
3649Optimizer::TextureAtlasBuilder::Source* Optimizer::TextureAtlasBuilder::getSource(const osg::Image* image)
3650{
3651    for(SourceList::iterator itr = _sourceList.begin();
3652        itr != _sourceList.end();
3653        ++itr)
3654    {
3655        if ((*itr)->_image == image) return itr->get();
3656    }
3657    return 0;
3658}
3659
3660Optimizer::TextureAtlasBuilder::Source* Optimizer::TextureAtlasBuilder::getSource(const osg::Texture2D* texture)
3661{
3662    for(SourceList::iterator itr = _sourceList.begin();
3663        itr != _sourceList.end();
3664        ++itr)
3665    {
3666        if ((*itr)->_texture == texture) return itr->get();
3667    }
3668    return 0;
3669}
3670
3671bool Optimizer::TextureAtlasBuilder::Source::suitableForAtlas(int maximumAtlasWidth, int maximumAtlasHeight, int margin)
3672{
3673    if (!_image) return false;
3674
3675    // size too big?
3676    if (_image->s()+margin*2 > maximumAtlasWidth) return false;
3677    if (_image->t()+margin*2 > maximumAtlasHeight) return false;
3678
3679    switch(_image->getPixelFormat())
3680    {
3681        case(GL_COMPRESSED_ALPHA_ARB):
3682        case(GL_COMPRESSED_INTENSITY_ARB):
3683        case(GL_COMPRESSED_LUMINANCE_ALPHA_ARB):
3684        case(GL_COMPRESSED_LUMINANCE_ARB):
3685        case(GL_COMPRESSED_RGBA_ARB):
3686        case(GL_COMPRESSED_RGB_ARB):
3687        case(GL_COMPRESSED_RGB_S3TC_DXT1_EXT):
3688        case(GL_COMPRESSED_RGBA_S3TC_DXT1_EXT):
3689        case(GL_COMPRESSED_RGBA_S3TC_DXT3_EXT):
3690        case(GL_COMPRESSED_RGBA_S3TC_DXT5_EXT):
3691            // can't handle compressed textures inside an atlas
3692            return false;
3693        default:
3694            break;
3695    }
3696
3697    if ((_image->getPixelSizeInBits() % 8) != 0)
3698    {
3699        // pixel size not byte aligned so report as not suitable to prevent other atlas code from having problems with byte boundaries.
3700        return false;
3701    }
3702    if (_texture.valid())
3703    {
3704
3705        if (_texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
3706            _texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR)
3707        {
3708            // can't support repeating textures in texture atlas
3709            return false;
3710        }
3711
3712        if (_texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
3713            _texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR)
3714        {
3715            // can't support repeating textures in texture atlas
3716            return false;
3717        }
3718
3719        if (_texture->getReadPBuffer()!=0)
3720        {
3721            // pbuffer textures not suitable
3722            return false;
3723        }
3724    }
3725
3726    return true;
3727}
3728
3729osg::Matrix Optimizer::TextureAtlasBuilder::Source::computeTextureMatrix() const
3730{
3731    if (!_atlas) return osg::Matrix();
3732    if (!_image) return osg::Matrix();
3733    if (!(_atlas->_image)) return osg::Matrix();
3734
3735    typedef osg::Matrix::value_type Float;
3736    return osg::Matrix::scale(Float(_image->s())/Float(_atlas->_image->s()), Float(_image->t())/Float(_atlas->_image->t()), 1.0)*
3737           osg::Matrix::translate(Float(_x)/Float(_atlas->_image->s()), Float(_y)/Float(_atlas->_image->t()), 0.0);
3738}
3739
3740Optimizer::TextureAtlasBuilder::Atlas::FitsIn Optimizer::TextureAtlasBuilder::Atlas::doesSourceFit(Source* source)
3741{
3742    // does the source have a valid image?
3743    const osg::Image* sourceImage = source->_image.get();
3744    if (!sourceImage) return DOES_NOT_FIT_IN_ANY_ROW;
3745
3746    // does pixel format match?
3747    if (_image.valid())
3748    {
3749        if (_image->getPixelFormat() != sourceImage->getPixelFormat()) return DOES_NOT_FIT_IN_ANY_ROW;
3750        if (_image->getDataType() != sourceImage->getDataType()) return DOES_NOT_FIT_IN_ANY_ROW;
3751    }
3752
3753    const osg::Texture2D* sourceTexture = source->_texture.get();
3754    if (sourceTexture)
3755    {
3756        if (sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
3757            sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR)
3758        {
3759            // can't support repeating textures in texture atlas
3760            return DOES_NOT_FIT_IN_ANY_ROW;
3761        }
3762
3763        if (sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
3764            sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR)
3765        {
3766            // can't support repeating textures in texture atlas
3767            return DOES_NOT_FIT_IN_ANY_ROW;
3768        }
3769
3770        if (sourceTexture->getReadPBuffer()!=0)
3771        {
3772            // pbuffer textures not suitable
3773            return DOES_NOT_FIT_IN_ANY_ROW;
3774        }
3775
3776        if (_texture.valid())
3777        {
3778
3779            bool sourceUsesBorder = sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::CLAMP_TO_BORDER ||
3780                                    sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::CLAMP_TO_BORDER;
3781
3782            bool atlasUsesBorder = sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::CLAMP_TO_BORDER ||
3783                                   sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::CLAMP_TO_BORDER;
3784
3785            if (sourceUsesBorder!=atlasUsesBorder)
3786            {
3787                // border wrapping does not match
3788                return DOES_NOT_FIT_IN_ANY_ROW;
3789            }
3790
3791            if (sourceUsesBorder)
3792            {
3793                // border colours don't match
3794                if (_texture->getBorderColor() != sourceTexture->getBorderColor()) return DOES_NOT_FIT_IN_ANY_ROW;
3795            }
3796
3797            if (_texture->getFilter(osg::Texture2D::MIN_FILTER) != sourceTexture->getFilter(osg::Texture2D::MIN_FILTER))
3798            {
3799                // inconsitent min filters
3800                return DOES_NOT_FIT_IN_ANY_ROW;
3801            }
3802
3803            if (_texture->getFilter(osg::Texture2D::MAG_FILTER) != sourceTexture->getFilter(osg::Texture2D::MAG_FILTER))
3804            {
3805                // inconsitent mag filters
3806                return DOES_NOT_FIT_IN_ANY_ROW;
3807            }
3808
3809            if (_texture->getMaxAnisotropy() != sourceTexture->getMaxAnisotropy())
3810            {
3811                // anisotropy different.
3812                return DOES_NOT_FIT_IN_ANY_ROW;
3813            }
3814
3815            if (_texture->getInternalFormat() != sourceTexture->getInternalFormat())
3816            {
3817                // internal formats inconistent
3818                return DOES_NOT_FIT_IN_ANY_ROW;
3819            }
3820
3821            if (_texture->getShadowCompareFunc() != sourceTexture->getShadowCompareFunc())
3822            {
3823                // shadow functions inconsitent
3824                return DOES_NOT_FIT_IN_ANY_ROW;
3825            }
3826
3827            if (_texture->getShadowTextureMode() != sourceTexture->getShadowTextureMode())
3828            {
3829                // shadow texture mode inconsitent
3830                return DOES_NOT_FIT_IN_ANY_ROW;
3831            }
3832
3833            if (_texture->getShadowAmbient() != sourceTexture->getShadowAmbient())
3834            {
3835                // shadow ambient inconsitent
3836                return DOES_NOT_FIT_IN_ANY_ROW;
3837            }
3838        }
3839    }
3840
3841    if (sourceImage->s() + 2*_margin > _maximumAtlasWidth)
3842    {
3843        // image too big for Atlas
3844        return DOES_NOT_FIT_IN_ANY_ROW;
3845    }
3846
3847    if (sourceImage->t() + 2*_margin > _maximumAtlasHeight)
3848    {
3849        // image too big for Atlas
3850        return DOES_NOT_FIT_IN_ANY_ROW;
3851    }
3852
3853    if ((_y + sourceImage->t() + 2*_margin) > _maximumAtlasHeight)
3854    {
3855        // image doesn't have up space in height axis.
3856        return DOES_NOT_FIT_IN_ANY_ROW;
3857    }
3858
3859    // does the source fit in the current row?
3860    if ((_x + sourceImage->s() + 2*_margin) <= _maximumAtlasWidth)
3861    {
3862        // yes it fits :-)
3863        OSG_INFO<<"Fits in current row"<<std::endl;
3864        return FITS_IN_CURRENT_ROW;
3865    }
3866
3867    // does the source fit in the new row up?
3868    if ((_height + sourceImage->t() + 2*_margin) <= _maximumAtlasHeight)
3869    {
3870        // yes it fits :-)
3871        OSG_INFO<<"Fits in next row"<<std::endl;
3872        return IN_NEXT_ROW;
3873    }
3874
3875    // no space for the texture
3876    return DOES_NOT_FIT_IN_ANY_ROW;
3877}
3878
3879bool Optimizer::TextureAtlasBuilder::Atlas::addSource(Source* source)
3880{
3881    // double check source is compatible
3882    if (!doesSourceFit(source))
3883    {
3884        OSG_INFO<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<this<<std::endl;
3885        return false;
3886    }
3887    const osg::Image* sourceImage = source->_image.get();
3888    const osg::Texture2D* sourceTexture = source->_texture.get();
3889
3890    if (!_image)
3891    {
3892        // need to create an image of the same pixel format to store the atlas in
3893        _image = new osg::Image;
3894        _image->setPacking(sourceImage->getPacking());
3895        _image->setPixelFormat(sourceImage->getPixelFormat());
3896        _image->setDataType(sourceImage->getDataType());
3897    }
3898
3899    if (!_texture && sourceTexture)
3900    {
3901        _texture = new osg::Texture2D(_image.get());
3902
3903        _texture->setWrap(osg::Texture2D::WRAP_S, sourceTexture->getWrap(osg::Texture2D::WRAP_S));
3904        _texture->setWrap(osg::Texture2D::WRAP_T, sourceTexture->getWrap(osg::Texture2D::WRAP_T));
3905
3906        _texture->setBorderColor(sourceTexture->getBorderColor());
3907        _texture->setBorderWidth(0);
3908
3909        _texture->setFilter(osg::Texture2D::MIN_FILTER, sourceTexture->getFilter(osg::Texture2D::MIN_FILTER));
3910        _texture->setFilter(osg::Texture2D::MAG_FILTER, sourceTexture->getFilter(osg::Texture2D::MAG_FILTER));
3911
3912        _texture->setMaxAnisotropy(sourceTexture->getMaxAnisotropy());
3913
3914        _texture->setInternalFormat(sourceTexture->getInternalFormat());
3915
3916        _texture->setShadowCompareFunc(sourceTexture->getShadowCompareFunc());
3917        _texture->setShadowTextureMode(sourceTexture->getShadowTextureMode());
3918        _texture->setShadowAmbient(sourceTexture->getShadowAmbient());
3919
3920    }
3921
3922    // now work out where to fit it, first try current row.
3923    if ((_x + sourceImage->s() + 2*_margin) <= _maximumAtlasWidth)
3924    {
3925        // yes it fits, so add the source to the atlas's list of sources it contains
3926        _sourceList.push_back(source);
3927
3928        OSG_INFO<<"current row insertion, source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3929
3930        // set up the source so it knows where it is in the atlas
3931        source->_x = _x + _margin;
3932        source->_y = _y + _margin;
3933        source->_atlas = this;
3934
3935        // move the atlas' cursor along to the right
3936        _x += sourceImage->s() + 2*_margin;
3937
3938        if (_x > _width) _width = _x;
3939
3940        int localTop = _y + sourceImage->t() + 2*_margin;
3941        if ( localTop > _height) _height = localTop;
3942
3943        return true;
3944    }
3945
3946    // does the source fit in the new row up?
3947    if ((_height + sourceImage->t() + 2*_margin) <= _maximumAtlasHeight)
3948    {
3949        // now row so first need to reset the atlas cursor
3950        _x = 0;
3951        _y = _height;
3952
3953        // yes it fits, so add the source to the atlas' list of sources it contains
3954        _sourceList.push_back(source);
3955
3956        OSG_INFO<<"next row insertion, source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3957
3958        // set up the source so it knows where it is in the atlas
3959        source->_x = _x + _margin;
3960        source->_y = _y + _margin;
3961        source->_atlas = this;
3962
3963        // move the atlas' cursor along to the right
3964        _x += sourceImage->s() + 2*_margin;
3965
3966        if (_x > _width) _width = _x;
3967
3968        _height = _y + sourceImage->t() + 2*_margin;
3969
3970        OSG_INFO<<"source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3971
3972        return true;
3973    }
3974
3975    OSG_INFO<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<this<<std::endl;
3976
3977    // shouldn't get here, unless doesSourceFit isn't working...
3978    return false;
3979}
3980
3981void Optimizer::TextureAtlasBuilder::Atlas::clampToNearestPowerOfTwoSize()
3982{
3983    int w = 1;
3984    while (w<_width) w *= 2;
3985
3986    int h = 1;
3987    while (h<_height) h *= 2;
3988
3989    OSG_INFO<<"Clamping "<<_width<<", "<<_height<<" to "<<w<<","<<h<<std::endl;
3990
3991    _width = w;
3992    _height = h;
3993}
3994
3995
3996void Optimizer::TextureAtlasBuilder::Atlas::copySources()
3997{
3998    GLenum pixelFormat = _image->getPixelFormat();
3999    GLenum dataType = _image->getDataType();
4000    GLenum packing = _image->getPacking();
4001    OSG_INFO<<"Allocated to "<<_width<<","<<_height<<std::endl;
4002    _image->allocateImage(_width,_height,1,
4003                          pixelFormat, dataType,
4004                          packing);
4005
4006    {
4007        // clear memory
4008        unsigned int size = _image->getTotalSizeInBytes();
4009        unsigned char* str = _image->data();
4010        for(unsigned int i=0; i<size; ++i) *(str++) = 0;
4011    }
4012
4013    OSG_INFO<<"Atlas::copySources() "<<std::endl;
4014
4015    for(SourceList::iterator itr = _sourceList.begin();
4016        itr !=_sourceList.end();
4017        ++itr)
4018    {
4019        Source* source = itr->get();
4020        Atlas* atlas = source->_atlas;
4021
4022        if (atlas == this)
4023        {
4024            OSG_INFO<<"Copying image "<<source->_image->getFileName()<<" to "<<source->_x<<" ,"<<source->_y<<std::endl;
4025            OSG_INFO<<"        image size "<<source->_image->s()<<","<<source->_image->t()<<std::endl;
4026
4027            const osg::Image* sourceImage = source->_image.get();
4028            osg::Image* atlasImage = atlas->_image.get();
4029            //assert(sourceImage->getPacking() == atlasImage->getPacking()); //Test if packings are equals.
4030            unsigned int rowSize = sourceImage->getRowSizeInBytes();
4031            unsigned int pixelSizeInBits = sourceImage->getPixelSizeInBits();
4032            unsigned int pixelSizeInBytes = pixelSizeInBits/8;
4033            unsigned int marginSizeInBytes = pixelSizeInBytes*_margin;
4034
4035            //assert(atlas->_width  == static_cast<int>(atlasImage->s()));
4036            //assert(atlas->_height == static_cast<int>(atlasImage->t()));
4037            //assert(source->_x + static_cast<int>(source->_image->s())+_margin <= static_cast<int>(atlas->_image->s()));        // "+_margin" and not "+2*_margin" because _x already takes the margin into account
4038            //assert(source->_y + static_cast<int>(source->_image->t())+_margin <= static_cast<int>(atlas->_image->t()));
4039            //assert(source->_x >= _margin);
4040            //assert(source->_y >= _margin);
4041            int x = source->_x;
4042            int y = source->_y;
4043
4044            int t;
4045            for(t=0; t<sourceImage->t(); ++t, ++y)
4046            {
4047                unsigned char* destPtr = atlasImage->data(x, y);
4048                const unsigned char* sourcePtr = sourceImage->data(0, t);
4049                for(unsigned int i=0; i<rowSize; i++)
4050                {
4051                    *(destPtr++) = *(sourcePtr++);
4052                }
4053            }
4054
4055            // copy top row margin
4056            y = source->_y + sourceImage->t();
4057            int m;
4058            for(m=0; m<_margin; ++m, ++y)
4059            {
4060                unsigned char* destPtr = atlasImage->data(x, y);
4061                const unsigned char* sourcePtr = sourceImage->data(0, sourceImage->t()-1);
4062                for(unsigned int i=0; i<rowSize; i++)
4063                {
4064                    *(destPtr++) = *(sourcePtr++);
4065                }
4066
4067            }
4068
4069
4070
4071            // copy bottom row margin
4072            y = source->_y-1;
4073            for(m=0; m<_margin; ++m, --y)
4074            {
4075                unsigned char* destPtr = atlasImage->data(x, y);
4076                const unsigned char* sourcePtr = sourceImage->data(0, 0);
4077                for(unsigned int i=0; i<rowSize; i++)
4078                {
4079                    *(destPtr++) = *(sourcePtr++);
4080                }
4081
4082            }
4083
4084            // copy left column margin
4085            y = source->_y;
4086            for(t=0; t<sourceImage->t(); ++t, ++y)
4087            {
4088                x = source->_x-1;
4089                for(m=0; m<_margin; ++m, --x)
4090                {
4091                    unsigned char* destPtr = atlasImage->data(x, y);
4092                    const unsigned char* sourcePtr = sourceImage->data(0, t);
4093                    for(unsigned int i=0; i<pixelSizeInBytes; i++)
4094                    {
4095                        *(destPtr++) = *(sourcePtr++);
4096                    }
4097                }
4098            }
4099
4100            // copy right column margin
4101            y = source->_y;
4102            for(t=0; t<sourceImage->t(); ++t, ++y)
4103            {
4104                x = source->_x + sourceImage->s();
4105                for(m=0; m<_margin; ++m, ++x)
4106                {
4107                    unsigned char* destPtr = atlasImage->data(x, y);
4108                    const unsigned char* sourcePtr = sourceImage->data(sourceImage->s()-1, t);
4109                    for(unsigned int i=0; i<pixelSizeInBytes; i++)
4110                    {
4111                        *(destPtr++) = *(sourcePtr++);
4112                    }
4113                }
4114            }
4115
4116            // copy top left corner margin
4117            y = source->_y + sourceImage->t();
4118            for(m=0; m<_margin; ++m, ++y)
4119            {
4120                unsigned char* destPtr = atlasImage->data(source->_x - _margin, y);
4121                unsigned char* sourcePtr = atlasImage->data(source->_x - _margin, y-1); // copy from row below
4122                for(unsigned int i=0; i<marginSizeInBytes; i++)
4123                {
4124                    *(destPtr++) = *(sourcePtr++);
4125                }
4126            }
4127
4128            // copy top right corner margin
4129            y = source->_y + sourceImage->t();
4130            for(m=0; m<_margin; ++m, ++y)
4131            {
4132                unsigned char* destPtr = atlasImage->data(source->_x + sourceImage->s(), y);
4133                unsigned char* sourcePtr = atlasImage->data(source->_x + sourceImage->s(), y-1); // copy from row below
4134                for(unsigned int i=0; i<marginSizeInBytes; i++)
4135                {
4136                    *(destPtr++) = *(sourcePtr++);
4137                }
4138            }
4139
4140            // copy bottom left corner margin
4141            y = source->_y - 1;
4142            for(m=0; m<_margin; ++m, --y)
4143            {
4144                unsigned char* destPtr = atlasImage->data(source->_x - _margin, y);
4145                unsigned char* sourcePtr = atlasImage->data(source->_x - _margin, y+1); // copy from row below
4146                for(unsigned int i=0; i<marginSizeInBytes; i++)
4147                {
4148                    *(destPtr++) = *(sourcePtr++);
4149                }
4150            }
4151
4152            // copy bottom right corner margin
4153            y = source->_y - 1;
4154            for(m=0; m<_margin; ++m, --y)
4155            {
4156                unsigned char* destPtr = atlasImage->data(source->_x + sourceImage->s(), y);
4157                unsigned char* sourcePtr = atlasImage->data(source->_x + sourceImage->s(), y+1); // copy from row below
4158                for(unsigned int i=0; i<marginSizeInBytes; i++)
4159                {
4160                    *(destPtr++) = *(sourcePtr++);
4161                }
4162            }
4163
4164        }
4165    }
4166}
4167
4168
4169void Optimizer::TextureAtlasVisitor::reset()
4170{
4171    _statesetMap.clear();
4172    _statesetStack.clear();
4173    _textures.clear();
4174    _builder.reset();
4175}
4176
4177bool Optimizer::TextureAtlasVisitor::pushStateSet(osg::StateSet* stateset)
4178{
4179    osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
4180
4181    // if no textures ignore
4182    if (tal.empty()) return false;
4183
4184    bool pushStateState = false;
4185
4186    // if already in stateset list ignore
4187    if (_statesetMap.count(stateset)>0)
4188    {
4189        pushStateState = true;
4190    }
4191    else
4192    {
4193        bool containsTexture2D = false;
4194        for(unsigned int unit=0; unit<tal.size(); ++unit)
4195        {
4196            osg::Texture2D* texture2D = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
4197            if (texture2D)
4198            {
4199                containsTexture2D = true;
4200                _textures.insert(texture2D);
4201            }
4202        }
4203
4204        if (containsTexture2D)
4205        {
4206            _statesetMap[stateset];
4207            pushStateState = true;
4208        }
4209    }
4210
4211    if (pushStateState)
4212    {
4213        _statesetStack.push_back(stateset);
4214    }
4215
4216
4217    return pushStateState;
4218}
4219
4220void Optimizer::TextureAtlasVisitor::popStateSet()
4221{
4222    _statesetStack.pop_back();
4223}
4224
4225void Optimizer::TextureAtlasVisitor::apply(osg::Node& node)
4226{
4227    bool pushedStateState = false;
4228
4229    osg::StateSet* ss = node.getStateSet();
4230    if (ss && ss->getDataVariance()==osg::Object::STATIC)
4231    {
4232        if (isOperationPermissibleForObject(&node) &&
4233            isOperationPermissibleForObject(ss))
4234        {
4235            pushedStateState = pushStateSet(ss);
4236        }
4237    }
4238
4239    traverse(node);
4240
4241    if (pushedStateState) popStateSet();
4242}
4243
4244void Optimizer::TextureAtlasVisitor::apply(osg::Geode& geode)
4245{
4246    if (!isOperationPermissibleForObject(&geode)) return;
4247
4248    osg::StateSet* ss = geode.getStateSet();
4249
4250
4251    bool pushedGeodeStateState = false;
4252
4253    if (ss && ss->getDataVariance()==osg::Object::STATIC)
4254    {
4255        if (isOperationPermissibleForObject(ss))
4256        {
4257            pushedGeodeStateState = pushStateSet(ss);
4258        }
4259    }
4260    for(unsigned int i=0;i<geode.getNumDrawables();++i)
4261    {
4262
4263        osg::Drawable* drawable = geode.getDrawable(i);
4264        if (drawable)
4265        {
4266            bool pushedDrawableStateState = false;
4267
4268            ss = drawable->getStateSet();
4269            if (ss && ss->getDataVariance()==osg::Object::STATIC)
4270            {
4271                if (isOperationPermissibleForObject(drawable) &&
4272                    isOperationPermissibleForObject(ss))
4273                {
4274                    pushedDrawableStateState = pushStateSet(ss);
4275                }
4276            }
4277
4278            if (!_statesetStack.empty())
4279            {
4280                for(StateSetStack::iterator ssitr = _statesetStack.begin();
4281                    ssitr != _statesetStack.end();
4282                    ++ssitr)
4283                {
4284                    _statesetMap[*ssitr].insert(drawable);
4285                }
4286            }
4287
4288            if (pushedDrawableStateState) popStateSet();
4289        }
4290
4291    }
4292
4293    if (pushedGeodeStateState) popStateSet();
4294}
4295
4296void Optimizer::TextureAtlasVisitor::optimize()
4297{
4298    _builder.reset();
4299
4300    if (_textures.size()<2)
4301    {
4302        // nothing to optimize
4303        return;
4304    }
4305
4306    Textures texturesThatRepeat;
4307    Textures texturesThatRepeatAndAreOutOfRange;
4308
4309    StateSetMap::iterator sitr;
4310    for(sitr = _statesetMap.begin();
4311        sitr != _statesetMap.end();
4312        ++sitr)
4313    {
4314        osg::StateSet* stateset = sitr->first;
4315        Drawables& drawables = sitr->second;
4316
4317        osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
4318        for(unsigned int unit=0; unit<tal.size(); ++unit)
4319        {
4320            osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
4321            if (texture)
4322            {
4323                bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4324                                texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4325
4326                bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4327                                texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4328
4329                if (s_repeat || t_repeat)
4330                {
4331                    texturesThatRepeat.insert(texture);
4332
4333                    bool s_outOfRange = false;
4334                    bool t_outOfRange = false;
4335
4336                    float s_min = -0.001;
4337                    float s_max = 1.001;
4338
4339                    float t_min = -0.001;
4340                    float t_max = 1.001;
4341
4342                    for(Drawables::iterator ditr = drawables.begin();
4343                        ditr != drawables.end();
4344                        ++ditr)
4345                    {
4346                        osg::Geometry* geom = (*ditr)->asGeometry();
4347                        osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4348                        if (texcoords && !texcoords->empty())
4349                        {
4350                            for(osg::Vec2Array::iterator titr = texcoords->begin();
4351                                titr != texcoords->end() /*&& !s_outOfRange && !t_outOfRange*/;
4352                                ++titr)
4353                            {
4354                                osg::Vec2 tc = *titr;
4355                                if (tc[0]<s_min) { s_min = tc[0]; s_outOfRange = true; }
4356                                if (tc[0]>s_max) { s_max = tc[0]; s_outOfRange = true; }
4357
4358                                if (tc[1]<t_min) { t_min = tc[1]; t_outOfRange = true; }
4359                                if (tc[1]>t_max) { t_max = tc[1]; t_outOfRange = true; }
4360                            }
4361                        }
4362                        else
4363                        {
4364                            // if no texcoords then texgen must be being used, therefore must assume that texture is truely repeating
4365                            s_outOfRange = true;
4366                            t_outOfRange = true;
4367                        }
4368                    }
4369
4370                    if (s_outOfRange || t_outOfRange)
4371                    {
4372                        texturesThatRepeatAndAreOutOfRange.insert(texture);
4373                    }
4374
4375                }
4376            }
4377        }
4378    }
4379
4380    // now change any texture that repeat but all texcoords to them
4381    // are in 0 to 1 range than converting the to CLAMP mode, to allow them
4382    // to be used in an atlas.
4383    Textures::iterator titr;
4384    for(titr = texturesThatRepeat.begin();
4385        titr != texturesThatRepeat.end();
4386        ++titr)
4387    {
4388        osg::Texture2D* texture = *titr;
4389        if (texturesThatRepeatAndAreOutOfRange.count(texture)==0)
4390        {
4391            // safe to convert into CLAMP wrap mode.
4392            OSG_INFO<<"Changing wrap mode to CLAMP"<<std::endl;
4393            texture->setWrap(osg::Texture2D::WRAP_S, osg::Texture::CLAMP_TO_EDGE);
4394            texture->setWrap(osg::Texture2D::WRAP_T, osg::Texture::CLAMP_TO_EDGE);
4395        }
4396    }
4397    //typedef std::list<osg::Texture2D *> SourceListTmp;
4398    //SourceListTmp sourceToAdd;
4399    // add the textures as sources for the TextureAtlasBuilder
4400    for(titr = _textures.begin();
4401        titr != _textures.end();
4402        ++titr)
4403    {
4404        osg::Texture2D* texture = *titr;
4405
4406        bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4407                        texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4408
4409        bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4410                        texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4411
4412        if (texture->getImage() && !s_repeat && !t_repeat)
4413        {
4414            _builder.addSource(*titr);
4415        }
4416    }
4417
4418    _builder.buildAtlas();
4419
4420
4421    typedef std::set<osg::StateSet*> StateSetSet;
4422    typedef std::map<osg::Drawable*, StateSetSet> DrawableStateSetMap;
4423    DrawableStateSetMap dssm;
4424    for(sitr = _statesetMap.begin();
4425        sitr != _statesetMap.end();
4426        ++sitr)
4427    {
4428        Drawables& drawables = sitr->second;
4429        for(Drawables::iterator ditr = drawables.begin();
4430            ditr != drawables.end();
4431            ++ditr)
4432        {
4433            dssm[(*ditr)->asGeometry()].insert(sitr->first);
4434        }
4435    }
4436
4437    Drawables drawablesThatHaveMultipleTexturesOnOneUnit;
4438    for(DrawableStateSetMap::iterator ditr = dssm.begin();
4439        ditr != dssm.end();
4440        ++ditr)
4441    {
4442        osg::Drawable* drawable = ditr->first;
4443        StateSetSet& ssm = ditr->second;
4444        if (ssm.size()>1)
4445        {
4446            typedef std::map<unsigned int, Textures> UnitTextureMap;
4447            UnitTextureMap unitTextureMap;
4448            for(StateSetSet::iterator ssm_itr = ssm.begin();
4449                ssm_itr != ssm.end();
4450                ++ssm_itr)
4451            {
4452                osg::StateSet* ss = *ssm_itr;
4453                unsigned int numTextureUnits = ss->getTextureAttributeList().size();
4454                for(unsigned int unit=0; unit<numTextureUnits; ++unit)
4455                {
4456                    osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(ss->getTextureAttribute(unit, osg::StateAttribute::TEXTURE));
4457                    if (texture) unitTextureMap[unit].insert(texture);
4458                }
4459            }
4460            bool drawablesHasMultiTextureOnOneUnit = false;
4461            for(UnitTextureMap::iterator utm_itr = unitTextureMap.begin();
4462                utm_itr != unitTextureMap.end() && !drawablesHasMultiTextureOnOneUnit;
4463                ++utm_itr)
4464            {
4465                if (utm_itr->second.size()>1)
4466                {
4467                    drawablesHasMultiTextureOnOneUnit = true;
4468                }
4469            }
4470            if (drawablesHasMultiTextureOnOneUnit)
4471            {
4472                drawablesThatHaveMultipleTexturesOnOneUnit.insert(drawable);
4473            }
4474
4475        }
4476    }
4477
4478    // remap the textures in the StateSet's
4479    for(sitr = _statesetMap.begin();
4480        sitr != _statesetMap.end();
4481        ++sitr)
4482    {
4483        osg::StateSet* stateset = sitr->first;
4484        osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
4485        for(unsigned int unit=0; unit<tal.size(); ++unit)
4486        {
4487            osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
4488            if (texture)
4489            {
4490                bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4491                                texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4492
4493                bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4494                                texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4495
4496                osg::Texture2D* newTexture = _builder.getTextureAtlas(texture);
4497                if (newTexture && newTexture!=texture)
4498                {
4499                    if (s_repeat || t_repeat)
4500                    {
4501                        OSG_NOTICE<<"Warning!!! shouldn't get here"<<std::endl;
4502                    }
4503
4504                    stateset->setTextureAttribute(unit, newTexture);
4505
4506                    Drawables& drawables = sitr->second;
4507
4508                    osg::Matrix matrix = _builder.getTextureMatrix(texture);
4509
4510                    // first check to see if all drawables are ok for applying texturematrix to.
4511                    bool canTexMatBeFlattenedToAllDrawables = true;
4512                    for(Drawables::iterator ditr = drawables.begin();
4513                        ditr != drawables.end() && canTexMatBeFlattenedToAllDrawables;
4514                        ++ditr)
4515                    {
4516                        osg::Geometry* geom = (*ditr)->asGeometry();
4517                        osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4518
4519                        if (!texcoords)
4520                        {
4521                            canTexMatBeFlattenedToAllDrawables = false;
4522                        }
4523
4524                        if (drawablesThatHaveMultipleTexturesOnOneUnit.count(*ditr)!=0)
4525                        {
4526                            canTexMatBeFlattenedToAllDrawables = false;
4527                        }
4528                    }
4529
4530                    if (canTexMatBeFlattenedToAllDrawables)
4531                    {
4532                        // OSG_NOTICE<<"All drawables can be flattened "<<drawables.size()<<std::endl;
4533                        for(Drawables::iterator ditr = drawables.begin();
4534                            ditr != drawables.end();
4535                            ++ditr)
4536                        {
4537                            osg::Geometry* geom = (*ditr)->asGeometry();
4538                            osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4539                            if (texcoords)
4540                            {
4541                                for(osg::Vec2Array::iterator titr = texcoords->begin();
4542                                    titr != texcoords->end();
4543                                    ++titr)
4544                                {
4545                                    osg::Vec2 tc = *titr;
4546                                    (*titr).set(tc[0]*matrix(0,0) + tc[1]*matrix(1,0) + matrix(3,0),
4547                                              tc[0]*matrix(0,1) + tc[1]*matrix(1,1) + matrix(3,1));
4548                                }
4549                            }
4550                            else
4551                            {
4552                                OSG_NOTICE<<"Error, Optimizer::TextureAtlasVisitor::optimize() shouldn't ever get here..."<<std::endl;
4553                            }
4554                        }
4555                    }
4556                    else
4557                    {
4558                        // OSG_NOTICE<<"Applying TexMat "<<drawables.size()<<std::endl;
4559                        stateset->setTextureAttribute(unit, new osg::TexMat(matrix));
4560                    }
4561                }
4562            }
4563        }
4564
4565    }
4566}
4567
4568
4569
4570
4571////////////////////////////////////////////////////////////////////////////
4572// StaticObjectDectionVisitor
4573////////////////////////////////////////////////////////////////////////////
4574
4575void Optimizer::StaticObjectDetectionVisitor::apply(osg::Node& node)
4576{
4577    if (node.getStateSet()) applyStateSet(*node.getStateSet());
4578
4579    traverse(node);
4580}
4581
4582void Optimizer::StaticObjectDetectionVisitor::apply(osg::Geode& geode)
4583{
4584    if (geode.getStateSet()) applyStateSet(*geode.getStateSet());
4585
4586    for(unsigned int i=0; i<geode.getNumDrawables(); ++i)
4587    {
4588        applyDrawable(*geode.getDrawable(i));
4589    }
4590}
4591
4592void Optimizer::StaticObjectDetectionVisitor::applyStateSet(osg::StateSet& stateset)
4593{
4594    stateset.computeDataVariance();
4595}
4596
4597
4598void Optimizer::StaticObjectDetectionVisitor::applyDrawable(osg::Drawable& drawable)
4599{
4600
4601    if (drawable.getStateSet()) applyStateSet(*drawable.getStateSet());
4602
4603    drawable.computeDataVariance();
4604}
4605
4606
4607
4608////////////////////////////////////////////////////////////////////////////
4609// FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor
4610////////////////////////////////////////////////////////////////////////////
4611
4612void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::reset()
4613{
4614    _matrixStack.clear();
4615}
4616
4617void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Group& group)
4618{
4619    // only continue if there is a parent
4620    const unsigned int nodepathsize = _nodePath.size();
4621    if(!_matrixStack.empty() && group.getNumParents() > 1 && nodepathsize > 1)
4622    {
4623        // copy this Group
4624        osg::ref_ptr<osg::Object> new_obj = group.clone(osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4625        osg::Group* new_group = dynamic_cast<osg::Group*>(new_obj.get());
4626
4627        // New Group should only be added to parent through which this Group
4628        // was traversed, not to all parents of this Group.
4629        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4630        if(parent_group)
4631        {
4632            parent_group->replaceChild(&group, new_group);
4633            // traverse the new Group
4634            traverse(*(new_group));
4635        }
4636        else
4637        {
4638            OSG_NOTICE << "No parent for this Group" << std::endl;
4639        }
4640    }
4641    else
4642    {
4643        // traverse original node
4644        traverse(group);
4645    }
4646}
4647
4648
4649void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Transform& transform)
4650{
4651    bool pushed = false;
4652
4653    // only continue if there is a parent and this is a STATIC transform
4654    const unsigned int nodepathsize = _nodePath.size();
4655    if(transform.getDataVariance() == osg::Object::STATIC && nodepathsize > 1)
4656    {
4657        osg::Matrix matrix;
4658        if(!_matrixStack.empty())
4659            matrix = _matrixStack.back();
4660        transform.computeLocalToWorldMatrix(matrix, this);
4661        _matrixStack.push_back(matrix);
4662        pushed = true;
4663
4664        // convert this Transform to a Group
4665        osg::ref_ptr<osg::Group> group = new osg::Group(dynamic_cast<osg::Group&>(transform),
4666            osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4667
4668        // New Group should only be added to parent through which this Transform
4669        // was traversed, not to all parents of this Transform.
4670        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4671        if(parent_group)
4672        {
4673            parent_group->replaceChild(&transform, group.get());
4674            // traverse the new Group
4675            traverse(*(group.get()));
4676        }
4677        else
4678        {
4679            OSG_NOTICE << "No parent for this Group" << std::endl;
4680        }
4681    }
4682    else
4683    {
4684        // traverse original node
4685        traverse(transform);
4686    }
4687
4688    // pop matrix off of stack
4689    if(pushed)
4690        _matrixStack.pop_back();
4691}
4692
4693
4694void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::LOD& lod)
4695{
4696    const unsigned int nodepathsize = _nodePath.size();
4697    if(!_matrixStack.empty() && lod.getNumParents() > 1 && nodepathsize > 1)
4698    {
4699        osg::ref_ptr<osg::LOD> new_lod = new osg::LOD(lod,
4700            osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4701
4702        // New LOD should only be added to parent through which this LOD
4703        // was traversed, not to all parents of this LOD.
4704        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4705        if(parent_group)
4706        {
4707            parent_group->replaceChild(&lod, new_lod.get());
4708
4709            // move center point
4710            if(!_matrixStack.empty())
4711                new_lod->setCenter(new_lod->getCenter() * _matrixStack.back());
4712
4713            // traverse the new Group
4714            traverse(*(new_lod.get()));
4715        }
4716        else
4717            OSG_NOTICE << "No parent for this LOD" << std::endl;
4718    }
4719    else
4720    {
4721        // move center point
4722        if(!_matrixStack.empty())
4723            lod.setCenter(lod.getCenter() * _matrixStack.back());
4724
4725        traverse(lod);
4726    }
4727}
4728
4729
4730void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Geode& geode)
4731{
4732    if(!_matrixStack.empty())
4733    {
4734        // If there is only one parent, just transform all vertices and normals
4735        if(geode.getNumParents() == 1)
4736        {
4737            transformGeode(geode);
4738        }
4739        else
4740        {
4741            // Else make a copy and then transform
4742            const unsigned int nodepathsize = _nodePath.size();
4743            if(nodepathsize > 1)
4744            {
4745                // convert this Transform to a Group
4746                osg::ref_ptr<osg::Geode> new_geode = new osg::Geode(geode,
4747                    osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4748
4749                // New Group should only be added to parent through which this Transform
4750                // was traversed, not to all parents of this Transform.
4751                osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4752                if(parent_group)
4753                    parent_group->replaceChild(&geode, new_geode.get());
4754                else
4755                    OSG_NOTICE << "No parent for this Geode" << std::endl;
4756
4757                transformGeode(*(new_geode.get()));
4758            }
4759        }
4760    }
4761}
4762
4763
4764void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Billboard& billboard)
4765{
4766    if(!_matrixStack.empty())
4767    {
4768        // If there is only one parent, just transform this Billboard
4769        if(billboard.getNumParents() == 1)
4770        {
4771            transformBillboard(billboard);
4772        }
4773        else
4774        {
4775            // Else make a copy and then transform
4776            const unsigned int nodepathsize = _nodePath.size();
4777            if(nodepathsize > 1)
4778            {
4779                // convert this Transform to a Group
4780                osg::ref_ptr<osg::Billboard> new_billboard = new osg::Billboard(billboard,
4781                    osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4782
4783                // New Billboard should only be added to parent through which this Billboard
4784                // was traversed, not to all parents of this Billboard.
4785                osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4786                if(parent_group)
4787                    parent_group->replaceChild(&billboard, new_billboard.get());
4788                else
4789                    OSG_NOTICE << "No parent for this Billboard" << std::endl;
4790
4791                transformBillboard(*(new_billboard.get()));
4792            }
4793        }
4794    }
4795}
4796
4797
4798void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformGeode(osg::Geode& geode)
4799{
4800    for(unsigned int i=0; i<geode.getNumDrawables(); i++)
4801    {
4802        transformDrawable(*geode.getDrawable(i));
4803    }
4804
4805    geode.dirtyBound();
4806}
4807
4808
4809void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformDrawable(osg::Drawable& drawable)
4810{
4811    osg::Geometry* geometry = drawable.asGeometry();
4812    if(geometry)
4813    {
4814        // transform all geometry
4815        osg::Vec3Array* verts = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray());
4816        if(verts)
4817        {
4818            for(unsigned int j=0; j<verts->size(); j++)
4819            {
4820                (*verts)[j] = (*verts)[j] * _matrixStack.back();
4821            }
4822        }
4823        else
4824        {
4825            osg::Vec4Array* verts = dynamic_cast<osg::Vec4Array*>(geometry->getVertexArray());
4826            if(verts)
4827            {
4828                for(unsigned int j=0; j<verts->size(); j++)
4829                {
4830                    (*verts)[j] = _matrixStack.back() * (*verts)[j];
4831                }
4832            }
4833        }
4834        osg::Vec3Array* normals = dynamic_cast<osg::Vec3Array*>(geometry->getNormalArray());
4835        if(normals)
4836        {
4837            for(unsigned int j=0; j<normals->size(); j++)
4838                (*normals)[j] = osg::Matrix::transform3x3((*normals)[j], _matrixStack.back());
4839        }
4840
4841        geometry->dirtyBound();
4842        geometry->dirtyDisplayList();
4843    }
4844}
4845
4846
4847void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformBillboard(osg::Billboard& billboard)
4848{
4849    osg::Vec3 axis = osg::Matrix::transform3x3(billboard.getAxis(), _matrixStack.back());
4850    axis.normalize();
4851    billboard.setAxis(axis);
4852
4853    osg::Vec3 normal = osg::Matrix::transform3x3(billboard.getNormal(), _matrixStack.back());
4854    normal.normalize();
4855    billboard.setNormal(normal);
4856
4857    for(unsigned int i=0; i<billboard.getNumDrawables(); i++)
4858    {
4859        osg::Vec3 originalBillboardPosition = billboard.getPosition(i);
4860        billboard.setPosition(i, originalBillboardPosition * _matrixStack.back());
4861
4862        osg::Matrix matrixForDrawable = _matrixStack.back();
4863        matrixForDrawable.preMult(osg::Matrix::translate(originalBillboardPosition));
4864        matrixForDrawable.postMult(osg::Matrix::translate(-billboard.getPosition(i)));
4865
4866        _matrixStack.push_back(matrixForDrawable);
4867        transformDrawable(*billboard.getDrawable(i));
4868        _matrixStack.pop_back();
4869    }
4870
4871    billboard.dirtyBound();
4872}
4873
4874
Note: See TracBrowser for help on using the browser.