朱厚盛 朱春元 鲍宪帅 谢益武(大连海事大学信息科学技术学院 辽宁 大连 116026)

0 引 言

图形构造是指使用点、线结合的方式在二维平面构造出符合实际需要图形的一种有效方法，在平面设计、图形构造、空间模拟等工程领域有着广泛应用[1]。当前常见的图形构造方法有构造几何法和边界表示法等[2-5]。构造几何法通过基本图元构造图形，由于构造几何法可以调整基本图元来修改图形，因而有一定的复用性，但同时缺乏交互性。边界表示法通过直接构造边界来设计图形，直观而简洁，交互性好，但复用性不足。基于以上问题，Kim等[6]提出分解构造合成特征树法改进边界表示法构造图形过程。该方法可以有效地提高边界表示法的复用性，但是对边界表示法的图形构造效率造成一定影响。曹秉万等[7]提出一套实现组合曲面模型的自动特征简化和高质量边界生成的算法，引入离散曲面和虚面等概念，扩展边界表示法自动识别短边、邻近和不光滑边界等四类曲面特征，最终通过若干特征简化和网格生成提高构图效率，但是操作上较为复杂，适用性较低。王鑫[8]提出基于STEP标准的中性文件向MCNP几何文件的转换法，将构造几何法拆分成子模块，通过输入图元数据、特征点分类和MCNP几何文件构造目标图形，有效地提高了构造几何法的交互性和效率性，但是其构造出的图形不具有复用性。因此，当前构图方法的缺点是无法兼顾复用性和交互性。缺乏交互性，设计者的意图很难直观地显示在图形里；而缺乏复用性，则会使得设计者在不同的设计中做一些重复的工作，降低了工作效率。为克服这些缺点，本文提出了一种兼顾复用性和交互性的基于中轴变换的参数化构图方法。本文方法利用中轴的控制点进行交互，确保了构造时的交互性；同时，只需对参数值进行改变，即可构造相似的图形，因而也保证了方法的复用性。

中轴最先是由Blum[9]作为描述几何对象而引入的一种图形的表示方法，是指一个形状内部与边界有两个或以上最近点的点集。由于其出色的性能表现和严格规范的数学定义，使得其在三维打印、碰撞检测和表面重建等工程领域得到了广泛的应用[10]。中轴点与边界的距离称作中轴半径。利用中轴半径，图形中轴可以与图形边界进行变换，这种变换称作中轴变换[11-12]。基于中轴变换思想，丁展等[13]提出一种基于线框映射的中值面提取方法；Zhang等[14]提出基于compensated-convexity的方法用于提取图形的中轴，首先计算距离场函数的平方，然后构造出一个含参数的凸变换函数，最后得到参数二次多尺度的图形中轴；Boussuge等[15]提出一种从给定的B-rep形状中精确提取图形中轴的方法；Zhu等[16]提出一种计算自由曲线图形中轴的方法。由于中轴与图形边界存在基于中轴半径的变换关系，因而也可以将中轴变换应用于图形边界的构造方法中。

本文方法首先通过控制点生成中轴段；然后，通过中轴半径确定图形边界信息；接着，基于上一条中轴段的端点迭代生成中轴段及其边界；最后，基于这些边界信息，构造出图形。

1 常见图形构造方法

1.1 构造几何法

几乎所有图形都可以进行极限分割处理最终得到一系列基本图元数据，这些基本图元是由一些规则的图形组成[17-18]，如三角形、圆等。不过，现实生活中的图形通常比较复杂和不规则，而使用极限分割的构造几何法会比较繁琐。构造几何法在具体实施过程中分为三大步骤：① 确定基本图形；② 对基本图元不断进行布尔运算得到新的图形；③ 调整和优化布尔运算后的图形。通过这种方法构造的图形容易对局部细节进行构造，并且图形的结构层次清晰，易于修改和重用，且效率较高[17]。但是通过这种方法构造图形的过程较为繁琐，需要不断地通过布尔运算来达到最终的图形，导致构造过程中交互性不足。综上，构造几何法有一定的复用性和效率，但交互性不足。

1.2 边界表示法

