Dans l'article précédent, nous avions les bases de la programmation graphique: les conseils aux programmeurs et les fonctions utiles du BIOS. A l'époque, je ne connaissais pas encore Linux. Depuis, cette lacune a été comblée. Dans tout ce qui va suivre, les techinques utilisées sont applicables à Linux moyennant certaines précautions. Toutes les modifications à effectuer aux exemples ci dessous, de même que ce qui n'a pas pu etre traité dans l'article précédent sera regroupé dans la fin de l'article.

Dans cet article, nous allons voir les primitives de dessin en mode 13h, appliquées au jeux video. Dans ce domaine, l'imagination et la reflexion sont plus importante que la connaissance. C'est pour ca que chaque primitive sera presentée de facon progressive, en partant de la fonction standard et universelle pour arriver aux routines optimisées en vitesse. Le but d'une telle demarche est de vous faire acquérir les mécanismes de raisonnement nécessaire afin de l'appliquer à des choses autres que celles traitées ici.
Les routines que je vous présente ici sont les plus rapide que j'ai pu imaginer. Il est possible que vous puissiez trouver encore mieux. Si c'est le cas, je serais heureux que vous me fassiez parvenir ce que vous avez obtenus.

I] Disposition de la mémoire en mode 13h.

Le mode 320 X 200, 256 couleurs est le mode standard le plus utilisé dans la programmation des jeux vidéo en raison de sa simplicité d'utilisation. De plus, il offre une richesse de couleur assez élevé qui compense largement sa faible résolution.
Dans ce mode, la mémoire commense à l'adresse A000:0000 et mesure 64000 octets d'un seul tenant. Le programmeur peut donc facilement accéder à tous les pixels de l'écran. De plus, contrairement aux modes 16 couleurs, chaque octet représente un pixel et chaque pixel est codé par un octet. Les pixels sont disposés linéairement en mémoire en partant du coin supérieur gauche et en parcourant l'écran de gauche à droite et de haut en bas. Ceux qui ont programmé les modes 16 couleurs apprécieront la simplicité.
Dans ce mode, l'adresse d'un pixel (X,Y) en mémoire se calcule par la formule suivante : offset = 320 * Y + X

II] Primitives de dessins

1) Afficher un pixel.

Comme il a été dit plus haut. La mémoire vidéo est organisée de manière linéaire, chaque octet correspondant à un pixel. Chaque ligne fait 320 octets. La position d'un pixel (X,Y) en mémoire vidéo est : 320 x Y + X.

char *VideoRam = (char *) MK_FP(0xA000,0000); // pointeur sur ram vidéo

VideoRam[320 * Y + X] = Couleur; // allume un pixel à une couleur donnée
Couleur = VideoRam[320 * Y + X]; // lit la couleur d'un pixel

Peut on faire mieux. Cela semble dur. Comment peut on faire mieux qu'une simple multiplication et une addition. Justement, la multiplication est avec la division, l'operation arithmétique la plus lente. Ne pourrait on pas la remplacer par autre chose. Nous savons que nous pouvons remplacer une multiplcation par une puissance de deux par un décalage de bits vers la gauche. Seulement 320 n'est pas une puissace de 2. Mais, 320 = 256 + 64. Deux décalage et une addition seraient donc équivalent à une multiplication par 320. Reecrivons la fonction d'affichage de pixel en remplacant 256 et 64 par le decalage de bits correspondant.

char *VideoRam = (char *) MK_FP(0xA000,0000); // pointeur sur ram vidéo

VideoRam[(Y << 8) + (Y << 6) + X] = Couleur; // allume un pixel à une couleur donnée
Couleur = VideoRam[(Y << 8) + (Y << 6) + X]; // lit la couleur d'un pixel

A l'usage, cette routine fonctionne bien plus vite que la routine précédente.

2) Tracer des lignes.

a) Cas général.

