CGAL筆記之單元格復(fù)合體和多面體篇—曲面網(wǎng)格

• 0、前言
• 1、用法
• • 1、示例
• 2、連通性
• 3、范圍和迭代器
• • 3.1 示例
• 4、循環(huán)器
• • 1、示例
• 5、屬性
• • 1、示例
• 6、邊界
• 7、Surface Mesh和 BGL API
• • 1、示例
  • • 8、表面網(wǎng)格 I/O
• 9、內(nèi)存管理
• • 1、 示例
• 10、繪制Surface Mesh
• 11 實(shí)現(xiàn)細(xì)節(jié)

---

0、前言

類(lèi)Surface_mesh是半邊數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，可用于表示多面體表面。它是 CGAL 包Halfedge Data Structures和3D Polyhedral Surface的替代品。主要區(qū)別在于它是基于索引的，而不是基于指針的。此外，向頂點(diǎn)、半邊、邊和面添加信息的機(jī)制要簡(jiǎn)單得多，并且是在運(yùn)行時(shí)完成的，而不是在編譯時(shí)完成的。

因?yàn)閿?shù)據(jù)結(jié)構(gòu)使用整數(shù)索引作為頂點(diǎn)、半邊、邊和面的描述符，所以它比基于 64 位指針的版本具有更低的內(nèi)存占用。由于索引是連續(xù)的，因此它們可以用作存儲(chǔ)屬性的向量的索引。

當(dāng)元素被移除時(shí)，它們只是被標(biāo)記為已移除，必須調(diào)用垃圾回收函數(shù)才能真正移除它們。

該類(lèi)Surface_mesh可以通過(guò)其類(lèi)成員函數(shù)以及CGAL 包和 Boost Graph Library中描述的 BGL API 來(lái)使用，因?yàn)樗莄oncept的 MutableFaceGraph和FaceListGraph的模型。

1、用法

主類(lèi)Surface_mesh提供了四個(gè)嵌套類(lèi)，代表半邊數(shù)據(jù)結(jié)構(gòu)的基本元素：

• Surface_mesh::Vertex_index
• Surface_mesh::Halfedge_index
• Surface_mesh::Face_index
• Surface_mesh::Edge_index

這些類(lèi)型只是整數(shù)的包裝器，它們的主要目的是保證類(lèi)型安全。它們是默認(rèn)可構(gòu)造的，這會(huì)產(chǎn)生無(wú)效元素。Surface_mesh可以通過(guò)一組不保持連接性的低級(jí)函數(shù)添加和刪除新元素。一個(gè)例外是Surface_mesh::add_face()，它嘗試向網(wǎng)格（由一系列頂點(diǎn)定義）添加一個(gè)新面，如果該操作在拓?fù)渖蠠o(wú)效則失敗。在這種情況下，返回的Face_index是Surface_mesh::null_face()。

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與基于索引的Vertex_index、Halfedge_index、Edge_index和Face_index一樣，沒(méi)有成員函數(shù)來(lái)訪(fǎng)問(wèn)連通性或?qū)傩浴urface_mesh必須使用創(chuàng)建它們的實(shí)例的函數(shù)來(lái)獲取此信息。

1、示例

下面的示例展示了如何Surface_mesh通過(guò)添加 2 個(gè)面來(lái)創(chuàng)建一個(gè)非常簡(jiǎn)單的網(wǎng)格，以及如何檢查面是否已正確添加到網(wǎng)格中。

#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;// Add the points as verticesvertex_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,1,0));vertex_descriptor x = m.add_vertex(K::Point_3(1,0,0));m.add_face(u,v,w);face_descriptor f = m.add_face(u,v,x);if(f == Mesh::null_face()){std::cerr<<"The face could not be added because of an orientation error."<<std::endl;f = m.add_face(u,x,v);assert(f != Mesh::null_face());}return 0; }

2、連通性