常见的图形都是由不同形状的线条构成，这些线条也组成了图形的边界信息[17-18]。因此，如果根据图形的边界信息来构造一个图形，可以精确地构造出图形的边界，交互性较好。但是边界表示法只针对图形的边界进行描述，无法体现出图形的特征，因此在对图形进行修改和复用时，需要重新绘制图形边界，在复用性上不足。同时，在构造图形边界时由于边界边的数量较多，构造效率不高。综上，边界表示法有一定的交互性，但复用性和效率不足。

1.3 基于图像的虚拟技术构造法

基于图像的虚拟技术构造法是指通过利用相机等设备采集图形的离散图像或者利用摄像机连续采集图形的视频资料为基础构造图形的一种方法[19]。该方法对采集到的数据进行研究和处理，然后借助图像处理软件进行分析并生成全景图像，再将全景图像通过自适应图形进行加工处理，构造成最终的图形[20-21]。这种建模方法不需要几何建模系统的参与，适应于构造精度要求不高的图形，虽然效率较高，但精度不足。同时，针对不同的图形，均需要重新进行采样收集，没有交互性和复用性。综上，虚拟技术构造法效率较高，但精度、交互性和复用性不足。

2 中轴构造法及相关概念

2.1 方法简介

依据Blum[9]提出的中轴变换理论，每个图形都有其降维表示的中轴变换。因此，当构造一个图形时，可以根据图形的中轴、中轴半径等参数值确定其形状。由于中轴变换是图形边界的降维表示，而中轴可以分解为中轴段，各个中轴段构造简单且易于交互修改，因而使用这种方法构造图形，不仅能够很好地解决图形构造中的效率问题，还可以确保构造过程中的交互性和复用性[22-24]。该方法主要流程如图1所示。

图1 中轴构造法流程

(1) 构造中轴段：首先通过输入控制点的数据来确定中轴段位置。(2) 确定中轴段对应边界：输入特征参数值，结合步骤(1)中已确定的中轴段，共同确定中轴段对应的边界。(3) 迭代生成新中轴段及其对应边界：基于上一条中轴段的端点，重复步骤(1)和(2)，迭代生成中轴段及其边界。(4) 生成图形：最终基于这些生成的边界信息，构造出图形。

2.2 相关概念

本节主要介绍论文中提到的一些相关概念。

中轴：一个形状内部距离边界至少具有两个及以上最近点的点的集合，也可以看成是一个形状的边界最大内切圆圆心的集合[25-26]。

中轴段：由形状内部中轴点的集合所构成的线段，如图2所示，l1、l2和l3都是中轴段。

中轴端点：中轴段两端的点称作其端点，如图2所示，中轴段l1的端点是A(x1,y1)和P(x4,y4)。

中轴缝合点：三个或三个以上中轴段之间的交叉点，如图2所示，P(x4,y4)为中轴缝合点。

中轴方向：中轴段的两个端点之间形成的向量，如图2所示，中轴段l1的中轴方向是(x1-x4,y1-y4)。

边界方向：中轴段与其对应两条边界线之间的相对角度，如图2所示，中轴段l1的边界方向是l1和AB或AC形成的方向角。根据中轴定义可知，这两个角度值相同。

3 方法设计

3.1 构造中轴段

在构造图形之前，首先需要确定图形中轴，其可以通过输入的控制点进行确定。在平面坐标中，给定中轴段的初始控制点和终控制点的坐标位置(x1,y1)、(x2,y2)，连接两控制点即可得到中轴段，如图3所示。

图3 输入控制点获取中轴段

3.2 确定中轴段对应边界

输入中轴段对应的特征参数值，结合3.1节中的已确定的中轴段，共同确定该中轴段对应的边界。根据特征值的不同，可以分为以下三种情况。

1) 当输入的中轴半径值r1=r2=d时，可以得到如图4所示的中轴段对应边界。

2) 当中轴半径值r1≠r2时，可以构造出如图5所示的图形。

图5 半径不等的中轴段构造图

3) 当中轴半径值r1=0且r2≠d时，该中轴段构造出的图形如图6所示，实际是一个内角的角平分线。

图6 角平分线中轴段构造图

