如何使用CGAL计算两个三角化曲面网格间的距离？

核心解决方案：基于AABB树的最近点对计算 #

CGAL中可以通过AABB树结合最近点查询来高效计算两个三角化曲面网格的最小欧氏距离，这是最直接且高效的方案，步骤如下：

1. 预处理与AABB树构建 #

首先确保两个网格均为三角化结构（若存在非三角面，先调用三角化工具处理），再为每个网格的三角面片构建AABB树：

#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;
typedef Kernel::Triangle_3 Triangle;
typedef CGAL::Surface_mesh<Point> Mesh;
typedef std::vector<Triangle>::iterator TriIter;
typedef CGAL::AABB_traits<Kernel, TriIter> AABBTraits;
typedef CGAL::AABB_tree<AABBTraits> AABBTree;

// 提取网格的所有三角面片
std::vector<Triangle> extract_triangles(const Mesh& mesh) {
    std::vector<Triangle> tris;
    for (auto f : faces(mesh)) {
        std::vector<Point> pts;
        for (auto v : vertices_around_face(halfedge(f, mesh), mesh)) {
            pts.push_back(mesh.point(v));
        }
        tris.emplace_back(pts[0], pts[1], pts[2]);
    }
    return tris;
}

// 构建AABB树
AABBTree build_aabb_tree(const std::vector<Triangle>& tris) {
    return AABBTree(tris.begin(), tris.end());
}

2. 计算两个网格的最小距离 #

利用CGAL的closest_points函数，传入两个AABB树即可获取最近点对，进而计算距离：

#include <CGAL/closest_points_3.h>
#include <iostream>

int main() {
    Mesh mesh1, mesh2;
    // 假设已完成两个网格的加载

    // 三角化非三角面（若需要）
    CGAL::Polygon_mesh_processing::triangulate_faces(mesh1);
    CGAL::Polygon_mesh_processing::triangulate_faces(mesh2);

    auto tris1 = extract_triangles(mesh1);
    auto tris2 = extract_triangles(mesh2);

    AABBTree tree1 = build_aabb_tree(tris1);
    AABBTree tree2 = build_aabb_tree(tris2);

    // 获取两个曲面的最近点对
    Point p_on_mesh1, p_on_mesh2;
    CGAL::closest_points(tree1, tree2, p_on_mesh1, p_on_mesh2);

    // 计算距离（平方距离避免开方，若需实际距离再取平方根）
    Kernel::FT squared_dist = CGAL::squared_distance(p_on_mesh1, p_on_mesh2);
    std::cout << "最小距离平方值：" << squared_dist << std::endl;
    std::cout << "最小距离：" << std::sqrt(squared_dist) << std::endl;

    return 0;
}

额外说明 #

• 若需要计算豪斯多夫距离（双向最大最小距离），可使用CGAL的CGAL::Polygon_mesh_processing::hausdorff_distance()函数，需确保输入网格为三角化结构。
• 选择Kernel时，Exact_predicates_inexact_constructions_kernel适合多数场景，高精度需求可改用Exact_predicates_exact_constructions_kernel。

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