Reference / Paper · 1989
Berkeley master's thesis, 17 June 1989. The closed-form square-to-quadrilateral projective mapping that OpenFIRE's aiming maths uses.
Fundamentals of Texture Mapping and Image Warping Master’s Thesis under the direction of Carlo Séquin Paul S. Heckbert Dept. of Electrical Engineering and Computer Science University of California, Berkeley, CA 94720 ©1989 Paul S. Heckbert June 17, 1989 Abstract The applications of texture mapping in computer graphics and image distortion (warping) in image processing share a core of fundamental techniques. We explore two of these techniques, the two- dimensional geometric mappings that arise in the parameterization and pro jection of textures onto surfaces, and the filters necessary to eliminate aliasing when an image is resampled during texture mapping or warping. With respect to mappings, this work presents a tutorial on three common classes of mapping: the affine, bilinear, and projective. For resampling, this work develops a new theory describing the ideal, space variant antialiasing filter for signals warped and resampled ac- cording to an arbitrary mapping. Efficient implementations of the mapping and filtering techniques are discussed and demonstrated. Contents 1 Introduction 5 1.1 Texture Mapping... 6... ee ee ee ee ee 5 1.2 Image Warping .. 1... . ee 6 1.3 Organization of this Thesis 2... 1... ee ee et ees 8 2 Two-Dimensional Mappings 9 2.1 Naive Texture Mapping ... 2... ee ee ee es 9 2.1.1 Coordinate Systems ... 1... ee ee es 9 2.1.2 A Naive Implementation of Texture Mapping ..........-252 200s 10 2.2 Simple Two-Dimensional Mappings... 1... 0. ee eee ee ee ee eee 11 2.2.1 Affine Mappings .. 2.1... fe ee ee ee es 13 2.2.2 Bilinear Mappings . 2... 1... ee ee es 14 2.2.3 Projective Mappings... 2... 1 ee eee es 17 2.2.4 Comparison of Simple Mappings .... 0... 0. cee ee ee 21 2.3 Two-Dimensional Mappings in Texture Mapping .............-.50500-. 22 2.3.1 Parameterizing Planar Patches ... 1... 2. ee ee ee es 22 2.3.2 Deducing Projective Mappings .... 2... eee ee ee eee 23 2.3.3 Other Parameterizations.... 2... 2... ee ee 23 2.3.4 Scanning Textures and Image Warps... .. 2... 2... eee ee eee ee es 24 2.3.5 Incremental Techniques for Screen Order Scanning ............... 26 2.4 Example: Photomosaics by Image Warping ...............2-2-.05.. 26 2.5 Summary .... 2... 0... ee ee 27 3 Resampling Filters 30 3.1 Is Filtering Needed? ©... 2... ee ee ee ee 30 3.2 Sampling: The Cause of Aliasing .. 2... 1. ee ee ee 30 3.2.1 Frequency Analysis of Aliasing .. 1... 2.2... eee eee ee eee 33 3.3 Antialiasing . 2... es 36 3.3.1 Sampling at Higher Frequency .. 1... 2... 2 eee ee ee ee et eee 36 3.3.2 Prefiltering ... 2... 2... eee ee ee 36 3.3.3 Some Low Pass Filters... 0... ee ee 37 3.4 Ideal Resampling Filters... 2... ee 41 3.4.1 General, Ideal Resampling Filters... 2... 2... ee ee ee 42 3.4.2 Affine Mappings and Space Invariant Resampling. ..............-. 45 3.4.3. Two-Dimensional Affine Mappings ...............200 0000085 45 3.4.4 Summary: Resampling Affine Mappings .............-...0.0.00-4 46 3.5 Image Resampling in Practice... 1... ee ee 46 3.5.1 Resampling by Postfiltering .. 2... . ee ee ee 46 3.5.2 Image Processing Considerations .... 1... 2... ee eee ee ee ee ee es 47 3.5.3 FilterShape.. 2... ee ee ee 47 3.5.4 Resampling Filter Shape... 1... . ee ee ee 47 3.5.5 Local Affine Approximation... 1... 0... 00. eee ee ee ee ee ee 50 3.5.6 Magnification and Decimation Filters ©... 2... eee ee ee ee ee 51 3.5.7 Linear Filter Warps ....... 2... 2. eee ee ee ee ee ee ee 52 3.5.8 Elliptical Gaussian Filters... 1... ee ee eee 53 3.5.9 An Implementation of Elliptical Gaussian Filters ................ 57 3.6 Future Work .. 2.2.2.2... 2. 2 ee 62 Source Code for Mapping Inference 66 A.1 Basic Data Structures and Routines ... 2... 2.2... .. 2.0... eee eee eee 66 All polyh . 1... eee 66 Al.2 pmaph .. 1... ee ee ee 66 AL3 mxBh ow. ee ee ee 67 A.L4 mxB.c 2. ee ee 67 A.2 Inferring Projective Mappings from 2-D Quadrilaterals ................. 68 A.2.1 pmap_poly.c.. 2... ee 68 A.2.2 pmap.gen.c .. 2... ee 70 A.2.3 mapping_example.c. 2... ee ee ee 72 A.3 Inferring Affine Parameterizations from 3-D Polygons ........----+-++--- 73 A.3.1 pmap-param.c 2... ee es 73 A.3.2 param-example.c . 1... eee ee ee es 74 Ellipses 76 B.1 Implicit Ellipse . 2... ee ee 76 B.2 Transforming an Implicit Ellipse .. 2... ee eee ee ee ee ee 77 B.3 Ellipse Analysis by Rotation. ©... 6 6. ee ee ee ee ee 77 B.4 Ellipse Synthesis by Transforming a Circle... .. 2... ee ee eee ee ees 79 B.5 Parametric Ellipse .. 2... 1 ee ee ee 79 B.6 Converting Parametric to Implicit ©... 6... - ee ee ee es 80 B.7 Converting Implicit to Parametric ©... 6. ee ee ee es 81 Acknowledgements Thanks to Charlie Gunn for clarifying projective geometry, Rick Sayre for his careful reading, and Jules Bloomenthal for detailed critiques between runs on Granite Chief. My readers, Professors Carlo Séquin and Brian Barsky, and Ed Catmull, provided helpful comments. Carlo Séquin and a grant from MICRO generously supported this research. Reference recommendations by Professor Avideh Zakhor and Ken Turkowski, formatting help from Ziv Gigus, and photographic assistance from Greg Ward were also invaluable. The guys of 508-7, John Hartman, Mike Hohmeyer, and Ken Shirriff, created the crucial camaraderie. This paper is based on research begun at the New York Institute of Technology Computer Graphics Lab, where Lance Williams suggested numerous texture applications, Ned Greene and Dick Lundin demanded faster Omnimax resampling programs, and Ephraim Cohen showed me the 8 x 8 system for projective mapping inference. Kevin Hunter suggested the decomposition into two square-to-quadrilateral mappings. Discussions of “resize bugs” with Pat Hanrahan and Tom Porter at Pixar underscored the importance of both reconstruction and prefiltering during resampling. If only there were more time, we could do it all. Chapter 1 Introduction In this thesis, we are interested in the modeling and rendering problems common to texture mapping and image warping. We begin by reviewing the goals and applications of texture mapping and image warping. 1.1 Texture Mapping Texture mapping is a shading technique for image synthesis in which a texture image is mapped onto a surface in a three dimensional scene, much as wallpaper is applied to a wall [Catmull74], [Blinn- Newell76], [Heckbert86b]. If we were modeling a table, for example, we might use a rectangular box for the table top, and four cylinders for the legs. Unadorned, this table model would look quite dull when rendered. The realism of the rendered image can be enhanced immensely by mapping a wood grain pattern onto the table top, using the values in the texture to define the color at each point of the surface. The advantage of texture mapping is that it adds much detail to a scene while requiring only a modest increase in rendering time. Texture mapping does not affect hidden surface elimination, but merely adds a small incremental cost to the shading process. The technique generalizes easily to curved surfaces [Catmull74]. Texture mapping can be used to define many surface parameters besides color. These include the perturbation of surface normal vectors to simulate bumpy surfaces (bump mapping), transparency mapping to modulate the opacity of a translucent surface, specularity mapping to vary the glossiness of a surface, and illumination mapping to model the distribution of incoming light in all directions. These applications are surveyed, and their original literature is cited, in [Carey-Greenberg85]. In all of the varieties of texture mapping mentioned above, geometric mappings are fundamental. Two-dimensional mappings are used to define the parameterization of a surface and to describe the transformation between the texture coordinate system and the screen coordinate system. In texture mapping applications the latter mapping is usually fully determined by the 3-D transformation defined by the camera, the modeling transformations describing the geometry of the scene, and the parameterization that maps a texture onto a surface. There are many texture representations, but in this work we restrict ourselves to the most common: discrete 2-D images. When rendering a textured surface it is necessary to sample the texture image to produce the screen image. Except for scenes viewed with parallel projections, texture mappings are non- affine, so they have nonuniform resampling grids, as shown in figure 1.1 (affine mappings are those composed of rotations, scales, and translations). Antialiasing non-affine texture mappings requires a space variant texture filter, however. Such filters change shape as a function of position, and are much more difficult to implement than space invariant filters. Space variant filters are particularly important for texture mapping applications because of the extreme range of scales involved in many 3-D scenes. (These issues are explored in detail in chapter 3.) 1.2 Image Warping Image warping is the act of distorting a source image into a destination image according to a mapping between source space (u,v) and destination space (z, y). The mapping is usually specified by the functions z(u,v) and y(u, v). (We use the term “warp” instead of its synonyms “distortion” and “transformation” because of its conciseness and specificity: “warp” specifically suggests a mapping of the domain of an image, while “transformation” can mean a mapping of the image range as well). Image warping is used in image processing primarily for the correction of geometric distortions introduced by imperfect imaging systems [Gonzalez-Wintz87]. Camera lenses sometimes introduce pincushion or barrel distortions, perspective views introduce a projective distortion, and other nonlinear optical components can create more complex distortions. In image processing, we do image warping typically to remove the distortions from an image, while in computer graphics we are usually introducing one. Image warps are also used for artistic purposes and special effects in interactive paint programs. For image processing applications, the mapping may be derived given a model of the geometric distortions of a system, but more typically the mapping is inferred from a set of corresponding points in the source and destination images. The point correspondence can be automatic, as for stereo matching, or manual, as in paint programs. Most geometric correction systems support a limited set of mapping types, such as piecewise affine, bilinear, biquadratic, or bicubic mappings. Such mappings are usually parameterized by a grid of control points. A survey of mapping and filtering techniques for image processing is found in [Wolberg88]. The appropriate antialiasing filter for non-affine mappings in image warping is, in general, space variant, just as for texture mapping. Filter quality and efficiency is less of a problem for image processing, however, since the mappings used there usually have a more uniform sampling grid than those for texture mapping. When it is known a priori that the sampling grid is nearly uniform, a fixed “interpolation” filter can be used with good results [Gonzalez-Wintz87]. Uniform resampling (often known as “sampling rate conversion”) is a fairly common task for 1-D signals such as audio [Crochiere-Rabiner83]. Nonuniform sampling has received much less attention to date. 1.3. Organization of this Thesis This thesis is split into two halves: chapter 2 contains a discussion of basic 2-D mappings, and chapter 3 develops and applies a theory for resampling filters. There are also two appendices: the first contains source code for several mapping tasks, and the second summarizes the mathematics (a) ® screen pixel center Pca nen” screen (b) Figure 1.1: a) A teztured surface viewed in perspective. b) Nonuniform grid of texture samples in the screen, of ellipses relevant to filtering. Chapter 2 Two-Dimensional Mappings In our discussion of mappings we restrict ourselves, for the most part, to 2-D images mapped to planar surfaces. The simplest classes of 2-D mappings are the affine, bilinear, and projective transformations. These mappings are well known in mathematics and have been used for years in computer graphics. Despite their fundamental importance, however, the latter two mappings have received little attention in the computer graphics literature. Other aspects of texture mapping and image warping, such as texture synthesis and filtering, have received much more attention, probably because they have more apparent impact on image quality than simple 2-D mappings. We believe that texture mapping would be more common in rendering systems if basic 2-D mappings were more widely understood. In this work we hope to revive appreciation for one class of mappings in particular, the projective mapping. 2.1 Naive Texture Mapping 2.1.1 Coordinate Systems To discuss texture mapping, we need to define several coordinate systems. Tezture space is the 2-D space of surface textures and object space is the 3-D coordinate system in which 3-D geometry such as polygons and patches are defined. Typically, a polygon is defined by listing the object space coordinates of each of its vertices. For the classic form of texture mapping with which we are concerned, texture coordinates (u, v) are assigned to each vertex. World space is a global coordinate system that is related to each object’s local object space using 3-D modeling transformations (translations, rotations, and scales). 3-D screen space is the 3-D coordinate system of the display, a perspective space with pixel coordinates (ar, y) and depth z (used for z-buffering). It is related to world space by the camera parameters (position, orientation, and field of view). Finally, 2-D screen space is the 2-D subset of 3-D screen space without z. When we use the phrase “screen space” by itself we mean 2-D screen space. The correspondence between 2-D texture space and 3-D object space is called the parameteri- zation of the surface, and the mapping from 3-D object space to 2-D screen space is the projection defined by the camera and the modeling transformations (figure 2.1). Note that when we are ren- dering a particular view of a textured surface, it is the compound mapping from 2-D texture space 2-D texture space parameterization compound . mapping 3-D object space projection 2-D screen space Figure 2.1: The compound mapping is the composition of the surface parameterization and the viewing projection. to 2-D screen space that is of interest. For resampling purposes, once the 2-D to 2-D compound mapping is known, the intermediate 3-D space can be ignored. The compound mapping in texture mapping is an example of an image warp, the resampling of a source image to produce a destination image according to a 2-D geometric mapping. 2.1.2 A Naive Implementation of Texture Mapping To demonstrate the subtleties of 2-D mappings, we outline here an algorithm for texture mapping within a z-buffer polygon renderer [Rogers 85]. This simple algorithm will produce a number of visual flaws that are quite instructive. We begin by defining the object space coordinates (z,y,z) and texture coordinates (u,v) at each vertex of each polygon. The polygons are transformed to screen space, yielding z, y, and z coordinates for each vertex. We will need to compute z, u, and v at each pixel, and we would like to do this with fast, incremental techniques. It is well known that the perspective transformation maps lines to lines and planes to planes [Foley-van Dam 82], so linear interpolation is appropriate for computing z. Linear interpolation is also used in Gouraud and Phong shading, so it might seem reasonable to interpolate the texture coordinates (u,v) linearly as well. Following this reasoning, we scan convert the polygon into pixels by linearly interpolating z, z, u, and wv along the left and tight sides of the polygon and linearly interpolating z, u, and v across each scan line. Having texture coordinates (u,v) at each pixel, we can sample the texture array and use the resulting color as the screen pixel value. 10 The inner loop of this primitive texture mapper will then be: for x = xleft to xright if z < ZBUF[x,y] then is new point closer? ZBUF [x,y] = z update z-buffer (r, g, b) = TEX(u,v] sample texture SCR{x,y] = (r, g, b) write screen z= ztdz (u, v) = Cu, v) + (du, dv) where (a,6,c) denotes a vector. The increment values dz, du, and dv are calculated once per scan line. This code uses the texture as the output pixel color (ie. no lighting effects) and it point samples the texture (i.e. no filtering). Close examination of figure 2.2 reveals some of the flaws in the algorithm above. Aliasing (not visible here) would result from a high frequency texture. This can be eliminated by filtering an area surrounding the texture point (u,v) rather than sampling just a single pixel [Feibush- Levoy-Cook80], [Heckbert86b]. More fundamentally, however, these images do not exhibit the foreshortening we expect from perspective (compare with figure 2.3). The textured polygon also shows disturbing discontinuities along horizontal lines passing through each vertex. These discon- tinuities are artifacts of the linear interpolation of u and v. In animation, the horizontal ripples will move distractingly as the camera rolls, since the ripples are rotation variant, and the lack of foreshortening will make the texture appear to swim across a surface. As we will see, this naive terture mapper is correct only for affine mappings. These problems occur because the terture transformation effected by our linear interpolation of u and v is inconsistent with the geometry transformation used to transform the vertices to screen space. Linear interpolation of (u,v) in a scan line algorithm computes a bilinear mapping, while the actual image warp defined by perspective is a projective mapping. One ad hoc solution to this inconsistency is to continue with linear interpolation, but to finely subdivide the polygon. If the texture coordinates are correctly computed for the vertices of the new polygons, the resulting picture will exhibit less rippling. It is hard to know how finely to subdivide the polygon, however. We can find more satisfactory, theoretically correct, solutions to these problems by studying simple, generic 2-D mappings. Later we will apply the generic techniques to texture mapping. 2.2 Simple Two-Dimensional Mappings There is a limitless variety of possible 2-D mappings. Mappings for applications of texture mapping or image warping must satisfy the needs of both the user and the implementer of the system. For a designer modeling a 3-D scene or the user of image distortion software, one of the most important criteria for selecting a mapping is predictability. One form of predictability present in the simplest mappings is the preservation of straight lines. If a texture mapping or image warp bends lines then the results are less predictable than those of a line-preserving mapping. Other desirable properties are the preservation of equispaced points, angles [Fiume-Fournier-Canale87], and areas. The implementer of such a system seeks efficient, incremental computations and well- behaved functions (single-valued and invertible). We will see how well the simplest 2-D mappings meet these criteria. 11 POS Ss PRIS POOUT INSET EE, Figure 2.2: Left: A checkerboard texture. Right: Image produced by naive terture mapper using linear interpolation of u,v. Note horizontal lines of discontinuity passing through vertices (indicated with dashed lines). Figure 2.3: Image produced by projective warp algorithm of §2.3.5 using rational linear interpolation of texture coordinates. Note proper foreshortening. 12 A two-dimensional mapping is a mapping (transformation) that distorts a 2-D source space into a 2-D destination space. It maps a source point (u,v) to a destination point (z,y), according to the functions z(u,v) and y(u,v). We will discuss three classes of mappings: affine, bilinear, and projective. Homogeneous Notation The homogeneous representation for points provides a consistent notation for affine and projective mappings. Homogeneous notation was used in projective geometry [Maxwell46], [Coxeter78] long before its introduction to computer graphics [Roberts66]. The homogeneous notation is often misunderstood so we will take a moment to clarify its use and properties. In familiar Euclidean geometry we represent points of the real plane R? by vectors of the form (x,y). Projective geometry deals with the projective plane, a superset of the real plane, whose ho- mogeneous coordinates are (x', y', w). In projective geometry the 2-D real point (z, y) is represented by the homogeneous vector p = (2’, y’, w) = (zw, yw, w), where w is an arbitrary nonzero number. Vectors of the form (rw, yw, w) for w # 0 form the equivalence class of homogeneous representations for the real point (x,y). To recover the actual coordinates from a homogeneous vector, we simply divide by the homogeneous component; e.g., the homogeneous vector p = (rw, yw, w) = (2’,y’, w) represents the actual point (z,y) = (z'/w,y'/w). This division, a projection onto the w = 1 plane, cancels the effect of scalar multiplication by w. When representing real points with homogeneous notation we could use any nonzero w, but it is usually most convenient to choose w = 1 so that the real coordinates can be recovered without division. Projective space also includes the points at infinity: vectors of the form (x’, y’,0), excluding (0,0,0). The points at infinity lie on the line at infinity. We will see later how augmentation of the real plane by these points simplifies projective geometry. In homogeneous notation, 2-D points are represented by 3-vectors and 3-D points are represented by 4-vectors. For affine and projective mappings, we denote points in source space by ps = (u’, v’,q) and points in the destination space by pg = (2’,y’, w). 2.2.1 Affine Mappings Affine mappings include scales, rotations, translations, and shears; they are linear mappings plus a translation [Foley-van Dam82]. Formally, a mapping T(z) is linear iff T(z + y) = T(z) + T(y) and T(az) = aT(zx) for any scalar a, and a mapping T(z) is affine iff there exists a constant c and a linear mapping L(x) such that T(x) = L(x) +c for all z. Obviously, linear mappings are a subset of affine mappings. A general 2-D affine mapping may be written algebraically as: Pa = PsMga ad 0 (x y l)=(u v 1)]6 e 0 ce f 1 Transform matrices are denoted Map where a is the initial coordinate system and 6 is the final coordinate system. Notice that we have chosen w = g = 1 without loss of generality. The 3 x 3 13 Figure 2.4: Affine warps of image at left. matrix Mgq has 6 degrees of freedom. Geometrically, the vectors (a,d) and (b,e) are basis vectors of the destination space, and (c, f) is the origin. As shown in figure 2.4, affine mappings preserve parallel lines and preserve equispaced points along lines (meaning that equispaced points along a line in the source space transform to equispaced points along a line in the destination space, although the spacing in the two coordinate systems may be different). We can invert an affine mapping to find the destination-to-source transformation simply by inverting the mapping matrix (iff M,q has an inverse). Similarly, affine mappings may be composed by concatenating their matrices. Since an affine mapping has 6 degrees of freedom, it may be defined geometrically by specify- ing the source and destination coordinates of three points. The mapping and its inverse will be nondegenerate if the three points are noncollinear in both spaces. To infer the affine transform matrix from a three point correspondence that maps (ux, vg) to (zx, yk) for k = 0,1, 2, we solve the following matrix equation for M.q: = MsMga Zo Yo uo ve a d 0 [ae - ESUEL Z2 1 ec f 1 The above relation is 6 scalar «uations in 6 unknowns a-f, but the system simplifies easily into two 3 x 3 systems, one for z and one for y. Affine mappings can map any triangle in source space into any triangle in destination space, or map a source rectangle into a destination parallelogram, but no more general distortions are possible. To warp a rectangle into a general quadrilateral, we will need a bilinear, projective, or some other more complex mapping. 2.2.2 Bilinear Mappings Bilinear mappings are most commonly defined as a mapping of a square into a quadrilateral. As shown in figure 2.5, this mapping can be computed by linearly interpolating by fraction u along the top and bottom edges of the quadrilateral, and then linearly interpolating by fraction v between 14 M ¥ pil 4 a 1 oni | { x (u,v) ' pol ! 10 \ Pp | ' ad t u | ; poo 0 say > u > x 0 source space 1 destination space Figure 2.5: Bilinear mapping. the two interpolated points to yield destination point (z, y) [Faux-Pratt79]: (z,y) = (1— u)(1— v)poo + u(1 — v)pio + (1 — u)epor + wvpi1 The general form in matrix notation is: ae (x y)=(uv uw v 1) , ; dh A bilinear mapping is affine ifa = e = 0. The matrix of 8 coefficients may be computed from the four point correspondence of w 2.5 as follows: a ; -1 1 Zoo 6Yoo b 0 0 Z10 Yi10 c ; } Zo. Yo d T1110 This mapping transforms a unit square into the » general vada tora P00, P10; P11; P01, Which an affine mapping cannot do. The bilinear mapping has an unusual mix of properties. Because of its linear interpolation, the forward transform from source to destination space preserves lines which are horizontal or vertical in the source space, and preserves equispaced points along such lines, but it does not preserve diagonal lines, as shown in figure 2.6. Also, the composition of two bilinear mappings is not bilinear, but biquadratic. The inverse mapping from destination space to source space is not a bilinear mapping either; in fact it is not single-valued. The inverse can be derived by solving for v in the x equation: z—bu-—d aut+ec 15 Figure 2.6: Bilinear warps of a test grid. a) Grid in source space. b) Warped grid in destination space for quadrilateral 1 (vertices marked with dots). Note curvature of diagonals. c) Warped grid tn destination space for quadrilateral 2. Diagonals map to parabolas in destination space. Note foldover of some diagonals (caused by the existence of two roots in quadratic equation). 16 and substituting into the y equation. The same can be done for wu, yielding the two quadratic equations: (au+c)(fut+th—y)—(eut+ g)(bu+d—2z)=0 (av+b\(gv+h—y)—(ev+ f)(ev+d—z)=0 so Au?+ Bu+C =0 Dv?+Ev+- F =0 where Az=af—be B=exr—aytah—det+cf—bg C= gr—cy+ch—dg Dz=ag-ce E=exr—aytah-—de-—cf+bg F = fr—by+bh—df We can find (u,v) in terms of (z,y) by evaluating the coefficients A, B, and C above and then computing: _-B+VB?=4AC st bu -d “= 2A 7 0 “Gute The inverse transform is multi-valued, and is much more difficult to compute than the forward transform. 2.2.3. Projective Mappings The projective mapping, also known as the perspective or homogeneous transformation, is a projec- tion from one plane through a point onto another plane [Maxwell46]. Homogeneous transformations are used extensively for 3-D affine modeling transformations and for perspective camera transforma- tions [Foley-van Dam82]. The 2-D projective mappings studied here are a subset of these familiar 3-D homogeneous transformations. The general form of a projective mapping is a rational linear mapping: _ aut+tbvt+e _ du+ev+ f re guthoda’ I Guthot+i (2.1) Manipulation of projective mappings is much easier in the homogeneous matrix notation: Pda = PsMga ad g =(2' y' w)=(u' vw nfs e i c f i where (z,y) = (2'/w,y'/w) for w # 0, and (u,v) = (u’/g, v'/q) for q 0. Although there are 9 coefficients in the matrix above, these mappings are homogeneous, so any nonzero scalar multiple of these matrices gives an equivalent mapping. Hence there are only 8 degrees of freedom in a 2-D projective mapping. We can assume without loss of generality that i = 1 except in the special case that source point (0,0) maps to a point at infinity. A projective mapping is affine when g =A =0. Projective mappings will in general map the line at infinity to a line in the real plane. We can think of this line as the horizon line of all vanishing points, by analogy to the perspective projection. Affine mappings are the special case of projective mappings that map the line at infinity into itself. By defining the projective mapping over the projective plane and not just the real plane, projective 17 Figure 2.7: Projective warps of a test grid controlled by the same quadrilaterals as figure 2.6. a) Warped grid in destination space for quadrilateral 1. b) Warped grid in destination space for quadrilateral 2. Note the vanishing points. mappings become bijections (one-to-one and onto), except when the mapping matrix is singular. For nondegenerate mappings the forward and inverse transforms are single-valued, just as for an affine mapping. Projective mappings share many of the desirable properties of affine mappings. Unlike bilinear mappings, which preserve equispaced points along certain lines, the projective mappings do not in general preserve equispaced points (figure 2.7). Instead they preserve a quantity called the “cross ratio” of points [Coxeter78]. Like affine mappings, projective mappings preserve lines at all orientations. In fact, projective mappings are the most general line-preserving bijective mappings. Projective mappings may be composed by concatenating their matrices. Another remarkable property is that the inverse of a projective mapping is a projective mapping. This is intuitively explained by reversing the plane-to-plane mapping by which a projective mapping is defined. The matrix for the inverse mapping is the inverse or adjoint of the forward mapping. (The adjoint of a matrix is the transpose of the matrix of cofactors [Strang80]; M —! = adj(M)/det(M)). In homogeneous algebra, the adjoint matrix can be used in place of the inverse matrix whenever an inverse transform is needed, since the two are scalar multiples of each other, and the adjoint always exists, while the inverse does not if the matrix is singular. The inverse transformation is thus: Ps = PaMas 18 (A DG q)=(2' y' w)|B E H .C F I (ei—fh fg—di tsa =(2' y’ w)| ch-—bi ai-cg bg—ah (bf -—ce cd-—af ae-—bd When mapping a point by the inverse transform we compute (u, v) from (z,y). If w # 0 and q # 0 then we can choose w = 1 and calculate: u= Az+By+C v= De+Eyt+F Gre+Hy+I’ Ge+Hy+l (2.2) Inferring Projective Mappings In an interactive image warper one might specify the four corners of source and destination quadri- laterals with a tablet or mouse, and wish to warp one area to the other. This sort of task is an ideal application of projective mappings, but how do we find the mapping matrix? A projective mapping has 8 degrees of freedom which can be determined from the source and destination coordinates of the four corners of a quadrilateral. Let the correspondence map (ux, vz) to (xk, yx) for vertices numbered cyclically k = 0,1,2,3. All coordinates are assumed to be real (finite). To compute the forward mapping matrix Mgq, assuming that 1 = 1, we have eight equations in the eight unknowns a-g: m= auz + bu, +c 4 Gurt+ hu, +1 7 du, + eu, + f gupthu,+1 for k = 0,1,2,3. This can be rewritten as an 8 xX 8 system: => upatupbt+ec— upreg — URTEh = TE => upd+uet+ f — unyeg — RYE = YE (uo vo 1 0 0 O —Up%o —VorO)} (4) ( Lo ) uw yy 1 0 0 0 -uy2y —2; b 24 U2 «V2 1 0 0 O —U22%2 —V2%2 c Z2 U3 «U3 1 0 0 O —U3r%3 —V373 d _ 73 0 0 0 to % 1 —Uo¥o ~Vo¥o e| | Yo 0 0 0 wm wy 1 -Hy -1H f 1 0 0 O ug v2 1 —U2y2 —vV2Y2 9g Yy2 Lo 60 (0 uz v3 1 —ugzy3 —v3y32 Lh? \ 3 J This linear system can be solved using Gaussian elimination for the forward mapping coefficients a-h. If the inverse mapping is desired instead, then either we compute the adjoint of Mgq or we follow the same procedure, starting from equation (2.2) instead of (2.1), and solve an 8 x 8 system for coefficients A-H. In speed-critical special cases, there are more efficient formulas for computing the mapping matrix. The formula above handles the case where the polygon is a general quadrilateral in both source and destination spaces. We will consider three additional cases: square-to-quadrilateral, quadrilateral-to-square, and (again) the general quadrilateral-to-quadrilateral mapping. Case 1. The system is easily solved symbolically in the special case where the uv quadrilateral is a unit square. If the vertex correspondence is as follows: 19 x y uv Zo yo O O 21 yw 1 0 Z2 y 1 i zz yz O 1 then the eight equations reduce to c= 29 ate-gr=7} atb+c— grat hr2= 22 b+c—hzr3= 23 f= d+f-m=n dt+e+f-—gythy =y e+ f —hys = ys If we define Az, =21—-2%2 Atg=23-—2q Le =AXZyo-— 2714+ 22-73 Ay=yn—y2 Ay=ys- yo Ly=yYyo-wt y2— ys then the solution splits into two sub-cases: (a) Sz = 0 and Sy = 0. This implies that the zy polygon is a parallelogram, so the mapping is affine, and a = 21 — 29, b= 22—-21,c=2%0,d=91 -Y,€=Y-N, f=y,g=0,h=0. (b) a # 0 or Ly F O gives a projective mapping: _ {Xr Are Az, Axg I=|Sy Ay / Ay Ay h-= Az, Laz / Az, Aza Ay Ly{' {Ay Aye @=2%1—%o+ 92 b=273-—29+hr3 c= 29 d=y1-yot gu € = y3 — yo + hys f= yo This computation is much faster than a straightforward 8 x 8 system solver. The mapping above is easily generalized to map a rectangle to a quadrilateral by pre-multiplying with a scale and translation matrix. Case 2. The inverse mapping, a quadrilateral to a square, can also be optimized. It turns out that the most efficient algorithm for computing this is not purely symbolic, as in the previous case, but numerical. We use the square-to-quadrilateral formulas just described to find the inverse of the desired mapping, and then take its adjoint to compute the quadrilateral-to-square mapping. 20 >< >< case 2 . casel ——$<——> > 0 >u 0 1 case 3 Figure 2.8: Quadrilateral to quadrilateral mapping as a composition of simpler mappings. Case 3. Since we can compute quadrilateral-to-square and square-to-quadrilateral mappings quickly, the two mappings can easily be composed to yield a general quadrilateral-to-quadrilateral mapping (figure 2.8). This solution method is faster than a general 8 x 8 system solver. Source code to infer a projective mapping from a quadrilateral correspondence is contained in §A.2. 2.2.4 Comparison of Simple Mappings As mentioned previously, affine and projective mappings are closed under composition, but bilinear mappings are not. The three basic mapping classes compose as follows: 4} MAP1 o MAP2 > | affine | bilinear | projective | affine affine bilinear projective bilinear bilinear biquadratic tational bilinear projective projective | rational biquadratic | projective Thus, the composition of two bilinear mappings is a biquadratic mapping. Since (nonsingular) affine and projective mappings are closed under composition, have an iden- tity and inverses, and obey the associative law, they each form a group under the operation of composition. Bilinear mappings do not form a group in this sense. We summarize the properties of affine, bilinear, and projective mappings below: 21 PROPERTY AFFINE BILINEAR PROJECTIVE preserves parallel lines yes no no preserves lines yes not yes preserves equispaced points yes not no maps square to parallelogram quadrilateral quadrilateral degrees of freedom 6 8 8 closed under composition yes no, biquadratic yes closed under inversion yes no, solve quadratic yes single-valued inverse yes no yes forms a group yes no yes incremental forward mapping | 2 adds 2 adds 2 divs, 3 adds? incremental inverse mapping | 2 adds 1 square root, more 2 divs, 3 adds texcept for horizontal and vertical lines in source space see §2.3.5 For the designer, affine mappings are the simplest of the three classes. If more generality is needed, then projective mappings are preferable to bilinear mappings because of the predictability of line-preserving mappings. For the implementer, the group properties of affine and projective mappings make their inverse mappings as easy to compute as their forward mappings. Bilinear mappings are computationally preferable to projective mappings only when the forward mapping is used much more heavily than the inverse mapping. 2.3. Two-Dimensional Mappings in Texture Mapping As mentioned earlier, texture mapping consists of a transformation of 2-D texture space to a 3- D surface via the parameterization, and then a projection of that surface into 2-D screen space. Two-dimensional mappings are central to each of these transformations. Parameterization is a 2-D mapping of a texture onto a surface in 3-D, and rendering uses a 2-D mapping to control the resampling of the texture to produce a screen image. We can thus make use of the 2-D mappings discussed above in both modeling and rendering textured surfaces. 2.3.1 Parameterizing Planar Patches The 2-D mappings described earlier can be used to parameterize polygons and other planar surfaces. A surface parameterization describes surface points in 3-D object space in terms of two parameters u and v. We call a parameterized plane a planar patch. Planes are most easily parameterized affinely, by selecting two linearly independent basis vectors in the plane and a point in the plane. These three 3-D points define the 9 degrees of freedom of an affine parameterization or affine patch. An affine patch is given by: adg (x y z)=(u v ot e i ec f i 22 Just as with purely 2-D mappings, affine patches allow arbitrary triangle-to-triangle and rectangle- to-parallelogram mappings, but not rectangle-to-arbitrary-quadrilateral mappings. Source code to infer an affine mapping from the texture and object space coordinates of a polygon is given in §A.3. Occasionally one may need more generality than is provided by affine mappings, for example, to distort a rectangular brick texture into a trapezoidal keystone. For this we need bilinear or projective patches (the latter also known as rational linear patches). The general form of a bilinear patch is: (x y z)=(uv uw v 1) Aa ome TQ SH ~~ Tt, and projective patches have the form: o. j k l (The coefficients a — / are unrelated between these three forms, of course). ad z w)y=(uv' v' oe e ec f Like affine patches, projective patches are always planar. Bilinear patches can be nonplanar, however. The general bilinear patch has 12 degrees of freedom, while planar bilinear patches and projective patches have 11 degrees of freedom. The coefficients of a bilinear or projective patch can be inferred from a four point correspondence between texture space and object space. Bilinear patches are sometimes used in texture mapping [Hourcade-Nicolas83], [Catmull-Smith80] when nonplanar quadrilaterals are needed. Projective patches are usually preferable for planar quadrilaterals, however, because of their superior properties. Occasionally, practitioners have used bilinear patches when projective patches would have been more appropriate. For example, bilin- ear parameterizations were proposed for point-in-quadrilateral testing in a ray tracing machine [Ullner83]. In that algorithm, a ray is intersected with the plane of a polygon to determine the intersection point in object space. Next, point inclusion is determined by inverting the bilinear mapping, transforming object space coordinates to texture space, and testing if (u,v) lies within a unit square. The hardware designed was quite complex, as it involved square roots. If projective patches had been used instead then the inverse mapping could have been much simpler. (There are faster methods for point-in-quadrilateral testing than transforming to a unit square, of course.) 2.3.2 Deducing Projective Mappings If a chain of transformations from texture space to screen space is known, then we can synthesize the compound mapping matrix; there is no need to infer i