官方手册Chapter_3D_Polyhedral_Surface
作者：Lutz Kettner Introduced in 版本引入: CGAL 1.0
Depends on 依赖库: Halfedge Data Structures
BibTeX 文献版本: cgal:k-ps-17b
License 版权许可: GPL
Windows Demo 示例程序 : Polyhedron demo
Common Demo Dlls动态依赖库: dlls
简介：
- 三维空间中的多面体表面是由顶点、边、面以及他们之前的关联构成的。
- 组织的基础是半边数据结构，这个数据结构约束可描述的表面到定向二维流行上，包含有边界和无边界的。
- 如果表面封闭，我们称之为多面体。
介绍
多边体的表面是由点（vertices），线（edges），面（facets），入射关系（incidence relationship）表示的。
- 由于要用半边数据结构来储存这些组织结构，要求多边形表面是二维可定向流形（orientable 2-manifolds）
- 有没有边界倒是无所谓。如果这样的表面是封闭的，就称其为多面体（polyhedron）
定义
多边体的表面Polyhedron_3<PolyhedronTraits_3>的每一条边都是由2条方向相反的半边组成的，如下图：
- vertex表示空间中的点
- edge是两个端点（endpoint）之间的线段，一个线段被分成两个方向相反的半边
- facet是没有洞（hole）的多边形平面
- facet由一串有顺序的循环的半边定义的，这些半边是该面的边缘
- 多边形表面是可以有洞的，由于每一个facet都不准有洞，每一个facet至少需要两个facet和它相邻
洞（hole）周围的半边被叫做border halfedge
- border halfedge是没有incident facet的
- 一条edge是border edge当且仅当它的其中一条halfedges是border halfedges
- 一个表面如果不含border halfedges，那它就是封闭的。一个封闭的表面的是一个多面体在三维空间中的表现
人为规定
- 从多面体的外部观察，facet是由逆时针方向排列的半边表示的
- 点（vertices）周围的halfedges是顺时针排列的
- facets的法向量是朝外的（右手定律）
二维定向流形是指
- 每个点的周围既不和disc拓扑等价也不和half disc拓扑等价（either homeomorphic to a disc or to a half disc），除非（except for vertices where many holes and surfaces with boundary can join）
- 此外，最小的代表表面如三角形和四面体，要避免自交（self intersection）
- 在欧拉操作（Euler operations）下，二维可定向流形的边界表达是封闭的（关于欧拉操作的解释，移步这里）
Polyhedron_3<PolyhedronTraits_3>只实现了欧拉操作下的多面体表面的组合完整性（combinatorial integrity）判定，而没有考虑点的坐标或者其他几何信息。Polyhedron_3<PolyhedronTraits_3> 既能够表达多面体表面，又能够表达多面体。我们将接口设计成了可以忽略border edge，所以用户不需要考虑目标网格是多面体表面还是多面体，统一将该网格当做多面体去操作就行了。
例子
多面体表面的实现用到了灵活性很高的半边数据结构。灵活性方面的例程可以参考本文的第五部分Extending Vertices, Halfedges, and Facets，和专门介绍半边结构的章节Section Examples
读接下来的例子之前你不需要懂得刚刚给出的两个链接中的内容。
创建一个多面体
第一个例子是如何创建一个多面体，它的traits class是kernel。
//File Polyhedron/polyhedron_prog_simple.cpp#include <CGAL/Simple_cartesian.h>#include <CGAL/Polyhedron_3.h>typedef CGAL::Simple_cartesian<double> Kernel;typedef CGAL::Polyhedron_3<Kernel> Polyhedron;typedef Polyhedron::Halfedge_handle Halfedge_handle;int main() {//创造了一个四面体Polyhedron P;//取四面体其中一条半边，将这个半边的引用存储在该四面体的Halfedge_handle中Halfedge_handle h = P.make_tetrahedron();//检测了一个halfedge是不是指向一个四面体。该例子检测了和halfedge h相连的部分，而不是整个多边形表面整体。if ( P.is_tetrahedron(h))return 0;return 1;}
- handles，或称trivial iterators。能存放半边，点，面的引用，以便于后续使用
- 用来枚举半边的type叫Halfedge_iterator type
- 这样的iterator type可以用在所有要求有handle的地方
- 同时提供了多面体的Halfedgeconst_handle和Halfedge_const_iterator，还有其他类似的handles和iterators，用Vertex和Facet_做前缀。
- 这个例子只适用于combinatorial层面上的多面体表面。
带几何信息的vertex例子
该程序的输出内容//File Polyhedron/polyhedron_prog_tetra.cpp #include <CGAL/Simple_cartesian.h> #include <CGAL/Polyhedron_3.h> #include <iostream> typedef CGAL::Simple_cartesian<double> Kernel; typedef Kernel::Point_3 Point_3; typedef CGAL::Polyhedron_3<Kernel> Polyhedron; typedef Polyhedron::Vertex_iterator Vertex_iterator; int main() { Point_3 p( 1.0, 0.0, 0.0); Point_3 q( 0.0, 1.0, 0.0); Point_3 r( 0.0, 0.0, 1.0); Point_3 s( 0.0, 0.0, 0.0); Polyhedron P; //4个点的坐标值作为参数传递给构造函数 P.make_tetrahedron( p, q, r, s); CGAL::set_ascii_mode(std::cout); //展示了vertex iterator的用法和如何访问vertices中的点 for (Vertex_iterator v = P.vertices_begin(); v != P.vertices_end(); ++v) //注意v->point()这个访问接口 std::cout << v->point() << std::endl; return 0; }1 0 0 0 1 0 0 0 1 0 0 0
同理，只要给出相应的handle或iterator，所有存储在vertex, halfedge, facet的信息都可以通过成员函数访问到
比如，有了一个halfedge的handle h
- 我们能写
h->next()来得到下一个halfedge的handle h->opposite()得到对面那条半边的handleh->vertex()能得到h的入点
多面体提供了一个便捷的iterator。
使用std::copy 和 ostream iterator adaptor，以上程序中的循环可以简写成如下一句话：
std::copy(
P.points_begin(), P.points_end(),
std::ostream_iterator<Point_3>(std::cout,"\n")
);
仿射变换
仿射变化A可以当做一个functor，用来变化点的位置。
假设我们只需要多面体P中点的坐标值来进行变换，std::transform可以做这个工作：
std::transform( P.points_begin(), P.points_end(), P.points_begin(), A);
计算平面方程
Polyhedral Surface能给每一个facet存储平面方程。但是，它没有提供一个函数来计算平面方程。
这个例子计算了多面体表面的平面方程，它的实现在函数compute_plane_equations()里
- 计算精不精确和facets的形状（凸包/不凸包）都会影响算法的选择
- 我们假设要求严格的凸facets与精确计算
这个例子中用了齐次整数坐标，程序的输出是四面体的4个平面方程
File Polyhedron/polyhedron_prog_planes.cpp
#include <CGAL/Homogeneous.h>
#include <CGAL/Polyhedron_3.h>
#include <iostream>
#include <algorithm>
//平面方程
struct Plane_equation {
template <class Facet>
typename Facet::Plane_3 operator()( Facet& f) {
typename Facet::Halfedge_handle h = f.halfedge();
typedef typename Facet::Plane_3 Plane;
return Plane( h->vertex()->point(),
h->next()->vertex()->point(),
h->next()->next()->vertex()->point());
}
};
typedef CGAL::Homogeneous<int> Kernel;
typedef Kernel::Point_3 Point_3;
typedef Kernel::Plane_3 Plane_3;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
int main() {
Point_3 p( 1, 0, 0);
Point_3 q( 0, 1, 0);
Point_3 r( 0, 0, 1);
Point_3 s( 0, 0, 0);
//根据四个点创建一个四面体
Polyhedron P;
P.make_tetrahedron( p, q, r, s);
//遍历每个Face，计算Face所在平面，并存放在P中
std::transform(
P.facets_begin(), P.facets_end(), //遍历每个Face
P.planes_begin(), //把结果放入planes中
Plane_equation() //将每一个Face丢到Plane_equation()中计算
//得到的结果放到P.planes_begin()迭代器中
);
CGAL::set_pretty_mode( std::cout);
//循环输出平面
std::copy( P.planes_begin(), P.planes_end(),
std::ostream_iterator<Plane_3>( std::cout, "\n"));
return 0;
}
用vector取代list
polyhedron类其实有4个参数，其中3个是有默认值的。
在下面这个例子里我们会显式地用到前三个默认参数值，第四个参数可以忽略，因为第四个参数是容器类的标准allocator。polyhedron的定义如下：
typedef CGAL::Polyhedron_3<Traits, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_default> Polyhedron;
//第一个参数Traits，是Polyhedron_3需要使用到的萃取器
//第二个参数Polyhedron_items_3类，它包含了vertices, edges, facets所用的类型
//第三个参数HalfedgeDS_default类，其定义了list型的半边数据结构表示法
另外一种是vector型的半边数据结构表示法
- 可以利用vector提供对多面体表面元素的随机访问，空间上的效率也更高，缺点是不能随意删除这些元素
- 使用list能实现随意的删除，但是只支持双向的iterator所以在空间效率上表现不佳
接下来的例子创建了一个四面体，它的点是用vector来表示的
- vector型的表示法能自动修改容量
- 在修改容量是，所有的handles，iterators和circulators都失效了，要想更新这些组件是需要时间的，所以我们建议使用注释中推荐的备用构造函数（
Polyhedron P(4,12,4);），留出足够多的空间 - 请注意，是polyhedron，而不是半边数据结构引发的resize操作，因为resize操作要求一些先决条件，比如有效入射关系，而这些先决条件只有polyhedron才能保证
//File Polyhedron/polyhedron_prog_vector.cpp #include <CGAL/Simple_cartesian.h> #include <CGAL/HalfedgeDS_vector.h> #include <CGAL/Polyhedron_3.h> #include <iostream> typedef CGAL::Simple_cartesian<double> Kernel; typedef Kernel::Point_3 Point_3; typedef CGAL::Polyhedron_3< Kernel, CGAL::Polyhedron_items_3, CGAL::HalfedgeDS_vector> Polyhedron; int main() { Point_3 p( 1.0, 0.0, 0.0); Point_3 q( 0.0, 1.0, 0.0); Point_3 r( 0.0, 0.0, 1.0); Point_3 s( 0.0, 0.0, 0.0); Polyhedron P; //备用构造函数: Polyhedron P(4,12,4); P.make_tetrahedron( p, q, r, s); CGAL::set_ascii_mode( std::cout); std::copy( P.points_begin(), P.points_end(), std::ostream_iterator<Point_3>( std::cout, "\n")); return 0; }
写入OFF文件
我们创建一个四面体，然后用std::cout将其写入OFF文件。
- 这个例子使用了STL algorithms（
std::copy, std::distance），STLstd::ostream_iterator, 和 CGAL circulators
多面体表面提供了circulators来遍历逆时针排列的facet的半边循环序列，或者顺时针排列的vertex周围的半边循环序列。
- 然而，在输出facet的内循环中，对vertex序号的计算不建议使用std::distance函数，因为它会花费线性的时间来费随机访问的iterator，这将导致二次方的运行时间
- 要减少运行时间，vertex的序号需要分开来存储，并且在写入facets之前只能计算一次。为了达到这种效果，vertex序号可以存储在hash结构中。详情见下面的File I/O章节。
//File Polyhedron/polyhedron_prog_off.cpp #include <CGAL/Simple_cartesian.h> #include <CGAL/Polyhedron_3.h> #include <iostream> typedef CGAL::Simple_cartesian<double> Kernel; typedef Kernel::Point_3 Point_3; typedef CGAL::Polyhedron_3<Kernel> Polyhedron; typedef Polyhedron::Facet_iterator Facet_iterator; typedef Polyhedron::Halfedge_around_facet_circulator Halfedge_facet_circulator; int main() { Point_3 p( 0.0, 0.0, 0.0); Point_3 q( 1.0, 0.0, 0.0); Point_3 r( 0.0, 1.0, 0.0); Point_3 s( 0.0, 0.0, 1.0); Polyhedron P; P.make_tetrahedron( p, q, r, s); // Write polyhedron in Object File Format (OFF). CGAL::set_ascii_mode( std::cout); std::cout << "OFF" << std::endl << P.size_of_vertices() << ' ' << P.size_of_facets() << " 0" << std::endl; std::copy( P.points_begin(), P.points_end(), std::ostream_iterator<Point_3>( std::cout, "\n")); for ( Facet_iterator i = P.facets_begin(); i != P.facets_end(); ++i) { Halfedge_facet_circulator j = i->facet_begin(); // Facets in polyhedral surfaces are at least triangles. CGAL_assertion( CGAL::circulator_size(j) >= 3); std::cout << CGAL::circulator_size(j) << ' '; do { std::cout << ' ' << std::distance(P.vertices_begin(), j->vertex()); } while ( ++j != i->facet_begin()); std::cout << std::endl; } return 0; }
用欧拉操作创建立方体
欧拉操作是修改多面体表面的一个很自然的方法
- 我们提供了一系列操作：
split_facet()、join_facet()、split_vertex()、join_vertex()、split_loop()、join_loop()。这6个基本操作的组合可以构成其他操作。比如我们已经帮您实现好了的运算符split_edge() - 此外，我们还提供了作用在border edges上的运算符，比如删除或者制造洞（holes）。
接下来的例子就是使用了一个能让单位立方体成为多面体表面的函数。为了记录创建立方体过程中的不同步骤，我们画了一个草图来配合代码进行说明
//File Polyhedron/polyhedron_prog_cube.cpp
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <iostream>
template <class Poly>
typename Poly::Halfedge_handle make_cube_3( Poly& P) {
// appends a cube of size [0,1]^3 to the polyhedron P.
CGAL_precondition( P.is_valid());
typedef typename Poly::Point_3 Point;
typedef typename Poly::Halfedge_handle Halfedge_handle;
Halfedge_handle h = P.make_tetrahedron( Point( 1, 0, 0),
Point( 0, 0, 1),
Point( 0, 0, 0),
Point( 0, 1, 0));
Halfedge_handle g = h->next()->opposite()->next(); // Fig. (a)
P.split_edge( h->next());
P.split_edge( g->next());
P.split_edge( g); // Fig. (b)
h->next()->vertex()->point() = Point( 1, 0, 1);
g->next()->vertex()->point() = Point( 0, 1, 1);
g->opposite()->vertex()->point() = Point( 1, 1, 0); // Fig. (c)
Halfedge_handle f = P.split_facet( g->next(),
g->next()->next()->next()); // Fig. (d)
Halfedge_handle e = P.split_edge( f);
e->vertex()->point() = Point( 1, 1, 1); // Fig. (e)
P.split_facet( e, f->next()->next()); // Fig. (f)
CGAL_postcondition( P.is_valid());
return h;
}
typedef CGAL::Simple_cartesian<double> Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
typedef Polyhedron::Halfedge_handle Halfedge_handle;
int main() {
Polyhedron P;
Halfedge_handle h = make_cube_3(P);
return (P.is_tetrahedron(h) ? 1 : 0);
}
File I/O
简单的多面体表面file I/O已经在库里面实现了
- 多面体表面的file I/O里面只是点的坐标值和拓扑结构
- 它没有存储平面方程或者用户添加的属性，比如颜色值
CGAL默认的输入输出文件格式是OFF（Object File Format），以.off作为后缀
- OFF文件可以用ASCII码写，也可以用二进制写
- 为了能选择用哪一种格式写off文件，CGAL有一个修改符作用于streams上，分别是
set_ascii_mode()和set_binary_mode() - 如果想写几行注释到输出文件，可以使用另一个修改符
set_pretty_mode()。output里面默认是没有注释的ASCII格式 - 由于OFF格式是默认格式，所以我们提供了相应的iostream的运算符
```cpp
include
template
template
其他支持的输出文件格式有：
- OpenInventor (.iv)
- VRML 1.0 and 2.0 (.wrl)
- Wavefront Advanced Visualizer object format (.obj). Geomview
CGAL也为这些格式配备了相应的stream运算符
```cpp
#include <CGAL/IO/Polyhedron_inventor_ostream.h>
#include <CGAL/IO/Polyhedron_VRML_1_ostream.h>
#include <CGAL/IO/Polyhedron_VRML_2_ostream.h>
#include <CGAL/IO/Polyhedron_geomview_ostream.h>
template <class PolyhedronTraits_3>
Inventor_ostream& operator<<( Inventor_ostream& out,
const CGAL::Polyhedron_3<PolyhedronTraits_3>& P);
template <class PolyhedronTraits_3>
VRML_1_ostream& operator<<( VRML_1_ostream& out,
const CGAL::Polyhedron_3<PolyhedronTraits_3>& P);
template <class PolyhedronTraits_3>
VRML_2_ostream& operator<<( VRML_2_ostream& out,
const CGAL::Polyhedron_3<PolyhedronTraits_3>& P);
template <class PolyhedronTraits_3>
Geomview_stream& operator<<( Geomview_stream& out,
const CGAL::Polyhedron_3<PolyhedronTraits_3>& P);
所有这些文件格式都有一个共性，就是它们都把平面表示成facets的集合
- 每个facet是一个指向vertices集合里的点的序号的list
- vertices被表达成坐标的三元组
I/O对这些文件有一些限制，比如已经在“1.介绍”里提到的，多面体表面必须只能是二维流形，没有孤立的顶点。
一些关于不同文件格式的例程可以在examples/Polyhedron_IO/ 和 demo/Polyhedron_IO/下面找到。下面我们展示一个转化off格式为VRML 1.0格式输出的例子。
//File Polyhedron_IO/polyhedron2vrml.cpp
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/IO/Polyhedron_VRML_1_ostream.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
int main() {
Polyhedron P;
std::cin >> P;
CGAL::VRML_1_ostream out(std::cout);
out << P;
return ( std::cin && std::cout) ? 0 : 1;
}
对Vertices, Halfedges, Facets进行扩展（挂接属性）
在上面的例子中我们已经看过如何修改默认的半边数据结构从list型表示法变成vector型表示法
typedef CGAL::Polyhedron_3<Traits,
CGAL::Polyhedron_items_3,
CGAL::HalfedgeDS_default> Polyhedron;
我们现在要深究一下第二个参数Polyhedron_items_3，这个参数制定了哪种vertex, halfedge, facet被使用了
- Polyhedron_items_3的实现有点像嵌套的包装类模板
- 简单来说，就是Polyhedron_items_3中局部定义的typedef，它们定义了Vertex, the Halfedge, Face的类型
注意我们用face而不是facet，因为face是在半边数据结构中用到的概念，只有最高层级的多面体表面使用facet来代替face作为别名
class Polyhedron_items_3 { public: template <class Refs, class Traits> struct Vertex_wrapper { typedef typename Traits::Point_3 Point; typedef CGAL::HalfedgeDS_vertex_base<Refs, CGAL::Tag_true, Point> Vertex; }; template < class Refs, class Traits> struct Halfedge_wrapper { typedef CGAL::HalfedgeDS_halfedge_base<Refs> Halfedge; }; template < class Refs, class Traits> struct Face_wrapper { typedef typename Traits::Plane_3 Plane; typedef CGAL::HalfedgeDS_face_base<Refs, CGAL::Tag_true, Plane> Face; }; };如果我们去查参考手册里这三个typedef中类的定义，我们会发现默认的多面体使用了所有支持的入射，vertex类中一个点，face类中一个平面方程。
包装类有两个模板参数：Refs（下文再细谈）
- Traits是几何特征类，它提供了多面体表面的点的类型和平面方程的类型
用这个例子的代码我们能写我们自己的items类
- 如果我们只是想要改动一个类，假设我们的face结构里不想要平面方程属性，而是想要颜色属性
- 为了简化vertex, halfedge, face类的创建，通常都会建议在已有的基类上派生。即使基类没有任何数据，这种方法还是能很方便的使你定义新类型
所以，我们从基类开始派生，如果有必要就重复强制性构造函数（一般在vertex类中需要，在face类中不需要），并且加入颜色变量。
template <class Refs> struct My_face : public CGAL::HalfedgeDS_face_base<Refs> { CGAL::Color color; };新的items从旧的items上派生出来，包含face typedef的warpper（包装类）也得到了重载。注意wrapper的名字和它的模板参数是固定的，它们不能被修改。
struct My_items : public CGAL::Polyhedron_items_3 { template <class Refs, class Traits> struct Face_wrapper { typedef My_face<Refs> Face; }; };现在可以使用自己定义的新items类了
我们新的face类可以用在半边数据结构中，颜色属性也在Polyhedron_3::Facet中能访问
- 我们在局部定义的face typedef My_face并不是Polyhedron_3::Facet，而是派生于Polyhedron_3::Facet上的派生类
- 所以，除了构造函数，其他在局部face type中存放的参数都能被Polyhedron_::Facet类型访问到（基类指针或者引用能指向派生类）
- 更多半边数据结构的细节，可以参考Halfedge Data Structures章节
完整代码
//File Polyhedron/polyhedron_prog_color.cpp
#include <CGAL/Simple_cartesian.h>
#include <CGAL/IO/Color.h>
#include <CGAL/Polyhedron_3.h>
// A face type with a color member variable.
template <class Refs>
struct My_face : public CGAL::HalfedgeDS_face_base<Refs> {
CGAL::Color color;
};
// An items type using my face.
struct My_items : public CGAL::Polyhedron_items_3 {
template <class Refs, class Traits>
struct Face_wrapper {
typedef My_face<Refs> Face;
};
};
typedef CGAL::Simple_cartesian<double> Kernel;
typedef CGAL::Polyhedron_3<Kernel, My_items> Polyhedron;
typedef Polyhedron::Halfedge_handle Halfedge_handle;
int main() {
Polyhedron P;
Halfedge_handle h = P.make_tetrahedron();
h->facet()->color = CGAL::RED;
return 0;
}
若有收获，就点个赞吧
0 人点赞
