Skip to content

Latest commit

 

History

History
341 lines (250 loc) · 37.1 KB

21 - 隐式建模.md

File metadata and controls

341 lines (250 loc) · 37.1 KB

21 - 隐式建模

计算机图形学中的隐式建模(也称为隐式曲面)涵盖了许多定义模型的不同方法。这些包括骨架隐式建模、偏移曲面、水平集、变分曲面和代数曲面。 在本章中,我们将简要介绍这些方法,并更详细地描述如何构建骨架隐式模型。 曲线可以用如下形式的隐式方程来定义: $$f(x,y)=0$$ 如果我们考虑一个半径为 r 的封闭曲线,例如圆,那么隐式方程可以写成: $$f(x,y)=x^2+y^2-r^2=0$$ f (x, y)的值可以为正(在圆外),也可以为负(在圆内),或者恰好在圆上(正好为 0)。在三维空间中,等值集是一个由一组围绕着的点暗示的封闭曲面,这个曲面占据了给定的空间体积或区域。体积形成一个标量场,也就是说,我们可以为每个点计算一个值,例如对于圆而言,负值意味着点被限制在圆的内部。 曲面可以被可视化为场中的轮廓,连接具有特定值(如零)的点。计算这样一个曲面意味着)空间中寻找满足隐式方程的点;这种方法不太可能产生一个有效的绘制算法(更不太可能在三维)。这也许是参数化曲线曲面算法先于隐式曲面算法被开发的原因。 然而,也有一些很好的理由来为隐式曲面开发可视化算法。

尽管寻找隐式曲面的计算开销很大,但与其他建模方法相比,使用隐式建模技术进行设计具有一些优势。使用隐式方法简化了许多几何运算,包括:

  1. 混合的定义
  2. 构造立体几何 CSG 的标准集操作(并、交、差等)
  3. 与其他隐式函数的功能组合)例如,R-函数、Barthe 混合、Ricci 混合和翘曲)
  4. 内部/外部测试(例如,用于碰撞检测)

可视化表面可以通过使用直接光线追踪算法来完成首先转换为多边形。 最早的方法之一是 Ricci 早在 1973 年就提出的,他也在同一篇论文中介绍了 CSG。Jim Blinn 在电子密度场中寻找轮廓(算法被称为 Blobby molecules)、Nishimura 的 Metaballs 以及 Wyvills 的 Soft Objects 都是隐式建模方法的早期例子。Jim Blinn 的 Blobby Man(见图 21.1)是第一个非代数隐式模型的渲染。

21.1 隐式函数、骨架基元以及求和混合

在建模的语境下,隐式函数被定义为函数 f 作用于点 p∈E3,产生标量值 ∈R。

隐式函数 fi(x, y, z)可以分为距离函数 di(x, y, z)和衰减滤波函数 gi(r),其中 r 表示到骨架的距离,下标表示第 i 个骨架元素。

我们将使用以下符号: $$f_i(x,y,z)=g_i,\circ,d_i(x,y,z)$$ 一个简单的例子是一个点原语,我们用恒星向太空辐射热量来类比。场值(本例中的温度)可以在任何点 p 处测量,通过取 p 到恒星中心的距离并将该值提供给类似于图 21.2 所示的一个衰减滤波函数来求出场值。 在这些样例函数中,恒星中心的场被赋值为 1;该值随着距离的增加而下降。 模型的表面可以由隐式函数 f (x, y, z)导出为一系列空间点,这些点的值等于某个期望的等值(iso)。 通常,选择滤波函数(gi)是为了使场值在骨架上最大化,并在距离骨架的某个选定距离处降为零。在结果曲面混合在一起的简单情况下,对象的全局场 f (x, y, z)隐式函数,可以定义为 $$f(x,y,z)=\sum_{i=1}^{i=n},f_i(x,y,z)$$ 其中 n 个骨架元素对产生的结果场值有贡献。如图 21.3 所示,其中任意点(x, y, z)处的场值计算如式(21.3)所示。

在这种情况下,两个点原语被放置得很近。当两个点在一起时,表面凸起,然后混合在一起。之所以使用术语滤波函数,是因为该函数会将原语模糊在一起,这有点类似于图像的过滤器函数。求和混合是适用于隐式曲面的最紧凑、最有效的混合操作(式(21.3))。

使用具有有限距离的滤波函数的一个优点是,远离 p 的原语对曲面没有贡献,因此不需要考虑。

21.1.1 C1 连续性与梯度

