《Fundamentals of Computer Graphics》5th(计算机图形学基础/虎书),中文翻译。
第 21 章 Implicit Modeling 隐式建模
计算机图形学中的隐式建模(也称为隐式表面)涵盖了许多不同的定义模型的方法,包括骨架隐式建模、偏移表面、水平集、变分表面和代数表面。在本章中,我们简要介绍这些方法,并更详细地描述如何构建骨架隐式模型。曲线可以由以下形式的隐式方程定义:
如果我们考虑一个半径为 r 的圆等闭合曲线,则隐式方程可以写作
f(x,y) 的值可以是正值(在圆外),负值(在圆内)或者对于圆上的点精确为零。在三维空间中,相应的是围绕一组占据给定体积或空间区域的点的封闭曲面。该体积形成一个标量场,即我们可以计算每个点的值,就像对于圆的情况,负值被隐式曲线或曲面限制。曲面可以被视为在场中连接具有特定值(如零,参见式 (21.1)) 的点的轮廓线。计算这样的曲面意味着搜索空间以找到满足隐式方程的点。这种方法不太可能导致一个高效的圆绘制算法(在三维空间中更不可能)。这或许是参数化曲线和曲面建模算法在隐式方法之前被研究的原因;然而,开发算法可视化隐式表面也有一些好的理由。在本章中,我们探讨了从建模过程中推导数据与从扫描仪中获取数据的差异。
尽管寻找隐式表面需要计算开销,但使用隐式建模技术进行设计比其他建模方法具有一些优势。许多几何操作都可以使用隐式方法简化,包括:
可以通过使用算法进行直接光线追踪来可视化表面,如 (Kalra&Barr,1989; Mitchell,1990; Hart&Baker,1996; deGroot&Wyvill,2005),或者先转换为多边形 (Wyvill,McPheeters,&Wyvill,1986)。
最早的方法之一是由 Ricci 于 1973 年提出 (Ricci,1973),他在同一篇论文中也介绍了 CSG。Jim Blinn 为找到电子密度场中轮廓线而开发的算法,即 Blobby 分子 (J. Blinn,1982),Nishimura 的 Metaballs(Nishimura 等,1985) 和 Wyvills 的 Soft Objects(Wyvill 等,1986) 都是隐式建模方法的早期例子。Jim Blinn 的 Blobby Man(见图 21.1) 是非代数隐式模型的第一个渲染。
图 21.1。Blinn 的 Blobby Man 1980 年。图像由 Jim Blinn 提供。
在建模上下文中,隐式函数被定义为应用于点 的函数 ,产生一个实数值 。
隐式函数 可以分解为距离函数 和衰减滤波函数 [1] ,其中 表示到骨架的距离,下标指代第 个骨架元素。
[1] 这些函数过去被研究人员赋予了许多名称,例如过滤器、势函数、径向基、核函数,但我们使用衰减滤波器作为简单术语来描述它们的外观。
我们将使用以下符号:
一个简单的例子是点基元,我们采用恒星向太空辐射热量的类比。可以在任何点 处测量场值(例如温度),并通过从 到恒星中心的距离,提供值给类似于图 21.2 中所示的衰减滤波器函数。在这些样本函数中,场在恒星中心处被赋予值 ;该值随着距离的增加而衰减。模型的表面可以从隐式函数 中推导出来,作为空间点的值等于某个所需等值线值 () 的点;在恒星的示例中,对于 ,我们得到一个球形壳体。
图 21.2。衰减滤波函数 ()。 (a)Blinn 的高斯或“Blobby”函数;(b)Nishimura 的“Metaball”函数;(c)Wyvill 等人的“soft objects”函数;(d)Wyvill 函数。
通常,滤波器函数 () 被选择为场值在骨架上最大,并在距离骨架一定距离时衰减至零。在简单情况下,其中多个表面被混合在一起,对象的全局场 ,即隐式函数,可以定义为
个骨架元素对结果场值有贡献。图 21.3 显示了一个例子,在该例子中,任何点 处的场都计算如式 (21.3) 所示。
图 21.3。每列显示两个相互靠近的点基元。从左到右:使用的衰减滤波函数分别是 Blobby、Metaball、soft objects 和 Wyvill。图像由 Erwin DeGroot 提供。
在这种情况下,将两个点基元放置在靠近位置。随着这两个点的接近,曲面会凸起并融合在一起。术语“滤波器函数”之所以被使用,是因为该函数导致基元相互模糊,类似于图像的滤波器函数。求和混合是可以应用于隐式表面的最简洁和高效的混合操作(参见式 (21.3))。
使用有限支持的滤波函数的优点之一是远离点 的基元将不会产生贡献,因此无需考虑这些基元 (Wyvill 等人,1986)。
最基本的连续性形式是 连续性,它确保函数没有“跳跃”。更高阶的连续性是通过函数的导数来定义的(见第 15 章)。
对于 3D 标量场 ,第一阶导数是一个向量函数,称为梯度,写作 ,并定义为
如果所有点都定义了 ,并且三个一维偏导数每个都是 ,则 是 。非正式地说, 曲面连续性意味着曲面法线沿曲面平稳变化。曲面法线是垂直于曲面的单位向量。例如,在立方体的边缘上无法定义唯一的曲面法线,则该曲面不是 。对于隐式表面上的点,可以通过归一化梯度向量 来计算曲面法线。在圆的例子中,内部点具有负值,外部点具有正值。对于许多类型的隐式表面,内部和外部的方向是相反的,由于法向量必须始终指向外部,因此可能与梯度方向相反。
通过将衰减滤波函数应用于未签名距离场,如式 (21.2) 所示,创建骨架隐式基元。虽然距离场在骨架处永远不是 的,但可以通过使用合适的衰减函数 (Akleman&Chen,1999) 消除这些不连续性。如果运算符 组合隐式函数 和 ,其中所有点都是 ,则 不一定是 。例如,可以使用 和 运算符制作尖锐的 CSG 连接点。由于 和 运算符没有该属性,因此组合不具有 连续性(请参见第 21.5 节)。
运算符的分析变得复杂,因为有时需要创建 不连续性。每当需要曲面上的褶皱时,就会出现这种情况。例如,立方体不是 ,因为在每个边缘处存在切线不连续性。要使用 基元创建褶皱,运算符必须引入 不连续性,因此本身不能是 。
距离场是相对于某个几何对象 定义的:
在视觉上, 是从 到 的最短距离。因此,当 位于 上时,,并且由隐式函数创建的曲面是对象 。在 之外,返回非零距离。函数 可以是嵌入 3D 中的任何几何实体 - 点、曲线、曲面或立体图形。使用距离场进行程序化建模始于 Ricci(Ricci,1973); R-函数 (Rvachev,1963) 则在 20 多年后首次应用于形状建模(参见 (Shapiro,1994) 和 (A. Pasko,Adzhiev,Sourin & Savchenko,1995))。
R-函数 或 Rvachev 函数是一种函数,其符号仅在其中一个参数的符号更改时才会更改;也就是说,它的符号仅由其参数确定。 R-函数为真实函数的布尔组合提供了一个强大的理论框架,允许构建 Cn CSG 运算符 (Shapiro,1988)。这些 CSG 运算符可以通过将固定偏移量添加到结果中简单地创建混合运算符 (A. Pasko 等人,1995)。尽管这些混合函数不再是技术上的 R-函数,但它们具有大部分理想的属性,并且可以自由地与 R-函数混合以创建复杂的分层模型 (Shapiro,1988)。基于 R-函数的混合和 CSG 运算符称为 R-运算符(参见第 21.4 节)。 Hyperfun 系统 (Adzhiev 等人,1999) 基于 F-Reps(函数表示),这是隐式表面的另一个名称。该系统使用类似 C 的过程性语言来描述许多类型的隐式表面。
通过常规网格 (Barthe,Mora,Dodgson&Sabin,2002) 或自适应网格 (Frisken,Perry,Rockwood 和 Jones,2000),以离散方式表示隐式场是有用的。在等值集的情况下,多边形化算法正是这样做的;此外,除了构建多边形之外,网格还可以用于各种其他目的。通常通过在定期间隔处对连续函数进行采样来获得 的离散表示。例如,采样的函数可以由其他体积模型表示定义 (V.V. Savchenko,Pasko,Sourin 和 Kunii,1998)。数据也可能是使用三维成像技术采样的物理对象。离散体积数据最常与等值集方法 (Osher&Sethian,1988) 结合使用,该方法定义了使用曲率依赖速度函数动态修改数据结构的方法。基于等值集的交互式建模环境已被定义 (Museth,Breen,Whitaker&Barr,2002),尽管等值集仅是使用离散表示隐式场的一种方法。还探索了使用标准隐式表面技术交互式定义离散表示的方法 (Baerentzen&Christensen,2002)。
采用离散数据结构的关键优势是其能够作为由潜在场定义的所有各种体积模型的统一方法(离散或非离散)(V.V. Savchenko 等人,1998)。将任何连续函数转换为离散表示引入了如何重构连续函数的问题,这是为了完成其他建模操作和可视化结果的潜在场所需的。已知解决此问题的解决方案是使用卷积运算符应用滤波器 (请参见第 9 章)。选择滤波器的指导原则是重构所需的期望属性,并且已经探索了许多滤波器 (Marschner&Lobb,1994)。显著的一点是,通常选择的滤波器效率和重构的平滑度之间存在权衡;另请参见第 21.9 节。
为了实现交互性,离散系统必须相对于可用计算能力限制网格的大小。这反过来限制了建模者包括高频细节的能力。此外,平滑三次滤波器使得无法包含尖锐的边缘,如果需要的话。这个问题的一个部分解决方案是使用自适应网格,尽管在任何离散表示中都会有限制。在 (Schmidt,Wyvill 和 Galin,2005) 中使用离散网格作为表示 BlobTree 节点的缓存。该工作中的网格用于快速原型制作,并使用三线性插值来计算位置和较慢、更准确的三次三次插值来计算梯度值,因为眼睛对梯度误差的观察能力更加敏锐。
通常需要将采样数据转换为隐式表示。变分隐式曲面使用全局支持的基函数的加权和来插值或近似一组点 (V. Savchenko,Pasko,Okunev 和 Kunii,1995;Turk 和 O'Brien,1999;Carr 等人,2001;Turk 和 O'Brien,2002)。这些径向对称的基函数应用于每个采样点。这样的曲面的连续性取决于基函数的选择。最常用的是 薄板样条 (Turk&O'Brien,2002;Carr 等人,2001)。就像 Blinn 的指数函数一样(见图 21.2),该函数是无界的,因此得到的变分隐式曲面也是无界的。
如果场是全局 ,则无法定义折痕;然而,可以使用各向异性基函数来产生更快变化并可能出现折痕的场 (Dinh,Slabaugh 和 Turk,2001)。在适当的尺度下,表面仍然平滑。光滑场意味着不会发生自交,并且因此永远定义了体积。薄板样条保证全局曲率最小化 (Duchon,1977)。变分插值具有 3D 建模所需的许多属性;但是,控制所得到的曲面可能会很困难。
变分隐式曲面也可以基于紧支持径向基函数 (CS-RBF) 来降低变分插值技术的计算成本 (Morse,Yoo,Rheingans,Chen 和 Subramanian,2001)。每个 CS-RBF 仅影响局部区域,因此计算 仅需要在 的某个小邻域内评估基函数。与全局支持的对应项一样,得到的场是 Ck,不支持折痕,并且自交不会发生 [3]。每个基函数的局部支持导致有界全局场。这也保证了存在额外的等值轮廓线,正如各种研究人员所指出的那样 (Ohtake,Belyaev 和 Pasko,2003;Reuter,2003)。
[3] 注意, 取决于 RBF(请参见第 15.2 节)。
卷积曲面是由 Bloomenthal 和 Shoemake(Bloomenthal&Shoemake,1991) 引入的,通过将几何骨架 与核函数 进行卷积来产生。因此,空间中任何位置的值都是通过对骨架进行积分定义的:
可以使用任何有限支持的函数作为 h;有关不同内核的详细分析,请参见 (Sherstyuk,1999)。
与骨架基元类似,卷积曲面具有有界场。Blinn 的“Blobby molecules”是卷积曲面的最简单形式 (J. Blinn,1982);在这种情况下,骨架仅包含点。Bloomenthal 将其扩展为包括线、弧、三角形和多边形骨架 (Bloomenthal&Shoemake,1991)。这些表示 1D 和 2D 基元; Bloomenthal(Bloomenthal,1995) 后来描述了 3D 基元。
卷积曲面的组合由基础几何骨架的组合构成,并具有消除组合多个骨架基元时可能出现的隆起的优点。由组合骨架卷积得到的曲面没有隆起,如图 21.4 所示,并且即使组合骨架是非凸的,场也是连续的。卷积曲面从骨架的凸部分偏移固定距离,但在骨架的凹部分产生圆角。
图 21.4 显示了卷积圆柱体的两个混合形式。左侧:总和混合;右侧:卷积曲面,有一个几乎无法识别的隆起 (Bloomenthal,1997)。图片提供 Erwin DeGroot。
图 21.5 显示了使用卷积的骨架元素构建复杂模型的示例。手模型包含 14 个基元。
正如我们将在以下章节中看到的那样,渲染隐式模型需要找到大量点的场值和梯度。我们需要距离以供方程 (21.2) 使用,而梯度对于根查找以及光照计算也很有用。提供图 21.2 的衰减滤波函数的距离是计算到骨架基元最近距离的问题,对于点基元来说很简单,但对于更复杂的几何形状则有些棘手。线段基元 () 可以定义为一个围绕着带有半球形端盖的线的圆柱体(见图 21.6)。点 位于表面上,其中 且 ,因为它位于线基元的影响范围之外。从某个 Pi 到线的距离可以通过简单地投影到线 AB 上并计算垂直距离来找到,例如 ;这可以从 中找到,因为 , 和 都是已知的:
在图 21.6 中, 的场值 ,因为 在半球形端盖内,这可以单独检查。这个想法的变化可以定义具有不同半径端盖的基元,从而产生有趣的锥形。图 21.7 显示了一个例子。
图 21.7。圆柱体基元与球体的混合。图片由 Erwin DeGroot 提供。
描述了许多不同类型的几何骨架,原则上只需要定义从某点 到骨架的距离以及 处的梯度即可。例如,可以从三角形的顶点和半径 定义偏移曲面。实现这一方法的简单方式是使用线段基元来描述连结顶点的边界圆柱(半径 )。对于不在线段基元边界范围内的三角形内部点 ,则返回垂直于三角形平面的垂直距离作为距离值。其他例子包括用一个圆和厚度参数定义的隐式圆盘、用一个圆和截面半径(或内外圆半径)定义的环面、从圆盘和高度定义的圆锥、带有圆角的立方体等(见图 21.8)。
图 21.8。各种骨架基元生成的隐式模型。图片由 ErwinDeGroot 提供。
建模方法(例如参数曲面)非常适合可视化,因为可以轻松地遍历直接从定义方程中找到的曲面上的点。例如 , 产生一个圆。
通常使用两种技术来渲染隐式曲面:光线追踪和表面切片。在实践中,设计师希望快速可视化隐式曲面模型,以交互目的为代价牺牲质量以换取速度。原型算法致力于生成可以在现代工作站上实时渲染的多边形网格。找到最佳近似所需曲面的多边形网格被称为多边形化或表面切片。对于动画或最终可视化,更喜欢质量而不是速度的情况,直接对隐式曲面进行光线追踪而无需先进行多边形化会产生出色的结果。
图 21.9。射线追踪的恐龙模型,显示了底层的骨架基元。图片由 Erwin DeGroot 提供。
如前所述,要找到一个隐式曲面需要在空间中搜索满足 的点。执行这种搜索有两个主要方法:空间分割——将空间分割成易管理的单元,例如立方体;以及非空间分割,例如 marching triangles(Hartmann, 1998; Akkouche & Galin, 2001) 和 shrinkwrap 算法 (van Overveld & Wyvill, 2004)。
在本章中,我们描述了最初的空间分割算法,并让读者探索更高级的方法。此算法与网格细化的后处理(见第 12 章)和缓存结合使用,为在现代工作站上交互式查看隐式模型提供了一种方法。
将空间均匀划分为立方体单元格,并计算每个顶点的值,是一种寻找隐式曲面的基本方法。每个单元格都被替换成一组最佳近似包含在该单元格内部的曲面的多边形。该方法的问题在于许多单元格完全在体积之外或之内;因此,处理了许多不包含任何曲面部分的单元格。对于大量数据的网格来说,这可能非常耗时和占用内存。
为避免存储整个网格,使用哈希表仅存储包含曲面一部分的立方体,基于 (Wyvill 等人,1986) 中使用的数据结构。工作软件发表在 Graphics Gems IV(Bloomenthal,1990) 中。该算法基于数值连续性;它从相交曲面的种子立方体开始,并根据需要构建相邻立方体以跟踪曲面。
该算法有两个部分。在第一部分中,找到包含曲面的立方体单元格,在第二部分中,每个立方体单元格被三角形替换。算法的第一部分由一个立方体队列驱动,每个立方体都包含曲面的一部分;算法的第二部分是基于表的驱动。
该算法的快速概述如下:
首先,将空间细分为立方体网格,接下来的任务是找到包含曲面部分的种子立方体。曲面内部的立方体顶点 将具有场值 ,而在曲面外部的顶点将具有场值 ;因此,一个具有一种类型的顶点的交叉边将与曲面相交。我们称之为交汇边。可以通过按照方程 (21.3) 计算基元的贡献来评估第一个基元最近的立方体顶点处的场值,尽管稍后还将看到其他运算符也可以使用。我们假设 ,这表示 位于固体内部。用户选择 的值;当使用软衰减函数时,例如 ,它具有一些对称性质,导致很好的混合(见图 21.3)。依次评估沿一个轴的顶点,直到发现值 。包含交汇边的立方体单元格是种子立方体。
检查种子立方体的相邻单元格,并将至少包含一个交汇边的单元格添加到队列中以供处理。要处理一个立方体单元格,我们要检查每个面。如果任何一个限制边具有相反符号的顶点,则曲面将通过该面,并且必须处理面邻居。当所有面都已完成此过程后,应用算法的第二阶段于立方体单元格。如果曲面是闭合的,最终会重新访问立方体单元格,并且找不到未标记的相邻单元格,搜索算法将终止。处理一个立方体单元格涉及将其标记为已处理并处理其未标记的相邻单元格。其中包含交汇边的单元格被处理,直到整个曲面被覆盖(见图 21.10)。
图 21.10。立方体网格的截面。+号表示位于曲面内部的顶点 和-表示位于外部的 的顶点。
每个立方体单元格都由一个识别顶点索引,我们定义为左下角远端(即具有最低 (x,y,z) 坐标值的顶点(见图 21.11))。对于每个位于曲面内部的顶点,相应的位将被设置为在 8 位表中形成地址(见图 21.11 和第 21.3.3 节)。
通过从立方体单元格的 坐标位置计算出的整数 ,, 寻址识别顶点,如 等,其中 side 是立方体单元格的大小。每个立方体单元格的识别顶点可能出现在多达八个其他立方体单元格中,因此存储这些顶点多次是低效的。因此,顶点以唯一方式存储在链接的哈希表中。由于大部分空间不包含曲面的任何部分,因此只会存储访问过的立方体单元格。随着存储在哈希表中的每个顶点,都会找到其隐式函数值。
由于不知道曲面的拓扑结构,因此必须从每个基元开始搜索,以避免错过任何断开的曲面部分。可以使用标量来缩放基元的影响。如果标量可以小于零,则可能会沿一个轴进行搜索而找不到交汇边。在这种情况下,必须执行更复杂的搜索来找到种子立方体 (Galin&Akkouche,1999)。
数据结构
哈希表条目包含五个值:
哈希函数通过从 、、 中选择一些比特位,并进行算术组合来计算哈希表中的地址。例如,最低有效位产生一个 15 位的地址,必须具有长度为 215 的表。这种哈希函数可以在 C 预处理器中实现如下:
c#define NBITS 5
#define BMASK 037
#define HASH(a,b,c) (((a&BMASK)<<NBITS|b&BMASK)
<<NBITS|c&BMASK)
#define HSIZE 1<<NBITS*3
队列 (FIFO 列表)用作临时存储以标识要处理的相邻单元格。算法从标记为已访问并放置在队列中的种子立方体单元格开始。将队列上的第一个立方体单元格出列,并将其所有未访问的相邻单元格添加到队列中。如果立方体单元格包含曲面的一部分,则会处理每个立方体单元格并将其传递给算法的第二阶段。然后处理队列,直到为空。
算法的第二阶段独立地处理每个立方体单元格。该单元格由一组三角形替换,其最佳匹配通过单元格的那部分曲面的形状。算法必须决定如何进行多边形化,给定每个顶点的隐式函数值。这些值将是正数或负数(即小于或大于等于 iso 值),为立方体的八个顶点提供 256 种正或负顶点的组合。256 个条目的表提供每个三角形要使用的正确顶点(图 21.12)。例如,条目 4(00000100) 指向记录限制交汇边的顶点的第二个表。在此示例中,顶点编号 2 位于曲面内部 ,因此,我们希望画一个连接与边缘相交的曲面上的点的三角形,这些边缘由 , 和 界定,如图 21.13 所示。
图 21.12。表 2 包含被曲面截断的边缘。表 1 指向表 2 中适当的条目。
查找立方体-曲面相交
图 21.13 显示了一个立方体,其中顶点 位于曲面内部,所有其他顶点都在外部。如图所示,与曲面的相交发生在三个边缘上。曲面在边缘 处与点 相交。计算 的最快但不精确的方法是使用线性插值:
图 21.13。查找曲面与立方体边缘的交点。
如果立方体边长为 ,且要求 的 iso 值为 ,则
这对于静态图像效果良好,但在动画中,帧之间的误差差异将非常明显。应使用诸如 的根查找方法。随着需要评估交点处梯度而变得更加计算昂贵。渲染表面点时,还需要梯度。对于许多类型的基元,使用围绕 的采样点进行数值逼近更简单,如下所示:
经验上已经发现, 的合理值为 ,其中 side 是立方体边的长度。
对于制造网格而不是一组独立三角形,第二个哈希表可以维护所有相交边缘的列表。由于每个立方体边缘最多被四个相邻单元格共享,因此边缘哈希表可以防止重复计算曲面-立方体边缘的交点。哈希地址可以从与顶点相同的哈希函数中派生(应用于边界点)。
当面(或立方体)的对角线具有相同的符号且面上另一对顶点具有相反的符号时,会出现歧义(参见图 21.14)。在面的中心取样将提示立方体是否表示两个曲面的相遇或鞍点。需要明确的是,空间网格存储了每个顶点的隐式函数样本。如果函数在单元格内部变化很大,则多边形表示不会显示这种变化(参见图 21.15)。除非已知曲面的曲率,否则无法仅通过采样来解决曲面。该主题的良好讨论可在 (Kalra&Barr,1989) 中找到。
图 21.14。顶点在曲面内 (+) 和外部 (-) 的示例。注意,额外采样可提供避免歧义情况的线索。
图 21.15。立方体太大,无法捕捉隐式函数中的小变化。
这种歧义问题(而不是欠采样问题)可以通过将立方体单元格细分为四面体来避免。然后可以无歧义地对四面体进行多边形化。由于每个四面体有四个顶点,因此 16 个条目的表将提供正确的三角形信息。缺点是会生成大约两倍数量的多边形。
立方体的细分
在不需要额外的单元格顶点的情况下,可以将立方体分解为五个或六个四面体,如图 21.16 所示。这些分解引入了立方体面上的对角线,并且为了保持邻居之间一致的对角线方向,六个分解是更可取的。引入对角线边产生比直接用三角形替换每个立方体产生更高分辨率的表面。将立方体分解为四面体并用三角形替换四面体是快速的、基于表格的算法,可产生拓扑一致的网格。
图 21.16。将立方体分解为六个四面体。图像由 Erwin DeGroot 提供。
使用均匀空间细分时出现了两个明显的问题。该算法输出的三角形大小不适应曲面的曲率,并且需要进一步采样以解决歧义,其中立方体单元格被替换为多边形。 Bloomenthal(Bloomenthal,1988) 开发了一种基于八叉树的空间细分算法,其确实适应曲面的曲率。单元格被分成八个八分之一,通过使用受限八叉树方案避免裂缝,即相邻单元格之间不能超过一个细分级别的差异。这确实减少了生成的多边形数量,但只有在曲面的平坦区域恰好完全落入适当的八分之一中时,才能充分利用大单元格的优势。该算法在实践中证明要比均匀体素算法慢得多,并且更难以实现。
第 21.1 节显示了当场值相加时可以进行混合。在他的标志性论文中 (Ricci,1973),Ricci 描述了超椭圆形混合。给定两个函数 和 ,先前我们仅将隐式值找到为 。我们可以将此更一般的混合运算符表示为 。 Ricci 混合定义为:
有趣的是指出以下属性:
此外,该广义混合是关联的,即 。标准混合运算符+证明是超椭圆形混合的特殊情况,其中 。当 从 变化到无穷大时,它创建了一组介于混合 和联合 之间的混合(参见图 21.17)。图 21.27 显示节点为二元或一元;实际上,可以使用上述公式轻松扩展二元节点以形成 元节点。
图 21.17。通过变化 ,可以使 Ricci 混合在混合和联合之间平滑变化。图像由 Erwin DeGroot 提供。
Ricci 运算符的威力在于它们在所有可能的隐式体积空间上的操作下是封闭的,这意味着对运算符的应用只会产生定义另一个隐式体积的另一个标量场。可以使用其他字段再次使用 Ricci 运算符组合此新字段。无论它们有多复杂,方程 (21.4) 始终会产生两个隐式体积的精确联合。与将布尔 CSG 操作应用于 B-rep 表面所涉及的困难相比,使用隐式体积进行实体建模非常简单。
按照 Pasko 的功能表示 (A. Pasko 等人,1995),可以定义另一个广义混合函数:
当 从 变化到 时,创建了一组混合,插值联合和交集运算符。但是,该运算符不再是关联的,这与 元运算符的定义不兼容。
隐式模型通常称为隐式表面;然而,它们本质上是体积模型,并且对于实体建模操作非常有用。 Ricci 引入了一种从基元 (Ricci,1973) 的并、交、差和混合等操作中定义复杂形状的构造几何。该表面被认为是 定义内部和 定义外部的半空间之间的边界。这种最初的实体建模方法发展成为构造实体几何或 CSG(Ricci,1973; Requicha,1980)。通常按照二叉树自下而上评估 CSG,低次多项式基元作为叶节点,内部节点表示布尔集合运算。这些方法很容易适应隐式建模的使用,对于骨架隐式表面的情况,将布尔集合运算定义如下 (Wyvill、Galin 和 Guy,1999):
图 21.18 展示了点基元 和 的 Ricci 运算符。对于联合(左下方),联合内所有点的场值将是 和 中较大的那个。对于交集(中心),标记为 区域内的点将具有 的值,因为在其影响范围之外, 的贡献将为零。同样,对于标记为 P2 的区域,(A 的影响为零,即最小值),仅留下具有正值的交集区域。差异使用三个标记区域 () 中的等值体积 (iso-value) 类似如下:
图 21.18。用于 CSG 的 Ricci 操作符。图像由 Erwin DeGroot 提供。
CSG 运算符会创建折痕,即 不连续性。例如, 运算符(方程 (21.5)) 在所有点上创建 不连续性,其中 。当应用于两个球体时,此联合运算符产生的不连续性将导致表面上出现折痕,如图 21.18 所示,这是期望的结果。不幸的是,不连续性扩展到表面外的场中,这在此图像中不可见。如果然后对联合结果应用混合,则场中的 不连续面会产生阴影不连续性(图 21.19)。
图 21.19。由于 不连续面,联合和混合操作产生了阴影不连续性。图像由 Erwin DeGroot 提供。
图 21.19。左侧的两个点基元通过 Ricci 联合连接。第三个基元混合到结果中,在场中创建了一个不需要的折痕。图像由 Erwin DeGroot 提供。
这个问题可以在一定程度上避免 (G. Pasko,Pasko,Ikeda 和 Kunii,2002),并且已经开发出 在除 之外的所有点处的 CSG 运算符 (Barthe,Dodgson,Sabin,Wyvill 和 Gaildrat,2003)。
通过扭曲其邻域中的空间来扭曲表面形状的能力是一种有用的建模工具。Warp 是将 映射到 的连续函数 。Sederberg 在描述自由形变时提供了关于 warp 的好比喻 (Sederberg&Parry,1986)。他建议将扭曲空间类比为一个透明的灵活的塑料平行六面体,其中嵌入了要进行变形的对象。可以通过简单地应用一些 warp 函数 到隐式方程式来定义扭曲元素:
扭曲元素可以通过到其骨架 的距离、其衰减滤波函数 和最终的 warp 函数 来完全描述。要渲染或执行对隐式表面的操作,必须找到许多点 的隐式值。首先, 被扭曲函数转换为某个新点 ,并在 的位置返回 。在图 21.20 中,不返回一些点 的隐式值,而是返回 的值。在这种情况下,返回等值体积,隐式表面 (2D 中的曲线)通过 而不是 。因此,圆形变成了椭圆形。
图 21.20。点 返回点 的场值。
Barr 引入了使用扭曲、锥形和弯曲操作应用于参数曲面的全局和局部变形概念 (Barr,1984)。这些变形可以嵌套以生成诸如图 21.27 所示的模型。从概念上讲,这些很容易应用于隐式表面,如公式 (21.6) 所示。
请注意,不能以类似于扭曲点的方式计算法线。这个问题类似于第 13.2 节中概述的实例化问题。在这种情况下,最容易使用公式 (21.3.3) 来逼近法线,尽管使用雅可比矩阵,如 (Barr,1984) 中建议的那样,可以得到精确的结果。 Barr warps 在以下章节中描述。
在此示例中,三个混合的隐式圆柱体围绕 轴旋转 (见图 21.21),并对它们应用了扭曲 warp。
沿 的扭曲表示为
锥形沿一个主轴应用。线性锥形已被证明是最有用的,尽管二次和三次锥形也很容易实现。例如,沿 轴的线性锥形涉及更改 和 坐标(见图 21.22)。在线性缩放 和 之间应用于 :
图 21.22。三个混合的隐式圆柱体,先扭曲再锥形。图像由 Erwin DeGroot 提供。
弯曲也沿一个主轴应用(见图 21.23)。对于下面的弯曲示例,弯曲率为 (以弧度/单位长度测量),弯曲轴是 ,角度θ定义为 。围绕 的弯曲是
精确接触建模 (PCM) 是一种在保持 连续性的准确接触表面的同时,在接触情况下变形隐式表面基元的方法 (Gascuel,1993)。PCM 很重要,因为它是一种简单而自动的方法,可以显示模型如何对其环境做出反应。这不是使用非隐式方法可以轻松完成的(参见图 21.24)。
通过包含修改每个点返回的场值的变形函数 来实现 PCM。对于每对对象,首先使用边界框测试检测碰撞。一旦确定可能发生碰撞,就应用 PCM。计算并添加局部几何变形项 到隐式函数 中。碰撞物体的体积被分成穿透区域和变形区域。应用 的结果是,压缩穿透区域,以保持接触而不发生穿透(见图 21.25)。在传播区域内, 的效果被衰减为零,以使两个区域之外的体积不发生变形。
图 21.25。碰撞中的两个对象的 2D 截面,显示不同区域和 PCM 变形。图像由 Erwin DeGroot 提供。
给定生成场 和 的两个骨架元素,计算每个表面为
我们需要生成共同的表面(图 21.25 中的虚线),即它们在穿透区域中某些 p 处共享解决方案的地方:
直观地说,物体 2 在物体 1 内部穿透得越深,物体 1 的隐式值就越高,因此物体 2 被压缩得越多。
函数 被定义为在穿透区域的边界上产生平滑的接口,换句话说,当 但其导数大于零时。从这里到传播区域的边界, 用于将传播衰减到零。通过跟随梯度找到穿透区域边界上最近的点 。
在传播区域内,,其中 是正在计算其隐式值的点,(见图 21.26)。 的值由用户设置,定义了传播区域的大小。超出此区域不会发生变形。为了控制对象在传播区域内膨胀的程度,用户为参数 提供一个值。 的最大值是 。 的当前最小值在穿透区域中为负,并且表示为 ,其中 。因此,物体将在穿透区域内被压缩并在传播区域内膨胀。 的方程分为两部分,由两个三次多项式组成,这些多项式设计为在 处连接,斜率为零:
图 21.26。函数 是传播区域中变形函数 的值。
从穿透区域移动到传播区域时,我们希望具有 连续性。因此,在图 21.26 中, 是在接口处(在图 21.25 中标记为 ) 的 的方向导数。如方程 (21.7) 所示,在穿透区域中,,因此:
PCM 仅是正确变形表面的近似,但由于其简单性,它是一种有吸引力的算法。
BlobTree 是一种采用树结构的方法,将 CSG 树扩展为包括使用骨架基元进行各种混合操作 (Wyvill 等人,1999 年)。具有类似功能的系统 Hyperfun 项目使用专门的语言来描述 F-rep 对象 (Adzhiev 等人,1999 年)。
在 BlobTree 系统中,模型是由组合隐式基元和运算符 (并集)、(交集)、(差集)、(混合)、(超椭圆混合)和 (扭曲)的表达式定义的。BlobTree 不仅是从这些表达式构建的数据结构,而且还是一种可视化模型结构的方式。上述运算符是二元的,除了扭曲之外,它是一元运算符。通常,使用 元运算符比使用二元运算符更有效率。BlobTree 将仿射变换作为节点进行合并,因此它也是场景图,并且基元(例如骨架)形成叶节点。
图 21.27 显示了包括 Barr 扭曲和 CSG 操作的 BlobTree 示例。其他节点可以包括 2D 纹理 (Schmidt、Grimm 和 Wyvill,2006 年)、精确接触建模以及动画和其他属性。遍历 BlobTree 本质上非常简单。渲染对象需要通过多边形化或光线追踪找到任意点的隐式值(及其相应的梯度)。这可以通过遍历树来完成。多边形化和光线追踪算法需要在空间中评估大量点的隐式场函数。函数 返回节点 在点 处的场值,具体取决于节点类型。值 和 表示探索树的左侧或右侧分支。以下算法(为简单起见)是针对二叉树编写的:
function :
图 21.27。BlobTree。螺旋楼梯是由中央纹理圆柱体构建的,楼梯和栏杆与其混合。栏杆由一系列圆柱体与两个圆环(环面)基元混合而成,并进一步与垂直圆柱体混合。BlobTree 也是场景图形,实例节点重复由适当矩阵变换的各个部分。每个台阶都由锥形多边形基元(变成偏移表面)制成;相交和并集节点将充气的盘与台阶结合起来。
图 21.28 显示了一个复杂的 BlobTree 模型,展示了已经集成的许多功能。
图 21.28。“螺旋楼梯”。在 Erwin DeGroot 的 BlobTree.net 系统中创建的复杂 BlobTree 隐式模型。
早期的基于草图的建模系统,例如 Teddy(Igarashi、Matsuoka 和 Tanaka,1999 年),使用用户的几笔画来推断 3D 空间中的多边形模型。随着硬件和算法的改进,现在可以使用基于草图的隐式建模系统。Shapeshop 使用隐式扫描曲面从 2D 用户笔画制造 3D 笔画,并且保留 BlobTree 的层次结构,而早期的系统则生成了均匀网格 (Schmidt、Wyvill、Sousa 和 Jorge,2005 年)。这使用户可以从几个简单的笔画中制作任意拓扑的复杂模型。页边的图显示了一个闭合的绘制笔画(图 21.29) 膨胀成一个隐式扫描并用 CSG 减去较小的扫描对象的第二个扫描(图 21.30)。
图 21.29。轮廓被膨胀。图像由 Erwin DeGroot 提供。
使这一切成为可能的改进之一是缓存系统,它在 BlobTree 的每个节点处使用固定的三维隐式值网格来表示遍历该节点以下树时发现的值 (Schmidt、Wyvill 和 Galin,2005 年)。如果需要节点 处的某个点 的值,则可以返回一个值,而无需遍历 N 以下的树,前提是树的一部分未更改。相反,使用插值方案(参见第 9 章)来找到 p 的值。此方案加快了对于复杂 BlobTrees 的遍历,是使系统以交互速率运行的因素之一。
下一代隐式建模系统将利用硬件和软件的进步,能够交互式处理越来越复杂的分层模型。图 21.31 显示了一个更复杂的 Shapeshop 示例。
图 21.30。 BlobTree 操作可以被应用,例如 CSG 差异。图像由 Erwin DeGroot 提供。
图 21.31。 “下一步”。 艺术家 Corien Clapwijk(Andusan) 在 Ryan Schmidt 的 Shapeshop 中交互式创建的复杂 BlobTree 隐式模型。
本文作者:青波
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!