Content deleted Content added
kill my mentioning of preprocessing: the simpler intro the better. "Efficiency" mentioned instead |
added generation section, some other edits |
||
Line 11:
The downside is the requirement for a time consuming pre-processing of the scene, which makes it impossible to 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's BSP implementation). Other uses include [[ray tracing]] and [[collision detection]].
==Generation==
Binary space partitioning is a generic process of [[recusion|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 a implementation. In 3D space, planes are used to partition and split an object's faces; in 2D space lines plit 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 vertexes of the polygon and intersected none of its segments. If the partitioning line interesects 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.
[[Image:Binary space partition.png|thumb|center|460px|1. A is the root of the tree and the entire polygon<br/>2. A is split into B and C<br/>3. B is split into D and E.<br/>4. D is split into F and G, which are convex and hence become leaves on the tree.]]▼
Since the usefulness of a BSP tree depends upon how well it was generated a good algorithm is essential. Most algorithms will test many possibilites 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 usuallly requires long computations.
There is a Java applet which demonstrates the process of tree generation at the address: http://symbolcraft.com/graphics/bsp/
==BSP (binary space partition) tree==
Line 64 ⟶ 78:
▲[[Image:Binary space partition.png|thumb|center|460px|1. A is the root of the tree and the entire polygon<br/>2. A is split into B and C<br/>3. B is split into D and E.<br/>4. D is split into F and G, which are convex and hence become leaves on the tree.]]
==Other space partitioning structures==
BSP trees are closely related to [[quadtree]]s and [[octree]]s
==External Link==
| |||