连续性的最基本形式是 C0 连续性,它确保了函数中没有“跳跃”。高阶连续性是用函数的导数来定义的。 在三维标量场 f 的情况下,一阶导数是一个称为梯度的矢量函数,写为 ∇f,定义为: 如果 ∇f 在所有点都有定义,且三个一阶偏导数均满足 C0 连续性,则 f 满足 C1 连续性。通俗地说,C1 表面连续性意味着表面法线在表面上平滑地变化。举个例子,如果无法在立方体的边缘上定义唯一的面法线,那么这个立方体就不满足 C1 连续性。 对于隐式曲面上的点,可以通过归一化梯度向量 ∇f 来计算曲面法线。对于许多类型的隐式曲面,内部和外部在感觉上应该是颠倒的,并且由于法向量必须始终指向外,因此它可以与梯度方向相反。

骨架隐式原语是通过对无符号距离场应用衰减滤波函数创建的。尽管距离场在骨架处从来都不满足 C1 连续性,但这些不连续可以通过使用合适的衰减函数来消除。 如果一个算子 g 结合了隐函数 f1 和 f2,其中所有的点都是 C1,那么 g(f1, f2)不一定是 C1(???)。例如,可以使用最小值和最大值算子来制作一个锐利的 CSG 结。这个组合几何体不是 C1 连续的,因为最小和最大运算符没有这个性质。

算子的分析是复杂的,因为有时需要创建一个 C1 不连续的几何体。这种情况发生在任何需要在表面产生折痕的时候。 例如,一个立方体不是 C1,因为在每条边上的切线都不连续。要使用 C1 原语来创建折痕,算子必须引入 C1 不连续点,因此不能是 C1 本身。

21.1.2 距离场、R-函数以及函数表示(F-Reps)

距离场是根据某个几何物体 T 来定义的: $$F(T,p)=min_{q\in T},\vert q-p \vert$$ 从视觉上看,F(T, p)是从 p 到 T 的最短距离。因此,当 p 位于 T 上时,F(T, p) = 0,此时由隐函数的 0 水平集创建的曲面是对象 T。如果点 p 在几何体 T 之外,函数 F 返回一个非零距离。T 可以是嵌入在 3d 空间中的任何几何实体——点、曲线、曲面或实体。 距离场的程序化建模始于 Ricci;R-函数在 20 多年后首次应用于形状建模。

一个 R-函数或 Rvachev 函数是一个函数,当且仅当它的一个参数的符号改变时,它的符号可以改变。也就是说,它的符号完全由它的参数决定。 r 函数为实函数的布尔组合提供了一个健壮的理论框架,允许构造 Cn 连续的 CSG 算子。这些 CSG 算子可以简单地通过在结果中添加固定偏移量来创建混合算子。虽然这些混合函数在技术上不再是 r 函数,但它们具有大多数理想的性质,可以与 r 函数自由混合以创建复杂的分层模型。这些基于 r 函数的混合算子和 CSG 算子被称为 R-算子。 Hyperfun 系统基于 F-reps(函数表示),这是隐式曲面的另一个名称。该系统使用程序化的类 c 语言来描述多种类型的隐式曲面。

21.1.3 水平集(前沿论文展示)

通过规则网格或自适应网格来离散地表示隐式场是有用的。这正是多边形化算法在水平集中的作用。此外,除了构建多边形之外,网格还可以用于各种其他目的。 f 的离散表示通常是通过在规则间隔内对连续函数进行采样来获得的。例如,采样函数可以通过其他体积模型表示来定义。数据也可以是使用三维成像技术取样的物理对象。离散体数据通常与水平集方法结合使用,该方法定义了一种使用曲率相关速度函数动态修改数据结构的方法。 基于水平集的交互式建模环境已经被定义,尽管水平集只是使用隐式场的离散表示的一种方法。使用标准隐式表面技术交互式定义离散表示的方法也已被探索。

采用离散数据结构的一个关键优势是,它能够作为一种统一的方法,适用于所有由势场(离散或非离散)定义的各种体积模型。任何连续函数到离散表示的转换引入了如何重建连续函数的问题,为了实现额外的建模操作以及对隐式场的可视化。 这个问题的一个众所周知的解决方案是使用卷积算子应用滤波器 g。滤波器的选择是由期望的重建属性决定,并且我们已经探索了许多滤波器。所选滤波器的效率和重建结果的平滑性之间通常存在权衡。

