Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 


Submitted by Martin Cronje, posted on December 17, 2001




Image Description, by Martin Cronje



This is from a terrain generator that I've been working on in the last couple of weeks. So you may ask what's the big deal? I know there are SEVERAL random terrain generators out there but the problem with them is that they generally cannot generate a full-sized planet. They are generally created on a square or rectangular grid and therefor discontinous at the borders.

So here goes. The way I do it is to generate a sphere from 12 connected pentagons (like a tetrahedron, but with pentagons instead of triangles). This gives me 12*5=60 triangles to work with as a basic sphere. You'll see this in the bottom left picture. I outlined three of the pentagons with red. To increase the poly count in the sphere, I simply split each of these triangles into four additional triangles. The middle and left picture contains 3840 and 61440 polys respectively. This is done blindingly fast and doesn't seem to impact the generation (which I'll get to just now) much. I store the vertices and the triangles in two arrays; the triangles as a triangles list with each triangle having three indices referring to its three vertices PLUS three indices referring to it's neighbouring triangles (might be important for some reason like triangle strips or something). Another reason I used 12 pentagons was to have all of the triangles in the final sphere model almost the same size. Tetrahedrons as base models normally have a wide size range, especially at high triangle counts.

The terrain generation is very simple: I form a random plane at a random distance perpendicular to some random vector eminating from the centre of the sphere. This distance will of course be between 0 and the radius of the sphere. Then I go through the vertex list and determine for each vertex whether the vertex is in front of or behind the plane (simple dot product calculation). The vertices on the one side of the plane is raised whereas those on the other side are left as they are. I say here raised but for every vertex I have also included a height property and this I increase or decrease, I don't actually alter the spatial coordinate of the vertex (this can be done at a later stage). Another thing to keep the continents balanced is that every iteration I change which side of the plane heights are altered, i.e. Iteration 1: front is raised, iteration 2: back is raised, etc. Otherwise you end up with Himalayas on one side of your planet and the Abyss on the other.

The two half-spheres in the top of the picture are the results. You can see that the terrain is continuous all over the surface of the planet. The spheres I used consisted of 245 760 triangles. I ran the program on a PIII 600MHz machine (no 3D yet) for a 1000 iterations (top) and 2000 iterations (bottom). The first terrain took about 4.5 minutes and the second 9 minutes. There seems to be a linear increase in time with an increase in one of the variables (number of polygons and number of iterations). You'll also see that with increasing number of iterations some of the sharp "cliffs" are removed. The smoothness of the terrain will improve with increasing number of iterations.

Possible applications I can think of at the moment would be planet generation for a planet-wide strategy game or something like that. Anyway, if anybody wants the code, just mail me. There's still some minor alterations that I'd like to make and documentation to write. (all code in C++).

Rho


[prev]
Image of the Day Gallery
www.flipcode.com

[next]

 
Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
psykotic

December 17, 2001, 08:17 AM

Nice work. The algorithm for generating the terrain displacements sound exactly like what is described on Hugo Elias' website. Another way of doing this would be modify the geosphere algorithm. You usually take a base mesh homomorphic to a sphere, continually subdiving its faces and projecting its vertices onto a sphere of the desired radius. By using a procedural 3D texture based on Perlin noise (the unperturbed vertex coordinates being the input) you could generate displacements which would vary in a coherent way across the sphere. I haven't seen this algorithm described anywhere else but it seems like an obvious extention to the geosphere algorithm. Anyone?

 
z80

December 17, 2001, 08:41 AM

Yeah, makes perfect sense to use a perlin noise function to calculate the displacement. Would certainly be faster than 5-10 mins pr map on a 650mhz, and simpler to implement as well.

Another idea that comes to mind, is to implement some ROAM-like algorithm so triangles are used where they are needed, instead of being constant over the sphere. Click here to read more about this on Gamasutra...

 
MiNDHiVE

December 17, 2001, 09:09 AM

From my impression of his algorithm, I'd imagine the triangle count would have to be contant across the sphere surface - thus his tesselation technique. You could certainly implement something ROAM like when viewing the created planet inside a game (but really, what's the point with todays hardware), but I think the high triangle count is required by his algorithm by the look of things.

As far as the technique is concerned, it sounds quite processor and memory hungry. The results however do look very cool. I like :)

Besides, creating a world by hand is going to take you alot longer than 9 minutes ;)

 
Lars W.

December 17, 2001, 09:24 AM

