commit 8bd4dda029305b5e835621b512f92a8240decc35
parent beabe73d18f2a371d5fb492b05bd27468ebf6f4a
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 25 Sep 2020 15:32:53 +0200
Update the memory layout of the tetrahedral mesh
Store indices as uint32_t and vertex position as float. Fix variable
names and add precomputed normals support.
Diffstat:
5 files changed, 305 insertions(+), 123 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -49,7 +49,8 @@ set(SUVM_FILES_SRC
suvm_device.c
suvm_volume.c)
set(SUVM_FILES_INC
- suvm_device.h)
+ suvm_device.h
+ suvm_volume.h)
set(SUVM_FILES_INC_API
suvm.h)
@@ -63,6 +64,9 @@ rcmake_prepend_path(SUVM_FILES_DOC ${PROJECT_SOURCE_DIR}/../)
add_library(suvm SHARED ${SUVM_FILES_SRC} ${SUVM_FILES_INC} ${SUVM_FILES_INC_API})
target_link_libraries(suvm RSys ${EMBREE_LIBRARIES})
+if(CMAKE_COMPILER_IS_GNUCC)
+ target_link_libraries(suvm m)
+endif()
set_target_properties(suvm PROPERTIES
DEFINE_SYMBOL SUVM_SHARED_BUILD
diff --git a/src/suvm.h b/src/suvm.h
@@ -52,20 +52,28 @@ struct suvm_primitive {
size_t iprim; /* Identifier of the primitive */
size_t nvertices; /* #vertices of the primitive */
};
+#define SUVM_PRIMITIVE_NULL__ {NULL, {NULL}, SIZE_MAX, SIZE_MAX}
+static const struct suvm_primitive SUVM_PRIMITIVE_NULL = SUVM_PRIMITIVE_NULL__;
struct suvm_tetrahedral_mesh_args {
- size_t ntetrahedras; /* #tetrahedrals */
+ size_t ntetrahedra; /* #tetrahedra */
size_t nvertices; /* #vertices */
- /* Each tetrahedra has to list the bottom triangle in conterclockwise order,
+ /* Each tetrahedron has to list the bottom triangle in conterclockwise order,
* and then the top vertex. */
void (*get_indices)(const size_t itetra, size_t ids[4], void* ctx);
void (*get_position)(const size_t ivert, double pos[3], void* ctx);
- /* Per tetrahedra/vertex data. SUVM_DATA_NULL <=> no data */
- struct suvm_data tetrahedra_data;
+ /* Per tetrahedron/vertex data. SUVM_DATA_NULL <=> no data */
+ struct suvm_data tetrahedron_data;
struct suvm_data vertex_data;
+ /* Define whether tetrahedron normals are precomputed or not. When
+ * precomputed, the normals of each tetrahedron facet are explicitly stored
+ * and thus increase the memory footprint but speed up accessors that use
+ * them (e.g. suvm_volume_at). */
+ int precompute_normals;
+
void* context; /* Client data set as the last param of the callbacks */
};
static const struct suvm_tetrahedral_mesh_args SUVM_TETRAHEDRAL_MESH_ARGS_NULL;
diff --git a/src/suvm_volume.c b/src/suvm_volume.c
@@ -16,13 +16,14 @@
#include "suvm.h"
#include "suvm_c.h"
#include "suvm_device.h"
+#include "suvm_volume.h"
#include <rsys/cstr.h>
#include <rsys/dynamic_array_double.h>
#include <rsys/dynamic_array_size_t.h>
+#include <rsys/float3.h>
#include <rsys/ref_count.h>
-#include <embree3/rtcore_device.h>
#include <embree3/rtcore_builder.h>
/* Generate the dynamic array of RTCBuildPrimitive */
@@ -31,53 +32,6 @@
#define DARRAY_ALIGNMENT ALIGNOF(struct RTCBuildPrimitive)
#include <rsys/dynamic_array.h>
-struct buffer {
- void* mem; /* Raw memory block storing the data */
- size_t elmt_size; /* Size in bytes of one data */
- size_t elmt_stride; /* Size in bytes between two consecutive data */
- size_t elmt_alignment; /* Data alignment */
- size_t size; /* #data */
- struct mem_allocator* allocator;
-};
-static const struct buffer BUFFER_NULL;
-
-enum node_type { NODE_INNER, NODE_LEAF };
-
-/* Generic node */
-struct node {
- enum node_type type;
-};
-
-/* Inner node */
-struct ALIGN(16) node_inner {
- float low[2][3];
- float upp[2][3];
- struct node* children[2];
- struct node node;
-};
-
-/* Leaf node */
-struct ALIGN(16) node_leaf {
- float low[3];
- unsigned int geom_id;
- float upp[3];
- unsigned int prim_id;
- struct node node;
-};
-
-struct suvm_volume {
- struct darray_size_t indices; /* List of size_t[4] */
- struct darray_double positions; /* List of double[3] */
- struct buffer prim_data; /* Per primitive data */
- struct buffer vert_data; /* Per vertex data */
-
- RTCBVH bvh;
- struct node* bvh_root;
-
- struct suvm_device* dev;
- ref_T ref;
-};
-
/*******************************************************************************
* Helper functions
******************************************************************************/
@@ -85,7 +39,7 @@ static INLINE int
check_tetrahedral_mesh_args(const struct suvm_tetrahedral_mesh_args* args)
{
return args
- && args->ntetrahedras
+ && args->ntetrahedra
&& args->nvertices
&& args->get_indices
&& args->get_position;
@@ -146,77 +100,175 @@ error:
goto exit;
}
-static INLINE size_t
-volume_get_primitives_count(const struct suvm_volume* vol)
+static res_T
+setup_tetrahedral_mesh_indices
+ (struct suvm_volume* vol, const struct suvm_tetrahedral_mesh_args* args)
{
- ASSERT(vol);
- return darray_size_t_size_get(&vol->indices) / 4/*#indices per primitive*/;
+ size_t itetra;
+ res_T res = RES_OK;
+ ASSERT(vol && args);
+
+ res = darray_u32_resize
+ (&vol->indices, args->ntetrahedra*4/*#vertices per tetra*/);
+ if(res != RES_OK) goto error;
+
+ /* Locally copy the indices */
+ FOR_EACH(itetra, 0, args->ntetrahedra) {
+ size_t tetra[4];
+ uint32_t* tetra_u32 = darray_u32_data_get(&vol->indices)+itetra*4;
+ args->get_indices(itetra, tetra, args->context);
+ ASSERT(tetra[0] < UINT32_MAX);
+ ASSERT(tetra[1] < UINT32_MAX);
+ ASSERT(tetra[2] < UINT32_MAX);
+ ASSERT(tetra[3] < UINT32_MAX);
+ tetra_u32[0] = (uint32_t)tetra[0];
+ tetra_u32[1] = (uint32_t)tetra[1];
+ tetra_u32[2] = (uint32_t)tetra[2];
+ tetra_u32[3] = (uint32_t)tetra[3];
+ }
+
+exit:
+ return res;
+error:
+ darray_u32_purge(&vol->indices);
+ goto exit;
}
static res_T
-setup_tetrahedral_mesh
+setup_tetrahedral_mesh_position
(struct suvm_volume* vol, const struct suvm_tetrahedral_mesh_args* args)
{
- size_t itetra;
size_t ivert;
res_T res = RES_OK;
ASSERT(vol && args);
- /* Store the tetrahedral indices */
- res = darray_size_t_resize
- (&vol->indices, args->ntetrahedras*4/*#vertices per tetra*/);
- if(res != RES_OK) {
- log_err(vol->dev,
- "Could not allocate the list of tetrahedra indices -- %s.\n",
- res_to_cstr(res));
- goto error;
- }
- FOR_EACH(itetra, 0, args->ntetrahedras) {
- size_t* tetra = darray_size_t_data_get(&vol->indices)+itetra*4;
- args->get_indices(itetra, tetra, args->context);
+ res = darray_float_resize
+ (&vol->positions, args->nvertices*3/*#coords per vertex*/);
+ if(res != RES_OK) goto error;
+
+ /* Locally copy the positions */
+ FOR_EACH(ivert, 0, args->nvertices) {
+ double vertd[3];
+ float* vertf = darray_float_data_get(&vol->positions)+ivert*3;
+ args->get_position(ivert, vertd, args->context);
+ vertf[0] = (float)vertd[0];
+ vertf[1] = (float)vertd[1];
+ vertf[2] = (float)vertd[2];
}
- /* Store the vertex positions */
- res = darray_double_resize
- (&vol->positions, args->nvertices*3/*#coords per vertex*/);
- if(res != RES_OK) {
- log_err(vol->dev,
- "Could not allocate the list of tetrahedra vertices -- %s.\n",
- res_to_cstr(res));
- goto error;
+exit:
+ return res;
+error:
+ darray_float_purge(&vol->positions);
+ goto exit;
+}
+
+static INLINE float*
+compute_tetrahedron_normal
+ (const struct suvm_volume* vol,
+ const size_t itetra,
+ const int ifacet/*In [0,3]*/,
+ float normal[3])
+{
+ const uint32_t* ids;
+ const float* v0;
+ const float* v1;
+ const float* v2;
+
+ float E0[3], E1[3];
+
+ /* Facet indices, Ensure CCW ordering */
+ const int facet[4][3] = {{0,1,2}, {0,3,1}, {1,3,2}, {2,3,0}};
+
+ ASSERT(vol && itetra < volume_get_primitives_count(vol));
+
+ /* Fetch tetrahedron indices */
+ ids = darray_u32_cdata_get(&vol->indices) + itetra*4;
+
+ /* Fetch facet vertices */
+ v0 = darray_float_cdata_get(&vol->positions) + ids[facet[ifacet][0]]*3;
+ v1 = darray_float_cdata_get(&vol->positions) + ids[facet[ifacet][1]]*3;
+ v2 = darray_float_cdata_get(&vol->positions) + ids[facet[ifacet][2]]*3;
+
+ /* Compute the normal */
+ f3_sub(E0, v1, v0);
+ f3_sub(E1, v2, v0);
+ f3_cross(normal, E0, E1);
+ f3_normalize(normal, normal);
+
+ return normal;
+}
+
+static res_T
+compute_tetrahedral_mesh_normals(struct suvm_volume* vol)
+{
+ size_t itetra;
+ size_t ntetrahedra;
+ res_T res = RES_OK;
+ ASSERT(vol);
+
+ ntetrahedra = volume_get_primitives_count(vol);
+
+ res = darray_float_resize(&vol->normals,
+ ntetrahedra * 4/*#facets per tetrahedron*/ * 3/*#coords per normal*/);
+ if(res != RES_OK) goto error;
+
+ FOR_EACH(itetra, 0, ntetrahedra) {
+ float* n0 = darray_float_data_get(&vol->normals) + (itetra*4 + 0)*3;
+ float* n1 = darray_float_data_get(&vol->normals) + (itetra*4 + 1)*3;
+ float* n2 = darray_float_data_get(&vol->normals) + (itetra*4 + 3)*3;
+ float* n3 = darray_float_data_get(&vol->normals) + (itetra*4 + 2)*3;
+ compute_tetrahedron_normal(vol, itetra, 0, n0);
+ compute_tetrahedron_normal(vol, itetra, 1, n1);
+ compute_tetrahedron_normal(vol, itetra, 2, n2);
+ compute_tetrahedron_normal(vol, itetra, 3, n3);
}
- FOR_EACH(ivert, 0, args->nvertices) {
- double* vert = darray_double_data_get(&vol->positions)+ivert*3;
- args->get_position(ivert, vert, args->context);
+
+exit:
+ return res;
+error:
+ darray_float_purge(&vol->normals);
+ goto exit;
+}
+
+static res_T
+setup_tetrahedral_mesh
+ (struct suvm_volume* vol, const struct suvm_tetrahedral_mesh_args* args)
+{
+ res_T res = RES_OK;
+ ASSERT(vol && args);
+
+ res = setup_tetrahedral_mesh_indices(vol, args);
+ if(res != RES_OK) goto error;
+ res = setup_tetrahedral_mesh_position(vol, args);
+ if(res != RES_OK) goto error;
+
+ /* Precompute the facet normals */
+ if(args->precompute_normals) {
+ res = compute_tetrahedral_mesh_normals(vol);
+ if(res != RES_OK) goto error;
}
- /* Store the per tetrahedral data */
- if(args->tetrahedra_data.get) {
+ /* Store the per tetrahedron data */
+ if(args->tetrahedron_data.get) {
res = buffer_init_from_data(vol->dev->allocator, &vol->prim_data,
- &args->tetrahedra_data, args->ntetrahedras, args->context);
- if(res != RES_OK) {
- log_err(vol->dev,
- "Could not setup the per volumetric primitive data -- %s.\n",
- res_to_cstr(res));
- goto error;
- }
+ &args->tetrahedron_data, args->ntetrahedra, args->context);
+ if(res != RES_OK) goto error;
}
/* Store the per vertex data */
if(args->vertex_data.get) {
res = buffer_init_from_data(vol->dev->allocator, &vol->vert_data,
&args->vertex_data, args->nvertices, args->context);
- if(res != RES_OK) {
- log_err(vol->dev, "Could not setup the per vertex data -- %s.\n",
- res_to_cstr(res));
- goto error;
- }
+ if(res != RES_OK) goto error;
}
+
exit:
return res;
error:
- darray_size_t_purge(&vol->indices);
- darray_double_purge(&vol->positions);
+ darray_u32_purge(&vol->indices);
+ darray_float_purge(&vol->positions);
+ darray_float_purge(&vol->normals);
buffer_release(&vol->prim_data);
buffer_release(&vol->vert_data);
goto exit;
@@ -330,18 +382,18 @@ build_bvh(struct suvm_volume* vol)
/* Setup the primitive array */
FOR_EACH(iprim, 0, nprims) {
- const size_t* ids = darray_size_t_cdata_get(&vol->indices) + iprim*4;
- const double* verts[4];
+ const uint32_t* ids = darray_u32_cdata_get(&vol->indices) + iprim*4;
+ const float* verts[4];
struct RTCBuildPrimitive* prim = darray_rtc_prim_data_get(&rtc_prims)+iprim;
double low[3], upp[3];
- /* Fetch the tetrahedral vertices */
- verts[0] = darray_double_cdata_get(&vol->positions) + ids[0]*3/*#coords*/;
- verts[1] = darray_double_cdata_get(&vol->positions) + ids[1]*3/*#coords*/;
- verts[2] = darray_double_cdata_get(&vol->positions) + ids[2]*3/*#coords*/;
- verts[3] = darray_double_cdata_get(&vol->positions) + ids[3]*3/*#coords*/;
+ /* Fetch the tetrahedron vertices */
+ verts[0] = darray_float_cdata_get(&vol->positions) + ids[0]*3/*#coords*/;
+ verts[1] = darray_float_cdata_get(&vol->positions) + ids[1]*3/*#coords*/;
+ verts[2] = darray_float_cdata_get(&vol->positions) + ids[2]*3/*#coords*/;
+ verts[3] = darray_float_cdata_get(&vol->positions) + ids[3]*3/*#coords*/;
- /* Compute the tetrahedral AABB */
+ /* Compute the tetrahedron AABB */
low[0] = MMIN(MMIN(verts[0][0],verts[1][0]), MMIN(verts[2][0],verts[3][0]));
low[1] = MMIN(MMIN(verts[0][1],verts[1][1]), MMIN(verts[2][1],verts[3][1]));
low[2] = MMIN(MMIN(verts[0][2],verts[1][2]), MMIN(verts[2][2],verts[3][2]));
@@ -413,8 +465,9 @@ volume_release(ref_T* ref)
ASSERT(ref);
vol = CONTAINER_OF(ref, struct suvm_volume, ref);
dev = vol->dev;
- darray_size_t_release(&vol->indices);
- darray_double_release(&vol->positions);
+ darray_u32_release(&vol->indices);
+ darray_float_release(&vol->positions);
+ darray_float_release(&vol->normals);
buffer_release(&vol->prim_data);
buffer_release(&vol->vert_data);
if(vol->bvh) rtcReleaseBVH(vol->bvh);
@@ -447,8 +500,9 @@ suvm_tetrahedral_mesh_create
ref_init(&vol->ref);
SUVM(device_ref_get(dev));
vol->dev = dev;
- darray_size_t_init(dev->allocator, &vol->indices);
- darray_double_init(dev->allocator, &vol->positions);
+ darray_u32_init(dev->allocator, &vol->indices);
+ darray_float_init(dev->allocator, &vol->positions);
+ darray_float_init(dev->allocator, &vol->normals);
/* Locally copy the volumetric mesh data */
res = setup_tetrahedral_mesh(vol, args);
@@ -458,6 +512,27 @@ suvm_tetrahedral_mesh_create
res = build_bvh(vol);
if(res != RES_OK) goto error;
+ /* Setup the volume AABB */
+ if(vol->bvh_root->type == NODE_LEAF) {
+ const struct node_leaf* leaf = NULL;
+ leaf = CONTAINER_OF(vol->bvh_root, struct node_leaf, node);
+ vol->low[0] = leaf->low[0];
+ vol->low[1] = leaf->low[1];
+ vol->low[2] = leaf->low[2];
+ vol->upp[0] = leaf->upp[0];
+ vol->upp[1] = leaf->upp[1];
+ vol->upp[2] = leaf->upp[2];
+ } else {
+ const struct node_inner* inner = NULL;
+ inner = CONTAINER_OF(vol->bvh_root, struct node_inner, node);
+ vol->low[0] = MMIN(inner->low[0][0], inner->low[1][0]);
+ vol->low[1] = MMIN(inner->low[0][1], inner->low[1][1]);
+ vol->low[2] = MMIN(inner->low[0][2], inner->low[1][2]);
+ vol->upp[0] = MMIN(inner->upp[0][0], inner->upp[1][0]);
+ vol->upp[1] = MMIN(inner->upp[0][1], inner->upp[1][1]);
+ vol->upp[2] = MMIN(inner->upp[0][2], inner->upp[1][2]);
+ }
+
exit:
if(out_vol) *out_vol = vol;
return res;
@@ -482,3 +557,4 @@ suvm_volume_ref_put(struct suvm_volume* vol)
return RES_OK;
}
+
diff --git a/src/suvm_volume.h b/src/suvm_volume.h
@@ -0,0 +1,90 @@
+/* Copyright (C) 2013-2020 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * The RSys library 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef SUVM_VOLUME_H
+#define SUVM_VOLUME_H
+
+#include <rsys/dynamic_array_u32.h>
+#include <rsys/dynamic_array_float.h>
+#include <rsys/ref_count.h>
+
+#include <embree3/rtcore_device.h>
+
+/* Forward declarations */
+struct suvm_device;
+struct mem_allocator;
+
+struct buffer {
+ void* mem; /* Raw memory block storing the data */
+ size_t elmt_size; /* Size in bytes of one data */
+ size_t elmt_stride; /* Size in bytes between two consecutive data */
+ size_t elmt_alignment; /* Data alignment */
+ size_t size; /* #data */
+ struct mem_allocator* allocator;
+};
+static const struct buffer BUFFER_NULL;
+
+enum node_type { NODE_INNER, NODE_LEAF };
+
+/* Generic node */
+struct node {
+ enum node_type type;
+};
+
+/* Inner node */
+struct ALIGN(16) node_inner {
+ float low[2][3];
+ float upp[2][3];
+ struct node* children[2];
+ struct node node;
+};
+
+/* Leaf node */
+struct ALIGN(16) node_leaf {
+ float low[3];
+ unsigned int geom_id;
+ float upp[3];
+ unsigned int prim_id;
+ struct node node;
+};
+
+struct suvm_volume {
+ struct darray_u32 indices; /* List of uint32_t[4] */
+ struct darray_float positions; /* List of double[3] */
+ struct darray_float normals; /* List of per tetrahedron facet normals */
+ struct buffer prim_data; /* Per primitive data */
+ struct buffer vert_data; /* Per vertex data */
+
+ float low[3], upp[3]; /* Volume AABB */
+
+ RTCBVH bvh;
+ struct node* bvh_root;
+
+ struct suvm_device* dev;
+ ref_T ref;
+};
+
+static FINLINE size_t
+volume_get_primitives_count(const struct suvm_volume* vol)
+{
+ size_t sz = 0;
+ ASSERT(vol);
+ sz = darray_u32_size_get(&vol->indices);
+ ASSERT(sz % 4/*#vertices per tetrahedron*/ == 0);
+ return sz / 4;
+}
+
+#endif /* SUVM_VOLUME_H */
+
diff --git a/src/test_suvm_volume.c b/src/test_suvm_volume.c
@@ -116,11 +116,11 @@ main(int argc, char** argv)
CHK(suvm_device_create(NULL, &mem_default_allocator, 1, &dev) == RES_OK);
- args.ntetrahedras = box_ntetras;
+ args.ntetrahedra = box_ntetras;
args.nvertices = box_nverts;
args.get_indices = get_indices;
args.get_position = get_position;
- args.tetrahedra_data = SUVM_DATA_NULL;
+ args.tetrahedron_data = SUVM_DATA_NULL;
args.vertex_data = SUVM_DATA_NULL;
args.context = NULL;
@@ -135,9 +135,9 @@ main(int argc, char** argv)
CHK(suvm_volume_ref_put(vol) == RES_OK);
CHK(suvm_volume_ref_put(vol) == RES_OK);
- args.ntetrahedras = 0;
+ args.ntetrahedra = 0;
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_BAD_ARG);
- args.ntetrahedras = box_ntetras;
+ args.ntetrahedra = box_ntetras;
args.nvertices = 0;
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_BAD_ARG);
args.nvertices = box_nverts;
@@ -150,23 +150,27 @@ main(int argc, char** argv)
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_OK);
CHK(suvm_volume_ref_put(vol) == RES_OK);
- args.tetrahedra_data.get = get_tetra_data;
- args.tetrahedra_data.size = sizeof(size_t[4]);
- args.tetrahedra_data.alignment = 64;
+ args.precompute_normals = 1;
+ CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_OK);
+ CHK(suvm_volume_ref_put(vol) == RES_OK);
+
+ args.tetrahedron_data.get = get_tetra_data;
+ args.tetrahedron_data.size = sizeof(size_t[4]);
+ args.tetrahedron_data.alignment = 64;
args.vertex_data.get = get_vert_data;
args.vertex_data.size = sizeof(double[3]);
args.vertex_data.alignment = 32;
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_OK);
CHK(suvm_volume_ref_put(vol) == RES_OK);
- args.tetrahedra_data.size = 0;
+ args.tetrahedron_data.size = 0;
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_BAD_ARG);
- args.tetrahedra_data.size = sizeof(size_t[4]);
- args.tetrahedra_data.alignment = 0;
+ args.tetrahedron_data.size = sizeof(size_t[4]);
+ args.tetrahedron_data.alignment = 0;
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_BAD_ARG);
- args.tetrahedra_data.alignment = 3;
+ args.tetrahedron_data.alignment = 3;
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_BAD_ARG);
- args.tetrahedra_data.alignment = 64;
+ args.tetrahedron_data.alignment = 64;
args.vertex_data.size = 0;
CHK(suvm_tetrahedral_mesh_create(dev, &args, &vol) == RES_BAD_ARG);
args.vertex_data.size = sizeof(double[3]);
