CGAL笔记:单元格复合体和多面体篇——多面体的 3D Minkowski 和

介绍

如下图，勺子和星星的 Minkowski 和。

分解法

计算非凸多面体闵可夫斯基和的分解方法利用了凸多面体闵可夫斯基和比较容易计算的特点。它将两个多面体分解为凸块，计算凸块的所有成对 Minkowski 和，并合并成对和。

图 中的分解方法将两个输入多面体分解为凸部分，计算凸部分的所有成对 Minkowski 和，并将成对和合并。

特性和约束

这个包是为了允许计算全维多面体的 Minkowski 和，即使在所谓的紧密通道场景中也是如此。狭窄通道场景出现在机器人运动规划中，此时机器人的宽度刚好等于它需要穿过的通道。在这些场景中，至少有一个多面体——障碍物或机器人——必须建模为一个开放集。那么 Minkowski 和也将是一个开集，并且紧通道将作为低维排除项出现，即作为面、线或顶点，与它们周围的体积相比，它们不是结果点集的一部分。下图显示了这样一个狭窄的通道场景。

我们的实现用于Nef_polyhedron_3对输入多面体和结果多面体建模。的实例Nef_polyhedron_3表示将三维空间细分为顶点、边、面和体积。其中一些项目形成多面体（选中），而其他项目表示多面体（未选中）内的外部体积或孔。例如，单位立方体是点集[0,1]3. 代表单位立方体的最小细分有 8 个顶点、12 条边、6 个面和 2 个体积。由顶点、边和面包围的体积是立方体的内部，因此被选中。立方体外部的体积不属于它，因此未被选中。顶点、边和面——也表示为边界项——需要用来分隔两个体积，但也可用于表示拓扑属性。在（封闭的）单位立方体的情况下，边界项是多面体的一部分，因此被选中，但在开放的单位立方体的情况下[0,1)3他们未被选中。每个项目都有自己的选择标记，允许正确表示 Nef 多面体，这些多面体在布尔和拓扑运算下是封闭的。

的使用Nef_polyhedron_3允许超出两个实体的 Minkowski 和的许多场景。首先，他们可以对紧密通道场景的输入和结果进行建模，即，他们可以根据输入模型的需要对开放和封闭实体进行建模，并且他们可以对紧密通道进行建模，这些通道是低维排除项，表示为未选择的面、边和顶点。我们努力扩展包以适用于任意 3D Nef 多面体。除了两个实体的 Minkowski 和之外，我们还添加了几个特征。目前我们允许输入多面体包括：

1. 奇点
2. 奇异边
3. 没有孔的奇异凸面
4. 具有没有孔洞的凸面的表面。
5. 三维特征，其共面小平面具有共同的选择标记（这包括开放和封闭的实体）

换个角度看，实现上有如下限制：

1. 输入多面体必须有界（忽略选定的外部体积）。
2. 全维特征的所有共面面集必须具有相同的选择标记（如果选择标记不同，则假定未选择）。
3. 低维特征的所有面都需要是凸的，不能有孔（非凸面和孔被忽略）。

第二个限制可能看起来有点奇怪。它源于这样一个事实，即凸多面体上的 Minkowski 和只能处理边由单个面组成的多面体。分解过程通常会在凸部、其相邻凸部和外部体积之间产生复杂的邻接关系。然后将凸块的边分解为多个小平面，每个小平面代表这些邻接关系中的一个。对于凸 Minkowski 和，我们忽略边的分解，但需要找到一个共同的选择标记。如果有两个面与外体积相邻，但有不同的选择标记，我们不能在不破坏 Minkowski 和的正确性的情况下设置一个共同的选择标记。

用法

该函数minkowski_sum_3()应与 一起使用Exact_predicates_exact_constructions_kernel，这通常是最有效的选择并且允许浮点输入。

下面的示例代码说明了函数的用法minkowski_sum_3()。请注意，如果输入多面体是非凸的，则该函数将对其进行修改。因此，如果进一步需要它们，则需要首先复制它们。复制不是由函数本身完成的，以尽可能减少内存使用量。

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/minkowski_sum_3.h>
#include <fstream>
#include <iostream>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
int main() {
  Nef_polyhedron N0, N1;
  std::ifstream in("cube.nef3");
  in >> N0;
  std::cin >> N1;
  Nef_polyhedron result = CGAL::minkowski_sum_3(N0, N1);
}

通过该函数，minkowski_sum_3()还可以实现其他有趣的几何操作，例如滑动操作，它计算沿着多边形路径移动的多面体扫过的点集。下面的示例演示如何构建多边形路径，然后通过调用函数计算滑动操作minkowski_sum_3()。

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/minkowski_sum_3.h>
#include <iostream>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel>     Nef_polyhedron;
typedef Kernel::Point_3 Point_3;
typedef Point_3* point_iterator;
typedef std::pair<point_iterator,point_iterator>
  point_range;
typedef std::list<point_range> polyline;
int main()
{
  Nef_polyhedron N0;
  std::cin >> N0;
  Point_3 pl[6] =
    {Point_3(-100,0,0),
     Point_3(40,-70,0),
     Point_3(40,50,40),
     Point_3(-90,-60,60),
     Point_3(0, 0, -100),
     Point_3(30,0,150)
  };
  polyline poly;
  poly.push_back(point_range(pl,pl 6));
  Nef_polyhedron N1(poly.begin(), poly.end(), Nef_polyhedron::Polylines_tag());
  Nef_polyhedron result = CGAL::minkowski_sum_3(N0, N1);
}

这篇好文章是转载于：学新通技术网