[Bf-blender-cvs] [dd3ea78bc88] newboolean: Some fixes for some small epsilon cases.
Howard Trickey
noreply at git.blender.org
Mon Dec 2 15:06:13 CET 2019
Commit: dd3ea78bc88874ea12a88751993a09fb2c71e840
Author: Howard Trickey
Date: Mon Dec 2 08:29:28 2019 -0500
Branches: newboolean
https://developer.blender.org/rBdd3ea78bc88874ea12a88751993a09fb2c71e840
Some fixes for some small epsilon cases.
Also changed default epsilon to 1e-5 from 1e-6, as the latter
is too close to hairy edge and anyway produceds really tiny faces
and edges that I doubt users really want. There's even a case for
it being 1e-4 by default.
===================================================================
M release/scripts/addons
M release/scripts/addons_contrib
M source/blender/blenlib/intern/delaunay_2d.c
M source/blender/bmesh/tools/bmesh_boolean.c
M source/blender/editors/mesh/editmesh_intersect.c
M source/blender/modifiers/intern/MOD_boolean.c
M tests/gtests/blenlib/BLI_delaunay_2d_test.cc
===================================================================
diff --git a/release/scripts/addons b/release/scripts/addons
index 52b58daa975..14d4b8f4e93 160000
--- a/release/scripts/addons
+++ b/release/scripts/addons
@@ -1 +1 @@
-Subproject commit 52b58daa9759d56e45aa6dabd90ec36910e7084a
+Subproject commit 14d4b8f4e936d37eb783ae7368549f6b98d34761
diff --git a/release/scripts/addons_contrib b/release/scripts/addons_contrib
index af1d8170e6f..a7fe2ba6378 160000
--- a/release/scripts/addons_contrib
+++ b/release/scripts/addons_contrib
@@ -1 +1 @@
-Subproject commit af1d8170e6fb19851fd547fe228bceede3375bfe
+Subproject commit a7fe2ba6378e81c7e8a9f73167567141882834c1
diff --git a/source/blender/blenlib/intern/delaunay_2d.c b/source/blender/blenlib/intern/delaunay_2d.c
index 27f7a2a4430..993215580e8 100644
--- a/source/blender/blenlib/intern/delaunay_2d.c
+++ b/source/blender/blenlib/intern/delaunay_2d.c
@@ -111,6 +111,7 @@ 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 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 +152,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
@@ -1569,6 +1567,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 +1580,210 @@ 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) {
+ 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.
+ */
+#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
+ 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. */
+ 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)) {
-#ifdef DEBUG_CDT
- if (dbg_level > 0) {
- fprintf(stderr, "ray goes through va\n");
+ done = true;
+ }
+ 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);
+#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
- state_through_vert = true;
- tout = t;
- t = t->next;
- break;
- }
- else if (ccw2 == 0 && in_line(t->vert->co, vb->co, v2->co)) {
+ if (ccw1 == 0 && in_line(t->vert->co, va->co, v2->co, epsilon)) {
#ifdef DEBUG_CDT
- if (dbg_level > 0) {
- fprintf(stderr, "ray goes through vb\n");
- }
+ if (dbg_level > 0) {
+ fprintf(stderr, "ray goes through va\n");
+ }
#endif
- state_through_vert = true;
- t = t->next->next;
- tout = sym(t);
- break;
- }
- else if (ccw1 > 0 && ccw2 < 0) {
-#ifdef DEBUG_CDT
- if (dbg_level > 0) {
- fprintf(stderr, "segment intersects\n");
+ state_through_vert = true;
+ tout = t;
+ t = t->next;
+ break;
}
+ else if (ccw2 == 0 && in_line(t->vert->co, vb->co, v2->co, epsilon)) {
+#ifdef DEBUG_CDT
+ if (dbg_level > 0) {
+ fprintf(stderr, "ray goes through vb\n");
+ }
#endif
- state_through_vert = false;
- tout = t;
- t = t->next;
- break;
- }
- t = t->rot;
+ state_through_vert = true;
+ t = t->next->next;
+ tout = sym(t);
+ break;
+ }
+ else if (ccw1 > 0 && ccw2 < 0) {
#ifdef DEBUG_CDT
- if (dbg_level > 1) {
- dump_se_cycle(t, "next rot tri", 4);
- }
+ if (dbg_level > 0) {
+ fprintf(stderr, "segment intersects\n");
+ }
#endif
- } while (t != tstart);
- BLI_assert(tout != NULL); /* TODO: something sensible for "this can't happen" */
- crossings[BLI_array_len(crossings) - 1].out = tout;
- }
- }
- else { /* State is "through edge", not "through vert" */
- /* Invariant: ray v1--v2 intersects segment t->edge, not at either end.
- * and t->face is the face we have just passed through. */
- va = t->vert;
- vb = t->next->vert;
+ state_through_vert = false;
+ tout = t;
+ t = t->next;
+ break;
+ }
+ t = t->rot;
#ifdef DEBUG_CDT
- if (dbg_level > 1) {
- fprintf(stderr, "through edge case\n");
- dump_v(va, " va");
- dump_v(vb, " vb");
- }
+ if (dbg_level > 1) {
+ dump_se_cycle(t, "next rot tri", 4);
+ }
#endif
- isect = isect_seg_seg_v2_lambda_mu_db(va->co, vb->co, v1->co, v2->co, &lambda, NULL);
- /* TODO: something sensible for "this can't happen" */
- BLI_assert(isect == ISECT_LINE_LINE_CROSS);
- UNUSED_VARS_NDEBUG(isect);
+ } while (t != tstart);
+ BLI_assert(tout != NULL); /* TODO: something sensible for "this can't happen" */
+ crossings[BLI_array_len(crossings) - 1].out = tout;
+ }
+ }
+ else { /* State is "through edge", not "through vert" */
+ /* Invariant: ray v1--v2 intersects segment t->edge, not at either end.
+ * and t->face is the face we have just passed through. */
+ va = t->vert;
+ vb = t->next->vert;
#ifdef DEBUG_CDT
- if (dbg_level > 0) {
- fprintf(stderr, "intersect point at %f along va--vb\n", lambda);
- if (dbg_level
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list