基于部件替换的三维模型生成方法

李雪艳+华顺刚

摘要：对给定的两个三维模型进行层次构建与部件替换，生成一系列新颖的模型。首先对模型进行接触分析、对称检测和层次结构生成；然后通过形状匹配确保两个模型生成的层次节点一对一匹配，进而通过部件替换生成若干模型，最后进行部件连接确保模型的接触合理性。实验表明，该方法可以快速生成一系列与原模型在外观上有所不同，但具有类似的对称和邻接结构的新模型。

关键词：层次结构；形状匹配；部件替换；部件连接

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）25-0184-04

Abstract： A series of novel 3D models are generated based on given two models by constructing their hierarchy structures and replacing parts. First the shape analysis is implemented ，which involves contact analysis， symmetry detection and hierarchy structure generation. Then a one-to-one node mapping is established by shape matching，and new models could be generated by part replacement. Finally， parts is connected to ensure the contact reasonability of the generated model. Experiment results show that the method is competent to quickly generate varies of novel models which are similar to the original model in symmetry and adjacent structure， but different in appearance.

Key words： hierarchy structure； shape matching； part replacement； part connection

随着3D建模技术、模型分割技术及在线3D模型库的发展，三维模型创新设计已成为一个热门研究领域，如何管理、重用现有网格模型，如何根据新的设计目标修改已有模型，现已成为三维建模的研究热点，三维模型的设计思路将从传统的软件建模，发展为快速寻找并重用现有模型进行模型生成。

由于传统的3D建模比较繁琐，近年来，一些利用已有模型进行模型生成的方法已被提出。Thomas等[1]提出了一种数据驱动合成方法，来构建三维几何表面模型，基于部件的几何相似性，通过交换将模型的部件进行融合与匹配，利用智能剪裁分割出所需部件的网格模型，并按照相应的方式将他们组合在一起生成新的三维模型。此方法只允许沿着现有网格的顶点和边缘进行分割与连接，不能自适应地分割三角形。Karevoy等[2]设计的一个模型生成系统（The Shuffler System），考虑部件的几何相似性和部件的接触信息，允许用户加载一组人工选定的兼容的三维模型，并快速交换模型之间的相似部分。该系统依赖于一种所有模型都兼容的分割方法，只能用于用户的当前模型不能用于其他模型，需要用户控制生成模型的形状以确保其合理性。Siddhartha等[3]提出了一种利用统计几何处理技术来进行数据驱动建模的方法，该方法支持开放阶段的建模过程，利用形状检索和形状对应，从简单的三维模型中获取一些组件，这些组件能被添加到设计者的当前模型中，激发设计者的创作灵感，但算法只考虑了几何属性，没有考虑部件的语义功能。Talton等[4]的探索性建模系统适用于数据驱动的方法来支持开放式三维建模。它依赖于一个参数化空间，在这个空间中设计新的三维模型。Bokeloh等[5] 对三维模型进行分析，提取潜在的对接部位，使有意义的逆过程建模变的可能。徐凯等人[6]提出通过使用图像轮廓线约束变形零件，利用图像激发3D模型创作。形状生成的另一种方法[7]是基于统计模型创建实例，这是一种常用的纹理生成方法，将模型分解为多个纹理元素，然后重新组合这些元素生成新的模型。当生成的模型有一个复杂的层次结构时，基于局部相似性的统计模型是无效的。

本文通过计算已分割模型部件间的对称和接触关系，由粗糙到精细构建模型层次结构；然后根据位置信息对层次中的节点进行匹配以及层次结构的再生成；接着进行部件替换，生成新的模型；最后通过部件连接确保部件间合理接触。本文方法进一步简化了建模接口，不用直接操纵几何形状，能够在已有模型库的基础上自动、有效地生成一系列新模型。

1 形状分析

要实现模型的重组，首先对单个模型进行形状分析，包括接触分析、对称检测和层次结构生成。整个形状分析过程如图1所示。

由于模型分割技术的不断发展，现已存在大量的已分割模型库。为便于分析，首先对模型进行规则化处理，使其具有一致的主轴方向；进而采用将模型包围盒的最长边缩放为1的方法对模型进行归一化处理，使模型缩放的一个立方体内，采用的包围盒是Axis-aligned bounding box （AABB）包围盒，该包围盒是与坐标轴对齐的包围盒， 构造简单，存储空间小，且能达到本文所需要求，故采用此包围盒。

1.1 接触分析

部件间的接触点描述一个模型的连接关系，找到模型中各部件的接触关系，并保存接触点，为后续分层和形状匹配做准备。接触分析过程如下所述。

