Today I'm going to talk about the approach to ambient occlusion used in the Minecraft mapper.
First of all, we assume that light falls uniformly from the sky, like on an overcast day. The amount of light illuminating a particular patch of ground is thus proportional to the amount of the sky that can be seen unobstructed from that point. The following diagrams show the general idea in 2D from the side:
The red point on top of a plateau has an unobstructed view of the sky, so it is maximally illuminated. The green point is only slightly occluded by the peak on the left. The blue point is substantially occluded on both sides, so it will be quite dark.
That's the general idea. The amount of illumination for every point will be proportional to the solid angle of the sky visible from that point. However, that's quite a lot of work to do. We're going to cheat a lot by making a number of simplifications:
- We're going to ignore overhead obstructions and only consider the occlusion caused by neighbouring cells.
- We're going to assume that the sky is in fact a horizontal plane 3m above the point we're rendering.
- We're further going to consider only a 2m×2m square of that plane, and assume that the visible 2D area of that square is a reasonable approximation of the solid angle of sky visible from the point.
The following diagram gives an idea of what we're talking about, again looking at things side-on:
The reason these simplifications help is that we can now calculate the occlusion just from a height-field describing the heights of the cells that we're rendering. For each pixel, we consider the height of the cell it's in and the height of the neighbouring cells. For each neighbouring cell, we consider how much higher it is than the central cell, and how far the edge of that cell is horizontally from the point being rendered. Based on all that, we can calculate how much of the 2m square patch of sky is visible.
In this diagram the red point is a pixel for which we want to calculate the ambient occlusion. The pixel is very close to the tall cell to the north, which will occlude a fair bit of the sky. The medium sized block to the east is a bit further away and not as tall, so it won't occlude as much, and might not occlude any at all. The only other taller block, to the south-west, is sufficiently far away and small that it's not going to occlude any of the patch of sky we're considering.
Next time I might go over the maths, or I might set this aside for now and talk about how we flip and rotate tiles for rendering minecart tracks. Let me know if you have a preference.
I'd like to see the maths. Are you calculating the actual pixel illumination or are you simply using a fixed calculation based on the number of occluded rays?
ReplyDeleteI'm guessing the "fancy" lighting version of minecraft actually calculates the pixel values at each of the vertices and blends them across the face.
I actually assumed that the basic lighting model worked on a per cell basis (light travels in vertical, horizontal and 45degrees) which would only require a 2x2 neighbour check as anything at 3m or above is not capable of illuminating the cell in question.
Subject to the gross simplifications listed, it does calculate the actual pixel illumination. It doesn't cast individual rays, it just calculates the size of the occlusions of the eight neighbouring cells as projected onto the "sky square", accounting for overlap. (I think there's actually one more simplification I didn't mention that I'll cover in a subsequent post.)
ReplyDeleteI'm not sure how Minecraft's "fancy" lighting works, but I think it's something like what you describe. We're going to do the calculations per-pixel rather than per-vertex (at substantial cost) to get quite a nice effect, but I don't think our approach would generalize to the full 3D case.