diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2021-07-18 17:48:57 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2021-07-18 17:48:57 +0300 |
commit | 3c8d261557e0b76d2d97902ade5668b6044227b6 (patch) | |
tree | bb93cca1993dbe982a9c3b62275a5a2a3739ac9f /source/blender/blenlib/tests/BLI_delaunay_2d_test.cc | |
parent | e82c5c660778b3805f50f3f2901923692c17db2a (diff) |
Greatly improve speed of Delaunay when have a lot of holes.
Using part of a patch from Erik Abrahamsson, this replaces the
use of linked lists for original id tracking by Sets.
I had thought that the lists were unlikely to grow to more than
a few elements, but when the mesh has a lot of holes (whose
original ids go *outside* the hole, and therefore, most of the
mesh), this assumption can be very wrong.
On a Text regression test, the time went from 11.67s to 0.16s
with this fix. I also tested to make sure that Boolean didn't
slow down with this, and found it actually had a very slight speedup.
Using Sets exposed a dependency on the ordering of the items
in the id lists, luckily caught by a mesh intersect regression test,
so fixed that.
Diffstat (limited to 'source/blender/blenlib/tests/BLI_delaunay_2d_test.cc')
-rw-r--r-- | source/blender/blenlib/tests/BLI_delaunay_2d_test.cc | 78 |
1 files changed, 77 insertions, 1 deletions
diff --git a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc index 08a3818e18f..9356201063b 100644 --- a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc +++ b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc @@ -241,7 +241,7 @@ template<typename T> std::ostream &operator<<(std::ostream &os, const CDT_result for (int i : r.edge.index_range()) { os << "e" << i << " = (" << r.edge[i].first << ", " << r.edge[i].second << ")\n"; os << " orig: "; - for (int j : r.edge_orig[i].size()) { + for (int j : r.edge_orig[i].index_range()) { os << r.edge_orig[i][j] << " "; } os << "\n"; @@ -797,6 +797,55 @@ template<typename T> void crosssegs_test() } } +template<typename T> void cutacrosstri_test() +{ + /* Right triangle with horizontal segment exactly crossing in the middle. */ + const char *spec = R"(5 1 1 + 0.0 0.0 + 1.0 0.0 + 0.0 1.0 + 0.0 0.5 + 0.5 0.5 + 3 4 + 0 1 2 + )"; + + CDT_input<T> in = fill_input_from_string<T>(spec); + CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL); + EXPECT_EQ(out.vert.size(), 5); + EXPECT_EQ(out.edge.size(), 7); + EXPECT_EQ(out.face.size(), 3); + int v0_out = get_orig_index(out.vert_orig, 0); + int v1_out = get_orig_index(out.vert_orig, 1); + int v2_out = get_orig_index(out.vert_orig, 2); + int v3_out = get_orig_index(out.vert_orig, 3); + int v4_out = get_orig_index(out.vert_orig, 4); + EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1 && v4_out != -1); + if (out.face.size() == 3) { + int e0_out = get_orig_index(out.edge_orig, 0); + EXPECT_NE(e0_out, -1); + int fe0_out = get_output_edge_index(out, v0_out, v1_out); + EXPECT_NE(fe0_out, -1); + int fe1a_out = get_output_edge_index(out, v1_out, v4_out); + EXPECT_NE(fe1a_out, -1); + int fe1b_out = get_output_edge_index(out, v4_out, v2_out); + EXPECT_NE(fe1b_out, -1); + if (fe1a_out != 0 && fe1b_out != 0) { + EXPECT_EQ(e0_out, get_orig_index(out.edge_orig, 0)); + EXPECT_TRUE(out.edge_orig[fe1a_out].size() == 1 && out.edge_orig[fe1a_out][0] == 11); + EXPECT_TRUE(out.edge_orig[fe1b_out].size() == 1 && out.edge_orig[fe1b_out][0] == 11); + } + int e_diag = get_output_edge_index(out, v0_out, v4_out); + EXPECT_NE(e_diag, -1); + if (e_diag != -1) { + EXPECT_EQ(out.edge_orig[e_diag].size(), 0); + } + } + if (DO_DRAW) { + graph_draw<T>("CutAcrossTri", out.vert, out.edge, out.face); + } +} + template<typename T> void diamondcross_test() { /* Diamond with constraint edge from top to bottom. Some dup verts. */ @@ -1470,6 +1519,11 @@ TEST(delaunay_d, CrossSegs) crosssegs_test<double>(); } +TEST(delaunay_d, CutAcrossTri) +{ + cutacrosstri_test<double>(); +} + TEST(delaunay_d, DiamondCross) { diamondcross_test<double>(); @@ -1610,6 +1664,11 @@ TEST(delaunay_m, CrossSegs) crosssegs_test<mpq_class>(); } +TEST(delaunay_m, CutAcrossTri) +{ + cutacrosstri_test<mpq_class>(); +} + TEST(delaunay_m, DiamondCross) { diamondcross_test<mpq_class>(); @@ -1876,6 +1935,23 @@ TEST(delaunay_d, TextB10_10_10) text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES); } +# ifdef WITH_GMP +TEST(delaunay_m, TextB10) +{ + text_test<mpq_class>(10, 1, 1, CDT_INSIDE_WITH_HOLES); +} + +TEST(delaunay_m, TextB200) +{ + text_test<mpq_class>(200, 1, 1, CDT_INSIDE_WITH_HOLES); +} + +TEST(delaunay_m, TextB10_10_10) +{ + text_test<mpq_class>(10, 10, 10, CDT_INSIDE_WITH_HOLES); +} +# endif + #endif #if DO_RANDOM_TESTS |