Faire un renderer 3D basique en software

note : HAPI est une API qu'on est obligés d'utiliser en Game Software Development. En gros ca permet juste de créer une fenêtre, et manipuler le buffer de celle-ci. Aucune autre librairie externe n'est autorisée (à part STL quand même). Son but est de nous apprendre les bases des graphismes 2D, comme le blitting, le background scrolling, les sprites, les animations ...

Etant pas mal en avance sur la plupart de mes modules en ce moment, et après une discussion avec un camarade de classe sur "faire un jeu en mode 7 avec HAPI" ... l'envie m'est pris de faire coder un renderer 3D avec.
"Ca peut sembler dingue" pensais-je, mais pour obtenir quelque chose de basique, il ne faut pas grand chose!

Les pré-requis
Ils sont surtout mathématiques, et pas si dur que ça, on peut trouver et comprendre tout ça très rapidement sur wikipedia :

1) Les vecteurs :

• Addition
• Soustraction
• Produit vectoriel
• Produit scalaire

2) Les matrices :

• Identité
• Produit matriciel

3) La combo des deux : le produit vecteur fois matrice.

4) Une expérience avec DirectX ou OpenGL ne fait vraiment pas de mal!

Les points à dessiner
C'est pas tout ca, mais il faut bien quelque chose à afficher!
Pour tester mon programme, j'ai commencé par créer un cube avec ces coordonnées :

p1( 1, 1, 1)
p2( 1,-1, 1)
p3(-1,-1, 1)
p4(-1, 1, 1)
p5( 1, 1,-1)
p6( 1,-1,-1)
p7(-1,-1,-1)
p8(-1, 1,-1)

L'étape suivante, c'est de transformer ces points pour obtenir leur position à l'écran.

Les matrices de transformation
Mais avant ça, il faut obtenir des matrices de transformation, qu'on va combiner entre elles pour obtenir une matrice de transformation finale, laquelle va être appliquée à nos points (d'où la multiplication de vecteur par matrice).

Vous pouvez trouver comment les produire avec la documentation OpenGL (que j'ai évidemment utilisée!).
Un autre lien intéressant, qui explique le principe de ces matrices, sur le site du zéro.

Il n'y a pas besoin de plus que ces matrices là, vraiment :

• Translation
• Rotation autour d'un axe (X, Y, Z ou même quelconque)
• Perspective
• LookAt (pour la caméra)
• ViewPort (pour adapter à la taille de l'écran)
  

Catégorisation des matrices
Pour obtenir la matrice de transformation finale, il est bon de savoir quelle matrice de transformation utiliser, à quel moment et dans quel ordre. C'est là qu'on voit trois catégories apparaître :

• La matrice de projection
• La matrice de la caméra
• La matrice "du monde"
  

Pour la première, c'est généralement celle où on applique la matrice de perspective. C'est pas obligé en temps normal, mais pour avoir de la 3D c'est indispensable (or c'est le but ici!). Dans notre cas, pas comme dans DirectX ou OpenGL, il faut aussi prendre en compte la taille de l'écran. Donc on la combine aussi avec une matrice view port. Ce qui donne (précisément dans cet ordre) :

Projection = ViewPort * Perspective

Pour la caméra, un bon vieux LookAt reste toujours très efficace. Mais rien n'empêche de la bouger à coup de translate et/ou rotate. Si on choisit de fait comme ca, il faut garder à l'esprit que la position de départ de la caméra correspondrais à ce LookAt :

LookAt( 0,0,0, 0,0,-1, 0,-1,0)

Pour la matrice du monde, c'est celle qui est utilisée pour transformer les objets qu'on veut afficher. Donc essentiellement du rotate et du translate. C'est aussi là que push et pop sont utiles pour les transformations locales.

Projection des points
Enfin, lorsqu'on veut afficher un objet, il faut commencer par projeter tout ses points sur l'écran. Et là, rien de plus simple, à part qu'il ne faut pas négliger l'ordre de multiplication des matrices :

pointProjeté = point * projection * caméra * monde
// ou pour être encore plus précis :
//(j'insiste sur l'ordre!)
pointProjeté = point * ViewPort * Perspective * LookAt * matriceMondeCourante

Dans le cas du cube, on applique ceci pour p1 jusqu'à p8. Dans des points à part c'est mieux, histoire de ne pas avoir à redéfinir la position de base à chaque frame (question d'optimisation).

Dessin du triangle
Vous avez suivi? Si vous voulez expérimenter comme moi, le mieux serait d'abord d'afficher uniquement des points pour voir si la projection fonctionne.
En tout cas, maintenant on prend ces points projetés trois par trois, et on affiche un triangle à partir de ceci!
Si vous voulez un algorithme, réfléchissez-y vous même ou bien cherchez sur Google avec le mot clef "rasterize". Personnellement j'ai cherché de cette façon mais je n'ai pas trouvé quelque chose d'acceptable. Alors je me suis posé devant une feuille de papier et j'ai créé un algorithme. Ce n'est pas si compliqué, mais pas forcément le plus optimisé (j'utilise uniquement des nombres flottants, mais vu la puissance des processeurs actuels et le but de ce renderer c'est pas si grave je pense).

Le depth buffer
Le depth buffer est un tableau à deux dimensions de la même taille que l'écran. Chaque position correspond à une profondeur pour chaque pixel. A chaque fois qu'on ajoute un pixel, on vérifie si sa profondeur est plus ou moins grande que celle du depth buffer à cette position. Si la nouvelle profondeur est "plus profonde" alors on ne l'affiche pas, sinon ... ben on l'affiche.
Cette technique permet de régler le problème d'ordre d'affichage des triangles. En l'utilisant, on se fout de l'ordre et même deux triangles peuvent être en intersection. C'est aussi très facile à implémenter. N'oubliez pas d'interpoler la valeur z également lors du dessin du triangle!

Optimisation
On a maintenant assez pour afficher quelque chose de correct à l'écran! Mais on peut aussi ajouter un "backface culling", c'est à dire ne pas prendre en compte les triangles qui ne sont pas "tournés vers" la caméra. C'est utile pour l'affichage de formes fermées (comme le cube), mais ca implique de devoir spécifier les points du triangle dans le sens inverse des aiguilles d'une montre.
Implémenter un backface culling n'est pas dur non plus :
1) on récupère la normale du triangle avec ses points projetés
2) on vérifie si la valeur z est négative (ou positive, je sais plus...)
3) si oui, on l'affiche
Ce qui donne :

