algorithme rapide pour dessiner des cercles remplis?

Question

J'utilise l'algorithme du cercle de Bresenham pour le tracé rapide d'un cercle. Cependant, je souhaite également (à la demande de l'utilisateur) tracer un cercle rempli.

Existe-t-il un moyen rapide et efficace de procéder? Quelque chose dans le même sens que Bresenham?

Le langage que j'utilise est le C.

Answer 1

Après avoir lu la page Wikipedia sur l'algorithme de cercle de Bresenham (également appelé 'Midpoint') , semble que la chose la plus facile à faire serait de modifier ses actions, de telle sorte qu'au lieu de

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

et similaire, chaque fois que vous faites plutôt

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

C’est-à-dire que, pour chaque paire de points (avec le même y ) que Bresenham vous auriez votre tracé , vous connectez-vous avec une ligne .

Answer 2

Utilisez simplement la force brute. Cette méthode itère sur un trop grand nombre de pixels, mais utilise uniquement des multiplications et des ajouts d’entiers. Vous évitez complètement la complexité de Bresenham et l'éventuel goulot d'étranglement 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);

Answer 3

Voici un guide approximatif en C # (cela ne devrait pas être si difficile d’obtenir la bonne idée pour C) - c’est le "brut". forme sans utiliser Bresenham pour éliminer les racines carrées répétées.

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 4

Vous pouvez utiliser ceci:

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 5

J'aime la réponse de palm3D. Pour être force brute, c'est une solution incroyablement rapide. Il n'y a pas de fonction racine carrée ou de fonction trigonométrique pour le ralentir. Sa seule faiblesse est la boucle imbriquée.

En convertissant cela en une seule boucle, cette fonction est presque deux fois plus rapide.

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

Cette solution en boucle unique rivalise avec l’efficacité d’une solution de dessin au trait.

            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 6

Voici comment je le fais:
J'utilise des valeurs de points fixes avec une précision de deux bits (nous devons gérer des demi-points et des valeurs carrées de demi-points)

Comme mentionné dans une réponse précédente, j'utilise également des valeurs carrées au lieu de racines carrées.
Premièrement, je détecte la limite de la frontière de mon cercle dans une portion du 1/8 du cercle. J'utilise symétrique de ces points pour dessiner les 4 "frontières". du cercle. Ensuite, je dessine le carré à l'intérieur du cercle.

Contrairement à l’algorithme cercle de point médian , celui-ci fonctionnera avec des diamètres pairs (et avec des diamètres de nombres réels également, avec quelques modifications mineures).

S'il vous plaît, pardonnez-moi si mes explications n'étaient pas claires, je suis française;)

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

Pour utiliser un diamètre non entier, vous pouvez augmenter la précision du point fixe ou utiliser des valeurs doubles. Il devrait même être possible de faire une sorte d'anti-alias en fonction de la différence entre dY2 + (rayon - x) * (rayon - x) et rayon2 (dx² + dy² et r²)

Answer 7

Si vous voulez un algorithme rapide, envisagez de dessiner un polygone avec N côtés, plus le N est haut, plus le cercle sera précis.

Answer 8

L’algorithme de force brute de palm3D a été un bon point de départ. Cette méthode utilise le même principe, mais elle inclut plusieurs manières d’ignorer la plupart des pixels.

D'abord, voici le code:

int largestX = circle.radius;
for (int y = 0; y <= radius; ++y) {
    for (int x = largestX; x >= 0; --x) {
        if ((x * x) + (y * y) <= (circle.radius * circle.radius)) {
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y + y);
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y - y);
            largestX = x;
            break; // go to next y coordinate
        }
    }
}

Ensuite, l'explication.

La première chose à noter est que si vous trouvez la coordonnée x minimale comprise dans le cercle pour une ligne horizontale donnée, vous connaissez immédiatement la coordonnée x maximale. Cela est dû à la symétrie du cercle. Si la coordonnée x minimale est de 10 pixels devant la gauche du cadre de sélection du cercle, le maximum de x se trouve 10 pixels derrière la droite du cadre de sélection du cercle.

La raison pour passer d'une valeur x élevée à une valeur x faible est que la valeur x minimale sera trouvée avec moins d'itérations. Cela est dû au fait que la valeur minimale de x est plus proche de la gauche du cadre de sélection que de la coordonnée centrale du cercle pour la plupart des lignes, car le cercle est courbé vers l'extérieur, comme indiqué sur cette image La prochaine chose à noter est que puisque le cercle est aussi symétrique verticalement, chaque ligne trouvée vous donne une seconde ligne libre à tracer. Chaque fois que vous trouvez une ligne dans la moitié supérieure du cercle, vous en obtenez une dans la moitié inférieure. la coordonnée rayon-y. Par conséquent, chaque fois qu'une ligne est trouvée, deux peuvent être dessinés et seule la moitié supérieure des valeurs y doit être itérée.

La dernière chose à noter est que si vous commencez par une valeur située au centre du cercle, puis que vous vous dirigez vers le haut pour y, la valeur minimale de x pour chaque ligne suivante doit être plus proche du centre. Coordonnée x du cercle que la dernière ligne. Cela est également dû au fait que le cercle se recourbe plus près de la valeur centrale x lorsque vous remontez le cercle. Voici un aperçu de la situation.

En résumé:

1. Si vous trouvez la coordonnée x minimale d'une ligne, vous obtenez gratuitement la coordonnée x maximale.
2. Chaque ligne que vous trouvez à dessiner sur la moitié supérieure du cercle vous donne une ligne gratuite sur la moitié inférieure du cercle.
3. Chaque coordonnée x minimale doit être plus proche du centre du cercle que la coordonnée x précédente pour chaque ligne lors de l'itération de la coordonnée y centrale vers le haut.

Vous pouvez également stocker la valeur de (rayon * rayon) , ainsi que (y * y) au lieu de les calculer.  plusieurs fois.

Answer 9

Je voudrais simplement générer une liste de points, puis utiliser une fonction de dessin de polygone pour le rendu.