3d - 计算平面的所有离散点

Question

我希望填充由三个点定义的平面上的所有点，以便：

• 所有点的坐标都是整数，即没有小数点坐标。
• 该平面上的所有点都不在由定义该平面的三个点形成的边界之外

例如，给定由点A(3, 0, 0)、B(0, 3, 0)和C(0, 0, 3)定义的平面 P ：

• 点D(1, 1, 1)满足这个条件
• 点E(6, 3, -6)不满足这个条件，因为它在平面上但在边界之外
• 点F(4, 1, 3)不满足这个条件，因为它不在平面上

我尝试过应用Bresenham 的 3d 线算法并将其扩展到平面绘图，但我无法弄清楚。

标签： 3dcomputational-geometryrasterizing

Answer 1

扫描填充解决方案：

将三角形投影到XY并扫描填充它（考虑和和Y之间的所有整数纵坐标，并通过与边的交点找到每个的和；取所有中间的）。YminYmaxYXminXmaxX

然后检查对应Z的是否为整数（平面方程为a.X + b.Y + c.Z + d = 0）。

工作量与三角形的投影面积成正比。

你可以稍微加快这个过程，注意对于一个常数Y，你只使用丢番图方程的解a.X + c.Z = - d - b.Y。这个方程只有在gcd(a, c)除法时才有解d + b.Y，这限制了可能的Y。

---

在您的情况下，平面是X + Y + Z = 3和投影三角形(0, 0), (3, 0), (0, 3)。

通过填充，有十个网格点，其中三个角，六个点在边缘，一个在里面。对于所有这些点，Z是一个整数。（加速技术在这里不适用。）

(0, 0, 3), (1, 0, 2), (2, 0, 1), (3, 0, 0), 
(0, 1, 2), (1, 1, 1), (2, 1, 0),
(0, 2, 1), (1, 2, 0), 
(0, 3, 0).