Patent ID: 6081624
Filing Date: 2000-06-27
Classification: G06T

Abstract:
A computer-implemented method for reducing storage requirements of data having spatial extents, comprising the steps of:(a) representing the data in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure; and(b) storing a Spatial ID in each node that comprises an encoded representation of the relation of the node's extents with respect to its parent node, in order to obtain the extents of the node without explicitly storing the data, wherein the encoded representation indicates the node's subdivision of the parent node's extents according to a type selected from a group comprising: (1) a normal octant subdivision; (2) a 1/16th expanded version of an octant subdivision along coordinate planes that divide root extents; and (3) a merger of a plurality of expanded octants along a coordinate axis.