尋找一個快速概述的線條渲染算法

我正在尋找一個快速的算法來繪製一個概述的線條。對於這個應用程序，輪廓只需要1個像素寬。無論是默認還是通過選項，應該可以使兩條線無縫連接在一起，如果它們有共同點。尋找一個快速概述的線條渲染算法

打擾ASCII藝術，但這可能是證明它的最好方法。

法線：

## 
    ## 
    ## 
     ## 
     ## 
      ##

「概述」行：

** 
*##** 
**##** 
    **##** 
    **##** 
     **##** 
     **##* 
      **

我工作的一個dsPIC33FJ128GP802。它是一個小型的微控制器/數字信號處理器，能夠達到40MIPS（每秒百萬條指令）。它只能進行整數運算（加法，減法和乘法：可以進行除法運算，但需要約19個週期）。同時處理OSD層，處理時間只有3-4 MIPS可用於計算，因此速度至關重要。像素佔據三種狀態：黑色，白色和透明;視頻領域是192x128像素。這是一個開源項目的超級OSD：http://code.google.com/p/super-osd/

我想到的第一個解決方案是在第一遍繪製3x3矩形的輪廓像素和第二遍的常規像素，但這可能會很慢，至於每個像素至少有3個像素被覆蓋，花費在繪製它們上的時間被浪費。所以我正在尋找更快的方法。每個像素花費大約30個週期。目標是< 50,000個週期繪製一條100像素長度的線。

來源

2010-10-11 Thomas O

我不認爲[如何使用Bresenham創建任意厚度的線？]（http://stackoverflow.com/questions/1222713/how-do-i-create-a-line-of-任意厚度使用bresenham）是重複的，但它可能是相關的。 – dmckee 2010-10-11 17:30:30

+1感謝您的鏈接。這涉及到輪廓線，所以我正在尋找一種用邊框繪製線條的有效方法。畫一條粗線然後細線與我給出的選項基本相同。 – 2010-10-11 17:33:43

線寬是1像素嗎？ – ybungalobill 2010-10-12 10:53:50

我的建議是（C /僞混合）：

void draw_outline(int x1, int y1, int x2, int y2) 
{ 
    int x, y; 
    double slope; 

    if (abs(x2-x1) >= abs(y2-y1)) { 
     // line closer to horizontal than vertical 
     if (x2 < x1) swap_points(1, 2); 
     // now x1 <= x2 
     slope = 1.0*(y2-y1)/(x2-x1); 
     draw_pixel(x1-1, y1, '*'); 
     for (x = x1; x <= x2; x++) { 
      y = y1 + round(slope*(x-x1)); 
      draw_pixel(x, y-1, '*'); 
      draw_pixel(x, y+1, '*'); 
      // here draw_line() does draw_pixel(x, y, '#'); 
     } 
     draw_pixel(x2+1, y2, '*'); 
    } 
    else { 
     // same as above, but swap x and y 
    } 
}

編輯：如果你想有連續線無縫連接，我覺得你真的要畫在第一遍的所有輪廓，然後然後行。我編輯了上面的代碼只繪製了輪廓。 draw_line()函數將完全相同，但只有一個單獨的 draw_pixel(x, y, '#');而不是四個draw_pixel(..., ..., '*');。然後你只是：

void draw_polyline(point p[], int n) 
{ 
    int i; 

    for (i = 0; i < n-1; i++) 
     draw_outline(p[i].x, p[i].y, p[i+1].x, p[i+1].y); 
    for (i = 0; i < n-1; i++) 
     draw_line(p[i].x, p[i].y, p[i+1].x, p[i+1].y); 
}

來源

2010-10-12 20:23:38

這基本上就是它 - 這個例子不使用快速Bresenham算法，但這個想法可以適應。用文字而不是僞碼：每個「行」像素需要上下左右的「輪廓」像素。因此，對於每個水平線段，將一個輪廓像素放在左側，沿線段繪製線條並在上方+下方畫出輪廓線，然後將輪廓像素放在右側。類似的下一個水平段。但是您可以優化，因爲此水平線段的頂部邊框與最後一個邊線的右邊線重疊，所以您只需爲第一個/最後一個線段執行L/R像素。 – psmears 2010-10-12 21:47:47

@psmears：您確實想繪製所有線段的左/右邊框，因爲您可能有從左到右的線段，然後是從右到左的線段，例如在繪製類似'>'符號的圖形時。 – 2010-10-13 12:23:42

如果處理器不能在硬件中進行浮點運算，我會改用固定點來計算斜率。然後，假設你可以爲小數部分預留16位，那麼y的計算就會變成：'hi_res_y + = slope; y = hi_res_y >> 16;'。這只是一個添加和一個位的轉變。我會初始化'hi_res_y =（y << 16）+ 0x8000'爲了得到正確的runding。 – 2010-10-13 12:25:00

我的方法是使用布氏來畫多條。看看你的ASCII藝術，你會注意到輪廓線與Bresenham線相同，只是向上和向下移動了1個像素 - 在第一個點的左邊和最後一個右邊加上了一個像素。

對於通用版本，您需要確定您的生產線是平坦還是陡峭 - 即是否爲abs(y1 - y0) <= abs(x1 - x0)。對於陡峭的線條，輪廓向左和向右移動1個像素，並且關閉像素在起點之上和終點之下。

這可能是值得優化的，通過繪製線條和兩個輪廓像素一次爲每一行像素。但是，如果您需要無縫輪廓，最簡單的解決方案是首先繪製所有輪廓，然後繪製線條 - 這不適用於「三像素Bresenham」優化。

來源

2015-03-01 13:31:53

尋找一個快速概述的線條渲染算法

回答

相關問題