3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as published by
7 the Free Software Foundation; either version 2.1 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 #include "voxelalgorithms.h"
37 * Two directions are opposite only if their sum is 5.
41 * Relative node position.
42 * This represents a node's position in its map block.
43 * All coordinates must be between 0 and 15.
45 typedef v3s16 relative_v3;
47 * Position of a map block (block coordinates).
48 * One block_pos unit is as long as 16 node position units.
50 typedef v3s16 mapblock_v3;
52 //! Contains information about a node whose light is about to change.
53 struct ChangingLight {
54 //! Relative position of the node in its map block.
55 relative_v3 rel_position;
56 //! Position of the node's block.
57 mapblock_v3 block_position;
58 //! Pointer to the node's block.
59 MapBlock *block = NULL;
61 * Direction from the node that caused this node's changing
64 direction source_direction = 6;
66 ChangingLight() = default;
68 ChangingLight(relative_v3 rel_pos, mapblock_v3 block_pos,
69 MapBlock *b, direction source_dir) :
70 rel_position(rel_pos),
71 block_position(block_pos),
73 source_direction(source_dir)
78 * A fast, priority queue-like container to contain ChangingLights.
79 * The ChangingLights are ordered by the given light levels.
80 * The brightest ChangingLight is returned first.
83 //! For each light level there is a vector.
84 std::vector<ChangingLight> lights[LIGHT_SUN + 1];
85 //! Light of the brightest ChangingLight in the queue.
89 * Creates a LightQueue.
90 * \param reserve for each light level that many slots are reserved.
92 LightQueue(size_t reserve)
94 max_light = LIGHT_SUN;
95 for (u8 i = 0; i <= LIGHT_SUN; i++) {
96 lights[i].reserve(reserve);
101 * Returns the next brightest ChangingLight and
102 * removes it from the queue.
103 * If there were no elements in the queue, the given parameters
105 * \param light light level of the popped ChangingLight
106 * \param data the ChangingLight that was popped
107 * \returns true if there was a ChangingLight in the queue.
109 bool next(u8 &light, ChangingLight &data)
111 while (lights[max_light].empty()) {
112 if (max_light == 0) {
118 data = lights[max_light].back();
119 lights[max_light].pop_back();
124 * Adds an element to the queue.
125 * The parameters are the same as in ChangingLight's constructor.
126 * \param light light level of the ChangingLight
128 inline void push(u8 light, relative_v3 rel_pos,
129 mapblock_v3 block_pos, MapBlock *block,
130 direction source_dir)
132 assert(light <= LIGHT_SUN);
133 lights[light].emplace_back(rel_pos, block_pos, block, source_dir);
138 * This type of light queue is for unlighting.
139 * A node can be pushed in it only if its raw light is zero.
140 * This prevents pushing nodes twice into this queue.
141 * The light of the pushed ChangingLight must be the
142 * light of the node before unlighting it.
144 typedef LightQueue UnlightQueue;
146 * This type of light queue is for spreading lights.
147 * While spreading lights, all the nodes in it must
148 * have the same light as the light level the ChangingLights
149 * were pushed into this queue with. This prevents unnecessary
150 * re-pushing of the nodes into the queue.
151 * If a node doesn't let light trough but emits light, it can be added
154 typedef LightQueue ReLightQueue;
157 * neighbor_dirs[i] points towards
159 * See the definition of the type "direction"
161 const static v3s16 neighbor_dirs[6] = {
162 v3s16(1, 0, 0), // right
163 v3s16(0, 1, 0), // top
164 v3s16(0, 0, 1), // back
165 v3s16(0, 0, -1), // front
166 v3s16(0, -1, 0), // bottom
167 v3s16(-1, 0, 0), // left
171 * Transforms the given map block offset by one node towards
172 * the specified direction.
173 * \param dir the direction of the transformation
174 * \param rel_pos the node's relative position in its map block
175 * \param block_pos position of the node's block
177 bool step_rel_block_pos(direction dir, relative_v3 &rel_pos,
178 mapblock_v3 &block_pos)
182 if (rel_pos.X < MAP_BLOCKSIZE - 1) {
191 if (rel_pos.Y < MAP_BLOCKSIZE - 1) {
200 if (rel_pos.Z < MAP_BLOCKSIZE - 1) {
212 rel_pos.Z = MAP_BLOCKSIZE - 1;
221 rel_pos.Y = MAP_BLOCKSIZE - 1;
230 rel_pos.X = MAP_BLOCKSIZE - 1;
240 * Removes all light that is potentially emitted by the specified
241 * light sources. These nodes will have zero light.
242 * Returns all nodes whose light became zero but should be re-lighted.
244 * \param bank the light bank in which the procedure operates
245 * \param from_nodes nodes whose light is removed
246 * \param light_sources nodes that should be re-lighted
247 * \param modified_blocks output, all modified map blocks are added to this
249 void unspread_light(Map *map, const NodeDefManager *nodemgr, LightBank bank,
250 UnlightQueue &from_nodes, ReLightQueue &light_sources,
251 std::map<v3s16, MapBlock*> &modified_blocks)
253 // Stores data popped from from_nodes
255 ChangingLight current;
256 // Data of the current neighbor
257 mapblock_v3 neighbor_block_pos;
258 relative_v3 neighbor_rel_pos;
260 bool is_valid_position;
261 // Direction of the brightest neighbor of the node
262 direction source_dir;
263 while (from_nodes.next(current_light, current)) {
264 // For all nodes that need unlighting
266 // There is no brightest neighbor
269 const MapNode &node = current.block->getNodeNoCheck(
270 current.rel_position, &is_valid_position);
271 const ContentFeatures &f = nodemgr->get(node);
272 // If the node emits light, it behaves like it had a
273 // brighter neighbor.
274 u8 brightest_neighbor_light = f.light_source + 1;
275 for (direction i = 0; i < 6; i++) {
278 // The node that changed this node has already zero light
279 // and it can't give light to this node
280 if (current.source_direction + i == 5) {
283 // Get the neighbor's position and block
284 neighbor_rel_pos = current.rel_position;
285 neighbor_block_pos = current.block_position;
286 MapBlock *neighbor_block;
287 if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
288 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
289 if (neighbor_block == NULL) {
290 current.block->setLightingComplete(bank, i, false);
294 neighbor_block = current.block;
296 // Get the neighbor itself
297 MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
299 const ContentFeatures &neighbor_f = nodemgr->get(
300 neighbor.getContent());
301 u8 neighbor_light = neighbor.getLightRaw(bank, neighbor_f);
302 // If the neighbor has at least as much light as this node, then
303 // it won't lose its light, since it should have been added to
304 // from_nodes earlier, so its light would be zero.
305 if (neighbor_f.light_propagates && neighbor_light < current_light) {
306 // Unlight, but only if the node has light.
307 if (neighbor_light > 0) {
308 neighbor.setLight(bank, 0, neighbor_f);
309 neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
310 from_nodes.push(neighbor_light, neighbor_rel_pos,
311 neighbor_block_pos, neighbor_block, i);
312 // The current node was modified earlier, so its block
313 // is in modified_blocks.
314 if (current.block != neighbor_block) {
315 modified_blocks[neighbor_block_pos] = neighbor_block;
319 // The neighbor can light up this node.
320 if (neighbor_light < neighbor_f.light_source) {
321 neighbor_light = neighbor_f.light_source;
323 if (brightest_neighbor_light < neighbor_light) {
324 brightest_neighbor_light = neighbor_light;
329 // If the brightest neighbor is able to light up this node,
330 // then add this node to the output nodes.
331 if (brightest_neighbor_light > 1 && f.light_propagates) {
332 brightest_neighbor_light--;
333 light_sources.push(brightest_neighbor_light, current.rel_position,
334 current.block_position, current.block,
335 (source_dir == 6) ? 6 : 5 - source_dir
336 /* with opposite direction*/);
342 * Spreads light from the specified starting nodes.
344 * Before calling this procedure, make sure that all ChangingLights
345 * in light_sources have as much light on the map as they have in
346 * light_sources (if the queue contains a node multiple times, the brightest
347 * occurrence counts).
349 * \param bank the light bank in which the procedure operates
350 * \param light_sources starting nodes
351 * \param modified_blocks output, all modified map blocks are added to this
353 void spread_light(Map *map, const NodeDefManager *nodemgr, LightBank bank,
354 LightQueue &light_sources,
355 std::map<v3s16, MapBlock*> &modified_blocks)
357 // The light the current node can provide to its neighbors.
359 // The ChangingLight for the current node.
360 ChangingLight current;
361 // Position of the current neighbor.
362 mapblock_v3 neighbor_block_pos;
363 relative_v3 neighbor_rel_pos;
365 bool is_valid_position;
366 while (light_sources.next(spreading_light, current)) {
368 for (direction i = 0; i < 6; i++) {
369 // This node can't light up its light source
370 if (current.source_direction + i == 5) {
373 // Get the neighbor's position and block
374 neighbor_rel_pos = current.rel_position;
375 neighbor_block_pos = current.block_position;
376 MapBlock *neighbor_block;
377 if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
378 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
379 if (neighbor_block == NULL) {
380 current.block->setLightingComplete(bank, i, false);
384 neighbor_block = current.block;
386 // Get the neighbor itself
387 MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
389 const ContentFeatures &f = nodemgr->get(neighbor.getContent());
390 if (f.light_propagates) {
391 // Light up the neighbor, if it has less light than it should.
392 u8 neighbor_light = neighbor.getLightRaw(bank, f);
393 if (neighbor_light < spreading_light) {
394 neighbor.setLight(bank, spreading_light, f);
395 neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
396 light_sources.push(spreading_light, neighbor_rel_pos,
397 neighbor_block_pos, neighbor_block, i);
398 // The current node was modified earlier, so its block
399 // is in modified_blocks.
400 if (current.block != neighbor_block) {
401 modified_blocks[neighbor_block_pos] = neighbor_block;
409 struct SunlightPropagationUnit{
413 SunlightPropagationUnit(v2s16 relpos, bool sunlit):
414 relative_pos(relpos),
419 struct SunlightPropagationData{
420 std::vector<SunlightPropagationUnit> data;
425 * Returns true if the node gets sunlight from the
428 * \param pos position of the node.
430 bool is_sunlight_above(Map *map, v3s16 pos, const NodeDefManager *ndef)
432 bool sunlight = true;
433 mapblock_v3 source_block_pos;
434 relative_v3 source_rel_pos;
435 getNodeBlockPosWithOffset(pos + v3s16(0, 1, 0), source_block_pos,
437 // If the node above has sunlight, this node also can get it.
438 MapBlock *source_block = map->getBlockNoCreateNoEx(source_block_pos);
439 if (source_block == NULL) {
440 // But if there is no node above, then use heuristics
441 MapBlock *node_block = map->getBlockNoCreateNoEx(getNodeBlockPos(pos));
442 if (node_block == NULL) {
445 sunlight = !node_block->getIsUnderground();
448 bool is_valid_position;
449 MapNode above = source_block->getNodeNoCheck(source_rel_pos,
451 if (is_valid_position) {
452 if (above.getContent() == CONTENT_IGNORE) {
454 if (source_block->getIsUnderground()) {
457 } else if (above.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
458 // If the node above doesn't have sunlight, this
459 // node is in shadow.
467 static const LightBank banks[] = { LIGHTBANK_DAY, LIGHTBANK_NIGHT };
469 void update_lighting_nodes(Map *map,
470 const std::vector<std::pair<v3s16, MapNode>> &oldnodes,
471 std::map<v3s16, MapBlock*> &modified_blocks)
473 const NodeDefManager *ndef = map->getNodeDefManager();
474 // For node getter functions
475 bool is_valid_position;
477 // Process each light bank separately
478 for (LightBank bank : banks) {
479 UnlightQueue disappearing_lights(256);
480 ReLightQueue light_sources(256);
481 // Nodes that are brighter than the brightest modified node was
482 // won't change, since they didn't get their light from a
484 u8 min_safe_light = 0;
485 for (auto it = oldnodes.cbegin(); it < oldnodes.cend(); ++it) {
486 u8 old_light = it->second.getLight(bank, ndef);
487 if (old_light > min_safe_light) {
488 min_safe_light = old_light;
491 // If only one node changed, even nodes with the same brightness
492 // didn't get their light from the changed node.
493 if (oldnodes.size() > 1) {
496 // For each changed node process sunlight and initialize
497 for (auto it = oldnodes.cbegin(); it < oldnodes.cend(); ++it) {
498 // Get position and block of the changed node
501 mapblock_v3 block_pos;
502 getNodeBlockPosWithOffset(p, block_pos, rel_pos);
503 MapBlock *block = map->getBlockNoCreateNoEx(block_pos);
504 if (block == NULL || block->isDummy()) {
508 MapNode n = block->getNodeNoCheck(rel_pos, &is_valid_position);
509 if (!is_valid_position) {
513 // Light of the old node
514 u8 old_light = it->second.getLight(bank, ndef);
516 // Add the block of the added node to modified_blocks
517 modified_blocks[block_pos] = block;
519 // Get new light level of the node
521 if (ndef->get(n).light_propagates) {
522 if (bank == LIGHTBANK_DAY && ndef->get(n).sunlight_propagates
523 && is_sunlight_above(map, p, ndef)) {
524 new_light = LIGHT_SUN;
526 new_light = ndef->get(n).light_source;
527 for (const v3s16 &neighbor_dir : neighbor_dirs) {
528 v3s16 p2 = p + neighbor_dir;
530 MapNode n2 = map->getNode(p2, &is_valid);
532 u8 spread = n2.getLight(bank, ndef);
533 // If it is sure that the neighbor won't be
534 // unlighted, its light can spread to this node.
535 if (spread > new_light && spread >= min_safe_light) {
536 new_light = spread - 1;
542 // If this is an opaque node, it still can emit light.
543 new_light = ndef->get(n).light_source;
547 light_sources.push(new_light, rel_pos, block_pos, block, 6);
550 if (new_light < old_light) {
551 // The node became opaque or doesn't provide as much
552 // light as the previous one, so it must be unlighted.
554 // Add to unlight queue
555 n.setLight(bank, 0, ndef);
556 block->setNodeNoCheck(rel_pos, n);
557 disappearing_lights.push(old_light, rel_pos, block_pos, block,
560 // Remove sunlight, if there was any
561 if (bank == LIGHTBANK_DAY && old_light == LIGHT_SUN) {
562 for (s16 y = p.Y - 1;; y--) {
563 v3s16 n2pos(p.X, y, p.Z);
567 n2 = map->getNode(n2pos, &is_valid_position);
568 if (!is_valid_position)
571 // If this node doesn't have sunlight, the nodes below
572 // it don't have too.
573 if (n2.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
576 // Remove sunlight and add to unlight queue.
577 n2.setLight(LIGHTBANK_DAY, 0, ndef);
578 map->setNode(n2pos, n2);
579 relative_v3 rel_pos2;
580 mapblock_v3 block_pos2;
581 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
582 MapBlock *block2 = map->getBlockNoCreateNoEx(
584 disappearing_lights.push(LIGHT_SUN, rel_pos2,
586 4 /* The node above caused the change */);
589 } else if (new_light > old_light) {
590 // It is sure that the node provides more light than the previous
591 // one, unlighting is not necessary.
592 // Propagate sunlight
593 if (bank == LIGHTBANK_DAY && new_light == LIGHT_SUN) {
594 for (s16 y = p.Y - 1;; y--) {
595 v3s16 n2pos(p.X, y, p.Z);
599 n2 = map->getNode(n2pos, &is_valid_position);
600 if (!is_valid_position)
603 // This should not happen, but if the node has sunlight
604 // then the iteration should stop.
605 if (n2.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN) {
608 // If the node terminates sunlight, stop.
609 if (!ndef->get(n2).sunlight_propagates) {
612 relative_v3 rel_pos2;
613 mapblock_v3 block_pos2;
614 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
615 MapBlock *block2 = map->getBlockNoCreateNoEx(
617 // Mark node for lighting.
618 light_sources.push(LIGHT_SUN, rel_pos2, block_pos2,
626 unspread_light(map, ndef, bank, disappearing_lights, light_sources,
628 // Initialize light values for light spreading.
629 for (u8 i = 0; i <= LIGHT_SUN; i++) {
630 const std::vector<ChangingLight> &lights = light_sources.lights[i];
631 for (std::vector<ChangingLight>::const_iterator it = lights.begin();
632 it < lights.end(); ++it) {
633 MapNode n = it->block->getNodeNoCheck(it->rel_position,
635 n.setLight(bank, i, ndef);
636 it->block->setNodeNoCheck(it->rel_position, n);
640 spread_light(map, ndef, bank, light_sources, modified_blocks);
645 * Borders of a map block in relative node coordinates.
646 * Compatible with type 'direction'.
648 const VoxelArea block_borders[] = {
649 VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
650 VoxelArea(v3s16(0, 15, 0), v3s16(15, 15, 15)), //Y+
651 VoxelArea(v3s16(0, 0, 15), v3s16(15, 15, 15)), //Z+
652 VoxelArea(v3s16(0, 0, 0), v3s16(15, 15, 0)), //Z-
653 VoxelArea(v3s16(0, 0, 0), v3s16(15, 0, 15)), //Y-
654 VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15)) //X-
659 * -the node has unloaded neighbors
660 * -the node doesn't have light
661 * -the node's light is the same as the maximum of
662 * its light source and its brightest neighbor minus one.
665 bool is_light_locally_correct(Map *map, const NodeDefManager *ndef,
666 LightBank bank, v3s16 pos)
668 bool is_valid_position;
669 MapNode n = map->getNode(pos, &is_valid_position);
670 const ContentFeatures &f = ndef->get(n);
671 if (f.param_type != CPT_LIGHT) {
674 u8 light = n.getLightNoChecks(bank, &f);
675 assert(f.light_source <= LIGHT_MAX);
676 u8 brightest_neighbor = f.light_source + 1;
677 for (const v3s16 &neighbor_dir : neighbor_dirs) {
678 MapNode n2 = map->getNode(pos + neighbor_dir,
680 u8 light2 = n2.getLight(bank, ndef);
681 if (brightest_neighbor < light2) {
682 brightest_neighbor = light2;
685 assert(light <= LIGHT_SUN);
686 return brightest_neighbor == light + 1;
689 void update_block_border_lighting(Map *map, MapBlock *block,
690 std::map<v3s16, MapBlock*> &modified_blocks)
692 const NodeDefManager *ndef = map->getNodeDefManager();
693 bool is_valid_position;
694 for (LightBank bank : banks) {
695 // Since invalid light is not common, do not allocate
696 // memory if not needed.
697 UnlightQueue disappearing_lights(0);
698 ReLightQueue light_sources(0);
699 // Get incorrect lights
700 for (direction d = 0; d < 6; d++) {
701 // For each direction
702 // Get neighbor block
703 v3s16 otherpos = block->getPos() + neighbor_dirs[d];
704 MapBlock *other = map->getBlockNoCreateNoEx(otherpos);
708 // Only update if lighting was not completed.
709 if (block->isLightingComplete(bank, d) &&
710 other->isLightingComplete(bank, 5 - d))
713 block->setLightingComplete(bank, d, true);
714 other->setLightingComplete(bank, 5 - d, true);
715 // The two blocks and their connecting surfaces
716 MapBlock *blocks[] = {block, other};
717 VoxelArea areas[] = {block_borders[d], block_borders[5 - d]};
719 for (u8 blocknum = 0; blocknum < 2; blocknum++) {
720 MapBlock *b = blocks[blocknum];
721 VoxelArea a = areas[blocknum];
723 for (s32 x = a.MinEdge.X; x <= a.MaxEdge.X; x++)
724 for (s32 z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++)
725 for (s32 y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
726 MapNode n = b->getNodeNoCheck(x, y, z,
728 u8 light = n.getLight(bank, ndef);
730 if (light < LIGHT_SUN) {
731 // Unlight if not correct
732 if (!is_light_locally_correct(map, ndef, bank,
733 v3s16(x, y, z) + b->getPosRelative())) {
734 // Initialize for unlighting
735 n.setLight(bank, 0, ndef);
736 b->setNodeNoCheck(x, y, z, n);
737 modified_blocks[b->getPos()]=b;
738 disappearing_lights.push(light,
739 relative_v3(x, y, z), b->getPos(), b,
747 unspread_light(map, ndef, bank, disappearing_lights, light_sources,
749 // Initialize light values for light spreading.
750 for (u8 i = 0; i <= LIGHT_SUN; i++) {
751 const std::vector<ChangingLight> &lights = light_sources.lights[i];
752 for (std::vector<ChangingLight>::const_iterator it = lights.begin();
753 it < lights.end(); ++it) {
754 MapNode n = it->block->getNodeNoCheck(it->rel_position,
756 n.setLight(bank, i, ndef);
757 it->block->setNodeNoCheck(it->rel_position, n);
761 spread_light(map, ndef, bank, light_sources, modified_blocks);
766 * Resets the lighting of the given VoxelManipulator to
767 * complete darkness and full sunlight.
768 * Operates in one map sector.
770 * \param offset contains the least x and z node coordinates
772 * \param light incoming sunlight, light[x][z] is true if there
773 * is sunlight above the voxel manipulator at the given x-z coordinates.
774 * The array's indices are relative node coordinates in the sector.
775 * After the procedure returns, this contains outgoing light at
776 * the bottom of the voxel manipulator.
778 void fill_with_sunlight(MMVManip *vm, const NodeDefManager *ndef, v2s16 offset,
779 bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
781 // Distance in array between two nodes on top of each other.
782 s16 ystride = vm->m_area.getExtent().X;
783 // Cache the ignore node.
784 MapNode ignore = MapNode(CONTENT_IGNORE);
785 // For each column of nodes:
786 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
787 for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
788 // Position of the column on the map.
789 v2s16 realpos = offset + v2s16(x, z);
790 // Array indices in the voxel manipulator
791 s32 maxindex = vm->m_area.index(realpos.X, vm->m_area.MaxEdge.Y,
793 s32 minindex = vm->m_area.index(realpos.X, vm->m_area.MinEdge.Y,
795 // True if the current node has sunlight.
796 bool lig = light[z][x];
797 // For each node, downwards:
798 for (s32 i = maxindex; i >= minindex; i -= ystride) {
800 if (vm->m_flags[i] & VOXELFLAG_NO_DATA)
804 // Ignore IGNORE nodes, these are not generated yet.
805 if(n->getContent() == CONTENT_IGNORE)
807 const ContentFeatures &f = ndef->get(n->getContent());
808 if (lig && !f.sunlight_propagates)
809 // Sunlight is stopped.
812 n->setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
813 n->setLight(LIGHTBANK_NIGHT, 0, f);
815 // Output outgoing light.
821 * Returns incoming sunlight for one map block.
822 * If block above is not found, it is loaded.
824 * \param pos position of the map block that gets the sunlight.
825 * \param light incoming sunlight, light[z][x] is true if there
826 * is sunlight above the block at the given z-x relative
829 void is_sunlight_above_block(ServerMap *map, mapblock_v3 pos,
830 const NodeDefManager *ndef, bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
832 mapblock_v3 source_block_pos = pos + v3s16(0, 1, 0);
833 // Get or load source block.
834 // It might take a while to load, but correcting incorrect
835 // sunlight may be even slower.
836 MapBlock *source_block = map->emergeBlock(source_block_pos, false);
837 // Trust only generated blocks.
838 if (source_block == NULL || source_block->isDummy()
839 || !source_block->isGenerated()) {
840 // But if there is no block above, then use heuristics
841 bool sunlight = true;
842 MapBlock *node_block = map->getBlockNoCreateNoEx(pos);
843 if (node_block == NULL)
844 // This should not happen.
847 sunlight = !node_block->getIsUnderground();
848 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
849 for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
850 light[z][x] = sunlight;
852 // Dummy boolean, the position is valid.
853 bool is_valid_position;
855 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
856 for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
857 // Get the bottom block.
858 MapNode above = source_block->getNodeNoCheck(x, 0, z,
860 light[z][x] = above.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN;
866 * Propagates sunlight down in a given map block.
868 * \param data contains incoming sunlight and shadow and
869 * the coordinates of the target block.
870 * \param unlight propagated shadow is inserted here
871 * \param relight propagated sunlight is inserted here
873 * \returns true if the block was modified, false otherwise.
875 bool propagate_block_sunlight(Map *map, const NodeDefManager *ndef,
876 SunlightPropagationData *data, UnlightQueue *unlight, ReLightQueue *relight)
878 bool modified = false;
880 MapBlock *block = map->getBlockNoCreateNoEx(data->target_block);
881 if (block == NULL || block->isDummy()) {
882 // The work is done if the block does not contain data.
888 // For each changing column of nodes:
890 for (index = 0; index < data->data.size(); index++) {
891 SunlightPropagationUnit it = data->data[index];
892 // Relative position of the currently inspected node.
893 relative_v3 current_pos(it.relative_pos.X, MAP_BLOCKSIZE - 1,
896 // Propagate sunlight.
897 // For each node downwards:
898 for (; current_pos.Y >= 0; current_pos.Y--) {
899 MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
900 const ContentFeatures &f = ndef->get(n);
901 if (n.getLightRaw(LIGHTBANK_DAY, f) < LIGHT_SUN
902 && f.sunlight_propagates) {
903 // This node gets sunlight.
904 n.setLight(LIGHTBANK_DAY, LIGHT_SUN, f);
905 block->setNodeNoCheck(current_pos, n);
907 relight->push(LIGHT_SUN, current_pos, data->target_block,
910 // Light already valid, propagation stopped.
916 // For each node downwards:
917 for (; current_pos.Y >= 0; current_pos.Y--) {
918 MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
919 const ContentFeatures &f = ndef->get(n);
920 if (n.getLightRaw(LIGHTBANK_DAY, f) == LIGHT_SUN) {
921 // The sunlight is no longer valid.
922 n.setLight(LIGHTBANK_DAY, 0, f);
923 block->setNodeNoCheck(current_pos, n);
925 unlight->push(LIGHT_SUN, current_pos, data->target_block,
928 // Reached shadow, propagation stopped.
933 if (current_pos.Y >= 0) {
934 // Propagation stopped, remove from data.
935 data->data[index] = data->data.back();
936 data->data.pop_back();
944 * Borders of a map block in relative node coordinates.
945 * The areas do not overlap.
946 * Compatible with type 'direction'.
948 const VoxelArea block_pad[] = {
949 VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
950 VoxelArea(v3s16(1, 15, 0), v3s16(14, 15, 15)), //Y+
951 VoxelArea(v3s16(1, 1, 15), v3s16(14, 14, 15)), //Z+
952 VoxelArea(v3s16(1, 1, 0), v3s16(14, 14, 0)), //Z-
953 VoxelArea(v3s16(1, 0, 0), v3s16(14, 0, 15)), //Y-
954 VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15)) //X-
958 * The common part of bulk light updates - it is always executed.
959 * The procedure takes the nodes that should be unlit, and the
960 * full modified area.
962 * The procedure handles the correction of all lighting except
963 * direct sunlight spreading.
965 * \param minblock least coordinates of the changed area in block
967 * \param maxblock greatest coordinates of the changed area in block
969 * \param unlight the first queue is for day light, the second is for
970 * night light. Contains all nodes on the borders that need to be unlit.
971 * \param relight the first queue is for day light, the second is for
972 * night light. Contains nodes that were not modified, but got sunlight
973 * because the changes.
974 * \param modified_blocks the procedure adds all modified blocks to
977 void finish_bulk_light_update(Map *map, mapblock_v3 minblock,
978 mapblock_v3 maxblock, UnlightQueue unlight[2], ReLightQueue relight[2],
979 std::map<v3s16, MapBlock*> *modified_blocks)
981 const NodeDefManager *ndef = map->getNodeDefManager();
985 // --- STEP 1: Do unlighting
987 for (size_t bank = 0; bank < 2; bank++) {
988 LightBank b = banks[bank];
989 unspread_light(map, ndef, b, unlight[bank], relight[bank],
993 // --- STEP 2: Get all newly inserted light sources
998 for (blockpos.X = minblock.X; blockpos.X <= maxblock.X; blockpos.X++)
999 for (blockpos.Y = minblock.Y; blockpos.Y <= maxblock.Y; blockpos.Y++)
1000 for (blockpos.Z = minblock.Z; blockpos.Z <= maxblock.Z; blockpos.Z++) {
1001 MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
1002 if (!block || block->isDummy())
1003 // Skip not existing blocks
1005 // For each node in the block:
1006 for (relpos.X = 0; relpos.X < MAP_BLOCKSIZE; relpos.X++)
1007 for (relpos.Z = 0; relpos.Z < MAP_BLOCKSIZE; relpos.Z++)
1008 for (relpos.Y = 0; relpos.Y < MAP_BLOCKSIZE; relpos.Y++) {
1009 MapNode node = block->getNodeNoCheck(relpos.X, relpos.Y, relpos.Z, &is_valid);
1010 const ContentFeatures &f = ndef->get(node);
1012 // For each light bank
1013 for (size_t b = 0; b < 2; b++) {
1014 LightBank bank = banks[b];
1015 u8 light = f.param_type == CPT_LIGHT ?
1016 node.getLightNoChecks(bank, &f):
1019 relight[b].push(light, relpos, blockpos, block, 6);
1024 // --- STEP 3: do light spreading
1026 // For each light bank:
1027 for (size_t b = 0; b < 2; b++) {
1028 LightBank bank = banks[b];
1029 // Sunlight is already initialized.
1030 u8 maxlight = (b == 0) ? LIGHT_MAX : LIGHT_SUN;
1031 // Initialize light values for light spreading.
1032 for (u8 i = 0; i <= maxlight; i++) {
1033 const std::vector<ChangingLight> &lights = relight[b].lights[i];
1034 for (std::vector<ChangingLight>::const_iterator it = lights.begin();
1035 it < lights.end(); ++it) {
1036 MapNode n = it->block->getNodeNoCheck(it->rel_position,
1038 n.setLight(bank, i, ndef);
1039 it->block->setNodeNoCheck(it->rel_position, n);
1043 spread_light(map, ndef, bank, relight[b], *modified_blocks);
1047 void blit_back_with_light(ServerMap *map, MMVManip *vm,
1048 std::map<v3s16, MapBlock*> *modified_blocks)
1050 const NodeDefManager *ndef = map->getNodeDefManager();
1051 mapblock_v3 minblock = getNodeBlockPos(vm->m_area.MinEdge);
1052 mapblock_v3 maxblock = getNodeBlockPos(vm->m_area.MaxEdge);
1053 // First queue is for day light, second is for night light.
1054 UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
1055 ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
1056 // Will hold sunlight data.
1057 bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
1058 SunlightPropagationData data;
1062 // --- STEP 1: reset everything to sunlight
1064 // For each map block:
1065 for (s16 x = minblock.X; x <= maxblock.X; x++)
1066 for (s16 z = minblock.Z; z <= maxblock.Z; z++) {
1067 // Extract sunlight above.
1068 is_sunlight_above_block(map, v3s16(x, maxblock.Y, z), ndef, lights);
1070 offset *= MAP_BLOCKSIZE;
1071 // Reset the voxel manipulator.
1072 fill_with_sunlight(vm, ndef, offset, lights);
1073 // Copy sunlight data
1074 data.target_block = v3s16(x, minblock.Y - 1, z);
1075 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
1076 for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
1077 data.data.emplace_back(v2s16(x, z), lights[z][x]);
1078 // Propagate sunlight and shadow below the voxel manipulator.
1079 while (!data.data.empty()) {
1080 if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
1082 (*modified_blocks)[data.target_block] =
1083 map->getBlockNoCreateNoEx(data.target_block);
1085 data.target_block.Y--;
1089 // --- STEP 2: Get nodes from borders to unlight
1093 // In case there are unloaded holes in the voxel manipulator
1094 // unlight each block.
1096 for (blockpos.X = minblock.X; blockpos.X <= maxblock.X; blockpos.X++)
1097 for (blockpos.Y = minblock.Y; blockpos.Y <= maxblock.Y; blockpos.Y++)
1098 for (blockpos.Z = minblock.Z; blockpos.Z <= maxblock.Z; blockpos.Z++) {
1099 MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
1100 if (!block || block->isDummy())
1101 // Skip not existing blocks.
1103 v3s16 offset = block->getPosRelative();
1104 // For each border of the block:
1105 for (const VoxelArea &a : block_pad) {
1106 // For each node of the border:
1107 for (relpos.X = a.MinEdge.X; relpos.X <= a.MaxEdge.X; relpos.X++)
1108 for (relpos.Z = a.MinEdge.Z; relpos.Z <= a.MaxEdge.Z; relpos.Z++)
1109 for (relpos.Y = a.MinEdge.Y; relpos.Y <= a.MaxEdge.Y; relpos.Y++) {
1111 // Get old and new node
1112 MapNode oldnode = block->getNodeNoCheck(relpos, &is_valid);
1113 const ContentFeatures &oldf = ndef->get(oldnode);
1114 MapNode newnode = vm->getNodeNoExNoEmerge(relpos + offset);
1115 const ContentFeatures &newf = oldnode == newnode ? oldf :
1118 // For each light bank
1119 for (size_t b = 0; b < 2; b++) {
1120 LightBank bank = banks[b];
1121 u8 oldlight = oldf.param_type == CPT_LIGHT ?
1122 oldnode.getLightNoChecks(bank, &oldf):
1123 LIGHT_SUN; // no light information, force unlighting
1124 u8 newlight = newf.param_type == CPT_LIGHT ?
1125 newnode.getLightNoChecks(bank, &newf):
1127 // If the new node is dimmer, unlight.
1128 if (oldlight > newlight) {
1130 oldlight, relpos, blockpos, block, 6);
1137 // --- STEP 3: All information extracted, overwrite
1139 vm->blitBackAll(modified_blocks, true);
1141 // --- STEP 4: Finish light update
1143 finish_bulk_light_update(map, minblock, maxblock, unlight, relight,
1148 * Resets the lighting of the given map block to
1149 * complete darkness and full sunlight.
1151 * \param light incoming sunlight, light[x][z] is true if there
1152 * is sunlight above the map block at the given x-z coordinates.
1153 * The array's indices are relative node coordinates in the block.
1154 * After the procedure returns, this contains outgoing light at
1155 * the bottom of the map block.
1157 void fill_with_sunlight(MapBlock *block, const NodeDefManager *ndef,
1158 bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
1160 if (block->isDummy())
1164 // For each column of nodes:
1165 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
1166 for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
1167 // True if the current node has sunlight.
1168 bool lig = light[z][x];
1169 // For each node, downwards:
1170 for (s16 y = MAP_BLOCKSIZE - 1; y >= 0; y--) {
1171 MapNode n = block->getNodeNoCheck(x, y, z, &is_valid);
1172 // Ignore IGNORE nodes, these are not generated yet.
1173 if (n.getContent() == CONTENT_IGNORE)
1175 const ContentFeatures &f = ndef->get(n.getContent());
1176 if (lig && !f.sunlight_propagates) {
1177 // Sunlight is stopped.
1181 n.setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
1182 n.setLight(LIGHTBANK_NIGHT, 0, f);
1183 block->setNodeNoCheck(x, y, z, n);
1185 // Output outgoing light.
1190 void repair_block_light(ServerMap *map, MapBlock *block,
1191 std::map<v3s16, MapBlock*> *modified_blocks)
1193 if (!block || block->isDummy())
1195 const NodeDefManager *ndef = map->getNodeDefManager();
1196 // First queue is for day light, second is for night light.
1197 UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
1198 ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
1199 // Will hold sunlight data.
1200 bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
1201 SunlightPropagationData data;
1205 // --- STEP 1: reset everything to sunlight
1207 mapblock_v3 blockpos = block->getPos();
1208 (*modified_blocks)[blockpos] = block;
1209 // For each map block:
1210 // Extract sunlight above.
1211 is_sunlight_above_block(map, blockpos, ndef, lights);
1212 // Reset the voxel manipulator.
1213 fill_with_sunlight(block, ndef, lights);
1214 // Copy sunlight data
1215 data.target_block = v3s16(blockpos.X, blockpos.Y - 1, blockpos.Z);
1216 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
1217 for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
1218 data.data.emplace_back(v2s16(x, z), lights[z][x]);
1220 // Propagate sunlight and shadow below the voxel manipulator.
1221 while (!data.data.empty()) {
1222 if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
1224 (*modified_blocks)[data.target_block] =
1225 map->getBlockNoCreateNoEx(data.target_block);
1227 data.target_block.Y--;
1230 // --- STEP 2: Get nodes from borders to unlight
1232 // For each border of the block:
1233 for (const VoxelArea &a : block_pad) {
1235 // For each node of the border:
1236 for (relpos.X = a.MinEdge.X; relpos.X <= a.MaxEdge.X; relpos.X++)
1237 for (relpos.Z = a.MinEdge.Z; relpos.Z <= a.MaxEdge.Z; relpos.Z++)
1238 for (relpos.Y = a.MinEdge.Y; relpos.Y <= a.MaxEdge.Y; relpos.Y++) {
1241 MapNode node = block->getNodeNoCheck(relpos, &is_valid);
1242 const ContentFeatures &f = ndef->get(node);
1243 // For each light bank
1244 for (size_t b = 0; b < 2; b++) {
1245 LightBank bank = banks[b];
1246 u8 light = f.param_type == CPT_LIGHT ?
1247 node.getLightNoChecks(bank, &f):
1249 // If the new node is dimmer than sunlight, unlight.
1250 // (if it has maximal light, it is pointless to remove
1251 // surrounding light, as it can only become brighter)
1252 if (LIGHT_SUN > light) {
1254 LIGHT_SUN, relpos, blockpos, block, 6);
1260 // STEP 3: Remove and spread light
1262 finish_bulk_light_update(map, blockpos, blockpos, unlight, relight,
1266 VoxelLineIterator::VoxelLineIterator(const v3f &start_position, const v3f &line_vector) :
1267 m_start_position(start_position),
1268 m_line_vector(line_vector)
1270 m_current_node_pos = floatToInt(m_start_position, 1);
1271 m_start_node_pos = m_current_node_pos;
1272 m_last_index = getIndex(floatToInt(start_position + line_vector, 1));
1274 if (m_line_vector.X > 0) {
1275 m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5) + 1.5
1276 - m_start_position.X) / m_line_vector.X;
1277 m_intersection_multi_inc.X = 1 / m_line_vector.X;
1278 } else if (m_line_vector.X < 0) {
1279 m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5)
1280 - m_start_position.X + 0.5) / m_line_vector.X;
1281 m_intersection_multi_inc.X = -1 / m_line_vector.X;
1282 m_step_directions.X = -1;
1285 if (m_line_vector.Y > 0) {
1286 m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5) + 1.5
1287 - m_start_position.Y) / m_line_vector.Y;
1288 m_intersection_multi_inc.Y = 1 / m_line_vector.Y;
1289 } else if (m_line_vector.Y < 0) {
1290 m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5)
1291 - m_start_position.Y + 0.5) / m_line_vector.Y;
1292 m_intersection_multi_inc.Y = -1 / m_line_vector.Y;
1293 m_step_directions.Y = -1;
1296 if (m_line_vector.Z > 0) {
1297 m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5) + 1.5
1298 - m_start_position.Z) / m_line_vector.Z;
1299 m_intersection_multi_inc.Z = 1 / m_line_vector.Z;
1300 } else if (m_line_vector.Z < 0) {
1301 m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5)
1302 - m_start_position.Z + 0.5) / m_line_vector.Z;
1303 m_intersection_multi_inc.Z = -1 / m_line_vector.Z;
1304 m_step_directions.Z = -1;
1308 void VoxelLineIterator::next()
1311 if ((m_next_intersection_multi.X < m_next_intersection_multi.Y)
1312 && (m_next_intersection_multi.X < m_next_intersection_multi.Z)) {
1313 m_next_intersection_multi.X += m_intersection_multi_inc.X;
1314 m_current_node_pos.X += m_step_directions.X;
1315 } else if ((m_next_intersection_multi.Y < m_next_intersection_multi.Z)) {
1316 m_next_intersection_multi.Y += m_intersection_multi_inc.Y;
1317 m_current_node_pos.Y += m_step_directions.Y;
1319 m_next_intersection_multi.Z += m_intersection_multi_inc.Z;
1320 m_current_node_pos.Z += m_step_directions.Z;
1324 s16 VoxelLineIterator::getIndex(v3s16 voxel){
1326 abs(voxel.X - m_start_node_pos.X) +
1327 abs(voxel.Y - m_start_node_pos.Y) +
1328 abs(voxel.Z - m_start_node_pos.Z);
1331 } // namespace voxalgo