三维网格模型的处理技术研究进展-唐杰2005

1、wStructured or UnstructuredwRegular or IrregularwManifold or Nonmanifoldvvv（a）（b）（c）vvv（a）（b）（c）wSIGGRAPH连续三年，每年3个有关mesh的sessionwEUROGRAPHwPACIFIC GRAPHwvertices(-1, -1, -1) (-1, -1, 1) (-1, 1, -1) (-1, 1, 1) (1, -1, -1) (1, -1, 1) (1, 1, -1) (1, 1, 1) wFaces: 1 2 4 5 7 8 1

2、 5 6 3 4 8 ：struct SM_face SM_vert* vert3; struct SM_edge SM_vert* vert2;SM_face* face2;struct SM_vert float coord3;SM_face* nbFace;SM_edge* nbEdge;struct SM_mesh SM_vert* vert;SM_face* face;SM_edge* edge;例如Garland的qslim等void GetVertexStar(CVertex* pVertex, CVertex* arrPVertex) CTriangle* arrTriangl

3、e = pVertex-GetNeighborTriangles(); for(int i=0; iarrTriangle.GetSize(); i+) for(int j=0; jGetVertex(j)-SetMark(0); pVertex-SetMark(1); for(i=0; iarrTriangle.GetSize(); i+) for(int j=0; jGetVertex(j)-GetMark() arrPVertex.Add(arrTrianglei-GetVertex(j); arrTrianglei-GetVertex(j)-SetMark(byte)1); struc

4、t we struct we* l_next; struct we* l_prev; struct we* r_next; struct we* r_prev; struct vert* st_vert; struct vert* end_vert; struct face* l_f; struct face* r_f; struct vert struct we* rep; float coord3; struct face struct we* rep; struct HE_edge HE_vert* vert; HE_edge* pair; HE_face* face; HE_edge*

5、 next; ; struct HE_vert float x; float y; float z; HE_edge* edge; ; struct HE_face HE_edge* edge; ; w边edge的端点和邻接三角片查询：HE_vert* vert1 = edge-vert; HE_vert* vert2 = edge-pair-vert; HE_face* face1 = edge-face; HE_face* face2 = edge-pair-face; w三角片face的三条边：HE_edge* edge = face-edge;do edge = edge-next;

6、while (edge != face-edge); w点vert的邻接边：HE_edge* edge = vert-edge;do edge = edge-pair-next; while (edge != vert-edge); w：2221FEGMLNKw )(222221FEGNEMFLGHw w niiniiAk00312)(1)(cot(cot41iNjijjjvvAHn其中：i为三角片在该顶点处内角的度数； Ai为三角片的面积； n为网格模型中包含该顶点的三角片的个数 减1。w 其中：n为该点法矢， A为三角片面积和， N1(i)为点vi的一阶邻接点集， j和j分别是边vivj所

7、对应的角。 2|)(2)(pqpqNTtp)(1iNjtijijijijiTTwM12221133ppw QQ 拟合点的要求：拟合点的要求： 能反映网格模型在该点处的实际形状能反映网格模型在该点处的实际形状 不能跨越网格模型上的不能跨越网格模型上的C1不连续界限不连续界限 不能小于不能小于9个个拟合点的参数化拟合点的参数化 投影到切平面投影到切平面 旋转到旋转到XOYXOY平面平面 包围盒调整包围盒调整 比例变换比例变换v 曲面拟合：曲面拟合：曲率计算曲率计算RMMMDTT1)(其中：其中：R为顶点向量，为顶点向量，n维；维；M为为n9的矩阵，与的矩阵，与B样条基函数值有关样条基函数值有关22

8、21FEGMLNK)(222221FEGNEMFLGH其中：其中：E，G，F，是曲面的第一类基本量；，是曲面的第一类基本量； L，M，N是曲面第二类基本量。是曲面第二类基本量。 vivjvjvivjvj1vj2vs2122jsYsXdvv22222)(jsYXisXdvvvvivi1vi2vsvivi1vi2vsvivi1vi2vs 1.4140 ),(min),(yxdMxdMyE网格模型的几何相似性网格模型的几何相似性 ),(max) ,(MxdMMdEMxs), (),(max() ,(MMdMMdMMdssH空间一点x到网格模型M的距离dE定义为： 网格M 到M的单向Hausdorff

9、距离ds定义为：网格M0到M 的对称Hausdorff距离dH定义为: 网格模型的外观相似性评估网格模型的外观相似性评估 njjjIInMM021其中：Ij为M上第j个采样点处的RGB向量；Ij为M上距离采样点j最近的点处的RGB向量；| Ij Ij|为向量Ij与Ij之间的欧氏距离，n为采样点的个数。v1v0v21222333平均单元格法平均单元格法首先确定首先确定M和和M的外接包围盒的范围；的外接包围盒的范围；长方体包围盒划分成长方体包围盒划分成l lm mn n个小立方体栅格个小立方体栅格若某三角片与一个单元格相交，则将该三角片若某三角片与一个单元格相交，则将该三角片分配给该单元格分配给该

10、单元格 单元格的大小：单元格的大小：单元格的大小决定了每个单元单元格的大小决定了每个单元 格中三角片的数量。格中三角片的数量。 d1d2T1T2v0.01438901.0 0 1.732 0 Points cloudMeshjjNPjiPnO1TijijOPOPA)(w细分法w网格简化拆分合并vivj v拆分点删除边初始初始向下向下采样采样修改修改操作操作vivj vvivj 1 2 3 4 5 6 7 8 vvivj 1 2 3 4 5 6 7 8 vvivj 1 1 vvivj 1 2 3 4 5 6 7 8vivj v 2 2 vvivj 1 2 3 4 5 6 7 8 vvi vvj

11、3 3 vvivj 1 2 3 4 5 6 7 8 vvivj 4 4 vvivj 1 2 3 4 5 6 7 8 vvivj 5 5 vvivj 1 2 3 4 5 6 7 8 vvivj vvivj 6 6 vvivj 1 2 3 4 5 6 7 8 vvivj vvivj 7 7 vvivj 1 2 3 4 5 6 7 8 vvivj vvivj 8 8 vvivj 1 2 3 4 5 6 7 8 vvivj vvivj 8 8 vvivj 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 v v0 v1 v2)(61)(610dvnvvnVTiTii)()(22dvn

12、dnvdvnVTiiTTiiiTiiTcvbvAv2)2()(2iTiiTicvbvAvVvfiTiiTcvbvAv2cvbAvvTT2bAv1 vivjvivj),(maxTvDErrortVvsvivjv23222134lll 80000 40000 20000 10000 5000 250011 9111011101110 1112345678 91012 12345678 9 1234678 9 123468 9 123468 123468 9M1M2M3M4M5 M5 M3 M2 M1 M4增大网格模型分辨率时：增大网格模型分辨率时：m5m4m3m2m1 减小网格模型分辨率时：减小网

13、格模型分辨率时：m1m2m3m4m5 SdSsE2221)(kkVKIV)(1kkVKIKIV)(1)(11iNjkjikipwvkqpqpkVLILILIV)()()(1 ,)1 (242KbaaHFTP SqiiqiqqSqiiqiqiqqivvgvcfavvgvcfvav|)(|)(|)(|)(|)(其中：q为一个三角片，S为点vi周围三角片集。aq为三角片q的面积。q(vi)为点vi在q所在平面上的投影。cq为三角片q的质心。f为空间权函数，g为影响权函数，都采用Gaussian函数。)()()(|)(|)(|)(|)(ijijvNvjisjicvNvjisjicjiivvnWvvWv

14、vnWvvWvvndnivitvi+2vi+1vi-1vi-2 nivitvi+2vi+1vi-1vi-2ni2ni1ni1ni2 n1n2vi图3.18 确定截断距离的大小)()()*1 ()(|)(|)*1 ()(|)(|)(ijijvNvjinjijsjicvNvjinjijsjicjijinnWvvnWvvWnnWvvnWvvWvvnd光顺种类光顺参数Laplacian 循环次数n：20；Improved Laplacian循环次数n：20；：0；：0.5；Taubin循环次数n：20；：0.6307；：-0.6732；Jones循环次数n：1；f/|e|：2；g/|e|：1；Flei

15、shman循环次数n：1；c/|e|：2；s/|e|：1；Ours循环次数n：1；c/|e|：2；s/|e|：1；f/|e|：0.3；（a）（b）（c）（d）（e）（g）（f）（h）w定义：在不影响使用的情况下定义：在不影响使用的情况下, ,在载体作品中不可感知地在载体作品中不可感知地嵌入一些特殊信息。嵌入一些特殊信息。w目的：版权保护目的：版权保护w要求：要求：抵御各种攻击抵御各种攻击仿射变换仿射变换RemeshingRemeshingReindexingReindexing简化简化光顺光顺加噪声加噪声不影响模型正常使用不影响模型正常使用w 加载空间加载空间 网格模型会受到许多严厉的攻击，例

16、如裁剪、简化等网格模型会受到许多严厉的攻击，例如裁剪、简化等，如果将水印直接加在网格模型的某个固定分辨率上，如果将水印直接加在网格模型的某个固定分辨率上，当网格模型遇简化攻击时，易造成水印丢失。当网格模型遇简化攻击时，易造成水印丢失。w 误差控制误差控制 当模型面向工程应用时，加载水印引起的误差应控制当模型面向工程应用时，加载水印引起的误差应控制在用户制定范围内。在用户制定范围内。w 有意义有意义 水印信息应有意义水印信息应有意义原始网格M0构建多分辨模型，并将模型降到最低分辨率计算由于水印导致的L误差水印字串str调整模型分辨率私钥加密转换为比特流w在当前分辨率上嵌入水印wi水印网格Mw水印

17、比对文件 水印长度水印长度 字串长度字串长度s 比特流长度比特流长度8s冗余比特流长冗余比特流长度度8sr 加载点的分布加载点的分布 表示同一个比特信息的表示同一个比特信息的r个顶点分布应尽量均匀以抵个顶点分布应尽量均匀以抵抗裁剪、简化等操作的攻击，抗裁剪、简化等操作的攻击，通过多分辨模型实现。通过多分辨模型实现。 误差控制误差控制 计算该顶点的一阶邻接三角片上的采样点到初始网计算该顶点的一阶邻接三角片上的采样点到初始网格模型的距离。放弃或调低水印强度。格模型的距离。放弃或调低水印强度。iijiinlwfvv)( 原始网格M0根据多数原则判决该比特信息wi水印网格Mw水印字串w 水印比对文件网

18、格对准 重新网格化提取每个嵌入水印的比特信息wik计算相关度 其中：其中：wik为第为第i个比特中第个比特中第k个顶点所表示的信息；个顶点所表示的信息；vj和和vj分别为加载分别为加载wik的初始网格模型顶点和水印网的初始网格模型顶点和水印网 格顶点；格顶点；nj为对应的初始网格该顶点法矢为对应的初始网格该顶点法矢。 提取提取wik0)(00)(1jjjjjjiknvvnvvw 确定确定wi 相关度计算相关度计算w基于模型图w基于骨架图w基于Reeb图w3D model retrieval system, http:/3.tw/dynamic/.w3D model search engine, .w3D model similarity search e