star-enclosures-3d

Extract enclosures from 3D geometry
git clone git://git.meso-star.fr/star-enclosures-3d.git
Log | Files | Refs | README | LICENSE

commit cca59400847b1a8edebba9191b7f20f47557a9d1
parent fd6b2fb9d87207c366816b143d2ded57b8560ef1
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date:   Wed, 21 Feb 2018 19:05:52 +0100

Remove useless intermediate data structures.

Diffstat:
Msrc/senc_scene_analyze.c | 354+++++++++++++++++++++++++++++--------------------------------------------------
Msrc/senc_scene_analyze_c.h | 2+-
2 files changed, 132 insertions(+), 224 deletions(-)

diff --git a/src/senc_scene_analyze.c b/src/senc_scene_analyze.c @@ -205,53 +205,20 @@ add_side_to_stack trgsides[side_id].list_id = FLAG_WAITING_STACK; } -static FINLINE void -add_side_to_medium_list - (struct senc_scene* scn, - struct darray_side_id* side_ids_by_medium, - struct trgside* trgsides, - const side_id_t side_id) -{ - (void)scn; - ASSERT(scn && side_ids_by_medium && trgsides - && side_id < 2 * scn->nutris); - if(trgsides[side_id].list_id == FLAG_LIST_BY_MEDIUM) { - ASSERT((darray_side_id_size_get(side_ids_by_medium) > 128) - || find_side_in_list(trgsides, side_ids_by_medium, side_id, - FLAG_LIST_BY_MEDIUM)); - return; - } - ASSERT((darray_side_id_size_get(side_ids_by_medium) > 128) - || !find_side_in_list(trgsides, side_ids_by_medium, side_id, - FLAG_LIST_BY_MEDIUM)); - darray_side_id_push_back(side_ids_by_medium, &side_id); - trgsides[side_id].list_id = FLAG_LIST_BY_MEDIUM; -} - static side_id_t -get_side_from_medium_list_not_in_connex_component +get_side_not_in_connex_component (struct senc_scene* scn, struct trgside* trgsides, - side_id_t* first_side_by_medium_not_in_component, - const struct darray_side_id* side_ids_by_medium) + side_id_t* first_side_not_in_component) { - side_id_t i, sz; - size_t tmp; - const side_id_t* ids; - (void)scn; - ASSERT(scn && trgsides && first_side_by_medium_not_in_component - && side_ids_by_medium); - tmp = darray_side_id_size_get(side_ids_by_medium); - ids = darray_side_id_cdata_get(side_ids_by_medium); - ASSERT(tmp <= SIDE_MAX__); - sz = (side_id_t)tmp; - i = *first_side_by_medium_not_in_component; - while(i < sz && trgsides[ids[i]].list_id != FLAG_LIST_BY_MEDIUM) ++i; - - *first_side_by_medium_not_in_component = i+1; - if(i == sz) return SIDE_NULL__; - ASSERT(trgsides[ids[i]].list_id == FLAG_LIST_BY_MEDIUM); - return ids[i]; + side_id_t i; + ASSERT(scn && trgsides && first_side_not_in_component); + i = *first_side_not_in_component; + while(i < 2 * scn->nutris && trgsides[i].list_id != FLAG_LIST_SIDE_LIST) ++i; + + *first_side_not_in_component = i+1; + if(i == 2 * scn->nutris) return SIDE_NULL__; + return i; } static FINLINE side_id_t @@ -276,8 +243,7 @@ extract_connex_components struct trgside* trgsides, struct darray_cc_descriptor* connex_components, struct darray_triangle_tmp* triangles_tmp_array, - struct darray_triangle_comp* triangles_comp, - struct darray_side_id* side_ids_by_medium) + struct darray_triangle_comp* triangles_comp) { res_T res = RES_OK; medium_id_t m; @@ -285,157 +251,131 @@ extract_connex_components struct senc_scene* scn; struct mem_allocator* alloc; struct darray_side_id stack; - /* Arrays of cc_descriptor ids, organized by medium. */ - struct darray_component_id* component_ids_by_medium = NULL; + /* Id of the first trgside not already in a connex component */ + side_id_t first_side_not_in_component = 0; + struct cc_descriptor current_cc; - ASSERT(trgsides && desc && connex_components && triangles_tmp_array - && side_ids_by_medium); + ASSERT(trgsides && desc && connex_components && triangles_tmp_array); alloc = descriptor_get_allocator(desc); scn = desc->scene; - /* Init data structures */ + /* Init stack */ darray_side_id_init(alloc, &stack); - component_ids_by_medium - = MEM_ALLOC(alloc, scn->nmeds * sizeof(struct darray_component_id)); - if(!component_ids_by_medium) { - res = RES_MEM_ERR; - goto error; - } - FOR_EACH(m, 0, scn->nmeds) { - struct darray_component_id* const cc = component_ids_by_medium + m; - darray_component_id_init(alloc, cc); - } - /* For each medium extract connex components */ - FOR_EACH(m, 0, scn->nmeds) { - struct darray_component_id* const cc_ids_by_medium - = component_ids_by_medium + m; - struct cc_descriptor current_cc; - /* Id of the first trgside not already in a connex component */ - side_id_t first_side_by_medium_not_in_component = 0; - /* Init current component */ - cc_descriptor_init(alloc, &current_cc); - + /* Extract connex components until every side is involved */ + cc_descriptor_init(alloc, &current_cc); + for(;;) { + /* Any not-already-used side is used as a starting point */ + const side_id_t start_side_id = get_side_not_in_connex_component(scn, + trgsides, &first_side_not_in_component); + side_id_t crt_side_id = start_side_id; + char* side_membership; + + ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nutris); + if(start_side_id == SIDE_NULL__) + break; /* start_side_id=SIDE_NULL__ => done! */ + ASSERT(trgsides[start_side_id].list_id == FLAG_LIST_SIDE_LIST); + + m = trgsides[start_side_id].medium; + + /* Reset CC data for a new CC */ + tmp = darray_cc_descriptor_size_get(connex_components); + ASSERT(tmp <= COMPONENT_MAX__); + cc_descriptor_clear(&current_cc); + /* 1 char per triangle (2 sides) */ + darray_char_resize(&current_cc.side_membership, scn->nutris); + side_membership = darray_char_data_get(&current_cc.side_membership); + memset(side_membership, 0, scn->nutris * sizeof(char)); + current_cc.cc_id = (component_id_t)tmp; + current_cc.medium = m; + for(;;) { - /* Any not-already-used side by medium is used as a starting point */ - const side_id_t start_side_id = - get_side_from_medium_list_not_in_connex_component(scn, trgsides, - &first_side_by_medium_not_in_component, side_ids_by_medium + m); - side_id_t crt_side_id = start_side_id; - char* side_membership; - - ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nutris); - if(start_side_id == SIDE_NULL__) - break; /* start_side_id=SIDE_NULL__ => medium done! */ - ASSERT(trgsides[start_side_id].list_id == FLAG_LIST_BY_MEDIUM); - - /* Reset CC data for a new CC */ - tmp = darray_cc_descriptor_size_get(connex_components); - ASSERT(tmp <= COMPONENT_MAX__); - cc_descriptor_clear(&current_cc); - /* 1 char per triangle (2 sides) */ - darray_char_resize(&current_cc.side_membership, scn->nutris); - side_membership = darray_char_data_get(&current_cc.side_membership); - memset(side_membership, 0, scn->nutris * sizeof(char)); - current_cc.cc_id = (component_id_t)tmp; - current_cc.medium = m; - - for(;;) { - int i; - /* Pop waiting stack to feed crt_side */ - struct trgside* crt_side = trgsides + crt_side_id; - const trg_id_t crt_trg_id = TRGSIDE_2_TRG(crt_side_id); - struct triangle_comp* trg_comp = - darray_triangle_comp_data_get(triangles_comp) + crt_trg_id; - ASSERT(crt_trg_id < scn->nutris); - ASSERT(trgsides[crt_side_id].medium == m); - - /* Record crt_side both as component and triangle level */ - current_cc.side_count++; - trgsides[crt_side_id].list_id = FLAG_LIST_COMPONENT; - if(TRGSIDE_IS_FRONT(crt_side_id)) { - ASSERT(trg_comp->component[SIDE_FRONT] == USHRT_MAX); - trg_comp->component[SIDE_FRONT] = current_cc.cc_id; - ASSERT(!(side_membership[crt_trg_id] & FLAG_FRONT)); - side_membership[crt_trg_id] |= FLAG_FRONT; - } else { - ASSERT(trg_comp->component[SIDE_BACK] == USHRT_MAX); - trg_comp->component[SIDE_BACK] = current_cc.cc_id; - ASSERT(!(side_membership[crt_trg_id] & FLAG_BACK)); - side_membership[crt_trg_id] |= FLAG_BACK; - } + int i; + /* Pop waiting stack to feed crt_side */ + struct trgside* crt_side = trgsides + crt_side_id; + const trg_id_t crt_trg_id = TRGSIDE_2_TRG(crt_side_id); + struct triangle_comp* trg_comp = + darray_triangle_comp_data_get(triangles_comp) + crt_trg_id; + ASSERT(crt_trg_id < scn->nutris); + ASSERT(trgsides[crt_side_id].medium == m); + + /* Record crt_side both as component and triangle level */ + current_cc.side_count++; + trgsides[crt_side_id].list_id = FLAG_LIST_COMPONENT; + if(TRGSIDE_IS_FRONT(crt_side_id)) { + ASSERT(trg_comp->component[SIDE_FRONT] == USHRT_MAX); + trg_comp->component[SIDE_FRONT] = current_cc.cc_id; + ASSERT(!(side_membership[crt_trg_id] & FLAG_FRONT)); + side_membership[crt_trg_id] |= FLAG_FRONT; + } else { + ASSERT(trg_comp->component[SIDE_BACK] == USHRT_MAX); + trg_comp->component[SIDE_BACK] = current_cc.cc_id; + ASSERT(!(side_membership[crt_trg_id] & FLAG_BACK)); + side_membership[crt_trg_id] |= FLAG_BACK; + } #ifndef NDEBUG - crt_side->member_of_cc = current_cc.cc_id; + crt_side->member_of_cc = current_cc.cc_id; #endif - /* Store neighbour sides in a waiting stack */ - FOR_EACH(i, 0, 3) { - side_id_t neighbour_id = crt_side->facing_side_id[i]; - trg_id_t nbour_trg_id = TRGSIDE_2_TRG(neighbour_id); - struct trgside* neighbour = trgsides + neighbour_id; - if(neighbour->medium != crt_side->medium) { - /* Found medium discontinuity! Model topology is broken. */ - const struct triangle_in* triangles_in - = darray_triangle_in_cdata_get(&scn->triangles_in); - const union double3* positions - = darray_position_cdata_get(&scn->vertices); - log_err(scn->dev, - "Medium mismatch found between neighbour triangles %lu %s" - " side and %u %s side.\n", - (unsigned long)triangles_in[crt_trg_id].global_id, - TRGSIDE_IS_FRONT(crt_side_id) ? "front": "back", - triangles_in[nbour_trg_id].global_id, - TRGSIDE_IS_FRONT(neighbour_id) ? "front" : "back"); - log_err(scn->dev, - "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n", - (unsigned long)triangles_in[crt_trg_id].global_id, - SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[0]].vec), - SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[1]].vec), - SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[2]].vec)); - log_err(scn->dev, - "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n", - (unsigned long)triangles_in[nbour_trg_id].global_id, - SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[0]].vec), - SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[1]].vec), - SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[2]].vec)); - log_err(desc->scene->dev, "Media: %lu VS %lu\n", - neighbour->medium, crt_side->medium); - res = RES_BAD_ARG; - cc_descriptor_release(&current_cc); - goto error; - } - if(neighbour->list_id == FLAG_LIST_COMPONENT) { - /* Already processed */ + /* Store neighbour sides in a waiting stack */ + FOR_EACH(i, 0, 3) { + side_id_t neighbour_id = crt_side->facing_side_id[i]; + trg_id_t nbour_trg_id = TRGSIDE_2_TRG(neighbour_id); + struct trgside* neighbour = trgsides + neighbour_id; + if(neighbour->medium != crt_side->medium) { + /* Found medium discontinuity! Model topology is broken. */ + const struct triangle_in* triangles_in + = darray_triangle_in_cdata_get(&scn->triangles_in); + const union double3* positions + = darray_position_cdata_get(&scn->vertices); + log_err(scn->dev, + "Medium mismatch found between neighbour triangles %lu %s" + " side and %u %s side.\n", + (unsigned long)triangles_in[crt_trg_id].global_id, + TRGSIDE_IS_FRONT(crt_side_id) ? "front" : "back", + triangles_in[nbour_trg_id].global_id, + TRGSIDE_IS_FRONT(neighbour_id) ? "front" : "back"); + log_err(scn->dev, + "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n", + (unsigned long)triangles_in[crt_trg_id].global_id, + SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[0]].vec), + SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[1]].vec), + SPLIT3(positions[triangles_in[crt_trg_id].vertice_id[2]].vec)); + log_err(scn->dev, + "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n", + (unsigned long)triangles_in[nbour_trg_id].global_id, + SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[0]].vec), + SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[1]].vec), + SPLIT3(positions[triangles_in[nbour_trg_id].vertice_id[2]].vec)); + log_err(desc->scene->dev, "Media: %lu VS %lu\n", + neighbour->medium, crt_side->medium); + res = RES_BAD_ARG; + cc_descriptor_release(&current_cc); + goto error; + } + if(neighbour->list_id == FLAG_LIST_COMPONENT) { + /* Already processed */ #ifndef NDEBUG - ASSERT(neighbour->member_of_cc == current_cc.cc_id); + ASSERT(neighbour->member_of_cc == current_cc.cc_id); #endif - continue; - } - if(neighbour->list_id == FLAG_WAITING_STACK) { - continue; /* Already processed */ - } - add_side_to_stack(scn, &stack, trgsides, neighbour_id); + continue; + } + if(neighbour->list_id == FLAG_WAITING_STACK) { + continue; /* Already processed */ } - if(darray_side_id_size_get(&stack) == 0) - break; /* Empty stack => connex component is done! */ - crt_side_id = get_side_from_stack(trgsides, &stack); + add_side_to_stack(scn, &stack, trgsides, neighbour_id); } - /* Keep track of this new connex component */ - darray_component_id_push_back(cc_ids_by_medium, &current_cc.cc_id); - find_component_Zmax(scn, triangles_tmp_array, &current_cc); - darray_cc_descriptor_push_back(connex_components, &current_cc); + if(darray_side_id_size_get(&stack) == 0) + break; /* Empty stack => connex component is done! */ + crt_side_id = get_side_from_stack(trgsides, &stack); } - cc_descriptor_release(&current_cc); + /* Keep track of this new connex component */ + find_component_Zmax(scn, triangles_tmp_array, &current_cc); + darray_cc_descriptor_push_back(connex_components, &current_cc); } + cc_descriptor_release(&current_cc); exit: - if(component_ids_by_medium) { - FOR_EACH(m, 0, scn->nmeds) { - struct darray_component_id* cc = component_ids_by_medium + m; - darray_component_id_release(cc); - } - MEM_RM(scn->dev->allocator, component_ids_by_medium); - } darray_side_id_release(&stack); ASSERT(desc->triangle_count == darray_triangle_comp_size_get(triangles_comp)); @@ -683,7 +623,6 @@ group_connex_components } /* Post-process links to group connex components */ - printf("\n"); FOR_EACH(c, 0, cc_count) { struct cc_descriptor* const cc = descriptors + c; const struct cc_descriptor* other_desc = cc; @@ -716,7 +655,7 @@ scan_edges struct darray_triangle_tmp* triangles_tmp_array) { trg_id_t t; - struct triangle_in *triangles_in; + const struct triangle_in *triangles_in; struct triangle_tmp *triangles_tmp; edge_id_t max_nbedges; /* Htable used to give an id to edges */ @@ -734,8 +673,9 @@ scan_edges OK(darray_triangle_tmp_resize(triangles_tmp_array, scn->nutris)); /* Loop on triangles to register edges. */ - triangles_in = darray_triangle_in_data_get(&scn->triangles_in); + triangles_in = darray_triangle_in_cdata_get(&scn->triangles_in); triangles_tmp = darray_triangle_tmp_data_get(triangles_tmp_array); + ASSERT(scn->nutris == darray_triangle_tmp_size_get(triangles_tmp_array)); FOR_EACH(t, 0, scn->nutris) { struct darray_neighbour* neighbour_list; struct neighbour_info neighbour; @@ -786,23 +726,21 @@ link_neighbours (struct senc_scene* scn, struct trgside* trgsides, struct darray_neighbourhood* neighbourhood_by_edge, - struct darray_triangle_tmp* triangles_tmp_array, - struct darray_side_id* side_ids_by_medium) + struct darray_triangle_tmp* triangles_tmp_array) { edge_id_t e, edge_count; - struct triangle_in *triangles_in; + const struct triangle_in *triangles_in; struct triangle_tmp *triangles_tmp; const union double3* vertices; size_t tmp; res_T res = RES_OK; - ASSERT(scn && neighbourhood_by_edge && triangles_tmp_array - && side_ids_by_medium); + ASSERT(scn && trgsides && neighbourhood_by_edge && triangles_tmp_array); /* Loop on edges. * For each edge sort triangle sides by rotation angle * and connect neighbours. */ - triangles_in = darray_triangle_in_data_get(&scn->triangles_in); + triangles_in = darray_triangle_in_cdata_get(&scn->triangles_in); triangles_tmp = darray_triangle_tmp_data_get(triangles_tmp_array); vertices = darray_position_cdata_get(&scn->vertices); tmp = darray_neighbourhood_size_get(neighbourhood_by_edge); @@ -838,7 +776,7 @@ link_neighbours FOR_EACH(i, 0, neighbour_count) { struct neighbour_info* neighbour_info = darray_neighbour_data_get(neighbour_list) + i; - struct triangle_in *trg_in = triangles_in + neighbour_info->trg_id; + const struct triangle_in *trg_in = triangles_in + neighbour_info->trg_id; struct triangle_tmp *neighbour = triangles_tmp + neighbour_info->trg_id; char actual_vid; v2 = trg_in->vertice_id[(neighbour_info->edge_rank + 2) % 3]; @@ -903,15 +841,13 @@ link_neighbours /* Link sides */ p_crt_side->facing_side_id[crt_edge] = ccw_side_idx; p_ccw_side->facing_side_id[ccw_edge] = crt_side_idx; - /* Record sides by medium */ + /* Record media */ p_crt_side->medium = triangles_in[crt_id].medium[crt_side]; p_ccw_side->medium = triangles_in[ccw_id].medium[ccw_side]; ASSERT(p_crt_side->medium < scn->nmeds); ASSERT(p_ccw_side->medium < scn->nmeds); - add_side_to_medium_list(scn, side_ids_by_medium + p_crt_side->medium, - trgsides, crt_side_idx); - add_side_to_medium_list(scn, side_ids_by_medium + p_ccw_side->medium, - trgsides, ccw_side_idx); + p_crt_side->list_id = FLAG_LIST_SIDE_LIST; + p_ccw_side->list_id = FLAG_LIST_SIDE_LIST; } } return res; @@ -1073,13 +1009,10 @@ res_T senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc) { res_T res = RES_OK; - unsigned m; struct senc_descriptor* desc = NULL; /* By triangle tmp data */ struct darray_triangle_tmp triangles_tmp; char triangles_tmp_initialized = 0; - /* Arrays of trgside ids, organized by medium */ - struct darray_side_id* side_ids_by_medium = NULL; /* Array of connex components. * They are refered to by arrays of ids. */ struct darray_cc_descriptor connex_components; @@ -1115,16 +1048,6 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc) goto error; } - side_ids_by_medium - = MEM_ALLOC(scn->dev->allocator, scn->nmeds * sizeof(struct darray_side_id)); - if(!side_ids_by_medium) { - res = RES_MEM_ERR; - goto error; - } - FOR_EACH(m, 0, scn->nmeds) { - struct darray_side_id* const s = side_ids_by_medium + m; - darray_side_id_init(scn->dev->allocator, s); - } trgsides = MEM_CALLOC(scn->dev->allocator, 2 * scn->nutris, sizeof(struct trgside)); if(!trgsides) { @@ -1134,7 +1057,7 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc) /* Step 2: link triangles by neighbourhood */ res = link_neighbours(scn, trgsides, &neighbourhood_by_edge, - &triangles_tmp, side_ids_by_medium); + &triangles_tmp); if(res != RES_OK) { log_err(scn->dev, "%s: could not link neighbours.\n", FUNC_NAME); goto error; @@ -1150,7 +1073,7 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc) /* Step 3: extract triangle connex components */ res = extract_connex_components(desc, trgsides, &connex_components, - &triangles_tmp, &triangles_comp, side_ids_by_medium); + &triangles_tmp, &triangles_comp); if(res != RES_OK) { log_err(scn->dev, "%s: could not extract connex components from scene.\n", FUNC_NAME); @@ -1159,14 +1082,6 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc) darray_triangle_tmp_release(&triangles_tmp); triangles_tmp_initialized = 0; - if(side_ids_by_medium) { - FOR_EACH(m, 0, scn->nmeds) { - struct darray_side_id* cc = side_ids_by_medium + m; - darray_side_id_release(cc); - } - MEM_RM(scn->dev->allocator, side_ids_by_medium); - } - side_ids_by_medium = NULL; /* Step 4: group components */ res = group_connex_components(desc, trgsides, &triangles_comp, @@ -1194,13 +1109,6 @@ exit: darray_neighbourhood_release(&neighbourhood_by_edge); if(triangles_tmp_initialized) darray_triangle_tmp_release(&triangles_tmp); if(triangles_comp_initialized) darray_triangle_comp_release(&triangles_comp); - if(side_ids_by_medium) { - FOR_EACH(m, 0, scn->nmeds) { - struct darray_side_id* cc = side_ids_by_medium + m; - darray_side_id_release(cc); - } - MEM_RM(scn->dev->allocator, side_ids_by_medium); - } if(trgsides) MEM_RM(scn->dev->allocator, trgsides); if(desc) *out_desc = desc; return res; diff --git a/src/senc_scene_analyze_c.h b/src/senc_scene_analyze_c.h @@ -39,7 +39,7 @@ enum side_flag { enum list_id { FLAG_NO_LIST = 0, - FLAG_LIST_BY_MEDIUM = BIT(1), + FLAG_LIST_SIDE_LIST = BIT(1), FLAG_LIST_COMPONENT = BIT(2), FLAG_WAITING_STACK = BIT(3), FLAG_ANY_LIST = 0xFF