*James Burke ---The Pinball Effect. How Renaissance*
*Water Gardens Made The Carburetor Possible, 1996 [14].*

In the progress of line drawing interpretation, a very interesting algorithm
was developed by Huffman, which is called
Labeling
Scheme. This algorithm is used to solve the type-PA problems with
assumptions O1, O4, W3, D1, and D2, that is, a realizability problem of
a hidden-line-eliminated line drawing in the trihedral object world with
the nonaccidentalness assumption. So we know that each line in the picture
corresponds to exactly one edge of the object. The algorithm classifies
the lines into three categories and assigns different labels to them.

First, we define two types of edges:

The meaning of concave and convex are quite obviously here, an edge is convex(concave) if it can be spatially interpreted as a convex(concave) edge between two spatial faces. Then we classify each edge into one of the following three categories.

- Category One: the line corresponding to a convex edge whose both sides are visible. Label it with "+"
- Category Two: the line corresponding to a concave edge. Label it with "--"
- Category Three: the line corresponding to a convex edge one of whose side faces is hedden by the other. Label it with an arrow "-->", the direction of the arrow is chosen so that the visible side face is to the right of the arrow.

Figure: List of possible vertices in the trihedral object world

All other labelings are impossible. With this labeling scheme, we can quickly find that in the following figure:

The labeling in (a) corresponds to the interpretation of the picture as a triangular pyramid, and that in (b) as a truncated pyramid. This algorithm is quite simple and the number of possible cases is also rather small, only twelve. All the line drawings of those possible polyhedrons under those assumptions (O1, O4, W3, D1, and D2) must correspond to one of the twelve labelings. How well it would be if any one of the twelve labelings also must corresponds to a correct polyhedron ! However, regretly the answer is NO. We can easily find an picture which has a consistent way of labeling, but it does not correspond to any polyhedron. For example:

Thus, for a picture to admit a consistent labeling
is only a necessary, but not sufficient, condition for the picture to represent
a polyhedron correctly. A labeling that is consistent with those
twelve cases gives merely a candidate for the spatial structure of the
object. Let's go forward toward our goal ......