为了具有交互性,离散系统必须根据可用的计算能力来限制网格的大小。这反过来又限制了模型中的高频细节。此外,平滑滤波器使得它不可能包括尖锐的边缘。 这个问题的部分解决方案是使用自适应网格,尽管使用任何离散表示都会有局限性。Schmidt 在他论文中使用离散网格作为表示 BlobTree 节点的缓存。本工作中的网格用于快速原型设计,并使用三线性插值来定位,使用更慢,更精确的三二次插值来计算梯度值,因为眼睛在观察梯度误差时比位置误差更有辨识力。

21.1.4 变分隐式曲面(前沿论文展示)

通常需要将采样数据转换为隐式表示。变分隐式曲面使用全局支持基函数的加权和来插值或近似一组点。这些径向对称基函数应用于每个采样点。这种曲面的连续性取决于基函数的选择。C2 薄盘样条线是最常用的。与 Blinn 的指数函数(见图 21.2)一样,该函数是无界的,由此产生的变分隐式曲面也是无界的。

如果场全局为 C2,则不能定义折痕;然而,各向异性基函数可以用来产生变化更快的场,并且可能出现折痕。在适当的尺度下,表面仍然是光滑的。光滑的场意味着不会发生自交,因此体积总是定义良好的。薄板样条线保证了整体曲率最小。变分插值具有三维建模所需的许多特性;然而,控制产生的表面可能是困难的。

变分隐式曲面也可以基于紧支持径向基函数(CS-RBF),以减少变分插值技术的计算成本。每个 CS-RBF 只影响一个局部区域,因此计算 f (p)只需要在 p 的一个小邻域内评估基函数。与全局支持的对应物一样,得到的场是 Ck 连续的,不支持折痕,也不会发生自交每个基函数的局部支持产生一个有界的全局域。正如许多研究人员所指出的那样,这也保证了其他等等高线的存在。

21.1.5 卷积曲面

卷积曲面是由几何骨架 S 与核函数 h 卷积产生的。因此,空间中任何位置的值由骨架上的积分定义: $$f(p)=\int_S,g(r)h(p-r)dr$$ 任意有限支持(有限范围)的函数都可以作为 h。

像骨架基元一样,卷积曲面也有有界域。Blinn 的“Blobby molecules”是卷积曲面的最简单形式;在这种情况下,骨架仅由点组成。这一理念被 Bloomenthal 扩展到包括直线、圆弧、三角形和多边形骨架。它们代表 1D 和 2D 基元;3D 基元后来由 Bloomenthal 描述。 卷积曲面的组合是由底层几何骨架的组合来定义的,它的优点是消除了当使用加性混合组合多个骨架基元时容易出现的凸起(膨胀)。组合骨架卷积得到的表面不存在图 21.4 所示的凸起,即使组合骨架是非凸的,也能形成连续的隐式场。卷积表面与骨架的凸起部分偏离固定距离,但沿着骨架的凹陷部分产生圆角。

21.1.6 定义骨架基元

正如我们在以下部分中所看到的那样,渲染隐式模型需要找到大量点的场值和梯度。我们需要距离来提供给方程(21.2),而梯度对于寻根和照明计算很有用。 提供到图 21.2 的衰减过滤器函数的距离是计算到骨骼基元的最近距离的问题,对于点基元来说很简单,但对于更复杂的几何形状来说有点棘手。 直线段基元(AB)可以定义为围绕线的圆柱体(参见图 21.6),在线的两端加上两个半圆形的盖子。点 Po 位于 f(Po)= iso 的表面上且 f(P1)= 0,因为它位于线基元的影响范围之外。通过简单地投影到线 AB 上并计算垂直距离即可找到 Pi 到线的距离: 在图 21.6 中,P2 的场值> 0,因为 P2 在半球形端帽内,这可以单独检查。这种想法的变体可以定义具有不同半径的端帽的基元,从而产生有趣的锥形。例如图 21.7。 各种各样的几何骨架已经被描述过了,原则上,这只是定义从某一点到骨架的距离和 p 点的梯度的问题。例如:三角形的偏移面可以由三角形的顶点和半径 r 来定义。 实现这一点的一种简单方法是使用线段基元来描述连接顶点(半径 r)的边界圆柱体。在三角形中不属于某个线段基元边界域的点 q 的距离返回为与三角形平面的垂直距离(???)。 其他例子还包括由圆和厚度参数定义的隐式圆盘、同样由圆和截面半径(或内外圆半径)定义的环面、由圆和高度组成的圆锥形、圆角立方体等(见图 21.8)。

