Tutoriel sur le BSP

Comme de nombreuses personnes posent toujours les mêmes questions sur les erreurs de compilation ou sur les divers problèmes de map qui sont soit très longues à compiler ou qui ont un taux de rafraichissement très bas, je vais faire ce petit tutoriel pour expliquer comment le fichier bsp est créé et que fait VIS dans la création du fichier BSP.

Ce petit tutorial se base sur divers tutoriels qui existent et qui sont parsemé ça et la sur divers sites.

La fonction de l'utilitaire BSP

Nous allons voir les différente étapes de la création du BSP et pourquoi cela a lieu.

En effet la map que l'éditeur crée est inutilisable par le jeu, cette map doit être compilée et traitée pour plusieurs raisons.

Ceux qui ont fait des niveaux pour Jedi-Knight comprendront très vite, car l'éditeur de JK qui s'apelle JED fonctionne très différemment des éditeurs pour les jeux basés sur le moteur de Quake.

En effet JED ne compile pas la carte crée, car JED crée directement un bsp, c'est pourquoi c'est plus difficile et moins naturel que de placer des murs des planchers des toits et diverses cloisons comme avec Quark ou Worldcraft pour Half-Life.

Avec JED on cré un secteur de base avec des parois d'épaisseur nulle et ont ajoute ensuite des secteurs les un aux autres, on crée ainsi un volume fermé sans fuites ayant des parois d'épaisseur nulle, on apelle ça un hull en anglais ou coque en français.

Voici un exemple de construction avec JED directement en mode bsp:

On voit que les murs n'ont pas d'épaisseur, tout le niveau est constitués de secteurs convexes séparés par des surfaces dont les propriétés peuvent être modifiées pour les rendre visible ou invisible, traversable ou non. La carte ne nécessite pas de compilation puisqu'elle est déjà au format utilisable par le moteur du jeu. Il n'y a pas non plus de visibilité précalculée , elle est calculée pendant le jeu suivant le déplacement du joueur, ce n'est pas trop pénalisant car les cartes étaient très simples et le nombre de polygones limité .

On voit bien qu'avec cette méthode c'est assez dur de créer un niveau, ce n'est pas très intuitif de travailler avec des épaisseur nulles. La meilleure façon d'expliquer ce travail est de s'imaginer tel un mineur creusant le niveau de l'intérieur dans un grand bloc de matière. On étend le niveau de pièce en pièces en creusant toujours plus loin et en reliant les pièces les une aux autres.

L'éditeur d'Unreal fonctionne aussi de cette manière, on creuse également comme une souris dans un gruyère.

En fait tous les moteurs de jeu utilisent le même principe, ils ont besoin d'une coque sans fuite dans laquelle le joueur pourra se déplacer.

Les éditeurs pour HL tel Quark utilisent une façon plus naturelle de construction, on place des murs et des volumes dans le vide pour créer un niveau fermé.

Ce n'est que lors de la compilation que la coque sera créée, on comprend donc pourquoi la map doit être bien fermée, s'il y a des fuites, le compilateur ne pourra pas créer un coque fermée nécessitée par le moteur du jeu.

Le processus de création du BSP va définir les contours extérieurs de la coque, éliminer les épaisseurs des murs extérieurs et diviser tout le niveau en secteurs (bsp nodes) convexes.

Un secteur convexe est un volume dans lequel n'importe quel point de ce volume peut voir tous les autre points du même volume. Une sphère est un volume convexe, un cube ou un tétrahèdre également. Mais si on prend un cube et qu'on lui fait une bosse en le frappant de l'extérieur, il ne sera plus convexe, car aux alentours de la bosse il y aura des endroits qui ne pourront pas voir ce qu'il y a de l'autre côté de la bosse.

Exemple de secteur concave (tiré du tutoriel sur Jedi_knight) :

On voit bien que le secteur "enfoncé" ne correspond pas à la définition d'un secteur convexe, certains endroits ne sont pas visibles de partout.

Prenons un exemple concret:

On va faire une map très simple , une pièce rectangulaire avec un cube et un tétrahèdre , ci dessous la map et la vue 3d de cette carte.

J'ai enlevé le ciel pour mieux voir, BSP va donc éliminer les épaisseurs des murs extérieurs et découper la carte .

Le BSP va donc découper le niveau en secteurs (bsp nodes) convexes en respectant des règles établies afin de créer aussi peu de secteurs que possible. Si aucunes règles n'étaient bien définies il y aurait le risque de se retrouver avec des découpes inutiles, tout l'art de créer un utilitaire BSP est donc de trouver une manière optimale de découper la map. Si on le faisait à la main comme avec JED on pourrait voir le résultat et utiliser notre supposée intelligence pour l'optimiser. Avec l'utilitaire BSP on en est réduit à trouver une méthode d'optimisation automatique qui n'est pas parfaite et qui peut parfois entraîner des résultats insatisfaisants.

On obtient alors le résultat suivant pour notre exemple:

On voit bien les secteurs définis et les murs extérieurs éliminés et les deux polyèdres solides en orange

Pendant la création du BSP, les polyèdres sont pris un a un et placés dans un arbre bsp, le bsp a une structure d'arbre avec des ramifications représentant les découpes succéssives. Le volume sera découpé en morceaux de plus en plus petits jusqu'à obtenir des secteurs convexes.

On se rend donc compte que l'ordre dans lequel les polyèdres seront placés modifiera la structure du bsp, c'est à ce moment qu'il faut trouver une méthode pour l'ordre de placement des polyèdres dans l'arbre bsp.

En fait BSP utilise des priorités en prenant tout d'abord les polyèdres ayant des axes communs, ceux qui ont des faces coplanaires par exemple puis il prendra les polyèdres qui vont créer le moins possible de découpes, c'est un calcul qui est réalisé et la meilleure solution est retenue.

A la fin on se retrouvera avec un niveau entièrement découpé en secteurs convexes (bsp nodes) et optimisé .

Il y a des astuces pour créer un bsp optimal, sachant comment BSP fonctionne, on peut choisir sa géométrie de construction en favorisant l'alignement des murs et en créant une géométrie la plus pure possible, il faudra bien utiliser la symétrie chaque fois que c'est possible.

Il y a une autre astuce importante, il faut éviter les découpes inutiles au maximum, par exemple, pour une colonne au milieu d'une pièce. Si on fait en sorte que le pied de la colonne touche le sol, le sol sera découpé au point de contact en plusieurs parties, si on laisse un espace très petit et donc invisible à l'oeil nu, le sol ne sera pas découpé. Il faudra donc ne pas oublier de ne pas coller inutilement des objets contre les murs ou sur le sol, il est préférable de laisser un petit espace pour éviter un maximum de découpes.

Placer un tableau sur un mur c'est très joli, mais ça va le découper en quatre parties!, si on laisse quelques milimètres de jeu, pas de découpe.

Mais il intervient encore une autre limitation lors du découpage de la map en bsp nodes, la dimension maximale pour un polygone est de 256, ce qui fait que les surfaces plus grande seront découpées, il est donc inutile de privilégier les très grandes surfaces , car elles seront de toute manière découpées en élément de 256 max de côté.

Nous allons voir maintenant la fonction de VIS

VIS et ses vicissitudes: