commit 80400589dd31f02d77b47a5879f25cd0aa4d3aeb
parent 4dbcc9d0894071ffbf63bf1158e2381dc6a0a1c5
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Tue, 17 Apr 2018 18:28:27 +0200
BugFix: fix interior/exterior detection for components.
Diffstat:
2 files changed, 94 insertions(+), 170 deletions(-)
diff --git a/src/senc_scene_analyze.c b/src/senc_scene_analyze.c
@@ -44,8 +44,8 @@
#include <stdlib.h>
#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,\
+ -1, VRTX_NULL__, 0, MEDIUM_NULL__,\
+ CC_ID_NONE, CC_GROUP_ROOT_NONE, ENCLOSURE_NULL__,\
{ TRG_NULL__, 0}\
}
const struct cc_descriptor CC_DESCRIPTOR_NULL = CC_DESCRIPTOR_NULL__;
@@ -181,7 +181,7 @@ self_hit_filter
enum side_id hit_side;
component_id_t hit_component;
- (void) ray_org; (void) ray_dir;
+ (void)ray_org; (void)ray_dir;
ASSERT(hit && triangles_comp && origin_component);
ASSERT(hit->prim.prim_id < darray_triangle_comp_size_get(triangles_comp));
hit_trg_comp = darray_triangle_comp_cdata_get(triangles_comp)
@@ -213,6 +213,7 @@ extract_connex_components
struct mem_allocator* alloc;
int64_t mm;
struct darray_side_id stack;
+ const union double3* positions;
#ifndef NDEBUG
trg_id_t t;
component_id_t c;
@@ -222,6 +223,8 @@ extract_connex_components
&& component_count && res);
alloc = descriptor_get_allocator(desc);
scn = desc->scene;
+ positions = darray_position_cdata_get(&scn->vertices);
+ darray_side_id_init(alloc, &stack);
#ifndef NDEBUG
#pragma omp single
@@ -242,8 +245,6 @@ extract_connex_components
}
#endif
- darray_side_id_init(alloc, &stack);
-
#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;
@@ -263,6 +264,7 @@ extract_connex_components
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;
+ double max_z = -DBL_MAX;
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! */
@@ -303,72 +305,56 @@ extract_connex_components
darray_triangle_tmp_cdata_get(triangles_tmp_array) + crt_trg_id;
const union double3* vertices =
darray_position_cdata_get(&scn->vertices);
+ int use_max_z_vrtx = 0;
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;
+ * Keep track of the appropriate vertex 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(max_z < trg_tmp->max_z) {
+ /* New best vertex */
+ max_z = trg_tmp->max_z;
+ cc->max_z_nz = 0;
+ /* Scan vertices to find one with z == max_z */
+ FOR_EACH(i, 0, 3) {
+ if(max_z == positions[trg_in->vertice_id[i]].pos.z) {
+ cc->max_z_vrtx_id = trg_in->vertice_id[i];
+ break;
}
- } 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_rank < 3);
- ASSERT(trg_in->vertice_id[trg_tmp->max_z_vrtx_rank] < scn->nverts);
- cc->max_z_vrtx_id = trg_in->vertice_id[trg_tmp->max_z_vrtx_rank];
- 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);
- }
+ ASSERT(i < 3); /* One of the vertices matched */
+ }
+ use_max_z_vrtx = 1;
+ } else if(max_z == trg_tmp->max_z) {
+ /* Does this triangle use the currently selected max_z vertex? */
+ FOR_EACH(i, 0, 3) {
+ if(cc->max_z_vrtx_id == trg_in->vertice_id[i]) {
+ use_max_z_vrtx = 1;
+ break;
}
}
}
+ if(use_max_z_vrtx) {
+ /* One of the sides using the current best vertex.
+ * Contribute to the normal at the vertex. */
+ double edge0[3], edge1[3], normal[3], norm;
+
+ 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)) {
+ cc->max_z_nz += normal[2];
+ } else {
+ cc->max_z_nz -= normal[2];
+ }
+ }
/* Record crt_side both as component and triangle level */
cc->side_count++;
@@ -389,8 +375,6 @@ extract_connex_components
/* 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",
@@ -532,6 +516,7 @@ group_connex_components
/* This function is called from an omp parallel block and executed
* concurrently. */
struct cc_descriptor** descriptors;
+ const union double3* positions;
size_t tmp;
component_id_t cc_count;
int64_t ccc;
@@ -545,6 +530,7 @@ group_connex_components
tmp = darray_ptr_component_descriptor_size_get(connex_components);
ASSERT(tmp <= COMPONENT_MAX__);
cc_count = (component_id_t)tmp;
+ positions = darray_position_cdata_get(&desc->scene->vertices);
/* Cast rays to find links between connex components */
#pragma omp for
@@ -556,10 +542,8 @@ group_connex_components
const float dir[3] = { 0, 0, 1 };
const float range[2] = { 0, FLT_MAX };
struct cc_descriptor* const cc = descriptors[c];
- const struct triangle_comp* origin_trg =
- darray_triangle_comp_cdata_get(triangles_comp) + cc->max_z_vrtx_id;
- component_id_t self_hit_component
- = origin_trg->component[1 - TRGSIDE_2_SIDE(cc->max_z_side_id)];
+ component_id_t self_hit_component = cc->cc_id;
+ const double* max_vrtx = positions[cc->max_z_vrtx_id].vec;
if(*res != RES_OK) continue;
ASSERT(cc->cc_id == c);
@@ -575,17 +559,7 @@ group_connex_components
continue;
}
- ASSERT(cc->max_z_nz != 0
- /* The only situation with nz==0 we can think of is this one: */
- || (trgsides[cc->max_z_side_id].medium
- == trgsides[TRGSIDE_OPPOSITE(cc->max_z_side_id)].medium
- && (trgsides[cc->max_z_side_id].facing_side_id[0]
- == TRGSIDE_OPPOSITE(cc->max_z_side_id)
- || trgsides[cc->max_z_side_id].facing_side_id[1]
- == TRGSIDE_OPPOSITE(cc->max_z_side_id)
- || trgsides[cc->max_z_side_id].facing_side_id[2]
- == TRGSIDE_OPPOSITE(cc->max_z_side_id))));
- f3_set_d3(origin, cc->max_vrtx);
+ f3_set_d3(origin, max_vrtx);
/* Self-hit data: self hit if hit this component "on the other side" */
tmp_res = s3d_scene_view_trace_ray(s3d_view, origin, dir, range,
&self_hit_component, &hit);
@@ -600,36 +574,24 @@ group_connex_components
/* Keep track of the first component facing infinity */
ATOMIC_CAS_PTR(infinity_first_cc, cc, NULL);
if((*infinity_first_cc)->medium != cc->medium) {
- const side_id_t infinity_first_side = (*infinity_first_cc)->max_z_side_id;
- const medium_id_t infinity_medium = (*infinity_first_cc)->medium;
/* Medium mismatch! Model topology is broken. */
- const trg_id_t t1 = TRGSIDE_2_TRG(infinity_first_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
- = darray_position_cdata_get(&desc->scene->vertices);
+ const double* infinity_max_vrtx =
+ positions[(*infinity_first_cc)->max_z_vrtx_id].vec;
log_err(desc->scene->dev,
- "Medium mismatch found between triangle %lu %s side and triangle"
- " %lu %s side, both facing infinity.\n",
- (unsigned long)triangles_in[t1].global_id,
- TRGSIDE_IS_FRONT(infinity_first_side) ? "front" : "back",
- (unsigned long)triangles_in[t2].global_id,
- TRGSIDE_IS_FRONT(cc->max_z_side_id) ? "front" : "back");
+ "Medium mismatch found between vertex %lu and vertex %lu,"
+ " both facing infinity.\n",
+ (unsigned long)(*infinity_first_cc)->max_z_vrtx_id,
+ (unsigned long)cc->max_z_vrtx_id);
log_err(desc->scene->dev,
- "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
- (unsigned long)triangles_in[t1].global_id,
- SPLIT3(positions[triangles_in[t1].vertice_id[0]].vec),
- SPLIT3(positions[triangles_in[t1].vertice_id[1]].vec),
- SPLIT3(positions[triangles_in[t1].vertice_id[2]].vec));
+ "Vertex %lu: (%g %g %g)\n",
+ (unsigned long)(*infinity_first_cc)->max_z_vrtx_id,
+ SPLIT3(infinity_max_vrtx));
log_err(desc->scene->dev,
- "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
- (unsigned long)triangles_in[t2].global_id,
- SPLIT3(positions[triangles_in[t2].vertice_id[0]].vec),
- SPLIT3(positions[triangles_in[t2].vertice_id[1]].vec),
- SPLIT3(positions[triangles_in[t2].vertice_id[2]].vec));
+ "Vertex %lu: (%g %g %g)\n",
+ (unsigned long)cc->max_z_vrtx_id,
+ SPLIT3(max_vrtx));
log_err(desc->scene->dev, "Media: %lu VS %lu\n",
- (unsigned long)infinity_medium, (unsigned long)cc->medium);
+ (unsigned long)(*infinity_first_cc)->medium, (unsigned long)cc->medium);
*res = RES_BAD_ARG;
}
/* Same medium as previous members of the group: OK */
@@ -660,34 +622,28 @@ group_connex_components
#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(cc->max_z_side_id);
+ const trg_id_t tr = TRGSIDE_2_TRG(hit_side_id);
const struct triangle_in* triangles_in
= darray_triangle_in_cdata_get(&desc->scene->triangles_in);
- const union double3* positions
- = darray_position_cdata_get(&desc->scene->vertices);
log_err(desc->scene->dev,
- "Medium mismatch found between triangle %lu %s side and triangle"
+ "Medium mismatch found between vertex %lu and triangle"
" %lu %s side facing each other.\n",
- (unsigned long)triangles_in[t1].global_id,
- TRGSIDE_IS_FRONT(hit_side) ? "front" : "back",
- (unsigned long)triangles_in[t2].global_id,
- TRGSIDE_IS_FRONT(cc->max_z_side_id) ? "front" : "back");
+ (unsigned long)cc->max_z_vrtx_id,
+ (unsigned long)triangles_in[tr].global_id,
+ TRGSIDE_IS_FRONT(hit_side_id) ? "front" : "back");
log_err(desc->scene->dev,
- "Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
- (unsigned long)triangles_in[t1].global_id,
- SPLIT3(positions[triangles_in[t1].vertice_id[0]].vec),
- SPLIT3(positions[triangles_in[t1].vertice_id[1]].vec),
- SPLIT3(positions[triangles_in[t1].vertice_id[2]].vec));
+ "Vertex %lu: (%g %g %g)\n",
+ (unsigned long)cc->max_z_vrtx_id,
+ SPLIT3(max_vrtx));
log_err(desc->scene->dev,
"Triangle %lu:\n (%g %g %g)\n (%g %g %g)\n (%g %g %g)\n",
- (unsigned long)triangles_in[t2].global_id,
- SPLIT3(positions[triangles_in[t2].vertice_id[0]].vec),
- SPLIT3(positions[triangles_in[t2].vertice_id[1]].vec),
- SPLIT3(positions[triangles_in[t2].vertice_id[2]].vec));
+ (unsigned long)triangles_in[tr].global_id,
+ SPLIT3(positions[triangles_in[tr].vertice_id[0]].vec),
+ SPLIT3(positions[triangles_in[tr].vertice_id[1]].vec),
+ SPLIT3(positions[triangles_in[tr].vertice_id[2]].vec));
log_err(desc->scene->dev, "Media: %lu VS %lu\n",
- (unsigned long)hit_trg_in->medium[hit_side],
- (unsigned long)cc->medium);
+ (unsigned long)cc->medium,
+ (unsigned long)hit_trg_in->medium[hit_side]);
*res = RES_BAD_ARG;
}
}
@@ -725,7 +681,6 @@ group_connex_components
++enclosures[cc->enclosure_id].cc_count;
/* Linked list of componnents */
fst = enclosures[cc->enclosure_id].first_component;
- 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);
@@ -852,7 +807,6 @@ collect_and_link_neighbours
= darray_neighbourhood_data_get(&neighbourhood_by_edge) + e;
struct darray_neighbour* neighbour_list = &neighbourhood->neighbours;
side_id_t i, neighbour_count;
- unsigned char maxz_vrank, maxz_vrank_edge;
sz = darray_neighbour_size_get(neighbour_list);
ASSERT(sz <= SIDE_MAX__);
neighbour_count = (side_id_t)sz;
@@ -860,13 +814,7 @@ collect_and_link_neighbours
v0 = neighbourhood->edge.vrtx0;
v1 = neighbourhood->edge.vrtx1;
d3_sub(common_edge, vertices[v1].vec, vertices[v0].vec);
- if(vertices[v0].pos.z > vertices[v1].pos.z) {
- maxz_edge = vertices[v0].pos.z;
- maxz_vrank_edge = 0;
- } else {
- maxz_edge = vertices[v1].pos.z;
- maxz_vrank_edge = 1;
- }
+ maxz_edge = MMAX(vertices[v0].pos.z, vertices[v1].pos.z);
norm = d3_normalize(common_edge, common_edge);
ASSERT(norm); (void)norm;
d33_basis(basis, common_edge);
@@ -874,33 +822,14 @@ collect_and_link_neighbours
FOR_EACH(i, 0, neighbour_count) {
struct neighbour_info* neighbour_info
= darray_neighbour_data_get(neighbour_list) + i;
- const struct triangle_in* trg_in = triangles_in + neighbour_info->trg_id;
- struct triangle_tmp* neighbour = triangles_tmp + neighbour_info->trg_id;
- unsigned char actual_vrank;
- v2 = trg_in->vertice_id[(neighbour_info->common_edge_rank + 2) % 3];
- if(vertices[v2].pos.z > maxz_edge) {
- max_z = vertices[v2].pos.z;
- maxz_vrank = 2;
- } else {
- max_z = maxz_edge;
- maxz_vrank = maxz_vrank_edge;
- }
- /* Compute the actual vertex id
- * as vertices are not in the v0 v1 v2 order in the actual triangle */
- if(maxz_vrank == 2) {
- actual_vrank =
- (unsigned char)((neighbour_info->common_edge_rank + 2) % 3);
- } else {
- unsigned char is_r =
- neighbour->reversed_edge[neighbour_info->common_edge_rank];
- ASSERT(maxz_vrank == 0 || maxz_vrank == 1);
- actual_vrank = (unsigned char)((is_r ? 1 - maxz_vrank : maxz_vrank)
- + neighbour_info->common_edge_rank) % 3;
- }
+ const trg_id_t crt_id = neighbour_info->trg_id;
+ const unsigned char crt_edge = neighbour_info->common_edge_rank;
+ const struct triangle_in* trg_in = triangles_in + crt_id;
+ struct triangle_tmp* neighbour = triangles_tmp + crt_id;
+ v2 = trg_in->vertice_id[(crt_edge + 2) % 3];
+ max_z = MMAX(vertices[v2].pos.z, maxz_edge);
ASSERT(neighbour->max_z <= max_z);
neighbour->max_z = max_z;
- ASSERT(actual_vrank <= 2);
- neighbour->max_z_vrtx_rank = actual_vrank;
/* Compute rotation angle around common edge */
d3_sub(edge, vertices[v2].vec, vertices[v0].vec);
d33_muld3(edge, basis, edge);
@@ -923,6 +852,9 @@ collect_and_link_neighbours
= darray_neighbour_cdata_get(neighbour_list) + (i + 1) % neighbour_count;
/* Rank of the edge of interest in triangles */
const unsigned char crt_edge = current->common_edge_rank;
+ /* Here ccw refers to the rotation around the common edge
+ * and has nothing to do with vertices order in triangle definition
+ * nor Front/Back side convention */
const unsigned char ccw_edge = ccw_neighbour->common_edge_rank;
/* User id of current triangles */
const trg_id_t crt_id = current->trg_id;
@@ -1241,10 +1173,10 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
&connex_components, s3d_view, &next_enclosure_id, &infinity_first_cc,
&res);
/* Barrier at the end of step 3: data used in step 3 can be released /
- * data produced by step 2 can be used */
+ * data produced by step 3 can be used */
/* One thread releases some data before going to step 4,
- * the others go to step 4 without sync */
+ * the others go to step 4 without sync */
#pragma omp single nowait
{
if(s3d_view) S3D(scene_view_ref_put(s3d_view));
diff --git a/src/senc_scene_analyze_c.h b/src/senc_scene_analyze_c.h
@@ -109,9 +109,7 @@ struct trgside {
#define CC_GROUP_ROOT_INFINITE (COMPONENT_MAX__-1)
#define CC_GROUP_ID_NONE COMPONENT_MAX__
struct cc_descriptor {
- double max_vrtx[3];
double max_z_nz;
- side_id_t max_z_side_id;
vrtx_id_t max_z_vrtx_id;
side_id_t side_count;
medium_id_t medium;
@@ -119,11 +117,8 @@ struct cc_descriptor {
component_id_t cc_id;
component_id_t cc_group_root;
enclosure_id_t enclosure_id;
- /* To create by-medium linked lists of componnents */
- 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;
@@ -179,8 +174,6 @@ struct triangle_tmp {
/* Are the edges of the triangle defined in the same order than
* the edges they are linked to? */
unsigned char reversed_edge[3];
- /* tmp data used to find the +Z-most vertex of components */
- unsigned char max_z_vrtx_rank;
double max_z;
};
@@ -188,10 +181,9 @@ struct triangle_tmp {
static FINLINE void
triangle_tmp_init(struct mem_allocator* alloc, struct triangle_tmp* trg) {
int i;
- (void) alloc;
+ (void)alloc;
ASSERT(trg);
FOR_EACH(i, 0, 3) trg->reversed_edge[i] = UCHAR_MAX;
- trg->max_z_vrtx_rank = UCHAR_MAX;
trg->max_z = -DBL_MAX;
}
#define DARRAY_FUNCTOR_INIT triangle_tmp_init
