一种基于拉普拉斯坐标的网格细分方法
一种基于拉普拉斯坐标的网格细分方法
【技术领域】
[0001] 本发明涉及三维网格模型的建模和细分技术，具体地说是涉及到保持三维网格模 型指定特点的精细度提高技术。
【背景技术】
[0002] 目前，在计算机图形学中，随着计算机硬件的不断发展，图形处理能力越来越强， 为了实现高真实感，许多计算机图形应用都使用复杂的，具有高精度细节信息的模型。因此 常用模型的构造常常需要高精度的。虽然，有三维扫描之类的技术来一次性获得高密度的 顶点，但是，仅仅依靠扫描还满足不了人们对三维模型的日益增长的需求。那么，人们需要 根据自己的想法使用各种工具设计出模型。直接逐个确定高精度模型的顶点，是比较冗余 繁琐的工作。通常人们是先构造出一个基本符合要求的低精细度的网格模型，然后再使用 工具在保持指定特点的同时，提高网格模型的精细度。另一方面，三维扫描所得的模型，由 于设备的级别不同，有些时候也还是精细度不够。因此，人们迫切需要一些可以提高网格模 型精细度的技术。网格细分就是其中一类重要的技术。
[0003] 细分技术，能够从一个任意的拓扑网格结构构造出一个极限连续的曲面，是20世 纪70年代提出的一种曲线曲面造型技术。根据细分后的极限曲面是否插值初始的控制网 格，分为逼近细分和插值细分。
[0004] 逼近细分已有不少经典算法：Catmull-Clark细分方法基于四边形网格，采用1-4 四边形分裂算子生成新网格，其中使用双三次均匀B样条；Doo-Sabin细分方法类似于雕塑 过程，即不断地切削网格的棱边和角，使之趋向光滑，但是在奇异点处，光滑效果不够；Loop 细分方法基于三角网格，采用1-4三角形分裂，取得了不错的效果。
[0005] 插值细分也有不少经典算法：蝶形细分方法采用1-4三角网格分裂，由于其面具 与蝴蝶相似而得名，但得到的极限曲面光顺不太好；4-8细分方法，虽然面片增长速度慢了 下来，但是操作过于复杂，还需要先用Catmull-Clark方法把网格处理为四边形，然后把每 个四边形变为三角形。
[0006] 还有借助拉普拉斯坐标来修正顶点位置的细分方法，但是它是在求解的过程中先 求出拉普拉斯坐标，然后用于求顶点平移增量来调整。Weimer和Warren在1998年研究过 细分方法与变分问题的关系，但他们也是通过线性组合的角度用矩阵来求解新的顶点。
[0007] 上面提到的细分方法大都是线性且静态的，就是说，对网格上任一细分层次使用 的规则都不变，而且新顶点简单地由旧顶点的线性组合得到，需要多步骤地求解才能得到 结果。细分曲面没有解析形式，曲面的连续性和光滑性分析无论从理论还是应用角度来说 都显得很重要，当然相对来说也比较复杂。
[0008] 本发明提出一种通过求解线性方程，一次性求出所有的新顶点的方法，从而避免 分步骤进行细分，并且能够让拓扑结构更加自由。它把新顶点位置的拉普拉斯坐标设成向 量0。在极限情况下，在新顶点位置是极小曲面。由于调和函数总是无穷次可导（光滑） 的，所以所得极限曲面是光滑的。
【发明内容】
[0009] 本发明的方法是基于低精细度的网格模型和给定的精细度提高需求，使用拉普拉 斯坐标，通过线性系统求解出高精细度的网格模型。
[0010] 为达到上述的目的，本发明采用的技术方案是：一种基于拉普拉斯坐标的网格细 分方法。该方法包括以下几个步骤：
[0011] (1)输入低精细度的三维网格模型Ml;
[0012] ⑵用户确定Ml的各个顶点在细分过程中的插值程度，其中可以按区域来指定；
[0013] (3)用户确定新网格的拓扑结构，可以使用其它插值细分方法获取拓扑结构的方 法来得到，但该步骤不必求出各个新顶点的坐标；
[0014] (4)根据新网格的拓扑结构，构造新网格的拉普拉斯矩阵L;
[0015] (5)根据L和用户给定的插值程度，构造扩展后的拉普拉斯矩阵A，以及新网格的 期望拉普拉斯坐标b，其中跟新顶点对应的拉普拉斯坐标设成0 ;
[0016] (6)求解线性系统AV' =b，得到V' ；
[0017] (7)由得到的V'以及拓扑结构，构成新的高精细度的网格模型M2。
【附图说明】
[0018] 图1为本发明方法的流程示意图；
[0019] 图2为本发明方法对一个四面体网格处理的效果图；
[0020] 图3为本发明方法对一个兔子网格处理的效果图。
【具体实施方式】
[0021] 下面结合附图对本发明做进一步的说明。
[0022] 首先，输入低精细度的三维网格模型，设为Ml。其中包括顶点集合V= {v0，vl，…， vi，…}、边集合E= {e0，el，…，ej,…}，还有面集合F= {f0，fl、…，fk，…}。不妨 设顶点数为N。
[0023] 为了确定V中各个顶点的被插值或逼近的程度，需要给每个顶点vi确定一个逼近 值cvi。该值可以是任意正数。当该值越大，表示新网格中对应的顶点越逼近原顶点，也就 是越接近插值。当该值无穷大时，就是插值原顶点。当该值越小，表示该点越自由，越是由 光滑因素来决定其位置。
[0024] 用户可以通过以下几种方式给定插值程度值；
[0025] (1)为所有顶点逐个指定一个值；
[0026] (2)为所有边逐条指定一个值，每条边所被赋予的值就相当于赋予它的两个顶点。 这样，每个顶点将获得多个值。再通过线性求值方式获得每个顶点的插值程度值。比如：取 最大值、取最小值、取平均值等；
[0027] (3)为所有面逐个指定一个值，每个面所被赋予的值就相当于赋予它的三个顶点。 这样，每个顶点将获得多个值。再通过线性求值方式获得每个顶点的插值程度值。比如：取 最大值、取最小值、取平均值等；
[0028] (4)前面儿种方式的组合来指定所有顶点的插值程度值。
[0029] 新的高精细度网格模型跟原来低精细度的网格模型相比，肯定增加顶点，也就导 致其拓扑结构肯定与原来的不同。不妨设新的顶点数为T。本发明对于新拓扑结构只要求 它包含原网格的顶点，不再限定其它形式。这样，用户可以给出更加自由的拓扑结构。
[0030] 用户可以通过类似其它细分方法的获取拓扑结构的方式，获取新拓扑结构。当然， 这里只是获取拓扑结构，也就是顶点的连接关系，而不必计算顶点位置。计算量将只是其它 细分方法的计算过程的一小部分而已。用户还可以手动或使用其它工具，给出一些符合特 定要求的拓扑结构，使原网格的某些区域被细分得比较粗，而某些区域则被细分得比较细。
[0031] 假设新的拓扑结构以TXT连接矩阵P的方式给出。P的每个元素pij具体取值如 下：
[0033] 构造TXT矩阵D来记录每个顶点的度数，其中每个元素dij具体取值如下：
[0035] 其中di为vi的度，即ESpis。
[0036] 使用P和D，构造TXT拉普拉斯矩阵L=D-P。其中L的每个元素lij具体取值 如下：
[0038] 由于在L中，每一行记录了新拓扑结构中一个顶点的情况，而新网格中包含了N个 顶点跟原网格对应。不妨设，和原网格顶点对应的N个顶点排在L中的前N行。构造扩展 后的（T+N)XT拉普拉斯矩阵A如下：
[0039] ;
[0040] 其中C是一个NXN对角矩阵。C的每一行对应原网格的一个顶点。第i行主对角 线上的元素就是用户为Vi设定的插值程度值cvi。
[0041] 接下来，构造期望拉普拉斯坐标值（T+N)X3矩阵b如下：
[0042] ;
[0043] 其中V为NX3矩阵，每一行分别是原网格的一个顶点的x、y、z坐标。即V的第i 行是vi的坐标。
[0044] 使用A和b，构造一个线性系统：AV' =b。其中V'是新网格的顶点坐标类似V构 成的矩阵。由于拉普拉斯矩阵L的秩是T-1，再加上C的扩展，就能够使得A的秩为T，所以 该线性系统有唯一解。通过求解该线性系统，就可以得到V'。它是新网格的顶点集，总共有 T个顶点。
[0045] 最后，V'结合新网格的拓扑结构，构成高精细度的网格模型。
[0046] 使用本发明方法，对一个四面体网格进行细分得到实验效果如图2。其中（a)为初 始网格，（b)和（c)分别是从两个不同视角观察处理后的网格的效果。对兔子网格进行细 分得到实验效果如图2。其中（a)为初始网格，（b)、（c)和（d)分别是从三个不同视角观察 处理后的网格的效果。
【主权项】
1. 一种基于拉普拉斯坐标的网格细分方法，其特征在于，该方法包含以下步骤： (1) 输入三角网格模型； (2) 利用基于拉普拉斯坐标的网格细分方法编辑模型： (3) 生成目标网格模型。2. 根据权利要求1所述的，利用基于拉普拉斯坐标的网格细分方法编辑模型，可用以 下步骤来实现： (1) 根据原网格，以及细分要求，构造目标网格的拓扑结构； (2) 基于拓扑结构，构造目标网格的拉普拉斯矩阵A; (3) 根据细分要求，构造目标网格的拉普拉斯坐标b; (4) 求解线性系统AV' =b，得到目标网格模型的顶点坐标V'。3. 权利要求2所述中的细分要求，包括： (1) 原网格上的各个三角面片的细分粒度，可以按区域的方式给定； (2) 原网格上的各个顶点的逼近程度。
【专利摘要】一种基于拉普拉斯坐标的网格细分方法，本发明涉及三维网格模型的建模和细分技术，具体地说是涉及到保持三维网格模型指定特点的精细度提高技术。随着计算机硬件的不断发展，为了实现高真实感，许多计算机图形应用都使用复杂的，具有高精度细节信息的模型。但是高精细度的网格模型的构造还不能满足需要。本发明就是为了促进这方面工作而提出的。本发明基于低精细皮的网格模型，由用户确定顶点的插值程度以及新网格的拓扑结构，然后构造扩展的拉普拉斯矩阵以及对应的期望拉普拉斯坐标，形成线性系统，从而求解新网格的顶点位置。最后，结合拓扑结构，构成新的高精细度网格模型。具体实现流程如附图。
【IPC分类】G06T17/30
【公开号】CN104899929
【申请号】CN201410075900
【发明人】邓正杰, 石春, 何书前
【申请人】海南师范大学
【公开日】2015年9月9日
【申请日】2014年3月4日
【技术领域】
[0001] 本发明涉及三维网格模型的建模和细分技术，具体地说是涉及到保持三维网格模 型指定特点的精细度提高技术。
【背景技术】
[0002] 目前，在计算机图形学中，随着计算机硬件的不断发展，图形处理能力越来越强， 为了实现高真实感，许多计算机图形应用都使用复杂的，具有高精度细节信息的模型。因此 常用模型的构造常常需要高精度的。虽然，有三维扫描之类的技术来一次性获得高密度的 顶点，但是，仅仅依靠扫描还满足不了人们对三维模型的日益增长的需求。那么，人们需要 根据自己的想法使用各种工具设计出模型。直接逐个确定高精度模型的顶点，是比较冗余 繁琐的工作。通常人们是先构造出一个基本符合要求的低精细度的网格模型，然后再使用 工具在保持指定特点的同时，提高网格模型的精细度。另一方面，三维扫描所得的模型，由 于设备的级别不同，有些时候也还是精细度不够。因此，人们迫切需要一些可以提高网格模 型精细度的技术。网格细分就是其中一类重要的技术。
[0003] 细分技术，能够从一个任意的拓扑网格结构构造出一个极限连续的曲面，是20世 纪70年代提出的一种曲线曲面造型技术。根据细分后的极限曲面是否插值初始的控制网 格，分为逼近细分和插值细分。
[0004] 逼近细分已有不少经典算法：Catmull-Clark细分方法基于四边形网格，采用1-4 四边形分裂算子生成新网格，其中使用双三次均匀B样条；Doo-Sabin细分方法类似于雕塑 过程，即不断地切削网格的棱边和角，使之趋向光滑，但是在奇异点处，光滑效果不够；Loop 细分方法基于三角网格，采用1-4三角形分裂，取得了不错的效果。
[0005] 插值细分也有不少经典算法：蝶形细分方法采用1-4三角网格分裂，由于其面具 与蝴蝶相似而得名，但得到的极限曲面光顺不太好；4-8细分方法，虽然面片增长速度慢了 下来，但是操作过于复杂，还需要先用Catmull-Clark方法把网格处理为四边形，然后把每 个四边形变为三角形。
[0006] 还有借助拉普拉斯坐标来修正顶点位置的细分方法，但是它是在求解的过程中先 求出拉普拉斯坐标，然后用于求顶点平移增量来调整。Weimer和Warren在1998年研究过 细分方法与变分问题的关系，但他们也是通过线性组合的角度用矩阵来求解新的顶点。
[0007] 上面提到的细分方法大都是线性且静态的，就是说，对网格上任一细分层次使用 的规则都不变，而且新顶点简单地由旧顶点的线性组合得到，需要多步骤地求解才能得到 结果。细分曲面没有解析形式，曲面的连续性和光滑性分析无论从理论还是应用角度来说 都显得很重要，当然相对来说也比较复杂。
[0008] 本发明提出一种通过求解线性方程，一次性求出所有的新顶点的方法，从而避免 分步骤进行细分，并且能够让拓扑结构更加自由。它把新顶点位置的拉普拉斯坐标设成向 量0。在极限情况下，在新顶点位置是极小曲面。由于调和函数总是无穷次可导（光滑） 的，所以所得极限曲面是光滑的。
【发明内容】
[0009] 本发明的方法是基于低精细度的网格模型和给定的精细度提高需求，使用拉普拉 斯坐标，通过线性系统求解出高精细度的网格模型。
[0010] 为达到上述的目的，本发明采用的技术方案是：一种基于拉普拉斯坐标的网格细 分方法。该方法包括以下几个步骤：
[0011] (1)输入低精细度的三维网格模型Ml;
[0012] ⑵用户确定Ml的各个顶点在细分过程中的插值程度，其中可以按区域来指定；
[0013] (3)用户确定新网格的拓扑结构，可以使用其它插值细分方法获取拓扑结构的方 法来得到，但该步骤不必求出各个新顶点的坐标；
[0014] (4)根据新网格的拓扑结构，构造新网格的拉普拉斯矩阵L;
[0015] (5)根据L和用户给定的插值程度，构造扩展后的拉普拉斯矩阵A，以及新网格的 期望拉普拉斯坐标b，其中跟新顶点对应的拉普拉斯坐标设成0 ;
[0016] (6)求解线性系统AV' =b，得到V' ；
[0017] (7)由得到的V'以及拓扑结构，构成新的高精细度的网格模型M2。
【附图说明】
[0018] 图1为本发明方法的流程示意图；
[0019] 图2为本发明方法对一个四面体网格处理的效果图；
[0020] 图3为本发明方法对一个兔子网格处理的效果图。
【具体实施方式】
[0021] 下面结合附图对本发明做进一步的说明。
[0022] 首先，输入低精细度的三维网格模型，设为Ml。其中包括顶点集合V= {v0，vl，…， vi，…}、边集合E= {e0，el，…，ej,…}，还有面集合F= {f0，fl、…，fk，…}。不妨 设顶点数为N。
[0023] 为了确定V中各个顶点的被插值或逼近的程度，需要给每个顶点vi确定一个逼近 值cvi。该值可以是任意正数。当该值越大，表示新网格中对应的顶点越逼近原顶点，也就 是越接近插值。当该值无穷大时，就是插值原顶点。当该值越小，表示该点越自由，越是由 光滑因素来决定其位置。
[0024] 用户可以通过以下几种方式给定插值程度值；
[0025] (1)为所有顶点逐个指定一个值；
[0026] (2)为所有边逐条指定一个值，每条边所被赋予的值就相当于赋予它的两个顶点。 这样，每个顶点将获得多个值。再通过线性求值方式获得每个顶点的插值程度值。比如：取 最大值、取最小值、取平均值等；
[0027] (3)为所有面逐个指定一个值，每个面所被赋予的值就相当于赋予它的三个顶点。 这样，每个顶点将获得多个值。再通过线性求值方式获得每个顶点的插值程度值。比如：取 最大值、取最小值、取平均值等；
[0028] (4)前面儿种方式的组合来指定所有顶点的插值程度值。
[0029] 新的高精细度网格模型跟原来低精细度的网格模型相比，肯定增加顶点，也就导 致其拓扑结构肯定与原来的不同。不妨设新的顶点数为T。本发明对于新拓扑结构只要求 它包含原网格的顶点，不再限定其它形式。这样，用户可以给出更加自由的拓扑结构。
[0030] 用户可以通过类似其它细分方法的获取拓扑结构的方式，获取新拓扑结构。当然， 这里只是获取拓扑结构，也就是顶点的连接关系，而不必计算顶点位置。计算量将只是其它 细分方法的计算过程的一小部分而已。用户还可以手动或使用其它工具，给出一些符合特 定要求的拓扑结构，使原网格的某些区域被细分得比较粗，而某些区域则被细分得比较细。
[0031] 假设新的拓扑结构以TXT连接矩阵P的方式给出。P的每个元素pij具体取值如 下：
[0033] 构造TXT矩阵D来记录每个顶点的度数，其中每个元素dij具体取值如下：
[0035] 其中di为vi的度，即ESpis。
[0036] 使用P和D，构造TXT拉普拉斯矩阵L=D-P。其中L的每个元素lij具体取值 如下：
[0038] 由于在L中，每一行记录了新拓扑结构中一个顶点的情况，而新网格中包含了N个 顶点跟原网格对应。不妨设，和原网格顶点对应的N个顶点排在L中的前N行。构造扩展 后的（T+N)XT拉普拉斯矩阵A如下：
[0039] ;
[0040] 其中C是一个NXN对角矩阵。C的每一行对应原网格的一个顶点。第i行主对角 线上的元素就是用户为Vi设定的插值程度值cvi。
[0041] 接下来，构造期望拉普拉斯坐标值（T+N)X3矩阵b如下：
[0042] ;
[0043] 其中V为NX3矩阵，每一行分别是原网格的一个顶点的x、y、z坐标。即V的第i 行是vi的坐标。
[0044] 使用A和b，构造一个线性系统：AV' =b。其中V'是新网格的顶点坐标类似V构 成的矩阵。由于拉普拉斯矩阵L的秩是T-1，再加上C的扩展，就能够使得A的秩为T，所以 该线性系统有唯一解。通过求解该线性系统，就可以得到V'。它是新网格的顶点集，总共有 T个顶点。
[0045] 最后，V'结合新网格的拓扑结构，构成高精细度的网格模型。
[0046] 使用本发明方法，对一个四面体网格进行细分得到实验效果如图2。其中（a)为初 始网格，（b)和（c)分别是从两个不同视角观察处理后的网格的效果。对兔子网格进行细 分得到实验效果如图2。其中（a)为初始网格，（b)、（c)和（d)分别是从三个不同视角观察 处理后的网格的效果。
【主权项】
1. 一种基于拉普拉斯坐标的网格细分方法，其特征在于，该方法包含以下步骤： (1) 输入三角网格模型； (2) 利用基于拉普拉斯坐标的网格细分方法编辑模型： (3) 生成目标网格模型。2. 根据权利要求1所述的，利用基于拉普拉斯坐标的网格细分方法编辑模型，可用以 下步骤来实现： (1) 根据原网格，以及细分要求，构造目标网格的拓扑结构； (2) 基于拓扑结构，构造目标网格的拉普拉斯矩阵A; (3) 根据细分要求，构造目标网格的拉普拉斯坐标b; (4) 求解线性系统AV' =b，得到目标网格模型的顶点坐标V'。3. 权利要求2所述中的细分要求，包括： (1) 原网格上的各个三角面片的细分粒度，可以按区域的方式给定； (2) 原网格上的各个顶点的逼近程度。
【专利摘要】一种基于拉普拉斯坐标的网格细分方法，本发明涉及三维网格模型的建模和细分技术，具体地说是涉及到保持三维网格模型指定特点的精细度提高技术。随着计算机硬件的不断发展，为了实现高真实感，许多计算机图形应用都使用复杂的，具有高精度细节信息的模型。但是高精细度的网格模型的构造还不能满足需要。本发明就是为了促进这方面工作而提出的。本发明基于低精细皮的网格模型，由用户确定顶点的插值程度以及新网格的拓扑结构，然后构造扩展的拉普拉斯矩阵以及对应的期望拉普拉斯坐标，形成线性系统，从而求解新网格的顶点位置。最后，结合拓扑结构，构成新的高精细度网格模型。具体实现流程如附图。
【IPC分类】G06T17/30
【公开号】CN104899929
【申请号】CN201410075900
【发明人】邓正杰, 石春, 何书前
【申请人】海南师范大学
【公开日】2015年9月9日
【申请日】2014年3月4日
最新回复(0)