JP3316092B2 - Closest point search device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to collision avoidance and path planning in the operation of robots and self-propelled vehicles (path planning).
The present invention relates to an apparatus for searching for the closest point which can be applied to a computer. In particular, it is possible to determine whether a plurality of shape models (CG models) of objects constructed on a computer are separated from each other, in contact with each other, or interfere with each other. Further, the present invention relates to an apparatus for searching for a closest approach point which can calculate a closest approach point, a contact point, and a distance between objects in real time. The present invention provides a CAD system for machine design, path generation for mobile robots such as manipulators and self-propelled vehicles, animation creation in multimedia,
It can be applied to various fields using computer graphics such as game software.

[0002]

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

[0003] If the closest point and the distance between objects can be measured, a robot or a self-propelled vehicle can be moved while avoiding obstacles. You can run. For this reason, there is a demand for a method of searching for a point of closest approach between objects in sequential collision avoidance of robots and self-propelled vehicles and in advance path planning. That is, when there are a plurality of objects, it is determined whether they are separated from each other, in contact with each other, or interferes with each other, and the closest point between the objects (in the case of contact or interference, , A contact point or an interference point) and a closest approach point search method for efficiently calculating a distance.

The basic approach to the closest point search problem is a method in which shape, position, and orientation data of a target object is loaded on a computer and solved by elementary geometric calculation. Usually, a graphic simulator used in the CAD field uses a planar convex polygon (convex polygon).
Are attached to represent one object. Therefore,
The simplest method for checking the interference state between two objects is to search for the closest approach point between the convex polygons constituting each object for all the combinations of the convex polygons. Specifically, for each convex polygon constituting two objects arbitrarily arranged in space, the closest point is searched for each grid point (vertex), side, and surface, and the closest approach distance is determined. 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)} . O () is a function indicating the order of the calculation load.

The development of algorithms for reducing the computational load of O (M ₁ · M ₂ ) has been studied mainly in the field of computational geometry, and O (MlogM) (M = M ₁ + M ₂ ) An algorithm having such an asymptotic characteristic (when M ₁ and M ₂ are very large) has been developed. Although this type of algorithm is theoretically correct, both focus on asymptotic properties,
There is no practical discussion on how much the computational load is reduced when M ₁ and M ₂ are of a practical size, and it cannot be said that it is a truly practical algorithm. On the other hand, historically,
A method using a Voronoi diagram that connects the perpendicular bisectors between the grid points to show the proximity of each grid point, or occupies the object by dividing the three-dimensional space into eight quadrants one after another A method of searching for the closest approach point using an oct-tree method for converting an area into a database is also known. Each of these methods is effective when the object is statically constant, and is not suitable when the object dynamically changes one after another due to disassembly or assembly.

Now, 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 for computational geometry, etc., the object to be handled is limited to a convex polyhedron (see FIG. 69 (a)). However, in practice, many interference problems with the non-convex polyhedron occur as shown in FIG. Therefore, it is necessary to extend the closest point search algorithm to a non-convex polyhedron. The convex polyhedron is a polyhedron in which a line connecting any two points inside the polyhedron is included in the polyhedron.

2) Extension to non-single connected polyhedron When assembling a truss or plumbing, it is necessary to consider the interference with a perforated object. 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 by a combination of multiple polygons on a graphic simulator. FIG. 69 (d) shows the 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 increase the approximation accuracy, or to treat the curved surface analytically using a spline surface or the like.

[0010] 4) Responsiveness to environmental fluctuation The object handled in the interference problem is not always stationary, and generally the environment dynamically fluctuates through operations such as disassembly, transportation, and assembly. Combining convex polyhedrons to assemble a non-convex structure often occurs. Further, 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 polyhedrons (generally a non-convex object). At this time, when trying to grasp the target object OBJ with the robot hand RBH at the tip of the arm AM as shown in FIG. 70 (a), 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 able to respond flexibly and quickly to such dynamic environmental changes.

5) Response 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 handling is more difficult with shape change. For this reason, Professor Gilbert of Michigan University has proposed an extremely practical method (called the Gilbert method) for the search for the point of closest approach between convex polyhedrons. This Gilbe
According to the rt method, the computational load of the algorithm is O.sub.0 for most convex polyhedral combinations with very pathological exceptions.
(M ₁ + M ₂ ). The Gilbert method is extended to a non-convex polyhedron by considering the non-convex polyhedron as a set of a plurality of convex polygons. Hereinafter, the Gilbert method will be described in detail.

[0010] Finding the closest point between convex polyhedrons using the Gilbert method
Search algorithm (a) Object representation method and distance between objects Consider a convex polyhedron X in a three-dimensional space. At this time, an arbitrary point x in X is a lattice point (vertex) xi∈ located at the boundary of X.
It can be expressed as follows using X. x = Σλi · xi (i = 1 to m): xi∈X, λi ≧ 0 λ ₁ + λ ₂ +... + λm = 1 (1) The above equation is expressed as a set of lattice points {xi: i = 1,2, .. May be defined as a convex polyhedron spanned by m｝. {xi} is called the base of the convex polyhedron X. Now, two convex polyhedrons K ₁ and K ₂
think of. At this time, the closest approach distance between the two objects is defined as follows.

D (K ₁ , K ₂ ) = min ｛| xy−: x∈K ₁ , y∈K ₂ ) (2) where x and y are position vectors, and | xy− = {(X ₁ −y ₁ ) ² + (x ₂ −y ₂ ) ² + (x ₃ −y ₃ )} ² . Therefore, the problem of finding the point of closest approach between two convex polyhedrons is to find x and y that satisfy equation (2) by the following equations. x = {λi · xi (i = _{1 to} m ₁ ): xi∈K ₁ , λi ≧ 0 λ ₁ + λ ₂ +... + λm ₁ = 1 y = {μi · yi (i = 1 to m ₂ ): yi} K ₂ , μi ≧ 0 μ ₁ + μ ₂ +... + Μm ₂ = 1 (3) When simply considered, in equation (3), since both λ and μ are variables, the calculation load is O (M _1. M ₂ ). Equation (2) can be rewritten as follows.

The union and difference sets of arbitrary objects K ₁ and K ₂ are represented by K
_{1 ± K 2 = {x ±} y: x∈K 1, y∈K 2} when 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. 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. Object. Equation (4) shows that the search for the closest approach point
This is equivalent to the problem of finding the closest point to the polyhedron K from. When both the polyhedrons K ₁ and K ₂ are convex polyhedrons, the polyhedron K is also a convex polyhedron, and a set Z of lattice points constituting the convex polyhedron K is given below.

Z = ｛zi = xj−yk: xj∈K₁, Yk∈K_Two, I = 1,2, ... m₁m_Two  j = 1,2, ... m₁  k = 1,2, ... m_Two｝ (5) Summarizing the above, the following conclusions are drawn. Sand
Chi, "Two convex polyhedrons K₁, K_TwoFor finding the closest point between
The title is a convex polyhedron K (= K₁-K_TwoThe best to
Equivalent to the problem of finding the approach point. Where K is m₁m_TwoPieces (m₁:
K₁Grid points of m _Two: K_TwoLattice points ｛zi =
xj-yk} is a convex polyhedron. "

(B) Outline of Gilbert's Method From the conclusion in (a), the problem of finding the closest point between two convex polyhedrons K ₁ and K ₂ is the problem of finding the closest point from one point O to convex polyhedron K. Is returned to The Gilbert method uses this fact and a function called a support function described below. Support function hx for convex polyhedron
(η): R ³ → R is defined as follows. hx (η) = max {xi · η: i = 1 to m} (6) where {xi} is a set of lattice points serving as a base of the convex polyhedron X, and denotes a vector inner product. , And R
³ → R means conversion from three dimensions to one dimension. Therefore, the support function hx (η) in 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 determined. ing. Now, assuming that a 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 of the closest approach point search by the Gilbert method is O (M ₁ + M ₂ ).
Becomes The reason is based on the fact that the following rule is satisfied for the support function hk (η) and the position vector sk (η) of the difference set K of the convex polyhedrons K ₁ and K ₂ . _{hk (η) = hk 1 (} η) + hk 2 (-η), sk (η) = sk 1 (η) -sk 2 (-η) (8) above equation, the m ₁ m ₂ grid points Convex polyhedron K = K ₁ −K ₂
Mean that the support function for is composed of the sum of the support functions for the convex polyhedrons 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 closest point search by the Gilbert method is that the support function hx (η) is repeatedly used to gradually approach the closest point. That is, the Gilbert method includes the following four processes.

(C) Algorithm for searching for the closest point by the Gilbert method 1) Initialization For the convex polyhedrons K ₁ and K ₂ , let K be the difference convex polyhedron K ₁ -K ₂ . Take arbitrary points in the convex polyhedron K and denote them as y ₁ , y ₂
... Yp と す る K. Incidentally, y ₁ , y _2, ... Yp do not necessarily have to be base lattice points of the convex polyhedron K. p is generally 1 ≦ p ≦ 4. At this time, a set V of initial lattice points
Let _k (= V ₀ ) be V _k = {y ₁ , y ₂ ... yp}, k = 0.

2) Search for the closest point to the basic polyhedron With respect to a set Vk of lattice points consisting of the number of elements p (four or less), ν _k = ν (coV _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 a vector (position vector) of the point of closest approach to.

3) Determination of closest approach point A function g _K (x) for 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 a given point on the convex polyhedron K, where x is the position vector of the point. The second term on the right side means an inner product of the lattice point position vector closest to the origin in the vector x direction and the vector -x. In other words, h _K (−x) is the minimum value of the inner product of the position vector of the grid point and x. g _K (x)
Is the determination function of the closest approach point. If x is the closest approach point from the origin O to K, then g _K (x) = 0 only at that time. Note that g _K (x) can be proved to be a function of determining the closest approach point, but is omitted. See “IEEE JOUNAL OF ROBOT” for details.
ICS ANDAUTOMATION, VOL.4, NO.2, APRIL 1988, p.193
~ 203 `` A Fast Procedure for Computing the Distance
Between Complex Objects in Three-Dimensional Spac
Please refer to “e”. From the above, if ν _k obtained by equation (9)
On the other hand, if g _K (ν _k ) = 0 (10), ν (K) = ν _k , and the closest approach point search process ends.

4) Increment of k If equation (10) does not hold, k is incremented. That is, V _{(k + 1) is set} to V _{(k + 1)} = V _k ′ ∪ ｛s _K (−ν _k )} (11). Here, 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) does not hold, k is incremented by the expression (11), the process returns to the step 2), and the subsequent processing is repeated until the expression (10) holds.

(D) Application of closest point search algorithm by Gilbert method In order to deepen the understanding of the closest point search algorithm by Gilbert method, the closest point search will be described with reference to FIG. In FIG. 72, the initial value V ₀ = {z ₁ , z ₂ , z ₃ }
And then, the [nu ₀ when obtaining the point of closest approach vector in V _0. At this time, since the expression (10) is not satisfied, k is incremented. V ₁ = V _{0 is' ∪ {s k (-ν 0} )} = V 0 '∪ {z 4}, _{also, V 0' = {z 2} , z 3} from the V ₁ = {z
_2, z _3, a z _4}. When the closest approach point vector at V ₁ is obtained, ν ₁ is obtained. At this time, since the expression (10) is not satisfied, k is incremented.

V ₂ = V ₁ ′ {s _k (−ν ₁ )} = V ₁ ′ {z ₅ }, and V ₁ ′ = {z ₃ , z ₄ }, so that V ₂ = ｛Z
_3, z _4, the z _5}. When the closest approach point vector in V ₁ is obtained, it becomes ν ₂ , and this ν ₂ satisfies the expression (10),
ν ₂ becomes the closest approach point vector, and ν ₂ = ν (K) ∈co {z ₄ , z ₅ }. As a result, the closest approach distance d is d = | ν ₂ |. Let's do the same with different initial values. In FIG. 72, when the initial value V ₀ = {z ₂ } and the closest point vector at V ₀ is determined, ν ₀ ′ (= z ₂ ). At this time, (1
Since equation (0) is not satisfied, k is incremented. V ₁ = V ₀ ′ ∪ ｛s _K (−ν ₀ ′)} = V ₀ ′ ∪ ｛z ₅ 、, and V ₀ ｛= ｛z ₂か ら, V ₁ = ｛z ₂ , z
₅ ｝.

When the closest point vector at V ₁ is obtained, it becomes ν ₁ '. At this time, since the expression (10) is not satisfied, k is incremented. V ₂ = V ₁ ′ ∪ ｛s _K (−ν ₁ ′)} = V ₁ ′ ∪ ｛z ₄ 、 and V ₁ ′ = {z ₂ , z ₅か ら, so that V ₂ = ｛z
_2, z _4, the z _5}. Determining points of closest approach vector in V ₂ When ν ₂ '(= ν _2), and this [nu _2' (10)
The equation is satisfied, and ν ₂ becomes the closest point vector, and ν ₂ ′ = ν ₂ = ν (K) ∈co ｛z ₄ , z ₅ ｝. As a result, the closest approach distance d is d = | ν ₂ |, and the same result as when the initial value V ₀ is V ₀ = {z ₁ , z ₂ , z ₃ } is obtained.

(E) Discussion In the above algorithm, the computations required are (9) and (1)
0) and (11). First, equation (9) means that this means that the closest point from one point O to a point, a side, a plane, or a tetrahedron is calculated. This part is not related to the complexity of the convex polyhedron, and can be executed by preparing a subroutine as described later in advance. Next, the calculation of equation (10), g _K (ν _k )
In calculating h _K (−ν _k ), the decomposition rule of equation (8) is used. This part is calculated only by evaluating the inner product of the convex polyhedrons K ₁ and K ₂ with respect to the base lattice point (the inner product of the position vector of the base lattice point and ν _k ), as shown in equation (6). That is, h _K (−ν _k ) is to find the minimum of the inner product between the position vector of the base lattice point and ν _k , and therefore, the calculation load of this part is O (M ₁ + M ₂ ). .

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

The initial lattice point (initial value) of the Gilbert method
Although V ₀ is generally arbitrary, it is efficient to start from a lattice point in the gravity center difference direction 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 lattice point of K ₁ z _c2 = Σ (yi / M ₂ ) (i = 1 to M ₂ ) yi: Base lattice point of convex polyhedron K ₂ .

