3 #include "testing/testing.h"
16 #include <type_traits>
18 #define DO_CPP_TESTS 1
20 #define DO_TEXT_TESTS 0
21 #define DO_RANDOM_TESTS 0
39 template<
typename T>
CDT_input<T> fill_input_from_string(
const char *spec)
41 std::istringstream ss(spec);
44 std::istringstream hdrss(line);
45 int nverts, nedges, nfaces;
46 hdrss >> nverts >> nedges >> nfaces;
50 Array<vec2<T>>
verts(nverts);
51 Array<std::pair<int, int>> edges(nedges);
52 Array<Vector<int>>
faces(nfaces);
54 while (i < nverts && getline(ss, line)) {
55 std::istringstream iss(line);
60 verts[i] = vec2<T>(p0, p1);
64 while (i < nedges && getline(ss, line)) {
65 std::istringstream ess(line);
68 edges[i] = std::pair<int, int>(e0, e1);
72 while (i < nfaces && getline(ss, line)) {
73 std::istringstream fss(line);
85 if (std::is_same<mpq_class, T>::value) {
100 static int get_orig_index(
const Array<Vector<int>> &out_to_orig,
int orig_index)
102 int n =
static_cast<int>(out_to_orig.size());
103 for (
int i = 0; i < n; ++i) {
104 for (
int orig : out_to_orig[i]) {
105 if (orig == orig_index) {
125 template<>
double math_to_double<mpq_class>(
const mpq_class
v)
134 template<> mpq_class
math_abs(
const mpq_class
v)
140 template<>
double math_abs(
const double v)
148 template<
typename T>
int get_vertex_by_coord(
const CDT_result<T> &
out,
double x,
double y)
150 int nv =
static_cast<int>(
out.vert.size());
151 for (
int i = 0; i < nv; ++i) {
163 int get_output_edge_index(
const CDT_result<T> &
out,
int out_index_1,
int out_index_2)
165 int ne =
static_cast<int>(
out.edge.size());
166 for (
int i = 0; i < ne; ++i) {
167 if ((
out.edge[i].first == out_index_1 &&
out.edge[i].second == out_index_2) ||
168 (
out.edge[i].first == out_index_2 &&
out.edge[i].second == out_index_1)) {
176 bool output_edge_has_input_id(
const CDT_result<T> &
out,
int out_edge_index,
int in_edge_index)
178 return out_edge_index < static_cast<int>(
out.edge_orig.size()) &&
179 out.edge_orig[out_edge_index].contains(in_edge_index);
185 template<
typename T>
int get_output_face_index(
const CDT_result<T> &
out,
const Array<int> &poly)
187 int nf =
static_cast<int>(
out.face.size());
188 int npolyv =
static_cast<int>(poly.size());
189 for (
int f = 0; f < nf; ++f) {
190 if (
out.face[f].size() != poly.size()) {
193 for (
int cycle_start = 0; cycle_start < npolyv; ++cycle_start) {
195 for (
int k = 0; ok && k < npolyv; ++k) {
196 if (
out.face[f][(cycle_start + k) % npolyv] != poly[k]) {
214 Array<int> tri{out_index_1, out_index_2, out_index_3};
215 return get_output_face_index(
out, tri);
219 bool output_face_has_input_id(
const CDT_result<T> &
out,
int out_face_index,
int in_face_index)
221 return out_face_index < static_cast<int>(
out.face_orig.size()) &&
222 out.face_orig[out_face_index].contains(in_face_index);
229 os <<
r.vert.size() <<
" verts, " <<
r.edge.size() <<
" edges, " <<
r.face.size() <<
" faces\n";
231 for (
int i :
r.vert.index_range()) {
232 os <<
"v" << i <<
" = " <<
r.vert[i] <<
"\n";
234 for (
int j :
r.vert_orig[i].index_range()) {
235 os <<
r.vert_orig[i][j] <<
" ";
240 for (
int i :
r.edge.index_range()) {
241 os <<
"e" << i <<
" = (" <<
r.edge[i].first <<
", " <<
r.edge[i].second <<
")\n";
243 for (
int j :
r.edge_orig[i].index_range()) {
244 os <<
r.edge_orig[i][j] <<
" ";
249 for (
int i :
r.face.index_range()) {
250 os <<
"f" << i <<
" = ";
251 for (
int j :
r.face[i].index_range()) {
252 os <<
r.face[i][j] <<
" ";
256 for (
int j :
r.face_orig[i].index_range()) {
257 os <<
r.face_orig[i][j] <<
" ";
264 static bool draw_append =
false;
267 void graph_draw(
const std::string &
label,
268 const Array<vec2<T>> &
verts,
269 const Array<std::pair<int, int>> &edges,
270 const Array<Vector<int>> &
faces)
276 constexpr
const char *drawfile =
"./cdt_test_draw.html";
278 constexpr
const char *drawfile =
"/tmp/cdt_test_draw.html";
280 constexpr
int max_draw_width = 1400;
281 constexpr
int max_draw_height = 1000;
282 constexpr
int thin_line = 1;
283 constexpr
int vert_radius = 3;
284 constexpr
bool draw_vert_labels =
false;
285 constexpr
bool draw_edge_labels =
false;
287 if (
verts.size() == 0) {
290 vec2<double> vmin(1e10, 1e10);
291 vec2<double> vmax(-1e10, -1e10);
292 for (
const vec2<T> &
v :
verts) {
293 for (
int i = 0; i < 2; ++i) {
303 double draw_margin = ((vmax.x - vmin.x) + (vmax.y - vmin.y)) * 0.05;
304 double minx = vmin.x - draw_margin;
305 double maxx = vmax.x + draw_margin;
306 double miny = vmin.y - draw_margin;
307 double maxy = vmax.y + draw_margin;
309 double width = maxx - minx;
310 double height = maxy - miny;
312 int view_width = max_draw_width;
313 int view_height =
static_cast<int>(view_width * aspect);
314 if (view_height > max_draw_height) {
315 view_height = max_draw_height;
316 view_width =
static_cast<int>(view_height / aspect);
318 double scale = view_width /
width;
320 #define SX(x) ((math_to_double(x) - minx) * scale)
321 #define SY(y) ((maxy - math_to_double(y)) * scale)
325 f.open(drawfile, std::ios_base::app);
331 std::cout <<
"Could not open file " << drawfile <<
"\n";
335 f <<
"<div>" <<
label <<
"</div>\n<div>\n"
336 <<
"<svg version=\"1.1\" "
337 "xmlns=\"http://www.w3.org/2000/svg\" "
338 "xmlns:xlink=\"http://www.w3.org/1999/xlink\" "
339 "xml:space=\"preserve\"\n"
340 <<
"width=\"" << view_width <<
"\" height=\"" << view_height <<
"\">n";
342 for (
const Vector<int> &fverts :
faces) {
343 f <<
"<polygon fill=\"azure\" stroke=\"none\"\n points=\"";
344 for (
int vi : fverts) {
345 const vec2<T> &co =
verts[vi];
346 f <<
SX(co[0]) <<
"," <<
SY(co[1]) <<
" ";
351 for (
const std::pair<int, int> &
e : edges) {
352 const vec2<T> &uco =
verts[
e.first];
353 const vec2<T> &vco =
verts[
e.second];
354 int strokew = thin_line;
355 f << R
"(<line fill="none" stroke="black" stroke-width=")" << strokew << "\" x1=\""
356 <<
SX(uco[0]) <<
"\" y1=\"" <<
SY(uco[1]) <<
"\" x2=\"" <<
SX(vco[0]) <<
"\" y2=\""
357 <<
SY(vco[1]) <<
"\">\n";
358 f <<
" <title>[" <<
e.first <<
"][" <<
e.second <<
"]</title>\n";
360 if (draw_edge_labels) {
361 f <<
"<text x=\"" <<
SX(0.5 * (uco[0] + vco[0])) <<
"\" y=\"" <<
SY(0.5 * (uco[1] + vco[1]))
362 << R
"(" font-size="small">)";
363 f << "[" <<
e.first <<
"][" <<
e.second <<
"]</text>\n";
368 for (
const vec2<T> &vco :
verts) {
369 f << R
"(<circle fill="black" cx=")" << SX(vco[0]) << "\" cy=\"" <<
SY(vco[1]) <<
"\" r=\""
370 << vert_radius <<
"\">\n";
371 f <<
" <title>[" << i <<
"]" << vco <<
"</title>\n";
373 if (draw_vert_labels) {
374 f <<
"<text x=\"" <<
SX(vco[0]) + vert_radius <<
"\" y=\"" <<
SY(vco[1]) - vert_radius
375 << R
"(" font-size="small">[)" << i << "]</text>\n";
386 constexpr
bool DO_DRAW =
false;
388 template<
typename T>
void expect_coord_near(
const vec2<T> &testco,
const vec2<T> &refco);
392 void expect_coord_near<mpq_class>(
const vec2<mpq_class> &testco,
const vec2<mpq_class> &refco)
399 template<>
void expect_coord_near<double>(
const vec2<double> &testco,
const vec2<double> &refco)
401 EXPECT_NEAR(testco[0], refco[0], 1
e-5);
402 EXPECT_NEAR(testco[1], refco[1], 1
e-5);
407 template<
typename T>
void empty_test()
420 template<
typename T>
void onept_test()
422 const char *spec = R
"(1 0 0
431 if (
out.vert.size() >= 1) {
432 expect_coord_near<T>(
out.vert[0], vec2<T>(0, 0));
436 template<
typename T>
void twopt_test()
438 const char *spec = R
"(2 0 0
448 int v0_out = get_orig_index(
out.vert_orig, 0);
449 int v1_out = get_orig_index(
out.vert_orig, 1);
450 EXPECT_NE(v0_out, -1);
451 EXPECT_NE(v1_out, -1);
452 EXPECT_NE(v0_out, v1_out);
453 if (
out.vert.size() >= 1) {
454 expect_coord_near<T>(
out.vert[v0_out], vec2<T>(0.0, -0.75));
455 expect_coord_near<T>(
out.vert[v1_out], vec2<T>(0.0, 0.75));
457 int e0_out = get_output_edge_index(
out, v0_out, v1_out);
460 graph_draw<T>(
"TwoPt",
out.vert,
out.edge,
out.face);
464 template<
typename T>
void threept_test()
466 const char *spec = R
"(3 0 0
477 int v0_out = get_orig_index(
out.vert_orig, 0);
478 int v1_out = get_orig_index(
out.vert_orig, 1);
479 int v2_out = get_orig_index(
out.vert_orig, 2);
480 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1);
481 EXPECT_TRUE(v0_out != v1_out && v0_out != v2_out && v1_out != v2_out);
482 int e0_out = get_output_edge_index(
out, v0_out, v1_out);
483 int e1_out = get_output_edge_index(
out, v1_out, v2_out);
484 int e2_out = get_output_edge_index(
out, v2_out, v0_out);
485 EXPECT_TRUE(e0_out != -1 && e1_out != -1 && e2_out != -1);
486 EXPECT_TRUE(e0_out != e1_out && e0_out != e2_out && e1_out != e2_out);
487 int f0_out = get_output_tri_index(
out, v0_out, v2_out, v1_out);
490 graph_draw<T>(
"ThreePt",
out.vert,
out.edge,
out.face);
494 template<
typename T>
void mixedpts_test()
497 const char *spec = R
"(4 3 0
511 int v0_out = get_orig_index(
out.vert_orig, 0);
512 int v1_out = get_orig_index(
out.vert_orig, 1);
513 int v2_out = get_orig_index(
out.vert_orig, 2);
514 int v3_out = get_orig_index(
out.vert_orig, 3);
515 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
516 int e0_out = get_output_edge_index(
out, v0_out, v1_out);
517 int e1_out = get_output_edge_index(
out, v1_out, v2_out);
518 int e2_out = get_output_edge_index(
out, v2_out, v3_out);
519 EXPECT_TRUE(e0_out != -1 && e1_out != -1 && e2_out != -1);
520 EXPECT_TRUE(output_edge_has_input_id(
out, e0_out, 0));
521 EXPECT_TRUE(output_edge_has_input_id(
out, e1_out, 1));
522 EXPECT_TRUE(output_edge_has_input_id(
out, e2_out, 2));
524 graph_draw<T>(
"MixedPts",
out.vert,
out.edge,
out.face);
528 template<
typename T>
void quad0_test()
530 const char *spec = R
"(4 0 0
541 int e_diag_out = get_output_edge_index(
out, 1, 3);
542 EXPECT_NE(e_diag_out, -1);
544 graph_draw<T>(
"Quad0",
out.vert,
out.edge,
out.face);
548 template<
typename T>
void quad1_test()
550 const char *spec = R
"(4 0 0
561 int e_diag_out = get_output_edge_index(
out, 0, 2);
562 EXPECT_NE(e_diag_out, -1);
564 graph_draw<T>(
"Quad1",
out.vert,
out.edge,
out.face);
568 template<
typename T>
void quad2_test()
570 const char *spec = R
"(4 0 0
581 int e_diag_out = get_output_edge_index(
out, 1, 3);
582 EXPECT_NE(e_diag_out, -1);
584 graph_draw<T>(
"Quad2",
out.vert,
out.edge,
out.face);
588 template<
typename T>
void quad3_test()
590 const char *spec = R
"(4 0 0
601 int e_diag_out = get_output_edge_index(
out, 0, 2);
602 EXPECT_NE(e_diag_out, -1);
604 graph_draw<T>(
"Quad3",
out.vert,
out.edge,
out.face);
608 template<
typename T>
void quad4_test()
610 const char *spec = R
"(4 0 0
621 int e_diag_out = get_output_edge_index(
out, 0, 1);
622 EXPECT_NE(e_diag_out, -1);
624 graph_draw<T>(
"Quad4",
out.vert,
out.edge,
out.face);
628 template<
typename T>
void lineinsquare_test()
630 const char *spec = R
"(6 1 1
646 graph_draw<T>(
"LineInSquare - full",
out.vert,
out.edge,
out.face);
652 graph_draw<T>(
"LineInSquare - constraints", out2.vert, out2.edge, out2.face);
658 graph_draw<T>(
"LineInSquare - inside with holes", out3.vert, out3.edge, out3.face);
664 graph_draw<T>(
"LineInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
668 template<
typename T>
void lineholeinsquare_test()
670 const char *spec = R
"(10 1 2
691 graph_draw<T>(
"LineHoleInSquare - full",
out.vert,
out.edge,
out.face);
697 graph_draw<T>(
"LineHoleInSquare - constraints", out2.vert, out2.edge, out2.face);
703 graph_draw<T>(
"LineHoleInSquare - inside with holes", out3.vert, out3.edge, out3.face);
709 graph_draw<T>(
"LineHoleInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
713 template<
typename T>
void nestedholes_test()
715 const char *spec = R
"(12 0 3
738 graph_draw<T>(
"NestedHoles - full",
out.vert,
out.edge,
out.face);
744 graph_draw<T>(
"NestedHoles - constraints", out2.vert, out2.edge, out2.face);
750 graph_draw<T>(
"NestedHoles - inside with holes", out3.vert, out3.edge, out3.face);
756 graph_draw<T>(
"NestedHoles - valid bmesh with holes", out4.vert, out4.edge, out4.face);
760 template<
typename T>
void crosssegs_test()
762 const char *spec = R
"(4 2 0
776 int v0_out = get_orig_index(
out.vert_orig, 0);
777 int v1_out = get_orig_index(
out.vert_orig, 1);
778 int v2_out = get_orig_index(
out.vert_orig, 2);
779 int v3_out = get_orig_index(
out.vert_orig, 3);
780 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
781 if (
out.vert.size() == 5) {
782 int v_intersect = -1;
783 for (
int i = 0; i < 5; i++) {
784 if (!
ELEM(i, v0_out, v1_out, v2_out, v3_out)) {
789 EXPECT_NE(v_intersect, -1);
790 if (v_intersect != -1) {
791 expect_coord_near<T>(
out.vert[v_intersect], vec2<T>(0, 0));
795 graph_draw<T>(
"CrossSegs",
out.vert,
out.edge,
out.face);
799 template<
typename T>
void cutacrosstri_test()
802 const char *spec = R
"(5 1 1
817 int v0_out = get_orig_index(
out.vert_orig, 0);
818 int v1_out = get_orig_index(
out.vert_orig, 1);
819 int v2_out = get_orig_index(
out.vert_orig, 2);
820 int v3_out = get_orig_index(
out.vert_orig, 3);
821 int v4_out = get_orig_index(
out.vert_orig, 4);
822 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1 && v4_out != -1);
823 if (
out.face.size() == 3) {
824 int e0_out = get_orig_index(
out.edge_orig, 0);
825 EXPECT_NE(e0_out, -1);
826 int fe0_out = get_output_edge_index(
out, v0_out, v1_out);
827 EXPECT_NE(fe0_out, -1);
828 int fe1a_out = get_output_edge_index(
out, v1_out, v4_out);
829 EXPECT_NE(fe1a_out, -1);
830 int fe1b_out = get_output_edge_index(
out, v4_out, v2_out);
831 EXPECT_NE(fe1b_out, -1);
832 if (fe1a_out != 0 && fe1b_out != 0) {
834 EXPECT_TRUE(
out.edge_orig[fe1a_out].size() == 1 &&
out.edge_orig[fe1a_out][0] == 11);
835 EXPECT_TRUE(
out.edge_orig[fe1b_out].size() == 1 &&
out.edge_orig[fe1b_out][0] == 11);
837 int e_diag = get_output_edge_index(
out, v0_out, v4_out);
838 EXPECT_NE(e_diag, -1);
844 graph_draw<T>(
"CutAcrossTri",
out.vert,
out.edge,
out.face);
848 template<
typename T>
void diamondcross_test()
851 const char *spec = R
"(7 5 0
872 graph_draw<T>(
"DiamondCross",
out.vert,
out.edge,
out.face);
876 template<
typename T>
void twodiamondscross_test()
878 const char *spec = R
"(12 9 0
907 if (
out.vert.size() == 8 &&
out.edge.size() == 15 &&
out.face.size() == 8) {
909 for (
int i = 0; i < 12; ++i) {
910 v_out[i] = get_orig_index(
out.vert_orig, i);
911 EXPECT_NE(v_out[i], -1);
918 for (
int i = 0; i < 8; ++i) {
919 e_out[i] = get_output_edge_index(
out, v_out[in.edge[i].first], v_out[in.edge[i].second]);
920 EXPECT_NE(e_out[i], -1);
923 EXPECT_EQ(get_output_edge_index(
out, v_out[10], v_out[11]), -1);
924 int e_cross_1 = get_output_edge_index(
out, v_out[0], v_out[2]);
925 int e_cross_2 = get_output_edge_index(
out, v_out[2], v_out[5]);
926 int e_cross_3 = get_output_edge_index(
out, v_out[5], v_out[7]);
927 EXPECT_TRUE(e_cross_1 != -1 && e_cross_2 != -1 && e_cross_3 != -1);
928 EXPECT_TRUE(output_edge_has_input_id(
out, e_cross_1, 8));
929 EXPECT_TRUE(output_edge_has_input_id(
out, e_cross_2, 8));
930 EXPECT_TRUE(output_edge_has_input_id(
out, e_cross_3, 8));
933 graph_draw<T>(
"TwoDiamondsCross",
out.vert,
out.edge,
out.face);
937 template<
typename T>
void manycross_test()
940 const char *spec = R
"(27 21 0
997 graph_draw<T>(
"ManyCross",
out.vert,
out.edge,
out.face);
1001 template<
typename T>
void twoface_test()
1003 const char *spec = R
"(6 0 2
1019 if (
out.vert.size() == 6 &&
out.edge.size() == 9 &&
out.face.size() == 4) {
1021 for (
int i = 0; i < 6; i++) {
1022 v_out[i] = get_orig_index(
out.vert_orig, i);
1023 EXPECT_NE(v_out[i], -1);
1025 int f0_out = get_output_tri_index(
out, v_out[0], v_out[1], v_out[2]);
1026 int f1_out = get_output_tri_index(
out, v_out[3], v_out[4], v_out[5]);
1027 EXPECT_NE(f0_out, -1);
1028 EXPECT_NE(f1_out, -1);
1029 int e0_out = get_output_edge_index(
out, v_out[0], v_out[1]);
1030 int e1_out = get_output_edge_index(
out, v_out[1], v_out[2]);
1031 int e2_out = get_output_edge_index(
out, v_out[2], v_out[0]);
1032 EXPECT_NE(e0_out, -1);
1033 EXPECT_NE(e1_out, -1);
1034 EXPECT_NE(e2_out, -1);
1035 EXPECT_TRUE(output_edge_has_input_id(
out, e0_out,
out.face_edge_offset + 0));
1036 EXPECT_TRUE(output_edge_has_input_id(
out, e1_out,
out.face_edge_offset + 1));
1037 EXPECT_TRUE(output_edge_has_input_id(
out, e2_out,
out.face_edge_offset + 2));
1038 EXPECT_TRUE(output_face_has_input_id(
out, f0_out, 0));
1039 EXPECT_TRUE(output_face_has_input_id(
out, f1_out, 1));
1042 graph_draw<T>(
"TwoFace",
out.vert,
out.edge,
out.face);
1046 template<
typename T>
void twoface2_test()
1048 const char *spec = R
"(6 0 2
1064 if (
out.vert.size() == 10 &&
out.edge.size() == 18 &&
out.face.size() == 9) {
1066 for (
int i = 0; i < 6; i++) {
1069 int v6 = get_vertex_by_coord(
out, 3.0, 3.0);
1071 int v7 = get_vertex_by_coord(
out, 3.0, 3.75);
1073 int v8 = get_vertex_by_coord(
out, 0.0, 3.0);
1075 int v9 = get_vertex_by_coord(
out, 1.0, 1.0);
1078 int f0 = get_output_tri_index(
out, 0, 9, 5);
1080 EXPECT_TRUE(output_face_has_input_id(
out, f0, 0));
1081 EXPECT_FALSE(output_face_has_input_id(
out, f0, 1));
1082 int f1 = get_output_tri_index(
out, 0, 5, 2);
1084 EXPECT_TRUE(output_face_has_input_id(
out, f1, 0));
1085 EXPECT_FALSE(output_face_has_input_id(
out, f1, 1));
1086 int f2 = get_output_tri_index(
out, 2, 5, 8);
1088 EXPECT_TRUE(output_face_has_input_id(
out, f2, 0));
1089 EXPECT_FALSE(output_face_has_input_id(
out, f2, 1));
1090 int f3 = get_output_tri_index(
out, 6, 1, 7);
1092 EXPECT_TRUE(output_face_has_input_id(
out, f3, 0));
1093 EXPECT_FALSE(output_face_has_input_id(
out, f3, 1));
1095 int f4 = get_output_tri_index(
out, 8, 7, 4);
1097 EXPECT_FALSE(output_face_has_input_id(
out, f4, 0));
1098 EXPECT_TRUE(output_face_has_input_id(
out, f4, 1));
1099 int f5 = get_output_tri_index(
out, 3, 6, 9);
1101 EXPECT_FALSE(output_face_has_input_id(
out, f5, 0));
1102 EXPECT_TRUE(output_face_has_input_id(
out, f5, 1));
1104 int f6 = get_output_tri_index(
out, 5, 9, 6);
1106 EXPECT_TRUE(output_face_has_input_id(
out, f6, 0));
1107 EXPECT_TRUE(output_face_has_input_id(
out, f6, 1));
1108 int f7 = get_output_tri_index(
out, 5, 6, 7);
1110 EXPECT_TRUE(output_face_has_input_id(
out, f7, 0));
1111 EXPECT_TRUE(output_face_has_input_id(
out, f7, 1));
1112 int f8 = get_output_tri_index(
out, 5, 7, 8);
1114 EXPECT_TRUE(output_face_has_input_id(
out, f8, 0));
1115 EXPECT_TRUE(output_face_has_input_id(
out, f8, 1));
1118 graph_draw<T>(
"TwoFace2",
out.vert,
out.edge,
out.face);
1122 template<
typename T>
void overlapfaces_test()
1124 const char *spec = R
"(12 0 3
1147 if (
out.vert.size() == 14 &&
out.edge.size() == 33 &&
out.face.size() == 20) {
1149 for (
int i = 0; i < 12; i++) {
1150 v_out[i] = get_orig_index(
out.vert_orig, i);
1151 EXPECT_NE(v_out[i], -1);
1155 T x =
out.vert[v_int1][0] -
T(1);
1160 expect_coord_near<T>(
out.vert[v_int1], vec2<T>(1, 0.5));
1161 expect_coord_near<T>(
out.vert[v_int2], vec2<T>(0.5, 1));
1164 int f0_out = get_output_tri_index(
out, v_out[1], v_int1, v_out[4]);
1165 EXPECT_NE(f0_out, -1);
1166 EXPECT_TRUE(output_face_has_input_id(
out, f0_out, 0));
1167 int f1_out = get_output_tri_index(
out, v_out[4], v_int1, v_out[2]);
1168 EXPECT_NE(f1_out, -1);
1169 EXPECT_TRUE(output_face_has_input_id(
out, f1_out, 0));
1170 EXPECT_TRUE(output_face_has_input_id(
out, f1_out, 1));
1171 int f2_out = get_output_tri_index(
out, v_out[8], v_out[9], v_out[10]);
1173 f2_out = get_output_tri_index(
out, v_out[8], v_out[9], v_out[11]);
1175 EXPECT_NE(f2_out, -1);
1176 EXPECT_TRUE(output_face_has_input_id(
out, f2_out, 0));
1177 EXPECT_TRUE(output_face_has_input_id(
out, f2_out, 2));
1180 graph_draw<T>(
"OverlapFaces - full",
out.vert,
out.edge,
out.face);
1187 graph_draw<T>(
"OverlapFaces - inside", out2.vert, out2.edge, out2.face);
1193 graph_draw<T>(
"OverlapFaces - inside with holes", out3.vert, out3.edge, out3.face);
1199 graph_draw<T>(
"OverlapFaces - constraints", out4.vert, out4.edge, out4.face);
1205 graph_draw<T>(
"OverlapFaces - valid bmesh", out5.vert, out5.edge, out5.face);
1211 graph_draw<T>(
"OverlapFaces - valid bmesh with holes", out6.vert, out6.edge, out6.face);
1215 template<
typename T>
void twosquaresoverlap_test()
1217 const char *spec = R
"(8 0 2
1236 graph_draw<T>(
"TwoSquaresOverlap",
out.vert,
out.edge,
out.face);
1240 template<
typename T>
void twofaceedgeoverlap_test()
1242 const char *spec = R
"(6 0 2
1258 if (
out.vert.size() == 5 &&
out.edge.size() == 7 &&
out.face.size() == 3) {
1261 for (
int i = 0; i < 6; i++) {
1262 v_out[i] = get_orig_index(
out.vert_orig, i);
1263 EXPECT_NE(v_out[i], -1);
1264 EXPECT_NE(v_out[i], v_int);
1268 int e01 = get_output_edge_index(
out, v_out[0], v_out[1]);
1269 int foff =
out.face_edge_offset;
1270 EXPECT_TRUE(output_edge_has_input_id(
out, e01, foff + 1));
1271 int e1i = get_output_edge_index(
out, v_out[1], v_int);
1272 EXPECT_TRUE(output_edge_has_input_id(
out, e1i, foff + 0));
1273 int ei2 = get_output_edge_index(
out, v_int, v_out[2]);
1274 EXPECT_TRUE(output_edge_has_input_id(
out, ei2, foff + 0));
1275 int e20 = get_output_edge_index(
out, v_out[2], v_out[0]);
1276 EXPECT_TRUE(output_edge_has_input_id(
out, e20, foff + 2));
1277 EXPECT_TRUE(output_edge_has_input_id(
out, e20, 2 * foff + 2));
1278 int e24 = get_output_edge_index(
out, v_out[2], v_out[4]);
1279 EXPECT_TRUE(output_edge_has_input_id(
out, e24, 2 * foff + 0));
1280 int e4i = get_output_edge_index(
out, v_out[4], v_int);
1281 EXPECT_TRUE(output_edge_has_input_id(
out, e4i, 2 * foff + 1));
1282 int ei0 = get_output_edge_index(
out, v_int, v_out[0]);
1283 EXPECT_TRUE(output_edge_has_input_id(
out, ei0, 2 * foff + 1));
1284 int f02i = get_output_tri_index(
out, v_out[0], v_out[2], v_int);
1285 EXPECT_NE(f02i, -1);
1286 EXPECT_TRUE(output_face_has_input_id(
out, f02i, 0));
1287 EXPECT_TRUE(output_face_has_input_id(
out, f02i, 1));
1288 int f24i = get_output_tri_index(
out, v_out[2], v_out[4], v_int);
1289 EXPECT_NE(f24i, -1);
1290 EXPECT_TRUE(output_face_has_input_id(
out, f24i, 1));
1291 EXPECT_FALSE(output_face_has_input_id(
out, f24i, 0));
1292 int f10i = get_output_tri_index(
out, v_out[1], v_out[0], v_int);
1293 EXPECT_NE(f10i, -1);
1294 EXPECT_TRUE(output_face_has_input_id(
out, f10i, 0));
1295 EXPECT_FALSE(output_face_has_input_id(
out, f10i, 1));
1298 graph_draw<T>(
"TwoFaceEdgeOverlap",
out.vert,
out.edge,
out.face);
1302 template<
typename T>
void triintri_test()
1304 const char *spec = R
"(6 0 2
1321 graph_draw<T>(
"TriInTri",
out.vert,
out.edge,
out.face);
1325 template<
typename T>
void diamondinsquare_test()
1327 const char *spec = R
"(8 0 2
1332 0.14644660940672627 0.5
1333 0.5 0.14644660940672627
1334 0.8535533905932737 0.5
1335 0.5 0.8535533905932737
1346 graph_draw<T>(
"DiamondInSquare",
out.vert,
out.edge,
out.face);
1350 template<
typename T>
void diamondinsquarewire_test()
1352 const char *spec = R
"(8 8 0
1357 0.14644660940672627 0.5
1358 0.5 0.14644660940672627
1359 0.8535533905932737 0.5
1360 0.5 0.8535533905932737
1377 graph_draw<T>(
"DiamondInSquareWire",
out.vert,
out.edge,
out.face);
1381 template<
typename T>
void repeatedge_test()
1383 const char *spec = R
"(5 3 0
1398 graph_draw<T>(
"RepeatEdge",
out.vert,
out.edge,
out.face);
1402 template<
typename T>
void repeattri_test()
1404 const char *spec = R
"(3 0 2
1416 EXPECT_TRUE(output_face_has_input_id(out, 0, 0));
1417 EXPECT_TRUE(output_face_has_input_id(out, 0, 1));
1419 graph_draw<T>(
"RepeatTri",
out.vert,
out.edge,
out.face);
1423 template<
typename T>
void square_o_test()
1425 const char *spec = R
"(8 0 2
1441 graph_draw<T>(
"Square O - inside with holes", out1.vert, out1.edge, out1.face);
1447 graph_draw<T>(
"Square O - valid bmesh with holes", out2.vert, out2.edge, out2.face);
1451 TEST(delaunay_d, Empty)
1453 empty_test<double>();
1456 TEST(delaunay_d, OnePt)
1458 onept_test<double>();
1461 TEST(delaunay_d, TwoPt)
1463 twopt_test<double>();
1466 TEST(delaunay_d, ThreePt)
1468 threept_test<double>();
1471 TEST(delaunay_d, MixedPts)
1473 mixedpts_test<double>();
1476 TEST(delaunay_d, Quad0)
1478 quad0_test<double>();
1481 TEST(delaunay_d, Quad1)
1483 quad1_test<double>();
1486 TEST(delaunay_d, Quad2)
1488 quad2_test<double>();
1491 TEST(delaunay_d, Quad3)
1493 quad3_test<double>();
1496 TEST(delaunay_d, Quad4)
1498 quad4_test<double>();
1501 TEST(delaunay_d, LineInSquare)
1503 lineinsquare_test<double>();
1506 TEST(delaunay_d, LineHoleInSquare)
1508 lineholeinsquare_test<double>();
1511 TEST(delaunay_d, NestedHoles)
1513 nestedholes_test<double>();
1516 TEST(delaunay_d, CrossSegs)
1518 crosssegs_test<double>();
1521 TEST(delaunay_d, CutAcrossTri)
1523 cutacrosstri_test<double>();
1526 TEST(delaunay_d, DiamondCross)
1528 diamondcross_test<double>();
1531 TEST(delaunay_d, TwoDiamondsCross)
1533 twodiamondscross_test<double>();
1536 TEST(delaunay_d, ManyCross)
1538 manycross_test<double>();
1541 TEST(delaunay_d, TwoFace)
1543 twoface_test<double>();
1546 TEST(delaunay_d, TwoFace2)
1548 twoface2_test<double>();
1551 TEST(delaunay_d, OverlapFaces)
1553 overlapfaces_test<double>();
1556 TEST(delaunay_d, TwoSquaresOverlap)
1558 twosquaresoverlap_test<double>();
1561 TEST(delaunay_d, TwoFaceEdgeOverlap)
1563 twofaceedgeoverlap_test<double>();
1566 TEST(delaunay_d, TriInTri)
1568 triintri_test<double>();
1571 TEST(delaunay_d, DiamondInSquare)
1573 diamondinsquare_test<double>();
1576 TEST(delaunay_d, DiamondInSquareWire)
1578 diamondinsquarewire_test<double>();
1581 TEST(delaunay_d, RepeatEdge)
1583 repeatedge_test<double>();
1586 TEST(delaunay_d, RepeatTri)
1588 repeattri_test<double>();
1591 TEST(delaunay_d, SquareO)
1593 square_o_test<double>();
1597 TEST(delaunay_m, Empty)
1599 empty_test<mpq_class>();
1602 TEST(delaunay_m, OnePt)
1604 onept_test<mpq_class>();
1606 TEST(delaunay_m, TwoPt)
1608 twopt_test<mpq_class>();
1611 TEST(delaunay_m, ThreePt)
1613 threept_test<mpq_class>();
1616 TEST(delaunay_m, MixedPts)
1618 mixedpts_test<mpq_class>();
1621 TEST(delaunay_m, Quad0)
1623 quad0_test<mpq_class>();
1626 TEST(delaunay_m, Quad1)
1628 quad1_test<mpq_class>();
1631 TEST(delaunay_m, Quad2)
1633 quad2_test<mpq_class>();
1636 TEST(delaunay_m, Quad3)
1638 quad3_test<mpq_class>();
1641 TEST(delaunay_m, Quad4)
1643 quad4_test<mpq_class>();
1646 TEST(delaunay_m, LineInSquare)
1648 lineinsquare_test<mpq_class>();
1651 TEST(delaunay_m, LineHoleInSquare)
1653 lineholeinsquare_test<mpq_class>();
1656 TEST(delaunay_m, NestedHoles)
1658 nestedholes_test<mpq_class>();
1661 TEST(delaunay_m, CrossSegs)
1663 crosssegs_test<mpq_class>();
1666 TEST(delaunay_m, CutAcrossTri)
1668 cutacrosstri_test<mpq_class>();
1671 TEST(delaunay_m, DiamondCross)
1673 diamondcross_test<mpq_class>();
1676 TEST(delaunay_m, TwoDiamondsCross)
1678 twodiamondscross_test<mpq_class>();
1681 TEST(delaunay_m, ManyCross)
1683 manycross_test<mpq_class>();
1686 TEST(delaunay_m, TwoFace)
1688 twoface_test<mpq_class>();
1691 TEST(delaunay_m, TwoFace2)
1693 twoface2_test<mpq_class>();
1696 TEST(delaunay_m, OverlapFaces)
1698 overlapfaces_test<mpq_class>();
1701 TEST(delaunay_m, TwoSquaresOverlap)
1703 twosquaresoverlap_test<mpq_class>();
1706 TEST(delaunay_m, TwoFaceEdgeOverlap)
1708 twofaceedgeoverlap_test<mpq_class>();
1711 TEST(delaunay_m, TriInTri)
1713 triintri_test<mpq_class>();
1716 TEST(delaunay_m, DiamondInSquare)
1718 diamondinsquare_test<mpq_class>();
1721 TEST(delaunay_m, DiamondInSquareWire)
1723 diamondinsquarewire_test<mpq_class>();
1726 TEST(delaunay_m, RepeatEdge)
1728 repeatedge_test<mpq_class>();
1731 TEST(delaunay_m, RepeatTri)
1733 repeattri_test<mpq_class>();
1740 TEST(delaunay_d, CintTwoFace)
1742 float vert_coords[][2] = {
1743 {0.0, 0.0}, {1.0, 0.0}, {0.5, 1.0}, {1.1, 1.0}, {1.1, 0.0}, {1.6, 1.0}};
1744 int faces[] = {0, 1, 2, 3, 4, 5};
1745 int faces_len[] = {3, 3};
1746 int faces_start[] = {0, 3};
1749 input.verts_len = 6;
1750 input.edges_len = 0;
1751 input.faces_len = 2;
1752 input.vert_coords = vert_coords;
1753 input.edges =
nullptr;
1755 input.faces_len_table = faces_len;
1756 input.faces_start_table = faces_start;
1757 input.epsilon = 1e-5f;
1758 input.need_ids =
false;
1763 TEST(delaunay_d, CintTwoFaceNoIds)
1765 float vert_coords[][2] = {
1766 {0.0, 0.0}, {1.0, 0.0}, {0.5, 1.0}, {1.1, 1.0}, {1.1, 0.0}, {1.6, 1.0}};
1767 int faces[] = {0, 1, 2, 3, 4, 5};
1768 int faces_len[] = {3, 3};
1769 int faces_start[] = {0, 3};
1772 input.verts_len = 6;
1773 input.edges_len = 0;
1774 input.faces_len = 2;
1775 input.vert_coords = vert_coords;
1776 input.edges =
nullptr;
1778 input.faces_len_table = faces_len;
1779 input.faces_start_table = faces_start;
1780 input.epsilon = 1e-5f;
1781 input.need_ids =
true;
1789 template<
typename T>
1791 int arc_points_num,
int lets_per_line_num,
int lines_num,
CDT_output_type otype,
bool need_ids)
1793 constexpr
bool print_timing =
true;
1816 const char *b_before_arcs = R
"(13 0 3
1835 CDT_input<T> b_before_arcs_in = fill_input_from_string<T>(b_before_arcs);
1836 constexpr int narcs = 4;
1837 int b_npts = b_before_arcs_in.vert.size() + narcs * arc_points_num;
1838 constexpr
int b_nfaces = 3;
1839 Array<vec2<T>> b_vert(b_npts);
1840 Array<Vector<int>> b_face(b_nfaces);
1841 std::copy(b_before_arcs_in.vert.begin(), b_before_arcs_in.vert.end(), b_vert.begin());
1842 std::copy(b_before_arcs_in.face.begin(), b_before_arcs_in.face.end(), b_face.begin());
1843 if (arc_points_num > 0) {
1844 b_face[0].pop_last();
1845 for (
int arc = 0; arc < narcs; ++arc) {
1846 int arc_origin_vert;
1847 int arc_terminal_vert;
1851 arc_origin_vert = 1;
1852 arc_terminal_vert = 2;
1856 arc_origin_vert = 2;
1857 arc_terminal_vert = 3;
1861 arc_origin_vert = 7;
1862 arc_terminal_vert = 6;
1866 arc_origin_vert = 11;
1867 arc_terminal_vert = 10;
1873 vec2<T> start_co = b_vert[arc_origin_vert];
1874 vec2<T> end_co = b_vert[arc_terminal_vert];
1875 vec2<T> center_co = 0.5 * (start_co + end_co);
1877 double radius =
abs(math_to_double<T>(end_co[1] - center_co[1]));
1878 double angle_delta =
M_PI / (arc_points_num + 1);
1879 int start_vert = b_before_arcs_in.vert.size() + arc * arc_points_num;
1880 Vector<int> &face = b_face[(arc <= 1) ? 0 : arc - 1];
1881 for (
int i = 0; i < arc_points_num; ++i) {
1883 float ang = ccw ? (-
M_PI_2 + (i + 1) * angle_delta) : (
M_PI_2 - (i + 1) * angle_delta);
1884 delta[0] =
T(radius *
cos(ang));
1885 delta[1] =
T(radius *
sin(ang));
1886 b_vert[start_vert + i] = center_co + delta;
1887 face.append(start_vert + i);
1890 face.append(arc_terminal_vert);
1896 int tot_instances = lets_per_line_num * lines_num;
1897 if (tot_instances == 1) {
1902 in.vert = Array<vec2<T>>(tot_instances * b_vert.size());
1903 in.face = Array<Vector<int>>(tot_instances * b_face.size());
1907 T delta_y =
T(3.25);
1909 for (
int line = 0; line < lines_num; ++line) {
1910 for (
int let = 0; let < lets_per_line_num; ++let) {
1911 vec2<T> co_offset(cur_x, cur_y);
1913 for (
int v = 0;
v < b_vert.size(); ++
v) {
1914 in.vert[in_v_offset +
v] = b_vert[
v] + co_offset;
1917 for (
int f : b_face.index_range()) {
1918 for (
int fv : b_face[f]) {
1919 in.face[in_f_offset + f].append(in_v_offset + fv);
1935 std::cout <<
"time = " << tend - tstart <<
"\n";
1944 if (lets_per_line_num > 1) {
1947 if (lines_num > 1) {
1960 TEST(delaunay_d, TextB10)
1965 TEST(delaunay_d, TextB10_noids)
1970 TEST(delaunay_d, TextB10_inside)
1972 text_test<double>(10, 1, 1,
CDT_INSIDE,
true);
1975 TEST(delaunay_d, TextB10_inside_noids)
1977 text_test<double>(10, 1, 1,
CDT_INSIDE,
false);
1980 TEST(delaunay_d, TextB10_constraints)
1985 TEST(delaunay_d, TextB10_constraints_noids)
1990 TEST(delaunay_d, TextB10_constraints_valid_bmesh)
1995 TEST(delaunay_d, TextB10_constraints_valid_bmesh_noids)
2000 TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes)
2005 TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes_noids)
2010 TEST(delaunay_d, TextB200)
2015 TEST(delaunay_d, TextB10_10_10)
2020 TEST(delaunay_d, TextB10_10_10_noids)
2026 TEST(delaunay_m, TextB10)
2031 TEST(delaunay_m, TextB200)
2036 TEST(delaunay_m, TextB10_10_10)
2041 TEST(delaunay_m, TextB10_10_10_noids)
2057 RANDOM_TRI_BETWEEN_CIRCLES,
2060 template<
typename T>
2061 void rand_delaunay_test(
int test_kind,
2068 constexpr
bool print_timing =
true;
2070 Array<double> times(max_lg_size + 1);
2073 for (
int lg_size = start_lg_size; lg_size <= max_lg_size; ++lg_size) {
2074 int size = 1 << lg_size;
2075 times[lg_size] = 0.0;
2076 if (
size == 1 && test_kind != RANDOM_PTS) {
2080 for (
int rep = 0; rep < reps_per_size; ++rep) {
2085 std::string test_label;
2086 switch (test_kind) {
2099 test_label =
"Random poly with " +
std::to_string(nedges) +
" edges";
2101 case RANDOM_TILTED_GRID: {
2114 case RANDOM_CIRCLE: {
2122 case RANDOM_TRI_BETWEEN_CIRCLES: {
2130 " triangles between circles (inner radius=" +
std::to_string(param) +
")";
2133 std::cout <<
"unknown delaunay test type\n";
2138 test_label +=
" (inside)";
2141 test_label +=
" (constraints)";
2144 test_label +=
" (valid bmesh)";
2149 in.vert = Array<vec2<T>>(npts);
2151 in.edge = Array<std::pair<int, int>>(nedges);
2154 in.face = Array<Vector<int>>(nfaces);
2158 switch (test_kind) {
2162 for (
int i = 0; i <
size; i++) {
2165 if (test_kind != RANDOM_PTS) {
2167 in.edge[i - 1].first = i - 1;
2168 in.edge[i - 1].second = i;
2172 if (test_kind == RANDOM_POLY) {
2173 in.edge[
size - 1].first =
size - 1;
2174 in.edge[
size - 1].second = 0;
2178 case RANDOM_TILTED_GRID: {
2179 for (
int i = 0; i <
size; ++i) {
2180 for (
int j = 0; j <
size; ++j) {
2181 in.vert[i *
size + j][0] =
T(i * param + j);
2182 in.vert[i *
size + j][1] =
T(i);
2185 for (
int i = 0; i <
size; ++i) {
2187 in.edge[i].first = i *
size;
2188 in.edge[i].second = i *
size +
size - 1;
2190 in.edge[
size + i].first = i;
2195 case RANDOM_CIRCLE: {
2197 double angle_delta = 2.0 *
M_PI /
size;
2198 for (
int i = 0; i <
size; i++) {
2199 in.vert[i][0] =
T(
cos(start_angle + i * angle_delta));
2200 in.vert[i][1] =
T(
sin(start_angle + i * angle_delta));
2201 in.face[0].append(i);
2205 case RANDOM_TRI_BETWEEN_CIRCLES: {
2206 for (
int i = 0; i <
size; i++) {
2214 in.vert[ia][0] =
T(
cos(angle1));
2215 in.vert[ia][1] =
T(
sin(angle1));
2216 in.vert[ib][0] =
T(
cos(angle2));
2217 in.vert[ib][1] =
T(
sin(angle2));
2218 in.vert[ic][0] =
T((param *
cos(angle3)));
2219 in.vert[ic][1] =
T((param *
sin(angle3)));
2221 in.face[i].append(ia);
2222 int orient =
orient2d(in.vert[ia], in.vert[ib], in.vert[ic]);
2224 in.face[i].append(ib);
2225 in.face[i].append(ic);
2228 in.face[i].append(ic);
2229 in.face[i].append(ib);
2238 EXPECT_NE(
out.vert.size(), 0);
2241 graph_draw<T>(test_label,
out.vert,
out.edge,
out.face);
2246 std::cout <<
"\nsize,time\n";
2247 for (
int lg_size = 0; lg_size <= max_lg_size; lg_size++) {
2248 int size = 1 << lg_size;
2249 std::cout <<
size <<
"," << times[lg_size] <<
"\n";
2255 TEST(delaunay_d, RandomPts)
2257 rand_delaunay_test<double>(RANDOM_PTS, 0, 7, 1, 0.0,
CDT_FULL);
2260 TEST(delaunay_d, RandomSegs)
2262 rand_delaunay_test<double>(RANDOM_SEGS, 1, 7, 1, 0.0,
CDT_FULL);
2265 TEST(delaunay_d, RandomPoly)
2267 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_FULL);
2270 TEST(delaunay_d, RandomPolyConstraints)
2272 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_CONSTRAINTS);
2275 TEST(delaunay_d, RandomPolyValidBmesh)
2280 TEST(delaunay_d, Grid)
2282 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0,
CDT_FULL);
2285 TEST(delaunay_d, TiltedGridA)
2287 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0,
CDT_FULL);
2290 TEST(delaunay_d, TiltedGridB)
2292 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01,
CDT_FULL);
2295 TEST(delaunay_d, RandomCircle)
2297 rand_delaunay_test<double>(RANDOM_CIRCLE, 1, 7, 1, 0.0,
CDT_FULL);
2300 TEST(delaunay_d, RandomTrisCircle)
2302 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25,
CDT_FULL);
2305 TEST(delaunay_d, RandomTrisCircleB)
2307 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1
e-4,
CDT_FULL);
2311 TEST(delaunay_m, RandomPts)
2313 rand_delaunay_test<mpq_class>(RANDOM_PTS, 0, 7, 1, 0.0,
CDT_FULL);
2316 TEST(delaunay_m, RandomSegs)
2318 rand_delaunay_test<mpq_class>(RANDOM_SEGS, 1, 7, 1, 0.0,
CDT_FULL);
2321 TEST(delaunay_m, RandomPoly)
2323 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_FULL);
2326 TEST(delaunay_d, RandomPolyInside)
2328 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_INSIDE);
2331 TEST(delaunay_m, RandomPolyInside)
2333 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_INSIDE);
2336 TEST(delaunay_m, RandomPolyConstraints)
2338 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0,
CDT_CONSTRAINTS);
2341 TEST(delaunay_m, RandomPolyValidBmesh)
2346 TEST(delaunay_m, Grid)
2348 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0,
CDT_FULL);
2351 TEST(delaunay_m, TiltedGridA)
2353 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0,
CDT_FULL);
2356 TEST(delaunay_m, TiltedGridB)
2358 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01,
CDT_FULL);
2361 TEST(delaunay_m, RandomCircle)
2363 rand_delaunay_test<mpq_class>(RANDOM_CIRCLE, 1, 7, 1, 0.0,
CDT_FULL);
2366 TEST(delaunay_m, RandomTrisCircle)
2368 rand_delaunay_test<mpq_class>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25,
CDT_FULL);
2371 TEST(delaunay_m, RandomTrisCircleB)
2373 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1
e-4,
CDT_FULL);
CDT_result * BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_type output_type)
@ CDT_CONSTRAINTS_VALID_BMESH
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES
void BLI_delaunay_2d_cdt_free(CDT_result *result)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
Math vector functions needed specifically for mesh intersect and boolean.
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
struct RNG * BLI_rng_new(unsigned int seed)
double BLI_rng_get_double(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei height
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei width
Read Guarded memory(de)allocation.
in reality light always falls off quadratically Particle Retrieve the data of the particle that spawned the object instance
Platform independent time functions.
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
blender::meshintersect::CDT_result< double > delaunay_2d_calc(const CDT_input< double > &input, CDT_output_type output_type)
ccl_global KernelShaderEvalInput ccl_global float * output
ccl_global KernelShaderEvalInput * input
ccl_device_inline float2 fabs(const float2 &a)
INLINE Rall1d< T, V, S > cos(const Rall1d< T, V, S > &arg)
INLINE Rall1d< T, V, S > sin(const Rall1d< T, V, S > &arg)
double math_to_double< double >(const double v)
double math_to_double(const T UNUSED(v))
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
int orient2d(const double2 &a, const double2 &b, const double2 &c)
std::string to_string(const T &n)
static const pxr::TfToken out("out", pxr::TfToken::Immortal)
static void copy(bNodeTree *dest_ntree, bNode *dest_node, const bNode *src_node)
double PIL_check_seconds_timer(void)