Interesting terrain generation procedures

Found this at Outerra forums: Artificial Terrain Generation. It even covers spherical planets!

Ooooooooo~.....

How nice looking. Everything on this page looks like it could definitely be of some use, as it covers
basically every department that we need to work on. :3


And also, someone seems to be developing a very ambitious project with this same technology and it looks
like it could contribute to our "space phase"....


http://www.infinity-universe.com/Infinity/index.php?option=com_content&task=view&id=12&Itemid=33

I like the resized hemisphere one.. It may even work within a simple latlon sphere. We wouldn't have strange bumps at the top.. Lemme think about this.

That's a very helpful link, and it covers just about everything we need to implement. Excellent find!

SIGGRAPH man, SIGGRAPH. It is the biggest computer graphics journal out there, and often some of its papers are free! Google for it and go sniffin' on the database

the link wont load ?

Was working just a few days ago. The basic VTP link is still working though.

Code:

i = 0;
for(x in 0 to xcount)
  for(y in 0 to ycount)
  {
    addvertex(x * cellwidth, y * cellwidth)

    if(x < (xcount - 1) and y < (ycount - 1))
    {
      addtriangle(i, i + 1, i + xcount)
      addtriangle(i, i + xcount, i + xcount + 1)
    }
  }

Something like this should suffice for a terrain generator. Amiright?

Believable terrains will need fractal erosion and snow deposition as well as pretty complex landmasses, but that's something for later. For now, simple perlin should be fine.

Commander Keen wrote:

Believable terrains will need fractal erosion and snow deposition as well as pretty complex landmasses, but that's something for later. For now, simple perlin should be fine.

That's for dynamic planets, which we'll cover later.

AIs-null wrote:

Code:

i = 0;
for(x in 0 to xcount)
  for(y in 0 to ycount)
  {
    addvertex(x * cellwidth, y * cellwidth)

    if(x < (xcount - 1) and y < (ycount - 1))
    {
      addtriangle(i, i + 1, i + xcount)
      addtriangle(i, i + xcount, i + xcount + 1)
    }
  }

Something like this should suffice for a terrain generator. Amiright?

The problem is, we not only have to wrap that around into a sphere, but apply seamless perlin noise to it as well. That means we have to somehow find a way to avoid artifacts at the top. We also need to have a way to LOD the terrain.

EDIT: libnoise works great for perlin noise, that's not the issue.

