#ifndef DC_OCTREE_CLIPMAP_H
#define DC_OCTREE_CLIPMAP_H
// Octree clipmap data structures for LOD-based terrain.
// Pure C++ core -- Godot types conditionally included.
//
// OctreeClipmapNode: represents a single cell in the clipmap octree.
// OctreeNodePool: block allocator with free-list recycling.
// SeamNodeInfo: boundary node data for cross-LOD seam stitching.
#include <array>
#include <cstdint>
#include <cstring>
#include <vector>
#include <unordered_map>
// ---------- Godot / standalone compatibility ----------
// When building inside Godot GDExtension, Vector3i and RID are available.
// For standalone tests, provide minimal stubs.
#if defined(GODOT_MODULE) || __has_include(<godot_cpp/variant/vector3i.hpp>)
#define DC_CLIPMAP_GODOT 1
#include <godot_cpp/variant/vector3i.hpp>
#include <godot_cpp/variant/rid.hpp>
using godot::Vector3i;
using godot::RID;
#else
#define DC_CLIPMAP_GODOT 0
struct Vector3i {
int x = 0, y = 0, z = 0;
Vector3i() = default;
Vector3i(int x_, int y_, int z_) : x(x_), y(y_), z(z_) {}
bool operator==(const Vector3i& o) const { return x == o.x && y == o.y && z == o.z; }
bool operator!=(const Vector3i& o) const { return !(*this == o); }
};
struct RID {
uint64_t id = 0;
RID() = default;
bool is_valid() const { return id != 0; }
};
#endif
// ---------- SeamNodeInfo ----------
// Boundary node data for cross-LOD seam stitching (48 bytes).
struct SeamNodeInfo {
Vector3i local_min; // voxel grid position (0..31)
float position[3] = {}; // world-space QEF vertex
float normal[3] = {}; // surface normal
uint32_t corner_signs = 0; // 8-bit sign field
uint32_t material_id = 0;
};
// ---------- OctreeClipmapNode ----------
// Single cell in the clipmap octree (~176 bytes, pool-allocated).
struct OctreeClipmapNode {
enum State : uint8_t {
EMPTY,
PENDING,
GENERATING,
READY,
ACTIVE,
PENDING_MERGE
};
// Mesh lifecycle state for BLOCKING_SWAP mode (coexists with State for EAGER_FADE compat)
enum MeshState : uint8_t {
MESH_NEVER_UPDATED = 0,
MESH_PENDING, // queued for worker
MESH_GENERATING, // worker processing
MESH_UP_TO_DATE, // mesh built and uploaded
MESH_NEED_UPDATE // needs re-generation (edit invalidation)
};
Vector3i position; // voxel-space corner
int lod_level = 0; // 0 = finest
uint64_t morton_code = 0; // spatial hash
OctreeClipmapNode* children[8] = {}; // null if leaf
OctreeClipmapNode* parent = nullptr;
State state = EMPTY;
RID mesh_instance;
// The origin HANDED TO instance_set_transform, recorded rather than
// recomputed. Comparing the visual surface against the collision surface is
// only evidence if both numbers come from what was actually used: the
// collision side is read back from PhysicsServer3D, so this side must be
// the value that was actually set, not the formula re-evaluated.
float mesh_origin[3] = { 0.0f, 0.0f, 0.0f };
RID collision_body;
RID collision_shape;
RID normal_map_texture;
uint32_t triangle_count = 0;
SeamNodeInfo* seam_nodes = nullptr;
int num_seam_nodes = 0;
RID seam_mesh_instance;
uint32_t active_voxel_count = 0;
float geometric_error = 0.0f; // max surface deviation in world units (for content-aware LOD)
bool content_known = false; // true after worker has generated this cell
uint32_t generation = 0; // incremented on each pool allocation, for stale pointer detection
uint32_t last_split_frame = 0;
uint32_t last_merge_frame = 0; // frame when this node was re-created by a merge
uint32_t last_visible_frame = 0;
// Transition state: parent mesh/collision kept until children are ready
bool parent_mesh_stale = false; // true = this internal node still has visible parent mesh
bool parent_collision_stale = false; // true = parent collision kept until children have collision
float fade_t = 1.0f; // 0 = invisible (dithered out), 1 = fully opaque
float fade_target = 1.0f; // animation target
bool shadow_disabled_for_stale = false; // true = shadow casting turned off on stale parent
// BLOCKING_SWAP mode fields
MeshState mesh_state = MESH_NEVER_UPDATED;
// Set by edit/stamp ops so the dispatcher routes this node's remesh through
// the worker's high-priority lane (1b). Cleared on successful dispatch and
// on reset() (recycled-slot safe — no dangling DCTerrain-side pointer set).
bool edit_dirty = false;
// "Remesh once more after your in-flight result lands." Same lifecycle as
// edit_dirty — consumed on successful dispatch — but deliberately NOT part
// of the priority-lane sort.
//
// edit_dirty conflated two jobs: the priority lane AND the guaranteed
// follow-up remesh for a chunk that was GENERATING when an edit landed
// (dc_terrain.cpp: mark_pending() no-ops on GENERATING, so the post-upload
// re-queue is the ONLY thing that gets that chunk remeshed). A NON-interactive
// edit needs the second without the first: the §5a.2 level shell is one edit
// with a 64 m radius that overlaps hundreds of chunks at once, and putting all
// of them in the priority lane starves normal LOD streaming — which is exactly
// why map_dc_world passes interactive=false. Without this flag it bought that
// by silently giving up the follow-up remesh, so every chunk that happened to
// be in flight when the shell landed kept its pre-stamp geometry for the whole
// session: terrain standing inside the level's rooms while the density field
// at those very points reads air.
bool remesh_after_upload = false;
bool is_leaf() const { return children[0] == nullptr; }
void reset() {
position = Vector3i();
lod_level = 0;
morton_code = 0;
for (int i = 0; i < 8; i++) children[i] = nullptr;
parent = nullptr;
state = EMPTY;
mesh_instance = RID();
collision_body = RID();
collision_shape = RID();
normal_map_texture = RID();
triangle_count = 0;
seam_nodes = nullptr;
num_seam_nodes = 0;
seam_mesh_instance = RID();
active_voxel_count = 0;
geometric_error = 0.0f;
content_known = false;
last_split_frame = 0;
last_merge_frame = 0;
last_visible_frame = 0;
parent_mesh_stale = false;
parent_collision_stale = false;
fade_t = 1.0f;
fade_target = 1.0f;
shadow_disabled_for_stale = false;
mesh_state = MESH_NEVER_UPDATED;
edit_dirty = false;
remesh_after_upload = false;
}
};
// ---------- OctreeNodePool ----------
// Block allocator with free-list recycling. Blocks of 1024 nodes.
class OctreeNodePool {
static constexpr int BLOCK_SIZE = 1024;
struct Block {
OctreeClipmapNode nodes[BLOCK_SIZE];
};
std::vector<Block*> blocks_;
OctreeClipmapNode* free_list_ = nullptr;
int allocated_ = 0;
int next_in_block_ = BLOCK_SIZE; // force first allocation to create a block
public:
OctreeNodePool() = default;
~OctreeNodePool() {
for (auto* b : blocks_) delete b;
}
// Non-copyable
OctreeNodePool(const OctreeNodePool&) = delete;
OctreeNodePool& operator=(const OctreeNodePool&) = delete;
OctreeClipmapNode* allocate() {
OctreeClipmapNode* node;
if (free_list_) {
node = free_list_;
free_list_ = free_list_->parent; // reuse parent ptr as next-free
} else {
if (next_in_block_ >= BLOCK_SIZE) {
blocks_.push_back(new Block());
next_in_block_ = 0;
}
node = &blocks_.back()->nodes[next_in_block_++];
}
node->reset();
node->generation++; // new allocation = new generation (survives reset)
allocated_++;
return node;
}
void free(OctreeClipmapNode* node) {
node->parent = free_list_; // reuse parent ptr as next-free
free_list_ = node;
allocated_--;
}
int allocated_count() const { return allocated_; }
};
// ---------- Utility functions ----------
// LOD voxel span in integer voxel units (for position calculations).
// LOD 0 with vpc=32 → 32, LOD -1 → 16, LOD 1 → 64.
inline int lod_voxel_span(int voxels_per_cell, int lod_level) {
if (lod_level >= 0)
return voxels_per_cell * (1 << lod_level);
else
return std::max(1, voxels_per_cell / (1 << (-lod_level)));
}
// LOD voxel size — handles negative LOD levels (sub-LOD splitting near edits).
// LOD 0 = base, LOD 1 = 2x, LOD -1 = 0.5x, LOD -2 = 0.25x.
inline float lod_voxel_size(float base_voxel_size, int lod_level) {
if (lod_level >= 0)
return base_voxel_size * static_cast<float>(1 << lod_level);
else
return base_voxel_size / static_cast<float>(1 << (-lod_level));
}
// Cell world size for a given LOD level (supports negative LOD).
inline float cell_world_size(int lod, float base_voxel_size, int voxels_per_cell) {
return lod_voxel_size(base_voxel_size, lod) * static_cast<float>(voxels_per_cell);
}
// Morton code encoding: interleave x, y, z bits with lod in high bits.
// Supports 20 bits per axis (coordinates 0..1048575).
inline uint64_t morton_encode(int x, int y, int z, int lod) {
auto expand = [](uint64_t v) -> uint64_t {
v &= 0xFFFFF; // 20 bits
v = (v | (v << 32)) & 0x1F00000000FFFF;
v = (v | (v << 16)) & 0x1F0000FF0000FF;
v = (v | (v << 8)) & 0x100F00F00F00F00F;
v = (v | (v << 4)) & 0x10C30C30C30C30C3;
v = (v | (v << 2)) & 0x1249249249249249;
return v;
};
uint64_t code = expand(static_cast<uint64_t>(x))
| (expand(static_cast<uint64_t>(y)) << 1)
| (expand(static_cast<uint64_t>(z)) << 2);
// Pack lod into top 4 bits
code |= (static_cast<uint64_t>(lod & 0xF) << 60);
return code;
}
// ---------- Forward declarations for pre-mesh cache ----------
// DCMeshData is defined in dc_contour.h — include it for CachedMeshData.
#include "dc_contour.h"
// Cached mesh data for pre-mesh entries (stored before octree nodes exist)
struct CachedMeshData {
DCMeshData mesh_data;
std::vector<SeamNodeInfo> seam_nodes;
uint32_t active_voxel_count = 0;
uint32_t triangle_count = 0;
float geometric_error = 0.0f;
};
struct PreMeshEntry {
OctreeClipmapNode::MeshState state = OctreeClipmapNode::MESH_NEVER_UPDATED;
CachedMeshData data;
uint32_t generation = 0;
uint32_t dispatch_frame = 0; // frame when MESH_GENERATING started
Vector3i position; // voxel-space position
int lod_level = 0;
};
// ---------- ClipmapStats ----------
// LOD transition mode
enum LodMode : uint8_t {
LOD_EAGER_FADE = 0, // existing behavior: split eagerly, fade covers gap
LOD_BLOCKING_SWAP = 1 // godot-voxel pattern: block splits until children ready
};
struct ClipmapStats {
int total_splits = 0;
int total_merges = 0;
int splits_this_frame = 0;
int merges_this_frame = 0;
int leaf_count = 0;
int pending_count = 0;
int blocked_count = 0; // nodes waiting for children (BLOCKING_SWAP mode)
int lod0_wanted = 0; // coarse (lod>0) leaves still wanting to refine toward LOD0
bool lod0_settled = false; // true once the LOD0 tree is done -> allow sub-LOD (-2)
bool settled = false; // true when traverse produced zero splits/merges/blocks
};
// ---------- OctreeClipmap ----------
// Manages the octree LOD hierarchy with distance-based split/merge and hysteresis.
class OctreeClipmap {
public:
// Configuration (set before initialize())
float base_voxel_size = 0.25f;
int voxels_per_cell = 32;
float lod_factor = 2.0f; // K: split if distance < cell_size * K
float hysteresis = 1.5f; // merge at K * hysteresis (wider gap prevents split-merge thrashing)
int max_lod_levels = 12;
int max_splits_per_frame = 4;
int max_merges_per_frame = 4;
int merge_cooldown_frames = 60;
bool content_aware_lod = false; // enable content-aware merge optimization
LodMode lod_mode = LOD_BLOCKING_SWAP;
// Screen-space error metric parameters
float screen_split_threshold = 1.0f; // split when error > N pixels
float screen_merge_threshold = 0.5f; // merge when error < N pixels
float viewport_height = 1080.0f; // updated from camera each frame
float camera_fov_rad = 1.0472f; // radians (60 degrees default)
bool use_screen_space_error = false; // disabled: causes split-merge thrashing at island boundaries
// Callback invoked on each node before it is freed during merge/clear.
// Use this to clean up external resources (RIDs, meshes, etc.).
using FreeCallback = void(*)(OctreeClipmapNode* node, void* userdata);
FreeCallback on_node_free = nullptr; // frees ALL resources (mesh + collision)
FreeCallback on_mesh_free = nullptr; // frees ONLY mesh, keeps collision alive
FreeCallback on_collision_free = nullptr; // frees ONLY collision body
void* on_node_free_userdata = nullptr;
// Camera direction for frustum-aware LOD (set by DCTerrain each frame)
float cam_forward[3] = {0.0f, 0.0f, -1.0f};
void initialize(); // create root node at root_center_
void traverse(const float cam_pos[3], uint32_t frame); // per-frame traversal
void recenter(const Vector3i& new_center, uint32_t frame); // full rebuild at new center (fallback)
void recenter_incremental(const Vector3i& new_center, uint32_t frame); // shift-and-transplant
Vector3i get_root_center() const { return root_center_; }
// Edit focus points: positions where terrain needs fine LOD regardless of camera.
// Each acts as a virtual camera for the split decision.
std::vector<std::array<float, 4>> edit_focus_points; // x, y, z, radius
// Adaptive architecture LOD (experimental, default OFF): nodes overlapping the edited-
// architecture AABB may refine to arch_min_lod (e.g. -1 = 2x) when near the camera —
// gated on lod0_settled + the normal distance split, capped at arch_min_lod. Set by
// DCTerrain. Off = zero behaviour change.
bool arch_lod_active = false;
int arch_min_lod = -1;
float arch_min[3] = {0.0f, 0.0f, 0.0f};
float arch_max[3] = {0.0f, 0.0f, 0.0f};
void invalidate_settled(); // force re-traverse (call when camera moves)
void check_stale_parents(); // free parent meshes when all children are ACTIVE
std::vector<OctreeClipmapNode*> get_leaves() const;
std::vector<OctreeClipmapNode*> get_stale_parents() const; // nodes with parent_mesh_stale
std::vector<OctreeClipmapNode*> drain_pending(); // get nodes needing generation
void mark_ready(OctreeClipmapNode* node);
void mark_active(OctreeClipmapNode* node);
void mark_pending(OctreeClipmapNode* node); // re-queue for generation
void requeue_pending(OctreeClipmapNode* node); // force re-enqueue (bypasses state guard) — for dispatch-failure recovery
const ClipmapStats& get_stats() const;
void clear();
OctreeNodePool& pool();
OctreeClipmapNode* get_root() const { return root_; }
// Find the leaf node containing a given voxel-space position.
// Returns nullptr if the position is outside the octree bounds.
OctreeClipmapNode* find_leaf_containing(int vx, int vy, int vz) const;
// Pre-mesh cache for BLOCKING_SWAP LOD transitions
PreMeshEntry* get_pre_mesh(uint64_t morton);
PreMeshEntry& ensure_pre_mesh(uint64_t morton);
void clear_pre_mesh_cache();
std::unordered_map<uint64_t, PreMeshEntry>& pre_mesh_cache_ref() { return pre_mesh_cache_; }
struct ChildInfo {
Vector3i position;
int lod_level;
uint64_t morton_code;
};
void compute_child_info(OctreeClipmapNode* parent, ChildInfo out[8]) const;
void split_node_from_cache(OctreeClipmapNode* node, uint32_t frame);
void merge_node_from_cache(OctreeClipmapNode* node, uint32_t frame);
private:
OctreeNodePool pool_;
OctreeClipmapNode* root_ = nullptr;
Vector3i root_center_ = Vector3i(0, 0, 0); // voxel-space anchor
std::unordered_map<uint64_t, PreMeshEntry> pre_mesh_cache_;
ClipmapStats stats_;
std::vector<OctreeClipmapNode*> pending_; // nodes that need generation
void _traverse_node(OctreeClipmapNode* node, const float cam_pos[3],
uint32_t frame, int& splits_rem, int& merges_rem);
float _distance_to_node(const float cam_pos[3], OctreeClipmapNode* node) const;
float _cell_size(int lod) const;
void _split_node(OctreeClipmapNode* node, uint32_t frame);
void _merge_node(OctreeClipmapNode* node, uint32_t frame);
void _collect_leaves(OctreeClipmapNode* node, std::vector<OctreeClipmapNode*>& out) const;
void _check_stale_recursive(OctreeClipmapNode* node);
bool _subtree_has_collision(OctreeClipmapNode* node);
void _free_subtree(OctreeClipmapNode* node);
};
#endif // DC_OCTREE_CLIPMAP_H