绘制在3D体素空间中穿过3D线的所有体素

Question

我想绘制一条3D体素线，即找到一条线所经过的所有体素。 3D bresenham总是会跳过一些体素。如图所示，由3D bresenham生成的体素不能完全包含起始体素和目标体素之间的线。

此链接中的算法：Algorithm for drawing a 4-connected line可以在2D平面上解决我的问题，但我无法将其改进为3D。

Answer 1

皮埃尔·巴雷特的链接中的方法可以解决我的问题。当线只通过某个体素的顶点时，是否访问当前体素是一个非常模糊的问题，所以我对该方法做了一点改动。当tMaxX，tMaxY和tMaxZ中的两个或多个值相等时，由纸张中的方法生成的体素如a所示。我做了一点改动，在b中生成结果。更正常的条件在c中示出，其分别比较由3D bresenham和该方法生成的线。

由c ++实现的代码：

void line3D(int endX, int endY, int endZ, int startX, int startY, int startZ, void draw){
int x1 = endX, y1 = endY, z1 = endZ, x0 = startX, y0 = startY, z0 = startZ;
int dx = abs(x1 - x0);
int dy = abs(y1 - y0);
int dz = abs(z1 - z0);
int stepX = x0 < x1 ? 1 : -1;
int stepY = y0 < y1 ? 1 : -1;
int stepZ = z0 < z1 ? 1 : -1;
double hypotenuse = sqrt(pow(dx, 2) + pow(dy, 2) + pow(dz, 2));
double tMaxX = hypotenuse*0.5 / dx;
double tMaxY = hypotenuse*0.5 / dy;
double tMaxZ = hypotenuse*0.5 / dz;
double tDeltaX = hypotenuse / dx;
double tDeltaY = hypotenuse / dy;
double tDeltaZ = hypotenuse / dz;
while (x0 != x1 || y0 != y1 || z0 != z1){
    if (tMaxX < tMaxY) {
        if (tMaxX < tMaxZ) {
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
        }
        else if (tMaxX > tMaxZ){
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
        else{
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
    }
    else if (tMaxX > tMaxY){
        if (tMaxY < tMaxZ) {
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
        }
        else if (tMaxY > tMaxZ){
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
        else{
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;

        }
    }
    else{
        if (tMaxY < tMaxZ) {
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
        }
        else if (tMaxY > tMaxZ){
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
        else{
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;

        }
    }
    draw(x0, y0, z0);
}

}