茂之钳
43 lines
1.2 KiB
C++
43 lines
1.2 KiB
C++
#pragma once
|
|
#include "vde/core/point.h"
|
|
#include <vector>
|
|
#include <array>
|
|
|
|
namespace vde::mesh {
|
|
using core::Point2D;
|
|
using core::Point3D;
|
|
using core::Vector3D;
|
|
|
|
/**
|
|
* @brief 四面体网格结构
|
|
* @ingroup mesh
|
|
*/
|
|
struct TetrahedronMesh {
|
|
std::vector<Point3D> vertices; ///< 顶点坐标
|
|
std::vector<std::array<int, 4>> tetrahedra; ///< 四面体索引，每个 {i0,i1,i2,i3}
|
|
};
|
|
|
|
/**
|
|
* @brief 3D Delaunay 四面体化（Bowyer-Watson 增量算法）
|
|
*
|
|
* 将 3D 点集剖分为 Delaunay 四面体网格：任意四面体的外接球内不含其他顶点。
|
|
* 算法是 2D 版本的自然推广：
|
|
* 1. 构建超级四面体包含所有点
|
|
* 2. 逐点插入：删除外接球包含新点的四面体 → 空洞 → 重连
|
|
* 3. 去除超级四面体相关单元
|
|
*
|
|
* @param points 输入 3D 点集（至少 4 个不共面点）
|
|
* @return TetrahedronMesh 四面体网格
|
|
*
|
|
* @note 时间复杂度与 2D 类似：平均 O(n log n)，最坏 O(n²)
|
|
* @note 输出包括内部和边界四面体；通过 alpha_shapes 可提取表面
|
|
* @code{.cpp}
|
|
* auto tet_mesh = delaunay_3d(point_cloud);
|
|
* @endcode
|
|
* @see alpha_shapes
|
|
* @ingroup mesh
|
|
*/
|
|
TetrahedronMesh delaunay_3d(const std::vector<Point3D>& points);
|
|
|
|
} // namespace vde::mesh
|