next up previous contents
Next: Summary of Sliding Issues Up: The ASSF Implementation Previous: The ASSF Implementation

Scene and Problem Representation

When establishing possible sliding motion, the most important information about the scene is the description of what features or objects are in contact with other features or objects. These contacts were represented using ``contact lists''. Whenever one shape feature comes into contact with another, a contact list is created for each feature. The contact list is linked to the feature by the name of that feature at the head of the list. The rest of the list consists of all features which are in contact with the feature at the head. Any further contacts that occur can be added to this list.

The contact lists are ordered in a clockwise direction (relative to the object on which the head feature is found). This implicit direction in the contact list ordering is used as the basis for distinguishing between clockwise and anticlockwise sliding, since the system must be able to tell what relative direction successive slides occur in.

All contacts between objects in a scene are collected in the ``contact set'', which is the set of all contact lists. The contact set contains two entries for every contact; one entry is found on the contact list of each of the two features in contact. It is necessary to maintain consistency in the contact set by removing entries from the relevant contact lists when a contact is broken, and removing whole lists when the feature the list refers to is no longer in contact with anything.

For ease in formulating the problem, one object in a scene is represented directly as the moving-object, while all others are called obstacle-1, obstacle-2 etc. The analysis of sliding therefore commences with the contact lists for each feature of moving-object.

In order to represent motion around the boundary of a single obstacle, the features on the boundary must be ordered. This is also achieved by using an implicit clockwise ordering in the list of features that are in a given subpart or object. Use of a linear list for this purpose created some problems, in that the clockwise ordering of features on the boundary is circular. It is possible to create circular lists in LISP, but they are difficult to operate on - the reasoning system therefore had to allow for a ``wrap-around'' from the last item in a list of features to the first, and vice-versa in the anticlockwise direction.

Although size comparison between features on different objects would have been useful, this system was not able to easily perform such comparison. This resulted from the fact that feature sizes are expressed by the relationship between the length of the feature axis, and the length of the main object or subpart axis. The relative sizes of whole objects were expressed in a similar fashion. Comparison of two features therefore required following a chain of qualitative size comparisons through two objects - by the end of the chain, it was seldom possible to make any clear conclusion of size relative to the feature at the start of the chain.

As described above, the sliding system searches exhaustively for all possible contact states. This exhaustive search terminates when a previous contact state is repeated (when the moving object has circumnavigated all obstacles). Detection of a repeated contact state is not trivial, because there is no canonical ordering of the contact set (even though all contact lists and object feature lists are guaranteed to be clockwise-ordered, they can start and end at different points). It was therefore necessary to construct a function for comparing overall scene configurations after each sliding motion.

next up previous contents
Next: Summary of Sliding Issues Up: The ASSF Implementation Previous: The ASSF Implementation
Alan Blackwell