#ifndef DC_BRUSH_HULL_H
#define DC_BRUSH_HULL_H
// ============================================================================
// THE CONVEX HULL OF A POINT SET, AS A PLANE SET.
//
// Everything else in this store works the other way round — a brush IS a plane set
// and its vertices are derived — and that direction is what makes it exact. This is
// the one operation that has to go backwards, because it is the only way a single
// corner moves without dragging its neighbours with it (see tests/test_brush_hull.cpp
// for why the plane path cannot do that, and why it is not a bug in the editor).
//
// BRUTE FORCE OVER TRIPLES, deliberately. For every three points, take the plane
// through them and ask whether every other point lies on one side; if so it is a
// hull face. A brush has 8-30 vertices, so this is a few thousand operations, once,
// on a keypress — and against that, quickhull buys speed nobody needs in exchange
// for the merge and degeneracy cases it is famous for getting subtly wrong. This
// cannot get them wrong: it only ever asks a question with a yes or no answer.
//
// DETERMINISM IS A REQUIREMENT, NOT A NICETY. Two peers replaying the same journal
// record must build the same solid, or the level forks. So the triples are visited
// in index order, planes are appended in the order they are first seen, and the
// dedup keeps the FIRST occurrence — no sorting by anything derived from floating
// point, no hashing, nothing that could order differently on another machine.
// ============================================================================
#include "dc_edit.h" // ConvexPlane
#include "dc_csg4.h" // CSG4Vec3
#include <vector>
#include <cmath>
namespace dc_hull {
// How far off a plane a point may be and still count as ON it. The brush lattice is
// Quake units scaled by 0.028, so the smallest thing anyone can author is ~0.028;
// 1e-4 is far below that and far above float noise on coordinates of a few hundred.
inline constexpr float ON_PLANE = 1e-4f;
// Two planes are the same face when they point the same way and sit at the same
// offset. Normals are unit, so the dot is a cosine: 0.9999 is about 0.8 degrees.
inline constexpr float SAME_NORMAL = 0.9999f;
inline constexpr float SAME_OFFSET = 1e-3f;
inline bool same_plane(const ConvexPlane& a, const ConvexPlane& b) {
return (a.nx * b.nx + a.ny * b.ny + a.nz * b.nz) > SAME_NORMAL &&
std::fabs(a.d - b.d) < SAME_OFFSET;
}
// The hull of `pts`, as outward-facing half-spaces (n.x <= d inside), which is the
// convention every other plane in this store uses.
//
// Returns false — and leaves `out` empty — when the points do not enclose a volume:
// fewer than four, or all coplanar. Both are real answers rather than errors; a drag
// that flattens a brush has to be refused, not clamped into something nobody asked
// for.
inline bool hull_planes(const std::vector<CSG4Vec3>& pts,
std::vector<ConvexPlane>& out) {
out.clear();
const size_t n = pts.size();
if (n < 4) return false;
for (size_t i = 0; i < n; i++) {
for (size_t j = i + 1; j < n; j++) {
for (size_t k = j + 1; k < n; k++) {
// The plane through three points, if they are not in line.
const float ax = pts[j].x - pts[i].x;
const float ay = pts[j].y - pts[i].y;
const float az = pts[j].z - pts[i].z;
const float bx = pts[k].x - pts[i].x;
const float by = pts[k].y - pts[i].y;
const float bz = pts[k].z - pts[i].z;
float nx = ay * bz - az * by;
float ny = az * bx - ax * bz;
float nz = ax * by - ay * bx;
const float len = std::sqrt(nx * nx + ny * ny + nz * nz);
if (len < 1e-9f) continue; // colinear: no plane
nx /= len; ny /= len; nz /= len;
float d = nx * pts[i].x + ny * pts[i].y + nz * pts[i].z;
// A hull face has every OTHER point strictly on one side. If they
// are all on the far side, the same plane flipped is the hull face —
// which is what orients the result outward without a centroid, and
// therefore without a tie to break when the centroid sits on it.
bool any_above = false, any_below = false;
for (size_t m = 0; m < n; m++) {
const float s = nx * pts[m].x + ny * pts[m].y + nz * pts[m].z - d;
if (s > ON_PLANE) any_above = true;
else if (s < -ON_PLANE) any_below = true;
if (any_above && any_below) break; // interior plane
}
if (any_above && any_below) continue;
if (any_above) { nx = -nx; ny = -ny; nz = -nz; d = -d; }
const ConvexPlane p{nx, ny, nz, d};
bool seen = false;
for (const ConvexPlane& q : out)
if (same_plane(p, q)) { seen = true; break; }
if (!seen) out.push_back(p);
}
}
}
// Four planes is a tetrahedron — the least that can enclose anything.
if (out.size() < 4) { out.clear(); return false; }
return true;
}
} // namespace dc_hull
#endif // DC_BRUSH_HULL_H