|
Description du fonctionnement du moteur 3d des donuts by Marcheu |
Le moteur 3d des donuts utilise OpenGL. Il est écrit en C, travaille au niveau des objets 3d et est encapsulé pour permettre une réutilisation facile du code. L'objectif principal est la performance. Et bien sûr, tout ça est GPL. Et bien sûr, tout ça tourne sous linux (en deux versions : une version SDL et une version X11).
Le moteur 3d permet de manipuler deux types d'objets : les objets statiques et les objets dynamiques. Ces deux types d'objets sont manipulés différemment.
 |
Il n'y a qu'un seul objet statique. Cet objet est en général le décor du niveau. Pour cet objet statique on construit un octree. Pour ce faire, on prend l'ensemble des triangles qu'on englobe dans un grand cube (une boite englobante mais cubique). Ensuite, on sépare ce cube en 8 petits cubes ce qui sépare l'ensemble des triangles en 8 sous-ensembles. On continue récursivement jusqu'à ce que le nombre de triangles dans un cube soit en dessous d'un certain seuil ou qu'on ait atteint un certain niveau de récursion. Pour choisir dans lequel des 8 noeuds fils on va mettre un triangle, on regarde simplement dans lequel de ces fils se trouve le centre de gravité de ce triangle. Ce n'est qu'une heuristique, mais cela semble marcher assez bien (et se programme facilement). |
|
Pendant la construction de l'octree les triangles qui se trouvent à cheval sur deux noeuds ne sont ni dupliqués ni découpés, car cela créerait beaucoup trop de nouveaux triangles. Mais si un triangle dans ce cas a une portion trop importante hors du cube auquel il appartient, il peut arriver qu'il ne soit pas dessiné alors qu'il est visible car le cube auquel il appartient n'est plus visible. Nous verrons plus tard comment ce problème a été résolu. |
 |
Les objets dynamiques sont en général les véhicules, les parties mobiles du décor etc... Ils sont manipulés différemment. On ne calcule pas d'octree pour eux (ces objets sont plus petits et contiennent nettement moins de triangles que les objets statiques), mais juste une sphère englobante.
Après avoir calculé l'octree, on peut l'utiliser pour la suppression des faces cachées.
La première étape est le frusum culling c'est-à-dire la suppression des faces qui sont hors de la pyramide de vision. Cette étape est accomplie assez facilement avec l'utilisation de l'octree : on se base sur le fait que si un noeud n'est pas visible, aucun de ses fils ne sera visible. De même, si un noeud est totalement visible, on ne teste plus la visibilité des fils car ils sont tous entièrement visibles. Par contre, si un noeud est partiellement visible, on doit continuer récursivement le parcours de l'octree. Pour savoir si un noeud est visible ou non, on utilise les sphères englobantes. Comme les noeuds sont tous cubiques il n'y a pas trop de pertes et le test de visibilité d'une sphère coûete 6 fois moins cher que celui d'un cube. On pré-calcule le centre et le rayon de ces sphères englobantes lors de la construction de l'octree pour les ensembles de triangles intermédiaires, ainsi si un noeud ne contient des triangles que dans sa moitié inférieure par exemple, il ne sera affiché que si cette moitié inférieure est visible. Cela permet de résoudre le problème des triangles qui n'étaient pas affichés alors qu'ils étaient visibles puisque les sphères englobantes renvoyées peuvent être plus grandes que celles qui englobent parfaitement un cube. Ceci permet d'éliminer totalement le problème précédent. Pour afficher d'un coup l'ensemble des triangles qui appartiennent à un noeud on se sert des listes d'affichage OpenGL qui permette d'accélérer l'affichage et de simplifier la programmation.
Un programme auxiliaire permet de pré-calculer certaines infos de visibilités des noeuds pour accélérer l'exécution. Ainsi, si un noeud se trouve dans la pyramide de vision mais qu'il n'est pas visible (il est caché par d'autres polygones) il ne sera pas affiché. Malheureusement cela n'est pas parfait : l'approche choisie est discrète c'est-à-dire que le pré-calcul des noeuds visibles est fait pour un certain nombre de points de vue et il reste encore une certaine portion de noeuds qui sont affichés alors qu'ils sont cachés par d'autres polygones. On peut choisir lors de la compilation du moteur si on veut utiliser ou non cette technique. Pour effectuer le précalcul, on associe une couleur unique à chaque ensemble de polygones puis on affiche la scène pour tous les points de vue possibles (pour tous les noeuds) et on regarde quels noeuds sont visibles en regardant quelles couleurs sont présentes dans le buffer d'affichage.
On a vu dans le paragraphe précédent qu'on n'arrivait pas à supprimer tous les noeuds cachés avec un pré-calcul. Pour améliorer la situation (non, on n'arrivera toujours pas avec cette technique à supprimer 100% des noeuds invisibles), on peut utiliser le principe des occluders : un occluder est un ensemble de un ou plusieurs triangles qui est susceptible de masquer un ou plusieurs noeuds (une ou plusieurs sphères englobantes).
On se sert de la sphère englobante des objets dynamiques pour supprimer ceux-ci du champ de vision. On peut aussi masquer les objets dynamiques avec les occluders.
Le moteur est encapsulé dans un classe (pour l'instant assez simple) qui permet de travailler directement au niveau des objets 3d. Voici sa définition :
// la définition de l'interface du moteur 3d
typedef struct moteur3d
{
moteur3d(); // constructeur
~moteur3d(); // destructeur
id_objet charge_dynamique (char *); // charge un objet dynamique
void supprime_dynamique (id_objet); // supprime un objet dynamique
bool charge_statique (char *,GLuint*); // charge l'objet statique
void supprime_statique (); // supprime un objet statique
void affiche (float,float,float,float,float); // affiche la scène
dword nb_objets_dynamiques; // le nombre d'objets dynamiques
objet_dynamique *liste_objets_dynamiques; // la liste des objets dynamiques
objet_statique obj_statique; // l'objet statique
GLuint texture_ciel; // le numéro de la texture OpenGL du ciel
GLuint* texture; // la liste des textures
}
moteur3d;
Pour les objets dynamiques comme pour chaque noeud de l'octree on calcule plusieurs (3-4) niveaux de détail du modèle et on en choisit un lors de l'affichage, en fonction de la distance et de la vitesse d'affichage du moteur pour les images précédentes (si un objets est distant, on peut choisir un modèle à basse résolution pour le représenter, et si le moteur 3d est trop lent, on peut décider de baisser le niveau de détail de la géométrie pour redresser la situation).
Pour accélérer l'affichage OpenGL on trie les triangles par texture puis on transforme les ensembles de triangles en triangles strips ce qui permet d'accélérer l'affichage sous OpenGL (cela correspond aux vertex buffer de DirectX). Il suffit ensuite de stocker ces listes de triangles dans des listes d'affichage OpenGL. Cette étape est un précalcul.
Lors du parcours des l'octree on effectue beaucoup de calculs de visibilité qui peuvent être parallélisés en utilisant les registres MMX des processeurs intel ou compatibles intel.
Pour accélérer l'affichage OpenGL on trie les triangles par texture puis on transforme les ensembles de triangles en triangles strips ce qui permet d'accélérer l'affichage sous OpenGL (cela correspond aux vertex buffer de DirectX). Cette étape est un pré-calcul.
Lors du parcours des l'octree on effectue beaucoup de calculs de visibilité qui peuvent être parallélisés en utilisant les registres MMX des processeurs intel ou compatibles intel.
Il peut arriver aue lesw logiciels de modelisation 3d dupliquent les points des objets qu'on veut ensuite importer, ou même créent deux points très proches mais non confondus alors au'il s'agit du même point. Pour remédier à ce probleme on fusionne les points qui sont dans ce cas.