Bounding volume
From Free net encyclopedia
In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex objects. Normally, simpler volumes have simpler ways to test for overlap.
Contents |
Uses of bounding volumes
Bounding volumes are most often used to accelerate certain kinds of tests.
In ray tracing, bounding volumes are used in ray-intersection tests, and in many rendering algorithms, it is used for viewing frustum tests. If the ray or viewing frustum does not intersect the bounding volume, it cannot intersect the object contained in the volume. These intersection tests produce a list of objects that must be displayed. Here, displayed means rendered or rasterized.
In collision detection, when two bounding volumes do not intersect, then the contained objects cannot collide, either.
Testing against a bounding volume is typically much faster than testing against the object itself, because of the bounding volume's simpler geometry. This is because an 'object' is typically composed of polygons or data structures that are reduced to polygonal approximations. In either case, it is computationally wasteful to test each polygon against the view volume if the object is not visible. (Onscreen objects must be 'clipped' to the screen, regardless of whether their surfaces are actually visible.)
To obtain bounding volumes of complex objects, a common way is to break the objects/scene down using a scene graph or more specifically bounding volume hierarchies like e.g. OBB Trees. The basic idea behind this is to organize a scene in a tree-like structure where the root comprises the whole scene and each leaf contains a smaller subpart.
Common types of bounding volume
A bounding sphere is a sphere containing the object. Spheres are very quick to test for collision with each other: two spheres are separated if the distance between their centres is greater than the sum of their radii. This makes bounding spheres appropriate for objects that can move in three dimensions.
A bounding cylinder is an upright axis-aligned cylinder containing the object. Cylinders are appropriate for objects that can rotate about the vertical axis but not about other axes, and especially appropriate for objects that are constrained to move along a flat horizontal surface. Two axis-aligned cylinders on a flat surface intersect if the horizontal distance between their axes is less than the sum of their radii. In video games, bounding cylinders are often used as bounding volumes for people standing upright.
A bounding box is a cuboid containing an object. In dynamical simulation, bounding boxes are better than other shapes of bounding volume such as bounding spheres or cylinders for objects that are roughly cuboid in shape, so that the intersection test is very accurate. This gives a benefit for objects that rest close to each other, for example a car resting on the ground: a bounding sphere would show the car possibly intersecting with the ground which would then be rejected by a more expensive test of the actual model of the car; a bounding box would show the car not intersecting with the ground, saving the more expensive test.
A bounding box is sometimes called an oriented bounding box (OBB) to distinguish it from an axis-aligned bounding box (AABB), which is a bounding box aligned with the axes of the co-ordinate system. Axis-aligned bounding boxes are simpler to test for intersection than oriented bounding boxes, but have the disadvantage that they cannot be rotated.
A discrete oriented polytope with k faces (k-DOP) is a convex polytope surrounding an object (in 2-dimensional graphics the DOP is a polygon; in 3-dimensional graphics it is a polyhedron). A DOP is constructed by taking k planes at infinity and moving them until they collide with the object. The DOP is the convex polytope resulting from intersection of the half-spaces bounded by the planes. Popular choices of DOP in 3-dimensional graphics include the bounding box, made from 6 axis-aligned planes, and the beveled bounding box, made from 10 (if beveled only on vertical edges, say) 18 (if beveled on all edges), or 26 planes (if beveled on all edges and corners).
A convex hull is the smallest convex polytope surrounding an object (the smallest possible DOP).
Basic Intersection Checks
For some types of bounding volume (OBB and Convex Polyhedra), an effective check is that of the Separating Axis Test. The idea here is that, if there exists an axis by which the objects do not overlap, then the objects do not intersect. Usually the axes checked are those of the basic axes for the volumes (the unit axes in the case of an AABB, or the 3 base axes from each OBB in the case of OBBs). Often, this is followed by also checking the cross-products of the previous axes (one axis from each object).
In the case of an AABB, this tests becomes a simple set of overlap tests in terms of the unit axes. For an AABB defined by M,N against one defined by O,P they do not intersect if (Mx>Px) or (Ox>Nx) or (My>Py) or (Oy>Ny) or (Mz>Pz) or (Oz>Nz).
An AABB can also be projected along an axis, for example, if it has edges of length L and is centered at C, and is being projected along the axis N:
r=0.5Lx|Nx|+0.5Ly|Ny|+0.5Lz|Nz|, and b=C*N or b=CxNx+CyNy+CzNz, and m=b-r, n=b+r
where m and n are the minimum and maximum extents.
An OBB is similar in this respect, but is slightly more complicated. For an OBB with L and C as above, and with I, J, and K as the OBB's base axes, then:
r=0.5Lx|N*I|+0.5Ly|N*J|+0.5Lz|N*K|
m=C*N-r and n=C*N+r
For the ranges m,n and o,p it can be said that they do not intersect if m>p or o>n. Thus, by projecting the ranges of 2 OBBs along the I, J, and K axes of each OBB, and checking for non-intersection, it is possible to detect non-intersection. By additionally checking along the cross products of these axes (I0×I1, I0×J1, ...) one can be more certain that intersection is impossible.
This concept of determining non-intersection via use of axis projection also extends to Convex Polyhedra, however with the normals of each polyhedral face being used instead of the base axes, and with the extents being based on the minimum and maximum dot products of each vertex against the axes. Note that this description assumes the checks are being done in world space.
