#ifndef DC_LEVEL_SHELL_H
#define DC_LEVEL_SHELL_H
// ---------------------------------------------------------------------------
// dc_level_shell — the closed boundary of a level's SEALED VOLUME, as a mesh.
//
// level-mesh-implementation.md §5a.2, hyper-games #25 §2. The terrain field has
// to have the level's sealed volume removed from it or the procedural ground
// fills the rooms. Today that is done with the level's inflated AABB — one box,
// 324622 m^3 against a level whose own solid is 12600, and from inside it reads
// as "a large aabb cut out around the map".
//
// This produces the surface that replaces it, for a single subtractive
// TerrainEdit::MESH.
//
// 1. rasterize every brush into a grid, CONSERVATIVELY (a cell is solid if a
// brush overlaps it at all)
// 2. flood fill from the border through non-solid cells -> EXTERIOR
// 3. emit a quad wherever a non-exterior cell touches an exterior one
// 4. snap the lattice corners onto the brush planes
//
// WHY A VOXEL BOUNDARY AND NOT THE csg4 SKIN. The skin is exact and is what the
// level renders, but it is polygon SOUP: every face is clipped independently
// against its neighbours, so a split face gains vertices its neighbour does not
// have and 45% of its edges never pair. A pseudonormal SDF needs a manifold. The
// boundary of a voxel set is closed by construction, with corners keyed on the
// integer lattice so welding is exact rather than epsilon-based.
//
// FOUR THINGS HERE ARE LOAD-BEARING AND WERE EACH FOUND BY A FAILING MEASUREMENT
// (tests/test_outer_shell.cpp is the harness; every number below is from it):
//
// CONSERVATIVE rasterization. Quake walls are commonly 16 units = 0.448 m at
// world_scale 0.028, so sampling cell CENTRES at 1 m misses them entirely, the
// flood pours through, and every room is marked exterior. The interior comes
// back EMPTY without erroring.
//
// SKY BRUSHES MUST BE INCLUDED. A sky brush is solid — it blocks the player —
// and only its rendering is special. Drop the 19 of them and the boundary has
// holes and the fill leaks out through the ceiling. Import with include_sky.
//
// THE WINDING IS REVERSED from the obvious choice. Emitting a,b,c/a,c,d gives a
// divergence volume of +38805, which by the usual convention reads as
// outward-facing, and the SDF then reports INSIDE for open void and OUTSIDE for
// sealed rooms — exactly inverted (exterior 1.2% correct). Area, closure and
// manifoldness are ALL invariant under a global flip, which is how 0.768.0
// shipped an inside-out level with a passing gate (hyper-games #9). Only an
// inside/outside test can see it.
//
// THE SNAP CLAMP MUST STAY UNDER HALF A WALL. At 1.5 cells (0.375 m) against
// 0.448 m walls, snapping pushes the two sides of a wall through each other and
// leaves inverted pockets that read as inside 10 m deep into open void — 19% of
// exterior samples wrong. At 0.5 cells (0.125 m) the sign check is 20000/20000
// on all three of interior, solid and exterior.
//
// The residual is a half-cell fringe of over-subtraction, 0.125 m at the default
// cell, which is BELOW the terrain's own 0.224 m voxel — smaller than the thing
// that will mesh it.
//
// CLEARANCE BRUSHES (CSG4Brush::clearance, hyper-games #25 §2). The fill above
// answers "what is sealed", which is the right question for a room and the wrong
// one for a passage: the bore of an archway driven into a hillside is reachable
// from the void, so it comes back EXTERIOR, no terrain is subtracted from it and
// the tunnel is full of dirt. A clearance brush is air the level OWNS — it
// rasterizes as blocking so the fill stops at it and the sealed volume runs
// through the passage, but it is counted as INTERIOR rather than solid, because
// sealed() weighs air against wall and a generous bore filed as wall would fail
// a level that is perfectly sealed. csg4 never sees one (DCBrushStore::csg4_view
// drops them; shell_view is what feeds this) — clipping the stairs against their
// own headroom would delete the treads.
//
// Engine-free (libdc rule), so it is testable from a bare main().
// ---------------------------------------------------------------------------
#include <cstdint>
#include <vector>
#include "dc_csg4.h" // CSG4Brush — the same brush view csg4 takes
namespace dc_level_shell {
// Grid resolution. 0.25 m sits just above the terrain's 0.224 m voxel, so the
// residual fringe is sub-voxel; finer costs quadratically in triangles for an
// error nothing can display.
constexpr float DEFAULT_CELL = 0.25f;
// How far a corner may be pulled, in cells. MUST stay below half the thinnest
// wall — see the header. 0.5 is measured-good; 1.5 inverts pockets.
constexpr float DEFAULT_CLAMP_CELLS = 0.5f;
struct ShellMesh {
std::vector<float> vertices; // x,y,z triples
std::vector<int> indices; // triangle list
// Diagnostics — cheap to compute here and expensive to reconstruct later.
int grid[3] = {0, 0, 0};
long long cells_solid = 0, cells_exterior = 0, cells_interior = 0;
long long snapped = 0, unmoved = 0;
double volume = 0.0; // divergence volume of the emitted surface
double area = 0.0;
// WATERTIGHTNESS, PROVED PER BUILD RATHER THAN ASSUMED FROM THE GATES.
// The offline harness proves it for a pristine START.MAP; the runtime build
// uses the level as it ACTUALLY IS, including replayed brush deletions. A
// deleted brush punches a hole in the sealed boundary, the flood fill escapes
// through it, and the shell degenerates into the boundary of the solid alone
// — still closed, still ~12600 m^3, and enclosing none of the rooms. Terrain
// then fills every one of them while every count still looks plausible, which
// is why a volume threshold alone cannot catch it.
long long boundary_edges = 0; // used by exactly one triangle; 0 = closed
long long nonmanifold_edges = 0; // used by more than two
double solid_volume = 0.0; // cells_solid * cell^3
double interior_volume = 0.0; // cells_interior * cell^3
// A sealed level encloses more AIR than its walls occupy — 21729 m^3 interior
// against 12600 m^3 solid on START. When the fill leaks, interior collapses
// toward zero, and that is the clearest single signal the boundary is holed.
bool sealed() const {
return boundary_edges == 0 && interior_volume > solid_volume * 0.5;
}
int triangle_count() const { return (int)(indices.size() / 3); }
int vertex_count() const { return (int)(vertices.size() / 3); }
};
// Build the shell. `brushes` must have had dc_csg4::compute_bounds() called on
// it. Returns false only if the input is empty or the grid would be degenerate.
//
// DEGENERATE TRIANGLES ARE KEPT ON PURPOSE. Snapping collapses stair risers to
// zero area, and deleting them TEARS the surface — welding by position first is
// not enough, and boundary edges appear as soon as the clamp exceeds 0.5 cells.
// Left in, they are inert: dc_generator_mesh_sdf.h:51-54 guards normalized() so a
// zero-length normal returns (0,0,0) rather than NaN, contributing nothing to
// pseudonormal accumulation instead of poisoning it.
bool build(const std::vector<CSG4Brush>& brushes,
ShellMesh& out,
float cell = DEFAULT_CELL,
float clamp_cells = DEFAULT_CLAMP_CELLS);
// ---------------------------------------------------------------------------
// ISLANDS — the same shell, but never one grid spanning empty space.
//
// build() takes the AABB of EVERY brush and allocates one dense grid over it, so
// its cost is set by how far apart things are rather than by how much geometry
// there is. MEASURED, two identical sealed 10x6x10 huts, 29848 triangles either
// way, cell 0.25:
//
// adjacent (12 m) 92 x 28 x 44 = 113 K cells 9.3 ms
// 200 m apart, one axis 844 x 28 x 44 = 1.0 M cells 38.7 ms
// 1 km apart, one axis 4044 x 28 x 44 = 5.0 M cells 250.0 ms
// 100 m in X and Z 444 x 28 x 444 = 5.5 M cells 165.0 ms
// 200 m in X and Z 844 x 28 x 844 = 19.9 M cells 878.2 ms
// 400 m in X and Z 1644 x 28 x1644 = 75.7 M cells 5003.2 ms
//
// 538x the cost for the same two huts. Scattered buildings — the ordinary shape
// of a large map — are the pathological case, and they arrive long before a
// genuinely large single level does.
//
// So: cluster the brushes into connected components first (union-find over AABBs
// inflated by `merge`), grid each component over ITS OWN extent, and concatenate
// what they emit. Cost becomes the sum of the buildings instead of the bounding
// box of everything, and nothing ever rasterizes the empty kilometre between.
//
// ONE MESH OUT, DELIBERATELY. The obvious next step is one TerrainEdit::MESH per
// island, and it is NOT taken here: dc_compute.cpp:1391 uploads one BVH per
// chunk, so two mesh SDFs culled into the same chunk leave the second evaluating
// against the first one's tree — silently wrong geometry. Today there is exactly
// one mesh and that cannot happen; splitting the STAMP would introduce the risk,
// and at coarse LODs a chunk spans hundreds of metres, so "far apart" is not a
// defence. Splitting the BUILD costs nothing and risks nothing, because a mesh
// with disjoint closed components is already what a detached clearance volume
// produces today.
//
// `merge` only decides what counts as one component. Too small and a level that
// is one building gets split into pieces whose grids overlap — harmless, just
// wasted work. Too large and it degenerates back to build().
constexpr float DEFAULT_MERGE = 4.0f;
bool build_islands(const std::vector<CSG4Brush>& brushes,
ShellMesh& out,
float cell = DEFAULT_CELL,
float clamp_cells = DEFAULT_CLAMP_CELLS,
float merge = DEFAULT_MERGE,
int* island_count = nullptr);
} // namespace dc_level_shell
#endif // DC_LEVEL_SHELL_H