Perspective Texture Mapping by Chris Hecker
Perspective Texture Mapping by Chris Hecker
This page discusses copyrighted material published elsewhere, and used with permission. It is intended as an add-on and a pointer, not as a replacement. If you want to know what you are doing, you should get the articles and read them very closely. Be sure to have a look at Chris Hecker's home page for current info.
In 1995, Chris Hecker started an article series on "Perspective Texture Mapping" in the Game Developer magazine, published by Miller Freeman. The series is finished by now. The articles in question as published in the "Under the Hood/Behind the Screen" column are:
The C++ sample sources are all available from the MFI FTP site. In the archives of the respective issues, you will find
It is recommended to use the final version of the texture mapper that has been released with the April/May 1996 issue, and available on the sites mentioned above. It includes the following files:
texture.h ; Win32 app header file texture.cpp ; Win32 app source texture.rc ; Win32 resource script texture.ico ; Win32 application icon makefile ; Win32 VC++ nmake makefile files.txt ; this file mappers.h ; common texture mapping declarations divflfl.cpp ; Apr/May '95 -- floating point edges and mapping, div/pix divifl.cpp ; Jun/Jul '95 -- integer edge DDA, float mapping, div/pix divfxfl.cpp ; Aug/Sep '95 -- fixedpoint edge, float mapping, div/pix subafxfl.cpp ; Dec/Jan '95 -- fixedpt edge, float mapper, subdiv affine gradient.txt ; comment for subafxfl.cpp rounding setup subafopt.cpp ; Apr/May '96 -- subdividing affine assembly wrapper subaloop.asm ; Apr/May '96 -- subdividing affine assembly inner loop dumb3d.hpp ; cheesy vector library header dumb3d.cpp ; cheesy vector library sourceYou will find the full archive at Chris Hecker's home page or on the MFI FTP site. If everything fails, here is a local copy I am maintaining with permission from Chris Hecker. Please do not redistribute this archive without asking him.
This article series is important and recommended for two reasons: Firstly, from what I have read so far, it is the best comprehensive discussion of perspective texture mapping to be found, including lots and lots of practical issues and an implementation. The theory is surely covered best in sources like Paul Heckbert's Master Thesis, or books like "Digital Image Warping" by George Wolberg, but all you need for a very good start is here. Secondly, the parts I do not (yet) have available reportedly discuss the ideas and the details of a P5-specific optimization of the fast inner loop that has been invented by Michael Abrash. Let's look at what goodies are available.
Included are discussions of definitions and concepts, such as perspective projection, forward mapping, backward or inverse mapping, affine mapping and its drawbacks, linearity of 1/z in screen space, interpolation and triangle gradients, polygon fill conventions, sampling from pixel center and pre-stepping.
This article focuses on triangle rasterization, again with top-left fill convention, lighting all pixels strictly inside the polygon boundaries and pixels exactly on top or left edge boundaries. Instead of the straight floating point implementation used in the previous issue, this time an integer approach is discussed. Chris Hecker provides insights in the floor() and ceil() conversion functions, forward differences, and a side remark in the annoying implementation dependance of the ANSI C mod operator. He discusses use of error-term DDA instead of fixed-point rasterization to scan the edges, with respect to jump predicition failures, taking into account the sampling from pixel center and the pre-stepping.
In his previous article, Chris Hecker concluded mentioning another failure of many texture mappers, namely jerkiness due to using integer endpoints to compute the triangle gradients. To remove this visible jitter, he now takes a close looks at fractional endpoints and their advantages for mapping purposes, and their importance for subdivision approximations of perspective correct texture mapping. He selects a 28.4 fixed point format for representing fractional endpoints, and develops in detail a fixed-point initialized error-term DDA to replace the integer intialized one.
In addition, he describes a subtle bug in the
computing the integer coordinates in the source texture
(of the texel) from the real texture coordinates for the center
of a given screen pixel, and sets off to an in-depth
discussion of truncating and rounding as involved in
defining a mapping rule from real source coordinates to
integer source coordinates. This bug affects the sampling
dependend on texture direction, i.e. rotation affects
visual appearance.
In the archive
you will find the gradient.txt file discussing
how to choose the appropriate rounding rule.
I am hoping for MFI getting them delivered any time soon.
The floating point pipeling code for the texture mapping inner loop described in the articles exploits the fact that the P5 architecture allows for scheduling integer and floating operations in parallel, and effectively reduces computation to 4 cycles/pixel in best case.
The article series does not mention Quake, and the details of the implementation id's rasterizer is acutally using might differ. In his CGDC talk, Michael Abrash stated that screen gradients for texture coordinates and 1/z are used to calculate perspective correct texture coordinates every 8 or 16 pixels, and linear interpolation is used between those points. He characterized the loop to be 100% floating-point down to the 8 or 16 pixel subdivisions, and mentions overlapping FDIV. In summary, their inner loop is clearly faster in floating-point on Pentium than it would be in fixed-point.
Btw., the z-fill that is done by the Quake rasterizer while processing world BSP polygons is not done within the same loop as the perspective texture mapping, because of the ever present lack of general purpose registers on the Intel x86 architecture, as pointed out to me by Chris Hecker and confirmed by John Carmack.
Chris Hecker, articles published in the Game Developer magazine, back issues available.
