Method of searching for points of closest approach, and preprocessing method therefor

• US 5,675,720 A
• Filed: 09/19/1996
• Issued: 10/07/1997
• Est. Priority Date: 09/14/1993
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nagashima, Fumio, Maruyama, Tsugito, Sato, Yuichi, Hirata, Mitsunori
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): HONG, STEPHEN S
• Application Number:
  US08/710,550
• Time in Patent Office: 383 Days
• Field of Search: 395/119, 395/120, 395/121, 395/123, 395/127, 395/138, 395/90, 395/958, 395/173, 395/174, 364/460, 364/461, 364/462, 364/474.28
• US Class Current: 345/419
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: Y10S 345/958 Collision avoidance

Abstract

A method of searching for a point of closest approach between two convex polyhedrons K₁, K₂, wherein each convex polyhedron is expressed by creating directed-graph structure data. The method uses a processing unit for searching for points of closest approach. The method includes the step of successively obtaining points of closest approach to a difference convex polyhedron, which is a difference of sets (K₁ -K₂) between the two convex polyhedrons K₁, K₂, and finally obtaining the point of closest approach on each convex polyhedron K₁, K₂. In the evaluation of inner products executed in the course of searching for points of closest approach, the method further includes the step of judging whether the point of closest approach on each convex polyhedron corresponding to the successively obtained point of closest approach to the difference convex polyhedron resides on a vertex, edge or polygon. This judging step is also performed by the processing unit. In each particular case, the vertices used in the inner-product evaluation are obtained from the directed-graph structure data and the inner product evaluation is performed using the position vectors of these vertices.

Claims

1. A point-of-closest-approach search method for one of collision avoidance between two convex polyhedrons and path planning in operating a robot, said method searching for a point of closest approach from a coordinate origin to a figure which is one of a polygon and a polyhedron formed by a subset whose elements are p-number of points on a difference convex polyhedron, which is formed by a set of position vectors obtained by vector subtraction of arbitrary position vectors of two convex polyhedrons, calculating an inner product between a position vector x of the point of closest approach and position vectors of the vertices of each convex polyhedron, calculating a sum of the inner product and |X |², judging, in a case where the sum is equal to 0, that the point of closest approach is a point of closest approach from the coordinate origin to the difference convex polyhedron and, in a case where the sum is not 0, altering the figure by changing a combination of said p-number of points, repeating the previous steps until the sum becomes 0, and finally obtaining the point of closest approach from the coordinate origin to the difference convex polyhedron to thereby find a point of closest approach of each convex polyhedron, said method comprising the steps of:

expressing each convex polyhedron by directed-graph structure data which is obtained by arraying surface polygons of the corresponding convex polyhedron, arraying vertices and edges, which are elements of the corresponding surface polygon, below each corresponding surface polygon of the corresponding convex polyhedron and arraying polygons, which form the vertices and edges, below respective ones of the vertices and edges;

determining whether a point of closest approach on each convex polyhedron corresponding to the point of the closest approach from the coordinate origin to the figure resides on one of the corresponding vertices, edges and surface polygons of the corresponding convex polyhedron;

if the point of closest approach resides on one of the corresponding vertices, obtaining the surface polygons forming this vertex from the directed-graph structure data and using position vectors of the vertices of the obtained surface polygons in the next calculation of said inner product;

if the point of closest approach resides on one of the corresponding edges, obtaining the surface polygons forming this edge from the directed-graph structure data and using position vectors of the vertices of the obtained surface polygons in the next calculation of said inner product;

if the point of closest approach resides on one of the corresponding polygons, using position vectors of the vertices of this polygon in the next calculation of said inner product, thereby obtaining the point of closest approach from the origin to the difference convex polyhedron and obtaining the point of closest approach of each convex polyhedron; and

controlling operation of the robot based upon the points of closest approach.

2. The method according to claim 1, further comprising the following steps when searching the point of closest approach between non-convex polyhedrons:

generating convex hulls which are the smallest convex polyhedrons which cover the respective non-convex polyhedrons;

creating directed-graph structure data of the convex hulls; and

searching for the point of closest approach between the non-convex polyhedrons using the directed-graph structure data of the convex hulls.

3. The method according to claim 2, further comprising the steps of:

rendering a flag which is referred to as virtuality="0" if a surface convex polygon forming one of the convex hulls is same as a surface convex polygon of the corresponding non-convex polyhedron and virtuality="1" if the surface convex polygon forming the convex hull is not the same as the surface convex polygon of the corresponding non-convex polyhedron; and

if the surface convex polygon of virtuality="1" has interfered with another convex hull, decomposing the corresponding non-convex polyhedron into a plurality of convex polyhedrons which form the corresponding non-convex polyhedron, and processing for searching for a point of closest approach with regard to the individual convex polyhedrons.

