Arithmetic unit for calculating distance between objects

• US 5,761,391 A
• Filed: 10/02/1996
• Issued: 06/02/1998
• Est. Priority Date: 05/22/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Maruyama, Tsugito, Sato, Yuichi, Hirata, Mitsunori
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Rhodes, Jason W.
• Application Number:
  US08/725,308
• Time in Patent Office: 608 Days
• Field of Search: 364/461, 364/460, 395/119, 395/90, 395/105, 395/120
• US Class Current: 700/255
• CPC Class Codes: G05B 19/41 characterised by interpolation, e.g. the computation of intermediate points between programmed end points to define the path to be followed and the rate of travel along that path G05B19/25, G05B19/31, G05B19/37, G05B19/39, G05B19/40 take precedence
• CPC Class Codes: G05B 2219/35084 Geometric feature extraction, concave and convex regions, object recognition
• CPC Class Codes: G05B 2219/49137 Store working envelop, limit, allowed zone

Abstract

A unit in a computer for computing a closest distance between two three-dimensional convex objects. At least one of the objects is a convex curved surface object. A first closest vector arithmetic unit is provided for identifying a preliminary closest vector coupling the closest points of the two objects by repeatedly calculating for each object an inner product of a candidate for the preliminary closest vector directed from a first of the two objects to a second of the two objects and a plurality of position vectors. Each position vector being one of a position vector of a vertex where the first object is a convex polyhedron, and a position vector of a control point of a convex curved surface patch where the first object is a convex curved surface object comprising sets of convex curved surface patches. A position vector for each object having a maximum inner product is extracted and a new candidate for the preliminary closest vector is formed by a vector connecting the two position vectors. A second closest vector arithmetic unit corrects the preliminary closest vector to identify a new closest vector perpendicularly intersecting a tangent plane in contact with the object having a convex curved surface at the closest point by starting from the preliminary closest vector and sequentially updating a given coordinate on the surface of the object until an inner product of a vector on the tangent plane and the closest vector on the given coordinates has the smallest possible value.

Claims

1. An arithmetic unit in a computer for computing a closest distance between a first and a second three-dimensional convex object, at least one of the objects being a convex curved surface object, in accordance with shape information including arrangement position information about the objects, the arithmetic unit comprising:

first closest vector arithmetic means for identifying a preliminary closest vector coupling the closest points of the two objects, displayed on a computer screen by repeatedly calculating for each object an inner product of a candidate for the preliminary closest vector directed from a first of the two objects to a second of the two objects and a plurality of position vectors, each position vector being one of;

a position vector of a vertex where the first object is a convex polyhedron defined by vertexes, and

a position vector of a control point of a convex curved surface patch where the first object is a convex curved surface object comprising sets of convex curved surface patches defined by control points, wherein a position vector for each object having a maximum inner product is extracted and a new candidate for the preliminary closest vector is formed by a vector connecting the two position vectors; and

second closest vector arithmetic means for correcting the preliminary closest vector identified by said first closest vector arithmetic means to identify a new closest vector perpendicularly intersecting a tangent plane in contact with the object having a convex curved surface at the closest point of the object having a convex curved surface by starting from the preliminary closest vector and sequentially updating a given coordinate on the surface of the object having a convex curved surface until an inner product of a vector on the tangent plane and the closest vector on the given coordinates has the smallest possible value.

2. An arithmetic unit according to claim 1, wherein said arithmetic unit further comprises collision determination means for determining whether the first and second objects are in a collision state in accordance with the new closest vector evaluated by said second closest vector arithmetic means.

3. An arithmetic unit according to claim 1, wherein said arithmetic unit further comprises:

shape information storage means for storing shape information comprising sets of the control points constituting the convex curved surface patches constituting the object having a convex curved surface including sets of the vertexes of a convex polygon in a case where one of the objects is a convex polyhedron;

shape information updating means for performing arithmetic on coordinates after a movement or a deformation of the vertexes or the control points of the objects in accordance with information for instructing a movement or a deformation of the objects, thereby evaluating a new shape information; and

curved surface patch information producing means for producing convex curved surface patches constituting the object having a convex curved surface in accordance with the shape information of the object having a convex curved surface.

4. An arithmetic unit according to claim 3, wherein when the object is moved or deformed, said second closest vector arithmetic means modifies the new closest vector evaluated before a current movement or deformation to a further new closest vector, instead of evaluating a closest vector after a movement or a deformation by said first closest vector arithmetic means.

5. An arithmetic unit according to claim 3, wherein said arithmetic unit further comprises display means for displaying the objects based on the shape information stored in said shape information storage means and the new shape information evaluated by said shape information updating means.

6. An arithmetic unit in a computer for computing a closest distance between a first and a second two dimensional convex object, at least one of the objects being a convex curved line object, in accordance with shape information including arrangement position information about the objects, comprising:

first closest vector arithmetic means for identifying a preliminary closest vector coupling the closest points of the two objects, displayed on a computer screen by repeatedly calculating for each object an inner product of a candidate for the preliminary closest vector directed from a first of the two objects to a second of the two objects and a plurality of position vectors, each position vector being one of;

a position vector of a vertex where the first object is a convex polyhedron defined by vertexes, and

a position vector of a control point of a convex curved line patch where the first object is a convex curved line object comprising sets of convex curved surface patches defined by control points, wherein a position vector for each object having a maximum inner product is extracted and a new candidate for the preliminary closest vector is formed by a vector connecting the two position vectors; and

second closest vector arithmetic means for correcting the preliminary closest vector identified by said first closest vector arithmetic means to identify a new closest vector perpendicularly intersecting a tangent plane in contact with the convex curved line object at the closest point of the convex curved line object by starting from the preliminary closest vector and sequentially updating a given coordinate on the surface of the object having a convex curved surface until an inner product of a vector on the tangent plane and the closest vector on the given coordinates has the smallest possible value.

7. An arithmetic unit according to claim 6, wherein said arithmetic unit further comprises collision determination means for determining whether the first and second objects are in a collision state in accordance with the new closest vector evaluated by said second closest arithmetic means.

8. An arithmetic unit according to claim 6, wherein said arithmetic unit further comprises:

shape information storage means for storing shape information comprising sets of the control points constituting the convex curved line patches constituting the convex curved line object, including sets of the vertexes of a convex polygon where one of the objects is a convex polyhedron;

shape information updating means for performing arithmetic on coordinates after a movement or a deformation of the vertexes or the control points of the objects in accordance with information for instructing a movement or a deformation of the objects, thereby evaluating a new shape information; and

curved line patch information producing means for producing convex curved line patches constituting the convex curved line object in accordance with the shape information of the convex curved line object.

9. An arithmetic unit according to claim 8, wherein when the object is moved or deformed, said second closest vector arithmetic means modifies the new closest vector evaluated before a current movement or deformation to a further new closest vector, instead of evaluating a closest vector after a movement or a deformation by said first closest vector arithmetic means.

10. An arithmetic unit according to claim 8, wherein said arithmetic unit further comprises display means for displaying the objects based on the shape information stored in said shape information storage means and the new shape information evaluated by said shape information updating means.