어떤 보셀이 마우스 오버입니까?

Question

필자는 내보기의 앞에서 뒤로 줄을 계산합니다. 내 코드에서, front에서 back로 이동 :

나는 그 줄에 복셀을 방문 3D로 Bresenham's line algorithm를 사용하려고

:이 종종 일부 복셀이 골대를 벗어났습니다

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

;

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 

내 의심 Math.floor 내 사용하는 것입니다,하지만 난 그 자리에 무엇을 사용해야합니다 0,0,0->1,1,1에있는 복셀 통과하는 라인이, 예를 들어, 카메라가있을 때 놓친는 10,10,10에있다? 0을 향해 라운딩하거나 0에서 멀어지면 내 미스가 움직이고 실제로 풀리지 않습니다.

마우스 커서의 광선이 통과하는 모든 복셀을 정확하게 방문하려면 어떻게해야합니까?

Answer 1

@AakashM이 지적했듯이, Bresenham은이 문제에 적합하지 않습니다.

나는 this code을 발견하고 등등 부정적인 좌표와 함께 작동하도록 :

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