fastest way to perform proximity check on large set of objects?

i’m writing a script (not for a game) that that checks if an object’s location falls within a certain proximity of any members of another set of objects.

currently i’ve got something where i just iterate through a list of objects, calculate each objects’ distance from the original object using vector math, and then check if that falls below a certain threshold, returning True on the first occurrence.

its not bad, but i am hoping to call this function numerous times on really large sets of objects, so i was just curious if there is anything more efficient already built into blender. every similar discussion i’ve found about this type of problem is usually related to the game engine, but i don’t have a lot of experience there, nor do i know if game engine functions can be used for ‘vanilla’ scripting that isn’t actually for a game scenario?

being that blender does seem to have a fairly fast system for finding nearby objects (consider proportional editing in object mode), i was hoping there was some way to leverage this.

anyone have any thoughts? thanks!

The first thing that came to mind is that you might want to do a bounding box culling as your first step. So take your source object and multiply it’s bounding box by the distance. Then check to see if other bounding boxes fall within the source objects bounding box. This might be quicker than using the square root to calculate distance. Once you have a smaller list of objects that are close to the source then you can run your existing routine for a finer proximity results.

I don’t know if it would be quicker, however, you may have to conduct speed test on various techniques.

Which algorithms and data structures are suitable for this depends on how dynamic your object positions are. For example if you have just 1 moving object and the rest are static then you can use some techniques and if all of them are moving then you have to do something else.

So what are the properties of your objects?

  • How many are moving
  • Do they all interact?

you can use the squared lengths, avoiding a square root operation on length calculation

hey guys!

thanks very much for the replies!

what i actually ended up doing was, i think, something similar to what Atom was suggesting. since this was a proximity test and didn’t need to be super precise, i basically used a box-proximity test where i checked distance on each axis individually, avoiding any heavy math. with this route, if their x distance was outside the proximity value, i could immediately return false without even bothering to check y or z.

i also was able to optimize further upstream in the code, reducing the number of times the check even had to be performed. which is a good thing, because i’m using it to check potentially hundreds of objects against hundreds of others, with all objects in motion!

hm… and how about

threshold_squared = threshold ** 2
if (Object2.location-Object1.location).length_squared < threshold_squared:

thanks CoDEmanX!

one thing i noticed about that approach, though, is that to get location values at a particular frame, you must first set scene.frame_current. seems simple enough, except i’m finding scripts take a noticeable performance hit when you globally change the scene frame (i’m guessing it evaluates animations for the entire scene). so instead i’ve been going the route of using the evaluate() function on individual f-curves.