svx_bintree.c (4675B)
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 #include "svx_c.h" 19 #include "svx_device.h" 20 #include "svx_tree.h" 21 #include "svx_tree_builder.h" 22 23 #include <rsys/mem_allocator.h> 24 25 /* Generate the bintree_builder API */ 26 #define TREE_DIMENSION 1 27 #include "svx_tree_builder.h" 28 29 /******************************************************************************* 30 * Exported functions 31 ******************************************************************************/ 32 res_T 33 svx_bintree_create 34 (struct svx_device* dev, 35 const double lower, /* Lower bound of the bintree */ 36 const double upper, /* Upper bound of the bintree */ 37 const size_t nvoxels, /* # voxels along the range */ 38 const enum svx_axis axis, /* Axis along which the binary tree is defined */ 39 const struct svx_voxel_desc* desc, /* Descriptor of a voxel */ 40 struct svx_tree** out_bintree) 41 { 42 struct svx_tree* bintree = NULL; 43 double vox_sz; /* World space size of a voxel */ 44 struct bintree_builder bldr; 45 struct voxel vox = VOXEL_NULL; 46 size_t ivox; 47 res_T res = RES_OK; 48 49 if(!dev || !check_svx_voxel_desc(desc) || !out_bintree || axis<0 || axis>2) { 50 res = RES_BAD_ARG; 51 goto error; 52 } 53 if(lower >= upper) { 54 log_err(dev, 55 "%s: the submitted range is degenerated\n" 56 "\tlower = %g, upper = %g\n", FUNC_NAME, lower, upper); 57 res = RES_BAD_ARG; 58 goto error; 59 } 60 if(!nvoxels) { 61 log_err(dev, 62 "%s: the number of voxels along cannot be null.\n" 63 "\t#voxels = %lu.\n", 64 FUNC_NAME, (unsigned long)nvoxels); 65 res = RES_BAD_ARG; 66 goto error; 67 } 68 69 res = tree_create(dev, SVX_BINTREE, desc->size, &bintree); 70 if(res != RES_OK) goto error; 71 72 /* The binary tree definition that must be a power of two */ 73 bintree->definition = round_up_pow2(nvoxels); 74 75 bintree->frame[0] = axis; 76 77 /* Setup the binary tree AABB in world space */ 78 bintree->lower[axis] = lower; 79 bintree->upper[axis] = upper; 80 81 /* Compute the world space range of the binary tree */ 82 vox_sz = (upper - lower) / (double)nvoxels; 83 bintree->tree_low[axis] = lower; 84 bintree->tree_upp[axis] = lower + (double)bintree->definition * vox_sz; 85 bintree->tree_size[axis] = bintree->tree_upp[axis] - bintree->tree_low[axis]; 86 87 /* Initialize the bintree builder */ 88 res = bintree_builder_init(&bldr, bintree->definition, bintree->tree_low, 89 bintree->tree_upp, bintree->frame, desc, &bintree->buffer); 90 if(res != RES_OK) goto error; 91 92 /* Allocate the memory space of a temporary voxel */ 93 vox.data = MEM_CALLOC(dev->allocator, 1, desc->size); 94 if(!vox.data) { 95 res = RES_MEM_ERR; 96 goto error; 97 } 98 99 FOR_EACH(ivox, 0, bintree->definition) { 100 size_t xyz[3] = {0, 0, 0}; 101 if(ivox >= nvoxels) continue; /* Out of bound voxels */ 102 103 /* Retrieve the voxel data from the caller */ 104 xyz[axis] = ivox; 105 desc->get(xyz, ivox, vox.data, desc->context); 106 vox.mcode = ivox; 107 108 /* Register the voxel against the bintree */ 109 res = bintree_builder_add_voxel(&bldr, &vox); 110 if(res != RES_OK) goto error; 111 } 112 113 res = bintree_builder_finalize(&bldr, &bintree->root, bintree->root_attr); 114 if(res != RES_OK) goto error; 115 116 bintree->nleaves = bldr.nleaves; 117 bintree->depth = (size_t)(bldr.tree_depth - bldr.non_empty_lvl) 118 + 1 /* leaf level */; 119 ASSERT(bldr.tree_depth > bldr.non_empty_lvl); 120 121 #ifndef NDEBUG 122 { 123 size_t nleaves = 0; 124 CHK(buffer_check_tree(&bintree->buffer, bintree->root, 1, &nleaves) == RES_OK); 125 CHK(nleaves == bintree->nleaves); 126 } 127 #endif 128 129 /* Adjust the binary tree definition with respect to the binary tree depth 130 * since finest levels might be removed during the build due to the merging 131 * process */ 132 bintree->definition = bintree->definition / ((size_t)1<<bldr.non_empty_lvl); 133 134 exit: 135 if(vox.data) MEM_RM(dev->allocator, vox.data); 136 if(out_bintree) *out_bintree = bintree; 137 return res; 138 error: 139 if(bintree) { 140 SVX(tree_ref_put(bintree)); 141 bintree = NULL; 142 } 143 goto exit; 144 } 145 146