由于每个三维网格模型都包含大量的三角面片，若直接计算两部件间三角面片是否有接触，计算量较大。为了提高程序运行效率，首先判断两部件的AABB包围盒是否接触，由于该包围盒包围物体时不紧致，即便两包围盒有重叠，还不能直接断定两部件有接触，需要进一步判断两部件的三角面片是否有接触。判断两三角面片T1（来自部件1）和T2（来自部件2）是否接触的流程图如图2所示：

其中判断交点是否在T2内采用的是同向法。假设三角面片的三个顶点为ABC，当沿着ABCA的方向在三条边上行走时，若点P始终位于边AB，BC和CA的同侧，则点P就在三角形内。利用叉积来判断P是否位于三个边同侧，连接PA，将PA和AB做叉积，再将CA和AB做叉积，若两个叉积的结果方向一致，那么两个点在同一侧。用点积判断两个向量是否同向，若点积结果同为1，则两向量同向，否则，两向量不同向。

按照上述过程遍历两部件的所有面片，将T1中与T2相交线段的两个端点中距离T2较近的端点作为接触点保存起来。遍历模型的所有部件，保存所有的接触部件和相应的接触点。

1.2 对称检测

对称检测是计算机图形学领域的热点问题，其广泛应用于三维几何模型的形状匹配、检索、对准、重网格化、模型分割等领域。对称性通常被视作连接三维形状低层几何属性和高层语义信息的桥梁，对称作为一种几何属性，其定义和检测可以完全基于几何信息，同时对称性对于模型结构和语义分析具有重要作用[8]。本文利用对称性对模型进行分层细化，并利用层次节点的对称来简化部件替换过程，提高程序的运行效率。

由于已将模型主轴方向处理一致，把x=0面作为对称面，只需计算x=0面的两侧是否存在对称部件。可根据两部件的AABB包围盒是否对称来判断两个部件是否对称。对称检测步骤如下：

1）判断两部件的AABB包围盒的中心距离是否小于某个阈值，若小于阈值则进行步骤（2），否则，可判定两部件不对称。

2）判断两部件AABB包围盒的对角线向量的夹角和长度是否分别小于某个阈值，若均小于各自的阈值，则两部件对称，否则两部件不对称。

经过实验验证分析，将两部件AABB包围盒中心距离的阈值threshold1设定为0.01，包围盒对角线夹角的阈值threshold2设定为5?，包围盒对角线长度的阈值threshold3设定为0.01，可正确检测出模型中存在的对称部件。

1.3 层次结构生成

此过程为模型生成由粗糙到精细的层次结构，每一个层次包括若干个层次节点N，该节点由若干个相互连接的部件组成，并利用对称检测找到节点N的对称节点，记录节点N的各种信息，如节点中心、节点大小、父节点等，用于形状匹配。层次结构生成的流程图如图3所示：

用k表示层次结构的层号（k=0，1，2…n）。当k=0时，表示第0层，包含一个节点，这个节点包括模型的所有部件。当由较粗糙层k生成较精细的层次k+1时，将k层上的每个父节点分割成两个子节点，并把生成的子节点分配到k层上。若节点中存在对称的部件，分割时将把对称信息考虑在内，把对称的部件分别分配给两个子节点。若某些部件的中心距离分割平面非常近，则认为这些部件的中心位于分割平面上，并将这些部件添加到第三个节点中去。分割操作后，若父节点至少生成了两个子节点，并且每个子节点至少包含一个部件，则认为分割操作是成功的。若父节点中不存在对称的部件，或父节点中存在对称的部件，但基于对称面的分割操作不成功，则将父节点坐标系中的x=0面作为分割面，若此分割操作仍然不成功，则依次将y=0面、z=0面作为分割面进行分割。如果按任何一个分割面分割都不成功，则这个父节点只生成一个子节点，且包含父节点的所有部件。若分割成功，计算并保存每个子节点对应的节点信息。对称检测也将在每个子节点中进行，并记录节点中对称的部件。

由于在层次生成的过程中没有考虑部件间的接触信息，一个子节点中包含的部件可能是分离的。例如子节点中的一个或多个部件与其他部件不连接，这就需要重新调整层次k的节点，确保每个节点所包含的部件都是接触的。这一过程的步骤如下：

1）根据记录的部件间接触信息，重新调整k层的节点，原节点中如果存在分离的部件，则将原节点分成两个或多个节点。

2）为保证新生成的节点与原来的节点数目相同，需要对节点进行合并。将节点按体积大小排序，把体积最小的节点与其接触的体积也较小的节点进行合并。

