Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : Assembleur - 3D surface pleine
(Article écrit par Jérôme Étienne et extrait d'Amiga News Tech - septembre 1991)
|
|
Le listing en fin d'article est relativement efficace dans son domaine. Je l'ai agrémenté de certaines ruses
pour accélérer le temps d'exécution, ce qui est primordial pour une démo digne de ce nom.
Il nécessite donc un nombre important de points à expliquer. Dans le désordre, nous avons : le détourage
de polygones (derivé du détourage de droites déjà expliqué), la technique des faces cachées en elle-même
(encore des formules mathématiques, mais comment faire autrement en 3D ?), la méthode utilisée pour remplir
les polygones visibles et enfin la structure de l'objet en mémoire, afin que vous puissiez faire bouger
autre chose qu'un simple cube.
La technique des faces cachées
Celle que j'utilise, comme disait Coluche, a des avantages et des inconvénients. Elle permet de déterminer si une
face est orientée ou non vers l'observateur. Pour ce faire, on oriente chacune des faces dans un sens constant
puis l'on teste si elles sont dirigées vers l'observateur. D'après les résultats, on affiche uniquement celles
qui sont bien orientées. Ceci peut s'obtenir grâce à un calcul relativement simple, en utilisant la composante
z du produit vectoriel (et c'est reparti pour un cours de maths).
Comme chacun sait, le produit vectoriel est une opération entre deux vecteurs ayant pour résultat un vecteur
normal au plan formé par ces deux vecteurs. Ainsi, si l'on effectue cette opération après avoir transformé l'objet
spatial dans le plan formé par l'écran, le vecteur résultat sera normal à l'écran si les points étaient bien orientés,
ou dirigé vers le fond s'ils ne l'étaient pas. Le signe de la partie z nous permet de connaître l'orientation du
vecteur normal. En effet, si la partie z est positive, la face est visible. Dans le cas contraire, la face est
invisible, on ne l'affiche pas et l'on passe à la suivante.
Dans notre cas, les deux vecteurs sont deux arêtes consécutives du polygone représentant la face. Pour accélérer le
temps d'exécution et simplifier la création des objets, les vecteurs sont codés sous la forme des trois sommets des
deux vecteurs (deux extrémités pour chacun, mais il y en a une commune, du fait qu'ils sont consécutifs). On peut
noter que ces trois points sont tout bonnement trois points consécutifs du polygone.
Une fois les trois paires de coordonnées (x1,y1), (x2,y2) et (x3,y3) obtenues, on calcule la partie z du produit
vectoriel, avec la formule :
|
z=(y2-y1)*(x3-x1)-(y3-y1)*(x2-x1)
|
Suivant le signe de z, le vecteur normal à la face sera dirigé soit vers le fond, soit vers l'observateur, ce
qui nous permet de choisir si l'on affiche ou pas la face en question.
Les avantages d'une telle technique sont rapidité d'exécution et simplicité de programmation. Mais elle possède
également un inconvénient majeur : l'objet doit absolument être convexe (rappel : un objet est dit convexe lorsque
toutes ses diagonales sont situées à l'intérieur de l'objet). Ceci est une restriction importante, car elle permet
de gérer uniquement des objets tels que le cube, le triangle, la sphère, etc. et en aucun cas des objets de la forme
d'un hélicoptère, ou autres formes complexes. Dans le cas d'une routine gérant aussi les formes concaves, il faudrait
calculer quelle partie de chaque face est visible, puis tracer les parties apparentes. Cette technique est efficace
pour l'affichage mais longue au niveau du calcul ; elle est donc utilisable par exemple sur les gros PC connus pour
leur rapidité de calcul et la lenteur de leur mémoire graphique, mais difficilement sur un Amiga 68000. On pourrait
également utiliser la méthode dite du "z buffer" (tampon de profondeur), qui consiste à calculer la distance qui sépare
chaque face de l'observateur puis à les trier dans l'ordre décroissant afin d'afficher une par une chaque face en
commençant par la plus éloignée et finissant par la plus proche. Elle a l'avantage de ne posséder aucune restriction
de forme, mais elle est bien plus lente à l'affichage, chaque face de l'objet étant dessinée, qu'elle soit visible ou pas.
L'affichage des polygones
Je passerai sur la description du fonctionnement du mode remplissage du Blitter ; vous pouvez la trouver dans les
livres tel que le Hardware Manual.
Grâce à ma technique de calcul très contraignante, il n'y a que deux cas à traiter : soit la face est entièrement
visible, soit elle est totalement cachée et nous n'avons pas à l'afficher. Pour faire apparaître l'objet, nous
allons donc dans un premier temps tracer toutes les arêtes de chaque polygone dans les bons plans de bits. Prenons par
exemple une face de couleur 3 : il faut tracer les arêtes sur les plans de bits 1 et 2 mais pas sur le 3. Ainsi, après
le remplissage, la face ne sera dessinée que sur les plans de bits 1 et 2 et sera bien de couleur 3.
Un autre problème se pose. Imaginons en effet le coin d'un polygone qui serait dirigé vers le bas à l'intersection
des deux arêtes : il n'y aura plus qu'un seul point sur la ligne horizontale. Le Blitter va donc commencer à remplir,
mais ne s'arrêtera pas sur le second côté, car en fait, il était confondu avec le premier, d'où bogue
hideux et crapuleux. Pour éviter ce problème, il faut dessiner les droites en mode EOR (minterms $4A) et du haut
vers le bas. Je ne vous expliquerai pas pourquoi, ayant moi-même trouvé ceci en tatonant. L'utilisaton du mode
EOR implique que si l'on dessine deux fois la même droite, nous revenons à l'état initial. Afin d'éviter une opération
inutile, j'exécute une routine qui élimine les droites tracées deux fois ; dans le source, elle est mêlée au
calcul du produit vectoriel. Son principe est que, sachant que toutes les arêtes d'une même face ont la même couleur,
à chaque nouvelle face, on met sa couleur dans le registre couleur de chaque ligne (le troisième mot dans le tableau
tab_line) composant cette face par un EOR. Ainsi une ligne qui aurait du être dessinée deux fois ne le sera pas du tout.
Après avoir convenablement tracé les lignes, il ne reste plus qu'à remplir les faces pour faire apparaître l'objet. Ceci
peut s'effectuer de différentes manières : la première, que je n'utilise pas, consiste à encadrer l'objet dans un rectangle
de la taille minimum et à le remplir avec le Blitter. Elle paraît la plus efficace car la fenêtre est la plus petite
possible, mais il n'en est rien. En effet, son temps d'exécution varie énormément en fonction de la taille de l'objet,
ce qui peut être très gênant dans une démo. De plus, on passe une grande partie du temps-machine à attendre le Blitter,
ce qui est aussi très mauvais.
J'utilise donc une autre méthode, dont le principe est de remplir tout l'écran en permanence. Cela permet d'avoir un
temps d'exécution constant et donc d'utiliser de façon optimum le jumelage Blitter/68000. Je vous avais déjà expliqué
lors du premier article sur la 3D, que pour effacer plus vite l'écran,
je me servais simultanément du 68000 et du Blitter. Ici, on utilise à nouveau cette technique, en l'améliorant toutefois
un peu. En effet, non seulement le 68000 efface l'écran en même temps que le Blitter, mais aussi pendant que celui-ci
le remplit ! Ceux qui suivent encore doivent se demander comment je fais pour effacer l'écran tout en le remplissant ?
Eh bien c'est une bonne question, et je me remercie de me l'avoir posée. En fait, ce cas ne se produit jamais car
j'utilise trois pages pour le "flipping" : une qui apparaît à l'écran, une que je remplis au Blitter et une que j'efface
au 68000 et au Blitter.
Le détourage de polygones
Résumé des épisodes précédents : la technique utilisée est la dichotomie. Le détourage de droite est le moyen de
connaître les coordonnées de la partie visible de la droite. Le détourage de polygone s'inspire fortement de ce
dernier, car en fait, il équivaut à un détourage de droite sur chacune des arêtes, plus un léger additif pour le
cas où le polygone dépasserait sur la droite de l'écran.
Pour être plus clair, prenons pour exemple un losange régulier dont les quatre bords sortent de chaque côté de
l'écran. Les détourages haut et bas se font avec une déconcertante facilité. Il suffit en effet de bien déterminer
le registre BLTSIZE de manière à ce que le Blitter commence son action en bas de la partie visible et la termine en
haut. Le détourage gauche est lui aussi relativement aisé, car il ne nécessite absolument rien à part le simple
détourage de droite qui est commun à chaque cas de détourage. Nous en arrivons au détourage
droit qui engendre le supplément de travail évoqué plus haut. Le problème est que si l'extrémité droite du losange
(polygone exemple) dépasse du côté droit de l'écran, les points les plus à droite seront théoriquement allumés.
De plus, on sait que le Blitter remplit de la droite vers la gauche. Donc, si nous effectuons un unique détourage
de droite, les points les plus à droite de l'écran seront vides et le Blitter sera persuadé qu'il ne doit pas remplir
cette surface, d'où, encore une fois, un horrible et méchant bogue, la surface théoriquement pleine apparaissant
en partie vide.
Pour palier à ce problème, il faut dessiner une droite verticale le long du bord droit de l'écran, allant du y de
l'extrémité droite de la droite détourée jusqu'au y prévu avant le détourage. Affinons l'exemple avec une droite
de coordonnées (300,0)-(340,40). Pour détourer convenablement cette arête, il faudra afficher non seulement la droite
simplement détourée (300,0)-(320,20) mais en plus une droite verticale (320,20)-(320.40). Grâce à cette droite supplémentaire,
le Blitter rencontrera des points allumés à l'extrémité droite de l'écran et remplira donc la surface comme prévu.
La structure des objets
La structure est composée de quatre zones de données :
coor_e regroupe les coordonnées spatiales des points les unes à la suite des autres, la première donnée
décrivant le nombre total de points composant l'objet.
coor_p sert uniquement à stocker les coordonnées planes des points après rotation et projection.
tab_line définit les lignes par groupe de trois valeurs. Deux sont en fait les numéros des points
extrémités, prémultipliés par 4 pour ne pas avoir à le faire au moment de l'accès à la table des coordonnées planes.
La troisième valeur est initialisée à 0 et sert, lors du dessin de la ligne, à savoir dans quel(s) plan(s) de bits la
tracer, afin de ne pas afficher deux fois la même ligne inutilement. La valeur nb_line doit contenir le nombre de
lignes dont l'objet est composé.
tab_face détermine les faces, leur orientation et leur couleur. Le premier mot est le nombre de faces de
l'objet. Vient ensuite la description de chaque face une par une, ainsi décomposée : trois mots (là encore prémultipliés par 4)
contenant les numéros des trois points d'orientation (qui doivent se suivre dans le sens inverse des aiguilles
d'une montre lorsque l'on se trouve devant la face), un mot contenant le nombre d'arêtes qui composent cette face,
un mot contenant la couleur puis tous les numéros (prémultipliés par 6) des lignes du polygone. Pourquoi prémultipliés
par 6 ? Simplement parce que chaque ligne est codée sur trois mots, soit six octets !
Conclusion
Je m'insurge contre la vague de conformisme qui s'empare des demomakers depuis trop longtemps. En effet, il y
en a un, en Scandinavie, qui a trouvé un effet original, et le reste de l'Europe l'use jusqu'à la corde en le
reproduisant sans vergogne. Et ce n'est encore pas le pire... Il y a aussi la vague de démos purement graphiques
qui prend une forte ampleur. Revenons aux sources mes frères ! N'oublions jamais qu'en des temps reculés,
le terme "démo" signifiait réellement "démonstration". Le but était de montrer les capacités de la machine...
Prions le Dieu 68000 ! Honorons-le avec des offrandes ne pouvant pas être programmées en BASIC
ni même en C ! Pour votre pénitence, vous me ferez chacun une démo originale, demandant un bon niveau technique !
Ainsi finit le sermon du nostalgique. Je reprends le calme qui a fait la réputation du grand prêcheur charismatique
que je suis, pour vous annoncer que la prochaine fois, nous verrons comment dépasser allégrement les limites du
matériel en mettant plus de huit sprites sur une même ligne de raster.
|