Tracer une ligne équivaut à tracer chacun des pixels qui composent la ligne. La ligne étant un objet mathématisé, sa représentation à l'écran est assez simple.
Considérons une ligne allant de (Xd,Yd) à (Xf,Yf). Chaque point (Xn,Yn) de cette ligne respecte l'équation suivante :

Y = m * X + p

 
où m représente la pente de la droite et p l'ordonnée à l'origine.
Tout le probleme est donc de déterminer m et p, puis de parcourir toutes les valeurs de Xd a Xf et de calculer la valeur de Y correspondante.
Premier probleme. Combien de pixels devront nous calculer. Souvenont nous que les pixels ont des coordonnées entières. Si le deplacement en X est supérieur au deplacement en Y, pas de problème, en calculant un point pour chaque valeur entière de X, les points seront bien jointifs. Mais si c'est le contraire, les points de la ligne seront disjoints. Ce cas est assez simple également, il suffit de calculer X pour chaque valeur de Y en utilisant l'équation inverse:

X = (Y - p) / m

 
Si on pose m' = 1 / m et p' = - p / m, on aboutit a l'equation suivante :

X = m' * Y + p'

 
Comme vous pouvez le remarquer la forme de cette équation est identique à la première, avec des valeurs de m et p différentes. Ca veux dire que les meme formules vont servir dans les deux cas. Je vais vous donner les formules pour le premier cas, uniquement. Pour obtenir les formules pour le second cas, il suffira juste d'echanger X et Y dans les équations.

En faisant de simples transformations mathématiques, on obtient assez facilement les formules qui permettent le calcul de m et de p à partir des extremités du segment de droite :

m = (Yf - Yd) / (Xf - Xd);

p = Yd - m * Xd;

for (X = Xd; X <= Xf; X++){

Y = m * X + p;

VideoRam[(Y<<8 + Y << 6) + X] = couleur;

}

Ceci n'est qu'un exemple. Dans un vrai listing, il aurait fallu faire les transtypage nécessaires dans le calcul de m parce que cette valeur est flottante. Dans l'article précédent, j'avais proscris l'utilisation des types flottants. Malheureusement, nous n'avons pas encore les connaissances necessaire pour nous l'éliminer. Nous devrons donc nous en accomoder jusqu'à ce que je vous parle des optimisations.
Malgré ceci, cette routine fonctionne. Mais peut on faire mieux ? (Comme vous avez pu le constater jusqu'a present, cette question est celle que nous nous posons le plus souvent). En fait dans le calcul du pixel, nous avons une multiplication à l'interieur d'une boucle. C'est genant, j'aimerai bien la supprimer. Le probleme c'est que m est variable, et de plus non entier. Nous ne pouvons pas le remplacer par un decalage. Mais on peut quand même supprimer cette multiplication.

Une multiplication, ce n'est rien d'autre qu'une serie d'addition. Nous allons donc remplacer la multiplication par une addition. Quand X varie de 1, Y varie de combien ? C'est simple, de m. Mais attention, Y doit a son tour être défini comme une variable flottante. D'ou la nouvelle boucle :

  for(X = Xd, Y = Yd; X <= Xf; X++, Y += m)
VideoRam[(Y << 8) + (Y << 6) + X] = couleur;

 
Tiens, vous avez remarqué, p n'intervient plus dans le calcul de Y. C'est génial ca, ce n'est plus la peine de calculer p, on économise une multiplication de plus.

Le simple fait de supprimer cette multiplication a fortement accéléré cette routine. Que peut on améliorer d'autre ? En fait, pas grand chose. Nous pourrions déjà supprimer les variables flottantes. Il y a une technique pour ça, l'arithmétique en virgule fixe, mais cette technique est suffisament complexe pour mériter un article à elle seule. Nous la reverrons ultérieurement.
Il y a aussi des cas particuliers de lignes qui peuvent être tracée beaucoup plus rapidement que dans le cas général. Ce sont les lignes horizontales, verticales et inclinées à 45 degrés. Nous allons les étudier maintenant.


b) Lignes particulières

