Jump to content
  • Advertisement
VanillaSnake21

Finding a bounding box around other boxes

Recommended Posts

I have individual bounding boxes around objects in my world, I'm trying to find one larger bounding box that encompasses all the bounding boxes of the small objects. How would I do that considering that my current bounding box is defined as such:

struct _bounding_box
{
	XMFLOAT3 center;
	float xExtent;
	float yExtent;
	float zExtent;
};

Also it's worth noting that all the bounding boxes are axis aligned.

At the moment what I'm doing is converting the (center, extent) representation into individual vertices and then finding the smallest and largest vertex, but this involves me decomposing each individual box into 8 verticies as such:

Vertex v1, v2, v3, v4, v5, v6, v7, v8;
v1.pos = center + xAxis*xExtent + yAxis*yExent;
v2.pos = center + xAxis*(-xExtent) + yAxis*yExtent;
v3.pos = center + xAxis*xExent - yAxis*yExtent;
//.. and so on

I feel like there might be some solution that allows me to directly use the (center, extent) representation of the boxes directly to find the overall bounding box. Is there?

Share this post


Link to post
Share on other sites
Advertisement

Assuming I'm understanding the question correctly, you don't need to compute all the vertices, because for each cardinal axis i, the extrema for an individual box can be found as:

min = center[i] - extents[i]
max = center[i] + extents[i]

(Note that it can be useful for this sort of algorithm to have indexed access available for vectors, and to represent the extents using a vector or other indexable type.)

From there, any given extremum for the encompassing bounding box is of course just the min or max (as appropriate) of all the corresponding min's/max's of the individual boxes.

Share this post


Link to post
Share on other sites
6 minutes ago, Zakwayda said:

Assuming I'm understanding the question correctly, you don't need to compute all the vertices, because for each cardinal axis i, the extrema for an individual box can be found as:


min = center[i] - extents[i]
max = center[i] + extents[i]

(Note that it can be useful for this sort of algorithm to have indexed access available for vectors, and to represent the extents using a vector or other indexable type.)

From there, any given extremum for the encompassing bounding box is of course just the min or max (as appropriate) of all the corresponding min's/max's of the individual boxes.

@Zakwayda That simplifies it by a bunch, thanks! 

The thing is that I'm trying to implement bounding volume hierarchies in my terrain at the moment and I have 60,000 of these said bounding boxes (one for each triangle) so having this extra internal loop is a bit much, but this 3 ply loop is actually much better than what I currently have, so I'll take it! I just thought there was some vector/matrix magic that could just run off the extents. 

Share this post


Link to post
Share on other sites

If instead of center and extent you were to store minimum and maximum values for each coordinate, you would just need to compute the minimum of the minimums and the maximum of the maximums.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!