Le fonctionnement du BSP et du VIS

Écrit le 28/11/2003 par 00940
Dernière mise à jour : 01/02/2006

Introduction

Ce tutorial est écrit pour Quake I et II et dans une certaine mesure pour Quake 3. Cependant, tous les jeux basés sur le moteur de Quake fonctionnent sur un même principe (même si tous n'ont pas de hintbrushs ou de détails brushs).

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifCe symbole représente un important avertissement.

http://www.game-lab.com/images/tuts/bsp_vis/q3.gifCes sections s'appliquent à Quake 3 Arena.

http://www.game-lab.com/images/tuts/bsp_vis/q3.gifDans Quake 3 Arena, q3map s'occupe de toutes les fonctions que traitent q3bsp, qvis3 et qrad3 pour Quake II.

La Map

Les exemples de ce tutorial utiliseront la map suivante qui consiste en 4 murs et 2 objets places au milieu :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_quake2view.jpg

Nous utiliseront l'aperçu suivant pour le tuto :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_base.gif

Cette map est seulement en 2D. Les lignes dans cette carte correspondent donc à des polygones dans la map en 3D. Les polygones dans cette vue 2D correspondront eux à des brushs dans la map 3D.

Le fonctionnement du BSP

Il y a 12 polygones externes sur les faces extérieures de cette map, simplifions donc un peu les choses en les supprimant (ce qui se produit de toute façon pendant le BSP s'il n'y a pas de leaks) :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_start.gif

La zone grise autour du bord représente la partie du monde dont nous ne nous soucions pas puisqu'elle est hors de la surface du jeu. Il y aura quelques découpages par les BSP dus à ces 12 faces éliminées mais rien qui puisse affecter l'intérieur de la map. Le blanc est là où le joueur peut bouger. La pierre représente les solides.

Pendant le BSP, qbsp3 prend chaque polygone un à un et les insère dans l'arborescence du bsp. Le terme arborescence décrit la structure du stockage des bsp (si la structure des données est dessinée sur un bout de papier, cela ressemble à un arbre ou à un buisson). Comme chaque polygone est inséré, cela va diviser l'espace en régions de plus en plus petite, mais toujours dans la région précédente. Le processus est montré graphiquement ci-dessous ( si l'image ne s'anime pas, actualise la page et n'arrête pas son chargement, ou alors ouvre l'image dans un nouvelle fenêtre):

http://www.game-lab.com/images/tuts/bsp_vis/bsp_process.gif

Comme vous pouvez voir, l'ordre d'insertion des brushs a un effet sur comment la map est subdivisée. Ajouter, supprimer ou changer un simple brush peut entraîner le qbsp3 dans des directions très différentes et provoquer des changements significatifs de performances (que ce soit en pire ou en mieux).

En réalité, qbsp3 utilise un certain nombre de règles pour choisir l'ordre d'insertion des polygones. Tout d'abord, il assigne une grande priorité au polygones axiaux. Ce sont les polygones dont les valeurs en X sont toutes les mêmes, ou les valeurs en Y ou encore les valeurs en Z(dans l'éditeur, dans 2 des 3 vues 2D possibles, le polygone sera une simple ligne). Après, il cherchera les polygones qui découpent le moins les polygones non encore insérés. L'animation du BSP avec le bord gris foncé est la plus représentative de ce que qbsp3 fait vraiment. Cependant, pour ce tuto, je n'utiliserai que celui avec le bord gris pour la clarté du propos.

Tant les grosses lignes bleues que les fines noires sont sur ce que l'on appelle des plans de découpage du bsp. Ils découpent la map en de petites (pas toujours si petites) régions. Chacune de ces régions est un bsp node. Vous ne trouverez jamais un polygone du monde au milieu d'un bsp node. Ils sont tous sur le bord ou l'angle d'un bsp node. Les objets mobiles ne font pas partie de l'arborescence du bsp et sont traités séparément.

Les grosses bleues sont vos polygones "solides". Vous ne pouvez passer à travers. Ils sont presque toujours visibles. S'ils ne sont pas visibles pour quelque raison que ce soit, vous aurez sans doute ce que l'on appelle un effet de palais des glaces ( Hall Of Mirrors - HOM ou vous verrez d'autres parties de votre niveau à travers.

Les fines lignes noires sont les "portals". Les portals séparent les bsp nodes la-à où il n'y a pas de polygones de solides. Ils ne sont pas visibles, mais les polygones générés par des brushs foireux ou des brushs non solides peuvent les chevaucher. Ils ne bloquent pas le mouvement. Il y en a en fait chaque fois 2 pour séparer 2 bsp nodes (là où il n'y a pas de polygones de solide). Chacun de ces 2 portals est attaché à son bsp node respectif .Voyez l'image ci-dessous :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_twin_portals.gif

