Solid-modeling system using topology directed subdivision for determination of surface intersections
First Claim
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 SA and SB of said models A and B;
(2) operating on said retrieved patch descriptions to perform a mutual point exclusion test for said surface patches SA and SB 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 SA and SB for processing;
(3) operating on said retrieved patch descriptions to determine if said pair of surface patches SA and SB 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 SA and SB 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 SA and SB and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches SA and SB for processing;
(5) operating on said retrieved patch descriptions to subdivide one or both of said surface patches SA and SB 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 SA and SB for processing; and
(6) operating on said retrieved patch descriptions for said pair of surface patches SA and SB 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 SA and SB 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 SA and SB for processing.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
38 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 SA and SB of said models A and B; (2) operating on said retrieved patch descriptions to perform a mutual point exclusion test for said surface patches SA and SB 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 SA and SB for processing; (3) operating on said retrieved patch descriptions to determine if said pair of surface patches SA and SB 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 SA and SB 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 SA and SB and returning to step 1 to retrieve from said first pool further patch descriptions representing a new pair of surface patches SA and SB for processing; (5) operating on said retrieved patch descriptions to subdivide one or both of said surface patches SA and SB 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 SA and SB for processing; and (6) operating on said retrieved patch descriptions for said pair of surface patches SA and SB 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 SA and SB 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 SA and SB for processing. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 26)
-
-
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 SA and SB 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 SA and SB 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 SA and SB 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. - View Dependent Claims (21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38)
Specification