草图建模综述.doc

《草图建模综述.doc》由会员分享，可在线阅读，更多相关《草图建模综述.doc（29页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除基于草图的建模综述摘要:传统建模工具的用户界面都基于WIMP的。尽管这些界面功能强大，但对于新手而言，这些界面的使用非常麻烦，令人畏惧。使用这些工具创建一个复杂模型需要相当多的专业技能和精力。近来，一个趋势是引入更方便和自然的用户界面，基于草图的用户界面(Sketch Based Interface and Modeling, SBIM)就是其中之一，其目标在于允许用户在建模过程中使用自由手绘草图，包括从粗略模型直到完整细节的构建过程。由于模糊性的存在，将一幅2D草图映射到3D模型是一个非常困难的任务。本文根据SBIM解释草图的策略选择进行分类，

2、包括三种基本方法：创建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-ba

3、sed modeling1、引言从严格意义上讲，“所有人都会画”并不是一个正确的论断，但是其揭示了一种普遍存在的视觉通信能力。这也是为什么古人通过象形文字讲故事，而每个会议室的墙上都挂着一个白板的原因。绘制草图是一种直接而快速的思想交流方式：只要看到少量的笔画，人们的脑海中便可勾勒出复杂的图形。在计算机建模领域，在纸上绘制草图在设计初期(即早期原型设计阶段)经常发生，此后这些描述性设计草图由熟练的3D绘制人员转换为3D模型(如图1所示)。因此，模型创建是产品流水线的一个主要瓶颈，这一过程需要大量人手以创建复杂多变的形状以及错综复杂的内部关系。当前一些高端建模系统(如Maya1、SolidWor

4、ks2和CATIA3)都提供功能强大的精确几何模型构建和操纵工具。这些系统通常采用WIMP界面范例，即：用户需要从菜单和浮动窗口中选择操作类型，在对话框中输入参数以及移动控制点等。近来在建模工具界面的一个趋势是引入自动(或辅助)直接从草图到3D模型的转换技术，即面向模型创建的草图交互界面(sketch-based interface for modeling，SBIM)。这类界面的主要研究问题是：计算机如何在三维空间中理解和解释用户绘制的草图？多年来研究人员一直在考察这个问题。人类视觉系统可以从简单的图像或草图，甚至是从简单的线画图形(并没有阴影线索)中理解复杂的形状，但是人的感知过程是如此的

5、简单，却使得人们很难对这一过程进行理解和形式化。开发一个能够直观地模拟人类观察能力的SBIM系统需要考虑感知和认知问题。事实上，SBIM处于多个不同领域的交叉点，包括计算机视觉、人机用户界面以及人工智能。尽管这一研究主要是由计算机建模领域发起，但是更强大商用计算机硬件的出现以及各方面研究成果推动了该领域取得了令人兴奋的成果。SBIM研究的最终目标是在原有基于WIMP系统的基础上整合草图交互方式，构筑更实用的建模系统。使用这类系统时用户以渐进的方式构造和修改模型，从初期的概念到详细精确的最终模型。尽管目前对于SBIM有诸多的研究，但是工业界并未完全支持SBIM，因为SBIM不能满足建模任务的所有

6、功能要求。商用建模工具包中支持手绘草图的有Archipelis Designer4和Sunny3D5，其它一些程序，如ZBrush6和MudBox7等，也支持建模人员使用刷子以笔画形式在模型表面绘制细节。草图交互界面可追溯到Sutherland的SketchPad系统8，该系统使用光笔作为输入设备在屏幕上直接创建和操纵对象，这种交互方式先于目前流行的鼠标交互方式多年。SketchPad系统预见了许多SBIM会面临的挑战，包括：如何接受和处理用户输入、解释用户输入(作为一个对象或者操作)及表示结果对象。现在的系统主要在SketchPad基础上提升其处理的自动性：SketchPad用户必须显式指定

7、所有的几何信息，而现在的系统可使用更优化的算法减轻用户负担及提高计算能力，进而可以自动的从2D输入推导3D形状。基于草图的技术可被用于多种建模任务，其中的一些将在第7章进行讨论。本文(9中的修改和扩展)对基于草图的用户界面在3D几何建模中的应用进行综述。SBIM的主要挑战在于草图解释，对此，我们分为三种主要方法：创建3D模型、(在现有模型上)添加细节及模型变形和操纵。图2总结了SBIM应用的主要流程。第一步是从用户输入获取草图(第三章)；接着是草图过滤，对草图进行预处理和一些变换(第四章)；最后是草图解释，以得到3D模型的具体描述(或者解释为对模型的操作)。本文的组织如下：第二章简要讨论了感知

