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?
Quote this message in a reply
DoG
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:
[Image: pp-display.png]

and the controls:
[Image: pp-settings.png]

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.
Quote this message in a reply
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)

[Image: aworld9gd.jpg]

[Image: picture16xj.jpg]
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.
Quote this message in a reply
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
Quote this message in a reply
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.
Quote this message in a reply
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!
Quote this message in a 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;
}
Quote this message in a reply
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)
Quote this message in a reply
Post Reply