JPH07134735A - Closest point search method and preprocessing method thereof - Google Patents

Abstract

(57) [Summary] [Purpose] Performs the closest point search between convex polyhedrons or non-convex polyhedrons with a small calculation load. [Structure] When the closest points of _two convex polyhedra K ₁ and K ₂ are searched, directed polyhedral structure data is created to represent each convex polyhedron. The closest point search processing unit 15 sequentially obtains the closest point to the difference convex polyhedron which is the difference set (K ₁ −K ₂ ) of the two convex polyhedra K ₁ and K ₂ , and finally obtains each convex polyhedron. K ₁ ,
Find the closest point on K ₂ . In the inner product evaluation executed in the process of obtaining the closest point, the closest point search processing unit 15 determines that the closest point on each convex polyhedron corresponding to the closest point to the difference convex polyhedron that is sequentially obtained is on the grid point. It is determined whether it exists, it exists on the side, or it exists on the polygon, and the grid point used for the inner product evaluation in each case is obtained from the directed graph structure data, and the inner product evaluation is performed using the position vector of the grid point. To do.

Description

Detailed Description of the Invention

[0001]

The present invention relates to collision avoidance and route design (path planning) in the operation of robots and self-propelled vehicles.
It is possible to determine whether or not they are apart from each other, are in contact with each other, or interfere with a shape model (CG model) of a plurality of objects constructed on a computer. In addition, the present invention relates to a closest approach point search method and a preprocessing method therefor capable of calculating the closest approach point, contact point, and distance between objects in real time. The present invention is
It can be applied to various fields such as CAD system for machine design, path generation of mobile robots such as manipulators and self-propelled vehicles, animation creation in multimedia, computer graphics such as game software.

[0002]

2. Description of the Related Art Usually, a robot is operated by remote operation by an operator or by program operation based on data created on a computer. When operating the robot remotely, the operator must operate it while avoiding unexpected collision and interference with other objects surrounding the robot. Further, when the robot is operated by a program, it is necessary to perform path planning in advance so as not to cause collision or interference with an obstacle on a computer. On the other hand, when operating a self-propelled vehicle, the self-propelled vehicle takes in environmental map data of the direction in which it is going to travel through a sensor and runs autonomously while avoiding obstacles, or map information stored in advance on a computer. The program runs according to the path created based on. In these cases as well, as in the case of the robot, sequential collision avoidance and path planning without interference are required.

If the closest point and the distance between the objects can be measured, the robot or the self-propelled vehicle can be moved while avoiding obstacles, or a travel route that does not cause collision or interference can be programmed and programmed. Can drive. Therefore, there is a demand for a method of searching for the closest point between objects in sequential avoidance of collisions in robots and self-propelled vehicles and in advance path planning. That is, when a plurality of objects are present, it is determined whether they are separated from each other, touching, or interfering with each other, and the closest points between the objects (in the case of contacting or interfering, respectively, , A contact point or an interference point) and a method for searching for the closest point that efficiently calculates the distance.

The basic approach to the problem of searching for the closest point is a method in which the shape, position, and orientation data of the target object are loaded into a computer and solved by elementary geometric calculation. Usually, in a graphic simulator used in the CAD field, a planar convex polygon (convex polygon) is used.
Is attached to represent one object. Therefore,
The simplest method of checking the interference state between two objects is to search the closest point between the convex polygons forming each object for all combinations of convex polygons. Specifically, for each convex polygon that forms two objects arbitrarily arranged in space, the closest point is searched for at each lattice point (vertex), side, and face, and the closest distance is calculated. It is to calculate. Of course, when the closest approach distance is zero, it can be said that the two objects are in an interference state. In this way, the number of lattice points that represent the two objects when the M _1, M _2, involves the computational load of _{O (M 1 · M 2)} . Note that O () is a function indicating the order of calculation load.

The development of an algorithm for reducing the calculation load of O (M ₁ · M ₂ ) is mainly studied in the field of computational geometry, and O (MlogM) (M = M ₁ + M ₂ ). An algorithm having the asymptotic property (when M ₁ and M ₂ are very large) has been developed. Although this kind of algorithm is theoretically correct, they all focus on the asymptotic property,
There is no practical discussion on how much the calculation load is reduced when M ₁ and M ₂ have a practical size, and it cannot be said to be a truly practical algorithm. On the other hand, historically,
A method that uses a Voronoi diagram that connects neighboring bisectors between grid points to illustrate the proximity of each grid point, or divides a three-dimensional space into quadrants one after another and occupies the target There is also known a method of searching for the closest point by the oct-tree method that makes a region into a database. All of these methods are effective when the object is static and constant, and are not suitable when the object dynamically changes one after another due to disassembly and assembly.

In order to improve the practicality of the closest point search algorithm, it is necessary to cover the following requirements 1) to 5). 1) Extension to non-convex polyhedron In the closest point search algorithm that has been conventionally developed in computational geometry, the target is limited to the convex polyhedron (see Fig. 69 (a)). However, in reality, many interference problems with the non-convex polyhedron occur as shown in FIG. 69 (b). Therefore, it is necessary to extend the closest point search algorithm to a non-convex polyhedron. A convex polyhedron is a polyhedron in which a line segment connecting any two points inside the polyhedron is included inside the polyhedron.

2) Expansion to a non-single-connected polyhedron In assembling a truss or piping work, it is necessary to consider interference with an object having a hole. FIG. 69 (c) shows the assembly of the truss, where TR is the truss and RBH.
Is a robot hand. 3) Extension to an object with a general free-form surface An object with a general free-form surface is represented on a graphic simulator by combining multiple polygons. FIG. 69 (d) shows an assembly of an antenna having a free-form surface, where AT is an antenna and RBH is a robot hand. In order to deal with the problem of interference with an object having a general free-form surface, it is necessary to increase the number of polygons to improve the accuracy of approximation or to express the surface analytically as a spline curved surface.

4) Responsiveness to environmental fluctuations Objects to be dealt with due to interference problems are not always stationary, and generally the environment dynamically changes through operations such as disassembly, transportation, and assembly. It is often the case that convex polyhedrons are combined to build up a non-convex structure. Also, when each ring of the arm is represented by a convex polyhedron, the arm itself can be regarded as an aggregate of dynamically moving convex polyhedra (generally a non-convex object). At this time, as shown in FIG. 70 (a), when the target object OBJ is grasped by the robot hand RBH at the tip of the arm AM, not only the interference between the hand and the target object but also the arm elbow and the other object OBS. Interference must also be considered.
Practical algorithms must be flexible and able to quickly respond to such dynamic environmental changes.

5) Correspondence to shape change When the target object has flexibility, the shape of the object itself dynamically changes (see FIG. 70 (b)). This can be regarded as a kind of environmental change in 4), but it is more difficult to handle the shape change. For this reason, Professor Gilbert of the University of Michigan has proposed a very practical method (called Gilbert method) for the closest point search problem between convex polyhedra. This Gilbe
According to the rt method, the computational load of the algorithm is O for most combinations of convex polyhedra with very pathological exceptions.
(M ₁ + M ₂ ). The Gilbert method is extended to a non-convex polyhedron by treating the non-convex polyhedron as a set of multiple convex polygons. The Gilbert method will be described in detail below.

Finding the closest point between convex polyhedra by the Gilbert method
Search algorithm (a) Object representation method and distance between objects Consider a convex polyhedron X in 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) .. 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}. "

(B) From the conclusion in the outline (a) of Gilbert's method, the problem of finding the closest point between two convex polyhedra K ₁ and K ₂ is the problem of finding the closest point from one point O to the convex polyhedron K. Be reduced to. 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 support function hx (η) of the equation (6) means that when the vector η is determined as shown in FIG. 71, 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 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.

(C) Closest point search algorithm by Gilbert method 1) Initialization The difference convex polyhedron K ₁ -K _{2 is set} to K with respect to the convex polyhedrons K ₁ and 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, the set V of initial grid points
Let _k (= 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 p (4 or less) of elements, ν _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 The function g _K (x) from R ³ → R is defined as follows. g _K (x) = | x | ² + h _K (−x) In the above equation, the first term on the right side means the square of the distance to the point when the position vector of a 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 _K (−x) is the minimum value of the inner products of the position vector of the lattice points and x. g _K (x)
Is a decision function of the closest point, and if x is the closest point from the origin O to K, then only then, g _K (x) = 0. Incidentally, it can be proved that g _K (x) is the decision function of the closest point, but it is omitted here. For details, see "IEEE JOUNAL OF ROBOT
ICS AND AUTOMATION, VOL.4, NO.2, APRIL 1988, p.193
~ 203 "A Fast Procedure for Computing the Distance
Between Complex Objects in Three-Dimensional Spac
See e. From the above, if ν _k obtained by Eq. (9)
On the other hand, if g _K (ν _k ) = 0 (10), then ν (K) = ν _k is set, and the closest point search processing ends.

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 '. (11) includes a subset V _k of V _k '(including [nu _k), the minimum of the lattice points nearest the origin at the closest point vector [nu _k direction in V _k s _K a (-v _k) Means a set. From the above, (1
If the expression (0) is not established, k is incremented by the expression (11), the process returns to step 2), and the subsequent processing is repeated until the expression (10) is established.

(D) Application of Closest Point Search Algorithm by Gilbert Method In order to deepen the understanding of the above-mentioned Gilbert method, the closest point search algorithm will be described with reference to FIG. In FIG. 72, 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. 72, 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. V ₂ = V ₁ ′ ∪ {s _K (−ν ₁ ′)} = V ₁ ′ ∪ {z ₄ } and V ₁ ′ = {z ₂ , z ₅ }, so 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.

(E) Consideration In the above algorithm, calculation is required in (9), (1
This is the part of equations (0) and (11). First, regarding the expression (9), the meaning of this expression is to calculate the closest point from one point O to a point, an edge, a surface, or a tetrahedron. This part is a part that is not related to the complexity of the convex polyhedron, and can be executed by preparing a subroutine to be described later in advance. Next, regarding the calculation of the equation (10), g _K (ν _k )
When calculating h _K (−ν _k ) of, the decomposition law of Eq. (8) is used. This portion is calculated only by evaluating the inner product (the inner product of the position vector of the base lattice point and ν _k ) of each convex polyhedron K ₁ , K ₂ with respect to the base lattice point, as shown in equation (6). That is, h _K (−ν _k ) is to find the minimum inner product of the position vector of the base lattice point and ν _k , and therefore the calculation load of this part is O (M ₁ + M ₂ ). ..

Equation (11) is s in the process of calculating g _K (ν _k ).
_{Since K} (−ν _k ) is obtained and V _k ′ is automatically obtained from the lemma algorithm described later, the calculation load of this part is M ₁ ,
Negligible constan that does not depend on M ₂
t). The advantage of Gilbert's method is that it reaches the closest point for almost all convex polyhedrons by repeating the above four processes 1) to 4) several times. In many cases, it has been confirmed by numerical experiments that convergence occurs after 3 to 4 iterations. From the above, the essence of the method of searching for the closest point by the Gilbert method can be summarized as follows. That is, the closest point between the _two convex polyhedra K ₁ and K ₂ is the decision function g for the convex polyhedron K = K ₁ −K _2.
It can be obtained by repeatedly applying _K (x) = | x | ² + h _K (−x). Then, the number of iterations converges to 3 to 4 for most convex polyhedra.

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

(F) Gilbert's method lemma In step 2) of the Gilbert method, the closest point from one point (origin O) to the convex polyhedron (point, side, face, tetrahedron) stretched on the lattice points of 4 or less. An algorithm to find the vector was needed. The lemma described below holds for a convex polyhedron stretched by 5 or more lattice points, but is particularly efficient when the number of lattice points is small. 1) Lemma 1 For a lattice point set Y = {y ₁ , y ₂ , ... Ym} ∈ R ³ ,
Let any subset of Y be Ys = {y _i : i∈Is⊆ {1,2,
... m}} and the complement of Is is Is'. At this time, the sequence Δ _i (Ys) is created based on the following law. Δ _i ({y _i }) = 1, _i ∈ Is Δ _j (Ys ∪ {y _j }) = ΣΔ _i (Ys) (y _i y _k −y _i y _j ).
(iεIs) However, k = min {i: iεIs}, jεIs At this time, Ys exists as a subset of Y satisfying the following property. (1) Δ _i (Ys)> 0 for each i where i ∈ Is
(I ∈ Is) (2) For each j with _j ∈ Is, Δ _j (Ys ∪
{Y _j }) ≦ 0 (jεIs)

2) Lemma 2 For a lattice point set Y = {y ₁ , y ₂ , ... Y m} εR ³ ,
When the convex polyhedron stretched by Y is co Y and the vector of the closest point from the origin O to co Y is ν (co Y), ν (co Y)
Is given by the following formula. ν (co Y) = Σλ _i y _i , _i ∈ Is ⊆ {1, 2, ...
m} Here, the proportionality constant λ _i is given by the following equation using Δ _i (Ys) for the subset Ys obtained in Lemma 1. λ _i = Δ _i (Ys) / Δ (Ys), Ys = {y _i : iεIs} Δ (Ys) = ΣΔ _i (Ys) (iεIs) The detailed proof of the above lemma is omitted here, The meaning of the lemma is easy to understand. Apply the above lemma to a tetrahedron. As shown in FIGS. 73 (a) to 73 (d), the closest approach vector between a point O and a tetrahedron is calculated by calculating the lattice points, edges, and
It may exist inside a surface or a tetrahedron. Therefore, if the subset Ys of Y consists of one point,
If it consists of 2 points, it corresponds to the case where the closest point exists on the side if it consists of 3 points, and if it consists of 4 points it corresponds to the case where the origin O exists inside the tetrahedron. .

When actually executing the lemmas 1 and 2, the following algorithm is followed. (g) Gilbert's lemma algorithm For a lattice point set Y = {y ₁ , y ₂ , ... Ym} ∈ R ³ ,
Let Ys = {y _i : iεIs⊆ {1, 2, ...
m}}, the complement of Is is Is'. Also, s = 1, 2,
It is assumed that all subsets of Y are designated by setting σ. At this time, the Gilbert's algorithm 2) is as follows.

2) ₁ 1 → s 2) ₂ If Δ _i (Ys)> 0 (iεIs) for each i in iεIs, and for each j in jεIs, then If Δ _j (Ys∪ {y _j }) ≦ 0 (jεIs), then λ _i = Δ _i (Ys) / Δ (Ys), Ys = {y _i : iεIs} Δ (Ys) = stop the _{ΣΔ i (Ys) (i∈Is)} ν (co Y) = Σλ i y i (i∈Is) (12) ', executing the algorithm 3) subsequent Gilbert method. 2) ₃ However, if the condition of 2) ₂ is not satisfied, s is incremented and step 2) ₂ is executed. That is, steps 2) ₂ and 2) ₃ are repeated until the condition 2) ₂ is satisfied, and 2) ₂
When the condition of is satisfied, ν (co Y) is calculated and then Gilber
Carry out the algorithm of t method 3).

(I) Numerical test The closest point search algorithm by the Gilbert method can be summarized in a subroutine having the following inputs and outputs. Input: Coordinate value of each grid point of the bi-convex polyhedron Output: Coordinate value of the closest point, closest distance FIG. 74 is a numerical test example when the Gilbert method is executed by fault run and applied to various convex polyhedrons. A star mark indicates that two objects are close to each other (free), a white circle indicates that two objects are in contact, and a square black mark indicates that two objects interfere with each other. The computer used is Harris 800, which is slightly faster than the VAX 780 and has the performance of a current PC.

M on the horizontal axis of FIG. 74 is the number of lattice points, and EF on the vertical axis is the amount defined by the following equation. EF = (t _M N _M ＋ t _A N _A ＋ t _D N _D ＋ t _C N _C ) / (t _M ＋ t _A ) (13) Where, N _M is the number of times of addition, N _A is the number of times of addition, and N _D is the number of times of division. ,
N _C is the number of comparison operations, t _M , t _A , t _D , and t _C are the calculation times required for each. In the case of Harris 800, t _M = 3.8 μ
s, t _A = 2.1 μs, t _D = 6.7 μs, t _C = 1.7 μs. EF
The value of does not change greatly by the computer and can be used as a machine-independent index.
In the case of Harris 800, the value obtained by multiplying EF by 6/10 ⁶ is CP
Corresponds to the U scale. Sparc chip (CPU chip)
In the case of a workstation using, you can expect an increase in speed of one digit or more.