8、在SBIM中的作用，第三到五章详细描述了SBIM流程的每一个阶段，本文包括了对两个重要问题的讨论：表面表示(5.4)和界面设计(第六章)。第八章总结了本领域面临的挑战和一些开放性问题。2、感知的作用人类视觉系统非常复杂，我们考察该系统是因为它在我们生活中一直非常容易地运行。对认识科学的深入讨论已经超出本文和我们的知识范围，该领域的一些观点对SBIM系统的设计已经产生了一些影响(隐式或显式)，毫无疑问在今后也会产生影响。毕竟人们对形状的感知影响他们如何进行绘制：感知和交流是我们视觉智能的两个侧面。我们视觉系统必须考虑的基本问题是“眼睛所看到的图像可以有无数种可能的解释”10。考虑一个最简单的仅包

9、含一个点的草图，尽管我们已经知道这个点准确的2D坐标，然而这个草图可以解释为任何一个经过该点和观察者眼睛的直线上的点的子集。图3示出了非平凡(non-trivial)线画图形问题，其中展示了三种与立方体具有类似投影的物体，这类物体可以有无数种。尽管我们大脑的逻辑部分可以相信绘制的内容不一定是立方体，但是我们的视觉部分并不一定这么认为。我们尽可能多地尝试，这个物体却总是被看成是立方体。这一实例可以说明我们视觉系统的一些简单的支配规则。我们如何把图3解释为立方体，而不是其它无数种候选呢？我们可以观察图3中三个混淆模型，这三个模型的轮廓线都可投影为类似于立方体的投影，但只有立方体本身符合我们的视觉规

10、则。Hoffman10将其它的候选称为“无意视图”(accidental views)，因为视点的微小变化都会揭示这些模型不是立方体。换句话说，“无意视图”并不稳定(unstable)，而物体的大部分视图在微小变化下仍然是稳定的。我们的视觉系统更偏向于稳定的解释。现在我们考虑艺术家正准备绘制上述的一种非立方体物体。他们会不会选择从“无意视图”绘制这个物体呢？并不一定，因为他们自身的视觉规则会发觉这是一个立方体。因此，尽管可以有无数种方式来重构一个绘图，“自身的视觉系统是有偏的。它只构建那些符合规则的3D世界”10。视觉规则可以帮助我们解释从未见过的图像，但是它们也会限制我们，使我们只看到最简单

11、的物体。我们的记忆中有非常多的形状用于解释各种图像12，并应用于从未见过的复杂事物。例如，当看到运动汽车的一幅图像或者仅仅只是轮廓，我们可以很快的判断出其属于汽车类别，并推导出其近似的几何、对称以及大小信息。这点突出了识别(recognition)和重建(reconstruction)的一个重要区别13：重建是指根据物体的2D表示创建该物体完整的3D几何信息；识别是一个类似但又截然不同的任务，即基于形状记忆根据物体的一幅图像判断其所属的类别。换句话说，如果视觉记忆可以识别出一个形状，我们可以更简单的重建该形体。否则，对物体的重建将依赖于视觉规则系统。对称是许多物体的另外一个重要属性。从2D表示

12、中发现或推导对称性可为3D重建提供非常有价值的信息。这里不仅包括“真”对称，也包括对称3D物体的任意投影。Tanaka等14讨论了三种对称：真实对称(real symmetry)：对称轴是图像平面内的一条直线；斜对称(skewed symmetry)：对称轴是穿过图像平面的一条直线；一般对称(generalized symmetry)：对称轴是3D空间中一条自由线。图4展示了这些概念。感知的一些概念可以帮助我们理解SBIM面临的挑战以及设计中所要做出的决策。在第五章中我们将看到SBIM系统基于视觉记忆和规则处理简单图像中模糊性。在第8章中我们也会看到，理解我们的感知也会提高SBIM系统所需要的

