• entries
232
1462
• views
953702

# Procedural asteroid fields

1838 views

I spent a week or two playing with a new shadowing algorithm, ie. the infamous trapezoidal shadow maps. I'll keep it short: it's an improvement over light-space shadow maps, but I'm still not happy with this variable resolution ( when the camera is looking in the light direction, or in the opposite direction ), resolution degenerates to standard shadow maps, and eveyrthing gets blurry ( plus it increases shadow acne ). So far, it is however the best shadowing solution I've explored.

I still have to experiment parallel-split shadow maps. They're quite similar to cascaded shadow maps in philosophy, so compared to trapezoidal shadow maps, I'm expecting:
- a worst best case (in other words, the nice sharp shadow that I have with trapezoidal shadow maps will look worse with parallel-split shadow maps)
- a best worst case (in other words, the horrible degenerated case of TSM will not happen with PSSM). Quality will be best balanced.
- in average, quality will be a bit lower with PSSM than TSM.
- performance wise, they'll be similar, but I might have to decrease the maximum shadowing range.

When will the engine be complete ? When will you start working on the game ?

The engine will never be complete. It'll be expanded, optimized and new modules added in the coming years. I can't say at a specific date: "the engine is complete!".

As for when I'll start working on the game, it's also an ambiguous question. The game is composed of thousands of tasks, some which are low-level, some which are higher level of abstraction. For example, the XML file describing how spaceships are assembled is definately not part of the engine. But although it's part of the game, it's still a very technical thing. So if we include this technical work, the answer to the question is: work on the game has started months, if not a good year ago. After all, some code of the ICP is getting reused in the game, so you could say that as soon as I started to work on the ICP, I started on the game.

But I have a feeling that people who ask when I'll start working on the game have in mind the following question: "When will you implement gameplay features ?" such as trading, A.I., going in stations / cities, etc.. In that case, it's not likely that I'll start on that part before end 2007, as there are tons of technical issues ( data structures, algorithms, databases ) related to the game that need to be set up first.

