Thread: Calculating min and max values of an arbitrary mesh.

1. Calculating min and max values of an arbitrary mesh.

How are the min and max values calculated for an arbitrary mesh? (for setting bounding volumes)

I know it has something to do with adding up the total verticies, and then dividing or subtracting something else..or not. I don't really know.

Thanks.

2. Just iterate through all the vertices keeping track of min/max x, y, and z?

3. That works too.

I was almost positive that there was some formula (or more complicated way) of doing it though. Maybe I confused it with something else?

4. None that I know of except using averaging and/or tracking min/max.

When you're loading the model you're iterating through all the vertices anyways, just check each one to find out if it is higher or lower then the one before...

Then store the minimum and maximum...

To me this sounds very costly though.

6. >To me this sounds very costly though.

why is that? you iterate through every vertex while you read it in anyway. And a couple of lt/gt's isn't going to hurt anything. The only alternative would be to store the bounds.

7. The way to setup bounding volumes is to use meshes. In the 3D modeler you will create your mesh and then also create a bounding mesh for it as well. The bounding mesh can double as your physics collision hull. In order to do accurate collision detection you must simplify your mesh which is done by creating a totally new one based on the actual mesh.

The bounding volume can either be included as a very simple cube mesh or you can iterate the vertices of the collision mesh/hull to find out the min/maxes.

8. Shrug, maybe you're right...

But those greater and less than signs might cause a problem with a couple if's in a loop of 5000++ vertices.

Course I could be underestimating the processing abilities of modern processors.

9. Once you have the min/max as perspective said, you can define the middle as:

Vector3 middle = (maxs + mins) * .5f;

If you want the mesh exactly centered around this 'middle,' while in object space, you simply do:

for(each_vertex)
vertices[current_vertex] -= middle;

And if you want a radius:

if(-mins.x > maxs.x)
else

..etc...

10. Originally Posted by Shamino
Shrug, maybe you're right...

But those greater and less than signs might cause a problem with a couple if's in a loop of 5000++ vertices.

Course I could be underestimating the processing abilities of modern processors.
I think you would get a greater bottle neck from disk I/O.

11. It's not like you need to do this every frame.

Anything you would need to do in computer graphics is never considered expensive just as long as you only need to do it once.

12. For my skeletal animation I'm looping through all vertices, normals and tangents once per frame for every model and recalculating them for the new skeleton. This process takes about 0.5 milliseconds for a model I've imported from Doom3 and with all optimisations on. And that is on a 4 years old computer, 1.6 GHz. Since I'm used to Flash I always underestimate the power nowadays myself I simulated a simulation (ehm, yes ^^) of half a million particles and that would run at about 25 fps, and that simulation involved a square root calculation for each particle along with ~40 lines of other calculations.

So I think that you can take the ~0.5 milliseconds at startup to calculate the bounding box for the mesh Thats at least what I'm going to do after I've figured out how to write a good scene manager.

EDIT: Small spelling mistake.

13. Got it working. The loading time didn't seem to increase at all, and if it did, it was by a very, very small amount.