// ============================================================================
// LEAF COUNT vs OCTREE DEPTH — does view distance cost chunks, and how many?
//
// THE QUESTION. Extending view distance means raising octree_depth: the world a
// clipmap covers is base_voxel_size * voxels_per_cell * 2^(depth-1), so depth is
// the only knob that moves it. Everything else in the range discussion — the GPU
// stage costs, dispatch batching, MAX_GPU_EDITS — is downstream of how many
// chunks that actually produces.
//
// The claim being tested is one I have been ASSERTING and never measured: that a
// clipmap adds a SHELL of cells per level, so leaf count grows roughly LINEARLY
// with depth rather than exponentially. If that holds, range is cheap and the
// blockers are elsewhere (MAX_LOD_MATERIALS, the coarse-LOD edit cap, the fbm
// octave renormalisation). If leaf count is super-linear in THIS traversal, the
// priority order inverts and meshing throughput becomes the ceiling after all.
//
// A clipmap is not obliged to be linear. _traverse_node's split rule, the
// hysteresis band, the frustum-aware term and the per-frame split budget are all
// real code that can produce a different curve than the textbook picture. That is
// exactly why this is measured rather than reasoned about.
//
// IT DRIVES THE SHIPPING CLASS. OctreeClipmap comes from src/dc_octree_clipmap.h
// — the same header dc_terrain.cpp instantiates — with the configuration
// dc_terrain.cpp:280-300 actually applies. No reimplementation of the traversal,
// because a reimplementation would only prove itself.
//
// CONFIG FIDELITY MATTERS AND ONE VALUE IS A TRAP. dc_terrain.cpp:281 sets
// voxels_per_cell = 28 // nominal = 32 - 2*overlap(2)
// NOT 32. Using 32 overstates the world extent by 14% at every depth. And
// lod_factor is assigned twice — :282 from lod_factor_ (3.0), then :296
// overwrites it with (seamless_lod_ ? 1000.0f : 2.0f), so the shipping value is
// 2.0 and lod_factor_ is dead unless seamless_lod_ is on. Both taken from source
// rather than from the defaults in the header, which differ.
//
// Build (no engine, no godot, no scons):
// g++ -O2 -std=c++17 -I src -I libdc/include \
// -o /tmp/leafcount tests/test_leaf_count_vs_depth.cpp src/dc_octree_clipmap.cpp
//
// Run: /tmp/leafcount
// ============================================================================
#include "dc_octree_clipmap.h"
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <cstdlib>
// Shipping configuration, from dc_terrain.cpp:280-300 and hyper-tps'
// dc_world_setup.gd / map_dc_world.tscn.
// NOT const: overridable, because the two maps that matter disagree.
// dc_world_setup.gd:19 uses 0.224 m; map_dc_erosion.tscn uses 1.0 m, and extent
// scales with it, so a run that reports one map's extents says nothing about the
// other's. --voxel picks which world you are asking about.
static float VOXEL_SIZE = 0.224f; // dc_world_setup.gd:19
static const int VOXELS_PER_CELL = 28; // dc_terrain.cpp:281 — NOT 32
// Overridable too. lod_factor is the knob that decides how fast voxels coarsen
// with distance, which is what actually limits how far a MOUNTAIN stays visible
// -- extent only decides how far the world goes. Unlike depth it is NOT free.
static float LOD_FACTOR = 2.0f; // dc_terrain.cpp:296, seamless off
static const float HYSTERESIS = 1.3f; // dc_terrain.h:430
static const int MAX_SPLITS_PER_FRAME= 16; // dc_terrain.cpp:297
static const int MAX_MERGES_PER_FRAME= 8; // dc_terrain.cpp:298
struct Result {
int depth = 0;
double extent_m = 0.0;
int leaves = 0;
int frames = 0;
bool settled = false;
std::map<int,int> per_lod;
};
// Run one clipmap to convergence and report what it settled on.
//
// SETTLING IS THE WHOLE MEASUREMENT. traverse() splits at most
// max_splits_per_frame per call, so an unsettled tree reports whatever partial
// refinement the frame budget reached — which is a measure of the budget, not of
// the depth. The loop runs until stats.settled, and reports `frames` so a run
// that hit the cap is visible rather than silently reported as a leaf count.
static Result run_depth(int depth, const float cam[3], int max_frames) {
Result r;
r.depth = depth;
r.extent_m = double(VOXEL_SIZE) * double(VOXELS_PER_CELL) * std::pow(2.0, depth - 1);
OctreeClipmap cm;
cm.base_voxel_size = VOXEL_SIZE;
cm.voxels_per_cell = VOXELS_PER_CELL;
cm.lod_factor = LOD_FACTOR;
cm.hysteresis = HYSTERESIS;
cm.max_lod_levels = depth;
cm.max_splits_per_frame = MAX_SPLITS_PER_FRAME;
cm.max_merges_per_frame = MAX_MERGES_PER_FRAME;
cm.content_aware_lod = false;
cm.lod_mode = LOD_BLOCKING_SWAP;
cm.initialize();
for (int f = 0; f < max_frames; f++) {
cm.traverse(cam, (uint32_t)f);
// DRIVING BLOCKING_SWAP CORRECTLY IS THE WHOLE TRICK, AND I GOT IT WRONG
// FIRST. drain_pending() + mark_ready() + mark_active() moves NODE state,
// and that is not what gates a split. _traverse_node:394-404 additionally
// requires all eight CHILDREN to hold a pre-mesh cache entry in
// MESH_UP_TO_DATE — the entry the engine writes when a chunk's mesh
// actually completes. Without it the root never splits, every depth
// reports exactly 1 leaf, and the run looks like a clipmap that ignores
// its own configuration. (test/test_octree_clipmap.cpp drives it the same
// wrong way and core-dumps, so it was no help as a reference.)
//
// Marking every requested entry UP_TO_DATE is the instant-mesh
// idealisation: it answers "how many leaves does this traversal converge
// on", which is the question, and deliberately not "how fast does it get
// there", which would need real mesh latency.
auto pending = cm.drain_pending();
for (auto* n : pending) { cm.mark_ready(n); cm.mark_active(n); }
for (auto& kv : cm.pre_mesh_cache_ref())
kv.second.state = OctreeClipmapNode::MESH_UP_TO_DATE;
r.frames = f + 1;
if (cm.get_stats().settled && pending.empty()) { r.settled = true; break; }
}
auto leaves = cm.get_leaves();
r.leaves = (int)leaves.size();
for (auto* n : leaves) r.per_lod[n->lod_level]++;
return r;
}
int main(int argc, char** argv) {
int max_frames = 20000;
for (int i = 1; i < argc; i++)
if (std::string(argv[i]) == "--frames" && i + 1 < argc) max_frames = atoi(argv[++i]);
// Camera at the origin — the root centre, so refinement is symmetric and the
// count is not a function of where the camera happens to sit in a cell.
float cam[3] = {0.0f, 0.0f, 0.0f};
int max_depth = 14;
for (int i = 1; i < argc; i++) {
if (!strcmp(argv[i], "--voxel") && i + 1 < argc) VOXEL_SIZE = (float)atof(argv[++i]);
else if (!strcmp(argv[i], "--lod-factor") && i + 1 < argc) LOD_FACTOR = (float)atof(argv[++i]);
else if (!strcmp(argv[i], "--max-depth") && i + 1 < argc) max_depth = atoi(argv[++i]);
}
printf("Leaf count vs octree depth\n");
printf(" voxel %.3f m, voxels_per_cell %d, lod_factor %.1f, hysteresis %.1f\n",
VOXEL_SIZE, VOXELS_PER_CELL, LOD_FACTOR, HYSTERESIS);
printf(" splits/frame %d, merges/frame %d, camera at origin\n\n",
MAX_SPLITS_PER_FRAME, MAX_MERGES_PER_FRAME);
printf("%-6s %12s %10s %10s %9s %10s\n",
"depth", "extent(m)", "leaves", "d(leaves)", "frames", "settled");
std::vector<Result> all;
int prev = 0;
for (int d = 2; d <= max_depth; d++) {
Result r = run_depth(d, cam, max_frames);
printf("%-6d %12.1f %10d %10d %9d %10s\n",
r.depth, r.extent_m, r.leaves, r.leaves - prev, r.frames,
r.settled ? "yes" : "NO (capped)");
prev = r.leaves;
all.push_back(r);
}
// THE VERDICT, stated as a ratio rather than an adjective. A shell-per-level
// structure adds a roughly CONSTANT number of leaves per depth, so d(leaves)
// flattens and leaves/depth tends to a constant. Doubling per level instead
// would show d(leaves) doubling, and that would make view distance a
// meshing-throughput problem after all.
printf("\nGrowth check (a shell-per-level clipmap adds ~constant leaves/level):\n");
printf("%-6s %14s %14s\n", "depth", "leaves/depth", "leaves/2^depth");
for (auto& r : all)
printf("%-6d %14.1f %14.4f\n", r.depth,
double(r.leaves) / double(r.depth),
double(r.leaves) / std::pow(2.0, r.depth));
// Per-LOD distribution at the deepest settled depth: which levels hold the
// chunks decides where the coarse-LOD edit cap (hyper-games #43 P3) bites.
for (auto it = all.rbegin(); it != all.rend(); ++it) {
if (!it->settled) continue;
printf("\nLeaves per LOD at depth %d (extent %.0f m):\n", it->depth, it->extent_m);
for (auto& kv : it->per_lod) {
double cell = double(VOXEL_SIZE) * double(VOXELS_PER_CELL) * std::pow(2.0, kv.first);
printf(" LOD %-3d %8d leaves cell %10.1f m\n", kv.first, kv.second, cell);
}
break;
}
return 0;
}