Efficient data structure

1. A computer aided design (CAD) system, comprising:

interface means configured to receive input defining at least a portion of an engineered structure;

processing means configured to modify data that represents at least a portion of the defined engineered structure, including the engineered structure's material composition, wherein:

the data structurally comprises a plurality of nodes hierarchically arranged in a shared, regularly-subdivided tree arrangement including a plurality of leaf nodes;

each of the plurality of nodes is associated with a spatial subdivision of another node associated with a higher hierarchical level; and

each of the plurality of leaf nodes is associated with one of a plurality of cube data structures each comprising a digital representation of a cubical spatial subdivision of the engineered structure and representing the material composition of the spatial subdivision of the engineered structure corresponding to the leaf node;

a library of component cells that are selectable via the interface means; and

means for storing the data and the library;

wherein the material composition is selected from a list consisting of: a semiconductor material, a ceramic, an oxide material, and a metal.

2. A computer aided design (CAD) system, comprising:

interface means configured to receive input defining at least a portion of an engineered structure;

processing means configured to modify data that represents at least a portion of the defined engineered structure, including the engineered structure's material composition, wherein:

the data structurally comprises a plurality of nodes hierarchically arranged in a shared, regularly-subdivided tree arrangement including a plurality of leaf nodes;

each of the plurality of nodes is associated with a spatial subdivision of another node associated with a higher hierarchical level; and

each of the plurality of leaf nodes is associated with one of a plurality of cube data structures each comprising a digital representation of a cubical spatial subdivision of the engineered structure and representing the material composition of the spatial subdivision of the engineered structure corresponding to the leaf node;

a library of component cells that are selectable via the interface means; and

means for storing the data and the library;

wherein the engineering structure comprises a Micro-Electro-Mechanical device.

3. A computer aided design (CAD) system, comprising:

interface means configured to receive input defining at least a portion of an engineered structure;

processing means configured to modify data that represents at least a portion of the defined engineered structure, including the engineered structure's material composition, wherein:

the data structurally comprises a plurality of nodes hierarchically arranged in a shared, regularly-subdivided tree arrangement including a plurality of leaf nodes;

each of the plurality of nodes is associated with a spatial subdivision of another node associated with a higher hierarchical level; and

each of the plurality of leaf nodes is associated with one of a plurality of cube data structures each comprising a digital representation of a cubical spatial subdivision of the engineered structure and representing the material composition of the spatial subdivision of the engineered structure corresponding to the leaf node;

a library of component cells that are selectable via the interface means; and

means for storing the data and the library;

wherein the processing means is operable to modify the data according to a component cell of the library that is selected via the interface means.

4. The CAD system of claim 3 wherein the processing means is operable to replace a repeated pattern with a reference to another node.

5. The CAD system of claim 3 wherein the plurality of nodes does not comprise a repeated pattern from any two nodes.

6. The CAD system of claim 3 wherein the engineered structure is a three-dimensional structure and the tree arrangement is an octree arrangement.

7. A data structure for representing a spatial region, comprising:

a plurality of cube data structures, each cube data structure comprising a cubical digital representation of non-binary data defining a material composition pattern, wherein no two cube data structures represent identical material composition patterns; and

a plurality of nodes hierarchically arranged in a shared, regularly-subdivided tree arrangement, wherein:

each node corresponds to a regular spatial subdivision of the spatial region;

the hierarchical arrangement of nodes forms a directed acyclic graph;

the hierarchical arrangement of nodes comprises leaf nodes that are each associated with one of the plurality of cube data structures;

each of the plurality of cube data structures represents the material composition of the spatial region subdivision associated with the leaf node;

each of the plurality of cube data structures associated with each leaf node includes at least one of a first data value, a second data value, and a third data value;

the first, second, and third data values are each unique relative to each other;

the first, second, and third data values each represent a corresponding one of three different material compositions;

a first one of the leaf nodes is associated with the first data value;

a second one of the leaf nodes is associated with the second data value;

a third one of the leaf nodes is associated with the third data value; and

each of the plurality of cube data structures is stored in a means for storing data.

8. The data structure of claim 7 wherein each of the three different material compositions is selected from the group consisting of: a semiconductor material, a ceramic, an oxide material, and a metal.