基于手绘的3D概念模型建模

邓媛劼，王 倩

(黄河科技学院现代教育技术中心，河南 郑州 450063)

概念建模方法目的在于产生一个粗糙的概念模型，其方法应该更加符合人的思考和设计习惯，而且更加简单。概念设计的原则应该是基于纸笔。在概念设计中，基于纸笔的设计过程，使得用户的建模具有随意性、模糊性。首先用户习惯用笔绘制物体的2D轮廓，在绘制过程中，可以随意绘制任何拓扑的轮廓;其次，用户的绘制过程只产生轮廓信息，而深度信息却是模糊的。

文中采用变分隐式曲面对物体进行建模，充分利用变分隐式函数闭合，光滑的特性，绘制具有任何拓扑轮廓的物体;采用基于轮廓推测物体深度信息的方法，根据轮廓的宽度信息推测物体的深度信息。

1 概念模型建模设计与实现

1.1 程序框架和轮廓预处理

程序采用MFC框架，使用基于对话框的结构，在对话框中添加static text控件用于图形显示，并添加继承CSTATIC的类SWVIEW，类中使用Windows的消息机制，完成图形的左键绘制，左键拾取、右键旋转、滚轮放缩功能。

程序支持多笔绘制，用户可以绘制一个开放、未封闭的笔画，然后逐步添加开放的笔画，直到形成一个封闭轮廓。程序通过设定两个笔画之间的最小距离MIN_STORKE_DISTANCE来完成这个功能。如果两个笔画的端点小于此距离，则被认为是一个笔画，进行合并，否则认为是两个笔画。程序支持交叉识别、包含识别。通过判断一个笔画的点是否在另一个笔画所形成的多边形中判断两个笔画是否相交，如果一个笔画的点完全落在另一个笔画所形成的多边形中，则判断两个笔画包含。对于相交，则将两个笔画交叉部分的点除去，然后将两个笔画合并成一个笔画。对于包含，则将包含的笔画除去。

1.2 输入点的采样

用户使用鼠标进行笔画的输入，鼠标以固定的频率对屏幕上的移动轨迹进行采样。一般采用基于曲率的［1］采样算法，但效率较差，文中提出了一种间接提取算法［2］。

假设鼠标所采样到的点{pi，i=0，1，2，…，n}，则将其分解为 x 轴上的序列{xi，i=0，1，2，…，n}和 y 轴上的序列{yi，i=0，1，2，…，n}，分别对 x 轴上的序列和 y 轴上的序列求特征值集合。最后根据特征值进行合并。

以x轴上的序列为例，求其特征点集，y轴上的序列同样如此。x轴序列中任意xi的特征点取为其曲率的h2倍。其推导过程如下

该算法具体步骤如下:

(1)求曲线x轴序列的特征点集。计算x(i)每一点的q值并按照一下规则进行判断，若在某一区间内，对于区间内的所有点都有q≤2，则该区间内不存在特征点，这是存在两种情况，一是区间内大部分点的q值都等于零，只有少量q≤2，则可认为是噪音点，该区间对应一条存在噪声的直线段;二是区间内大部分点的q值不为0且＜2，该区间对应一条弯曲程度较小的直线，所以可以假设这两种情况都不存在特征点，若在某一区间内，对所有的点都由q＞2，则该区间对应一条变化程度较大的直线，为更好地逼近曲线，设定适当的步长，找出每个步长内q值最大的点作为特征点。

(2)求曲线y轴序列的特征点集。

(3)综合x轴序列与y轴序列上的点，求pi上的特征点集。对于x轴序列上的任意特征点集px，对于y轴序列上的任意特征点py，设其序号分别为i，j，若≤3，则 px，py对应同一个特征点，若＞3则px，py对应不同特征点。

1.3 简单多边形的约束Delaunay三角化

用户通过鼠标输入的轮廓，在计算机中表示的是一个点序列，这些点连接起来后形成一个简单多边形，在程序中，为寻找轮廓的形态信息，必须将其进行Delaunay三角化，文中采用的算法［3］将Delaunay三角化分为3个步骤进行:

