Friday, July 15, 2016

Asteroid Belts and Planet Clouds

I added asteroid belts to 3DWorld a while back, maybe a year or so ago. I thought they looked pretty good at the time. Recently I watched an asteroid belt video from the Kickstarter campaign of the Infinity: Battlescape space game. Sorry, I can't seem to find the original video, but here is a similar video by the same team/company. I realized that my asteroid belts lacked the fine reflective particle clouds that add a sense of volume to the scene. I decided to reuse the same procedural volumetric fog/cloud framework that was used for nebulae, explosions, and clouds in 3DWorld.

That wasn't my first approach. I originally wanted to ray cast into the asteroid belt volume and perform ray marching through it, integrating a randomly generated density field along the way. This is similar to how volumetric fog was done in 3DWorld as shown in this previous post. This technique works well when your scene is a large cube, but unfortunately isn't so easy when the domain is a complex shape such as a circular asteroid belt.

Asteroid Belt Bounding Volume

Let me take a step back and explain how asteroid belts are created in 3DWorld, in particular how their shape and asteroid distribution is chosen. There are two types of 3DWorld asteroid belts: system asteroid belts and planetary ring asteroid belts. 3DWorld also has spherical asteroid fields, but those work differently and won't be discussed here. System asteroid belts orbit the star in a solar system, similar to the orbits of planets. Planetary asteroid belts surround a single planet and are much smaller in size (radius) and asteroid count.

Each asteroid belt is generated by placing asteroids in a Gaussian distribution around an elliptical path in the orbital plane of the system or planet. The entire set of asteroids is contained within a non-uniformly scaled torus volume. The orbital plane normal forms the z (center) axis of the torus, like an axle through a tire. The  z-scale is typically set to around 25% of the x/y scales to produce a flattened shape that resembles a thin disk. The x and y scales can be different, producing a non-circular (ellipsoid) shape. There is also an inner radius and outer radius for the torus.

This is not a very nice shape to work with, since it is mathematically fairly complex and involves higher order trigonometric functions. It's much easier to perform a series of transforms to convert the asteroid belt shape into a unit (normalized) torus using the following steps:
  1. Translate the torus by the asteroid belt center to put the origin at (0,0,0)
  2. Rotate the torus so that its axis is oriented in the +z direction
  3. Scale the torus independently in x, y, and z to produce a circular shape with an inner radius of 1
It's fairly easy to determine if a point is inside of the asteroid belt volume by applying these transforms and checking for point-in-torus. Sphere intersection is more complex, but not too bad. However, computing the intersection points of a line with a torus is much more difficult because it requires solving for the roots of a quartic equation. There are up to four intersection points. I managed to find some existing source code to do this, but it's not something I would have wanted to derive, write, and debug myself. If you must know, parts of the source code can be found here and here. If you're really interested in the math, here is a fun paper that's guaranteed to keep you busy for a while or put you to sleep. If anyone knows of a simpler way to compute the intersection of a line with a torus, please let me know. Bonus points if it works both on the CPU and on the GPU.

Anyway, if you remember from the second paragraph, the volume ray marching approach requires computing all intersection points of a line with the asteroid belt bounding volume on the GPU. This would require porting the transform code, quartic solver code, and torus intersection code to GLSL. Now, I'm sure this would be possible, but it would be a huge time sink to debug, and there may be floating-point precision issues if it was all done on the shader in single precision. And it would probably be very slow. I decided to abandon that approach and go with something different and (hopefully) easier.

Asteroid Placement

Let me explain how asteroids are actually placed and rendered to produce a realistic volume consisting of millions of asteroids of various sizes. There are three types of asteroids drawn:
  1. Large asteroids drawn as procedurally generated 3D triangle meshes; Up to 10,000 instances of 100 uniquely generated asteroids; They dynamically move and rotate over time.
  2. Smaller asteroid point sprites that are rendered as spheres in the fragment shader; 1M generated, though only nearby asteroids are visible
  3. Smaller asteroids drawn as points to fill in the gaps when the player is near or within the belt; ~100K points per few degree arc slice of visible nearby torus (~1M max visible)
This set of asteroids fill in the space in the belt fairly well. Type 1 asteroids are highly detailed and also include normal mapping and procedural craters to make them look more convincing. The smaller points and spheres are thrown in as part of the background to trick the user into thinking there are millions of large, detailed asteroids out there. It works!

Asteroid Belt Screenshots

Here is a screenshot of what these three types of asteroids look like together. This is just a small section of the asteroid belt, maybe 1-2% of the total. How many asteroids does it look like this section contains?

Closeup view of an asteroid in the asteroid belt showing normal mapped craters and a nebula in the background.

Pretty good, but the density is not as high as the asteroids in the original Infinity video. Something needs to be added to fill the spaces between the meshes, spheres, and points. How about some procedural, reflective dust clouds?

Asteroid belt with procedural volumetric dust clouds reflecting the star's light, shaded with the star's color.

This looks much better. The asteroid belt has more volume and looks more interesting. The dust clouds properly occlude asteroids that lie behind them and produce a sort of fog in the distance. The dust is a yellowish color based on the star's color. Now it looks like there really are millions of asteroids visible, from huge ones to tiny bits of dust. Of course it's another trick, there are only a few thousand of them. Here is another view of this system asteroid belt, from outside looking in toward the star.

Asteroid belt and reflective dust clouds viewed from the outside facing the yellow star.

