Bonjour à tous,

Alors cette question ne s'adresse pas aux utilisateurs de moteurs de jeu (unreal, id tech, etc) mais à ceux qui ont déjà programmé des encodeurs de bsp-tree pour des usages personnels différents de ce qu'en font ces moteurs.

(ce que j'essaye de faire c'est générer automatiquement un graph de cellules convexes à partir d'un enchevêtrement de solides convex plus grossiers, bon je sais qu'il y'a d'autres solutions je pourrais stocker ces objets dans un octree par exemple et les faire se clipper entre eux, mais le bsp étant la technique la plus générique qui permet de tout régler avec une structure unique, j'essaye celle là d'abord)

Pour l'instant je prototype ça sur les scripts de logiciels 3d (3dsmax, blender) histoire de pouvoir visualiser en temps réel ce que ça donne.

Donc je fais pas un bête bsp pour stocker des faces, mais je stock des volumes, donc c'est construit à partir de solides convexes ("brushes") et bien évidemment je me cogne sur tous les fameux bugs provoqués par cette structure: "leaks", "holes", "distortions", etc... bugs dùs à la nature approximative des vecteurs 3d et qui se produisent quand les découpes deviennent trop fines, génèrent des polygones incohérents, ou rejettent les points du mauvais côté d'un plan.

Donc je cherche comment corriger, colmater ou minimiser ces bugs en m'inspirant des moteurs de jeux existants,

Dans unreal le bsp est régénéré au fur et à mesure que le modélisateur ajoute/vire/déplace les brushes, l'éditeur de level laisse tout bêtement le bsp planter, on laisse le modélisateur déplacer les brushes pour virer les bugs, bon enfin les unreal modeleurs connaissent la séance de torture.

Alors là je jette un oeil aux sources de Quake pour voir comment ils ont fait:

https://github.com/id-Software/GtkRadiant/blob/master/tools/quake2/q2map/brushbsp.c

Je repère pour l'instant deux techniques

- avant toute découpe les plans des polygones sont stockés dans un tableau, comme ça même si le polygone est déformé par une découpe trop fine, le plan lui reste intact, ce qui va éviter les grosses distortions

- lorsque les points d'un brush sont testés contre un plan y'a une marge epsilon de 0.1 qui va arbitrairement rejeter les points trop proches du plan histoire de pas provoquer d'ambiguité

	if (d_front < 0.1) // PLANESIDE_EPSILON)
	{	// only on back
		*back = CopyBrush (brush);
		return;
	}
	if (d_back > -0.1) // PLANESIDE_EPSILON)
	{	// only on front
		*front = CopyBrush (brush);
		return;
	}

Technique bourrin qui a tendance à générer un tas de "flat leaves" et carmack a fait tout un algo pour corriger ça (et qui à la compilation prend plus de temps que la construction du bsp-tree...).

Bon voilà, je sais pas si ça va suffire ou s'il faut d'autres rustines pour colmater toutes les brèches de cette structure casse-gueule.

Mais plus j'étudie les bsp-tree plus je constate que c'est vraiment une structure dégueulasse et je capte pourquoi les moteurs de jeu s'en servent de moins en moins.

[EDIT]

Bon en fait je crois que je vais écouter la voix de la sagesse et laisser tomber ce vieil algo plein de bugs.

Y'a un ingénieur d'epic qui m'a dit que le bsp c'était utile pour générer un cellgraph très fin à l'époque où il fallait optimiser face par face mais aujourd'hui on utilise des cellgraph plus grossiers pour faire un culling objet par objet. (depuis unreal 4 ils utilisent un cellgraph en gros cubes pour le culling, le bsp sert juste comme outil de modeling)

Donc je peux bêtement modéliser les cellules manuellement et les ranger dans un octree, ça revient au cellgraph de quake avec les portails, mais adapté aux gros objets de la 3d moderne et sans tous les bugs du bsp.

-
Edité par AdemarPatamob 9 janvier 2018 à 14:26:19

C'est aussi que les BSP se pretent tres bien a certains types de geometrie (i.e. interieur de batiments assez "cubiques", c-a-d avec bcp de parois qui suivent des alignements determines, et des plans de coupes propres). Or ajd la tendance est aux open-worlds et aux environnement complexes qui melangent interieurs et exterieux ; la structure est peu adaptee a ces utilisations.

En fait ce dont ont besoin les "intérieurs" c'est d'un graph de cellules.

Dans le quake engine le bsp permettait de le générer automatiquement à partir de solides de collision simples.

Mais à l'ère du high-poly cette technique n'a plus aucun intérêt.

Ils l'avaient réutilisé en open-world dans idtech 5 (rage), les architectures étaient toujours gérées par des bsp-trees, mais ça a pas eu beaucoup de succès car le low-polygon c'est has been.

-
Edité par AdemarPatamob 13 janvier 2018 à 23:06:29