(J) Conclusion 1) From the above, the closest point search by the Gilbert method is when the total number of lattice points of two convex polyhedra is M, when they interfere, when they are in contact, when they are free. Each of them has a calculation load proportional to M, and the proportional constant is EF.
The value of / M falls within the range of 14 to 19. 2) When the Gilbert method is applied to two convex polyhedra on a workstation of about 1 M Flops, the total number of grid points is 20.
It is possible to calculate the closest point in a few ms even if it is about zero.

[0033]

As described above, according to the Gilbert method, there is an effect that the search for the closest point between two objects can be executed efficiently in a short time. However, the Gilbert method has the following limits or constraints. 1) Limits of Gilbert's method: Correspondence to continuous search problem Let us consider the case of continuously chasing the closest point between two convex polyhedra. Such a problem of continuously chasing the closest point between two convex polyhedra is called a continuous search problem. As the object moves, the closest point transitions in each convex polyhedron such that it walks from face to side, side to vertex, and vertex to face. Therefore, when the closest point is obtained at a certain time point, the closest point at the next time point should be near the previous closest point. In other words, the search for the closest point is a local problem and should be independent of the complexity of the entire area of the convex polyhedron.

However, in the Gilbert method, since the closest search process considering all grid points in the continuous search problem is performed,
O (M ₁ + M ₂ ) depending on the total number of lattice points M ₁ and M ₂ of the convex polyhedron
There is a problem that the calculation load of is required each time the closest point is searched. Further, since the calculation load is large, there is a problem that the closest approach point search processing cannot be completed in time when the robot and the self-propelled vehicle move at high speed.

2) Constraint condition of Gilbert method: Correspondence to non-convex polyhedron Gilbert method is an algorithm for searching the closest point between convex polyhedra. Therefore, in order to improve the practicality, it is necessary to extend to non-convex polyhedrons, non-singly connected polyhedrons, and objects having free-form surfaces. When the closest point search between non-convex polyhedrons is performed by the Gilbert method, each non-convex polyhedron K ₁ , K ₂ is divided into a plurality of convex polyhedrons A, B; a, b, c as shown in FIG. Then, the closest point search algorithm is applied to all combinations of convex polyhedra, and the shortest one among the obtained closest distances is selected. However, such a method has a problem that the number of combinations increases and the calculation load increases. In view of the above, an object of the present invention is to provide a closest point search method and a preprocessing method thereof capable of executing a continuous search problem between objects at high speed with a small calculation load. Another object of the present invention is to provide a closest point search method and a preprocessing method thereof, which can perform a closest point search between objects, at least one of which is a non-convex polyhedron, at high speed with a small calculation load.

[0036]

FIG. 1 is a diagram for explaining the principle of the present invention. In FIG. 1A, reference numeral 12 denotes a storage unit that stores convex polyhedron data that specifies two target convex polyhedrons,
13 is a directed graph data creation unit that defines a convex polyhedron in a directed graph using convex polyhedron data, 14 is a storage unit that stores directed graph structure data, and 15 is the closest point search process between two objects based on the Gilbert method The closest point search processing unit. In FIG. 1 (b), 22a is a polygon data storage unit that stores all polygon data that covers two target convex polyhedra, and 22b is a near-point linear list storage unit.
Reference numeral 23 has a data structure in which the vertices of each polygon are linked in the first direction (next direction), and a group of vertices connected to each vertex via polygon sides are linked to the vertices in the second direction (branch direction). A proximity point linear list creation unit that creates a proximity point linear list, and 26 is a closest approach point search processing unit.

[0037]

First Closest Point Search Method When searching for the closest points of two convex polyhedra K ₁ and K ₂ , the directed graph data creation unit 13 uses each convex polyhedron data stored in the storage unit 12. Each convex polyhedron K ₁ ,
Create a directed graph structure data representing K ₂ . This directed graph type structure data includes lattice points which are elements of the polygon below each surface polygon (polygon) of the convex polyhedron,
The sides are arranged, and the lattice points are arranged, and the polygons forming the lattice points and the sides are arranged below the sides, respectively. Then, the closest point search processing unit (processor) 15 executes a closest point search process. That is, the closest point to the shape formed by the subset having p points on the difference convex polyhedron, which is the difference set (K ₁ −K ₂ ) of the two convex polyhedra K ₁ and K ₂ , is found. , The inner vector of the position vector of the closest point and the position vector of the lattice point of each convex polyhedron K ₁ , K ₂ is evaluated, and based on the evaluation result, the point of the closest point is a difference convex polyhedron (K ₁ − K ₂ )
Determines whether it matches with the point of closest approach to, and change the subset if they do not match, eventually each convex polyhedrons K ₁ seeking the point of closest approach from the origin to Satotsu polyhedron, closest approach of K ₂ Ask for points.

In the inner product evaluation, the closest point search processing unit 15 determines that the closest point of each convex polyhedron corresponding to the closest point of the shape formed by the subset exists on the grid point or on the side. Yes, or whether it exists on the polygon. The closest point of each convex polyhedron, 1) when present on the grid point, to find the polygons forming the grid point from the directed graph structure data, using the grid point of the polygon for the inner product evaluation,
2) If it exists on the side, the polygons that compose the side are obtained from the directed graph structure data, and the grid points of the polygon are used for the inner product evaluation. 3) If it exists on the polygon, the grid of the polygon Points are used for the inner product evaluation. In this way, the number of grid points applied to the inner product evaluation can be reduced, and the calculation load can be reduced as compared with the conventional example in which the inner product evaluation is applied to all the grid points.

Second Closest Point Search Method A surface polygon (polygon) forming a convex polyhedron is divided into triangles, and the lattice points and sides which are elements of the triangular polygon are arranged below the triangular polygon, and the lattice points are arranged. , Each of the convex polyhedrons is created by creating directed graph structure data in which grid points and triangular polygons forming the sides are arranged below the sides. The closest point search processing unit 15 has the closest point of each convex polyhedron corresponding to the closest point of the shape formed by the subset on the grid point, on the side, or on the triangular polygon. Decide whether to do it. The closest point of each convex polyhedron is 1)
If it exists on a grid point, the triangular polygons that compose the grid point are obtained from the directed graph structure data, and the grid points of the triangular polygon are used for the inner product evaluation. 2) If it exists on the side, the directed graph structure A triangular polygon forming the side is obtained from the data, and the lattice points of the triangular polygon are used for inner product evaluation. 3) When the triangular polygon exists on the triangular polygon, the lattice point of the triangular polygon is used for inner product evaluation. In this way, the number of grid points forming a triangle is the minimum (3
The number of grid points applied to the inner product evaluation can be further reduced as compared with the first closest point searching method, and the calculation load can be reduced.

Third Closest Point Search Method When searching for the closest point between non-convex polyhedra, the smallest convex polyhedron that encloses the non-convex polyhedron (convex hull).
To generate. Then, the directed graph type structural data of the convex hull is created, and the first or second closest point searching method is applied using the directed graph type structural data of the convex hull to search for the closest point between non-convex polyhedra. To do. Also, if the surface convex polygons forming the convex hull match the surface convex polygons of the original non-convex polyhedron, virtuality = 0, otherwise virtuality = 1, and virtuality = When the surface convex polygon of 1 interferes with other objects, the convex hull is released,
Hereafter, the first is applied to a plurality of convex polyhedrons forming the non-convex polyhedron.
Alternatively, the second closest point search process is applied to perform the closest point search between non-convex polyhedra. By doing this, it is possible to search for the closest point between the non-convex polyhedrons, and the calculation load required for the closest point search processing until the surface convex polygon of virtuality = 1 interferes with other objects. Can be reduced. Further, when the surface convex polygon of virtuality = 1 interferes with another object to cancel the convex hull, and when the surface convex polygon no longer interferes with another object, the convex hull is restored to obtain the closest point. If the search process is performed, the calculation load of the closest point search process after restoration can be reduced.

Fourth Closest Point Search Method The vertex coordinates of all polygons covering the convex polyhedron are input, and the near point linear list creation unit 24 sets the first vertex of each polygon.
A closest point linear list having a data structure in which a vertex group linked to a direction (next direction) and connected to each vertex via a polygon edge is linked to the vertex in a second direction (branch direction) Created before executing the search process.
After that, the closest point search processing unit 26 obtains the vertex closest to the latest closest point from the closest point linear list, searches the closest point at the next time from these vertices, and checks the interference. Do.

[0042]

【Example】

 (A) First method for searching for the closest point between convex polyhedra (a) Principle Gilbert's method O (M₁+ M₂) The process that causes the computational load
Is the decision function g in step 3)_K(Ν_k) H_K(-
ν_k) In the inner product calculation. That is, h _K(-Ν
_k) Is from equation (8) h_K(-Ν_k) = H_K1(-Ν_k) + H_K2(-Ν_k) = -Min {x_i・ Ν_k: I = 1, 2, ... M₁} + −min {y_i・ Ν_k: I = 1, 2, ... M₂} (14), so h_KIn the process of evaluating₁, K₂of
Calculate inner product over all grid points to determine minimum
O (M₁+ M₂) Calculation load occurs.

An effective measure for reducing the number of inner product calculations is to divide the convex polyhedrons K ₁ and K ₂ into convex polyhedrons or convex polygons having a smaller number of grid points, and to project the convex polyhedrons or the convex polygons located in the vicinity of the current closest point. This is a method for evaluating the inner product only for a convex polygon. The simplest division method is a method of dividing a convex polyhedron into a set of surface polygons, as shown in FIG. At this time, the closest point in the convex polyhedron can be one of 1) on the lattice point, 2) on the side, and 3) on the surface.

Therefore, the surface polygons whose inner products are evaluated may be limited as follows. That is,
If the closest point is on 1) a grid point, all surface polygons that have that grid point as a vertex, and 2) if they are on a side, a surface polygon that has that side as one side. 3) If it exists on the surface, the surface polygon where the closest point currently exists ... (15) is the surface polygon whose inner product is evaluated. That is, the inner product is evaluated only for the lattice points (vertices) that form the surface polygon shown in 1) to 3) of (15) according to the position where the closest point exists ( ), The decision function g
_It suffices to calculate _K (ν _k ). In this way, the number of grid points required for inner product evaluation is reduced, and the calculation load is reduced.

(B) Data structure of convex polyhedron for closest point search In order to continuously obtain the surface polygons required for inner product evaluation by the above 1) to 3), a data structure defining a convex polyhedron is used. Need some ingenuity. FIG. 3 is an example of the data structure in the case of the hexahedron of FIG. 2, and uses directed graph type structure data.
This directed graph type structured data can be expressed as follows when abstracted. 1) Number the surface polygons that make up the convex polyhedron and assign one polygon node to each. 2) Under each polygon node, a lattice node (Vertex node) for arranging all lattice points and all sides that compose the polygon.
And an edge node. The set of grid points and the set of edges that make up a polygon are
exists as e). 3) Under the grid point node and the edge node, a polygon having those grid points or edges as constituent elements is allocated as a polygon node. If there are multiple polygons, assign them as brother nodes.

(C) Inner product evaluation method of decision function g _K (ν _k ) As described above, when the data structure of the convex polyhedron is created, (1
5) can be expressed as follows. The evaluation of h _K (−ν _k ) in the calculation of the decision function g _K (ν _k ) is as follows: 1) If the closest point is on a grid point, it is placed below the grid point node corresponding to the grid point. Inner product evaluation is performed on the surface polygon points corresponding to all the continuous polygon nodes. 2) When the closest point exists on the side, all the continuous points under the edge node corresponding to the side The inner product is evaluated for the polygonal grid points corresponding to the polygon node. 3) If the closest point is on the surface, the inner product is evaluated for the grid points on the surface.・ ・ ・ (15) ′ If the inner product evaluation is limited to (15) ′, the calculation load of the decision function g _K (ν _k ) is the maximum value of the number of grid points of the surface convex polygon of the convex polyhedron. When it is L, it can be suppressed to O (L) or less.

(D) Closest Point Search Algorithm Employing Inner Product Evaluation Method of the Present Invention FIG. 4 is a flow chart of the closest point search algorithm between two convex polyhedra according to the present invention. First, data that specifies two target convex polyhedra is input (initial input: environment model setting of convex polyhedron). In this case, data specifying each convex polyhedron is input in the following method (see FIG. 5). That is, the polygon number P1i (i = 1, 2, ..., M) is assigned to the surface polygon forming the first convex polyhedron PH1. Then, the i-th polygon number P1i is input, and thereafter, the coordinate values of the lattice points forming the polygon number P1i and the outward normal direction of the polygon number P1i are input, and all polygons P1 are input.
The polygon number for 1i (i = 1, 2, ... M),
Enter the grid point coordinate values and the outward normal direction. The coordinate values of the lattice points forming the polygon are input clockwise toward the outward normal vector.

Thereafter, similarly, polygon numbers P2i (i = 1, 2,
... n) is attached. Then, the i-th polygon number P2i
Then, the coordinate values of the lattice points forming the polygon number P2i and the outward normal direction of the polygon number P2i are input, and all polygons P2i (i = 1, 2, ... N) are input.
For, the polygon number, the coordinate value of the grid point, and the outward normal direction are input (above step 101). When the input of the data specifying each convex polyhedron is completed, the directed graph structure data is created based on the input data (step 10).
2). When the creation of the directed graph structure data is completed, the Gilbert method is applied to the convex polyhedra PH1 and PH2. First, the initial lattice point set V _k (k = 0) is determined (step 103), and the closest point vector ν _k is calculated for the initial lattice point set V ₀ and output (step 104).

Then, it is checked whether the closest point on each convex polyhedron PH1, PH2 corresponding to the closest point is on a grid point, on a side or on a surface, and based on the existing position, (15) ' determining the grid points to be used for the inner product evaluation, the decision function g _K
(Ν _k ) is calculated (step 105). Incidentally, the convex polyhedron P
Let x _{1i be} the grid point on H1 and x be the grid point on the convex polyhedron PH2.
Assuming _2i , the expression (12) ′ is ν (co Y) = Σλ _i y _i (iεIs) = Σλ _i (x _1i −x _2i ) (iεIs) = Σλ _i x _1i −Σλ _i x _2i ( i∈Is) (12) ″. The first term on the right side of (12) ″ is the position vector of the closest point on the convex polyhedron PH1, and the second term on the right side is the convex polyhedron PH1.
2 is the position vector of the closest point on 2. Therefore, in the process of computing the closest point vector ν _k ,
The closest point on each convex polyhedron PH1, PH2 corresponding to the closest point vector can be obtained by calculating the term and the second term on the right side.

Once the decision function is obtained, g_K(Ν_k) = 0
Check if there is any (step 106), g _K(Ν_k) = 0
If so, the closest point search ends. But g_K(Ν_k) Is 0
If not, k is incremented and the next grid point set V₁
Output the closest point vector for (step 10
7). After that, if you repeat the processing after step 105,
Finally g_K(Ν_k) = 0, the closest distance and the closest point are
I want it. That is, the difference between the two convex polyhedrons PH1 and PH2
The vector of the closest point to the set convex polyhedron is calculated by Eq. (12) '.
Therefore, the distance from the origin O to the closest point is the closest distance.
Becomes Also, at this time, in the first term and the second term on the right side of the equation (12) ″,
The closest point on each convex polyhedron PH1 and PH2 can be found from
You can

(E) Configuration diagram of the closest point search device adopting the inner product evaluation method of the present invention FIG. 6 is a configuration diagram of the closest point search device between two convex polyhedrons. In the figure, 11 is an input unit for inputting data (see FIG. 5) that specifies two target convex polyhedrons, 12 is a storage unit for storing the input convex polyhedron data, and 13 is convex polyhedron data for each convex polyhedron. A directed graph structure data creating unit that creates directed graph structure data using 14; a storage unit 14 that stores directed graph structure data; The search processing unit 16 reads the grid points for inner product evaluation corresponding to the position (grid point, side, surface) where the closest point exists from the directed graph structure data storage unit 14 and inputs it to the closest point search processing unit 15. This is a grid point reading unit for inner product evaluation.