(F) The lemma of the Gilbert method In step 2) of the Gilbert method, the point of closest approach from one point (origin O) to a convex polyhedron (point, side, surface, tetrahedron) spanning four or less grid points An algorithm for finding a vector was needed. The lemma described below also holds for a convex polyhedron spanned by five or more grid points, but is particularly efficient when the number of grid points is small. 1) Lemma 1 For a set of lattice points Y = ｛y ₁ , y ₂ ,... Ym 3R ³
An arbitrary subset of Y is represented by Ys = {y _i : i∈Is⊆ ｛1,2,2
.. M, the complement of Is is Is'. At this time, the sequence Δ _i (Ys) is created based on the following rule. Δ _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, there is a subset of Y satisfying the following property, Ys. (1) For each i where i) Is, Δ _i (Ys)> 0
(I∈Is) (2) For each j for which j∈Is, Δ _j (Ys∪
{Y _j }) ≦ 0 (j∈Is)

2) Lemma 2 For a set of lattice points Y = ｛y ₁ , y ₂ ,... Ym｝ ∈R ³ ,
When the convex polyhedron spanned by Y is coY and the closest point vector from the origin O to coY is ν (coY), ν (coY)
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 = {yi: i∈Is} Δ (Ys) = ΣΔ i (Ys) (i∈Is) detailed proof of the lemma is omitted here, The meaning of the lemma is easy to understand. Let's apply the above lemma to a tetrahedron. As shown in FIGS. 73 (a) to 73 (d), the closest approach vector between the one point O and the tetrahedron is represented by each lattice point, side,
It may be in a plane or inside a tetrahedron. Therefore, if the subset Ys of Y consists of one point,
The case of two points corresponds to the case where the closest point exists on the side, and the case of three points corresponds to the case where the closest approach point exists on the surface. The case of four points corresponds to the case where the origin O exists inside the tetrahedron. .

When Lemma 1 and 2 are actually executed, the following algorithm is used. (g) The lemma algorithm of the Gilbert method For a set of lattice points Y = ｛y ₁ , y ₂ ,... ym｝ ∈R ³ ,
The subset of Y is represented by Ys = {y _i : i∈Is⊆ ｛1,2,.
Let m 'and the complement of Is be Is'. Also, s = 1, 2,
.. Σ indicate all subsets of Y. At this time, the algorithm 2) of the Gilbert method is as follows.

[0029] _{2) 1 1 → s 2)} 2 If a delta _i for each i of i∈Is (Ys)> 0 (i∈Is ), and, for each j for j∈Is If Te _{Δ j (Ys∪ {y j}} ) ≦ 0 (j∈Is), λ i = Δ i (Ys) / Δ (Ys), Ys = {y i: i∈Is} Δ (Ys) = Stop as iΔ _i (Ys) (i∈Is) ν (co Y) = Σλ _i y _i (i∈Is) (12) ′, and thereafter execute algorithm 3) of the Gilbert method. 2) ₃ However, if the condition of 2) ₂ is not satisfied, s is incremented and step 2) ₂ is executed. That is, 2) 2 until _second condition is satisfied) Repeat steps _2, 2) _3, 2) ₂
Is satisfied, ν (co Y) is calculated, and then Gilber
Execute algorithm 3) of t method.

(I) Numerical test The closest point search algorithm by the Gilbert method can be summarized into a subroutine having the following inputs and outputs. Input: Coordinate values of each grid point of the biconvex polyhedron Output: Coordinate values of the closest approach point, closest approach distance FIG. 74 is a numerical test example when the Gilbert method is executed in Fortran and applied to various convex polyhedrons. An asterisk indicates a case where two objects are approaching (free), an open circle indicates a case where the two objects are in contact, and a square black mark indicates a case where the two objects are interfering. The computer used is a Harris 800, which is a bit faster than the VAX 780 and has the performance of a current personal computer.

M shown on the horizontal axis of FIG. 74 is the number of grid points, and EF shown on the vertical axis is an 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 integrations, N _A is the number of additions, N _D is the division number ,
N _C is the number of comparison operations, t _M , t _A , t _D , and t _C are the calculation time required for each. For Harris 800, t _M = 3.8 μm
s, t _A = 2.1 μs, t _D = 6.7 μs, and t _C = 1.7 μs. EF
Can be used as a machine-independent index without greatly fluctuating depending on the computer.
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, a speed of one digit or more can be expected.

(J) Conclusion 1) From the above, the search for the closest approach point by the Gilbert method is performed when the total number of lattice points of two convex polyhedrons is M, when there is interference, when there is contact, and when free. Each has a computational load approximately proportional to M, and the proportionality constant is EF
The value falls within the range of 14 to 19 in terms of the value of / M. 2) When applying the Gilbert method to two convex polyhedrons on a workstation of about 1M Flops, the total number of grid points is 20
Even at about 0, the closest approach point can be calculated in a few ms.

[0033]

As described above, according to the Gilbert method, there is an effect that the closest point search between two objects can be efficiently executed in a short time. However, the Gilbert method has the following limitations or constraints. 1) Limit of Gilbert's method: Support for continuous search problem Consider the case where the closest point between two convex polyhedrons is continuously chased. The problem of continuously following the point of closest approach between two convex polyhedrons is called a continuous search problem. With the movement of the object, the point of closest approach transitions in each convex polyhedron so as to walk from the surface to the side, from the side to the vertex, and from the vertex to the surface. Therefore, if the closest point is obtained at a certain point in time, the closest point at the next point in time should be near the previous closest point. In other words, the search for the point of closest approach is a local problem and should be independent of the complexity of the entire convex polyhedron.

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

2) Constraints of Gilbert's Method: Correspondence to Nonconvex Polyhedron Gilbert's method is an algorithm for searching for the closest point between convex polyhedrons. For this reason, in order to increase the practicality, it is necessary to extend the object to a non-convex polyhedron, a non-single connected polyhedron, and an object having a free-form surface. When the closest point search between non-convex polyhedrons is performed by the Gilbert method, as shown in FIG. 75, each non-convex polyhedron K1, K2 is divided into a plurality of convex polyhedrons A, B; a, b, c, The closest point search algorithm is applied to all combinations of convex polyhedrons, and the shortest one among the obtained closest distances is selected. However, this 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 an apparatus for searching for a closest approach point which can execute a continuous search problem between objects at high speed with a small calculation load.
To provide.

[0036]

FIG. 1 is a diagram illustrating the principle of the present invention. In FIG. 1 , reference numeral 12 denotes a storage unit that stores convex polyhedron data for specifying two target convex polyhedrons;
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 type structure data, and 15 is a unit that performs a closest point search process between two objects based on the Gilbert method. It is an approaching point search processing unit.

[0037]

In the first method of searching for the closest point, when searching for the closest point of the two convex polyhedrons 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 ₁ ,
To create a directed graph structure data to represent the K _2. The directed graph type structure data includes, under each surface polygon (polygon) of the convex polyhedron, grid points which are elements of the polygon,
Sides are arranged, and grid points and polygons forming the sides are arranged below the sides. Next, the closest approach point search processing unit (processor) 15 executes the closest approach point search process. That is, a point of closest approach to a shape formed by a subset of p points on the difference convex polyhedron, which is a difference set (K ₁ −K ₂ ) of two convex polyhedrons K ₁ and K ₂ , is obtained. The inner product 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 closest point is determined as the difference convex polyhedron (K ₁ − K ₂₎
It is determined whether or not they match the closest approach point. If they do not match, the subset is changed. Finally, the closest approach point from the origin to the difference convex polyhedron is obtained, and the closest approach of each convex polyhedron K ₁ , K ₂ is performed. Find points.

In the inner product evaluation, the closest point search processing unit 15 determines whether the closest point of each convex polyhedron corresponding to the closest point of the shape formed by the subset exists on the lattice point or on the side. Or exist on the polygon. The point of closest approach of each convex polyhedron is 1) When a grid point is present, a polygon constituting the grid point is obtained from the directed graph type structure data, and the grid point of the polygon is used for the inner product evaluation,
2) If it exists on an edge, a polygon constituting the edge is obtained from the directed graph type structure data, and the grid points of the polygon are used for the inner product evaluation. The 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 grid points.

Second Method of Searching for the Nearest Approach Point A surface polygon (polygon) constituting the convex polyhedron is divided into triangles, and lattice points and sides, which are elements of the triangle polygon, are arranged below the triangle polygon. , And creates a directed graph type structure data in which grid points and triangular polygons constituting the side are arranged below the side, and expresses each convex polyhedron. The closest point search processing unit 15 determines whether the closest point of each convex polyhedron corresponding to the closest point of the shape formed by the subset exists on a lattice point, on a side, or on a triangular polygon. Judge whether to do. The point of closest approach of each convex polyhedron is 1)
If it exists on a grid point, a triangular polygon constituting the grid point is obtained from the directed graph type structure data, and the grid point of the triangular polygon is used for inner product evaluation. 2) If it exists on a side, a directed graph type structure A triangular polygon constituting the side is obtained from the data, and the grid points of the triangular polygon are used for inner product evaluation. 3) When the triangular polygon exists on the triangular polygon, the grid points of the triangular polygon are used for inner product evaluation. In this way, the number of grid points constituting the triangle is minimized (3
), The number of grid points applied to the inner product evaluation can be further reduced as compared with the first closest point search method, and the calculation load can be reduced.

Third Nearest Point Search Method When searching for the closest point between non-convex polyhedrons, the smallest convex polyhedron enclosing the non-convex polyhedron (convex hull).
Generate Then, a directed graph type structure data of the convex hull is created, and a first or second closest point search method is applied using the directed graph type structure data of the convex hull to search for a closest point between non-convex polyhedrons. Do. If the surface convex polygon constituting the convex hull coincides with the surface convex polygon of the original non-convex polyhedron, virtuality = 0, otherwise, virtuality = 1 and virtuality = If the surface convex polygon 1 interferes with another object, the convex hull is released,
Hereinafter, the first convex polyhedron constituting the non-convex polyhedron
Alternatively, the second closest point search process is applied to search for the closest point between the non-convex polyhedrons. In this way, it is possible to search for the point of closest approach between non-convex polyhedrons, and to reduce the computational load required for the point of closest approach search processing until the surface convex polygon with virtuality = 1 interferes with another object. Can be reduced. Also, after the surface convex polygon with virtuality = 1 interferes with another object and releases the convex hull, when the surface convex polygon no longer interferes with other objects, the convex hull is restored and the closest approach point is obtained. If the search processing is performed, the calculation load of the closest approach point search processing after restoration can be reduced.

[0041]

[0042]

【Example】

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

An effective measure to reduce the number of calculations of the inner product is to divide the convex polyhedrons K ₁ and K ₂ into convex polyhedrons or polygons having a smaller number of grid points, and to construct a convex polyhedron or a convex polyhedron located near the current closest point This is a method of 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 approach point in the convex polyhedron can be one of the following three cases: 1) existing on a grid point, 2) existing on a side, and 3) existing on a plane.

Therefore, the surface polygon for which the inner product is evaluated for each of them may be limited as follows. That is,
If the closest point is on a grid point, 1) all surface polygons that have the grid point at the apex. 2) If they are on sides, the surface polygon has that side as one side. , 3) If it exists on the surface, the surface polygon on which the closest point is present ... (15) is the surface polygon for evaluating the inner product. That is, the inner product is evaluated only for the grid points (vertexes) constituting the surface polygon shown in 1) to 3) of (15) according to the position where the closest approach point exists (the grid point at which the inner product is minimized is determined). ), Judgment function g
_K (ν _k ) may be calculated. By doing so, 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 Searching for Nearest Point In order to continuously obtain surface polygons required for inner product evaluation according to the above 1) to 3), a data structure for defining a convex polyhedron It needs some ingenuity. FIG. 3 shows an example of a data structure in the case of the hexahedron shown in FIG. 2, and employs directed graph type structure data.
This directed graph type structural data can be expressed as follows when abstracted. 1) Number the surface polygons that make up the convex polyhedron, and assign a polygon node to each one. 2) Below each polygon node, a lattice point node (Vertex node) for arranging all the grid points and all sides that make up the polygon
And an edge node. The set of grid points and the set of edges that make up the polygon are the brother node (brother nod
e) exists as 3) Under the grid point node and the edge node, a polygon having those grid points or sides as constituent elements is allocated as a polygon node. If there are a plurality of polygons, they are assigned as brother nodes.

(C) Method for evaluating inner product of decision function g _K (ν _k ) As described above, when a data structure of a 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 exists on a grid point, Perform inner product evaluation on grid points of the surface polygon corresponding to all connected polygon nodes.2) If the closest point exists on the side, all the points connected below the edge node corresponding to the side are evaluated. The inner product is evaluated for the polygonal lattice points corresponding to the polygon nodes. 3) If the closest point exists on the surface, the inner product is evaluated for the lattice points on the surface. (15) 'When the inner product evaluation is restricted as in (15)', the calculation load of the decision function g _K (ν _k ) is determined by the maximum value of the number of lattice points of the convex polygon on the surface of the convex polyhedron. If L, it can be suppressed to O (L) or less.

(D) Algorithm for Finding the Nearest Point Using the Inner Product Evaluation Method of the Present Invention FIG. 4 is a flowchart of the algorithm for finding the closest point between two convex polyhedrons according to the present invention. First, data for specifying two target convex polyhedrons is input (initial input: environment model setting of convex polyhedron). In this case, data specifying each convex polyhedron is input in the following manner (see FIG. 5). That is, a polygon number P1i (i = 1, 2,... M) is assigned to a surface polygon constituting the first convex polyhedron PH1. Then, the i-th polygon number P1i is input, and thereafter, the coordinate values of the grid points constituting the polygon number P1i and the outward normal direction of the polygon number P1i are input, and all polygons P1i are input.
Polygon number for 1i (i = 1, 2,... M),
Enter the coordinate values of the grid points and the outward normal direction. Note that the coordinate values of the grid points forming the polygon are input clockwise toward the outward normal vector.

Thereafter, similarly, polygon numbers P2i (i = 1, 2, 2) are assigned to surface polygons constituting the second convex polyhedron PH2.
.. N). Then, the i-th polygon number P2i
, And then input the coordinate values of the lattice points constituting the polygon number P2i and the outward normal direction of the polygon number P2i, and enter all the polygons P2i (i = 1, 2,... N).
, A polygon number, grid point coordinate values, and outward normal directions are input (step 101). When the input of the data for specifying each convex polyhedron is completed, directed graph type structure data is created based on the input data (step 10).
2). When the creation of the directed graph type structure data is completed, the Gilbert method is applied to the convex polyhedra PH1, PH2. First, an initial lattice point set V _k (k = 0) is determined (step 103), and a closest point vector v _k is calculated and output for the initial lattice point set V ₀ (step 104).

Next, it is checked whether the closest point on each of the convex polyhedrons PH1 and PH2 corresponding to the closest point exists on the lattice point, on the side, or on the 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). Note that the convex polyhedron P
Let the lattice points on H1 be x _1i and the lattice points on the convex polyhedron PH2 be x
Assuming _2i , equation (12) 'is given by ν (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 PH.
2 is the position vector of the point of closest approach on FIG. Therefore, in the process of calculating the closest approach point vector ν _k , the first right side of the equation (12) ″
By calculating the term and the second term on the right side, the closest point on each convex polyhedron PH1, PH2 corresponding to the closest point vector can be obtained.

