2

我正在开发 WPF 中的可视化工具，它具有通过 3-D 形状显示切割平面的功能。例如，像这样的 3-d 几何：

全几何

...被飞机切割。切割后，该算法识别沿切割平面的所有独特轮廓，并以 CW 或 CCW 缠绕顺序填充线段列表。任何简单的多边形都可以使用 Cuting Ears 算法轻松进行三角剖分和渲染，如下所示：

切割平面图像 在此处输入图像描述

给定右侧三角剖分的输入，以及左侧平面上可见的内部折线，是否有一种算法可以重新配置三角剖分以构造由折线勾勒出的孔？

如果已经在 C# 或其他 CLR 语言中推出了算法，我很想了解它们。我正在使用 WPF 调用的 Point3D 列表来描述 MeshGeometry3D 三角形网格，但是如果需要，我显然可以填充任何数据结构，或者通过研究其他语言代码或伪代码来旋转我自己的类。

编辑：查看接受的答案；我正在使用Poly2Tri的 C# 实现，这是一个受约束的 Delaunay 三角剖分。但是，（图像未按比例缩放）Poly2Tri 算法（中心）以 780 段折线失败，而 Cuting Ears（右）没有，直到我剥离了输入的精度，将单精度值向上转换为双精度值而不是双精度值. 它现在产生的三角剖分与 Cut Ears 不同，但尊重外部多段线的边界。

复聚 复杂CDT 复杂的耳朵

4

2 回答 2

2

以边界线段作为约束条件计算受约束的 Delaunay 三角剖分。确定一个内三角形。从那里扩大该区域，直到您到达边界。作为一个积极的副作用，这样的三角剖分将具有更好的三角形形状。

区域的约束 Delaunay

于 2012-10-31T08:46:19.737 回答
0

在 SketchUp 和 3DSMax 之间制作导出/导入插件时必须解决完全相同的问题。Sketchup 使用概念或外部和内部循环，而 3DS Max 是纯几何。

可悲的是，我没有插件，所以我会尽量记住它：

foreach point in outerLoop
{
    // Loop over all other point to find the nearest valid one
    foreach otherPoint in both outerLoop and all innerLoops where otherPoint is not point
    {
        if otherPoint is adjacent to point
            reject otherPoint 

        if distance between point and otherPoint is bigger than previous distance
            reject otherPoint 

        // Test is vector is point outside the geometry in case of convexe shapes
        if cross product of vector from (point - adjacent point) and (point - nearest point) is pointing away from cross product of vectors of (point - both adjacents point)
            reject otherPoint 

        nearestPoint = otherPoint
    }

    for the two adjacentPoint of nearestPoint
    {
        if adjacentPoint is also adjacent to point
            make triangle(point, adjacentPoint, nearestPoint)
        if cross product of vector from (point - adjacent point) and (point - nearest point) is pointing in the same direction as cross product of vectors of (point - both adjacents point)
            make triangle(point, adjacentPoint, nearestPoint)
    }
}

repeat the above for innerLoops point while only checking against other innerLoops

make triangle function should check if the triangle already exist from previous iteration.

它不是超级漂亮而且有点粗鲁，但它可以与无限数量的内部循环一起使用，并且总是尽可能地创建最好的三角形。

我很确定会有办法提高它的性能，但我从来没有给它足够的时间。

于 2012-10-31T07:20:03.197 回答