4
votes

L'algorithme de cercle Xiaolin Wu rend le cercle avec des trous à l'intérieur

J'ai implémenté l'algorithme de cercle Xiaolin Wu à partir d'ici: https: //create.stephan -brumme.com/antialias-circle/ en c ++:

void setPixel4(int x, int y, int deltaX, int deltaY, int r, int g, int b, int a, int radius, int maxRadius, unsigned char* data, unsigned char* areasData, bool blendColor) {

    for(int j = 0; j < 4; j++) {

        int px, py;
        if(j == 0) {
            px = x + deltaX;
            py = y + deltaY;
        } else if(j == 1) {
            px = x - deltaX;
            py = y + deltaY;
        } else if(j == 2) {
            px = x + deltaX;
            py = y - deltaY;
        } else if(j == 3) {
            px = x - deltaX;
            py = y - deltaY;
        }

        int index = (px + (img->getHeight() - py - 1) * img->getWidth()) * 4;

        bool alreadyInBuffer = false;
        for(int i = 0; i < dfBufferCounter; i++) {
            if(i >= DRAW_FILLED_CIRCLE_BUFFER_SIZE) break;
            if(drawFilledCircleBuffer[i] == index) {
                alreadyInBuffer = true;
                break;
            }
        }

        if(!alreadyInBuffer) {
            if(dfBufferCounter < DRAW_FILLED_CIRCLE_BUFFER_SIZE) {
                drawFilledCircleBuffer[dfBufferCounter++] = index;
            }

            setPixelWithCheckingArea(px, py, r, g, b, a, data, areasData, blendColor);
        }
    }

}

x, y sont les coordonnées du centre du cercle.

À mon avis, ça ressemble très bien:

 entrez la description de l'image ici

Cependant, j'ai besoin d'un cercle à remplir. Je me trompe peut-être, mais j'ai développé un algorithme simple: itérer de 1 à rayon et dessiner simplement un cercle. Cela ressemble à ceci:

 entrez la description de l'image ici

Étrange. Donc, pour résoudre ce problème, je règle également la transparence au maximum jusqu'à ce que j'atteigne le dernier rayon (donc c'est un cercle extérieur):

 entrez la description de l'image ici

Comme vous pouvez le voir, il y a d'étranges trous entre les couches externes et les autres. J'ai essayé de faire deux couches extérieures et des trucs similaires, mais je n'ai pas obtenu le bon résultat.

Voici la version finale du code:

void drawFilledCircle(int x, int y, int startRadius, int endRadius, int r, int g, int b, int a, unsigned char* data, unsigned char* areasData, int startAngle, int endAngle, bool blendColor) {
    assert(startAngle <= endAngle);
    assert(startRadius <= endRadius);

    dfBufferCounter = 0;

    for(int i = 0; i < DRAW_FILLED_CIRCLE_BUFFER_SIZE; i++) {
        drawFilledCircleBuffer[i] = -1;
    }

    for(int cradius = endRadius; cradius >= startRadius; cradius--) {
        bool last = cradius == endRadius;
        bool first = cradius == startRadius && cradius != 0;

        float radiusX = cradius;
        float radiusY = cradius;
        float radiusX2 = radiusX * radiusX;
        float radiusY2 = radiusY * radiusY;

        float maxTransparency = 127;

        float quarter = roundf(radiusX2 / sqrtf(radiusX2 + radiusY2));
        for(float _x = 0; _x <= quarter; _x++) {
            float _y = radiusY * sqrtf(1 - _x * _x / radiusX2);
            float error = _y - floorf(_y);

            float transparency = roundf(error * maxTransparency);
            int alpha = last ? transparency : maxTransparency;
            int alpha2 = first ? maxTransparency - transparency : maxTransparency;

            setPixel4(x, y, _x, floorf(_y), r, g, b, alpha, cradius, endRadius, data, areasData, blendColor);
            setPixel4(x, y, _x, floorf(_y) - 1, r, g, b, alpha2, cradius, endRadius, data, areasData, blendColor);
        }

        quarter = roundf(radiusY2 / sqrtf(radiusX2 + radiusY2));
        for(float _y = 0; _y <= quarter; _y++) {
            float _x = radiusX * sqrtf(1 - _y * _y / radiusY2);
            float error = _x - floorf(_x);

            float transparency = roundf(error * maxTransparency);
            int alpha = last ? transparency : maxTransparency;
            int alpha2 = first ? maxTransparency - transparency : maxTransparency;

            setPixel4(x, y, floorf(_x), _y, r, g, b, alpha, cradius, endRadius, data, areasData, blendColor);
            setPixel4(x, y, floorf(_x) - 1, _y, r, g, b, alpha2, cradius, endRadius, data, areasData, blendColor);
        }
    }
}

Comment puis-je résoudre ce problème?

modifier:

Parce que je ne peux pas utiliser de remplissage pour remplir le cercle (la zone sur laquelle je dessine peut ne pas être un arrière-plan d'une couleur et j'ai besoin de mélanger ces couleurs), j'ai implémenté une méthode simple pour connecter des points avec des lignes:

J'ai ajouté 2 appels drawLine dans la méthode setPixel4:

void setPixel4(int x, int y, int deltaX, int deltaY, int r, int g, int b, int a, unsigned char* data, unsigned char* areasData, bool blendColor) {
    drawLine(x - deltaX, y - deltaY, x + deltaX, y + deltaY, r, g, b, 127, data, areasData); //maxTransparency
    drawLine(x + deltaX, y - deltaY, x - deltaX, y + deltaY, r, g, b, 127, data, areasData); //maxTransparency

    setPixelWithCheckingArea(x + deltaX, y + deltaY, r, g, b, a, data, areasData, blendColor);
    setPixelWithCheckingArea(x - deltaX, y + deltaY, r, g, b, a, data, areasData, blendColor);
    setPixelWithCheckingArea(x + deltaX, y - deltaY, r, g, b, a, data, areasData, blendColor);
    setPixelWithCheckingArea(x - deltaX, y - deltaY, r, g, b, a, data, areasData, blendColor);
}

et cela ressemble exactement à la troisième image. Je pense que ces pixels blancs à l'intérieur sont causés par le cercle extérieur (de l'algorithme xiaolin wu) lui-même.