4. The method according to claim 3, wherein when a surface convex polygon of virtuality="1" ceases interfering with the another convex hull, the canceled convex hull is generated again and processing for searching for a point of closest approach is executed.

5. The method according to claim 1, further comprising the following steps when searching for a point of closest approach between non-convex polyhedrons:

generating smallest convex hulls which are the smallest convex polyhedrons which cover the respective non-convex polyhedrons;

partitioning polygons forming the convex hulls into triangles and creating directed-graph structure data in which smallest units of the polygons serve as triangular polygons; and

searching for the point of closest approach between the non-convex polyhedrons using the directed-graph structure data of the convex hulls.

6. The method according to claim 5, further comprising the steps of:

rendering a flag which is referred to as virtuality="0" if a triangular polygon forming one of the convex hulls is same as a triangular polygon of the corresponding non-convex polyhedron and virtuality="1" if the triangular polygon forming the one of the convex hulls is not the same as the triangular polygon of the corresponding non-convex polyhedron; and

if a triangular polygon of virtuality="1" has interfered with another convex hull, decomposing the corresponding non-convex polyhedron into a plurality of convex polyhedrons which form the corresponding non-convex polyhedron and processing for searching for a point of closest approach with regard to the individual convex polyhedrons is executed.

7. The method according to claim 6, wherein when a triangular polygon of virtuality="1" ceases interfering with another convex hull, the corresponding convex hull is generated again and processing for searching for a point of closest approach between the non-convex polyhedrons using the directed-graph structure data of the convex hulls is executed.

8. A point-of-closest-approach search method for one of collision avoidance between two convex polyhedrons and path planning in operating a robot, said method searching for a point of closest approach from a coordinate origin to a figure, which is one of a polygon and polyhedron, formed by a subset whose elements are p-number of points on a difference convex polyhedron, which is formed by a set of position vectors obtained by vector subtraction of arbitrary position vectors of two convex polyhedrons, calculating an inner product between a position vector x of the point of closest approach and position vectors of the vertices of each convex polyhedron, calculating a sum of the inner product and |x|², judging, in a case where the sum is equal to 0, that the point of closest approach is a point of closest approach from the origin to the difference convex polyhedron and, in a case where the sum is not 0, altering the figure by changing a combination of said p-number of points, repeating previous steps until the sum equals 0, and finally obtaining the point of closest approach from the coordinate origin to the difference convex polyhedron to thereby find a point of closest approach of each convex polyhedron, said method comprising the steps of:

partitioning each surface polygon of the convex polyhedrons into triangular polygons and expressing each convex polyhedron by directed-graph structure data which is obtained by arraying triangular polygons of the convex polyhedrons, arraying vertices and edges, which are elements of the triangular polygons, below the corresponding triangular polygon and arraying the triangular polygons, which form the vertices and edges, below respective ones of the vertices and edges;

determining whether a point of closest approach on each convex polyhedron corresponding to the point of closest approach from the coordinate origin to the figure resides on one of the corresponding vertices, edges and triangular polygons;

if the point of closest approach resides on one of the corresponding vertices, obtaining the triangular polygons forming this vertex from the directed-graph structure data and using the vertices of the obtained triangular polygons in the next calculation of said inner product;

if the point of closest approach resides on one of the corresponding edges, obtaining the triangular polygons forming this edge from the directed-graph structure data and using position vectors of the vertices of the obtained triangular polygons in the next calculation of said inner product;

if the point of closest approach resides on one of the corresponding triangular polygons, using position vectors of the vertices of this triangular polygon in the next calculation of said inner product, thereby obtaining the point of closest approach from the origin to the difference convex polyhedron and obtaining the point of closest approach on each convex polyhedron; and

controlling operation of the robot based upon the points of closest approach.

9. A point-of-closest-approach search method for one of collision avoidance between two convex polyhedrons and path planning in operating a robot, said method continuously searching for a point of closest approach between two convex polyhedrons to check for interference between the two convex polyhedrons, said method comprising the steps of:

inputting vertex coordinates of all polygons covering each convex polyhedron;

creating for each convex polyhedron, a list which is referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by an edge of any polygon are arranged adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;

obtaining vertices, which are adjacent to a point of closest approach obtained most recently on each convex polyhedron, from the nearby-point linear list of each convex polyhedron;

performing an interference check by searching for a point of closest approach on each convex polyhedron at a next moment in time from among said obtained vertices of each convex polyhedron;

controlling operation of the robot based upon the points of closest approach.

10. A point-of-closest-approach search method for one of collision avoidance between two non-convex polyhedrons and path planning in operating a robot, said method decomposing first and second non-convex polyhedrons into respective ones of convex polyhedrons and continuously searching for points of closest approach between the convex polyhedrons, thereby checking for interference between the non-convex polyhedrons, said method comprising the steps of:

