【CAD/CG笔记】Bezier交Bezier预备知识
Bezier交Bezier实现_预备知识
线段求交
要计算两条线段的交点，我们首先需要确定这两条线段是否相交。线段可以由两个端点定义，设线段AB的端点为$A(x_1, y_1)$和$B(x_2, y_2)$，线段CD的端点为$C(x_3, y_3)$和$D(x_4, y_4)$。
推导如下，
- 确定线段的方程：线段$AB$和$CD$可以表示为参数方程：
$$
AB : \begin{cases}
x = x_1 + t(x_2 - x_1) \
y = y_1 + t(y_2 - y_1)
\end{cases} \quad (0 \leq t \leq 1)
$$
$$
CD : \begin{cases}
x = x_3 + s(x_4 - x_3) \
y = y_3 + s(y_4 - y_3)
\end{cases} \quad (0 \leq s \leq 1)
$$
- 设置交点条件：如果线段相交，那么存在t和s使得：
$$
x_1 + t(x_2 - x_1) = x_3 + s(x_4 - x_3)
$$
$$
y_1 + t(y_2 - y_1) = y_3 + s(y_4 - y_3)
$$
- 解方程组：解这个方程得到t和s。
$$
t = \frac{(x_3 - x_1)(y_4 - y_3) - (y_3 - y_1)(x_4 - x_3)}{(x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3)}
$$
$$
s = \frac{(x_3 - x_1)(y_2 - y_1) - (y_3 - y_1)(x_2 - x_1)}{(x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3)}
$$
如果t和s都在[0,1]区间内，那么线段相交。
- 计算交点：交点的坐标为：
$$
P(x_1 + t(x_2 - x_1), y_1 + t(y_2 - y_1))
$$
N条线段求交的扫描线算法
N条线段求交的扫描线算法_线段相交 扫描线算法-CSDN博客
牛顿迭代法
牛顿迭代法又称为牛顿-拉弗森方法。
一、单变量牛顿迭代公式
设$r$ 是 $f(x)=0$ 的根，选取 $x_0$ 作为 $r$ 的初始近似值，过点 $(x_0,f(x_0))$ 做曲线 $y=f(x)$ 的切线 $L$，
$$
L: y=f(x_0)+f’(x_0)(x-x_0)
$$
则 $L$ 与 $x$ 轴交点的横坐标 $x_1=x_0-\frac{f(x_0)}{f’(x_0)}$，称 $x_1$ 为 $r$ 的一次近似值。过点 $(x_1,f(x_1))$ 做曲线 $y=f(x)$ 的切线，并求该切线与$x$轴交点的横坐标 $x_2=x_1-\frac{f(x_1)}{f’(x_1)}$，称 $x_2$ 为的二次近似值。重复以上过程，得 $r$ 的近似值序列，其中，$x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}$ 称为 $r$ 的 $n+1$ 次近似值，上式称为牛顿迭代公式。
用牛顿迭代法解非线性方程，是把非线性方程 $f(x)=0$ 线性化的一种近似方法。把 $f(x)$ 在点 $x_0$ 的某邻域内展开成泰勒级数
$$
f(x)=f(x_0)+f’(x_0)(x-x_0)+\frac{f’’(x_0)(x-x_0)^2}{2!}+\cdots+\frac{f^{(n)}(x_0)(x-x_0)^n}{n!}+R_n(x)
$$
取其线性部分（即泰勒展开的前两项），并令其等于0，即
$$
f(x_0)+f’(x_0)(x-x_0)=0
$$
以此作为非线性方程 $f(x)=0$ 的近似方程，若 $f’(x_0)\neq 0$，则其解为 $x_1=x_0-\frac{f(x_0)}{f’(x_0)}$，这样，得到牛顿迭代法的一个迭代关系式：
$$
x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}
$$
已经证明，如果是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。并且，如果不为0，那么牛顿法将具有平方收敛的性能。粗略的说，这意味着每迭代一次，牛顿法的有效数字将增加一倍。
一、单变量牛顿迭代基本思想与迭代公式
通常对已知方程$f(x)=0$进行变形而构造的迭代函数$\varphi(x)$不是惟一的。在实际作用中，如果希望迭代函数$\varphi(x)$有一种固定格式的构造方法，就可以采用Newton迭代法。
Newton迭代法的基本思想是：设法将一个非线性方程$f(x)=0$转化为某种线性方程求解，其解决问题的基础是Taylor（泰勒）多项式$\mathcal{Q}$。具体描述如下：
设$f(x)=0$的近似根为$x_k$，则函数$f(x)$在点$x_k$附近可用一阶Taylor多项式$p_1(x)$来近似，即：
$$
p(x)=f(x_k)+f’(x_k)(x-x_k)\cong f(x)
$$
从而得到线性方程：
$$
f(x_k)+f’(x_k)(x-x_k)=0
$$
解之，得该线性方程的根$x$，但它是$f(x)=0$的一个新近似根，记做$x_{k+1}$，即：
$$
x_{k+1}=x_k-\frac{f(x_k)}{f’(x_k)}
$$
上式实质上就是一种迭代格式，称为Newton迭代格式。相应地，Newton迭代函数为：
$$
\varphi(x)=x-\frac{f(x)}{f’(x)}
$$
于是，按（1）式构造迭代函数解方程$f(x)=0$的方法，就是Newton迭代法。
Newton迭代法的几何解释如下图所示。方程$f(x)=0$的根$x_{0}$为$y=f(x)$和$y=0$（即x轴）的交点。设$x_k$为$x_{0}$的某个初始近似值，过$p_k$点$(x_k, f(x_k))$作$y=f(x)$的切线交x轴于$x_{k+1}$，即为所获得的近似值。继续过$p_{k+1}$点$(x_{k+1}, f(x_{k+1}))$，$p_{k+2}$点$(x_{k+2}, f(x_{k+2})),\cdots$，作$y=f(x)$的切线，即可逐步逼近精确的根$x_{0}$。因此，Newton法也叫切线法，因为它是沿着曲线$y=f(x)$上某一点作切线逐步外推逼近的。从$p_k$点作切线与x轴的交点$x_{k+1}$，由于$y=f(x)$不是直线，所以$f(x_{k+1})$就不可能为零。因此必须以$x_{k+1}$作为新的起点，从与之对应的$p_{k+1}$点继续作切线，重复上述步骤，直至$f(x_{k+1})$充分小，逼近零时为止。
二、多变量牛顿迭代公式
梯度算子的定义
梯度算子$ \nabla$是一个向量微分算子，定义为
$$
\nabla = \left( \frac{\partial}{\partial x}, \frac{\partial}{\partial y}, \frac{\partial}{\partial z} \right)
$$
其中：
- $ \frac{\partial}{\partial x} $、$\frac{\partial}{\partial y} $、$\frac{\partial}{\partial z} $ 分别是关于 $x $、$ y $、$ z $ 的偏导数。
- 梯度算子可以作用在标量函数或向量函数上。
梯度算子的作用
梯度算子$ \nabla$可以用于计算以下内容：
(1) 梯度（Gradient）
当 $ \nabla $ 作用在标量函数$ f(x, y, z) $上时，结果是函数的梯度：
$$
\nabla f = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z} \right)
$$
梯度是一个向量，表示函数在某一点处的最大变化率和方向。
(2) 散度（Divergence）
当 $ \nabla $ 与向量函数 $\mathbf{F} = (F_x, F_y, F_z) $ 点乘时，结果是散度：
$$
\nabla \cdot \mathbf{F} = \frac{\partial F_x}{\partial x} + \frac{\partial F_y}{\partial y} + \frac{\partial F_z}{\partial z}
$$
散度是一个标量，表示向量场的“源”或“汇”的强度。
泰勒公式与Jacobian矩阵、Hessian矩阵
将$f(x)$ 用泰勒公式展开为二阶，如下：
$$
f(x)=f(x_0)+f’(x_0)(x-x_0)+\frac12{f’’(x_0)(x-x_0)^2}+R_n(x)
$$
针对于多变量来说，这里的一阶导数就是Jacobian矩阵，二阶导数就是Hessian矩阵。
根据高等数学知识，若一元函数 $f(x)$ 在 $x = x^{(0)}$ 点某个领域内具有任意阶导数，则 $f(x)$ 在 $x^{(0)}$ 处的泰勒展开式为
$$
f(x)=f\left(x^{(0)}\right)+f^{\prime}\left(x^{(0)}\right)\Delta x+\frac{1}{2}f^{\prime\prime}\left(x^{(0)}\right)(\Delta x)^2+\ldots
$$
其中 $\Delta x=x-x^{(0)},\Delta x^2=\left(x-x^{(0)}\right)^2$ 对于二元函数 $f\left(x_1, x_2\right)$ 在 $X^{(0)}\left(x_1^{(0)}, x_2^{(0)}\right)$ 点处的泰勒展开式为：
其中 $\Delta x_1=x_1-x_1^{(0)},\Delta x_2=x_2-x_2^{(0)}$
将上述展开式写成矩阵形式，则有：
即：
$$
f(X)=f\left(X^{(0)}\right)+\Delta f\left(X^{(0)}\right)^{T}\Delta X+\frac{1}{2}\Delta X^{T}G\left(X^{(0)}\right)\Delta X+…
$$
其中
$$
G\left(X^{(0)}\right)=\left(\left.\begin{array}{cc}\frac{\partial^2 f}{\partial x_1^2}&\frac{\partial^2 f}{\partial x_1\partial x_2}\ \frac{\partial^2 f}{\partial x_2\partial x_1}&\frac{\partial^2 f}{\partial x_2^2}\end{array}\right)\right|_{X^{(0)}},\Delta X=\left(\begin{array}{c}\Delta x_1\ \Delta x_2\end{array}\right)
$$
$G\left(X^{(0)}\right)$ 是 $f\left(x_1, x_2\right)$ 在 $X^{(0)}$ 处的黑塞矩阵。它是由函数 $f\left((x_1, x_2\right))$ 在 $X^{(0)}.$ 处的二阶偏导数所组成的方阵
多元函数的黑塞矩阵
将二元函数的泰勒展开式推广到多元函数，则 $f\left(x_1, x_2,\ldots, x_n\right)$ 在 $X^{(0)}$ 点处的泰勒展开式的矩阵形式为：
$$
f(X)=f\left(X^{(0)}\right)+\Delta f\left(X^{(0)}\right)^{T}\Delta X+\frac{1}{2}\Delta X^{T}G\left(X^{(0)}\right)\Delta X+\ldots
$$
其中：
(1) $\Delta f(X^{(0)}) = \left[ \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, …, \frac{\partial f}{\partial x_n} \right]^T_{X^{(0)}}$ ，他是 $f(x)$ 在 $X^{(0)}$ 点处的梯度
(2) $G(X^{(0)}) = \left(\begin{array}{cccc}\frac{\partial^2 f}{\partial x_1^2}&\frac{\partial^2 f}{\partial x_1\partial x_2}&\cdots&\frac{\partial^2 f}{\partial x_1\partial x_n}\\frac{\partial^2 f}{\partial x_2\partial x_1}&\frac{\partial^2 f}{\partial x_2^2}&\cdots&\frac{\partial^2 f}{\partial x_2\partial x_n}\\vdots&\vdots&\ddots&\vdots\\frac{\partial^2 f}{\partial x_n\partial x_1}&\frac{\partial^2 f}{\partial x_n\partial x_2}&\cdots&\frac{\partial^2 f}{\partial x_n^2}\end{array}\right)_{X^{(0)}}$ 为函数 $f(X)$ 在 $X^{(0)}$ 点处的黑塞矩阵。
黑塞矩阵是由目标函数 $f$ 在点 $X$ 处的二阶偏导数组成的 $n \times n$ 阶对称矩阵。
参考博客一：雅可比与泰勒公式的关系 - 知乎
参考博客二：泰勒展开与黑塞矩阵(Hessian Matrix)_泰勒展开式用矩阵表示-CSDN博客
参考博客三：多元函数的泰勒展开式 - 知乎
Jacobian矩阵
假设函数$F: R^n \rightarrow R^m$ 是一个将欧氏$n$维空间映射到欧氏$m$维空间的函数，该函数由$m$个实函数构成：
$y_1(x_1,\ldots,x_n),y_2(x_1,\ldots,x_n),\ldots,y_m(x_1,\ldots,x_n)$。这些函数的偏导数$^*$组成一个$m$行$n$列的矩阵，即Jacobian矩阵：
$$
J_F(x_1,\ldots,x_n) = \begin{bmatrix}
\frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_n} \
\vdots & \ddots & \vdots \
\frac{\partial y_m}{\partial x_1} & \cdots & \frac{\partial y_m}{\partial x_n}
\end{bmatrix}
$$
也可以表示为$\frac{\partial(y_1,\cdots,y_m)}{\partial(x_1,\cdots,x_n)}$。
如果$p$是$R^n$中的一个点，函数$F$在$p$点可微，则$F$在这一点的导数由$J_F(p)$给出。
如果$m=n$，则$J_F(x_1,\cdots,x_n)$是一个方块阵，取其行列式为Jacobian行列式。
Hessian矩阵
如果$F$的所有二阶导数都存在，则$F$的Hessian矩阵为：
$$
H(F)(x) = \begin{bmatrix}
\frac{\partial^2 F}{\partial x_1^2} & \frac{\partial^2 F}{\partial x_1\partial x_2} & \cdots & \frac{\partial^2 F}{\partial x_1\partial x_n} \
\frac{\partial^2 F}{\partial x_2\partial x_1} & \frac{\partial^2 F}{\partial x_2^2} & \cdots & \frac{\partial^2 F}{\partial x_2\partial x_n} \
\vdots & \vdots & \ddots & \vdots \
\frac{\partial^2 F}{\partial x_n\partial x_1} & \frac{\partial^2 F}{\partial x_n\partial x_2} & \cdots & \frac{\partial^2 F}{\partial x_n^2}
\end{bmatrix}
$$
可以用二阶导数的值判断梯度下降的速率。
Hessian matrix和Jacobi matrix关系：
$$
H_{F}=J(\nabla F^{T})
$$
即：Hessian矩阵是梯度向量对自变量$x$的Jacobian矩阵。
高维情况的牛顿迭代公式是：
$$
x_{n+1}=x_n-\left[HF(x_n)\right]^{-1}\nabla F(x_n), n>=0
$$
三、当前算法背景下如何使用牛顿迭代
对于向量值函数 $F$，Hessian 矩阵 $HF(x_n)$ 是一个高阶张量（三阶张量），而不是一个矩阵。因此，直接使用 Hessian 矩阵在计算上非常复杂。
牛顿-雅可比迭代法是一种用于求解非线性方程和非线性方程组的数值方法。这种方法结合了牛顿法和雅可比矩阵的概念，旨在通过迭代方式逼近方程的根。牛顿法依赖于泰勒展开和线性近似来快速找到方程根的近似值，而雅可比矩阵则提供了一种处理多变量函数的方式，使得该方法可以广泛应用于求解多维非线性问题。
下面详细介绍牛顿-雅可比迭代法。
（1）牛顿法原理
牛顿法基于以下原理：假设你想找到一个函数 $f(x)=0$ 的根，可以从一个初始猜测值 $x_0$ 开始，然后使用函数在该点的泰勒展开的线性部分来找到一个更好的近似。数学上，这可以表示为：
$$
x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}
$$
其中 $x_{n+1}$ 是下一个近似根， $x_n$ 是当前的近似根， $f’(x_n)$ 是函数在 $x_n$ 点的导数。
（2）雅可比矩阵
雅可比矩阵是一个非常重要的概念，用于描述多变量函数相对于其各自变量的一阶偏导数。在牛顿-雅可比迭代法中，雅可比矩阵的作用是帮助我们理解多变量函数在某一点附近的行为。
对于由 n 个方程构成的非线性方程组，其中每个方程都是 m 个变量的函数，雅可比矩阵是一个 $n \times m$ 矩阵，其元素由下式给出：
$$
J_{ij}=\frac{\partial f_i}{\partial x_j}
$$
这里， $f_i$ 是方程组中的第 i 个方程， $x_j$ 是变量向量中的第 j 个变量。雅可比矩阵提供了方程组输出相对于输入的局部线性近似。
在使用牛顿-雅可比迭代法求解非线性方程组时，在多变量的情况下， $f(x)$ 变成了一个向量函数 $f(X)=0$，其中 $X$是变量的向量。这时， $f’(x_n)$ 由雅可比矩阵 $J(X)$ 替代，它是函数 $f(X)$ 相对于$X$的所有偏导数的矩阵。牛顿法的多变量形式可以写成：
$$
X_{n+1}=X_n-J^{-1}(X_n) f(X_n)
$$
这里， $J^{-1}(x_n)$ 是雅可比矩阵在 $x_n$ 点的逆矩阵；
对于向量函数 $\mathbf{F} = (f_1, f_2, f_3,…) $，公式为
$$
X_{n+1}=X_n-J^{-1}(X_n)F(X_n)
$$
（3）使用牛顿雅可比迭代法求解非线性方程组的步骤
1、选择初始猜测：选择一个接近方程根的初始猜测值 $x_0$。
2、计算雅可比矩阵和函数值：在当前猜测值 $x_n$ 处计算雅可比矩阵 $J(x_n)$ 和函数值 $f(x_n)$。
3、求解线性方程组：求解线性方程组 $J(x_n)\Delta x=-f(x_n)$ 以找到 $\Delta x$。
4、更新猜测值：更新猜测值 $x_{n+1}=x_n+\Delta x$。
5、检查收敛性：如果 $x_{n+1}$ 足够接近于方程的根，或者 $f(x_{n+1})$ 足够小，那么停止迭代。否则，回到步骤2继续迭代。
（4）牛顿法和牛顿-雅可比迭代法的区别
牛顿法通常用于单一方程的根求解，利用函数的导数来迭代寻找根的近似值。
牛顿- 雅可比迭代法扩展了牛顿法的应用范围，允许求解多变量的非线性方程组。它使用雅可比矩阵代替导数，适用于多维问题。
以上是牛顿-雅可比迭代法详细介绍，下面是补充。
泰勒展开的基本思想
泰勒展开是用多项式来近似一个函数的值。对于一个函数 $F(x)$，在点 $x_n$ 处的勒展开可以写成：
$$
F(x_n + \Delta x) = F(x_n) + J_F(x_n) \Delta x + 高阶项
$$
其中：
$F(x_n)$ 是函数在 $x_n$ 处的值。
$J_F(x_n)$ 是函数在 $x_n$ 处的雅可比矩阵（一阶导数）。
$\Delta x$ 是一个小的增量。
高阶项包括二阶导数（Hessian 矩阵）及更高阶的项。
局部线性近似
在牛顿法中，我们忽略高阶项，只保留一阶项，得到局部线性近似：
$$
F(x_n + \Delta x) \approx F(x_n) + J_F(x_n) \Delta x
$$
这个近似在 $\Delta x$ 很小的时候是有效的。
牛顿法的目标
牛顿法的目标是找到 $\Delta x$，使得 $F(x_n + \Delta x) = 0$。根据局部近似，我们有：
$$
F(x_n + \Delta x) \approx F(x_n) + J_F(x_n) \Delta x = 0
$$
解这个方程可以得到 $\Delta x$：
$$
J_F(x_n) \Delta x = -F(x_n)
$$
然后解这个线性方程组，得到：
$$
\Delta x = -J_F(x_n)^{-1} F(x_n)
$$
更新公式
根据 $\Delta x = -J_F(x_n)^{-1} F(x_n)$，我们可以更新 $x_n$：
$$
x_{n+1} = x_n + \Delta x = x_n - J_F(x_n)^{-1} F(x_n)
$$
这就是牛顿法的迭代公式。
- 牛顿法通过泰勒展开对 $F(x_n + \Delta x)$ 进行局部线性近似：
$$
F(x_n + \Delta x) \approx F(x_n) + J_F(x_n) \Delta x
$$
- 目标是找到 $\Delta x$，使得 $F(x_n + \Delta x) = 0$，从而得到：
$$
\Delta x = -J_F(x_n)^{-1} F(x_n)
$$
- 最终迭代公式为：
$$
x_{n+1} = x_n - J_F(x_n)^{-1} F(x_n)
$$
关于Jacobian矩阵内元素的偏导数
使用中心差分（求一阶导）
利用Taylor展开，可得：
$$
\begin{align*}
& u\left(x_i+\Delta x, t_n\right)=u\left(x_i, t_n\right)+\frac{\partial u}{\partial x}\left(x_i, t_n\right)\Delta x+\mathcal{O}\left(\Delta x^2\right)\
& u\left(x_i-\Delta x, t_n\right)=u\left(x_i, t_n\right)-\frac{\partial u}{\partial x}\left(x_i, t_n\right)\Delta x+\mathcal{O}\left(\Delta x^2\right)
\end{align*}
$$
上面的两式相减即可得到：
$$
\frac{\partial u}{\partial x}\left(x_i, t_n\right)\approx\frac{u\left(x_i+\Delta x, t_n\right)-u\left(x_i-\Delta x, t_n\right)}{2\Delta x}
$$
四、关于Bezie曲线的子曲线控制点
在 Bézier 曲线 中，如果我们从一条曲线中提取出一段子曲线，那么这段子曲线的控制点与原曲线的控制点通常并不完全相同，尤其是在没有进行任何曲线修改或重构的情况下。
假设有一条 Bézier 曲线，由控制点 $P_0, P_1, …, P_n $定义。曲线的参数 $t $范围是 [0, 1]。如果你从这条曲线中取出一个区间的子曲线，假设该区间的 $t$范围为 $[t_1, t_2]$，这段子曲线的控制点并不等同于原曲线的某一部分控制点。
为什么子曲线的控制点不同：
Bézier 曲线是通过控制点和 Bernstein 基函数加权计算得到的。当你从原始曲线中选取一个子区间时，你实际上是在局部范围内对原曲线进行参数化，而这个局部区间对应的控制点会不同。
具体例子：
假设有一条三次 Bézier 曲线，其控制点为 $P_0, P_1, P_2, P_3$表示为：
$$
B(t) = (1-t)^3 P_0 + 3(1-t)^2 t P_1 + 3(1-t) t^2 P_2 + t^3 P_3
$$
如果我们从曲线中提取一个子区间，例如$t \in [0.2, 0.8]$，那么我们将得到一段新的$ Bézier$曲线。这个新的曲线将由新的控制点组成，并且这些新的控制点并不是原来控制点的简单子集。
如何提取子曲线的控制点？
GME已提供API。
总结：
- 如果从 Bézier 曲线中取出一段子曲线，控制点通常会有所不同。