13、基于软件的感知。3、草图获取SBIM系统的最基本操作显然是从用户获取草图。基于草图的输入设备的一个关键特性是支持自由手绘输入。标准的鼠标符合该定义，但是更类似于在纸上自由绘制的设备(如平板显示器)可以更好地帮助用户进行绘制。此外，显示和输入耦合在一起的设备更适合于自然的交互(如图5)。实际的纸笔是一种非常有表现力的交流媒介。用户不仅可以使用整体的构成也可以通过压力和笔画的风格来表达信息。从用户角度看，这种媒介通过纸的质地纹理提供用户反馈，用户可以感受到笔在纸表面的刮擦(例如：在餐巾纸上绘制会有一种与普通纸所不同的触感)。有一些研究致力于将上述各方面转移到数字领域。目前许多平板设备具有压力敏感性

14、，其不仅仅可以提供笔端的位置信息，也可以提供用户在平板上的压力大小信息。一些设备还提供笔的方向性数据。触觉(Haptic)设备15是一种更新的研发成果，其可以通过笔设备本身提供用户直接的反馈，如：低频振动以模拟笔和纸之间的摩擦。另外一些可用的输入设备包括平板显示器16，甚至虚拟现实设备17。这些设备都致力于提升用户的沉浸感，但它们往往又比较笨重并可能降低沉浸感。例如，触感输入笔被附着到胳膊上以提供力反馈，但这种方式又降低了设备与笔的类似程度。随着这些硬件越来越紧凑、便宜以及具有真正的沉浸感，越来越多的人会使用它们。可以认为最终最逼真的界面应该是真正的纸笔与一些主动数字化能力的结合。现有一些商业

15、产品提供对文字和图形的自动数字化18，但到目前为止支持3D重建的几乎没有。离线扫描草图也可作为一种输入，但是这种方法更类似于计算机视觉中图像识别问题。这种方法在某些特定领域应用可能会有效，如：建筑工程图纸扫描。但对于一般建模任务而言，这一方法非常复杂，目前也缺乏鲁棒的解决方案。交互式系统通常更可行，它可以提供用户更多的信息(绘制顺序、速度等)以及不断的反馈。在本文中我们仅考虑交互式系统。3.1草图表示一个基于笔的输入设备至少需要提供2D坐标系统中的位置信息，通常采用窗口坐标。不同设备的采样速率会有所不同，但无论如何，采样位置都表示连续运动的分段线性近似(图6b)。采样点在间隔上是不规则的，由绘

16、制速度决定。用户在接近拐角处会更加小心，相应的采样点会更加密集，这一事实可用于确定草图的“关键”部分1920。我们把笔画看作是一个时序的点序列，其中：包含了2D坐标和时间戳，笔画的开始和结束由笔落下和笔抬起操作界定。一幅草图包含一条或多条笔画。笔画信息也可以包含压力或笔方向信息，这些取决于目标应用和硬件设备。由于图像处理领域已有大量研究，一些SBIM应用选择基于图像的笔画表示，如图6c所示，笔画被近似表示为一个像素网格。随着输入设备在虚拟纸上移动，它在纸上留下了“墨水尾巴”。基于图像表示的优势有：固定的存储大小以及自动多笔画混合。但是其中草图的时间特性等一些可用的辅助信息被丢失了。在SBIM系

17、统中，“画布(drawing canvas)”这一概念2122被用于将一幅草图嵌入到3D世界坐标系中。最简单的画布定义是指定一个特别的平面，如：x-y或用户指定的平面，并将草图投射到该平面上(例如：将深度或z坐标的值设为0)。活动视平面(active view plane)也可以像画布一样很好的运行，允许用户变换视点从多个角度进行绘制(深度仍然不受约束)。假定输入的笔画是平面对称的并反转视投影，每一个对称的3D曲线是可重获的(recoverable)23。最后的变换是基于当前视点将草图投射到一个已有的3D模型(图7)。一些SBIM系统被设计为面向非经常用户或入门用户，而不是专业用户。为了帮助入

18、门用户进行草图绘制，画布可被替换为图像，用户在图像上进行绘制24252627。图像可被用于辅助绘制草图，其中输入的笔画被附着到图像的边缘25。4、草图过滤在试图解释一幅草图之前，有必要进行一些过滤。原因之一是输入中不可避免的包含一些噪音或者错误的采样点。Sezgin和Davis28给出了两类误差来源：用户和设备错误。绘制技术不熟练，或轻微抖动都会使用户画出不直的线段和不平滑的曲线。第二种错误源是“数字化噪声”，其发生于机械硬件设备对输入进行空间和时间量化的过程：“一个传统的数字化平板分辨率可能低到4-5dpi，而扫描图像的分辨率达到1200-2400dpi。由于用户有时绘制速度很快以致即使设备