21.2 渲染

建模方法,如参数曲面,有助于可视化,因为它很容易迭代表面上的点,这些点可以直接从定义方程中找到。

有两种技术通常用于渲染隐式表面:光线追踪和表面平铺。在实践中,设计师希望快速可视化隐式表面模型,牺牲质量以达到交互目的的速度。 原型算法一直关注于生成可以在现代工作站上实时渲染的多边形网格。找到最接近所需表面的多边形网格被称为多边形化表面平铺。对于动画或最终的可视化,质量比速度更重要,直接光线追踪隐式表面而不首先多边形化会产生很好的效果。

如前所述,寻找隐式曲面需要在空间中搜索以找到满足 f (p) = 0 的点。执行这种搜索有两种主要方法:空间划分——将空间划分为可管理的单元,如立方体,以及非空间划分,如行进三角形和 shrinkwrap 算法。

在本章中,我们描述了原始的空间划分算法,留给读者去探索更高级的方法。该算法与网格细化的后处理(见第 12 章)和缓存一起提供了一种在现代工作站上交互式查看隐式模型的方法。

21.3 空间划分

21.3.1 穷举搜索

用于平铺隐式曲面的基本立方空间划分算法首次发表在 Wyvill 的文章上和面向体积可视化的类似算法,称为行进立方体。从那时起,行进立方体算法有许多改进和扩展。

寻找隐式曲面的第一种方法是将空间均匀地细分为立方体单元的规则晶格,并为每个顶点计算一个值。每个单元格被替换为一组最能近似该单元格中包含的表面部分的多边形。 这种方法的问题是,许多晶胞将完全在体积外或完全在体积内。因此,许多不包含表面部分的晶胞也被处理。对于大型数据网格,这可能非常耗时且占用大量内存。

为了避免存储整个网格,基于 wyville 中使用的数据结构,使用哈希表仅存储包含一片表面的立方体。软件发表在 Graphics Gems IV 上。该算法基于数值延拓;它从一个种子立方体开始,它与表面的一部分相交,并根据需要建立邻近的立方体来追踪表面。

该算法分为两部分。在第一部分中,发现包含表面的立方体晶胞,在第二部分中,每个立方体被三角形取代。算法的第一部分由一个立方体队列驱动,每个立方体包含表面的一部分;算法的第二部分是表驱动的。

21.3.2 算法描述

算法的快速概述如下:

  1. 将空间划分为立方体体素
  2. 从骨架元素开始寻找表面
  3. 将体素添加到队列,标记它已被访问
  4. 搜索邻居
  5. 完成后,用多边形替换体素

首先,空间被细分成一个立方晶格,接下来的任务是找到一个包含部分表面的种子立方体。隐式曲面内的立方体顶点 vi 的场值 vi >= iso,隐式曲面外的立方体顶点的场值 vi < iso;因此,同时拥有两种顶点的边线一定与曲面相交,我们称它为相交边线。 距离第一个基元最近的立方体顶点处的场值可以通过公式(21.3)对所有基元的贡献求和求出,尽管后面还可以使用其他操作符。 我们假设 f (v0) > iso,这表明 v0 在隐式曲面内。iso 的值由用户选择;当使用软衰减函数时,一个例子是 iso = 0.5,它具有一些对称属性,可以产生很好的混合效果(图 21.3)。沿着一个轴的顶点依次求值,直到找到值 vi < iso。包含相交边的立方体是种子立方体

检查种子立方体的邻居,并将那些包含至少一个相交边的邻居添加到队列中以备处理。 为了处理一个立方体,我们检查每个面。如果任何边界边有相反符号的顶点,则说明隐式曲面穿过该面,并且必须处理相邻的面。当所有的面都被检查,算法的第二阶段应用到立方体上。 如果表面是闭合的,最终,立方体将被重新访问,如果没有发现更多未标记的邻居,搜索算法将终止。 处理一个立方体包括将其标记为已处理,并处理其未标记的邻居。那些包含相交边的邻居会被处理,直到整个表面被覆盖(见图 21.10)。 每个立方体标识顶点索引,我们将其定义为左下角远角(即具有最低(x, y, z)坐标值的顶点(参见图 21.11))。对于在曲面内的每个顶点,相应的位将被设置成一个 8 位表中的地址(参见图 21.11 和章节 21.3.3)。

每个立方体有一个字节码(8 位),设置为 1 的对应顶点表示该顶点位于隐式曲面内。

标识顶点由整数 i, j, k 寻址,从立方体的(x, y, z)坐标位置计算,例如 x = side * i,其中 side 是立方体的大小。 每个立方体的标识顶点可能出现在多达八个其他立方体中,并且多次存储这些顶点将是低效的。因此,这些顶点被唯一地存储在一个链式散列表中。由于大部分空间不包含曲面的任何部分,因此只存储访问过的立方体。当每个顶点存储在哈希表中时,会为其找到隐式函数值。

关于表面的布局我们一无所知,因此搜索必须从每个基元开始,以避免错过表面的任何不相连的部分。可使用常量来缩放基元的影响。如果常量可以小于零,那么可以沿着轴搜索而不会找到相交边(???)。在这种情况下,必须进行更复杂的搜索才能找到种子立方体。

数据结构

Hash 表的输入有 5 个值:

  1. 标识顶点的晶格索引 i、j、k。
  2. f,标识顶点的隐式函数值。
  3. 用来表示该晶格是否被访问的布尔值。

Hash 函数通过在 i、j、k 中选择一些特定的位(bit)然后按照一定的规则组合起来在 hash 表中计算出一个地址。例如用后 5 位(bit)组合成一个 15 位(bit)的地址,它有$2^{15}$种可能。这样的函数可以使用 C 语言的预处理器来实现: 队列(FIFO 列表)用作临时存储,以标识要处理的邻居。 算法从一个种子立方体开始,该种子立方体被标记为已访问并放置在队列中。队列上的第一个多维数据集被从队列中取出,其所有未访问的邻居被添加到队列中。如果每个立方体包含表面的一部分,则对其进行处理并传递到算法的第二阶段。然后处理队列,直到队列清空。

21.3.3 多边形化算法

算法的第二阶段是独立处理每个立方体。单元格被一组三角形取代,这些三角形与穿过单元格的部分表面的形状最匹配。 该算法必须在给定每个顶点的隐式函数值的情况下决定如何将单元格多边形化。这些值将是正数或负数(即,小于或大于 iso 值),8 顶点的立方体有 256 个正数或负数顶点的可能组合(2 的 8 次方)。一个包含 256 项的表提供了三角形片面该如何放置的信息(图 21.12)。例如,条目 4(00000100)指向第二个表,该表记录了所有将相交边线围起的顶点。 在本例中,顶点数 2 位于隐式曲面内(f (v2) >= iso),因此,我们希望绘制一个三角形,将曲面上与以(v2, v0), (v2, v3)和(v2, v6)为界的边相交的点连接起来,如图 21.13 所示。

寻找 立方体-曲面 的交线

图 21.13 显示了一个立方体,其中顶点 V2 在隐式曲面内部,所有其他顶点都在表面外部。与隐式曲面相交的三条边如图所示。隐式曲面与边缘 V2−V6 相交于点 A。计算 A 的最快但不准确的方法是使用线性插值: 如果立方体的边长是 1,f (A)的等值(iso)是 0.5,那么: $$A=V_2+ \frac{0.5-f(V_2)}{f(V_6)-f(V_2)}$$ 这对于静态图像很有效,但在动画中帧与帧之间的误差将非常明显。应该采用诸如试位法之类的寻根方法。这在计算上变得更加昂贵,因为需要梯度来计算交点。在渲染的表面点上也需要梯度(求面法向量)。对于许多类型的基元,使用 p 周围的样本点找到数值近似值会更简单,如:

Regula Falsi:试位法(False Position)是在计算机工具非常落后的条件下人们为了改进二分法而得到的一个方法。 先做出一个估计,再从这个估计出发并根据未知量的性质求出代求的未知量。 试位法类似于二分法,也是将含根区间逐渐缩小,但它并不是单一的二分区间,而是利用区间两个端点的线性插值来求一个近似根。

经验发现 Δ 的合理值为 0.01 * side,其中 side 是立方体边的长度。

为了产生一个网格,而非一组独立的三角形,需要第二个哈希表来维护所有相交边的列表。由于每个立方体边线最多由四个邻居共享,因此边线哈希表可以防止表面-立方体边线相交计算的重复。哈希地址可以从与顶点相同的哈希函数中产生(应用于边线端点)。

21.3.4 采样问题

