哪個體素是鼠標懸停的？

我計算從我的視圖的前面到後面的線。在我的代碼，它的旅行從front到back：哪個體素是鼠標懸停的？

然後我嘗試使用Bresenham's line algorithm在3D訪問該行的體素：

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

這往往錯過一些體素;通過體素是在0,0,0->1,1,1通過一條線，例如，錯過當相機處於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

我懷疑是我使用的Math.floor，但我應該在它的地方使用？向0或從0向外舍入只會改變我的想法，但實際上並沒有解決它們。

我該如何準確地訪問鼠標光標所經過的所有體素？

來源

2013-07-05 Will

不是我的領域，但我不知道一個布氏算法是正確的完成這個任務。看看例如[維基百科上的這個2d Bresenham插圖]（http://en.wikipedia.org/wiki/File:Bresenham.svg），我們可以看到該算法確實*不識別該行遇到的所有*單元，只是最接近線路的那些（在某種意義上）。 – AakashM

@AakashM看起來你是對的;如何實際確定體素仍然是一個懸而未決的問題，當然是 – Will

http://stackoverflow.com/questions/16505905/walk-a-line-between-two-points-in-a-3d-voxel-space-visiting -all-cells/16597423＃16597423任何好？ – AakashM

正如@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; 
}

來源

2013-07-05 21:07:06 Will

哪個體素是鼠標懸停的？

回答

相關問題