C++ Bresenham的線算法繪製弧和旋轉

Question

我正在尋找使用Bresenham的線算法制作弧的方法。這個算法繪製完美的圓形，但是如果我需要繪製圓弧（從0到Pi）並將其旋轉30度（例如）？

void DrawCircle(HDC hdc,int x0, int y0, int radius) 
{ 
     int x = 0; 
     int y = radius; 
     int delta = 2 - 2 * radius; 
     int error = 0; 

     while(y >= 0) { 
       //SetPixel(hdc,x0 + x, y0 + y,pencol); 
       SetPixel(hdc,x0 + x, y0 - y,pencol); 
       //SetPixel(hdc,x0 - x, y0 + y,pencol); 
       SetPixel(hdc,x0 - x, y0 - y,pencol); 
       error = 2 * (delta + y) - 1; 
       if(delta < 0 && error <= 0) { 
         ++x; 
         delta += 2 * x + 1; 
         continue; 
       } 
       error = 2 * (delta - x) - 1; 
       if(delta > 0 && error > 0) { 
         --y; 
         delta += 1 - 2 * y; 
         continue; 
       } 
       ++x; 
       delta += 2 * (x - y); 
       --y; 
     } 
} 

Answer 1

要獲得1/2的圓圈（對於pi），只能調用其中一個SetPixel例程。要使弧形旋轉30度需要一些觸發。你可以讓上面的循環運行，直到你的x/y比率等於tan（30度），然後開始實際繪製直到你的比例達到你想停止的值。不是最有效的方式，但它會起作用。爲了讓它更好，你需要預先計算你的起始4個var值。你可以從上面的運行中取值，並將它們作爲起始值插入，這將是非常有效的。

你從Michael Abrash's Black Book東西得到了上述算法嗎？如果沒有，我會爲此作爲快速圓/弧繪圖的第二參考點。

那麼，唉，撕裂章節的橢圓不包括在那裏。這裏的東西我聲稱是從Abrash在網絡上找到：

/* One of Abrash's ellipse algorithms */ 

void draw_ellipse(int x, int y, int a, int b, int color) 
{ 
    int wx, wy; 
    int thresh; 
    int asq = a * a; 
    int bsq = b * b; 
    int xa, ya; 

    draw_pixel(x, y+b, color); 
    draw_pixel(x, y-b, color); 

    wx = 0; 
    wy = b; 
    xa = 0; 
    ya = asq * 2 * b; 
    thresh = asq/4 - asq * b; 

    for (;;) { 
     thresh += xa + bsq; 

     if (thresh >= 0) { 
      ya -= asq * 2; 
      thresh -= ya; 
      wy--; 
     } 

     xa += bsq * 2; 
     wx++; 

     if (xa >= ya) 
      break; 


     draw_pixel(x+wx, y-wy, color); 
     draw_pixel(x-wx, y-wy, color); 
     draw_pixel(x+wx, y+wy, color); 
     draw_pixel(x-wx, y+wy, color); 
    } 

    draw_pixel(x+a, y, color); 
    draw_pixel(x-a, y, color); 

    wx = a; 
    wy = 0; 
    xa = bsq * 2 * a; 

    ya = 0; 
    thresh = bsq/4 - bsq * a; 

    for (;;) { 
     thresh += ya + asq; 

     if (thresh >= 0) { 
      xa -= bsq * 2; 
      thresh = thresh - xa; 
      wx--; 
     } 

     ya += asq * 2; 
     wy++; 

     if (ya > xa) 
      break; 

     draw_pixel(x+wx, y-wy, color); 
     draw_pixel(x-wx, y-wy, color); 
     draw_pixel(x+wx, y+wy, color); 
     draw_pixel(x-wx, y+wy, color); 
    } 
} 

的想法是，你在一個時間X4繪製圓的8，然後翻轉得到繪製的3/8等。儘管如此，仍然不直接回答你的問題。正在處理...

同樣，您的代碼應該可以工作，您只需要仔細控制開始和結束條件。在完成「弧長」時，y> = 0需要變爲y，並且需要將起始值計算爲弧的起點。

這不會是一件簡單的事情。可能更容易使用浮點數例程。數學更直接，處理器傾向於更好地處理它們，比起這些整型例程製作得更好。

Answer 2

如果你不需要肯定布氏，有介紹in this SO post，在這裏你可以設置中心點，起點和圓弧角快速步法。它不需要停止標準，因爲它已包含在算法中（以弧角表示）。最快速的是預先計算切向和徑向移動因子，而實際的循環沒有三角函數調用，只能進行乘法，加法和減法。

AFAIK有三種類型的方法：
A）增量等的Bresenham
B）細分方法等this
C）步驟（或段）方法

我會採取步驟的一個例子緩慢方法（如果速度是重要的不使用此）：

// I know the question is tagged c++, but the idea comes clear in javascript 
var start_angle = 0.5, end_angle = 1.1, r = 30; 
for(var i = start_angle; i < end_angle; i = i + 0.05) 
{ 
    drawpixel(50 + Math.cos(i) * r, y: 100 + Math.sin(i) * r); // center point is (50,100) 
} 

的緩慢來自哪個重複（不必要的）在環COS和sin。這可以通過按照上述SO帖子中所述預先計算cos和sin來解決。這意味着巨大的加速（在top5 javascript引擎中平均12倍）。

我做了一個非完全可比的speedtest的各種圓弧和弧線繪製算法。 Bresenham速度很快，但需要添加啓動和停止標準邏輯，這會減慢算法的速度。如果你真的需要Bresenham和弧線，我還沒有現成的解決方案，但還沒有找到。這當然是可能的。順便說一句，與Bresenham相比，使用預先計算的trig的步驟方法性能並不差（至少在javascript中）。請用C++測試並報告。