生活随笔
收集整理的這篇文章主要介紹了
图形处理（十二）拉普拉斯网格优化、最小二乘网格模型光顺
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
看這篇博文前，請(qǐng)先參考我的另外一篇博文《圖形處理（三）簡(jiǎn)單拉普拉斯網(wǎng)格變形-Siggraph 2004》學(xué)習(xí)拉普拉斯坐標(biāo)的相關(guān)理論知識(shí)。這里要分享的paper，是通過(guò)拉普拉斯的方法實(shí)現(xiàn)三角網(wǎng)格模型的優(yōu)化。如果你已經(jīng)非常熟悉三角網(wǎng)格曲面的拉普拉斯相關(guān)理論，實(shí)現(xiàn)這篇paper也就非常容易了。網(wǎng)格曲面的拉普拉斯坐標(biāo)不但可以用于變形、光順，還可以用于優(yōu)化，總之好處多多，你只要學(xué)會(huì)了這一招，那么就可以學(xué)會(huì)這些算法了。
一、優(yōu)化原理
利用Laplacian?坐標(biāo)重建的方法進(jìn)行網(wǎng)格光順，原理很簡(jiǎn)單，最簡(jiǎn)單的就是只要把源網(wǎng)格模型Laplacian?坐標(biāo)δ的模長(zhǎng)縮小，方向不變，就可以然后進(jìn)行Laplacian?網(wǎng)格重建，就可以實(shí)現(xiàn)簡(jiǎn)單的光順效果。
然而如果要進(jìn)行網(wǎng)格優(yōu)化呢？怎么實(shí)現(xiàn)？大牛們告訴我們一個(gè)比較規(guī)則的網(wǎng)格模型一個(gè)特點(diǎn)：當(dāng)網(wǎng)格曲面上任意頂點(diǎn)的局部片中包含的所有三角面片都為等腰三角形時(shí)，該頂點(diǎn)的同一Laplacian?坐標(biāo)和余切Laplacian?坐標(biāo)相等。當(dāng)將上述結(jié)論由某一個(gè)三角面片擴(kuò)展到整個(gè)模型表面時(shí)可以發(fā)現(xiàn)：如果所有的三角面片都接近于正三角形，所有頂點(diǎn)的同一Laplacian?坐標(biāo)和余切Laplacian?坐標(biāo)接近相等。
ok，上面的原理便是paper的思想，只要你懂得了抓住這個(gè)思想，那么算法實(shí)現(xiàn)起來(lái)就容易了。
在三角網(wǎng)格曲面上，頂點(diǎn)vi的拉普拉斯坐標(biāo)定義為，vi點(diǎn)與其一鄰接頂點(diǎn)加權(quán)組合的差：
當(dāng)然權(quán)重wij需要滿足歸一化
權(quán)值的選取很多，但比較常用的權(quán)值是均勻權(quán)、余切權(quán)，其計(jì)算公式如下：
二、網(wǎng)格優(yōu)化算法實(shí)現(xiàn)
算法原理主要是：
1、通過(guò)先求解網(wǎng)格曲面余切權(quán)計(jì)算得到的Laplacian?坐標(biāo)δ
2、構(gòu)建均勻權(quán)下的拉普拉斯矩陣A
3、然后求解AX=δ.
[cpp]?view plaincopy
void?CMeshOptimize::OptimizeMesh(TriMesh*Tmesh)?? {?? ????Tmesh->need_neighbors();?? ????int?vn=Tmesh->vertices.size();?? ?????? ????int?count0=0;?? ????vector<int>begin_N(vn);?? ????for?(int?i=0;i<vn;i++)?? ????{????? ????????begin_N[i]=count0;?? ????????count0+=Tmesh->neighbors[i].size()+1;?? ????}?? ????typedef?Eigen::Triplet<double>?T;?? ????std::vector<T>?tripletList(count0+vn);?? ????for(int?i=0;i<vn;i++)?? ????{?? ????????int?nei_n=Tmesh->neighbors[i].size();?? ????????tripletList[begin_N[i]]=T(i,i,-1.0*nei_n);?? ????????for?(int?k?=?0;k<nei_n;++k)??? ????????{?? ????????????tripletList[begin_N[i]+k+1]=T(i,Tmesh->neighbors[i][k],1);?? ????????}?? ????}?? ?????? ????m_boundary_wieght=100*m_contrain_weight;?? ????for?(int?i=0;i<vn;i++)?? ????{?? ????????if(Tmesh->is_bdy(i))tripletList[count0+i]=T(vn+i,i,m_boundary_wieght);?? ????????else?tripletList[count0+i]=T(vn+i,i,m_contrain_weight);?? ????}?? ?? ????SparseMatrixType?Ls(2*vn,vn);??? ????Ls.setFromTriplets(tripletList.begin(),?tripletList.end());?? ?? ?????? ????SparseMatrixType?ls_transpose=Ls.transpose();?? ????SparseMatrixType?LsLs?=ls_transpose*?Ls;?? ????vector<Eigen::VectorXd>?RHSPos;?? ????Compute_RHS(RHSPos);?? ????Eigen::SimplicialCholesky<SparseMatrixType>MatricesCholesky(LsLs);?? ????#pragma?omp?parallel?for?? ????for?(int?i=0;i<3;i++)?? ????{?? ????????Eigen::VectorXd?xyzRHS=ls_transpose*RHSPos[i];?? ????????Eigen::VectorXd?xyz=MatricesCholesky.solve(xyzRHS);?? ????????for(int?j=0;j<vn;j++)?? ????????{?? ????????????Tmesh->vertices[j][i]=xyz[j];?? ????????}?? ????}?? ?????? }?? ?? void?CMeshOptimize::Compute_RHS(vector<Eigen::VectorXd>?&RHSPos)?? {?? ????int?vn=m_OptimizeMesh->vertices.size();?? ????m_OptimizeMesh->need_neighbors();?? ????m_OptimizeMesh->need_adjacentfaces();?? ????RHSPos.clear();?? ????RHSPos.resize(3);?? ????for?(int?i=0;i<3;i++)?? ????{?? ????????RHSPos[i].resize(2*vn);?? ????????RHSPos[i].setZero();?? ????}?? ?? ????int?fn=m_OptimizeMesh->faces.size();?? ????m_OptimizeMesh->need_adjacentedges();?? ????#pragma?omp?parallel?for?? ????for?(int?i=0;i<vn;i++)?? ????{????? ????????vector<float>CotWeight;?? ????????float?SumWeight;?? ????????CotangentWeights(m_OptimizeMesh,i,CotWeight,SumWeight);?? ????????int?nei_n=m_OptimizeMesh->neighbors[i].size();?? ?????????? ????????vector<int>&a=m_OptimizeMesh->neighbors[i];?? ????????vec?ls;?? ????????for?(int?j=0;j<nei_n;j++)?? ????????{????? ????????????ls=ls+CotWeight[j]*m_OptimizeMesh->vertices[a[j]];?? ????????}?? ????????ls=ls-SumWeight*m_OptimizeMesh->vertices[i];?? ????????for?(int?j=0;j<3;j++)?? ????????{?? ????????????RHSPos[j][i]=ls[j];?? ????????}?? ????}?? ????for?(int?i=vn;i<2*vn;i++)?? ????{?? ????????for?(int?j=0;j<3;j++)?? ????????{????? ????????????if(m_OptimizeMesh->is_bdy(i-vn))RHSPos[j][i]=m_OptimizeMesh->vertices[i-vn][j]*m_boundary_wieght;?? ????????????else?RHSPos[j][i]=m_OptimizeMesh->vertices[i-vn][j]*m_contrain_weight;?? ????????}?? ????}?? ?? ?? }?? ?? void?CMeshOptimize::CotangentWeights(TriMesh*TMesh,int?vIndex,vector<float>&vweight,float?&WeightSum)?? {????? ????int?NeighborNumber=TMesh->neighbors[vIndex].size();?? ????vweight.resize(NeighborNumber);?? ????WeightSum=0;?? ????vector<int>&NeiV=TMesh->neighbors[vIndex];?? ????for?(int?i=0;i<NeighborNumber;i++)?? ????{?? ????????int?j_nei=NeiV[i];?? ????????vector<int>tempnei;?? ????????Co_neighbor(TMesh,vIndex,j_nei,tempnei);?? ????????float?cotsum=0.0;?? ????????for?(int?j=0;j<tempnei.size();j++)?? ????????{?? ????????????vec?vivo=TMesh->vertices[vIndex]-TMesh->vertices[tempnei[j]];?? ????????????vec?vjvo=TMesh->vertices[j_nei]-TMesh->vertices[tempnei[j]];?? ????????????float?dotvector=vivo?DOT?vjvo;?? ????????????dotvector=dotvector/sqrt(len2(vivo)*len2(vjvo)-dotvector*dotvector);?? ????????????cotsum+=dotvector;?? ????????}?? ????????vweight[i]=cotsum/2.0;?? ????????WeightSum+=vweight[i];?? ????}?? ????for?(int?k=0;k<NeighborNumber;++k)?? ????{?? ????????vweight[k]=NeighborNumber*vweight[k]/WeightSum;?? ????}?? ????WeightSum=NeighborNumber;?? ?? }?? void?CMeshOptimize::Co_neighbor(TriMesh?*Tmesh,int?u_id,int?v_id,vector<int>&co_neiv)?? {?? ????Tmesh->need_adjacentedges();?? ????vector<int>&u_id_ae=Tmesh->adjancetedge[u_id];??? ????int?en=u_id_ae.size();?? ????Tedge?Co_Edge;?? ????for?(int?i=0;i<en;i++)?? ????{?? ????????Tedge?&ae=Tmesh->m_edges[u_id_ae[i]];?? ????????int?opsi=ae.opposite_vertex(u_id);?? ????????if?(opsi==v_id)?? ????????{?? ????????????Co_Edge=ae;?? ????????????break;?? ????????}?? ????}?? ????for?(int?i=0;i<Co_Edge.m_adjacent_faces.size();i++)?? ????{?? ????????TriMesh::Face?af=Tmesh->faces[Co_Edge.m_adjacent_faces[i]];?? ????????for?(int?j=0;j<3;j++)?? ????????{?? ????????????if((af[j]!=u_id)&&(af[j]!=v_id))?? ????????????{?? ????????????????co_neiv.push_back(af[j]);?? ????????????}?? ????????}?? ????}?? }??
至此三角網(wǎng)格的優(yōu)化可以說(shuō)算法講完了。因?yàn)樗惴ū容^簡(jiǎn)答，本篇文章篇幅比較小，所以在這篇博文中順便講一下最小二乘網(wǎng)格的相關(guān)概念。
參考文獻(xiàn)：Laplacian Mesh Optimization
三、最小二乘網(wǎng)格相關(guān)理論
這邊順便講一下最小二乘網(wǎng)格，最小二乘網(wǎng)格最初的概念來(lái)源于paper《Least-squares Meshes》，我最初看到最小二乘網(wǎng)格這個(gè)概念是在paper《基于最小二乘網(wǎng)格的模型變形算法》中看到的，因?yàn)橹皩W(xué)習(xí)微分域的網(wǎng)格變形算法的時(shí)候，基本上對(duì)每種變形算法都有看過(guò)相關(guān)的paper，用最小二乘網(wǎng)格的方法實(shí)現(xiàn)網(wǎng)格變形，其實(shí)跟基于多分辨率的網(wǎng)格變形算法是一樣的，都是對(duì)低頻空間中的網(wǎng)格模型進(jìn)行變形操作。
最小二乘網(wǎng)格模型又稱為全局的拉普拉斯光順網(wǎng)格，就是通過(guò)把網(wǎng)格模型的拉普拉斯坐標(biāo)設(shè)置為0，然后求解拉普拉斯方程：
即：
其中權(quán)重wij為：
這樣重建求解的網(wǎng)格即為最小二乘網(wǎng)格，也是一個(gè)光順后的網(wǎng)格模型，因?yàn)樵撃Ｐ偷睦绽棺鴺?biāo)全部為0。
當(dāng)然求解上面的方程還需要控制頂點(diǎn)，控制頂點(diǎn)的個(gè)數(shù)對(duì)效果的影響還是蠻大的，可以看一下下面這個(gè)圖：
總之就是控制頂點(diǎn)的個(gè)數(shù)越少，越是光順。
在paper《Least-squares Meshes》中還演示了通過(guò)給定的拓?fù)滏溄雨P(guān)系，進(jìn)行網(wǎng)格補(bǔ)洞，與原網(wǎng)格模型的區(qū)別。
本文地址：http://blog.csdn.net/hjimce/article/details/46505863?? ? 作者：hjimce ? ? 聯(lián)系qq：1393852684 ??更多資源請(qǐng)關(guān)注我的博客：http://blog.csdn.net/hjimce? ? ? ? ? ? ? ? 原創(chuàng)文章，版權(quán)所有，轉(zhuǎn)載請(qǐng)保留本行信息。
參考文獻(xiàn)：
1、《Least-squares Meshes》
2、《Laplacian Mesh Optimization》
3、《基于最小二乘網(wǎng)格的模型變形算法》
總結(jié)
以上是生活随笔為你收集整理的图形处理（十二）拉普拉斯网格优化、最小二乘网格模型光顺的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
