Plato --The Republic, Book VII, 427-347 BC
"Plato seems to have foreseen, on the basis of what
must have been very
sparse evidence indeed at that time, that: on the
one hand, mathematics
must be studied and understood for its own sake, and
one must not demand
completely accurate applicability to the objects of
physical experience; on the
other hand, the workings of the actual external world
can ultimately be
understood only in terms of precise mathematics".
Roger Perrose --The Emperor's New Mind, Chapter 5, 1991 [74].
Telling whether a given line drawing correctly represents the projection
of a plane-faced polyhedron in 3D-space is a long-standing challenge for
Artificial Intelligence and Robotics. The availability of an efficient
algorithm achieving this task would have important applications in projective
geometry, image understanding, monocular vision, automatic 3D reconstruction
and modelling of real environments.
The aim of this project is to find
out a necessary and sufficient condition for realizability.
First Look
A polyhedron is a solid object bounded
by a finite number of planar faces. It is not necessarily convex; it may
be concave or even have holes.
A line drawing is
made of straight line segments and junctions --points where two or more
of the segments meet. A line drawing is said to be realizable
or
correct
if
it is the orthographic or perspective projection of some 3-dimensional
scene of polyhedral objects, and non-realizable orincorrect
otherwise.
Such a scene is known as a spatial realization
or interpretation of the drawing.
Here there are some examples of correct drawings:
Truncated Pyramid Question
The most naive type of the realization problem is the following:
Naive Problem: Given a line drawing, judge whether a polyhedron is realizable from the line drawing.
Why do we say this question is naive ? Because without some constraints, it's impossible to answer whether a polyhedron is realizable from a line drawing. For example, let's look at that classical Truncated Pyramid Question, we will mention it many times in this project. The question is: consider a line drawing shown in the following figure(a):
One may say yes, because it can usually be regarded as an illustration
of a truncated pyramid seen from above. In a mathematical sense, however,
it cannot be a picture of any truncated pyramid. Because the three side
faces of a truncated pyramid should have a common point of intersection
in a space(when extended), and hence the three lines corresponding to the
pairwise intersections of the three faces should meet at a common point
on the picture plane, but obviously they do not as shown in (b). So it
seems that one should answer that a polyhedron is not realizable from such
line drawing. We can, however, object to this answer. Indeed that line
drawing cannot be a picture of any truncated pyramid, but can be a picture
of other kind of polyhedrons. The object shown in (c) is an example of
a polyhedron that can yield the line drawing in (a). So it seems that one
should answer yes again !
From this example, we see how tricky that object and situation are
! Thus, it's nonsense to discuss whether a polyhedron is realizable from
a line drawing without any constraints. For this sake, Sugihara introduced
a list of assumptions on objects, on view points, on drawing rules, etc.
So, let's move on to the assumptions......