From the input unit 11, connect the convex polyhedrons PH1 and PH2
The data to be specified is input and stored in the storage unit 12. Directed
The graph type structure data creation unit 13 is based on the input data.
Create directed graph type structure data and store it in the storage unit 14.
It Closest when creation of directed graph structure data is completed
The point search processing unit 15 applies Gi to the convex polyhedrons PH1 and PH2.
The lbert method is applied. First, the initial grid point set V_k(K =
0) is determined, and the initial grid point set V₀About the closest
Cutle ν_kTo calculate. Then, the closest vector ν _kIn response
Find the closest point on each convex polyhedron, and find the closest point
Check whether the point is on the grid point, on the side, or on the surface,
Read out existing positions (grid points, sides, faces) for inner product evaluation grid points
It is input to the output section 16. The reading unit 16 is at the closest point position.
Directed graph of grid points used for inner product evaluation
Read from the type structure data storage unit 14 and search for the closest point
Input to the section 15. The closest point search processing unit 15 is input
The inner product is evaluated using the determined grid points to determine the decision function g
_K(Ν_k) Is calculated. After that, if the decision function is obtained,
g_K(Ν_k) = 0 is checked, g_K(Ν_k) = 0
If the closest point search is completed, the closest distance and the closest point are output.
To do. But g_K(Ν_k) Is not 0, ink k
The next grid point set V₁About the closest point
Output toll. After that, the same process is performed and finally
To g_K(Ν_k) = 0, the closest distance and the closest point are output
To be done. If the convex polyhedrons PH1 and PH2 move,
Based on the movement data for each fixed time,
The grid point position is obtained and the above processing is performed.

(B) Second Method for Searching for Closest Point between Convex Polyhedra (a) Principle In the first method for searching for the closest point, the convex polyhedron that is the target object is divided into surface convex polygons that respectively enclose it. , The calculation load was on the order of the number of grid points of the convex polygon. When the idea of the first closest approach search method is further investigated, it is clear that if the surface of the convex polygon is covered with triangular polygons, the number of times of one inner product evaluation will be minimized. Figure 7 (a)
FIG. 4 is an explanatory diagram of a state in which the closest point to the convex polyhedron K moves along the surface polygon along with the movement of the origin O. Origin O
The closest point S is a convex polygon P1 → convex polygon P according to the movement of
2 → Transition continuously on the convex polygon P3. Therefore,
If the convex polygon is divided into triangles Tij as shown in FIG. 7 (b), the closest point S becomes a triangle T11 → as the origin O moves.
T12 → T21 → T22 → T23 → T24 → T25 → T
It will continuously change from 26 to T31.

Therefore, there is no problem even if all the surface convex polygons forming the convex polyhedron are divided into triangles and the first closest search processing is performed. Then, by dividing into triangles, the number of times of one inner product evaluation can be reduced. For example, assuming that the closest point S'is present on the side E11 in FIGS. 7A and 7B, in the case of FIG. 7A, the grid points used for the inner product evaluation are V1 to V6. Although there are six, four in the case of FIG. 7B, V1, V3, V4, and V6 are sufficient, and the number of times of one inner product evaluation can be reduced. From the above, if the target convex polyhedron is preprocessed and the surface convex polygons are all divided into triangular polygons, then the calculation load when continuously evaluating g _K (ν _k ) is Can be kept below a certain value regardless of the complexity of the convex polyhedron.

As a method of dividing an arbitrary convex polygon into triangular polygons, some algorithms are known in the field of computational geometry. The best known method is triangulation, which uses dynamic programming to minimize the sum of chord lengths. FIG. 8 shows an example thereof. The strings are L1 to L6
Is a line segment for dividing into triangles. The calculation load of this algorithm is O (n ³ ) where n is the number of grid points of the first polygon. Regarding algorithms for polygons into triangles, Tetsuo Asano "Computational Geometry" (Asakura Shoten), Te. Asano, Ta. Asano and Y. Ohsuga: "Partitio
ning a Polygonal Region into a Minimum Number of T
riangles ", Trans. IECE of Japan, vol.E67, pp.232〜
233, 1984.

From the above, the method for dealing with the continuous search problem for the closest point (second closest point search method) can be summarized as follows. 1) Preprocessing 1: Triangulation algorithm is applied to each surface convex polygon that wraps the target convex polyhedron (Triangulation algorithm) 2) Preprocessing 2: Using a triangle, a directed graph as in the first closest point search method Create type structure data. 3) Inner product evaluation: Limit the range of inner product evaluation at g _K (ν _k ) according to (15) ′.

(B) Second Closest Point Search Algorithm of the Present Invention FIG. 9 is a flow chart of the closest approach point search algorithm according to the second closest approach point search method of the present invention. First, data that specifies two target convex polyhedra is input (initial input: environment model setting of convex polyhedron). Data specifying each convex polyhedron is input in the following method (see FIG. 5). That is,
The number P1 is assigned to the surface polygon forming the first convex polyhedron PH1.
i (i = 1, 2, ... M) is attached. Then, the i-th polygon number P1i is input, and thereafter, the coordinate values of the lattice points forming the polygon of the number P1i and the outward normal direction of the polygon are input, and similarly all polygons P1i (i =
1, 2, ..., M), the polygon number, the grid point coordinate value, and the outward normal direction are input. The coordinate values of the lattice points forming the polygon are input clockwise toward the outward normal vector. Similarly, a polygon number P2i (i = 1, 2, ...) Is assigned to the surface polygon forming the second convex polyhedron PH2.
・ ・ Add n). Next, the i-th polygon number P2i is input, and thereafter, the coordinate values of the lattice points forming the polygon number P2i and the outward normal direction of the polygon number P2i are input, and all polygons P2i (i = 1, 2 ,. .. for n), the polygon number, grid point coordinate value, and outward normal direction are input (above step 201).

When the input of the data specifying each convex polyhedron is completed, the surface convex polygon forming the convex polyhedron is divided into triangles based on the input data, and the polygon number T is assigned to each triangle.
ij is added (step 202). Then, using the obtained triangle as a polygon node, directed graph type structure data is created in the same manner as in the first closest point searching method (step 203). When the data creation of the directed graph type structure is completed, the Gilbert method is applied to the convex polyhedrons PH1 and PH2. First, the initial grid point set V _k (k = 0) is determined (step 204), and the closest point vector ν _k is calculated and output for the initial grid point set V ₀ (step 20).
5).

Then, the closest point vector ν_kAccording to each
Find the closest points on the convex polyhedron, and calculate the closest points
Examine whether it exists on the child point, on the side, or on the surface, and
The grid points used for the inner product evaluation are determined by (15) ′
Determine and judge function g_K(Ν_k) Is calculated (step 20)
6). If the decision function is obtained, g_K(Ν_k) = 0
Examine (step 207), g _K(Ν_k) = 0 is the closest
The near point search ends. But g_K(Ν_k) Must be 0
If k is incremented, the next grid point set V₁About
And outputs the closest point vector (step 208). Since
If you repeat the processing after step 105, g
_K(Ν_k) = 0, and the closest distance and the closest point are obtained.
It should be noted that if the convex polyhedrons PH1 and PH2 move, then at predetermined time intervals.
Position of each convex polyhedron after movement based on the movement data
Then, the above processing is performed.

(C) Configuration diagram of the second closest point searching device of the present invention FIG. 10 is a configuration diagram of a device that realizes the second closest point searching method of the present invention. Are given the same reference numerals. 6 is different from FIG. 6 in that 1) a triangle dividing unit 17 that divides a surface convex polygon forming the convex polyhedron into triangles based on convex polyhedron data that specifies the convex polyhedron, 2) directed graph type The structure data creation unit 13 is a point that creates the directed graph type structure data using each triangle as a polygon node and stores it in the storage unit 14.

(D) Effects of the second closest approach point searching method According to the second closest approach point searching method, the following advantages 1) and 2) are obtained. 1) High speed: When chasing the closest point continuously, the calculation load can be made almost constant regardless of the complexity of the target polyhedron except for the time required for initialization. The constant value is almost equal to the search time of the closest point between the triangular polygons. 2) Application to free-form surface: When a free-form surface is represented by combining triangular polygons, the time to search for the closest point is always constant even if the number of polygons is increased to improve the accuracy of the expression.

(C) First Method for Searching for Closest Point between Non-Convex Polyhedra (a) Principle The basic principle for extending the Gilbert method to a non-convex polyhedron is to define a non-convex polyhedron as a set of convex polyhedra. The goal is to reduce the number of convex polyhedron combinations that must be checked for interference when captured. Of course, the Gilbert method is used to check the interference between convex polyhedra. To reduce the number of convex polyhedra, merging (mergin
Introduce the concept of g). The merging of object A and object B is the smallest convex object (Copnvex hull) that includes A and B.
Is to configure. In FIG. 11, a non-convex polyhedron K is divided into two convex polyhedrons A and B, and A and B are subjected to merging processing.
It is the example which constituted the minimum convex object (convex hull) C containing. When the convex hull is generated, the interference check of the non-convex polyhedron results in the interference check of the convex hulls (the convex polyhedrons), and the first closest point search method of the present invention can be applied.

In constructing the convex hull C, an index called virtuality is introduced. The virtuality is a flag for identifying a virtual polygon generated by merging of a plurality of convex polyhedra. In the example of FIG. 11, the virtuality is “for a polygon (polygons 4, 5, 6) that straddles two existing convex polyhedra (rectangular solids) A and B.
1 ", and for other polygons that actually exist, the virtuality is" 0. "A convex hull is created by merging, and the first closest point search method is applied to the convex hull. 12 creates the effective graph type structural data of the convex hull, and Fig. 12 shows the directed graph type structural data of the convex hull shown in Fig. 11, in which the surface polygon polygons 1, 2, ... of the convex hull are polygon nodes. A lattice point node and an edge node are arranged below, and a polygon node is arranged below each lattice point node and an edge node, and a virtuality is added to the polygon.

(B) Merging Algorithm FIG. 13 is a flowchart of the merging algorithm. The target non-convex polyhedron is divided into two or more convex polyhedra, and the data specifying each convex polyhedron is input (initial input: environment model setting of convex polyhedron). That is, the first convex polyhedron PH1
The polygon number P1i (i = 1,
2, ... m). Then, the i-th polygon number P
1i, and then the coordinate values of the lattice points forming the polygon number P1i and the outward normal direction of the polygon number P1i are input, and all polygons P1i (i = 1, 2, ...
For m), enter the polygon number, grid point coordinate value, and outward normal direction. Thereafter, similarly, polygon numbers P2i (i = 1, 1) are assigned to the surface polygons forming the other convex polyhedron PH2.
2, ... n), all polygons P2i (i = 1, 1,
2, ... n), polygon number, grid point coordinate value,
The outward normal direction is input (above step 301).

When the input of the data for specifying each convex polyhedron is completed, the data of the directed graph type structure is created based on the input data (step 302). Then, the smallest convex hull PH (1,2) including the respective convex polyhedrons PH1, PH2 is generated (step 303). Then, the polygon number P _{PH (1,2) i} (i = 1,2, ... r) is added to the surface polygon forming the convex hull PH (1,2).
After inputting the i-th polygon number P _{PH (1,2) i} , the coordinate values of the lattice points forming the i-th polygon, the virtuality of the polygon, and the outward normal direction are obtained and stored (see FIG. 14). ). After that, similarly, all polygons P _{PH (1,2 ) i} (i = 1,2,
... r), the polygon number, the grid point coordinate value, and the virtuality outward normal direction are obtained, and the directed graph type structural data of the convex hull is created and stored in the memory. If the polygon P _{PH (1,2) i} includes both grid points of the convex polyhedron PH1 and PH2, the virtuality is “1”, and if only one grid point is included, the virtuality is “1”. It becomes 0 "(the above steps 304 and 305).

The merging algorithm is an algorithm which creates a convex hull from a plurality of convex polyhedra and creates directed graph structure data. Algorithms for creating convex hulls are well known in computational geometry. For a three-dimensional convex hull, the computational load is O (M
-Log M) algorithm is known. For example, F.
P. Preparata and SJ Hong, "Convex hulls of finit
e sets of points intwo and three dimensions ", Com
m. ACM 2 (20), pp.87-93, 1977. The merging algorithm causes convex polyhedrons that are relatively stationary to act on each other, and cancels merging when a polygon of virtuality "1" contacts or collides with another object. As a result, thereafter, the closest point search processing is performed on the set state of the lower convex polyhedra. In addition, after the merging is released (after the convex hull is released), when the interference with other objects does not occur for a certain period of time, the convex hull decomposed by the interference is recovered by a recovery algorithm (described later).

(C) Activation of the merging algorithm The merging algorithm is caused to act offline on the target object in the initial setting, and when the environment starts to change dynamically, that is, a convex polyhedron in the environment. If is started, the merging process is temporarily stopped while maintaining the current state, and an interference check is performed. Then, when the environment stops, merging processing is executed to create a convex hull after the environment change and to create a directed graph structure data of the convex hull. FIG. 15 is an explanatory diagram of the merging process by the processor in consideration of the above. A flag ms (i) for monitoring the static motion of the convex hull is prepared for all convex hulls. If the static / moving flag ms (i) = "1", move, ms (i)
When = “0”, it is static, and i covers the entire convex hull.

As a task of the processor, all m
By the state monitoring task Task1 that monitors the value of s (i) to monitor the static state of the convex hull, and if any ms (i) is “1”, the above first closest point search method Task2 (interference check task) that executes other processes for interference check, and Task3 (merging task that executes merging process when all ms (i) = "0", that is, when all convex hulls are stationary. ). The static state of all convex hulls is monitored by a robot controller (not shown), and ms (i) = "1" or ms (i) is stored in the memory MEM.
It is written as "0". Status monitoring task Task
1 monitors the content of ms (i), and when all are "0", the merging task Task3 is activated to execute a merging process to create a convex hull and directed graph structure data. The merging task Task3 is stopped after forming one convex hull, and waits for the next activation instruction. On the other hand, either m
When s (i) is “1”, in other words, when any convex hull is moving, the interference check task Task2
Performs the interference check and other processing by the first closest point search method. After that, the above operation is repeated and the interference check is executed.

The above is the case of executing the merging process, the interference check process, etc. by switching the task.
It is also possible to perform merging processing sequentially by using an ile statement. FIG. 16 is an explanatory diagram of a case where the merging process is executed using the While statement. While
In the sentence, ms (i) of all convex hulls is monitored for "0", and if all "0", the merging process is executed to create one convex hull (step 401). After that, Wh
The ile statement is exited, interference check and other processing are executed (step 402), and the While statement is executed again.
After that, the merging process and the interference check process are constantly executed repeatedly.

When the environment changes dynamically, for example, as shown in FIG.
When the robot arm AM passes through the arch AC, which is a non-convex polyhedron, and grabs the object OB on the opposite side, as shown in FIG. In this case, the merging is released when the robot arm AM comes into contact with the convex polygon of the convex hull virtuality "1". After that, the individual convex polyhedrons AC1 to AC1 that form the robot arm AM and the arch AC1.
An interference check with AC3 is performed, and the robot arm reaches the object OB so as not to contact the arch AC, grasps the object, and carries it to the target location. The convex hull from which the merging has been canceled is restored by the recovery algorithm described below. Fig. 18 (a) shows a convex hull CH on the work table BS and arch AC.
18B is an example in which the arch AC and the object O are generated.
This is an example of the case where convex hulls CH2 and CH3 are generated for B respectively, and the robot arm AM has a convex hull CH1 composed of a work table BS and an arch AC, and a convex hull formed of an arch as shown in FIG. 18 (c). Object OB pierced by parcel CH2 one after another
Reach the target object, grasp the object and carry it to the desired location.

(D) Recovery Algorithm The convex hull decomposed by interference is recovered for a certain period of time when it does not interfere with other objects. The recovery process operates only on the convex hull in which the merging state data structure remains. Therefore, the convex polyhedron set in which the relative positional relationship has moved and the data structure of the original convex hull is lost is not recovered by the recovery process, and a new convex hull is constructed by applying the merging algorithm.

FIG. 19 is an explanatory diagram of merging processing and recovery processing by the processor. A flag ms (i) for monitoring the static motion of the convex hull is prepared for all convex hulls. If the static / moving flag ms (i) = "1", move, ms (i)
When = “0”, it is static, and i covers the entire convex hull. As a task of the processor, a status monitoring task Tas that constantly monitors all ms (i) values to monitor the static state of the convex hull
k1 and Task2 (interference check / recovery task) that executes interference check processing, recovery processing, and other processing by the first closest point search method when any ms (i) is “1”, and When ms (i) = “0”, that is, when all the convex hulls are stationary, there is Task3 (merging task) for executing the merging process.

The static / moving state of all the convex hulls is monitored by a robot controller (not shown), and ms (i) = ”is stored in the memory MEM.
It is written as 1 ”or ms (i) =“ 0 ”. The state monitoring task Task1 monitors the contents of ms (i), and if all“ 0 ”, the merging task Task3 is activated. The merging task Task3 is merging. By executing the processing, a convex hull is created, and directed graph type structure data is created.The merging task Task3 stops after forming one convex hull, and waits for the next activation instruction.
When s (i) is “1”, in other words, when any convex hull is moving, the interference check task Task2
Performs the interference check by the first closest point searching method and also executes the recovery process and other processes. After that, the above operation is repeated and the interference check is executed.