Les flèches indiquent comment sont tournés les portals. Le node grisé est le node auquel est attaché le portal.

Quand un polygone est inséré entre plusieurs bsp nodes, il est découpé en différents morceaux tant que chaque morceau n'est pas dans un seul node. Cependant, qbsp3 essayera plus tard de fusionner les faces avec les mêmes propriétés si possible (de telle façon qu'un même polygone pourra être dans plusieurs nodes), si bien que ce processus est quasi invisible même si vous employer gl_showtris.

Le suivant est la représentation en 3D de cette map dans Quake II:

http://www.game-lab.com/images/tuts/bsp_vis/bsp_quake2view2.jpg

Les fines vitres semi-transparentes représentent les portals que vous ne voyez normalement pas.

http://www.game-lab.com/images/tuts/bsp_vis/q3.gifAlors que qbsp3 divise les polygones pour les faire rentrer dans les nodes, avant d'essayer de les fusionner de nouveau ensuite, q3map pour Quake 3 Arena laisse les polygones entiers et n'essaye pas de les fusionner après. L'effet final est en gros le même. L'arborescence du bsp elle-même est construire normalement.

Visibility Nodes

Prenons ce possible arrangement final du bsp :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_final1.gif

Comme dit plus haut, chacune des zones blanches est un bsp node. Ces bsp nodes sont aussi utilisée pour déterminer ce qui est visible. Qvis3 détermine quels nodes sont visibles depuis un node donné. Prenons les 2 point suivants, l'un étant l'observateur, l'autre le point sur le mur qu'il regarde :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_view1.gif

Comment vous pouvez le voir avec la ligne rouge, les 2 points ne sont pas visibles l'un à l'autre. Mais, avec ce bsp, qvis3 va penser que si. Pourquoi ? Parce que les nodes dans lesquels ils sont peuvent se voir. Qvis3, quand il vérifie la visibilité, vérifie chaque portal par rapport aux autres portals. S'il trouve 2 portals qui peuvent se voir, alors, il présume que les 2 nodes correspondant aussi. Dans l'image suivante, les portals vérifiés sont en jaune.

http://www.game-lab.com/images/tuts/bsp_vis/bsp_portal1.gif

Puisque ils peuvent se voir l'un l'autre (une des infinies possibilités de vision est marquées en rouge), les bsp nodes comprenant les points noirs peuvent se voir. Cela signifie que tant qu'il s'agit de qvis3, l'observateur peut voir le point sur le mur.

Voilà par ailleurs, comment le fichu "Leaf portals saw into leaf" apparaît. Quand cela arrive, cela signifie que qvis3 tente de comparer 2 portals qui appartiennent à un même visibility node. C'était un sale bug dans le qbsp3 original (oui qbsp3. Il a écrit un mauvais bsp qui cause des problèmes au vis) qui entraînait l'apparition fréquente de cette erreur. Voir cette erreur signifiait que la map avait de sérieux problèmes. Cependant, il existe maintenant un certain nombre de qbsp3 avec ce problème fixé. Dans la section fichiers (en bas de la page), il y a un lien vers mon gddqbsp3 qui a fixé le bug. Mais même avec, vous pourriez avoir l'erreur quand même. Jetez un oeil sur le suivant :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_leaferror.gif

