As if by magic, some maths appeared

I've not really done any programming lately, so this week there's no Minecraft. Instead there's some maths. Hurrah! Hey, where are you—

I was reading Richard Wiseman's Friday puzzle. It's very short and not at all hard, so you might want to go and solve it and come back. Go on, I'll wait.

Okay, you're back? I'll try not to state the answer outright, but it will probably become pretty obvious very quickly. Right, so this got me thinking about sums of series. The case in the question is sufficiently small that you don't even need to work out the formula for the sum of sequence in question, but I was thinking about it nonetheless.

Now, I knew the formula for the sum of an arithmetic sequence, and I knew that you could easily enough prove it by induction, but this is a very unsatisfying form of proof. It doesn't feel like something you could have figured out on your own. Imagine just picking random equations one at a time and testing them until you find one that you can prove correct with induction! I thought about it a little and came up with what I thought was a pretty compelling geometric proof, at least for the simple case where you start at 1 and increment by 1. (I have no idea if a proper mathematician would call this a proof. I am certainly not a proper mathematician.)

Is it obvious? On the left in the green we have a square with area 1, a rectangle with area 2, a rectangle with area 3, etc. The area of the whole shape must be the sum of those areas. By dividing up the space differently, we can easily see how to produce the closed form.

Great, I thought. Now lets do the same for the sum of squares. It must be just as obvious in 3D. Right?

Hmmm. Well, it gives the right answer, and it's satisfying to figure it out by hand, but it lacks the obviousness of the diagram for the arithmetic sequence sum. Perhaps there's a simpler way to do it?

As an aside, I think I'm getting the hang of Inkscape, although there are still some areas I find I much prefer Visio. Inkscape has some pretty painful and inflexible handling of arrowheads, for example. They're always black, regardless of the line colour, and then there's a special menu action just to make them change to match the line colour. The selection of arrowheads available is limited and weird, and most of them aren't resizable. I'm not sure if that's because SVG forces arrowheads to behave in strange and unintuitive ways, or that's just the way that Inkscape chooses to work.

Maybe next week there will be more programming. We shall see.

Minecraft mapping - Rotation and flipping

Last time, I discussed ambient occlusion for adding depth to the map. Today I'm going to explain how the fragment shader rotates and flips oriented blocks like minecart tracks.

As you may have noticed, there's only one block ID for regular minecart tracks. The 4-bit data value encodes the orientation of the track, from 10 possibilities - 2 orientations of straight track, 4 orientations of corner track, and 4 orientations of sloped track.

A minecraft texture pack includes only two textures for normal minecart tracks: one curved and one straight. We need to use these to make up all the other orientations. We could either do that in advance - building up a bigger texture atlas with all the orientations we need, or we can do it in the shader. By doing it in the shader we avoid the need for a much expanded texture atlas and some fiddly work to assemble textures, at the cost of extra work in the shader.

