dibujar - caracteristicas del algoritmo de bresenham

¿Algoritmo rápido para dibujar círculos rellenos?

Question

Estoy usando el algoritmo de círculo de Bresenham para dibujar círculos rápidamente. Sin embargo, también quiero (a petición del usuario) dibujar un círculo relleno.

¿Hay una manera rápida y eficiente de hacer esto? ¿Algo parecido con Bresenham?

El lenguaje que estoy usando es C.

Answer 1

Aquí hay una guía aproximada de C # (no debería ser tan difícil obtener la idea correcta para C): esta es la forma "sin procesar" sin usar Bresenham para eliminar las raíces cuadradas repetidas.

Bitmap bmp = new Bitmap(200, 200);

int r = 50; // radius
int ox = 100, oy = 100; // origin

for (int x = -r; x < r ; x++)
{
    int height = (int)Math.Sqrt(r * r - x * x);

    for (int y = -height; y < height; y++)
        bmp.SetPixel(x + ox, y + oy, Color.Red);
}

bmp.Save(@"c:/users/dearwicker/Desktop/circle.bmp");

Answer 2

Así es como lo estoy haciendo:
Estoy usando valores de puntos fijos con dos bits de precisión (tenemos que administrar los puntos medios y los valores cuadrados de los puntos medios)
Como se mencionó en una respuesta anterior, también estoy usando valores cuadrados en lugar de raíces cuadradas.
Primero, estoy detectando el límite de borde de mi círculo en una porción de 1/8 del círculo. Estoy usando la simetría de estos puntos para dibujar los 4 "bordes" del círculo. Entonces estoy dibujando el cuadrado dentro del círculo.

A diferencia del algoritmo de círculo del punto medio , este funcionará con diámetros pares (y también con diámetros de números reales, con algunos pequeños cambios).

Por favor, perdóneme si mis explicaciones no fueron claras, soy francés;)

void DrawFilledCircle(int circleDiameter, int circlePosX, int circlePosY)
{
    const int FULL = (1 << 2);
    const int HALF = (FULL >> 1);

    int size = (circleDiameter << 2);// fixed point value for size
    int ray = (size >> 1);
    int dY2;
    int ray2 = ray * ray;
    int posmin,posmax;
    int Y,X;
    int x = ((circleDiameter&1)==1) ? ray : ray - HALF;
    int y = HALF;
    circlePosX -= (circleDiameter>>1);
    circlePosY -= (circleDiameter>>1);

    for (;; y+=FULL)
    {
        dY2 = (ray - y) * (ray - y);

        for (;; x-=FULL)
        {
            if (dY2 + (ray - x) * (ray - x) <= ray2) continue;

            if (x < y)
            {
                Y = (y >> 2);
                posmin = Y;
                posmax = circleDiameter - Y;

                // Draw inside square and leave
                while (Y < posmax)
                {
                    for (X = posmin; X < posmax; X++)
                        setPixel(circlePosX+X, circlePosY+Y);
                    Y++;
                }
                // Just for a better understanding, the while loop does the same thing as:
                // DrawSquare(circlePosX+Y, circlePosY+Y, circleDiameter - 2*Y);
                return;
            }

            // Draw the 4 borders
            X = (x >> 2) + 1;
            Y = y >> 2;
            posmax = circleDiameter - X;
            int mirrorY = circleDiameter - Y - 1;

            while (X < posmax)
            {
                setPixel(circlePosX+X, circlePosY+Y);
                setPixel(circlePosX+X, circlePosY+mirrorY);
                setPixel(circlePosX+Y, circlePosY+X);
                setPixel(circlePosX+mirrorY, circlePosY+X);
                X++;
            }
            // Just for a better understanding, the while loop does the same thing as:
            // int lineSize = circleDiameter - X*2;
            // Upper border:
            // DrawHorizontalLine(circlePosX+X, circlePosY+Y, lineSize);
            // Lower border:
            // DrawHorizontalLine(circlePosX+X, circlePosY+mirrorY, lineSize);
            // Left border:
            // DrawVerticalLine(circlePosX+Y, circlePosY+X, lineSize);
            // Right border:
            // DrawVerticalLine(circlePosX+mirrorY, circlePosY+X, lineSize);

            break;
        }
    }
}

void DrawSquare(int x, int y, int size)
{
    for( int i=0 ; i<size ; i++ )
        DrawHorizontalLine(x, y+i, size);
}

void DrawHorizontalLine(int x, int y, int width)
{
    for(int i=0 ; i<width ; i++ )
        SetPixel(x+i, y);
}

void DrawVerticalLine(int x, int y, int height)
{
    for(int i=0 ; i<height ; i++ )
        SetPixel(x, y+i);
}

Para usar un diámetro no entero, puede aumentar la precisión del punto fijo o usar valores dobles. Incluso debería ser posible hacer un tipo de anti-alias dependiendo de la diferencia entre dY2 + (ray - x) * (ray - x) y ray2 (dx² + dy² y r²)

Answer 3

Habiendo leído la página de Wikipedia en el algoritmo de círculo de Bresenham (también ''Punto medio'') , parecería que lo más fácil sería modificar sus acciones, de modo que en lugar de

setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);

Y similar, cada vez que lo hagas

lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);

Es decir, para cada par de puntos (con la misma y ) que Bresenham le haría trazar , en su lugar, conecte con una línea .

Answer 4

Me gusta la respuesta de palm3D. Por ser una fuerza bruta, esta es una solución sorprendentemente rápida. No hay raíz cuadrada o funciones trigonométricas para frenarla. Su única debilidad es el bucle anidado.

Convertir esto en un solo bucle hace que esta función sea casi el doble de rápida.

int r2 = r * r;
int area = r2 << 2;
int rr = r << 1;

for (int i = 0; i < area; i++)
{
    int tx = (i % rr) - r;
    int ty = (i / rr) - r;

    if (tx * tx + ty * ty <= r2)
        SetPixel(x + tx, y + ty, c);
}

Esta solución de un solo bucle rivaliza con la eficiencia de una solución de dibujo lineal.

            int r2 = r * r;
            for (int cy = -r; cy <= r; cy++)
            {
                int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5);
                int cyy = cy + y;

                lineDDA(x - cx, cyy, x + cx, cyy, c);
            }

Answer 5

Puedes usar esto:

void DrawFilledCircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int xChange = 1 - (radius << 1);
    int yChange = 0;
    int radiusError = 0;

    while (x >= y)
    {
        for (int i = x0 - x; i <= x0 + x; i++)
        {
            SetPixel(i, y0 + y);
            SetPixel(i, y0 - y);
        }
        for (int i = x0 - y; i <= x0 + y; i++)
        {
            SetPixel(i, y0 + x);
            SetPixel(i, y0 - x);
        }

        y++;
        radiusError += yChange;
        yChange += 2;
        if (((radiusError << 1) + xChange) > 0)
        {
            x--;
            radiusError += xChange;
            xChange += 2;
        }
    }
}

Answer 6

Si desea un algoritmo rápido, considere dibujar un polígono con N lados, cuanto más alto sea N, más preciso será el círculo.

Answer 7

Solo generaría una lista de puntos y luego usaría una función de dibujo de polígono para el renderizado.

Answer 8

Solo usa la fuerza bruta. Este método se repite en demasiados píxeles, pero solo utiliza multiplicaciones de enteros y adiciones. Evita por completo la complejidad de Bresenham y el posible cuello de botella de sqrt.

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);