US4890242A — Solid-modeling system using topology directed sub…

Claim 1

Independent Claim 698 words

A recursive subdivision process performed in a solid-modeling system including computer means for performing a plurality of functions and storage means for storing data, said process for operating said computer means to identify intersections between the surfaces of a pair of solid models A and B represented by digital data surface descriptions stored in said storage means, said digital data surface descriptions produced by computer-aided design, said models representing, for example, articles of manufacture, machine parts or the path described by the movement thereof through space, each said surface description of each said model subdivided into a plurality of surface patches S each represented by a corresponding digital data surface path description stored in a first pool of surface patch description pairs in said storage means, each said pair including one surface patch description from each of said models A and B, said process for determining by recursive subdivision which said surface patch description pairs in said first pool have a transversal intersection to produce a second pool of surface patch description pairs each known to have a transversal intersection, said process further determining when each of a said pair of surface patch descriptions in said first pool have been subdivided to a limit specified by a predetermined criterion to produce a third pool of surface patch description pairs wherein both surface patch descriptions of said pair are known to meet said predetermined criterion, said process comprising causing said computer means to perform the steps of: (1) reading said storage means to retrieve from said first pool a pair of digital data patch descriptions representing, respectively a pair of surface patches S A and S B of said models A and B; (2) operating on said retrieved patch descriptions to perform a mutual point exclusion test for said surface patches S A and S B and if no mutual points exist terminating further intersection identifying processing on said pair and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing; (3) operating on said retrieved patch descriptions to determine if said pair of surface patches S A and S B are transversal and if transversal terminating further subdivision of said pair and going to step 6; (4) operating on said retrieved patch descriptions to test each of said surface patches S A and S B against a predetermined criterion and if said criterion is met for both said surface patches classifying said pair in said third pool as having met said criterion whereby the intersection set of said pair can be approximated and terminating further subdivision on said surface patches S A and S B and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing; (5) operating on said retrieved patch descriptions to subdivide one or both of said surface patches S A and S B if they do not meet said predetermined criterion, said patch or patches subdivided into a further plurality of patches to create a plurality of new surface patch pairs representing new patch descriptions, and storing the digital data patch descriptions representing said new pairs in said first pool in said storage means for further processing and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing; and (6) operating on said retrieved patch descriptions for said pair of surface patches S A and S B determined to be transversal to perform a test to detect intersection between said pair and if an intersection of said pair is detected classifying said pair of surface patches S A and S B in said second pool as having a transversal intersection whereby it is known that said pair intersect in a curve if they intersect so that the intersection set can be determined without further subdivision, and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing.

Claim 2

Dependent Claim 698 words

A recursive subdivision process performed in a solid-modeling system including computer means for performing a plurality of functions and storage means for storing data, said process for operating said computer means to identify intersections between the surfaces of a pair of solid models A and B represented by digital data surface descriptions stored in said storage means, said digital data surface descriptions produced by computer-aided design, said models representing, for example, articles of manufacture, machine parts or the path described by the movement thereof through space, each said surface description of each said model subdivided into a plurality of surface patches S each represented by a corresponding digital data surface path description stored in a first pool of surface patch description pairs in said storage means, each said pair including one surface patch description from each of said models A and B, said process for determining by recursive subdivision which said surface patch description pairs in said first pool have a transversal intersection to produce a second pool of surface patch description pairs each known to have a transversal intersection, said process further determining when each of a said pair of surface patch descriptions in said first pool have been subdivided to a limit specified by a predetermined criterion to produce a third pool of surface patch description pairs wherein both surface patch descriptions of said pair are known to meet said predetermined criterion, said process comprising causing said computer means to perform the steps of: (1) reading said storage means to retrieve from said first pool a pair of digital data patch descriptions representing, respectively a pair of surface patches S A and S B of said models A and B; (2) operating on said retrieved patch descriptions to perform a mutual point exclusion test for said surface patches S A and S B and if no mutual points exist terminating further intersection identifying processing on said pair and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing; (3) operating on said retrieved patch descriptions to determine if said pair of surface patches S A and S B are transversal and if transversal terminating further subdivision of said pair and going to step 6; (4) operating on said retrieved patch descriptions to test each of said surface patches S A and S B against a predetermined criterion and if said criterion is met for both said surface patches classifying said pair in said third pool as having met said criterion whereby the intersection set of said pair can be approximated and terminating further subdivision on said surface patches S A and S B and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing; (5) operating on said retrieved patch descriptions to subdivide one or both of said surface patches S A and S B if they do not meet said predetermined criterion, said patch or patches subdivided into a further plurality of patches to create a plurality of new surface patch pairs representing new patch descriptions, and storing the digital data patch descriptions representing said new pairs in said first pool in said storage means for further processing and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing; and (6) operating on said retrieved patch descriptions for said pair of surface patches S A and S B determined to be transversal to perform a test to detect intersection between said pair and if an intersection of said pair is detected classifying said pair of surface patches S A and S B in said second pool as having a transversal intersection whereby it is known that said pair intersect in a curve if they intersect so that the intersection set can be determined without further subdivision, and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches S A and S B for processing.