19、采样率较高(如100Hz)也只能采集到少量的点(每英寸)”28。即使用户更加仔细绘制，设备错误和采样问题也仍然存在。因此，基于草图系统的输入通常并不是用户意图的完美描述，在进行解释前必须进行“清理(cleaned up)”或者过滤。这一过程可以减少噪声以得到在后续工作中更便于使用的表示形式。下面我们将介绍一些在SBIM领域中常用的过滤方法。4.1重采样和平滑由于输入设备和绘图速度的不同，原始输入笔画采样点之间的距离也不同。重采样(resample)是一种降低输入笔画数据噪音的方法。重采样过程可在绘制过程中同时进行，舍弃一些与前面采样点距离低于一定阈值的采样点，并对样本点之间距离多于一定阈值的情

20、况进行插值。这一过程也可以在笔画绘制结束后进行。根据具体应用的实际需要可以选择线性或者平滑插值(图8a所示)。重采样的一个极端形式是折线(或多边形)逼近，只保留少量采样点，这样可以降低笔画的复杂度(图8b)。例如：在Teddy29系统中将笔画的首点和末点相连以构成一个闭合多边形，同时对笔画进行预处理以使得各边的长度为一预先定义的固定值。另一种简单方法保留笔画的每个第n个点(n-th)。这些方法适合于平滑的输入，否则不会得到令人满意的结果(样本分布不基于局部笔画特征，如边角)。在通常情况下，鲁棒的算法会对由于拟合引入错误数设定一定的范围，在较平坦的区域保留较少的点，在细节较多的地方保留相对较多的

21、点。例如，最大最小法30使得任一点到拟合直线的最大距离保持最小。有一些严格的计算几何方法31可以解决这一问题，但是它们只使用草图输入的位置信息，而草图的时间信息可以用于找出笔画上的感知重要点，如边角。例如，Saga19使用绘制速度来找出“分割点”，并提示用户确认不确定的分割点；Sezgin等20使用曲率(最大值)和绘制速度(最小值)来确定边角点。即使在重采样之后，噪声采样点仍然可能存在。平滑算子可以用于降低噪声，其代价是可能会隐藏输入中真实的中断点。此外还有一些技术，包括对每一个采样点使用局部平均过滤器(也就是将每一个样本点替换为其相邻点的平均值)32，或者Gaussian过滤器(中心加权平均

22、)33。4.2拟合在重采样或平滑之后，草图中仍会有大量冗余的采样点。将草图拟合为其它表示具有双重作用：简化输入以及简化其与其它草图进行比较。事实上，曲线拟合在一些SBIM系统中非常必要，其中重建的表面基于构建型曲线(如旋转的曲面)。曲线拟合是一种简化方法，相比多边形拟合其错误率更低，但是需要更多的计算量。最小二乘方多项式拟合34是一种可选的解决方法，但是参数形式如Bzier3536和B样条曲线373839是更可取的。图8c举例说明了样条曲线拟合。最近，SBIM系统使用了细分(subdivision curve)和变量隐式曲线(variational implicit curve)方法。Alex

23、e等32使用Haar小波变化以得到多尺度的笔画表示；Cherlin等40对原始笔画采样点使用反Chaikin细分将笔画拟合到细分曲线，有效地降低了数据的噪声；Schmidt等16从输入的草图中推导几何约束并拟合到变量隐式曲线。有很多草图输入实例中同时包含分段线性和平滑的部分。将草图的直线部分和曲线部分进行分割，并对前者进行折线拟合以及后者进行平滑处理20364142，有益于系统的后期处理。例如，Sezgin等20使用输入草图的速度和曲率信息进行折线拟合，然后对拟合误差率较高的直线段使用立方Bzier曲线进行拟合，如图8d所示。Yu43指出由于样条曲线在高层次很难进行比较，使用一些基本图元(如：

24、矩形、椭圆和圆弧)进行拟合效果会更好；这也是Saga19采用的方法以对自由手绘CAD系统中的形状进行拟合，但是系统也需要用户判断和修正标注。基本图元拟合方法已经在一些SBIM系统4445中得到采用。上面讨论的所有技术都可以说是在局部或者笔画层次进行操作。草图规整化(Sketch Beautification，借用了Igarashi等46提出的术语)是一种在全局层次推导笔画间几何约束(如：线性、平行、垂直、对称等)的技术(图9)。举例来说，当绘制矩形时，系统可以使用直线段拟合每条边，同时推导相邻的边应具有一定的夹角。草图规整化过程可以交互式进行464748，也可以在草图绘制结束后批处理进行49。

