Discussion :

[hbx360]

Bonjour, pourriez-vous me dire concernant l'algorithme de bresenham pourquoi quand on calcule la progression de l'erreur dans le cas 1 on passe de :


erreur = 4x² + 4y² + 8x − 4y + 5 − R² + 8x + 12 à
erreur = 4x² + 4y² + 8x − 4y + 5 − R² + 8x + 4

pourquoi (là ou j'ai surligné) on passe de 12 à 4

pareille pour le cas 2 ou on passe de :

erreur = 4x² + 4y² + 8x − 4y + 5 − R² + 8x − 8y + 20
erreur = 4x² + 4y² + 8x − 4y + 5 − R² + 8x − 8y + 4

on passe de 20 à 4

Dans le code ci-dessous on met donc e+=8x+4 et non e+=8x +12
et dans e+=-8y on ne mais pas de constante je ne comprends pas pourquoi, puisque dans le cas 2 on vois que l'on a 8x-8y+20 ;

Donc admettons que l'on mette 4 à 8x (8x+4) dans ce cas là il faudrait mettre a -8y : +16 pour retrouver le 20 au départ pour moi si on a 8x+12 alors pour -8y on devrait avoir -8y+8.

Pourriez-vous m'expliquer ce qui justifie de mettre 8x+4 et -8y dans le code au lieu de 8x+12 et -8y+8

De plus dans le code que voici je n'ai pas un cercle identique a celui de paint (voir image : Pièce jointe 193874) j'ai quelque pixel qui sont en trop quand j'ai des grands rayon supérieur à 32 des pixels en trop commence à apparaître pourriez-vous me dire de quoi ça vient. En vous remerciant par avance.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
void line_bresenham(SDL_Surface* display,color c)
{
 
  int x=0;
  int r=128, cx=128, cy=128;
  int y =r;
  int e=5-4*r;
 
  while(x<=y)
    {
      *((int*)display->pixels + x+ cx+display->w*(cy+y))=c; /*allume le pixel*/
 
      if(e>0)
	{
	  y--;
	  e+=-8*y;
	}
 
      x++;
      e+=8*x+4;
 
      SDL_Flip(display);
    }

[Flodelarab]

Bonjour

là ou j'ai surligné

Tu n'as pas surligné mais souligné.

De quoi parles-tu ? Quels sont les cas 1 et 2 ?

[anapurna]

salut,

je pense qu'il parle de l'algo pour les arc de cercle de Bresenham

la démonstration ce trouve sur cette page ci

[hbx360]

Merci pour vos réponses

Oui je parle bien de l'algorithme de bresenham.

En utilisant le fait que 4m = 4x² + 4y² + 8x - 4y + 5-4R²,
on obtient 4(m+1) = 4m + 8x + 12 = 4m + 8x + 4.

Mais je ne comprends toujours pas pourquoi on passe de 8x+12 à 8x+4 qu'est-ce qui justifie cette transformation ?

Pourriez-vous me dire aussi pourquoi mon code au dessus d'un rayon de 32 il y a des point en trop (voir l'image de mon premier commentaire).

Merci par avance.

[anapurna]

salut

d’après ce que je vois tu n'indique pas les indice de ta fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
4m<sub>i+1</sub>=4m<sub>i</sub>+8x<sub>i+1</sub>+4
tu remplace 
x<sub>i+1</sub> par xi+1
 
on a donc 
4m<sub>i+1</sub>=4m<sub>i</sub>+8(x<sub>i</sub>+1)+4
=> 4m<sub>i+1</sub>=4m<sub>i</sub>+8(x<sub>i</sub>)+8+4
=> 4m<sub>i+1</sub>=4m<sub>i</sub>+8x<sub>i</sub>+12

j’espère que c'est plus simple comme cela

[hbx360]

Merci pour ta réponse rapide je vais étudier ça de près.

[hbx360]

@anapurna oui mais je vois que tu fait la démonstration a l'envers.

Mais dans la démonstration on part de 4mi+1 donc ça fait :

= 4_mi+1
= 4x²_i+1 + 4y²_i+1 + 8x_i+1 − 4y_i+1 + 5 − R²
= 4(x_i + 1)² + 4y²_i + 8(x_i + 1) − 4y_i + 5 − R²
= 4x²_i + 8x_i + 4 + 4y²_i + 8x_i + 8 − 4y_i + 5 − R²

et on arrive donc à :
=4x²_i + 4y²_i + 8x_i − 4y_i + 5 − R² +8x_i + 12

et on arrive donc à : 4m_i + 8x_i+1 + 4

Je comprend que quand tu remplace x_i+1 par x_i+1 pour 4m_i + 8x_i+1 + 4

Mais la on veut passer de 4m_i+8x_i + 12 à 4m_i + 8x_i+1 + 4 c'est sa que je ne comprends pas ; faire l'inverse ok pour retrouver le 12 mais passer du 12 au 4 il faudrait faire un truc du genre x_i+1 remplacer par x_i-1 et cela nous donnerai : 8(x-1) ce qui donnerai 8x-8 et la effectivement on retrouverait bien notre 4 mais la démonstration n'en parle pas.

[anapurna]

salut

mais non

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 4mi+8x<sub>i</sub> + 12 
=> 4m<sub>i</sub> + 8x<sub>i+1</sub> + 4

on utilise la propriete de transitivité des multiplication et des addition
genre 4+2 = 2+4 et 4*2=2*4=2*(2+2) ou 2*(2*2) selon ce que l'on a besoin

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 4mi+8x<sub>i</sub> + 12
=>  4mi+8x<sub>i</sub>  + 8   + 4  
=>  4mi+8(x<sub>i</sub> + 1) + 4 
=>  4mi+8(x<sub>i+1</sub>)   + 4

[hbx360]

Merci pour ta réponse anapurna c'est claire pour moi maintenant j'ai compris.

Et pour mon code : pourquoi si je compare mon (tracé pixel vert 1/8ieme de cercle) avec le cercle fait dans paint y a t-il des pixel en trop (voir image : ) au dessus d'un rayon de 32 qu'est-ce qui ne va pas dans mon code ?

[anapurna]

bon

je vois pas ton image
mais quand je vois ton code je me dis que ton probleme dois se situer au niveau du display

je suppose que pixels est un tableau d'octet
par contre je ne vois pas a quoi correspond le w

en pascal j'aurais surement fait un truc du genre

display.pixels[x+cx, cy+y]:=c; /*allume le pixel*/
ou display.pixels[x+cx+(y*width)+cy]:=c;
cx et cy étant de décalage je n'ai pas besoin de multiplier le décalage en y par sa position

[hbx360]

le display->w correspond à la largeur de ma fenêtre SDL ; le display->pixels correspond au premier octet de ma fenêtre SDL.
En fait j'ai créer une SDL_Surface *display;

En tous cas merci d'avoir pris du temps pour répondre tu m'a bien aidé.

[hbx360]

Pour les pixels en trop sa vient de paint car sur the gimp c'est nikel.

[hbx360]

Euh en faite j'aurai encore une petite question concernant le 8x + 4 :

dans 4mi + 8x_i+1 + 4 dans notre programme ne devrait on pas mettre plutôt 8(x+1)+4 au lieu
de 8x +4 j'ai du mal a saisir pourquoi 8x_i+1 + 4 devient dans notre programme 8x+4 ?

Merci par avance.

[anapurna]

salut

tu confond la formule mathématique avec la variable d’incrément

bon on va reprendre la démonstration
on veut passer de m_i à m_i+1
on sais que
m_i+1 = m_i+8x_i+12
le x actuel est celui connu pour le m_i
on sais aussi 8*(xi+1) = 8*xi + 8*1
=> 8*x_i+1+4
donc si l'on veut incrémenter notre position m il faut 8*le nouveau x + 4
on détermine donc que ton X vaut xi+1


PS : n'oubli pas que ton calcul ne se fait que sur un quart de cercle
donc ton x et ton y on une évolution orienté
je veut dire que selon le cadrant soit la valeur de x augmente soit elle diminue sur un même cadrant elle ne peut pas faire les deux et ceci est valable aussi pour ta variable y

[hbx360]

Merci pour ta réponse je penses que c'est bon maintenant j'ai compris.