在 3D 多边形网格上插入边界边的算法

Question

我有一个多边形汤网格（即没有清晰结构的网格），并且想要将边缘插入到多边形中，正确处理孔、紧角等。

例如给定网格：

我希望能够像这样生成轮廓：

我研究了几种轮廓并行刀具路径生成技术，但大多数都假设由单个边界边定义的二维多边形。即使是处理 3D 情况的那些似乎也将其展平为 2D 空间，我不确定这是否适用于非常凸的形状。

所以： 给定一个具有边界/开放边缘的任意 3D 多边形网格，如何从边缘生成轮廓/插图？

Answer 1

只是评论：

• 我会研究Matlab“3D”轮廓源代码。 （我的电脑上没有 Matlab。我相信如果你要安装它，你必须能够访问他们的源代码并了解他们的 3D 轮廓是如何实现的。）

• NIST 将轮廓定义为绘图，即“一种通过在二维格式上绘制常量 z 切片（称为轮廓）来表示 3 维表面的图形技术。也就是说，给定 z 值，绘制线条用于连接 z 值出现的 (x,y) 坐标。"

• 我尝试查看格雷厄姆的扫描，但看起来并不那么简单。我们应该首先定义曲面，并为“z 值发生的位置”明确定义一个或多个 2-d 平面，以便将任何算法从 2-d 缩放到 3-d 来绘制轮廓。

• 这是在 3D 中使用格雷厄姆扫描的失败尝试。可能会给你一些线索：

import random
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np


def orient_3d(p, q, r):
    val = (q[1] - p[1]) * ((r[0] - p[0]) * (q[2] - p[2]) - (r[2] - p[2]) * (q[0] - p[0])) - \
        (q[0] - p[0]) * ((r[1] - p[1]) * (q[2] - p[2]) - (r[2] - p[2]) * (q[1] - p[1]))
    if val == 0:
        return 0
    return 1 if val > 0 else 2


def graham_3d(points):
    if len(points) < 3:
        return []

    SPS = sorted(points, key=lambda x: (x[1], x[0], x[2]))
    SPS = SPS[:1] + sorted(SPS[1:], key=lambda x: (x[1] - SPS[0][1]) / (
        x[0] - SPS[0][0]) if (x[0] - SPS[0][0]) != 0 else float('inf'))

    stack = [SPS[0], SPS[1], SPS[2]]
    for i in range(3, len(SPS)):
        while len(stack) > 1 and orient_3d(stack[-2], stack[-1], SPS[i]) != 2:
            stack.pop()
        stack.append(SPS[i])

    return stack


random.seed(0)
A = []
for i in range(8):
    for j in range(8):
        for k in range(8):
            A.append((random.randint(1, 25), random.randint(50, 75), random.randint(26, 45)))


contour = []

while len(set(A)) > 2:
    A = list(set(A))
    convex_hull_3d = graham_3d(A)
    contour.append(convex_hull_3d)
    A = list(set(A) - set(convex_hull_3d))

# Plotting
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')

# Plot each convex hull
for convex_hull in contour:
    convex_hull.append(convex_hull[0])
    x, y, z = zip(*convex_hull)
    ax.plot(x, y, z)

ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.set_zlabel('Z')

plt.show()

• 上面随机绘制的格雷厄姆扫描不考虑任何二维平面来旋转轮廓。这些图像显示了它的外观：

图1

图2