表面網(wǎng)格是一種以邊為中心的數(shù)據(jù)結(jié)構(gòu)，能夠維護(hù)頂點(diǎn)、邊和面的關(guān)聯(lián)信息。每條邊由兩個(gè)方向相反的半邊表示。每個(gè)半邊存儲(chǔ)對(duì)入射面和入射頂點(diǎn)的引用。此外，它還會(huì)將下一個(gè)和上一個(gè)半邊事件的引用存儲(chǔ)到其事件面。對(duì)于每個(gè)面和每個(gè)頂點(diǎn)，都會(huì)存儲(chǔ)一個(gè)關(guān)聯(lián)的半邊。半邊不存儲(chǔ)相對(duì)半邊的索引，因?yàn)镾urface_mesh在內(nèi)存中連續(xù)存儲(chǔ)相對(duì)半邊。

下圖說(shuō)明了允許在表面網(wǎng)格中導(dǎo)航的函數(shù)：Surface_mesh::opposite()、Surface_mesh::next()、Surface_mesh::prev()、Surface_mesh::target()和Surface_mesh::face()。此外，這些函數(shù)Surface_mesh::halfedge()允許獲得與頂點(diǎn)和面相關(guān)聯(lián)的半邊。或者，可以使用包CGAL 和 Boost Graph Library中定義的具有相同名稱(chēng)的函數(shù)。

入射到面的半邊形成一個(gè)循環(huán)。根據(jù)我們從表面的哪一側(cè)看，半邊的序列似乎是順時(shí)針或逆時(shí)針?lè)较颉．?dāng)在本手冊(cè)中我們談到遍歷的方向時(shí)，我們會(huì)看到表面周?chē)陌脒吺悄鏁r(shí)針?lè)较虻摹?/p>

連通性不允許表示有孔的面。

3、范圍和迭代器

Surface_mesh提供迭代器范圍以枚舉所有頂點(diǎn)、半邊、邊和面。它提供返回與Boost.Range庫(kù)兼容的元素范圍的成員函數(shù)。

3.1 示例

以下示例顯示如何從范圍中獲取迭代器類(lèi)型、獲取開(kāi)始和結(jié)束迭代器的備選方案以及基于范圍的循環(huán)的備選方案。

#include <vector> #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 verticesvertex_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_rangeMesh::Vertex_range::iterator vb, ve;Mesh::Vertex_range r = m.vertices();// The iterators can be accessed through the C++ range APIvb = r.begin();ve = r.end();// or the boost Range APIvb = boost::begin(r);ve = boost::end(r);// or with boost::tie, as the CGAL range derives from std::pairfor(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 rangefor(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_FOREACHfor(vertex_descriptor vd : m.vertices()){std::cout << vd << std::endl;}}return 0; }

4、循環(huán)器

在 CGAL 包和 Boost Graph Library中，圍繞面和頂點(diǎn)的循環(huán)器作為類(lèi)模板提供。

圍繞面的循環(huán)器基本上是Surface_mesh::next()為了從 halfedge 到 halfedge 逆時(shí)針繞著面進(jìn)行調(diào)用，當(dāng)取消引用時(shí)返回 halfedge 或入射頂點(diǎn)或相反的面。

• CGAL::Halfedge_around_face_circulator<Mesh>
• CGAL::Vertex_around_face_circulator<Mesh>
• CGAL::Face_around_face_circulator<Mesh>

邊的目標(biāo)頂點(diǎn)周?chē)沫h(huán)行器基本上是Surface_mesh::opposite(Surface_mesh::next())為了圍繞同一目標(biāo)頂點(diǎn)從半邊順時(shí)針轉(zhuǎn)到半邊。

• CGAL::Halfedge_around_target_circulator<Mesh>
• CGAL::Vertex_around_target_circulator<Mesh>
• CGAL::Face_around_target_circulator<Mesh>

所有循環(huán)器模型BidirectionalCirculator。除此之外，它們還支持轉(zhuǎn)換為bool以更方便地檢查是否為空。

1、示例

以下示例顯示如何枚舉給定半邊的目標(biāo)周?chē)捻旤c(diǎn)。第二個(gè)循環(huán)顯示這些循環(huán)器類(lèi)型中的每一個(gè)都帶有一個(gè)等效的迭代器和一個(gè)創(chuàng)建迭代器范圍的自由函數(shù)。

#include <CGAL/Simple_cartesian.h> #include <CGAL/Surface_mesh.h> #include <vector> 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 verticesvertex_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 loopfor(vertex_descriptor vd : vertices_around_face(m.halfedge(f), m)){std::cout << vd << std::endl;}return 0; }

5、屬性

Surface_mesh提供了一種在運(yùn)行時(shí)為頂點(diǎn)、半邊、邊和面指定新屬性的機(jī)制。每個(gè)屬性都由一個(gè)字符串及其鍵類(lèi)型標(biāo)識(shí)。給定屬性的所有值都存儲(chǔ)為連續(xù)的內(nèi)存塊。每當(dāng)將鍵類(lèi)型的新元素添加到數(shù)據(jù)結(jié)構(gòu)或Surface_mesh::collect_garbage()執(zhí)行函數(shù)時(shí)，對(duì)屬性的引用就會(huì)失效。刪除元素后，元素的屬性將繼續(xù)存在。嘗試通過(guò)無(wú)效元素訪(fǎng)問(wèn)屬性將導(dǎo)致未定義的行為。

默認(rèn)保留一個(gè)屬性，即"v:point". 通過(guò) 向數(shù)據(jù)結(jié)構(gòu)添加新點(diǎn)時(shí)，必須提供此屬性的值Surface_mesh::add_vertex()。可以使用Surface_mesh::points()或直接訪(fǎng)問(wèn)該屬性Surface_mesh::point(Surface_mesh::Vertex_index v)。

當(dāng)一個(gè)元素被移除時(shí)，它只是被標(biāo)記為已移除，當(dāng)Surface_mesh::collect_garbage()被調(diào)用時(shí)它才真正被移除。垃圾回收也會(huì)真正去除這些元素的屬性。

連通性也存儲(chǔ)在屬性中，即名為“v:connectivity”、“h:connectivity”和“f:connectivity”的屬性。刪除元素的標(biāo)記非常相似，我們有“v:removed”、“e:removed”和“f:removed”。

提供了方便的功能來(lái)刪除用戶(hù)添加的屬性映射，無(wú)論是按索引類(lèi)型 ( Surface_mesh::remove_property_maps<I>()) 還是全部 ( Surface_mesh::remove_all_property_maps())。

要清除網(wǎng)格，您可以得到一個(gè)刪除了所有添加的屬性映射的網(wǎng)格 ( Surface_mesh::clear()) 或保留它們 ( Surface_mesh::clear_without_removing_property_maps())。請(qǐng)注意，在這兩種情況下，“v:point”屬性映射將被保留并且保持對(duì)它的引用是安全的。

1、示例

此示例說(shuō)明如何使用屬性系統(tǒng)的最常見(jiàn)功能。

#include <string> #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;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 emptyMesh::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 verticesname[v0] = "hello";name[v2] = "world";{// You get an existing property, and created will be falseMesh::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 existMesh::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 functionMesh::Property_map<vertex_descriptor, K::Point_3> location = m.points();for(vertex_descriptor vd : m.vertices()) {std::cout << name[vd] << " @ " << location[vd] << std::endl;}std::vector<std::string> props = m.properties<vertex_descriptor>();for(std::string p : props){std::cout << p << std::endl;}// delete the string property againm.remove_property_map(name);return 0; }

6、邊界

半邊存儲(chǔ)對(duì)面的引用，即它的入射面。一條半邊h在邊界上，如果它沒(méi)有入射面，即如果。如果一條邊的任何半邊在邊界上，則該邊在邊界上。如果頂點(diǎn)的任何關(guān)聯(lián)半邊在邊界上，則該頂點(diǎn)在邊界上。sm.face(h) == Surface_mesh::null_face()

一個(gè)頂點(diǎn)只有一個(gè)關(guān)聯(lián)的半邊。如果用戶(hù)注意關(guān)聯(lián)的半邊是邊界半邊，如果頂點(diǎn)在邊界上，則無(wú)需在函數(shù)中查看所有入射半邊以查找頂點(diǎn)is_border()。為了只檢查關(guān)聯(lián)的半邊是否在邊界上，Surface_mesh::is_border(Vertex_index v, bool check_all_incident_halfedges = true)必須使用調(diào)用函數(shù)check_all_incident_halfedges = false。