edit 2:

Merci à @JaMiT, j'ai amélioré mon code et cela fonctionne pour un cercle, mais échoue quand j'en ai plus l'un sur l'autre. Tout d'abord, nouveau code:

for(int cradius = startRadius; cradius <= endRadius; cradius++) {
    bool last = cradius == endRadius;

    float radiusX = cradius;
    float radiusY = cradius;
    float radiusX2 = radiusX * radiusX;
    float radiusY2 = radiusY * radiusY;

    float maxTransparency = 127;

    float quarter = roundf(radiusX2 / sqrtf(radiusX2 + radiusY2));
    for(float _x = 0; _x <= quarter; _x++) {
        float _y = radiusY * sqrtf(1 - _x * _x / radiusX2);
        float error = _y - floorf(_y);

        float transparency = roundf(error * maxTransparency);
        int alpha = transparency;
        int alpha2 = maxTransparency - transparency;

        if(!last) {
            alpha = maxTransparency;
            alpha2 = maxTransparency;
        }

        setPixel4(x, y, _x, floorf(_y), r, g, b, alpha, data, areasData, false);
        setPixel4(x, y, _x, floorf(_y) - 1, r, g, b, alpha2, data, areasData, false);
    }

    quarter = roundf(radiusY2 / sqrtf(radiusX2 + radiusY2));
    for(float _y = 0; _y <= quarter; _y++) {
        float _x = radiusX * sqrtf(1 - _y * _y / radiusY2);
        float error = _x - floorf(_x);

        float transparency = roundf(error * maxTransparency);
        int alpha = transparency;
        int alpha2 = maxTransparency - transparency;

        if(!last) {
            alpha = maxTransparency;
            alpha2 = maxTransparency;
        }

        setPixel4(x, y, floorf(_x), _y, r, g, b, alpha, data, areasData, false);
        setPixel4(x, y, floorf(_x) - 1, _y, r, g, b, alpha2, data, areasData, false);
    }
}

Sans les appels drawLine dans setPixel4, cela ressemble à ceci:

 entrez la description de l'image ici

J'ai amélioré la méthode setPixel4 pour éviter de redessiner le même pixel:

float radiusX = endRadius;
float radiusY = endRadius;
float radiusX2 = radiusX * radiusX;
float radiusY2 = radiusY * radiusY;

float maxTransparency = 127;

float quarter = roundf(radiusX2 / sqrtf(radiusX2 + radiusY2));
for(float _x = 0; _x <= quarter; _x++) {
    float _y = radiusY * sqrtf(1 - _x * _x / radiusX2);
    float error = _y - floorf(_y);

    float transparency = roundf(error * maxTransparency);
    int alpha = transparency;
    int alpha2 = maxTransparency - transparency;

    setPixel4(x, y, _x, floorf(_y), r, g, b, alpha, data, areasData, false);
    setPixel4(x, y, _x, floorf(_y) - 1, r, g, b, alpha2, data, areasData, false);
}

