Bounding Volume: Exploring Spatial Representation in Computer Vision

By Fouad Sabry

What is Bounding Volume

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed region that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations, such as by using simple regions, having simpler ways to test for overlap.

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Bounding volume

Chapter 2: Sphere

Chapter 3: Ellipsoid

Chapter 4: Collision detection

Chapter 5: Cone

Chapter 6: Cylinder

Chapter 7: Convex polytope

Chapter 8: Bounding volume hierarchy

Chapter 9: Minimum bounding box

Chapter 10: Geometric separator

(II) Answering the public top questions about bounding volume.

(III) Real world examples for the usage of bounding volume in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Bounding Volume.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: May 4, 2024

Book preview

Chapter 1: Bounding volume

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that entirely encloses their union. Using simple volumes to hold more complicated objects, bounded volumes are used to increase the efficiency of geometrical processes. Typically, simpler volumes have simpler overlap detection methods.

A bounding volume for a collection of items is also a bounding volume for the object formed by their union, and vice versa. Therefore, the description can be restricted to a single object, which is presumed to be non-empty and bounded (finite).

Most frequently, bounding volumes are utilized to speed particular types of tests.

In ray tracing, bounding volumes are utilized for ray-intersection tests, and in many rendering techniques, they are utilized for frustum tests. If the ray or viewing frustum does not intersect the bounding volume, it is impossible for it to intersect the item enclosed therein, allowing for trivial rejection. Likewise, if the frustum contains the totality of the bounded volume, the contents may be accepted without additional examination. These intersection tests generate a list of displayable objects (rendered; rasterized).

When two bounding volumes in collision detection do not intersect, the included objects cannot collide.

Due to the simplified geometry of a bounding volume, testing against it is often far faster than testing against the item itself. This is due to the fact that a 'object' is often constructed of polygons or data structures that are approximated using polygons. If an object is not visible, it is computationally inefficient to test each polygon against the view volume. (Onscreen objects must be clipped to the screen whether or not their surfaces are visible.)

To acquire the bounding volumes of complex objects, it is customary to use a scene graph or a bounding volume hierarchy, such as OBB trees, to decompose the objects/scene. The main idea is to organize a scene in a tree-like structure, with the root representing the entire scene and each leaf representing a component.

A visual hull is a boundary volume reconstructed from silhouettes of an item in computer stereo vision.

the computational cost of computing a bounding volume for an object, the cost of updating it in applications where the objects can move or change shape or size, the cost of determining intersections, and the desired precision of the intersection test influence the selection of the type of bounding volume for a given application. The precision of the intersection test is proportional to the amount of void space within the bounding volume that is not associated with the bounded object. In general, sophisticated bounding volumes allow for less vacant area but incur more processing costs. It is typical to employ multiple types simultaneously, such as a cheap one for a quick but imprecise test alongside a more exact but also more expensive one.

All of the types discussed here have convex boundary volumes. If it is known that the item being constrained is convex, this is not a constraint. If non-convex bounding volumes are needed, they can be represented as the union of many convex bounding volumes. Unfortunately, intersection checks grow progressively more expensive as the complexity of the bounding boxes increases.

The object's bounding box is a cuboid or, in two dimensions, a rectangle. In dynamical simulation, bounding boxes are favored over alternative types of bounding volume, such as bounding spheres or cylinders, for roughly cuboid-shaped objects when the accuracy of the intersection test is essential. For objects that rest upon others, such as an automobile lying on the ground, the benefit is evident. A bounding sphere would indicate that the car may intersect with the ground, which would require a more expensive test of the actual model of the car to reject; however, a bounding box would immediately indicate that the car does not intersect with the ground, thereby eliminating the need for the more expensive test.

In a number of applications, the bounding box is aligned with the axes of the coordinate system, at which point it is referred to as an axis-aligned bounding box (AABB). To differentiate the general situation from an AABB, an arbitrary bounding box is sometimes referred to as an oriented bounding box (OBB) or an OOBB when the local coordinate system of an existing object is employed. AABBs are easier to verify for intersection than OBBs, but when the model is rotated, they must be recalculated and cannot simply be rotated with it.

A bounding capsule is a swept sphere (the volume a sphere occupies as it moves along a straight line segment) that encloses the object. The radius of the swept sphere and the section across which the sphere is swept can be used to symbolize capsules. It shares characteristics with a cylinder, but is easier to manipulate because the intersection test is less complicated. A capsule and another object intersect if the distance between the capsule's defining segment and a feature of the other object is less than the radius of the capsule. Two capsules intersect, for instance, if the distance between their segments is less than the sum of their radii. This is true for arbitrarily rotating capsules, which makes them more desirable than cylinders in practical applications.

A circumscribing cylinder is a cylinder that contains the item. The axis of the cylinder is often aligned with the vertical direction of the scene in the majority of applications. Cylinders are suitable for three-dimensional objects that can only rotate along a vertical axis, but not about any other axes, and are otherwise limited to translational movement exclusively. Two vertical-axis-aligned cylinders collide when their projections on the vertical axis – two line segments – and their projections on the horizontal plane – two circular disks – intersect simultaneously. Each is simple to test. In video games, bounding cylinders are frequently employed as bounding volumes for upright individuals.

An object's bounding ellipsoid is the ellipse that contains the object. Typically, ellipsoids produce tighter fittings than spheres. Intersections with ellipsoids are accomplished by scaling the other object along the primary axes of the ellipsoid by a factor equal to the multiplicative inverse of the ellipsoid's radii, so simplifying the problem to crossing the scaled item with a unit sphere. If the applied scaling introduces skew, care must be taken to avoid complications. Skew can render the use of ellipsoids impracticable in some circumstances, such as when two arbitrary ellipsoids collide.

A bounding sphere is a sphere in which the object is contained. In two-dimensional graphics, this is a circle. The center and radius of a spherical boundary represent it. Two spheres collide when the distance between their centers is less than the total of their radii. This is a very rapid test for collision. This makes