C++ Thuật toán dòng của Bresenham vẽ vòng cung và xoay

Question

Tôi đang tìm cách tạo vòng cung bằng thuật toán dòng của Bresenham. Algoritm vẽ vòng tròn hoàn hảo, nhưng nếu tôi cần vẽ vòng cung (từ 0 đến Pi) và xoay nó cho 30 độ (ví dụ)?

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

Để nhận 1/2 vòng tròn (thành pi), chỉ cần gọi một trong các thói quen SetPixel của bạn. Để có vòng cung của bạn xoay 30 độ đòi hỏi một số trig. Bạn có thể để vòng lặp trên chạy cho đến khi tỷ lệ x/y của bạn bằng tan (30 độ), sau đó bắt đầu thực sự vẽ cho đến khi tỷ lệ của bạn đạt đến giá trị mà bạn muốn dừng. Không phải là cách hiệu quả nhất, nhưng nó sẽ hoạt động. Để làm cho nó tốt hơn, bạn cần phải tính toán trước 4 giá trị var bắt đầu của mình. Bạn có thể lấy các giá trị từ chạy trên và cắm chúng vào như các giá trị bắt đầu và điều đó sẽ rất hiệu quả.

Bạn có nhận được thuật toán trên từ Michael Abrash's Black Book nội dung không? Nếu không, tôi sẽ google cho rằng như là một điểm thứ hai của tài liệu tham khảo về vòng tròn nhanh/vòng cung vẽ.

Vâng, than ôi, các hình elip trích xuất chương không được bao gồm trong đó. Dưới đây là một cái gì đó tôi tìm thấy trên web mà tuyên bố là từ 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); 
    } 
} 

Ý tưởng là bạn vẽ một thứ 8 của vòng tròn tại một x4 thời gian và sau đó lật để có được những 8ths khác rút ra. Tuy nhiên, không trực tiếp trả lời câu hỏi của bạn. Làm việc trên đó ...

Một lần nữa, mã của bạn ở trên sẽ hoạt động, bạn chỉ cần kiểm soát cẩn thận điều kiện bắt đầu và kết thúc. Y> = 0 cần phải trở thành bất cứ điều gì y sẽ được khi kết thúc chiều dài 'arc' của bạn và các giá trị bắt đầu cần phải được tính toán để được bắt đầu của vòng cung của bạn.

Đây sẽ không phải là một nhiệm vụ thẳng về phía trước với những thứ giống như chúng. Chỉ có thể dễ dàng hơn để sử dụng một thói quen dấu chấm động thay thế. Toán học là nhiều hơn nữa thẳng về phía trước và bộ vi xử lý có xu hướng xử lý chúng tốt hơn bây giờ hơn khi các thói quen số nguyên được chế tác.

Answer 2

Nếu bạn không cần phải chắc chắn Bresenham, có một nhanh bước phương pháp giới thiệu in this SO post, nơi bạn có thể thiết lập điểm trung tâm, điểm bắt đầu và góc hồ quang. Nó không cần tiêu chí dừng, bởi vì nó đã được bao gồm trong thuật toán (bởi góc hồ quang). Điều gì làm cho nó nhanh chóng là precalculation của các yếu tố chuyển động tiếp tuyến và xuyên tâm và vòng lặp thực tế không có cuộc gọi chức năng trig, chỉ nhân, cộng và trừ.

AFAIK có ba loại phương pháp:
A) cộng dồn như Bresenham
B) Chia nhỏ phương pháp như this
C) Bước (hoặc phân khúc) phương pháp

Tôi sẽ lấy một ví dụ chậm bước phương pháp (không sử dụng này nếu tốc độ là quan trọng):

// 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) 
} 

Các sự chậm chạp đến từ cos và tội lỗi được lặp đi lặp lại (không cần thiết) trong vòng lặp. Điều này có thể được giải quyết bằng cách tính toán cos và sin như mô tả trong bài viết SO đã đề cập ở trên. Điều này có nghĩa là tăng tốc rất lớn (trung bình 12x trong các công cụ javascript top5).

Tôi đã thực hiện một không đầy đủ so sánh speedtest các thuật toán vẽ vòng tròn và hình cung khác nhau. Bresenham nhanh, nhưng logic bắt đầu và dừng lại cần phải được thêm vào, điều này làm chậm bản ngã một chút. Nếu bạn thực sự cần Bresenham và vòng cung, tôi không có giải pháp sẵn sàng cho điều này và không tìm thấy như vậy được nêu ra. Nó chắc chắn là có thể.Bằng cách này, phương pháp bước bằng cách sử dụng trigal được tính toán trước không phải là quá xấu trong hiệu suất so với Bresenham (trong javascript ít nhất). Vui lòng kiểm tra trong c + + và báo cáo.