Newsgroups: comp.graphics
From: lansd@dgp.toronto.edu (Robert Lansdale)
Subject: Fire sale: Interesting thesis/tutorial on 2D texture mapping
Organization: CSRI, University of Toronto
Distribution: na
Date: 9 Nov 92 23:24:33 GMT

I have available 11 remaining copies on my master's thesis that are currently 
taking up wasted space in my office. I'll let each go for (US$) $15  to cover 
the costs of copying, binding and shipping. Please email me to reserve a copy 
(lansd@dgp.toronto.edu).

The thesis deals with the 2d texture mapping process, from simplistic  basics 
to  state-of-the-art resampling  techniques (texture anti-aliasing).  Readers 
with  little  knowledge  of  2d texture  mapping  will  find  the  conceptual 
tutorials easy to comprehend and informative, while the new research material 
will hopefully spur on the experts to try out the new filtering techniques in 
their own renderers. 

This list describes some of the interestings aspects of the thesis:

     - 163 pages, double sided, single spaced
     - 59 complex diagrams and images
     - A thorough overview of the 2d texture mapping process (72 pages).  The 
       tutorial/discussion begins assuming that the reader knows little about 
       texture  mapping and slowly progresses through to advanced 2d  texture 
       resampling. 
     - Discussions,  explanations  and comparisons of  all  2d  anti-aliasing 
       (resampling) techniques.
     - How  robust  2d texture mapping and resampling was integrated  into  a 
       production-quality scanline renderer. 
     - Two detailed chapters on two new texture resampling techniques (EWA  & 
       NIL).  This  includes theory, implementation and results, as  well  as 
       "do-it-yourself" sections. 
     - An   appendix   describing  parametric  curves  &  surfaces   from   a 
       programmer's  (intuitive)  viewpoint  rather  than  a   mathematicians 
       viewpoint. 
     - An  appendix  describing in detail how to add  depth-of-field,  motion 
       blur  and stochastic anti-aliasing effects to a  _scanline_  renderer. 
       This augments existing research which implements these techniques uses 
       distributed ray tracing or zbuffer algorithms. 

The table of contents and the abstract of the thesis follow:

		         Table of Contents
		         =================

1. The texturing process
	1.1 Applications of texturing to computer graphics
	1.2 The texturing process
		1.2.1 Texture function selection
		1.2.2 The texture "map" derivation
		1.2.3 Texture distortion control
		1.2.4 Rendering textured surfaces
	1.3 Extended applications of texture filtering

2.  Surface parameterizations, geometric mappings, and accurate texture rendering
	2.1 Composing the compound texture map matrix
		2.1.1 Derivation of the surface parameterization
		2.1.2 Induced geometric surface parameterization
		2.1.3 The projective surface parameterization
			2.1.3.1 Computing an induced projective surface parameterization
	2.2 Interpolation anomalies in a scanline renderer
		2.2.1 Corrective solutions to interpolation anomalies
		2.2.2 Retrofitting a scanline renderer for accurate texturing
	2.3 Summary

3. The Texture Resampling Process
	3.1 The texture resampling problem
	3.2 Resampling in the 1d domain
		3.2.1 Introduction to aliasing in 1d signals
		3.2.2 An overview of 1d signal processing
			3.2.2.1 Filtering basics
			3.2.2.2 Reconstruction filters
			3.2.2.3 Discrete convolution
		3.2.3 A naive implementation of 1d signal resampling
		3.2.4 The ideal resampling process in 1d
	3.3 Extension to 2d filtering
	3.4 2D Resampling introduction
		3.4.1 The screen-space-based ideal 2d resampling process
		3.4.2 The texture-space-based ideal resampling process
			3.4.2.1 Space-invariant filtering
			3.4.2.2 Space-variant filtering
	3.5 Approximating the ideal resampling process
		3.5.1 Space-variant filtering with direct convolution
			3.5.1.1 Non-uniform resampling with direct convolution
			3.5.1.2 Retrospective on direct convolution
		3.5.2 Constant-time direct convolution techniques
			3.5.2.1 The MIP mapping technique
			3.5.2.2 The summed-area table technique
		3.5.3 Non-uniform resampling with ideal supersampling
		3.5.4 Supersampling
			3.5.4.1 Adaptive supersampling
			3.5.4.2 Stochastic sampling
	3.6 Preview of the EWA and NIL filtering techniques
	3.7 Summary

4. The Elliptical Weighted Average Filter
	4.1 The EWA resampling filter
	4.2 Overview of the EWA filtering technique
		4.2.1 Operation of the EWA filter
		4.2.2 Example run-through of the EWA filter
	4.3 Implementation of the EWA in a scanline renderer
	4.4 EWA filter extensions
	4.5 Performance test results
	4.6 Shortcomings of the EWA filter
	4.7 Extending EWA for use with arbitrary filter functions
	4.8 Future work
	4.9 Summary

5. NIL - Constant-time, Space-Variant filtering
	5.1 Introduction to the NIL filtering process
		5.1.1 Providing for Oddly-shaped convolution mask regions
		5.1.2 Example use of the NIL filtering technique
	5.2 Extensions to the NIL filtering algorithm
		5.2.1 Extending NIL into a unified resampling technique
		5.2.2 Improving the convolution mask area approximation
		5.2.3 New patch subdivision techniques
	5.3 Applying NIL to the checkerboard test image
	5.4 NIL as a "texture manipulation" tool
	5.5 Future work
	5.6 Summary

6. Conclusions
	6.1 Comparison of the MIPmap, Supersampling, EWA & NIL techniques
	6.2 Future work
	6.3 Retrospective

A. Example Images using explicit and induced surface parameterizations
	A.1 Image 1
	A.2 Image 2

C. The 2D-3D projective surface parameterization algorithm

D. Reparameterizing the 4x4 orthographic projection matrix into a 4x3 matrix

E. The Fourier Transform

F. Fourier Convolution

G. Parametric curves and surfaces
	G.1 Parametric curves
		G.1.1 Example application of an Order 2 (bilinear) curve
	G.2 Parametric surfaces

H. Integration of NIL into a scanline renderer

I. Application of an accumulation buffer in a scanline renderer
	I.1 Depth-of-field effects
	I.2 Stochastic and supersampled anti-aliasing
	I.3 Motion blur

============================================================================

                    	      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     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  a  scanline  renderer  with  the  addition  of   an  
accumulation  buffer.

-- 
Robert Lansdale - (416) 978-6619       Dynamic Graphics Project	
Internet: lansd@dgp.toronto.edu        Computer Systems Research Institute
UUCP:   ..!uunet!dgp.toronto.edu!lansd University of Toronto
Bitnet:	  lansd@dgp.utoronto           Toronto, Ontario M5S 1A4, CANADA
Newsgroups: comp.graphics,comp.graphics.animation,sci.image.processing