直观地说,将曲线视为您可以用笔绘制的东西。曲线是笔在时间间隔内跟踪的点的集合。虽然我们通常想象用笔在 2D 的纸上,但实际上笔可以在 3D 中移动以生成空间曲线,或者您可以想象笔在某些其他类型的空间中移动。
在数学上,曲线的定义至少可以通过两种方式看到
- n 维空间中某个小区间上的连续图像。
- 从一维空间到 n 维空间的连续映射。
这两个定义都是从区间的思想开始构思的。然而,有一个显着差异:在第一个定义中,曲线是笔迹(图像)上点的集合。而在第二个定义中,曲线是时间和点集之间的映射。 在本章中,我们使用第一个定义。
静态的曲线和动态的曲线?
曲线是一组拥有无限数量的点的集合。曲线中的点都有两个邻居,除了端点。 有些曲线没有端点,要么因为它们是无限的,要么是封闭的。
由于曲线的笔迹很细(无限小的厚度),因此很难单纯的用线来填充出一个实心的区域。虽然在数学上的用曲线填充空间是由可能的(通过让它们自己折叠无限多次),但我们在这里不考虑这样的数学奇数。 一般来说,我们认为曲线是事物的轮廓,而不是“内部”的填充。
我们需要解决的问题是如何确定曲线——为曲线给出名称或表示方法,以便我们可以将它表示在计算机上。 对于一些曲线,命名它们很容易,因为它们具有已知的形状:线段、圆、椭圆弧等。 有时没有“命名”形状的一般曲线称为自由形式(free-form)曲线。因为自由形式曲线只能取任何形状,所以更难指定。
在数学上指定曲线有三个主要方法:
- 隐式曲线表示通过给出一个隐式函数来定义曲线上的点集,可以通过不断测试这个等式来查看一个点是否在曲线上。通常,隐式曲线表示由形式的隐函数定义:$f(x,y)=0$。所以曲线是这个方程为“true”的点的集合。请注意,隐式函数 f 是一个标量函数。
- 参数曲线表示提供了从自由参数到曲线上点集的映射。也就是说,这个自由参数为曲线上的点提供了一个索引。曲线的参数形式是将位置分配给自由参数值的函数。这条曲线的参数函数告诉我们笔在任何时刻的位置:$(x,y)f(t)$。请注意,参数函数是一个向量值函数。
- 生成式或程序化曲线提供了与前两种方案不同的生成方法。生成曲线描述的例子包括细分和分形。
请记住,曲线是一组点。这些表示为我们提供了指定这些点的集合的方法。任何曲线都有许多可能的表示。 出于这个原因,数学家通常小心地区分曲线及其表示。然而在计算机图形学中,我们经常是草率指定的。因为我们通常只引用它的表示,而非真实的曲线本身。所以当有人说“隐式曲线”时,它们要么指的是由某个隐函数表示的曲线,要么指的是某个曲线的隐函数。这种区别通常并不重要,除非我们需要考虑同一曲线的不同表示。 我们将在本章中考虑不同的曲线表示,因此我们将更加小心。当我们使用像“多项式曲线”这样的术语时,我们将意味着可以用多项式表示的曲线。
根据本章开头给出的定义,对于曲线,它必须具有参数表示。
然而,许多曲线还有其他表示。例如,二维中的一个圆,其中心在原点,半径等于 1,可以写成隐式形式或者参数化形式:
参数形式不一定是给定曲线的最方便的表示。
事实上,一条曲线可能有具有简单隐式或生成式的表示方法,但它很难找到参数表示。
曲线的不同表示有优缺点。例如,参数曲线更容易绘制,因为我们可以采样自由参数。 一般来说,参数形式是计算机图形学中最常用的形式,因为它们更容易使用。我们的重点是曲线的参数表示。
参数曲线是指在特定区间内由特定参数函数给出的曲线。更准确地说,参数曲线有一个给定的函数,它是从参数区间的映射。在单位区间从 0 到 1 上的参数通常使用起来很方便。当自由参数在单位区间上变化时,我们通常将参数表示为 u。
如果我们将参数曲线视为用笔绘制的线,我们可以将 u = 0 视为笔首先在落在纸上的时间,时间单位是绘制曲线所需的时间(u = 1 是曲线的末端)。曲线可以由时间映射到位置的函数来指定——“时间 u 时,笔在哪里?”
如果我们得到一个函数 f (t),它指定区间 [a, b] 上的曲线,我们可以很容易地定义一个新函数 f2(u),该函数指定单位区间上相同曲线。我们可以首先定义:
两个方程表示的曲线相同,但是参数的取值范围不一样。
这两个函数 f 和 f2 都代表相同的曲线;但是,它们提供了曲线的不同参数化。为现有曲线创建一个新的参数化过程称为重参数化,从旧参数到新参数的映射称为重参数化函数。
如果我们通过一些参数化定义了一条曲线,那么存在无限多的其他参数化(因为我们总是可以重参数化)。能够对曲线进行多个参数化是有用的,因为它允许我们创建方便的参数化。然而,它也可能有问题,因为它使比较两个函数是否表示相同的曲线变得困难。
这个问题的本质是更普遍的——自由参数(或时间元素)的存在为我们的曲线表示增加了一个看不见的,潜在的未知元素。当我们看到画好的曲线时,这支笔可能在整个时间区间内以恒定的速度移动,或者它可能开始很慢,然后加速。考虑下面一条非常简单的曲线的表示:
这三个函数在单位区间上表示同一曲线。然而,当 u 不为 0 或 1 时,f (u)是不同的点,这取决于曲线的表示。
如果我们给出了曲线的参数化,我们可以直接使用它来确定曲线,或者我们可以开发一个更方便的参数化。 通常,自然参数化是以一种方便(或自然)指定曲线的方式,因此我们不必知道速度如何沿着曲线变化。
如果我们知道笔以恒定的速度移动,那么自由参数的值就更有意义了。 参数空间的一半就是曲线的一半。这个参数不是测量时间,而是沿着曲线测量长度。这样的参数化称为弧长参数化,因为它们通过沿曲线的距离(称为弧长)映射到位置的函数来定义曲线。我们经常用变量 s 来表示弧长参数。
从技术上讲,如果参数化曲线的正切的大小是恒定的,则参数化就是弧长参数化。用方程表示:
其中 f (t)是用自然参数化定义曲线的函数。
使用弧长参数化要求能够在给定 s 的情况下解出 t 的式子。 对于我们所研究的许多类型的曲线,它不能在首尾相接的形式下结算,而必须使用数值解。
通常,我们使用变量 u 来表示在单位区间内的自由参数,s 来表示弧长自由参数,t 来表示不属于其他两个参数之一的参数。
对于一些曲线,定义一个参数函数来表示它们的形状是很容易的。例如,直线、圆和椭圆都有简单的函数,可以根据参数定义它们所包含的点。对于许多曲线来说,找到一个函数来指定它们的形状是很困难的。 我们用来创建复杂曲线的主要策略是分而治之——我们将曲线分解成许多更简单的小块,每个小块都有一个简单的描述。
例如,考虑图 15.1 中的曲线。前两条曲线很容易用两部分来表示。在图 15.1(b)所示曲线的情况下,我们需要两种不同的部件:线段和圆。
要创建复合曲线的参数表示(如图 15.1(b)中的曲线),我们需要让参数函数在表示各个部分的函数之间切换。如果我们在 0≤u≤1 的范围内定义参数函数,那么图 15.1(a)或(b)中的曲线可以定义为
其中 f1 是第一部分的参数化,f2 是第二部分的参数化,这两个函数都是在单位区间上定义的。
我们需要仔细定义函数 f1 和 f2 以确保曲线的各个部分能匹配在一起。如果 f1(1) != f2(0),那么我们的曲线段不会连接在一起,不会形成单一的连续曲线。
为了表示图 15.1(b)中的曲线,我们需要使用两种不同类型的片:线段和圆弧。为了简单起见,我们可能更喜欢使用单一类型的 piece。 如果我们试图只用一种类型的部件(线段)来表示图 15.1(b)中的曲线,我们就不能精确地重新创建曲线(除非我们使用无限数量的线段)。虽然由线段组成的新曲线(如图 15.1(c)所示)可能与图 15.1(b)中的形状不完全相同,但对于我们的使用来说,它可能足够接近。 在这种情况下,我们可能更喜欢使用更简单的线段片段的简单性,而不是使用更准确地表示形状的曲线。
同时,注意当我们使用越来越多的片段时,我们可以得到更好的近似值。 在极限情况下(使用无限数量的碎片),我们可以准确地表示原始形状。
因此,如果我们试图表示一个复杂的形状,我们可能会决定一个粗略的近似是可以接受的,并使用少量的简单部分。
为了提高近似,我们可以选择使用更多的片段和使用更复杂的片段。 在计算机图形学实践中,我们倾向于使用相对简单的曲线片段(线段、弧段或多项式段)。
在电脑出现之前,当绘图员想要画一条光滑的曲线时,他们使用的一种工具是一块刚性的金属,他们将其弯曲成所需的形状以进行描摹。因为金属会弯曲,所以它会有一个光滑的形状。 这种刚性意味着金属会尽可能少地弯曲,以达到理想的形状。这块刚性的金属被称为样条曲线。
数学家们发现,他们可以用分段多项式函数来表示绘图员的样条曲线。最初,他们用样条来表示光滑的分段多项式函数。 最近,术语”样条“被用来描述任何分段多项式函数。我们更喜欢后一种定义。
对我们来说,样条是一个分段多项式函数。这样的函数在表示曲线时非常有用。
为了描述一条曲线,我们需要给出一些关于它的性质。对于常见的曲线(线段、圆、椭圆等),属性通常根据曲线的类型而特定。例如,要描述一个圆,我们可以提供它的半径和圆心的位置。对于椭圆,我们还可以提供其长轴的方向和轴长之比。 然而,对于自由曲线,我们需要一组更一般的属性来描述单个曲线。
曲线的一些性质只与曲线上的一个位置有关,而另一些性质则需要了解整个曲线。 为了直观地了解两者的区别,可以把曲线想象成火车轨道。如果你在雾天站在赛道上,你可以分辨出赛道是直的还是弯的,以及你是否在终点。这些是局部属性。 你无法判断轨迹是否是闭合曲线,或者交叉,或者它有多长。我们称这种属性为全局属性。
对几何物体(曲线和曲面)局部性质的研究被称为微分几何。 从技术上讲,要成为可微的性质,这些性质有一些数学上的限制(换句话说,在火车轨道的比喻中,您将无法使用 GPS 或指南针)。 与其担心这个属于上的区别,我们简单的将使用”局部“性质而不是可微性质。
局部性质是描述曲线的重要工具,因为它们不需要了解整个曲线。局部属性包括:
- 连续性
- 曲线上特定位置的 position
- 点的方向
- 曲率或其他导数
通常,我们想要考察特定点在不在曲线上。 如果一个点是曲线的一部分,我们就说它是曲线的内插点。如果对于一组曲线参数 u 而言,存在的某个值 t,使得 f (t) = v,函数 f 就会插值一个点 v,我们把插值的位置,也就是 t 的值,称为位置。
理解两条参数曲线的局部性质是非常重要的,当两条参数化曲线连接在一起的时候。 如果曲线是用类似于式的公式定义的,那么我们需要注意如何定义这些部分。如果 ff1(1) != f2(0),那么曲线将被“折断”——我们将无法在连续的笔划中绘制曲线。我们把曲线片段拼接在一起的条件称为连续性条件,因为如果它们成立,曲线就可以被画成一个连续的片段。 因为我们在本章开头对“曲线”的定义要求曲线是连续的,所以从技术上讲,“断裂曲线”不是曲线。
除了位置,我们还可以检查曲线的导数是否匹配正确。若 f ' 1(1) != f ' 2(0),则组合曲线在切换点处的一阶导数会发生突变:一阶导数不是连续的。
一般来说,我们说一条曲线是 Cn 连续的,如果它所有的 n 阶导数都连续。我们将位置本身表示为零阶导数,因此 C0 连续条件意味着曲线的位置是连续的,C1 连续意味着位置和一阶导数是连续的。
曲线的基本定义要求曲线为 C0 连续。
一阶导数的不连续通常是明显的,因为它显示了一个尖角。二阶导数的不连续有时在视觉上是明显的。
根据不同的应用,高阶导数的不连续可能会有影响。例如,如果曲线表示运动,则二阶导数(加速度)的突变是明显的,因此三阶导数连续性通常是有用的(3 阶连续可以防止 2 阶导数突变)。
如果曲线上有流体流过(例如,如果它是飞机机翼或船体的形状),那么四阶或五阶导数的不连续可能会导致湍流。
我们刚刚介绍的连续性类型(Cn)通常被称为参数连续性,因为它取决于两个曲线片段的参数化。如果每一块的“速度”不同,那么它们就不是连续的。
对于我们关心曲线形状而不是其参数化的情况,我们定义几何连续性,要求当曲线被等效参数化时曲线片段的导数匹配(例如,使用弧长参数化)。直观地说,这意味着相应的导数必须有相同的方向,即使它们的大小不同。
一般来说,几何连续性比参数连续性约束更少。Cn 曲线就是 Gn,除非参数导数消失。
计算机图形学中最广泛使用的曲线表示是将多项式定义的基本元素拼凑在一起,称为多项式片段。
我们可以为不同的应用选择方便的多项式形式,我们称它们为基函数或混合函数(多项式基函数)。如果基函数集选择正确,则任何 n + 1 次多项式都可以用适当选择的 c 来表示。
标准形式并不总是有方便的系数。出于实际目的,在本章中,我们将找到一组基函数,这些基函数的系数是控制由多项式函数表示的曲线的方便方法。
要指定嵌入在二维空间中的曲线
- 可以指定 t 中的两个多项式:一个表示 x 如何随 t 变化,另一个表示 y 如何随 t 变化;
- 或者指定一个多项式,其中每个 ai(标准多项式的系数)都是一个 2D 点。
对于 n 维空间中的任何曲线都存在类似的情况。
考虑一条连接点 p0 和点 p1 的线段。我们可以把这个线段在单位域中的参数函数写成
虽然用其端点的位置来描述线段是显而易见且通常很方便的,但还有其他方法来描述线段:
- 线段中心的位置、方向、长度
- 一个端点的位置和第二个端点相对于第一个端点的位置
- 线段的中间和一个端点的位置。
描述线段的另一种方法是使用多项式的标准形式(端点-位移型):
为了将标准形式写成向量表达式,我们定义一个向量 u,它是 u 的幂向量:
虽然它在数学上很简单,但标准形式并不总是表示曲线的最方便的方式。
例如,我们可能更喜欢通过其端点的位置来指定线段。如果我们想定义 p0 为线段的起点,p1 为线段的终点,我们可以这样写
对于更复杂的示例,将公式写成矩阵形式会更容易:
我们称 C 为约束矩阵。
我们可以通过求 C 的逆矩阵来解出 a。这个逆矩阵我们用 B 表示并它叫做基矩阵。
基矩阵非常方便,因为它告诉我们如何在方便的参数(端点式)和标准形式 a 之间进行转换,因此,它给了我们一种计算曲线的简单方法:
非线性定义例如线段的长度和角度。
线段是如此简单,以至于找到一个基矩阵是微不足道的。然而,对于更高度的曲线,这是一个很好的引导。 首先,让我们考虑二次曲线(二次曲线)。标准形式的优点是,它适用于这些更复杂的曲线,仅仅只是让 n 换成一个更大的数字就行。
二次多项式(二次多项式)有三个系数:a0、a1 和 a2。这些系数不便于描述曲线的形状。
然而,我们可以使用相同的基矩阵方法来设计更方便的参数。假设我们想用起始点(u = 0)、中间点 2 (u = 0.5)和结束点(u = 1)的位置来描述我们的曲线。那么:
有一种附加类型的约束(或参数)有时很容易指定:曲线在特定值处的导数(相对于其自由参数)。
直观上,导数告诉我们曲线如何变化,一阶导数告诉我们曲线的方向,二阶导数告诉我们曲线改变方向的速度,等等。
练习题
如果我们知道基矩阵 B,我们可以把它乘以参数向量 u,得到一个函数向量:
混合函数为描述曲线提供了一个很好的抽象概念。任何类型的曲线都可以表示为其控制点的线性组合,其中这些权重则由是自由参数计算的向量函数。
一般来说,n 次多项式可以插值 n + 1 个值的集合(在 n+1 个点上准确成立)。如果给我们一个向量 p = (p0),…, pn)和另一个向量 t= (t0,…, tn)(其中 ti != tj),我们可以使用前面章节中描述的方法来确定一个 n + 1 × n + 1 基矩阵,该矩阵给出一个函数 f (t),使得 f (ti) = pi(拉格朗日多项式插值)。
对于任意给定的向量 t,我们需要建立并求解一个 n = 1 × n + 1 的线性方程组。这为我们提供了一组 n + 1 个基函数来执行插值:
拉格朗日多项式插值
插值多项式提供了一种机制来定义插值一组点的曲线。虽然可以创建一个多项式来插值任意数量的点,但我们很少使用高阶多项式来表示计算机图形学中的曲线。
相反,插值样条(分段低次多项式函数)是首选。
现在我们已经了解了如何制作多项式曲线的各个部分,我们可以考虑如何将这些部分组合在一起。
分段参数函数的基本思想是,每一个片段只在某个参数范围内使用。例如,如果我们想定义一个函数,它有两个分段线性线段连接三个点,我们可以定义
对于我们的分段函数中的每个多项式,都有一个位置(或参数值)、开始点和结束点。函数开始或结束的位置称为结。
我们也可以把分段多项式函数写成基函数的和,每个基函数由一个系数缩放。例如,我们可以将上面的两条线段重写为:
多项式函数的结是用来创建它的所有部分的结的集合。结向量是一个以升序存储所有结值的向量。
注意,在本节中,我们使用了两种不同的机制来组合多项式片段:
- 对参数的不同范围使用独立的多项式片段,
- 以及将分段多项式函数混合在一起。
上文中,我们定义了单位参数范围内的多项式片段。如果我们想要组合这些部分,我们需要将整个函数的参数转换为该部分的参数值。 最简单的方法是在参数范围[0,n]上定义整体曲线,其中 n 是段的数量。根据参数的值,我们可以将其移动到所需的范围。
如果我们想从两条线段中做出一条曲线,我们需要确保第一个线段的末端与下一个线段的起点在同一位置。连接这两个部分的方法有三种:
- 将线段表示为它的两个端点,然后对两者使用同一点——共享点方案
- 每当第一个段的参数改变时,将第一个段结束点的值复制到第二个段的起始点——依赖方案
- 写出两个线段连接的显式方程,并在其他参数发生变化时通过数值方法来强制保证连接性。
虽然更简单的方案是可取的,因为它们需要较少的工作,但它们也对线段参数化的方式施加了更多的限制。 例如,如果我们想使用线段的中心作为参数(以便用户可以直接指定),我们将使用每个线段的开始和线段的中心作为它们的参数。这将迫使我们使用依赖方案。
注意,如果我们使用共享点或依赖方案,控制点的总数小于 n * m,其中 n 是片段的数量,m 是每个片段的控制点的数量。独立片段的许多控制点将作为其他片段的函数来计算。 请注意,如果我们对直线使用共享点方案(每个线段使用其两个端点作为参数,并与其相邻的线段共享内部点),或者如果我们使用依赖方案(例如具有第一个端点和中点的示例),我们最终会对 n 个线段曲线使用 n + 1 个控制参数。
依赖方案有一个更严重的问题。曲线上一个地方的变化可以传播到整个曲线。这就是所谓的局部性缺失。
局部性意味着如果你移动曲线上的一个点,它只会影响局部区域。局部区域可能很大,但它将是有限的。如果曲线的控制没有局部性,改变一个控制点可能会影响无限远的点。
为了了解局部性和局部性的缺失,考虑两条线段链。
- 一条链的各个部分由端点参数化,并使用点共享来保持连续性。
- 另一个则通过端点和中点参数化其片段,并使用依赖关系传播将片段保持在一起。
这两个线段链可以表示相同的曲线——它们都是 n 个相连线段的集合。 但是,由于局部性问题,端点共享表单可能对用户更方便。考虑改变每条链中第一个控制点的位置。对于端点共享方案,只有第一个段会改变,而在中点版本中,所有的段都会受到影响。 实际上,对于端点共享版本中移动的任何点,最多只会改变两条线段。在中点版本中,被移动的控制点之后的所有片段都会改变,即使链是无限长的。
在此示例中,依赖传播方案是没有局部控制的方案,当这并不总是正确的。也有直接共享方案,不满足局部性。
我们强调局部性是一个控制便利性的问题。 虽然每次都改变整个曲线很不方便,但可以对曲线进行相同的改变。 只需要一致地移动几个点。
在图形中,当我们使用分段多项式表示曲线时,我们通常对片段使用线性或三次多项式。三次多项式在计算机图形学中很受欢迎的原因有很多:
- 分段三次多项式允许 C2 连续性,这通常足以满足大多数视觉任务。两次插值提供地 C1 平滑度常常不够平滑。由高次多项式提供的平滑性很重要。
- 三次曲线为一组点提供最小曲率插值。也就是说,如果你有一组 n +3 个点,并定义了穿过它们的“最平滑”曲线(即在其长度上具有最小曲率的曲线,曲率半径最大),则该曲线可以表示为具有 n 个分段的分段三次曲线。
- 三次多项式具有良好的对称性,在开始和结束时可以指定位置和导数。
- 三次多项式在计算的数值问题和平滑度之间有很好的权衡。
请注意,我们不需要非得使用立方插值;它们只是在平滑度和复杂性之间取得很好的权衡。
不同的应用程序可能有不同的权衡。我们专注于立方插值,因为它们是最常用的。
我们寻求三次多项式的形式,其中系数是控制三次表示的结果曲线的一种方便方法。主要便利性之一是提供确保片段的连通性和片段之间的连续性的方法。
每个三次多项式段需要四个系数或控制点。这意味着对于具有 n 个片段的分段多项式,如果没有段之间的共享或使用依赖项,我们可能需要多达 4n 个控制点。 更常见的是,每个片段的某些部分要么共享,要么依赖于相邻的片段,因此控制点的总数要低得多。
不幸的是,分段三次没有单一的“最佳”表示。 不可能存在一个分段多项式曲线表示,这个表示具有以下所有理想属性:
- 每条曲线都是三次的
- 曲线插值控制点(曲线进过插值点)
- 曲线具有局部控制
- 曲线具有 C2 连续性。
我们可以拥有任何的三个属性,但无法拥有全部的 4 个属性。 在本书中,我们将讨论三次 B 样条曲线(不经过插值点,但拥有局部控制和 C2 平滑性)、Cardinal 样条线、Catmull-Rom 样条线(经过插值点,也有局部控制,但是没有 C2 平滑),以及普通的三次插值(经过插值点,C2 也有,但是没有局部控制)。
连续性特性是指段之间的连续性(在结点处)。三次插值本身的导数具有无限的连续性。请注意,如果您有很多控制点(或节),则曲线可以摆动,但看起来并不”光滑“(震荡,实际上是光滑的,但看上去不光滑)。
使用分段三次曲线,可以创建一个 C2 曲线。为此,我们需要在每个段的开头指定位置和一阶、二阶导数(以便我们可以确保它与前一个段的末尾相同)。
请注意,每条曲线段从其链中先前曲线的四个参数中接收三个。这些三次的 C2 连续插值有时被称为自然三次样条。
给定一组 n 个控制点,自然三次样条有 n-1 个立方体段。第一部分使用控制点在开始时定义其起始位置、结束位置和一阶、二阶导数。使用依赖方案从上一个片段的结束点上复制 position、一二阶导数,用于下一个片段。
自然三次样条的缺点是它们不是局部的。任何线段中的任何更改都可能需要更改整个曲线(至少会影响更改点之后的曲线)。 更糟糕的是,自然三次样条曲线往往是病态的:曲线开始时的一个小变化可能导致后来的大变化。 另一个问题是,我们只能控制曲线开始时的导数。曲线起点之后的段的导数由段起始点决定。
三次 Hermite 样条的一个片段允许指定其两个端点的位置和一阶导数。一条曲线可以链接到 CI 平滑的样条上,只要两个曲线在端点上拥有相同的位置和一阶导数。
给定一组 n 个控制点,其他的每一个控制点都是一个导数值,三次 Hermite 样条包含(n—2)/2 个三次分段。Hermit 三次插值进过所有的插值点,但是只有 C1 的平滑度。
Hermite 三次插值是方便的,因为它们提供了对形状的局部控制,并提供了 C1 连续性然而,由于用户必须指定位置和导数。
基数三次样条是 C1 平滑的一种类型。由三次多项式段组成的插值样条。 给定一组 n 个控制点,基数三次样条使用 n-2 个三次多项式片段来插值所有的点(除了起点和终点)
基数样条曲线有一个称为张力的参数,用于控制曲线在其插入的点之间的“紧度”。张力是范围[0,1],用于控制曲线如何向下一个控制点弯曲。
对于 t = 0 的重要特殊情况,样条被称为 Catmull-Rom 样条。
基数样条的每一段使用四个控制点。对于线段 i,使用的点是 i、i +1、i +2 和 i +3,因为线段与其相邻线段共享三个点。每一段开始于其第二个控制点,结束于其第三个控制点。曲线开始处的导数由第一个和第三个控制点之间的矢量确定,而曲线结束处的导数由第二个和第四个控制点之间的矢量给出。
张力参数调整导数的缩放程度。具体地:
由于线段 i 的第三个点是线段 i +1 的第二个点,所以基数样条的相邻线段连接。类似地,相同的点用于指定每个线段的一阶导数,提供 C1 连续性。
基数样条很有用,因为它们提供了一种简单的方法来插值具有 CI 连续性和局部控制的点集。他们只是 C1,所以他们有时会得到“扭结”。张力参数可以控制插值点之间发生的情况。
这不是玩贝塞尔曲线经常会看到的么。。。
给定一组 n 个点进行插值,您可能想知道为什么我们可能更喜欢使用基数三次样条,而不是一条高次多项式插值。插值多项式的一些缺点是:
- 插值多项式倾向于超调点(震荡)。随着点数的增加,这种超调(震荡)变得更糟。基本样条线在点之间的行为往往很好。
- •插值多项式的控制不是局部的。在样条起始片段改变一个点会影响整个样条线。基数样条是局部的——样条上的任何位置最多受其四个相邻点的影响。
- •插值多项式的评估不是局部的。评估多项式上的一个点需要访问所有的点。评估分段三次插值上的一个点需要固定数量的计算(查询点局部的点),无论点的总数有多大。
基数样条的缺点是它不插值第一个和最后一个点,这可以通过在序列的末尾添加额外的点来轻松固定。基数样条也不是连续的——仅在节点处提供 C1 连续性。
控制曲线的最简单方法是让曲线插值指定的一组点。然而,在实践中,插值方案往往具有不良属性,因为它们的连续性较小,并且对于插值点之间的曲线缺少控制。
拟合曲线方案通常是首选。使用近似方案,控制点影响曲线的形状,但不准确地指定它。虽然我们放弃了让曲线通过指定点的能力,但我们获得了曲线和局部控制的更好性能。 我们应该需要对一组点进行插值,可以计算出控制点的位置,使曲线通过这些插值点。
计算机图形学中两种最重要的近似曲线类型是贝塞尔曲线和 B 样条曲线。
B́ezier 曲线是计算机图形学中自由形式曲线最常见的表示之一。B́ezier 曲线是近似其控制点的多项式曲线。曲线可以是任何次数的多项式。d 次曲线由 d + 1 个控制点控制。曲线插值其第一个和最后一个控制点(准确通过起点和终点),形状直接受到其他点的影响。 通常,通过连接低次的一组 B́ezier 曲线(通常使用三次(d=3)B́ezier 曲线),来实现复杂的形状。
Bézier 曲线在计算机图形学中非常流行,因为它们易于控制,具有许多有用的性质,并且有非常高效的算法来处理它们。Bézier 曲线构造如下:
- 曲线插值第一个和最后一个控制点
- 曲线在其起点(终点)的一阶导数由相邻的控制点确定。导数由这些点之间的向量给出,并按曲线的阶数缩放。
- 曲线起点(终点)的高阶导数。n 阶导数取决于前(后)n +1 个点。
考虑图 15.10 中的 3 次贝塞尔曲线。该曲线有四个(d +1)控制点。它开始于第一个控制点(po),结束于最后一个控制点(p1)。开始时的一阶导数与第一和第二控制点之间的矢量(p1—po)成比例。具体地,f '(0)= 3(p1—po)。类似地,曲线末端的一阶导数由 f'(1)= 3(p3—p2)给出。
曲线开始处的二阶导数可以由控制点 po、p1 和 p2 确定。利用前面一段中关于贝塞尔三次函数的知识,我们可以为它们创建一个参数函数:
幸运的是,B́ezier 曲线的混合函数具有适用于所有次数的特殊形式。这些函数被称为伯恩斯坦基多项式(Bernstein basis polynomials),具有一般形式:
B́ezier 曲线有几个有用的性质:·
- 曲线受控制点的围成的凸包的限制(曲线位于凸包内部)。·
- 任何直线与曲线相交的次数不超过与连接控制点的线段集相交的次数。这被称为变化递减特性。
- 曲线是对称的:反转控制点的顺序会产生相同的曲线,具有反向参数化。•
- 曲线是仿射不变的。这意味着平移、缩放、旋转或偏移控制点与对曲线本身执行这些操作相同。•
- 有良好的简单算法可以将曲线细分为小片段,这些小片段也是贝塞尔曲线。可以使用稍后描述的算法来有效地完成细分,可以使用分治方法来创建有效的算法,用于诸如绘制 Bézier 曲线、用线段逼近它们以及确定两条曲线之间的交点等重要任务。
当贝塞尔曲线段连接在一起以形成样条曲线时,通过共享端点来创建曲线之间的连通性。然而,导数的连续性必须通过定位其他控制点来创建。这为用户提供了对平滑度的控制。
为了 G1 平滑度,第一条曲线的倒数第二个点和第二条曲线的第二个点必须与端点共线。对于 C1 连续,点之间的距离也必须相等。(G1 只要求方向相同,C1 还要保证大小也相同)
图 15.13 显示了这一点。通过正确定位更多的点可以创建更高程度的连续性。
贝塞尔曲线可以从几何原理和上述的代数方法导出。我们来谈谈几何原理,因为它们提供了 Bézier 曲线机制的直观理解。
假设我们有一组控制点,我们希望从中创建一条平滑的曲线。简单地用线连接点(形成控制多边形)将导致一些不光滑的东西。它将有尖锐的拐角。
我们可以想象通过切掉尖角来“平滑”这个多边形,产生一个更平滑的新多边形,但在数学意义上仍然不是“平滑”(因为曲线仍然是一个多边形,因此只有 C1)。我们可以重复这个过程,每次都会得到一个平滑的多边形。在极限下,如果我们重复这个过程无限次,我们将得到一条 C1 光滑曲线。
我们用角点切割所做事情的是定义一个了细分方案。也就是说,我们通过将更简单的线段分解为更小的部分(细分它)的过程来定义曲线。得到的曲线是通过无限多次应用过程来实现的极限曲线。如果细分方案被正确定义,结果将是一条平滑的曲线,它将具有参数形式。
让我们考虑将角点切割应用于单个角点。给定三个点(p0, p1, p2),我们重复“切断角”。在每一步中,我们将每条线段分成半段,连接中点,然后将角点移动到新线段的中点。
请注意,在这个过程中,引入了新点,移动一次,然后保持该位置的任何剩余迭代。端点永远不会移动。
该结构实际上适用于沿每个片段的其他比例距离。u 是点距离端点的距离比例,我们可以将这个表达式重写为:
B́ezier 曲线的一个很好的特性是有一种非常简单和通用的方法来计算和细分它们。该方法称为 de Casteljau 算法,使用一系列线性插值来计算沿着任意顺序的贝塞尔曲线的位置。它是前一节中描述的细分方案的推广。
de Casteljau 算法首先使用线来连接相邻的点,并找到这些线上插值系数为 u 的点(n 片段上共有 n-1 个这样的点)。然后,相应插值系数的点用线相连,再次寻找线段上插值为 u 的点,这次我们只得到一组 n—2 个点。重复这个过程,直到线段上只有一个插值为 u 的点。
计算贝塞尔线段上的点的过程还提供了一种在该点处划分线段的方法。在 de Casteljau 算法中计算出的中间点构成了新的、较小的段的新控制点,如图下图所示。
Bézier 曲线分割算法的存在使得分治算法成为可能。
例如,在绘制贝塞尔曲线时,很容易检查曲线是否接近一条直线,因为它受其凸包的限制。如果曲线的控制点都接近共线,则曲线可以绘制为一条直线。
类似的算法可用于确定两条曲线的交点。由于此类算法的存在,其他曲线表示通常被转换为 B ́ezier 形式进行处理。
B-Splines 提供了一种用 d 次多项式组成的曲线来近似一组 n 个点的方法,该曲线给出了 C(d−1)连续性。 与上一节的 B ́ezier 样条不同,B 样条允许为任何所需连续性程度(几乎能达到 Cn 连续性)生成曲线。正因为如此,b 样条是计算机图形学中指定非常平滑的曲线(高度连续性)的首选方法。如果我们想通过任意数量的点进行 C2 或更高平滑度曲线,B 样条可能是正确的方法。
我们可以用 b 样条基函数的线性组合来表示曲线。由于这些基函数本身是样条曲线,我们称它们为基样条或 b 样条。每个 B 样条或基函数由一组 d + 1 个多项式组成,每个多项式次数为 d。 B 样条方法为定义这些函数提供了通用程序。
b 样条一词特指一个基函数,而不是由一组 b 样条的线性组合产生的函数。然而,在计算机图形学中如何使用这个术语是不一致的。通常,“b 样条曲线”用于表示由 b 样条的线性组合表示的曲线。
将样条表示为其他样条的线性组合:
PI 是系数,bi 是基函数。如果系数是点(向量),我们将它们称为控制点。
使这种方法起作用的关键是适当地定义 bi。b 样条提供了一种非常通用的方法:
一组 b 样条可以定义为若干个系数 n 和一个参数值 k(k = d + 1)。 b 样条很重要,因为它们提供了一种非常通用的方法来创建具有许多有用属性的函数(用于表示曲线)。用 n 个点和参数值为 k 的 B 样条创建的曲线为:
- 是 C(k−2)连续的;•
- 由 k−1 次多项式组成;•
- 具有局部控制-曲线上的任何位置仅取决于 k 个控制点(附近的 k 个控制点)
- 被点的凸包所包围;•
- 表现出如图 15.12 所示的变化递减特性。
使用 b 样条创建的曲线不一定要插值其控制点。
考虑如下形式的一组基函数:
这些函数中的每一个看起来都像一个位于 i 和 i + 2 之间的小三角形“帽子”,其峰值位于 i + 1。每个都是分段多项式,结点分别在 i, i + 1, i + 2 处。每个函数$b_{i,2}$都是一次(线性)b 样条。
注意,我们选择将 b 样条的下缘(它的第一个结)放在 i 处。因此,第一个 b 样条(i = 1)的第一个结在 1 处。对系数向量的 b 样条或元素的迭代从 1 到 n。当在程序中实现 b 样条时,它们通常被编号为 0 到 n - 1。
我们可以使用公式 15.15 从一组 n 个控制点创建一个函数,这些函数用于 bi 来创建受系数影响的“整体函数”。 如果我们要使用这些(k = 2) b 样条来定义整个函数,我们将定义一个分段多项式函数,它将在 t = k 和 t = n + 1 之间线性插值控制点。 请注意,(k = 2) b 样条插值其所有系数时,更高次的 b 样条在某些特定条件下会才这样做,我们将在 15.6.3 节中讨论。
在这个简单的例子中可以看出 b 样条的一些性质。我们将用 k(参数)和 n(系数或控制点的数量)将其写成一般形式:
- 每个 b 样条有 k + 1 个结点。•
- 每个 b 样条在其第一个结之前和最后一个结之后都是零。•
- 整体样条具有局部控制,因为每个系数仅乘以一个 b 样条,并且该 b 样条仅在 k + 1 节之间是非零的。•
- 整个样条有 n + k 个结点。(曲线可以向控制点外延伸,因为每个点至多由附近 k 个点插值而来,第一个点应该是由前 k/2 个控制点插值而来)
- 每个 b 样条是 C(k−2)连续的,因此整个样条是 C(k−2)连续的。•
- 对于结点 k 和 n + 1 之间的所有参数值,b 样条的集合和为 1(前后 k 个点的系数和不足 1)。这个范围是有 k 个非零的 b 样条。求和为 1 很重要,因为它意味着 b 样条是平移不变的:平移控制点将平移整个曲线(???)。
- 在它的每个结点之间,b 样条是一个次多项式= k−1。因此,整个曲线(将它们加在一起)也可以表示为任何相邻结点之间的单个 d 次多项式。
在这个例子中,我们选择了均匀间隔的结。稍后我们将考虑具有非均匀间距的 b 样条。 当结间距是均匀的,每个 b 样条是相同的,除了移位。具有均匀结间距的 b 样条有时称为均匀 b 样条或周期 b 样条。
前一节中列出的 b 样条的性质是有意为任意 n 和 k 编写的。稍后将提供构造 b 样条的一般过程,但首先,让我们考虑 k = 3 的另一种特殊情况。
它由二次项组成。它是 C1 连续的并且只在它张成的四个节范围内是非零的。
注意,一个二次 b 样条由三块组成,一块在结 1 和 2 之间,一块在结 2 和 3 之间,一块在结 3 和 4 之间。
为了使表达式更简单,我们将每个部分的函数写成适用于 0 到 1 的范围。
如果我们对 b 样条求和得到的整个函数求值,在任何时候,只有 k 个(这里是 3 个)样条的函数值是非零的。因此,我们可以把整个函数的任何部分看作是只有非零样条线的求和,在本例中 k=3:
如果我们有一组 n 个点,我们可以使用 B 样条来创建曲线。如果我们有七个点,我们将需要一组七个 B 样条。
上图显示了 k = 3 时的一组七个 B 样条。注意,有 n + k(10)个节点,B 样条的和在范围 k 到 n +1(节点 3 到 8)上为 1。
哪里有 7 个点???
由于三次多项式在计算机图形学中是非常普遍的,所以 k = 4 的 B—样条的特殊情况是也非常重要的。
三次 B 样条由四个三次多项式段定义。确定这些分段函数的一般过程等一会再讨论,首先结果是:
我们可以将结点 i + 3 和结点 i + 4 之间的整体曲线的函数写成参数 u 在 0 到 1 之间以及影响它的四个控制点的函数:
这可以用前几节的矩阵符号重写,给出的三次 b 样条的基矩阵:
与第 15.5 节中从约束中导出的矩阵不同,这个矩阵是由下一节中定义的一般 b 样条过程确定的多项式创建的。
b 样条的一个很好的特征是它们可以在任意 k > 1 时被定义。所以如果我们需要一条更平滑的曲线,我们可以简单地增加 k 的值。
到目前为止,我们已经说过 b 样条可以推广到任意 k > 1 和 n≥d,在我们展示如何实际计算这些 b 样条之前,要介绍最后一个推广。
b 样条对于任何非递减的结向量都有定义。
对于给定的 n 和 k, b 样条的集合(以及由它们的线性组合生成的函数)有 n + k 个结点。我们可以把这些结点的值写成一个向量,记作 t。对于均匀 b 样条,结点向量是[1,2,3,…, n + k]。然而,对于长度为 n + k 的任何结向量,只要其值是非递减的(例如,ti+1≥ti),都可以生成 b 样条(不一定要等间距)。
非均匀结间距之所以有用,主要有两个原因:
- 它使我们能够控制每个控制点影响的整体函数的范围,
- 它允许我们使用重复的结。例如,创建之间没有间隔的结),以便在这些点周围创建具有不同属性的函数。后者将在本节后面讨论。
为 b 样条指定结点值(控制点的位置)的能力类似于能够为插值样条曲线指定插值位置(设定插值点的位置)。它允许我们将曲线特征与参数值联系起来。通过指定非均匀结向量,我们指定 b 样条曲线的每个控制点影响的参数范围。记住,b 样条 i 只在结点 i 和结点 i + k 之间是非零的。因此,与它相关的控制点只影响这些参数值之间的曲线。
控制点离得越远,这些控制点的影响范围越大。
控制结值(控制点的位置)特别有用的一个地方是在序列开始附近插入或删除结。 为了说明这一点,考虑使用线性 b 样条(k = 2)定义的曲线。控制点 n=4,均匀结向量为[1,2,3,4,5,6]。该曲线由四个控制点控制,横跨参数范围 t = 2 至 t = 5。最后一个控制点位于曲线的“末端”(t = 5)。
如果我们在点集的中间插入一个新的点,我们将需要一个更长的结点向量。b 样条的局域性防止这种插入影响曲线末端的值。较长的曲线仍然会在其末端插入其最后一个控制点。 然而,如果我们选择保持统一的结间距,那么新的结向量将是[1,2,3,4,5,6,7]。曲线的末端将在 t = 6 处,最后一个控制点插入处的参数值将与插入前的参数值不同(原本是 0)。对于不均匀的结间距,我们可以使用结向量[1,2,3,3.5,4,5,6],以便曲线的末端不受变化的影响(线性 B-样条的影响范围只有两个点)。 具有非均匀结点间距的能力使得 b 样条的局域性不仅是一个几何性质,而且是一个代数性质。
现在我们介绍定义 b 样条的一般方法。给定系数数 n、b 样条参数 k 和结点向量 t(长度为 n + k)的值,下面的递归方程定义了 b 样条:
这个方程被称为 Cox-de Boor 递归式。它可以用来计算特定 b 样条基函数的特定值。然而,它更常应用于代数推导方程。
看看一个实际的例子,考虑如何推导公式。使用均匀的结向量[1,2,3,…]和 k=3,来产生 B-样条的基函数:
为了理解这个表达式等价于公式 15.17,我们注意到每个(k = 1) b 样条就像一个开关,只在特定的参数范围内打开。
例如,bi,1 只在 i 和 i + 1 之间是非零的。所以,如果 i≤t < i + 1,表达式中只有第一个(k = 1) b 样条是非零的,所以:
虽然 b 样条有许多很好的性质,但用它们定义的函数通常不能插值控制点(无法准确地进过控制点)。如果我们用它们来定义一条曲线,我们想要插入一个特定的点,这可能会很不方便。
我们在这里简要介绍了如何使用 b 样条插值一个特定的点。
使 b 样条插值其控制点的一种方法是重复结点。如果特定 b 样条的所有内部结点具有相同的值,则整个函数将插值(准确经过)该 b 样条的控制点。
重复结点的插值代价很高:它消除了 b 样条的平滑性以及由此产生的整体函数的光滑性。
然而,在样条的开始和结束,连续性不是问题,结点重复对于创建在终结点上插值的曲线很重要。
虽然第一个(或最后一个)结的值对于插值并不重要,但为了简单起见,我们使前(或后)k 个结具有相同的值来实现插值。
端点插值二次 b 样条如图所示。前两条和后两条 b 样条不同于均匀 b 样条。他们的表达式可以使用 Cox-de Boor 递归式计算:
尽管 B 样条提供了所有的通用性,但仍有一些函数不能用它们精确地表示。特别是,B 样条不能表示圆锥截面。为了表示这样的曲线,我们使用两个多项式的比值。非均匀 B 样条用于表示分子和分母。
最一般的形式是非均匀有理 B-样条,简称 NURBS。NURBS 将一个标量权重 hi 与每个控制点 pi 相关联,并对两者使用相同的 b 样条:
其中 b 是参数为 k 的 b 样条和结点向量 t。
NURBS 在几何建模中被广泛用于表示曲线和曲面,因为除了 b 样条的有用特性之外,NURBS 还提供了惊人的多功能性。
[!note] 贝塞尔曲线和 B-样条曲线 补充资料 补充资料:贝塞尔曲线和 B-样条曲线