[Bf-blender-cvs] [a0892bb690f] master: Fix crash in delaunay triangulation due to epsilon issues.
Howard Trickey
noreply at git.blender.org
Sat Dec 21 18:27:02 CET 2019
Commit: a0892bb690fec36edd7999d6729e0826d72dab86
Author: Howard Trickey
Date: Sat Dec 21 12:23:02 2019 -0500
Branches: master
https://developer.blender.org/rBa0892bb690fec36edd7999d6729e0826d72dab86
Fix crash in delaunay triangulation due to epsilon issues.
===================================================================
M source/blender/blenlib/intern/delaunay_2d.c
M tests/gtests/blenlib/BLI_delaunay_2d_test.cc
===================================================================
diff --git a/source/blender/blenlib/intern/delaunay_2d.c b/source/blender/blenlib/intern/delaunay_2d.c
index 27f7a2a4430..350f99ce434 100644
--- a/source/blender/blenlib/intern/delaunay_2d.c
+++ b/source/blender/blenlib/intern/delaunay_2d.c
@@ -53,6 +53,7 @@ typedef struct CDTVert {
SymEdge *symedge; /* Some edge attached to it. */
LinkNode *input_ids; /* List of corresponding vertex input ids. */
int index; /* Index into array that cdt keeps. */
+ int visit_index; /* Which visit epoch has this been seen. */
} CDTVert;
typedef struct CDTEdge {
@@ -110,7 +111,9 @@ static void dump_v(const CDTVert *v, const char *lab);
static void dump_se_cycle(const SymEdge *se, const char *lab, const int limit);
static void dump_id_list(const LinkNode *id_list, const char *lab);
static void dump_cdt(const CDT_state *cdt, const char *lab);
+static void dump_cdt_vert_neighborhood(CDT_state *cdt, int v, int maxdist, const char *lab);
static void cdt_draw(CDT_state *cdt, const char *lab);
+static void write_cdt_input_to_file(const CDT_input *inp);
static void validate_face_centroid(SymEdge *se);
static void validate_cdt(CDT_state *cdt, bool check_all_tris);
#endif
@@ -151,14 +154,11 @@ static int CCW_test(const double a[2], const double b[2], const double c[2], con
return 0;
}
-/** return true if a -- b -- c are in that order, assuming they are on a straight line. */
-static bool in_line(const double a[2], const double b[2], const double c[2])
+/** return true if a -- b -- c are in that order, assuming they are on a straight line according to
+ * CCW_test. */
+static bool in_line(const double a[2], const double b[2], const double c[2], double eps)
{
- double dir_ab[2], dir_ac[2];
-
- sub_v2_v2v2_db(dir_ab, a, b);
- sub_v2_v2v2_db(dir_ac, a, c);
- return dot_v2v2_db(dir_ab, dir_ac) >= 0.0;
+ return fabs(len_v2v2_db(a, c) - (len_v2v2_db(a, b) + len_v2v2_db(b, c))) <= eps;
}
#ifndef NDEBUG
@@ -208,6 +208,7 @@ static CDTVert *add_cdtvert(CDT_state *cdt, double x, double y)
}
BLI_assert(cdt->vert_array_len < cdt->vert_array_len_alloc);
v->index = cdt->vert_array_len;
+ v->visit_index = 0;
cdt->vert_array[cdt->vert_array_len++] = v;
return v;
}
@@ -365,8 +366,8 @@ static CDTEdge *add_diagonal(CDT_state *cdt, SymEdge *s1, SymEdge *s2)
CDTFace *fold, *fnew;
SymEdge *sdiag, *sdiagsym;
SymEdge *s1prev, *s1prevsym, *s2prev, *s2prevsym, *se;
- BLI_assert(reachable(s1, s2, 20));
- BLI_assert(reachable(s2, s1, 20));
+ BLI_assert(reachable(s1, s2, 2000));
+ BLI_assert(reachable(s2, s1, 2000));
fold = s1->face;
fnew = add_cdtface(cdt);
s1prev = prev(s1);
@@ -385,7 +386,7 @@ static CDTEdge *add_diagonal(CDT_state *cdt, SymEdge *s1, SymEdge *s2)
s2->rot = sdiagsym;
sdiagsym->rot = s2prevsym;
#ifdef DEBUG_CDT
- BLI_assert(reachable(s2, sdiag, 20));
+ BLI_assert(reachable(s2, sdiag, 2000));
#endif
for (se = s2; se != sdiag; se = se->next) {
se->face = fnew;
@@ -1505,7 +1506,8 @@ static void add_edge_constraint(
SymEdge *se;
CDTEdge *edge;
int ccw1, ccw2, isect;
- int i, search_count;
+ int i, search_count, visit;
+ double curco[2];
double lambda;
const double epsilon = cdt->epsilon;
bool done, state_through_vert;
@@ -1553,7 +1555,7 @@ static void add_edge_constraint(
* in = a
* out = b
*
- * crossings[0] will have in = NULL, and crossings[last] will have out = NULL
+ * crossings[0] will have in = NULL, and crossings[last] will have out = NULL.
*/
if (r_edges) {
*r_edges = NULL;
@@ -1569,6 +1571,9 @@ static void add_edge_constraint(
dump_se(vse1, " se1");
dump_se(vse2, " se2");
}
+ if (dbg_level > 2) {
+ dump_cdt(cdt, "before insert_segment");
+ }
}
#endif
if (v1 == v2) {
@@ -1579,181 +1584,292 @@ static void add_edge_constraint(
#endif
return;
}
- state_through_vert = true;
+ /* Quick check for special case where segment is one of edges from v1. */
+ tstart = t = vse1;
done = false;
- t = vse1;
- search_count = 0;
- while (!done) {
- /* Invariant: crossings[0 .. BLI_array_len(crossings)] has crossing info for path up to
- * but not including the crossing of edge t, which will either be through a vert
- * (if state_through_vert is true) or through edge t not at either end.
- * In the latter case, t->face is the face that ray v1--v2 goes through after path-so-far.
- */
-#ifdef DEBUG_CDT
- if (dbg_level > 1) {
- fprintf(
- stderr, "top of insert_segment main loop, state_through_vert=%d\n", state_through_vert);
- dump_se_cycle(t, "current t ", 4);
- }
-#endif
- if (state_through_vert) {
- /* Invariant: ray v1--v2 contains t->vert. */
- cdata.in = (BLI_array_len(crossings) == 0) ? NULL : t;
- cdata.out = NULL; /* To be filled in if this isn't final. */
+ do {
+ if (t->next->vert == v2) {
+ cdata.in = NULL;
+ cdata.out = t->next;
cdata.lambda = 0.0;
cdata.vert = t->vert;
BLI_array_append(crossings, cdata);
- if (t->vert == v2) {
+ cdata.in = t->next->rot;
+ cdata.out = NULL;
+ cdata.lambda = 0.0;
+ cdata.vert = v2;
+ BLI_array_append(crossings, cdata);
#ifdef DEBUG_CDT
- if (dbg_level > 0) {
- fprintf(stderr, "found v2, so done\n");
- }
+ if (dbg_level > 1) {
+ fprintf(stderr, "special one segment case\n");
+ dump_se(t, " ");
+ }
#endif
- done = true;
+ done = true;
+ break;
+ }
+ t = t->rot;
+ } while (t != tstart);
+ if (!done) {
+ /* To prevent infinite loop in the face of epsilon tests that might lead us back to
+ * an already-visited (vertex, face) pair, use visit indices.
+ */
+ visit = ++cdt->visit_count;
+ state_through_vert = true;
+ done = false;
+ t = vse1;
+ search_count = 0;
+ while (!done) {
+ /* Invariant: crossings[0 .. BLI_array_len(crossings)] has crossing info for path up to
+ * but not including the crossing of edge t, which will either be through a vert
+ * (if state_through_vert is true) or through edge t not at either end.
+ * In the latter case, t->face is the face that ray v1--v2 goes through after path-so-far.
+ * Rather than continually looking for intersection of v1--v2, we keep track of
+ * last vertex or intersection point in curco,because that may be slightly off the ray
+ * v1--v2.
+ */
+#ifdef DEBUG_CDT
+ if (dbg_level > 1) {
+ fprintf(stderr,
+ "top of insert_segment main loop, state_through_vert=%d\n",
+ state_through_vert);
+ dump_se_cycle(t, "current t ", 4);
}
- else {
- /* Do ccw scan of triangles around t->vert to find exit triangle for ray v1--v2. */
- tstart = t;
- tout = NULL;
- do {
- va = t->next->vert;
- vb = t->next->next->vert;
- ccw1 = CCW_test(t->vert->co, va->co, v2->co, epsilon);
- ccw2 = CCW_test(t->vert->co, vb->co, v2->co, epsilon);
+#endif
+ BLI_assert(t->vert->visit_index != visit || t->face->visit_index != visit);
+ t->vert->visit_index = visit;
+ t->face->visit_index = visit;
+ if (state_through_vert) {
+ /* Invariant: ray vcur--v2 contains t->vert. */
+ cdata.in = (BLI_array_len(crossings) == 0) ? NULL : t;
+ cdata.out = NULL; /* To be filled in if this isn't final. */
+ cdata.lambda = 0.0;
+ cdata.vert = t->vert;
+ BLI_array_append(crossings, cdata);
+ if (t->vert == v2) {
#ifdef DEBUG_CDT
- if (dbg_level > 1) {
- fprintf(stderr, "non-final through vert case\n");
- dump_v(va, " va");
- dump_v(vb, " vb");
- fprintf(stderr, "ccw1=%d, ccw2=%d\n", ccw1, ccw2);
+ if (dbg_level > 0) {
+ fprintf(stderr, "found v2, so done\n");
}
#endif
- if (ccw1 == 0 && in_line(t->vert->co, va->co, v2->co)) {
+ done = true;
+ }
+ else {
+ /* Do ccw scan of triangles around t->vert to find exit triangle for ray vcur--v2. */
+ tstart = t;
+ tout = NULL;
+ do {
+ va = t->next->vert;
+ vb = t->next->next->vert;
+ ccw1 = CCW_test(t->vert->co, va->co, v2->co, epsilon);
+ ccw2 = CCW_test(t->vert->co, vb->co, v2->co, epsilon);
+#ifdef DEBUG_CDT
+ if (dbg_level > 1) {
+ fprintf(stderr, "non-final through vert case\n");
+ dump_v(va, " va");
+ dump_v(vb, " vb");
+ fprintf(stderr, "ccw1=%d, ccw2=%d\n", ccw1, ccw2);
+ }
+#endif
+ if (ccw1 == 0 && in_line(t->vert->co, va->co, v2->co, epsilon) &&
+ va->visit_index != visit) {
#ifdef DEBUG_CDT
- if (dbg_level > 0) {
- fprintf(stderr, "ray goes through va\n");
+ if (dbg_level > 0) {
+ fprintf(stderr, "ray goes through va\n");
+ }
+#endif
+ state_through_vert = true;
+ tout = t;
+ t = t->next;
+ break;
}
+ else if (ccw2 == 0 && in_line(t->vert->co, vb->co, v2->co, epsilon) &&
+ vb->visit_index != visit) {
+#ifdef DEBUG_CDT
+ if (dbg_level > 0) {
+ fprintf(stderr, "ray goes through vb\n");
+ }
#endif
- state_through_vert = true;
- tout = t;
- t = t->next;
- break;
- }
- else if (ccw2 == 0 && in_line(t->vert->co, vb->co, v2->co)) {
+ state_through_vert = true;
+ t = t->next->next;
+ tout = sym(t);
+ break;
+ }
+ else if (ccw1 > 0 && ccw2 < 0 &&
+ (t->next->vert->visit_index != visit ||
+ t->next->face->visit_index != visit)) {
+#ifdef DEBUG_CDT
+ if (dbg_level > 0) {
+ fprintf(stderr, "segment intersects\n");
+ }
+#endif
+ state_through_vert = false;
+ tout = t;
+ t = t->next;
+ break
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list