Which voxel is the mouse over?

Question

I compute the line from the front to the back of my view. In my code, it travels from front to back:

I then try to use Bresenham's line algorithm in 3D to visit the voxels on that line:

var pX = front[0], pY = front[1], pZ = front[2],
    dX = back[0] - pX, dY = back[1] - pY, dZ = back[2] - pZ,
    N = Math.max(Math.abs(dX),Math.abs(dY),Math.abs(dZ)), N1 = 1/N,
    sX = dX*N1, sY = dY*N1, sZ = dZ*N1,
    i, x, y, z, block;
console.log("line",front,"->",back,"in",N,"steps, each",sX,sY,sZ);
for(i = 0; i<N; i++) {
    // todo skip whole empty sectors etc; optimisation easy later
    x = Math.floor(pX); y = Math.floor(pY); z = Math.floor(pZ);
    block = this.getBlock(x,y,z);
    console.log("visit",pX,pY,pZ,"->",x,y,z,"=",block);
    pX += sX; pY += sY; pZ += sZ;
}

This often misses some voxels; a line that passes through a voxel that is at 0,0,0->1,1,1, for example, is missed when the camera is is at 10,10,10:

line [8.654657271453807, 8.654143321776402, 8.654641478483198] ->
   [-55.95993231456806, -61.09857638545028, -56.11783581825804]
   in 69.75271970722667 steps, each -0.9263379242734749 -1 -0.9286014591059814
visit 8.654657271453807 8.654143321776402 8.654641478483198 -> 8 8 8 = null 
visit 7.728319347180332 7.654143321776402 7.7260400193772165 -> 7 7 7 = null
visit 6.801981422906858 6.654143321776402 6.797438560271235 -> 6 6 6 = null 
visit 5.875643498633383 5.654143321776402 5.868837101165254 -> 5 5 5 = null 
visit 4.949305574359908 4.654143321776402 4.940235642059273 -> 4 4 4 = null 
visit 4.022967650086433 3.6541433217764023 4.0116341829532915 -> 4 3 4 = null 
visit 3.0966297258129583 2.6541433217764023 3.0830327238473103 -> 3 2 3 = null
visit 2.1702918015394834 1.6541433217764023 2.154431264741329 -> 2 1 2 = null 
visit 1.2439538772660086 0.6541433217764023 1.2258298056353478 -> 1 0 1 = null
visit 0.31761595299253365 -0.34585667822359767 0.29722834652936647 -> 0 -1 0 = null 
visit -0.6087219712809413 -1.3458566782235977 -0.6313731125766149 -> -1 -2 -1 = null
visit -1.5350598955544164 -2.3458566782235977 -1.5599745716825963 -> -2 -3 -2 = null
...                                                                                 
visit -54.33632157914253 -59.3458566782236 -54.490257740723585 -> -55 -60 -55 = null
visit -55.262659503416 -60.3458566782236 -55.41885919982957 -> -56 -61 -56 = null

My suspicion is my use of Math.floor, but what should I use in its place? Rounding towards 0 or away from 0 just moves my misses around and doesn't actually solve them.

How can I accurately visit all the voxels that the mouse cursor's ray passes over?

Answer 1

As @AakashM pointed out, Bresenham is not suitable for this problem.

I found this code and adapted it to work with negative coordinates and so on:

function lineBlocksIntersection(line) {
    var oX = line[0][0], oY = line[0][1], oZ = line[0][2],
        dX = line[1][0], dY = line[1][1], dZ = line[1][2],
        x = Math.floor(oX), y = Math.floor(oY), z = Math.floor(oZ),
        intBound = function(s,ds) { return ds > 0? (Math.ceil(s)-s)/ds: (s-Math.floor(s))/-ds; },
        tMaxX = intBound(oX,dX), tMaxY = intBound(oY,dY), tMaxZ = intBound(oZ,dZ),
        sign = function(x) { return x > 0 ? 1 : x < 0 ? -1 : 0; },
        stepX = sign(dX), stepY = sign(dY), stepZ = sign(dZ),
        deltaX = stepX/dX, deltaY = stepY/dY, deltaZ = stepZ/dZ,
        fX, fY, fZ, ret, block;
    for(;;) {
        if(tMaxX <= tMaxY && tMaxX <= tMaxZ) {
            x += stepX;
            if(dX < 0? x < oX+dX: x > oX+dX)
                break;
            tMaxX += deltaX;
            fX = stepX; fY = 0; fZ = 0;
        } else if(tMaxY <= tMaxX && tMaxY <= tMaxZ) {
            y += stepY;
            if(dY < 0? y < oY+dY: y > oY+dY)
                break;
            tMaxY += deltaY;
            fX = 0; fY = stepY; fZ = 0;
        } else {
            z += stepZ;
            if(dZ < 0? z < oZ+dZ: z > oZ+dZ)
                break;
            tMaxZ += deltaZ;
            fX = 0; fY = 0; fZ = stepZ;
        }
        block = getBlock(x,y,z);
        if(block) {
            if(!ret)
                ret = [];
            ret.push([[x,y,z],block,[fX,fY,fZ]]);
        }
    }
    return ret;
}