CGAL::Polyhedron_3调用make_tetrahedron产生重复顶点如何解决？

我在使用CGAL::Polyhedron_3数据结构生成体网格的测试过程中，发现make_tetrahedron函数会重复存储多面体中已存在的顶点。

测试场景：两个共享公共面的四面体 #

测试代码 #

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <iostream>

typedef CGAL::Simple_cartesian<double>     Kernel;
typedef Kernel::Point_3                    Point_3;
typedef CGAL::Polyhedron_3<Kernel>         Polyhedron;
typedef Polyhedron::Vertex_iterator        Vertex_iterator;

int main(void) {
    // 公共点
    Point_3 p( 1.0, 0.0, 0.0 );
    Point_3 q( 0.0, 1.0, 0.0 );
    Point_3 s( 0.0, 0.0, 0.0 );

    // 另外两个顶点
    Point_3 r( 0.0, 0.0, 1.0 );
    Point_3 d( 0.0, 0.0,-1.0 );

    Polyhedron P;
    P.make_tetrahedron( p, q, r, s );
    P.make_tetrahedron( p, q, s, d );

    CGAL::IO::set_ascii_mode( std::cout );
    
    // 打印所有顶点
    for ( Vertex_iterator v = P.vertices_begin(); v != P.vertices_end(); ++v )
        std::cout << v->point() << std::endl;

    return 0;
}

期望输出 #

我预期得到5个不重复的顶点：

1 0 0
0 1 0
0 0 1
0 0 0
0 0 -1

实际输出 #

运行后得到的结果存在重复顶点：

1 0 0
0 1 0
0 0 1
0 0 0
1 0 0
0 1 0
0 0 0
0 0 -1

问题 #

调用make_tetrahedron函数时，能否实现CGAL::Polyhedron_3中同一个坐标点仅作为一个顶点存储？

解答 #

make_tetrahedron默认没有自动去重逻辑，每次传入Point_3调用时都会独立插入4个全新顶点、构建对应的四面体拓扑，不会主动比对现有顶点的坐标来复用实例，因此会出现重复存储的问题。可以通过以下两种方案实现同坐标顶点仅存一份：

方案1：手动复用顶点句柄 #

make_tetrahedron支持传入Vertex_handle类型参数而非Point_3，你可以先把所有唯一顶点插入多面体拿到对应句柄，再用句柄构建四面体，不会生成新的重复顶点，修改后的示例代码如下：

int main(void) {
    Point_3 p( 1.0, 0.0, 0.0 );
    Point_3 q( 0.0, 1.0, 0.0 );
    Point_3 s( 0.0, 0.0, 0.0 );
    Point_3 r( 0.0, 0.0, 1.0 );
    Point_3 d( 0.0, 0.0,-1.0 );

    Polyhedron P;
    // 先插入所有唯一顶点，拿到对应句柄
    auto v_p = P.make_vertex(p);
    auto v_q = P.make_vertex(q);
    auto v_s = P.make_vertex(s);
    auto v_r = P.make_vertex(r);
    auto v_d = P.make_vertex(d);
    // 用顶点句柄构建四面体，不会生成新顶点
    P.make_tetrahedron(v_p, v_q, v_r, v_s);
    P.make_tetrahedron(v_p, v_q, v_s, v_d);

    CGAL::IO::set_ascii_mode( std::cout );
    for ( Vertex_iterator v = P.vertices_begin(); v != P.vertices_end(); ++v )
        std::cout << v->point() << std::endl;
    return 0;
}

方案2：全局批量去重 #

如果你已经用Point_3参数调用make_tetrahedron生成了带重复顶点的多面体，可以调用CGAL的拓扑处理工具做全局顶点合并：使用CGAL::Polygon_mesh_processing::merge_duplicate_vertices函数，指定坐标容差即可把坐标一致的顶点合并为同一个实例。

内容的提问来源于stack exchange，提问作者Davide