Efficient way to find set of objects inside or intersecting bounding box?

Question

i'm having set of 3d objects {obj1,obj2,.....objn}, and a 3D bounding box B . Right now to find the set of objects inside or intersecting the bounding box B i'm using below code,which computes in O(n)

     for(int i = 0; i < n; i++){
            obj = objectsArray[i];
            objBox = obj.BoundingBox;
            if ((B.Max.Z > objBox.Max.Z || B.Max.Z > objBox.Min.Z) && (B.Min.Z < objBox.Max.Z || B.Min.Z < objBox.Min.Z) && (B.Max.X > objBox.Max.X || B.Max.X > objBox.Min.X) && (B.Min.X < objBox.Max.X || B.Min.X < objBox.Min.X) && (B.Max.Y > objBox.Max.Y || B.Max.Y > objBox.Min.Y) && (B.Min.Y < objBox.Max.Y || B.Min.Y < objBox.Min.Y)) {
                // obj is  inside or overlapping box B
                ObjectsInsideB.add(obj) 
             } else{
                // obj out of box B
             }
      }
// objBox.Max bounding box vertex at maximum end
// objBo.min bounding box vertex at minimum end

I'm looking for efficient way to compute this , to reduce O(n) search, is there any way ? As the bounding box B changes per frame, it is very slow for 100000 objects.

Do the object coordinates change too? Or is it just the bounding box that moves? — biziclop
– biziclop, Commented Nov 22, 2015 at 11:39
Just the bounding box moves, out of the total objects 10 % of objects are moving remaining are static. — VivekParamasivam
– VivekParamasivam, Commented Nov 22, 2015 at 11:43

Dave · Accepted Answer · 2015-11-22 12:23:23Z

1

When I once had to do something similar, I created a fixed set of bounding boxes for my points, (so each point was in exactly 1 box), then when given a query for a bounding box B (not necessarily in my set), I found the set of bounding boxes that collectively contained B (typically 8 of them) based on the coordinates of B, and quickly checked the points in them to see if they were in B.

If the size of B is fixed, use that size for the boxes in your fixed set.

E.g., in 3-space with n points randomly distributed in some large box, if we form our grid of subboxes by dividing each dimension into k pieces then each box will have about (1/k)^3 of our points.

answered Nov 22, 2015 at 12:23

Dave

9,1603 gold badges30 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

VivekParamasivam Over a year ago

sounds good , i will implement your method , and come back with pros and cons i face.

Dave Over a year ago

@GoodnezEverywer How did it go?

biziclop · Accepted Answer · 2015-11-22 12:35:05Z

1

You can sort your static objects by ascending X,Y and Z coordinates (so you have 3 lists of the same objects) and do binary search to find which objects fit in the X, Y, Z ranges (you only need to search for the first and the last), then intersect those results.

For the moving objects it's a bit trickier but if there are restrictions on movement speed, you can still put objects in rough categories, which you only re-calculate once every X frames.

answered Nov 22, 2015 at 12:35

biziclop

50k12 gold badges80 silver badges108 bronze badges

1 Comment

VivekParamasivam Over a year ago

thanks biziclop i will try your method and come up with pros and cons

TilmannZ · Accepted Answer · 2015-11-22 23:06:01Z

1

If I understand correctly, you may want to use a multi-dimensional index and perform a window query on them. Multi-dim indexes are build specifically for this. Simple standard multi-indexes are quadtree/octree, kd-tree and R-Tree. If you have a lot of objects, and if your objects are moving, you may want to have a look specialized moving-objects tree. On example of those would be the PH-Tree, here (Java) is an implementation that I wrote.

edited Nov 22, 2015 at 23:06

answered Nov 22, 2015 at 22:09

TilmannZ

1,89914 silver badges20 bronze badges

1 Comment

VivekParamasivam Over a year ago

thanks for the response tilmannz, i will update you after analysing your solution.

Collectives™ on Stack Overflow

Efficient way to find set of objects inside or intersecting bounding box?

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related