The recovery process is a convex hull virtuality "
When the convex polygon of 1 "comes into contact with another object and the merging is released, it is monitored whether the convex hull does not interfere with the object,
When the interference does not occur and the interference does not occur for a predetermined time continuously, the convex hull is restored. In the example of FIG. 17, when the robot arm AM grips the object OB and passes through the arch AC, the convex hull and the arm do not interfere with each other.

Although the above is the case where the recovery processing and the like is executed by switching the tasks, the recovery processing can be performed sequentially by using the While statement. Figure 2
Reference numeral 0 is an explanatory diagram in the case where the recovery process is executed using the While statement. M of all convex hulls in a While sentence
It is monitored whether s (i) is "0", and if all are "0", a merging process is executed to create one convex hull (step 501). Then, the While statement is exited, interference check processing, recovery processing, and other processing are executed (step 502), and the While statement is executed again. After that, the merging process, the interference check process, and the recovery process are constantly and repeatedly executed.

(E) Overall Process of Searching for Closest Point between Non-Convex Polyhedra FIG. 21 is an overall process flow diagram for searching for a closest point between non-convex polyhedrons. Input the data that specifies the target non-convex polyhedron (initial input: environment model setting). ... Step 601 Then, the non-convex polyhedron is divided into convex polyhedrons, and each convex polyhedron P is divided.
Create a directed graph structure data of Hi. Further, the convex hull is generated by the merging process, and the directed graph structure data of the convex hull is created (step 602). When the above initialization process is completed, a first closest point search process (interference check) process is executed (step 603). Next, it is checked whether they interfere (step 604). If they interfere, it is checked whether the virtuality = "1" portion interferes (step 605). If the virtuality = "0", the movement is immediately stopped ( If the virtuality is "1" (step 606), the merging is canceled (step 607), and the process returns to step 603. After that, the closest point search process is executed for each convex polyhedron forming the non-convex polyhedron until the convex hull is recovered.

On the other hand, if there is no interference at step 604, recovery processing is executed (step 60).
6). In the recovery process, it is checked whether or not there is a convex hull in which merging has been canceled, and if it exists, it is checked whether or not it interferes with another object, and if it does not interfere, the non-interference time is counted. Then, if the non-interference time of the convex hull in which the merging is canceled is equal to or longer than the set value, the convex hull is restored. However, if it interferes with another object or if the non-interference time is not longer than the set value, the convex hull is not restored and the next step is executed. When the relative positional relationship of the parts forming the convex hull moves and the original convex hull data is lost, the convex hull is not recovered. Then, it is checked whether or not all the parts of the convex hull are stationary (step 609). If not stationary, the process returns to step 603 to repeat the subsequent processes, and if stationary, the merging process is executed and a new process is performed. A convex hull is created (step 610), and then the process returns to step 603 to repeat the subsequent processes.

(F) Configuration of Closest Point Searching Device between Non-Convex Polyhedrons FIG. 22 is a configuration diagram of a closest approaching point searching device between non-convex polyhedrons. Reference numeral 21 is an input unit for inputting data for identifying a target non-convex polyhedron, 22 is a storage unit for storing the input non-convex polyhedron data, and 23 is a non-convex polyhedron divided into a plurality of convex polyhedra. A convex polyhedron division / directed graph creation unit that creates directed graph structure data for each, 24 is a convex hull of a non-convex polyhedron, and a convex hull creation / directed graph creation unit that creates directed graph structure data of the convex hull is A storage unit that stores the directed graph structure data CVD of each convex polyhedron and the directed graph structure data CHD of the convex hull, 26 is a processor that performs state monitoring, interference check, merging, and recovery processing, and 27 is sent from the robot controller. A memory that stores the static / moving flag ms (i) and the position data of each object, and 28 is a memory that stores whether or not the merging of the convex hull is released for each convex hull. That.

Data for specifying the target non-convex polyhedron is input from the input unit 21 and stored in the memory 22. The convex polyhedron division / directed graph creation unit 23 divides the non-convex polyhedron into convex polyhedra, and the directed graph structure data CVD of each convex polyhedron.
Is created and stored in the memory 25. Further, the convex hull creating / directed graph creating unit 24 creates a convex hull by merging processing, creates the directed graph type structure data CHD of the convex hull, and stores it in the memory 25.

When the above initialization processing is completed, the processor 26 executes the above-mentioned first closest point search processing (interference check) processing using the directed graph type structure data of the convex hull. For moving objects, calculate the grid point position based on the movement data input from the robot controller,
The closest point search process is performed based on the grid point position. Convex hull (virtuality = "1") by the closest point search process
When the interference with is detected, the merging of the convex hull is released, and the release flag FR = “1” is stored in the memory 28.
Thereafter, the processor 26 refers to the release flag FR to check whether the convex hull has been recovered, and if not recovered, the closest point search process is performed using the directed flag structure data of each convex polyhedron forming the non-convex polyhedron. Run. Further, the processor 26 executes the recovery process unless it interferes with the convex hull (virtuality = “1”).

In the recovery process, the cancellation flag memory 28 is referred to check whether or not there is a convex hull in which the merging has been cancelled. For example, the non-interference time T is measured. Then, if the non-interference time T of the convex hull in which the merging is canceled is equal to or longer than the set value, the convex hull is restored. That is, the release flag FR is set to 0. However, the convex hull is not restored when it interferes with another object or when the non-interference time is not longer than the set value. Then, referring to the stationary flag ms (i) input from the robot controller, it is checked whether all the convex hulls are stationary, and if they are not stationary, the interference check is repeated. When stationary, when the relative positional relationship of the convex polyhedrons forming the non-convex polyhedron has changed, merging processing is executed to create a new convex hull, which is stored in the memory 25. Repeat the process.

As described above, according to the method of searching for the closest point between non-convex polyhedra of the present invention, a convex hull is created, directed graph type structural data of the convex hull is created, and based on the directed graph type structural data of the convex hull. Since the closest point search process is performed,
The number of combinations of convex polyhedra can be significantly reduced.
Also, if the convex hull collapses due to a dynamic change in the environment, then the original convex hull is restored for a certain period of time without interference with other objects, and the number of convex polyhedra is minimized. It can be held and the calculation load can be realized.

(D) First method in continuous search for closest points between non-convex polyhedrons (a) Principle In the "continuous search problem for closest points" in which the closest points between a plurality of non-convex polyhedrons are continuously tracked , We perform merging processing on each non-convex polyhedron, and reduce and solve the continuous problem of the closest points between formally convex polyhedra. At this time, for each convex polyhedron obtained by merging, number the surface convex polygons that form the convex polyhedron, and register the grid points, edges, and convex polygons that are located near each convex polygon. Creates a directed graph type structure data and sets the calculation load of the closest point search to the order of the maximum value of the number of grid points of the surface polygon.
(L) Keep below. For merging, we will introduce an index called virtuality. What is virtuality?
In the surface polygon of the convex polyhedron obtained in the merging process, virtuality = 0 if it matches the original surface polygon of the non-convex polyhedron, and virtuality = 1 if they do not match.

When interference with a convex polygon of virtuality = 1 occurs, merging is canceled and the first non-convex polyhedron of the present invention is applied to the combination of convex polyhedrons constituting the original non-convex polyhedron. The nearest point search method of is applied.
The rules for canceling merging are as follows. 1) If a polygon with virtuality = 1 (a component of convex hull A) and a polygon with virtuality = 0 (a component of convex hull B) interfere with each other, then a convex hull A having a polygon with virtuality = 1 is selected. To release. 2) If a polygon with virtuality = 1 (component of convex hull A) and a polygon with virtuality = 1 (component of convex hull B) interfere with each other, a configuration when the convex hull is decomposed into a convex polyhedron Release the convex hull with the smaller number. 3) If polygons with virtuality = 0 interfere with each other, neither convex hull is released.

As shown in FIG. 23, if the convex hull A and the convex hull B interfere with each other (see (b)) and the convex hull A is released and a set DA (Decomposed A) of constituent convex polyhedra appears ((( See c))
The first closest point search method of the present invention in the convex polyhedron between the set DA and the convex hull B is applied. The algorithm in this case is as follows. (b) Closest point search algorithm between convex polyhedron set and convex hull 1) PA (Virt
uality (PA) = 1). At this time, each side of the interference surface PA is composed of the element Edge (DA, PA) of the set DA and the side of the virtuality = 1, and the lattice points of the interference surface PA are the elements Verte of the set DA.
It is composed of x (DA, PA).

2) Constitution Checking the interference between the set of convex polyhedra DA and the convex hull B is Edge (DA, PA), Vertex (DA, PA) and the convex hull B.
This is performed by applying the first closest point search method of the present invention in a convex polyhedron. That is, Edge (DA, PA),
Each convex polyhedron (A ′, which forms a non-convex polyhedron) is a surface convex polygon of DA including Vertex (DA, PA) (see the hatched portion in (c)).
A ″) is searched from the directed graph type structure data. Then, the first closest approach point search method is applied in parallel between the surface polygon and the convex hull B that are respectively obtained to perform interference check ((d)). 3) If you get out of the state of interference with the convex polygon with virtuality = 1, the convex hull released by the recovery process is recovered, and the closest point search process is applied to the convex hull (see (e)). By the process of 2), the convex polyhedron A ′ which is the target of the closest point search,
The number of faces of A ″ can be reduced (one face for the convex polyhedron A ′ and two faces for the convex polyhedron A ″), and the calculation load of the closest point search processing can be reduced.

(C) Flow of the closest point continuous search process FIG. 24 is a process flow diagram of the closest point continuous search process between non-convex polyhedra. Input the data that specifies the target non-convex polyhedron (initial input: environment model setting). ... Step 701 Then, the non-convex polyhedron is divided into convex polyhedra, and each convex polyhedron P is divided.
Create a directed graph structure data of Hi. Further, the convex hull is generated by the merging process, and the directed graph structure data of the convex hull is created (step 702). When the above initialization processing is completed, the first aspect of the present invention for the convex polyhedron
The closest point search process (interference check) is executed (step 703). Next, it is checked whether they interfere with each other (step 704), and if they do interfere with each other, it is checked whether polygons with virtuality = 0 interfere with each other (step 705), and YES.
If so, neither convex hull is released and the process is stopped, and the next instruction is awaited. However, if the polygons with virtuality = 0 do not interfere with each other, it is checked whether the polygon with virtuality = 1 (component of convex hull A) and the polygon with virtuality = 0 (component of convex hull B) interfere with each other. (Step 706).

If YES, the convex hull A having a polygon of virtuality = 1 is released (step 707). NO
In other words, in other words, if the polygon with virtuality = 1 (component of convex hull A) and the polygon with virtuality = 1 (component of convex hull B) interfere, decompose the convex hull into a convex polyhedron. The convex hull having the smaller number of constituent convex polyhedrons is obtained (step 708) and the convex hull is canceled (step 707). Then, the surface convex polygons of the set DA including Edge (DA, PA) and Vertex (DA, PA) of the interference surface PA are retrieved from the directed graph structure data of each convex polyhedron and passed to the processor (step 7).
09). After that, the processor finds the surface polygon and the convex hull B
In parallel with this, the first closest approach point search method is applied to perform interference check (step 703).

On the other hand, in step 704, if there is no interference between the objects, recovery processing is executed (step 710). In the recovery process, it is checked whether or not there is a convex hull in which merging has been canceled, and if it exists, it is checked whether or not it interferes with another object, and if it does not interfere, the non-interference time is counted. Then, if the non-interference time of the convex hull in which the merging is canceled is equal to or longer than the set value, the convex hull is restored. However, if it interferes with another object or if the non-interference time is not longer than the set value, the convex hull is not restored and the next step is executed. After that, the process returns to step 703 and the subsequent processes are repeated. Then, it is checked whether or not all the parts of the convex hull are stationary (step 711). If not stationary, the process returns to step 703 to repeat the subsequent processes, and if stationary, the merging process is executed to newly execute. A convex hull is created (step 712), and then the process returns to step 703 to repeat the subsequent processing.

(E) Second method in continuous search for closest points between non-convex polyhedrons (a) Principle In the "continuous search problem for closest points" in which the closest points between a plurality of non-convex polyhedrons are continuously tracked , We perform merging processing on each non-convex polyhedron, and reduce and solve the continuous problem of the closest points between formally convex polyhedra. At this time, the second closest point searching method of the present invention is applied. That is, for each convex polyhedron obtained by merging, triangulation (Triangulat) into each surface convex polygon enclosing the convex polyhedron.
Ion) and takes a directed graph type data structure for the result of triangulation to keep the calculation load of the closest point search constant regardless of the complexity of the target convex polyhedron. For merging, we will introduce an index called virtuality.
In the surface polygon of the convex polyhedron obtained in the process of merging, the virtuality is set to virtuality = 0 when it matches the surface polygon of the original non-convex polyhedron, and virtuality = 1 when they do not match.

When interference with a triangular polygon of virtuality = 1 occurs, merging is canceled (convex hull is canceled), and the combination of convex polyhedrons constituting the original non-convex polyhedron of the present invention is canceled. The second closest point search method is applied. The rules for canceling merging are as follows. 1) If a triangular polygon with a virtuality = 1 (a component of convex hull A) and a triangular polygon with a virtuality = 0 (a component of convex hull B) interfere with each other, a convex hull A having a triangular polygon with virtuality = 1 is created. To release. 2) If the triangular polygon with virtuality = 1 (component of convex hull A) and the triangular polygon with virtuality = 1 (component of convex hull B) interfere with each other, the configuration when the convex hull is decomposed into a convex polyhedron Release the convex hull with the smaller number. 3) If the triangular polygons with virtuality = 0 interfere with each other, neither convex hull is released.

As shown in FIG. 25, if the convex hull A and the convex hull B interfere with each other (see (b)) and the convex hull A is released and a set DA (Decomposed A) of constituent convex polyhedra appears ((( See c))
The second closest point search method of the present invention in the convex polyhedron between the set DA and the convex hull B is applied. The algorithm in this case is as follows. 1) Let TA (Virtuality (TA) = 1) be the interference triangular polygon of the convex hull A when the convex hull A is released. At this time, each side of the interference triangular polygon TA is composed of the element Edge (DA, PA) of the set DA and the side of virtuality = 1, and the lattice points of the interference triangular polygon TA are the elements Vertex (DA, PA) of the set DA. Composed of.

2) Constitution Checking the interference between the set of convex polyhedra DA and convex hull B is Edge (DA, PA), Vertex (DA, PA) and convex hull B.
This is performed by applying the second closest point search method of the present invention in a convex polyhedron. That is, Edge (DA, PA),
A DA triangular polygon including Vertex (DA, PA) (see the hatched portion in (c)) is searched from the directed graph structure data of each convex polyhedron (A ′, A ″) that constitutes the non-convex polyhedron.
Then, the second closest approaching point search method is applied in parallel between the triangular polygons and the convex hull B obtained from the respective interference checks (see (d)). 3) When exiting from the state of interference with the triangular polygon of virtuality = 1, the convex hull released by the recovery process is recovered, and the closest point search process is performed on the convex hull ((e)). By the process of 2), the convex polyhedron A ′, which is the target of the closest point search,
The number of triangular polygons in A ″ can be reduced (convex polyhedron A ′,
It is possible to reduce the calculation load of the closest point search process by using A ″.

(B) Closest point continuous search process between non-convex polyhedrons FIG. 26 is a flow chart of a second closest point continuous search process between non-convex polyhedra. Input the data that specifies the target non-convex polyhedron (initial input: environment model setting). ... Step 801 Then, the non-convex polyhedron is divided into convex polyhedrons, and each convex polyhedron P is divided.
Triangulation is performed on Hi, and then directed graph structure data of each convex polyhedron is created. Further, the convex hull is generated by the merging process, and the directed graph structure data of the convex hull is created (step 802).

When the above initialization process is completed, a second closest point search process (interference check) between non-convex polyhedrons is executed (step 803). It is checked whether they interfere with each other (step 804), and if they do interfere with each other, it is checked whether the triangular polygons with virtuality = 0 interfere with each other (step 80).
5) If YES, neither convex hull is released, the process is stopped, and the next instruction is awaited. However, virtuality = 0
If there is no interference between the triangular polygons of (1), it is checked whether or not the triangular polygon of virtuality = 1 (component of convex hull A) and the triangular polygon of virtuality = 0 (component of convex hull B) interfered (step 806). If YES, the convex hull A having the triangular polygon of virtuality = 1 is canceled (step 807). If NO, in other words, if the triangular polygon with virtuality = 1 (component of convex hull A) and the triangular polygon with virtuality = 1 (component of convex hull B) interfere, the convex hull becomes a convex polyhedron. The convex hull with the smaller number of constituent convex polyhedra when decomposed is obtained (step 8).
08), the convex hull is released (step 807).

