Space partitioning
Encyclopedia
In mathematics
, space partitioning is the process of dividing a space
(usually a Euclidean space
) into two or more disjoint subset
s (see also partition of a set
). In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions.
, meaning that a space (or a region of space) is divided into several regions, and then the same space-partitioning system is recursively
applied to each of the regions thus created. The regions can be organized into a tree, called a space-partitioning tree.
Most space-partitioning systems use plane
s (or, in higher dimensions, hyperplane
s) to divide space: points on one side of the plane form one region, and points on the other side form another. Points exactly on the plane are usually arbitrarily assigned to one or the other side. Recursively partitioning space using planes in this way produces a BSP tree, one of the most common forms of space partitioning.
Space partitioning is particularly important in computer graphics
, where it is frequently used to organize the objects in a virtual scene. Storing objects in a space-partitioning data structure
makes it easy and fast to perform certain kinds of geometry queries — for example, determining whether two objects are close to each other in collision detection
, or determining whether a ray intersects an object in ray tracing.
. A typical scene may contain millions of polygons. Performing a ray/polygon intersection test with each would be a very computationally expensive task. The use of a proper space partitioning data structure (kd-tree
or BVH
for example) can reduce the number of intersection test to just a few per primary ray, yielding a logarithmic time complexity
with respect to the number of polygons.
Space partitioning is also often used in scanline algorithms to eliminate the polygons out of the camera's viewing frustum
, limiting the number of polygons processed by the pipeline.
, an important step is design rule check. This step ensures that the completed design is manufacturable. The check involves rules that specify widths and spacings and other geometry patterns. A modern design can have billions of polygons that represent wires and transistors. Efficient checking relies heavily on geometry query. For example, a rule may specify that any polygon must be at least n nanometers from any other polygon. This is converted into a geometry query by enlarging a polygon by n at all sides and query to find all intersecting polygons.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, space partitioning is the process of dividing a space
Space
Space is the boundless, three-dimensional extent in which objects and events occur and have relative position and direction. Physical space is often conceived in three linear dimensions, although modern physicists usually consider it, with time, to be part of a boundless four-dimensional continuum...
(usually a Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
) into two or more disjoint subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s (see also partition of a set
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
). In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions.
Overview
Space-partitioning systems are often hierarchicalHierarchy
A hierarchy is an arrangement of items in which the items are represented as being "above," "below," or "at the same level as" one another...
, meaning that a space (or a region of space) is divided into several regions, and then the same space-partitioning system is recursively
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
applied to each of the regions thus created. The regions can be organized into a tree, called a space-partitioning tree.
Most space-partitioning systems use plane
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
s (or, in higher dimensions, hyperplane
Hyperplane
A hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...
s) to divide space: points on one side of the plane form one region, and points on the other side form another. Points exactly on the plane are usually arbitrarily assigned to one or the other side. Recursively partitioning space using planes in this way produces a BSP tree, one of the most common forms of space partitioning.
Space partitioning is particularly important in computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
, where it is frequently used to organize the objects in a virtual scene. Storing objects in a space-partitioning data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
makes it easy and fast to perform certain kinds of geometry queries — for example, determining whether two objects are close to each other in collision detection
Collision detection
Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...
, or determining whether a ray intersects an object in ray tracing.
Use in computer graphics
Space partitioning is heavily used in ray tracingRay tracing
In computer graphics, ray tracing is a technique for generating an image by tracing the path of light through pixels in an image plane and simulating the effects of its encounters with virtual objects. The technique is capable of producing a very high degree of visual realism, usually higher than...
. A typical scene may contain millions of polygons. Performing a ray/polygon intersection test with each would be a very computationally expensive task. The use of a proper space partitioning data structure (kd-tree
Kd-tree
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
or BVH
Bounding volume hierarchy
A bounding volume hierarchy is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes...
for example) can reduce the number of intersection test to just a few per primary ray, yielding a logarithmic time complexity
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
with respect to the number of polygons.
Space partitioning is also often used in scanline algorithms to eliminate the polygons out of the camera's viewing frustum
Viewing frustum
In 3D computer graphics, the viewing frustum or view frustum is the region of space in the modeled world that may appear on the screen; it is the field of view of the notional camera. The exact shape of this region varies depending on what kind of camera lens is being simulated, but typically it is...
, limiting the number of polygons processed by the pipeline.
Other uses
In integrated circuit designIntegrated circuit design
Integrated circuit design, or IC design, is a subset of electrical engineering and computer engineering, encompassing the particular logic and circuit design techniques required to design integrated circuits, or ICs...
, an important step is design rule check. This step ensures that the completed design is manufacturable. The check involves rules that specify widths and spacings and other geometry patterns. A modern design can have billions of polygons that represent wires and transistors. Efficient checking relies heavily on geometry query. For example, a rule may specify that any polygon must be at least n nanometers from any other polygon. This is converted into a geometry query by enlarging a polygon by n at all sides and query to find all intersecting polygons.
Types of space partitioning data structures
Common space partitioning systems include:- BSP trees
- QuadtreeQuadtreeA quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...
s - OctreeOctreeAn octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
s - kd-treesKd-treeIn computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
- BinsBin (computational geometry)In computational geometry, the bin data structure allows efficient region queries, i.e., if there are some axis-aligned rectangles on a 2D plane, answer the question Given a query rectangle, return all rectangles intersecting it. kd-tree is another data structure that can answer this question...
- R-treeR-treeR-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both research and real-world applications...
s - Bounding volume hierarchiesBounding volume hierarchyA bounding volume hierarchy is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes...
- SEADSs.