Blender  V3.3
BLI_delaunay_2d_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 
5 #include "MEM_guardedalloc.h"
6 
7 extern "C" {
8 #include "BLI_math.h"
9 #include "BLI_rand.h"
10 #include "PIL_time.h"
11 }
12 
13 #include <fstream>
14 #include <iostream>
15 #include <sstream>
16 #include <type_traits>
17 
18 #define DO_CPP_TESTS 1
19 #define DO_C_TESTS 1
20 #define DO_TEXT_TESTS 0
21 #define DO_RANDOM_TESTS 0
22 
23 #include "BLI_array.hh"
24 #include "BLI_math_boolean.hh"
25 #include "BLI_math_mpq.hh"
27 #include "BLI_vector.hh"
28 
29 #include "BLI_delaunay_2d.h"
30 
31 namespace blender::meshintersect {
32 
33 /* The spec should have the form:
34  * #verts #edges #faces
35  * <float> <float> [#verts lines)
36  * <int> <int> [#edges lines]
37  * <int> <int> ... <int> [#faces lines]
38  */
39 template<typename T> CDT_input<T> fill_input_from_string(const char *spec)
40 {
41  std::istringstream ss(spec);
42  std::string line;
43  getline(ss, line);
44  std::istringstream hdrss(line);
45  int nverts, nedges, nfaces;
46  hdrss >> nverts >> nedges >> nfaces;
47  if (nverts == 0) {
48  return CDT_input<T>();
49  }
50  Array<vec2<T>> verts(nverts);
51  Array<std::pair<int, int>> edges(nedges);
52  Array<Vector<int>> faces(nfaces);
53  int i = 0;
54  while (i < nverts && getline(ss, line)) {
55  std::istringstream iss(line);
56  double dp0, dp1;
57  iss >> dp0 >> dp1;
58  T p0(dp0);
59  T p1(dp1);
60  verts[i] = vec2<T>(p0, p1);
61  i++;
62  }
63  i = 0;
64  while (i < nedges && getline(ss, line)) {
65  std::istringstream ess(line);
66  int e0, e1;
67  ess >> e0 >> e1;
68  edges[i] = std::pair<int, int>(e0, e1);
69  i++;
70  }
71  i = 0;
72  while (i < nfaces && getline(ss, line)) {
73  std::istringstream fss(line);
74  int v;
75  while (fss >> v) {
76  faces[i].append(v);
77  }
78  i++;
79  }
80  CDT_input<T> ans;
81  ans.vert = verts;
82  ans.edge = edges;
83  ans.face = faces;
84 #ifdef WITH_GMP
85  if (std::is_same<mpq_class, T>::value) {
86  ans.epsilon = T(0);
87  }
88  else {
89  ans.epsilon = T(0.00001);
90  }
91 #else
92  ans.epsilon = T(0.00001);
93 #endif
94  return ans;
95 }
96 
97 /* Find an original index in a table mapping new to original.
98  * Return -1 if not found.
99  */
100 static int get_orig_index(const Array<Vector<int>> &out_to_orig, int orig_index)
101 {
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) {
106  return i;
107  }
108  }
109  }
110  return -1;
111 }
112 
113 template<typename T> static double math_to_double(const T UNUSED(v))
114 {
115  BLI_assert(false); /* Need implementation for other type. */
116  return 0.0;
117 }
118 
119 template<> double math_to_double<double>(const double v)
120 {
121  return v;
122 }
123 
124 #ifdef WITH_GMP
125 template<> double math_to_double<mpq_class>(const mpq_class v)
126 {
127  return v.get_d();
128 }
129 #endif
130 
131 template<typename T> static T math_abs(const T v);
132 
133 #ifdef WITH_GMP
134 template<> mpq_class math_abs(const mpq_class v)
135 {
136  return abs(v);
137 }
138 #endif
139 
140 template<> double math_abs(const double v)
141 {
142  return fabs(v);
143 }
144 
145 /* Find an output index corresponding to a given coordinate (approximately).
146  * Return -1 if not found.
147  */
148 template<typename T> int get_vertex_by_coord(const CDT_result<T> &out, double x, double y)
149 {
150  int nv = static_cast<int>(out.vert.size());
151  for (int i = 0; i < nv; ++i) {
152  double vx = math_to_double(out.vert[i][0]);
153  double vy = math_to_double(out.vert[i][1]);
154  if (fabs(vx - x) <= 1e-5 && fabs(vy - y) <= 1e-5) {
155  return i;
156  }
157  }
158  return -1;
159 }
160 
161 /* Find an edge between two given output vertex indices. -1 if not found, */
162 template<typename T>
163 int get_output_edge_index(const CDT_result<T> &out, int out_index_1, int out_index_2)
164 {
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)) {
169  return i;
170  }
171  }
172  return -1;
173 }
174 
175 template<typename T>
176 bool output_edge_has_input_id(const CDT_result<T> &out, int out_edge_index, int in_edge_index)
177 {
178  return out_edge_index < static_cast<int>(out.edge_orig.size()) &&
179  out.edge_orig[out_edge_index].contains(in_edge_index);
180 }
181 
182 /* Which out face is for a give output vertex ngon? -1 if not found.
183  * Allow for cyclic shifts vertices of one poly vs the other.
184  */
185 template<typename T> int get_output_face_index(const CDT_result<T> &out, const Array<int> &poly)
186 {
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()) {
191  continue;
192  }
193  for (int cycle_start = 0; cycle_start < npolyv; ++cycle_start) {
194  bool ok = true;
195  for (int k = 0; ok && k < npolyv; ++k) {
196  if (out.face[f][(cycle_start + k) % npolyv] != poly[k]) {
197  ok = false;
198  }
199  }
200  if (ok) {
201  return f;
202  }
203  }
204  }
205  return -1;
206 }
207 
208 template<typename T>
209 int get_output_tri_index(const CDT_result<T> &out,
210  int out_index_1,
211  int out_index_2,
212  int out_index_3)
213 {
214  Array<int> tri{out_index_1, out_index_2, out_index_3};
215  return get_output_face_index(out, tri);
216 }
217 
218 template<typename T>
219 bool output_face_has_input_id(const CDT_result<T> &out, int out_face_index, int in_face_index)
220 {
221  return out_face_index < static_cast<int>(out.face_orig.size()) &&
222  out.face_orig[out_face_index].contains(in_face_index);
223 }
224 
225 /* For debugging. */
226 template<typename T> std::ostream &operator<<(std::ostream &os, const CDT_result<T> &r)
227 {
228  os << "\nRESULT\n";
229  os << r.vert.size() << " verts, " << r.edge.size() << " edges, " << r.face.size() << " faces\n";
230  os << "\nVERTS\n";
231  for (int i : r.vert.index_range()) {
232  os << "v" << i << " = " << r.vert[i] << "\n";
233  os << " orig: ";
234  for (int j : r.vert_orig[i].index_range()) {
235  os << r.vert_orig[i][j] << " ";
236  }
237  os << "\n";
238  }
239  os << "\nEDGES\n";
240  for (int i : r.edge.index_range()) {
241  os << "e" << i << " = (" << r.edge[i].first << ", " << r.edge[i].second << ")\n";
242  os << " orig: ";
243  for (int j : r.edge_orig[i].index_range()) {
244  os << r.edge_orig[i][j] << " ";
245  }
246  os << "\n";
247  }
248  os << "\nFACES\n";
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] << " ";
253  }
254  os << "\n";
255  os << " orig: ";
256  for (int j : r.face_orig[i].index_range()) {
257  os << r.face_orig[i][j] << " ";
258  }
259  os << "\n";
260  }
261  return os;
262 }
263 
264 static bool draw_append = false; /* Will be set to true after first call. */
265 
266 template<typename T>
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)
271 {
272  /* Would like to use BKE_tempdir_base() here, but that brings in dependence on kernel library.
273  * This is just for developer debugging anyway, and should never be called in production Blender.
274  */
275 #ifdef WIN32
276  constexpr const char *drawfile = "./cdt_test_draw.html";
277 #else
278  constexpr const char *drawfile = "/tmp/cdt_test_draw.html";
279 #endif
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;
286 
287  if (verts.size() == 0) {
288  return;
289  }
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) {
294  double dvi = math_to_double(v[i]);
295  if (dvi < vmin[i]) {
296  vmin[i] = dvi;
297  }
298  if (dvi > vmax[i]) {
299  vmax[i] = dvi;
300  }
301  }
302  }
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;
308 
309  double width = maxx - minx;
310  double height = maxy - miny;
311  double aspect = height / width;
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);
317  }
318  double scale = view_width / width;
319 
320 #define SX(x) ((math_to_double(x) - minx) * scale)
321 #define SY(y) ((maxy - math_to_double(y)) * scale)
322 
323  std::ofstream f;
324  if (draw_append) {
325  f.open(drawfile, std::ios_base::app);
326  }
327  else {
328  f.open(drawfile);
329  }
330  if (!f) {
331  std::cout << "Could not open file " << drawfile << "\n";
332  return;
333  }
334 
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";
341 
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]) << " ";
347  }
348  f << "\"\n />\n";
349  }
350 
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";
359  f << "</line>\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";
364  }
365  }
366 
367  int i = 0;
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";
372  f << "</circle>\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";
376  }
377  ++i;
378  }
379 
380  draw_append = true;
381 #undef SX
382 #undef SY
383 }
384 
385 /* Should tests draw their output to an html file? */
386 constexpr bool DO_DRAW = false;
387 
388 template<typename T> void expect_coord_near(const vec2<T> &testco, const vec2<T> &refco);
389 
390 #ifdef WITH_GMP
391 template<>
392 void expect_coord_near<mpq_class>(const vec2<mpq_class> &testco, const vec2<mpq_class> &refco)
393 {
394  EXPECT_EQ(testco[0], refco[0]);
395  EXPECT_EQ(testco[0], refco[0]);
396 }
397 #endif
398 
399 template<> void expect_coord_near<double>(const vec2<double> &testco, const vec2<double> &refco)
400 {
401  EXPECT_NEAR(testco[0], refco[0], 1e-5);
402  EXPECT_NEAR(testco[1], refco[1], 1e-5);
403 }
404 
405 #if DO_CPP_TESTS
406 
407 template<typename T> void empty_test()
408 {
409  CDT_input<T> in;
410 
412  EXPECT_EQ(0, out.vert.size());
413  EXPECT_EQ(0, out.edge.size());
414  EXPECT_EQ(0, out.face.size());
415  EXPECT_EQ(0, out.vert_orig.size());
416  EXPECT_EQ(0, out.edge_orig.size());
417  EXPECT_EQ(0, out.face_orig.size());
418 }
419 
420 template<typename T> void onept_test()
421 {
422  const char *spec = R"(1 0 0
423  0.0 0.0
424  )";
425 
426  CDT_input<T> in = fill_input_from_string<T>(spec);
428  EXPECT_EQ(out.vert.size(), 1);
429  EXPECT_EQ(out.edge.size(), 0);
430  EXPECT_EQ(out.face.size(), 0);
431  if (out.vert.size() >= 1) {
432  expect_coord_near<T>(out.vert[0], vec2<T>(0, 0));
433  }
434 }
435 
436 template<typename T> void twopt_test()
437 {
438  const char *spec = R"(2 0 0
439  0.0 -0.75
440  0.0 0.75
441  )";
442 
443  CDT_input<T> in = fill_input_from_string<T>(spec);
445  EXPECT_EQ(out.vert.size(), 2);
446  EXPECT_EQ(out.edge.size(), 1);
447  EXPECT_EQ(out.face.size(), 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));
456  }
457  int e0_out = get_output_edge_index(out, v0_out, v1_out);
458  EXPECT_EQ(e0_out, 0);
459  if (DO_DRAW) {
460  graph_draw<T>("TwoPt", out.vert, out.edge, out.face);
461  }
462 }
463 
464 template<typename T> void threept_test()
465 {
466  const char *spec = R"(3 0 0
467  -0.1 -0.75
468  0.1 0.75
469  0.5 0.5
470  )";
471 
472  CDT_input<T> in = fill_input_from_string<T>(spec);
474  EXPECT_EQ(out.vert.size(), 3);
475  EXPECT_EQ(out.edge.size(), 3);
476  EXPECT_EQ(out.face.size(), 1);
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);
488  EXPECT_EQ(f0_out, 0);
489  if (DO_DRAW) {
490  graph_draw<T>("ThreePt", out.vert, out.edge, out.face);
491  }
492 }
493 
494 template<typename T> void mixedpts_test()
495 {
496  /* Edges form a chain of length 3. */
497  const char *spec = R"(4 3 0
498  0.0 0.0
499  -0.5 -0.5
500  -0.4 -0.25
501  -0.3 0.8
502  0 1
503  1 2
504  2 3
505  )";
506 
507  CDT_input<T> in = fill_input_from_string<T>(spec);
509  EXPECT_EQ(out.vert.size(), 4);
510  EXPECT_EQ(out.edge.size(), 6);
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));
523  if (DO_DRAW) {
524  graph_draw<T>("MixedPts", out.vert, out.edge, out.face);
525  }
526 }
527 
528 template<typename T> void quad0_test()
529 {
530  const char *spec = R"(4 0 0
531  0.0 1.0
532  1.0 0.0
533  2.0 0.1
534  2.25 0.5
535  )";
536 
537  CDT_input<T> in = fill_input_from_string<T>(spec);
539  EXPECT_EQ(out.vert.size(), 4);
540  EXPECT_EQ(out.edge.size(), 5);
541  int e_diag_out = get_output_edge_index(out, 1, 3);
542  EXPECT_NE(e_diag_out, -1);
543  if (DO_DRAW) {
544  graph_draw<T>("Quad0", out.vert, out.edge, out.face);
545  }
546 }
547 
548 template<typename T> void quad1_test()
549 {
550  const char *spec = R"(4 0 0
551  0.0 0.0
552  0.9 -1.0
553  2.0 0.0
554  0.9 3.0
555  )";
556 
557  CDT_input<T> in = fill_input_from_string<T>(spec);
559  EXPECT_EQ(out.vert.size(), 4);
560  EXPECT_EQ(out.edge.size(), 5);
561  int e_diag_out = get_output_edge_index(out, 0, 2);
562  EXPECT_NE(e_diag_out, -1);
563  if (DO_DRAW) {
564  graph_draw<T>("Quad1", out.vert, out.edge, out.face);
565  }
566 }
567 
568 template<typename T> void quad2_test()
569 {
570  const char *spec = R"(4 0 0
571  0.5 0.0
572  0.15 0.2
573  0.3 0.4
574  .45 0.35
575  )";
576 
577  CDT_input<T> in = fill_input_from_string<T>(spec);
579  EXPECT_EQ(out.vert.size(), 4);
580  EXPECT_EQ(out.edge.size(), 5);
581  int e_diag_out = get_output_edge_index(out, 1, 3);
582  EXPECT_NE(e_diag_out, -1);
583  if (DO_DRAW) {
584  graph_draw<T>("Quad2", out.vert, out.edge, out.face);
585  }
586 }
587 
588 template<typename T> void quad3_test()
589 {
590  const char *spec = R"(4 0 0
591  0.5 0.0
592  0.0 0.0
593  0.3 0.4
594  .45 0.35
595  )";
596 
597  CDT_input<T> in = fill_input_from_string<T>(spec);
599  EXPECT_EQ(out.vert.size(), 4);
600  EXPECT_EQ(out.edge.size(), 5);
601  int e_diag_out = get_output_edge_index(out, 0, 2);
602  EXPECT_NE(e_diag_out, -1);
603  if (DO_DRAW) {
604  graph_draw<T>("Quad3", out.vert, out.edge, out.face);
605  }
606 }
607 
608 template<typename T> void quad4_test()
609 {
610  const char *spec = R"(4 0 0
611  1.0 1.0
612  0.0 0.0
613  1.0 -3.0
614  0.0 1.0
615  )";
616 
617  CDT_input<T> in = fill_input_from_string<T>(spec);
619  EXPECT_EQ(out.vert.size(), 4);
620  EXPECT_EQ(out.edge.size(), 5);
621  int e_diag_out = get_output_edge_index(out, 0, 1);
622  EXPECT_NE(e_diag_out, -1);
623  if (DO_DRAW) {
624  graph_draw<T>("Quad4", out.vert, out.edge, out.face);
625  }
626 }
627 
628 template<typename T> void lineinsquare_test()
629 {
630  const char *spec = R"(6 1 1
631  -0.5 -0.5
632  0.5 -0.5
633  -0.5 0.5
634  0.5 0.5
635  -0.25 0.0
636  0.25 0.0
637  4 5
638  0 1 3 2
639  )";
640 
641  CDT_input<T> in = fill_input_from_string<T>(spec);
643  EXPECT_EQ(out.vert.size(), 6);
644  EXPECT_EQ(out.face.size(), 6);
645  if (DO_DRAW) {
646  graph_draw<T>("LineInSquare - full", out.vert, out.edge, out.face);
647  }
649  EXPECT_EQ(out2.vert.size(), 6);
650  EXPECT_EQ(out2.face.size(), 1);
651  if (DO_DRAW) {
652  graph_draw<T>("LineInSquare - constraints", out2.vert, out2.edge, out2.face);
653  }
655  EXPECT_EQ(out3.vert.size(), 6);
656  EXPECT_EQ(out3.face.size(), 6);
657  if (DO_DRAW) {
658  graph_draw<T>("LineInSquare - inside with holes", out3.vert, out3.edge, out3.face);
659  }
661  EXPECT_EQ(out4.vert.size(), 6);
662  EXPECT_EQ(out4.face.size(), 2);
663  if (DO_DRAW) {
664  graph_draw<T>("LineInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
665  }
666 }
667 
668 template<typename T> void lineholeinsquare_test()
669 {
670  const char *spec = R"(10 1 2
671  -0.5 -0.5
672  0.5 -0.5
673  -0.5 0.5
674  0.5 0.5
675  -0.25 0.0
676  0.25 0.0
677  -0.4 -0.4
678  0.4 -0.4
679  0.4 -0.3
680  -0.4 -0.3
681  4 5
682  0 1 3 2
683  6 7 8 9
684  )";
685 
686  CDT_input<T> in = fill_input_from_string<T>(spec);
688  EXPECT_EQ(out.vert.size(), 10);
689  EXPECT_EQ(out.face.size(), 14);
690  if (DO_DRAW) {
691  graph_draw<T>("LineHoleInSquare - full", out.vert, out.edge, out.face);
692  }
694  EXPECT_EQ(out2.vert.size(), 10);
695  EXPECT_EQ(out2.face.size(), 2);
696  if (DO_DRAW) {
697  graph_draw<T>("LineHoleInSquare - constraints", out2.vert, out2.edge, out2.face);
698  }
700  EXPECT_EQ(out3.vert.size(), 10);
701  EXPECT_EQ(out3.face.size(), 12);
702  if (DO_DRAW) {
703  graph_draw<T>("LineHoleInSquare - inside with holes", out3.vert, out3.edge, out3.face);
704  }
706  EXPECT_EQ(out4.vert.size(), 10);
707  EXPECT_EQ(out4.face.size(), 2);
708  if (DO_DRAW) {
709  graph_draw<T>("LineHoleInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
710  }
711 }
712 
713 template<typename T> void nestedholes_test()
714 {
715  const char *spec = R"(12 0 3
716  -0.5 -0.5
717  0.5 -0.5
718  -0.5 0.5
719  0.5 0.5
720  -0.4 -0.4
721  0.4 -0.4
722  0.4 0.4
723  -0.4 0.4
724  -0.2 -0.2
725  0.2 -0.2
726  0.2 0.2
727  -0.2 0.2
728  0 1 3 2
729  4 7 6 5
730  8 9 10 11
731  )";
732 
733  CDT_input<T> in = fill_input_from_string<T>(spec);
735  EXPECT_EQ(out.vert.size(), 12);
736  EXPECT_EQ(out.face.size(), 18);
737  if (DO_DRAW) {
738  graph_draw<T>("NestedHoles - full", out.vert, out.edge, out.face);
739  }
741  EXPECT_EQ(out2.vert.size(), 12);
742  EXPECT_EQ(out2.face.size(), 3);
743  if (DO_DRAW) {
744  graph_draw<T>("NestedHoles - constraints", out2.vert, out2.edge, out2.face);
745  }
747  EXPECT_EQ(out3.vert.size(), 12);
748  EXPECT_EQ(out3.face.size(), 10);
749  if (DO_DRAW) {
750  graph_draw<T>("NestedHoles - inside with holes", out3.vert, out3.edge, out3.face);
751  }
753  EXPECT_EQ(out4.vert.size(), 12);
754  EXPECT_EQ(out4.face.size(), 3);
755  if (DO_DRAW) {
756  graph_draw<T>("NestedHoles - valid bmesh with holes", out4.vert, out4.edge, out4.face);
757  }
758 }
759 
760 template<typename T> void crosssegs_test()
761 {
762  const char *spec = R"(4 2 0
763  -0.5 0.0
764  0.5 0.0
765  -0.4 -0.5
766  0.4 0.5
767  0 1
768  2 3
769  )";
770 
771  CDT_input<T> in = fill_input_from_string<T>(spec);
773  EXPECT_EQ(out.vert.size(), 5);
774  EXPECT_EQ(out.edge.size(), 8);
775  EXPECT_EQ(out.face.size(), 4);
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)) {
785  EXPECT_EQ(v_intersect, -1);
786  v_intersect = i;
787  }
788  }
789  EXPECT_NE(v_intersect, -1);
790  if (v_intersect != -1) {
791  expect_coord_near<T>(out.vert[v_intersect], vec2<T>(0, 0));
792  }
793  }
794  if (DO_DRAW) {
795  graph_draw<T>("CrossSegs", out.vert, out.edge, out.face);
796  }
797 }
798 
799 template<typename T> void cutacrosstri_test()
800 {
801  /* Right triangle with horizontal segment exactly crossing in the middle. */
802  const char *spec = R"(5 1 1
803  0.0 0.0
804  1.0 0.0
805  0.0 1.0
806  0.0 0.5
807  0.5 0.5
808  3 4
809  0 1 2
810  )";
811 
812  CDT_input<T> in = fill_input_from_string<T>(spec);
814  EXPECT_EQ(out.vert.size(), 5);
815  EXPECT_EQ(out.edge.size(), 7);
816  EXPECT_EQ(out.face.size(), 3);
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) {
833  EXPECT_EQ(e0_out, get_orig_index(out.edge_orig, 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);
836  }
837  int e_diag = get_output_edge_index(out, v0_out, v4_out);
838  EXPECT_NE(e_diag, -1);
839  if (e_diag != -1) {
840  EXPECT_EQ(out.edge_orig[e_diag].size(), 0);
841  }
842  }
843  if (DO_DRAW) {
844  graph_draw<T>("CutAcrossTri", out.vert, out.edge, out.face);
845  }
846 }
847 
848 template<typename T> void diamondcross_test()
849 {
850  /* Diamond with constraint edge from top to bottom. Some dup verts. */
851  const char *spec = R"(7 5 0
852  0.0 0.0
853  1.0 3.0
854  2.0 0.0
855  1.0 -3.0
856  0.0 0.0
857  1.0 -3.0
858  1.0 3.0
859  0 1
860  1 2
861  2 3
862  3 4
863  5 6
864  )";
865 
866  CDT_input<T> in = fill_input_from_string<T>(spec);
868  EXPECT_EQ(out.vert.size(), 4);
869  EXPECT_EQ(out.edge.size(), 5);
870  EXPECT_EQ(out.face.size(), 2);
871  if (DO_DRAW) {
872  graph_draw<T>("DiamondCross", out.vert, out.edge, out.face);
873  }
874 }
875 
876 template<typename T> void twodiamondscross_test()
877 {
878  const char *spec = R"(12 9 0
879  0.0 0.0
880  1.0 2.0
881  2.0 0.0
882  1.0 -2.0
883  0.0 0.0
884  3.0 0.0
885  4.0 2.0
886  5.0 0.0
887  4.0 -2.0
888  3.0 0.0
889  0.0 0.0
890  5.0 0.0
891  0 1
892  1 2
893  2 3
894  3 4
895  5 6
896  6 7
897  7 8
898  8 9
899  10 11
900  )";
901 
902  CDT_input<T> in = fill_input_from_string<T>(spec);
904  EXPECT_EQ(out.vert.size(), 8);
905  EXPECT_EQ(out.edge.size(), 15);
906  EXPECT_EQ(out.face.size(), 8);
907  if (out.vert.size() == 8 && out.edge.size() == 15 && out.face.size() == 8) {
908  int v_out[12];
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);
912  }
913  EXPECT_EQ(v_out[0], v_out[4]);
914  EXPECT_EQ(v_out[0], v_out[10]);
915  EXPECT_EQ(v_out[5], v_out[9]);
916  EXPECT_EQ(v_out[7], v_out[11]);
917  int e_out[9];
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);
921  }
922  /* there won't be a single edge for the input cross edge, but rather 3 */
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));
931  }
932  if (DO_DRAW) {
933  graph_draw<T>("TwoDiamondsCross", out.vert, out.edge, out.face);
934  }
935 }
936 
937 template<typename T> void manycross_test()
938 {
939  /* Input has some repetition of vertices, on purpose */
940  const char *spec = R"(27 21 0
941  0.0 0.0
942  6.0 9.0
943  15.0 18.0
944  35.0 13.0
945  43.0 18.0
946  57.0 12.0
947  69.0 10.0
948  78.0 0.0
949  91.0 0.0
950  107.0 22.0
951  123.0 0.0
952  0.0 0.0
953  10.0 -14.0
954  35.0 -8.0
955  43.0 -12.0
956  64.0 -13.0
957  78.0 0.0
958  91.0 0.0
959  102.0 -9.0
960  116.0 -9.0
961  123.0 0.0
962  43.0 18.0
963  43.0 -12.0
964  107.0 22.0
965  102.0 -9.0
966  0.0 0.0
967  123.0 0.0
968  0 1
969  1 2
970  2 3
971  3 4
972  4 5
973  5 6
974  6 7
975  7 8
976  8 9
977  9 10
978  11 12
979  12 13
980  13 14
981  14 15
982  15 16
983  17 18
984  18 19
985  19 20
986  21 22
987  23 24
988  25 26
989  )";
990 
991  CDT_input<T> in = fill_input_from_string<T>(spec);
993  EXPECT_EQ(out.vert.size(), 19);
994  EXPECT_EQ(out.edge.size(), 46);
995  EXPECT_EQ(out.face.size(), 28);
996  if (DO_DRAW) {
997  graph_draw<T>("ManyCross", out.vert, out.edge, out.face);
998  }
999 }
1000 
1001 template<typename T> void twoface_test()
1002 {
1003  const char *spec = R"(6 0 2
1004  0.0 0.0
1005  1.0 0.0
1006  0.5 1.0
1007  1.1 1.0
1008  1.1 0.0
1009  1.6 1.0
1010  0 1 2
1011  3 4 5
1012  )";
1013 
1014  CDT_input<T> in = fill_input_from_string<T>(spec);
1016  EXPECT_EQ(out.vert.size(), 6);
1017  EXPECT_EQ(out.edge.size(), 9);
1018  EXPECT_EQ(out.face.size(), 4);
1019  if (out.vert.size() == 6 && out.edge.size() == 9 && out.face.size() == 4) {
1020  int v_out[6];
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);
1024  }
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));
1040  }
1041  if (DO_DRAW) {
1042  graph_draw<T>("TwoFace", out.vert, out.edge, out.face);
1043  }
1044 }
1045 
1046 template<typename T> void twoface2_test()
1047 {
1048  const char *spec = R"(6 0 2
1049  0.0 0.0
1050  4.0 4.0
1051  -4.0 2.0
1052  3.0 0.0
1053  3.0 6.0
1054  -1.0 2.0
1055  0 1 2
1056  3 4 5
1057  )";
1058 
1059  CDT_input<T> in = fill_input_from_string<T>(spec);
1061  EXPECT_EQ(out.vert.size(), 10);
1062  EXPECT_EQ(out.edge.size(), 18);
1063  EXPECT_EQ(out.face.size(), 9);
1064  if (out.vert.size() == 10 && out.edge.size() == 18 && out.face.size() == 9) {
1065  /* Input verts have no dups, so expect output ones match input ones. */
1066  for (int i = 0; i < 6; i++) {
1067  EXPECT_EQ(get_orig_index(out.vert_orig, i), i);
1068  }
1069  int v6 = get_vertex_by_coord(out, 3.0, 3.0);
1070  EXPECT_NE(v6, -1);
1071  int v7 = get_vertex_by_coord(out, 3.0, 3.75);
1072  EXPECT_NE(v7, -1);
1073  int v8 = get_vertex_by_coord(out, 0.0, 3.0);
1074  EXPECT_NE(v8, -1);
1075  int v9 = get_vertex_by_coord(out, 1.0, 1.0);
1076  EXPECT_NE(v9, -1);
1077  /* f0 to f3 should be triangles part of input face 0, not part of input face 1. */
1078  int f0 = get_output_tri_index(out, 0, 9, 5);
1079  EXPECT_NE(f0, -1);
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);
1083  EXPECT_NE(f1, -1);
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);
1087  EXPECT_NE(f2, -1);
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);
1091  EXPECT_NE(f3, -1);
1092  EXPECT_TRUE(output_face_has_input_id(out, f3, 0));
1093  EXPECT_FALSE(output_face_has_input_id(out, f3, 1));
1094  /* f4 and f5 should be triangles part of input face 1, not part of input face 0. */
1095  int f4 = get_output_tri_index(out, 8, 7, 4);
1096  EXPECT_NE(f4, -1);
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);
1100  EXPECT_NE(f5, -1);
1101  EXPECT_FALSE(output_face_has_input_id(out, f5, 0));
1102  EXPECT_TRUE(output_face_has_input_id(out, f5, 1));
1103  /* f6 to f8 should be triangles part of both input faces. */
1104  int f6 = get_output_tri_index(out, 5, 9, 6);
1105  EXPECT_NE(f6, -1);
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);
1109  EXPECT_NE(f7, -1);
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);
1113  EXPECT_NE(f8, -1);
1114  EXPECT_TRUE(output_face_has_input_id(out, f8, 0));
1115  EXPECT_TRUE(output_face_has_input_id(out, f8, 1));
1116  }
1117  if (DO_DRAW) {
1118  graph_draw<T>("TwoFace2", out.vert, out.edge, out.face);
1119  }
1120 }
1121 
1122 template<typename T> void overlapfaces_test()
1123 {
1124  const char *spec = R"(12 0 3
1125  0.0 0.0
1126  1.0 0.0
1127  1.0 1.0
1128  0.0 1.0
1129  0.5 0.5
1130  1.5 0.5
1131  1.5 1.3
1132  0.5 1.3
1133  0.1 0.1
1134  0.3 0.1
1135  0.3 0.3
1136  0.1 0.3
1137  0 1 2 3
1138  4 5 6 7
1139  8 9 10 11
1140  )";
1141 
1142  CDT_input<T> in = fill_input_from_string<T>(spec);
1144  EXPECT_EQ(out.vert.size(), 14);
1145  EXPECT_EQ(out.edge.size(), 33);
1146  EXPECT_EQ(out.face.size(), 20);
1147  if (out.vert.size() == 14 && out.edge.size() == 33 && out.face.size() == 20) {
1148  int v_out[12];
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);
1152  }
1153  int v_int1 = 12;
1154  int v_int2 = 13;
1155  T x = out.vert[v_int1][0] - T(1);
1156  if (math_abs(x) > in.epsilon) {
1157  v_int1 = 13;
1158  v_int2 = 12;
1159  }
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));
1162  EXPECT_EQ(out.vert_orig[v_int1].size(), 0);
1163  EXPECT_EQ(out.vert_orig[v_int2].size(), 0);
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]);
1172  if (f2_out == -1) {
1173  f2_out = get_output_tri_index(out, v_out[8], v_out[9], v_out[11]);
1174  }
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));
1178  }
1179  if (DO_DRAW) {
1180  graph_draw<T>("OverlapFaces - full", out.vert, out.edge, out.face);
1181  }
1182 
1183  /* Different output types. */
1185  EXPECT_EQ(out2.face.size(), 18);
1186  if (DO_DRAW) {
1187  graph_draw<T>("OverlapFaces - inside", out2.vert, out2.edge, out2.face);
1188  }
1189 
1191  EXPECT_EQ(out3.face.size(), 14);
1192  if (DO_DRAW) {
1193  graph_draw<T>("OverlapFaces - inside with holes", out3.vert, out3.edge, out3.face);
1194  }
1195 
1197  EXPECT_EQ(out4.face.size(), 4);
1198  if (DO_DRAW) {
1199  graph_draw<T>("OverlapFaces - constraints", out4.vert, out4.edge, out4.face);
1200  }
1201 
1203  EXPECT_EQ(out5.face.size(), 5);
1204  if (DO_DRAW) {
1205  graph_draw<T>("OverlapFaces - valid bmesh", out5.vert, out5.edge, out5.face);
1206  }
1207 
1209  EXPECT_EQ(out6.face.size(), 3);
1210  if (DO_DRAW) {
1211  graph_draw<T>("OverlapFaces - valid bmesh with holes", out6.vert, out6.edge, out6.face);
1212  }
1213 }
1214 
1215 template<typename T> void twosquaresoverlap_test()
1216 {
1217  const char *spec = R"(8 0 2
1218  1.0 -1.0
1219  -1.0 -1.0
1220  -1.0 1.0
1221  1.0 1.0
1222  -1.5 1.5
1223  0.5 1.5
1224  0.5 -0.5
1225  -1.5 -0.5
1226  7 6 5 4
1227  3 2 1 0
1228  )";
1229 
1230  CDT_input<T> in = fill_input_from_string<T>(spec);
1232  EXPECT_EQ(out.vert.size(), 10);
1233  EXPECT_EQ(out.edge.size(), 12);
1234  EXPECT_EQ(out.face.size(), 3);
1235  if (DO_DRAW) {
1236  graph_draw<T>("TwoSquaresOverlap", out.vert, out.edge, out.face);
1237  }
1238 }
1239 
1240 template<typename T> void twofaceedgeoverlap_test()
1241 {
1242  const char *spec = R"(6 0 2
1243  5.657 0.0
1244  -1.414 -5.831
1245  0.0 0.0
1246  5.657 0.0
1247  -2.121 -2.915
1248  0.0 0.0
1249  2 1 0
1250  5 4 3
1251  )";
1252 
1253  CDT_input<T> in = fill_input_from_string<T>(spec);
1255  EXPECT_EQ(out.vert.size(), 5);
1256  EXPECT_EQ(out.edge.size(), 7);
1257  EXPECT_EQ(out.face.size(), 3);
1258  if (out.vert.size() == 5 && out.edge.size() == 7 && out.face.size() == 3) {
1259  int v_int = 4;
1260  int v_out[6];
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);
1265  }
1266  EXPECT_EQ(v_out[0], v_out[3]);
1267  EXPECT_EQ(v_out[2], v_out[5]);
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));
1296  }
1297  if (DO_DRAW) {
1298  graph_draw<T>("TwoFaceEdgeOverlap", out.vert, out.edge, out.face);
1299  }
1300 }
1301 
1302 template<typename T> void triintri_test()
1303 {
1304  const char *spec = R"(6 0 2
1305  -5.65685 0.0
1306  1.41421 -5.83095
1307  0.0 0.0
1308  -2.47487 -1.45774
1309  -0.707107 -2.91548
1310  -1.06066 -1.45774
1311  0 1 2
1312  3 4 5
1313  )";
1314 
1315  CDT_input<T> in = fill_input_from_string<T>(spec);
1317  EXPECT_EQ(out.vert.size(), 6);
1318  EXPECT_EQ(out.edge.size(), 8);
1319  EXPECT_EQ(out.face.size(), 3);
1320  if (DO_DRAW) {
1321  graph_draw<T>("TriInTri", out.vert, out.edge, out.face);
1322  }
1323 }
1324 
1325 template<typename T> void diamondinsquare_test()
1326 {
1327  const char *spec = R"(8 0 2
1328  0.0 0.0
1329  1.0 0.0
1330  1.0 1.0
1331  0.0 1.0
1332  0.14644660940672627 0.5
1333  0.5 0.14644660940672627
1334  0.8535533905932737 0.5
1335  0.5 0.8535533905932737
1336  0 1 2 3
1337  4 5 6 7
1338  )";
1339 
1340  CDT_input<T> in = fill_input_from_string<T>(spec);
1342  EXPECT_EQ(out.vert.size(), 8);
1343  EXPECT_EQ(out.edge.size(), 10);
1344  EXPECT_EQ(out.face.size(), 3);
1345  if (DO_DRAW) {
1346  graph_draw<T>("DiamondInSquare", out.vert, out.edge, out.face);
1347  }
1348 }
1349 
1350 template<typename T> void diamondinsquarewire_test()
1351 {
1352  const char *spec = R"(8 8 0
1353  0.0 0.0
1354  1.0 0.0
1355  1.0 1.0
1356  0.0 1.0
1357  0.14644660940672627 0.5
1358  0.5 0.14644660940672627
1359  0.8535533905932737 0.5
1360  0.5 0.8535533905932737
1361  0 1
1362  1 2
1363  2 3
1364  3 0
1365  4 5
1366  5 6
1367  6 7
1368  7 4
1369  )";
1370 
1371  CDT_input<T> in = fill_input_from_string<T>(spec);
1373  EXPECT_EQ(out.vert.size(), 8);
1374  EXPECT_EQ(out.edge.size(), 8);
1375  EXPECT_EQ(out.face.size(), 2);
1376  if (DO_DRAW) {
1377  graph_draw<T>("DiamondInSquareWire", out.vert, out.edge, out.face);
1378  }
1379 }
1380 
1381 template<typename T> void repeatedge_test()
1382 {
1383  const char *spec = R"(5 3 0
1384  0.0 0.0
1385  0.0 1.0
1386  1.0 1.1
1387  0.5 -0.5
1388  0.5 2.5
1389  0 1
1390  2 3
1391  2 3
1392  )";
1393 
1394  CDT_input<T> in = fill_input_from_string<T>(spec);
1396  EXPECT_EQ(out.edge.size(), 2);
1397  if (DO_DRAW) {
1398  graph_draw<T>("RepeatEdge", out.vert, out.edge, out.face);
1399  }
1400 }
1401 
1402 template<typename T> void repeattri_test()
1403 {
1404  const char *spec = R"(3 0 2
1405  0.0 0.0
1406  1.0 0.0
1407  0.5 1.0
1408  0 1 2
1409  0 1 2
1410  )";
1411 
1412  CDT_input<T> in = fill_input_from_string<T>(spec);
1414  EXPECT_EQ(out.edge.size(), 3);
1415  EXPECT_EQ(out.face.size(), 1);
1416  EXPECT_TRUE(output_face_has_input_id(out, 0, 0));
1417  EXPECT_TRUE(output_face_has_input_id(out, 0, 1));
1418  if (DO_DRAW) {
1419  graph_draw<T>("RepeatTri", out.vert, out.edge, out.face);
1420  }
1421 }
1422 
1423 template<typename T> void square_o_test()
1424 {
1425  const char *spec = R"(8 0 2
1426  0.0 0.0
1427  1.0 0.0
1428  1.0 1.0
1429  0.0 1.0
1430  0.2 0.2
1431  0.2 0.8
1432  0.8 0.8
1433  0.8 0.2
1434  0 1 2 3
1435  4 5 6 7
1436  )";
1437  CDT_input<T> in = fill_input_from_string<T>(spec);
1439  EXPECT_EQ(out1.face.size(), 8);
1440  if (DO_DRAW) {
1441  graph_draw<T>("Square O - inside with holes", out1.vert, out1.edge, out1.face);
1442  }
1443 
1445  EXPECT_EQ(out2.face.size(), 2);
1446  if (DO_DRAW) {
1447  graph_draw<T>("Square O - valid bmesh with holes", out2.vert, out2.edge, out2.face);
1448  }
1449 }
1450 
1451 TEST(delaunay_d, Empty)
1452 {
1453  empty_test<double>();
1454 }
1455 
1456 TEST(delaunay_d, OnePt)
1457 {
1458  onept_test<double>();
1459 }
1460 
1461 TEST(delaunay_d, TwoPt)
1462 {
1463  twopt_test<double>();
1464 }
1465 
1466 TEST(delaunay_d, ThreePt)
1467 {
1468  threept_test<double>();
1469 }
1470 
1471 TEST(delaunay_d, MixedPts)
1472 {
1473  mixedpts_test<double>();
1474 }
1475 
1476 TEST(delaunay_d, Quad0)
1477 {
1478  quad0_test<double>();
1479 }
1480 
1481 TEST(delaunay_d, Quad1)
1482 {
1483  quad1_test<double>();
1484 }
1485 
1486 TEST(delaunay_d, Quad2)
1487 {
1488  quad2_test<double>();
1489 }
1490 
1491 TEST(delaunay_d, Quad3)
1492 {
1493  quad3_test<double>();
1494 }
1495 
1496 TEST(delaunay_d, Quad4)
1497 {
1498  quad4_test<double>();
1499 }
1500 
1501 TEST(delaunay_d, LineInSquare)
1502 {
1503  lineinsquare_test<double>();
1504 }
1505 
1506 TEST(delaunay_d, LineHoleInSquare)
1507 {
1508  lineholeinsquare_test<double>();
1509 }
1510 
1511 TEST(delaunay_d, NestedHoles)
1512 {
1513  nestedholes_test<double>();
1514 }
1515 
1516 TEST(delaunay_d, CrossSegs)
1517 {
1518  crosssegs_test<double>();
1519 }
1520 
1521 TEST(delaunay_d, CutAcrossTri)
1522 {
1523  cutacrosstri_test<double>();
1524 }
1525 
1526 TEST(delaunay_d, DiamondCross)
1527 {
1528  diamondcross_test<double>();
1529 }
1530 
1531 TEST(delaunay_d, TwoDiamondsCross)
1532 {
1533  twodiamondscross_test<double>();
1534 }
1535 
1536 TEST(delaunay_d, ManyCross)
1537 {
1538  manycross_test<double>();
1539 }
1540 
1541 TEST(delaunay_d, TwoFace)
1542 {
1543  twoface_test<double>();
1544 }
1545 
1546 TEST(delaunay_d, TwoFace2)
1547 {
1548  twoface2_test<double>();
1549 }
1550 
1551 TEST(delaunay_d, OverlapFaces)
1552 {
1553  overlapfaces_test<double>();
1554 }
1555 
1556 TEST(delaunay_d, TwoSquaresOverlap)
1557 {
1558  twosquaresoverlap_test<double>();
1559 }
1560 
1561 TEST(delaunay_d, TwoFaceEdgeOverlap)
1562 {
1563  twofaceedgeoverlap_test<double>();
1564 }
1565 
1566 TEST(delaunay_d, TriInTri)
1567 {
1568  triintri_test<double>();
1569 }
1570 
1571 TEST(delaunay_d, DiamondInSquare)
1572 {
1573  diamondinsquare_test<double>();
1574 }
1575 
1576 TEST(delaunay_d, DiamondInSquareWire)
1577 {
1578  diamondinsquarewire_test<double>();
1579 }
1580 
1581 TEST(delaunay_d, RepeatEdge)
1582 {
1583  repeatedge_test<double>();
1584 }
1585 
1586 TEST(delaunay_d, RepeatTri)
1587 {
1588  repeattri_test<double>();
1589 }
1590 
1591 TEST(delaunay_d, SquareO)
1592 {
1593  square_o_test<double>();
1594 }
1595 
1596 # ifdef WITH_GMP
1597 TEST(delaunay_m, Empty)
1598 {
1599  empty_test<mpq_class>();
1600 }
1601 
1602 TEST(delaunay_m, OnePt)
1603 {
1604  onept_test<mpq_class>();
1605 }
1606 TEST(delaunay_m, TwoPt)
1607 {
1608  twopt_test<mpq_class>();
1609 }
1610 
1611 TEST(delaunay_m, ThreePt)
1612 {
1613  threept_test<mpq_class>();
1614 }
1615 
1616 TEST(delaunay_m, MixedPts)
1617 {
1618  mixedpts_test<mpq_class>();
1619 }
1620 
1621 TEST(delaunay_m, Quad0)
1622 {
1623  quad0_test<mpq_class>();
1624 }
1625 
1626 TEST(delaunay_m, Quad1)
1627 {
1628  quad1_test<mpq_class>();
1629 }
1630 
1631 TEST(delaunay_m, Quad2)
1632 {
1633  quad2_test<mpq_class>();
1634 }
1635 
1636 TEST(delaunay_m, Quad3)
1637 {
1638  quad3_test<mpq_class>();
1639 }
1640 
1641 TEST(delaunay_m, Quad4)
1642 {
1643  quad4_test<mpq_class>();
1644 }
1645 
1646 TEST(delaunay_m, LineInSquare)
1647 {
1648  lineinsquare_test<mpq_class>();
1649 }
1650 
1651 TEST(delaunay_m, LineHoleInSquare)
1652 {
1653  lineholeinsquare_test<mpq_class>();
1654 }
1655 
1656 TEST(delaunay_m, NestedHoles)
1657 {
1658  nestedholes_test<mpq_class>();
1659 }
1660 
1661 TEST(delaunay_m, CrossSegs)
1662 {
1663  crosssegs_test<mpq_class>();
1664 }
1665 
1666 TEST(delaunay_m, CutAcrossTri)
1667 {
1668  cutacrosstri_test<mpq_class>();
1669 }
1670 
1671 TEST(delaunay_m, DiamondCross)
1672 {
1673  diamondcross_test<mpq_class>();
1674 }
1675 
1676 TEST(delaunay_m, TwoDiamondsCross)
1677 {
1678  twodiamondscross_test<mpq_class>();
1679 }
1680 
1681 TEST(delaunay_m, ManyCross)
1682 {
1683  manycross_test<mpq_class>();
1684 }
1685 
1686 TEST(delaunay_m, TwoFace)
1687 {
1688  twoface_test<mpq_class>();
1689 }
1690 
1691 TEST(delaunay_m, TwoFace2)
1692 {
1693  twoface2_test<mpq_class>();
1694 }
1695 
1696 TEST(delaunay_m, OverlapFaces)
1697 {
1698  overlapfaces_test<mpq_class>();
1699 }
1700 
1701 TEST(delaunay_m, TwoSquaresOverlap)
1702 {
1703  twosquaresoverlap_test<mpq_class>();
1704 }
1705 
1706 TEST(delaunay_m, TwoFaceEdgeOverlap)
1707 {
1708  twofaceedgeoverlap_test<mpq_class>();
1709 }
1710 
1711 TEST(delaunay_m, TriInTri)
1712 {
1713  triintri_test<mpq_class>();
1714 }
1715 
1716 TEST(delaunay_m, DiamondInSquare)
1717 {
1718  diamondinsquare_test<mpq_class>();
1719 }
1720 
1721 TEST(delaunay_m, DiamondInSquareWire)
1722 {
1723  diamondinsquarewire_test<mpq_class>();
1724 }
1725 
1726 TEST(delaunay_m, RepeatEdge)
1727 {
1728  repeatedge_test<mpq_class>();
1729 }
1730 
1731 TEST(delaunay_m, RepeatTri)
1732 {
1733  repeattri_test<mpq_class>();
1734 }
1735 # endif
1736 #endif
1737 
1738 #if DO_C_TESTS
1739 
1740 TEST(delaunay_d, CintTwoFace)
1741 {
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};
1747 
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;
1754  input.faces = faces;
1755  input.faces_len_table = faces_len;
1756  input.faces_start_table = faces_start;
1757  input.epsilon = 1e-5f;
1758  input.need_ids = false;
1761 }
1762 
1763 TEST(delaunay_d, CintTwoFaceNoIds)
1764 {
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};
1770 
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;
1777  input.faces = faces;
1778  input.faces_len_table = faces_len;
1779  input.faces_start_table = faces_start;
1780  input.epsilon = 1e-5f;
1781  input.need_ids = true;
1784 }
1785 
1786 #endif
1787 
1788 #if DO_TEXT_TESTS
1789 template<typename T>
1790 void text_test(
1791  int arc_points_num, int lets_per_line_num, int lines_num, CDT_output_type otype, bool need_ids)
1792 {
1793  constexpr bool print_timing = true;
1794  /*
1795  * Make something like a letter B:
1796  *
1797  * 4------------3
1798  * | )
1799  * | 12--11 )
1800  * | | ) a3 ) a1
1801  * | 9---10 )
1802  * | )
1803  * | 2
1804  * | )
1805  * | 8----7 )
1806  * | | ) a2 ) a0
1807  * | 5----6 )
1808  * | )
1809  * 0------------1
1810  *
1811  * Where the numbers are the first 13 vertices, and the rest of
1812  * the vertices are in arcs a0, a1, a2, a3, each of which have
1813  * arc_points_num per arc in them.
1814  */
1815 
1816  const char *b_before_arcs = R"(13 0 3
1817  0.0 0.0
1818  1.0 0.0
1819  1.0 1.5
1820  1.0 3.0
1821  0.0 3.0
1822  0.2 0.2
1823  0.6 0.2
1824  0.6 1.4
1825  0.2 1.4
1826  0.2 1.6
1827  0.6 1.6
1828  0.6 2.8
1829  0.2 2.8
1830  3 4 0 1 2
1831  6 5 8 7
1832  10 9 12 11
1833  )";
1834 
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(); /* We'll add center point back between arcs for outer face. */
1845  for (int arc = 0; arc < narcs; ++arc) {
1846  int arc_origin_vert;
1847  int arc_terminal_vert;
1848  bool ccw;
1849  switch (arc) {
1850  case 0:
1851  arc_origin_vert = 1;
1852  arc_terminal_vert = 2;
1853  ccw = true;
1854  break;
1855  case 1:
1856  arc_origin_vert = 2;
1857  arc_terminal_vert = 3;
1858  ccw = true;
1859  break;
1860  case 2:
1861  arc_origin_vert = 7;
1862  arc_terminal_vert = 6;
1863  ccw = false;
1864  break;
1865  case 3:
1866  arc_origin_vert = 11;
1867  arc_terminal_vert = 10;
1868  ccw = false;
1869  break;
1870  default:
1871  BLI_assert(false);
1872  }
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);
1876  BLI_assert(start_co[0] == end_co[0]);
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) {
1882  vec2<T> delta;
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);
1888  }
1889  if (arc == 0) {
1890  face.append(arc_terminal_vert);
1891  }
1892  }
1893  }
1894 
1895  CDT_input<T> in;
1896  int tot_instances = lets_per_line_num * lines_num;
1897  if (tot_instances == 1) {
1898  in.vert = b_vert;
1899  in.face = b_face;
1900  }
1901  else {
1902  in.vert = Array<vec2<T>>(tot_instances * b_vert.size());
1903  in.face = Array<Vector<int>>(tot_instances * b_face.size());
1904  T cur_x = T(0);
1905  T cur_y = T(0);
1906  T delta_x = T(2);
1907  T delta_y = T(3.25);
1908  int instance = 0;
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);
1912  int in_v_offset = instance * b_vert.size();
1913  for (int v = 0; v < b_vert.size(); ++v) {
1914  in.vert[in_v_offset + v] = b_vert[v] + co_offset;
1915  }
1916  int in_f_offset = instance * b_face.size();
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);
1920  }
1921  }
1922  cur_x += delta_x;
1923  ++instance;
1924  }
1925  cur_y += delta_y;
1926  cur_x = T(0);
1927  }
1928  }
1929  in.epsilon = b_before_arcs_in.epsilon;
1930  in.need_ids = need_ids;
1931  double tstart = PIL_check_seconds_timer();
1932  CDT_result<T> out = delaunay_2d_calc(in, otype);
1933  double tend = PIL_check_seconds_timer();
1934  if (print_timing) {
1935  std::cout << "time = " << tend - tstart << "\n";
1936  }
1937  if (!need_ids) {
1938  EXPECT_EQ(out.vert_orig.size(), 0);
1939  EXPECT_EQ(out.edge_orig.size(), 0);
1940  EXPECT_EQ(out.face_orig.size(), 0);
1941  }
1942  if (DO_DRAW) {
1943  std::string label = "Text arcpts=" + std::to_string(arc_points_num);
1944  if (lets_per_line_num > 1) {
1945  label += " linelen=" + std::to_string(lets_per_line_num);
1946  }
1947  if (lines_num > 1) {
1948  label += " lines=" + std::to_string(lines_num);
1949  }
1950  if (!need_ids) {
1951  label += " no_ids";
1952  }
1953  if (otype != CDT_INSIDE_WITH_HOLES) {
1954  label += " otype=" + std::to_string(otype);
1955  }
1956  graph_draw<T>(label, out.vert, out.edge, out.face);
1957  }
1958 }
1959 
1960 TEST(delaunay_d, TextB10)
1961 {
1962  text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, true);
1963 }
1964 
1965 TEST(delaunay_d, TextB10_noids)
1966 {
1967  text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, false);
1968 }
1969 
1970 TEST(delaunay_d, TextB10_inside)
1971 {
1972  text_test<double>(10, 1, 1, CDT_INSIDE, true);
1973 }
1974 
1975 TEST(delaunay_d, TextB10_inside_noids)
1976 {
1977  text_test<double>(10, 1, 1, CDT_INSIDE, false);
1978 }
1979 
1980 TEST(delaunay_d, TextB10_constraints)
1981 {
1982  text_test<double>(10, 1, 1, CDT_CONSTRAINTS, true);
1983 }
1984 
1985 TEST(delaunay_d, TextB10_constraints_noids)
1986 {
1987  text_test<double>(10, 1, 1, CDT_CONSTRAINTS, false);
1988 }
1989 
1990 TEST(delaunay_d, TextB10_constraints_valid_bmesh)
1991 {
1992  text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, true);
1993 }
1994 
1995 TEST(delaunay_d, TextB10_constraints_valid_bmesh_noids)
1996 {
1997  text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, false);
1998 }
1999 
2000 TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes)
2001 {
2002  text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, true);
2003 }
2004 
2005 TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes_noids)
2006 {
2007  text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, false);
2008 }
2009 
2010 TEST(delaunay_d, TextB200)
2011 {
2012  text_test<double>(200, 1, 1, CDT_INSIDE_WITH_HOLES, true);
2013 }
2014 
2015 TEST(delaunay_d, TextB10_10_10)
2016 {
2017  text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES, true);
2018 }
2019 
2020 TEST(delaunay_d, TextB10_10_10_noids)
2021 {
2022  text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES, false);
2023 }
2024 
2025 # ifdef WITH_GMP
2026 TEST(delaunay_m, TextB10)
2027 {
2028  text_test<mpq_class>(10, 1, 1, CDT_INSIDE_WITH_HOLES, true);
2029 }
2030 
2031 TEST(delaunay_m, TextB200)
2032 {
2033  text_test<mpq_class>(200, 1, 1, CDT_INSIDE_WITH_HOLES, true);
2034 }
2035 
2036 TEST(delaunay_m, TextB10_10_10)
2037 {
2038  text_test<mpq_class>(10, 10, 10, CDT_INSIDE_WITH_HOLES, true);
2039 }
2040 
2041 TEST(delaunay_m, TextB10_10_10_noids)
2042 {
2043  text_test<mpq_class>(10, 10, 10, CDT_INSIDE_WITH_HOLES, false);
2044 }
2045 # endif
2046 
2047 #endif
2048 
2049 #if DO_RANDOM_TESTS
2050 
2051 enum {
2052  RANDOM_PTS,
2053  RANDOM_SEGS,
2054  RANDOM_POLY,
2055  RANDOM_TILTED_GRID,
2056  RANDOM_CIRCLE,
2057  RANDOM_TRI_BETWEEN_CIRCLES,
2058 };
2059 
2060 template<typename T>
2061 void rand_delaunay_test(int test_kind,
2062  int start_lg_size,
2063  int max_lg_size,
2064  int reps_per_size,
2065  double param,
2066  CDT_output_type otype)
2067 {
2068  constexpr bool print_timing = true;
2069  RNG *rng = BLI_rng_new(0);
2070  Array<double> times(max_lg_size + 1);
2071 
2072  /* For powers of 2 sizes up to max_lg_size power of 2. */
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) {
2077  continue;
2078  }
2079  /* Do 'rep' repetitions. */
2080  for (int rep = 0; rep < reps_per_size; ++rep) {
2081  /* First use test type and size to set npts, nedges, and nfaces. */
2082  int npts = 0;
2083  int nedges = 0;
2084  int nfaces = 0;
2085  std::string test_label;
2086  switch (test_kind) {
2087  case RANDOM_PTS: {
2088  npts = size;
2089  test_label = std::to_string(npts) + "Random points";
2090  } break;
2091  case RANDOM_SEGS: {
2092  npts = size;
2093  nedges = npts - 1;
2094  test_label = std::to_string(nedges) + "Random edges";
2095  } break;
2096  case RANDOM_POLY: {
2097  npts = size;
2098  nedges = npts;
2099  test_label = "Random poly with " + std::to_string(nedges) + " edges";
2100  } break;
2101  case RANDOM_TILTED_GRID: {
2102  /* A 'size' x 'size' grid of points, tilted by angle 'param'.
2103  * Edges will go from left ends to right ends and tops to bottoms,
2104  * so 2 x size of them.
2105  * Depending on epsilon, the vertical-ish edges may or may not go
2106  * through the intermediate vertices, but the horizontal ones always should.
2107  * 'param' is slope of tilt of vertical lines.
2108  */
2109  npts = size * size;
2110  nedges = 2 * size;
2111  test_label = "Tilted grid " + std::to_string(npts) + "x" + std::to_string(npts) +
2112  " (tilt=" + std::to_string(param) + ")";
2113  } break;
2114  case RANDOM_CIRCLE: {
2115  /* A circle with 'size' points, a random start angle,
2116  * and equal spacing thereafter. Will be input as one face.
2117  */
2118  npts = size;
2119  nfaces = 1;
2120  test_label = "Circle with " + std::to_string(npts) + " points";
2121  } break;
2122  case RANDOM_TRI_BETWEEN_CIRCLES: {
2123  /* A set of 'size' triangles, each has two random points on the unit circle,
2124  * and the third point is a random point on the circle with radius 'param'.
2125  * Each triangle will be input as a face.
2126  */
2127  npts = 3 * size;
2128  nfaces = size;
2129  test_label = "Random " + std::to_string(nfaces) +
2130  " triangles between circles (inner radius=" + std::to_string(param) + ")";
2131  } break;
2132  default:
2133  std::cout << "unknown delaunay test type\n";
2134  return;
2135  }
2136  if (otype != CDT_FULL) {
2137  if (otype == CDT_INSIDE) {
2138  test_label += " (inside)";
2139  }
2140  else if (otype == CDT_CONSTRAINTS) {
2141  test_label += " (constraints)";
2142  }
2143  else if (otype == CDT_CONSTRAINTS_VALID_BMESH) {
2144  test_label += " (valid bmesh)";
2145  }
2146  }
2147 
2148  CDT_input<T> in;
2149  in.vert = Array<vec2<T>>(npts);
2150  if (nedges > 0) {
2151  in.edge = Array<std::pair<int, int>>(nedges);
2152  }
2153  if (nfaces > 0) {
2154  in.face = Array<Vector<int>>(nfaces);
2155  }
2156 
2157  /* Make vertices and edges or faces. */
2158  switch (test_kind) {
2159  case RANDOM_PTS:
2160  case RANDOM_SEGS:
2161  case RANDOM_POLY: {
2162  for (int i = 0; i < size; i++) {
2163  in.vert[i][0] = T(BLI_rng_get_double(rng)); /* will be in range in [0,1) */
2164  in.vert[i][1] = T(BLI_rng_get_double(rng));
2165  if (test_kind != RANDOM_PTS) {
2166  if (i > 0) {
2167  in.edge[i - 1].first = i - 1;
2168  in.edge[i - 1].second = i;
2169  }
2170  }
2171  }
2172  if (test_kind == RANDOM_POLY) {
2173  in.edge[size - 1].first = size - 1;
2174  in.edge[size - 1].second = 0;
2175  }
2176  } break;
2177 
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);
2183  }
2184  }
2185  for (int i = 0; i < size; ++i) {
2186  /* Horizontal edges: connect `p(i,0)` to `p(i,size-1)`. */
2187  in.edge[i].first = i * size;
2188  in.edge[i].second = i * size + size - 1;
2189  /* Vertical edges: connect `p(0,i)` to `p(size-1,i)`. */
2190  in.edge[size + i].first = i;
2191  in.edge[size + i].second = (size - 1) * size + i;
2192  }
2193  } break;
2194 
2195  case RANDOM_CIRCLE: {
2196  double start_angle = BLI_rng_get_double(rng) * 2.0 * M_PI;
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);
2202  }
2203  } break;
2204 
2205  case RANDOM_TRI_BETWEEN_CIRCLES: {
2206  for (int i = 0; i < size; i++) {
2207  /* Get three random angles in [0, 2pi). */
2208  double angle1 = BLI_rng_get_double(rng) * 2.0 * M_PI;
2209  double angle2 = BLI_rng_get_double(rng) * 2.0 * M_PI;
2210  double angle3 = BLI_rng_get_double(rng) * 2.0 * M_PI;
2211  int ia = 3 * i;
2212  int ib = 3 * i + 1;
2213  int ic = 3 * i + 2;
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)));
2220  /* Put the coordinates in CCW order. */
2221  in.face[i].append(ia);
2222  int orient = orient2d(in.vert[ia], in.vert[ib], in.vert[ic]);
2223  if (orient >= 0) {
2224  in.face[i].append(ib);
2225  in.face[i].append(ic);
2226  }
2227  else {
2228  in.face[i].append(ic);
2229  in.face[i].append(ib);
2230  }
2231  }
2232  } break;
2233  }
2234 
2235  /* Run the test. */
2236  double tstart = PIL_check_seconds_timer();
2237  CDT_result<T> out = delaunay_2d_calc(in, otype);
2238  EXPECT_NE(out.vert.size(), 0);
2239  times[lg_size] += PIL_check_seconds_timer() - tstart;
2240  if (DO_DRAW) {
2241  graph_draw<T>(test_label, out.vert, out.edge, out.face);
2242  }
2243  }
2244  }
2245  if (print_timing) {
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";
2250  }
2251  }
2252  BLI_rng_free(rng);
2253 }
2254 
2255 TEST(delaunay_d, RandomPts)
2256 {
2257  rand_delaunay_test<double>(RANDOM_PTS, 0, 7, 1, 0.0, CDT_FULL);
2258 }
2259 
2260 TEST(delaunay_d, RandomSegs)
2261 {
2262  rand_delaunay_test<double>(RANDOM_SEGS, 1, 7, 1, 0.0, CDT_FULL);
2263 }
2264 
2265 TEST(delaunay_d, RandomPoly)
2266 {
2267  rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_FULL);
2268 }
2269 
2270 TEST(delaunay_d, RandomPolyConstraints)
2271 {
2272  rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS);
2273 }
2274 
2275 TEST(delaunay_d, RandomPolyValidBmesh)
2276 {
2277  rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS_VALID_BMESH);
2278 }
2279 
2280 TEST(delaunay_d, Grid)
2281 {
2282  rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0, CDT_FULL);
2283 }
2284 
2285 TEST(delaunay_d, TiltedGridA)
2286 {
2287  rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0, CDT_FULL);
2288 }
2289 
2290 TEST(delaunay_d, TiltedGridB)
2291 {
2292  rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01, CDT_FULL);
2293 }
2294 
2295 TEST(delaunay_d, RandomCircle)
2296 {
2297  rand_delaunay_test<double>(RANDOM_CIRCLE, 1, 7, 1, 0.0, CDT_FULL);
2298 }
2299 
2300 TEST(delaunay_d, RandomTrisCircle)
2301 {
2302  rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25, CDT_FULL);
2303 }
2304 
2305 TEST(delaunay_d, RandomTrisCircleB)
2306 {
2307  rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1e-4, CDT_FULL);
2308 }
2309 
2310 # ifdef WITH_GMP
2311 TEST(delaunay_m, RandomPts)
2312 {
2313  rand_delaunay_test<mpq_class>(RANDOM_PTS, 0, 7, 1, 0.0, CDT_FULL);
2314 }
2315 
2316 TEST(delaunay_m, RandomSegs)
2317 {
2318  rand_delaunay_test<mpq_class>(RANDOM_SEGS, 1, 7, 1, 0.0, CDT_FULL);
2319 }
2320 
2321 TEST(delaunay_m, RandomPoly)
2322 {
2323  rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_FULL);
2324 }
2325 
2326 TEST(delaunay_d, RandomPolyInside)
2327 {
2328  rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_INSIDE);
2329 }
2330 
2331 TEST(delaunay_m, RandomPolyInside)
2332 {
2333  rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_INSIDE);
2334 }
2335 
2336 TEST(delaunay_m, RandomPolyConstraints)
2337 {
2338  rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS);
2339 }
2340 
2341 TEST(delaunay_m, RandomPolyValidBmesh)
2342 {
2343  rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS_VALID_BMESH);
2344 }
2345 
2346 TEST(delaunay_m, Grid)
2347 {
2348  rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0, CDT_FULL);
2349 }
2350 
2351 TEST(delaunay_m, TiltedGridA)
2352 {
2353  rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0, CDT_FULL);
2354 }
2355 
2356 TEST(delaunay_m, TiltedGridB)
2357 {
2358  rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01, CDT_FULL);
2359 }
2360 
2361 TEST(delaunay_m, RandomCircle)
2362 {
2363  rand_delaunay_test<mpq_class>(RANDOM_CIRCLE, 1, 7, 1, 0.0, CDT_FULL);
2364 }
2365 
2366 TEST(delaunay_m, RandomTrisCircle)
2367 {
2368  rand_delaunay_test<mpq_class>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25, CDT_FULL);
2369 }
2370 
2371 TEST(delaunay_m, RandomTrisCircleB)
2372 {
2373  rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1e-4, CDT_FULL);
2374 }
2375 # endif
2376 
2377 #endif
2378 
2379 } // namespace blender::meshintersect
#define BLI_assert(a)
Definition: BLI_assert.h:46
CDT_result * BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_type output_type)
CDT_output_type
@ CDT_CONSTRAINTS_VALID_BMESH
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES
@ CDT_CONSTRAINTS
@ CDT_INSIDE
@ CDT_FULL
@ CDT_INSIDE_WITH_HOLES
void BLI_delaunay_2d_cdt_free(CDT_result *result)
#define SY(y)
#define SX(x)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
#define M_PI_2
Definition: BLI_math_base.h:23
#define M_PI
Definition: BLI_math_base.h:20
Math vector functions needed specifically for mesh intersect and boolean.
Random number functions.
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition: rand.cc:58
struct RNG * BLI_rng_new(unsigned int seed)
Definition: rand.cc:39
double BLI_rng_get_double(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: rand.cc:88
#define UNUSED(x)
#define ELEM(...)
@ TEST
_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)
Definition: btDbvt.cpp:52
const char * label
blender::meshintersect::CDT_result< double > delaunay_2d_calc(const CDT_input< double > &input, CDT_output_type output_type)
static float verts[][3]
ccl_global KernelShaderEvalInput ccl_global float * output
ccl_global KernelShaderEvalInput * input
ccl_device_inline float2 fabs(const float2 &a)
Definition: math_float2.h:222
#define T
static char faces[256]
INLINE Rall1d< T, V, S > cos(const Rall1d< T, V, S > &arg)
Definition: rall1d.h:319
INLINE Rall1d< T, V, S > sin(const Rall1d< T, V, S > &arg)
Definition: rall1d.h:311
T abs(const T &a)
double math_to_double< double >(const double v)
Definition: delaunay_2d.cc:61
double math_to_double(const T UNUSED(v))
Definition: delaunay_2d.cc:48
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
Definition: delaunay_2d.cc:177
T math_abs(const T v)
Definition: delaunay_2d.cc:31
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)
float size
Definition: particles.h:27
Definition: rand.cc:33
double PIL_check_seconds_timer(void)
Definition: time.c:64