Dans les jeux vidéo, il est rare de tracer des lignes quelconques, sauf pour les dessins en fils de fer. En revanche, les lignes verticales et horizontales sont assez fréquentes, de plus elles sont faciles à implementer.

char *VideoRam = (char *) MK_FP(0xA000,0000); // pointeur sur ram vidéo
for(X = XD; X <= XF; X++)
VideoRam[320 * Y + X] = Couleur;

tracé de ligne horizontale
char *VideoRam = (char *) MK_FP(0xA000,0000); // pointeur sur ram vidéo
for(Y = YD; X <= YF; Y++)
VideoRam[320 * Y + X] = Couleur;

tracé de ligne verticale

Ces deux routines fonctionnent, mais il est possible de faire nettement mieux. Examinons d'abord le tracé de la ligne horizontale. Si on regarde de plus prés, on constate que tracer une ligne horizontale revient à remplir un bloc d'octet contigüe avec la même valeur. Une fonction de la librairie standard du C fait ceci : memset. Nous pouvons reecrire la fonction de la facon suivante :

unsigned int Debut = 320 * Y + XD;
memset(VideoRam+Debut,(XF-XD+1), Couleur);

tracé de ligne horizontale avec memset.

La fonction ainsi ecrire n'est pas plus courte, elle fonctionne cependant plus rapidement. En effet, memset est optimisée pour aller le plus vite possible. Elle est ecrite en assembleur, et en plus elle remplit la RAM vidéo par bloc de 16 bits, soit 2 pixels à la fois (pour les petits veinards qui utilise linux, la routine travaille même en 32 bits). En utilisant du C pur, il n'est donc pas possible de faire plus vite.


Passons maintenant à la ligne verticale. Dans ce cas, les octets ne sont plus contigüe en mémoire. La fonction memset n'est donc plus utilisable. Mais on peut quand même ameliorer. Pour chaque pixel, le calcul complet 320 * Y + X (une multiplication et une addition) est refait. Or, la position de deux pixels consecutifs ne differe que de 320. Nous ecrirons donc :

char *VideoRam = (char *) MK_FP(0xA000,0000); // pointeur sur ram vidéo
Debut = 320 * YD + X; // position du premier pixel
YF++; // augmente la fin d'une unité
for(Y = YD; X < YF; Y++, Debut += 320)
VideoRam[Debut] = Couleur;

tracé de ligne verticale

Au passage, vous pouvez remplacer la valeur d'incremenattion 320 par 319 ou 321. La routine tracera alors des lignes orientees à 45 degres. D'autres valeurs ne sont pas utilisables car les points ne seront plus jointifs. Le principal problème de cette routine est qu'elle ecrit en RAM vidéo en utilisant des char (8 bits). Elle fonctionne donc au moins deux fois moins vite que la ligne horizontale. Il n'est hélas pas possible de faire mieux. Elle fonctionne toutefois plus vite que la methode générale car elle n'emploie que des valeurs entières.

3) tracé de rectangle.

De meme qu'une ligne est une succession de pixels, un rectangle est un succession de lignes, horizontales ou verticales. Les lignes horizontales pouvant être tracée plus rapidement que les lignes verticales, les rectangles seront tracé horizontalement :

unsigned int Debut = (Y<<8) + (Y << 6) + Xd;
for (Y = Yd; Y < Yf; Y++, Debut += 320)
memset(VideoRam+Debut, (Xf-Xd) + 1, Couleur);

Comme vous pouvez le remarquer, je n'utilise pas la fonction de tracé de ligne hprizontale précédente. En effet, un appel de fonction coute cher en temps d'éxécution. Comme la fonction HLine est très simple, il est plus rapide et moins complexe d'integrer le code de HLine dans la fonction Rectangle. En plus certains calculs effectués dans HLine, on déjà été faits dans Rectangle. En procédant ainsi, cela évite de les refaire.

III] Sélection des couleurs

