NURBS蒙皮/放样曲面生成算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了NURBS蒙皮/放样曲面生成算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

参考资料

《The NURBS Book 2nd》中文版（清华大学出版社）

nurbs曲线蒙皮,算法,几何学,图形渲染,数学建模
学习NURBS的经典书籍，对于NURBS相关的定义与算法进行了详细介绍，并对算法给出了类C风格的代码描述。在书的10.3节中，对生成蒙皮曲面的思路进行了介绍。

github仓库：tinynurbs

tinynurbs仓库地址
轻量级的NURBS库，定义了NURBS相关的数据结构，并实现了如NURBS曲线曲面求值、求切向、求法向、节点插入等基本算法，但没有实现高级曲面构造算法（如蒙皮曲面）。

问题引入

蒙皮/放样

给定空间中的一组NURBS曲线，生成一张经过它们的NURBS曲面，这一过程可以形象地看作是对由曲线形成的骨架蒙上一层皮，因此被称为蒙皮（skinning）或放样（lofting）。蒙皮只是放样的新名词，二者的含义是等价的。

算法思路

对于这组NURBS曲线（常被称为截面曲线），首先需要进行一定的预处理：

如果这组曲线的次数（degree）不统一，使用升阶算法令其统一
（次数=阶数-1，degree指次数，但常用阶数一词描述曲线）
如果这组曲线的节点向量（knots）不统一，使用节点细化算法令其统一
对同阶且节点向量相同的曲线组，使用蒙皮算法

NURBS_Surface Skinning(vector<NURBS_Curve>curves){
	//参考《The NURBS Book 2nd》5.5节
	if(各曲线阶数不统一){
		//将所有曲线的阶数升到与最高阶的曲线相同
		newDegree = max(curves.degree);
		DegreeElevateCurve(curves,newDegree);
	}
	
	//参考《The NURBS Book 2nd》5.3节
	if(各曲线节点向量不统一){
		//合并各曲线节点向量
		new_knots = merge_knots(curves,knots);
		//令各曲线的节点向量改为新节点向量
		RefineKnotVectCurve(curves,new_knots);
	}
	
	//参考《The NURBS Book 2nd》10.3节
	skinSurface = BuildSkinSurface(curves);
	
	return skinSurface；
}

本文将重点讨论完成预处理后的情况，即对同阶且节点向量相同的曲线组生成蒙皮曲面，对于升阶和节点细化算法则仅作简单介绍。

蒙皮曲面生成算法

算法思路

tips：本文采用的NURBS数据结构及属性/方法命名与tinynurbs库一致。
要确定一个NURBS曲面，需要定义以下属性：

u方向次数（degree_u）
v方向次数（degree_v）
u方向节点向量（knots_u）
v方向节点向量（knots_v）
曲面控制点（cotrol_points）
曲面控制点的权重（weights）

以输入的曲线组的方向为u方向，蒙皮的方向为v方向，根据输入的曲线组可以直接确定蒙皮曲面的以下属性：

//各曲线的阶数和节点向量均相同，这就是预处理的意义
skinSurface.degree_u = curve.degree;
skinSurface.knots_u = curve.knots;

对于剩下的属性，分别采用以下方法得到：

v方向次数（degree_v）：任意选取，只要小于曲线数即可
v方向节点向量（knots_v）：参考《The NURBS Book 2nd》中公式10.8和9.8
曲面控制点（cotrol_points）和曲面控制点的权重（weights）：将原曲线组的每列（v方向）控制点作为型值点，根据计算knots_v时得到的参数和节点向量进行曲线插值，反求控制点（参考《The NURBS Book 2nd》例9.1）

《The NURBS Book 2nd》10.3节描述这一过程的原文为：

基于B样条曲线，蒙皮曲面的构造过程如下，令
$C_{k}^{w}(u) =\sum_{i=0}^{n} N_{i,p}(u)P_{i,k}^{w}\quad\quad\quad(k=0,1,...,K)$
为有理或非有理的截面曲线。

注：即曲线组内共有0 ~ K条曲线，每条曲线有0 ~ n个控制点。

在 $v$ 方向，选择次数 $q$ ，确定参数 $\left \{\bar v_{k} \right \},(k=0,...,K)$ 和节点矢量 $V$ 。
然后，根据这些参数和节点矢量对截面曲线的控制点进行 $n + 1$ 次曲线插值，即得到蒙皮曲面的控制点 $Q_{i,j}^{w}$ 。
具体地， $Q_{i,j}^{w}$ 是插值于 $P_{i,0}^{w},...,P_{i,K}^{w}$ 的 $q$ 次曲线的第 $j$ 个控制点。

注：即蒙皮曲面的每列控制点，由对原曲线组的每列控制点插值得到。

注意，即使在截面曲线 $C_{k}^{w}(u)$ 中只有一条是有理曲线，在 $v$ 方向对 $P_{i,k}^{w}$ 的插值也要在四维空间中进行；否则，仅需插值三维点 $P_{i,k}^{w}$

注：即应首先将控制点(x,y,z)变为带权控制点(wx,wy,wz,w)

计算v方向节点向量

计算参数 $\left \{\bar v_{k} \right \}$

首先，需要计算参数 $\left \{\bar v_{k} \right \}$ ，其表示每条截面曲线在 $v$ 方向所对应的参数。
nurbs曲线蒙皮,算法,几何学,图形渲染,数学建模
根据《The NURBS Book 2nd》公式10.8， $\left \{\bar v_{k} \right \}$ 的计算方法如下：

