java - 由体素制成的平面 3D 三角形

Question

我有一个问题，我似乎无法找到一个有效的算法，我已经尝试了好几天，虽然很接近，但到目前为止还很接近。

我想画一个由 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;
                }
            }
        }
    }
}

Answer 1

你可以使用类似 Besenham's line algorithm 的东西，但扩展到三个维度。我们想从中得到的两个主要想法是:

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

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

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

2. 您希望平面足够不陡，以避免出现洞。您必须满足这些条件:

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

   将法 vector 和初始点绕 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 步中执行了任何旋转，请以相反的顺序对您的体素集合执行与这些旋转相反的操作。