My idea is to use 3D perlin noise after generating a sphere. We then plug each cartesian (not spherical) coordinate into a 3D perlin noise function. Each value is then used to move that point further or closer to the center of the sphere, creating a seamless heightmap. Unfortunately, hangovers are a no-go with this method. (which probably isn't an issue)

roadkillguy wrote:

AIs-null wrote:

Code:

i = 0;
for(x in 0 to xcount)
  for(y in 0 to ycount)
  {
    addvertex(x * cellwidth, y * cellwidth)

    if(x < (xcount - 1) and y < (ycount - 1))
    {
      addtriangle(i, i + 1, i + xcount)
      addtriangle(i, i + xcount, i + xcount + 1)
    }
  }

Something like this should suffice for a terrain generator. Amiright?

The problem is, we not only have to wrap that around into a sphere, but apply seamless perlin noise to it as well. That means we have to somehow find a way to avoid artifacts at the top. We also need to have a way to LOD the terrain.

EDIT: libnoise works great for perlin noise, that's not the issue.

My idea is to use 3D perlin noise after generating a sphere. We then plug each cartesian (not spherical) coordinate into a 3D perlin noise function. Each value is then used to move that point further or closer to the center of the sphere, creating a seamless heightmap. Unfortunately, hangovers are a no-go with this method. (which probably isn't an issue)

Hangovers and caves can be added in with boolean operations and populated after the initial heightmap.

How? How will the vertices be displaced? Were talking low level opengl calls here.

I belive we have no other option than having caves (and equal) to be independant 3d objects then?

I suppose caves would have to be independent. I'm no expert on programming in OpenGL, I just assumed you could intersect meshes and delete unnecessary parts to make the caves.

Mesh intersection.. you'd have to have an equation governing each cave.. other than that I have no Idea.

I've written some code!

EDIT: I found the code box.

Node.cpp:

Code:

#include "Node.h"

using namespace std;

Node::Node(int _levels, int _size)
{
   m_level = _levels;
   m_size = _size;
   
   m_active = false;
   
   m_data = 0;
   
   if(m_level > 1)
   {
      m_a = new Node(m_level - 1, m_size);
      m_b = new Node(m_level - 1, m_size);
      m_c = new Node(m_level - 1, m_size);
      m_d = new Node(m_level - 1, m_size);
      
      m_leaf = false;
   }
   else
   {
      m_a = 0;
      m_b = 0;
      m_c = 0;
      m_d = 0;
      
      m_leaf = true;
   }
   
   //cout << "Node created at level " << m_level << endl;
}

void Node::setActive(bool _active)
{
   int i, j;
   
   if(_active)
   {
      m_data = new float * [m_size];
      for(i = 0;i < m_size;i ++)
      {
         m_data[i] = new float [m_size];
         for(j = 0;j < m_size;j ++)
         {
            m_data[i][j] = 0;  //OR WHATEVER THE VALUE SHOULD BE
         }
      }
   }
   else
   {
      for(i = 0;i < m_size;i ++)
      {
         delete [] m_data[i];
      }
      delete [] m_data;
   }
   
   m_active = _active;
}

Terrain.cpp

Code:

#include "Terrain.h"

using namespace std;

Terrain::Terrain(int _levels, int _nodeSize) //_levels SHOULDN'T BE LESS THAN 1
{
   m_levels = _levels;
   m_nodeSize = _nodeSize;
   
   int leafNum = pow(4, m_levels - 1);
   
   m_size = sqrt(leafNum)*_nodeSize;
   
   m_activeNodeList = new Node * [leafNum];
   
   m_node = new Node(m_levels, _nodeSize);
   
   cout << "There are " << leafNum << " leaves in this terrain (" << sqrt(leafNum) << "x" << sqrt(leafNum) << ") with " << leafNum*_nodeSize*_nodeSize << " data values (" << m_size << "x" << m_size << ") (" << _nodeSize << "x" << _nodeSize << " per leaf)" << endl;
}

void Terrain::UpdateLOD(float _x, float _y, float _depth)
{
   
}

Main.cpp

Code:

#include <iostream>

#include "Terrain.h"

using namespace std;

int main(int _argc, char ** _argv)
{
   Terrain * terrain = new Terrain(8, 8);
   
   return 0;
}

(Assume Node.h and Terrain.h are valid headers)

This is great because.. well it's the data structure for 2D LOD(Level of detail) terrain.

Once a node is created, it is assigned how many more levels of nodes it will, in turn, create. When a node is activated it will initialize it's memory and when it's deactivated, it will delete it's memory, thus conserving RAM --which is essentially the point of LOD. The m_data array contains the list of heights from the average altitude for every vertex on the planet.

The terrain class is essentially a container class for nodes, that contains a list of every possible leaf, as well as some other functions for operating on said node.

If you noticed, the terrain class has an empty function. That's the function that will update which nodes are currently visible/activated. I'm not sure what needs to happen at this point; I'm still thinking of loops and linear functions right now.

In the end, with 8 node levels (layers of subdivision) and 8 vertices per node, it outputs:
There are 16384 leaves in this terrain (128x128) with 1048576 data values (1024x1024) (8x8 per leaf)

Which should give you an idea of just how much memory is used in this data tree.

1048576 floats is 1048576*4 = 4 194 304 bytes of memory. This is for just one of 6 2D faces of the radiated cube. (It's not technically much, but a floating point value may be the wrong datatype to use for the data itself)

Anyway, it's a step in the right direction for terrain that looks like this.

Awwh It's a pain in the...to read Code in non code boxes

Anyways, it looks good. I can't seem to remember what it was called, but it was a method used to hide vertices not shown on screen and just store them on your harddrive instead. That is what you need to put in

Code:

void Terrain::UpdateLOD(float _x, float _y, float _depth)
{
    HERE
  }

Once a terrain is generated, it would need to be stored somewere, and not just erased afterwards so that you can go back and re-visit that area.

I'll get back to this once I can get some sleep...

Terrain - great. Suitably rough when zoomed into, smooths out decently from afar.

AIs-null wrote:

Awwh It's a pain in the...to read Code in non code boxes

Anyways, it looks good. I can't seem to remember what it was called, but it was a method used to hide vertices not shown on screen and just store them on your harddrive instead. That is what you need to put in

Code:

void Terrain::UpdateLOD(float _x, float _y, float _depth)
{
    HERE
  }

Once a terrain is generated, it would need to be stored somewere, and not just erased afterwards so that you can go back and re-visit that area.

I'll get back to this once I can get some sleep...

I realize that. Would passing around a file pointer be too slow?

roadkillguy wrote:

I realize that. Would passing around a file pointer be too slow?

Now I remember, Occlusion Culling.
https://www.youtube.com/watch?v=fU2L7IdYDVc

It's your choice, so you can try it?

Occlusion culling is hardcore.. I've got no idea where to start to make it that fast.

LOD is well, Level of Detail, so the terrain will use more or less vertices depending on how close you are to the object.


I've also come up with a solution to the empty function by placing updateLOD on the node, rather than the terrain. I'm about to put it into code.

How about Face Culling?

Anyways maybe it is more clever to not worry about this right now.

Face culling isn't very much faster due to the fact that you still iterate through those vertices. It's very easy to enable, and requires no other math.

Code:

void Node::updateLOD(float _x, float _y, float _depth)
{
   if(!m_leaf)
   {
      float dist = sqrt(_x*_x + _y*_y);
      
      cout << "x: " << _x << ", y: " << _y << endl;
      
      float level = dist/LEVEL_THRESHOLD + 1;
      
      cout << "dist: " << dist << endl;
      
      cout << "level: " << level << endl;
      
      cout << "m_level: " << m_level << endl;
      
      cout << "depth: " << _depth << endl;
      
      //ENFORCE THE DEPTH
      if(level < _depth)
      {
         level = _depth;
      }
      
      //IF THIS LEVEL IS DEEPER THAN OUR LEVEL
      if(level < m_level)
      {
         setActive(false);
         
         getNodeA()->updateLOD(-m_width/4 - _x, -m_width/4 - _y, _depth);
         cout << " on A" << endl;
         getNodeB()->updateLOD(m_width/4 - _x, -m_width/4 - _y, _depth);
         cout << " on B" << endl;
         getNodeC()->updateLOD(-m_width/4 - _x, m_width/4 - _y, _depth);
         cout << " on C" << endl;
         getNodeD()->updateLOD(m_width/4 - _x, m_width/4 - _y, _depth);
         cout << " on D" << endl;
      }
      else
      {
         setActive(true);
      }
   }
   else
   {
      setActive(true);
   }
}

This function will hand down the distance relative to each node throughout the node tree, and toggle them displayed or not based on the distance.

The only problem is, I no longer have a way of keeping track of an active node list in my terrain class.

roadkillguy wrote:

Occlusion culling is hardcore.. I've got no idea where to start to make it that fast.

LOD is well, Level of Detail, so the terrain will use more or less vertices depending on how close you are to the object.


I've also come up with a solution to the empty function by placing updateLOD on the node, rather than the terrain. I'm about to put it into code.

What kind of scale is LOD generally done on? (logarithmic or linear)