2

我有一个问题，我似乎无法找到一个可行的算法，我已经尝试了好几天，但距离如此之近。

我想绘制一个由 3 个点（p0、p1、p2）定义的三角形。这个三角形可以是任何形状、大小和方向。三角形也必须在里面填充。

以下是我尝试过的一些事情以及它们失败的原因：

1

  • 沿着三角形从一边到另一边画线
    • 失败，因为三角形会有孔，并且由于在有角度的表面上随着位置变化而画线的笨拙而不是平坦的

2

  • 迭代一个区域并测试该点是否落在与三角形平行的平面以及投影到覆盖三角形区域的 XY、ZY 和 XZ 平面上的其他 3 个平面
    • 失败是因为对于某些三角形（具有非常接近的边）会有不可预测的结果，例如漂浮在周围的体素没有连接到任何东西

3

  • 沿着三角形的边迭代一个区域（线算法）并测试一个点是否越过平行平面
    • 失败是因为从 p0 到 p1 画一条线与从 p1 到 p0 画一条线不同，任何重新排列的尝试都没有帮助，或者会导致更多问题。不对称是这个问题。

这都是为了制作多边形和平面。3 给了我最大的成功并制作了准确的三角形，但是当我尝试将它们连接在一起时，一切都崩溃了，我遇到了无法连接、不对称等问题。我相信 3 可以进行一些调整，但我只是磨损了从试图使这项工作这么长时间并需要帮助。

我的算法中有很多不相关的小细节，所以我把它们排除在外。对于数字 3，这可能是我的实现而不是算法本身的问题。如果您想要代码，我会尝试将其清理到足以理解的程度，不过这需要我几分钟。但我正在寻找已知有效的算法。我似乎在任何地方都找不到任何体素形状制作算法，我一直在从头开始做所有事情。

编辑：

这是第三次尝试。这是一个烂摊子，但我试图清理它。

// Point3i is a class I made, however the Vector3fs you'll see are from lwjgl

public void drawTriangle (Point3i r0, Point3i r1, Point3i r2)
{
    // Util is a class I made with some useful stuff inside

    // Starting values for iteration

    int sx = (int) Util.min(r0.x, r1.x, r2.x);
    int sy = (int) Util.min(r0.y, r1.y, r2.y);
    int sz = (int) Util.min(r0.z, r1.z, r2.z);

    // Ending values for iteration

    int ex = (int) Util.max(r0.x, r1.x, r2.x);
    int ey = (int) Util.max(r0.y, r1.y, r2.y);
    int ez = (int) Util.max(r0.z, r1.z, r2.z);

    // Side lengths

    float l0 = Util.distance(r0.x, r1.x, r0.y, r1.y, r0.z, r1.z);
    float l1 = Util.distance(r2.x, r1.x, r2.y, r1.y, r2.z, r1.z);
    float l2 = Util.distance(r0.x, r2.x, r0.y, r2.y, r0.z, r2.z);

    // Calculate the normal vector

    Vector3f nn = new Vector3f(r1.x - r0.x, r1.y - r0.y, r1.z - r0.z);
    Vector3f n   = new Vector3f(r2.x - r0.x, r2.y - r0.y, r2.z - r0.z);
    Vector3f.cross(nn, n, n);

    // Determines which direction we increment for

    int iz = n.z >= 0 ? 1 : -1;
    int iy = n.y >= 0 ? 1 : -1;
    int ix = n.x >= 0 ? 1 : -1;

    // Reorganize for the direction of iteration

    if (iz < 0) {
        int tmp = sz;
        sz = ez;
        ez = tmp;
    }
    if (iy < 0) {
        int tmp = sy;
        sy = ey;
        ey = tmp;
    }
    if (ix < 0) {
        int tmp = sx;
        sx = ex;
        ex = tmp;
    }

    // We're we want to iterate over the end vars so we change the value
    // by their incrementors/decrementors

    ex += ix;
    ey += iy;
    ez += iz;

    // Maximum length

    float lmax = Util.max(l0, l1, l2);

    // This is a class I made which manually iterates over a line, I already
    // know that this class is working

    GeneratorLine3d g0, g1, g2;

    // This is a vector for the longest side

    Vector3f v = new Vector3f();

    // make the generators

    if (lmax == l0) {
        v.x = r1.x - r0.x;
        v.y = r1.y - r0.y;
        v.z = r1.z - r0.z;

        g0 = new GeneratorLine3d(r0, r1);
        g1 = new GeneratorLine3d(r0, r2);
        g2 = new GeneratorLine3d(r2, r1);
    }
    else if (lmax == l1) {
        v.x = r1.x - r2.x;
        v.y = r1.y - r2.y;
        v.z = r1.z - r2.z;

        g0 = new GeneratorLine3d(r2, r1);
        g1 = new GeneratorLine3d(r2, r0);
        g2 = new GeneratorLine3d(r0, r1);
    }
    else {
        v.x = r2.x - r0.x;
        v.y = r2.y - r0.y;
        v.z = r2.z - r0.z;

        g0 = new GeneratorLine3d(r0, r2);
        g1 = new GeneratorLine3d(r0, r1);
        g2 = new GeneratorLine3d(r1, r2);
    }

    // Absolute values for the normal

    float anx = Math.abs(n.x);
    float any = Math.abs(n.y);
    float anz = Math.abs(n.z);

    int i, o;
    int si, so;
    int ii, io;
    int ei, eo;

    boolean maxx, maxy, maxz,
    midy, midz, midx,
    minx, miny, minz;

    maxx = maxy = maxz =
    midy = midz = midx =
    minx = miny = minz = false;

    // Absolute values for the longest side vector      

    float rnx = Math.abs(v.x);
    float rny = Math.abs(v.y);
    float rnz = Math.abs(v.z);

    int rmid = Util.max(rnx, rny, rnz);

    if (rmid == rnz) midz = true;
    else if (rmid == rny) midy = true;

    midx = !midz && !midy;

    // Determine the inner and outer loop directions

    if (midz) {
        if (any > anx) 
        {
            maxy = true;
            si = sy;
            ii = iy;
            ei = ey;
        }
        else {
            maxx = true;
            si = sx;
            ii = ix;
            ei = ex;
        }
    }
    else {
        if (anz > anx) {
            maxz = true;
            si = sz;
            ii = iz;
            ei = ez;
        }
        else {
            maxx = true;
            si = sx;
            ii = ix;
            ei = ex;
        }
    }

    if (!midz && !maxz) {
        minz = true;
        so = sz;
        eo = ez;
    }
    else if (!midy && !maxy) {
        miny = true;
        so = sy;
        eo = ey;
    }
    else {
        minx = true;
        so = sx;
        eo = ex;
    }

    // GeneratorLine3d is iterable
    Point3i p1;
    for (Point3i p0 : g0) {
        // Make sure the two 'mid' coordinate correspond for the area inside the triangle

        if (midz)
            do p1 = g1.hasNext() ? g1.next() : g2.next();
            while (p1.z != p0.z);
        else if (midy)
            do p1 = g1.hasNext() ? g1.next() : g2.next();
            while (p1.y != p0.y);
        else
            do p1 = g1.hasNext() ? g1.next() : g2.next();
            while (p1.x != p0.x);

        eo = (minx ? p0.x : miny ? p0.y : p0.z);
        so = (minx ? p1.x : miny ? p1.y : p1.z);
        io = eo - so >= 0 ? 1 : -1;

        for (o = so; o != eo; o += io) {
            for (i = si; i != ei; i += ii) {
                int x = maxx ? i : midx ? p0.x : o;
                int y = maxy ? i : midy ? p0.y : o;
                int z = maxz ? i : midz ? p0.z : o;

                // isPassing tests to see if a point goes past a plane
                // I know it's working, so no code

                // voxels is a member that is an arraylist of Point3i

                if (isPassing(x, y, z, r0, n.x, n.y, n.z)) {
                    voxels.add(new Point3i(x, y, z));
                    break;
                }
            }
        }
    }
}
4

