Traverse all chunk blocks in a unified (and cache-friendly) way

4 files changed, 76 insertions, 57 deletions

diff --git a/src/World/Chunk.cpp b/src/World/Chunk.cpp
index b4a9ece..eeaefa0 100644
--- a/src/World/Chunk.cpp
+++ b/src/World/Chunk.cpp
@@ -39,10 +39,18 @@ Bool Chunk::is_valid_position(Position::BlockLocal pos) {
     return pos.x() < Width && pos.y() < Height && pos.z() < Width;
 }
 
-U64 Chunk::pos(U32 x, U32 y, U32 z) {
+U64 Chunk::pos(U32 const x, U32 const y, U32 const z) {
     return x + Width * y + Width * Height * z;
 }
 
+Position::BlockLocal Chunk::pos(U64 const i) {
+    return {
+        i % Width,
+        i / Width % Height,
+        i / (Width * Height)
+    };
+}
+
 AABB Chunk::block_bounds(Position::BlockLocal pos) {
     return {
         {pos.x(), pos.y(), pos.z()},
diff --git a/src/World/Chunk.hpp b/src/World/Chunk.hpp
index bab20f2..e958b9a 100644
--- a/src/World/Chunk.hpp
+++ b/src/World/Chunk.hpp
@@ -7,6 +7,7 @@
 #include "BlockType.hpp"
 #include "ChunkIndex.hpp"
 #include "Position.hpp"
+#include "../Common/Iteration.hpp"
 #include "../GFX/Mesh.hpp"
 
 namespace MC::World {
@@ -16,6 +17,8 @@ public:
     static constexpr U32 Width = ChunkDimensions::Width;
     static constexpr U32 Height = ChunkDimensions::Height;
 
+    static constexpr U32 BlockCount = Width * Height * Width;
+
     Chunk(I64 x, I64 y)
         : m_blocks{Width * Height * Width, {BlockType::Air}},
         m_index(x, y),
@@ -48,16 +51,32 @@ public:
     void set_details(const Details& details) { m_details = details; }
     Details& details(){ return m_details; }
 
+    // Cache-friendly iteration through all blocks in the chunk.
     template <typename F>
     void for_each(F f) {
+        for (U32 i = 0; i < BlockCount; ++i) {
+            Iteration control = f(pos(i), m_blocks[i]);
+            if (control == Iteration::Break) break;
+        }
+    }
+
+    // Iteration through all blocks in the chunk by column.
+    // Starts from the top of the chunk and goes down.
+    enum class ColumnIteration { Continue, Break, SkipColumn };
+    template <typename F>
+    void for_each_by_column(F f) {
+        // TODO: Maybe add a way to lookup the highest block in a column
+        // to skip all the air?
         for (U32 x = 0; x < Width; ++x) {
-            for (U32 y = 0; y < Height; ++y) {
-                for (U32 z = 0; z < Width; ++z) {
-                    Position::BlockLocal pos{x, y, z};
-                    f(pos, at(x, y, z));
+            for (U32 z = 0; z < Width; ++z) {
+                for (UInt y = Height - 1; y != 0; y--) {
+                    ColumnIteration control = f({x, y, z}, m_blocks.at(pos(x, y, z)));
+                    if (control == ColumnIteration::Break) goto end;
+                    if (control == ColumnIteration::SkipColumn) break;
                 }
             }
         }
+        end: return;
     }
 
     ChunkIndex index() const;
@@ -70,7 +89,10 @@ public:
     static AABB block_bounds(Position::BlockLocal pos);
     static AABB block_bounds(Position::BlockWorld pos);
 private:
+    // Convert a local position to a chunk block index.
     static U64 pos(U32 x, U32 y, U32 z);
+    // Convert a chunk block index to a local position.
+    static Position::BlockLocal pos(U64 i);
 
     ChunkIndex m_index;
     Vector<3> m_position;
diff --git a/src/World/Generation/ChunkMeshing.hpp b/src/World/Generation/ChunkMeshing.hpp
index c745a3b..16ba701 100644
--- a/src/World/Generation/ChunkMeshing.hpp
+++ b/src/World/Generation/ChunkMeshing.hpp
@@ -47,29 +47,26 @@ template <typename Decisions>
 GFX::Mesh create_mesh(Chunk& chunk, const SurroundingContext& context) {
     GFX::Util::MeshBuilder<Normal, TexCoord, Light, AO> builder;
 
-    for (Int x = 0; x < Chunk::Width; x++) {
-        for (Int y = 0; y < Chunk::Height; y++) {
-            for (Int z = 0; z < Chunk::Width; z++) {
-                auto block = chunk.at(x, y, z);
-                if (Decisions::should_ignore_block(block))
-                    continue;
+    chunk.for_each([&](Position::BlockLocal pos, Chunk::BlockData block) {
+        auto [x, y, z] = pos.values();
+        if (Decisions::should_ignore_block(block)) return Iteration::Continue;
 
-                for (auto side: BlockSide::all()) {
-                    if (!Decisions::is_face_visible(chunk, context, x, y, z, side))
-                        continue;
+        for (auto side: BlockSide::all()) {
+            if (!Decisions::is_face_visible(chunk, context, x, y, z, side))
+                continue;
 
-                    U32 s = builder.vertex_count();
+            builder.positions(Decisions::face_positions(side, x, y, z));
+            builder.attributes<0>(Decisions::face_normals(side));
+            builder.attributes<1>(Decisions::face_tex_coords(block.type, side));
+            builder.attributes<2>(Decisions::face_light(chunk, context, x, y, z, side));
+            builder.attributes<3>(Decisions::face_ao_values(chunk, context, x, y, z, side));
 
-                    builder.positions(Decisions::face_positions(side, x, y, z));
-                    builder.attributes<0>(Decisions::face_normals(side));
-                    builder.attributes<1>(Decisions::face_tex_coords(block.type, side));
-                    builder.attributes<2>(Decisions::face_light(chunk, context, x, y, z, side));
-                    builder.attributes<3>(Decisions::face_ao_values(chunk, context, x, y, z, side));
-                    builder.indices(std::array{ s + 0, s + 1, s + 2, s + 2, s + 3, s + 0 });
-                }
-            }
+            U32 s = builder.vertex_count();
+            builder.indices(std::array{ s + 0, s + 1, s + 2, s + 2, s + 3, s + 0 });
         }
-    }
+
+        return Iteration::Continue;
+    });
 
     return builder.mesh();
 }
diff --git a/src/World/Generation/Decoration.cpp b/src/World/Generation/Decoration.cpp
index 0623c05..ecfa49b 100644
--- a/src/World/Generation/Decoration.cpp
+++ b/src/World/Generation/Decoration.cpp
@@ -43,35 +43,31 @@ void Decorator::draw_circle(Chunk& chunk, Pos pos, Vector<3> axis, Real radius,
 
 void TreeDecorator::decorate_chunk(Chunk& chunk) {
     Pos last_tree = Pos::max();
-    for (UInt x = 0; x < Chunk::Width; x++) {
-        for (UInt z = 0; z < Chunk::Width; z++) {
-            for (UInt y = Chunk::Height - 1; y != 0; y--) {
-                Pos pos{x, y, z};
-                if (!is_valid_position(pos))
-                    continue;
+    chunk.for_each_by_column([&](Pos pos, Chunk::BlockData& block) {
+        auto pos_above = pos + Pos::up();
+        if (!is_valid_position(pos_above))
+            return Chunk::ColumnIteration::Continue;
 
-                auto& block_below = chunk.at(x, y-1, z);
-                if (block_below.empty())
-                    continue;
+        if (block.empty())
+            return Chunk::ColumnIteration::Continue;
 
-                auto type = block_below.type;
-                if (type != BlockType::Snow && type != BlockType::Grass && type != BlockType::Dirt)
-                    break;
+        auto type = block.type;
+        if (type != BlockType::Snow && type != BlockType::Grass && type != BlockType::Dirt)
+            return Chunk::ColumnIteration::SkipColumn;
 
-                auto noise = m_tree_noise.at({(Real)x, (Real)z});
-                if (noise < 0.8f)
-                    continue;
+        auto noise = m_tree_noise.at({TO(Real, pos.x()), TO(Real, pos.z())});
+        if (noise < 0.8f)
+            return Chunk::ColumnIteration::Continue;
 
-                if (last_tree.distance(pos) < s_tree_radius * 3)
-                    continue;
+        if (last_tree.distance(pos_above) < s_tree_radius * 3)
+            return Chunk::ColumnIteration::Continue;
 
-                draw_tree(chunk, pos);
-                block_below = {BlockType::Dirt};
-                last_tree = pos;
-                break;
-            }
-        }
-    }
+        draw_tree(chunk, pos_above);
+        block = {BlockType::Dirt};
+        last_tree = pos_above;
+
+        return Chunk::ColumnIteration::SkipColumn;
+    });
 }
 
 void TreeDecorator::draw_tree(Chunk& chunk, Pos pos) const {
@@ -97,15 +93,11 @@ Bool TreeDecorator::is_valid_position(Pos pos) {
 }
 
 void DefaultLightDecorator::decorate_chunk(Chunk& chunk) {
-    for (UInt x = 0; x < Chunk::Width; x++) {
-        for (UInt z = 0; z < Chunk::Width; z++) {
-            for (UInt y = Chunk::Height - 1; y != 0; y--) {
-                auto& block = chunk.at(x, y, z);
-                if (!block.type.is_translucent()) break;
-                chunk.at(x, y, z).light = 200;
-            }
-        }
-    }
+    chunk.for_each_by_column([&](Pos pos, Chunk::BlockData& block) {
+        if (!block.type.is_translucent()) return Chunk::ColumnIteration::Break;
+        block.light = 200;
+        return Chunk::ColumnIteration::Continue;
+    });
 }
 
 }