Jump to content
  • Advertisement
  • entries
    19
  • comments
    16
  • views
    10295

Planet Generation Plans

nukomod

629 views

 

Hey all!

This time I'm going to write a little about my plans for generating planets. This entry won’t go into any specific details of the terrain generation but will be just a very high level overview of the basic framework. I don't think any of the ideas in here are new.. the procedural generation community are a very clever bunch indeed! I'm always amazed how when an idea pops into my head I'm able to find an existing article about it that goes into fine detail on the subject. Anyway let's crack on!

Heightmaps & Voxels

When it comes to generating terrain an easy first choice is to generate height maps and build the terrain mesh from that. You can get some good looking results quickly by overlaying some noise generation and tweaking things here and there.

image3.jpg.d0643950ffdd9f86dd0f6e1020922ba8.jpg

Though these can give some nice results they have limitations. For example tunnels and overhanging terrain can’t be represented in a simple height map. You also have to choose a projection scheme to map a 2D height map onto a sphere.

image2.jpg.4f5a2e118dcbb0837f584cfc2e21d34d.jpg

There’s another approach to terrain generation using voxels and that’s what I’m aiming to use. With voxels you can define all sorts of complex terrain and you can define what’s hiding under the ground too - whether it's seams of coal, ore or underground rivers. Many games use voxel terrains to great effect such as the infamous Minecraft. Sign me up!

In Minecraft the voxels are arranged in a grid, keeping everything nice and simple.. until you want to model a whole planet. Then you’d get something like this:

image4.jpg.06803f5afaa2b9138cb96c5e1150a331.jpg

Though that does look really cool, I don’t want my worlds to be great big cubes floating in space, so what do I do? There are all sorts of solutions to building a spherical world from a voxel grid, but they seem to be full of difficult space warping, caveats and rendering complications. I’d rather not deal with these kinds of complications, so I’m going to try a different approach.

Instead of arranging the voxels in a grid I’m planning to arrange them as points on a geodesic sphere like this (imagine the vertices are voxel points):

image9.jpg.0446fca9ecb9619023c5af59509a80be.jpg

It’s like taking the space warping issues you’d need to do at the cubes edges and spreading it evenly across the entire surface of the sphere. Instead of it becoming a difficult edge case it becomes a constant low level annoyance and keeps things consistent at all times. It will make the mesh generation a little more fun later too ;)

Voxel Planet Generation

The plan is to use an icosahedron as a starting point. Each vertex here is a voxel. This can be considered the lowest possible Level Of Detail (LOD) of a planet.


image1.jpg.a202d4363bdf2de698a27ea7eebeadd1.jpg

The space is chopped up into tetrahedrons from the planet surface into its core. There is an extra vertex at the centre of the planet for this.

image7.jpg.8681f66211b5b6385177bcae6a15e424.jpgimage8.gif.257e47a37cb70829e3a746f664e40150.gif

These tetrahedrons can be subdivided through to the core of the planet as required.

image5.png.87fe7726c2411700a7f6d0545558fae7.png

These illustrations are somewhat misleading though as this isn’t just generating a spherical mesh, but a bunch of voxels that could be empty space. The voxel points (vertices) hold information about what's actually in the space they occupy, whether it’s atmosphere, rock, magma etc. It is the job of the terrain generator to define what a voxel contains. I'm going to keep a clear divide between the planet voxel generation code and the terrain generation code this way.

I have some uncertainties on how to best manage the subdivisions of the planets voxels as required, but I’ll bash it out in a prototype.

Dynamic Changes

The game also needs to be able to make permanent changes to the terrain during play. Large explosions should create craters and I want them to persist. To do this I will need to be address the voxels and save state changes about them. I'm not 100% sure on the approach for this yet either. One train of thought is to basically create an algorithm for the voxel generation that that is able to assign each possibly generated vertex a unique 64bit number. That would have no waste and allow the maximum number of voxels, and some napkin math makes me believe it would have good detail on earth sized planets. Another approach could be some kind of hash of their XYZ or polar coordinates, though that will be more wasteful so it’d bring the total addressable voxels way below what a 64bit unique id could theoretically hold.

Ok that’s enough for now!
 

 

 

 



8 Comments


Recommended Comments

I've had some success applying the usual cube-> sphere transformations to a cube where each face is a voxel shell with some pre-determined thickness. It's not terribly elegant, but it's easy to get up and running. Your tetrahedral approach might avoid some of the distortion and apparent grid - interested to see how it turns out.

Share this comment


Link to comment

Very interesting.  I'll be curious to see how you realise the plan.

Share this comment


Link to comment

Looks neat. In fact I'm working on almost the exact same thing :)  However I'm not sure you can divide tetrahedrons evenly. You can get four new ones on the corners and then you get this sort of odd center space.  In your picture it looks to me like you divided up the faces of the original tetrahedrons which you can do easily, however chopping up the insides might be tricky, however if you figure out a good way to do it, it would be way cool.

I decided to use prisms, just because you can make an octree out of them like you can a cube.  The down side is you can't go all the way to the center of your sphere and also the inner ones are a bit smaller than the outer ones. But if you build your geometry around some reasonable band of the world it shouldn't be a huge problem, and also it gets rid of the problem of geometry looking different in different corners of the world like you would get if you generated your world in a simple subdivided cube.

I had an old version working a few years back but it just used height-maps applied to a subdivided icosahedron based simplex-noise. However it did let you walk around a huge planet without generating any data in advance.

Share this comment


Link to comment
19 minutes ago, Gnollrunner said:

However I'm not sure you can divide tetrahedrons evenly. You can get four new ones on the corners and then you get this sort of odd center space.

That odd sort of space in the centre is an octahedron. Decomposing the octahedorn is tricky, but not impossible

Share this comment


Link to comment

You guys are spot on about dividing up the space. I didn't realise at first that tetrahedrons don't tessellate in 3D space, it would have been great if they did. The picture of the sphere where you can see inside is quite misleading isn't it! Gnollrunner I'm playing with some options now, which includes some with prisms, seems I may be going down the same route you did :) Do you have any links related to what you did?

Share this comment


Link to comment
1 hour ago, nukomod said:

You guys are spot on about dividing up the space. I didn't realise at first that tetrahedrons don't tessellate in 3D space, it would have been great if they did. The picture of the sphere where you can see inside is quite misleading isn't it! Gnollrunner I'm playing with some options now, which includes some with prisms, seems I may be going down the same route you did :) Do you have any links related to what you did?

I really don't, I'm just kind of winging it.  I'm basically doing the same thing as marching cubes except with prisms. The hard part is really the LOD transitions.  I think surface nets or dual contouring does that better but then you get other issues you need to deal with. I haven't found any magic bullets. I'm using octrees with chunking such that all cells in a chunk that have any geometry must be at the same level AND neighboring chunks can at most have one level difference. Even with that, the edge conditions are a pain. I worked out an algorithm that seems to work but I'm still debugging all the cases. I have table look ups with pointers to little subroutines that handle various cases. It's a lot of code, but I'm tying to avoid a lot of ifs.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!