25、4.3重绘拟合方法最适合于有一定精度需求的应用，如：工程性绘制。在强调自由绘制以及对用户意图很少做假定的应用中，拟合有可能不经意地破坏草图的一些重要信息。在这种情况下，用户应能够绘制他们确切想要的形式，在错误出现时用户自行进行修正。“重绘(Oversketching)”是一种常见的用户界面元素，用户在绘制过程中出现错误时，系统允许用户在错误区域仔细地重绘，系统找出后续笔画影响区域，粘结新的部分并平滑新旧片段以更新草图(图10a)。2D空间的重绘可在草图解释前进行205152，系统也可保留原始草图以便“三维重绘”过程使用(5.3)。当草图中有重叠笔画时，设计者会采用另一种重绘形式，即：将这些重叠

26、笔画合并为单一的对象(图10b)。一些SBIM系统允许这种多笔画的输入方式，系统自动将这些笔画混合到一起27505354。在笔画空间方法(stroke-space approach)中，笔画间的几何关系被用于混合笔画。例如：Pusch等50使用层次化空间划分方法将多个笔画分成局部可定向的片段，然后使用B样条曲线进行拟合；在基于图像的方法中，笔画“自由”地按照用户绘制的样式进行混合；文献16则提出了一种半自动化方法：用户指定哪些笔画可以被混合到一起。5、SBIM中的草图解释草图得到充分过滤后，最后一步是解释草图，将其映射到一个3D建模操作。我们使用解释(interpret)这一词，即，为草图赋予

27、意义。与从菜单选择一个命令不同，自由手绘输入具有固有的模糊性(多种解释)。用户的绘制意图是什么？输入是否是合法和一致的？草图如何映射到一个建模操作？这些是SBIM系统需要回答的问题。上述问题有多种解决方法，但我们可找出其中一些公共成分。我们基于建模操作的类型对SBIM系统进行分类。最重要的类别是从输入草图自动创建完全3D模型(5.1)；此外，一些重要任务包括使用笔画增加现有模型的细节(5.2)及变形处理(5.3)；对3D物体进行建模有多种曲面表示方法，每一种都有其优缺点(5.4)；最终，一个精心设计的界面应该在正确的时间选择正确的解释(第6章)。具有了多种解释功能后，一个完全的SBIM系统可用

28、于建模流程中各个步骤，包括从原型化到微调(fine-tuning)的全过程。由于分类的主观性，有一些系统可能不能确定的归类到其中某一类。在下文中，我们以上述类别为主线，对草图解释进行概览并讨论相关工作。5.1模型创建系统模型创建系统(model creation system)试图从2D草图输入中重建3D模型。我们将所有的创建系统分为两类：唤起型(evocative)和构造型(constructive)。二者区别在于：构造型系统某种程度上是将输入草图直接映射到输出模型；唤起型系统则利用输入草图来对与输入类似的内置模型类型(built-in model types)进行实例化。这只是SBIM可用

29、分类标准的一种，与重建和识别的区别相对应。唤起型系统首先根据一组模板识别草图，然后使用模板重建几何模型；构造型系统则试图直接重建几何模型，没有识别步骤。换句话说，唤起型系统与视觉记忆类似，而构造型系统更多的依赖于规则。唤起型系统使用模板对象来解释笔画，其表现能力由模板集的大小决定；构造型系统直接将草图映射到模型特征，其表现能力由重建算法的鲁棒性和系统接口揭示潜在模型的能力(即：模型映射函数的泛化或映射机制的拓展能力)来决定。(Because evocative systems usetemplate objectsto interpret strokes, their expressivene

30、ss is determined by therichness of the template set. Constructive systems, meanwhile, map input sketches directly tomodel features; therefore, their expressiveness is limited only bythe robustness of the reconstruction algorithmandthe ability of the systems interface to expose the full potential.)当然