在應(yīng)用了可能使此屬性無(wú)效的操作后，用戶(hù)負(fù)責(zé)正確設(shè)置與頂點(diǎn)關(guān)聯(lián)的半邊。函數(shù)Surface_mesh::set_vertex_halfedge_to_border_halfedge(Vertex_index v)、Surface_mesh::set_vertex_halfedge_to_border_halfedge(Halfedge_index h)和分別為單個(gè)頂點(diǎn)v、面邊界上的所有頂點(diǎn)和表面網(wǎng)格的所有頂點(diǎn)hSurface_mesh::set_vertex_halfedge_to_border_halfedge()設(shè)置邊界半邊。

7、Surface Mesh和 BGL API

該類(lèi)是Boost Graph Library 中定義的Surface_mesh概念模型。這使得可以直接在表面網(wǎng)格上IncidenceGraph應(yīng)用諸如Dijkstra 最短路徑或Kruskal 最小生成樹(shù)等算法。

BGL API 的類(lèi)型和自由函數(shù)都有相似的類(lèi)型或成員函數(shù)，例如

BGLSurface_mesh評(píng)論

boost::graph_traits<G>::vertex_descriptor	Surface_mesh::Vertex_index
boost::graph_traits<G>::edge_descriptor	Surface_mesh::Edge_index
vertices(const G& g)	sm.vertices()
edges(const G& g)	sm.edges()
vd = source(ed,g)	vd = sm.source(ed)
na	n = sm.number_of_vertices()	計(jì)算未刪除的頂點(diǎn)并且沒(méi)有 BGL 等價(jià)物
n = num_vertices(g)	n = sm.number_of_vertices() + sm.number_of_removed_vertices()	計(jì)算已使用和已刪除的頂點(diǎn)，以便在使用的最大頂點(diǎn)索引上有一個(gè)上限

返回頂點(diǎn)數(shù)而不考慮刪除的頂點(diǎn)會(huì)更好，但這會(huì)與底層頂點(diǎn)/邊索引映射交互不良。[0,num_vertices(g))索引映射將不再落在許多算法中假定的范圍內(nèi)。

該類(lèi)也是包CGAL 和 Boost Graph Library 中定義的concept的Surface_mesh的模型。這個(gè)和concept類(lèi)型的 HalfedgeGraph類(lèi)似，通過(guò)引入半邊和面的概念以及圍繞面和頂點(diǎn)的半邊循環(huán)來(lái)改進(jìn) BGL 的圖形概念。同樣，有類(lèi)似的類(lèi)型和，例如：MutableFaceGraph和HalfedgeGraph

BGL表面網(wǎng)格

boost::graph_traits<G>::halfedge_descriptor	Surface_mesh::Halfedge_index
boost::graph_traits<G>::face_descriptor	Surface_mesh::Face_index
halfedges(const G& g)	sm.halfedges()
faces(const G& g)	sm.faces()
hd = next(hd, g)	hd = sm.next(hd)
hd = prev(hd, g)	hd = sm.prev(hd)
hd = opposite(hd,g)	hd = sm.opposite(hd)
hd = halfedge(vd,g)	hd = sm.halfedge(vd)
ETC。

CGAL包和 Boost Graph Library中描述的 BGL API使我們能夠編寫(xiě)在表面網(wǎng)格上運(yùn)行的幾何算法，適用于FaceGraph, 或的任何模型MutableFaceGraph。即表面網(wǎng)格簡(jiǎn)化、變形或分割算法適用于Surface_mesh和Polyhedron_3。

BGL 算法使用屬性映射將信息關(guān)聯(lián)到頂點(diǎn)和邊。一個(gè)重要的屬性是索引，一個(gè)圖的頂點(diǎn)0之間的整數(shù)。這允許算法創(chuàng)建適當(dāng)大小的向量以存儲(chǔ)每個(gè)頂點(diǎn)信息。例如，用于存儲(chǔ)在圖形遍歷期間是否已訪(fǎng)問(wèn)頂點(diǎn)的布爾值。num_vertices(g)``g

檢索圖的頂點(diǎn)索引屬性映射的 BGL 方法g是vipm = get(boost::vertex_index, g)，然后get(vipm, vd)為了檢索頂點(diǎn)描述符的索引vd，它是get(vertex_index, g, vd)直接獲取頂點(diǎn)索引。

1、示例

