A computational theory of hidden line perception

The nonuniqueness of perceiving hidden lines from a single line drawing of a solid is illustrated by examples. We assume the solids are trihedral polyhedra without holes and the drawing has been labeled. Our problem is to determine the gradients of the visible and hidden faces as well as to hypothesize the topology of the hidden part. We make the plausible assumption that no hidden face, whose boundary is completely hidden, exists. Under this assumption, we show that the number of possible hidden graphs is finite and is a Catalan number. We then report four search trees for enumerating all possible hidden graphs. The trees, except the first one, are minimal in the sense that no two nodes of the trees represent identical subgraphs. The entropy of a hidden subgraph is then defined. The entropy of an embedding of a hidden subgraph is modeled as the variety of the exterior angles at vertices. This formulation allows both past experience and context to be incorporated in a statistical manner. We then report a minimum-entropy beam search to find nonunique solutions in order of their naturalness. Finally, we propose a surface construction paradigm based on this theory and the shape-from-contour heuristics. © 1988 SPIE.