Definition: A camera C, such that all p_{i} have distinct xcoordinates in the image.
We can check for this condition with this simple algorithm (see also figure 6):
Let's consider each pair of vertices P_{i}, P_{j}, j i of the polyhedron. There are exactly n^{2} such pairs. The projection center and each of those pairs of points i and j (assuming nothreepoint colinearities) yield n^{2} 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 Yaxis 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 Yaxis one after another. But since there are O(n^{2}) forbidden positions and that each line have measure zero in space, there exists an infinite number of valid 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 nondistinct xcoordinates. We know that each pair of points (no two points with same ycoordinates) can define a plane that intersects the projection plane in a line parallel to the Yaxis of the image. This construction is possible by intersecting the line P_{i}P_{j} with the projection plane yielding a point p_{ij}. Using any other point t_{ij} with the same xcoordinate as p_{ij}, you build the plane P_{i}P_{j}t_{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.
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_{0} with projection center c_{0}. Project each P_{i} using J_{0}. Check if all p_{i} have distinct xcoordinates. This task is achieved in O(n log n) by sorting p_{i} relative to their xcoordinates, and then check for duplicates in the list. If all p_{i} have distinct xcoordinates, we are done. If not, then we know that at least two points have the same xcoordinates. Let's define c_{1} the closest forbidden projection center such that c_{1, z} < c_{0, z} (getting further away from the P_{i}). Projecting from c_{1}, there are at least two points p_{ij} and p_{ij + 1} whose xcoordinates are equal. Moving the projection center from c_{0} to c_{1} 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_{1} (figure 9). To find c_{1}, we consider each one of those pair of points P_{i}, and build the plane parallel to the Yaxis passing through those points (figure 8). Then we intersect each one of those plane with the Zaxis. This is done in O(n). c_{1} is the closest intersection to c_{0}, so any point on the open line segment is allowed. Overall, this is a O(n log n) algorithm. This is better than considering every pair of point, which is O(n^{2}).
Greg ALOUPIS 20031222