Search code examples
cgalboolean-operations

Subtracting multiple polyhedra continuously from a polyhedron

I want to get the result of subtracting multiple (probably hundreds) polyhedra from a polyhedron. I found that the CGAL library's "3D Boolean Operations on Nef Polyhedra" package supports Boolean Operations between Polyhedra. I wanted to use this package to solve my problem, but I ran into a lot of trouble. While I knew the CGAL library was a powerful one, I was completely new to it and had no idea how to use it most effectively to solve my problem. My goal is to use the CGAL library to implement one polyhedron minus multiple polyhedrons, and I'll go into more detail about this problem as well as my approach and the errors that the program produced. I'd appreciate it if you could tell me why the program is producing these errors and how I can efficiently use the CGAL library to implement one polyhedron minus multiple polyhedra.

The problem I want to solve with CGAL: I used MATLAB to get some polyhedra: A,B1,B2,...,Bi,..., Bn(n probably several hundred). I want to get the result of A-B1-B2-...-Bn.

My approach to solve this problem with CGAL library: In fact, only A is a 2-manifold, and Bi were both 3-dimensional surface with boundaries. In order to use CGAL library's "3D Boolean Operations on Nef Polyhedron" package, I turned these surfaces into closed polyhedrons. I saved A as a ".off" format file named "blank.off". Bi was converted to ".off" format, and all Bi were saved in one file named "sv.off". Each Bi is separated by a newline character. I use CGAL::OFF_to_nef_3() to read file "blank.off" into a Nef_polyhedron object nef1. Then I wrote a looping statement, in which I use CGAL::OFF_to_nef_3() to read file "sv.off" into a Nef_polyhedron object nef2 and do nef1-=nef2.

code is as follows:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

#include <CGAL/Polyhedron_3.h>

#include <CGAL/Nef_polyhedron_3.h>

#include <CGAL/IO/Polyhedron_iostream.h>

#include <CGAL/draw_nef_3.h>

#include <CGAL/OFF_to_nef_3.h>
    
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel; 

typedef CGAL::Polyhedron_3<Kernel>  Polyhedron;

typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;

#include<fstream>
#include<ctime>

int main() {

    Polyhedron p1, p2, res;
    int n = 0;

    std::ifstream fin1("blank.off");
    std::ifstream fin2("sv.off");
    std::cout << "how many polyhedra in sv.off\n";
    std::cin >> n;

    //load nef2 and do bool operations
    Nef_polyhedron nef1(p1);
    Nef_polyhedron nef2(p2);
    CGAL::OFF_to_nef_3(fin1, nef1);
    fin1.close();
    for (int i = 0; i < n;i++) {

        nef2.clear();
        CGAL::OFF_to_nef_3(fin2, nef2);
        fin2.get();

        nef1 -= nef2;
        std::cout << "A-B" << i+1 << " have been calculated" << std::endl;

    }

    //convert nef2 to res.off
    nef1.convert_to_polyhedron(res);
    std::ofstream fout("res.off");
    fout << res;

    //draw
    //CGAL::draw(nef1);
    fin2.close();

    return 0;
}

You can download blank.off and sv.off files from Github. Download link: blank.off and sv.off

Problems that occur while the program is running

  1. On the fifth iteration(i==4) of the program, sometimes the IDE will stop running or crash without any exception thrown. Why does this problem arise? Is it because the memory usage is too high?
  2. After 12 cycles(i==11), I want to convert nef1 to .off file to save current result. But it fails when the program reaches the sentence "nef1.convert_to_polyhedron(res)"since nef1.is_simple() returns false. I looked in the manual and I realized that this means that nef1 is no longer a 2-manifold. But what causes nef1 to no longer be a 2-manifold? Is there a function in the CGAL that can modify nef1 to make it a 2-manifold again?
  3. This is not an error, but the computing speed is too slow. Is there another way to do it faster?

Other problems: In fact, what I originally got using MATLAB were sets of points for the polyhedron A without boundary and the surface B with boundaries. In order to perform boolean operations on A and B. I wrote some programs with MATLAB to triangulate A and B, and convert B to closed polyhedron. I know the quality of triangulation mesh produced by the program is not high, which maybe the main reason why so many errors occur. Whether these can be done entirely with the CGAL library? How to do it? The most important question is whether the CGAL library is suitable for performing hundreds of continuous Boolean operations on three-dimensional geometry?

Thank you very much for reading this question, I would appreciate it if you could help me.

Solution

  • After playing a little with your inputs, I can say that the most plausible cause for all of your problems is that your insputs are not very clean. If you manage to remove degenerated faces from your OFFs in sv.off, everything should run fine. Now, there is a way to make everything much faster : corefine_and_compute_difference. If I adapt your code to use it, it looks like :

    #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/draw_surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Epic;

typedef CGAL::Surface_mesh<Epic::Point_3>  Surface_mesh;
int main() {
    std::cout << "how many polyhedra in sv.off\n";
    std::cin >> n;
    std::ifstream fin1("data/blank.off");
    std::ifstream fin2("data/sv.off");

    //load nef2 and do bool operations
    Surface_mesh s1, s2, out;
    CGAL::IO::read_OFF(fin1, s1);
    fin1.close();
    for (int i = 0; i < n;i++) {

        s2.clear();
        CGAL::IO::read_OFF(fin2, s2);
        fin2.get();

        std::ofstream fout("s2.off");
        fout << s2;
        fout.close();
        CGAL::Polygon_mesh_processing::corefine_and_compute_difference(s1, s2, s1);
        std::cout << "A-B" << i+1 << " have been calculated" << std::endl;

    }

    //convert nef2 to res.off
    std::ofstream fout("res.off");
    fout << s1;
    fout.close();
    //draw
    CGAL::draw(s1);
    fin2.close();

    return 0;
}

    But you have to be sure your sv meshes are "clean", they must not have degenerated faces, for example. From the shape of the first sv mesh, I'd say you can use CGAL's Advancing Front Surface Reconstruction (example here) to get your meshes from your point sets, and they should be clean enough. (I tried with the first one and it worked well).