This is the beta 2 version of a document describing the algorithm used by many 3d engines around like the Nintendo 64, Quake and Quake 2, voodoo and voodoo2 chipsets and many more (playstation does NOT use this algorithm!!!!! agrrr) for mapping a texture onto a polygon .

    First, what is interpolation?:

        In general, any function that consists of a first degree polynomial is a linear function. The following are examples of linear functions:

        z = 3x + 6y
        t = 23x + 3y - 102z
        w = 24x - y - z + 2t

and the these are not linear functions:

        z = 3x^2 + 6y^3
        t = 4x^2 + 4y - 10z

(a^b means a to the b power).

Let's consider a function of the form:
 
        z = Ax + By

The representation of this function is a plane. In other words, the subset of coordinates that make this equation true is called a plane. Imagine that x and y are in fact screen coordinates and let's rename them (but z is not the z cartesian coordinate!).

        z = AX + BY

When we scanconvert a polygon, we move along a line in the screen. For every (X,Y) pair, we obtain a z and thus, we have a line in 3d that lies on the plane represented by the equation above. Notice that the important thing here is that IT IS A LINE. Remember the equation of a line?? :)

        (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) = (z - z1) / (z2 -z1)

where (x1,y1,z1) and (x2,y2,z2) are two points of the line and (x,y,z) are ALL the points of the line. Solving for z gives:

        z = z1 + ( (z2 - z1) / (y2 - y1) ) * (y - y1)

And now let's get rid of that product...

        zn = z1 + m(yn - y1)    where m = (z2 - z1) / (y2 -y1)

        z(n-1) = z1 + m(y(n-1) - y1)

Solving for -my1 gives:

        -my1 = z(n-1) - z1 -my(n-1)

substituting in the first equation...:

        zn = z1 +myn +z(n-1) - z1 -my(n-1)

and finally:

        zn = z(n-1) + m(yn - y(n-1))

but when we scanconvert yn - y(n-1) = 1 et voila:

        zn = z(n-1) + (z2 - z1) / (y2 - y1)
 
In conclusion, given a linear function in screen space, we can use that formula to interpolate its values when we scanconvert a polygon.

(Notice that interpolating 1/z is also usefull for the z-buffer algorithm!).

  ok but, you said that 1/z, u/z and v/z are linear in screen space...?:

    First, let's proof that 1/z is linear:

    We have a polygon in 3d space every point of which has to be a solution for:

        Ax + By +Cz + D = 0

which is the equation of the plane the polygon lies on (however, not every solution of the equation corresponds to a point on the polygon). On the other hand, from the perspective projection we know that:

        X = x * E / z
        Y = y * E / z

where X and Y are the screen coordinates and E is the distance from the eye to the screen. Solving for x and y gives:

        x = Xz / E
        y = Yz / E

Substituting x and y with the formulas from the perspective projection yields:

        (A/E)Xz + (B/E)Yz + Cz + D= 0

and now solving for 1/z gives:

        1/z =  -(A/ED)X -(B/ED)Y -C/D

which is a first degree polynomial! :)

And now, u/z (and applying analogy v/z):

Again, be a polygon in 3D space. The polygon is lying on a texture as you can see in the figure, and the texture is actually a plane determined by 3 points, let's say O, Q and R. Now, consider a point P lying on the poly. If you want to determine P, you could just give its cartesian coordinates x, y and z, but what we are looking for are its components relative to the texture, let's call them u and v (s and t for those OpenGl freaks). Notice that we only need 2 coordinates to determine a point within a plane. This reference system has to unitary vectors: u and v, which are not only unitary but also normal (orthonormal?). We are looking for two scalars such that P = u u + v v. It's easy to see that u (scalar!) is the projection of D over R where D = P - O. This is:
 
        u = R * D / RR     where * represents the scalar or dot product of two vectors.

substituting D:

        u = R * (P - O) / RR

distributing:
 
        u = (R * P - R * O) / RR

using the definition of the dot product and the modulus:

        u = (Rxx + Ryy + Rzz - Rx Ox + Ry Oy + Rz Oz) / RxRx + RyRy + RzRz

or

        u = ax + by + cz + d

where:

        a = Rx / (RxRx + RyRy + RzRz)
        b = Ry / (RxRx + RyRy + RzRz)
        c = Ry / (RxRx + RyRy + RzRz)
        d = (RxOx + RyOy + RzOz) / (RxRx + RyRy + RzRz)

Again, substituting x and y with the formulas from the perspective projection yields:

        u = aXz + bYz + cz + d
 
dividing by z:

        u / z = aX + bY +c + (d / z)

Substituting the 1/z with the formula from the previous calculation:

          u / z = aX + bY + c + d ( -(A/ED)X -(B/ED)Y -C/D)

or

        u / z = X(a - d(A/ED)) + Y(b - d(B/ED)) + c - d(C/D)

which is a first degree polynomial! :)

Written by Marc Salmurri because sharing knowledge makes the world a better place.
email: e6623018@est.fib.upc.es
smail: c/st jaume nº22 1r 4a Sant Cugat del Vallès 08190 Barcelona Spain
(email me if you have any question, suggestion, correction, job (XDDD) or else, don't
hesitate!! :)