第一個(gè)示例表明我們可以直接在表面網(wǎng)格上應(yīng)用 Kruskal 的最小生成樹(shù)算法。

#include <CGAL/Simple_cartesian.h> #include <CGAL/Surface_mesh.h> #include <boost/graph/kruskal_min_spanning_tree.hpp> #include <iostream> #include <fstream> #include <list> typedef CGAL::Simple_cartesian<double> Kernel; typedef Kernel::Point_3 Point; typedef CGAL::Surface_mesh<Point> Mesh; typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor; typedef boost::graph_traits<Mesh>::vertex_iterator vertex_iterator; typedef boost::graph_traits<Mesh>::edge_descriptor edge_descriptor; void kruskal(const Mesh& sm) {// We use the default edge weight which is the squared length of the edgestd::list<edge_descriptor> mst;boost::kruskal_minimum_spanning_tree(sm,std::back_inserter(mst));std::cout << "#VRML V2.0 utf8\n""Shape {\n"" appearance Appearance {\n"" material Material { emissiveColor 1 0 0}}\n"" geometry\n"" IndexedLineSet {\n"" coord Coordinate {\n"" point [ \n";vertex_iterator vb,ve;for(boost::tie(vb, ve) = vertices(sm); vb!=ve; ++vb){std::cout << " " << sm.point(*vb) << "\n";}std::cout << " ]\n"" }\n"" coordIndex [\n";for(std::list<edge_descriptor>::iterator it = mst.begin(); it != mst.end(); ++it){edge_descriptor e = *it ;vertex_descriptor s = source(e,sm);vertex_descriptor t = target(e,sm);std::cout << " " << s << ", " << t << ", -1\n";}std::cout << "]\n"" }#IndexedLineSet\n""}# Shape\n"; } int main(int argc, char** argv) {Mesh sm;std::string fname = argc==1?CGAL::data_file_path("meshes/knot1.off"):argv[1];if(!CGAL::IO::read_polygon_mesh(fname, sm)){std::cerr << "Invalid input file." << std::endl;return EXIT_FAILURE;}kruskal(sm);return 0; }

第二個(gè)示例展示了我們?nèi)绾螌傩杂成溆糜谥T如 Prim 的最小生成樹(shù)之類(lèi)的算法。該算法在內(nèi)部也使用頂點(diǎn)索引屬性映射調(diào)用get(boost::vertex_index_t,sm)。對(duì)于這個(gè)類(lèi)，Surface_mesh這歸結(jié)為一個(gè)身份函數(shù)，因?yàn)轫旤c(diǎn)是索引。

#include <CGAL/Simple_cartesian.h> #include <CGAL/Surface_mesh.h> #include <iostream> #include <fstream> // workaround a bug in Boost-1.54 #include <CGAL/boost/graph/dijkstra_shortest_paths.h> #include <boost/graph/prim_minimum_spanning_tree.hpp> typedef CGAL::Simple_cartesian<double> Kernel; typedef Kernel::Point_3 Point; typedef CGAL::Surface_mesh<Point> Mesh; typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor; int main(int argc, char* argv[]) {Mesh sm;std::string fname = argc==1?CGAL::data_file_path("meshes/knot1.off"):argv[1];if(!CGAL::IO::read_polygon_mesh(fname, sm)){std::cerr << "Invalid input file." << std::endl;return EXIT_FAILURE;}Mesh::Property_map<vertex_descriptor,vertex_descriptor> predecessor;predecessor = sm.add_property_map<vertex_descriptor,vertex_descriptor>("v:predecessor").first;boost::prim_minimum_spanning_tree(sm, predecessor, boost::root_vertex(*vertices(sm).first));std::cout << "#VRML V2.0 utf8\n""DirectionalLight {\n""direction 0 -1 0\n""}\n""Shape {\n"" appearance Appearance {\n"" material Material { emissiveColor 1 0 0}}\n"" geometry\n"" IndexedLineSet {\n"" coord Coordinate {\n"" point [ \n";for(vertex_descriptor vd : vertices(sm)){std::cout << " " << sm.point(vd) << "\n";}std::cout << " ]\n"" }\n"" coordIndex [\n";for(vertex_descriptor vd : vertices(sm)){if(predecessor[vd]!=vd){std::cout << " " << std::size_t(vd) << ", " << std::size_t(predecessor[vd]) << ", -1\n";}}std::cout << "]\n"" }#IndexedLineSet\n""}# Shape\n";sm.remove_property_map(predecessor);return 0; }

