JPH0877210A - Pretreatment method for interference check - Google Patents

Abstract

(57) [Summary] [Objective] A polygonal set of a non-convex polyhedron is rapidly divided into a plurality of partial polygonal sets of convex elements. [Structure] The dividing means 2 divides a large number of convex polygons (initial polygon set) 1 forming a non-convex polyhedron into two groups, first and second groups 3a and 3b, and grouping means 4a,
4b, a polygon subset having a convex relationship with an adjacent polygon in each group 3a, 3b is obtained. Then, the merging means 5 merges those having a convex relationship between the polygon subsets of the first group and the polygon subsets of the second group having a common boundary edge line to obtain a plurality of new polygon subsets 6. Output.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an interference check preprocessing method for checking interference between a non-convex polyhedron and another object, and more particularly to a polygon set forming a non-convex polyhedron having a plurality of convex polygonal subsets. On how to split into.
More specifically, according to the present invention, an arbitrary model of a three-dimensional CAD model constructed in a graphic workstation or the like is judged to have unevenness in each area of the model, thereby determining the initial model as a finite number of convex objects. The present invention relates to a method for automatically decomposing into a set, and relates to a technique necessary for realizing a real-time interference check system for checking an interference state between three-dimensional CAD models at high speed.

[0002]

2. Description of the Related Art In a real-time interference check system for checking the interference state between three-dimensional CAD models at high speed, all the conventionally known interference check methods have limited the object to a convex object. For example, the Boblow method (A Dir
ect Minimization Approach for Obtaining the Distan
ce between Convex Polyhedra., The International J
ournal of Robotics Research, Vol.8, No.3, pp.65-7
6), Lin / Carry method (A Fast Algorithm for Incremental
Distance Calculation., Proceeedings of the 1991 I
EEE International Conference on Robotics and Automa
tion, pp.1008-1014, 1991), Gilbert method (A Fast Proc
edure for Computing the Distance Between Complex O
bjects inThree-Dimensional Space., IEEE Journal of
Robotics and Automation, Vol.4, No.2, pp.193-203,
1988). Both of these methods have a computational load of O.
The closest point can be calculated in a calculation time of (N) (0 () is a function representing the calculation load, and N is the total number of target grid points). However, the targets to which these methods can be applied are limited to convex polyhedrons.

On the other hand, commercially available three-dimensional CA such as Pro / Engineer
Shape data designed using the D system is almost always a non-convex object. Therefore, it is not possible to apply a real-time interference check method such as the Boblow method, the Lin / Carry method, or the Gilbert method to the interference check between the parts, and it is possible to apply only between the polygons forming the parts. A method of performing a brute force interference check and a method of analytically taking time to solve an equation defining a shape have been adopted.

[0004]

As described above, conventionally, there is a problem that the interference check between the non-convex polyhedron and another object cannot be performed at high speed. Further, conventionally, there has been a problem that a real-time interference check method such as the Gilbert method cannot be applied to the interference check between a non-convex polyhedron and another object. From the above, the first object of the present invention is to provide a convex decomposition method for separating a polygon set forming a non-convex polyhedron into a plurality of polygon subsets having a convex relationship.
A second object of the present invention is to provide an interference check pre-processing method capable of performing an interference check between a non-convex polyhedron and another object at high speed. A third object of the present invention is to provide a Gilb that has real-time property when checking the interference between convex polyhedrons.
An object of the present invention is to provide a pre-processing method for interference check, to which an interference check method such as the ert method can be applied.

[0005]

FIG. 1 is a diagram for explaining the principle of the present invention. 1 is a set of polygons forming a non-convex polyhedron,
2 is a means for dividing a polygon set into two groups, a first and a second group, 3a and 3b are first and second divided polygon sets, and 4a and 4b are in a convex relationship in the first and second groups. Means for grouping into certain polygon subsets, 5
Is a merging means for merging the first and second groups of convex polygon subsets, and 6 is a plurality of convex polygon subsets in the non-convex polyhedron.

[0006]

The dividing means 2 divides a large number of convex polygons (polygons) 1 forming a non-convex polyhedron into the first and second groups 3a and 3b, and the grouping means 4a and 4b divides each group 3a, 3b. In 3b, a polygon subset having a convex relationship with an adjacent polygon is obtained. Then, the merging means 5 merges those having a convex relationship between the polygon subsets of the first group and the polygon subsets of the second group having a common boundary edge line to obtain a plurality of new polygon subsets 6. Output (divide and conquer metho
d). In the divide-and-conquer method, the merging means 5 determines whether or not the polygon subset of the first group and the polygon subset of the second group have a convex relationship as follows. That is, all combinations of polygons sharing the boundary ridge line are obtained, and when the polygons have a convex relationship in all the combinations, it is determined that the polygon subset of the first group and the polygon subset of the second group have a convex relationship. However, if even one set has a concave relationship, it is determined that the relationship is not convex. According to the above, the initial polygon set of the non-convex polyhedron can be divided into polygon sub-sets of convex elements at high speed, and the interference check method such as the Gilbert method which has real-time property in the interference check can be applied.

Further, the merging possibility in the division-and-conquer method is checked by checking whether the convex objects constituted by the boundary edges of each polygon subset interfere with each other, and if they do not interfere, it is judged that there is no common boundary edge. The subsequent merging possibility processing is skipped, and when interference occurs, it is determined that a common boundary edge line exists, and the subsequent merging possibility processing is continued. By doing so, the time required for the merging possibility determination process can be shortened, and the polygon subset for each convex element can be obtained at higher speed. Furthermore, the convex decomposition processing by the division-and-conquer method is repeatedly applied to a plurality of polygon subsets obtained by the convex decomposition processing by the division-and-conquer method. If you do this,
It can be divided into a minimum number of convex elements (a local minimum of convex elements can be obtained).

When the non-convex polyhedron has a negative shape (negative object) such as a hole, the sign of the normal vector of each convex polygon (polygon) forming the non-convex polyhedron is reversed to invert the shape. Assuming the above model, a large number of polygons forming the inverted shape model are divided into two groups, and then the division and conquer method is applied to obtain a polygon subset of negative objects. Then, the polygon subset of the negative object is removed from the initial polygon set that forms the non-convex polyhedron, and the polygonal structure of the positive object is applied by applying the divide-and-conquer method to the polygon set of the non-inverted shape obtained by the removal. Obtain a subset and output each positive and negative polygon subset. By doing so, even when a negative object such as a hole exists in the non-convex polyhedron, the non-convex polyhedron can be divided into convex polyhedrons including the negative object.

[0009]