Claim 3

Dependent Claim 17 words

A process according to claim 1 wherein said test performed in step 6 is a boundary test.

Claim 4

Dependent Claim 46 words

A process according to claim 2 further including the step of operating on said retrieved data for said pair of surface patches S A and S B determined to have a transversal intersection to compute a representation of the intersection of the intersection of said pair.

Claim 5

Dependent Claim 43 words

A process according to claim 1 further including the step of operating on said retrieved data for said pair of surface patches S A and S B determined to have a transversal intersection to compute a representation of the intersection of said pair.

Claim 6

Dependent Claim 19 words

A process according to claim 1 wherein said predetermined criterion of said step (4) is a patch flatness criterion.

Claim 7

Dependent Claim 66 words

A process according to claim 1 including the step of operating on said data for said pair of surface patches S A and S B which meet said predetermined criterion to approximate the surface patches S A and S B to a geometry for which the intersection set can be computed and computing a representation of said intersection set and storing it in said storage means.

Claim 8

Dependent Claim 32 words

A process according to claim 1, 2, 4, 3, 5 or 6 wherein said surface patches S A and S B are represented by said data in the form of boundary representations.

Claim 9

Dependent Claim 32 words

A process according to claim 1, 2, 4, 3, 5 or 6 wherein said surface patches S A and S B are represented by said data in the form of faceted representations.

Claim 10

Dependent Claim 52 words

A process according to claim 1, 2, 4, 3, 5 or 6 wherein said surface patches S A and S B are represented by said data so that it is possible to extract information about said surface patches whose disjoint union comprises the bounding surfaces of the respective objects A and B.

Claim 11

Dependent Claim 93 words

A process according to claim 1 wherein said pair of surface patches S A and S B are determined not to be transversal if W A ∩W B =.0. wherein S A and S B are two smooth surfaces in R 3 , and W A , W B are subsets of unit spherical surface S 2 around the origin S 2 containing points x A and x B such that ##EQU18## wherein δ A and δ B are bounds on the sets of normals N(S A ) and N(S B ), respectively.

Claim 12

Dependent Claim 40 words

A process according to claim 10 wherein said W A ∩W B =.0. is determined to be true if D(x A , x B )>δ A +δ B wherein x A εN(S A ) and x B εN(S B ).

Claim 13

Dependent Claim 83 words

A process according to claim 11 wherein said bounds δ A and δ B on N(S A ) and N(S B ) for said surface patches S A and S B are computable so that an x A εN(S A ) and a δ A are computable such that D(x A , x)≦δ A , xδN(S A ) and an x B δN(S B ) and a δ B are compatible such that D(x B , x)≦δ B , x εN(S B ).

Claim 14

Dependent Claim 169 words

A process according to claim 12 wherein said step (3) of determining whether said pair of surface patches S A and S B are transversal includes causing said computer means to operate on said retrieved data to perform the steps of: (a) computing x A and x B for each of said surface patches S A and S B , respectively, wherein x A and x B are elements of the respective sets of normals N(S A ) and N(S B ) to said patches S A and S B ; (b) computing D(x A ,x B )=√1-(x A ,x B ) (c) computing δ A and δ B for each of said surface patches S A and S B respectively wherein δ A and δ B are bounds on the sets of normals N(S A ) and N(S B ), respectively; and (d) determining if D(x A ,x B )>δ A +δ B which if true indicates that said surface patches S A and S B are transversal.

