home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / PERTEX.TR < prev    next >
Text File  |  1996-08-02  |  10KB  |  246 lines

  1. - Texture Mapping Polygons in Perspective (TM13);Paul Heckbert;4/83.
  2.   this is a troff source file
  3.   It's missing the hand-written equations and pasteup figures
  4.  
  5.   Computer Graphics Lab
  6.   New York Institute of Technology
  7.   Technical Memo No. 13
  8.   28 April 1983
  9.  
  10.  
  11. INTRODUCTION
  12.  
  13. Mapping textures onto polygons is more difficult for perspective
  14. projections than for parallel ones.  Texture mapping in perspective
  15. requires a division at each pixel in the general case,
  16. while parallel projections require none.
  17. Simple incremental formulas presented here make perspective texture mapping
  18. efficient for the inner loop of a polygon renderer.
  19.  
  20. We will also discuss the use of a "mipmap" for efficient, approximate
  21. antialiasing of textures.
  22. Use of a mipmap requires the
  23. calculation of a variable "d" which is a measure of the area in the
  24. texture to be filtered.
  25. We will discuss several formulas for "d" which apply to many surface types
  26. (not just polygons).
  27. We show how one of these formulas can be efficiently computed for polygons;
  28. it is currently in use by my POLY program.
  29.  
  30. Notation:
  31.     
  32.     (x,y) is a point in screen space (frame buffer coords)
  33.  
  34.     (u,v) is a point in texture space
  35.  
  36.     d is proportional to the diameter of the area in the
  37.     texture to be filtered
  38.  
  39.     points are represented by 3 or 4 element column vectors
  40.  
  41.     points are transformed by matrix multiplication with a
  42.     4x3 or 4x4 transformation matrix on the left
  43.  
  44.  
  45. TEXTURE MAPPING POLYGONS IN PERSPECTIVE
  46.  
  47. When mapping a texture onto a polygon in 3D, you usually specify the
  48. mapping by setting up a correspondence between points in object space
  49. (the space in which the polygon vertices are defined)
  50. and points in texture space.
  51.  
  52. In my program POLY, this is done by specifying the u and v coordinates
  53. corresponding to each vertex of the polygon.
  54. For simplicity of implementation, the mapping between texture space and
  55. object space is assumed to be affine (to consist of only scales, rotations,
  56. and translations).  You can map a rectangle to a
  57. parallelogram (or vice versa), but you can't map a rectangle to a trapezoid.
  58. Since a 3D affine transformation has six degrees of freedom,
  59. three points can determine it.
  60. This affine texture space to object space transformation
  61. can be written as follows:
  62.  
  63. The standard formula for mapping object space to screen space is best
  64. expressed with a 4x4 matrix using homogeneous coordinates:
  65. A perspective mapping of texture space to screen space
  66. can be computed by concatenating the two matrices above:
  67. Z is irrelevant, since it is not needed for texture mapping.
  68. Note that we can choose I=1 with no loss of generality.
  69.  
  70. This transformation maps a rectangle in texture space into a quadrilateral
  71. in screen space.
  72.  
  73. For synthesized animation, you usually know the object to
  74. screen space transform.  In interactive or motion-tracking applications,
  75. however, you might want to define the texture space to
  76. screen space mapping by giving the screen-space coordinates of the
  77. vertices of a polygon.  Four points define a perspective
  78. texture to screen space transform, since they have eight degrees of freedom,
  79. and the equations above have eight variables.
  80.  
  81. The transform can be found very simply by setting up the following
  82. equations for each of the four points:
  83.  
  84. This forms an 8x8 system of equations in the variables A-G [2].
  85. This is the method used by my PWARP program.
  86.  
  87. For parallel projections,
  88. the eye is infinitely far away, so w' is constant,
  89. and the formulas reduce to an affine transformation:
  90.  
  91. When texture mapping a polygon, you usually scan it out in screen space
  92. and compute u and v from x and y.  This means we'll need the inverse of
  93. the mappings above.  The inverse mapping has the same form
  94. as the original:
  95.  
  96. A rectangle in screen space is mapped to a quadrilateral in
  97. texture space.  For parallel projections, the quadrilateral is
  98. a parallelogram.
  99.  
  100. For a given scan line, y is constant, so most of the terms are constant.
  101. The two numerators and one denominator can be evaluated once at the left
  102. end of the scan segment and computed incrementally in the x loop.
  103. This requires only three additions and two divisions per pixel.
  104.  
  105. Inner loop of a polygon texture-mapper which samples:
  106.  
  107.    x = xleft
  108.    unum = t0*x+t1*y+t2
  109.    vnum = t3*x+t4*y+t5
  110.    den  = t6*x+t7*y+t8
  111.    for (; x<=xright; x++) {
  112.       sample the point (unum/den,vnum/den) in texture
  113.       write texture color to (x,y) in screen
  114.       unum += t0
  115.       vnum += t3
  116.       den  += t6
  117.    }
  118.  
  119. TEXTURE MAPPING WITH MIP
  120.  
  121. Below is a brief description of mipmaps.
  122.  
  123. At NYIT, textures are usually in the form of a "mipmap", which is
  124. a frame buffer containing the red, green, and blue components
  125. of a texture or image in the upper right, lower right, and lower left
  126. quadrants, respectively.
  127. Each component is filtered down to 9 different scales,
  128. and the 27 pictures fit nicely into a 512x512 frame buffer.
  129. Mipmaps are currently made by repeatedly halving the size of the picture,
  130. starting with the 512x512 original, averaging 2x2 blocks of pixels
  131. on one level to compute the pixel values on the next level up.
  132. This averaging has the same effect as convolution with a square box filter.
  133.  
  134. If you stack the maps they form a pyramid.
  135. We'll use the variable "d" to measure height in this pyramid.
  136. Let's label the original 512x512 image with d=1 (even though it is not in
  137. most mipmaps), the 256x256 image with d=2, ..., up to the tiny 1x1 image,
  138. which will have d=512.
  139.  
  140. To sample a texture using a mipmap, the variable d selects which of the nine
  141. sets of maps is referenced, and (u,v) selects the pixel to be pulled from
  142. that map.  The current implementation actually reads 8 pixels per component
  143. (four from each of two maps) and performs trilinear interpolation among them.
  144. So for the constant cost of 24 pixel reads and 21 (or more) multiplications,
  145. you can approximately filter any square window of the texture.
  146.  
  147. The standard alternative to "mipmapping" is straightforward filtering
  148. of the texture every time you need a sample.  This can be quite slow,
  149. especially when scaling a texture way down.
  150.  
  151.  
  152. We'll assume that most surfaces (whether bicubic, quadric, or whatever)
  153. are approximately planar over the area covered by a pixel.
  154. Under this approximation, a rectangular screen space pixel is mapped into
  155. a quadrilateral in texture space.
  156. We want to filter the quadrilateral to compute the average
  157. texture color for the current pixel.
  158. For most pixels you can further assume
  159. the quadrilateral is nearly a parallelogram.
  160. This is a valid assumption for pixels which are not near a vanishing point
  161. or a singularity of the texture.
  162. (If all pixels map to parallelograms, the surface is planar and
  163. parallel-projected).
  164.  
  165. The size of the approximating parallelogram
  166. is given by four partial derivatives:
  167. The vertices of the quadrilateral can be found exactly by computing
  168.  
  169. differences between the u's and v's of adjacent pixels.
  170. The standard mipmap access cannot filter an arbitrary quadrilateral
  171. (or even an arbitrary rectangle).  It can only "properly" filter square areas.
  172. We thus have the problem of choosing a "good" value for d.
  173.  
  174. With the numbering system described above, d is the side length ("diameter")
  175. of the squares in the original texture to be averaged.
  176. We need to approximate a quadrilateral with a square in order to choose
  177. a value for d.
  178. If our square is too small, the filter will be too sharp, and the mapped
  179. texture jaggy.  If the square is too large, the mapped texture will be
  180. unnecessarily blurry.
  181.  
  182. Choosing a formula for d is a problem in heuristics and approximation.
  183. Here are some of the formulas for d which I have dreamed up:
  184.  
  185. find box around
  186. quadrilateral:
  187.  
  188. box approximating
  189. parallelogram:
  190.  
  191. find lengths of x and y
  192. direction vectors:
  193.  
  194. COMPUTING D FOR POLYGON TEXTURE MAPPING
  195.  
  196. For a polygon in perspective, the four partial derivatives simplify to:
  197.  
  198. Note that the numerators of the x terms are functions of y only,
  199. and the numerators of the y terms functions of x only.
  200. This simplifies many of the formulas for d substantially.
  201.  
  202. We discard the area-related formulas, since they will cause aliasing when
  203. the quadrilateral is thin (we'd rather be blurry than jaggy).
  204. To be on the safe side, we can further dismiss the
  205. formulas which use an average rather than
  206. a maximum, since they will underfilter along the longer dimension of
  207. a rectangular area.
  208.  
  209. From the remaining candidates, we pick formula (7).
  210. It can be calculated as follows:
  211.  
  212. If we pre-compute ylen for the polygon's range of x's
  213. and save these in an array, and compute xlen once per scan line,
  214. we can avoid the sqrt at each pixel!
  215. The cost of this formula is
  216. one max function, one multiply, and one divide at each pixel,
  217. which is very reasonable (much faster than the mipmap access, in fact).
  218.  
  219. This is the formula currently in use by POLY.
  220. As you can see in figure 3, it blurs too much near the horizon.
  221. The blurriness cannot be helped much by choosing a different formula.
  222. When texture mapping a polygon like the one in this figure,
  223. we need to filter long, thin strips in the texture.
  224. We have run into the fundamental limitation of mipmaps: they
  225. are intended for square filters.
  226. Experiments have shown that
  227. less conservative formulas (eg. (6)) cause aliasing.
  228. Based on these experiments, I have concluded that
  229. (7) is the best formula for d.
  230.  
  231. REFERENCES
  232.  
  233. [1] Smith, Alvy Ray,
  234. Incremental Rendering of Textures in Perspective,
  235.  
  236. [2] Thornton, Robert,
  237. MS Thesis, Cornell U., 1977, p. 17
  238. [3] /usr1/e/movi/trin.c
  239. [4] Williams, Lance,
  240. Pyramidal Parametrics,
  241. [5] Newman, William M., and Robert F. Sproull,
  242. McGraw Hill, NY. 1979
  243. [6] Carlblom, Ingrid, and Joseph Paciorek,
  244. Planar Geometric Projections and Viewing Transformations,
  245. Vol. 10, No. 4, Dec. 1978
  246.