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 on other sites

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 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 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.

Create an account

Register a new account

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 14
• 10
• 33
• 23