当一个面(或立方体)的对角具有相同的符号,而面上的其他对顶点具有相反的符号时,就会出现歧义(图 21.14)。 此时需要在面的中心采集样本将提供额外的线索,以确定立方体是代表两个表面的交汇还是代表一个马鞍。应该明确的是,空间网格在每个顶点存储隐式函数的采样值。如果函数值恰好在一个单元格内变化很大,那么多边形表示将无法展示出这样丰富的变化(图 21.15)。除非对曲面的曲率有所了解,否则单靠采样是无法解算这样的曲面。 这种模糊性问题(指歧义问题,不是欠采样问题)可以通过将立方单元细分为四面体来避免(行进四面体)。这样,四面体就可以明确地多边形化。由于每个四面体中有四个顶点,因此一个包含 16 个条目的表将提供正确的三角形网格信息。缺点是将生成大约两倍数量的多边形。

细分立方体

不需要额外的单元格顶点,一个立方体可以分解成五个或六个四面体。这些分解在立方体表面引入对角线,并且为了保持相邻之间一致的对角线方向,六分解是优选的。 对角线的引入比直接用三角形替换每个立方体能产生更高分辨率的表面。分解为四面体和用三角形替换四面体是一种快速的表格驱动的算法,可以产生拓扑一致的网格。

21.3.5 单元多边形化

使用统一空间细分会出现两个明显的问题。该算法输出的三角形的大小不适应曲面的曲率,需要进一步的采样来解决歧义,其中立方单元格被多边形取代。 Bloomenthal 提出了一种基于八叉树的空间细分算法,该算法能够适应曲面的曲率。单元格被细分为八个八边形(???怎么做到的),并且通过使用一个受限的八叉树方案来避免裂缝,即相邻的单元不能超过一个细分等级。这确实减少了生成的多边形的数量,但只有当表面的平坦区域恰好完全落在适当的八边形内时,才能充分利用大单元格的优势。 实践证明,该算法比均匀体素算法慢得多,而且实现起来更复杂。

21.4 More on 混合

第 21.1 节表明,当隐式场值相加时,可以进行混合。Ricci 在他具有里程碑意义的论文中描述了超椭圆混合。 给定两个函数 FA 和 FB,之前我们简单地发现隐式场值为 Ftotal = FA + FB。我们可以将这个更一般的混合算子表示为$A\circ B$。Ricci 混合定义为: 而且,这种广义混合满足结合律,即$f_{(A\circ B)\circ C}=f_{A\circ (B\circ C)}$。标准混合算子+被证明是 n = 1 的超椭圆混合的一种特殊情况。 当 n 从 1 到 ∞ 变化时,它会建立一组混合插值,在 A + B 和 A∪B 之间变化(见图 21.17)。图 21.27 显示了节点是一元或二元的。事实上,二元节点可以很容易地使用上述公式扩展到 n 维节点。 Ricci 算子的强大之处在于它在所有可能的隐式体积空间上的运算下是封闭的,这意味着一个算子的应用仅仅产生另一个定义另一个隐式体积的标量场。这个新场可以与其他场组合,同样使用 Ricci 的算子。公式(21.4)总是产生两个隐式体积的精确并集,不管它们有多复杂。与将布尔 CSG 操作应用于 B-rep 表面的困难相比,使用隐式体积的实体建模非常简单。

根据 Pasko 的函数表示,可以定义另一种广义混合函数: 当 α∈[−1,1]在 −1 到 1 之间变化时,它创建了一组混合插值,从并算子到交集算子。然而,这个操作符不再满足结合律,这与 n 元操作符的定义不兼容。

21.5 构造立体几何(CSG)

隐式模型通常被称为隐式曲面。然而,它们本质上是体积模型,对于实体建模操作很有用。

Ricci 引入了构造性几何,用于从基元上的并、交、差和混合等操作来定义复杂的形状。该表面被认为是半空间 f(p)<1(定义内部)和半空间 f(p)>1(定义外部)之间的边界。 这种最初的实体建模方法演变为构造立体几何或 CSG。通常根据二元树自下而上地评估 CSG,其中低级基元作为叶节点,内部节点代表布尔操作。 这些方法很容易适用于隐式建模,并且在骨架隐式表面的情况下,布尔集操作并、交集和差定义如下: 点基元 A 和 B 的 Ricci 运算符如图 21.18 所示。对于并操作(左下),并集内部所有点的场值将是 fA()和 fB()中的较大者。 对于交集(中心),标记为 P1 区域中的点将具有场值 min(fa,fb)=0,因为 B 的贡献在其影响范围之外时为零。 同样,对于标记为 P2 的区域,(A 的影响为零,即最小值)仅留下具有正值的相交区域。 差集的工作原理类似,在三个区域中利用等高值(iso)计算: CSG 算子创建折痕,即 C1 不连续性。例如,min 运算符在所有$f_1(p)=f_2(p)$的位置上产生 C1 不连续性。 当应用于两个球体时,此并运算符产生的不连续会导致表面上出现折痕,如图 21.18 所示。不幸的是,不连续性延伸到表面之外的区域,这在这张图像中不可见。如果随后将混合操作应用于并操作的结果,则场中的 C1 不连续平面将产生着色不连续性(图 21.19)。 这个问题在一定程度上是可以避免的,并且 CSG 算子有了新的升级,现在除了那些$f_1(p)=f_2(p)=iso$的点之外,都满足 C1 连续性。

