// ============================================================================
// INTERIOR DECOMPOSITION ORACLE — level-mesh-implementation.md §5a.2, hyper-games #25 §2.
//
// THE QUESTION THIS EXISTS TO ANSWER, before a line of engine code is written:
// how many convex volumes does START.MAP's interior decompose into, and does that
// fit under the cap?
//
// dc_compute.cpp:22 static constexpr int MAX_GPU_EDITS = 1536; // PER CHUNK
// dc_compute.cpp:1418 if (gpu_edits.size() >= MAX_GPU_EDITS) break;
//
// The excess is DROPPED, silently. A decomposition that overruns that does not
// error — terrain leaks back into the rooms, by an amount that varies with LOD
// and camera position, because the cap is applied per chunk AFTER culling. That
// is the worst failure mode on offer, so the count is the design constraint and
// not a detail to discover afterwards.
//
// WHAT IS BEING REPLACED. Today the whole level's inflated AABB is subtracted
// from the terrain field in ONE edit (quake_map_importer.gd:295-297): correct,
// crude, and shaped like a box rather than like the level, which is what "it
// still just cuts out a large aabb around the map" looks like from inside.
//
// THE APPROACH, and why it is boxes rather than exact portalization:
//
// 1. rasterize every brush into a grid (each brush only over its own AABB, so
// the cost is sum-of-brush-volumes, not cells x brushes)
// 2. flood fill from the grid border through non-solid cells -> EXTERIOR
// 3. INTERIOR = neither solid nor reachable from outside. This is qbsp's own
// inside/outside test — the flood fill it uses to detect leaks.
// 4. greedy-merge interior cells into axis-aligned boxes
//
// Exact portalization (BSP empty leaves) gives the true convex decomposition and
// is the eventual answer; this measures whether the cheap version is good enough
// to ship first, which is a question only a number can settle.
//
// SKY BRUSHES ARE REQUIRED. A Quake sky brush is SOLID — it blocks the player,
// only its rendering is special. Drop them and the map has 19 holes, the flood
// fill pours through, every room is marked exterior, and the interior comes back
// EMPTY without erroring. Hence the sky-inclusive dump.
//
// Input: /tmp/startmap_brushes_sky.bin
// (godot4 --headless --script res://scenes/test/oracle_dump.gd -- --sky)
// Build: g++ -O2 -std=c++17 -o /tmp/interior_decomp tests/test_interior_decomp.cpp
// ============================================================================
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
struct Plane { float nx, ny, nz, d; };
struct Brush {
float cx, cy, cz, radius, strength;
uint32_t material;
std::vector<Plane> planes;
};
// ---------------------------------------------------------------- dump reader
static bool read_dump(const char* path, std::vector<Brush>& out,
float& world_scale, float carve_half[3], float carve_center[3]) {
FILE* f = fopen(path, "rb");
if (!f) { fprintf(stderr, "cannot open %s\n", path); return false; }
char magic[4];
if (fread(magic, 1, 4, f) != 4 || memcmp(magic, "DCOR", 4) != 0) {
fprintf(stderr, "bad magic in %s\n", path); fclose(f); return false;
}
uint32_t version = 0;
fread(&version, 4, 1, f);
fread(&world_scale, 4, 1, f);
fread(carve_half, 4, 3, f);
fread(carve_center, 4, 3, f);
uint32_t n = 0;
fread(&n, 4, 1, f);
out.resize(n);
for (uint32_t i = 0; i < n; i++) {
Brush& b = out[i];
fread(&b.cx, 4, 1, f); fread(&b.cy, 4, 1, f); fread(&b.cz, 4, 1, f);
fread(&b.radius, 4, 1, f);
fread(&b.strength, 4, 1, f);
fread(&b.material, 4, 1, f);
uint32_t pc = 0;
fread(&pc, 4, 1, f);
b.planes.resize(pc);
for (uint32_t p = 0; p < pc; p++) {
fread(&b.planes[p].nx, 4, 1, f);
fread(&b.planes[p].ny, 4, 1, f);
fread(&b.planes[p].nz, 4, 1, f);
fread(&b.planes[p].d, 4, 1, f);
uint32_t proj; fread(&proj, 4, 1, f);
}
}
fclose(f);
return true;
}
// ------------------------------------------------------------------- geometry
// Brush AABB from its half-space set, by clipping a generous box against each
// plane along the axes. The dump carries a bounding SPHERE (centre+radius) which
// is enough and much simpler — use it, then tighten per-axis with the planes
// that happen to be axis-aligned (91.7% of START sits on the 8-unit grid).
static void brush_aabb(const Brush& b, float lo[3], float hi[3]) {
lo[0] = b.cx - b.radius; hi[0] = b.cx + b.radius;
lo[1] = b.cy - b.radius; hi[1] = b.cy + b.radius;
lo[2] = b.cz - b.radius; hi[2] = b.cz + b.radius;
for (const Plane& p : b.planes) {
// An axis-aligned plane bounds exactly one side of one axis.
if (p.ny == 0 && p.nz == 0 && p.nx != 0) {
float v = p.d / p.nx;
if (p.nx > 0) hi[0] = std::min(hi[0], v); else lo[0] = std::max(lo[0], v);
} else if (p.nx == 0 && p.nz == 0 && p.ny != 0) {
float v = p.d / p.ny;
if (p.ny > 0) hi[1] = std::min(hi[1], v); else lo[1] = std::max(lo[1], v);
} else if (p.nx == 0 && p.ny == 0 && p.nz != 0) {
float v = p.d / p.nz;
if (p.nz > 0) hi[2] = std::min(hi[2], v); else lo[2] = std::max(lo[2], v);
}
}
}
static inline bool inside_brush(const Brush& b, float x, float y, float z) {
for (const Plane& p : b.planes)
if (p.nx * x + p.ny * y + p.nz * z - p.d > 0.0f) return false;
return true;
}
// CONSERVATIVE: does the brush overlap the CELL AT ALL, rather than contain its
// centre? This is not a refinement, it is a correctness fix, and the first cut of
// this oracle got it wrong in a way that looked like a finding.
//
// Quake walls are commonly 16 units = 0.448 m at world_scale 0.028. Sampling cell
// CENTRES at 1 m therefore misses most walls entirely, the exterior flood pours
// straight through them, and every room is marked exterior — reported as
// "interior 0" at 1 m and 2 m, which reads exactly like "this level has no
// interior" rather than "this test cannot see walls".
//
// A convex brush overlaps a box unless the box lies entirely outside one of its
// planes. Test the box corner FURTHEST along -n (the support point): if even that
// corner is outside, no part of the box is inside.
static inline bool overlaps_cell(const Brush& b, float x0, float y0, float z0, float cell) {
const float x1 = x0 + cell, y1 = y0 + cell, z1 = z0 + cell;
for (const Plane& p : b.planes) {
const float sx = (p.nx > 0.0f) ? x0 : x1;
const float sy = (p.ny > 0.0f) ? y0 : y1;
const float sz = (p.nz > 0.0f) ? z0 : z1;
if (p.nx * sx + p.ny * sy + p.nz * sz - p.d > 0.0f) return false;
}
return true;
}
// ------------------------------------------------------------------- windings
//
// brush.c CreateBrushFaces: a face is its plane's polygon clipped by every OTHER
// plane of the same brush. Raw per-brush windings, NOT the csg4 neighbour clip —
// and that is sufficient here, because a face buried inside an abutting brush has
// SOLID on its outward side and the grid test below rejects it for that reason
// rather than needing the skin computed first.
struct Vec3 { double x, y, z; };
typedef std::vector<Vec3> Winding;
static Winding base_winding(const Plane& p) {
// Largest axis of the normal decides the up vector, so the basis never
// degenerates on an axis-aligned plane (which most of START's are).
double ax = std::fabs(p.nx), ay = std::fabs(p.ny), az = std::fabs(p.nz);
Vec3 up{0,0,0};
if (ax >= ay && ax >= az) up = {0,0,1};
else if (ay >= az) up = {0,0,1};
else up = {0,1,0};
Vec3 n{p.nx, p.ny, p.nz};
double d = up.x*n.x + up.y*n.y + up.z*n.z;
up.x -= n.x*d; up.y -= n.y*d; up.z -= n.z*d;
double l = std::sqrt(up.x*up.x + up.y*up.y + up.z*up.z);
if (l < 1e-12) return {};
up.x/=l; up.y/=l; up.z/=l;
Vec3 rt{ up.y*n.z - up.z*n.y, up.z*n.x - up.x*n.z, up.x*n.y - up.y*n.x };
Vec3 org{ n.x*p.d, n.y*p.d, n.z*p.d };
const double B = 1.0e4;
Winding w(4);
for (int i = 0; i < 4; i++) {
double su = (i == 0 || i == 3) ? -B : B;
double sv = (i < 2) ? B : -B;
w[i] = { org.x + up.x*su + rt.x*sv,
org.y + up.y*su + rt.y*sv,
org.z + up.z*su + rt.z*sv };
}
return w;
}
// Keep the side with n.p <= d.
static Winding clip_winding(const Winding& w, const Plane& p) {
if (w.empty()) return w;
const double EPS = 1e-6;
Winding out;
const size_t n = w.size();
for (size_t i = 0; i < n; i++) {
const Vec3& a = w[i];
const Vec3& b = w[(i + 1) % n];
double da = p.nx*a.x + p.ny*a.y + p.nz*a.z - p.d;
double db = p.nx*b.x + p.ny*b.y + p.nz*b.z - p.d;
if (da <= EPS) out.push_back(a);
if ((da > EPS && db < -EPS) || (da < -EPS && db > EPS)) {
double t = da / (da - db);
out.push_back({ a.x + (b.x-a.x)*t, a.y + (b.y-a.y)*t, a.z + (b.z-a.z)*t });
}
}
return out;
}
static void winding_stats(const Winding& w, Vec3& centroid, double& area, const Plane& p) {
centroid = {0,0,0}; area = 0.0;
if (w.size() < 3) return;
for (const Vec3& v : w) { centroid.x += v.x; centroid.y += v.y; centroid.z += v.z; }
centroid.x /= w.size(); centroid.y /= w.size(); centroid.z /= w.size();
// Fan from vertex 0; magnitude of the cross product, halved, per triangle.
for (size_t i = 1; i + 1 < w.size(); i++) {
Vec3 u{ w[i].x - w[0].x, w[i].y - w[0].y, w[i].z - w[0].z };
Vec3 v{ w[i+1].x - w[0].x, w[i+1].y - w[0].y, w[i+1].z - w[0].z };
Vec3 c{ u.y*v.z - u.z*v.y, u.z*v.x - u.x*v.z, u.x*v.y - u.y*v.x };
area += 0.5 * std::sqrt(c.x*c.x + c.y*c.y + c.z*c.z);
}
(void)p;
}
// ------------------------------------------------------------------ the oracle
enum : uint8_t { AIR = 0, SOLID = 1, EXTERIOR = 2 };
struct Box { int x0, y0, z0, x1, y1, z1; }; // inclusive cell range
struct Result {
int nx, ny, nz;
long long solid, exterior, interior;
std::vector<Box> boxes;
double interior_m3;
// Kept so the shell pass can ask "what is just outside this face?" without
// recomputing the fill — the classification IS the flood fill's by-product.
std::vector<uint8_t> grid;
float lo[3];
float cell;
};
static Result run(const std::vector<Brush>& brushes, float cell, bool conservative) {
Result r{};
// World AABB over all brushes, padded by two cells so the flood fill always
// has an outside to start from even if a brush touches the boundary.
float lo[3] = { 1e30f, 1e30f, 1e30f }, hi[3] = { -1e30f, -1e30f, -1e30f };
for (const Brush& b : brushes) {
float bl[3], bh[3];
brush_aabb(b, bl, bh);
for (int a = 0; a < 3; a++) { lo[a] = std::min(lo[a], bl[a]); hi[a] = std::max(hi[a], bh[a]); }
}
for (int a = 0; a < 3; a++) { lo[a] -= cell * 2.0f; hi[a] += cell * 2.0f; }
r.nx = (int)std::ceil((hi[0] - lo[0]) / cell);
r.ny = (int)std::ceil((hi[1] - lo[1]) / cell);
r.nz = (int)std::ceil((hi[2] - lo[2]) / cell);
const long long N = (long long)r.nx * r.ny * r.nz;
std::vector<uint8_t> g((size_t)N, AIR);
auto idx = [&](int x, int y, int z) -> size_t {
return ((size_t)z * r.ny + y) * r.nx + x;
};
// 1. Rasterize each brush over ITS OWN AABB only.
for (const Brush& b : brushes) {
float bl[3], bh[3];
brush_aabb(b, bl, bh);
int x0 = std::max(0, (int)std::floor((bl[0] - lo[0]) / cell));
int y0 = std::max(0, (int)std::floor((bl[1] - lo[1]) / cell));
int z0 = std::max(0, (int)std::floor((bl[2] - lo[2]) / cell));
int x1 = std::min(r.nx - 1, (int)std::ceil((bh[0] - lo[0]) / cell));
int y1 = std::min(r.ny - 1, (int)std::ceil((bh[1] - lo[1]) / cell));
int z1 = std::min(r.nz - 1, (int)std::ceil((bh[2] - lo[2]) / cell));
for (int z = z0; z <= z1; z++)
for (int y = y0; y <= y1; y++)
for (int x = x0; x <= x1; x++) {
size_t i = idx(x, y, z);
if (g[i] == SOLID) continue;
float cx0 = lo[0] + x * cell;
float cy0 = lo[1] + y * cell;
float cz0 = lo[2] + z * cell;
bool solid = conservative
? overlaps_cell(b, cx0, cy0, cz0, cell)
: inside_brush(b, cx0 + cell * 0.5f, cy0 + cell * 0.5f, cz0 + cell * 0.5f);
if (solid) g[i] = SOLID;
}
}
// 2. Flood fill EXTERIOR from the border. Iterative — the recursion depth on
// a 15M-cell grid would blow the stack.
std::vector<int> stack;
stack.reserve(1 << 20);
auto push_if_air = [&](int x, int y, int z) {
if (x < 0 || y < 0 || z < 0 || x >= r.nx || y >= r.ny || z >= r.nz) return;
size_t i = idx(x, y, z);
if (g[i] != AIR) return;
g[i] = EXTERIOR;
stack.push_back(x); stack.push_back(y); stack.push_back(z);
};
for (int z = 0; z < r.nz; z++)
for (int y = 0; y < r.ny; y++)
for (int x = 0; x < r.nx; x++)
if (x == 0 || y == 0 || z == 0 || x == r.nx - 1 || y == r.ny - 1 || z == r.nz - 1)
push_if_air(x, y, z);
while (!stack.empty()) {
int z = stack.back(); stack.pop_back();
int y = stack.back(); stack.pop_back();
int x = stack.back(); stack.pop_back();
push_if_air(x + 1, y, z); push_if_air(x - 1, y, z);
push_if_air(x, y + 1, z); push_if_air(x, y - 1, z);
push_if_air(x, y, z + 1); push_if_air(x, y, z - 1);
}
r.cell = cell;
r.lo[0] = lo[0]; r.lo[1] = lo[1]; r.lo[2] = lo[2];
for (long long i = 0; i < N; i++) {
if (g[i] == SOLID) r.solid++;
else if (g[i] == EXTERIOR) r.exterior++;
else r.interior++;
}
r.interior_m3 = (double)r.interior * cell * cell * cell;
// 3. Greedy box merge over the remaining AIR (= interior) cells.
std::vector<uint8_t> used((size_t)N, 0);
for (int z = 0; z < r.nz; z++)
for (int y = 0; y < r.ny; y++)
for (int x = 0; x < r.nx; x++) {
size_t i = idx(x, y, z);
if (g[i] != AIR || used[i]) continue;
int x1 = x;
while (x1 + 1 < r.nx && g[idx(x1 + 1, y, z)] == AIR && !used[idx(x1 + 1, y, z)]) x1++;
int y1 = y;
bool ok = true;
while (ok && y1 + 1 < r.ny) {
for (int xx = x; xx <= x1; xx++) {
size_t j = idx(xx, y1 + 1, z);
if (g[j] != AIR || used[j]) { ok = false; break; }
}
if (ok) y1++;
}
int z1 = z;
ok = true;
while (ok && z1 + 1 < r.nz) {
for (int yy = y; yy <= y1 && ok; yy++)
for (int xx = x; xx <= x1; xx++) {
size_t j = idx(xx, yy, z1 + 1);
if (g[j] != AIR || used[j]) { ok = false; break; }
}
if (ok) z1++;
}
for (int zz = z; zz <= z1; zz++)
for (int yy = y; yy <= y1; yy++)
for (int xx = x; xx <= x1; xx++) used[idx(xx, yy, zz)] = 1;
r.boxes.push_back({x, y, z, x1, y1, z1});
}
r.grid = std::move(g);
return r;
}
// ------------------------------------------------------------------- the shell
//
// WHICH BRUSHES FORM THE OUTER BOUNDARY? §5a.3 called the definition of "outside
// walls" the crux and offered two candidates — a face whose outward ray escapes
// the AABB, or outer-hull membership. The flood fill answers it more directly and
// with no new machinery: a brush is on the boundary if any cell it occupies is
// adjacent to an EXTERIOR cell. Visible-skin membership is NOT sufficient (an
// interior room face is equally visible) and this test does not confuse the two,
// because an interior face's neighbours are INTERIOR, never EXTERIOR.
//
// The number that matters is how much of the level the shell is. A small subset
// means the shell is cheap to build and cheap to subtract; most of the level
// means this framing is wrong.
struct ShellStats { int boundary_brushes; int interior_brushes; int sky_boundary; int sky_total; };
static ShellStats classify_brushes(const std::vector<Brush>& brushes, const Result& r,
const std::vector<uint8_t>& is_sky) {
ShellStats s{};
const int nx = r.nx, ny = r.ny, nz = r.nz;
auto at = [&](int x, int y, int z) -> uint8_t {
if (x < 0 || y < 0 || z < 0 || x >= nx || y >= ny || z >= nz) return EXTERIOR;
return r.grid[((size_t)z * ny + y) * nx + x];
};
for (size_t bi = 0; bi < brushes.size(); bi++) {
const Brush& b = brushes[bi];
float bl[3], bh[3];
brush_aabb(b, bl, bh);
int x0 = std::max(0, (int)std::floor((bl[0] - r.lo[0]) / r.cell) - 1);
int y0 = std::max(0, (int)std::floor((bl[1] - r.lo[1]) / r.cell) - 1);
int z0 = std::max(0, (int)std::floor((bl[2] - r.lo[2]) / r.cell) - 1);
int x1 = std::min(nx - 1, (int)std::ceil((bh[0] - r.lo[0]) / r.cell) + 1);
int y1 = std::min(ny - 1, (int)std::ceil((bh[1] - r.lo[1]) / r.cell) + 1);
int z1 = std::min(nz - 1, (int)std::ceil((bh[2] - r.lo[2]) / r.cell) + 1);
bool touches_exterior = false;
for (int z = z0; z <= z1 && !touches_exterior; z++)
for (int y = y0; y <= y1 && !touches_exterior; y++)
for (int x = x0; x <= x1 && !touches_exterior; x++) {
if (at(x, y, z) != SOLID) continue;
float cx0 = r.lo[0] + x * r.cell, cy0 = r.lo[1] + y * r.cell, cz0 = r.lo[2] + z * r.cell;
if (!overlaps_cell(b, cx0, cy0, cz0, r.cell)) continue;
if (at(x+1,y,z) == EXTERIOR || at(x-1,y,z) == EXTERIOR ||
at(x,y+1,z) == EXTERIOR || at(x,y-1,z) == EXTERIOR ||
at(x,y,z+1) == EXTERIOR || at(x,y,z-1) == EXTERIOR) touches_exterior = true;
}
if (is_sky[bi]) s.sky_total++;
if (touches_exterior) { s.boundary_brushes++; if (is_sky[bi]) s.sky_boundary++; }
else s.interior_brushes++;
}
return s;
}
// ------------------------------------------------------- per-chunk histogram
//
// THE NUMBER §7.8 IS BLOCKED ON, and the level-wide table above does not contain
// it. MAX_GPU_EDITS is applied PER CHUNK, AFTER culling (dc_compute.cpp:1448), so
// "1240 boxes vs a cap of 1536" compares a level total against a per-chunk cap and
// is not an answer. What decides the design is what the WORST chunk sees.
//
// Chunk geometry is read out of the engine rather than assumed
// (dc_terrain.cpp:906-926, dc_world_setup.gd:12):
//
// voxel_size 0.224 m at LOD0 (Quake's 8-unit grid x world_scale 0.028)
// lod_voxel = voxel_size << lod
// grid_size = 32, overlap = 2 -> 28 OWNED voxels per chunk
// owned span = 28 * lod_voxel -> the lattice chunk origins sit on
// CULL BOX = [origin - 2*lod_voxel, + 32*lod_voxel]
//
// The cull box INCLUDES the overlap, because that is the AABB
// cull_edits_for_chunk is actually handed (req.cell_origin, not nominal_origin).
//
// SWEEP EVERY LOD, not just LOD0. A coarse chunk covers 2^lod times more world and
// therefore culls to more edits — the worst chunk is a COARSE one. A histogram
// that walked LOD0 alone would report a comfortable maximum and miss the only
// failure mode on offer, which is the silent `break` at the cap.
//
// The overlap test is cull_edits_for_chunk's BOX branch, character for character:
// an interior box is a TerrainEdit::BOX (axis-aligned, six half-extents, NO convex
// planes), so MAX_CONVEX_PLANES does not apply to this decomposition at all.
struct BoxW { double lo[3], hi[3]; };
static std::vector<BoxW> boxes_to_world(const Result& r) {
std::vector<BoxW> out;
out.reserve(r.boxes.size());
for (const Box& b : r.boxes) {
BoxW w;
w.lo[0] = r.lo[0] + (double)b.x0 * r.cell;
w.lo[1] = r.lo[1] + (double)b.y0 * r.cell;
w.lo[2] = r.lo[2] + (double)b.z0 * r.cell;
w.hi[0] = r.lo[0] + (double)(b.x1 + 1) * r.cell;
w.hi[1] = r.lo[1] + (double)(b.y1 + 1) * r.cell;
w.hi[2] = r.lo[2] + (double)(b.z1 + 1) * r.cell;
out.push_back(w);
}
return out;
}
struct ChunkHisto {
long long chunks_touched;
int max_edits, p50, p95, p99;
long long over_cap;
double mean;
double chunk_span;
};
static ChunkHisto per_chunk_histogram(const std::vector<BoxW>& boxes,
double voxel_size, int lod, int cap) {
ChunkHisto h{};
const double lod_voxel = voxel_size * (double)(1 << lod);
const double owned = 28.0 * lod_voxel; // lattice spacing
const double cull_span = 32.0 * lod_voxel; // what the culler is handed
const double back = 2.0 * lod_voxel; // overlap shift
h.chunk_span = owned;
if (boxes.empty()) return h;
double lo[3] = { 1e30, 1e30, 1e30 }, hi[3] = { -1e30, -1e30, -1e30 };
for (const BoxW& b : boxes)
for (int a = 0; a < 3; a++) { lo[a] = std::min(lo[a], b.lo[a]); hi[a] = std::max(hi[a], b.hi[a]); }
// Chunk indices on the owned lattice, widened by one so a chunk whose OVERLAP
// reaches the level but whose owned region does not is still counted.
int i0[3], i1[3];
for (int a = 0; a < 3; a++) {
i0[a] = (int)std::floor(lo[a] / owned) - 1;
i1[a] = (int)std::floor(hi[a] / owned) + 1;
}
std::vector<int> counts;
for (int iz = i0[2]; iz <= i1[2]; iz++)
for (int iy = i0[1]; iy <= i1[1]; iy++)
for (int ix = i0[0]; ix <= i1[0]; ix++) {
const double cmin[3] = { ix * owned - back, iy * owned - back, iz * owned - back };
const double ccx = cmin[0] + cull_span * 0.5;
const double ccy = cmin[1] + cull_span * 0.5;
const double ccz = cmin[2] + cull_span * 0.5;
const double ch = cull_span * 0.5;
int n = 0;
for (const BoxW& b : boxes) {
// cull_edits_for_chunk, BOX branch: |e.centre - chunk centre| <= sum of halves.
const double ex = (b.lo[0] + b.hi[0]) * 0.5, ehx = (b.hi[0] - b.lo[0]) * 0.5;
const double ey = (b.lo[1] + b.hi[1]) * 0.5, ehy = (b.hi[1] - b.lo[1]) * 0.5;
const double ez = (b.lo[2] + b.hi[2]) * 0.5, ehz = (b.hi[2] - b.lo[2]) * 0.5;
if (std::fabs(ex - ccx) <= ehx + ch &&
std::fabs(ey - ccy) <= ehy + ch &&
std::fabs(ez - ccz) <= ehz + ch) n++;
}
if (n > 0) counts.push_back(n);
}
if (counts.empty()) return h;
std::sort(counts.begin(), counts.end());
h.chunks_touched = (long long)counts.size();
h.max_edits = counts.back();
h.p50 = counts[counts.size() * 50 / 100];
h.p95 = counts[std::min(counts.size() - 1, counts.size() * 95 / 100)];
h.p99 = counts[std::min(counts.size() - 1, counts.size() * 99 / 100)];
double sum = 0.0;
for (int c : counts) { sum += c; if (c > cap) h.over_cap++; }
h.mean = sum / (double)counts.size();
return h;
}
// -------------------------------------------------------------- requeue reach
//
// THE OTHER HALF OF THE COMPARISON, and the one a player feels. The cap question
// is "does the subtract survive"; this is "how much has to be re-meshed when one
// brush moves". _requeue_chunks_for_mesh_stamp (dc_terrain.cpp:3134) tests a
// SPHERE about the stamp point against each chunk's own box.
//
// For the level shell that sphere is centred on the mesh centroid with a radius
// reaching its furthest AABB corner (the #41 §3 fix), so it provably contains the
// whole level — every chunk overlapping the level is requeued, on every edit. For
// a box/convex edit the sphere is the edit's own.
static long long requeue_reach(const double centre[3], double radius,
const double level_lo[3], const double level_hi[3],
double voxel_size, int lod) {
const double lod_voxel = voxel_size * (double)(1 << lod);
const double owned = 28.0 * lod_voxel;
const double span = 28.0 * lod_voxel; // the requeue test uses the OWNED box
int i0[3], i1[3];
for (int a = 0; a < 3; a++) {
i0[a] = (int)std::floor(level_lo[a] / owned) - 1;
i1[a] = (int)std::floor(level_hi[a] / owned) + 1;
}
long long n = 0;
for (int iz = i0[2]; iz <= i1[2]; iz++)
for (int iy = i0[1]; iy <= i1[1]; iy++)
for (int ix = i0[0]; ix <= i1[0]; ix++) {
const double c[3] = { ix * owned + span * 0.5,
iy * owned + span * 0.5,
iz * owned + span * 0.5 };
const double h = span * 0.5;
double d2 = 0.0;
for (int a = 0; a < 3; a++) {
double d = std::max(0.0, std::fabs(centre[a] - c[a]) - h);
d2 += d * d;
}
if (d2 <= radius * radius) n++;
}
return n;
}
int main(int argc, char** argv) {
const char* path = (argc > 1) ? argv[1] : "/tmp/startmap_brushes_sky.bin";
std::vector<Brush> brushes;
float ws = 0; float ch[3] = {0,0,0}, cc[3] = {0,0,0};
if (!read_dump(path, brushes, ws, ch, cc)) return 1;
long long planes = 0;
for (const Brush& b : brushes) planes += (long long)b.planes.size();
printf("dump: %s\n", path);
printf(" brushes %zu planes %lld world_scale %.4f\n", brushes.size(), planes, ws);
printf(" moat (what we are replacing): centre (%.2f %.2f %.2f) half (%.2f %.2f %.2f)\n",
cc[0], cc[1], cc[2], ch[0], ch[1], ch[2]);
printf(" moat volume %.0f m^3 <-- ONE edit today\n\n",
8.0 * ch[0] * ch[1] * ch[2]);
// BUILD-COST PROBE (`--time`). Times THIS ORACLE's flood fill + greedy merge,
// which is the same rasterize-and-fill libdc's build_shell runs before it
// extracts a surface. It is NOT a measurement of libdc: single-threaded, -O2,
// no surface extraction, no BVH. What it bounds is the SHAPE of the cost —
// whether the decomposition is in the same class as the 2.2 s shell build or
// an order out.
// THE GATE (`--assert-cap [cell]`). The measurement above is a report; this is
// the thing that fails a build.
//
// It asserts the SHIPPING configuration (0.5 m by default), not the one we
// know overflows — a gate that is red by design is a gate people learn to
// ignore. It then PRINTS what the next finer resolution would do, so whoever
// raises the resolution meets the cliff here rather than in a chunk of missing
// terrain that varies with camera angle.
//
// This is also the real verification for the loud-truncation change: the
// engine-side report only fires on an actual overflow, and forcing one needs
// headless GPU meshing. This measures the same quantity with no GPU at all.
if (argc > 2 && std::string(argv[2]) == "--assert-cap") {
const double VOXEL_SIZE = 0.224; // dc_world_setup.gd:12
const int CAP = 1536; // dc_compute.cpp:22
const float cell = (argc > 3) ? (float)atof(argv[3]) : 0.5f;
Result r = run(brushes, cell, true);
std::vector<BoxW> bw = boxes_to_world(r);
printf("assert-cap: cell %.3f m, %zu boxes level-wide, cap %d per chunk\n",
cell, bw.size(), CAP);
int worst = 0, worst_lod = -1;
long long over = 0;
for (int lod = 0; lod <= 6; lod++) {
ChunkHisto h = per_chunk_histogram(bw, VOXEL_SIZE, lod, CAP);
if (h.chunks_touched == 0) continue;
printf(" lod %d chunk %7.2f m chunks %5lld max %5d p99 %5d over %lld\n",
lod, h.chunk_span, h.chunks_touched, h.max_edits, h.p99, h.over_cap);
if (h.max_edits > worst) { worst = h.max_edits; worst_lod = lod; }
over += h.over_cap;
}
// The worst chunk is ALWAYS the coarsest LOD, because a coarse chunk is
// wider than the level and culls to nearly everything. A gate that walked
// LOD0 alone would report a comfortable number and miss the only failure.
printf(" worst chunk: %d edits at lod %d (%.0f%% of cap)\n",
worst, worst_lod, 100.0 * worst / CAP);
if (over > 0) {
printf("FAIL: %lld chunk(s) exceed MAX_GPU_EDITS — the excess is dropped\n"
" SILENTLY in the shader upload, so terrain leaks back into the\n"
" level by an amount that varies with LOD and camera.\n"
" Feed coarse LODs a coarser decomposition, or raise the cap.\n", over);
return 1;
}
printf("PASS: no chunk exceeds the cap at any LOD\n");
// Advisory: where the cliff is. Not a failure — nothing ships at this cell.
const float finer = cell * 0.5f;
Result rf = run(brushes, finer, true);
std::vector<BoxW> bf = boxes_to_world(rf);
int fworst = 0; long long fover = 0;
for (int lod = 0; lod <= 6; lod++) {
ChunkHisto h = per_chunk_histogram(bf, VOXEL_SIZE, lod, CAP);
if (h.max_edits > fworst) fworst = h.max_edits;
fover += h.over_cap;
}
printf(" (advisory) at %.3f m the worst chunk would be %d, %lld over cap%s\n",
finer, fworst, fover, fover ? " <-- DO NOT RAISE RESOLUTION WITHOUT LOD-MATCHING" : "");
return 0;
}
if (argc > 2 && std::string(argv[2]) == "--time") {
for (float cell : { 1.0f, 0.5f, 0.25f }) {
clock_t t0 = clock();
Result r = run(brushes, cell, true);
double ms = 1000.0 * (double)(clock() - t0) / CLOCKS_PER_SEC;
printf("cell %.3f m grid %dx%dx%d interior %lld cells -> %zu boxes %.0f ms\n",
cell, r.nx, r.ny, r.nz, r.interior, r.boxes.size(), ms);
fflush(stdout);
}
return 0;
}
printf("%-8s %-18s %12s %12s %12s %10s %12s\n",
"cell(m)", "grid", "solid", "exterior", "interior", "boxes", "interior m^3");
for (int mode = 0; mode < 2; mode++) {
const bool cons = (mode == 1);
printf("-- %s --\n", cons
? "CONSERVATIVE (cell solid if the brush overlaps it at all)"
: "CENTRE SAMPLE (cell solid if its centre is inside) -- misses thin walls");
for (float cell : { 2.0f, 1.0f, 0.5f, 0.25f }) {
Result r = run(brushes, cell, cons);
char grid[64];
snprintf(grid, sizeof(grid), "%dx%dx%d", r.nx, r.ny, r.nz);
printf("%-8.3f %-18s %12lld %12lld %12lld %10zu %12.0f%s\n",
cell, grid, r.solid, r.exterior, r.interior, r.boxes.size(), r.interior_m3,
r.boxes.size() > 1536 ? " OVER CAP" : "");
fflush(stdout);
}
printf("\n");
}
printf("cap: MAX_GPU_EDITS = 1536 per chunk (dc_compute.cpp:22), excess dropped silently\n");
// ---- the shell: how much of the level is boundary? ----
// No sky flag in the dump (format v1, and the published oracles read it), so
// the sky breakdown is left out rather than guessed from material ids.
printf("\n-- OUTER SHELL: FACE level --\n");
printf("%-8s %8s %8s %10s %12s %14s %14s %8s\n",
"cell", "faces", "shell", "shell%", "shell m^2", "encl. m^3", "voxel m^3", "ratio");
for (float cell : { 1.0f, 0.5f, 0.25f }) {
Result r = run(brushes, cell, true);
const int nx = r.nx, ny = r.ny, nz = r.nz;
auto at = [&](int x, int y, int z) -> uint8_t {
if (x < 0 || y < 0 || z < 0 || x >= nx || y >= ny || z >= nz) return EXTERIOR;
return r.grid[((size_t)z * ny + y) * nx + x];
};
long long total_faces = 0, shell_faces = 0;
double shell_area = 0.0, encl = 0.0;
for (const Brush& b : brushes) {
for (size_t pi = 0; pi < b.planes.size(); pi++) {
Winding w = base_winding(b.planes[pi]);
for (size_t pj = 0; pj < b.planes.size() && !w.empty(); pj++)
if (pj != pi) w = clip_winding(w, b.planes[pj]);
if (w.size() < 3) continue;
total_faces++;
Vec3 c; double area;
winding_stats(w, c, area, b.planes[pi]);
if (area <= 0.0) continue;
// Sample just OUTSIDE the face. 0.75 of a cell clears the face's
// own cell without stepping past a neighbouring thin wall.
const Plane& p = b.planes[pi];
double sx = c.x + p.nx * cell * 0.75;
double sy = c.y + p.ny * cell * 0.75;
double sz = c.z + p.nz * cell * 0.75;
int gx = (int)std::floor((sx - r.lo[0]) / r.cell);
int gy = (int)std::floor((sy - r.lo[1]) / r.cell);
int gz = (int)std::floor((sz - r.lo[2]) / r.cell);
if (at(gx, gy, gz) != EXTERIOR) continue;
shell_faces++;
shell_area += area;
// Divergence theorem: for a CLOSED, outward-wound surface,
// V = 1/3 * sum (c . n) * A. Comparing that against the flood
// fill's own solid+interior volume is a real closure test — an
// open surface does not agree with an independently measured
// volume by accident.
encl += (c.x*p.nx + c.y*p.ny + c.z*p.nz) * area / 3.0;
}
}
double voxel_m3 = (double)(r.solid + r.interior) * cell * cell * cell;
printf("%-8.3f %8lld %8lld %9.1f%% %12.0f %14.0f %14.0f %8.3f\n",
cell, total_faces, shell_faces,
100.0 * shell_faces / (double)std::max(1LL, total_faces),
shell_area, encl, voxel_m3, encl / std::max(1.0, voxel_m3));
fflush(stdout);
}
printf("\n-- OUTER SHELL: brushes touching the exterior --\n");
std::vector<uint8_t> no_sky(brushes.size(), 0);
for (float cell : { 1.0f, 0.5f, 0.25f }) {
Result r = run(brushes, cell, true);
ShellStats st = classify_brushes(brushes, r, no_sky);
printf("cell %-6.3f boundary %5d interior %5d (%.1f%% of %zu are shell)\n",
cell, st.boundary_brushes, st.interior_brushes,
100.0 * st.boundary_brushes / (double)brushes.size(), brushes.size());
fflush(stdout);
}
// ---- §7.8: what does the WORST CHUNK see? ----
const double VOXEL_SIZE = 0.224; // dc_world_setup.gd:12
const int CAP = 1536; // dc_compute.cpp:22
printf("\n=== PER-CHUNK EDIT COUNT (the cap is per chunk, not level-wide) ===\n");
printf("voxel_size %.3f m at LOD0; chunk owns 28 voxels; cull box is 32 (incl. overlap)\n",
VOXEL_SIZE);
for (float cell : { 1.0f, 0.5f, 0.25f }) {
Result r = run(brushes, cell, true);
std::vector<BoxW> bw = boxes_to_world(r);
printf("\n-- decomposition cell %.3f m: %zu boxes level-wide --\n", cell, bw.size());
printf("%-5s %10s %10s %8s %6s %6s %6s %8s %10s\n",
"lod", "chunk(m)", "chunks", "max", "p99", "p95", "p50", "mean", "over cap");
for (int lod = 0; lod <= 6; lod++) {
ChunkHisto h = per_chunk_histogram(bw, VOXEL_SIZE, lod, CAP);
if (h.chunks_touched == 0) continue;
printf("%-5d %10.2f %10lld %8d %6d %6d %6d %8.1f %10lld%s\n",
lod, h.chunk_span, h.chunks_touched, h.max_edits,
h.p99, h.p95, h.p50, h.mean, h.over_cap,
h.over_cap > 0 ? " OVER CAP" : "");
fflush(stdout);
}
}
// ---- requeue reach: one edit, how many chunks re-mesh? ----
printf("\n=== REQUEUE REACH (chunks re-meshed by ONE edit) ===\n");
{
Result r = run(brushes, 0.5f, true);
std::vector<BoxW> bw = boxes_to_world(r);
double lo[3] = { 1e30, 1e30, 1e30 }, hi[3] = { -1e30, -1e30, -1e30 };
for (const BoxW& b : bw)
for (int a = 0; a < 3; a++) { lo[a] = std::min(lo[a], b.lo[a]); hi[a] = std::max(hi[a], b.hi[a]); }
double ctr[3] = { (lo[0]+hi[0])*0.5, (lo[1]+hi[1])*0.5, (lo[2]+hi[2])*0.5 };
double half_diag = 0.0;
for (int a = 0; a < 3; a++) half_diag += (hi[a]-lo[a])*(hi[a]-lo[a])*0.25;
half_diag = std::sqrt(half_diag);
printf("level extent %.1f x %.1f x %.1f m; shell sphere >= %.1f m by construction\n",
hi[0]-lo[0], hi[1]-lo[1], hi[2]-lo[2], half_diag);
printf("%-5s %14s %14s %14s %14s\n",
"lod", "shell (whole)", "clearance 2m", "clearance 4m", "clearance 8m");
for (int lod = 0; lod <= 4; lod++) {
long long a = requeue_reach(ctr, half_diag, lo, hi, VOXEL_SIZE, lod);
long long b2 = requeue_reach(ctr, std::sqrt(3.0)*1.0, lo, hi, VOXEL_SIZE, lod);
long long b4 = requeue_reach(ctr, std::sqrt(3.0)*2.0, lo, hi, VOXEL_SIZE, lod);
long long b8 = requeue_reach(ctr, std::sqrt(3.0)*4.0, lo, hi, VOXEL_SIZE, lod);
printf("%-5d %14lld %14lld %14lld %14lld\n", lod, a, b2, b4, b8);
fflush(stdout);
}
}
return 0;
}