两组网格之间的快速布尔运算

Question

这是这个问题的简化版。基本上我只是在问问题中的第一部分。

假设我有两组网格，网格类的定义如下（C#语法）：

public class Mesh
{
 public List<Element> elements;
 public List<Point> points;
}

public class Element
{
  public List<int> PointIndex;
}

public class Point
{
  public double X;
  public double Y;
}

有没有一种高效的方法/实现方式可以找到两个Mesh之间布尔运算结果（在我的情况下，我想找到多边形式的交集）？

朴素的方法是循环遍历Mesh对象中的所有Element，检查另一个Mesh对象中的其他Element，并获得结果。

但我相信有更有效的算法可以做到这一点-- 利用平面扫描算法。

如果已经在.Net、C++或matlab中实现了这样的算法，那就更好了。

- Graviton

---

你是在寻找集合式的交集（即，存在于网格A和网格B中的所有点），还是多边形式的交集（几何上都在两个网格内的所有点）？ - Zac Howland

@ Zac，我正在寻找多边形交集的样式。 - Graviton

Answer 1

仅有网格并不足以对其进行布尔运算。

class B
{
public:
   virtual bool Inside(Point p) const=0;
};

在提供了额外信息之后，布尔运算变得非常简单：

class Intersect : public B
{
public:
   Intersect(B &b1, B &b2) : b1(b1), b2(b2) { }
   bool Inside(Point p) const { return b1.Inside(p) && b2.Inside(p); }
private:
   B &b1;
   B &b2;
};

但是从这个结构中获取网格要困难得多。你不会从中获得任何有用的东西。最好的解决方案是使用类似于Marching Cubes的算法，但是从那里得到的网格看起来并不好。

- tp1

Answer 2

网格布尔运算很难正确实现，您尝试使用一些现有的代码是正确的。

一个现有的适合您需求的C++库是CGAL。

您可以查看手册。

- rotoglup

---

正如问题所述，我正在寻找一种更高效的多边形叠加操作方法，以便在大规模情况下使用。因此，我需要比朴素算法更高效的解决方案，该算法只是对Mesh列表中的每个多边形进行相交运算。 - Graviton

我理解你有多个多边形。CGAL希望支持对多边形集合进行布尔运算，不仅仅是针对单个多边形。请查看手册中的“执行聚合操作”。 - rotoglup

这就是我从Unity转到虚幻引擎的原因。一个月前，我遇到了类似的问题，并发现如果没有外部库，解决起来会非常痛苦。 - Cheshire Cat

在实现网格布尔运算时，有哪些常见的陷阱？ - Dorijan Cirkveni

Answer 3

在C++开源库MeshLib中，有一个快速而强大的实现三角网格布尔运算。

这里有一个基于MeshLib的MeshInspector应用程序的视频，作者甚至声称可以在适度复杂的网格上实时执行。

- Fedor

Answer 4

在C++中，如果您将网格保持排序（或在操作之前对其进行排序），并使用std::set_intersection，则可以更高效地完成此操作。 为此，您必须向Point添加某种排序关系。（假设在C++中，List是一个标准容器；可能是vector或deque，语言将自动生成其他类的排序操作符）。

- James Kanze

---

首先，你如何“排序”Mesh？其次，元素（或多边形）交集与通常的set_intersection不同。 - Graviton