When the judgment function is obtained, g_K(Ν_k) = 0
Check (step 106), g _K(Ν_k) = 0
If so, the search for the closest approach point ends. But g_K(Ν_k) Is 0
Otherwise, k is incremented and the next set of grid points V₁
Is output as the closest approach point vector (step 10).
7). Thereafter, by repeating the processing after step 105,
Finally g_K(Ν_k) = 0, and the closest approach distance and the closest approach point
I get 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 equation (12) '.
Therefore, the distance from the origin O to the closest point is the closest distance.
Becomes At this time, the first and second terms on the right side of the equation (12) ″
Find the closest point on each convex polyhedron PH1, PH2
Can be.

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

From the input unit 11, the convex polyhedrons PH1 and PH2 are
The data to be specified is input and stored in the storage unit 12. Directed
The graph type structure data creating unit 13 performs
Create directed graph type structure data and store it in the storage unit 14
You. Closest approach when creation of directed graph type structure data is completed
The point search processing unit 15 provides Gi for the convex polyhedrons PH1 and PH2.
Apply lbert method. First, the initial grid point set V_k(K =
0), and the initial lattice point set V₀About the closest approach
Kutor ν_kIs calculated. Next, the closest approach vector ν _kIn response
The closest point on each convex polyhedron
Check whether the point is on a grid point, on an edge, or on a surface,
Reads the existence position (lattice point, side, surface) for inner product evaluation grid point
Input to the input unit 16. The reading unit 16 is located at the position of the closest approach point.
Grid points used for inner product evaluation determined based on a directed graph
Nearest point search processing by reading from the type structure data storage unit 14
Input to the unit 15. The closest approach point search processing unit 15 is
Inner product evaluation using the grid points
_K(Ν_k) Is calculated. Then, if the decision function is found,
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.
I do. But g_K(Ν_k) Is not 0, k is ink
The next grid point set V₁About the closest point Bek
Output torque. Thereafter, similar processing is performed, and finally
To g_K(Ν_k) = 0, the closest approach distance and the closest approach point are output
Is done. Note that if the convex polyhedrons PH1 and PH2 move,
Based on the movement data for each fixed time, each convex polyhedron
The grid point position is obtained, and the above processing is performed.

(B) Second Method of Searching for the Nearest Point between Convex Polyhedra (a) Principle In the first method of searching for the closest point, the convex polyhedron, which is the target object, is divided into surface convex polygons each wrapping the convex polyhedron. The calculation load was on the order of the number of lattice points of the convex polygon. Further elaborating the concept of the first closest approach search method, it is clear that if the surface of the convex polygon is completely covered with the triangular polygon, the number of times of one inner product evaluation is minimized. Fig. 7 (a)
Is an explanatory view of a state in which the point of closest approach to the convex polyhedron K moves on the surface polygon in accordance with the movement of the origin O. Origin O
The closest approach point S changes from the convex polygon P1 to the convex polygon P according to the movement of
2 → Continuously changes 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 can be changed to the triangle T11 according to the movement of the origin O.
T12 → T21 → T22 → T23 → T24 → T25 → T
26 → T31 continuously changes.

Therefore, there is no problem even if all the surface convex polygons constituting the convex polyhedron are divided into triangles and the first closest approach 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 ′ exists on the side E11 in FIGS. 7A and 7B, in the case of FIG. 7A, the grid points used for inner product evaluation are V1 to V6. There are six, but in the case of FIG. 7 (b), only four of V1, V3, V4, and V6 are sufficient, and the number of times of one inner product evaluation can be reduced. As described above, if the target convex polyhedron is subjected to preprocessing to form a data structure in which all surface convex polygons are divided into triangular polygons, the calculation load for continuously evaluating g _K (ν _k ) is Irrespective of the complexity of the convex polyhedron to be obtained.

Several algorithms for dividing an arbitrary convex polygon into triangular polygons 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. The strings are L1 to L6
Is a line segment for dividing into triangles as shown in FIG. The calculation load of this algorithm is O (n ³ ), where n is the number of grid points of the first polygon. For an algorithm to convert polygons into triangles, see 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〜
See 233, 1984.

As described above, the method for dealing with the continuous search for the closest approach point (second closest approach search method) can be summarized as follows. 1) Preprocessing 1: Triangulation of each surface convex polygon surrounding the target convex polyhedron (Triangulation algorithm) 2) Preprocessing 2: Directed graph as in the first closest point search method using triangles Create type structure data. 3) Inner product evaluation: The range of inner product evaluation in g _K (ν _k ) is limited according to (15) ′.

(B) Second Nearest Point Search Algorithm of the Present Invention FIG. 9 is a flowchart of the closest point search algorithm according to the second closest point search method of the present invention. First, data for specifying two target convex polyhedrons is input (initial input: environment model setting of convex polyhedron). Data for specifying each convex polyhedron is input in the following manner (see FIG. 5). That is,
The number P1 is assigned to the surface polygon constituting 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 constituting the polygon of the number P1i and the outward normal direction of the polygon are input, and similarly, all the polygons P1i (i =
For 1, 2,... M), a polygon number, grid point coordinate values, and outward normal directions are input. Note that the coordinate values of the grid points forming the polygon are input clockwise toward the outward normal vector. Similarly, the polygon numbers P2i (i = 1, 2,...) Are assigned to the surface polygons constituting the second convex polyhedron PH2.
・ ・ N) Then, the i-th polygon number P2i is input, and thereafter, the coordinate values of the grid points constituting the polygon number P2i and the outward normal direction of the polygon number P2i are input, and all polygons P2i (i = 1, 2,. .. N), a polygon number, grid point coordinate values, and outward normal directions are input (step 201).

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

Next, the closest approach point vector ν_kAccording to each
Find the closest points on the convex polyhedron and find the closest points
Examine whether it exists on a child point, on an edge, or on a surface, and
(15) ′ based on the position
Determine and determine function g_K(Ν_k) (Step 20)
6). If the judgment function is obtained, g_K(Ν_k) = 0
Check (step 207), g _K(Ν_k) = 0 if closest
The near point search ends. But g_K(Ν_k) Must be 0
If k is incremented, the next set of grid points V₁About
Then, the closest approach point vector is output (step 208). Less than
By repeating the processing from step 105 onward, g
_K(Ν_k) = 0, and the closest approach distance and the closest approach point are obtained.
In addition, if the convex polyhedrons PH1 and PH2 move, every predetermined time
Grid points of each convex polyhedron after moving based on the moving data of
And the above processing is performed.

(C) Configuration of Second Nearest-Point Searching Apparatus of the Present Invention FIG. 10 is a block diagram of an apparatus for implementing the second closest-point searching method of the present invention. Have the same reference numerals. 6 is different from FIG. 6 in that: 1) a triangular division unit 17 for dividing a convex polygon constituting a convex polyhedron into triangles based on convex polyhedral data for specifying the convex polyhedron is provided; 2) a directed graph type The structure data creation unit 13 creates directed graph type structure data using each triangle as a polygon node and stores it in the storage unit 14.

(D) Effect of the second closest approach point search method According to the second closest approach point search method, the following effects 1) and 2) can be obtained. 1) High speed: When following the closest approach point continuously, the calculation load can be kept almost constant irrespective of the complexity of the target convex polyhedron except for the time required for initialization. The constant value is substantially equal to the time for searching for the closest point between the triangular polygons. 2) Application to free-form surfaces: When a free-form surface is expressed by laminating triangular polygons, the time for searching for the closest approach point is always constant even if the number of polygons is increased in order to increase the accuracy of the expression.

(C) First Method of Searching for the Nearest Point between Non-convex Polyhedrons (a) Principle The basic policy for extending the Gilbert method to a non-convex polyhedron is to set the non-convex polyhedron to a set of convex polyhedrons. An object of the present invention is to reduce the number of combinations of convex polyhedrons that must be checked for interference when captured. Of course, the Gilbert method is used to check for interference between convex polyhedrons. Merging (mergin) for multiple convex polyhedra to reduce the number of convex polyhedra
g) is introduced. The merging of the object A and the object B is the smallest convex object including A and B (Copnvex hull: convex hull)
It is to constitute. FIG. 11 shows that the non-convex polyhedron K is divided into two convex polyhedrons A and B, and A and B are merged.
This is an example in which a minimum convex object (convex hull) C including the following is configured. When the convex hull is generated, the interference check of the non-convex polyhedron results in the interference check of the convex hulls (convex polyhedrons), and the first closest point search method of the present invention can be applied.

In forming the convex hull C, an index called virtuality is introduced. The virtuality is a flag for identifying a virtual polygon generated by merging a plurality of convex polyhedrons. In the example of FIG. 11, the virtuality is "for a polygon (polygons 4, 5, 6) extending over two existing convex polyhedrons (cuboids) A and B.
1 ”, and the virtuality is“ 0 ”for other actually existing polygons. Creates effective graph type structure data of a convex hull.FIG. 12 shows directed graph type structure data of a convex hull shown in FIG. A grid point node and an edge node are arranged below, and a polygon node is arranged below each grid point node and the edge node.

(B) Merging Algorithm FIG. 13 is a flowchart of the merging algorithm. The target non-convex polyhedron is divided into two or more convex polyhedrons, and data for specifying each convex polyhedron is input (initial input: environment model setting of the convex polyhedron). That is, the first convex polyhedron PH1
Are assigned polygon numbers P1i (i = 1,
2,... M). Then, the i-th polygon number P
1i, and thereafter, the coordinate values of the grid 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,...) Are input.
For m), a polygon number, grid point coordinate values, and outward normal directions are input. Hereinafter, similarly, the polygon numbers P2i (i = 1, 2) are assigned to the surface polygons constituting the other convex polyhedron PH2.
2,... N) and all polygons P2i (i = 1, 2)
2,... N), polygon numbers, grid point coordinate values,
An outward normal direction is input (step 301).

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

The merging algorithm is an algorithm for creating a convex hull from a plurality of convex polyhedrons and creating directed graph type structure data. Algorithms for creating convex hulls are well known in computational geometry. For the current three-dimensional convex hull, if the total number of grid points is M, the computational load is O (M
The algorithm of log M) is known. For example, F.
P. Preparata and SJ Hong, "Convex hulls of finit
e sets of points intwo and three dimensions ", Com
m. See ACM 2 (20), pp. 87-93, 1977. The merging algorithm operates on relatively stationary convex polyhedrons, and cancels merging when the polygon of virtuality "1" comes into contact with or collides with another object. As a result, the closest point search process is performed on the set state of the lower convex polyhedron. Further, after the merging is released (after the convex hull is released), if there is no interference with another object for a certain period of time, the convex hull decomposed by the interference is recovered by a recovery algorithm (described later).

(C) Activating the Merging Algorithm The merging algorithm is applied to the target object offline in the initial setting, and when the environment starts to change dynamically, that is, a certain convex polyhedron in the environment If has started, the merging process stops temporarily while maintaining the current state, and performs an interference check. Then, when the environment is stopped, a merging process is executed to create a convex hull after the environment is changed, and to create a directed graph type structure data of the convex hull. FIG. 15 is an explanatory diagram of merging processing by the processor in consideration of the above. A flag ms (i) for monitoring the static movement of the convex hull is prepared for all convex hulls. If the static motion flag ms (i) = "1", it is dynamic, ms (i)
== "0" is static and i spans all convex hulls.

As a task of the processor, all m
A state monitoring task Task1 that monitors the value of s (i) to monitor the static motion state of the convex hull, and the first closest approach point search method described above when any of ms (i) is “1”. Task2 (an interference check task) for executing other processing for interference check, and Task3 (for a merging task) for executing merging processing 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.
= "0" is written. Status monitoring task Task
1 monitors the contents of ms (i), and if all are "0", a merging task Task3 is activated to execute a merging process to create a convex hull and create directed graph type structure data. The merging task Task3 stops when one convex hull is formed, and waits for the next activation instruction. On the other hand, any m
If s (i) is "1", in other words, if any convex hull is moving, the interference check task Task2
Performs the interference check and other processing by the first closest approach point search method. Thereafter, the above operation is repeated to execute the interference check.

The above is the case where merging processing, interference check processing, and the like are executed by task switching.
The merging process can be performed sequentially using an ile statement. FIG. 16 is an explanatory diagram of a case where a merging process is executed using a While sentence. While
In the sentence, it is monitored whether ms (i) of all convex hulls is "0", and if all are "0", a merging process is executed to create one convex hull (step 401). After a while, Wh
The ile sentence is escaped, interference check and other processes are executed (step 402), and the While sentence is executed again.
Thereafter, the merging process and the interference check process are repeatedly and continuously executed.

When the environment changes dynamically, for example, FIG.
When the robot arm AM passes through the arch AC, which is a non-convex polyhedron, and grasps the object OB on the opposite side as shown in (1), the arm AM breaks through the convex hull constituted by the arch AC and reaches the object OB. In this case, merging is canceled when the robot arm AM comes into contact with the convex polygon of the virtual hull “1” of the convex hull. After that, the individual convex polyhedrons AC1 to AC1 constituting the robot arm AM and the arch AC will be described.
A check for interference with AC3 is performed, and the robot arm reaches the object OB so as not to contact the arch AC, and grabs the object and transports it to a target location. The convex hull from which merging has been canceled is restored by a recovery algorithm described below. FIG. 18A shows a convex hull CH on the worktable BS and the arch AC.
FIG. 18B shows an example in which an arch AC and an object O are generated.
This is an example in which convex hulls CH2 and CH3 are generated for each of B, and the robot arm AM has a convex hull CH1 composed of a worktable BS and an arch AC, and a convex hull composed of an arch, as shown in FIG. Object OB by piercing the parcel CH2 one after another
, And grasps and transports the object to a target location.

(D) Recovery Algorithm The convex hull decomposed by the interference recovers when there is no interference with another object for a certain period of time. The recovery process operates only on the convex hull in which the data structure in the merging state remains. Therefore, a convex polyhedron set in which the relative positional relationship has moved and the original data structure of the convex hull has been lost is not recovered by the recovery processing, and a new convex hull is formed 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 movement of the convex hull is prepared for all convex hulls. If the static motion flag ms (i) = "1", it is dynamic, ms (i)
== "0" is static and i spans all convex hulls. As a task of the processor, a state monitoring task Tas that constantly monitors all values of ms (i) to monitor the static state of the convex hull.
k1 and Task2 (interference check / recovery task) for executing interference check processing, recovery processing, and other processing by the first closest approach point search method when any of ms (i) is “1”; If ms (i) = "0", that is, if all convex hulls are stationary, there is a Task 3 (merging task) that executes the merging process.

The stationary state of all the convex hulls is monitored by a robot controller (not shown), and ms (i) = “
It is written as 1 "or ms (i) =" 0 ". The status monitoring task Task1 monitors the contents of ms (i), and if all are" 0 ", the merging task Task3 is activated. The processing is executed to create a convex hull and create directed graph type structure data.The merging task Task3 stops when one convex hull is formed, and waits for the next activation instruction.
If s (i) is "1", in other words, if any convex hull is moving, the interference check task Task2
Executes the interference check by the first closest approach point search method, and executes the recovery process and other processes. Thereafter, the above operation is repeated to execute the interference check.

