US5553206A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for producing mesh representations of objects
Assignee: International Business Machines Corp
•
Filing: 1993-02-12
•
Granted: 1996-09-03
•
Expires: 2013-02-12
Abstract
Abstract A method is provided for producing a mesh representation of an arbitrarily shaped object, for applications such as finite element analysis. The method includes the identifying elements of a mesh, such as a tetrahedral mesh, which are suitable, based on predetermined criteria, for merging into one of a predetermined set of target elements. For instance, if the predetermined set of target elements includes pentahedra and hexahedra, and the method operates on a tetrahedral mesh, then tetrahedra of the mesh are identified based on known ways of decomposing the target elements into tetrahedra. The groups of tetrahedra are identified based on whether they share faces in common, and whether they have faces which share a common edge and which are either coplanar or have an angle between the faces which satisfies a predetermined condition. The latter faces are referred to as quadrilateral pairs. A graph representation of the mesh is used, preferably including nodes representing regions of the mesh (i.e., tetrahedra) and edges between the nodes representing faces shared in common and quadrilateral pairs of faces. Using a search tree representation of a graph of a target element, the graph of the mesh is searched to identify subsets of the graph of the mesh, which represent groups of the tetrahedra of the mesh which are suitable for merging into the target element. By merging the tetrahedra this way, the total number of elements of the mesh is reduced, compared with the original tetrahedral mesh.
Inventors
- 👤 Siavash N. Meshkat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 03:02
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
181 words
A finite element modeling method for determining a physical attribute of an object using a mesh representation of the object the mesh including elements from a predetermined set of first and second elements, the method comprising the steps of: decomposing the object into a mesh including a set of tetrahedra; identifying a group of first elements of the mesh as being suitable for merging into a second element from the predetermined set; merging the identified group of first elements into the second element from the predetermined set; displaying a representation of the physical attribute of the object based on the mesh representation of the object produced by the steps of decomposing, identifying, and merging; and representing the tetrahedra produced in the step of decomposing in the form of a graph which shows (i) nodes representing the tetrahedra, (ii) first node connectors representing faces shared in common between pairs of the tetrahedra, and (iii) second node connectors representing two faces, each face being of different tetrahedra which have an edge in common and have an angle therebetween which satisfies a predetermined condition.
Claim 2
Dependent Claim
181 words
A finite element modeling method for determining a physical attribute of an object using a mesh representation of the object the mesh including elements from a predetermined set of first and second elements, the method comprising the steps of: decomposing the object into a mesh including a set of tetrahedra; identifying a group of first elements of the mesh as being suitable for merging into a second element from the predetermined set; merging the identified group of first elements into the second element from the predetermined set; displaying a representation of the physical attribute of the object based on the mesh representation of the object produced by the steps of decomposing, identifying, and merging; and representing the tetrahedra produced in the step of decomposing in the form of a graph which shows (i) nodes representing the tetrahedra, (ii) first node connectors representing faces shared in common between pairs of the tetrahedra, and (iii) second node connectors representing two faces, each face being of different tetrahedra which have an edge in common and have an angle therebetween which satisfies a predetermined condition.
Claim 3
Dependent Claim
98 words
A method as recited in claim 1, wherein: the elements of the predetermined set are represented as a set of respective subgraphs representing groups of tetrahedra which may be merged into respective ones of the elements of the predetermined set; the step of identifying includes finding a portion of the graph, the portion matching one of the respective subgraphs, and representing a group of the tetrahedra produced in the step of decomposing, which matches one of the respective subgraphs; and the step of merging includes merging the group of tetrahedra represented by the portion into the respective element.
Claim 4
Dependent Claim
99 words
A method as recited in claim 2, wherein: the elements of the predetermined set are represented as a set of respective search trees representing arrangements of the nodes of the respective subgraphs into (i) a root node corresponding with a first node of the subgraph representation of the element, and (ii) other nodes corresponding with other nodes of the subgraph and having node connectors which correspond with a first and second node connector of the respective subgraphs; and the step of identifying includes finding a portion of the graph, the portion matching one of the set of search trees.
Claim 5
Dependent Claim
123 words
A method as recited in claim 3, wherein the step of identifying includes: selecting an initial node of the graph as corresponding to a root node of the search tree; searching for a first group of other nodes of the graph which have connectors to at least one initial node and which have connectors to one other node of the first group, each connector corresponding with a connector between nodes of the search tree; and determining that the first group of nodes of the graph which, together, correspond with the nodes of the search tree and have corresponding connectors which correspond with a second group of elements of the mesh which are suitable for merging into one of the predetermined set of elements.
Claim 6
Dependent Claim
185 words
A finite element modeling and processing system for determining a physical attribute of an object using a mesh representation of the object, the mesh including elements from a predetermined set of elements, the system comprising: means for decomposing the object into a mesh including a set of tetrahedra; means for identifying a group of first elements of the mesh as being suitable for merging into an element from the predetermined set; means for merging the identified group of first elements into the element from the predetermined set; means for displaying a representation of the physical attribute of the object based on the mesh representation of the object produced by the means for decomposing, identifying, and merging; and means for representing the tetrahedra produced in the step of decomposing in the form of a graph which shows (i) nodes representing the tetrahedra, (ii) first node connectors representing faces shared in common between pairs of the tetrahedra, and (iii) second node connectors representing two faces, each face being of different tetrahedra which have an edge in common and have an angle therebetween which satisfies a predetermined condition.
Claim 7
Dependent Claim
185 words
A finite element modeling and processing system for determining a physical attribute of an object using a mesh representation of the object, the mesh including elements from a predetermined set of elements, the system comprising: means for decomposing the object into a mesh including a set of tetrahedra; means for identifying a group of first elements of the mesh as being suitable for merging into an element from the predetermined set; means for merging the identified group of first elements into the element from the predetermined set; means for displaying a representation of the physical attribute of the object based on the mesh representation of the object produced by the means for decomposing, identifying, and merging; and means for representing the tetrahedra produced in the step of decomposing in the form of a graph which shows (i) nodes representing the tetrahedra, (ii) first node connectors representing faces shared in common between pairs of the tetrahedra, and (iii) second node connectors representing two faces, each face being of different tetrahedra which have an edge in common and have an angle therebetween which satisfies a predetermined condition.
Claim 8
Dependent Claim
102 words
A system as recited in claim 5, wherein: the elements of the predetermined set are represented as a set of respective subgraphs representing groups of tetrahedra which may be merged into respective ones of the elements of the predetermined set; the means for identifying includes means for finding a portion of the graph, the portion matching one of the respective subgraphs, and representing a group of the tetrahedra produced in the step of decomposing which matches one of the respective subgraphs; and the means for merging includes means for merging the group of tetrahedra represented by the portion into the respective element.
Claim 9
Dependent Claim
101 words
A system as recited in claim 6, wherein: the elements of the predetermined set are represented as a set of respective search trees representing arrangements of the nodes of the respective subgraphs into (i) a root node corresponding with a first node of the subgraph representation of the element, and (ii) other nodes corresponding with other nodes of the subgraph and having node connectors which correspond with a first and second node connector of the respective subgraphs; and the means for identifying includes means for finding a portion of the graph, the portion matching one of the sets of search trees.
Claim 10
Dependent Claim
139 words
A system as recited in claim 7, wherein the means for identifying includes: means for selecting an initial node of the graph as corresponding to a root node of the search tree; means for searching for a first group of nodes of the graph which have connectors to at least one initial node and which have connectors to at least one other node of the group of nodes, each connector corresponding with a connector between nodes of the search tree; and means for determining that the group of nodes of the graph correspond with a group of elements of the mesh which are suitable for merging into one of the second elements of the predetermined set of elements, wherein the group of nodes of the graph, taken together, correspond with nodes of the search tree and have corresponding connectors.
Claim 11
Dependent Claim
248 words
A computer program product, for use with a finite element modeling and processing system for determining a physical attribute of an object using a mesh representation of the object, the mesh including elements from a predetermined set of first and second elements, the computer program product comprising: a computer-readable recording medium including a substrate; means, recorded on the medium, for directing the system to decompose the object into a mesh including a set of tetrahedra; means, recorded on the medium, for directing the system to identify a group of first elements of the mesh as being suitable for merging into a second element from the predetermined set; means, recorded on the medium, for directing the system to merge the identified group of first elements into the second element from the predetermined set; means, recorded on the medium, for directing the system to display a representation of the physical attribute of the object based on the mesh representation of the object produced by the means for directing to decompose, identify, and merge; and means, recorded on the medium, for directing the system to represent the tetrahedra produced in the step of decomposing in the form of a graph which shows (i) nodes representing the tetrahedra, (ii) first node connectors representing faces shared in common between pairs of the tetrahedra, and (iii) second node connectors representing two faces, each face being of different tetrahedra which have an edge in common and have an angle therebetween which satisfies a predetermined condition.
Claim 12
Dependent Claim
248 words
A computer program product, for use with a finite element modeling and processing system for determining a physical attribute of an object using a mesh representation of the object, the mesh including elements from a predetermined set of first and second elements, the computer program product comprising: a computer-readable recording medium including a substrate; means, recorded on the medium, for directing the system to decompose the object into a mesh including a set of tetrahedra; means, recorded on the medium, for directing the system to identify a group of first elements of the mesh as being suitable for merging into a second element from the predetermined set; means, recorded on the medium, for directing the system to merge the identified group of first elements into the second element from the predetermined set; means, recorded on the medium, for directing the system to display a representation of the physical attribute of the object based on the mesh representation of the object produced by the means for directing to decompose, identify, and merge; and means, recorded on the medium, for directing the system to represent the tetrahedra produced in the step of decomposing in the form of a graph which shows (i) nodes representing the tetrahedra, (ii) first node connectors representing faces shared in common between pairs of the tetrahedra, and (iii) second node connectors representing two faces, each face being of different tetrahedra which have an edge in common and have an angle therebetween which satisfies a predetermined condition.
Claim 13
Dependent Claim
124 words
A computer program product as recited in claim 9, wherein: the elements of the predetermined set are represented as a set of respective subgraphs representing groups of tetrahedra which may be merged into respective ones of the elements of the predetermined set; the means for directing to identify includes means, recorded on the medium, for directing the system to find a portion of the graph, the portion matching one of the respective subgraphs, and representing a group of the tetrahedra produced in the step of decomposing, which matches one of the respective subgraphs; and the means for directing to merge includes means, recorded on the medium, for directing the system to merge the group of tetrahedra represented by the portion into the respective element.
Claim 14
Dependent Claim
113 words
A computer program product as recited in claim 10, wherein: the elements of the predetermined set are represented as a set of respective search trees representing arrangements of the nodes of the respective subgraphs into (i) a root node corresponding with a first node of the subgraph representation of the element, and (ii) other nodes corresponding with other nodes of the subgraph and having node connectors which correspond with a first and second node connector of the respective subgraphs; and the means for directing to identify includes means, recorded on the medium, for directing the system to find a portion of the graph, the portion matching one of the set of search trees.
Claim 15
Dependent Claim
159 words
A computer program product as recited in claim 11, wherein the means for directing to identify includes: means, recorded on the medium, for directing the system to select an initial node of the graph as corresponding to a root node of the search tree; means for means, recorded on the medium, for directing the system to search for a first group of other nodes of the graph which have connectors to at least one initial node and which have connectors to one other node of the first group, each connector corresponding with a connector between nodes of the search tree; and means, recorded on the medium, for directing the system to determine that the first group of nodes of the graph which, together, correspond with the nodes of the search tree and have corresponding connectors which correspond with a second group of elements of the mesh which are suitable for merging into one of the predetermined set of elements.
References Cited (Backward Citations)
GB227146A
Cited
US3889107A
Cited
US4440532A
Cited
US4502257A
Cited
US4534813A
Cited
US4646251A
Cited
US4912644A
Cited
JPS63178372A
Cited
US4930092A
Cited
US4785399A
Cited
US5100358A
Cited
EP0339272A2
Cited
US4933889A
Cited
US4995813A
Cited
US5020002A
Cited
US5128872A
Cited
EP0405106A2
Cited
US5222202A
Cited
US5046988A
Cited
US5104125A
Cited
US5101444A
Cited
WO1992003196A1
Cited
US5125038A
Cited
US5497452A
Cited
US5315537A
Cited
US5345490A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-09-03 | 2000-03-04 | 2000-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-09-03 | 2004-03-04 | 2004-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-09-03 | 2008-03-04 | 2008-09-03 | $7700.00 | Window Closed / Lapsed |