lecture de langage algorithmique sur wikipedia et traduction en langage c (Bresenham)

Version imprimable

28/12/2016, 11h33
piponux

lecture de langage algorithmique sur wikipedia et traduction en langage c (Bresenham)
Bonjour et bonnes fêtes.
je suis en train d'écrire une fonction en langage c qui est la traduction de l'algorithme de Bresenham.
https://fr.wikipedia.org/wiki/Algori...t_de_Bresenham

j'ai un doute sur mon code :

quand on voit:

dy <- (e <-dy) x 2

est que la bonne traduction en c est :
Code:

1 2 3 e = dy; e *= 2; dy = e;
ou bien
Code:

1 2 e = (dy * 2); dy = e;
?
merci pour vos réponses. (je pense que la première proposition est la bonne).
28/12/2016, 13h46
Médinoc
Pour moi ce n'est ni l'une ni l'autre, mais plutôt:
Code:

1 2 e = dy; dy = e*2;
28/12/2016, 14h03
piponux

1 pièce(s) jointe(s)

Merci Medinoc.
j'ai essayé ta solution. Elle paraît identique à ma première proposition (la tienne passe par une étape intermédiaire en moins).
En tous cas, graphiquement, il n'y a pas de différence entre les deux: (le trait en haut à gauche)

ma fonction Bresenham complete

Je vous livre ici ma fonction complète qui est la traduction mot à mot de l'algorithme trouvé sur wikipedia.
Il y a des if dans tous les sens, je trouve cela super moche et laborieux (250 lignes pour une seule fonction : est-ce normal?), mais ça fonctionne sans erreur, sur une image tga 24 bits non compressée.
Il y a à coup sur moyen de la raccourcir, mais pour l'instant, je ne pense pas avoir le niveau pour faire mieux.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
void bresenham2 (image I, int x1, int y1, int x2, int y2, byte r, byte g, byte b, byte a)
{
 int dx = x2 - x1;
/* int dy = y2 - y1;*/
int dy;
 if (dx != 0)
  {
   if (dx > 0)
    {
    fprintf (stderr, "dx > 0, dx = %d\n", dx);
     if ((dy = y2 - y1) != 0)
      {
       if (dy > 0)
        {
         if (dx >= dy)
          {
           fprintf (stderr, "dx >= dy, dx = %d\n", dx);
           int e;
           e = dx;
           e *= 2;
           dx = e;
           dy = dy * 2;
           while (1)
            {
             colour* ptr = I->pixel + y1 * I->w + x1;
	     image_putpixel_alpha (ptr, r, g, b, a);
	     x1++;
	     if (x1 == x2) break;
	      if ( (e -= dx) < 0)
	       {
	        y1++;
	        e += dx;
	       }
             }
            } 
           else /*vecteur oblique proche de la verticale dans le 2d octant*/
            {
             fprintf (stderr, "dx > 0, dy > 0 et dx < dy\n");
             int e;
             e = dy;
             e *= 2;
             dy = e;
             dx *= 2;
             while (1)
              {
               colour* ptr = I->pixel + y1 * I->w + x1;
	       image_putpixel_alpha (ptr, r, g, b, a);
               if ((y1++) == y2) break;
                if ((e -= dx) < 0)
                 {
                  x1++;
                  e += dy;
                 }/*fin si*/
              }/*fin boucle*/
            }/*fin sinon*/
         } /*fin du dy > 0*/
 
         else if (dy < 0 && dx > 0)
          {
           if (dx >= -dy)
            {
             fprintf (stderr, "dy < 0, dx > 0 et dx >= -dy\n");
             int e;
             e = dx;
             e *= 2;
             dx = e;
             dy *= 2;
              while (1)
               {
               colour* ptr = I->pixel + y1 * I->w + x1;
	       image_putpixel_alpha (ptr, r, g, b, a);
               if ((x1++) == x2) break;
                if ((e += dy) < 0)
                 {
                  y1--;
                  e += dx;
                 } 
               }
            }/*fin du if dx >= -dy*/
             else  
             {
              int e;
              e = dy;
              e *= 2;
              dy = e;
              dx *= 2;
              while (1)
               {
                colour* ptr = I->pixel + y1 * I->w + x1;
	        image_putpixel_alpha (ptr, r, g, b, a);
                 if ((y1--) == y2) break;
                 if ((e += dx ) > 0)
                  {
                   x1++;
                   e += dy;
                  }/*fin du if*/
               }/*fin du while*/
             }/*fin du else ligne 274 */ 
          }/*fin du else il dy < 0 et dx > 0*/
 
        }/*fin du il dy != 0 ligne 212 => erreur?*/
 
        else if (dy == 0 && dx > 0) 
         {
          fprintf(stderr, "dy = 0 && dx > 0\n");
          do {
              colour* ptr = I->pixel + y1 * I->w + x1;
              image_putpixel_alpha (ptr, r, g, b, a);
 
 
             }while ((x1++) != x2);
         }
 
        /*}*//*fin du if dy != 0 ligne 212*/ 
 
     }
 
     if (dx < 0)
      {
       fprintf (stderr, "dx < 0\n");
       if ((dy = y2 - y1) != 0)
        {
         if (dy > 0)
          {
           if (-dx >= dy)
            {
             fprintf (stderr, "-dx >= dy\n");
             int e;
             e = dx;
             e *= 2;
             dx = e;
             dy *= 2;
             while (1)
              {
               colour* ptr = I->pixel + y1 * I->w + x1;
               image_putpixel_alpha (ptr, r, g, b, a);
               if ((x1--) == x2) break;
                if ((e += dy) >=0)
                 {
                  y1++;
                  e += dx;
                 }
              }
            }
           else if (-dx < dy)  /*debut sinon, et fin du if -dx >= dy*/
            {
             int e;
             e = dy;
             e *= 2;
             dy = e;
             dx *= 2;
             fprintf(stderr, "-dx < dy\n");
             while (1)
              {
               colour* ptr = I->pixel + y1 * I->w + x1;
               image_putpixel_alpha (ptr, r, g, b, a);
               if ((y1++) == y2) break;
               if ((e += dx) <= 0)
                {
                 x1--;
                 e += dy;
                }
              }             
            }/*fin de -dx < dy ligne 339*/
          }
          else if (dy < 0 && dx < 0)
           {
            fprintf (stderr, "dy < 0 && dx < 0\n");
            if (dx <= dy)
             {
              fprintf (stderr, "dy < 0 && dx < 0 + dx <= dy\n");
              int e;
              e = dx;
              e *= 2;
              dx = e;
              dy *= 2;
              while (1)
               {
                colour* ptr = I->pixel + y1 * I->w + x1;
                image_putpixel_alpha (ptr, r, g, b, a);
                if ((x1--) == x2) break;
                if ((e -= dy) >= 0)
                 {
                  y1--;
                  e += dx;
                 }
               }
             }
             else if (dx > dy) 
              {
               fprintf(stderr, "dx > dy\n");
               int e;
               e = dy;
               e *= 2;
               dy = e;
               dx *= 2;
               while (1)
                {
                 colour* ptr = I->pixel + y1 * I->w + x1;
                 image_putpixel_alpha (ptr, r, g, b, a);
                 if ((y1--) == y2) break;
                 if ((e -= dx) >= 0)
                  {
                   x1--;
                   e += dy;
                  }
                }
              }
           }
        }
        else if (dy == 0 && dx < 0)
         {
          fprintf (stderr, "dy = 0 && dx < 0\n");
          do 
           {
            colour* ptr = I->pixel + y1 * I->w + x1;
            image_putpixel_alpha (ptr, r, g, b, a);
           }while ((x1--) != x2);
         }
 
      }
   }
 
   if (dx == 0)
    {
     fprintf (stderr, "dx = 0\n");
     if ((dy = y2 - y1) != 0)
      {
       if (dy >0)
        {
         fprintf (stderr, "dy > 0\n");
         do
          {
            colour* ptr = I->pixel + y1 * I->w + x1;
            image_putpixel_alpha (ptr, r, g, b, a);
          }while ((y1++) != y2);
        }
       else if (dy < 0 && dx == 0)
        {
         fprintf (stderr, "dy < 0 && dx = 0\n");
         do
          {
            colour* ptr = I->pixel + y1 * I->w + x1;
            image_putpixel_alpha (ptr, r, g, b, a);
          }while ((y1--) != y2);
        } 
      }
    }
}

