# BezierIntersection

**Repository Path**: april0220/bezier-intersection

## Basic Information

- **Project Name**: BezierIntersection
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-12-13
- **Last Updated**: 2023-12-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 三维空间内贝塞尔曲线求交

## 1. 两条线段求交

算法简述：用参数方程表示线段$P_a$和$P_b$，联立方程解出$u_a$和$u_b$，从而判断两条线段是否XOY平面相交，若在XOY平面相交且满足$z = z1 + u_a (z2 - z1)$，则两线段在3D空间相交，返回这个交点。
$$
P_a = P1 + u_a ( P2 - P1 )\\
P_b = P3 + u_b ( P4 - P3 )
$$
如果线段重合，在空间中有多个交点，本算法只返回其中任一个交点。

## 2. 两条二次贝塞尔曲线求交

算法简述：求两条曲线的包围盒，若不相交则返回false；若相交则二分两条曲线，并递归的判断四条子曲线是否相交，直到两条曲线的中点距离小于给定阈值为止，返回交点。对于返回的交点集和，距离小于给定阈值的算作同一个交点。

## 3. 空间加速思路

1. 缩小空间范围。对空间中的曲线包围盒构建BVH树，排除和目标曲线包围盒无交集的曲线包围盒。
2. 缩小曲线包围盒。若AABB包围盒相交，先判断由三个控制点组成的三角形是否相交，若相交再继续递归求解。
3. 优化求解算法。改为基于论文Curve intersection using Bézier clipping 的算法，基于"Fat-line"更快的使交点求解收敛。