Soundbomber's picture

3D extents

Does anyone know of a method to calculate the extents for all 3D objects in a scene?
So I want x_min,x_max........z_max calculated by comparing each solid after any transformations.


Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
objarni's picture

Just multiply each vertex coordinate with the current ModelView matrix and Max/Min the result in x-y-z. Pseudo code:

vector3 min, max = ...; // make max == MinValue in each axis, and min == MaxValue
foreach(vector3 v in AllVertices()) {
  vector3 u = ModelViewMatrix * v;
  min.x = Math.Min(u.x, min.x);
  // same for Max and y, z
}

Now min,max define your bounding box.

Soundbomber's picture

So no nice obscure function somewhere that does all that for me?

objarni's picture

I don't know if there is some vertex shader trick that can do it for you ... Like rendering all graphics and saving the max/min values. But I doubt it's going to be faster than the above, since you have to round-trip the gfx card with all data. But that is deep water for me, maybe someone with real shader experience instead of "read class" experience can give a clearer answer.

the Fiddler's picture

No, not really.

You typically define bounding boxes when you create your models (you can also use spheres or other bounding primitives). Since transforming bounding primitives is relatively fast, doing it on the CPU shouldn't be a problem in typical scenes (it *will* become a problem if you start transforming hundreds or thousands of objects, but most games don't do that).

There are ways to do this on the GPU, but the GPU->CPU latency is higher than doing it on the CPU directly. If you simply need visibility information and can tolerate one or two frames of latency, you can use occlusion queries. There's also a crazy trick that gives you the bounding box of an object in the rgb components of an 1x1 texture, but this doesn't really have any practical use.

objarni's picture

+1 on Fiddlers advice. You should have bounding boxes of all models if they are somewhat complex (100+ triangles). Then you can loop over the transformed bounding boxes corners instead of over each and every model vertex.

However, if my scene was made up of 10-20 models with 10-20 triangles each, I wouldn't bother. The speed gain vs. the added complexity in code isn't worth adding BB for each model. (The speed gain would not be noticeable to a user, that's my rule-of-thumb for optimizating realtime graphics apps')

Soundbomber's picture

As all my objects have individual transforms as well as global ones, calculating the Bounding Box when I create my model isn't really an option. I don't quite yet have thousands of objects, closer to hundreds, but it's possible in the future. Do you feel that speed could become an issue if I calculate the BB on the fly (every frame render)?

objarni's picture

Calculating the BB on the fly - why? Are your objects animated (changing dynamically)?

If not, calculate the BB's in model space -- they won't change for the lifetime of the application. Make a copy-operation in the BB class and then transform that for Extents3d computation.

Soundbomber's picture

No - what am I thinking - of course I don't need to calculate the BB every render, just when one of my objects changes position (which isn't really what you would call animation - just a user input position change usually by changing a number in a textbox). So let me get this straight - If I create a bounding box for each object, then apply each objects transforms to that bounding box, I will then have a collection of BB's with which to compare the results and then have the equivalent of a 'global bounding box'.
Going to give it a try! Thanks.

Soundbomber's picture

This method doesnt give me 'true' orthogonal bounding boxes but orientated boxes. (see attached)
How could I get orthogonal boxes?

AttachmentSize
BB.PNG242.44 KB
the Fiddler's picture

Axis-aligned bounding boxes is the correct terminology, I think. Check out this gamasutra article on AABBs.