	Dithering couleur
	*****************


	Aprs vous avoir parl du filtre de Bayer en monochrome,
attaquons-nous au dithering couleur. Je vais vous prsenter la mthode
dite "ordered dithering". Son application la plus vidente est l'affichage
d'images 16, 24 ou 32 bits sur un cran 256 couleurs. Mais, supposons que
vous ayez  afficher sur une seule page plusieurs images 256c n'ayant pas
la mme palette, le recours au dithering est sans doute la meilleure
solution puisqu'il utilise une palette fixe!

LES 216 COULEURS
----------------

	Cette palette contient toutes les combinaisons possibles avec 6
niveaux de rouge, six niveaux de vert et six niveaux de bleu. Elle est
ainsi construite  partir de l'index 0 (les valeurs sont les triplets
R,V,B):

	0,0,0
	51,0,0
	102,0,0
	153,0,0
	204,0,0
	255,0,0
	0,51,0
	51,51,0
	102,51,0
	etc...

	255,255,255

	On remarque que les couleurs augmentent par pas de 51, en effet,
il y a six multiples de 51 entre 0 et 255. On remarque galement que le
rouge change  chaque index, le vert change tous les six indexs et le bleu
ne change que tous les 36 indexs.

PREMIERE UTILISATION
--------------------

	Supposons que je doive reprsenter la couleur R=29, V=121, B=209.
Je peux chercher dans ma palette la couleur s'en approchant le plus:
	Ainsi 29/51=0, je choisis le niveau 0 de rouge R=0
	De mme 121/51=2, je choisis le niveau 2 de vert V=102
	Et 209/51=4, je choisis le niveau 4 de bleu B=204.
	Par un simple calcul j'obtiens la valeur de l'index qui
m'intresse:
	I = Niveau R*1 + Niveau V*6 + Niveau B*36
	I = 0 + 12 + 144 = 156.

	C'est donc la couleur 156 de ma palette qui vaut (0,102,204) qui
s'approche le plus, par dfaut, de la couleur que je voulais reprsenter.
Cette mthode simple ne donne pas encore de bons rsultats. En effet, si
j'ai un fond uni, j'obtiens par dithering un autre fond uni mais d'une
couleur diffrente. On a donc affin la mthode...

ORDERED DITHERING
-----------------

	On constate que les divisions par 51 ne tombent pas forcment
justes. Il me reste 29 pour le rouge, 19 pour le vert et 5 pour le bleu.
On va encore une fois utiliser une matrice contenant des valeurs de 0
 50, c'est  dire les restes possibles d'une division par 51,
judicieusement rparties dans un carr de 16 sur 16.
	Selon la position d'un pixel dans l'image, on prendra une valeur
prcise de la matrice et, si les restes dpassent cette valeur on
augmentra de 1 le niveau des composantes. Reprenons notre pixel prcdent
et piochons quelques valeurs M de la matrice:

	Si M=34, il est suprieur aux trois restes, je garde donc l'index
	156.

	Si M=20, le reste de rouge (29) dpasse M, j'augmente donc de 1 le
	niveau de rouge et je recalcule:
	I= 1 + 12 + 144 = 157

	Si M=10, les restes de rouge et vert dpassent M, j'augmente de 1
	ces deux niveaux et je recalcule:
	I= 1 + 18 + 144 = 163

	Si M=0, les trois restes dpassent M, jes les augmente tous et je
	recalcule:
	I= 1 + 18 + 180 = 199.

	On voit que, selon la valeur de M, mon pixel d'origine sera
preprsent par l'une des quatre couleurs suivantes de ma palette fixe:
156, 157, 163 ou 199. Toujours avec un fond uni au dpart, j'obtiendrai un
mlange de ces 4 couleurs, dans des proportions dpendant des restes, qui
donneront l'illusion de la couleur d'origine.

LES TABLES
----------

	Les tables utiles au programme sont: les quotients et les restes
par 51 de tous les entiers compris entre 0 et 255 ainsi que la fameuse
matrice 16x16.
	Vous remarquerez que les quotients correspondent directement au
niveaux de rouge, vert et bleu. Dans la formule donnant I, on remarque
galement que le niveau de rouge est TOUJOURS multipli par 1, celui de
vert par 6 et celui de bleu par 36. J'ai donc construit 3 tables
diffrentes avec les prmultiplications, notre routine vitera donc ces
calculs lourds.

restes:
	rept 5
	dc.b 0,1,2,3,4,5,6,....,50
	endr
	dc.b 0

;  256 octets de "restes"

quot_rouge:
	dcb.b 51,0
	dcb.b 51,1
	dcb.b 51,2
	dcb.b 51,3
	dcb.b 51,4
	dc.b 5

;  512 octets de "restes"

quot_vert6:
	dcb.b 51,0
	dcb.b 51,6
	dcb.b 51,12
	dcb.b 51,18
	dcb.b 51,24
	dc.b 30

;  768 octets de "restes"

quot_bleu36:
	dcb.b 51,0
	dcb.b 51,36
	dcb.b 51,72
	dcb.b 51,108
	dcb.b 51,144
	dc.b 180

; plus la matrice est grande, moins on note une rgularit de trame 
; l'cran, la matrice 16x16 donne de bien meilleurs rsultats qu'une
; 8x8 qui aurait pourtant t suffisante pour loger les 51 valeurs:

