diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2019-12-21 20:23:02 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2019-12-21 20:23:02 +0300 |
commit | a0892bb690fec36edd7999d6729e0826d72dab86 (patch) | |
tree | da1d94d5e26a026dabeabaaa67fb2769e1c11d53 /tests/gtests/blenlib/BLI_delaunay_2d_test.cc | |
parent | 51d8d790d75f61cc30af08f03db92c38b196d793 (diff) |
Fix crash in delaunay triangulation due to epsilon issues.
Diffstat (limited to 'tests/gtests/blenlib/BLI_delaunay_2d_test.cc')
-rw-r--r-- | tests/gtests/blenlib/BLI_delaunay_2d_test.cc | 272 |
1 files changed, 239 insertions, 33 deletions
diff --git a/tests/gtests/blenlib/BLI_delaunay_2d_test.cc b/tests/gtests/blenlib/BLI_delaunay_2d_test.cc index 8b29128eb0d..85e8ae3f141 100644 --- a/tests/gtests/blenlib/BLI_delaunay_2d_test.cc +++ b/tests/gtests/blenlib/BLI_delaunay_2d_test.cc @@ -15,6 +15,10 @@ extern "C" { #include <fstream> #include <sstream> +#define DO_REGULAR_TESTS 1 +#define DO_RANDOM_TESTS 0 +#define DO_FILE_TESTS 0 + static void fill_input_verts(CDT_input *r_input, float (*vcos)[2], int nverts) { r_input->verts_len = nverts; @@ -43,6 +47,117 @@ static void add_input_faces( r_input->faces_len_table = faces_len_table; } +/* The spec should have the form: + * #verts #edges #faces + * <float> <float> [#verts lines) + * <int> <int> [#edges lines] + * <int> <int> ... <int> [#faces lines] + */ +static void fill_input_from_string(CDT_input *r_input, const char *spec) +{ + std::string line; + std::vector<std::vector<int>> faces; + int i, j; + int nverts, nedges, nfaces; + float(*p)[2]; + int(*e)[2]; + int *farr; + int *flen; + int *fstart; + + std::istringstream ss(spec); + getline(ss, line); + std::istringstream hdrss(line); + hdrss >> nverts >> nedges >> nfaces; + if (nverts == 0) { + return; + } + p = (float(*)[2])MEM_malloc_arrayN(nverts, 2 * sizeof(float), __func__); + if (nedges > 0) { + e = (int(*)[2])MEM_malloc_arrayN(nedges, 2 * sizeof(int), __func__); + } + if (nfaces > 0) { + flen = (int *)MEM_malloc_arrayN(nfaces, sizeof(int), __func__); + fstart = (int *)MEM_malloc_arrayN(nfaces, sizeof(int), __func__); + } + i = 0; + while (i < nverts && getline(ss, line)) { + std::istringstream iss(line); + iss >> p[i][0] >> p[i][1]; + i++; + } + i = 0; + while (i < nedges && getline(ss, line)) { + std::istringstream ess(line); + ess >> e[i][0] >> e[i][1]; + i++; + } + i = 0; + while (i < nfaces && getline(ss, line)) { + std::istringstream fss(line); + int v; + faces.push_back(std::vector<int>()); + while (fss >> v) { + faces[i].push_back(v); + } + i++; + } + fill_input_verts(r_input, p, nverts); + if (nedges > 0) { + add_input_edges(r_input, e, nedges); + } + if (nfaces > 0) { + for (i = 0; i < nfaces; i++) { + flen[i] = (int)faces[i].size(); + if (i == 0) { + fstart[i] = 0; + } + else { + fstart[i] = fstart[i - 1] + flen[i - 1]; + } + } + farr = (int *)MEM_malloc_arrayN(fstart[nfaces - 1] + flen[nfaces - 1], sizeof(int), __func__); + for (i = 0; i < nfaces; i++) { + for (j = 0; j < (int)faces[i].size(); j++) { + farr[fstart[i] + j] = faces[i][j]; + } + } + add_input_faces(r_input, farr, fstart, flen, nfaces); + } +} + +static void fill_input_from_file(CDT_input *in, const char *filename) +{ + std::FILE *fp = std::fopen(filename, "rb"); + if (fp) { + std::string contents; + std::fseek(fp, 0, SEEK_END); + contents.resize(std::ftell(fp)); + std::rewind(fp); + std::fread(&contents[0], 1, contents.size(), fp); + std::fclose(fp); + fill_input_from_string(in, contents.c_str()); + } + else { + printf("couldn't open file %s\n", filename); + } +} + +static void free_spec_arrays(CDT_input *in) +{ + if (in->vert_coords) { + MEM_freeN(in->vert_coords); + } + if (in->edges) { + MEM_freeN(in->edges); + } + if (in->faces_len_table) { + MEM_freeN(in->faces_len_table); + MEM_freeN(in->faces_start_table); + MEM_freeN(in->faces); + } +} + /* which output vert index goes with given input vertex? -1 if not found */ static int get_output_vert_index(const CDT_result *r, int in_index) { @@ -187,6 +302,7 @@ static void dump_result(CDT_result *r) } } +#if DO_REGULAR_TESTS TEST(delaunay, Empty) { CDT_input in; @@ -692,7 +808,108 @@ TEST(delaunay, TriInTri) BLI_delaunay_2d_cdt_free(out); } -#if 0 +TEST(delaunay, DiamondInSquare) +{ + CDT_input in; + CDT_result *out; + const char *spec = R"(8 0 2 + 0.0 0.0 + 1.0 0.0 + 1.0 1.0 + 0.0 1.0 + 0.14644660940672627 0.5 + 0.5 0.14644660940672627 + 0.8535533905932737 0.5 + 0.5 0.8535533905932737 + 0 1 2 3 + 4 5 6 7 + )"; + fill_input_from_string(&in, spec); + out = BLI_delaunay_2d_cdt_calc(&in, CDT_CONSTRAINTS_VALID_BMESH); + EXPECT_EQ(out->verts_len, 8); + EXPECT_EQ(out->edges_len, 10); + EXPECT_EQ(out->faces_len, 3); + free_spec_arrays(&in); +} + +TEST(delaunay, DiamondInSquareWire) +{ + CDT_input in; + CDT_result *out; + const char *spec = R"(8 8 0 + 0.0 0.0 + 1.0 0.0 + 1.0 1.0 + 0.0 1.0 + 0.14644660940672627 0.5 + 0.5 0.14644660940672627 + 0.8535533905932737 0.5 + 0.5 0.8535533905932737 + 0 1 + 1 2 + 2 3 + 3 0 + 4 5 + 5 6 + 6 7 + 7 4 + )"; + fill_input_from_string(&in, spec); + out = BLI_delaunay_2d_cdt_calc(&in, CDT_CONSTRAINTS); + EXPECT_EQ(out->verts_len, 8); + EXPECT_EQ(out->edges_len, 8); + EXPECT_EQ(out->faces_len, 2); + free_spec_arrays(&in); +} + +TEST(delaunay, ClosePts) +{ + CDT_input in; + CDT_result *out; + const char *spec = R"(7 2 1 + 0.46876350045204163 0.06087132915854454 + 0.46865847706794739 0.03632887825369835 + 0.49176687002182007 0.03632888197898865 + 0.49166208505630493 0.06087132543325424 + 0.49171400070190430 0.04841339960694313 + 0.49171534180641174 0.04839951172471046 + 0.49045535922050476 0.06087132915854454 + 4 5 + 6 4 + 0 1 2 3 + )"; + fill_input_from_string(&in, spec); + out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL); + EXPECT_EQ(out->verts_len, 7); + EXPECT_EQ(out->edges_len, 12); + EXPECT_EQ(out->faces_len, 6); + free_spec_arrays(&in); +} + +TEST(delaunay, ClosePts2) +{ + CDT_input in; + CDT_result *out; + const char *spec = R"(6 1 1 + -0.17878936231136322 -0.44374340772628784 + -0.17871695756912231 -0.45601493120193481 + -0.17544384300708771 -0.45601493120193481 + -0.17537136375904083 -0.44374340772628784 + -0.17544738948345184 -0.45602506399154663 + -0.17872454226016998 -0.45472940802574158 + 4 5 + 0 1 2 3 + )"; + fill_input_from_string(&in, spec); + out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL); + EXPECT_EQ(out->verts_len, 6); + EXPECT_EQ(out->edges_len, 10); + EXPECT_EQ(out->faces_len, 5); + free_spec_arrays(&in); +} +#endif + +#if DO_RANDOM_TESTS enum { RANDOM_PTS, RANDOM_SEGS, @@ -780,17 +997,17 @@ static void rand_delaunay_test(int test_kind, TEST(delaunay, randompts) { - rand_delaunay_test(RANDOM_PTS, 7, 1, CDT_FULL); + rand_delaunay_test(RANDOM_PTS, 7, 100, CDT_FULL); } TEST(delaunay, randomsegs) { - rand_delaunay_test(RANDOM_SEGS, 7, 1, CDT_FULL); + rand_delaunay_test(RANDOM_SEGS, 7, 100, CDT_FULL); } TEST(delaunay, randompoly) { - rand_delaunay_test(RANDOM_POLY, 7, 1, CDT_FULL); + rand_delaunay_test(RANDOM_POLY, 7, 100, CDT_FULL); } TEST(delaunay, randompoly_inside) @@ -809,48 +1026,36 @@ TEST(delaunay, randompoly_validbmesh) } #endif -#if 0 -/* For debugging or timing large examples. - * The given file should have one point per line, as a space-separated pair of floats +#if DO_FILE_TESTS +/* For timing large examples of points only. + * The given file should have one point per line, as a space-separated pair of floats. */ static void points_from_file_test(const char *filename) { - std::ifstream f; - std::string line; - struct XY { - float x; - float y; - } xy; - std::vector<XY> pts; - int i, n; CDT_input in; CDT_result *out; double tstart; - float (*p)[2]; - f.open(filename); - while (getline(f, line)) { - std::istringstream iss(line); - iss >> xy.x >> xy.y; - pts.push_back(xy); - } - n = (int)pts.size(); - fprintf(stderr, "read %d points\n", (int)pts.size()); - p = (float (*)[2])MEM_malloc_arrayN(n, 2 * sizeof(float), "delaunay"); - for (i = 0; i < n; i++) { - xy = pts[i]; - p[i][0] = xy.x; - p[i][1] = xy.y; - } + fill_input_from_file(&in, filename); tstart = PIL_check_seconds_timer(); - fill_input_verts(&in, p, n); out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL); fprintf(stderr, "time to triangulate=%f seconds\n", PIL_check_seconds_timer() - tstart); BLI_delaunay_2d_cdt_free(out); - MEM_freeN(p); + free_spec_arrays(&in); +} + +TEST(delaunay, debug) +{ + CDT_input in; + CDT_result *out; + fill_input_from_file(&in, "/tmp/cdtinput.txt"); + out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL); + BLI_delaunay_2d_cdt_free(out); + free_spec_arrays(&in); } -# define POINTFILEROOT "/tmp/" +# if 0 +# define POINTFILEROOT "/tmp/" TEST(delaunay, terrain1) { @@ -866,4 +1071,5 @@ TEST(delaunay, terrain3) { points_from_file_test(POINTFILEROOT "points3.txt"); } +# endif #endif |