My master's thesis, "Texture Mapping and Resampling for Computer Graphics",
is now available for electronic access. The thesis is an in-depth examination
of the entire texture mapping process, starting with simple introductory
concepts and ending with a discussion of new state-of-the-art texture
filtering algorithms developed during the course of this thesis research work.

The thesis is geared to beginners and experts alike. The first half of the
thesis introduces the concepts of texture mapping, how texture coordinates
are assigned to surfaces (the parameterization), how texture is rendered
onto a surface, and why a texture image must be filtered before it is applied
to an object (72 pages). This is then followed by a review of current and 
popular texture filtering algorithms (MIPmapping, summed area tables, 
stochastic and adaptive supersampling) which are analyzed and related to the 
filtering theory outlined in previous sections of the thesis.

All material is presented in a non-mathematical, conceptual nature with dozens 
of accompanying illustrations for clarification. For the expert, most concepts
are expanded upon with some form of semi-rigorous, mathematical explanation. 

The "Texture Resampling Process" chapter is of particular interest to any 
reader wishing to gain an insight into the concepts and mathematical theory 
behind the resampling of a 2D image onto an arbitrarily-oriented plane in 
3-space (in other words, how to texture map a 2D image onto a 3D object with 
no artifacts appearing in the final image).

The latter half of the thesis introduces the EWA and NIL image filtering 
techniques and how they were incorporated into the author's scanline rendering
system as texture filtering algorithms. The thesis results show that the EWA 
filter produces higher quality textured images than that of the common MIPmap 
texture filtering algorithm, yet with only slight decrease in rendering speed.

The appendices also include a conceptual tutorial on parametric curves and 
surfaces, and an interesting discussion of how to add an accumulation buffer
to a scanline renderer so that depth-of-field, motion blur and pseudo-stochastic
anti-aliasing can be simulated. 

The thesis is 163 pages of single-spaced text, with 58 illustrations and 8 
tables. The uncompressed Postscript file is 9.5Mb in size. It can be viewed 
with an appropriate Postscript viewer or printed to any Postscript printer. 
Note that it is very important to have the print density on the laser printer 
cartridge set properly so that the bitmap images do not get printed overly 
dark.

Appended to this message are:

	1) How to obtain this thesis by FTP
	2) Abstract from the thesis
	3) Table of contents from the thesis

Please contact lansd@dgp.toronto.edu if you have any further questions or
problems. The thesis is Copyright (c) 1991 by Robert C. Lansdale.

------------------------->>>>  How to FTP  <<<<------------------------------

To obtain a copy by anonymous FTP, please use the following procedure:

  % ftp explorer.dgp.toronto.edu 	<--- or: 128.100.4.1 --->

  Name (explorer.dgp.toronto.edu:lansd): anonymous
  Password: {---> type your name & address here,  e.g. lansd@dgp.toronto.edu <---}

  ftp> cd pub/lansd
  ftp> binary
  ftp> get lansd.ps.Z
  ftp> quit
  % uncompress lansd.ps.Z
  % lpr -P{---postscript-printer---} lansd.ps

Notes: 
	1. The Postscript file includes several bitmap images and will render 
	   best on a 300 dpi laser printer.
	2. Anonymous FTP is only accepted from hosts that are running the
	   finger daemon.

--------------------------->>>>  Abstract  <<<<-------------------------------

Texture mapping is a popular rendering technique used in three-dimensional 
computer graphics. It allows textures represented as digital images to be 
mapped across surfaces in a 3D scene, providing a simple method for adding 
realistic detail to computer generated imagery. The process of transforming 
a discrete 2D texture image onto a 3D surface and subsequently onto the 2D 
projection window (the screen) is called image resampling. Deformations 
applied to the texture image during this process often lead to visual 
artifacts in the textured surface, many of which result from frequencies 
in the transformed texture image too high for the output display to reproduce.
These artifacts can be removed by filtering the texture in accordance with 
digital signal filtering theory.

Texture filtering removes high frequencies from the texture image before it is 
resampled to the screen. Since this tends to be an expensive operation, 
researchers have developed several cost effective, constant-time techniques. 
These techniques allow the filtering operation to be performed in a bounded 
number of accesses to the texture image, independent of the image's size. 
However, approximations of the ideal filtering process with low quality, 
space-invariant filter functions tend to produce poor results. 