quarter = roundf(radiusY2 / sqrtf(radiusX2 + radiusY2));
for(float _y = 0; _y <= quarter; _y++) {
    float _x = radiusX * sqrtf(1 - _y * _y / radiusY2);
    float error = _x - floorf(_x);

    float transparency = roundf(error * maxTransparency);
    int alpha = transparency;
    int alpha2 = maxTransparency - transparency;

    setPixel4(x, y, floorf(_x), _y, r, g, b, alpha, data, areasData, false);
    setPixel4(x, y, floorf(_x) - 1, _y, r, g, b, alpha2, data, areasData, false);
}

Puis, enfin:

entrer l'image description here

C'est presque parfait. Cependant, j'ai beaucoup de mal à me débarrasser de ce contour blanc, mais je ne peux pas.


5 commentaires

Pourquoi pas un simple remblai du centre?


si vous dessinez de l'extérieur vers l'intérieur, je suppose que cela aurait l'air bien.


mais je ne peux pas croire qu'il n'y ait pas de fonction pour dessiner un cercle anti-aliasing (rempli).


Le remplissage par inondation a du sens, mais .. l'objectif est de dessiner des cercles à moitié transparents et de mélanger leurs couleurs. Ainsi, l'arrière-plan peut ne pas toujours être de la même couleur et le remplissage ne vous aidera pas.


Juste un petit mot: cet algorithme est très bien, j'ai juste eu un problème avec le mélange. Voici la solution: stackoverflow.com/a/54695312/1264375


3 Réponses :


3
votes

Parce que vous discrétisez les cercles, certains pixels manquent forcément. L'image que vous avez obtenue montre l'effet Moiré, qui est bien connu.

La meilleure solution est d'utiliser n'importe quel algorithme de remplissage ou de synthétiser le plus trivial qui dessinerait des lignes entre les points des cercles sur les mêmes lignes horizontales (ou verticales si vous préférez).


7 commentaires

Le remplissage par inondation a du sens, mais .. l'objectif est de dessiner des cercles à moitié transparents et de mélanger leurs couleurs. Ainsi, l'arrière-plan peut ne pas toujours être de la même couleur et le remplissage ne vous aidera pas. Je suppose que je me retrouve avec des lignes horizontales / verticales.


@Makalele Vous pouvez essayer de dessiner des cercles en faisant un pas de moins de 1 pixel à chaque étape ... Comme je ne comprends pas quel genre d'effet vous essayez d'obtenir, difficile de vous aider davantage. Ou utilisez un autre algorithme que celui de Wu car il s'agit d'un type très spécial d'algorithme d'anti-crénelage.


J'ai déjà essayé ça. Je veux avoir un cercle rempli avec des bords lisses (donc la première image, juste remplie).


@Makalele Ensuite, dessinez à nouveau le cercle et tracez une ligne entre d'un point à un autre sur la même horizontale! Analysez l'algorithme pour comprendre comment les points sont générés par symétrie et quels sont les points limites ... S'il doit s'agir d'un disque, alors c'est facile.


Voir ma modification. Je suis arrivé à la même image en dessinant des lignes.


dessinez les lignes après les pixels! Je veux dire dessiner les lignes entre les "vrais" pixels sur le cercle.


Il n'y a rien de mal dans votre implémentation. Ce sera mon dernier commentaire sur le sujet. Si vous tracez une ligne entre les pixels des points intérieurs du cercle dessiné, cela fonctionnera (je sais que c'est possible, car je l'ai déjà fait dans le passé).



2
votes

Pensez à ce que vous faites pour obtenir la troisième image (celle avec les "trous étranges" juste à l'intérieur de la circonférence). Vous avez dessiné le disque interne et vous voulez dessiner un cercle autour de lui pour le rendre un peu plus grand. Bonne idée. (Votre professeur de calcul devrait approuver.)

Cependant, vous ne tracez pas simplement un cercle autour de lui; vous dessinez un cercle anti-crénelé autour de lui. Qu'est-ce que ça veut dire? Cela signifie qu'au lieu de simplement dessiner un point, vous en dessinez deux, avec des transparences différentes pour tromper l'œil en lui faisant croire que c'est un seul. L'un de ces points (le point intérieur) va écraser un point du disque que vous avez déjà dessiné.

Lorsque le point extérieur est plus transparent, il n'y a pas d'autre problème que peut-être un peu de flou. Lorsque le point interne est plus transparent, cependant, vous avez ce comportement étrange où le disque commence principalement opaque, devient plus transparent, puis revient à l'opacité totale. Vous avez pris un point complètement opaque du disque et l'avez rendu presque transparent. Votre œil interprète cela comme un trou.

Alors, comment résoudre ce problème ?

1) Tant que votre disque est censé être uniformément coloré (comptabilité pour la transparence), votre dernière tentative devrait fonctionner si vous inversez la boucle extérieure - passez du plus grand rayon à zéro. Etant donné que seul le cercle le plus à l'extérieur reçoit l'anticrénelage, seule la première itération de cette boucle inversée écraserait un pixel par un pixel plus transparent. Et il n'y a rien à écraser à ce stade.

