// Standalone octree clipmap tests -- no Godot required.
// Build:
// g++ -std=c++17 -O2 -I src test/test_octree_clipmap.cpp -o test/test_octree_clipmap
#include "dc_octree_clipmap.h"
#include <cstdio>
#include <cassert>
#include <cmath>
#include <set>
static int tests_passed = 0;
static int tests_failed = 0;
#define TEST(name) \
static void test_##name(); \
struct Register_##name { Register_##name() { test_##name(); } } reg_##name; \
static void test_##name()
#define CHECK(cond, msg) do { \
if (!(cond)) { \
printf(" FAIL: %s (line %d)\n", msg, __LINE__); \
tests_failed++; \
} else { \
tests_passed++; \
} \
} while(0)
// ---------- Test 1: Node creation and is_leaf ----------
TEST(node_creation_and_is_leaf) {
printf("Test: node creation and is_leaf\n");
OctreeClipmapNode node;
node.reset();
CHECK(node.is_leaf(), "fresh node should be leaf");
CHECK(node.state == OctreeClipmapNode::EMPTY, "fresh node state should be EMPTY");
CHECK(node.lod_level == 0, "fresh node lod should be 0");
CHECK(node.triangle_count == 0, "fresh node triangle count should be 0");
CHECK(node.parent == nullptr, "fresh node parent should be null");
CHECK(node.seam_nodes == nullptr, "fresh node seam_nodes should be null");
CHECK(node.num_seam_nodes == 0, "fresh node num_seam_nodes should be 0");
CHECK(node.active_voxel_count == 0, "fresh node active_voxel_count should be 0");
// Set position and verify
node.position = Vector3i(10, 20, 30);
CHECK(node.position.x == 10, "position.x should be 10");
CHECK(node.position.y == 20, "position.y should be 20");
CHECK(node.position.z == 30, "position.z should be 30");
// After reset, position should be zeroed
node.reset();
CHECK(node.position.x == 0, "reset position.x should be 0");
printf(" passed\n");
}
// ---------- Test 2: Pool allocator ----------
TEST(pool_allocator) {
printf("Test: pool allocator\n");
OctreeNodePool pool;
CHECK(pool.allocated_count() == 0, "empty pool should have 0 allocated");
// Allocate some nodes
OctreeClipmapNode* a = pool.allocate();
OctreeClipmapNode* b = pool.allocate();
OctreeClipmapNode* c = pool.allocate();
CHECK(pool.allocated_count() == 3, "should have 3 allocated");
CHECK(a != b, "allocations should be distinct");
CHECK(b != c, "allocations should be distinct");
CHECK(a != c, "allocations should be distinct");
// Allocated nodes should be reset
CHECK(a->is_leaf(), "allocated node should be leaf");
CHECK(a->state == OctreeClipmapNode::EMPTY, "allocated node should be EMPTY");
// Free one and re-allocate — should recycle
pool.free(b);
CHECK(pool.allocated_count() == 2, "should have 2 after freeing one");
OctreeClipmapNode* d = pool.allocate();
CHECK(pool.allocated_count() == 3, "should have 3 after re-allocating");
CHECK(d == b, "should recycle freed node");
CHECK(d->is_leaf(), "recycled node should be reset to leaf");
printf(" passed\n");
}
// ---------- Test 3: Pool allocator bulk + block boundaries ----------
TEST(pool_bulk_allocation) {
printf("Test: pool bulk allocation across blocks\n");
OctreeNodePool pool;
const int N = 2500; // spans multiple blocks of 1024
std::set<OctreeClipmapNode*> ptrs;
for (int i = 0; i < N; i++) {
OctreeClipmapNode* n = pool.allocate();
ptrs.insert(n);
}
CHECK(pool.allocated_count() == N, "should have N allocated");
CHECK((int)ptrs.size() == N, "all pointers should be unique");
// Free all
for (auto* p : ptrs) pool.free(p);
CHECK(pool.allocated_count() == 0, "should have 0 after freeing all");
// Re-allocate — all from free list
for (int i = 0; i < N; i++) pool.allocate();
CHECK(pool.allocated_count() == N, "should recycle all N nodes");
printf(" passed\n");
}
// ---------- Test 4: Child management — split parent into 8 children ----------
TEST(child_management) {
printf("Test: child management\n");
OctreeNodePool pool;
OctreeClipmapNode* parent = pool.allocate();
parent->position = Vector3i(0, 0, 0);
parent->lod_level = 2;
parent->state = OctreeClipmapNode::ACTIVE;
CHECK(parent->is_leaf(), "parent should start as leaf");
// Split into 8 children
int child_size = 16; // arbitrary
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(
parent->position.x + cx * child_size,
parent->position.y + cy * child_size,
parent->position.z + cz * child_size
);
child->lod_level = parent->lod_level - 1;
child->parent = parent;
parent->children[i] = child;
}
CHECK(!parent->is_leaf(), "parent with children should not be leaf");
CHECK(pool.allocated_count() == 9, "should have 9 nodes (1 parent + 8 children)");
// Verify child positions
CHECK(parent->children[0]->position == Vector3i(0, 0, 0), "child 0 position");
CHECK(parent->children[7]->position == Vector3i(child_size, child_size, child_size), "child 7 position");
CHECK(parent->children[5]->position == Vector3i(child_size, 0, child_size), "child 5 position");
// Verify child LOD and parent pointers
for (int i = 0; i < 8; i++) {
CHECK(parent->children[i]->lod_level == 1, "child lod should be parent-1");
CHECK(parent->children[i]->parent == parent, "child parent should point to parent");
CHECK(parent->children[i]->is_leaf(), "children should be leaves");
}
printf(" passed\n");
}
// ---------- Test 5: cell_world_size calculation ----------
TEST(cell_world_size_calc) {
printf("Test: cell_world_size calculation\n");
float base = 0.5f;
int voxels = 32;
// LOD 0: 0.5 * 1 * 32 = 16.0
float s0 = cell_world_size(0, base, voxels);
CHECK(s0 == 16.0f, "LOD 0 should be 16.0");
// LOD 1: 0.5 * 2 * 32 = 32.0
float s1 = cell_world_size(1, base, voxels);
CHECK(s1 == 32.0f, "LOD 1 should be 32.0");
// LOD 2: 0.5 * 4 * 32 = 64.0
float s2 = cell_world_size(2, base, voxels);
CHECK(s2 == 64.0f, "LOD 2 should be 64.0");
// LOD 5: 0.5 * 32 * 32 = 512.0
float s5 = cell_world_size(5, base, voxels);
CHECK(s5 == 512.0f, "LOD 5 should be 512.0");
// Different base/voxels: base=1.0, voxels=16, LOD 3 => 1.0 * 8 * 16 = 128.0
float s3 = cell_world_size(3, 1.0f, 16);
CHECK(s3 == 128.0f, "base=1, voxels=16, LOD 3 should be 128.0");
printf(" passed\n");
}
// ---------- Test 6: morton_encode uniqueness ----------
TEST(morton_encode_uniqueness) {
printf("Test: morton_encode uniqueness\n");
// Basic: different coords produce different codes
uint64_t m000 = morton_encode(0, 0, 0, 0);
uint64_t m100 = morton_encode(1, 0, 0, 0);
uint64_t m010 = morton_encode(0, 1, 0, 0);
uint64_t m001 = morton_encode(0, 0, 1, 0);
CHECK(m000 != m100, "different x should differ");
CHECK(m000 != m010, "different y should differ");
CHECK(m000 != m001, "different z should differ");
CHECK(m100 != m010, "x=1 vs y=1 should differ");
// Same coords, different LOD should differ
uint64_t m_lod0 = morton_encode(5, 3, 7, 0);
uint64_t m_lod1 = morton_encode(5, 3, 7, 1);
CHECK(m_lod0 != m_lod1, "same coords different LOD should differ");
// Brute-force uniqueness over a small range
std::set<uint64_t> codes;
int collisions = 0;
for (int x = 0; x < 8; x++)
for (int y = 0; y < 8; y++)
for (int z = 0; z < 8; z++) {
uint64_t code = morton_encode(x, y, z, 0);
if (!codes.insert(code).second) collisions++;
}
CHECK(collisions == 0, "no collisions in 8x8x8 range");
CHECK((int)codes.size() == 512, "should have 512 unique codes");
// Verify interleave pattern: morton(1,0,0) should set bit 0 of x channel
// x goes to bits 0,3,6,... y goes to bits 1,4,7,... z goes to bits 2,5,8,...
uint64_t m1 = morton_encode(1, 0, 0, 0);
CHECK((m1 & 0x1) == 1, "x=1 should set bit 0");
uint64_t m2 = morton_encode(0, 1, 0, 0);
CHECK((m2 & 0x2) == 2, "y=1 should set bit 1");
uint64_t m3 = morton_encode(0, 0, 1, 0);
CHECK((m3 & 0x4) == 4, "z=1 should set bit 2");
printf(" passed\n");
}
// ---------- Test 7: SeamNodeInfo basics ----------
TEST(seam_node_info) {
printf("Test: SeamNodeInfo basics\n");
SeamNodeInfo info;
info.local_min = Vector3i(5, 10, 15);
info.position[0] = 1.0f;
info.position[1] = 2.0f;
info.position[2] = 3.0f;
info.normal[0] = 0.0f;
info.normal[1] = 1.0f;
info.normal[2] = 0.0f;
info.corner_signs = 0b10101010;
info.material_id = 42;
CHECK(info.local_min.x == 5, "local_min.x");
CHECK(info.local_min.y == 10, "local_min.y");
CHECK(info.position[1] == 2.0f, "position[1]");
CHECK(info.normal[1] == 1.0f, "normal[1]");
CHECK(info.corner_signs == 0xAA, "corner_signs");
CHECK(info.material_id == 42, "material_id");
printf(" passed\n");
}
// ---------- Test 8: Basic traversal produces LOD 0 near camera ----------
TEST(traversal_lod0_near_camera) {
printf("Test: traversal produces LOD 0 near camera\n");
OctreeClipmap clipmap;
clipmap.base_voxel_size = 0.25f;
clipmap.voxels_per_cell = 32;
clipmap.lod_factor = 2.0f;
clipmap.hysteresis = 1.2f;
clipmap.max_lod_levels = 6;
clipmap.max_splits_per_frame = 64; // generous budget
clipmap.merge_cooldown_frames = 60;
clipmap.initialize();
// Camera at origin, run enough frames for full refinement
float cam[3] = {0.0f, 0.0f, 0.0f};
for (uint32_t f = 0; f < 20; f++) {
clipmap.traverse(cam, f);
// Drain and mark all pending as active so splits can continue
auto pending = clipmap.drain_pending();
for (auto* n : pending) {
clipmap.mark_ready(n);
clipmap.mark_active(n);
}
}
auto leaves = clipmap.get_leaves();
CHECK(!leaves.empty(), "should have leaves after traversal");
// Find minimum LOD among leaves
int min_lod = 999;
for (auto* leaf : leaves) {
if (leaf->lod_level < min_lod) min_lod = leaf->lod_level;
}
CHECK(min_lod == 0, "should have LOD 0 leaves near camera");
// Verify LOD 0 leaves exist near camera (small world position)
bool found_lod0_near = false;
for (auto* leaf : leaves) {
if (leaf->lod_level == 0) {
float wx = leaf->position.x * clipmap.base_voxel_size;
float wy = leaf->position.y * clipmap.base_voxel_size;
float wz = leaf->position.z * clipmap.base_voxel_size;
float dist = std::fabs(wx) + std::fabs(wy) + std::fabs(wz);
if (dist < 50.0f) found_lod0_near = true;
}
}
CHECK(found_lod0_near, "LOD 0 leaves should exist near origin");
clipmap.clear();
printf(" passed\n");
}
// ---------- Test 9: Hysteresis prevents thrashing ----------
TEST(hysteresis_prevents_thrashing) {
printf("Test: hysteresis prevents thrashing\n");
OctreeClipmap clipmap;
clipmap.base_voxel_size = 0.25f;
clipmap.voxels_per_cell = 32;
clipmap.lod_factor = 2.0f;
clipmap.hysteresis = 1.2f;
clipmap.max_lod_levels = 4;
clipmap.max_splits_per_frame = 64;
clipmap.max_merges_per_frame = 64;
clipmap.merge_cooldown_frames = 0; // disable cooldown for this test
clipmap.initialize();
// First, let it converge with camera at origin
float cam[3] = {0.0f, 0.0f, 0.0f};
for (uint32_t f = 0; f < 30; f++) {
clipmap.traverse(cam, f);
auto pending = clipmap.drain_pending();
for (auto* n : pending) {
clipmap.mark_ready(n);
clipmap.mark_active(n);
}
}
int leaf_count_converged = (int)clipmap.get_leaves().size();
// Now oscillate camera ±2m around split boundary and count total splits/merges
// The split boundary for LOD 1 cell (size=16) is at distance 32 (cell_size * K)
// Hysteresis merge boundary is at 38.4 (32 * 1.2)
// Oscillating ±2m should stay within the hysteresis band and not cause changes
int splits_during_oscillation = 0;
int merges_during_oscillation = 0;
for (uint32_t f = 30; f < 50; f++) {
// Oscillate around the split boundary
float offset = (f % 2 == 0) ? 2.0f : -2.0f;
cam[0] = 34.0f + offset; // between 32 and 36.4, within hysteresis band
clipmap.traverse(cam, f);
splits_during_oscillation += clipmap.get_stats().splits_this_frame;
merges_during_oscillation += clipmap.get_stats().merges_this_frame;
auto pending = clipmap.drain_pending();
for (auto* n : pending) {
clipmap.mark_ready(n);
clipmap.mark_active(n);
}
}
// After initial convergence, oscillation within hysteresis band
// should cause very few additional changes
CHECK(splits_during_oscillation + merges_during_oscillation < 10,
"hysteresis should prevent excessive split/merge thrashing");
clipmap.clear();
printf(" passed\n");
}
// ---------- Test 10: Frame budget limits splits ----------
TEST(frame_budget_limits_splits) {
printf("Test: frame budget limits splits\n");
OctreeClipmap clipmap;
clipmap.base_voxel_size = 0.25f;
clipmap.voxels_per_cell = 32;
clipmap.lod_factor = 2.0f;
clipmap.max_lod_levels = 8;
clipmap.max_splits_per_frame = 4;
clipmap.initialize();
float cam[3] = {0.0f, 0.0f, 0.0f};
// Run several frames and verify split budget is respected each frame
for (uint32_t f = 0; f < 10; f++) {
clipmap.traverse(cam, f);
CHECK(clipmap.get_stats().splits_this_frame <= 4,
"splits per frame should not exceed budget");
auto pending = clipmap.drain_pending();
for (auto* n : pending) {
clipmap.mark_ready(n);
clipmap.mark_active(n);
}
}
// Verify that splits DID happen (total should be > 0 after several frames)
CHECK(clipmap.get_stats().total_splits > 0, "should have performed some splits");
clipmap.clear();
printf(" passed\n");
}
// ---------- Test 11: Merge works when camera moves far away ----------
TEST(merge_when_camera_far) {
printf("Test: merge works when camera moves far away\n");
OctreeClipmap clipmap;
clipmap.base_voxel_size = 0.25f;
clipmap.voxels_per_cell = 32;
clipmap.lod_factor = 2.0f;
clipmap.hysteresis = 1.2f;
clipmap.max_lod_levels = 4;
clipmap.max_splits_per_frame = 64;
clipmap.max_merges_per_frame = 64;
clipmap.merge_cooldown_frames = 0; // disable cooldown for test
clipmap.initialize();
// Camera at origin -- let it fully split
float cam[3] = {0.0f, 0.0f, 0.0f};
for (uint32_t f = 0; f < 20; f++) {
clipmap.traverse(cam, f);
auto pending = clipmap.drain_pending();
for (auto* n : pending) {
clipmap.mark_ready(n);
clipmap.mark_active(n);
}
}
int leaves_near = (int)clipmap.get_leaves().size();
CHECK(leaves_near > 1, "should have multiple leaves when camera is near");
// Move camera very far away -- should trigger merges
cam[0] = 100000.0f;
cam[1] = 100000.0f;
cam[2] = 100000.0f;
for (uint32_t f = 20; f < 40; f++) {
clipmap.traverse(cam, f);
auto pending = clipmap.drain_pending();
for (auto* n : pending) {
clipmap.mark_ready(n);
clipmap.mark_active(n);
}
}
int leaves_far = (int)clipmap.get_leaves().size();
CHECK(leaves_far < leaves_near, "should have fewer leaves when camera is far away");
CHECK(clipmap.get_stats().total_merges > 0, "should have performed merges");
clipmap.clear();
printf(" passed\n");
}
// ---------- Test 12: find_leaf_containing ----------
TEST(find_leaf_containing) {
printf("Test: find_leaf_containing\n");
OctreeClipmap clipmap;
clipmap.base_voxel_size = 0.25f;
clipmap.voxels_per_cell = 32;
clipmap.lod_factor = 2.0f;
clipmap.hysteresis = 1.2f;
clipmap.max_lod_levels = 4;
clipmap.max_splits_per_frame = 64;
clipmap.initialize();
// Let it converge with camera at origin
float cam[3] = {0.0f, 0.0f, 0.0f};
for (uint32_t f = 0; f < 20; f++) {
clipmap.traverse(cam, f);
auto pending = clipmap.drain_pending();
for (auto* n : pending) {
clipmap.mark_ready(n);
clipmap.mark_active(n);
}
}
// Find leaf at origin — should return LOD 0 leaf
auto* leaf0 = clipmap.find_leaf_containing(0, 0, 0);
CHECK(leaf0 != nullptr, "should find leaf at origin");
CHECK(leaf0->is_leaf(), "result should be a leaf");
CHECK(leaf0->lod_level == 0, "leaf at origin should be LOD 0");
// Find leaf at a position inside the octree but further out
int root_span = (1 << 3) * 32; // max_lod_levels-1 = 3, so root is LOD 3
auto* leaf_far = clipmap.find_leaf_containing(root_span / 2, root_span / 2, root_span / 2);
CHECK(leaf_far != nullptr, "should find leaf in octree interior");
CHECK(leaf_far->is_leaf(), "far result should be a leaf");
// Position outside octree bounds should return nullptr
auto* outside = clipmap.find_leaf_containing(root_span + 100, 0, 0);
CHECK(outside == nullptr, "position outside octree should return nullptr");
// Negative position should return nullptr
auto* neg = clipmap.find_leaf_containing(-10, 0, 0);
CHECK(neg == nullptr, "negative position should return nullptr");
clipmap.clear();
printf(" passed\n");
}
// ---------- main ----------
int main() {
printf("=== OctreeClipmapNode Tests ===\n\n");
// Tests run via static registration above
printf("\n=== Results: %d passed, %d failed ===\n", tests_passed, tests_failed);
return tests_failed > 0 ? 1 : 0;
}