diff options
| -rw-r--r-- | source/blender/blenlib/intern/delaunay_2d.c | 125 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_delaunay_2d_test.cc | 27 |
2 files changed, 133 insertions, 19 deletions
diff --git a/source/blender/blenlib/intern/delaunay_2d.c b/source/blender/blenlib/intern/delaunay_2d.c index d5dcd40346f..4abe0dee594 100644 --- a/source/blender/blenlib/intern/delaunay_2d.c +++ b/source/blender/blenlib/intern/delaunay_2d.c @@ -325,6 +325,18 @@ static bool exists_edge(const CDTVert *a, const CDTVert *b) return false; } +/** Is the vertex v incident on face f? */ +static bool vert_touches_face(const CDTVert *v, const CDTFace *f) +{ + SymEdge *se = v->symedge; + do { + if (se->face == f) { + return true; + } + } while ((se = se->rot) != v->symedge); + return false; +} + /** * Assume s1 and s2 are both SymEdges in a face with > 3 sides, * and one is not the next of the other. @@ -1901,35 +1913,107 @@ static void dissolve_symedge(CDT_state *cdt, SymEdge *se) delete_edge(cdt, se); } -static void remove_non_constraint_edges(CDT_state *cdt, const bool valid_bmesh) +/* Remove all non-constraint edges. */ +static void remove_non_constraint_edges(CDT_state *cdt) +{ + LinkNode *ln; + CDTEdge *e; + SymEdge *se; + + for (ln = cdt->edges; ln; ln = ln->next) { + e = (CDTEdge *)ln->link; + se = &e->symedges[0]; + if (!is_deleted_edge(e) && !is_constrained_edge(e)) { + dissolve_symedge(cdt, se); + } + } +} + +/* + * Remove the non-constraint edges, but leave enough of them so that all of the + * faces that would be bmesh faces (that is, the faces that have some input representative) + * are valid: they can't have holes, they can't have repeated vertices, and they can't have + * repeated edges. + * + * Not essential, but to make the result look more aesthetically nice, + * remove the edges in order of decreasing length, so that it is more likely that the + * final remaining support edges are short, and therefore likely to make a fairly + * direct path from an outer face to an inner hole face. + */ + +/* For sorting edges by decreasing length (squared). */ +struct EdgeToSort { + double len_squared; + CDTEdge *e; +}; + +static int edge_to_sort_cmp(const void *a, const void *b) +{ + const struct EdgeToSort *e1 = a; + const struct EdgeToSort *e2 = b; + + if (e1->len_squared > e2->len_squared) { + return -1; + } + else if (e1->len_squared < e2->len_squared) { + return 1; + } + return 0; +} + +static void remove_non_constraint_edges_leave_valid_bmesh(CDT_state *cdt) { LinkNode *ln; CDTEdge *e; SymEdge *se, *se2; CDTFace *fleft, *fright; bool dissolve; + size_t nedges; + int i, ndissolvable; + const double *co1, *co2; + struct EdgeToSort *sorted_edges; + nedges = 0; + for (ln = cdt->edges; ln; ln = ln->next) { + nedges++; + } + if (nedges == 0) { + return; + } + sorted_edges = BLI_memarena_alloc(cdt->arena, nedges * sizeof(*sorted_edges)); + i = 0; for (ln = cdt->edges; ln; ln = ln->next) { e = (CDTEdge *)ln->link; - dissolve = !is_deleted_edge(e) && !is_constrained_edge(e); - if (dissolve) { - se = &e->symedges[0]; - if (valid_bmesh && !edge_touches_frame(e)) { - fleft = se->face; - fright = sym(se)->face; - if (fleft != cdt->outer_face && fright != cdt->outer_face && - (fleft->input_ids != NULL || fright->input_ids != NULL)) { - /* Is there another symedge with same left and right faces? */ - for (se2 = se->next; dissolve && se2 != se; se2 = se2->next) { - if (sym(se2)->face == fright) { - dissolve = false; - } + if (!is_deleted_edge(e) && !is_constrained_edge(e)) { + sorted_edges[i].e = e; + co1 = e->symedges[0].vert->co; + co2 = e->symedges[1].vert->co; + sorted_edges[i].len_squared = len_squared_v2v2_db(co1, co2); + i++; + } + } + ndissolvable = i; + qsort(sorted_edges, ndissolvable, sizeof(*sorted_edges), edge_to_sort_cmp); + for (i = 0; i < ndissolvable; i++) { + e = sorted_edges[i].e; + se = &e->symedges[0]; + dissolve = true; + if (!edge_touches_frame(e)) { + fleft = se->face; + fright = sym(se)->face; + if (fleft != cdt->outer_face && fright != cdt->outer_face && + (fleft->input_ids != NULL || fright->input_ids != NULL)) { + /* Is there another symedge with same left and right faces? + * Or is there a vertex not part of e touching the same left and right faces? */ + for (se2 = se->next; dissolve && se2 != se; se2 = se2->next) { + if (sym(se2)->face == fright || (se2->vert != se->next->vert && vert_touches_face(se2->vert, fright))) { + dissolve = false; } } } - if (dissolve) { - dissolve_symedge(cdt, se); - } + } + if (dissolve) { + dissolve_symedge(cdt, se); } } } @@ -2066,8 +2150,11 @@ static void prepare_cdt_for_output(CDT_state *cdt, const CDT_output_type output_ UNUSED_VARS(f); #endif - if (output_type == CDT_CONSTRAINTS || output_type == CDT_CONSTRAINTS_VALID_BMESH) { - remove_non_constraint_edges(cdt, output_type == CDT_CONSTRAINTS_VALID_BMESH); + if (output_type == CDT_CONSTRAINTS) { + remove_non_constraint_edges(cdt); + } + else if (output_type == CDT_CONSTRAINTS_VALID_BMESH) { + remove_non_constraint_edges_leave_valid_bmesh(cdt); } else if (output_type == CDT_FULL || output_type == CDT_INSIDE) { remove_outer_edges(cdt, output_type == CDT_INSIDE); diff --git a/tests/gtests/blenlib/BLI_delaunay_2d_test.cc b/tests/gtests/blenlib/BLI_delaunay_2d_test.cc index 315e5804784..b62ad50c870 100644 --- a/tests/gtests/blenlib/BLI_delaunay_2d_test.cc +++ b/tests/gtests/blenlib/BLI_delaunay_2d_test.cc @@ -667,6 +667,32 @@ TEST(delaunay, TriCutoff) BLI_delaunay_2d_cdt_free(out); } +TEST(delaunay, TriInTri) +{ + CDT_input in; + CDT_result *out; + float p[][2] = { + {-5.65685f, 0.0f}, + {1.41421f, -5.83095f}, + {0.0f, 0.0f}, + {-2.47487f, -1.45774f}, + {-0.707107f, -2.91548f}, + {-1.06066f ,-1.45774f}, + }; + int f[] = {0, 1, 2, 3, 4, 5}; + int fstart[] = {0, 3}; + int flen[] = {3, 3}; + + fill_input_verts(&in, p, 6); + add_input_faces(&in, f, fstart, flen, 2); + out = BLI_delaunay_2d_cdt_calc(&in, CDT_CONSTRAINTS_VALID_BMESH); + EXPECT_EQ(out->verts_len, 6); + EXPECT_EQ(out->edges_len, 8); + EXPECT_EQ(out->faces_len, 3); + BLI_delaunay_2d_cdt_free(out); +} + +#if 0 enum { RANDOM_PTS, RANDOM_SEGS, @@ -781,6 +807,7 @@ TEST(delaunay, randompoly_validbmesh) { rand_delaunay_test(RANDOM_POLY, 7, 1, CDT_CONSTRAINTS_VALID_BMESH); } +#endif #if 0 /* For debugging or timing large examples. |