三維網(wǎng)格模型的處理技術(shù)研究進(jìn)展-唐杰2005

1、wStructured or UnstructuredwRegular or IrregularwManifold or Nonmanifoldvvv（a）（b）（c）vvv（a）（b）（c）wSIGGRAPH連續(xù)三年，每年3個(gè)有關(guān)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的端點(diǎn)和鄰接三角片查詢：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點(diǎn)vert的鄰接邊：HE_edge* edge = vert-edge;do edge = edge-pair-next; while (edge != vert-edge); w：2221FEGMLNKw )(222221FEGNEMFLGHw w niiniiAk00312)(1)(cot(cot41iNjijjjvvAHn其中：i為三角片在該頂點(diǎn)處內(nèi)角的度數(shù)； Ai為三角片的面積； n為網(wǎng)格模型中包含該頂點(diǎn)的三角片的個(gè)數(shù) 減1。w 其中：n為該點(diǎn)法矢， A為三角片面積和， N1(i)為點(diǎn)vi的一階鄰接點(diǎn)集， j和j分別是邊vivj所

7、對應(yīng)的角。 2|)(2)(pqpqNTtp)(1iNjtijijijijiTTwM12221133ppw QQ 擬合點(diǎn)的要求：擬合點(diǎn)的要求： 能反映網(wǎng)格模型在該點(diǎn)處的實(shí)際形狀能反映網(wǎng)格模型在該點(diǎn)處的實(shí)際形狀 不能跨越網(wǎng)格模型上的不能跨越網(wǎng)格模型上的C1不連續(xù)界限不連續(xù)界限 不能小于不能小于9個(gè)個(gè)擬合點(diǎn)的參數(shù)化擬合點(diǎn)的參數(shù)化 投影到切平面投影到切平面 旋轉(zhuǎn)到旋轉(zhuǎn)到XOYXOY平面平面 包圍盒調(diào)整包圍盒調(diào)整 比例變換比例變換v 曲面擬合：曲面擬合：曲率計(jì)算曲率計(jì)算RMMMDTT1)(其中：其中：R為頂點(diǎn)向量，為頂點(diǎn)向量，n維；維；M為為n9的矩陣，與的矩陣，與B樣條基函數(shù)值有關(guān)樣條基函數(shù)值有關(guān)22

8、21FEGMLNK)(222221FEGNEMFLGH其中：其中：E，G，F(xiàn)，是曲面的第一類基本量；，是曲面的第一類基本量； L，M，N是曲面第二類基本量。是曲面第二類基本量。 vivjvjvivjvj1vj2vs2122jsYsXdvv22222)(jsYXisXdvvvvivi1vi2vsvivi1vi2vsvivi1vi2vs 1.4140 ),(min),(yxdMxdMyE網(wǎng)格模型的幾何相似性網(wǎng)格模型的幾何相似性 ),(max) ,(MxdMMdEMxs), (),(max() ,(MMdMMdMMdssH空間一點(diǎn)x到網(wǎng)格模型M的距離dE定義為： 網(wǎng)格M 到M的單向Hausdorff

9、距離ds定義為：網(wǎng)格M0到M 的對稱Hausdorff距離dH定義為: 網(wǎng)格模型的外觀相似性評估網(wǎng)格模型的外觀相似性評估 njjjIInMM021其中：Ij為M上第j個(gè)采樣點(diǎn)處的RGB向量；Ij為M上距離采樣點(diǎn)j最近的點(diǎn)處的RGB向量；| Ij Ij|為向量Ij與Ij之間的歐氏距離，n為采樣點(diǎn)的個(gè)數(shù)。v1v0v21222333平均單元格法平均單元格法首先確定首先確定M和和M的外接包圍盒的范圍；的外接包圍盒的范圍；長方體包圍盒劃分成長方體包圍盒劃分成l lm mn n個(gè)小立方體柵格個(gè)小立方體柵格若某三角片與一個(gè)單元格相交，則將該三角片若某三角片與一個(gè)單元格相交，則將該三角片分配給該單元格分配給該

10、單元格 單元格的大?。簡卧竦拇笮。簡卧竦拇笮Q定了每個(gè)單元單元格的大小決定了每個(gè)單元 格中三角片的數(shù)量。格中三角片的數(shù)量。 d1d2T1T2v0.01438901.0 0 1.732 0 Points cloudMeshjjNPjiPnO1TijijOPOPA)(w細(xì)分法w網(wǎng)格簡化拆分合并vivj v拆分點(diǎn)刪除邊初始初始向下向下采樣采樣修改修改操作操作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增大網(wǎng)格模型分辨率時(shí)：增大網(wǎng)格模型分辨率時(shí)：m5m4m3m2m1 減小網(wǎng)格模型分辨率時(shí)：減小網(wǎng)

13、格模型分辨率時(shí)：m1m2m3m4m5 SdSsE2221)(kkVKIV)(1kkVKIKIV)(1)(11iNjkjikipwvkqpqpkVLILILIV)()()(1 ,)1 (242KbaaHFTP SqiiqiqqSqiiqiqiqqivvgvcfavvgvcfvav|)(|)(|)(|)(|)(其中：q為一個(gè)三角片，S為點(diǎn)vi周圍三角片集。aq為三角片q的面積。q(vi)為點(diǎn)vi在q所在平面上的投影。cq為三角片q的質(zhì)心。f為空間權(quán)函數(shù)，g為影響權(quán)函數(shù)，都采用Gaussian函數(shù)。)()()(|)(|)(|)(|)(ijijvNvjisjicvNvjisjicjiivvnWvvWv

14、vnWvvWvvndnivitvi+2vi+1vi-1vi-2 nivitvi+2vi+1vi-1vi-2ni2ni1ni1ni2 n1n2vi圖3.18 確定截?cái)嗑嚯x的大小)()()*1 ()(|)(|)*1 ()(|)(|)(ijijvNvjinjijsjicvNvjinjijsjicjijinnWvvnWvvWnnWvvnWvvWvvnd光順種類光順參數(shù)Laplacian 循環(huán)次數(shù)n：20；Improved Laplacian循環(huán)次數(shù)n：20；：0；：0.5；Taubin循環(huán)次數(shù)n：20；：0.6307；：-0.6732；Jones循環(huán)次數(shù)n：1；f/|e|：2；g/|e|：1；Flei

15、shman循環(huán)次數(shù)n：1；c/|e|：2；s/|e|：1；Ours循環(huán)次數(shù)n：1；c/|e|：2；s/|e|：1；f/|e|：0.3；（a）（b）（c）（d）（e）（g）（f）（h）w定義：在不影響使用的情況下定義：在不影響使用的情況下, ,在載體作品中不可感知地在載體作品中不可感知地嵌入一些特殊信息。嵌入一些特殊信息。w目的：版權(quán)保護(hù)目的：版權(quán)保護(hù)w要求：要求：抵御各種攻擊抵御各種攻擊仿射變換仿射變換RemeshingRemeshingReindexingReindexing簡化簡化光順光順加噪聲加噪聲不影響模型正常使用不影響模型正常使用w 加載空間加載空間 網(wǎng)格模型會(huì)受到許多嚴(yán)厲的攻擊，例

16、如裁剪、簡化等網(wǎng)格模型會(huì)受到許多嚴(yán)厲的攻擊，例如裁剪、簡化等，如果將水印直接加在網(wǎng)格模型的某個(gè)固定分辨率上，如果將水印直接加在網(wǎng)格模型的某個(gè)固定分辨率上，當(dāng)網(wǎng)格模型遇簡化攻擊時(shí)，易造成水印丟失。當(dāng)網(wǎng)格模型遇簡化攻擊時(shí)，易造成水印丟失。w 誤差控制誤差控制 當(dāng)模型面向工程應(yīng)用時(shí)，加載水印引起的誤差應(yīng)控制當(dāng)模型面向工程應(yīng)用時(shí)，加載水印引起的誤差應(yīng)控制在用戶制定范圍內(nèi)。在用戶制定范圍內(nèi)。w 有意義有意義 水印信息應(yīng)有意義水印信息應(yīng)有意義原始網(wǎng)格M0構(gòu)建多分辨模型，并將模型降到最低分辨率計(jì)算由于水印導(dǎo)致的L誤差水印字串str調(diào)整模型分辨率私鑰加密轉(zhuǎn)換為比特流w在當(dāng)前分辨率上嵌入水印wi水印網(wǎng)格Mw水印

17、比對文件 水印長度水印長度 字串長度字串長度s 比特流長度比特流長度8s冗余比特流長冗余比特流長度度8sr 加載點(diǎn)的分布加載點(diǎn)的分布 表示同一個(gè)比特信息的表示同一個(gè)比特信息的r個(gè)頂點(diǎn)分布應(yīng)盡量均勻以抵個(gè)頂點(diǎn)分布應(yīng)盡量均勻以抵抗裁剪、簡化等操作的攻擊，抗裁剪、簡化等操作的攻擊，通過多分辨模型實(shí)現(xiàn)。通過多分辨模型實(shí)現(xiàn)。 誤差控制誤差控制 計(jì)算該頂點(diǎn)的一階鄰接三角片上的采樣點(diǎn)到初始網(wǎng)計(jì)算該頂點(diǎn)的一階鄰接三角片上的采樣點(diǎn)到初始網(wǎng)格模型的距離。放棄或調(diào)低水印強(qiáng)度。格模型的距離。放棄或調(diào)低水印強(qiáng)度。iijiinlwfvv)( 原始網(wǎng)格M0根據(jù)多數(shù)原則判決該比特信息wi水印網(wǎng)格Mw水印字串w 水印比對文件網(wǎng)

18、格對準(zhǔn) 重新網(wǎng)格化提取每個(gè)嵌入水印的比特信息wik計(jì)算相關(guān)度 其中：其中：wik為第為第i個(gè)比特中第個(gè)比特中第k個(gè)頂點(diǎn)所表示的信息；個(gè)頂點(diǎn)所表示的信息；vj和和vj分別為加載分別為加載wik的初始網(wǎng)格模型頂點(diǎn)和水印網(wǎng)的初始網(wǎng)格模型頂點(diǎn)和水印網(wǎng) 格頂點(diǎn)；格頂點(diǎn)；nj為對應(yīng)的初始網(wǎng)格該頂點(diǎn)法矢為對應(yīng)的初始網(wǎng)格該頂點(diǎn)法矢。 提取提取wik0)(00)(1jjjjjjiknvvnvvw 確定確定wi 相關(guān)度計(jì)算相關(guān)度計(jì)算w基于模型圖w基于骨架圖w基于Reeb圖w3D model retrieval system, http:/3.tw/dynamic/.w3D model search engine, .w3D model similarity search e