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