Monday, May 11, 2015

Infinite Fields of Grass

Before I write about grass, I want to post a more recent screenshot of trees. That last blog post on trees got me working to improve their quality, mostly by adding more variation to height, branch placement, leaf size, textures, etc. The 5 different species of trees look more different from each other after these changes, and add increased variety to the scene. Here is how the trees are looking now:

The latest version of  5 species of procedurally generated trees in an open landscape. There are around 5000 visible trees.

Now, onto infinite fields of grass. Well, not really infinite - the grass does end, just far enough away that you can't see the transition. There are actually two scene modes, as noted in the previous post on trees.

Finite Grass

The first mode is a small cube of land that the player can walk around in and is mostly pre-generated and static. Not static in the sense that it can't be modified (because it can), but static in the sense that it's all generated upfront for a fixed area. I'll describe how grass works here fist, since it's simpler. In this mode, several million blades of grass can be generated and stored in a VBO (vertex buffer object) on the GPU. This takes a lot of graphics memory, and a significant fraction of a second of CPU time (using OpenMP parallelism again of course), but on the plus side there is no LOD (level-of-detail) to deal with so the grass looks very nice. It does help to divide the grass up into a few hundred patches with bounding cubes so that they can be dynamically updated and view culled so that patches that aren't visible aren't drawn. A few million blades of grass (typically 1.2M to 2.0M) in those grassy meadow-type scenes is a lot to draw, even as a single textured triangle each. Fortunately, it's relatively easy to do view frustum culling and occlusion culling against the terrain mesh and scene objects for each patch of grass.

Grass in this mode is very dynamic. It sways in the wind. The player can step on it and flatten out an area of grass. Similarly, it can be shaped and flattened by other heavy objects moving over it. Some game mode weapons will cut the grass. Explosions and fires will burn and flatten it. If the grass gets covered with dynamic water it will die and turn brown. And of course, since this mode supports a first person shooter game, the grass will get bloody. Most of this is handled on the CPU side by updating individual patches of grass when they change, which is a single VBO update call since each patch is stored together in a contiguous block GPU memory.

The grass shaders are some of the more unique of the custom shaders used in 3DWorld. The vertex shader moves the grass blades in the wind based on a wind direction uniform variable and wind speed texture map. Only the top point on the grass triangle moves in the wind, so the root part of the grass stays in place. Everything else is done per-pixel in the fragment shader: texturing, shadow maps, direct and indirect lighting, fog, etc. The fragment shader is somewhat slow and expensive, but grass doesn't usually take up much screen space so this tends to not be a limiting factor unless the camera height is around the height of the grass - which of course can happen, since grass height can be set to any value in the config file. But in most cases the grass height is low.

Here are two screenshots of grass modeled outside my parents' house.