matrice16_16:
	dc.b 34,5,21,44,32,3,20,42,33,4,21,43,35,6,22,44
	dc.b 15,50,28,12,13,48,26,10,14,49,27,11,15,51,28,12
	dc.b 31,8,18,47,29,7,16,45,30,8,17,46,32,9,19,48
	dc.b 25,41,37,2,23,39,36,0,24,40,37,1,25,41,38,3
	dc.b 33,4,20,43,35,6,22,45,34,5,21,43,33,4,20,42
	dc.b 14,49,27,10,16,51,29,13,14,50,27,11,13,49,26,10
	dc.b 30,7,17,46,32,9,19,48,31,8,18,47,30,7,17,46
	dc.b 23,39,36,1,26,42,38,3,24,40,37,2,23,39,36,1
	dc.b 34,5,21,44,33,4,20,42,33,4,20,43,35,6,22,45
	dc.b 15,50,28,11,13,49,26,10,14,49,27,11,16,51,29,12
	dc.b 31,8,18,47,29,7,16,45,30,7,17,46,32,9,19,48
	dc.b 24,40,37,2,23,39,36,0,24,40,36,1,25,41,38,3
	dc.b 34,5,21,43,35,6,22,44,34,5,22,44,32,3,19,42
	dc.b 14,50,27,11,15,51,28,12,15,50,28,12,13,48,26,10
	dc.b 30,8,18,46,31,9,19,47,31,9,18,47,29,6,16,45
	dc.b 24,40,37,1,25,41,38,2,25,41,38,2,23,39,35,0

LE PROGRAMME
------------

	En entre, les mots "hauteur" et "largeur" doivent contenir les
dimensions de l'image. "Source" contient l'adresse d'une image 24 bits
contenant les triplets R, V, B pour chaque pixel. "Dest" contient
l'adresse de l'image en 216 couleurs  calculer avec un octet par pixel,
c'est--dire l'index de couleur I.

	Carte des registres:

D0: les composantes R,V,B
D2: la valeur courante de la matrice
D3: l'index I
D4: largeur-1
D6: compteur de lignes
D7: compteur de pixels par ligne

A0: pointe sur les tables restes et quotients
A1: l'image source
A2: pointe sur la valeur courante de la matrice
A3: images destination
A4: fin de ligne matrice pour A2

	Remarquez les comparaisons d'octets: s'agissant de valeurs non
signes (de 0  255 et non de -128  +127) il faut utiliser la retenue
(Carry) pour savoir lequel est le plus grand: bcc veut dire "branch if
carry cleared" c'est--dire sauter si il n'y a pas de retenue.

	Le programme tourne sur n'importe quel 680x0, je n'utilise aucun
code ni accs rserv au 68030.


dither_216:
	move.l source,a1
	lea restes,a0
	move.l dest,a3
	move hauteur,d6
	subq #1,d6
	move largeur,d4
	subq #1,d4
	lea matrice16_16,a2
	moveq #0,d0
.ligne:
	move d4,d7
	lea 16(a2),a4
.pixel:
	; valeur M
	move.b (a2)+,d2
	; couleur ROUGE dans d0
	move.b (a1)+,d0
	; niveau de ROUGE dans d3=I
	move.b 256(a0,d0.w),d3
	; reste de ROUGE>M?
	cmp.b 0(a0,d0.w),d2
	bcc.s .pas_rouge
	; si suprieur  M, on ajoute 1  I
	addq.b #1,d3
.pas_rouge:
	; idem pour l'octet VERT
	move.b (a1)+,d0
	add.b 512(a0,d0.w),d3
	cmp.b 0(a0,d0.w),d2
	bcc.s .pas_vert
	addq.b #6,d3
.pas_vert:
	; idem pour l'octet BLEU
	move.b (a1)+,d0
	add.b 768(a0,d0.w),d3
	cmp.b 0(a0,d0.w),d2
	bcc.s .pas_bleu
	add.b #36,d3
.pas_bleu:
	; range l'index I
	move.b d3,(a3)+
	; fin de ligne matrice?
	cmp.l a2,a4
	bne.s .pas_fin
	; si oui, reculer de 16
	lea -16(a4),a2
.pas_fin:
	dbf d7,.pixel
	; fin de matrice?
	cmp.l #matrice16_16+256,a4
	bne.s .pas_fin_matrice
	; si oui, revenir 16 lignes au dessus
	lea -256(a4),a4
.pas_fin_matrice:
	move.l a4,a2
	dbf d6,.ligne
	rts

CONCLUSION
----------

	La mthode prsente ici est celle qui est utilise dans GEMVIEW
par exemple ou dans M_Player lorsqu'il convertit une animation. Je sais
que tout le monde n'utilise pas l'assembleur mais je prfre vous donner
un programme qui tourne (quoiqu'une faute de frappe ou une ligne oublie,
c'est vite arriv!) plutt qu'un semblant de programme dans un autre
langage que je ne matrise pas.
	Vous voil prts  tramer en 256 couleurs. Avec les routines de
conversion pixel->8 plans dj prsentes, vous pourrez galement afficher
vos images sur un cran Atari.
	Je vous dis  la prochaine fois!

	Guillaume Tello
	gtello@wanadoo.fr