OU

2) Aux deux endroits où vous définissez alpha2 , définissez à maxTransparency . Il s'agit de la transparence du pixel intérieur et vous ne voulez pas que le bord intérieur soit anticrénelé. Continuez et parcourez les rayons dans les deux sens, en construisant votre disque à partir de cercles. Continuez à régler les deux transparents au maximum lorsque vous ne dessinez pas le cercle le plus à l'extérieur. Cette approche a l'avantage de pouvoir mettre un trou au milieu de votre disque; le startRadius n'a pas à être nul. Lorsque vous êtes à startRadius (et que startRadius n'est pas égal à zéro), définissez alpha2 en fonction de l'algorithme d'anitaliasing, mais définissez alpha code> à maxTransparency.

Donc, votre logique de réglage alpha ressemblerait à quelque chose comme

    bool first = cradius == startRadius  &&  cRadius != 0; // Done earlier
    int alpha = last ? transparency : maxTransparency;
    int alpha2 = first ? maxTransparency - transparency : maxTransparency;

Edit: em> En y réfléchissant bien, il y aurait division par zéro si cRadius était nul. Puisque vous avez apparemment déjà pris en compte cela, vous devriez être en mesure d'adapter le concept de "premier" pour signifier "cercle le plus profond et nous sommes en fait en train de laisser un trou".

OU

3) Vous pouvez dessiner des lignes comme cela a été suggéré, mais il y a quelques choses à modifier pour minimiser les artefacts. Tout d'abord, supprimez le deuxième appel à setPixel4 dans chaque paire; nous couvrirons ce cas avec les lignes. Cela supprime le besoin d'avoir alpha2 (qui était de toute façon la cause des trous). Ensuite, essayez de dessiner une boîte (quatre lignes) au lieu de deux lignes parallèles. Avec cet algorithme, la moitié du dessin est basée sur des lignes horizontales et l'autre moitié sur la verticale. En dessinant les deux tout le temps, vous avez couvert vos bases. Troisièmement, si vous voyez toujours des artefacts, essayez de dessiner une deuxième boîte à l'intérieur de la première.


5 commentaires

Un grand merci pour la réponse détaillée. La méthode n ° 1 fonctionne bien, je ne peux pas croire que c'était aussi simple à réparer. Le cercle est superbe. Cependant, j'ai également besoin d'un mélange de couleurs. Et c'est là que les problèmes commencent. Quand j'ai 2 cercles (ou plus) qui se croisent partiellement, je reçois un artefact étrange sur les contours qui se croisent. J'utilise également la méthode n ° 2 en même temps. Je n'ai pas aidé cependant. J'ai essayé d'implémenter la méthode n ° 3, mais je n'ai pas réussi. Voir ma réponse modifiée pour plus de détails.


@Makalele "J'ai besoin aussi" - cela suggère que vous avez une deuxième question à poser. Le fait d'insérer une deuxième question dans ce post pourrait vous être bénéfique à court terme, mais cela a tendance à laisser un désordre indéchiffrable pour les autres qui tentent de résoudre le même problème. Je suggérerais d'annuler votre dernière modification, puis de commencer une nouvelle question pour le nouveau problème. (Assurez-vous que les gens peuvent comprendre la nouvelle question même s'ils n'ont pas lu celle-ci.)


Mais c'est à peu près le même algorithme, il suffit juste d'être légèrement modifié. De plus, si cela fonctionne, ce sera simplement une meilleure réponse.


J'ai découvert que maintenant, le problème vient du mélange, pas de l'algorithme xiaolin wu lui-même. Donc, maintenant poser une nouvelle question a du sens: stackoverflow.com/questions/54692947/…


J'ai pensé qu'il était logique de créer une nouvelle question dès que vous avez ajouté un deuxième cercle. La question initiale était de savoir comment donner une apparence correcte à un cercle. Quelqu'un d'autre pourrait poser la même question. Y a-t-il une raison de penser qu'une autre personne voudra deux cercles? Pas vraiment. Une deuxième question a donc du sens. (Si la deuxième réponse était purement une amélioration par rapport à la première, les réponses peuvent être mises à jour. Plus facile de fusionner les réponses que de séparer les questions.)



1
votes

Vous ne devriez dessiner qu'un seul cercle extérieur avec une connexion du côté gauche au pixel droit par des lignes simples horizontales pleines.

[entrez la description de l'image ici] 1


0 commentaires