// ============================================================================
// SUBTRACT — A \ B, as a set of convex brushes.
//
// Clip, CSG subtract and "cut a shape into a face" are ONE operation with different
// cutters (docs/build-mode-operators.md §5b). Each takes an edit and must produce a
// SET OF CONVEX BRUSHES; they differ only in how many planes the cutter carries:
//
// one plane -> two pieces, both kept (this is split_brush)
// N planes -> up to N pieces (this)
//
// The construction is the standard brush-editor one, and it is exact:
//
// piece_i = A ∩ outside(B.plane[i]) ∩ inside(B.plane[0..i-1])
//
// Every piece is an intersection of half-spaces, which is what a brush IS — so
// nothing is hulled, nothing is triangulated, and no piece can come out invalid. The
// pieces are disjoint (piece_i is outside plane i, every later piece is inside it)
// and their union is exactly A minus B. That last claim is the one worth testing, so
// this tests it by VOLUME rather than by counting faces: a face count tells you the
// shape changed, not that it changed into the right shape.
//
// Build: g++ -O2 -std=c++17 -I libdc/include -o /tmp/bsub \
// tests/test_brush_subtract.cpp libdc/src/dc_csg4.cpp
// ============================================================================
#include "dc_brush_store.h"
#include "dc_csg4.h"
#include <cstdio>
#include <cmath>
#include <vector>
static int fails = 0;
static void ok(const char* what, bool cond) {
if (!cond) fails++;
std::printf(" %-64s %s\n", what, cond ? "OK" : "**FAIL**");
}
static void eqi(const char* what, long got, long want) {
bool c = got == want;
if (!c) fails++;
std::printf(" %-64s %-4ld want %-4ld %s\n", what, got, want, c ? "OK" : "**FAIL**");
}
static std::vector<ConvexPlane> box(float x0, float y0, float z0,
float x1, float y1, float z1) {
return {
{-1, 0, 0, -x0}, {1, 0, 0, x1},
{0, -1, 0, -y0}, {0, 1, 0, y1},
{0, 0, -1, -z0}, {0, 0, 1, z1},
};
}
static bool inside(const std::vector<ConvexPlane>& pl, float x, float y, float z,
float eps = 1e-4f) {
for (const ConvexPlane& p : pl)
if (p.nx * x + p.ny * y + p.nz * z > p.d + eps) return false;
return true;
}
static int live_brushes(const DCBrushStore& s) {
int n = 0;
for (const DCBrush& b : s.brushes()) if (!b.tombstoned) n++;
return n;
}
static bool inside_brush(const DCBrushStore& s, uint32_t id, float x, float y, float z) {
const DCBrush* b = s.get(id);
if (!b || b->tombstoned) return false;
return inside(b->planes, x, y, z);
}
int main() {
std::printf("=== brush subtract: A \\ B as convex pieces ===\n\n");
std::printf("-- a doorway: subtract a door-sized box from a wall --\n");
{
DCBrushStore s;
// A wall 0..8 x 0..4 x 0..1, and a doorway 3..5 x 0..3 punched through it.
uint32_t wall = s.add_brush(box(0, 0, 0, 8, 4, 1), {}, 7, 0, false, "wall:1");
std::vector<uint32_t> pieces;
const int n = s.subtract_brush(wall, box(3, -1, -1, 5, 3, 2), "alice:1", pieces);
ok("the subtract is accepted", n > 0);
std::printf(" -> %d pieces\n", n);
// THE VOLUME TEST. Sample the wall's bounding box: every point that was in
// the wall and NOT in the doorway must be in exactly one piece, and no point
// in the doorway may be in any piece.
int wrong_in = 0, wrong_out = 0, overlap = 0;
for (int ix = 0; ix <= 32; ix++)
for (int iy = 0; iy <= 16; iy++)
for (int iz = 0; iz <= 4; iz++) {
const float x = 0.0f + (float)ix * 0.25f;
const float y = 0.0f + (float)iy * 0.25f;
const float z = 0.0f + (float)iz * 0.25f;
const bool in_wall = inside(box(0, 0, 0, 8, 4, 1), x, y, z, -1e-3f);
const bool in_door = inside(box(3, -1, -1, 5, 3, 2), x, y, z, -1e-3f);
int hits = 0;
for (uint32_t p : pieces) if (inside_brush(s, p, x, y, z)) hits++;
// STRICT interior for the overlap count. Adjacent pieces SHARE the plane
// they were cut on — piece_i is outside it and piece_i+1 is inside it —
// so a point exactly on that plane is in both closed half-spaces and
// always will be. The property worth having is that no VOLUME is covered
// twice, not that the pieces fail to touch.
int strict = 0;
for (uint32_t p : pieces) {
const DCBrush* pb = s.get(p);
if (pb && !pb->tombstoned && inside(pb->planes, x, y, z, -1e-3f)) strict++;
}
if (in_wall && !in_door && hits == 0) wrong_out++; // lost volume
if (in_door && hits > 0) wrong_in++; // the hole is filled
if (strict > 1) overlap++; // shared VOLUME
}
eqi("no point of the wall outside the doorway was lost", wrong_out, 0);
eqi("no point inside the doorway survived", wrong_in, 0);
eqi("and the pieces do not overlap each other", overlap, 0);
bool all_solid = true;
for (uint32_t p : pieces)
if (s.live_face_count(p) < 4) all_solid = false;
ok("every piece is a real solid (>= 4 live faces)", all_solid);
}
std::printf("\n-- one plane is a CLIP: the degenerate case of the same thing --\n");
{
DCBrushStore s;
uint32_t b = s.add_brush(box(0, 0, 0, 8, 4, 1), {}, 7, 0, false, "wall:2");
std::vector<ConvexPlane> half = { {1, 0, 0, 4.0f} }; // keep x >= 4
std::vector<uint32_t> pieces;
const int n = s.subtract_brush(b, half, "alice:2", pieces);
eqi("exactly one piece comes back", (long)n, 1);
ok("the kept half is the far side", inside_brush(s, pieces[0], 6, 2, 0.5f));
ok("and the near side is gone", !inside_brush(s, pieces[0], 2, 2, 0.5f));
}
std::printf("\n-- a cutter that swallows the brush consumes it --\n");
{
DCBrushStore s;
uint32_t b = s.add_brush(box(0, 0, 0, 1, 1, 1), {}, 7, 0, false, "small:1");
std::vector<uint32_t> pieces;
const int n = s.subtract_brush(b, box(-5, -5, -5, 5, 5, 5), "alice:3", pieces);
eqi("zero pieces", (long)n, 0);
ok("and the brush is tombstoned, not left floating", s.get(b) == nullptr ||
s.get(b)->tombstoned);
}
std::printf("\n-- a cutter that misses is REFUSED, and changes nothing --\n");
{
DCBrushStore s;
uint32_t b = s.add_brush(box(0, 0, 0, 1, 1, 1), {}, 7, 0, false, "small:2");
std::vector<uint32_t> pieces;
const int n = s.subtract_brush(b, box(50, 50, 50, 51, 51, 51), "alice:4", pieces);
eqi("refused", (long)n, -1);
ok("the brush is untouched", inside_brush(s, b, 0.5f, 0.5f, 0.5f));
ok("and still has its own key", s.brush_by_key("small:2") == b);
}
std::printf("\n-- deterministic: two peers, one record, identical solids --\n");
{
DCBrushStore a, b;
uint32_t wa = a.add_brush(box(0, 0, 0, 8, 4, 1), {}, 7, 0, false, "wall:3");
uint32_t wb = b.add_brush(box(0, 0, 0, 8, 4, 1), {}, 7, 0, false, "wall:3");
std::vector<uint32_t> pa, pb;
a.subtract_brush(wa, box(3, -1, -1, 5, 3, 2), "alice:5", pa);
b.subtract_brush(wb, box(3, -1, -1, 5, 3, 2), "alice:5", pb);
eqi("same piece count", (long)pa.size(), (long)pb.size());
bool same = pa.size() == pb.size();
for (size_t i = 0; i < pa.size() && same; i++) {
const DCBrush* x = a.get(pa[i]);
const DCBrush* y = b.get(pb[i]);
if (!x || !y || x->planes.size() != y->planes.size() || x->key != y->key) {
same = false;
break;
}
for (size_t j = 0; j < x->planes.size(); j++)
if (std::fabs(x->planes[j].d - y->planes[j].d) > 1e-6f ||
std::fabs(x->planes[j].nx - y->planes[j].nx) > 1e-6f)
same = false;
}
ok("identical plane sets and identical durable keys", same);
}
std::printf("\n-- a FOLD replay does not double the geometry --\n");
{
// The real mechanism, not a bare second call: a fold rewinds to base and
// replays every live record. So the question is not "is subtract_brush
// idempotent on its own output" (it is not, and should not be — subtracting
// twice from an already-cut brush is a different edit); it is whether
// replaying the RECORD lands on the same brushes.
DCBrushStore s;
// AN IMPORTED WALL — add_brush sets from_import = key.empty(), and
// reset_to_base tombstones everything that was CREATED. A wall the editor
// made is supposed to vanish on a rewind and come back from its own record;
// the brush being subtracted FROM here has to be one the .MAP supplied, or
// the test is rewinding away its own subject.
uint32_t w = s.add_brush(box(0, 0, 0, 8, 4, 1), {}, 7, 0, false, "");
std::vector<uint32_t> first, again;
const int n1 = s.subtract_brush(w, box(3, -1, -1, 5, 3, 2), "alice:6", first);
const int before = live_brushes(s);
s.reset_to_base(); // what fold() does first
const int n2 = s.subtract_brush(w, box(3, -1, -1, 5, 3, 2), "alice:6", again);
eqi("the same piece count after a rewind and replay", (long)n2, (long)n1);
ok("the same brush ids, not a second set", first == again);
eqi("and no brushes accumulated", (long)live_brushes(s), (long)before);
}
std::printf("\n%s\n", fails ? "FAILED" : "PASS");
return fails ? 1 : 0;
}