Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Rotation d'ellipses en langage C
Bonjour,
je suis en train de programmer un petit editeur de sprites / dessins en langage c avec SDL2.
J'en suis aux ellipses, que je veux faire pivoter selon un certain angle et à partir d'une origine en x et y.
Pour l'instant, je n'ai programmé que les angles 300°, 315°, 330° et 345°.
voici le résultat où l'origine est en (0,0).
ma question est la suivante : l'écrasement des ellipses est il un phénomène normal? et comment résoudre le problème des trous?
Souvent en 2D, un truc simple et assez rapide pour rendre plus joli son "programme": augmenter la définition
Sérieux, tu travailles en 80x60
Parce que ton histoire de trous doit venir du fait qu'en affichage, on travaille en espace discret (avec des entiers et non pas des flottants)
Des algos comme celui de Bresenham permettent de faire fi, en partie, de cette particularité: cherche-en 1 pour tracer des ellipses
Salut, je veux m'éclater en apprenant à programmer et en voyant de près comment ça marche. Je ne suis pas du tout du métier, donc je travaille sans pression et sans impératif, et celà reste un plaisir et un loisir avant tout.Sérieux, tu travailles en 80x60 tu veux faire quoi
Je n'avais pas pensé à Bresenham: merci pour l'idée!
j'ai trouvé ce lien : http://raphaello.univ-fcomte.fr/ig/a...orithmique.htm
mais je ne suis pas sûr que les trous viennent de l'agorithme de tracé, mais plutot de la rotation d'un tracé existant.
Mon but est de dessiner une forme quelle qu'elle soit, et de la faire pivoter à volonté.
Justement, si on effectue une rotation d'un tracé on ne peut obtenir qu'une dégradation du tracé initial. En faisant "tourner" chaque pixel, sa coordonnée finale devant être arrondie et l'orientation de son dessin restant constante, on obtient un résultat forcément déplorable.Envoyé par piponux
Sur une figure avec une résolution énorme (avec une épaisseur de trait de plus de 10 pixels), le problème est moins visible, mais existera toujours.
Seul moyen pour un tracé correct : recalculer entièrement l'ellipse.
Bonjour,
Ah ? Ce n'est pas là-dessus que tu es parti depuis le départ ? Il y a écrit « BRESENHAM CIRCLE » au bas de ta capture d'écran…
Faire pivoter une ellipse, quand on n'est pas une brute en mathématiques, est effectivement un serpent de mer.j'ai trouvé ce lien : http://raphaello.univ-fcomte.fr/ig/a...orithmique.htm
mais je ne suis pas sûr que les trous viennent de l'agorithme de tracé, mais plutot de la rotation d'un tracé existant.
Mon but est de dessiner une forme quelle qu'elle soit, et de la faire pivoter à volonté.
Ici, le résultat que tu obtiens dépend beaucoup de la manière dont tu effectues ta rotation, ce qui n'est pas précisé ici.
Le principe de l'algo de Bresenham est double : d'une part, il s'agit de garantir un tracé continu et, de l'autre, de minimiser les calculs à effectuer de façon à obtenir un tracé rapide, ce qui était critique avec les ordinateurs d'ancienne génération, notamment les huit bits (et aujourd'hui, les micro-contrôleurs). Ceux qui ont connu cette époque étaient tous habitués à avoir une commande CIRCLE en Basic et ça paraissait normal, mais peu savent ce qu'ils doivent aux algos optimisés. C'est aussi intéressant d'aller voir comment cela était implémenté en assembleur à l'époque (et pas compilé depuis le C). Les quelques lignes de C qui suffisent à l'implémenter (principalement parce qu'il s'agit d'une formule mathématique) se traduisaient par une routine occupant 4 % de l'espace total de l'une des deux banques ROM consacrées au langage.
Pour faire cela, donc, Bresenham trace un quart de cercle en faisant « avancer » un pixel, en partant de la gauche puis le déplace soit vers la droite si on est au dessus d'un certain seuil, soit vers le haut si on est en dessous. Et pour connaître ces seuils, il dérive initialement deux fois l'équation du cercle, de sorte que la différence entre deux pixels diffère — elle-même — d'une valeur constante à chaque fois. Il est donc très facile de mettre les compteurs à jour à chaque étape. Une simple addition et une multiplication, qui étaient déjà coûteuses à l'époque parce qu'elles étaient purement logicielles, et parce qu'elles étaient obligatoirement sur 32 bits, ce qui n'était pas du tout le format naturel des machines de l'époque (un 6809, par exemple, avait des registres de 8 et 16 bits. Au dessus, il fallait faire l'addition à la main). Mais par contre, ça permettait de s'affranchir du calcul de la prohibitive racine carrée…
Tout cela pour dire que ce n'est pas forcément très difficile MAIS que l'algo en question dépend fortement du repère dans lequel il travaille : si tu veux faire pivoter ton ellipse tout en gardant un tracé rapide et continu, tu es en fait obligé de tracer une autre courbe et il faut donc modifier l'équation. Avec cela, il faut tenir compte du fait qu'en temps normal et à l'origine, une ellipse admet les axes x et y comme axes de symétrie et se comporte comme une fonction sur le quadrant traité, ce qui n'est plus possible dès lors qu'on la fait pivoter.
il est écrit "bresenham circle" car lorsque j'ai pris la capture d'écran, la zone selectionnée était le cercle. L'ellipse, quant à elle, est encore calculée en mode de sélection non graphique.
voici le code des ellipses (ex 1er quadrant):
Code c : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
et voici le code de la rotation d'un pixel:
Code c : Sélectionner tout - Visualiser dans une fenêtre à part
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
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
et donc, ci dessous, on voit le point jaune qui est l'image (je pense qu'on dit comme ça - car effectivement je suis loin d'être un brute en maths) du point rouge, avec un angle de 60°.
Sauf erreur de ma part, il manque quelque chose dans ton code.
Le premier extrait semble être Bresenham, qui te trace donc un quart d'ellipse alignée le long des axes, et le second a l'air de faire une translation de ta figure le long d'un rayon du cercle, avec des angles spéciaux. Ça va déplacer ton ellipse mais ça ne devrait pas la faire tourner elle-même…
oui ,c'est tout à fait ça. En fait celà ne fait pas tourner l'ellipse, mais ça la transforme (d'où l'impression d'applati).
voici un carré avec l'algo de rotation pixel par pixel : le résultat n'est pas du tout ce que j'attendais.
Au passage, ceci est la taille réelle de l'image produite avec l'éditeur que je programme. (mais les dimensions de l'image sont modifiables).
j'ai vu quelque part qu'il y a une matrice de rotation -T.
avec le mal que j'ai eu à programmer des effets reliefs / sobel-like, j'imagine les prises de tête qui m'attendent. Mais peut être arriverais je au résultat attendu.
Veux-tu vraiment faire toi même la "rasterization", c'est à dire la transformation forme vers ensemble de pixels?
C'est une opération intéressante d'un point de vue théorique, mais qu'il vaut mieux ne jamais coder soi-même.
Surtout que tu sembles utiliser la SDL, qui fournit cette capacité.
En fait, dans ton cas comme en 3D, on distingue plusieurs espaces:
- l'espace de modélisation, où se trouve ton ellipse, et qui correspond au monde 2D ou 3D que tu veux représenter.
- l'espace de visualisation, qui est celui depuis la caméra.
- l'espace de dessin, constitué d'une grille de pixels, c'est à dire, de petits carrés atomiques.
- l'espace d'affichage, c'est à dire l'écran, mesuré en cm²
- et l'espace de perception: l'œil, qui mesure en en angle apparant.
Les deux derniers sont hors de portée du programme, mais interviennent sur la qualité perçue de l'image.
En 2D, l'espace de modélisation est un plan, théoriquement infini et infiniment précis.
L'espace de visualisation est la partie qu'on montrera, c'est un rectangle dans le plan précédent. En général, l'information correspondante est la position et la taille de ce rectangle.
L'espace de dessin lui, correspond à la discrétisation du précédent: c'est une grille d'un certain nombre de pixels. Par exemple, sur un écran large standard, en plein écran, on dispose de 1920 pixels de large et 1080 de haut. (on parle de résolution d'écran en mode plein écran, et de taille de fenêtre sinon).
Faire tourner un objet dans l'espace de modélisation est la bonne chose à faire. C'est aussi sensément la plus aisée, et surtout la plus exacte.
Dans le plan de visualisation, c'est contre productif.
Quant à l'espace de dessin, c'est trop tard, il n'y a plus d'objets. C'est encore plus vrai quand tu t'attaqueras aux deux algorithmes important du dessin: l'antialiasing et la transparence.
En fait, ton code doit faire une distinction entre ce qu'il représente, et la manière de l'afficher.
Tu n'échapperas pas au calcul mathématique permettant de déterminer quel pixel correspond à tel point de l'espace de modélisation. La transformation inverse est inutile tant que tu ne souhaites pas faire de la sélection par clic.
Mes principes de bases du codeur qui veut pouvoir dormir:Pour faire des graphes, essayez yEd.
- Une variable de moins est une source d'erreur en moins.
- Un pointeur de moins est une montagne d'erreurs en moins.
- Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
- jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
- La plus sotte des questions est celle qu'on ne pose pas.
le ter nel est le titre porté par un de mes personnages de jeu de rôle
Oui, mais même. Vu comme cela, ta figure, quelle qu'elle soit, devrait être translatée dans le plan mais pas déformée ni pivotée. Après une deuxième lecture, je m'aperçois qu'il y manque le « +x » correspondant au +y de la ligne suivante :
Apparemment, c'est ce « trou » qui provoque la déformation de ton image. Mais ce n'est pas une rotation.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3case 330 : coordonnees_du_point_en_x = origine_en_x + (Distance * sqrt(3) / 2); coordonnees_du_point_en_y = origine_en_y + y + (Distance / 2);
C'est celle-ci :
| cos(α) -sin(α) | | sin(α) cos(α) |
… soit en algèbre habituelle :
x' = x⋅cos(α) - y⋅sin(α) y' = x⋅sin(α) + y⋅cos(α)
À noter que tu peux tout-à-fait écrire une fonction qui prenne en paramètre une paire de coordonnées x,y et un angle, et qui te retourne une autre paire x',y'. Tu peux ensuite passer à cette fonction les coordonnées initiales calculées par ton Bresenham, et tu obtiendras bien l'ellipse pivotée que tu convoites. MAIS :
- Tu auras quand même des trous car le mapping ne sera pas parfait du fait que les coordonnées d'arrivée ne seront pas des nombres entiers. Le problème sera exactement le même que si tu traçais une ellipse dans un logiciel de dessin et que tu appliquais ensuite une rotation sur l'ensemble de l'image ;
- L'algorithme sera catastrophique en terme de performances, même si à l'œil nu, le rendu sera immédiat sur une machine moderne.
Bonjour
Je ne sais pas quel est ton niveau en mathématique, mais si tu connais le principe de repère polaire:
Alors tu peux facilement avoir une équation pour ton ellipse et lui appliquer Bresenham (ou autre) puisque la rotation en système polaire est simple puisque pour une rotation de a, il suffit de calculer r(θ+a).Dans le repère défini par le centre et l'axe focal, [ l'équation polaire de l'ellipse de demi-axes a et b ] est
avec
(e représente l'excentricité de l'ellipse.)
Après, la rasterisation, c'est une autre paire de manches...
Hello,
Ça vaut le coup de le souligner en effet mais malheureusement, ici, ça n'a pas beaucoup d'utilité, parce que les coordonnées des pixels d'un ordinateur sont cartésiennes par nature. Cela veut donc dire qu'il faudrait ensuite qu'il faudrait reconvertir les coordonnées de chaque point vers ses coordonnées cartésiennes. Et peut-être même les convertir d'abord depuis les coordonnées rectangulaires vers les polaires si on utilise un générateur de figure distinct.
En outre, dans l'équation que tu nous présentes, la clé est la fonction cos(). C'est elle qui module le rayon de l'ellipse au fur et à mesure que l'on tourne autour du pôle. Donc, on perd tout le bénéfice des algos type Bresenham ou autre, et on retombe dans le problème initial, c'est-à-dire la discontinuité de la courbe formée par les pixels successifs.
Je n'avais pas vu ton message en répondant, et effectivement ta solution est meilleure dans ce cas de figure que la mienne.
On retombe dans un grand dilemme de l'informatique, la solution la plus simple/esthétique mathématiquement est souvent loin d’être la plus simple/rapide à calculer en pratique.
(Note toutefois que si cette solution est inadaptée ici, un changement de repère peut parfois simplifier drastiquement les calculs, donc c’est intéressant de savoir le faire en cas de besoin.)
Merci Obsidian pour ces précisions
Merci Obsidian pour ces explications quant à la matrice de rotation.
emixam16, mon niveau en maths s'arrête bien avant ta démonstration.
Aprés plusieurs erreurs et prises de tête, (les points ne se trouvaient pas du tout là où ils devaient être après leur rotation) je me suis aperçu (ça doit être évident pour vous mais à coup sûr pas pour moi) qu'il fallait convertir les degrés en radians.
J'ai donc abandonné ma première fonction, car on ne peut pas choisir l'angle qu'on veut, pour celle ci:
Code c : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
Maintenant les pixels sont à l'endroit prévu par le cercle trigonométrique en fonction de l'angle que je chosis pour les faire pivoter.
Reste ce problème des trous. Les ellipses, quant à elles, ne sont plus déformées / applaties .
Je continue donc à chercher une solution.
ici, le carré subit une rotation de 145 degrés et une de 225 degrés.
je crois que j'ai trouvé une piste (discussion de 2006 sur le forum de ce site) :
https://www.developpez.net/forums/d1...on-d-image-2d/Ce dont tu parles c'est d'une interpolation bi-linéaire (ordre 1).
En outre, c'est ainsi que l'on fait la rotation d'une image, en calculant pour chaque pixel de l'image d'arrivée les coordonnées correspondantes du pixel de l'image de départ. Dans l'autre sens on se retrouve avec des "trous" dans l'image d'arrivée.
Donc soit tu peux faire une rotation bête et méchante sans interpolation (ça marche quand même et ça reste propre) (donc la coordonée x=5.78 deviendra x=6), soit tu peux faire avec interpolation bi-linéaire :
Tu veux calculer le niveau de gris du couple d'entier (x2;y2) de l'image d'arrivée, en faisant la rotation inverse tu te retrouves avec le couple de floattants (x1;y1) de l'image de départ auquel tu peux adjoindre 4 couples d'entiers :
- le couple C1 (x11; y11) avec un niveau de gris G1
- le couple C2 (x11+1; y11) avec un niveau de gris G2
- le couple C3 (x11; y11+1) avec un niveau de gris G3
- le couple C4 (x11+1; y11+1) avec un niveau de gris G4
Ne fait jamais de Jeux vidéo , j'ai jamais vu un truc aussi long x)
Faire du cos/sinus a chaque pixel voila quoi (enfin faire un appel de fonction sur chaque pixel c'est aussi quelque chose d'assez long aussi )....
Sinon la rastérisation ne se fait pas comme cela , il faut que tu dessine ligne par ligne , ce que tu dois calculer c'est néanmoins les deux extrémité (de chaque ligne).
Mais pas avec cos/sin , on calcule normalement les 4 sommets (vertex) ensuite quand on connaît ces 4 sommets on peut connaître l'extrémité , et puis on dessine une ligne (ce qui est très rapide du coup).
La 3D n'est guère différente , on met une matrice de projection et ça fait de la 3D :p
(même si le mieux c'est de faire un Z-Buffer pour prendre en compte la profondeur).
Et ton souci des trous sera résolu en passant
Merci pour les encouragementsNe fait jamais de Jeux vidéo , j'ai jamais vu un truc aussi long x)
Si je comprends bien il faut que je laisse tomber l'interpolation bilinéaire. Soit. Je vais donc aller chercher des infos sur la rastérisation.
Je ne suis pas tendre certe , mais il est important de choisir les bon algo et connaître les bonnes optimisations.Merci pour les encouragements
Il ne faut pas toujours se satisfaire du code qu'on possède (surtout que même si on réinvente la roue dans ton cas , faudrait pas trop que cela soit trop long comparé a l'existant).
**voix de vieux** a une époque on devait les pre calculer les cos/sin , tu vois mon enfant les cpu était trop long et n'avait pas de FPU intégré **tousse**
Bref j'espere que tu utilisera cos/siin avec parcimonie , de nos jours ça a guère changer pour les gros calcul on évite de les faire trop souvent ou en les pre-ecalcul si certaines valeurs revienne souvent.
Mais pour ce genre de calcul on utilise une matrice en général : https://jeux.developpez.com/faq/math...ransformations
Tu pourrait dans un premier temps tenté de le faire avec les info que je t'ai énoncé , une droite , un segment étant linéaire , il est facile de prédire ou se trouvera les points.
Sinon il existe OpenGL qui te le ferait très rapidement (en terme de code et de performance).
Sinon il existe aussi quelque lib Allegro qui doit le faire je crois en soft , ou lire des codes sources (certain émulateur permet les faire en software par exemple MAME) , je crois que Mesa aussi a une version software.
Certes tu n es pas tendre mais ça ne me dérange pas. "Entrainement difficile guerre facile" comme on dit, et puis, c'est constructif.
Sinon . Peut on par exemple calculer les coordonnées uniquement des sommets d une figure quelconque qu on veut faire pivoter, appliquer cos et sin uniquement sur ces sommets, puis calculer les scanlines à partir des nouvelles coordonnées des sommets ?
oui c'est ce qu'il faut faire , mais pas simple tout même en pratique bonne chance.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager