Discussion :

[Troumf Grognon]

Bonjour, je sais que ces trois lettres font peur car Carmack nous en a un peu dégoûté en sur-compliquant l'algorithme qui devait faire d'une pierre trois coups (modélisation, occlusion, collision), erreur répercutée sur Unreal ensuite...

Donc je cherche à revenir à un usage simple de cet arbre à savoir trier les faces.

Outil destiné principalement aux utilisateurs de Unity, ThreeJs, et autres moteurs qui ne gèrent pas l'occlusion des architectures. (dans Unity, une colline est occlusive, mais pas une cloison fine). Mais même pour les unrealeurs ça peut toujours servir à guider l'IA dans les architectures (quel perso générer, pathfinding, etc).

En 3d moderne on trie des faces invisibles "portails" qu'on clippe entre elles pour trouver les feuilles que la caméra peut voir. L'algo de quake faisait des arbres tellement compliqués qu'il y'avait plus de portails que de polygones à clipper, ce pourquoi carmack a du précalculer l'occlusion ("pvs") et c'est trop compliqué donc.

J'ai fait mes premiers prototypes sur MaxScript mais je me tâte pour passer sur Blender, j'attends vos avis.

Alors, avant de taper du code il faut surtout pas zapper la phase de conception pour ce genre d'outil donc pour le moment on réfléchit aux algos.

Voilà un schéma qui explique les étapes:



[EDIT 1] Je corrige des erreurs dans mon "plan" d'algo:

1/ Créer trois listes d'objets: brushes (occluders convexes), n-gons, plans, avec tous les rapports de bijections. Les polygones sont groupés par plans avec une marge epsilon (si deux ngons ont quasiment le même plan on considère qu'ils sont dans le même plan). Enfin on recale la vertlist de chaque brush pour qu'elle colle au plus près du plan.

2/ Insertion des, n-gons un par un dans l'arbre (en commençant par le plus proche du centre de l'architecture): test vertList VS bsp, on trouve les feuilles, et on les transforme en nouveaux noeuds avec deux nouvelles feuilles. A chaque insertion on splitte la BBox en petits morceaux pour savoir quels plans détourent les feuilles. Ca permet d'éliminer les faces qui ont déjà un plan qui détourent la feuille et ainsi on évite les flat-nodes. Le bsp-tree est construit, avec la géométrie de chaque feuille. (deux nouvelles listes: nodes, leaves).

3/ On génère les polygones qui connectent les feuilles deux par deux ("portals"). Chaque face de la feuille parcourt le BSP avec une marge epsilon pour trouver les feuilles voisines. Ensuite elle est splittée par les plans des feuilles voisines. Nouvelle liste: portails. Chaque portail contient les index de la feuille et du portail qui se trouvent de l'autre côté.

4/ On rétrécit légèrement les brushes avec marge e conservative, puis on teste la vertList contre l'arbre pour trouver les feuilles qui sont dedans, on les marque comme feuilles occlusives. Là on va surtout pas faire comme carmack qui crée une feuille solide qui ne voit rien, car au moindre bug de collisions la caméra ne peut plus rien voir. On va donc uniquement marquer comme bloquants les portails associés dans les feuilles voisines (et pouf on retrouve les bons vieux occluders traversables de duke3d).

Et voilà, normalement y'a rien d'autre à faire. Après vous récupérez le fichier .json à votre sauce et stockez ce que vous voulez dans l'arbre.

J'attends vos conseils, avis, coups de mains, etc... Je tiens à ce que l'algo soit bien réfléchi avant de commencer à coder mais bon en théorie c'est l'approche bête et classique du bsp-tree.

Je pourais ajouter tout un tas d'optimisation comme éliminer les portails trop petits, remplacer les brushes par des polygones à deux faces pour éliminer 50% des portails, mais la premature optimization est la route de all evil dead.

[edit] J'ai choisi de faire ça sur blender. Je préfère avoir un contrôle précis des algos split / clip plutôt que 3ds le fasse à ma place.

[Troumf Grognon]

Bon en fait je vais quand même faire quelques benchmarks avant de trancher.

[Kannagi]

Intéressant comme projet , même si j'ai toujours privilégier le quadtrre/octree

[Troumf Grognon]

Intéressant comme projet , même si j'ai toujours privilégier le quadtrre/octree

Oé mais ça c'est des structures pour le streaming d'open-space. La carte dans un quadTree et les chunks dans des octrees

Après si tu veux ajouter des bâtiments ou des grottes c'est plein d'occlusions à calculer et bah le bsp est la structure la plus "classique". Sinon y'a le potatoe-diagram du cryEngine mais du coup les graphistes ils cry.

Or là j'essaye de me mettre à la place des graphistes et une occlusionMap simplifiée c'est une première ébauche toute simple.

Mettons que tu veuilles faire un immeuble. Un brush pour le plancher de chaque étage (en laissant la place à la cage d'escaliser) va déjà faire une occlusion significative. Ensuite si tu veux occluder les murs les plus grands, un brush suffit pour tous les étages. Ca permet de modéliser à partir d'un "croquis 3d" tout con, avant même de s'occuper des proxies de collision et des jolis apparts en high-poly.

[Troumf Grognon]

Bon je viens de repérer deux erreurs dans mon "cdc",

1/ Y'a à priori pas besoin de sliptter les polygones occludants ("anti-portals") en construisant l'arbre vu que c'est les portals qu'on doit z-order. Donc en théorie on peut insérer chaque face dans l'arbre juste en faisant un test n-gon vs bsp, ensuite on convertit la liste de feuilles trouvées en nodes avec des nouvelles feuilles. Ca peut (peut-être ?) générer des noeuds inutiles mais premature optimization is racine de tous les pas gentils.

2/ J'ai pas du tout anticipé le problème des "flat leaves". Carmack a fait un algo lourdingue qui les élimine en aval seulement il reste tout un tas de flat nodes qui encombrent l'arbre pour rien. Donc, si on veut les éliminer en amont, dès la construction de l'arbre, il faut connaître les plans de la feuille pour pouvoir dégager les polygones qui ont un plan commun. Et là je vois pas 36 solutions à part procéder comme pour les kd-trees et les octrees, on démarre d'une BBox et on la découpe en petits morceaux. Comme ça la géométrie des feuilles est déjà prête pour générer les portails.

Donc je vais revoir le procédé avant de taper la moindre ligne de python.

P.S. J'ai réfléchi que les automatisations du maxscript en fait c'est pas bon car ça rend impossible les bijections face/plan. Or python est plus rapide en calcul donc je confirme le choix de Blender.