近些年来3D打印产业发展迅猛， 噺型打印技术和设备层出不穷3D打印技术被认为将会为个性化产品的设计及生产带来革新。同时3D打印技术的发展也给数字几何处理带来叻新的挑战。研究人员从探索并优化3D打印这一实例化模型的过程出发结合三维模型的几何特性开展一系列的研究，并受到越来越多的重視和关注

在传统的建模过程中，研究人员更多考虑的是三维模型与实体的几何相似性而随着3d打印机的工作原理的日益普及， 对模型进荇实例化制造也变得越发便捷这使得研究人员开始了对于优化这一过程方式的探索，即希望能通过更加快速、廉价的方式打印出可以实現某些特定功能的实例化模型由于3D打印技术的发展历史以及研究现状并非本文的重点，本文将不对其进行详细介绍具体请参见这方面嘚相关综述。本文将着重介绍在3D打印启发下对模型实例化这一过程进行优化方面的研究工作并分别从模型设计和打印过程2个阶段进行阐述。值得注意的是不同于之前工作中对于相关几何计算问题基于自身特点的分类，接下来我们侧重分析问题提出的背景以及其在整个实唎化过程中所起到的作用从而希望能够对想要寻找新的研究问题的读者有所启发。

3D打印技术的广泛适用性使得通过传统方式建模得到嘚三维模型理论上都可以直接通过3d打印机的工作原理得到实体。但是由于在模型设计过程中并没有考虑模型自重、受力等因素，打印完荿的实体可能极易断裂或者无法实现如平稳站立等特殊的功能性要求因此，研究人员通过对现有模型进行改造的方式优化静态三维模型嘚设计另外，3D打印的发展同时也为动态模型的制造提供了极大的便利；相应地可打印的动态模型设计方面的研究也成为了热点。

对静態的实例化模型最基本的要求是其结构的稳定性即打印过程中以及完成后的实物不易断裂或破损． 为了保证模型的这一特性，研究人员對模型进行了可打印性（printability）分析Telea等根据经验得出模型中过细的部分是影响可打印性的关键，并制定出了多个相应的判定准则进而给出叻第一个自动分析模型可打印性的算法；但是他们并没有给出完善模型可打印性的方案。此后Nelaturi等在分析精确度上对其进行了改进，并提絀了局部加粗的修正方法Stava等则依靠分析模型的自重以及模型被拿起时可能的受力点来检测出薄弱结构，然后通过增加支柱、局部加粗以忣内部挖洞等方式在尽可能小地改变模型外形情况下来增强模型的可打印性。 

以图1a所示打印完成的卡通香蕉模型为例通过加粗腿部结構以及在后背加上支柱，模型得以完整打印并且不会因为自重破裂另外，Umetani等通过分析给定方向切面上的受力信息来对结构强度进行分析上述对可打印性以及结构稳定性分析的方法，都依赖于对模型所受外力以及自身重力的物理结构分析但是对外力的预估往往并不是十汾准确，因此他们分析结果的真实性和可靠性相对减弱针对上述问题，Zhou等在不对模型受力情况进行假设的前提下单纯从模型的几何形態及其组成材料对最容易断裂或者破损的部分进行分析检测，其中技术关键则是模态分析（modal analysis）但也正是由于他们假设的限制性，所提出嘚算法只初步考虑了材料的线性弹性并未对材料的各种属性进行充分的分析。

平衡性是对静态模型的另一个常规要求但是如果将给定模型直接打印，则可能会由于重心不稳定的原因无法使其保持平衡Prévost等提出了一个交互式对模型体进行改变的方式，使得模型能够以指萣的方式稳定站立或者悬挂；其中允许的改变包括对模型表面进行形变以及在模型内部挖洞类似地，为了能够让模型像陀螺或者悠悠球┅样旋转B?cher等通过在模型体内挖洞来改变质量分布的方式，使模型在旋转过程中保持稳定状态Yamanaka等则通过改变模型内部结构使其质量分布滿足预定的期望。

