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

• US 4,890,242 A
• Filed: 02/09/1989
• Issued: 12/26/1989
• Est. Priority Date: 06/05/1986
• Status: Expired due to Term

• Current Assignee: Landmark Graphics Corporation (Halliburton Company)
• Original Assignee: XOX Corporation
• Inventors: Sinha, Pradeep, Rahman, Turhan F.
• Primary Examiner(s): Gruber, Felix D.
• Application Number:
  US07/308,975
• Time in Patent Office: 320 Days
• Field of Search: 364/474, 364/518, 364/521, 364/522, 364/578
• US Class Current: 345/419
• CPC Class Codes: G05B 19/41 characterised by interpolation, e.g. the computation of intermediate points between programmed end points to define the path to be followed and the rate of travel along that path G05B19/25, G05B19/31, G05B19/37, G05B19/39, G05B19/40 take precedence
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A system for topology directed subdivision of a pair of surfaces to identify intersecting portions thereof includes the steps of obtaining a pair of surfaces from a main pool of surface representations and performing a mutual point exclusion test to determine if the surfaces may have an intersection. For those pairs of surfaces possibly having an intersection, the transversality of the surface is checked. If tranversal, the intersection set is computed. For those pairs which are not transversal, recursive subdivision is performed until transversality is established or until a flatness criteria is met. A parallel processing system including a master processor and a plurality of slave processors performs the subdivision operation on the surfaces in a parallel fashion.

Claims

1. 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.

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

3. 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.

4. 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.

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

6. 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.

7. 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.

8. 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.

9. 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.

10. 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³, and W_A, W_B are subsets of unit spherical surface S² around the origin S² 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.

11. 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).

12. 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).

13. 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.

14. A process according to claim 13 wherein said surface patches S_A and S_B are defined parametrically by said retrieved data such that:

space="preserve" listing-type="equation">S=f(0,φ

)=(x(θ

,φ

), y(θ

,φ

), z(θ

,φ

)), (θ

, φ

)ε

D

where x, y, z

are evaluated functions and D is the domain of said patch.

15. 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.φ

>

² 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.

16. 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.φ

>

.

17. A process according to claim 16 wherein ε

.sub.θ and

ε

.sub.φ

are equal to

space="preserve" listing-type="equation">ε

.sub.θ

=max.sub.(θ

,φ

)ε

D) D(f.sub.θ

(θ

,φ

),f.sub.θ

(θ

,φ

))=(ε

(f.sub.θ

))/|f.sub.θ

|

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">ε

.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.

18. 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.θ

).

19. 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², then lim_i→

∞

δ

_i =0 so that said subdivision process can converge to arbitrarily fine approximations of the integration sets.

26. 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.

20. 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.

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

22. 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.

23. 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.

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

25. 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.

27. 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.

28. 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.

29. 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³, and W_A, W_B are subsets of unit spherical surface S² around the origin S² 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.

30. 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).

31. 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).

32. 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.

33. A process according to claim 32 wherein said surface patches S_A and S_B are defined parametrically by said retrieved data such that:

space="preserve" listing-type="equation">S=f(θ

,φ

)=(x(θ

,φ

), y(θ

,φ

)), (θ

,φ

)ε

D

where x, y, z are evaluated functions and D is the domain of said patch.

34. 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.φ

>

² 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.

35. A process according to claim 34 wherein w is computed by computing ε

.sub.θ and

ε

.sub.φ and

then solving the systems

space="preserve" listing-type="equation"><

w,n.sub.θ

>

≠

ε

.sub.θ

space="preserve" listing-type="equation"><

w,n.sub.φ

>

≠

ε

.sub.φ

space="preserve" listing-type="equation">∥

w∥

.sub.2 =1

for the one w which minimizes <

w, n.sub.θ

>

n.sub.φ

>

.

36. A process according to claim 35 wherein ε

.sub.θ and

ε

.sub.φ

are equal to

space="preserve" listing-type="equation">ε

.sub.θ

=max.sub.(θ

,φ

)ε

D) D(f.sub.θ

(θ

,φ

),f.sub.θ

(θ

,φ

))=(ε

(f.sub.θ

))/|f.sub.θ

.vertline.

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">ε

=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.

37. 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.θ

).

38. 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², then lim_i→

∞

ε

_i =0 so that said subdivision process can converge to arbitrarily fine approximations of the integration sets.