The problem with his approach is, that it is impossible to get high resolution Terrain at low altitude, lets say when flying from the moon to the planet, you wan't to land on the planet, you need to throw away all the vertices that arent visible.
If you use a realistic size for your planet (about 6000km radius)
and you need polygons with a size of at least 10 Meters for a good landing pad. then you would have so much vertices, that you can't precompute everything and because you need many iterations for fine grained terrain (maybe 10000) you can't do this on runtime for each vertex.
I think the perlin noise besed algorithm is more usefull for this type of application (the whole wolrd rts) but the algorithm is perfect for creating random asteroids when making the offset larger.

Lars

 
Bunnz

December 17, 2001, 09:34 AM

Hi realley cool

Never heard if this before ;)

Have fun
Bunnz
Visit: Bunnz Productions

 
SodoMaxx

December 17, 2001, 10:22 AM

I am just working on something like that.
The sphere is based on a cube, so the subdivision yields square patches, which will be procedurally textured (as the height displacement also based on Perlin noise, but hw-generated). For the reduction of the mesh to realtime-friendly sizes I use ROAM though I am looking for more GPU-demanding approaches. Anyone got an idea?

 
StiNKy

December 17, 2001, 10:47 AM

Niiiice! this looks really cool

 
shrike

December 17, 2001, 11:55 AM

That is a good idea of subdividing the tetrahedron, but the algo doesn't scale well, as others have mentioned. It is cool for still shots however, even if a bit slow. Maybe it could be combined with the good old plasma algo to boost speed?

 
Morgan

December 17, 2001, 12:07 PM

Beautiful design.

Lars W.'s comments are very insightful. Procedural terrain (with procedural objects) seems to be the only practical solution for planet-wide games. Steve Dollins at Brown is doing this and it looks really good.



-m

 
Def

December 17, 2001, 12:31 PM

This is almost identical to a project I was playing around with earlier this year. My subdivision algorithm was slightly different to yours though because I was able to subdivide individual triangles as I needed to instead of having to process the entire sphere. I managed this by only having to store a single extra number in the triangle class but almost went mad trying to get it working properly. (Which I eventually did. ;o) I then took the process a stage further to generate texture maps for a low resolution mesh.

As you have probably noticed the algorithm itself isn't the speediest around. I did spend some considerable time speeding it up (which involved lots of lookup tables) and managed to get it generating an entire planet's worth of textures (about 200,000 points iirc - although I may have over estimated this number, it's been a while) with 6000 iterations per point in about 11 seconds on my Duron 900. That was written in C++ still and was at that point that I began to realise the algorithm was never going to be fast enough for a realtime application. Something else I noticed (as Lars W points out) was when zooming in (my LOD algorithm partially worked - occasionally) the closer you got to the surface the more iterations you required to keep the detail of the coastline improving.

I've kinda got bogged down with other things recently and haven't been back to this for a while, but I think when I do (finally) return to it I'll look at other methods of generation. I will keep it sphere based though, I hate the thought of square maps. ;o)

Def

 
joke_dst

December 17, 2001, 01:00 PM

Those planets look really good! I'm working on a planet generator for a game I'm working on (www.starflight3.com), but I don't use any triangles at all, rather some sort of raycasting... And square maps (wich make the poles look funny, I know...). But at least mine runs at realtime on my 300MHz compu :)

 
=[Scarab]=

December 17, 2001, 01:34 PM

Very nice! Btw, a twelve-sided regular polyhedron of pentagons is called a dodecahedron. :)

 
Lion V

December 17, 2001, 01:55 PM

Interesting.
Just on a side note...
I used to mod X-Wing vs TIE Fighter- great game- and I made a mod with 'real' sized planets in it.
Due to the game constraints, I had to scale the solar system down a bit, but there are a few things I learned from that.

A planet is straight-up huge.
Even scaled down.
So if you are in a x/wing, it will take you like two hours going from one planet to the next.
Because I had to scale the planets down, my apparent speed going ovre the planet was unrealistic.

So if you have a RTS even partly to scale, you are gonna have to have one bloody huge map going.
Heres why-
I calculate that the minimun size for a unit is 5x5 feet.
So 1 tile=5x5 ft.
In 1 sq mi, you have a little over 1000 of these tiles.
The Earths surface area is about 49,342,498 sq mi.
Thats 4.9342497e12 tiles, I think. Perhaps its e13, not e12- but my point is:
To have a earth-size RTS planet, you are gonna need alot of memory.
If my calculations are correct, you would need hundreds of gigs of RAM, just to hold the actual data.
However, if you had a standard RTS or RPG, you could put a moon in the sky with this tecnique, and it would look good.
So yes, it does look nice.


 
Rob James