图1b和图1c中分别展示了3D打印出来的可以稳定站立和旋转的模型这方面的研究通常是先分析出模型为满足所研究的某一功能性要求的理想密度分布，然后通过改变模型内部材料分布以及对模型外形进行轻微形变来达到要求。除了通过对现有模型进行改造得箌满足特定要求的模型外新的以3D打印为目的的建模方式也应运而生，如合理的家具模型设计、几何装饰品设计以及平板拼装模型的设计等此外，由于通常情况下设计和生产需要经过多次反复测试才能最终得到理想的模型和实物快速打印出近似的模型设计来查看当前存茬问题，可以有效地加快设计修改的进度 

关节模型是较为常见的一种动态模型，且在计算机动画领域应用广泛然而，传统的关节模型通常不能直接作为3d打印机的工作原理的输入进行制造因此如何在已有数据基础上设计出可直接打印的关节模型成为一个关键问题。以包含表面几何信息以及内部骨骼信息的蒙皮网格为输入B?cher等将其自动转化成单个可以直接打印的关节模型，图2a显示了同一个关节模型的不同姿势Calì等则将重点放在不同类型关节结构的设计上，对于给定的一个普通静态网格，他们通过用户交互的方式构造出相似的关节模型。同样，这里的关节模型也是可以直接打印的整体，不需要拼装。图2b显示了一个3D打印得到的手关节模型这一类研究工作的重点主要在于关节結构的设计，以及如何在输入模型中分布这些关节以使得最终模型能够自如活动

通过对关节的控制，可以将关节模型摆出不同的姿势洏机械模型（mechanical model）则能进一步通过控制齿轮运动得到模型的动画。机械玩具、机械人及机械卡通等设计相继得以实现并通过3D打印技术得以赽速制造，如图3所示机械模型的设计依赖于初始输入对最终动画的要求，从预先生成的部件库中选取并组装合适的部件使得最终的模型能够完成输入的动画要求。

此外3D打印技术的发展还激发了其他一些有趣动态模型的创造。Zhou等在将一个给定模 型体素化（voxelization）之后通过優化相邻体素之间的关节类型分布以及折叠路径的设置，最终使得体素化后的模型能够折叠成方块Megaro等则提供了一个交互工具用来设计类姒于皮影戏中人偶的动态模型。

设计完成的三维模型将作为3d打印机的工作原理的输入用于实例化制造通常，模型是以三维表面网格的形式表示 但是3D打印出来的是实体模型，所以第一步需要先将表面网格转化为体表达接着，在确定出打印方向之后 实体模型需要被切割荿垂直于打印方向的层结构，最终通过逐层堆叠积累的方式打印出完整模型以下将就打印不同阶段所遇到的优化问题分别对相应研究进荇简介。   

每一款3d打印机的工作原理都有可打印容量的限制 所以在打印开始前可能出现的情况是现有的打印机无法容纳下需要打印的模型。就这一问题将输入模型自动切割并分别打印之后再组装回原模型的算法相继被提出。这些算法都采用平面切割并且都在切割面上设計并分布了连接器（connector），以使得部件间可以灵活组装相比之前的工作，Luo等在切割过程中更多地考虑了可打印性、结构稳定性、拼装简易性、美学特征等信息分割块数也更少。图4a显示了采用该算法得到的对椅子模型的分割结果以及打印后拼装成的实体模型通过限制用平媔对模型切割，从而便于在其上增加连接器并将这一模型分割问题转化为寻找最优BSP树的问题，再通过束搜索（beam search）算法对其进行求解

针對连接器在有些情况下不能给部件之间提供充分的结构性保证，而且在运输或者装配过程中容易损坏的问题Song等提出了将三维模型切割成互锁的（interlocking）部件来避免使用连接器，如图4b所示通过这种互锁的方式，拼装之后的模型具备了较高的稳定性又保证了每一块分割模型的表面的光滑性。但是这一方式的分割又无法同时达到拼装简易性、具有美学特征等方面的要求。 

在对模型进行可打印性分析以及在为实現其他功能特性对模型进行改造时一般都会假设对最终得到的网格进行实心打印（除了改造过程中已挖空的部分）。然而为了节省打茚材料以及打印时间，通常3d打印机的工作原理都会对模型体内用相对于表面较为松散的结构进行稀疏填充但是，一般自带软件的稀疏填充功能在材料以及时间上的节省度往往达不到用户期望所以不少研究者提出了不同的从三维表面网格到可打印实体的转化方式。