28/12/2016, 15h42
BufferBob

salut,

Citation:

Envoyé par piponux

250 lignes pour une seule fonction : est-ce normal?

oui et non

non car il semblerait qu'on puisse faire un chouillat plus court

oui car dans l'absolu ce n'est pas la longueur du code qui détermine son efficacité, au contraire l'algorithme de Bresenham quand il est optimisé nécessite plus de lignes de code, et s'exécute pourtant plus vite ;)
28/12/2016, 16h05
piponux

salut,
ok, merci pour la réponse BufferBob.
Pour ce qui est des runs (http://www.phatcode.net/res/224/file...6-03.html#Fig5), je trouve cela un peu trop balaise pour moi pour l'instant...

1 pièce(s) jointe(s)

Et comme j'ai l'impression de ne faire que poser des questions, voici ma fonction Bresenham pour les cercles (sans poser de question).
Cela marche bien avec la fonction de flood_fill.

real 0m0.121s
user 0m0.120s
sys 0m0.000s

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void bresenham_cercle (image I, int rayon, int x_centre, int y_centre, byte r, byte g, byte b, byte a)
{
 int x, y, m;
 x = 0;
 y = rayon;
 m = 5 - (4 * rayon);
 while (x <= y)
  {
   colour* ptr = NULL;
 
   ptr = I->pixel + (y + y_centre) * I->w + (x + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);
 
   ptr = I->pixel + (x + y_centre) * I->w + (y + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);
 
   ptr = I->pixel + (y + y_centre) * I->w - (x + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);
 
   ptr = I->pixel + (x + y_centre) * I->w - (y + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);   
 
   ptr = I->pixel + (-y + y_centre) * I->w + (x + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);
 
   ptr = I->pixel + (-x + y_centre) * I->w + (y + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);
 
   ptr = I->pixel + (-y + y_centre) * I->w - (x + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);
 
   ptr = I->pixel + (-x + y_centre) * I->w - (y + x_centre);
   image_putpixel_alpha (ptr, r, g, b, a);
 
   if (m > 0)
    {
     y--;
     m = m - 8 * y;
    }
 
   x++;
   m = m + (8 * x) + 4; 
 
  }
}

EDIT : il y a des erreurs. Il faut remplacer toutes les soustractions en x du style

Code:

I->w - (x + x_centre)

par

Code:

1
2
 
I->w + (-x + x_centre)

Sinon, cela donne un cercle bancal.