The Datafile PD-CD 3/PDCD_3.iso/utilities/utilsf/graphtext/Eddie1

Internet Message Format | 1995-06-12 | 5.5 KB

To: [e-mail]
From: Eddie Edwards <[e-mail]>
Subject: Fast texture coordinate calculation
Reply-To: [e-mail]
Date: Mon, 01 May 1995 19:35:04 +0100
Message-ID: <[e-mail]>
Organization: I Inhaled
X-Mailer: Archimedes TTFN Version 0.36

 SUMMARY
 =======

 This article presents a fast method for calculating texture-map column
 indices when rendering Wolf 3D or DOOM-style walls.  Although the method I
 describe assumes that you are plotting a square texture (e.g. 128x128
 pixels) the method could easily be extended for plotting non-square
 textures.

 NOTATION
 ========

 (u,v) are coordinates in texture space
 (x,y) are coordinates in screen space
 A texture mapping is a pair of functions u(x,y) and v(x,y) which take
 screen coordinates to texture coordinates.  This map gives you the texture
 coordinates corresponding to any screen coordinate, and hence gives all
 the information needed to render a textured plane.

 THE PROBLEM
 ===========

 +-> y                    +-> u
 |         SCREEN         |             TEXTURE
 V x  *--                 V v  *------*
      |  ---                   |      |
      |     ---                |      |
      |        --*             |      |
      |          |             *------*
      |          |
      |        --*
      |     ---
      |  ---
      *--                    Figure 1



 Plotting a DOOM-style wall using a square texture requires drawing a
 parallelogram on the screen (Figure 1).  The very shape of this polygon
 strongly suggests plotting a series of vertical strips of differing widths
 in order to render it.  Since z is constant while y varies, there is no
 effect due to perspective along these strips.  The strip plotter then
 merely stretches a vertical strip from the texture into the vertical strip
 on screen.  But how do we determine which strip?  In Wolfenstein 3D this
 was easy, because the u coordinate can be explicitly calculated by the
 raycasting engine.  However, this method is not available without
 raycasting.  We require a method for calculating a series of u coordinates
 which are perspectively correct.

 SIMPLEST APPROACH
 =================

 A simplistic approach just interpolates u values linearly along the width
 of the polygon.  E.g.

 uinc = 1/(right-left)
 for (x = left, u = 0 ; x < right ; x++, u += uinc)
 {
   plot_strip(u);
 }

 However, this does not take into account the effect of perspective fore-
 shortening.

 To take perspective into account, it seems that for each x coordinate you
 must

 1. Calculate the z coordinate of the point, and hence calculate the actual
    x coordinate (by inverting the perspective transform)
 2. Calculate the texture coordinate from this x value

 Step 2 is a lot of work and requires either a square root or a vector
 rotation (if the angle of the line is precalculated).  Also, the
 introduction of complex floating- or fixed-point calculations at this
 stage of the rendering pipeline is undesirable.

 AN ALGORITHM
 ============

 +-> y                    +-> u
 |         SCREEN         |             TEXTURE
 V x  *=-                 V v  *=-----*
      | =---                   | =    |
      |  == ---                |  ==  |
      |    =   --*             |    = |
      |     ==   |             *-----=*
      |       =  |
      |        ==*
      |     ---
      |  ---
      *--                    Figure 2

 Figure 2 is the same as figure 1, but with the addition of a line which, in
 texture space, is represented by the equation u = v.
 Since the perspective transformation preserves straight lines (a fact
 certain game authors might bear in mind ;-)  the line is straight in
 screen space. Any point on the line in screen space therefore corresponds
 to a pair of equal coordinates (u,u) in texture space.

 But we know that calculating values of v for a strip is easy (they are
 linearly related) so if we can calculate the value of v for a point on
 this line, then we automatically know the value of u.  Therefore, all we
 need to do is trace this line in screen space (easy - it's a straight
 line) and then for each column just find the v coordinate of the current
 point on this line.  This gives us the u coordinate.

 SAMPLE CODE
 ===========

 plot_wall(left,right,ytopleft,ybottomleft,ytopright,ybottomright)
 {
   /* assumes 128x128 textures */

   /* overall */
   width = right - left
   lheight = ybottomleft - ytopleft
   rheight = ybottomright - ytopright

   /* top line */
   y1 = ytopleft
   y1inc = (ytopright - ytopleft)/width

   /* vertical */
   height = lheight
   heightinc = (rheight - lheight)/width

   /* magic line */
   y2 = 0
   y2inc = rheight/width

   for (x = left ; x < right ; x++)
   {
     u = (128 * y2)/height;
     plot_strip(x, y1, height, u);

     y1 += y1inc
     y2 += y2inc
     height += heightinc
   }
 }

 EXTENSIONS
 ==========

 This could easily be extended for non-square textures, but I feel that to
 do so here would detract from the simplicity of the underlying algorithm.

 NOTES
 =====

 I came up with this idea yesterday, when staring blankly at a doodle I'd
 just found myself drawing!  Ping!  I seriously doubt that this really *is*
 new, but it is certainly not widely known.  I haven't thought about
 extending this to arbitrary polygons, but I think something groovy could
 be done.

 By biggest problem is with the division to calculate u.  I don't know
 enough about DDAs to comment, but it seems to me that there must be *some*
 way of getting the value of u iteratively.  Any ideas?

--
Eddie xxx ([e-mail], [e-mail], [e-mail])