Dans les exemples précédent, vous avez certains remarqué l'intervention frequence d'un paramêtre unsigned char Couleur que je n'ai pas expliqué. Si vous regarder la documentation de votre carte graphique, vous decouvrirez qu'elle dispose de 260000 couleurs au moins (exactement 262144 pour une carte VGA standard). Toutes ces couleurs sont disponibles en mode 0x13. Comment un nombre compris en 0 et 255 peut il designer une couleur parmis 262000. En fait le mode 0x13 ne peut afficher que 256 couleurs simultanément mais choisies parmis les 262000. Les couleurs choisies sont rangees dans un registre tableau de la carte VGA nommé palette et contenant 256 entrée. Le paramêtre Couleur précédent ne represente pas directement une couleur mais une entrée de la palette. Cela permet plusieurs effets intéressants que nous verront plus tard, mais pour le moment, nous devont trouver comment choisir les couleurs de la palette.

1) Accés à la palette

La palette est organisée en 256 registres de 3 octets chacun dont seuls les 6 bits de poids faibles sont significatifs, ce qui fait un total de 18 bits. 218, cela correspond bien aux 262144 couleurs possibles sur une carte VGA. Dans le registre, chaque octet représente une intensité d'une composante rouge,vert ou bleu de la couleur. Ainsi le noir est code par 00 00 00 et le blanc par 63 63 63 (ou 0x5F 0x5F 0x5F). Voici dans le tableau suivant quelques exemples de couleurs.

noir

0x00 0x00 0x00

rouge

0x5F 0x00 0x00

vert

0x00 0x5F 0x00

bleu

0x00 0x00 0x5F

jaune

0x00 0x5F 0x5F

violet

0x5F 0x00 0x5F

gris moyen

0x30 0x30 0x30

blanc

0x5F 0x5F 0x5F

La palette est située directement sur la carte graphique, on doit y accéder uniquement par les ports d'entree/sortie de la carte. Les 4 ports que nous allons utiliser sont :

Voyons maintenant un exemple en écriture, puis en lecture:

void SetPalette(char index, char rouge, char vert, char bleu) {
_outp(0x03C6, 0xFF); // met le registre de masque a 0xFF.
_outp(0x03C8, index); //selectionne le registre de palette a modifier.
_outp(0x03C9, rouge);
_outp(0x03C9, vert);
_outp(0x03C9, bleu);
}

Attribution d'une couleur à un registre de palette

PaletteStruct GetPalette(char index) {

PaletteStruct Couleur;

_outp(0x03C6, 0xFF);
_outp(0x03C7, index);
inp(0x03C9);
inp(0x03C9);
inp(0x03C9);
_outp(0x03C6, 0xFF);
_outp(0x03C7, index);
Couleur->rouge = inp(0x03C9);
Couleur->vert = inp(0x03C9);
Couleur->bleu = inp(0x03C9);
}

Lecture de la couleur d'un registre de palette

Le premier listing ne presente aucun mystère. En revanche, si vous étudiez attentivement le second, vous remarquerez que je lis le registre de palette deux fois, et que seul le résultat de la deuxième lecture est renvoyé. Ce n'est pas une erreur de ma part, mais le résultat d'un bug qui affecte de nombreuse cartes VGA : en premiere lecture, la couleur renvoyée n'est pas toujours celle du bon registre. Il faut donc faire deux lectures successives, la deuxième etant toujours juste. Il est à noter que seules certaines cartes VGA présentent ce bug.

IV] Adaptation des sources à Linux

1) La librairie svgalib.

