commit 703a37a89bbef21f45329f06217c83e654c335b5
parent fe205d708689b01f2d47071ff6e4f19d0b684b25
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Tue, 31 Jul 2018 11:54:21 +0200
Just to save work
Diffstat:
3 files changed, 117 insertions(+), 138 deletions(-)
diff --git a/src/senc2d_internal_types.h b/src/senc2d_internal_types.h
@@ -81,15 +81,20 @@ typedef uint32_t enclosure_id_t;
/* Component IDs use the same type than enclosure IDs */
typedef enclosure_id_t component_id_t;
-#define COMPONENT_MAX__ (UINT32_MAX - 3) /* To allow special values */
+#define COMPONENT_MAX__ (UINT32_MAX - 2) /* To allow special values */
#define COMPONENT_NULL__ UINT32_MAX
/* Special values */
#define CC_GROUP_ROOT_NONE UINT32_MAX
#define CC_GROUP_ROOT_INFINITE (UINT32_MAX - 1)
-#define CC_IN_STACK (UINT32_MAX - 2)
#define CC_GROUP_ID_NONE UINT32_MAX
#define CC_ID_NONE UINT32_MAX
+/* This one is used as flag */
+enum side_flag {
+ FLAG_FRONT = BIT(0),
+ FLAG_BACK = BIT(1)
+};
+
/* This one is used as an index to arrays */
enum side_id {
SIDE_FRONT = 0,
@@ -113,6 +118,11 @@ SEGSIDE_2_SIDE(side_id_t s) {
return (s & 1) ? SIDE_BACK : SIDE_FRONT;
}
+static FINLINE enum side_flag
+SEGSIDE_2_SIDEFLAG(side_id_t s) {
+ return (s & 1) ? FLAG_BACK : FLAG_FRONT;
+}
+
static FINLINE side_id_t
SEGIDxSIDE_2_SEGSIDE(seg_id_t s, enum side_id i) {
ASSERT((((size_t)s << 1) | (i == SIDE_BACK)) < SIDE_MAX__);
diff --git a/src/senc2d_scene_analyze.c b/src/senc2d_scene_analyze.c
@@ -25,6 +25,7 @@
#include <rsys/mem_allocator.h>
#include <rsys/hash_table.h>
#include <rsys/dynamic_array.h>
+#include <rsys/dynamic_array_uchar.h>
#include <star/s2d.h>
@@ -54,40 +55,19 @@ neighbour_cmp(const void* w1, const void* w2)
return (a1 > a2) - (a1 < a2);
}
-static FINLINE res_T
-add_side_to_stack
- (const struct senc2d_scene* scn,
- struct darray_side_id* stack,
- struct segment_comp* segments_comp,
- const side_id_t side_id)
-{
- (void)scn;
- ASSERT(scn && segments_comp && stack
- && side_id < SIDE_MAX__ && side_id < 2 * scn->nusegs);
- {
- seg_id_t seg = SEGSIDE_2_SEG(side_id);
- enum side_flag sf = SEGSIDE_2_SIDE(side_id);
- ASSERT(segments_comp[seg].component[sf] == COMPONENT_NULL__);
- segments_comp[seg].component[sf] = CC_IN_STACK;
- return darray_side_id_push_back(stack, &side_id);
- }
-}
-
static side_id_t
get_side_not_in_connex_component
(const seg_id_t last_side,
const struct segside* segsides,
- struct segment_comp* segments_comp,
+ const unsigned char* processed,
side_id_t* first_side_not_in_component,
const medium_id_t medium)
{
- ASSERT(segsides && segments_comp && first_side_not_in_component);
+ ASSERT(segsides && processed && first_side_not_in_component);
{
side_id_t i = *first_side_not_in_component;
while(i <= last_side
- && (segsides[i].medium != medium
- || (segments_comp[SEGSIDE_2_SEG(i)].component[SEGSIDE_2_SIDE(i)]
- <= COMPONENT_MAX__))) {
+ && (segsides[i].medium != medium || processed[i])) {
++i;
}
*first_side_not_in_component = i + 1;
@@ -96,25 +76,6 @@ get_side_not_in_connex_component
}
}
-static FINLINE side_id_t
-get_side_from_stack
- (struct segment_comp* segments_comp,
- struct darray_side_id* stack)
-{
- ASSERT(segments_comp && stack);
- (void)segments_comp;
- {
- side_id_t id;
- size_t sz = darray_side_id_size_get(stack);
- ASSERT(sz);
- id = darray_side_id_cdata_get(stack)[sz - 1];
- ASSERT(segments_comp[SEGSIDE_2_SEG(id)].component[SEGSIDE_2_SIDE(id)]
- == CC_IN_STACK);
- darray_side_id_pop_back(stack);
- return id;
- }
-}
-
static void
get_scn_indices(const unsigned iseg, unsigned ids[2], void* ctx) {
int i;
@@ -184,11 +145,13 @@ extract_connex_components
struct darray_side_id ids_of_sides_around_max_y_vertex;
const union double2* positions;
const struct segment_tmp* segments_tmp;
+ struct segment_comp* segments_comp;
+ /* An array to flag sides when processed */
+ unsigned char* processed;
+ /* An array to store the component being processed */
+ struct darray_side_id current_component;
size_t ii, sz;
res_T res2 = RES_OK;
- /* Per-thread component table to allow sync-free access; to be merged */
- struct darray_segment_comp local_comp_array;
- struct segment_comp* local_comp;
ASSERT(segsides && desc && connex_components && segments_tmp_array
&& segments_comp_array && s2d_view && component_count && res);
@@ -196,16 +159,15 @@ extract_connex_components
scn = desc->scene;
positions = darray_position_cdata_get(&scn->vertices);
segments_tmp = darray_segment_tmp_cdata_get(segments_tmp_array);
+ segments_comp = darray_segment_comp_data_get(segments_comp_array);
darray_side_id_init(alloc, &stack);
darray_side_id_init(alloc, &ids_of_sides_around_max_y_vertex);
-
- darray_segment_comp_init(alloc, &local_comp_array);
- res2 = darray_segment_comp_resize(&local_comp_array, scn->nusegs);
- if(res2 != RES_OK) {
- *res = res2;
+ darray_side_id_init(alloc, ¤t_component);
+ processed = calloc(scn->nusegs, sizeof(unsigned char));
+ if (!processed) {
+ *res = RES_MEM_ERR;
return;
}
- local_comp = darray_segment_comp_data_get(&local_comp_array);
#ifndef NDEBUG
#pragma omp single
@@ -229,9 +191,8 @@ extract_connex_components
/* We loop on sides to build connex components. */
#pragma omp for schedule(dynamic) nowait
- for(mm = 0; mm < (int64_t)scn->nmeds; mm++) { /* Process all media */
- const medium_id_t m = (medium_id_t)mm;
- struct cc_descriptor* cc;
+ for (mm = 0; mm < (int64_t) scn->nmeds; mm++) { /* Process all media */
+ const medium_id_t m = (medium_id_t) mm;
/* Any not-already-used side is used as a starting point */
const struct side_range* media_use =
darray_side_range_cdata_get(&scn->media_use) + m;
@@ -241,147 +202,158 @@ extract_connex_components
char one = 1;
ATOMIC id;
- if(*res != RES_OK) continue;
- if(first_side_not_in_component == SIDE_NULL__)
+ if (*res != RES_OK) continue;
+ if (first_side_not_in_component == SIDE_NULL__)
continue; /* Unused medium */
ASSERT(first_side_not_in_component < 2 * scn->nusegs);
ASSERT(darray_side_id_size_get(&stack) == 0);
- for(;;) { /* Process all components for this medium */
+ ASSERT(darray_side_id_size_get(¤t_component) == 0);
+ for (;;) { /* Process all components for this medium */
const side_id_t start_side_id = get_side_not_in_connex_component
- (last_side, segsides, local_comp, &first_side_not_in_component, m);
+ (last_side, segsides, processed, &first_side_not_in_component, m);
side_id_t crt_side_id = start_side_id;
side_id_t last_side_id = start_side_id;
+ vrtx_id_t max_y_vrtx_id = VRTX_NULL__;
+ struct cc_descriptor *cc;
double max_y = -DBL_MAX;
ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nusegs);
- if(*res != RES_OK) break;
- if(start_side_id == SIDE_NULL__)
- break; /* start_side_id=SIDE_NULL__ => done! */
+ if (*res != RES_OK) break;
+ if (start_side_id == SIDE_NULL__)
+ break; /* start_side_id=SIDE_NULL__ => component done! */
#ifndef NDEBUG
{
seg_id_t tid = SEGSIDE_2_SEG(start_side_id);
- enum side_flag s = SEGSIDE_2_SIDE(start_side_id);
+ enum side_id s = SEGSIDE_2_SIDE(start_side_id);
medium_id_t side_med
= darray_segment_in_data_get(&desc->scene->segments_in)[tid].medium[s];
ASSERT(side_med == m);
}
#endif
- /* Create and init a new component */
- cc = MEM_ALLOC(alloc, sizeof(struct cc_descriptor));
- if(!cc) {
- *res = RES_MEM_ERR;
- continue;
- }
- cc_descriptor_init(alloc, cc);
- ASSERT(m == segsides[start_side_id].medium);
- id = ATOMIC_INCR(component_count) - 1;
- ASSERT(id <= COMPONENT_MAX__);
- cc->cc_id = (component_id_t)id;
- cc->side_range.first = start_side_id;
- /* First medium of the component */
- htable_media_set(&cc->media, &m, &one);
-
- for(;;) { /* Process all sides of this component */
+ for (;;) { /* Process all sides of this component */
int i;
- enum side_flag crt_side_flag = SEGSIDE_2_SIDE(crt_side_id);
+ enum side_flag crt_side_flag = SEGSIDE_2_SIDEFLAG(crt_side_id);
struct segside* crt_side = segsides + crt_side_id;
const seg_id_t crt_seg_id = SEGSIDE_2_SEG(crt_side_id);
const struct segment_in* seg_in =
darray_segment_in_cdata_get(&scn->segments_in) + crt_seg_id;
- struct segment_comp* seg_comp = local_comp + crt_seg_id;
+ unsigned char* seg_used = processed + crt_seg_id;
const struct segment_tmp* const seg_tmp = segments_tmp + crt_seg_id;
res_T tmp_res;
ASSERT(crt_seg_id < scn->nusegs);
- if(*res != RES_OK) break;
+ if (*res != RES_OK) break;
/* Record Ymax information
* Keep track of the appropriate vertex of the component in order
* to cast a ray at the component grouping step of the algorithm.
* The most appropriate vertex is (the) one with the greater Y
* coordinate. */
- if(max_y < seg_tmp->max_y) {
+ if (max_y < seg_tmp->max_y) {
/* New best vertex */
max_y = seg_tmp->max_y;
/* New vertex: reset list of sides */
darray_side_id_clear(&ids_of_sides_around_max_y_vertex);
/* Select a vertex with y == max_y */
- if(max_y == positions[seg_in->vertice_id[0]].pos.y) {
- cc->max_y_vrtx_id = seg_in->vertice_id[0];
- } else {
+ if (max_y == positions[seg_in->vertice_id[0]].pos.y) {
+ max_y_vrtx_id = seg_in->vertice_id[0];
+ }
+ else {
ASSERT(max_y == positions[seg_in->vertice_id[1]].pos.y);
- cc->max_y_vrtx_id = seg_in->vertice_id[1];
+ max_y_vrtx_id = seg_in->vertice_id[1];
}
/* List of sides using the vertex */
tmp_res = darray_side_id_push_back(&ids_of_sides_around_max_y_vertex,
&crt_side_id);
- if(tmp_res != RES_OK) *res = tmp_res;
- } else if(max_y == seg_tmp->max_y) {
+ if (tmp_res != RES_OK) *res = tmp_res;
+ }
+ else if (max_y == seg_tmp->max_y) {
/* Does this segment use the currently selected max_y vertex? */
FOR_EACH(i, 0, 2) {
- if(cc->max_y_vrtx_id == seg_in->vertice_id[i]) {
+ if (max_y_vrtx_id == seg_in->vertice_id[i]) {
/* List of sides using the vertex */
tmp_res = darray_side_id_push_back(&ids_of_sides_around_max_y_vertex,
&crt_side_id);
- if(tmp_res != RES_OK) *res = tmp_res;
+ if (tmp_res != RES_OK) *res = tmp_res;
break;
}
}
}
- if(*res != RES_OK) break;
+ if (*res != RES_OK) break;
/* Record crt_side both as component and segment level */
- cc->side_count++;
- ASSERT(seg_comp->component[crt_side_flag] > COMPONENT_MAX__);
- seg_comp->component[crt_side_flag] = cc->cc_id;
+ ASSERT((*seg_used & crt_side_flag) == 0);
+ *seg_used |= crt_side_flag;
+ tmp_res = darray_side_id_push_back(¤t_component, &crt_side_id);
+ if (tmp_res != RES_OK) *res = tmp_res;
+ if (*res != RES_OK) break;
/* Store neighbours' sides in a stack */
FOR_EACH(i, 0, 2) {
side_id_t neighbour_id = crt_side->facing_side_id[i];
seg_id_t nbour_seg_id = SEGSIDE_2_SEG(neighbour_id);
- seg_id_t nbour_side_id = SEGSIDE_2_SIDE(neighbour_id);
- struct segment_comp* nbour_comp = local_comp + nbour_seg_id;
+ enum side_flag nbour_side_id = SEGSIDE_2_SIDEFLAG(neighbour_id);
+ unsigned char* nbour_used = processed + nbour_seg_id;
const struct segside* neighbour = segsides + neighbour_id;
- if(neighbour->medium < m) {
+ if (neighbour->medium < m) {
/* Not the same medium.
* Neighbour's medium id is less than current medium: the whole
* component is to be processed by another thread (possibly the one
* associated with neighbour's medium). */
-
+ darray_side_id_clear(¤t_component);
continue;
}
- if(nbour_comp->component[nbour_side_id] != COMPONENT_NULL__) {
-#ifndef NDEBUG
- /* If already affected must be to the same component */
- ASSERT(nbour_comp->component[nbour_side_id] == CC_IN_STACK
- || nbour_comp->component[nbour_side_id] == cc->cc_id);
-#endif
- continue; /* Already processed */
- }
- tmp_res = add_side_to_stack(scn, &stack, local_comp, neighbour_id);
- if(tmp_res != RES_OK) *res = tmp_res;
- if(*res != RES_OK) break;
+ if (*nbour_used & nbour_side_id) continue; /* Already processed */
+ /* Mark neighbour as processed and stack it */
+ *nbour_used |= nbour_side_id;
+ tmp_res = darray_side_id_push_back(&stack, &neighbour_id);
+ if (tmp_res != RES_OK) *res = tmp_res;
+ if (*res != RES_OK) break;
}
- if(*res != RES_OK) break;
- if(darray_side_id_size_get(&stack) == 0)
- break; /* Empty stack => component is done! */
- crt_side_id = get_side_from_stack(local_comp, &stack);
+ if (*res != RES_OK) break;
+ sz = darray_side_id_size_get(&stack);
+ if (sz == 0) break; /* Empty stack => component is done! */
+ crt_side_id = darray_side_id_cdata_get(&stack)[sz - 1];
+ darray_side_id_pop_back(&stack);
last_side_id = MMAX(last_side_id, crt_side_id);
}
- if(*res != RES_OK) {
- MEM_RM(alloc, cc);
- cc = NULL;
- break;
- }
+ if (*res != RES_OK) break;
+
+ /* Register the new component and get it initialized */
+ cc = MEM_ALLOC(alloc, sizeof(struct cc_descriptor));
+ if (!cc) *res = RES_MEM_ERR;
+ if (*res != RES_OK) break;
- /* Keep track of this new connex component */
+ ASSERT(m == segsides[start_side_id].medium);
+ ASSERT(max_y_vrtx_id != VRTX_NULL__);
+ cc_descriptor_init(alloc, cc);
+ id = ATOMIC_INCR(component_count) - 1;
+ ASSERT(id <= COMPONENT_MAX__);
+ cc->cc_id = (component_id_t)id;
+ sz = darray_side_id_size_get(¤t_component);
+ ASSERT(sz <= SIDE_MAX__);
+ cc->side_count = (side_id_t)sz;
cc->side_range.last = last_side_id;
+ cc->side_range.first = start_side_id;
+ cc->max_y_vrtx_id = max_y_vrtx_id;
+ /* First medium of the component */
+ htable_media_set(&cc->media, &m, &one); /* FIX FIX FIX */
+
+ /* Write component membership in the global structure
+ * No need for sync here as an unique thread write a given side */
+ ASSERT(sizeof(cc->cc_id) >= 4); /* Atomic write */
+ sz = darray_side_id_size_get(¤t_component);
+ FOR_EACH(ii, 0, sz) {
+ const side_id_t s = darray_side_id_cdata_get(¤t_component)[ii];
+ segments_comp[SEGSIDE_2_SEG(s)].component[SEGSIDE_2_SIDE(s)] = cc->cc_id;
+ }
+ darray_side_id_clear(¤t_component);
/* Compute the normal at the max_y vertex. */
max_y_ny = 0;
@@ -392,7 +364,7 @@ extract_connex_components
const seg_id_t seg_id = SEGSIDE_2_SEG(side_id);
const struct segment_in* seg_in =
darray_segment_in_cdata_get(&scn->segments_in) + seg_id;
- struct segment_comp* seg_comp = local_comp + seg_id;
+ struct segment_comp* seg_comp = segments_comp + seg_id;
const union double2* vertices =
darray_position_cdata_get(&scn->vertices);
double edge[2], normal[2], norm;
@@ -402,37 +374,38 @@ extract_connex_components
* contribute (remember than x + y - x - y can be non-zero). */
ASSERT(seg_comp->component[SIDE_FRONT] == cc->cc_id
|| seg_comp->component[SIDE_BACK] == cc->cc_id);
- if(seg_comp->component[SIDE_FRONT] == seg_comp->component[SIDE_BACK])
+ if (seg_comp->component[SIDE_FRONT] == seg_comp->component[SIDE_BACK])
continue;
d2_sub(edge, vertices[seg_in->vertice_id[1]].vec,
vertices[seg_in->vertice_id[0]].vec);
d2(normal, edge[1], -edge[0]);
norm = d2_normalize(normal, normal);
- ASSERT(norm); (void)norm;
+ ASSERT(norm); (void) norm;
/* Geometrical normal points toward the back side */
- if(SEGSIDE_IS_FRONT(side_id)) {
+ if (SEGSIDE_IS_FRONT(side_id)) {
max_y_ny -= normal[1];
- } else {
+ }
+ else {
max_y_ny += normal[1];
}
}
- if(*res != RES_OK) break;
+ if (*res != RES_OK) break;
cc->is_outer_border = (max_y_ny < 0);
/* Need to synchronize connex_components growth as this global structure
* is accessed by multipe threads */
- #pragma omp critical
+#pragma omp critical
{
struct cc_descriptor** components;
sz = darray_ptr_component_descriptor_size_get(connex_components);
- if(sz <= cc->cc_id) {
+ if (sz <= cc->cc_id) {
res_T tmp_res = darray_ptr_component_descriptor_resize(connex_components,
1 + cc->cc_id);
- if(tmp_res != RES_OK) *res = tmp_res;
+ if (tmp_res != RES_OK) *res = tmp_res;
}
- if(*res == RES_OK) {
+ if (*res == RES_OK) {
/* Don't set the pointer before resize as this can lead to move data */
components =
darray_ptr_component_descriptor_data_get(connex_components);
@@ -443,6 +416,8 @@ extract_connex_components
}
} /* No barrier here */
+ free(processed);
+ darray_side_id_release(¤t_component);
darray_side_id_release(&stack);
darray_side_id_release(&ids_of_sides_around_max_y_vertex);
diff --git a/src/senc2d_scene_analyze_c.h b/src/senc2d_scene_analyze_c.h
@@ -23,12 +23,6 @@
#include <rsys/hash_table.h>
#include <rsys/double2.h>
-/* This one is used as flag */
-enum side_flag {
- FLAG_FRONT = BIT(0),
- FLAG_BACK = BIT(1)
-};
-
/* Information kept during the building side groups. */
struct segside {
/* Rank of the segside facing this segside through its vertices */
