I'm writing a little software rasteriser which lets you apply an arbitrary transformation to a 2D image. This includes both translation, rotation, scaling and shearing (the affine transformations) as well as full perspective mapping.
There are a few tricks to do quick affine transformations which I won't go into here; they're pretty easy to find, online and in books. Essentially, you exploit the fact that opposite sides are parallel in the quadrilateral (or quad) that defines the boundaries of the transformed image.
What is harder to find is dealing with perspective mapping; at least, in a 2D context.
The mathematics of perspective
A perspective-mapped rectangle has one or two vanishing points; the point at which opposite sides of the rectangle meet. Objects which are regularly spaced apart will appear closer together the further away they are, such as the sleepers on a railway track:
The further back you go, the smaller everything gets. More specifically, the apparent size of an object is inversely proportional to its distance, reaching its limit at the vanishing point where everything is infinitely small. Obviously we can't just linearly interpolate between the corners of our quad, like we can with an affine transformation; we need to include the depth information in our calculation. The interpolation equation (shamelessly lifted from Wikipedia) :
where with endpoints specified by and .
Extruding flatland at an angle
So that's great, but how exactly do you get that depth variable from a 2D quad? Consider the above equation. When it is equivalent to linear interpolation. We know that the vanishing point is asymptotic and that the apparent size is inversely proportional to distance (or depth) - the latter is accounted for in the interpolation equation, so we need only select appropriate reference points.
Setting to represent the vanishing point will give us an asymptote via division by zero. Setting will leave the point on the quad furthest from the vanishing point unchanged; now all we need is to find the depth of the point closer to the vanishing point where .
Cross products and angry merchandise
We can find out if there is a vanishing point by using the vector cross-product. If you're familiar with the vector cross-product, feel free to skip a few paragraphs. Otherwise, here is its definition:
This calculates the vector perpendicular to both and in three dimensional space. You will note that, in two dimensions, the z component is always zero, leaving us with the simplified equation
which means it is also the magnitude of that vector. It can be considered a measure of 'perpendicularness', as is apparent when taking the cross-product of the unit vectors: and .
Diversion over. Take the vectors of two opposite sides of our perspective-mapping quad:
where is the vector from the origin to points A and D, respectively. If the cross-product then the lines are parallel and there is no vanishing point; otherwise we may find the intersection by calculating the point at which the two line equations are equal:
Cross both sides by :
Making use of the cross-product identity .
Now we have our value for we may substitute it into the first line equation to find our intersection point, aka. the vanishing point:
Note that if is negative then the intersection lies in the direction opposite , making B the farthest point from the vanishing point and therefore the nearest point to us.
The depth equation
Now we may calculate the depth of the farthest point by linearly interpolating between the nearest point to us (A or B as found in the last paragraph; referred to in the equations as ) and our vanishing point , and applying our depth formula. Remember that .
Tying it all together
With two-point perspective, the depth is the same along each parallel edge, with the longest at and the other . However, three-point perspective places each corner at a different depth. We calculate the depth of the two points on the same line as the nearest point, and then calculate the final point's depth as the product of the two adjacent to it. (Two-point perspective is a special case of this method - can you see why?)
Luckily for us, depth along these lines is a linear function - so we now have everything we need to map perspective. First, find the line upon which our u, v coordinates lie by interpolating by on opposite sides of the quad.
Now we can calculate u, v by interpolating along the line between those two points.
This just leaves one part left: how do we use these coordinates to render our image? And how do we actually render the image efficiently? This will be revealed in the next part coming soon...