Comment sont fait vos routines de cercles? - Page 1

Bon voila en ce moment j'ai un cours d'image de synthese et les premiers TP etait sur l'affaichage d'une ligne par l'algorithme de brenstein... et aussi des cercles..
Et j'ai etait tres surpris que l'algorithme ne comportait aucun calcul de cosinus ou sinus juste deux equation du premier ordre et le resultat est stupéfiant!!!
Un cercle parfait !
Donc j'aurais aimé savoir si cette methode est utilsé sr ti?
Sinon ben va falloir que je la porte ca doit etre une des plus rapide (en tout ca c'est la methode utilsé par opengl!

Bon voila l'algo en C (sous glut)


void MidPointCircleAlgo(int x0, int y0, int r)
{
/* x0 abscisse centre du cercle */
/* y0 ordonnee centre du cercle */
/* r rayon du cercle */

int x,y,d;
glBegin(GL_POINTS);
x = 0 ;
y = r ;
d = 1 - r ;
plot(x+x0,y+y0);
plot(y+x0,x+y0);
plot(y+x0,-x+y0);
plot(x+x0,-y+y0);
plot(-x+x0,-y+y0);
plot(-y+x0,-x+y0);
plot(-y+x0,x+y0);
plot(-x+x0,y+y0);
while ( y > x )
{
if ( d < 0 )
d += 2 * x + 3 ;
else
{
d += 2 * (x - y) + 5 ;
y-- ;
}
x++ ;
plot(x+x0,y+y0);
plot(y+x0,x+y0);
plot(y+x0,-x+y0);
plot(x+x0,-y+y0);
plot(-x+x0,-y+y0);
plot(-y+x0,-x+y0);
plot(-y+x0,x+y0);
plot(-x+x0,y+y0);
}

glEnd();

}

Je vous enverrez l'exe pour voir le resultat!

Voici XCercle, tirée de la source de XLib:
L'algo doit être une poil plus rapide...

void XCercle(short ctrx, short ctry, short rayon, short color)
{
   short chgmt, xx, yy,zz;
   xx = 0;
   yy = rayon;
   zz = 0;
   chgmt = -rayon;

   do {
	 XGPxlPut(ctrx+xx, ctry+yy, color);
	 XGPxlPut(ctrx-xx, ctry+yy, color);
	 XGPxlPut(ctrx-xx, ctry-yy, color);
	 XGPxlPut(ctrx+xx, ctry-yy, color);
	 XGPxlPut(ctrx+yy, ctry+xx, color);
	 XGPxlPut(ctrx-yy, ctry+xx, color);
	 XGPxlPut(ctrx-yy, ctry-xx, color);
	 XGPxlPut(ctrx+yy, ctry-xx, color);
	 
	 if ((chgmt += (xx++) + xx) >= 0)
	 {
	  zz = yy--;
	  chgmt -= zz + yy;
	 }

   }while (xx <= yy);
}

c'est clair que c'est assez impressionnant. Soit dit en passant, ca marche aussi pour les ellipses

oué, mais avec 4 points d'ailleurs si tu veux mastergb pour l'ellipse, j'ai aussi idem, pour XLib ...

J'ai des doutes sur la qualité du cercle avec cet algo!
Mais je vais essayer...

Ben je n'ai pas de doute moi, ca marche parfaitement !

Sur Ti ca marche
Pas sur PC!
Sur PC c'est pas bon quand le cercle est trop grand!

heurf, ca bug a partir de combien ?

Attend je regarde a peu pres....
Mais le je suis encore en synthese et je suis sur le clipping de droite par fenetrage de polygone!!!!
Algorithme cyrus et beck


tres tres lourd....
Et dur aussi.

ça fait une espèce d'octogone ça non ?

je pense que ca doit ressembler à ca oué ... mais non fermé je pense

L'algo marche pas du tout sur pc!
Ca foire totalement!

Nan il marche mais il est moin lissé!!!!!!

OKI, donc ne pas prendre cet algo pour les PC, thx

Sisi tu peut le prendre autant pour moa....
Je viens de voir le prof cet algo est applicable qu'a des cercles...
L'algo du haut est utilsable pour toute courbe du type x²+y²=c....
En gros elle est aussi applicable pour les ellipses!

nEUrOne, il y a un bogue dans ton code (ou celui de TiMad)!
if ((chgmt += (xx++) + xx) >= 0)
Tu n'as pas le droit d'utiliser xx++ et xx dans la même expression (dans le même "sequence point")!

Ben ca marche tres bien kevin l'algo..
Je viens de tester en opengl...
Vraiment bien..
La difference entre les 2 algos sont minime...

mastergb1
a écrit : La difference entre les 2 algos sont minime...

On se doute que le premier doit mettre un chouïa plus de temps à s'exécuter...

Je parle au niveau graphique...
Le premier n'affiche pas que des cercles...
Celui de timad si!

Et les courbes de beziers ya l'equivalent sur ti?

kk: c le mien, ca marche nickel
mastergb1: j'ai aussi codé pour bezier si tu veux

mastergb1
a écrit : Ben ca marche tres bien kevin l'algo..

Ça marche très bien par pur hasard! C'est de l'"undefined behavior"! Si ça marche, c'est un coup de chance, pas plus!

Il ne faut pas écrire:
if ((chgmt += (xx++) + xx) >= 0)
mais:

	 chgmt += (xx++);
	 if ((chgmt += xx) >= 0)

ou:

	 chgmt += xx;
	 if ((chgmt += (xx++)) >= 0)

(selon ce qui était voulu)!!!

(D'ailleurs, la deuxième et la troisième écriture sont toujours à la limite du lisible, mais c'est du C valide contrairement à la première, qui en plus d'être illisible est fausse.)

Raisonnement: les 2 écritures ici montrent bien 2 manières possibles d'interpréter ce qu'il y a écrit. Et de plus, le standard C n'oblige nullement le compilateur de choisir une de ces 2 écritures. Il a parfaitement le droit de générer du code qui formate votre disque dur, détruit votre carte mère ou efface votre zone des certificats!

En tout cas, avec du code comme ça, ne venez pas vous plaindre si vos programmes ne marchent plus avec la prochaine version de TIGCC!

C'est tout de même bien étrange que ca marche parfaitement sous divers compilateurs ... nan ?

Parceque tous ces compilos sont des portages de GCC
Et même si ce n'est pas le cas, c'est un coup de chance ! Ton code pourrait tout planter sur d'autres compilateurs qui n'incrémentent pas xx au même "moment".

Thibaut a écrit :
Parceque tous ces compilos sont des portages de GCC

Même des versions de GCC pour des plateformes différentes ou des versions différentes de GCC pour la même plateforme pourraient traîter ça différemment!

C'est le "frontend" qui décide "quand" incrémenter ?

Se qui me laisse perplexe c que g tjrs lu que le C utilise un ordre de priorité, et lisait de gauche a droite..

Donc :
if ((chgmt += (xx++) + xx) >= 0)

=

1 -> xx++
2 -> chgmt += xx
3 -> chgmt += xx
4 -> chgmt >= 0

Voir plus simple :

1 -> xx++
2 -> chgmt += xx*2
4 -> chgmt >= 0

On pourrait donc changer le code en :

if ((chgmt += ((xx++) * 2 )) >= 0)
ou
if ((chgmt += ((xx++) << 1)) >= 0)