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

Revision 11204, 157.9 kB (checked in by robert, 5 years ago)

From Time Moore, "This submission implements 3 optimizations for meshes. INDEX_MESH turns DrawArrays? style geometry into DrawElements?, uniquifying the vertices in the process. This is useful for certain loaders, like ac3d, which just spit out DrawArrays?. VERTEX_POSTTRANSFORM and VERTEX_PRETRANSFORM optimize mesh triangle and vertex order for the caches on a modern GPU, using Tom Forsyth's algorithm. I describe this and the big difference it makes (38% improvement on a very large mesh) in my blog,
http://shiny-dynamics.blogspot.com/2010/03/vertex-cache-optimization-for-osg.html."

  • 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::notify(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(osg::INFO)<<"Optimizer::optimize() doing FLATTEN_STATIC_TRANSFORMS"<<std::endl;
248
249        int i=0;
250        bool result = false;
251        do
252        {
253            OSG_NOTIFY(osg::DEBUG_INFO) << "** 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_NOTIFY(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_NOTIFY(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_NOTIFY(osg::INFO)<<"MERGE_GEODES took "<<osg::Timer::instance()->delta_s(startTick,endTick)<<std::endl;
288    }
289
290    if (options & CHECK_GEOMETRY)
291    {
292        OSG_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(osg::INFO)<<"MERGE_GEOMETRY took "<<osg::Timer::instance()->delta_s(startTick,endTick)<<std::endl;
319    }
320   
321    if (options & TRISTRIP_GEOMETRY)
322    {
323        OSG_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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::notify(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_NOTIFY(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_NOTIFY(osg::INFO) << "state attribute list"<< std::endl;
577            for(AttributeList::iterator aaitr = attributeList.begin();
578                aaitr!=attributeList.end();
579                ++aaitr)
580            {
581                OSG_NOTIFY(osg::INFO) << "    "<<*aaitr << "  "<<(*aaitr)->className()<< std::endl;
582            }
583
584            OSG_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(osg::INFO) << "state uniform list"<< std::endl;
629            for(UniformList::iterator uuitr = uniformList.begin();
630                uuitr!=uniformList.end();
631                ++uuitr)
632            {
633                OSG_NOTIFY(osg::INFO) << "    "<<*uuitr << "  "<<(*uuitr)->getName()<< std::endl;
634            }
635
636            OSG_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(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_NOTIFY(osg::WARN)<<"Warning:: during Optimize::CollectLowestTransformsVisitor::removeTransforms(Node*)"<<std::endl;
1141                        OSG_NOTIFY(osg::WARN)<<"          unhandled of setting of indentity matrix on "<< titr->first->className()<<std::endl;
1142                        OSG_NOTIFY(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// CombineStatucTransforms
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.getUpdateCallback() &&
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_NOTIFY(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_NOTIFY(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
1854bool Optimizer::MergeGeometryVisitor::mergeGeode(osg::Geode& geode)
1855{
1856    if (!isOperationPermissibleForObject(&geode)) return false;
1857
1858    if (geode.getNumDrawables()>=2)
1859    {
1860   
1861        // OSG_NOTIFY(osg::NOTICE)<<"Before "<<geode.getNumDrawables()<<std::endl;
1862   
1863        typedef std::vector<osg::Geometry*>                         DuplicateList;
1864        typedef std::map<osg::Geometry*,DuplicateList,LessGeometry> GeometryDuplicateMap;
1865
1866        typedef std::vector<DuplicateList> MergeList;
1867
1868        GeometryDuplicateMap geometryDuplicateMap;
1869        osg::Geode::DrawableList standardDrawables;
1870
1871        unsigned int i;
1872        for(i=0;i<geode.getNumDrawables();++i)
1873        {
1874            osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1875            if (geom)
1876            {
1877                //geom->computeCorrectBindingsAndArraySizes();
1878
1879                if (!geometryContainsSharedArrays(*geom) &&
1880                      geom->getDataVariance()!=osg::Object::DYNAMIC &&
1881                      isOperationPermissibleForObject(geom))
1882                {
1883                    geometryDuplicateMap[geom].push_back(geom);
1884                }
1885                else
1886                {
1887                    standardDrawables.push_back(geode.getDrawable(i));
1888                }
1889            }
1890            else
1891            {           
1892                standardDrawables.push_back(geode.getDrawable(i));
1893            }
1894        }
1895
1896#if 1
1897        bool needToDoMerge = false;
1898        MergeList mergeList;
1899        for(GeometryDuplicateMap::iterator itr=geometryDuplicateMap.begin();
1900            itr!=geometryDuplicateMap.end();
1901            ++itr)
1902        {
1903            mergeList.push_back(DuplicateList());
1904            DuplicateList* duplicateList = &mergeList.back();
1905           
1906            if (itr->second.size()>1)
1907            {
1908                std::sort(itr->second.begin(),itr->second.end(),LessGeometryPrimitiveType());
1909                osg::Geometry* lhs = itr->second[0];
1910
1911                duplicateList->push_back(lhs);
1912               
1913                unsigned int numVertices = lhs->getVertexArray() ? lhs->getVertexArray()->getNumElements() : 0;
1914
1915                for(DuplicateList::iterator dupItr=itr->second.begin()+1;
1916                    dupItr!=itr->second.end();
1917                    ++dupItr)
1918                {
1919               
1920                    osg::Geometry* rhs = *dupItr;
1921                   
1922                    unsigned int numRhsVertices = rhs->getVertexArray() ? rhs->getVertexArray()->getNumElements() : 0;
1923
1924                    if (numVertices+numRhsVertices < _targetMaximumNumberOfVertices)
1925                    {
1926                        duplicateList->push_back(rhs);
1927                        numVertices += numRhsVertices;
1928                        needToDoMerge = true;
1929                    }
1930                    else
1931                    {
1932                        numVertices = numRhsVertices;
1933                        mergeList.push_back(DuplicateList());
1934                        duplicateList = &mergeList.back();
1935                        duplicateList->push_back(rhs);
1936                    }
1937
1938                }
1939            }
1940            else if (itr->second.size()>0)
1941            {
1942                duplicateList->push_back(itr->second[0]);
1943            }
1944        }
1945       
1946        if (needToDoMerge)
1947        {
1948            // first take a reference to all the drawables to prevent them being deleted prematurely
1949            osg::Geode::DrawableList keepDrawables;
1950            keepDrawables.resize(geode.getNumDrawables());
1951            for(i=0; i<geode.getNumDrawables(); ++i)
1952            {
1953                keepDrawables[i] = geode.getDrawable(i);
1954            }
1955           
1956            // now clear the drawable list of the Geode so we don't have to remove items one by one (which is slow)
1957            geode.removeDrawables(0, geode.getNumDrawables());
1958           
1959            // add back in the standard drawables which arn't possible to merge.
1960            for(osg::Geode::DrawableList::iterator sitr = standardDrawables.begin();
1961                sitr != standardDrawables.end();
1962                ++sitr)
1963            {
1964                geode.addDrawable(sitr->get());
1965            }
1966               
1967            // now do the merging of geometries
1968            for(MergeList::iterator mitr = mergeList.begin();
1969                mitr != mergeList.end();
1970                ++mitr)
1971            {
1972                DuplicateList& duplicateList = *mitr;
1973                if (duplicateList.size()>1)
1974                {
1975                    osg::Geometry* lhs = duplicateList.front();
1976                    geode.addDrawable(lhs);
1977                    for(DuplicateList::iterator ditr = duplicateList.begin()+1;
1978                        ditr != duplicateList.end();
1979                        ++ditr)
1980                    {
1981                        mergeGeometry(*lhs,**ditr);
1982                    }
1983                }
1984                else if (duplicateList.size()>0)
1985                {
1986                    geode.addDrawable(duplicateList.front());
1987                }
1988            }
1989        }
1990
1991#else
1992        // don't merge geometry if its above a maximum number of vertices.
1993        for(GeometryDuplicateMap::iterator itr=geometryDuplicateMap.begin();
1994            itr!=geometryDuplicateMap.end();
1995            ++itr)
1996        {
1997            if (itr->second.size()>1)
1998            {
1999                std::sort(itr->second.begin(),itr->second.end(),LessGeometryPrimitiveType());
2000                osg::Geometry* lhs = itr->second[0];
2001                for(DuplicateList::iterator dupItr=itr->second.begin()+1;
2002                    dupItr!=itr->second.end();
2003                    ++dupItr)
2004                {
2005               
2006                    osg::Geometry* rhs = *dupItr;
2007                   
2008                    if (lhs->getVertexArray() && lhs->getVertexArray()->getNumElements()>=_targetMaximumNumberOfVertices)
2009                    {
2010                        lhs = rhs;
2011                        continue;
2012                    }
2013
2014                    if (rhs->getVertexArray() && rhs->getVertexArray()->getNumElements()>=_targetMaximumNumberOfVertices)
2015                    {
2016                        continue;
2017                    }
2018                   
2019                    if (lhs->getVertexArray() && rhs->getVertexArray() &&
2020                        (lhs->getVertexArray()->getNumElements()+rhs->getVertexArray()->getNumElements())>=_targetMaximumNumberOfVertices)
2021                    {
2022                        continue;
2023                    }
2024                   
2025                    if (mergeGeometry(*lhs,*rhs))
2026                    {
2027                        geode.removeDrawable(rhs);
2028
2029                        static int co = 0;
2030                        OSG_NOTIFY(osg::INFO)<<"merged and removed Geometry "<<++co<<std::endl;
2031                    }
2032                }
2033            }
2034        }
2035#endif
2036
2037        // OSG_NOTIFY(osg::NOTICE)<<"After "<<geode.getNumDrawables()<<std::endl;
2038
2039    }
2040
2041
2042    // convert all polygon primitives which has 3 indices into TRIANGLES, 4 indices into QUADS.
2043    unsigned int i;
2044    for(i=0;i<geode.getNumDrawables();++i)
2045    {
2046        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
2047        if (geom)
2048        {
2049            osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2050            for(osg::Geometry::PrimitiveSetList::iterator itr=primitives.begin();
2051                itr!=primitives.end();
2052                ++itr)
2053            {
2054                osg::PrimitiveSet* prim = itr->get();
2055                if (prim->getMode()==osg::PrimitiveSet::POLYGON)
2056                {
2057                    if (prim->getNumIndices()==3)
2058                    {
2059                        prim->setMode(osg::PrimitiveSet::TRIANGLES);
2060                    }
2061                    else if (prim->getNumIndices()==4)
2062                    {
2063                        prim->setMode(osg::PrimitiveSet::QUADS);
2064                    }
2065                }
2066            }
2067        }
2068    }
2069
2070    // now merge any compatible primitives.
2071    for(i=0;i<geode.getNumDrawables();++i)
2072    {
2073        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
2074        if (geom)
2075        {
2076            if (geom->getNumPrimitiveSets()>0 &&
2077                geom->getNormalBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2078                geom->getColorBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2079                geom->getSecondaryColorBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2080                geom->getFogCoordBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET)
2081            {
2082           
2083#if 1
2084                bool doneCombine = false;
2085
2086                osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2087                unsigned int lhsNo=0;
2088                unsigned int rhsNo=1;
2089                while(rhsNo<primitives.size())
2090                {
2091                    osg::PrimitiveSet* lhs = primitives[lhsNo].get();
2092                    osg::PrimitiveSet* rhs = primitives[rhsNo].get();
2093 
2094                    bool combine = false;
2095
2096                    if (lhs->getType()==rhs->getType() &&
2097                        lhs->getMode()==rhs->getMode())
2098                    {
2099
2100                        switch(lhs->getMode())
2101                        {
2102                        case(osg::PrimitiveSet::POINTS):
2103                        case(osg::PrimitiveSet::LINES):
2104                        case(osg::PrimitiveSet::TRIANGLES):
2105                        case(osg::PrimitiveSet::QUADS):
2106                            combine = true;       
2107                            break;
2108                        }
2109                       
2110                    }
2111
2112                    if (combine)
2113                    {
2114                   
2115                        switch(lhs->getType())
2116                        {
2117                        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2118                            combine = mergePrimitive(*(static_cast<osg::DrawArrays*>(lhs)),*(static_cast<osg::DrawArrays*>(rhs)));
2119                            break;
2120                        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2121                            combine = mergePrimitive(*(static_cast<osg::DrawArrayLengths*>(lhs)),*(static_cast<osg::DrawArrayLengths*>(rhs)));
2122                            break;
2123                        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2124                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUByte*>(lhs)),*(static_cast<osg::DrawElementsUByte*>(rhs)));
2125                            break;
2126                        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2127                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUShort*>(lhs)),*(static_cast<osg::DrawElementsUShort*>(rhs)));
2128                            break;
2129                        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2130                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUInt*>(lhs)),*(static_cast<osg::DrawElementsUInt*>(rhs)));
2131                            break;
2132                        default:
2133                            combine = false;
2134                            break;
2135                        }
2136                    }
2137
2138                    if (combine)
2139                    {
2140                        // make this primitive set as invalid and needing cleaning up.
2141                        rhs->setMode(0xffffff);
2142                        doneCombine = true;
2143                        ++rhsNo;
2144                    }
2145                    else
2146                    {
2147                        lhsNo = rhsNo;
2148                        ++rhsNo;
2149                    }
2150                }
2151
2152    #if 1               
2153                if (doneCombine)
2154                {
2155                    // now need to clean up primitiveset so it no longer contains the rhs combined primitives.
2156
2157                    // first swap with a empty primitiveSet to empty it completely.
2158                    osg::Geometry::PrimitiveSetList oldPrimitives;
2159                    primitives.swap(oldPrimitives);
2160                   
2161                    // now add the active primitive sets
2162                    for(osg::Geometry::PrimitiveSetList::iterator pitr = oldPrimitives.begin();
2163                        pitr != oldPrimitives.end();
2164                        ++pitr)
2165                    {
2166                        if ((*pitr)->getMode()!=0xffffff) primitives.push_back(*pitr);
2167                    }
2168                }
2169    #endif
2170
2171#else           
2172
2173                osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2174                unsigned int primNo=0;
2175                while(primNo+1<primitives.size())
2176                {
2177                    osg::PrimitiveSet* lhs = primitives[primNo].get();
2178                    osg::PrimitiveSet* rhs = primitives[primNo+1].get();
2179 
2180                    bool combine = false;
2181
2182                    if (lhs->getType()==rhs->getType() &&
2183                        lhs->getMode()==rhs->getMode())
2184                    {
2185
2186                        switch(lhs->getMode())
2187                        {
2188                        case(osg::PrimitiveSet::POINTS):
2189                        case(osg::PrimitiveSet::LINES):
2190                        case(osg::PrimitiveSet::TRIANGLES):
2191                        case(osg::PrimitiveSet::QUADS):
2192                            combine = true;       
2193                            break;
2194                        }
2195                       
2196                    }
2197
2198                    if (combine)
2199                    {
2200                   
2201                        switch(lhs->getType())
2202                        {
2203                        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2204                            combine = mergePrimitive(*(static_cast<osg::DrawArrays*>(lhs)),*(static_cast<osg::DrawArrays*>(rhs)));
2205                            break;
2206                        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2207                            combine = mergePrimitive(*(static_cast<osg::DrawArrayLengths*>(lhs)),*(static_cast<osg::DrawArrayLengths*>(rhs)));
2208                            break;
2209                        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2210                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUByte*>(lhs)),*(static_cast<osg::DrawElementsUByte*>(rhs)));
2211                            break;
2212                        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2213                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUShort*>(lhs)),*(static_cast<osg::DrawElementsUShort*>(rhs)));
2214                            break;
2215                        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2216                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUInt*>(lhs)),*(static_cast<osg::DrawElementsUInt*>(rhs)));
2217                            break;
2218                        default:
2219                            break;
2220                        }
2221                    }
2222                    if (combine)
2223                    {
2224                        primitives.erase(primitives.begin()+primNo+1);
2225                    }
2226
2227                    if (!combine)
2228                    {
2229                        primNo++;
2230                    }
2231                }
2232#endif
2233            }
2234        }
2235
2236
2237    }
2238
2239//    geode.dirtyBound();
2240
2241
2242    return false;
2243}
2244
2245bool Optimizer::MergeGeometryVisitor::geometryContainsSharedArrays(osg::Geometry& geom)
2246{
2247    if (geom.getVertexArray() && geom.getVertexArray()->referenceCount()>1) return true;
2248    if (geom.getNormalArray() && geom.getNormalArray()->referenceCount()>1) return true;
2249    if (geom.getColorArray() && geom.getColorArray()->referenceCount()>1) return true;
2250    if (geom.getSecondaryColorArray() && geom.getSecondaryColorArray()->referenceCount()>1) return true;
2251    if (geom.getFogCoordArray() && geom.getFogCoordArray()->referenceCount()>1) return true;
2252   
2253
2254    for(unsigned int unit=0;unit<geom.getNumTexCoordArrays();++unit)
2255    {
2256        osg::Array* tex = geom.getTexCoordArray(unit);
2257        if (tex && tex->referenceCount()>1) return true;
2258    }
2259   
2260    // shift the indices of the incoming primitives to account for the pre existing geometry.
2261    for(osg::Geometry::PrimitiveSetList::iterator primItr=geom.getPrimitiveSetList().begin();
2262        primItr!=geom.getPrimitiveSetList().end();
2263        ++primItr)
2264    {
2265        if ((*primItr)->referenceCount()>1) return true;
2266    }
2267   
2268   
2269    return false;
2270}
2271
2272
2273class MergeArrayVisitor : public osg::ArrayVisitor
2274{
2275    public:
2276   
2277        osg::Array* _lhs;
2278        int         _offset;
2279   
2280        MergeArrayVisitor() :
2281            _lhs(0),
2282            _offset(0) {}
2283           
2284           
2285        void merge(osg::Array* lhs,osg::Array* rhs, int offset=0)
2286        {
2287            if (lhs==0 || rhs==0) return;
2288            if (lhs->getType()!=rhs->getType()) return;
2289           
2290            _lhs = lhs;
2291            _offset = offset;
2292           
2293            rhs->accept(*this);
2294        }
2295       
2296        template<typename T>
2297        void _merge(T& rhs)
2298        {
2299            T* lhs = static_cast<T*>(_lhs);
2300            lhs->insert(lhs->end(),rhs.begin(),rhs.end());
2301        }
2302       
2303        template<typename T>
2304        void _mergeAndOffset(T& rhs)
2305        {
2306            T* lhs = static_cast<T*>(_lhs);
2307
2308            typename T::iterator itr;
2309            for(itr = rhs.begin();
2310                itr != rhs.end();
2311                ++itr)
2312            {
2313                lhs->push_back(*itr + _offset);
2314            }
2315        }
2316           
2317        virtual void apply(osg::Array&) { OSG_NOTIFY(osg::WARN) << "Warning: Optimizer's MergeArrayVisitor cannot merge Array type." << std::endl; }
2318
2319        virtual void apply(osg::ByteArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2320        virtual void apply(osg::ShortArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2321        virtual void apply(osg::IntArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2322        virtual void apply(osg::UByteArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2323        virtual void apply(osg::UShortArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2324        virtual void apply(osg::UIntArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2325
2326        virtual void apply(osg::Vec4ubArray& rhs) { _merge(rhs); }
2327        virtual void apply(osg::FloatArray& rhs) { _merge(rhs); }
2328        virtual void apply(osg::Vec2Array& rhs) { _merge(rhs); }
2329        virtual void apply(osg::Vec3Array& rhs) { _merge(rhs); }
2330        virtual void apply(osg::Vec4Array& rhs) { _merge(rhs); }
2331       
2332        virtual void apply(osg::DoubleArray& rhs) { _merge(rhs); }
2333        virtual void apply(osg::Vec2dArray& rhs) { _merge(rhs); }
2334        virtual void apply(osg::Vec3dArray& rhs) { _merge(rhs); }
2335        virtual void apply(osg::Vec4dArray& rhs) { _merge(rhs); }
2336       
2337        virtual void apply(osg::Vec2bArray&  rhs) { _merge(rhs); }
2338        virtual void apply(osg::Vec3bArray&  rhs) { _merge(rhs); }
2339        virtual void apply(osg::Vec4bArray&  rhs) { _merge(rhs); }       
2340        virtual void apply(osg::Vec2sArray& rhs) { _merge(rhs); }
2341        virtual void apply(osg::Vec3sArray& rhs) { _merge(rhs); }
2342        virtual void apply(osg::Vec4sArray& rhs) { _merge(rhs); }
2343};
2344
2345bool Optimizer::MergeGeometryVisitor::mergeGeometry(osg::Geometry& lhs,osg::Geometry& rhs)
2346{
2347
2348    MergeArrayVisitor merger;
2349 
2350    unsigned int base = 0;
2351    unsigned int vbase = lhs.getVertexArray() ? lhs.getVertexArray()->getNumElements() : 0;
2352    if (lhs.getVertexArray() && rhs.getVertexArray())
2353    {
2354
2355        base = lhs.getVertexArray()->getNumElements();
2356        merger.merge(lhs.getVertexArray(),rhs.getVertexArray());
2357
2358    }
2359    else if (rhs.getVertexArray())
2360    {
2361        base = 0;
2362        lhs.setVertexArray(rhs.getVertexArray());
2363    }
2364   
2365    if (lhs.getVertexIndices() && rhs.getVertexIndices())
2366    {
2367
2368        base = lhs.getVertexIndices()->getNumElements();
2369        merger.merge(lhs.getVertexIndices(),rhs.getVertexIndices(),vbase);
2370
2371    }
2372    else if (rhs.getVertexIndices())
2373    {
2374        base = 0;
2375        lhs.setVertexIndices(rhs.getVertexIndices());
2376    }
2377   
2378
2379    unsigned int nbase = lhs.getNormalArray() ? lhs.getNormalArray()->getNumElements() : 0;
2380    if (lhs.getNormalArray() && rhs.getNormalArray() && lhs.getNormalBinding()!=osg::Geometry::BIND_OVERALL)
2381    {
2382        merger.merge(lhs.getNormalArray(),rhs.getNormalArray());
2383    }
2384    else if (rhs.getNormalArray())
2385    {
2386        lhs.setNormalArray(rhs.getNormalArray());
2387    }
2388
2389    if (lhs.getNormalIndices() && rhs.getNormalIndices() && lhs.getNormalBinding()!=osg::Geometry::BIND_OVERALL)
2390    {
2391        merger.merge(lhs.getNormalIndices(),rhs.getNormalIndices(),nbase);
2392    }
2393    else if (rhs.getNormalIndices())
2394    {
2395        // this assignment makes the assumption that lhs.NormalArray is empty as well and NormalIndices
2396        lhs.setNormalIndices(rhs.getNormalIndices());
2397    }
2398
2399
2400    unsigned int cbase = lhs.getColorArray() ? lhs.getColorArray()->getNumElements() : 0;
2401    if (lhs.getColorArray() && rhs.getColorArray() && lhs.getColorBinding()!=osg::Geometry::BIND_OVERALL)
2402    {
2403        merger.merge(lhs.getColorArray(),rhs.getColorArray());
2404    }
2405    else if (rhs.getColorArray())
2406    {
2407        lhs.setColorArray(rhs.getColorArray());
2408    }
2409   
2410    if (lhs.getColorIndices() && rhs.getColorIndices() && lhs.getColorBinding()!=osg::Geometry::BIND_OVERALL)
2411    {
2412        merger.merge(lhs.getColorIndices(),rhs.getColorIndices(),cbase);
2413    }
2414    else if (rhs.getColorIndices())
2415    {
2416        // this assignment makes the assumption that lhs.ColorArray is empty as well and ColorIndices
2417        lhs.setColorIndices(rhs.getColorIndices());
2418    }
2419
2420    unsigned int scbase = lhs.getSecondaryColorArray() ? lhs.getSecondaryColorArray()->getNumElements() : 0;
2421    if (lhs.getSecondaryColorArray() && rhs.getSecondaryColorArray() && lhs.getSecondaryColorBinding()!=osg::Geometry::BIND_OVERALL)
2422    {
2423        merger.merge(lhs.getSecondaryColorArray(),rhs.getSecondaryColorArray());
2424    }
2425    else if (rhs.getSecondaryColorArray())
2426    {
2427        lhs.setSecondaryColorArray(rhs.getSecondaryColorArray());
2428    }
2429   
2430    if (lhs.getSecondaryColorIndices() && rhs.getSecondaryColorIndices() && lhs.getSecondaryColorBinding()!=osg::Geometry::BIND_OVERALL)
2431    {
2432        merger.merge(lhs.getSecondaryColorIndices(),rhs.getSecondaryColorIndices(),scbase);
2433    }
2434    else if (rhs.getSecondaryColorIndices())
2435    {
2436        // this assignment makes the assumption that lhs.SecondaryColorArray is empty as well and SecondaryColorIndices
2437        lhs.setSecondaryColorIndices(rhs.getSecondaryColorIndices());
2438    }
2439
2440    unsigned int fcbase = lhs.getFogCoordArray() ? lhs.getFogCoordArray()->getNumElements() : 0;
2441    if (lhs.getFogCoordArray() && rhs.getFogCoordArray() && lhs.getFogCoordBinding()!=osg::Geometry::BIND_OVERALL)
2442    {
2443        merger.merge(lhs.getFogCoordArray(),rhs.getFogCoordArray());
2444    }
2445    else if (rhs.getFogCoordArray())
2446    {
2447        lhs.setFogCoordArray(rhs.getFogCoordArray());
2448    }
2449
2450    if (lhs.getFogCoordIndices() && rhs.getFogCoordIndices() && lhs.getFogCoordBinding()!=osg::Geometry::BIND_OVERALL)
2451    {
2452        merger.merge(lhs.getFogCoordIndices(),rhs.getFogCoordIndices(),fcbase);
2453    }
2454    else if (rhs.getFogCoordIndices())
2455    {
2456        // this assignment makes the assumption that lhs.FogCoordArray is empty as well and FogCoordIndices
2457        lhs.setFogCoordIndices(rhs.getFogCoordIndices());
2458    }
2459
2460
2461    unsigned int unit;
2462    for(unit=0;unit<lhs.getNumTexCoordArrays();++unit)
2463    {
2464        unsigned int tcbase = lhs.getTexCoordArray(unit) ? lhs.getTexCoordArray(unit)->getNumElements() : 0;
2465        merger.merge(lhs.getTexCoordArray(unit),rhs.getTexCoordArray(unit));
2466       
2467        if (lhs.getTexCoordIndices(unit) && rhs.getTexCoordIndices(unit))
2468        {
2469            merger.merge(lhs.getTexCoordIndices(unit),rhs.getTexCoordIndices(unit),tcbase);
2470        }
2471    }
2472   
2473    for(unit=0;unit<lhs.getNumVertexAttribArrays();++unit)
2474    {
2475        unsigned int vabase = lhs.getVertexAttribArray(unit) ? lhs.getVertexAttribArray(unit)->getNumElements() : 0;
2476        merger.merge(lhs.getVertexAttribArray(unit),rhs.getVertexAttribArray(unit));
2477       
2478        if (lhs.getVertexAttribIndices(unit) && rhs.getVertexAttribIndices(unit))
2479        {
2480            merger.merge(lhs.getVertexAttribIndices(unit),rhs.getVertexAttribIndices(unit),vabase);
2481        }
2482    }
2483
2484
2485    // shift the indices of the incoming primitives to account for the pre existing geometry.
2486    osg::Geometry::PrimitiveSetList::iterator primItr;
2487    for(primItr=rhs.getPrimitiveSetList().begin(); primItr!=rhs.getPrimitiveSetList().end(); ++primItr)
2488    {
2489        osg::PrimitiveSet* primitive = primItr->get();
2490       
2491        switch(primitive->getType())
2492        {
2493        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2494            {
2495                osg::DrawElementsUByte* primitiveUByte = static_cast<osg::DrawElementsUByte*>(primitive);
2496                unsigned int currentMaximum = 0;
2497                for(osg::DrawElementsUByte::iterator eitr=primitiveUByte->begin();
2498                    eitr!=primitiveUByte->end();
2499                    ++eitr)
2500                {
2501                    currentMaximum = osg::maximum(currentMaximum,(unsigned int)*eitr);
2502                }
2503                if ((base+currentMaximum)>=65536)
2504                {
2505                    // must promote to a DrawElementsUInt
2506                    osg::DrawElementsUInt* new_primitive = new osg::DrawElementsUInt(primitive->getMode());
2507                    std::copy(primitiveUByte->begin(),primitiveUByte->end(),std::back_inserter(*new_primitive));
2508                    new_primitive->offsetIndices(base);
2509                    (*primItr) = new_primitive;
2510                } else if ((base+currentMaximum)>=256)
2511                {
2512                    // must promote to a DrawElementsUShort
2513                    osg::DrawElementsUShort* new_primitive = new osg::DrawElementsUShort(primitive->getMode());
2514                    std::copy(primitiveUByte->begin(),primitiveUByte->end(),std::back_inserter(*new_primitive));
2515                    new_primitive->offsetIndices(base);
2516                    (*primItr) = new_primitive;
2517                }
2518                else
2519                {
2520                    primitive->offsetIndices(base);
2521                }
2522            }
2523            break;
2524
2525        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2526            {
2527                osg::DrawElementsUShort* primitiveUShort = static_cast<osg::DrawElementsUShort*>(primitive);
2528                unsigned int currentMaximum = 0;
2529                for(osg::DrawElementsUShort::iterator eitr=primitiveUShort->begin();
2530                    eitr!=primitiveUShort->end();
2531                    ++eitr)
2532                {
2533                    currentMaximum = osg::maximum(currentMaximum,(unsigned int)*eitr);
2534                }
2535                if ((base+currentMaximum)>=65536)
2536                {
2537                    // must promote to a DrawElementsUInt
2538                    osg::DrawElementsUInt* new_primitive = new osg::DrawElementsUInt(primitive->getMode());
2539                    std::copy(primitiveUShort->begin(),primitiveUShort->end(),std::back_inserter(*new_primitive));
2540                    new_primitive->offsetIndices(base);
2541                    (*primItr) = new_primitive;
2542                }
2543                else
2544                {
2545                    primitive->offsetIndices(base);
2546                }
2547            }
2548            break;
2549
2550        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2551        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2552        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2553        default:
2554            primitive->offsetIndices(base);
2555            break;
2556        }
2557    }
2558   
2559    for(primItr=rhs.getPrimitiveSetList().begin(); primItr!=rhs.getPrimitiveSetList().end(); ++primItr)
2560    {
2561        lhs.addPrimitiveSet(primItr->get());
2562    }
2563
2564    lhs.dirtyBound();
2565    lhs.dirtyDisplayList();
2566   
2567    return true;
2568}
2569
2570bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawArrays& lhs,osg::DrawArrays& rhs)
2571{
2572    if (lhs.getFirst()+lhs.getCount()==rhs.getFirst())
2573    {
2574        lhs.setCount(lhs.getCount()+rhs.getCount());
2575        return true;
2576    }
2577    return false;
2578}
2579
2580bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawArrayLengths& lhs,osg::DrawArrayLengths& rhs)
2581{
2582    int lhs_count = std::accumulate(lhs.begin(),lhs.end(),0);
2583
2584    if (lhs.getFirst()+lhs_count==rhs.getFirst())
2585    {
2586        lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2587        return true;
2588    }
2589    return false;
2590}
2591
2592bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUByte& lhs,osg::DrawElementsUByte& rhs)
2593{
2594    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2595    return true;
2596}
2597
2598bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUShort& lhs,osg::DrawElementsUShort& rhs)
2599{
2600    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2601    return true;
2602}
2603
2604bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUInt& lhs,osg::DrawElementsUInt& rhs)
2605{
2606    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2607    return true;
2608}
2609
2610
2611////////////////////////////////////////////////////////////////////////////////////////////
2612//
2613//  Spatialize the scene to accelerate culling
2614//
2615
2616void Optimizer::SpatializeGroupsVisitor::apply(osg::Group& group)
2617{
2618    if (typeid(group)==typeid(osg::Group) || group.asTransform())
2619    {
2620        if (isOperationPermissibleForObject(&group))
2621        {
2622            _groupsToDivideList.insert(&group);
2623        }
2624    }
2625    traverse(group);
2626}
2627
2628void Optimizer::SpatializeGroupsVisitor::apply(osg::Geode& geode)
2629{
2630    if (typeid(geode)==typeid(osg::Geode))
2631    {
2632        if (isOperationPermissibleForObject(&geode))
2633        {
2634            _geodesToDivideList.insert(&geode);
2635        }
2636    }
2637    traverse(geode);
2638}
2639
2640bool Optimizer::SpatializeGroupsVisitor::divide(unsigned int maxNumTreesPerCell)
2641{
2642    bool divided = false;
2643    for(GroupsToDivideList::iterator itr=_groupsToDivideList.begin();
2644        itr!=_groupsToDivideList.end();
2645        ++itr)
2646    {
2647        if (divide(*itr,maxNumTreesPerCell)) divided = true;
2648    }
2649   
2650    for(GeodesToDivideList::iterator geode_itr=_geodesToDivideList.begin();
2651        geode_itr!=_geodesToDivideList.end();
2652        ++geode_itr)
2653    {
2654        if (divide(*geode_itr,maxNumTreesPerCell)) divided = true;
2655    }
2656   
2657    return divided;
2658}
2659
2660bool Optimizer::SpatializeGroupsVisitor::divide(osg::Group* group, unsigned int maxNumTreesPerCell)
2661{
2662    if (group->getNumChildren()<=maxNumTreesPerCell) return false;
2663   
2664    // create the original box.
2665    osg::BoundingBox bb;
2666    unsigned int i;
2667    for(i=0;i<group->getNumChildren();++i)
2668    {
2669        bb.expandBy(group->getChild(i)->getBound().center());
2670    }
2671   
2672    float radius = bb.radius();
2673    float divide_distance = radius*0.7f;
2674    bool xAxis = (bb.xMax()-bb.xMin())>divide_distance;
2675    bool yAxis = (bb.yMax()-bb.yMin())>divide_distance;
2676    bool zAxis = (bb.zMax()-bb.zMin())>divide_distance;
2677
2678    OSG_NOTIFY(osg::INFO)<<"Dividing "<<group->className()<<"  num children = "<<group->getNumChildren()<<"  xAxis="<<xAxis<<"  yAxis="<<yAxis<<"   zAxis="<<zAxis<<std::endl;
2679   
2680    if (!xAxis && !yAxis && !zAxis)
2681    {
2682        OSG_NOTIFY(osg::INFO)<<"  No axis to divide, stopping division."<<std::endl;
2683        return false;
2684    }
2685   
2686    unsigned int numChildrenOnEntry = group->getNumChildren();
2687   
2688    typedef std::pair< osg::BoundingBox, osg::ref_ptr<osg::Group> > BoxGroupPair;
2689    typedef std::vector< BoxGroupPair > Boxes;
2690    Boxes boxes;
2691    boxes.push_back( BoxGroupPair(bb,new osg::Group) );
2692
2693    // divide up on each axis   
2694    if (xAxis)
2695    {
2696        unsigned int numCellsToDivide=boxes.size();
2697        for(unsigned int i=0;i<numCellsToDivide;++i)
2698        {
2699            osg::BoundingBox& orig_cell = boxes[i].first;
2700            osg::BoundingBox new_cell = orig_cell;
2701
2702            float xCenter = (orig_cell.xMin()+orig_cell.xMax())*0.5f;
2703            orig_cell.xMax() = xCenter;
2704            new_cell.xMin() = xCenter;
2705
2706            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2707        }
2708    }
2709
2710    if (yAxis)
2711    {
2712        unsigned int numCellsToDivide=boxes.size();
2713        for(unsigned int i=0;i<numCellsToDivide;++i)
2714        {
2715            osg::BoundingBox& orig_cell = boxes[i].first;
2716            osg::BoundingBox new_cell = orig_cell;
2717
2718            float yCenter = (orig_cell.yMin()+orig_cell.yMax())*0.5f;
2719            orig_cell.yMax() = yCenter;
2720            new_cell.yMin() = yCenter;
2721
2722            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2723        }
2724    }
2725
2726    if (zAxis)
2727    {
2728        unsigned int numCellsToDivide=boxes.size();
2729        for(unsigned int i=0;i<numCellsToDivide;++i)
2730        {
2731            osg::BoundingBox& orig_cell = boxes[i].first;
2732            osg::BoundingBox new_cell = orig_cell;
2733
2734            float zCenter = (orig_cell.zMin()+orig_cell.zMax())*0.5f;
2735            orig_cell.zMax() = zCenter;
2736            new_cell.zMin() = zCenter;
2737
2738            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2739        }
2740    }
2741
2742
2743    // create the groups to drop the children into
2744   
2745
2746    // bin each child into associated bb group
2747    typedef std::vector< osg::ref_ptr<osg::Node> > NodeList;
2748    NodeList unassignedList;
2749    for(i=0;i<group->getNumChildren();++i)
2750    {
2751        bool assigned = false;
2752        osg::Vec3 center = group->getChild(i)->getBound().center();
2753        for(Boxes::iterator itr=boxes.begin();
2754            itr!=boxes.end() && !assigned;
2755            ++itr)
2756        {
2757            if (itr->first.contains(center))
2758            {
2759                // move child from main group into bb group.
2760                (itr->second)->addChild(group->getChild(i));
2761                assigned = true;
2762            }
2763        }
2764        if (!assigned)
2765        {
2766            unassignedList.push_back(group->getChild(i));
2767        }
2768    }
2769
2770
2771    // now transfer nodes across, by :
2772    //      first removing from the original group,
2773    //      add in the bb groups
2774    //      add then the unassigned children.
2775   
2776   
2777    // first removing from the original group,
2778    group->removeChildren(0,group->getNumChildren());
2779   
2780    // add in the bb groups
2781    typedef std::vector< osg::ref_ptr<osg::Group> > GroupList;
2782    GroupList groupsToDivideList;
2783    for(Boxes::iterator itr=boxes.begin();
2784        itr!=boxes.end();
2785        ++itr)
2786    {
2787        // move child from main group into bb group.
2788        osg::Group* bb_group = (itr->second).get();
2789        if (bb_group->getNumChildren()>0)
2790        {
2791            if (bb_group->getNumChildren()==1)
2792            {
2793                group->addChild(bb_group->getChild(0));
2794            }
2795            else
2796            {
2797                group->addChild(bb_group);
2798                if (bb_group->getNumChildren()>maxNumTreesPerCell)
2799                {
2800                    groupsToDivideList.push_back(bb_group);
2801                }
2802            }
2803        }
2804    }
2805   
2806   
2807    // add then the unassigned children.
2808    for(NodeList::iterator nitr=unassignedList.begin();
2809        nitr!=unassignedList.end();
2810        ++nitr)
2811    {
2812        group->addChild(nitr->get());
2813    }
2814
2815    // now call divide on all groups that require it.
2816    for(GroupList::iterator gitr=groupsToDivideList.begin();
2817        gitr!=groupsToDivideList.end();
2818        ++gitr)
2819    {
2820        divide(gitr->get(),maxNumTreesPerCell);
2821    }
2822
2823    return (numChildrenOnEntry<group->getNumChildren());
2824   
2825}
2826
2827bool Optimizer::SpatializeGroupsVisitor::divide(osg::Geode* geode, unsigned int maxNumTreesPerCell)
2828{
2829
2830    if (geode->getNumDrawables()<=maxNumTreesPerCell) return false;
2831   
2832    // create the original box.
2833    osg::BoundingBox bb;
2834    unsigned int i;
2835    for(i=0; i<geode->getNumDrawables(); ++i)
2836    {
2837        bb.expandBy(geode->getDrawable(i)->getBound().center());
2838    }
2839   
2840    float radius = bb.radius();
2841    float divide_distance = radius*0.7f;
2842    bool xAxis = (bb.xMax()-bb.xMin())>divide_distance;
2843    bool yAxis = (bb.yMax()-bb.yMin())>divide_distance;
2844    bool zAxis = (bb.zMax()-bb.zMin())>divide_distance;
2845
2846    OSG_NOTIFY(osg::INFO)<<"INFO "<<geode->className()<<"  num drawables = "<<geode->getNumDrawables()<<"  xAxis="<<xAxis<<"  yAxis="<<yAxis<<"   zAxis="<<zAxis<<std::endl;
2847   
2848    if (!xAxis && !yAxis && !zAxis)
2849    {
2850        OSG_NOTIFY(osg::INFO)<<"  No axis to divide, stopping division."<<std::endl;
2851        return false;
2852    }
2853   
2854    osg::Node::ParentList parents = geode->getParents();
2855    if (parents.empty())
2856    {
2857        OSG_NOTIFY(osg::INFO)<<"  Cannot perform spatialize on root Geode, add a Group above it to allow subdivision."<<std::endl;
2858        return false;
2859    }
2860
2861    osg::ref_ptr<osg::Group> group = new osg::Group;
2862    group->setName(geode->getName());
2863    group->setStateSet(geode->getStateSet());
2864    for(i=0; i<geode->getNumDrawables(); ++i)
2865    {
2866        osg::Geode* newGeode = new osg::Geode;
2867        newGeode->addDrawable(geode->getDrawable(i));
2868        group->addChild(newGeode);
2869    }
2870   
2871    divide(group.get(), maxNumTreesPerCell);
2872   
2873    // keep reference around to prevent it being deleted.
2874    osg::ref_ptr<osg::Geode> keepRefGeode = geode;
2875   
2876    for(osg::Node::ParentList::iterator itr = parents.begin();
2877        itr != parents.end();
2878        ++itr)
2879    {
2880        (*itr)->replaceChild(geode, group.get());
2881    }
2882   
2883    return true;
2884}
2885
2886////////////////////////////////////////////////////////////////////////////////////////////
2887//
2888//  Duplicated subgraphs which are shared
2889//
2890
2891void Optimizer::CopySharedSubgraphsVisitor::apply(osg::Node& node)
2892{
2893    if (node.getNumParents()>1 && isOperationPermissibleForObject(&node))
2894    {
2895        _sharedNodeList.insert(&node);
2896    }
2897    traverse(node);
2898}
2899
2900void Optimizer::CopySharedSubgraphsVisitor::copySharedNodes()
2901{
2902    OSG_NOTIFY(osg::INFO)<<"Shared node "<<_sharedNodeList.size()<<std::endl;
2903    for(SharedNodeList::iterator itr=_sharedNodeList.begin();
2904        itr!=_sharedNodeList.end();
2905        ++itr)
2906    {
2907        OSG_NOTIFY(osg::INFO)<<"   No parents "<<(*itr)->getNumParents()<<std::endl;
2908        osg::Node* node = *itr;
2909        for(unsigned int i=node->getNumParents()-1;i>0;--i)
2910        {
2911            // create a clone.
2912            osg::ref_ptr<osg::Object> new_object = node->clone(osg::CopyOp::DEEP_COPY_NODES |
2913                                                          osg::CopyOp::DEEP_COPY_DRAWABLES);
2914            // cast it to node.                                             
2915            osg::Node* new_node = dynamic_cast<osg::Node*>(new_object.get());
2916
2917            // replace the node by new_new
2918            if (new_node) node->getParent(i)->replaceChild(node,new_node);
2919        }
2920    }
2921}
2922
2923
2924////////////////////////////////////////////////////////////////////////////////////////////
2925//
2926//  Set the attributes of textures up.
2927//
2928
2929
2930void Optimizer::TextureVisitor::apply(osg::Node& node)
2931{
2932   
2933    osg::StateSet* ss = node.getStateSet();
2934    if (ss &&
2935        isOperationPermissibleForObject(&node) &&
2936        isOperationPermissibleForObject(ss))
2937    {
2938        apply(*ss);
2939    }
2940
2941    traverse(node);
2942}
2943
2944void Optimizer::TextureVisitor::apply(osg::Geode& geode)
2945{
2946    if (!isOperationPermissibleForObject(&geode)) return;
2947
2948    osg::StateSet* ss = geode.getStateSet();
2949   
2950    if (ss && isOperationPermissibleForObject(ss))
2951    {
2952        apply(*ss);
2953    }
2954
2955    for(unsigned int i=0;i<geode.getNumDrawables();++i)
2956    {
2957        osg::Drawable* drawable = geode.getDrawable(i);
2958        if (drawable)
2959        {
2960            ss = drawable->getStateSet();
2961            if (ss &&
2962               isOperationPermissibleForObject(drawable) &&
2963               isOperationPermissibleForObject(ss))
2964            {
2965                apply(*ss);
2966            }
2967        }
2968    }
2969}
2970
2971void Optimizer::TextureVisitor::apply(osg::StateSet& stateset)
2972{
2973    for(unsigned int i=0;i<stateset.getTextureAttributeList().size();++i)
2974    {
2975        osg::StateAttribute* sa = stateset.getTextureAttribute(i,osg::StateAttribute::TEXTURE);
2976        osg::Texture* texture = dynamic_cast<osg::Texture*>(sa);
2977        if (texture && isOperationPermissibleForObject(texture))
2978        {
2979            apply(*texture);
2980        }
2981    }
2982}
2983
2984void Optimizer::TextureVisitor::apply(osg::Texture& texture)
2985{
2986    if (_changeAutoUnRef)
2987    {
2988        unsigned numImageStreams = 0;
2989        for (unsigned int i=0; i<texture.getNumImages(); ++i)
2990        {
2991            osg::ImageStream* is = dynamic_cast<osg::ImageStream*>(texture.getImage(i));
2992            if (is) ++numImageStreams;
2993        }
2994       
2995        if (numImageStreams==0)
2996        {
2997            texture.setUnRefImageDataAfterApply(_valueAutoUnRef);
2998        }
2999    }
3000   
3001    if (_changeClientImageStorage)
3002    {
3003        texture.setClientStorageHint(_valueClientImageStorage);
3004    }
3005   
3006    if (_changeAnisotropy)
3007    {
3008        texture.setMaxAnisotropy(_valueAnisotropy);
3009    }
3010
3011}
3012
3013////////////////////////////////////////////////////////////////////////////
3014// Merge geodes
3015////////////////////////////////////////////////////////////////////////////
3016
3017void Optimizer::MergeGeodesVisitor::apply(osg::Group& group)
3018{
3019    if (typeid(group)==typeid(osg::Group)) mergeGeodes(group);
3020    traverse(group);
3021}
3022
3023struct LessGeode
3024{
3025    bool operator() (const osg::Geode* lhs,const osg::Geode* rhs) const
3026    {
3027        if (lhs->getNodeMask()<rhs->getNodeMask()) return true;
3028        if (lhs->getNodeMask()>rhs->getNodeMask()) return false;
3029
3030        return (lhs->getStateSet()<rhs->getStateSet());
3031    }
3032};
3033
3034bool Optimizer::MergeGeodesVisitor::mergeGeodes(osg::Group& group)
3035{
3036    if (!isOperationPermissibleForObject(&group)) return false;
3037
3038    typedef std::vector< osg::Geode* >                      DuplicateList;
3039    typedef std::map<osg::Geode*,DuplicateList,LessGeode>   GeodeDuplicateMap;
3040
3041    unsigned int i;
3042    osg::NodeList children;
3043    children.resize(group.getNumChildren());
3044    for (i=0; i<group.getNumChildren(); ++i)
3045    {
3046        // keep a reference to this child so we can safely clear the group of all children
3047        // this is done so we don't have to do a search and remove from the list later on.
3048        children[i] = group.getChild(i);
3049    }
3050   
3051    // remove all children
3052    group.removeChildren(0,group.getNumChildren());
3053
3054    GeodeDuplicateMap geodeDuplicateMap;
3055    for (i=0; i<children.size(); ++i)
3056    {
3057        osg::Node* child = children[i].get();
3058
3059        if (typeid(*child)==typeid(osg::Geode))
3060        {
3061            osg::Geode* geode = static_cast<osg::Geode*>(child);
3062            geodeDuplicateMap[geode].push_back(geode);
3063        }
3064        else
3065        {
3066            // not a geode so just add back into group as its a normal child
3067            group.addChild(child);
3068        }
3069    }
3070
3071    // if no geodes then just return.
3072    if (geodeDuplicateMap.empty()) return false;
3073   
3074    OSG_NOTIFY(osg::INFO)<<"mergeGeodes in group '"<<group.getName()<<"' "<<geodeDuplicateMap.size()<<std::endl;
3075   
3076    // merge
3077    for(GeodeDuplicateMap::iterator itr=geodeDuplicateMap.begin();
3078        itr!=geodeDuplicateMap.end();
3079        ++itr)
3080    {
3081        if (itr->second.size()>1)
3082        {
3083            osg::Geode* lhs = itr->second[0];
3084
3085            // add geode back into group
3086            group.addChild(lhs);
3087           
3088            for(DuplicateList::iterator dupItr=itr->second.begin()+1;
3089                dupItr!=itr->second.end();
3090                ++dupItr)
3091            {
3092                osg::Geode* rhs = *dupItr;
3093                mergeGeode(*lhs,*rhs);
3094            }
3095        }
3096        else
3097        {
3098            osg::Geode* lhs = itr->second[0];
3099
3100            // add geode back into group
3101            group.addChild(lhs);
3102        }
3103    }
3104
3105    return true;
3106}
3107
3108bool Optimizer::MergeGeodesVisitor::mergeGeode(osg::Geode& lhs, osg::Geode& rhs)
3109{
3110    for (unsigned int i=0; i<rhs.getNumDrawables(); ++i)
3111    {
3112        lhs.addDrawable(rhs.getDrawable(i));
3113    }
3114
3115    return true;
3116}
3117
3118
3119
3120////////////////////////////////////////////////////////////////////////////
3121// FlattenBillboardVisitor
3122////////////////////////////////////////////////////////////////////////////
3123void Optimizer::FlattenBillboardVisitor::reset()
3124{
3125    _billboards.clear();
3126}
3127
3128void Optimizer::FlattenBillboardVisitor::apply(osg::Billboard& billboard)
3129{
3130    _billboards[&billboard].push_back(getNodePath());
3131}
3132
3133void Optimizer::FlattenBillboardVisitor::process()
3134{
3135    for(BillboardNodePathMap::iterator itr = _billboards.begin();
3136        itr != _billboards.end();
3137        ++itr)
3138    {
3139        bool mergeAcceptable = true;   
3140
3141        osg::ref_ptr<osg::Billboard> billboard = itr->first;
3142
3143        NodePathList& npl = itr->second;
3144        osg::Group* mainGroup = 0;
3145        if (npl.size()>1)
3146        {       
3147            for(NodePathList::iterator nitr = npl.begin();
3148                nitr != npl.end();
3149                ++nitr)
3150            {
3151                osg::NodePath& np = *nitr;
3152                if (np.size()>=3)
3153                {
3154                    osg::Group* group = dynamic_cast<osg::Group*>(np[np.size()-3]);
3155                    if (mainGroup==0) mainGroup = group;
3156
3157                    osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(np[np.size()-2]);
3158
3159                    if (group == mainGroup &&
3160                        np[np.size()-1]==billboard.get() &&
3161                        mt && mt->getDataVariance()==osg::Object::STATIC &&
3162                        mt->getNumChildren()==1)
3163                    {
3164                        const osg::Matrix& m = mt->getMatrix();
3165                        mergeAcceptable = (m(0,0)==1.0 && m(0,1)==0.0 && m(0,2)==0.0 && m(0,3)==0.0 &&
3166                                           m(1,0)==0.0 && m(1,1)==1.0 && m(1,2)==0.0 && m(1,3)==0.0 &&
3167                                           m(2,0)==0.0 && m(2,1)==0.0 && m(2,2)==1.0 && m(2,3)==0.0 &&
3168                                           m(3,3)==1.0);
3169                    }
3170                    else
3171                    {
3172                       mergeAcceptable = false;
3173                    }
3174                }
3175                else
3176                {
3177                    mergeAcceptable = false;
3178                }
3179            }
3180        }
3181        else
3182        {
3183            mergeAcceptable = false;
3184        }
3185
3186        if (mergeAcceptable)
3187        {
3188            osg::Billboard* new_billboard = new osg::Billboard;
3189            new_billboard->setMode(billboard->getMode());
3190            new_billboard->setAxis(billboard->getAxis());
3191            new_billboard->setStateSet(billboard->getStateSet());
3192            new_billboard->setName(billboard->getName());               
3193
3194            mainGroup->addChild(new_billboard);
3195
3196            typedef std::set<osg::MatrixTransform*> MatrixTransformSet;
3197            MatrixTransformSet mts;
3198
3199            for(NodePathList::iterator nitr = npl.begin();
3200                nitr != npl.end();
3201                ++nitr)
3202            {
3203                osg::NodePath& np = *nitr;
3204                osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(np[np.size()-2]);
3205                mts.insert(mt);
3206            }
3207
3208            for(MatrixTransformSet::iterator mitr = mts.begin();
3209                mitr != mts.end();
3210                ++mitr)
3211            {
3212                osg::MatrixTransform* mt = *mitr;
3213                for(unsigned int i=0; i<billboard->getNumDrawables(); ++i)
3214                {
3215                    new_billboard->addDrawable(billboard->getDrawable(i),
3216                                               billboard->getPosition(i)*mt->getMatrix());
3217                }
3218                mainGroup->removeChild(mt);
3219            }
3220        }
3221    }
3222
3223}
3224
3225
3226
3227////////////////////////////////////////////////////////////////////////////
3228// TextureAtlasBuilder
3229////////////////////////////////////////////////////////////////////////////
3230
3231Optimizer::TextureAtlasBuilder::TextureAtlasBuilder():
3232    _maximumAtlasWidth(2048),
3233    _maximumAtlasHeight(2048),
3234    _margin(8)
3235{
3236}
3237
3238void Optimizer::TextureAtlasBuilder::reset()
3239{
3240    _sourceList.clear();
3241    _atlasList.clear();
3242}
3243
3244void Optimizer::TextureAtlasBuilder::setMaximumAtlasSize(unsigned int width, unsigned int height)
3245{
3246    _maximumAtlasWidth = width;
3247    _maximumAtlasHeight = height;
3248}
3249
3250void Optimizer::TextureAtlasBuilder::setMargin(unsigned int margin)
3251{
3252    _margin = margin;
3253}
3254
3255void Optimizer::TextureAtlasBuilder::addSource(const osg::Image* image)
3256{
3257    if (!getSource(image)) _sourceList.push_back(new Source(image));
3258}
3259
3260void Optimizer::TextureAtlasBuilder::addSource(const osg::Texture2D* texture)
3261{
3262    if (!getSource(texture)) _sourceList.push_back(new Source(texture));
3263}
3264
3265void Optimizer::TextureAtlasBuilder::buildAtlas()
3266{
3267    // assign the source to the atlas
3268    _atlasList.clear();
3269    for(SourceList::iterator sitr = _sourceList.begin();
3270        sitr != _sourceList.end();
3271        ++sitr)
3272    {
3273        Source* source = sitr->get();
3274        if (source->suitableForAtlas(_maximumAtlasWidth,_maximumAtlasHeight,_margin))
3275        {
3276            bool addedSourceToAtlas = false;
3277            for(AtlasList::iterator aitr = _atlasList.begin();
3278                aitr != _atlasList.end() && !addedSourceToAtlas;
3279                ++aitr)
3280            {
3281                OSG_NOTIFY(osg::INFO)<<"checking source "<<source->_image->getFileName()<<" to see it it'll fit in atlas "<<aitr->get()<<std::endl;
3282                if ((*aitr)->doesSourceFit(source))
3283                {
3284                    addedSourceToAtlas = true;
3285                    (*aitr)->addSource(source);
3286                }
3287                else
3288                {
3289                    OSG_NOTIFY(osg::INFO)<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<aitr->get()<<std::endl;
3290                }
3291            }
3292
3293            if (!addedSourceToAtlas)
3294            {
3295                OSG_NOTIFY(osg::INFO)<<"creating new Atlas for "<<source->_image->getFileName()<<std::endl;
3296
3297                osg::ref_ptr<Atlas> atlas = new Atlas(_maximumAtlasWidth,_maximumAtlasHeight,_margin);
3298                _atlasList.push_back(atlas.get());
3299               
3300                atlas->addSource(source);
3301            }
3302        }
3303    }
3304   
3305    // build the atlas which are suitable for use, and discard the rest.
3306    AtlasList activeAtlasList;
3307    for(AtlasList::iterator aitr = _atlasList.begin();
3308        aitr != _atlasList.end();
3309        ++aitr)
3310    {
3311        Atlas* atlas = aitr->get();
3312
3313        if (atlas->_sourceList.size()==1)
3314        {
3315            // no point building an atlas with only one entry
3316            // so disconnect the source.
3317            Source* source = atlas->_sourceList[0].get();
3318            source->_atlas = 0;
3319            atlas->_sourceList.clear();
3320        }
3321       
3322        if (!(atlas->_sourceList.empty()))
3323        {
3324            std::stringstream ostr;
3325            ostr<<"atlas_"<<activeAtlasList.size()<<".rgb";
3326            atlas->_image->setFileName(ostr.str());
3327       
3328            activeAtlasList.push_back(atlas);
3329            atlas->clampToNearestPowerOfTwoSize();
3330            atlas->copySources();
3331           
3332        }
3333    }
3334   
3335    // keep only the active atlas'
3336    _atlasList.swap(activeAtlasList);
3337
3338}
3339
3340osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(unsigned int i)
3341{
3342    Source* source = _sourceList[i].get();
3343    Atlas* atlas = source ? source->_atlas : 0;
3344    return atlas ? atlas->_image.get() : 0;
3345}
3346
3347osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(unsigned int i)
3348{
3349    Source* source = _sourceList[i].get();
3350    Atlas* atlas = source ? source->_atlas : 0;
3351    return atlas ? atlas->_texture.get() : 0;
3352}
3353
3354osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(unsigned int i)
3355{
3356    Source* source = _sourceList[i].get();
3357    return source ? source->computeTextureMatrix() : osg::Matrix();
3358}
3359
3360osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(const osg::Image* image)
3361{
3362    Source* source = getSource(image);
3363    Atlas* atlas = source ? source->_atlas : 0;
3364    return atlas ? atlas->_image.get() : 0;
3365}
3366
3367osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(const osg::Image* image)
3368{
3369    Source* source = getSource(image);
3370    Atlas* atlas = source ? source->_atlas : 0;
3371    return atlas ? atlas->_texture.get() : 0;
3372}
3373
3374osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(const osg::Image* image)
3375{
3376    Source* source = getSource(image);
3377    return source ? source->computeTextureMatrix() : osg::Matrix();
3378}
3379
3380osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(const osg::Texture2D* texture)
3381{
3382    Source* source = getSource(texture);
3383    Atlas* atlas = source ? source->_atlas : 0;
3384    return atlas ? atlas->_image.get() : 0;
3385}
3386
3387osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(const osg::Texture2D* texture)
3388{
3389    Source* source = getSource(texture);
3390    Atlas* atlas = source ? source->_atlas : 0;
3391    return atlas ? atlas->_texture.get() : 0;
3392}
3393
3394osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(const osg::Texture2D* texture)
3395{
3396    Source* source = getSource(texture);
3397    return source ? source->computeTextureMatrix() : osg::Matrix();
3398}
3399
3400Optimizer::TextureAtlasBuilder::Source* Optimizer::TextureAtlasBuilder::getSource(const osg::Image* image)
3401{
3402    for(SourceList::iterator itr = _sourceList.begin();
3403        itr != _sourceList.end();
3404        ++itr)
3405    {
3406        if ((*itr)->_image == image) return itr->get();
3407    }
3408    return 0;
3409}
3410
3411Optimizer::TextureAtlasBuilder::Source* Optimizer::TextureAtlasBuilder::getSource(const osg::Texture2D* texture)
3412{
3413    for(SourceList::iterator itr = _sourceList.begin();
3414        itr != _sourceList.end();
3415        ++itr)
3416    {
3417        if ((*itr)->_texture == texture) return itr->get();
3418    }
3419    return 0;
3420}
3421
3422bool Optimizer::TextureAtlasBuilder::Source::suitableForAtlas(unsigned int maximumAtlasWidth, unsigned int maximumAtlasHeight, unsigned int margin)
3423{
3424    if (!_image) return false;
3425   
3426    // size too big?
3427    if (_image->s()+margin*2 > maximumAtlasWidth) return false;
3428    if (_image->t()+margin*2 > maximumAtlasHeight) return false;
3429   
3430    switch(_image->getPixelFormat())
3431    {
3432        case(GL_COMPRESSED_ALPHA_ARB):
3433        case(GL_COMPRESSED_INTENSITY_ARB):
3434        case(GL_COMPRESSED_LUMINANCE_ALPHA_ARB):
3435        case(GL_COMPRESSED_LUMINANCE_ARB):
3436        case(GL_COMPRESSED_RGBA_ARB):
3437        case(GL_COMPRESSED_RGB_ARB):
3438        case(GL_COMPRESSED_RGB_S3TC_DXT1_EXT):
3439        case(GL_COMPRESSED_RGBA_S3TC_DXT1_EXT):
3440        case(GL_COMPRESSED_RGBA_S3TC_DXT3_EXT):
3441        case(GL_COMPRESSED_RGBA_S3TC_DXT5_EXT):
3442            // can't handle compressed textures inside an atlas
3443            return false;
3444        default:
3445            break;
3446    }
3447
3448    if ((_image->getPixelSizeInBits() % 8) != 0)
3449    {
3450        // pixel size not byte aligned so report as not suitable to prevent other atlas code from having problems with byte boundaries.
3451        return false;
3452    }
3453
3454    if (_texture.valid())
3455    {
3456
3457        if (_texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
3458            _texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR)
3459        {
3460            // can't support repeating textures in texture atlas
3461            return false;
3462        }
3463
3464        if (_texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
3465            _texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR)
3466        {
3467            // can't support repeating textures in texture atlas
3468            return false;
3469        }
3470
3471        if (_texture->getReadPBuffer()!=0)
3472        {
3473            // pbuffer textures not suitable
3474            return false;
3475        }
3476    }
3477   
3478    return true;
3479}
3480
3481osg::Matrix Optimizer::TextureAtlasBuilder::Source::computeTextureMatrix() const
3482{
3483    if (!_atlas) return osg::Matrix();
3484    if (!_image) return osg::Matrix();
3485    if (!(_atlas->_image)) return osg::Matrix();
3486   
3487    return osg::Matrix::scale(float(_image->s())/float(_atlas->_image->s()), float(_image->t())/float(_atlas->_image->t()), 1.0)*
3488           osg::Matrix::translate(float(_x)/float(_atlas->_image->s()), float(_y)/float(_atlas->_image->t()), 0.0);
3489}
3490
3491bool Optimizer::TextureAtlasBuilder::Atlas::doesSourceFit(Source* source)
3492{
3493    // does the source have a valid image?
3494    const osg::Image* sourceImage = source->_image.get();
3495    if (!sourceImage) return false;
3496   
3497    // does pixel format match?
3498    if (_image.valid())
3499    {
3500        if (_image->getPixelFormat() != sourceImage->getPixelFormat()) return false;
3501        if (_image->getDataType() != sourceImage->getDataType()) return false;
3502    }
3503   
3504    const osg::Texture2D* sourceTexture = source->_texture.get();
3505    if (sourceTexture)
3506    {
3507        if (sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
3508            sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR)
3509        {
3510            // can't support repeating textures in texture atlas
3511            return false;
3512        }
3513
3514        if (sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
3515            sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR)
3516        {
3517            // can't support repeating textures in texture atlas
3518            return false;
3519        }
3520
3521        if (sourceTexture->getReadPBuffer()!=0)
3522        {
3523            // pbuffer textures not suitable
3524            return false;
3525        }
3526
3527        if (_texture.valid())
3528        {
3529
3530            bool sourceUsesBorder = sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::CLAMP_TO_BORDER ||
3531                                    sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::CLAMP_TO_BORDER;
3532
3533            bool atlasUsesBorder = sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::CLAMP_TO_BORDER ||
3534                                   sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::CLAMP_TO_BORDER;
3535
3536            if (sourceUsesBorder!=atlasUsesBorder)
3537            {
3538                // border wrapping does not match
3539                return false;
3540            }
3541
3542            if (sourceUsesBorder)
3543            {
3544                // border colours don't match
3545                if (_texture->getBorderColor() != sourceTexture->getBorderColor()) return false;
3546            }
3547           
3548            if (_texture->getFilter(osg::Texture2D::MIN_FILTER) != sourceTexture->getFilter(osg::Texture2D::MIN_FILTER))
3549            {
3550                // inconsitent min filters
3551                return false;
3552            }
3553 
3554            if (_texture->getFilter(osg::Texture2D::MAG_FILTER) != sourceTexture->getFilter(osg::Texture2D::MAG_FILTER))
3555            {
3556                // inconsitent mag filters
3557                return false;
3558            }
3559           
3560            if (_texture->getMaxAnisotropy() != sourceTexture->getMaxAnisotropy())
3561            {
3562                // anisotropy different.
3563                return false;
3564            }
3565           
3566            if (_texture->getInternalFormat() != sourceTexture->getInternalFormat())
3567            {
3568                // internal formats inconistent
3569                return false;
3570            }
3571           
3572            if (_texture->getShadowCompareFunc() != sourceTexture->getShadowCompareFunc())
3573            {
3574                // shadow functions inconsitent
3575                return false;
3576            }
3577               
3578            if (_texture->getShadowTextureMode() != sourceTexture->getShadowTextureMode())
3579            {
3580                // shadow texture mode inconsitent
3581                return false;
3582            }
3583
3584            if (_texture->getShadowAmbient() != sourceTexture->getShadowAmbient())
3585            {
3586                // shadow ambient inconsitent
3587                return false;
3588            }
3589        }
3590    }
3591   
3592    if (sourceImage->s() + 2*_margin > _maximumAtlasWidth)
3593    {
3594        // image too big for Atlas
3595        return false;
3596    }
3597   
3598    if (sourceImage->t() + 2*_margin > _maximumAtlasHeight)
3599    {
3600        // image too big for Atlas
3601        return false;
3602    }
3603
3604    if ((_y + sourceImage->t() + 2*_margin) > _maximumAtlasHeight)
3605    {
3606        // image doesn't have up space in height axis.
3607        return false;
3608    }
3609
3610    // does the source fit in the current row?
3611    if ((_x + sourceImage->s() + 2*_margin) <= _maximumAtlasWidth)
3612    {
3613        // yes it fits :-)
3614        OSG_NOTIFY(osg::INFO)<<"Fits in current row"<<std::endl;
3615        return true;
3616    }
3617
3618    // does the source fit in the new row up?
3619    if ((_height + sourceImage->t() + 2*_margin) <= _maximumAtlasHeight)
3620    {
3621        // yes it fits :-)
3622        OSG_NOTIFY(osg::INFO)<<"Fits in next row"<<std::endl;
3623        return true;
3624    }
3625   
3626    // no space for the texture
3627    return false;
3628}
3629
3630bool Optimizer::TextureAtlasBuilder::Atlas::addSource(Source* source)
3631{
3632    // double check source is compatible
3633    if (!doesSourceFit(source))
3634    {
3635        OSG_NOTIFY(osg::INFO)<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<this<<std::endl;
3636        return false;
3637    }
3638   
3639    const osg::Image* sourceImage = source->_image.get();
3640    const osg::Texture2D* sourceTexture = source->_texture.get();
3641
3642    if (!_image)
3643    {
3644        // need to create an image of the same pixel format to store the atlas in
3645        _image = new osg::Image;
3646        _image->setPixelFormat(sourceImage->getPixelFormat());
3647        _image->setDataType(sourceImage->getDataType());
3648    }
3649   
3650    if (!_texture && sourceTexture)
3651    {
3652        _texture = new osg::Texture2D(_image.get());
3653
3654        _texture->setWrap(osg::Texture2D::WRAP_S, sourceTexture->getWrap(osg::Texture2D::WRAP_S));
3655        _texture->setWrap(osg::Texture2D::WRAP_T, sourceTexture->getWrap(osg::Texture2D::WRAP_T));
3656       
3657        _texture->setBorderColor(sourceTexture->getBorderColor());
3658        _texture->setBorderWidth(0);
3659           
3660        _texture->setFilter(osg::Texture2D::MIN_FILTER, sourceTexture->getFilter(osg::Texture2D::MIN_FILTER));
3661        _texture->setFilter(osg::Texture2D::MAG_FILTER, sourceTexture->getFilter(osg::Texture2D::MAG_FILTER));
3662
3663        _texture->setMaxAnisotropy(sourceTexture->getMaxAnisotropy());
3664
3665        _texture->setInternalFormat(sourceTexture->getInternalFormat());
3666
3667        _texture->setShadowCompareFunc(sourceTexture->getShadowCompareFunc());
3668        _texture->setShadowTextureMode(sourceTexture->getShadowTextureMode());
3669        _texture->setShadowAmbient(sourceTexture->getShadowAmbient());
3670
3671    }
3672
3673    // now work out where to fit it, first try current row.
3674    if ((_x + sourceImage->s() + 2*_margin) <= _maximumAtlasWidth)
3675    {
3676        // yes it fits, so add the source to the atlas's list of sources it contains
3677        _sourceList.push_back(source);
3678
3679        OSG_NOTIFY(osg::INFO)<<"current row insertion, source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3680
3681        // set up the source so it knows where it is in the atlas
3682        source->_x = _x + _margin;
3683        source->_y = _y + _margin;
3684        source->_atlas = this;
3685       
3686        // move the atlas' cursor along to the right
3687        _x += sourceImage->s() + 2*_margin;
3688       
3689        if (_x > _width) _width = _x;
3690       
3691        unsigned int localTop = _y + sourceImage->t() + 2*_margin;
3692        if ( localTop > _height) _height = localTop;
3693
3694        return true;
3695    }
3696
3697    // does the source fit in the new row up?
3698    if ((_height + sourceImage->t() + 2*_margin) <= _maximumAtlasHeight)
3699    {
3700        // now row so first need to reset the atlas cursor
3701        _x = 0;
3702        _y = _height;
3703
3704        // yes it fits, so add the source to the atlas' list of sources it contains
3705        _sourceList.push_back(source);
3706
3707        OSG_NOTIFY(osg::INFO)<<"next row insertion, source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3708
3709        // set up the source so it knows where it is in the atlas
3710        source->_x = _x + _margin;
3711        source->_y = _y + _margin;
3712        source->_atlas = this;
3713       
3714        // move the atlas' cursor along to the right
3715        _x += sourceImage->s() + 2*_margin;
3716
3717        if (_x > _width) _width = _x;
3718
3719        _height = _y + sourceImage->t() + 2*_margin;
3720
3721        OSG_NOTIFY(osg::INFO)<<"source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3722
3723        return true;
3724    }
3725
3726    OSG_NOTIFY(osg::INFO)<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<this<<std::endl;
3727
3728    // shouldn't get here, unless doesSourceFit isn't working...
3729    return false;
3730}
3731
3732void Optimizer::TextureAtlasBuilder::Atlas::clampToNearestPowerOfTwoSize()
3733{
3734    unsigned int w = 1;
3735    while (w<_width) w *= 2;
3736
3737    unsigned int h = 1;
3738    while (h<_height) h *= 2;
3739   
3740    OSG_NOTIFY(osg::INFO)<<"Clamping "<<_width<<", "<<_height<<" to "<<w<<","<<h<<std::endl;
3741   
3742    _width = w;
3743    _height = h;
3744}
3745
3746
3747void Optimizer::TextureAtlasBuilder::Atlas::copySources()
3748{
3749    OSG_NOTIFY(osg::INFO)<<"Allocated to "<<_width<<","<<_height<<std::endl;
3750    _image->allocateImage(_width,_height,1,
3751                          _image->getPixelFormat(),_image->getDataType(),
3752                          _image->getPacking());
3753                         
3754    {
3755        // clear memory
3756        unsigned int size = _image->getTotalSizeInBytes();
3757        unsigned char* str = _image->data();
3758        for(unsigned int i=0; i<size; ++i) *(str++) = 0;
3759    }       
3760
3761    OSG_NOTIFY(osg::INFO)<<"Atlas::copySources() "<<std::endl;
3762    for(SourceList::iterator itr = _sourceList.begin();
3763        itr !=_sourceList.end();
3764        ++itr)
3765    {
3766        Source* source = itr->get();
3767        Atlas* atlas = source->_atlas;
3768
3769        if (atlas)
3770        {
3771            OSG_NOTIFY(osg::INFO)<<"Copying image "<<source->_image->getFileName()<<" to "<<source->_x<<" ,"<<source->_y<<std::endl;
3772            OSG_NOTIFY(osg::INFO)<<"        image size "<<source->_image->s()<<","<<source->_image->t()<<std::endl;
3773
3774            const osg::Image* sourceImage = source->_image.get();
3775            osg::Image* atlasImage = atlas->_image.get();
3776
3777            unsigned int rowSize = sourceImage->getRowSizeInBytes();
3778            unsigned int pixelSizeInBits = sourceImage->getPixelSizeInBits();
3779            unsigned int pixelSizeInBytes = pixelSizeInBits/8;
3780            unsigned int marginSizeInBytes = pixelSizeInBytes*_margin;
3781
3782            unsigned int x = source->_x;
3783            unsigned int y = source->_y;
3784
3785            int t;
3786            for(t=0; t<sourceImage->t(); ++t, ++y)
3787            {
3788                unsigned char* destPtr = atlasImage->data(x, y);
3789                const unsigned char* sourcePtr = sourceImage->data(0, t);
3790                for(unsigned int i=0; i<rowSize; i++)
3791                {
3792                    *(destPtr++) = *(sourcePtr++);
3793                }
3794            }
3795           
3796            // copy top row margin
3797            y = source->_y + sourceImage->t();
3798            unsigned int m;
3799            for(m=0; m<_margin; ++m, ++y)
3800            {
3801                unsigned char* destPtr = atlasImage->data(x, y);
3802                const unsigned char* sourcePtr = sourceImage->data(0, sourceImage->t()-1);
3803                for(unsigned int i=0; i<rowSize; i++)
3804                {
3805                    *(destPtr++) = *(sourcePtr++);
3806                }
3807               
3808            }
3809           
3810
3811
3812            // copy bottom row margin
3813            y = source->_y-1;
3814            for(m=0; m<_margin; ++m, --y)
3815            {
3816                unsigned char* destPtr = atlasImage->data(x, y);
3817                const unsigned char* sourcePtr = sourceImage->data(0, 0);
3818                for(unsigned int i=0; i<rowSize; i++)
3819                {
3820                    *(destPtr++) = *(sourcePtr++);
3821                }
3822               
3823            }
3824
3825            // copy left column margin
3826            y = source->_y;
3827            for(t=0; t<sourceImage->t(); ++t, ++y)
3828            {
3829                x = source->_x-1;
3830                for(m=0; m<_margin; ++m, --x)
3831                {
3832                    unsigned char* destPtr = atlasImage->data(x, y);
3833                    const unsigned char* sourcePtr = sourceImage->data(0, t);
3834                    for(unsigned int i=0; i<pixelSizeInBytes; i++)
3835                    {
3836                        *(destPtr++) = *(sourcePtr++);
3837                    }
3838                }
3839            }           
3840
3841            // copy right column margin
3842            y = source->_y;
3843            for(t=0; t<sourceImage->t(); ++t, ++y)
3844            {
3845                x = source->_x + sourceImage->s();
3846                for(m=0; m<_margin; ++m, ++x)
3847                {
3848                    unsigned char* destPtr = atlasImage->data(x, y);
3849                    const unsigned char* sourcePtr = sourceImage->data(sourceImage->s()-1, t);
3850                    for(unsigned int i=0; i<pixelSizeInBytes; i++)
3851                    {
3852                        *(destPtr++) = *(sourcePtr++);
3853                    }
3854                }
3855            }           
3856
3857            // copy top left corner margin
3858            y = source->_y + sourceImage->t();
3859            for(m=0; m<_margin; ++m, ++y)
3860            {
3861                unsigned char* destPtr = atlasImage->data(source->_x - _margin, y);
3862                unsigned char* sourcePtr = atlasImage->data(source->_x - _margin, y-1); // copy from row below
3863                for(unsigned int i=0; i<marginSizeInBytes; i++)
3864                {
3865                    *(destPtr++) = *(sourcePtr++);
3866                }
3867            }
3868
3869            // copy top right corner margin
3870            y = source->_y + sourceImage->t();
3871            for(m=0; m<_margin; ++m, ++y)
3872            {
3873                unsigned char* destPtr = atlasImage->data(source->_x + sourceImage->s(), y);
3874                unsigned char* sourcePtr = atlasImage->data(source->_x + sourceImage->s(), y-1); // copy from row below
3875                for(unsigned int i=0; i<marginSizeInBytes; i++)
3876                {
3877                    *(destPtr++) = *(sourcePtr++);
3878                }
3879            }
3880
3881            // copy bottom left corner margin
3882            y = source->_y - 1;
3883            for(m=0; m<_margin; ++m, --y)
3884            {
3885                unsigned char* destPtr = atlasImage->data(source->_x - _margin, y);
3886                unsigned char* sourcePtr = atlasImage->data(source->_x - _margin, y+1); // copy from row below
3887                for(unsigned int i=0; i<marginSizeInBytes; i++)
3888                {
3889                    *(destPtr++) = *(sourcePtr++);
3890                }
3891            }
3892
3893            // copy bottom right corner margin
3894            y = source->_y - 1;
3895            for(m=0; m<_margin; ++m, --y)
3896            {
3897                unsigned char* destPtr = atlasImage->data(source->_x + sourceImage->s(), y);
3898                unsigned char* sourcePtr = atlasImage->data(source->_x + sourceImage->s(), y+1); // copy from row below
3899                for(unsigned int i=0; i<marginSizeInBytes; i++)
3900                {
3901                    *(destPtr++) = *(sourcePtr++);
3902                }
3903            }
3904
3905        }
3906    }
3907}
3908
3909
3910void Optimizer::TextureAtlasVisitor::reset()
3911{
3912    _statesetMap.clear();
3913    _statesetStack.clear();
3914    _textures.clear();
3915    _builder.reset();
3916}
3917
3918bool Optimizer::TextureAtlasVisitor::pushStateSet(osg::StateSet* stateset)
3919{
3920    osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
3921   
3922    // if no textures ignore
3923    if (tal.empty()) return false;
3924   
3925    bool pushStateState = false;
3926
3927    // if already in stateset list ignore
3928    if (_statesetMap.count(stateset)>0)
3929    {
3930        pushStateState = true;
3931    }
3932    else
3933    {
3934        bool containsTexture2D = false;
3935        for(unsigned int unit=0; unit<tal.size(); ++unit)
3936        {
3937            osg::Texture2D* texture2D = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
3938            if (texture2D)
3939            {
3940                containsTexture2D = true;
3941                _textures.insert(texture2D);
3942            }
3943        }
3944
3945        if (containsTexture2D)
3946        {
3947            _statesetMap[stateset];
3948            pushStateState = true;
3949        }
3950    }
3951   
3952    if (pushStateState)
3953    {
3954        _statesetStack.push_back(stateset);
3955    }
3956
3957   
3958    return pushStateState; 
3959}
3960
3961void Optimizer::TextureAtlasVisitor::popStateSet()
3962{
3963    _statesetStack.pop_back();
3964}
3965
3966void Optimizer::TextureAtlasVisitor::apply(osg::Node& node)
3967{
3968    bool pushedStateState = false;
3969   
3970    osg::StateSet* ss = node.getStateSet();
3971    if (ss && ss->getDataVariance()==osg::Object::STATIC)
3972    {
3973        if (isOperationPermissibleForObject(&node) &&
3974            isOperationPermissibleForObject(ss))
3975        {
3976            pushedStateState = pushStateSet(ss);
3977        }
3978    }
3979
3980    traverse(node);
3981   
3982    if (pushedStateState) popStateSet();
3983}
3984
3985void Optimizer::TextureAtlasVisitor::apply(osg::Geode& geode)
3986{
3987    if (!isOperationPermissibleForObject(&geode)) return;
3988
3989    osg::StateSet* ss = geode.getStateSet();
3990   
3991   
3992    bool pushedGeodeStateState = false;
3993
3994    if (ss && ss->getDataVariance()==osg::Object::STATIC)
3995    {
3996        if (isOperationPermissibleForObject(ss))
3997        {
3998            pushedGeodeStateState = pushStateSet(ss);
3999        }
4000    }
4001    for(unsigned int i=0;i<geode.getNumDrawables();++i)
4002    {
4003
4004        osg::Drawable* drawable = geode.getDrawable(i);
4005        if (drawable)
4006        {
4007            bool pushedDrawableStateState = false;
4008
4009            ss = drawable->getStateSet();
4010            if (ss && ss->getDataVariance()==osg::Object::STATIC)
4011            {
4012                if (isOperationPermissibleForObject(drawable) &&
4013                    isOperationPermissibleForObject(ss))
4014                {
4015                    pushedDrawableStateState = pushStateSet(ss);
4016                }
4017            }
4018           
4019            if (!_statesetStack.empty())
4020            {
4021                for(StateSetStack::iterator ssitr = _statesetStack.begin();
4022                    ssitr != _statesetStack.end();
4023                    ++ssitr)
4024                {
4025                    _statesetMap[*ssitr].insert(drawable);
4026                }
4027            }
4028
4029            if (pushedDrawableStateState) popStateSet();
4030        }
4031       
4032    }
4033   
4034    if (pushedGeodeStateState) popStateSet();
4035}
4036
4037void Optimizer::TextureAtlasVisitor::optimize()
4038{
4039    _builder.reset();
4040   
4041    if (_textures.size()<2)
4042    {
4043        // nothing to optimize
4044        return;
4045    }
4046
4047    Textures texturesThatRepeat;
4048    Textures texturesThatRepeatAndAreOutOfRange;
4049
4050    StateSetMap::iterator sitr;
4051    for(sitr = _statesetMap.begin();
4052        sitr != _statesetMap.end();
4053        ++sitr)
4054    {
4055        osg::StateSet* stateset = sitr->first;
4056        Drawables& drawables = sitr->second;
4057
4058        osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
4059        for(unsigned int unit=0; unit<tal.size(); ++unit)
4060        {
4061            osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
4062            if (texture)
4063            {
4064                bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4065                                texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4066
4067                bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4068                                texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4069                               
4070                if (s_repeat || t_repeat)
4071                {
4072                    texturesThatRepeat.insert(texture);
4073               
4074                    bool s_outOfRange = false;
4075                    bool t_outOfRange = false;
4076 
4077                    float s_min = -0.001;
4078                    float s_max = 1.001;
4079
4080                    float t_min = -0.001;
4081                    float t_max = 1.001;
4082                   
4083                    for(Drawables::iterator ditr = drawables.begin();
4084                        ditr != drawables.end();
4085                        ++ditr)
4086                    {
4087                        osg::Geometry* geom = (*ditr)->asGeometry();
4088                        osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4089                        if (texcoords && !texcoords->empty())
4090                        {
4091                            for(osg::Vec2Array::iterator titr = texcoords->begin();
4092                                titr != texcoords->end() /*&& !s_outOfRange && !t_outOfRange*/;
4093                                ++titr)
4094                            {
4095                                osg::Vec2 tc = *titr;
4096                                if (tc[0]<s_min) { s_min = tc[0]; s_outOfRange = true; }
4097                                if (tc[0]>s_max) { s_max = tc[0]; s_outOfRange = true; }
4098
4099                                if (tc[1]<t_min) { t_min = tc[1]; t_outOfRange = true; }
4100                                if (tc[1]>t_max) { t_max = tc[1]; t_outOfRange = true; }
4101                            }
4102                        }
4103                        else
4104                        {
4105                            // if no texcoords then texgen must be being used, therefore must assume that texture is truely repeating
4106                            s_outOfRange = true;
4107                            t_outOfRange = true;
4108                        }                       
4109                    }
4110
4111                    if (s_outOfRange || t_outOfRange)
4112                    {                   
4113                        texturesThatRepeatAndAreOutOfRange.insert(texture);
4114                    }
4115
4116                }
4117            }
4118        }
4119    }
4120
4121    // now change any texture that repeat but all texcoords to them
4122    // are in 0 to 1 range than converting the to CLAMP mode, to allow them
4123    // to be used in an atlas.
4124    Textures::iterator titr;
4125    for(titr = texturesThatRepeat.begin();
4126        titr != texturesThatRepeat.end();
4127        ++titr)
4128    {
4129        osg::Texture2D* texture = *titr;
4130        if (texturesThatRepeatAndAreOutOfRange.count(texture)==0)
4131        {
4132            // safe to convert into CLAMP wrap mode.
4133            OSG_NOTIFY(osg::INFO)<<"Changing wrap mode to CLAMP"<<std::endl;
4134            texture->setWrap(osg::Texture2D::WRAP_S, osg::Texture::CLAMP);
4135            texture->setWrap(osg::Texture2D::WRAP_T, osg::Texture::CLAMP);
4136        }
4137    }
4138
4139    // add the textures as sources for the TextureAtlasBuilder
4140    for(titr = _textures.begin();
4141        titr != _textures.end();
4142        ++titr)
4143    {
4144        osg::Texture2D* texture = *titr;
4145
4146        bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4147                        texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4148
4149        bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4150                        texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4151
4152        if (!s_repeat && !t_repeat)
4153        {
4154            _builder.addSource(*titr);
4155        }
4156    }
4157   
4158    // build the atlas'
4159    _builder.buildAtlas();
4160
4161
4162    typedef std::set<osg::StateSet*> StateSetSet;
4163    typedef std::map<osg::Drawable*, StateSetSet> DrawableStateSetMap;
4164    DrawableStateSetMap dssm;
4165    for(sitr = _statesetMap.begin();
4166        sitr != _statesetMap.end();
4167        ++sitr)
4168    {
4169        Drawables& drawables = sitr->second;
4170        for(Drawables::iterator ditr = drawables.begin();
4171            ditr != drawables.end();
4172            ++ditr)
4173        {
4174            dssm[(*ditr)->asGeometry()].insert(sitr->first);
4175        }
4176    }
4177   
4178    Drawables drawablesThatHaveMultipleTexturesOnOneUnit;
4179    for(DrawableStateSetMap::iterator ditr = dssm.begin();
4180        ditr != dssm.end();
4181        ++ditr)
4182    {
4183        osg::Drawable* drawable = ditr->first;
4184        StateSetSet& ssm = ditr->second;
4185        if (ssm.size()>1)
4186        {
4187            typedef std::map<unsigned int, Textures> UnitTextureMap;
4188            UnitTextureMap unitTextureMap;
4189            for(StateSetSet::iterator ssm_itr = ssm.begin();
4190                ssm_itr != ssm.end();
4191                ++ssm_itr)
4192            {
4193                osg::StateSet* ss = *ssm_itr;
4194                unsigned int numTextureUnits = ss->getTextureAttributeList().size();
4195                for(unsigned int unit=0; unit<numTextureUnits; ++unit)
4196                {
4197                    osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(ss->getTextureAttribute(unit, osg::StateAttribute::TEXTURE));
4198                    if (texture) unitTextureMap[unit].insert(texture);
4199                }
4200            }
4201            bool drawablesHasMultiTextureOnOneUnit = false;
4202            for(UnitTextureMap::iterator utm_itr = unitTextureMap.begin();
4203                utm_itr != unitTextureMap.end() && !drawablesHasMultiTextureOnOneUnit;
4204                ++utm_itr)
4205            {
4206                if (utm_itr->second.size()>1)
4207                {
4208                    drawablesHasMultiTextureOnOneUnit = true;
4209                }
4210            }
4211            if (drawablesHasMultiTextureOnOneUnit)
4212            {
4213                drawablesThatHaveMultipleTexturesOnOneUnit.insert(drawable);
4214            }
4215
4216        }
4217    }
4218       
4219    // remap the textures in the StateSet's
4220    for(sitr = _statesetMap.begin();
4221        sitr != _statesetMap.end();
4222        ++sitr)
4223    {
4224        osg::StateSet* stateset = sitr->first;
4225        osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
4226        for(unsigned int unit=0; unit<tal.size(); ++unit)
4227        {
4228            osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
4229            if (texture)
4230            {
4231                bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4232                                texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4233
4234                bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4235                                texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4236
4237                osg::Texture2D* newTexture = _builder.getTextureAtlas(texture);
4238                if (newTexture && newTexture!=texture)
4239                {
4240                    if (s_repeat || t_repeat)
4241                    {
4242                        OSG_NOTIFY(osg::NOTICE)<<"Warning!!! shouldn't get here"<<std::endl;
4243                    }
4244
4245                    stateset->setTextureAttribute(unit, newTexture);
4246                   
4247                    Drawables& drawables = sitr->second;
4248                   
4249                    osg::Matrix matrix = _builder.getTextureMatrix(texture);
4250                   
4251                    // first check to see if all drawables are ok for applying texturematrix to.
4252                    bool canTexMatBeFlattenedToAllDrawables = true;
4253                    for(Drawables::iterator ditr = drawables.begin();
4254                        ditr != drawables.end() && canTexMatBeFlattenedToAllDrawables;
4255                        ++ditr)
4256                    {
4257                        osg::Geometry* geom = (*ditr)->asGeometry();
4258                        osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4259
4260                        if (!texcoords)
4261                        {
4262                            canTexMatBeFlattenedToAllDrawables = false;
4263                        }
4264                       
4265                        if (drawablesThatHaveMultipleTexturesOnOneUnit.count(*ditr)!=0)
4266                        {
4267                            canTexMatBeFlattenedToAllDrawables = false;
4268                        }
4269                    }
4270
4271                    if (canTexMatBeFlattenedToAllDrawables)
4272                    {
4273                        // OSG_NOTIFY(osg::NOTICE)<<"All drawables can be flattened "<<drawables.size()<<std::endl;
4274                        for(Drawables::iterator ditr = drawables.begin();
4275                            ditr != drawables.end();
4276                            ++ditr)
4277                        {
4278                            osg::Geometry* geom = (*ditr)->asGeometry();
4279                            osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4280                            if (texcoords)
4281                            {
4282                                for(osg::Vec2Array::iterator titr = texcoords->begin();
4283                                    titr != texcoords->end();
4284                                    ++titr)
4285                                {
4286                                    osg::Vec2 tc = *titr;
4287                                    (*titr).set(tc[0]*matrix(0,0) + tc[1]*matrix(1,0) + matrix(3,0),
4288                                              tc[0]*matrix(0,1) + tc[1]*matrix(1,1) + matrix(3,1));
4289                                }
4290                            }
4291                            else
4292                            {
4293                                OSG_NOTIFY(osg::NOTICE)<<"Error, Optimizer::TextureAtlasVisitor::optimize() shouldn't ever get here..."<<std::endl;
4294                            }                       
4295                        }
4296                    }
4297                    else
4298                    {
4299                        // OSG_NOTIFY(osg::NOTICE)<<"Applying TexMat "<<drawables.size()<<std::endl;
4300                        stateset->setTextureAttribute(unit, new osg::TexMat(matrix));
4301                    }
4302                }
4303            }
4304        }
4305
4306    }
4307}
4308
4309
4310
4311
4312////////////////////////////////////////////////////////////////////////////
4313// StaticObjectDectionVisitor
4314////////////////////////////////////////////////////////////////////////////
4315
4316void Optimizer::StaticObjectDetectionVisitor::apply(osg::Node& node)
4317{
4318    if (node.getStateSet()) applyStateSet(*node.getStateSet());
4319
4320    traverse(node);
4321}
4322
4323void Optimizer::StaticObjectDetectionVisitor::apply(osg::Geode& geode)
4324{
4325    if (geode.getStateSet()) applyStateSet(*geode.getStateSet());
4326
4327    for(unsigned int i=0; i<geode.getNumDrawables(); ++i)
4328    {
4329        applyDrawable(*geode.getDrawable(i));
4330    }
4331}
4332
4333void Optimizer::StaticObjectDetectionVisitor::applyStateSet(osg::StateSet& stateset)
4334{
4335    stateset.computeDataVariance();
4336}
4337
4338
4339void Optimizer::StaticObjectDetectionVisitor::applyDrawable(osg::Drawable& drawable)
4340{   
4341   
4342    if (drawable.getStateSet()) applyStateSet(*drawable.getStateSet());
4343   
4344    drawable.computeDataVariance();
4345}
4346
4347
4348
4349////////////////////////////////////////////////////////////////////////////
4350// FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor
4351////////////////////////////////////////////////////////////////////////////
4352
4353void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::reset()
4354{
4355    _matrixStack.clear();
4356}
4357
4358void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Group& group)
4359{
4360    // only continue if there is a parent
4361    const unsigned int nodepathsize = _nodePath.size();
4362    if(!_matrixStack.empty() && group.getNumParents() > 1 && nodepathsize > 1)
4363    {
4364        // copy this Group
4365        osg::ref_ptr<osg::Object> new_obj = group.clone(osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4366        osg::Group* new_group = dynamic_cast<osg::Group*>(new_obj.get());
4367
4368        // New Group should only be added to parent through which this Group
4369        // was traversed, not to all parents of this Group.
4370        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4371        if(parent_group)
4372        {
4373            parent_group->replaceChild(&group, new_group);
4374            // traverse the new Group
4375            traverse(*(new_group));
4376        }
4377        else
4378        {
4379            OSG_NOTIFY(osg::NOTICE) << "No parent for this Group" << std::endl;
4380        }
4381    }
4382    else
4383    {
4384        // traverse original node
4385        traverse(group);
4386    }
4387}
4388
4389
4390void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Transform& transform)
4391{
4392    bool pushed = false;
4393
4394    // only continue if there is a parent and this is a STATIC transform
4395    const unsigned int nodepathsize = _nodePath.size();
4396    if(transform.getDataVariance() == osg::Object::STATIC && nodepathsize > 1)
4397    {
4398        osg::Matrix matrix;
4399        if(!_matrixStack.empty())
4400            matrix = _matrixStack.back();
4401        transform.computeLocalToWorldMatrix(matrix, this);
4402        _matrixStack.push_back(matrix);
4403        pushed = true;
4404   
4405        // convert this Transform to a Group
4406        osg::ref_ptr<osg::Group> group = new osg::Group(dynamic_cast<osg::Group&>(transform),
4407            osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4408
4409        // New Group should only be added to parent through which this Transform
4410        // was traversed, not to all parents of this Transform.
4411        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4412        if(parent_group)
4413        {
4414            parent_group->replaceChild(&transform, group.get());
4415            // traverse the new Group
4416            traverse(*(group.get()));
4417        }
4418        else
4419        {
4420            OSG_NOTIFY(osg::NOTICE) << "No parent for this Group" << std::endl;
4421        }
4422    }
4423    else
4424    {
4425        // traverse original node
4426        traverse(transform);
4427    }
4428
4429    // pop matrix off of stack
4430    if(pushed)
4431        _matrixStack.pop_back();
4432}
4433
4434
4435void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::LOD& lod)
4436{
4437    const unsigned int nodepathsize = _nodePath.size();
4438    if(!_matrixStack.empty() && lod.getNumParents() > 1 && nodepathsize > 1)
4439    {
4440        osg::ref_ptr<osg::LOD> new_lod = new osg::LOD(lod,
4441            osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4442
4443        // New LOD should only be added to parent through which this LOD
4444        // was traversed, not to all parents of this LOD.
4445        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4446        if(parent_group)
4447        {
4448            parent_group->replaceChild(&lod, new_lod.get());
4449
4450            // move center point
4451            if(!_matrixStack.empty())
4452                new_lod->setCenter(new_lod->getCenter() * _matrixStack.back());
4453
4454            // traverse the new Group
4455            traverse(*(new_lod.get()));
4456        }
4457        else
4458            OSG_NOTIFY(osg::NOTICE) << "No parent for this LOD" << std::endl;
4459    }
4460    else
4461    {
4462        // move center point
4463        if(!_matrixStack.empty())
4464            lod.setCenter(lod.getCenter() * _matrixStack.back());
4465
4466        traverse(lod);
4467    }
4468}
4469
4470
4471void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Geode& geode)
4472{
4473    if(!_matrixStack.empty())
4474    {
4475        // If there is only one parent, just transform all vertices and normals
4476        if(geode.getNumParents() == 1)
4477        {
4478            transformGeode(geode);
4479        }   
4480        else
4481        {
4482            // Else make a copy and then transform
4483            const unsigned int nodepathsize = _nodePath.size();
4484            if(nodepathsize > 1)
4485            {
4486                // convert this Transform to a Group
4487                osg::ref_ptr<osg::Geode> new_geode = new osg::Geode(geode,
4488                    osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4489
4490                // New Group should only be added to parent through which this Transform
4491                // was traversed, not to all parents of this Transform.
4492                osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4493                if(parent_group)
4494                    parent_group->replaceChild(&geode, new_geode.get());
4495                else
4496                    OSG_NOTIFY(osg::NOTICE) << "No parent for this Geode" << std::endl;
4497
4498                transformGeode(*(new_geode.get()));
4499            }
4500        }
4501    }
4502}
4503
4504
4505void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Billboard& billboard)
4506{
4507    if(!_matrixStack.empty())
4508    {
4509        // If there is only one parent, just transform this Billboard
4510        if(billboard.getNumParents() == 1)
4511        {
4512            transformBillboard(billboard);
4513        }
4514        else
4515        {
4516            // Else make a copy and then transform
4517            const unsigned int nodepathsize = _nodePath.size();
4518            if(nodepathsize > 1)
4519            {
4520                // convert this Transform to a Group
4521                osg::ref_ptr<osg::Billboard> new_billboard = new osg::Billboard(billboard,
4522                    osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4523
4524                // New Billboard should only be added to parent through which this Billboard
4525                // was traversed, not to all parents of this Billboard.
4526                osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4527                if(parent_group)
4528                    parent_group->replaceChild(&billboard, new_billboard.get());
4529                else
4530                    OSG_NOTIFY(osg::NOTICE) << "No parent for this Billboard" << std::endl;
4531
4532                transformBillboard(*(new_billboard.get()));
4533            }
4534        }
4535    }
4536}
4537
4538
4539void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformGeode(osg::Geode& geode)
4540{
4541    for(unsigned int i=0; i<geode.getNumDrawables(); i++)
4542    {
4543        transformDrawable(*geode.getDrawable(i));
4544    }
4545
4546    geode.dirtyBound();
4547}
4548
4549
4550void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformDrawable(osg::Drawable& drawable)
4551{
4552    osg::Geometry* geometry = drawable.asGeometry();
4553    if(geometry)
4554    {
4555        // transform all geometry
4556        osg::Vec3Array* verts = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray());
4557        if(verts)
4558        {
4559            for(unsigned int j=0; j<verts->size(); j++)
4560            {
4561                (*verts)[j] = (*verts)[j] * _matrixStack.back();
4562            }
4563        }
4564        else
4565        {
4566            osg::Vec4Array* verts = dynamic_cast<osg::Vec4Array*>(geometry->getVertexArray());
4567            if(verts)
4568            {
4569                for(unsigned int j=0; j<verts->size(); j++)
4570                {
4571                    (*verts)[j] = _matrixStack.back() * (*verts)[j];
4572                }
4573            }
4574        }
4575        osg::Vec3Array* normals = dynamic_cast<osg::Vec3Array*>(geometry->getNormalArray());
4576        if(normals)
4577        {
4578            for(unsigned int j=0; j<normals->size(); j++)
4579                (*normals)[j] = osg::Matrix::transform3x3((*normals)[j], _matrixStack.back());
4580        }
4581
4582        geometry->dirtyBound();
4583        geometry->dirtyDisplayList();
4584    }
4585}
4586
4587
4588void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformBillboard(osg::Billboard& billboard)
4589{
4590    osg::Vec3 axis = osg::Matrix::transform3x3(billboard.getAxis(), _matrixStack.back());
4591    axis.normalize();
4592    billboard.setAxis(axis);
4593
4594    osg::Vec3 normal = osg::Matrix::transform3x3(billboard.getNormal(), _matrixStack.back());
4595    normal.normalize();
4596    billboard.setNormal(normal);
4597
4598    for(unsigned int i=0; i<billboard.getNumDrawables(); i++)
4599    {
4600        osg::Vec3 originalBillboardPosition = billboard.getPosition(i);
4601        billboard.setPosition(i, originalBillboardPosition * _matrixStack.back());
4602
4603        osg::Matrix matrixForDrawable = _matrixStack.back();
4604        matrixForDrawable.preMult(osg::Matrix::translate(originalBillboardPosition));
4605        matrixForDrawable.postMult(osg::Matrix::translate(-billboard.getPosition(i)));
4606
4607        _matrixStack.push_back(matrixForDrawable);
4608        transformDrawable(*billboard.getDrawable(i));
4609        _matrixStack.pop_back();
4610    }
4611
4612    billboard.dirtyBound();
4613}
4614
4615
Note: See TracBrowser for help on using the browser.