【Example】

(A) First Embodiment of the Present Invention (a) System Configuration FIG. 2 is a system configuration diagram in the case of performing interference check pre-processing on a shape model on a graphic workstation. GWS is a graphic workstation.
The CPU is a processor for executing the interference check preprocessing, the interference check processing, and other processing, and the MEM is a memory for storing the shape data FDT designed by the three-dimensional CAD system (not shown), the interference check preprocessing program ICP, and the like. , DPL is a display unit, OPS is an operation unit such as a keyboard and mouse, and OPR is an operator. The operator OPR inputs a preprocessing command to the shape model on the graphic workstation GWS using the operation unit OPS. When the pre-processing command is input, the processor CPU uses the non-convex polyhedron shape data FDT based on the interference check pre-processing program ICP stored in the memory MEM to perform the pre-processing (dividing the polygon set of the non-convex polyhedron). ) Is executed. Then, the division result is stored in the memory MEM and the preprocessing result is presented to the operator through the display unit DPL.

(B) Outline of Interference Check Preprocessing FIG. 3 is a schematic processing flow of the interference check preprocessing of the present invention. The three-dimensional CAD system creates a shape model (non-convex polyhedron) to create a graphic workstation GW.
Input to S (steps 1001 and 1002). CAD
The system inputs all polygon data when an object (non-convex polyhedron) is covered with polygons. The polygon data has information indicating the coordinate value of each vertex of the polygon and the light reflection direction at that point. The most general polygon data is represented by combining triangular polygons as shown in FIG. In the case of the triangular polygon data shown in FIG. 3, three real numbers following normal represent the light reflection direction, and three real numbers following vertex represent the vertex coordinate values. The procedure for outputting polygon data from the shape model in the three-dimensional CAD system is usually prepared in the three-dimensional CAD system. Then, the polygon data is divided into a set of polygon data (polygon subset) divided for each convex element in accordance with the convex decomposition basic algorithm by the division and conquer method. That is, the initial polygon data (polygon set of non-convex polyhedron) is divided into sets of subsets for each convex element and output (steps 1003, 100).
4). After that, a convex polyhedron is generated for each subset.
Incidentally, although each shape of the polygon is generally arbitrary, each polygon is assumed to satisfy the convexity.

(C) Basic Algorithm for Convex Decomposition by Divide and Conquer Method FIG. 4 is a flow chart of the basic algorithm for convex decomposition by the divide and conquer method. An initial polygon set (polygon set of non-convex polyhedron) P is input (step 1101), and then the initial polygon set P is processed by the division and conquer method (step 1102). That is, the initial polygon set P
Is divided into two groups, a first group and a second group, and a polygon subset having a convex relationship with an adjacent polygon in each group is obtained. Then, a plurality of new polygon sub-sets DP1, DP2, ... for each convex element are merged by merging those in which the polygon sub-sets of the first group and the polygon sub-sets of the second group having a common boundary edge are in a convex relationship. · Ask for. Then, the polygon subsets DP1, DP2, ...
Is output (step 1103).

The following is an example of a detailed program of the divisional governance method. Definition P = {p ₁ , p ₂ , p ₃ , ...}: Initial polygon set DC (P) = {DP1 = { ₁ p ₁ , ₁ p ₂ , ₁ p ₃ , ...}, DP2 = { _{2 p 1, 2 p 2,} 2 p 3, ···}, ···}: P divided polygon sets NoP: number of elements P Algorithm (divide and conquer) an if (number of input polygons 1, ie, NoP = 1) then DC (P) = P else DIVIDE: k = [number of elements of P / 2] PL = {p ₁ , p ₂ , p ₃ , ..., P _k }: polygon set of k or less PH = { _{Pk + 1} , _{pk + 2} , _{pk + 3} , ..., _pNoP }: Polygon set larger than k RECUR: Costruct DC (PL) and DC (PH) recursively. MERGE: Merge DC (PL) and DC (PH) DC (P) = Merge (DC (PL), DC (PH)) endif As can be seen from the above algorithm, in the divide and conquer method, the process of division and reign is recursively repeated. The most important point where problem dependence exists in the divide-and-conquer law is the "merging" process, that is, the method of constructing the function Merge.

(D) Merge Process in Divide and Conquer Method FIG. 5 is a flow chart of the Merge process in the Divide and Conquer method. 1) Prepare convex element sets DC (PL), DC (PH)
(Steps 1111a, 1111b). Convex element set DC
Each element of (PL) and DC (PH) is CLi, C in FIG.
As indicated by Hj, a set of polygons that form the element and a set of boundary edges that form the boundary of the element.
(boundary edges). 2) Judgment of possibility of merging It is judged whether or not the convex elements CLi and CHj can be merged with each other (step 1112). The judgment conditions are as follows. Condition 1: All boundary edges shared by the convex elements CLi and CHj are extracted. Whether or not they are shared can be determined by comparing the midpoints of the polygon sides that form the boundary ridge. If there is no shared boundary edge line, it is determined that Merge is impossible. Condition 2: With respect to the shared boundary ridge, the uneven relationship between the CLi polygon and the CHj polygon sharing the ridge is checked. If there is a combination of polygons that are in a concave relationship, it is determined that the merge is impossible. Condition 3: When condition 1 and condition 2 are cleared, that is,
It is determined that Merege is possible when polygons have a convex relationship in all combinations of polygons sharing a boundary ridge.

3) Merge Order Merge of convex elements is performed in the following order. 3-1) Convex element CL₁Is CH_jIs it possible to merge with (j = 1,2, ... NPH)?
Determine whether or not. If CL₁Is CH_jAnd Merge is possible
Then, after that, CL₁, DC (PH) as follows
To do. CL₁∪CH_j→ CL₁  DC (PH) = {CH₁, CH₂・ ・ ・ CH_j-1, CH_{j + 1}・
..} 3-2) Perform the same procedure for CLi (i = 2,3, ... NPL)
It 4) Construction of merged convex element set DC (P) By the process of 3) above, merged convex element set DC (P) = Merge (DC (PL), D
C (PH)) is executed, and DC (P) = {CL₁, CL₂・ ・ ・ ・ ・ ・ CLP_NPL, C
H_j′, CH_jThe merged convex element set DC (P) given by ″ ...} is output.
(Step 1113). Where {CH_j′, CH_j″ ・ ・
・} Is for DC (PH) that does not merge with any CLi
It is a convex element.