creating, for each convex polyhedron, a list referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by a an edge of any polygon are arrayed adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;

obtaining, for each non-convex polyhedron, a maximum coordinate value V_max and a minimum coordinate value V_min, along each axis, from among coordinate value of vertices of the non-convex polyhedron, and generating an envelope sphere, having a diameter equal to a value |V_max -V_min |, to be able to cover the non-convex polyhedron;

checking whether envelope spheres of the first and second non-convex polyhedrons interfere with each other;

searching for a point of closest approach between two arbitrary convex polyhedrons obtained by decomposing the non-convex polyhedrons after the envelope spheres of the first and second non-convex polyhedrons have interfered with each other;

obtaining vertices which are adjacent to the point of closest approach obtained most recently on each convex polyhedron, from the nearby-point linear list of each convex polyhedron, and searching for a point of closest approach at a next moment in time from among these vertices;

performing an interference check using whichever distance between points of closest approach between the convex polyhedrons is shortest; and

controlling operation of the robot based upon the points of closest approach.

11. The method according to claim 10, further comprising the steps of:

generating convex hulls which are the smallest convex polyhedrons which cover the respective non-convex polyhedrons;

checking whether the convex hulls of the first and second convex polyhedrons interfere after the envelope spheres of the first and second non-convex polyhedrons have interfered; and

after the convex hulls of the first and second convex polyhedrons have interfered with each other, performing an interference check by searching for the point of closest approach between convex polyhedrons obtained by decomposing the non-convex polyhedrons.

12. A point-of-closest-approach search method for one of collision avoidance between two non-convex polyhedrons and path planning in operating a robot, said method decomposing first and second non-convex polyhedrons into respective ones of convex polyhedrons and continuously searching for points of closest approach between the convex polyhedrons, thereby checking for interference between the non-convex polyhedrons, said method comprising the steps of:

creating for each convex polyhedron, a list referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by an edge of any polygon are arrayed adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;

generating convex hulls which are the smallest convex polyhedrons which cover the respective non-convex polyhedrons;

checking whether the convex hulls of the first and second convex polyhedrons interfere;

searching for a point of closest approach between two arbitrary convex polyhedrons after the convex hulls have interfered with each other;

obtaining vertices which are adjacent to the point of closest approach obtained most recently on each convex polyhedron, from the nearby-point linear list of each convex polyhedron, and searching for a point of closest approach at a next moment in time from among these vertices;

performing an interference check using whichever distance between points of closest approach between the convex polyhedrons is shortest; and

controlling operation of the robot based upon the points of closest approach.

13. The method according to claim 12, wherein after the convex hulls have interfered with each other, one of the convex hulls is canceled and an interference check is performed between the other convex hull and each convex polyhedron obtained by decomposing the corresponding non-convex polyhedron;

and

after interference has occurred between a convex polyhedron and the other convex hull, the other convex hull is canceled and an interference check is performed by searching for a point of closest approach between the convex polyhedrons obtaining by decomposing each of the non-convex polyhedrons.

14. A point-of-closest-approach search method for one of collision avoidance between two convex polyhedrons and path planning in operating a robot, said method searching for a point of closest approach from a coordinate origin to a figure which is one of a polygon and a polyhedron formed by a subset whose elements are p-number of points on a difference convex polyhedron, which is formed by a set of position vectors obtained by vector subtraction of arbitrary position vectors of two convex polyhedrons, calculating an inner product between a position vector x of the point of closest approach and position vectors of the vertices of each convex polyhedron, calculating a sum of the inner product and |x|², judging, in a case where the sum is equal to 0, that the point of closest approach is a point of closest approach from the coordinate origin to the difference convex polyhedron and, in a case where the sum is not 0, altering the figure by changing a combination of said p-number of points, repeating the previous steps until the sum becomes 0, and finally obtaining the point of closest approach from the coordinate origin to the difference convex polyhedron to thereby find a point of closest approach of each convex polyhedron, said method comprising the steps of:

inputting vertex coordinates of all polygons covering each convex polyhedron;

creating for each convex polyhedron, a list referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by an edge of any polygon are arrayed adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;

obtaining vertices from the nearby-point linear list of each convex polyhedron which are adjacent to a point of closest approach on each convex polyhedron corresponding to the point of the closest approach from the coordinate origin to the figure;

using position vectors of the obtained vertices in the next calculation of said inner product, thereby obtaining the point of closest approach from the origin to the difference convex polyhedron and obtaining the point of closest approach of each convex polyhedron; and

controlling operation of the robot based upon the points of closest approach.