In the recovery process, a convex hull virtuality is used.
When the convex polygon of 1 "comes into contact with another object and the merging is released, it is monitored whether the convex hull no longer interferes with the object,
If no interference continues for a predetermined time after the interference stops, the convex hull is restored. In the example of FIG. 17, when the robot arm AM grasps the object OB and passes through the arch AC, interference between the convex hull and the arm disappears.

The above is a case where the recovery processing is executed by switching tasks, but the recovery processing can be performed sequentially using a While statement. FIG.
0 is an explanatory diagram in the case where recovery processing is executed using a While statement. M of all convex hulls in a While sentence
It monitors whether s (i) is "0", and if all are "0", executes a merging process to create one convex hull (step 501). Thereafter, the While sentence is escaped, interference check processing, recovery processing, and other processing are executed (step 502), and the While sentence is executed again. Thereafter, the merging process, the interference check process, and the recovery process are repeatedly and continuously executed.

(E) Overall processing for searching for the closest point between non-convex polyhedrons FIG. 21 is an overall processing flowchart for searching for the closest point between non-convex polyhedrons. Input data specifying the target non-convex polyhedron (initial input: environment model setting). Step 601 Next, the non-convex polyhedron is divided into convex polyhedrons, and each convex polyhedron P
Create Hi-directed graph type structure data. Further, a convex hull is generated by the merging process, and directed graph type structure data of the convex hull is generated (step 602). When the above initialization processing is completed, a first closest approach point search processing (interference check) processing is executed (step 603). Next, it is checked whether or not interference occurs (step 604). If there is interference, it is checked whether or not the portion of virtuality = “1” has interfered (step 605). In step 606), if the virtuality is "1", merging is canceled (step 607), and the process returns to step 603. Thereafter, until the convex hull is recovered, the closest point searching process is executed for each convex polyhedron constituting the non-convex polyhedron.

On the other hand, in step 604, if there is no interference, a recovery process is executed (step 60).
6). In the recovery process, it is checked whether or not the convex hull whose merging has been canceled exists. If there is, it is checked whether or not it interferes with another object. Then, if the non-interference time of the convex hull whose merging has been canceled is equal to or longer than the set value, the convex hull is restored. However, if it interferes with another object or the non-interference time is not longer than the set value, the next step is executed without restoring the convex hull. If the original convex hull data is lost due to a change in the relative positional relationship between the parts constituting the convex hull, the convex hull is not restored. Next, it is checked whether all parts of the convex hull are stationary (step 609). If not stationary, the process returns to step 603 and the subsequent processing is repeated. A convex hull is created (step 610), and the process returns to step 603 to repeat the subsequent processes.

(F) Configuration of apparatus for searching for points of closest approach between non-convex polyhedrons FIG. 22 is a block diagram of an apparatus for searching for points of closest approach between non-convex polyhedrons. Reference numeral 21 denotes an input unit for inputting data for specifying a target non-convex polyhedron, reference numeral 22 denotes a storage unit for storing the input non-convex polyhedron data, and reference numeral 23 divides the non-convex polyhedron into a plurality of convex polyhedrons. A convex polyhedron division / directed graph creation unit for creating directed graph type structure data for each, a convex hull creation / directed graph creation unit for creating a convex hull of a non-convex polyhedron and creating directed graph type structure data of the convex hull, 25 A storage unit for storing the directional graph type structure data CVD of each convex polyhedron and the directional graph type structure data CHD of the convex hull, 26 is a processor for performing state monitoring, interference check, merging, and recovery processing, and 27 is sent from the robot controller. A memory 28 stores the static motion flag ms (i) and the position data of each object, and a memory 28 stores, for each convex hull, whether or not merging of the convex hull is canceled. 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 a non-convex polyhedron into convex polyhedrons, and generates a directed graph type structure data CVD of each convex polyhedron.
Is created and stored in the memory 25. In addition, the convex hull creation / directed graph creation unit 24 creates a convex hull by merging processing, creates 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-described first closest approach point search processing (interference check) processing using the directed graph type structural data of the convex hull. For a moving object, a grid point position is calculated based on movement data input from the robot control device,
A closest point search process is performed based on the grid point position. Convex hull (virtuality = "1") by closest point search processing
When the interference with the convex hull 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 checks whether the convex hull has been recovered by referring to the release flag FR, and if not recovered, performs the closest approach point search process using the directed flag structure data of each convex polyhedron constituting the non-convex polyhedron. Execute. In addition, the processor 26 executes the recovery process if it does not interfere with the convex hull (virtuality = “1”).

In the recovery processing, the release flag memory 28 is referenced to check whether or not a convex hull whose merging has been released exists. If there is, it is checked whether or not it interferes with another object. For example, the non-interference time T is measured. Then, if the non-interference time T of the convex hull from which merging has been 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 of the convex hulls are stationary, and if not, the above interference check is repeated. When stationary, when the relative positional relationship of the convex polyhedrons constituting the non-convex polyhedron is changing, a merging process is executed to create a new convex hull, store it in the memory 25, and thereafter, Repeat the process.

As described above, according to the method of searching for the closest point between non-convex polyhedrons according to the present invention, a convex hull is created, directed graph-type structure data of the convex hull is created, and based on the directed graph-type structure data of the convex hull. The closest approach point search process.
The number of combinations of convex polyhedrons can be greatly reduced.
Also, if the convex hull collapses due to the dynamic change of the environment, the original convex hull will be restored if there is no interference with other objects for a certain period of time, and the number of convex polyhedrons will be minimized. Can be maintained and the computational load can be reduced.

(D) First Method in Continuous Search for Nearest Points between Nonconvex Polyhedrons (a) Principle In the “continuous search for closest points”, which continuously tracks the closest points between a plurality of nonconvex polyhedrons The merging process is performed on each of the non-convex polyhedrons to reduce and solve the continuity problem of the points of closest approach between the formal convex polyhedrons. At this time, for each convex polyhedron obtained by merging, numbers are assigned to surface convex polygons constituting the convex polyhedron, and lattice points, sides, and convex polygons located near each convex polygon are registered. Create a directed graph type structure data and calculate the calculation load of the closest point search by the order O of the maximum value of the number of grid points of the surface polygon.
(L) Keep below. In merging, an index called virtuality is introduced. What is virtuality?
In the surface polygon of the convex polyhedron obtained in the process of merging, if the surface polygon of the original non-convex polyhedron matches, the virtuality is set to 0, and if not, the virtuality is set to 1.

When interference with the convex polygon of virtuality = 1 occurs, merging is canceled and the first polyhedron of the present invention in the convex polyhedron is compared with the combination between the convex polyhedrons constituting the original non-convex polyhedron. The method of searching for the closest point 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, a convex hull A having a polygon with virtuality = 1 is generated. To release. 2) If the polygon with virtuality = 1 (the component of the convex hull A) and the polygon with the virtuality = 1 (the component of the convex hull B) interfere with each other, the constituent convex polyhedron when the convex hull is decomposed into a convex polyhedron Release the smaller number of convex hulls. 3) If the 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 polyhedrons appears ((( 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) Algorithm for searching for the point of closest approach between the convex polyhedron set and the convex hull 1) The interference surface of convex hull A when convex hull A is released is defined as PA (Virt
uality (PA) = 1). At this time, each side of the interference plane PA is composed of an element Edge (DA, PA) of the set DA and a side with virtuality = 1, and the lattice points of the interference plane PA are elements of the set DA
x (DA, PA).

2) The interference check between the set DA of the constituent convex polyhedron and the convex hull B is performed by Edge (DA, PA), Vertex (DA, PA) and convex hull B
This is performed by applying the first closest approach point search method of the present invention in a convex polyhedron. That is, Edge (DA, PA),
The surface convex polygon of DA including Vertex (DA, PA) (see the shaded portion of (c)) is converted to each convex polyhedron (A ′,
A ″) is searched from the directed graph type structure data.Then, the interference check is performed by applying the first closest approach point search method in parallel between the surface polygon and the convex hull B obtained respectively ((d)). 3) If the state escapes from the state of interference with the convex polygon of virtuality = 1, the convex hull released by the recovery processing is recovered, and the closest approach point search processing is performed on the convex hull (see (e)). By the processing of 2), the convex polyhedron A ′ to be searched for the closest approach point,
The number of planes of A ″ can be reduced (one plane for convex polyhedron A ′, two planes for convex polyhedron A ″), and the calculation load of the closest point search processing can be reduced.

(C) Flow of the closest approach point continuous search process FIG. 24 is a process flowchart of the closest approach point continuous search process between non-convex polyhedrons. Input data specifying the target non-convex polyhedron (initial input: environment model setting). Step 701 Next, the non-convex polyhedron is divided into convex polyhedrons, and each convex polyhedron P
Create Hi-directed graph type structure data. In addition, a convex hull is generated by merging, and directed graph type structure data of the convex hull is generated (step 702). When the above initialization process is completed, the first polyhedron of the present invention in the convex polyhedron is completed.
(Step 703). Next, it is checked whether or not they interfere (step 704). If they do, it is checked whether or not polygons having virtuality = 0 have interfered (step 705), and YES
If so, the processing is stopped without releasing either of the convex hulls, and the next instruction is awaited. However, if there is no interference between polygons of virtuality = 0, it is checked whether the polygon of virtuality = 1 (component of convex hull A) and the polygon of virtuality = 0 (component of convex hull B) have interfered. (Step 706).

If YES, the convex hull A having the polygon of virtuality = 1 is released (step 707). NO
Then, in other words, if the polygon of virtuality = 1 (the component of convex hull A) and the polygon of virtuality = 1 (component of convex hull B) interfere, the convex hull is decomposed into a convex polyhedron. Then, the convex hull having the smaller number of constituent convex polyhedrons is obtained (step 708), and the convex hull is released (step 707). Then, a surface convex polygon of a set DA including Edge (DA, PA) and Vertex (DA, PA) of the interference plane PA is retrieved from the directed graph type structure data of each convex polyhedron and passed to the processor (step 7).
09). After that, the processor calculates the surface polygon and convex hull B
In parallel, an interference check is performed by applying the first closest approach point search method (step 703).

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

(E) Second Method in Continuous Search for Nearest Points between Non-convex Polyhedrons (a) Principle In the “continuous search for closest points” in which the closest points between a plurality of non-convex polyhedrons are continuously tracked. The merging process is performed on each of the non-convex polyhedrons to reduce and solve the continuity problem of the points of closest approach between the formal convex polyhedrons. At this time, the second closest approach point search method of the present invention is applied. That is, for each convex polyhedron obtained by merging, a triangulation (Triangulat
ion) and take a directed graph type data structure for the result of the triangulation, and keep the calculation load of the search for the closest approach point constant irrespective of the complexity of the target convex polyhedron. In merging, an index called virtuality is introduced.
In the surface polygon of the convex polyhedron obtained in the merging process, the virtuality is set to virtuality = 0 when the surface polygon matches the surface polygon of the original non-convex polyhedron, and virtuality = 1 when the surface polygon does not match.

When interference with a triangular polygon with virtuality = 1 occurs, merging is canceled (release of the convex hull), and the present invention is applied to the combination between the convex polyhedrons constituting the original non-convex polyhedron. A second closest point search method is applied. The rules for canceling merging are as follows. 1) If a triangular polygon with virtuality = 1 (component of convex hull A) and a triangular polygon with virtuality = 0 (component of convex hull B) interfere, a convex hull A having a triangular polygon with virtuality = 1 is generated. 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, the convex polyhedron when the convex hull is decomposed into a convex polyhedron Release the smaller number of convex hulls. 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 polyhedrons appears (( 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) The interference triangle polygon of the convex hull A when the convex hull A is released is set to TA (Virtuality (TA) = 1). 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 point of the interference triangular polygon TA is the element Vertex (DA, PA) of the set DA. It consists of.

2) The interference check between the set DA of the constituent convex polyhedron and the convex hull B is performed by 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 triangular polygon of DA including Vertex (DA, PA) (see the hatched portion in (c)) is searched from the directed graph structure data of each convex polyhedron (A ′, A ″) constituting the non-convex polyhedron.
Next, an interference check is performed by applying the second closest approach point search method in parallel between the triangular polygon and the convex hull B obtained respectively (see (d)). 3) If the state escapes from the interference state with the triangular polygon of virtuality = 1, the convex hull released by the recovery processing is recovered, and the closest hull search processing is performed on the convex hull ((e)). By the processing of 2), the convex polyhedron A ′ to be searched for the closest approach point,
A ″ can reduce the number of triangular polygons (convex polyhedron A ′,
A ″, two for each), the calculation load of the closest point search process can be reduced.

(B) Process for continuously searching for points of closest approach between non-convex polyhedrons FIG. 26 is a flowchart of a process for continuously searching for points of closest approach between non-convex polyhedrons. Input data specifying the target non-convex polyhedron (initial input: environment model setting). Step 801 Next, the non-convex polyhedron is divided into convex polyhedrons, and each convex polyhedron P
Triangulation is performed on Hi, and thereafter, directed graph type structural data of each convex polyhedron is created. Further, a convex hull is generated by the merging process, and directed graph type structure data of the convex hull is generated (step 802).

When the above initialization processing is completed, a second closest point search processing (interference check) between the non-convex polyhedrons is executed (step 803). It is checked whether or not they interfere (step 804). If they do, it is checked whether or not the triangular polygons with virtuality = 0 have interfered (step 80).
5) If YES, stop processing without releasing either convex hull and wait for the next instruction. However, virtuality = 0
If the triangle polygons do not interfere with each other, it is checked whether or not the triangular polygon with the virtuality = 1 (the component of the convex hull A) and the triangular polygon with the virtuality = 0 (the component of the convex hull B) have interfered (step 806). If YES, the convex hull A having the triangular polygon with virtuality = 1 is released (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 is converted into a convex polyhedron. Find the convex hull with the smaller number of constituent polyhedrons when decomposed (step 8)
08), the convex hull is released (step 807).

Next, the edge of the interference triangle polygon TA
Triangular polygons of a set DA including (DA, PA) and Vertex (DA, PA) are retrieved from the directed graph structure data of each convex polyhedron and passed to the processor (step 809). After that, the processor performs an interference check by applying the second closest approach point search method in parallel between the obtained triangular polygon and the convex hull B (step 803). On the other hand, if there is no interference between the objects in step 804, a recovery process is executed (step 810).

In the recovery processing, it is checked whether or not the convex hull whose merging has been canceled exists. If there is, it is checked whether or not it interferes with another object. If not, the non-interference time is measured. Then, if the non-interference time of the convex hull whose merging has been canceled is equal to or longer than the set value, the convex hull is restored. However, if it interferes with another object or the non-interference time is not longer than the set value, the next step is executed without restoring the convex hull. Next, it is checked whether all parts of the convex hull are stationary (step 811). If not stationary, the process returns to step 803 and the subsequent processing is repeated. Create a convex hull (step 812),
03 and the subsequent processing is repeated.