(E) Judgment of Concavo-convex Relationship between Polygons FIG. 6 is an explanatory diagram of the concavo-convex relationship judgment processing between polygons.
As shown in FIG. 6 (a), one boundary ridge line BEG is shared 2
Assume one polygon A, B. The relative positional relationship of the polygons is either distant from each other or contacting each other via a ridgeline as shown in FIG. 6A, and other relationships (for example, intersecting at a portion other than the ridgeline). Etc.) is not available. 6 (a), the vector b, c is a perpendicular vector down each polygon B, the center of gravity p of the polygon A, from q to boundary edge x ₁ -x ₀ = a. Also, vectorized units of vectors a, b, and c are e ₀ , e ₁ , and
e ₂ . n _A and n _B represent outward normal vectors of the polygon A and the polygon B (the averages of the light reflection directions at the respective lattice points defining the polygon). At this time, b, c, e ₀ , e ₁ and e ₂ are given by the following equations.

B = px _0- (x ₁ -x ₀ ) * (px ₀ ) (x ₁ -x ₀ ) / | x ₁ -x ₀ | ² * is a vector inner product = px ₀ -e ₀ * ( px ₀ ) e ₀ c = q-x ₀ -e ₀ · (q-x ₀ ) e ₀ e ₀ = a / | a | e ₁ = b / | b | e ₂ = c / | c | In order to determine the concave-convex relationship between the polygon A and the polygon B, the vector b is X ₀ as shown in FIG. 6B. Coordinate conversion is performed so that it matches the axis. The transformation matrix at this time is

[Equation 1] Given in.

If either of the following two conditions is satisfied depending on the direction of the normal vector n _B , it can be said that the polygon A and the polygon B have a convex relationship. That is, 1) when (e ₀ × e ₁ ) · n _B > 0, [T · c] _Z <0, and when (e ₁ × e ₂ ) · n _A > 0, 2) ( When e ₀ × e ₁ ) · n _B ≦ 0 [T · c] _Z ≧ 0 and (e ₁ × e ₂ ) · n _A ≦ 0 is satisfied, polygon A and polygon B are convex. It can be said that there is a relationship. Actual C
When dealing with AD data, the judgment conditions are as follows in consideration of the error.

1) When (e ₀ × e ₁ ) · n _B > 0 [T · c] _Z <ε and (e ₁ × e ₂ ) · n _A > −ε, 2 ) (e ₀ × e ₁ ) · n _B ≦ 0 [T · c] _Z ≧ −ε and (e ₁ × e ₂ ) · n _A ≦ ε are satisfied, polygon A and polygon B Have a convex relationship. Here, ε is a minute amount determined by the object to be handled. Each element of the set DC (P) of polygon subsets obtained by the division and conquer method is not always convex. The unevenness determination condition shown in FIG. 6 is a local condition. However, when the initial polygon set is divided under the conditions shown in FIG. 6, very good convexity is shown in many cases.

(B) Second Embodiment When convex decomposition is performed by a basic algorithm based on the divide-and-conquer method, the number of convex elements after decomposition is not always the minimum. In the second embodiment, the number of convex elements is optimized (reduced as much as possible) by repeatedly using the convex decomposition basic algorithm. The optimization method of the second embodiment is not a method of minimizing the number of convex elements in a strict sense, but is a method of reducing the number of elements as much as possible within a limited time. FIG. 7 is a flowchart of the process of the second embodiment (optimization method). An initial polygon set (non-convex polyhedron polygon set) P is input from a three-dimensional CAD system or the like (step 1201), and then a convex decomposition basic algorithm by the division-and-conquer method is applied to the initial polygon set P (step 1202). . That is, the initial polygon set P is divided into two groups, a first group and a second group, and a polygon subset having a convex relationship with an adjacent polygon in each group is obtained. Then, a plurality of new polygon sub-sets DP1, DP2, ... for each convex element are merged by merging those in which the polygon sub-sets of the first group and the polygon sub-sets of the second group having a common boundary edge are in a convex relationship. · Ask for.

After that, the polygon subsets DP1 and DP
A convex element set DC (P) whose elements are 2, ... Is output (step 1203). The number of convex elements is NDC (P)
Is. Then, the convex decomposition basic algorithm based on the divide and conquer method is applied again to the convex element set DC (P) (step 1204). That is, a plurality of polygon subsets forming the convex element set DC (P) are divided into first and second groups, and in each group, a subset of polygons having a convex relationship with an adjacent polygon is obtained, and common polygon subsets are obtained. A plurality of new polygon sub-sets DDP1, DDP2, ... Are obtained by merging the polygon sub-sets of the first group and the polygon sub-sets of the second group having the boundary ridges in a convex relationship. After that, polygon subsets DDP1 and DDP
A convex element set DC (DC (P)) having 2, 2, ...
Is output (step 1205). The number of convex elements is ND
DC (P).

Next, the number NDC (P) of polygon subsets obtained last time and the number ND of polygon subsets obtained this time
DC (P) are compared (step 1206), and if they match, the convex element set DC (DC (P)) is finally output (step 1207). And this convex element set DC
On the other hand, a convex polyhedron will be generated using the polygon subset that constitutes (DC (P)). On the other hand, if NDDC (P) and NDC (P) are not equal (for example, NDDC (P) <NDC ( P)), DC
(DC (P)) → DC (P) (step 120
8) After that, the processing from step 1204 is repeated.
That is, a plurality of newly obtained polygon subsets DC
(DC (P)) is repeatedly subjected to convex decomposition processing by the division-and-conquer method. In the optimization method, the convex decomposition basic algorithm is repeatedly applied to the output DC (P) until the number of convex elements is no longer reduced.

(C) Third Embodiment In the method using the basic algorithm by the division and conquer method,
There is a possibility that the number of divided convex elements in recognizing holes etc. will increase more than expected. In the third embodiment, in order to reduce the number of convex elements, the Boolean algebra is regarded as negative for an object such as a hole and convex decomposition processing is performed, and for other positive objects, the convex decomposition processing of the first embodiment is performed. Is to be applied. To regard a Boolean algebra as negative means to simply reverse the sign of the normal direction of each polygon (reverse the normal direction). By combining the basic algorithm based on the ordinary divide-and-conquer method with the negative object recognition method, convex decomposition with a small number of convex elements becomes possible.
FIG. 8 is an explanatory diagram of an object representation method by a Boolean set operation of an object including a shape (negative object) such as a hole. HL is a hole, HL '
Is a hole portion in which the normal direction is reversed, and BDY is an object without a hole (object without a hole). The object with a hole is represented by subtracting the hole portion with the normal direction reversed from the object BDY without a hole.

