|In the above hypothetical
situation we have provided one definition of nice viewpoint,
however nice viewpoint is more general then this and is in fact
a whole family of problems. Nice viewpoints in fact arise in many
situation in which three dimensional data must be displayed on
a two dimensional medium.
Therefore by a nice viewpoint we mean a projection
of a set of lines or points, in three dimensions, such that all (or
most) of the features of the set, relevant for some task, are clearly
In this paper we will restrict ourselves to just looking
at nice viewpoints of polyhedra in space which is of interests in the
fields of computer graphics, and computer vision.
Problem and Formulation Of Solution
Formulation of Solution
|We wish to find a projection in which
the general appearance of the object is preserved. By "general" we mean
that the 3-D information of the object is maximized in it's 2-D projection.
First we note that degeneracies remove information and secondly
that the degeneracies come in only two flavors:
The above mentioned degeneracies happen in only two instances. When
the projection direction is parallel to:
- a line is reduced to a point or
- 2 or more lines are reduced to a line
So if we want to get a nice viewpoint then we have to find a projection
in which none of the above things happen, that is the projection direction
is not parallel to a line or plane. It should be noted that if we stay
away from the second problem then we also stay away from the first.
- a line or
- a plane containing 2 or more lines
Definition of Solution
|We noted in the previous section that we get degeneracies
if the projection direction is parallel to any plane containing two or
more lines. Now we know that if a vector is parallel to a plane then the
dot product of the normal of the plane and the vector is zero. We also
know that as we move toward the normal the dot product between the normal
and a vector increases until it hits it's maximum when the vector and normal
are parallel. So if we generate a set of planes from the lines of our
polyhedron and then look for a direction that is the closest to all normals
then we have our projection direction. Let's define our solution now.
L : the set of lines
of the object
T : the set of unit normal vectors
of the planes containing two or more elements of L
We evaluate a given projection direction, p, by looking at
all normals, t,in T and assigning the evaluation
function G(p) the smallest dot product of p with
t since the dot product is the smallest when for the
normal that is the farthest from p.
G(p) = mint e T(|p.t|)
Now we look to evaluate this evaluation function over all possible
p , looking for the p, that produces the largest
max|p| = 1G(p)
The above formulation leads directly to an algorithm.
Straight Forward Algorithm
|The idea is to find the smallest diameter circle that encloses
every t or -t of T. This leads directly to two cases.
Case 1: the circle is defined by two normals.
The two normals lie on a diameter of the circle so...
|t1.p| = |t2.p|
p = t1 + t2
/ |t1 + t2|
but because the normals in T can have two directions we also
p' = t1 - t2
/ |t1 - t2|
So what we do then is create a p and a p'
for every pair of normals in T and then evaluate each projection
direction keeping only those that have G(p) = |t1
.p| = |t2.p| (that is keeping only those p for
which all t in T are inside the circle defined
by t 1and t2). This section of
the algorithm can be easily seen to be O(n6) since
there are O(n 2) normals and therefore
O(n4 ) pairs of normals and thus O(n4)
projection directions which need to be checked against O(n2
) normals, where n is the number of edges.
Case 2: the circle is defined by at least three
In this because the normals in T have two directions we get
four different projection directions (while in Case 1 we had only
p = center(t1
p' = center(-t1,t2
p'' = center(t1,-t 2
p''' = center(t1,t 2
center(x,y,z) = (x-y) X (x-z) / |(x-y)
We evaluate these p as previously only keeping
those that have G(p) = |t1.p| = |t2
.p| = |t3.p|. This section of the algorithm can
be easily seen to be O(n8) since there are O(n
2) normals and therefore O(n6) triples of
normals and thus O(n 6) projection directions
which need to be checked against O(n 2) normals where
n is the number of edges.
Now that we have generated all possible projection directions and tested
them to see if they contain all normals (the smallest circle around
them that is), now we just look at all projection directions, at the values
of their evaluation functions, and choose the projection direction with
largest evaluation function value, G(p). and we are done.
See it happening in this Java applet
|In conclusion we should note that the above algorithm is pretty
slow, in fact, as we noted, it is O(n8) in the number of
edges. Faster algorithms do exist. One faster algorithm is given in the paper
by Kamada and Kawai and it is O(n6log n). An even faster
algorithm is given in Bose, Gomez, et al. that is O(n
- G. Toussaint, "The complexity of
computing nice viewpoints of objects in space", Keynote Address, Vision
Geometry IX, Proc. SPIE International Symposium on Optical Science
and Technology , 30 July to 4 August 2000, San Diego, California.
- P, Bose, M. F. Gomez, P. Ramos and
G. Tossaint, "Drawing nice projections of objects in space",
Proc. Graph Drawing'95, pp.52-63, Germany,
- T. Kamada, and S. Kawai, "A simple
method for computing general position in displaying three-dimensional
objects," Computer Vision, Graphics and
Image Processing 41, pp. 43-56,