Bounding Volumes

From Math Images
Revision as of 16:33, 25 July 2011 by Chanj (talk | contribs)
Jump to: navigation, search
Inprogress.png
Bounding Box
Bounding box.png
Fields: Algebra and Geometry
Image Created By: chanj

Bounding Box

A box bounding the Stanford Bunny mesh.


Basic Description

A bounding volume in computer graphics is a shape that encloses one or more objects. The shape should be the tightest fit to the set of objects. Many figures are complicated and have hundreds of vertices, which make up their shapes. By bounding them in simple geometric shapes, it would lower the computational cost when detecting collisions between multiple objects and checking for intersections in ray tracing.

A More Mathematical Explanation

Note: understanding of this explanation requires: *algebra, geometry

Ray tracing is a method of generating a graphical image on the screen. It is used display simulated o [...]

Ray tracing is a method of generating a graphical image on the screen. It is used display simulated optical effects such as shadows, reflection and refraction. Light rays are cast onto the scene and the program must test if the rays are intersecting the object in the scene. Depending on the surface of the object, the rays would determine how it would be rendered. Because the program must determine if the rays intersect the object’s vertices, the computational cost can be expensive. The bounding box or any simple geometric volume that is a tight fit to the object lowers the computational cost. With the box, the rays would not trace points that are not in the box, since that would mean the object does not exist outside of it.

The same concept applies to collision detection. With bounding volumes, there is a hierarchy of tests for intersections of vertices and edges. The program can quickly decide if the object are near each other before testing for the vertices of the object. For example, if there are two bounding spheres, and they are across the room from each other. The program can detect that from the center of one sphere to the other is bigger than both of their radii combined. If the distance is smaller, then we can compare the vertices to determine if they colliding. The first step saves computational power, since the vertices do not have to test against each other until the two objects are close together.

Different Bounding Volumes

Axis aligned bounding box
Oriented bounding box
Bounding sphere

Bounding Box
It is a cuboid that contains the object. It is best for shapes that are shaped like rectangles or squares. One use of this shape is to detect collision of cup on a table. Sometimes, an axis aligned bounding box is not the tightest fit for the shape (figure on the left), and the the tighter fit is a non-axis aligned box or an oriented bounding box (figure on the right). An axis aligned bounding box is easier to implement and test, but if the object is rotated, an oriented bounding box would have an advantage in computing cost.

Bounding Sphere
It is a sphere that encapsulate the object, like a hamster in a hamster ball. The challenge with this shape is finding the tightest fit. The images below (under "show more") show a bunny in a sphere, but there is a lot of empty space in the sphere because it was created using the box as guide, i.e. the sphere is bounding the box. The radius of the sphere was calculated using the distance from the center to a corner in the cuboid.

Bounding sphere large.png

Bounding box sphere large2.png

To find a tighter fitting sphere, a better method would be to compare the center point of the object to the vertices of the object, and the longest distance would be the radius. The challenging part of this method is finding where the center should be. Below (under "show more"), the center of the sphere is the center of the cubiod, and that point is compared with all the vertices on the bunny. The second image shows that the sphere is no longer bounding the red bounding box.

Tighter bounding sphere.png

Tighter bounding sphere-2.png

Even though the sphere above is a tighter fit, it is still not the tightest. Finding the correct center point for the sphere would get the tightest sphere. There are many different methods to finding the point closest to a tight fitting sphere, but there is no one correct way that works for any figure.

An arbitrary convex bounding volume

Other Bounding Volumes

Bounding volumes can be any shape. Other frequently used ones are ellipsoids, which are like flattened spheres, and cylinders. Cylinders are typically used to bound an upright human or human-like figure.


Why It's Interesting

blank

How the Main Image Relates

The image is a visual of a bounding on an object.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

About the Creator of this Image

I used OpenGL with C++. Most of the code belongs to User:Cutler.


Related Links

Additional Resources

Collision Detection by Robert Dunlop
Java: Bounding Sphere (javax.media.j3d.Bounds)
CGAL: Bounding Volumes

References

Barb Cutler's (User:Cutler) Lectures: Collisions, Ray Tracing

Future Directions for this Page

blank




If you are able, please consider adding to or editing this page!


Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.