commit 9c5d64be7a05ff6b62791b9dc83c3039b57e942b
parent 0fb2cca41450262c361b5fd5c7db7338d15a4138
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Tue, 20 Oct 2020 16:44:35 +0200
Add the suvm_volume_intersect_aabb function
Diffstat:
5 files changed, 184 insertions(+), 6 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -48,7 +48,8 @@ set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
set(SUVM_FILES_SRC
suvm_device.c
suvm_volume.c
- suvm_volume_at.c)
+ suvm_volume_at.c
+ suvm_volume_intersect_aabb.c)
set(SUVM_FILES_INC
suvm_device.h
suvm_volume.h)
diff --git a/src/suvm.h b/src/suvm.h
@@ -80,6 +80,15 @@ struct suvm_tetrahedral_mesh_args {
};
static const struct suvm_tetrahedral_mesh_args SUVM_TETRAHEDRAL_MESH_ARGS_NULL;
+/* Callback invoked on suvm_volume_intersect_aabb invocation on each primitives
+ * intersected by the submitted Axis Aligned Bounding Box */
+typedef void
+(*suvm_primitive_intersect_aabb_T)
+ (const struct suvm_primitive* primitive, /* Intersected primitive */
+ const double low[3], /* AABB lower bound */
+ const double upp[3], /* AABB upper bound */
+ void* context); /* User data */
+
/* Forward declaration of external data types */
struct logger;
struct mem_allocator;
@@ -131,6 +140,10 @@ suvm_volume_get_aabb
double lower[3],
double upper[3]);
+/* Return the primitive into which `pos' lies and the barycentric coordinates
+ * of `pos' into this primitive. The returned primitive is SUVM_PRIMITIVE_NULL
+ * if `pos' is not included into any volumic primitive. One can use the
+ * SUVM_PRIMIIVE_NONE macro to check this case. */
SUVM_API res_T
suvm_volume_at
(struct suvm_volume* volume,
@@ -138,6 +151,16 @@ suvm_volume_at
struct suvm_primitive* prim, /* Geometric primitive where `pos' lies */
double barycentric_coords[4]); /* `pos' into the primitive */
+/* Iterate over the volumic primitives that intersect the submitted Axis
+ * Aligned Bounding Box and invoke the `clbk' function onto them */
+SUVM_API res_T
+suvm_volume_intersect_aabb
+ (struct suvm_volume* volume,
+ const double low[3], /* AABB lower bound */
+ const double upp[3], /* AABB upper bound */
+ suvm_primitive_intersect_aabb_T clbk,
+ void* context); /* User data sent as the last argument of clbk */
+
END_DECLS
#endif /* SUVM_H */
diff --git a/src/suvm_volume.h b/src/suvm_volume.h
@@ -44,6 +44,11 @@ struct node {
enum node_type type;
};
+/* Generate the dynamic array of BVH node */
+#define DARRAY_NAME node
+#define DARRAY_DATA struct node*
+#include <rsys/dynamic_array.h>
+
/* Inner node */
struct ALIGN(16) node_inner {
float low[2][3];
diff --git a/src/suvm_volume_at.c b/src/suvm_volume_at.c
@@ -17,11 +17,6 @@
#include "suvm_device.h"
#include "suvm_volume.h"
-/* Generate the dynamic array of BVH node */
-#define DARRAY_NAME node
-#define DARRAY_DATA struct node*
-#include <rsys/dynamic_array.h>
-
/*******************************************************************************
* Helper functions
******************************************************************************/
diff --git a/src/suvm_volume_intersect_aabb.c b/src/suvm_volume_intersect_aabb.c
@@ -0,0 +1,154 @@
+/* Copyright (C) 2020 |Meso|Star> (contact@meso-star.com)
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "suvm.h"
+#include "suvm_device.h"
+#include "suvm_volume.h"
+
+/*******************************************************************************
+ * Helper functions
+ ******************************************************************************/
+static INLINE int
+aabb_intersect_aabb
+ (const float low0[3],
+ const float upp0[3],
+ const float low1[3],
+ const float upp1[3])
+{
+ ASSERT(low0 && upp0 && low1 && upp1);
+ ASSERT(low0[0] < upp0[0] && low0[1] < upp0[1] && low0[2] < upp0[2]);
+ ASSERT(low1[0] < upp1[0] && low1[1] < upp1[1] && low1[2] < upp1[2]);
+ return low0[0] < upp1[0] && upp0[0] > low1[0]
+ && low0[1] < upp1[1] && upp0[1] > low1[1]
+ && low0[2] < upp1[2] && upp0[2] > low1[2];
+}
+
+/*******************************************************************************
+ * Exported function
+ ******************************************************************************/
+res_T
+suvm_volume_intersect_aabb
+ (struct suvm_volume* vol,
+ const double low[3], /* AABB lower bound */
+ const double upp[3], /* AABB upper bound */
+ suvm_primitive_intersect_aabb_T clbk,
+ void* context)
+{
+ struct darray_node stack;
+ struct node* node = NULL;
+ struct node_leaf* leaf = NULL;
+ struct node_inner* inner = NULL;
+ int stack_is_init = 0;
+ float lowf[3];
+ float uppf[3];
+ res_T res = RES_BAD_ARG;
+
+ if(!vol || !low || !upp || !clbk) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ /* Convert the input AABB in single precision */
+ lowf[0] = (float)low[0];
+ lowf[1] = (float)low[1];
+ lowf[2] = (float)low[2];
+ uppf[0] = (float)upp[0];
+ uppf[1] = (float)upp[1];
+ uppf[2] = (float)upp[2];
+
+ /* Check AABB consistency */
+ if(lowf[0] >= uppf[0] || lowf[1] >= uppf[1] || lowf[2] >= uppf[2]) {
+ log_err(vol->dev, "%s: invalid AABB {%g, %g, %g}, {%g, %g, %g}.\n",
+ FUNC_NAME, SPLIT3(low), SPLIT3(upp));
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ darray_node_init(vol->dev->allocator, &stack);
+ stack_is_init = 1;
+
+ node = vol->bvh_root;
+ ASSERT(node);
+
+ if(!aabb_intersect_aabb(lowf, uppf, vol->low, vol->upp)) {
+ goto exit;
+ }
+
+ res = darray_node_reserve(&stack, 32);
+ if(res != RES_OK) goto error;
+
+ for(;;) {
+ size_t istack;
+
+ if(node->type == NODE_LEAF) {
+ leaf = CONTAINER_OF(node, struct node_leaf, node);
+ if(aabb_intersect_aabb(lowf, uppf, leaf->low, leaf->upp)) {
+ struct suvm_primitive prim = SUVM_PRIMITIVE_NULL;
+ /* Setup the intersected primitive */
+ prim.nvertices = 4;
+ prim.iprim = leaf->prim_id;
+ if(vol->has_prim_data) {
+ prim.data = volume_get_primitive_data(vol, prim.iprim);
+ }
+ if(vol->has_vert_data) {
+ prim.vertex_data[0] = volume_primitive_get_vertex_data(vol, prim.iprim, 0);
+ prim.vertex_data[1] = volume_primitive_get_vertex_data(vol, prim.iprim, 1);
+ prim.vertex_data[2] = volume_primitive_get_vertex_data(vol, prim.iprim, 2);
+ prim.vertex_data[3] = volume_primitive_get_vertex_data(vol, prim.iprim, 3);
+ }
+ /* Invoke the user callback on the intersected primitive */
+ clbk(&prim, low, upp, context);
+ }
+
+ } else {
+ int traverse_child[2] = {0,0};
+ inner = CONTAINER_OF(node, struct node_inner, node);
+
+ /* Check the provided AABB agains the children's AABBs */
+ traverse_child[0] = aabb_intersect_aabb
+ (lowf, uppf, inner->low[0], inner->upp[0]);
+ traverse_child[1] = aabb_intersect_aabb
+ (lowf, uppf, inner->low[1], inner->upp[1]);
+
+ if(traverse_child[0] && traverse_child[1]) { /* Traverse both children */
+ res = darray_node_push_back(&stack, &inner->children[1]);
+ if(UNLIKELY(res != RES_OK)) goto error;
+ node = inner->children[0];
+ continue;
+
+ } else if(traverse_child[0]) { /* Traverse only child 0 */
+ node = inner->children[0];
+ continue;
+
+ } else if(traverse_child[1]) { /* Traverse only child 1 */
+ node = inner->children[1];
+ continue;
+ }
+ }
+
+ istack = darray_node_size_get(&stack);
+ if(!istack) break; /* No more stack entry: stop traversal */
+
+ /* Pop the stack */
+ node = darray_node_data_get(&stack)[istack-1];
+ darray_node_pop_back(&stack);
+ }
+
+exit:
+ if(stack_is_init) darray_node_release(&stack);
+ return res;
+error:
+ goto exit;
+}