Lush green grass surrounds this house model. This grass is dynamically shadowed and sways in the wind. [Note that I haven't updated this scene to use the new tree models as this requires recomputing indirect lighting.]

Grass is fully dynamic. It can be cut, crushed by walking on it, burned and flattened by explosions, stained red by blood, browned out by over watering, and even spray painted different colors.

Infinite Grass

Now I'll describe how I implemented an "infinite" field of grass for tiled terrain mode. In this mode, several hundred terrain tiles are generated around the player, and the ~100 tiles falling within the view frustum (visible to the player) are drawn. As the player moves around, old/distant tiles are discarded and new tiles are generated to maintain a constant number of active tiles. Each tile is the size of the entire scene in the previous (finite) mode. So that's 100x as much visible grass! It's no longer possible to generate, store, or draw that much grass on today's graphics hardware. The grass needs to be more dynamic and more compact. I chose to use hardware instancing of 32 unique patches of around 1500 grass blades each for ~500K total grass blades, which is actually 4x less memory than the finite terrain mode uses. Each tile contains many patches, and each patch is a random index representing which of the unique patches to instance in that position. This solves the generation time and memory problem, and the tiling artifacts of reusing patches aren't very noticeable.

It took quite a bit of work to figure out how to map a constant density, constant color, flat, square patch of uniform grass onto a curved landscape requiring variation in color, height, and density. All of this had to be done in the vertex shader on the GPU. The shader takes the terrain heightmap, terrain type map (which grass height, density, and color are derived from), and some 2D noise textures used to select random subsets of grass blades to remove. Grass blades selected to be removed are mapped to a degenerate single point triangle and made fully transparent in the hopes that the rasterizer (or at least the fragment shader) will discard them. It seemed a bit wasteful to discard 100% of the grass over rocky, snowy, or ocean terrain, so grass patches aren't even generated for tiles that contain no grassy terrain types. I think about half of the blades are discarded on average per patch/tile, which seems acceptable and the best I was able to come up with.

The time taken to draw that many (> 100M) individual grass blades is prohibitive, so a LOD (level of detail) system was needed. I decided to create approximate powers-of-two LOD with 5 levels plus the base full detail. Each detail level starts from the previous detail level and works by selecting a grass blade, then finding the blade closest to it to merge into a single larger grass blade. The surface area/width of the merged blade is the sum of the two input blades and the position and color is averaged. Preserving the total surface area is important to give the grass a consistent density across detail levels. This process of merging grass blades is continued until half the blades have been merged, or there are no nearby blades that can be merged together. This produces nearly a power-of-two reduction in the grass vertex count. In reality the sizes of each LOD level are more like 1500, 800, 450, 250, 150, 100. This works well, but gives at most a 15x reduction in the number of grass blades. Going further to higher LOD levels starts to create blades that are too wide and look unnatural.

15x isn't quite enough to get the rendering time down to a reasonable level, but there are other tricks to be played. The more distant tiles that are over a mile away don't need to have their grass drawn as individual blades. They can simply use a green grass terrain texture, which looks fine in the distance. The trick is making the transition from grass geometry to grass texture smooth so that the user can't see it. It turns out that always using the grass texture, even for nearby grass, looks just fine. The nearby grass blade geometry blocks most of the texture anyway, so the player doesn't see much of it. The harder part is removing those 5-th level LOD grass blades (that are made from merging some 15 nearby blades together) in a smooth transition when they reach the geometry/texture boundary distance. I tried various things:
  • Remove random blades near the cutoff distance so that the density decreases smoothly to zero
  • Increase transparency of grass near the cutoff distance smoothly from alpha = 1.0 to 0.0
  • Introduce random noise dithering to make individual pixels transparent in the distance
  • Translate the blades incrementally downward (in -z) until their tops go under the mesh
It turns out that the last approach (translation) worked the best and was also one of the simplest and most efficient. It worked so well, in fact, that it was nearly impossible to determine where the geometry to texture transition point was just by looking. So that's how I decided to do the transition.

Unfortunately, since the grass patches are instanced, it's no longer possible to dynamically update them for object interactions (crushed, burnt, dead, colored by blood) like in the case of finite grass. But this grass can still move in the wind, which preserves at least some of the dynamic nature of grass so that it doesn't look entirely static. As another optimization, wind motion is only enabled for nearby patches where the individual blades are apparent.

In addition to the grass, I added some colorful wildflowers for variety. These use a similar generation and rendering system, except that they're much sparser and don't require instancing. Flowers are procedurally generated, placed with density based on terrain type, and also move in the wind.

I'm not sure how much of what I did here for infinite grass is actually novel. There are plenty of papers out there on rendering infinite fields of grass. What I did here was a combination of what I read in those papers and some new tricks and ideas I came up with. It looks pretty good, is very efficient, and may be more generally useful than grass shown in many of those papers. After all, 3DWorld's grass is just one of many components of the entire scene, not the only/primary component. It needs to share runtime and resources with everything else and blend into the rest of the scene.

Here are some grass screenshots from tiled terrain mode.

A grassy field with wildflowers. The grass extends out to the distance, simulating many millions of individual grass blades. This nearly infinite field is still drawn at 135 FPS (frames per second). Can you spot the LOD transitions?

Grassy hillside showing how grass color and density can vary with terrain type between grassy, sandy, and rocky terrain.

Well, that's all I have to say about grass for now. I wonder if writing this blog post will get me working on grass again just like writing the previous tree post got me working on trees?