Les portals rouges et jaunes était au départ un même portal qui a été coupe en 2. Normalement, qvis3 a une fonction qui interdit la comparaison inutile entre ces portals, mais ça peut planter. Les 2 portals devraient être sur un même plan, mais à cause des limitations des nombres en virgule flottante du pc, leurs coordonnées pourraient être très légèrement différentes. (impossible à voir à l'oeil nu bien sur). Si cela arrive, dans une configuration concave, vous aurez l'erreur. L'image suivante montre à quoi cela ressemble :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_leaferroranim.gif

Les angles ont été très exagérés. La ligne hachurée montre que le node se voit lui-même. Dans cette situation, cela n'a pas de conséquences fâcheuses. Il y a d'autres cas où vous pourrez voir cet avertissement à cause des limitations de calcul en virgule flottante. Même avec un qbsp3 fixé, ne vous inquiétez pas de cet avertissement.

Evidemment, si le portal en question est axial, cela ne devrait pas arriver.

Vérifier le travail du VIS

Donc, vous avez lance votre map ingame et vous voulez voir comment le vis a fait son boulot là où ça ralentit. Le moyen de base est de se mettre en opengl et d'introduire le paramètre gl_showtris 1. Prenons la vue suivante de base64 (compilation deathmatch de base1, base2, et base3 du solo):

http://www.game-lab.com/images/tuts/bsp_vis/notris.jpg

Et maintenant gl_showtris 1:

http://www.game-lab.com/images/tuts/bsp_vis/tris.jpg

Ceci nous montre que Quake II croit qu'un paquet de polygones sont visibles alors qu'en fait, ils ne le sont pas. Cela montre tous les polygones dans tous les nodes visibles. Au cas où vous vous demanderiez est passée l'arme, je l'ai enlevée en tapant "hand 2" dans la console.

Les triangles ne sont pas dans les bsp ; quand le rendering des polygones est fait, ils sont coupés en triangles par le moteur.

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifTant dans Quake II que dans Quake 3 Arena, il est possible d'avoir des polygones franchissant les frontières des nodes. Le gl_showtris n'est donc pas très utile pour savoir où sont vos portals.

Cartes 3Dfx

Le 3dfx minidriver ne supporte pas gl_showtris. Vous pouvez utiliser les drivers OpenGL par défaut, mais si vous utilisez l' OpenGL software (Microsoft ou SGI), cela sera très lent et passablement instable. Vous pouvez aussi employer les drivers MesaGL pour les cartes 3dfx . Un lien vers ces drivers est dans la section fichiers (en bas de la page). Une fois que vous aurez ces drivers, mettez les dans votre dossier Quake II directory (NE LES METTEZ PAS dans votre dossier system/system32). Vérifiez qu'ils sont appelés opengl32.dll. Maintenant, quand vous utiliserez les drivers par defaut, cela emploiera en fait les drivers Mesa.

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifCes données datent de début 1999; les dernières versions de MesaGL pourraient ne pas supporter gl_showtris. Par contre, les dernières versions des drivers 3dfx pourraient peut-être le faire.

Vous ne voyez toujours pas les triangles ?
Essayez alors ces commandes console :

gl_ext_multitexture 0
vid_restart

Comme cela pourrait expliquer des degradations de performances, n'oubliez pas de taper ceci dans la console après vous être servi de gl_showtris:

gl_ext_multitexture 1
vid_restart

Hint Brushes

Dans le bsp d'exemple, il n'y a que 4 paires de bsp nodes qui ne peuvent se voir (comme marqué ci-dessous):

http://www.game-lab.com/images/tuts/bsp_vis/bsp_nonvis1.gif

Il y a 21 paires de bsp nodes et seulement 4 qui ne peuvent se voir. Pas terrible. On va avoir le problème de la map base64 vue plus haut. En fait, la map base64 n'est pas catastrophique mais vous trouverez facilement des exemples où l'on voit 3, 5 fois trop de polygones. Dans le Quake d'origine, les mappeurs devaient déployer toute leur astuce pour garder le VIS en laisse. Heureusement, depuis Quake II, nous avons un outil qui permet de contrôler les découpes du bsp : la texture hint. Que fait-elle ? Elle force un découpage du bsp même si elle n'est pas elle-même visible. Une autre propriété est que qbsp3 ne choisira pas un ordre d'insertion des polygones tel qu'il en résulterait un découpage d'un polygone hint par un autre type de polygone.

La texture hint est toujours utilisée en combinaison avec la texture skip. Les polygones avec la texture skip ne sont pas insérés dans l'arborescence du bsp et donc ne sont pas utilises par Quake II. L'idée est de prendre un brush, de lui appliquer la texture skip et ensuite appliquer la texture hint sur une face. On obtient donc un simple polygone hint, ce qui est en général tout ce dont vous avez besoin. Vous pouvez vous servir de brushs entièrement recouverts de hint mais les découpages du bsp vont être plus ardus à gérer.

Quand vous placez vos hint, vous devez les mettre de telle façon que les zones qui ne doivent pas se voir ne doivent pas avoir de bords en hint qui se voient. Pour la map d'exemple, essayons la grille ci-dessous :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_myhints.gif

Dans un éditeur (ce screenshot vient de Qeradiant), cela ressemblera à quelque chose comme ça :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_quake2hint.jpg

L'agrandissement montre la zone au bout de la ligne sous un autre angle. Ces brushs ont tous 5 faces en skip et 1 en hint. Les faces skips sont complètement ignorées par la compilation, seules les faces hint sont prises en compte. Nous pourrions réduire le nombre de brushs en hint et skip à 3 en utilisant plus d'une face hint par brush, mais pour cette exemple, nous nous contenterons d'utiliser une face par brush (un avantage est qu'il est plus facile de s'y retrouver dans la vue 3D de l'éditeur).

