PDA

View Full Version : How to creat the bounding box ?



HaVyThoai
01-01-2008, 07:55 AM
Dear everybody,

I'm doing the NC machining simulator, I have created successfully the swept surface using Frenet frame. Now, the next work is that I have to take the swept surface to intersect stock (representing by Z vectors). My swept surface is series of triangles, and I have known the algorithm of Ray - Triangle intersection.

The problem I got is that how to create a bounding box around a given triangle so that Z vectors which in bounding box would be taken to intersect with that triangle, but it don't take the Z vectors outside the bounding box to do.

http://upload.tinhco.net/thoai/boundingbox.JPG

I never do this before, so the term "bounding box" is new to me. Is there any idea ? or a similiar example code would be nice :D

please, help me :)

HenriH
01-01-2008, 08:12 PM
A bounding box is a volume which is big enought to contain each vertex in a set of polygons, but no bigger. Generally there are two classes of bounding boxes: 1) axis aligned bounding boxes, which are always oriented along the cardinal axes (X, Y, Z), and 2) oriented bounding boxes which can be (obviously) oriented arbitrarily.

Because of the restriction, axis aligned bounding boxes are easier to calculate and tested for intersection. The simplest case for calculating an AABB, is to iterate over all vertices involved and expand the box as needed. Here is pseudo-code for calculating an AABB.

// min = minium coordinate of the box
// max = maxium coordinate of the box
Point min = V[0];
Point max = V[0];
for (i = 1; i < n; ++i)
{
if ( V[i].x < min.x ) min.x = V[i].x;
if ( V[i].y < min.y ) min.y = V[i].y;
if ( V[i].z < min.z ) min.z = V[i].z;
if ( V[i].x > max.x ) max.x = V[i].x;
if ( V[i].y > max.y ) max.y = V[i].y;
if ( V[i].z > max.z ) max.z = V[i].z;
}

Oriented bounding boxes are more complicated to calculate. Check for web resources if you wish to know.

I hope this helped.

k_szczech
01-02-2008, 12:05 PM
A bounding sphere will work faster.
It's a bit trickier to find a sphere, but it's a lot easier and faster to check ray-sphere intersection. I'm sure you'll find some whitepapers about bounding spheres easy enough.

One word of advice: creating one bounding box for every triangle will slow your application down. Bounding boxes/spheres are meant to contain many triangles (usually entire objects, fragments of objects or even groups of objects).

For collision detection (physics or AI) it's usually best to have 3-5 triangles in one bounding sphere or 5-10 triangles in one bounding box at least. And of course you put 5-10 of these bounding boxes/spheres into another, larger bounding box/sphere and so on, until you have one final bounding box/sphere for your entire scene.

For rendering it's better to have even more triangles in one bouding box, depending on how your vertex data is stored on the GPU. It's just faster to render 1000 polygons with one draw call than even 100 polygons with 10 draw calls (10*10).

jwatte
01-03-2008, 12:44 AM
Note that all the Z rays are parallel, and in the Z direction only. Bounding box tests will actually probably be faster. However, it will probably be even faster to map the triangles onto the stock, instead of the other way around. In this special case, all he really wants is a depth buffer, as seen from the stocks Z direction point of view.

HaVyThoai
01-03-2008, 11:38 AM
Thank you,

what jwatte said is really hard to understand, because I'm not good at OpenGL, I just experience it for 2 months. An example code would be nice :).