I'm thinking that the straight-forward way would be to just iterate through the objects and just find the maximum and minimum coordinates on each axis, but this seems a little bit unoptimal.

Is there a faster, more efficient way of doing this?

  • \$\begingroup\$ may I ask, first is your scene 2D or 3D, and second why do you need a volume that contains all objects? \$\endgroup\$ – Ali1S232 Jun 24 '11 at 10:26
  • \$\begingroup\$ it's a 3D scene.I'm trying to build an octree to reduce the number of collision detection checks. \$\endgroup\$ – adivasile Jun 24 '11 at 10:47
  • 1
    \$\begingroup\$ @Gajet it has to be 3D, it's a volume ;-) \$\endgroup\$ – The Communist Duck Jun 24 '11 at 11:59

I don't know why or how exact your volume needs to be, but if you give each object a bounding sphere (you probably already have that, or it might be wise) you can very cheaply merge all these bounding spheres to find the entire volume. Of course this would still be O(N) but merging bounding spheres is really cheap.

Another solution would be spatial partitioning, you divide your world into large (axis aligned cube like) chunks and every time an object moves you update in which chunk it is, at the same time you can also check if the chunk it moved to is more to the outside as the last most outside part.

You have to take care though that if an object leaves one of the most outside parts you have to check if that outside chunk is now empty, and if so slightly shrink the volume.

A good way to do this would be to store an int[x,y,z] that stores how many objects are present, or another structure like a list, that stores a references to each object in that chunk.

Anyway if you clarify your question even further by describing what you're trying to accomplish we would probably be able to give you a better answer.

| improve this answer | |

When building an Octree, you can start at any size and change it later, for example, I once wrote an octree to help reduce the interation tests in my physics collision detection routine, and started out with size 1.0f for each axis. As physics elements were added to the scene, the octree grew, the first element was a 4.0f radius object somewhere quite far from the origin, lets say (5,4,100), so as there were no elements in the octree, I merely resized the root node (doubling it until it fit) to 128.0f.

The second element is where you see interesting things, the second element added was also outside the existing octree, (200,200,200, Radius4) so the root node could not hold it, so instead, i created a new double size root node, and pushed the current root node contents out into the 8 new nodes (only one created in this case as the octree was brand new)

The new root was big enough, so now I had two nodes, one root and one octree branch.

This carried on until all the elements were added to the scene, adding a new node at the root whenever the content was outside the existing range, adding new nodes at the branch whenever the number of items in the branch went over my arbitrary limit.

The side effect of starting with a small size and resizing cannot be overstated. Unless you're working in a constrained world, you're bound to go out-of-bounds at some point.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.