31、，这二者间有一定的重叠，主要表现为：唤起型系统可以利用模板对象变形来匹配用户输入草图(deform the template objectsto match the input sketch)26，而构造型系统也使用一些领域相关知识(exploit domain-specific knowledge)来指导重建。5.1.1唤起型系统唤起型系统内置有一定的3D图形“记忆”，可以用于指导解释输入的草图。例如：一个面向人物创建的系统中，其形状记忆可能用于确定草图的哪一部分属于头部、躯干等等。由于形状和相关的比例是可预知的，3D构建变得更加简单。这类系统可分为两种：图标型(Iconic)系统和模板检索

32、型(Template Retrieval)系统。(1).图标型系统这种系统仅从一些“图标性笔画”推断最终的3D形状444860。Zeleznik等的SKETCH系统44是一个典型实例，该系统使用简单的笔画组定义基本的3D物体。例如：三条相交于一点的直线表示一个立方体，立方体的维度由这些笔画确定(如图11)。Jorge等提出的GIDeS系统45也采用了类似的设计，系统提供了一系列基本物体的模板和一系列工程设计的参数化模板(5.1.2)。Igarashi和Hughes提出的Chateau系统47也可从少量笔画推断形状，尽管这种形状不是完全自由形状。系统面向建筑结构的限制允许对输入作一些假定，如：平

33、面、对称以及正交等；系统的交互特性也使得识别过程变得更加简单，由于用户可以即时看到系统如何解释他们的操作，就可以避免许多有问题的情况发生。(2).模板检索型系统另一种唤起型系统是从模板库中检索模板对象26637478。相对于简单的基本对象，这些模板更加完整和复杂。从用户的角度来说，他们必须提供目标对象的一幅完整而有意义的草图，而不仅仅是一些唤起性笔画。这种方法比推断法更容易进行扩展，因为系统新特性的添加恰如向模板库中添加新对象那样容易。相反，由于构造单元(形状模板)更加复杂，因此，可能无法通过组合模板对象来得到特定的结果。在基本的匹配算法中，必须考虑输入和输出端增加的复杂度。基于检索的系统面对

34、2D草图与3D模板的匹配问题，评价它们在3D空间中的相似度需要对草图进行重建，这是系统需要解决的根本问题。因此，系统通常从3D模板中抽取2D形状来进行比较(也有其它一些方法，如：图匹配78)。Funhouser等63根据他们“人们通常从一个相当一贯的观察方向集绘制草图”的观察结果，采用从13个视点得到的物体投影轮廓来定义一个对象的形状描述子，系统通过对每个轮廓进行图像变换(image-based transformations)而抽取出一个定长而具旋转不变性的特征来创建对象模板，然后，输入草图通过采用相同的图像变换并与存储的模板进行比较来与某个对象进行匹配。此外，为提高识别率，用户可以至多从3

35、个不同的视角绘制同一个物体。计算机视觉领域对2D形状匹配问题进行了大量研究，多数方法通过基于图像的方法对侧面(silhouette)和轮廓(contour)进行比较(Veltkamp79很好地介绍了这方面内容)。SBIM中基于图像的技术舍弃了草图中潜在比较重要的时间和其它一些辅助信息(压力等)，但其也受益于现有形状匹配的大量成果。Funhouser等63也赞成使用基于图像的匹配，因为这种方法使用户可以提供“片段化草图标记(fragmented sketch marks)”(相对于基于笔画系统中需要长而连续的笔画)。按照近来批处理重绘的一些工作，将片段化草图混合成单一轮廓(blend fragm

36、ented sketches into a single contour)已经不再是问题了。Shin和Igarashi提出的Magic Canvas系统74采用模板检索方法进行场景构建(如图12)。他们也从每个模板中抽取一些轮廓(16个)，但是，他们使用基于傅立叶的方法进行草图匹配。使用多个物体构建场景不仅需要模板检索，也需要修正场景中每个物体的位置。据此，Magic Canvas系统旋转和缩放物体以匹配输入草图的方向，同时推断简单的几何关系(如：灯放置在桌子上)。系统也需要用户的干预以初始化对场景中子草图的检索过程并要从多个候选集中选择合适的物体。Yang等26提出了类似的基于模板系统，他们

