Discussion :

[piponux]

NdlM : discussion scindée depuis la discussion « Rotation d'ellipses en langage C », à partir du message #24.

re bonjour.
Je suis en train de me documenter sur la façon dont fonctionne l'algorithme de scanline fill.
j'ai acheté le livre "Computer Graphics : Principles and practice", de, entre autre, James D. Foley, en occas sur Amazon.
A l'intérieur, il parle de "bucket sort" pour les Sorted Edge Table.
Je n'arrive pas à traduire la signification de "bucket sort". Je vois bien qu'il s'aqit d'un tri, mais lequel?
Au passage, j'ai vu sur le site wiki que l'invention du scanline fill est revendiquée par un français. Or, aucune documentation n'est disponible en Français. Pourquoi?

[Obsidian]

Bonjour,

A l'intérieur, il parle de "bucket sort" pour les Sorted Edge Table.
Je n'arrive pas à traduire la signification de "bucket sort". Je vois bien qu'il s'aqit d'un tri, mais lequel ?

Le bucket sort, apparemment appelé tri par paquets en français. Je ne le connais pas beaucoup. Apparemment, il ressemble un peu au tri fusion…

Au passage, j'ai vu sur le site wiki que l'invention du scanline fill est revendiquée par un français. Or, aucune documentation n'est disponible en Français. Pourquoi?

Parce qu'honnêtement, à mon avis, tout le monde y a plus ou moins pensé tout seul. C'est un peu comme le buffer circulaire ou autres concepts élémentaires. Bien souvent, le problème présenté tel quel paraît ésotérique mais il suffit souvent de se demander comme on s'y prendrait, soi-même, pour le résoudre pour se rendre compte qu'on suivrait le même chemin et aboutirait à la même solution en une vingtaine de minutes.

C'est un peu comme l'approche pair-impair pour remplir un polygone, fût-il concave par endroits. On comprend que la première chose à faire pour remplir l'intérieur de ce polygone est de définir ce que l'on entend par « intérieur ». Et là, on voit bien que si l'on part des limites de la zone d'affichage, on se trouve bien dans « l'extérieur » par défaut. Puis, à partir du moment où je rencontre une frontière, quelle qu'elle soit, c'est que je passe de l'extérieur à l'intérieur. Si j'en rencontre une nouvelle, c'est que je ressort à l'extérieur. Si j'en rencontre une troisième, je repasse à l'intérieur, et ainsi de suite… et ce, quelle que soit ma trajectoire !

Il arrive aussi que les gens à qui on accorde la paternité d'un concept l'aient découvert très tôt dans l'histoire, mais c'est bien souvent, là aussi, parce qu'ils s'agissait de personnes qui travaillaient sur le sujet en laboratoire au sein d'un projet plus vaste, qui par conséquent avait accès à des machines qui ne l'étaient pas encore au grand public, et qui ont fait la même démarche à ce moment-là. Et la plupart du temps, ces gens ne revendiquent pas la découverte d'un concept particulièrement révolutionnaire. Celui-ci est simplement consigné parce que c'était normal de le faire à ce moment.

[piponux]

bon, je dois reconnaître que c'est quand même balaise pour mon niveau. Je vais donc utiliser le code qui se trouve dans le livre "Computer Graphics" de Hearn, page 120-124.
Celà vous paraissait il aussi dur à coder vous même lorsque vous étiez étudiant, disons dans la première / deuxième année?

[Kannagi]

Pour ma part le code d'un Scanline fill je l'ai trouvé sur M.A.M.E (un émulateur de borne d'acade et le but n'était pas vraiment de trouver cette fonction , je cherchais par curiosité comment fonctionné certaine machine).

