Parabolic Curves And Fake-G
Introduction
One of the most useful methods for programmers these days, considering the CPU over memory speed advantage, is interpolation. It has been the craze amongst the demo/3D coding community for a number of years. In fact most programmers were using interpolation without even knowning about it.
Perhaps the strongest reason for employing it in your code is that of its ability to give an infinite resolution to any interval between any two points or values. Almost everyone has seen a fractal zoom, filled polygon objects, or basic 1-pixel wide lines, you may have even heard interpolation in the form of a sample player/tracker.
The motive behind this article is to get away from all but the most primative mathematics and explain how even on a stone age CPU (like the Z80 or 6502) it is possible to use interpolation or binary sub-division to create reasonably looking curves. This simplistic approach will hopefully give newbie coders a first step into this subject without being confronted by a mountain of technical terms or difficult maths.
What's Interpolation?
Interpolation is the method by which value are calculated between a number of known end points. These end points could for example be the (X,Y) co-ordinates of a straight line, or two neighbouring samples of a sound.
But why calculate these values when we could store them?
Well, because on modern CPUs the trend seems to be more one of CPU power in terms of instruction execution speed than of memory access speed. Memory accessing still seems to be far behind instruction performance, and so calculating values can often be much more efficient than using a table of data values. In the old days this was the complete reverse, so back then code would be unrolled hundreds or thousands of times, or vast tables were used because the instruction execution (including the instruction fetch from memory) was slower than simply using a table.
It seems that until memory can compete with the CPU for speed, real-time calculation will continue to be the fastest method for most things. As most CPUs have a reasonable amount of cache the instruction usually don't need to be re-fetched from memory as they are already held in it.
A good reason for using calculation is that tables of any reasonable resolution needs a large amount of memory, and calculations do not require any initialisation code, or CPU time.
Linear Interpolation.
The name itself implies, a "linear" (straight-line) interpolation. In short a constant slope between the two end-points is used to calculate the desired value at a certain point. If you have ever written a line drawing, polygon drawing or a scaling function/routine then you have probably used linear interpolation or something like it without knowing. You have no doubt used them in maths at school or in technical drawing when scaling the points from one line onto another. The words "similar triangles" spring to mind.
The only formula I have seen used terms like F[a1], F[a2], a1 and a2, but personally I found this confusing.
Anyway here is that formula:
F[C] = F[a1] + (F[a2]-F[a2]) * (C-a1) / (a2-a1)
This interpolates the value C that lies in the interval [a1...a2].
I think this looks a bit ugly, so I will use some 2D co-ordinates such as (x1,y1) and (x2,y2) instead, where the X axis is the input value given to the function F, and the Y axis is the value returned by the function F. The variable C is the position within the interval at which we want to interpolate.
Using a nice ASCII diagram should hopefully make everything much clearer (well, as clear as ASCII can be).
(x2,y2)
o
---.
--- .
--- .
--- .
-o- . ^
--- . . ³
--- . . K
--- . . ³
--- . . ³
(x1,y1) o............................ Á
Ã----- C ----->
K = y1 + ( C * (y2 - y1) / (x2 - x1) )
The value K is the what we want to find within the interval x1...x2 using the variable C.
The above method is normally used in line clipping algorithms to find the intersection point of a line against a screen edge.
The problem with linear interpolation is that it is, er... linear. When used for large areas with many interpolations the results isn't too good, it looks flat so isn't too convincing when used to approximate curved objects and surfaces. If it was used for shading then you would have a stair-case effect where step would be the same size as every other one.
Non-Linear interpolation (or "fake-G")
It would be far better to use some form of curve to draw objects or shading, this would be more realistic than a linear interpolation.
Now the problem is finding a very quick way to calculate curves in the small amount of code and time.
One of the most basic (and so, quickest) forms of curve is a parabolic one. Think of the way that a ball travels as it is affected by gravity. Gravity is simply a change of speed over time.
I will give some QBASIC code here, although it's such an easy technique that you probably don't need it.
screen 12 <--- any screen mode will do.
y = 0
speed = 1
for x = 0 to 100
pset (x, y)
y = y + speed
next x
Now ground breaking I know, but we're only using 1 ADD per iteration.
Now as gravity affects speed over time, let's use a 2nd increment.
screen 12
y = 0
speed = 1
accel = 0.01
for x = 0 to 100
pset (x, y)
speed = speed + accel
y = y + speed
next x
So we have incremented the increment, and we get a parabolic curve. I know it's a cheesy method but it only takes 2 ADDs per iteration.
The Parabolic Curve.
The formula for a parabolic curve is this:
x^2 = 4ay
rearrange for y:
y = x^2 / 4a
and here is the "fake-G" loop:
a = 2
screen 12
y = 0
speed = 0
accel = 1 / 2*a
for x = 1 to 100
pset (x, y)
speed = speed + accel
y = y + accel
next x
The problem with this (and all other) incremental methods is that they can suffer from accumulative errors. This happens when a fration can not be represented with total accuracy so some small amount of error creeps into the increment value. Now if this value is used for very large areas with many iterations then the errors can grow very large. This can be reduced using a greater precision or by recalculating at the mid-point.
The "accel" fraction seems to be a reciprocal half of the 4a term in the formula x^2 = 4ay. I haven't looked into this yet, but parabolic curves seem to be a little like square roots or other exponeal functions, they grow faster and faster over time.
Closing Words
I've seen a brief mention of "QUAD-ADDERS" and the Imphobia 10 magazine which I believe had an article about parabolic curves. I have NOT seen this article and all of the above was done after seeing the phrase:
".... it only takes 2 ADDs per pixel !!!"
That certainly got my attention so I thought about how to draw curves quickly and came up with the "fake-G" idea above. If you are serious about the subject then I surgess trying to find the Imphobia 10 magazine and the article in question.
Enjoy.
Regards