suvm_volume_intersect_aabb.c (4848B)
1 /* Copyright (C) 2020-2023 |Méso|Star> (contact@meso-star.com) 2 * 3 * This program is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published by 5 * the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with this program. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #include "suvm.h" 17 #include "suvm_device.h" 18 #include "suvm_volume.h" 19 20 #include <rsys/float2.h> 21 #include <rsys/float3.h> 22 23 /******************************************************************************* 24 * Helper functions 25 ******************************************************************************/ 26 static INLINE int 27 aabb_intersect_aabb 28 (const float low0[3], 29 const float upp0[3], 30 const float low1[3], 31 const float upp1[3]) 32 { 33 ASSERT(low0 && upp0 && low1 && upp1); 34 ASSERT(low0[0] < upp0[0] && low0[1] < upp0[1] && low0[2] < upp0[2]); 35 ASSERT(low1[0] < upp1[0] && low1[1] < upp1[1] && low1[2] < upp1[2]); 36 return low0[0] < upp1[0] && upp0[0] > low1[0] 37 && low0[1] < upp1[1] && upp0[1] > low1[1] 38 && low0[2] < upp1[2] && upp0[2] > low1[2]; 39 } 40 41 /******************************************************************************* 42 * Exported function 43 ******************************************************************************/ 44 res_T 45 suvm_volume_intersect_aabb 46 (struct suvm_volume* vol, 47 const double low[3], /* AABB lower bound */ 48 const double upp[3], /* AABB upper bound */ 49 suvm_primitive_intersect_aabb_T clbk, 50 void* context) 51 { 52 struct darray_node stack; 53 struct node* node = NULL; 54 struct node_leaf* leaf = NULL; 55 struct node_inner* inner = NULL; 56 int stack_is_init = 0; 57 float lowf[3]; 58 float uppf[3]; 59 res_T res = RES_OK; 60 61 if(!vol || !low || !upp || !clbk) { 62 res = RES_BAD_ARG; 63 goto error; 64 } 65 66 /* Convert the input AABB in single precision */ 67 lowf[0] = (float)low[0]; 68 lowf[1] = (float)low[1]; 69 lowf[2] = (float)low[2]; 70 uppf[0] = (float)upp[0]; 71 uppf[1] = (float)upp[1]; 72 uppf[2] = (float)upp[2]; 73 74 /* Check AABB consistency */ 75 if(lowf[0] >= uppf[0] || lowf[1] >= uppf[1] || lowf[2] >= uppf[2]) { 76 log_err(vol->dev, "%s: invalid AABB {%g, %g, %g}, {%g, %g, %g}.\n", 77 FUNC_NAME, SPLIT3(low), SPLIT3(upp)); 78 res = RES_BAD_ARG; 79 goto error; 80 } 81 82 darray_node_init(vol->dev->allocator, &stack); 83 stack_is_init = 1; 84 85 node = vol->bvh_root; 86 ASSERT(node); 87 88 if(!aabb_intersect_aabb(lowf, uppf, vol->low, vol->upp)) { 89 goto exit; 90 } 91 92 res = darray_node_reserve(&stack, 32); 93 if(res != RES_OK) goto error; 94 95 for(;;) { 96 size_t istack; 97 98 if(node->type == NODE_LEAF) { 99 struct suvm_polyhedron tetra; 100 enum suvm_intersection_type intersect; 101 102 leaf = CONTAINER_OF(node, struct node_leaf, node); 103 104 /* Check the intersection between the tetrahedron and the AABB */ 105 tetrahedron_setup(vol, leaf->low, leaf->upp, leaf->prim_id, &tetra); 106 intersect = suvm_polyhedron_intersect_aabb(&tetra, lowf, uppf); 107 108 if(intersect != SUVM_INTERSECT_NONE) { 109 struct suvm_primitive prim = SUVM_PRIMITIVE_NULL; 110 /* Setup the intersected primitive */ 111 volume_primitive_setup(vol, leaf->prim_id, &prim); 112 /* Invoke the user callback on the intersected primitive */ 113 clbk(&prim, low, upp, context); 114 } 115 116 } else { 117 int traverse_child[2] = {0,0}; 118 inner = CONTAINER_OF(node, struct node_inner, node); 119 120 /* Check the provided AABB agains the children's AABBs */ 121 traverse_child[0] = aabb_intersect_aabb 122 (lowf, uppf, inner->low[0], inner->upp[0]); 123 traverse_child[1] = aabb_intersect_aabb 124 (lowf, uppf, inner->low[1], inner->upp[1]); 125 126 if(traverse_child[0] && traverse_child[1]) { /* Traverse both children */ 127 res = darray_node_push_back(&stack, &inner->children[1]); 128 if(UNLIKELY(res != RES_OK)) goto error; 129 node = inner->children[0]; 130 continue; 131 132 } else if(traverse_child[0]) { /* Traverse only child 0 */ 133 node = inner->children[0]; 134 continue; 135 136 } else if(traverse_child[1]) { /* Traverse only child 1 */ 137 node = inner->children[1]; 138 continue; 139 } 140 } 141 142 istack = darray_node_size_get(&stack); 143 if(!istack) break; /* No more stack entry: stop traversal */ 144 145 /* Pop the stack */ 146 node = darray_node_data_get(&stack)[istack-1]; 147 darray_node_pop_back(&stack); 148 } 149 150 exit: 151 if(stack_is_init) darray_node_release(&stack); 152 return res; 153 error: 154 goto exit; 155 }