commit 0d72160dfdab024b3150ce5a49c086148b61b95b
parent 82e791c5e66d828a4988995854369667c09daab6
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Fri, 29 Mar 2024 15:41:49 +0100
Further rework on connex component grouping
Instead of a postprocess, we now use a preprocess to determine the
distance of the closest geometry. Then the real processing is done by
another closest point query that does not accept hits (thus not
decreasing the search range) so that any hit at the same distance is
analyzed.
Also rules on CC inclusion are made excplicit and tested to avoid some
errors.
Diffstat:
2 files changed, 233 insertions(+), 252 deletions(-)
diff --git a/src/senc3d_scene_analyze.c b/src/senc3d_scene_analyze.c
@@ -30,6 +30,7 @@
#include <rsys/dynamic_array_uint.h>
#include <rsys/dynamic_array_uchar.h>
#include <rsys/clock_time.h>
+#include <rsys/str.h>
#include <star/s3d.h>
@@ -39,7 +40,7 @@
#include <stdlib.h>
#define CC_DESCRIPTOR_NULL__ {\
- 0, 0, NULL,\
+ 0, 0, {{DBL_MAX,-DBL_MAX}, {DBL_MAX,-DBL_MAX}, {DBL_MAX,-DBL_MAX}}, NULL,\
0, INT_MAX, VRTX_NULL__, 0,\
CC_ID_NONE, CC_GROUP_ROOT_NONE, ENCLOSURE_NULL__,\
{ TRG_NULL__, 0}\
@@ -66,6 +67,11 @@ const struct cc_descriptor CC_DESCRIPTOR_NULL = CC_DESCRIPTOR_NULL__;
* If ray.normal < threshold we suspect accuracy could be a problem */
#define DOT_THRESHOLD 0.0001f
+struct filter_ctx0 {
+ component_id_t origin_component;
+ struct darray_triangle_comp* triangles_comp;
+};
+
struct filter_ctx1 {
struct senc3d_scene* scn;
struct s3d_scene_view* view;
@@ -87,24 +93,18 @@ struct filter_ctx2 {
component_id_t component;
};
-struct filter_ctx3 {
- /* Result of hit */
- struct darray_uint* collected_trg_ids;
-};
-
enum fctx_type {
+ FCTX0,
FCTX1,
- FCTX2,
- FCTX3,
- FCTX4
+ FCTX2
};
struct filter_ctx {
enum fctx_type type;
union {
+ struct filter_ctx0 ctx0;
struct filter_ctx1 ctx1;
struct filter_ctx2 ctx2;
- struct filter_ctx3 ctx3;
} c;
};
@@ -124,6 +124,76 @@ neighbour_cmp(const void* w1, const void* w2)
return (a1 > a2) - (a1 < a2);
}
+/* Returns 1 if cc2 is inside cc1, 0 otherwise */
+static FINLINE int
+is_component_inside
+ (struct cc_descriptor* cc1,
+ struct cc_descriptor* cc2,
+ struct filter_ctx1* ctx)
+{
+ int i;
+ side_id_t side;
+ const struct triangle_in* trg = NULL;
+ double pt[3] = { 0, 0, 0 };
+ float org[3], dir[3] = { 0, 0, 1 }, rg[2] = { 0, FLT_MAX };
+ struct filter_ctx ctx2;
+ struct s3d_hit hit = S3D_HIT_NULL;
+ const struct triangle_comp*
+ trg_comp = darray_triangle_comp_cdata_get(ctx->triangles_comp);
+ const struct triangle_in*
+ triangles = darray_triangle_in_cdata_get(&ctx->scn->triangles_in);
+ const union double3* vertices = darray_position_cdata_get(&ctx->scn->vertices);
+ ASSERT(cc1 && cc2 && ctx);
+ /* Volume must be compatible */
+ if(fabs(cc2->_6volume) >= fabs(cc1->_6volume))
+ return 0;
+ /* Bbox must be compatible */
+ for(i = 0; i < 3; i++) {
+ if(cc2->bbox[i][0] < cc1->bbox[i][0] || cc2->bbox[i][1] > cc1->bbox[i][1])
+ return 0;
+ }
+ /* Check if component cc2 is inside component cc1.
+ * We already know that bbox and volume allow cc2 to fit inside component
+ * ccc1, but it is not enough.
+ * The method is to cast a ray from cc2 and count the number of times it
+ * crosses component cc1; as components must not overlap, testing from a
+ * single point is OK, as long as the point is not on cc1 boundary (it is on
+ * cc2 boundary, though). */
+ for(side = cc2->side_range.first; side <= cc2->side_range.last; side++) {
+ /* Find a triangle on cc2 boundary that is not on cc1 boundary (it exists,
+ * as the 2 components cannot share all their triangles) */
+ trg_id_t t = TRGSIDE_2_TRG(side);
+ const component_id_t* candidate_comp = trg_comp[t].component;
+ if(candidate_comp[SENC3D_FRONT] != cc2->cc_id
+ && candidate_comp[SENC3D_BACK] != cc2->cc_id)
+ continue;
+ if(candidate_comp[SENC3D_FRONT] == cc1->cc_id
+ || candidate_comp[SENC3D_BACK] == cc1->cc_id)
+ continue;
+ /* This triangle is OK */
+ trg = triangles + t;
+ break;
+ }
+ ASSERT(trg != NULL);
+ /* Any point on trg can do the trick: use the barycenter */
+ FOR_EACH(i, 0, 3) {
+ vrtx_id_t v = trg->vertice_id[i];
+ ASSERT(v < darray_position_size_get(&ctx->scn->vertices));
+ d3_add(pt, pt, vertices[v].vec);
+ }
+ d3_divd(pt, pt, 3);
+ f3_set_d3(org, pt);
+ /* Trace a ray and count intersections with component c */
+ ctx2.type = FCTX2;
+ ctx2.c.ctx2.triangles_comp = ctx->triangles_comp;
+ ctx2.c.ctx2.cpt = 0;
+ ctx2.c.ctx2.component = cc1->cc_id;
+ S3D(scene_view_trace_ray(ctx->view, org, dir, rg, &ctx2, &hit));
+ /* cc2 is not inside cc1 if cpt is even */
+ if(ctx2.c.ctx2.cpt % 2 == 0) return 0;
+ return 1;
+}
+
static side_id_t
get_side_not_in_connex_component
(const side_id_t last_side,
@@ -182,6 +252,8 @@ self_hit_filter
(void)ray_org; (void)ray_range; (void)filter_data;
ASSERT(fctx_);
+ ASSERT(hit->uv[0] == CLAMP(hit->uv[0], 0, 1));
+ ASSERT(hit->uv[1] == CLAMP(hit->uv[1], 0, 1));
switch (fctx_->type) {
default: FATAL("Invalid");
@@ -204,25 +276,32 @@ self_hit_filter
return 1; /* Reject to continue counting */
}
- case FCTX3: {
- /* The filter is used to posprocess FCTX1 cases ending with a nearly
- * parallel triangle that does not allow to select reliably a side and its
- * attached component information using a closest point request.
- *
- * This filter will collect any triangle in the search area (around the
- * point returned at step FCTX1). These triangles will be further
- * processed by FCTX4 filter with a raytracing request. */
- struct filter_ctx3* ctx = &fctx_->c.ctx3;
- res_T res = darray_uint_push_back(ctx->collected_trg_ids, &hit->prim.prim_id);
- CHK(res == RES_OK);
- return 1; /* Reject do avoid decreasing the search radius */
- }
+ case FCTX0: {
+ /* This filter is called from a closest point query from a point belonging
+ * to origin_component. The returned hit is used to determine the search
+ * radius for FCTX1 main computation. */
+ struct filter_ctx0* ctx = &fctx_->c.ctx0;
+ const struct triangle_comp*
+ trg_comp = darray_triangle_comp_cdata_get(ctx->triangles_comp);
+ const component_id_t*
+ hit_comp = trg_comp[hit->prim.prim_id].component;
- case FCTX4:
- /* The filter is used to posprocess FCTX3 triangles using a single ray.
- *
- * No specific processing is due here. */
- return 0; /* Keep */
+ ASSERT(hit->prim.prim_id
+ < darray_triangle_comp_size_get(ctx->triangles_comp));
+
+ if(hit_comp[SENC3D_FRONT] == ctx->origin_component
+ || hit_comp[SENC3D_BACK] == ctx->origin_component)
+ {
+ /* Self hit */
+ return 1; /* Reject */
+ }
+
+ if(hit->distance > 0 && ray_dir[2] <= 0) {
+ return 1; /* Not upward */
+ }
+
+ return 0; /* Keep*/
+ }
case FCTX1: {
/* This filter is called from a closest point query from a point belonging
@@ -230,6 +309,11 @@ self_hit_filter
* to which origin_component is linked. At a later stage the algorithm
* process linked components to determine their relative inclusions.
*
+ * This filter is called with a search distance that has been ajusted in
+ * FCTX0 filter. This distance must be left unchanged to ensure visiting
+ * all the surfaces at the determined distance: allways reject hits to
+ * avoid decreasing search distance.
+ *
* For each hit, the filter computes if the hit is on a component above
* origin_component (that is with >= Z).
* If the hit is distant (dist>0), we just keep the hit as a valid candidate,
@@ -246,24 +330,24 @@ self_hit_filter
trg_comp = darray_triangle_comp_cdata_get(ctx->triangles_comp);
const component_id_t*
hit_comp = trg_comp[hit->prim.prim_id].component;
- const struct triangle_in*
- triangles = darray_triangle_in_cdata_get(&ctx->scn->triangles_in);
const union double3* vertices = darray_position_cdata_get(&ctx->scn->vertices);
- const struct triangle_in* trg = NULL;
- double org_z, mz = -INF;
enum senc3d_side hit_side;
float s = 0, hit_normal[3], rdir[3];
- int i;
ASSERT(hit->prim.prim_id
< darray_triangle_comp_size_get(ctx->triangles_comp));
- ASSERT(hit->uv[0] == CLAMP(hit->uv[0], 0, 1));
- ASSERT(hit->uv[1] == CLAMP(hit->uv[1], 0, 1));
- /* No self hit */
if(hit_comp[SENC3D_FRONT] == ctx->origin_component
|| hit_comp[SENC3D_BACK] == ctx->origin_component)
- return 1; /* Reject */
+ {
+ /* Self hit */
+ return 1;
+ }
+
+ if(hit->distance > 0 && ray_dir[2] <= 0) {
+ /* Not upward */
+ return 1;
+ }
if(hit->distance == 0) {
/* origin_component is in contact with some other components
@@ -274,100 +358,69 @@ self_hit_filter
FOR_EACH(n, 0, (hit_comp[SENC3D_FRONT] == hit_comp[SENC3D_BACK] ? 1 : 2)) {
const enum senc3d_side sides[2] = { SENC3D_FRONT, SENC3D_BACK };
component_id_t c = hit_comp[sides[n]];
- side_id_t side;
- double pt[3] = { 0, 0, 0 };
- float org[3], dir[3] = { 0, 0, 1 }, rg[2] = { 0, FLT_MAX };
- struct s3d_hit hit2 = S3D_HIT_NULL;
- struct filter_ctx fctx2;
ASSERT(c < darray_ptr_component_descriptor_size_get(ctx->components));
if(comp_descriptors[c]->is_outer_border) {
- if(fabs(comp_descriptors[c]->_6volume)
- <= fabs(comp_descriptors[ctx->origin_component]->_6volume))
- /* Component is not large enough to include origin_component */
+ double v;
+ /* The inner component we are trying to link can only be linked to
+ * an outer component if it is inside */
+ if(!is_component_inside(comp_descriptors[c],
+ comp_descriptors[ctx->origin_component], ctx))
+ {
continue;
+ }
+ v = fabs(comp_descriptors[c]->_6volume);
+ /* If origin_component is inside several outer components, the one
+ * we are looking for is the smallest one (to manage outer component
+ * inside another outer component) */
+ if(v < ctx->current_6volume) {
+ ctx->hit_component = c;
+ ctx->current_6volume = v;
+ ctx->hit_dist = 0;
+ ctx->hit_prim = hit->prim;
+ }
} else {
- vrtx_id_t c_z_id = comp_descriptors[c]->max_z_vrtx_id;
- vrtx_id_t o_z_id = comp_descriptors[ctx->origin_component]->max_z_vrtx_id;
- ASSERT(c_z_id < darray_position_size_get(&ctx->scn->vertices));
- ASSERT(o_z_id < darray_position_size_get(&ctx->scn->vertices));
- if(vertices[c_z_id].pos.z <= vertices[o_z_id].pos.z)
- /* Component is not above origin_component */
+ /* c is an inner component */
+ vrtx_id_t c_z_id;
+ double org_z, v;
+ /* If we've already found a valid outer component, inner components
+ * should not be considered anymore */
+ if(ctx->hit_component != COMPONENT_NULL__
+ && comp_descriptors[ctx->hit_component]->is_outer_border )
+ {
continue;
- }
- /* Check if component c includes origin_component; as components cannot
- * overlap, testing a single point is OK, as long as the point is not on
- * c boundary (can be on origin_component boundary, though).
- * As this case is supposed to be rare, we go for a basic algorithm */
- for(side = comp_descriptors[ctx->origin_component]->side_range.first;
- side <= comp_descriptors[ctx->origin_component]->side_range.last;
- side++)
- {
- /* Find a triangle on origin_component boundary that is not on c
- * boundary (the 2 components cannot share all their triangles) */
- trg_id_t t = TRGSIDE_2_TRG(side);
- const component_id_t* candidate_comp = trg_comp[t].component;
- if(candidate_comp[SENC3D_FRONT] != ctx->origin_component
- && candidate_comp[SENC3D_BACK] != ctx->origin_component)
- continue;
- if(candidate_comp[SENC3D_FRONT] == c
- || candidate_comp[SENC3D_BACK] == c)
- continue;
- /* This triangle is OK */
- trg = triangles + t;
- break;
- }
- ASSERT(trg != NULL);
- /* Any point on trg not on an edge can do the trick: use the barycenter */
- FOR_EACH(i, 0, 3) {
- vrtx_id_t v = trg->vertice_id[i];
- ASSERT(v < darray_position_size_get(&ctx->scn->vertices));
- d3_add(pt, pt, vertices[v].vec);
- }
- d3_divd(pt, pt, 3);
- f3_set_d3(org, pt);
- /* Trace a ray and count intersections with components of trg */
- fctx2.type = FCTX2;
- fctx2.c.ctx2.triangles_comp = ctx->triangles_comp;
- fctx2.c.ctx2.cpt = 0;
- fctx2.c.ctx2.component = c;
- S3D(scene_view_trace_ray(ctx->view, org, dir, rg, &fctx2, &hit2));
- ASSERT(S3D_HIT_NONE(&hit2)); /* The ray is supposed to go to infinity */
- /* origin_component is linked_to an outer component if cpt is odd,
- * linked_to an inner component if cpt is even */
- if(comp_descriptors[c]->is_outer_border == (fctx2.c.ctx2.cpt % 2)) {
- double v = fabs(comp_descriptors[c]->_6volume);
- /* If origin_component is inside several components, the one we are
- * looking for is the smallest one */
- if(v >= ctx->current_6volume) continue;
- ctx->hit_component = fctx2.c.ctx2.component;
- ctx->current_6volume = v;
- /* Continue searching for a smaller component that includes
- * origin_component */
+ }
+ /* The inner component we are trying to link can only be linked to
+ * another inner component if (at least partly) above it and not
+ * inside */
+ c_z_id = comp_descriptors[c]->max_z_vrtx_id;
+ org_z =
+ vertices[comp_descriptors[ctx->origin_component]->max_z_vrtx_id].pos.z;
+ ASSERT(c_z_id < darray_position_size_get(&ctx->scn->vertices));
+ ASSERT(vertices[c_z_id].pos.z >= org_z);
+ if(vertices[c_z_id].pos.z == org_z) {
+ continue; /* Not above */
+ }
+ if(is_component_inside(comp_descriptors[c],
+ comp_descriptors[ctx->origin_component], ctx))
+ {
+ continue; /* Inside */
+ }
+ v = fabs(comp_descriptors[c]->_6volume);
+ /* If origin_component is facing several inner components, the one
+ * we are looking for is the largest one (to manage inner component
+ * inside another inner component) */
+ if(v > ctx->current_6volume) {
+ ctx->hit_component = c;
+ ctx->current_6volume = v;
+ ctx->hit_dist = 0;
+ ctx->hit_prim = hit->prim;
+ }
}
}
- return 1; /* Reject */
+ return 1;
}
- /* Reject hits with < Z */
- ASSERT(hit->prim.prim_id <
- darray_triangle_in_size_get(&ctx->scn->triangles_in));
- trg = triangles + hit->prim.prim_id;
- /* Check if the hit is above ray_org (hit[2] > ray_org[2])
- * As we cannot rely on numerical accuracy when computing hit positions,
- * we use the triangle vertices to check if some part of the hit triangle
- * is above ray_org */
- FOR_EACH(i, 0, 3) {
- vrtx_id_t v = trg->vertice_id[i];
- const union double3* p = vertices + v;
- ASSERT(v < darray_position_size_get(&ctx->scn->vertices));
- if(i == 0 || mz < p->pos.z) mz = p->pos.z;
- }
- /* Don't use org[2] as, being float, it would lead to a float VS double
- * comparison that causes accuracy problems. */
- org_z = vertices[comp_descriptors[ctx->origin_component]->max_z_vrtx_id].pos.z;
- if(mz <= org_z)
- return 1; /* Hit triangle is below ray_org: reject */
-
+ ASSERT(hit->distance > 0);
if(hit_comp[SENC3D_FRONT] == hit_comp[SENC3D_BACK]) {
/* Easy case and hit component is known */
ctx->hit_component = hit_comp[SENC3D_FRONT];
@@ -375,7 +428,7 @@ self_hit_filter
f3_set(ctx->hit_dir, ray_dir);
ctx->hit_dist = hit->distance;
ctx->hit_prim = hit->prim;
- return 0; /* Keep */
+ return 1;
}
/* Compute hit side */
@@ -386,16 +439,16 @@ self_hit_filter
if(fabsf(s) < DOT_THRESHOLD) {
/* We cannot know for sure which side to consider */
- if(ctx->hit_dist == hit->distance && ctx->s > s) {
+ if(ctx->hit_dist == hit->distance && fabsf(ctx->s) > fabsf(s)) {
/* Same distance with worse s: keep the previous hit */
- return 1; /* Reject */
+ return 1;
}
ctx->hit_component = COMPONENT_NULL__;
ctx->s = s;
f3_set(ctx->hit_dir, ray_dir);
ctx->hit_dist = hit->distance;
ctx->hit_prim = hit->prim;
- return 0; /* Keep */
+ return 1;
}
/* Determine which side was hit */
hit_side =
@@ -410,7 +463,7 @@ self_hit_filter
f3_set(ctx->hit_dir, ray_dir);
ctx->hit_dist = hit->distance;
ctx->hit_prim = hit->prim;
- return 0; /* Keep */
+ return 1;
}
}
}
@@ -681,8 +734,8 @@ extract_connex_components
>= medium_id_2_medium_idx(medium));
cmp[side] = cc->cc_id;
}
- /* Compute component area and volume, and record information on the
- * max_z side of the component to help find out if the component is
+ /* Compute component's bbox, area and volume, and record information on
+ * the max_z side of the component to help find out if the component is
* inner or outer */
fst_nz = 1;
max_nz = 0;
@@ -701,10 +754,18 @@ extract_connex_components
const double* v0 = vertices[trg_in->vertice_id[0]].vec;
const double* v1 = vertices[trg_in->vertice_id[1]].vec;
const double* v2 = vertices[trg_in->vertice_id[2]].vec;
- int is_2sided = (trg_comp->component[SENC3D_FRONT]
+ int n, is_2sided = (trg_comp->component[SENC3D_FRONT]
== trg_comp->component[SENC3D_BACK]);
- /* Compute component area and volume */
+ /* Compute component's bbox, area and volume */
+ for(n = 0; n < 3; n++) {
+ cc->bbox[n][0] = MMIN(cc->bbox[n][0], v0[n]);
+ cc->bbox[n][0] = MMIN(cc->bbox[n][0], v1[n]);
+ cc->bbox[n][0] = MMIN(cc->bbox[n][0], v2[n]);
+ cc->bbox[n][1] = MMAX(cc->bbox[n][1], v0[n]);
+ cc->bbox[n][1] = MMAX(cc->bbox[n][1], v1[n]);
+ cc->bbox[n][1] = MMAX(cc->bbox[n][1], v2[n]);
+ }
d3_sub(edge0, v1, v0);
d3_sub(edge1, v2, v0);
d3_cross(normal, edge0, edge1);
@@ -938,10 +999,8 @@ group_connex_components
size_t tmp;
component_id_t cc_count;
int64_t ccc;
- struct filter_ctx ctx1, ctx3, ctx4;
+ struct filter_ctx ctx0, ctx1;
float lower[3], upper[3];
- struct darray_uint collected_triangles;
- int collected_initialized = 0;
ASSERT(scn && triangles_comp && connex_components
&& s3d_view && next_enclosure_id && res);
@@ -961,6 +1020,8 @@ group_connex_components
ASSERT(tmp <= COMPONENT_MAX__);
cc_count = (component_id_t)tmp;
positions = darray_position_cdata_get(&scn->vertices);
+ ctx0.type = FCTX0;
+ ctx0.c.ctx0.triangles_comp = triangles_comp;
ctx1.type = FCTX1;
ctx1.c.ctx1.scn = scn;
ctx1.c.ctx1.view = s3d_view;
@@ -983,10 +1044,9 @@ group_connex_components
ASSERT(cc->cc_group_root == CC_GROUP_ID_NONE);
ASSERT(cc->max_z_vrtx_id < scn->nverts);
- max_vrtx = positions[cc->max_z_vrtx_id].vec;
if(cc->is_outer_border) {
ATOMIC id;
- /* No need to query closest point */
+ /* No need to create a link from this CC: inner CC are doing the job */
cc->cc_group_root = cc->cc_id; /* New group with self as root */
id = ATOMIC_INCR(next_enclosure_id) - 1;
ASSERT(id <= ENCLOSURE_MAX__);
@@ -994,143 +1054,61 @@ group_connex_components
continue;
}
+ /* First step is to determine the distance of the closest upward geometry */
+ max_vrtx = positions[cc->max_z_vrtx_id].vec;
f3_set_d3(origin, max_vrtx);
- /* Self-hit data: self hit if hit this component "on the other side" */
- ctx1.c.ctx1.origin_component = cc->cc_id;
- ctx1.c.ctx1.current_6volume = DBL_MAX;
- ctx1.c.ctx1.hit_dist = FLT_MAX;
- ctx1.c.ctx1.hit_component = COMPONENT_NULL__;
/* Limit search radius. Only upwards moves (+Z) will be considered.
* Use a radius allowing to reach the closest top vertex of scene's AABB */
FOR_EACH(i, 0, 2) {
ASSERT(lower[i] <= origin[i] && origin[i] <= upper[i]);
rrr[i] = MMIN(origin[i] - lower[i], upper[i] - origin[i]);
}
- ASSERT(lower[2] <= origin[2] && origin[2] <= upper[2]);
rrr[2] = upper[2] - origin[2];
r = f3_len(rrr) + FLT_EPSILON; /* Ensure r > 0 */
+ ctx0.c.ctx0.origin_component = cc->cc_id;
+ tmp_res = s3d_scene_view_closest_point(s3d_view, origin, r, &ctx0, &hit);
+ if(tmp_res != RES_OK) {
+ *res = tmp_res;
+ continue;
+ }
+ /* If no hit, the component is facing an infinite medium */
+ if(S3D_HIT_NONE(&hit)) {
+ cc->cc_group_root = CC_GROUP_ROOT_INFINITE;
+ cc->enclosure_id = 0;
+ continue;
+ }
+
+ /* Second step is to determine which component faces component #c */
+ ctx1.c.ctx1.origin_component = cc->cc_id;
+ ctx1.c.ctx1.current_6volume = DBL_MAX;
+ ctx1.c.ctx1.hit_dist = FLT_MAX;
+ ctx1.c.ctx1.hit_component = COMPONENT_NULL__;
+ /* New search radius is hit.distance + some margin to cope with numerical
+ * issues (and r==0 is an error) */
+ r = hit.distance * (1 + FLT_EPSILON) + FLT_EPSILON;
/* Cast a sphere to find links between connex components */
tmp_res = s3d_scene_view_closest_point(s3d_view, origin, r, &ctx1, &hit);
if(tmp_res != RES_OK) {
*res = tmp_res;
continue;
}
- /* If no hit, the component is facing an infinite medium */
+ /* As FCTX1 filter rejects any hit, do not rely on hit but use result as
+ * stored in ctx1 */
+ /* If no hit is accepted, the component is facing an infinite medium */
if(ctx1.c.ctx1.hit_dist == FLT_MAX) {
cc->cc_group_root = CC_GROUP_ROOT_INFINITE;
cc->enclosure_id = 0;
+ continue;
}
else if(ctx1.c.ctx1.hit_component == COMPONENT_NULL__) {
/* The selected triangle was nearly parallel to the line of sight:
* FRONT/BACK discrimination was not reliable enough and should be done
* differently. */
- const struct triangle_in*
- triangles = darray_triangle_in_cdata_get(&scn->triangles_in);
- const union double3* vertices = darray_position_cdata_get(&scn->vertices);
- struct s3d_hit tmp_hit = S3D_HIT_NULL;
- const struct triangle_comp*
- trg_comp = darray_triangle_comp_cdata_get(triangles_comp);
- component_id_t hit_comp;
- float hit_pt[3];
- float short_range;
- const unsigned* ids;
- size_t n;
- int found_conclusive = 0;
- if(!collected_initialized) {
- darray_uint_init(scn->dev->allocator, &collected_triangles);
- collected_initialized = 1;
- }
- /* First step is to collect triangles around the hit previously returned */
- ctx3.type = FCTX3;
- darray_uint_clear(&collected_triangles);
- ctx3.c.ctx3.collected_trg_ids = &collected_triangles;
- /* Check that |ray_dir| == ray_dist i.e. no need to use ray_dir*ray_dist */
- ASSERT(f3_len(ctx1.c.ctx1.hit_dir) == ctx1.c.ctx1.hit_dist);
- f3_add(hit_pt, origin, ctx1.c.ctx1.hit_dir);
- short_range = MMAX(1e-3f, 1e-3f * f3_len(hit_pt));
- tmp_res = s3d_scene_view_closest_point(s3d_view, hit_pt, short_range,
- &ctx3, &tmp_hit);
- if(tmp_res != RES_OK || darray_uint_size_get(&collected_triangles) == 0) {
- log_err(scn->dev, LIB_NAME": %s: %d: collect failed.\n", FUNC_NAME,
- __LINE__ );
- *res = (tmp_res != RES_OK) ? tmp_res : RES_BAD_OP;
- continue;
- }
- /* Second step is to trace rays towards these triangles to find the
- * closest geometry from origin whose normal allows to discrimine reliably
- * which side is seen. Stop after a first conclusive triangle. */
- ids = darray_uint_cdata_get(&collected_triangles);
- for(n = 0; n < darray_uint_size_get(&collected_triangles); n++) {
- const struct triangle_in* trg = triangles + ids[n];
- float rdir[3], range[2], bary[3];
- double pt[3] = { 0, 0, 0 };
- int fst_hit_found = 0;
- ctx4.type = FCTX4;
- /* Any point on trg can do the trick: use the barycenter */
- FOR_EACH(i, 0, 3) {
- vrtx_id_t v = trg->vertice_id[i];
- ASSERT(v < darray_position_size_get(&scn->vertices));
- d3_add(pt, pt, vertices[v].vec);
- }
- f3_set_d3(bary, pt);
- f3_divf(bary, bary, 3);
- f3_sub(rdir, bary, origin);
- f3_normalize(rdir, rdir);
- /* Search starts at half the distance of the closest geometry to avoid
- * self hits */
- range[0] = ctx1.c.ctx1.hit_dist * 0.5f;
- range[1] = FLT_MAX;
- while(1) {
- S3D(scene_view_trace_ray(s3d_view, origin, rdir, range, &ctx4, &tmp_hit));
- if(S3D_HIT_NONE(&tmp_hit)) {
- /* Unexpected => next candidate */
- break;
- }
- if(!fst_hit_found) {
- /* Continue only if conclusive */
- float normal[3], s;
- enum senc3d_side hit_side;
- f3_normalize(normal, tmp_hit.normal);
- s = f3_dot(rdir, normal);
- if(fabsf(s) < DOT_THRESHOLD) {
- /* Unconclusive */
- break;
- }
- /* Determine which side was hit */
- hit_side =
- ((s < 0) /* Facing geometrical normal of hit */
- == ((scn->convention & SENC3D_CONVENTION_NORMAL_FRONT) != 0))
- /* Warning: following Embree 2 convention for geometrical normals,
- * the Star3D hit normal is left-handed while star-enclosures-3d uses
- * right-handed convention */
- ? SENC3D_BACK : SENC3D_FRONT;
- /* Keep it */
- hit_comp = trg_comp[tmp_hit.prim.prim_id].component[hit_side];
- fst_hit_found = 1;
- }
- if(!S3D_PRIMITIVE_EQ(&ctx1.c.ctx1.hit_prim, &tmp_hit.prim)) {
- /* Not a problem as long as the ray eventualy hits the barycenter */
- range[0] = nextafterf(tmp_hit.distance, FLT_MAX);
- continue; /* raytrace again to visit the end of the segment */
- }
- /* At the barycenter */
- break;
- }
- if(fst_hit_found) {
- found_conclusive = 1;
- break; /* Don't need more */
- }
- }
- if(!found_conclusive) {
- /* Could try something else; now just report a failure */
- log_err(scn->dev, LIB_NAME": %s: %d: search failed.\n", FUNC_NAME,
- __LINE__ );
- *res = RES_BAD_OP;
- continue;
- }
- /* We finally got it! Group this component */
- cc->cc_group_root = hit_comp;
- ASSERT(cc->cc_group_root < cc_count);
+ /* Could try something; now just report a failure */
+ log_err(scn->dev, LIB_NAME": %s: %d: search failed.\n", FUNC_NAME,
+ __LINE__ );
+ *res = RES_BAD_OP;
+ continue;
} else {
/* If hit, group this component */
cc->cc_group_root = ctx1.c.ctx1.hit_component;
@@ -1191,7 +1169,6 @@ group_connex_components
}
/* Implicit barrier here */
end:
- if(collected_initialized) darray_uint_release(&collected_triangles);
return;
}
@@ -1662,7 +1639,7 @@ build_result
/* Build side and vertex lists. */
OK2(darray_sides_enc_resize(&enc->sides, enc->side_count));
- /* Size is just a int */
+ /* Size is just a hint */
OK2(darray_vrtx_id_reserve(&enc->vertices,
(size_t)(enc->side_count * 0.6)));
/* New vertex numbering scheme local to the enclosure */
diff --git a/src/senc3d_scene_analyze_c.h b/src/senc3d_scene_analyze_c.h
@@ -17,6 +17,8 @@
#define SENC3D_SCNENE_ANALYZE_C_H
#include "senc3d_internal_types.h"
+#include "senc3d_side_range.h"
+#include "senc3d_scene_c.h"
#include "senc3d.h"
#include <rsys/mem_allocator.h>
@@ -47,6 +49,8 @@ struct cc_descriptor {
double _2area;
/* Six times the signed volume of the component */
double _6volume;
+ /* The component's bounding Box */
+ double bbox[3][2];
/* Media used by this component */
uchar* media;
unsigned media_count;
