ABSTRACT
Working with large sets of objects, whether in two-dimensional or in three-dimensional, often requires performing various spatial queries to locate objects satisfying certain spatial conditions. One of the simplest tricks used in working with complex objects or groups of objects is to use Bounding Volumes. The bounding volume is just a sufficiently simple shape containing a complex shape inside. A simple and most often-used bounding volume is a rectangle with sides parallel to coordinate axes. It is very simple to build such a volume and checks with it also tend to be very simple and fast. Another example of an adaptive hierarchical spatial index are quad-trees or oct-trees. They have very much in common; the only difference is the dimension of the data they are built on. A simple solution to possible improportional boxes is to split the box in two parts every time along only one axis, choosing the axis for every split.
