Computing Nice Views of Objects in Space

by James Waterhouse  

presented to Prof. Godfried T. Toussaint 
308-507A - Computational Geometry -- Web Project  
Fall 2000 
McGill University




Let's say you have met a person from a foreign country and you want to tell them what the english words are for different three dimensional objects. Well one way you might do this is by sending them word-picture pairs. The problem is what is the best way to take a picture such that your friend has the  greatest chance of knowing what the object is when they see it. This can be seen as trying to maximize the three dimensional information contained in the image through varying the viewpoint. For example, if you wanted to give them the pair for cube then what would be the best viewpoint to take the picture from? If you took a picture above the center of a face then you would get an image of a square. Fig 1. From such a picture your friend might conclude that "cube" means square. On the other hand he may not know what it means if he knows this picture is supposed to represent a three dimensional object. Why might it be ambiguous? Well the square might be a face of a cube or the bottom of a pyramid or any other object where the rest of the object can be hidden behind a square face. So what we want then is to get a nice viewpoint, a projection of the cube such that the information is maximized  so the image is as unambiguous as can be. One such nice viewpoint is given in Fig 2. degenerate viewpoint of cube  
Fig. 1 - Degenerate viewpoint of  a cube  
nice viewpoint of cube  
Fig. 2 - Nice viewpoint of a cube
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 visible. 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:
  • a line is reduced to a point or
  • 2 or more lines are reduced to a line
The above mentioned degeneracies happen in only two instances. When the projection direction is parallel to:
  • a line or
  • a plane containing 2 or more lines
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.

Definition of Solution


Evaluation Function

Maximin Formulation

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

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

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 have,

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

In this because the normals in T have two directions we get four different projection directions (while in Case 1 we had only two).

p = center(t1 ,t2,t3)
p' = center(-t1,t2 ,t3)
p'' = center(t1,-t 2 ,t3)
p''' = center(t1,t 2 ,-t3)


center(x,y,z) = (x-y) X (x-z) / |(x-y) X (x-z)|

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

Related Material


  1. 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.
  2. 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, 1995.
  3. 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, 1988.  
Geometry Links