[alg] 畫線- bresenhan & 吳小林

Bresenham

• 概念: 什麼時候y會增加1(可以處理無法整除的誤差問題　循環誤差問題)
• AAC stsc無法整除問題( chunk duration: 500ms, samples per chunk: 48000*0.5/1024=23.4375)，套用bresenham演算法即 試(chunkId, sampleTotal)，如下改成(chunkId, sample per chunk)

pseudo code:

     gradient = 23.4375

     LOOP x, Xstart to Xend

          tmp = x*gradient-x*roundOff(gradient)

          y[i] = tmp - INT(tmp ) < 0.5  ?  roundOff(gradient) : roundup(gradient);

輸出：

x	1	2	3	4
tmp	0.4	0.9	1.3	2.2
y	23	24	23	24

吴小林直线算法(抗鋸齒線性算法)

• 概念: y在此x時要畫多深的顏色(y小數點越大顏色越深)

藉由畫不同的深淺來使鋸齒狀不要那麼明顯，畫兩個像素點在岔在直線兩邊，並按照直線相近的顏色著色，而線段末端的像素點另外處理。如果線段寬度小於一像素，將會被作為特殊情況考慮。

假設 start(0,0) -> end(10,4)

function drawLine(x1,y1,x2,y2)
    dx = x2 - x1//10
    dy = y2 - y1//4
    if abs(dx) < abs(dy) then                
      swap x1, y1
      swap x2, y2
      swap dx, dy    end if
    if x2 < x1
      swap x1, x2
      swap y1, y2
    end if

    gradient = dy / dx //0.4
   
    // 1. handle first endpoint
    xend = round(x1) // 0
    yend = y1 + gradient * (xend - x1) // 0
    xgap = rfpart(x1 + 0.5) // 5

x1小數點	0	1	2	3	4	5	6	7	8	9
xgap	5	4	3	2	1	0	9	8	7	6

    xpxl1 = xend  // this will be used in the main loop//0
    ypxl1 = ipart(yend) //0

    plot(xpxl1, ypxl1, rfpart(yend) * xgap)//(0,0,5)    //(10,4, 9*4=36) //離整數越接近顏色越深, 假設是10.1, 那麼在0這條線就要x9, 1這條就x1
    plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap)//(0,1,0) //(10,5, 1*4=4)

    intery = yend + gradient // first y-intersection for the main loop//0.4
   
    // handle second endpoint
    xend = round (x2)//10
    yend = y2 + gradient * (xend - x2)//4
    xgap = fpart(x2 + 0.5)//5

x(fraction)	0	1	2	3	4	5	6	7	8	9
xgap	5	6	7	8	9	0	1	2	3	4

    xpxl2 = xend  // this will be used in the main loop//4
    ypxl2 = ipart (yend)//10
    plot (xpxl2, ypxl2, rfpart (yend) * xgap)//(10,4,5)
    plot (xpxl2, ypxl2 + 1, fpart (yend) * xgap)//(10,5,0)
   
    // main loop //什麼時後跳Y，Y的比重有多少

    for x from xpxl1 + 1 to xpxl2 - 1 do //x 1~9
        plot (x, ipart (intery), rfpart (intery)) //(1,0,6) ,(2,0,2),(3,1,8)
        plot (x, ipart (intery) + 1, fpart (intery))//(1,1,4),(2,1,8),(3,2,2)

   intery = intery + gradient //

            end function

4
3
2				8(2)
1	2(0)	4(4)	6(8)	7(8)
0	1(5)	3(6)	5(2)
y/x 座標	0	1	2	3

輸出:  order(顏色深淺)