next up previous contents
Next: A Two Dimensional Derivative Up: 2D Qualitative Geometry from Previous: 2D Qualitative Geometry from

A Two Dimensional Derivative of Constructive Solid Geometry

The basis of constructive solid geometry is the description of complex shapes as a combination of simpler ones. Therefore the fundamental requirements of a CSG scheme are: a set of primitive shapes, and a method of describing the relationships between primitives. Applications of CSG in the robotics domain (e.g. [WLPL+80]) had previously found that it was also useful to be able to define new primitives, such as solids of revolution, or laminar shapes.

A large set of simple primitives for CSG, and also some complex shapes, can be elegantly defined using the generalised cones method. Geometric primitives such as cones, pyramids, or blocks can all be described as a two dimensional shape swept along an axis, as can mechanical ``primitives'' such as washers, brackets, channels and wires. This appeared to provide a consistent way of both describing standard primitives, and defining new ones when necessary. The sweeping axis can also be used as a reference direction when combining primitives.

There is no two dimensional equivalent of the generalised cones method that provides the same kind of power in description of physical objects. It is certainly possible to construct two dimensional shape in terms of swept line segments, but there is little advantage to be gained in doing so, especially since it is difficult to gain qualitative knowledge about the shape from this type of construction. The alternative that I chose was to define shape primitives in terms of their qualitative features - features such as curves, angles, and lines.

The shape elements that are constructed from these features are still defined in terms of axes, and are combined in the same way as subobjects are combined in CSG schemes - by defining the relative positions of their axes, together with a logical operator. A single general method was used to define objects, subparts and features; all shape features are described in terms of their axes, so that the feature can be described relative to the overall axes of the subpart, which are then described relative to the axes of other subparts.

A conscious concern in proposing this representation was that it should be feasible to construct a scene description from visual data. This is one of the disadvantages of constructive solid geometry - although it is easy for people to define a complex shape using CSG, it is not so easy to take a picture of a complex shape, and construct a CSG representation from it. In fact, CSG cannot be used as the basis for a canonical shape description, because there is no unique set of primitives which combine to form a given shape. The feature-based qualitative representation could however make use of a number of techniques for feature detection in scenes (such as [KJ86] [RKH85]).

Connell and Brady describe a method for decomposing two dimensional shape into CSG-like primitives. The smoothed local symmetry representation makes use of cues from the object boundary to find ``joins'' that break an object into subparts [CB85a]. I have made use of a far less sophisticated technique for identifying joins: subparts are defined as being convex, and the junction between two subparts is therefore delimited by a ``waist'' - the narrowest extent between concavities. A canonical description of two dimensional shape is provided by the smallest possible number of convex subparts.

The relationships between these subparts can be described with respect to axes. I define the ``major axis'' of a shape as the line along which it extends furthest, and the ``minor axis'' as that along which it is narrowest. These axes are used to describe relative position of subparts, and are also used as size references. When an overall shape is divided into convex subparts, these are also defined and oriented by their axes. The convex subparts are described as collections of shape features, all of which are related in terms of their own axes' orientation with respect to the major and minor axes of the subpart.

This description of subparts and shape features in terms of the relative positions of their axes I describe as ``Axially Specified Subparts and Features''. For convenience, I will refer to the general method by the initials ASSF.


next up previous contents
Next: A Two Dimensional Derivative Up: 2D Qualitative Geometry from Previous: 2D Qualitative Geometry from
Alan Blackwell
2000-11-17