Home       About Me       Contact       Downloads       Part 19    Part 21   

Part 20: Still More Transparency

May 18, 2011

At the end of the last update, I said I was going to leave transparency alone for now and get back to it later. I lied... I just couldn't leave it alone.

In the last part, I thought I had a good solution for transparency -- the "screen door" technique. It turns out I had implemented it incorrectly and not even noticed that it wasn't working. The reason is that this particular Minecraft landscape isn't doing anything complicated. We only have three transparent blocks -- water, glass and leaves. The water is mostly lying flat over ground and doesn't need to be sorted. The glass mostly obscures other glass or opaque stuff, and doesn't need to be sorted. And the leaves appear in a bunch around a tree and sort errors aren't very noticeable.

When I implemented screen door transparency correctly, it looked pretty bad and I realized it just wasn't good enough. I wanted to move on to more world building, but the question still nagged at me. I want to let users create their own blocks with their own textures eventually. What if I just can't implement that due to the time it takes to render transparent data correctly?

This video is the nightmare that was haunting me. Show it at 480p to see the true horror of aliasing gone mad!

Reader Simon Buchan suggested "Quake 2-style" transparency, where the halftoning is done not on the surface of the object being rendered, but in "view-space". That prevents aliasing (mostly) and sparkle as you move. It looks better, and I was trying to tell myself that it was good enough. Here's a video of that. If you focus your eye on the noise in the halftone pattern, you can see that it moves with the screen and not the world.

Sort Less Often

Florian had given me a big list of things to try regarding transparency. Several of them amounted to the same sensible advice -- if sorting is costing too much, sort less often. For example:

  • Spread the sorting out over several frames. The eye won't notice if things are briefly in the wrong order.

  • Sort nearby objects first, and leave distant ones for later. Errors at a distance won't be as noticeable.

  • Sort only when you need to sort -- when the eye moves and changes perspective on a piece of the scene.

Fig 1: When do we sort?

If we were drawing arbitrary triangles in the scene, potentially any change in eye position could change the sort order. But these scenes are all cubes, and they are better behaved. It turns out, there's a quick test for whether we need to sort a chunk after a move.

If you think of which cubes are nearest the eye in the start and end position, you can see that only when the eye transitions between two different rows of cubes do we need to sort. Off the ends are a special case -- if the eye is moving around to one side of the chunk, it does not affect the sort order. We do this test in x, y, and z, and if none of them require a re-sort, we leave the chunk alone.

In practice, this produces a somewhat strange result. When you move one unit, all the chunks to the horizon in same X, Y or Z as the eye re-sort, while the chunks to the sides are unchanged. Since the landscape is mostly horizontal, you only get really big sorts (of a whole plane of chunks) when you move vertically.

I added code to keep a list of "sort-required" chunks. As it renders, it tests each chunk and adds to this list. At each frame, we sort some number of chunks off the list. Eventually, this will be controlled by some estimate of how much CPU time I can afford. Right now, it's an option, "sortCount".

This simple algorithm accomplishes all three optimizations I listed above. Sorting is done a few chunks at a time, from near to far, and only when you move.

This video shows the sort list being constructed and processed. Chunks are drawn in red when the sort test says they might need to be sorted.

The video was made at 30 fps with 2 chunks sorted per frame. In the demo, I'm getting more like 90 fps and sorting 10 chunks at a time, so you can't actually see any of the sorts happening. Also, I don't even check chunks with no transparent cubes. I was having trouble even telling if it was doing the sorts (because so little sorting is required on this landscape), so I added a bunch of floating boxes with transparent sides.

This video shows the final result. On my machines, I have yet to catch it with an out of sort area. The frame rate is fine, even on my slower Linux machine. Give it a try and let me know. I've removed the point summary at a distance for now, so the "summaryDistance" and "detailDistance" options have no effect.

I'm happy with this, so now I can get back to world building!

Build Your Own Landscape

There's a new project in the source code, called BuildWorld. It is the back end of my Minecraft extraction code and will let you create your own landscape. You'll need to have the programming tools to recompile the code, but not much programming skill otherwise. In the file Source/BuildWorld/BuildWorld.cpp, find the routine createWorld. You can write something simple like this:

  // add a terrain from noise
  for (int x = 0; x < WORLD_XSIZE; x++)
    for (int z = 0; z < WORLD_ZSIZE; z++)
      double value = (noise(x*DENSITY, z*DENSITY) - noiseMin)/noiseRange;
      int height = 5+(int) (MAXHEIGHT * value);
      height = max(0, min(WORLD_YSIZE-1, height));

      for (int y = 0; y < height; y++)
        WORLD_CELL(x, y, z) = 1;  // stone

You are setting bytes in a big array (1024 by 128 by 1024). Set any pattern of blocks you like. The numbers for the different block types can be found in docs/blocks/mcblocks.xml in the Crafty demo. The BuildWorld program will crunch this array and set all the visiblity flags, then write out the huge directory of chunks for use by Crafty. If you want a smaller world, you can change the size in the BuildWorld.cpp file. Just make sure your dimensions are a multiple of 32.

Create a directory "newworld" for it to write chunks into. Run it and it will produce a landscape like Figure 2:

Fig 2: Default BuildWorld landscape

Edit the options.xml file in Crafty to set "worlddir" to "newworld" and you can display your world.

The Demo

Demo 20 will use the same world files as parts 19 and 15. Download The Part 19 Demo World. Unzip it into the same directory as the demo. The directory "world" should be next to "docs" and "options.xml". Or you can edit the "worldDir" attribute in "options.xml" to point to it wherever you like.

For Windows, download The Part 20 Demo - Windows.

For Linux, download The Part 20 Demo - Linux.

The Source Code

Download The Part 20 Source, or go to https://github.com/mgoodfel/SeaOfMemes for the GitHub repository.

Home       About Me       Contact       Downloads       Part 19    Part 21   

blog comments powered by Disqus