Now let's take a look at Sugihara's famous assumptions on line drawing interpretation problems:

1.  Assumptions on Objects:

Assumption O1:  Polyhedrons are bounded and homogeneously three-dimentional.

With this assumption we avoid unusual polyhedrons. For instance, Since the polyhedrons are bounded, infinite objects such as a half space are excluded. Since they are homogeneously three-dimensional, lower-dimensional objects such as a sheet of paper are also excluded.

Assumption O2:  Polyhedrons are topologically equivalent to a ball

Assumption O3:  Polyhedrons are convex.

Assumption O4:  Polyhedrons are trihedral.

A vertex is called trihedral if it is on exactly three faces.
A polyhedron is called trihedral if all the vertices are trihedral.

Assumption O5:  Polyhedrons are rectangular.

A vertex is called rectangular if all the faces meeting at the vertex are mutually perpendicular.
A polyhedron is called rectangular if all the vertices are rectangular.

Note that O5 does not imply O4. The following figure is an example that is rectangular but not trihedral, six faces meet at the central vertex.

Figure:  Polyhedron that is rectangular but not trihedral.

2.  Assumptions on Points of View:

Assumption W1:  No face of a polyhedron is coplanar with the view point.

It implies that every face of a polyhedron corresponds to some region of the picture with nonzero area.

Assumption W2:  No pair of edges of a polyhedron is coplanar with the view point unless the two edges are collinear in the space.

It implies that neither distance edges accidentally overlap in the picture nor noncollinear edges become collinear in the picture.

Assumption W3:  No pair of a vertex and an edge of a polyhedron is coplanar with the view point unless the vertex is one of the two terminal points of the edge.

It implies that a vertex does not lie on an edge in the picture unless the vertex is originally a terminal point of the edge.

Assumption W4:  No pair of vertices of a polyhedron is collinear with the view point.

It implies that two distince vertices never fall at the same point on the picture plane.

Figure:  An object, the view point, and the picture.

Note the assumption W2 implies W1, and W3 implies both W2 and W4(hence, W1 too). These types of assumptions are often called nonaccidentalness assumption. So for that Truncated Pyramid Question we mentioned in the introduction part, the situation showed in Figure 1(c) violates assumptions W1, W2, W3, and W4; consequently, if we choose at least one of these four assumptions, we can avoid the tricky answer.

3.  Assumptions on Drawing Rules:

• Assumption D1:  Edges only are drawn in line drawings.

Even if the object surface has texture, scribbles, cracks, or shadows, they are not drawn.

• Assumption D2:  Visible edges only are drawn.
• Assumption D3:  Visible edges are drawn with solid lines, and invisible edges are drawn with broken lines.
 
Assumption D2 is useful for image analysis, and D3 for engineering drawings.

• Assumption D4:  All edges, visible and invisible, are drawn with solid lines.

This assumption seems less realistic, but more fundamental for study of the mathematical structure of line drawings.

We have listed many assumptions which are necessary and useful to make the realizability problem senseful. Usually only some subset of these assumption set are adopted. Different subsets define different problems. In this project, the following type of realizability problems are considered:

1.  Problem with Assumption(PA)

Definition:  given a line drawings and a set of assumptions, judge whether a polyhedron is realizable from the line drawings.


2.  Problem with the View point(PV)

 
Definition:  given a line drawings and the view point, judge whether a polyhedron is realizable from the line drawings with respect to the view point.


3.  Problem with additional Knowledge(PK)
 

Definition:  given a line drawing and some additional knowledge about the structure of a polyhedron, judge whether a polyhedron with the given structure is realizable from the line drawing.

What's additional knowledge ? A typical knowledge of such knowledge is given by labels assigned to lines, as will be seen in the page Labeling Algorithm. A problem in which additional knowledge about the structure of the object is not given is usually decomposed into a set of subproblems of the type PK.


4.  Problem requiring Flexibility(PF)
 

Definition: given a line drawing, judge whether it can be regarded(in some practical sense) as a picture of a polyhedron.
This problem arised from whether the realizability is judge strictly or flexibly. As we have seen, the line drawing in that Truncated Pyramid Question is not a correct projection of a truncated pyramid. This kind of incorrectness, however, usually arises in practical data: digitization errors are inevitable when picture data are given to a computer. So, the realizability should be judged "flexibly" in the sense that pictures are regarded as being "practically correct" if incorrectness is only dut to small errors in vertex positions.

In this way we shall distinguish the problem types by thr symbols PA, PV, PK, and PF. We shall use the symbols also in combination. For example, PAV stands for the type of a problem in which a set of assumptions and the view point are given. PAVK stands for the type of a problem in which a set of assumptions, the view point, and additional knowledge about the structure of the object are given, etc. Obviously a problem of the type PAK is a subproblem of the corresponding problem of the type PA. Here we are going to talk about a method for decomposing a type-PA problem into type-PAK subproblems. The method is just the famous Labeling Algorithm.