#include "dc_seam.h"
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <cstring>
// ---------------------------------------------------------------------------
// Contour constants (same as leven/contour_constants.h and dc_contour.cpp)
// ---------------------------------------------------------------------------
static const int CHILD_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},
};
// Edge vertex map: 12 edges, each connecting 2 of 8 corners
static const int seam_edgevmap[12][2] = {
{0,4},{1,5},{2,6},{3,7}, // x-axis
{0,2},{1,3},{4,6},{5,7}, // y-axis
{0,1},{2,3},{4,5},{6,7}, // z-axis
};
static const int seam_cellProcFaceMask[12][3] = {
{0,4,0},{1,5,0},{2,6,0},{3,7,0},
{0,2,1},{4,6,1},{1,3,1},{5,7,1},
{0,1,2},{2,3,2},{4,5,2},{6,7,2},
};
static const int seam_cellProcEdgeMask[6][5] = {
{0,1,2,3,0},{4,5,6,7,0},
{0,4,1,5,1},{2,6,3,7,1},
{0,2,4,6,2},{1,3,5,7,2},
};
static const int seam_faceProcFaceMask[3][4][3] = {
{{4,0,0},{5,1,0},{6,2,0},{7,3,0}},
{{2,0,1},{6,4,1},{3,1,1},{7,5,1}},
{{1,0,2},{3,2,2},{5,4,2},{7,6,2}},
};
static const int seam_faceProcEdgeMask[3][4][6] = {
{{1,4,0,5,1,1},{1,6,2,7,3,1},{0,4,6,0,2,2},{0,5,7,1,3,2}},
{{0,2,3,0,1,0},{0,6,7,4,5,0},{1,2,0,6,4,2},{1,3,1,7,5,2}},
{{1,1,0,3,2,0},{1,5,4,7,6,0},{0,1,5,0,4,1},{0,3,7,2,6,1}},
};
static const int seam_edgeProcEdgeMask[3][2][5] = {
{{3,2,1,0,0},{7,6,5,4,0}},
{{5,1,4,0,1},{7,3,6,2,1}},
{{6,4,2,0,2},{7,5,3,1,2}},
};
static const int seam_processEdgeMask[3][4] = {
{3,2,1,0}, {7,5,6,4}, {11,10,9,8},
};
// ---------------------------------------------------------------------------
// AABB helper
// ---------------------------------------------------------------------------
static inline bool point_in_aabb(const int p[3], const int aabb_min[3], int aabb_size) {
return p[0] >= aabb_min[0] && p[0] < aabb_min[0] + aabb_size &&
p[1] >= aabb_min[1] && p[1] < aabb_min[1] + aabb_size &&
p[2] >= aabb_min[2] && p[2] < aabb_min[2] + aabb_size;
}
// ---------------------------------------------------------------------------
// Hash for spatial parent lookup
// ---------------------------------------------------------------------------
static inline uint64_t hash_min(int x, int y, int z) {
// Pack coordinates into 64 bits (20 bits each, signed offset)
uint64_t ux = static_cast<uint64_t>(x + (1 << 19)) & 0xFFFFF;
uint64_t uy = static_cast<uint64_t>(y + (1 << 19)) & 0xFFFFF;
uint64_t uz = static_cast<uint64_t>(z + (1 << 19)) & 0xFFFFF;
return ux | (uy << 20) | (uz << 40);
}
// ---------------------------------------------------------------------------
// Chunk boundary helper for preventing overlapping seam triangles
// ---------------------------------------------------------------------------
// Determine which "chunk" (cell) a position belongs to given a cell size.
// Used to prevent contouring across cells that belong to the same chunk.
static inline void chunk_min_for_pos(const int pos[3], int cell_size,
int out[3]) {
for (int i = 0; i < 3; i++) {
out[i] = (pos[i] < 0)
? ((pos[i] - cell_size + 1) / cell_size) * cell_size
: (pos[i] / cell_size) * cell_size;
}
}
static inline bool ivec3_eq(const int a[3], const int b[3]) {
return a[0] == b[0] && a[1] == b[1] && a[2] == b[2];
}
// ---------------------------------------------------------------------------
// FilterSeamNode (ported from leven clipmap.cpp)
// ---------------------------------------------------------------------------
bool seam_filter_node(int child_index,
const int seam_bounds[3],
const int node_min[3],
const int node_max[3]) {
switch (child_index) {
case 0:
return node_max[0] == seam_bounds[0] ||
node_max[1] == seam_bounds[1] ||
node_max[2] == seam_bounds[2];
case 1:
return node_min[2] == seam_bounds[2];
case 2:
return node_min[1] == seam_bounds[1];
case 3:
return node_min[1] == seam_bounds[1] ||
node_min[2] == seam_bounds[2];
case 4:
return node_min[0] == seam_bounds[0];
case 5:
return node_min[0] == seam_bounds[0] ||
node_min[2] == seam_bounds[2];
case 6:
return node_min[0] == seam_bounds[0] ||
node_min[1] == seam_bounds[1];
case 7:
return node_min[0] == seam_bounds[0] &&
node_min[1] == seam_bounds[1] &&
node_min[2] == seam_bounds[2];
}
return false;
}
// ---------------------------------------------------------------------------
// SelectSeamNodes (ported from leven clipmap.cpp)
// ---------------------------------------------------------------------------
void seam_select_nodes(
const int host_min[3],
int host_size,
int neighbor_size,
int neighbor_index,
const SeamNodeInfo* seam_nodes,
int num_seam_nodes,
int voxels_per_cell,
SeamOctreeArena& arena,
std::vector<SeamOctreeNode*>& out)
{
int seam_bounds[3] = {
host_min[0] + host_size,
host_min[1] + host_size,
host_min[2] + host_size,
};
// AABB for filtering: 2x host size centered on host_min
int aabb_min[3] = { host_min[0], host_min[1], host_min[2] };
int aabb_size = host_size * 2;
// Seam node size in voxel units
int node_size = neighbor_size / voxels_per_cell;
for (int j = 0; j < num_seam_nodes; j++) {
const SeamNodeInfo& info = seam_nodes[j];
// Compute world-space min from local_min (voxel grid coords)
// The neighbor's seam nodes have local_min in grid coordinates.
// We need to convert to world voxel coordinates.
// In the leven reference: seamNode->min = ivec3(info.localspaceMin) * seamNodeSize + neighborMin
// But our SeamNodeInfo.local_min is already the voxel-space grid position.
// The caller stores it as the absolute voxel position.
int nmin[3] = {
info.local_min.x,
info.local_min.y,
info.local_min.z,
};
int nmax[3] = {
nmin[0] + node_size,
nmin[1] + node_size,
nmin[2] + node_size,
};
if (!seam_filter_node(neighbor_index, seam_bounds, nmin, nmax))
continue;
if (!point_in_aabb(nmin, aabb_min, aabb_size))
continue;
// Create a seam octree leaf node from this SeamNodeInfo
SeamOctreeNode* leaf = arena.alloc();
leaf->type = SeamOctreeNode::LEAF;
leaf->min[0] = nmin[0];
leaf->min[1] = nmin[1];
leaf->min[2] = nmin[2];
leaf->size = node_size;
leaf->position[0] = info.position[0];
leaf->position[1] = info.position[1];
leaf->position[2] = info.position[2];
leaf->normal[0] = info.normal[0];
leaf->normal[1] = info.normal[1];
leaf->normal[2] = info.normal[2];
leaf->corner_signs = info.corner_signs;
out.push_back(leaf);
}
}
// ---------------------------------------------------------------------------
// ConstructParents (ported from leven octree.cpp)
// ---------------------------------------------------------------------------
static std::vector<SeamOctreeNode*> construct_parents(
SeamOctreeArena& arena,
const std::vector<SeamOctreeNode*>& nodes,
int parent_size,
const int root_min[3])
{
std::unordered_map<uint64_t, SeamOctreeNode*> parent_map;
for (auto* node : nodes) {
// Calculate parent position: snap to parent grid
int local[3] = {
node->min[0] - root_min[0],
node->min[1] - root_min[1],
node->min[2] - root_min[2],
};
int parent_pos[3];
for (int i = 0; i < 3; i++) {
// Modulo for signed: local % parent_size
int rem = local[i] % parent_size;
if (rem < 0) rem += parent_size;
parent_pos[i] = node->min[i] - rem;
}
uint64_t key = hash_min(parent_pos[0] - root_min[0],
parent_pos[1] - root_min[1],
parent_pos[2] - root_min[2]);
SeamOctreeNode* parent = nullptr;
auto it = parent_map.find(key);
if (it == parent_map.end()) {
parent = arena.alloc();
parent->type = SeamOctreeNode::INTERNAL;
parent->min[0] = parent_pos[0];
parent->min[1] = parent_pos[1];
parent->min[2] = parent_pos[2];
parent->size = parent_size;
parent_map[key] = parent;
} else {
parent = it->second;
}
// Find which child slot this node occupies
int half = parent_size / 2;
bool found = false;
for (int i = 0; i < 8; i++) {
int child_pos[3] = {
parent_pos[0] + CHILD_OFFSETS[i][0] * half,
parent_pos[1] + CHILD_OFFSETS[i][1] * half,
parent_pos[2] + CHILD_OFFSETS[i][2] * half,
};
if (child_pos[0] == node->min[0] &&
child_pos[1] == node->min[1] &&
child_pos[2] == node->min[2]) {
parent->children[i] = node;
found = true;
break;
}
}
(void)found; // assert(found) in debug
}
std::vector<SeamOctreeNode*> parents;
parents.reserve(parent_map.size());
for (auto& [key, parent] : parent_map) {
parents.push_back(parent);
}
return parents;
}
// ---------------------------------------------------------------------------
// Octree_ConstructUpwards (ported from leven octree.cpp)
// ---------------------------------------------------------------------------
SeamOctreeNode* seam_construct_upwards(
SeamOctreeArena& arena,
const std::vector<SeamOctreeNode*>& input_nodes,
const int root_min[3],
int root_size)
{
if (input_nodes.empty())
return nullptr;
// Copy and sort by size (ascending) to handle mixed-size seam nodes
std::vector<SeamOctreeNode*> nodes(input_nodes);
std::sort(nodes.begin(), nodes.end(),
[](const SeamOctreeNode* a, const SeamOctreeNode* b) {
return a->size < b->size;
});
// Process nodes in stages: group by size, construct parents,
// merge with remaining larger nodes, repeat
while (nodes.front()->size != nodes.back()->size) {
auto it = nodes.begin();
int sz = (*it)->size;
while (it != nodes.end() && (*it)->size == sz) ++it;
std::vector<SeamOctreeNode*> run(nodes.begin(), it);
run = construct_parents(arena, run, sz * 2, root_min);
// Remaining nodes + new parents
run.insert(run.end(), it, nodes.end());
std::swap(nodes, run);
// Re-sort by size
std::sort(nodes.begin(), nodes.end(),
[](const SeamOctreeNode* a, const SeamOctreeNode* b) {
return a->size < b->size;
});
}
// Now all nodes have the same size — construct parents until root
int parent_size = nodes.front()->size * 2;
while (parent_size <= root_size) {
nodes = construct_parents(arena, nodes, parent_size, root_min);
parent_size *= 2;
}
if (nodes.size() != 1)
return nullptr; // should not happen with valid input
return nodes.front();
}
// ---------------------------------------------------------------------------
// Vertex index assignment for seam octree
// ---------------------------------------------------------------------------
static void seam_assign_vertex_indices(SeamOctreeNode* node, DCMeshData& mesh) {
if (!node) return;
bool has_children = false;
for (int i = 0; i < 8; i++) {
if (node->children[i]) { has_children = true; break; }
}
if (has_children) {
for (int i = 0; i < 8; i++)
seam_assign_vertex_indices(node->children[i], mesh);
} else if (node->type == SeamOctreeNode::LEAF) {
node->vertex_index = static_cast<int>(mesh.positions.size() / 3);
mesh.positions.push_back(node->position[0]);
mesh.positions.push_back(node->position[1]);
mesh.positions.push_back(node->position[2]);
mesh.normals.push_back(node->normal[0]);
mesh.normals.push_back(node->normal[1]);
mesh.normals.push_back(node->normal[2]);
}
}
// ---------------------------------------------------------------------------
// DC contouring on the seam octree (ported from leven octree.cpp)
// ---------------------------------------------------------------------------
// Forward declarations
static void seam_contour_face(SeamOctreeNode* node[2], int dir,
int cell_size, DCMeshData& mesh);
static void seam_contour_edge(SeamOctreeNode* node[4], int dir,
int cell_size, DCMeshData& mesh);
static void seam_contour_process_edge(SeamOctreeNode* node[4], int dir,
DCMeshData& mesh) {
int min_size = INT_MAX;
int min_index = 0;
int indices[4] = {-1, -1, -1, -1};
bool flip = false;
bool sign_change[4] = {};
for (int i = 0; i < 4; i++) {
if (!node[i] || node[i]->type == SeamOctreeNode::INTERNAL)
continue;
int edge = seam_processEdgeMask[dir][i];
int c0 = seam_edgevmap[edge][0];
int c1 = seam_edgevmap[edge][1];
int corners = node[i]->corner_signs & 0xFF;
int m0 = (corners >> c0) & 1;
int m1 = (corners >> c1) & 1;
if (node[i]->size < min_size) {
min_size = node[i]->size;
min_index = i;
flip = m1 != 1;
}
indices[i] = node[i]->vertex_index;
sign_change[i] = (m0 != m1);
}
if (!sign_change[min_index])
return;
// Bug fix: skip if any vertex index is invalid (-1 from missing/non-leaf nodes)
if (indices[0] < 0 || indices[1] < 0 || indices[2] < 0 || indices[3] < 0)
return;
if (!flip) {
mesh.indices.push_back(indices[0]);
mesh.indices.push_back(indices[1]);
mesh.indices.push_back(indices[3]);
mesh.indices.push_back(indices[0]);
mesh.indices.push_back(indices[3]);
mesh.indices.push_back(indices[2]);
} else {
mesh.indices.push_back(indices[0]);
mesh.indices.push_back(indices[3]);
mesh.indices.push_back(indices[1]);
mesh.indices.push_back(indices[0]);
mesh.indices.push_back(indices[2]);
mesh.indices.push_back(indices[3]);
}
}
static void seam_contour_edge(SeamOctreeNode* node[4], int dir,
int cell_size, DCMeshData& mesh) {
if (!node[0] || !node[1] || !node[2] || !node[3])
return;
// Prevent overlapping seams: only process edges spanning multiple cells.
// Count distinct chunk origins among the 4 nodes.
int chunks[4][3];
for (int i = 0; i < 4; i++)
chunk_min_for_pos(node[i]->min, cell_size, chunks[i]);
bool all_same = true;
for (int i = 1; i < 4; i++) {
if (!ivec3_eq(chunks[i], chunks[0])) { all_same = false; break; }
}
if (all_same)
return;
bool is_branch[4];
for (int i = 0; i < 4; i++)
is_branch[i] = (node[i]->type == SeamOctreeNode::INTERNAL);
if (!is_branch[0] && !is_branch[1] && !is_branch[2] && !is_branch[3]) {
seam_contour_process_edge(node, dir, mesh);
} else {
for (int i = 0; i < 2; i++) {
SeamOctreeNode* edge_nodes[4];
int c[4] = {
seam_edgeProcEdgeMask[dir][i][0],
seam_edgeProcEdgeMask[dir][i][1],
seam_edgeProcEdgeMask[dir][i][2],
seam_edgeProcEdgeMask[dir][i][3],
};
for (int j = 0; j < 4; j++) {
if (!is_branch[j])
edge_nodes[j] = node[j];
else
edge_nodes[j] = node[j]->children[c[j]];
}
seam_contour_edge(edge_nodes,
seam_edgeProcEdgeMask[dir][i][4],
cell_size, mesh);
}
}
}
static void seam_contour_face(SeamOctreeNode* node[2], int dir,
int cell_size, DCMeshData& mesh) {
if (!node[0] || !node[1])
return;
// Prevent overlapping seams
int c0[3], c1[3];
chunk_min_for_pos(node[0]->min, cell_size, c0);
chunk_min_for_pos(node[1]->min, cell_size, c1);
if (ivec3_eq(c0, c1))
return;
bool is_branch[2] = {
node[0]->type == SeamOctreeNode::INTERNAL,
node[1]->type == SeamOctreeNode::INTERNAL,
};
if (is_branch[0] || is_branch[1]) {
for (int i = 0; i < 4; i++) {
SeamOctreeNode* face_nodes[2];
int c[2] = {
seam_faceProcFaceMask[dir][i][0],
seam_faceProcFaceMask[dir][i][1],
};
for (int j = 0; j < 2; j++) {
if (!is_branch[j])
face_nodes[j] = node[j];
else
face_nodes[j] = node[j]->children[c[j]];
}
seam_contour_face(face_nodes, seam_faceProcFaceMask[dir][i][2],
cell_size, mesh);
}
const int orders[2][4] = {
{0, 0, 1, 1},
{0, 1, 0, 1},
};
for (int i = 0; i < 4; i++) {
SeamOctreeNode* edge_nodes[4];
int c[4] = {
seam_faceProcEdgeMask[dir][i][1],
seam_faceProcEdgeMask[dir][i][2],
seam_faceProcEdgeMask[dir][i][3],
seam_faceProcEdgeMask[dir][i][4],
};
const int* order = orders[seam_faceProcEdgeMask[dir][i][0]];
for (int j = 0; j < 4; j++) {
if (!is_branch[order[j]])
edge_nodes[j] = node[order[j]];
else
edge_nodes[j] = node[order[j]]->children[c[j]];
}
seam_contour_edge(edge_nodes,
seam_faceProcEdgeMask[dir][i][5],
cell_size, mesh);
}
}
}
static void seam_contour_cell(SeamOctreeNode* node, int cell_size,
DCMeshData& mesh) {
if (!node || node->type == SeamOctreeNode::LEAF)
return;
for (int i = 0; i < 8; i++)
seam_contour_cell(node->children[i], cell_size, mesh);
for (int i = 0; i < 12; i++) {
SeamOctreeNode* face_nodes[2] = {
node->children[seam_cellProcFaceMask[i][0]],
node->children[seam_cellProcFaceMask[i][1]],
};
seam_contour_face(face_nodes, seam_cellProcFaceMask[i][2],
cell_size, mesh);
}
for (int i = 0; i < 6; i++) {
SeamOctreeNode* edge_nodes[4] = {
node->children[seam_cellProcEdgeMask[i][0]],
node->children[seam_cellProcEdgeMask[i][1]],
node->children[seam_cellProcEdgeMask[i][2]],
node->children[seam_cellProcEdgeMask[i][3]],
};
seam_contour_edge(edge_nodes, seam_cellProcEdgeMask[i][4],
cell_size, mesh);
}
}
// ---------------------------------------------------------------------------
// seam_generate_mesh
// ---------------------------------------------------------------------------
void seam_generate_mesh(
SeamOctreeNode* root,
const int host_min[3],
int host_size,
DCMeshData& out_mesh)
{
if (!root)
return;
out_mesh.positions.clear();
out_mesh.normals.clear();
out_mesh.indices.clear();
seam_assign_vertex_indices(root, out_mesh);
seam_contour_cell(root, host_size, out_mesh);
}
// ---------------------------------------------------------------------------
// seam_generate_for_cell (high-level API)
// ---------------------------------------------------------------------------
void seam_generate_for_cell(
const int host_min[3],
int host_size,
int voxels_per_cell,
const std::vector<SeamNeighborInfo>& neighbors,
DCMeshData& out_mesh)
{
out_mesh.positions.clear();
out_mesh.normals.clear();
out_mesh.indices.clear();
SeamOctreeArena arena;
std::vector<SeamOctreeNode*> seam_leaves;
seam_leaves.reserve(2048);
for (int i = 0; i < 8 && i < static_cast<int>(neighbors.size()); i++) {
const auto& n = neighbors[i];
if (!n.seam_nodes || n.num_seam_nodes == 0 || n.cell_size == 0)
continue;
seam_select_nodes(host_min, host_size, n.cell_size, i,
n.seam_nodes, n.num_seam_nodes,
voxels_per_cell, arena, seam_leaves);
}
if (seam_leaves.empty())
return;
// Root size must accommodate the largest neighbor's seam nodes.
// A coarser neighbor (e.g. LOD 3 vs host LOD 0) has larger nodes
// that may extend beyond 2 * host_size.
int max_neighbor_size = host_size;
for (int i = 0; i < 8 && i < static_cast<int>(neighbors.size()); i++) {
if (neighbors[i].cell_size > max_neighbor_size)
max_neighbor_size = neighbors[i].cell_size;
}
int root_min[3] = { host_min[0], host_min[1], host_min[2] };
int root_size = std::max(host_size * 2, max_neighbor_size * 2);
// Round up to power of 2 (required for octree structure)
int rs = 1;
while (rs < root_size) rs *= 2;
root_size = rs;
SeamOctreeNode* root = seam_construct_upwards(arena, seam_leaves,
root_min, root_size);
if (!root)
return;
seam_generate_mesh(root, host_min, host_size, out_mesh);
}