FIG. 9 is a flow chart of the convex decomposition process of the third embodiment,
FIG. 10 is an explanatory diagram of the convex decomposition result. Three-dimensional CAD
An initial polygon set (non-convex polyhedron polygon set) P is input from a system or the like (step 1301), and then a polygon set P _B in which all the normal directions of the initial polygon set P are reversed is created (step 1302). Thereafter, the convex decomposition basic algorithm is applied to the polygon set P _B (step 1303). That is, the polygon set P _B is divided into two groups, a first group and a second group, and a polygon subset having a convex relationship with an adjacent polygon in each group is obtained. Then, the polygon subsets of the first group and the polygon subsets of the second group having a common boundary edge are merged to obtain a plurality of new polygon subsets for each convex element.

Thereafter, a convex element set DC (P _B ) (see FIG. 10) having the plurality of polygon subsets as elements is output, and each convex element of the convex element set DC (P _B )
The convex elements composed of two or more polygons are taken out, and all the polygon sets forming these convex elements are set to P ₂ (D
C (P _B )). That is, the polygons forming the negative object convex elements such as holes are collected and set as P ₂ (DC (P _B )) (step 1304). Next, a difference set between the initial polygon sets P and P ₂ (DC (P _B )) is taken to obtain a polygon set PP ₂ (DC (P _B )) that constitutes a true object (step 130).
5). When the polygon set (difference set) that constitutes the true object is obtained, the convex decomposition basic algorithm by the division and convolution method is applied to the difference set PP ₂ (DC (P _B )) (step 130).
6). That is, the difference set PP ₂ (DC (P _B )) is divided into the first and second 2
Divide into one group, and find a polygon subset in which the relationship with adjacent polygons is convex in each group. Then, the polygon subsets of the first group and the polygon subsets of the second group having a common boundary edge are merged to obtain a plurality of new polygon subsets for each convex element. Then, a convex element set DC (PP ₂ (DC (P _B ))) having the plurality of polygon subsets as elements is output (step 1307, FIG. 10) to recognize a true object. Finally, DC (PP ₂ (DC (P _B ))) is the convex element of the positive object, DC
Output (P _B ) as the convex element of the negative object (step 1
308). After that, a convex polyhedron is generated using the polygon subset of each convex element.

(D) Fourth Embodiment The number of convex elements is reduced by applying the optimization method to the third embodiment, in the same way as the number of convex elements is reduced by applying the optimization method to the first embodiment. be able to. FIG. 11 is a flowchart of the convex decomposition process in such a case, and the difference from the third embodiment is that the optimization method is applied instead of the convex decomposition basic algorithm in steps 1303 ′ and 1306 ′.

(E) Fifth Embodiment of the Present Invention (a) Consideration In the above embodiments, the polygon subset C of the first group is used.
Merge of Li and polygon subset CHj of the second group
The possibility is judged as follows. That is, regardless of whether the polygon subset CLi and the polygon subset CHj have a common edge or not, among all the polygon edges forming the boundary edge of CLi and all the polygon edges forming the boundary edge of CHj. A common boundary ridge line is obtained depending on whether the points match.

However, in the merge possibility determination process, it is not necessary to check whether or not the midpoints match in all combinations of polygon subsets, and also in brute force combinations of polygon edges forming a boundary ridge. Since it does not happen, it takes a considerable amount of time to process the merge possibility determination,
It limits the speed of convex decomposition. By the way, when the boundary ridgeline of the convex element CLi and the boundary ridgeline of the convex element CHj have a common boundary ridgeline portion, a convex object constituted by the boundary ridgeline of the convex element CLi and a convex object constituted by the boundary ridgeline of the convex element CHj. Interfere with. Therefore, before executing the process of obtaining the common boundary ridgeline of the convex elements CLi and CLj, the boundary between the convex object and the convex element CHj formed by the boundary ridgeline of the convex element CLi by the interference check method with a calculation load of O (N). Check if the convex object formed by the ridge line interferes. Then, when there is no interference, the subsequent merge processing is skipped, and only when there is interference, the subsequent Merge processing is continued. By doing so, the time required for the Merge processing can be significantly reduced, and the convex decomposition processing can be performed at high speed.

(B) Outline of Pre-Processing for Interference Check FIG. 12 is another schematic process flow of the pre-processing for interference check of the fifth embodiment. The same parts as those in the first embodiment of FIG. are doing. The difference from the first embodiment is that, in step 1003 ′, a convex decomposition basic algorithm (fast convex decomposition basic algorithm) by an interference check built-in type divide-conquer method is applied in place of the convex decomposition basic algorithm by the divide-conquer method. That is the point.

FIG. 13 is a processing flow of the fast convex decomposition basic algorithm. An initial polygon set (non-convex polyhedron polygon set) P is input (step 1101), and then the initial polygon set P is subjected to convex decomposition processing by a high-speed convex decomposition algorithm (step 1102 '). That is, the initial polygon set P is divided into two groups, a first group and a second group, and a polygon subset having a convex relationship with an adjacent polygon in each group is obtained. Next, a plurality of new polygon subsets DP1 for each convex element are merged by merging the polygonal subsets of the first group and the polygonal subsets of the second group having a common boundary ridge in a convex relationship. Find DP2, ... Thereafter, the polygon subsets DP1, DP2, ... Are output (step 1103). Incidentally, each polygon subset DP
A convex polyhedron is generated based on 1, DP2, ...
The most important point where problem dependence exists in the divide-and-conquer law is the "merging" process, that is, the method of constructing the function Merge.

(C) Merge Process in Divide and Conquer Method In order for the convex elements CLi and CHj to be mergeable, C
Li and CHj have a common boundary edge line. That is, it is a necessary condition that the convex elements CLi and CHj interfere with each other through the boundary ridge. Therefore, the interference check algorithm is applied between the convex elements CLi and CHj, and if there is no interference, the subsequent Merge process for CLi and CHj can be skipped. FIG. 14 is a flowchart of the Merge process in the Divide and Conquer method. 1) Prepare convex element sets DC (PL), DC (PH)
(Steps 1111a, 1111b). DC (PL) = {CL1, CL2, ··· CLi, ···} i = 1,2, ··· NDC (PL) CLi {polygons = {p CL11, p CL12, p CL13, ··· p _{NCLP1} boundary edges = {b CL11} , b CL12, b CL13, ··· b NCLB1}} DC (PH) = {CH1, CH2, ·· CHi, ···} i = 1,2, ··· NDC (PH) CLi {polygons = {p _CH11 , p _CH12 , p _CH13 , ・ ・ ・ p _NCHP1 } boundary edges = {b _CH11 , b _CH12 , b _CH13 , ・ ・ ・ b _NCHB1 }} Convex element set DC (PL) Each element of DC (PH) is composed of polygon subsets and a set of boundary edges that form the boundary of the elements.