Procedural asteroid fields ( aka gas giant's rings )

In the past two weeks I've been working on procedural asteroid fields. I've recorded a new video ( see link below ). Don't expect anything fancy in the rendering area: it's just per-vertex lighting with a diffuse texture. The gas giant planet is missing too, at the center of the rings.

The asteroid field system is based on a combination of many elements, which are:

Ring geometry

The ring is composed of a disc of quads. Nothing special here, except that tesselation is dynamically adapted based on the distance to the camera ( similar to level-of-detail ). When the camera is on the rings, the geometry weights around 6500 triangles. When the camera is far away, it can decrease to no more than a thousand.

Ring noise

At a closer distance, some noise starts to appear on the rings. This is to simulate the thin dust composing the rings. In the same time, dust points get procedurally spawned, giving a parallax effect.

Asteroids meshes

Asteroids are not procedurally generated, only procedurally placed. There are 10 types of asteroid meshes. They are textured with a single diffuse map, but we found that setting the texture coordinates correctly to avoid seams was impossible ( and a real pain to get just "good enough" ). So instead, I came up with a technique used by NVidia in their "floating cave" demo, which avoid seams in texture coordinates. Basically, the asteroid is planar-mapped from 3 directions ( X Y and Z ); then, depending on the triangle normals, 3 weights are generated. The diffuse texture is then sampled 3 times and the weights are used to blend the 3 samples together.

Another problem with asteroids was that they became blurry up close. Increasing texture coordinates would virtually increase the resolution, but patterns would appear. Instead I've experimented a noise texture ( actually, 2 levels of noise textures ) that is modulating the diffuse color. Of course, it also requires to be sampled 3 times to avoid seams..

Procedural asteroids placement

The whole algorithm is based on an octree. A the moment, the ring has a diameter of 300,000 Km, and the octree a depth of 14 levels.

When the octree gets split into new children, depending on the depth level of the new node, asteroids of a certain size get spawned. For example, at level 10, asteroids that are Km-sized are generated, while at level 14, asteroids that are 50 to 100m only are generated. This ensures that when asteroids pop up on screen, their size on screen is not too large.

Each asteroid is assigned a unique ID that will be used in gameplay code later ( for example for mining ). Unique IDs are a real problem, as they are currently encoded on a 64-bits integer. You'd think 64 bits is more than enough, but there can be hundreds ( if not thousands ) of asteroids generated per octree node, with a depth of 14, the number of combinations grow exponentially.

Thanks to the unique IDs, all the code that generates asteroid attributes ( such as their type, position, orientation, speed, etc.. ) is replicable ( ie. it's not really random, as the same asteroid ID will end up with the exact same attributes each time it gets generated ). In other words, you can zoom out a million kilometers away and come back at the same place, the asteroid will be at the same place ( assuming it was motionless ) and look the same. It's important especially in a multiplayer context, as two different players need to see the same thing on screen, and transfering all those asteroid attributes from the server to the client would saturate bandwidth ( there are thousands of asteroids visible on screen ) quickly.

Asteroids also rotate and follow an elliptical orbit, which is randomized, giving an impression of chaos when you're inside the asteroid field.

Performance

Performance wasn't very good at first, especially when you were starting to move inside the field. The reason for that is that when asteroids are spawned, a new object must be added to the scene graph. When you're moving fast, thousands of objects must be added ( and in the opposite direction of the movement, removed ) to the scene graph. It really stresses the CPU.

I implemented a spawn queue to maintain a good performance. The algorithm is given a maximum amount of time ( around 5 milliseconds at the moment ) during which it tries to spawn as many asteroids objects as possible. The procedural algorithm fills this queue with new requests in a FIFO order.

Densities

Another aspect of the procedural asteroids generation are the spawn probabilities, related to the ring density. The ring has a small thickness ( currently of around 10 Km, although it's not a sharp thing ). The chance that any asteroid spawns above or under this 10-Km thickness is very low ( on my experiments, the most extreme case I've found is a huge asteroid that spawned 200 Km above from the ring plane ).

The ring density is taken from the ring texture ( at the moment, Saturn ring's texture ). The alpha of this texture contains a density value ranging from 0 to 1. It's used to change the probability that an asteroid should be spawned based on its position in the rings. In other words, if there are black spaces in the ring texture, asteroids will not get spawned there ( or at a lower probability ).

See this image, taken between two ring features:

Future work:

System belts are tricky because of the 64-bits UID limit. Exceeding this limit might be hard technically, and require all sorts of hacks. A better way to handle it would be to keep the 14 octree depth level, but since system belts are millions of times wider than a gas giant's ring, that means asteroids would be so sparse that they'be almost impossible to find. I'll continue to experiment.

Impostors: there is at the moment a distance at which asteroids are rendered as dots, and closer to that distance, get replaced by a real object. Instead of rendering dots, I plan to use an impostors system. I'm not sure if I'll do that in the coming weeks, or if I'll delay in many months. The popping of asteroids when they go from a dot to a real object isn't too horrible.

Collisions: there are currently no asteroids collisions, they just intersect each other. Ideally I'd detect collisions, play an explosion effect, and remove the two colliding asteroids ( or if a small one hits a big one, remove the small one only ). I'd have to keep a list of UIDs of destroyed asteroids, and check those IDs out each time asteroids are spawned. This might cause performance problem if the number of destroyed asteroids isn't kept under control.

Video:

Asteroid field, 16 MB Divx 5 ( low quality )

Can't you combine the 64 bit variable with a location name ? Like .. Galaxy[x][y].GetAstroid(64bit number). That could decrease the huge numbers.. Or do you consider that a hack ?

I would be very lazy with this problem..

public struct HugeID{
uint64 ID1;
uint64 ID2;
override string ToString()
{
return ID1.ToString() + ":" + ID2.ToString();
}
}
:\$

Hi Ysaneya,

I had heard of the "blending three planar-mapped sets of texture-coordinates together" technique before, but haven't ever found an algo or demo. Could you point me towards where you got your info from?

Thanks heaps,

Lachlan.

Amazing as always, Ysaneya.

Quote:
 Original post by LachlanL Hi Ysaneya, I had heard of the "blending three planar-mapped sets of texture-coordinates together" technique before, but haven't ever found an algo or demo. Could you point me towards where you got your info from? Thanks heaps, Lachlan.

The exact name of the .PDF is "Cascades by Nvidia" from Ryan Geiss and Michael Thompson. It's really dead easy, here is the relevant GLSL shader code:

    vec3 blendWeights = abs(gl_TexCoord[1].xyz) - 0.2;
blendWeights = blendWeights * 4.0;
blendWeights = pow(blendWeights, 3.0);
blendWeights = max(blendWeights, 0.0);
blendWeights = blendWeights / dot(blendWeights, 1.0);

vec4 diffuse = texture2D(diffuseTex, vec2(gl_TexCoord[2].y, gl_TexCoord[2].z) * 2.0);
vec4 diffuse2 = texture2D(diffuseTex, vec2(gl_TexCoord[2].x, gl_TexCoord[2].z) * 2.0);
vec4 diffuse3 = texture2D(diffuseTex, vec2(gl_TexCoord[2].x, gl_TexCoord[2].y) * 2.0);
diffuse = diffuse * blendWeights.x + diffuse2 * blendWeights.y + diffuse3 * blendWeights.z;


gl_TexCoord[1] contains the normal in object space and gl_TexCoord[2] the vertex position in object space, directly copied from the vertex shader. Many of the constants are arbitrary.

Quote:
 Original post by MarijnStevens (...)Can't you combine the 64 bit variable with a location name ? Like .. Galaxy[x][y].GetAstroid(64bit number). That could decrease the huge numbers.. Or do you consider that a hack ? (...)

This might help a lot, using the spawn coordinates as the asteroid's ID. Although in the case of planetary rings I'd use polar coordinates instead.

Something that really baffles me is how you can find an asteroid again in the correct position of its elliptical orbit? If they were static it would be dead easy, but this way you would have to store it and keep track of its position, or work some magic ;) Great video, as usual it gives an amazing sense of scale!

Ysaneya, are there any variables for the 10 asteroid meshes other than texture noise?

Quote:
 Original post by MarijnStevens (...)Can't you combine the 64 bit variable with a location name ? Like .. Galaxy[x][y].GetAstroid(64bit number). That could decrease the huge numbers.. Or do you consider that a hack ? (...)

This might help a lot, using the spawn coordinates as the asteroid's ID. Although in the case of planetary rings I'd use polar coordinates instead.

Something that really baffles me is how you can find an asteroid again in the correct position of its elliptical orbit? If they were static it would be dead easy, but this way you would have to store it and keep track of its position, or work some magic ;) Great video, as usual it gives an amazing sense of scale!

Quote:
 Original post by Vileedge Ysaneya, are there any variables for the 10 asteroid meshes other than texture noise?

What do you mean ? They all have tons of variables, including position, orientation, scale, orbit radii, orbit inclination, speed, etc..

Y.

I suspect he means, are there more ways in which the appearance of the asteroids themselves are procedurally varied (in terms of overall shape, color, and whatnot). Personally I think that would be overkill, and that it's fine the way it is.

I've been following your progress with keen interest, but that video is stunning. The use of the octree is great, and that'll speed up physics too. The thought of doing collision detection with all those asteroids with no advanced scene management makes me shudder.

I have to admit though, I'm not sure what to think of the elliptical orbits and asteroids being able to collide with each other. That seems like realism taken to an unnecessary extreme. If asteroids can collide and be destroyed, aren't you worried about rings gradually disappearing? Granted, that would take a long time, but still. Or are you planning to have new asteroids spawn periodically?

Quote:
 Original post by gharen2I have to admit though, I'm not sure what to think of the elliptical orbits and asteroids being able to collide with each other. That seems like realism taken to an unnecessary extreme. If asteroids can collide and be destroyed, aren't you worried about rings gradually disappearing? Granted, that would take a long time, but still. Or are you planning to have new asteroids spawn periodically?

That would only be temporary.. but how long would depend on the size of the asteroid. A kilometer-sized asteroid would respawn maybe weeks after it's been destroyed, but a small peeble, only a few minutes. The ring will never disapear, and although collisions could happen and rocks orbit, it's still "static" in nature.

Hey, thanks mate.

Nice implementation! Asteroid fields sound like they'll be dangerous places, what with the randomized orbits. I noticed in the video one flew by the camera, moving at a very high relative velocity! Wouldn't want that to hit your ship....

Dude, wow.