HYPERBOLIC MAPPING, complete explanation
Jan Vondrak
description of my implementation of 'hyperbolic mapping'.
The examples are in C, and I leave the conversion to assembly
to you, as well as some obvious optimizations (array walks
=> pointer walks, etc.). The purpose of this article is
to explain the basic idea and to suggest the solution of
some problems associated with this method.
First, I'll summarize our task:
We want to render one scan-line of a texture-mapped polygon,
i.e. a row of pixels from [x1;y] to [x2;y] (x1 included, x2 not).
For each pixel [x;y], we need to get the appropriate texel [u;v].
If the texture coordinates are linear functions in the polygon
plane (even if their gradients are not perpendicular, which
means you are not limited to square texels), they depend on x
(for a constant y) like this:
A * x + B
u(x) = -----------
C * x + D
E * x + F
v(x) = -----------
G * x + H
It is outside the scope of this article to derive these formulae,
or to explain the meaning of A,B,C,D,E,F,G,H, but I think enough
has been said about this already. The denominators are actually
equal (C = G, D = H), but I will denote them separately, because
they will be modified independently later.
Now, we'd like to acquire the values of u,v for every x from x1
to x2, but it's clear that calculating every single value from
scratch is not exactly the best thing to do. Rather, we would
like to use the information that the results for adjacent
pixels are relatively close to each other. (This may not be
exactly true, but for now let's suppose this is the case).
Moreover, we don't even need to calculate u, v precisely -
we just need an integer value (a texture bitmap index).
Now take a look at the equations above. They involve a division,
which is too bad. But we can get rid of that easily:
p(x,u) = (A * x + B) - (C * x + D) * u = 0
q(x,v) = (E * x + F) - (G * x + H) * v = 0
This is an equivalent set of equations, defining u,v implicitly.
It is not suitable for calculating u, v directly, but remember
we know what the values were in the previous pixel. If x has
increased by 1, the function which was equal to 0 is not 0 anymore.
To put it back to 0, we have to adjust u or v appropriately.
We won't probably make it exactly zero, because we can only change
u,v by discrete increments, but that's not our goal anyway.
To clear up the situation, let's adjust the constants A,B,C,D,
E,F,G,H so that A*x+B > 0, E*x+F > 0 (we may change the signs
of A,B,C,D or E,F,G,H without changing the result), and then
determine the direction in which u, v should move:
ustep, vstep = +1 or -1, so that
(C*x+D)*ustep > 0, (G*x+H)*vstep > 0.
This way, increasing x will increase p(x,u), q(x,v) and
advancing u,v by their respective increments will decrease
p(x,u), q(x,v). The algorithm is obvious: stepping 1 pixel
to the right will increase p(x,u). If p(x,u) is still negative,
nothing happens. If it is positive, it means we must advance u;
and we will do it as long as p(x,u) is above zero. Same way
with v and q(x,v). However, we must be careful. How does this
method round our u,v coordinates ? When p(x,u) drops below zero,
it means we've just passed the precise value. The value we have
at this moment is rounded in the direction of ustep, sometimes
up and sometimes down. But we'd like to have a consistent
rounding convention, for example 'always down'. We could have
a special loop for positive and negative directions, but it's
easier to tweak the starting values. If ustep (or vstep) is
positive, we will decrease u (or v) by 1.
( Warning! This is the only moment when we modify u, v and
not p(x,u), q(x,v). Otherwise, every change of u, v must be
followed by a corresponding update of p(x,u), q(x,v)! )
Now we are very close to our first actual implementation.
The tricky part is to update the functions p(x,u), q(x,v)
using only addition and subtraction. To achieve this,
we'll have to keep some auxiliary variables:
Name Meaning Value
-----------------------------------------------------------
p_xstep change of p at x++ A - C*u
p_ustep change of p at u+=ustep -ustep*(C*x + D)
p_xstep_ustep change of p_xstep at ustep -ustep*C
p_ustep_xstep change of p_ustep at x++ -ustep*C
q_xstep change of q at x++ E - G*v
q_vstep change of q at v+=vstep -vstep*(G*x + H)
q_xstep_vstep change of q_xstep at vstep -vstep*G
q_vstep_xstep change of q_vstep at x++ -vstep*G
The combined 'advances of advances' have the same values,
so we can keep them each pair in one variable, with a little
confusing names: 'p_step_step' and 'q_step_step'.
The rendering loop will look like this:
for (x=x1;x<x2;x++)
{
putpixel (x,y,texture[v][u]);
p += p_xstep;
p_ustep += p_step_step;
while (p > 0)
{
u += ustep;
p += p_ustep;
p_xstep += p_step_step;
}
q += q_xstep;
q_vstep += p_step_step;
while (q > 0)
{
v += vstep;
q += q_vstep;
q_xstep += q_step_step;
}
}
Now we have a mapper which doesn't contain any multiplication
or division and it is very accurate. But can we rest in peace ?
Not yet ! Imagine what happens if the difference between adjacent
pixels is more than 1 texel: the 'while (p>0) { ... }' loop will
repeat twice, thrice, or even more. That's something we must avoid
at any rate. Nevertheless, we have to skip more 1 texel somehow,
and quickly. So what we'll do is: double ustep (or vstep), and
double all the advances associated with ustep (vstep), too.
And how do we know it's time to double the advances ? Easy:
if the loop executes once and the loop condition still holds,
it means the step is not big enough to skip the distance we need,
and we must double it.
for (x=x1;x<x2;x++)
{
putpixel (x,y,texture[v][u]);
p += p_xstep;
p_ustep += p_step_step;
while (p > 0)
{
u += ustep;
p += p_ustep;
p_xstep += p_step_step;
if (p > 0)
{
ustep <<= 1;
p_ustep <<= 1;
p_step_step <<= 1;
}
}
q += q_xstep;
q_vstep += p_step_step;
while (q > 0)
{
v += vstep;
q += q_vstep;
q_xstep += q_step_step;
if (q > 0)
{
vstep <<= 1;
q_vstep <<= 1;
q_step_step <<= 1;
}
}
}
This runs really fast. The advancing loops will not repeat more
than once on average; even if the starting advance is too big,
doubling the steps will quickly adapt them to the appropriate
value. But still, there's one more obstacle ! (This time
I promise it's the last one). What if the scan-line starts
at the far end of the polygon ? As we move along the scan line,
the advances get smaller and smaller. And our loop, it can only
increase its advances. It won't get slower, but the results
will be downright nasty. The loop will skip 8 or 16 texels,
then sleep for the next 10 pixels, then jump again ...
I've seen it, and it's not a lovely thing to behold.
And the solution ? I guess you should know by now: we'll
decrease the advances, too ! When ? Of course, when the loop
learns it jumps too far and too seldom. If the advancing branch
is not taken twice in a row, it means: either the advance
is too big - then we must halve the advances, or it is 1 texel
- then there's nothing we can do and nothing we should worry
about. We will store the number of not-taken branches
in variables 'p_const_count' and 'q_const_count'. We won't
increase the count if the u, v advance is +1 or -1,
because there's no need to halve advances then.
for (x=x1;x<x2;x++)
{
putpixel (x,y,texture[v][u]);
p += p_xstep;
p_ustep += p_step_step;
if (p <= 0)
{
u_const_count += (ustep & 1) ^ 1;
if (u_const_count >= 2)
{
u_const_count = 0;
ustep >>= 1;
p_ustep >>= 1;
p_step_step >>= 1;
}
}
else {
u_const_count = 0;
for (;;)
{
u += ustep;
p += p_ustep;
p_xstep += p_step_step;
if (p > 0)
{
ustep <<= 1;
p_ustep <<= 1;
p_step_step <<= 1;
}
else break;
}
}
q += q_xstep;
q_vstep += p_step_step;
if (q <= 0)
{
v_const_count += (vstep & 1) ^ 1;
if (v_const_count >= 2)
{
v_const_count = 0;
vstep >>= 1;
q_vstep >>= 1;
q_step_step >>= 1;
}
}
else {
v_const_count = 0;
for (;;)
{
v += vstep;
q += q_vstep;
q_xstep += q_step_step;
if (q > 0)
{
vstep <<= 1;
q_vstep <<= 1;
q_step_step <<= 1;
}
else break;
}
}
}
At last, this is something which deserves to be called
a 'texture mapper'. I agree the code looks frighteningly
complex, but it's the best I can contrive. Also, don't
forget that about half of the code is executed only rarely,
and it contains only simple instructions - add, subtract,
compare, and occasionally some shifting.
Anyway, I'd be glad to hear any ideas how to improve this
technique, or reports on how efficiently you've managed
to implement it.
-- Jan Vondrak
Daniel Goldstein
>
> In response to numerous requests, I have composed a detailed
> description of my implementation of 'hyperbolic mapping'.
>
> a 'texture mapper'. I agree the code looks frighteningly
> complex, but it's the best I can contrive. Also, don't
> forget that about half of the code is executed only rarely,
> and it contains only simple instructions - add, subtract,
> compare, and occasionally some shifting.
>
> Anyway, I'd be glad to hear any ideas how to improve this
> technique, or reports on how efficiently you've managed
> to implement it.
>
> -- Jan Vondrak
Well, for starters how about using a mip-map style algorithm. Instead of
doubling or halving the step rate when necessary, you can change to a
different texture map which represents the texture scaled and
anti-aliased at 1/2x or 1/4x etc normal size. This would make a marked
improvement in image quality, probably even surpassing Quake's level of
detail transitions. I haven't studied it extensively yet, but they are
definitely doing mip-map type operations. They, however, _seem_ to be
doing it on a per polygon basis or something. I could be wrong though.
Other than that, I would suggest trying to table some of the changes in
much the same way as you can set up a two entry bresenham table which
remains in the cache for quick access. This would help eliminate the
comparisons/jumps, replacing them with cached memory accesses. I
personally have not implemented any hyperbolic mapping as you call it,
but I plan to in the near future. I'll post if I get something cool
working.
Oh, one other interesting thing about Quake which I noticed was that the
water and lava 'swirls' were being done in screen-space rather than
texture-space. By this I mean that they are not manipulating the texture
before drawing. Instead they are drawing in some funky sinusoidal
manner. Wonder how they're doing that :) I suppose it is probably a
pretty good clue to how their algorithm works in general.
-Dan Goldstein
Tim Sweeney
to this a few months ago, but dropped it after a few hours
of experimentation because of temporal problems. It produced
great stills, but moving textures jiggled. I might have been
missing something, though. Have you run your texture mapper
at realtime speeds? Does it have this aliasing problem?
-Tim
Jan Vondrak
I have it running very fast. I'm getting 20 cycles per pixel on a 486
as long as no increment adjustments are needed. There's a slowdown,
of course, when the polygon is edge-on and the adjustments occur
too frequently. As regards visual quality, it is pretty flawless
on near polygons; it gets worse when the polygon is far enough
to make the increments double. To avoid this, you can shift the
increment adjustment barrier to a greater distance, for example
doubling the increments only when the advancing loop repeats
three or four times; but it's a speed-for-quality trade-off.
-- Jan Vondrak