#include "dc_csg4.h"
#include <cmath>
#include <algorithm>
// ---------------------------------------------------------------------------
// Local vector helpers (kept file-static; libdc has no shared vec type)
// ---------------------------------------------------------------------------
namespace {
typedef CSG4Vec3 V3;
inline V3 add(V3 a, V3 b) { return {a.x+b.x, a.y+b.y, a.z+b.z}; }
inline V3 sub(V3 a, V3 b) { return {a.x-b.x, a.y-b.y, a.z-b.z}; }
inline V3 mul(V3 a, float s) { return {a.x*s, a.y*s, a.z*s}; }
inline float dot(V3 a, V3 b) { return a.x*b.x + a.y*b.y + a.z*b.z; }
inline V3 cross(V3 a, V3 b) {
return {a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x};
}
inline float len(V3 a) { return std::sqrt(dot(a,a)); }
inline V3 norm(V3 a) { float l = len(a); return l > 1e-20f ? mul(a, 1.0f/l) : a; }
inline V3 plane_n(const ConvexPlane& p) { return {p.nx, p.ny, p.nz}; }
// Split a winding by a plane into front (n·p − d > 0) and back (< 0), inserting
// the crossing point on BOTH sides so the two fragments stay watertight.
// (winding.c ClipWinding / SplitFace.)
void split_winding(const std::vector<V3>& w, V3 n, float d,
std::vector<V3>& front, std::vector<V3>& back) {
front.clear();
back.clear();
const int cnt = (int)w.size();
if (cnt == 0) return;
std::vector<float> dist(cnt);
int nf = 0, nb = 0;
for (int i = 0; i < cnt; i++) {
dist[i] = dot(n, w[i]) - d;
if (dist[i] > dc_csg4::ON_EPS) nf++;
else if (dist[i] < -dc_csg4::ON_EPS) nb++;
}
if (!nf) { back = w; return; } // wholly behind
if (!nb) { front = w; return; } // wholly in front
for (int i = 0; i < cnt; i++) {
const V3& p1 = w[i];
if (dist[i] > dc_csg4::ON_EPS) front.push_back(p1);
else if (dist[i] < -dc_csg4::ON_EPS) back.push_back(p1);
else { front.push_back(p1); back.push_back(p1); continue; } // on the plane
const int j = (i + 1) % cnt;
const bool crosses =
(dist[i] > dc_csg4::ON_EPS && dist[j] < -dc_csg4::ON_EPS) ||
(dist[i] < -dc_csg4::ON_EPS && dist[j] > dc_csg4::ON_EPS);
if (crosses) {
const float t = dist[i] / (dist[i] - dist[j]);
const V3 mid = add(p1, mul(sub(w[j], p1), t));
front.push_back(mid);
back.push_back(mid);
}
}
}
// csg4.c ClipInside — remove the part of `face` lying inside brush `B`.
// Appends surviving fragments to `out`. Sets `fully_removed` when the whole face
// was interior. If nothing was inside, the face is appended INTACT (never
// fragment for free — spurious splits would inflate the triangle count).
void clip_inside(const std::vector<V3>& face, V3 face_n, float face_d,
const CSG4Brush& B, uint32_t self_index, uint32_t other_index,
std::vector<std::vector<V3>>& out, bool& fully_removed) {
fully_removed = false;
// Coplanar handling. A plane of B coplanar with the face is NOT a clipping
// plane — the brush's OTHER planes define the 2D extent of the shared region.
// same-facing : the two brushes are flush on one surface. Keep it exactly
// once (lower index wins) or they z-fight.
// opposite : the brushes abut face-to-face. The shared region is
// interior to the union — BOTH lose it.
std::vector<const ConvexPlane*> clip;
clip.reserve(B.plane_count);
int coplanar = 0; // +1 same-facing, -1 opposite-facing, 0 none
for (uint32_t i = 0; i < B.plane_count; i++) {
const ConvexPlane& q = B.planes[i];
const V3 qn = plane_n(q);
const float nd = dot(qn, face_n);
if (std::fabs(nd) > dc_csg4::COPLANAR_N) {
// compare offsets in the face's own orientation
const float qd = (nd > 0.0f) ? q.d : -q.d;
if (std::fabs(qd - face_d) < dc_csg4::COPLANAR_D) {
coplanar = (nd > 0.0f) ? 1 : -1;
continue;
}
}
clip.push_back(&q);
}
if (coplanar == 1 && self_index < other_index) {
out.push_back(face); // this brush owns the shared surface
return;
}
std::vector<std::vector<V3>> keep;
std::vector<V3> cur = face, front, back;
for (const ConvexPlane* q : clip) {
split_winding(cur, plane_n(*q), q->d, front, back);
if (front.size() >= 3) keep.push_back(front);
if (back.size() < 3) { // nothing left inside -> face is wholly outside
out.push_back(face);
return;
}
cur.swap(back);
}
// `cur` is inside B on every clipping plane -> discard it.
if (keep.empty()) { fully_removed = true; return; }
for (auto& k : keep) out.push_back(std::move(k));
}
inline bool aabb_overlap(const CSG4Brush& a, const CSG4Brush& b, float e) {
return !(a.hi.x + e < b.lo.x || a.lo.x - e > b.hi.x ||
a.hi.y + e < b.lo.y || a.lo.y - e > b.hi.y ||
a.hi.z + e < b.lo.z || a.lo.z - e > b.hi.z);
}
} // namespace
// ---------------------------------------------------------------------------
namespace dc_csg4 {
bool face_winding(const CSG4Brush& b, uint32_t fi, std::vector<CSG4Vec3>& out, float eps) {
out.clear();
if (fi >= b.plane_count) return false;
const ConvexPlane* P = b.planes;
const int n = (int)b.plane_count;
const V3 fn = plane_n(P[fi]);
// Every triple-plane intersection that satisfies all half-spaces is a corner.
for (int i = 0; i < n; i++) {
if (i == (int)fi) continue;
for (int j = i + 1; j < n; j++) {
if (j == (int)fi) continue;
const V3 a = fn, c = plane_n(P[i]), e = plane_n(P[j]);
const float den = dot(a, cross(c, e));
if (std::fabs(den) < 1e-7f) continue; // no unique intersection
const V3 p = mul(add(add(mul(cross(c, e), P[fi].d),
mul(cross(e, a), P[i].d)),
mul(cross(a, c), P[j].d)), 1.0f / den);
bool inside = true;
for (int k = 0; k < n && inside; k++)
if (dot(plane_n(P[k]), p) - P[k].d > eps) inside = false;
if (!inside) continue;
bool dup = false;
for (const V3& q : out) if (len(sub(q, p)) < 1e-4f) { dup = true; break; }
if (!dup) out.push_back(p);
}
}
if (out.size() < 3) { out.clear(); return false; }
// Order around the face normal.
V3 ctr{0,0,0};
for (const V3& p : out) ctr = add(ctr, p);
ctr = mul(ctr, 1.0f / (float)out.size());
const V3 u = norm(std::fabs(fn.x) < 0.9f ? cross(fn, V3{1,0,0}) : cross(fn, V3{0,1,0}));
const V3 v = cross(fn, u);
std::sort(out.begin(), out.end(), [&](const V3& A, const V3& B) {
const V3 da = sub(A, ctr), db = sub(B, ctr);
return std::atan2(dot(da, v), dot(da, u)) < std::atan2(dot(db, v), dot(db, u));
});
return true;
}
void compute_bounds(CSG4Brush& b, float eps) {
b.lo = { 1e30f, 1e30f, 1e30f};
b.hi = {-1e30f, -1e30f, -1e30f};
std::vector<V3> w;
for (uint32_t fi = 0; fi < b.plane_count; fi++) {
if (!face_winding(b, fi, w, eps)) continue;
for (const V3& p : w) {
b.lo.x = std::min(b.lo.x, p.x); b.hi.x = std::max(b.hi.x, p.x);
b.lo.y = std::min(b.lo.y, p.y); b.hi.y = std::max(b.hi.y, p.y);
b.lo.z = std::min(b.lo.z, p.z); b.hi.z = std::max(b.hi.z, p.z);
}
}
b.bounds_valid = (b.lo.x <= b.hi.x);
}
void compute_bounds(std::vector<CSG4Brush>& brushes, float eps) {
for (auto& b : brushes) compute_bounds(b, eps);
}
void neighbours(const std::vector<CSG4Brush>& brushes, uint32_t index,
std::vector<uint32_t>& out, float eps) {
out.clear();
if (index >= brushes.size()) return;
const CSG4Brush& B = brushes[index];
for (uint32_t j = 0; j < (uint32_t)brushes.size(); j++) {
if (j == index) continue;
if (aabb_overlap(B, brushes[j], eps)) out.push_back(j);
}
}
float face_area(const CSG4Face& f) {
if (f.pts.size() < 3) return 0.0f;
V3 acc{0,0,0};
for (size_t i = 1; i + 1 < f.pts.size(); i++)
acc = add(acc, cross(sub(f.pts[i], f.pts[0]), sub(f.pts[i+1], f.pts[0])));
return 0.5f * len(acc);
}
// Clip every face of brush `index` against `nbr`, appending survivors to `out`.
// Shared by clip_all and clip_brush so the incremental path cannot drift from
// the full pass.
static void clip_one_brush(const std::vector<CSG4Brush>& brushes, uint32_t index,
const std::vector<uint32_t>& nbr,
std::vector<CSG4Face>& out, CSG4Stats* st) {
const CSG4Brush& B = brushes[index];
std::vector<V3> face;
for (uint32_t fi = 0; fi < B.plane_count; fi++) {
// INTERNAL faces clip but never draw. Skipped here, at emission, rather
// than by leaving the plane out of the brush — the plane is load-bearing
// geometry (it is what makes the piece the right solid, and what every
// OTHER brush gets clipped against); only its own face is suppressed.
// A brush with every plane internal is therefore a pure clipper.
if (B.plane_internal && B.plane_internal[fi]) continue;
if (!face_winding(B, fi, face)) continue;
CSG4Face raw;
raw.pts = face;
raw.brush_id = B.id;
raw.face_index = fi;
raw.proj = B.plane_proj ? B.plane_proj[fi] : 0u;
raw.material_id = B.material_id;
if (st) {
st->raw_faces++;
st->raw_tris += face_tri_count(raw);
st->raw_area += face_area(raw);
}
const V3 fn = plane_n(B.planes[fi]);
const float fd = B.planes[fi].d;
std::vector<std::vector<V3>> cur{face}, next;
for (uint32_t j : nbr) {
next.clear();
for (const std::vector<V3>& w : cur) {
bool gone = false;
clip_inside(w, fn, fd, brushes[j], index, j, next, gone);
}
cur.swap(next);
if (cur.empty()) break;
}
if (cur.empty()) {
if (st) st->removed++;
continue;
}
if (st) {
if (cur.size() > 1) st->fragmented++;
st->max_fragments = std::max(st->max_fragments, (uint32_t)cur.size());
}
for (std::vector<V3>& w : cur) {
if (w.size() < 3) continue;
CSG4Face f;
f.pts = std::move(w);
f.brush_id = B.id;
f.face_index = fi;
f.proj = raw.proj;
f.material_id = raw.material_id;
if (st) {
st->out_faces++;
st->out_tris += face_tri_count(f);
st->out_area += face_area(f);
}
out.push_back(std::move(f));
}
}
}
void clip_brush(const std::vector<CSG4Brush>& brushes, uint32_t index,
std::vector<CSG4Face>& out) {
if (index >= brushes.size()) return;
std::vector<uint32_t> nbr;
neighbours(brushes, index, nbr);
clip_one_brush(brushes, index, nbr, out, nullptr);
}
// All neighbour lists in ONE sweep instead of a scan per brush.
//
// neighbours() is a linear pass over every brush, and clip_all called it once per
// brush: 1190 brushes on START.MAP is ~1.4M AABB tests per rebuild, which is
// where the measured ms_clip ~35ms went. Sort by lo.x and sweep, keeping only
// brushes whose hi.x still reaches the cursor: the same O(N^2) worst case in
// theory, but the measured mean overlap is 6.9, so in practice it collapses to
// roughly N log N.
//
// Deliberately NOT an incremental "re-clip only what changed" cache, which is the
// other way to attack this. That needs face bookkeeping keyed per brush across
// rebuilds, and split pieces SHARE their parent's brush_id, so the obvious key is
// ambiguous. This is a pure speedup with no cross-rebuild state to get wrong, and
// it speeds up the import path too.
static void all_neighbours(const std::vector<CSG4Brush>& brushes,
std::vector<std::vector<uint32_t>>& out, float eps) {
const uint32_t n = (uint32_t)brushes.size();
out.assign(n, {});
std::vector<uint32_t> order(n);
for (uint32_t i = 0; i < n; i++) order[i] = i;
std::sort(order.begin(), order.end(), [&](uint32_t a, uint32_t b) {
return brushes[a].lo.x < brushes[b].lo.x;
});
std::vector<uint32_t> active;
for (uint32_t oi = 0; oi < n; oi++) {
const uint32_t i = order[oi];
const CSG4Brush& B = brushes[i];
// Drop anything that can no longer reach the sweep cursor.
for (size_t k = 0; k < active.size(); ) {
if (brushes[active[k]].hi.x + eps < B.lo.x) {
active[k] = active.back();
active.pop_back();
} else {
k++;
}
}
for (uint32_t j : active) {
if (aabb_overlap(B, brushes[j], eps)) {
out[i].push_back(j);
out[j].push_back(i);
}
}
active.push_back(i);
}
}
void clip_all(const std::vector<CSG4Brush>& brushes,
std::vector<CSG4Face>& out, CSG4Stats* stats) {
CSG4Stats local;
CSG4Stats* st = stats ? stats : &local;
*st = CSG4Stats();
std::vector<std::vector<uint32_t>> nbrs;
all_neighbours(brushes, nbrs, WINDING_EPS);
uint64_t overlap_total = 0;
for (uint32_t i = 0; i < (uint32_t)brushes.size(); i++) {
overlap_total += nbrs[i].size();
st->max_overlap = std::max(st->max_overlap, (uint32_t)nbrs[i].size());
clip_one_brush(brushes, i, nbrs[i], out, st);
}
if (!brushes.empty())
st->mean_overlap = (double)overlap_total / (double)brushes.size();
}
} // namespace dc_csg4