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 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.
Parashar Krishnamachari