C++ L'algoritmo della linea di Bresenham disegna un arco e ruota

Question

Sto cercando un modo per creare un arco con l'algoritmo di linea di Bresenham. Questo algoritmo disegna un cerchio perfetto, ma cosa succede se ho bisogno di disegnare un arco (da 0 a Pi) e ruotarlo di 30 gradi (per esempio)?

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

Per ottenere 1/2 cerchio (in pi), chiamare solo una delle routine di SetPixel. Per far ruotare il tuo arco di 30 gradi è necessario un certo trigbo. Potresti lasciare che il ciclo precedente funzioni finché il tuo rapporto x/y è uguale a tan (30 gradi), quindi inizia effettivamente a disegnare finché il tuo rapporto non raggiunge il valore a cui vuoi fermarti. Non è il modo più efficiente, ma funzionerà. Per migliorarlo, è necessario calcolare preventivamente i 4 valori var iniziali. Puoi prendere i valori dalla corsa precedente e collegarli come valori iniziali e sarebbe molto efficiente.

Hai ricevuto l'algoritmo di cui sopra dal materiale Michael Abrash's Black Book? In caso contrario, mi piacerebbe google per questo come un secondo punto di riferimento sul disegno circolare/arco veloce.

Beh, ahimè, le ellissi che strappano il capitolo non sono state incluse. Ecco qualcosa che ho trovato sul web che sostiene di essere da 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); 
    } 
} 

L'idea è che si disegna un 8 ° del cerchio in un x4 volta e poi capovolgere per ottenere le altre 8ths disegnati. Tuttavia, non risponde direttamente alla tua domanda. Lavorando su questo ...

Ancora, il codice sopra dovrebbe funzionare, devi solo controllare attentamente le condizioni di partenza e di arrivo. Il y> = 0 deve diventare qualsiasi cosa che avresti dopo aver terminato la tua lunghezza 'arco' e i valori iniziali devono essere calcolati per essere l'inizio dell'arco.

Questo non sarà un compito semplice con le cose come sono. Potrebbe essere più semplice usare una routine a virgola mobile. La matematica è molto più semplice e i processori tendono a gestirli meglio ora rispetto a quando queste routine intere sono state create.

Answer 2

Se non avete bisogno di sicuro Bresenham, c'è un veloce metodo passo introdotto in this SO post, dove è possibile impostare il punto centrale, punto di partenza e l'angolo dell'arco. Non ha bisogno di fermare il criterio, perché è già incluso nell'algoritmo (per angolo d'arco). Ciò che lo rende veloce è il calcolo preliminare dei fattori di movimento tangenziale e radiale e il ciclo reale non ha chiamate di funzioni trigonometriche, ma solo moltiplicare, aggiungere e sottrarre.

per quanto ne so non c'è tre tipi di metodi:
A) incrementali come Bresenham
B) Suddividere metodo come this
C Step) (o segmento) Metodo

Prenderò un lento esempio di passo metodo (non utilizzare questo se la velocità è importante):

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

La lentezza deriva dal cos e il peccato che si ripetono (inutilmente) in loop. Questo può essere risolto precalcolando cos e sin come descritto nel post SO sopra menzionato. Ciò significa un enorme aumento della velocità (media 12x nei motori top5 javascript).

Ho creato uno speedtest non completo di vari algoritmi di cerchio e arco. Il Bresenham è veloce, ma bisogna aggiungere la logica del criterio di partenza e di arresto, che rallenta un po 'l'algo. Se davvero hai bisogno di Bresenham e Arc, non ho una soluzione pronta per questo e non ho ancora trovato tale. È sicuramente possibile.A proposito, il metodo step che utilizza trigonomi precalcolati non è così male nelle prestazioni rispetto a Bresenham (almeno in javascript). Si prega di testare in C++ e report.