CSE168, Computer Graphics II: RenderingTexture Filtering and Mip-MappingMatthias Zwicker1 IntroductionIf we render textures using bi-linear interpolation we will observe aliasing arti-facts in ray-traced images. Intuitively, we can avoid such problems by averagingthe texture over the area of a pixel instead of evaluating it at a single point.To implement such a procedure we have to solve two problems: First, we needto compute the region in the texture that corresponds to the pixel area. Wecall this region the pixel footprint. We describe pixel footprint computationin Section 2. Second, we need a fast procedure to obtain the average of thetexture over this area. This can be achieved using mip-mapping and trilinearinterpolation, which is described in Section 3.2 Calculating the Pixel Footprint2.1 OverviewWe denote pixel coordinates by x and y. We represent the area of a rectangularpixel with side lengths ∆x and ∆y by two perpendicular vectors·∆x0¸and·0∆y¸(1)Our goal is to find the two corresponding vectors in texture space that span thearea corresponding to the pixel. Let us assume we know the functions u(x, y)and v(x, y) that map pixel coordinates to texture coordinates. In other words,given a ray through pixel x, y, these functions return the texture coordinatesu, v at the ray-surface intersection point. The Jacobi matrix of these functionsis defined as the 2 × 2 matrix consisting of their partial derivatives. Intuitively,the Jacobi matrix relates small changes in pixel coordinates to small changes intexture coordinates:·∆u∆v¸="∂u(x,y)∂x∂u(x,y)∂y∂v(x,y)∂x∂v(x,y)∂y#·∆x∆y¸.We multiply the Jacobi matrix with the vectors spanning a rectangular pixelfrom Equation 1. This yields the vectors in texture coordinates that span the1area corresponding to the pixel:"∂u(x,y)∂x∂u(x,y)∂y∂v(x,y)∂x∂v(x,y)∂y#·∆x0¸="∂u(x,y)∂x∆x∂v(x,y)∂x∆x#(2)"∂u(x,y)∂x∂u(x,y)∂y∂v(x,y)∂x∂v(x,y)∂y#·0∆y¸="∂u(x,y)∂y∆y∂v(x,y)∂y∆y#. (3)The pixel footprint in texture coordinates is given by the parallelogram spannedby these two vectors.2.2 Detailed DerivationWe now describe in more detail how to compute the partial derivatives ∂u/∂x,∂u/∂y, ∂v/∂x, and ∂v/∂y. Instead of deriving the functions u(x, y) and v(x, y),we will first compute the inverse functions x(u, v) and y(u, v) and their Jacobimatrix. The desired partial derivatives are then found by inverting this Jacobimatrix. Our discussion here is restricted to the case of triangles with texturecoordinates.The functions x(u, v) and y(u, v) are a concatenation of several steps, whichwe will consider separately. First, we will derive a function p(u, v) that computesa 3D point on a triangle given a pair of texture coordinates. Then we willintroduce functions x0(p) and y0(p) that project 3D points to pixel coordinates.The concatenation of these two steps yields the desired functions x(u, v) =x0(p(u, v)) and y(u, v) = y0(p(u, v)).Let us denote the three coordinates of a point p in world space by p0, p1, p2.For each of the coordinates we will determine a linear mapping p0(u, v), p1(u, v)and p2(u, v) given by three coefficients. We write the linear mappings withunknown coefficients a, b, c . . . i asp0(u, v) =£u v 1¤abc,p1(u, v) =£u v 1¤def,p2(u, v) =£u v 1¤ghi.Given that each triangle vertex stores 3D world co ordinates p0,i, p1,i, p2,iandtexture coordinates ui, vifor i ∈ 0, 1, 2, we can formulate three equations withthree unknowns for each of the coordinates:p0,0p0,1p0,2=u0v01u1v11u2v21abc,p1,0p1,1p1,2=u0v01u1v11u2v21def,p2,0p2,1p2,2=u0v01u1v11u2v21ghi.Therefore, the unknown coefficients are given byabc=u0v01u1v11u2v21−1p0,0p0,1p0,2, (4)def=u0v01u1v11u2v21−1p1,0p1,1p1,2, (5)ghi=u0v01u1v11u2v21−1p2,0p2,1p2,2. (6)This means that we need to perform one inversion of a 3 × 3 matrix and threematrix-vector multiplications to find the unknown coefficients.We now have the mapping from texture coordinates to a point in 3D worldcoordinatesp(u, v) =p0(u, v)p1(u, v)p2(u, v)1=a b cd e fg h i0 0 1uv1= Muv→wuv1, (7)where we expressed p using homogeneous coordinates and introduced the matrixMuv→wcontaining the coefficients a, b, c, . . . i.Next, we look at the projection of the homogeneous point p from worldcoordinates to x, y image coordinates, which we represent by the functions x0(p)and y0(p). This involves the transformation of p to camera coordinates, theperspective projection, and 2D scaling and translation to image coordinates.Let us denote the 4 × 4 transformation from world to camera coordinates byMw→c. The projection functions x0(p) and y0(p) are given byx0(p) =(Mw→cp)0(Mw→cp)2sx+ tx, (8)x0(p) =(Mw→cp)1(Mw→cp)2sy+ ty, (9)where sx, tx, sy, tyare scaling and translation coefficients that are given by thefield of view of your camera and the image resolution. Note that the notation(·)0, (·)1, (·)2refers to the elements 0, 1, 2 of a given vector.We now express p using Equation 7 and introduce the 4 × 3 matrix M =Mw→cMuv→wwhose elements we call mi,j. We rewrite Equations 8 and 9 asx(u, v) =m0,0u + m0,1v + m0,2m2,0u + m2,1v + m2,2sx+ tx,y(u, v) =m1,0u + m1,1v + m1,2m2,0u + m2,1v + m2,2sy+ ty.We use the quotient rule to obtain the partial derivatives of x(u, v) and y(u, v):∂x∂u=m0,0(m2,0u + m2,1v + m2,2) − m2,0(m0,0u + m0,1v + m0,2)(m2,0u + m2,1v + m2,2)2sx,(10)∂x∂v=m0,1(m2,0u + m2,1v + m2,2) − m2,1(m0,0u + m0,1v + m0,2)(m2,0u + m2,1v + m2,2)2sx,(11)∂y∂u=m1,0(m2,0u + m2,1v + m2,2) − m2,0(m1,0u + m1,1v + m1,2)(m2,0u + m2,1v + m2,2)2sy,(12)∂y∂v=m1,1(m2,0u + m2,1v + m2,2) − m2,1(m1,0u + m1,1v + m1,2)(m2,0u + m2,1v + m2,2)2sy.(13)These partial derivatives are the elements of the Jacobi matrix J of x(u, v) andy(u, v)J ="∂x(u,v)∂u∂x(u,v)∂v∂y(u,v)∂u∂y(u,v)∂v#. (14)Finally, we compute the inverse of this matrix to obtain the partial derivativesthat we were looking forJ−1="∂u(x,y)∂x∂u(x,y)∂y∂v(x,y)∂x∂v(x,y)∂y#. (15)Note that we are usually interested in the fo otprint of unit square pixels, i.e.,∆x = 1 and ∆y = 1 in Equations 2 and 3. Therefore, the pixel footprint