// Build+run: g++ -std=c++17 -I../include test_cull_support.cpp -o test_cull_support && ./test_cull_support
//
// THE CULL-VOLUME INVARIANT — hyper-games #42 P2.
//
// For every shape: if an edit changes density at p, then p lies inside that
// edit's declared cull volume.
//
// cull_edits_for_chunk (dc_terrain.cpp:49) drops any edit whose volume misses a
// chunk's AABB. That is only sound if the volume CONTAINS the edit's support —
// otherwise a real change falls outside the volume, the edit is culled from the
// chunk that needed it, and geometry silently disappears. Testing point-in-volume
// is the right reduction: if the support is inside the volume, no chunk that
// misses the volume can contain any point of the support.
//
// This property was never asserted, and it cost hyper-games #41 four rounds of
// debugging. The MESH radius was half the AABB diagonal — the radius of a sphere
// about the BOX CENTRE — while the cull test is about the STAMP POINT, the mesh
// centroid. Those coincide only when the vertices are symmetric about their
// bounds, and the level shell is the exact opposite: 284k vertices in the level
// plus ~2.5k in an arch 95 m away leaves the centroid on the level while the AABB
// reaches out to the arch. The subtract was correct and was thrown away one layer
// below, by `if (dist2 > radius*radius) continue;`.
//
// Case 5 below REPRODUCES that, so this file is not only a regression lock: it is
// red for the right reason if anyone recomputes a radius the old way.
#include "dc_edit.h"
#include <cstdio>
#include <cmath>
#include <vector>
#include <random>
#include <memory>
// An asymmetric "mesh": a big ball at the origin plus a small ball far along +X.
// Deliberately the shell's geometry — the mass (and so the centroid) sits at the
// origin while the bounds reach out to the far ball.
struct TwoBallSDF : public DCGenerator {
float far_x, r_big, r_small;
TwoBallSDF(float fx, float rb, float rs) : far_x(fx), r_big(rb), r_small(rs) {}
// positive = inside, matching the MESH branch's `mesh_d` convention.
float evaluate(float x, float y, float z, float) override {
float d1 = r_big - std::sqrt(x * x + y * y + z * z);
float dx = x - far_x;
float d2 = r_small - std::sqrt(dx * dx + y * y + z * z);
return d1 > d2 ? d1 : d2;
}
// The VIRTUAL, not a same-named sibling. Defining bounds() instead left the
// generator "unbounded", add_mesh returned FLT_MAX, and the positive mesh case
// passed trivially because a cull volume of everything contains everything.
// The run printed the FLT_MAX radius, which is how it was caught.
bool get_bounds(float lo[3], float hi[3]) const override {
lo[0] = -r_big; hi[0] = far_x + r_small;
lo[1] = -r_big; hi[1] = r_big;
lo[2] = -r_big; hi[2] = r_big;
return true;
}
};
static int failures = 0;
// The cull volume, exactly as cull_edits_for_chunk states it: BOX is an AABB
// about (x,y,z) with half_ext; everything else is a sphere of `radius`.
static bool inside_cull_volume(const TerrainEdit& e, float px, float py, float pz) {
if (e.shape == TerrainEdit::BOX) {
return std::fabs(px - e.x) <= e.half_ext[0] &&
std::fabs(py - e.y) <= e.half_ext[1] &&
std::fabs(pz - e.z) <= e.half_ext[2];
}
float dx = px - e.x, dy = py - e.y, dz = pz - e.z;
return dx * dx + dy * dy + dz * dz <= e.radius * e.radius;
}
// THE REFERENCE MUST BE UNGATED, and this is the whole reason the bug lived.
//
// DCEditList::apply's MESH branch begins `if (dist2 > radius*radius) continue;`.
// Ask it whether a too-small radius loses anything and it says no — because the
// radius it is being judged on is the one doing the skipping. A gated oracle
// certifies its own gate. The first cut of this test made exactly that mistake
// and reported the #41 radius as correct.
//
// So this mirrors dc_edit.h's math with every RADIUS/AABB early-out removed, and
// keeps only the gates that are part of the SHAPE. The metaball sphere's
// `dist_sq < r_sq` is one of those: t = 1 - d^2/r^2 turns positive again outside
// the radius, so the bound defines the blend rather than optimising it.
static float ungated_apply(const TerrainEdit& e, float wx, float wy, float wz, float base) {
float result = base;
if (e.shape == TerrainEdit::SPHERE) {
float dx = wx - e.x, dy = wy - e.y, dz = wz - e.z;
float dist_sq = dx*dx + dy*dy + dz*dz;
if (e.op == TerrainEdit::OP_HARD) {
float sdf = std::sqrt(dist_sq) - e.radius; // ungated
result = (e.strength < 0.0f) ? std::min(result, sdf) : std::max(result, -sdf);
} else if (dist_sq < e.radius * e.radius) { // SHAPE, not a cull
float t = 1.0f - dist_sq / (e.radius * e.radius);
result += e.strength * t * t;
}
} else if (e.shape == TerrainEdit::BOX) {
float dx = std::fabs(wx - e.x) - e.half_ext[0];
float dy = std::fabs(wy - e.y) - e.half_ext[1];
float dz = std::fabs(wz - e.z) - e.half_ext[2];
float max_comp = std::max({dx, dy, dz});
float outside = std::sqrt(std::max(dx,0.f)*std::max(dx,0.f) +
std::max(dy,0.f)*std::max(dy,0.f) +
std::max(dz,0.f)*std::max(dz,0.f));
float sdf = outside + std::min(max_comp, 0.0f);
result = (e.strength < 0.0f) ? std::min(result, sdf) : std::max(result, -sdf);
} else if (e.shape == TerrainEdit::MESH && e.mesh_sdf) {
float lx = (wx - e.x) / e.scale, ly = (wy - e.y) / e.scale, lz = (wz - e.z) / e.scale;
float sdf = -e.mesh_sdf->evaluate(lx, ly, lz, 0.0f); // ungated
result = (e.strength < 0.0f) ? std::min(result, sdf) : std::max(result, -sdf);
} else if (e.shape == TerrainEdit::CONVEX) {
float f = -1e30f;
for (const auto& pl : e.planes) {
float dp = pl.nx*wx + pl.ny*wy + pl.nz*wz - pl.d;
if (dp > f) f = dp;
}
result = (e.strength < 0.0f) ? std::min(result, f) : std::max(result, -f);
}
return result;
}
// SIGN, not value. A subtract far outside a box does min(50, sdf) and drops the
// density from 50 to 3 — the value moved, the classification did not, and no
// surface is anywhere near. What culling may not lose is a point whose SOLID/AIR
// answer the edit changes; that is the thing geometry is made of, and it is the
// same oracle test_convex.cpp uses.
static int sgn(float v) { return v > 0.f ? 1 : (v < 0.f ? -1 : 0); }
// radius_override < 0 means "use what the list computed". The negative cases
// corrupt the snapshot rather than passing a bad radius in, because the
// production API no longer HAS a radius parameter — that is item 3 of the plan,
// and it is the structural half of this invariant. Corrupting the snapshot keeps
// the proof: the assertion catches a wrong radius however it got there.
static void check(const char* name, const DCEditList& list, float span, bool expect_pass,
float radius_override = -1.0f) {
auto edits = list.snapshot();
if (edits.size() != 1) { printf(" %-34s SETUP ERROR\n", name); failures++; return; }
if (radius_override >= 0.0f) edits[0].radius = radius_override;
const TerrainEdit& e = edits[0];
std::mt19937 rng(12345);
std::uniform_real_distribution<float> U(-span, span);
int escaped = 0, flipped = 0;
for (int i = 0; i < 200000; i++) {
float px = U(rng), py = U(rng), pz = U(rng);
// Both bases: an add can only flip a point that is currently air, a
// subtract only one that is currently solid. One base tests half the support.
for (float base : { -50.0f, 50.0f }) {
float truth = ungated_apply(e, px, py, pz, base);
if (sgn(truth) == sgn(base)) continue;
flipped++;
if (!inside_cull_volume(e, px, py, pz)) escaped++;
}
}
bool passed = (escaped == 0);
printf(" %-34s %-8s sign-flips=%-8d outside-volume=%d\n",
name, passed ? "OK" : "ESCAPED", flipped, escaped);
if (flipped == 0) { printf(" (vacuous — no sign flips; the case is not exercising anything)\n"); failures++; }
if (passed != expect_pass) failures++;
}
int main() {
printf("cull-volume invariant: a SIGN change outside the declared volume is a BUG\n\n");
// ---- 1-2. SPHERE, both CSG ops ----------------------------------------
for (int hard = 0; hard < 2; hard++) {
// The SMOOTH sphere is additive — it contributes strength*t^2, t <= 1 —
// so a strength of 1 cannot move a base of 50 across zero and the case
// measures nothing. The magnitude has to exceed the base or the test is
// vacuous, which the run reports rather than passing quietly.
for (float strength : hard ? std::vector<float>{ 1.0f, -1.0f }
: std::vector<float>{ 100.0f, -100.0f }) {
DCEditList l;
l.add_sphere(0, 0, 0, 2.0f, strength,
hard ? TerrainEdit::OP_HARD : TerrainEdit::OP_SMOOTH);
char nm[64];
snprintf(nm, sizeof(nm), "SPHERE %s %s", hard ? "hard" : "smooth",
strength > 0 ? "add" : "sub");
check(nm, l, 4.0f, true);
}
}
// ---- 3. BOX ------------------------------------------------------------
for (float strength : { 1.0f, -1.0f }) {
DCEditList l;
l.add_box(0.5f, -0.25f, 0.75f, 1.0f, 2.0f, 0.5f, strength);
check(strength > 0 ? "BOX add" : "BOX sub", l, 5.0f, true);
}
// ---- 4. CONVEX ---------------------------------------------------------
// add_convex computes its radius from the plane set (item 3). A cube of
// half-extent 1 needs sqrt(3); anything less clips the corners.
{
std::vector<ConvexPlane> cube = {
{ 1, 0, 0, 1}, {-1, 0, 0, 1},
{ 0, 1, 0, 1}, { 0,-1, 0, 1},
{ 0, 0, 1, 1}, { 0, 0,-1, 1},
};
DCEditList l;
l.add_convex(0, 0, 0, cube, -1.0f);
printf("\n convex radius computed from planes: %.4f (cube half-extent 1 needs %.4f)\n",
l.snapshot()[0].radius, std::sqrt(3.0f));
check("CONVEX cube, computed radius", l, 3.0f, true);
// The corner-clipping mistake, stated: an inscribed-sphere radius looks
// right and misses all eight corners. No longer reachable through the API.
check("CONVEX cube, inscribed radius", l, 3.0f, false, 1.0f);
}
// ---- 5. MESH — the #41 bug, reproduced --------------------------------
{
const float FAR = 12.0f, RB = 3.0f, RS = 0.6f;
auto sdf = std::make_shared<TwoBallSDF>(FAR, RB, RS);
float lo[3], hi[3];
sdf->get_bounds(lo, hi);
// The stamp point is the mesh CENTROID, which for this shape sits on the
// big ball — NOT at the centre of the bounds.
const float stamp_x = 0.0f, stamp_y = 0.0f, stamp_z = 0.0f;
// THE OLD RADIUS: half the AABB diagonal. Correct for a sphere about the
// box centre; wrong for one about the stamp point.
float half_diag = 0.5f * std::sqrt(
(hi[0]-lo[0])*(hi[0]-lo[0]) + (hi[1]-lo[1])*(hi[1]-lo[1]) + (hi[2]-lo[2])*(hi[2]-lo[2]));
// THE FIX: the furthest AABB corner FROM THE STAMP POINT.
float furthest = 0.0f;
for (int cx = 0; cx < 2; cx++)
for (int cy = 0; cy < 2; cy++)
for (int cz = 0; cz < 2; cz++) {
float dx = (cx ? hi[0] : lo[0]) - stamp_x;
float dy = (cy ? hi[1] : lo[1]) - stamp_y;
float dz = (cz ? hi[2] : lo[2]) - stamp_z;
float d = std::sqrt(dx*dx + dy*dy + dz*dz);
if (d > furthest) furthest = d;
}
printf("\n mesh radii: half-diagonal %.3f (old) furthest-corner %.3f (fixed)\n",
half_diag, furthest);
DCEditList l;
l.add_mesh(stamp_x, stamp_y, stamp_z, 1.0f, -1.0f, sdf);
printf(" mesh radius computed by the list: %.3f\n", l.snapshot()[0].radius);
// #41's radius, no longer reachable through the API — asserted anyway, so
// the invariant stays proven rather than merely unreachable.
check("MESH, half-AABB-diagonal radius", l, 16.0f, false, half_diag);
check("MESH, computed radius", l, 16.0f, true);
(void)furthest;
}
printf("\n%s (%d unexpected)\n", failures ? "FAIL" : "PASS", failures);
return failures ? 1 : 0;
}