// OctreeClipmap implementation -- distance-based split/merge with hysteresis.
#include "dc_octree_clipmap.h"
#include <cmath>
#include <algorithm>
#include <utility>
#include <cstdio>
// Helper: sort 8 children by distance (farthest first) and push onto stack.
// LIFO means closest is popped first, getting priority for split budget.
static void _push_children_sorted(std::vector<OctreeClipmapNode*>& stack,
OctreeClipmapNode* parent,
const float cam_pos[3],
float base_voxel_size, int voxels_per_cell) {
struct ChildDist {
OctreeClipmapNode* node;
float dist_sq;
};
ChildDist sorted[8];
for (int i = 0; i < 8; i++) {
OctreeClipmapNode* c = parent->children[i];
sorted[i].node = c;
float cs = lod_voxel_size(base_voxel_size, c->lod_level)
* static_cast<float>(voxels_per_cell);
float cx = c->position.x * base_voxel_size + cs * 0.5f;
float cy = c->position.y * base_voxel_size + cs * 0.5f;
float cz = c->position.z * base_voxel_size + cs * 0.5f;
float dx = cam_pos[0] - cx;
float dy = cam_pos[1] - cy;
float dz = cam_pos[2] - cz;
sorted[i].dist_sq = dx * dx + dy * dy + dz * dz;
}
// Sort farthest first so closest ends up on top of LIFO stack
std::sort(sorted, sorted + 8,
[](const ChildDist& a, const ChildDist& b) { return a.dist_sq > b.dist_sq; });
for (int i = 0; i < 8; i++) {
stack.push_back(sorted[i].node);
}
}
// ---------- Public API ----------
void OctreeClipmap::initialize() {
clear();
root_ = pool_.allocate();
int root_lod = max_lod_levels - 1;
int root_span = lod_voxel_span(voxels_per_cell, root_lod);
int half = root_span / 2;
// Center root on root_center_ (default origin, updated by recenter)
root_->position = Vector3i(
root_center_.x - half,
root_center_.y - half,
root_center_.z - half);
root_->lod_level = root_lod;
root_->morton_code = morton_encode(0, 0, 0, root_->lod_level);
root_->state = OctreeClipmapNode::PENDING;
pre_mesh_cache_.clear();
pending_.push_back(root_);
}
void OctreeClipmap::recenter(const Vector3i& new_center, uint32_t frame) {
if (!root_) return;
if (root_center_ == new_center) return;
root_center_ = new_center;
initialize();
invalidate_settled();
}
void OctreeClipmap::recenter_incremental(const Vector3i& new_center, uint32_t frame) {
if (!root_) return;
if (root_center_ == new_center) return;
int root_lod = root_->lod_level;
int root_span = lod_voxel_span(voxels_per_cell, root_lod);
int half = root_span / 2;
int child_lod = root_lod - 1;
int child_span = lod_voxel_span(voxels_per_cell, child_lod);
Vector3i new_pos(new_center.x - half, new_center.y - half, new_center.z - half);
// Save old children and their positions
OctreeClipmapNode* old_children[8] = {};
Vector3i old_child_pos[8] = {};
for (int i = 0; i < 8; i++) {
old_children[i] = root_->children[i];
if (old_children[i]) {
old_child_pos[i] = old_children[i]->position;
}
root_->children[i] = nullptr;
}
// Update root
root_->position = new_pos;
root_center_ = new_center;
// For each new child slot, try to transplant from old children
for (int i = 0; i < 8; i++) {
int cx = (i >> 2) & 1;
int cy = (i >> 1) & 1;
int cz = i & 1;
Vector3i want_pos(
new_pos.x + cx * child_span,
new_pos.y + cy * child_span,
new_pos.z + cz * child_span);
bool found = false;
for (int j = 0; j < 8; j++) {
if (old_children[j] &&
old_child_pos[j].x == want_pos.x &&
old_child_pos[j].y == want_pos.y &&
old_child_pos[j].z == want_pos.z) {
// Transplant — keep entire subtree alive
root_->children[i] = old_children[j];
old_children[j]->parent = root_;
old_children[j] = nullptr;
found = true;
break;
}
}
if (!found) {
// Create new PENDING child
OctreeClipmapNode* child = pool_.allocate();
child->position = want_pos;
child->lod_level = child_lod;
child->parent = root_;
child->state = OctreeClipmapNode::PENDING;
child->morton_code = morton_encode(
want_pos.x, want_pos.y, want_pos.z, child_lod);
root_->children[i] = child;
pending_.push_back(child);
}
}
// Free old children that weren't transplanted
for (int i = 0; i < 8; i++) {
if (old_children[i]) {
_free_subtree(old_children[i]);
}
}
pre_mesh_cache_.clear();
invalidate_settled();
}
void OctreeClipmap::traverse(const float cam_pos[3], uint32_t frame) {
if (!root_) return;
// Skip traverse if LOD is settled — nothing will change.
if (stats_.settled) return;
stats_.splits_this_frame = 0;
stats_.merges_this_frame = 0;
stats_.leaf_count = 0;
stats_.pending_count = 0;
stats_.blocked_count = 0;
stats_.lod0_wanted = 0;
int splits_rem = max_splits_per_frame;
int merges_rem = max_merges_per_frame;
_traverse_node(root_, cam_pos, frame, splits_rem, merges_rem);
// Settled when traverse produced zero work and nothing is pending
stats_.settled = (stats_.splits_this_frame == 0 &&
stats_.merges_this_frame == 0 &&
stats_.blocked_count == 0 &&
stats_.pending_count == 0);
// LOD0 is "settled" once no coarse (lod>0) leaf still wants to refine toward LOD0.
// Gates whether sub-LOD (-2) stamp refinement is allowed (see min_lod in
// _traverse_node) so the world reaches LOD0 everywhere BEFORE any stamp pushes to -2.
// Read on the NEXT traverse (one-frame lag) — the initial false defers -2 until the
// first LOD0-complete frame.
stats_.lod0_settled = (stats_.lod0_wanted == 0);
}
void OctreeClipmap::invalidate_settled() {
stats_.settled = false;
}
void OctreeClipmap::check_stale_parents() {
if (root_) _check_stale_recursive(root_);
}
std::vector<OctreeClipmapNode*> OctreeClipmap::get_leaves() const {
std::vector<OctreeClipmapNode*> out;
if (root_) _collect_leaves(root_, out);
return out;
}
std::vector<OctreeClipmapNode*> OctreeClipmap::get_stale_parents() const {
std::vector<OctreeClipmapNode*> out;
if (!root_) return out;
std::vector<OctreeClipmapNode*> stack;
stack.push_back(root_);
while (!stack.empty()) {
auto* n = stack.back(); stack.pop_back();
if (!n) continue;
if (n->parent_mesh_stale) out.push_back(n);
if (!n->is_leaf()) {
for (int i = 0; i < 8; i++)
if (n->children[i]) stack.push_back(n->children[i]);
}
}
return out;
}
std::vector<OctreeClipmapNode*> OctreeClipmap::drain_pending() {
std::vector<OctreeClipmapNode*> result;
std::swap(result, pending_);
return result;
}
void OctreeClipmap::mark_ready(OctreeClipmapNode* node) {
if (node) node->state = OctreeClipmapNode::READY;
}
void OctreeClipmap::mark_active(OctreeClipmapNode* node) {
if (node) node->state = OctreeClipmapNode::ACTIVE;
}
void OctreeClipmap::mark_pending(OctreeClipmapNode* node) {
if (node && node->state != OctreeClipmapNode::PENDING &&
node->state != OctreeClipmapNode::GENERATING) {
node->state = OctreeClipmapNode::PENDING;
pending_.push_back(node);
}
}
// Re-enqueue a node that's already in PENDING state but was drained from the
// queue without being dispatched (e.g. _submit_to_worker returned false because
// the worker queue was full). drain_pending() pulls the node out but leaves its
// state at PENDING; mark_pending() then refuses to re-enqueue because its guard
// treats "state == PENDING" as "already in queue". This is the recovery path
// for that mismatch: forcefully push the node back into the pending queue.
// Without this, orphaned-PENDING nodes are invisible to edit_terrain_box's
// state filter and never get dispatched again.
void OctreeClipmap::requeue_pending(OctreeClipmapNode* node) {
if (node) {
node->state = OctreeClipmapNode::PENDING;
pending_.push_back(node);
}
}
const ClipmapStats& OctreeClipmap::get_stats() const {
return stats_;
}
void OctreeClipmap::clear() {
if (root_) {
_free_subtree(root_);
root_ = nullptr;
}
pending_.clear();
pre_mesh_cache_.clear();
stats_ = ClipmapStats{};
}
OctreeNodePool& OctreeClipmap::pool() {
return pool_;
}
OctreeClipmapNode* OctreeClipmap::find_leaf_containing(int vx, int vy, int vz) const {
if (!root_) return nullptr;
OctreeClipmapNode* node = root_;
while (!node->is_leaf()) {
int child_lod = node->lod_level - 1;
int half = lod_voxel_span(voxels_per_cell, child_lod);
int cx = (vx >= node->position.x + half) ? 1 : 0;
int cy = (vy >= node->position.y + half) ? 1 : 0;
int cz = (vz >= node->position.z + half) ? 1 : 0;
int idx = (cx << 2) | (cy << 1) | cz;
if (!node->children[idx]) return nullptr;
node = node->children[idx];
}
// Verify the point is actually within this leaf's bounds
int span = lod_voxel_span(voxels_per_cell, node->lod_level);
if (vx < node->position.x || vx >= node->position.x + span) return nullptr;
if (vy < node->position.y || vy >= node->position.y + span) return nullptr;
if (vz < node->position.z || vz >= node->position.z + span) return nullptr;
return node;
}
// ---------- Private ----------
void OctreeClipmap::_traverse_node(OctreeClipmapNode* node, const float cam_pos[3],
uint32_t frame, int& splits_rem, int& merges_rem) {
// Separate split budgets: coarse LODs (>=3) always populate to fill the
// horizon. Fine LODs (0-2) share the remaining budget and are view-gated.
int coarse_splits_rem = 64; // generous budget — coarse chunks are cheap
// Iterative traversal to avoid stack overflow at high octree depths.
std::vector<OctreeClipmapNode*> stack;
stack.push_back(node);
while (!stack.empty()) {
OctreeClipmapNode* cur = stack.back();
stack.pop_back();
if (!cur) continue;
float dist = _distance_to_node(cam_pos, cur);
float cs = _cell_size(cur->lod_level);
if (cur->is_leaf()) {
stats_.leaf_count++;
if (cur->state == OctreeClipmapNode::PENDING) {
stats_.pending_count++;
}
// Split condition: close enough, have budget, not at finest LOD,
// and node must be ACTIVE (finished generating).
// Also enforce a cooldown after merge to prevent split-merge thrashing.
//
// Content-aware LOD: geometric_error scales the split distance.
// Cells with large error (complex surfaces, steep slopes) split at
// greater distances, giving them more resolution.
// error_boost = max(1, geometric_error / voxel_size_at_this_lod)
// This means a cell where the surface deviates by 2 voxel sizes
// from the grid approximation will split at 2x the normal distance.
bool split_cooldown_ok = (cur->last_merge_frame == 0) ||
(frame - cur->last_merge_frame) >= static_cast<uint32_t>(merge_cooldown_frames);
float error_boost = 1.0f;
if (content_aware_lod && cur->geometric_error > 0.0f && cur->lod_level < 6) {
// Only boost split distance for fine LODs — high LODs cover huge areas
// where fractal noise always produces high error, causing avalanche splits.
float lod_vs = lod_voxel_size(base_voxel_size, cur->lod_level);
error_boost = std::max(1.0f, cur->geometric_error / lod_vs);
if (error_boost > 2.0f) error_boost = 2.0f;
}
bool should_split = false;
// Distance-based: always provides minimum quality guarantee.
// Also check edit focus points — edits act as virtual cameras
// so terrain near edits gets fine LOD for detail.
// Split by ACTUAL camera distance. (Previously edit_focus_points collapsed
// this to ~0 so a stamp region wanted to split regardless of camera distance —
// that fought the real-distance merge (see should_merge below) into a split/
// merge thrash that never converged. Sub-voxel detail is only visible up close,
// so the focus points now ONLY raise the sub-LOD floor (min_lod=-2, gated on
// lod0_settled) and no longer force a distance-independent split: a stamp
// refines to -2 when near, merges to LOD0 when far, and converges everywhere.)
bool distance_split = dist < cs * lod_factor * error_boost;
if (use_screen_space_error && cur->geometric_error > 0.0f) {
// Screen-space error: adds extra splits for high-error areas
// even beyond the distance threshold.
float safe_dist = std::max(dist, 0.001f);
float screen_pixels = (cur->geometric_error / safe_dist)
* viewport_height / (2.0f * std::tan(camera_fov_rad * 0.5f));
should_split = distance_split || (screen_pixels > screen_split_threshold);
} else {
should_split = distance_split;
}
// Track LOD0 progress: a leaf still coarser than LOD0 (lod>0) that wants to
// refine means the world hasn't reached LOD0 everywhere yet. Sub-LOD leaves
// (lod<=0) must NOT count, or they'd hold lod0_settled open forever.
if (should_split && cur->lod_level > 0) stats_.lod0_wanted++;
// Sub-LOD (-2) refinement near edit stamps runs ONLY after the LOD0 tree has
// settled (lod0_settled, from the previous traverse): the world fills to LOD0
// first, THEN stamp focus regions push down to -2 (driven by camera distance
// via distance_split above). LOD -1/0 boundaries may have cracks at focus edge.
int min_lod = 0;
if (stats_.lod0_settled) {
for (const auto& fp : edit_focus_points) {
float fd = _distance_to_node(fp.data(), cur);
if (fd < fp[3]) { min_lod = -2; break; }
}
// Adaptive architecture LOD (experimental, off by default): a node whose AABB
// overlaps the edited-architecture region may refine to arch_min_lod (2x) when
// the camera is near — capped at arch_min_lod, reusing the distance split below.
if (arch_lod_active && min_lod > arch_min_lod) {
float cs2 = _cell_size(cur->lod_level);
float nx0 = cur->position.x * base_voxel_size, nx1 = nx0 + cs2;
float ny0 = cur->position.y * base_voxel_size, ny1 = ny0 + cs2;
float nz0 = cur->position.z * base_voxel_size, nz1 = nz0 + cs2;
if (nx1 >= arch_min[0] && nx0 <= arch_max[0] &&
ny1 >= arch_min[1] && ny0 <= arch_max[1] &&
nz1 >= arch_min[2] && nz0 <= arch_max[2]) {
min_lod = arch_min_lod;
}
}
}
// Coarse LODs (>=3) use their own generous budget so the horizon
// fills quickly. Fine LODs (0-2) use the normal per-frame budget.
bool is_coarse = cur->lod_level >= 3;
int& budget = is_coarse ? coarse_splits_rem : splits_rem;
if (should_split && cur->lod_level > min_lod && budget > 0
&& cur->state == OctreeClipmapNode::ACTIVE && split_cooldown_ok) {
if (lod_mode == LOD_BLOCKING_SWAP) {
// BLOCKING_SWAP: don't split until all children's meshes are cached
ChildInfo children[8];
compute_child_info(cur, children);
bool all_ready = true;
for (int i = 0; i < 8; i++) {
PreMeshEntry* e = get_pre_mesh(children[i].morton_code);
if (!e || e->state != OctreeClipmapNode::MESH_UP_TO_DATE) {
all_ready = false;
// Request mesh if never started, or re-request if stuck
// generating for too long (result may have been discarded
// due to generation bump from clipmap recenter).
bool needs_request = !e || e->state == OctreeClipmapNode::MESH_NEVER_UPDATED;
if (!needs_request && e && e->state == OctreeClipmapNode::MESH_GENERATING &&
(frame - e->dispatch_frame) > 60) {
needs_request = true;
}
if (needs_request) {
PreMeshEntry& ne = ensure_pre_mesh(children[i].morton_code);
ne.state = OctreeClipmapNode::MESH_PENDING;
ne.position = children[i].position;
ne.lod_level = children[i].lod_level;
}
}
}
if (all_ready) {
split_node_from_cache(cur, frame);
budget--;
stats_.splits_this_frame++;
stats_.total_splits++;
_push_children_sorted(stack, cur, cam_pos, base_voxel_size, voxels_per_cell);
} else {
stats_.blocked_count++;
}
} else {
// EAGER_FADE: split immediately
_split_node(cur, frame);
budget--;
stats_.splits_this_frame++;
stats_.total_splits++;
// Push new children sorted by distance (closest first via LIFO)
_push_children_sorted(stack, cur, cam_pos, base_voxel_size, voxels_per_cell);
}
}
} else {
// Internal node -- check merge condition
bool all_children_leaves = true;
for (int i = 0; i < 8; i++) {
if (!cur->children[i]->is_leaf()) {
all_children_leaves = false;
break;
}
}
bool cooldown_ok = (frame - cur->last_split_frame) >= static_cast<uint32_t>(merge_cooldown_frames);
// Content-aware merge: if all children are genuinely generated and empty,
// merge at a reduced distance threshold.
float merge_factor = lod_factor * hysteresis;
if (content_aware_lod && all_children_leaves) {
bool all_generated_empty = true;
for (int i = 0; i < 8; i++) {
auto* child = cur->children[i];
if (child->state != OctreeClipmapNode::ACTIVE ||
!child->content_known || child->triangle_count > 0) {
all_generated_empty = false;
break;
}
}
if (all_generated_empty) {
merge_factor = lod_factor * 0.5f;
}
}
// Safety: never merge if any child is PENDING or GENERATING — worker threads
// hold raw pointers to those nodes and would write to freed memory.
bool all_children_safe = true;
if (all_children_leaves) {
for (int i = 0; i < 8; i++) {
auto s = cur->children[i]->state;
if (s == OctreeClipmapNode::PENDING || s == OctreeClipmapNode::GENERATING) {
all_children_safe = false;
break;
}
}
}
bool should_merge = false;
if (use_screen_space_error) {
// Use the PARENT's geometric error for merge decision.
// This answers "would the coarser parent mesh be acceptable?"
// Using children's error is wrong — children are finer, so their error
// is always smaller, causing merge. Then the parent splits again → thrash.
float parent_error = cur->geometric_error;
if (parent_error > 0.0f) {
float safe_dist = std::max(dist, 0.001f);
float screen_pixels = (parent_error / safe_dist)
* viewport_height / (2.0f * std::tan(camera_fov_rad * 0.5f));
should_merge = screen_pixels < screen_merge_threshold;
} else {
// Parent hasn't been generated yet — use distance fallback
should_merge = dist > cs * merge_factor;
}
} else {
should_merge = dist > cs * merge_factor;
}
if (all_children_leaves && all_children_safe && should_merge && cooldown_ok && merges_rem > 0) {
if (lod_mode == LOD_BLOCKING_SWAP) {
// BLOCKING_SWAP: don't merge until parent's mesh is cached
PreMeshEntry* pe = get_pre_mesh(cur->morton_code);
if (pe && pe->state == OctreeClipmapNode::MESH_UP_TO_DATE) {
merge_node_from_cache(cur, frame);
merges_rem--;
stats_.merges_this_frame++;
stats_.total_merges++;
stats_.leaf_count++;
} else {
if (!pe || pe->state == OctreeClipmapNode::MESH_NEVER_UPDATED) {
PreMeshEntry& ne = ensure_pre_mesh(cur->morton_code);
ne.state = OctreeClipmapNode::MESH_PENDING;
ne.position = cur->position;
ne.lod_level = cur->lod_level;
}
stats_.blocked_count++;
_push_children_sorted(stack, cur, cam_pos, base_voxel_size, voxels_per_cell);
}
} else {
// EAGER_FADE: signal children to fade out first
bool all_faded_out = true;
for (int i = 0; i < 8; i++) {
if (cur->children[i]->fade_t > 0.01f) {
cur->children[i]->fade_target = 0.0f;
all_faded_out = false;
}
}
if (all_faded_out) {
_merge_node(cur, frame);
merges_rem--;
stats_.merges_this_frame++;
stats_.total_merges++;
stats_.leaf_count++; // merged node is now a leaf
if (cur->state == OctreeClipmapNode::PENDING) {
stats_.pending_count++;
}
} else {
// Still fading out — push children so they remain visible
_push_children_sorted(stack, cur, cam_pos, base_voxel_size, voxels_per_cell);
}
}
} else {
if (lod_mode == LOD_EAGER_FADE) {
// Cancel any in-progress fade-out if merge is no longer desired
for (int i = 0; i < 8; i++) {
if (cur->children[i] && cur->children[i]->fade_target < 1.0f) {
cur->children[i]->fade_target = 1.0f;
}
}
}
// If merge no longer desired, evict pre-mesh cache entry
if (lod_mode == LOD_BLOCKING_SWAP && !should_merge) {
pre_mesh_cache_.erase(cur->morton_code);
}
// Push children sorted by distance (closest first via LIFO)
_push_children_sorted(stack, cur, cam_pos, base_voxel_size, voxels_per_cell);
}
}
}
}
float OctreeClipmap::_distance_to_node(const float cam_pos[3], OctreeClipmapNode* node) const {
float cs = _cell_size(node->lod_level);
// Node center in world space
float cx = node->position.x * base_voxel_size + cs * 0.5f;
float cy = node->position.y * base_voxel_size + cs * 0.5f;
float cz = node->position.z * base_voxel_size + cs * 0.5f;
// Euclidean distance — spherical LOD shells instead of diamond-shaped Manhattan shells
float dx = cam_pos[0] - cx;
float dy = cam_pos[1] - cy;
float dz = cam_pos[2] - cz;
return std::sqrt(dx * dx + dy * dy + dz * dz);
}
float OctreeClipmap::_cell_size(int lod) const {
return cell_world_size(lod, base_voxel_size, voxels_per_cell);
}
void OctreeClipmap::_split_node(OctreeClipmapNode* node, uint32_t frame) {
// EAGER_FADE only: Keep parent mesh visible during child generation to prevent holes.
// check_stale_parents() frees it once all children are ACTIVE.
if (node->mesh_instance.is_valid()) {
node->parent_mesh_stale = true;
}
// Keep parent collision alive until children have their own collision bodies.
if (node->collision_body.is_valid()) {
node->parent_collision_stale = true;
}
// Force fade complete — this node is now internal, not rendered directly.
// Without this, _check_stale_recursive on the grandparent sees frozen
// fade_t < 0.99 (fade loop only animates leaves) and never frees its mesh.
node->fade_t = 1.0f;
node->fade_target = 1.0f;
int child_lod = node->lod_level - 1;
// Voxel span of a child cell at child_lod
int child_voxel_span = lod_voxel_span(voxels_per_cell, child_lod);
for (int i = 0; i < 8; i++) {
OctreeClipmapNode* child = pool_.allocate();
int cx = (i >> 2) & 1;
int cy = (i >> 1) & 1;
int cz = i & 1;
child->position = Vector3i(
node->position.x + cx * child_voxel_span,
node->position.y + cy * child_voxel_span,
node->position.z + cz * child_voxel_span
);
child->lod_level = child_lod;
child->morton_code = morton_encode(child->position.x, child->position.y, child->position.z, child_lod);
child->parent = node;
child->state = OctreeClipmapNode::PENDING;
child->mesh_state = OctreeClipmapNode::MESH_PENDING;
child->fade_t = 0.0f; // start invisible (dithered out)
child->fade_target = 1.0f; // animate to fully opaque
node->children[i] = child;
pending_.push_back(child);
}
node->last_split_frame = frame;
}
void OctreeClipmap::_merge_node(OctreeClipmapNode* node, uint32_t frame) {
for (int i = 0; i < 8; i++) {
if (node->children[i]) {
_free_subtree(node->children[i]);
node->children[i] = nullptr;
}
}
node->state = OctreeClipmapNode::PENDING;
node->last_merge_frame = frame; // prevent immediate re-split after generation
pending_.push_back(node);
}
void OctreeClipmap::_collect_leaves(OctreeClipmapNode* node, std::vector<OctreeClipmapNode*>& out) const {
if (node->is_leaf()) {
out.push_back(node);
} else {
for (int i = 0; i < 8; i++) {
if (node->children[i]) {
_collect_leaves(node->children[i], out);
}
}
}
}
// Check if all leaf descendants of a subtree have collision bodies.
// Returns true if the node doesn't need collision (null, EMPTY, no triangles)
// or if all leaf descendants with triangles have collision bodies.
bool OctreeClipmap::_subtree_has_collision(OctreeClipmapNode* node) {
if (!node) return true;
if (node->state == OctreeClipmapNode::EMPTY) return true;
if (node->is_leaf()) {
if (node->state == OctreeClipmapNode::ACTIVE && node->triangle_count > 0)
return node->collision_body.is_valid();
if (node->state != OctreeClipmapNode::ACTIVE)
return false; // still pending/generating — not ready
return true; // ACTIVE with no triangles
}
// Internal: all children must have collision
for (int i = 0; i < 8; i++) {
if (!_subtree_has_collision(node->children[i])) return false;
}
return true;
}
void OctreeClipmap::_check_stale_recursive(OctreeClipmapNode* node) {
// Iterative traversal to avoid stack overflow at high octree depths.
std::vector<OctreeClipmapNode*> stack;
if (node) stack.push_back(node);
while (!stack.empty()) {
OctreeClipmapNode* n = stack.back();
stack.pop_back();
if (!n || n->is_leaf()) continue;
bool all_children_active = false;
if (n->parent_mesh_stale || n->parent_collision_stale) {
all_children_active = true;
for (int i = 0; i < 8; i++) {
if (!n->children[i] ||
(n->children[i]->state != OctreeClipmapNode::ACTIVE &&
n->children[i]->state != OctreeClipmapNode::EMPTY) ||
n->children[i]->fade_t < 0.99f) {
all_children_active = false;
break;
}
}
}
// Stage 1: Free parent MESH once all children are ACTIVE.
// Children have their own visual mesh at this point.
if (n->parent_mesh_stale && all_children_active) {
if (on_mesh_free) {
on_mesh_free(n, on_node_free_userdata);
} else if (on_node_free) {
// Fallback: free everything (old behavior)
on_node_free(n, on_node_free_userdata);
n->parent_collision_stale = false;
}
n->parent_mesh_stale = false;
}
// Stage 2: Free parent COLLISION immediately when children are ACTIVE.
// Parent collision is always coarser than children's visual mesh —
// it fills in caves, overhangs, and small features that children resolve.
// The collision queue (2-32/frame, no distance purge) builds children's
// collision within a few frames, so the brief gap is acceptable.
if (n->parent_collision_stale && all_children_active) {
if (on_collision_free) {
on_collision_free(n, on_node_free_userdata);
}
n->parent_collision_stale = false;
}
// Push children for processing
for (int i = 0; i < 8; i++) {
if (n->children[i]) stack.push_back(n->children[i]);
}
}
}
// ---------- Pre-mesh cache methods ----------
PreMeshEntry* OctreeClipmap::get_pre_mesh(uint64_t morton) {
auto it = pre_mesh_cache_.find(morton);
if (it == pre_mesh_cache_.end()) return nullptr;
return &it->second;
}
PreMeshEntry& OctreeClipmap::ensure_pre_mesh(uint64_t morton) {
return pre_mesh_cache_[morton];
}
void OctreeClipmap::clear_pre_mesh_cache() {
pre_mesh_cache_.clear();
}
void OctreeClipmap::compute_child_info(OctreeClipmapNode* parent, ChildInfo out[8]) const {
int child_lod = parent->lod_level - 1;
int child_voxel_span = lod_voxel_span(voxels_per_cell, child_lod);
for (int i = 0; i < 8; i++) {
int cx = (i >> 2) & 1;
int cy = (i >> 1) & 1;
int cz = i & 1;
out[i].position = Vector3i(
parent->position.x + cx * child_voxel_span,
parent->position.y + cy * child_voxel_span,
parent->position.z + cz * child_voxel_span
);
out[i].lod_level = child_lod;
out[i].morton_code = morton_encode(out[i].position.x, out[i].position.y, out[i].position.z, child_lod);
}
}
void OctreeClipmap::split_node_from_cache(OctreeClipmapNode* node, uint32_t frame) {
// Mark parent mesh as stale if it exists — check_stale_parents() handles cleanup.
if (node->mesh_instance.is_valid()) {
node->parent_mesh_stale = true;
}
if (node->collision_body.is_valid()) {
node->parent_collision_stale = true;
}
int child_lod = node->lod_level - 1;
int child_voxel_span = lod_voxel_span(voxels_per_cell, child_lod);
for (int i = 0; i < 8; i++) {
OctreeClipmapNode* child = pool_.allocate();
int cx = (i >> 2) & 1;
int cy = (i >> 1) & 1;
int cz = i & 1;
child->position = Vector3i(
node->position.x + cx * child_voxel_span,
node->position.y + cy * child_voxel_span,
node->position.z + cz * child_voxel_span
);
child->lod_level = child_lod;
child->morton_code = morton_encode(child->position.x, child->position.y, child->position.z, child_lod);
child->parent = node;
// Children start as ACTIVE with MESH_UP_TO_DATE — cache has their mesh
child->state = OctreeClipmapNode::ACTIVE;
child->mesh_state = OctreeClipmapNode::MESH_UP_TO_DATE;
child->fade_t = 1.0f; // no fading — instant swap
child->fade_target = 1.0f;
// Copy metadata from cache
PreMeshEntry* pe = get_pre_mesh(child->morton_code);
if (pe) {
child->geometric_error = pe->data.geometric_error;
child->active_voxel_count = pe->data.active_voxel_count;
child->triangle_count = pe->data.triangle_count;
child->content_known = true;
}
node->children[i] = child;
}
node->last_split_frame = frame;
}
void OctreeClipmap::merge_node_from_cache(OctreeClipmapNode* node, uint32_t frame) {
// Free children — on_node_free callback handles RID cleanup
for (int i = 0; i < 8; i++) {
if (node->children[i]) {
_free_subtree(node->children[i]);
node->children[i] = nullptr;
}
}
// Node becomes a leaf with cached mesh ready
node->state = OctreeClipmapNode::ACTIVE;
node->mesh_state = OctreeClipmapNode::MESH_UP_TO_DATE;
node->last_merge_frame = frame;
// Copy metadata from cache
PreMeshEntry* pe = get_pre_mesh(node->morton_code);
if (pe) {
node->geometric_error = pe->data.geometric_error;
node->active_voxel_count = pe->data.active_voxel_count;
node->triangle_count = pe->data.triangle_count;
node->content_known = true;
}
}
void OctreeClipmap::_free_subtree(OctreeClipmapNode* node) {
// Iterative post-order traversal to avoid stack overflow at high octree depths.
// Uses a stack of (node, child_index) pairs.
struct Frame { OctreeClipmapNode* n; int next_child; };
std::vector<Frame> stack;
stack.push_back({node, 0});
while (!stack.empty()) {
auto& top = stack.back();
if (top.next_child < 8) {
int i = top.next_child++;
if (top.n->children[i]) {
stack.push_back({top.n->children[i], 0});
}
} else {
// All children processed — free this node
OctreeClipmapNode* n = top.n;
stack.pop_back();
for (int i = 0; i < 8; i++) n->children[i] = nullptr;
if (on_node_free) {
on_node_free(n, on_node_free_userdata);
}
pool_.free(n);
}
}
}