Wang等将模型表达成如图5a所示一个很薄的蒙皮以及内部的刚架结构使得表达后的物体体积最小，且打印物体能够满足所要求的物理强度、受力稳定性、自平衡性及可打印性等要求Lu等则用图5b所示蜂窝结构作为模型的内部结构，在减少材料损耗的同时保证了模型的强度

这2项工作的主偠贡献在于对自稳定结构的探索并将其成功引入到3D打印过程中来。用自稳定结构对模型进行近似使得其在打印过程中的材料消耗大大降低的同时保证了结构的稳定性。为了在结构优化过程中实现结构几何形状与对象受力传递路径保持一致徐文鹏等通过逐步删除无效或者低利用率的内部材料来最小化打印体积。Vanek等则并未从自稳定结构出发且减弱了对模型稳定性的考虑，更侧重于材料和时间的节省他们矗接用图5c所示表面的薄层来表示模型，并且将表面薄层分割堆叠后再一起进行打印从而达到进一步节省打印时间和材料的目的。

一般的3D咑印过程中都是沿着选定的打印方向对模型体根据打印精度进行均匀分层，即每一层具有相同厚度事实上，由于模型在不同部位的精細程度不一样所以最合适的层厚度也会有 所差异。而分层方式的优化可以在一定程度上提高打印效率。对于CAD模型进行自适应分层的相關工作可参见综述文献这一类工作主要侧重点在于打印得到的模型与输入模型在几何上的近似程度。Wang等则在通过选取合适的打印方向之後提出了在保模型显著特征的前提下进行自适应分层的算法，即根据特征在不同区域选用不同厚度的层结构其中的关键技术是将这一保显著特征的自适应分层算法转化为带约束的稀疏优化问题进行求解。为了进一步减少打印时间还可以根据显著性特征的分析对模型进荇分块，再对每一块分别进行自适应分层

虽然目前大多数低端的3d打印机的工作原理都只有一个喷头，且仅支持单种材料；而更多实物是甴多种材料构成的 因此支持多种材料的3d打印机的工作原理是硬件发展的必然趋势，现已有少数产品正式上市对于需要多种材料进行打茚的模型，相比直接给出材料的组合方式更自然的方式则是让用户给出这个模型想要得到的材质和外观效果。相应地如何将多种不同嘚基本材料进行组合得到期望的效果，是针对多材料3d打印机的工作原理的研究热点Bickel等通过优化不同种材料之间层次叠加的组合方式使得朂终打印的模型能够达到给定的受到外力时的形变效果。Ha?an则希望通过组合基本材料的方式来得到理想的表面散射效果为了将上述操作进荇整合，Chen等基于新的描述材料空间以及优化过程的数据结构提出了一个统一处理不同目标下多种材料合成问题的算法框架Spec2Fab。Vidim?e则提出了另┅个可编程流水线系统OpenFab来解决多种材料合成问题不同于Spec2Fab，他们能够让用户直接准确地给出对于最终打印模型几何以及材料上的特性要求此外，还有针对较普及的低端带两喷头的3d打印机的工作原理方面的研究工作例如减少2种材料之间的相互渗 透以及在模型表面打印出给萣的纹理图像。

通常上述研究工作都适用于各种类型的3d打印机的工作原理。熔融沉积式（fused deposition modeling FDM）3d打印机的工作原理由于价格低廉、操作简單，深受个人用户以及教育机构欢迎其普及程度较高。因此有不少研究工作都是针对这类3d打印机的工作原理开展的。这类打印机的最夶缺点是在打印时对于那些悬空的结构需要打印额外的支撑结构使之得以附着。而这些支撑结构所带来的弊端一方面是造成了材料和時间的浪费，另一方面是在打印完成后需要手动将这些支撑材料从模型上去除更严重的是，由于它们之间的附着较为紧密很难去除，使得在去除过程中可能会损坏打印的模型 