$\bar v_{0}=0,\bar v_{K}=1$
$\bar v_{k}=\bar v_{k-1}+\frac{1}{n+1}\sum_{i=0}^{n}\frac{\left | P_{i,k}^{w}- P_{i,k-1}^{w} \right |}{d_{i}}\quad\quad\quad(k=1,2,...,K-1)$
这里 $d_{i}$ 表示 $P_{i,0}^{w},...,P_{i,K}^{w}$ 的总弦长，即 $d_{i}=\left | P_{i,1}^{w}- P_{i,0}^{w} \right |+\left | P_{i,2}^{w}- P_{i,1}^{w} \right |+...+\left | P_{i,K}^{w}- P_{i,K-1}^{w} \right |$

注：曲线组内共有0 ~ K条曲线，每条曲线有0 ~ n个控制点，第k条曲线的第i个控制点 $P_{i,k}^{w}$
$\bar v_{0}=0,\bar v_{K}=1$ 表明了蒙皮曲面在 $v$ 方向将以第一条与最后一条截面线作为边界，接下来我们来理解 $\bar v_{k}$ 的表达式。
$\left \{\bar v_{k} \right \}$ 表示截面曲线在 $v$ 方向的参数值，其中第 $k$ 条曲线的参数值 $\bar v_{k}$ 比第 $k - 1$ 条曲线的参数值 $\bar v_{k-1}$ 增加了
$\frac{1}{n+1}\sum_{i=0}^{n}\frac{\left | P_{i,k}^{w}- P_{i,k-1}^{w} \right |}{d_{i}}\quad\quad\quad(k=1,2,...,K-1)$

而 $\left | P_{i,k}^{w}- P_{i,k-1}^{w} \right |$ 表示第k条曲线的第i个控制点 $P_{i,k}^{w}$ 和第k-1条曲线的第i个控制点 $P_{i,k-1}^{w}$ 间的距离， $d_{i}$ 表示所有曲线的第i个控制点间的距离之和，因此 $\frac{\left | P_{i,k}^{w}- P_{i,k-1}^{w} \right |}{d_{i}}$ 描述了前后两条曲线的间距在总距离中的占比。
对0 ~ n号控制点分别计算该比例后再取平均（除以 $n + 1$ ），以该值作为截面曲线的参数增加值。

std::vector<double> v;
v.push_back(0); //v_0=0;
double v_pre = 0;
for(int k = 1; k < K; k++) {
	double sum = 0;	//sum(P/d)
	for(int i = 0; i <= n; i++) {
		//第k条曲线的第i个控制点和第k-1条曲线的第i个控制点的距离
		double P_distance = distance(P[k][i], P[k-1][i]);
		//所有曲线第i个控制点间的距离之和
		double sum_P_distance = 0;	//di
		for(int l = 1;l <= K; l++) {
			sum_P_distance += distance(P[l][i], P[l-1][i]
		}
		sum += P_distance / sum_P_distance;	
	}
	double v_k = v_pre + sum / (n+1);
	v.push_back(v_k);
	v_pre = v_k;
}
v.push_back(1);	//v_K=1

计算节点向量

根据《The NURBS Book 2nd》公式9.8，可以用如下方法计算节点向量 $U=\left \{u_{0},u_{1},...,u_{m}\right \}$ ：
$u_{0}=u_{1}=...=u_{p}=0,\quad u_{m-p}=u_{m-p-1}=...=u_{m}=1$
$u_{j+p}=\frac{1}{p}\sum_{i=j}^{j+p-1}\bar v_{i}\quad\quad (j=1,2,...,n-p)$
其中， $p$ 为v方向次数，即前文提到的degree_v。
节点值由参数值取平均得到，用这种方式定义的节点矢量能很好地反应参数值的分布情况。

计算曲面控制点及权重

计算曲面控制点的方法可以用一句话概括：以截面曲线组v方向的每列控制点为型值点，反求曲面在v方向的每列控制点。这一过程被称为曲线插值，具体来说流程如下：
截面曲线组中共有 $(K + 1)$ 条曲线，每条曲线均具有 $(n + 1)$ 个控制点。以所有曲线的第 $i\quad(i=0,1,...,n)$ 个控制点为一列，构造一条经过这列控制点的NURBS曲线。这条新构造的曲线的控制点就是蒙皮曲面的第 $i$ 列控制点。
这一过程是曲线求值的逆过程，因此通过解线性方程组即可求得蒙皮曲面的控制点。
注意：虽然需要对每一列控制点都进行曲线插值，但只需要计算一次参数和节点向量，这对于每列控制点都是统一的。
为简化描述，前文常使用控制点一词替代带权控制点。实际上，即使在截面曲线组中只有一条是有理曲线，在 $v$ 方向对 $P_{i,k}^{w}$ 的插值也要在四维空间中进行。因此，最后需要将计算得到的蒙皮曲面的带权控制点还原为控制点 $(x, y, z)$ 和权值 $w$ 。

预处理截面曲线

升阶算法

参考《The NURBS Book 2nd》5.5节

节点细化算法

参考《The NURBS Book 2nd》5.3节
节点插入是指一次插入单个节点，而节点细化是指一次插入多个节点。显然，节点细化可以通过多次应用节点插入算法来实现，但节点细化存在更有效的算法。这一算法的实现，可以参考《The NURBS Book 2nd》中的算法A5.4。
对于节点插入算法，tinynurbs库进行了实现，是include/tinynurbs/core/modify.h中的curveKnotInsert方法。如果插入节点较少，也可以通过多次调用该方法来实现节点细化。