Content deleted Content added
m (structure) |
Frencheigh (talk | contribs) mNo edit summary |
||
Line 18:
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
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.
| |||