Efficient data structure

• US 7,519,603 B2
• Filed: 11/27/2002
• Issued: 04/14/2009
• Est. Priority Date: 11/27/2002
• Status: Expired due to Fees

• Current Assignee: Zyvex Labs, Llc
• Original Assignee: Zyvex Labs, Llc
• Inventors: Parker, Eric G.
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Brown; Sheree N
• Application Number:
  US10/306,464
• Publication Number:
  US 20060143202A1
• Time in Patent Office: 2,330 Days
• Field of Search: 707/100, 600/159, 345/440, 345420-421, 345/428, 716/6, 365/222, 703 1- 2, 700/184, 717/125, 715/823
• 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 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.