Blender  V3.3
BLI_mesh_intersect_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 <algorithm>
6 #include <fstream>
7 #include <iostream>
8 
9 #include "PIL_time.h"
10 
11 #include "BLI_array.hh"
12 #include "BLI_math_mpq.hh"
14 #include "BLI_mesh_intersect.hh"
15 #include "BLI_task.h"
16 #include "BLI_vector.hh"
17 
18 #define DO_REGULAR_TESTS 1
19 #define DO_PERF_TESTS 0
20 
21 #ifdef WITH_GMP
22 namespace blender::meshintersect::tests {
23 
24 constexpr bool DO_OBJ = false;
25 
26 /* Build and hold an IMesh from a string spec. Also hold and own resources used by IMesh. */
27 class IMeshBuilder {
28  public:
29  IMesh imesh;
30  IMeshArena arena;
31 
32  /* "Edge orig" indices are an encoding of <input face#, position in face of start of edge>. */
33  static constexpr int MAX_FACE_LEN = 1000; /* Used for forming "orig edge" indices only. */
34 
35  static int edge_index(int face_index, int facepos)
36  {
37  return face_index * MAX_FACE_LEN + facepos;
38  }
39 
40  static std::pair<int, int> face_and_pos_for_edge_index(int e_index)
41  {
42  return std::pair<int, int>(e_index / MAX_FACE_LEN, e_index % MAX_FACE_LEN);
43  }
44 
53  IMeshBuilder(const char *spec)
54  {
55  std::istringstream ss(spec);
56  std::string line;
57  getline(ss, line);
58  std::istringstream hdrss(line);
59  int nv, nf;
60  hdrss >> nv >> nf;
61  if (nv == 0 || nf == 0) {
62  return;
63  }
64  arena.reserve(nv, nf);
65  Vector<const Vert *> verts;
66  Vector<Face *> faces;
67  bool spec_ok = true;
68  int v_index = 0;
69  while (v_index < nv && spec_ok && getline(ss, line)) {
70  std::istringstream iss(line);
71  mpq_class p0;
72  mpq_class p1;
73  mpq_class p2;
74  iss >> p0 >> p1 >> p2;
75  spec_ok = !iss.fail();
76  if (spec_ok) {
77  verts.append(arena.add_or_find_vert(mpq3(p0, p1, p2), v_index));
78  }
79  ++v_index;
80  }
81  if (v_index != nv) {
82  spec_ok = false;
83  }
84  int f_index = 0;
85  while (f_index < nf && spec_ok && getline(ss, line)) {
86  std::istringstream fss(line);
87  Vector<const Vert *> face_verts;
88  Vector<int> edge_orig;
89  int fpos = 0;
90  while (spec_ok && fss >> v_index) {
91  if (v_index < 0 || v_index >= nv) {
92  spec_ok = false;
93  continue;
94  }
95  face_verts.append(verts[v_index]);
96  edge_orig.append(edge_index(f_index, fpos));
97  ++fpos;
98  }
99  if (fpos < 3) {
100  spec_ok = false;
101  }
102  if (spec_ok) {
103  Face *facep = arena.add_face(face_verts, f_index, edge_orig);
104  faces.append(facep);
105  }
106  ++f_index;
107  }
108  if (f_index != nf) {
109  spec_ok = false;
110  }
111  if (!spec_ok) {
112  std::cout << "Bad spec: " << spec;
113  return;
114  }
115  imesh = IMesh(faces);
116  }
117 };
118 
119 /* Return a const Face * in mesh with verts equal to v0, v1, and v2, in
120  * some cyclic order; return nullptr if not found.
121  */
122 static const Face *find_tri_with_verts(const IMesh &mesh,
123  const Vert *v0,
124  const Vert *v1,
125  const Vert *v2)
126 {
127  Face f_arg({v0, v1, v2}, 0, NO_INDEX);
128  for (const Face *f : mesh.faces()) {
129  if (f->cyclic_equal(f_arg)) {
130  return f;
131  }
132  }
133  return nullptr;
134 }
135 
136 /* How many instances of a triangle with v0, v1, v2 are in the mesh? */
137 static int count_tris_with_verts(const IMesh &mesh, const Vert *v0, const Vert *v1, const Vert *v2)
138 {
139  Face f_arg({v0, v1, v2}, 0, NO_INDEX);
140  int ans = 0;
141  for (const Face *f : mesh.faces()) {
142  if (f->cyclic_equal(f_arg)) {
143  ++ans;
144  }
145  }
146  return ans;
147 }
148 
149 /* What is the starting position, if any, of the edge (v0, v1), in either order, in f? -1 if none.
150  */
151 static int find_edge_pos_in_tri(const Vert *v0, const Vert *v1, const Face *f)
152 {
153  for (int pos : f->index_range()) {
154  int nextpos = f->next_pos(pos);
155  if (((*f)[pos] == v0 && (*f)[nextpos] == v1) || ((*f)[pos] == v1 && (*f)[nextpos] == v0)) {
156  return static_cast<int>(pos);
157  }
158  }
159  return -1;
160 }
161 
162 # if DO_REGULAR_TESTS
163 TEST(mesh_intersect, Mesh)
164 {
165  Vector<const Vert *> verts;
166  Vector<Face *> faces;
167  IMeshArena arena;
168 
169  verts.append(arena.add_or_find_vert(mpq3(0, 0, 1), 0));
170  verts.append(arena.add_or_find_vert(mpq3(1, 0, 1), 1));
171  verts.append(arena.add_or_find_vert(mpq3(0.5, 1, 1), 2));
172  faces.append(arena.add_face(verts, 0, {10, 11, 12}));
173 
174  IMesh mesh(faces);
175  const Face *f = mesh.face(0);
176  EXPECT_TRUE(f->is_tri());
177 }
178 
179 TEST(mesh_intersect, TriangulateTri)
180 {
181  const char *spec = R"(3 1
182  0 0 0
183  1 0 0
184  1/2 1 0
185  0 1 2
186  )";
187 
188  IMeshBuilder mb(spec);
189  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
190  EXPECT_EQ(im_tri.faces().size(), 1);
191 }
192 
193 TEST(mesh_intersect, TriangulateQuad)
194 {
195  const char *spec = R"(4 1
196  0 0 0
197  1 0 0
198  1 1 0
199  0 1 0
200  0 1 2 3
201  )";
202 
203  IMeshBuilder mb(spec);
204  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
205  EXPECT_EQ(im_tri.faces().size(), 2);
206 }
207 
208 TEST(mesh_intersect, TriangulatePentagon)
209 {
210  const char *spec = R"(5 1
211  0 0 0
212  1 0 0
213  1 1 0
214  1/2 2 0
215  0 1 0
216  0 1 2 3 4
217  )";
218 
219  IMeshBuilder mb(spec);
220  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
221  EXPECT_EQ(im_tri.faces().size(), 3);
222  if (DO_OBJ) {
223  write_obj_mesh(im_tri, "pentagon");
224  }
225 }
226 
227 TEST(mesh_intersect, TriangulateTwoFaces)
228 {
229  const char *spec = R"(7 2
230  461/250 -343/125 103/1000
231  -3/40 -453/200 -97/500
232  237/100 -321/200 -727/500
233  451/1000 -563/500 -1751/1000
234  12/125 -2297/1000 -181/1000
235  12/125 -411/200 -493/1000
236  1959/1000 -2297/1000 -493/1000
237  1 3 2 0 6 5 4
238  6 0 1 4
239  )";
240 
241  IMeshBuilder mb(spec);
242  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
243  EXPECT_EQ(im_tri.faces().size(), 7);
244  if (DO_OBJ) {
245  write_obj_mesh(im_tri, "twofaces");
246  }
247 }
248 
249 TEST(mesh_intersect, OneTri)
250 {
251  const char *spec = R"(3 1
252  0 0 0
253  1 0 0
254  1/2 1 0
255  0 1 2
256  )";
257 
258  IMeshBuilder mb(spec);
259  IMesh imesh = trimesh_self_intersect(mb.imesh, &mb.arena);
260  imesh.populate_vert();
261  EXPECT_EQ(imesh.vert_size(), 3);
262  EXPECT_EQ(imesh.face_size(), 1);
263  const Face &f_in = *mb.imesh.face(0);
264  const Face &f_out = *imesh.face(0);
265  EXPECT_EQ(f_in.orig, f_out.orig);
266  for (int i = 0; i < 3; ++i) {
267  EXPECT_EQ(f_in[i], f_out[i]);
268  EXPECT_EQ(f_in.edge_orig[i], f_out.edge_orig[i]);
269  }
270 }
271 
272 TEST(mesh_intersect, TriTri)
273 {
274  const char *spec = R"(6 2
275  0 0 0
276  4 0 0
277  0 4 0
278  1 0 0
279  2 0 0
280  1 1 0
281  0 1 2
282  3 4 5
283  )";
284 
285  /* Second triangle is smaller and congruent to first, resting on same base, partway along. */
286  IMeshBuilder mb(spec);
287  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
288  out.populate_vert();
289  EXPECT_EQ(out.vert_size(), 6);
290  EXPECT_EQ(out.face_size(), 6);
291  if (out.vert_size() == 6 && out.face_size() == 6) {
292  const Vert *v0 = mb.arena.find_vert(mpq3(0, 0, 0));
293  const Vert *v1 = mb.arena.find_vert(mpq3(4, 0, 0));
294  const Vert *v2 = mb.arena.find_vert(mpq3(0, 4, 0));
295  const Vert *v3 = mb.arena.find_vert(mpq3(1, 0, 0));
296  const Vert *v4 = mb.arena.find_vert(mpq3(2, 0, 0));
297  const Vert *v5 = mb.arena.find_vert(mpq3(1, 1, 0));
298  EXPECT_TRUE(v0 != nullptr && v1 != nullptr && v2 != nullptr);
299  EXPECT_TRUE(v3 != nullptr && v4 != nullptr && v5 != nullptr);
300  if (v0 != nullptr && v1 != nullptr && v2 != nullptr && v3 != nullptr && v4 != nullptr &&
301  v5 != nullptr) {
302  EXPECT_EQ(v0->orig, 0);
303  EXPECT_EQ(v1->orig, 1);
304  const Face *f0 = find_tri_with_verts(out, v4, v1, v5);
305  const Face *f1 = find_tri_with_verts(out, v3, v4, v5);
306  const Face *f2 = find_tri_with_verts(out, v0, v3, v5);
307  const Face *f3 = find_tri_with_verts(out, v0, v5, v2);
308  const Face *f4 = find_tri_with_verts(out, v5, v1, v2);
309  EXPECT_TRUE(f0 != nullptr && f1 != nullptr && f2 != nullptr && f3 != nullptr &&
310  f4 != nullptr);
311  /* For boolean to work right, there need to be two copies of the smaller triangle in the
312  * output. */
313  EXPECT_EQ(count_tris_with_verts(out, v3, v4, v5), 2);
314  if (f0 != nullptr && f1 != nullptr && f2 != nullptr && f3 != nullptr && f4 != nullptr) {
315  EXPECT_EQ(f0->orig, 0);
316  EXPECT_TRUE(f1->orig == 0 || f1->orig == 1);
317  EXPECT_EQ(f2->orig, 0);
318  EXPECT_EQ(f3->orig, 0);
319  EXPECT_EQ(f4->orig, 0);
320  }
321  int e03 = find_edge_pos_in_tri(v0, v3, f2);
322  int e34 = find_edge_pos_in_tri(v3, v4, f1);
323  int e45 = find_edge_pos_in_tri(v4, v5, f1);
324  int e05 = find_edge_pos_in_tri(v0, v5, f3);
325  int e15 = find_edge_pos_in_tri(v1, v5, f0);
326  EXPECT_TRUE(e03 != -1 && e34 != -1 && e45 != -1 && e05 != -1 && e15 != -1);
327  if (e03 != -1 && e34 != -1 && e45 != -1 && e05 != -1 && e15 != -1) {
328  EXPECT_EQ(f2->edge_orig[e03], 0);
329  EXPECT_TRUE(f1->edge_orig[e34] == 0 ||
330  f1->edge_orig[e34] == 1 * IMeshBuilder::MAX_FACE_LEN);
331  EXPECT_EQ(f1->edge_orig[e45], 1 * IMeshBuilder::MAX_FACE_LEN + 1);
332  EXPECT_EQ(f3->edge_orig[e05], NO_INDEX);
333  EXPECT_EQ(f0->edge_orig[e15], NO_INDEX);
334  }
335  }
336  }
337  if (DO_OBJ) {
338  write_obj_mesh(out, "tritri");
339  }
340 }
341 
342 TEST(mesh_intersect, TriTriReversed)
343 {
344  /* Like TriTri but with triangles of opposite orientation.
345  * This matters because projection to 2D will now need reversed triangles. */
346  const char *spec = R"(6 2
347  0 0 0
348  4 0 0
349  0 4 0
350  1 0 0
351  2 0 0
352  1 1 0
353  0 2 1
354  3 5 4
355  )";
356 
357  IMeshBuilder mb(spec);
358  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
359  out.populate_vert();
360  EXPECT_EQ(out.vert_size(), 6);
361  EXPECT_EQ(out.face_size(), 6);
362  if (out.vert_size() == 6 && out.face_size() == 6) {
363  const Vert *v0 = mb.arena.find_vert(mpq3(0, 0, 0));
364  const Vert *v1 = mb.arena.find_vert(mpq3(4, 0, 0));
365  const Vert *v2 = mb.arena.find_vert(mpq3(0, 4, 0));
366  const Vert *v3 = mb.arena.find_vert(mpq3(1, 0, 0));
367  const Vert *v4 = mb.arena.find_vert(mpq3(2, 0, 0));
368  const Vert *v5 = mb.arena.find_vert(mpq3(1, 1, 0));
369  EXPECT_TRUE(v0 != nullptr && v1 != nullptr && v2 != nullptr);
370  EXPECT_TRUE(v3 != nullptr && v4 != nullptr && v5 != nullptr);
371  if (v0 != nullptr && v1 != nullptr && v2 != nullptr && v3 != nullptr && v4 != nullptr &&
372  v5 != nullptr) {
373  EXPECT_EQ(v0->orig, 0);
374  EXPECT_EQ(v1->orig, 1);
375  const Face *f0 = find_tri_with_verts(out, v4, v5, v1);
376  const Face *f1 = find_tri_with_verts(out, v3, v5, v4);
377  const Face *f2 = find_tri_with_verts(out, v0, v5, v3);
378  const Face *f3 = find_tri_with_verts(out, v0, v2, v5);
379  const Face *f4 = find_tri_with_verts(out, v5, v2, v1);
380  EXPECT_TRUE(f0 != nullptr && f1 != nullptr && f2 != nullptr && f3 != nullptr &&
381  f4 != nullptr);
382  /* For boolean to work right, there need to be two copies of the smaller triangle in the
383  * output. */
384  EXPECT_EQ(count_tris_with_verts(out, v3, v5, v4), 2);
385  if (f0 != nullptr && f1 != nullptr && f2 != nullptr && f3 != nullptr && f4 != nullptr) {
386  EXPECT_EQ(f0->orig, 0);
387  EXPECT_TRUE(f1->orig == 0 || f1->orig == 1);
388  EXPECT_EQ(f2->orig, 0);
389  EXPECT_EQ(f3->orig, 0);
390  EXPECT_EQ(f4->orig, 0);
391  }
392  int e03 = find_edge_pos_in_tri(v0, v3, f2);
393  int e34 = find_edge_pos_in_tri(v3, v4, f1);
394  int e45 = find_edge_pos_in_tri(v4, v5, f1);
395  int e05 = find_edge_pos_in_tri(v0, v5, f3);
396  int e15 = find_edge_pos_in_tri(v1, v5, f0);
397  EXPECT_TRUE(e03 != -1 && e34 != -1 && e45 != -1 && e05 != -1 && e15 != -1);
398  if (e03 != -1 && e34 != -1 && e45 != -1 && e05 != -1 && e15 != -1) {
399  EXPECT_EQ(f2->edge_orig[e03], 2);
400  EXPECT_TRUE(f1->edge_orig[e34] == 2 ||
401  f1->edge_orig[e34] == 1 * IMeshBuilder::MAX_FACE_LEN + 2);
402  EXPECT_EQ(f1->edge_orig[e45], 1 * IMeshBuilder::MAX_FACE_LEN + 1);
403  EXPECT_EQ(f3->edge_orig[e05], NO_INDEX);
404  EXPECT_EQ(f0->edge_orig[e15], NO_INDEX);
405  }
406  }
407  }
408  if (DO_OBJ) {
409  write_obj_mesh(out, "tritrirev");
410  }
411 }
412 
413 TEST(mesh_intersect, TwoTris)
414 {
415  Array<mpq3> verts = {
416  mpq3(1, 1, 1), mpq3(1, 4, 1), mpq3(1, 1, 4), /* T0 */
417  mpq3(2, 2, 2), mpq3(-3, 3, 2), mpq3(-4, 1, 3), /* T1 */
418  mpq3(2, 2, 2), mpq3(-3, 3, 2), mpq3(0, 3, 5), /* T2 */
419  mpq3(2, 2, 2), mpq3(-3, 3, 2), mpq3(0, 3, 3), /* T3 */
420  mpq3(1, 0, 0), mpq3(2, 4, 1), mpq3(-3, 2, 2), /* T4 */
421  mpq3(0, 2, 1), mpq3(-2, 3, 3), mpq3(0, 1, 3), /* T5 */
422  mpq3(1.5, 2, 0.5), mpq3(-2, 3, 3), mpq3(0, 1, 3), /* T6 */
423  mpq3(1, 0, 0), mpq3(-2, 3, 3), mpq3(0, 1, 3), /* T7 */
424  mpq3(1, 0, 0), mpq3(-3, 2, 2), mpq3(0, 1, 3), /* T8 */
425  mpq3(1, 0, 0), mpq3(-1, 1, 1), mpq3(0, 1, 3), /* T9 */
426  mpq3(3, -1, -1), mpq3(-1, 1, 1), mpq3(0, 1, 3), /* T10 */
427  mpq3(0, 0.5, 0.5), mpq3(-1, 1, 1), mpq3(0, 1, 3), /* T11 */
428  mpq3(2, 1, 1), mpq3(3, 5, 2), mpq3(-2, 3, 3), /* T12 */
429  mpq3(2, 1, 1), mpq3(3, 5, 2), mpq3(-2, 3, 4), /* T13 */
430  mpq3(2, 2, 5), mpq3(-3, 3, 5), mpq3(0, 3, 10), /* T14 */
431  mpq3(0, 0, 0), mpq3(4, 4, 0), mpq3(-4, 2, 4), /* T15 */
432  mpq3(0, 1.5, 1), mpq3(1, 2.5, 1), mpq3(-1, 2, 2), /* T16 */
433  mpq3(3, 0, -2), mpq3(7, 4, -2), mpq3(-1, 2, 2), /* T17 */
434  mpq3(3, 0, -2), mpq3(3, 6, 2), mpq3(-1, 2, 2), /* T18 */
435  mpq3(7, 4, -2), mpq3(3, 6, 2), mpq3(-1, 2, 2), /* T19 */
436  mpq3(5, 2, -2), mpq3(1, 4, 2), mpq3(-3, 0, 2), /* T20 */
437  mpq3(2, 2, 0), mpq3(1, 4, 2), mpq3(-3, 0, 2), /* T21 */
438  mpq3(0, 0, 0), mpq3(4, 4, 0), mpq3(-3, 0, 2), /* T22 */
439  mpq3(0, 0, 0), mpq3(4, 4, 0), mpq3(-1, 2, 2), /* T23 */
440  mpq3(2, 2, 0), mpq3(4, 4, 0), mpq3(0, 3, 2), /* T24 */
441  mpq3(0, 0, 0), mpq3(-4, 2, 4), mpq3(4, 4, 0), /* T25 */
442  };
443  struct two_tri_test_spec {
444  int t0;
445  int t1;
446  int nv_out;
447  int nf_out;
448  };
449  Array<two_tri_test_spec> test_tris = Span<two_tri_test_spec>{
450  {0, 1, 8, 8}, /* 0: T1 pierces T0 inside at (1,11/6,13/6) and (1,11/5,2). */
451  {0, 2, 8, 8}, /* 1: T2 intersects T0 inside (1,11/5,2) and edge (1,7/3,8/3). */
452  {0, 3, 8, 7}, /* 2: T3 intersects T0 (1,11/5,2) and edge-edge (1,5/2,5/2). */
453  {4, 5, 6, 4}, /* 3: T5 touches T4 inside (0,2,1). */
454  {4, 6, 6, 3}, /* 4: T6 touches T4 on edge (3/2,2/1/2). */
455  {4, 7, 5, 2}, /* 5: T7 touches T4 on vert (1,0,0). */
456  {4, 8, 4, 2}, /* 6: T8 shared edge with T4 (1,0,0)(-3,2,2). */
457  {4, 9, 5, 3}, /* 7: T9 edge (1,0,0)(-1,1,1) is subset of T4 edge. */
458  {4, 10, 6, 4}, /* 8: T10 edge overlaps T4 edge with seg (-1,1,0)(1,0,0). */
459  {4, 11, 6, 4}, /* 9: T11 edge (-1,1,1)(0,1/2,1/2) inside T4 edge. */
460  {4, 12, 6, 2}, /* 10: parallel planes, not intersecting. */
461  {4, 13, 6, 2}, /* 11: non-parallel planes, not intersecting, all one side. */
462  {0, 14, 6, 2}, /* 12: non-parallel planes, not intersecting, alternate sides. */
463  /* Following are all co-planar cases. */
464  {15, 16, 6, 8}, /* 13: T16 inside T15. NOTE: dup'd tri is expected. */
465  {15, 17, 8, 8}, /* 14: T17 intersects one edge of T15 at (1,1,0)(3,3,0). */
466  {15, 18, 10, 12}, /* 15: T18 intersects T15 at (1,1,0)(3,3,0)(3,15/4,1/2)(0,3,2). */
467  {15, 19, 8, 10}, /* 16: T19 intersects T15 at (3,3,0)(0,3,2). */
468  {15, 20, 12, 14}, /* 17: T20 intersects T15 on three edges, six intersects. */
469  {15, 21, 10, 11}, /* 18: T21 intersects T15 on three edges, touching one. */
470  {15, 22, 5, 4}, /* 19: T22 shares edge T15, one other outside. */
471  {15, 23, 4, 4}, /* 20: T23 shares edge T15, one other outside. */
472  {15, 24, 5, 4}, /* 21: T24 shares two edges with T15. */
473  {15, 25, 3, 2}, /* 22: T25 same T15, reverse orientation. */
474  };
475  static int perms[6][3] = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
476 
477  const int do_only_test = -1; /* Make this negative to do all tests. */
478  for (int test = 0; test < test_tris.size(); ++test) {
479  if (do_only_test >= 0 && test != do_only_test) {
480  continue;
481  }
482  int tri1_index = test_tris[test].t0;
483  int tri2_index = test_tris[test].t1;
484  int co1_i = 3 * tri1_index;
485  int co2_i = 3 * tri2_index;
486 
487  const bool verbose = false;
488 
489  if (verbose) {
490  std::cout << "\nTest " << test << ": T" << tri1_index << " intersect T" << tri2_index
491  << "\n";
492  }
493 
494  const bool do_all_perms = true;
495  const int perm_limit = do_all_perms ? 3 : 1;
496 
497  for (int i = 0; i < perm_limit; ++i) {
498  for (int j = 0; j < perm_limit; ++j) {
499  if (do_all_perms && verbose) {
500  std::cout << "\nperms " << i << " " << j << "\n";
501  }
502  IMeshArena arena;
503  arena.reserve(2 * 3, 2);
504  Array<const Vert *> f0_verts(3);
505  Array<const Vert *> f1_verts(3);
506  for (int k = 0; k < 3; ++k) {
507  f0_verts[k] = arena.add_or_find_vert(verts[co1_i + perms[i][k]], k);
508  }
509  for (int k = 0; k < 3; ++k) {
510  f1_verts[k] = arena.add_or_find_vert(verts[co2_i + perms[i][k]], k + 3);
511  }
512  Face *f0 = arena.add_face(f0_verts, 0, {0, 1, 2});
513  Face *f1 = arena.add_face(f1_verts, 1, {3, 4, 5});
514  IMesh in_mesh({f0, f1});
515  IMesh out_mesh = trimesh_self_intersect(in_mesh, &arena);
516  out_mesh.populate_vert();
517  EXPECT_EQ(out_mesh.vert_size(), test_tris[test].nv_out);
518  EXPECT_EQ(out_mesh.face_size(), test_tris[test].nf_out);
519  bool constexpr dump_input = true;
520  if (DO_OBJ && i == 0 && j == 0) {
521  if (dump_input) {
522  std::string name = "test_tt_in" + std::to_string(test);
523  write_obj_mesh(in_mesh, name);
524  }
525  std::string name = "test_tt" + std::to_string(test);
526  write_obj_mesh(out_mesh, name);
527  }
528  }
529  }
530  }
531 }
532 
533 TEST(mesh_intersect, OverlapCluster)
534 {
535  /* Chain of 5 overlapping coplanar tris.
536  * Ordered so that clustering will make two separate clusters
537  * that it will have to merge into one cluster with everything. */
538  const char *spec = R"(15 5
539  0 0 0
540  1 0 0
541  1/2 1 0
542  1/2 0 0
543  3/2 0 0
544  1 1 0
545  1 0 0
546  2 0 0
547  3/2 1 0
548  3/2 0 0
549  5/2 0 0
550  2 1 0
551  2 0 0
552  3 0 0
553  5/2 1 0
554  0 1 2
555  3 4 5
556  9 10 11
557  12 13 14
558  6 7 8
559  )";
560 
561  IMeshBuilder mb(spec);
562  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
563  out.populate_vert();
564  EXPECT_EQ(out.vert_size(), 16);
565  EXPECT_EQ(out.face_size(), 18);
566  if (DO_OBJ) {
567  write_obj_mesh(out, "overlapcluster");
568  }
569 }
570 
571 TEST(mesh_intersect, TriCornerCross1)
572 {
573  /* A corner formed by 3 tris, and a 4th crossing two of them. */
574  const char *spec = R"(12 4
575  0 0 0
576  1 0 0
577  0 0 1
578  0 0 0
579  0 1 0
580  0 0 1
581  0 0 0
582  1 0 0
583  0 1 0
584  1 1 1/2
585  1 -2 1/2
586  -2 1 1/2
587  0 1 2
588  3 4 5
589  6 7 8
590  9 10 11
591  )";
592 
593  IMeshBuilder mb(spec);
594  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
595  out.populate_vert();
596  EXPECT_EQ(out.vert_size(), 10);
597  EXPECT_EQ(out.face_size(), 14);
598  if (DO_OBJ) {
599  write_obj_mesh(out, "test_tc_1");
600  }
601 }
602 
603 TEST(mesh_intersect, TriCornerCross2)
604 {
605  /* A corner formed by 3 tris, and a 4th coplanar with base. */
606  const char *spec = R"(12 4
607  0 0 0
608  1 0 0
609  0 0 1
610  0 0 0
611  0 1 0
612  0 0 1
613  0 0 0
614  1 0 0
615  0 1 0
616  1 1 0
617  1 -2 0
618  -2 1 0
619  0 1 2
620  3 4 5
621  6 7 8
622  9 10 11
623  )";
624 
625  IMeshBuilder mb(spec);
626  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
627  out.populate_vert();
628  EXPECT_EQ(out.vert_size(), 7);
629  EXPECT_EQ(out.face_size(), 8);
630  if (DO_OBJ) {
631  write_obj_mesh(out, "test_tc_2");
632  }
633 }
634 
635 TEST(mesh_intersect, TriCornerCross3)
636 {
637  /* A corner formed by 3 tris, and a 4th crossing all 3. */
638  const char *spec = R"(12 4
639  0 0 0
640  1 0 0
641  0 0 1
642  0 0 0
643  0 1 0
644  0 0 1
645  0 0 0
646  1 0 0
647  0 1 0
648  3/2 -1/2 -1/4
649  -1/2 3/2 -1/4
650  -1/2 -1/2 3/4
651  0 1 2
652  3 4 5
653  6 7 8
654  9 10 11
655  )";
656 
657  IMeshBuilder mb(spec);
658  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
659  out.populate_vert();
660  EXPECT_EQ(out.vert_size(), 10);
661  EXPECT_EQ(out.face_size(), 16);
662  if (DO_OBJ) {
663  write_obj_mesh(out, "test_tc_3");
664  }
665 }
666 
667 TEST(mesh_intersect, TetTet)
668 {
669  const char *spec = R"(8 8
670  0 0 0
671  2 0 0
672  1 2 0
673  1 1 2
674  0 0 1
675  2 0 1
676  1 2 1
677  1 1 3
678  0 1 2
679  0 3 1
680  1 3 2
681  2 3 0
682  4 5 6
683  4 7 5
684  5 7 6
685  6 7 4
686  )";
687 
688  IMeshBuilder mb(spec);
689  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
690  out.populate_vert();
691  EXPECT_EQ(out.vert_size(), 11);
692  EXPECT_EQ(out.face_size(), 20);
693  /* Expect there to be a triangle with these three verts, oriented this way, with original face 1.
694  */
695  const Vert *v1 = mb.arena.find_vert(mpq3(2, 0, 0));
696  const Vert *v8 = mb.arena.find_vert(mpq3(0.5, 0.5, 1));
697  const Vert *v9 = mb.arena.find_vert(mpq3(1.5, 0.5, 1));
698  EXPECT_TRUE(v1 && v8 && v9);
699  if (v1 && v8 && v9) {
700  const Face *f = mb.arena.find_face({v1, v8, v9});
701  EXPECT_NE(f, nullptr);
702  if (f != nullptr) {
703  EXPECT_EQ(f->orig, 1);
704  int v1pos = f->vert[0] == v1 ? 0 : (f->vert[1] == v1 ? 1 : 2);
705  EXPECT_EQ(f->edge_orig[v1pos], NO_INDEX);
706  EXPECT_EQ(f->edge_orig[(v1pos + 1) % 3], NO_INDEX);
707  EXPECT_EQ(f->edge_orig[(v1pos + 2) % 3], 1001);
708  EXPECT_EQ(f->is_intersect[v1pos], false);
709  EXPECT_EQ(f->is_intersect[(v1pos + 1) % 3], true);
710  EXPECT_EQ(f->is_intersect[(v1pos + 2) % 3], false);
711  }
712  }
713  if (DO_OBJ) {
714  write_obj_mesh(out, "test_tc_3");
715  }
716 }
717 
718 TEST(mesh_intersect, CubeCubeStep)
719 {
720  const char *spec = R"(16 24
721  0 -1 0
722  0 -1 2
723  0 1 0
724  0 1 2
725  2 -1 0
726  2 -1 2
727  2 1 0
728  2 1 2
729  -1 -1 -1
730  -1 -1 1
731  -1 1 -1
732  -1 1 1
733  1 -1 -1
734  1 -1 1
735  1 1 -1
736  1 1 1
737  0 1 3
738  0 3 2
739  2 3 7
740  2 7 6
741  6 7 5
742  6 5 4
743  4 5 1
744  4 1 0
745  2 6 4
746  2 4 0
747  7 3 1
748  7 1 5
749  8 9 11
750  8 11 10
751  10 11 15
752  10 15 14
753  14 15 13
754  14 13 12
755  12 13 9
756  12 9 8
757  10 14 12
758  10 12 8
759  15 11 9
760  15 9 13
761  )";
762 
763  IMeshBuilder mb(spec);
764  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
765  out.populate_vert();
766  EXPECT_EQ(out.vert_size(), 22);
767  EXPECT_EQ(out.face_size(), 56);
768  if (DO_OBJ) {
769  write_obj_mesh(out, "test_cubecubestep");
770  }
771 
772  IMeshBuilder mb2(spec);
773  IMesh out2 = trimesh_nary_intersect(
774  mb2.imesh, 2, [](int t) { return t < 12 ? 0 : 1; }, false, &mb2.arena);
775  out2.populate_vert();
776  EXPECT_EQ(out2.vert_size(), 22);
777  EXPECT_EQ(out2.face_size(), 56);
778  if (DO_OBJ) {
779  write_obj_mesh(out2, "test_cubecubestep_nary");
780  }
781 }
782 
783 TEST(mesh_intersect, RectCross)
784 {
785  const char *spec = R"(8 4
786  3/2 0 1
787  -3/2 0 1
788  -3/2 0 -1
789  3/2 0 -1
790  1 0 -5
791  -1 0 -5
792  1 0 5
793  -1 0 5
794  1 0 3
795  1 3 2
796  5 4 6
797  5 6 7
798  )";
799 
800  IMeshBuilder mb(spec);
801  IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
802  out.populate_vert();
803  EXPECT_EQ(out.vert_size(), 17);
804  EXPECT_EQ(out.face_size(), 28);
805  if (DO_OBJ) {
806  write_obj_mesh(out, "test_rectcross");
807  }
808 }
809 # endif
810 
811 # if DO_PERF_TESTS
812 
813 static void get_sphere_params(
814  int nrings, int nsegs, bool triangulate, int *r_verts_num, int *r_faces_num)
815 {
816  *r_verts_num = nsegs * (nrings - 1) + 2;
817  if (triangulate) {
818  *r_faces_num = 2 * nsegs + 2 * nsegs * (nrings - 2);
819  }
820  else {
821  *r_faces_num = nsegs * nrings;
822  }
823 }
824 
825 static void fill_sphere_data(int nrings,
826  int nsegs,
827  const double3 &center,
828  double radius,
829  bool triangulate,
830  MutableSpan<Face *> face,
831  int vid_start,
832  int fid_start,
833  IMeshArena *arena)
834 {
835  int verts_num;
836  int faces_num;
837  get_sphere_params(nrings, nsegs, triangulate, &verts_num, &faces_num);
838  BLI_assert(faces_num == face.size());
839  Array<const Vert *> vert(verts_num);
840  const bool nrings_even = (nrings % 2 == 0);
841  int half_nrings = nrings / 2;
842  const bool nsegs_even = (nsegs % 2) == 0;
843  const bool nsegs_four_divisible = (nsegs % 4 == 0);
844  int half_nsegs = nrings;
845  int quarter_nsegs = half_nsegs / 2;
846  double delta_phi = 2 * M_PI / nsegs;
847  double delta_theta = M_PI / nrings;
848  int fid = fid_start;
849  int vid = vid_start;
850  auto vert_index_fn = [nrings, verts_num](int seg, int ring) {
851  if (ring == 0) { /* Top vert. */
852  return verts_num - 2;
853  }
854  if (ring == nrings) { /* Bottom vert. */
855  return verts_num - 1;
856  }
857  return seg * (nrings - 1) + (ring - 1);
858  };
859  auto face_index_fn = [nrings](int seg, int ring) { return seg * nrings + ring; };
860  auto tri_index_fn = [nrings, nsegs](int seg, int ring, int tri) {
861  if (ring == 0) {
862  return seg;
863  }
864  if (ring < nrings - 1) {
865  return nsegs + 2 * (ring - 1) * nsegs + 2 * seg + tri;
866  }
867  return nsegs + 2 * (nrings - 2) * nsegs + seg;
868  };
869  Array<int> eid = {0, 0, 0, 0}; /* Don't care about edge ids. */
870  /*
871  * (x, y, z) is given from inclination theta and azimuth phi,
872  * where: `0 <= theta <= pi; 0 <= phi <= 2pi`.
873  * `x = radius * sin(theta) cos(phi)`
874  * `y = radius * sin(theta) sin(phi)`
875  * `z = radius * cos(theta)`
876  */
877  for (int s = 0; s < nsegs; ++s) {
878  double phi = s * delta_phi;
879  double sin_phi;
880  double cos_phi;
881  /* Avoid use of trig functions for pi/2 divisible angles. */
882  if (s == 0) {
883  /* phi = 0. */
884  sin_phi = 0.0;
885  cos_phi = 1.0;
886  }
887  else if (nsegs_even && s == half_nsegs) {
888  /* phi = pi. */
889  sin_phi = 0.0;
890  cos_phi = -1.0;
891  }
892  else if (nsegs_four_divisible && s == quarter_nsegs) {
893  /* phi = pi/2. */
894  sin_phi = 1.0;
895  cos_phi = 0.0;
896  }
897  else if (nsegs_four_divisible && s == 3 * quarter_nsegs) {
898  /* phi = 3pi/2. */
899  sin_phi = -1.0;
900  cos_phi = 0.0;
901  }
902  else {
903  sin_phi = sin(phi);
904  cos_phi = cos(phi);
905  }
906  for (int r = 1; r < nrings; ++r) {
907  double theta = r * delta_theta;
908  double r_sin_theta;
909  double r_cos_theta;
910  if (nrings_even && r == half_nrings) {
911  /* theta = pi/2. */
912  r_sin_theta = radius;
913  r_cos_theta = 0.0;
914  }
915  else {
916  r_sin_theta = radius * sin(theta);
917  r_cos_theta = radius * cos(theta);
918  }
919  double x = r_sin_theta * cos_phi + center[0];
920  double y = r_sin_theta * sin_phi + center[1];
921  double z = r_cos_theta + center[2];
922  const Vert *v = arena->add_or_find_vert(mpq3(x, y, z), vid++);
923  vert[vert_index_fn(s, r)] = v;
924  }
925  }
926  const Vert *vtop = arena->add_or_find_vert(mpq3(center[0], center[1], center[2] + radius),
927  vid++);
928  const Vert *vbot = arena->add_or_find_vert(mpq3(center[0], center[1], center[2] - radius),
929  vid++);
930  vert[vert_index_fn(0, 0)] = vtop;
931  vert[vert_index_fn(0, nrings)] = vbot;
932  for (int s = 0; s < nsegs; ++s) {
933  int snext = (s + 1) % nsegs;
934  for (int r = 0; r < nrings; ++r) {
935  int rnext = r + 1;
936  int i0 = vert_index_fn(s, r);
937  int i1 = vert_index_fn(s, rnext);
938  int i2 = vert_index_fn(snext, rnext);
939  int i3 = vert_index_fn(snext, r);
940  Face *f;
941  Face *f2 = nullptr;
942  if (r == 0) {
943  f = arena->add_face({vert[i0], vert[i1], vert[i2]}, fid++, eid);
944  }
945  else if (r == nrings - 1) {
946  f = arena->add_face({vert[i0], vert[i1], vert[i3]}, fid++, eid);
947  }
948  else {
949  if (triangulate) {
950  f = arena->add_face({vert[i0], vert[i1], vert[i2]}, fid++, eid);
951  f2 = arena->add_face({vert[i2], vert[i3], vert[i0]}, fid++, eid);
952  }
953  else {
954  f = arena->add_face({vert[i0], vert[i1], vert[i2], vert[i3]}, fid++, eid);
955  }
956  }
957  if (triangulate) {
958  int f_index = tri_index_fn(s, r, 0);
959  face[f_index] = f;
960  if (r != 0 && r != nrings - 1) {
961  int f_index2 = tri_index_fn(s, r, 1);
962  face[f_index2] = f2;
963  }
964  }
965  else {
966  int f_index = face_index_fn(s, r);
967  face[f_index] = f;
968  }
969  }
970  }
971 }
972 
973 static void spheresphere_test(int nrings, double y_offset, bool use_self)
974 {
975  /* Make two UV-spheres with nrings rings ad 2*nrings segments. */
976  if (nrings < 2) {
977  return;
978  }
979  BLI_task_scheduler_init(); /* Without this, no parallelism. */
980  double time_start = PIL_check_seconds_timer();
981  IMeshArena arena;
982  int nsegs = 2 * nrings;
983  int sphere_verts_num;
984  int sphere_tris_num;
985  get_sphere_params(nrings, nsegs, true, &sphere_verts_num, &sphere_tris_num);
986  Array<Face *> tris(2 * sphere_tris_num);
987  arena.reserve(6 * sphere_verts_num / 2, 8 * sphere_tris_num);
988  double3 center1(0.0, 0.0, 0.0);
989  fill_sphere_data(nrings,
990  nsegs,
991  center1,
992  1.0,
993  true,
994  MutableSpan<Face *>(tris.begin(), sphere_tris_num),
995  0,
996  0,
997  &arena);
998  double3 center2(0.0, y_offset, 0.0);
999  fill_sphere_data(nrings,
1000  nsegs,
1001  center2,
1002  1.0,
1003  true,
1004  MutableSpan<Face *>(tris.begin() + sphere_tris_num, sphere_tris_num),
1005  sphere_verts_num,
1006  sphere_verts_num,
1007  &arena);
1008  IMesh mesh(tris);
1009  double time_create = PIL_check_seconds_timer();
1010  // write_obj_mesh(mesh, "spheresphere_in");
1011  IMesh out;
1012  if (use_self) {
1013  out = trimesh_self_intersect(mesh, &arena);
1014  }
1015  else {
1016  int nf = sphere_tris_num;
1017  out = trimesh_nary_intersect(
1018  mesh, 2, [nf](int t) { return t < nf ? 0 : 1; }, false, &arena);
1019  }
1020  double time_intersect = PIL_check_seconds_timer();
1021  std::cout << "Create time: " << time_create - time_start << "\n";
1022  std::cout << "Intersect time: " << time_intersect - time_create << "\n";
1023  std::cout << "Total time: " << time_intersect - time_start << "\n";
1024  if (DO_OBJ) {
1025  write_obj_mesh(out, "spheresphere");
1026  }
1028 }
1029 
1030 static void get_grid_params(
1031  int x_subdiv, int y_subdiv, bool triangulate, int *r_verts_num, int *r_faces_num)
1032 {
1033  *r_verts_num = x_subdiv * y_subdiv;
1034  if (triangulate) {
1035  *r_faces_num = 2 * (x_subdiv - 1) * (y_subdiv - 1);
1036  }
1037  else {
1038  *r_faces_num = (x_subdiv - 1) * (y_subdiv - 1);
1039  }
1040 }
1041 
1042 static void fill_grid_data(int x_subdiv,
1043  int y_subdiv,
1044  bool triangulate,
1045  double size,
1046  const double3 &center,
1047  double rot_deg,
1048  MutableSpan<Face *> face,
1049  int vid_start,
1050  int fid_start,
1051  IMeshArena *arena)
1052 {
1053  if (x_subdiv <= 1 || y_subdiv <= 1) {
1054  return;
1055  }
1056  int verts_num;
1057  int faces_num;
1058  get_grid_params(x_subdiv, y_subdiv, triangulate, &verts_num, &faces_num);
1059  BLI_assert(face.size() == faces_num);
1060  Array<const Vert *> vert(verts_num);
1061  auto vert_index_fn = [x_subdiv](int ix, int iy) { return iy * x_subdiv + ix; };
1062  auto face_index_fn = [x_subdiv](int ix, int iy) { return iy * (x_subdiv - 1) + ix; };
1063  auto tri_index_fn = [x_subdiv](int ix, int iy, int tri) {
1064  return 2 * iy * (x_subdiv - 1) + 2 * ix + tri;
1065  };
1066  Array<int> eid = {0, 0, 0, 0}; /* Don't care about edge ids. */
1067  double r = size / 2.0;
1068  double delta_x = size / (x_subdiv - 1);
1069  double delta_y = size / (y_subdiv - 1);
1070  int vid = vid_start;
1071  double cos_rot = cosf(rot_deg * M_PI / 180.0);
1072  double sin_rot = sinf(rot_deg * M_PI / 180.0);
1073  for (int iy = 0; iy < y_subdiv; ++iy) {
1074  double yy = iy * delta_y - r;
1075  for (int ix = 0; ix < x_subdiv; ++ix) {
1076  double xx = ix * delta_x - r;
1077  double x = center[0] + xx;
1078  double y = center[1] + yy;
1079  double z = center[2];
1080  if (rot_deg != 0.0) {
1081  x = center[0] + xx * cos_rot - yy * sin_rot;
1082  y = center[1] + xx * sin_rot + yy * cos_rot;
1083  }
1084  const Vert *v = arena->add_or_find_vert(mpq3(x, y, z), vid++);
1085  vert[vert_index_fn(ix, iy)] = v;
1086  }
1087  }
1088  int fid = fid_start;
1089  for (int iy = 0; iy < y_subdiv - 1; ++iy) {
1090  for (int ix = 0; ix < x_subdiv - 1; ++ix) {
1091  int i0 = vert_index_fn(ix, iy);
1092  int i1 = vert_index_fn(ix, iy + 1);
1093  int i2 = vert_index_fn(ix + 1, iy + 1);
1094  int i3 = vert_index_fn(ix + 1, iy);
1095  if (triangulate) {
1096  Face *f = arena->add_face({vert[i0], vert[i1], vert[i2]}, fid++, eid);
1097  Face *f2 = arena->add_face({vert[i2], vert[i3], vert[i0]}, fid++, eid);
1098  face[tri_index_fn(ix, iy, 0)] = f;
1099  face[tri_index_fn(ix, iy, 1)] = f2;
1100  }
1101  else {
1102  Face *f = arena->add_face({vert[i0], vert[i1], vert[i2], vert[i3]}, fid++, eid);
1103  face[face_index_fn(ix, iy)] = f;
1104  }
1105  }
1106  }
1107 }
1108 
1109 static void spheregrid_test(int nrings, int grid_level, double z_offset, bool use_self)
1110 {
1111  /* Make a uv-sphere and a grid.
1112  * The sphere is radius 1, has `nrings` rings and `2 * nrings` segments,
1113  * and is centered at (0,0,z_offset).
1114  * The plane is 4x4, has `2 ** grid_level` subdivisions x and y,
1115  * and is centered at the origin. */
1116  if (nrings < 2 || grid_level < 1) {
1117  return;
1118  }
1119  BLI_task_scheduler_init(); /* Without this, no parallelism. */
1120  double time_start = PIL_check_seconds_timer();
1121  IMeshArena arena;
1122  int sphere_verts_num;
1123  int sphere_tris_num;
1124  int nsegs = 2 * nrings;
1125  int grid_verts_num;
1126  int grid_tris_num;
1127  int subdivs = 1 << grid_level;
1128  get_sphere_params(nrings, nsegs, true, &sphere_verts_num, &sphere_tris_num);
1129  get_grid_params(subdivs, subdivs, true, &grid_verts_num, &grid_tris_num);
1130  Array<Face *> tris(sphere_tris_num + grid_tris_num);
1131  arena.reserve(3 * (sphere_verts_num + grid_verts_num) / 2,
1132  4 * (sphere_tris_num + grid_tris_num));
1133  double3 center(0.0, 0.0, z_offset);
1134  fill_sphere_data(nrings,
1135  nsegs,
1136  center,
1137  1.0,
1138  true,
1139  MutableSpan<Face *>(tris.begin(), sphere_tris_num),
1140  0,
1141  0,
1142  &arena);
1143  fill_grid_data(subdivs,
1144  subdivs,
1145  true,
1146  4.0,
1147  double3(0, 0, 0),
1148  0.0,
1149  MutableSpan<Face *>(tris.begin() + sphere_tris_num, grid_tris_num),
1150  sphere_verts_num,
1151  sphere_tris_num,
1152  &arena);
1153  IMesh mesh(tris);
1154  double time_create = PIL_check_seconds_timer();
1155  // write_obj_mesh(mesh, "spheregrid_in");
1156  IMesh out;
1157  if (use_self) {
1158  out = trimesh_self_intersect(mesh, &arena);
1159  }
1160  else {
1161  int nf = sphere_tris_num;
1162  out = trimesh_nary_intersect(
1163  mesh, 2, [nf](int t) { return t < nf ? 0 : 1; }, false, &arena);
1164  }
1165  double time_intersect = PIL_check_seconds_timer();
1166  std::cout << "Create time: " << time_create - time_start << "\n";
1167  std::cout << "Intersect time: " << time_intersect - time_create << "\n";
1168  std::cout << "Total time: " << time_intersect - time_start << "\n";
1169  if (DO_OBJ) {
1170  write_obj_mesh(out, "spheregrid");
1171  }
1173 }
1174 
1175 static void gridgrid_test(int x_level_1,
1176  int y_level_1,
1177  int x_level_2,
1178  int y_level_2,
1179  double x_off,
1180  double y_off,
1181  double rot_deg,
1182  bool use_self)
1183 {
1184  /* Make two grids, each 4x4, with given subdivision levels in x and y,
1185  * and the second offset from the first by x_off, y_off, and rotated by rot_deg degrees. */
1186  BLI_task_scheduler_init(); /* Without this, no parallelism. */
1187  double time_start = PIL_check_seconds_timer();
1188  IMeshArena arena;
1189  int x_subdivs_1 = 1 << x_level_1;
1190  int y_subdivs_1 = 1 << y_level_1;
1191  int x_subdivs_2 = 1 << x_level_2;
1192  int y_subdivs_2 = 1 << y_level_2;
1193  int grid_verts_1_num;
1194  int grid_verts_2_num;
1195  int grid_tris_1_num;
1196  int grid_tris_2_num;
1197  get_grid_params(x_subdivs_1, y_subdivs_1, true, &grid_verts_1_num, &grid_tris_1_num);
1198  get_grid_params(x_subdivs_2, y_subdivs_2, true, &grid_verts_2_num, &grid_tris_2_num);
1199  Array<Face *> tris(grid_tris_1_num + grid_tris_2_num);
1200  arena.reserve(3 * (grid_verts_1_num + grid_verts_2_num) / 2,
1201  4 * (grid_tris_1_num + grid_tris_2_num));
1202  fill_grid_data(x_subdivs_1,
1203  y_subdivs_1,
1204  true,
1205  4.0,
1206  double3(0, 0, 0),
1207  0.0,
1208  MutableSpan<Face *>(tris.begin(), grid_tris_1_num),
1209  0,
1210  0,
1211  &arena);
1212  fill_grid_data(x_subdivs_2,
1213  y_subdivs_2,
1214  true,
1215  4.0,
1216  double3(x_off, y_off, 0),
1217  rot_deg,
1218  MutableSpan<Face *>(tris.begin() + grid_tris_1_num, grid_tris_2_num),
1219  grid_verts_1_num,
1220  grid_tris_1_num,
1221  &arena);
1222  IMesh mesh(tris);
1223  double time_create = PIL_check_seconds_timer();
1224  // write_obj_mesh(mesh, "gridgrid_in");
1225  IMesh out;
1226  if (use_self) {
1227  out = trimesh_self_intersect(mesh, &arena);
1228  }
1229  else {
1230  int nf = grid_tris_1_num;
1231  out = trimesh_nary_intersect(
1232  mesh, 2, [nf](int t) { return t < nf ? 0 : 1; }, false, &arena);
1233  }
1234  double time_intersect = PIL_check_seconds_timer();
1235  std::cout << "Create time: " << time_create - time_start << "\n";
1236  std::cout << "Intersect time: " << time_intersect - time_create << "\n";
1237  std::cout << "Total time: " << time_intersect - time_start << "\n";
1238  if (DO_OBJ) {
1239  write_obj_mesh(out, "gridgrid");
1240  }
1242 }
1243 
1244 TEST(mesh_intersect_perf, SphereSphere)
1245 {
1246  spheresphere_test(512, 0.5, false);
1247 }
1248 
1249 TEST(mesh_intersect_perf, SphereSphereSelf)
1250 {
1251  spheresphere_test(64, 0.5, true);
1252 }
1253 
1254 TEST(mesh_intersect_perf, SphereGrid)
1255 {
1256  spheregrid_test(512, 4, 0.1, false);
1257 }
1258 
1259 TEST(mesh_intersect_perf, SphereGridSelf)
1260 {
1261  spheregrid_test(64, 4, 0.1, true);
1262 }
1263 
1264 TEST(mesh_intersect_perf, GridGrid)
1265 {
1266  gridgrid_test(8, 2, 4, 2, 0.1, 0.1, 0.0, false);
1267 }
1268 
1269 TEST(mesh_intersect_perf, GridGridTilt)
1270 {
1271  gridgrid_test(8, 2, 4, 2, 0.0, 0.0, 1.0, false);
1272 }
1273 
1274 # endif
1275 
1276 } // namespace blender::meshintersect::tests
1277 #endif
#define BLI_assert(a)
Definition: BLI_assert.h:46
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
#define M_PI
Definition: BLI_math_base.h:20
void BLI_task_scheduler_init(void)
void BLI_task_scheduler_exit(void)
@ TEST
NSNotificationCenter * center
_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 z
_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 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 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 i1
_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 t
_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 v1
Platform independent time functions.
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert * v
ccl_device_inline float delta_phi(int p, float gamma_o, float gamma_t)
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
static int verbose
Definition: cineonlib.c:29
#define sinf(x)
Definition: cuda/compat.h:102
#define cosf(x)
Definition: cuda/compat.h:101
static float verts[][3]
uint pos
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
vec_base< double, 3 > double3
std::string to_string(const T &n)
static const pxr::TfToken out("out", pxr::TfToken::Immortal)
double PIL_check_seconds_timer(void)
Definition: time.c:64