CGAL的3D多面体表面

本文介绍: 三维多面体表面 Poly h e d ron_3 由顶点 V、边 E、面 F 和它们之间的关联关系组成。每条边由两个方向相反的半边表示。用半边存储的关联关系如下图所示顶点表示空间中的点。边是两个端点之间的直线段。面是没有孔的平面多边形，可能是非凸多边形。面由沿其边界的半边的圆形序列定义。多面体表面本身可以有孔（至少有两个面围绕它，因为单个面不能有孔）。沿孔边界的半边称为边界半边，没有入射面。如果一条边的一条半边是边界半边，则该边是边界边。

1、介绍

三维多面体表面由顶点、边、面和它们之间的关联关系组成。其底层组织是一种半边数据结构，它限制了可表示的表面类为可定向的2-流形，有边界和无边界。如果表面是封闭的，我们称之为多面体，例如，见下面的锤头模型

多面体表面被实现为容器类，该容器类管理顶点、半边、面及其关联，并保持它们的组合完整性。它基于半边数据结构的高度灵活的设计。然而，即使不知道底层设计，也可以使用和理解多面体表面。

2、定义

三维多面体表面 Poly hed ron_3<Poly hed ron Tr ai ts _3&g t; 由顶点 V、边 E、面 F 和它们之间的关联关系组成。每条边由两个方向相反的半边表示。用半边存储的关联关系如下图所示

顶点表示空间中的点。边是两个端点之间的直线段。面是没有孔的平面多边形，可能是非凸多边形。面由沿其边界的半边的圆形序列定义。多面体表面本身可以有孔（至少有两个面围绕它，因为单个面不能有孔）。沿孔边界的半边称为边界半边，没有入射面。如果一条边的一条半边是边界半边，则该边是边界边。如果表面不包含边界半边，则表面是闭合的。闭合表面是三维多面体的边界表示。惯例是半边围绕面逆时针方向取向，从多面体的外部看。这意味着半边围绕顶点顺时针方向取向。由半边方向定义的面的实边概念扩展到具有边界边的多面体表面，尽管它们没有定义闭合对象。如果考虑面的法向量，法线指向外（遵循右手定则）。

这个定义的一个含义是多面体表面总是具有边界边缘的可定向和定向的2-流形，即多面体表面上每个点的邻域要么与圆盘同胚，要么与半圆盘同胚，除了多个孔连接的顶点。另一个含义是避免自交的最小可表示表面是三角形（对于具有边界边缘的多面体表面）或四面体（对于多面体）。可定向2-流形的边界表示在欧拉运算下是闭合的。它们通过在表面上创建或闭合孔的操作进行扩展。

除了关联关系之外，不允许其他交点。然而，在操作中不会自动验证这一点，因为自交点不容易有效地检查。 Polyhedron_3<Polyhedron Tr a i ts _3>只维护多面体表面的组合完整性（使用欧拉操作），不考虑点的坐标或任何其他几何信息。

Polyhedr on _3<Polyhedr on Tr a i ts _3> 可以表示多面体表面以及多面体。该接口的设计方式使得它很容易忽略边界边缘，并且只处理多面体。

3、I/O 文件

I/O当前仅考虑曲面的拓扑及其点坐标。它忽略可能的平面方程式或任何用户添加的属性，例如颜色。

CGAL中支持输出和输入的默认文件格式是对象文件格式（OFF），文件扩展名为.OFF。可以使用修饰符 set _pretty_mode（）在输出中允许（一些）结构化注释。否则，输出将没有注释。默认的书写方式是不带注释。由于此文件格式是默认格式，因此为其提供了i ostream 运算符。

所有这些文件格式都有一个共同点，它们将曲面表示为一组面。每个面都是一个指向一组顶点的索引列表。顶点表示为坐标三元组。多面体曲面 Polyhedron_3 的文件 I/O 对这些格式施加了某些限制。

4、顶点、半边和面的延申

多面体类模板实际上有四个参数，其中三个参数具有默认值。

