Computer apparatus and method for finite element identification in interactive modeling

• US 5,289,567 A
• Filed: 04/01/1991
• Issued: 02/22/1994
• Est. Priority Date: 04/01/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Roth, James W.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/678,691
• Time in Patent Office: 1,058 Days
• Field of Search: 395/119, 395/120, 395/133, 395/155, 395/161
• US Class Current: 345/420
• CPC Class Codes: G06F 30/23 using finite element methods [FEM] or finite difference methods [FDM]

Abstract

Computer apparatus for querying elements of a finite element model. The apparatus includes a tree data structure having leaf nodes corresponding to elements of the model and intermediate nodes corresponding to subsets of elements of the model. The tree data structure is recursively constructed in a working memory in response to initial user command to query a desired model. The tree data structure is traversed in response to user interaction with a desired element of the model displayed in a screen view on a display unit. Within an intermediate level of the tree, nodes in the level are arranged according to spatial relationship of corresponding subsets of elements of the model with respect to at least one axis of a geometric area covered by the elements in a screen view of the model. The tree is traversed according to geometric area in which the desired element is positioned in the screen view of the model. The traversal results in location of a leaf node which corresponds to the desired element and which provides an indication of memory location of data of the desired element for access thereof. Such memory location and access of data of an element is on the order of the log of the number of model elements, which is faster than a linear search for element data in the memory.

Claims

1. In a computer system having (i) a source of models of objects, each model formed of a plurality of elements, (ii) a memory area holding data defining each element, (iii) a display unit for displaying screen views of a model, and (iv) a digital processor coupled to the source of models, memory area and display unit, the digital processor enabling user interaction with the screen view of a desired one of the models, computer apparatus for accessing from the memory area data of elements of a desired mode, computer apparatus comprising:

(a) a memory for holding a data tree, the data tree having;

a root node, and

a plurality of tree nodes and leaf nodes corresponding to subsets of elements of a desired model,

the root node and plurality of tree nodes and leaf nodes arranged in a hierarchy such that the root node is at a highest level, the tree nodes are at intermediate levels and leaf nodes are at a lowest level, each leaf node providing an indication of location in the memory area of data of corresponding elements,

within each of the intermediate levels, nodes in a common level being arranged according to spatial relationship of corresponding subsets of elements of the model with respect to at least one axis of a geometric area covered by the elements of the corresponding subsets in a screen view of the model; and

(b) the digital processor capable of traversing the data tree in response to user interaction with a desired element of a model display on the display unit, the digital processor traversing the tree according to geometric area in which the desired element is positioned in a screen view of the model, the digital processor locating a leaf node in the tree corresponding to the desired element, and from the leaf node the digital processor obtaining indication of location in the memory area of data of the desired element, such that the digital processor may access the data using the location in the memory area of data of the desired element.

2. Computer apparatus as claimed in claim 1 wherein the digital processor performs a recursive routine for traversing the tree.

3. Computer apparatus as claimed in claim 1 wherein the data tree is recursively constructed by the digital processor in a working memory in response to an initial user command to query a desired model.

4. Computer apparatus as claimed in claim 1 wherein the geometric area covered by elements corresponding to nodes in a common level is rectangular and has a longitudinal axis, such that the nodes in the common level are arranged with a first node corresponding to a subset of elements lying on one side of the longitudinal axis being positioned at one end of the common level, a second node corresponding to a subset of elements lying on an opposite side of the longitudinal axis being positioned at an opposite end of the common level, and a third node corresponding to a subset of elements bridging the longitudinal axis being positioned between the first and second nodes in the common level.

5. Computer apparatus as claimed in claim 4 wherein the rectangular geometric area further includes a minor axis transverse to the longitudinal axis;

and

the data tree further has a leaf node corresponding to a subset of elements straddling both the longitudinal and minor axes.

6. Computer apparatus for user interaction with finite element models comprising:

a digital processor;

a first memory coupled to the digital processor

for holding a plurality of models of objects, each model formed of a multiplicity of elements;

a second memory coupled to the digital processor for holding data defining each element of the models;

