Projection with distinct x-coordinates

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

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

Figure 6: Projection of p_i on the x-axis.

Existence of such a projection

Let's consider each pair of vertices P_i, P_j, j $\not=$i of the polyhedron. There are exactly n² such pairs. The projection center and each of those pairs of points i and j (assuming no-three-point co-linearities) yield n² planes in space intersecting the projection plane in a certain line l_ij. A forbidden projection J is one such that at least one line l_ij 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(n²) 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.

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 P_iP_j with the projection plane yielding a point p_ij. Using any other point t_ij with the same x-coordinate as p_ij, you build the plane P_iP_jt_ij, (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

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 P_i and the projection J₀ with projection center c₀. Project each P_i using J₀. Check if all p_i have distinct x-coordinates. This task is achieved in O(n log n) by sorting p_i relative to their x-coordinates, and then check for duplicates in the list. If all p_i 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 c₁ the closest forbidden projection center such that c_{1, z} < c_{0, z} (getting further away from the P_i). Projecting from c₁, there are at least two points p_ij and p_{ij + 1} whose x-coordinates are equal. Moving the projection center from c₀ to c₁ is a continuous linear transformation in the projection plane. Thus, the points p_ij and p_{ij + 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 c₁ (figure 9). To find c₁, we consider each one of those pair of points P_i, 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). c₁ is the closest intersection to c₀, 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(n²).

Figure 9: We only need to consider consecutive pairs in the sorted list of points

.