To let the shader know what orientation to use, we encode it in the blue channel of our map data texture. We use 2 bits to encode a rotation (0°, 90°, 180° 270°) and 1 bit to encode a possible flip. (I don't think we actually use the flip at the moment, but it might be useful for doors.)

The shader code isn't actually terribly exciting. I should however point out that this version treats the map texture as having normalized float values, rather than integers. For most of the earlier posts I had been updating the code to use integer textures to simplify things a bit, but I haven't gotten around to doing that with this code. That's why we multiply the sample values by 255.0 – as normalized floats they've already been rescaled from 0 to 255 to the range 0.0 to 1.0.

    float flipx = (tiles_sample.b * 255.0) >= 8.0 ? -1.0 : 1.0;
    float rotation = mod(
        tiles_sample.b * 255.0, 8.0) *
        0.5 * 3.141592653589793;
    mat2 transform = mat2(
        flipx * cos(rotation),  flipx * sin(rotation),
        -sin(rotation),         cos(rotation));

We form a rotation matrix with the rotation value of 0, 0.5π, π or 1.5π. The sines and cosines just work out as -1, 0 or +1. There's probably a cheaper way to calculate them.

This will rotate around the origin. Before we transform our texture coordinate we rescale it to the range -1..1, then adjust it back afterwards.

Some mention should be given to how we obtain the rotation values in the first place. There's no trick – there's just a great big table mapping block id and data values to texture coordinates and orientations. The same table is used to pick coloured wool values.

And here's the end result. I think I've talked about most of the things I had originally set out to cover. Next week I might touch on light levels, but there's not a lot to say there. If I find the time I'd like to do some work on cave rendering, but I'm not sure I'll both find the time to work on it and write a blog post, so next week's post may be quite short.

Minecraft mapping - Ambient occlusion 2

Last time I described in principle how the ambient occlusion shader works, but didn't really go into the details. Today I'll go into a bit more detail.

Something that I think may not have been clear last time is that we're calculating ambient occlusion independently from lighting based on the "blocklight" and "skylight" values. For ambient occlusion we're considering only the arrangement of solid blocks in the immediate neighbourhood, not any genuine sources of light. As a separate step we later multiply together the ambient occlusion value and the light-level based on blocklight and skylight. Again, this is a simplification, and it does result in extra shadows in dark areas, but it generally looks fine.

As we saw previously, to determine the the level of shadow added by occlusion, we determine how much "sky" is visible from the rendered surface, where the sky is actually a horizontal square not very far above the surface. This screenshot shows the view from the ground looking up. The white blocks represent the sky square, and the stone slabs are neighbouring taller cells.

The yellow outline shows the unoccluded area of sky. The following diagram breaks that down into the areas shadowed by each of the eight neihbouring columns:

Area A is the occlusion from a neighbouring corner block, while areas B and C are occlusions from neighbouring side blocks. You'll observe that 1. the corner blocks always occlude rectangular regions of sky; 2. the side blocks occlude trapezoidal areas and 3. the corner block occlusions can overlap with the neighbouring side blocks.

Now, I have to admit that I made a bit of a mistake when I first worked this out, and didn't realise that the side blocks were occluding trapezoids, so I worked it as if they were rectangles instead, like this diagram:

The problem with making this as a simplification is that it will result in significant discontinuities around corners. Encountering these, but not understanding why, I experimented with tweaking values and if you look in the shader code you'll see a comment, "TODO: Figure out why the 2* multiplier is needed in the next line!" I haven't actually figured out why that works yet, but I plan to work through the maths again with trapezoids, if it's not too complicated, and see how it compares. However, for now I'm going to discuss the slightly broken version with the rectangles.

Here's another pair of diagrams of those occlusion rectangles:

On the left we have a similar case with some extra occluding columns. Things to note here are that the yellow corner column provides no extra occlusion because it is shorter than both of the neighbouring side columns. The dotted line shows the division of the sky square into quadrants, each of which we'll handle separately.

On the right diagram, you can see the same arrangement, but different rectangles are highlighted. The orange "+" rectangle is the area of unoccluded sky in the quadrant ignoring the corner column. This can be easily calculated based on the proximity of the neighbouring cells on the sides, and the heights of the columns in those cells. The teal "−" rectangle is the extra occlusion provided by the corner column, which we subtract from the unoccluded area to find the total unoccluded area in the quadrant. We calculate the teal area similarly, using the proximity of the neighbouring side cells, and the height of the corner column, but we make sure to clamp its dimensions to be positive – if either dimension would be negative it means the corner block is not going to provide any occlusion and can be ignored.

I've left this a bit late, so I don't have formatted code snippets or a nice runnable example, but you can go look at the complete fragment shader in github. The obscurely named "lightcalc" calculates the dimension of one side of the orange rectangle based on the height and proximity of the neighbouring cell, with 1 being the maximum unoccluded size. "cornerlight" calculates the unoccluded area in the quadrant, again with 1 being entirely unoccluded.

This shader is pretty slow. It results in a noticeable frame-rate drop for me. I haven't yet investigated whether the cost is in the quantity of calculations or from sampling all eight neighbouring cells for their height, but I suspect it's the latter. If that's the case, we could preprocess the image and store information about each cell's neighbours in a compressed form, reducing the number of samples needed. Maybe an expert could suggest the most fruitful avenues to optimization.

Here's what it looks like without any textures:

Any thoughts? It occurs to me that I could very well have overlooked a much easier or a less horrifically simplified way to do this. I'll need to look into how feasible it is to properly calculate the trapezoidal areas, and also figure out why the bodge of doubling the teal area results in continous results (at least, continuous between cells of equal height; we don't want continuity across height changes – the whole point of this is to highlight height differences). Feel free to ask questions if it's not clear. I may yet do one more post on this topic if people would like further clarification.