(1)对输入点进行标准 Delaunay三角化，标准Delaunay三角化又分为两个步骤，首先，将输入点按照X轴进行排序，逐点插入，寻找每个点的可见点，其次，对于新插入的边进行优化，判断对角是否＞180°，当所有的输入点插入完毕，则标准Delaunay三角化完成。

(2)调整标准三角化的结果。判断用户手绘的约束边与标准三角化的边是否相交，如果相交，则将其删除，并同时连接另外的对边，对标准三角化得到的图进行调整，使得多边形的边和标准三角化的结果不相交。

(3)过滤调整后的图。判断每个边是否在输入多边形的外部，如果是，则说明其为多边形凸出的边，予以删除。

三角化的效果如图1所示。

图1 约束三角化(CDT)

1.4 求取骨骼点并过滤

一般采用中线轴变换(Medial Axis Transform)或弦轴变换(Cordal Axis Transform)的方法从轮廓中提取骨骼，MAT相对于CAT，计算时间较长，产生的骨架不理想，可逆性较差。文中使用 CAT［4］(Chordal Axis Transform)方法，其步骤如下:

(1)首先对多边形进行带约束的Delaunay三角化，将多边形分解成3类三角形，分别为T三角形，S三角形，J三角形，T三角形有两个外边，S三角形有一个外边，J三角形没有外边。

(2)从CDT中获取离散的CAT骨架。首先任选一条边界边，从该边开始沿顺时针或者逆时针遍历并将边界边编号，将S三角形内边的中点连接起来，对于J三角形，如果是锐角三角形就取其外心，如果是钝角三角形，就取其最长边的中点。

(3)获取整体CAT骨架。遍历每个J三角形，如果J三角形是锐角三角形，则连接其各边中点到外心，如果J三角形是钝角三角形，则连接两边中点到其最长边中点上。

需要注意，当对边界点的采样密集时，会包含噪声或者是小的波动，这会产生非重要形态的骨架分支，而从形态学的意义来说，其并不具有骨骼的意义，所以必须将其过滤掉。首先将每个骨骼分支的重要性予以量化，如图2所示，d代表分支中T三角形顶点到J三角形边的距离，图2中黑色代表分支的T三角形;斜线阴影部分代表J三角形;P代表T三角形一顶点;AB代表J三角形的一条边;d代表p到AB的距离，则这一分支的重要性可以定量表示为λ=d/AB。

图2 计算骨骼的重要性

然后遍历每个分支，求出每个分支的重要性，设置一个阈值，如果这个分支的重要性小于阈值，则予以删除。至此分支过滤完毕，其所求骨骼效果如图3所示。

图3 轮廓的骨骼

1.5 投影获得骨骼点的深度信息

在此之前，所有点的坐标都是视口坐标，必须将其转化到空间视域体中。程序中使用正交投影，根据视口与视域体的比例关系，进行坐标转化，将点投影到视域体z=0的平面内。

前期得到的手绘信息仅是物体的轮廓，没有其深度信息，如果欲构建模型，则必须推断物体的深度信息。文中采用基于轮廓的宽度推测深度信息的推断方法。对于骨骼上的每一个点，根据其CDT的结果，如果骨骼点所在边的三角形是S三角形，则可以找到其所在边所在的四边形;如果是J三角形，且是锐角三角形，则找到骨骼点所在的三角形，然后找到骨骼上点到四边形4个端点，或者三角形3个端点的平均距离，这个距离称为深度信息。由于这个深度信息是模糊的，推测的结果可能并不符合用户的要求，因此，通过增加一系数，并允许用户通过控制这个系数，控制高度的变化，其效果如图4所示。

图4 骨骼上点的深度信息

1.6 确定约束

文中使用两种约束来构造变分隐式函数。

(1)0值约束，即曲面一定经过的点。对轮廓上的输入点进行过滤后得到的特征点，以及CDT后所求的骨骼点，都可以作为0值约束，即f(c)=0。