Then, the edge of the interference triangular polygon TA
(DA, PA) and Vertex (DA, PA) are searched for triangular polygons of the set DA from the directed graph structure data of each convex polyhedron and passed to the processor (step 809). After that, the processor applies the second closest approach point search method in parallel between the obtained triangular polygon and the convex hull B to perform the interference check (step 803). On the other hand, in step 804, if there is no interference between the objects, recovery processing is executed (step 810).

In the recovery processing, it is checked whether or not there is a convex hull from which merging has been canceled, and if it exists, it is checked whether or not it interferes with another object, and if there is no interference, the non-interference time is counted. Then, if the non-interference time of the convex hull in which the merging is canceled is equal to or longer than the set value, the convex hull is restored. However, if it interferes with another object or if the non-interference time is not longer than the set value, the convex hull is not restored and the next step is executed. Next, it is checked whether all the parts of the convex hull are stationary (step 811). If not stationary, the process returns to step 803 to repeat the processing thereafter, and if stationary, the merging processing is executed to newly execute. A convex hull (step 812), and then step 8
Return to 03 and repeat the subsequent processing.

(F) First Decomposition Processing of Non-Convex Polyhedron into Convex Polyhedron (Preprocessing) (a) System Configuration To execute the closest point search between non-convex polyhedrons, the non-convex polyhedron is converted into a convex polyhedron. Need to be disassembled. FIG. 27 is a system configuration diagram in the case of performing preprocessing for searching for the closest point on the shape model on the graphic workstation,
GWS is a graphic workstation, CPU is a processor that performs preprocessing for the closest point search, closest point search processing, and other processing, MEM is a memory, and shape data FD designed by a three-dimensional CAD system (not shown).
T and a preprocessing program ICP for searching for the closest point are stored, DPL is a display unit, OPS is an operation unit such as a keyboard and mouse, and OPR is an operator. Operator O
The PR uses the operation unit OPS to input a command to the processor CPU to perform preprocessing on the geometric model on the graphic workstation GWS. When the preprocessing command is input, the processor CPU causes the memory ME
Preprocessing program I for searching for the closest point stored in M
Preprocessing (division processing of the polygon set of the non-convex polyhedron) is executed using the shape data FDT of the non-convex polyhedron based on the CP. 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 Pre-Processing for Closest-Point Searching FIG. 28 is a schematic process flow of pre-processing for the closest-point searching according to the present invention. The three-dimensional CAD system creates a shape model (non-convex polyhedron) and performs graphic work step 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. 28, 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 a shape model in a three-dimensional CAD system is usually three-dimensional CA.
It is prepared in the D 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) Convex Decomposition Basic Algorithm by Divide and Conquer Method FIG. 29 is a flowchart of the convex decomposition basic algorithm 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 subsets DP1, DP2, ... for each convex element are merged by merging those in which the polygon subsets of the first group and the polygon subsets 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 a detailed program example of the divide and conquer method. Definition P = {p ₁ , p ₂ , p ₃ , ...}: Initial polygon set DC (P) = {DP1 = { ₁ p ₁ , ₁ p ₂ , ₁ p ₃ , ...}, DP2 = { ₂ p ₁ , ₂ p ₂ , ₂ p ₃ , ...}, ...}: P divided polygon set NoP: P number of elements Algorithm (divided and controlled) if (input polygon number is 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 division-and-conquer method, division and governance processes are repeated recursively. 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. 30 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). Convex element set DC
Each element of (PL) and DC (PH) is CLi,
As indicated by CHj, it is composed of a set of polygons forming the element and a set of boundary edges forming the boundary of the element. 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. 31 is an explanatory diagram of the concavo-convex relationship judgment processing between polygons. As shown in FIG. 31 (a), assume two polygons A and B that share one boundary ridgeline BEG. The relative positional relationship of the polygons is either distant from each other or contacting each other via a ridgeline as shown in FIG. 31 (a), and other relationships (for example, intersecting at a portion other than the ridgeline). etc)
There is no. In FIG. 31 (a), the vector b,
c is a perpendicular vector drawn from the centers of gravity p and q of the polygon B and the polygon A to the boundary edge line x ₁ −x ₀ = a. Also, unitized vectors a, b, and c are referred to as e ₀ , e ₁ , and e ₂ , respectively. 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 = p-x₀-(x₁-x₀) ・ (P-x₀) (x₁-x₀) / | x₁-x₀|²・ Ha
It is the inner product of cuttles = p-x₀-e₀・ (P-x₀) e₀  c = q-x₀-e₀・ (Q-x₀) e₀  e₀= A / | a | e₁= B / | b | e₂= C / | c |
Vector b is X like 6 (b)₀Coordinates to match the axis
Convert. 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, polygon A and polygon B are convex. It can be said that there is a relationship. When handling actual CAD data, the judgment conditions are as follows in consideration of the error.

1) In the case of (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. Where ε
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. 31 is a local condition. However, when the initial polygon set is divided under the conditions shown in FIG. 31, very good convexity is shown in many cases.

(G) Second Example of Decomposition Processing into Convex Polyhedron (Preprocessing) When convex decomposition is performed by the basic algorithm by the division and convolution 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. 32 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 subsets DP1, DP2, ... for each convex element are merged by merging those in which the polygon subsets of the first group and the polygon subsets of the second group having a common boundary edge are in a convex relationship. · Ask for.

Thereafter, 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
While a convex polyhedron will be generated using the polygon subset forming (DC (P)), NDDC (P) and N
If DC (P) is not equal (eg NDDC
(P) <NDC (P)), DC (DC (P)) → DC
(P) (step 1208), and then step 12
The processing from 04 is repeated. That is, the convex decomposition processing by the division-and-conquer method is repeatedly applied to the newly obtained polygon subsets DC (DC (P)). In the optimization method,
The convex decomposition basic algorithm is repeatedly applied to the output DC (P) until the number of convex elements is not further reduced.

(H) Third Example of Decomposition Processing into Convex Polyhedron (Preprocessing) 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 the 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. 33 is an explanatory diagram of an object representation method by a Boolean set operation of an object including a shape such as a hole (negative object). HL is a hole, H
L'denotes a hole with the normal direction reversed, and BDY is an object without a hole (object without a hole). Objects with holes are objects without holes BDY
It is expressed by subtracting the hole part with the normal direction reversed from.

FIG. 34 is a flow chart of the convex decomposition process of the third embodiment, and FIG. 35 is an explanatory diagram of the convex decomposition result. Three-dimensional C
An initial polygon set (non-convex polyhedron polygon set) P is input from an AD 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). After that,
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 first with a common boundary ridge
The polygon subsets of the group and the polygon subsets of the second group are merged to obtain a plurality of new polygon subsets for each convex element.

Thereafter, a convex element set DC (P _B ) (see FIG. 35) 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. Thereafter, a convex element set DC (PP ₂ (DC (P _B ))) having the plurality of polygon subsets as elements is output (step 1307, FIG. 35) 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.

(I) Fourth Example of Decomposition Processing into Convex Polyhedron (Pre-Processing) Similarly to the case where the number of convex elements is reduced by applying the optimization method to the first example of convex decomposition, the third embodiment The example can be subjected to an optimization method to reduce the number of convex elements. FIG. 36 is a flowchart of the convex decomposition processing 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'.

(J) Fifth Example of Decomposition Processing into Convex Polyhedron (Preprocessing) (a) Consideration In the above examples, 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 any combination of polygon subsets, and in a brute force combination 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 Interference Check Preprocessing FIG. 37 is another schematic processing flow of the interference check preprocessing of the fifth embodiment. The same parts as those in the first embodiment of FIG. is 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. 38 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. 39 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 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: 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. 40 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) Search between the closest points between convex objects formed by the boundary edges Bedge _CLi and Bedge _CHj of the convex elements CLi and CHj and their distance di
st (Bedge _CLi , Bedge _CHj ) is obtained by the Gilbert method described above. The initial grid point (initial value) V ₀ of the Gilbert method is generally arbitrary, but it is efficient to start from the grid point in the direction of the center of gravity difference of each object. When finding the closest point by the Gilbert method, the following inequalities hold (see FIG. 41). r
_k = −h _k (−ν _k ) / | ν _k | ≦ | ν (K) | ≦ | ν _k
| (16) Therefore, if r _k > 0 for a certain k, it can be said that there is no interference between two convex objects.

(G) Merge Possibility Judgment Process Based on Gibert Method FIG. 42 is a merge possibility judgment process flow 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 (17) is constructed. Then, using this V ₀ , r = −h _k (−V ₀ ) = − h _k1 (−V ₀ ) −h _k2 (V ₀ ) (18) 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. 43 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 ').

(K) Modified Example of Convex Decomposition (a) Modified Example 1 It is possible to reduce the number of convex elements by performing optimization processing on the convex decomposition method of the fifth embodiment described above. The processing flow in this case is shown in FIG. In FIG. 44, step 12 is different from the processing of the second embodiment (see FIG. 32).
In 02 ′ and 1204 ′, the convex decomposition basic algorithm is replaced with a high-speed convex decomposition algorithm of a built-in interference check. (b) Modification 2 The interference check built-in type 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. 45, 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.

(L) Preprocessing of Closest Point Search (Creation of Proximity Point Linear List) In the above, the directed graph type structure data is generated from the polygon data by the preprocessing, and this directed graph type structure data is used to convert between convex polyhedrons or This is a case where the closest point search process between non-convex polyhedra is performed. Structure data different from the directed graph structure data, that is, a proximity point linear list is created by preprocessing and the continuous search of the closest points can be sped up by using this list. The close point linear list links the vertices of each polygon forming the shape model (CG model) in the first direction (next direction), and a group of vertices connected to each vertex via polygon sides in the second direction (b).
It is a list having a data structure formed by linking to the apex in the (runch direction). By sequentially tracing from the head of the list, it is possible to find all the neighboring points connected to the vertex.

(A) Example of Proximity Point Linear List FIG. 46 shows an example of a rectangular parallelepiped proximity point linear list. As shown in the figure, the proximity point linear list has two directions, that is, a next direction in which vertices are sequentially connected and a branch direction in which proximity points connected to each vertex via a polygon edge are arranged. At the beginning of the branch direction, the vertex itself enters. (b) Construction Method of Proximity Point Linear List FIG. 47 is a flow chart of processing for creating a proximity point linear list.
As shown in FIG. 48, the target object is composed of a set of triangular polygons, and each triangular polygon is represented by the coordinate values of three vertexes following the vertex and the light reflection direction data at each of the three vertexes following normal. It

The three-dimensional CAD system creates a shape model and outputs a polygon data file (step 20).
01, 2002). Then, the polygon data is divided into polygon data sets (polygon subsets) divided for each convex element according to a convex decomposition basic algorithm based on the interference check built-in division-and-conquer method. That is, the initial polygon data is divided into a set of subsets for each convex element and output (steps 2003 and 2004). After that, a proximity point linear list is generated using the proximity point linear list construction algorithm for each subset, that is, for each convex polyhedron, and expanded in the memory (steps 2005 and 2006). Then, the closest point linear list is used to perform the closest point search process (interference check process), and the closest point linear list is stored in the external storage medium (step 2007). After that,
If the proximity point linear list is required, it is not newly created, but is read from the external recording medium and expanded in the memory (step 2008).

(C) Proximity Point Linear List Construction Algorithm FIG. 49 is an explanatory diagram of polygon data for each convex element of the target object,
FIG. 50 is an explanatory diagram of a near-point linear list construction algorithm. Assuming that the target object is composed of a set of triangular polygons, the near point linear list is structured according to the following flow. 1) Prepare polygon data for each convex element by the convex decomposition basic algorithm (see FIG. 49). 2) For each polygon data (pi, qi, ri), connect each vertex to the list L. The next direction is the linear list direction with respect to the vertices, and the branch direction is the neighboring point direction of each vertex. The first element of the list L is the first vertex of the first polygon, and has a data structure shown in FIG. Specifically, the list is created as follows. 2-1) Allocate the top element top of list L. That is,
Assign the first vertex of the first polygon as top.

2-2) For the polygon (pi, qi, ri),
Repeat the following allocation. 1) If if (Lj ≠ pi for all j), a new element p i is assigned to the end in the next direction (see FIG. 50 (b)). Then, for the branch direction of the vertex Lj + 1, pi and q
i and ri are allocated (see FIG. 50 (c)). 2) If if (Lj = pi for a certain j), then qi and ri are assigned to the branch direction of Lj. If there is already the same vertex as qi and ri in the branch direction, it will not be assigned (see FIG. 50 (d)). 3) Perform the processes 1) and 2) for the vertex qi. However, branch candidates other than qi for the vertex qi are pi and ri. 4) The above processes 1) and 2) are executed for the vertex ri. However, the branch candidates other than ri for the vertex ri are pi and qi. 2-3) For all polygon sets ∪i (pi, qi, ri),
Repeat the process of 2-2).

(D) Example of Producing Near-Point Linear List FIGS. 51 and 52 are explanatory diagrams of an example of producing a near-point linear list. Polygon data for each convex element is prepared by the convex decomposition basic algorithm (step 2011). After that, the first
The polygon is incorporated into the list (step 2012), and then the second polygon is incorporated into the list L (step 2).
013). That is, in step 2012, first, the first vertex V ₁ of the first polygon is assigned as top. That is, top = L ₁ = V ₁ (2012a). Then, branc for vertex V ₁
All vertices V ₁ , V ₂ , V ₃ of the first polygon are assigned in the h direction (step 2012b). Then, the second vertex V ₂ is ne
Allocation in the xt direction (step 2012c), after allocation,
Vertex V ₂ all vertices V ₂ of the first polygon in the branch direction for, V _3, allocate V ₁ (step 2012d). Thereafter, similarly allocated a third vertex V ₃ in the next direction (step 2012E), after allocation, all vertices V ₃ of the first polygon in the branch direction for vertices V _3, allocate V _1, V ₂ (step 2012f).

In step 2013, the first vertex V ₁ of the second polygon is assigned. In this case, since the vertex V ₁ has already been allocated in the next direction, the branch of the vertex V ₁
The vertices V ₁ , V ₃ and V ₄ are assigned to the direction. However, since the vertices V ₁ and V ₃ have already been assigned, only the vertex V ₄ is assigned (step 2013a). Then, the second
Allocate vertex V ₃ in the next direction. In this case, since the vertex V ₃ has already been allocated in the next direction, br of the vertex V ₃
The vertices V ₃ , V ₄ and V ₁ are assigned in the anch direction. But,
Since the vertices V ₃ and V ₁ have already been assigned, the vertex V ₄
Allocate only (step 2013b). After that,
The third vertex V ₄ is allocated in the next direction (step 201).
3c). Then, the vertex V ₄ in the branch direction of the vertex V _4,
V ₁ and V ₃ are assigned (step 2013d). In the above description, the polygon is described as a triangular polygon, but the polygon is not limited to a triangular polygon, and any polygonal polygon may be used. The computational load of creating a near-point linear list from N vertices is O (N ² ).

(M) Preprocessing of Closest Point Search (Creation of Proximity Point Multi-Tree List) The calculation load for generating a proximity point linear list is O (N ² ) for N vertices, which is large. Therefore, a list of another data structure (proximity point branch tree list) that can be used for continuous search for the closest point is created, and the continuous search for the closest point is speeded up by using this list. The near point multi-branch tree list is an array list of the following vertices. That is, the reference vertex is determined, the first next direction (xright) larger than the X coordinate value of the reference vertex, and the second second smaller than the X coordinate value.
Next direction (xleft), third next direction (yright) larger than Y coordinate value, fourth next direction smaller than Y coordinate value
(yleft), the 5th next direction larger than the Z coordinate value (zrigh
t) and the sixth next direction (zleft) smaller than the Z coordinate value. Then, each axis coordinate value of the reference vertex is compared with each axis coordinate value of a vertex (referred to as a target vertex) connected to the reference vertex by a polygon side, and the next direction linking the target vertex is obtained according to the size. At the same time, the target vertices are linked in the order of being closer to the reference vertex in the next direction. When linking target vertices in the next direction, if the coordinate values of the other vertices already linked in the next direction and the coordinate values of the target vertices are equal, set the coordinate values of the axes of the other vertices and the target vertices. Compare. Then, the next direction according to the magnitude is obtained, and the target vertex is linked to the next direction with respect to the other vertices. Further, a branch direction is set for each vertex, and all the vertices connected to the vertex by polygon sides are arranged in that direction. The neighbor point multi-tree list is created as described above.