2) Judgment of Mergeability It is judged whether or not the convex elements CLi and CHj can be merged with each other (step 1112 '). The judgment conditions are as follows. Condition 1: Boundary edge lines Bedge _CLi , Be of the convex elements CLi, CHj
Interference check between dge _CHj . If there is no interference, Merg
e Determined as impossible. Condition 2: Convex elements CLi and CH that may interfere with each other
For j, all boundary edges shared between CLi and CHj are extracted. Whether or not they are shared can be determined by comparing the midpoints of the polygon sides that form the boundary ridge. If there is no shared boundary edge line, it is determined that Merge is impossible. Condition 3: With respect to the shared boundary ridge line, the uneven relationship between the CLi polygon and the CHj polygon sharing the ridge line is checked. If there is a combination of polygons that are in a concave relationship, it is determined that the merge is impossible. Condition 3: Me if condition 1, condition 2 and condition 3 are cleared
Judge that rege is possible.

3) Merge Order Merge of convex elements is performed in the following order. 3-1) Convex element CL₁Is CH_jIs it possible to merge with (j = 1,2, ... NPH)?
Determine whether or not. If CL₁Is CH_jAnd Merge is possible
Then, after that, CL₁, DC (PH) as follows
To do. CL₁∪CH_j→ CL₁  DC (PH) = {CH₁, CH₂・ ・ ・ CH_j-1, CH_{j + 1}・
..} 3-2) Perform the same procedure for CLi (i = 2,3, ... NPL)
It 4) Construction of merged convex element set DC (P) By the process of 3) above, merged convex element set DC (P) = Merge (DC (PL), D
C (PH)) is executed, and DC (P) = {CL₁, CL₂・ ・ ・ ・ ・ ・ CLP_NPL, C
H_j′, CH_jThe merged convex element set DC (P) given by ″ ...} is output.
(Step 1113 '). Where {CH_j′, CH_j″ ・
..} is a DC (PH) that does not merge with any CLi
It is a convex element.

(D) Interference check algorithm Among the interference check algorithms between convex objects, Bobrow
Method, Lin / Canny method, and Gilbert method can be used as the interference check method of the existing calculation load O (N). FIG. 15 is a schematic processing flow of the interference check algorithm. Convex element CLi,
An interference check algorithm is applied between the convex objects formed by the boundary edges Bedge _CLi and Bedge _CHj of CHj (step 1401). By applying the interference check algorithm, the distance dist (Bed between the closest points of the boundary edges Bedge _CLi and Bedge _CHj
ge _CLi , Bedge _CHj ) and output (step 140
2). If the distance between the closest points is found, the distance dist (Bedge
_CLi , Bedge _CHj ) and ε are compared, and dist (Bedge _CLi , B
edge _CHj ) ≦ ε, it is determined that interference occurs, and dist (Bedge
_{If CLi} and Bedge _CHj )> ε, it is determined that there is no interference.
Note that ε is a user-defined minute constant that determines the accuracy of interference check determination.

(F) Interference check method (Gilbert method) (f-1) Object representation method and distance between objects Consider a convex polyhedron X in a three-dimensional space. At this time, an arbitrary point x in X is a grid point (vertex) xi ∈ located at the boundary of X.
It can be expressed as follows using X. x = Σλixi (i = 1 to m): xi∈X, λi ≧ 0 λ ₁ + λ ₂ + ... + λm = 1 (1) The above equation is a set of lattice points {xi: i = 1, 2, .. may be defined as a convex polyhedron stretched by m}. The {xi} is called the base of the convex polyhedron X. Now, the two convex polyhedra K ₁ and K ₂
think of. At this time, the closest distance between the two objects is defined as follows.

D (K ₁ , K ₂ ) = min {| x−y |: xεK ₁ , yεK ₂ ) (2) where x and y are position vectors and | x−y | _{= √ {(x 1 -y 1} ) 2 + (x 2 -y 2) 2 + (x 3 -y 3)} ^2. Therefore, the problem of finding the closest point between two convex polyhedra is to find x and y that satisfy the equation (2) by the following equation. x = Σλi · xi (i = _{1 to} m ₁ ): xi i K ₁ , λi ≧ 0 λ ₁ + λ ₂ + ... + λm ₁ = 1 y = Σμi · yi (i = 1 to m ₂ ): yi ∈ K ₂ , μi ≧ 0 μ ₁ + μ ₂ + ... + μm ₂ = 1 (3) Simply thinking, in equation (3), both λ and μ are variables, so the calculation load is O (M ₁ · M ₂ ). Equation (2) can be rewritten as follows.

Let K be the union and difference sets of arbitrary objects K ₁ and K _{2.
When 1} ± K ₂ = {x ± y: x∈K ₁ , y∈K ₂ } is defined,
Equation (2) is equivalent to the following equation. d ₁₂ = min {| z |: zεK}, K = K ₁ −K ₂ (4) The union of the objects K ₁ and K ₂ is the vector addition of arbitrary position vectors x and y of each object. Is an object composed of a set of position vectors z obtained by the above, and the difference set of the objects X ₁ and X ₂ is a set of position vectors z obtained by vector subtraction of arbitrary position vectors x and y of each object. It is an object that has been destroyed. In equation (4), the problem of searching for the closest point is the coordinate origin O
Tells that it is equivalent to the problem of finding the closest point to polyhedron K. When both the polyhedra K ₁ and K ₂ are convex polyhedrons, the polyhedron K is also a convex polyhedron, and the set Z of lattice points forming the convex polyhedron K is given below.

Z = {zi = xj-yk: xjεK₁, Yk ∈ K₂, I = 1, 2, ... m₁m₂  j = 1, 2, ... m₁  k = 1, 2, ... m₂} (5) Summarizing the above, the following conclusions are derived. Sanawa
Then, "Two convex polyhedra K₁, K₂The question to find the closest point between
The problem is the convex polyhedron K (= K₁-K₂Up to)
It is equivalent to the problem of finding the approach point. However, K is m₁m₂Pieces (m₁:
K₁Number of grid points of, m ₂: K₂Number of grid points) of the grid points {zi =
It is a convex polyhedron stretched by xj-yk}. "

