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

Question

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

​

​

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

Answer 1

Pierre Baret链接中的方法可以解决我的问题。当线只通过某个体素的顶点时，是否访问当前体素是一个非常模糊的问题，所以我对方法做了一些修改。当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);
}

}