star-3d

Surface structuring for efficient 3D geometric queries
git clone git://git.meso-star.fr/star-3d.git
Log | Files | Refs | README | LICENSE

commit 12415ae8847a1ae4c8b20795e4be979f10351966
parent 00b83a314f65d0a33bb507ea6238c1b3343ab347
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Thu, 16 Apr 2015 16:52:32 +0200

First implementation of the sampler API

Diffstat:
Mcmake/CMakeLists.txt | 1+
Msrc/s3d.h | 46+++++++++++++++++++++++++++++++++++++---------
Msrc/s3d_primitive.c | 8++++----
Asrc/s3d_sampler.c | 492+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Msrc/s3d_scene.c | 11++++++-----
Msrc/s3d_shape.c | 15---------------
6 files changed, 540 insertions(+), 33 deletions(-)

diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt @@ -63,6 +63,7 @@ set(S3D_FILES_SRC s3d_instance.c s3d_mesh.c s3d_primitive.c + s3d_sampler.c s3d_scene.c s3d_shape.c) set(S3D_FILES_INC_API s3d.h) diff --git a/src/s3d.h b/src/s3d.h @@ -85,9 +85,9 @@ enum s3d_transform_space { struct s3d_primitive { /* Internal data. Should not be accessed */ - void* ptr__; + void* mesh__; + void* inst__; unsigned iprim__; - unsigned igeom__; }; /* Untyped vertex attribute */ @@ -125,7 +125,7 @@ struct s3d_hit { /* Constant defining a NULL intersection. Should be used to initialize a hit */ static const struct s3d_hit S3D_HIT_NULL = -{{NULL, (unsigned)-1, (unsigned)-1}, {0.f,0.f,0.f}, {0.f,0.f}, FLT_MAX}; +{{NULL, NULL, (unsigned)-1}, {0.f,0.f,0.f}, {0.f,0.f}, FLT_MAX}; /* Helper macro that defines whether or not the hit is valid, i.e. the ray * intersects a shape or not */ @@ -133,6 +133,7 @@ static const struct s3d_hit S3D_HIT_NULL = /* Forward declaration of s3d opaque data types */ struct s3d_device; /* Entry point of the library */ +struct s3d_sampler; /* Random distribution of shape positions */ struct s3d_scene; /* Collection of shapes */ struct s3d_shape; /* Untyped geometry */ @@ -275,15 +276,42 @@ s3d_shape_is_attached (struct s3d_shape* shape, char* is_attached); -/* Sample the shape with respect to 3 uniform random variables. TODO not - * implemented yet */ +/******************************************************************************* + * Sampler API + ******************************************************************************/ S3D_API res_T -s3d_shape_sample +s3d_sampler_create (struct s3d_shape* shape, - /* Uniform random variables in [0, 1) */ + struct s3d_sampler** sampler); + +S3D_API res_T +s3d_sampler_ref_get + (struct s3d_sampler* sampler); + +S3D_API res_T +s3d_sampler_ref_put + (struct s3d_sampler* sampler); + +/* Synchronize the sampler geometry with the geometry of its attached shape. If + * a s3d_sampler_begin_sampling is already active on `sample' a RES_BAD_OP + * error is returned. On success no other begin samping can be invoked on + * `sampler' until s3d_sampler_end_sampling is called. A s3d_sampler_get + * operation can be invoked on `sampler' only between a + * s3d_sampler_begin_sampling and s3d_sampler_end_sampling call. */ +S3D_API res_T +s3d_sampler_begin_sampling + (struct s3d_sampler* sampler); + +S3D_API res_T +s3d_sampler_end_sampling + (struct s3d_sampler* sampler); + +S3D_API res_T +s3d_sampler_get + (struct s3d_sampler* sampler, const float u, const float v, const float w, - struct s3d_primitive* primitive, /* Sampled primitive */ - float uv[2]); /* Sampled barycentric coordinate onto `primitive' */ + struct s3d_primitive* primitive, /* sampled primitive */ + float uv[2]); /******************************************************************************* * Primitive API - Define a geometric primitive of a shape diff --git a/src/s3d_primitive.c b/src/s3d_primitive.c @@ -61,12 +61,12 @@ s3d_primitive_get_attrib if(uv[0] < 0.f || uv[1] < 0.f) return RES_BAD_ARG; - if(prim->igeom__ == RTC_INVALID_GEOMETRY_ID) { - mesh = (struct mesh*)prim->ptr__; + if(prim->inst__ == NULL) { + mesh = (struct mesh*)prim->mesh__; } else { - const struct instance* inst = (const struct instance*)prim->ptr__; + const struct instance* inst = (const struct instance*)prim->inst__; + mesh = (struct mesh*)prim->mesh__; transform = inst->transform; - mesh = scene_get_mesh(inst->scene, prim->igeom__); if(!mesh) { res = RES_BAD_ARG; goto error; diff --git a/src/s3d_sampler.c b/src/s3d_sampler.c @@ -0,0 +1,492 @@ +/* Copyright (C) |Meso|Star> 2015 (contact@meso-star.com) + * + * This software is a computer program whose purpose is to describe a + * virtual 3D environment that can be ray-traced and sampled both robustly + * and efficiently. + * + * This software is governed by the CeCILL license under French law and + * abiding by the rules of distribution of free software. You can use, + * modify and/or redistribute the software under the terms of the CeCILL + * license as circulated by CEA, CNRS and INRIA at the following URL + * "http://www.cecill.info". + * + * As a counterpart to the access to the source code and rights to copy, + * modify and redistribute granted by the license, users are provided only + * with a limited warranty and the software's author, the holder of the + * economic rights, and the successive licensors have only limited + * liability. + * + * In this respect, the user's attention is drawn to the risks associated + * with loading, using, modifying and/or developing or reproducing the + * software by the user in light of its specific status of free software, + * that may mean that it is complicated to manipulate, and that also + * therefore means that it is reserved for developers and experienced + * professionals having in-depth computer knowledge. Users are therefore + * encouraged to load and test the software's suitability as regards their + * requirements in conditions enabling the security of their systems and/or + * data to be ensured and, more generally, to use and operate it in the + * same conditions as regards security. + * + * The fact that you are presently reading this means that you have had + * knowledge of the CeCILL license and that you accept its terms. */ + +#include "s3d_device_c.h" +#include "s3d_scene_c.h" +#include "s3d_shape_c.h" + +#include <rsys/dynamic_array_float.h> +#include <rsys/dynamic_array_size_t.h> +#include <rsys/float33.h> + +#include <algorithm> + +/* The sampler is used to compute uniform random variates of a shape */ +struct s3d_sampler { + struct s3d_shape* shape; /* The shape to sample */ + + /* Register the shape mesh to sample. For a SHAPE_INSTANCE, it lists the + * instantiated shape mesh while for SHAPE_MESH it stores only one mesh, i.e. + * the mesh of the shape. Actually, this cache is synchronised with the shape + * data on s3d_sampler_begin_sampling invocation by creating meshes that get + * a reference onto the shape mesh data. This makes the sampling robust to + * shape updates until the s3d_sampler_end_sampling invocation */ + struct darray_mesh cached_meshes; + + /* Register the shape instance data. If the shape is not a SHAPE_INSTANCE, + * the cached_instance is NULL. The cached instance data are synchronised on + * s3d_sampler_begin_invocation by copying the shape instance data to the + * cache instance. This makes the sampling robust to the updates of shape + * instance data until the s3d_sampler_end_sampling invocation */ + struct instance* cached_instance; + + /* List of cached_mesh CDF ordered with respect to the cached_mesh list, i.e. + * the first value is the CDF of the first cached mesh, the second value the + * CDF of the second cached mesh, etc.*/ + struct darray_float meshes_cdf; + /* Map a cached mesh id to its 1st triangle CDF */ + struct darray_size_t mesh2triangle; + /* List of triangle CDF ordered with respect to the cached_mesh list, i.e. + * the first N values stores the CDF of the N triangles of the first cached + * mesh, the next M values are the CDF of the M triangles of the second + * cached mesh, etc. Use the mesh2triangle data structure to retrieve the + * list of triangle CDF of a specific cached mesh */ + struct darray_float triangles_cdf; + + char is_sync; /* Define if the sampler is in a sampling process */ + ref_T ref; +}; + +/******************************************************************************* + * Helper functions + ******************************************************************************/ +/* The `cache' get a reference onto the `mesh' data. Return 1 if the `cache' + * *geometry* data are updated and 0 otherwise */ +static char +cache_mesh(struct mesh* cache, struct mesh* mesh) +{ + char upd_geom = 0; + size_t i; + ASSERT(cache && mesh); + + /* Get a reference onto the shape mesh indices */ + if(cache->indices != mesh->indices) { + if(cache->indices) { /* Release previous cached indices */ + index_buffer_ref_put(cache->indices); + cache->indices = NULL; + } + index_buffer_ref_get(mesh->indices); + cache->indices = mesh->indices; + upd_geom = 1; + } + + /* Get a reference onto the shape mesh attribs */ + FOR_EACH(i, 0, S3D_ATTRIBS_COUNT__) { + if(cache->attribs[i] == mesh->attribs[i]) + continue; + + if(i == S3D_POSITION) + upd_geom = 1; + + if(cache->attribs[i]) { /* Release previous cached attribs */ + vertex_buffer_ref_put(cache->attribs[i]); + cache->attribs[i] = NULL; + } + + if(!mesh->attribs[i]) + continue; + + vertex_buffer_ref_get(mesh->attribs[i]); + cache->attribs[i] = mesh->attribs[i]; + cache->attribs_type[i] = mesh->attribs_type[i]; + } + return upd_geom; +} + +/* Release all cached meshes */ +static void +sampler_clear_cached_meshes(struct s3d_sampler* sampler) +{ + size_t i = 0; + ASSERT(sampler); + FOR_EACH(i, 0, darray_mesh_size_get(&sampler->cached_meshes)) + mesh_ref_put(darray_mesh_data_get(&sampler->cached_meshes)[i]); + darray_mesh_clear(&sampler->cached_meshes); +} + +/* Clean-up the CDF */ +static void +sampler_clear_cdf(struct s3d_sampler* sampler) +{ + ASSERT(sampler); + darray_float_clear(&sampler->meshes_cdf); + darray_float_clear(&sampler->triangles_cdf); + darray_size_t_clear(&sampler->mesh2triangle); +} + +/* Clean-up the synchronised data */ +static void +sampler_clear(struct s3d_sampler* sampler) +{ + ASSERT(sampler); + sampler_clear_cached_meshes(sampler); + sampler_clear_cdf(sampler); + sampler->is_sync = 0; +} + +/* Compute the CDF of the cached meshes */ +static res_T +sampler_compute_cdf(struct s3d_sampler* sampler) +{ + struct mesh** meshes = NULL; + size_t* mesh2triangle = NULL; + float* meshes_cdf = NULL; + size_t imesh, nmeshes; + size_t itri; + float area = 0.f, rcp_area = 0.f; + res_T res = RES_OK; + ASSERT(sampler); + + /* Fetched cached meshes */ + meshes = darray_mesh_data_get(&sampler->cached_meshes); + nmeshes = darray_mesh_size_get(&sampler->cached_meshes); + + /* Reserve meshes CDF memory space */ + sampler_clear_cdf(sampler); + res = darray_float_resize(&sampler->meshes_cdf, nmeshes); + if(res != RES_OK) goto error; + res = darray_size_t_resize(&sampler->mesh2triangle, nmeshes); + if(res != RES_OK) goto error; + + /* Fetch meshes CDF data */ + meshes_cdf = darray_float_data_get(&sampler->meshes_cdf); + mesh2triangle = darray_size_t_data_get(&sampler->mesh2triangle); + + FOR_EACH(imesh, 0, nmeshes) { + const size_t ntris = mesh_get_ntris(meshes[imesh]); + const uint32_t* ids = mesh_get_ids(meshes[imesh]); + const float* verts = mesh_get_pos(meshes[imesh]); + + mesh2triangle[imesh] = darray_float_size_get(&sampler->triangles_cdf); + res = darray_float_reserve + (&sampler->triangles_cdf, mesh2triangle[imesh] + ntris); + if(res != RES_OK) goto error; + + FOR_EACH(itri, 0, ntris ) { + int i; + const float* positions[3]; + float edges[2][3], normal[3]; + float triangle_area; + + FOR_EACH(i, 0, 3) { /* Fetch vertex positions */ + const uint32_t id = ids[itri*3 + i]; + ASSERT(id < mesh_get_nverts(meshes[imesh])); + positions[i] = verts + id * 3/*#coords*/; + } + /* Compute triangle area. Note that actually, we compute the double of + * the triangle area since it saves computation times whithout affecting + * the sampling result */ + f3_sub(edges[0], positions[1], positions[0]); + f3_sub(edges[1], positions[2], positions[2]); + f3_cross(normal, edges[0], edges[1]); + triangle_area = f3_len(normal); + + /* Store the CDF value of the triangle `itri' */ + area += triangle_area; + darray_float_push_back(&sampler->triangles_cdf, &area); + } + /* Store the CDF value of the mesh `imesh' */ + meshes_cdf[imesh] = area; + } + + /* Normalize the meshes/triangles CDF */ + rcp_area = 1.f / area; + FOR_EACH(imesh, 0, nmeshes) { + meshes_cdf[imesh] *= rcp_area; + } + FOR_EACH(itri, 0, darray_float_size_get(&sampler->triangles_cdf)) { + darray_float_data_get(&sampler->triangles_cdf)[itri] *= rcp_area; + } + +exit: + return res; +error: + sampler_clear_cdf(sampler); + goto exit; +} + +/* Cache the sampler shape mesh */ +static res_T +sampler_cache_mesh(struct s3d_sampler* sampler, char* upd_geom) +{ + struct mesh* mesh; + res_T res = RES_OK; + ASSERT(sampler && sampler->shape->type == SHAPE_MESH && upd_geom); + + if(darray_mesh_size_get(&sampler->cached_meshes)) { + /* Fetch the cached entry */ + mesh = darray_mesh_data_get(&sampler->cached_meshes)[0]; + } else { + /* 1st sync process => create the cached entry */ + res = mesh_create(sampler->shape->dev, &mesh); + if(res != RES_OK) goto error; + res = darray_mesh_push_back(&sampler->cached_meshes, &mesh); + if(res != RES_OK) goto error; + } + /* Cache the instance mesh data */ + *upd_geom = cache_mesh(mesh, sampler->shape->data.mesh); + +exit: + return res; +error: + sampler_clear_cached_meshes(sampler); + goto exit; +} + +/* Cache the sampler instance */ +static res_T +sampler_cache_instance(struct s3d_sampler* sampler, char* upd_geom) +{ + struct list_node* node; + struct mesh* mesh; + size_t ishape = 0; + size_t nshapes; + res_T res = RES_OK; + ASSERT(sampler && sampler->shape->type == SHAPE_INSTANCE && upd_geom); + + f33_set /* Cache the instance rotation */ + (sampler->cached_instance->transform, + sampler->shape->data.instance->transform); + f3_set /* Cache the instance translation */ + (sampler->cached_instance->transform + 9, + sampler->shape->data.instance->transform + 9); + + LIST_FOR_EACH(node, &sampler->shape->data.instance->scene->shapes) { + struct s3d_shape* shape = CONTAINER_OF + (node, struct s3d_shape, scene_attachment); + ASSERT(shape->type == SHAPE_MESH); + + if(ishape <= darray_mesh_size_get(&sampler->cached_meshes)) { + /* Fetch the previous cache entry */ + mesh = darray_mesh_data_get(&sampler->cached_meshes)[ishape]; + } else { + /* Create a new cache entry */ + res = mesh_create(sampler->shape->dev, &mesh); + if(res != RES_OK) goto error; + res = darray_mesh_push_back(&sampler->cached_meshes, &mesh); + if(res != RES_OK) goto error; + } + /* Cache the instance mesh data */ + *upd_geom = *upd_geom || cache_mesh(mesh, shape->data.mesh); + } + nshapes = ishape; + + /* Flush the "no more in use" cache entries */ + FOR_EACH(ishape, ishape, darray_mesh_size_get(&sampler->cached_meshes)) + mesh_ref_put(darray_mesh_data_get(&sampler->cached_meshes)[ishape]); + darray_mesh_resize(&sampler->cached_meshes, nshapes); + + *upd_geom = *upd_geom || (nshapes != ishape); + +exit: + return res; +error: + sampler_clear_cached_meshes(sampler); + goto exit; +} + +/* Synchronise the sampler with the shape data */ +static res_T +sampler_sync(struct s3d_sampler* sampler) +{ + char upd_geom = 0; + res_T res = RES_OK; + ASSERT(sampler); + + if(sampler->is_sync) + return RES_BAD_OP; + + switch(sampler->shape->type) { + case SHAPE_MESH: sampler_cache_mesh(sampler, &upd_geom); break; + case SHAPE_INSTANCE: sampler_cache_instance(sampler, &upd_geom); break; + default: FATAL("Unreachable code\n"); break; + } + + if(upd_geom) { + res = sampler_compute_cdf(sampler); + if(res != RES_OK) goto error; + } + sampler->is_sync = 1; + +exit: + return res; +error: + sampler_clear_cached_meshes(sampler); + goto exit; +} + +static void +sampler_release(ref_T* ref) +{ + struct s3d_sampler* sampler; + struct s3d_shape* shape; + + ASSERT(ref); + sampler = CONTAINER_OF(ref, struct s3d_sampler, ref); + shape = sampler->shape; + + sampler_clear_cached_meshes(sampler); + darray_mesh_release(&sampler->cached_meshes); + darray_float_release(&sampler->triangles_cdf); + darray_float_release(&sampler->meshes_cdf); + darray_size_t_release(&sampler->mesh2triangle); + + if(sampler->cached_instance) + instance_ref_put(sampler->cached_instance); + + MEM_FREE(shape->dev->allocator, sampler); + S3D(shape_ref_put(shape)); +} + +/******************************************************************************* + * Exported functions + ******************************************************************************/ +res_T +s3d_sampler_create(struct s3d_shape* shape, struct s3d_sampler** out_sampler) +{ + struct s3d_sampler* sampler = NULL; + res_T res = RES_OK; + + if(!out_sampler || !shape) { + res = RES_BAD_ARG; + goto error; + } + sampler = (struct s3d_sampler*) + MEM_CALLOC(shape->dev->allocator, 1, sizeof(struct s3d_sampler)); + if(!sampler) { + res = RES_MEM_ERR; + goto error; + } + ref_init(&sampler->ref); + S3D(shape_ref_get(shape)); + sampler->shape = shape; + darray_mesh_init(shape->dev->allocator, &sampler->cached_meshes); + darray_float_init(shape->dev->allocator, &sampler->triangles_cdf); + darray_float_init(shape->dev->allocator, &sampler->meshes_cdf); + darray_size_t_init(shape->dev->allocator, &sampler->mesh2triangle); + + if(shape->type == SHAPE_INSTANCE) { + res = instance_create(shape->data.instance->scene, &sampler->cached_instance); + if(res != RES_OK) goto error; + } + +exit: + if(out_sampler) *out_sampler = sampler; + return res; +error: + if(sampler) { + S3D(sampler_ref_put(sampler)); + sampler = NULL; + } + goto exit; +} + +res_T +s3d_sampler_ref_get(struct s3d_sampler* sampler) +{ + if(!sampler) return RES_BAD_ARG; + ref_get(&sampler->ref); + return RES_OK; +} + +res_T +s3d_sampler_ref_put(struct s3d_sampler* sampler) +{ + if(!sampler) return RES_BAD_ARG; + ref_put(&sampler->ref, sampler_release); + return RES_OK; +} + +res_T +s3d_sampler_begin_sampling(struct s3d_sampler* sampler) +{ + if(!sampler) return RES_BAD_ARG; + return sampler_sync(sampler); +} + +res_T +s3d_sampler_end_sampling(struct s3d_sampler* sampler) +{ + if(!sampler) return RES_BAD_ARG; + sampler_clear(sampler); + return RES_OK; +} + +res_T +s3d_sampler_get + (struct s3d_sampler* sampler, + const float u, const float v, const float w, + struct s3d_primitive* primitive, /* sampled primitive */ + float uv[2]) +{ + const float* cdf_start = NULL; + const float* cdf_stop = NULL; + const float* cdf_found = NULL; + struct mesh* mesh = NULL; + size_t imesh; + size_t imesh2tri; + res_T res = RES_OK; + + if(!sampler || !primitive || !uv) { + res = RES_BAD_ARG; + goto error; + } + + /* Find which mesh is sampled */ + cdf_start = darray_float_cdata_get(&sampler->meshes_cdf); + cdf_stop = cdf_start + darray_float_size_get(&sampler->triangles_cdf); + cdf_found = std::lower_bound(cdf_start, cdf_stop, u); + ASSERT(cdf_found != cdf_stop); + + imesh = cdf_found - cdf_start; + imesh2tri = darray_size_t_data_get(&sampler->mesh2triangle)[imesh]; + mesh = darray_mesh_data_get(&sampler->cached_meshes)[imesh]; + + /* Find which triangle is sampled into the mesh */ + cdf_start = darray_float_cdata_get(&sampler->triangles_cdf) + imesh2tri; + cdf_stop = cdf_start + mesh_get_ntris(mesh); + cdf_found = std::lower_bound(cdf_start, cdf_stop, u); + ASSERT(cdf_found != cdf_stop); + + primitive->mesh__ = mesh; + primitive->inst__ = sampler->cached_instance; + primitive->iprim__ = (unsigned)(cdf_found - cdf_start); + + /* TODO sample the triangle */ + (void)v, (void)w; + +exit: + return res; +error: + goto exit; +} + diff --git a/src/s3d_scene.c b/src/s3d_scene.c @@ -273,7 +273,6 @@ scene_setup_shape_instance(struct s3d_scene* scn, struct s3d_shape* shape) if(res != RES_OK) goto error; res = htable_inst_set(&scn->cached_instances, &shape, &inst); if(res != RES_OK) goto error; - } ASSERT(inst->scene == shape->data.instance->scene); f33_set(inst->transform, shape->data.instance->transform); @@ -636,14 +635,16 @@ s3d_scene_trace_ray if((unsigned)ray.instID == RTC_INVALID_GEOMETRY_ID) { ASSERT((unsigned)ray.geomID < darray_mesh_size_get(&scn->meshes)); - hit->prim.ptr__ = darray_mesh_data_get(&scn->meshes)[ray.geomID]; + hit->prim.mesh__ = darray_mesh_data_get(&scn->meshes)[ray.geomID]; + hit->prim.inst__ = NULL; hit->prim.iprim__ = ray.primID; - hit->prim.igeom__ = RTC_INVALID_GEOMETRY_ID; } else { /* The hit shape is instantiated */ /* Retrieve the hit instance */ + struct instance* instance; ASSERT((unsigned)ray.instID < darray_inst_size_get(&scn->instances)); - hit->prim.ptr__ = darray_inst_data_get(&scn->instances)[ray.instID]; - hit->prim.igeom__ = ray.geomID; + instance = darray_inst_data_get(&scn->instances)[ray.instID]; + hit->prim.mesh__ = scene_get_mesh(instance->scene, ray.geomID); + hit->prim.inst__ = instance; hit->prim.iprim__ = ray.primID; } } diff --git a/src/s3d_shape.c b/src/s3d_shape.c @@ -202,21 +202,6 @@ s3d_shape_is_attached(struct s3d_shape* shape, char* is_attached) } res_T -s3d_shape_sample - (struct s3d_shape* shape, - const float u, const float v, const float w, - unsigned iprim[2], - float uv[2]) -{ - if(!shape || !iprim || !uv) - return RES_BAD_ARG; - /* TODO */ - (void)u, (void)v, (void)w; - ASSERT(0); - return RES_OK; -} - -res_T s3d_instance_set_position (struct s3d_shape* shape, const float position[3]) {