半邊數據結構學習
- 一、網格數據結構
- 二、半邊數據結構
- 頂點(Vertex)
- 半邊(HalfEdge)
- 面片(Face)
- 三、OpenMesh 相關代碼
- 拓撲關聯對象
- 遍歷
- 四、OpenFilpper 相關代碼
- HoleInfo類
- 孔洞檢測
- 孔洞信息
- HoleFiller類
- 孔洞補全
一、網格數據結構
對于表面網絡來說，其關鍵在于拓撲，也就是曲面是如何表達的。拓撲的不同造就了不同的數據結構和標準，其進行網格查詢和編輯的性能也不同。
常見的網格數據結構有基于面的數據結構、基于邊的數據結構、半邊數據結構、有向邊數據結構等。這里主要結合OpenMesh以及OpenFlipper學習一下半邊數據結構。
二、半邊數據結構
每個邊分為兩個半邊，每個半邊都是一個有向邊，方向相反。如果一個邊被兩個面片公用，則每個面片都能各自擁有一個半邊。如果一個邊僅被一個面片占用（邊界邊），則這個面片僅擁有該邊的其中一個半邊，另一個半邊為閑置狀態。每一條半邊僅存儲它的起點指針。
那么是否可以通過邊的閑置狀態來定位網格中的孔洞或邊界？
半邊數據結構僅支持流形網絡。
計算機圖形學上，通常說的流形是一種幾何模型表面（但不是所有的），即二維流形，對應拓撲流形。如果網格的每個邊最多被兩個面片共用，那么這個網格就是流形網絡，否則稱為非流形網絡。
半邊數據結構的三個重要的數據結構——頂點、半邊、面片。
頂點(Vertex)
包含出半邊（OutgoingHalfedge）的指針或索引。
在半邊數據結構中的點儲存著其位置和以其為起始點的半邊的指針。
當在點上存在有多條半邊相連，可以指向任意一半邊，可以通過以下查詢方式遍歷所有半邊
struct HE_vert { float x,y,z; HE_edge* edge; // one of the half-edges emantating from the vertex 指向任意一個以它為出發點的半邊};
半邊(HalfEdge)
包含起點（StartVertex）、鄰接面(AdjacentFace)、下一條半邊(NextHalfedge)、相反邊（opposite）的指針或索引。
注意：有的實現方式是將指向半邊的終點。
struct HE_edge { HE_vert* vert; // vertex at the start of the half-edge 指向半邊的出發點 HE_edge* pair; // oppositely oriented adjacent half-edge 指向相反的相鄰半邊(也稱twin)HE_edge* next; // next half-edge around the face 指向后一個半邊HE_face* face; // face the half-edge borders 指向半邊相鄰的面片};
面片(Face)
包含一條起始邊（FirstHalfedge）的指針或索引對于一個半邊數據結構的簡單形式，一個面僅僅需要儲存一個圍繞它的邊的指針，在一些特定場合可能要求我們儲存比如材質和法向一類的信息。和上面一樣，雖然有很多邊圍繞著面，我們只需要儲存其中一條，而無所謂是哪一條。
struct HE_face { HE_edge* edge; // one of the half-edges bordering the face 指向任意一個環繞它的半邊};
頂點可能有兩條或以上的出半邊，而頂點的數據表達只有一條出半邊，那這條出半邊是哪一條？半邊的下一條半邊又是哪一條？面片的起始半邊又是哪一條？通過某個網格的數據結構圖能看得出這些信息嗎？
事實上，半邊數據結構的網格的構建通常是通過面列表來創建的，也就是說，正常的構建半邊數據結構網格是通過一個一個面片的添加來構建的。
所以面的添加順序就決定了點邊面結構的信息，添加面的方法通常是addFace(a,b,c,…)，a,b,c…參數是該面片按其某條環路順序排列的頂點的指針或索引。注意，環路可以是順時針或者逆時針，決定了該面片的方向（法向量的方向）。
三、OpenMesh 相關代碼
OpenMesh就是使用的半邊數據結構。
拓撲關聯對象
// Type declarations for handles: 句柄類型聲明：
OpenMesh::VertexHandle verH; // 頂點句柄聲明
OpenMesh::FaceHandle facH; // 面句柄聲明
OpenMesh::HalfedgeHandle hedH, hedH_n, hedH_p; // 半邊句柄聲明
OpenMesh::Vec3d point; // 三維向量，用于存儲頂點坐標// Half-edge operations: 半邊操作:
half-edge → vert: verH = mesh.to_vertex_handle(hedH); // 從半邊獲取頂點句柄
half-edge→ pair→vert:verH = mesh.from_vertex_handle(hedH); // 從對向半邊獲取頂點句柄
half-edge→ next:hedH_n = mesh.next_halfedge_handle(hedH); // 獲取當前面中下一條半邊的句柄
half-edge→pair:hedH_p = mesh.opposite_halfedge_handle(hedH); // 獲取當前半邊的對向半邊的句柄
half-edge → face: facH = mesh.face_handle(hedH); // 獲取包含給定半邊的面句柄
face → half-edge: hedH = mesh.halfedge_handle(facH); // 獲取給定面的一條半邊句柄
vert → half-edge: hedH = mesh.halfedge_handle(verH); // 獲取從給定頂點出發的一條半邊句柄
vert coordinates: point = mesh.point(verH); // 獲取與頂點句柄相關聯的頂點的三維坐標
遍歷
// vertex iterator
typedef OpenMesh::TriMesh_ArrayKernelT<> MyMesh; // 定義網格類型
MyMesh mesh;
OpenMesh::VertexHandle verH; // 定義頂點句柄
MyMesh::VertexIter vit; // 定義頂點迭代器
OpenMesh::Vec3d p;
int valence; // 定義存儲頂點度的變量
OpenMesh::IO::read_mesh(mesh, "cube.off")
for (vit = mesh.vertices_begin(); vit != mesh.vertices_end(); vit++) // 遍歷所有頂點
{verH = *vit; // 獲取當前迭代器指向的頂點句柄p = mesh.point(verH); // 獲取頂點坐標valence = mesh.valence(verH); // 獲取頂點的度（連接的邊數）cout << p[0] << " " << p[1] << " " << p[2] << " " << valence << endl; // 輸出頂點坐標和度數
}
// face iteratortypedef OpenMesh::TriMesh_ArrayKernelT<> MyMesh;
MyMesh mesh;
OpenMesh::FaceHandle facH; // 定義面句柄
MyMesh::FaceIter fit; // 定義面迭代器
int nvert; // 定義存儲頂點數的變量
OpenMesh::IO::read_mesh(mesh, "cube.off")
for (fit = mesh.faces_begin(); fit != mesh.faces_end(); fit++) // 遍歷所有面
{facH = *fit; // 獲取當前迭代器指向的面句柄nvert = mesh.valence(facH); // 獲取面的頂點數（面的度）cout << "Number of vertices = " << nvert << endl;
}
// edge iteratortypedef OpenMesh::TriMesh_ArrayKernelT<> MyMesh;
MyMesh mesh;
OpenMesh::EdgeHandle edgH; // 定義邊句柄
MyMesh::EdgeIter eit; // 定義邊迭代器
float len, angle; // 定義存儲邊長度和二面角的變量
OpenMesh::IO::read_mesh(mesh, "cube.off")
for (eit = mesh.edges_begin(); eit != mesh.edges_end(); eit++) // 遍歷所有邊
{edgH = *eit;len = mesh.calc_edge_length(edgH); // 計算邊的長度angle = mesh.calc_dihedral_angle(edgH); // 輸出邊的長度和二面角cout << "Edge length = " << len <<" Dihedral angle = " << angle << endl;
}
半面及二面角 ：一條直線把平面分成兩個部分，其中的每一部分都稱為半平面。從一條直線出發的兩個半平面所組成的圖形稱為二面角。這條直線稱為二面角的棱，這兩個半平面稱為二面角的面。
四、OpenFilpper 相關代碼
在三維重建中，建模的網格嘗嘗由于遮擋等原因產生孔洞，導致其完整性降低，因此，常通過網格孔洞修復來得到一個完整的結構（但一般只能用于簡單網格）。接下來看一下OpenFilpper中是怎么查找和修復孔洞的。
HoleInfo類
孔洞檢測
template< class MeshT >void HoleInfo< MeshT >::getHoles(){// Property for the active mesh to mark already visited edges // 邊界搜索的屬性句柄，用于標記已訪問的邊界邊OpenMesh::EPropHandleT< bool > boundary_search;// Add a property to the mesh to store original vertex positionsmesh_->add_property( boundary_search, "Boundary search" ); // Initialize Property // 先都初始化為false，表示未被訪問typename MeshT::EdgeIter e_it, e_end=mesh_->edges_end();for (e_it=mesh_->edges_begin(); e_it!=e_end; ++e_it) {mesh_->property( boundary_search , *e_it ) = false;}holes_.clear();for (e_it=mesh_->edges_begin(); e_it!=e_end; ++e_it) {// Skip already visited edges // 跳過已訪問的邊if ( mesh_->property( boundary_search , *e_it ) )continue;// Check only boundary edges // 只處理邊界邊if ( !mesh_->is_boundary(*e_it))continue; // Get boundary halfedge // 獲取邊界的半邊typename MeshT::HalfedgeHandle hh = mesh_->halfedge_handle( *e_it, 0 );if ( ! mesh_->is_boundary( hh ) )hh = mesh_->opposite_halfedge_handle( hh );typename MeshT::Point center(0,0,0);Hole currentHole; // 初始化孔洞信息// Collect boundary edges // 收集邊界邊typename MeshT::HalfedgeHandle ch = hh;do {currentHole.push_back( mesh_->edge_handle(ch) );// 計算孔洞中心center += mesh_->point( mesh_->from_vertex_handle(ch) ); mesh_->property( boundary_search , mesh_->edge_handle(ch) ) = true;//check number of outgoing boundary HEH's at Vertex // 檢查頂點的出邊數目int c = 0;typename MeshT::VertexHandle vh = mesh_->to_vertex_handle(ch);for ( typename MeshT::VertexOHalfedgeIter voh_it(*mesh_,vh); voh_it.is_valid(); ++voh_it)if ( mesh_->is_boundary( *voh_it ) )c++;if ( c >= 2){ // 如果頂點有多于兩條出邊，選擇下一個出邊typename MeshT::HalfedgeHandle op = mesh_->opposite_halfedge_handle( ch );typename MeshT::VertexOHalfedgeIter voh_it(*mesh_,op);ch = *(++voh_it);} elsech = mesh_->next_halfedge_handle( ch );} while ( ch != hh );center /= currentHole.size(); // 計算孔洞中心bool isHole = true; // 檢查孔洞形狀int err = 0;for (unsigned int i=0; i < currentHole.size(); i++){typename MeshT::HalfedgeHandle hh = mesh_->halfedge_handle( currentHole[i], 0 );if ( ! mesh_->is_boundary( hh ) )hh = mesh_->opposite_halfedge_handle( hh );typename MeshT::VertexHandle vh = mesh_->from_vertex_handle(hh);typename MeshT::Normal n = mesh_->normal( vh );typename MeshT::Point p = mesh_->point( vh );// 檢查孔洞中每個點到孔洞中心的距離if ( (p - center).norm() < (p + n - center).norm() ){// isHole = false;// break;err++;}}// std::cerr << "Errors " << err << " Size " << hole.count << std::endl; if (isHole) // 如果是孔洞，將其加入孔洞列表holes_.push_back(currentHole);}mesh_->remove_property( boundary_search); // 結束時，移除boundary_search屬性}
使用半邊數據結構檢測孔洞的步驟
- 標記邊界邊
- 遍歷網格的所有邊，找出只有半邊的邊作為邊界邊。
- 遍歷邊界邊
- 對于每條邊界邊，獲取與該邊關聯的半邊。
- 跟蹤半邊環
- 從一條邊界邊開始，可以通過半邊數據結構相關函數沿著邊界環遍歷。
- 遍歷半邊環的方法：
- 使用
next_halfedge_handle()函數從當前半邊跳轉到下一條邊界上的半邊。 - 如果遇到頂點有多條出邊的情況（表示頂點是網格的拐角），可以使用
opposite_halfedge_handle()函數找到對稱的半邊，然后從中選擇下一個出邊。
- 使用
- 收集孔洞邊
- 在遍歷半邊環的過程中，收集所有構成孔洞的邊界邊。可以使用一個列表或類似的數據結構來存儲這些邊的句柄或索引。
- 驗證孔洞
- 一旦收集完一條半邊環上的所有邊界邊，可以進行一些驗證步驟來確認它確實是一個孔洞，比如計算孔洞的幾何中心，檢查邊界邊是否按某種順序排列等。
- 存儲孔洞
- 驗證通過則將孔洞的邊界邊等信息存儲在孔洞列表中。
孔洞信息
template< class MeshT >void HoleInfo< MeshT >::getHolePostitionInfo(const int _index, typename MeshT::Normal& _holeNormal, typename MeshT::Point& _holeCenter) const{// 計算指定孔洞 _index 的中心位置和平均法線 _holeCenter = typename MeshT::Point(0.0,0.0,0.0);_holeNormal = typename MeshT::Normal(0.0,0.0,0.0);// Center of gravity of hole and an average normal at the hole boundaryfor ( size_t i = 0 ; i < holes_[_index].size() ; ++i ) {const typename MeshT::HalfedgeHandle he = mesh_->halfedge_handle(holes_[_index][i],0);const typename MeshT::VertexHandle vh_to = mesh_->to_vertex_handle(he);_holeCenter += mesh_->point(vh_to);_holeNormal += mesh_->normal(vh_to);}_holeCenter /= typename MeshT::Scalar(holes_[_index].size());_holeNormal /= typename MeshT::Scalar(holes_[_index].size());_holeNormal.normalize();}template< class MeshT >void HoleInfo< MeshT >::getHoleInfo(const unsigned int _index, size_t& _edges, typename MeshT::Scalar& _diagonal, typename MeshT::Scalar& _boundaryLength) const{//獲取指定孔洞 _index 的基本信息，包括邊數、對角線長度和邊界長度 if ( _index >= holes_.size() ) {std::cerr << "Invalid hole index " << _index << std::endl;return;}_boundaryLength = 0.0;typename MeshT::Point minCoord = typename MeshT::Point(std::numeric_limits<typename MeshT::Scalar>::max(),std::numeric_limits<typename MeshT::Scalar>::max(),std::numeric_limits<typename MeshT::Scalar>::max());typename MeshT::Point maxCoord = typename MeshT::Point(-std::numeric_limits<typename MeshT::Scalar>::max(),-std::numeric_limits<typename MeshT::Scalar>::max(),-std::numeric_limits<typename MeshT::Scalar>::max());for (size_t i = 0 ; i < holes_[_index].size() ; ++i) {_boundaryLength += mesh_->calc_edge_length(holes_[_index][i]);typename MeshT::Point pos = mesh_->point(mesh_->from_vertex_handle(mesh_->halfedge_handle(holes_[_index][i],0)));minCoord[0] = std::min(minCoord[0],pos[0]);minCoord[1] = std::min(minCoord[1],pos[1]);minCoord[2] = std::min(minCoord[2],pos[2]);maxCoord[0] = std::max(maxCoord[0],pos[0]);maxCoord[1] = std::max(maxCoord[1],pos[1]);maxCoord[2] = std::max(maxCoord[2],pos[2]);}_edges = holes_[_index].size();_diagonal = (maxCoord - minCoord).length();}template< class MeshT >std::vector< std::vector< typename MeshT::EdgeHandle > >* HoleInfo< MeshT >::holes(){//返回指向孔洞列表 holes_ 的指針return &holes_;}
HoleFiller類
孔洞補全
template< class MeshT >
void HoleInfo< MeshT >::fillHole(int _index, int _stages)
{if ((uint) _index > holes_.size()){ // 檢查索引是否有效std::cerr << "Cannot fill hole. Index invalid." << std::endl;return;}// 如果filler為空，則創建一個新fillerif (filler_ == 0)filler_ = new HoleFiller< MeshT >(*mesh_);// 使用filler填補指定孔洞的第一個邊界邊filler_->fill_hole(holes_[_index][0], _stages);// 垃圾回收，清理無效數據mesh_->garbage_collection();// 清除邊選擇狀態MeshSelection::clearEdgeSelection(mesh_);// 更新網格法線mesh_->update_normals();
}template< class MeshT >
void HoleInfo< MeshT >::fillHole(typename MeshT::EdgeHandle _eh, int _stages)
{if (filler_ == 0)filler_ = new HoleFiller< MeshT >(*mesh_);filler_->fill_hole(_eh, _stages);mesh_->garbage_collection();MeshSelection::clearEdgeSelection(mesh_);mesh_->update_normals();
}template< class MeshT >void HoleInfo< MeshT >::fillAllHoles(int _stages){if (filler_ == 0)filler_ = new HoleFiller< MeshT >(*mesh_);filler_->fill_all_holes( _stages );}
//=============================================================================
//
// Fill a hole which is identified by one of its boundary edges.
// 通過其邊界邊填補一個被識別的孔洞。
//
//=============================================================================template< class MeshT >
void HoleFiller< MeshT >::fill_hole( EH _eh, int _stages )
{std::cerr << " Stage 1 : Computing a minimal triangulation ... ";// 打印信息：階段1：計算最小三角剖分// 記錄最后一個頂點，用于選擇新頂點typename MeshT::VertexHandle old_last_handle = *(--mesh_.vertices_end());// 如果沒有邊界邊，則不是孔洞if ( ! mesh_.is_boundary( _eh ) )return;// 獲取邊界半邊HH hh = mesh_.halfedge_handle( _eh, 0 );if ( ! mesh_.is_boundary( hh ) )hh = mesh_.opposite_halfedge_handle( hh );// 收集邊界頂點和相對應的對向頂點boundary_vertex_.clear();opposite_vertex_.clear();HH ch = hh;do {boundary_vertex_.push_back( mesh_.from_vertex_handle( ch ) );opposite_vertex_.push_back( mesh_.to_vertex_handle(mesh_.next_halfedge_handle( mesh_.opposite_halfedge_handle( ch ) ) ) );// 計算頂點處的外向半邊數量int c = 0;VH vh = mesh_.to_vertex_handle(ch);for ( typename MeshT::VertexOHalfedgeIter voh_it(mesh_, vh); voh_it.is_valid(); ++voh_it )if ( mesh_.is_boundary( *voh_it ) )c++;if ( c >= 2 ) {HH op = mesh_.opposite_halfedge_handle( ch );typename MeshT::VertexOHalfedgeIter voh_it(mesh_, op);ch = *(++voh_it);} elsech = mesh_.next_halfedge_handle( ch );} while ( ch != hh );int nv = boundary_vertex_.size();// 計算初始三角剖分所需的權重和連接信息w_.clear();w_.resize( nv, std::vector<Weight>( nv, Weight() ) );l_.clear();l_.resize( nv, std::vector<int>( nv, 0 ) );// 初始化邊界上相鄰頂點的權重為0for ( int i = 0; i < nv - 1; ++i )w_[i][i+1] = Weight( 0, 0 );// 動態規劃計算最小權重的三角剖分for ( int j = 2; j < nv; ++j ) {#pragma omp parallel for shared(j, nv)for ( int i = 0; i < nv - j; ++i ) {Weight valmin;int argmin = -1;for ( int m = i + 1; m < i + j; ++m ) {Weight newval = w_[i][m] + w_[m][i+j] + weight( i, m, i+j );if ( newval < valmin ) {valmin = newval;argmin = m;}}w_[i][i+j] = valmin;l_[i][i+j] = argmin;}}// 實際填補孔洞。收集所有新生成的三角形和邊界邊hole_edge_.clear();hole_triangle_.clear();if ( fill( 0, nv - 1 ) ) {std::cerr << "ok\n";// 如果只需要一階段，則返回if ( _stages <= 1 )return;std::cerr << " Stage 2 : Fairing the filling ... ";// 打印信息：階段2：平滑填充區域std::vector< FH > handles = hole_triangle_;// 對填補后的三角形進行平滑處理fairing(handles);// 標記所有新頂點為已選擇狀態typename MeshT::VertexIter old_end = ++typename MeshT::VertexIter(mesh_, old_last_handle);typename MeshT::VertexIter v_end = mesh_.vertices_end();for ( ; old_end != v_end; ++old_end )if ( !mesh_.status(*old_end).deleted() )mesh_.status(*old_end).set_selected( true );std::cerr << "ok\n";} elsestd::cerr << "Could not create triangulation" << std::endl;
}使用 OpenFlipper 測試了一下，孔洞都能找到，但是需要進一步篩選。然后如果孔洞較大、不規則，其補全效果其實比較差。
先到這兒。
參考以推薦閱讀：
1.半邊數據結構&網格細分與簡化
2.半邊數據結構與OpenMesh中的處理
3.Polygon Mesh Processing 閱讀筆記(2) 網格數據結構
4.The Half Edge Data Structure
5.Half-Edge Data Structures
![MySql性能調優03-[SQL優化]](http://pic.xiahunao.cn/MySql性能調優03-[SQL優化])
