// ============================================================================
// CSG4 WINDING-CLIP POLYCOUNT — the baked level mesh, measured.
//
// tests/test_brush_polycount.cpp measures the RAW per-brush convex hulls: every
// face of every brush, including faces buried inside neighbours and faces shared
// with abutting brushes. That is the INPUT to a bake, not its output.
//
// This is the bake: Quake's own csg4 algorithm (hmap2/csg4.c CSGFaces), as
// specified in docs/csg-dc-meeting-point.md and hyper-games #1 item 4:
//
// brush.c CreateBrushFaces : face = plane clipped by the brush's sibling planes
// csg4.c CSGFaces : AABB-reject other brushes, then clip each face
// against the overlapping brush's planes
// (ClipInside/SplitFace), discarding the interior
// fragment. What remains = the exact visible skin.
//
// It is per-face half-space clipping, NOT a mesh boolean (the doc is explicit).
// Robustness in Quake comes from integer-grid snapping rather than exact
// predicates, and 99.4% of START.MAP sits on the 8-unit grid — that is the
// precondition that makes an epsilon-clip safe here.
//
// COPLANAR TIE-BREAK (csg4 handles this; a naive clip does not):
// - opposite-facing coplanar (two brushes abutting face-to-face) -> the shared
// region is interior to the union; BOTH faces lose it.
// - same-facing coplanar (two brushes flush on the same surface) -> keep it
// exactly once, lower brush index wins, else the two z-fight.
//
// Reports the number that decides the dense-junction subsystem: the FRAGMENTATION
// histogram. docs/level-mesh-architecture.md says exact brush-CSG "would explode
// into fragments or get numerically fragile" at dense junctions, which is why the
// voxel-model fallback exists — but the threshold has never been validated.
//
// Input: /tmp/startmap_brushes.bin from hyper-tps/scenes/test/oracle_dump.gd
// Build: g++ -O2 -std=c++17 -o /tmp/csg4_poly tests/test_csg4_polycount.cpp
// ============================================================================
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
struct V3 { float x,y,z; };
static inline V3 operator+(V3 a,V3 b){return{a.x+b.x,a.y+b.y,a.z+b.z};}
static inline V3 operator-(V3 a,V3 b){return{a.x-b.x,a.y-b.y,a.z-b.z};}
static inline V3 operator*(V3 a,float s){return{a.x*s,a.y*s,a.z*s};}
static inline float dot(V3 a,V3 b){return a.x*b.x+a.y*b.y+a.z*b.z;}
static inline V3 cross3(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};}
static inline float len3(V3 a){return std::sqrt(dot(a,a));}
static inline V3 norm3(V3 a){float l=len3(a);return l>1e-20f?a*(1.0f/l):a;}
struct Plane { V3 n; float d; unsigned proj; };
struct Brush { V3 center; float radius,strength; unsigned material;
std::vector<Plane> planes; V3 lo, hi; };
typedef std::vector<V3> Winding;
static const float ON_EPS = 1e-4f; // world units (~0.1 mm at this scale)
// ---------------------------------------------------------------------------
static bool load_dump(const char* path, std::vector<Brush>& out, float& ws) {
FILE* f=fopen(path,"rb"); if(!f){fprintf(stderr,"cannot open %s\n",path);return false;}
char m[4]; size_t r=fread(m,1,4,f); (void)r;
if(memcmp(m,"DCOR",4)!=0){fprintf(stderr,"bad magic\n");fclose(f);return false;}
unsigned ver; r=fread(&ver,4,1,f); r=fread(&ws,4,1,f);
float carve[6]; r=fread(carve,4,6,f);
unsigned n; r=fread(&n,4,1,f); out.reserve(n);
for(unsigned i=0;i<n;i++){
Brush b; float c[3]; r=fread(c,4,3,f); b.center={c[0],c[1],c[2]};
r=fread(&b.radius,4,1,f); r=fread(&b.strength,4,1,f); r=fread(&b.material,4,1,f);
unsigned pc; r=fread(&pc,4,1,f); b.planes.reserve(pc);
for(unsigned p=0;p<pc;p++){float v[4];unsigned pr;r=fread(v,4,4,f);r=fread(&pr,4,1,f);
b.planes.push_back({{v[0],v[1],v[2]},v[3],pr});}
out.push_back(std::move(b));
}
fclose(f); return true;
}
// ---------------------------------------------------------------------------
// brush.c CreateBrushFaces — face winding = plane clipped by sibling planes.
// Built from plane triples, then ordered around the face normal.
static Winding face_polygon(const Brush& b, int fi, float eps) {
const auto& P = b.planes; int n=(int)P.size(); Winding pts;
for (int i=0;i<n;i++){ if(i==fi) continue;
for (int j=i+1;j<n;j++){ if(j==fi) continue;
V3 a=P[fi].n,c=P[i].n,e=P[j].n;
float den=dot(a,cross3(c,e));
if (std::fabs(den)<1e-7f) continue;
V3 p=(cross3(c,e)*P[fi].d + cross3(e,a)*P[i].d + cross3(a,c)*P[j].d)*(1.0f/den);
bool ok=true;
for(int k=0;k<n&&ok;k++) if(dot(P[k].n,p)-P[k].d>eps) ok=false;
if(!ok) continue;
bool dup=false; for(const auto&q:pts) if(len3(q-p)<1e-4f){dup=true;break;}
if(!dup) pts.push_back(p);
}
}
if (pts.size()<3) return pts;
V3 ctr{0,0,0}; for(auto&p:pts) ctr=ctr+p; ctr=ctr*(1.0f/(float)pts.size());
V3 nrm=P[fi].n;
V3 u=norm3(std::fabs(nrm.x)<0.9f?cross3(nrm,V3{1,0,0}):cross3(nrm,V3{0,1,0}));
V3 v=cross3(nrm,u);
std::sort(pts.begin(),pts.end(),[&](const V3&A,const V3&B){
V3 da=A-ctr,db=B-ctr;
return std::atan2(dot(da,v),dot(da,u))<std::atan2(dot(db,v),dot(db,u));});
return pts;
}
// winding.c ClipWinding / SplitFace — split by plane into front (n.p-d > 0) and
// back (n.p-d < 0), inserting the crossing points on both.
static void split_winding(const Winding& w, V3 n, float d,
Winding& front, Winding& back) {
front.clear(); back.clear();
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]>ON_EPS) nf++; else if(dist[i]<-ON_EPS) nb++;
}
if(!nf){ back=w; return; }
if(!nb){ front=w; return; }
for(int i=0;i<cnt;i++){
const V3& p1=w[i];
if(dist[i]>ON_EPS) front.push_back(p1);
else if(dist[i]<-ON_EPS) back.push_back(p1);
else { front.push_back(p1); back.push_back(p1); continue; }
int j=(i+1)%cnt;
if((dist[i]>ON_EPS&&dist[j]<-ON_EPS)||(dist[i]<-ON_EPS&&dist[j]>ON_EPS)){
float t=dist[i]/(dist[i]-dist[j]);
V3 mid=p1+(w[j]-p1)*t;
front.push_back(mid); back.push_back(mid);
}
}
}
// csg4.c ClipInside — remove the part of `face` that lies inside brush B.
// Returns surviving fragments. If nothing was inside, returns the face intact
// (never fragment for free).
static void clip_inside(const Winding& face, V3 face_n, float face_d,
const Brush& B, int bi, int bj,
std::vector<Winding>& out, bool& fully_removed) {
fully_removed = false;
// Coplanar handling: a plane of B coplanar with the face is not a clipping
// plane — the OTHER planes define the 2D extent of the shared region.
std::vector<const Plane*> clip;
int coplanar = 0; // +1 same-facing, -1 opposite-facing
for (const auto& q : B.planes) {
float ndot = dot(q.n, face_n);
if (std::fabs(ndot) > 0.999f && std::fabs(q.d - face_d*(ndot>0?1.0f:-1.0f)) < 1e-3f) {
// coplanar with the face plane (d compared in the face's orientation)
coplanar = (ndot > 0) ? 1 : -1;
continue;
}
clip.push_back(&q);
}
if (coplanar == 1 && bi < bj) { out.push_back(face); return; } // we own it
// coplanar == 1 && bi > bj -> the other brush owns it, remove the overlap
// coplanar == -1 -> sandwiched, remove the overlap
// coplanar == 0 -> ordinary volumetric clip
std::vector<Winding> keep;
Winding cur = face, front, back;
for (const Plane* q : clip) {
split_winding(cur, q->n, q->d, front, back);
if (front.size() >= 3) keep.push_back(front);
if (back.size() < 3) { out.push_back(face); return; } // nothing inside
cur = back;
}
// `cur` is inside B -> discarded.
if (keep.empty()) { fully_removed = true; return; }
for (auto& k : keep) out.push_back(std::move(k));
}
static float poly_area(const Winding& p){
if(p.size()<3) return 0.0f;
V3 acc{0,0,0};
for(size_t i=1;i+1<p.size();i++) acc=acc+cross3(p[i]-p[0],p[i+1]-p[0]);
return 0.5f*len3(acc);
}
static bool aabb_overlap(const Brush&a,const Brush&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);
}
int main(int argc,char**argv){
const char* dump=(argc>1)?argv[1]:"/tmp/startmap_brushes.bin";
std::vector<Brush> bs; float ws=0;
if(!load_dump(dump,bs,ws)) return 1;
// tight-ish AABBs from the face windings
for (auto& b : bs) {
b.lo={1e30f,1e30f,1e30f}; b.hi={-1e30f,-1e30f,-1e30f};
for(int fi=0;fi<(int)b.planes.size();fi++){
Winding w=face_polygon(b,fi,1e-3f);
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);
}
}
}
long raw_faces=0, raw_tris=0;
long out_faces=0, out_tris=0, removed=0, split_faces=0;
double raw_area=0, out_area=0;
std::vector<int> frag_hist(33,0);
long overlap_total=0, overlap_max=0;
for (size_t bi=0; bi<bs.size(); bi++) {
const Brush& B = bs[bi];
// AABB-gated neighbour set (csg4 does this first)
std::vector<int> nbr;
for (size_t bj=0; bj<bs.size(); bj++)
if (bj!=bi && aabb_overlap(B,bs[bj],1e-3f)) nbr.push_back((int)bj);
overlap_total += (long)nbr.size();
overlap_max = std::max(overlap_max,(long)nbr.size());
for (int fi=0; fi<(int)B.planes.size(); fi++) {
Winding face = face_polygon(B,fi,1e-3f);
if (face.size()<3) continue;
raw_faces++; raw_tris += (long)face.size()-2; raw_area += poly_area(face);
std::vector<Winding> cur{face};
for (int bj : nbr) {
std::vector<Winding> next;
for (const Winding& w : cur) {
bool gone=false;
clip_inside(w, B.planes[fi].n, B.planes[fi].d,
bs[bj], (int)bi, bj, next, gone);
}
cur.swap(next);
if (cur.empty()) break;
}
if (cur.empty()) { removed++; frag_hist[0]++; continue; }
int nf=(int)cur.size();
if (nf>1) split_faces++;
frag_hist[std::min(nf,32)]++;
for (const Winding& w : cur) {
if (w.size()<3) continue;
out_faces++; out_tris += (long)w.size()-2; out_area += poly_area(w);
}
}
}
printf("CSG4 WINDING-CLIP POLYCOUNT — START.MAP\n");
printf("brushes=%zu world_scale=%.4f\n", bs.size(), ws);
printf("AABB-overlapping neighbours per brush: mean=%.1f max=%ld\n\n",
(double)overlap_total/(double)bs.size(), overlap_max);
printf(" RAW (per-brush convex hulls, no cross-brush clip)\n");
printf(" faces=%-7ld triangles=%-7ld area=%.1f m2\n", raw_faces, raw_tris, raw_area);
printf(" CSG4-CLIPPED (exact visible exterior skin)\n");
printf(" faces=%-7ld triangles=%-7ld area=%.1f m2\n", out_faces, out_tris, out_area);
printf(" faces fully removed (buried/shared) = %ld (%.1f%%)\n",
removed, 100.0*(double)removed/(double)raw_faces);
printf(" faces fragmented = %ld (%.1f%%)\n",
split_faces, 100.0*(double)split_faces/(double)raw_faces);
printf(" triangle delta vs RAW = %+ld (%.2fx)\n",
out_tris-raw_tris, (double)out_tris/(double)std::max(1L,raw_tris));
printf(" surface area removed = %.1f m2 (%.1f%%)\n",
raw_area-out_area, 100.0*(raw_area-out_area)/std::max(1e-6,raw_area));
printf("\n FRAGMENTATION HISTOGRAM (pieces a face was cut into)\n");
printf(" 0 (removed) = %d\n", frag_hist[0]);
for (int i=1;i<33;i++) if (frag_hist[i])
printf(" %-2d %-9s = %d\n", i, i==32?"(>=32)":"", frag_hist[i]);
return 0;
}