dc-terrain / libdc / include / dc_octree.h

#ifndef DC_OCTREE_H
#define DC_OCTREE_H

// Octree construction for Dual Contouring.
// Pure C++ -- no Godot dependencies.
//
// Recursively subdivides a 3D density field, pruning uniform regions
// (all solid or all air). Only leaf nodes at sign-change boundaries
// survive -- these are where the isosurface passes through.
//
// Child ordering matches Nick Gildea's DC implementation:
//   0:(0,0,0)  1:(0,0,1)  2:(0,1,0)  3:(0,1,1)
//   4:(1,0,0)  5:(1,0,1)  6:(1,1,0)  7:(1,1,1)

#include "dc_qef.h"
#include "dc_density_grid.h"
#include "dc_pool.h"
#include <cstdint>

struct OctreeNode {
    enum Type : uint8_t { NONE, INTERNAL, LEAF, PSEUDO };
    Type type = NONE;
    int min[3];           // voxel-space minimum corner
    int size;             // side length in voxels
    OctreeNode* children[8] = {};

    // Leaf/Pseudo data (filled by contouring, not construction)
    int vertex_index = -1;
    float position[3] = {};
    float average_normal[3] = {};
    uint8_t corners = 0;           // bitmask: bit i = 1 if corner i is inside (positive density)
    uint8_t corner_materials = 0;  // bitmask: bit i = 1 if corner i is inside a box edit
    float corner_densities[8] = {}; // cached density values at each corner
    QEFData qef;
};

// Density callback: evaluates density at world position (x,y,z).
// Positive = solid, negative = air.
typedef float (*DensityFunc)(float x, float y, float z, void* userdata);

// Pack voxel coordinates into a uint64 key for hash maps.
// Supports coords in [-2^20, 2^20) range.
inline uint64_t pack_voxel_key(int x, int y, int z) {
    uint64_t ux = static_cast<uint64_t>(x + (1 << 20)) & 0x1FFFFF;
    uint64_t uy = static_cast<uint64_t>(y + (1 << 20)) & 0x1FFFFF;
    uint64_t uz = static_cast<uint64_t>(z + (1 << 20)) & 0x1FFFFF;
    return (ux << 42) | (uy << 21) | uz;
}

// Unified offsets for both child subdivision and corner sampling.
// Nick Gildea ordering: x-bit=4, y-bit=2, z-bit=1.
//   i=0:(0,0,0)  i=1:(0,0,1)  i=2:(0,1,0)  i=3:(0,1,1)
//   i=4:(1,0,0)  i=5:(1,0,1)  i=6:(1,1,0)  i=7:(1,1,1)
// Bit extraction: x = (i>>2)&1, y = (i>>1)&1, z = i&1
inline constexpr int CHILD_MIN_OFFSETS[8][3] = {
    {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1},
    {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}
};

// Build an octree over the density field.
//   min[3]      - voxel-space minimum corner of the root
//   size        - side length in voxels (must be power of 2)
//   voxel_scale - world units per voxel
//   origin[3]   - world position of voxel (0,0,0)
//   density_fn  - density callback
//   userdata    - passed through to density_fn
OctreeNode* construct_octree(
    int min[3], int size,
    float voxel_scale,
    float origin[3],
    DensityFunc density_fn,
    void* userdata
);

// Build an octree using direct grid lookups (no hash map overhead).
// Grid must cover the same voxel-space domain as the octree.
OctreeNode* construct_octree_grid(
    int min[3], int size,
    const DensityGrid& grid
);

// Build an octree using pool allocation (better cache locality, no per-node alloc).
// Pool owns all nodes — do NOT call destroy_octree on the result.
OctreeNode* construct_octree_grid_pooled(
    int min[3], int size,
    const DensityGrid& grid,
    Pool<OctreeNode>& pool
);

// Recursively free all nodes in the tree.
void destroy_octree(OctreeNode* node);

// Count all LEAF nodes in the tree.
int count_leaves(const OctreeNode* node);

#endif // DC_OCTREE_H