// Standalone octree tests -- no Godot required.
// Build:
// g++ -std=c++17 -O2 -I src test/test_octree.cpp src/dc_octree.cpp src/dc_qef.cpp -o test/test_octree -lm
#include "dc_octree.h"
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
// ---------- density functions ----------
static float density_all_air(float, float, float, void*) {
return -1.0f;
}
static float density_all_solid(float, float, float, void*) {
return 1.0f;
}
// Plane at y=0: solid below (positive), air above (negative).
static float density_plane_y0(float, float y, float, void*) {
return -y;
}
// Sphere with given radius and center.
struct SphereParams { float radius; float cx, cy, cz; };
static float density_sphere(float x, float y, float z, void* ud) {
SphereParams* p = (SphereParams*)ud;
float dx = x - p->cx, dy = y - p->cy, dz = z - p->cz;
return p->radius - sqrtf(dx * dx + dy * dy + dz * dz);
}
// ---------- test helpers ----------
static int tests_run = 0;
static int tests_passed = 0;
#define TEST(name) \
do { \
tests_run++; \
printf(" %-40s ", name); \
} while (0)
#define PASS() \
do { \
tests_passed++; \
printf("PASS\n"); \
} while (0)
#define FAIL(msg) \
do { \
printf("FAIL: %s\n", msg); \
} while (0)
// ---------- tests ----------
static void test_all_air() {
TEST("all air returns nullptr");
int min[3] = {0, 0, 0};
float origin[3] = {0, 0, 0};
OctreeNode* root = construct_octree(min, 32, 1.0f, origin, density_all_air, nullptr);
if (root == nullptr) { PASS(); }
else { FAIL("expected nullptr"); destroy_octree(root); }
}
static void test_all_solid() {
TEST("all solid returns nullptr");
int min[3] = {0, 0, 0};
float origin[3] = {0, 0, 0};
OctreeNode* root = construct_octree(min, 32, 1.0f, origin, density_all_solid, nullptr);
if (root == nullptr) { PASS(); }
else { FAIL("expected nullptr"); destroy_octree(root); }
}
static void test_plane_y0() {
TEST("plane y=0 has leaves near y=0");
// Octree from (-16,-16,-16) to (16,16,16) in world space.
int min[3] = {0, 0, 0};
float origin[3] = {-16.0f, -16.0f, -16.0f};
OctreeNode* root = construct_octree(min, 32, 1.0f, origin, density_plane_y0, nullptr);
if (!root) { FAIL("expected non-null root"); return; }
int leaves = count_leaves(root);
// The plane at y=0 should create leaves. With 32^3 voxels, we expect
// a strip of leaves at y=16 (where world y=0). Should be roughly 32*32 = 1024
// but pruning reduces this. Just check > 0 and < total voxels.
if (leaves > 0 && leaves < 32 * 32 * 32) { PASS(); }
else { char buf[64]; snprintf(buf, sizeof(buf), "leaf count = %d", leaves); FAIL(buf); }
destroy_octree(root);
}
static void test_sphere() {
TEST("sphere has reasonable leaf count");
// Sphere radius 8 centred at (5,5,5) in a [0..32] world-space grid.
// Off-centre placement ensures root corners have mixed signs:
// corner (0,0,0) dist=8.66 > 8 (outside), corner (32,32,32) dist=46.8 (outside)
// but corner (0,0,0) is close, and subdivided children will find the surface.
// Actually: place sphere so one root corner is inside.
// Centre (8,8,8), radius 10: corner (0,0,0) dist=13.9 > 10, corner (32,0,0) dist=25.6.
// Use centre (0,0,0), radius 20: corner (0,0,0) dist=0 (inside!), corner (32,32,32) dist=55.4 (outside).
SphereParams sp = { 20.0f, 0.0f, 0.0f, 0.0f };
int min[3] = {0, 0, 0};
float origin[3] = {0.0f, 0.0f, 0.0f};
OctreeNode* root = construct_octree(min, 32, 1.0f, origin, density_sphere, &sp);
if (!root) { FAIL("expected non-null root"); return; }
int leaves = count_leaves(root);
// Sphere surface intersects the grid. Expect a reasonable number of leaves.
if (leaves > 50 && leaves < 32 * 32 * 32) { PASS(); }
else { char buf[64]; snprintf(buf, sizeof(buf), "leaf count = %d", leaves); FAIL(buf); }
destroy_octree(root);
}
static void test_leaf_corners_mixed() {
TEST("leaf corners are mixed (not 0x00/0xFF)");
int min[3] = {0, 0, 0};
float origin[3] = {-16.0f, -16.0f, -16.0f};
OctreeNode* root = construct_octree(min, 32, 1.0f, origin, density_plane_y0, nullptr);
if (!root) { FAIL("expected non-null root"); return; }
// Walk tree and check all leaves.
struct Walker {
bool all_mixed;
static void walk(const OctreeNode* n, Walker* w) {
if (!n) return;
if (n->type == OctreeNode::LEAF) {
if (n->corners == 0x00 || n->corners == 0xFF) {
w->all_mixed = false;
}
}
for (int i = 0; i < 8; i++) walk(n->children[i], w);
}
};
Walker w = { true };
Walker::walk(root, &w);
if (w.all_mixed) { PASS(); }
else { FAIL("found leaf with uniform corners"); }
destroy_octree(root);
}
static void test_destroy_no_crash() {
TEST("destroy nullptr no crash");
destroy_octree(nullptr);
PASS();
}
static void test_destroy_tree_no_crash() {
TEST("destroy constructed tree no crash");
SphereParams sp = { 20.0f, 0.0f, 0.0f, 0.0f };
int min[3] = {0, 0, 0};
float origin[3] = {0.0f, 0.0f, 0.0f};
OctreeNode* root = construct_octree(min, 32, 1.0f, origin, density_sphere, &sp);
destroy_octree(root);
PASS();
}
static void test_small_octree_size2() {
TEST("size=2 octree exact structure");
// Plane at y=0, origin at (-1,-1,-1), size=2, scale=1.
// Voxel corners span [(-1,-1,-1) to (1,1,1)].
// y=0 plane: solid where y<0, air where y>0.
int min[3] = {0, 0, 0};
float origin[3] = {-1.0f, -1.0f, -1.0f};
OctreeNode* root = construct_octree(min, 2, 1.0f, origin, density_plane_y0, nullptr);
if (!root) { FAIL("expected non-null root"); return; }
// Root should be INTERNAL with size=2.
if (root->type != OctreeNode::INTERNAL) { FAIL("root not INTERNAL"); destroy_octree(root); return; }
if (root->size != 2) { FAIL("root size != 2"); destroy_octree(root); return; }
// Count children: some should be leaves (sign change), some nullptr (uniform).
int leaf_count = 0;
int null_count = 0;
for (int i = 0; i < 8; i++) {
if (!root->children[i]) null_count++;
else if (root->children[i]->type == OctreeNode::LEAF) leaf_count++;
}
int total_leaves = count_leaves(root);
// With plane at y=0, children touching y=0 have sign changes.
// Expect some leaves and some nulls.
if (leaf_count > 0 && null_count > 0 && total_leaves == leaf_count) { PASS(); }
else {
char buf[128];
snprintf(buf, sizeof(buf), "leaves=%d nulls=%d total=%d", leaf_count, null_count, total_leaves);
FAIL(buf);
}
destroy_octree(root);
}
static void test_node_defaults() {
TEST("leaf node defaults (vertex_index, position)");
int min[3] = {0, 0, 0};
float origin[3] = {-1.0f, -1.0f, -1.0f};
OctreeNode* root = construct_octree(min, 2, 1.0f, origin, density_plane_y0, nullptr);
if (!root) { FAIL("expected non-null root"); return; }
// Find first leaf and check defaults.
struct Finder {
const OctreeNode* found;
static void find(const OctreeNode* n, Finder* f) {
if (!n || f->found) return;
if (n->type == OctreeNode::LEAF) { f->found = n; return; }
for (int i = 0; i < 8; i++) find(n->children[i], f);
}
};
Finder f = { nullptr };
Finder::find(root, &f);
if (!f.found) { FAIL("no leaf found"); destroy_octree(root); return; }
bool ok = (f.found->vertex_index == -1) &&
(f.found->position[0] == 0.0f) &&
(f.found->position[1] == 0.0f) &&
(f.found->position[2] == 0.0f);
if (ok) { PASS(); }
else { FAIL("leaf defaults not as expected"); }
destroy_octree(root);
}
// ---------- main ----------
int main() {
printf("=== Octree Tests ===\n");
test_all_air();
test_all_solid();
test_plane_y0();
test_sphere();
test_leaf_corners_mixed();
test_destroy_no_crash();
test_destroy_tree_no_crash();
test_small_octree_size2();
test_node_defaults();
printf("\n%d/%d tests passed.\n", tests_passed, tests_run);
return (tests_passed == tests_run) ? 0 : 1;
}