## Fractal Terrain

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
I'm trying to learn how to do fractal terrain generation <-LINK but I can't figure out how to implement it. I understand the math of the algorithm and even how to loop through the values, but I'm not sure how to code it. I thought about using an NSBezierPath, but couldn't figure out how to add points to the center of a line. I want to figure out how to do it in C/C++ for my "engine", but any language works I suppose. Has anyone done this before and can lend some advice?
Moderator
Posts: 869
Joined: 2003.01
Post: #2
For the creation of planetary terrain, I use 3D perlin noise to generate a fractal climate model (rain, temp, altitude), and then apply a set of curves to determine the terrain type based on the climate. Looks like this:

and the controls:

The triangle mesh itself is generated using a variation of ROAM. ROAM is only partially suited to real-time LOD, as it has a quite high CPU load, but it can be used to efficiently pre-generate a very good mesh.

You can apply the same principles to flat terrain, only you need 2D perlin noise and a flat mesh.
Member
Posts: 41
Joined: 2006.01
Post: #3
Doing an entire planet is difficult because the coordinate system gets complicated. If you can stick to a bounded flat area, it's much easier. There's no need to use nurbs or beziers. Any deterministic random can be used, and up-ressing the patch by taking midpoints isn't that hard, just code it.

Avoid:
- doing a whole globe
- attempting to evaluate the terrain in real time (though it is doable)
- rivers, lakes and real erosion (this is very hard)

These are bare-bones gouraud images with a primitive tree, ellipse frustrum.
The planet is a real-time Earth sized fractal sphere.
27.8ms on a 450MHz G4.
Moderator
Posts: 102
Joined: 2003.07
Post: #4
wow, those demos look pretty nice... do you have the programs on your respective websites so maybe we can mess with them a bit?

-CarbonX
Member
Posts: 715
Joined: 2003.04
Post: #5
Wow looking at this stuff puny humans can do, I just get awestruck at what a few billion years of evolution might allow a species to achieve.

Somewhere out in the universe is a website called "idevCosmos.com", and someone is posting about the bugs in Earth .034 beta release.
Sage
Posts: 1,403
Joined: 2005.07
Post: #6
Chris Ball that is a very cool way to draw map is definitly reducing the stetch marks you can get from a low res texture using a more simple mapping, is there a name for it?

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Sage
Posts: 1,066
Joined: 2004.07
Post: #7
I just revisited the website (http://www.gameprogrammer.com/fractal.html) and figured out that an STL list class would work perfectly. I set out in GLUT to implement this and have some success. My only problem is that after about 3 recursions, I can't see the difference. Is it a problem in my code or a natural glitch of the algoritm? Here's the full source to my program:
Code:
//g++ main.cpp -framework GLUT -framework OpenGL -framework Cocoa

#include <GLUT/glut.h>
#include <OpenGL/gl.h>
#include <OpenGL/glu.h>
#include <list>
#include <math.h>
#include <time.h>

using std::list;

class Point
{
public:
Point():x(0),y(0) {}
Point(float a, float b):x(a),y(b) {}

float x, y;

void Normalize()
{
float mag = 1 / sqrt(x*x+y*y);
x *= mag;
y *= mag;
}

void operator=(Point a)
{
x = a.x;
y = a.y;
}

void operator+=(Point a)
{
x += a.x;
y += a.y;
}

void operator-=(Point a)
{
x -= a.x;
y -= a.y;
}

Point operator-(Point a)
{
Point r;
r.x = x - a.x;
r.y = y - a.y;
return r;
}

Point operator+(Point a)
{
Point r;
r.x = x + a.x;
r.y = y + a.y;
return r;
}

Point operator*(float a)
{
Point r;
r.x = x * a;
r.y = y * a;
return r;
}

void operator*=(float a)
{
x *= a;
y *= a;
}
};

float Distance(Point a, Point b)
{
return (sqrt(pow(a.x - b.x, 2) +
pow(a.y - b.y, 2)));
}

list <Point> points;
float changeAmount = 200;

void display()
{
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

list<Point>::const_iterator iter;

glColor3f(0,1,0);
glBegin(GL_LINE_STRIP);
for(iter = points.begin(); iter != points.end(); iter++)
glVertex2f((*iter).x, (*iter).y);
glEnd();

glutSwapBuffers();
}

void reshape(int width, int height)
{
glViewport(0, 0, width, height);

glMatrixMode(GL_PROJECTION);
gluOrtho2D(0, width, 0, height);

glMatrixMode(GL_MODELVIEW);
}

void idle()
{
glutPostRedisplay();
}

void keyboard(unsigned char key, int x, int y)
{
if(key == 'a')
{
//perform single recursion on line
list<Point>::iterator itr, itr2;
Point start, end, slope, mid;
float distance, frandom;
int random;
itr = points.begin();
itr2 = points.begin();
for(itr++; itr != points.end(); itr++, itr2++)
{
//first we must get the height of the halfway point.
//our iterator points to the position of the vertex
//on the right side. so itr-1 is the position of the
//vertex on the left side. we must then find a slope
//and use the equation of a line to find the midpoint.
end = (*itr);
start = (*itr2);
slope = end - start;
slope.Normalize();
distance = Distance(end, start);
mid = end - (slope * (.5 * distance));
random = (rand() % 201) - 100;
frandom = (float)random / 100;
mid.y += frandom * changeAmount;
itr2 = points.insert(itr, Point(mid.x, mid.y));
changeAmount *= .5;
}
}

else if(key == 'r')
{
//reset the line
points.clear();
points.push_back(Point(20, 200));
points.push_back(Point(780, 200));
changeAmount = 100;
}
}

int main(int argc, char *argv[])
{
glutInit(&argc, argv);

glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE | GLUT_DEPTH);
glutInitWindowSize(800,600);
glutCreateWindow("Testing");

glutDisplayFunc(display);
glutReshapeFunc(reshape);
glutIdleFunc(idle);
glutKeyboardFunc(keyboard);

glEnable(GL_DEPTH_TEST);
glEnable(GL_POLYGON_SMOOTH);
glEnable(GL_LINE_SMOOTH);
glEnable(GL_POINT_SMOOTH);

points.push_back(Point(20, 200));
points.push_back(Point(780, 200));

srand(time(NULL));

glutMainLoop();

return 0;
}
Sage
Posts: 1,066
Joined: 2004.07
Post: #8
Figured out my mistake. I'm lowering the change amount during each iteration of the list, not once per recursion. My bad.

(Oh, and sorry if my terms are a bit off as far as iteration and recursion. I think those are the right words, but it's late and I'm just learning these things)