(F) First Decomposition Process of Nonconvex Polyhedron into Convex Polyhedron (Preprocessing) (a) System Configuration To execute the search for the closest point between the nonconvex polyhedrons, the nonconvex polyhedron is converted into a convex polyhedron. Need to be disassembled. FIG. 27 is a system configuration diagram in a case where preprocessing for searching for the closest approach point is performed on the shape model on the graphic workstation.
GWS is a graphic workstation, CPU is a processor that executes pre-processing for searching for the closest approach point, processing for searching for the closest approach point, and other processing. MEM is a memory, and the shape data FD designed by a three-dimensional CAD system (not shown).
TPL, a preprocessing program ICP for searching for the closest approach point, and the like, DPL is a display unit, OPS is an operation unit such as a keyboard and a mouse, and OPR is an operator. Operator O
The PR uses the operation unit OPS to input a command to the processor CPU to execute preprocessing on the shape model on the graphic workstation GWS. When the preprocessing command is input, the processor CPU
Preprocessing program I for searching for the closest approach point stored in M
Based on the CP, preprocessing (division processing of a polygon set of the non-convex polyhedron) is performed using the non-convex polyhedron shape data FDT. 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 Preprocessing for Searching for Nearest Point FIG. 28 is a schematic processing flow of preprocessing for searching for the closest point according to the present invention. The 3D CAD system creates a shape model (non-convex polyhedron) and creates a graphic work step GW
Input to S (steps 1001 and 1002). CAD
The system inputs all polygon data when the 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 common polygon data is represented by a combination of triangular polygons as shown in FIG. In the case of the triangular polygon data shown in FIG. 28, three real numbers following normal indicate the light reflection direction, and three real numbers following vertex indicate the vertex coordinate values. The procedure for outputting polygon data from a shape model in a three-dimensional CAD system is usually a three-dimensional CA
It is provided in the D system. Next, the polygon data is divided into sets of polygon data (polygon subsets) divided for each convex element according to a basic algorithm for convex decomposition based on the division and conquer method. That is, initial polygon data (polygon set of non-convex polyhedron) is divided into sets of subsets for each convex element and output (steps 1003 and 100).
4). Thereafter, a convex polyhedron is generated for each subset.
Although each shape of the polygon is generally arbitrary, it is assumed that each polygon satisfies convexity.

(C) Basic Algorithm for Convex Decomposition by Divide and Conquer FIG. 29 is a flowchart of a basic algorithm for convex decomposition by divide and conquer. An initial polygon set (polygon set of a non-convex polyhedron) P is input (step 1101), and the initial polygon set P is subjected to processing by the divide and conquer method (step 1102). That is, the initial polygon set P
Is divided into first and second groups, and a polygon subset having a convex relationship with adjacent polygons in each group is obtained. Next, a polygonal subset of the first group and a polygonal subset of the second group having a common boundary ridge are merged in a convex relationship to form a plurality of new polygon subsets DP1, DP2,.・ ・Then, the polygon subsets DP1, DP2,.
Is output (step 1103).

The following is a detailed program example of the divide and conquer method. Define _{P = {p 1, p 2} , p 3, ···}: initial polygon set DC (P) = {DP1 = {1 p 1, 1 p 2, 1 p 3, ···}, DP2 = { ₂ p ₁ , ₂ p ₂ , ₂ p ₃ ,...},...｝: P divided polygon set NoP: Number of elements of P Algorithm (divided and conquer method) 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 less than k PH = {P _{k + 1} , p _{k + 2} , p _{k + 3} ,..., P _NoP }: polygon set larger than k RECUR: Costruct DC (PL) and DC (PH) recursively. MERGE: Merge DC (PL) and DC (PH) DC (P) = Merge (DC (PL), DC (PH)) endif As can be seen from the above algorithm, in the divide-and-conquer method, the process of divide and conquer is repeated recursively. The most important place where problem dependence exists in the divide-and-conquer method is the "merging" process, that is, the construction method of the function Merge.

(D) Merge process in the divide-and-conquer method FIG. 30 is a flowchart of the Merge process in the divide-and-conquer method. 1) Prepare convex element set DC (PL), DC (PH)
(Steps 1111a and 1111b). Convex element set DC
(PL) and DC (PH) are represented by CLi,
As shown by CHj, it is composed of a set of polygons (polygons) constituting the element and a set of boundary edges (boundary edges) forming the boundary of the element. 2) Judgment of Merge Possibility 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 constituting the boundary ridge line. If there is no shared border ridge, it is determined that merging is not possible. Condition 2: With respect to the shared boundary ridge line, the unevenness relationship between the CLi polygon and the CHj polygon sharing the ridge line is examined. If there is at least one combination of polygons having a concave relationship, it is determined that merging is impossible. Condition 3: When conditions 1 and 2 are cleared, that is,
If the polygons have a convex relationship in all combinations of polygons sharing the boundary ridge line, it is determined that Merge is possible.

3) Merge order Merge of convex elements is performed in the following order. 3-1) Convex element CL₁Is CH_j(j = 1,2, ... NPH) and Merge available
Determine whether or not. If CL₁Is CH_jAnd Merge is possible
Then, after that, CL₁, DC (PH) as follows
I do. CL₁∪CH_j→ CL₁  DC (PH) = $ CH₁, CH_Two, ... CH_j-1, CH_{j + 1}・
・ ・｝ 3-2) Execute the same procedure for CLi (i = 2,3, ... NPL)
You. 4) Configuration 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_Two, ... 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 Unevenness Relationship between Polygons FIG. 31 is an explanatory diagram of the unevenness relationship determination processing between polygons. As shown in FIG. 31A, two polygons A and B sharing one boundary ridge BEG are assumed. The relative positional relationship of the polygons is either apart from each other or in contact with each other via an edge as shown in FIG. etc)
Shall not exist. In FIG. 31 (a), vectors b,
c is a perpendicular vector dropped from the centroids p and q of the polygons B and A to the boundary ridge line x ₁ −x ₀ = a, respectively. Moreover, the vector a, b, respectively obtained by the unit of the c and _{e 0, e 1, e 2} . n _A and n _B represent outward normal vectors of the polygons A and _B , respectively (average of light reflection directions at respective grid points defining the polygons). 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₀|^Two・ Ha
Is the inner product of the vector = p-x₀-e₀・ (P-x₀) e₀  c = q-x₀-e₀・ (Q-x₀) e₀  e₀= A / | a | e₁= B / | b | e_Two= C / | c | to determine the unevenness relationship between polygon A and polygon B
As shown in 6 (b), the vector b is X₀Coordinates to match axis
Perform the conversion. The transformation matrix at this time is

(Equation 1) Given by

If one of the following two conditions is satisfied according to 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) ( If 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 dealing with actual CAD data, determination conditions are as follows in consideration of errors.

1) When (e ₀ × e ₁ ) · n _B > 0 When [T · c] _Z <ε and (e ₁ × e ₂ ) · n _A > −ε, 2 ) When (e ₀ × e ₁ ) · n _B ≦ 0 [T · c] _Z ≧ −ε and (e ₁ × e ₂ ) · n _A ≦ ε, polygon A and polygon B Are in a convex relationship. Where ε
Is a very small amount determined by the object to be treated. Each element of the set DC (P) of the polygon subset obtained by the divide-and-conquer method is not necessarily 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 exhibited in many cases.

(G) Second Example of Decomposition into Convex Polyhedron (Preprocessing) When performing convex decomposition by a basic algorithm based on the divide-and-conquer method, the number of convex elements after decomposition is not always the minimum. In the second embodiment, the number of convex elements is optimized (minimized as much as possible) by repeatedly using the basic algorithm of convex decomposition. The optimization method of the second embodiment is not a method of strictly minimizing the number of convex elements, but 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 (polygon set of non-convex polyhedron) P is input from a three-dimensional CAD system or the like (step 1201), and then a basic algorithm for convex decomposition based on the divide and conquer method is applied to the initial polygon set P (step 1202). . That is, the initial polygon set P
Is divided into first and second groups, and a polygon subset having a convex relationship with adjacent polygons in each group is obtained. Next, a polygonal subset of the first group and a polygonal subset of the second group having a common boundary ridge are merged in a convex relationship to form a plurality of new polygon subsets DP1, DP2,.・ ・

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

Next, the number of polygon subsets NDC (P) obtained previously and the number ND of polygon subsets obtained this time are calculated.
DC (P) is compared (step 1206), and if they match, a convex element set DC (DC (P)) is finally output (step 1207). And this convex element set DC
A convex polyhedron is generated using a polygon subset constituting (DC (P)), while NDDC (P) and N
If DC (P) is not equal (eg, NDDC
(P) <NDC (P)), DC (DC (P)) → DC
(P) (step 1208).
The process after 04 is repeated. That is, a plurality of newly obtained polygon subsets DC (DC (P)) are repeatedly subjected to convex decomposition processing by the divide-and-conquer method. In the optimization method,
The convex decomposition basic algorithm is repeatedly applied to the output DC (P) until the number of convex elements no longer decreases.

(H) Third Example of Decomposition into Convex Polyhedron (Preprocessing) In the method using the basic algorithm by the divide-and-conquer method,
There is a possibility that the number of divided convex elements in recognition of a hole or the like increases more than expected. In the third embodiment, in order to reduce the number of convex elements, convex decomposition processing is performed on an object such as a hole by regarding a Boolean algebra as negative, and the convex decomposition processing of the first embodiment is performed on other positive objects. Is applied. To regard a Boolean algebra as negative is to simply reverse the sign of the normal direction of each polygon (reverse the normal direction). Combining the basic algorithm based on the ordinary divide-and-conquer method with the negative object recognition method enables convex decomposition with a small number of convex elements.
FIG. 33 is an explanatory diagram of an object expression method by a Boolean set operation of an object including a shape such as a hole (negative object). HL is a hole, H
L 'is a hole portion whose normal direction is reversed, and BDY is an object without a hole (object without a hole). Objects with holes are BDY without holes
It is expressed by subtracting the hole portion whose normal direction is reversed from.

FIG. 34 is a flowchart of the convex decomposition processing of the third embodiment, and FIG. 35 is an explanatory diagram of the result of the convex decomposition. 3D C
Initial polygon set from AD system or the like enter the P (polygon set of non-convex polyhedron) (step 1301), then making the polygon set P _B was reversed all the normal direction of the initial polygon set P (step 1302). After a while
Applying a convex decomposition basic algorithm for polygon set P _B (step 1303). That is, the first polygon set P _B, is divided into second two groups, obtaining the polygon subset relationship between adjacent polygons is convex in each group. Then the first with a common border ridge
The polygon subsets of the group and the polygon subsets of the second group that have a convex relationship are merged to determine 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 for each convex element of the convex element set DC (P _B ),
A convex element composed of two or more polygons is extracted, and all the polygon sets constituting the convex element are represented by P ₂ (D
C (P _B )). That is, polygons constituting a negative object convex element such as a hole 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 obtained, and a polygon set PP ₂ (DC (P _B )) constituting the positive object is obtained (step 130).
5). When the polygon set (difference set) constituting the regular object is obtained, the basic algorithm for convex decomposition by the divide and conquer 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
Each group is divided into groups, and a polygon subset having a convex relationship with adjacent polygons in each group is obtained. Then, a plurality of new polygon subsets for each convex element are obtained by merging polygon subsets of the first group and polygon subsets of the second group having a common boundary ridge in a convex relationship. Thereafter, a convex element set DC (PP ₂ (DC (P _B ))) having the plurality of polygon subsets as elements is output (step 1307, FIG. 35), and recognition of a regular object is performed. Finally, DC (PP ₂ (DC (P _B ))) is a convex element of a positive object, DC
(P _B ) is output as a convex element of a negative object (Step 1)
308). Thereafter, a convex polyhedron is generated using the polygon subset of each convex element.

(I) Fourth Embodiment of Decomposition into Convex Polyhedron (Pre-Processing) The third embodiment is similar to the first embodiment of the convex decomposition in which the number of convex elements is reduced by performing an optimization method. An optimization method can be applied to the example to reduce the number of convex elements. FIG. 36 is a flowchart of the convex decomposition processing in such a case, which is different from the third embodiment in that an optimization method is applied instead of the basic convex decomposition algorithm in steps 1303 'and 1306'.

(J) Fifth Embodiment of Decomposition into Convex Polyhedron (Preprocessing) (a) Consideration In the above embodiment, the polygon subset C of the first group is used.
Merge of Li and polygon subset CHj of the second group
The possibility is determined as follows. That is, irrespective of whether the polygon subset CLi and the polygon subset CHj have a common edge, or not, all of the polygon edges forming the boundary edge of CLi and all the polygon edges forming the boundary edge of CHj A common boundary ridge is determined based on whether or not the points match.

However, in the merging possibility determination processing, it is not necessary to check whether or not the midpoints match in all combinations of polygon subsets and in brute force combinations of polygon sides constituting the boundary ridge line. Therefore, it takes a considerable amount of time to determine the possibility of Merge,
This limits the speed of convex decomposition. By the way, when the boundary ridge line of the convex element CLi and the boundary ridge line of the convex element CHj have a common boundary ridge portion, the convex object formed by the boundary ridge line of the convex element CLi and the convex object formed by the boundary ridge line of the convex element CHj And interfere. Therefore, before executing a process for obtaining a common boundary ridge line of the convex elements CLi and CLj, the boundary between the convex object and the convex element CHj formed by the boundary ridge line of the convex element CLi is calculated by an O (N) interference check method. It is checked whether or not there is interference between the ridge and the convex object. Then, when no interference occurs, the subsequent merge processing is skipped, and only when interference occurs, the subsequent merge processing is continued. In this way, the time required for the Merge processing can be greatly reduced, and the convex decomposition processing can be performed at high speed.

(B) Outline of interference check pre-processing FIG. 37 is another schematic processing flow of the interference check pre-processing of the fifth embodiment, and the same reference numerals are assigned to the same parts as those of the first embodiment of FIG. are doing. The difference from the first embodiment is that in step 1003 ', instead of the convex decomposition basic algorithm based on the divide-and-conquer method, the basic algorithm for convex decomposition based on the divide-and-conquer method incorporating the interference check is applied (the basic algorithm for high-speed convex decomposition). It is a point.

FIG. 38 is a flowchart of the processing of the basic algorithm for high-speed convex decomposition. An initial polygon set (polygon set of a non-convex polyhedron) 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 first and second groups, and a polygon subset having a convex relationship with adjacent polygons in each group is obtained. Next, a polygonal subset of the first group and a polygonal subset of the second group having a common boundary ridge line are merged (merged) to form a plurality of new polygon subsets DP1 for each convex element. DP2,... Thereafter, the polygon subsets DP1, DP2,... Are output (step 1103). Note that each polygon subset DP
A convex polyhedron is generated based on 1, DP2,.
The most important place where problem dependence exists in the divide-and-conquer method is the "merging" process, that is, the construction method of the function Merge.

