一个多面体连续减去多个多面体

Question

我想得到一个多面体减去多个（可能是几百个）多面体的结果。我发现 CGAL 库的“3D Boolean Operations on Nef Polyhedra”包支持多面体之间的布尔运算。我想用这个包来解决我的问题，但是我运行陷入了很多麻烦。虽然我知道 CGAL 库是一个强大的库，但我对它完全陌生，不知道如何最有效地使用它来解决我的问题。我的目标是使用 CGAL 库实现一个多面体减去多个多面体，我将更详细地介绍这个问题以及我的方法和程序产生的错误。如果你能告诉我为什么程序会产生这些错误以及我如何有效地使用 CGAL 库来实现一个多面体减去多个多面体，我将不胜感激。

我想用CGAL解决的问题： 我用 MATLAB 得到了一些多面体：A,B1,B2,...,Bi,..., Bn（n 可能有几百个）。我想得到 A-B1-B2-...-Bn.

的结果

我用CGAL库解决这个问题的方法： 事实上，只有A是2-流形，而Bi都是有边界的3维曲面。为了使用 CGAL 库的“Nef 多面体上的 3D 布尔运算”包，我将这些表面变成了闭合多面体。我将 A 保存为名为“blank.off”的“.off”格式文件。 Bi 被转换为“.off”格式，所有 Bi 都保存在一个名为“sv.off”的文件中。每个 Bi 由换行符分隔。我使用 CGAL::OFF_to_nef_3() 将文件“blank.off”读入 Nef_polyhedron 对象 nef1。然后我写了一个循环语句，其中我使用 CGAL::OFF_to_nef_3() 将文件“sv.off”读入 Nef_polyhedron 对象 nef2 并执行 nef1-=nef2.

代码如下：

#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;
}

您可以从 Github 下载 blank.off 和 sv.off 文件。下载link：blank.off and sv.off

程序运行时出现的问题运行

在程序的第五次迭代 (i==4) 中，有时 IDE 会停止运行或崩溃而不会抛出任何异常。为什么会出现这个问题？是不是内存占用太高了？
12 次循环后(i==11)，我想将nef1 转换为.off 文件以保存当前结果。但是当程序执行到"nef1.convert_to_polyhedron(res)"since nef1.is_simple() returns false这句时就失败了。我查看了手册，意识到这意味着 nef1 不再是 2-流形。但是是什么导致 nef1 不再是 2-流形？ CGAL 中是否有函数可以修改 nef1 使其再次成为 2-流形？
这不是错误，而是计算速度太慢了。还有其他方法可以更快吗？

其他问题： 事实上，我最初使用 MATLAB 得到的是无边界的多面体 A 和有边界的曲面 B 的点集。为了对A和B进行布尔运算，我用MATLAB编写了一些程序来对A和B进行三角剖分，并将B转换为闭合多面体。我知道程序生成的三角网格质量不高，这可能是出现这么多错误的主要原因。这些是否完全可以用 CGAL 库来完成？怎么做？最重要的问题是CGAL库是否适合对三维几何进行数百次连续的布尔运算？

非常感谢您阅读这个问题，如果您能帮助我，我将不胜感激。

Answer 1

在对您的输入进行了一些研究之后，我可以说您所有问题的最合理原因是您的输入不是很干净。如果您设法从 sv.off 的 OFF 中移除退化的面孔，一切都应该运行没问题。现在，有一种方法可以使一切变得更快：corefine_and_compute_difference。如果我调整你的代码来使用它，它看起来像：

#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;
}

但是您必须确保您的 sv 网格是“干净的”，例如它们不能有退化的面。从第一个 sv 网格的形状来看，我想说你可以使用 CGAL 的 Advancing Front Surface Reconstruction (example here) 从你的点集中获取你的网格，它们应该足够干净。（我试过第一个，效果很好）。

一个多面体连续减去多个多面体

Subtracting multiple polyhedra continuously from a polyhedron

cgal

boolean-operations