(A) Example of Proximity Point Multitree Tree List FIG. 53 shows an example of a rectangular parallelepiped multipoint tree list. As shown in the figure, in the near-point multi-branch tree list, each vertex has six link directions xright, xleft, yright, yleft, zright, zleft corresponding to the magnitude of each axis in x, y, z, and one branch. It has a direction. Apex
In the branch direction, all vertices connected to the vertices by polygon sides are arranged, and the vertices themselves are arranged at the head thereof.

(B) Method for Constructing Proximity Point Multi-Tree List FIG. 54 is a flow chart of the processing for creating the proximity point multi-tree list. The three-dimensional CAD system creates a shape model and outputs a polygon data file (steps 2101, 2).
102). Then, the polygon data is divided into polygon data sets (polygon subsets) divided for each convex element according to a convex decomposition basic algorithm based on the interference check built-in division-and-conquer method. That is, the initial polygon data is divided into subset sets for each convex element and output (steps 2103 and 2104). Thereafter, a near-point multi-tree list is generated using the near-point multi-tree list construction algorithm for each subset, that is, for each convex polyhedron (step 2105). Next, the near-point multi-tree conversion algorithm is used to convert the near-point multi-tree list into a near-point linear list and expand it in the memory (steps 2106 and 21).
07). Then, the closest point search process (interference check process) is executed using the near point linear list, and the near point linear list is stored in the external storage medium (step 21).
08). After that, when the neighborhood point linear list is required,
Instead of newly creating it, it is read from the external recording medium and expanded in the memory (step 2109).

(C) Proximity Point Multi-Tree List Construction Algorithm Assuming that the object is composed of a set of triangular polygons, the proximity point multi-tree list is constructed according to the following flow. 1) Prepare polygon data for each convex element by the convex decomposition basic algorithm (see FIG. 49). 2) For each polygon data (pi, qi, ri), connect each vertex to the multi-tree list ML. Maybe tree list M
In L, xright, xleft, yright, yleft, zright,
x, y, z as seen from the vertices that focus on zleft
The direction of the axis is large or small. In addition, each vertex is a near point direction
It has a branch direction. Specifically, the neighboring point multi-tree list ML is constructed according to the following procedure (see FIG. 53).

2-1) Allocate the top element top of ML. to
As p, assign the first vertex of the first polygon. 2-2) Repeat the following allocation for polygons (pi, qi, ri). (1) Compared to the apex p i in the order of magnitude of x coordinate value, y coordinate value, and z coordinate value as viewed from the top element ML of the ML in a lexicographical manner, and allocation is performed. That is, first, the vertex p
When the x coordinate value of i is larger than the x coordinate value of top, the x coordinate value of another element that has been arranged in the xright direction from the top is compared with the x coordinate value of the vertex p i to compare with the xright direction. And arrange p i in ascending order. X coordinate value of vertex pi is to
When it is smaller than the x coordinate value of p, the same arrangement is performed in the xleft direction when viewed from top. If there is an already-placed vertex having an x-coordinate value that matches the x-coordinate value of the vertex p i, the y-coordinate values are compared, and the y-coordinates are arranged in ascending order when viewed from the already-placed vertex. To do. When there is an already-arranged vertex whose y-coordinate value matches, the same ascending order arrangement is performed for the z-coordinate value. If there is a vertex with the same coordinate values of x, y, and z, the vertex p i is regarded as the same as that point. (2) For the newly allocated vertex p i, the branc of the vertex p i
Allocate pi and qi, ri in the h direction. If the vertex pi already has a branch element, it is compared with each branch element to avoid the allocation of the same point.

(3) The above processes (1) and (2) are executed for the vertex qi. However, the branch other than qi for the vertex qi
The candidates are pi and ri. (4) The above processes (1) and (2) are executed for the vertex ri.
However, branch candidates other than ri for vertex ri are pi,
qi. 2-3) For all polygon sets ∪i (pi, qi, ri),
Repeat the process of 2-2). In the above description, the polygon is described as a triangular polygon, but the polygon is not limited to a triangular polygon, and any polygonal polygon may be used. The calculation load for creating a neighbor multi-tree list from N vertices is O (NlogN)
Is.

(D) Proximity point multi-tree list conversion algorithm In the interference check between convex polyhedra (closest point search processing), the vector inner product with each vertex forming the convex polyhedron is taken and the maximum value is detected. Repeat. This time,
If each vertex is in the form of a near-point multi-tree tree, many complicated decision functions will be involved when sequentially tracing each vertex. Therefore, once the proximity points of the vertices are constructed in the form of the proximity point multi-branch list, if the multi-branch tree list is converted into a linear list, the amount of calculation thereafter will be small.
To convert a multi-branch tree list to a linear list, for example, the recursive function vertex * MultiToLinear () shown below is used.

Vertex * MultiToLinear () {vertex * V; v = this; // this represents the pointer of the current vertex if (next = 0) {if (xleft! = 0) {// assign xleft to next next = xleft; v = xleft → MultiToLinear (); // act recursively in the xleft direction} if (xright! = 0) {// for xright, yleft, yright, zleft, zright and so on v → next = xright; v = xright → MultiToLinear ();} if (yleft! = 0) {v → next = yleft; v = yleft → MultiToLinear ();} if (yright! = 0) {v → next = yright; v = yright → MultiToLinear ();} if (zleft! = 0) {v → next = zleft; v = zleft → MultiToLinear ();} if (zright! = 0) {v → next = zright; v = zright → MultiToLinear ();}} return V;} When the above function is applied to the top element top of the multi-tree list ML (top → MultiToLinear ()), the multi-tree list ML is converted to the linear list L. The calculation time of the near-point multi-tree list conversion algorithm is O (N) where N is the total number of vertices.
Is. Therefore, the total calculation time for generating the adjacent point linear list L from the polygon data through the adjacent point multi-tree list construction algorithm is O (NlogN).

(N) Pre-processing of closest point search (dumping and loading of linear list of closest points) The closest point linear list information required for the closest point search processing, that is, the interference check processing is all developed on the memory. I have to keep it. If it takes the same calculation time (O (NlogN) for the total number N of vertices) to construct the near-point multi-tree list, it is necessary to expand the dump file into the memory. , It makes no sense to create a dump file. Therefore, in the present invention, the format of the dump file is determined so that the loading time from the dump file is O (N). (a) Dump file format The dump file format is as shown in FIG. In this file format, the essential items for high-speed loading are as follows. 1) Each convex element is separated, 2) Total number of vertices that make up a convex element (count), 3) Each vertex is numbered, 4) Each vertex , The number of neighboring points of that vertex (bcount)
5) There is an item that defines the coordinates of each vertex.

(B) Loading Method from Dump File 1) Read the total number of vertices (count) forming the convex element, and create a count-dimensional array containing each vertex. 2) While accommodating each vertex of the convex element in the array, connect each vertex in the next direction to form a linear list. For example, Ve
When the array containing rtex is V [Ni], V [0], V
[1], ... Are sequentially connected in the next direction to form a linear list. 3) Apply the processing of 1) and 2) to each convex element.

4) With respect to each vertex of each convex element, a list of neighboring points in the branch direction is set according to the number of neighboring points of branch (designate the position in the array). For example, when the array that contains Vertex is V [Ni], the branch number of Vertex V [0] is
If (0,9,1,7,8), V in the branch direction of VertexV [0]
Connect [0], V [9], V [1], V [7], V [8] into a linear list. 5) The process of 4) is applied to each convex element. In the above loading method, a total of 2 times (1), 2), 3) for the same file,
4) and 5) read the second time). In most cases, the number of branches at each vertex can be kept below several tens, so
The total loading time is O (N). As shown in FIG. 55, a dump file divided for each convex element is called an L file. (c) Dump file for convex hull For the smallest convex polyhedron (convex hull) that wraps a non-convex polyhedron, the same dump file as in FIG. 55 is defined. In this case, the number of convex elements is one, and the vertex is composed of all the vertices forming the non-convex polyhedron. A file in the format of FIG. 55 for a convex hull is called an HL file.

(O) Interference check sub-algorithm (preliminary check by envelope sphere) For an arbitrary non-convex polyhedron, a sphere that envelopes it is generated in preprocessing. At this time, before starting the interference check between the non-convex polyhedrons, the interference check is performed between the envelope spheres to increase the speed. (a) Envelope sphere construction method A non-convex polyhedron is represented by a set of triangular polygons.
It is expressed as ∪i (pi, qi, ri). The suffix i is a subscript that identifies each polygon. The coordinate values of pi, qi, ri are pi = (pix, piy, piz), qi = (qix, qiy,
qiz) and ri = (rix, riy, riz). This time,
Find the max and min points of the convex hull as follows. max = (MAXi (pix, qix, rix), MAXi (piy, qiy, riy), MAXi (pi
z, qiz, riz)) min = (MINi (pix, qix, rix), MINi (piy, qiy, riy), MINi (pi
z, qiz, riz)) The envelope sphere is defined based on the following formula. Radius R = | max-min | / 2 Center Pc = (max + min) / 2

(B) Envelope sphere for convex element For each convex element, a sphere enclosing each convex element is defined. The calculation method is the same as in (a). However, m
The suffix i when defining ax, min means the polygon set of each convex element. (c) Preliminary Check Algorithm Using Envelope Sphere FIG. 56 is a processing flow of preliminary check using the envelope sphere. Envelope sphere radii R _A , R _{B of} each non-convex polyhedron A, B and envelope sphere centers P _CA , P _CB are determined by the method described above (step 220).
1,2202), the following equation r = distance between the centers r of each envelope spheres | P _CA -P _CB | determined _{by, r ≦ (R A + R} B) or check (step 2203). If r> (R _A + R _B ), it is determined that there is no interference (step 2204). If r ≦ (R _A + R _B ), it is determined that they interfere with each other, and thereafter, an interference check between non-convex polyhedrons is performed (step 2205).

(P) Interference check sub-algorithm (continuous search in convex polyhedron interference check) From the adjacent point linear list, the vertices that are closest to the closest approach point are extracted, and the interference check method by the Gilbert method is applied to these vertices. Is applied to search for the closest point after a predetermined time. By doing so, the time required for the interference check can be suppressed to a fixed number or less, which hardly depends on the number of polygons expressing the convex polyhedron. (a) Gilbert method The distance ν (K) between the closest points between convex polyhedra K ₁ and K ₂ is g _K
To (ν _K) = 0 and becomes ν _K, (12) 'by using the equation _{ν (K) = ν k =} ν (coV k) = Σλ i y i (i∈Is) = Σλ i x 1 i (IεI _K1Sk ) −Σλ _i x ² _i (iεI _K2Sk ) (19) where, vertices forming x ¹ _i : K ₁ and vertices forming x ² _i : K ₂ are given.

(B) Intuitive understanding of Gilbert's method FIG.
It is an explanatory view that can be solved. Simplify each process
To explain it simply: 1) Set vector η Connect the geometric centers of gravity of two objects,₀(Fig. 57
(Figure (a)). 2) The following inner product calculation h_K1(-Ν₀) = Max {−x¹ _i・ Ν₀: I = 1, ... m₁} (20) h_K2(-Ν₀) = Max {−x² _i・ Ν₀: I = 1, ... m₂} (21) is performed and the vector ν₀Are closest to each other in
2 points p₀, Q₀Is selected (Fig. 57 (a)). 3) ν₁Update 2 points p₀, Q₀Tie together ν₁(FIG. 57 (b)). 4) Inner product calculation ν₁The same inner product calculation as 2) is performed for 2 new points p₁，
q₁Is selected (FIG. 57 (b)). 5) Inner product calculation and ν₁Repeatedly update the final closest
Point vector ν_finalIs obtained (FIG. 57 (c)). As can be seen from the above process, the main Gilbert method
The calculation load occurs in the process of inner product calculation. Therefore, Gilber
The calculation time for the closest point search in the t method is O (m₁+ m ₂) Tona
It

(C) Continuous interference check in convex polyhedron The calculation load in the Gilbert method depends on the support functions h _K1 and h _K2.
It occurs in the process of calculating the inner product of. Therefore, in order to reduce the number of inner product calculations, a method of efficiently finding the closest point of the closest vector ν (K) will be considered. The closest points ν _K1 and ν _K2 of the convex polyhedra K ₁ and K ₂ are given by the following equation from the equation (19). ν _K1 = Σλ _i x ¹ _i ( _i ∈ I _K1Sk ) (22) ν _K2 = Σ λ _i x ² _i ( _i ∈ I _K2Sk ) (23) When searching for the closest point continuously, The approach points exist near ν _K1 and ν _K2 given by Eqs. (22) and (23). Therefore, the vertices for calculating the support functions h _K1 and h _K2 can be limited to the neighboring points of the vertices x ¹ _i and x ² _{i in} the expressions (22) and (23).

FIG. 58 is a flow of a continuous interference check algorithm for a convex polyhedron. First, the geometric centers G _K1 and G _K2 of the two convex polyhedrons are _calculated , and the vector ν ₀ = G _K1 −G _K2 is calculated (step 2301). Next, an interference check algorithm by the Gilbert method is executed with ν ₀ as an initial value, and ν _K1 and ν _K2 given by the equations (22) and (23) are obtained (step 2302). Then, ν ₀ = ν _K1 −ν _K2 and G
Execute the interference check algorithm by the ilbert method
(Step 2303). However, in the calculation of the support function h _K (−ν ₁ ) = h _K1 (−ν ₁ ) + h _K2 (ν ₁ ), h _K1 (−ν ₁ ) and h _K2 (ν ₁ ) are calculated based on the following equations. calculate. h _K1 (−ν ₁ ) = max {−x ¹ _i · ν ₁ : p = the number of the neighboring point set of x ¹ _i given by the formula (22)} h _K2 (−ν ₁ ) = max {−x ² _i · ν ₁ : p = the number of the neighbor point set of x ¹ _i given by equation (22)} Then, the closest point is calculated by equations (22) and (23), and then g _K
The processing after step 2303 is repeated until (ν _K ) = 0. The number of adjacent points of the vertices x ¹ _i and x ² _i in FIG. 58 is 10 in most CG models (shape models).
It can be suppressed to the following. Therefore, the calculation load of the continuous interference check algorithm is constant regardless of the number of polygons of the CG model.

(Q) Interference Check Sub-algorithm (Dynamic Construction / Release of Convex Hull) For a non-convex polyhedron, a convex hull is defined as the smallest convex polyhedron that envelopes it. When the distance between the non-convex polyhedrons is sufficiently large, the interference check between the convex hulls is performed. When the convex hulls start to interfere with each other, the process automatically shifts to the interference check between the convex elements forming the non-convex polyhedron. . When the distance between the non-convex polyhedra becomes large again, the convex hulls are restored and the interference check between the convex hulls is restored. (a) Basic Concept of Convex Hull Dynamic Configuration / Release FIG. 59 and FIG. 60 are explanatory views showing the basic concept of convex hull configuration / release. In FIG. 59, A and B are the first,
The second non-convex polyhedron, C _A1 and C _A2, are convex polyhedrons forming the non-convex polyhedron A, and C _B1 and C _B2 are convex polyhedrons forming the non-convex polyhedron B. 1) When the non-convex polyhedrons A and B are sufficiently separated, the interference between the convex hulls A ′ and B ′ is checked (see FIG. 60 (a)).

2) When convex hulls A'and B'begin to interfere with each other
(See FIG. 60 (b)), one convex hull A'is released, and the convex element C
The interference between _A1 and C _A2 and the convex hull B ′ is checked, and if they interfere, the convex element C _A1 is taken out (see FIG. 60 (c)). 3) Then, the positions of the convex hull and the convex hull are exchanged, the other convex hull B ′ is released, and the convex element C _B1 of the released convex hull,
The interference between C _B2 and the convex hull A ′ is checked and the interfering convex element C _B1 is taken out (see FIG. 60 (d)). 4) Finally, all the combinations of extracted convex elements (Fig. 6)
At 0, interference check is performed on C _A1 , C _B1 ) and the distance that minimizes the distance is obtained. (Fig. 60
(e)). In 2), for example, as shown in FIG. 61 (a), convex elements C _A1, C _A2 and the convex hull B 'if such interference does not exist between the convex elements C _A1, C _A2 and the convex hull B' The closest vector between the two is obtained, and the two end points p and q that give the vector are the closest points. Also, as shown in FIG. 61 (b), when the positions between the convex elements C _B1 and C _B2 and the convex hull A ′ are exchanged, and there is no interference between the convex hull and the convex hull, the convex hull C _B1 , C _B2
And the convex hull A ', the closest vector is obtained, and the two end points p', q'that give the vector are the closest points.

