C++ algoritmo de línea de Bresenham dibujar arco y rotar

Question

Estoy buscando la forma de hacer arco con el algoritmo de línea de Bresenham. Este algoritmo dibuja un círculo perfecto, pero ¿y si necesito dibujar un arco (de 0 a Pi) y rotarlo a 30 grados (por ejemplo)?

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

Para obtener 1/2 círculo (a pi), solo llame a una de sus rutinas SetPixel. Para que su arco gire 30 grados requiere algo de trigonometría. Puedes dejar que el ciclo anterior se ejecute hasta que tu relación x/y sea igual a tan (30 grados), y luego empieces a dibujar realmente hasta que tu relación alcance el valor que deseas detener. No es la forma más eficiente, pero funcionará. Para hacerlo mejor, necesitarás precalcular tus valores iniciales de var. Puede tomar los valores de la ejecución anterior y conectarlos como valores iniciales y eso sería muy eficiente.

¿Obtuvo el algoritmo anterior de Michael Abrash's Black Book cosas? Si no, buscaría eso como segundo punto de referencia en el dibujo rápido de círculo/arco.

Bueno, por desgracia, las elipsis que rasgar el capítulo no se incluyeron allí. Aquí hay algo que encontré en la web que dice ser de 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); 
    } 
} 

La idea es dibujar un octavo del círculo en un x4 tiempo y luego se da la vuelta para conseguir las otras 8ths dibujados. Aún así, no responde directamente a tu pregunta. Trabajando en eso ...

De nuevo, su código anterior debería funcionar, solo necesita controlar las condiciones de inicio y finalización con cuidado. El y> = 0 necesita convertirse en lo que sea y cuando termine la longitud de su "arco" y los valores iniciales deben calcularse para que sean el inicio de su arco.

Esta no será una tarea sencilla con las cosas como son. Podría ser más fácil usar una rutina de punto flotante en su lugar. La matemática es mucho más directa y los procesadores tienden a manejarlos mejor ahora que cuando estas rutinas enteras fueron creadas.

Answer 2

Si no es necesario para asegurarse de Bresenham, hay un método rápido paso introducido in this SO post, donde se puede establecer punto central, punto de partida y el ángulo del arco. No es necesario detener el criterio, porque ya está incluido en el algoritmo (por ángulo de arco). Lo que lo hace rápido es el cálculo previo de los factores de movimiento tangenciales y radiales y el ciclo real no tiene llamadas a la función trigonométrica, solo multiplica, suma y resta.

AFAIK hay tres tipos de métodos:
A) incrementales como Bresenham
B) Subdivida método como this
C) Paso (o segmento) método

Voy a tomar un ejemplo lenta de paso método (no utilizar esto si la velocidad es 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 lentitud viene de COS y sin que se repiten (innecesariamente) en bucle. Esto se puede resolver calculando el cos y el pecado previamente, tal como se describe en la publicación SO anteriormente mencionada. Esto significa una gran aceleración (promedio de 12x en los principales motores de JavaScript).

Hice un speedtest no completo comparable de varios algoritmos de dibujo de círculos y arcos. El Bresenham es rápido, pero es necesario agregar la lógica de los criterios de inicio y finalización, lo que ralentiza un poco el algoritmo. Si realmente necesita Bresenham y arco, no tengo una solución preparada para esto y todavía no la encuentro. Seguramente es posible.Por cierto, el método de paso usando trigonométricos precalculados no es tan malo en el rendimiento en comparación con Bresenham (en javascript al menos). Por favor prueba en C++ e informa.