Algorithm for representation of objects to enable robotic recongnition

• US 5,760,778 A
• Filed: 08/15/1995
• Issued: 06/02/1998
• Est. Priority Date: 08/15/1995
• Status: Expired due to Fees

• Current Assignee: Glenn M. Friedman
• Original Assignee: Glenn M. Friedman
• Inventors: Friedman, Glenn M.
• Primary Examiner(s): Nguyen, Phu K.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US08/515,303
• Time in Patent Office: 1,022 Days
• Field of Search: 395/120, 395/119, 395/121, 395/123, 395/124, 395/125, 364/468.04, 364/578, 382/173
• US Class Current: 345/420
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06V 10/422 for representing the structure of the pattern or shape of an object therefor

Abstract

An algorithm for representing complex three-dimensional objects in a computer for the purpose of robotic recognition of such objects comprises the generation of superquadric volume primitives, the combination of such superquadric volume primitives, the discarding of all vertices making up such volume primitives except for surface vertices, and the automatic generation of a Winged Edge graph structure from the list of surface vertices. The size of the Winged Edge graph structure is reduced by joining adjacent, coplanar faces, removing the common edge of such faces, and joining unidirectional, collinear edges resulting from any joining of adjacent, coplanar faces.

Claims

1. An algorithm for the efficient representation of complex three-dimensional objects, said algorithm aiding in the robotic recognition of objects and comprising the steps of:

a. the generation of superquadric volume primitives;

b. converting said superquadric volume primitives into voxels in a voxel space;

c. combining said voxels at the direction of a user of the algorithm to obtain a volumetric representation of a particular three-dimensional object;

d. discarding all voxels except for the surface voxels included in said volumetric representation of said particular three-dimensional object; and

e. automatically generating from the list of said surface voxels a Winged Edge graph structure, said Winged Edge graph structure comprising edges and faces automatically generated by said algorithm from said list of said surface voxels, said Winged Edge graph structure representing said particular three-dimensional object in a computer;

said particular three-dimensional object not being defined by said Winged Edge graph structure until the termination of said algorithm.

2. An algorithm according to claim 1, wherein said generation of said superquadric volume primitives is accomplished by the use of ruled shape functions.

3. An algorithm according to claim 2, wherein said ruled shape functions generate ruled volume functions.

4. An algorithm according to claim 3, wherein said superquadric volume primitives are a subset of said ruled volume functions.

5. An algorithm according to claim 4, wherein said ruled volume functions are generated by at least three of said ruled shape functions, said ruled shape functions being shape functions of two basis quantities, a squareness parameter, and at least one angular parameter.

6. An algorithm according to claim 5, wherein, said squareness parameter is a squareness function of two basis quantities, a rotation parameter, and an angular parameter.

7. An algorithm according to claim 6, wherein said shape functions and said squareness function comprise a superinterpolator function.

8. An algorithm according to claim 6, wherein said shape functions and said squareness function comprise a superelliptic function.

9. An algorithm according to claim 1, wherein said combining of said voxels comprises employing the following operations:

(a) Union;

(b) Intersection;

(c) Complement; and

(d) Difference.

10. An algorithm according to claim 1, wherein said discarding of all voxels except for said surface voxels comprises searching for adjacent voids for every voxel in said volumetric representation of a particular three-dimensional object.

11. An algorithm according to claim 1, wherein said automatic generation of a Winged Edge graph structure comprises:

a. searching said voxel space for the first occurrence of a voxel;

b. upon finding said first voxel, initializing said Winged Edge graph structure as a self-loop;

c. for each voxel found after said first voxel, forward searching by Cartesian coordinates normally, diagonally, and at corners for adjacent voxels;

d. creating an edge between said voxel and each of said adjacent voxels;

e. for each of said newly created edges that shares a common voxel with an existing edge, defining the necessary adjacency relationships between said newly created edge and said existing edge; and

f. for each of said newly created edges that shares a common voxel with an existing edge and that completes a closed loop of edges, said closed loop of edges establishing a new face, joining said new face to said Winged Edge graph structure.

12. An algorithm according to claim 11, further comprising joining adjacent coplanar faces.

13. An algorithm according to claim 12, further comprising removing the edge common to said adjacent coplanar faces which are joined.

14. An algorithm according to claim 13, further comprising joining edges which are unidirectional, collinear, and share a common voxel.