Fix T82301, exact boolean fail on cube with bump.

The code for determining coplanar clusters had a bug where it would
miss some triangles. The fix for now is to just put triangles in
the cluster if their bounding boxes overlap. This works but maybe
makes clusters bigger then they have to be. I'll follow this commit
with work on making the CDT routine faster when using exact arithmetic.
Also removed a lot of unused code, and added some new intersect
performance tests.

1 files changed, 100 insertions, 2 deletions

diff --git a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
index 7b0f05444e2..fef4a52d9c9 100644
--- a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
+++ b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
@@ -968,6 +968,7 @@ static void fill_grid_data(int x_subdiv,
                            bool triangulate,
                            double size,
                            const double3 &center,
+                           double rot_deg,
                            MutableSpan<Face *> face,
                            int vid_start,
                            int fid_start,
@@ -991,11 +992,19 @@ static void fill_grid_data(int x_subdiv,
   double delta_x = size / (x_subdiv - 1);
   double delta_y = size / (y_subdiv - 1);
   int vid = vid_start;
+  double cos_rot = cosf(rot_deg * M_PI / 180.0);
+  double sin_rot = sinf(rot_deg * M_PI / 180.0);
   for (int iy = 0; iy < y_subdiv; ++iy) {
+    double yy = iy * delta_y - r;
     for (int ix = 0; ix < x_subdiv; ++ix) {
-      double x = center[0] - r + ix * delta_x;
-      double y = center[1] - r + iy * delta_y;
+      double xx = ix * delta_x - r;
+      double x = center[0] + xx;
+      double y = center[1] + yy;
       double z = center[2];
+      if (rot_deg != 0.0) {
+        x = center[0] + xx * cos_rot - yy * sin_rot;
+        y = center[1] + xx * sin_rot + yy * cos_rot;
+      }
       const Vert *v = arena->add_or_find_vert(mpq3(x, y, z), vid++);
       vert[vert_index_fn(ix, iy)] = v;
     }
@@ -1059,6 +1068,7 @@ static void spheregrid_test(int nrings, int grid_level, double z_offset, bool us
                  true,
                  4.0,
                  double3(0, 0, 0),
+                 0.0,
                  MutableSpan<Face *>(tris.begin() + num_sphere_tris, num_grid_tris),
                  num_sphere_verts,
                  num_sphere_tris,
@@ -1085,16 +1095,104 @@ static void spheregrid_test(int nrings, int grid_level, double z_offset, bool us
   BLI_task_scheduler_exit();
 }
 
+static void gridgrid_test(int x_level_1,
+                          int y_level_1,
+                          int x_level_2,
+                          int y_level_2,
+                          double x_off,
+                          double y_off,
+                          double rot_deg,
+                          bool use_self)
+{
+  /* Make two grids, each 4x4, with given subdivision levels in x and y,
+   * and the second offset from the first by x_off, y_off, and rotated by rot_deg degrees. */
+  BLI_task_scheduler_init(); /* Without this, no parallelism. */
+  double time_start = PIL_check_seconds_timer();
+  IMeshArena arena;
+  int x_subdivs_1 = 1 << x_level_1;
+  int y_subdivs_1 = 1 << y_level_1;
+  int x_subdivs_2 = 1 << x_level_2;
+  int y_subdivs_2 = 1 << y_level_2;
+  int num_grid_verts_1;
+  int num_grid_verts_2;
+  int num_grid_tris_1;
+  int num_grid_tris_2;
+  get_grid_params(x_subdivs_1, y_subdivs_1, true, &num_grid_verts_1, &num_grid_tris_1);
+  get_grid_params(x_subdivs_2, y_subdivs_2, true, &num_grid_verts_2, &num_grid_tris_2);
+  Array<Face *> tris(num_grid_tris_1 + num_grid_tris_2);
+  arena.reserve(num_grid_verts_1 + num_grid_verts_2, num_grid_tris_1 + num_grid_tris_2);
+  fill_grid_data(x_subdivs_1,
+                 y_subdivs_1,
+                 true,
+                 4.0,
+                 double3(0, 0, 0),
+                 0.0,
+                 MutableSpan<Face *>(tris.begin(), num_grid_tris_1),
+                 0,
+                 0,
+                 &arena);
+  fill_grid_data(x_subdivs_2,
+                 y_subdivs_2,
+                 true,
+                 4.0,
+                 double3(x_off, y_off, 0),
+                 rot_deg,
+                 MutableSpan<Face *>(tris.begin() + num_grid_tris_1, num_grid_tris_2),
+                 num_grid_verts_1,
+                 num_grid_tris_1,
+                 &arena);
+  IMesh mesh(tris);
+  double time_create = PIL_check_seconds_timer();
+  // write_obj_mesh(mesh, "gridgrid_in");
+  IMesh out;
+  if (use_self) {
+    out = trimesh_self_intersect(mesh, &arena);
+  }
+  else {
+    int nf = num_grid_tris_1;
+    out = trimesh_nary_intersect(
+        mesh, 2, [nf](int t) { return t < nf ? 0 : 1; }, false, &arena);
+  }
+  double time_intersect = PIL_check_seconds_timer();
+  std::cout << "Create time: " << time_create - time_start << "\n";
+  std::cout << "Intersect time: " << time_intersect - time_create << "\n";
+  std::cout << "Total time: " << time_intersect - time_start << "\n";
+  if (DO_OBJ) {
+    write_obj_mesh(out, "gridgrid");
+  }
+  BLI_task_scheduler_exit();
+}
+
 TEST(mesh_intersect_perf, SphereSphere)
 {
   spheresphere_test(512, 0.5, false);
 }
 
+TEST(mesh_intersect_perf, SphereSphereSelf)
+{
+  spheresphere_test(64, 0.5, true);
+}
+
 TEST(mesh_intersect_perf, SphereGrid)
 {
   spheregrid_test(512, 4, 0.1, false);
 }
 
+TEST(mesh_intersect_perf, SphereGridSelf)
+{
+  spheregrid_test(64, 4, 0.1, true);
+}
+
+TEST(mesh_intersect_perf, GridGrid)
+{
+  gridgrid_test(8, 2, 4, 2, 0.1, 0.1, 0.0, false);
+}
+
+TEST(mesh_intersect_perf, GridGridTilt)
+{
+  gridgrid_test(8, 2, 4, 2, 0.0, 0.0, 1.0, false);
+}
+
 #  endif
 
 }  // namespace blender::meshintersect::tests