FIG. 62 is a processing flow of the dynamic construction / cancellation algorithm of the convex hull. Convex hulls A'of non-convex polyhedra A, B,
Interference check processing (closest search processing) is performed between B ',
The distance r (A ', B') between the closest points is obtained. Then,
The magnitude of r (A ', B') and ε _CH is judged (step 2).
401). ε _CH is a user-defined small constant. r
When (A ′, B ′)> ε _CH , the convex hulls A ′ and B ′ do not interfere, so the closest point between the convex hulls A ′ and B ′ is the closest point between the non-convex polyhedrons A and B. And output (step 240
2). After that, the above process is repeated while maintaining the convex hull.
On the other hand, when r (A ′, B ′) ≦ ε _CH , the convex hulls interfere with each other, so that one convex hull, for example, convex hull A ′ is released.
The union of the convex elements C _Ai of the non-convex polyhedron A is expressed as ∪ _i C _Ai . Then, the distance r between the convex hull B ′ and each convex element C _Ai
A subset ∪ _i CC of convex elements whose (C _Ai , B ′) is ε _{CC H} or less
_Ai is calculated (step 2403). ε _CCH is a user-defined small constant. Then, it is checked whether the number of convex elements forming the subset ∪ _i CC _Ai is 0 (step 2
404). When ∪ _i CC _Ai = 0, r (C _Ai ,
B ′), the convex element C _Ak that gives the minimum distance MIN _i r (C _Ai , B ′) is determined, the closest point between the convex element C _Ak and the convex hull B ′ is determined, and the closest point is determined as It is output as the closest point between the convex polyhedrons A and B (step 2405).

However, when ∪ _i CC _Ai > 0, the other convex hull B ′ is released. The union of the convex elements C _Bj of the non-convex polyhedron B is expressed as ∪ _j C _Bj . Then, a subset ∪ _j CC _Bj of convex elements whose distance r (C _Bj , A ') between the convex hull A'and each convex element C _{B j} is ε _CCH or less is obtained (step 2406).
Then, the number of convex elements forming the subset ∪ _j CC _Bj is 0.
Is checked (step 2407). ∪ _j CC
_{When Bj} = 0, the minimum distance M out of r (C _Bj , A ′)
A convex element C _Bk that gives IN _j r (C _Bj , A ′) is obtained, the closest point between the convex element C _Bk and the convex hull A ′ is obtained, and the closest point is between the non-convex polyhedrons A and B. It is output as the closest point (step 2408). However, when ∪ _j CC _Bj > 0, the minimum distance MIN _{i, j} R between the subsets ∪ _i CC _Ai and ∪ _j CC _Bj.
The convex elements CC _Ap and CC _Bq that give (CC _Ai , CC _Bj ) are found, the closest point between them is found, and output as the closest point between the non-convex polyhedrons A and B (step 2409). After that, the process returns to the beginning and the subsequent processes are repeated.

(R) Interference Check Sub-algorithm (Dynamic Construction / Release of Convex Hull and Convex Polyhedron Continuous Interference Check) For a non-convex polyhedron, a convex hull is defined as the smallest convex polyhedron that envelopes it. If the distance between the non-convex polyhedrons is sufficiently large, continuous interference check between convex hulls is performed, and if the convex hulls start to interfere with each other, automatically shift to interference check between convex elements that compose the non-convex polyhedron. To do. When the distance between the non-convex polyhedrons becomes large again, the convex hulls are restored and the continuous interference check between the convex hulls is restored. FIG. 63 is a process flow of the algorithm of the dynamic construction / cancellation of the convex hull and the continuous polyhedron interference check, and FIGS. 64 to 66 are explanatory diagrams thereof. Interference check processing (closest approach search processing) is performed between the convex hulls A ′ and B ′ of the non-convex polyhedrons A and B, and the distance r (A ′, B ′) between the closest points is obtained.
Ask for. Then, the magnitude of r (A ', B') and ε _CH is determined. Further, the flag contflg _A ′ = 1 is set (step 2501). When r (A ′, B ′)> ε _CH , convex hulls A ′ and B ′ do not interfere, so the closest point between convex hulls A ′ and B ′ is the closest point between non-convex polyhedrons A and B. It is output as a point (step 2502). After that, the above process is repeated while maintaining the convex hull.

FIG. 64 shows the steps 2501 and 2502.
It specifically shows the process. As shown in FIG.
In the interference check between convex hulls, the first support function h
Is calculated based on inner product calculation for all points
However, from the next time onward, it will be based on the continuous interference checking algorithm.
It is calculated based on That is, the inner product calculation is performed near the closest point.
Limited to contact points. In the continuous interference check, the last contact
It is necessary to retain near-point information, but this information
Is held as an attribute of one of the convex hulls A ′ and B ′. Su
In the process of step 2502, contflg_A′ = 1 flag
Stands, and the interference check between (A ', B') is continuous.
It In step 2501, r (A ′, B ′) ≦ ε
_CH, The convex hulls interfere with each other, so one convex hull, eg
For example, the convex hull A'is released. Convex element C of non-convex polyhedron A _Aiof
Union ∪_iC_AiExpress. Then, the convex hull B'and each convex
Element C_AiDistance r (C_Ai, B ′) is ε_CCHThe following points
Prime subset ∪_iCC_AiAsk for. Also flag contflg
_CCA1= 1 (step 2503).

After that, it is checked whether the number of convex elements forming the subset ∪ _i CC _Ai is 0 (step 250).
4). ∪ _i CC in the case of _Ai = 0 _{is, r (C Ai, B '} ) ( convex element C giving the minimum distance MIN _i r C _Ai, B) of the'
_Ak is determined, and the closest point between the convex element _CAk and the convex hull B'is determined. Then, the closest point is output as the closest point between the non-convex polyhedrons A and B (step 2505). r (C _Ai ,
B ') is obtained by continuous interference check.

FIG. 65 (a) shows steps 2503 to 250.
5 is a specific explanatory diagram of FIG. The previous closest point information in the continuous interference check is held as an attribute of the convex element C _Ai of the non-convex polyhedron A. In step 2503 cont
The flag of flg _CCA1 = 1 is set, and the interference check between (C _Ai , B ′) in step 2505 is continuous. In step 2504, if ∪ _i CC _Ai > 0, the other convex hull B ′ is released. The union of the convex elements C _Bj of the non-convex polyhedron B is expressed as ∪ _j C _Bj . Then, a subset ∪ _j CC _Bj of convex elements in which the distance r (C _Bj , A ′) between the convex hull A ′ and each convex element C _Bj is ε _CCH or less is obtained. Also flag contflg
_CCB1 = 1 is set (step 2506). Then, it is checked whether the number of convex elements forming the subset ∪ _j CC _Bj is 0 (step 2507). When ∪ _j CC _Bj = 0, the minimum distance MIN _j r (C _Bj , r (C _Bj , A ′))
'Obtains a convex element C _Bk giving), convex element C _Bk and the convex hull A' A search of the point of closest approach between the outermost approach point non-convex polyhedron A,
It is output as the closest point between B (step 2508).

FIG. 65 (b) shows steps 2506-250.
It is a concrete explanatory view of No. 8. The previous closest point information in the continuous interference check is held as an attribute of the convex element C _Bj of the non-convex polyhedron B. In step 2506, cont
The flag of flg _CCBj = 1 is set, and the interference check between (C _Ai , B ′) in step 2508 is a continuous type. In step 2507, if ∪ _j CC _Bj > 0,
Minimum distance between subsets ∪ _i CC _Ai and ∪ _j CC _Bj MIN _{i, j} R
The convex elements CC _Ap and CC _Bq that give (CC _Ai , CC _Bj ) are found, the closest point between them is found, and output as the closest point between the non-convex polyhedrons A and B. Also, all flags contfl
g _A ', contflg _B', the contflg _CCA1, contflg _CCBj 0
(Step 2509). After that, the process returns to the beginning and the subsequent processes are repeated. FIG. 66 is an explanatory diagram showing the overall flow described above.

(S) Interference Check Sub-algorithm (Dynamic Construction / Release of Convex Hull and Envelope Sphere Interference Check) For a non-convex polyhedron, a convex hull is defined as the smallest convex polyhedron that envelopes it. When the distance between the non-convex polyhedrons is sufficiently large, the interference check of the convex envelope envelope spheres that envelope the convex hull is performed, and when the convex envelope envelope spheres start to interfere, the interference check of the convex hulls is performed. When the convex hulls start to interfere with each other, the envelope sphere interference check and the convex polyhedron interference check are performed on the convex elements forming the non-convex polyhedron. The envelope sphere interference check and the configuration / release of the convex hull are dynamically switched according to the distance between the non-convex polyhedra. FIG. 67 is a processing flow of dynamic configuration / cancellation of the convex hull and envelope sphere interference check. Each non-convex polyhedron A, B
Determined by, | the envelope spheres radius R _A, R _B, envelope spheres center P _CA, obtains a P _CB (step 2501, 2502), the distance between the centers following equation r r = in each envelope spheres | P _CA -P _{CB r ≦ (R A + R B} ) or to check (step 250
3).

If r> (R _A + R _B ), it is determined that there is no interference, and r is output as the distance between the closest points (step 25).
04). If r ≦ (R _A + R _B ), the non-convex polyhedron A, B
The interference check process (closest approach search process) is performed between the convex hulls A'and B'to obtain the distance r (A ', B') between the closest points. Then, the magnitude of r (A ', B') and ε _CH is determined (step 2505). When r (A ', B')> ε _CH , the convex hulls A'and B'do not interfere, so the convex hulls A'and B '
The closest point between them is set as the closest point between the non-convex polyhedrons A and B and output (step 2506). On the other hand, r (A ', B')
When ≦ ε _CH , the convex hulls interfere with each other, so that one convex hull, for example, convex hull A ′ is released. The union of the convex elements C _Ai of the non-convex polyhedron A is expressed as ∪ _i C _Ai . Next, an interference check is performed between the envelope sphere of each convex element C _{Ai and} the envelope sphere of the non-convex polyhedron B, and an interference check is performed between each convex element C _Ai and convex hull B ′ that interfere. Then, a subset ∪ _i of convex elements whose distance r (C _Ai , B ′) between the convex hull B ′ and each convex element C _Ai is ε _CCH or less.
SCC _Ai is calculated (step 2507).

Then, it is checked whether the number of convex elements forming the subset ∪ _i SCC _Ai is 0 (step 250).
8). When ∪ _i SCC _Ai = 0, r (C _Ai , B ′)
Among them, the convex element C _Ak that gives the minimum distance MIN _i r (C _Ai , B ′) is found, the closest point between the convex element C _Ak and the convex hull B ′ is found, and the closest point is the non-convex polyhedron A. , B is output as the closest point (step 2509). If ∪ _i SCC _Ai > 0, the other convex hull B ′ is released. The union of the convex elements C _Bj of the non-convex polyhedron B is expressed as ∪ _j C _Bj . Then, an interference check is performed between the envelope sphere of each convex element C _{Bj and} the envelope sphere of the non-convex polyhedron A, and an interference check is performed between each convex element C _Bj and the convex hull A ′ that interfere. Thereafter, a subset ∪ _j SCC _Bj of convex elements whose distance r (C _Bj , A ') between the convex hull A'and each convex element C _Bj is ε _CCH or less is obtained (step 2510). Then, it is checked whether the number of convex elements forming the subset ∪ _j SCC _Bj is 0 (step 2511). ∪ _j SCC _Bj
= 0, the minimum distance MIN of r (C _Bj , A ′)
_The convex element C _Bk that gives _i r (C _Bj , A ′) is obtained, the closest point between the convex element C _Bk and the convex hull A ′ is obtained, and the closest point is determined as the closest point between the non-convex polyhedrons A and B. It is output as an approach point (step 2512).

However, ∪_jSCC_BjIf> 0, then
Minute set ∪_iSCC_AiAnd ∪_jSCC_BjMinimum distance between MIN_{i, j}
r (SCC_Ai, SCC_Bj) Giving a convex element SCC_Ap, S
CC _Bq, The closest point between them, and the non-convex polyhedron
It is output as the closest point between A and B (step 251).
3). After that, the process returns to the beginning and the subsequent processes are repeated. The figure
67 algorithm, the continuous interference check of the convex polyhedron of FIG.
Speed up interference check by incorporating a clock processing
can do.

(T) Structure of Interference Check System FIG. 68 is a block diagram of the interference check system of the present invention, in which 21 is a three-dimensional CAD system for generating a shape model and outputting a polygon data file, and 22 is a polygon data file. Or a memory for storing the convex element data obtained by the preprocessing, the near-point multi-tree list, the near-point linear list, etc., 23 is a near-point multi-tree list creating unit for creating the near-point multi-tree list from the polygon data file, and 24 is A proximity point linear list creation unit that generates a proximity point linear list from the proximity point multi-tree list, 25 is a convex decomposition unit that decomposes a non-convex polyhedron into a set of convex elements, 26 is an interference check unit, and 27 is a proximity point linear list. A list input / output unit 28 which outputs the data to an external recording medium and appropriately reads it and expands it in the memory 22 is an external recording device such as a hard disk. It is a medium.

(U) Application Fields of the Present Invention The present invention can be applied in the following fields. (a) CAD system for mechanical design In mechanical design, careless interference often occurs when assembling products. In order to prevent such a situation in advance, it is important to carefully check the bonding relationship between parts and the margin on the mechanical design CAD system. By incorporating the real-time interference check system into the CAD system for mechanical design, it is possible to perform a preliminary check in a form close to an actual product. (b) Path planning for mobile robots In many cases, mobile robots such as manipulators and self-propelled vehicles are driven after planning paths so that they do not collide with other objects. For example, in the assembly of parts using a manipulator, it is necessary to plan a route while checking the interference between the parts and the interference between the parts and the manipulator. In addition, self-propelled robots such as cleaning robots, guard robots, and transport robots require route planning that avoids collisions with obstacles such as walls, columns, or desks when moving between points. In such a case, it is effective to incorporate a high-speed interference check system into the manipulator or the robot control unit and check in advance.

(C) Creation of Animation in Multimedia In the field of animation, creation of highly realistic animation using a graphic computer is desired. For example, when walking an android model, it is necessary to solve a contact problem between the android model and the ground, and when simulating a car collision, it is necessary to solve an inter-car interference problem. (d) Game software Conventional game software was mostly two-dimensional, but it is expected that three-dimensional display using a graph computer will become mainstream in the future. In game software, there are many problems of interference between objects such as collision between missile and fighter in shooting game and collision between cars in racing game. The real-time interference checking system of the present invention provides a powerful tool in the above application fields. 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.

[0168]

As described above, according to the present invention, it is determined whether the closest point of each convex polyhedron is on a grid point, on a side, or on a polygon, and (1) on the grid point. If it exists on the side (2), the polygon that composes the grid point is obtained from the directed graph structure data, and the grid point of the polygon is used for the inner product evaluation in the closest point search processing by the Gilbert method. Since the polygons forming the sides are obtained, the lattice points of the polygon are used for the inner product evaluation, and (3) the lattice points of the polygon are used for the inner product evaluation when they are present on the polygon. , The number of grid points applied to the inner product evaluation can be reduced, and the calculation load can be reduced.

Further, according to the present invention, a surface polygon (polygon) forming a convex polyhedron is divided into triangles, and whether the closest point of each convex polyhedron is on a grid point or on a side. , It is determined whether or not it exists on a triangular polygon, and (1) if it exists on a lattice point, the triangular polygon that constitutes the lattice point is obtained from the directed graph structure data, and the lattice point of the triangular polygon is used for inner product evaluation. , (2) If it exists on the side, the triangular polygons that compose the side are obtained, and the grid points of the triangular polygon are used for the inner product evaluation. (3) If it exists on the triangular polygon, Since the grid points are used for the inner product evaluation, the number of grid points applied to the inner product evaluation can be further reduced and the calculation load can be reduced.

Further, according to the present invention, the smallest convex polyhedron (convex hull) enclosing a non-convex polyhedron is generated, the directed graph type structural data of the convex hull is created, and the directed graph type structural data of the convex hull is used. To find the closest point between the non-convex polyhedrons, and if the surface convex polygon with virtuality = 1 interferes with another object, the convex hull is released, and then the non-convex Since the closest point search processing is performed on a plurality of convex polyhedrons that form a polyhedron, the closest point between non-convex polyhedrons can be searched, and surface convex polygons with virtuality = 1 can be used. It is possible to reduce the calculation load required for the closest point search process until the object interferes with the object. Further, according to the present invention, when the convex convex surface of the virtuality = 1 interferes with another object to cancel the convex hull, and when the convex polygon of the surface no longer interferes with another object, the convex convex hull is formed. Since the restoration is performed and the closest point search processing is performed, the calculation load of the restored closest point search processing can be reduced.

