计算机图形学基础-15-曲线
《Fundamentals of Computer Graphics》5th(计算机图形学基础/虎书),中文翻译。
第 15 章 Curves 曲线
15.1 曲线
直观地,将曲线视为可以用笔画出的东西。曲线是笔在一段时间内轨迹所经过的点的集合。虽然我们通常认为笔写在纸上(如二维空间中的曲线),但笔可以在三维空间中移动以生成空间曲线,或者你可以想象笔在其他种类的空间中移动。
从数学上讲,曲线的定义可以看作至少有两种方式:
- 在 维空间中某个区间的连续图像;
- 从一维空间到 维空间的连续映射。
这两种定义都始于一个时间范围的概念(笔描绘曲线的时间)。然而,它们之间存在着重要的差异:在第一种定义中,曲线是笔描绘的点的集合(图像),而在第二个定义中,曲线是时间和那些点的集合之间的映射。在本章中,我们使用第一种定义。
曲线是一个无限大的点集。曲线的点具有这样的属性,即除了一小部分只有一个相邻点的点(端点)外,任何一个点都有两个相邻点。有些曲线没有端点,要么是因为它们是无限长的(如一条直线),要么是封闭的(绕着自己打结)。
由于曲线“笔”很细(无限小),所以很难创建填充区域。虽然空间填充曲线是可能的(通过让它们无限次地折叠),但我们在这里不考虑这种数学怪异性。通常,我们将曲线视为物体的轮廓,而不是内部。
我们需要解决的问题是如何指定曲线 —— 给曲线一个名称或表示形式,以便我们可以在计算机上表示它。对于一些曲线,命名的问题很容易,因为它们具有已知的形状:线段、圆、椭圆弧等。一般的曲线没有“命名”形状,有时称为自由形 (free-form) 曲线。由于自由形曲线可以呈现几乎任何形状,因此它们更难规定。
从数学上讲,指定曲线的三种主要方式:
- 隐式曲线 (Implicit):表示法通过给出一个能够测试一个点是否在曲线上的过程来定义曲线上的点的集合。通常,隐式曲线表示法是由形如 的隐函数定义的,因此曲线是满足此方程的点的集合。请注意,隐函数 是一个标量函数(返回一个实数)。
- 参数曲线 (Parametric):表示法为自由参数到曲线上的点的映射提供了一种方式。也就是说,这个自由参数为曲线上的点提供一个索引。曲线的参数形式是将位置分配给自由参数值的函数。直观地说,如果你认为曲线是可以在纸上用笔画出的东西,那么自由参数就是时间,它在从我们开始画曲线到结束的时间间隔内变化。该曲线的参数函数告诉我们笔在任何时刻的位置: 。请注意,参数函数是一个向量值函数。这个例子是一个二维曲线,所以函数的输出是一个二维向量;在三维中,它将是一个三维向量。
- 生成或过程曲线 (Generative or procedural):表示法提供了可以生成不属于前两种类别的曲线上的点的过程。生成曲线描述的示例包括细分方案和分形。
请记住,曲线是一个点的集合。这些表示法给我们提供了指定这些集合的方式。任何曲线都有许多可能的表示方法。因此,数学家通常会仔细区分曲线和它的表示。在计算机图形学中,我们经常不太严谨,因为我们通常只涉及表示,而不是实际曲线本身。所以当有人说“一个隐式曲线”时,他们要么是指由某个隐函数表示的曲线,要么是指隐函数作为某个曲线的一种表示。这样的区别通常不重要,除非我们需要考虑同一曲线的不同表示。我们将在本章中考虑不同的曲线表示,因此我们会更加小心。当我们使用像“多项式曲线”这样的术语时,我们是指可以用多项式表示的曲线。
根据本章开头给出的定义,为了成为曲线,必须具有参数化表示。然而,许多曲线具有其他表示形式。例如,在 2D 中心点位于原点半径为 1 的圆可以写成隐式形式:
或者用参数形式表示为
对于给定的曲线来说,参数化形式不一定是最方便的表示形式。事实上,可能存在具有简单隐式或生成表示形式的曲线,但很难找到参数化表示。
曲线的不同表示法各有优缺点。例如,参数曲线易于绘制,因为我们可以对自由参数进行采样。一般来说,在计算机图形学中最常用的是参数化形式,因为它们更容易处理。我们的重点将放在曲线的参数化表示上。
15.1.1 参数化和重新参数化
参数曲线指的是由特定参数函数在某个特定区间内给出的曲线。更精确地说,参数曲线具有一个特定函数,该函数是一个从参数的区间映射而来的映射。通常情况下,让参数从 到 的单位区间运行会更方便。当自由参数在单位区间上变化时,我们通常将参数表示为 。
如果我们将参数曲线视为用笔画出的线条,我们可以将 视为笔第一次放在纸上的时间,时间单位为绘制曲线所需的时间( 是曲线的结束)。
曲线可以由将时间(在这些单位坐标中)映射到位置的函数来指定。基本上,曲线的规定是一个能够回答“笔在时间 时在哪里?”这个问题的函数。
如果我们有一个指定了区间 上曲线的函数 ,我们可以轻松地定义一个新函数 ,以在单位区间上指定相同的曲线。我们首先可以定义
然后
函数 和 都代表相同的曲线;然而,它们提供了曲线的不同参数化。创建现有曲线的新参数化过程称为重新参数化,而从旧参数到新参数的映射(在这个例子中为 )称为重新参数化函数 (reparameterization function)。
如果我们已经用某种参数化定义了一个曲线,那么无限多个其他参数化形式也存在(因为我们总是可以重新参数化)。拥有曲线的多个参数化方式很有用,因为它允许我们创建方便的参数化形式。但是,它也可能会导致问题,因为它使比较两个函数以确定它们是否表示相同曲线变得困难。
该问题的本质更为一般:自由参数(或时间元素)的存在会向我们对曲线的表示中添加一个看不见的、潜在的未知因素。当我们看完画出的曲线时,我们不一定知道时间。笔可能在整个时间间隔内以恒定速度移动,也可能缓慢开始并加速。例如,虽然 是参数空间的一半,但如果笔的运动从开始就缓慢并加速到结束,则它可能不是曲线的一半。考虑以下非常简单的曲线表示:
这三个函数都在单位区间上表示相同的曲线;然而,当 不是 或 时, 根据曲线的表示方法指代不同的点。
如果我们已经有了曲线的参数化,我们可以直接将其用作曲线的规定,也可以开发更方便的参数化。通常,自然参数化是以方便(或自然)的方式创建的,用于指定曲线,因此我们不必知道速度沿曲线如何变化。
如果我们知道笔以恒定速度移动,则自由参数的值具有更多的含义。在参数空间中间时即为曲线的一半。参数可以被认为是测量沿着曲线的长度。这种参数化称为弧长参数化,因为它们通过将沿着曲线的距离(称为弧长)映射到位置的函数来定义曲线。我们通常使用变量 来表示弧长参数。
从技术上讲,如果参数化的切线大小(即相对于参数的导数)恒定,则参数化是弧长参数化。表达为一个方程式:
计算沿曲线的长度可能会很棘手。通常情况下,它由导数的大小的积分来定义(直观地说,导数的大小是笔在沿着曲线移动时的速度)。因此,给定参数 的值,可以计算弧长距离 (从点 到点 沿曲线的弧长距离),如下所示:
其中 是定义具有自然参数化的曲线的函数。
使用弧长参数化需要能够解方程式(15.1)以得到 ,给定 。对于我们研究的许多曲线类型而言,这不能简单地通过封闭形式完成,必须进行数值求解。
一般来说,我们使用变量 表示自由参数,其范围为单位区间,使用 表示弧长自由参数,并使用 表示不是这两个变量之一的参数。
15.1.2 分段参数化表示
对于一些曲线,定义一个代表其形状的参数化函数很容易。例如,线、圆和椭圆都有简单的函数,可以用参数表示它们包含的点。对于许多曲线而言,找到指定形状的函数可能很困难。我们用的主要策略是分而治之:我们将曲线分成一些更简单的小块,每个小块都有一个简单的描述。
例如,考虑图 15.1 中的曲线。前两条曲线可以根据两个部分轻松地指定。在图 15.1(b) 的曲线中,我们需要两种不同的部分:一条直线段和一个圆。
图 15.1。(a) 可以轻松表示为两条线的曲线;(b) 可以轻松表示为一条线和一个圆弧的曲线;© 用五个线段逼近图 (b) 中的曲线。
要创建化合曲线的参数化表示(例如图 15.1(b) 中的曲线),我们需要让参数化函数在表示各部分的函数之间切换。如果我们将参数化函数定义在 的范围内,则图 15.1(a) 或 (b) 中的曲线可以定义为:
其中 是第一部分的参数化, 是第二部分的参数化,这两个函数都在单位区间内定义。
我们需要小心地定义 和 函数,以确保曲线的各部分相互贴合。如果 ,则我们的曲线部分不会连接并且不会形成单个连续曲线。
要表示图 15.1(b) 中的曲线,我们需要使用两种不同类型的部分:一条直线段和一个圆弧。为简单起见,我们可能更喜欢使用一种类型的片段。如果我们尝试仅使用一种类型的片段(如线段)来表示图 15.1(b) 中的曲线,则无法完全重现曲线(除非我们使用无限数量的片段)。虽然由线段制成的新曲线(如图 15.1© 所示)可能不是与图 15.1(b) 中完全相同的形状,但它可能足够接近我们的使用。在这种情况下,我们可能更喜欢使用简单的线段部分的简单性,而不是拥有更准确地表示形状的曲线。
此外,请注意随着我们使用越来越多的部分,我们可以获得更好的逼近。在极限情况下(使用无限数量的部分),我们可以完全表示原始形状。
使用分段表示的一个优点是,它允许我们在以下方面进行权衡:
- 我们所表示的曲线有多好地逼近我们试图表示的真实形状;
- 我们使用的部件有多复杂;
- 我们使用多少个部件。
因此,如果我们试图表示一个复杂的形状,那么我们可能会决定接受粗略的逼近,并使用少量简单的部分。要改善逼近度,我们可以选择使用更多的部件或更复杂的部件。
在计算机图形学实践中,我们倾向于使用相对简单的曲线部分(线段、弧或多项式部分)。
15.1.3 样条曲线 (Splines)
在计算机出现之前,绘图员想要画一条平滑的曲线时,会使用一条硬质金属杆,将其弯成所需的形状,用于描绘。由于金属只会弯曲而不是折叠,所以它会有一个平滑的形状。硬度意味着金属会尽可能少地弯曲以形成所需的形状。这种硬质金属杆被称为样条 (spline)。
数学家发现,绘图员的样条创建的曲线可以用分段多项式函数来表示。最初,他们使用术语"样条"来表示平滑、分段多项式函数。最近,该术语被用来描述任何分段多项式函数。我们更喜欢后一种定义。
对于我们而言,样条是一个分段多项式函数。这样的函数非常有用,用于表示曲线。
15.2 曲线属性
要描述一条曲线,我们需要提供关于其属性的一些信息。对于“命名”曲线,属性通常根据曲线类型进行特定描述。例如,要描述一个圆,我们可能会提供其半径和中心位置。对于椭圆,我们还可以提供其主轴的方向和轴长比率。但是,对于自由形式曲线,我们需要有更一般的属性集来描述单个曲线。
某些曲线的属性仅归因于曲线上的单个位置,而其他属性则需要知道整个曲线。为了感受这种差异,想象一下曲线是铁路轨道。如果你在雾天站在轨道上,你可以看出轨道是直线还是弯曲的,以及你是否处于端点。这些都是局部属性。您无法确定轨道是否为闭合曲线、是否相交或长度多长。我们称此类型的属性为全局属性。
研究几何对象(曲线和曲面)的局部性质被称为微分几何学。从技术上讲,要成为微分属性,这些属性存在一些数学限制(粗略地说,在铁路轨道的比喻中,您将无法使用 GPS 或罗盘)。我们不必担心这种区别,而是使用"局部属性"而不是"微分属性"的术语。
局部属性是描述曲线的重要工具,因为它们不需要对整个曲线有所了解。局部属性包括:
- 连续性 (continuity),
- 曲线上特定位置的位置,
- 曲线上特定位置的方向,
- 曲率 (curvature)(和其他导数)。
通常,我们想要指定曲线包括特定点。如果该点是曲线的一部分,则称曲线插值该点。如果存在某些参数 的值,使得 ,则函数 插值值 。我们将插值的位置(即 的值)称为站点。
15.2.1 连续性 (continuity)
理解曲线在两个参数片段相互连接的局部属性将非常重要。如果使用类似于方程 (15.2) 的等式定义曲线,则需要注意如何定义片段。如果 ,则曲线将被“断开” —— 我们将无法用一笔画连续地绘制曲线。我们称这种曲线片段拟合在一起的条件为连续性条件,因为如果条件成立,则可以将曲线作为连续的一部分进行绘制。由于本章开始时对“曲线”的定义要求曲线是连续的,因此技术上,“断裂的曲线”不是曲线。
除了位置之外,我们还可以检查片段的导数是否正确匹配。如果 ,则组合曲线在切换点处的第一导数将有一个突然变化;第一导数不连续。通常,我们说如果所有的导数都能够匹配,则曲线是 连续的。我们将位置本身表示为零阶导数,以便 连续性条件意味着曲线的位置是连续的,而 连续性条件意味着位置和第一导数是连续的。曲线的定义要求曲线是 连续的。
图 15.2 显示了一些连续性条件的示例。第一导数的不连续(曲线是 但不是 )通常是显著的,因为它显示一个尖角。第二个导数的不连续有时会在视觉上引人注目。高阶导数的不连续可能很重要,这取决于应用程序。例如,如果曲线表示运动,则第二个导数的突然变化是明显的,因此第三个导数的连续性通常很有用。如果曲线将有流体流过它(例如,如果它是飞机翼或船体的形状),则第四或第五导数的不连续可能会引起湍流。
图 15.2 显示了两个曲线片段之间各种类型的连续性的示例。
我们刚刚介绍的连续性类型()通常称为参数连续性,因为它取决于两个曲线片段的参数化。如果每个片段的“速度”不同,则它们将不连续。对于我们关心曲线形状而不是其参数化的情况,我们定义几何连续性,要求在等效地参数化曲线时曲线片段的导数匹配(例如,使用弧长参数化)。直观地说,这意味着相应的导数必须具有相同的方向,即使它们具有不同的大小。
因此,如果 连续性条件是:
则 连续性条件将是:
其中 是某个标量值。一般来说,几何连续性比参数连续性要少限制。除非参数导数为零,否则 曲线也是 曲线。
15.3 多项式片段
计算机图形学中最广泛使用的曲线表示方法是通过组合由多项式定义的基本元素 —— 称为多项式片段。例如,一条线段由一个线性多项式给出。在 15.3.1 节中,我们给出了一个正式的定义,并解释了如何组合多项式片段。
15.3.1 多项式表示法
多项式是以下形式的函数:
其中, 被称为系数,如果 ,则 被称为多项式的次数。 我们还可以用公式 (15.4) 将式子(15.3)写成如下的形式:
我们称这个多项式为规范形式。
我们可以将规范形式推广到
其中 是一个多项式。 我们可以为不同的应用程序选择这些多项式,使它们具有方便的形式,并称它们为基函数或混合函数(参见第 15.3.5 节)。在公式 (15.4) 中, 是公式 (15.5) 中的 。如果正确选择了基函数集,则任何次数为 的多项式都可以通过适当选择 来表示。
规范形式并不总是具有方便的系数。出于实际目的,在整个本章中,我们将找到一组基础函数,使得系数是控制由多项式函数表示的曲线的方便方式。
要指定嵌入两个维度的曲线,可以指定两个关于 的多项式:一个关于 如何随 变化,另一个关于 如何随 变化;或者指定一个单独的多项式,其中每个 是一个二维点。对于任何 维空间中的曲线都存在类似的情况。
15.3.2 线段
为了介绍分段多项式曲线表示的概念,我们将讨论线段。在实践中,线段是如此简单,以至于数学推导似乎过多。然而,通过理解这种简单情况,在移动到更复杂的多项式时,事情将变得更容易。
考虑连接点 和 的线段。我们可以将该线段在单位域上的参数函数写成
通过将其写成向量形式,我们隐藏了点的维度和我们正在分别处理每个维度的事实。例如,如果我们正在使用 2D,则可以创建单独的方程:
我们指定的线由两个端点确定,但从现在开始,我们将坚持向量符号,因为它更加简洁。我们将控制参数向量称为 ,控制点为控制参数的向量, 中的每个元素都是一个控制点。
虽然通过其端点的位置描述一条线段是显而易见且通常方便的,但还有其他描述一条线段的方法。例如,
- 线段中心的位置、方向和长度;
- 一个端点的位置及相对于第一个端点的第二点的位置;
- 线段中心的位置和一个端点。
很明显,给定一种线段描述的方式,我们可以切换到另一种。
描述线段的不同方法是使用多项式的规范形式(如 15.3.1 节中所讨论的):
任何线段都可以通过指定 和 或端点 ( 和 ) 来表示。通常更方便指定端点,因为我们可以从端点计算出其他参数。
将规范形式写成向量表达式,我们定义一个向量 ,它是 的幂的向量:
这样公式 (15.4) 就可以写成
这个向量符号将使得在不同形式的曲线之间转换更容易。
公式 (15.8) 通过简单形式的多项式的系数集合来描述曲线片段。我们称这种表示法为规范形式。我们用 表示规范形式的参数。
虽然在数学上很简单,但规范形式并不总是指定曲线的最方便的方式。例如,我们可能更喜欢通过其端点的位置来指定线段。如果我们想要定义 为线段的开始(当 时,线段位于什么位置),并且 为线段的结束(当 时,线段位于什么位置),我们可以写成
我们可以解这些方程式得到 和 :
多项式的矩阵形式
虽然第一个例子足够简单,但是对于更复杂的例子,将公式 (15.9) 写成形式
会更容易。或者,我们可以写成
其中我们称 为约束矩阵。如果有向量的点让你困扰,您可以分别考虑每个维度(例如 是 或 ,并且相应地处理 )
通过找到 的逆来解方程(15.10)以求得 。我们把这个逆矩阵记作 ,即基矩阵。基矩阵非常方便,因为它告诉我们如何在便捷的参数 和规范形式 之间进行转换,从而给我们评估曲线 提供了一种简单的方法。
只要参数定义中没有非线性项,我们就可以为想要的任何曲线找到一个基矩阵。非线性定义参数的示例包括线段的长度和角度。
现在,假设我们想将线段参数化,使得 是一半的位置(),而 是结束点()。为了推导这种参数化的基矩阵,我们设置:
因此,
并且
15.3.3 超越线段
线段如此简单,以至于找到基础矩阵是微不足道的。然而,这对于更高次数的曲线是很好的练习。首先,让我们考虑二次曲线(二次曲线)。规范形式(公式 (15.4))的优点是,它可以通过让 成为一个更大的数字,用于这些更复杂的曲线。
二次曲线(二次多项式)有三个系数,、 和 。这些系数不方便描述曲线的形状。然而,我们可以使用相同的基础矩阵方法来设计更方便的参数。如果我们知道 的值,公式 (15.4) 变为参数的线性方程,上一节的线性代数仍然有效。
假设我们想要通过 、和 的位置来描述我们的曲线。将适当的值输入公式 (15.4):
因此约束矩阵为
基础矩阵是
还有一种额外的约束(或参数)类型,有时指定它更方便:曲线在特定值处(相对于其自由参数)的导数。直观地说,导数告诉我们曲线如何改变,因此第一导数告诉我们曲线的方向,第二导数告诉我们曲线正在快速改变方向等。稍后我们将看到指定导数为什么有用的例子。
对于二次曲线,
导数很简单:
和
或者,更一般地,
例如,考虑一个这样的情况,我们希望通过其中心 (u=0.5) 的位置、一阶导数和二阶导数来指定二次曲线片段。
约束矩阵是
基础矩阵是
15.3.4 三次基础矩阵
在图形学中,三次多项式很受欢迎(见第 15.5 节)。各种形式的三次导数的推导就像我们已经在本节中看到的一样。我们将通过另一个例子进行练习。
一种非常有用的三次多项式形式是 Hermite 形式,在这种形式中,我们在开始和结束时指定位置和一阶导数,即,
因此约束矩阵为
基础矩阵为
我们将在第 15.5.2 节讨论 Hermite 三次样条曲线。
15.3.5 混合函数
如果我们知道基础矩阵 ,我们可以将其乘以参数向量 u,得到一个函数向量
注意,我们用 表示这个向量,以强调它的值取决于自由参数 。我们称 的元素为混合函数,因为它们指定如何混合控制点向量的值:
重要的是要注意,在选择 的一个值时,公式 (15.11) 是一个线性方程,指定控制点的线性混合 (linear blend)(或加权平均)。无论双函数内隐藏了什么程度的多项式,这都是正确的。
混合函数为描述曲线提供了一个很好的抽象。任何类型的曲线都可以表示为其控制点的线性组合,其中这些权重被计算为自由参数的任意函数。
15.3.6 插值多项式
一般地, 次多项式可以插入 个值。如果我们给出一个要插值的点向量 ,和一个递增参数值向量 ,,我们可以使用前面的章节中描述的方法来确定一个 基础矩阵,该矩阵给我们一个函数 ,使得 。对于任何给定的向量 ,我们需要设置并解决一个 的线性系统。这为我们提供了一组执行插值的 个基础函数:
这些插值基础函数可以用其他方式推导出来。其中一种特别优雅的定义方式是 Lagrange 形式:
有比 Lagrange 形式更计算有效的表达插值基础函数的方法(有关详细信息,请参见 De Boor(1978))。
插值多项式提供了定义插值一组点的曲线的机制。图 15.3 显示了一些示例。虽然可以创建单个多项式来插值任意数量的点,但在计算机图形学中,我们很少使用高阶多项式表示曲线。取而代之的是,使用插值样条(分段多项式函数)。这其中的原因在第 15.5.3 节中进行了考虑。
图 15.3。多点插值多项式。在 (a) 和 (b) 中,曲线在点之间包含额外的波动和超量。在 © 中添加第六个点时,由于插值多项式的非局部特性,它完全改变了曲线的形状。
15.4 把部分拼起来
现在我们已经看到如何制作多项式曲线的单个部分,我们可以考虑如何将这些部分组合起来。
15.4.1 结节点
图 15.4。 (a) 两条线段连接三个点;(b) 每个点的混合函数在右侧绘制。
分段参数化函数的基本思想是每个部分只在某个参数范围内使用。例如,如果我们想定义一个具有两个分段线性线段连接三个点的函数(如图 15.4(a) 所示),我们可以定义
其中 和 是每个线段的函数。请注意,我们已经为每个部分重新调整了参数,以便于将它们的方程写成
对于我们分段函数中的每个多项式,都有一个起始点和结束点。多项式开始或结束的位置称为结点。对于 Equation(15.13)中的示例,结点的值为 0、0.5 和 1。
我们还可以将分段多项式函数写成一组基础函数的和,每个函数都乘以一个系数。例如,我们可以将 Equation(15.13)中的两个线段重写为
其中函数 定义为
b2 和 b3 类似地定义。这些函数在图 15.4(b) 中绘制出来。
多项式函数的结点是用于创建它的所有部分的结点的组合。结节点向量是按升序存储所有结节点值的向量。
请注意,在本节中,我们使用了两种不同的机制来组合多项式部件:为参数的不同范围使用独立的多项式部件,并混合分段多项式函数。
15.4.3 组合部分
如果我们想从两个线段制作一个单一的曲线,我们需要确保第一个线段的末端与下一个线段的开头位于同一位置。有三种连接这两个线段的方式(按简单性顺序):
- 将线段表示为其两个端点,然后将相同的点用于两者。我们称之为共享点方案 (shared-point scheme)。
- 每当第一个线段的参数发生变化时,将第一个线段的末端值复制到第二个线段的开头。我们称之为依赖方案 (dependency scheme)。
- 为连接编写显式方程,并通过数字方法在其他参数更改时执行它。
尽管简单的方案更可取,因为它们需要较少的工作,但它们也对线段的参数化方式施加了更多的限制。例如,如果我们想使用线段的中心作为参数(以便用户可以直接指定),我们将使用每个线段的开头和线段的中心作为它们的参数。这将迫使我们使用依赖方案。
请注意,如果我们使用共享点或依赖方案,则控制点的总数小于 ,其中 是线段的数量, 是每个线段的控制点数;独立部分的许多控制点将被计算为其他部分的函数。请注意,如果我们对行使用共享点方案(每个线段使用其两个端点作为参数,并与其邻居共享内部点),或者如果我们使用依赖方案(例如第一个端点和中点的示例),我们最终得到 个控件,表示 线段曲线。
依赖方案有一个更严重的问题。曲线中的一个位置的变化可能会传播到整个曲线。这称为缺乏局部性。局部性意味着,如果您移动曲线上的一点,它只会影响局部区域。局部区域可能很大,但是它将是有限的。如果曲线的控制没有局部性,则更改控制点可能会影响无限远的点。
要在操作中看到局部性和缺乏局部性,请考虑两条线段链,如图 15.5 所示。一个链具有其部分由其端点参数化,并使用点共享来保持连续性。另一个链通过端点和中点对其部分进行参数化,并使用依赖传播来将线段连接在一起。这两个线段链可以表示相同的曲线:它们都是一组 个相连的线段。但是,由于局部性问题,共享端点形式可能更方便用户。请考虑更改每个链中第一个控制点的位置。对于共享端点版本,仅第一个线段将更改,而对于中点版本,所有线段都将受到影响,如图 15.5 所示。实际上,对于在共享端点版本中移动的任何点,最多只有两个线段会更改。在中点版本中,移动的控制点后面的所有线段都将更改,即使链是无限长的。
图 15.5。具有局部控制的线段链和非局部控制的线段链。
在这个例子中,依赖传播方案是没有局部控制的方案。这并不总是正确的。有一些直接共享方案不是局部的,而有些传播方案是局部的。
我们强调,局部性是控制问题的方便性问题。虽然每次整个曲线都更改是不方便的,但可以对曲线进行相同的更改。它只需要同时移动多个点。
15.5 立方体
在图形学中,当我们使用分段多项式表示曲线时,通常使用线段或立方体多项式来表示部分。以下是立方体在计算机图形学中受欢迎的原因:
- 分段立方体多项式允许 连续性,通常对于大多数视觉任务足够。二次曲线提供的 平滑度通常不足。高阶多项式提供的更大平滑度很少重要。
- 立方曲线为一组点提供最小曲率插值器。也就是说,如果您有 个点,并定义通过它们的“最平滑”曲线(即在其长度上具有最小曲率的曲线),则该曲线可以表示为具有 个段的分段立方体。
- 立方体多项式具有美好的对称性,其中可以在开头和结尾指定位置和导数。
- 立方体多项式在计算中具有良好的数字问题和平滑度之间的权衡。
请注意,我们不必使用立方体;它们只是平滑度和复杂度之间一个很好的权衡。不同的应用程序可能具有不同的权衡。我们专注于立方体,因为它们是最常用的。
立方体多项式的规范形式是
正如我们在 15.3 节中讨论的那样,这些规范形式系数不是一种方便描述立方体部分的方式。
我们寻找立方体多项式的形式,其系数是控制由立方体表示的结果曲线的一种便捷方式。其中一个主要便利将是提供方法来确保部件的连接性和段之间的连续性。
每个立方体多项式部件需要四个系数或控制点。这意味着对于具有 个部件的分段多项式,如果未进行片段之间的共享或依赖,则可能需要多达 个控制点。更经常地,每个段的某个部分都是共享的或取决于相邻段,因此控制点的总数要低得多。此外,请注意控制点可能是曲线的位置或导数。
不幸的是,没有单一的“最佳”分段立方体表示。不可能有一种分段多项式曲线表示,具有所有以下理想特性:
- 曲线的每个部分都是立方体;
- 曲线插值控制点;
- 曲线具有局部控制;
- 曲线具有 连续性。
在这些属性中,我们可以有任何三个,但不能全部四个;有表示形式具有任何三个组合。在本书中,我们将讨论不插值其控制点(但具有局部控制且具有 )的立方体 B 样条;Cardinal 样条和 Catmull-Rom 样条插值其控制点并提供局部控制,但不具备 ;以及插值且具有 的自然立方体,但没有局部控制。
立方体的连续性属性是指段之间(在结点上)的连续性。立方体部件本身在其导数中具有无限连续性(到目前为止我们一直在谈论连续性的方式)。请注意,如果您有许多控制点(或结点),则曲线可能会变得波动,这可能看起来不“平滑”。
自然立方体是一种分段立方体曲线,可以创建 曲线。为此,我们需要在每个部分的开头指定位置和第一和第二导数(以确保与前一个部分的末尾相同)。请注意,每个曲线部分都从链中的前一个曲线接收三个参数中的一个。这些 连续的立方体链有时称为自然立方体样条。
对于自然立方体的一个部分,我们需要通过其端点和开始点处的第一和第二导数来参数化立方体。因此控制点为
因此,约束矩阵为
基础矩阵为
给定一组 个控制点,自然立方体样条具有 个立方体部分。第一段使用控制点定义其开始位置、结束位置和开始时的第一和第二导数。依赖关系方案将第一段末端的位置和第一和第二导数复制以在第二段中使用。
自然立方体样条的缺点是它们不是局部的。任何一个部分的任何更改可能需要整个曲线发生变化(至少在更改后的部分)。更糟糕的是,自然立方体样条往往不具备良好的条件:曲线开头的小变化会导致后面的大变化。另一个问题是我们只能控制曲线在其开始处的导数。曲线开始之后的段确定它们的导数从它们的起始点确定。
Hermite 立方体多项式在 15.3.4 节中介绍过。立方体 Hermite 样条的一段允许指定两个端点的位置和第一导数。通过使用相同的值来表示一段的结束位置和下一段的开始位置,可以将几段链接成 样条。
给定一组 个控制点,其中每个其他控制点都是导数值,则 Hermite 立方体样条包含(n-2)/ 2 个立方体部分。样条插值点,如图 15.6 所示,但只能保证 连续性。
Hermite 立方体很方便,因为它们提供形状的局部控制,并提供 连续性。但是,由于用户必须指定位置和导数,因此必须提供导数的特殊接口。一种可能性是向用户提供表示导数向量结束的点,如果将它们“放”在位置点上,则可以表示该点。
15.5.3 Cardinal 立方体样条
Cardinal 立方体样条是一种由立方多项式部分组成的 插值样条。给定 个控制点,Cardinal 立方体样条使用 个立方多项式部分来插值其除第一个和最后一个之外的所有点。
Cardinal 样条具有一个称为"张力 (tension)“的参数,该参数控制其插值点之间曲线的"紧密程度”。张力是一个在 范围内的数字,控制着曲线向下一个控制点弯曲的程度。对于重要的特殊情况 ,这些样条被称为 Catmull-Rom 样条。
每个 Cardinal 样条段使用四个控制点。对于段 ,所使用的点为 ,, 和 ,因为相邻段共享三个点。每个段从其第二个控制点开始,以其第三个控制点结束。曲线起始处的导数由第一个和第三个控制点之间的向量确定,而曲线末端的导数由第二个和第四个点之间的向量给出,如图 15.7 所示。
图 15.7. Cardinal 立方体样条段插值其第二个和第三个控制点( 和 ),并使用其他点来确定曲线起始和结束处的导数。
张力参数调整导数的缩放程度。具体而言,导数按 进行缩放。因此,立方体的约束为
解这些方程以确定控制点(定义 s = (1 - t)/2)可得:
这产生了 Cardinal 矩阵
由于第 个段的第三个点是第 个段的第二个点,相邻的 Cardinal 样条段相连。同样,使用相同的点来指定每个段的第一导数,从而提供 连续性。
Cardinal 样条很有用,因为它们提供了一种简单的方式来插值具有 连续性和局部控制的点集。但是它们只能实现 连续性,因此有时会出现"皱褶"。张力参数在插值点之间发生的情况上提供了一些控制,如图 15.8 所示,其中显示了通过一组点的一组 Cardinal 样条。这些曲线使用相同的控制点,但它们使用不同的张力参数值。请注意,第一个和最后一个控制点未被插值。
图 15.8 带有不同张力参数 值的七个控制点的 Cardinal 样条。
给定一组 个要插值的点,您可能会想知道为什么我们更喜欢使用 Cardinal 立方体样条(即 个立方形块)而不是像第 15.3.6 节中描述的单个 次多项式。以下是一些插值多项式的缺点:
- 插值多项式往往会超出要插值的点,如图 15.9 所示。随着点数的增加,这种过冲会变得越来越严重。而 Cardinal 样条在点之间的表现往往比较好。
- 插值多项式的控制不是局部的。更改样条开头的点会影响整个样条。Cardinal 样条是局部的:样条上的任何位置最多受到其四个相邻点的影响。
- 插值多项式的评估不是局部的。评估多项式上的一个点需要访问所有的点。评估分段三次函数上的一个点需要进行固定数量的计算,无论点的总数有多大。
图 15.9 插值九个控制点(用小十字标记),厚橙色线显示插值多项式,细线显示 Catmull-Rom 样条。后者由七个立方体段组成,每个段以交替的蓝色色调显示。
随着插值样条中的点数增加,还存在其他各种数字和技术问题。有关更多信息,请参阅 De Boor(2001)。
Cardinal 样条的缺点是它不插值第一个或最后一个点,但这可以通过在序列的任一端添加额外的点来轻松解决。Cardinal 样条也不像连续性那么好,在节(即节点)上只提供 连续性。
15.6 曲线逼近 (Approximating Curves)
看起来控制曲线的最简单方法是为其指定一组要插值的点。但实际上,插值方案通常具有不良属性,因为它们具有较少的连续性并且在插值点之间没有任何控制。通常更喜欢仅逼近点的曲线方案。采用逼近方案时,控制点影响曲线的形状,但不完全指定曲线。虽然我们放弃了直接指定曲线要穿过的点的能力,但我们获得了更好的曲线行为和局部控制。如果需要插值一组点,则可以计算控制点的位置,使曲线穿过这些插值点。
计算机图形学中最重要的两种逼近曲线类型是 Bézier 曲线和 B-spline 曲线。
15.6.1 Bézier 曲线
Bézier 曲线是计算机图形学中自由形曲线的最常见表示之一。该曲线以开发者之一 Pierre Bézier 命名。Bézier 曲线具有一个有趣的历史,多个独立团队同时开发了它们。
Bézier 曲线是逼近其控制点的多项式曲线,可以是任何次数的多项式。次数为 的曲线由 个控制点控制。该曲线插值其第一个和最后一个控制点,并且其形状直接受其他点的影响。
通常,通过连接多条低次数的 Bézier 曲线来制作复杂的形状,在计算机图形学中,立方体()Bézier 曲线通常用于此目的。许多流行的插图程序,例如 Adobe Illustrator,以及字体表示方案,例如在 Postscript 中使用的方案,都使用立方体 Bézier 曲线。 Bézier 曲线在计算机图形学中非常受欢迎,因为它们易于控制,具有许多有用属性,并且有非常高效的算法可用于处理它们。
构造 Bézier 曲线的方式如下:
- 曲线以 和 分别插值第一个和最后一个控制点。
- 曲线在其开头(末尾)的第一导数由第一个和第二个(倒数第二个和最后一个)控制点之间的向量确定。这些导数由与这些点之间的向量缩放的曲线次数给出。
- 曲线开头(末尾)的更高阶导数取决于曲线开头(末尾)的点。第 个导数取决于前面(后面)的 个点。
例如,考虑如图 15.10 所示的三次 Bézier 曲线。该曲线有四个 个控制点。它从第一个控制点()开始,并以最后一个控制点()结束。在曲线的开头处,第一导数与第一个和第二个控制点之间的向量成比例()。具体而言,。同样,曲线结尾处的第一导数由 给出。可以从控制点 、 和 确定曲线开头的第二导数。
图 15.10。一个立方 Bézier 曲线由四个点控制。它插值第一个和最后一个点,并且开头和末尾的导数是第一个两个(或最后两个)点之间向量的三倍。
利用前面段落中关于 Bézier 立方体的事实,我们可以使用节 15.5 的方法为它们创建参数化函数。开头和结尾的插值和导数定义为
这可以解决基矩阵
然后写成
或者
其中 ,3 是三次 Bézier 混合函数:
幸运的是,Bézier 曲线的混合函数具有适用于所有次数的特殊形式。这些函数称为伯恩斯坦基多项式,具有一般形式
其中 是 Bézier 曲线的阶数, 是介于 和 (含)之间的混合函数编号。 是二项式系数:
给定控制点 的位置,评估 阶(具有 个控制点)Bézier 曲线的函数为
图 15.11 显示了一些 Bézier 段。
图 15.11。阶数为 2 至 6 的各种 Bézier 段。控制点用叉形图示,控制多边形(连接控制点的线段)也显示出来。
Bézier 段具有几个有用的属性:
- 曲线由控制点的凸包所限定。
- 任何直线与曲线相交的次数不超过其与连接控制点的线段集合相交的次数。这称为变差减小性质。该属性如图 15.12 所示。
- 曲线是对称的:将控制点的顺序反转可产生相同的曲线,只是参数化反向。
- 曲线是仿射不变的。这意味着平移、缩放、旋转或倾斜控制点与在曲线本身上执行这些操作是一样的。
- 有很好的简单算法可用于评估和将 Bézier 曲线细分为自身就是 Bézier 曲线的片段。因为使用稍后描述的算法有效地进行细分,所以可以使用分治法来创建有效的算法,用于重要任务,例如渲染 Bézier 曲线、使用线段近似它们以及确定两条曲线之间的交点。
图 15.12。Bézier 曲线的变差减小性质意味着曲线不会比其控制多边形更多地穿过一条直线。因此,如果控制多边形没有“抖动”,曲线也不会有。
当将 Bézier 段连接在一起形成样条时,通过共享端点创建段之间的连通性。然而,导数的连续性必须通过定位其他控制点来创建。这为 Bézier 样条的用户提供了对平滑度的控制。对于 连续性,第一个曲线的倒数第二个点和第二个曲线的第二个点必须与相等的端点共线。对于 连续性,点之间的距离也必须相等。如图 15.13 所示。通过适当地定位更多的点可以创建更高阶的连续性。
图 15.13。两个 Bézier 段连接形成一个 样条,因为第一个段的最后两个点之间的向量等于第二个段的前两个点之间的向量。
几何直觉 Bézier 曲线
Bézier 曲线可以从几何原理上推导出来,也可以从上述代数方法中描述。我们概述几何原理,因为它们提供了有关 Bézier 曲线如何工作的直觉。
想象一下,我们有一组控制点,我们想要创建一个平滑曲线。简单地用直线连接这些点(形成控制多边形)将导致非平滑的结果。它将具有锐角。我们可以想象通过去除尖角“平滑”该多边形,得到一个更平滑的新多边形,但在数学意义上仍然不是“平滑”的(因为曲线仍然是一个多边形,因此只能达到 )。我们可以重复这个过程,每次都得到一个更平滑的多边形,如图 15.14 所示。在极限情况下,即如果我们无限次重复这个过程,我们将获得一个 平滑曲线。
图 15.14。二次 Bézier 的细分过程。每个线段被划分为两半,并连接这些中点(蓝色点和线)。内部控制点移动到新线段的中点(橙色点)。
我们所做的尖角切割定义了一个细分方案。也就是说,我们已经定义了一种通过将较简单的曲线分成较小部分(例如,将其细分)的过程来定义曲线的方法。所得到的曲线是通过无限次应用该过程而实现的极限曲线。如果定义的细分方案正确,则结果将是平滑曲线,并且具有参数形式。
让我们考虑将角落切割应用于单个角落。给定三个点(、、),如图 15.15 所示,我们重复地“切掉角”。在每个步骤中,我们将每个线段分成两半,连接中点,然后将角点移动到新线段的中点。请注意,在此过程中,引入了新的点,移动了一次,然后对于任何剩余的迭代都保持在这个位置。端点从不移动。
图 15.15。通过反复切除多边形的角,我们逐渐接近平滑曲线。
如果我们将 的“新”位置计算为中点的中点,则得到表达式
实际上,该构造方法适用于每个线段上沿着每个距离的其他比例。如果我们让 u 是沿着我们放置中间点的每个线段开始和结束之间的距离,我们可以将此表达式重写为
重新排列项得到二次 Bézier 函数:
de Casteljau 算法
Bézier 曲线的一个好处是有一种非常简单且通用的方法来计算和细分它们。该方法称为 de Casteljau 算法,使用一系列线性插值来计算任意阶 Bézier 曲线上的位置。它是前一节描述的细分方案的推广。
de Casteljau 算法首先通过连接相邻的点对之间的直线,并找到在这些直线上给定 插值的点,从而得到 个点。然后将这些点用直线连接起来,这些线段再次通过 进行插值,得到 个点。这个过程重复进行,直到只剩下一个点为止。该过程的示例如图 15.16 所示。
图 15.16。用于三次 Bézier 的 de Casteljau 算法的示例。左侧图像显示了 的构造方式。右侧图像显示了 0.25、0.5 和 0.75 的构造方式。
计算 Bézier 段上的点的过程还提供了一种在该点处将段分割的方法。在 de Casteljau 算法期间计算的中间点形成新的,较小段的新控制点,如图 15.17 所示。
图 15.17。使用 de Casteljau 算法对三次 Bézier 段进行细分。最初的点(黑色钻石 A、B、C 和 D)被线性插值为蓝色圆圈(AB、BC、CD),这些蓝色圆圈被线性插值为橙色圆圈(AC、BD),这些橙色圆圈被线性插值为三次 AD 上的点。这个过程也将控制点为 A、B、C、D 的 Bézier 段分成了具有控制点 A、AB、AC、AD 和 AD、BD、CD、D 的两个 Bézier 段。
存在一个良好的算法来细分 Bézier 曲线使得分治算法成为可能。例如,在绘制 Bézier 曲线段时,很容易检查曲线是否接近直线,因为它受到其凸包的限制。如果曲线的控制点都接近共线,曲线可以绘制为一条直线。否则,曲线可以被分成较小的片段,并重复该过程。类似的算法可用于确定两条曲线之间的交点。由于存在这样的算法,其他曲线表示通常会被转换为 Bézier 形式进行处理。
15.6.2 B 样条 (B-splines)
B 样条提供了一种用具有 d 次多项式的曲线来近似 个点并具有 连续性的方法。与前一节中讨论的贝塞尔样条不同,B 样条允许生成任何所需连续度(几乎达到点数)。因此,在计算机图形学中,B 样条是指定非常平滑的曲线(高连续度)的首选方法。如果我们想通过任意数量的点得到一个 或更高的曲线,则使用 B 样条可能是正确的方法。
我们可以使用 B 样条基函数的线性组合来表示曲线。由于这些基函数本身就是样条,我们将它们称为基样条或简称 B 样条。每个 B 样条或基函数由一组 个 次多项式组成。B 样条方法提供了定义这些函数的通用过程。
术语“B 样条”特指其中一种基函数,而不是由一组 B 样条的线性组合创建的函数。然而,在计算机图形学中对该术语的使用存在不一致性。通常,“B 样条曲线”是指由 B 样条的线性组合表示的曲线。
在 15.3.1 和 15.3.5 节中已讨论将多项式表示为其他多项式的线性组合的思想。在 15.4.1 节中,已经展示了将样条表示为其他样条的线性组合。事实上,给出的例子是 B 样条的一个简单案例。
将函数表示为其他函数的线性组合的一般符号是:
其中 是系数, 是基函数或 B 样条。如果系数是点(例如,2 或 3 个向量),我们称它们为控制点。使这种方法成功的关键是适当地定义 。B 样条提供了非常通用的方法来实现这一点。
可以为系数 和参数值 定义一组 B 样条曲线。 的值比用于生成 B 样条的多项式的次数高 1。即 。
B 样条很重要,因为它们提供了一种非常通用的创建具有许多有用属性的函数(对于表示曲线很有用)的方法。使用参数值为 的 B 样条制作的 个点的曲线:
- 具有 连续性;
- 由次数为 的多项式组成;
- 具有局部控制性 —— 曲线上任何一个点只依赖于 个控制点;
- 受到点的凸包的限制;
- 展现了图 15.12 所示的变化减少特性。
使用 B 样条创建的曲线不一定插值其控制点。
我们将首先查看一个特定的简单案例来介绍这些概念,然后推广这些方法并说明它们的有趣之处。由于计算 B 样条的方法非常通用,因此我们延迟介绍,直到展示这些推广的含义。
均匀线性 B 样条
考虑以下形式的基函数集:
这些函数中的每一个看起来像是在 和 之间有一个小三角形的“帽子”,其顶点在 处。每个函数都是分段多项式,其节点为 , 和 。图 15.18 中展示了其中两个的图形。
这些函数 中的每一个都是一阶(线性)B 样条。由于我们稍后将考虑其他参数值的 B 样条,因此在下标中用 2 表示。
注意我们选择将 B 样条的下边缘(即其第一个节点)放在 i 处。因此,第一个 B 样条()的第一个节点就是 。对 B 样条或系数向量元素进行迭代时是从 到 (见式 15.15)。实现 B 样条时,以及在许多其他关于它们的讨论中,它们通常是从 到 编号的。
我们可以使用式 15.15 中的这些函数来创建一个由 个控制点组成的函数,其中这些函数用于创建受系数影响的“整体函数”。如果我们要使用这些()B 样条来定义整体函数,那么我们将定义一个分段多项式函数,它在 和 之间线性插值系数 。请注意,虽然()B 样条插值其所有系数,但更高次数的 B 样条只有在某些特定条件下才能做到这一点,我们将在 15.6.3 节中讨论这些条件。
在这个简单的案例中可以看到一些 B 样条的性质。我们将使用参数 和系数或控制点的数量 来写出这些性质:
- 每个 B 样条有 个节点。
- 每个 B 样条在其第一个节点之前和最后一个节点之后为零。
- 整体样条具有局部控制,因为每个系数仅乘以一个 B 样条,而且这个 B 样条只在 个节点之间非零。
- 整体样条有 个节点。
- 每个 B 样条都是 连续的,因此整体样条也是 连续的。
- B 样条集对于所有处于 和 之间的参数值求和等于 1。这个范围是存在 个非零 B 样条的地方。总和为 很重要,因为它意味着 B 样条是平移不变的:平移控制点会平移整个曲线。
- 在其每个节点之间,B 样条都是一个次数为 的单一多项式。因此,整体曲线(将它们相加)也可以在任何相邻节点之间表示为单一的 次多项式。
在这个例子中,我们选择了均匀间隔的节点。稍后我们将考虑非均匀间隔的 B 样条。当结点间距是均匀的时,每个 B 样条除了平移之外都是相同的。具有均匀节距的 B 样条有时被称为均匀 B 样条或周期 B 样条。
均匀二次 B 样条
在前一节列出的 B 样条属性是故意为任意 和 编写的。稍后将提供构造 B 样条的一般过程,但首先让我们考虑另一个特定情况,即 。
B 样条 b2,3 如图 15.19 所示。它由二次片段(次数为 2)组成,共有三个。它是 连续的,只在它跨越的四个节点内非零。请注意,二次 B 样条由三个部分组成,其中一个在结点 1 和 2 之间,一个在结点 2 和 3 之间,另一个在结点 3 和 4 之间。在第 15.6.3 节中,我们将看到构建这些函数的一般过程。现在,我们只需检查这些函数:
图 15.19. b 样条 ,具有均匀的结间距。
为了使表达式更简单,我们将每个部分的函数写成作用于 0 到 1 范围内的形式。
如果我们评估从这些 B 样条相加而成的整体函数,在任何时刻只有 (在本例中为 3)个非零的 B 样条。其中一个会在式 15.17 的第一部分中,一个将在第二部分中,而另一个将在第三部分中。因此,我们可以认为整体函数的任何部分都由依赖于 个系数的 多项式组成。对于 的情况,我们可以写成:
其中 。这定义了整体函数的部分,当 时。
如果我们有一组 个点,我们可以使用 B 样条创建一条曲线。如果我们有七个点,则需要一组七个 B 样条。具有 的七个 B 样条的示例如图 15.20 所示。请注意,有 个节点,而 B 样条在 到 范围内的总和为 1。使用这些 B 样条和一组点指定的曲线如图 15.21 所示。
图 15.20。7 条 且结点间距均匀的 B 样条集合
图 15.21。由 7 条二次 B 样条构成的曲线,使用 7 个控制点。
均匀三次 B 样条
由于计算机图形学中常用的是三次多项式,因此在讨论一般情况之前,具有 k = 4 的 B 样条特例非常重要。一个三次 B 样条由四个三次多项式片段定义。稍后将描述确定这些片段的一般过程,但结果是:
这个三次 B 样条在 时的图像如图 15.22 所示。
图 15.22。具有均匀结点的三次 B 样条。
我们可以将影响它的四个控制点和参数 (介于 0 到 1 之间)写成跨越结点 和 之间的整体曲线函数:
这可以使用先前部分中的矩阵表示法重新编写,给出三次 B 样条的基础矩阵:
与第 15.5 节中从约束导出的矩阵不同,此矩阵是由下一节中定义的一般 B 样条过程确定的多项式创建的。
15.6.3 非均匀 B 样条
B 样条的一个好处是它们可以定义任何 的 B 样条。因此,如果我们需要更平滑的曲线,我们可以简单地增加 的值。如图 15.23 所示。
图 15.23。使用相同的均匀结点和相同的控制点,针对不同的 值生成的 B 样条曲线。请注意,随着 的增加,曲线的有效参数范围缩小。
到目前为止,我们已经说过 B 样条可以推广到任何 和任何 。在我们展示如何实际计算这些 B 样条之前,还有一个推广要介绍。B 样条定义为任何非递减结点向量。
对于给定的 和 ,B 样条(以及由它们的线性组合创建的函数)具有 个节点。我们可以将这些结点的值写成一个向量,我们将其表示为 。对于均匀 B 样条,结点向量是 。但是,B 样条可以生成任何长度为 的结点向量,只要值是非递减的(例如,)。
非均匀结点间距有两个主要原因:它使我们能够控制每个系数影响整体函数的哪个参数范围,并且它允许我们重复结点(例如,在这些点周围创建没有空格的结点)以创建具有不同特性的函数。后者将在本节后面考虑。
指定 B 样条的结点值的能力类似于能够指定插值样条曲线的插值站点。它允许我们将曲线特征与参数值关联起来。通过指定非均匀结点向量,我们指定每个 B 样条曲线系数影响的参数范围。请记住,B 样条 i 仅在结点 和结点 之间非零。因此,与其关联的系数仅影响这些参数值之间的曲线。
控制结点值的一个特别有用的地方是在序列开头插入或删除结点。为了说明这一点,考虑在第 15.6.2 节中讨论过的使用线性 B 样条 定义的曲线。对于 ,均匀节点向量为 。该曲线由一组四个点控制,并跨越参数范围 到 。曲线的“末端”()插值最后一个控制点。如果我们在点集的中间插入一个新点,则需要更长的结点向量。B 样条的局部化属性防止这种插入影响曲线在两端的值。较长的曲线仍然在其末尾插值其最后一个控制点。但是,如果我们选择保持均匀结点间距,则新的结点向量将为 。曲线的末端将位于 ,并且插值最后一个控制点的参数值将与插入之前不同。使用非均匀节点间距,我们可以使用结点向量 ,以使曲线的两端不受更改的影响。具有非均匀结点间距的能力使 B 样条的局部性质成为代数属性和几何属性。
现在,我们介绍定义 B 样条的一般方法。给定系数数量 、B 样条参数 和结点向量 (其长度为 )的值,在下面的递归方程中定义 B 样条:
式(15.19)和(15.20)定义的 Cox-de Boor 递推公式可以用于计算特定 B 样条的特定值。但是,它通常更多地被应用于导出像式(15.17)或(15.18)这样的方程。
例如,考虑我们如何导出式(15.17)。在式(15.20)中使用均匀节点向量 ,,以及 ,则得到:
继续递归,我们必须计算递归表达式:
将这些结果插入到式(15.22)中,得到:
为了证明这个表达式等价于式(15.17),我们注意到每个 B 样条就像一个开关,只在特定的参数范围内打开。例如, 仅在 和 之间非零。因此,如果 ,则表达式中仅有第一个 B 样条非零,因此
类似的操作给出了式(15.17)的其他部分。
重复节点和 B 样条插值
虽然 B 样条有很多好的属性,但使用它们定义的函数通常不会插值系数。如果我们使用它们定义一个曲线并想要插值一个特定点,这可能会不方便。我们在这里简要介绍如何使用 B 样条插值特定点。更完整的讨论可以在本章注释中列出的书籍中找到。
使 B 样条插值其系数的一种方法是重复节点。如果特定 B 样条的所有内部节点都具有相同的值,则整个函数将插值该 B 样条的系数。Figure 15.24 展示了一个例子。
图 15.24 显示了由二次 B 样条 参数化的曲线,具有七个控制点。在(a)中使用均匀节点向量 ,而在(b)中使用非均匀节点向量 。第 4 个和第 8 个节点的重复意味着第 3 个和第 7 个 B 样条的所有内部点都相等,因此曲线插值与这些节点相关联的控制点。
通过重复节点进行插值的代价很高:它会破坏 B 样条和所表示的曲线的平滑性。
然而,在样条的开头和结尾,连续性不是问题的地方,节点的重复对于创建端点插值的 B 样条很有用。虽然第一个(或最后一个)节点的值对于插值不重要,但为了简单起见,我们使前(或后) 个节点具有相同的值以实现插值。
图 15.25 显示了端点插值的二次 B 样条,。节点向量为 。前两个和后两个 B 样条与均匀的 B 样条不同。它们的表达式可以通过使用 Cox-de Boor 递推公式导出:
图 15.25。端点插值二次 B 样条曲线,对于 。结点向量为 。第一个和最后两个 B 样条曲线是非周期性的,而中间四个(用虚线表示)是周期性的,并且与图 15.20 中的曲线完全相同。
15.6.4 NURBS
尽管 B 样条提供了所有的普遍性,但有些函数不能用它们精确表示。特别是,B 样条无法表示圆锥曲线。为了表示这样的曲线,使用两个多项式的比率。非均匀 B 样条用于表示分子和分母。其中最通用的形式是非均匀有理 B 样条,简称 NURBS。
NURBS 将每个控制点 与一个标量权重 相关联,并对两者使用相同的 B 样条:
其中 是具有参数 和节点向量 的 B 样条。
由于 NURBS 提供了惊人的通用性,除了 B 样条的有用属性之外,在几何建模中广泛使用以表示曲线和曲面。
15.7 总结
本章中,我们讨论了多种自由形曲线的表示方法。对于计算机图形学而言,最重要的是:
- Cardinal 样条使用一组立方块来插值控制点。它们通常比插值多项式更受欢迎,因为它们是局部的,易于评估。
- Bézier 曲线近似其控制点,并具有许多有用的属性和相关算法。因此,在图形应用程序中很受欢迎。
- B 样条曲线将曲线表示为 B 样条函数的线性组合。它们是通用的,并具有许多有用的属性,如被其凸包所限制和变差递减。当需要平滑曲线时,通常使用 B 样条。
注释
表示数学形状是一个完全的领域,通常称为几何建模。表示曲线只是开始,通常是建模曲面和固体的前兆。有关曲线的更详细讨论可以在大多数几何建模文本中找到,例如《Geometric Modeling》(Mortenson,1985)对于计算机图形学学生而言易于理解。许多几何建模书籍专门关注平滑曲线和曲面。像《An Introduction to Splines for Use in Computer Graphics》(Bartels、Beatty 和 Barsky,1987)、《Curves and Surfaces for CAGD: A Practical Guide》(Farin,2002)和《Geometric Modeling with Splines: An Introduction》(E. Cohen,Riesenfeld 和 Elber,2001)提供了关于曲线和曲面表示的相当详细的信息。其他书籍则专注于样条的数学;《A Practical Guide to Splines》(De Boor,2001)是标准参考。
曲线和曲面表示方法的发展历史复杂,参见 Handbook of Computer Aided Geometric Design (Farin,Hoschek 和 Kim,2002) 中的 Farin 一章或该主题的书 An Introduction to NURBS: With Historical Perspective(D.F. Rogers,2000)进行讨论。
许多思想由多个组独立开发,他们从不同的学科角度解决问题。因此,很难将思想归功于单个人或指出“原始”来源。这也导致文献中符号、术语和介绍概念的方式多种多样。
练习
- 对于练习题 1-4,找到约束矩阵、基础矩阵和基础函数。您可以使用 MATLAB 或 OCTAVE(类似 MATLAB 的免费系统)等程序来求解矩阵的逆。
- 使用 作为起点位置()、 作为起点处的一阶导数、以及 作为起点处的二阶导数来参数化一个二次曲线。
- 其控制点等间距( 的 值为 , 的 值为 1/3, 的 值为 2/3, 的 u 值为 1)的三次曲线。
- 五次曲线(一个五次多项式,所以矩阵将会是 6×6 的),其中 是开始位置, 是初始导数, 是中间位置(), 是中间位置的一阶导数, 是结束位置, 是结束位置的一阶导数。
- Lagrange 形式(公式 (15.12))可用于表示练习 3 的插值立方体。在多个不同的参数值处使用它来确认它确实产生了与从练习 3 推导出的基础函数相同的结果。
- 设计一个弧长参数化,来表示由参数函数 表示的曲线。
- 给定 Hermite 样条的一段的四个控制点,计算等效 Bézier 曲线段的控制点。
- 使用 de Casteljau 算法来计算控制点在 、、 和 的三次 Bézier 曲线在参数值 和 时的位置。绘制一个草图将有助于您完成此操作。
- 使用 Cox-de Boor 递归推导出公式 (15.16)。