(C) Merge process in the 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. That is, it is a necessary condition that the convex elements CLi and CHj interfere with each other through the boundary ridge line. Therefore, the interference check algorithm is applied between the convex elements CLi and CHj, and if there is no interference, the subsequent merge processing can be skipped for CLi and CHj. FIG. 39 is a flowchart of the Merge process in the divide-and-conquer method. 1) Prepare convex element set DC (PL), DC (PH)
(Steps 1111a and 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 b _NCHB1 ｝｝ convex element set DC (PL) , DC (PH) are composed of polygon subsets (polygons) and a set of boundary edges (boundary edges) forming the boundaries of the elements.

2) Judgment of Merge Possibility 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 edges Bedge _CLi , Be of convex elements CLi, CHj
_Perform interference check between dge _CHj . Merg without interference
e Judge as impossible. Condition 2: convex elements CLi, CH possibly interfering
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 constituting the boundary ridge line. If there is no shared border ridge, it is determined that merging is not possible. Condition 3: With respect to the shared boundary ridge line, the unevenness relationship between the CLi polygon and the CHj polygon sharing the ridge line is examined. If there is at least one combination of polygons having a concave relationship, it is determined that merging is impossible. Condition 3: Me when 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_j(j = 1,2, ... NPH) and Merge available
Determine whether or not. If CL₁Is CH_jAnd Merge is possible
Then, after that, CL₁, DC (PH) as follows
I do. CL₁∪CH_j→ CL₁  DC (PH) = $ CH₁, CH_Two, ... CH_j-1, CH_{j + 1}・
・ ・｝ 3-2) Execute the same procedure for CLi (i = 2,3, ... NPL)
You. 4) Configuration 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_Two, ... 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 the 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 interference check methods for the existing computational 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 convex objects constituted by the boundary edges Bedge _CLi and Bedge _CHj of CHj (step 1401). By applying the interference check algorithm, the distance between the closest points of the boundary edges Bedge _CLi and Bedge _CHj dist (Bed
ge _CLi , Bedge _CHj ) and output it (step 140).
2). Once the distance between the closest points is obtained, the distance dist (Bedge
_CLi, and compares the Bedge _CHj) and ε, dist (Bedge _CLi, B
edge _CHj ) ≦ ε, it is determined that interference occurs, and dist (Bedge
_{If CLi} , Bedge _CHj )> ε, it is determined that there is no interference.
Here, ε is a user-defined minute constant that determines the accuracy of the interference check determination.

(F) Interference Checking Method (Gilbert Method) Search between the closest points between the convex objects constituted by the boundary edges Bedge _CLi and Bedge _CHj of the convex elements CLi and CHj and the 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 of each object in the direction of the center of gravity difference. When finding the point of closest approach by the Gilbert method, the following inequality holds (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 the biconvex objects.

(G) Merge Possibility Judgment Processing Based on Gibert Method FIG. 42 is a flowchart of Merge possibility judgment processing based on the Gilbert method. Boundary ridges Bedge _CLi , Be of convex elements CLi, CHj
by applying the Gilbert method between each composed convex object with dge _CHj, it computes the r _k of (13) (step 141
1). Next, r _k> 0 it is determined whether or not (step 141
2) If r _k > 0, there is no interference, so it is determined that Merge is not possible (step 1413). However, if r _k ≦ 0, it is determined that Merge interference exists because of interference, and Merge possibility / impossibility is determined from the above Merge possibility conditions 2 to 4 (step 1414).

(H) Merge Possibility Determination Processing Based on Simplified Gibert Method Merge possibility determination processing based on the Gibert method is further simplified. The point of simplification is to set an arbitrary vertex from the vertex set Bedge _CLi and Bedge _CHj on the boundary edge as the initial lattice point V ₀ of the Gilbert method.
Select the Bedge _CLi0, Bedge _CHji0, constitute V ₀ = Bedge _CLi0 -Bedge _CHji0 (17). Then, using this V ₀ , r = −h _k (−V ₀ ) = − h _k1 (−V ₀ ) −h _k2 (V ₀ ) (18) is calculated. If r> 0, Bedge _CLi , Bedge _CHj
There is no interference between them, and it is determined that there is no possibility of merging the convex elements CLi and CHj.

FIG. 43 shows Mer based on the simplified Gilbert method.
It is a ge possibility determination processing flow. Convex elements 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 determined whether r> 0 (step 1412 ′). If r> 0, there is no interference, so it is determined that Merge is impossible (step 141).
3 '). However, when r ≦ 0, interference occurs.
It is determined that there is Merge interference, and Merge is possible / impossible from the above Merge possibility conditions 2 to 4 (step 141).
4 ').

(K) Modification of Convex Decomposition (a) Modification 1 The convex decomposition method of the fifth embodiment described above may be configured to perform optimization processing to reduce the number of convex elements. FIG. 44 shows a processing flow in this case. In FIG. 44, the difference from the processing of the second embodiment (see FIG. 32) is that
02 'and 1204', a high-speed convex decomposition algorithm incorporating an interference check is used instead of the basic convex decomposition algorithm. (b) Modification 2 The high-speed convex decomposition algorithm of the interference check built-in type can be applied to the convex decomposition processing in the presence of a negative object. FIG. 45 shows a processing flow in this case. In FIG. 45, the difference from the third embodiment is that step 1303 ′,
In 1306 ', a high-speed convex decomposition algorithm incorporating an interference check is used instead of the basic convex decomposition algorithm. (c) Modification 3 Modification 2 may be further optimized to reduce the number of convex elements.

(L) Preprocessing for Searching for Nearest Point (Formation of Linear List of Proximity Points) In the above description, directed graph type structural data is generated from polygon data by preprocessing, and between the convex polyhedrons or using the directed graph type structural data. This is the case where the closest point search processing between non-convex polyhedrons is performed. Structural data different from the directed graph structure data, that is, a near-point linear list is created by preprocessing, and by using the list, the continuous search for the closest point can be speeded up. The near-point linear list is such that vertices of each polygon constituting a shape model (CG model) are linked in a first direction (next direction), and a vertex group connected to each vertex via a polygon side is defined in a second direction (b).
This is a list provided with a data structure linked to the vertex in the (rank direction). By sequentially tracing from the top of the list, it is possible to pick up all adjacent 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: a next direction in which vertices are sequentially connected, and a branch direction in which proximity points connected to each vertex via polygon sides are arranged. The top of the branch direction contains the vertex itself. (b) Method of Constructing Proximity Point Linear List FIG. 47 is a flowchart of a process of 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 three vertex coordinate values following vertex and light reflection direction data at three vertices following normal. You.

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 sets of polygon data (polygon subsets) divided for each convex element according to a basic algorithm for convex decomposition based on an interference check built-in division and conquer method. That is, the initial polygon data is divided into sets of subsets for each convex element and output (steps 2003 and 2004). Thereafter, a near-point linear list is generated for each subset, that is, for each convex polyhedron using a near-point linear list construction algorithm, and is expanded in a memory (steps 2005 and 2006). Next, the closest point search processing (interference check processing) is executed using the close point linear list, and the close point linear list is stored in the external storage medium (step 2007). Since then
If the proximity point linear list is required, the list is read from an external recording medium and developed in a memory without newly creating the list (step 2008).

(C) Proximity point linear list construction algorithm FIG. 49 is an explanatory diagram of polygon data for each convex element of a target object.
FIG. 50 is an explanatory diagram of a neighboring point linear list construction algorithm. Assuming that the target object is constituted by a set of triangular polygons, the near point linear list is constituted according to the following flow. 1) Polygon data for each convex element is prepared 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 defined as a linear list direction with respect to the vertices, and the branch direction is defined as a direction of a point near each vertex. The head element of the list L is the first vertex of the first polygon, and has a data structure shown in FIG. Specifically, a list is created as follows. 2-1) Assign 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 assignment. 1) If if (Lj ≠ pi for all j), assign a new element pi 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 assigned (see FIG. 50 (c)). 2) If if (Lj = pi for a certain j), 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, no assignment is made (see FIG. 50 (d)). 3) The above processes 1) and 2) are performed on the vertex qi. However, branch candidates other than qi for vertex qi are pi and ri. 4) The above processes 1) and 2) are executed for the vertex ri. However, 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 Creating Proximate Point Linear List FIGS. 51 and 52 are explanatory diagrams of an example of creating a proximal point linear list. Polygon data for each convex element is prepared by the basic convex decomposition algorithm (step 2011). Since then,
The polygon is incorporated into the list (step 2012), and the second polygon is incorporated into the list L (step 2).
013). That is, in step 2012, firstly allocates a first vertex V ₁ of the first polygon as top. That is, top = L ₁ = V ₁ (2012a). Then, branc for the vertex V ₁
All vertices V ₁ , V ₂ , V ₃ of the first polygon are allocated in the h direction (step 2012b). Then, the second vertex V _{2 is set} to ne
Assignment in xt direction (Step 2012c)
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).

[0134] In step 2013 allocates the first vertex V ₁ of the second polygon. In this case, since the vertex V ₁ in the next direction is already assigned, the vertex V ₁ branch
Vertices V ₁ , V ₃ , V ₄ are allocated in the directions. However, since the vertices V ₁ and V ₃ have already been allocated, only the vertex V ₄ is allocated (step 2013a). Then the second
Assigned vertex V ₃ in the next direction. In this case, since the vertex V ₃ in the next direction it is already assigned, the vertex V ₃ br
Vertices V ₃ , V ₄ and V ₁ are allocated in the anch direction. But,
Since the vertices V ₃ and V ₁ have already been allocated, the vertex V ₄
Only (step 2013b). After a while
The third vertex V ₄ assigned to 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, the polygon has been described as a triangular polygon, but is not limited to a triangular polygon, and may be any polygonal polygon. The computational load for creating a near-point linear list from N vertices is O (N ² ).

(M) Preprocessing for Searching for Nearest Point (Preparation of Proximity Point Multi-Tree List) The calculation load for preparing the linear list of proximity points is O (N ² ) for N vertices, which is large. Therefore, a list (proximity point multi-tree list) of another data structure 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 the list. The proximity point multitree list is an array list of vertices as follows. 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 direction 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 fifth next direction (zrigh
t), a sixth next direction (zleft) smaller than the Z coordinate value is determined. Then, each axis coordinate value of the reference vertex is compared with each axis coordinate value of a vertex connected to the reference vertex by a polygon side (referred to as a target vertex), and a next direction for linking the target vertex is determined according to the magnitude. At the same time, the target vertices are linked in the next direction in the order closer to the reference vertex. When linking the target vertex in the next direction, if the coordinate value of the other vertex already linked in the next direction is equal to the coordinate value of the target vertex, the axis coordinates of the other vertex and the target vertex are changed. Compare. Then, a next direction corresponding to the magnitude is obtained, and the target vertex is linked to the other vertex in the next direction. Also, a branch direction is determined for each vertex, and all vertices connected to the vertex by polygon sides are arranged in the direction. The one created as described above is the proximity point multi-tree list.

(A) Example of Proximity Point Multi-Tree List FIG. 53 shows an example of a rectangular parallel-tree multi-point tree list. As shown in the drawing, each vertex has six link directions xright, xleft, yright, yleft, zright, and zleft corresponding to the magnitudes of the x, y, and z axes, and one branch. Has directions. Vertex
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 of Constructing Proximity Point Multi-Tree List FIG. 54 is a flowchart of a process of creating a 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 sets of polygon data (polygon subsets) divided for each convex element according to a basic algorithm for convex decomposition based on an interference check built-in division and conquer method. That is, the initial polygon data is divided into sets of subsets for each convex element and output (steps 2103 and 2104). Thereafter, a near-point multitree list is generated for each subset, that is, for each convex polyhedron by using a near-point multitree list construction algorithm (step 2105). Next, the near-point multitree tree conversion algorithm is used to convert the near-point multitree tree list into a near-point linear list and expand it in the memory (steps 2106 and 21).
07). Thereafter, the closest point search processing (interference check processing) is executed using the close point linear list, and the close point linear list is stored in the external storage medium (step 21).
08). Thereafter, when the proximity point linear list is required,
Instead of creating a new one, it is read from the external recording medium and expanded in the memory (step 2109).

(C) Proximity point multitree list construction algorithm Assuming that the target object is composed of a set of triangular polygons, the proximity point multitree list is constructed according to the following flow. 1) Polygon data for each convex element is prepared 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 viewed from the vertex where zleft is focused
It is the direction of the axis. Also, each vertex is defined as
Has a branch direction. Specifically, the proximity point multi-tree list ML is constructed according to the following procedure (see FIG. 53).

2-1) The top element top of the ML is allocated. to
As p, assign the first vertex of the first polygon. 2-2) The following assignment is repeated for polygons (pi, qi, ri). (1) The vertices pi are compared lexicographically in the order of the magnitude of the x coordinate value, the magnitude of the y coordinate value, and the magnitude of the z coordinate value as viewed from the top element top of the ML, and are assigned. 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 arranged in the xright direction is compared with the x-coordinate value of the vertex pi when viewed from top. Are arranged in ascending order. The 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 the top. If there is a placed vertex having an x-coordinate value that matches the x-coordinate value of the vertex pi, the y-coordinate value is compared, and the vertices are arranged in ascending order in the y-coordinate direction when viewed from the placed vertex. I do. If there is an already-arranged vertex having the same y-coordinate value, similar ascending arrangement is performed on the z-coordinate value. If there is a vertex at which all the coordinate values of x, y and z match, the vertex pi is regarded as the same. (2) For the newly allocated vertex pi, the branc of this vertex pi
Assign 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 assigning the same point.

(3) The above processes (1) and (2) are performed on the vertex qi. However, a branch other than qi for vertex qi
Candidates are pi and ri. (4) The above processes (1) and (2) are performed on 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, the polygon has been described as a triangular polygon, but is not limited to a triangular polygon, and may be any polygonal polygon. The computational load for creating a near-point multitree list from N vertices is O (NlogN)
It is.

(D) Proximity point multi-tree list conversion algorithm In the interference check between convex polyhedrons (closest point search processing), a calculation is performed to obtain a vector inner product with each vertex of the convex polyhedron and detect the maximum value. Repeat. At this time,
If each vertex is in the form of a proximity point multitree list, a large number of complicated determination functions will be involved when sequentially following each vertex. Therefore, once the proximity point of each vertex is formed in the form of the proximity point multi-tree list, the calculation amount can be reduced by converting the multi-tree list into a linear list.
To convert a multi-tree list into a linear list, for example, use the following recursive function vertex * MultiToLinear ().

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 xleft direction} if (xright! = 0) {// same for xright, yleft, yright, zleft, zright 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 into a linear list L. The calculation time of the neighboring point multitree list conversion algorithm is O (N), where N is the total number of vertices.
It is. Therefore, the total calculation time for generating the proximity point linear list L from the polygon data through the proximity point multi-tree list construction algorithm is O (NlogN).

(N) Preprocessing for Searching for Nearest Point (Dumping and Loading of Near-Point Linear List) The closest-point linear list information required for the closest-point search processing, that is, the interference check processing, is all expanded on the memory. Must be kept. If it takes the same calculation time (O (NlogN) with respect to the total number of vertices N) as constructing the neighboring point multi-tree list, it is necessary to expand the dump file (dump file) on the memory. There is no point in creating 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 becomes O (N). (a) Format of Dump File The format of the dump file is as shown in FIG. In this file format, essential items for high-speed loading are as follows. 1) Each convex element is separated, 2) There is an item of the total number of vertices (count) constituting the convex element, 3) Each vertex is numbered, 4) Each vertex , The number of neighboring points of the vertex (bcount)
5) There is an item that defines the coordinates of each vertex.