Les 2 points employés plus haut sont toujours visibles l'un pour l'autre puisque les nouvelles nodes se voient toujours :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_portal2.gif

Cependant, il y a plus de zones cachées les unes aux autres. Aucune des zones marquées avec la même lettre ne voient celle marquée avec la même. Il y a plus de zones ne se voyant pas qu'indiqué sur le dessin, mais en mettre plus aurait rendu l'aperçu illisible. Gardez en tête que la visibilité ne sera jamais parfaite. A n'importe quel point de votre map, il y aura toujours plus de faces calculées que de faces vraiment visibles (avec quelques exceptions comme lorsque vous regardez un mur donnant sur l'extérieur, sans rien derrière).

Cela vous prendra bien quelques essais et erreurs avant de sentir que ça marche bien. Décider où placer les hintbrushs s'apparente à de l'art en quelque sorte. Un bon usage des hint brushes dans un couloir se présente comme ceci :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_hall1.gif

Vous pouvez empêcher que l'on ne voit trop loin après le coin en plaçant un hintbrush à travers le coin de cette façon :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_hall2.gif

De cette façon, vous serez sur que l'on ne peut voir les deux couloirs à la fois que depuis le coin.

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifUne chose que vous devez surveiller, c'est que les hint brushes doivent être en contact avec la map sur tous leurs bords. Autrement, si qbsp3 place une ligne de découpe entre votre hintbrushe et un worldbrush, vous risquez des résultats surprenants. Il vaut même mieux passer un peu dans le mur.

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifIl est possible que des portals sur un même plan causent des problèmes. Nous pouvons faire confiance aux hintbrushes pour que les nodes plus haut ne se voient pas réciproquement même s'ils partagent de même portails puisque les hintbrushs sont placés à angle droit, mais regardez plutôt ceci :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_nonvis2.gif

Les portals sur le plan partagent les mêmes nodes grisés mais ne sont pas parallèles. Le résultat ? : de légères erreurs de calcul dues aux limites du cpu dans les calculs à virgule flottante pourraient entraîner que les 2 nodes se voient quand même :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_unaligned.gif

Bien sur, l'angle d'erreur est très exagéré. Quand vous voulez forcer un découpage sur des plans non parallèles, un simple hint brush pourrait ne pas suffire. Il vaut mieux employer un hintbrushs de 8 à 16 unités de larges, recouvert de 2 cotés. Voyez en bas comment faire dans ce cas, avec de parfaits portals :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_double.gif

Les lignes rouges/jaunes/noires sont les hint brushes. Les 2 parties rouges sont les faces hint du bloc, les autres seront recouvertes de skip. La ligne noire au centre est l'emplacement du portal original. Cela va interdire toute erreur entre les 2 plans. Vous pouvez aussi utilisez 2 blocs . Ce truc n'est nécessaire que si vous avez 2 ou plusieurs portals sur un même plan et interagissant entre eux.

En plus, en plaçant des hintbrushs pour faire des portals, vous pouvez le faire de façon à séparer les parties de la map et ainsi, éviter des découpes inutiles. Par exemple, si la map consiste en deux parties uniquement connectées par téléporteurs, placez un immense hint brush a travers la map, entre les 2 parties. Vous empêcherez ainsi des brushs d'une partie d'interférer dans les découpages de l'autre partie.

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifEn fait, à cause du merging des faces dans Quake II ou du système de non-découpage de Quake 3 Arena, les polygones dans le périmètre jouable traversent plusieurs nodes, et si un polygone est visible dans un de ces nodes, il est totalement visible. Dans notre exemple, cela rendrait les hintbrushes presque totalement inutiles. Dans une vraie map, avec une bien plus grande densité de polygones, c'est un problème moins important.

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifIl peut sembler tentant de diviser la map en tout plein de petites zones avec les hint brushes mais si cela peut améliorer la visibilité, cela va surtout multiplier le temps nécessaire aux calculs de qvis3 et vous dépasserez peut-être la limite de 1megabytes pour les informations de visibilité. Ne vous servez des hintbrushs que si nécessaire. Souvent, la simple géométrie du niveau sera suffisante.

