US5553009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel method for subdivision of arbitrary curved solids
Assignee: International Business Machines Corp
•
Filing: 1995-11-01
•
Granted: 1996-09-03
•
Expires: 2015-11-01
Abstract
Abstract A method and system are provided for subdividing an arbitrarily shaped object into a collection of geometric elements ("cells") having predefined, simple topologies which facilitate further subdivision into tetrahedra, and which are well suited for further applications, such as finite element calculations. Initially, a representation of the object includes one or more regions, at least one of the regions not meeting the definition of "cell", each region having vertices, edges, and faces. An edge is selected according to a priority scheme, and slices which run through the edge and which also either run through other edges or vertices of the representation, are coplanar with other faces of the representation, or have other predetermined attributes, are considered for use in subdividing the representation. A score, which was initially calculated for the representation, is recalculated for hypothetical subdivisions of the representation incorporating each respective one of such slices. The scores are related to predetermined factors, such as the number of regions which are cells, relative to the total number of regions, the number of faces whose topologies correspond with the topologies of faces of cells, relative to the total number of faces, and factors relating to the shapes of the regions and faces. For one of the slices, the score is maximized. The representation is then subdivided, using that slice. This process is repeated until no regions of the representation remain which do not meet the definition of a cell. The method or the invention is preferably practiced using parallel processing at one or more levels. That is, either (i) different regions of the object are subdivided in parallel, (ii) for a given region, interesting slices are scored for different high-priority edges in parallel, (iii) for a given high-priority edge or a given region, interesting slices through that edge are scored in parallel, or a suitable combination thereof.
Inventors
- 👤 Siavash N. Meshkat
- 👤 Susan A. Meshkat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 05:14
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 57
Claim 1
Independent Claim
94 words
A method of operating a data processing system to simulate subdivision of an object into regions to facilitate computer analysis of the object, the method comprising the steps of: receiving as an input a digital representation of the object; identifying a plurality of slices that subdivide the object into regions; calculating a score for each of the plurality of slices; choosing one of the plurality of slices based on the scores calculated by the step of calculating; subdividing the object with the chosen slice; and providing a digital output representative of the subdivided object.
Claim 2
Independent Claim
94 words
A method of operating a data processing system to simulate subdivision of an object into regions to facilitate computer analysis of the object, the method comprising the steps of: receiving as an input a digital representation of the object; identifying a plurality of slices that subdivide the object into regions; calculating a score for each of the plurality of slices; choosing one of the plurality of slices based on the scores calculated by the step of calculating; subdividing the object with the chosen slice; and providing a digital output representative of the subdivided object.
Claim 3
Dependent Claim
38 words
A method as recited in claim 1, wherein the step of calculating includes one of (i) calculating the scores in series, by a single processor, and (ii) calculating the scores in parallel, by a plurality of parallel processors.
Claim 4
Dependent Claim
48 words
A method as recited in claim 1, wherein: the object includes a plurality of regions, and the steps of calculating and choosing are performed for each of the regions one of (i) in parallel, by a plurality of parallel processors, and (ii) in series, by a single processor.
Claim 5
Dependent Claim
37 words
A method as recited in claim 1, further comprising the step of selecting the plurality of slices, for which the scores are to be calculated by the step of calculating, in terms of features of the object.
Claim 6
Dependent Claim
89 words
A method as recited in claim 4, wherein: the digital representation of the object represents the object in terms of faces, edges between adjacent ones of the faces, and vertices between adjacent ones of the edges, the faces and edges being algebraic surfaces and algebraic curves, respectively, and the step of selecting operates to select the plurality of slices based on the faces, edges, and vertices of the object, each one of the plurality of selected slices being one of (i) a plane, and (ii) an algebraic curved surface.
Claim 7
Dependent Claim
34 words
A method as recited in claim 5, wherein the step of selecting includes: selecting one of the edges; and selecting the plurality of slices as slices which include the selected one of the edges.
Claim 8
Dependent Claim
44 words
A method as recited in claim 6, wherein the step of selecting one of the edges is executed a plurality of times for the edges, one of (i) in series, by a single processor, and (ii) in parallel, by a plurality of parallel processors.
Claim 9
Dependent Claim
119 words
A method as recited in claim 6, wherein the step of selecting an edge includes selecting the edge based on at least one of the criteria: (a) whether the two adjacent faces, between which is the selected edge, have an interior angle which falls within a predetermined range of values. (b) whether at least one of the two adjacent faces, between which is the selected edge, has a curvature measurable in terms of a predetermined parameter whose value falls within a predetermined range of values, and (c) whether the length of the selected edge, relative to one of (i) other edges of the object and (ii) the overall size of the object, falls within a predetermined range of values.
Claim 10
Dependent Claim
204 words
A method as recited in claim 6, wherein the step of selecting the plurality of slices includes selecting slices which satisfy at least one of the following criteria: (a) the slice is an extension of one of the two adjacent faces, between which is the selected one of the edges, (b) the slice includes a second one of the edges of the object, the second edge being visible from the selected edge, (c) the slice is normal to one of (i) one of the two adjacent faces, between which is the selected edge, the one adjacent face being visible from the selected edge, and (ii) another face of the object, the other face being visible from the selected edge, (d) the slice is normal to another edge of the object, the other edge being visible from the selected edge, and (e) the slice includes a vertex of the object other than vertices of the selected one of the edges, the included vertex being visible from the selected edge; an edge, face, or vertex being visible from the selected edge if any line segment connecting a point of the selected edge with a point of the edge, face, or vertex is entirely within the region.
Claim 11
Dependent Claim
59 words
A method as recited in claim 1, further comprising the steps of: determining whether the object includes any regions which do not conform to a predetermined criterion, and iteratively executing the steps of calculating, choosing, and determining, until it is determined in the step of determining that all of the regions of the object conform to the predetermined criterion.
Claim 12
Dependent Claim
33 words
A method as recited in claim 10, wherein the step of determining includes determining whether the regions of the object conform to the criterion of falling within a predetermined set of geometric elements.
Claim 13
Dependent Claim
21 words
A method as recited in claim 11, wherein, in the step of determining, the predetermined set includes tetrahedra, pentahedra, and hexahedra.
Claim 14
Dependent Claim
70 words
A method as recited in claim 1, wherein: the method further comprises the step of calculating an initial score for the object without any of the plurality of slices; and the step of choosing includes selecting the one of the plurality of slices based on which of the scores maximizes a ratio of the score with the slice to the score without any slices produced in the step of calculating.
Claim 15
Dependent Claim
59 words
A method as recited in claim 13, further comprising the steps of: determining whether the object includes any regions which do not conform to a predetermined criterion, and iteratively executing the steps of calculating, choosing, and determining, until it is determined in the step of determining that all of the regions of the object conform to the predetermined criterion.
Claim 16
Dependent Claim
33 words
A method as recited in claim 14, wherein the step of determining includes determining whether the regions of the object conform to the criterion of falling within a predetermined set of geometric elements.
Claim 17
Dependent Claim
21 words
A method as recited in claim 15, wherein, in the step of determining, the predetermined set includes tetrahedra, pentahedra, and hexahedra.
Claim 18
Dependent Claim
112 words
A method as recited in claim 16, wherein the step of calculating a score for a slice includes calculating according to the formula ##EQU4## where s is the score, C is the number of regions of the object which meet the definition of cell, R is the total number of regions of the object, Q is the number of quadrilateral faces of the regions of the object, F is the total number of faces of the object, σ f is an average of shape coefficients σ f (f) for the faces of the object, and σ r is an average of shape coefficients σ r (r) for the regions of the object.
Claim 19
Dependent Claim
63 words
A method as recited in claim 17, wherein, in the step of calculating, the shape σ f (f) of a face f of the object, having area A and perimeter p, is given by the formula ##EQU5## and the shape σ r (r) of a region r of the object, having surface area A and volume V, is given by the formula ##EQU6##
Claim 20
Dependent Claim
137 words
A digital data processing system for simulating subdivision of an object to facilitate computer analysis of the object, the system comprising: a memory; at least one processor; and program instruction code means, for execution by the at least one processor, for directing the digital data processing system to perform method steps for subdividing an object into regions, the program code means comprising: means for receiving, as an input, a distal representation of a physical object; means for identifying a plurality of slices that subdivide the object into regions; means for calculating a score for each of the plurality of slices; means for choosing one of the plurality of slices based on the calculated scores for slices; means for subdividing the object with the. chosen slice; and means for providing a digital output representative of the subdivided object.
Claim 21
Dependent Claim
137 words
A digital data processing system for simulating subdivision of an object to facilitate computer analysis of the object, the system comprising: a memory; at least one processor; and program instruction code means, for execution by the at least one processor, for directing the digital data processing system to perform method steps for subdividing an object into regions, the program code means comprising: means for receiving, as an input, a distal representation of a physical object; means for identifying a plurality of slices that subdivide the object into regions; means for calculating a score for each of the plurality of slices; means for choosing one of the plurality of slices based on the calculated scores for slices; means for subdividing the object with the. chosen slice; and means for providing a digital output representative of the subdivided object.
Claim 22
Dependent Claim
37 words
A system as recited in claim 19, wherein the means for calculating includes one of (i) a single processing means for calculating the scores in series, and (ii parallel processing means for calculating the scores in parallel.
Claim 23
Dependent Claim
57 words
A system as recited in claim 19, wherein: the object includes a plurality of regions, and the means for calculating and choosing include one of (i) parallel processing means for calculating and choosing for each of the regions in parallel, and (ii) a single processing means for calculating and choosing for each of the regions in series.
Claim 24
Dependent Claim
36 words
A system as recited in claim 19, further comprising means for selecting the plurality of slices, for which the scores are to be calculated by the means for calculating, in terms of features of the object.
Claim 25
Dependent Claim
85 words
A system as recited in claim 22, wherein: the object is represented in terms of faces, edges between adjacent ones of the faces, and vertices between adjacent ones of the edges, the faces and edges being algebraic surfaces and algebraic curves, respectively, and the means for selecting includes means for selecting the plurality of slices based on the faces, edges, and vertices of the object, each one of the plurality of selected slices being one of (i) a plane, and (ii) a curved algebraic surface.
Claim 26
Dependent Claim
38 words
A system as recited in claim 23, wherein the means for selecting includes: means for selecting one of the edges; and means for selecting the plurality of slices as slices which include the selected one of the edges.
Claim 27
Dependent Claim
42 words
A system as recited in claim 24, wherein the means for selecting one of the edges includes one of (i) a plurality of parallel processors for selecting the edges in parallel, and (ii) a single processor for selecting the edges in series.
Claim 28
Dependent Claim
121 words
A system as recited in claim 24, wherein the means for selecting an edge includes means for selecting the edge based on at east one of the criteria: (a) whether the two adjacent faces, between which is the selected edge, have an interior angle which falls within a predetermined range of values, (b) whether at least one of the two adjacent faces, between which is the selected edge, has a curvature measurable in terms of a predetermined parameter whose values falls within a predetermined range of values, and (c) whether the length of the selected edge, relative to one of (i) other edges of the object and (ii) the overall size of the object, falls within a predetermined range of values.
Claim 29
Dependent Claim
204 words
A system as recited in claim 24, wherein the means for selecting the plurality of slices includes means for selecting slices which satisfy at least one of the following criteria: (a) the slice is an extension of one of the two adjacent faces, between which is selected one of the edges, (b) the slice includes another one of the edges of the object, the other edge being visible from the selected edge, (c) the slice is normal to one of (i) one of the two adjacent faces, between which is the selected edge, the one adjacent face being visible from the selected edge, and (ii) another face of the object, the other face being visible from the selected edge, (d) the slice is normal to another edge of the object, the other edge being visible form the selected edge, and (e) the slice includes a vertex of the object other than vertices of the selected one of the edges, the included vertex being visible from the selected edge; an edge, face, or vertex being visible from the selected edge if any line segment connecting a point of the selected edge with a point of the edge, face, or vertex is entirely within the region.
Claim 30
Dependent Claim
60 words
A system as recited in claim 19, further comprising: means for determining whether the object includes any regions which do not conform to a predetermined criterion, and means for iteratively operating the means for calculating, choosing, and determining, until it is determined by the means for determining that all of the regions of the object conform to the predetermined criterion.
Claim 31
Dependent Claim
35 words
A system as recited in claim 28, wherein the means for determining includes means for determining whether the regions of the object conform to the criterion of falling within a predetermined set of geometric elements.
Claim 32
Dependent Claim
21 words
A system as recited in claim 29, wherein in the means for determining, the predetermined set includes tetrahedra, pentahedra, and hexahedra.
Claim 33
Dependent Claim
71 words
A system as recited in claim 19 wherein: the system further comprises means for calculating an initial score for the object without any of the plurality of slices; and the means for choosing includes means for selecting the one of the plurality of slices based on which of the scores maximizes a ratio of the score with the slice to the score without any slices produced by the means for calculating.
Claim 34
Dependent Claim
60 words
A system as recited in claim 31, further comprising; means for determining whether the object includes any regions which do not conform to a predetermined criterion, and means for iteratively operating the means for calculating, choosing, and determining, until it is determined by the means for determining that all of the regions of the object conform to the predetermined criterion.
Claim 35
Dependent Claim
35 words
A system as recited in claim 32, wherein the means for determining includes means for determining whether the regions of the object conform to the criterion of falling within a predetermined set of geometric elements.
Claim 36
Dependent Claim
21 words
A system as recited in claim 33, wherein, in the means for determining, the predetermined set includes tetrahedra, pentahedra, and hexahedra.
Claim 37
Dependent Claim
114 words
A system as recited in claim 34, wherein the means for calculating a score for a slice includes means for calculating according to the formula ##EQU7## where s is the score, C is the number of regions of the object which meet the definition of cell, R is the total number of regions of the object, Q is the number of quadrilateral faces of the regions of the object, F is the total number of faces of the object, σ f is an average of shape coefficients σ f (f) for the faces of the object, and σ r is an average of shape coefficients σ f (r) for the regions of the object.
Claim 38
Dependent Claim
63 words
A system as recited in claim 35, wherein, in the means for calculating, the shape σ f (f) of a face f of the object, having area A and perimeter p, is given by the formula ##EQU8## and the shape σ f (r) of a region r of the object, having surface area A and volume V, is given by the formula ##EQU9##
Claim 39
Dependent Claim
99 words
A machine-readable digital data storage device tangibly embodying a program of instruction executable by a processing system for performing method steps to subdivide an object into regions to facilitate computer analysis of the object, the method steps comprising: receiving, as an input, a digital representation of a physical object; identifying a plurality of slices that subdivide the object into regions; calculating a score for each of the plurality of slices; choosing one of the plurality of slices based on the scores calculated; subdividing the object with a chosen slice; and providing a digital output representative of the subdivided object.
Claim 40
Dependent Claim
99 words
A machine-readable digital data storage device tangibly embodying a program of instruction executable by a processing system for performing method steps to subdivide an object into regions to facilitate computer analysis of the object, the method steps comprising: receiving, as an input, a digital representation of a physical object; identifying a plurality of slices that subdivide the object into regions; calculating a score for each of the plurality of slices; choosing one of the plurality of slices based on the scores calculated; subdividing the object with a chosen slice; and providing a digital output representative of the subdivided object.
Claim 41
Dependent Claim
23 words
A storage device as recited in claim 37, wherein the step of calculating is performed in parallel on a plurality of parallel processors.
Claim 42
Dependent Claim
31 words
A storage device as recited in claim 37, wherein: the object includes a plurality of regions, and the step of calculating is performed in parallel on a plurality of parallel processors.
Claim 43
Dependent Claim
35 words
A storage device as recited in claim 37, the method steps further comprising steps of selecting the plurality of slices, for which the scores are to be calculated in terms of features for the object.
Claim 44
Dependent Claim
80 words
A storage device as recited in claim 40, wherein: the object is represented in terms of faces, edges between adjacent ones of the faces, and vertices between adjacent ones of the edges, the faces and edges being algebraic surfaces and algebraic curves, respectively, and the plurality of slices are selected based on the faces, edges, and vertices of the object, each one of the plurality of selected slices being one of (i) a plane, and (ii) an algebraic curved surface.
Claim 45
Dependent Claim
37 words
A storage device as recited in claim 41 wherein the selecting step includes the steps of: selecting one of the edges; and selecting the plurality of slices as slices which include the selected one of the edges.
Claim 46
Dependent Claim
51 words
A storage device as recited in claim 42, wherein the step of selecting one of the edges includes one of the following steps of (i) selecting the edges in parallel by means of a plurality of parallel processors, and (ii) selecting the edges in series by means of a single processor.
Claim 47
Dependent Claim
125 words
A storage device as recited in claim 42, wherein the step of selecting one of the edges includes the steps of selecting an edge based on at least one of the criteria: (a) whether the two adjacent faces, between which is the selected edge, have an interior angle which falls within a predetermined range of values, (b) whether at least one of the two adjacent faces, between which is the selected edge, has a curvature measurable in terms of a predetermined parameter whose value falls within a predetermined range of values, and (c) whether the length of the selected edge, relative to one of (i) other edges of the object and (ii) the overall size of the object, falls within a predetermined range of values.
Claim 48
Dependent Claim
207 words
A storage device as recited in claim 42, wherein the step of selecting the plurality of slices includes the steps of selecting slices which satisfy at least one of the following criteria: (a) the slice is an extension of one of the two adjacent faces, between which is the selected one of the edges, (b) the slice includes another one of the edges of the object, the other edge being visible from the selected edge, (c) the slice is normal to one of (i) one of the two adjacent faces, between which is the selected edge, the one adjacent face being visible from the selected edge, and (ii) another face of the object, the other face being visible from the selected edge, (d) the slice is normal to another edge of the object, the other edge being visible from the selected edge, and (c) the slice includes a vertex of the object other than vertices of the selected once of the edges, the included vertex being visible from the selected edge, and edge, face, or vertex being visible from the selected edge if any line segment connecting a point of the selected edge with a point of the edge, face, or vertex is entirely within the region.
Claim 49
Dependent Claim
54 words
A storage device as recited in claim 37, the method steps further comprising: determining whether the object includes any regions which do not conform to a predetermined criterion, and iteratively performing the calculating, choosing, and determining steps until it is determined that all of the regions of the object conform to the predetermined criterion.
Claim 50
Dependent Claim
36 words
A storage device as recited in claim 46, wherein the determining step includes the steps of determining whether the regions of the object conform to the criterion of falling within a predetermined set of geometric elements.
Claim 51
Dependent Claim
17 words
A storage device as recited in claim 47, wherein the predetermined set includes tetrahedra, pentahedra, and hexahedra.
Claim 52
Dependent Claim
76 words
A storage device as recited in claim 37, wherein: p1 the method steps further comprise the steps of calculating an initial score for the object without any of the plurality of slices; and the choosing step includes a step of selecting one of the plurality of slices based on which of the scores maximizes a ratio of the score with the slice to the score without any slices produced by the means for directing to calculate.
Claim 53
Dependent Claim
59 words
A storage device as recited in claim 49, the method steps further comprising the steps of: determining whether the object includes any regions which do not conform to a predetermined criterion, and wherein the iteratively performing the calculating, choosing, and determining steps until it is determined that all of the regions of the object conform to the predetermined criterion.
Claim 54
Dependent Claim
36 words
A storage device as recited in claim 50, wherein the determining step includes the steps of determining whether the regions of the object conform to the criterion of falling within a predetermined set of geometric elements.
Claim 55
Dependent Claim
17 words
A storage device as recited in claim 51, wherein the predetermined set includes tetrahedra, pentahedra, and hexahedra.
Claim 56
Dependent Claim
112 words
A storage device as recited in claim 52, wherein the step of calculating an initial score is performed according to the formula ##EQU10## where s is the score, C is the number of regions of the object which meet the definition of cell, R is the total number of regions of the object, Q is the number of quadrilateral faces of the regions of the object, F is the total number of faces of the object, σ f is an average of shape coefficients σ f (f) for the faces of the object, and σ r , is an average of shape coefficients σ f (r) for the regions of the object.
Claim 57
Dependent Claim
59 words
A storage device as recited in claim 53, wherein the shape σ f (f) of a face f of the object, having area A and perimeter p, is given by the formula ##EQU11## and the shape σ f (r) of a region r or the object, having surface area A and volume V, is given by the formula ##EQU12##
References Cited (Backward Citations)
US3889107A
Cited
US4649498A
Cited
US4797842A
Cited
US4775946A
Cited
US4742473A
Cited
US4750818A
Cited
US5003498A
Cited
US4893260A
Cited
US4941114A
Cited
US5010501A
Cited
US4912664A
Cited
US4933889A
Cited
US5088054A
Cited
US5113490A
Cited
US5125038A
Cited
US5214752A
Cited
US5315537A
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 |