2 回答 2

1

您可以使用类似Besenham 的线算法，但扩展到三个维度。我们想从中获得的两个主要想法是：

  • 旋转初始线，使其斜率不会太陡。
  • 对于任何给定的 x 值，找到最接近理想 y 值的整数值。

正如 Bresenham 的算法通过执行初始旋转来防止间隙一样，我们将通过执行两次初始旋转来避免空洞。

  1. 获取代表三角形所在平面的法线向量和点。提示：使用（从 p0 到 p1 的线）和（从 p0 到 p2 的线）的叉积作为向量，并使用任何角点作为该点。

  2. 您希望飞机足够不陡，以避免出现孔洞。您必须满足以下条件：

    • -1 >= norm.x / norm.y >= 1
    • -1 >= norm.z / norm.y >= 1

    将法线向量和初始点绕 x 轴旋转 90 度，绕 z 轴旋转 90 度，直到满足这些条件。我不确定如何以最少的旋转次数做到这一点，但我相当确定您可以满足任何飞机的这些条件。

  3. 创建一个函数 f(x,z)，它代表您旋转的三角形现在所在的平面。它应该返回任意一对 X 和 Z 值的 Y 值。
  4. 将您的三角形投影到 XZ 平面上（即，将所有 y 值设置为 0），并使用您最喜欢的 2d 三角形绘制算法来获取 x 和 z 坐标的集合。
  5. 对于第 4 步中的每个像素值，将 x 和 z 值传递给第 3 步中的函数 f(x,z)。将结果四舍五入为最接近的整数，并将 x、y 和 z 值作为体素存储在某处。
  6. 如果您在步骤 2 中执行了任何旋转，请在您的体素集合上以相反的顺序执行这些旋转的相反操作。
于 2012-06-11T17:42:15.310 回答
0

从检查三角形/体素相交的函数开始。现在你可以扫描一个体积并找到与三角形相交的体素——这些是你感兴趣的。这是一个糟糕的算法，但也是对你尝试的其他任何东西的回归测试。使用 SAT（分离轴定理）并考虑三角形退化体积（1 个面，3 个边）并考虑体素对称性（只有 3 个面法线），该测试很容易实现。

我使用八叉树，所以我首选的方法是针对一个大体素测试一个三角形，并找出它与 8 个子八分圆中的哪一个相交。然后对相交的孩子使用递归，直到达到所需的细分水平。提示：最多有 6 个孩子可以与三角形相交，而且通常少于这个数。这很棘手，但会产生与第一种方法相同的结果，但要快得多。

3d 中的光栅化可能是最快的，但恕我直言，更难保证在所有情况下都没有漏洞。同样，使用第一种方法进行比较。

于 2012-06-11T18:03:25.200 回答