3.3 在原中轴段节点迭代生成新中轴段及其对应边界

在3.2节中，通过输入特征参数值，结合已确定的中轴段，可以初步构造中轴段对应的边界。在旧的中轴段节点(起点或终点)的基础上迭代生成新中轴段及其对应边界，基于点P2(x2,y2)继续延伸中轴段至点P3(x3,y3)或点P4(x4,y4)，并给出对应的中轴半径值r3=0，则可以得到新的中轴段l2，根据新的中轴段和中轴半径进而生成新的对应边界，如图7所示。

(a)

3.4 生成图形

重复进行3.3节中的操作，即可得到与中轴对应的所有边界，最终能够构造的图形如图8所示。

(b)图8 中轴构造图形示例

4 算法介绍

当给定中轴的起始点P1(x1,y1)和终止点P2(x2,y2)，并给定边界方向∠AEP1(用α来表示，0°≤α≤90°)和中轴半径值r1=d1，r2=d2，如图9所示。

图9 平面构造图示例

根据中轴段在平面中的坐标可知P1、P2的欧氏距离：

(1)

kP1P2=(y1-y2)/(x1-x2)

(2)

以P1(x1,y1)为参考点，构造水平角α1及α2：

tanα1=kP1P2

(3)

α1=tan-1kP1P2

(4)

根据直角三角形的两角互余和三角形外角定理可知：

α2=α1+α

(5)

|AP1|x=d1×sinα2

(6)

|AP1|y=d1×cosα2

(7)

于是可以求得A的坐标(x3,y3)为(x1±|AP1|x,y1±|AP1|y)，正负值根据kP1P2值的正负进行判断。

具体的距离长度获取算法和坐标获取算法如算法1和算法2所示。

算法1距离长度获取算法

根据给定的半径r和方向角度α，确定边界起始点距离中轴边界点的坐标长度；

根据求得的距离，由getPoint()中的坐标运算确定边界点；

//start