Claim 15

Dependent Claim 44 words

A process according to claim 13 wherein said surface patches S A and S B are defined parametrically by said retrieved data such that: S=f(0,φ)=(x(θ,φ), y(θ,φ), z(θ,φ)), (θ, φ)εD where x, y, z are evaluated functions and D is the domain of said patch.

Claim 16

Dependent Claim 101 words

A process according to claim 14 said bounds on the set of normals over said patches S A and S B are each defined as a real number ε such that ε≧D(N x (S), N x (S)) xεS wherein x=f(θ,φ) in S, and further wherein each said bound is the one for which ε=max x εS D(N x (S), N x (S))≦√1-<w,n.sub.θ ×n.sub.φ > 2 wherein w is a vector denoting the maximum variation of N x (S) over S from N x (S) and x=f(θ,φ),n.sub.θ =f.sub.θ (θ,φ), n.sub.θ =f.sub.φ (θ,φ), and <,> denotes inner products, and x deniotes cross product.

Claim 17

Dependent Claim 31 words

A process according to claim 15 wherein w is computed by computing ε.sub.θ and ε.sub.φ and then solving the systems ##EQU19## for the one w which minimizes <w, n.sub.θ ×n.sub.φ >.

Claim 18

Dependent Claim 40 words

A process according to claim 16 wherein ε.sub.θ and ε.sub.φ are equal to ε.sub.θ =max.sub.(θ,φ)εD) D(f.sub.θ (θ,φ),f.sub.θ (θ,φ))=(ε(f.sub.θ))/|f.sub.θ | and ε.sub.φ =max.sub.(θ,φ)εD D(f.sub.φ (θ,φ),f.sub.φ (θ,φ))=(ε(f.sub.φ))/|f.sub.φ |. wherein D is domain of the parametric patches S A and S B .

Claim 19

Dependent Claim 74 words

A process according to claim 17 wherein ε.sub.θ and ε.sub.φ are computed using Taylor series expansion and interval arithmetic wherein ##EQU20## wherein ∥θ-θ∥ and ∥φ-φ∥ are known for one of said patches S A and S B from their respective domains D while ##EQU21## are computed using interval arithmetic on the symbolic expression for x.sub.θθ derivable from f(θ,φ), and further wherein ε(y.sub.θ), ε(z.sub.θ), ε(x.sub.φ), ε(y.sub.φ), ε(z.sub.φ) are computed in a similar manner to ε(x.sub.θ).

Claim 20

Dependent Claim 99 words

A method according to claim 1 further wherein if {S i } is a sequence of surface patches S A or S B , such that S j is a subpatch of S j-1 and diameter (S i )→0 as i→∞, and such that δ i is the sequence of computed bounds on N(S) such that D(x i , x)≦δ i , xεN(S i ) for some sequence of points {x i } in S 2 , then lim i →∞ δ i =0 so that said subdivision process can converge to arbitrarily fine approximations of the integration sets.

Claim 21

Dependent Claim 329 words

In a subdivision process performed in a solid-modeling system including storage means for storing data to identify an intersection between a pair of surface patches S A and S B each representing, respectively, a portion of the surface of a pair of solid-models A and B represented by digital data surface descriptions stored in said storage means, said digital data surface descriptions produced by computer-aided design, said models representing, for example, articles of manufacture, machine parts or the path described by the movement thereof through space, said surface patches S A and S B each repreented by a corresponding digital data surface patch description stored in a first pool of surface patch description pairs in said storage means, each said pair including one surface patch description from each of said models, wherein said process operates on said patch descriptions to subdivide said pair of surface patches in said first pool unless mutual point exclusion is proved or unless each surface of said pair meets a predetermined criterion permitting the intersection set of said pair to be determined from approximations of the geometry of each of said surface patches, the improvement comprising: operating on said digital data surface patch descriptions representing said pair for those said pair of surface patches S A and S B for which mutual point exclusion is not proved to determine if said pair of surface patches are transversal, whereby it is known that said pair intersects in a curve if intersecting, and if transversal terminating further subdivision of said pair and operating further on said retrieved patch descriptions to perform a test to detect intersection between said pair and if an intersection is detected classifying said pair as having a transversal intersection to produce a second pool of surface patch description pairs each known to have a transversal intersection whereby a description of the intersection of said pairs in said second pool can be determined by exploiting the known curve intersection geometry of said pair.