Polyhedron_item s_3类包含用于顶点、边和镶嵌面的类型。Halfd edgeDS_default类定义了所使用的半边缘数据结构，在这种情况下，它是基于列表的表示。另一种选择是基于向量的表示。使用向量为多面体表面中的元素提供了随机访问，并且更节省空间，但元素不能被任意删除。使用列表允许任意删除，但只提供双向迭代器，而且空间效率较低。

如果保留容量不足以容纳创建的新项目，则基于矢量的表示会自动调整大小。调整所有句柄的大小后，迭代器和循环器将无效。它们在半边缘数据结构中的正确更新代价高昂，因此建议提前预留足够的空间。

请注意，触发调整大小操作的是多面体，而不是底层的半边数据结构，因为调整大小操作需要一些前提条件，例如有效的关联度，只有多面体才能保证。

欧拉算子是修改多面体曲面的自然方法。我们为多面体提供了一组操作：split_facet（）、join_facet。我们添加了更多方便的运算符，例如 split_edge（）。然而，它们可以使用上面的六个运算符来实现。此外，我们提供了更多的操作符来处理具有边界边的多面体曲面，例如，创建和删除孔。关于欧拉算子的定义和图示，我们参考参考手册。

在使用矢量而不是列表表示的部分示例中，我们已经了解了如何更改默认列表表示

typedef CGAL::Polyhedron_3< Traits,
CGAL::Polyhedron_items_3,
CGAL::HalfedgeDS_default&gt; Polyhedron;

涉及底层半边缘数据结构的基于矢量的表示。现在，我们想更仔细地看一下第二个模板参数Polyhedron_item s_3，它指定使用哪种顶点、半边和小平面。Polyhedron_item s_3的实现看起来有点涉及嵌套包装器类模板。但忽略了这一技术性问题，剩下的是三个局部 typedef，它们定义了多面体曲面的“顶点”、“半边缘”和“面”。请注意，我们在这里使用Face而不是facet。面是用于半边缘数据结构的术语。只有多面体曲面的顶层提供别名，将面重命名为面。

class Polyhedron_items_3 {
public:
template < class Refs, class Traits&gt;
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;
};
};

如果我们在参考手册中查找 typedefs中使用的三个类的定义，我们将看到默认多面体使用所有支持的关联、顶点类中的一个点和面类中的平面方程的确认。请注意包装器类是如何提供两个模板参数的，Refs（我们稍后将讨论）和Traits（多面体曲面使用的几何特征类），在这里为我们提供了点和平面方程的类型。

使用这个示例代码，我们可以编写自己的items类。相反，如果我们只想交换一个类，我们将说明一种更简单的方法。我们使用一个没有平面方程但添加了颜色属性的更简单的面。为了简化顶点、半边或面类的创建，建议始终从给定的基类之一派生。即使基类不包含任何数据，它也会提供方便的类型定义。因此，我们从基类派生，如果需要的话，重复强制性构造函数——这不是面的情况，而是顶点的情况——并添加颜色属性。

template <class Refs>
struct My_face : public CGAL::HalfedgeDS_face_base<Refs> {
CGAL::IO::Color color;
};

新items类是从旧items类派生而来的，并且包含face type def的包装器将被重写。请注意，包装器的名称及其模板参数是固定的。即使没有使用模板参数，也不能更改它们，如本例所示。

当我们使用具有多面体表面的新项目类时，我们的新面类用于半边数据结构，颜色属性在类型 Polyhedron_3::Facet 中可用。但是，Polyhedron_3::Facet 与我们局部面 My_fa ce 的类型定义不同，但它是由它派生的。因此，除了构造函数外，我们放入局部面类型中的所有内容都可以在 Polyhedron_3::Facet 类型中使用。将所有部分组合在一起，完整的示例程序说明了定义颜色属性后访问它的容易程度。

我们回到包装类的第一个模板参数Refs。该参数为我们提供了局部类型，使我们能够在顶点、半边和小平面之间进行进一步的引用，而这些在当前设计中尚未准备好。这些局部类型分别为Polyhedron_3::Verte x_handle, Polyhedron_3::Halfedge_handle, Polyhedron_3::Facet_handle。