In modern computer technologies, the spatial arrangement of objects usually includes a division of the space (scene) into smaller parts. The partitioning can be done in various ways, and the method can take into account different types of the space. For example, two-dimensional objects are often divided into quadrants; three-dimensional objects are often divided into octants. In two-dimensional and three-dimensional computer graphics, the partitioning of space is usually done during processing of data by a graphics pipeline in order to decrease future computations and minimize the number of objects sent for processing to the graphics pipeline. This is disclosed in greater detail in the US patent application 20030227455 A1 “Grid-based loose octree for spatial partitioning”.
Once the space has been divided, and all the objects of this space have been defined in suitable cells for them, the results are usually stored in a defined data structure for later use by the components of the graphic data processing, such as a video game engine or animation generator. The data structure is usually created after creating the scene, but prior to its visualization and prior to the moment of interaction of the user with the scene. During the visualization of the scene, it may be required to find an object in the scene that corresponds to a selected point. Having received the corresponding point in unidimensional coordinates (such as the x axis), or in two-dimensional coordinates (such as the coordinates of the x, y axes) or in three-dimensional coordinates (such as the coordinates of the x, y, z axes), or in multidimensional coordinates, the data structure enables a search in order to retrieve information on the object containing the selected point.
There are at least several existing techniques and data structures corresponding to these techniques for spatial partitioning. These include the regular coordinate grid, the binary tree, the tree of quadrants, the tree of octants, and the k-tree. Each technique has its own peculiarities.
Thus, for example, the binary tree has a root node, which has two child nodes (a left child node and a right child node). Each child node in turn can have two child nodes apiece, and so on. Each node constitutes a segment of space. Each segment is subdivided into two child segments. Each node of the data structure has a pointer, that is, the parent node points to the child nodes. A finer partitioning into segments of each subsequent level is done for zones with a substantial number of objects situated there. The binary tree can be subdivided uniformly or not uniformly, depending on the spatial partitioning algorithm used. The binary tree hierarchically partitions the space into segments down to a defined depth (level of detail).
The tree of quadrants has a structure similar to the binary tree, but the nodes of the tree of quadrants have a larger number of child nodes (usually four). Each node of the tree of quadrants constitutes a quadrant of the space. Each quadrant can be subdivided into child quadrants (usually four). Each parent quadrant can have pointers to the child quadrants. A finer partitioning into quadrants of each subsequent level is done for zones with significant number of objects situated there. The tree of quadrants can be subdivided uniformly or not uniformly, depending on the spatial partitioning algorithm used. The tree of quadrants hierarchically partitions the space into quadrants down to a defined depth (level of detail).
The tree of octants has a structure similar to the binary tree, and also similar to the tree of quadrants, but the nodes of the tree of octants have a larger number of child nodes (usually eight). Each node of the tree of octants constitutes an octant of the space. Each octant can be subdivided into child octants (usually eight). Each parent octant can have pointers to the child octants. A finer partitioning into octants of each subsequent level is done for zones with significant number of objects situated there. The tree of octants can be subdivided uniformly or not uniformly, depending on the spatial partitioning algorithm used. The tree of octants hierarchically partitions the space into octants down to a defined depth (level of detail).
The objects arranged in the cells (such as octants, quadrants, segments) can be divided when the partitioning boundaries intersect these objects. The processing of such divided objects requires significant resource costs.
Thus, while the usual computer systems in existence are acceptable, nevertheless an improvement of these systems is possible.