高效线段-三角形相交：万级几何体可见顶点筛选优化方案问询

需求背景 #

我有一组构成任意几何体的三角形（从OFF文件读取），每个三角形由三个3D顶点定义。现有一个观测点，需要移除几何体中所有不可见顶点——即连接观测点与该顶点的线段不与任何三角形相交的顶点。

当前问题：

• 单个对象的顶点与三角形数量均为10^4量级；
• 已实现的带符号体积方案包含两层嵌套循环，虽在首次相交时终止，但仍需调用带符号体积函数达1.92亿次，效率极低；
• 如Möller和Trumbore在1997年《图形工具期刊》发表的《快速、低存储量的光线-三角形相交检测》这类高效算法，因假设为无限直线而非线段，会误删与更远三角形相交的可见顶点，无法直接使用。

优化方案 #

1. 空间划分：用BVH减少检测次数 #

对所有三角形预构建包围盒层次结构（BVH）：

• 将三角形按空间位置分组，构建树状结构，每个节点对应一组三角形的最小包围盒；
• 检测线段（观测点→顶点）与三角形相交时，先遍历BVH：若节点包围盒与线段不相交，直接跳过该节点下的所有三角形；仅对相交的节点继续递归检测；
• 针对10^{4量级的三角形，BVH构建时间可忽略，每个线段的检测次数能从平均10}4次降至几十次以内，大幅减少计算量。

2. 适配线段的高效相交检测 #

基于Möller-Trumbore算法修改，适配线段而非无限光线：

• 原算法计算光线与三角形交点的参数t，需新增两个关键判断：
  • t ∈ [0, 1]：确保交点落在观测点到目标顶点的线段范围内；
  • 交点的重心坐标u ≥ 0、v ≥ 0、u + v ≤ 1：确保交点在三角形内部；
• 前置过滤优化：
  • 先计算线段的包围盒，跳过与线段包围盒无重叠的三角形；
  • 通过带符号体积快速判断观测点和目标顶点是否在三角形同侧，同侧则直接排除该三角形，无需完整计算相交。

3. 批量剔除无效三角形 #

• 预计算每个三角形相对于观测点的朝向：计算三角形法向量与“观测点到三角形中心”向量的点积，若点积为负（三角形背向观测点），则该三角形不可能遮挡任何顶点，直接从检测集合中剔除，减少后续检测量。

4. 并行化处理 #

每个顶点的可见性检测独立，可通过并行计算进一步提速：

• CPU端：用OpenMP对顶点循环做并行化，注意BVH的线程安全访问；
• GPU端：将三角形、顶点数据上传至GPU，用CUDA或Shader实现批量线段-三角形相交检测，适合处理10^4量级的顶点规模。

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