Bounding Volumes
| Bounding Box |
|---|
 |
Bounding Box
- A box bounding the Stanford Bunny mesh.
Contents
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. There can be multiple levels of bounding volumes for a set of objects, e.g. smaller bounding boxes for different parts of a human figure (a box for the head and another for the torso, etc.) in a bigger box that bounds the whole body.
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
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.
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.
Other Bounding Volumes
Bounding volumes can be any shape. Other frequently used ones are ellipsoids, which are like flattened spheres, and cylinders. Ellipsoids are used for objects like fighter jets or figures where the length of the sides are not similar and would leave a lot of empty space if bounded by a sphere. Cylinders are typically used to bound an upright human or any humanoid figure. Besides the common bounding shapes, a convex hull, which is an arbitrary convex volume that contains the object(s) in the smallest space, can also be used.
Why It's Interesting
Ray tracing and collision detection is used in animation for films, special effects and video games. Although ray tracing can create photo-realistic looking images, like the image to the left by Henrik Wann Jensen, it is not efficient for real-time applications, like video games, because it is computationally expensive, which would need time to render. However accurate collision detection is important in video games, especially since modern games are becoming more realistic. For example, people are not supposed to walk through walls, so the character could only be a certain distance with the wall before the characters becomes absorbed by it. Bounding volumes are useful with collisions detection by putting a hierarchy of bounding volumes around the object. However, self-colliding objects, like cloth, is a more difficult problem.
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, available under Related Links, belongs to User:Cutler.
Related Links
Additional Resources
Code of the Images
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
- ↑ Jensen, Henrik W. (2001). http://graphics.ucsd.edu/~henrik/images/raytrace.html. Ray Tracing.
- ↑ Baraff, David. (2003). http://graphics.pixar.com/library/UntanglingCloth/index.html. Untangling Cloth.
Future Directions for this Page
- Pages focused on ray tracing and collision detection can be created.
- If someone finds a better way to make a tighter sphere, they can put up examples and explanations on the page, and put it up on Google Code.
- If someone has code and examples of different shapes, they can also put that up.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.
