Make your own free website on Tripod.com

Affine Texture Mapping by Index Interpolation


When I came up with the concept of Index Interpolation, I always thought it was an old idea, but nobody ever said anything about it. I thought I would take it upon myself by bringing it up in the newsgroups and see what I got. I actually had a handful of answers that said it's an old idea and has been done before. The only thing is I also got many many more (72 to be exact) that said that wasn't true at all. Even stranger was that I got still more (1624 replies!) that said this one basic idea -- "It will never work. No way for it to work. That's it. It's over. It's a hopeless cause in every way. Give it up. Go home to your mother."

They say it doesn't really work, but it does. When they tell what weaknesses there are in the theory, they're absolutely right. But all such problems are ameliorable. First off, let me begin by saying you cannot interpolate memory index of texture coords. You can only interpolate index within the the span of the texture table. Think of how we always used to index our pixels in good old 13h...

        320*y + x    -- 320 is the offset

		That's basically all there is to it.  
		But this is not where it is in RAM!!

	A0000h + [320*y + x]  -- There we go!!

        That is the kind of value we cannot interpolate with the tmap.
      If we have a 256x256x8-bit tmap... then tmap index is

                (v shl 8) + u    -- This we can interpolate

                TmapPtr + [(v shl 8) + u]  --- This we cannot interpolate

        We can only add TmapPtr later.  It has to be done this way because large
	values like pointers are definitely going to affect the delta values.  Also
	we would have to give up all of our fractional bits.  It is the fractional
	bits that gives us the better representation of <u,v> coordinate interp.

That solves problem number one.
Next is the problem of alignment. The above example talked about a 256x256 8 bit indexed color tmap. What do you do with a 256x256 16-bit RGB map? If you interpolate index in the table you may run into halfway points and such. We can't have that.

        The equation for indexing a 256x256x16bit map is...

                (v shl 9) + (u shl 1)

        As you can probably guess, indices should be even numbers.
        But if we interpolate this value the deltas could be odd or even.
        That may result in odd numbers which means we'll be ending halfway
        between one texel and another.

                You could AND it with FFFEh, but the more accurate method
        would be to factor out the two and multiply it in afterwards.

                (v shl 8) + u  --- This quantity is interpolated The result is 
				   multiplied by two. Same trick could be pulled
				   on a 32-bit tmap.( mul by 4 ) 

		Another possibility would be to factor out the two and compute
	deltas based on that value, then multiply all quantities by two before
	the inner loop. (i.e. compute deltas based on [v shl 8 + u], but then
	put mul both the index and the Index-delta by two, then do the inner
	loop)

Let's also be clear on one other thing. This method of index interpolation works ONLY on affine tmapping. It could be made to work on perspective mapping, but it may not be that simple. You would have to multiply current u,v deltas by the corresponding amounts. Or do u,v interp for the few points if you do scanline or area subdivision and so on. I am working out some equations for index interp for perspective mapping, but it seems to depend on the algorithm as to whether or not it will work (See below). Still there are those who would shoot down the concept, but I wrote up a simple proof that shows that it DOES work. UNCONDITIONALLY!!!
You can see from the proof that whether you do (u,v) coord interpolation or texel index interpolation, the deltas prove to be 100% exactly the same. That's all there is to it. While it only shows the case of interpolation on a scanline, the same logic can be extended to edges. The initial values cannot possibly be wrong as long as you're still using the same routines to generate those. Nothing so far is disputable.


You know, I've gone on all this time and I haven't really said what Index interpolation IS. Well, from the examples so far, you should be able to guess. Normal texture mapping involves linearly interpolating the (u,v) texture coordinates. The texture coordinates are then indexed in the texture table by using the table offset and the coordinates (u + v*offset). Finally, we have the texel we need to plot on the screen. Index interpolation cuts out the middleman by indexing (u,v) texture coords ahead of time and interpolating those resulting quantities. So instead of adding du to u and dv to v, then taking (v*offset) + u and looking up in the table; You add dI to I and look up in the table.
        You may think an inner loop like...

                u += du;
                v += dv;
                c = Tmap[v][u];

        is fast, but that last instruction actually involves multiplying
        v by the offset and adding u and adding that result to Tmap's
        pointer.

        Now compare to....
                
		I += dI;
		c = Tmap[I];

        Hmmmmmmmm.... That's a toughie...
		Fewer operations in the inner loop, Fewer div's in polygon setup,
	possibly even fewer parameters to be passed in, smaller code.


NOTE : As far as using this for Perspective Correct Texture Mapping, it does work for methods that use 1/z interpolation.  This includes Area and Scanline Subdivision and even "perfect mapping."  However, my tests and a few calculations ground out on paper shows that it also works just fine and dandy for parabolic interpolation.  This should make sense as the final value of slope for parabolic interp depends on the value from linear interp.  Of course, as you know, parabolic is simply an approximation.  I'm planning to do some tests for hyperbolic interpolation which will produce 100% correct results.  I cranked out some calculations on paper which show that it will work, but I haven't done any test routines yet [funny, but the proof for that was even shorter than the linear one!].  For that matter, I haven't done any tests w/ 1/z interp, but some work on paper shows that Index Interpolation will definitely work.  I'll try and post the Perspective proofs ASAP.

The work w/ hyperbolic and parabolic interp really came about because of the fact that it would be inconceivably faster than 1/z perfect mapping.  Lately though, it's become rather mainstream to pull various little tricks like writing your own inversion routine to make it all go very fast.  The hard part is to somehow speed up the interaction between the floats and ints.  If you depend on the compiler, you will lose.

Note that when I did my work w/ the hyperbolic interp. on texture indices, I used a different method than you might have expected.  Instead of linear operators or a tanh delta curve, I use the value curve.  
f(t) = 2.414213562375... * (SQRT(t^2 + 1) - 1)
t goes from zero to 1 across the scanline.  (Although that's not the case when the poly has been clipped somewhere).  If you were to do this for u,v interp.  You would take the difference in u and v across the scanline.  DO NOT DIVIDE!  These differences would be multiplied by the current value for f(t) in the scanline.  The result is added to the starting (u,v).  STARTING values, not CURRENT values.  I've worked out most everything so that you can do the same thing w/ index interpolation.  It looks as if it will be the exact same algorithm.  I have only one problem to hurdle over and it regards that very last pixel in the scanline.

Don't expect to wait long on the solution.   (To speed freaks : Of COURSE f(t) is stored in a table).  NOTE to all those real nit-picky mathematicians -- a Hyperbolic interp is not REALLY 100% correct, but in the discretised world of raster displays, it certainly IS.  The differences start to be really noticable at really high resolutions like 1280x1024+.  Try out your FFT's on the two functions at integer increments...  Bear in mind that we also have to round these things to integer values in order to display them -- you'll find that they work out exactly the same.


People are stupid.


C.P.I. / ASMiNC

Parashar Krishnamachari