The major contribution of this thesis is the adaptation and implementation of 
two recently published high-quality, space-variant, constant-time filtering 
techniques into the author's NuGraf-3d scanline rendering system. These are 
the "Elliptical Weighted Average Filter" by Greene and Heckbert and the 
"NIL Constant-Time Space-Variant Filter" by Fournier and Fiume.

A second significant contribution of this thesis is the development of stable 
surface parameterizations for projective and affine mappings. The solutions 
presented are applicable both to texture mapping and to other applications. 
The thesis also provides a thorough overview of all phases of the texture 
mapping process, including a tutorial of 1D and 2D filtering theory, and a 
detailed review of existing filtering techniques. An appendix describes how 
uniform and stochastic supersampling, depth-of-field and motion blur were 
accommodated in NuGraf-3d with the addition of an accumulation buffer.

----------------------->>>>  Table of Contents  <<<<--------------------------

0  Introduction

   0.1 Thesis Overview  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :   3
   0.2 Contributions of Thesis   : : : : : : : : : : : : : : : : : : : : : : : : : : : : :   5

1  The Texturing Process

   1.1 Applications of Texturing To Computer Graphics  : : : : : : : : : : : : : : :   7
   1.2 The Texturing Process  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :   8
       1.2.1 Texture Function Selection  : : : : : : : : : : : : : : : : : : : : : : :   8
       1.2.2 The Texture "Map" Derivation  : : : : : : : : : : : : : : : : : : : : :  10
       1.2.3 Texture Distortion Control  : : : : : : : : : : : : : : : : : : : : : : :  10
       1.2.4 Rendering Textured Surfaces  : : : : : : : : : : : : : : : : : : : : : :  10
   1.3 Extended Applications of Texture Filtering  : : : : : : : : : : : : : : : : : :  11

2  Surface Parameterization, Geometric Mappings, and Accurate Texture Rendering

   2.1 Composing the Compound Texture Map  : : : : : : : : : : : : : : : : : : :  14
       2.1.1 Derivation of the Surface Parameterization  : : : : : : : : : : : : : :  15
       2.1.2 Induced Geometric Surface Parameterizations  : : : : : : : : : : : : :  17
       2.1.3 The Projective Surface Parameterization : : : : : : : : : : : : : : : :  18
             2.1.3.1 Computing an Induced Projective Surface Parameterization   20
   2.2 Interpolation Anomalies in a Scanline Renderer  : : : : : : : : : : : : : : : :  22
       2.2.1 Corrective Solutions to Interpolation Anomalies : : : : : : : : : : : :  24
       2.2.2 Retrofitting NuGraf-3d for Accurate Texturing  : : : : : : : : : : : :  26
   2.3 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  29

3  The Texture Resampling Process

   3.1 The Texture Resampling Problem   : : : : : : : : : : : : : : : : : : : : : : :  32
   3.2 Resampling in the One-Dimensional Domain   : : : : : : : : : : : : : : : : :  35
       3.2.1 Introduction to Aliasing in 1D Signals  : : : : : : : : : : : : : : : : :  35
       3.2.2 An Overview of 1D Signal Processing   : : : : : : : : : : : : : : : : :  38
             3.2.2.1 Filtering Basics   : : : : : : : : : : : : : : : : : : : : : : : :  39
             3.2.2.2 Reconstruction Filters  : : : : : : : : : : : : : : : : : : : : :  42
             3.2.2.3 Discrete Convolution   : : : : : : : : : : : : : : : : : : : : :  44
       3.2.3 A Naive Implementation of 1D Signal Resampling  : : : : : : : : : :  45
       3.2.4 The Ideal Resampling Process in 1D  : : : : : : : : : : : : : : : : : :  47
   3.3 Extension to 2D Filtering  : : : : : : : : : : : : : : : : : : : : : : : : : : : :  51
   3.4 2D Resampling Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : :  52
       3.4.1 The Screen-Space-Based Ideal 2D Resampling Process  : : : : : : : :  54
       3.4.2 The Texture-Space-Based Ideal Resampling Process  : : : : : : : : :  56
             3.4.2.1 Space-Invariant Filtering  : : : : : : : : : : : : : : : : : : :  58
             3.4.2.2 Space-Variant Filtering  : : : : : : : : : : : : : : : : : : : :  59
   3.5 Approximating the Ideal Resampling Process  : : : : : : : : : : : : : : : : :  59
       3.5.1 Space-Variant Filtering with Direct Convolution  : : : : : : : : : : :  61
             3.5.1.1 Non-Uniform Resampling with Direct Convolution  : : : : :  62
             3.5.1.2 Retrospective on Direct Convolution : : : : : : : : : : : : :  63
       3.5.2 Constant-Time Direct Convolution Techniques  : : : : : : : : : : : :  63
             3.5.2.1 The MIP mapping Technique  : : : : : : : : : : : : : : : : :  64
             3.5.2.2 The Summed-Area Table Technique  : : : : : : : : : : : : :  65
       3.5.3 Non-uniform Resampling with Ideal Supersampling : : : : : : : : : :  67
       3.5.4 Supersampling  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  68
             3.5.4.1 Adaptive Supersampling   : : : : : : : : : : : : : : : : : : :  70
             3.5.4.2 Stochastic Sampling  : : : : : : : : : : : : : : : : : : : : : :  71
   3.6 Preview of the EWA and NIL Filtering Techniques  : : : : : : : : : : : : : :  72
   3.7 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  73

