作者:Mario Botsch, Daniel Sieger, Philipp Moeller, Andreas Fabri Introduced in 版本引入: CGAL 4.6 BibTeX 文献排版: cgal:bsmf-sm-17b
License 版本许可: GPL
这个包提供的表面网格类是对可表示多面体表面的半边数据结构的实现。
- 该包是半边数据结构和三维多面体表面的替代品,主要的区别在于他是基于索引的而不是基于指针的
- 并且向顶点、半边、边以及面上添加信息的机制很简单,并且可以在运行时使用而不是编译时使用
介绍
Surface_mesh基于半边结构实现,可用于表示多面体表面网格。
- 它是CGAL包Halfedge Data Structure和3D Polyhedral Surface的替代方案。主要区别在于它是基于索引的,而不是基于指针的。此外,将信息添加到顶点,半边,边和面的机制要简单得多,并且可以在运行时(runtime)完成,而不必在编译时完成。
- 因为数据结构使用整数索引作为顶点,半边,边和面的描述符,所以它的内存占用空间比基于64位指针的版本要低。由于索引是连续的,因此它们可以用作存储属性的向量的索引。
- 当元素被删除时,它们仅被标记为已删除,并且必须调用垃圾回收函数才能真正删除它们。
数据结构
Surface_mesh只存一份顶点的坐标,放在成员变量.point
中,半边、弧段、面等只存储下标
主类Surface_mesh提供了四个嵌套类,它们表示半边数据结构的基本元素:
- Surface_mesh::Vertex_index 顶点的下标
- Surface_mesh::Halfedge_index 半边的下标
- Surface_mesh::Face_index 面的下标
- Surface_mesh::Edge_index 边的下标
说明:
- 这些class是基本图元的封装,这样做的目的是为了保证类型安全。
- 它们默认是可构造的,因此可能会产生一些无效的元素。
新的元素可以通过一系列不包括连通性的低级函数向surface mesh这个类添加或者删除。一个例外是Surface_mesh::add_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是一种能够保持顶点,边和面的入射信息的,以边为核心的数据结构。
每个边由两个方向相反的半边表示,每个半边均存储对入射面和入射顶点的引用,此外,它还存储对入射面的下一个和上一个入射半边的引用。
- 其实说白了,surface mesh有一个半边结构的表达方式:对于一个半边h它有以下这样几个导航的表达方式:Surface_mesh::opposite(),Surface_mesh::next(),Surface_mesh::prev(),Surface_mesh::target(),和Surface_mesh::face()和半边数据结构是差不多的。
使用
构造
#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 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<<"由于方向错误,无法添加该面"<<std::endl;
f = m.add_face(u,x,v);
assert(f != Mesh::null_face());
}
return 0;
}
迭代器与范围访问
Surface_mesh提供迭代器,以枚举所有顶点,半边,边和面。它提供的成员函数返回与Boost.Range库兼容的元素范围。
来自官方文档的示例,演示如何从范围中获取迭代器类型,获得begin和end迭代器的替代方法以及基于范围(range for c++11)的循环的替代方法
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 CGALPoint3;
typedef CGAL::Surface_mesh<CGALPoint3> CGALMesh;