DirectXGraphics:
Cubic Terrain Patches
Author:
Jack Hoxley
Written: 10th May 2002
Contact: [Email]
Download: GR_Cubic.Zip
(138kb)
Contents
of this lesson
1. Introduction
2. The Cubic Equations
1. Introduction
Welcome to
another extended DirectXGraphics article. This
isn't going to be a tutorial as such, more of a
coveringnote for the downloadable source code.
I have a
considerable interest in terrain modeling, and
often read articles/whitepapers on the subject.
One area that crops up every so often is the use
of quadratic/cubic/quartic/quintic patches to
approximate an area of terrain. There are many
advantages to this  the mathematical nature of
the terrain makes it easy to implement LOD (Level
Of Detail) algorithms, and it also provides nice
results :)
So, just for fun
I decided to reread several articles that I found
and see if I could get it working in VB, and the
fact that you're now reading this text shows that
I managed to do it  and maybe you'd be interested
in seeing how it all works!
The
following 6 pictures show (in wireframe and solid
forms) what the results are, the LOD is scalar, so
the higher it is the smoother the terrain (but the
more triangles / slower it gets).
Above and below: The
lowest (0) possible setting
Above and Below: A
low setting, but starting to look better!
Above and Below: A
high resolution render, note very smooth :)
2. The Cubic
Equations
The equations
used to generate these "patches" are
quite simple if you're good at math's, but if
you're not familiar with parametric equations
you'll need to do some research before continuing
(I don't have the time to teach/explain them
properly!)
First we take the
simple linear equation:
(A+B)=1
where A is the distance from the start (0.0 to
1.0) and B is the distance from the end (0.0 to
1.0). This basically expands to:
A + t(BA)
with a little work.
We can then
extend this to be "to the power n"  2
(Quadratic), 3 (Cubic), 4 (Quartic), 5 (Quintic).
When we raise it to one of these powers we need to
multiply out the brackets, which gives us the
polynomial to power n. For example:
(A+B)^{2}
= A^{2} + 2AB + B^{2}
(A+B)^{3} = A^{3} + 3A^{2}B
+ 3AB^{2} + B^{3}
(A+B)^{4} = A^{4} + 4A^{3}B
+ 6A^{2}B^{2} + 4AB^{3} +
B^{4}
(A+B)^{5} = A^{5} + 5A^{4}B
+ 10A^{2}B^{3} + 5AB^{4} +
B^{5}
I'm going to
focus on the cubic equation, but you can easily
work out the other versions if you really want
them...
if we take A and
B to be the distances along the line, we need to
express them as one parameter (so we can get an
f(t) formatted function). using the linear
equation above:
(A+B)^{3} = 1
'cuberoot both sides
(A+B) = 1
'cube root of 1 is still 1
B =
1A
'rearrange for B
if we now
substitute this into the main cubic equation:
A^{3} +
3A^{2}(1A) + 3A(1A)^{2} + (1A)^{3}
don't simplify it
yet, as all you'll do is prove that 1=1 or 0=0 :)
to control our
curve we're going to add a coefficient to each
term of the equation and consider them to be
"control points"  these are additional
3D points that will "guide" the curve
accordingly. I will use lower case letters a, b,
c, d (don't muddle these with A and B).
aA^{3} +
b3A^{2}(1A) + c3A(1A)^{2} +
d(1A)^{3}
as it stands,
with parameter A being in the range 0<=A<=1,
control point 'a' is the start of the line
(A=0.0), 'd' is the end of the line (A=1.0) and
points 'b' and 'c' are just used to guide the
curve (the curve wont actually pass through these
points).
We can now expand
these into the final parametric equations:
X(A) = a_{x}A^{3}
+ b_{x}3A^{2}(1A) + c_{x}3A(1A)^{2}
+ d_{x}(1A)^{3}
Y(A) = a_{y}A^{3} + b_{y}3A^{2}(1A)
+ c_{y}3A(1A)^{2} + d_{y}(1A)^{3}
Z(A) = a_{z}A^{3} + b_{z}3A^{2}(1A)
+ c_{z}3A(1A)^{2} + d_{z}(1A)^{3}
^{These
equations will work perfectly for drawing a line
between 'a' and 'd' influenced by 'c' and 'd'}
An example of a cubic spline
Okay, we now need
to expand this to cover a 2D patch, where we pass
in an x and y value, and we get the
"height" at the given point (this is the
equation used to generate the meshes shown above).
(A+B)^{3}•(C+D)^{3}=1
basically, we
just multiply the two curves, and we'll get the
desired result!
(A^{3} +
3A^{2}B + 3AB^{2} + B^{3})•(A^{3}
+ 3A^{2}B + 3AB^{2} + B^{3})
I'll just jump to
the full parametric equations, feel free to do the
workingthrough if you want!
X(a,c) = A_{x}a³c³
+ B_{x}3a³c²(1c) + C_{x}3a³c(1c)²
+ D_{x}a³(1c)³ + E_{x}3a²(1a)c³
+
F_{x}9a²(1a)c²(1c) + G_{x}9a²(1a)c(1c)²
+ H_{x}3a²(1a)(1c)³ + I_{x}3a(1a)²c³
+
J_{x}9a(1a)²c²(1c)
+ K_{x}9a(1a)²c(1c)²
+ L_{x}3a(1a)²(1c)³ +
M_{x}(1a)³c³
+ N_{x}3(1a)³c²(1c)
+ O_{x}3(1a)³c(1c)²
+ P_{x}(1a)³(1c)³
Y(a,c) = A_{y}a³c³
+ B_{y}3a³c²(1c) + C_{y}3a³c(1c)²
+ D_{y}a³(1c)³ + E_{y}3a²(1a)c³
+
F_{y}9a²(1a)c²(1c) + G_{y}9a²(1a)c(1c)²
+ H_{y}3a²(1a)(1c)³ + I_{y}3a(1a)²c³
+
J_{y}9a(1a)²c²(1c)
+ K_{y}9a(1a)²c(1c)²
+ L_{y}3a(1a)²(1c)³ +
M_{y}(1a)³c³
+ N_{y}3(1a)³c²(1c)
+ O_{y}3(1a)³c(1c)²
+ P_{y}(1a)³(1c)³
Z(a,c) = A_{z}a³c³
+ B_{z}3a³c²(1c) + C_{z}3a³c(1c)²
+ D_{z}a³(1c)³ + E_{z}3a²(1a)c³
+
F_{z}9a²(1a)c²(1c) + G_{z}9a²(1a)c(1c)²
+ H_{z}3a²(1a)(1c)³ + I_{z}3a(1a)²c³
+
J_{z}9a(1a)²c²(1c)
+ K_{z}9a(1a)²c(1c)²
+ L_{z}3a(1a)²(1c)³ +
M_{z}(1a)³c³
+ N_{z}3(1a)³c²(1c)
+ O_{z}3(1a)³c(1c)²
+ P_{z}(1a)³(1c)³
That's the math's
behind the cubicpatch, you'll have to read
through the source code in order to understand it
fully.
As a final note,
whilst all the source code is written by me, the
math's/theory is based on the work featured in
several articles on www.GameDev.Net
(amongst other sites).
You
can download the source code from the top of the
page, or from the downloads
page.
AMENDMENT:
I've added an nth degree polynomial version for
download, meaning you can test quadratic/quartic/quintic
(or any other value for n). you can download it here
(315kb)
