commit 3f864fc7d4d70c571c9474f26bb559ede06b024a
parent 5afa312ad2caffe9cbae56084694848da46223a5
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Tue, 6 Mar 2018 16:10:17 +0100
Remove bit arrays storing side membership information.
Both for components and enclosures.
Diffstat:
3 files changed, 220 insertions(+), 250 deletions(-)
diff --git a/src/senc_enclosure_data.h b/src/senc_enclosure_data.h
@@ -18,7 +18,6 @@
#include <rsys/rsys.h>
#include <rsys/ref_count.h>
-#include <rsys/dynamic_array_uchar.h>
#include "senc.h"
#include "senc_scene_c.h"
@@ -44,12 +43,14 @@ struct enclosure_data {
struct darray_triangle_in sides;
/* Index of vertices in scene's unique vertices */
struct darray_vrtx_id vertices;
- /* TODO: use only 1 bit per side (now 1 char per triangle) */
- struct darray_uchar side_membership;
/* Number of components involved in this enclosure */
component_id_t cc_count;
/* Linked list of the components */
component_id_t first_component;
+ /* Range of triangles member of the enclosure */
+ struct side_range side_range;
+ /* Counts */
+ side_id_t side_count;
};
static FINLINE void
@@ -58,9 +59,11 @@ enclosure_data_init(struct mem_allocator* alloc, struct enclosure_data* enc) {
init_header(&enc->header);
enc->cc_count = 0;
enc->first_component = COMPONENT_NULL__;
+ enc->side_range.first = SIDE_NULL__;
+ enc->side_range.last = 0;
+ enc->side_count = 0;
darray_triangle_in_init(alloc, &enc->sides);
darray_vrtx_id_init(alloc, &enc->vertices);
- darray_uchar_init(alloc, &enc->side_membership);
}
static FINLINE res_T
@@ -73,9 +76,10 @@ enclosure_data_copy
dst->header = src->header;
dst->cc_count = src->cc_count;
dst->first_component = src->first_component;
+ dst->side_range = src->side_range;
+ dst->side_count = src->side_count;
OK(darray_triangle_in_copy(&dst->sides, &src->sides));
OK(darray_vrtx_id_copy(&dst->vertices, &src->vertices));
- OK(darray_uchar_copy(&dst->side_membership, &src->side_membership));
error:
return res;
}
@@ -85,7 +89,6 @@ enclosure_data_release(struct enclosure_data* n) {
ASSERT(n);
darray_triangle_in_release(&n->sides);
darray_vrtx_id_release(&n->vertices);
- darray_uchar_release(&n->side_membership);
}
static FINLINE res_T
@@ -98,9 +101,10 @@ enclosure_data_copy_and_release
dst->header = src->header;
dst->cc_count = src->cc_count;
dst->first_component = src->first_component;
+ dst->side_range = src->side_range;
+ dst->side_count = src->side_count;
OK(darray_triangle_in_copy_and_release(&dst->sides, &src->sides));
OK(darray_vrtx_id_copy_and_release(&dst->vertices, &src->vertices));
- OK(darray_uchar_copy(&dst->side_membership, &src->side_membership));
error:
return res;
}
diff --git a/src/senc_scene_analyze.c b/src/senc_scene_analyze.c
@@ -36,7 +36,7 @@
#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__, 0}, { NULL, 0, 0, NULL }\
+ { TRG_NULL__, 0}\
}
const struct cc_descriptor CC_DESCRIPTOR_NULL = CC_DESCRIPTOR_NULL__;
@@ -81,92 +81,9 @@ neighbour_cmp(const void* w1, const void* w2)
return (a1 > a2) - (a1 < a2);
}
-static void
-find_component_Zmax
- (struct senc_scene* scn,
- struct darray_triangle_tmp* triangles_tmp_array,
- struct cc_descriptor* cc)
-{
- trg_id_t trid;
- double edge0[3], edge1[3], normal[3], norm, side_nz;
- struct triangle_in* triangles_in;
- struct triangle_tmp* triangles_tmp;
- const union double3* vertices;
- const unsigned char* side_membership;
- ASSERT(scn && triangles_tmp_array && cc);
-
- vertices = darray_position_cdata_get(&scn->vertices);
- triangles_in = darray_triangle_in_data_get(&scn->triangles_in);
- triangles_tmp = darray_triangle_tmp_data_get(triangles_tmp_array);
- side_membership = darray_uchar_cdata_get(&cc->side_membership);
-
- /* Build the sorted list of side ids */
- ASSERT(darray_triangle_tmp_size_get(triangles_tmp_array)
- == darray_triangle_in_size_get(&scn->triangles_in));
- ASSERT(scn->nutris
- == darray_triangle_in_size_get(&scn->triangles_in));
- FOR_EACH(trid, 0, scn->nutris) {
- const unsigned char member = side_membership[trid];
- struct triangle_in* const trg_in = triangles_in + trid;
- struct triangle_tmp* const trg_tmp = triangles_tmp + trid;
- enum side_id side;
- int change = 0;
-
- if(!member) continue;
-
- /* Keep track of the appropriate vertex/side of the connex 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 Z coordinate.
- * If more than one vertex/side has the same Z, we want the side that most
- * faces Z (that is the one with the greater nz).
- * This is mandatory to select the correct side when both sides of a triangle
- * are candidate. */
- if(cc->max_vrtx[2] > trg_tmp->max_z)
- continue;
-
- d3_sub(edge0, vertices[trg_in->vertice_id[1]].vec,
- vertices[trg_in->vertice_id[0]].vec);
- d3_sub(edge1, vertices[trg_in->vertice_id[2]].vec,
- vertices[trg_in->vertice_id[0]].vec);
- d3_cross(normal, edge0, edge1);
- norm = d3_normalize(normal, normal);
- ASSERT(norm); (void)norm;
-
- if((member & FLAG_FRONT) && (member & FLAG_BACK)) {
- /* Select the side with nz>0 */
- side_nz = fabs(normal[2]);
- side = (normal[2] > 0) ? SIDE_FRONT : SIDE_BACK;
- } else if(member & FLAG_FRONT) {
- side_nz = normal[2];
- side = SIDE_FRONT;
- } else {
- ASSERT(member & FLAG_BACK);
- side_nz = -normal[2];
- side = SIDE_BACK;
- }
-
- if(cc->max_vrtx[2] < trg_tmp->max_z) {
- change = 1; /* Try first to improve z */
- } else if(cc->max_z_nz <= 0 && fabs(cc->max_z_nz) < fabs(side_nz)) {
- change = 1; /* If nz <= 0, the more negative the better */
- } else if(cc->max_z_nz > 0 && cc->max_z_nz < side_nz) {
- change = 1; /* If nz > 0, the more positive the better */
- }
- if(change) {
- cc->max_z_nz = side_nz;
- cc->max_z_side_id = TRGIDxSIDE_2_TRGSIDE(trid, side);
- ASSERT(trg_tmp->max_z_vrtx_id < 3);
- ASSERT(trg_in->vertice_id[trg_tmp->max_z_vrtx_id] < scn->nverts);
- cc->max_z_vrtx_id = trg_in->vertice_id[trg_tmp->max_z_vrtx_id];
- ASSERT(trg_tmp->max_z == vertices[cc->max_z_vrtx_id].pos.z);
- d3_set(cc->max_vrtx, vertices[cc->max_z_vrtx_id].vec);
- }
- }
-}
-
static FINLINE void
add_side_to_stack
- (struct senc_scene* scn,
+ (const struct senc_scene* scn,
struct darray_side_id* stack,
struct trgside* trgsides,
const side_id_t side_id)
@@ -182,30 +99,30 @@ add_side_to_stack
static side_id_t
get_side_not_in_connex_component
- (struct senc_scene* scn,
- struct trgside* trgsides,
+ (const struct senc_scene* scn,
+ const struct trgside* trgsides,
side_id_t* first_side_not_in_component,
- medium_id_t medium)
+ const 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 < last_side
+ 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 == last_side) return SIDE_NULL__;
+ if(i > last_side) return SIDE_NULL__;
return i;
}
static FINLINE side_id_t
get_side_from_stack
- (struct trgside* trgsides,
+ (const struct trgside* trgsides,
struct darray_side_id* stack)
{
side_id_t id;
@@ -213,6 +130,7 @@ get_side_from_stack
(void)trgsides;
ASSERT(trgsides && stack);
sz = darray_side_id_size_get(stack);
+ ASSERT(sz);
id = darray_side_id_cdata_get(stack)[sz - 1];
ASSERT(trgsides[id].list_id == FLAG_WAITING_STACK);
darray_side_id_pop_back(stack);
@@ -224,17 +142,18 @@ extract_connex_components
(struct senc_descriptor* desc,
struct trgside* trgsides,
struct darray_ptr_component_descriptor* connex_components,
- struct darray_triangle_tmp* triangles_tmp_array,
+ const struct darray_triangle_tmp* triangles_tmp_array,
struct darray_triangle_comp* triangles_comp)
{
res_T res = RES_OK;
- struct senc_scene* scn;
+ const struct senc_scene* scn;
struct mem_allocator* alloc;
ATOMIC component_count = 0;
int stack_initialised = 0;
int mm;
#ifndef NDEBUG
trg_id_t t;
+ component_id_t c;
#endif
ASSERT(trgsides && desc && connex_components && triangles_tmp_array);
@@ -248,8 +167,8 @@ extract_connex_components
#ifndef NDEBUG
FOR_EACH(t, 0, scn->nutris) {
- struct triangle_in* trg_in =
- darray_triangle_in_data_get(&scn->triangles_in) + t;
+ const struct triangle_in* trg_in =
+ darray_triangle_in_cdata_get(&scn->triangles_in) + t;
const struct side_range* media_use
= darray_side_range_cdata_get(&scn->media_use);
FOR_EACH(mm, 0, 2) {
@@ -263,87 +182,152 @@ extract_connex_components
#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 cc_descriptor* cc;
struct darray_side_id stack;
/* Any not-already-used side is used as a starting point */
- side_id_t first_side_not_in_component
+ side_id_t first_side_not_in_component;
+ if(res != RES_OK) continue;
+ first_side_not_in_component
= darray_side_range_cdata_get(&scn->media_use)[m].first;
- if (first_side_not_in_component == SIDE_NULL__)
+ 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 */
+ for(;;) { /* Process all components 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;
+ stack_initialised = 0; /* TODO: don't recreate stack for same thread */
darray_side_id_release(&stack);
}
break;
}
ASSERT(trgsides[start_side_id].list_id == FLAG_LIST_SIDE_LIST);
+#ifndef NDEBUG
+ {
+ trg_id_t tid = TRGSIDE_2_TRG(start_side_id);
+ enum side_flag s = TRGSIDE_2_SIDE(start_side_id);
+ medium_id_t side_med = darray_triangle_in_data_get(&desc->scene->triangles_in)[tid].medium[s];
+ ASSERT(side_med == m);
+ }
+#endif
+
/* Create and init a new component */
- current_cc = MEM_ALLOC(alloc, sizeof(struct cc_descriptor));
- if(!current_cc) {
+ cc = MEM_ALLOC(alloc, sizeof(struct cc_descriptor));
+ if(!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));
+ cc_descriptor_init(alloc, cc);
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;
+ cc->cc_id = (component_id_t)(ATOMIC_INCR(&component_count) - 1);
+ cc->medium = m;
+ cc->side_range.first = start_side_id;
- for(;;) { /* Process all sides of this enclosure */
+ for(;;) { /* Process all sides of this component */
int i;
- /* Pop waiting stack to feed crt_side */
+ enum side_flag crt_side_flag = TRGSIDE_2_SIDE(crt_side_id);
struct trgside* crt_side = trgsides + crt_side_id;
const trg_id_t crt_trg_id = TRGSIDE_2_TRG(crt_side_id);
+ const struct triangle_in* trg_in =
+ darray_triangle_in_cdata_get(&scn->triangles_in) + crt_trg_id;
struct triangle_comp* trg_comp =
darray_triangle_comp_data_get(triangles_comp) + crt_trg_id;
+ const struct triangle_tmp* const trg_tmp =
+ darray_triangle_tmp_cdata_get(triangles_tmp_array) + crt_trg_id;
+ const union double3* vertices =
+ darray_position_cdata_get(&scn->vertices);
ASSERT(crt_trg_id < scn->nutris);
ASSERT(trgsides[crt_side_id].medium == m);
+ /* Record Zmax information
+ * Keep track of the appropriate vertex/side of the connex 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 Z
+ * coordinate.
+ * If more than one vertex/side has the same Z, we want the side that
+ * most faces Z (that is the one with the greater nz).
+ * This is mandatory to select the correct side when both sides of a
+ * triangle are candidate. */
+ if(cc->max_vrtx[2] <= trg_tmp->max_z) {
+ /* Can either improve z or nz */
+
+ if(cc->max_z_side_id == TRGSIDE_OPPOSITE(crt_side_id)) {
+ /* Both sides are in cc and the opposite side is currently selected
+ * Just keep the side with nz>0 */
+ if(cc->max_z_nz < 0) {
+ /* Change side! */
+ cc->max_z_nz = -cc->max_z_nz;
+ cc->max_z_side_id = crt_side_id;
+ }
+ } else {
+ double edge0[3], edge1[3], normal[3], norm, side_nz;
+ int process = 0;
+
+ d3_sub(edge0, vertices[trg_in->vertice_id[1]].vec,
+ vertices[trg_in->vertice_id[0]].vec);
+ d3_sub(edge1, vertices[trg_in->vertice_id[2]].vec,
+ vertices[trg_in->vertice_id[0]].vec);
+ d3_cross(normal, edge0, edge1);
+ norm = d3_normalize(normal, normal);
+ ASSERT(norm); (void) norm;
+
+ if(TRGSIDE_IS_FRONT(crt_side_id)) {
+ side_nz = normal[2];
+ process = 1;
+ } else {
+ side_nz = -normal[2];
+ process = 1;
+ }
+
+ if(process) {
+ int change = 0;
+ if(cc->max_vrtx[2] < trg_tmp->max_z) {
+ change = 1; /* Try first to improve z */
+ } else if (cc->max_z_nz <= 0 && fabs(cc->max_z_nz) < fabs(side_nz)) {
+ change = 1; /* If nz <= 0, the more negative the better */
+ } else if (cc->max_z_nz > 0 && cc->max_z_nz < side_nz) {
+ change = 1; /* If nz > 0, the more positive the better */
+ }
+
+ if(change) {
+ cc->max_z_nz = side_nz;
+ cc->max_z_side_id = crt_side_id;
+ ASSERT(trg_tmp->max_z_vrtx_id < 3);
+ ASSERT(trg_in->vertice_id[trg_tmp->max_z_vrtx_id] < scn->nverts);
+ cc->max_z_vrtx_id = trg_in->vertice_id[trg_tmp->max_z_vrtx_id];
+ ASSERT(trg_tmp->max_z == vertices[cc->max_z_vrtx_id].pos.z);
+ d3_set(cc->max_vrtx, vertices[cc->max_z_vrtx_id].vec);
+ }
+ }
+ }
+ }
+
/* Record crt_side both as component and triangle level */
- current_cc->side_count++;
+ 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;
- }
+ ASSERT(trg_comp->component[crt_side_flag] == COMPONENT_NULL__);
+ trg_comp->component[crt_side_flag] = cc->cc_id;
#ifndef NDEBUG
- crt_side->member_of_cc = current_cc->cc_id;
+ crt_side->member_of_cc = 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;
+ const struct trgside* neighbour = trgsides + neighbour_id;
+ CHK(m == crt_side->medium);
if(neighbour->medium != crt_side->medium) {
/* Found medium discontinuity! Model topology is broken. */
const struct triangle_in* triangles_in
@@ -377,7 +361,7 @@ extract_connex_components
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 == cc->cc_id);
#endif
continue;
}
@@ -392,22 +376,25 @@ extract_connex_components
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;
+ cc->side_range.last = last_side_id;
/* Need to synchronize connex_components growth as this global structure
- * is accessed bay multipe threads */
+ * is accessed by 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(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(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);
+ ASSERT(components[cc->cc_id] == NULL);
+ components[cc->cc_id] = cc;
+ }
}
}
error:
@@ -424,6 +411,12 @@ extract_connex_components
ASSERT(trg_comp->component[SIDE_FRONT] != COMPONENT_NULL__);
ASSERT(trg_comp->component[SIDE_BACK] != COMPONENT_NULL__);
}
+ FOR_EACH(c, 0, component_count) {
+ struct cc_descriptor** components =
+ darray_ptr_component_descriptor_data_get(connex_components);
+ ASSERT(components[c] != NULL &&
+ components[c]->cc_id == c);
+ }
#endif
exit:
@@ -588,7 +581,7 @@ group_connex_components
= darray_position_cdata_get(&desc->scene->vertices);
log_err(desc->scene->dev,
"Medium mismatch found between triangle %lu %s side and triangle"
- " %lu %s side, both facing infinite.\n",
+ " %lu %s side, both facing infinity.\n",
(unsigned long)triangles_in[t1].global_id,
TRGSIDE_IS_FRONT(infinite_medium_first_side) ? "front" : "back",
(unsigned long)triangles_in[t2].global_id,
@@ -634,14 +627,12 @@ group_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);
}
#endif
if(hit_trg_in->medium[hit_side] != cc->medium) {
/* Medium mismatch! Model topology is broken. */
const trg_id_t t1 = TRGSIDE_2_TRG(hit_side_id);
- const trg_id_t t2 = TRGSIDE_2_TRG(hit_side);
+ const trg_id_t t2 = TRGSIDE_2_TRG(cc->max_z_side_id);
const struct triangle_in* triangles_in
= darray_triangle_in_cdata_get(&desc->scene->triangles_in);
const union double3* positions
@@ -668,6 +659,7 @@ group_connex_components
log_err(desc->scene->dev, "Media: %lu VS %lu\n",
(unsigned long)hit_trg_in->medium[hit_side],
(unsigned long)cc->medium);
+
res = RES_BAD_ARG;
goto error;
}
@@ -695,8 +687,13 @@ group_connex_components
++enclosures[cc->enclosure_id].cc_count;
/* Linked list of componnents */
fst = enclosures[cc->enclosure_id].first_component;
- cc->next_component = fst;
+ cc->enclosure_next_component = fst;
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;
}
exit:
@@ -928,43 +925,58 @@ error:
static res_T
build_result
(struct senc_descriptor* desc,
- struct darray_ptr_component_descriptor* connex_components)
+ const struct darray_ptr_component_descriptor* connex_components,
+ const struct darray_triangle_comp* triangles_comp_array)
{
res_T res = RES_OK;
struct mem_allocator* alloc;
- struct cc_descriptor** cc_descriptors;
+ const struct cc_descriptor* const* cc_descriptors;
struct enclosure_data* enclosures;
const struct triangle_in* triangles_in;
struct triangle_enc* triangles_enc;
+ const struct triangle_comp* triangles_comp;
+ int tt;
int ee;
- ASSERT(desc && connex_components);
+ ASSERT(desc && connex_components && triangles_comp_array);
alloc = descriptor_get_allocator(desc);
ASSERT(darray_ptr_component_descriptor_size_get(connex_components) < COMPONENT_MAX__);
- cc_descriptors = darray_ptr_component_descriptor_data_get(connex_components);
+ cc_descriptors = darray_ptr_component_descriptor_cdata_get(connex_components);
enclosures = darray_enclosure_data_get(&desc->enclosures);
triangles_in = darray_triangle_in_cdata_get(&desc->scene->triangles_in);
+ triangles_comp = darray_triangle_comp_cdata_get(triangles_comp_array);
OK2(darray_triangle_enc_resize(&desc->triangles_enc, desc->scene->nutris),
error_);
triangles_enc = darray_triangle_enc_data_get(&desc->triangles_enc);
+ /* Build global enclosure information */
+ #pragma omp parallel for
+ for(tt = 0; tt < (int)desc->scene->nutris; tt++) {
+ trg_id_t t = (trg_id_t)tt;
+ const component_id_t cf_id = triangles_comp[t].component[SIDE_FRONT];
+ const component_id_t cb_id = triangles_comp[t].component[SIDE_BACK];
+ const struct cc_descriptor* cf = cc_descriptors[cf_id];
+ const struct cc_descriptor* cb = cc_descriptors[cb_id];
+ const enclosure_id_t ef_id = cf->enclosure_id;
+ const enclosure_id_t eb_id = cb->enclosure_id;
+ ASSERT(triangles_enc[t].enclosure[SIDE_FRONT] == ENCLOSURE_NULL__);
+ triangles_enc[t].enclosure[SIDE_FRONT] = ef_id;
+ ASSERT(triangles_enc[t].enclosure[SIDE_BACK] == ENCLOSURE_NULL__);
+ triangles_enc[t].enclosure[SIDE_BACK] = eb_id;
+ }
+
/* 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 htable_vrtx_id vtable;
- const unsigned char* enc_memb;
- uint64_t* enc_memb64;
- trg_id_t fst_ixd = 0;
- trg_id_t sgd_ixd;
+ const struct cc_descriptor* current = cc_descriptors[enc->first_component];
+ struct htable_vrtx_id vtable; /* TODO: don't recreate vtable for same thread */
+ trg_id_t fst_idx = 0;
+ trg_id_t sgd_idx = enc->side_count;;
trg_id_t t;
- 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__);
@@ -978,76 +990,29 @@ build_result
enc->header.enclosed_medium
= (unsigned)current->medium; /* Back to API type */
ASSERT(enc->header.enclosed_medium < desc->scene->nmeds);
- /* 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);
- enc_memb64 = (uint64_t*)enc_memb;
- /* Check we can use uint64_t to merge bit vectors */
- ASSERT(darray_uchar_capacity(&enc->side_membership)
- % sizeof(*enc_memb64) == 0);
- ASSERT(darray_uchar_size_get(&enc->side_membership)
- == desc->scene->nutris);
- /* Merge enclosures' membership information */
- for(;;) {
- uint64_t* cc_memb64;
- trg_id_t t64, tmin64, tmax64;
- size_t tmin, tmax;
- ASSERT(enc->header.enclosed_medium == (unsigned)current->medium);
- side_count += current->side_count;
- first_member_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;
- 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);
- /* 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;
- /* 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);
- }
- /* Translate membership into side and vertex lists. */
- OK(darray_triangle_in_resize(&enc->sides, side_count));
- OK(darray_vrtx_id_reserve(&enc->vertices, side_count / 2));
+ /* Build side and vertex lists. */
+ OK(darray_triangle_in_resize(&enc->sides, enc->side_count));
+ /* Size is just a int */
+ OK(darray_vrtx_id_reserve(&enc->vertices,
+ enc->side_count / 2 + enc->side_count / 8));
/* New vertex numbering scheme local to the enclosure */
htable_vrtx_id_init(alloc, &vtable);
ASSERT(desc->scene->nutris
== darray_triangle_in_size_get(&desc->scene->triangles_in));
- fst_ixd = 0;
- sgd_ixd = side_count;
/* Put at the end the back-faces of triangles that also have their
* front-face in the list. */
- for(t = TRGSIDE_2_TRG(first_member_side);
- t <= TRGSIDE_2_TRG(last_member_side);
+ for(t = TRGSIDE_2_TRG(enc->side_range.first);
+ t <= TRGSIDE_2_TRG(enc->side_range.last);
t++)
{
const struct triangle_in* trg_in = triangles_in + t;
struct triangle_in* trg;
unsigned vertice_id[3];
int i;
- if(!enc_memb[t]) continue;
+ if(triangles_enc[t].enclosure[SIDE_FRONT] != e
+ && triangles_enc[t].enclosure[SIDE_BACK] != e)
+ continue;
++enc->header.unique_triangle_count;
FOR_EACH(i, 0, 3) {
@@ -1066,31 +1031,27 @@ build_result
++enc->header.vertices_count;
}
}
- ASSERT((enc_memb[t] & FLAG_FRONT) || (enc_memb[t] & FLAG_BACK));
- if(enc_memb[t] & FLAG_FRONT) {
+ ASSERT(triangles_enc[t].enclosure[SIDE_FRONT] == e
+ || triangles_enc[t].enclosure[SIDE_BACK] == e);
+ if(triangles_enc[t].enclosure[SIDE_FRONT] == e) {
++enc->header.triangle_count;
- trg = darray_triangle_in_data_get(&enc->sides) + fst_ixd++;
+ trg = darray_triangle_in_data_get(&enc->sides) + fst_idx++;
FOR_EACH(i, 0, 2) trg->medium[i] = trg_in->medium[i];
trg->global_id = trg_in->global_id;
FOR_EACH(i, 0, 3) trg->vertice_id[i] = vertice_id[i];
- ASSERT(triangles_enc[t].enclosure[SIDE_FRONT] == ENCLOSURE_NULL__);
- triangles_enc[t].enclosure[SIDE_FRONT] = e;
}
- if(enc_memb[t] & FLAG_BACK) {
+ if(triangles_enc[t].enclosure[SIDE_BACK] == e) {
++enc->header.triangle_count;
trg = darray_triangle_in_data_get(&enc->sides) +
- ((enc_memb[t] & FLAG_FRONT) ? --sgd_ixd : fst_ixd++);
+ ((triangles_enc[t].enclosure[SIDE_FRONT] == e) ? --sgd_idx : fst_idx++);
FOR_EACH(i, 0, 2) trg->medium[i] = trg_in->medium[1 - i];
trg->global_id = trg_in->global_id;
FOR_EACH(i, 0, 3) trg->vertice_id[i] = vertice_id[2 - i];
- ASSERT(triangles_enc[t].enclosure[SIDE_BACK] == ENCLOSURE_NULL__);
- triangles_enc[t].enclosure[SIDE_BACK] = e;
}
- if(fst_ixd == sgd_ixd) break;
+ if(fst_idx == sgd_idx) break;
}
- darray_uchar_purge(&enc->side_membership);
htable_vrtx_id_release(&vtable);
error:
/* Cannot exit openmp block */
@@ -1185,16 +1146,16 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
goto error;
}
- darray_triangle_comp_release(&triangles_comp);
- triangles_comp_initialized = 0;
-
/* Build result. */
- res = build_result(desc, &connex_components);
+ res = build_result(desc, &connex_components, &triangles_comp);
if(res != RES_OK) {
log_err(scn->dev, "%s: could not build result.\n", FUNC_NAME);
goto error;
}
+ darray_triangle_comp_release(&triangles_comp);
+ triangles_comp_initialized = 0;
+
exit:
if(connex_components_initialized) {
size_t c, cc_count =
diff --git a/src/senc_scene_analyze_c.h b/src/senc_scene_analyze_c.h
@@ -120,33 +120,38 @@ struct cc_descriptor {
component_id_t cc_group_root;
enclosure_id_t enclosure_id;
/* 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) */
- struct side_range in_use_membership_range;
- struct darray_uchar side_membership;
+ component_id_t enclosure_next_component;
+ /* Range of sides member of this component */
+ struct side_range side_range;
};
extern const struct cc_descriptor CC_DESCRIPTOR_NULL;
static FINLINE void
-cc_descriptor_init(struct mem_allocator* alloc, struct cc_descriptor* data)
+cc_descriptor_init
+ (struct mem_allocator* alloc,
+ struct cc_descriptor* data)
{
ASSERT(data);
+ (void)alloc;
*data = CC_DESCRIPTOR_NULL;
- darray_uchar_init(alloc, &data->side_membership);
}
static FINLINE void
-ptr_component_descriptor_init(struct mem_allocator* alloc, struct cc_descriptor** data) {
- (void) alloc;
+ptr_component_descriptor_init
+ (struct mem_allocator* alloc,
+ struct cc_descriptor** data)
+{
+ (void)alloc;
ASSERT(data);
*data = NULL;
}
static FINLINE void
-ptr_component_descriptor_release(struct mem_allocator* allocator, struct cc_descriptor** data)
+ptr_component_descriptor_release
+ (struct mem_allocator* allocator,
+ struct cc_descriptor** data)
{
ASSERT(allocator && data);
- darray_uchar_release(&(*data)->side_membership);
MEM_RM(allocator, *data);
}
