Separate by vertex count - fast

Question

I make a terrain (ground + vegetation mesh) for an old game engine which needs all the geometry to be separated into chunks consisting of ~ 25k vertices max.

So far I use my "separate by radius" script which enters Edit mode, select faces in a given radius, separate using bpy.ops.mesh.separate(type='SELECTED') and continues until it is separated completely.

This is the original script:

import bpy
import bmesh
import time

class SeparateByRadius(bpy.types.Operator):
    bl_idname = "object.separate_by_radius"
    bl_label = "Separate by Radius"
    bl_options = {'REGISTER', 'UNDO'}

    max_diameter = bpy.props.IntProperty(name="Radius", default=0)

    def execute(self, context):

        if self.max_diameter == 0:
             return {'FINISHED'}

        context = bpy.context
        scene = context.scene

        bpy.ops.object.mode_set(mode="EDIT")

        obj = bpy.context.edit_object
        me = obj.data

        bm = bmesh.from_edit_mesh(me)

        time_start_updating = time.time()

        def separateNextChunk():

            bm.faces.ensure_lookup_table()

            if len(bm.faces) == 0:
                bpy.ops.object.mode_set(mode="OBJECT")
                bpy.ops.object.select_all(action='DESELECT')
                context.active_object.select = True
                bpy.ops.object.delete()
            else:
                active_median = bm.faces[-1].calc_center_median()

                continue_next = False

                for f in bm.faces:
                    f.select = False
                    if (f.calc_center_median()-active_median).length <= self.max_diameter / 2:
                        f.select = True
                        continue_next = True


                bpy.ops.mesh.separate(type='SELECTED')
                # Show the updates in the viewport
                # and recalculate n-gon tessellation.
                bmesh.update_edit_mesh(me, True)

                if continue_next == True:
                    separateNextChunk()

        separateNextChunk()

        print("Separated in " + str(time.time() - time_start_updating))

        return {'FINISHED'}

def register():
    bpy.utils.register_class(SeparateByRadius)


def unregister():
    bpy.utils.unregister_class(SeparateByRadius)

if __name__ == "__main__":
    register()

While it does the job, it is EXTREMELY slow - the splitting often results into ~2000 objects and this take hours to separate using this method. I suspect the reason is that we are doing modifications of the original (large) mesh by the each single separation.

I have tried to find some alternative methods that would generate the chunks without modifying the original mesh, but as I am not a Python programmer, it started to be too complex for me.

I would appreciate so much if anyone can share some specific ideas how to enhance the script to get it work noticeably faster with the same output, the requirements are:

• separating into chunks of a given max vertex count or given area
• splitting must use the existing mesh (no cutting)
• UVs, materials and vertex colors must be preserved perfectly

A .blend with the resulted mesh, just Join all the pieces to single mesh for the purpose of a script testing.

Answer 1

Divide and conquer!

I think the main point for performance is to have smallest objects as soon as possible.

For that, the idea is to use a dichotomy: split the object in half, then each half in half, etc. So cutting an object is faster at each iteration.

The following code is doing it using the bounding box of the object. Boundings are in local coordinates in Blender.

So we get the boundings. Find the spatially largest axis then cut in half on it.

Once vertices are selected, we use 'select linked' to avoid the faces or edges to be cut.

import bpy
import bmesh
import time
from mathutils import Vector


def cut_object( obj ):
    #Gets the bounds
    bounds = [b[:] for b in obj.bound_box]
    #0 is the min
    min_bounds = Vector( bounds[0] )
    #6 is opposite corner to 0
    max_bounds = Vector( bounds[6] )
    delta_bounds = max_bounds - min_bounds

    #Get the axis which corresponds to the largest area
    axis = 0
    if ( delta_bounds.x < delta_bounds.y ): axis = 1
    #Commented below as using Z axis has unwanted effects in your situation
    #if ( delta_bounds.y < delta_bounds.z ): axis = 2

    #The center is the limit    
    limit = min_bounds[axis] + 0.5 * delta_bounds[axis]

    #Set the object active
    bpy.ops.object.mode_set(mode = 'OBJECT')
    bpy.context.scene.objects.active = obj
    #Set selection mode
    bpy.ops.object.mode_set(mode="EDIT")
    bpy.ops.mesh.select_mode(type="VERT")

    #Select the wanted vertices
    bpy.ops.object.mode_set(mode = 'OBJECT')

    for v in obj.data.vertices:
        v.select = v.co[axis] < limit

    #Extend to linked parts (so wont cut the faces or edges)    
    bpy.ops.object.mode_set(mode="EDIT")
    bpy.ops.mesh.select_linked()

    #Get the selected vertex count
    selected_count = sum( 1 for v in obj.data.vertices if v.select )

    print( "Axis: " + str( axis ) )
    print( "Selected: " + str( selected_count ) + "/" + str( len( obj.data.vertices ) ) )

    result = True
    #Check that will separate something
    if selected_count == 0 or selected_count == len( obj.data.vertices ):
        result = False
    else:
        bpy.ops.mesh.separate(type='SELECTED')

    bpy.ops.object.mode_set(mode="OBJECT")

    return result

print( '-----------------' )

max_vertices = 10000
max_iterations = 20
iteration = 0

found = True

start_time = time.time()

discarded_objects = {}

while found and iteration < max_iterations:

    found = False

    #Get all objects that have more than the wanted vertex amount
    for obj in [x for x in bpy.context.scene.objects if len(x.data.vertices) > max_vertices and discarded_objects.get( x ) != True]:
        if cut_object( obj ):
            found = True
        else:
            #We can not cut it, so discard it
            discarded_objects[obj] = True

    iteration += 1            
    print( "Iteration: " + str( iteration ) + "   Objects: " + str( len( bpy.context.scene.objects ) ) )

end_time = time.time()

print( "Elapse: " + str( end_time - start_time ) )

The code is commented. So I think all is said about that.

Results

For a limit of 25k per chunk that gives 33s here.

For 10k, this is 50s.

Comments

You may prefer cutting differently. For instance defining a virtual cube surrounding the object, then cut it in half and use its part to cut the mesh.

The given code version does not included cutting along Z. It works, but is far longer when the wanted amount of vertices is low (10k for instance). The reason is we can only separate few faces at each iteration.

I'm also wondering why you need to start with such large mesh? Why the process does not allow to start from small parts instead this big one?

Here is the blend file with the script included:

Edit

Here is a version with no iteration limit and including the cut along Z.

But, practically cutting along Z won't work for small chunks (tested on 10k).

The reason is several parts of the mesh are tall and close to each other. So they can't be separated the way the algorithm works because select linked will nearly select them all and only few very small parts will be separated.