[Bf-blender-cvs] [2867c35d4e7] master: Fix T73271, Delaunay Triangulation not robust enough.
Howard Trickey
noreply at git.blender.org
Tue Jan 28 15:54:42 CET 2020
Commit: 2867c35d4e72cc2223e59ad2036ccc03c56fb2e4
Author: Howard Trickey
Date: Tue Jan 28 09:42:40 2020 -0500
Branches: master
https://developer.blender.org/rB2867c35d4e72cc2223e59ad2036ccc03c56fb2e4
Fix T73271, Delaunay Triangulation not robust enough.
A big rework of the code now uses exact predicates for orientation
and incircle. Also switched the main algorithm to use a faster
divide and conquer algorithm, which is possible with the exact
predicates.
===================================================================
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 4faaf1605e0..118949d1c46 100644
--- a/source/blender/blenlib/intern/delaunay_2d.c
+++ b/source/blender/blenlib/intern/delaunay_2d.c
@@ -17,8 +17,7 @@
/** \file
* \ingroup bli
*
- * Dynamic Constrained Delaunay Triangulation.
- * See paper by Marcelo Kallmann, Hanspeter Bieri, and Daniel Thalmann
+ * Constrained 2d Delaunay Triangulation.
*/
#include "MEM_guardedalloc.h"
@@ -29,12 +28,11 @@
#include "BLI_math.h"
#include "BLI_memarena.h"
#include "BLI_mempool.h"
-#include "BLI_rand.h"
#include "BLI_delaunay_2d.h"
/* Uncomment this define to get helpful debugging functions etc. defined. */
-// #define DEBUG_CDT
+#define DEBUG_CDT
struct CDTEdge;
struct CDTFace;
@@ -53,20 +51,21 @@ 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. */
+ int merge_to_index; /* Index of a CDTVert that this has merged to. -1 if no merge. */
} CDTVert;
typedef struct CDTEdge {
LinkNode *input_ids; /* List of input edge ids that this is part of. */
SymEdge symedges[2]; /* The directed edges for this edge. */
+ bool in_queue; /* Used in flipping algorithm. */
} CDTEdge;
typedef struct CDTFace {
- double centroid[2]; /* Average of vertex coords. */
SymEdge *symedge; /* A symedge in face; only used during output. */
LinkNode *input_ids; /* List of input face ids that this is part of. */
int visit_index; /* Which visit epoch has this been seen. */
bool deleted; /* Marks this face no longer used. */
+ bool in_queue; /* Used in remove_small_features algorithm. */
} CDTFace;
typedef struct CDT_state {
@@ -76,6 +75,7 @@ typedef struct CDT_state {
CDTVert **vert_array;
int vert_array_len;
int vert_array_len_alloc;
+ int input_vert_tot;
double minx;
double miny;
double maxx;
@@ -83,19 +83,13 @@ typedef struct CDT_state {
double margin;
int visit_count;
int face_edge_offset;
- RNG *rng;
MemArena *arena;
BLI_mempool *listpool;
double epsilon;
+ double epsilon_squared;
bool output_prepared;
} CDT_state;
-typedef struct LocateResult {
- enum { OnVert, OnEdge, InFace } loc_kind;
- SymEdge *se;
- double edge_lambda;
-} LocateResult;
-
#define DLNY_ARENASIZE 1 << 14
/**
@@ -105,60 +99,57 @@ typedef struct LocateResult {
#define DLNY_MARGIN_PCT 2000.0
#ifdef DEBUG_CDT
+# ifdef __GNUC__
+# define ATTU __attribute__((unused))
+# else
+# define ATTU
+# endif
# define F2(p) p[0], p[1]
-static void dump_se(const SymEdge *se, const char *lab);
-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);
+# define F3(p) p[0], p[1], p[2]
+ATTU static void dump_se(const SymEdge *se, const char *lab);
+ATTU static void dump_v(const CDTVert *v, const char *lab);
+ATTU static void dump_se_cycle(const SymEdge *se, const char *lab, const int limit);
+ATTU static void dump_id_list(const LinkNode *id_list, const char *lab);
+ATTU static void dump_cdt(const CDT_state *cdt, const char *lab);
+ATTU static void dump_cdt_vert_neighborhood(CDT_state *cdt, int v, int maxdist, const char *lab);
+ATTU static void cdt_draw(CDT_state *cdt, const char *lab);
+ATTU static void cdt_draw_vertex_region(CDT_state *cdt, int v, double dist, const char *lab);
+ATTU static void write_cdt_input_to_file(const CDT_input *inp);
+ATTU static void validate_cdt(CDT_state *cdt,
+ bool check_all_tris,
+ bool check_delaunay,
+ bool check_visibility);
#endif
-/**
- * Return 1 if a,b,c forms CCW angle, -1 if a CW angle, 0 if straight.
- * For straight test, allow b to be withing eps of line.
- */
-static int CCW_test(const double a[2], const double b[2], const double c[2], const double eps)
+static void exactinit(void);
+static double orient2d(const double *pa, const double *pb, const double *pc);
+static double incircle(const double *pa, const double *pb, const double *pc, const double *pd);
+
+/** Return other #SymEdge for same #CDTEdge as se. */
+BLI_INLINE SymEdge *sym(const SymEdge *se)
{
- double det;
- double ab;
+ return se->next->rot;
+}
- /* This is twice the signed area of triangle abc. */
- det = (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]);
- if (eps == 0.0) {
- if (det > 0) {
- return 1;
- }
- else if (det < 0) {
- return -1;
- }
- else {
- return 0;
- }
- }
- ab = len_v2v2_db(a, b);
- if (ab <= eps) {
- return 0;
- }
- det /= ab;
- if (det > eps) {
- return 1;
- }
- else if (det < -eps) {
- return -1;
- }
- return 0;
+/** Return SymEdge whose next is se. */
+BLI_INLINE SymEdge *prev(const SymEdge *se)
+{
+ return se->rot->next->rot;
}
-/** 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)
+/** Return true if a -- b -- c are in that order, assuming they are on a straight line according to
+ * orient2d and we know the order is either abc or bac.
+ * This means ab . ac and bc . ac must both be non-negative. */
+static bool in_line(const double a[2], const double b[2], const double c[2])
{
- return fabs(len_v2v2_db(a, c) - (len_v2v2_db(a, b) + len_v2v2_db(b, c))) <= eps;
+ double ab[2], bc[2], ac[2];
+ sub_v2_v2v2_db(ab, b, a);
+ sub_v2_v2v2_db(bc, c, b);
+ sub_v2_v2v2_db(ac, c, a);
+ if (dot_v2v2_db(ab, ac) < 0.0) {
+ return false;
+ }
+ return dot_v2v2_db(bc, ac) >= 0.0;
}
#ifndef NDEBUG
@@ -176,21 +167,6 @@ static bool reachable(SymEdge *s1, SymEdge *s2, int limit)
}
#endif
-static void calc_face_centroid(SymEdge *se)
-{
- SymEdge *senext;
- double *centroidp = se->face->centroid;
- int count;
- copy_v2_v2_db(centroidp, se->vert->co);
- count = 1;
- for (senext = se->next; senext != se; senext = senext->next) {
- add_v2_v2_db(centroidp, senext->vert->co);
- count++;
- }
- centroidp[0] /= count;
- centroidp[1] /= count;
-}
-
/** Using array to store these instead of linked list so can make a random selection from them. */
static CDTVert *add_cdtvert(CDT_state *cdt, double x, double y)
{
@@ -208,7 +184,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;
+ v->merge_to_index = -1;
cdt->vert_array[cdt->vert_array_len++] = v;
return v;
}
@@ -220,6 +196,7 @@ static CDTEdge *add_cdtedge(
SymEdge *se = &e->symedges[0];
SymEdge *sesym = &e->symedges[1];
e->input_ids = NULL;
+ e->in_queue = false;
BLI_linklist_prepend_arena(&cdt->edges, (void *)e, cdt->arena);
se->edge = sesym->edge = e;
se->face = fleft;
@@ -243,6 +220,7 @@ static CDTFace *add_cdtface(CDT_state *cdt)
f->deleted = false;
f->symedge = NULL;
f->input_ids = NULL;
+ f->in_queue = false;
BLI_linklist_prepend_arena(&cdt->faces, (void *)f, cdt->arena);
return f;
}
@@ -290,37 +268,24 @@ static void add_list_to_input_ids(LinkNode **dst, const LinkNode *src, CDT_state
}
}
-/** Return other #SymEdge for same #CDTEdge as se. */
-static inline SymEdge *sym(const SymEdge *se)
-{
- return se->next->rot;
-}
-
-/** Return SymEdge whose next is se. */
-static inline SymEdge *prev(const SymEdge *se)
-{
- return se->rot->next->rot;
-}
-
-static inline bool is_border_edge(const CDTEdge *e, const CDT_state *cdt)
+BLI_INLINE bool is_border_edge(const CDTEdge *e, const CDT_state *cdt)
{
return e->symedges[0].face == cdt->outer_face || e->symedges[1].face == cdt->outer_face;
}
-/** Does one edge of this edge touch the frame? */
-static bool edge_touches_frame(const CDTEdge *e)
+BLI_INLINE bool is_constrained_edge(const CDTEdge *e)
{
- return e->symedges[0].vert->index < 4 || e->symedges[1].vert->index < 4;
+ return e->input_ids != NULL;
}
-static inline bool is_constrained_edge(const CDTEdge *e)
+BLI_INLINE bool is_deleted_edge(const CDTEdge *e)
{
- return e->input_ids != NULL;
+ return e->symedges[0].next == NULL;
}
-static inline bool is_deleted_edge(const CDTEdge *e)
+BLI_INLINE bool is_original_vert(const CDTVert *v, CDT_state *cdt)
{
- return e->symedges[0].next == NULL;
+ return (v->index < cdt->input_vert_tot);
}
/** Is there already an edge between a and b? */
@@ -357,7 +322,6 @@ static bool vert_touches_face(const CDTVert *v, const CDTFace *f)
* Add an edge from s1->v to s2->v, splitting the face in two.
* The original face will continue to be associated with the subface
* that has s1, and a new face will be made for s2's new face.
- * The centroids of both faces are recalculated.
* Return the new diagonal's CDTEdge *.
*/
static CDTEdge *add_diagonal(CDT_state *cdt, SymEdge *s1, SymEdge *s2)
@@ -366,8 +330,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, 2000));
- BLI_assert(reachable(s2, s1, 2000));
+ BLI_assert(reachable(s1, s2, 20000));
+ BLI_assert(reachable(s2, s1, 20000));
fold = s1->face;
fnew = add_cdtface(cdt);
s1prev = prev(s1);
@@ -392,11 +356,60 @@ static CDTEdge *add_diagonal(CDT_state *cdt, SymEdge *s1, SymEdge *s2)
se->face = fnew;
}
add_list_to_input_ids(&fnew->input_ids, fold->input_ids
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list