Voila le code source légèrement modifié par mes soins :

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
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
 
 void fill_slope(SDL_Surface* surface,SDL_Surface* texture, int color, int x1, int x2, int sl1, int sl2, int y1, int y2, int *nx1, int *nx2,struct m1_fpoint *tp)
{
 
/*
	if(y2 > view->y2)
		y2 = view->y2+1;
 
	if(y1 < view->y1) {
		int delta = view->y1 - y1;
		x1 += delta*sl1;
		x2 += delta*sl2;
		y1 = view->y1;
	}
*/
	int ix,x;
	if(x1 > x2 || (x1==x2 && sl1 > sl2)) {
		int t, *tp;
		t = x1;
		x1 = x2;
		x2 = t;
		t = sl1;
		sl1 = sl2;
		sl2 = t;
		tp = nx1;
		nx1 = nx2;
		nx2 = tp;
	}
 
	//
 
	int y = y1;
	int i, l = 0;
	//printf("\n----------------------\n");
	int *tex = texture->pixels;
	while(y1 < y2) {
		//if(y1 >= view->y1) {
			//int xx1 = x1>>FRAC_SHIFT;
			int xx2 = x2>>FRAC_SHIFT;
			//if(xx1 <= view->x2 || xx2 >= view->x1) {
				//if(xx1 < view->x1)
					//xx1 = view->x1;
				//if(xx2 > view->x2)
					//xx2 = view->x2;
 
					ix = x1>>FRAC_SHIFT;
 
					int *p = (int*)((char*)surface->pixels + y1 * surface->pitch + ix * 4);
					int *p2 = (int*)((char*)surface->pixels + y1 * surface->pitch + xx2 * 4);
 
 
 
					float coef = (float)(y2-y1)/(float)(y2-y);
					int i = (int)(texture->w*coef)*(texture->h);
					l += sl1>>FRAC_SHIFT;
 
					//i = (y2-y1)*(texture->w);
 
					//printf("(%d %d),",i,(int)(coef*texture->h) );
 
					while(p <= p2)
					{
					//SDL_PutPixel32(surface,ix,y1,color);
 
					*p = 0x00FF;tex[i];
					p++;
					i++;
					//ix++;
				}
 
 
					//draw_hline(surf, xx1, xx2, y1, color);
			//}
		//}
 
		x1 += sl1;
		x2 += sl2;
		y1++;
	}
	*nx1 = x1;
	*nx2 = x2;
}
 
 void fill_tri(SDL_Surface* surf,SDL_Surface* texture,int bitmap, const struct quad_m1 *q)
{
	int sl1, sl2, cury, limy, x1 = 0, x2 = 0;
	int pmin, pmax, i, ps1, ps2;
	struct m1_spoint p[8];
	struct m1_fpoint tp[8];
 
	tp[0].x = 0;
	tp[0].y = 0;
 
	tp[1].x = 1;
	tp[1].y = 0;
 
	tp[2].x = 0;
	tp[2].y = 1;
 
	for(i=0; i<3; i++) {
		p[i].x = p[i+3].x = q[i].x << FRAC_SHIFT;
		p[i].y = p[i+3].y = q[i].y;
	}
 
	pmin = pmax = 0;
	for(i=1; i<3; i++)
	{
		if(p[i].y < p[pmin].y)
			pmin = i;
		if(p[i].y > p[pmax].y)
			pmax = i;
	}
 
	cury = p[pmin].y;
	limy = p[pmax].y;
 
	if(cury == limy)
	{
		x1 = x2 = p[0].x;
		for(i=1; i<3; i++) {
			if(p[i].x < x1)
				x1 = p[i].x;
			if(p[i].x > x2)
				x2 = p[i].x;
		}
 
		Line(surf,x1>>FRAC_SHIFT, cury, x2>>FRAC_SHIFT, limy,bitmap);
		return;
	}
 
 
 
	ps1 = pmin+3;
	ps2 = pmin;
 
	while(p[ps1-1].y == cury)
		ps1--;
	while(p[ps2+1].y == cury)
		ps2++;
	x1 = p[ps1].x;
	x2 = p[ps2].x;
	sl1 = (x1-p[ps1-1].x)/(cury-p[ps1-1].y);
	sl2 = (x2-p[ps2+1].x)/(cury-p[ps2+1].y);
 
 
	if(p[ps1-1].y == p[ps2+1].y)
	{
		fill_slope(surf,texture, bitmap, x1, x2, sl1, sl2, cury, p[ps1-1].y, &x1, &x2,tp);
		return;
	}
 
 
	if(p[ps1-1].y < p[ps2+1].y)
	{
 
		for(;;)
		{
			fill_slope(surf,texture, bitmap, x1, x2, sl1, sl2, cury, p[ps1-1].y, &x1, &x2,tp);
 
			cury = p[ps1-1].y;
			if(cury >= limy)
				break;
			ps1--;
			while(p[ps1-1].y == cury)
				ps1--;
			x1 = p[ps1].x;
			sl1 = (x1-p[ps1-1].x)/(cury-p[ps1-1].y);
		}
		return;
	}
	for(;;)
	{
		fill_slope(surf, texture,bitmap, x1, x2, sl1, sl2, cury, p[ps2+1].y, &x1, &x2,tp);
		cury = p[ps2+1].y;
		if(cury >= limy)
			break;
		ps2++;
		while(p[ps2+1].y == cury)
			ps2++;
		x2 = p[ps2].x;
		sl2 = (x2-p[ps2+1].x)/(cury-p[ps2+1].y);
	}
 
}

