203 lines
7.4 KiB
C++
203 lines
7.4 KiB
C++
|
#pragma once
|
|||
|
|
/**
|
|||
|
|
* @file advanced_intersection.h
|
|||
|
|
* @brief 高级曲面求交 — 鲁棒 SSI(三阶段)、曲线-曲面求交、自交检测
|
|||
|
|
*
|
|||
|
|
* 对标 CGM 的工业级曲面求交算法，提供：
|
|||
|
|
* - 鲁棒曲面-曲面求交（三阶段：AABB细分→Newton精化→奇异点处理）
|
|||
|
|
* - 曲线-曲面求交
|
|||
|
|
* - 曲面自交检测
|
|||
|
|
*
|
|||
|
|
* @ingroup curves
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
#include "vde/curves/nurbs_curve.h"
|
|||
|
|
#include "vde/curves/nurbs_surface.h"
|
|||
|
|
#include "vde/core/point.h"
|
|||
|
|
#include "vde/core/aabb.h"
|
|||
|
|
#include <vector>
|
|||
|
|
#include <array>
|
|||
|
|
#include <utility>
|
|||
|
|
#include <functional>
|
|||
|
|
#include <limits>
|
|||
|
|
|
|||
|
|
namespace vde::curves {
|
|||
|
|
|
|||
|
|
using core::Point3D;
|
|||
|
|
using core::Vector3D;
|
|||
|
|
using core::AABB3D;
|
|||
|
|
|
|||
|
|
// ═══════════════════════════════════════════════════════════
|
|||
|
|
// Robust SSI — 鲁棒曲面-曲面求交
|
|||
|
|
// ═══════════════════════════════════════════════════════════
|
|||
|
|
|
|||
|
|
/// SSI 交线段（参数空间）
|
|||
|
|
struct SSISegment {
|
|||
|
|
/// 曲面 A 上的参数点 (u,v)
|
|||
|
|
std::vector<std::pair<double, double>> params_a;
|
|||
|
|
/// 曲面 B 上的参数点 (u,v)
|
|||
|
|
std::vector<std::pair<double, double>> params_b;
|
|||
|
|
/// 3D 空间点
|
|||
|
|
std::vector<Point3D> points;
|
|||
|
|
/// 是否为奇异交线（切线接触、重叠等）
|
|||
|
|
bool is_singular = false;
|
|||
|
|
/// 奇异类型描述
|
|||
|
|
std::string singularity_type;
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
/// SSI 选项
|
|||
|
|
struct SSIOptions {
|
|||
|
|
/// 阶段1：AABB 细分参数
|
|||
|
|
int max_subdivision_depth = 8; ///< 最大细分深度
|
|||
|
|
double subdivision_tolerance = 1e-3; ///< 细分终止容差
|
|||
|
|
int min_patch_samples = 4; ///< 每子面片最少采样点
|
|||
|
|
|
|||
|
|
/// 阶段2：Newton 精化参数
|
|||
|
|
double newton_tolerance = 1e-12; ///< Newton 收敛容差
|
|||
|
|
int max_newton_iter = 30; ///< Newton 最大迭代次数
|
|||
|
|
double step_damping = 0.5; ///< 步长阻尼因子
|
|||
|
|
|
|||
|
|
/// 阶段3：奇异点检测参数
|
|||
|
|
double singular_condition_threshold = 1e-8; ///< 条件数阈值（小于此值判为奇异）
|
|||
|
|
double tangent_contact_angle_tol = 0.01; ///< 切线接触角度容差（弧度）
|
|||
|
|
bool detect_overlap = true; ///< 是否检测重叠面
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
/// SSI 完整结果
|
|||
|
|
struct SSIResult {
|
|||
|
|
/// 交线段列表
|
|||
|
|
std::vector<SSISegment> segments;
|
|||
|
|
/// 阶段统计
|
|||
|
|
int phase1_subdivisions = 0; ///< 细分次数
|
|||
|
|
int phase1_candidates = 0; ///< 候选种子数
|
|||
|
|
int phase2_converged = 0; ///< Newton 收敛数
|
|||
|
|
int phase2_diverged = 0; ///< Newton 发散数
|
|||
|
|
int phase3_singularities = 0; ///< 检测到的奇异点数
|
|||
|
|
double total_time_ms = 0.0; ///< 总耗时（毫秒）
|
|||
|
|
bool success = false; ///< 是否成功完成
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
/**
|
|||
|
|
* @brief 鲁棒曲面-曲面求交（三阶段）
|
|||
|
|
*
|
|||
|
|
* **阶段1：边界盒预筛选 + 自适应细分**
|
|||
|
|
* - 计算两曲面 AABB 盒，快速排除不相交区域
|
|||
|
|
* - 在参数域自适应四叉树细分，定位交线种子点
|
|||
|
|
* - 使用区间算术评估曲面片相交性
|
|||
|
|
*
|
|||
|
|
* **阶段2：Newton-Raphson 精化**
|
|||
|
|
* - 从种子点启动 Newton 迭代求解 F(u1,v1,u2,v2)=0
|
|||
|
|
* - 收敛到 1e-12 高精度
|
|||
|
|
* - 沿交线追踪（marching）生成连续交线段
|
|||
|
|
*
|
|||
|
|
* **阶段3：奇异点检测 + 特殊处理**
|
|||
|
|
* - Jacobian 条件数检测：识别切线接触、高阶接触
|
|||
|
|
* - 奇异点处使用 subdivision + 约束优化
|
|||
|
|
* - 重叠面使用采样投票 + 特征值分析
|
|||
|
|
*
|
|||
|
|
* @param surf_a 曲面 A
|
|||
|
|
* @param surf_b 曲面 B
|
|||
|
|
* @param options SSI 选项
|
|||
|
|
* @return 交线结果（含阶段统计）
|
|||
|
|
*
|
|||
|
|
* @note 对标 CGM Robust SSI / ACIS intersector
|
|||
|
|
* @ingroup curves
|
|||
|
|
*/
|
|||
|
|
[[nodiscard]] SSIResult robust_ssi(
|
|||
|
|
const NurbsSurface& surf_a,
|
|||
|
|
const NurbsSurface& surf_b,
|
|||
|
|
const SSIOptions& options = {});
|
|||
|
|
|
|||
|
|
// ═══════════════════════════════════════════════════════════
|
|||
|
|
// Curve-Surface Intersection — 曲线-曲面求交
|
|||
|
|
// ═══════════════════════════════════════════════════════════
|
|||
|
|
|
|||
|
|
/// 曲线-曲面交点
|
|||
|
|
struct CSIntersectionPoint {
|
|||
|
|
double t; ///< 曲线上的参数
|
|||
|
|
double u, v; ///< 曲面上的参数 (u,v)
|
|||
|
|
Point3D position; ///< 3D 交点坐标
|
|||
|
|
double distance; ///< 交点处曲线到曲面的距离
|
|||
|
|
bool tangent_contact = false; ///< 是否为切线接触
|
|||
|
|
int multiplicity = 1; ///< 交点重数
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
/**
|
|||
|
|
* @brief 曲线-曲面求交
|
|||
|
|
*
|
|||
|
|
* 计算 NURBS 曲线与 NURBS 曲面的所有交点。
|
|||
|
|
* 算法：
|
|||
|
|
* 1. 将曲线离散为线性段，建立曲线 AABB 加速结构
|
|||
|
|
* 2. 在曲面参数域使用细分 + Newton 精化
|
|||
|
|
* 3. 对切线接触情况使用更高阶方法
|
|||
|
|
*
|
|||
|
|
* @param curve NURBS 曲线
|
|||
|
|
* @param surf NURBS 曲面
|
|||
|
|
* @param tolerance 收敛容差（默认 1e-10）
|
|||
|
|
* @return 交点列表（按曲线参数 t 排序）
|
|||
|
|
*
|
|||
|
|
* @note 对标 CGM Curve-Surface Intersection
|
|||
|
|
* @ingroup curves
|
|||
|
|
*/
|
|||
|
|
[[nodiscard]] std::vector<CSIntersectionPoint> curve_surface_intersection(
|
|||
|
|
const NurbsCurve& curve,
|
|||
|
|
const NurbsSurface& surf,
|
|||
|
|
double tolerance = 1e-10);
|
|||
|
|
|
|||
|
|
// ═══════════════════════════════════════════════════════════
|
|||
|
|
// Self-Intersection Detection — 自交检测
|
|||
|
|
// ═══════════════════════════════════════════════════════════
|
|||
|
|
|
|||
|
|
/// 自交区域
|
|||
|
|
struct SelfIntersectionRegion {
|
|||
|
|
/// 参数空间中检测到自交的子区域范围
|
|||
|
|
double u_min, u_max, v_min, v_max;
|
|||
|
|
/// 自交类型
|
|||
|
|
enum Type {
|
|||
|
|
NONE = 0,
|
|||
|
|
EDGE_OVERLAP = 1, ///< 边界重叠
|
|||
|
|
INTERIOR_CROSS = 2, ///< 内部交叉
|
|||
|
|
TANGENT_CONTACT = 3, ///< 切线接触
|
|||
|
|
LOCAL_LOOP = 4 ///< 局部环
|
|||
|
|
};
|
|||
|
|
Type type = NONE;
|
|||
|
|
/// 3D 空间中最近交点
|
|||
|
|
Point3D closest_intersection;
|
|||
|
|
double min_distance = std::numeric_limits<double>::max();
|
|||
|
|
/// 曲面上最近自交处的法线夹角
|
|||
|
|
double normal_angle_deg = 0.0;
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
/// 自交检测结果
|
|||
|
|
struct SelfIntersectionResult {
|
|||
|
|
bool has_self_intersection = false;
|
|||
|
|
std::vector<SelfIntersectionRegion> regions;
|
|||
|
|
double global_min_distance = std::numeric_limits<double>::max();
|
|||
|
|
int total_checks = 0;
|
|||
|
|
int intersecting_pairs = 0;
|
|||
|
|
double detection_time_ms = 0.0;
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
/**
|
|||
|
|
* @brief 曲面自交检测
|
|||
|
|
*
|
|||
|
|
* 检测 NURBS 曲面是否自交（不同参数值映射到同一点/相近点）。
|
|||
|
|
* 算法：
|
|||
|
|
* 1. 对曲面参数域构建 BVH 加速结构
|
|||
|
|
* 2. 对每对不相邻的 BVH 节点，检测是否在 3D 空间相交
|
|||
|
|
* 3. 对疑似自交区域进行 Newton 精化确认
|
|||
|
|
* 4. 分类自交类型（交叉、重叠、切线接触、局部环）
|
|||
|
|
*
|
|||
|
|
* @param surface NURBS 曲面
|
|||
|
|
* @param tolerance 自交检测容差（3D 空间距离，默认 1e-8）
|
|||
|
|
* @return 自交检测结果
|
|||
|
|
*
|
|||
|
|
* @note 对标 CGM Self-Intersection Check / ACIS self-intersect
|
|||
|
|
* @ingroup curves
|
|||
|
|
*/
|
|||
|
|
[[nodiscard]] SelfIntersectionResult self_intersection_detection(
|
|||
|
|
const NurbsSurface& surface,
|
|||
|
|
double tolerance = 1e-8);
|
|||
|
|
|
|||
|
|
} // namespace vde::curves
|