Changeset 545

Timestamp:

03/12/08 19:40:44 (10 months ago)

Author:

phill

Message:

o So much to batch, so little time...

Files:

• branches/morph-targets/libx42make/include/x42make-modelbuilder.h (modified) (7 diffs)
• branches/morph-targets/libx42make/modelbuilder-batch.cpp (modified) (18 diffs)
• branches/morph-targets/libx42make/modelbuilder-geometry.cpp (modified) (6 diffs)
• branches/morph-targets/libx42make/modelbuilder.cpp (modified) (1 diff)

branches/morph-targets/libx42make/include/x42make-modelbuilder.h

@@ -119 +119 @@
-        class group_split_target;
-        class group_split_context;
+        class topological_group_split_context;
-
-        class model_data_builder;
@@ -378 +379 @@
-        vertex_weight& operator[] ( size_t index ) { if( index >= max_weights ) throw error(); return _weights[index]; }
-        const vertex_weight& operator[] ( size_t index ) const { if( index >= max_weights ) throw error(); return _weights[index]; }
+
+        float find_weight( const influence_ptr &influence ) const;
-
-        bool operator == ( const vertex_weights &other ) const;
@@ -470 +473 @@
-        std::vector< index > get_list_indices() const;
-
+        std::vector< index > get_point_reps( float pos_tol = 1e-5F, float wt_tol = 1e-5F ) const;
+
-        X42_DECLARE_ENUM( optimize_type )
-                match_current,
@@ -510 +515 @@
-
-private:
-
+
+
+
+
+
+
-
-        friend class lod;
@@ -516 +526 @@
-        friend class _impl::group_split_target;
-        friend class _impl::group_split_context;
+        friend class _impl::topological_group_split_context;
-        friend group_ptr _impl::merge_groups( group_ptr a, group_ptr b );
-};
-
-class group_enumerator;
+
+X42_DECLARE_ENUM( group_split_type )
+        greedy,
+        topological,
+X42_END_ENUM( group_split_type );
+
+struct group_split_limits
+{
+        static const size_t default_max_verts = 10000;
+        static const size_t default_max_prims = 10000;
+        static const size_t default_max_influences = 30;
+
+        size_t max_verts;
+        size_t max_prims;
+        size_t max_influences;
+
+        group_split_limits()
+                : max_verts( default_max_verts ),
+                max_prims( default_max_prims ),
+                max_influences( default_max_influences )
+        {
+        }
+};
-
-class lod : public ref_obj
@@ -530 +564 @@
-        group_ptr create_group( const std::string &surface_name = std::string(),
-                const std::string &material_name = std::string() );
+
+        void split_large_groups(
+                const group_split_limits &limits = group_split_limits(),
+                group_split_type preferred_split_type = group_split_type::topological ); 
+        void split_by_weight_count(
+                float up_merge_limit_factor = 0.5F,
+                const group_split_limits &limits = group_split_limits() );
+        void merge_small_groups(
+                float merge_limit_factor = 0.5F,
+                const group_split_limits &limits = group_split_limits() );
-
-private:
@@ -630 +674 @@
-        void compute_culling_info( uint frame_sample_stride = 1 );
-
+        void split_large_groups(
+                const group_split_limits &limits = group_split_limits(),
+                group_split_type preferred_split_type = group_split_type::topological ); 
+        void split_groups_by_weight_count(
+                float up_merge_limit_factor = 0.5F,
+                const group_split_limits &limits = group_split_limits() );
+        void merge_small_groups(
+                float merge_limit_factor = 0.5F,
+                const group_split_limits &limits = group_split_limits() );
+
-        model to_model( void ) const;
-

branches/morph-targets/libx42make/modelbuilder-batch.cpp

