一种基于共形几何的数模表面网格生成方法

专利主权项内容

1.一种基于共形几何的数模表面网格生成方法，其特征在于：所述方法包括如下步骤：步骤(1)、根据输入的三维模型数据判断三维模型表面是否可定向，计算曲面的亏格数目和边界数目；步骤(2)、根据计算得到的拓扑结构选择合适的共形映射函数，根据曲面单值化定理，将三维数模表面共形映射到球面，欧式平面和二维双曲空间中的一种；步骤(3)、根据所选的共形映射函数将三维模型共形映射到二维参数域上；步骤(4)、根据共形映射的结果，在参数域上进行有限元网格剖分，按需生成三角形单元网格或四边形单元网格；步骤(5)、根据共形映射过程中保持的角度，将重新剖分后的网格逆映射回三维空间域中，生成带表面网格的三维模型；步骤(1)中，三维空间区域到二维参数区域的共形变换能保持曲面角度不变，在平面参数域上进行网格剖分可以极大地减少插值的计算量；在步骤(1)中，将三维模型理解成连通的曲面进行处理，曲面的拓扑结构由是否可定向，环柄数目即亏格和边界数目所决定；在步骤(3)中，根据步骤(2)中判断的三维模型拓扑结构，将曲面共形变换到三种标准空间中的一种：球面，欧式平面和二维双曲空间；在步骤(4)中，网格剖分有两个重要的步骤：根据已知的网格拓扑结构，在待剖分区域内合理分布网格节点；将网格节点有效地连接起来，形成三角形或四边形单元网格，其中三角网格的生成遵循Delaunay法则；在步骤(5)中，按照步骤(2)中选择的共形映射函数对参数域剖分后的网格进行逆映射，并保持节点间的拓扑关系不变，局部面元的变化率和曲面的平均曲率完整地保持了原来曲面所有的几何信息，根据面元变化率和平均曲率来完全重建原始数模曲面；所述三维模型均可视作连通的曲面，对三维模型表面进行共形参数化可视作对曲面进行参数化映射，整个三维模型表面网格生成过程在数学上等价于求从曲面空间域到平面参数域的一个光滑双射；该方法具体的实现步骤：(1)根据所给三维模型，将其转换成可存入半边数据结构的.off或者.obj格式，首先，在半边数据结构中对模型进行边界识别，在遍历的过程中把只有一个邻接面的边当作边界边，如果边界边之间有闭环，则可当作存在一条边界；然后对曲面进行亏格识别，把能在曲面上画出而又不把曲面分割开的互不相交简单闭曲线的最多个数当作该模型曲面亏格的个数，统计曲面的边界个数和亏格个数，存为曲面的拓扑信息进行下一步；对于亏格为0的曲面，可以由调和映射来计算其共形结构，假设两个0亏格网格曲面M，M, h : M→M表示曲面的度为1的映射，接下来最小化调和能量E(h)，1212h的拉普拉斯方程可以简化为：Δh＝(Δh, Δh, Δh)PLPL0PL1PL2如果h是调和的，那么Δh的切向分量为0，定义投影算子：PL其中为张量积，I为单位矩阵，当且仅当h满足：时h是调和的，其中n是M的法线；2添加额外约束，迫使表面的质心位于原点：
是M的面积，在这个约束条件下构建偏微分方程：1h的稳态解是M到M的共形映射；12对于亏格为1的曲面，通过全纯微分来计算，基于Hodge理论，算法如下：输入网格曲面M，输出全纯微分基形式计算同源群基B＝{e, e, …, e}；122g计算对偶上同调群基Ω＝{w, w, …, w}；122g将每个w分散成调和1形式ζ；ii计算每个ζ的共轭，表示为*ζ，构造全纯1形式ii对于任意亏格的曲面，曲面的共形结构通过离散Ricci流来计算，具体步骤如下：假设给定带度量的曲面间的光滑映射(S, g)→(S, g)，局部上，非线性的映射/>用其一阶近似，切平面间的线性映射来逼近，即导映射：1122
会带来各种畸变，这些畸变的测量需要用到黎曼度量，对于任意一点p∈S，/>都是等距，或者保角，保面积，拟共形，则整体上/>是等距，或者保角，保面积，拟共形；1共形度量的计算和嵌入过程如下：通过黎曼度量计算长度、角度、面积和曲面S上的微分算子，在参数化过程中，黎曼度量被共形改变，除角度外的其他相关量也相应的改变，直到度量g变化为那么此时高斯曲率将变为：其中Δ为原始度量g的拉普拉斯算子；此时的测地曲率将变为：根据Gauss-Bonnet公式，总曲率和黎曼度量的选取无关，可以证明，存在唯一的共形度量使得目标曲率是常数而测地曲率为零；通过曲率控制来进行参数化的过程，即寻找合适的共形度量eg，使之诱导的曲率与预设之目标曲率一致即可；2u在光滑情形下，共形形变将无穷小圆映射到无穷小圆并保持圆与圆之间的交角，离散情形下，通过circle packing方法的引入在网格的每个顶点处设置一个半径为γ的圆，不同的圆互相相交；i在欧氏背景中，共形形变在保证圆与圆交角不变的情况下，通过改变半径达到参数化的目的，离散的Ricci曲率流有着和光滑情形Ricci流方程类似的形式：在球面或双曲几何背景下，使用Ricci曲率流来计算球面度量或者双曲度量时，过程和欧氏情形下一样，在计算几何量时，使用相应的球面几何或者双曲几何；假设双曲圆(c, r)以c为圆心以r为半径是欧氏圆(C, R)，满足：其中u＝(e-1)/(e+1)；rr接下来要先将第一个面[v, v, v]嵌入到双曲空间中，参数坐标分别为：012把与第一个面相邻的面f嵌入其中，假设顶点v, v已经在双曲平面中了，第三个顶点v即为以v, v为顶点的两个圆的交点，以同样的方式，将其他与f相邻的面都压入堆栈，按顺序嵌入到双曲平面中，双曲空间中的嵌入方式，和欧氏空间的嵌入方式一样，同样，在球面几何下嵌入的方法，也和欧氏空间及双曲空间下一样；ijkijkijijk直接变分法思路如下：用分片线性映射来表示从三角网格到平面区域的映射，M→D，固定一个三角形，将其铺到平面上，用v, v, v来表示顶点的平面坐标，用/>来表示顶点像的平面坐标，则线性映射矩阵可以直接写出：ijk如果e为0，则限制在此三角形上的线性映射为保角变换，整个映射和等距变换的差距定义为：ijk这里s代表相应三角形的面积，然后用非线性优化方法来优化这个能量，并将所得结果作为全局保角变换的近似：ijk如果目的是寻求保面积变换，则：e : ＝(λλ-1)＝(det(A)-1)ijk122ijk2如果目的在于等距变换，定义局部能量：e : ＝(λ-1)+(λ-1)＝(λ+λ)-2(λ+λ)-2λλ+2ijk12221221212等价地：e : ＝tr(A)-2tr(A)-2det(A)+2ijkijk2ijkijk下面是离散Ricci曲率流算法的具体步骤：1.通过最小化能量方程：为网格的边及顶点分别赋初始边长及半径，可赋初始值：2.使用余弦定理计算当前网格的黎曼度量即边长：3.计算网格的所有内角：4.为每个顶点计算离散的高斯曲率K：i5.使用如下公式更新顶点半径γ：i其中ε为步长；6.单位化网格顶点处的半径，使其乘积为1：7.检查当前曲率K与目标曲率之差，选取其中差距最大的：i当误差小于阈值，停止计算，否则跳调回第二步，选取一个顶点v，误差曲线为一条指数曲线；i(2)网格剖分的两个主要步骤分别是布点和单元格生成，网格的节点可以分为边界节点和内部节点两类，以下为两种节点的布点方法：1.边界节点的生成方法如果给定区域边界是以直线、曲线的方程形式给出，设定三角形单元的剖分尺寸为d，以d来等分区域边界，从而可以计算出边界节点的坐标；如果区域带有内部约束，其内部特征约束可以作如下处理：如果是点，直接把点当成边界节点计入节点数组中；如果是直线段、圆弧、曲线等组成的不封闭的环，将它们看成是有向曲线，并抽象成面积为零的封闭环，当作内边界环来处理；2.内部节点的生成方法对于内部节点的生成，在传统平行线布点的基础上，采用两组等距平行线交叉成60°角的布点方法；具体布点方法如下：先求出区域的横坐标和纵坐标的最大值X、Y及最小值X、Y；再在平面区域的最小矩阵包容盒内布点，Y＝Y和Y＝Y这两条线是极限扫描线，在这两条线之间可以生成等距的横向扫描线，条数为：maxmaxminminmaxminM＝int[(Y-Y)/(length×sin60°)+0.5]maxmin扫描线的方程为：Y＝Y＝Y+(Y-Y)×i/M i＝0, 1, 2…Miminmaxmin扫描线上点的个数为：N＝int[(X-X)/length+0.5]maxmin扫描线上点X的坐标为：其中i＝0, 1, 2, …M；j＝0, 1, 2, …N；k为自然数；扫描线上相邻两点间的距离是length，相邻扫描线间的距离是length×60°，length/2为纵向相邻两点错开的距离，这样可使得内部节点容易形成等边三角形；按上述方法布点之后，删掉外边界以外和内边界以内的节点，去掉距离边界较近的节点以保证网格剖分的质量，剩余的节点就是内部节点；平面区域三角网格生成采用Delaunay三角剖分法，假定S为E空间的有限点集，点集S的Delaunay三角化定义为满足以下条件的单纯形单元复形D(S)：d复形D(S)的0-单纯形组成的集合(即D(S)的所有顶点的集合)是S的子集；复形的底空间是点集S的凸包CH(S)；任意一个d-单纯形Δ∈D(S)，|T|＝k+1，满足：任意q∈S-T，q在Δ的外接球外；TT在二维参数域中生成三角网格后，再按照参数域到空间域的映射函数将参数域的网格共形映射成空间域的网格，并保持节点间拓扑关系不变，得到的空间域的网格就是所求的曲面三角网格。 来源：百度搜索马克数据网