8、表面網(wǎng)格 I/O

作為模型FaceGraph（請(qǐng)參閱部分曲面網(wǎng)格和 BGL API），CGAL::Surface_mesh可以使用多種不同的文件格式進(jìn)行讀取和寫(xiě)入。有關(guān)詳細(xì)信息，請(qǐng)參閱CGAL 和 Boost Graph Library包的I/O 函數(shù)以及多邊形網(wǎng)格處理包的I/O 函數(shù)。

此外，該包還提供來(lái)自CGAL 和 Boost Graph Library 中Surface_mesh包的 I/O 函數(shù)的特定重載。這允許直接從內(nèi)部屬性映射讀取/寫(xiě)入，有關(guān)更多信息，請(qǐng)參閱I/O 函數(shù)。

9、內(nèi)存管理

內(nèi)存管理是半自動(dòng)的。內(nèi)存隨著更多元素被添加到結(jié)構(gòu)中而增長(zhǎng)，但當(dāng)元素被移除時(shí)內(nèi)存不會(huì)減少。

當(dāng)您添加元素并且基礎(chǔ)向量的容量耗盡時(shí)，向量會(huì)重新分配內(nèi)存。由于描述符基本上是索引，因此它們?cè)谥匦路峙浜笠孟嗤脑亍?/p>

當(dāng)您刪除一個(gè)元素時(shí)，它只會(huì)被標(biāo)記為已刪除。在內(nèi)部，它被放在一個(gè)空閑列表中，當(dāng)您將元素添加到表面網(wǎng)格時(shí)，它們會(huì)從空閑列表中取出，以防它不為空。

對(duì)于所有元素，我們提供了一個(gè)函數(shù)來(lái)獲取已使用元素的數(shù)量，以及已使用和刪除元素的數(shù)量。對(duì)于頂點(diǎn)，函數(shù)分別是Surface_mesh::number_of_vertices()和Surface_mesh::number_of_removed_vertices()。num_vertices(const G&)第一個(gè)函數(shù)與BGL 包的免費(fèi)函數(shù)略有不同。由于 BGL 樣式算法使用元素的索引來(lái)訪(fǎng)問(wèn)臨時(shí)大小向量中的數(shù)據(jù)，因此num_vertices()此函數(shù)必須返回一個(gè)大于元素的最大索引的數(shù)字。

諸如Surface_mesh::Vertex_iterator僅枚舉未標(biāo)記為已刪除的元素的迭代器。

要真正縮小使用的內(nèi)存，Surface_mesh::collect_garbage()必須調(diào)用。垃圾收集還會(huì)壓縮與表面網(wǎng)格相關(guān)的屬性。

但是請(qǐng)注意，通過(guò)垃圾收集元素可以獲得新的索引。如果您保留頂點(diǎn)描述符，它們很可能不再引用正確的頂點(diǎn)。

1、 示例

