Subsections

Projection with distinct x-coordinates

Definition: A camera C, such that all pi have distinct x-coordinates in the image.

We can check for this condition with this simple algorithm (see also figure 6):

\framebox[6.0in]{
\begin{minipage}[h]{5.0in}
\par
For each point $p_i$\par
~~~~...
...\textcolor{Red}{O($n~log~n$)}\\
\par
Check for duplicates
\par
\end{minipage} }

Figure 6: Projection of pi on the x-axis.
\includegraphics[width=2.5in]{img/x-axis-proj}

Existence of such a projection

Let's consider each pair of vertices Pi, Pj, j $ \not=$i of the polyhedron. There are exactly n2 such pairs. The projection center and each of those pairs of points i and j (assuming no-three-point co-linearities) yield n2 planes in space intersecting the projection plane in a certain line lij. A forbidden projection J is one such that at least one line lij is parallel to the Y-axis of the image plane. Rotating the projection plane (changing R of the camera model) around the projection axis, each of those line becomes parallel to the Y-axis one after another. But since there are O(n2) forbidden positions and that each line have measure zero in space, there exists an infinite number of valid projection.

Figure 7: Construction of all possible lines from the projection of all the points. Rotating the camera around its Z-axis will yield one line at a time parallel to its Y-axis in the projection.
\includegraphics[width=4.5in]{img/proof_0}

up to this point, we have considered fixed projections, with a fixed projection center rotating around the projection axis. In [1], proof is presented using intersecting planes. Then we consider a forbidden projection center c such that the projection of the points on the projection plane from c yields at least one non-distinct x-coordinates. We know that each pair of points (no two points with same y-coordinates) can define a plane that intersects the projection plane in a line parallel to the Y-axis of the image. This construction is possible by intersecting the line PiPj with the projection plane yielding a point pij. Using any other point tij with the same x-coordinate as pij, you build the plane PiPjtij, (see figure 8). Each of these planes defines forbidden projection points in space. Nevertheless, each plane has measure zero in space and we conclude once again that there is an infinite number of allowed projection.

Notice that proving this theorem is quite easy and there are many ways to do it. The interesting part is that every proof gives almost all the ingredient for computing a valid projection. In the next section, we will use that last proof.

Figure 8: Constructing a plane in space of all forbidden projection center for two points
\includegraphics[width=4.5in]{img/plane}

Simple algorithm for computing a valid projection center

This is the algorithm presented in [1], modified to be compatible with the notation used here. Let's assume the point Pi and the projection J0 with projection center c0. Project each Pi using J0. Check if all pi have distinct x-coordinates. This task is achieved in O(n log n) by sorting pi relative to their x-coordinates, and then check for duplicates in the list. If all pi have distinct x-coordinates, we are done. If not, then we know that at least two points have the same x-coordinates. Let's define c1 the closest forbidden projection center such that c1, z < c0, z (getting further away from the Pi). Projecting from c1, there are at least two points pij and pij + 1 whose x-coordinates are equal. Moving the projection center from c0 to c1 is a continuous linear transformation in the projection plane. Thus, the points pij and pij + 1 were already consecutive in the first sorted list of points. Therefore, we only need to consider each pair of consecutive points in the sorted list of points, as possible pair of points defining c1 (figure 9). To find c1, we consider each one of those pair of points Pi, and build the plane parallel to the Y-axis passing through those points (figure 8). Then we intersect each one of those plane with the Z-axis. This is done in O(n). c1 is the closest intersection to c0, so any point on the open line segment $ \overline{c_0c_1}$ is allowed. Overall, this is a O(n log n) algorithm. This is better than considering every pair of point, which is O(n2).

Figure 9: We only need to consider consecutive pairs in the sorted list of points
\includegraphics[width=2.5in]{img/x-axis-proj2}
.

% latex2html id marker 1057
\framebox[6.0in]{
\begin{minipage}[h]{5.0in}
\par
...
... $c_0$\par
Open line segment $\overline{c_0c_1}$\ is valid
\par
\end{minipage} }

Greg ALOUPIS 2003-12-22