Binary Space Partitioning (BSP) Algorithm
(Redirected from Binary Space Partitioning)
Jump to navigation
Jump to search
A Binary Space Partitioning (BSP) Algorithm is a Recursive Algorithm for subdividing a Euclidean Space into convex sets by means of a BSP tree.
- Context:
- It can be represented by a BSP Tree.
- Example(s):
- Counter-Example(s):
- See: Ray Tracing (Graphics), Recursively, Euclidean Space, Convex Set, Hyperplane, Tree (Data Structure), 3D Computer Graphics, Graphic Rendering Algorithm, Constructive Solid Geometry, Computer-Aided Design, Collision Detection.
References
2020
- (GeeksforGeeks, 2020) ⇒ https://www.geeksforgeeks.org/binary-space-partitioning/
- QUOTE: Binary space partitioning is treated as a generic process of recursively dividing a scene into two until the partitioning satisfies one or more requirements. It can be viewed as a generalization of other spatial tree structures such as k-d trees and quadtrees, one where hyperplanes that partition space may have any orientation instead of being aligned with the coordinate axes as they are in k-d trees or quadtree.
2019
- (Fan et al., 2019) ⇒ Xuhui, Fan Bin Li, Scott A. Sisson (2019)."Binary Space Partitioning Forests". In: The 22nd International Conference on Artificial Intelligence and Statistics, PMLR.
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.