Computer Graphics:Applications of Previously Discussed Structures.
Applications of Previously Discussed Structures
Hidden Surface Removal: An Application of the BSP Tree
In addition to other algorithms, BSP (Binary Space Partitioning) trees are one example where a specific, widely used, data structure has direct application in computer graphics. Hidden surface removal is essential to realistic 3-D graphics, and a primary application of BSP trees.
Hidden surface removal is used anywhere 3-dimensional objects must be made visible from multiple, if not infinite view points within a graphics scene. Whether a scene is being viewed in a 3-D design application, or the latest sci-fi game, the problem is the same: objects furthest away from the user’s viewpoint may be hidden by closer objects. Therefore, the algorithm used to determine visibility must effectively sort the objects prior to rendering. This has been a hot topic until recent years, with researchers finding new and creative ways to tackle the problem. The z-buffer is now undeniably the most widely used algorithm. Tree algorithms are, on the other hand, also widely used where time-based rendering (animation) is not an issue, especially where the object positions are static. BSP trees are discussed in greater detail in Chapter 20.
The BSP tree is an example of a “painter’s algorithm.” [1] The basic concept of this algorithm involves sorting the objects (polygons) from back to front “relative to [the] view- point” and then drawing them in order. The key to the BSP algorithm in hidden surface removal is in the pre-processing, and encoding of the objects into a data structure that is later used to determine visibility. In other words, the data structure does not change, only the way it is viewed.
FIGURE 54.18: Objects in a plane.
For hidden surface removal, the BSP tree is built by passing a plane through each polygon in the scene. For each point p in front of the plane, f (p) > 0 and for each point behind the plane, f (p) < 0. The tree structure is created by applying this object to each polygon, and defining a “negative branch” and “positive branch” for each polygon relative to the current position in the tree. Also called the “half space” on each side of the plane, each vertex position in the tree is dictated by it position relative to the passing planes. One plane is treated as the root of the tree, and successive branches are defined from that root.
Because the relative position of vertices to each other is defined by the tree, regardless of position, the entire BSP tree can be pre-computed. Whether or not polygons in the tree are visible is then a function of their position in the viewer’s plane. Figure 54.19 demonstrates a BSP tree for vertices A through E shown in Figure 54.18.
FIGURE 54.19: BSP tree for Figure 54.18.
Note how each vertex can be located relative to at least two planes. For a viewpoint along h3, it is immediately apparent that vertex D is on the right, while A and E are on the left. Vertices C and B are located in the half space of h1 and h2, and are therefore of no interest. Vertices C and B will not be rendered. This relative method works for all positions in the BSP tree.
As mentioned, BSP trees are not a universal solution for hidden surface removal, mainly because of the pre-processing requirement. There is a major caveat; if the objects in the scene are moving, the pre-processing of the BSP tree is no longer valid as the polygons change relative position. The tree must be built every time the relative positions of objects within the tree change. Re-calculating the tree at each time step is often too slow, especially in 3-D gaming, where several million polygons must be rendered every second.
Another problem is that the BSP tree works in hidden surface removal only when “no polygon crosses the plane defined by any other polygon.” In other words, no object can be both behind and in front of another object for the BSP sorting algorithm to work. In gaming, it is common for objects to “collide” so this algorithm becomes even less desirable in these unpredictable conditions.
Proximity and Collision: Other Applications of the BSP Tree
Although BSP Tree structures are not as useful for determining the rendering order of moving polygons, they have other applications in graphics and gaming. For instance, trees are commonly used for collision detection, line-of sight, and other algorithms where the number of required calculations is lower. Determining between time-steps the relative positions of several (or several hundred) models, rather than several hundred million polygons, is much more feasible with today’s hardware. Enhanced Tree structures are even used in many of today’s more innovative artificial intelligence algorithms for gaming. These structures are used within the game space to quickly determine how an object sees, touches, and ultimately reacts with other objects.
Another widely used application of tree-based structures is application of Boolean operations to object construction. Constructive Solid Geometry, or CSG, modeling involves the construction of complex objects using only simple, primitive shapes. These shapes are added and subtracted to each other through “set operations,” or “Boolean operations.” The final objects are referred to as “compound,” “Boolean,” or “CSG” objects [4].
Figure 54.20 of a dumbbell illustrates a typical example of a CSG object.
To construct this object in a CSG environment, Boolean operations are applied to primitive objects. These operations are “intersection,” “union,” and “difference”[4]. Each step in the tree represents a boolean combination between two objects. The resulting object at each point in the tree is then combined again with another Boolean operation at the next step. This type of progression is continued until the finished object is created. Figure 54.21 illustrates the CSG tree used to construct this dumbbell using two spheres, a cylinder, and a half-plane.
A union operation is analogous to gluing two primitives together. An intersection operation results in only the portion (or volume) that both primitives occupy. Finally, a difference operation in effect removes the intersected section of one primitive from another. Armed with these three Boolean operations, modeling and displaying very complex shapes are possible. However, attempting to cover the surface of a final shape with a continuous mesh is another problem entirely, and the subject of numerous texts and papers. Consequently, CSG objects are largely used for initial visualization of a complete model. This solid model is then sent to another application that converts the model to a polygonal mesh.
FIGURE 54.21: CSG tree corresponding to Figure 54.20.
From a data structure and algorithm standpoint, CSG trees are quite useful. Firstly, and most obvious, the method utilizes the tree structure already mentioned throughout the text. Secondly, the final objects do not require individual mesh models to define them. Rather, each object is simply defined by its tree, where each node of the tree references primitives, such as the sphere, cone, cylinder, cube, and plane. With the basic models for the sphere, cone, etc. preprocessed and stored in memory, the overhead of CSG applications is kept to a minimum.
Many commercially available solid modeling and animation packages still provide CSG as a standard user-interface.
Comments
Post a Comment