A little grass

Playform has had grass for a while now, but I kept putting off the blog post. It still needs a lot of work, to be sure, but I think even shoddy grass can do a lot to help the sense of detail in a virtual world.

The approach is roughly taken from this GPU Gems article (which does a much better job, just for the record). The basic method is to arrange 2D grass billboards into cross-shaped patterns (see this diagram).

The billboards work equally well in each direction, so we turn off backface culling when we render grass (instead of placing redundant billboards facing in the opposite directions). The resulting tuft maintains a reasonable 3D look even as you walk around it, although they do look odd from above.

To start off, we just place one of these "tufts" pointing straight up, at the center of every polygon that supports grass:

This already works pretty well, but there are some problems. First of all, the grass in the background doesn't properly cover the terrain. We'll deal with that later. Another problem is that the tufts don't connect properly to the terrain! Because billboards are placed in cross-shaped patterns, the base of each tuft is 2D; if we place a tuft on a polygon, the base of the tuft should sit flat on the polygon, but that conflicts with our goal of having grass point straight up.

First of all, let's rotate the tufts so that they sit neatly on their underlying terrain polygons:

That also adds some variation into the grass direction, which improves the realism a bit. But now the grass always points straight out from the terrain surface, which creates a weird effect on steeper slopes.

To control where grass points without rotating the base, we apply a shear effect to each tuft. First, we decide which direction we want the tuft to point, in world coordinates. Directly upward seems like a good start. Then we transform that direction back into model space, and find the shear that would cause the normal vector (which, in model space, is straight up) to become that desired model-space vector (or some multiple of it).

There's no viable shear when the desired direction is more than 90 degrees away from the surface normal. To deal with this in a somewhat reasonable way, we find the angle between the normal and the desired direction, and feed that through a function to smoothly clamp it back to [0, 90). The particular function probably isn't that important; I just use acos(e^(cos(x)-1).

Shearing a vector changes its length, stretching the grass. Let's reset vector lengths after shearing:

We still have the problem that the grass tufts in the background are too small. More generally, if we're placing one grass tuft per terrain polygon, we want to make sure it roughly covers the polygon. So we apply a shader effect to scale the grass tuft based on the size of the polygon (again, the specific function probably doesn't make a huge difference).

Lastly, we can add a wind effect. I'm lazy, and I have this WebGL noise function lying around (which produces smooth noise given a point). We construct the input using the grass tuft position and the current time (plus some arbitrary offsets and trial-and-errored scaling factors), and we can get back two random angles, one clamped to [-180, 180], and the other clamped to [45, 135]. Taken together, these two angles can describe a vector that points within 45 degrees of straight up. Then we just apply a shear effect to make the grass point that way, similar to the one we're already applying to make it point upward.

And now we have rolling hills of waving grass! It's not winning any award, and there are definitely areas for improvement, but I think it will do the job for at least a little while.

The worst kind of crabgrass

I was experimenting with a shader effect that would make grass billboards grow bigger if they were farther from the camera, so lots of faraway terrain could be covered with relatively few grass billboards.

That was the idea anyway. I overshot it a little:

I had the scaling effect set so dramatically that as grass spawned further from the camera, it would gain back more than that distance by growing bigger. So it crept back towards the camera by getting huge.

I say "crept", but it wasn't a very subtle process.

Things didn't get much better from there.

Bugs! In *my* grass?

I'm still preparing the post on grass blades. Part of the slowness is because I'm trying to go through each step incrementally, and show screenshots of the improvement. Because this means commenting out and tweaking parts of the grass code, I've ended up rewriting it a few times. The latest rewrite made the code simpler and saved some math, but it introduced an interesting bug. See if you can spot what's wrong:

If you guessed "those weird streaks shouldn't be there", then consider yourself a programmer, because they should almost definitely probably not be there.

Although they are pretty dramatically placed...

And they look kind of exciting...

I got too close. I guess this is my life now.

Fixing/improving the grass illumination

As part of some mundane tech debt cleanup, I ended up tweaking the code that creates and places grass billboards (also: Playform has 3D grass now. Post on that soon). In doing that, I noticed that when a "tuft" of grass was placed on top of a polygon, the grass code was recalculating the surface normal. That information's already available from the polygon structure, so it's definitely a little silly to be recalculating it when it's sitting right there.

But the worse part is that I was doing it badly. The surface normal was just a cross-product of the polygon's sides. The surface normals stored in the polygon struct itself are averaged vertex normals, which make for smoother lighting. And they're sitting right there.

So long story short I took a little time out and made the code interpolate the vertex normals instead. Here's what the changed normals look like with grass debugging shaders:

(Before)

(After)

And in some non-debug shots:

(Before)

(After)

The grass itself has changed too, so it's hard to see the difference in the foreground. But the slope in the background really shows improvement.

Terrain loading design

Current Design

The Playform client divides the world into discrete, fixed-size chunks. A chunk is either entirely loaded or entirely unloaded, at some LOD. When a chunk is needed, the client requests all the voxels of the given LOD in that chunk, as well as neighboring voxels of that LOD. Each chunk in the client then "waits" to receive all the voxels it needs, before generating the mesh and loading it. Chunks are not unloaded until they are either further than the view distance, or a new chunk is being loaded at the same position.

Between adjacent chunks of different LODs, seam meshes need to be loaded to stitch together the different LODs. This is not done.

Ideal Design

Mesh generation happens around edges - every edge between four adjacent voxels can generate a mesh fragment. It doesn't require any chunking, and in fact, chunking adds annoying edge cases (heh) and things to be careful of. Ideally, voxels would just be requested at a given LOD based on their distance from the player. When the server sends a voxel back, we could examine all adjacent edges to see if any new mesh fragments should be loaded/unloaded.

There are some extra wrinkles with this approach: one is that a voxel may be received at a higher LOD than we had before, which means the new voxel is smaller. If we unload all the mesh fragments including the old voxel, in order to load the ones including the new voxel, we will have created holes. We face a similar problem right now, when chunk LODs need to be switched, which we solve by putting off unloading until all the new voxels have been received, at which point we can generate all the mesh fragments at a higher LOD. We can do something similar here, but it will be more complex, since chunks had fixed sizes and a more obvious set of legal positions.

Another related difficulty is the problem of determining which mesh fragments describe the same area. Fragments of different LODs are extracted from edges of different sizes, so we can't use any kind of equivalence relation (e.g. hashing) to find conflicting edges quickly. For example, if we receive a new voxel of size 1, we might look at its adjacent edges and find that some of them are able to generate mesh fragments that should be loaded. In this case, we would need to unload any mesh fragments associated with the same regions of space, but mesh fragments could be associated with that region not only via edges of size 1, but also of size 1/2, 1/4, 2, 4, etc. We need a data structure that gives a reasonably efficient way of finding which edges conflict with one another.