Note that the dust clouds extend further outside the torus envelope than the asteroids themselves. This seems to make sense physically: Larger, heavier asteroids are affected more by gravity, making them revolve around the star or planet faster, and forcing them into a thinner ring in the orbital plane. At least it may be correct to first order.

Here is an example of a cold, icy planetary asteroid belt, viewed from slightly above.

Cold planet with surrounding asteroid belt containing ice crystals and reflective dust.

The clouds seem to gently rise up out of the orbital plane with very slow animated motion. The star is behind and below the camera, causing the asteroid belt to cast ring-shaped shadows on the top part of the planet.

Here is a video of my ship flying into the system asteroid belt, bouncing off two large asteroids (collision detection is enabled), then flying to a ringed planet and crossing through its asteroid belt.

Rendering - How It's Done

There are 100 unique dust cloud models generated when the first asteroid belt becomes visible, and they're shared across multiple belts. The vertex data is stored in GPU memory for fast access for drawing. Limiting the number of unique clouds cuts down on CPU time and GPU memory. Each large type 1 asteroid has a dust cloud instance attached to it with a small random translational offset to make cloud placement look more random. Clouds are attached to asteroids so that they move with them, without having to independently compute orbital vectors for yet another type of object on the CPU. This way, there is no explicit physics update for dust clouds. They need to move to track a planet that revolves around the star. The movement also adds more dynamic effects to the rendering, which makes it more interesting. As a bonus, cloud positions don't need to be generated within the asteroid belt bounding torus as they inherit that property (approximately) from the asteroids they're attached to. This makes the code much simpler.

Each cloud model consists of 9 intersecting quad billboards that cover an approximately equally spaced set of normal vectors on the unit sphere. This is fewer than the 13 billboards used for nebulae and explosions, for a different quality vs. performance trade-off. The various billboards are faded in and out by modifying their transparency (alpha) values based on view distance and view angle. Distant clouds are faded to transparent and skipped to improve rendering time, since they don't contribute much to the final image. Clouds very close to the player/camera are also faded out to reduce the amount of fragment shader overdraw and minimize worst case framerate.

The GPU fragment shader computes per-pixel transparency by evaluating 4 octaves of 3D Perlin noise, where each octave is implemented as a lookup into a 3D precomputed noise texture. I used 4 octaves rather than the 5 octaves used for nebulae and explosions to improve performance. Since 9 billboards are used, a few of them are oriented toward the camera for every possible camera position, producing an illusion of a 3D volume with simulated parallax. Asteroid clouds have the most impact on performance when the camera is in the middle of the belt and the fragment shader must do significant work computing noise values. On average, enabling clouds reduces the framerate of this case from 260FPS to 140FPS, which is reasonable.

I chose a fairly simple lighting model for asteroid belt clouds. I assume the clouds are composed of small particles that reflect the star's light in all directions like tiny, randomly oriented mirrors. No explicit light scattering is modeled (yet). I also assume that the occlusion of the particles themselves is negligible, so that unlit/shadowed particles are effectively invisible. This is similar to how dust that is normally invisible will shine when it's caught in a path of sunlight in a room. With this approach, the lighting is independent of the camera view direction and the star's light direction, which simplifies the math and makes the shader faster. The CPU can simply intersect each dust cloud's light ray with the nearby planets and moons to determine which are in shadow. Shadowed clouds are simply not drawn, since they contribute no light and are assumed to produce no significant occlusion. The end result is that non-shadowed clouds are lit using the star's color and an intensity based on the distance to the star with a quadratic falloff.

Partially transparent surfaces are typically drawn in back-to-front depth order so that alpha blending works properly. However, sorting thousands of clouds by depth on the CPU is an expensive process. The sort would need to be performed every frame as both the camera and the clouds are moving. I decided to omit this sort, since it works well enough without it. Each cloud is around 95% transparent, so the depth sorting errors are barely noticeable, especially with alpha testing enabled.

Update: I added the sort, after filtering by distance and view frustum culling. It only seems to add around 1% additional render time. It makes very little difference in the final image, so it's probably not necessary. For reference, the culling, sorting, and the rest of the CPU side of rendering only takes around 0.3ms.


This post so far has been a wall of text, but not too many fancy pictures/videos. Here are some bonus screenshots of planets showing off planetary clouds and other effects.

View from moon orbit showing a highly detailed moon surface with normal maps and GPU tessellation, a Terran planet behind it, and an asteroid belt in the distance.

This first image shows a closeup of a moon's surface. The high resolution procedural normal map is generated from height differences in the fragment shader. The moon's horizon is also very detailed thanks to the tessellation shader that converts a low polygon sphere into a detailed, bumpy planet. A procedural Terran planet and some large procedural voxel asteroids are visible in the background. [The asteroids are probably unreasonably large.] Behind them are the system asteroid belt, and behind that is an ice and rock planet. You can even see a few space ships floating around by the moon and near planet.

Water/ocean planet and moon. The planet is covered with clouds that cast shadows on the water.

This image shows a cloudy ocean planet in a solar system with a yellow-orange sun. The clouds are procedurally animated in the fragment shader and cast shadows on the water under them. A moon is shown to the left, with a volumetric nebula behind it. This nebula uses a rendering approach similar to the asteroid belt clouds, but it uses three color channels rather than an alpha channel only. In addition, the nebula uses ridged noise and different noise constants.