Affine Arithmetic-Based B-Spline Surface Intersection with GPU Acceleration 阅读

发表期刊：TVCG 2014
团队：浙江大学 CAD&CG 团队

基于仿射算术的 B-Spline 曲面相交算法的 GPU 加速。

主要贡献：

1. 使用仿射算术计算 B-Spline 基函数;
2. 使用GPU加速曲面相交算法；
3. 对可能相交的带状区域进行快速细化。

文章思路

1. 对参数域进行给定分辨率的分块（给定分辨率与GPU cuda核数量相关，分块不依赖节点插入，只是给出结向量的double上下界）

2. 对每个分块进行 AA 计算，得到 AABB 与 BVH （GPU进行）

3. 对 AABB 与 BVH 进行相交检测，得到可能相交的区域 （CPU进行）

4. 对可能相交的区域进行步骤 1-3 的迭代，直到满足参数域上的精度要求（精度由预先给定的 tree depth 决定）

5. 带状区域细化： 对每个区域计算四个角点，计算角点的AABB（这一步会存在误差）

6. 计算角点位置： 对 AABB 相交的区域，采两个参数域的质心，分别计算对应三维空间的点，取这两个点的中点作为交点。

7. 提升交点精度： 取三个平面的点作为优化后的交点。以 表示曲面1上的区域质心的三维坐标，以 表示曲面2上的区域质心的三维坐标，以 表示 。这三个平面分别是： 与 的切平面； 与 确定的平面。

8. 从一个相交区域出发，向四周遍历，直到延伸到两端无相交区域，或当前带状区域的最长边的长度大于相交带状区域的局部宽度。这部分工作需要进一步阅读引用参考文献。 TO BE CONTINUED…

缺点

1. 第 5 步存在误差，可能遗漏交点；

2. AA 难以用于 NURBS 曲面，精度扩散严重；

3. AA 是否真的比用控制点算 AABB 性价比更高？

概念

Interval arithmetic (IA) 与 Affine arithmetic (AA)

IA 与 AA 是两种区间算术，都应用在了 SSI 中，思路都是通过不断细分参数空间，用以提升计算稳定性。仿射算术可以被看作是区间算术的一种扩展。当仿射函数中的线性项为零时，仿射算术可以退化为区间算术。

根据文章所述，对于相同的区间输入，AA 方法计算结果更加紧凑。但 AA 方法的计算量大，计算得到的结果是带状区域而不是曲线。

笔者本人理解 IA 与 AA 没有本质区别。可能只是表示方法的差异，导致数值计算精度 AA 更准确。

交线计算精度 relative root mean square (RMS) error

交线计算精度是通过计算相交曲线与真实曲线的 RMS 误差来衡量的。误差越小，计算精度越高。

RMS 误差的计算公式为：

其中 与 分别是第 i 个点到曲面 P 与 Q 的距离， 是两个曲面 AABB 的对角线长度。