線光柵化：無論線條漸變，是否覆蓋所有像素？

Question

基本上，我想使用一個線路算法來確定哪些單元格來檢查我的raycaster碰撞。

Bresenham對此不太好，因爲它使用統一厚度的方法，這意味着它會忽略至少不覆蓋線的一半的單元。不是很好，因爲這意味着我的一些線段沒有被檢查與單元的交點，導致錯誤。

我似乎無法找到任何「粗線」算法，任何人都可以幫我找到一個？

綠：我想要什麼。
紅色：我現在有什麼，不想要什麼。

Answer 1

我和你有完全相同的問題，並找到了一個非常簡單的解決方案。通常情況下，布氏有兩個連續的，如果是，以確定它是否應該增加對兩個維度的座標：

public void drawLine(int x0, int y0, int x1, int y1, char ch) { 
    int dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1; 
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1; 
    int err = dx + dy, e2; // error value e_xy 

    for (;;) { 
     put(x0, y0, ch); 

     if (x0 == x1 && y0 == y1) break; 

     e2 = 2 * err; 

     // horizontal step? 
     if (e2 > dy) { 
      err += dy; 
      x0 += sx; 
     } 

     // vertical step? 
     if (e2 < dx) { 
      err += dx; 
      y0 += sy; 
     } 
    } 
} 

現在，所有你需要做的是第二if前插入一個else：

public void drawLineNoDiagonalSteps(int x0, int y0, int x1, int y1, char ch) { 
    int dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1; 
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1; 
    int err = dx + dy, e2; 

    for (;;) { 
     put(x0, y0, ch); 

     if (x0 == x1 && y0 == y1) break; 

     e2 = 2 * err; 

     // EITHER horizontal OR vertical step (but not both!) 
     if (e2 > dy) { 
      err += dy; 
      x0 += sx; 
     } else if (e2 < dx) { // <--- this "else" makes the difference 
      err += dx; 
      y0 += sy; 
     } 
    } 
} 

現在算法不再一次改變兩個座標。 我還沒有徹底測試過，但它似乎工作得很好。

Answer 2

佈雷森漢姆有一個附加約束條件，允許不允許對角線移動：用傳統算法生成點，然後作爲後處理步驟插入進行正交運動所需的額外步驟。

Answer 3

有一個在GPU寶石提供了一個有趣的文章，也許它可以幫助你：Chapter 22. Fast Prefiltered Lines

Answer 4

你可以找到所有的射線具有與水平網格線的交叉點，然後標記的行中的所有細胞或者在一側有交叉點，或者在行上有交叉點的兩個單元之間。

通過從原點開始，將點前進到第一個交點（並標記過程中的單元格），找到將您從交點轉到下一個點的向量（這兩個操作都可以完成）是基本類似的三角形（或三角形）），然後逐列推進，直到你走得足夠遠。逐列推進涉及每列添加一個矢量，並且用一個小循環來填充具有交叉點的單元格之間的單元格。如果您正在處理單元格，請將「mark」替換爲「process」 - 此算法可確保僅標記每個單元格一次。

垂直線也可以做同樣的事情，但是網格通常存儲在水平切片中，所以我選擇了這個。如果您使用的是trig，則需要處理帶有特殊情況的直線水平線。

順便說一句，據我所知，這是基於網格的raycaster「3D」遊戲（如Wolfenstein 3D）已經完成了多久。我第一次從this book開始閱讀這個算法。

Answer 5

不失一般性，假設X2> = X1，然後

int x = floor(x1); 
int y = floor(y1); 
double slope = (x2 - x1)/(y2 - y1); 
if (y2 >= y1) { 
    while (y < y2) { 
    int r = floor(slope * (y - y1) + x1); 
    do { 
     usepixel(x, y); 
     ++x; 
    } while (x < r); 
    usepixel(x, y); 
    ++y; 
    } 
} 
else { 
    while (y > y2) { 
    int r = floor(slope * (y - y1) + x1); 
    do { 
     usepixel(x, y); 
     ++x; 
    } while (x < r); 
    usepixel(x, y); 
    --y; 
    } 
} 

的樓層呼叫大概可以寫，就像鑄造到整數。

Answer 6

這個線程歲，但我認爲這將會是值得把這個在互聯網上：

// This prints the pixels from (x, y), increasing by dx and dy. 
// Based on the DDA algorithm (uses floating point calculations). 
void pixelsAfter(int x, int y, int dx, int dy) 
{ 
    // Do not count pixels |dx|==|dy| diagonals twice: 
    int steps = Math.abs(dx) == Math.abs(dy) 
      ? Math.abs(dx) : Math.abs(dx) + Math.abs(dy); 
    double xPos = x; 
    double yPos = y; 
    double incX = (dx + 0.0d)/steps; 
    double incY = (dy + 0.0d)/steps; 
    System.out.println(String.format("The pixels after (%d,%d) are:", x, y)); 
    for(int k = 0; k < steps; k++) 
    { 
     xPos += incX; 
     yPos += incY; 
     System.out.println(String.format("A pixel (%d) after is (%d, %d)", 
      k + 1, (int)Math.floor(xPos), (int)Math.floor(yPos))); 
    } 
}