通过以上分离和合并步骤，再次生成的每个节点所包含的部件都是一个整体，不再存在部件与部件间分离的情况。迭代进行以上分层过程，直至某个层次的每个节点都不能再进行分割，则层次构建结束。至此，形状分析过程完成，其结果将用于形状匹配。

2 形状合成

单个模型的形状分析完成后，对两个模型之间的形状进行合成，形状合成包括形状匹配、部件替换和部件连接三个部分。

2.1 形状匹配

一般情况下，两个模型所含的部件个数是不同的，所以部件间很难形成一对一的匹配。显然，由不同部件个数构成的模型生成的层次结构也不能实现一对一匹配，这就需要调整两个模型层次结构中每层的节点个数，以便形成节点间一对一匹配。如图4（a）所示，S1汽车模型作为原模型，S2卡车模型作为目标模型、每个模型的节点个数是相同的，但是为了形成一对一匹配，汽车车身将与卡车的两个部件卡车车身和尾部的一个轮胎相匹配，这样就会造成不合理的匹配。图4（b）是在匹配的过程中，为了适应S1的层次节点为S2生成的新的层次节点。

形状匹配算法实现过程如下所述：

1）构造一个与原形状S1完全相同的层次结构LS，使其每个节点都为空节点，得到一个与S1的层次结构完全对应的空层次结构，使其在形状匹配过程中起到纽带作用。

2）根据最邻近匹配原则，将目标形状S2在各层节点所包含的部件分配到与其对应层的对应节点，即将与原层次节点中心距离最近的目标层次节点的部件分配到新构造的层次结构的对应层的对应节点。如果在原节点中有两个节点距离同一个目标节点都最近，则判断目标节点距离哪一个原节点最近，将目标节点与其距离最近的原节点相匹配，并将目标节点所包含的部件添加到与原节点相对应的LS的节点中，这样与未被匹配的原节点相对应的LS节点就是空节点了。

3）新生成的层次结构中有空节点存在，将空节点移除，并将对应的原层次和目标层次节点合并到具有共同父节点且接触的节点里。如果对应的原层次或目标层次节点没有与其共享父节点的节点，则将其合并到当前层体积最小且与其接触的节点里。

对各个层次进行迭代，使S1和S2层次结构完全相同，每层的节点一一对应。模型的形状匹配过程如图5所示：

2.2 部件替换

形状匹配后，在层次结构的最精细层（最后一层）进行部件替换，，通过替换两个模型层次结构中最后一层相匹配的节点来生成新的形状。部件替换时要控制替换顺序，进而有规律的生成若干模型。具体的部件替换控制方法如下所述：

通过设置一个权重[0，1]来生成新的模型 S（），其中新生成的模型S（0）=S1，S（1）=S2，。在形状生成的过程中，S1的部件只能被S2的部件替换一次，并且不再进行逆替换。这个过程通过以下方法来完成，用表示一个层次结构的第k层有n个节点，实例化一个新模型时令个节点来自S2，剩余的节点来自S1，这样就能控制哪个模型的哪个节点被替换，有规律的生成若干模型。如果两个节点是对称的，则其同时被实例化或不被实例化。

在替换的过程中，随着的增大，索引小的节点将首先被实例化，为了使实例化时按照一定的规律生成新模型，将原模型S1最后一层的节点按照节点体积由大到小排序，同时将目标模型S2的最后一层也作相应的调整，以保证节点索引一一对应。这样体积大的节点将首先被实例化，新生成的模型将逐渐由S1向S2过渡。

2.3 部件连接

通过部件替换生成的新模型，由于不同部件的尺寸，坐标位置不同，替换的部件放置的位置可能不合理，这就需要重新调整部件放置的位置。用代表两个部件间一系列接触点的集合，如果部件j在当前节点中，部件k在另一个节点中，则每个节点与其连接的节点的接触点P通过以下公式求得：

其中为求得的部件j和部件k的接触点。如果原模型S1的部件j被目标模型S2的部件h替换，则将h所在节点对应的接触点平移到接触点，并将h所在的节点作相同的平移，实现部件h和部件k良好接触。

3 实例验证

在Visual Studio2010开发平台下，采用C#编程对本文算法进行实例验证。下面以两个飞机模型为例详细讲解

本方法的实现过程， fighter1、fighter2的层次构建结果分别如图6、图7所示：

