commit d3bee41ff5362004ccd0879177100e960166317a
parent 82dc8990419d2d5329110828b63e8a303b83b1ee
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Tue, 27 Feb 2018 14:06:21 +0100
Merge branch 'feature_openmp' into develop
Diffstat:
13 files changed, 445 insertions(+), 378 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -26,6 +26,7 @@ option(NO_TEST "Do not build tests" OFF)
find_package(RCMake 0.4 REQUIRED)
find_package(Star3D 0.5 REQUIRED)
find_package(RSys 0.6.1 REQUIRED)
+find_package(OpenMP 1.2 REQUIRED)
if(NOT NO_TEST)
find_package(StarSP 0.7 REQUIRED)
@@ -81,11 +82,12 @@ target_link_libraries(senc RSys Star3D)
set_target_properties(senc PROPERTIES
DEFINE_SYMBOL SENC_SHARED_BUILD
VERSION ${VERSION}
+ COMPILE_FLAGS ${OpenMP_C_FLAGS}
SOVERSION ${VERSION_MAJOR})
rcmake_copy_runtime_libraries(senc)
if(CMAKE_COMPILER_IS_GNUCC)
- set_target_properties(senc PROPERTIES LINK_FLAGS "-lm")
+ set_target_properties(senc PROPERTIES LINK_FLAGS "${OpenMP_C_FLAGS} -lm")
endif()
rcmake_setup_devel(senc StarEnc ${VERSION} senc_version.h)
diff --git a/src/senc.h b/src/senc.h
@@ -78,12 +78,14 @@ BEGIN_DECLS
/*******************************************************************************
* StarEnclosures device. It is an handle toward the StarEnc library.
* It manages the lib resources.
+ * If provided, the allocator has to be suitable for parallel high frequency
+ * allocations. As a consequence, a rsys proxy allocator should be avoided.
******************************************************************************/
SENC_API res_T
senc_device_create
(struct logger* logger, /* May be NULL <=> use default logger */
struct mem_allocator* allocator, /* May be NULL <=> use default allocator */
- const unsigned nthreads_hint, /* UNUSED */
+ const unsigned nthreads_hint,
const int verbose,
struct senc_device** device);
diff --git a/src/senc_descriptor.c b/src/senc_descriptor.c
@@ -48,21 +48,26 @@ struct senc_descriptor*
descriptor_create(struct senc_scene* scn)
{
struct senc_descriptor* desc;
+ res_T res = RES_OK;
ASSERT(scn);
desc = MEM_CALLOC(scn->dev->allocator, 1, sizeof(struct senc_descriptor));
if(desc) {
desc->scene = scn;
SENC(scene_ref_get(desc->scene));
+ ref_init(&desc->ref);
darray_triangle_enc_init(scn->dev->allocator, &desc->triangles_enc);
/* Enclosure 0 is always defined for infinite */
darray_enclosure_init(scn->dev->allocator, &desc->enclosures);
- darray_enclosure_resize(&desc->enclosures, 1);
+ OK(darray_enclosure_resize(&desc->enclosures, 1));
desc->enclosures_count = 1;
desc->triangle_count = scn->nutris;
desc->vertices_count = scn->nuverts;
- ref_init(&desc->ref);
}
+end:
return desc;
+error:
+ if(desc) SENC(descriptor_ref_put(desc));
+ goto end;
}
struct mem_allocator*
diff --git a/src/senc_device.c b/src/senc_device.c
@@ -19,6 +19,8 @@
#include <rsys/logger.h>
#include <rsys/mem_allocator.h>
+#include <omp.h>
+
/*******************************************************************************
* Helper functions
******************************************************************************/
@@ -104,6 +106,8 @@ senc_device_create
dev->logger = log;
dev->allocator = allocator;
dev->verbose = verbose;
+ dev->nthreads = MMIN(nthreads_hint, (unsigned)omp_get_num_procs());
+ omp_set_num_threads((int)dev->nthreads);
ref_init(&dev->ref);
exit:
diff --git a/src/senc_device_c.h b/src/senc_device_c.h
@@ -19,10 +19,6 @@
#include <rsys/free_list.h>
#include <rsys/ref_count.h>
-#define OK(expr)\
- res = expr;\
- if(res != RES_OK) goto error;
-
struct name { FITEM; };
#define FITEM_TYPE name
#include <rsys/free_list.h>
@@ -31,6 +27,7 @@ struct senc_device {
struct logger* logger;
struct mem_allocator* allocator;
int verbose;
+ unsigned nthreads;
ref_T ref;
};
diff --git a/src/senc_enclosure_data.h b/src/senc_enclosure_data.h
@@ -41,14 +41,23 @@ struct enclosure_data {
struct darray_triangle_in sides;
/* Index of vertices in scene's unique vertices */
struct darray_vrtx_id vertices;
+ /* TODO: use only 1 bit per side (now 1 char per triangle) */
+ struct darray_char side_membership;
+ /* Number of components involved in this enclosure */
+ component_id_t cc_count;
+ /* Linked list of the components */
+ component_id_t first_component;
};
static FINLINE void
enclosure_data_init(struct mem_allocator* alloc, struct enclosure_data* enc) {
ASSERT(enc);
init_header(&enc->header);
+ enc->cc_count = 0;
+ enc->first_component = COMPONENT_NULL__;
darray_triangle_in_init(alloc, &enc->sides);
darray_vrtx_id_init(alloc, &enc->vertices);
+ darray_char_init(alloc, &enc->side_membership);
}
static FINLINE res_T
@@ -59,9 +68,13 @@ enclosure_data_copy
res_T res = RES_OK;
ASSERT(src && dst);
dst->header = src->header;
- res = darray_triangle_in_copy(&dst->sides, &src->sides);
- if(res != RES_OK) return res;
- return darray_vrtx_id_copy(&dst->vertices, &src->vertices);
+ dst->cc_count = src->cc_count;
+ dst->first_component = src->first_component;
+ OK(darray_triangle_in_copy(&dst->sides, &src->sides));
+ OK(darray_vrtx_id_copy(&dst->vertices, &src->vertices));
+ OK(darray_char_copy(&dst->side_membership, &src->side_membership));
+error:
+ return res;
}
static FINLINE void
@@ -69,6 +82,7 @@ enclosure_data_release(struct enclosure_data* n) {
ASSERT(n);
darray_triangle_in_release(&n->sides);
darray_vrtx_id_release(&n->vertices);
+ darray_char_release(&n->side_membership);
}
static FINLINE res_T
@@ -79,9 +93,13 @@ enclosure_data_copy_and_release
res_T res = RES_OK;
ASSERT(src && dst);
dst->header = src->header;
- res = darray_triangle_in_copy_and_release(&dst->sides, &src->sides);
- if(res != RES_OK) return res;
- return darray_vrtx_id_copy_and_release(&dst->vertices, &src->vertices);
+ dst->cc_count = src->cc_count;
+ dst->first_component = src->first_component;
+ OK(darray_triangle_in_copy_and_release(&dst->sides, &src->sides));
+ OK(darray_vrtx_id_copy_and_release(&dst->vertices, &src->vertices));
+ OK(darray_char_copy(&dst->side_membership, &src->side_membership));
+error:
+ return res;
}
#endif /* SENC_ENCLOSURE_DATA_H */
diff --git a/src/senc_internal_types.h b/src/senc_internal_types.h
@@ -20,6 +20,13 @@
#include <stdint.h>
+/* Utility macros */
+#define OK2(Expr, Label)\
+ res = (Expr);\
+ if(res != RES_OK) goto Label;
+
+#define OK(Expr) OK2((Expr), error)
+
/* Side IDs are uint32_t */
typedef uint32_t side_id_t;
#define SIDE_MAX__ (UINT32_MAX-1)
diff --git a/src/senc_scene.c b/src/senc_scene.c
@@ -141,8 +141,7 @@ senc_scene_add_geometry
} else {
/* New vertex */
unique_v = scn->nuverts + actual_nuverts;
- res = darray_position_push_back(&scn->vertices, &tmp);
- if(res != RES_OK) goto error;
+ OK(darray_position_push_back(&scn->vertices, &tmp));
ASSERT(unique_v == htable_vrtx_size_get(&scn->unique_vertices));
OK(htable_vrtx_set(&scn->unique_vertices, &tmp, &unique_v));
++actual_nuverts;
@@ -248,8 +247,7 @@ senc_scene_add_geometry
}
}
}
- }
- else {
+ } else {
/* New triangle */
trg_id_t u = scn->nutris + actual_nutris;
ASSERT(u == htable_trg_size_get(&scn->unique_triangles));
diff --git a/src/senc_scene_analyze.c b/src/senc_scene_analyze.c
@@ -29,12 +29,14 @@
#include <star/s3d.h>
+#include <omp.h>
#include <limits.h>
#include <stdlib.h>
#define CC_DESCRIPTOR_NULL__ {\
{0,0,-DBL_MAX}, -1, SIDE_NULL__, VRTX_NULL__, 0, MEDIUM_NULL__,\
- CC_ID_NONE, CC_GROUP_ROOT_NONE, CC_GROUP_ID_NONE\
+ CC_ID_NONE, CC_GROUP_ROOT_NONE, CC_GROUP_ID_NONE, CC_ID_NONE, TRG_NULL__,\
+ TRG_NULL__\
}
const struct cc_descriptor CC_DESCRIPTOR_NULL = CC_DESCRIPTOR_NULL__;
@@ -170,11 +172,9 @@ find_component_Zmax
if(cc->max_vrtx[2] < trg_tmp->max_z) {
change = 1; /* Try first to improve z */
- }
- else if(cc->max_z_nz <= 0 && fabs(cc->max_z_nz) < fabs(side_nz)) {
+ } else if(cc->max_z_nz <= 0 && fabs(cc->max_z_nz) < fabs(side_nz)) {
change = 1; /* If nz <= 0, the more negative the better */
- }
- else if(cc->max_z_nz > 0 && cc->max_z_nz < side_nz) {
+ } else if(cc->max_z_nz > 0 && cc->max_z_nz < side_nz) {
change = 1; /* If nz > 0, the more positive the better */
}
if(change) {
@@ -247,13 +247,12 @@ extract_connex_components
{
res_T res = RES_OK;
medium_id_t m;
- size_t tmp;
struct senc_scene* scn;
struct mem_allocator* alloc;
struct darray_side_id stack;
/* Id of the first trgside not already in a connex component */
side_id_t first_side_not_in_component = 0;
- struct cc_descriptor current_cc;
+ struct cc_descriptor* current_cc;
ASSERT(trgsides && desc && connex_components && triangles_tmp_array);
@@ -263,32 +262,35 @@ extract_connex_components
/* Init stack */
darray_side_id_init(alloc, &stack);
- /* Extract connex components until every side is involved */
- cc_descriptor_init(alloc, ¤t_cc);
for(;;) {
/* Any not-already-used side is used as a starting point */
const side_id_t start_side_id = get_side_not_in_connex_component(scn,
trgsides, &first_side_not_in_component);
side_id_t crt_side_id = start_side_id;
+ side_id_t last_side_id = start_side_id;
char* side_membership;
+ size_t sz;
ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nutris);
if(start_side_id == SIDE_NULL__)
break; /* start_side_id=SIDE_NULL__ => done! */
ASSERT(trgsides[start_side_id].list_id == FLAG_LIST_SIDE_LIST);
- m = trgsides[start_side_id].medium;
-
- /* Reset CC data for a new CC */
- tmp = darray_cc_descriptor_size_get(connex_components);
- ASSERT(tmp <= COMPONENT_MAX__);
- cc_descriptor_clear(¤t_cc);
- /* 1 char per triangle (2 sides) */
- darray_char_resize(¤t_cc.side_membership, scn->nutris);
- side_membership = darray_char_data_get(¤t_cc.side_membership);
+ /* Create and init a new component */
+ sz = darray_cc_descriptor_size_get(connex_components);
+ OK(darray_cc_descriptor_resize(connex_components, 1+ sz));
+ current_cc = darray_cc_descriptor_data_get(connex_components) + sz;
+ /* 1 char per triangle (2 sides); allow uint64_t* access */
+ OK(darray_char_reserve(¤t_cc->side_membership,
+ ((scn->nutris + 7) / 8) * 8));
+ OK(darray_char_resize(¤t_cc->side_membership, scn->nutris));
+ side_membership = darray_char_data_get(¤t_cc->side_membership);
memset(side_membership, 0, scn->nutris * sizeof(char));
- current_cc.cc_id = (component_id_t)tmp;
- current_cc.medium = m;
+ m = trgsides[start_side_id].medium;
+ ASSERT(sz <= COMPONENT_MAX__);
+ current_cc->cc_id = (component_id_t)sz;
+ current_cc->medium = m;
+ current_cc->first_member_id = TRGSIDE_2_TRG(start_side_id);
for(;;) {
int i;
@@ -301,21 +303,21 @@ extract_connex_components
ASSERT(trgsides[crt_side_id].medium == m);
/* Record crt_side both as component and triangle level */
- current_cc.side_count++;
+ current_cc->side_count++;
trgsides[crt_side_id].list_id = FLAG_LIST_COMPONENT;
if(TRGSIDE_IS_FRONT(crt_side_id)) {
ASSERT(trg_comp->component[SIDE_FRONT] == USHRT_MAX);
- trg_comp->component[SIDE_FRONT] = current_cc.cc_id;
+ trg_comp->component[SIDE_FRONT] = current_cc->cc_id;
ASSERT(!(side_membership[crt_trg_id] & FLAG_FRONT));
side_membership[crt_trg_id] |= FLAG_FRONT;
} else {
ASSERT(trg_comp->component[SIDE_BACK] == USHRT_MAX);
- trg_comp->component[SIDE_BACK] = current_cc.cc_id;
+ trg_comp->component[SIDE_BACK] = current_cc->cc_id;
ASSERT(!(side_membership[crt_trg_id] & FLAG_BACK));
side_membership[crt_trg_id] |= FLAG_BACK;
}
#ifndef NDEBUG
- crt_side->member_of_cc = current_cc.cc_id;
+ crt_side->member_of_cc = current_cc->cc_id;
#endif
/* Store neighbour sides in a waiting stack */
FOR_EACH(i, 0, 3) {
@@ -350,13 +352,12 @@ extract_connex_components
log_err(desc->scene->dev, "Media: %lu VS %lu\n",
neighbour->medium, crt_side->medium);
res = RES_BAD_ARG;
- cc_descriptor_release(¤t_cc);
goto error;
}
if(neighbour->list_id == FLAG_LIST_COMPONENT) {
/* Already processed */
#ifndef NDEBUG
- ASSERT(neighbour->member_of_cc == current_cc.cc_id);
+ ASSERT(neighbour->member_of_cc == current_cc->cc_id);
#endif
continue;
}
@@ -368,12 +369,12 @@ extract_connex_components
if(darray_side_id_size_get(&stack) == 0)
break; /* Empty stack => connex component is done! */
crt_side_id = get_side_from_stack(trgsides, &stack);
+ last_side_id = MMAX(last_side_id, crt_side_id);
}
/* Keep track of this new connex component */
- find_component_Zmax(scn, triangles_tmp_array, ¤t_cc);
- darray_cc_descriptor_push_back(connex_components, ¤t_cc);
+ find_component_Zmax(scn, triangles_tmp_array, current_cc);
+ current_cc->last_member_id = TRGSIDE_2_TRG(last_side_id);
}
- cc_descriptor_release(¤t_cc);
exit:
darray_side_id_release(&stack);
@@ -453,6 +454,7 @@ group_connex_components
side_id_t infinite_medium_first_side = SIDE_MAX__;
char infinite_medium_is_known = 0;
(void)trgsides;
+ ASSERT(desc && trgsides && triangles_comp && connex_components);
alloc = descriptor_get_allocator(desc);
descriptors = darray_cc_descriptor_data_get(connex_components);
@@ -587,8 +589,7 @@ group_connex_components
}
#endif
if(hit_trg_in->medium[hit_side] != cc->medium) {
- /* Medium mismatch!
- * Model topology is broken. */
+ /* Medium mismatch! Model topology is broken. */
const trg_id_t t1 = TRGSIDE_2_TRG(hit_side_id);
const trg_id_t t2 = TRGSIDE_2_TRG(hit_side);
const struct triangle_in* triangles_in
@@ -623,9 +624,13 @@ group_connex_components
}
/* Post-process links to group connex components */
+ OK(darray_enclosure_resize(&desc->enclosures, desc->enclosures_count));
FOR_EACH(c, 0, cc_count) {
struct cc_descriptor* const cc = descriptors + c;
const struct cc_descriptor* other_desc = cc;
+ struct enclosure_data* enclosures
+ = darray_enclosure_data_get(&desc->enclosures);
+ component_id_t fst;
while(other_desc->enclosure_id == CC_GROUP_ID_NONE) {
other_desc = darray_cc_descriptor_cdata_get(connex_components)
@@ -635,6 +640,11 @@ group_connex_components
ASSERT(other_desc->enclosure_id != CC_GROUP_ID_NONE);
cc->cc_group_root = other_desc->cc_group_root;
cc->enclosure_id = other_desc->enclosure_id;
+ ++enclosures[cc->enclosure_id].cc_count;
+ /* Linked list of componnents */
+ fst = enclosures[cc->enclosure_id].first_component;
+ cc->next_component = fst;
+ enclosures[cc->enclosure_id].first_component = cc->cc_id;
}
exit:
@@ -649,207 +659,214 @@ error:
}
static res_T
-scan_edges
- (struct senc_scene* scn,
- struct darray_neighbourhood* neighbourhood_by_edge,
- struct darray_triangle_tmp* triangles_tmp_array)
-{
- trg_id_t t;
- const struct triangle_in *triangles_in;
- struct triangle_tmp *triangles_tmp;
- edge_id_t max_nbedges;
- /* Htable used to give an id to edges */
- struct htable_edge_id edge_ids;
- res_T res = RES_OK;
-
- ASSERT(scn && neighbourhood_by_edge && triangles_tmp_array);
- ASSERT((size_t)scn->nuverts + (size_t)scn->nutris + 2 <= EDGE_MAX__);
-
- /* Make some room for edges. */
- max_nbedges = (edge_id_t)(scn->nuverts + scn->nutris + 2);
- htable_edge_id_init(scn->dev->allocator, &edge_ids);
- OK(htable_edge_id_reserve(&edge_ids, max_nbedges));
- OK(darray_neighbourhood_reserve(neighbourhood_by_edge, max_nbedges));
- OK(darray_triangle_tmp_resize(triangles_tmp_array, scn->nutris));
-
- /* Loop on triangles to register edges. */
- triangles_in = darray_triangle_in_cdata_get(&scn->triangles_in);
- triangles_tmp = darray_triangle_tmp_data_get(triangles_tmp_array);
- ASSERT(scn->nutris == darray_triangle_tmp_size_get(triangles_tmp_array));
- FOR_EACH(t, 0, scn->nutris) {
- struct darray_neighbour* neighbour_list;
- struct neighbour_info neighbour;
- struct edge_neighbourhood neighbourhood;
- char e;
- FOR_EACH(e, 0, 3) {
- edge_id_t* p_id;
- edge_id_t id;
-
- /* Create edge. */
- set_edge(triangles_in[t].vertice_id[e],
- triangles_in[t].vertice_id[(e + 1) % 3],
- &neighbourhood.edge, &triangles_tmp[t].reversed_edge[e]);
- /* Find edge id; create it if not already done. */
- p_id = htable_edge_id_find(&edge_ids, &neighbourhood.edge);
-
- if(p_id) {
- id = *p_id;
- } else {
- /* Create id */
- size_t tmp;
- tmp = htable_edge_id_size_get(&edge_ids);
- ASSERT(tmp <= EDGE_MAX__);
- id = (edge_id_t)tmp;
- OK(htable_edge_id_set(&edge_ids, &neighbourhood.edge, &id));
- darray_neighbour_init(scn->dev->allocator, &neighbourhood.neighbours);
- OK(darray_neighbourhood_push_back(neighbourhood_by_edge,
- &neighbourhood));
- }
- /* Add neighbour info to edge's neighbour list */
- neighbour_list
- = &darray_neighbourhood_data_get(neighbourhood_by_edge)[id].neighbours;
- neighbour.trg_id = t;
- neighbour.edge_rank = e;
- darray_neighbour_push_back(neighbour_list, &neighbour);
- }
- }
-
-exit:
- htable_edge_id_release(&edge_ids);
- return res;
-error:
- goto exit;
-}
-
-static res_T
-link_neighbours
+collect_and_link_neighbours
(struct senc_scene* scn,
struct trgside* trgsides,
- struct darray_neighbourhood* neighbourhood_by_edge,
struct darray_triangle_tmp* triangles_tmp_array)
{
- edge_id_t e, edge_count;
+ res_T res = RES_OK;
const struct triangle_in *triangles_in;
struct triangle_tmp *triangles_tmp;
const union double3* vertices;
- size_t tmp;
- res_T res = RES_OK;
- ASSERT(scn && trgsides && neighbourhood_by_edge && triangles_tmp_array);
+ ASSERT(scn && trgsides && triangles_tmp_array);
+ ASSERT((size_t) scn->nuverts + (size_t) scn->nutris + 2 <= EDGE_MAX__);
- /* Loop on edges.
- * For each edge sort triangle sides by rotation angle
- * and connect neighbours. */
triangles_in = darray_triangle_in_cdata_get(&scn->triangles_in);
triangles_tmp = darray_triangle_tmp_data_get(triangles_tmp_array);
vertices = darray_position_cdata_get(&scn->vertices);
- tmp = darray_neighbourhood_size_get(neighbourhood_by_edge);
- ASSERT(tmp <= EDGE_MAX__);
- edge_count = (edge_id_t)tmp;
-
- FOR_EACH(e, 0, edge_count) {
- double edge[3], common_edge[3], basis[9], norm, mz, mz_edge;
- vrtx_id_t v0, v1, v2;
- struct edge_neighbourhood* neighbourhood
- = darray_neighbourhood_data_get(neighbourhood_by_edge) + e;
- struct darray_neighbour* neighbour_list = &neighbourhood->neighbours;
- side_id_t i, neighbour_count;
- char mz_vid, mz_vid_edge;
- tmp = darray_neighbour_size_get(neighbour_list);
- ASSERT(tmp <= SIDE_MAX__);
- neighbour_count = (side_id_t)tmp;
- ASSERT(neighbour_count);
- v0 = neighbourhood->edge.vrtx0;
- v1 = neighbourhood->edge.vrtx1;
- d3_sub(common_edge, vertices[v1].vec, vertices[v0].vec);
- if(vertices[v0].pos.z > vertices[v1].pos.z) {
- mz_edge = vertices[v0].pos.z;
- mz_vid_edge = 0;
- } else {
- mz_edge = vertices[v1].pos.z;
- mz_vid_edge = 1;
+
+ ASSERT(scn->nutris == darray_triangle_tmp_size_get(triangles_tmp_array));
+
+#pragma omp parallel
+ {
+ const int thread_count = omp_get_num_threads();
+ const int rank = omp_get_thread_num();
+ /* Htable used to give an id to edges */
+ struct htable_edge_id edge_ids;
+ /* Array to keep neighbourhood of edges */
+ struct darray_neighbourhood neighbourhood_by_edge;
+ edge_id_t e, edge_count;
+ edge_id_t nbedges_guess;
+ trg_id_t t;
+ size_t tmp;
+
+ htable_edge_id_init(scn->dev->allocator, &edge_ids);
+ darray_neighbourhood_init(scn->dev->allocator, &neighbourhood_by_edge);
+
+ /* Make some room for edges. */
+ nbedges_guess = 4 + (thread_count == 1
+ ? (edge_id_t) (scn->nuverts + scn->nutris)
+ : (edge_id_t) ((scn->nuverts + scn->nutris) / (0.75 * thread_count)));
+ OK(darray_neighbourhood_reserve(&neighbourhood_by_edge, nbedges_guess));
+ OK(htable_edge_id_reserve(&edge_ids, nbedges_guess));
+
+ /* Loop on triangles to register edges. */
+ FOR_EACH(t, 0, scn->nutris) {
+ struct trg_edge edge;
+ char ee;
+ FOR_EACH(ee, 0, 3) {
+ edge_id_t* p_id;
+ const vrtx_id_t v0 = triangles_in[t].vertice_id[ee];
+ const vrtx_id_t v1 = triangles_in[t].vertice_id[(ee + 1) % 3];
+ /* Process only "my" edges! */
+ const int h =
+ v0 + v1 + MMIN(v0, v1); /* v0,v1 and v1,v0 must give the same hash!!! */
+ if(h % thread_count != rank) continue;
+ /* Create edge. */
+ set_edge(v0, v1, &edge, &triangles_tmp[t].reversed_edge[ee]);
+ /* Find edge id; create it if not already done. */
+ p_id = htable_edge_id_find(&edge_ids, &edge);
+ if(p_id) {
+ struct edge_neighbourhood* n =
+ darray_neighbourhood_data_get(&neighbourhood_by_edge) + *p_id;
+ struct neighbour_info* info;
+ size_t sz;
+ /* Add neighbour info to existing edge's neighbour list */
+ ASSERT(n->edge.vrtx0 == edge.vrtx0 && n->edge.vrtx1 == edge.vrtx1);
+ sz = darray_neighbour_size_get(&n->neighbours);
+ OK(darray_neighbour_resize(&n->neighbours, 1 + sz));
+ info = darray_neighbour_data_get(&n->neighbours) + sz;
+ info->trg_id = t;
+ info->edge_rank = ee;
+ } else {
+ /* Create id */
+ edge_id_t id;
+ struct edge_neighbourhood* n;
+ struct neighbour_info* info;
+ size_t sz = htable_edge_id_size_get(&edge_ids);
+ ASSERT(sz <= EDGE_MAX__);
+ id = (edge_id_t) sz;
+ ASSERT(htable_edge_id_size_get(&edge_ids)
+ == darray_neighbourhood_size_get(&neighbourhood_by_edge));
+ OK(htable_edge_id_set(&edge_ids, &edge, &id));
+ OK(darray_neighbourhood_resize(&neighbourhood_by_edge, 1 + sz));
+ n = darray_neighbourhood_data_get(&neighbourhood_by_edge) + sz;
+ /* Add neighbour info to a newly created edge's neighbour list */
+ n->edge = edge;
+ ASSERT(darray_neighbour_size_get(&n->neighbours) == 0);
+ OK(darray_neighbour_reserve(&n->neighbours, 2));
+ OK(darray_neighbour_resize(&n->neighbours, 1));
+ info = darray_neighbour_data_get(&n->neighbours);
+ info->trg_id = t;
+ info->edge_rank = ee;
+ }
+ }
}
- norm = d3_normalize(common_edge, common_edge);
- ASSERT(norm);
- d33_basis(basis, common_edge);
- d33_inverse(basis, basis);
- FOR_EACH(i, 0, neighbour_count) {
- struct neighbour_info* neighbour_info
- = darray_neighbour_data_get(neighbour_list) + i;
- const struct triangle_in *trg_in = triangles_in + neighbour_info->trg_id;
- struct triangle_tmp *neighbour = triangles_tmp + neighbour_info->trg_id;
- char actual_vid;
- v2 = trg_in->vertice_id[(neighbour_info->edge_rank + 2) % 3];
- if(vertices[v2].pos.z > mz_edge) {
- mz = vertices[v2].pos.z;
- mz_vid = 2;
+
+ /* Loop on collected edges.
+ * For each edge sort triangle sides by rotation angle
+ * and connect neighbours. */
+ tmp = darray_neighbourhood_size_get(&neighbourhood_by_edge);
+ ASSERT(tmp <= EDGE_MAX__);
+ edge_count = (edge_id_t) tmp;
+ FOR_EACH(e, 0, edge_count) {
+ double edge[3], common_edge[3], basis[9], norm, mz, mz_edge;
+ vrtx_id_t v0, v1, v2;
+ struct edge_neighbourhood* neighbourhood
+ = darray_neighbourhood_data_get(&neighbourhood_by_edge) + e;
+ struct darray_neighbour* neighbour_list = &neighbourhood->neighbours;
+ side_id_t i, neighbour_count;
+ char mz_vid, mz_vid_edge;
+ tmp = darray_neighbour_size_get(neighbour_list);
+ ASSERT(tmp <= SIDE_MAX__);
+ neighbour_count = (side_id_t) tmp;
+ ASSERT(neighbour_count);
+ v0 = neighbourhood->edge.vrtx0;
+ v1 = neighbourhood->edge.vrtx1;
+ d3_sub(common_edge, vertices[v1].vec, vertices[v0].vec);
+ if(vertices[v0].pos.z > vertices[v1].pos.z) {
+ mz_edge = vertices[v0].pos.z;
+ mz_vid_edge = 0;
} else {
- mz = mz_edge;
- mz_vid = mz_vid_edge;
+ mz_edge = vertices[v1].pos.z;
+ mz_vid_edge = 1;
}
- /* Compute the actual vertex id
- * as vertices are not in the v0 v1 v2 order in the actual triangle */
- if(mz_vid == 2) {
- actual_vid = (2 + neighbour_info->edge_rank) % 3;
- } else {
- int is_r = neighbour->reversed_edge[neighbour_info->edge_rank];
- ASSERT(mz_vid == 0 || mz_vid == 1);
- actual_vid = ((is_r ? 1 - mz_vid : mz_vid) + neighbour_info->edge_rank) % 3;
+ norm = d3_normalize(common_edge, common_edge);
+ ASSERT(norm);
+ d33_basis(basis, common_edge);
+ d33_inverse(basis, basis);
+ FOR_EACH(i, 0, neighbour_count) {
+ struct neighbour_info* neighbour_info
+ = darray_neighbour_data_get(neighbour_list) + i;
+ const struct triangle_in *trg_in = triangles_in + neighbour_info->trg_id;
+ struct triangle_tmp *neighbour = triangles_tmp + neighbour_info->trg_id;
+ char actual_vid;
+ v2 = trg_in->vertice_id[(neighbour_info->edge_rank + 2) % 3];
+ if(vertices[v2].pos.z > mz_edge) {
+ mz = vertices[v2].pos.z;
+ mz_vid = 2;
+ } else {
+ mz = mz_edge;
+ mz_vid = mz_vid_edge;
+ }
+ /* Compute the actual vertex id
+ * as vertices are not in the v0 v1 v2 order in the actual triangle */
+ if(mz_vid == 2) {
+ actual_vid = (2 + neighbour_info->edge_rank) % 3;
+ } else {
+ int is_r = neighbour->reversed_edge[neighbour_info->edge_rank];
+ ASSERT(mz_vid == 0 || mz_vid == 1);
+ actual_vid = ((is_r ? 1 - mz_vid : mz_vid) + neighbour_info->edge_rank) % 3;
+ }
+ ASSERT(neighbour->max_z <= mz);
+ neighbour->max_z = mz;
+ ASSERT(0 <= actual_vid && actual_vid <= 2);
+ neighbour->max_z_vrtx_id = actual_vid;
+ /* Compute rotation angle around common edge */
+ d3_sub(edge, vertices[v2].vec, vertices[v0].vec);
+ d33_muld3(edge, basis, edge);
+ ASSERT(d3_len(edge) && (edge[0] || edge[1]));
+ neighbour_info->angle = atan2(edge[1], edge[0]);
+ if(neighbour_info->angle < 0) neighbour_info->angle += 2 * PI;
+ /* Due to catastrophic cancelation, -eps+2pi translates to 2pi */
+ ASSERT(0 <= neighbour_info->angle && neighbour_info->angle <= 2 * PI);
+ }
+ /* Sort triangles by rotation angle */
+ qsort(darray_neighbour_data_get(neighbour_list), neighbour_count,
+ sizeof(struct neighbour_info), neighbour_cmp);
+ /* Link sides.
+ * Create cycles of sides by neighbourhood around common edge. */
+ FOR_EACH(i, 0, neighbour_count) {
+ /* Neighbourhood info for current pair of triangles */
+ const struct neighbour_info* current
+ = darray_neighbour_cdata_get(neighbour_list) + i;
+ const struct neighbour_info* ccw_neighbour
+ = darray_neighbour_cdata_get(neighbour_list) + (i + 1) % neighbour_count;
+ /* Rank of the edge of interest in triangles */
+ const char crt_edge = current->edge_rank;
+ const char ccw_edge = ccw_neighbour->edge_rank;
+ /* User id of current triangles */
+ const trg_id_t crt_id = current->trg_id;
+ const trg_id_t ccw_id = ccw_neighbour->trg_id;
+ /* Facing sides of triangles */
+ const enum side_id crt_side
+ = triangles_tmp[crt_id].reversed_edge[crt_edge] ? SIDE_BACK : SIDE_FRONT;
+ const enum side_id ccw_side
+ = triangles_tmp[ccw_id].reversed_edge[ccw_edge] ? SIDE_FRONT : SIDE_BACK;
+ /* Index of sides in trgsides */
+ const side_id_t crt_side_idx = TRGIDxSIDE_2_TRGSIDE(crt_id, crt_side);
+ const side_id_t ccw_side_idx = TRGIDxSIDE_2_TRGSIDE(ccw_id, ccw_side);
+ /* Side ptrs */
+ struct trgside* const p_crt_side = trgsides + crt_side_idx;
+ struct trgside* const p_ccw_side = trgsides + ccw_side_idx;
+ /* Link sides */
+ p_crt_side->facing_side_id[crt_edge] = ccw_side_idx;
+ p_ccw_side->facing_side_id[ccw_edge] = crt_side_idx;
+ /* Record media */
+ p_crt_side->medium = triangles_in[crt_id].medium[crt_side];
+ p_ccw_side->medium = triangles_in[ccw_id].medium[ccw_side];
+ ASSERT(p_crt_side->medium < scn->nmeds);
+ ASSERT(p_ccw_side->medium < scn->nmeds);
+ p_crt_side->list_id = FLAG_LIST_SIDE_LIST;
+ p_ccw_side->list_id = FLAG_LIST_SIDE_LIST;
}
-
- ASSERT(neighbour->max_z <= mz);
- neighbour->max_z = mz;
- ASSERT(0 <= actual_vid && actual_vid <= 2);
- neighbour->max_z_vrtx_id = actual_vid;
- /* Compute rotation angle around common edge */
- d3_sub(edge, vertices[v2].vec, vertices[v0].vec);
- d33_muld3(edge, basis, edge);
- ASSERT(d3_len(edge) && (edge[0] || edge[1]));
- neighbour_info->angle = atan2(edge[1], edge[0]);
- if(neighbour_info->angle < 0) neighbour_info->angle += 2 * PI;
- /* Due to catastrophic cancelation, -eps+2pi translates to 2pi */
- ASSERT(0 <= neighbour_info->angle && neighbour_info->angle <= 2 * PI);
- }
- /* Sort triangles by rotation angle */
- qsort(darray_neighbour_data_get(neighbour_list), neighbour_count,
- sizeof(struct neighbour_info), neighbour_cmp);
- /* Link sides.
- * Create cycles of sides by neighbourhood around common edge. */
- FOR_EACH(i, 0, neighbour_count) {
- /* Neighbourhood info for current pair of triangles */
- const struct neighbour_info* current
- = darray_neighbour_cdata_get(neighbour_list) + i;
- const struct neighbour_info* ccw_neighbour
- = darray_neighbour_cdata_get(neighbour_list) + (i + 1) % neighbour_count;
- /* Rank of the edge of interest in triangles */
- const char crt_edge = current->edge_rank;
- const char ccw_edge = ccw_neighbour->edge_rank;
- /* User id of current triangles */
- const trg_id_t crt_id = current->trg_id;
- const trg_id_t ccw_id = ccw_neighbour->trg_id;
- /* Facing sides of triangles */
- const enum side_id crt_side
- = triangles_tmp[crt_id].reversed_edge[crt_edge] ? SIDE_BACK : SIDE_FRONT;
- const enum side_id ccw_side
- = triangles_tmp[ccw_id].reversed_edge[ccw_edge] ? SIDE_FRONT : SIDE_BACK;
- /* Index of sides in trgsides */
- const side_id_t crt_side_idx = TRGIDxSIDE_2_TRGSIDE(crt_id, crt_side);
- const side_id_t ccw_side_idx = TRGIDxSIDE_2_TRGSIDE(ccw_id, ccw_side);
- /* Side ptrs */
- struct trgside* const p_crt_side = trgsides + crt_side_idx;
- struct trgside* const p_ccw_side = trgsides + ccw_side_idx;
- /* Link sides */
- p_crt_side->facing_side_id[crt_edge] = ccw_side_idx;
- p_ccw_side->facing_side_id[ccw_edge] = crt_side_idx;
- /* Record media */
- p_crt_side->medium = triangles_in[crt_id].medium[crt_side];
- p_ccw_side->medium = triangles_in[ccw_id].medium[ccw_side];
- ASSERT(p_crt_side->medium < scn->nmeds);
- ASSERT(p_ccw_side->medium < scn->nmeds);
- p_crt_side->list_id = FLAG_LIST_SIDE_LIST;
- p_ccw_side->list_id = FLAG_LIST_SIDE_LIST;
}
+error:
+ darray_neighbourhood_release(&neighbourhood_by_edge);
+ htable_edge_id_release(&edge_ids);
}
+
return res;
}
@@ -860,146 +877,151 @@ build_result
{
res_T res = RES_OK;
struct mem_allocator* alloc;
- const struct cc_descriptor* cc_descriptors;
+ struct cc_descriptor* cc_descriptors;
struct enclosure_data* enclosures;
- char* side_membership = NULL;
const struct triangle_in* triangles_in;
struct triangle_enc* triangles_enc;
- struct htable_vrtx_id vtable;
- size_t tmp;
- component_id_t cc_count, c;
- enclosure_id_t e;
- side_id_t* side_counts;
+ int ee;
ASSERT(desc && connex_components);
alloc = descriptor_get_allocator(desc);
- tmp = darray_cc_descriptor_size_get(connex_components);
- ASSERT(tmp < COMPONENT_MAX__);
- cc_count = (component_id_t)tmp;
- cc_descriptors = darray_cc_descriptor_cdata_get(connex_components);
- darray_enclosure_resize(&desc->enclosures, desc->enclosures_count);
+ ASSERT(darray_cc_descriptor_size_get(connex_components) < COMPONENT_MAX__);
+ cc_descriptors = darray_cc_descriptor_data_get(connex_components);
enclosures = darray_enclosure_data_get(&desc->enclosures);
triangles_in = darray_triangle_in_cdata_get(&desc->scene->triangles_in);
- /* Set some enclosure data */
- side_counts = MEM_CALLOC(alloc, desc->enclosures_count, sizeof(side_id_t));
- if(!side_counts) {
- res = RES_MEM_ERR;
- goto error;
- }
- FOR_EACH(e, 0, desc->enclosures_count) {
- struct enclosure_data* enc = enclosures + e;
- ASSERT(e < UINT_MAX);
- enc->header.enclosure_id = (unsigned)e; /* Back to API type */
- enc->header.is_infinite = (e == 0);
- }
- /* Process components to feed enclosures */
- FOR_EACH(c, 0, cc_count) {
- const struct cc_descriptor* cc = cc_descriptors + c;
- const enclosure_id_t e_id = cc->enclosure_id;
- struct enclosure_data* enc = enclosures + e_id;
- ASSERT(enc->header.enclosed_medium == MEDIUM_NULL__ /* Unset */
- || enc->header.enclosed_medium == cc->medium); /* Same medium */
- ASSERT(enc->header.enclosed_medium < UINT_MAX);
- enc->header.enclosed_medium = (unsigned)cc->medium; /* Back to API type */
- side_counts[e_id] += cc->side_count;
- }
- side_membership
- = MEM_ALLOC(alloc, desc->scene->nutris * sizeof(*side_membership));
- if(!side_membership) {
- res = RES_MEM_ERR;
- goto error;
- }
- res = darray_triangle_enc_resize(&desc->triangles_enc, desc->scene->nutris);
- if(res != RES_OK) goto error;
+ OK2(darray_triangle_enc_resize(&desc->triangles_enc, desc->scene->nutris),
+ error_);
triangles_enc = darray_triangle_enc_data_get(&desc->triangles_enc);
- htable_vrtx_id_init(alloc, &vtable);
- FOR_EACH(e, 0, desc->enclosures_count) {
+
+#pragma omp parallel for schedule(dynamic)
+ FOR_EACH(ee, 0, desc->enclosures_count) {
+ const enclosure_id_t e = (enclosure_id_t)ee;
struct enclosure_data* enc = enclosures + e;
+ struct cc_descriptor* current = cc_descriptors + enc->first_component;
+ struct htable_vrtx_id vtable;
+ const char* enc_memb;
+ uint64_t* enc_memb64;
+ trg_id_t fst_ixd = 0;
+ trg_id_t sgd_ixd;
trg_id_t t;
- memset(side_membership, 0, desc->scene->nutris * sizeof(*side_membership));
- /* Process all CC enclosures_count times to limit memory footprint. */
- FOR_EACH(c, 0, cc_count) {
- const struct cc_descriptor* cc = cc_descriptors + c;
- const char* cc_membership
- = darray_char_cdata_get(&cc->side_membership);
- if(cc->enclosure_id != e) continue;
- FOR_EACH(t, 0, desc->scene->nutris) side_membership[t] |= cc_membership[t];
+ trg_id_t first_member_id = desc->scene->nutris;
+ trg_id_t last_member_id = 0;
+ side_id_t side_count = 0;
+ ASSERT(ee <= ENCLOSURE_MAX__);
+ ASSERT(current != NULL);
+
+ if(res != RES_OK) continue;
+ enc->header.enclosure_id = (unsigned)e; /* Back to API type */
+ enc->header.is_infinite = (e == 0);
+ enc->header.enclosed_medium
+ = (unsigned)current->medium; /* Back to API type */
+ ASSERT(enc->header.enclosed_medium < desc->scene->nmeds);
+ /* Get side_membership information from component */
+ darray_char_copy_and_clear(&enc->side_membership,
+ ¤t->side_membership);
+ enc_memb = darray_char_cdata_get(&enc->side_membership);
+ enc_memb64 = (uint64_t*)enc_memb;
+ /* Check we can use uint64_t to merge bit vectors */
+ ASSERT(darray_char_capacity(&enc->side_membership)
+ % sizeof(*enc_memb64) == 0);
+ ASSERT(darray_char_size_get(&enc->side_membership)
+ == desc->scene->nutris);
+ /* Merge enclosures' membership information */
+ for(;;) {
+ uint64_t* cc_memb64;
+ trg_id_t t64, tmin64, tmax64;
+ size_t tmin, tmax;
+ ASSERT(enc->header.enclosed_medium == (unsigned)current->medium);
+ side_count += current->side_count;
+ first_member_id = MMIN(first_member_id, current->first_member_id);
+ last_member_id = MMAX(last_member_id, current->last_member_id);
+ if(current->next_component == COMPONENT_NULL__) break;
+ current = cc_descriptors + current->next_component;
+ ASSERT(darray_char_size_get(¤t->side_membership)
+ == desc->scene->nutris);
+ cc_memb64 = (uint64_t*)darray_char_cdata_get(¤t->side_membership);
+ ASSERT(darray_char_capacity(¤t->side_membership)
+ % sizeof(*enc_memb64) == 0);
+ tmin = current->first_member_id / sizeof(*enc_memb64);
+ tmax = (darray_char_size_get(&enc->side_membership) + sizeof(*enc_memb64) - 1)
+ / sizeof(*enc_memb64);
+ ASSERT(tmin <= tmax);
+ ASSERT(tmax < TRG_MAX__);
+ tmin64 = (trg_id_t)tmin;
+ tmax64 = (trg_id_t)tmax;
+ FOR_EACH(t64, tmin64, tmax64) enc_memb64[t64] |= cc_memb64[t64];
+ darray_char_purge(¤t->side_membership);
}
- /* Translate membership into a side and vertex lists. */
- OK(darray_triangle_in_reserve(&enc->sides, side_counts[e]));
- OK(darray_vrtx_id_reserve(&enc->vertices, side_counts[e] / 2));
+
+ /* Translate membership into side and vertex lists. */
+ OK(darray_triangle_in_resize(&enc->sides, side_count));
+ OK(darray_vrtx_id_reserve(&enc->vertices, side_count / 2));
/* New vertex numbering scheme local to the enclosure */
- htable_vrtx_id_clear(&vtable);
+ htable_vrtx_id_init(alloc, &vtable);
ASSERT(desc->scene->nutris
== darray_triangle_in_size_get(&desc->scene->triangles_in));
- /* Proceed in 2 steps; the second step puts at the end the back-faces
- * of triangles that also have front-face in the list. */
- FOR_EACH(t, 0, desc->scene->nutris) {
+ fst_ixd = 0;
+ sgd_ixd = side_count;
+ /* Put at the end the back-faces of triangles that also have their
+ * front-face in the list. */
+ FOR_EACH(t, first_member_id, desc->scene->nutris) {
const struct triangle_in* trg_in = triangles_in + t;
- struct triangle_in trg;
+ struct triangle_in* trg;
+ unsigned vertice_id[3];
int i;
- if(!side_membership[t]) continue;
+ if(!enc_memb[t]) continue;
++enc->header.unique_triangle_count;
+
FOR_EACH(i, 0, 3) {
vrtx_id_t* id = htable_vrtx_id_find(&vtable, trg_in->vertice_id + i);
if(id) {
- trg.vertice_id[i] = *id; /* Known vertex */
+ vertice_id[i] = *id; /* Known vertex */
} else {
/* Create new association */
- tmp = htable_vrtx_id_size_get(&vtable);
+ size_t tmp = htable_vrtx_id_size_get(&vtable);
ASSERT(tmp == darray_vrtx_id_size_get(&enc->vertices));
ASSERT(tmp < VRTX_MAX__);
- trg.vertice_id[i] = (vrtx_id_t)tmp;
+ vertice_id[i] = (vrtx_id_t)tmp;
OK(htable_vrtx_id_set(&vtable, trg_in->vertice_id + i,
- trg.vertice_id + i));
- OK(darray_vrtx_id_push_back(&enc->vertices, trg_in->vertice_id + i));
+ vertice_id + i));
+ OK(darray_vrtx_id_push_back(&enc->vertices, vertice_id + i));
++enc->header.vertices_count;
}
}
- FOR_EACH(i, 0, 2) trg.medium[i] = trg_in->medium[i];
- trg.global_id = trg_in->global_id;
- if(side_membership[t] & FLAG_FRONT) {
+ ASSERT((enc_memb[t] & FLAG_FRONT) || (enc_memb[t] & FLAG_BACK));
+ if(enc_memb[t] & FLAG_FRONT) {
++enc->header.triangle_count;
- OK(darray_triangle_in_push_back(&enc->sides, &trg));
+ trg = darray_triangle_in_data_get(&enc->sides) + fst_ixd++;
+
+ FOR_EACH(i, 0, 2) trg->medium[i] = trg_in->medium[i];
+ trg->global_id = trg_in->global_id;
+ FOR_EACH(i, 0, 3) trg->vertice_id[i] = vertice_id[i];
ASSERT(triangles_enc[t].enclosure[SIDE_FRONT] == ENCLOSURE_NULL__);
triangles_enc[t].enclosure[SIDE_FRONT] = e;
- } else if(side_membership[t] & FLAG_BACK) {
+ }
+ if(enc_memb[t] & FLAG_BACK) {
++enc->header.triangle_count;
- triangle_in_flip(&trg);
- OK(darray_triangle_in_push_back(&enc->sides, &trg));
+ trg = darray_triangle_in_data_get(&enc->sides) +
+ ((enc_memb[t] & FLAG_FRONT) ? --sgd_ixd : fst_ixd++);
+
+ FOR_EACH(i, 0, 2) trg->medium[i] = trg_in->medium[1 - i];
+ trg->global_id = trg_in->global_id;
+ FOR_EACH(i, 0, 3) trg->vertice_id[i] = vertice_id[2 - i];
ASSERT(triangles_enc[t].enclosure[SIDE_BACK] == ENCLOSURE_NULL__);
triangles_enc[t].enclosure[SIDE_BACK] = e;
}
+ if(fst_ixd == sgd_ixd) break;
}
- FOR_EACH(t, 0, desc->scene->nutris) {
- const struct triangle_in* trg_in = triangles_in + t;
- struct triangle_in trg;
- int i;
- if(!((side_membership[t] & FLAG_FRONT) && (side_membership[t] & FLAG_BACK)))
- continue;
- ++enc->header.triangle_count;
- FOR_EACH(i, 0, 3) {
- vrtx_id_t* id = htable_vrtx_id_find(&vtable, trg_in->vertice_id + i);
- ASSERT(id);
- trg.vertice_id[2-i] = *id; /* Known vertex */
- }
- FOR_EACH(i, 0, 2) trg.medium[1-i] = trg_in->medium[i];
- trg.global_id = trg_in->global_id;
- OK(darray_triangle_in_push_back(&enc->sides, &trg));
- ASSERT(triangles_enc[t].enclosure[SIDE_BACK] == ENCLOSURE_NULL__);
- triangles_enc[t].enclosure[SIDE_BACK] = e;
- }
- ASSERT(darray_triangle_in_size_get(&enc->sides) == side_counts[e]);
+ darray_char_purge(&enc->side_membership);
+ htable_vrtx_id_release(&vtable);
+ error:
+ /* Cannot exit openmp block */
+ continue;
}
-exit:
- htable_vrtx_id_release(&vtable);
- if(side_membership) MEM_RM(alloc, side_membership);
- if(side_counts) MEM_RM(alloc, side_counts);
+error_:
return res;
-error:
- goto exit;
}
/*******************************************************************************
@@ -1038,16 +1060,8 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
darray_triangle_tmp_init(scn->dev->allocator, &triangles_tmp);
triangles_tmp_initialized = 1;
- darray_neighbourhood_init(scn->dev->allocator, &neighbourhood_by_edge);
- neighbourhood_by_edge_initialized = 1;
-
- /* Step 1: list edges and connect triangles to edges */
- res = scan_edges(scn, &neighbourhood_by_edge, &triangles_tmp);
- if(res != RES_OK) {
- log_err(scn->dev, "%s: could not scan edges.\n", FUNC_NAME);
- goto error;
- }
+ OK(darray_triangle_tmp_resize(&triangles_tmp, scn->nutris));
trgsides
= MEM_CALLOC(scn->dev->allocator, 2 * scn->nutris, sizeof(struct trgside));
if(!trgsides) {
@@ -1055,23 +1069,22 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
goto error;
}
- /* Step 2: link triangles by neighbourhood */
- res = link_neighbours(scn, trgsides, &neighbourhood_by_edge,
- &triangles_tmp);
+ /* Step 1: build neighbourhoods */
+ res = collect_and_link_neighbours(scn, trgsides, &triangles_tmp);
+
if(res != RES_OK) {
- log_err(scn->dev, "%s: could not link neighbours.\n", FUNC_NAME);
+ log_err(scn->dev,
+ "%s: could not build neighbourhoods from scene.\n", FUNC_NAME);
goto error;
}
- darray_neighbourhood_release(&neighbourhood_by_edge);
- neighbourhood_by_edge_initialized = 0;
darray_cc_descriptor_init(scn->dev->allocator, &connex_components);
connex_components_initialized = 1;
darray_triangle_comp_init(scn->dev->allocator, &triangles_comp);
triangles_comp_initialized = 1;
OK(darray_triangle_comp_resize(&triangles_comp, scn->nutris));
- /* Step 3: extract triangle connex components */
+ /* Step 2: extract triangle connex components */
res = extract_connex_components(desc, trgsides, &connex_components,
&triangles_tmp, &triangles_comp);
if(res != RES_OK) {
@@ -1083,7 +1096,7 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
darray_triangle_tmp_release(&triangles_tmp);
triangles_tmp_initialized = 0;
- /* Step 4: group components */
+ /* Step 3: group components */
res = group_connex_components(desc, trgsides, &triangles_comp,
&connex_components);
if(res != RES_OK) {
@@ -1111,6 +1124,7 @@ exit:
if(triangles_comp_initialized) darray_triangle_comp_release(&triangles_comp);
if(trgsides) MEM_RM(scn->dev->allocator, trgsides);
if(desc) *out_desc = desc;
+
return res;
error:
if(desc) SENC(descriptor_ref_put(desc));
diff --git a/src/senc_scene_analyze_c.h b/src/senc_scene_analyze_c.h
@@ -153,8 +153,13 @@ struct cc_descriptor {
component_id_t cc_id;
component_id_t cc_group_root;
enclosure_id_t enclosure_id;
+ /* To create linked lists of componnents */
+ component_id_t next_component;
/* TODO: use only 1 bit per side (now 1 char per triangle) */
+ trg_id_t first_member_id;
+ trg_id_t last_member_id;
struct darray_char side_membership;
+
};
extern const struct cc_descriptor CC_DESCRIPTOR_NULL;
@@ -185,6 +190,9 @@ cc_descriptor_clear(struct cc_descriptor* data)
data->cc_id = CC_DESCRIPTOR_NULL.cc_id;
data->cc_group_root = CC_DESCRIPTOR_NULL.cc_group_root;
data->enclosure_id = CC_DESCRIPTOR_NULL.enclosure_id;
+ data->next_component = CC_DESCRIPTOR_NULL.next_component;
+ data->first_member_id = CC_DESCRIPTOR_NULL.first_member_id;
+ data->last_member_id = CC_DESCRIPTOR_NULL.last_member_id;
darray_char_clear(&data->side_membership);
}
@@ -200,6 +208,9 @@ cc_descriptor_purge(struct cc_descriptor* data)
data->cc_id = CC_DESCRIPTOR_NULL.cc_id;
data->cc_group_root = CC_DESCRIPTOR_NULL.cc_group_root;
data->enclosure_id = CC_DESCRIPTOR_NULL.enclosure_id;
+ data->next_component = CC_DESCRIPTOR_NULL.next_component;
+ data->first_member_id = CC_DESCRIPTOR_NULL.first_member_id;
+ data->last_member_id = CC_DESCRIPTOR_NULL.last_member_id;
darray_char_purge(&data->side_membership);
}
@@ -216,6 +227,9 @@ cc_descriptor_copy(struct cc_descriptor* dst, const struct cc_descriptor* src)
dst->cc_id = src->cc_id;
dst->cc_group_root = src->cc_group_root;
dst->enclosure_id = src->enclosure_id;
+ dst->next_component = src->next_component;
+ dst->first_member_id = src->first_member_id;
+ dst->last_member_id = src->last_member_id;
return darray_char_copy(&dst->side_membership, &src->side_membership);
}
@@ -234,6 +248,9 @@ cc_descriptor_copy_and_release
dst->cc_id = src->cc_id;
dst->cc_group_root = src->cc_group_root;
dst->enclosure_id = src->enclosure_id;
+ dst->next_component = src->next_component;
+ dst->first_member_id = src->first_member_id;
+ dst->last_member_id = src->last_member_id;
return darray_char_copy_and_release(&dst->side_membership,
&src->side_membership);
}
diff --git a/src/senc_scene_c.h b/src/senc_scene_c.h
@@ -143,21 +143,18 @@ trg_make_key(union vrtx_id3* k, const vrtx_id_t t[3])
k->vec[1] = t[0];
k->vec[2] = t[1];
return 0;
- }
- else {
+ } else {
k->vec[1] = t[1];
k->vec[2] = t[0];
return 1;
}
- }
- else {
+ } else {
k->vec[0] = t[1];
if(t[0] < t[2]) {
k->vec[1] = t[0];
k->vec[2] = t[2];
return 1;
- }
- else {
+ } else {
k->vec[1] = t[2];
k->vec[2] = t[0];
return 0;
diff --git a/src/test_senc_enclosure.c b/src/test_senc_enclosure.c
@@ -166,9 +166,9 @@ main(int argc, char** argv)
FOR_EACH(i, 0, 2)
CHK(senc_enclosure_get_triangle(enclosures[i], n, indices[i]) == RES_OK);
/* Same triangles, opposite sides */
- CHK(indices[0][0] == indices[1][0]);
- CHK(indices[0][1] == indices[1][2]);
- CHK(indices[0][2] == indices[1][1]);
+ CHK(indices[0][0] == indices[1][2]);
+ CHK(indices[0][1] == indices[1][1]);
+ CHK(indices[0][2] == indices[1][0]);
}
FOR_EACH(i, 0, 2)
CHK(senc_enclosure_ref_put(enclosures[i]) == RES_OK);
@@ -212,21 +212,14 @@ main(int argc, char** argv)
CHK(header->vertices_count == box_nvertices);
CHK(header->is_infinite == 1);
- FOR_EACH(t, 0, header->triangle_count) {
+ FOR_EACH(t, 0, header->unique_triangle_count) {
+ /* The first unique_triangle_count triangles of an enclosure
+ * are unique triangles */
CHK(senc_enclosure_get_triangle_global_id(enclosure, t, &gid) == RES_OK);
- CHK(gid == (t % header->unique_triangle_count));
+ CHK(gid == t);
}
FOR_EACH(n, 0, header->unique_triangle_count) {
- /* Read 2 consecutive triangles in the enclosure */
- FOR_EACH(i, 0, 2) /* Triangle n VS 2n */
- CHK(senc_enclosure_get_triangle(enclosure,
- n + i * header->unique_triangle_count, indices[i]) == RES_OK);
- /* Same triangles, opposite sides */
- CHK(indices[0][0] == indices[1][2]);
- CHK(indices[0][1] == indices[1][1]);
- CHK(indices[0][2] == indices[1][0]);
-
/* Put geometry in a 3D view */
CHK(s3d_shape_create_mesh(s3d, &s3d_shp) == RES_OK);
diff --git a/src/test_senc_many_triangles.c b/src/test_senc_many_triangles.c
@@ -75,26 +75,25 @@ main(int argc, char** argv)
struct s3dut_mesh* cyl = NULL;
struct s3dut_context ctx;
unsigned count;
- unsigned cyl_trg_count, cyl_vrtx_count;
- int i;
+ unsigned cyl_trg_count, cyl_vrtx_count, i;
char dump[64];
struct time t0, t1;
(void) argc, (void) argv;
- CHK(mem_init_proxy_allocator(&allocator, &mem_default_allocator) == RES_OK);
- CHK(senc_device_create
- (NULL, &allocator, SENC_NTHREADS_DEFAULT, 1, &dev) == RES_OK);
+ CHK(mem_init_regular_allocator(&allocator) == RES_OK);
+ CHK(senc_device_create (NULL, &allocator, SENC_NTHREADS_DEFAULT, 1, &dev)
+ == RES_OK);
+#define NB_CYL 10
/* Create the scene */
- CHK(senc_scene_create(dev, 2, &scn) == RES_OK);
+ CHK(senc_scene_create(dev, NB_CYL/2+1, &scn) == RES_OK);
ctx.ctx.positions = NULL;
ctx.ctx.indices = NULL;
ctx.ctx.scale = 1;
ctx.ctx.reverse_vrtx = 0;
ctx.ctx.reverse_med = 0;
- ctx.ctx.front_media = medium0;
- ctx.ctx.back_media = medium1;
+ ctx.ctx.back_media = medium0;
/* Create a cylinder (320 K trg, 160 K vrtx). */
CHK(s3dut_create_cylinder(&allocator, 1, 2, 400, 400, &cyl) == RES_OK);
S3DUT(mesh_get_data(cyl, &ctx.data));
@@ -102,8 +101,9 @@ main(int argc, char** argv)
ASSERT(ctx.data.nvertices < UINT_MAX);
cyl_trg_count = (unsigned)ctx.data.nprimitives;
cyl_vrtx_count = (unsigned)ctx.data.nvertices;
-#define NB_CYL 10
FOR_EACH(i, 0, NB_CYL) {
+ unsigned mmm = i/2;
+ ctx.ctx.front_media = &mmm;
d3(ctx.ctx.offset, 0, 0, i * 10);
CHK(senc_scene_add_geometry(scn, cyl_trg_count, get_s3dut_indices,
get_s3dut_media, NULL, cyl_vrtx_count, get_s3dut_position, &ctx)
@@ -122,12 +122,25 @@ main(int argc, char** argv)
CHK(senc_descriptor_get_global_triangles_count(desc, &count) == RES_OK);
CHK(count == NB_CYL * cyl_trg_count);
+ CHK(senc_descriptor_get_enclosure_count(desc, &count) == RES_OK);
+ CHK(count == 1 + NB_CYL);
+
+ FOR_EACH(i, 0, count) {
+ struct senc_enclosure* enclosure;
+ struct enclosure_header* header;
+ CHK(senc_descriptor_get_enclosure(desc, i, &enclosure) == RES_OK);
+ CHK(senc_enclosure_get_header(enclosure, &header) == RES_OK);
+ CHK(header->triangle_count ==
+ i ? cyl_trg_count : NB_CYL * cyl_trg_count);
+ CHK(senc_enclosure_ref_put(enclosure) == RES_OK);
+ }
+
CHK(senc_scene_ref_put(scn) == RES_OK);
CHK(senc_device_ref_put(dev) == RES_OK);
CHK(senc_descriptor_ref_put(desc) == RES_OK);
check_memory_allocator(&allocator);
- mem_shutdown_proxy_allocator(&allocator);
+ mem_shutdown_regular_allocator(&allocator);
CHK(mem_allocated_size() == 0);
return 0;
}