37、使用过程化描述模型(procedurally described model)，而不是基于网格的模板。以一个马克杯为例，他们用模板来描述如何从简单的基本元素组成一个马克杯，而不是使用马克杯网格作为模板。这种方法的优点在于模板可通过形变来匹配输入草图，而不只是仅用模板的一个实例。然而，过程化模板定义(procedural template definition)使得新模板的添加比基于网格方法要困难得多。Lee和Funkhouser77近期提出的方法偏离了模板模型的概念，而更接近于模板部件(part)。以飞机为例，系统包含了机翼、引擎等多个模板，而不只是一个完整的飞机模板。使用草图用户界面，用户可

38、以通过在模型上近似位置绘制某一部件的轮廓而将部件添加到已有模型上，系统找到匹配的部件，并在用户选择合适的匹配后将部件组合到已有模型中，且自动地相对于其它元素放置。5.1.2构造型系统纯粹的重建与“识别再重建”相比要困难得多，因为后者使用了预先定义的知识以定义草图的3D几何信息，一定程度上避开了模糊性问题(模糊性问题在识别阶段仍然存在)。构造笔画系统必须仅仅根据规则从草图重建3D物体，因为重建是一个非常复杂的多学科问题，现有许多研究都在尝试提出解决方法。我们介绍构造型系统的三种主要类型：机械性物体、光滑物体以及从多视角绘制的物体。(1).工程设计系统我们的视觉系统可重建机械的(硬边界)和光滑的物

39、体，或介于二者之间的物体。然而，基于草图建模应用通常着重于其中的某一方面，因为设计层次上选择光滑或非光滑的解释将减少草图可能的解释。设计和描述工程性物体(即，大部分是平坦的)是计算机建模在工业中的一个重要应用。因此，在SBIM研究早期就引起了研究者的注意80。Lipson和Shpitalni58提出的基于最优化方法封装了许多技术，每一个输入笔画都假定表示3D线架模型中一条边，而同时产生的每个端点是模型的顶点，同时，假定草图表示该物体在平行投射下的投影。这些约束给用户了少许限制，但可以极大降低系统的复杂度。在检测2D草图中一些重要的关系(平坦、拐角、等距、正交等)后，通过对每个顶点深度未知的一个

40、线性方程进行优化来完成重建过程。从线画图形重建3D几何形状在计算机视觉领域已经有所研究。线标注(Line labeling)81是一种对图像中线段进行分类的算法，线段类别有凹的、凸的或轮廓线，定义了几何约束以供3D重建。显然，我们可以直接使用该方法处理草图输入。线画图形重建的一个困难是如何确定点、角和边的位置。在交互式系统中，这些可以在用户绘制笔画的过程中确定，然后重建过程可以采用“批处理”的方式进行11174968。对称性是工程性物体的一个公共属性。尽管难以进行检测，但是在重建构成中可以使用一些关于对称的知识以减小搜索空间6264。线标注方法的一个不足在于对曲线段的支持有限。Varley等6

41、7使用两阶段方法：在第一阶段中，用户只使用直线绘制一个总体模型结构；第二阶段中使用曲线段对模型进行重绘，从第一阶段重新构建的模型作为重建的模板。Masry和Lipson11也使用了两阶段方法，但是他们的方法对用户隐藏了细节，系统通过分割自动抽取线画表示。除批处理方式外，系统也可采用交互式方式，在用户绘制草图过程中重建3D模型(如图13)。该方式下，用户可立即看到运行结果，即时修正成为可能。系统也可采用更简单的重建规则。最通用的方法是挤压(extrusion)方法，将一个剖面曲线(profile curve)沿着某一向量(或曲线)“推过”空间1636536075，如图14所示。该技术非常适合于创

42、建具有硬边界的模型，如：立方体(由一个正方形挤压)或圆柱体(由圆挤压得到)。挤压方法与唤起型系统有点交叉，因为用户只需要绘制剖面曲线以及挤压向量。然而其重建过程并不基于或限于识别：用户可自由创建相应领域中近乎无限多的物体，而不受限于模板集。(2).自由设计系统尽管一些工程设计系统支持曲线笔画，但是其重建仍然基于直线型表示。平滑、自然的物体的重建需要不同的方法。有观察表明：人类视觉系统偏向于将平滑的线画图形解释为3D轮廓10。因此，多数构造型SBIM系统选择将笔画解释为轮廓线1629323640555666。（轮廓可定义为表面法向量与视方向垂直的物体上所有点的投影，将物体的可视部分从不可视部分分

