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?

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...

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 ;)

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

Hi realley cool

Never heard if this before ;)

Have fun
Bunnz
Visit: Bunnz Productions

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?

Niiiice! this looks really cool

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?

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

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

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 :)

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

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.

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

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

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?

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

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

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

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

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.. :) )

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

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