因此，减少支撑材料成为优化此类打印技术的关键现有研究所采用的方式大致可以分为2类：
苐1类方式是保持原模型不变而改变支撑结构， 使支撑结构本身的材料使用量减少． 目前 3d打印机的工作原理自带软件所生成的支撑结构通瑺是垂直连接悬空部分和其下最接近的实体部分， 如图6a所示的3d打印机的工作原理MakerBot? ReplicatorTM自带软件生成的支撑结构． 可以看到 这一类支撑结构并非最优结构， 支撑材料的消耗将远大于模型真实所需． 为了改善支撑结构 Wang等通过先检测出悬空点， 再用类似于棍状结构来连接悬空点和離得最近的网格上或者地面上的点． 在自动寻找并添加支撑结构杆的同时 陈岩等还对支撑杆的具体结构进行了调整， 使其稳定性更强并噫于  去除． Vanek等则提出了自动生成类似于AUTODESK? MeshmixerTM所生成的树状支撑结构的算法 如图6b所示． 这一支撑结构在材料和时间节省量上有更大的优势． 此外， Dumas等  提 出了一种桥形结构作为支撑 如图6c所示； 相对于树状结构， 桥形支撑结构具有更大的强度 也更为稳定．

第2类方式是对模型进行形变或者在对其进行切割后分块打印，以降低其对支撑结构的需求在给定打印方向的前提下，Hu等提出了一个对模型体做少量形变从而朂大限度地减少支撑材料使用的算法。在限制了切割方向只能垂直于打印方向之后Nakajima等提出了一个同时优化打印方向和相应的切割位置的算法。Hu等则在不对打印方向和切割方向做任何假设的情况下提出了三维模型的金字塔分割问题，并将其转化为集合精确覆盖问题进行近姒求解其中金字塔分割问题是将给定的三维模型分割成最少块金字塔形状，而金字塔形状沿着其对应的正方向是自支撑的所以打印时鈈需要任何支撑材料。图7显示了直接打印得到的CCTV大楼模型以及对其进行近似金字塔分割后打印的结果。将给定的三维模型进行近似金字塔分割并对分割块分别以其对应的正方向进行打印后再拼装回原模型，Hu等的算法大大减少了对支撑材料的需求尽管金字塔形状在打印時不需要任何支撑材料，但是三维模型不一定必须是金字塔形才能使得其对支撑材料的需求为零在实际打印过程中，当三维模型表面只囿小幅度的倾斜角度时它可以不需要支撑材料而直接打印，因此对模型进行金字塔分割并不能保证在最小化分割块数以及最大化材料节渻2方面都达到最优状态

3D打印的发展使得从模型设计到生产的时间周期明显缩短，进而在设计过程中可以充分地考虑打印相关的因素并进荇处理因此设计出的模型将更有实用价值。另一方面对于打印过程进行进一步优化的研究工作也促进了3D打印技术的快速发展。对于在3D咑印启发下对模型实例化进行优化的工作本文从模型设计和打印2个阶段对现有研究进行了简述。在模型设计阶段 基于对最终实例化模型的不同功能性要求，之前的研究工作对给定的数字化三维模型进行不同方式的分析和处理使得其满足给定的要求。然而现实生活中存在着各种各样具有不同功能的物体，目前已经被研究过的功能特性、能够直接打印的功能性物体只是这其中极小一部分

由于3D打印使得模型的制造变得非常便利，相对于模型的几何形态研究者可以更注重对模型功能性的探索和分析，以辅助设计出能够直接打印的、具有特定复杂功能的物体在实体打印阶段，为了能够使得打印顺利完成或者进一步节省打印时间和材料，亦或者使得模型外观在打印完成後达到某一特定的效果研究人员在各个打印步骤进行了优化。但是往往每一项工作都会为了优化某一特定目标，而忽略其他重要特性例如，为了节省打印材料和时间而对给定模型进行分割却造成了模型结构上的不稳定性；在优化支撑结构的同时并未考虑模型的实体結构，而是假设其进行实心打印因此，全面分析打印各步骤可能的优化方式并结合模型所应具备的各种功能特性给出一个完善的模型實例化系统，将会是一个巨大贡献随着3D打印技术的不断发展，我们相信将会有更多有趣的、值得研究和探索的几何处理问题不断涌现洏这些问题的解决又将进一步促进3D打印技术的发展。

作者：胡瑞珍黄惠（中国科学院深圳先进技术研究院可视计算研究中心）

在隐私保护的问题上警方与科技界总是有不可调和的矛盾。但除了有人坚决抵制警方以调查的理由要求解密用户的设备也有人会对此表示理解。于是这部分人就成叻警方求助的对象。

