diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2021-07-23 15:31:40 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2021-07-23 15:31:40 +0300 |
commit | de2c4ee58782a26f0e2dcac47d54bceb67a137e2 (patch) | |
tree | 796377b10fdd119fd8bd0261a8710b2285cb8680 /source/blender | |
parent | f23b14091f60ccb23659075885d29bd24cd97f9d (diff) |
Another slight increase in speed for Delaunay CDT.
When the new "need_ids" flag is false and the output type is not
one of the valid BMesh kinds, there is no need to propagate even
a dummy id to all of the faces.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/intern/delaunay_2d.cc | 15 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_delaunay_2d_test.cc | 51 |
2 files changed, 64 insertions, 2 deletions
diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc index 47e4617d094..4582ea69d9b 100644 --- a/source/blender/blenlib/intern/delaunay_2d.cc +++ b/source/blender/blenlib/intern/delaunay_2d.cc @@ -2208,7 +2208,10 @@ static int power_of_10_greater_equal_to(int x) * order around each face in turn. And then the next face starts at * cdt->face_edge_offset beyond the start for the previous face. */ -template<typename T> void add_face_constraints(CDT_state<T> *cdt_state, const CDT_input<T> &input) +template<typename T> +void add_face_constraints(CDT_state<T> *cdt_state, + const CDT_input<T> &input, + CDT_output_type output_type) { int nv = input.vert.size(); int nf = input.face.size(); @@ -2265,8 +2268,16 @@ template<typename T> void add_face_constraints(CDT_state<T> *cdt_state, const CD } int fedge_end = fedge_start + flen - 1; if (face_symedge0 != nullptr) { + /* We need to propagate face ids to all faces that represent #f, if #need_ids. + * Even if `need_ids == false`, we need to propagate at least the fact that + * the face ids set would be non-empty if the output type is one of the ones + * making valid BMesh faces. */ int id = cdt_state->need_ids ? f : 0; add_face_ids(cdt_state, face_symedge0, id, fedge_start, fedge_end); + if (cdt_state->need_ids || (output_type == CDT_CONSTRAINTS_VALID_BMESH || + output_type == CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES)) { + add_face_ids(cdt_state, face_symedge0, f, fedge_start, fedge_end); + } } fstart += flen; } @@ -2779,7 +2790,7 @@ CDT_result<T> delaunay_calc(const CDT_input<T> &input, CDT_output_type output_ty add_input_verts(&cdt_state, input); initial_triangulation(&cdt_state.cdt); add_edge_constraints(&cdt_state, input); - add_face_constraints(&cdt_state, input); + add_face_constraints(&cdt_state, input, output_type); return get_cdt_output(&cdt_state, input, output_type); } diff --git a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc index f158a5bbae9..f221036419e 100644 --- a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc +++ b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc @@ -1948,6 +1948,12 @@ void text_test( if (num_lines > 1) { label += " lines=" + std::to_string(num_lines); } + if (!need_ids) { + label += " no_ids"; + } + if (otype != CDT_INSIDE_WITH_HOLES) { + label += " otype=" + std::to_string(otype); + } graph_draw<T>(label, out.vert, out.edge, out.face); } } @@ -1957,6 +1963,51 @@ TEST(delaunay_d, TextB10) text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, true); } +TEST(delaunay_d, TextB10_noids) +{ + text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, false); +} + +TEST(delaunay_d, TextB10_inside) +{ + text_test<double>(10, 1, 1, CDT_INSIDE, true); +} + +TEST(delaunay_d, TextB10_inside_noids) +{ + text_test<double>(10, 1, 1, CDT_INSIDE, false); +} + +TEST(delaunay_d, TextB10_constraints) +{ + text_test<double>(10, 1, 1, CDT_CONSTRAINTS, true); +} + +TEST(delaunay_d, TextB10_constraints_noids) +{ + text_test<double>(10, 1, 1, CDT_CONSTRAINTS, false); +} + +TEST(delaunay_d, TextB10_constraints_valid_bmesh) +{ + text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, true); +} + +TEST(delaunay_d, TextB10_constraints_valid_bmesh_noids) +{ + text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, false); +} + +TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes) +{ + text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, true); +} + +TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes_noids) +{ + text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, false); +} + TEST(delaunay_d, TextB200) { text_test<double>(200, 1, 1, CDT_INSIDE_WITH_HOLES, true); |