// ============================================================================
// dc_brush_split GATE — bound the voxel pocket to the EDIT, not to the BRUSH.
//
// Measured in-game (hyper-games, 0.823.0): a 0.6m sphere carve produced 34,520
// then 45,520 pocket triangles, because a carve voxelized the WHOLE brush no
// matter how large. Pocket cost scaled with the brush; it should scale with the
// edit.
//
// The fix rests on one property of the representation: a brush IS a set of
// half-spaces, so splitting it by a plane is FREE — append the plane, and both
// halves are still valid brushes. No boolean, no geometry, no clipping. So a
// carve's AABB peels the brush into at most 6 exact outside pieces plus one
// remainder (brush AND aabb), and ONLY that remainder voxelizes.
//
// What this gate proves, and why each part earns its place:
//
// COVERAGE pieces + remainder == the original brush. Without this the split
// could silently delete solid, which would read in-game as a hole
// that appears when you carve NEAR a wall rather than into it.
// DISJOINT no two pieces overlap, and no piece enters the pocket AABB. An
// overlap is double-rendered, z-fighting geometry AND a doubled
// collider.
// EXACTNESS every piece is a real brush, so it keeps sharp edges and a convex
// collider — the entire reason for not voxelizing it.
//
// Sampling, not analysis: the union of convex pieces is not convex, so there is
// no closed form to compare against. A deterministic point sample over the
// brush AABB is the honest instrument, and the seed is fixed so a failure
// reproduces exactly.
//
// Build:
// g++ -O2 -std=c++17 -I libdc/include -o /tmp/brush_split \
// tests/test_brush_split.cpp libdc/src/dc_csg4.cpp
// ============================================================================
#include "dc_brush_store.h"
#include "dc_brush_split.h"
#include "dc_csg4.h"
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
static int failures = 0;
static void check(bool cond, const char* what, const std::string& detail = "") {
printf(" %s %s %s\n", cond ? "ok " : "FAIL", what, detail.c_str());
if (!cond) failures++;
}
static bool inside(const std::vector<ConvexPlane>& planes, float x, float y, float z, float eps = 0.0f) {
for (const ConvexPlane& p : planes)
if (p.nx*x + p.ny*y + p.nz*z - p.d > eps) return false;
return true;
}
static bool inside_aabb(const CSG4Vec3& lo, const CSG4Vec3& hi, float x, float y, float z, float eps = 0.0f) {
return x >= lo.x - eps && x <= hi.x + eps &&
y >= lo.y - eps && y <= hi.y + eps &&
z >= lo.z - eps && z <= hi.z + eps;
}
static std::vector<ConvexPlane> box_planes(float cx, float cy, float cz,
float hx, float hy, float hz) {
return {
{ 1, 0, 0, cx + hx}, {-1, 0, 0, -(cx - hx)},
{ 0, 1, 0, cy + hy}, { 0,-1, 0, -(cy - hy)},
{ 0, 0, 1, cz + hz}, { 0, 0,-1, -(cz - hz)},
};
}
// Deterministic LCG — a fixed seed so a failure is reproducible, and no
// dependency on the platform's rand().
static uint32_t rng_state = 12345u;
static float frand(float lo, float hi) {
rng_state = rng_state * 1664525u + 1013904223u;
return lo + (hi - lo) * ((float)(rng_state >> 8) / (float)(1u << 24));
}
struct Case {
const char* name;
std::vector<ConvexPlane> planes;
CSG4Vec3 carve_lo, carve_hi;
};
static void run_case(const Case& c) {
printf("\n-- %s ------------------------------------------\n", c.name);
DCBrushStore store;
std::vector<uint32_t> proj(c.planes.size(), 7u); // non-zero, so we can see it carried
const uint32_t id = store.add_brush(c.planes, proj, 3u);
const DCBrush* b = store.get(id);
dc_brush_split::SplitResult r;
const bool ok = dc_brush_split::split_by_aabb(*b, c.carve_lo, c.carve_hi, r);
check(ok, "split runs");
if (!ok) return;
printf(" %zu exact piece(s), pocket [%.2f,%.2f,%.2f]..[%.2f,%.2f,%.2f]\n",
r.pieces.size(), r.pocket_lo.x, r.pocket_lo.y, r.pocket_lo.z,
r.pocket_hi.x, r.pocket_hi.y, r.pocket_hi.z);
// Every piece must carry the parent's material and its ORIGINAL faces' proj,
// or the split silently repaints the level.
bool proj_kept = true, mat_kept = true;
for (const dc_brush_split::Piece& p : r.pieces) {
if (p.material_id != 3u) mat_kept = false;
if (p.planes.size() != p.plane_proj.size()) proj_kept = false;
if (p.planes.size() != p.plane_internal.size()) proj_kept = false;
for (size_t i = 0; i < p.planes.size(); i++)
if (!p.plane_internal[i] && p.plane_proj[i] != 7u) proj_kept = false;
}
check(mat_kept, "pieces keep the parent material");
check(proj_kept, "original faces keep their projection; arrays stay parallel");
// ---- COVERAGE + DISJOINTNESS, by deterministic sampling ----------------
int n_in_brush = 0, miscovered = 0, overlapped = 0, piece_in_pocket = 0;
const int N = 200000;
const float pad = 0.5f;
for (int i = 0; i < N; i++) {
const float x = frand(b->lo.x - pad, b->hi.x + pad);
const float y = frand(b->lo.y - pad, b->hi.y + pad);
const float z = frand(b->lo.z - pad, b->hi.z + pad);
const bool in_brush = inside(c.planes, x, y, z);
const bool in_pocket = inside_aabb(r.pocket_lo, r.pocket_hi, x, y, z);
int hits = 0;
for (const dc_brush_split::Piece& p : r.pieces)
if (inside(p.planes, x, y, z)) hits++;
if (in_brush) n_in_brush++;
// The solid must be reproduced exactly: a point in the brush is either
// in a piece, or inside the pocket AABB (where the voxel mesh takes
// over). Anything else is solid that vanished.
if (in_brush && hits == 0 && !in_pocket) miscovered++;
// ...and nothing outside the brush may appear in a piece.
if (!in_brush && hits > 0) miscovered++;
if (hits > 1) overlapped++;
// A piece reaching into the pocket would be drawn twice: once exact,
// once voxel.
if (hits > 0 && inside_aabb(r.pocket_lo, r.pocket_hi, x, y, z, -1e-4f)) piece_in_pocket++;
}
// The remainder is the clip-only solid that keeps hidden-face removal working
// inside the pocket. It must be exactly brush AND aabb, and must draw nothing.
if (r.has_remainder) {
int rem_wrong = 0;
for (int i = 0; i < 20000; i++) {
const float x = frand(b->lo.x - pad, b->hi.x + pad);
const float y = frand(b->lo.y - pad, b->hi.y + pad);
const float z = frand(b->lo.z - pad, b->hi.z + pad);
const bool want = inside(c.planes, x, y, z) &&
inside_aabb(r.pocket_lo, r.pocket_hi, x, y, z);
if (inside(r.remainder.planes, x, y, z) != want) rem_wrong++;
}
check(rem_wrong == 0, "remainder == brush AND aabb",
std::to_string(rem_wrong) + " mismatched samples");
bool all_internal = true;
for (uint8_t f : r.remainder.plane_internal) if (!f) all_internal = false;
check(all_internal && !r.remainder.plane_internal.empty(),
"remainder is clip-only (every plane internal, emits no face)");
}
check(n_in_brush > 1000, "sampling actually hit the brush",
std::to_string(n_in_brush) + " samples inside");
check(miscovered == 0, "pieces + pocket reconstruct the brush exactly",
std::to_string(miscovered) + " miscovered samples");
check(overlapped == 0, "pieces are pairwise disjoint",
std::to_string(overlapped) + " overlapping samples");
check(piece_in_pocket == 0, "no exact piece reaches into the pocket AABB",
std::to_string(piece_in_pocket) + " samples");
// ---- the point of the whole exercise ----------------------------------
// The pocket must be bounded by the EDIT, not the brush. Compare volumes:
// that ratio IS the triangle saving.
const double bvol = (double)(b->hi.x - b->lo.x) * (b->hi.y - b->lo.y) * (b->hi.z - b->lo.z);
const double pvol = (double)(r.pocket_hi.x - r.pocket_lo.x) *
(r.pocket_hi.y - r.pocket_lo.y) *
(r.pocket_hi.z - r.pocket_lo.z);
char d[128];
snprintf(d, sizeof(d), "pocket %.3f m^3 vs brush %.3f m^3 = %.1f%%",
pvol, bvol, 100.0 * pvol / std::max(bvol, 1e-9));
check(pvol <= bvol, "pocket is no larger than the brush", d);
}
int main() {
printf("=== dc_brush_split gate — bound the pocket to the edit ===\n");
Case cases[] = {
// The motivating case: a big wall, a small carve in the middle. This is
// the one that produced 34,520 triangles for a 0.6m sphere.
{"large wall, carve in the middle",
box_planes(0, 0, 0, 10.0f, 4.0f, 0.25f),
{-0.9f, -0.9f, -0.9f}, {0.9f, 0.9f, 0.9f}},
// Carve at a corner: three of the six AABB planes miss the brush
// entirely, so three pieces must come back EMPTY rather than degenerate.
{"carve at a corner",
box_planes(0, 0, 0, 2.0f, 2.0f, 2.0f),
{1.4f, 1.4f, 1.4f}, {3.0f, 3.0f, 3.0f}},
// Carve swallowing the brush: every piece is empty and the pocket is the
// whole thing. Must not produce a bogus piece.
{"carve larger than the brush",
box_planes(0, 0, 0, 0.5f, 0.5f, 0.5f),
{-2.0f, -2.0f, -2.0f}, {2.0f, 2.0f, 2.0f}},
// A non-axis-aligned brush, because Quake maps are 91.7% axis-aligned
// and the other 8.3% is where every previous bug in this pipeline lived.
{"oblique brush",
{{ 0.7071f, 0.7071f, 0, 3.0f}, {-0.7071f, -0.7071f, 0, 3.0f},
{-0.7071f, 0.7071f, 0, 3.0f}, { 0.7071f, -0.7071f, 0, 3.0f},
{ 0, 0, 1, 1.0f}, { 0, 0, -1, 1.0f}},
{-0.6f, -0.6f, -0.6f}, {0.6f, 0.6f, 0.6f}},
};
for (const Case& c : cases) run_case(c);
printf("\n=== %s ===\n", failures == 0 ? "PASS" : "FAIL");
return failures == 0 ? 0 : 1;
}