http://www.game-lab.com/images/tuts/bsp_vis/q3.gifhttp://www.game-lab.com/images/tuts/bsp_vis/attention.gifQuake 3 Arena a une texture skip mais elle ne marche pas. En fait, vu la façon dont q3map compile la map, cela ne représenterait rien, tout le brush doit être en hint.

http://www.game-lab.com/images/tuts/bsp_vis/q3.gifhttp://www.game-lab.com/images/tuts/bsp_vis/attention.gifIn Quake 3 Arena, les hint brushes ne bénéficient pas de priorité dans l'insertion dans l'arborescence du BSP. Cela signifie que le truc de séparer deux parties de la map ne fonctionnera pas, ils permettent seulement de créer de nouveaux portals.

Detail Brushes

Reprenons la map précédente, et ajoutons quelques petits brushs. Le bsp final ressemblera à quelque chose comme ceci :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_splits.gif

Comme vous pouvez le voir, le nombre de bsp nodes passé de 7 à 13. Le nombre de nodes va entraîner près du double de calcul et va presque quadrupler la taille des informations de visibilité. Cependant, les nouveaux brushes ne font rien ou presque pour en cacher d'autres, compliquant sans raison le bsp. Dans le Quake original, vous deviez vivre avec ça. Avec Quake II, comme pour la texture hint, nous avons désormais un outil : le detail brush (func_wall dans Half-Live). Mais au contraire du hint qui s'applique par une texture, la propriété "detail" s'applique à tout le brush.

Ce qui se passe avec les details brushes, c'est que ces polygones sont insérés en dernier dans l'arborescence du BSP. De plus, quand ils sont insérés, ils ne créent pas de portals et les bsp nodes qu'ils découpent sont traités comme un même visibility node. Faisons 3 brushes triangulaires en detail brush. Nous obtiendrons quelque chose comme ça :

http://www.game-lab.com/images/tuts/bsp_vis/bsp_detail.gif

Les lignes hachurées sont des découpages du BSP mais ne contiennent pas de portals. Qvis3 traite toute la face ombrée comme un simple visibility node. Cela simplifie beaucoup le travail de qvis3 et le rend bien plus rapide. Quand vous avez à décidez si oui ou non un brush doit être transformé en detail brush, vous devez bien vérifier que cela ne va pas entraîner l'affichage de plus de polygones. Des bons candidats sont les tuyaux, les lampes, les pc, toutes ces petites choses qui ne bloquent pas grand chose point de vue de la visibilité. Ca peut être difficile au début, mais après quelques essais et pas mal d'erreurs ça devrait venir. Servez vous de gl_showtris comme vu plus haut pour vous aider.

http://www.game-lab.com/images/tuts/bsp_vis/attention.gifVérifiez que toutes les faces de vos detail brushes sont soit detail soit structural. Si ce n'était pas le cas, vous aurez des avertissements pour mélange de propriétés. Si votre éditeur à une option pour changer un brush en detail brush, utilisez cette option plutôt que de vous servir de la fenêtre d'édition des faces.

http://www.game-lab.com/images/tuts/bsp_vis/q3.gifhttp://www.game-lab.com/images/tuts/bsp_vis/attention.gifLes detail brushes fonctionnent différemment sous Quake 3 que sous Quake II. Ils sont toujours employés dans les mêmes situations, mais les faces cachées ne sont pas enlevées par le CSG. Cela signifie que vous devez les supprimer manuellement en vous servant de la texture "caulk" et en l'appliquant sur toute face cachée qui ne doit pas être affichée.

Detail Hint Brushes

Les détails hint brushes ne font pas partie des outils de compilations de ID. Si vous les employez, vous ne pourrez pas employez les détails hint brushes. Dans mon gddqbsp3 (voyez la section fichiers ci-dessous), ils sont implémentés de telle sorte qu'ils sont des hintbrushs qui n'affectent que les détails brushes. Ils ont été intégrés au départ pour aider des générateurs de terrain à éviter des découpes entre des détails brushes mobiles. Gensurf (voyez la section fichiers ci-dessous) est capable des les utiliser (il vient de plus avec une version de qbsp3 qui intègre les détails hintbrushes).

Fichiers

gddqbsp3 et d'autres de mes outils de compilation améliorés
Gensurf par David Hyde
MesaGL

Crédits

Tutorial écrit par Geoffrey De Wan gdewan@prairienet.org

Un grand merci à tous ceux qui m'ont aidé dans la rédaction de ce tutorial:

SmallPileofGibs
bushboy (pour les images optimisées)
quelques types qui savent que je les connais
EutecTic
Johnny Law
XO (pour la version pdf)

Traduction française par 00940, publication autorisée par l'auteur.