commit 424534f9cb6b262982371037ad9be360ca5971bf
parent 2169ed6ff92ad461dcff2eb14dd0f88400c72f57
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Fri, 2 Mar 2018 20:57:05 +0100
Parallelize component extraction
Diffstat:
6 files changed, 358 insertions(+), 285 deletions(-)
diff --git a/src/senc_descriptor.c b/src/senc_descriptor.c
@@ -88,6 +88,7 @@ senc_descriptor_get_enclosure_count
if(!desc || !count) return RES_BAD_ARG;
tmp = darray_enclosure_size_get(&desc->enclosures);
ASSERT(tmp < UINT_MAX); /* API type */
+ ASSERT(desc->enclosures_count == tmp);
*count = (unsigned)tmp;
return RES_OK;
}
diff --git a/src/senc_internal_types.h b/src/senc_internal_types.h
@@ -23,7 +23,10 @@
/* Utility macros */
#define OK2(Expr, Label)\
res = (Expr);\
- if(res != RES_OK) goto Label;
+ if(res != RES_OK) {\
+ fprintf(stderr, "%s: error code set to %d at line %d\n", __FUNCTION__, res, __LINE__);\
+ goto Label;\
+ }
#define OK(Expr) OK2((Expr), error)
@@ -68,4 +71,40 @@ typedef enclosure_id_t component_id_t;
#define COMPONENT_MAX__ ENCLOSURE_MAX__
#define COMPONENT_NULL__ ENCLOSURE_NULL__
+/* This one is used as an index to arrays */
+enum side_id {
+ SIDE_FRONT = 0,
+ SIDE_BACK = 1
+};
+
+/* Utility macros */
+static FINLINE trg_id_t
+TRGSIDE_2_TRG(side_id_t s) {
+ ASSERT(((size_t)s >> 1) <= TRG_MAX__);
+ return s >> 1;
+}
+
+static FINLINE int
+TRGSIDE_IS_FRONT(side_id_t s) {
+ return (s & 1) == 0;
+}
+
+static FINLINE enum side_id
+TRGSIDE_2_SIDE(side_id_t s) {
+ return (s & 1) ? SIDE_BACK : SIDE_FRONT;
+}
+
+static FINLINE side_id_t
+TRGIDxSIDE_2_TRGSIDE(trg_id_t t, enum side_id i) {
+ ASSERT((((size_t)t << 1) | (i == SIDE_BACK)) < SIDE_MAX__);
+ ASSERT(i == SIDE_FRONT || i == SIDE_BACK);
+ return (side_id_t)((t << 1) | (i == SIDE_BACK));
+}
+
+static FINLINE side_id_t
+TRGSIDE_OPPOSITE(side_id_t s) {
+ return TRGIDxSIDE_2_TRGSIDE(TRGSIDE_2_TRG(s),
+ TRGSIDE_IS_FRONT(s) ? SIDE_BACK : SIDE_FRONT);
+}
+
#endif /* SENC_INTERNAL_TYPES_H */
diff --git a/src/senc_scene.c b/src/senc_scene.c
@@ -37,6 +37,7 @@ scene_release(ref_T * ref)
darray_position_release(&scn->vertices);
htable_vrtx_release(&scn->unique_vertices);
htable_trg_release(&scn->unique_triangles);
+ darray_side_range_release(&scn->media_use);
MEM_RM(dev->allocator, scn);
SENC(device_ref_put(dev));
}
@@ -75,6 +76,8 @@ senc_scene_create
darray_position_init(dev->allocator, &scn->vertices);
htable_vrtx_init(dev->allocator, &scn->unique_vertices);
htable_trg_init(dev->allocator, &scn->unique_triangles);
+ darray_side_range_init(dev->allocator, &scn->media_use);
+ darray_side_range_resize(&scn->media_use, nmeds);
exit:
if(scn) *out_scn = scn;
@@ -245,16 +248,26 @@ senc_scene_add_geometry
(unsigned long)trg[*p_trg].global_id);
if(!same) {
FOR_EACH(j, 0, 2) {
- tmp.medium[j] = (medium_id_t) med[1-j];
+ tmp.medium[j] = (medium_id_t)med[1-j];
}
}
}
} else {
/* New triangle */
trg_id_t u = scn->nutris + actual_nutris;
+ struct side_range* media_use;
ASSERT(u == htable_trg_size_get(&scn->unique_triangles));
OK(htable_trg_set(&scn->unique_triangles, &trg_key, &u));
OK(darray_triangle_in_push_back(&scn->triangles_in, &tmp));
+ FOR_EACH(j, 0, 2) {
+ ASSERT(tmp.medium[j] < scn->nmeds);
+ media_use = darray_side_range_data_get(&scn->media_use) + tmp.medium[j];
+ media_use->first = MMIN(media_use->first, TRGIDxSIDE_2_TRGSIDE(u, j));
+ ASSERT(media_use->first < 2 * (scn->nutris + actual_nutris + 1));
+ media_use->last = MMAX(media_use->last, TRGIDxSIDE_2_TRGSIDE(u, j));
+ ASSERT(media_use->last < 2 * (scn->nutris + actual_nutris + 1));
+ ASSERT(media_use->first <= media_use->last);
+ }
++actual_nutris;
}
++actual_ntris;
diff --git a/src/senc_scene_analyze.c b/src/senc_scene_analyze.c
@@ -35,8 +35,8 @@
#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, TRG_NULL__,\
- TRG_NULL__, { NULL, 0, 0, NULL }\
+ CC_ID_NONE, CC_GROUP_ROOT_NONE, CC_GROUP_ID_NONE, CC_ID_NONE,\
+ { TRG_NULL__, 0}, { NULL, 0, 0, NULL }\
}
const struct cc_descriptor CC_DESCRIPTOR_NULL = CC_DESCRIPTOR_NULL__;
@@ -184,15 +184,22 @@ static side_id_t
get_side_not_in_connex_component
(struct senc_scene* scn,
struct trgside* trgsides,
- side_id_t* first_side_not_in_component)
+ side_id_t* first_side_not_in_component,
+ medium_id_t medium)
{
side_id_t i;
+ const trg_id_t last_side
+ = darray_side_range_cdata_get(&scn->media_use)[medium].last;
ASSERT(scn && trgsides && first_side_not_in_component);
i = *first_side_not_in_component;
- while(i < 2 * scn->nutris && trgsides[i].list_id != FLAG_LIST_SIDE_LIST) ++i;
+ while(i < last_side
+ && (trgsides[i].medium != medium
+ || trgsides[i].list_id != FLAG_LIST_SIDE_LIST)) {
+ ++i;
+ }
*first_side_not_in_component = i+1;
- if(i == 2 * scn->nutris) return SIDE_NULL__;
+ if(i == last_side) return SIDE_NULL__;
return i;
}
@@ -216,148 +223,215 @@ static res_T
extract_connex_components
(struct senc_descriptor* desc,
struct trgside* trgsides,
- struct darray_cc_descriptor* connex_components,
+ struct darray_ptr_component_descriptor* connex_components,
struct darray_triangle_tmp* triangles_tmp_array,
struct darray_triangle_comp* triangles_comp)
{
res_T res = RES_OK;
- medium_id_t m;
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;
+ ATOMIC component_count = 0;
+ int stack_initialised = 0;
+ int mm;
+#ifndef NDEBUG
+ trg_id_t t;
+#endif
ASSERT(trgsides && desc && connex_components && triangles_tmp_array);
-
+ ASSERT(darray_ptr_component_descriptor_size_get(connex_components) == 0);
alloc = descriptor_get_allocator(desc);
scn = desc->scene;
- /* Init stack */
- darray_side_id_init(alloc, &stack);
+ /* Just a hint; to avoid contention on first loop */
+ OK2(darray_ptr_component_descriptor_reserve(connex_components, 2 * scn->nmeds),
+ error_); /* Cannot jump into openmp block */
+
+#ifndef NDEBUG
+ FOR_EACH(t, 0, scn->nutris) {
+ struct triangle_in* trg_in =
+ darray_triangle_in_data_get(&scn->triangles_in) + t;
+ const struct side_range* media_use
+ = darray_side_range_cdata_get(&scn->media_use);
+ FOR_EACH(mm, 0, 2) {
+ const side_id_t side = TRGIDxSIDE_2_TRGSIDE(t, mm);
+ const medium_id_t medium = trg_in->medium[mm];
+ ASSERT(media_use[medium].first <= side && side <= media_use[medium].last);
+ }
+ }
+#endif
- for(;;) {
+ #pragma omp parallel for firstprivate(stack_initialised) schedule(dynamic)
+ for(mm = 0; mm < scn->nmeds; mm++) { /* Process all media */
+ const medium_id_t m = (medium_id_t)mm;
+ struct cc_descriptor* current_cc;
+ struct darray_side_id stack;
/* 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;
- unsigned 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);
-
- /* 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 uchar per triangle (2 sides); allow uint64_t* access */
- OK(darray_uchar_reserve(¤t_cc->side_membership,
- ((scn->nutris + 7) / 8) * 8));
- OK(darray_uchar_resize(¤t_cc->side_membership, scn->nutris));
- side_membership = darray_uchar_data_get(¤t_cc->side_membership);
- memset(side_membership, 0, scn->nutris * sizeof(unsigned char));
- 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);
+ side_id_t first_side_not_in_component
+ = darray_side_range_cdata_get(&scn->media_use)[m].first;
+ if (first_side_not_in_component == SIDE_NULL__)
+ continue; /* Unused medium */
+ ASSERT(first_side_not_in_component < 2 * scn->nutris);
+ if(res != RES_OK) continue;
+ if(!stack_initialised) {
+ stack_initialised = 1;
+ darray_side_id_init(alloc, &stack);
+ }
+ ASSERT(darray_side_id_size_get(&stack) == 0);
+ for(;;) { /* Process all enclosures for this medium */
+ const side_id_t start_side_id = get_side_not_in_connex_component(scn,
+ trgsides, &first_side_not_in_component, m);
+ side_id_t crt_side_id = start_side_id;
+ side_id_t last_side_id = start_side_id;
+ unsigned char* side_membership;
+
+ ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nutris);
+ if(start_side_id == SIDE_NULL__) { /* start_side_id=SIDE_NULL__ => done! */
+ if(stack_initialised) {
+ stack_initialised = 0;
+ darray_side_id_release(&stack);
+ }
+ break;
+ }
+ ASSERT(trgsides[start_side_id].list_id == FLAG_LIST_SIDE_LIST);
- for(;;) {
- int i;
- /* Pop waiting stack to feed crt_side */
- struct trgside* crt_side = trgsides + crt_side_id;
- const trg_id_t crt_trg_id = TRGSIDE_2_TRG(crt_side_id);
- struct triangle_comp* trg_comp =
- darray_triangle_comp_data_get(triangles_comp) + crt_trg_id;
- ASSERT(crt_trg_id < scn->nutris);
- ASSERT(trgsides[crt_side_id].medium == m);
-
- /* Record crt_side both as component and triangle level */
- 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;
- 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;
- ASSERT(!(side_membership[crt_trg_id] & FLAG_BACK));
- side_membership[crt_trg_id] |= FLAG_BACK;
+ /* Create and init a new component */
+ current_cc = MEM_ALLOC(alloc, sizeof(struct cc_descriptor));
+ if(!current_cc) {
+ res = RES_MEM_ERR;
+ goto error;
}
+ cc_descriptor_init(alloc, current_cc);
+ /* 1 uchar per triangle (2 sides); allow uint64_t* access */
+ OK(darray_uchar_reserve(¤t_cc->side_membership,
+ ((scn->nutris + 7) / 8) * 8));
+ OK(darray_uchar_resize(¤t_cc->side_membership, scn->nutris));
+ side_membership = darray_uchar_data_get(¤t_cc->side_membership);
+ memset(side_membership, 0, scn->nutris * sizeof(unsigned char));
+ ASSERT(m == trgsides[start_side_id].medium);
+ current_cc->cc_id = (component_id_t)(ATOMIC_INCR(&component_count) - 1);
+ current_cc->medium = m;
+ current_cc->in_use_membership_range.first = start_side_id;
+
+ for(;;) { /* Process all sides of this enclosure */
+ int i;
+ /* Pop waiting stack to feed crt_side */
+ struct trgside* crt_side = trgsides + crt_side_id;
+ const trg_id_t crt_trg_id = TRGSIDE_2_TRG(crt_side_id);
+ struct triangle_comp* trg_comp =
+ darray_triangle_comp_data_get(triangles_comp) + crt_trg_id;
+ ASSERT(crt_trg_id < scn->nutris);
+ ASSERT(trgsides[crt_side_id].medium == m);
+
+ /* Record crt_side both as component and triangle level */
+ 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] == COMPONENT_NULL__);
+ 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] == COMPONENT_NULL__);
+ 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) {
- side_id_t neighbour_id = crt_side->facing_side_id[i];
- trg_id_t nbour_trg_id = TRGSIDE_2_TRG(neighbour_id);
- struct trgside* neighbour = trgsides + neighbour_id;
- if(neighbour->medium != crt_side->medium) {
- /* Found medium discontinuity! Model topology is broken. */
- const struct triangle_in* triangles_in
- = darray_triangle_in_cdata_get(&scn->triangles_in);
- const union double3* positions
- = darray_position_cdata_get(&scn->vertices);
- log_err(scn->dev,
- "Medium mismatch found between neighbour triangles %lu %s"
- " side and %u %s side.\n",
- (unsigned long)triangles_in[crt_trg_id].global_id,
- TRGSIDE_IS_FRONT(crt_side_id) ? "front" : "back",
- triangles_in[nbour_trg_id].global_id,
- TRGSIDE_IS_FRONT(neighbour_id) ? "front" : "back");
- log_err(scn->dev,
- "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
- (unsigned long)triangles_in[crt_trg_id].global_id,
- SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[0]].vec),
- SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[1]].vec),
- SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[2]].vec));
- log_err(scn->dev,
- "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
- (unsigned long)triangles_in[nbour_trg_id].global_id,
- SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[0]].vec),
- SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[1]].vec),
- SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[2]].vec));
- log_err(desc->scene->dev, "Media: %lu VS %lu\n",
- (unsigned long)neighbour->medium, (unsigned long)crt_side->medium);
- res = RES_BAD_ARG;
- goto error;
- }
- if(neighbour->list_id == FLAG_LIST_COMPONENT) {
- /* Already processed */
+ /* Store neighbour sides in a waiting stack */
+ FOR_EACH(i, 0, 3) {
+ side_id_t neighbour_id = crt_side->facing_side_id[i];
+ trg_id_t nbour_trg_id = TRGSIDE_2_TRG(neighbour_id);
+ struct trgside* neighbour = trgsides + neighbour_id;
+ if(neighbour->medium != crt_side->medium) {
+ /* Found medium discontinuity! Model topology is broken. */
+ const struct triangle_in* triangles_in
+ = darray_triangle_in_cdata_get(&scn->triangles_in);
+ const union double3* positions
+ = darray_position_cdata_get(&scn->vertices);
+ log_err(scn->dev,
+ "Medium mismatch found between neighbour triangles %lu %s"
+ " side and %u %s side.\n",
+ (unsigned long)triangles_in[crt_trg_id].global_id,
+ TRGSIDE_IS_FRONT(crt_side_id) ? "front" : "back",
+ triangles_in[nbour_trg_id].global_id,
+ TRGSIDE_IS_FRONT(neighbour_id) ? "front" : "back");
+ log_err(scn->dev,
+ "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
+ (unsigned long)triangles_in[crt_trg_id].global_id,
+ SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[0]].vec),
+ SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[1]].vec),
+ SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[2]].vec));
+ log_err(scn->dev,
+ "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
+ (unsigned long)triangles_in[nbour_trg_id].global_id,
+ SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[0]].vec),
+ SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[1]].vec),
+ SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[2]].vec));
+ log_err(desc->scene->dev, "Media: %lu VS %lu\n",
+ (unsigned long)neighbour->medium, (unsigned long)crt_side->medium);
+ res = RES_BAD_ARG;
+ 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;
- }
- if(neighbour->list_id == FLAG_WAITING_STACK) {
- continue; /* Already processed */
+ continue;
+ }
+ if(neighbour->list_id == FLAG_WAITING_STACK) {
+ continue; /* Already processed */
+ }
+ add_side_to_stack(scn, &stack, trgsides, neighbour_id);
}
- add_side_to_stack(scn, &stack, trgsides, neighbour_id);
+ 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, current_cc);
+ current_cc->in_use_membership_range.last = last_side_id;
+ /* Need to synchronize connex_components growth as this global structure
+ * is accessed bay multipe threads */
+ #pragma omp critical
+ {
+ res_T tmp_res;
+ struct cc_descriptor** components;
+ size_t sz = darray_ptr_component_descriptor_size_get(connex_components);
+ tmp_res = darray_ptr_component_descriptor_resize(connex_components,
+ MMAX(sz, 1 + current_cc->cc_id));
+ if (tmp_res != RES_OK) res = tmp_res;
+ components =
+ darray_ptr_component_descriptor_data_get(connex_components);
+ ASSERT(components[current_cc->cc_id] == NULL);
+ components[current_cc->cc_id] = current_cc;
}
- 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, current_cc);
- current_cc->last_member_id = TRGSIDE_2_TRG(last_side_id);
+ error:
+ continue; /* Cannot exit openmp block */
}
+ OK2(res, error_);
+
+ ASSERT(component_count ==
+ (int)darray_ptr_component_descriptor_size_get(connex_components));
+#ifndef NDEBUG
+ FOR_EACH(t, 0, scn->nutris) {
+ struct triangle_comp* trg_comp =
+ darray_triangle_comp_data_get(triangles_comp) + t;
+ ASSERT(trg_comp->component[SIDE_FRONT] != COMPONENT_NULL__);
+ ASSERT(trg_comp->component[SIDE_BACK] != COMPONENT_NULL__);
+ }
+#endif
exit:
- darray_side_id_release(&stack);
ASSERT(desc->triangle_count
== darray_triangle_comp_size_get(triangles_comp));
/* triangles_enc is still unused: no size to assert */
return res;
-error:
+error_:
goto exit;
}
@@ -413,11 +487,11 @@ group_connex_components
(struct senc_descriptor* desc,
struct trgside* trgsides,
struct darray_triangle_comp* triangles_comp,
- struct darray_cc_descriptor* connex_components)
+ struct darray_ptr_component_descriptor* connex_components)
{
res_T res = RES_OK;
struct mem_allocator* alloc;
- struct cc_descriptor* descriptors;
+ struct cc_descriptor** descriptors;
struct s3d_device* s3d = NULL;
struct s3d_scene* s3d_scn = NULL;
struct s3d_shape* s3d_shp = NULL;
@@ -432,8 +506,8 @@ group_connex_components
ASSERT(desc && trgsides && triangles_comp && connex_components);
alloc = descriptor_get_allocator(desc);
- descriptors = darray_cc_descriptor_data_get(connex_components);
- tmp = darray_cc_descriptor_size_get(connex_components);
+ descriptors = darray_ptr_component_descriptor_data_get(connex_components);
+ tmp = darray_ptr_component_descriptor_size_get(connex_components);
ASSERT(tmp <= COMPONENT_MAX__);
cc_count = (component_id_t)tmp;
@@ -463,18 +537,19 @@ group_connex_components
float origin[3];
const float dir[3] = { 0, 0, 1 };
const float range[2] = { 0, FLT_MAX };
- struct cc_descriptor* const cc = descriptors + c;
+ struct cc_descriptor* const cc = descriptors[c];
const struct triangle_comp* origin_trg =
darray_triangle_comp_cdata_get(triangles_comp) + cc->max_z_vrtx_id;
component_id_t self_hit_component
= origin_trg->component[1 - TRGSIDE_2_SIDE(cc->max_z_side_id)];
+ ASSERT(cc->cc_id == c);
ASSERT(cc->cc_group_root == CC_GROUP_ID_NONE);
if(cc->max_z_nz < 0) {
/* Don't need to cast a ray */
- cc->cc_group_root = c; /* New group with self as root */
- ASSERT(desc->enclosures_count < USHRT_MAX);
+ cc->cc_group_root = cc->cc_id; /* New group with self as root */
+ ASSERT(desc->enclosures_count < ENCLOSURE_MAX__);
cc->enclosure_id = desc->enclosures_count++;
continue;
}
@@ -555,9 +630,9 @@ group_connex_components
{
const struct cc_descriptor* hit_desc;
ASSERT(cc->cc_group_root
- < darray_cc_descriptor_size_get(connex_components));
- hit_desc = darray_cc_descriptor_cdata_get(connex_components)
- + cc->cc_group_root;
+ < darray_ptr_component_descriptor_size_get(connex_components));
+ hit_desc = *(darray_ptr_component_descriptor_cdata_get(connex_components)
+ + cc->cc_group_root);
ASSERT(hit_desc->medium == hit_trg_in->medium[hit_side]);
ASSERT(darray_uchar_cdata_get(&hit_desc->side_membership)[hit_trg_id]
& TRGSIDE_IS_FRONT(hit_side) ? FLAG_FRONT : FLAG_BACK);
@@ -602,18 +677,19 @@ 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;
+ 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)
- + other_desc->cc_group_root;
+ other_desc = *(darray_ptr_component_descriptor_cdata_get(connex_components)
+ + other_desc->cc_group_root);
}
ASSERT(other_desc->cc_group_root != CC_GROUP_ROOT_NONE);
ASSERT(other_desc->enclosure_id != CC_GROUP_ID_NONE);
+ ASSERT(cc->medium == other_desc->medium);
cc->cc_group_root = other_desc->cc_group_root;
cc->enclosure_id = other_desc->enclosure_id;
++enclosures[cc->enclosure_id].cc_count;
@@ -646,7 +722,7 @@ collect_and_link_neighbours
const union double3* vertices;
ASSERT(scn && trgsides && triangles_tmp_array);
- ASSERT((size_t) scn->nuverts + (size_t) scn->nutris + 2 <= EDGE_MAX__);
+ ASSERT((size_t)scn->nuverts + (size_t)scn->nutris + 2 <= EDGE_MAX__);
triangles_in = darray_triangle_in_cdata_get(&scn->triangles_in);
triangles_tmp = darray_triangle_tmp_data_get(triangles_tmp_array);
@@ -654,13 +730,15 @@ collect_and_link_neighbours
ASSERT(scn->nutris == darray_triangle_tmp_size_get(triangles_tmp_array));
-#pragma omp parallel
+ #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 */
+ /* Array to keep neighbourhood of edges
+ * Resize/Push operations on neighbourhood_by_edge are valid in the
+ * openmp block because it is thread local data */
struct darray_neighbourhood neighbourhood_by_edge;
edge_id_t e, edge_count;
edge_id_t nbedges_guess;
@@ -672,8 +750,8 @@ collect_and_link_neighbours
/* 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)));
+ ? (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));
@@ -712,7 +790,7 @@ collect_and_link_neighbours
struct neighbour_info* info;
size_t sz = htable_edge_id_size_get(&edge_ids);
ASSERT(sz <= EDGE_MAX__);
- id = (edge_id_t) sz;
+ 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));
@@ -850,11 +928,11 @@ error:
static res_T
build_result
(struct senc_descriptor* desc,
- struct darray_cc_descriptor* connex_components)
+ struct darray_ptr_component_descriptor* connex_components)
{
res_T res = RES_OK;
struct mem_allocator* alloc;
- struct cc_descriptor* cc_descriptors;
+ struct cc_descriptor** cc_descriptors;
struct enclosure_data* enclosures;
const struct triangle_in* triangles_in;
struct triangle_enc* triangles_enc;
@@ -863,38 +941,44 @@ build_result
ASSERT(desc && connex_components);
alloc = descriptor_get_allocator(desc);
- ASSERT(darray_cc_descriptor_size_get(connex_components) < COMPONENT_MAX__);
- cc_descriptors = darray_cc_descriptor_data_get(connex_components);
+ ASSERT(darray_ptr_component_descriptor_size_get(connex_components) < COMPONENT_MAX__);
+ cc_descriptors = darray_ptr_component_descriptor_data_get(connex_components);
enclosures = darray_enclosure_data_get(&desc->enclosures);
triangles_in = darray_triangle_in_cdata_get(&desc->scene->triangles_in);
OK2(darray_triangle_enc_resize(&desc->triangles_enc, desc->scene->nutris),
error_);
triangles_enc = darray_triangle_enc_data_get(&desc->triangles_enc);
-#pragma omp parallel for schedule(dynamic)
+ /* Resize/push operations on enclosure's fields are valid in the
+ * openmp block as a given enclosure is processed by a single thread */
+ #pragma omp parallel for schedule(dynamic)
for(ee = 0; ee < (int)desc->enclosures_count; ee++) {
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 cc_descriptor* current = cc_descriptors[enc->first_component];
struct htable_vrtx_id vtable;
const unsigned char* enc_memb;
uint64_t* enc_memb64;
trg_id_t fst_ixd = 0;
trg_id_t sgd_ixd;
trg_id_t t;
- trg_id_t first_member_id = desc->scene->nutris;
- trg_id_t last_member_id = 0;
+ side_id_t first_member_side = SIDE_MAX__;
+ side_id_t last_member_side = 0;
side_id_t side_count = 0;
+ ASSERT(enc->first_component
+ < darray_ptr_component_descriptor_size_get(connex_components));
ASSERT(ee <= ENCLOSURE_MAX__);
- ASSERT(current != NULL);
+ ASSERT(current->cc_id == enc->first_component);
if(res != RES_OK) continue;
+ ASSERT(e <= UINT_MAX);
enc->header.enclosure_id = (unsigned)e; /* Back to API type */
+ ASSERT(current->enclosure_id == enc->header.enclosure_id);
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 */
+ /* Get side_membership information from first component */
darray_uchar_copy_and_clear(&enc->side_membership,
¤t->side_membership);
enc_memb = darray_uchar_cdata_get(&enc->side_membership);
@@ -911,23 +995,36 @@ build_result
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);
+ first_member_side = MMIN(first_member_side,
+ current->in_use_membership_range.first);
+ last_member_side = MMAX(last_member_side,
+ current->in_use_membership_range.last);
if(current->next_component == COMPONENT_NULL__) break;
- current = cc_descriptors + current->next_component;
+ ASSERT(current->next_component
+ < darray_ptr_component_descriptor_size_get(connex_components));
+ ASSERT(cc_descriptors[current->next_component]->cc_id == current->next_component);
+ current = cc_descriptors[current->next_component];
+ ASSERT(current->enclosure_id == enc->header.enclosure_id);
ASSERT(darray_uchar_size_get(¤t->side_membership)
== desc->scene->nutris);
cc_memb64 = (uint64_t*)darray_uchar_cdata_get(¤t->side_membership);
ASSERT(darray_uchar_capacity(¤t->side_membership)
% sizeof(*enc_memb64) == 0);
- tmin = current->first_member_id / sizeof(*enc_memb64);
- tmax = (darray_uchar_size_get(&enc->side_membership) + sizeof(*enc_memb64) - 1)
- / sizeof(*enc_memb64);
+ /* Merge only the range where current is defined */
+ tmin = TRGSIDE_2_TRG(current->in_use_membership_range.first
+ / sizeof(*enc_memb64));
+ tmax = TRGSIDE_2_TRG((current->in_use_membership_range.last
+ + 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];
+ /* We accept the for loop processes meaningless data,
+ * but it must be allocated! */
+ ASSERT(tmax * sizeof(*enc_memb64)
+ < darray_uchar_capacity(&enc->side_membership));
+ for(t64 = tmin64; t64 <= tmax64; t64++)
+ enc_memb64[t64] |= cc_memb64[t64];
darray_uchar_purge(¤t->side_membership);
}
@@ -942,7 +1039,10 @@ build_result
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) {
+ for(t = TRGSIDE_2_TRG(first_member_side);
+ t <= TRGSIDE_2_TRG(last_member_side);
+ t++)
+ {
const struct triangle_in* trg_in = triangles_in + t;
struct triangle_in* trg;
unsigned vertice_id[3];
@@ -996,9 +1096,12 @@ build_result
/* Cannot exit openmp block */
continue;
}
-
-error_:
+ OK2(res, error_);
+
+exit:
return res;
+error_:
+ goto exit;
}
/*******************************************************************************
@@ -1014,7 +1117,7 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
char triangles_tmp_initialized = 0;
/* Array of connex components.
* They are refered to by arrays of ids. */
- struct darray_cc_descriptor connex_components;
+ struct darray_ptr_component_descriptor connex_components;
char connex_components_initialized = 0;
/* Triangle neighbourhood by edge. */
struct darray_neighbourhood neighbourhood_by_edge;
@@ -1055,7 +1158,7 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
goto error;
}
- darray_cc_descriptor_init(scn->dev->allocator, &connex_components);
+ darray_ptr_component_descriptor_init(scn->dev->allocator, &connex_components);
connex_components_initialized = 1;
darray_triangle_comp_init(scn->dev->allocator, &triangles_comp);
triangles_comp_initialized = 1;
@@ -1093,8 +1196,16 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
}
exit:
- if(connex_components_initialized)
- darray_cc_descriptor_release(&connex_components);
+ if(connex_components_initialized) {
+ size_t c, cc_count =
+ darray_ptr_component_descriptor_size_get(&connex_components);
+ struct cc_descriptor** components =
+ darray_ptr_component_descriptor_data_get(&connex_components);
+ FOR_EACH(c, 0, cc_count) {
+ ptr_component_descriptor_release(scn->dev->allocator, components + c);
+ }
+ darray_ptr_component_descriptor_release(&connex_components);
+ }
if(neighbourhood_by_edge_initialized)
darray_neighbourhood_release(&neighbourhood_by_edge);
if(triangles_tmp_initialized) darray_triangle_tmp_release(&triangles_tmp);
diff --git a/src/senc_scene_analyze_c.h b/src/senc_scene_analyze_c.h
@@ -25,12 +25,6 @@
#include <rsys/double3.h>
-/* This one is used as an index to arrays */
-enum side_id {
- SIDE_FRONT = 0,
- SIDE_BACK = 1
-};
-
/* This one is used as flag */
enum side_flag {
FLAG_FRONT = BIT(0),
@@ -106,39 +100,10 @@ struct trgside {
#endif
};
-static FINLINE trg_id_t
-TRGSIDE_2_TRG(side_id_t s) {
- ASSERT(((size_t)s >> 1) <= TRG_MAX__);
- return s >> 1; }
-
-static FINLINE int
-TRGSIDE_IS_FRONT(side_id_t s) {
- return (s & 1) == 0;
-}
-
-static FINLINE enum side_id
-TRGSIDE_2_SIDE(side_id_t s) {
- return (s & 1) ? SIDE_BACK : SIDE_FRONT;
-}
-
-static FINLINE side_id_t
-TRGIDxSIDE_2_TRGSIDE(trg_id_t t, enum side_id i) {
- ASSERT((((size_t)t << 1) | (i == SIDE_BACK)) < SIDE_MAX__);
- ASSERT(i == SIDE_FRONT || i == SIDE_BACK);
- return (side_id_t)((t << 1) | (i == SIDE_BACK));
-}
-
-static FINLINE side_id_t
-TRGSIDE_OPPOSITE(side_id_t s) {
- return TRGIDxSIDE_2_TRGSIDE(TRGSIDE_2_TRG(s),
- TRGSIDE_IS_FRONT(s) ? SIDE_BACK : SIDE_FRONT);
-}
-
/* Descriptors for connex component.
* Define lists of trg sides starting from a given head.
* Also keeps the maximum z info of the component
- * along with the associated triangle id,
- * a star3D id */
+ * along with the associated triangle and vertex ids */
#define CC_ID_NONE USHRT_MAX
#define CC_GROUP_ROOT_NONE USHRT_MAX
#define CC_GROUP_ROOT_INFINITE (USHRT_MAX-1)
@@ -150,14 +115,14 @@ struct cc_descriptor {
vrtx_id_t max_z_vrtx_id;
side_id_t side_count;
medium_id_t medium;
+ /* Used when grouping components to form enclosures */
component_id_t cc_id;
component_id_t cc_group_root;
enclosure_id_t enclosure_id;
- /* To create linked lists of componnents */
+ /* To create by-medium linked lists of componnents */
component_id_t next_component;
/* TODO: use only 1 bit per side (now 1 uchar per triangle) */
- trg_id_t first_member_id;
- trg_id_t last_member_id;
+ struct side_range in_use_membership_range;
struct darray_uchar side_membership;
};
@@ -172,95 +137,22 @@ cc_descriptor_init(struct mem_allocator* alloc, struct cc_descriptor* data)
}
static FINLINE void
-cc_descriptor_release(struct cc_descriptor* data)
-{
+ptr_component_descriptor_init(struct mem_allocator* alloc, struct cc_descriptor** data) {
+ (void) alloc;
ASSERT(data);
- darray_uchar_release(&data->side_membership);
-}
-
-static FINLINE void
-cc_descriptor_clear(struct cc_descriptor* data)
-{
- d3_set(data->max_vrtx, CC_DESCRIPTOR_NULL.max_vrtx);
- data->max_z_nz = CC_DESCRIPTOR_NULL.max_z_nz;
- data->max_z_side_id = CC_DESCRIPTOR_NULL.max_z_side_id;
- data->max_z_vrtx_id = CC_DESCRIPTOR_NULL.max_z_vrtx_id;
- data->side_count = CC_DESCRIPTOR_NULL.side_count;
- data->medium = CC_DESCRIPTOR_NULL.medium;
- 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_uchar_clear(&data->side_membership);
+ *data = NULL;
}
-
static FINLINE void
-cc_descriptor_purge(struct cc_descriptor* data)
-{
- d3_set(data->max_vrtx, CC_DESCRIPTOR_NULL.max_vrtx);
- data->max_z_nz = CC_DESCRIPTOR_NULL.max_z_nz;
- data->max_z_side_id = CC_DESCRIPTOR_NULL.max_z_side_id;
- data->max_z_vrtx_id = CC_DESCRIPTOR_NULL.max_z_vrtx_id;
- data->side_count = CC_DESCRIPTOR_NULL.side_count;
- data->medium = CC_DESCRIPTOR_NULL.medium;
- 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_uchar_purge(&data->side_membership);
-}
-
-static FINLINE res_T
-cc_descriptor_copy(struct cc_descriptor* dst, const struct cc_descriptor* src)
-{
- ASSERT(dst && src);
- d3_set(dst->max_vrtx, src->max_vrtx);
- dst->max_z_nz = src->max_z_nz;
- dst->max_z_side_id = src->max_z_side_id;
- dst->max_z_vrtx_id = src->max_z_vrtx_id;
- dst->side_count = src->side_count;
- dst->medium = src->medium;
- 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_uchar_copy(&dst->side_membership, &src->side_membership);
-}
-
-static FINLINE res_T
-cc_descriptor_copy_and_release
- (struct cc_descriptor* dst,
- struct cc_descriptor* src)
+ptr_component_descriptor_release(struct mem_allocator* allocator, struct cc_descriptor** data)
{
- ASSERT(dst && src);
- d3_set(dst->max_vrtx, src->max_vrtx);
- dst->max_z_nz = src->max_z_nz;
- dst->max_z_side_id = src->max_z_side_id;
- dst->max_z_vrtx_id = src->max_z_vrtx_id;
- dst->side_count = src->side_count;
- dst->medium = src->medium;
- 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_uchar_copy_and_release(&dst->side_membership,
- &src->side_membership);
+ ASSERT(allocator && data);
+ darray_uchar_release(&(*data)->side_membership);
+ MEM_RM(allocator, *data);
}
-#define DARRAY_NAME cc_descriptor
-#define DARRAY_DATA struct cc_descriptor
-#define DARRAY_FUNCTOR_INIT cc_descriptor_init
-#define DARRAY_FUNCTOR_RELEASE cc_descriptor_release
-#define DARRAY_FUNCTOR_COPY cc_descriptor_copy
-#define DARRAY_FUNCTOR_COPY_AND_RELEASE cc_descriptor_copy_and_release
+#define DARRAY_NAME ptr_component_descriptor
+#define DARRAY_DATA struct cc_descriptor*
+#define DARRAY_FUNCTOR_INIT ptr_component_descriptor_init
#include <rsys/dynamic_array.h>
/* Triangle information.
diff --git a/src/senc_scene_c.h b/src/senc_scene_c.h
@@ -179,6 +179,22 @@ trg_key_eq(const union vrtx_id3* k1, const union vrtx_id3* k2)
#define HTABLE_KEY_FUNCTOR_EQ trg_key_eq
#include <rsys/hash_table.h>
+struct side_range {
+ side_id_t first, last;
+};
+static FINLINE void
+side_range_init(struct mem_allocator* alloc, struct side_range* data)
+{
+ ASSERT(data);
+ (void) alloc;
+ data->first = SIDE_NULL__;
+ data->last = 0;
+}
+#define DARRAY_NAME side_range
+#define DARRAY_DATA struct side_range
+#define DARRAY_FUNCTOR_INIT side_range_init
+#include <rsys/dynamic_array.h>
+
struct senc_scene {
/* Triangle information as given by user; no duplicates here */
struct darray_triangle_in triangles_in;
@@ -201,6 +217,7 @@ struct senc_scene {
trg_id_t ntris, nutris; /* Trg count, unique trg count */
vrtx_id_t nverts, nuverts; /* Vrtx count, unique vrtx count */
medium_id_t nmeds;
+ struct darray_side_range media_use;
ref_T ref;
struct senc_device* dev;
