由体素制成的扁平3D三角形

我有一个问题，我似乎无法得到一个有效的算法，我已经尝试了几天，并且如此接近，但到目前为止 .

我想绘制一个由3个点（p0，p1，p2）定义的三角形 . 该三角形可以是任何形状，大小和方向 . 内部也必须填充三角形 .

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

1

• 沿三角形从一侧到另一侧绘制线条

• 失败，因为三角形会有孔而且由于角度曲面上绘制线条的不方便而不会变平

2

• 迭代一个区域并测试该点是否落在平行于三角形的平面上，另外3个平面投影到覆盖三角形区域的XY，ZY和XZ平面上

• 失败，因为对于某些三角形（具有非常接近的边），会出现不可预测的结果，例如浮动的体素没有连接到任何东西

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;
                }
            }
        }
    }
}