- Texture Mapping Polygons in Perspective (TM13);Paul Heckbert;4/83.
  this is a troff source file
  It's missing the hand-written equations and pasteup figures

  Computer Graphics Lab
  New York Institute of Technology
  Technical Memo No. 13
  28 April 1983


INTRODUCTION

Mapping textures onto polygons is more difficult for perspective
projections than for parallel ones.  Texture mapping in perspective
requires a division at each pixel in the general case,
while parallel projections require none.
Simple incremental formulas presented here make perspective texture mapping
efficient for the inner loop of a polygon renderer.

We will also discuss the use of a "mipmap" for efficient, approximate
antialiasing of textures.
Use of a mipmap requires the
calculation of a variable "d" which is a measure of the area in the
texture to be filtered.
We will discuss several formulas for "d" which apply to many surface types
(not just polygons).
We show how one of these formulas can be efficiently computed for polygons;
it is currently in use by my POLY program.

Notation:
    
    (x,y) is a point in screen space (frame buffer coords)

    (u,v) is a point in texture space

    d is proportional to the diameter of the area in the
    texture to be filtered

    points are represented by 3 or 4 element column vectors

    points are transformed by matrix multiplication with a
    4x3 or 4x4 transformation matrix on the left


TEXTURE MAPPING POLYGONS IN PERSPECTIVE

When mapping a texture onto a polygon in 3D, you usually specify the
mapping by setting up a correspondence between points in object space
(the space in which the polygon vertices are defined)
and points in texture space.

In my program POLY, this is done by specifying the u and v coordinates
corresponding to each vertex of the polygon.
For simplicity of implementation, the mapping between texture space and
object space is assumed to be affine (to consist of only scales, rotations,
and translations).  You can map a rectangle to a
parallelogram (or vice versa), but you can't map a rectangle to a trapezoid.
Since a 3D affine transformation has six degrees of freedom,
three points can determine it.
This affine texture space to object space transformation
can be written as follows:

The standard formula for mapping object space to screen space is best
expressed with a 4x4 matrix using homogeneous coordinates:
A perspective mapping of texture space to screen space
can be computed by concatenating the two matrices above:
Z is irrelevant, since it is not needed for texture mapping.
Note that we can choose I=1 with no loss of generality.

This transformation maps a rectangle in texture space into a quadrilateral
in screen space.

For synthesized animation, you usually know the object to
screen space transform.  In interactive or motion-tracking applications,
however, you might want to define the texture space to
screen space mapping by giving the screen-space coordinates of the
vertices of a polygon.  Four points define a perspective
texture to screen space transform, since they have eight degrees of freedom,
and the equations above have eight variables.

The transform can be found very simply by setting up the following
equations for each of the four points:

This forms an 8x8 system of equations in the variables A-G [2].
This is the method used by my PWARP program.

For parallel projections,
the eye is infinitely far away, so w' is constant,
and the formulas reduce to an affine transformation:

When texture mapping a polygon, you usually scan it out in screen space
and compute u and v from x and y.  This means we'll need the inverse of
the mappings above.  The inverse mapping has the same form
as the original:

A rectangle in screen space is mapped to a quadrilateral in
texture space.  For parallel projections, the quadrilateral is
a parallelogram.

For a given scan line, y is constant, so most of the terms are constant.
The two numerators and one denominator can be evaluated once at the left
end of the scan segment and computed incrementally in the x loop.
This requires only three additions and two divisions per pixel.

Inner loop of a polygon texture-mapper which samples:

   x = xleft
   unum = t0*x+t1*y+t2
   vnum = t3*x+t4*y+t5
   den  = t6*x+t7*y+t8
   for (; x<=xright; x++) {
      sample the point (unum/den,vnum/den) in texture
      write texture color to (x,y) in screen
      unum += t0
      vnum += t3
      den  += t6
   }

TEXTURE MAPPING WITH MIP

Below is a brief description of mipmaps.

At NYIT, textures are usually in the form of a "mipmap", which is
a frame buffer containing the red, green, and blue components
of a texture or image in the upper right, lower right, and lower left
quadrants, respectively.
Each component is filtered down to 9 different scales,
and the 27 pictures fit nicely into a 512x512 frame buffer.
Mipmaps are currently made by repeatedly halving the size of the picture,
starting with the 512x512 original, averaging 2x2 blocks of pixels
on one level to compute the pixel values on the next level up.
This averaging has the same effect as convolution with a square box filter.

If you stack the maps they form a pyramid.
We'll use the variable "d" to measure height in this pyramid.
Let's label the original 512x512 image with d=1 (even though it is not in
most mipmaps), the 256x256 image with d=2, ..., up to the tiny 1x1 image,
which will have d=512.

To sample a texture using a mipmap, the variable d selects which of the nine
sets of maps is referenced, and (u,v) selects the pixel to be pulled from
that map.  The current implementation actually reads 8 pixels per component
(four from each of two maps) and performs trilinear interpolation among them.
So for the constant cost of 24 pixel reads and 21 (or more) multiplications,
you can approximately filter any square window of the texture.

The standard alternative to "mipmapping" is straightforward filtering
of the texture every time you need a sample.  This can be quite slow,
especially when scaling a texture way down.


We'll assume that most surfaces (whether bicubic, quadric, or whatever)
are approximately planar over the area covered by a pixel.
Under this approximation, a rectangular screen space pixel is mapped into
a quadrilateral in texture space.
We want to filter the quadrilateral to compute the average
texture color for the current pixel.
For most pixels you can further assume
the quadrilateral is nearly a parallelogram.
This is a valid assumption for pixels which are not near a vanishing point
or a singularity of the texture.
(If all pixels map to parallelograms, the surface is planar and
parallel-projected).

The size of the approximating parallelogram
is given by four partial derivatives:
The vertices of the quadrilateral can be found exactly by computing

differences between the u's and v's of adjacent pixels.
The standard mipmap access cannot filter an arbitrary quadrilateral
(or even an arbitrary rectangle).  It can only "properly" filter square areas.
We thus have the problem of choosing a "good" value for d.

With the numbering system described above, d is the side length ("diameter")
of the squares in the original texture to be averaged.
We need to approximate a quadrilateral with a square in order to choose
a value for d.
If our square is too small, the filter will be too sharp, and the mapped
texture jaggy.  If the square is too large, the mapped texture will be
unnecessarily blurry.

Choosing a formula for d is a problem in heuristics and approximation.
Here are some of the formulas for d which I have dreamed up:

find box around
quadrilateral:

box approximating
parallelogram:

find lengths of x and y
direction vectors:

COMPUTING D FOR POLYGON TEXTURE MAPPING

For a polygon in perspective, the four partial derivatives simplify to:

Note that the numerators of the x terms are functions of y only,
and the numerators of the y terms functions of x only.
This simplifies many of the formulas for d substantially.

We discard the area-related formulas, since they will cause aliasing when
the quadrilateral is thin (we'd rather be blurry than jaggy).
To be on the safe side, we can further dismiss the
formulas which use an average rather than
a maximum, since they will underfilter along the longer dimension of
a rectangular area.

From the remaining candidates, we pick formula (7).
It can be calculated as follows:

If we pre-compute ylen for the polygon's range of x's
and save these in an array, and compute xlen once per scan line,
we can avoid the sqrt at each pixel!
The cost of this formula is
one max function, one multiply, and one divide at each pixel,
which is very reasonable (much faster than the mipmap access, in fact).

This is the formula currently in use by POLY.
As you can see in figure 3, it blurs too much near the horizon.
The blurriness cannot be helped much by choosing a different formula.
When texture mapping a polygon like the one in this figure,
we need to filter long, thin strips in the texture.
We have run into the fundamental limitation of mipmaps: they
are intended for square filters.
Experiments have shown that
less conservative formulas (eg. (6)) cause aliasing.
Based on these experiments, I have concluded that
(7) is the best formula for d.

REFERENCES

[1] Smith, Alvy Ray,
Incremental Rendering of Textures in Perspective,

[2] Thornton, Robert,
MS Thesis, Cornell U., 1977, p. 17
[3] /usr1/e/movi/trin.c
[4] Williams, Lance,
Pyramidal Parametrics,
[5] Newman, William M., and Robert F. Sproull,
McGraw Hill, NY. 1979
[6] Carlblom, Ingrid, and Joseph Paciorek,
Planar Geometric Projections and Viewing Transformations,
Vol. 10, No. 4, Dec. 1978