commit 772e86fd3822edd7038bb986d54d496e6e257b18
parent d63d9621865eed644204a84a3b56d5a8397d1241
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Tue, 11 Sep 2018 17:06:25 +0200
Merge remote-tracking branch 'origin/feature_multi_mat_enclosures_2' into develop
Diffstat:
17 files changed, 516 insertions(+), 403 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -46,8 +46,8 @@ endif()
# Configure and define targets
################################################################################
set(VERSION_MAJOR 0)
-set(VERSION_MINOR 1)
-set(VERSION_PATCH 1)
+set(VERSION_MINOR 2)
+set(VERSION_PATCH 0)
set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
set(SENC2D_FILES_SRC
diff --git a/src/senc2d.h b/src/senc2d.h
@@ -66,8 +66,8 @@ struct senc2d_enclosure_header {
unsigned unique_segment_count;
/* Number of vertices */
unsigned vertices_count;
- /* The medium inside the enclosure */
- unsigned enclosed_medium;
+ /* The number of media inside the enclosure */
+ unsigned enclosed_media_count;
/* Is the enclosure infinite?
* Only the outermost enclosure is infinite. */
char is_infinite;
@@ -163,7 +163,7 @@ senc2d_scene_ref_put
SENC2D_API res_T
senc2d_descriptor_get_max_medium
(const struct senc2d_descriptor* descriptor,
- unsigned* rank);
+ unsigned* max_medium_id);
SENC2D_API res_T
senc2d_descriptor_get_enclosure_count
@@ -173,7 +173,7 @@ senc2d_descriptor_get_enclosure_count
SENC2D_API res_T
senc2d_descriptor_get_enclosure_count_by_medium
(const struct senc2d_descriptor* descriptor,
- const unsigned imed,
+ const unsigned imed, /* Must be in [0 max_medium_id] */
unsigned* count);
SENC2D_API res_T
@@ -278,6 +278,12 @@ senc2d_enclosure_get_segment_global_id
unsigned* gid);
SENC2D_API res_T
+senc2d_enclosure_get_medium
+ (const struct senc2d_enclosure* enclosure,
+ const unsigned imed,
+ unsigned* medium);
+
+SENC2D_API res_T
senc2d_enclosure_ref_get
(struct senc2d_enclosure* enclosure);
diff --git a/src/senc2d_descriptor.c b/src/senc2d_descriptor.c
@@ -86,11 +86,11 @@ struct mem_allocator*
******************************************************************************/
res_T
senc2d_descriptor_get_max_medium
- (const struct senc2d_descriptor* desc, unsigned* rank)
+ (const struct senc2d_descriptor* desc, unsigned* max_medium_id)
{
- if(!desc || !rank) return RES_BAD_ARG;
+ if(!desc || !max_medium_id) return RES_BAD_ARG;
ASSERT(desc->scene->nmeds < UINT_MAX); /* API type */
- *rank = (unsigned)desc->scene->nmeds;
+ *max_medium_id = (unsigned)desc->scene->nmeds - 1;
return RES_OK;
}
@@ -136,8 +136,7 @@ senc2d_descriptor_get_enclosure
struct senc2d_enclosure* enc;
if(!desc || idx >= darray_enclosure_size_get(&desc->enclosures) || !out_enc)
return RES_BAD_ARG;
- enc =
- enclosure_create(desc, darray_enclosure_data_get(&desc->enclosures) + idx);
+ enc = enclosure_create(desc, idx);
if(!enc) return RES_MEM_ERR;
*out_enc = enc;
return RES_OK;
diff --git a/src/senc2d_descriptor_c.h b/src/senc2d_descriptor_c.h
@@ -45,7 +45,7 @@ segment_comp_init(struct mem_allocator* alloc, struct segment_comp* seg) {
#include <rsys/dynamic_array.h>
struct segment_enc {
- /* The connex component in which each side is. */
+ /* The enclosure in which each side is. */
enclosure_id_t enclosure[2];
};
diff --git a/src/senc2d_enclosure.c b/src/senc2d_enclosure.c
@@ -45,13 +45,15 @@ enclosure_release(ref_T * ref)
struct senc2d_enclosure*
enclosure_create
(struct senc2d_descriptor* desc,
- const struct enclosure_data* data)
+ const unsigned idx)
{
struct senc2d_enclosure* enc;
- ASSERT(desc);
+ ASSERT(desc && idx < darray_enclosure_size_get(&desc->enclosures));
enc = MEM_CALLOC(descriptor_get_allocator(desc),
1, sizeof(struct senc2d_enclosure));
if(enc) {
+ const struct enclosure_data* data
+ = darray_enclosure_data_get(&desc->enclosures) + idx;
SENC2D(descriptor_ref_get(desc));
enc->desc = desc;
enc->data = data;
@@ -156,6 +158,21 @@ senc2d_enclosure_get_segment_global_id
}
res_T
+senc2d_enclosure_get_medium
+ (const struct senc2d_enclosure* enclosure,
+ const unsigned imed,
+ unsigned* medium)
+{
+ if(!enclosure || !medium
+ || imed >= enclosure->data->header.enclosed_media_count)
+ return RES_BAD_ARG;
+ ASSERT(enclosure->data->header.enclosed_media_count
+ == darray_media_size_get(&enclosure->data->enclosed_media));
+ *medium = darray_media_cdata_get(&enclosure->data->enclosed_media)[imed];
+ return RES_OK;
+}
+
+res_T
senc2d_enclosure_ref_get(struct senc2d_enclosure* enc)
{
if(!enc) return RES_BAD_ARG;
diff --git a/src/senc2d_enclosure_c.h b/src/senc2d_enclosure_c.h
@@ -32,6 +32,6 @@ struct senc2d_enclosure {
struct senc2d_enclosure*
enclosure_create
(struct senc2d_descriptor* desc,
- const struct enclosure_data* data);
+ const unsigned idx);
#endif /* SENC2D_ENCLOSURE_C_H */
diff --git a/src/senc2d_enclosure_data.h b/src/senc2d_enclosure_data.h
@@ -18,6 +18,19 @@
#include <rsys/rsys.h>
#include <rsys/ref_count.h>
+#include <rsys/hash_table.h>
+#include <rsys/dynamic_array.h>
+
+/* unsigned char array with init to zero */
+static FINLINE void
+zero_init_uchar
+ (struct mem_allocator* alloc, unsigned char* data)
+{
+ ASSERT(data); (void)alloc;
+ *data = 0;
+}
+#define DARRAY_FUNCTOR_INIT zero_init_uchar
+#include <rsys/dynamic_array_uchar.h>
#include "senc2d.h"
#include "senc2d_scene_c.h"
@@ -33,16 +46,77 @@ init_header(struct senc2d_enclosure_header* header)
header->segment_count = 0;
header->unique_segment_count = 0;
header->vertices_count = 0;
- header->enclosed_medium = MEDIUM_NULL__;
+ header->enclosed_media_count = 0;
header->is_infinite = CHAR_MAX;
}
+#define DARRAY_NAME media
+#define DARRAY_DATA medium_id_t
+#include <rsys/dynamic_array.h>
+
+static FINLINE res_T
+bool_array_of_media_merge
+ (struct darray_uchar* dst,
+ const unsigned char* src,
+ const medium_id_t sz)
+{
+ res_T res = RES_OK;
+ medium_id_t i;
+ unsigned char* data_dst;
+
+ ASSERT(src && dst);
+
+ OK(darray_uchar_resize(dst, sz));
+ data_dst = darray_uchar_data_get(dst);
+ ASSERT(sz <= MEDIUM_MAX__);
+ if(res != RES_OK) goto error;
+ FOR_EACH(i, 0, sz) {
+ if(!src[i]) continue;
+ data_dst[i] = 1;
+ }
+end:
+ return res;
+error:
+ goto end;
+}
+
+static FINLINE res_T
+bool_array_of_media_to_darray_media
+ (struct darray_media* dst,
+ struct darray_uchar* src)
+{
+ res_T res = RES_OK;
+ medium_id_t i;
+ size_t sz;
+ const unsigned char* data;
+
+ ASSERT(src && dst);
+
+ data = darray_uchar_cdata_get(src);
+ sz = darray_uchar_size_get(src);
+ ASSERT(sz <= MEDIUM_MAX__);
+ darray_media_clear(dst);
+ if(res != RES_OK) goto error;
+ FOR_EACH(i, 0, (medium_id_t)sz) {
+ if(!data[i]) continue;
+ res = darray_media_push_back(dst, &i);
+ if(res != RES_OK) goto error;
+ }
+end:
+ return res;
+error:
+ goto end;
+}
+
struct enclosure_data {
struct senc2d_enclosure_header header;
/* Same segment can appear twice if both sides */
struct darray_segment_in sides;
/* Index of vertices in scene's unique vertices */
struct darray_vrtx_id vertices;
+ /* List of the enclosed media */
+ struct darray_uchar tmp_enclosed_media;
+ struct darray_media enclosed_media;
/* Number of components involved in this enclosure */
component_id_t cc_count;
/* Linked list of the components */
@@ -64,6 +138,8 @@ enclosure_data_init(struct mem_allocator* alloc, struct enclosure_data* enc) {
enc->side_count = 0;
darray_segment_in_init(alloc, &enc->sides);
darray_vrtx_id_init(alloc, &enc->vertices);
+ darray_uchar_init(alloc, &enc->tmp_enclosed_media);
+ darray_media_init(alloc, &enc->enclosed_media);
}
static FINLINE res_T
@@ -80,6 +156,8 @@ enclosure_data_copy
dst->side_count = src->side_count;
OK(darray_segment_in_copy(&dst->sides, &src->sides));
OK(darray_vrtx_id_copy(&dst->vertices, &src->vertices));
+ OK(darray_uchar_copy(&dst->tmp_enclosed_media, &src->tmp_enclosed_media));
+ OK(darray_media_copy(&dst->enclosed_media, &src->enclosed_media));
error:
return res;
}
@@ -89,6 +167,8 @@ enclosure_data_release(struct enclosure_data* n) {
ASSERT(n);
darray_segment_in_release(&n->sides);
darray_vrtx_id_release(&n->vertices);
+ darray_uchar_release(&n->tmp_enclosed_media);
+ darray_media_release(&n->enclosed_media);
}
static FINLINE res_T
@@ -105,6 +185,9 @@ enclosure_data_copy_and_release
dst->side_count = src->side_count;
OK(darray_segment_in_copy_and_release(&dst->sides, &src->sides));
OK(darray_vrtx_id_copy_and_release(&dst->vertices, &src->vertices));
+ OK(darray_uchar_copy_and_release(&dst->tmp_enclosed_media,
+ &src->tmp_enclosed_media));
+ OK(darray_media_copy_and_release(&dst->enclosed_media, &src->enclosed_media));
error:
return res;
}
diff --git a/src/senc2d_internal_types.h b/src/senc2d_internal_types.h
@@ -81,8 +81,19 @@ 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__ ENCLOSURE_MAX__
-#define COMPONENT_NULL__ ENCLOSURE_NULL__
+#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_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 {
@@ -107,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>
@@ -33,46 +34,28 @@
#include <stdlib.h>
#define CC_DESCRIPTOR_NULL__ {\
- CHAR_MAX, VRTX_NULL__, 0, MEDIUM_NULL__,\
+ CHAR_MAX, VRTX_NULL__, 0,\
CC_ID_NONE, CC_GROUP_ROOT_NONE, ENCLOSURE_NULL__,\
- { SEG_NULL__, 0}\
+ { SEG_NULL__, 0},\
+ NULL\
}
+#ifdef COMPILER_GCC
+ #pragma GCC diagnostic push
+ #pragma GCC diagnostic ignored "-Wmissing-field-initializers"
+#endif
const struct cc_descriptor CC_DESCRIPTOR_NULL = CC_DESCRIPTOR_NULL__;
+#ifdef COMPILER_GCC
+ #pragma GCC diagnostic pop
+#endif
#define DARRAY_NAME component_id
#define DARRAY_DATA component_id_t
#include <rsys/dynamic_array.h>
-#define DARRAY_NAME side_id
-#define DARRAY_DATA side_id_t
-#include <rsys/dynamic_array.h>
-
/*******************************************************************************
* Helper function
******************************************************************************/
static INLINE int
-find_side_in_list
- (const struct segside* segsides,
- const struct darray_side_id* side_ids,
- const side_id_t side_id,
- const enum list_id list_id)
-{
- side_id_t i;
- size_t tmp;
- (void)list_id;
- (void)segsides;
- ASSERT(segsides && side_ids);
- tmp = darray_side_id_size_get(side_ids);
- ASSERT(tmp <= SIDE_MAX__);
- FOR_EACH(i, 0, (side_id_t)tmp) {
- const side_id_t id = darray_side_id_cdata_get(side_ids)[i];
- ASSERT(segsides[id].list_id & list_id);
- if(id == side_id) return 1;
- }
- return 0;
-}
-
-static INLINE int
neighbour_cmp(const void* w1, const void* w2)
{
const double a1 = ((struct neighbour_info*)w1)->angle;
@@ -80,60 +63,25 @@ 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 segside* segsides,
- const side_id_t side_id)
-{
- (void)scn;
- ASSERT(scn && segsides && stack
- && side_id < SIDE_MAX__ && side_id < 2 * scn->nusegs);
- ASSERT((darray_side_id_size_get(stack) > 128)
- || !find_side_in_list(segsides, stack, side_id, FLAG_WAITING_STACK));
- segsides[side_id].list_id = FLAG_WAITING_STACK;
- return darray_side_id_push_back(stack, &side_id);
-}
-
static side_id_t
get_side_not_in_connex_component
- (const struct senc2d_scene* scn,
+ (const side_id_t last_side,
const struct segside* segsides,
+ const unsigned char* processed,
side_id_t* first_side_not_in_component,
const medium_id_t medium)
{
- side_id_t i;
- const seg_id_t last_side
- = darray_side_range_cdata_get(&scn->media_use)[medium].last;
- ASSERT(scn && segsides && first_side_not_in_component);
- i = *first_side_not_in_component;
- while(i <= last_side
- && (segsides[i].medium != medium
- || segsides[i].list_id != FLAG_LIST_SIDE_LIST)) {
- ++i;
+ 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
+ || (processed[SEGSIDE_2_SEG(i)] & SEGSIDE_2_SIDEFLAG(i))))
+ ++i;
+ *first_side_not_in_component = i + 1;
+ if(i > last_side) return SIDE_NULL__;
+ return i;
}
-
- *first_side_not_in_component = i+1;
- if(i > last_side) return SIDE_NULL__;
- return i;
-}
-
-static FINLINE side_id_t
-get_side_from_stack
- (const struct segside* segsides,
- struct darray_side_id* stack)
-{
- side_id_t id;
- size_t sz;
- (void)segsides;
- ASSERT(segsides && stack);
- sz = darray_side_id_size_get(stack);
- ASSERT(sz);
- id = darray_side_id_cdata_get(stack)[sz - 1];
- ASSERT(segsides[id].list_id == FLAG_WAITING_STACK);
- darray_side_id_pop_back(stack);
- return id;
}
static void
@@ -189,12 +137,12 @@ extract_connex_components
struct segside* segsides,
struct darray_ptr_component_descriptor* connex_components,
const struct darray_segment_tmp* segments_tmp_array,
- struct darray_segment_comp* segments_comp,
+ struct darray_segment_comp* segments_comp_array,
struct s2d_scene_view** s2d_view,
ATOMIC* component_count,
/* Shared error status.
* We accept to overwritte an error with a different error */
- res_T* res)
+ res_T* p_res)
{
/* This function is called from an omp parallel block and executed
* concurrently. */
@@ -204,23 +152,36 @@ extract_connex_components
struct darray_side_id stack;
struct darray_side_id ids_of_sides_around_max_y_vertex;
const union double2* positions;
- size_t sz, ii;
-#ifndef NDEBUG
- seg_id_t s_;
- component_id_t c;
-#endif
+ 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;
+ /* A bool array to store media of the component being processed */
+ unsigned char* current_media = NULL;
+ size_t ii, sz;
ASSERT(segsides && desc && connex_components && segments_tmp_array
- && s2d_view && component_count && res);
+ && segments_comp_array && s2d_view && component_count && p_res);
alloc = descriptor_get_allocator(desc);
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_side_id_init(alloc, ¤t_component);
+ processed = MEM_CALLOC(alloc, scn->nusegs, sizeof(unsigned char));
+ if(!processed) {
+ *p_res = RES_MEM_ERR;
+ return;
+ }
#ifndef NDEBUG
#pragma omp single
{
+ seg_id_t s_;
ASSERT(darray_ptr_component_descriptor_size_get(connex_components) == 0);
FOR_EACH(s_, 0, scn->nusegs) {
const struct segment_in* seg_in =
@@ -237,75 +198,77 @@ extract_connex_components
} /* Implicit barrier here */
#endif
+ /* 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;
/* Any not-already-used side is used as a starting point */
- side_id_t first_side_not_in_component;
+ const struct side_range* media_use =
+ darray_side_range_cdata_get(&scn->media_use) + m;
+ side_id_t first_side_not_in_component = media_use->first;
double max_y_ny;
+ const side_id_t last_side = media_use->last;
+ int component_canceled = 0;
+ res_T tmp_res = RES_OK;
+ ATOMIC id;
- if(*res != RES_OK) continue;
- first_side_not_in_component
- = darray_side_range_cdata_get(&scn->media_use)[m].first;
+ if(*p_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);
+ 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(scn,
- segsides, &first_side_not_in_component, m);
+ const side_id_t start_side_id = get_side_not_in_connex_component
+ (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);
+ darray_side_id_clear(¤t_component);
- if(*res != RES_OK) break;
+ if(*p_res != RES_OK) break;
if(start_side_id == SIDE_NULL__)
- break; /* start_side_id=SIDE_NULL__ => done! */
- ASSERT(segsides[start_side_id].list_id == FLAG_LIST_SIDE_LIST);
+ 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);
+ seg_id_t sid = SEGSIDE_2_SEG(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];
+ = darray_segment_in_data_get(&desc->scene->segments_in)[sid].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;
+ /* Reuse array if possible, or create a new one */
+ if(current_media) {
+ memset(current_media, 0, scn->nmeds);
+ } else {
+ current_media = MEM_CALLOC(alloc, scn->nmeds, sizeof(unsigned char));
+ if(!current_media) {
+ *p_res = RES_MEM_ERR;
+ continue;
+ }
}
- cc_descriptor_init(alloc, cc);
- ASSERT(m == segsides[start_side_id].medium);
- cc->cc_id = (component_id_t)(ATOMIC_INCR(component_count) - 1);
- cc->medium = m;
- cc->side_range.first = start_side_id;
-
+ current_media[m] = 1;
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 =
- darray_segment_comp_data_get(segments_comp) + crt_seg_id;
- const struct segment_tmp* const seg_tmp =
- darray_segment_tmp_cdata_get(segments_tmp_array) + crt_seg_id;
+ unsigned char* seg_used = processed + crt_seg_id;
+ const struct segment_tmp* const seg_tmp = segments_tmp + crt_seg_id;
ASSERT(crt_seg_id < scn->nusegs);
- ASSERT(segsides[crt_side_id].medium == m);
-
- if(*res != RES_OK) break;
+ if(*p_res != RES_OK) break;
/* Record Ymax information
- * Keep track of the appropriate vertex of the connex component in order
+ * 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. */
@@ -315,96 +278,95 @@ extract_connex_components
/* New vertex: reset list of sides */
darray_side_id_clear(&ids_of_sides_around_max_y_vertex);
- /* Select one vertex with y == max_y */
+ /* 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];
+ 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 */
- *res = darray_side_id_push_back(&ids_of_sides_around_max_y_vertex,
- &crt_side_id);
+ OK2(darray_side_id_push_back(&ids_of_sides_around_max_y_vertex,
+ &crt_side_id));
} 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 */
- *res = darray_side_id_push_back(&ids_of_sides_around_max_y_vertex,
- &crt_side_id);
+ OK2(darray_side_id_push_back(&ids_of_sides_around_max_y_vertex,
+ &crt_side_id));
break;
}
}
}
- if(*res != RES_OK) break;
/* Record crt_side both as component and segment level */
- cc->side_count++;
- segsides[crt_side_id].list_id = FLAG_LIST_COMPONENT;
- ASSERT(seg_comp->component[crt_side_flag] == COMPONENT_NULL__);
- seg_comp->component[crt_side_flag] = cc->cc_id;
-#ifndef NDEBUG
- crt_side->member_of_cc = cc->cc_id;
-#endif
+ if((*seg_used & crt_side_flag) == 0) {
+ OK2(darray_side_id_push_back(¤t_component, &crt_side_id));
+ *seg_used |= (unsigned char)crt_side_flag;
+ }
- /* Store neighbour sides in a waiting stack */
+ /* 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);
+ 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;
- ASSERT(m == crt_side->medium);
- if(neighbour->medium != crt_side->medium) {
- /* Found medium discontinuity! Model topology is broken. */
- const struct segment_in* segments_in
- = darray_segment_in_cdata_get(&scn->segments_in);
- log_err(scn->dev,
- "Medium mismatch found between neighbour segments %lu %s"
- " side and %u %s side.\n",
- (unsigned long)segments_in[crt_seg_id].global_id,
- SEGSIDE_IS_FRONT(crt_side_id) ? "front" : "back",
- segments_in[nbour_seg_id].global_id,
- SEGSIDE_IS_FRONT(neighbour_id) ? "front" : "back");
- log_err(scn->dev,
- "Segment %lu:\n (%g %g) (%g %g))\n",
- (unsigned long)segments_in[crt_seg_id].global_id,
- SPLIT2(positions[segments_in[crt_seg_id].vertice_id[0]].vec),
- SPLIT2(positions[segments_in[crt_seg_id].vertice_id[1]].vec));
- log_err(scn->dev,
- "Segment %lu:\n (%g %g) (%g %g)\n",
- (unsigned long)segments_in[nbour_seg_id].global_id,
- SPLIT2(positions[segments_in[nbour_seg_id].vertice_id[0]].vec),
- SPLIT2(positions[segments_in[nbour_seg_id].vertice_id[1]].vec));
- log_err(desc->scene->dev, "Media: %lu VS %lu\n",
- (unsigned long)neighbour->medium, (unsigned long)crt_side->medium);
- *res = RES_BAD_ARG;
- break;
+ if(*nbour_used & nbour_side_id) continue; /* Already processed */
+ 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). */
+ component_canceled = 1;
+ goto canceled;
}
- if(neighbour->list_id == FLAG_LIST_COMPONENT) {
- /* Already processed */
-#ifndef NDEBUG
- ASSERT(neighbour->member_of_cc == cc->cc_id);
-#endif
- continue;
- }
- if(neighbour->list_id == FLAG_WAITING_STACK) {
- continue; /* Already processed */
- }
- *res = add_side_to_stack(scn, &stack, segsides, neighbour_id);
- if(*res != RES_OK) break;
+ /* Mark neighbour as processed and stack it */
+ *nbour_used |= (unsigned char)nbour_side_id;
+ OK2(darray_side_id_push_back(&stack, &neighbour_id));
+ OK2(darray_side_id_push_back(¤t_component, &neighbour_id));
+ current_media[neighbour->medium] = 1;
}
- if(*res != RES_OK) break;
- if(darray_side_id_size_get(&stack) == 0)
- break; /* Empty stack => connex component is done! */
- crt_side_id = get_side_from_stack(segsides, &stack);
+ 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;
- }
- /* Keep track of this new connex component */
+canceled:
+ if(component_canceled) continue;
+
+ /* Register the new component and get it initialized */
+ cc = MEM_ALLOC(alloc, sizeof(struct cc_descriptor));
+ if(!cc) *p_res = RES_MEM_ERR;
+ if(*p_res != RES_OK) break;
+
+ 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.first = start_side_id;
cc->side_range.last = last_side_id;
+ cc->max_y_vrtx_id = max_y_vrtx_id;
+ /* Tranfer ownership of the array to component */
+ ASSERT(!cc->media && current_media);
+ cc->media = current_media;
+ current_media = NULL;
+
+ /* Write component membership in the global structure
+ * No need for sync here as an unique thread write a given side */
+ STATIC_ASSERT(sizeof(cc->cc_id) >= 4, Cannot_write_IDs_sync_free);
+ ASSERT(IS_ALIGNED(segments_comp->component, sizeof(cc->cc_id)));
+ 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;
+ }
/* Compute the normal at the max_y vertex. */
max_y_ny = 0;
@@ -415,8 +377,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 =
- darray_segment_comp_data_get(segments_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;
@@ -442,7 +403,6 @@ extract_connex_components
max_y_ny += normal[1];
}
}
- if(*res != RES_OK) break;
cc->is_outer_border = (max_y_ny < 0);
/* Need to synchronize connex_components growth as this global structure
@@ -452,11 +412,11 @@ extract_connex_components
struct cc_descriptor** components;
sz = darray_ptr_component_descriptor_size_get(connex_components);
if(sz <= cc->cc_id) {
- res_T tmp_res = darray_ptr_component_descriptor_resize(connex_components,
+ 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) *p_res = tmp_res;
}
- if(*res == RES_OK) {
+ if(*p_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);
@@ -465,15 +425,20 @@ extract_connex_components
}
}
}
+ tmp_error:
+ if(tmp_res != RES_OK) *p_res = tmp_res;
} /* No barrier here */
+ MEM_RM(alloc, processed);
+ MEM_RM(alloc, current_media);
+ darray_side_id_release(¤t_component);
darray_side_id_release(&stack);
darray_side_id_release(&ids_of_sides_around_max_y_vertex);
/* The first thread here creates the s2d view */
#pragma omp single nowait
- if(*res == RES_OK) {
- res_T tmp_res = RES_OK;
+ if(*p_res == RES_OK) {
+ res_T res = RES_OK;
struct s2d_device* s2d = NULL;
struct s2d_scene* s2d_scn = NULL;
struct s2d_shape* s2d_shp = NULL;
@@ -484,22 +449,22 @@ extract_connex_components
attribs.get = get_scn_position;
/* Put geometry in a 2D view */
- OK2(s2d_device_create(desc->scene->dev->logger, alloc, 0, &s2d));
- OK2(s2d_scene_create(s2d, &s2d_scn));
- OK2(s2d_shape_create_line_segments(s2d, &s2d_shp));
+ OK(s2d_device_create(desc->scene->dev->logger, alloc, 0, &s2d));
+ OK(s2d_scene_create(s2d, &s2d_scn));
+ OK(s2d_shape_create_line_segments(s2d, &s2d_shp));
/* Back to API type for ntris and nverts */
ASSERT(desc->scene->nusegs < UINT_MAX);
ASSERT(desc->scene->nuverts < UINT_MAX);
- OK2(s2d_line_segments_setup_indexed_vertices(s2d_shp,
+ OK(s2d_line_segments_setup_indexed_vertices(s2d_shp,
(unsigned)desc->scene->nusegs, get_scn_indices,
(unsigned)desc->scene->nuverts, &attribs, 1, desc->scene));
s2d_line_segments_set_hit_filter_function(s2d_shp, self_hit_filter,
- segments_comp);
- OK2(s2d_scene_attach_shape(s2d_scn, s2d_shp));
- OK2(s2d_scene_view_create(s2d_scn, S2D_TRACE, s2d_view));
- tmp_error:
- if(tmp_res != RES_OK) *res = tmp_res;
+ segments_comp_array);
+ OK(s2d_scene_attach_shape(s2d_scn, s2d_shp));
+ OK(s2d_scene_view_create(s2d_scn, S2D_TRACE, s2d_view));
+ error:
+ if(res != RES_OK) *p_res = res;
if(s2d) S2D(device_ref_put(s2d));
if(s2d_scn) S2D(scene_ref_put(s2d_scn));
if(s2d_shp) S2D(shape_ref_put(s2d_shp));
@@ -508,25 +473,25 @@ extract_connex_components
#ifndef NDEBUG
/* Need to wait for all threads done to be able to check stuff */
#pragma omp barrier
- if(*res != RES_OK) return;
+ if(*p_res != RES_OK) return;
#pragma omp single
{
+ seg_id_t s_;
+ component_id_t c;
ASSERT(ATOMIC_GET(component_count) ==
(int)darray_ptr_component_descriptor_size_get(connex_components));
FOR_EACH(s_, 0, scn->nusegs) {
- struct segment_comp* seg_comp =
- darray_segment_comp_data_get(segments_comp) + s_;
+ struct segment_comp* seg_comp =
+ darray_segment_comp_data_get(segments_comp_array) + s_;
ASSERT(seg_comp->component[SIDE_FRONT] != COMPONENT_NULL__);
ASSERT(seg_comp->component[SIDE_BACK] != COMPONENT_NULL__);
}
FOR_EACH(c, 0, ATOMIC_GET(component_count)) {
struct cc_descriptor** components =
darray_ptr_component_descriptor_data_get(connex_components);
- ASSERT(components[c] != NULL &&
- components[c]->cc_id == c);
+ ASSERT(components[c] != NULL && components[c]->cc_id == c);
}
- ASSERT(desc->segment_count
- == darray_segment_comp_size_get(segments_comp));
+ ASSERT(desc->segment_count == scn->nusegs);
} /* Implicit barrier here */
#endif
}
@@ -539,7 +504,6 @@ group_connex_components
struct darray_ptr_component_descriptor* connex_components,
struct s2d_scene_view* s2d_view,
ATOMIC* next_enclosure_id,
- ATOMIC* infinity_first_cc,
/* Shared error status.
* We accept to overwritte an error with a different error */
res_T* res)
@@ -554,7 +518,7 @@ group_connex_components
(void)segsides;
ASSERT(desc && segsides && segments_comp && connex_components
- && s2d_view && next_enclosure_id && infinity_first_cc && res);
+ && s2d_view && next_enclosure_id && res);
ASSERT(desc->enclosures_count == 1);
descriptors = darray_ptr_component_descriptor_data_get(connex_components);
@@ -574,18 +538,20 @@ group_connex_components
const float range[2] = { 0, FLT_MAX };
struct cc_descriptor* const cc = descriptors[c];
component_id_t self_hit_component = cc->cc_id;
- const double* max_vrtx = positions[cc->max_y_vrtx_id].vec;
+ const double* max_vrtx;
if(*res != RES_OK) continue;
ASSERT(cc->cc_id == c);
ASSERT(cc->cc_group_root == CC_GROUP_ID_NONE);
+ ASSERT(cc->max_y_vrtx_id < desc->scene->nverts);
+ max_vrtx = positions[cc->max_y_vrtx_id].vec;
if(cc->is_outer_border) {
- int64_t id;
+ ATOMIC id;
/* Don't need to cast a ray */
cc->cc_group_root = cc->cc_id; /* New group with self as root */
id = ATOMIC_INCR(next_enclosure_id) - 1;
- ASSERT(id < ENCLOSURE_MAX__);
+ ASSERT(id <= ENCLOSURE_MAX__);
cc->enclosure_id = (enclosure_id_t)id;
continue;
}
@@ -600,83 +566,20 @@ group_connex_components
}
/* If no hit, the component is facing an infinite medium */
if(S2D_HIT_NONE(&hit)) {
- struct cc_descriptor* inf_first_cc;
cc->cc_group_root = CC_GROUP_ROOT_INFINITE;
cc->enclosure_id = 0;
- /* Keep track of the first component facing infinity */
- ATOMIC_CAS(infinity_first_cc, (ATOMIC)cc, (ATOMIC)NULL);
- inf_first_cc = (struct cc_descriptor*)ATOMIC_GET(infinity_first_cc);
- if(inf_first_cc->medium != cc->medium) {
- /* Medium mismatch! Model topology is broken. */
- const double* infinity_max_vrtx =
- positions[inf_first_cc->max_y_vrtx_id].vec;
- log_err(desc->scene->dev,
- "Medium mismatch found between vertex %lu and vertex %lu,"
- " both facing infinity.\n",
- (unsigned long) inf_first_cc->max_y_vrtx_id,
- (unsigned long)cc->max_y_vrtx_id);
- log_err(desc->scene->dev,
- "Vertex %lu: (%g %g)\n",
- (unsigned long) inf_first_cc->max_y_vrtx_id,
- SPLIT2(infinity_max_vrtx));
- log_err(desc->scene->dev,
- "Vertex %lu: (%g %g)\n",
- (unsigned long)cc->max_y_vrtx_id,
- SPLIT2(max_vrtx));
- log_err(desc->scene->dev, "Media: %lu VS %lu\n",
- (unsigned long) inf_first_cc->medium, (unsigned long)cc->medium);
- *res = RES_BAD_ARG;
- }
- /* Same medium as previous members of the group: OK */
} else {
/* If hit, group this component */
const seg_id_t hit_seg_id = (seg_id_t)hit.prim.prim_id;
- const struct segment_in* hit_seg_in =
- darray_segment_in_cdata_get(&desc->scene->segments_in) + hit_seg_id;
const struct segment_comp* hit_seg_comp =
darray_segment_comp_cdata_get(segments_comp) + hit_seg_id;
enum side_id hit_side = (hit.normal[1] > 0) ? SIDE_FRONT : SIDE_BACK;
- const side_id_t hit_side_id = SEGIDxSIDE_2_SEGSIDE(hit_seg_id, hit_side);
-
+
ASSERT(hit_seg_id < desc->scene->nusegs);
/* Not really the root until following links */
cc->cc_group_root = hit_seg_comp->component[hit_side];
-#ifndef NDEBUG
- {
- const struct cc_descriptor* hit_desc;
- ASSERT(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_seg_in->medium[hit_side]);
- }
-#endif
- if(hit_seg_in->medium[hit_side] != cc->medium) {
- /* Medium mismatch! Model topology is broken. */
- const seg_id_t seg = SEGSIDE_2_SEG(hit_side_id);
- const struct segment_in* segments_in
- = darray_segment_in_cdata_get(&desc->scene->segments_in);
- log_err(desc->scene->dev,
- "Medium mismatch found between vertex %lu and segment"
- " %lu %s side facing each other.\n",
- (unsigned long)cc->max_y_vrtx_id,
- (unsigned long)segments_in[seg].global_id,
- SEGSIDE_IS_FRONT(hit_side_id) ? "front" : "back");
- log_err(desc->scene->dev,
- "Vertex %lu: (%g %g)\n",
- (unsigned long)cc->max_y_vrtx_id,
- SPLIT2(max_vrtx));
- log_err(desc->scene->dev,
- "Segment %lu:\n (%g %g) (%g %g)\n",
- (unsigned long)segments_in[seg].global_id,
- SPLIT2(positions[segments_in[seg].vertice_id[0]].vec),
- SPLIT2(positions[segments_in[seg].vertice_id[1]].vec));
- log_err(desc->scene->dev, "Media: %lu VS %lu\n",
- (unsigned long)cc->medium,
- (unsigned long)hit_seg_in->medium[hit_side]);
- *res = RES_BAD_ARG;
- }
+ ASSERT(cc->cc_group_root < cc_count);
}
}
/* Implicit barrier here */
@@ -692,12 +595,13 @@ group_connex_components
if(tmp_res != RES_OK) {
*res = tmp_res;
} else {
+ struct enclosure_data* enclosures
+ = darray_enclosure_data_get(&desc->enclosures);
FOR_EACH(ccc, 0, cc_count) {
component_id_t c = (component_id_t)ccc;
struct cc_descriptor* const cc = descriptors[c];
const struct cc_descriptor* other_desc = cc;
- struct enclosure_data* enclosures
- = darray_enclosure_data_get(&desc->enclosures);
+ struct enclosure_data* enc;
while(other_desc->enclosure_id == CC_GROUP_ID_NONE) {
other_desc = *(darray_ptr_component_descriptor_cdata_get(connex_components)
@@ -705,17 +609,21 @@ group_connex_components
}
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;
+ enc = enclosures + cc->enclosure_id;
+ ++enc->cc_count;
/* Linked list of componnents */
- enclosures[cc->enclosure_id].first_component = cc->cc_id;
- enclosures[cc->enclosure_id].side_range.first
- = MMIN(enclosures[cc->enclosure_id].side_range.first, cc->side_range.first);
- enclosures[cc->enclosure_id].side_range.last
- = MMAX(enclosures[cc->enclosure_id].side_range.last, cc->side_range.last);
- enclosures[cc->enclosure_id].side_count += cc->side_count;
+ enc->first_component = cc->cc_id;
+ enc->side_range.first = MMIN(enc->side_range.first, cc->side_range.first);
+ enc->side_range.last = MMAX(enc->side_range.last, cc->side_range.last);
+ enc->side_count += cc->side_count;
+ tmp_res = bool_array_of_media_merge(&enc->tmp_enclosed_media, cc->media,
+ desc->scene->nmeds);
+ if(tmp_res != RES_OK) {
+ *res = tmp_res;
+ break;
+ }
}
}
}
@@ -874,8 +782,6 @@ collect_and_link_neighbours
p_ccw_side->medium = segments_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;
}
}
/* Threads are allowed to return whitout sync. */
@@ -906,7 +812,7 @@ build_result
alloc = descriptor_get_allocator(desc);
ASSERT(darray_ptr_component_descriptor_size_get(connex_components)
- < COMPONENT_MAX__);
+ <= COMPONENT_MAX__);
cc_descriptors = darray_ptr_component_descriptor_cdata_get(connex_components);
enclosures = darray_enclosure_data_get(&desc->enclosures);
segments_in = darray_segment_in_cdata_get(&desc->scene->segments_in);
@@ -946,33 +852,45 @@ build_result
for(ee = 0; ee < (int64_t)desc->enclosures_count; ee++) {
const enclosure_id_t e = (enclosure_id_t)ee;
struct enclosure_data* enc = enclosures + e;
- const struct cc_descriptor* current = cc_descriptors[enc->first_component];
- struct darray_enc_id* enc_ids_by_medium;
seg_id_t fst_idx = 0;
seg_id_t sgd_idx = enc->side_count;
seg_id_t s;
+ medium_id_t m;
res_T tmp_res = RES_OK;
ASSERT(enc->first_component
< darray_ptr_component_descriptor_size_get(connex_components));
- ASSERT(current->cc_id == enc->first_component);
+ ASSERT(cc_descriptors[enc->first_component]->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);
+ ASSERT(cc_descriptors[enc->first_component]->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);
-
- enc_ids_by_medium =
- darray_enc_ids_array_data_get(&desc->enc_ids_array_by_medium)
- + current->medium;
- #pragma omp critical
- {
- tmp_res = darray_enc_id_push_back(enc_ids_by_medium, &e);
+
+ ASSERT(darray_uchar_size_get(&enc->tmp_enclosed_media) <= UINT_MAX);
+ ASSERT(enc->header.enclosed_media_count <= desc->scene->nmeds);
+ OK2(bool_array_of_media_to_darray_media
+ (&enc->enclosed_media, &enc->tmp_enclosed_media));
+ enc->header.enclosed_media_count
+ = (unsigned)darray_media_size_get(&enc->enclosed_media);
+ darray_uchar_purge(&enc->tmp_enclosed_media);
+
+ /* Add this enclosure in relevant by-medium lists */
+ FOR_EACH(m, 0, enc->header.enclosed_media_count) {
+ medium_id_t medium = darray_media_data_get(&enc->enclosed_media)[m];
+ struct darray_enc_id* enc_ids_by_medium =
+ darray_enc_ids_array_data_get(&desc->enc_ids_array_by_medium) + medium;
+ #pragma omp critical
+ {
+ tmp_res = darray_enc_id_push_back(enc_ids_by_medium, &e);
+ }
+ if(tmp_res != RES_OK) {
+ *res = tmp_res;
+ break;
+ }
}
- if(tmp_res != RES_OK) *res = tmp_res;
if(*res != RES_OK) continue;
/* Build side and vertex lists. */
@@ -1071,10 +989,6 @@ senc2d_scene_analyze
/* Atomic counters to share beetwen threads */
ATOMIC component_count = 0;
ATOMIC next_enclosure_id = 1;
- /* Used as args to have shared vars between threads in functions */
- static_assert(sizeof(intptr_t) == sizeof(ATOMIC),
- "Cannot use ATOMIC to store pointers");
- ATOMIC infinity_first_cc = (ATOMIC) NULL;
res_T res = RES_OK;
res_T res2 = RES_OK;
@@ -1102,7 +1016,7 @@ senc2d_scene_analyze
/* We create a neighbourhood for every single unique vertex,
* regardless the fact it is used by a segment.
- * This allows threads to use these neighbourhoods whithout syn. */
+ * This allows threads to use these neighbourhoods whithout sync. */
darray_neighbourhood_init(scn->dev->allocator, &neighbourhood_by_vertex);
neighbourhood_by_vertex_initialized = 1;
OK(darray_neighbourhood_resize(&neighbourhood_by_vertex, scn->nuverts));
@@ -1123,6 +1037,7 @@ senc2d_scene_analyze
#pragma omp single
{
res_T tmp_res = RES_OK;
+
darray_ptr_component_descriptor_init(scn->dev->allocator,
&connex_components);
connex_components_initialized = 1;
@@ -1187,7 +1102,7 @@ senc2d_scene_analyze
/* Step 3: group components */
group_connex_components(desc, segsides, &segments_comp, &connex_components,
- s2d_view, &next_enclosure_id, &infinity_first_cc, &res);
+ s2d_view, &next_enclosure_id, &res);
/* Barrier at the end of step 3: data used in step 3 can be released /
* data produced by step 3 can be used */
@@ -1230,7 +1145,6 @@ senc2d_scene_analyze
{
#pragma omp section
{
- ASSERT(connex_components_initialized);
custom_darray_ptr_component_descriptor_release(&connex_components);
connex_components_initialized = 0;
}
diff --git a/src/senc2d_scene_analyze_c.h b/src/senc2d_scene_analyze_c.h
@@ -20,65 +20,45 @@
#include "senc2d_internal_types.h"
#include <rsys/mem_allocator.h>
-#include <rsys/dynamic_array_uchar.h>
#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)
-};
-
-enum list_id {
- FLAG_NO_LIST = 0,
- FLAG_LIST_SIDE_LIST = BIT(1),
- FLAG_LIST_COMPONENT = BIT(2),
- FLAG_WAITING_STACK = BIT(3),
- FLAG_ANY_LIST = 0xFF
-};
-
/* Information kept during the building side groups. */
struct segside {
/* Rank of the segside facing this segside through its vertices */
side_id_t facing_side_id[2];
/* Id of this segside's medium */
medium_id_t medium;
- /* The list containing the segside; made of enum list_id flags */
- unsigned char list_id;
/* Implicit information that we don't need to store:
* - segment_id
* - side
* This is due to the memory layout of the elt darray:
* front(seg_0), back(seg_0), front(seg_1), back(seg_1), ... */
-
-#ifndef NDEBUG
- component_id_t member_of_cc;
-#endif
};
-/* Descriptors for connex component.
+#define DARRAY_NAME side_id
+#define DARRAY_DATA side_id_t
+#include <rsys/dynamic_array.h>
+
+/* Descriptors for connex components.
* Define lists of seg sides starting from a given head.
* Also keeps the maximum y info of the component
- * along with the associated segment and vertex ids */
-#define CC_ID_NONE COMPONENT_MAX__
-#define CC_GROUP_ROOT_NONE COMPONENT_MAX__
-#define CC_GROUP_ROOT_INFINITE (COMPONENT_MAX__-1)
-#define CC_GROUP_ID_NONE COMPONENT_MAX__
+ * along with the associated segment and vertex ids
+ * and the list of media found */
struct cc_descriptor {
/* Does this component is an outer border of an enclosure or an inner one? */
char is_outer_border;
- vrtx_id_t max_y_vrtx_id;
+ vrtx_id_t max_y_vrtx_id; /* id of the vrtx with max y value */
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;
/* Range of sides member of this component */
struct side_range side_range;
+ /* Media used by this component */
+ unsigned char* media;
};
extern const struct cc_descriptor CC_DESCRIPTOR_NULL;
@@ -118,7 +98,11 @@ custom_darray_ptr_component_descriptor_release
if(!array) return;
cc_count = darray_ptr_component_descriptor_size_get(array);
components = darray_ptr_component_descriptor_data_get(array);
- FOR_EACH(c, 0, cc_count) MEM_RM(array->allocator, components[c]);
+ FOR_EACH(c, 0, cc_count) {
+ if(!components[c]) continue;
+ MEM_RM(array->allocator, components[c]->media);
+ MEM_RM(array->allocator, components[c]);
+ }
darray_ptr_component_descriptor_release(array);
}
diff --git a/src/test_senc2d_descriptor.c b/src/test_senc2d_descriptor.c
@@ -28,7 +28,7 @@ main(int argc, char** argv)
struct senc2d_descriptor* desc = NULL;
struct senc2d_enclosure* enc = NULL;
struct context ctx;
- unsigned count;
+ unsigned count, maxm;
unsigned indices[2];
double coord[2];
unsigned media[2];
@@ -61,12 +61,12 @@ main(int argc, char** argv)
CHK(senc2d_descriptor_ref_put(NULL) == RES_BAD_ARG);
CHK(senc2d_descriptor_ref_put(desc) == RES_OK);
- CHK(senc2d_descriptor_get_max_medium(NULL, &count) == RES_BAD_ARG);
+ CHK(senc2d_descriptor_get_max_medium(NULL, &maxm) == RES_BAD_ARG);
CHK(senc2d_descriptor_get_max_medium(desc, NULL) == RES_BAD_ARG);
- CHK(senc2d_descriptor_get_enclosure_count(NULL, NULL) == RES_BAD_ARG);
- CHK(senc2d_descriptor_get_max_medium(desc, &count) == RES_OK);
+ CHK(senc2d_descriptor_get_max_medium(NULL, NULL) == RES_BAD_ARG);
+ CHK(senc2d_descriptor_get_max_medium(desc, &maxm) == RES_OK);
- CHK(count == 2);
+ CHK(maxm == 1);
CHK(senc2d_descriptor_get_enclosure_count(NULL, &count) == RES_BAD_ARG);
CHK(senc2d_descriptor_get_enclosure_count(desc, NULL) == RES_BAD_ARG);
diff --git a/src/test_senc2d_enclosure.c b/src/test_senc2d_enclosure.c
@@ -132,7 +132,16 @@ main(int argc, char** argv)
CHK(senc2d_enclosure_get_segment_global_id(NULL, nsegments, NULL)
== RES_BAD_ARG);
CHK(senc2d_enclosure_get_segment_global_id(enclosure, 0, &gid) == RES_OK);
-
+
+ CHK(senc2d_enclosure_get_medium(NULL, 0, medium) == RES_BAD_ARG);
+ CHK(senc2d_enclosure_get_medium(enclosure, 2, medium) == RES_BAD_ARG);
+ CHK(senc2d_enclosure_get_medium(enclosure, 0, NULL) == RES_BAD_ARG);
+ CHK(senc2d_enclosure_get_medium(NULL, 2, medium) == RES_BAD_ARG);
+ CHK(senc2d_enclosure_get_medium(NULL, 0, NULL) == RES_BAD_ARG);
+ CHK(senc2d_enclosure_get_medium(enclosure, 2, NULL) == RES_BAD_ARG);
+ CHK(senc2d_enclosure_get_medium(NULL, 2, NULL) == RES_BAD_ARG);
+ CHK(senc2d_enclosure_get_medium(enclosure, 0, medium) == RES_OK);
+
CHK(senc2d_enclosure_ref_put(enclosure) == RES_OK);
FOR_EACH(i, 0, ecount) {
@@ -144,7 +153,7 @@ main(int argc, char** argv)
CHK(senc2d_enclosure_get_header(enclosure, &header) == RES_OK);
CHK(header.enclosure_id == i);
- CHK((header.enclosed_medium == 0) == header.is_infinite);
+ CHK(header.enclosed_media_count == 1);
CHK(header.segment_count == nsegments);
CHK(header.unique_segment_count == nsegments);
CHK(header.vertices_count == nvertices);
@@ -203,7 +212,7 @@ main(int argc, char** argv)
CHK(senc2d_enclosure_get_header(enclosure, &header) == RES_OK);
CHK(header.enclosure_id == 0);
- CHK(header.enclosed_medium == 0);
+ CHK(header.enclosed_media_count == 1);
CHK(header.segment_count == 2 * header.unique_segment_count);
CHK(header.unique_segment_count == nsegments - 1);
CHK(header.vertices_count == nvertices);
diff --git a/src/test_senc2d_many_enclosures.c b/src/test_senc2d_many_enclosures.c
@@ -128,12 +128,15 @@ main(int argc, char** argv)
FOR_EACH(e, 0, count) {
struct senc2d_enclosure* enclosure;
struct senc2d_enclosure_header header;
+ unsigned m;
CHK(senc2d_descriptor_get_enclosure(desc, e, &enclosure) == RES_OK);
CHK(senc2d_enclosure_get_header(enclosure, &header) == RES_OK);
+ CHK(header.enclosed_media_count == 1);
+ CHK(senc2d_enclosure_get_medium(enclosure, 0, &m) == RES_OK);
CHK(header.segment_count ==
- (e == 0 /* Outermost enclosure: NB_CIRC_1*NB_CIRC_1 circles */
+ (header.is_infinite /* Outermost enclosure: NB_CIRC_1*NB_CIRC_1 circles */
? NB_CIRC_1 * NB_CIRC_1 * circ_seg_count
- : (header.enclosed_medium == 0
+ : (m == 0
? circ_seg_count /* Innermost enclosures: 1 circle */
: 2 * circ_seg_count))); /* Other enclosures: 2 circles */
CHK(senc2d_enclosure_ref_put(enclosure) == RES_OK);
diff --git a/src/test_senc2d_scene.c b/src/test_senc2d_scene.c
@@ -27,7 +27,7 @@ main(int argc, char** argv)
struct senc2d_scene* scn = NULL;
struct senc2d_descriptor* desc = NULL;
struct context ctx;
- unsigned count, i;
+ unsigned count, i, maxm;
(void)argc, (void)argv;
CHK(mem_init_proxy_allocator(&allocator, &mem_default_allocator) == RES_OK);
@@ -129,11 +129,24 @@ main(int argc, char** argv)
CHK(senc2d_scene_create(dev, &scn) == RES_OK);
CHK(senc2d_scene_add_geometry(scn, nsegments, get_indices, get_media,
get_global_id, nvertices, get_position, &ctx) == RES_OK);
- /* Medium mismatch between neighbour segments */
- CHK(senc2d_scene_analyze(scn, &desc) == RES_BAD_ARG);
- ctx.front_media = medium0;
+ /* Medium mismatch between neighbour segments, but OK */
+ CHK(senc2d_scene_analyze(scn, &desc) == RES_OK);
+
+ CHK(senc2d_descriptor_get_max_medium(desc, &maxm) == RES_OK);
+ CHK(maxm == 3);
+ CHK(senc2d_descriptor_get_enclosure_count_by_medium(desc, 0, &count) == RES_OK);
+ CHK(count == 0); /* Medium 0 unused */
+ CHK(senc2d_descriptor_get_enclosure_count_by_medium(desc, 1, &count) == RES_OK);
+ CHK(count == 2); /* Medium 1 used twice */
+ CHK(senc2d_descriptor_get_enclosure_count_by_medium(desc, 2, &count) == RES_OK);
+ CHK(count == 0); /* Medium 2 unused */
+ CHK(senc2d_descriptor_get_enclosure_count_by_medium(desc, 3, &count) == RES_OK);
+ CHK(count == 1); /* Medium 3 used */
+ check_desc(desc);
+ ctx.front_media = medium0;
CHK(senc2d_scene_ref_put(scn) == RES_OK);
+ CHK(senc2d_descriptor_ref_put(desc) == RES_OK);
CHK(senc2d_scene_create(dev, &scn) == RES_OK);
CHK(senc2d_scene_add_geometry(scn, nsegments, get_indices, get_media, NULL,
nvertices, get_position, &ctx) == RES_OK);
diff --git a/src/test_senc2d_square_behind_square.c b/src/test_senc2d_square_behind_square.c
@@ -18,30 +18,6 @@
#include <rsys/double2.h>
-void check_desc(struct senc2d_descriptor* desc) {
- unsigned mcount, ecount, i;
- CHK(senc2d_descriptor_get_max_medium(desc, &mcount) == RES_OK);
- CHK(mcount == 2);
- CHK(senc2d_descriptor_get_enclosure_count(desc, &ecount) == RES_OK);
- FOR_EACH(i, 0, mcount) {
- unsigned j, ecount_bym;
- unsigned found = 0;
- senc2d_descriptor_get_enclosure_count_by_medium(desc, i, &ecount_bym);
- FOR_EACH(j, 0, ecount_bym) {
- struct senc2d_enclosure* enc;
- struct senc2d_enclosure_header h;
- CHK(senc2d_descriptor_get_enclosure_by_medium(desc, i, j, &enc) == RES_OK);
- CHK(senc2d_enclosure_get_header(enc, &h) == RES_OK);
- found += (h.enclosed_medium == i);
- CHK(senc2d_enclosure_ref_put(enc) == RES_OK);
- }
- ASSERT(found == ecount_bym); /* All the enclosures enclose medim i */
- ASSERT(ecount_bym);
- ecount -= ecount_bym;
- }
- ASSERT(ecount == 0);
-}
-
int
main(int argc, char** argv)
{
@@ -50,6 +26,7 @@ main(int argc, char** argv)
struct senc2d_device* dev = NULL;
struct senc2d_scene* scn = NULL;
struct context ctx;
+ unsigned i, ecount, maxm;
(void)argc, (void)argv;
CHK(mem_init_proxy_allocator(&allocator, &mem_default_allocator) == RES_OK);
@@ -83,13 +60,26 @@ main(int argc, char** argv)
CHK(senc2d_scene_analyze(scn, &desc) == RES_OK);
+ CHK(senc2d_descriptor_get_enclosure_count(desc, &ecount) == RES_OK);
+ CHK(ecount == 3);
+
+ FOR_EACH(i, 0, ecount) {
+ struct senc2d_enclosure* enclosure;
+ struct senc2d_enclosure_header header;
+ CHK(senc2d_descriptor_get_enclosure(desc, i, &enclosure) == RES_OK);
+ CHK(senc2d_enclosure_get_header(enclosure, &header) == RES_OK);
+ ASSERT(header.enclosed_media_count == 1);
+ CHK(senc2d_enclosure_ref_put(enclosure) == RES_OK);
+ }
+
+ CHK(senc2d_descriptor_get_max_medium(desc, &maxm) == RES_OK);
+ CHK(maxm == 1);
check_desc(desc);
/* Even further in +Y, even bigger */
d2(ctx.offset, -3, 30);
ctx.scale = 7;
- /* Front/back media have been exchanged: external enclosure shows 2 media
- * analyze will fail */
+ /* Front/back media have been exchanged: external enclosure shows 2 media */
ctx.front_media = medium1;
ctx.back_media = medium0;
@@ -99,7 +89,23 @@ main(int argc, char** argv)
if(desc) CHK(senc2d_descriptor_ref_put(desc) == RES_OK);
desc = NULL;
- CHK(senc2d_scene_analyze(scn, &desc) == RES_BAD_ARG);
+ CHK(senc2d_scene_analyze(scn, &desc) == RES_OK);
+
+ CHK(senc2d_descriptor_get_enclosure_count(desc, &ecount) == RES_OK);
+ CHK(ecount == 4);
+
+ FOR_EACH(i, 0, ecount) {
+ struct senc2d_enclosure* enclosure;
+ struct senc2d_enclosure_header header;
+ CHK(senc2d_descriptor_get_enclosure(desc, i, &enclosure) == RES_OK);
+ CHK(senc2d_enclosure_get_header(enclosure, &header) == RES_OK);
+ ASSERT(header.enclosed_media_count == (header.is_infinite ? 2u : 1u));
+ CHK(senc2d_enclosure_ref_put(enclosure) == RES_OK);
+ }
+
+ CHK(senc2d_descriptor_get_max_medium(desc, &maxm) == RES_OK);
+ CHK(maxm == 1);
+ check_desc(desc);
CHK(senc2d_scene_ref_put(scn) == RES_OK);
CHK(senc2d_device_ref_put(dev) == RES_OK);
diff --git a/src/test_senc2d_square_in_square.c b/src/test_senc2d_square_in_square.c
@@ -26,6 +26,7 @@ main(int argc, char** argv)
struct senc2d_device* dev = NULL;
struct senc2d_scene* scn = NULL;
struct context ctx;
+ unsigned i, ecount, maxm;
(void)argc, (void)argv;
CHK(mem_init_proxy_allocator(&allocator, &mem_default_allocator) == RES_OK);
@@ -62,14 +63,31 @@ main(int argc, char** argv)
CHK(senc2d_scene_analyze(scn, &desc) == RES_OK);
+ CHK(senc2d_descriptor_get_enclosure_count(desc, &ecount) == RES_OK);
+ CHK(ecount == 3);
+
+ FOR_EACH(i, 0, ecount) {
+ struct senc2d_enclosure* enclosure;
+ struct senc2d_enclosure_header header;
+ CHK(senc2d_descriptor_get_enclosure(desc, i, &enclosure) == RES_OK);
+ CHK(senc2d_enclosure_get_header(enclosure, &header) == RES_OK);
+ ASSERT(header.enclosed_media_count == 1);
+ CHK(senc2d_enclosure_ref_put(enclosure) == RES_OK);
+ }
+
+ CHK(senc2d_descriptor_get_max_medium(desc, &maxm) == RES_OK);
+ CHK(maxm == 1);
+ check_desc(desc);
+
d2(ctx.offset, -4, -4);
ctx.scale = 10;
ctx.reverse_vrtx = 1;
ctx.reverse_med = 1;
/* Biggest square exterior is medium 1 */
ctx.front_media = medium1;
- /* Biggest square interior is medium 0 */
- ctx.back_media = medium0; /* mismatch with square 2 */
+ /* Biggest square interior is medium 0
+ * interior/exterior media have been exchanged: external enclosure shows 2 media */
+ ctx.back_media = medium0;
/* Third square */
CHK(senc2d_scene_add_geometry(scn, nsegments, get_indices, get_media, NULL,
@@ -77,7 +95,14 @@ main(int argc, char** argv)
if(desc) CHK(senc2d_descriptor_ref_put(desc) == RES_OK);
desc = NULL;
- CHK(senc2d_scene_analyze(scn, &desc) == RES_BAD_ARG);
+ CHK(senc2d_scene_analyze(scn, &desc) == RES_OK);
+
+ CHK(senc2d_descriptor_get_enclosure_count(desc, &ecount) == RES_OK);
+ CHK(ecount == 4);
+
+ CHK(senc2d_descriptor_get_max_medium(desc, &maxm) == RES_OK);
+ CHK(maxm == 1);
+ check_desc(desc);
CHK(senc2d_scene_ref_put(scn) == RES_OK);
CHK(senc2d_device_ref_put(dev) == RES_OK);
diff --git a/src/test_senc2d_utils.h b/src/test_senc2d_utils.h
@@ -236,5 +236,43 @@ circle_release(struct context* ctx)
ctx->indices = NULL;
}
+
+/*******************************************************************************
+ * Check functions
+ ******************************************************************************/
+static INLINE void check_desc(struct senc2d_descriptor* desc)
+{
+ unsigned maxm, ecount, i;
+ size_t e_cpt = 0;
+ CHK(senc2d_descriptor_get_max_medium(desc, &maxm) == RES_OK);
+ CHK(senc2d_descriptor_get_enclosure_count(desc, &ecount) == RES_OK);
+ for(i = 0; i <= maxm; i++) {
+ unsigned j, ecount_bym;
+ unsigned found = 0;
+ CHK(senc2d_descriptor_get_enclosure_count_by_medium(desc, i, &ecount_bym) == RES_OK);
+ /* Can be 0 if media numbering is not compact */
+ FOR_EACH(j, 0, ecount_bym) {
+ struct senc2d_enclosure* enc;
+ struct senc2d_enclosure_header h;
+ unsigned k;
+ int f = 0;
+ CHK(senc2d_descriptor_get_enclosure_by_medium(desc, i, j, &enc) == RES_OK);
+ CHK(senc2d_enclosure_get_header(enc, &h) == RES_OK);
+ ASSERT(h.enclosed_media_count);
+ FOR_EACH(k, 0, h.enclosed_media_count) {
+ unsigned m;
+ CHK(senc2d_enclosure_get_medium(enc, k, &m) == RES_OK);
+ found += (m == i);
+ f += (m == i);
+ }
+ ASSERT(f == 1); /* Single reference expected */
+ CHK(senc2d_enclosure_ref_put(enc) == RES_OK);
+ }
+ ASSERT(found == ecount_bym); /* All the enclosures enclose medim i */
+ e_cpt += ecount_bym;
+ }
+ ASSERT(e_cpt >= ecount); /* Every enc has been visited at least once */
+}
+
#endif /* TEST_UTILS2_H */