avec p1,p2 et p3 les points PROJETES du triangle :

// c'est à cause de ce cacul
// que le sens dans lequel
// les points sont spécifiés est important
normale = produitVectoriel( p2 - p1, p3 - p1 )
si (normale.z < 0)
{
dessinerTriangle(p1,p2,p3)
}

Et plus encore!
Prendre en compte des lumières! Dans mon cas, je me suis limité à une seule lumière directionelle. Une lumière ne fait que modifier la couleur d'une surface (d'un triangle quoi). Pour la lumière directionnelle, on multiplie la couleur qu'on veut attribuer au triangle par un produit scalaire entre les vecteur unitaires de la normale du triangle et de la direction de la lumière. En résumé :

n = vecteurUnitaire(normale)
d = vecteurUnitaire(directionLumière)
// j'appelle cette variable dot
// parce que produit scalaire
// en anglais donne dot product
dot = produitScalaire(n,d);
si (dot > 0)
{
couleurFinale = couleur * dot;
}
sinon
{
couleurFinale = noir;
}

Obtenir les vecteurs unitaires est très important.


Le mot de la fin
Voilà! Tout est dit! Je trouve ce sujet tellement passionnant que j'en suis même arrivé à en faire un tutoriel...
Je ne sais pas s'il est très clair, alors commentez-moi tout ca si vous voulez qu'il s'améliore! (le tutoriel hein)

Si j'en ai éventuellement le courage, je rajouterais peut-être quelques probables images pour illustrer le tutoriel. (en gros comptez pas dessus)
Ce qui est certain par contre, c'est qu'il y aura des images du jeu que je fais avec ce petit moteur! Et p't'êt' même que je mettrais les sources! Mais pour ces dernières, ce ne sera pas avant Janvier, car à Teesside ils sanctionnent violemment le plagiat, et moua je veut une bonne note. Rassurez vous tout de suite! Il ne m'ont jamais demandé de faire un moteur 3D, c'est juste mon esprit tordu qui m'a poussé à le faire, donc si vous envisagez de faire vos études là bas, que cela ne vous freine pas :P (et foncez même, elle est géniale cette école)