Binary Space Partitioning (BSP) Tree
Jump to navigation
Jump to search
A Binary Space Partitioning (BSP) Tree is a Binary Tree that is based on Binary Space Partitioning.
- Example(s):
- k-d Tree.
- …
- Counter-Example(s):
- See: Ray Tracing (Graphics), Recursively, Euclidean Space, Convex Set, Hyperplane, Tree (Data Structure), 3D Computer Graphics, Rendering (Computer Graphics), Constructive Solid Geometry, Computer-Aided Design, Collision Detection.
References
2018
- (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Binary_space_partitioning Retrieved:2018-8-5.
- In computer science, binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of objects within the space by means of a tree data structure known as a BSP tree.
Binary space partitioning was developed in the context of 3D computer graphics,[1][2] where the structure of a BSP tree allows spatial information about the objects in a scene that is useful in rendering, such as their ordering from front-to-back with respect to a viewer at a given location, to be accessed rapidly. Other applications include performing geometrical operations with shapes (constructive solid geometry) in CAD,[3] collision detection in robotics and 3D video games, ray tracing and other computer applications that involve handling of complex spatial scenes.
- In computer science, binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of objects within the space by means of a tree data structure known as a BSP tree.
- ↑ Schumacker, Robert A.; Brand, Brigitta; Gilliland, Maurice G.; Sharp, Werner H (1969). Study for Applying Computer-Generated Images to Visual Simulation (Report). U.S. Air Force Human Resources Laboratory. p. 142. AFHRL-TR-69-14.
- ↑ Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). "On Visible Surface Generation by A Priori Tree Structures" (PDF). SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive techniques. ACM, New York. pp. 124–133. doi:10.1145/965105.807481.
- ↑ Thibault, William C.; Naylor, Bruce F. (1987). "Set operations on polyhedra using binary space partitioning trees". SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM, New York. pp. 153–162. doi:10.1145/37402.37421.