| Binary Space Partitioning |
Article Index for Binary |
Website Links For Binary |
Information AboutBinary Space Partitioning |
| CATEGORIES ABOUT BINARY SPACE PARTITIONING | |
| trees structure | |
| geometric algorithms | |
|
In simpler words, it is a method of breaking up intricately shaped polygons into convex sets, or smaller polygons consisting entirely of non- Reflex Angle s (angles smaller than 180o). For a more general description of space partitioning, see Space Partitioning . Originally, this approach was proposed in 3D Computer Graphics to increase the Rendering efficiency. Some other applications include performing geometrical operations with shapes ( Constructive Solid Geometry ) in CAD , Collision Detection in Robotics and 3D Computer Game s, and other computer applications that involve handling of complex spatial scenes. OVERVIEW In computer graphics it is desirable that the drawing of a scene be both correct and quick. A simple way to draw a scene correctly is the Painter's Algorithm : draw it from back to front painting the background over with each closer object. However, that approach is quite limited since time is wasted drawing objects that will be overdrawn later, and not all objects will be drawn correctly. Z-buffering can ensure that scenes are drawn correctly and eliminate the ordering step of the painter's algorithm, but it is expensive in terms of memory use. BSP trees will split up objects so that the painter's algorithm will draw them correctly without need of a Z-buffer and eliminate the need to sort the objects as a simple Tree Traversal will yield them in the correct order. It also serves as base for other algorithms, such as Visibility Lists , which seek to reduce overdraw. The downside is the requirement for a time consuming pre-processing of the scene, which makes it difficult and inefficient to directly implement moving objects into a BSP tree. This is often overcome by using the BSP tree together with a Z-buffer, and using the Z-buffer to correctly merge movable objects such as doors and monsters onto the background scene. BSP trees are often used by 3D Computer Game s, particularly First-person Shooter s and those with indoor environments. Probably the earliest game to use a BSP data structure was '' Doom '' (see Doom Engine for an in-depth look at ''Doom'' GENERATION Binary space partitioning is a generic process of Recursively dividing a scene into two until they satisfy one or more requirements, the specific method of division varying depending on its final purpose. For instance, in a BSP tree used for collision detection the original object would be partitioned until each part becomes simple enough to be individually tested, and in rendering it's desirable that each part be convex so that the Painter's Algorithm can be used. The final number of objects will inevitably increase since lines or faces that cross the partitioning plane must be split into two, and it is also desirable that the final tree remains reasonably balanced. Therefore the algorithm for correctly and efficiently creating a good BSP tree is the most difficult part of an implementation. In 3D space, planes are used to partition and split an object's faces; in 2D space lines split an object's segments. The following picture illustrates the process of partitioning an irregular polygon into a series of convex ones. Notice how each step produces polygons with fewer segments until arriving at G and F, which are convex and require no further partitioning. In this particular case, the partitioning line was picked between existing vertices of the polygon and intersected none of its segments. If the partitioning line intersects a segment, or face in a 3D model, the offending segment(s) or face(s) have to be split into two at the line/plane because each resulting partition must be a full, independent object. Since the usefulness of a BSP tree depends upon how well it was generated, a good algorithm is essential. Most algorithms will test many possibilities for each partition until finding a good compromise and might also keep backtracking information in memory so that if a branch of the tree is found to be unsatisfactory other alternative partitions may be tried. Therefore producing a tree usually requires long computations. OTHER SPACE PARTITIONING STRUCTURES BSP trees divide a region of space into two subregions at each node. They are related to Quadtree s and Octree s, which divide each region into four or eight subregions, respectively. where ''p'' is the number of dividing planes used, and ''s'' is the number of subregions formed. BSP trees can be used in spaces with any number of dimensions, but quadtrees and octrees are most useful in subdividing 2- and 3-dimensional spaces, respectively. Another kind of tree that behaves somewhat like a quadtree or octree, but is useful in any number of dimensions, is the ''k''d-tree . TIMELINE from {Link without Title}
REFERENCES {Link without Title} AN INVESTIGATION INTO REAL-TIME 3D POLYGON RENDERING USING BSP TREES. Andrew Steven Winter. April 1999. available online {Link without Title} S. Chen and D. Gordon. “Front-to-Back Display of BSP Trees.” IEEE Computer Graphics & Algorithms, pp 79–85. September 1991. {Link without Title} H. Fuchs, Z. M. Kedem and B. F. Naylor. “On Visible Surface Generation by A Priori Tree Structures.” ACM Computer Graphics, pp 124–133. July 1980. SEE ALSO
EXTERNAL LINKS |
|
|