21.6 扭曲(Warping)

通过扭曲其邻近区域的空间来扭曲表面形状的能力是一个很有用的建模工具。扭曲是一个从$R^3$映射到$R^3$的连续函数$w(x,y,z)$。 在描述自由形式变形(Free From Deformation)时,Sederberg 为扭曲提供了一个很好的类比。他认为,扭曲的空间可以比作一个清晰、灵活、可塑的平行体,其中嵌入了被扭曲的物体。扭曲可以通过简单地将扭曲函数 w(p)应用于隐式方程来定义: $$f_i(x,y,z)=g_i\circ d_i\circ w_i(x,y,z)$$ 一个被扭曲的元素可以用它到骨架的距离 d、它的衰减滤波函数 g 以及它的扭曲函数 w 来完全表示。要对一个隐式曲面进行渲染或操作,必须要求出许多点的隐式场值 f(P)。 首先,通过 warp 函数将 P 变换到某个新点 Q,并返回 f (Q)代替 f (P)。在图 21.20 中,返回的不是某个点 f (Q)的隐式值,而是 f (P)的值(查询 Q 点的时候,返回 f(P))。在这种情况下,隐式曲面(2D 中的曲线)通过 Q 而不是 P。因此,圆被扭曲成一个椭圆。 Barr 引入了全局和局部变形的概念,使用扭曲、锥状变形和弯曲的操作应用于参数曲面。可以嵌套变形以生成如图 21.27 所示的模型。

注意到,法线不能以与扭曲点类似的方式计算。这个问题类似于第 13.2 节实例化中概述的问题。在这种情况下,虽然使用(Barr, 1984)中提及的 Jacobian 矩阵可以产生精确的结果,法向也可以使用容易地公式(21.3.3)来近似。

21.6.1 扭转(Twist)

对混合的三个隐式圆柱体施加绕 z 轴 θ 的扭转变形(图 21.21)。绕 z 旋转的扭转表示为:

21.6.2 锥状变形(Taper)

锥状变形仅沿着某一个轴施加。线性锥状变形被证明是最有用的,尽管二次锥状变形和三次锥状变形很容易实现。 例如,沿 y 轴的线性锥状变形涉及改变 x 和 z 坐标(参见图 21.22)。例如,在 ymax 和 ymin 之间对 y 进行线性缩放:

21.6.3 弯曲(Bend)

弯曲也仅应用于某一个轴(参见图 21.23)。在以下例子中,弯曲率是 k,以单位长度的弧度来测量,弯曲的轴是(x0,1 /k),θ 定义为(x−x0) * k。绕 z 的弯曲是:

21.7 精细接触建模(PCM)

精确接触建模 PCM 是一种在接触情况下变形隐式表面基元的方法,同时保持具有 C1 连续性的精确接触面。 PCM 很重要,因为它是一种简单而自动的方式,可以展示出模型如何对其环境做出反应。这是非隐式方法无法轻易做到的(见图 21.24)。 PCM 是通过包含一个变形函数 s(p)来实现的,该函数修改每个点返回的场值。对于每一对对象,首先使用边界盒测试检测碰撞。一旦确定可能发生碰撞,就应用 PCM。局部的、几何的变形项 si 被计算出来并添加到隐式函数 fi 中。 将碰撞物体的体积划分为相交区和变形区。施加变形项 si 的结果是压缩相交区域,从而使两物体保持接触而不发生相交(见图 21.25)。si 的影响在传播区域内衰减为零,因此两个区域外的体积不会变形。 给定两个生成场 f1(p)和 f2(p)的骨架元素,每个骨架元素周围的表面计算为: 我们需要生成两个元素共有的表面(图 21.25 中的虚线),也就是说,它们在相交区域中共享一个解: 直观地说,对象 2 渗透到对象 1 中越深,对象 1 的隐式场值值就越高,因此对象 2 将被压缩得更多。

