Next: Envisionment of Motion through Up: A Program for Reasoning Previous: Representing Contact State

## Contact State Transitions

All possible sliding motions involve changes of state between the above categories of contact, and this is represented by corresponding changes in the contact list for the moving object, and in those of the obstacles. The change in state which occurs after any given sliding motion depends on the shape of the features involved, and on the direction of the slide.

The shape of features which are neighbours to the current contact site is static information which can be obtained directly from the qualitative scene description. The direction of sliding motion is dynamic information, which must be determined for each change of state. Direction of sliding is conveniently described for a single moving object as being either clockwise or anticlockwise with respect to the boundary of the moving object (for multiple moving objects, direction would have to be stated relative to one of them).

The distinction between the clockwise and anticlockwise sliding directions in motion description must be supported by an annotation of shape description that establishes which neighbours of a feature lie in a clockwise or anticlockwise direction (this can be stated independently relative to the boundary of each object). If this were not done, the reasoning program would not be able to determine the ``handedness'' of the object descriptions, and would not be able to distinguish between mirror copies of objects.

A substantial amount of effort in the implementation of this sliding analysis program involved providing functions for accessing the shape representation in terms of the two directions, and describing both contacts and object boundaries in these terms. A typical problem in doing this was that the list of features which comprised a subpart or object was described as a simple list, whereas the clockwise ordering of neighbouring features had to be circular. The necessity for use of circular lists is mentioned again briefly in the discussion of implementation.

Having established the present state, the neighbouring features to the current contact position, and the direction in which motion toward the neighbouring features is taking place, it is possible to identify the next qualitative change in contact state that will occur.

The list of possible state transitions is much less than the square of the number of states, because very few states can possibly follow each unique contact type in a physically possible object description. In particular, any contact between non-vertex combinations must be followed by a contact that involves vertices. Possible transitions can be categorised in terms of their behaviour around vertices. The program described here distinguishes between three important types of sliding state around a vertex. I describe these as ``aligned'' contact, ``sliding over'' a vertex, and ``falling off'' a vertex.

• All contact states can be classified as either aligned or non-aligned. Aligned contacts are states in which any motion at all will alter the state, because there are vertices in contact with other vertices. There will always be an aligned contact state in between two non-aligned states, except when concave and convex combinations of features are in contact. At this point, the moving object is about to start (or has just finished) sliding over a vertex. These aligned states therefore mark a transition between sliding over edges, and sliding over vertices.
• It is only possible to slide-over convex vertices. Concave vertices require either that the moving object rotate, or that the aligned vertex on the moving object continue to slide with a vertex to edge contact over the following edge. There is therefore a second kind of motion that can occur around an aligned state: a combination of slide-to, and slide-from.
• If a line segment or curve is sliding over a convex vertex, and there is another convex vertex at the end of the moving segment, it is possible for the moving object to fall-off the obstacle that it is sliding around. The actual behaviour will depend on the free space motion characteristics of the scene space (in particular whether there is any gravity, or similar field). Possible behaviours which satisfy the sliding constraint are that the moving object rotates about the fall-off point, or slides-from the aligned vertex.

There are therefore three basic types of aligned to non-aligned transition: the slide-over motion, the slide-to/slide-from motion, and the fall-off motion. These transition categories, when expanded to included the relevant cases from the list of possible contact states, can describe the motion of a single moving object over the boundary of a single obstacle, but they must be extended to describe an object moving around a number of obstacles. This extension is not too complex, because two obstacles in contact (or even near each other) form a new feature that behaves like one of the normal features. The extensions that would be necessary identify the equivalent feature, and allow the concept of ``neighbouring'' features to include features on other objects which are candidates for the next contact.

Transitions between contacts with features on different objects are therefore of the same types as transitions between features on the same object. The main distinction is between the cases of sliding over an aligned boundary between objects, and an overlapping boundary. The simplest case is the aligned boundary, in which there is an intermediate state where the moving object is in contact with both objects.

There are several cases of overlapping obstacle contacts: there are two directions from which to approach an overlap - from the high side, the moving object will ``fall off'' onto the second obstacle. From the low side, the moving object will come into contact with the hanging part of the overlap. In either case, the behaviour also depends on the curvature of neighbouring shape features.

The level of analysis presented so far does not deal with one important case: contact between a concave and convex curve, or even between the areas surrounding a concave and convex vertex. If the angles of the curves or vertices include right angles, or if one is acute and the other obtuse, the resulting contact states can be determined. If both are acute or both obtuse, it is impossible to determine the contact that will occur, because the relative sizes of the angles are unknown.

A second case which is difficult to analyse is sliding across the gap between two obstacles which are not touching each other. This would require direct comparison between the size of the gap between the obstacles, and the size of the moving object. The other state transitions I have described can all be qualitatively analysed without size or angle magnitude comparison, and it was this case which made clear the deficiencies of the ASSF representation with respect to direct comparison of feature sizes. This is discussed further with other implementation issues.

Next: Envisionment of Motion through Up: A Program for Reasoning Previous: Representing Contact State
Alan Blackwell
2000-11-17