Calculating min and max values of an arbitrary mesh.

• 04-19-2006
psychopath
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.
• 04-19-2006
Perspective
Just iterate through all the vertices keeping track of min/max x, y, and z?
• 04-19-2006
psychopath
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?
• 04-19-2006
VirtualAce
None that I know of except using averaging and/or tracking min/max.
• 04-20-2006
Shamino

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.
• 04-20-2006
Perspective
>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.
• 04-20-2006
VirtualAce
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.
• 04-20-2006
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.
• 04-20-2006
BobMcGee123
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...

• 04-20-2006
Quantum1024
Quote:

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.
• 04-20-2006
BobMcGee123
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.
• 04-21-2006
The Wazaa
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.
• 04-21-2006
psychopath
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.