5#include "testing/testing.h"
19#define DO_REGULAR_TESTS 1
20#define DO_PERF_TESTS 0
23namespace blender::meshintersect::tests {
26constexpr bool DO_OBJ =
false;
35 static constexpr int MAX_FACE_LEN = 1000;
37 static int edge_index(
int face_index,
int facepos)
39 return face_index * MAX_FACE_LEN + facepos;
42 static std::pair<int, int> face_and_pos_for_edge_index(
int e_index)
44 return std::pair<int, int>(e_index / MAX_FACE_LEN, e_index % MAX_FACE_LEN);
55 IMeshBuilder(
const char *spec)
57 std::istringstream ss(spec);
60 std::istringstream hdrss(line);
63 if (nv == 0 || nf == 0) {
66 arena.reserve(nv, nf);
67 Vector<const Vert *> verts;
71 while (v_index < nv && spec_ok && getline(ss, line)) {
72 std::istringstream iss(line);
76 iss >> p0 >> p1 >> p2;
77 spec_ok = !iss.fail();
79 verts.append(arena.add_or_find_vert(mpq3(p0, p1, p2), v_index));
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;
92 while (spec_ok && fss >> v_index) {
93 if (v_index < 0 || v_index >= nv) {
97 face_verts.append(verts[v_index]);
98 edge_orig.append(edge_index(f_index, fpos));
105 Face *facep = arena.add_face(face_verts, f_index, edge_orig);
114 std::cout <<
"Bad spec: " << spec;
117 imesh = IMesh(faces);
124static const Face *find_tri_with_verts(
const IMesh &mesh,
129 Face f_arg({v0, v1, v2}, 0, NO_INDEX);
130 for (
const Face *f : mesh.faces()) {
131 if (f->cyclic_equal(f_arg)) {
139static int count_tris_with_verts(
const IMesh &mesh,
const Vert *v0,
const Vert *v1,
const Vert *v2)
141 Face f_arg({v0, v1, v2}, 0, NO_INDEX);
143 for (
const Face *f : mesh.faces()) {
144 if (f->cyclic_equal(f_arg)) {
153static int find_edge_pos_in_tri(
const Vert *v0,
const Vert *v1,
const Face *f)
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)) {
167 Vector<const Vert *> verts;
168 Vector<Face *> faces;
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}));
177 const Face *f = mesh.face(0);
181TEST(mesh_intersect, TriangulateTri)
183 const char *spec = R
"(3 1
190 IMeshBuilder mb(spec);
191 IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
195TEST(mesh_intersect, TriangulateQuad)
197 const char *spec = R
"(4 1
205 IMeshBuilder mb(spec);
206 IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
210TEST(mesh_intersect, TriangulatePentagon)
212 const char *spec = R
"(5 1
221 IMeshBuilder mb(spec);
222 IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
225 write_obj_mesh(im_tri,
"pentagon");
229TEST(mesh_intersect, TriangulateTwoFaces)
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
243 IMeshBuilder mb(spec);
244 IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
247 write_obj_mesh(im_tri,
"twofaces");
251TEST(mesh_intersect, OneTri)
253 const char *spec = R
"(3 1
260 IMeshBuilder mb(spec);
261 IMesh imesh = trimesh_self_intersect(mb.imesh, &mb.arena);
262 imesh.populate_vert();
265 const Face &f_in = *mb.imesh.face(0);
266 const Face &f_out = *imesh.face(0);
268 for (
int i = 0; i < 3; ++i) {
270 EXPECT_EQ(f_in.edge_orig[i], f_out.edge_orig[i]);
274TEST(mesh_intersect, TriTri)
276 const char *spec = R
"(6 2
288 IMeshBuilder mb(spec);
289 IMesh
out = trimesh_self_intersect(mb.imesh, &mb.arena);
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 &&
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 &&
317 if (f0 !=
nullptr && f1 !=
nullptr && f2 !=
nullptr && f3 !=
nullptr && f4 !=
nullptr) {
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) {
333 f1->edge_orig[e34] == 1 * IMeshBuilder::MAX_FACE_LEN);
334 EXPECT_EQ(f1->edge_orig[e45], 1 * IMeshBuilder::MAX_FACE_LEN + 1);
341 write_obj_mesh(
out,
"tritri");
345TEST(mesh_intersect, TriTriReversed)
349 const char *spec = R
"(6 2
360 IMeshBuilder mb(spec);
361 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
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 &&
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 &&
389 if (f0 !=
nullptr && f1 !=
nullptr && f2 !=
nullptr && f3 !=
nullptr && f4 !=
nullptr) {
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) {
405 f1->edge_orig[e34] == 1 * IMeshBuilder::MAX_FACE_LEN + 2);
406 EXPECT_EQ(f1->edge_orig[e45], 1 * IMeshBuilder::MAX_FACE_LEN + 1);
413 write_obj_mesh(
out,
"tritrirev");
417TEST(mesh_intersect, TwoTris)
419 Array<mpq3> verts = {
420 mpq3(1, 1, 1), mpq3(1, 4, 1), mpq3(1, 1, 4),
421 mpq3(2, 2, 2), mpq3(-3, 3, 2), mpq3(-4, 1, 3),
422 mpq3(2, 2, 2), mpq3(-3, 3, 2), mpq3(0, 3, 5),
423 mpq3(2, 2, 2), mpq3(-3, 3, 2), mpq3(0, 3, 3),
424 mpq3(1, 0, 0), mpq3(2, 4, 1), mpq3(-3, 2, 2),
425 mpq3(0, 2, 1), mpq3(-2, 3, 3), mpq3(0, 1, 3),
426 mpq3(1.5, 2, 0.5), mpq3(-2, 3, 3), mpq3(0, 1, 3),
427 mpq3(1, 0, 0), mpq3(-2, 3, 3), mpq3(0, 1, 3),
428 mpq3(1, 0, 0), mpq3(-3, 2, 2), mpq3(0, 1, 3),
429 mpq3(1, 0, 0), mpq3(-1, 1, 1), mpq3(0, 1, 3),
430 mpq3(3, -1, -1), mpq3(-1, 1, 1), mpq3(0, 1, 3),
431 mpq3(0, 0.5, 0.5), mpq3(-1, 1, 1), mpq3(0, 1, 3),
432 mpq3(2, 1, 1), mpq3(3, 5, 2), mpq3(-2, 3, 3),
433 mpq3(2, 1, 1), mpq3(3, 5, 2), mpq3(-2, 3, 4),
434 mpq3(2, 2, 5), mpq3(-3, 3, 5), mpq3(0, 3, 10),
435 mpq3(0, 0, 0), mpq3(4, 4, 0), mpq3(-4, 2, 4),
436 mpq3(0, 1.5, 1), mpq3(1, 2.5, 1), mpq3(-1, 2, 2),
437 mpq3(3, 0, -2), mpq3(7, 4, -2), mpq3(-1, 2, 2),
438 mpq3(3, 0, -2), mpq3(3, 6, 2), mpq3(-1, 2, 2),
439 mpq3(7, 4, -2), mpq3(3, 6, 2), mpq3(-1, 2, 2),
440 mpq3(5, 2, -2), mpq3(1, 4, 2), mpq3(-3, 0, 2),
441 mpq3(2, 2, 0), mpq3(1, 4, 2), mpq3(-3, 0, 2),
442 mpq3(0, 0, 0), mpq3(4, 4, 0), mpq3(-3, 0, 2),
443 mpq3(0, 0, 0), mpq3(4, 4, 0), mpq3(-1, 2, 2),
444 mpq3(2, 2, 0), mpq3(4, 4, 0), mpq3(0, 3, 2),
445 mpq3(0, 0, 0), mpq3(-4, 2, 4), mpq3(4, 4, 0),
447 struct two_tri_test_spec {
479 static int perms[6][3] = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
481 const int do_only_test = -1;
482 for (
int test = 0; test < test_tris.size(); ++test) {
483 if (do_only_test >= 0 && test != do_only_test) {
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;
491 const bool verbose =
false;
494 std::cout <<
"\nTest " << test <<
": T" << tri1_index <<
" intersect T" << tri2_index
498 const bool do_all_perms =
true;
499 const int perm_limit = do_all_perms ? 3 : 1;
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";
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);
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);
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) {
526 std::string name =
"test_tt_in" + std::to_string(test);
527 write_obj_mesh(in_mesh, name);
529 std::string name =
"test_tt" + std::to_string(test);
530 write_obj_mesh(out_mesh, name);
537TEST(mesh_intersect, OverlapCluster)
542 const char *spec = R
"(15 5
565 IMeshBuilder mb(spec);
566 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
571 write_obj_mesh(
out,
"overlapcluster");
575TEST(mesh_intersect, TriCornerCross1)
578 const char *spec = R
"(12 4
597 IMeshBuilder mb(spec);
598 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
603 write_obj_mesh(
out,
"test_tc_1");
607TEST(mesh_intersect, TriCornerCross2)
610 const char *spec = R
"(12 4
629 IMeshBuilder mb(spec);
630 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
635 write_obj_mesh(
out,
"test_tc_2");
639TEST(mesh_intersect, TriCornerCross3)
642 const char *spec = R
"(12 4
661 IMeshBuilder mb(spec);
662 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
667 write_obj_mesh(
out,
"test_tc_3");
671TEST(mesh_intersect, TetTet)
673 const char *spec = R
"(8 8
692 IMeshBuilder mb(spec);
693 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
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));
703 if (v1 && v8 && v9) {
704 const Face *f = mb.arena.find_face({v1, v8, v9});
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);
718 write_obj_mesh(
out,
"test_tc_3");
722TEST(mesh_intersect, CubeCubeStep)
724 const char *spec = R
"(16 24
767 IMeshBuilder mb(spec);
768 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
773 write_obj_mesh(
out,
"test_cubecubestep");
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();
783 write_obj_mesh(out2,
"test_cubecubestep_nary");
787TEST(mesh_intersect, RectCross)
789 const char *spec = R
"(8 4
804 IMeshBuilder mb(spec);
805 IMesh out = trimesh_self_intersect(mb.imesh, &mb.arena);
810 write_obj_mesh(
out,
"test_rectcross");
817static void get_sphere_params(
818 int nrings,
int nsegs,
bool triangulate,
int *r_verts_num,
int *r_faces_num)
820 *r_verts_num = nsegs * (nrings - 1) + 2;
822 *r_faces_num = 2 * nsegs + 2 * nsegs * (nrings - 2);
825 *r_faces_num = nsegs * nrings;
829static void fill_sphere_data(
int nrings,
831 const double3 ¢er,
834 MutableSpan<Face *> face,
841 get_sphere_params(nrings, nsegs, triangulate, &verts_num, &faces_num);
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;
851 double delta_theta =
M_PI / nrings;
854 auto vert_index_fn = [nrings, verts_num](
int seg,
int ring) {
856 return verts_num - 2;
858 if (ring == nrings) {
859 return verts_num - 1;
861 return seg * (nrings - 1) + (ring - 1);
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) {
868 if (ring < nrings - 1) {
869 return nsegs + 2 * (ring - 1) * nsegs + 2 * seg + tri;
871 return nsegs + 2 * (nrings - 2) * nsegs + seg;
873 Array<int> eid = {0, 0, 0, 0};
881 for (
int s = 0; s < nsegs; ++s) {
891 else if (nsegs_even && s == half_nsegs) {
896 else if (nsegs_four_divisible && s == quarter_nsegs) {
901 else if (nsegs_four_divisible && s == 3 * quarter_nsegs) {
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) {
916 radius_sin_theta = radius;
917 radius_cos_theta = 0.0;
920 radius_sin_theta = radius *
sin(theta);
921 radius_cos_theta = radius *
cos(theta);
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;
930 const Vert *vtop = arena->add_or_find_vert(mpq3(center[0], center[1], center[2] + radius),
932 const Vert *vbot = arena->add_or_find_vert(mpq3(center[0], center[1], center[2] - radius),
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) {
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);
947 f = arena->add_face({vert[i0], vert[i1], vert[i2]}, fid++, eid);
949 else if (r == nrings - 1) {
950 f = arena->add_face({vert[i0], vert[i1], vert[i3]}, fid++, eid);
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);
958 f = arena->add_face({vert[i0], vert[i1], vert[i2], vert[i3]}, fid++, eid);
962 int f_index = tri_index_fn(s, r, 0);
964 if (r != 0 && r != nrings - 1) {
965 int f_index2 = tri_index_fn(s, r, 1);
970 int f_index = face_index_fn(s, r);
977static void spheresphere_test(
int nrings,
double y_offset,
bool use_self)
983 BLI_task_scheduler_init();
984 double time_start = BLI_time_now_seconds();
986 int nsegs = 2 * nrings;
987 int sphere_verts_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,
998 MutableSpan<Face *>(tris.begin(), sphere_tris_num),
1002 double3 center2(0.0, y_offset, 0.0);
1003 fill_sphere_data(nrings,
1008 MutableSpan<Face *>(tris.begin() + sphere_tris_num, sphere_tris_num),
1013 double time_create = BLI_time_now_seconds();
1017 out = trimesh_self_intersect(mesh, &arena);
1020 int nf = sphere_tris_num;
1021 out = trimesh_nary_intersect(mesh, 2, [nf](
int t) {
return t < nf ? 0 : 1; },
false, &arena);
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";
1028 write_obj_mesh(
out,
"spheresphere");
1030 BLI_task_scheduler_exit();
1033static void get_grid_params(
1034 int x_subdiv,
int y_subdiv,
bool triangulate,
int *r_verts_num,
int *r_faces_num)
1036 *r_verts_num = x_subdiv * y_subdiv;
1038 *r_faces_num = 2 * (x_subdiv - 1) * (y_subdiv - 1);
1041 *r_faces_num = (x_subdiv - 1) * (y_subdiv - 1);
1045static void fill_grid_data(
int x_subdiv,
1049 const double3 ¢er,
1051 MutableSpan<Face *> face,
1056 if (x_subdiv <= 1 || y_subdiv <= 1) {
1061 get_grid_params(x_subdiv, y_subdiv, triangulate, &verts_num, &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;
1069 Array<int> eid = {0, 0, 0, 0};
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;
1087 const Vert *v = arena->add_or_find_vert(mpq3(
x,
y,
z), vid++);
1088 vert[vert_index_fn(ix, iy)] = v;
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);
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;
1105 Face *f = arena->add_face({vert[i0], vert[i1], vert[i2], vert[i3]}, fid++, eid);
1106 face[face_index_fn(ix, iy)] = f;
1112static void spheregrid_test(
int nrings,
int grid_level,
double z_offset,
bool use_self)
1119 if (nrings < 2 || grid_level < 1) {
1122 BLI_task_scheduler_init();
1123 double time_start = BLI_time_now_seconds();
1125 int sphere_verts_num;
1126 int sphere_tris_num;
1127 int nsegs = 2 * nrings;
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,
1142 MutableSpan<Face *>(tris.begin(), sphere_tris_num),
1146 fill_grid_data(subdivs,
1152 MutableSpan<Face *>(tris.begin() + sphere_tris_num, grid_tris_num),
1157 double time_create = BLI_time_now_seconds();
1161 out = trimesh_self_intersect(mesh, &arena);
1164 int nf = sphere_tris_num;
1165 out = trimesh_nary_intersect(mesh, 2, [nf](
int t) {
return t < nf ? 0 : 1; },
false, &arena);
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";
1172 write_obj_mesh(
out,
"spheregrid");
1174 BLI_task_scheduler_exit();
1177static void gridgrid_test(
int x_level_1,
1188 BLI_task_scheduler_init();
1189 double time_start = BLI_time_now_seconds();
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,
1210 MutableSpan<Face *>(tris.begin(), grid_tris_1_num),
1214 fill_grid_data(x_subdivs_2,
1218 double3(x_off, y_off, 0),
1220 MutableSpan<Face *>(tris.begin() + grid_tris_1_num, grid_tris_2_num),
1225 double time_create = BLI_time_now_seconds();
1229 out = trimesh_self_intersect(mesh, &arena);
1232 int nf = grid_tris_1_num;
1233 out = trimesh_nary_intersect(mesh, 2, [nf](
int t) {
return t < nf ? 0 : 1; },
false, &arena);
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";
1240 write_obj_mesh(
out,
"gridgrid");
1242 BLI_task_scheduler_exit();
1245TEST(mesh_intersect_perf, SphereSphere)
1247 spheresphere_test(512, 0.5,
false);
1250TEST(mesh_intersect_perf, SphereSphereSelf)
1252 spheresphere_test(64, 0.5,
true);
1255TEST(mesh_intersect_perf, SphereGrid)
1257 spheregrid_test(512, 4, 0.1,
false);
1260TEST(mesh_intersect_perf, SphereGridSelf)
1262 spheregrid_test(64, 4, 0.1,
true);
1265TEST(mesh_intersect_perf, GridGrid)
1267 gridgrid_test(8, 2, 4, 2, 0.1, 0.1, 0.0,
false);
1270TEST(mesh_intersect_perf, GridGridTilt)
1272 gridgrid_test(8, 2, 4, 2, 0.0, 0.0, 1.0,
false);
Platform independent time functions.
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)
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define EXPECT_EQ(result, expect)