(F-2) Outline of Gilbert's method From the conclusion in (f-1), the problem of finding the closest point between two convex polyhedrons K ₁ and K ₂ is that the closest point O to the convex polyhedron K is It comes down to the problem of finding points. Gilbert's method uses this fact and a function called the Support Function described below. Support function hx for convex polyhedron
(η): R ³ → R is defined below. hx (η) = max {xi · η: i = 1 to m} (6) where {xi} is the set of lattice points that are the base of the convex polyhedron X, and ・ means the vector inner product , Also R
³ → R means conversion from 3D to 1D. Therefore, the port function hx (η) of the equation (6) means that when the vector η is determined as shown in FIG. 16, the lattice point of the convex polyhedron X farthest from the origin in that direction is obtained. ing. Now, assuming that the vector (position vector) from the coordinate origin O to this grid point is sx (η), the equation (6) is as follows.

Hx (η) = sx (η) η (7) The calculation load for the closest point search by the Gilbert method is O (M ₁ + M ₂ ).
Becomes The reason is based on that the following law holds for the support function hk (η) and the position vector sk (η) of the difference set K of the convex polyhedra K ₁ and K ₂ . hk (η) = hk ₁ (η) + hk ₂ (−η), sk (η) = sk ₁ (η) −sk ₂ (−η) (8) The above equation is calculated from m ₁ m ₂ lattice points. Convex polyhedron K = K ₁ −K ₂
It means that the support function for is composed of the sum of the support functions for the convex polyhedra K ₁ and K ₂ . Therefore, as is clear from the definition of equation (6), the calculation load for obtaining hx (η) is O (M ₁ + M ₂ ). The essence of the Gilbert's method for searching for the closest point is that the closest point is gradually approached by repeatedly using the support function hx (η). That is, the Gilbert method is composed of the following four processes.

(F-3) Closest point search algorithm by Gilbert method 1) Initialization With respect to the convex polyhedrons K ₁ and K ₂ , the difference convex polyhedron K ₁ -K _{2 is set} to K. Take arbitrary points in the convex polyhedron K and set them as y ₁ , y ₂
... Let ypεK. Note that y ₁ , y ₂ ... Yp do not necessarily have to be the base lattice points of the convex polyhedron K. In general, p is 1 ≦ p ≦ 4. At this time, a set of initial grid points V _k
Let (= V ₀ ) be V _k = {y ₁ , y ₂ ... Yp}, k = 0.

2) Closest point search for the basic polyhedron For the set Vk of lattice points consisting of the number of elements p (4 or less), ν _k = ν (co V _k ) (9) is calculated. Here, co V _k is a convex polyhedron based on the lattice point set V _k , and ν (X) is a convex polyhedron X from the coordinate origin O.
Represents the closest point vector (position vector) to.

3) Closest point determination R ³ → function g _x (x) to R is defined as follows. g _x (x) = | x | ² + h _x (−x) In the above equation, the first term on the right side means the square of the distance to a given point when the position vector of the given point on the convex polyhedron K is x. The second term on the right side means the inner product of the vector −x and the lattice point position vector closest to the origin in the vector x direction. In other words, h _x (−x) is the minimum value of the inner products of the position vector of the lattice point and x. This g
x (x) is the judgment function of the closest point, and x is from the origin O to K
If it is the closest point to
_x (x) = 0. Incidentally, it can be proved that gx (x) is the judgment function of the closest point, but it is omitted here. For details, see above.
`` IEEE JOUNAL OF ROBOTICS AND AUTOMATION, VOL.4, N
O.2, APRIL 1988, pp. 193-203 `` A Fast Procedure for C
omputing the Distance Between Complex Objects in T
See hree-Dimensional Space ”. From the above,
If ν _k obtained by the equation (9) is g _k (ν _k ) = 0 (10), ν (K) = ν _k is set, and the closest point search process is terminated.

4) Increment of k If the equation (10) is not established, k is incremented. That is, V _{(k + 1) is set} to V _{(k + 1)} = V _k ′ ∪ {s _k (−ν _k )} (11). Where V _k ′ is V _k ′ ⊆V _k , and ν _k
It is the smallest subset of V _k which is a ∈co V _k '. Expression (11) is _obtained by calculating a subset V _k ′ (including ν _k ) of V _k and a lattice point s _k closest to the origin in the direction of the closest point vector ν _k in V _k .
It means a set including (−ν _k ). From the above, if equation (10) does not hold, increment k by equation (11)
The process after returning to 2) is repeated until Eq. (10) is satisfied.

(F-4) Application of the closest point search algorithm by the Gilbert method In order to deepen the understanding of the closest point search algorithm by the Gilbert method, the closest point search will be described with reference to FIG. In FIG. 17, initial values V ₀ = {z ₁ , z ₂ , z ₃ }
Then, the closest point vector at V ₀ is calculated as ν ₀ . At this time, since the expression (10) is not satisfied, k is incremented. Since V ₁ = V ₀ ′ ∪ {s _k (−ν ₀ )} = V ₀ ′ ∪ {z ₄ } and V ₀ ′ = {z ₂ , z ₃ }, V ₁ = {z
₂ , z ₃ , z ₄ }. The closest point vector at V ₁ is ν ₁ . At this time, since the expression (10) is not satisfied, k is incremented.

Since V ₂ = V ₁ ′ ∪ {s _k (−ν ₁ )} = V ₁ ′ ∪ {z ₅ } and V ₁ ′ = {z ₃ , z ₄ }, V ₂ = {Z
₃ , z ₄ , z ₅ }. When the vector of the closest point at V ₁ is calculated, it becomes ν ₂ , and this ν ₂ satisfies the equation (10),
ν ₂ is the closest point vector, and ν ₂ = ν (K) εco {z ₄ , z ₅ }. As a result, the closest distance d becomes d = | ν ₂ |. Try the same thing with different initial values. In FIG. 30, the initial value V ₀ = {z ₂ } is set, and the closest point vector at V ₀ is calculated to be ν ₀ ′ (= z ₂ ). At this time, (1
Since 0) is not satisfied, k is incremented. Since V ₁ = V ₀ ′ ∪ {s _k (−ν ₀ ′)} = V ₀ ′ ∪ {z ₅ } and V ₀ ′ = {z ₂ }, V ₁ = {z ₂ , z
₅ }.

The closest point vector at V ₁ is calculated as ν ₁ ′. At this time, since the expression (10) is not satisfied, k is incremented. Since V ₂ = V ₁ ′ ∪ {s _k (−ν ₁ ′)} = V ₁ ′ ∪ {z ₄ } and V ₁ ′ = {z ₂ , z ₅ }, V ₂ = {z
₂ , z ₄ , z ₅ }. When the vector of the closest point at V ₂ is calculated, it becomes ν ₂ ′ (= ν ₂ ), and by this ν ₂ ′, (10)
The expression is satisfied, and ν ₂ becomes the closest point vector, and ν ₂ ′ = ν ₂ = ν (K) εco {z ₄ , z ₅ }. As a result, the closest distance d becomes d = | ν ₂ |, and the same result as when the initial value V ₀ is V ₀ = {z ₁ , z ₂ , z ₃ } is obtained.