4  The Elliptical Weighted Average Filter

   4.1 The EWA Resampling Filter   : : : : : : : : : : : : : : : : : : : : : : : : : :  75
   4.2 Overview of the EWA Filtering Technique  : : : : : : : : : : : : : : : : : : :  76
       4.2.1 Operation of the EWA Filter  : : : : : : : : : : : : : : : : : : : : : :  77
       4.2.2 Example Run-Through of the EWA Filter  : : : : : : : : : : : : : : :  80
   4.3 Implementation of EWA in NuGraf-3d  : : : : : : : : : : : : : : : : : : : : :  82
   4.4 EWA Filter Extensions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  84
   4.5 Performance Test Results  : : : : : : : : : : : : : : : : : : : : : : : : : : : :  87
   4.6 Shortcomings of the EWA Filter  : : : : : : : : : : : : : : : : : : : : : : : :  88
   4.7 Extending EWA for use with Arbitrary Filter Functions  : : : : : : : : : : :  89
   4.8 Future Work   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  90
   4.9 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  91

5  NIL - Constant-Time, Space-Variant Filtering

   5.1 Introduction to the NIL Filtering Process  : : : : : : : : : : : : : : : : : : :  94
       5.1.1 Providing for Oddly-Shaped Convolution Mask Regions  : : : : : : :  94
       5.1.2 Example Use of the NIL Filtering Technique   : : : : : : : : : : : : :  98
   5.2 Extensions to the NIL Filtering Algorithm : : : : : : : : : : : : : : : : : : : 101
       5.2.1 Extending NIL into a Unified Resampling Technique  : : : : : : : : : 102
       5.2.2 Improving the Convolution Mask Area Approximation  : : : : : : : : 104
       5.2.3 New Patch Subdivision Techniques  : : : : : : : : : : : : : : : : : : : 105
   5.3 Applying NIL to the Checkerboard Test Image  : : : : : : : : : : : : : : : : 109
   5.4 NIL as a "Texture Manipulation" Tool  : : : : : : : : : : : : : : : : : : : : : 110
   5.5 Future Work   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 112
   5.6 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 114

6  Conclusions

   6.1 Comparison of the MIP map, Supersampling, EWA & NIL Techniques  : : : 116
   6.2 Future Work   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 117
   6.3 Retrospective  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 118

A  Example Images Using Explicit and Induced Surface Parameterizations

   A.1 Image 1  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 119
   A.2 Image 2  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 119

B  The 2D-3D Projective Surface Parameterization Algorithm

C  Reparameterizing the 4x4 Orthographic Projection Matrix into a 4x3 Matrix

D  The Fourier Transform

E  Fourier Convolution

F  Parametric Curves and Surfaces

   F.1 Parametric Curves  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 137
       F.1.1 Example Application of an Order 2 (Bilinear) Curve  : : : : : : : : : 138
   F.2 Parametric Surfaces   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 139

G  Integration of NIL into NuGraf-3d

H  Application of an Accumulation Buffer in NuGraf-3d

   H.1 Depth-of-field Effects  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 145
   H.2 Stochastic and Supersampled Anti-aliasing : : : : : : : : : : : : : : : : : : : 148
   H.3 Motion Blur : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 151
