commit 5389b8e84a033951b807f53ec8d276e71bf25962
parent d5d860d7610ab1447e6cc0c769a186a4fd7a5949
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 26 Sep 2018 15:24:06 +0200
Do not submit invalid voxels to the [challenge_]merge functors
Diffstat:
3 files changed, 108 insertions(+), 77 deletions(-)
diff --git a/src/svx_tree_builder.h b/src/svx_tree_builder.h
@@ -169,6 +169,7 @@ XD(stack_setup_node)
const uint8_t ichild_flag = (uint8_t)BIT(ichild);
struct XD(node)* child = stack->nodes + ichild;
int igrandchild;
+ size_t ngrandchildren = 0; /* #active grand children */
d3_splat(child_low, -INF);
FOR_EACH(i, 0, TREE_DIMENSION) {
@@ -177,33 +178,41 @@ XD(stack_setup_node)
if(ichild & (NCHILDREN >> (1+i))) child_low[iaxis] += child_sz[iaxis];
}
+ if(!(stack->mask & ichild_flag)) continue; /* Empty child */
+
/* Fetch the grandchildren data */
FOR_EACH(igrandchild, 0, NCHILDREN) {
struct svx_voxel* vox = &voxels[igrandchild];
+ const uint8_t igrandchild_flag = (uint8_t)BIT(igrandchild);
+
+ if(!(child->is_valid & igrandchild_flag)) continue; /* Empty grandchild */
- voxels[igrandchild].data = child->data[igrandchild];
- voxels[igrandchild].depth = node_depth + 2;
- voxels[igrandchild].id = SIZE_MAX;
- voxels[igrandchild].is_leaf = (child->is_leaf & BIT(igrandchild))!=0;
- voxels[igrandchild].data = child->data[igrandchild];
- data[igrandchild] = child->data[igrandchild];
+ voxels[ngrandchildren].data = child->data[igrandchild];
+ voxels[ngrandchildren].depth = node_depth + 2;
+ voxels[ngrandchildren].id = SIZE_MAX;
+ voxels[ngrandchildren].is_leaf = (child->is_leaf & igrandchild_flag)!=0;
+ voxels[ngrandchildren].data = child->data[igrandchild];
+ data[ngrandchildren] = child->data[igrandchild];
d3_splat(vox->lower,-INF);
d3_splat(vox->upper, INF);
FOR_EACH(i, 0, TREE_DIMENSION) {
const int iaxis = frame[i];
+ vox->lower[iaxis] = child_low[iaxis];
if(igrandchild & (NCHILDREN >> (1+i))) {
vox->lower[iaxis] += grandchild_sz[iaxis];
}
vox->upper[iaxis] = vox->lower[iaxis] + grandchild_sz[iaxis];
}
+
+ ++ngrandchildren;
}
- desc->merge(node->data[ichild], data, NCHILDREN, desc->context);
+ desc->merge(node->data[ichild], data, ngrandchildren, desc->context);
if(child->is_leaf == (BIT(NCHILDREN)-1)/*all active bitmask*/
- && desc->challenge_merge(voxels, NCHILDREN, desc->context)) {
- /* The node becomes a leaf : the children does not exist anymore */
+ && desc->challenge_merge(voxels, ngrandchildren, desc->context)) {
+ /* The node becomes a leaf: the children does not exist anymore */
node->is_leaf |= ichild_flag;
stack->mask ^= ichild_flag;
}
@@ -366,6 +375,8 @@ XD(builder_init)
FOR_EACH(i, 0, TREE_DIMENSION) {
const int iaxis = frame[i];
+ bldr->lower[iaxis] = lower[iaxis];
+ bldr->upper[iaxis] = upper[iaxis];
bldr->voxsz[iaxis] = (upper[iaxis] - lower[iaxis]) / (double)definition;
}
@@ -373,7 +384,6 @@ exit:
return res;
error:
goto exit;
-
}
static res_T
@@ -490,6 +500,7 @@ XD(builder_finalize)
size_t nleaves;
int ilvl;
int ichild;
+ size_t nchildren;
res_T res = RES_OK;
ASSERT(bldr);
@@ -547,11 +558,16 @@ XD(builder_finalize)
bldr->nleaves += nleaves;
/* Setup the root attribs */
+ nchildren = 0;
ASSERT(bldr->stacks[ilvl].mask == 1); /* Only the root node is active */
FOR_EACH(ichild, 0, NCHILDREN) {
- data[ichild] = bldr->stacks[ilvl].nodes[0].data[ichild];
+ const int ichild_flag = BIT(ichild);
+ if(!(bldr->stacks[ilvl].nodes[0].is_valid & ichild_flag)) continue;
+
+ data[nchildren] = bldr->stacks[ilvl].nodes[0].data[ichild];
+ ++nchildren;
}
- bldr->desc->merge(root_data, data, NCHILDREN, bldr->desc->context);
+ bldr->desc->merge(root_data, data, nchildren, bldr->desc->context);
exit:
return res;
diff --git a/src/test_svx_bintree.c b/src/test_svx_bintree.c
@@ -146,6 +146,7 @@ get_aabb(const size_t xyz[3], void* dst, void* ctx)
aabb->lower[AXIS] =
(double)xyz[AXIS] * build_ctx->voxsz[AXIS] + build_ctx->lower[AXIS];
aabb->upper[AXIS] = aabb->lower[AXIS] + build_ctx->voxsz[AXIS];
+ aabb->depth = build_ctx->max_depth;
}
@@ -153,6 +154,7 @@ static void
merge_aabb(void* dst, const void* voxels[], const size_t nvoxels, void* ctx)
{
const struct build_context* build_ctx = ctx;
+ double upper[3];
double voxsz[3];
struct aabb* aabb = dst;
size_t depth = SIZE_MAX;
@@ -169,33 +171,30 @@ merge_aabb(void* dst, const void* voxels[], const size_t nvoxels, void* ctx)
const struct aabb* vox_aabb = voxels[i];
if(depth == SIZE_MAX) {
depth = vox_aabb->depth;
- } else if(vox_aabb->depth != 0) { /* Not invalid */
+ } else { /* Not invalid */
CHK(depth == vox_aabb->depth);
- aabb->lower[AXIS] = MMIN(vox_aabb->lower[AXIS], aabb->lower[AXIS]);
}
+ aabb->lower[AXIS] = MMIN(vox_aabb->lower[AXIS], aabb->lower[AXIS]);
+ aabb->upper[AXIS] = MMAX(vox_aabb->upper[AXIS], aabb->upper[AXIS]);
}
- if(depth == 0) { /* Invalid voxel */
- aabb->lower[AXIS] = 0;
- aabb->upper[AXIS] = 0;
- aabb->depth = 0;
- } else {
- double upper[3];
- CHK(build_ctx->max_depth >= depth);
- CHK(depth > 0);
- aabb->depth = depth - 1;
+ d3_splat(upper, INF);
+ d3_splat(voxsz, INF);
- i = build_ctx->max_depth - aabb->depth;
- voxsz[AXIS] = build_ctx->voxsz[AXIS] * (double)(1<<i);
+ CHK(build_ctx->max_depth >= depth);
+ CHK(depth > 0);
+ aabb->depth = depth - 1;
- /* Clamp voxel to grid size */
- upper[AXIS] = MMIN(aabb->lower[AXIS] + voxsz[AXIS], build_ctx->upper[AXIS]);
+ i = build_ctx->max_depth - aabb->depth;
+ voxsz[AXIS] = build_ctx->voxsz[AXIS] * (double)(1<<i);
- /* Adjust the voxel size from the clampd voxel */
- voxsz[AXIS] = upper[AXIS] - aabb->lower[AXIS];
+ /* Clamp voxel to grid size */
+ upper[AXIS] = MMIN(aabb->lower[AXIS] + voxsz[AXIS], build_ctx->upper[AXIS]);
- CHK(eq_eps(voxsz[AXIS], aabb->upper[AXIS] - aabb->lower[AXIS], 1.e-6));
- }
+ /* Adjust the voxel size from the clampd voxel */
+ voxsz[AXIS] = upper[AXIS] - aabb->lower[AXIS];
+
+ CHK(eq_eps(voxsz[AXIS], aabb->upper[AXIS] - aabb->lower[AXIS], 1.e-6));
}
static int
@@ -214,12 +213,22 @@ challenge_aabb(const struct svx_voxel voxels[], const size_t nvoxels, void* ctx)
if(depth == SIZE_MAX) {
depth = aabb->depth;
- } else if(aabb->depth != 0) { /* Not invalid */
+ } else { /* Not invalid */
CHK(depth == aabb->depth);
- CHK(depth == voxels[i].depth);
- voxsz[AXIS] = build_ctx->voxsz[AXIS] * (double)(1<<n);
- CHK(eq_eps(voxsz[AXIS], aabb->upper[AXIS] - aabb->lower[AXIS], 1.e-6));
}
+ CHK(depth == voxels[i].depth);
+ CHK(eq_eps(aabb->lower[AXIS], voxels[i].lower[AXIS], 1.e-6));
+ CHK(eq_eps(aabb->upper[AXIS], voxels[i].upper[AXIS], 1.e-6));
+ CHK(aabb->lower[(AXIS+1)%3] == voxels[i].lower[(AXIS+1)%3]);
+ CHK(aabb->lower[(AXIS+2)%3] == voxels[i].lower[(AXIS+2)%3]);
+ CHK(aabb->lower[(AXIS+1)%3] == -INF);
+ CHK(aabb->lower[(AXIS+2)%3] == -INF);
+ CHK(aabb->upper[(AXIS+1)%3] == voxels[i].upper[(AXIS+1)%3]);
+ CHK(aabb->upper[(AXIS+2)%3] == voxels[i].upper[(AXIS+2)%3]);
+ CHK(aabb->upper[(AXIS+1)%3] == INF);
+ CHK(aabb->upper[(AXIS+2)%3] == INF);
+ voxsz[AXIS] = build_ctx->voxsz[AXIS] * (double)(1<<n);
+ CHK(eq_eps(voxsz[AXIS], aabb->upper[AXIS] - aabb->lower[AXIS], 1.e-6));
}
return 1;
}
@@ -373,6 +382,15 @@ main(int argc, char** argv)
test_at_accessor(tree, nvxls);
CHK(svx_tree_ref_put(tree) == RES_OK);
+ build_ctx.max_depth = (size_t)log2i((int)round_up_pow2(nvxls));
+
+ d3_splat(build_ctx.lower,-INF);
+ d3_splat(build_ctx.upper, INF);
+ d3_splat(build_ctx.voxsz, INF);
+ build_ctx.lower[AXIS] = low;;
+ build_ctx.upper[AXIS] = upp;
+ build_ctx.voxsz[AXIS] = (upp-low)/(double)nvxls;
+
vox_desc.get = get_aabb;
vox_desc.merge = merge_aabb;
vox_desc.challenge_merge = challenge_aabb;
diff --git a/src/test_svx_octree.c b/src/test_svx_octree.c
@@ -208,6 +208,7 @@ static void
merge_aabb(void* dst, const void* voxels[], const size_t nvoxels, void* ctx)
{
const struct build_context* build_ctx = ctx;
+ double upper[3];
double voxsz[3];
struct aabb* aabb = dst;
size_t depth = SIZE_MAX;
@@ -222,44 +223,39 @@ merge_aabb(void* dst, const void* voxels[], const size_t nvoxels, void* ctx)
const struct aabb* vox_aabb = voxels[i];
if(depth == SIZE_MAX) {
depth = vox_aabb->depth;
- } else if(vox_aabb->depth != 0) { /* Not invalid */
+ } else {
CHK(depth == vox_aabb->depth);
- aabb->lower[0] = MMIN(vox_aabb->lower[0], aabb->lower[0]);
- aabb->lower[1] = MMIN(vox_aabb->lower[1], aabb->lower[1]);
- aabb->lower[2] = MMIN(vox_aabb->lower[2], aabb->lower[2]);
- aabb->upper[0] = MMAX(vox_aabb->upper[0], aabb->upper[0]);
- aabb->upper[1] = MMAX(vox_aabb->upper[1], aabb->upper[1]);
- aabb->upper[2] = MMAX(vox_aabb->upper[2], aabb->upper[2]);
}
+ aabb->lower[0] = MMIN(vox_aabb->lower[0], aabb->lower[0]);
+ aabb->lower[1] = MMIN(vox_aabb->lower[1], aabb->lower[1]);
+ aabb->lower[2] = MMIN(vox_aabb->lower[2], aabb->lower[2]);
+ aabb->upper[0] = MMAX(vox_aabb->upper[0], aabb->upper[0]);
+ aabb->upper[1] = MMAX(vox_aabb->upper[1], aabb->upper[1]);
+ aabb->upper[2] = MMAX(vox_aabb->upper[2], aabb->upper[2]);
}
- if(depth == 0) { /* Invalid voxel */
- memset(aabb, 0, sizeof(*aabb));
- } else {
- double upper[3];
- CHK(build_ctx->max_depth >= depth);
- CHK(depth > 0);
- aabb->depth = depth - 1;
-
- i = build_ctx->max_depth - aabb->depth;
- voxsz[0] = build_ctx->voxsz[0] * (double)(1<<i);
- voxsz[1] = build_ctx->voxsz[1] * (double)(1<<i);
- voxsz[2] = build_ctx->voxsz[2] * (double)(1<<i);
-
- /* Clamp voxel to grid size */
- upper[0] = MMIN(aabb->lower[0] + voxsz[0], build_ctx->upper[0]);
- upper[1] = MMIN(aabb->lower[1] + voxsz[1], build_ctx->upper[1]);
- upper[2] = MMIN(aabb->lower[2] + voxsz[2], build_ctx->upper[2]);
-
- /* Adjust the voxel size from the clampd voxel */
- voxsz[0] = upper[0] - aabb->lower[0];
- voxsz[1] = upper[1] - aabb->lower[1];
- voxsz[2] = upper[2] - aabb->lower[2];
+ CHK(build_ctx->max_depth >= depth);
+ CHK(depth > 0);
+ aabb->depth = depth - 1;
- CHK(eq_eps(voxsz[0], aabb->upper[0] - aabb->lower[0], 1.e-6));
- CHK(eq_eps(voxsz[1], aabb->upper[1] - aabb->lower[1], 1.e-6));
- CHK(eq_eps(voxsz[2], aabb->upper[2] - aabb->lower[2], 1.e-6));
- }
+ i = build_ctx->max_depth - aabb->depth;
+ voxsz[0] = build_ctx->voxsz[0] * (double)(1<<i);
+ voxsz[1] = build_ctx->voxsz[1] * (double)(1<<i);
+ voxsz[2] = build_ctx->voxsz[2] * (double)(1<<i);
+
+ /* Clamp voxel to grid size */
+ upper[0] = MMIN(aabb->lower[0] + voxsz[0], build_ctx->upper[0]);
+ upper[1] = MMIN(aabb->lower[1] + voxsz[1], build_ctx->upper[1]);
+ upper[2] = MMIN(aabb->lower[2] + voxsz[2], build_ctx->upper[2]);
+
+ /* Adjust the voxel size from the clampd voxel */
+ voxsz[0] = upper[0] - aabb->lower[0];
+ voxsz[1] = upper[1] - aabb->lower[1];
+ voxsz[2] = upper[2] - aabb->lower[2];
+
+ CHK(eq_eps(voxsz[0], aabb->upper[0] - aabb->lower[0], 1.e-6));
+ CHK(eq_eps(voxsz[1], aabb->upper[1] - aabb->lower[1], 1.e-6));
+ CHK(eq_eps(voxsz[2], aabb->upper[2] - aabb->lower[2], 1.e-6));
}
static int
@@ -278,17 +274,18 @@ challenge_aabb(const struct svx_voxel voxels[], const size_t nvoxels, void* ctx)
if(depth == SIZE_MAX) {
depth = aabb->depth;
- } else if(aabb->depth != 0) { /* Not invalid */
+ } else {
CHK(depth == aabb->depth);
- CHK(depth == voxels[i].depth);
-
- voxsz[0] = build_ctx->voxsz[0] * (double)(1<<n);
- voxsz[1] = build_ctx->voxsz[1] * (double)(1<<n);
- voxsz[2] = build_ctx->voxsz[2] * (double)(1<<n);
- CHK(eq_eps(voxsz[0], aabb->upper[0] - aabb->lower[0], 1.e-6));
- CHK(eq_eps(voxsz[1], aabb->upper[1] - aabb->lower[1], 1.e-6));
- CHK(eq_eps(voxsz[2], aabb->upper[2] - aabb->lower[2], 1.e-6));
}
+ CHK(depth == voxels[i].depth);
+ CHK(d3_eq_eps(aabb->lower, voxels[i].lower, 1.e-6));
+ CHK(d3_eq_eps(aabb->upper, voxels[i].upper, 1.e-6));
+ voxsz[0] = build_ctx->voxsz[0] * (double)(1<<n);
+ voxsz[1] = build_ctx->voxsz[1] * (double)(1<<n);
+ voxsz[2] = build_ctx->voxsz[2] * (double)(1<<n);
+ CHK(eq_eps(voxsz[0], aabb->upper[0] - aabb->lower[0], 1.e-6));
+ CHK(eq_eps(voxsz[1], aabb->upper[1] - aabb->lower[1], 1.e-6));
+ CHK(eq_eps(voxsz[2], aabb->upper[2] - aabb->lower[2], 1.e-6));
}
return 1;
