Draw all voxels that pass through a 3D line in 3D voxel space

Question

I want to draw a 3D voxelized line, that is, to find all the voxels which a line passes. 3D bresenham always skips some voxels. As shown in the figure, the voxels generated by 3D bresenham cannot completely contain the line between the start voxel and target voxel.

3D line generated by 3D bresenham

The algorithm in this link: Algorithm for drawing a 4-connected line can solve my problem on a 2D plane, but I failed to improve it to 3D.

A few time ago I used this paper to do something like what you're trying to do: http://www.cs.yorku.ca/~amana/research/grid.pdf — Pierre Baret, Mar 20 '19 at 15:42
Thanks a lot. I made some changes to this method in the paper and have solved my problem. — yaqian chen, Mar 21 '19 at 09:03
use DDA its simple, faster than bresenham and easily portable to any dimensionality. Also take a look at this: [DDA + subpixel precision](https://stackoverflow.com/a/24682318/2521214) — Spektre, Mar 21 '19 at 09:51
Is your goal to draw _all voxels_ that pass through a 3D line? — Peter O., Mar 21 '19 at 21:32
@PeterO. yes. I've solved my problem by the following method. If you have a better solution, I'll try it. — yaqian chen, Mar 22 '19 at 02:07
@Spektre Thank you very much for your answer. I've tried it, but this method will generate some cells not intersected with the line. — yaqian chen, Mar 22 '19 at 11:53

score 5 · Answer 1 · edited Mar 22 '19 at 02:21

The method in Pierre Baret's link can solve my problem. When the line passes only the vertices of a certain voxel, whether to visit the current voxel is a very vague question, so I made a little changes to the method. When two or more values in tMaxX, tMaxY, and tMaxZ are equal, the voxels generated by the method in the paper are as shown in a. I made a little change to generate the result in b. A more normal condition is shown in c, which compares lines generated by 3D bresenham and this method respectively.

enter image description here

The code implemented by 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);
}

}

Draw all voxels that pass through a 3D line in 3D voxel space

1 Answers1