#include <iostream> #include <CGAL/Simple_cartesian.h> #include <CGAL/Surface_mesh.h> typedef CGAL::Simple_cartesian<double> K; typedef CGAL::Surface_mesh<K::Point_3>網(wǎng)格； typedef Mesh::Vertex_index vertex_descriptor; 主函數(shù)() {網(wǎng)格米;Mesh::Vertex_index u;對(duì)于（無(wú)符號(hào) 整數(shù)i=0；i < 5；++i）{網(wǎng)格::頂點(diǎn)索引 v = m。add_vertex (K::Point_3(0,0,i+1));如果（i==2）你=v；}m.remove_vertex(u);std::cout << "插入 5 個(gè)頂點(diǎn)并移除 3 個(gè)頂點(diǎn)后\n"<< “#個(gè)頂點(diǎn)/#個(gè)頂點(diǎn)+#個(gè)刪除的頂點(diǎn)=”<< m.number_of_vertices()<< " / " << m.number_of_vertices() + m.number_of_removed_vertices() << std::endl;std::cout << "遍歷頂點(diǎn)\n" ;{for (vertex_descriptor vd : m.vertices()){std::cout << m.point(vd) << std::endl;}}// 被使用或被移除的狀態(tài)存儲(chǔ)在屬性映射中Mesh::Property_map<Mesh::Vertex_index,bool> 移除= m.property_map<Mesh::Vertex_index, bool >( "v:removed" ).first;std::cout << "\n遍歷頂點(diǎn)并刪除頂點(diǎn)\n"<< “#個(gè)頂點(diǎn)/#個(gè)頂點(diǎn)+#個(gè)刪除的頂點(diǎn)=”<< m.number_of_vertices()<< " / " << m.number_of_vertices() + m.number_of_removed_vertices() << std::endl;{unsigned int i = 0, end = m.number_of_vertices() + m.number_of_removed_vertices();對(duì)于( ; i < 結(jié)束; ++i) {頂點(diǎn)描述符 vh(i);assert(m.is_removed(vh) == removed[vh]);std::cout << m.point(vh) << ((m.is_removed(vh)) ? " R\n" : "\n" );}}m.collect_garbage();std::cout << "\n垃圾回收后\n"<< “#個(gè)頂點(diǎn)/#個(gè)頂點(diǎn)+#個(gè)刪除的頂點(diǎn)=”<< m.number_of_vertices()<< " / " << m.number_of_vertices() + m.number_of_removed_vertices() << std::endl; {unsigned int i = 0, end = m.number_of_vertices() + m.number_of_removed_vertices();對(duì)于( ; i < 結(jié)束; ++i) {頂點(diǎn)描述符 vh(i);std::cout << m.point(vh) << ((m.is_removed(vh)) ? " R\n" : "\n" );}}返回0； }

10、繪制Surface Mesh

可以通過(guò)調(diào)用CGAL::draw()來(lái)可視化表面網(wǎng)格，如以下示例所示。此函數(shù)打開(kāi)一個(gè)新窗口，顯示給定的表面網(wǎng)格。對(duì)該函數(shù)的調(diào)用是阻塞的，也就是說(shuō)，只要用戶(hù)關(guān)閉窗口，程序就會(huì)繼續(xù)。

#include <CGAL/Surface_mesh.h> #include <CGAL/draw_surface_mesh.h> #include <fstream> typedef CGAL::Simple_cartesian<double> Kernel; typedef Kernel::Point_3 Point; typedef CGAL::Surface_mesh<Point> Mesh; int main(int argc, char* argv[]) {const std::string filename = (argc>1) ? argv[1] : CGAL::data_file_path("meshes/elephant.off");Mesh sm;if(!CGAL::IO::read_polygon_mesh(filename, sm)){std::cerr << "Invalid input file." << std::endl;return EXIT_FAILURE;}CGAL::draw(sm);return EXIT_SUCCESS; }

此函數(shù)需要, 且僅在定義CGAL_Qt5宏時(shí)可用。CGAL_USE_BASIC_VIEWER與 cmake 目標(biāo)鏈接CGAL::CGAL_Basic_viewer將鏈接CGAL_Qt5并添加定義CGAL_USE_BASIC_VIEWER。

11 實(shí)現(xiàn)細(xì)節(jié)

作為我們選擇的索引的整數(shù)類(lèi)型boost::uint32_t。在 64 位操作系統(tǒng)上，它們只占指針大小的一半。他們?nèi)匀辉试S擁有 20 億個(gè)元素的網(wǎng)格。

我們用于std::vector存儲(chǔ)屬性。因此，通過(guò)訪(fǎng)問(wèn)屬性映射的第 0 個(gè)元素的地址，您可以訪(fǎng)問(wèn)底層原始數(shù)組。這可能很有用，例如將點(diǎn)數(shù)組傳遞給 OpenGL。

我們對(duì)刪除的元素使用*空閑列表。*這意味著當(dāng)一個(gè)頂點(diǎn)被移除并稍后add_vertex被調(diào)用時(shí)，被移除元素的內(nèi)存將被重用。這尤其意味著第 n 個(gè)插入的元素不一定具有索引n-1，并且在遍歷元素時(shí)它們不會(huì)按插入順序枚舉。

總結(jié)

以上是生活随笔為你收集整理的CGAL笔记之单元格复合体和多面体篇—曲面网格的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。