Introduction
Fig. 1 - Degenerate viewpoint of a cube
Fig. 2 - Nice viewpoint of a cube
Problem and Formulation Of Solution
| Problem 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:
|
|
|
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|
Therefore,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) where 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 . |
|
Conclusion
|
|
| 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
|
|
|
|