Abstract:
In one embodiment, the present invention is directed to a data structure for representing a spatial region. The data structure comprises a hierarchical arrangement of nodes associated with a plurality of refinement levels, wherein each node of the hierarchical arrangement of nodes is a regular spatial subdivision of the spatial region or another node that is associated with a preceding refinement level. The hierarchical arrangement of nodes forms a directed acyclic graph. The hierarchical arrangement of nodes comprises at least two nodes that have respective edges that are traversed to a common child node such that the hierarchical arrangement of nodes does not comprise a repeated pattern from any two nodes of a common refinement level of the data structure.

Description:
TECHNICAL FIELD  
       [0001]     The present invention is generally related to data structures for the representation of spatial regions and, more particularly, to systems and methods for efficiently storing data sets that represent engineered structures.  
       BACKGROUND OF THE INVENTION  
       [0002]     In computer science, there are a number of data structures that have been developed to represent spatial data. For example, the quadtree data structure has been utilized to represent graphical data structures. A quadtree tree is a two dimensional data structure that represents objects hierarchically. Each child node of a quadtree represents a quadrant of a parent node.  
         [0003]      FIG. 1  graphically depicts exemplary quadtrcc  100  that includes nodes  101 ,  102 ,  103 , and  104  which are the first quadrants (spatial subdivisions) of the data structure. Node  103  is empty and, hence, does not contain any further child nodes. Accordingly, it is unnecessary to represent further spatial subdivisions of node  103 . A special code, character, or pointer-value may be used to implement node  103  to indicate that node  103  is an empty node. Nodes  101 ,  102 , and  104  are further subdivided. Specifically, the upper left and lower right quadrants of each of nodes  101 ,  102 , and  104  are occupied. Each of the parent nodes (nodes  101 ,  102 , and  104 ) may be implemented as a set of pointers (or other suitable characters or codes) to data structures that represent the respective child nodes. The empty child nodes of nodes  101 ,  102 , and  104  may be represented by the same special code, character, or pointer-value that is used to implement node  103 . The non-empty child nodes (nodes  105 - 110 ) of the parent nodes (nodes  101 ,  102 , and  104 ) may be represented in several ways. The non-empty child nodes may be represented as a pointer to a data structure that represents the contents of the child nodes. Alternatively, the non-empty child nodes may be represented by a suitable character or code that represents the contents of the child node. The implementation of the non-empty leaf nodes may depend upon the complexity of the contents of the leaf nodes. If the contents of the leaf nodes are limited (e.g., restricted to a small range of colors if the quadtree represents a graphical image), it may be more memory efficient to utilize a character or code as opposed to a pointer to another data structure.  
         [0004]     An octree is a generalization of the tree structure to three-dimensional space. Each node (“cube”) may be subdivided into eight further nodes.  FIG. 2  graphically depicts node  200  of the octree (which represents the entire spatial region associated with the octree), the first subdivided level  201  of the octree (which contains 8 nodes), and the second subdivided level  202  of the octree (which contains 64 nodes). In the same manner as a quadtree tree, leaf nodes may be identified at multiple levels of the same octree and a parent node may be implemented as a set of pointers to the respective child nodes of the parent node.  
         [0005]     Furthermore, a graph is another data structure that is well-known in computer science. A graph is a set of nodes and a set of edges where an edge is defined by the a pair of nodes it connects. A directed graph is a graph where the order of the nodes in an edge is relevant (e.g., the graph is traversed in a particular direction by an associated algorithm). Acyclic means there are no cycles in the graph, i.e., no path through the graph can traverse the same node more than once.  FIG. 3  depicts an example of a directed acyclic graph (DAG)  300  according to the prior art. DAG  300  begins at node A and continues to node B and then to node C. At node C, two edges may be traversed. At node C, an edge may be traversed by continuing to node E where the graph terminates. Also, at node C, another edge may be traversed by continuing to node D. From node D, DAG  300  continues to node E where the graph terminates.  100061  In one unusual known application, the binary quadtree data structure and the directed acyclic graph data structure were combined. Specifically, the adaptation of the “life algorithm” developed by Bill Gosper utilized this combination to represent the evolution of “life” in a finite two-dimensional space. The life algorithm begins by defining the presence or absence of life in each spatial subdivision of the finite two-dimensional space where a logical zero represents the absence of life and a logical one represents the presence of life. The life algorithm operates by determining whether existing life will continue or cease and whether life in each empty subdivision will develop. The algorithm makes these determinations upon the basis of density of life in adjacent spatial subdivisions. In essence, overcrowding leads to cessation of life while a certain amount of density is required for development. The life algorithm operates by iterating the determination of whether life will continue and whether life will develop. The advantage of the combination of the binary quadtree data structure and the DAG data structure is that similar patterns of “life” that arise in subsequent iterations do not require recalculation. Accordingly, the combination data structure simplifies the processing of the life algorithm.  
       BRIEF SUMMARY OF THE INVENTION  
       [0006]     The present invention is directed to a system and method which efficiently represent engineered or highly redundant data sets. Embodiments of the present invention are directed to a data structure for representing a complete region of space. The data structure may be related as a hierarchical arrangement of nodes associated with a plurality of refinement levels. Each node of the hierarchical arrangement of nodes may advantageously be a regular spatial subdivision of either the complete region of space or another node that is associated with a preceding refinement level. The hierarchical arrangement of nodes holds references or pointers at various nodes such that the hierarchical arrangement forms a directed acyclic graph. Also, the hierarchical arrangement of nodes does not comprise a repeated pattern of spatial subdivisions from any two nodes of a common refinement level. In embodiments of the present invention, the hierarchical arrangement does not comprise a repeated pattern of spatial subdivisions from any two nodes of the data structure. Additionally, the leaf nodes are advantageously associated with either a default value or a non-binary data structure that represents the contents of the respective leaf node.  
         [0007]     In embodiments of the present invention, such a data structure may be utilized to represent engineered devices. For example, embodiments of the present invention may provide a computer aided design (CAD) system to permit the design of Micro-Electro-Mechanical (MEMs) devices. MEMs devices may comprise a relatively large degree of redundancy due to the partial symmetry of discrete elements within the MEMs devices and the partial symmetry of MEMs devices themselves. Thus, embodiments of the present invention may store data representations of engineered devices with a substantial degree of efficiency by utilizing an advantageously designed data structure.  
         [0008]     The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims. The novel features which are believed to be characteristic of the invention, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that each of the figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present invention. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]     For a more complete understanding of the present invention, reference is now made to the following descriptions taken in conjunction with the accompanying drawing, in which:  
         [0010]      FIG. 1  depicts a quadtree according to the prior art;  
         [0011]      FIG. 2  depicts various levels of an octree according to the prior art;  
         [0012]      FIG. 3  depicts a directed acyclic graph according to the prior art;  
         [0013]      FIG. 4  depicts an exemplary object to be modeled by a data structure according to embodiments of the present invention;  
         [0014]      FIG. 5  depicts a pseudo-code representation of a DAG octree data structure according to embodiments of the present invention;  
         [0015]      FIGS. 6A-6C  depict various MEMs devices that are modeled using DAG octree data structures according to embodiments of the present invention; and  
         [0016]      FIG. 7  depicts a CAD system that utilizes a DAG octree data structure according to embodiments of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0017]     For the sake of illustration, reference is now made to  FIG. 4  which depicts object  400 . Object  400  is divided into octree elements or cubes. Object  400  may represent a manufactured object with each octree element representing the respective material used for the respective octree element or cube. The entire bottom portion of object  400  is shown as being empty. Specifically, element  401  (bottom front left), element  402  (bottom front right), and element  403  (bottom rear right element) are shown as being empty. The bottom rear left element is not shown in  FIG. 4  due to the perspective of the drawing. Element  406  (top rear right) and element  407  (top rear left) are shown as being uniformly composed of the same material. Element  404  (top front left) and element  405  (top front right) are identical and possess “checkerboard” designs. Specifically, the top front left, the top rear right, the bottom rear left, and the bottom front right sub-elements of elements  404  and  405  are uniformly composed of a selected material. As shown, elements  451 ,  452 , and  453  of element  404  are composed of the selected material (the other element is not shown due to the perspective of the drawing). Also, as shown, elements  454 ,  455 , and  456  of element  405  are composed of the selected material (the other element is not shown due to the perspective of the drawing).  
         [0018]      FIG. 5  depicts a pseudo-code representation of DAG octree  500  that represents object  400  according to embodiments of the present invention. OCTREE_ELEMENT_STRUCT_ 1  depicts the first regular spatial subdivision of the entire space occupied by object  400 , i.e., data elements  502  through  509  represent the eight octree elements or cubes at the first hierarchical level. Data elements  502 ,  503 , and  504  respectively represent elements  401 ,  402 , and  403  of object  400 . Data element  505  represents the bottom rear left corner of object  400  which is not shown in  FIG. 4 . All of these spatial subdivisions are identical. Accordingly, the spatial subdivisions are implemented using respective references or pointers to the same data structure (OCTREE_ELEMENT_STRUCT_ 4   590 ). Similarly, data elements  506  and  507  respectively represent elements  404  and  405  of object  400 . Because elements  404  and  405  are identical, DAG octree  500  does not separately represent each of these elements as separate data structures. Instead, data elements  506  and  507  may be advantageously implemented as references or pointers to refer to the same data structure (OCTREE_ELEMENT_STRUCT_ 2   550 ) that describes the same pattern. Data elements  508  and  509  represent the spatial subdivisions associated with elements  406  and  407 . Since elements  406  and  407  are identical, data elements  508  and  509  may be implemented as references to the same data structure (OCTREE_ELEMENT_STRUCT_ 3   570 ) that describes the same pattern.  
         [0019]     OCTREE_ELEMENT_STRUCT_ 2   550  represents another octree regular spatial subdivision. In this case, OCTREE_ELEMENT_STRUCT_ 2   550  represents a “checkerboard” pattern. Data elements  551 ,  553 ,  556 , and  558  may comprise a code or character that indicates that these elements are empty or associated with a default value. Data elements  552 ,  554 ,  555 , and  557  may comprise a non-binary data structure that represents the material composition of the associated elements (e.g., elements  451 ,  452 ,  453 , and the bottom rear left element which is not shown) of object  400 . Alternatively, each of data elements  552 ,  554 ,  555 , and  557  may comprise a pointer to a non-binary data structure that represents the material composition of the corresponding elements of object  400 . Likewise, OCTREE_ELEMENT_STRUCT_ 3   570  represents another octree regular spatial subdivision. In this case, OCTREE_ELEMENT_STRUCT_ 3   570  represents the uniform composition of elements  406  and  407  by comprising eight respective non-binary data structures  571 - 578  (or pointers thereto) that describes the particular composition associated with elements  406  and  407 . OCTREE_ELEMENT_STRUCT_ 4   590  represents another octree regular spatial subdivision. In this case, OCTREE_ELEMENT_STRUCT_ 4   590  represents the uniformly empty composition by comprising eight respective empty data structures  591 - 598 .  
         [0020]     DAG octree  500  provides several advantages. First, DAG octree  500  efficiently represents the redundancy of data associated with object  400 . For example, elements  404  and  405  of object  400  are identical. Accordingly, the paths associated with these elements are traversed by arriving at the same node via the pointers to OCTREE_ELEMENT_STRUCT_ 2 . Thus, the total amount of memory that is required to represent object  400  is reduced. It shall be appreciated that only a single copy of OCTREE_ELEMENT_STRUCT_ 2  is required regardless of how many times that the spatial pattern it represents occurs within the overall data structure. Additionally, it shall be appreciated that the compressed data representation of object  400  is lossless, i.e., object  400  may be fully reconstructed from the data structure of DAG octree  500  without loss of detail or resolution.  
         [0021]     The pseudo-code representation of DAG octree  500  is merely exemplary. Embodiments of the present invention may utilize any data structure representation or any suitable syntax or language to define a DAG tree structure that avoids or reduces repetition of patterns within the data structure. Also, it shall be appreciated that the present invention is not limited to octree structures. Embodiments of the present invention may operate with any arbitrary K-dimensional tree. Furthermore, embodiments of the present invention are not limited to the number of hierarchical levels shown in  FIGS. 4 and 5 . Embodiments of the present invention may utilize any number of hierarchical levels subject to storage capacity used for a particular implementation.  
         [0022]     It is appropriate to compare DAG octree structures according to embodiments of the present invention with concepts associated with known graphical data structures. Specifically, a certain amount of loss (e.g., by quantization) is thought to be typically required to store data that is used to create graphical images in an efficient manner. This assumption may be correct for various classes of data (e.g., digital photographs) related to graphical images. However, this assumption is not correct for specific classes of data. In particular, engineered objects may comprise a large degree of regularity or redundancy. Thus, engineered objects may be very efficiently represented by a DAG octree data structure according to embodiments of the present invention.  
         [0023]      FIGS. 6A-6C  represent engineered objects  601 - 603  which, for the sake of illustration, are MEMs devices. As shown, engineered object  601  is implemented in a space that occupies 452×562×92 spatial elements, engineered objected  602  is implemented in a space that occupies 3672×1594×92 spatial elements, and engineered object  603  is implemented in a space that occupies 15640×11046×96 spatial elements. Moreover, the representation of engineered objects  601 - 603  in the form of three dimensional arrays respectively required 68,555,504, 1,615,474,369 and 49,754,718,720 bytes of data. The representation of engineered objects  601 - 603  in the form of adaptive octrees respectively required 32,121,700, 812,738,552 and 11,900,655,552 bytes of data. According to embodiments of the present invention, the representation of engineered objects  601 - 603  in the form DAG octrees respectively required 2,613,536, 2,963,736 and 24,640,088 bytes of data. Thus, the representation of engineered objects  601 - 603  according to embodiments of the present invention entails a memory savings of 96.18% for object  601 , 99.81% for object  602 , and 99.95% for object  603  as compared to representation utilizing three dimensional arrays.  
         [0024]      FIG. 7  depicts computer aided design (CAD) system  700  according to embodiments of the present invention. CAD system  700  may be designed to create engineered objects (e.g., MEMs devices) from, in part, standard cell components. The standard cell components may be stored in library  701  stored utilizing mass storage device  706 . For the example of MEMs device design, the cell components may include discrete MEMs elements such as thermal actuators, electrostatic actuators, micro-grippers, micro-latches, micro-tethers, micro-rotators, and/or the like. The standard cell components may define the respective spatial composition of the various discrete elements.  
         [0025]     User interface  702  and CAD rendering program  703  may be implemented as software processes executing on computer system  705 . A user may “pick-and-place” discrete cell components utilizing user interface  702  and, in response, CAD rendering program  703  may select the respective cell component from cell library  701 . When the user “drops” the discrete cell component at a desired location, CAD rendering program  703  may locate the respective portions of DAG octree representation  704  of the device being designed. CAD rendering algorithm  703  may update the portions of DAG octree representation  704  to reflect the addition of the cell component. Specifically, the respective leaf nodes of DAG octree  704  may be created and/or modified to reflect the material composition(s) of the cell component at the respective locations. For MEMs devices, a non-binary data structure may be utilized to identify the possible material compositions such as semiconductor materials, oxides, ceramics, metals, and/or the like.  
         [0026]     Moreover, after the addition of a discrete component, CAD rendering algorithm  703  may examine DAG octree  704  to ensure that the addition of the data associated with the added element does not cause any repeated patterns within the nodes of DAG octree representation  704 . If a repeated pattern is discovered, CAD rendering program  703  may modify DAG octree representation  704  to comprise a reference or pointer to another suitable node of DAG octree representation  704  to eliminate the repeated pattern. Accordingly, CAD system  700  may store representations of engineered devices in an efficient manner thereby reducing the memory requirements necessary to operate CAD system  700 .  
         [0027]     Although embodiments of the present invention have been described in terms of operating with CAD systems, the present invention is not so limited. Embodiments of the present invention may operate with any data set that comprises sufficient redundancy to benefit from the described DAG K-dimensional tree data structure. For example, embodiments of the present invention may be utilized in medical imaging technology to represent biological structures in an efficient manner.  
         [0028]     Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims. Moreover, the scope of the present application is not intended to be limited to the particular embodiments of the process, machine, manufacture, composition of matter, means, methods and steps described in the specification. As one of ordinary skill in the art will readily appreciate from the disclosure of the present invention, processes, machines, manufacture, compositions of matter, means, methods, or steps, presently existing or later to be developed that perform substantially the same function or achieve substantially the same result as the corresponding embodiments described herein may be utilized according to the present invention. Accordingly, the appended claims are intended to include within their scope such processes, machines, manufacture, compositions of matter, means, methods, or steps.