getDistance(r,α){

求得中轴段的斜率k，根据k值转换为α2；

根据α和α2值以及r值求出|AP1|x和|AP1|y；

算法2坐标获取算法

输入：P1和P2坐标点的位置，特征半径r，以及延展方向参数α。

输出：P1和P2端点位置pointP1、pointP2对应的对称边界点point的坐标。

//start

getPoint(pointP1,pointP2,r,α){

if(slope_p1p2>0){

point.x=pointP1.x-|AP1|x

在平台创办主体上，调研的7家平台既有企业创办的，也有创办于事业单位和新型研发机构的，有两家平台还是创业人士为实现个人梦想创办的。创办企业的背景资料显示，有的平台具有科技金融投资背景，有的是资深科技服务机构，有的是行业联合创新中心，都与科技产业紧密关联。在平台规模上，调研发现，科研众包平台普遍规模较小，大的平台有40来个员工，小的则不到20人，人员结构上主要采取“平台运维人员+专业服务团队”的模式，呈现出很典型的互联网企业特征。

point.y=pointP1.y+|AP1|y

return(point);

elseif(slope_p1p2<0){

point.x=pointP1.x-|AP1|x

point.y=pointP1.y-|AP1|y

returnpoint;

}……

}

//end

点A(x3,y3)和点B(x4,y4)也是关于直线lP1P2轴对称，即A和B的对称中心点在直线lP1P2上，因此可知：

(y-y1)/(x-x1)=(y2-y1)/(x2-x1)

(8)

y=(y2-y1)/(x2-x1)×(x-x1)+y1

(9)

kAB×kP1P2=-1

(10)

(y-y3)/(x-x3)×(y2-y1)/(x2-x1)=-1

(11)

将A、B点的轴对称点坐标((x3+x4)/2,(y3+y4)/2)代入式(9)中的(x,y)，并利用式(11)中已知点A坐标(x3,y3)，即可求得对称点B(x4,y4)的坐标。同理即可求得其余C点和D点的坐标值。

若该图仅有一条中轴线，那么接下来的边界可知为圆弧，求圆弧公式如下：

x=x1+radius×cos(angle)

(12)

y=y1+radius×sin(angle)

(13)

式中：P1(x1,y1)为圆心；半径radius=d1；angle为角度。

以上求得各特征点的坐标值后，再结合已有的r=d1处中轴端点，即可构造出图形。

5 实验与结果分析

为了比较三种构图方法的效率性，采取了不同的数据进行实验，实验过程中使用的开发平台是Visual Studio 2015，处理器为Intel i7-8700，内存大小为8 GB，显卡为NVIDIA GTX 1050Ti。实验共分成六组:实验1是利用中轴构造简单图形;实验2和实验4是利用中轴构造不规则图形;实验3、实验5和实验6则是利用中轴构造较为复杂图形。实验构造图形如图10-图15所示。

图12 实验3构造图形 图13 实验4构造图形

图14 实验5构造图形图15 实验6构造图形

5.1 图形构造方法比较

针对不用构图方法分别对实验1-实验6进行多次构图实验并取平均用时，得到数据如表1所示。

使用边界表示法构造图形，需要确定图形的边界信息。因此在构造图形时，如果图形形状和边界信息较少，可以较快地构造出基本图形，具有良好的效率性。但是，如果图形边界信息较多、较为复杂时，需要确定的边界信息也随之增加，此时使用边界表示法构造目标图形的边界耗时明显增多，已经大幅度超过中轴构造法构图时间。

在构造几何法构造图形中，首先需要确定图形的基本图元组成，接着重复对基本图元进行布尔运算并消除重复边界，这使得该方法构造图形的耗时急剧增多，用时远超过另外两种方法，表现出较差的效率性。

中轴构造法在构造中轴信息较少图形时，由于图形内部构造简单，此时其效率比边界表示法稍好，优于构造几何法。但在构造复杂多边形时，利用中轴变换的特征优势，将图形的中轴特征变换为边界特征，使得构造图形时可以很好地简化构图过程，从而降低构图用时。所以，中轴构造法在构造图形上时具有更好的效率。

5.2 交互性分析

通过第4节介绍可知，利用中轴变换的特性以及给定特征参数，可以构造符合要求的图形。下面利用传统的构造几何法和边界表示法分别对图11、图12进行构造过程分析，用于对比本文提出的图形构造方法的交互性和复用性效果。

根据构造几何法中的定义可知，首先确定构造图形需要的基本图元，接着对基本图元不断进行布尔运算，最终消除图元之间的重复边界，确定最后的图形。因此构造几何法的构造过程如下：根据图12的结构，可知其由两个长方形组成，即可选定合适的三角形图元，如图16(a)所示，接着对基本图元进行布尔运算，最后消除图元之间的重复部分得到图形，即如图12所示的图形。构造图11的步骤和构造图12步骤相同，图11由多个图形组成，因此首先需要确定多个基本图元，如图16(b)所示，接着对基本图元进行多次布尔运算，最终才能得到图11所示的图形。

使用边界构造法构造图形不同于构造几何法，它需要确定原图形的边界信息，根据图形的边界信息，一步一步构造图形，最终确定图形的原状，如图17所示。

通过对比三种不同的构造图形方法可知，中轴构造法在构造过程中，通过输入中轴段和特征参数构造目标图形的内部结构和外表特征，在图形构造时有直观的输入输出效果，对图形的结构和边界信息有直接的展示，并且详细地记录了构图过程中特征元素的几何关系及相互间的拓扑信息。此外，该方法在构图过程中强调图形外表的细节，清晰地显示了所有构图元素(点、线、边界)的几何信息和之间的连接关系，具有很好的表达性和交互性。使用边界表示法确定目标图形的边界信息后，输入边界信息构造图形，一步步获得输出边界信息并最终得到目标图形，能够很好地体验构图过程，因此也具有一定的交互性。使用构造几何法，在确定基本图元后，对基本图元进行布尔运算，消除重复边界信息后获得目标图形。该方法通过直接输入基本图元构造目标图形，虽然在输入输出过程中具有一定的交互性，但是图元不同于边界信息，不能很好地展示图形基本构造信息，并且在布尔运算消除重复边界后无法记录各个图元的原始状态，图形边界和内部结构没有任何特征显示，在构造图形时存在交互性不足的问题。

5.3 复用性比较分析

使用中轴构造法在原始图形的基础上构造相似图形时，因为中轴构造法是基于中轴变换和参数化特征进行的，所以在构造相似图形时，对于局部性变化，通过调整对应中轴段和特征参数值即可得到目标图形。如构造图11-图12的相似图形，使用中轴构造法仅需要改变中轴段P1A的长度和对应的特征参数r=0，即可得到相似图形，如图18(a)所示；同理，使用该方法改变图12中轴段PP1对应的特征参数r=d,即可构造出相似图形，如图18(b)所示。此外，在图12的基础上对中轴段PP1的P点和P1点进行延展和特征值化，可以得到相似图形，如图14所示。当需要对原图形进行整体变化时，根据中轴构造法的定义，通过同步改变原始图形的中轴段和特征值，可以快速得到目标图形。中轴构造法在构造相似图形时极大地简化了构造步骤，其具有较好的复用性。

(a) (b)图18 中轴构造法构造相似图形

使用边界表示法在已构造图形的基础上构造相似图形时，由于边界表示法基于边界信息构造图形，当图形局部特征发生变化，需要重新修改对应的边界信息并重新进行构造，如构造图11的相似图形时，需要调整边界AB和CD信息并进行重新构造，如图19所示。构造图12的相似图形时，需要重新调整边界AB、HG和圆弧AH信息并进行构造，如图20所示。该过程在构图中耗时较多，复用性表现较差。当对原始图形进行整体变化时，由于边界信息不同于基本图元信息，当边界信息发生变化时，需要重新确定边界信息。此时使用边界表示法，需要对所有边界信息进行变化才能构造目标图形，因此几乎没有复用性。

图20 边界表示法构造相似图形

在构造几何法中，基于基本图元构造图形在对原始图形整体进行变化时，可以同步调整原始基本图元的大小，再对变换后的基本图元进行布尔运算即可构造目标图形，此时具有较好的复用性。当需要对原始图形进行局部变化时，使用该方法只需要对局部基本图元信息进行调整，再重新对调整后的基本图元进行布尔运算，便可以构造目标图形，如构造图11-图12的相似图形时，仅需调整图21(a)中E图元和图21(b)中的A图元即可，此时构图的复用性表现较好。

(a) (b)图21 构造几何法构造相似图形

使用三种方法分别对实验2-实验5等多边图形多次进行复用性构图实验并取平均用时，得到如表2所示数据。

通过对比三种不同的图形构造过程，从构造图形的过程和用时可知：构造几何法有一定的复用性和效率，但构图过程中交互性不足，无法很好地表现出图形的自身特征；而边界表示法有一定的交互性，但复用性和构图过程中的效率不足；基于中轴变换的参数化图形构造方法则在效率、交互性上均具有较好的表现，同时参数化的方式可以使得构造出的图形能以数据的形式进行存储。因此构造图形时采用中轴变换的参数化构图方法，综合来看具有更好的性能。

6 结 语

使用中轴构造图形的方法是简单、高效和可行的，可以在此基础上实现各种不同的图形构造。相比传统的构造几何法和边界表示法，利用中轴构造法构造图形不仅仅更加简单、高效，具有很强的交互性，而且还有很好的复用性。另外，通过坐标数据来描述中轴和特征值，具有很好的数据结构，十分便于保存和复原。此外，当利用中轴构造相似的图形时，仅需要改动特征参数值即可达到预期效果，极大地提高了原有数据的利用率，具有极佳的复用率。因此本文的主要贡献在于：(1) 利用中轴的特性构造图形，只需提供相关参数值就可构造出符合要求的图形，具有很好的交互性；(2) 根据中轴的数学定义，中轴和参数值的数据可以选择适当的数据结构进行保存，数据重用性很高；(3) 构造相似的图形时，只需适当更改参数值，即可得到所需的新图形，极大地提高了构图过程中的复用性。

未来的工作将主要集中在使用该方法生成复杂结构的图形，同时将其合理有效地拓展到三维空间中，并进一步研究如何利用中轴实现三维模型的模型构造。