## 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);     glLoadIdentity();     gluOrtho2D(0, width, 0, height);          glMatrixMode(GL_MODELVIEW);     glLoadIdentity(); } 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)