test_svx_bintree.c (11828B)
1 /* Copyright (C) 2018, 2020-2025 |Méso|Star> (contact@meso-star.com) 2 * Copyright (C) 2018 Université Paul Sabatier 3 * 4 * This program is free software: you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation, either version 3 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program. If not, see <http://www.gnu.org/licenses/>. */ 16 17 #include "svx.h" 18 19 #include "test_svx_utils.h" 20 #include <rsys/math.h> 21 22 #define AXIS SVX_AXIS_Y 23 24 struct leaves_context { 25 double lower; 26 double upper; 27 size_t nvoxels; 28 size_t depth; 29 enum svx_axis axis; 30 31 char* leaves; 32 size_t nleaves; 33 }; 34 35 struct at_context { 36 double position; 37 size_t depth; 38 }; 39 40 struct aabb { 41 double lower[3]; 42 double upper[3]; 43 size_t depth; 44 }; 45 46 struct build_context { 47 double voxsz[3]; 48 double lower[3]; 49 double upper[3]; 50 size_t max_depth; 51 }; 52 53 54 static void 55 get(const size_t xyz[3], const uint64_t mcode, void* dst, void* ctx) 56 { 57 double* val = dst; 58 CHK(xyz != NULL); 59 CHK(val != NULL); 60 CHK((intptr_t)ctx == 0xDECAFBAD); 61 CHK(mcode == xyz[AXIS]); 62 *val = (double)xyz[AXIS]; 63 } 64 65 static int 66 no_merge(const struct svx_voxel voxels[], const size_t nvoxels, void* ctx) 67 { 68 CHK(voxels != NULL); 69 CHK(nvoxels != 0); 70 CHK((intptr_t)ctx == 0xDECAFBAD); 71 return 0; /* Merge nothing */ 72 } 73 74 static void 75 keep_max(void* dst, const void* voxels[], const size_t nvoxels, void* ctx) 76 { 77 double* vox_dst = dst; 78 double max_val = -DBL_MAX; 79 size_t i; 80 81 CHK(dst != NULL); 82 CHK(voxels != NULL); 83 CHK(nvoxels != 0); 84 CHK(ctx != NULL); 85 86 FOR_EACH(i, 0, nvoxels) { 87 const double* val = voxels[i]; 88 max_val = MMAX(max_val, *val); 89 } 90 *vox_dst = max_val; 91 } 92 93 static int 94 max_lod 95 (const struct svx_voxel* vox, 96 const double pos[3], 97 void* context) 98 { 99 const struct at_context* ctx = context; 100 CHK(vox != NULL); 101 CHK(pos != NULL); 102 CHK(ctx != NULL); 103 CHK(vox->depth <= ctx->depth); 104 CHK(pos[AXIS] == ctx->position); 105 return vox->depth < ctx->depth; 106 } 107 108 static void 109 check_leaves 110 (const struct svx_voxel* leaf, 111 const size_t ileaf, 112 void* context) 113 { 114 const double* dbl = NULL; 115 struct leaves_context* ctx = context; 116 double delta; 117 double lower; 118 119 CHK(leaf != NULL); 120 CHK(leaf->data != NULL); 121 CHK(ctx != NULL); 122 CHK(leaf->lower[ctx->axis] < leaf->upper[ctx->axis]); 123 CHK(ileaf < ctx->nvoxels); 124 125 dbl = leaf->data; 126 CHK(*dbl >= 0); 127 128 delta = (ctx->upper - ctx->lower) / (double)ctx->nvoxels; 129 lower = *dbl * delta; 130 131 CHK(eq_eps(lower, leaf->lower[ctx->axis], 1.e-6)); 132 CHK(eq_eps(lower+delta, leaf->upper[ctx->axis], 1.e-6)); 133 134 CHK(leaf->depth == ctx->depth - 1); 135 CHK(ctx->leaves[ileaf] == 0); 136 ctx->leaves[ileaf] = 1; 137 ctx->nleaves += 1; 138 } 139 140 static void 141 get_aabb(const size_t xyz[3], const uint64_t mcode, void* dst, void* ctx) 142 { 143 const struct build_context* build_ctx = ctx; 144 struct aabb* aabb = dst; 145 146 CHK(mcode == xyz[AXIS]); 147 d3_splat(aabb->lower,-INF); 148 d3_splat(aabb->upper, INF); 149 aabb->lower[AXIS] = 150 (double)xyz[AXIS] * build_ctx->voxsz[AXIS] + build_ctx->lower[AXIS]; 151 aabb->upper[AXIS] = aabb->lower[AXIS] + build_ctx->voxsz[AXIS]; 152 aabb->depth = build_ctx->max_depth; 153 } 154 155 156 static void 157 merge_aabb(void* dst, const void* voxels[], const size_t nvoxels, void* ctx) 158 { 159 const struct build_context* build_ctx = ctx; 160 double upper[3]; 161 double voxsz[3]; 162 struct aabb* aabb = dst; 163 size_t depth = SIZE_MAX; 164 size_t i; 165 CHK(dst && voxels && nvoxels && ctx); 166 167 d3_splat(aabb->lower,-INF); 168 d3_splat(aabb->upper, INF); 169 aabb->depth = 0; 170 aabb->lower[AXIS] = DBL_MAX; 171 aabb->upper[AXIS] =-DBL_MAX; 172 173 FOR_EACH(i, 0, nvoxels) { 174 const struct aabb* vox_aabb = voxels[i]; 175 if(depth == SIZE_MAX) { 176 depth = vox_aabb->depth; 177 } else { /* Not invalid */ 178 CHK(depth == vox_aabb->depth); 179 } 180 aabb->lower[AXIS] = MMIN(vox_aabb->lower[AXIS], aabb->lower[AXIS]); 181 aabb->upper[AXIS] = MMAX(vox_aabb->upper[AXIS], aabb->upper[AXIS]); 182 } 183 184 d3_splat(upper, INF); 185 d3_splat(voxsz, INF); 186 187 CHK(build_ctx->max_depth >= depth); 188 CHK(depth > 0); 189 aabb->depth = depth - 1; 190 191 i = build_ctx->max_depth - aabb->depth; 192 voxsz[AXIS] = build_ctx->voxsz[AXIS] * (double)(1<<i); 193 194 /* Clamp voxel to grid size */ 195 upper[AXIS] = MMIN(aabb->lower[AXIS] + voxsz[AXIS], build_ctx->upper[AXIS]); 196 197 /* Adjust the voxel size from the clampd voxel */ 198 voxsz[AXIS] = upper[AXIS] - aabb->lower[AXIS]; 199 200 CHK(eq_eps(voxsz[AXIS], aabb->upper[AXIS] - aabb->lower[AXIS], 1.e-6)); 201 } 202 203 static int 204 challenge_aabb(const struct svx_voxel voxels[], const size_t nvoxels, void* ctx) 205 { 206 const struct build_context* build_ctx = ctx; 207 size_t depth = SIZE_MAX; 208 size_t i; 209 CHK(voxels && nvoxels && ctx); 210 211 FOR_EACH(i, 0, nvoxels) { 212 double voxsz[3]; 213 const struct aabb* aabb = voxels[i].data; 214 const size_t n = build_ctx->max_depth - aabb->depth; 215 CHK(build_ctx->max_depth >= aabb->depth); 216 217 if(depth == SIZE_MAX) { 218 depth = aabb->depth; 219 } else { /* Not invalid */ 220 CHK(depth == aabb->depth); 221 } 222 CHK(depth == voxels[i].depth); 223 CHK(eq_eps(aabb->lower[AXIS], voxels[i].lower[AXIS], 1.e-6)); 224 CHK(eq_eps(aabb->upper[AXIS], voxels[i].upper[AXIS], 1.e-6)); 225 CHK(aabb->lower[(AXIS+1)%3] == voxels[i].lower[(AXIS+1)%3]); 226 CHK(aabb->lower[(AXIS+2)%3] == voxels[i].lower[(AXIS+2)%3]); 227 CHK(aabb->lower[(AXIS+1)%3] == -INF); 228 CHK(aabb->lower[(AXIS+2)%3] == -INF); 229 CHK(aabb->upper[(AXIS+1)%3] == voxels[i].upper[(AXIS+1)%3]); 230 CHK(aabb->upper[(AXIS+2)%3] == voxels[i].upper[(AXIS+2)%3]); 231 CHK(aabb->upper[(AXIS+1)%3] == INF); 232 CHK(aabb->upper[(AXIS+2)%3] == INF); 233 voxsz[AXIS] = build_ctx->voxsz[AXIS] * (double)(1<<n); 234 CHK(eq_eps(voxsz[AXIS], aabb->upper[AXIS] - aabb->lower[AXIS], 1.e-6)); 235 } 236 return 1; 237 } 238 239 static void 240 test_at_accessor(struct svx_tree* tree, const size_t nvoxels) 241 { 242 struct svx_tree_desc desc; 243 struct at_context ctx; 244 size_t nvxls; 245 double tree_sz; 246 double delta; 247 enum svx_axis axis; 248 249 CHK(svx_tree_get_desc(tree, &desc) == RES_OK); 250 CHK(desc.type == SVX_BINTREE); 251 CHK(desc.frame[0] == AXIS); 252 253 axis = desc.frame[0]; 254 tree_sz = desc.upper[axis] - desc.lower[axis]; 255 delta = tree_sz / (double)nvoxels; 256 257 ctx.depth = desc.depth; 258 CHK(ctx.depth > 0); 259 260 nvxls = nvoxels; 261 262 /* TODO Comment this */ 263 while(ctx.depth-- != 0) { 264 double pos[3] = {0, 0, 0}; 265 const size_t iter = desc.depth - ctx.depth - 1; 266 size_t i; 267 268 FOR_EACH(i, 0, nvxls) { 269 struct svx_voxel vox; 270 const double low = desc.lower[axis] + (double)i * delta; 271 const double upp = low + delta; 272 size_t mcode; 273 274 pos[axis] = desc.lower[axis] + ((double)i+1.0/(1u<<(2+iter)))*delta; 275 276 ctx.position = pos[axis]; 277 CHK(svx_tree_at(tree, pos, max_lod, &ctx, &vox) == RES_OK); 278 279 mcode = i * (size_t)(1u<<iter) + ((1u << iter) - 1); 280 mcode = MMIN(mcode, nvoxels-1); 281 282 CHK(*((double*)vox.data) == mcode); 283 CHK(vox.is_leaf == (desc.depth-1 == ctx.depth)); 284 CHK(vox.depth == ctx.depth); 285 CHK(eq_eps(vox.lower[axis], low, 1.e-6)); 286 CHK(eq_eps(vox.upper[axis], upp, 1.e-6)); 287 } 288 289 nvxls = nvxls == 1 ? 0 : (nvxls + 1/*ceil*/)/2; 290 delta = MMIN(delta * 2, tree_sz); 291 } 292 CHK(nvxls == 0); 293 } 294 295 int 296 main(int argc, char** argv) 297 { 298 struct svx_device* dev = NULL; 299 struct svx_tree* tree = NULL; 300 struct mem_allocator allocator; 301 struct svx_voxel_desc vox_desc = SVX_VOXEL_DESC_NULL; 302 struct svx_tree_desc tree_desc = SVX_TREE_DESC_NULL; 303 struct build_context build_ctx; 304 struct leaves_context ctx; 305 enum svx_axis axis; 306 double low, upp; 307 size_t nvxls; 308 void* ptr = (void*)(intptr_t)0xDECAFBAD; 309 FILE* stream = NULL; 310 (void)argc, (void)argv; 311 312 CHK(mem_init_proxy_allocator(&allocator, &mem_default_allocator) == RES_OK); 313 CHK(svx_device_create(NULL, &allocator, 1, &dev) == RES_OK); 314 315 low = 0.0; 316 upp = 1.0; 317 axis = AXIS; 318 nvxls = 5; 319 320 vox_desc.get = get; 321 vox_desc.merge = keep_max; 322 vox_desc.challenge_merge = no_merge; 323 vox_desc.context = ptr; 324 vox_desc.size = sizeof(double); 325 326 #define NEW_TREE svx_bintree_create 327 328 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_OK); 329 CHK(svx_tree_ref_put(tree) == RES_OK); 330 331 upp = low; 332 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 333 upp = 1.0; 334 335 nvxls = 0; 336 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 337 nvxls = 5; 338 339 vox_desc.get = NULL; 340 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 341 vox_desc.get = get; 342 343 vox_desc.merge = NULL; 344 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 345 vox_desc.merge = keep_max; 346 347 vox_desc.challenge_merge = NULL; 348 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 349 vox_desc.challenge_merge = no_merge; 350 351 vox_desc.size = 0; 352 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 353 vox_desc.size = sizeof(double); 354 355 axis = SVX_AXIS_NONE__; 356 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 357 axis = AXIS; 358 359 CHK(NEW_TREE(NULL, low, upp, nvxls, axis, &vox_desc, &tree) == RES_BAD_ARG); 360 CHK(NEW_TREE(dev, low, upp, nvxls, axis, NULL, &tree) == RES_BAD_ARG); 361 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, NULL) == RES_BAD_ARG); 362 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_OK); 363 364 ctx.lower = low; 365 ctx.upper = upp; 366 ctx.nvoxels = nvxls; 367 ctx.depth = 4; 368 ctx.axis = AXIS; 369 370 ctx.nleaves = 0; 371 ctx.leaves = MEM_CALLOC(&allocator, 5, 1); 372 CHK(ctx.leaves); 373 CHK(svx_tree_for_each_leaf(tree, check_leaves, &ctx) == RES_OK); 374 CHK(ctx.nleaves == 5); 375 MEM_RM(&allocator, ctx.leaves); 376 377 CHK(svx_tree_get_desc(NULL, &tree_desc) == RES_BAD_ARG); 378 CHK(svx_tree_get_desc(tree, NULL) == RES_BAD_ARG); 379 CHK(svx_tree_get_desc(tree, &tree_desc) == RES_OK); 380 CHK(tree_desc.nleaves == 5); 381 CHK(tree_desc.nvoxels == tree_desc.nleaves + 6/*#parents*/); 382 CHK(tree_desc.depth == 4); 383 CHK(tree_desc.type == SVX_BINTREE); 384 CHK(tree_desc.lower[axis] == low); 385 CHK(tree_desc.upper[axis] == upp); 386 387 test_at_accessor(tree, nvxls); 388 389 CHK(stream = tmpfile()); 390 CHK(svx_tree_write(NULL, stream) == RES_BAD_ARG); 391 CHK(svx_tree_write(tree, NULL) == RES_BAD_ARG); 392 CHK(svx_tree_write(tree, stream) == RES_OK); 393 394 CHK(svx_tree_ref_put(tree) == RES_OK); 395 396 rewind(stream); 397 CHK(svx_tree_create_from_stream(NULL, stream, &tree) == RES_BAD_ARG); 398 CHK(svx_tree_create_from_stream(dev, NULL, &tree) == RES_BAD_ARG); 399 CHK(svx_tree_create_from_stream(dev, stream, NULL) == RES_BAD_ARG); 400 CHK(svx_tree_create_from_stream(dev, stream, &tree) == RES_OK); 401 fclose(stream); 402 403 test_at_accessor(tree, nvxls); 404 CHK(svx_tree_ref_put(tree) == RES_OK); 405 406 build_ctx.max_depth = (size_t)log2i((int)round_up_pow2(nvxls)); 407 408 d3_splat(build_ctx.lower,-INF); 409 d3_splat(build_ctx.upper, INF); 410 d3_splat(build_ctx.voxsz, INF); 411 build_ctx.lower[AXIS] = low;; 412 build_ctx.upper[AXIS] = upp; 413 build_ctx.voxsz[AXIS] = (upp-low)/(double)nvxls; 414 415 vox_desc.get = get_aabb; 416 vox_desc.merge = merge_aabb; 417 vox_desc.challenge_merge = challenge_aabb; 418 vox_desc.context = &build_ctx; 419 vox_desc.size = sizeof(struct aabb); 420 421 CHK(NEW_TREE(dev, low, upp, nvxls, axis, &vox_desc, &tree) == RES_OK); 422 423 #undef NEW_TREE 424 425 CHK(svx_tree_ref_put(tree) == RES_OK); 426 CHK(svx_device_ref_put(dev) == RES_OK); 427 428 check_memory_allocator(&allocator); 429 mem_shutdown_proxy_allocator(&allocator); 430 CHK(mem_allocated_size() == 0); 431 return 0; 432 } 433