commit d136a2d670bb6d843773af6a665ead9cf2a8f54e
parent c0e36df38179eae9dedecfa1272e5b7225c528eb
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Fri, 3 Jul 2020 17:49:02 +0200
Add area and volume to enclosure headers
Diffstat:
6 files changed, 109 insertions(+), 62 deletions(-)
diff --git a/src/senc2d.h b/src/senc2d.h
@@ -76,9 +76,9 @@ enum senc2d_side {
struct senc2d_enclosure_header {
/* The ID of the enclosure; 0, 1, ... */
unsigned enclosure_id;
- /* Number of segments; a segment can be accounted for twice, once by side */
+ /* Number of segments; a segment can be counted twice, once by side */
unsigned primitives_count;
- /* Number of segments; a segment cannot be accounted for twice */
+ /* Number of segments; a segment cannot be counted twice */
unsigned unique_primitives_count;
/* Number of vertices */
unsigned vertices_count;
@@ -88,6 +88,16 @@ struct senc2d_enclosure_header {
/* Is the enclosure open/infinite?
* Only the outermost enclosure is infinite. */
int is_infinite;
+ /* The volume of the enclosure, in m^2 (2D volume is in m^2!).
+ * For the outermost enclosure, that goes to infinity, the volume is negative
+ * and is the volume substracted from an hypothetical surrounding object.
+ * If the two sides of a segment are part of the enclosure, the segment is
+ * counted as 0. */
+ double volume;
+ /* The area of the enclosure, in m (2D area is in m!).
+ * If the two sides of a segment are part of the enclosure, the segment is
+ * counted twice. */
+ double area;
};
/* We consider the geometrical normal Ng to a segment V0 V1 that verifies
diff --git a/src/senc2d_enclosure_data.h b/src/senc2d_enclosure_data.h
@@ -67,7 +67,9 @@ init_header(struct senc2d_enclosure_header* header)
header->unique_primitives_count = 0;
header->vertices_count = 0;
header->enclosed_media_count = 0;
- header->is_infinite = CHAR_MAX;
+ header->is_infinite = INT_MAX;
+ header->volume = 0;
+ header->area = 0;
}
#define DARRAY_NAME media
diff --git a/src/senc2d_scene_analyze.c b/src/senc2d_scene_analyze.c
@@ -36,7 +36,7 @@
#include <stdlib.h>
#define CC_DESCRIPTOR_NULL__ {\
- CHAR_MAX, VRTX_NULL__, 0,\
+ 0, 0, INT_MAX, VRTX_NULL__, 0,\
CC_ID_NONE, CC_GROUP_ROOT_NONE, ENCLOSURE_NULL__,\
{ SEG_NULL__, 0},\
NULL\
@@ -149,7 +149,6 @@ extract_connex_components
struct mem_allocator* alloc;
int64_t m_idx; /* OpenMP requires a signed type for the for loop variable */
struct darray_side_id stack;
- 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;
@@ -168,7 +167,6 @@ extract_connex_components
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->nsegs, sizeof(uchar));
if(!processed) {
@@ -265,24 +263,22 @@ extract_connex_components
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;
uchar* seg_used = processed + crt_seg_id;
const struct segment_tmp* const seg_tmp = segments_tmp + crt_seg_id;
ASSERT(crt_seg_id < scn->nsegs);
if(*p_res != RES_OK) break;
- /* Record Ymax information
+ /* Record max_y 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) {
+ const struct segment_in* seg_in =
+ darray_segment_in_cdata_get(&scn->segments_in) + crt_seg_id;
/* 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 */
FOR_EACH(i, 0, 2) {
@@ -292,19 +288,6 @@ extract_connex_components
}
}
ASSERT(i < 2); /* Found one */
- /* List of sides using the vertex */
- 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(max_y_vrtx_id == seg_in->vertice_id[i]) {
- /* List of sides using the vertex */
- OK2(darray_side_id_push_back(&ids_of_sides_around_max_y_vertex,
- &crt_side_id));
- break;
- }
- }
}
/* Record crt_side both as component and segment level */
@@ -395,51 +378,84 @@ extract_connex_components
{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];
- seg_id_t segid = SEGSIDE_2_SEG(s);
- enum senc2d_side sid = SEGSIDE_2_SIDE(s);
- component_id_t* cmp = segments_comp[segid].component;
- ASSERT(cmp[sid] == COMPONENT_NULL__);
- ASSERT(medium_id_2_medium_idx(segsides[s].medium)
+ const side_id_t s_id = darray_side_id_cdata_get(¤t_component)[ii];
+ seg_id_t seg_id = SEGSIDE_2_SEG(s_id);
+ enum senc2d_side side = SEGSIDE_2_SIDE(s_id);
+ component_id_t* cmp = segments_comp[seg_id].component;
+ ASSERT(cmp[side] == COMPONENT_NULL__);
+ ASSERT(medium_id_2_medium_idx(segsides[s_id].medium)
>= medium_id_2_medium_idx(medium));
- cmp[sid] = cc->cc_id;
+ cmp[side] = cc->cc_id;
}
- /* Determine if this component can be an inner part inside another
- * component (substracting a volume) as only these components will need
- * to search for their possible outer component when grouping
- * components to create enclosures */
+ /* Compute component area and volume, and record information on the
+ * max_y side of the component to help find out if the component is
+ * inner or outer */
max_ny = 0;
max_ny_side_id = SIDE_NULL__;
- sz = darray_side_id_size_get(&ids_of_sides_around_max_y_vertex);
- ASSERT(sz > 0);
FOR_EACH(ii, 0, sz) {
- const side_id_t side_id =
- darray_side_id_cdata_get(&ids_of_sides_around_max_y_vertex)[ii];
- const seg_id_t seg_id = SEGSIDE_2_SEG(side_id);
- enum senc2d_side s = SEGSIDE_2_SIDE(side_id);
+ const side_id_t s_id = darray_side_id_cdata_get(¤t_component)[ii];
+ const seg_id_t seg_id = SEGSIDE_2_SEG(s_id);
+ enum senc2d_side side = SEGSIDE_2_SIDE(s_id);
+ const struct segment_comp* seg_comp = segments_comp + seg_id;
+ const struct segment_tmp* const seg_tmp = segments_tmp + seg_id;
const struct segment_in* seg_in =
darray_segment_in_cdata_get(&scn->segments_in) + seg_id;
- const 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;
+ const double* v0 = vertices[seg_in->vertice_id[0]].vec;
+ const double* v1 = vertices[seg_in->vertice_id[1]].vec;
+ int is_2sided = (seg_comp->component[SENC2D_FRONT]
+ == seg_comp->component[SENC2D_BACK]);
- ASSERT(seg_comp->component[s] == cc->cc_id); (void)s;
- d2_sub(edge, vertices[seg_in->vertice_id[1]].vec,
- vertices[seg_in->vertice_id[0]].vec);
+ /* Compute component area and volume */
+ d2_sub(edge, v1, v0);
d2(normal, -edge[1], +edge[0]);
norm = d2_normalize(normal, normal);
- ASSERT(norm); (void)norm;
+ ASSERT(norm);
+ /* The area is a n dim concept, that in 2D is in m
+ * Here the area contribution of the segment is its length */
+ cc->area += norm;
+
+ if(!is_2sided) {
+ /* Build a triangle whose base is the segment and whose apex is
+ * the coordinate system's origin. If the 2 sides of the segment
+ * are part of the component, the contribution of the segment
+ * must be 0. To achieve this, we just skip both sides */
+ double _2t = d2_cross(v0, v1); /* 2 * area of the triangle */
+
+ /* The volume is a n dim concept, that in 2D is in m^2
+ * Here the volume contribution of the segment is the area of the
+ * triangle v0,v1,O */
+ if((seg_comp->component[SENC2D_FRONT] == cc->cc_id)
+ == (scn->convention & SENC2D_CONVENTION_NORMAL_FRONT))
+ cc->_2volume += _2t;
+ else
+ cc->_2volume -= _2t;
+ }
- if(fabs(max_ny) < fabs(normal[1])) {
- max_ny_side_id = side_id;
- max_ny = normal[1];
- max_y_is_2sided = (seg_comp->component[SENC2D_FRONT]
- == seg_comp->component[SENC2D_BACK]);
+ ASSERT(seg_comp->component[side] != COMPONENT_NULL__); (void)side;
+ if(seg_tmp->max_y == max_y) {
+ int i;
+ /* candidate to define the max_y normal */
+ FOR_EACH(i, 0, 2) {
+ if(cc->max_y_vrtx_id == seg_in->vertice_id[i]) {
+ if(fabs(normal[1]) > fabs(max_ny)) {
+ max_ny_side_id = s_id;
+ max_ny = normal[1];
+ max_y_is_2sided = is_2sided;
+ break;
+ }
+ }
+ }
}
}
- /* The inner/outer property comes from the normal orientation of the
+ /* Determine if this component can be an inner part inside another
+ * component (substracting a volume) as only these components will need
+ * to search for their possible outer component when grouping
+ * components to create enclosures.
+ * The inner/outer property comes from the normal orientation of the
* segment on top of the component, this segment being the one whose
* |Ny| is maximal. If this segment has its 2 sides in the component,
* the component is inner */
@@ -484,7 +500,6 @@ extract_connex_components
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
@@ -926,7 +941,7 @@ compare_enclosures
const struct enclosure_data* e1 = ptr1;
const struct enclosure_data* e2 = ptr2;
ASSERT(e1->side_range.first != e2->side_range.first);
- return (e1->side_range.first - e2->side_range.first);
+ return (int)e1->side_range.first - (int)e2->side_range.first;
}
static void
@@ -992,10 +1007,13 @@ build_result
enclosure_id_t rank = enclosures[e].header.enclosure_id;
ordered_ids[rank] = e;
}
- /* Rewrite cc_descriptors */
FOR_EACH(d, 0, cc_count) {
- cc_descriptors[d]->enclosure_id =
- ordered_ids[cc_descriptors[d]->enclosure_id];
+ enclosure_id_t new_id = ordered_ids[cc_descriptors[d]->enclosure_id];
+ /* Update the enclosure ID in cc_descriptor */
+ cc_descriptors[d]->enclosure_id = new_id;
+ /* Sum up areas and volumes of components int oenclosures */
+ enclosures[new_id].header.area += cc_descriptors[d]->area;
+ enclosures[new_id].header.volume += cc_descriptors[d]->_2volume / 2;
}
single_err: (void)0;
}/* Implicit barrier here. */
diff --git a/src/senc2d_scene_analyze_c.h b/src/senc2d_scene_analyze_c.h
@@ -43,8 +43,12 @@ init_segside(struct mem_allocator* alloc, struct segside* data)
* Also keeps the maximum z info of the component
* and the list of media found */
struct cc_descriptor {
+ /* The area of the component */
+ double area;
+ /* Twice the signed volume of the component */
+ double _2volume;
/* Does this component is an outer border of an enclosure or an inner one? */
- char is_outer_border;
+ int is_outer_border;
vrtx_id_t max_y_vrtx_id; /* id of the vrtx with max z value */
side_id_t side_count;
/* Used when grouping components to form enclosures */
diff --git a/src/test_senc2d_enclosure.c b/src/test_senc2d_enclosure.c
@@ -39,6 +39,7 @@ test(const int convention)
unsigned gid;
enum senc2d_side side;
double vrtx[2];
+ double ext_v = 0;
struct context ctx = CONTEXT_NULL__;
unsigned i, n, s, count;
int conv;
@@ -136,6 +137,8 @@ test(const int convention)
CHK(header.unique_primitives_count == nsegments);
CHK(header.vertices_count == nvertices);
CHK(header.is_infinite == (i == 0));
+ if(i == 0) ext_v = header.volume;
+ else CHK(header.volume == -ext_v);
FOR_EACH(s, 0, header.primitives_count) {
OK(senc2d_enclosure_get_segment_id(enclosure, s, &gid, &side));
@@ -203,6 +206,7 @@ test(const int convention)
CHK(header.unique_primitives_count == nsegments - 1);
CHK(header.vertices_count == nvertices);
CHK(header.is_infinite == 1);
+ CHK(header.volume == 0);
FOR_EACH(s, 0, header.primitives_count) {
OK(senc2d_enclosure_get_segment_id(enclosure, s, &gid, &side));
diff --git a/src/test_senc2d_inconsistant_square.c b/src/test_senc2d_inconsistant_square.c
@@ -25,7 +25,7 @@
* | | 0----X
* | |
* 0----1 */
-/* Segment #1 order is not consistant with other segments */
+/* Segment #0 order is not consistant with other segments */
static unsigned
inconsistant_box_indices[4/*#segments*/ * 2/*#indices per segment*/] = {
2, 0,
@@ -36,11 +36,18 @@ inconsistant_box_indices[4/*#segments*/ * 2/*#indices per segment*/] = {
static const unsigned inconsistant_box_nsegments
= sizeof(inconsistant_box_indices) / (2 * sizeof(*inconsistant_box_indices));
-/* Media definitions reflect segment #1 inconsistancy */
+/* Media definitions reflect segment #0 inconsistancy */
static const unsigned
inconsistant_medium_front[4] = { 1, 0, 0, 0 };
static const unsigned
inconsistant_medium_back[4] = { 0, 1, 1, 1 };
+static const double
+inconsistant_square_vertices[4/*#vertices*/ * 2/*#coords per vertex*/] = {
+ 10.0, 10.0,
+ 11.0, 10.0,
+ 10.0, 11.0,
+ 11.0, 11.0
+};
static void
test(const int convention)
@@ -63,7 +70,7 @@ test(const int convention)
* but opposite sides.
* What differs in this test is that segment #0 vertices are given
* in the opposite rotation order. */
- ctx.positions = box_vertices;
+ ctx.positions = inconsistant_square_vertices;
ctx.indices = inconsistant_box_indices;
ctx.front_media = inconsistant_medium_front;
ctx.back_media = inconsistant_medium_back;
@@ -88,6 +95,8 @@ test(const int convention)
OK(senc2d_scene_get_enclosure(scn, e, &enclosure));
OK(senc2d_enclosure_get_header(enclosure, &header));
CHK(header.enclosed_media_count == 1);
+ CHK(header.area == 4);
+ CHK(header.volume == (header.is_infinite ? -1 : 1));
OK(senc2d_enclosure_get_medium(enclosure, 0, &medium));
/* If NORMAL_FRONT the external enclosure's medium should be 0,
* 1 if NORMAL_BACK */
@@ -108,7 +117,7 @@ test(const int convention)
expected_side = (inconsistant_medium_front[i] == expected_medium)
? SENC2D_FRONT : SENC2D_BACK;
cmp_seg(i, enclosure,
- inconsistant_box_indices + (2 * i), box_vertices,
+ inconsistant_box_indices + (2 * i), inconsistant_square_vertices,
&same, &reversed);
/* Should be made of the same segments */
CHK(same);
