Efficient data structure

• US 20060143202A1
• Filed: 11/27/2002
• Published: 06/29/2006
• Est. Priority Date: 11/27/2002
• Status: Active Grant

• Current Assignee: Zyvex Labs, Llc
• Original Assignee: Zyvex Corporation
• Inventors: Parker, Eric G.
• Granted Patent: US 7,519,603 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

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.

Claims

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

plurality of nodes associated 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 and

the hierarchical arrangement of nodes comprises leaf nodes, wherein each leaf node is associated with data that defines spatial content of the spatial region subdivision associated with the leaf node.

2. The data structure of claim 1 wherein the hierarchical arrangement of nodes does not comprise a repeated pattern from any two nodes.

3. The data structure of claim 1 wherein the data represents a material composition.

4. The data structure of claim 3 wherein the material composition is selected from the list consisting of:

a semiconductor material, a ceramic, an oxide material, and a metal.

5. The data structure of claim 3 wherein the non-binary data represents a Micro-Electro-Mechanical device.

6. The data structure of claim 1 wherein the spatial region is a two-dimensional region and the tree arrangement is a quadtree arrangement.

7. The data structure of claim 1 wherein the spatial region is a three-dimensional region and the tree arrangement is an octree arrangement.

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

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

processing means configured to modify data that represents at least a portion of the defined engineered structure, 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 a spatial subdivision of another node associated with a higher hierarchical level; and

the data includes content data associating each of the plurality of leaf nodes with contents of a corresponding regular subdivision of the engineered structure.

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

10. The CAD system of claim 8 wherein the content data represents a material composition.

11. The CAD system of claim 10 wherein the material composition is selected from the list consisting of:

a semiconductor material, a ceramic, an oxide material, and a metal.

12. The CAD system of claim 10 wherein the engineering structure comprises a Micro-Electro-Mechanical device.

13. The CAD system of claim 8 wherein the engineered structure is a two-dimensional structure and the tree arrangement is a quadtree arrangement.

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

15. The CAD system of claim 8 further comprising:

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

16. The CAD system of claim 15 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.

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

18. A program product, comprising:

a computer-readable storage medium; and

means recorded on the computer-readable storage medium for processing data associated with a multidimensional object, wherein;

the data substantially represents the multidimensional object as corresponding to a plurality of nodes hierarchically arranged in a shared, regularly-subdivided tree arrangement;

the plurality of nodes each correspond to at least one of a plurality of regular spatial subdivisions of the multidimensional object;

the plurality of hierarchical nodes comprises pluralities of first and second nodes;

the data includes content data and pointer data;

the content data is associated with the plurality of first nodes;

the pointer data is associated with the plurality of second nodes; and

the pointer data links each of the plurality of second nodes to a corresponding one of the plurality of first nodes where ones of the plurality of multidimensional object subdivisions corresponding to linked ones of the pluralities of first and second nodes have substantially similar contents.

19. The program product of claim 18 wherein the content data associated with the plurality of first nodes includes at least one of a plurality of data values, wherein the plurality of data values includes at least three different data values each corresponding to a different content, and wherein at least one of the plurality of first nodes is associated with each of the at least three different data values.

20. The program product of claim 18 wherein the multidimensional object is a three-dimensional object and the tree arrangement is an octree arrangement.