[Bf-blender-cvs] [cb8b424c6bf] master: Made BLI_delaunay_2d_cdt_calc better at tiny feature elimination.
Howard Trickey
noreply at git.blender.org
Sat Feb 29 19:37:33 CET 2020
Commit: cb8b424c6bff09bd0f7a8f66c2321c803c6e0bdd
Author: Howard Trickey
Date: Sat Feb 29 13:23:44 2020 -0500
Branches: master
https://developer.blender.org/rBcb8b424c6bff09bd0f7a8f66c2321c803c6e0bdd
Made BLI_delaunay_2d_cdt_calc better at tiny feature elimination.
The 'random' unit tests and some examples from the new boolean code
triggered asserts and crashes. This fixes those.
There is a new flag in the input that optionally disables a pass
over input to snap segment edges to other segments.
===================================================================
M source/blender/blenlib/BLI_delaunay_2d.h
M source/blender/blenlib/intern/delaunay_2d.c
M source/blender/python/mathutils/mathutils_geometry.c
M tests/gtests/blenlib/BLI_delaunay_2d_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index fe81de5fc5e..9d853dd9509 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -104,6 +104,11 @@
* If zero is supplied for epsilon, an internal value of 1e-8 used
* instead, since this code will not work correctly if it is not allowed
* to merge "too near" vertices.
+ *
+ * Normally, if epsilon is non-zero, there is an "input modify" pass which
+ * checks to see if some vertices are within epsilon of other edges, and
+ * snapping them to those edges if so. You can skip this pass by setting
+ * skip_input_modify to true. (This is also useful in some unit tests.)
*/
typedef struct CDT_input {
int verts_len;
@@ -115,6 +120,7 @@ typedef struct CDT_input {
int *faces_start_table;
int *faces_len_table;
float epsilon;
+ bool skip_input_modify;
} CDT_input;
/**
diff --git a/source/blender/blenlib/intern/delaunay_2d.c b/source/blender/blenlib/intern/delaunay_2d.c
index c222ed06aaa..235ea6a4da4 100644
--- a/source/blender/blenlib/intern/delaunay_2d.c
+++ b/source/blender/blenlib/intern/delaunay_2d.c
@@ -32,7 +32,7 @@
#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;
@@ -52,6 +52,7 @@ typedef struct CDTVert {
LinkNode *input_ids; /* List of corresponding vertex input ids. */
int index; /* Index into array that cdt keeps. */
int merge_to_index; /* Index of a CDTVert that this has merged to. -1 if no merge. */
+ int visit_index; /* Which visit epoch has this been seen. */
} CDTVert;
typedef struct CDTEdge {
@@ -61,7 +62,7 @@ typedef struct CDTEdge {
} CDTEdge;
typedef struct CDTFace {
- SymEdge *symedge; /* A symedge in face; only used during output. */
+ SymEdge *symedge; /* A symedge in face; only used during output, so only valid then. */
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. */
@@ -69,35 +70,30 @@ typedef struct CDTFace {
} CDTFace;
typedef struct CDT_state {
- LinkNode *edges;
- LinkNode *faces;
- CDTFace *outer_face;
- CDTVert **vert_array;
- int vert_array_len;
- int vert_array_len_alloc;
- int input_vert_tot;
- double minx;
- double miny;
- double maxx;
- double maxy;
- double margin;
- int visit_count;
- int face_edge_offset;
- MemArena *arena;
- BLI_mempool *listpool;
- double epsilon;
- double epsilon_squared;
- bool output_prepared;
+ LinkNode *edges; /* List of CDTEdge pointer. */
+ LinkNode *faces; /* List of CDTFace pointer. */
+ CDTFace *outer_face; /* Which CDTFace is the outer face. */
+ CDTVert **vert_array; /* Array of CDTVert pointer, grows. */
+ int vert_array_len; /* Current length of vert_array. */
+ int vert_array_len_alloc; /* Allocated length of vert_array. */
+ int input_vert_tot; /* How many verts were in input (will be first in vert_array). */
+ double minx; /* Used for debug drawing. */
+ double miny; /* Used for debug drawing. */
+ double maxx; /* Used for debug drawing. */
+ double maxy; /* Used for debug drawing. */
+ double margin; /* Used for debug drawing. */
+ int visit_count; /* Used for visiting things without having to initialized their visit fields. */
+ int face_edge_offset; /* Input edge id where we start numbering the face edges. */
+ MemArena *arena; /* Most allocations are done from here, so can free all at once at end. */
+ BLI_mempool *listpool; /* Allocations of ListNodes done from this pool. */
+ double epsilon; /* The user-specified nearness limit. */
+ double epsilon_squared; /* Square of epsilon. */
+ bool output_prepared; /* Set after the mesh has been modified for output (may not be all
+ triangles now). */
} CDT_state;
#define DLNY_ARENASIZE 1 << 14
-/**
- * This margin means that will only be a 1 degree possible
- * concavity on outside if remove all border touching triangles.
- */
-#define DLNY_MARGIN_PCT 2000.0
-
#ifdef DEBUG_CDT
# ifdef __GNUC__
# define ATTU __attribute__((unused))
@@ -106,14 +102,22 @@ typedef struct CDT_state {
# endif
# define F2(p) p[0], p[1]
# define F3(p) p[0], p[1], p[2]
+struct CrossData;
ATTU static void dump_se(const SymEdge *se, const char *lab);
+ATTU static void dump_se_short(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_cross_data(struct CrossData *cd, 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_region(
+ CDT_state *cdt, const char *lab, double minx, double miny, double maxx, double maxy);
+
ATTU static void cdt_draw_vertex_region(CDT_state *cdt, int v, double dist, const char *lab);
+ATTU static void cdt_draw_edge_region(
+ CDT_state *cdt, int v1, int v2, 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,
@@ -140,8 +144,7 @@ BLI_INLINE SymEdge *prev(const SymEdge *se)
/**
* 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.
- */
+ * 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])
{
double ab[2], bc[2], ac[2];
@@ -187,6 +190,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->merge_to_index = -1;
+ v->visit_index = 0;
cdt->vert_array[cdt->vert_array_len++] = v;
return v;
}
@@ -290,20 +294,38 @@ BLI_INLINE bool is_original_vert(const CDTVert *v, CDT_state *cdt)
return (v->index < cdt->input_vert_tot);
}
-/** Is there already an edge between a and b? */
-static bool exists_edge(const CDTVert *a, const CDTVert *b)
+/** Return the Symedge that goes from v1 to v2, if it exists, else return NULL. */
+static SymEdge *find_symedge_between_verts(const CDTVert *v1, const CDTVert *v2)
{
- SymEdge *se, *ss;
- se = a->symedge;
- if (se->next->vert == b) {
- return true;
- }
- for (ss = se->rot; ss != se; ss = ss->rot) {
- if (ss->next->vert == b) {
- return true;
+ SymEdge *tstart, *t;
+
+ t = tstart = v1->symedge;
+ do {
+ if (t->next->vert == v2) {
+ return t;
}
- }
- return false;
+ } while ((t = t->rot) != tstart);
+ return NULL;
+}
+
+/** Return the SymEdge attached to v that has face f, if it exists, else return NULL. */
+static SymEdge *find_symedge_with_face(const CDTVert *v, const CDTFace *f)
+{
+ SymEdge *tstart, *t;
+
+ t = tstart = v->symedge;
+ do {
+ if (t->face == f) {
+ return t;
+ }
+ } while ((t = t->rot) != tstart);
+ return NULL;
+}
+
+/** Is there already an edge between a and b? */
+static inline bool exists_edge(const CDTVert *v1, const CDTVert *v2)
+{
+ return find_symedge_between_verts(v1, v2) != NULL;
}
/** Is the vertex v incident on face f? */
@@ -533,7 +555,7 @@ static void delete_edge(CDT_state *cdt, SymEdge *e)
}
}
-static CDT_state *new_cdt_init(const CDT_input *in)
+static CDT_state *cdt_init(const CDT_input *in)
{
int i;
MemArena *arena = BLI_memarena_new(DLNY_ARENASIZE, __func__);
@@ -1121,496 +1143,711 @@ static void re_delaunay_triangulate(CDT_state *cdt, SymEdge *se)
}
}
+static double tri_orient(const SymEdge *t)
+{
+ return orient2d(t->vert->co, t->next->vert->co, t->next->next->vert->co);
+}
+
/**
- * Add a constrained edge between v1 and v2 to cdt structure.
- * This may result in a number of #CDTEdges created, due to intersections
- * and partial overlaps with existing cdt vertices and edges.
- * Each created #CDTEdge will have input_id added to its input_ids list.
+ * The CrossData struct gives defines either an endpoint or an intermediate point
+ * in the path we will take to insert an edge constraint.
+ * Each such point will either be
+ * (a) a vertex or
+ * (b) a fraction lambda (0 < lambda < 1) along some SymEdge.]
*
- * If \a r_edges is not NULL, the #CDTEdges generated or found that go from
- * v1 to v2 are put into that linked list, in order.
+ * In general, lambda=0 indicates case a and lambda != 0 indicates case be.
+ * The 'in' edge gives the destination attachment point of a diagonal from the previous crossing,
+ * and the 'out' edge gives the origin attachment point of a diagonal to the next crossing.
+ * But in some cases, 'in' and 'out' are undefined or not needed, and will be NULL.
*
- * Assumes that #BLI_constrained_delaunay_get_output has not been called yet.
+ * For case (a), 'vert' will be the vertex, and lambda will be 0, and 'in' will be the SymEdge from
+ * 'vert' that has as face the one that you go through to get to this vertex. If you go exactly
+ * along an edge then we set 'in' to NULL, since it won't be needed. The first crossing will have
+ * 'in' = NULL. We set 'out' to the SymEdge that has the face we go though to get to the next
+ * crossing, or, if the next crossing is a case (a), then it is the edge that goes to that next
+ * vertex. 'out' wlll be NULL for the last one.
+ *
+ * For case (b), vert will be NULL at first, and later filled in with the created split vertex,
+ * and 'in' will be the SymEdge that we go through, and lambda will be between 0 and 1,
+ * the fraction from in's vert to in->next'
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list