// ============================================================================
// THE OTHER TWO CSG OPS — intersect, and convex merge.
//
// With subtract_brush already built, these complete the set, and both fall straight
// out of what a brush already is:
//
// INTERSECT A ∩ B is the union of their PLANE SETS. An intersection of
// half-spaces intersected with another is still an intersection of
// half-spaces — one brush, no pieces, nothing derived.
//
// MERGE A ∪ B is NOT convex and therefore is not a brush at all. What every
// brush editor offers instead is a CONVEX MERGE: the hull of both
// vertex sets. TrenchBroom's csgConvexMerge does exactly this
// (Map_Geometry.cpp:607-640 — it collects the selected brushes'
// vertices and builds a Polyhedron3 from the points), and it is named
// "convex merge" rather than "union" for precisely this reason. So is
// ours, and the test below pins the difference down rather than
// papering over it: merging two separated cubes fills the gap between
// them, and that is the CORRECT answer for this operation.
//
// Build: g++ -O2 -std=c++17 -I libdc/include -o /tmp/bcsg \
// tests/test_brush_csg.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 in_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;
for (const ConvexPlane& p : b->planes)
if (p.nx * x + p.ny * y + p.nz * z > p.d + 1e-4f) 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;
}
int main() {
std::printf("=== brush csg: intersect and convex merge ===\n\n");
std::printf("-- INTERSECT is the union of the plane sets --\n");
{
DCBrushStore s;
uint32_t a = s.add_brush(box(0, 0, 0, 4, 4, 4), {}, 7, 0, false, "a:1");
ok("two boxes overlapping in an octant intersect",
s.intersect_brush(a, box(2, 2, 2, 6, 6, 6), "alice:1"));
ok("a point in the overlap survives", in_brush(s, a, 3, 3, 3));
ok("a point only in A is gone", !in_brush(s, a, 1, 1, 1));
ok("a point only in B is gone too", !in_brush(s, a, 5, 5, 5));
eqi("still ONE brush — an intersection needs no pieces", live_brushes(s), 1);
}
std::printf("\n-- an intersection that is empty is REFUSED --\n");
{
DCBrushStore s;
uint32_t a = s.add_brush(box(0, 0, 0, 1, 1, 1), {}, 7, 0, false, "a:2");
ok("boxes that do not meet are refused",
!s.intersect_brush(a, box(50, 50, 50, 51, 51, 51), "alice:2"));
ok("and A is untouched", in_brush(s, a, 0.5f, 0.5f, 0.5f));
}
std::printf("\n-- CONVEX MERGE is a hull, and that is not a union --\n");
{
DCBrushStore s;
// Two cubes with a gap between them: 0..1 and 3..4 on x.
uint32_t a = s.add_brush(box(0, 0, 0, 1, 1, 1), {}, 7, 0, false, "a:3");
uint32_t b = s.add_brush(box(3, 0, 0, 4, 1, 1), {}, 7, 0, false, "b:3");
std::vector<uint32_t> ids = {a, b};
ok("the merge is accepted", s.merge_brushes(ids, "alice:3"));
ok("both originals are inside the result", in_brush(s, a, 0.5f, 0.5f, 0.5f) &&
in_brush(s, a, 3.5f, 0.5f, 0.5f));
// THE HONEST ASSERTION. A union would leave the gap empty; a convex merge
// fills it, because the hull of both point sets spans them. That is what
// this operation IS, and a test that pretended otherwise would be lying
// about the tool.
ok("AND SO IS THE GAP — this is a hull, not a union",
in_brush(s, a, 2.0f, 0.5f, 0.5f));
eqi("the merged brushes collapse to one", live_brushes(s), 1);
}
std::printf("\n-- merging touching boxes gives the shape you expect --\n");
{
DCBrushStore s;
uint32_t a = s.add_brush(box(0, 0, 0, 2, 1, 1), {}, 7, 0, false, "a:4");
uint32_t b = s.add_brush(box(2, 0, 0, 4, 1, 1), {}, 7, 0, false, "b:4");
std::vector<uint32_t> ids = {a, b};
ok("the merge is accepted", s.merge_brushes(ids, "alice:4"));
ok("it spans both", in_brush(s, a, 0.5f, 0.5f, 0.5f) &&
in_brush(s, a, 3.5f, 0.5f, 0.5f));
ok("and nothing outside them", !in_brush(s, a, 5.0f, 0.5f, 0.5f));
eqi("a box, so six faces", (long)s.live_face_count(a), 6);
}
std::printf("\n-- refusals --\n");
{
DCBrushStore s;
uint32_t a = s.add_brush(box(0, 0, 0, 1, 1, 1), {}, 7, 0, false, "a:5");
std::vector<uint32_t> one = {a};
ok("merging one brush is refused — there is nothing to merge with",
!s.merge_brushes(one, "alice:5"));
std::vector<uint32_t> none;
ok("merging nothing is refused", !s.merge_brushes(none, "alice:6"));
ok("and A is still there", in_brush(s, a, 0.5f, 0.5f, 0.5f));
}
std::printf("\n-- deterministic across peers --\n");
{
DCBrushStore p, q;
uint32_t pa = p.add_brush(box(0, 0, 0, 1, 1, 1), {}, 7, 0, false, "a:6");
uint32_t pb = p.add_brush(box(3, 0, 0, 4, 1, 1), {}, 7, 0, false, "b:6");
uint32_t qa = q.add_brush(box(0, 0, 0, 1, 1, 1), {}, 7, 0, false, "a:6");
uint32_t qb = q.add_brush(box(3, 0, 0, 4, 1, 1), {}, 7, 0, false, "b:6");
std::vector<uint32_t> pi = {pa, pb}, qi = {qa, qb};
p.merge_brushes(pi, "alice:7");
q.merge_brushes(qi, "alice:7");
const DCBrush* x = p.get(pa);
const DCBrush* y = q.get(qa);
bool same = x && y && x->planes.size() == y->planes.size() && x->key == y->key;
for (size_t i = 0; same && i < x->planes.size(); i++)
if (std::fabs(x->planes[i].d - y->planes[i].d) > 1e-6f ||
std::fabs(x->planes[i].nx - y->planes[i].nx) > 1e-6f)
same = false;
ok("identical plane sets, identical order, identical key", same);
}
std::printf("\n%s\n", fails ? "FAILED" : "PASS");
return fails ? 1 : 0;
}