The initial grid points of Gilbert's method (initial values)
V ₀ is generally arbitrary, but it is efficient to start from lattice points in the direction of the difference in the center of gravity of each convex polyhedron as shown below. v ₀ = {s _k (−z _c1 + z _c2 )} (12) where z _c1 and z _c2 are, respectively, z _c1 = Σ (xi / M ₁ ) (i = _{1 to} M ₁ ) xi: convex polyhedron Base grid point of K ₁ z _c2 = Σ (yi / M ₂ ) (i = 1 to M ₂ ) yi: Base grid point of convex polyhedron K ₂ . The following inequalities hold when the closest point is determined by the Gilbert method (see FIG. 18). r _k = −h _k (−ν _k ) / | ν _k | ≦ | ν (K) | ≦ | ν _k | (13) Therefore, if r _k > 0 for a certain k, interference between two convex objects It can be said that there is no.

(G) Merge Possibility Judgment Process Based on Gibert Method FIG. 19 is a flowchart showing a merge possibility judgment process based on the Gilbert method. Boundary edge lines of convex elements CLi, CHj Bedge _CLi , Be
by applying the Gilbert method between each composed convex object with dge _CHj, it computes the r _k of (13) (step 141
1). Then, it is determined whether r _k > 0 (step 141
2) If r _k > 0, there is no interference, so it is determined that merge is impossible (step 1413). However, if r _k ≦ 0, it is determined that there is merge interference because of interference, and whether merge is possible / impossible is determined from the conditions 2 to 4 of merge possibility described above (step 1414).

(H) Simplified Merge possibility determination process based on Gibert method The merge possibility determination process based on Gibert method is further simplified. The point of simplification is to set the initial lattice point V ₀ of the Gilbert method as an arbitrary vertex from the set of vertices Bedge _CLi and Bedge _CHj on the boundary edge line.
By _selecting Bedge _CLi0 and Bedge _CHji0 , V ₀ = Bedge _CLi0 −Bedge _CHji0 (14) is constructed. Then, using this V ₀ , r = −h _k (−V ₀ ) = − h _k1 (−V ₀ ) −h _k2 (V ₀ ) (15) is calculated. If r> 0, Bedge _CLi , Bedge _CHj
It is determined that there is no interference between the convex elements CLi and CHj and there is no possibility of merging.

FIG. 20 shows Mer based on the simplified Gilbert method.
It is a ge possibility determination processing flow. Convex element CLi, CHj
Applying the simplified Gilbert method between the convex objects composed of the boundary edges Bedge _CLi and Bedge _CHj of
Is calculated (step 1411 '). Next, it is judged whether r> 0 (step 1412 '). If r> 0, there is no interference, so it is judged that merge is impossible (step 141).
3 '). However, if r ≦ 0, there is interference.
It is determined that merge is possible / impossible based on the conditions 2 to 4 of the possibility of merge described above as the presence of merge interference (step 141).
4 ').

(F) Modified Example (a) Modified Example 1 The convex decomposition method of the fifth embodiment described above can be configured to be optimized to reduce the number of convex elements. The processing flow in this case is shown in FIG. In FIG. 21, the difference from the processing of the second embodiment (see FIG. 7) is step 120.
In 2 ′ and 1204 ′, a convex convex decomposition algorithm is used instead of the convex decomposition basic algorithm. (b) Modification 2 The interference check built-in high-speed convex decomposition algorithm can be applied to the convex decomposition process when a negative object exists, and the processing flow in this case is shown in FIG. In FIG. 22, the difference from the third embodiment is that step 1303 ′,
In 1306 ′, the convex decomposition basic algorithm is replaced by a high-speed convex decomposition algorithm of interference check built-in type. (c) Modification 3 The modification 2 may be further subjected to an optimization process to reduce the number of convex elements. Although the present invention has been described above with reference to the embodiments, the present invention can be variously modified according to the gist of the present invention described in the claims, and the present invention does not exclude these.

[0052]

As described above, according to the present invention, it is possible to obtain a polygon subset for each convex element at high speed by the convex decomposition processing by the division-and-conquer method. Therefore, a non-convex polyhedron can be formed at high speed by using the polygon subset. It is possible to generate convex polyhedrons to be constructed, and to apply interference checking methods such as the Gilbert method, which has real-time property in interference check between convex polyhedrons, to interference check of non-convex polyhedron. Further, according to the present invention,
Since it is configured to repeatedly apply the convex decomposition processing by the division-and-conquer method to a plurality of polygon subsets obtained by the convex decomposition processing by the division-and-conquer method, the polygon can be locally divided into the minimum number of convex polyhedra.

Further, according to the present invention, when the non-convex polyhedron has a negative shape (negative object) such as a hole, the sign of the normal vector of each convex polygon (polygon) forming the non-convex polyhedron. Assuming an inverted shape model by reversing, and applying the divide-and-conquer method to the inverted shape model to obtain the polygon subset of the negative object, and then calculating the negative object's polygon from the initial polygon set forming the non-convex polyhedron. The polygon subset is removed, and the polygonal subset of the non-inverted shape obtained by removing the polygon subset is applied to obtain the polygon subset of the regular object. Since the convex polyhedron is generated from each of the positive and negative polygon subsets, even when a negative object such as a hole exists in the non-convex polyhedron, the non-convex polyhedron can be divided into convex polyhedrons including the negative object.

Further, according to the present invention, the merging possibility in the division-and-conquer method is checked to see if the convex objects formed by the boundary edges of each polygon subset interfere with each other. Since it is determined that there is no merging possibility, the subsequent merging possibility processing is skipped, and if there is interference, it is determined that a common boundary edge exists and the merging possibility processing after that is continued. The time required for the possibility processing can be shortened, and the polygon subset for each convex element can be obtained at high speed.

[Brief description of drawings]

FIG. 1 is a diagram illustrating the principle of the present invention.

FIG. 2 is a system configuration diagram of the present invention.

FIG. 3 is a schematic processing flow of interference check preprocessing.

FIG. 4 is a processing flow of a convex decomposition basic algorithm.

FIG. 5 is a flow chart of the Merge process.

FIG. 6 is an explanatory diagram for determining a concave-convex relationship between polygons.