@@ -85 +85 @@
-        std::vector< group_split_target_ptr > target_groups;
-
-_group_ptr 
+ const_group_ptr &
-        group_split_target_ptr create_target();
-
@@ -94 +94 @@
-
-        void split_by_weight_count();
-
-
-
-
-
-
-
+
+
+
+
+
-        group_split_target_ptr internal_merge_groups( group_split_target_ptr a, group_split_target_ptr b );
-};
@@ -125 +123 @@
-        std::vector< adj_entry > entries;
-        std::vector< size_t > values;
+};
+
+class bone_topology
+{
+public:
+        struct entry
+        {
+                const_bone_ptr                                  bone;
+
+                const_bone_ptr                                  parent;
+                std::vector< const_bone_ptr >   children;
+
+                const_bone_ptr                                  local_root;
+                size_t                                                  distance_to_local_root;
+
+                const_bone_ptr                                  nearest_leaf;
+                const_bone_ptr                                  path_to_nearest_leaf;
+                size_t                                                  distance_to_nearest_leaf;
+
+                bool is_root() const { return !parent; }
+                bool is_leaf() const { return !children.size(); }
+                size_t neighbor_count() const
+                {
+                        return (is_root() ? 0 : 1) + children.size();
+                }
+        };
+
+        std::vector< entry >                    entries;
+        std::vector< const_bone_ptr >   roots;
+        std::vector< const_bone_ptr >   leaves;
+
+        bone_topology()
+        {
+        }
+
+        void initialize( const std::vector< bone_ptr > &bones );
+        void initialize( const std::vector< const_bone_ptr > &bones );
+
+        size_t size() const { return entries.size(); }
+        const entry& operator [] ( size_t index ) const { return entries[index]; }
+        const entry& operator [] ( const const_bone_ptr &bone ) const { return entries[bone->index()]; }
+
+private:
+        void process_bone( const const_bone_ptr &bone );
+        void process_entries();
+};
+
+class topological_group_split_context : public group_split_context
+{
+public:
+        topological_group_split_context( const const_group_ptr &source );
+
+        group_split_target_ptr target_group() const { return target_groups[0]; }
+        group_split_target_ptr spillover_group() const { return target_groups[1]; }
+
+        void set_split_limits( size_t max_verts, size_t max_prims,
+                size_t max_influences );
+
+        void split_from_root( const group_split_limits &limits );
+        void split_from_leaves( const group_split_limits &limits );
+
+protected:
+        struct triangle
+        {
+                size_t  index;
+                size_t  inf_cost;
+                size_t  vert_cost;
+                bool    visited;
+
+                triangle()
+                        : visited( false )
+                {
+                }
+        };
+
+        adjacency adjacency;
+        bone_topology topology;
+        std::vector< triangle > triangles;
+
+        void internal_add_sets( std::vector< const_bone_ptr > &to_visit,
+                bool favor_root, const group_split_limits &limits );
+        void add_adjacency_set( size_t start_tri, const group_split_limits &limits );
+        void add_triangle( triangle &tri, const group_split_limits &limits );
+        void update_tri_list();
+
+private:
+        void initialize_for_split();
+        void resolve_point_reps( std::vector< index > &indices );
-};
-
@@ -214 +300 @@
-group_ptr merge_groups( group_ptr a, group_ptr b )
-{
-
+ a->owner 
-
-        if( a == b )
@@ -328 +414 @@
-
-/*
+        class bone_topology
+*/
+
+void bone_topology::initialize( const std::vector< bone_ptr > &bones )
+{
+        entries.clear();
+        entries.resize( bones.size() );
+
+        roots.clear();
+        leaves.clear();
+
+        for( size_t i = 0; i < bones.size(); i++ )
+                process_bone( bones[i] );
+        
+        process_entries();
+}
+
+void bone_topology::initialize( const std::vector< const_bone_ptr > &bones )
+{
+        entries.clear();
+        entries.resize( bones.size() );
+
+        roots.clear();
+        leaves.clear();
+
+        for( size_t i = 0; i < bones.size(); i++ )
+                process_bone( bones[i] );
+        
+        process_entries();
+}
+
+void bone_topology::process_bone( const const_bone_ptr &bone )
+{
+        entry &ent = entries[bone->index()];
+
+        ent.bone = bone;
+        ent.parent = bone->parent();
+
+        if( ent.parent )
+        {
+                entry &parent_ent = entries[ent.parent->index()];
+
+                parent_ent.children.push_back( bone );
+
+                ent.local_root = parent_ent.local_root;
+                ent.distance_to_local_root = parent_ent.distance_to_local_root + 1;
+        }
+        else
+        {
+                ent.local_root = bone;
+                ent.distance_to_local_root = 0;
+        }
+}
+
+void bone_topology::process_entries()
+{
+        for( size_t i = 0; i < entries.size(); i++ )
+        {
+                if( entries[i].is_root() )
+                        roots.push_back( entries[i].bone );
+        }
+
+        for( size_t i = 0; i < entries.size(); i++ )
+        {
+                if( entries[i].is_leaf() )
+                        leaves.push_back( entries[i].bone );
+        }
+
+        for( size_t i = 0; i < entries.size(); i++ )
+        {
+                entry &ent = entries[i];
+
+                if( ent.is_leaf() )
+                {
+                        ent.nearest_leaf = ent.bone;
+                        ent.distance_to_nearest_leaf = 0;
+                        continue;
+                }
+
+                ent.distance_to_nearest_leaf = size_t_traits::max_val;
+
+                for( size_t j = 0; j < ent.children.size(); j++ )
+                {
+                        entry &child = entries[ent.children[i]->index()];
+
+                        if( child.distance_to_nearest_leaf + 1 < ent.distance_to_nearest_leaf )
+                        {
+                                ent.distance_to_nearest_leaf = child.distance_to_nearest_leaf + 1;
+                                ent.nearest_leaf = child.nearest_leaf;
+                                ent.path_to_nearest_leaf = child.bone;
+                        }
+                }
+        }
+}
+
+/*
-        class group_split_target
-*/
@@ -333 +515 @@
-group_split_target::group_split_target( group_split_context *owner )
-        : owner( owner ),
-
+ owner->source->owner 
-        src_to_dst_vert_map( owner->source->geometry.vertex_count(), invalid_index ),
-        prim_count( 0 ), max_infs_per_vert( 0 )
@@ -342 +524 @@
-group_split_target::group_split_target( const group_split_target &src )
-        : owner( src.owner ),
-
+ src.source_group->owner 
-        src_to_dst_vert_map( src.src_to_dst_vert_map ), dst_to_src_vert_map( src.dst_to_src_vert_map ),\
-        influences( src.influences ), prim_count( src.prim_count ),
@@ -451 +633 @@
-        inf_cost = 0;
-
+        std::vector< influence_ptr > temp_infs( influences );
-        for( size_t i = 0; i < owner->elems_per_prim; i++ )
-        {
@@ -461 +644 @@
-                vert_cost++;
-                
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
-        }
-}
@@ -492 +684 @@
-*/
-
-_group_ptr 
+ const_group_ptr &
-        : source( source ), prim_count( source->geometry.primitive_count() ),
-        elems_per_prim( source->geometry.prim_type.elems_per_prim() ),
@@ -537 +729 @@
-}
-
-
-
+
-{
-        target_groups.clear();
@@ -547 +738 @@
-                
-                group_split_target_ptr target;
-, target_inf_cost
+ = 0, target_inf_cost = 0
-
-                for( size_t j = 0; j < target_groups.size(); j++ )
@@ -554 +745 @@
-                        
-                        //see if this candidate even has room for the insert
-
+limits.
-                                continue;
-
@@ -560 +751 @@
-                        candidate->compute_append_prim_cost( i_prim, vert_cost, inf_cost );
-
-
+limits.
-                                continue;
-
+limits.
-                                continue;
-
@@ -582 +773 @@
-}
-
-void group_split_context::topological_split_from_leaves( size_t max_verts,
-        size_t max_prims, size_t max_influences )
-{
-        if( elems_per_prim != 3 )
-                throw error( "Topological split only works on triangles." );
-
-
-}
-
-void group_split_context::topological_split_from_root( size_t max_verts,
-        size_t max_prims, size_t max_influences )
-{
-        if( elems_per_prim != 3 )
-                throw error( "Topological split only works on triangles." );
-
-
-}
-
-group_split_target_ptr group_split_context::internal_merge_groups(
-        group_split_target_ptr a, group_split_target_ptr b )
@@ -615 +788 @@
-}
-
-
+
+
-{
-        std::vector< group_split_target_ptr > src( target_groups );
@@ -640 +814 @@
-                }
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
-                        ag.vertex_count() < (size_t)(bg.vertex_count() * up_merge_limit_factor) )
-                {
@@ -669 +852 @@
-}
-
+/*
+        class topological_group_split_context
+*/
+
+topological_group_split_context::topological_group_split_context( const const_group_ptr &source )
+        : group_split_context( source )
+{
+        if( elems_per_prim != 3 )
+                throw error( "Topological split only works on triangles." );
+
+        std::vector< index > adjacency_indices( list_indices );
+        resolve_point_reps( adjacency_indices );
+        adjacency.initialize( adjacency_indices );
+
+        triangles.resize( prim_count );
+        for( size_t i = 0; i < triangles.size(); i++ )
+                triangles[i].index = i;
+
+        topology.initialize( source->owner->bones );
+}
+
+void topological_group_split_context::initialize_for_split()
+{
+        target_groups.clear();
+        create_target(); //create good target
+        create_target(); //create spillover target
+
+        for( size_t i = 0; i < triangles.size(); i++ )
+        {
+                triangle &tri = triangles[i];
+
+                tri.visited = false;
+        }
+}
+
+void topological_group_split_context::resolve_point_reps( std::vector< index > &indices )
+{
+        std::vector< index > point_reps = source->geometry.get_point_reps();
+        for( size_t i = 0; i < indices.size(); i++ )
+                indices[i] = point_reps[indices[i]];
+}
+
+void topological_group_split_context::split_from_leaves( const group_split_limits &limits )
+{
+        initialize_for_split();
+
+        struct leaf_sort
+        {
+        public:
+                leaf_sort( const bone_topology &topology )
+                        : topology( &topology ) { }
+
+                bool operator () ( const const_bone_ptr &a, const const_bone_ptr &b ) const
+                {
+                        return (*topology)[a].distance_to_local_root <
+                                (*topology)[b].distance_to_local_root;
+                }
+
+        private:
+                const bone_topology *topology;
+        };
+
+        std::vector< const_bone_ptr > to_visit( topology.leaves );
+        std::sort( to_visit.begin(), to_visit.end(), leaf_sort( topology ) );
+
+        internal_add_sets( to_visit, false, limits );
+}
+
+void topological_group_split_context::split_from_root( const group_split_limits &limits )
+{
+        initialize_for_split();
+
+        struct root_sort
+        {
+        public:
+                root_sort( const bone_topology &topology )
+                        : topology( &topology ) { }
+
+                bool operator () ( const const_bone_ptr &a, const const_bone_ptr &b ) const
+                {
+                        return (*topology)[a].distance_to_local_root >
+                                (*topology)[b].distance_to_local_root;
+                }
+
+        private:
+                const bone_topology *topology;
+        };
+
+        std::vector< const_bone_ptr > to_visit( topology.leaves );
+        std::sort( to_visit.begin(), to_visit.end(), root_sort( topology ) );
+
+        internal_add_sets( to_visit, false, limits );
+}
+
+void topological_group_split_context::internal_add_sets( std::vector< const_bone_ptr > &to_visit,
+                bool favor_root, const group_split_limits &limits )
+{
+        std::vector< bool > visited_bones( topology.size(), false );
+
+        while( to_visit.size() )
+        {
+                const_bone_ptr &bone = to_visit.back();
+                to_visit.pop_back();
+
+                if( visited_bones[bone->index()] )
+                        continue;
+                visited_bones[bone->index()] = true;
+
+                const bone_topology::entry &bone_ent = topology[bone];
+
+                if( favor_root )
+                {
+                        to_visit.insert( to_visit.end(), bone_ent.children.begin(), bone_ent.children.end() );
+                        if( !bone_ent.is_root() )
+                                to_visit.push_back( bone_ent.parent );
+                }
+                else
+                {
+                        if( !bone_ent.is_root() )
+                                to_visit.push_back( bone_ent.parent );
+                        to_visit.insert( to_visit.end(), bone_ent.children.begin(), bone_ent.children.end() );
+                }
+
+                for( size_t i = 0; i < influences.size(); i++ )
+                {
+                        const influence_ptr &inf = influences[i];
+
+                        if( inf->bone() != bone )
+                                continue;
+
+                        size_t candidate_tri = size_t_traits::max_val;
+                        for( size_t i = 0; i < list_indices.size(); i++ )
+                        {
+                                index src_idx = list_indices[i];
+                                if( source->geometry.weights[src_idx].find_weight( inf ) > 0 )
+                                {
+                                        candidate_tri = i / 3;
+                                        break;
+                                }
+                        }
+
+                        if( candidate_tri != size_t_traits::max_val )
+                                add_adjacency_set( candidate_tri, limits );
+                }
+        }
+
+        for( size_t i = 0; i < triangles.size(); i++ )
+        {
+                if( !triangles[i].visited )
+                        add_adjacency_set( i, limits );
+        }
+}
+
+void topological_group_split_context::update_tri_list()
+{
+        for( size_t i = 0; i < triangles.size(); i++ )
+        {
+                triangle &tri = triangles[i];
+
+                if( tri.visited )
+                {
+                        //force it to sort to the back
+                        tri.inf_cost = size_t_traits::max_val;
+                        tri.vert_cost = size_t_traits::max_val;
+                        continue;
+                }
+
+                target_group()->compute_append_prim_cost( tri.index,
+                        tri.vert_cost, tri.inf_cost );
+        }
+}
+
+void topological_group_split_context::add_adjacency_set( size_t start_tri,
+        const group_split_limits &limits )
+{
+        struct tri_cmp
+        {
+        public:
+                tri_cmp( topological_group_split_context *owner )
+                        : owner( owner ) { }
+
+                bool operator () ( size_t ia, size_t ib )
+                {
+                        const triangle &a = owner->triangles[ia];
+                        const triangle &b = owner->triangles[ib];
+
+                        if( a.inf_cost > b.inf_cost )
+                                return true;
+                        if( a.inf_cost < b.inf_cost )
+                                return false;
+
+                        return a.vert_cost > b.vert_cost;
+                }
+
+        private:
+                topological_group_split_context *owner;
+        };
+
+        std::vector< size_t > to_visit, next_visit;
+        to_visit.push_back( start_tri );
+
+        size_t prev_prims = target_group()->prim_count + 1;
+        while( to_visit.size() && prev_prims != target_group()->prim_count )
+        {
+                prev_prims = target_group()->prim_count;
+
+                update_tri_list();
+                std::sort( to_visit.begin(), to_visit.end(), tri_cmp( this ) );
+
+                size_t i;
+
+                //add any triangles we can sneak in nearly free
+                for( i = 0; i < to_visit.size(); i++ )
+                {
+                        triangle &tri = triangles[to_visit[i]];
+
+                        if( tri.visited )
+                                continue;
+
+                        if( tri.inf_cost != 0 )
+                                break;
+
+                        tri.visited = true;
+
+                        size_t num_adjacent = adjacency.adj_len( tri.index );
+                        for( size_t j = 0; j < num_adjacent;  j++ )
+                        {
+                                size_t adj = adjacency.adj_idx( tri.index, j );
+                                if( !triangles[adj].visited )
+                                        next_visit.push_back( adj );
+                        }
+
+                        add_triangle( tri, limits );
+                }
+
+                if( i )
+                {
+                        //have added triangles, merge next_visit with to_visit and continue from there
+                        to_visit.assign( next_visit.begin(), next_visit.end() );
+                        std::sort( to_visit.begin(), to_visit.end(), tri_cmp( this ) );
+                        next_visit.clear();
+                }
+
+                for( i = 0; i < to_visit.size(); i++ )
+                {
+                        triangle &tri = triangles[to_visit[i]];
+
+                        if( tri.visited )
+                                continue;
+
+                        tri.visited = true;
+
+                        size_t num_adjacent = adjacency.adj_len( tri.index );
+                        for( size_t j = 0; j < num_adjacent;  j++ )
+                        {
+                                size_t adj = adjacency.adj_idx( tri.index, j );
+                                if( !triangles[adj].visited )
+                                        next_visit.push_back( adj );
+                        }
+
+                        add_triangle( tri, limits );
+                }
+
+                to_visit.clear();
+                std::swap( next_visit, to_visit );
+        }
+}
+
+void topological_group_split_context::add_triangle( triangle &tri,
+        const group_split_limits &limits )
+{
+        group_split_target_ptr good_group = target_group();
+        group_split_target_ptr spill_group = spillover_group();
+
+        group_split_target_ptr target;
+
+        if( good_group->prim_count + 1 <= limits.max_prims &&
+                good_group->vertex_count() + tri.vert_cost <= limits.max_verts &&
+                good_group->influences.size() + tri.inf_cost <= limits.max_influences )
+        {
+                target = good_group;
+        }
+        else
+        {
+                target = spill_group;
+        }
+
+        target->append_prim( tri.index );
+}
+
-};
+
+/*
+        class lod
+*/
+
+void lod::split_large_groups(
+        const group_split_limits &limits,
+        group_split_type preferred_split_type )
+{
+        for( size_t i = 0; i < groups.size(); i++ )
+        {
+                group_ptr g = groups[i];
+
+                if( g->geometry.primitive_count() <= limits.max_prims &&
+                        g->geometry.vertex_count() <= limits.max_verts &&
+                        g->get_influences().size() <= limits.max_influences )
+                        continue;
+
+                if( preferred_split_type == group_split_type::topological &&
+                        g->geometry.prim_type.to_list_type() == primitive_type::triangle_list )
+                {
+                        group_ptr sg;
+                        std::vector< group_ptr > split_from_leaves, split_from_roots;
+
+                        sg = g;
+                        while(
+                                sg->geometry.primitive_count() > limits.max_prims ||
+                                sg->geometry.vertex_count() > limits.max_verts ||
+                                sg->get_influences().size() > limits.max_influences )
+                        {
+                                _impl::topological_group_split_context splitter( sg );
+                                splitter.split_from_leaves( limits );
+
+
+                                split_from_leaves.push_back( splitter.target_group()->target_group );
+                                sg = splitter.spillover_group()->target_group;
+                        }
+
+                        sg = g;
+                        while(
+                                sg->geometry.primitive_count() > limits.max_prims ||
+                                sg->geometry.vertex_count() > limits.max_verts ||
+                                sg->get_influences().size() > limits.max_influences )
+                        {
+                                _impl::topological_group_split_context splitter( sg );
+                                splitter.split_from_root( limits );
+
+
+                                split_from_roots.push_back( splitter.target_group()->target_group );
+                                sg = splitter.spillover_group()->target_group;
+                        }
+
+                        std::vector< group_ptr > *best = 0;
+                        if( split_from_roots.size() < split_from_leaves.size() )
+                                best = &split_from_roots;
+                        else if( split_from_leaves.size() < split_from_roots.size() )
+                                best = &split_from_leaves;
+
+                        if( !best )
+                        {
+                                size_t leaf_uploads = 0;
+                                for( size_t i = 0; i < split_from_leaves.size(); i++ )
+                                {
+                                        leaf_uploads += split_from_leaves[i]->get_influences().size();
+                                }
+
+                                size_t root_uploads = 0;
+                                for( size_t i = 0; i < split_from_roots.size(); i++ )
+                                {
+                                        root_uploads += split_from_roots[i]->get_influences().size();
+                                }
+
+                                if( root_uploads < leaf_uploads )
+                                        best = &split_from_roots;
+                                else if( leaf_uploads < root_uploads )
+                                        best = &split_from_leaves;
+                        }
+
+                        if( !best )
+                                best = &split_from_leaves;
+
+                        if( best->size() == 1 )
+                                //didn't actually split (for whatever reason...should this be an error?)
+                                continue;
+
+                        groups.erase( groups.begin() + i );
+                        groups.insert( groups.begin() + i, best->begin(), best->end() );
+
+                        i += best->size() - 1; //skip over what we just added
+                }
+                else
+                {
+                        _impl::group_split_context splitter( g );
+                        splitter.greedy_split( limits );
+
+                        if( splitter.target_groups.size() == 1 )
+                                //didn't actually split (for whatever reason...should this be an error?)
+                                continue;
+
+                        groups.erase( groups.begin() + i );
+                        for( size_t j = 0; j < splitter.target_groups.size(); j++ )
+                        {
+                                groups.insert( groups.begin() + i + j,
+                                        splitter.target_groups[i]->target_group );
+                        }
+
+                        i += splitter.target_groups.size() - 1; //skip over what we just added
+                }
+        }
+}
+
+void lod::split_by_weight_count(
+        float up_merge_limit_factor,
+        const group_split_limits &limits )
+{
+        for( size_t i = groups.size(); i--; )
+        {
+                _impl::group_split_context splitter( groups[i] );
+
+                splitter.split_by_weight_count();
+                splitter.cost_ordered_merge( limits, up_merge_limit_factor );
+
+                groups.erase( groups.begin() + i );
+                for( size_t j = splitter.target_groups.size(); j--; )
+                {
+                        groups.insert( groups.begin() + i,
+                                splitter.target_groups[j]->target_group );
+                }
+        }
+}
+
+void lod::merge_small_groups(
+        float merge_limit_factor,
+        const group_split_limits &limits )
+{
+        for( size_t ia = 0; ia < groups.size(); ia++ )
+        {
+                group_ptr ga = groups[ia];
+                
+                if( ga->geometry.primitive_count() >= limits.max_prims &&