Make your own free website on

"We all live in the great, dynamic web of change. It links
us to one another and, in some ways, to everything in the
past. And in the way that each of us influences the course
of events, it also links us to the future we are all busy
making, every second".

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.

With the aboved assumptions, Huffman proved that only twelve types of labeling can appear in line drawings of polyhedrons. They are listed in the following figure:

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 ......

AssumptionsHomePerpendicularity Condition