博文
论文推荐：基于草图的建模综述
||
基于草图的建模综述
摘要:传统建模工具的用户界面都基于WIMP的。尽管这些界面功能强大，但对于新手而言，这些界面的使用非常麻烦，令人畏惧。使用这些工具创建一个复杂模型需要相当多的专业技能和精力。近来，一个趋势是引入更方便和自然的用户界面，基于草图的用户界面(Sketch Based Interface and Modeling, SBIM)就是其中之一，其目标在于允许用户在建模过程中使用自由手绘草图，包括从粗略模型直到完整细节的构建过程。由于模糊性的存在，将一幅2D草图映射到3D模型是一个非常困难的任务。本文根据SBIM解释草图的策略选择进行分类，包括三种基本方法：创建3D模型，给现有模型添加细节及变形和操纵模型。文中对基于草图的用户界面在3D图形建模中的应用进行综述，对现有工作进行介绍和分类，总结了草图获取、过滤和解释技术；也介绍了一些SBIM的典型应用，讨论了本领域的主要挑战以及一些开放性问题以供研究者在今后的工作中参考。
Luke Olsen，Faramarz F. Samavati，Mario Costa Sousa，Joaquim A Jorge，Sketch-Based Modeling: ASurvey，《Computer & Graphics》, 2009,Vol.33, pp85-103.
Survey of Sketch-based modeling
1、引言
从严格意义上讲，“所有人都会画”并不是一个正确的论断，但是其揭示了一种普遍存在的视觉通信能力。这也是为什么古人通过象形文字讲故事，而每个会议室的墙上都挂着一个白板的原因。绘制草图是一种直接而快速的思想交流方式：只要看到少量的笔画，人们的脑海中便可勾勒出复杂的图形。
在计算机建模领域，在纸上绘制草图在设计初期(即早期原型设计阶段)经常发生，此后这些描述性设计草图由熟练的3D绘制人员转换为3D模型(如图1所示)。因此，模型创建是产品流水线的一个主要瓶颈，这一过程需要大量人手以创建复杂多变的形状以及错综复杂的内部关系。当前一些高端建模系统(如Maya[1]、SolidWorks[2]和CATIA[3])都提供功能强大的精确几何模型构建和操纵工具。这些系统通常采用WIMP界面范例，即：用户需要从菜单和浮动窗口中选择操作类型，在对话框中输入参数以及移动控制点等。
近来在建模工具界面的一个趋势是引入自动(或辅助)直接从草图到3D模型的转换技术，即面向模型创建的草图交互界面(sketch-based interface for modeling，SBIM)。这类界面的主要研究问题是：计算机如何在三维空间中理解和解释用户绘制的草图？
多年来研究人员一直在考察这个问题。人类视觉系统可以从简单的图像或草图，甚至是从简单的线画图形(并没有阴影线索)中理解复杂的形状，但是人的感知过程是如此的简单，却使得人们很难对这一过程进行理解和形式化。开发一个能够直观地模拟人类观察能力的SBIM系统需要考虑感知和认知问题。事实上，SBIM处于多个不同领域的交叉点，包括计算机视觉、人机用户界面以及人工智能。尽管这一研究主要是由计算机建模领域发起，但是更强大商用计算机硬件的出现以及各方面研究成果推动了该领域取得了令人兴奋的成果。
SBIM研究的最终目标是在原有基于WIMP系统的基础上整合草图交互方式，构筑更实用的建模系统。使用这类系统时用户以渐进的方式构造和修改模型，从初期的概念到详细精确的最终模型。尽管目前对于SBIM有诸多的研究，但是工业界并未完全支持SBIM，因为SBIM不能满足建模任务的所有功能要求。商用建模工具包中支持手绘草图的有Archipelis Designer[4]和Sunny3D[5]，其它一些程序，如ZBrush[6]和MudBox[7]等，也支持建模人员使用刷子以笔画形式在模型表面绘制细节。
草图交互界面可追溯到Sutherland的SketchPad系统[8]，该系统使用光笔作为输入设备在屏幕上直接创建和操纵对象，这种交互方式先于目前流行的鼠标交互方式多年。SketchPad系统预见了许多SBIM会面临的挑战，包括：如何接受和处理用户输入、解释用户输入(作为一个对象或者操作)及表示结果对象。现在的系统主要在SketchPad基础上提升其处理的自动性：SketchPad用户必须显式指定所有的几何信息，而现在的系统可使用更优化的算法减轻用户负担及提高计算能力，进而可以自动的从2D输入推导3D形状。基于草图的技术可被用于多种建模任务，其中的一些将在第7章进行讨论。
本文([9]中的修改和扩展)对基于草图的用户界面在3D几何建模中的应用进行综述。SBIM的主要挑战在于草图解释，对此，我们分为三种主要方法：创建3D模型、(在现有模型上)添加细节及模型变形和操纵。图2总结了SBIM应用的主要流程。第一步是从用户输入获取草图(第三章)；接着是草图过滤，对草图进行预处理和一些变换(第四章)；最后是草图解释，以得到3D模型的具体描述(或者解释为对模型的操作)。
本文的组织如下：第二章简要讨论了感知在SBIM中的作用，第三到五章详细描述了SBIM流程的每一个阶段，本文包括了对两个重要问题的讨论：表面表示(5.4)和界面设计(第六章)。第八章总结了本领域面临的挑战和一些开放性问题。
2、感知的作用
人类视觉系统非常复杂，我们考察该系统是因为它在我们生活中一直非常容易地运行。对认识科学的深入讨论已经超出本文和我们的知识范围，该领域的一些观点对SBIM系统的设计已经产生了一些影响(隐式或显式)，毫无疑问在今后也会产生影响。毕竟人们对形状的感知影响他们如何进行绘制：感知和交流是我们视觉智能的两个侧面。
我们视觉系统必须考虑的基本问题是“眼睛所看到的图像可以有无数种可能的解释”[10]。考虑一个最简单的仅包含一个点的草图，尽管我们已经知道这个点准确的2D坐标，然而这个草图可以解释为任何一个经过该点和观察者眼睛的直线上的点的子集。图3示出了非平凡(non-trivial)线画图形问题，其中展示了三种与立方体具有类似投影的物体，这类物体可以有无数种。尽管我们大脑的逻辑部分可以相信绘制的内容不一定是立方体，但是我们的视觉部分并不一定这么认为。我们尽可能多地尝试，这个物体却总是被看成是立方体。这一实例可以说明我们视觉系统的一些简单的支配规则。
我们如何把图3解释为立方体，而不是其它无数种候选呢？我们可以观察图3中三个混淆模型，这三个模型的轮廓线都可投影为类似于立方体的投影，但只有立方体本身符合我们的视觉规则。Hoffman[10]将其它的候选称为“无意视图”(accidental views)，因为视点的微小变化都会揭示这些模型不是立方体。换句话说，“无意视图”并不稳定(unstable)，而物体的大部分视图在微小变化下仍然是稳定的。我们的视觉系统更偏向于稳定的解释。
现在我们考虑艺术家正准备绘制上述的一种非立方体物体。他们会不会选择从“无意视图”绘制这个物体呢？并不一定，因为他们自身的视觉规则会发觉这是一个立方体。因此，尽管可以有无数种方式来重构一个绘图，“自身的视觉系统是有偏的。它只构建那些符合规则的3D世界”[10]。
视觉规则可以帮助我们解释从未见过的图像，但是它们也会限制我们，使我们只看到最简单的物体。我们的记忆中有非常多的形状用于解释各种图像[12]，并应用于从未见过的复杂事物。例如，当看到运动汽车的一幅图像或者仅仅只是轮廓，我们可以很快的判断出其属于汽车类别，并推导出其近似的几何、对称以及大小信息。
这点突出了识别(recognition)和重建(reconstruction)的一个重要区别[13]：重建是指根据物体的2D表示创建该物体完整的3D几何信息；识别是一个类似但又截然不同的任务，即基于形状记忆根据物体的一幅图像判断其所属的类别。换句话说，如果视觉记忆可以识别出一个形状，我们可以更简单的重建该形体。否则，对物体的重建将依赖于视觉规则系统。
对称是许多物体的另外一个重要属性。从2D表示中发现或推导对称性可为3D重建提供非常有价值的信息。这里不仅包括“真”对称，也包括对称3D物体的任意投影。Tanaka等[14]讨论了三种对称：真实对称(real symmetry)：对称轴是图像平面内的一条直线；斜对称(skewed symmetry)：对称轴是穿过图像平面的一条直线；一般对称(generalized symmetry)：对称轴是3D空间中一条自由线。图4展示了这些概念。
感知的一些概念可以帮助我们理解SBIM面临的挑战以及设计中所要做出的决策。在第五章中我们将看到SBIM系统基于视觉记忆和规则处理简单图像中模糊性。在第8章中我们也会看到，理解我们的感知也会提高SBIM系统所需要的基于软件的感知。
3、草图获取
SBIM系统的最基本操作显然是从用户获取草图。基于草图的输入设备的一个关键特性是支持自由手绘输入。标准的鼠标符合该定义，但是更类似于在纸上自由绘制的设备(如平板显示器)可以更好地帮助用户进行绘制。此外，显示和输入耦合在一起的设备更适合于自然的交互(如图5)。
实际的纸笔是一种非常有表现力的交流媒介。用户不仅可以使用整体的构成也可以通过压力和笔画的风格来表达信息。从用户角度看，这种媒介通过纸的质地纹理提供用户反馈，用户可以感受到笔在纸表面的刮擦(例如：在餐巾纸上绘制会有一种与普通纸所不同的触感)。
有一些研究致力于将上述各方面转移到数字领域。目前许多平板设备具有压力敏感性，其不仅仅可以提供笔端的位置信息，也可以提供用户在平板上的压力大小信息。一些设备还提供笔的方向性数据。触觉(Haptic)设备[15]是一种更新的研发成果，其可以通过笔设备本身提供用户直接的反馈，如：低频振动以模拟笔和纸之间的摩擦。另外一些可用的输入设备包括平板显示器[16]，甚至虚拟现实设备[17]。
这些设备都致力于提升用户的沉浸感，但它们往往又比较笨重并可能降低沉浸感。例如，触感输入笔被附着到胳膊上以提供力反馈，但这种方式又降低了设备与笔的类似程度。随着这些硬件越来越紧凑、便宜以及具有真正的沉浸感，越来越多的人会使用它们。
可以认为最终最逼真的界面应该是真正的纸笔与一些主动数字化能力的结合。现有一些商业产品提供对文字和图形的自动数字化[18]，但到目前为止支持3D重建的几乎没有。
离线扫描草图也可作为一种输入，但是这种方法更类似于计算机视觉中图像识别问题。这种方法在某些特定领域应用可能会有效，如：建筑工程图纸扫描。但对于一般建模任务而言，这一方法非常复杂，目前也缺乏鲁棒的解决方案。交互式系统通常更可行，它可以提供用户更多的信息(绘制顺序、速度等)以及不断的反馈。在本文中我们仅考虑交互式系统。
3.1 草图表示
一个基于笔的输入设备至少需要提供2D坐标系统中的位置信息，通常采用窗口坐标。不同设备的采样速率会有所不同，但无论如何，采样位置都表示连续运动的分段线性近似(图6b)。采样点在间隔上是不规则的，由绘制速度决定。用户在接近拐角处会更加小心，相应的采样点会更加密集，这一事实可用于确定草图的“关键”部分[19][20]。
我们把笔画看作是一个时序的点序列
由于图像处理领域已有大量研究，一些SBIM应用选择基于图像的笔画表示，如图6c所示，笔画被近似表示为一个像素网格。随着输入设备在虚拟纸上移动，它在纸上留下了“墨水尾巴”。基于图像表示的优势有：固定的存储大小以及自动多笔画混合。但是其中草图的时间特性等一些可用的辅助信息被丢失了。
在SBIM系统中，“画布(drawing canvas)”这一概念[21][22]被用于将一幅草图嵌入到3D世界坐标系中。最简单的画布定义是指定一个特别的平面，如：x-y或用户指定的平面，并将草图投射到该平面上(例如：将深度或z坐标的值设为0)。活动视平面(active view plane)也可以像画布一样很好的运行，允许用户变换视点从多个角度进行绘制(深度仍然不受约束)。假定输入的笔画是平面对称的并反转视投影，每一个对称的3D曲线是可重获的(recoverable)[23]。最后的变换是基于当前视点将草图投射到一个已有的3D模型(图7)。
一些SBIM系统被设计为面向非经常用户或入门用户，而不是专业用户。为了帮助入门用户进行草图绘制，画布可被替换为图像，用户在图像上进行绘制[24][25][26][27]。图像可被用于辅助绘制草图，其中输入的笔画被附着到图像的边缘[25]。
4、草图过滤
在试图解释一幅草图之前，有必要进行一些过滤。原因之一是输入中不可避免的包含一些噪音或者错误的采样点。Sezgin 和Davis[28]给出了两类误差来源：用户和设备错误。绘制技术不熟练，或轻微抖动都会使用户画出不直的线段和不平滑的曲线。第二种错误源是“数字化噪声”，其发生于机械硬件设备对输入进行空间和时间量化的过程：“一个传统的数字化平板……分辨率可能低到4-5dpi，而扫描图像的分辨率达到1200-2400dpi。由于用户有时绘制速度很快以致即使设备采样率较高(如100Hz)也只能采集到少量的点(每英寸)”[28]。
即使用户更加仔细绘制，设备错误和采样问题也仍然存在。因此，基于草图系统的输入通常并不是用户意图的完美描述，在进行解释前必须进行“清理(cleaned up)”或者过滤。这一过程可以减少噪声以得到在后续工作中更便于使用的表示形式。下面我们将介绍一些在SBIM领域中常用的过滤方法。
4.1 重采样和平滑
由于输入设备和绘图速度的不同，原始输入笔画采样点之间的距离也不同。重采样(resample)是一种降低输入笔画数据噪音的方法。重采样过程可在绘制过程中同时进行，舍弃一些与前面采样点距离低于一定阈值的采样点，并对样本点之间距离多于一定阈值的情况进行插值。这一过程也可以在笔画绘制结束后进行。根据具体应用的实际需要可以选择线性或者平滑插值(图8a所示)。
重采样的一个极端形式是折线(或多边形)逼近，只保留少量采样点，这样可以降低笔画的复杂度(图8b)。例如：在Teddy[29]系统中将笔画的首点和末点相连以构成一个闭合多边形，同时对笔画进行预处理以使得各边的长度为一预先定义的固定值。另一种简单方法保留笔画的每个第n个点(n-th)。这些方法适合于平滑的输入，否则不会得到令人满意的结果(样本分布不基于局部笔画特征，如边角)。
在通常情况下，鲁棒的算法会对由于拟合引入错误数设定一定的范围，在较平坦的区域保留较少的点，在细节较多的地方保留相对较多的点。例如，最大最小法[30]使得任一点到拟合直线的最大距离保持最小。有一些严格的计算几何方法[31]可以解决这一问题，但是它们只使用草图输入的位置信息，而草图的时间信息可以用于找出笔画上的感知重要点，如边角。例如，Saga[19]使用绘制速度来找出“分割点”，并提示用户确认不确定的分割点；Sezgin等[20]使用曲率(最大值)和绘制速度(最小值)来确定边角点。
即使在重采样之后，噪声采样点仍然可能存在。平滑算子可以用于降低噪声，其代价是可能会隐藏输入中真实的中断点。此外还有一些技术，包括对每一个采样点使用局部平均过滤器(也就是将每一个样本点替换为其相邻点的平均值)[32]，或者Gaussian过滤器(中心加权平均)[33]。
4.2 拟合
在重采样或平滑之后，草图中仍会有大量冗余的采样点。将草图拟合为其它表示具有双重作用：简化输入以及简化其与其它草图进行比较。事实上，曲线拟合在一些SBIM系统中非常必要，其中重建的表面基于构建型曲线(如旋转的曲面)。
曲线拟合是一种简化方法，相比多边形拟合其错误率更低，但是需要更多的计算量。最小二乘方多项式拟合[34]是一种可选的解决方法，但是参数形式如Bézier[35][36]和B样条曲线[37][38][39]是更可取的。图8c举例说明了样条曲线拟合。
最近，SBIM系统使用了细分(subdivision curve)和变量隐式曲线(variational implicit curve)方法。Alexe等[32]使用Haar小波变化以得到多尺度的笔画表示；Cherlin等[40]对原始笔画采样点使用反Chaikin细分将笔画拟合到细分曲线，有效地降低了数据的噪声；Schmidt等[16]从输入的草图中推导几何约束并拟合到变量隐式曲线。
有很多草图输入实例中同时包含分段线性和平滑的部分。将草图的直线部分和曲线部分进行分割，并对前者进行折线拟合以及后者进行平滑处理[20][36][41][42]，有益于系统的后期处理。例如，Sezgin等[20]使用输入草图的速度和曲率信息进行折线拟合，然后对拟合误差率较高的直线段使用立方Bézier曲线进行拟合，如图8d所示。
Yu[43]指出由于样条曲线在高层次很难进行比较，使用一些基本图元(如：矩形、椭圆和圆弧)进行拟合效果会更好；这也是Saga[19]采用的方法以对自由手绘CAD系统中的形状进行拟合，但是系统也需要用户判断和修正标注。基本图元拟合方法已经在一些SBIM系统[44][45]中得到采用。
上面讨论的所有技术都可以说是在局部或者笔画层次进行操作。草图规整化(Sketch Beautification，借用了Igarashi等[46]提出的术语)是一种在全局层次推导笔画间几何约束(如：线性、平行、垂直、对称等)的技术(图9)。举例来说，当绘制矩形时，系统可以使用直线段拟合每条边，同时推导相邻的边应具有一定的夹角。草图规整化过程可以交互式进行[46][47][48]，也可以在草图绘制结束后批处理进行[49]。
4.3 重绘
拟合方法最适合于有一定精度需求的应用，如：工程性绘制。在强调自由绘制以及对用户意图很少做假定的应用中，拟合有可能不经意地破坏草图的一些重要信息。在这种情况下，用户应能够绘制他们确切想要的形式，在错误出现时用户自行进行修正。
“重绘(Oversketching)”是一种常见的用户界面元素，用户在绘制过程中出现错误时，系统允许用户在错误区域仔细地重绘，系统找出后续笔画影响区域，粘结新的部分并平滑新旧片段以更新草图(图10a)。2D空间的重绘可在草图解释前进行[20][51][52]，系统也可保留原始草图以便“三维重绘”过程使用(5.3)。
当草图中有重叠笔画时，设计者会采用另一种重绘形式，即：将这些重叠笔画合并为单一的对象(图10b)。一些SBIM系统允许这种多笔画的输入方式，系统自动将这些笔画混合到一起[27][50][53][54]。在笔画空间方法(stroke-space approach)中，笔画间的几何关系被用于混合笔画。例如：Pusch等[50]使用层次化空间划分方法将多个笔画分成局部可定向的片段，然后使用B样条曲线进行拟合；在基于图像的方法中，笔画“自由”地按照用户绘制的样式进行混合；文献[16]则提出了一种半自动化方法：用户指定哪些笔画可以被混合到一起。
5、SBIM中的草图解释
草图得到充分过滤后，最后一步是解释草图，将其映射到一个3D建模操作。我们使用解释(interpret)这一词，即，为草图赋予意义。与从菜单选择一个命令不同，自由手绘输入具有固有的模糊性(多种解释)。用户的绘制意图是什么？输入是否是合法和一致的？草图如何映射到一个建模操作？这些是SBIM系统需要回答的问题。
上述问题有多种解决方法，但我们可找出其中一些公共成分。我们基于建模操作的类型对SBIM系统进行分类。最重要的类别是从输入草图自动创建完全3D模型(5.1)；此外，一些重要任务包括使用笔画增加现有模型的细节(5.2)及变形处理(5.3)；对3D物体进行建模有多种曲面表示方法，每一种都有其优缺点(5.4)；最终，一个精心设计的界面应该在正确的时间选择正确的解释(第6章)。
具有了多种解释功能后，一个完全的SBIM系统可用于建模流程中各个步骤，包括从原型化到微调(fine-tuning)的全过程。由于分类的主观性，有一些系统可能不能确定的归类到其中某一类。在下文中，我们以上述类别为主线，对草图解释进行概览并讨论相关工作。
5.1 模型创建系统
模型创建系统(model creation system)试图从2D草图输入中重建3D模型。我们将所有的创建系统分为两类：唤起型(evocative)和构造型(constructive)。二者区别在于：构造型系统某种程度上是将输入草图直接映射到输出模型；唤起型系统则利用输入草图来对与输入类似的内置模型类型(built-in model types)进行实例化。
这只是SBIM可用分类标准的一种，与重建和识别的区别相对应。唤起型系统首先根据一组模板识别草图，然后使用模板重建几何模型；构造型系统则试图直接重建几何模型，没有识别步骤。换句话说，唤起型系统与视觉记忆类似，而构造型系统更多的依赖于规则。
唤起型系统使用模板对象来解释笔画，其表现能力由模板集的大小决定；构造型系统直接将草图映射到模型特征，其表现能力由重建算法的鲁棒性和系统接口揭示潜在模型的能力(即：模型映射函数的泛化或映射机制的拓展能力)来决定。(Because evocative systems use template objects to interpret strokes, their expressiveness is determined by the richness of the template set. Constructive systems, meanwhile, map input sketches directly to model features; therefore, their expressiveness is limited only by the robustness of the reconstruction algorithm and the ability of the system’s interface to expose the full potential.)
当然，这二者间有一定的重叠，主要表现为：唤起型系统可以利用模板对象变形来匹配用户输入草图(deform the template objects to match the input sketch)[26]，而构造型系统也使用一些领域相关知识(exploit domain-specific knowledge)来指导重建。
5.1.1 唤起型系统
唤起型系统内置有一定的3D图形“记忆”，可以用于指导解释输入的草图。例如：一个面向人物创建的系统中，其形状记忆可能用于确定草图的哪一部分属于头部、躯干等等。由于形状和相关的比例是可预知的，3D构建变得更加简单。
这类系统可分为两种：图标型(Iconic)系统和模板检索型(Template Retrieval)系统。
(1). 图标型系统
这种系统仅从一些“图标性笔画”推断最终的3D形状[44][48][60]。Zeleznik等的SKETCH系统[44]是一个典型实例，该系统使用简单的笔画组定义基本的3D物体。例如：三条相交于一点的直线表示一个立方体，立方体的维度由这些笔画确定(如图11)。
Jorge等提出的GIDeS系统[45]也采用了类似的设计，系统提供了一系列基本物体的模板和一系列工程设计的参数化模板(5.1.2)。
Igarashi和Hughes提出的Chateau系统[47]也可从少量笔画推断形状，尽管这种形状不是完全自由形状。系统面向建筑结构的限制允许对输入作一些假定，如：平面、对称以及正交等；系统的交互特性也使得识别过程变得更加简单，由于用户可以即时看到系统如何解释他们的操作，就可以避免许多有问题的情况发生。
(2). 模板检索型系统
另一种唤起型系统是从模板库中检索模板对象[26][63][74][78]。相对于简单的基本对象，这些模板更加完整和复杂。从用户的角度来说，他们必须提供目标对象的一幅完整而有意义的草图，而不仅仅是一些唤起性笔画。
这种方法比推断法更容易进行扩展，因为系统新特性的添加恰如向模板库中添加新对象那样容易。相反，由于构造单元(形状模板)更加复杂，因此，可能无法通过组合模板对象来得到特定的结果。
在基本的匹配算法中，必须考虑输入和输出端增加的复杂度。基于检索的系统面对2D草图与3D模板的匹配问题，评价它们在3D空间中的相似度需要对草图进行重建，这是系统需要解决的根本问题。因此，系统通常从3D模板中抽取2D形状来进行比较(也有其它一些方法，如：图匹配[78])。
Funhouser等[63]根据他们“人们通常从一个相当一贯的观察方向集绘制草图”的观察结果，采用从13个视点得到的物体投影轮廓来定义一个对象的形状描述子，系统通过对每个轮廓进行图像变换(image-based transformations)而抽取出一个定长而具旋转不变性的特征来创建对象模板，然后，输入草图通过采用相同的图像变换并与存储的模板进行比较来与某个对象进行匹配。此外，为提高识别率，用户可以至多从3个不同的视角绘制同一个物体。
计算机视觉领域对2D形状匹配问题进行了大量研究，多数方法通过基于图像的方法对侧面(silhouette)和轮廓(contour)进行比较(Veltkamp[79]很好地介绍了这方面内容)。SBIM中基于图像的技术舍弃了草图中潜在比较重要的时间和其它一些辅助信息(压力等)，但其也受益于现有形状匹配的大量成果。Funhouser等[63]也赞成使用基于图像的匹配，因为这种方法使用户可以提供“片段化草图标记(fragmented sketch marks)”(相对于基于笔画系统中需要长而连续的笔画)。按照近来批处理重绘的一些工作，将片段化草图混合成单一轮廓(blend fragmented sketches into a single contour)已经不再是问题了。
Shin和Igarashi提出的Magic Canvas系统[74]采用模板检索方法进行场景构建(如图12)。他们也从每个模板中抽取一些轮廓(16个)，但是，他们使用基于傅立叶的方法进行草图匹配。使用多个物体构建场景不仅需要模板检索，也需要修正场景中每个物体的位置。据此，Magic Canvas系统旋转和缩放物体以匹配输入草图的方向，同时推断简单的几何关系(如：灯放置在桌子上)。系统也需要用户的干预以初始化对场景中子草图的检索过程并要从多个候选集中选择合适的物体。
Yang等[26]提出了类似的基于模板系统，他们使用过程化描述模型(procedurally described model)，而不是基于网格的模板。以一个马克杯为例，他们用模板来描述如何从简单的基本元素组成一个马克杯，而不是使用马克杯网格作为模板。这种方法的优点在于模板可通过形变来匹配输入草图，而不只是仅用模板的一个实例。然而，过程化模板定义(procedural template definition)使得新模板的添加比基于网格方法要困难得多。
Lee和Funkhouser[77]近期提出的方法偏离了模板模型的概念，而更接近于模板部件(part)。以飞机为例，系统包含了机翼、引擎等多个模板，而不只是一个完整的飞机模板。使用草图用户界面，用户可以通过在模型上近似位置绘制某一部件的轮廓而将部件添加到已有模型上，系统找到匹配的部件，并在用户选择合适的匹配后将部件组合到已有模型中，且自动地相对于其它元素放置。
5.1.2 构造型系统
纯粹的重建与“识别再重建”相比要困难得多，因为后者使用了预先定义的知识以定义草图的3D几何信息，一定程度上避开了模糊性问题(模糊性问题在识别阶段仍然存在)。构造笔画系统必须仅仅根据规则从草图重建3D物体，因为重建是一个非常复杂的多学科问题，现有许多研究都在尝试提出解决方法。我们介绍构造型系统的三种主要类型：机械性物体、光滑物体以及从多视角绘制的物体。
(1). 工程设计系统
我们的视觉系统可重建机械的(硬边界)和光滑的物体，或介于二者之间的物体。然而，基于草图建模应用通常着重于其中的某一方面，因为设计层次上选择光滑或非光滑的解释将减少草图可能的解释。
设计和描述工程性物体(即，大部分是平坦的)是计算机建模在工业中的一个重要应用。因此，在SBIM研究早期就引起了研究者的注意[80]。Lipson和Shpitalni[58]提出的基于最优化方法封装了许多技术，每一个输入笔画都假定表示3D线架模型中一条边，而同时产生的每个端点是模型的顶点，同时，假定草图表示该物体在平行投射下的投影。这些约束给用户了少许限制，但可以极大降低系统的复杂度。在检测2D草图中一些重要的关系(平坦、拐角、等距、正交等)后，通过对每个顶点深度未知的一个线性方程进行优化来完成重建过程。
从线画图形重建3D几何形状在计算机视觉领域已经有所研究。线标注(Line labeling)[81]是一种对图像中线段进行分类的算法，线段类别有凹的、凸的或轮廓线，定义了几何约束以供3D重建。显然，我们可以直接使用该方法处理草图输入。
线画图形重建的一个困难是如何确定点、角和边的位置。在交互式系统中，这些可以在用户绘制笔画的过程中确定，然后重建过程可以采用“批处理”的方式进行[11][17][49][68]。
对称性是工程性物体的一个公共属性。尽管难以进行检测，但是在重建构成中可以使用一些关于对称的知识以减小搜索空间[62][64]。
线标注方法的一个不足在于对曲线段的支持有限。Varley等[67]使用两阶段方法：在第一阶段中，用户只使用直线绘制一个总体模型结构；第二阶段中使用曲线段对模型进行重绘，从第一阶段重新构建的模型作为重建的模板。Masry和Lipson[11]也使用了两阶段方法，但是他们的方法对用户隐藏了细节，系统通过分割自动抽取线画表示。
除批处理方式外，系统也可采用交互式方式，在用户绘制草图过程中重建3D模型(如图13)。该方式下，用户可立即看到运行结果，即时修正成为可能。系统也可采用更简单的重建规则。最通用的方法是挤压(extrusion)方法，将一个剖面曲线(profile curve)沿着某一向量(或曲线)“推过”空间[16][36][53][60][75]，如图14所示。该技术非常适合于创建具有硬边界的模型，如：立方体(由一个正方形挤压)或圆柱体(由圆挤压得到)。
挤压方法与唤起型系统有点交叉，因为用户只需要绘制剖面曲线以及挤压向量。然而其重建过程并不基于或限于识别：用户可自由创建相应领域中近乎无限多的物体，而不受限于模板集。
(2). 自由设计系统
尽管一些工程设计系统支持曲线笔画，但是其重建仍然基于直线型表示。平滑、自然的物体的重建需要不同的方法。
有观察表明：人类视觉系统偏向于将平滑的线画图形解释为3D轮廓[10]。因此，多数构造型SBIM系统选择将笔画解释为轮廓线[16][29][32][36][40][55][56][66]。（轮廓可定义为表面法向量与视方向垂直的物体上所有点的投影，将物体的可视部分从不可视部分分开(图17所示)。轮廓不仅仅包括侧面轮廓(silhouette outline)，也揭示了一些内部特征，如：脸的下巴和鼻子部分。）
由于有多个物体对应于同一个给定轮廓，需要给出进一步的假定以重建草图。构造型系统的一个关键思想是根据一些内部规则选择简单图形，然后让用户完善该模型。
基于骨架的方法在“从轮廓草图创建3D模型”研究中非常流行[16][29][32][36][40][51][66][72]。骨架(skeleton)可定义为“与最近轮廓点等距的线(the line from which the closest contour points are equidistant)”，如图15所示，它提供了一个距离场(distance field)，可帮助确定地在3D空间中决定一个曲面(determine a surface in 3D unambiguously)，(以使得曲面到骨架的距离与轮廓线点到骨架的距离相关(such that the distance from surface to skeleton is related to the distance of contour points to the skeleton))。
找出准确骨架所花费的代价比较昂贵，但可以近似地从Delaunay三角化形式[82]中抽取骨架：连接相邻非边界三角形的中心(如图15b)，这也称为弦轴(chordal axis)变换。，Levet和Granier[83]最来提出了一种从少量伪分枝(spurious branch)生长出整个骨架的骨架抽取方法。
如何才能使用骨架生成3D模型？根据骨架结构的复杂度可以有多种方法。最简单的非平凡(non-trivial)骨架是一条直线；在一个对称的草图中，骨架是一条与对称轴对齐的直线；为生成曲面，草图可以绕骨架旋转而创建一个旋转曲面[16][36]。一条简单的笔画也可以指定轮廓，通过固定或用户手绘的旋转轴定义出曲面。
Cherlin等[40]扩展了这一思想用来生成一般旋转曲面，其中骨架是由两条笔画的中间轴确定(作者把这种构建称为转动混合曲面(rotational blending surfaces))，如图16a所示。他们的系统还允许用户提供定义自由横截面的第三条曲线，提升了这种构造的表现力。
这些构造假定输入的曲线在同一个(绘制)平面中，且生成相对该平面对称的物体。另一个更具挑战性的方法是将输入的草图看作对称3D曲线的投影，即：绘制的草图表现了歪斜的或者一般对称。Tanaka等[14]在早期提出的方法中假定两个输入笔画在3D空间中是对称的，并通过一些额外的用户输入确定对称轴以鉴别每个笔画的对称顶点，然后，将曲面重建为连接笔画的一般圆柱体(a general cylinder)。Kanai等[57][84]提出了一个更鲁棒的对称检测草图系统，该系统可以从多视图检测和协调(reconciling)对称性，并使用B样条曲面片重建曲面。
这些参数化构造方法的一个缺陷是有限的拓扑性，最终的结果(物体)总是可在2D平面上进行参数化，其骨架也不包含分枝。当骨架包含分枝时，就需要更鲁棒的方法。
对于简单(如不相交)闭合轮廓而言，膨胀法(inflation)是生成似是而非(plausible)3D模型的一种确切方法(an unambiguous way)。例如：Teddy系统[29]对轮廓进行膨胀，图16b展示了一个典型结果。
一个轮廓的骨架表示(skeletal representation)也自然地集成了一种隐式曲面表示(implicit surface representation)。在Alexe等[32]提出的方法中，球形隐含图元(spherical implicit primitive)被放置在骨架的每个顶点，当这些图元被混合到一起时，结果产生一个平滑的曲面，其轮廓可映射到输入的草图。其它一些系统[16][51][61]采用草图轮廓来定义隐式函数的约束，以取代变量隐式曲面[85]。
对于诸如包含自相交的非简单轮廓而言，简单的膨胀方法并不适用。轮廓将物体分成面向观察者和与观察者相对的两个部分，在非平凡物体中，也可能会出现曲面的部分面向观察者，但对于观察者而言并不可见，因为该部分被曲面的其它更靠近观察者的某一部分遮蔽了。图17演示了这样一个实例：脖子的轮廓被下巴挡住了，注意到脖子的轮廓在下巴后方穿过，可以看到在投影轮廓中有一个T型形状(称为T连接)，下巴的轮廓突然中止(称为尖端，cusp)，T连接和尖端意味着隐藏轮廓的存在。Williams[86]根据这些提出了一种推断图像中隐藏轮廓线存在性的方法。
Cordier和Seo[70]使用了Williams提出的轮廓补全算法(contour completion algorithm)支持包含T连接的复杂轮廓草图。隐藏轮廓可以根据相对深度进行排序，据此将草图放置在3D空间中，并对其进行膨胀(无自相交)；为重建曲面，作者使用了类似于Alexe等提出的隐曲面方法。Karpenko和Hughes[55]也使用了Williams的算法，该算法同时支持T相交和尖端的处理(如图15c)；他们使用了一种不同的重建方法：首先创建“拓扑嵌入(topological embedding)”，接着，构建“ (mass-spring)系统 (每条网格边具有弹簧)以得到光滑的形状，并找出平滑的均衡状态。不幸的是，质量-弹簧最优化需要细致的参数调整(parameter tuning)，且对于自相交也无法控制。
最后一种重建轮廓草图的方法是拟合(fit)尽可能平滑的曲面。曲面拟合将输入笔画解释为形状的几何约束，“曲面穿过该轮廓”；轮廓的外法线也约束该曲面法线，这些约束定义了一个最优化问题：在无穷的候选中，找出一个满足这些约束的合适匹配(of the infinite number of candidates, find one suitable candidate that satisfies the constraints)。诸如光滑度和薄板能量(thin-plate energy)[86]等额外约束将系统“推向”解决方案。Nealen等提出的FiberMesh系统[56]使用了非线性优化技术以生成平滑网格，同时也支持形状折痕和皱摺(sharp creases and darts)。
5.1.3 多视图系统
FiberMesh中使用的曲面拟合技术的一个优点是可以添加额外的笔画以定义曲面的更多约束，甚至可以在不同的绘制面而不只是初始的轮廓上。也就是说，用户可以在3D空间中绘制草图以定义一个笔画网络，这些总体定义出一个曲面。这是多视图草图绘制的一个实例。
FiberMesh系统是交互式的，曲面在每一个草图输入后可即时可视化；此外，也有一些多视图草图系统以批处理方式运行。在多视图草图系统[17][21][25][71][73]中，笔画通常被解释为物体的边界。例如：Das等[21]提出的系统使用曲线的3D网络定义物体的边界，并进行平滑插值以重建模型；Rose等[73]也使用3D边界草图来定义光滑的平坦变形。
Karpenko等[65]提出了一种基于“极线(epipolar lines)”的交互式草图系统。在绘制平面中绘制了一条笔画后，用户可以旋转视图并看到直线沿深度轴伸展(深度模糊性的可视化)；进一步输入的笔画被投射到这些直线上而固定深度成分(fixing the depth component)。通过这种方法可以使用草图创建复杂的3D曲线，作者也承认这一过程的是“认知复杂(cognitively difficult)”的。
在允许用户从诸如前视图、侧视图和顶视图等多个视角提供物体多幅草图的系统中[60][63]，多视图草图绘制已经在更文化层面上(in a more literal sense)被研究。这种情况下，重建过程需要系统找出各视图之间的相关性以构建3D曲线网络。
由于人类视觉系统是围绕2D刺激而建立的，3D空间绘制草图过程如果缺乏交互式反馈将非常复杂。因此，多数系统采用迭代的建模范例，也就是说，用户重建一个简单草图，对模型进行旋转，然后绘制新的部件或变形，直至得到期望的结果。
5.2 增加(Augmentation)
在前文中我们提到，从2D草图创建3D模型是一个非常困难的问题，其唯一可取的解决方法是重建。然而，在现有的模型基础上创建更精细的细节相对简单一点，因为已有的3D模型可作为笔画映射到3D空间的参照(如图7)。将笔画投射到已有模型上依赖于一些确定的图形学技术，如：光线衍射(ray-casting，将光线从眼睛位置衍射到绘制平面的笔画点)或者反投影(unprojection，转置观察矩阵，然后使用z缓冲找出深度)[87]。增加过程可以采用表面的(surficial)或附加的(additive)形式。
表面增加允许用户在模型的表面绘制特征，如：创建棱边等[56][87][88]。在草图被投影到一个表面后，系统沿着草图方向在表面创建特征。通常该表面沿着法线方向放置，适合于创建如纹理等细节(图18a)。在表面优化方法中手绘的线条也可以当作新的几何约束进行处理[56]。
表面式增加的进行通常不需要变化底层的曲面表示。例如：在三角形网格中创建一个棱边约束，现有的模型边可以被用于逼近草图特征以及沿着法线方向被放置以创建视觉特征[87][89]。
附加增加使用构建性笔画定义模型一个新的局部成分，与其它一些附加笔画一起标明新部件在何处与原始模型连接[29][56]。例如：Teddy[29]中挤压操作子使用圆形笔画初始化操作以及定义待挤压的区域；然后用户绘制新部件的轮廓，并被膨胀和附着到原始模型上(图18b)。Schmidt等[16]研究了使用简单blending方法(由一种隐含面提供)进行附加增加，也引入了连接点处光滑度的参数化控制。他们的系统不需要显式描述连接点，因为隐含面在紧密接近的地方自然会混合到一起。附加增加只影响原始模型上连接点邻近的部分。
这两种增加类型一个主观上的区别是增加的范围大小：表面增加是小范围增加，只需要简单的变化下面的表面，而附加增加是在原始模型范围上的增加。当系统允许更多的显著面(pronounced surficial)增加时这一区别会变得不明显，如Zelinka和 Garland提出的曲线类比框架[90]可以在任意的网格中嵌入2D曲线网络，然后根据一个草图曲线沿着这些曲线移动网格。
5.3 变形
除增加外，也有许多SBIM系统支持基于草图的编辑操作，如：切割(cutting)[56][91][92]、弯曲(bending)[29][39][40][75][92]、扭曲(twisting)[93]、挖掘(tunneling，创建一个洞)[16][56]、轮廓oversketching[40][89][94]、分割[92][95]、自由变形[96]以及仿射变换[97]。此外，与增加类似，基于草图的变形通常有直接和直观的解释，因为已有的模型或场景可以在3D空间中锚定输入的草图。
对一个模型进行切割时，用户只需要旋转模型到一个合适的视角，然后在需要分割的地方绘制笔画。系统将该笔画解释为一个切割平面，即笔画沿着视图方向扫掠(如图19a所示)。挖掘(tunneling)是切割的一种特殊情况，其中切割笔画是一个封闭的轮廓并包含于模型中。挖掘后模型中任何位于挖掘笔画投射范围内的部分都将丢弃，随之产生一个洞。
其它变形方法基于重绘的思想。例如，弯曲和扭曲可以将一个物体变形并将参照(reference)笔画映射到目标(target)笔画，如图19b所示。轮廓重绘也是基于将参照对象映射到目标笔画思想，但在这种情况下，参照对象是从模型本身抽取的轮廓，如图19c所示。
Nealen等[56]支持基把手(handle)的变形，允许物体轮廓可以像弹性物一样被操纵。当一个笔画被“抓住”和拖拽时，笔画会弹性变形并垂直到视平面，从而改变了由笔画所描述的几何约束。当笔画被移动时，曲面最优化算法重新交互式地计算新的合适曲面
FFFD是一种通用的变形技术，其主要思想是将一个控制格放置到物体或场景四周。当格子点移动时，对格子中的物体进行变形，就像操纵一块粘土。Draper和Egbert[96]提出了一种基于草图的FFD界面，其扩展了Teddy的功能，支持弯曲、扭曲和手绘草图。局部和全局的变形都可以由FFD指定。
Kara等[27]提出了一种模板变形系统(如图20)，用户提供概念草图然后手动地选择一个合适的模板与该草图进行匹配。系统使用计算机视觉技术将模板和输入的草图进行对齐，然后用户可以oversketch交互式对模板进行变形。如图20所示：将一个选中的模板物体(b)注册到输入的草图(a)；用户然后描摹草图，交互式对模板进行变形(c)；最终的结果模型为(d)
5.4 曲面表示
选择合适的曲面表示非常重要。每一种表示都有其优缺点需要结合实际应用需要进行考虑，下文讨论一些主要的曲面类型。
参数化曲面(Parametric surfaces)包括NURBS片、旋转曲面[16][36]及rotational blending曲面[40]。这些表示方法都已经得到很好的研究，也可以很容易地整合或者输出到其它建模软件。然而，由于2D参数空间比较简单，单个曲面的拓扑结构被限制到与一个平面同构的形状。构建更有趣的形状(具有分枝结构或复杂的拓扑结构)需要片的相交(crude patch intersection)或者经过仔细排列的多个片。
网格(Meshes)扩展了参数化曲面以得到更一般的拓扑结构，其被经常用于SBIM [21][29][71][83][89]。网格的主要缺点是部分编辑操作难以实现，如混合两个物体到一起。网格质量也是一个问题[59][75][83]，不规则的面会导致不稳定的光照以及面属性计算。尽管类网格描述(mesh-like representation)经常被用于绘制一个物体，在背景中我们需要更灵活的表示。
从建模的角度看，隐曲面(Implicit surfaces)具有多个优点，包括支持层次化建模、弯曲以及布尔操作。然而，它们本质上具有光滑性并带有斑点，同时也难以引入棱边或硬边约束。另一个缺点是不支持直接面操纵，所以不能使用“抓和拽”的建模隐喻。最后，交互性也是一个技术挑战，因为面在绘制前必须离散化为网格表示。不过隐含面表示如果经过仔细设计和实现在SBIM中也取得了好的效果[16][32][51][61]，也可以被用于中间表示以抽取网格[66][83]。
隐曲面可更准确地定义为从隐含体(implicit volume)中抽取的等值面(isosurface)。这种体表示可被用于对更多种类的拓扑结构进行建模，也简化了一些操作如切割[69]的实现。这种表示的缺点与隐含面类似：绘制需要离散化以及对面进行多边形化，也不可能进行直接操纵。
光顺曲面(Fair surface)受限最优化问题处理所得到的结果网格[56][73][86]。用户在不断绘制草图过程中定义了新的约束，解决方案也得到重计算。这是一种灵活的表示也非常适合于SBIM，但是有一些重大的缺点。首先，拟合的曲面往往比较光滑(即使是棱边约束)，限制了表现力。其次，由于曲面是全局最优化的结果，结果曲面有时很难从用户角度(user's perspective)预见。
在SBIM领域，更一般的，在整个建模领域，找出一种可以满足所有建模任务的曲面表示是一个重大的挑战。
6、界面设计
一个完整的建模系统应同时支持多种操作，如创建、增加、变形、plus viewing和绘制控制。每一种操作都表示一个模式或者一种状态。传统的“模式”界面设计需要显式的模式切换，通过按钮、菜单以及键盘快捷方式和修饰符等。例如，在Teddy系统中如要触发弯曲操作，用户必须在绘制相关笔画后点击一个按钮；该动作通知系统下一个笔画是一个目标笔画并执行一次弯曲操作。
在SBIM系统中，一个通用的做法是使用手势(gestural)界面以简化公共操作。手势界面使用简单的自由手绘笔画以触发特定的命令以及(直接或者间接地)操纵对象，它的使用可以避免使用基于菜单的命令描述。尽管没有菜单的情况下新用户可能更适应(没有多个菜单切换的烦恼)，用户仍然需要记住准确的笔画操作映射，这需要对用户进行训练，需要一定的认知负担。手势命令的实例有切割和删除笔画[25]，对象组合[98]，擦除和局部平滑[56]，笔画混合(blending)[16]。
手势识别可以使用用户相关参数值来确定手势命令的种类，这种方法相对比较复杂，最近在该领域出现了一些新的途径。Severn等[97]介绍了一种直接操纵方法(转换笔画，transformation strokes)，在他们所介绍的系统中，用户可以使用简单的U形手势快速缩放、旋转和平移物体。宽度和高度确定了纵横比，笔画的位置和方向确定了平移和旋转。深度始终是一个问题，但场景中的其它物体可用于消除变换后的物体位置的模糊性。在该方式下，物体的不同部分可以快速地装配。
Schmidt等[99]不使用手势直接操纵物体，而是用于初始化操作工具包，然后用户可以与工具包进行交互以操纵物体。例如，一条线性笔画与一个物体相交会初始化平移工具包，其中包括一个可以来回拖放的箭头用于平移该物体。初始化和执行变换操作的便利性使得物体的快速装配成为可能。
草图可以用于建模界面的多个方面，一个纯手势的草图用户界面会带来模式问题(modality problem)。也就是，一条笔画或者手势在不同的模式下可以有不同的意义。例如， Schmidt等[16][76][99]提出的ShapeShop系统中使用手势初始化工具包，但是也支持基于笔画的表面增加，如果一个用于表面增加的笔画与触发工具包的笔画相同怎么处理？只有用户可以知道该笔画的真正意图。因此，当设计手势和草图用户界面时，一个重要的问题是如何提供用户一致和可预测的界面，并且没有模态问题。
这一问题的解决有两种方法。一种是不同模式下的输入是互斥的(例如，笔画A只可能出现于模式X)。在支持自由输入的系统中，这一约束很难实现(例如，如何确保一个特定的笔画不能出现在草图输入中)。另一个更合理的解决方法是侦测模糊输入(即可以在多个模式中都是合法性输入)，提示用户确定其真实意图。这种方法一般被称为建议型界面(suggestive interface)(如图21)。
在建议型界面中，系统识别输入的笔画或草图所有可能的解释(通常称为“期望列表”，expectation list)，用户从这些解释中选择代表其意图的操作。期望列表不仅可以用于确定手势输入[45][76][100]，也可以用于系统的其它阶段如模型创建[16][45]。例如，图21b中列出了对于输入(线和圆)的多种可能性解释。
这些突出了在建议型界面中需要考虑的几个重要问题。首先，一个输入可能会有多个解释，但是很难将所有可能选择展示给用户。取而代之的是，系统应该根据相似度对解释进行排序并提供用户一些最相似的选择。这种方法也可以结合学习的方法以适应个人的使用模式[39][54]。其次，随着基于草图的系统功能性增加，其管理也越来越困难。频繁的弹出期望列表并要求用户干预可能会打扰用户的设计过程。在用户的自主性和用户控制之间如何进行折衷是一个挑战。
6.1 手势识别
在手势界面中，系统需要识别用户的输入，也就是说，如果用户绘制手势A，系统可以通过将其与模板
基于手势的用户界面的一个基本点是设计鲁棒和一致的手势集(图22)。由于“手势的感知相似性与可计算的特征(如弯曲度)相关”，对于一组明确的手势集，通常简单的识别方法就已经足够[102]。因此，我们需要仔细设计手势集，使其达到独特清楚、可记忆以及便于绘制的要求。
现有许多识别手势的方法。早期由Rubine提出的方法[103]使用几何属性(如初始角度和闭包大小)来比较笔画。基于图的方法根据草图中笔画间的空间关系(如相交和有公共端点[104])判断相似性。其它一些方法使用领域相关的知识抽取笔画的高层理解，如图式表示[105]或标定不同成分[106]。Hammond 和Davis[107]提出了一种草图识别“语言”，模板对象可以由其组成的图元和图元间的集合约束进行描述，例如，stick figure由一个圆连接一条直线构成，其本身被连接到四条其它直线。
手势匹配从轨迹分析中借鉴了一些概念，这二者都是处理运动物体的行为。在草图中，每一个笔画捕捉输入设备的轨迹。傅立叶描述可能是轨迹分析中最常用的技术[108][109]，将轨迹(等同于笔画)的2D位置信息分割为两个信号，并被转换为一个定长的特征，对每一个信号采用傅立叶变换，并保留一定数量的最重要的傅立叶系数。在这种方式下，傅立叶特征可以简单的使用element-wise距离度量进行比较。傅立叶描述的一个弱点是失去了输入的位置特征(locality of features in the input)。小波方法[110]使用小波解决这一问题，但是其受制于信号长度的约束。
手势识别已经成为用户界面领域研究的一个焦点。$1识别器是近期较流行的一种方法[111]。用户输入的手势首先进行重采样以消除绘制速度变化，然后沿着“指示角(indicative angle)”排列以提供旋转不变性。最终手势缩放到一个单位区域。模板都经过同样的变换，该方法使用point-wise距离比较两个经转换的笔画。该方法在训练最小和计算少的情况下具有很高的性能，也比较适合于基于手势的界面。
与一般的形状匹配比较，手势识别器的要求比较单一：只需要分辨出数目有限的区别明显的输入，但是必须尽可能快速。因此，基于草图的就系统经常牺牲精度以提高速度。例如，Teddy系统[29]使用笔画的简单几何属性，如笔画长度与凸包(convex hull)周长的比值，以匹配输入的笔画和操作(参见5.3节)。Yang等[26]从笔画中抽取一些简单的度量，包括直线长度、角度、自由弧的长度以及笔画和其拟合线段之间的区域面积，这些被当作笔画的“签名”以用于识别。最近，Olsen等[101]提出了一种基于量化角度分布的笔画描述方法，在SBIM中使用可以超过一些经典方法，包括傅立叶方法。上述每一种方法对于通用形状匹配而言效果都不一定很好，但是在SBIM的特定领域可能会有很好的效果。
7、应用
到目前为止，我们着重介绍SBIM在基本建模任务中的应用，此外也有一些特定领域的应用适用于使用自由手绘输入。本节将简要介绍草图用户界面在计算机图形学中某些领域的应用。
这些应用可以分为两组。计算机辅助设计应用的目标在于构建最终具有物理表示(physical manifestation)的3D物体。因此，输入草图应当辅助以约束以适应制造工艺的局限性。内容创建应用中所创建的3D模型只会在数字世界中存在，被用于计算机动画、交互式计算机游戏、电影等等。在本领域中，更强调设计者进行曲面绘制的自由性。
7.1 SBIM在计算机辅助设计中的应用
现有的CAD工具着重于表示几乎完整的设计思想和模型。目前，概念草图是2D形式的，然后通过人工使用传统的CAD工具转换为3D表示，这一过程可能需要花费许多星期的时间。这也是设计工业中产品生产周期较长的一个原因。SBIM工具可以更快更自然地探索思想，并支持从早期概念草图直到完成的设计期间3D模型的创建和系统化改进(图23)。
由于很难使用自由形态的实体表示精确的NURBS曲面，工业设计中内容创建是一个非常困难的任务。典型方法引入草图绘制和操纵构建曲线(construction curve)[112][113][114]或特性线(character line)[117]对3D模板进行变形。
机械工程物体的设计也遇到了类似的问题，很难基于草图精确表示部件位置和几何约束。一些系统如GIDeS[115][116]中已经对这些问题进行了讨论，提出了结合图标输入的方法以及动态菜单以支持复杂机械部件的创建。GIDeS使用约束和期望列表支持对物体的精确布置。CEGROSS[118]是一个类似的系统，它使用了一个约束满足引擎以支持用户在透视图中指定具体的机械部件。
自从Cocktail Napkin系统[119][120]出现后，建筑制图和建筑物描述成为本领域的一个研究内容。Esquisse系统[121][122]提供了一种全面的基于草图的建筑建模工具，支持建筑设计师从概念性草图构建3D建筑模型。Mental Canvas系统[22]的目标更多地在于支持概念绘制而不是完全的3D重建，提供了一个可以在多个位面(plane)进行草图绘制的界面，然后将草图通过3D空间“推”到其它画布以创建伪3D表示(quasi-3D representation)。
7.2 SBIM与数字内容创建
随着计算机生成的图像在电影和电视中得到广泛应用，以及交互式计算机游戏的涌现，业界对数字内容创建的需求也越来越高。因此，SBIM等可以提高该产业生产力的技术也受到了较高的重视(图24)。
Harold系统[123]允许用户手绘任意的元素，如地面、树木、建筑物和人物等以创建数字世界。世界几何(world geometry)可近似看作是2.5D模型，即，所有的平面笔画随着摄像头在世界中的移动，以一种视依赖(view-dependent)的方式被重新布置，以给用户三维的感觉。
Bourguignon等[126]提出了另一种类似的伪3D方法。系统的目标是视觉交互而不是曲面重建，绘制的笔画被“提升”(promoted)为3D形态。用户可以旋转视角从多个角度绘制3D物体或给导入的物体创建注释。系统对结果进行非真实感绘制，突出了非精确和非正式的特性。
草图交互界面也可用于虚拟服装设计领域。Turquin等[127]提出的系统中，用户绘制衣服前面和后面的轮廓，系统对衣服的整体形状进行几何推导。衣服的形状以及人物的穿着方式可同时确定。
草图交互界面也已用于人物动画设计，可以使用手绘草图绘制动画序列中特定的关键姿态或位置[128][129][130]。例如，Davis等[128]使用图像处理技术从stick-figure草图中抽取joint position，运用几何和物理约束排除不可能的姿态，然后对人物模型进行变形以匹配草图绘制的姿态。Thorne等[129]允许用户使用一组草图手势(映射到一组预定义的运动，如走和跳)手绘人物运动。
头发由于元素数目的繁多而很难进行建模。使用Wither等[125]提出的系统，用户可以绘制头部一侧的一部分实例头发，系统根据头发的几何和机械属性推导合适的头发模型以适应头皮形状。Malik[131]提出了一种基于草图的发型建模和编辑方法，该方法在3D头皮模型上模拟发型设计操作，如剪、梳、卷和扭曲等。
植物设计也是一个费时费力的过程。植物有复杂的分枝和器官结构，其姿势和空间分布也是多变的。植物世界本身也是多样性的，树木、花以及单茎植物具有相似但是又不同的几何特性。SBIM工具可更快速和更自然地表示植物姿势、分枝结构、器官几何和位置等。
Okabe和Igarashi提出的系统[132]从2D分枝结构草图中推导树的几何信息。Ijiri等[133]使用手势控制主干形状，主干具有递归定义的分枝结构。Zakaria和Shukri[134]使用草图绘制初始的树结构，然后在树冠区域“喷洒”树叶面，树的分枝向树叶方向生长。
Ijiri等[135]提出的系统中，手绘的花瓣和其它元素基于floral diagram的位置规则共同组成完整的花模型。这些花模型然后根据inflorescences diagram进行完整的排列。在其后进行的一项研究中，单个花的器官可以被绘制在处于植物结构的不同方向上的绘制平面上[136]。
Anastacio等[137]基于叶序(phyllotactic)模式使用概念草图进行3D植物布置。另一个更新的工作[138]将概念草图转换为位置函数以作为L系统(L-system)的输入，过程式生成最终的植物结构。
8、挑战和开放性问题
尽管近来我们在SBIM领域取得了实质性进步，但是目前该领域仍然有许多重要的开放性问题和挑战。实际上，计算机模拟人对2D草图的形状感知仍然是一个难以实现的目标。SBIM提供了传统系统更高的可用性，但是其仍然不能完全替代传统系统。现有的SBIM系统只能对有限数目的、低复杂度的物体进行建模，该领域尚有许多工作需要研究以满足实际需求。
8.1 界面
SBIM的一个主要目标是提供一个更自然的模拟传统媒介感觉的界面。在设计的初期，设计者使用真实纸笔进行草图绘制，其先绘制粗略的基本图元以定义物体的总体形态，然后使用许多细小的笔画完成整个草图(图25)。这些笔画定义了最终曲线的概括性描述，设计者可以自由地以任何次序进行绘制，笔画可以相交、断开甚至可以与主题无关系的。然而，多数草图用户界面远远不能称为“自由”，许多限定用户以特定的方法进行绘制，这样会降低沉浸感和使用的方便性。
设计一个与传统界面相比会明显提高可用性的用户界面是另一个挑战。在Maya中，通过浏览三级菜单项来找到所需要的操作可能会让人感到厌倦，但用户一旦找到并触发该菜单，其运行结果是可预测和确定的。另一方面，草图用户界面很大程度依赖于详尽的(elaborate)猜测和推导用户的意图，如用户的输入更可能是操作B而不是操作A。系统如果做出错误的选择，用户会有很大的挫败感。Landay和Mayers介绍他们的系统时指出：“缺少充足的对识别的用户反馈是多数混乱的来源”[98]。因此，设计SBIM系统时如何考虑算法和界面元素的组合，以提供用户稳定可预测的操作是现有研究的一个巨大的挑战，其中包括如何识别复杂的用户输入以及更平滑地指导用户。
草图用户界面也存在“自我暴露”(“self-disclosure”)问题[139]。传统WIMP界面是可发现的(discoverable)，也就是说，用户可以通过菜单标题、图标、按钮和对话框等了解到该系统可以做什么以及如何去做。而SBIM系统通常只提供用户一个空白的窗口(一张虚拟纸)，没有按钮和菜单等组件。尽管界面对于那些已经得到操作指南的用户而言更方便使用和更有效，但是该界面不暴露任何关于如何使用的线索。对这一问题的解决方法也是SBIM领域的一个挑战。
8.2 形状线索(shape cue)
多数SBIM系统使用轮廓线作为构建曲线以进行建模和变形。轮廓线具有丰富的感知意义，但在实际中并不总是足够的。传统艺术采用了其它一些形状线索，如：影线(hatching)、草绘(scribble line)、点画(stippling)、底纹(shading)及启发性轮廓(suggestive contour)构成3D形体(图26)。在草图解释中包含这些线索非常困难，但是这些线索可能极大提升建模、增加和变形技术。目前有一些工作研究从其它形状线索中抽取形状信息，包括从图像底纹中抽取[141][142]及使用其它一些重要的曲线[40][56][89]，该问题仍然是SBIM领域的一个开放和挑战性问题，仍需要进一步的研究。
这一研究方向在某些方面与非真实感绘制(non-photorealistic rendering，NPR)的研究可看作同步进行。NPR提出了“如何艺术化和实用化绘制3D模型，并准确和清楚地展现其形状”这一问题。NPR方法认为轮廓线是形状感知的重要因素，但是也考察了其它多种艺术形状线索，如hatching和suggestive contour。SBIM(可以看成“反NPR”)也许可以借鉴这些成果，从艺术线索中抽取形状信息。目前Wu[143]、Gingold和Zorin[144]在这一方向进行研究。
8.3 视觉记忆和视觉规则
人类感知在进行3D重建时同时依赖视觉记忆和视觉规则。然而，多数SBIM系统仅仅基于这二者之一，离实现人类感知多功能性还相距甚远。唤起型系统的主要局限性在于其“记忆”的大小以及草图和3D形状之间的相似度度量机制。设计一个成功的通用目的形状检索系统也是一个重要的挑战，一个证据是人脸识别(可能是目前研究最多的对象侦测应用)近年来一直得到稳定地研究和发展[145]。
另一方面，模糊性问题是构建型系统的一个重要挑战。缺少了视觉记忆，系统很难甚至不可能解决深度和闭塞(occlusion)模糊性(图27)。因此，构建型系统只能构建粗略的原型或者类似于卡通的模型，唤起型系统可以从有限模板集中构建更精确的模型。Karpenko和Hughes[55]指出，系统既可以膨胀用户输入的草图也可以根据模板库进行匹配，则系统的功能会很强大。Yang等[26]介绍了一个以此为目标的系统，但是其模板定义很难扩展。
8.4 模型质量
提高模型质量也是SBIM的一个重要挑战。参数化曲面如转动混合曲面(rotational blend)[40]可以从草图得到高质量的结果，也可以很方便地传递给专业建模工具。此外，它们可以提供有效的多分辨率表示以及简单的纹理映射。然而，拓扑的限制性需要格外仔细地对齐多个分片以创建复杂的模型。
多边形网格并没有拓扑局限性问题，一些工作(如FiberMesh[56])也表明使用基于笔画的操作可以确定复杂的形状。然而，近期的一些网格生成方法在生成高质量网格时速度较慢，其原因在于(有时是非线性的)能量最小化阶段(energy minimization stage)。同时，基于笔画的操作可能从全局上扭曲整个网格。如何找出高质量又高效的曲面表示，同时也支持局部的基于笔画的操作是一个挑战。
此外，SBIM建立的模型往往呈现出满是滴状斑点的(blobby)外观。如何添加高质量的细节和棱边约束(sharp feature)是另一个需要研究的问题。近期的一些工作[56][76][87]支持棱边的创建和移动(dart)。将来，支持更复杂的特征和模型概念(如多分辨率编辑)可以赋予基于草图的系统更高的可用性(图28)。
8.5 精确性
与基于控制点范例(control point paradigm)系统可以精确地选择和修改曲面相比，缺乏精确性是SBIM经常被提到的一个弱点。在SBIM系统中指定或推导几何约束(如平行、垂直、维度相等以及水平和竖直对齐)，可以提高精确性，至少在工程设计系统中如此(如GIDeS[45][115])。相应的，用户界面也会变得更加复杂，但是精确性的提高经常由牺牲简便性得到，尤其是在自由设计系统中。
基于控制点的操纵是否是精确界面操作的理想机制是一个值得商榷的问题。例如，假定我们需要在曲面上点P处放置一个曲面，沿着法线方向d个单位。哪一个控制点需要被替换并不是显而易见的，即使已经有一些好的候选点存在。理想的SBIM系统可以考虑到控制点盒外部(think outside of the control-point box)，可能会发现一个更符合人类经验和习惯的策略。
9、结论
基于草图的系统通常被认为适合于“快餐部式”(“quick-and-dirty”)[26]的建模任务，本文介绍了多种不同的技术和应用，展示了SBIM适用于多种建模任务的潜力。
我们也许应该包容(embrace)草图输入的模糊特性。艺术是一个不断迭代的过程，包括从粗略的轮廓到具有高度细节的产品。一个动画设计师开始时会使用椭圆等基本图元来绘制人物的外形，然后逐渐添加多个复杂层次。其中的关键在于该媒介是可预测的：画者可以准确地知道当铅笔在一张纸上划过或者一个刷子在画布上粉刷时会发生什么。传统的建模应用也支持迭代式的设计，如使用细分建模(subdivision)等工具。
这些都鼓舞SBIM研究领域创造更稳定和可预测的界面，其支持迭代式方法，而不仅仅是纯粹的重建。Nealen等[89]指出，尽管“我们从周围接触的图形得到(derive)智力模型的能力已经得到很好的发展，但是我们却难以跟机器进行这方面的交流。这也是为什么我们需要循环建模并不断地修正对我们意图的不恰当的解释的原因”。
一个具有充实的图形记忆、鲁棒的创建规则以及一定学习新图形的能力的混合系统最有可能接近于人对草图的理解。目前建模、视觉、人机界面以及感知等多个领域都致力于实现这样一个系统，这些也保证了基于草图的建模在最近几年仍然是一个令人激动和具有挑战性的主题。
每一年该领域都会有一些新的令人兴奋的进步。除了在计算机图形学、人机界面等领域的杂志会议中的发表大量论文，目前也有一些专门面向SBIM的杂志和会议，其中包括Eurographics关于SBIM的Workshop、AAAI关于草图理解的研讨会，20007年SIGGRAPH会议也提供了关于草图人机界面的课程。
参考文献
[1]. Autodesk Inc., Maya www.autodesk.com/maya .
[2]. Dassault Systèmes, Solidworks www.solidworks.com .
[3]. Dassault Systemes, Catia www.catia.com .
[4]. Archipelis, Archipelis designer www.archipelis.com .
[5]. E-Frontier, Sunny3d www.e-frontier.co.jp/sunny3d .
[6]. Pixologic, Inc., Zbrush www.pixologic.com .
[7]. Autodesk Inc., Mudbox www.mudbox3d.com .
[10]. D.D. Hoffman, Visual intelligence: how we create what we see, W.W. Norton & Company (2000).
[18]. LeapFrog Enterprises, Fly fusion pentop computer http://www.flyworld.com/whatis/index.html .
[34]. H. Koenig, Modern computational methods, Taylor & Francis, London (1998).
[84]. Shusaku, Super5 www.shusaku.co.jp/www/product_S5M.html .
[103]. Rubine D. Specifying gestures by example. In: Proceedings of SIGGRAPH ’91, 1991.
[139]. Joseph J, LaViola J. Sketching and gestures 101. In: ACM SIGGRAPH 2007 courses. ACM, 2007.
[140]. D. DeCarlo, A. Finkelstein, S. Rusinkiewicz and A. Santella, Suggestive contours for conveying shape, ACM Transactions on Graphics 22 (3) (2003), pp. 848–855 [Proceedings of SIGGRAPH’03]. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (61)
[146]. P.N. Belhumeur, D.J. Kriegman and A.L. Yuille, The bas-relief ambiguity, International Journal of Computer Vision 35 (1) (1999), pp. 33–44. Full Text via CrossRef | View Record in Scopus | Cited By in Scopus (79)
https://blog.sciencenet.cn/blog-39479-215042.html
上一篇：关于“学术造假根源”的肤浅看法
下一篇：基于内容的三维形状检索