a display unit coupled to the digital processor for displaying screen views of the desired model;

a working memory coupled to the digital processor for holding a tree data structure of a desired model, the tree data structure having a plurality of leaf nodes and tree nodes, the leaf nodes corresponding the plurality of elements of the model and the tree nodes corresponding to sets of element of the model, each tree node providing an indication of the leaf nodes of the corresponding elements, and each leaf node providing an indication of location in the second memory of data defining the corresponding the element; and

the digital processor capable of traversing the tree data structure in response to user interaction with a desired element of the model during display of a screen view of the model on the display unit, the digital processor traversing the tree data structure from tree nodes to a leaf node corresponding to the desired element, such that location in the second memory of data defining the desired element is obtained in an amount of time that is proportional to (log n) where n is the number of elements in the desired model.

7. Computer apparatus as claimed in claim 6 wherein the digital processor performs a recursive routine for traversing the tree data structure.

8. Computer apparatus as claimed in claim 6 wherein the tree nodes and leaf nodes of the tree data structure are arranged in a hierarchy of levels according to spatial relationship of corresponding elements with respect to an axis of a geometric area covered by the elements in the model, nodes in a common level being arranged such that a first node corresponding to a set of elements lying on one side of the axis is positioned at one end of the common level, a second node corresponding to a set of elements lying on an opposite side of the axis is positioned at an opposite end of the common level, and a third node corresponding to a set of elements straddling the axis is positioned between the first and second nodes of the common level.

9. Computer apparatus as claimed in claim 8 wherein the geometric area is rectangular in shape and the axis is a longitudinal axis.

10. Computer apparatus as claimed in claim 8 wherein:

the geometric area further includes a transverse axis; and

the leaf nodes include nodes corresponding to elements of the model that bridge both axes.

11. In a computer system having (i) a source of models of objects, each model formed of a plurality of elements (ii) a first memory area holding data defining each element, (iii) a display unit for displaying screen views of a model and (iv) a digital processor enabling user interaction with the screen view of the model, a method for accessing from memory data of elements of a desired model comprising the steps of:

providing in a working memory a data tree having a root node and a plurality of tree nodes and leaf nodes, the leaf nodes corresponding to elements of a desired model and the tree nodes corresponding to sets of the elements, the root node and plurality of tree nodes and leaf nodes arranged in a hierarchy such that the root node is at a highest level, the tree nodes are at intermediate levels and leaf nodes are at a lowest level, each leaf node providing an indication of location in the first memory area of data of corresponding elements, within each of the intermediate levels, nodes in a common level being arranged according to spatial relationship of corresponding sets of elements of the model with respect to at least one axis of a geometric area covered by the elements in a screen view of the model;

in response to user interaction with a desired element of a model displayed in the screen view of the display unit, traversing the tree according to geometric area in which the desired element is positioned in the displayed screen view of the model, the step of traversing including locating a leaf node in the data tree corresponding to the desired element; and

from the located leaf node, obtaining indication of location in the first memory area of data of the desired element, such that the digital processor may access the data using the location in the first memory area of data of the desired element.

12. A method as claimed in claim 11 wherein the step of providing a data tree includes recursively constructing the tree in the working memory area in response to an initial user command to query a desired model.

13. A method as claimed in claim 11 wherein the step of traversing the data tree and locating a leaf node corresponding to the desired element further includes recursively searching for the leaf node.

14. A method as claimed in claim 11 wherein the step of providing a data tree further includes:

defining a rectangular boundary of the geometric area covered by the elements such that there is a major axis and a transverse minor axis of the geometric area; and

arranging tree nodes of a common level by

(i) positioning at one end of the common level, a first tree node corresponding to a set of elements lying on one side of the major axis,

(ii) positioning at an opposite end of the common level, a second tree node corresponding to sets of elements lying on an opposite side of the major axis; and

(iii) positioning between the first and second tree nodes, a third node corresponding to element straddling the major axis.

15. A method as claimed in claim 14 wherein the step of providing a data tree further includes defining leaf nodes corresponding to elements of the model that straddle both the major and minor axes.