Lighting
Analysis is based on the decompiled source of the vanilla b1.7.3 client.
Light Opacity (sometimes referred to as Light Modifier) is a value between [0, 255] which describes how opaque a block is. Opaque blocks (including lava) have a light opacity of 255. Other values for light opacity are between [0, 15].
Block Light Value is a value between [0, 15] which describes how bright a voxel is. Sky Light Value is a value between [0, 15] which describes how much skylight a voxel receives. Light Value will be used as a generalization of both these terms.
Luminance describes how emissive a block type (e.g. a torch) is.
Each chunk maintains a height map (a 2D array, byte[Z][X]). The value for each index is the y-coordinate of the first block (starting from the top, y=127) in that column for which the block below does not have a Light Opacity equal to zero. I will refer to this voxel, and all voxels above it, as being "above the height map"; the remaining voxels in that column are "below the height map" (Picture a plane that lies above the top of the first (semi) opaque block in the column as the separator).
A separate per-chunk variable stores the y-coordinate of the lowest block but I'm currently unsure what it is used for.
Chunk::generateHeightMap()
{
for (X,Z in 0..<ChunkBaseSize)
{
var h = ChunkHeight - 1
while (h > 0)
{
let blockLightOpacityForBottomNeighbor := Chunk.getVoxelAt(X, h-1, Z).blockType.lightOpacity
if blockLightOpacityForBottomNeighbor != 0 then {
Chunk.heightMap[z][x] := h
break
}
h := h - 1
}
}
}
(Re)Lighting is not a one step process. Rather, it occurs over multiple iterations, which may span multiple ticks of the game loop, until a new state of equilibrium has been reached.
The actual (re)lighting is handled by distinct LightingOperations objects which are essentially a bounding box + lighting logic. These objects are created by the World object in response to some other object requesting a lighting update for a given bounding box, and scheduled for later execution. For instance, when a block in a chunk is modified, the chunk requests a lighting update with a 1x1x1 bounding box corresponding to the modified coordinate.
A LightingOperation can be for either Block or Skylight. I shall refer to these distinct cases as BlockLightingOperation and SkyLightingOperation (though Notch used the same class for both, with conditional checks).
The World maintains a LIFO queue of scheduled LightingOperations (up to 1000000 before the game aborts). On each iteration of the game loop up to 500 LightingOperations are dequeued and executed. Note that the execution of a LightingOperations will likely cause additional LightingOperations to be enqueued. Because the this is a LIFO queue, these new LightingOperations will be executed before older LightingOperations. This subroutine returns a boolean indicating if it was able to completely empty the queue before reaching the 500 limit. This is necessary because world generation use this same subroutine to light the world but it will invoke it continuously until it returns true.
As discussed previously, LightingOperations are created and enqueued by the World in response to some other object requesting an update for a given BoundingBox (in world coordinates, of course). The algorithm is shown below. Notch's implementation includes checks which immediately returns from the subroutine if there are 50 or more levels of recursion. However, it is not clear how this subroutine could be invoked recursively.
World::ScheduleLightingUpdate(Kind, BoundingBox)
{
// No idea
if blockExists(BoundingBox.centerX, 64, BoundingBox.centerY) == false then
return
// Notch's implementation asks the chunk containing BoundingBox.Center if it wants to
// prevent this update from being scheduled. Only empty chunks return true.
// Iterate over the last five scheduled lighting updates, but ignore SkyLightingOperations.
for lightingUpdate in scheduledLightingUpdates.reverseEnumerator[0..<5]
if lightingUpdate is BlockLightingOperation then
// Merge will only succeed the complement of BoundingBox and lightingUpdate.BoundingBox
// is two or fewer blocks along each axis AND
// MergedBoundingBox.Volume - lightingUpdate.BoundingBox.Volume <= 2.
if lightingUpdate.tryToMergeWith(BoundingBox) then
return
if Kind == .Sky then
scheduledLightingUpdates.enqueue( SkyLightingOperation(BoundingBox) )
else if Kind == .Block then
scheduledLightingUpdates.enqueue( BlockLightingOperation(BoundingBox) )
}
On execution of a LightingOperations, a new LightValue, C is computed for each voxel within the LightingOperations bounding box. The bounding box is enumerated in X->Z->Y order (X is outermost) starting from the minimum extent along each respective axis. If there the chunk containing (X,Z,Y) is empty, execution proceeds to the next voxel.
-
For a BlockLightingOperation,
Cis computed as the maximum of the Luminance for the block type at (X,Z,Y), and the Block Light Value from its brightest neighboring voxel minus the Light Opacity for the block type at (X,Z,Y). If the block type at (X,Z,Y) has a Light Opacity >= 15 and a Luminance of 0,Cis 0.If
Cis equal to the current Block Light Value for the voxel at (X,Z,Y), execution proceeds to the next voxel in the bounding box. Otherwise,Cis stored as the new Block Light Value for the voxel at (X,Z,Y) and a Block Light Value ofC - 1is propagated to the voxel's preceding neighbors along each axis (X-1, Y-1, Z-1). A Block Light Value ofC - 1is also propagated to the voxel's succeeding neighbors along each axis (X+1, Y+1, Z+1) iffX+1,Y+1, andZ+1are greater than the bounding box's maximum extents along each respective axis. -
For a SkyLightingOperation, 'C' is computed as the maximum of 15 (If the voxel is above the height map), and the Sky Light Value from its brightest neighboring voxel minus the Light Opacity for the block type at (X,Z,Y). If the block type at (X,Z,Y) has a Light Opacity >= 15 and the voxel is below the height map, the computed Sky Light Value for the voxel is always 0.
If
Cis equal to the current Sky Light Value for the voxel at (X,Z,Y), execution proceeds to the next voxel in the bounding box. Otherwise,Cis stored as the new Sky Light Value for the voxel at (X,Z,Y) and a Sky Light Value ofC - 1is propagated to the voxel's preceding neighbors along each axis (X-1, Y-1, Z-1). A Sky Light Value ofC - 1is also propagated to the voxel's succeeding neighbors along each axis (X+1, Y+1, Z+1) iffX+1,Y+1, andZ+1are greater than the bounding box's maximum extents along each respective axis.
BlockLightingOperation::execute()
{
for (X,Z,Y) in BoundingBox
{
if World.hasNonEmptyChunkContainingCoordinates(X, Z) == false then
continue
var voxel := World.getVoxelAt(X,Y,Z)
let currentVoxelLight := voxel.blockLight //voxel.skyLight for SkyLightingOperation
var newVoxelLight := 0
// Brightness must decay by at least 1
let blockLightOpacity := MAX(voxel.blockType.lightOpacity, 1)
// For SkyLightingOperation this is 15 if (X,Z,Y) is above the height map.
let emissiveness := voxel.blockType.luminance
if blockLightOpacity < 15 or emissiveness != 0 then {
newVoxelLight := collectNeighboringVoxels(X,Y,Z).reduce(0, { (maxNeighborLight, neighbor) in
return MAX(maxNeighborLight, neighbor.blockLight /* or .skyLight */)
})
newVoxelLight := MAX(newVoxelLight - blockLightOpacity, emissiveness, 0)
}
if newVoxelLight != currentVoxelLight then {
voxel.blockLight /* or .skyLight */ := newVoxelLight
let propagatedLightValue := MAX(newVoxelLight - 1, 0)
// .. or neighborSkyLightPropagationChanged
World.neighborBlockLightPropagationChanged(X-1, Y, Z, propagatedLightValue)
World.neighborBlockLightPropagationChanged(X, Y-1, Z, propagatedLightValue)
World.neighborBlockLightPropagationChanged(X, Y, Z-1, propagatedLightValue)
if X+1 >= BoundingBox.maximumX then
World.neighborBlockLightPropagationChanged(X+1, Y, Z, propagatedLightValue)
if Y+1 >= BoundingBox.maximumY then
World.neighborBlockLightPropagationChanged(X, Y+1, Z, propagatedLightValue)
if Z+1 >= BoundingBox.maximumZ then
World.neighborBlockLightPropagationChanged(X, Y, Z+1, propagatedLightValue)
}
}
}
The operation for propagating light to a neighboring voxel is rather simple. When propagating the result of a SkyLightingOperation, Notch first checks if the neighbor is at or above the height map. If so, the propagatedLightValue is set to 15. When propagating the result of a BlockLightingOperation, Notch first checks if the neighboring block type's Luminance is greater than the propagatedLightValue. If so, the propagatedLightValue is set to the Luminance of the neighboring block type. A final check compares the (possibly updated) propagatedLightValue to the current Light Value of the neighboring voxel. If this check fails, a new LightingOperation with bounding box of 1x1x1 (corresponding to the neighbor's coordinates) is created and scheduled (using ScheduleLightingUpdate, so it may be merged with another operation).
After terrain generation for a chunk completes, the new chunk calculates its height map (using the technique described above) and performs a quick lighting operation to calculate the Sky Light Value of every voxel that is exposed to the sky, including voxels that are below one or more voxels containing a semi-transparent block. Light spread is not calculated at this time so voxels which are below another voxel containing an opaque block are ignored. Still, this is usually enough to give the appearance of a properly lit chunk from a distance.
Chunk::afterTerrainGeneration()
{
generateHeightMap()
for (X,Z in 0..<ChunkBaseSize)
{
var skyLight := 15
var Y := ChunkHeight - 1
while Y > 0
{
var voxel := Chunk.getVoxelAt(X,Y,Z)
let blockLightOpacity := voxel.blockType.lightOpacity
skyLight := skyLight - blockLightOpacity
if skyLight > 0 then {
voxel.skyLight := skyLight
} else {
break
}
Y := Y - 1
}
}
for (X,Z in 0..<ChunkBaseSize)
{
Chunk::scheduleLightingUpdateForNeighborsOfColumn(X,Z)
}
}
After the initial quick lighting pass is performed a full lighting updated is scheduled for later execution. Notch's method for this is somewhat indirect. For each column in the new chunk, a Sky Lighting Operation is scheduled for each of the column's four neighbors.
Chunk::scheduleLightingUpdateForNeighborsOfColumn(X, Z)
{
let maxYForColumn := heightMap[z][x]
World.scheduleSkyLightingUpdateForColumn(X.inWorldSpace - 1, Z.inWorldSpace, maxYForColumn)
World.scheduleSkyLightingUpdateForColumn(X.inWorldSpace + 1, Z.inWorldSpace, maxYForColumn)
World.scheduleSkyLightingUpdateForColumn(X.inWorldSpace, Z.inWorldSpace - 1, maxYForColumn)
World.scheduleSkyLightingUpdateForColumn(X.inWorldSpace, Z.inWorldSpace + 1, maxYForColumn)
}
World::scheduleSkyLightingUpdateForColumn(X, Z, Y)
// Y is the height of the neighbor column requesting the update
{
let maxYForColumn := getHeightMapValueForColumn(X, Z)
// This method only relights the voxels between this column's height and
// the height of the neighbor column requesting the update.
if Y < maxYForColumn then {
// The neighbor column requesting this update is shorter than this column.
ScheduleLightingUpdate(.Sky, BoundingBox(X Y Z to X maxYForColumn Z))
} else if Y > maxYForColumn then {
// The neighbor column requesting this update is taller than this column.
ScheduleLightingUpdate(.Sky, BoundingBox(X maxYForColumn Z to X Y Z))
}
}
It may first appear that no lighting updates would end up being scheduled. However, in Notch's implementation, calling World::getHeightMapValueForColumn() would return 0 since the chunk has not yet been registered with the world so the second condition is always true. In addition, lighting updates may end up being scheduled for the edge columns of existing chunks that the new chunk borders.
The vertex buffer for a tessellation has four attributes: position, normal, u/v coordinates, and color. The color attribute is composed of four channels, RGBA, each represented as an unsigned byte [0-255]. Like all attributes, color is specified per vertex. During rasterization the lerp'd RGBA values from the color attributes of the primitive being rasterized are multiplied with the RGBA values from the corresponding texel to produce the final diffuse color for the fragment.
When Minecraft builds the mesh for a block, vertex color is kept consistent across all the vertices that compose each primitive for a given face. So the vertices in the primitives that makeup the top-face share the same vertex color, the vertices in the primitives that makeup the bottom-face share the same vertex color, etc. Colors are always opaque (any transparency in the final diffuse color comes from the texture).
Face-color is the multiplicative product of the following three inputs:
This is a color vended by the Voxel being tessellated. The default implementation returns white (1.0f, 1.0f, 1.0f). Grass, Leaves, Tall Grass return different a different color depending upon their metadata and the temperature & humidity of the voxel. Redstone wire returns a dark red (0.5f, 0f, 0f).
When tessellating a grass block, this input is ignored for all but the top face. A second tessellation pass is then performed for the sides of the grass block. During this pass, the texture is set to #38 (in terrain.png) and the BlockColor is used to apply the proper color to the green parts.
This value is used to force the faces of a block which are perpendicular the celestial axis (Top, East, West) to always be slightly brighter than those which are not (Bottom, North, South). The difference is noticeable even if the block is not exposed to sunlight. An example can be seen here:
This effect is accomplished by multiplying the face-color by a constant specific to the face.
- Top - 1.0
- East/West - 0.8
- North/South - 0.6
- Bottom - 0.5
This is actually the brightness of the neighboring voxel in the direction of the face being tessellated. For example, when tessellating the bottom face, look at the brightness of the voxel at (x, y-1, z). If the model for the block occupying the voxel does not completely fill the space within that voxel, the brightness for the inset faces is that of the voxel. This check is not applied for bottom faces which are assumed to never be inset (for standard blocks).
TODO - Discuss special blocks (torches, ladders, fences, ...)
The brightness for a voxel is the maximum of the block's Luminance, the voxel's Sky Light Value minus the subtracted skylight, and the voxel's Block Light Value. The subtracted skylight varies with the current celestial angle and other factors.
let brightness = MAX(voxel.blockType.luminance, voxel.skyLight - skylightSubtracted, voxel.blockLight)
For a voxel containing Stairs, Farmland, or a Slab block, the brightness of the brightest neighbor (excluding the bottom neighbor) is used instead.
The above value is an integer between [0-15] which Notch uses to index into a lookup table containing the actual brightness as a floating point value. This also allows for customizing the relationship between the brightness as it is used for gameplay purposes vs rendering. In vanilla Minecraft, a different lookup table is used for each dimension.
The lookup table is a 1-dimensional array of size 16.
-
Overworld: [0.05, 0.067, 0.085, 0.106, 0.129, 0.156, 0.186, 0.221, 0.261, 0.309, 0.367, 0.437, 0.525, 0.638, 0.789, 1.0]
-
Neather: [0.1, 0.116, 0.133, 0.153, 0.175, 0.2, 0.229, 0.262, 0.3, 0.345, 0.4, 0.467, 0.55, 0.657, 0.8, 1.0]