#ifndef DC_CSG4_H
#define DC_CSG4_H
// ---------------------------------------------------------------------------
// csg4 — exact visible-skin extraction from a set of convex brushes.
//
// Port of Quake's own compiler (hmap2/{brush,csg4,winding}.c), specified in
// docs/csg-dc-meeting-point.md and docs/level-mesh-implementation.md §6.
// It is PER-FACE HALF-SPACE CLIPPING, not a mesh boolean:
//
// 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, discarding
// the interior fragment. What remains is the exact
// visible exterior skin of the union.
//
// Engine-free by design (libdc/ rule) so it is testable from a bare main().
// The reference oracle is tests/test_csg4_polycount.cpp; the gate that this port
// reproduces it is tests/test_csg4_gate.cpp.
//
// ACCEPTANCE (measured on the real 1164-brush START.MAP dump):
// 6487 faces · 12747 triangles · 32101 m² · 2593 removed · 837 fragmented
//
// ROBUSTNESS: Quake relies on integer-grid snapping rather than exact
// predicates, and 99.4% of START.MAP sits on the 8-unit grid (91.7%
// axis-aligned). That is the precondition making an epsilon clip safe here.
// Do not reach for exact arithmetic before a real map demands it.
// ---------------------------------------------------------------------------
#include <cstdint>
#include <vector>
#include "dc_edit.h" // ConvexPlane (the type the Quake importer already emits)
struct CSG4Vec3 { float x, y, z; };
// One brush, as csg4 sees it. Non-owning views — the caller owns the storage.
struct CSG4Brush {
const ConvexPlane* planes = nullptr;
uint32_t plane_count = 0;
const uint32_t* plane_proj = nullptr; // parallel to planes; may be null
// Parallel to planes; may be null (= no face is internal). 1 marks a face
// that CLIPS like any other but is never EMITTED, because it is interior to
// the union. dc_brush_split produces these: peeling a brush around a carve's
// AABB creates cut faces with solid on both sides, and csg4 cannot cancel
// them the usual way because the thing on the other side is a voxel pocket,
// not a brush. A brush whose planes are ALL internal is a pure clipper —
// which is how the pocket's own volume keeps removing its neighbours' hidden
// faces after the brush it came from has been replaced by pieces.
const uint8_t* plane_internal = nullptr;
// A solid that exists ONLY to clip: no faces emitted, and NO COLLIDER. The
// carved remainder (brush AND carve-aabb) is one — its volume must keep
// removing neighbours' hidden faces, but giving it a convex collider would
// fill the hole the player just carved with invisible solid. That is not
// hypothetical: it shipped in 0.825.0 and was reported as "the collision
// trimesh isn't being recalced".
bool clip_only = false;
uint32_t material_id = 0;
uint32_t id = 0; // stable identity, carried onto faces
bool sky = false; // clips like any brush; no collider (see DCBrush::sky)
// AIR THE LEVEL OWNS — the headroom over a flight of stairs, the bore of an
// archway. csg4 NEVER SEES ONE: DCBrushStore::csg4_view drops them, because a
// clearance solid encloses the geometry it belongs to and clipping against it
// would eat the very faces it exists to keep reachable. It reaches only
// dc_level_shell, via shell_view, where it blocks the exterior flood so the
// sealed volume extends through it and the terrain is subtracted from it.
//
// Consequently this field is INERT in every other consumer of CSG4Brush, and
// that is deliberate: the transport type is shared, the meaning is not.
bool clearance = false;
// Cached bounds (dc_csg4::compute_bounds). Built from the FACE WINDINGS, not
// the bounding sphere — a sphere-derived AABB is far too loose for the gate
// to be meaningful (measured mean overlap would inflate well past 6.9).
CSG4Vec3 lo{0,0,0}, hi{0,0,0};
bool bounds_valid = false;
};
// One surviving face fragment. Provenance is carried so UVs and material come
// from the brush's own plane_proj/material_id — never from a per-vertex label.
struct CSG4Face {
std::vector<CSG4Vec3> pts; // convex, ordered around the face normal
uint32_t brush_id = 0;
uint32_t face_index = 0; // index into that brush's planes[]
uint32_t proj = 0; // plane_proj[face_index], 0 if none
uint32_t material_id = 0;
};
struct CSG4Stats {
uint32_t raw_faces = 0, out_faces = 0;
uint32_t raw_tris = 0, out_tris = 0;
uint32_t removed = 0; // faces fully buried/shared
uint32_t fragmented = 0; // faces cut into >1 piece
uint32_t max_fragments = 0;
double raw_area = 0.0, out_area = 0.0;
double mean_overlap = 0.0; // AABB-overlapping neighbours per brush
uint32_t max_overlap = 0;
};
namespace dc_csg4 {
// Default epsilons. ON_EPS is in world units (~0.1 mm at world_scale 0.028).
constexpr float ON_EPS = 1e-4f;
constexpr float WINDING_EPS = 1e-3f; // slack when testing a point against a plane
constexpr float COPLANAR_N = 0.999f; // |dot| above this = parallel normals
constexpr float COPLANAR_D = 1e-3f; // offset agreement for coplanar
// Build brush `b`'s face `fi` as a convex polygon (CreateBrushFaces).
// Returns false if the face is degenerate (<3 points).
bool face_winding(const CSG4Brush& b, uint32_t fi, std::vector<CSG4Vec3>& out,
float eps = WINDING_EPS);
// Fill b.lo/b.hi from the face windings and set bounds_valid.
void compute_bounds(CSG4Brush& b, float eps = WINDING_EPS);
void compute_bounds(std::vector<CSG4Brush>& brushes, float eps = WINDING_EPS);
// Full pass: clip every face of every brush against its AABB-overlapping
// neighbours. `stats` may be null.
void clip_all(const std::vector<CSG4Brush>& brushes,
std::vector<CSG4Face>& out, CSG4Stats* stats = nullptr);
// Incremental: re-clip ONE brush only. This is the interactive-edit path
// (docs §6.3) — bounded by the measured neighbour count (mean 6.9, max 53 on
// START.MAP), which is what makes a brush edit local rather than a rebuild.
// Appends to `out`; does not clear it.
void clip_brush(const std::vector<CSG4Brush>& brushes, uint32_t index,
std::vector<CSG4Face>& out);
// Indices of brushes whose AABB overlaps brush `index` (excluding itself).
void neighbours(const std::vector<CSG4Brush>& brushes, uint32_t index,
std::vector<uint32_t>& out, float eps = WINDING_EPS);
// Fan-triangulate a face: an n-gon costs n-2 triangles.
inline uint32_t face_tri_count(const CSG4Face& f) {
return f.pts.size() >= 3 ? (uint32_t)f.pts.size() - 2 : 0u;
}
float face_area(const CSG4Face& f);
} // namespace dc_csg4
#endif // DC_CSG4_H