(B) Loading Method from Dump File 1) The total number of vertices (count) constituting the convex element is read, and a count-dimensional array for storing each vertex is created. 2) Each vertex of the convex element is stored in the array, and each vertex is connected in the next direction to form a linear list. For example, Ve
When the array containing rtex is V [Ni], V [0], V
.. 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) For each vertex of each convex element, a list of adjacent points is set in the branch direction based on the adjacent point number of the branch (designating the position in the array). For example, when the array that stores the vertices is V [Ni], the number of the branch of the vertex V [0] is
If (0,9,1,7,8), V in the branch direction of VertexV [0]
[0], V [9], V [1], V [7], V [8] are linked to a linear list. 5) Apply the processing of 4) to each convex element. In the above-mentioned loading method, the same file is used twice (1), 2), 3) for the first time,
4) and 5) perform the second reading). In most cases, the number of branches at each vertex can be reduced to several tens or less.
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 A dump file similar to that in FIG. 55 is defined for the smallest convex polyhedron (convex hull) wrapping a non-convex polyhedron. In this case, the number of convex elements is one, and vertex consists of all vertices constituting the non-convex polyhedron. A file in the format shown in FIG. 55 for the convex hull is called an HL file.

(O) Interference Check Sub-Algorithm (Preliminary Check Using Envelope Sphere) For an arbitrary non-convex polyhedron, a sphere that envelopes it is generated in preprocessing. At this time, the interference check is performed between the envelope spheres before the interference check between the non-convex polyhedrons is started, and the speed is increased. (a) Construction method of envelope sphere A non-convex polyhedron is represented by a set of triangular polygons.
∪i (pi, qi, ri). The suffix i is a subscript for identifying each polygon. The coordinate values of pi, qi, ri are represented by pi = (pix, piy, piz), qi = (qix, qiy,
qiz), ri = (rix, riy, riz). At this time,
The max and min points of the convex hull are obtained 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 that envelopes each convex element is defined. The calculation method is the same as in (a). Where m
The suffix i when defining ax, min means a polygon set of each convex element. (c) Preliminary Check Algorithm Using Envelope Sphere FIG. 56 is a processing flow of a prior check using an envelope sphere. Each non-convex polyhedron A, envelope spheres radius R _A of B, R _B, envelope spheres center P _CA, the P _CB calculated by the above-described method (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 then interference between non-convex polyhedrons is checked (step 2205).

(P) Interference Check Sub-Algorithm (Continuous Search in Convex Polyhedron Interference Check) Extract vertices that are closest to the closest approach point obtained from the nearest point linear list, and use the Gilbert's interference check method for these vertices. Is applied to search for the closest approach point after a predetermined time. By doing so, the time required for the interference check can be suppressed to a certain number or less that hardly depends on the number of polygons representing the convex polyhedron. (a) Gilbert method The distance ν (K) between the closest points between the convex polyhedrons 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 2}} i (i∈I K2Sk) (19) However, x ¹ _i: vertex constituting the K ₁ x ² _i: given by vertices of the K _2.

(B) Intuitive understanding of Gilbert's method FIG.
FIG. 5 is an explanatory diagram that can be solved. Each process is simplified
The simple explanation is as follows. 1) Set the vector η Connect the geometric centroids of the 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^Two _i・ Ν₀： I = 1, ・ ・ ・ m_Two} (21), the vector ν₀Closest to each other in the direction of
2 points p₀, Q₀(FIG. 57 (a)). 3) ν₁Update 2 points p₀, Q₀Connect ν₁(FIG. 57 (b)). 4) Dot product calculation ν₁The same inner product calculation as in 2) is performed for₁,
q₁(FIG. 57 (b)). 5) Dot product calculation and ν₁Repeat the update to make the final closest approach
Point vector ν_final(FIG. 57 (c)). As you can see from the above process, the main Gilbert method
The calculation load occurs in the process of calculating the inner product. Therefore, Gilber
The calculation time of the closest approach point search in the t method is O (m₁+ m _Two)
You.

(C) Continuous interference check in convex polyhedron The computation load in the Gilbert method is determined by the support functions h _K1 and h _K2.
Occurs in the process of calculating the inner product of. Therefore, in order to reduce the number of times of calculating the inner product, a method of efficiently finding a proximity point of the closest approach vector ν (K) will be considered. The closest points ν _K1 and ν _K2 of the convex polyhedrons K ₁ and K ₂ are given by the following equations from the equation (19). ^{_{ν K1 = Σλ i x 1 i}} (i∈I K1Sk) (22) ν K2 = Σλ i x 2 i (i∈I K2Sk) (23) if continuously searching the closest point of approach, most of after a predetermined time The approaching point exists near ν _K1 and ν _K2 given by the equations (22) and (23). Therefore, the vertices when calculating the support functions h _K1 and h _K2 can be limited to the proximity points of the vertices x ¹ _i and x ² _{i in} the equations (22) and (23).

FIG. 58 is a flowchart 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 obtained, and the vector ν ₀ = G _K1 −G _K2 is obtained (step 2301). Next, an interference check algorithm based on the Gilbert method is executed using ν ₀ as an initial value, and ν _K1 and ν _K2 given by equations (22) and (23) are obtained (step 2302). Then, ν ₀ = ν _K1 −ν _K2 and G
Execute interference check algorithm by 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 = number of a set of proximity points of x ¹ _i given by equation (22)} h _K2 (−ν ₁ ) = max {−x ² _i · ν ₁ : p = number of a set of proximity points of x ¹ _i given by equation (22)} Then, the closest approach point is calculated by equations (22) and (23), and thereafter g _K
The processing of step 2303 and thereafter is repeated until (ν _K ) = 0. The number of points near the vertices x ¹ _i and x ² _i in FIG. 58 is equal to the number 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 in 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, an interference check between the convex hulls is performed. When the convex hulls start to interfere with each other, the process automatically shifts to an interference check between the convex elements constituting the non-convex polyhedron. . When the distance between the non-convex polyhedrons becomes large again, the convex hull is recovered, and the process returns to the interference check between convex hulls. (a) Basic Concept of Dynamic Configuration / Release of Convex Hull FIGS. 59 and 60 are explanatory diagrams showing the basic concept of configuration / release of a convex hull. In FIG. 59, A and B are the first,
The second non-convex polyhedrons, C _A1 and C _A2, are convex polyhedrons forming the non-convex polyhedron A, and C _B1 , C _B2 are convex polyhedrons forming the non-convex polyhedron B. 1) If the non-convex polyhedrons A and B are sufficiently separated, an interference check between the convex hulls A 'and B' is performed (see FIG. 60 (a)).

