Binary space partitioning: Difference between revisions

Revision as of 10:03, 2 June 2024

Revision as of 10:07, 2 June 2024

Line 32:

==Overview==

[[File:2D Binary Index.svg|thumb|An example of a recursive binary space partitioning algorithm[[quadtree]] for a 2D index.]]

Binary space partitioning is a generic process of [[recursion|recursively]] dividing a scene into two until the partitioning satisfies one or more requirements. It can be seen as a generalization of other spatial tree structures such as [[K-d tree|''k''-d trees]] and [[quadtree]]s, one where hyperplanes that partition the space may have any orientation, rather than being aligned with the coordinate axes as they are in ''k''-d trees or quadtrees. When used in computer graphics to render scenes composed of planar [[Polygon mesh|polygons]], the partitioning planes are frequently chosen to coincide with the planes defined by polygons in the scene.