(2)法线约束，即0值约束点在其法线方向移动若干个单位后得到的点。对于轮廓上的特征点和骨骼点，分别求其法线方向上的约束点。轮廓上的每个特征点都相连两条线段，用这两个线段法线的和作为点的法线，这样线段的长度自然成为权重，单位化后即得。骨骼上点的结构其实是一个图结构，骨骼上每一个点可能连接多个骨骼分支，因此对每一个骨骼段求法线，相加后单位化即可，即f(c)=1。

根据以上所描述的两种约束，求出并可视化，其如下图5所示。

图5 约束的求取

1.7 构造变分隐式曲面

文中使用的变分隐式曲面类似于薄板插值(Thinplate Interpolation)，需要满足两个条件:

(1)满足约束，给定i个约束点ci，且每个约束点有一个取值hi，必须使每一个点满足f(ci)=hi。

(2)光滑，用一个能量函数来量化光滑的概念，即其所有点的曲率和最小，能量函数如下

上式中，fxx，fxy，fyy为 f(x)的二阶偏导数，能量函数表示在区域Ω上所有点的曲率和。

Turk［5］在其文章中推荐使用一组径向基函数的线性组合来构造变分隐式函数，这样的函数可以自动满足两个条件，因此使用这种隐函数只需满足第一个条件即可。文中径向基函数使用Φ(x)=，则其线性组合为

论文使用一组以约束点为中心的径向基函数，其表示形式可以变形为

其必须满足条件一，即

其用矩阵形式可以表示为M*D=H。式中，M为系数矩阵;D为权重向量;H为约束点函数值向量，因为系数矩阵M对称和半正定，则这个方程有惟一解，程序通过LU分解来求解方程，得到权重向量，将权重向量回代函数中，即可构造变分隐式函数。需要注意的是，当约束点较多，方程较大时，则解方程则相当耗时，可以采用迭代法求解。

1.8 可视化变分隐式曲面

通过以上步骤可求得满足约束条件的变分隐式函数，然而为了显示曲面，必须将隐式函数的0值等值面显示出来，隐式函数可视化的传统方法是Marching Cube［6］算法，在程序中，用C++ 实现了经典的Marching Cube算法，其步骤如下:

(1)首先定义曲面与立方体相交的各种情况，曲面与立方体相交有256种情况，但可通过对称性和旋转对称性简化为14种情况，这14种情况可通过对称性和旋转对称性再现为256中情况，并构造出一查询表。

(2)在视域体中划分体素，对于每个体素，计算出与曲面相交的情况，然后查询构造出的查询表，通过三线性插值得到三角网格及每个顶点的法线向量。

三角网格绘制效果如图6所示。

图6 等值面

图6(a)图为 MC算法绘制 f(x，y，z)=x2+y2+z2－1=0的等值面，图6(b)为手绘的手掌所得的等值面。得到三角形网格和所有顶点的法向量后，通过Gouraud－Shading方法进行绘制，得到几何模型的效果如图7所示。

2 结束语

通过建模仿真，实验结果表明，使用变分隐式曲面绘制的模型具有光滑、封闭的特性，而且可以方便地进行融合和其他后续的编辑操作。

图7 Gouraud－Shading绘制

［1］张文景，许晓鸣.一种基于曲率提取轮廓特征点的方法［J］.上海交通大学学报，1999，33(5):592 －595.

［2］刘玉兰.一种间接提取轮廓特征点的算法［J］.计算机工程与应用，2004，40(10):51 －52.

［3］周晓云，刘慎权.实现约束Delaunay三角剖分的健壮算法［J］.计算机学报，1996，19(8):615 －624.

［4］PRASAD L.Morphological analysis of shapes［J］.CNLS Newsletter，1997，139(1):1997 －2007.

［5］TURK G，BRIEN J O.Variational implicit surfaces［EB/OL］.(2009－11－19)［2011－06－19］http://smartech.gatech.edu.

［6］LORENSEN W，CLINE H.Marching cubes:A high resolution 3D surface construction algorithm ［J］.ACM Computer Graphics，1987，21(4):163－172.