Introduction

Computing a perspective projection of a 3-D model is getting its 2-D image on a particular plane by projecting each vertex of the model on that plane in the direction of the projection center. The most obvious example of such a projection is taking a picture of our surrounding world with a camera. It is almost trivial that such a projection removes a lot of information about the particular object. Naturally, inference over an image is sometimes possible, but there is always ambiguity even though a lot of information about the model is previously known. For instance, can you tell which face of the cube in figure 1 is nearest?

A question arises from that observation: what kind of projection maximizes the information we can get from a single image? Instead of answering that question, I will actually give examples of projection where a lot of information is lost. Consider the square in figure 2. Of course, it is impossible to tell if it is a square in space or a cube. If it is the latter, then we call this projection degenerate.

A degenerate projection is a very generic term that defines certain projection that have a configuration of points or lines we would like to avoid. In this project, we face the problem of projection with distinct x-coordinates and non-parallel line in the projection. Gomez et al [1] have presented algorithms to compute projections without those degeneracies. They achieve O(n log n). At the end of this tutorial, it should be obvious that avoiding degeneracies (especially the one treated here) put us closer to ``computing projections that maximize the information'', which is still an opened problem.

In this tutorial, we will use a very different approach to [1]. We will show how the algorithms work in the case of a pin-hole camera, the most popular camera model in computer vision [2]. Also, this formulation is closer to the implementation of the algorithm.

Greg ALOUPIS 2003-12-22