next up previous contents
Next: Object Relative Position Representation Up: Space and Shape Representation Previous: Shape Boundary Representation

Constructive Solid Geometry Representation

Boundary shape representation is useful both for visual shape recognition, and for planning robot actions - the first because many industrial recognition tasks can proceed on the basis of boundary information only, and the second because robots only interact with shapes on their boundaries. Boundary representation does have disadvantages, however, where humans must operate with the representation, since we more often consider three dimensional objects to be collections of solid masses, rather than collections of surfaces.

For this reason, robot programming research has resulted in different types of shape representation from those used in object recognition or robot control. Constructive solid geometry (CSG) is often used for this purpose. In a CSG representation, overall three dimensional shape is described as a combination of simpler solids, which in turn can be decomposed, until an atomic level of ``shape primitives'' is reached.

An early paper by Grossman [Gro76] described the use of procedure calls to represent nested arrangements of parts and subparts in an assembly. The procedural structure of these reflected the hierachically decomposed structure of the assembly.

The approach became more sophisticated with the addition of a ``semantic overlay'' in a joint representation development project involving Grossman and Lozano-Perez, together with Wesley and Lieberman, the chief architects of the experimental AUTOPASS language [WLPL+80]. The ``Geometric Design Processor'' merges entities from the classes of object, hole, fastener, assembly, and so on, to form descriptions of assemblies in the world. The ``world-graph'' includes pointers to rigid or non-rigid objects, which in turn refer to their neighbours with friction and constraint relationships.

Generic objects, or particular objects in a scene, can be composed from combinations of solid primitives and ``hole'' primitives (which describe empty space). The primitive shapes available are cuboid, cylinder, cone, wedge, hemisphere, laminum (flat things), and revolute (solids of revolution). In addition to the shape description facilities of the geometric design processor, the AUTOPASS language provided facilities to describe robot operations at a ``human'' level, with basic operators such as `` INSERT'' and `` ATTACH''.

The designers of this representation system anticipated that it would be applied to computer vision, path planning, high level robot programming, and graphical design. In fact, the complexity of the system when compared to methods such as space filling or boundary representation has meant that few attempts have been made to use it so far. The AUTOPASS language has not been completed, so it is difficult to assess the overall utility of the scheme, but it includes many of the concepts that appear in other advanced representations.

Constructive solid geometry representations are discussed further under the heading of computer aided design below, since this is where they have most widely been used.

next up previous contents
Next: Object Relative Position Representation Up: Space and Shape Representation Previous: Shape Boundary Representation
Alan Blackwell