Light calculation: New bulk node lighting code

This commit introduces a new bulk node lighting algorithm to minimize
lighting bugs during l-system tree generation, schematic placement and
non-mapgen-object lua voxelmanip light calculation.

If the block above the changed area is not loaded, it gets loaded to avoid
lighting bugs.
Light is updated as soon as write_to_map is called on a voxel manipulator,
therefore update_map does nothing.

1 files changed, 367 insertions, 4 deletions

diff --git a/src/voxelalgorithms.cpp b/src/voxelalgorithms.cpp
index 3c32bc125..411369bd4 100644
--- a/src/voxelalgorithms.cpp
+++ b/src/voxelalgorithms.cpp
@@ -542,6 +542,21 @@ void spread_light(Map *map, INodeDefManager *nodemgr, LightBank bank,
 	}
 }
 
+struct SunlightPropagationUnit{
+	v2s16 relative_pos;
+	bool is_sunlit;
+
+	SunlightPropagationUnit(v2s16 relpos, bool sunlit):
+		relative_pos(relpos),
+		is_sunlit(sunlit)
+	{}
+};
+
+struct SunlightPropagationData{
+	std::vector<SunlightPropagationUnit> data;
+	v3s16 target_block;
+};
+
 /*!
  * Returns true if the node gets sunlight from the
  * node above it.
@@ -753,7 +768,7 @@ void update_lighting_nodes(Map *map,
 		for (u8 i = 0; i <= LIGHT_SUN; i++) {
 			const std::vector<ChangingLight> &lights = light_sources.lights[i];
 			for (std::vector<ChangingLight>::const_iterator it = lights.begin();
-					it < lights.end(); it++) {
+					it < lights.end(); ++it) {
 				MapNode n = it->block->getNodeNoCheck(it->rel_position,
 					&is_valid_position);
 				n.setLight(bank, i, ndef);
@@ -817,8 +832,10 @@ void update_block_border_lighting(Map *map, MapBlock *block,
 	bool is_valid_position;
 	for (s32 i = 0; i < 2; i++) {
 		LightBank bank = banks[i];
-		UnlightQueue disappearing_lights(256);
-		ReLightQueue light_sources(256);
+		// Since invalid light is not common, do not allocate
+		// memory if not needed.
+		UnlightQueue disappearing_lights(0);
+		ReLightQueue light_sources(0);
 		// Get incorrect lights
 		for (direction d = 0; d < 6; d++) {
 			// For each direction
@@ -873,7 +890,7 @@ void update_block_border_lighting(Map *map, MapBlock *block,
 		for (u8 i = 0; i <= LIGHT_SUN; i++) {
 			const std::vector<ChangingLight> &lights = light_sources.lights[i];
 			for (std::vector<ChangingLight>::const_iterator it = lights.begin();
-					it < lights.end(); it++) {
+					it < lights.end(); ++it) {
 				MapNode n = it->block->getNodeNoCheck(it->rel_position,
 					&is_valid_position);
 				n.setLight(bank, i, ndef);
@@ -885,6 +902,352 @@ void update_block_border_lighting(Map *map, MapBlock *block,
 	}
 }
 
+/*!
+ * Resets the lighting of the given VoxelManipulator to
+ * complete darkness and full sunlight.
+ * Operates in one map sector.
+ *
+ * \param offset contains the least x and z node coordinates
+ * of the map sector.
+ * \param light incoming sunlight, light[x][z] is true if there
+ * is sunlight above the voxel manipulator at the given x-z coordinates.
+ * The array's indices are relative node coordinates in the sector.
+ * After the procedure returns, this contains outgoing light at
+ * the bottom of the voxel manipulator.
+ */
+void fill_with_sunlight(MMVManip *vm, INodeDefManager *ndef, v2s16 offset,
+	bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
+{
+	// Distance in array between two nodes on top of each other.
+	s16 ystride = vm->m_area.getExtent().X;
+	// Cache the ignore node.
+	MapNode ignore = MapNode(CONTENT_IGNORE);
+	// For each column of nodes:
+	for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
+	for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
+		// Position of the column on the map.
+		v2s16 realpos = offset + v2s16(x, z);
+		// Array indices in the voxel manipulator
+		s32 maxindex = vm->m_area.index(realpos.X, vm->m_area.MaxEdge.Y,
+			realpos.Y);
+		s32 minindex = vm->m_area.index(realpos.X, vm->m_area.MinEdge.Y,
+			realpos.Y);
+		// True if the current node has sunlight.
+		bool lig = light[z][x];
+		// For each node, downwards:
+		for (s32 i = maxindex; i >= minindex; i -= ystride) {
+			MapNode *n;
+			if (vm->m_flags[i] & VOXELFLAG_NO_DATA)
+				n = &ignore;
+			else
+				n = &vm->m_data[i];
+			// Ignore IGNORE nodes, these are not generated yet.
+			if(n->getContent() == CONTENT_IGNORE)
+				continue;
+			const ContentFeatures &f = ndef->get(n->getContent());
+			if (lig && !f.sunlight_propagates)
+				// Sunlight is stopped.
+				lig = false;
+			// Reset light
+			n->setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
+			n->setLight(LIGHTBANK_NIGHT, 0, f);
+		}
+		// Output outgoing light.
+		light[z][x] = lig;
+	}
+}
+
+/*!
+ * Returns incoming sunlight for one map block.
+ * If block above is not found, it is loaded.
+ *
+ * \param pos position of the map block that gets the sunlight.
+ * \param light incoming sunlight, light[z][x] is true if there
+ * is sunlight above the block at the given z-x relative
+ * node coordinates.
+ */
+void is_sunlight_above_block(ServerMap *map, mapblock_v3 pos,
+	INodeDefManager *ndef, bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
+{
+	mapblock_v3 source_block_pos = pos + v3s16(0, 1, 0);
+	// Get or load source block.
+	// It might take a while to load, but correcting incorrect
+	// sunlight may be even slower.
+	MapBlock *source_block = map->emergeBlock(source_block_pos, false);
+	// Trust only generated blocks.
+	if (source_block == NULL || source_block->isDummy()
+			|| !source_block->isGenerated()) {
+		// But if there is no block above, then use heuristics
+		bool sunlight = true;
+		MapBlock *node_block = map->getBlockNoCreateNoEx(pos);
+		if (node_block == NULL)
+			// This should not happen.
+			sunlight = false;
+		else
+			sunlight = !node_block->getIsUnderground();
+		for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
+		for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
+			light[z][x] = sunlight;
+	} else {
+		// Dummy boolean, the position is valid.
+		bool is_valid_position;
+		// For each column:
+		for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
+		for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
+			// Get the bottom block.
+			MapNode above = source_block->getNodeNoCheck(x, 0, z,
+				&is_valid_position);
+			light[z][x] = above.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN;
+		}
+	}
+}
+
+/*!
+ * Propagates sunlight down in a given map block.
+ *
+ * \param data contains incoming sunlight and shadow and
+ * the coordinates of the target block.
+ * \param unlight propagated shadow is inserted here
+ * \param relight propagated sunlight is inserted here
+ *
+ * \returns true if the block was modified, false otherwise.
+ */
+bool propagate_block_sunlight(Map *map, INodeDefManager *ndef,
+	SunlightPropagationData *data, UnlightQueue *unlight, ReLightQueue *relight)
+{
+	bool modified = false;
+	// Get the block.
+	MapBlock *block = map->getBlockNoCreateNoEx(data->target_block);
+	if (block == NULL || block->isDummy()) {
+		// The work is done if the block does not contain data.
+		data->data.clear();
+		return false;
+	}
+	// Dummy boolean
+	bool is_valid;
+	// For each changing column of nodes:
+	size_t index;
+	for (index = 0; index < data->data.size(); index++) {
+		SunlightPropagationUnit it = data->data[index];
+		// Relative position of the currently inspected node.
+		relative_v3 current_pos(it.relative_pos.X, MAP_BLOCKSIZE - 1,
+			it.relative_pos.Y);
+		if (it.is_sunlit) {
+			// Propagate sunlight.
+			// For each node downwards:
+			for (; current_pos.Y >= 0; current_pos.Y--) {
+				MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
+				const ContentFeatures &f = ndef->get(n);
+				if (n.getLightRaw(LIGHTBANK_DAY, f) < LIGHT_SUN
+						&& f.sunlight_propagates) {
+					// This node gets sunlight.
+					n.setLight(LIGHTBANK_DAY, LIGHT_SUN, f);
+					block->setNodeNoCheck(current_pos, n);
+					modified = true;
+					relight->push(LIGHT_SUN, current_pos, data->target_block,
+						block, 4);
+				} else {
+					// Light already valid, propagation stopped.
+					break;
+				}
+			}
+		} else {
+			// Propagate shadow.
+			// For each node downwards:
+			for (; current_pos.Y >= 0; current_pos.Y--) {
+				MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
+				const ContentFeatures &f = ndef->get(n);
+				if (n.getLightRaw(LIGHTBANK_DAY, f) == LIGHT_SUN) {
+					// The sunlight is no longer valid.
+					n.setLight(LIGHTBANK_DAY, 0, f);
+					block->setNodeNoCheck(current_pos, n);
+					modified = true;
+					unlight->push(LIGHT_SUN, current_pos, data->target_block,
+						block, 4);
+				} else {
+					// Reached shadow, propagation stopped.
+					break;
+				}
+			}
+		}
+		if (current_pos.Y >= 0) {
+			// Propagation stopped, remove from data.
+			data->data[index] = data->data.back();
+			data->data.pop_back();
+			index--;
+		}
+	}
+	return modified;
+}
+
+/*!
+ * Borders of a map block in relative node coordinates.
+ * The areas do not overlap.
+ * Compatible with type 'direction'.
+ */
+const VoxelArea block_pad[] = {
+	VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
+	VoxelArea(v3s16(1, 15, 0), v3s16(14, 15, 15)), //Y+
+	VoxelArea(v3s16(1, 1, 15), v3s16(14, 14, 15)), //Z+
+	VoxelArea(v3s16(1, 1, 0), v3s16(14, 14, 0)),   //Z-
+	VoxelArea(v3s16(1, 0, 0), v3s16(14, 0, 15)),   //Y-
+	VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15))    //X-
+};
+
+void blit_back_with_light(ServerMap *map, MMVManip *vm,
+	std::map<v3s16, MapBlock*> *modified_blocks)
+{
+	INodeDefManager *ndef = map->getNodeDefManager();
+	mapblock_v3 minblock = getNodeBlockPos(vm->m_area.MinEdge);
+	mapblock_v3 maxblock = getNodeBlockPos(vm->m_area.MaxEdge);
+	// First queue is for day light, second is for night light.
+	UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
+	ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
+	// Will hold sunlight data.
+	bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
+	SunlightPropagationData data;
+	// Dummy boolean.
+	bool is_valid;
+
+	// --- STEP 1: reset everything to sunlight
+
+	// For each map block:
+	for (s16 x = minblock.X; x <= maxblock.X; x++)
+	for (s16 z = minblock.Z; z <= maxblock.Z; z++) {
+		// Extract sunlight above.
+		is_sunlight_above_block(map, v3s16(x, maxblock.Y, z), ndef, lights);
+		v2s16 offset(x, z);
+		offset *= MAP_BLOCKSIZE;
+		// Reset the voxel manipulator.
+		fill_with_sunlight(vm, ndef, offset, lights);
+		// Copy sunlight data
+		data.target_block = v3s16(x, minblock.Y - 1, z);
+		for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
+		for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
+			data.data.push_back(
+				SunlightPropagationUnit(v2s16(x, z), lights[z][x]));
+		// Propagate sunlight and shadow below the voxel manipulator.
+		while (!data.data.empty()) {
+			if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
+					&relight[0]))
+				(*modified_blocks)[data.target_block] =
+					map->getBlockNoCreateNoEx(data.target_block);
+			// Step downwards.
+			data.target_block.Y--;
+		}
+	}
+
+	// --- STEP 2: Get nodes from borders to unlight
+
+	// In case there are unloaded holes in the voxel manipulator
+	// unlight each block.
+	// For each block:
+	for (s16 b_x = minblock.X; b_x <= maxblock.X; b_x++)
+	for (s16 b_y = minblock.Y; b_y <= maxblock.Y; b_y++)
+	for (s16 b_z = minblock.Z; b_z <= maxblock.Z; b_z++) {
+		v3s16 blockpos(b_x, b_y, b_z);
+		MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
+		if (!block || block->isDummy())
+			// Skip not existing blocks.
+			continue;
+		v3s16 offset = block->getPosRelative();
+		// For each border of the block:
+		for (direction d = 0; d < 6; d++) {
+			VoxelArea a = block_pad[d];
+			// For each node of the border:
+			for (s32 x = a.MinEdge.X; x <= a.MaxEdge.X; x++)
+			for (s32 z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++)
+			for (s32 y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
+				v3s16 relpos(x, y, z);
+				// Get old and new node
+				MapNode oldnode = block->getNodeNoCheck(x, y, z, &is_valid);
+				const ContentFeatures &oldf = ndef->get(oldnode);
+				MapNode newnode = vm->getNodeNoExNoEmerge(relpos + offset);
+				const ContentFeatures &newf = ndef->get(newnode);
+				// For each light bank
+				for (size_t b = 0; b < 2; b++) {
+					LightBank bank = banks[b];
+					u8 oldlight = oldf.param_type == CPT_LIGHT ?
+						oldnode.getLightNoChecks(bank, &oldf):
+						LIGHT_SUN; // no light information, force unlighting
+					u8 newlight = newf.param_type == CPT_LIGHT ?
+						newnode.getLightNoChecks(bank, &newf):
+						newf.light_source;
+					// If the new node is dimmer, unlight.
+					if (oldlight > newlight) {
+						unlight[b].push(
+							oldlight, relpos, blockpos, block, 6);
+					}
+				} // end of banks
+			} // end of nodes
+		} // end of borders
+	} // end of blocks
+
+	// --- STEP 3: All information extracted, overwrite
+
+	vm->blitBackAll(modified_blocks, true);
+
+	// --- STEP 4: Do unlighting
+
+	for (size_t bank = 0; bank < 2; bank++) {
+		LightBank b = banks[bank];
+		unspread_light(map, ndef, b, unlight[bank], relight[bank],
+			*modified_blocks);
+	}
+
+	// --- STEP 5: Get all newly inserted light sources
+
+	// For each block:
+	for (s16 b_x = minblock.X; b_x <= maxblock.X; b_x++)
+	for (s16 b_y = minblock.Y; b_y <= maxblock.Y; b_y++)
+	for (s16 b_z = minblock.Z; b_z <= maxblock.Z; b_z++) {
+		v3s16 blockpos(b_x, b_y, b_z);
+		MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
+		if (!block || block->isDummy())
+			// Skip not existing blocks
+			continue;
+		// For each node in the block:
+		for (s32 x = 0; x < MAP_BLOCKSIZE; x++)
+		for (s32 z = 0; z < MAP_BLOCKSIZE; z++)
+		for (s32 y = 0; y < MAP_BLOCKSIZE; y++) {
+			v3s16 relpos(x, y, z);
+			MapNode node = block->getNodeNoCheck(x, y, z, &is_valid);
+			const ContentFeatures &f = ndef->get(node);
+			// For each light bank
+			for (size_t b = 0; b < 2; b++) {
+				LightBank bank = banks[b];
+				u8 light = f.param_type == CPT_LIGHT ?
+					node.getLightNoChecks(bank, &f):
+					f.light_source;
+				if (light > 1)
+					relight[b].push(light, relpos, blockpos, block, 6);
+			} // end of banks
+		} // end of nodes
+	} // end of blocks
+
+	// --- STEP 6: do light spreading
+
+	// For each light bank:
+	for (size_t b = 0; b < 2; b++) {
+		LightBank bank = banks[b];
+		// Sunlight is already initialized.
+		u8 maxlight = (b == 0) ? LIGHT_MAX : LIGHT_SUN;
+		// Initialize light values for light spreading.
+		for (u8 i = 0; i <= maxlight; i++) {
+			const std::vector<ChangingLight> &lights = relight[b].lights[i];
+			for (std::vector<ChangingLight>::const_iterator it = lights.begin();
+					it < lights.end(); ++it) {
+				MapNode n = it->block->getNodeNoCheck(it->rel_position,
+					&is_valid);
+				n.setLight(bank, i, ndef);
+				it->block->setNodeNoCheck(it->rel_position, n);
+			}
+		}
+		// Spread lights.
+		spread_light(map, ndef, bank, relight[b], *modified_blocks);
+	}
+}
+
 VoxelLineIterator::VoxelLineIterator(
 	const v3f &start_position,
 	const v3f &line_vector) :