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?
Answer
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.
No comments:
Post a Comment