#ifndef DC_PICK_H
#define DC_PICK_H
// ---------------------------------------------------------------------------
// dc_pick — resolve a ray to (brush, face). ENGINE-FREE.
//
// hyper-games #22 §5 item 3. Picking was engine-coupled: pick_face needs a brush
// id, and the only way to obtain one was get_brush_id_from_shape(), which takes
// the index of a Godot collision shape. So the editor's most basic query —
// "what am I pointing at" — required the physics server to have been fed, stepped
// and queried. blender-bridge has no physics server, which made it a blocker for
// a second consumer rather than a convenience.
//
// It never needed one. A brush IS an intersection of half-spaces, so the query is
// the textbook convex slab clip against its own plane set:
//
// for each plane (n, d), with the interior at n.p <= d:
// denom = n.dir, t = (d - n.o) / denom
// denom < 0 -> the ray is ENTERING that half-space -> t_enter = max(t_enter, t)
// denom > 0 -> it is LEAVING -> t_exit = min(t_exit, t)
// denom == 0 -> parallel: a miss iff the origin is already outside
// hit iff t_enter <= t_exit and t_exit >= 0
//
// The face is the plane that produced t_enter — the last one crossed on the way
// in. Exact, and identical on a machine with no renderer.
//
// TWO DELIBERATE DIFFERENCES FROM THE PHYSICS PATH:
//
// - SKY BRUSHES ARE PICKABLE. They render and clip but carry no collider
// (dc_level.cpp build_colliders skips them), so a physics ray goes straight
// through and the author cannot select the boundary they themselves marked.
// Here they are ordinary brushes.
// - CARVED BRUSHES ARE HIT AT THEIR HULL. A carved brush leaves the clean view
// and is rendered as a voxel pocket, but the pocket is a derived cache and the
// BRUSH is the editable thing, so that is what a pick resolves to.
//
// Both are improvements for an editor and differences for anything that assumed
// collider semantics, so they are stated here rather than discovered later.
// ---------------------------------------------------------------------------
#include <cmath>
#include <cstdint>
#include <vector>
#include "dc_brush_store.h"
#include "dc_csg4.h"
namespace dc_pick {
struct Hit {
uint32_t brush = 0; // 0 = none
uint32_t face = 0; // index into that brush's planes
CSG4Vec3 point{0, 0, 0}; // where the ray met the surface
CSG4Vec3 normal{0, 0, 0}; // that face's outward normal
float t = 0.0f; // distance along `dir`, which is normalized here
// The ray STARTED inside this brush, so `face` is the surface ahead (the exit)
// rather than one it entered through. A camera can legitimately be inside a
// wall — clipping, a carved pocket, spectating — and reporting nothing there
// would read as a broken pick.
bool inside = false;
};
// Cheap reject: does the ray meet the brush's AABB at all? A whole-level pick is
// one ray against ~1200 brushes, so this runs far more often than the slab clip
// below and exists to keep that from being ~7000 plane divisions.
inline bool aabb_hit(const DCBrush& b, const CSG4Vec3& o, const CSG4Vec3& dir,
float max_t, float t_min) {
float tmin = t_min, tmax = max_t;
const float lo[3] = {b.lo.x, b.lo.y, b.lo.z};
const float hi[3] = {b.hi.x, b.hi.y, b.hi.z};
const float od[3] = {o.x, o.y, o.z};
const float dd[3] = {dir.x, dir.y, dir.z};
for (int i = 0; i < 3; i++) {
if (std::fabs(dd[i]) < 1e-12f) {
if (od[i] < lo[i] || od[i] > hi[i]) return false; // parallel and outside
continue;
}
const float inv = 1.0f / dd[i];
float t1 = (lo[i] - od[i]) * inv;
float t2 = (hi[i] - od[i]) * inv;
if (t1 > t2) { const float s = t1; t1 = t2; t2 = s; }
if (t1 > tmin) tmin = t1;
if (t2 < tmax) tmax = t2;
if (tmin > tmax) return false;
}
return true;
}
// One brush. `t_min` lets a caller ignore geometry behind a near plane.
inline bool raycast_brush(const DCBrush& b, const CSG4Vec3& o, const CSG4Vec3& dir,
float max_t, Hit& out, float t_min = 0.0f) {
float t_enter = -1e30f, t_exit = 1e30f;
int enter_face = -1, exit_face = -1;
for (size_t i = 0; i < b.planes.size(); i++) {
const ConvexPlane& p = b.planes[i];
const float denom = p.nx * dir.x + p.ny * dir.y + p.nz * dir.z;
const float dist = p.d - (p.nx * o.x + p.ny * o.y + p.nz * o.z);
if (std::fabs(denom) < 1e-12f) {
// Parallel to this plane: it can only ever exclude, never bound.
if (dist < 0.0f) return false; // already outside, and staying
continue;
}
const float t = dist / denom;
if (denom < 0.0f) {
if (t > t_enter) { t_enter = t; enter_face = (int)i; }
} else {
if (t < t_exit) { t_exit = t; exit_face = (int)i; }
}
}
if (enter_face < 0 && exit_face < 0) return false; // unbounded in every plane
if (t_enter > t_exit) return false; // slabs do not overlap
if (t_exit < t_min) return false; // entirely behind us
const bool inside = t_enter < t_min;
const float t = inside ? t_exit : t_enter;
const int face = inside ? exit_face : enter_face;
if (face < 0 || t > max_t) return false;
out.brush = b.id;
out.face = (uint32_t)face;
out.t = t;
out.inside = inside;
out.point = { o.x + dir.x * t, o.y + dir.y * t, o.z + dir.z * t };
out.normal = { b.planes[face].nx, b.planes[face].ny, b.planes[face].nz };
return true;
}
// The whole store: nearest hit wins. Tombstoned brushes are not there to be hit.
//
// A TIE GOES TO THE EARLIER BRUSH IN STORE ORDER, which is import order and
// therefore identical on every peer — so this pick is deterministic across
// machines, which the physics one is not. Ties are not exotic: Quake maps abut
// brushes on shared planes, so a ray meets both at the same point with the same
// normal. Measured on START.MAP, 1 of 60 rays (brushes 165 and 112, gap 0.00000 m).
// Both answers are correct; this one is at least the same everywhere.
//
// `dir` is normalized internally, so `t` is a real distance and `max_t` is metres
// rather than a multiple of however long the caller's direction vector happened to
// be — a footgun worth closing at the boundary.
// `include_clearance` admits brushes that are air the level owns (DCBrush::
// clearance) — off by default, because a clearance volume ENCLOSES the shape it
// belongs to, so admitting it makes every ray aimed at a flight of stairs hit
// the headroom box in front of them instead. The editor's clearance view turns
// it on so those volumes can be selected and dragged like anything else.
inline bool raycast(const DCBrushStore& store, const CSG4Vec3& origin,
const CSG4Vec3& direction, float max_t, Hit& out,
float t_min = 0.0f, bool include_clearance = false) {
const float len = std::sqrt(direction.x * direction.x +
direction.y * direction.y +
direction.z * direction.z);
if (len < 1e-12f) return false; // no direction, no ray
const CSG4Vec3 dir{direction.x / len, direction.y / len, direction.z / len};
bool any = false;
Hit best;
for (const DCBrush& b : store.brushes()) {
if (b.tombstoned) continue;
if (b.clearance && !include_clearance) continue;
// AABB first: a whole-level pick is one ray against ~1200 brushes, and the
// slab clip is ~6 planes each. Rejecting on bounds keeps that honest.
if (b.bounds_valid && !aabb_hit(b, origin, dir, max_t, t_min)) continue;
Hit h;
if (!raycast_brush(b, origin, dir, max_t, h, t_min)) continue;
if (any && h.t >= best.t) continue;
best = h;
any = true;
}
if (!any) return false;
// A DORMANT plane must never win. A plane that currently bounds nothing stays
// in the set — that is what makes topology change reversible — but it is not a
// surface: handing the editor a face it cannot see or drag would be a lie, and
// nearest_face already refuses to. It can only tie, never strictly win (the
// solid lies inside it), so re-resolving by the hit POINT is exact and lands on
// the same face the physics path's pick_face would name.
if (!store.face_is_live(best.brush, best.face)) {
const int live = store.nearest_face(best.brush, best.point.x,
best.point.y, best.point.z);
if (live < 0) return false; // bounds nothing at all
best.face = (uint32_t)live;
const DCBrush* b = store.get(best.brush);
best.normal = { b->planes[live].nx, b->planes[live].ny, b->planes[live].nz };
}
out = best;
return true;
}
} // namespace dc_pick
#endif // DC_PICK_H