// ============================================================================
// BRUSH POLYCOUNT ORACLE — "a Quake level should not need millions of polygons."
//
// Measures the EXACT polygon count of START.MAP's brush geometry and compares it
// with what DC currently emits (5-17M triangles, hyper-games issue #5), so the
// meshing-architecture decision is made on a number instead of an impression.
//
// Method (this is what qbsp / func_godot do):
// Every convex brush face is the plane clipped by that brush's OTHER
// half-spaces -> a convex polygon. Build it by intersecting plane triples,
// keeping points inside all half-spaces, and ordering them around the face
// normal. Fan-triangulate: an n-gon costs n-2 triangles.
//
// Three counts are reported:
// RAW every face of every brush (what a naive brush->mesh emits)
// VISIBLE faces not fully buried inside another brush (cheap HSR, the
// same >1-voxel burial test bake_planeset.glsl:127 uses)
// DC ACTUAL for reference, what the voxel mesher produces at a given voxel
// size, estimated from surface area / voxel^2 (DC emits ~2 tris
// per surface cell, one vertex per cell).
//
// Input: /tmp/startmap_brushes.bin from hyper-tps/scenes/test/oracle_dump.gd
// Build: g++ -O2 -std=c++17 -o /tmp/brush_poly tests/test_brush_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; };
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;
}
static float brush_f(V3 p, const Brush& b){
float m=-1e30f; for(const auto&q:b.planes) m=std::max(m,dot(q.n,p)-q.d); return m;
}
// Convex face polygon of plane `fi` of brush b: all triple-plane intersections
// that satisfy every half-space, deduped and ordered around the normal.
static std::vector<V3> face_polygon(const Brush& b, int fi, float eps) {
const auto& P = b.planes;
int n = (int)P.size();
std::vector<V3> 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;
// order around the face normal
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;
}
static float poly_area(const std::vector<V3>& 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);
}
int main(int argc, char** argv) {
float vs = 0.224f;
if (argc > 1) vs = (float)atof(argv[1]);
const char* dump = (argc > 2) ? argv[2] : "/tmp/startmap_brushes.bin";
std::vector<Brush> bs; float ws = 0;
if (!load_dump(dump, bs, ws)) return 1;
long raw_faces=0, raw_tris=0, degenerate=0;
long vis_faces=0, vis_tris=0;
double raw_area=0, vis_area=0;
for (size_t bi = 0; bi < bs.size(); bi++) {
const Brush& B = bs[bi];
for (int fi = 0; fi < (int)B.planes.size(); fi++) {
auto poly = face_polygon(B, fi, 1e-3f);
if (poly.size() < 3) { degenerate++; continue; }
long t = (long)poly.size() - 2;
raw_faces++; raw_tris += t;
float a = poly_area(poly);
raw_area += a;
// cheap HSR: is the face fully buried inside some OTHER brush?
// Same >1-voxel burial test as bake_planeset.glsl:127.
bool buried = false;
for (size_t oj = 0; oj < bs.size() && !buried; oj++) {
if (oj == bi) continue;
const Brush& O = bs[oj];
bool all_in = true;
for (const auto& p : poly) {
V3 dc = p - O.center;
if (dot(dc,dc) > O.radius*O.radius) { all_in = false; break; }
if (brush_f(p, O) > -vs) { all_in = false; break; }
}
if (all_in) buried = true;
}
if (!buried) { vis_faces++; vis_tris += t; vis_area += a; }
}
}
printf("BRUSH POLYCOUNT ORACLE — START.MAP\n");
printf("brushes=%zu world_scale=%.4f voxel=%.3f\n\n", bs.size(), ws, vs);
printf(" RAW brush mesh (every face of every brush)\n");
printf(" faces=%ld triangles=%ld surface area=%.1f m2 (degenerate faces skipped=%ld)\n",
raw_faces, raw_tris, raw_area, degenerate);
printf(" VISIBLE (drop faces fully buried >1 voxel inside another brush)\n");
printf(" faces=%ld triangles=%ld surface area=%.1f m2\n", vis_faces, vis_tris, vis_area);
// DC emits ~1 vertex per surface cell, ~2 triangles per surface cell.
double cells = vis_area / (double)(vs*vs);
printf("\n DUAL CONTOURING at voxel=%.3f (est. from visible surface area)\n", vs);
printf(" surface cells ~= area/voxel^2 = %.0f triangles ~= 2*cells = %.0f\n", cells, cells*2.0);
printf(" ratio vs exact brush mesh: %.0fx\n", (cells*2.0) / std::max(1L, vis_tris));
printf("\n At other LODs:\n");
for (float v : {0.112f, 0.224f, 0.448f, 0.896f}) {
double c = vis_area/(double)(v*v);
printf(" voxel=%.3f -> ~%.0f tris (%.0fx exact)\n", v, c*2.0, (c*2.0)/std::max(1L,vis_tris));
}
return 0;
}