December 17, 2001, 03:18 PM

Hi,

An opportunity to let you all know that "Procedural Planet" isn't dead. Just resting!

http://www.baddoggames.com/planet

Expect more in 2002

ta ta

Rob

 
Jo Meder

December 17, 2001, 07:58 PM

MojoWorld is a commercial app which is essentially a procedural planet generator/renderer. It's the baby of Ken Musgrave, who I'm sure many of you have heard of, a pioneer in procedural landscape generation. MojoWorld has a realtime renderer, basically a realtime preview you can flythrough etc. and use for recording paths for animations. It's entirely procedural, the textures and landscape are refined on the fly, if you leave it a while you get a really good impression of the final render. I actually think this is the coolest part of the app. There's a free version, the Transporter, available at the website. I've been on at them to submit an image for IOTD with some info, I'm sure people here would find it interesting ( apart from being Yet Another Terrain Engine ;-).

In the interests of disclosure, I did much of the Mac porting for MojoWorld.

Jo Meder

 
Sdw

December 18, 2001, 03:07 AM

The sphere-generation seems interesting. When I want to create a sphere out of a bunch of triangles, I usually generate it as a number of 'rings' of triangles, starting with a small ring at the top of the sphere, then bigger and bigger to the middle of the sphere and then smaller again to the bottom. The good thing is that this way I get nice triangle strips. The bad thing is that the size of the triangles is VERY different over the sphere.
This dodecahedron-based way seems to generate much more uniformly sized triangles. While I understand how the algorithm works, I don't really know how to get started. Do you have a hard-coded definition of the original dodecahedron that is then used to generate the other triangles? Anyone have some source that shows how it's done?

 
Mr Rho

December 18, 2001, 05:46 AM

You all have very valid points. Just one quick comment though. The 4.5 minutes was the debug version. With optimization, I get 2.5 minutes (not much, but a difference nonetheless). Still not fast-enough for real-time though.

What this WOULD be useful for is pre-calculated, high-detail levels where you have to have a fairly constant grid. But I suppose you can get that with the other methods that were mentioned as well.

Thanx for all the clues and info though!

Rho

 
Johan Runeson

December 18, 2001, 07:34 AM

Any regular polyhedron will do as the basis. An octahedron or a cube (with split faces) would have very simple coordinates, but still give pretty regular triangles. Or, you could use the dual of the dodecahedron, the icosahedron (20 triangles, vertices at the centers of the dodecahedron faces).

Using a cube as the basis, you could store the height data as six bitmaps, one for each face of the cube. Might save some space.

/Johan

 
Sebastian Sylvan

December 19, 2001, 10:20 AM

Sounds like mandelbrot's algorithm for generating the terrain there. Only in an extra dimension.

 
Punchey

December 19, 2001, 02:17 PM

That's why you use procedural techniques to generate the planet using dynamic LOD as needed.

 
Raspberry

December 20, 2001, 04:20 AM

I think that if you wanted to get a better method to get the heights of the planet data, then use a 3D perlin noise function ( with the normal vector directed from the planet as the seed) (you would also get the ability to not care about the clumping of the triangles.. :) )

 
zed zeek

December 21, 2001, 04:11 PM

i to have been working on something very silimar :) (very much like rob james) though i only look at it about once a month thus progress is very slow.
great minds think alike

 
Rui Martins

January 03, 2002, 08:05 AM

Well, You could check the sphere tesselation (from where this is probably based), which comes as an example on the OGL Book A.K.A. "The Red Book".

Then you apply a Height Change/"Noise", based on something like the one in Hugo Elias page (or this IOTD), to make for the surface irregularities tipical of a planet.

Note1: The base polyhedron is obviously hardcoded, and then subdivided to some predefined depth.

Note2: Since each subdivision, makes 4 new triangles, for each triangle in the previous depth/level, you get a very fast growing number of tris.
To minimize this, you should choose a regular polyhedron (the base), with the least number of polys, because, the actual number of polys for a given sphere of depth (Depth) is:

NumTris = BaseTris * 4 ^ (Depth)

so reducing the number of inicial Tris is an obvious solution to the problem.
Another one is to not subdivide each triangle in 4 other but instead 2, which will give you a "smoother"/gradual growth in the number of tris.

Hope that helps, see ya

 
This thread contains 23 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.