Je trouve pas le code terrible , j'aurais fait très différemment je pense !
Disons que j'ai aucun intérêt pratique a le refaire (sauf sur un Atari ST et encore je l'aurais codé en assembleur sur cette bécane ).

Pour ton autre question , je ne pense pas que en 1ere/2eme année j'aurais réussi a refaire ce genre de truc , disons que pour ma part mon but principal les premières années était de maîtrisé le C est de respecté certain paradigme codé sans effet de bord , des fonctions facile a utilisé et utilisable sur n'importe quel programme , j'ai mis quelque année pour réussir ces trois choses correctement , c'est après que je me suis plus concentré sur l'algorithme et le bas niveau.

[piponux]

hello.
ça me rassure ce que tu dis car je n'aurais vraiment pas été capable de reproduire le code du livre "Computer Graphics" de Hearn. Quand j'aurais le temps je le copierai / collerai ici.
Pour ma part, je ne "code" en c qu'environ, en moyenne, deux ou trois heures par semaine, depuis deux ans, avec des pauses de plusieurs mois. Ma principale source est l'ensemble de videos publiées par Jacques Olivier Lapeyre, même si je commence à lire des bouquins.
Je comprends bien l'algorithme des scanline fill, mais l'implémenter correctement, c'est une autre histoire.
C'est peut être pour celà que la grande majorité des cours internet se basent exactement sur le même exemple, à savoir celui publié dans le livre "Computer Graphics" de Foley.

J'envisage de me procurer le livre sur Allegro 5 de Frédéric Drouillon, afin de voir comment est fait un squelette de jeu vidéo en c. Que pensez vous de ce choix? sachant que c'est un des rares (le seul?) bouquin en français.

[Kannagi]

Je ne suis pas très livre et je te dirai que je te le déconseille ,disons que si tu veux apprendre la prog de jeux vidéo ben.... il faut coder coder et encore coder ! (fait plein de démo )
Le livre est bien peut être mais je pense qu'il t'apprendra plus la lib Allegro que la prog de jeux vidéo (après je n'en sais rien j'ai pas lu le livre).

En général je propose de se concentrer sur :
-La gestion de la fenêtre/contexte
-Les evenement clavier/souris/joypad
-Les FPS (frame par seconde)
-La gestion des sprites (animée ou non)
-Du Background
-La Caméra
-Les Collisions

Et deja la tu a deja du boulot a faire , et cela te permettra d'apprendre a coder de manière modulaire , chaque partie peut être complètement indépendante.
Ce que j'ai énumérer suffit pour la plupart des jeux 2D.