Claim 22

Dependent Claim 329 words

In a subdivision process performed in a solid-modeling system including storage means for storing data to identify an intersection between a pair of surface patches S A and S B each representing, respectively, a portion of the surface of a pair of solid-models A and B represented by digital data surface descriptions stored in said storage means, said digital data surface descriptions produced by computer-aided design, said models representing, for example, articles of manufacture, machine parts or the path described by the movement thereof through space, said surface patches S A and S B each repreented by a corresponding digital data surface patch description stored in a first pool of surface patch description pairs in said storage means, each said pair including one surface patch description from each of said models, wherein said process operates on said patch descriptions to subdivide said pair of surface patches in said first pool unless mutual point exclusion is proved or unless each surface of said pair meets a predetermined criterion permitting the intersection set of said pair to be determined from approximations of the geometry of each of said surface patches, the improvement comprising: operating on said digital data surface patch descriptions representing said pair for those said pair of surface patches S A and S B for which mutual point exclusion is not proved to determine if said pair of surface patches are transversal, whereby it is known that said pair intersects in a curve if intersecting, and if transversal terminating further subdivision of said pair and operating further on said retrieved patch descriptions to perform a test to detect intersection between said pair and if an intersection is detected classifying said pair as having a transversal intersection to produce a second pool of surface patch description pairs each known to have a transversal intersection whereby a description of the intersection of said pairs in said second pool can be determined by exploiting the known curve intersection geometry of said pair.

Claim 23

Dependent Claim 16 words

A process according to claim 20 wherein said test to detect intersection is a boundary test.

Claim 24

Dependent Claim 42 words

A process according to claim 21 including the step of operating on said retrieved data for said pair of surface patches S A and S B determined to have a transversal intersection to compute a representation of the intersection of said pair.

Claim 25

Dependent Claim 43 words

A process according to claim 20 further including the step of operating on said retrieved data for said pair of surface patches S A and S B determined to have a transversal intersection to compute a representation of the intersection of said pair.

Claim 26

Dependent Claim 15 words

A process according to claim 20 wherein said predetermined criterion is a patch flatness criterion.

Claim 27

Dependent Claim 65 words

A process according to claim 20 including the step of operating on said data for said pair of surface patches S A and S B which meet said predetermined criterion to approximate the surface patches S A and S B to geometry for which the intersection set can be computed and computing a representation of said intersection set and storing it in said storage means.

Claim 28

Dependent Claim 32 words

A process according to claims 20, 21, 23, 22, 24 or 18 wherein said surface patches S A and S B are represented by said data in the form of boundary representations.

Claim 29

Dependent Claim 32 words

A process according to claim 20, 21, 25, 22, 24 or 25 wherein said surface patches S A and S B are represented by said data in the form of faceted representations.

Claim 30

Dependent Claim 52 words

A process according to claim 20, 21, 25, 22, 24 or 25 wherein said surface patches S A and S B are represented by said data so that it is possible to extract information about said surface patches whose disjoint union comprises the bounding surfaces of the respective objects A and B.

Claim 31

Dependent Claim 94 words

A process according to claim 20 wherein in said pair of surface patches S A and S B are determined not to be transversal if W A ∩W B =.0. wherein S A and S B are two smooth surfaces in R 3 , and W A , W B are subsets of unit spherical surface S 2 around the origin S 2 containing points x A and x B such that ##EQU22## wherein ε A and ε B are bounds on the sets of normals N(S A ) and N(S B ), respectively.

Claim 32

Dependent Claim 39 words

A process according to claim 29 wherein said W A ∩W B =.0. is determined to be true if D(x A ,x B )>ε A +ε B wherein x A εN(S A ) and x B εN(S B ).

Claim 33

Dependent Claim 81 words

A process according to claim 30 wherein said bounds ε A and ε B on N(S A ) and N(S B ) for said surface patches S A and S B are computable so that an x A εN(S A ) and a ε A are computable such that D(x A ,x)≦ε A , xεN(S A ) and an x B εN(S B ) and a ε B are computable such that D(x B , x)≦ε B , xεN(S B ).

Claim 34

Dependent Claim 161 words

A process according to claim 31 wherein in determining whether said pair of surface patches S A and S B are transversal includes operating on said retrieved data to perform the steps of: (a) computing x A and x B for each of said surface patches S A and S B , respectively, wherein x A and x B are elements of the respective sets of normals N(S A ) and N(S B ) to said patches S A and S B ; (b) computing D(x A ,x B )=√1-<x A ,x B > (c) computing ε A and ε B for each of said surface patches S A and S B respectively wherein ε A and ε B are bounds on the sets of normals N(S A ) and N(S B ), respectively; and (d) determining if D(x A ,x B )>ε A +ε B which if true indicates that said surface patches S A and S B are transversal.

Claim 35

Dependent Claim 42 words

A process according to claim 32 wherein said surface patches S A and S B are defined parametrically by said retrieved data such that: S=f(θ,φ)=(x(θ,φ), y(θ,φ)), (θ,φ)εD where x, y, z are evaluated functions and D is the domain of said patch.

Claim 36

Dependent Claim 102 words

A process according to claim 33 wherein said bounds on the set of normals over said patches S A and S B are each defined as a real number ε such that ε≧D(N x (S), N x (S)) xεS wherein x=f(θ,φ) in S, and further wherein each said bound is the one for which ε=max x εS D(N x (S), N x (S))≦√1-<w,n.sub.θ ×n.sub.φ > 2 wherein w is a vector denoting the maximum variation of N x (S) over S from N x (S) and x=f(θ,φ),n.sub.θ =f.sub.θ (θ,φ), n.sub.φ =f.sub.φ (θ,φ), and <,> denotes inner products, and x denotes cross product.

Claim 37

Dependent Claim 35 words

A process according to claim 34 wherein w is computed by computing ε.sub.θ and ε.sub.φ and then solving the systems <w,n.sub.θ >≠ε.sub.θ <w,n.sub.φ >≠ε.sub.φ ∥w∥.sub.2 =1 for the one w which minimizes <w, n.sub.θ >n.sub.φ>.

Claim 38

Dependent Claim 39 words

A process according to claim 35 wherein ε.sub.θ and ε.sub.φ are equal to ε.sub.θ =max.sub.(θ,φ)εD) D(f.sub.θ (θ,φ),f.sub.θ (θ,φ))=(ε(f.sub.θ))/|f.sub.θ.vertline. and ε=max .sub.(θ,φ)εD D(f.sub.θ (θ,φ),f.sub.φ (θ,φ))=(ε(f.sub.φ)/|f.sub.φ |. wherein D is domain of the parametric patches S A and S B .

Claim 39

Dependent Claim 75 words

A process according to claim 36 wherein ε.sub.θ and ε.sub.φ are computed using Taylor series expansion and interval arithmetic wherein ##EQU23## wherein ∥θ-θ∥ and ∥φ-φ∥ are known for one of said patches S A and S B from their respective domains D while ##EQU24## are computed using interval arithmetic on the symbolic expression for x.sub.θθ derivable from f(θ, φ), and further wherein ε(y.sub.θ), ε(z.sub.θ), ε(x.sub.φ), ε(y.sub.φ), ε(z.sub.φ) are computed in a similar manner to δ(x.sub.θ).

Claim 40

Dependent Claim 99 words

A method according to claim 20 further wherein if {S i } is a sequence of surface patches S A or S B , such that S j is a subpatch of S j-1 and diameter (S i )→0 as i→∞, and such that ε i is the sequence of computed bounds on N(S) such that D(x i , x)≦δ i , xεN(S i ) for some sequence of points {x i } in S 2 , then lim i →∞ ε i =0 so that said subdivision process can converge to arbitrarily fine approximations of the integration sets.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1992-12-25	1993-06-26	1993-12-26	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1996-12-25	1997-06-26	1997-12-26	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2000-12-25	2001-06-26	2001-12-26	$7700.00	Window Closed / Lapsed

Solid-modeling system using topology directed subdivision for determination of surface intersections

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag