Perspective Texture Mapping by Chris Hecker

Introduction

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.

The articles

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:

I received the back issues for Part I-III. MFI will hopefully deliver soon the Part IV issue on scanline subdivision, and Part V issue which contains the discussion of an example of a pipelined floating point texture mapper as invented by Michael Abrash. Another issue I got lays the foundations to the floating point approach Back issues can be ordered from MFI.

The Source

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 source
You 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.

Overview of the articles

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.

Part I: Foundations

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.

Part II: Rasterization

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.

Part III: Endpoints and Mapping

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.

Part IV/V

I am hoping for MFI getting them delivered any time soon.

Quake's Texture Mapping

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.


References:

Note: I add these references to the list -- b.


Author:

Chris Hecker, articles published in the Game Developer magazine, back issues available.


home qdev qdev dread rsc qdev doom license web
home dEr95 r3D dread netrsc quake doom legal web
Author: B., email to bernd@nero.uni-bonn.de, with public PGP key
Copyright (©) 1995, 1996 by author. All rights reserved.
Source: $Id: checker_texmap.html,v 1.2 1996/06/24 00:02:32 b1 Exp $