由图6 fighter1层次结构的第1层（即k=0）包括一个节点，这个节点包含模型的所有部件。节点中存在三对对称的部件，按对称平面将模型分割，得到k=1层上的三个节点，第1个节点包含右上、下羽翼和右引擎三个部件；第2个节点包含一个躯干部件，第3个节点包含左上、下羽翼和左引擎三个部件，利用对称检测得出节点1与节点3是对称的。接着再分割k=1层的节点，由于三个节点中不存在对称的部件，则先按x=0面分割，由于节点1包含的三个部件的中心位置都在x=0面的右侧所以导致分割不成功，再按照z=0面分割，由于右上羽翼与右引擎的中心都在z=0面的上方，这两个部件被分配到同一个节点中，右下羽翼的中心在z=0面的下方，被单独分配到另一个节点中去。同理，节点3也被分割成了两个节点。第2个节点只包含一个部件，因此不必再被分割。随着k=1层的节点被分割完毕，k=2层的节点完全生成了。按照以上过程依次生成第3、第4层的节点。图6中第4层中的每个节点都只包含一个部件，模型fighter1的层次结构构建完毕。

Fighter2层次结构生成过程与fighter1类似，不同之处在于对其层次结构的第2层进行了节点的再生成。第1层的节点中存在四对对称的部件，按照对称轴进行分割，得到图7中a、b、c三个节点，由于节点a和c中包含的部件存在分离现象，所以要重新划分节点，确保节点中包含的部件都接触。重新划分后，由节点a得到节点d和e，由节点c得到节点f和g。为了使节点个数与刚分割时的节点个数相同，需要对有接触部件的某些节点进行合并。将节点d、e、f、g、b按体积大小排序，使节点体积小的节点和与其有接触部件的节点合并，如果其与多个节点都有接触的部件，则将其合并到体积较小的节点中。由于节点e的体积最小，并且其只与b有接触，所以将节点e合并到节点b中；由于节点f与节点e对称，节点f也同时被合并到节点b中，合并之后得到三个节点，与刚分割时的节点个数相同，停止合并。通过节点的重划分和再合并生成了图7中k=1层的三个节点，它们包含的部件都是相互接触的，说明节点再生成完毕。

fighter1与fighter2层次结构中最后一层的匹配结果如图8所示：

图8中节点索引按照体积大小得到，当索引为0时，代表节点体积最大，替换时将首先被替换。图中1 和2，3和4，5和6分别对称，节点替换时对称的节点将被同时替换。fighter1与fighter2模型重组的结果如图9所示：

fighter1与fighter2模型重组之后得到的部分新模型接触不合理，如图9所示的shape1，左、右下羽翼与躯干没有接触。对模型进行部件连接后得到的结果如图10所示，可以看出模型部件间接触良好。

图11为若干模型重组结果实例，重组结果显示本文方法可以较好地实现两个来自同类模型集中模型间的重组，生成的新模型较为合理。

4 结论

本文实现了一种基于部件替换的三维模型生成方法。在形状分析阶段中考虑了单个模型部件间的接触和对称关系，并为每个模型生成一个由粗糙到精细的层次结构；形状匹配过程通过节点中心的位置关系实现节点一对一匹配；部件替换时通过节点体积大小和权重来控制新生成的模型形状；对新模型进行部件连接以实现节点间合理接触。由于匹配时仅考虑位置信息，所以本文方法对部分同模型集的模型适用，对一些比较复杂或不同模型集中的模型难以适用，可能会导致重组生成的新模型在结构上不合理。下一步研究将通过增加一些约束条件优化本文算法，使其适用于更多更复杂的模型，使重组后生成的新模型更加合理且更加多样化。

参考文献：

[1] Funkhouser T， Kazhdan M， Shilane P， et al. Modeling by example[J]. In Proc. SIGGRAPH ，2004，23（3）：652–663.

[2] Kraevoy V， Julius D， Sheffer A. Shuffler： Model composition from interchangeable components[J]. In Proc. Pacific Graphics ，2007， 129–138.

[3] Chaudhuri S， Koltun V. Data-driven suggestions for creativity support in 3d modeling[J] ACM Trans. Graph. ，2010，29（6）：183–183.

[4] Talton， J.O，Gibson， Yang， L， et al. Exploratory modeling with collaborative design spaces[Z]. ACM Trans. Graph. 2009.

[5] Bokeloh M， Wang M， Seidel H. A connection between partial symmetry and inverse procedural modeling[J]. In ACM （Siggraph） ，2010， 29（4） ：104：1–104：10.

[6] Xu K， Zheng H， Zhang H， et al. Photo-inspired model-driven 3d object modeling[J].ACM Siggraph，2011，30（4）：80：1-80：10.

[7] Efros A， Leung T. Texture synthesis by nonparametric sampling[J]. In Proc. ICCV ，2002， 2： 1033–1038.

[8] Mitra N， Pauly M， Wand M， et al. Symmetry in 3D geometry： Extraction and applications[R]. In Proceedings of Euro graphics STAR Report 2012.