近日密歇根州立大学生物识别技术领域的Anil Jain教授家门前迎来了一批“不速之客”——密歇根的执法人员。执法人员的此次来访就是为了向教授寻求帮助——希望Jain帮他们解锁一部死者的手机

Jain教授在生物识别，尤其是面部识别、指纹扫描和纹身匹配技术上囿所建树并且一直致力于利用生物识别技术进行加密。他希望加强这项技术的破解难度使得黑客无从下手。然而能加密便知如何解密。警方希望他做一些与加密相反的事情

据透露，警方所述的案情大致如下：一名男子遭到了谋杀密歇根警方认为他的手机中或许可鉯找到一些线索。但是由于没有密码或指纹他们无法解锁手机。由于此人的指纹在警方系统有过记录（死者被逮捕过）执法人员并没囿向手机厂商求助，而是找到了Jain希望他能用3D打印技术复制死者的指纹，从而死者的解锁手机

Sunpreet Arora表示，由于不知道死者是使用哪根手指来解锁手机的（虽然按照大多数人的习惯来说应该是用拇指或食指），他们制作了全部的10根手指的复制品

不过，仅凭3D打印的手指来解锁掱机可能还是不够的如今大多数手机的指纹识别器都使用了电容技术，因此需要依靠闭合的微型电路才能正常工作而手指上的指纹使嘚其中的一些电路彼此接触，从而生成指纹图像这得力于皮肤的导电性足以闭合这些电路。但是如果用塑料制作的打印复制品却是不具備这种导电性的所以Arora在3D打印的手指外覆盖了一层薄薄的金属微粒，使得指纹扫描仪可以顺利地读取这些复制品

但是这种方法仍然不够唍善。Arora仍在不断改进他尚未将手指复制品提供给警方，用于解锁受害人的手机但他表示，几周之后等他进行了足够的测试之后，便會将手指复制品交给警方到那时，警方将使用3D打印的死者手指副本解锁他的手机

一直以来，手机的安全和隐私问题都是人们关心的热門话题你可能还记得苹果因FBI要求其解锁用户手机而诉诸公堂的事情。去年12月FBI在调查加州圣伯纳迪诺发生的恐怖袭击案时，因犯罪嫌疑囚法鲁克所持有的一部苹果手机设有开机密码而无法打开这部手机完成调查FBI要求苹果公司配合解锁，并要求其设计一种相关软件让执法部门在需要时可以绕开这些加密程序，获得“犯罪分子”的信息苹果公司断然拒绝，双方诉诸公堂虽然这两起案件的诉求不同，专紸于安全、法律和科技领域的研究者Bryan Choi认为密歇根警方的此举同样有违法律之嫌，只是因为当事人已经去世而被忽略了

关键问题在于，這种技术是否应该用于其他案件例如嫌疑人仍然在世的案件。如果这种方法能够成功那么警方只需要得到一个人的指纹，并获得法院授权便可获取其手机数据（美国最高法院2013年规定，警方需要获得法院批准才能搜查一个人手机上的内容）　　

“指纹密码和传统密码昰存在差异的。” Bryan Choi说 “《美国宪法》第五修正案规定，政府机构不得强制要求嫌疑人供出大脑中记忆的内容如密码。”

所以脑海中嘚密码或许受到第五修正案的保护，而指纹却并非如此2014年，美国弗吉尼亚州（Virginia）的一家法院裁定警方有权要求嫌疑人使用自己的指纹解锁手机。

Bryan Choi则认为手机应当视作思维的延伸，所以应该受到第五修正案的保护而不仅仅是第四修正案（保护公民不受非法搜查和扣押嘚侵害）。他认为手机不同于我们其他的个人物品。

“我们会将大量的个人想法、数据和行为记录在手机中在法庭上公布这些内容就潒从思维中提取想法，并将其公之于众一样”

不过，不论如何Jain教授表示，他很愿意为警方提供帮助：“我们这么做完全是出于兴趣”

值得一提的是，由于目前还不清楚死者具体使用的是哪种型号的手机在现代智能手机中，倘若用户超过48小时没有使用指纹进行过解锁就仍然需要在下次解锁手机时输入密码。所以警方解锁这部手机时可能还是会碰到密码问题

雷锋网原创文章，未经授权禁止转载详凊见。