生活随笔
收集整理的這篇文章主要介紹了
图形处理（十一）Stroke Parameterization
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
轉眼已經過去了好幾年，最近開始寫技術博客，是為了回顧。《Stroke Parameterization》這篇paper是我人生寫的第一篇作者沒有提供代碼的文章，也是初次學會閱讀外文文獻的開始。三年前菜鳥一只，連如何通過paper寫代碼都還不懂，然而沒想到這篇paper花了兩周的時間，竟然被我搞定了，有了信心，從此菜鳥開始學習起飛……
這篇paper的作者也是一大牛，發了好多篇Siggraph的文章，所以自然這篇paper的質量還是挺不錯的。參數化算法的好壞一般是通過紋理貼圖的方法，進行驗證的。
一、相關理論
Stroke Parameterization顧名思義就是沿著曲線進行參數化的意思，在我的另外一篇博文中《離散指數映射Decal》是以一個點為源點，進行參數化，參數化結果為一圓形參數域。然而在網格曲面上，可能有的時候我們并不緊緊是想要圓形Decal，而是希望沿著曲線進行參數化，比如上面文字貼圖中，我們的圖片是一張長方形圖片，這個時候如果用固定邊界的參數化方法，或者用離散指數Decal,它們的參數域一般都類似于圓形，用于上面的貼圖肯定不行。
或者又如上圖，我們給定的一張魚的圖片是矩形的，把魚圖片貼到那個魚缸上，這個時候，我們就要用到沿著曲線進行參數化的方法了。
算法原理：
在網格曲面上，參數化無非就是要求解網格頂點的(u,v)坐標，如上圖所示，已知曲線C(tx)，我們的目標便是要求出曲線附近區域的每個頂點的(u,v)坐標，也就是我們要求出tx，dx，然后就可以得到二維的參數坐標：
dx表示網格頂點x到曲線的最短測地距離。
算法以Dijkstra算法為遍歷依據，根據加權平均的方法，通過已Frozen的鄰接頂點更新計算未知的X點的相關信息。在參數化的過程中通過遍歷的方法，逐個計算頂點的局部坐標系，參數化坐標。
1、頂點x局部標價的更新
頂點x的坐標基底e1更新公式：
其中Nu(x)表示已經被Dijkstra算法遍歷，且標記為Fronzen的頂點(進入隊列，并且又從隊列中刪除的點，也就是已經確定最短距離的頂點)，且其為X點的一鄰接頂點。然后x點局部坐標系的n軸為頂點的法矢，這個直接通過鄰接三角面片的加權平均就可以計算了。
然后，在已知n,e1軸后，我們可以直接用右手法則確定e2軸，也就是直接通過叉乘的方法確定e2:
2、參數化坐標(u,v)更新
頂點x的參數化坐標更新：
其中權重w(qi,x)的計算公式為：
ε是一個非常小的數，以防分母為0，說的簡單一點就是以鄰接邊長的倒數作為權重。
二、算法實現
后面我將結合我寫的代碼，進行算法實現講解，因為這個算法是我還是菜鳥的時候寫的代碼，然后后面也沒有經過整理，只是把效果顯示出來，得出結果，所以代碼很粗糙，將就一下。
Alogrithm：
1、初始化部分：
初始曲線s={pi}上的點pi相關參數初始化：
a、建立pi的局部標價e1為曲線pi點處的切矢，n為頂底法矢，以此根據右手法則計算出e2
[cpp]?view plaincopy
vector<CVector3D>m_e1(m_SeedID.size());?? ???point?pt;?? for(int?i=0;i<m_SeedID.size();i++)?? {?? ?? ????if?(i==0)?? ????{?? ????????pt=Tmesh->vertices[m_SeedID[i+1]]-Tmesh->vertices[m_SeedID[i]];?? ????????m_nodes[m_SeedID[i]].m_e1=CVector3D(pt[0],pt[1],pt[2]);?? ????????m_nodes[m_SeedID[i]].m_e1.Normalize();?? ????}?? ????else?if?(i<m_SeedID.size()-1)?? ????{?? ????????pt=Tmesh->vertices[m_SeedID[i+1]]-Tmesh->vertices[m_SeedID[i-1]];?? ????????m_nodes[m_SeedID[i]].m_e1=CVector3D(pt[0],pt[1],pt[2]);?? ????????m_nodes[m_SeedID[i]].m_e1.Normalize();?? ????}?? ????else??? ????{?? ????????pt=Tmesh->vertices[m_SeedID[i]]-Tmesh->vertices[m_SeedID[i-1]];?? ????????m_nodes[m_SeedID[i]].m_e1=CVector3D(pt[0],pt[1],pt[2]);?? ????????m_nodes[m_SeedID[i]].m_e1.Normalize();?? ????}?? }??
m_SeedID為源曲線上點按順序存儲的索引。
b、計算pi點的參數坐標為：
其中α(pi)為沿著曲線s，pi點的累積弧長，就是相當于累積弧長參數化。
[cpp]?view plaincopy
vec?ab;?? vector<double>arccoordate(m_SeedID.size(),0.0);?? ?? for(int?i=0;i<m_SeedID.size()-1;i++)?? {?? ????ab=Tmesh->vertices[m_SeedID[i+1]]-Tmesh->vertices[m_SeedID[i]];??? ????sumlength+=len(ab);?? ????arccoordate[i+1]=sumlength;?? }??
c、pi點的測地距離設置為0(Dijkstra算法源點集設置)。
[cpp]?view plaincopy
for(int?i=0;i<m_SeedID.size();i++)?? {?? ????m_nodes[m_SeedID[i]].m_UV.dx=arccoordate[i];?? ????m_nodes[m_SeedID[i]].m_UV.dy=0.0;?? ????m_nodes[m_SeedID[i]].m_VisitFlag=CDEMNode::Active;?? ????m_nodes[m_SeedID[i]].distance_from_source()=0.0;?? ????m_nodes[m_SeedID[i]].m_GeodesicDistance=m_nodes[m_SeedID[i]].m_UV.GetLength();?? ????m_nodes[m_SeedID[i]].m_Normal=m_VertexNormals[m_SeedID[i]];?? ????m_nodes[m_SeedID[i]].m_e2=m_nodes[m_SeedID[i]].m_e1?*?m_nodes[m_SeedID[i]].m_Normal;?? }??
2、Dijkstra算法更新鄰域點
根據前面所說的計算方法進行更新參數化坐標，及每個頂點的局部標價。這一步主要就是用到公式2和公式3，然后在結合Dijkstra算法就OK了
[cpp]?view plaincopy
void?CStrokeParameterization::DecalGeodesicVectors(TriMesh?*G1Mesh,double?r)????? {?? ?? ????G1Mesh->need_normals();?? ????G1Mesh->need_neighbors();?? ????VertexNormals.clear();?? ????m_VertexNormals.clear();?? ????for?(int?i=0;i<G1Mesh->vertices.size();i++)?? ????{?? ????????vec?nor;?? ????????nor=G1Mesh->normals[i];?? ????????VertexNormals.push_back(nor);?? ????????nor=normalize(nor);?? ????????m_VertexNormals.push_back(CVector3D(nor[0],nor[1],nor[2]));?? ????}?? ?? ?????? ????unsigned?vn,fn;?? ????vn=G1Mesh->vertices.size();??? ????fn=G1Mesh->faces.size();?? ????double?*pts;?? ????pts?=?new?double[vn*3];?? ????unsigned?*fs;?? ????fs?=?new?unsigned[fn*3];?? ?? ????for?(int?i=0;i<vn;i++)?? ????{?? ????????point?p=G1Mesh->vertices[i];?? ????????int?shift=i*3;?? ????????pts[shift]=p[0];?? ????????pts[shift+1]=p[1];?? ????????pts[shift+2]=p[2];?? ????}?? ????for?(int?i=0;i<fn;i++)?? ????{?? ????????int??shift=i*3;?? ????????fs[shift]=G1Mesh->faces[i][0];?? ????????fs[shift+1]=G1Mesh->faces[i][1];?? ????????fs[shift+2]=G1Mesh->faces[i][2];?? ????}?? ????Gmesh.from_TriMeshData(vn,pts,fn,fs);?? ????delete?[]pts;?? ????delete?[]fs;?? ????numOfVertices=G1Mesh->vertices.size();?? ????numOfFaces=G1Mesh->faces.size();?? ?? ?? ?? ????m_nodes.resize(numOfVertices);?? ????for(unsigned?i=0;?i<m_nodes.size();?++i)?? ????{?? ????????m_nodes[i].vertex()?=?&Gmesh.vertices()[i];?? ????????m_nodes[i].clear();?? ????????m_nodes[i].m_VertexID=i;?? ?????????? ????}?? ????std::set<DEMNode_pointer,?CDEMNode>??Queue0;??? ????Queue0.clear();?? ????InitializationSeed();?? ????for(int?i=0;i<m_CurveNeighbor.size();i++)?? ????{?? ??????Queue0.insert(&m_nodes[m_SeedCurve[i]]);?? ????}?? ????std::vector<double>?distances_between_nodes;?? ????std::vector<DEMNode_pointer>?neighbor_nodes;?? ????while(!Queue0.empty())?? ????{?? ????????DEMNode_pointer?min_node?=?*Queue0.begin();?? ????????Queue0.erase(Queue0.begin());?? ????????assert(min_node->distance_from_source()?<?GEODESIC_INF);?? ????????min_node->m_VisitFlag=CDEMNode::Frozen;?? ????????vector<int>::iterator?iter?=?find(m_CurveNeighbor.begin(),m_CurveNeighbor.end(),min_node->m_VertexID);?? ????????if?(iter==m_CurveNeighbor.end())?? ????????{?? ????????????min_node->m_e1=Average_e1(min_node->m_VertexID);?? ????????????min_node->m_Normal=m_VertexNormals[min_node->m_VertexID];?? ????????????min_node->m_e2=min_node->m_e1?*?min_node->m_Normal;?? ????????????min_node->m_UV=Average_GVector(min_node->m_VertexID);?? ????????????min_node->m_GeodesicDistance=min_node->m_UV.GetLength();?? ????????}?? ?????? ????????neighbor_nodes.clear();?? ????????distances_between_nodes.clear();?? ????????list_neighbor_from_node(min_node,?neighbor_nodes,?distances_between_nodes);?? ????????for(unsigned?i=0;?i<neighbor_nodes.size();?++i)???????? ????????{?? ????????????DEMNode_pointer?next_node?=?neighbor_nodes[i];?? ????????????if(next_node->distance_from_source()?>?min_node->distance_from_source()?+?? ????????????????distances_between_nodes[i])?? ????????????{?? ????????????????next_node->distance_from_source()?=?min_node->distance_from_source()?+?? ????????????????????distances_between_nodes[i];?? ????????????????next_node->previous()?=?min_node;?? ????????????}?? ????????}?? ?????? ????????int?neighbor_size_of_u=neighbor_size(min_node->vertex());?? ????????if((min_node->m_UV.dx<=(sumlength+r))&&(-r<(min_node->m_UV.dx))&&(abs(min_node->m_UV.dy)<=r))?? ????????{?? ????????????vertex_pointer?vertex_of_u=min_node->vertex();?? ????????????face_pointer?adjface_of_u;?? ????????????for?(int?i=0;i<vertex_of_u->adjacent_faces().size();i++)?? ????????????{?? ????????????????adjface_of_u=vertex_of_u->adjacent_faces()[i];?? ????????????????int?face_id=adjface_of_u->id();?? ????????????????G1Mesh->faces[face_id].beSelect=true;?? ????????????}?? ?? ?? ????????????for?(int?j=0;j<neighbor_size_of_u;j++)?? ????????????{?? ????????????????int?neighbors_of_u;?? ????????????????neighbors_of_u=neighbor_i(min_node->m_VertexID,j);?? ????????????????if?(m_nodes[neighbors_of_u].m_VisitFlag==CDEMNode::Inactive)?? ????????????????{?? ????????????????????Queue0.insert(&m_nodes[neighbors_of_u]);?? ????????????????????m_nodes[neighbors_of_u].m_VisitFlag=CDEMNode::Active;????????????? ????????????????}?? ????????????}?? ????????}?? ?????? ????}?? ???DecalNormalization(r);?? }?? ?? int?CStrokeParameterization::neighbor_size(geodesic::vertex_pointer?u)?? {?? ????int?number;?? ????number=u->adjacent_edges().size();?? ????return?number;?? }?? int?CStrokeParameterization::neighbor_i(geodesic::vertex_pointer?u,int?i)?? {?? ????int?neighbor_id;?? ????edge_pointer?adjacent_e_u=u->adjacent_edges()[i];?? ????neighbor_id=adjacent_e_u->opposite_vertex(u)->id();?? ????return?neighbor_id;?? }?? int?CStrokeParameterization::neighbor_i(int?u,int?i)?? {?? ????int?neighbor_id;?? ????vertex_pointer?vertex_u=&Gmesh.vertices()[u];?? ????edge_pointer?adjacent_e_u=vertex_u->adjacent_edges()[i];?? ????vertex_pointer?adjacent_v_u=adjacent_e_u->opposite_vertex(vertex_u);?? ????neighbor_id=adjacent_v_u->id();?? ????return?neighbor_id;?? }?? vector<int>?CStrokeParameterization::Co_neighbor(int?u_id,int?v_id)?? {?? ????vector<int>?co_neighbor;?? ????co_neighbor.clear();?? ????vertex_pointer?u,v;?? ????u=&Gmesh.vertices()[u_id];?? ????v=&Gmesh.vertices()[v_id];???? ????for?(int?i=0;i<neighbor_size(u);i++)?? ????{?? ????????int?u_nei,v_nei;?? ????????u_nei=neighbor_i(u_id,i);?? ????????for(int?j=0;j<neighbor_size(v);j++)?? ????????{?? ????????????v_nei=neighbor_i(v_id,j);?? ????????????if?(u_nei==v_nei)?? ????????????{?? ????????????????co_neighbor.push_back(v_nei);?? ????????????}?? ????????}?? ?? ????}?? ?? ????return?co_neighbor;?? }?? ?? void?CStrokeParameterization::DecalNormalization(double?radius)?? {?? ????double?dScale=?1.0/?(3.0*radius);??????????????????? ????for?(int?i=0;i<m_nodes.size();i++)?? ????{?? ????????m_nodes[i].m_UV.dx=dScale*m_nodes[i].m_UV.dx;????????????????????????????? ????????m_nodes[i].m_UV.dy=dScale*m_nodes[i].m_UV.dy;??? ????}?? }?? ?? ?? ?? void?CStrokeParameterization::list_neighbor_from_node(DEMNode_pointer?node,??? ????????????????????????????????????????????????????????????????????std::vector<DEMNode_pointer>&?storage,?? ????????????????????????????????????????????????????????????????????std::vector<double>&?distances)?? {?? ????vertex_pointer?v?=?node->vertex();?? ????assert(storage.size()?==?distances.size());?? ?? ????for(unsigned?i=0;?i<v->adjacent_edges().size();?++i)?? ????{?? ????????edge_pointer?e?=?v->adjacent_edges()[i];?? ????????vertex_pointer?new_v?=?e->opposite_vertex(v);?? ????????DEMNode_pointer?DEMNew_node=&m_nodes[node_index(new_v)];?? ????????double?l=e->length();?? ???????if(DEMNew_node->m_VisitFlag!=CDEMNode::Frozen)?? ???????{?? ???????????storage.push_back(DEMNew_node);?? ???????????distances.push_back(e->length());?? ???????}?????????? ????}?? }?? ?? ?? unsigned?CStrokeParameterization::?node_index(vertex_pointer?v)??????? {?? ????return?v->id();?? };??
[cpp]?view plaincopy
?? CVector2D?CStrokeParameterization::Average_GVector(int?q)?? {????? ?? ????CVector2D?AverageGvector;?? ????vector<int>?neighbor=Tmesh->neighbors[q];?? ????CVector3D?sume1;?? ????double?weight;?? ????double??sumweight=0.0;?? ????for(int?i=0;i<neighbor.size();i++)?? ????{????? ????????if?(m_nodes[neighbor[i]].m_VisitFlag==CDEMNode::Frozen)?? ???????{??? ????????vec?pq=Tmesh->vertices[q]-Tmesh->vertices[neighbor[i]];?? ????????weight=1.0/len(pq);?? ????????CVector3D?pq0(pq[0],pq[1],pq[2]);?? ????????pq0=pq0*AlignNormal(q,neighbor[i]);?? ????????CVector2D?uvofq(pq0|m_nodes[neighbor[i]].m_e1,pq0|m_nodes[neighbor[i]].m_e2);?? ????????uvofq=uvofq+m_nodes[neighbor[i]].m_UV;?? ????????uvofq=uvofq*weight;?? ????????AverageGvector=AverageGvector+uvofq;?? ????????sumweight+=weight;?? ???????}?? ????}?? ????AverageGvector=AverageGvector/sumweight;?? ??? ?? ??return?AverageGvector;?? }??
[cpp]?view plaincopy
?? CMatrix3D?CStrokeParameterization::AlignNormal(int?p,int?q)?? {?? ????double?angle=0.0;?? ????vec?p_nor,q_nor;?? ????CVector3D?p_Nor,q_Nor,Cross_qN_pN;?? ????CMatrix3D?rotMtrx1;?? ????p_nor=VertexNormals[p];?? ????q_nor=VertexNormals[q];?? ????p_Nor=CVector3D(p_nor[0],p_nor[1],p_nor[2]);?? ????q_Nor=CVector3D(q_nor[0],q_nor[1],q_nor[2]);?? ????p_Nor.Normalize();?? ????q_Nor.Normalize();?? ????angle=p_Nor|q_Nor;?? ????angle=acos(angle);?????????????????????????????????????? ????Cross_qN_pN=p_Nor*q_Nor;?? ????rotMtrx1=rotMtrx1.CreateRotateMatrix(angle,Cross_qN_pN);?? ?? return?rotMtrx1;?? }?? ?? CMatrix3D?CStrokeParameterization::AlignNormaln(CVector3D?np,CVector3D?nq)?? {?? ????double?angle=0.0;?? ????CVector3D?p_Nor,q_Nor,Cross_qN_pN;?? ????CMatrix3D?rotMtrx1;?? ????p_Nor=np;?? ????q_Nor=nq;?? ????p_Nor.Normalize();?? ????q_Nor.Normalize();?? ????angle=p_Nor|q_Nor;?? ????angle=acos(angle);?????????????????????????????????????? ????Cross_qN_pN=p_Nor*q_Nor;?? ????rotMtrx1=rotMtrx1.CreateRotateMatrix(angle,Cross_qN_pN);?? ????return?rotMtrx1;?? }??
Frame Field的更新顯示結果：
這種沿著曲線進行參數化的paper較少，還有另外一篇paper：《Texture Brush: An Interactive Surface Texturing Interface》也是沿著曲線參數化，不過效率速度都感覺沒有這個爽。不過那篇paper的紋理貼圖的效果看起來倒是挺漂亮的：
貼圖
這篇paper就講到這里吧。參數化在Siggraph上面的paper還是很多的，每一年都有Parameterization相關的模塊，所以還有很多paper等著我們去學習
本文地址：http://blog.csdn.net/hjimce/article/details/46489913?? ? 作者：hjimce ? ? 聯系qq：1393852684 ??更多資源請關注我的博客：http://blog.csdn.net/hjimce? ? ? ? ? ? ? ? 原創文章，轉載請保留本行信息。
參考文獻：
1、Texture Brush: An Interactive Surface Texturing Interface
2、Stroke Parameterization
3、Interactive Decal Compositing with Discrete Exponential Maps
總結
以上是生活随笔為你收集整理的图形处理（十一）Stroke Parameterization的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