43、开(图17所示)。轮廓不仅仅包括侧面轮廓(silhouette outline)，也揭示了一些内部特征，如：脸的下巴和鼻子部分。）由于有多个物体对应于同一个给定轮廓，需要给出进一步的假定以重建草图。构造型系统的一个关键思想是根据一些内部规则选择简单图形，然后让用户完善该模型。基于骨架的方法在“从轮廓草图创建3D模型”研究中非常流行1629323640516672。骨架(skeleton)可定义为“与最近轮廓点等距的线(the line from which the closest contour points are equidistant)”，如图15所示，它提供了一个距离场(distanc

44、e field)，可帮助确定地在3D空间中决定一个曲面(determine a surface in 3D unambiguously)，(以使得曲面到骨架的距离与轮廓线点到骨架的距离相关(such thatthe distance from surface to skeleton is related to the distance of contour points to the skeleton)。找出准确骨架所花费的代价比较昂贵，但可以近似地从Delaunay三角化形式82中抽取骨架：连接相邻非边界三角形的中心(如图15b)，这也称为弦轴(chordal axis)变换。，Levet和

45、Granier83最来提出了一种从少量伪分枝(spurious branch)生长出整个骨架的骨架抽取方法。如何才能使用骨架生成3D模型？根据骨架结构的复杂度可以有多种方法。最简单的非平凡(non-trivial)骨架是一条直线；在一个对称的草图中，骨架是一条与对称轴对齐的直线；为生成曲面，草图可以绕骨架旋转而创建一个旋转曲面1636。一条简单的笔画也可以指定轮廓，通过固定或用户手绘的旋转轴定义出曲面。Cherlin等40扩展了这一思想用来生成一般旋转曲面，其中骨架是由两条笔画的中间轴确定(作者把这种构建称为转动混合曲面(rotational blending surfaces)，如图16a所

46、示。他们的系统还允许用户提供定义自由横截面的第三条曲线，提升了这种构造的表现力。这些构造假定输入的曲线在同一个(绘制)平面中，且生成相对该平面对称的物体。另一个更具挑战性的方法是将输入的草图看作对称3D曲线的投影，即：绘制的草图表现了歪斜的或者一般对称。Tanaka等14在早期提出的方法中假定两个输入笔画在3D空间中是对称的，并通过一些额外的用户输入确定对称轴以鉴别每个笔画的对称顶点，然后，将曲面重建为连接笔画的一般圆柱体(a general cylinder)。Kanai等5784提出了一个更鲁棒的对称检测草图系统，该系统可以从多视图检测和协调(reconciling)对称性，并使用B样条曲

47、面片重建曲面。这些参数化构造方法的一个缺陷是有限的拓扑性，最终的结果(物体)总是可在2D平面上进行参数化，其骨架也不包含分枝。当骨架包含分枝时，就需要更鲁棒的方法。对于简单(如不相交)闭合轮廓而言，膨胀法(inflation)是生成似是而非(plausible)3D模型的一种确切方法(an unambiguous way)。例如：Teddy系统29对轮廓进行膨胀，图16b展示了一个典型结果。一个轮廓的骨架表示(skeletal representation)也自然地集成了一种隐式曲面表示(implicit surface representation)。在Alexe等32提出的方法中，球形隐含

48、图元(spherical implicit primitive)被放置在骨架的每个顶点，当这些图元被混合到一起时，结果产生一个平滑的曲面，其轮廓可映射到输入的草图。其它一些系统165161采用草图轮廓来定义隐式函数的约束，以取代变量隐式曲面85。对于诸如包含自相交的非简单轮廓而言，简单的膨胀方法并不适用。轮廓将物体分成面向观察者和与观察者相对的两个部分，在非平凡物体中，也可能会出现曲面的部分面向观察者，但对于观察者而言并不可见，因为该部分被曲面的其它更靠近观察者的某一部分遮蔽了。图17演示了这样一个实例：脖子的轮廓被下巴挡住了，注意到脖子的轮廓在下巴后方穿过，可以看到在投影轮廓中有一个T型形状(称为T连接)，下巴的轮廓突然中止(称为尖端，cusp)，T连接和尖端意味着隐藏轮廓的存在。Williams86根据这些提出了一种推断图像中隐藏轮廓线存在性的方法。Cordi