#ifndef DC_EDIT_H
#define DC_EDIT_H
// Terrain edit list: CSG-style add/subtract operations (sphere or box).
// Thread-safe — workers read a snapshot, main thread writes.
#include <vector>
#include <cmath>
#include <mutex>
#include <algorithm>
#include <memory>
#include <limits>
#include "dc_generator.h" // base class for mesh SDF evaluate
// A single outward half-space plane of a convex brush: inside = (n·p <= d).
struct ConvexPlane { float nx, ny, nz, d; };
struct TerrainEdit {
enum Shape : uint8_t { SPHERE, BOX, MESH, CONVEX };
// CSG operator. Currently read only for SPHERE (box/mesh are always hard
// SDF min/max by strength sign). OP_SMOOTH = the legacy metaball blend
// (d += strength·t²). OP_HARD = hard SDF min/max like box: a sharp sphere
// union (strength>0) / difference (strength<0). Default preserves the old
// sphere behavior so existing callers are unchanged.
enum CsgOp : uint8_t { OP_SMOOTH = 0, OP_HARD = 1 };
Shape shape = SPHERE;
CsgOp op = OP_SMOOTH; // CSG operator (see CsgOp; sphere only for now)
float x, y, z; // world position (center)
float radius; // sphere radius OR unused for box
float half_ext[3]; // box half-extents (only used when shape == BOX)
float strength; // positive = add material, negative = remove
uint32_t material_id = 0; // route ②: index into the terrain material/texture-plane
// table (0 = untextured → triplanar; >0 = Quake face texture,
// reprojected planar UV). See docs/quake-import-texturing.md.
float scale = 1.0f; // mesh scale (only used when shape == MESH)
std::shared_ptr<DCGenerator> mesh_sdf; // mesh SDF via base class (only when shape == MESH)
std::vector<ConvexPlane> planes; // convex brush half-spaces (only when shape == CONVEX)
std::vector<uint32_t> plane_proj; // per-face projection index into the shader's
// projection table (1-based; 0 = none). Parallel to
// planes; Stage-2 per-face texturing. Empty = no proj.
// MAP-AUTHORED LANDSCAPE, not a player edit. clear_edits() preserves these.
//
// There are two journals over one edit list. The player journal is owned by
// the game (hyper-tps: world:terrain:edit:*, replayed per room), and dropping
// it on a map change is correct. Landscape is authored by the MAP itself — the
// §5a.2 level shell subtract is one 563k-triangle MESH edit stamped during
// import — and nothing outside the map may drop it.
//
// Without this, entering map_dc_world stamped the shell and then TerrainEditManager
// .reenter_map() (on GameState.map_changing, which fires AFTER the map's deferred
// import) called clear_edits() on the terrain it had just found, wiping the shell
// and rebuilding the octree from a field with no subtract. The level's rooms
// filled with terrain while debug_sdf_at at those same points still read air —
// because the probe walks edit_list_ and the wipe had already happened by then.
bool persistent = false;
};
// ONE definition of the mesh cull radius, because callers need it too — the
// stamp registers an LOD focus point and requeues chunks with the same number.
// Two computations of it is exactly how the shipped code drifted: dc_terrain.cpp
// had its own _mesh_bounding_radius and the list took whatever it was handed.
//
// The mesh is evaluated in LOCAL coordinates about the stamp point, so the
// furthest corner from the stamp point is max(|lo|,|hi|) per axis. The +2 is the
// margin the shipped helper carried.
//
// AN UNBOUNDED GENERATOR IS NEVER CULLED: get_bounds() false means there is no
// basis for a cull volume, and inventing a finite one is the failure this exists
// to remove. Conservative costs chunk evaluations; wrong costs geometry.
inline float mesh_bounding_radius(const std::shared_ptr<DCGenerator>& sdf, float scale) {
float bmin[3], bmax[3];
if (!sdf || !sdf->get_bounds(bmin, bmax)) return std::numeric_limits<float>::max();
const float ex = std::max(std::fabs(bmin[0]), std::fabs(bmax[0])) * scale;
const float ey = std::max(std::fabs(bmin[1]), std::fabs(bmax[1])) * scale;
const float ez = std::max(std::fabs(bmin[2]), std::fabs(bmax[2])) * scale;
return std::sqrt(ex*ex + ey*ey + ez*ez) + 2.0f;
}
// Bounding radius of a convex polytope about an arbitrary centre, from its
// half-spaces. Enumerates the polytope's vertices (plane triples that satisfy
// every other plane) and takes the furthest. Returns FLT_MAX when the set has no
// enumerable vertex — unbounded or degenerate, and so not safely cullable.
inline float convex_bounding_radius(const std::vector<ConvexPlane>& planes,
float cx, float cy, float cz) {
const size_t n = planes.size();
if (n < 4) return std::numeric_limits<float>::max(); // cannot bound a solid
const float EPS = 1e-4f;
float best = -1.0f;
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++) {
const ConvexPlane &A = planes[i], &B = planes[j], &C = planes[k];
// Cramer's rule on the 3x3 of normals.
const float det =
A.nx * (B.ny * C.nz - B.nz * C.ny) -
A.ny * (B.nx * C.nz - B.nz * C.nx) +
A.nz * (B.nx * C.ny - B.ny * C.nx);
if (std::fabs(det) < 1e-9f) continue; // parallel / coincident
const float px = ( A.d * (B.ny * C.nz - B.nz * C.ny)
- A.ny * (B.d * C.nz - B.nz * C.d )
+ A.nz * (B.d * C.ny - B.ny * C.d ) ) / det;
const float py = ( A.nx * (B.d * C.nz - B.nz * C.d )
- A.d * (B.nx * C.nz - B.nz * C.nx)
+ A.nz * (B.nx * C.d - B.d * C.nx) ) / det;
const float pz = ( A.nx * (B.ny * C.d - B.d * C.ny)
- A.ny * (B.nx * C.d - B.d * C.nx)
+ A.d * (B.nx * C.ny - B.ny * C.nx) ) / det;
bool inside = true;
for (size_t m = 0; m < n && inside; m++) {
if (planes[m].nx * px + planes[m].ny * py + planes[m].nz * pz - planes[m].d > EPS)
inside = false;
}
if (!inside) continue;
const float dx = px - cx, dy = py - cy, dz = pz - cz;
const float d = std::sqrt(dx*dx + dy*dy + dz*dz);
if (d > best) best = d;
}
if (best < 0.0f) return std::numeric_limits<float>::max();
return best * 1.001f + 1e-4f; // epsilon, never inward
}
class DCEditList {
public:
void add_sphere(float x, float y, float z, float radius, float strength,
TerrainEdit::CsgOp op = TerrainEdit::OP_SMOOTH,
uint32_t material_id = 0) {
std::lock_guard<std::mutex> lock(mutex_);
TerrainEdit e;
e.shape = TerrainEdit::SPHERE;
e.op = op;
e.x = x; e.y = y; e.z = z;
e.radius = radius;
e.strength = strength;
e.material_id = material_id;
edits_.push_back(e);
}
void add_box(float x, float y, float z,
float hx, float hy, float hz, float strength,
uint32_t material_id = 0, bool persistent = false) {
std::lock_guard<std::mutex> lock(mutex_);
TerrainEdit e;
e.shape = TerrainEdit::BOX;
e.x = x; e.y = y; e.z = z;
e.half_ext[0] = hx; e.half_ext[1] = hy; e.half_ext[2] = hz;
e.radius = std::sqrt(hx*hx + hy*hy + hz*hz); // exact bounding sphere (corner distance)
e.strength = strength;
e.material_id = material_id;
e.persistent = persistent;
edits_.push_back(e);
}
// THE RADIUS IS NOT THE CALLER'S TO PASS — hyper-games #42 P2.
//
// It used to be a parameter, and two call sites computed it the same wrong
// way: half the AABB diagonal, which is the radius of a sphere about the BOX
// CENTRE, while the cull tests about the STAMP POINT. Those coincide only for
// vertices symmetric about their bounds, and the level shell is the opposite
// (hyper-games #41 §3). A caller that cannot pass a radius cannot pass a wrong
// one, so it is computed here from the generator's own bounds.
//
// The mesh is evaluated in LOCAL coordinates about the stamp point, so the
// furthest corner from the stamp point is max(|lo|,|hi|) per axis. The +2 is
// the margin the shipped helper carried.
//
// AN UNBOUNDED GENERATOR IS NEVER CULLED. get_bounds() returning false means
// there is no basis for a cull volume at all, and a made-up finite radius is
// exactly the failure this change exists to remove. Conservative costs chunk
// evaluations; wrong costs geometry.
void add_mesh(float x, float y, float z, float scale, float strength,
std::shared_ptr<DCGenerator> mesh_sdf,
uint32_t material_id = 0, bool persistent = false) {
std::lock_guard<std::mutex> lock(mutex_);
TerrainEdit e;
e.shape = TerrainEdit::MESH;
e.x = x; e.y = y; e.z = z;
e.scale = scale;
e.strength = strength;
e.mesh_sdf = mesh_sdf;
e.material_id = material_id;
e.persistent = persistent;
e.radius = mesh_bounding_radius(mesh_sdf, scale);
edits_.push_back(e);
}
// Convex brush = intersection of outward half-space planes (a Quake brush).
// center/bounding_radius are for chunk culling only; the SDF is the plane set.
// Radius computed from the PLANE SET, for the same reason as add_mesh: an
// inscribed-sphere radius looks plausible and misses all eight corners of a
// cube (test_cull_support.cpp measures 3512 escaping points).
//
// Vertices are the plane triples that intersect inside every other plane —
// the polytope's own corners. A brush is 6-8 planes, so this is tens to a few
// hundred 3x3 solves once at edit time, not per sample. A plane set with no
// enumerable vertex is unbounded or degenerate and is never culled.
void add_convex(float cx, float cy, float cz,
const std::vector<ConvexPlane>& planes, float strength,
uint32_t material_id = 0,
const std::vector<uint32_t>& plane_proj = {}) {
std::lock_guard<std::mutex> lock(mutex_);
TerrainEdit e;
e.shape = TerrainEdit::CONVEX;
e.x = cx; e.y = cy; e.z = cz;
e.radius = convex_bounding_radius(planes, cx, cy, cz);
e.strength = strength;
e.material_id = material_id;
e.planes = planes;
e.plane_proj = plane_proj; // parallel to planes (Stage-2 per-face texturing); may be empty
edits_.push_back(e);
}
// Legacy API — sphere edit
void add_edit(float x, float y, float z, float radius, float strength) {
add_sphere(x, y, z, radius, strength);
}
// Translate one edit in place (for interactive brush move). Convex brushes shift
// every half-space plane by n·delta; box/sphere/mesh shift the centre.
bool move_edit(int idx, float dx, float dy, float dz) {
if (idx < 0 || idx >= (int)edits_.size()) return false;
TerrainEdit& e = edits_[idx];
e.x += dx; e.y += dy; e.z += dz;
if (e.shape == TerrainEdit::CONVEX) {
for (auto& pl : e.planes) pl.d += pl.nx * dx + pl.ny * dy + pl.nz * dz;
}
return true;
}
bool remove_edit(int idx) {
std::lock_guard<std::mutex> lock(mutex_);
if (idx < 0 || idx >= (int)edits_.size()) return false;
edits_.erase(edits_.begin() + idx);
return true;
}
// Drop the PLAYER journal. Map-authored landscape (persistent) survives —
// see TerrainEdit::persistent. Returns how many were kept, so the caller can
// say so out loud rather than leaving a silent partial clear.
int clear() {
std::lock_guard<std::mutex> lock(mutex_);
std::vector<TerrainEdit> kept;
for (const auto& e : edits_) {
if (e.persistent) kept.push_back(e);
}
int n = static_cast<int>(kept.size());
edits_ = std::move(kept);
return n;
}
// Drop EVERYTHING including landscape. For teardown/tests only — a map change
// must use clear(), or it wipes the level shell it just stamped.
void clear_all() {
std::lock_guard<std::mutex> lock(mutex_);
edits_.clear();
}
// Drop ONLY the landscape, keeping the player journal. The inverse of clear().
//
// This is what makes a landscape stamp REPLACEABLE rather than additive, which
// re-deriving the level shell requires: stamping a second one would leave two
// overlapping mesh SDFs in the same chunks, and only the FIRST gets its BVH
// uploaded (dc_compute.cpp upload_edits) — the second is still packed as a
// type 4/5 edit and evaluated against the wrong tree, producing geometry that
// belongs to neither. Clear, then stamp.
int clear_landscape() {
std::lock_guard<std::mutex> lock(mutex_);
std::vector<TerrainEdit> kept;
for (const auto& e : edits_) {
if (!e.persistent) kept.push_back(e);
}
int dropped = static_cast<int>(edits_.size() - kept.size());
edits_ = std::move(kept);
return dropped;
}
int count() const {
std::lock_guard<std::mutex> lock(mutex_);
return static_cast<int>(edits_.size());
}
std::vector<TerrainEdit> snapshot() const {
std::lock_guard<std::mutex> lock(mutex_);
return edits_;
}
// Apply all edits to a density value at world position.
static float apply(const std::vector<TerrainEdit>& edits,
float wx, float wy, float wz, float base_density) {
float result = base_density;
for (const auto& e : edits) {
if (e.shape == TerrainEdit::SPHERE) {
float dx = wx - e.x;
float dy = wy - e.y;
float dz = wz - e.z;
float dist_sq = dx*dx + dy*dy + dz*dz;
float r_sq = e.radius * e.radius;
if (dist_sq < r_sq) {
if (e.op == TerrainEdit::OP_HARD) {
// Hard sphere CSG: SDF = dist - radius (negative inside,
// positive outside — same convention as box_sdf below).
// Union (strength>0) / difference (strength<0), matching box.
float sphere_sdf = std::sqrt(dist_sq) - e.radius;
if (e.strength < 0.0f) {
result = std::min(result, sphere_sdf);
} else {
result = std::max(result, -sphere_sdf);
}
} else {
// Smooth metaball blend (legacy default)
float t = 1.0f - dist_sq / r_sq;
result += e.strength * t * t;
}
}
} else if (e.shape == TerrainEdit::BOX) {
float dx = std::fabs(wx - e.x) - e.half_ext[0];
float dy = std::fabs(wy - e.y) - e.half_ext[1];
float dz = std::fabs(wz - e.z) - e.half_ext[2];
// Quick reject: if outside the box, SDF is positive.
// Subtraction min(result, +sdf) can't change negative result.
// Addition max(result, -sdf) can't change positive result.
float max_comp = std::max({dx, dy, dz});
if (max_comp > 0.0f) {
if (e.strength < 0.0f && result <= 0.0f) continue;
if (e.strength > 0.0f && result >= 0.0f) continue;
}
float outside = std::sqrt(
std::max(dx, 0.0f) * std::max(dx, 0.0f) +
std::max(dy, 0.0f) * std::max(dy, 0.0f) +
std::max(dz, 0.0f) * std::max(dz, 0.0f));
float inside = std::min(max_comp, 0.0f);
float box_sdf = outside + inside;
if (e.strength < 0.0f) {
result = std::min(result, box_sdf);
} else {
result = std::max(result, -box_sdf);
}
} else if (e.shape == TerrainEdit::MESH && e.mesh_sdf) {
// Mesh SDF: evaluate at local coordinates (centered + scaled)
// Quick bounding sphere reject
float mdx = wx - e.x, mdy = wy - e.y, mdz = wz - e.z;
if (mdx*mdx + mdy*mdy + mdz*mdz > e.radius * e.radius) continue;
float lx = mdx / e.scale;
float ly = mdy / e.scale;
float lz = mdz / e.scale;
float mesh_d = e.mesh_sdf->evaluate(lx, ly, lz, 0.0f);
// mesh_d: positive = inside mesh, negative = outside
// For CSG: use same convention as box
float mesh_sdf = -mesh_d; // negative inside, positive outside
if (e.strength < 0.0f) {
result = std::min(result, mesh_sdf);
} else {
result = std::max(result, -mesh_sdf);
}
} else if (e.shape == TerrainEdit::CONVEX) {
// Convex brush = intersection of half-spaces:
// f(p) = max_i (n_i·p - d_i) (negative inside, positive outside)
// Same sign convention as box_sdf → mirror the box CSG + quick-reject
// EXACTLY (the box path is proven in-game; don't re-reason solid/air).
float f = -1e30f;
for (const auto& pl : e.planes) {
float dp = pl.nx * wx + pl.ny * wy + pl.nz * wz - pl.d;
if (dp > f) f = dp;
}
if (f > 0.0f) { // clearly outside — mirror box's outside quick-reject
if (e.strength < 0.0f && result <= 0.0f) continue;
if (e.strength > 0.0f && result >= 0.0f) continue;
}
if (e.strength < 0.0f) {
result = std::min(result, f);
} else {
result = std::max(result, -f);
}
}
}
return result;
}
private:
std::vector<TerrainEdit> edits_;
mutable std::mutex mutex_;
};
#endif // DC_EDIT_H