Further, according to the present invention, a close point linear list is created in the preprocessing, and a vertex close to the closest approach point which has been obtained most recently at the time of interference check is obtained from the close point linear list. Since the closest point at the next time is continuously searched for, it is not necessary to perform the closest point search process on all the vertices, so that the interference check can be performed at high speed. In addition, since the neighbor point multi-branch tree list is created and the neighbor point multi-branch tree list is converted into the neighbor point linear list, the linear list can be created at high speed, and as a result, the interference check can be performed even faster. You can Further, by storing the proximity point linear list as a file in the external recording medium and reading the file as appropriate to perform the interference check, the interference check can be performed at high speed. Further, since the envelope sphere and the convex hull are generated and the interference check is performed by using the envelope sphere and the convex hull when they are apart from each other, the high-speed interference check can be performed.

[Brief description of drawings]

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

FIG. 2 is an exploded view of a convex polyhedron into surface polygons (in the case of a hexahedron).

FIG. 3 is an explanatory view of a convex polyhedron data structure for searching for the closest point (in the case of a hexahedron).

FIG. 4 is a processing flow chart of a first closest point searching method of the present invention.

FIG. 5 is an explanatory diagram of convex polyhedron data input.

FIG. 6 is a configuration diagram of a first closest point searching device.

FIG. 7 is an explanatory diagram of triangulation of a convex polyhedron.

FIG. 8 is an explanatory diagram of polygonal triangulation.

FIG. 9 is a processing flow chart of a second closest point searching method.

FIG. 10 is a block diagram of a second closest point searching device.

FIG. 11 is an explanatory diagram of a merging process.

FIG. 12 is an explanatory diagram of a merging data structure.

FIG. 13 is a flow chart of a merging algorithm.

FIG. 14 is an explanatory diagram of convex hull data.

FIG. 15 is an explanatory diagram of merging processing by a task.

FIG. 16 is an explanatory diagram of a merging process using a While sentence.

FIG. 17 is an explanatory diagram of the present invention when the environment dynamically changes.
(Part 1).

FIG. 18 is an explanatory diagram of the present invention when the environment dynamically changes.
(Part 2).

FIG. 19 is an explanatory diagram of merging and recovery processing.

FIG. 20 is an explanatory diagram of a recovery process using a While statement.

FIG. 21 is an overall processing flow diagram for searching for the closest point between non-convex polyhedra.

FIG. 22 is a block diagram of the closest point search device between non-convex polyhedra of the present invention.

FIG. 23 is a diagram illustrating a first method of continuous search for closest points between non-convex polyhedra.

FIG. 24 is a flowchart of a first closest point continuous search process between non-convex polyhedra.

FIG. 25 is a diagram illustrating a second method of continuous search for closest points between non-convex polyhedra.

FIG. 26 is a flowchart of a second closest point continuous search process between non-convex polyhedra.

FIG. 27 is a system configuration diagram.

FIG. 28 is a schematic process flow of a process before interference check.

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

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

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

FIG. 32 is a processing flow of a second example of convex decomposition preprocessing.

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

FIG. 34 is a processing flow of a third example of convex decomposition preprocessing.

FIG. 35 is an explanatory diagram of a result of convex division when there is a negative object.

FIG. 36 is a processing flow of the fourth example of the convex decomposition preprocessing.

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

FIG. 38 is a flowchart of a fast convex decomposition basic algorithm.

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

FIG. 40 is a schematic process flow of an interference check algorithm.

FIG. 41 is an explanatory diagram of the principle of interference check by the Gilbert method.

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

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

FIG. 44 is a processing flow of a first modification of convex decomposition.

FIG. 45 is a processing flow of a second modification of convex decomposition.

FIG. 46 is an example of a close point list.

FIG. 47 is a pre-processing flow for creating a near point linear list.

FIG. 48 is an explanatory diagram of rectangular parallelepiped and polygon data divided into triangular polygons.

FIG. 49 is an explanatory diagram of polygon data for each convex element.

FIG. 50 is an explanatory diagram of an algorithm for generating a near point linear list.

FIG. 51 is another explanatory diagram of an algorithm for generating a near point linear list.

FIG. 52 is an explanatory diagram of creating a near point linear list.

[Fig. 53] Fig. 53 is an example of a near-point multi-tree list.

FIG. 54 is a preprocessing flow for creating a near-point multi-tree list.

FIG. 55 is an explanatory diagram of a dump file format of a near point linear list.

FIG. 56 is a flow of a pre-check algorithm using an envelope sphere.

FIG. 57 is an explanatory diagram of a basic idea of the Gilbert method.

FIG. 58 is a flow of a continuous interference check algorithm for a convex polyhedron.

FIG. 59 is an explanatory diagram of a non-convex polyhedron.

[Fig. 60] Fig. 60 is an explanatory diagram of a basic concept of dynamic configuration / cancellation of a convex hull.

FIG. 61 is an explanatory diagram of interference check between the convex hull and the convex element.

FIG. 62 is a flow of a convex hull dynamic configuration / cancellation algorithm.

FIG. 63 is a flow chart of dynamic configuration / cancellation of a convex hull and continuous convex polyhedron interference check.

FIG. 64 is an explanatory diagram of continuous interference check between convex hulls.

FIG. 65 is an explanatory diagram of continuous interference check between a convex element and a convex hull.

66 is an explanatory diagram of interference check between convex elements. FIG.

FIG. 67 is a flow of a convex hull dynamic configuration / cancellation and envelope sphere interference check algorithm.

FIG. 68 is a configuration diagram of an interference check system.

FIG. 69 is an explanatory diagram (part 1) of points to be solved by the closest point algorithm.

FIG. 70 is an explanatory diagram (part 2) of points to be solved by the closest point algorithm.

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

[Fig. 72] Fig. 72 is an explanatory diagram of searching for the closest point by the Gilbert method.

FIG. 73 is an explanatory diagram of the Gilbert method.

FIG. 74 is an explanatory diagram of a numerical test result of the Gilbert method.

[Fig. 75] Fig. 75 is an explanatory diagram of searching for the closest point between non-convex polyhedra by the Gilbert method.

[Explanation of symbols]

 12 ... Storage unit for storing convex polyhedron data 13 ... Directed graph data creation unit 14 ... Storage unit for storing directed graph type structure data 15 ... Closest point search processing unit 22a ... Polygon data storage unit 22b ... Proximity Point linear list storage unit 24 ... Proximity point linear list creation unit 26 ... Closest point search processing unit

 ─────────────────────────────────────────────────── ─── Continuation of front page (72) Inventor Tsujito Maruyama 1015 Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Fujitsu Limited

Claims (17)

[Claims] 1. A closest point to a shape formed by a subset having p points on a difference convex polyhedron, which is a difference set of two convex polyhedrons, as an element, and a position vector of the closest point is obtained. Evaluate the inner product with the position vector of the lattice point of each convex polyhedron, and based on the evaluation result, determine whether the closest point matches the closest point from the origin to the differential convex polyhedron. Change the set, and finally find the closest point from the origin to the difference convex polyhedron to find the closest point of each convex polyhedron. In the closest point search method, below each surface polygon (polygon) of the convex polyhedron Each convex polyhedron is represented by directed graph structure data in which grid points and sides that are elements of the polygon are arranged, and grid points and polygons that form the grid are arranged below the sides, respectively. To the closest point of the shape formed by It is determined whether the closest point on each convex polyhedron is on a grid point, on a side, or on a polygon. If it is on a grid point, the grid is determined from the directed graph structure data. The polygons that make up the points are obtained, the grid points of the polygons are used for the inner product evaluation, and if they are on the sides, the polygons that make up the sides are obtained from the directed graph structure data, and the grid points of the polygons are set to the inner product. It is used for evaluation, and if it exists on a polygon, the grid points of the polygon are used for the inner product evaluation to find the closest point from the origin to the difference convex polyhedron, and find the closest point of each convex polyhedron. Search method. 2. When searching for the closest point between non-convex polyhedra, the smallest convex polyhedron (convex hull) that encloses the non-convex polyhedron is generated, and directed graph structure data of the convex hull is created, The closest approach point search method according to claim 1, wherein the closest approach point search between non-convex polyhedrons is performed using the directed graph structure data of the convex hull. 3. If the surface convex polygon forming the convex hull matches the surface convex polygon of the original non-convex polyhedron, then virtuality = 0, otherwise virtuality = 1, and virtuality = 3. When the surface convex polygon of No. 1 interferes with another object, the convex hull is released, and the closest approach point search process is performed on a plurality of convex polyhedrons that form the non-convex polyhedron thereafter. Approach point search method. 4. The method according to claim 3, wherein after the convex hull is released, when the surface convex polygon of virtuality = 1 does not interfere with other objects, the convex hull is restored to perform the closest point search process. Approach point search method. 5. When searching for the closest point between non-convex polyhedrons, the smallest convex polyhedron (convex hull) that encloses the non-convex polyhedron is generated, and the polygons forming the convex hull are divided into triangles. The closest approach point search method according to claim 1, wherein directed graph type structure data is created with the minimum unit of polygon as a triangular polygon, and the closest point search between non-convex polyhedra is performed using the directed graph type structure data of the convex hull. 6. A triangle polygon with a virtuality of 1 when the triangular polygons forming the convex hull and the original polygon of the non-convex polyhedron match, and a virtuality of 1 when they do not match. 6. The closest approach point search method according to claim 5, wherein when the object interferes with another object, the convex hull is released, and thereafter the closest point search process is performed on a plurality of convex polyhedrons forming the non-convex polyhedron. 7. The closest approach point according to claim 6, wherein the convex hull is restored and the closest point search processing is performed when the triangular polygon having the virtuality of 1 does not interfere with another object after the convex hull is released. Search method. 8. A closest point up to a shape formed by a subset having p points on a difference convex polyhedron which is a difference set of two convex polyhedrons as an element is obtained, and a position vector of the closest point is obtained. Evaluate the inner product with the position vector of the lattice point of each convex polyhedron, and based on the evaluation result, determine whether the closest point matches the closest point from the origin to the differential convex polyhedron. Change the set and finally find the closest point from the origin to the difference convex polyhedron to find the closest point of each convex polyhedron. In the closest point search method, each surface polygon of the convex polyhedron is made into a triangle. Directed graph structure data obtained by dividing and arranging the grid points and sides that are elements of the triangle polygon under each triangle polygon, and arranging the grid points and the triangle polygons configuring the side below the side, respectively. Express each convex polyhedron by , Determining whether the closest point on each convex polyhedron corresponding to the closest point of the shape formed by the subset is on a grid point, on a side, or on a triangular polygon, If it exists on a grid point, the triangular polygons that compose the grid point are obtained from the directed graph structure data, and the grid points of the triangular polygon are used for the inner product evaluation. If it exists on the side, the directed graph structure data Then, the triangular polygons that form the sides are obtained, and the lattice points of the triangular polygon are used for the inner product evaluation. If they exist on the triangular polygon, the lattice points of the triangular polygon are used for the inner product evaluation to obtain the difference from the origin. A method for finding the closest point on each convex polyhedron by finding the closest point to the convex polyhedron. 9. A closest point search preprocessing method for checking the interference between the convex polyhedrons by continuously searching for the closest point between them, by inputting vertex coordinates of all polygons covering the convex polyhedron, Proximity with a data structure in which the vertices of each polygon are linked in the first direction (next direction), and the vertices that are connected to each vertex via polygon sides are linked to the vertices in the second direction (branch direction) A pre-processing method for searching for the closest point, which is characterized by creating and outputting a point linear list. 10. The proximity point linear list is stored as a file in an external storage medium, and a file of a predetermined proximity point linear list is read out and expanded in the system memory when necessary. Preprocessing method for searching for the closest point of. 11. A closest point search pre-processing method for checking interference between the convex polyhedrons by continuously searching for the closest points between them, by inputting vertex coordinates of all polygons covering the convex polyhedron, While defining the reference vertex on the list, a first next direction larger than the X coordinate value of the reference vertex, a second next direction smaller than the X coordinate value, a third next direction larger than the Y coordinate value, and a fourth smaller than the Y coordinate value. A next direction, a fifth next direction larger than the Z coordinate value, and a sixth next direction smaller than the Z coordinate value are defined, and each axis coordinate value of the reference vertex and each vertex (target vertex) connected to the reference vertex by a polygon edge. The axis coordinates are compared with each other to find the next direction to be linked according to the magnitude, and the target vertices are linked in the order of being closer to the reference vertex in the next direction. If the coordinate value of the target vertex in the direction is equal to the coordinate value of the other vertex already linked, the coordinate values of the axes of the other vertex and the target vertex are compared, and the next direction according to the magnitude is calculated. , The closest approach, characterized in that the target vertices are linked in the order of being closer to other vertices already linked in the next direction, and a group of vertices connected to each vertex via polygon edges is arranged to create a near-point multi-tree list. Pre-processing method for point search. 12. The near-point multi-branch tree list links vertices of each polygon in a first direction (next direction), and a group of vertices connected to each vertex via polygon sides in a second direction (branch direction). 12. The closest approach point search preprocessing method according to claim 11, wherein the closest point linear list having a data structure linked to the vertices is converted and output. 13. A closest point search method for checking the interference between the convex polyhedrons by continuously searching for the closest points between the convex polyhedrons, in which the vertex coordinates of all polygons covering the convex polyhedron are input and the vertices of each polygon are input. Is linked in the first direction (next direction) and a group of vertices connected to each vertex via polygon sides is linked to the vertex in the second direction (branch direction). Created, the vertex closest to the closest point obtained latest is obtained from the close point linear list, the closest point at the next time is searched from these vertexes, and the interference check is performed. Approach point search method. 14. A closest approach point search for interfering between non-convex polyhedrons by disassembling each of the first and second non-convex polyhedrons into a convex polyhedron and continuously searching for closest points between the convex polyhedrons. In the method, for each convex polyhedron, the vertices of all polygons covering the convex polyhedron are linked in a first direction (next direction), and a group of vertices connected to each vertex via polygon sides is linked in a second direction (branc).
In the h direction), a near-point linear list having a data structure linked to the vertices is created, and for each non-convex polyhedron, among the vertex coordinate values of the non-convex polyhedron, the maximum coordinate value and the minimum coordinate value in each axis direction are generated. The coordinate values are obtained, an envelope sphere that encloses the non-convex polyhedron is generated based on the maximum coordinate value and the minimum coordinate value, and it is checked whether the envelope spheres of the first and second non-convex polyhedrons interfere with each other. The closest point between the convex polyhedrons obtained by decomposing the convex polyhedron is searched for, and the vertex closest to the latest closest point is obtained from the adjacent point linear list,
A method for searching for the closest point, wherein the closest point at the next time is searched from among these vertices, and interference is checked using the one with the shortest distance between the closest points between each convex polyhedron. 15. A minimum convex polyhedron (convex hull) that encloses each non-convex polyhedron is generated, and after the envelope spheres of the first and second non-convex polyhedrons interfere with each other, first and second non-convex polyhedrons are generated. After checking whether the convex hulls of the polyhedron interfere with each other, and after the first and second convex hulls interfere with each other, the closest points between the convex polyhedrons obtained by decomposing the non-convex polyhedron are searched for interference. 15. The closest approach point search method according to claim 14, wherein a check is performed. 16. A closest approach point search for performing interference check between the non-convex polyhedrons by disassembling each of the first and second non-convex polyhedrons into a convex polyhedron and continuously searching for a closest approach point between the convex polyhedrons. In the method, for each convex polyhedron, the vertices of all polygons covering the convex polyhedron are linked in a first direction (next direction), and a group of vertices connected to each vertex via polygon sides is linked in a second direction (branc).
A near-point linear list having a data structure linked to the vertices in the h direction) is created, and the smallest convex polyhedron (convex hull) that encloses each non-convex polyhedron is generated. It is checked whether the convex hulls of the convex polyhedron interfere with each other, and after the interference, the closest points between the convex polyhedrons are searched for, and the vertices close to the latest closest point are found from the adjacent point linear list. The closest approach point search method is characterized in that the closest point at the next time is searched from among, and the interference check is performed using the one having the shortest closest point distance between each convex polyhedron. 17. After the convex hulls interfere with each other, one convex hull is released and each convex polyhedron obtained by decomposing the non-convex polyhedron and the other convex hull are checked for interference. After the interference of the other convex hull, the other convex hull is released, and the interference check is performed by searching for the closest point between the convex polyhedra obtained by decomposing each non-convex polyhedron. The closest approach point search method according to claim 16.