Mesh Boolean Difference (Consecutive ) #9497

Activity

1. petrasvestartas commented on May 26, 2026

   

   petrasvestartas

   on May 26, 2026

   Last edited by petrasvestartas

   Author

   More actions

   The problem is really happens when elements are collinear, I am talking about -80.000000000000043 ~1e-14 level. This happens when doing Python Transformation using doubles. This is something that corefinement cannot catch if input is such. The obj files will work on c++ because CGAL IO obj will round to decimal places and would work.

   It is quite tricky to catch these bugs.

   The key issue is this: corefine_and_compute_difference returns false (failed) on valid closed meshes with both EPICK and EPECK, while union/intersection/swapped-difference all succeed on the same input. The problem is specifically the dirty cutter as operand B of A - B.

   Since obj will round coordinates I share .off files:

   cgal_debug.zip

   // Minimal reproducer for CGAL corefine_and_compute_difference returning false
   // on valid closed triangle meshes.
   //
   // corefine_and_compute_difference(A, B, out) returns ok=0, empty output.
   // corefine_and_compute_union(A, B, out)         returns ok=1, valid output.
   // corefine_and_compute_intersection(A, B, out)  returns ok=1, valid output.
   // corefine_and_compute_difference(B, A, out)    returns ok=1, valid output.
   //
   // Both meshes are valid, closed, consistently oriented triangle meshes.
   // The issue is triggered by sub-ULP floating-point noise (~1e-14) in mesh B's
   // vertex coordinates, introduced by a 4x4 transformation matrix multiply.
   //
   // Tested with CGAL 6.0.1, both EPICK and EPECK kernels.
   // Build: cmake with header-only CGAL + Boost multiprecision (no GMP).
   
   #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
   #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
   #include <CGAL/Surface_mesh.h>
   #include <CGAL/Polygon_mesh_processing/corefinement.h>
   #include <CGAL/IO/OFF.h>
   
   #include <iostream>
   #include <fstream>
   #include <string>
   
   namespace PMP = CGAL::Polygon_mesh_processing;
   
   typedef CGAL::Exact_predicates_inexact_constructions_kernel EPICK;
   typedef CGAL::Exact_predicates_exact_constructions_kernel  EPECK;
   
   template <typename K>
   bool run_test(const std::string& label,
                 const std::string& target_path,
                 const std::string& cutter_path)
   {
       using Mesh = CGAL::Surface_mesh<typename K::Point_3>;
   
       Mesh target, cutter;
   
       std::ifstream t_in(target_path);
       std::ifstream c_in(cutter_path);
       if (!t_in || !c_in) { std::cerr << "Cannot open files" << std::endl; return false; }
       CGAL::IO::read_OFF(t_in, target);
       CGAL::IO::read_OFF(c_in, cutter);
   
       std::cout << label << std::endl;
       std::cout << "  target: V=" << target.number_of_vertices()
                 << " F=" << target.number_of_faces()
                 << " closed=" << CGAL::is_closed(target) << std::endl;
       std::cout << "  cutter: V=" << cutter.number_of_vertices()
                 << " F=" << cutter.number_of_faces()
                 << " closed=" << CGAL::is_closed(cutter) << std::endl;
   
       // A - B (the failing case)
       {
           Mesh a = target, b = cutter, out;
           bool ok = PMP::corefine_and_compute_difference(a, b, out);
           std::cout << "  A - B:  ok=" << ok
                     << " V=" << out.number_of_vertices()
                     << " F=" << out.number_of_faces() << std::endl;
       }
       // A union B
       {
           Mesh a = target, b = cutter, out;
           bool ok = PMP::corefine_and_compute_union(a, b, out);
           std::cout << "  A | B:  ok=" << ok
                     << " V=" << out.number_of_vertices()
                     << " F=" << out.number_of_faces() << std::endl;
       }
       // A intersect B
       {
           Mesh a = target, b = cutter, out;
           bool ok = PMP::corefine_and_compute_intersection(a, b, out);
           std::cout << "  A & B:  ok=" << ok
                     << " V=" << out.number_of_vertices()
                     << " F=" << out.number_of_faces() << std::endl;
       }
       // B - A (swapped)
       {
           Mesh a = target, b = cutter, out;
           bool ok = PMP::corefine_and_compute_difference(b, a, out);
           std::cout << "  B - A:  ok=" << ok
                     << " V=" << out.number_of_vertices()
                     << " F=" << out.number_of_faces() << std::endl;
       }
       return true;
   }
   
   int main(int argc, char* argv[]) {
       std::string data_dir = "..";
       if (argc > 1) data_dir = argv[1];
   
       std::string target = data_dir + "/dirty_target.off";
       std::string cutter = data_dir + "/dirty_cutter.off";
   
       run_test<EPICK>("=== EPICK ===", target, cutter);
       std::cout << std::endl;
       run_test<EPECK>("=== EPECK ===", target, cutter);
   
       return 0;
   }
   
   
2. petrasvestartas commented on May 26, 2026

   

   petrasvestartas

   on May 26, 2026

   Author

   More actions

   I will try try autorefine_triangle_soup with apply_iterative_snap_rounding(true) .
3. petrasvestartas commented on May 26, 2026

   

   petrasvestartas

   on May 26, 2026

   Last edited by petrasvestartas

   Author

   More actions

   No, this does not help: https://doc.cgal.org/6.2-beta1/PMP_Boolean_operations/PMP_Boolean_operations_2corefinement_consecutive_bool_op_8cpp-example.html , we are really talking about super small tolerance, even input meshes are simple and completely valid.

   I am talking about precision of these edges, marked in red:

   
4. sloriot commented on Jun 1, 2026

   

   sloriot

   on Jun 1, 2026

   Member

   More actions

   OK as you said, the situation here is like in the drawing:

   

   when you are subtracting yellow you create a non-manifold connection between two red volumes.

   You can successfully compute the resulting triangle soup using either #9363 or the non-manifold visitor.

   However, you will end up with something that is a polygon soup and only #9363 is able to do any additional Boolean operations.

   If you are in a case where most of the things happening are axis-aligned, then a coordinate snapping might be the way to go (especially if you already know that some intermediate single float are used somewhere in the pipeline). Could that be something working for you?
5. petrasvestartas commented on Jun 1, 2026

   

   petrasvestartas

   on Jun 1, 2026

   Last edited by petrasvestartas

   Author

   More actions

   The situation is this, and yes because of imprecision it results in what you drew:

   

   The rounding helps, but this is because it is a specific case where I know what I do. If a user is not a software developer, then these cases would be troublesome to debug. Most of the user cases we have are in CAD, and they use doubles in the kernel.

   I am wondering if snapping to coordinates could be part of CGAL Mesh Boolean.

   I will try the PR and the example you referenced.
6. MaelRL

   added

   Pkg::PMP

   on Jun 1, 2026
7. sloriot commented on Jun 1, 2026

   

   sloriot

   on Jun 1, 2026

   Member

   More actions

   As I said, trying the PR and example will probably not help because you will end up with a soup.

   About snapping in CGAL, that was indeed my idea to have a pre-processing function. I did some tests in a PR, and in particular this commit:

   e94be55

   I'm expecting it to work great in your case, but in general cases, it was still missing some steps.
8. MaelRL

   assigned

   sloriot

   on Jun 3, 2026
9. MaelRL

   changed the title [-]Mesh Boolean Difference (Consequtive )[/-] [+]Mesh Boolean Difference (Consecutive )[/+] on Sep 22, 2026
10. MaelRL

    added this to the 6.4-beta milestone on Oct 5, 2026