Linux est un système d'exploitation 32 bits. Avec lui, le clivage traditionnel segment/offset n'a plus cours. Les programmes doivent tenir sur un seul segment, mais comme ils peuvent faire jusqu'a 4Go, ce n'est pas du tout un problème (au contraire). Les segments éxistent toujours bien sûr, mais Linux s'en réserve le contrôle pour protéger ses données, d'où sa fiabilité (pour ceux que ça intéresse, Linux répartit la mémoire adressable entre 4 segments, deux pour le noyau, deux pour les applications).
Sous Linux, les fonctions du BIOS n'existent pas. Il faut donc accéder directement à l'électronique de la carte et manipuler les registres, ce qui n'est pas particulièrement aisé. D'autre part, Linux fonctionne en mode protégé et la mémoire vidéo n'est plus en 0xA0000 (adresse linéaire de la mémoire), mais où Linux a decidé qu'elle serait. Enfin, Linux interdit l'accés hardware aux applications.
Aux vues de ces limitations, il n'est donc pas possible de faire du graphisme sous Linux. Le dernière est facile a tourner : les programmes root ont un libre acces au hardware. Pour les autres utilisateurs, il suffit en plus de lui accorder des droits d'accés suid. Inutile de vous dire que faire fonctionner un programme root pas exactement au point peut se révéler tres dangereux. Mais c'est hélas la seule solution, d'autre part la fiabilité de Linux est telle que jusqu'a présent même avec mes pires horreurs, je n'ai jamais perdu le contrôle du système, bien qu'à deux ou trois reprises (en 2 mois), j'ai parfois du le relancer (A titre de comparaison, sous Windows 95, je pouvais relancer le systeme jusqu'à 5 fois par heure pendant la mise au point de mes programmes).
Heureusement les autres problèmes peuvent etre aussi facilement résolus. Quelqu'un l'a déjà fait pour nous. Il s'agit de la librairie svgalib. Cette librairie a tous les avantages et les inconvenients du BIOS, universalité et lenteur. Nous allons donc utiliser cette librairie comme nous utilisions le BIOS, c'est à dire uniquement les fonctions d'initialisation, auxquelles nous rajouterons nos propres primitives de dessin. Le résultat, les routines de bases fonctionnent à la même vitesse que sous DOS avec une carte VGA standard (16 bits), les versions tamponnees (qui seront vues dans le 4eme article) et les cartes VLB et PCI fonctionnant 2 fois plus vite (voire plus avec un pentium pro).
Reste le problème de la localisation de la mémoire vidéo. La encore svgalib nous sauve, elle fournit une variable qui donne cette adresse: graph_mem. Tous les exemples ci dessus fonctionneront si vous remplacez toutes les références à la memoire écran par graph_mem.

L'utilisation de la librairie svgalib est tres simple. Avant tout, vous devez verifier qu'elle est installée sur votre système. Si ce n'est pas le cas, faite le (si vous ne le savez pas, lancez un programme qui l'utilise comme zgv, doom, ou povray et regardez si il marche). Maintenant, declarez le fichier vga.h dans la liste de vos include (path: /usr/local/include/). Il faut ensuite lier le fichier libvga.a au programme (path: /usr/local/lib). Apres compilation, le programme doit être declaré comme root et avoir des droits d'accés suid pour fonctionner.

2) Initialisation de la carte

svgalib fournit quelques routines qui permettent d'initialiser le mode graphique choisi. En fait, seules 2 routines vont nous être utiles:

Pour ces deux routines, les codes des modes graphiques n'ont rien a voir avec ceux du BIOS. La librairie svgalib fournit un jeu de constante pour faciliter le travail du programmeur. Ces constantes sont de la forme GXxYxC ou X représente la résolution horizontale, Y la resolution verticale et C le nombre de couleurs. Pour le mode DOS 0x13, la constante est G320x200x256 (PS : en réalité la valeur de cette constante est 5, d'ou son utilité).

 


Maintenant que vous savez tracer des points et des lignes, vous voila armé pour tracer à peu prés n'importe quoi. Toutefois, les graphismes ne deviendront réellement intéressant que lorsque nous sauront afficher des bitmaps et des sprites, ce qui sera fait dans le prochain article.
En attendant, vous pouvez télécharger les sources d'exemples en cliquant ici pour DOS et la pour Linux.