FIG. 7 is a processing flow of the second embodiment of the present invention.

FIG. 8 is an explanatory diagram of an object expression by a Boolean set operation.

FIG. 9 is a processing flow of a third embodiment of the present invention.

FIG. 10 is an explanatory diagram of a result of convex decomposition when there is a negative object.

FIG. 11 is a processing flow of the fourth embodiment of the present invention.

FIG. 12 is another schematic processing flow of the interference check preprocessing of the present invention.

FIG. 13 is a flow of a fast convex decomposition basic algorithm.

FIG. 14 is a flow chart of the Merge process.

FIG. 15 is a schematic processing flow of an interference check algorithm.

FIG. 16 is an explanatory diagram of a support function.

FIG. 17 is an explanatory diagram of the closest point search by the Gilbert method.

FIG. 18 is an explanatory diagram of an interference check principle based on the Gilbert method.

FIG. 19 is a flowchart of Merge possibility determination based on the Gilbert method.

FIG. 20 is a flow of merge possibility determination based on the simplified Gilbert method.

FIG. 21 is a processing flow of a first modified example of the present invention.

FIG. 22 is a processing flow of a second modified example of the present invention.

[Explanation of symbols]

1 ... Initial polygon set constituting a non-convex polyhedron 2. Dividing means 3a, 3b .. Polygon set of the first and second groups 4a, 4b .. Means for finding polygon subsets having a convex relationship 5 .. Means 6 ... A plurality of convex polygonal subsets obtained by merging

Claims (9)

[Claims] 1. A method for preprocessing an interference check in which a non-convex polyhedron is divided into convex polyhedrons and interference check of the non-convex polyhedron is performed using the convex polyhedron, and a large number of convex polygons (polygons) forming the non-convex polyhedron Is divided into first and second groups, and a subset of polygons in which the relationship with adjacent polygons is convex is found in each group, and the polygon subset of the first group and the polygon of the second group that have a common boundary edge A method for preprocessing interference check, characterized in that those having a convex relationship with a subset are merged to obtain and output a plurality of new polygon subsets. 2. Whether or not two polygon subsets have a convex relationship is determined by finding all combinations of polygons sharing the boundary ridge line, and when polygons have a convex relationship in all combinations, the first group 2. The polygonal subset and the polygonal subset of the second group are determined to have a convex relationship, and if even one set has a concave relationship, it is determined that the polygonal subset does not have a convex relationship. Interference check pretreatment method. 3. It is checked whether or not a convex object formed by the boundary edges of the polygon subset of the first group and a convex object formed by the polygon subset of the second group interfere with each other. It is judged that there is no boundary edge line, if there is interference, it is judged that there is a common boundary edge line, and it is judged whether or not there is the above convex relationship for two polygon subsets that have a common boundary edge line. The interference check pretreatment method according to claim 2. 4. A plurality of polygon subsets finally obtained are divided into first and second groups, and a subset of polygons having a convex relationship with an adjacent polygon in each group is obtained, and a common boundary is set. A plurality of new polygon subsets are obtained by merging the polygon subsets of the first group and the polygon subset of the second group, which have ridges, in a convex relationship. If the number of calculated polygon subsets is not equal, the above processing is repeated for a plurality of newly obtained polygon subsets,
2. The interference check preprocessing method according to claim 1, wherein each polygon subset obtained last time or this time is output if they are equal. 5. A non-convex polyhedron is divided into convex polyhedrons, and in the interference check preprocessing method for performing interference check of the non-convex polyhedrons using the convex polyhedron, each convex polygon (polygon) forming the non-convex polyhedron is Assuming an inverted shape model by reversing the sign of the normal vector, the polygon set forming the inverted shape model is divided into first and second groups, and in each group, the relationship with adjacent polygons is convex. Whether or not there is a normal vector, the polygons of each group are divided into a plurality of convex polygon subsets, and the polygon subsets of the first group and the polygons of the second group that have a common boundary edge A new polygon sub-set having an inverted shape is obtained by merging those having a convex relationship with the sub-set, and a polygon part having two or more polygons in the polygon sub-set. Are removed from the initial polygon set forming the non-convex polyhedron, the non-inverted polygon set obtained by the removal is divided into two groups, and the relationship with the adjacent polygon is convex in each group. Whether or not it is checked by using the normal vector of each polygon, the polygons of each group are divided into a plurality of polygon subsets having a convex relationship, and the first group of polygon subsets and the second group of polygons having a common boundary edge A polygonal subset of non-inverted convex elements and a polygonal subset of inverted convex elements are merged to obtain a plurality of new non-inverted polygonal subsets. An interference check pre-processing method characterized by outputting each. 6. To determine whether or not two polygon subsets have a convex relationship, all combinations of polygons sharing the boundary ridge line are obtained, and when the polygons have a convex relationship in all combinations, the first group 6. The polygonal subset and the polygonal subset of the second group are determined to be in a convex relationship, and if even one set is in a concave relationship, it is determined that they are not in a convex relationship. Interference check pretreatment method. 7. It is checked whether or not a convex object constituted by the boundary edges of the polygon subset of the first group and a convex object constituted by the polygon subset of the second group interfere with each other. It is judged that there is no boundary edge line, if there is interference, it is judged that there is a common boundary edge line, and it is judged whether or not there is the above convex relationship for two polygon subsets that have a common boundary edge line. The method for preprocessing interference check according to claim 6. 8. A plurality of polygonal subsets of the inverted shape are divided into first and second groups, and in each group, a normal vector of each polygon is determined by determining whether or not the relationship with an adjacent polygon is convex. The polygons of each group are investigated and divided into a plurality of polygon subsets having a convex relationship, and the polygon subset of the first group and the polygon subset of the second group having a common boundary ridge have a convex relationship. To obtain multiple new polygon subsets, and if the number of previously obtained polygon subsets and the number of currently obtained polygon subsets are not equal, 6. The interference check pretreatment method according to claim 5, wherein the above-mentioned processing is repeated until they become equal. 9. The non-inverted polygon sub-sets are divided into first and second groups, and a sub-set of polygons having a convex relationship with an adjacent polygon in each group is obtained, and a common boundary ridge line is obtained. A polygonal subset of the first group and a polygonal subset of the second group having a convex relationship are merged to obtain a plurality of new polygon subsets, and the number of previously obtained polygon subsets and this time are obtained. 6. The interference check preprocessing method according to claim 5, wherein if the number of polygon subsets is not equal, the above-mentioned processing is repeated until it becomes equal for a plurality of newly obtained polygon subsets.