User Manual 用戶手冊
該類Surface_mesh是半邊數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)予权，可用于表示多面體表面扫腺。它是CGAL包Halfedge Data Structure和3D Polyhedral Surface的替代方案。主要區(qū)別在于它是基于索引的攒至，而不是基于指針的迫吐。此外账忘，將信息添加到頂點鳖擒，半邊蒋荚，邊和面的機制要簡單得多，并且可以在運行時(runtime)完成惊奇，而不必在編譯時完成颂郎。
因為數(shù)據(jù)結(jié)構(gòu)使用整數(shù)索引作為頂點容为，半邊，邊和面的描述符房维，所以它的內(nèi)存占用空間比基于64位指針的版本要低咙俩。由于索引是連續(xù)的湿故，因此它們可以用作存儲屬性的向量的索引坛猪。
當元素被刪除時墅茉，它們僅被標記為已刪除，并且必須調(diào)用垃圾回收函數(shù)才能真正刪除它們悍募。
1 用法（usage）
主類Surface_mesh提供了四個嵌套類坠宴，它們表示半邊數(shù)據(jù)結(jié)構(gòu)的基本元素：
- Surface_mesh::Vertex_index
- Surface_mesh::Halfedge_index
- Surface_mesh::Face_index
- Surface_mesh::Edge_index
這些class是基本圖元個體的封裝喜鼓，這樣做的目的是為了保證類型安全衔肢。它們默認是可構(gòu)造的膀懈，因此可能會產(chǎn)生一些無效的元素谨垃。新的元素可以通過一系列不包括連通性的低級函數(shù)向surface mesh這個類添加或者刪除刘陶。一個例外是Surface_mesh::add_face()匙隔，它嘗試向網(wǎng)格（由一系列頂點定義）中添加一個新面，如果操作在拓撲上無效撼短，則失敗挺勿。
typedef Surface_mesh<Point> Mesh;
Mesh m;
Mesh::Vertex_index u = m.add_vertex(Point(0,1,0));
Mesh::Vertex_index v = m.add_vertex(Point(0,0,0));
Mesh::Vertex_index w = m.add_vertex(Point(1,0,0));
m.add_face(u, v, w);
正如Surface_mesh是基于索引的(index based)不瓶，Vertex_index，Halfedge_index蚊丐，Edge_index和Face_index沒有成員函數(shù)來訪問連接性或?qū)傩晕醪巍?a target="_blank">Surface_mesh中創(chuàng)建的函數(shù)必須有獲取這些信息的功能。
2 連通性（connectivity）
surface mesh是一種能夠保持頂點麦备，邊和面的入射信息的孽椰，以邊為核心的數(shù)據(jù)結(jié)構(gòu)。
每個邊由兩個方向相反的半邊表示泥兰，每個半邊均存儲對入射面和入射頂點的引用弄屡，此外，它還存儲對入射面的下一個和上一個入射半邊的引用鞋诗。
其實說白了，surface mesh有一個半邊結(jié)構(gòu)的表達方式：對于一個半邊h它有以下這樣幾個導航的表達方式：Surface_mesh::opposite()削彬，Surface_mesh::next()全庸，Surface_mesh::prev()，Surface_mesh::target()融痛，和Surface_mesh::face()和半邊數(shù)據(jù)結(jié)構(gòu)是差不多的壶笼。
3 范圍和迭代器（range and iterators）
Surface_mesh提供迭代器范圍以枚舉所有頂點，半邊雁刷，邊和面覆劈。它提供的成員函數(shù)返回與Boost.Range庫兼容的元素范圍。
來自官方文檔的示例,演示如何從范圍中獲取迭代器類型沛励，獲得begin和end迭代器的替代方法以及基于范圍(range for c++11)的循環(huán)的替代方法责语。
#include <vector>
#include <boost/foreach.hpp>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
int main()
{
Mesh m;
// u x
// +------------+
// | |
// | f |
// | |
// +------------+
// v w
// Add the points as vertices
vertex_descriptor u = m.add_vertex(K::Point_3(0,1,0));
vertex_descriptor v = m.add_vertex(K::Point_3(0,0,0));
vertex_descriptor w = m.add_vertex(K::Point_3(1,0,0));
vertex_descriptor x = m.add_vertex(K::Point_3(1,1,0));
/* face_descriptor f = */ m.add_face(u,v,w,x);
{
std::cout << "all vertices " << std::endl;
// The vertex iterator type is a nested type of the Vertex_range
Mesh::Vertex_range::iterator vb, ve;
Mesh::Vertex_range r = m.vertices();
// The iterators can be accessed through the C++ range API
vb = r.begin();
ve = r.end();
// or the boost Range API
vb = boost::begin(r);
ve = boost::end(r);
// or with boost::tie, as the CGAL range derives from std::pair
for(boost::tie(vb, ve) = m.vertices(); vb != ve; ++vb){
std::cout << *vb << std::endl;
}
// Instead of the classical for loop one can use
// the boost macro for a range
BOOST_FOREACH(vertex_descriptor vd, m.vertices()){
std::cout << vd << std::endl;
}
// or the C++11 for loop. Note that there is a ':' and not a ',' as in BOOST_FOREACH
#ifndef CGAL_CFG_NO_CPP0X_RANGE_BASED_FOR
for(vertex_descriptor vd : m.vertices()){
std::cout << vd << std::endl;
}
#endif
}
return 0;
}
4 循環(huán)器（circulators）
CGAL和Boost Graph Library中提供了圍繞面和頂點的循環(huán)器作為模板類。
圍繞面的循環(huán)器基本上會進行調(diào)用Surface_mesh::next()目派，以從該面的逆時針方向從半邊變?yōu)榘脒吚ず颍⑶胰∠脮r返回半邊或入射頂點或相對面。
- CGAL::Halfedge_around_face_circulator<Mesh>
- CGAL::Vertex_around_face_circulator<Mesh>
- CGAL::Face_around_face_circulator<Mesh>
圍繞目標邊的頂點的循環(huán)器基本上會進行調(diào)用Surface_mesh::opposite(Surface_mesh::next())企蹭，以使圍繞同一目標點的順時針方向從半邊變?yōu)榘脒叀?/p>
- CGAL::Halfedge_around_target_circulator<Mesh>
- CGAL::Vertex_around_target_circulator<Mesh>
- CGAL::Face_around_target_circulator<Mesh>
example:
下面的示例演示如何枚舉給定半邊目標周圍的頂點白筹。第二個循環(huán)表明智末，每種循環(huán)器類型都帶有一個等效的迭代器和一個用于創(chuàng)建迭代器范圍的自由函數(shù)
#include <vector>
#include <boost/foreach.hpp>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
int main()
{
Mesh m;
// u x
// +------------+
// | |
// | |
// | f |
// | |
// | |
// +------------+
// v w
// Add the points as vertices
vertex_descriptor u = m.add_vertex(K::Point_3(0,1,0));
vertex_descriptor v = m.add_vertex(K::Point_3(0,0,0));
vertex_descriptor w = m.add_vertex(K::Point_3(1,0,0));
vertex_descriptor x = m.add_vertex(K::Point_3(1,1,0));
face_descriptor f = m.add_face(u,v,w,x);
{
std::cout << "vertices around vertex " << v << std::endl;
CGAL::Vertex_around_target_circulator<Mesh> vbegin(m.halfedge(v),m), done(vbegin);
do {
std::cout << *vbegin++ << std::endl;
} while(vbegin != done);
}
{
std::cout << "vertices around face " << f << std::endl;
CGAL::Vertex_around_face_iterator<Mesh> vbegin, vend;
for(boost::tie(vbegin, vend) = vertices_around_face(m.halfedge(f), m);
vbegin != vend;
++vbegin){
std::cout << *vbegin << std::endl;
}
}
// or the same again, but directly with a range based loop
BOOST_FOREACH(vertex_descriptor vd,vertices_around_face(m.halfedge(f), m)){
std::cout << vd << std::endl;
}
return 0;
}
5 屬性（properties）
Surface_mesh提供一種實時為頂點，半邊徒河，邊和面指定新屬性的機制系馆。給定屬性的所有值都存儲為連續(xù)的內(nèi)存塊。每當將鍵類型的新元素添加到數(shù)據(jù)結(jié)構(gòu)中或Surface_mesh::collect_garbage()執(zhí)行功能時虚青，對屬性的引用都將無效它呀。元素的屬性在刪除后將繼續(xù)存在。嘗試通過無效的元素訪問屬性將導致未定義的行為棒厘。
默認情況下纵穿，會維護一個屬性"v:point"。通過將新點添加到數(shù)據(jù)結(jié)構(gòu)時奢人，必須提供此屬性的值Surface_mesh::add_vertex()谓媒。可以使用Surface_mesh::points()或直接訪問該屬性`Surface_mesh::point(Surface_mesh::Vertex_index v)何乎。
當元素被刪除時句惯，它僅被標記為已刪除，并且在Surface_mesh::collect_garbage()被調(diào)用時被真正刪除支救。垃圾回收也確實會刪除這些元素的屬性抢野。
連接性也存儲在屬性中，即名為“ v：connectivity”各墨，“ h：connectivity”和“ f：connectivity”的屬性指孤。對于已刪除元素的標記，它非常相似贬堵，其中有“ v：removed”恃轩，“ e：removed”和“ f：removed”。
example：
#include <string>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <boost/foreach.hpp>
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
int main()
{
Mesh m;
vertex_descriptor v0 = m.add_vertex(K::Point_3(0,2,0));
vertex_descriptor v1 = m.add_vertex(K::Point_3(2,2,0));
vertex_descriptor v2 = m.add_vertex(K::Point_3(0,0,0));
vertex_descriptor v3 = m.add_vertex(K::Point_3(2,0,0));
vertex_descriptor v4 = m.add_vertex(K::Point_3(1,1,0));
m.add_face(v3, v1, v4);
m.add_face(v0, v4, v1);
m.add_face(v0, v2, v4);
m.add_face(v2, v3, v4);
// give each vertex a name, the default is empty
Mesh::Property_map<vertex_descriptor,std::string> name;
bool created;
boost::tie(name, created) = m.add_property_map<vertex_descriptor,std::string>("v:name","");
assert(created);
// add some names to the vertices
name[v0] = "hello";
name[v2] = "world";
{
// You get an existing property, and created will be false
Mesh::Property_map<vertex_descriptor,std::string> name;
bool created;
boost::tie(name, created) = m.add_property_map<vertex_descriptor,std::string>("v:name", "");
assert(! created);
}
// You can't get a property that does not exist
Mesh::Property_map<face_descriptor,std::string> gnus;
bool found;
boost::tie(gnus, found) = m.property_map<face_descriptor,std::string>("v:gnus");
assert(! found);
// retrieve the point property for which exists a convenience function
Mesh::Property_map<vertex_descriptor, K::Point_3> location = m.points();
BOOST_FOREACH( vertex_descriptor vd, m.vertices()) {
std::cout << name[vd] << " @ " << location[vd] << std::endl;
}
std::vector<std::string> props = m.properties<vertex_descriptor>();
BOOST_FOREACH(std::string p, props){
std::cout << p << std::endl;
}
// delete the string property again
m.remove_property_map(name);
return 0;
}
