Algorithme pour pixelliser un torus/dougnut

Question

Je souhaite pixelliser un donut 2d en une matrice/pixels (le résultat devrait être un beignet rempli).

L'anneau est défini par r1, r2, x0, y0.

Je soupçonne que la solution est une fonction de l'algorithme de Bresenham https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Toutes les idées?

Answer 1

Oui, il est possible de remplir un anneau avec un cercle Bresenham ou un algorithme Midpoint.

Démarrer les marches parallèles pour les cercles intérieurs et extérieurs pour le 1er quadrant. Construire des segments horizontaux quand Y change. Arrêtez de marcher pour le cercle intérieur quand le sommet est atteint et continuez avec le cercle extérieur.

Notez que vous devez vous rappeler le premier (le plus grand) valeur X externe, mais la dernière valeur X intérieure (la plus petite) pour la même Y.

Answer 2

Bresenham est loin d'être optimale ces jours-ci ... ce A propos de l'exploitation de l'équation du cercle:

(x-x0)^2 + (x-y0)^2 = r^2 

nous allons:

x0,y0 - center 
r1 - outer radius 
r2 - inner radius 
r1<=r2 
xs,ys - screen resolution 
scr[ys][xy] - screen matrix 

dans C++ il ressemble à ceci:

int x,y,xx,yy,rr,rr1=r1*r1,rr2=r2*r2; 
for (y=y0-r1;y<=y0+r1;y++)     // loop all y positions 
if ((y>=0)&&(y<ys))      // clip to screen 
    for (yy=y-y0,yy*=yy,x=x0-r1;x<=x0+r1;x++) // loop all x positions 
    if ((x>=0)&&(x<xs))      // clip to screen 
    { 
    xx=x-x0; xx*=xx; rr=xx+yy; 
    if ((rr>=rr2)&&(rr<=rr1))    // is in between radiuses? 
    scr[y][x]=fill_color; 
    } 

Vous pouvez vous débarrasser de l'écran écrêtage if déclarations facilement limites pré-calcul pour les deux boucles qui sont à l'intérieur de l'écran ...

Pour les cercles remplis cette approche est généralement plus rapide alors Bresenham pour ne pas mentionner facilement parallélisable.