5#include "testing/testing.h"
18#define DO_TEXT_TESTS 0
19#define DO_RANDOM_TESTS 0
47 std::istringstream ss(spec);
50 std::istringstream hdrss(line);
51 int nverts, nedges, nfaces;
52 hdrss >> nverts >> nedges >> nfaces;
56 r_storage.
vert.reinitialize(nverts);
57 r_storage.
edge.reinitialize(nedges);
60 while (i < nverts && getline(ss, line)) {
61 std::istringstream iss(line);
70 while (i < nedges && getline(ss, line)) {
71 std::istringstream ess(line);
78 while (i < nfaces && getline(ss, line)) {
80 std::istringstream fss(line);
96 if (std::is_same_v<mpq_class, T>) {
114 int n = int(out_to_orig.size());
115 for (
int i = 0; i < n; ++i) {
116 for (
uint32_t orig : out_to_orig[i]) {
146template<> mpq_class
math_abs(
const mpq_class
v)
162 int nv = int(
out.vert.size());
163 for (
int i = 0; i < nv; ++i) {
177 int ne = int(
out.edge.size());
178 for (
int i = 0; i < ne; ++i) {
179 if ((
out.edge[i][0] == out_index_1 &&
out.edge[i][1] == out_index_2) ||
180 (
out.edge[i][0] == out_index_2 &&
out.edge[i][1] == out_index_1))
194 return out_vert_index < int(
out.vert_orig.size()) &&
195 out_vert_index < int(
out.intersected_edges_orig.size()) &&
196 out.intersected_edges_orig[out_vert_index][0] == in_edge1_index &&
197 out.intersected_edges_orig[out_vert_index][1] == in_edge2_index;
203 return out_edge_index < int(
out.edge_orig.size()) &&
204 out.edge_orig[out_edge_index].contains(in_edge_index);
212 int nf = int(
out.face.size());
213 int npolyv = int(poly.
size());
214 for (
int f = 0; f < nf; ++f) {
215 if (
out.face[f].size() != poly.
size()) {
218 for (
int cycle_start = 0; cycle_start < npolyv; ++cycle_start) {
220 for (
int k = 0; ok && k < npolyv; ++k) {
221 if (
out.face[f][(cycle_start + k) % npolyv] != poly[k]) {
239 Array<int> tri{out_index_1, out_index_2, out_index_3};
246 return out_face_index < int(
out.face_orig.size()) &&
247 out.face_orig[out_face_index].contains(in_face_index);
254 os << r.
vert.size() <<
" verts, " << r.
edge.size() <<
" edges, " << r.
face.size() <<
" faces\n";
256 for (
int i : r.
vert.index_range()) {
257 os <<
"v" << i <<
" = " << r.
vert[i] <<
"\n";
259 for (
int j : r.
vert_orig[i].index_range()) {
265 for (
int i : r.
edge.index_range()) {
266 os <<
"e" << i <<
" = (" << r.
edge[i][0] <<
", " << r.
edge[i][1] <<
")\n";
268 for (
int j : r.
edge_orig[i].index_range()) {
274 for (
int i : r.
face.index_range()) {
275 os <<
"f" << i <<
" = ";
276 for (
int j : r.
face[i].index_range()) {
277 os << r.
face[i][j] <<
" ";
281 for (
int j : r.
face_orig[i].index_range()) {
301 constexpr const char *drawfile =
"./cdt_test_draw.html";
303 constexpr const char *drawfile =
"/tmp/cdt_test_draw.html";
305 constexpr int max_draw_width = 1400;
306 constexpr int max_draw_height = 1000;
307 constexpr int thin_line = 1;
308 constexpr int vert_radius = 3;
309 constexpr bool draw_vert_labels =
false;
310 constexpr bool draw_edge_labels =
false;
312 if (verts.is_empty()) {
318 for (
int i = 0; i < 2; ++i) {
328 double draw_margin = ((vmax.x - vmin.x) + (vmax.y - vmin.y)) * 0.05;
329 double minx = vmin.x - draw_margin;
330 double maxx = vmax.x + draw_margin;
331 double miny = vmin.y - draw_margin;
332 double maxy = vmax.y + draw_margin;
334 double width = maxx - minx;
335 double height = maxy - miny;
336 double aspect = height / width;
337 int view_width = max_draw_width;
338 int view_height = int(view_width * aspect);
339 if (view_height > max_draw_height) {
340 view_height = max_draw_height;
341 view_width = int(view_height / aspect);
343 double scale = view_width / width;
345#define SX(x) ((math_to_double(x) - minx) * scale)
346#define SY(y) ((maxy - math_to_double(y)) * scale)
350 f.open(drawfile, std::ios_base::app);
356 std::cout <<
"Could not open file " << drawfile <<
"\n";
360 f <<
"<div>" << label <<
"</div>\n<div>\n"
361 <<
"<svg version=\"1.1\" "
362 "xmlns=\"http://www.w3.org/2000/svg\" "
363 "xmlns:xlink=\"http://www.w3.org/1999/xlink\" "
364 "xml:space=\"preserve\"\n"
365 <<
"width=\"" << view_width <<
"\" height=\"" << view_height <<
"\">n";
367 for (
const int i : faces.index_range()) {
368 f <<
"<polygon fill=\"azure\" stroke=\"none\"\n points=\"";
369 for (
int vi : faces[i]) {
371 f <<
SX(co[0]) <<
"," <<
SY(co[1]) <<
" ";
376 for (
const int2 &
e : edges) {
379 int strokew = thin_line;
380 f << R
"(<line fill="none" stroke="black" stroke-width=")" << strokew << "\" x1=\""
381 <<
SX(uco[0]) <<
"\" y1=\"" <<
SY(uco[1]) <<
"\" x2=\"" <<
SX(vco[0]) <<
"\" y2=\""
382 <<
SY(vco[1]) <<
"\">\n";
383 f <<
" <title>[" <<
e[0] <<
"][" <<
e[1] <<
"]</title>\n";
385 if (draw_edge_labels) {
386 f <<
"<text x=\"" <<
SX(0.5 * (uco[0] + vco[0])) <<
"\" y=\"" <<
SY(0.5 * (uco[1] + vco[1]))
387 << R
"(" font-size="small">)";
388 f << "[" <<
e[0] <<
"][" <<
e[1] <<
"]</text>\n";
394 f << R
"(<circle fill="black" cx=")" << SX(vco[0]) << "\" cy=\"" <<
SY(vco[1]) <<
"\" r=\""
395 << vert_radius <<
"\">\n";
396 f <<
" <title>[" << i <<
"]" << vco <<
"</title>\n";
398 if (draw_vert_labels) {
399 f <<
"<text x=\"" <<
SX(vco[0]) + vert_radius <<
"\" y=\"" <<
SY(vco[1]) - vert_radius
400 << R
"(" font-size="small">[)" << i << "]</text>\n";
447 const char *spec = R
"(1 0 0
456 if (
out.vert.size() >= 1) {
463 const char *spec = R
"(2 0 0
467 InputStorage<T> store;
478 if (
out.vert.size() >= 1) {
491 const char *spec = R
"(3 0 0
496 InputStorage<T> store;
505 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1);
506 EXPECT_TRUE(v0_out != v1_out && v0_out != v2_out && v1_out != v2_out);
511 EXPECT_TRUE(e0_out != e1_out && e0_out != e2_out && e1_out != e2_out);
522 const char *spec = R
"(4 3 0
531 InputStorage<T> store;
540 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
544 EXPECT_TRUE(e0_out != -1 && e1_out != -1 && e2_out != -1);
555 const char *spec = R
"(4 0 0
561 InputStorage<T> store;
575 const char *spec = R
"(4 0 0
595 const char *spec = R
"(4 0 0
615 const char *spec = R
"(4 0 0
621 InputStorage<T> store;
635 const char *spec = R
"(4 0 0
655 const char *spec = R
"(6 1 1
665 InputStorage<T> store;
683 graph_draw<T>(
"LineInSquare - inside with holes", out3.vert, out3.edge, out3.face);
689 graph_draw<T>(
"LineInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
695 const char *spec = R
"(10 1 2
722 graph_draw<T>(
"LineHoleInSquare - constraints", out2.vert, out2.edge, out2.face);
728 graph_draw<T>(
"LineHoleInSquare - inside with holes", out3.vert, out3.edge, out3.face);
734 graph_draw<T>(
"LineHoleInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
740 const char *spec = R
"(12 0 3
769 graph_draw<T>(
"NestedHoles - constraints", out2.vert, out2.edge, out2.face);
788 EXPECT_TRUE((f_inner_a != -1 && f_inner_b != -1) || (f_inner_c != -1 && f_inner_d != -1));
790 bool found_face_2 =
false;
791 for (
int f = 0; f < int(out3.face.size()); f++) {
800 graph_draw<T>(
"NestedHoles - inside with holes", out3.vert, out3.edge, out3.face);
806 graph_draw<T>(
"NestedHoles - valid bmesh with holes", out4.vert, out4.edge, out4.face);
815 const char *spec = R
"(20 0 5
854 for (
int k = 0; k < 4; k++) {
865 bool found_inner_id =
false;
866 for (
int f = 0; f < int(
out.face.size()); f++) {
868 found_inner_id =
true;
877 bool found_ring2_face =
false;
878 for (
int f = 0; f < int(
out.face.size()); f++) {
880 found_ring2_face =
true;
908 const char *spec = R
"(8 0 2
936 for (
int f = 0; f < int(
out.face.size()); f++) {
957 const char *spec = R
"(8 0 3
995 graph_draw<T>(
"EvenOddCoincidentPolygonsNeedIdsStable - even-odd",
999 graph_draw<T>(
"EvenOddCoincidentPolygonsNeedIdsStable - non-zero",
1013 const char *spec = R
"(8 0 2
1039 for (
const int f : out_ccw_ids.
face.index_range()) {
1043 for (
const int f : out_cw_ids.
face.index_range()) {
1055 const char *spec = R
"(6 0 1
1062 0 1 2 3 4 5 0 1 2 3 4 5
1078 const char *spec = R
"(6 0 1
1085 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
1087 InputStorage<T> store;
1102 const char *spec = R
"(10 0 2
1114 4 5 6 7 8 9 4 5 6 7 8 9
1116 InputStorage<T> store;
1130 const char *spec = R
"(10 0 2
1142 4 5 6 7 8 9 4 5 6 7 8 9 4 5 6 7 8 9
1155 const char *spec = R
"(6 0 2
1174 for (
int i = 0; i < 6; i++) {
1205 const char *spec = R
"(8 0 2
1226 "NonZeroWinding - even-odd", out_evenodd.vert, out_evenodd.edge, out_evenodd.face);
1234 "NonZeroWinding - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
1243 Vector<int> indices_flipped = store.face_vert_indices;
1244 for (
const int i :
in.face_offsets.index_range()) {
1245 std::ranges::reverse(indices_flipped.as_mutable_span().slice(
in.face_offsets[i]));
1250 EXPECT_EQ(out_flipped.vert.size(), out_nonzero.vert.size());
1251 EXPECT_EQ(out_flipped.face.size(), out_nonzero.face.size());
1260 const char *spec_hole = R
"(8 0 2
1278 EXPECT_EQ(out_evenodd_hole.vert.size(), 8);
1280 graph_draw<T>(
"NonZeroWindingNested - even-odd, inner CW (hole)",
1281 out_evenodd_hole.vert,
1282 out_evenodd_hole.edge,
1283 out_evenodd_hole.face);
1288 EXPECT_EQ(out_nonzero_hole.vert.size(), 8);
1290 graph_draw<T>(
"NonZeroWindingNested - non-zero, inner CW (hole)",
1291 out_nonzero_hole.vert,
1292 out_nonzero_hole.edge,
1293 out_nonzero_hole.face);
1297 EXPECT_EQ(out_evenodd_hole.face.size(), 8);
1298 EXPECT_EQ(out_nonzero_hole.face.size(), out_evenodd_hole.face.size());
1301 const char *spec_filled = R
"(8 0 2
1319 EXPECT_EQ(out_evenodd_filled.vert.size(), 8);
1321 graph_draw<T>(
"NonZeroWindingNested - even-odd, inner CCW (hole)",
1322 out_evenodd_filled.vert,
1323 out_evenodd_filled.edge,
1324 out_evenodd_filled.face);
1329 EXPECT_EQ(out_nonzero_filled.vert.size(), 8);
1331 graph_draw<T>(
"NonZeroWindingNested - non-zero, inner CCW (filled)",
1332 out_nonzero_filled.vert,
1333 out_nonzero_filled.edge,
1334 out_nonzero_filled.face);
1338 EXPECT_EQ(out_evenodd_filled.face.size(), 8);
1339 EXPECT_EQ(out_nonzero_filled.face.size(), 10);
1384 const char *spec = R
"(16 0 4
1474 const char *spec = R
"(8 0 3
1488 InputStorage<T> store;
1527 for (CDT_result<T> *out_p : {&out_evenodd, &out_nonzero}) {
1530 for (
int i = 0; i < 8; i++) {
1543 if (out_p == &out_evenodd) {
1583 const char *spec = R
"(8 0 3
1602 graph_draw<T>(
"NonZeroWindingMultiFaceEdgeMixed - even-odd",
1639 for (CDT_result<T> *out_p : {&out_evenodd, &out_nonzero}) {
1640 CDT_result<T> &
out = *out_p;
1642 for (
int i = 0; i < 8; i++) {
1703 const char *spec = R
"(10 0 4
1781 const char *spec = R
"(14 0 6
1865 const char *spec = R
"(5 0 4
1877 InputStorage<T> store;
1883 "NonZeroWindingFan - even-odd", out_evenodd.vert, out_evenodd.edge, out_evenodd.face);
1889 "NonZeroWindingFan - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
1928 const char *spec = R
"(8 0 2
1941 InputStorage<T> store;
1967 EXPECT_LT(out_evenodd.face.size(), out_nonzero.
face.size());
2000 const char *spec = R
"(4 0 1
2039 for (
int i = 0; i < 4; i++) {
2047 for (
int i = 0; i < int(out_evenodd.
vert.size()); i++) {
2048 if (!
ELEM(i, verts[0], verts[1], verts[2], verts[3])) {
2059 if (top_lobe == -1) {
2063 if (bot_lobe == -1) {
2103 const char *spec = R
"(20 0 5
2137 "NonZeroWindingDeepNest - even-odd", out_evenodd.
vert, out_evenodd.
edge, out_evenodd.
face);
2143 "NonZeroWindingDeepNest - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
2154 EXPECT_EQ(out_evenodd.
face.size(), out_nonzero.face.size());
2185 const char *spec = R
"(12 0 3
2229 EXPECT_NE(out_evenodd.
face.size(), out_nonzero.face.size());
2265 const char *spec = R
"(12 0 3
2310 EXPECT_EQ(out_evenodd.
face.size(), out_nonzero.face.size());
2345 const char *spec = R
"(6 0 2
2409 const char *spec = R
"(20 0 5
2462 EXPECT_EQ(out_evenodd.
face.size(), out_nonzero.face.size());
2498 const char *spec = R
"(8 0 3
2537 EXPECT_LT(out_evenodd.
face.size(), out_nonzero.face.size());
2564 const char *spec = R
"(8 0 2
2603 EXPECT_LT(out_evenodd.
face.size(), out_nonzero.face.size());
2640 const char *spec = R
"(5 0 3
2682 EXPECT_LT(out_evenodd.
face.size(), out_nonzero.face.size());
2698 const char *spec = R
"(6 0 1
2720 const char *spec = R
"(4 2 0
2728 InputStorage<T> store;
2738 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
2739 if (
out.vert.size() == 5) {
2740 int v_intersect = -1;
2741 for (
int i = 0; i < 5; i++) {
2742 if (!
ELEM(i, v0_out, v1_out, v2_out, v3_out)) {
2748 if (v_intersect != -1) {
2760 const char *spec = R
"(5 1 1
2780 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1 && v4_out != -1);
2781 if (
out.face.size() == 3) {
2790 if (fe1a_out != 0 && fe1b_out != 0) {
2795 out.edge_orig[fe1a_out][0] == face0_edge1);
2797 out.edge_orig[fe1b_out][0] == face0_edge1);
2813 const char *spec = R
"(7 5 0
2840 const char *spec = R
"(12 9 0
2863 InputStorage<T> store;
2869 if (
out.vert.size() == 8 &&
out.edge.size() == 15 &&
out.face.size() == 8) {
2871 for (
int i = 0; i < 12; ++i) {
2880 for (
int i = 0; i < 8; ++i) {
2889 EXPECT_TRUE(e_cross_1 != -1 && e_cross_2 != -1 && e_cross_3 != -1);
2902 const char *spec = R
"(27 21 0
2965 const char *spec = R
"(6 0 2
2981 if (
out.vert.size() == 6 &&
out.edge.size() == 9 &&
out.face.size() == 4) {
2983 for (
int i = 0; i < 6; i++) {
3010 const char *spec = R
"(6 0 2
3026 if (
out.vert.size() == 10 &&
out.edge.size() == 18 &&
out.face.size() == 9) {
3028 for (
int i = 0; i < 6; i++) {
3086 const char *spec = R
"(12 0 3
3109 if (
out.vert.size() == 14 &&
out.edge.size() == 33 &&
out.face.size() == 20) {
3111 for (
int i = 0; i < 12; i++) {
3149 graph_draw<T>(
"OverlapFaces - inside", out2.vert, out2.edge, out2.face);
3173 graph_draw<T>(
"OverlapFaces - valid bmesh with holes", out6.vert, out6.edge, out6.face);
3179 const char *spec = R
"(8 0 2
3204 const char *spec = R
"(6 0 2
3220 if (
out.vert.size() == 5 &&
out.edge.size() == 7 &&
out.face.size() == 3) {
3223 for (
int i = 0; i < 6; i++) {
3266 const char *spec = R
"(6 0 2
3289 const char *spec = R
"(8 0 2
3294 0.14644660940672627 0.5
3295 0.5 0.14644660940672627
3296 0.8535533905932737 0.5
3297 0.5 0.8535533905932737
3314 const char *spec = R
"(8 8 0
3319 0.14644660940672627 0.5
3320 0.5 0.14644660940672627
3321 0.8535533905932737 0.5
3322 0.5 0.8535533905932737
3345 const char *spec = R
"(5 3 0
3355 InputStorage<T> store;
3366 const char *spec = R
"(3 0 2
3411 const char *spec = R
"(7 0 2
3437 "SharedSplitBoundary - even-odd", out_evenodd.vert, out_evenodd.edge, out_evenodd.face);
3439 "SharedSplitBoundary - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
3445 const char *spec = R
"(8 0 2
3462 graph_draw<T>(
"Square O - inside with holes", out1.vert, out1.edge, out1.face);
3468 graph_draw<T>(
"Square O - valid bmesh with holes", out2.vert, out2.edge, out2.face);
3482 const char *spec = R
"(15 0 3
3514 for (
const int i :
in.face_offsets.index_range()) {
3515 store.face_vert_indices.as_mutable_span().slice(
in.face_offsets[i]).reverse();
3518 EXPECT_EQ(out_reversed.vert.size(), 15);
3519 EXPECT_EQ(out_reversed.edge.size(), 18);
3523 "FillCurveLetterB - reversed", out_reversed.vert, out_reversed.edge, out_reversed.face);
3535 const int grid_size = 10;
3536 const int cells_num = grid_size - 1;
3537 const int boundary_num = 4 * grid_size - 4;
3538 const int interior_faces_num = cells_num * cells_num;
3539 const int verts_num = boundary_num + 2 * interior_faces_num;
3540 const int faces_num = 1 + interior_faces_num;
3541 const double min = -0.5;
3542 const double max = 0.5;
3543 const double step = 1.0 / double(cells_num);
3545 Array<VecBase<T, 2>> verts(verts_num);
3546 Array<Vector<int>> faces(faces_num);
3549 auto add_vert = [&](
const double x,
const double y) {
3550 verts[vert_index++] = VecBase<T, 2>(
T(
x),
T(
y));
3553 for (
int i = 0; i < grid_size; i++) {
3556 for (
int i = 1; i < grid_size; i++) {
3559 for (
int i = 1; i < grid_size; i++) {
3562 for (
int i = 1; i < grid_size - 1; i++) {
3565 for (
int i = 0; i < boundary_num; i++) {
3570 for (
int x = 0;
x < cells_num;
x++) {
3571 for (
int y = 0;
y < cells_num;
y++) {
3572 const double cx =
min + (
x + 0.5) *
step;
3573 const double cy =
min + (
y + 0.5) *
step;
3574 const int first_vert = vert_index;
3577 faces[face_index].append(first_vert);
3578 faces[face_index].append(first_vert + 1);
3586 Vector<int> face_offsets;
3587 Vector<int> face_vert_offsets;
3588 for (
const int i : faces.index_range()) {
3589 face_offsets.append(face_vert_offsets.size());
3590 face_vert_offsets.extend(faces[i]);
3592 face_offsets.append(face_vert_offsets.size());
3596 in.face_offsets = OffsetIndices<int>(face_offsets);
3597 in.face_vert_indices = face_vert_offsets;
3598 in.epsilon =
T(0.00001);
3622 const char *spec = R
"(8 0 1
3653 const char *spec = R
"(9 0 1
3682 const char *spec = R
"(9 0 1
3706 const char *spec = R
"(9 0 1
3714 -0.260009 -0.0515187
3727 const char *spec = R
"(4 2 0
3748 const char *spec = R
"(8 0 2
3774TEST(delaunay_d, Empty)
3779TEST(delaunay_d, OnePt)
3784TEST(delaunay_d, TwoPt)
3789TEST(delaunay_d, ThreePt)
3794TEST(delaunay_d, MixedPts)
3799TEST(delaunay_d, Quad0)
3804TEST(delaunay_d, Quad1)
3809TEST(delaunay_d, Quad2)
3814TEST(delaunay_d, Quad3)
3819TEST(delaunay_d, Quad4)
3824TEST(delaunay_d, LineInSquare)
3829TEST(delaunay_d, LineHoleInSquare)
3834TEST(delaunay_d, NestedHoles)
3839TEST(delaunay_d, EvenOddNestedHolesDeep)
3844TEST(delaunay_d, EvenOddBoundaryDisagreement)
3849TEST(delaunay_d, EvenOddCoincidentPolygonsNeedIdsStable)
3854TEST(delaunay_d, CwOrigFaceIds)
3859TEST(delaunay_d, NonZeroWinding)
3864TEST(delaunay_d, NonZeroWindingNested)
3869TEST(delaunay_d, NonZeroWindingNestedUnion)
3874TEST(delaunay_d, NonZeroWindingMultiFaceEdge)
3879TEST(delaunay_d, NonZeroWindingMultiFaceEdgeMixed)
3884TEST(delaunay_d, NonZeroWindingCancelToZero)
3889TEST(delaunay_d, NonZeroWindingHighCount)
3894TEST(delaunay_d, NonZeroWindingFan)
3899TEST(delaunay_d, NonZeroWindingEdgeSplit)
3904TEST(delaunay_d, NonZeroWindingSelfIntersect)
3909TEST(delaunay_d, NonZeroWindingDeepNest)
3914TEST(delaunay_d, NonZeroWindingSharedSubsegment)
3919TEST(delaunay_d, NonZeroWindingIslandInHole)
3924TEST(delaunay_d, NonZeroWindingCoincidentVerts)
3929TEST(delaunay_d, NonZeroWindingManyCrossings)
3934TEST(delaunay_d, NonZeroWindingNegativeOnly)
3939TEST(delaunay_d, NonZeroWindingTJunction)
3944TEST(delaunay_d, NonZeroWindingExactSharedEdge)
3949TEST(delaunay_d, NonZeroWindingConcaveOuter)
3954TEST(delaunay_d, CrossSegs)
3959TEST(delaunay_d, CutAcrossTri)
3964TEST(delaunay_d, DiamondCross)
3969TEST(delaunay_d, TwoDiamondsCross)
3974TEST(delaunay_d, ManyCross)
3979TEST(delaunay_d, TwoFace)
3984TEST(delaunay_d, TwoFace2)
3989TEST(delaunay_d, OverlapFaces)
3994TEST(delaunay_d, TwoSquaresOverlap)
3999TEST(delaunay_d, TwoFaceEdgeOverlap)
4004TEST(delaunay_d, TriInTri)
4009TEST(delaunay_d, DiamondInSquare)
4014TEST(delaunay_d, DiamondInSquareWire)
4019TEST(delaunay_d, LoopingBack2x)
4024TEST(delaunay_d, LoopingBack3x)
4029TEST(delaunay_d, LoopingBackHole2x)
4034TEST(delaunay_d, LoopingBackHole3x)
4039TEST(delaunay_d, DisjointPolysInLargeHull)
4044TEST(delaunay_d, RepeatEdge)
4049TEST(delaunay_d, RepeatTri)
4054TEST(delaunay_d, SharedSplitBoundary)
4059TEST(delaunay_d, SquareO)
4064TEST(delaunay_d, FillCurveLetterB)
4069TEST(delaunay_d, FillCurveDegenerateInteriorFaces)
4074TEST(delaunay_d, DissolvePendantEdgeFace)
4079TEST(delaunay_d, StaleSymedgeBeforeRemoveFacesInHoles)
4084TEST(delaunay_d, FuzzReproMinimize1)
4089TEST(delaunay_d, FuzzReproMinimize2)
4094TEST(delaunay_d, IntersectionSimpleEdgeIds)
4099TEST(delaunay_d, IntersectionSquaresEdgeIds)
4105TEST(delaunay_m, Empty)
4110TEST(delaunay_m, OnePt)
4114TEST(delaunay_m, TwoPt)
4119TEST(delaunay_m, ThreePt)
4124TEST(delaunay_m, MixedPts)
4129TEST(delaunay_m, Quad0)
4134TEST(delaunay_m, Quad1)
4139TEST(delaunay_m, Quad2)
4144TEST(delaunay_m, Quad3)
4149TEST(delaunay_m, Quad4)
4154TEST(delaunay_m, LineInSquare)
4159TEST(delaunay_m, DisjointPolysInLargeHull)
4164TEST(delaunay_m, LineHoleInSquare)
4169TEST(delaunay_m, NestedHoles)
4174TEST(delaunay_m, EvenOddNestedHolesDeep)
4179TEST(delaunay_m, EvenOddBoundaryDisagreement)
4184TEST(delaunay_m, EvenOddCoincidentPolygonsNeedIdsStable)
4189TEST(delaunay_m, CwOrigFaceIds)
4194TEST(delaunay_m, NonZeroWinding)
4199TEST(delaunay_m, NonZeroWindingNested)
4204TEST(delaunay_m, NonZeroWindingNestedUnion)
4209TEST(delaunay_m, NonZeroWindingMultiFaceEdge)
4214TEST(delaunay_m, NonZeroWindingMultiFaceEdgeMixed)
4219TEST(delaunay_m, NonZeroWindingCancelToZero)
4224TEST(delaunay_m, NonZeroWindingHighCount)
4229TEST(delaunay_m, NonZeroWindingFan)
4234TEST(delaunay_m, NonZeroWindingEdgeSplit)
4239TEST(delaunay_m, NonZeroWindingSelfIntersect)
4244TEST(delaunay_m, NonZeroWindingDeepNest)
4249TEST(delaunay_m, NonZeroWindingSharedSubsegment)
4254TEST(delaunay_m, NonZeroWindingIslandInHole)
4259TEST(delaunay_m, NonZeroWindingCoincidentVerts)
4264TEST(delaunay_m, NonZeroWindingManyCrossings)
4269TEST(delaunay_m, NonZeroWindingNegativeOnly)
4274TEST(delaunay_m, NonZeroWindingTJunction)
4279TEST(delaunay_m, NonZeroWindingExactSharedEdge)
4284TEST(delaunay_m, NonZeroWindingConcaveOuter)
4289TEST(delaunay_m, CrossSegs)
4294TEST(delaunay_m, CutAcrossTri)
4299TEST(delaunay_m, DiamondCross)
4304TEST(delaunay_m, TwoDiamondsCross)
4309TEST(delaunay_m, ManyCross)
4314TEST(delaunay_m, TwoFace)
4319TEST(delaunay_m, TwoFace2)
4324TEST(delaunay_m, OverlapFaces)
4329TEST(delaunay_m, TwoSquaresOverlap)
4334TEST(delaunay_m, TwoFaceEdgeOverlap)
4339TEST(delaunay_m, TriInTri)
4344TEST(delaunay_m, DiamondInSquare)
4349TEST(delaunay_m, DiamondInSquareWire)
4354TEST(delaunay_m, LoopingBack2x)
4359TEST(delaunay_m, LoopingBack3x)
4364TEST(delaunay_m, LoopingBackHole2x)
4369TEST(delaunay_m, LoopingBackHole3x)
4374TEST(delaunay_m, RepeatEdge)
4379TEST(delaunay_m, RepeatTri)
4384TEST(delaunay_m, SharedSplitBoundary)
4389TEST(delaunay_m, IntersectionSimpleEdgeIds)
4394TEST(delaunay_m, IntersectionSquaresEdgeIds)
4399TEST(delaunay_m, FillCurveLetterB)
4408void text_test(
int arc_points_num,
4409 int lets_per_line_num,
4415 constexpr bool print_timing =
true;
4438 const char *b_before_arcs = R
"(13 0 3
4459 constexpr int narcs = 4;
4460 int b_npts = b_store.vert.size() + narcs * arc_points_num;
4461 constexpr int b_nfaces = 3;
4462 Array<VecBase<T, 2>> b_vert(b_npts);
4463 Array<Vector<int>> b_face(b_nfaces);
4464 std::copy(b_store.vert.begin(), b_store.vert.end(), b_vert.begin());
4466 IndexRange fspan = b_before_arcs_in.face_offsets[f];
4467 b_face[f] = Vector<int>(fspan.size());
4468 for (
const int i : fspan.index_range()) {
4469 b_face[f][i] = b_before_arcs_in.face_vert_indices[fspan[i]];
4472 if (arc_points_num > 0) {
4473 b_face[0].pop_last();
4474 for (
int arc = 0; arc < narcs; ++arc) {
4475 int arc_origin_vert;
4476 int arc_terminal_vert;
4480 arc_origin_vert = 1;
4481 arc_terminal_vert = 2;
4485 arc_origin_vert = 2;
4486 arc_terminal_vert = 3;
4490 arc_origin_vert = 7;
4491 arc_terminal_vert = 6;
4495 arc_origin_vert = 11;
4496 arc_terminal_vert = 10;
4503 VecBase<T, 2> start_co = b_vert[arc_origin_vert];
4504 VecBase<T, 2> end_co = b_vert[arc_terminal_vert];
4505 VecBase<T, 2> center_co = 0.5 * (start_co + end_co);
4508 double angle_delta =
M_PI / (arc_points_num + 1);
4509 int start_vert = b_before_arcs_in.vert.size() + arc * arc_points_num;
4510 Vector<int> &face = b_face[(arc <= 1) ? 0 : arc - 1];
4511 for (
int i = 0; i < arc_points_num; ++i) {
4512 VecBase<T, 2> delta;
4513 float ang = ccw ? (-
M_PI_2 + (i + 1) * angle_delta) : (
M_PI_2 - (i + 1) * angle_delta);
4514 delta[0] =
T(radius *
cos(ang));
4515 delta[1] =
T(radius *
sin(ang));
4516 b_vert[start_vert + i] = center_co + delta;
4517 face.append(start_vert + i);
4520 face.append(arc_terminal_vert);
4526 int tot_instances = lets_per_line_num * lines_num;
4528 int b_tot_face_verts = b_face[0].size() + b_face[1].size() + b_face[2].size();
4529 int tot_face_verts = tot_instances * b_tot_face_verts + (
invert ? 4 : 0);
4530 int tot_faces = tot_instances * b_nfaces + (
invert ? 1 : 0);
4531 store.vert.reinitialize(tot_face_verts);
4532 store.face_offsets.reinitialize(tot_faces + 1);
4533 store.face_vert_indices.reinitialize(tot_face_verts);
4538 T delta_y =
T(3.25);
4540 store.face_offsets[0] = 0;
4541 for (
int line = 0; line < lines_num; ++line) {
4542 for (
int let = 0; let < lets_per_line_num; ++let) {
4543 VecBase<T, 2> co_offset(cur_x, cur_y);
4544 int in_v_offset = instance * b_vert.size();
4545 for (
const int v : b_vert.index_range()) {
4546 store.vert[in_v_offset +
v] = b_vert[
v] + co_offset;
4549 const int inst_off = instance * b_nfaces;
4550 const int fsize = b_face[f].size();
4551 const int foff_start = store.face_offsets[inst_off + f];
4552 store.face_offsets[inst_off + f + 1] = foff_start + fsize;
4553 for (
int i = store.face_offsets[inst_off + f]; i < store.face_offsets[inst_off + f + 1];
4556 store.face_vert_indices[i] = b_face[f][i - store.face_offsets[inst_off + f]] +
4567 for (
const int f :
IndexRange(tot_faces - 1)) {
4568 const int fstart = store.face_offsets[f];
4569 const int fend = store.face_offsets[f + 1];
4570 std::reverse(store.face_vert_indices.begin() + fstart,
4571 store.face_vert_indices.begin() + fend);
4573 constexpr double margin = 0.25;
4574 T xmin =
T(-margin);
4575 T ymin =
T(-margin);
4576 T xmax =
T(lets_per_line_num * delta_x + margin);
4577 T ymax =
T(lines_num * delta_y + margin);
4578 const int rect_base = tot_face_verts - 4;
4579 store.vert[rect_base] = VecBase<T, 2>(xmin, ymin);
4580 store.vert[rect_base + 1] = VecBase<T, 2>(xmax, ymin);
4581 store.vert[rect_base + 2] = VecBase<T, 2>(xmax, ymax);
4582 store.vert[rect_base + 3] = VecBase<T, 2>(xmin, ymax);
4583 store.face_vert_indices[tot_face_verts - 4] = rect_base;
4584 store.face_vert_indices[tot_face_verts - 3] = rect_base + 1;
4585 store.face_vert_indices[tot_face_verts - 2] = rect_base + 2;
4586 store.face_vert_indices[tot_face_verts - 1] = rect_base + 3;
4587 store.face_offsets[tot_faces] = store.face_offsets[tot_faces - 1] + 4;
4592 in.face_offsets = store.face_offsets.as_span();
4593 in.face_vert_indices = store.face_vert_indices;
4594 in.edge = store.edge;
4595 in.epsilon = b_before_arcs_in.epsilon;
4596 in.needed_ids = needed_ids;
4601 std::cout <<
"time = " << tend - tstart <<
"\n";
4603 if (needed_ids == 0) {
4609 std::string label =
"Text arcpts=" + std::to_string(arc_points_num);
4610 if (lets_per_line_num > 1) {
4611 label +=
" linelen=" + std::to_string(lets_per_line_num);
4613 if (lines_num > 1) {
4614 label +=
" lines=" + std::to_string(lines_num);
4616 if (needed_ids == 0) {
4620 label +=
" otype=" + std::to_string(otype);
4631TEST(delaunay_d, TextB1)
4636TEST(delaunay_d, TextB10)
4641TEST(delaunay_d, TextB10_noids)
4646TEST(delaunay_d, TextB10_inside)
4648 text_test<double>(10, 1, 1,
CDT_INSIDE, need_vef_ids,
false);
4651TEST(delaunay_d, TextB10_inside_noids)
4656TEST(delaunay_d, TextB10_constraints)
4661TEST(delaunay_d, TextB10_constraints_noids)
4666TEST(delaunay_d, TextB10_constraints_valid_bmesh)
4671TEST(delaunay_d, TextB10_constraints_valid_bmesh_noids)
4676TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes)
4681TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes_noids)
4686TEST(delaunay_d, TextB200)
4691TEST(delaunay_d, TextB10_10_10)
4696TEST(delaunay_d, TextB10_10_10_noids)
4701TEST(delaunay_d, TextB1_inverted)
4708TEST(delaunay_d, TextB10_inverted)
4713TEST(delaunay_d, TextB10_inverted_nonzero)
4718TEST(delaunay_d, TextB10_10_10_inverted_noids)
4723TEST(delaunay_d, TextB10_20_20_inverted)
4729TEST(delaunay_m, TextB10)
4734TEST(delaunay_m, TextB200)
4739TEST(delaunay_m, TextB10_10_10)
4744TEST(delaunay_m, TextB10_10_10_noids)
4759 RANDOM_TRI_BETWEEN_CIRCLES,
4763void rand_delaunay_test(
int test_kind,
4770 constexpr bool print_timing =
true;
4772 Array<double> times(max_lg_size + 1);
4775 for (
int lg_size = start_lg_size; lg_size <= max_lg_size; ++lg_size) {
4776 int size = 1 << lg_size;
4777 times[lg_size] = 0.0;
4778 if (size == 1 && test_kind != RANDOM_PTS) {
4782 for (
int rep = 0; rep < reps_per_size; ++rep) {
4787 std::string test_label;
4788 switch (test_kind) {
4791 test_label = std::to_string(npts) +
"Random points";
4797 test_label = std::to_string(nedges) +
"Random edges";
4803 test_label =
"Random poly with " + std::to_string(nedges) +
" edges";
4806 case RANDOM_TILTED_GRID: {
4816 test_label =
"Tilted grid " + std::to_string(npts) +
"x" + std::to_string(npts) +
4817 " (tilt=" + std::to_string(param) +
")";
4820 case RANDOM_CIRCLE: {
4826 test_label =
"Circle with " + std::to_string(npts) +
" points";
4829 case RANDOM_TRI_BETWEEN_CIRCLES: {
4836 test_label =
"Random " + std::to_string(nfaces) +
4837 " triangles between circles (inner radius=" + std::to_string(param) +
")";
4841 std::cout <<
"unknown delaunay test type\n";
4847 test_label +=
" (inside)";
4850 test_label +=
" (constraints)";
4853 test_label +=
" (valid bmesh)";
4858 store.
vert.reinitialize(npts);
4860 store.edge.reinitialize(nedges);
4863 store.face_offsets.reinitialize(nfaces + 1);
4867 switch (test_kind) {
4871 for (
int i = 0; i <
size; i++) {
4874 if (test_kind != RANDOM_PTS) {
4876 store.edge[i - 1][0] = i - 1;
4877 store.edge[i - 1][1] = i;
4881 if (test_kind == RANDOM_POLY) {
4882 store.edge[
size - 1][0] =
size - 1;
4883 store.edge[
size - 1][1] = 0;
4887 case RANDOM_TILTED_GRID: {
4888 for (
int i = 0; i <
size; ++i) {
4889 for (
int j = 0; j <
size; ++j) {
4890 store.vert[i *
size + j][0] =
T(i * param + j);
4891 store.vert[i *
size + j][1] =
T(i);
4894 for (
int i = 0; i <
size; ++i) {
4896 store.edge[i][0] = i *
size;
4897 store.edge[i][1] = i *
size +
size - 1;
4899 store.edge[
size + i][0] = i;
4900 store.edge[
size + i][1] = (
size - 1) * size + i;
4904 case RANDOM_CIRCLE: {
4906 double angle_delta = 2.0 *
M_PI /
size;
4907 store.face_vert_indices.reinitialize(size);
4908 for (
int i = 0; i <
size; i++) {
4909 store.vert[i][0] =
T(
cos(start_angle + i * angle_delta));
4910 store.vert[i][1] =
T(
sin(start_angle + i * angle_delta));
4911 store.face_vert_indices[i] = i;
4913 store.face_offsets[0] = 0;
4914 store.face_offsets[1] =
size;
4917 case RANDOM_TRI_BETWEEN_CIRCLES: {
4918 store.face_vert_indices.reinitialize(3 * size);
4919 store.face_offsets[0] = 0;
4920 for (
int i = 0; i <
size; i++) {
4928 store.vert[ia][0] =
T(
cos(angle1));
4929 store.vert[ia][1] =
T(
sin(angle1));
4930 store.vert[ib][0] =
T(
cos(angle2));
4931 store.vert[ib][1] =
T(
sin(angle2));
4932 store.vert[ic][0] =
T((param *
cos(angle3)));
4933 store.vert[ic][1] =
T((param *
sin(angle3)));
4935 store.face_vert_indices[ia] = ia;
4936 int orient =
orient2d(store.vert[ia], store.vert[ib], store.vert[ic]);
4937 store.face_vert_indices[ib] = orient >= 0 ? ib : ic;
4938 store.face_vert_indices[ic] = orient >= 0 ? ic : ib;
4939 store.face_offsets[i + 1] = store.face_offsets[i] + 3;
4947 in.edge = store.edge;
4948 in.face_offsets = store.face_offsets.as_span();
4949 in.face_vert_indices = store.face_vert_indices;
4951 in.needed_ids = need_vef_ids;
4964 std::cout <<
"\nsize,time\n";
4965 for (
int lg_size = 0; lg_size <= max_lg_size; lg_size++) {
4966 int size = 1 << lg_size;
4967 std::cout <<
size <<
"," << times[lg_size] <<
"\n";
4973TEST(delaunay_d, RandomPts)
4975 rand_delaunay_test<double>(RANDOM_PTS, 0, 7, 1, 0.0,
CDT_FULL);
4978TEST(delaunay_d, RandomSegs)
4980 rand_delaunay_test<double>(RANDOM_SEGS, 1, 7, 1, 0.0,
CDT_FULL);
4983TEST(delaunay_d, RandomPoly)
4985 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_FULL);
4988TEST(delaunay_d, RandomPolyConstraints)
4990 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_CONSTRAINTS);
4993TEST(delaunay_d, RandomPolyValidBmesh)
4998TEST(delaunay_d, Grid)
5000 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0,
CDT_FULL);
5003TEST(delaunay_d, TiltedGridA)
5005 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0,
CDT_FULL);
5008TEST(delaunay_d, TiltedGridB)
5010 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01,
CDT_FULL);
5013TEST(delaunay_d, RandomCircle)
5015 rand_delaunay_test<double>(RANDOM_CIRCLE, 1, 7, 1, 0.0,
CDT_FULL);
5018TEST(delaunay_d, RandomTrisCircle)
5020 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25,
CDT_FULL);
5023TEST(delaunay_d, RandomTrisCircleB)
5025 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1
e-4,
CDT_FULL);
5029TEST(delaunay_m, RandomPts)
5031 rand_delaunay_test<mpq_class>(RANDOM_PTS, 0, 7, 1, 0.0,
CDT_FULL);
5034TEST(delaunay_m, RandomSegs)
5036 rand_delaunay_test<mpq_class>(RANDOM_SEGS, 1, 7, 1, 0.0,
CDT_FULL);
5039TEST(delaunay_m, RandomPoly)
5041 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_FULL);
5044TEST(delaunay_d, RandomPolyInside)
5046 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_INSIDE);
5049TEST(delaunay_m, RandomPolyInside)
5051 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_INSIDE);
5054TEST(delaunay_m, RandomPolyConstraints)
5056 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_CONSTRAINTS);
5059TEST(delaunay_m, RandomPolyValidBmesh)
5064TEST(delaunay_m, Grid)
5066 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0,
CDT_FULL);
5069TEST(delaunay_m, TiltedGridA)
5071 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0,
CDT_FULL);
5074TEST(delaunay_m, TiltedGridB)
5076 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01,
CDT_FULL);
5079TEST(delaunay_m, RandomCircle)
5081 rand_delaunay_test<mpq_class>(RANDOM_CIRCLE, 1, 7, 1, 0.0,
CDT_FULL);
5084TEST(delaunay_m, RandomTrisCircle)
5086 rand_delaunay_test<mpq_class>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25,
CDT_FULL);
5089TEST(delaunay_m, RandomTrisCircleB)
5091 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1
e-4,
CDT_FULL);
Math vector functions needed specifically for mesh intersect and boolean.
Platform independent time functions.
Read Blender memory allocation and freeing.
Span< T > as_span() const
const T & last(const int64_t n=0) const
void reinitialize(const int64_t new_size)
constexpr IndexRange()=default
void append(const T &value)
Array< Vector< int > > face
Array< Vector< uint32_t > > vert_orig
Array< Vector< uint32_t > > face_orig
Array< VecBase< T, 2 > > vert
Array< Vector< uint32_t > > edge_orig
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
float2x2 invert(float2x2 mat)
float3x3 scale(float3x3 mat, float2 scale)
#define EXPECT_FALSE(result)
#define EXPECT_LT(result, expect)
#define EXPECT_GE(result, expect)
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define EXPECT_EQ(result, expect)
#define EXPECT_NEAR(result, expect, threshold)
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
int size(const AssetLibraryReference *library_reference)
static int get_orig_index(const Span< Vector< uint32_t > > out_to_orig, int orig_index)
void expect_coord_near(const VecBase< T, 2 > &testco, const VecBase< T, 2 > &refco)
void nonzero_winding_nested_test()
void fill_curve_degenerate_interior_faces_test()
void intersection_simple_edge_ids_test()
void looping_back_2x_test()
bool output_vert_is_intersection_and_has_edge_input_ids(const CDT_result< T > &out, int out_vert_index, int in_edge1_index, int in_edge2_index)
void stale_symedge_before_remove_faces_in_holes_test()
void looping_back_hole_3x_test()
int get_output_edge_index(const CDT_result< T > &out, int out_index_1, int out_index_2)
void fill_curve_letter_b_test()
void nonzero_winding_deep_nest_test()
void diamondinsquare_test()
void graph_draw(const std::string &label, const Span< VecBase< T, 2 > > verts, const Span< int2 > edges, const Span< Vector< int > > faces)
void nonzero_winding_exact_shared_edge_test()
void even_odd_nested_holes_deep_test()
void intersection_squares_edge_ids_test()
void disjoint_polys_in_large_hull_test()
void shared_split_boundary_test()
void fuzz_repro_minimize_test1()
void nonzero_winding_cancel_to_zero_test()
void diamondinsquarewire_test()
void looping_back_3x_test()
void fuzz_repro_minimize_test2()
void nonzero_winding_coincident_verts_test()
void nonzero_winding_nested_union_test()
void nonzero_winding_negative_only_test()
void looping_back_hole_2x_test()
void nonzero_winding_concave_outer_test()
void nonzero_winding_multi_face_edge_test()
void nonzero_winding_high_count_test()
void even_odd_coincident_polygons_needed_ids_stable_test()
int get_output_tri_index(const CDT_result< T > &out, int out_index_1, int out_index_2, int out_index_3)
void nonzero_winding_island_in_hole_test()
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
int get_vertex_by_coord(const CDT_result< T > &out, double x, double y)
void nonzero_winding_shared_subsegment_test()
void twosquaresoverlap_test()
void nonzero_winding_edge_split_test()
CDT_input< T > fill_input_from_string(const char *spec, InputStorage< T > &r_storage)
void nonzero_winding_fan_test()
void nonzero_winding_multi_face_edge_mixed_test()
void even_odd_boundary_disagreement_test()
void nonzero_winding_many_crossings_test()
void lineholeinsquare_test()
bool output_face_has_input_id(const CDT_result< T > &out, int out_face_index, uint32_t in_face_index)
double math_to_double(const T)
CDT_result< T > delaunay_2d_calc(const CDT_input< T > &input, CDT_output_type output_type)
void cw_orig_face_ids_test()
void nonzero_winding_test()
void nonzero_winding_tjunction_test()
void twodiamondscross_test()
void dissolve_pendant_edge_face_test()
int get_output_face_index(const CDT_result< T > &out, const Array< int > &poly)
void twofaceedgeoverlap_test()
bool output_edge_has_input_id(const CDT_result< T > &out, int out_edge_index, uint32_t in_edge_index)
void nonzero_winding_self_intersect_test()
constexpr StringRefNull radius
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
double BLI_rng_get_double(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
int orient2d(const double2 &a, const double2 &b, const double2 &c)
@ CDT_CONSTRAINTS_VALID_BMESH
@ CDT_INSIDE_WITH_HOLES_NONZERO
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES
VecBase< double, 2 > double2
ATTR_WARN_UNUSED_RESULT const BMVert * v
struct RNG * BLI_rng_new(unsigned int seed)
VecBase< int32_t, 2 > int2
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
double BLI_time_now_seconds()
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e