2) When convex hulls A 'and B' start to interfere with each other
(See FIG. 60 (b)), one convex hull A 'is released, and the convex element C
_A check is made for interference between _A1 and _CA2 and the convex hull B ', and if they do interfere, the convex element _CA1 is taken out (see FIG. 60 (c)). 3) Next, the positions of the convex element and the convex hull are exchanged, and the other convex hull B ′ is released, and the convex elements C _B1 ,
The interference between C _B2 and the convex hull A ′ is checked, and the interfering convex element C _B1 is extracted (see FIG. 60 (d)). 4) Finally, all combinations of the extracted convex elements (Fig. 6
At 0, interference check is performed for 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 approach vector between them is determined, and two end points p and q giving the vector are defined as the closest approach points. As shown in FIG. 61 (b), when the positions between the convex elements C _B1 and C _B2 and the convex hull A ′ are switched, and when there is no interference between the convex hull and the convex element, the convex element C _B1 , C _B2
And the closest point between the convex hull A ′ and the two end points p ′ and q ′ that give the vector is defined as the point of closest approach.

FIG. 62 is a processing flow of a dynamic construction / cancellation algorithm of a convex hull. Convex hull A 'of non-convex polyhedrons A and B,
Interference check processing (closest search processing) is performed between B '
The distance r (A ', B') between the closest points is obtained. Then
judge the magnitude of r (A ', B') and ε _CH (step 2
401). ε _CH is a user-defined minute constant. r
When (A ′, B ′)> ε _CH , the convex hulls A ′ and B ′ do not interfere with each other, 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). Thereafter, the above processing is repeated while maintaining the convex hull.
On the other hand, when r (A ′, B ′) ≦ ε _CH , one convex hull, for example, the convex hull A ′ is released because the convex hulls interfere with each other.
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
(C _Ai, B ') is epsilon _CC subset ∪ of _H following convex elements _i CC
_Ai is obtained (step 2403). ε _CCH is a user-defined minute constant. Thereafter, it is checked whether the number of convex elements constituting the subset ∪ _i CC _Ai is 0 (step 2).
404). ∪ When _i CC _Ai = 0, r (C _Ai ,
B ′), a convex element C _Ak that gives the minimum distance MIN _i r (C _Ai , B ′) is obtained, the closest point between the convex element C _Ak and the convex hull B ′ is obtained, and the closest point is determined as It is output as the point of closest approach 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, '(convex hull A distance r C _Bj, A) between each convex element C _{B j'} seek a subset ∪ _j CC _Bj of the following convex elements epsilon _CCH (step 2406).
Then, the number of convex elements constituting the subset ０ _j CC _Bj is 0
Is checked (step 2407). ∪ _j CC
_{If Bj} = 0, the minimum distance M of r (C _Bj , A ')
A convex element C _Bk that gives IN _j r (C _Bj , A ′) is obtained, a closest approach point between the convex element C _Bk and the convex hull A ′ is obtained, and the closest approach point is determined between the non-convex polyhedrons A and B. Output as the closest approach point (step 2408). However, if ∪ _j CC _Bj > 0, the minimum distance MIN _{i, j} R between subsets ∪ _i CC _Ai and ∪ _j CC _Bj
Convex elements CC _Ap and CC _Bq that give (CC _Ai , CC _Bj ) are obtained, the closest point between them is obtained, and output as the closest point between the non-convex polyhedrons A and B (step 2409). Thereafter, the process returns to the beginning and the subsequent processes are repeated.

(R) Interference Check Sub-Algorithm (Dynamic Construction / Cancellation 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, a continuous interference check between the convex hulls is performed. If the convex hulls start to interfere with each other, the system automatically shifts to the interference check between the convex elements constituting the non-convex polyhedron I do. When the distance between the non-convex polyhedrons is increased again, the convex hull is recovered, and the process returns to the continuous interference check between convex hulls. FIG. 63 is a processing flow of an algorithm for dynamically constructing / releasing a convex hull and checking for a convex polyhedron continuous interference, and FIGS. 64 to 66 are explanatory diagrams thereof. An interference check process (closest search process) is performed between the convex hulls A 'and B' of the non-convex polyhedrons A and B, and a distance r (A ', B') between the closest points.
Ask for. Next, the magnitudes of r (A ', B') and ε _CH are determined. Also, the flag contflg _A ′ = 1 is set (step 2501). When r (A ', B')> ε _CH , the convex hulls A 'and B' do not interfere with each other, so the point of closest approach between the convex hulls A 'and B' is the closest approach between the non-convex polyhedrons A and B. A point is output (step 2502). Thereafter, the above processing is repeated while maintaining the convex hull.

FIG. 64 is a flowchart showing steps 2501 and 2502.
The process is specifically shown. As shown in FIG.
In the interference check between convex hulls, the first support function h
Is calculated based on the inner product calculation for all points
However, the next time, based on the continuous interference check algorithm,
It is calculated based on That is, the inner product calculation is
Limited to contacts. In continuous interference check,
It is necessary to keep near point information.
Is held as one attribute of the convex hulls A ′ and B ′. S
In the process of Step 2502, contflg_A'= 1 flag
And the interference check between (A ', B') becomes continuous.
You. In step 2501, r (A ′, B ′) ≦ ε
_CHIn the case of, one convex hull, eg,
For example, the convex hull A 'is released. Convex element C of non-convex polyhedron A _Aiof
Union_iC_AiIs expressed as Next, the convex hull B 'and each convex
Element C_AiDistance r (C_Ai, B ') is ε_CCHThe following key points
Subset of primes∪_iCC_AiAsk for. Also, the flag contflg
_CCA1= 1 (step 2503).

Thereafter, it is checked whether the number of convex elements constituting 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 obtained, and the closest point between the convex element C _Ak and the convex hull B ′ is obtained. Then, the closest approach point is output as the closest approach point between the non-convex polyhedrons A and B (step 2505). r (C _Ai ,
B ') is obtained by a continuous interference check.

FIG. 65A shows steps 2503 to 250
FIG. 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. Cont in step 2503
The flag of flg _CCA1 = 1 is set, and the interference check between (C _Ai , B ′) in step 2505 becomes a continuous type. 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 whose distance r (C _Bj , A ′) between the convex hull A ′ and each convex element C _Bj is equal to or _smaller than ε _CCH is obtained. Also, the flag contflg
_CCB1 = 1 is set (step 2506). Thereafter, it is checked whether the number of convex elements constituting the subset ∪ _j CC _Bj is 0 (step 2507). When ∪ _j CC _Bj = 0, the minimum distance MIN _j r (C _Bj , r) of 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 point of closest approach between B (step 2508).

FIG. 65 (b) shows steps 2506 to 250
FIG. 8 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 _Bj of the non-convex polyhedron B. Cont in step 2506
The flag of flg _CCBj = 1 is set, and the interference check between (C _Ai , B ′) in step 2508 becomes a continuous type. In step 2507, if ∪ _j CC _Bj > 0,
The minimum distance MIN _{i, j} R between the subsets ∪ _i CC _Ai and ∪ _j CC _Bj
Convex elements CC _Ap and CC _Bq that give (CC _Ai , CC _Bj ) are obtained, the closest approach point between them is obtained, and output as the closest approach 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). Thereafter, the process returns to the beginning and the subsequent processes are repeated. FIG. 66 is an explanatory diagram showing the entire 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, an interference check is performed between the convex envelope spheres that envelope the convex hull, and when the convex envelope spheres start to interfere with each other, an interference check between the convex hulls is performed. When the convex hulls start to interfere with each other, an envelope sphere interference check and a convex polyhedron interference check are performed on the convex elements constituting the non-convex polyhedron. The envelope sphere interference check and the configuration / cancellation of the convex hull are dynamically switched according to the distance between the non-convex polyhedrons. FIG. 67 is a processing flow of dynamic configuration / cancellation of a convex hull and an envelope sphere interference check. Each non-convex polyhedron A, B
Of the envelope spheres R _A , R _B and the centers of the envelope spheres P _CA , P _CB are obtained (steps 2501 and 2502), and the distance r between the centers of the envelope spheres is obtained by the following equation: r = | 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 approach points (step 25).
04). If r ≦ (R _A + R _B ), the non-convex polyhedrons A and B
Is subjected to interference check processing (closest search processing) between the convex hulls A 'and B', and the distance r (A ', B') between the closest points is obtained. Next, the magnitude of r (A ', B') and ε _CH is determined (step 2505). r (A ', B')> epsilon convex hull A in the case of _CH ', B' are do not interfere, convex hulls A ', B'
The point of closest approach between is set as the point of closest approach between the non-convex polyhedrons A and B, and is output (step 2506). On the other hand, r (A ', B')
In the case of ≦ ε _CH , one convex hull, for example, convex hull A ′ is released because the convex hulls interfere with each other. The union of the convex elements C _Ai of the non-convex polyhedron A is expressed as ∪ _i C _Ai . Then, an interference check between the envelope sphere of each convex element C _{Ai and} the envelope sphere of the non-convex polyhedron B is performed, and an interference check is performed between the interfering convex element C _Ai and the convex hull B ′. Thereafter, a subset 凸_i of convex elements whose distance r (C _Ai , B ′) between the convex hull B ′ and each convex element C _Ai is equal to or less than ε _CCH.
SCC _Ai is obtained (step 2507).

Next, it is checked whether the number of convex elements constituting the subset ∪ _i SCC _Ai is 0 (step 250).
8). ∪ When _i SCC _Ai = 0, r (C _Ai , B ′)
Of the convex element C _Ak that gives the minimum distance MIN _i r (C _Ai , B ′), the closest point between the convex element C _Ak and the convex hull B ′ is obtained, and the closest point is defined as the non-convex polyhedron A , B (step 2509). If ∪ _i SCC _Ai > 0, release the other convex hull B ′. The union of the convex elements C _Bj of the non-convex polyhedron B is expressed as ∪ _j C _Bj . Next, 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 interfering convex element C _Bj and convex hull A ′. 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 equal to or _smaller than ε _CCH is obtained (step 2510). Next, it is checked whether the number of convex elements constituting the subset ∪ _j SCC _Bj is 0 (step 2511). ∪ _j SCC _Bj
= 0, the minimum distance MIN of r (C _Bj , A ′)
_Find the convex element C _Bk that gives _i r (C _Bj , A ′), find the closest point between the convex element C _Bk and the convex hull A ′, and determine the closest point between the non-convex polyhedrons A and B. Output as an approach point (step 2512).

However, ∪_jSCC_BjIf> 0, the part
Subset∪_iSCC_AiAnd ∪_jSCC_BjMinimum distance between MIN_{i, j}
r (SCC_Ai, SCC_BjThe convex element SCC that gives_Ap, S
CC _Bq, The closest point between them is found, and the non-convex polyhedron
Output as the point of closest approach between A and B (step 251)
3). Thereafter, the process returns to the beginning and the subsequent processes are repeated. The figure
The algorithm for continuous interference of the convex polyhedron shown in FIG.
Interference check speed by incorporating
can do.

(T) Structure of Interference Check System FIG. 68 is a diagram showing the structure of the interference check system of the present invention. Reference numeral 21 denotes a three-dimensional CAD system for generating a shape model and outputting a polygon data file. 23 is a memory that stores convex element data obtained by pre-processing, a proximity point multi-tree list, a proximity point linear list, etc., 23 is a proximity point multi-tree list creation unit that creates a proximity point multi-tree list from a polygon data file, and 24 is A near-point linear list creation unit that generates a near-point linear list from a near-point multitree 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 near-point linear list. A list input / output unit 28 that outputs the data to an external recording medium, reads the data as appropriate, and expands the data in the memory 22. Medium.

(U) Field of Application of the Present Invention The present invention can be applied in the following fields. (a) CAD system for mechanical design In mechanical design, inadvertent 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 components and the margin on the CAD system for mechanical design. 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 Mobile robots such as manipulators and self-propelled vehicles are often driven after performing path planning in advance so as not to collide with other objects. For example, in assembling parts using a manipulator, it is necessary to plan a path while checking interference between parts and interference between the part and the manipulator. In addition, a self-propelled robot such as a cleaning robot, a guard robot, or a transport robot needs a path plan that avoids collision with an obstacle such as a wall, a pillar, or a desk 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 perform a 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, to make an android model walk, it is necessary to solve a contact problem between the android model and the ground, and to simulate an automobile collision, it is necessary to solve an interference problem between automobiles. (d) Game software Conventional game software was mostly two-dimensional, but in the future it is expected that those that use graph computers and display three-dimensionally will become mainstream. In game software, for example, there are many interference problems between objects such as a collision between a missile and a fighter in a shooting game and a collision between cars in a racing game. The real-time interference check system of the present invention provides a powerful means in the above application field. As described above, the present invention has been described with reference to the embodiments. However, the present invention can be variously modified in accordance with 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 exists on a grid point, on a side, or on a polygon. If it exists on the side, (2) When the polygon that constitutes the grid point is obtained from the directed graph type structural data, and the grid point of the polygon is used for inner product evaluation in the closest approach point search process by the GIbert method, The polygons constituting the side are obtained, and the grid points of the polygons are used for the inner product evaluation. (3) When the polygon points are present on the polygon, the grid points of the polygon are used for the inner product evaluation. , The number of grid points applied to the inner product evaluation can be reduced, and the calculation load can be reduced.

According to the present invention, the surface polygon (polygon) constituting the convex polyhedron is divided into triangles, and whether the point of closest approach of each convex polyhedron exists on a lattice point or on a side is determined. It is determined whether or not it exists on a triangular polygon. (1) If it exists on a grid point, a triangular polygon constituting the grid point is obtained from the directed graph type structure data, and the grid point of the triangular polygon is used for inner product evaluation. (2) If it exists on a side, a triangular polygon constituting the side is obtained, and grid points of the triangular polygon are used for inner product evaluation. (3) If the triangular polygon exists on a 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, a minimum convex polyhedron (convex hull) enclosing a non-convex polyhedron is generated, directed graph type structure data of the convex hull is created, and the directed graph type structure data of the convex hull is used. The closest point between non-convex polyhedrons is searched for, 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 constituting the polyhedron, the closest point search between non-convex polyhedrons can be performed, and a surface convex polygon with virtuality = 1 can be used. It is possible to reduce the calculation load required for the closest approach point search processing until it interferes with another object. Further, according to the present invention, after the surface convex polygon of virtuality = 1 interferes with another object and releases the convex hull, when the surface convex polygon no longer interferes with another object, the convex hull is removed. Since the closest approach point search processing is performed after restoration, the calculation load of the closest approach point search processing after restoration can be reduced.

[0171]

[Brief description of the drawings]

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

FIG. 2 is an exploded explanatory 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 a point of closest approach (in the case of a hexahedron).

FIG. 4 is a processing flowchart of a first closest approach point search method of the present invention.

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

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

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

FIG. 8 is an explanatory diagram of triangulation of a polygon.

FIG. 9 is a processing flowchart of a second closest approach point search method.

FIG. 10 is a configuration 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 flowchart 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 changes dynamically.
(Part 1).

FIG. 18 is an explanatory diagram of the present invention when the environment changes dynamically.
(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 flowchart of searching for a point of closest approach between non-convex polyhedrons.

FIG. 22 is a configuration diagram of a device for searching for a point of closest approach between non-convex polyhedrons according to the present invention.

FIG. 23 is an explanatory diagram of a first method of continuous search for the closest point between non-convex polyhedrons.

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

FIG. 25 is an explanatory diagram of a second method of continuous search for the closest point between non-convex polyhedrons.

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

FIG. 27 is a system configuration diagram.

FIG. 28 is a schematic processing flow of an interference check pre-processing;

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

FIG. 30 is a flowchart of the Merge process.

FIG. 31 is an explanatory diagram of determining the unevenness relationship between polygons.

FIG. 32 is a process flow of a second embodiment of the pre-decomposition processing.

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

FIG. 34 is a processing flow of a third embodiment of the pre-decomposition processing.

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 embodiment of the pre-decomposition processing.

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

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

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

FIG. 40 is a schematic processing 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 modified example of convex decomposition.

FIG. 45 is a processing flow of a second modified example of the convex decomposition.

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

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

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

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 proximity point linear list.

FIG. 51 is another explanatory diagram of the algorithm for generating the proximity point linear list.

FIG. 52 is an explanatory diagram of creation of a proximity point linear list.

FIG. 53 is an example of a proximity point multi-tree list.

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

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

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

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

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

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

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 a convex hull and a convex element.

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

FIG. 63 is a flowchart of dynamic configuration / release of a convex hull and a continuous polyhedron continuous interference check.

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

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

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

FIG. 67 is a flowchart of a dynamic configuration / release of a convex hull and an algorithm for checking an envelope sphere interference.

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

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

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

FIG. 72 is an explanatory diagram of the search for the closest approach 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 is an explanatory diagram of searching for a point of closest approach between non-convex polyhedrons using the Gilbert method.

[Explanation of symbols]

 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

──────────────────────────────────────────────────続 き Continued on the front page (72) Inventor Tsutomu Maruyama Fujitsu Limited (1015) Kamikodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Prefecture (58) Field surveyed (Int.Cl. ⁷ , DB name) G06F 17/50 628

Claims (8)

(57) [Claims] 1. A difference convex polyhedron which is a set of two convex polyhedrons.
Formed by a subset of p elements on the body
Up to the shapeFrom the originFind the closest point, and find the position of the closest point.
Between the position vector and the position vector of the lattice point of each convex polyhedron
Evaluate the product and determine whether the closest point is the origin based on the evaluation result.
From the point of closest approach to the convex polyhedron from the
If not, change the subset and finally
Find the closest point to the convex polyhedron and find the closest point for each convex polyhedron
Finding the closest approach pointapparatusThe polygons below each surface polygon (polygon) of the convex polyhedron
The grid points and sides that are the elements of the
Array the polygons that make up the grid points and sidesDo
And directed graph type structural data expressing each convex polyhedron by
Graph-structured data generator that creates a graph , Storage unit for storing the directed graph type structure data , Of the shape formed by the subsetFrom the originTo the closest point
Closest point on each corresponding convex polyhedronMeans to seek, Closest point on each convex polyhedron Exists on a grid point or on an edge
Or on a polygon, lattice
If it exists on a point, the
Find the polygons that make up the grid points and calculate the grid points
To the inner product evaluationShall be used,A place that exists on the side
In this case, the direction
Gon is calculated, and the grid points of the polygon areUse
Shall beIf it exists on a polygon, the polygon
Grid points for the inner product evaluationTo use , Internal commentary
Means for finding grid points for value , Perform inner product evaluation using the grid points for the inner product evaluation original
Find the point of closest approach from the point to the difference convex polyhedron and calculate each convex polyhedronUp
The closest point to find the closest pointmeans , Closest point searching device having 2. Searching for the closest point between non-convex polyhedrons
Produces the smallest convex polyhedron (convex hull) that wraps the nonconvex polyhedron
MakeConvex hull generator,  Create a directed graph type structure data of the convex hullThe storage unit
Means to store in , Equipped , The closest point searching means, Directed graph of the convex hull
Search for the closest point between non-convex polyhedrons using type structure data
Search for the closest approach point according to claim 1.apparatus. 3. The closest approach point searching means, wherein the surface convex polygon constituting the convex hull coincides with the surface convex polygon of the original non-convex polyhedron; If charity = 1 and the surface convex polygon with virtuality = 1 interferes with another object, the convex hull is released,
3. The closest point searching device according to claim 2, wherein a closest point searching process is performed on a plurality of convex polyhedrons constituting the non-convex polyhedron. 4. The closest approach point searching means, wherein the convex hull is restored and the convex hull is restored when the surface convex polygon of virtuality = 1 does not interfere with another object after the convex hull is released. 4. The closest point searching device according to claim 3, wherein: 5. A means for generating a minimum convex polyhedron (convex hull) enclosing the non-convex polyhedron when searching for a point of closest approach between the non-convex polyhedrons, dividing a polygon constituting the convex hull into triangles. and, by creating a directed graph type structure data the smallest unit of a polygon as a triangle polygon comprising means for storing in the storage unit, the closest approach point search means, non-convex using the directed graph type structure data of the convex hull The apparatus for searching for a point of closest approach between polyhedrons according to claim 1. 6. The closest approach point searching means sets virtuality = 0 when a triangular polygon constituting the convex hull matches the triangular polygon of the original non-convex polyhedron, and sets virtuality = 1 when the triangular polygon does not match. 6. The method according to claim 5, wherein when the triangular polygon with virtuality = 1 interferes with another object, the convex hull is released, and thereafter, a closest point search process is performed on a plurality of convex polyhedrons constituting the non-convex polyhedron. Search for the closest approach point
Equipment . 7. The closest approach point searching means performs a closest approach point search process by restoring the convex hull when the triangular polygon with virtuality = 1 does not interfere with another object after releasing the convex hull. An apparatus for searching for a point of closest approach according to claim 6. 8. A difference convex polyhedron, which is a difference set of two convex polyhedrons
Formed by a subset of p elements on the body
Up to the shapeFrom the originFind the closest point, and find the position of the closest point.
Between the position vector and the position vector of the lattice point of each convex polyhedron
Evaluate the product and determine whether the closest point is the origin based on the evaluation result.
From the point of closest approach to the convex polyhedron from the
If not, change the subset and finally
Find the closest point to the convex polyhedron and find the closest point for each convex polyhedron
Finding the closest approach pointapparatusIn, each surface polygon (polygon) of the convex polyhedron is divided into triangles
And below each triangle polygon,
Arrange the grid points and sides that are
Array of triangular polygons that make up grid points and sidesTo do
Gives a directed graph type structure data that represents each convex polyhedron
Directed graph type structure data creation unit to create , The directed graph
Storage unit for storing type structure data , Of the shape formed by the subsetFrom the originTo the closest point
Closest point on each corresponding convex polyhedronMeans to seek, Closest point on each convex polyhedron Exists on a grid point or on an edge
Or on a triangular polygon,
Directed graph type structure data if it exists on a grid point
Then, a triangular polygon constituting the grid point is obtained,
The grid points of the polygon are evaluated for the inner productShall be used,
If it exists on the edge, use the directed graph type data
A triangular polygon constituting the side is obtained, and the triangular polygon is
Grid points for the inner product evaluationShall be used,triangle
The grid of the triangular polygon if it is on a polygon
Points to the inner product evaluationTo use , Case for inner product evaluation
Means for finding child points , Perform inner product evaluation using the grid points for the inner product evaluation original
Find the closest point from the point to the difference convex polyhedron, and on each convex polyhedron
The closest point to find the closest pointmeans , Closest point searching device having