This is a tough question. There are many strategies possible to remove overlapping, all with their pros and cons. You could simply remove all overlapping spheres in a second pass and be happy with that. You could add some another spheres and repeat. You could try random positions for a new sphere until it does not overlap with any existing ones. You could move overlapping spheres away from each other and repeat until all spheres found a unique place, and so on... Brute force methods may be simple to implement but rather soon impractical, entering the realm of performance optimizations (for example space partitioning like Octrees).
I suggest you are looking for a non necessarily perfect method which is good enough to continue to work with. A very short way to achieve that is to give every sphere a rigid body and let the built-in physics engine do the collision resolving work for you. Try this script as a starter:
import bpy
from random import randint
numX = 4
numY = 4
numZ = 4
bpy.ops.object.select_all(action='SELECT')
bpy.ops.object.delete(use_global=False, confirm=False)
bpy.context.scene.frame_set(1) # reset frame
for x in range (0,numX):
posX = randint(-25, 25)
for y in range (0,numY):
posY = randint(-25, 25)
for z in range (0,numZ):
posZ = randint(-25, 25)
bpy.ops.mesh.primitive_uv_sphere_add(radius=randint(1,2), location=(posX,posY,posZ))
bpy.ops.rigidbody.object_add() # connect to the physics api
bpy.context.object.rigid_body.collision_shape = 'SPHERE' # edit: faster than convex hull
bpy.ops.object.shade_smooth()
bpy.context.scene.frame_set(2) # run the physics api for one frame to resolve overlapping
The big advantage is that you dont need to think about implementing your own collision detection and resolving algorithm (which is -as i hope made clear- pretty hard done well) and can utilize what others have already done better.
Keep in mind that you may have to tweak the simulation step and clean up the results appropiate to your problem, that may include
- dont use gravity
- throw away the rigid bodies
- check spheres against the cube hull
- ...
but the overlappings should be resolved.
Edit: I did some quick tests with 1000 spheres (numX/Y/Z = 10). Adding the spheres to the scene (no matter if with rigid body or not) is by far slower than the physics simulation step. Thus the simulation step is not the bottleneck here, but a more efficient way to add a lot of objects should be found.
Edit2: Investigated further the bottleneck. It turns out that bpy.ops calls (especially in loops) are slow as they trigger UI updates. Bypassing these calls ramps up the performance. For anyone who is interested i have assembled a script which creates 1000 non overlapping spheres in under a second (10000 spheres are close to 10 seconds) on my machine, whereas the original script takes around 2 minutes.
import bpy
import time
import random
NUMSPHERES = 1000
bpy.ops.object.select_all(action='DESELECT')
# geometry resolution and real duplicates affect performance of setup step
bpy.ops.mesh.primitive_uv_sphere_add(segments=8, ring_count=4)
sphere = bpy.context.object
if bpy.context.scene.rigidbody_world == None:
bpy.ops.rigidbody.world_add()
spheres = []
# create n spheres without ops
t1 = time.time()
for i in range(NUMSPHERES - 1):
obj = sphere.copy()
#obj.data = sphere.data.copy() # activate for real duplicates
spheres.append(obj)
bpy.context.collection.objects.link(obj)
sphere.select_set(True)
# add rigid body for all at once
bpy.ops.rigidbody.objects_add(type='ACTIVE')
# optimize rigid body shape and tweak spheres
for sphere in spheres:
sphere.rigid_body.collision_shape = 'SPHERE'
sphere.location = (random.uniform(-25, 25), random.uniform(-25, 25), random.uniform(-25, 25))
sc = random.uniform(1, 2)
sphere.scale = (sc, sc, sc)
t2 = time.time()
print("setup spheres:", t2 - t1)
# run the physics api to resolve overlapping
t1 = time.time()
bpy.context.scene.frame_set(1)
bpy.context.scene.frame_set(2)
# clean up
bpy.ops.object.visual_transform_apply() # apply simulation result
bpy.ops.rigidbody.objects_remove() # remove rigid body for all at once
bpy.context.scene.frame_set(1) # reset timeline
bpy.ops.object.select_all(action='DESELECT')
t2 = time.time()
print("simulation step:", t2 - t1)