函数 s 被定义为在相交区域的边界处产生光滑的连接,换句话说,其中 si=0,但其导数大于零。从这里到传播区域的边界,si 用于将传播衰减到零。沿着梯度找到相交区域边界上最近的点 po。 在传播区域内 si(p)= hi(r),其中 p =(x,y,z)是正在计算隐式场值的点,并且$r=\vert p-p_0 \vert$(图 21.26)。ri 的值由用户设置,定义了传播区域的大小;超出该区域不会发生变形。 为了控制对象在传播区域中膨胀的程度,用户提供参数 alpha 的值。 hi 的最大值是 Mi。当前相交区 si 的最小值是负数,用 simin 来表示,其中$M_i=-\alpha_i s_{imin}$。因此物体在相交区被压缩,在传播区膨胀。hi 的方程由两个三次多项式组成,它们被设计成在 r = ri/2 处相接,那里的斜率为 0: 当我们从相交区移动到传播区时,我们希望有 C1 连续性。因此,图 21.26 中的$h_i'(0)=k$是 si 在结点处的方向导数(在图 21.25 中标记为 p0)。由式(21.7)可知,相交间区中 si =−fi,那么: $$k=\Vert gradient(f_i,p_0) \Vert$$ PCM 只是一个适当变形表面的近似,但由于它的简单性,它是一个有吸引力的算法。

21.8 BlobTree

BlobTree 是一种采用树形结构的方法,该树形结构扩展了 CSG 树,以包含使用骨架基元的各种混合操作。具有类似功能的系统 Hyperfun 项目使用一种专门的语言来描述 F-rep 物体。

在 BlobTree 系统中,模型由组合隐式基元和操作符的表达式来定义,其中操作符有:∪(并集)、∩(交集)、−(差集)、+ (混合)、$\circ$(超椭圆混合)和 w(扭曲)。 BlobTree 不仅是由这些表达式构建的数据结构,而且是一种可视化模型结构的方法。上面列出的操作符都是二元的,除了 warp 是一元操作符。 一般来说,使用 n 元运算符比使用二元运算符更有效。BlobTree 结合了仿射变换作为节点,因此它也是一个场景图和基元(例如,骨架)形成叶节点。

21.8.1 遍历 BlobTree

一个包含 Barr 扭曲和 CSG 操作的 BlobTree 示例如图 21.27 所示。其他节点可以包括 2D 纹理,精确接触建模,以及动画和其他属性。 对 BlobTree 的遍历本质上非常简单。通过多边形化或光线追踪来渲染物体所需要做的就是找到任何点的隐式值(以及相应的梯度,作为面法向量)。这可以通过遍历树来实现。 多边形化和光线跟踪算法需要对空间中大量点的隐式场函数进行求值。函数 f (N, M)返回节点 N 在点 M 处的隐式场值,这取决于节点的类型。值 L 和 R 表示探索树的左分支或右分支。 下面的算法(为了简单起见)被写成了二叉树: 图 21.28 显示了一个复杂的 BlobTree 模型,图像中显示了许多已经集成的特性。

21.9 交互式隐式建模系统

早期基于草图的建模系统,如 Teddy,使用用户绘制的一些笔画来推断三维空间中的多边形模型。有了更好的硬件和改进的算法,基于草图的隐式建模系统现在是可能的。Shapeshop 使用隐式扫描表面从 2D 用户笔画中生成 3D 笔画,并且还保留了 BlobTree 的层次结构,而不像早期的系统那样产生各向同性网格。这使用户能够从几个简单的笔画中生成任意拓扑的复杂模型。边距图显示了一个封闭绘制的笔画(图 21.29)膨胀为一个隐式扫描。第二个扫描(图 21.30),使用 CSG 减去了一个较小的扫描对象。 实现这一目标的改进之一是缓存系统,该系统在 BlobTree 的每个节点上使用固定的 3D 隐式场值网格,表示通过遍历节点子树找到的值。如果节点 N 需要某个点 p 的值,则可以在不遍历 N 子树的情况下返回它的值,前提是树的一部分不变。相反,使用插值方案来查找 p 的值。该方案加快了复杂 blobtree 的遍历速度,并且是使系统以交互速率运行的一个因素。 下一代隐式建模系统将利用硬件和软件的进步,能够交互式地处理越来越复杂的层次模型。图 21.31 显示了一个更复杂的 Shapeshop 示例。