Je viens de lire plusieurs articles sur les arbres BSP mais une question subsiste : le programme va il traiter toutes la faces d´un mondes ?
Cela veut il dire que l´arbre BSP n´est qu´une version pré-calculée de l´algorithme du peintre ou agit il également sur l´optimisation du rendu d´une image en occultant certaines faces.
Dans les exemples de pseudo code que j´ai lu, le programme recherchait d´abord les faces cachées, puis les faces coplanaires et enfin les faces avant, qu´il stockait dans un tableau. Mais traite il toutes les faces ?

Regarde donc cette page ( c´est interactif)

http://symbolcraft.com/graphics/bsp/index.html

tu comprendras mieux le fonctionnement

va falloir que je fasse un peu d´algo parceque là jecommence à prendre du retard sur vous les gars

Je comprends rien

les BSP comme on les entends c pas bien simple et perso g pas trop compris.
le pire c´est les portals, alors la je vois pas du tout comment ca marche.

j´ai choisi la methode facile: octree.
sauf que l´octree pur etait mauvais pour moi, donc j´ai modifé en un BiTree.

methode:
detection de la bounding box de la map
detection de l´axe le plus long, et découpage selon cet axe en 2 BB ( sous espaces complementaires de la grande).
cette recursion jusqu´a que dans chaque ´secteur´ il reste autant ou moins de polygones que dans la consigne.

je m´en servirais pour limiter les polygones de test pendant la detection des collisions.

mais je n´ai pas encore trouvé le moyen de créer un potientially Visibla Set.

c´est la tout l´avantage d´un vrai BSP, il parait que la determination de ce qui est potentiellement visible se fait naturellement pendant la construction de l´arbre.

chez moi ca va risquer d´être tres compliqué etant donné que les dimensions de mes secteurs ne sont pas calquées sur des polygones de reference comme en BSP.

bon, tout ca pour dire que je peux pas trop te renseigner avec precision
mais que tout de meme, le principe d´un arbre est de créer des " conteneurs" ( ce que j´ai appelé ´secteurs´) pour manier des polygones par paquet.
et non de tous les traiter un par un ce qui ferait un algo en complexité o².
l´avantage de l´arbre est d´avoir une complexité en log2(o).
( log2 pour le binaire, log8 pour l´octree etc...)

G pas voulut lire..trop long jsuis dsl.......

soit désolé pour toi bonhomme

je parle pour lag-it

Euh i didn´t understand ^^ Ouai enfin voilà.....

j´en profite pour attirer l´attention sur certains points :
- les BSP " solid" : en stockant le polys un peu différement ( en " faisant" les fronts ou back dans les noeurs) on obtient une information bien sympathie : les zones pleines ( ou fermées, selon comment vous l´appeler ; un pilier parallélépipédique, par ex. est une zone solide dans laquelle le joueur ne peut aller). On a alors en temps constant si un point est dans une zone solide ou non : c´est *TRES* pratique pour les collisions, ou pour les algos de visibilité.
- le PVS, si on n´a pas d´apriori sur le scène, peut etre construit " à la bourrin" : c´est long mais c´est encore le plus précis. Pour cela, on sudivise chaque poly ( genre par une grille régulière), on teste la visibilité des centres des autres polys depuis chacune des subdivisions, et on tient à jour pour chaque poly ceux qui sont visibles. Bien sûr, la finesse de la subdivision influe sur le temps de calcul du PVS durant la compilation du BSP mais également sur la précision ( si vous avez joué à UT, sur certaines cartes et depuis certaines positions, il y a des imprecisions : des polys non affichés alors qu´ils devraient l´etre)
- enfin, l´importance du choix du splitter ; sans apriori sur la scène, il faut avoir une idée de ce qu´on recherche : un arbre équilibré, le minimum de subdivision, etc. ?

moi je dis bravo, g rien comprit mais si a peu prés ça va sauf quelques termes

edit :
. ..en " faisant" DESCENDRE les fronts...
noeurs => noeuds
sympathie => sympathique
+/- qq autres moindres

salut LGV

Je crois que pour toi faudrait faire un systeme pour reéditer les posts

LOL, ouais c´est clair ; ) sur tous les forums j´ai l´habitude de poster, de me relire, et de me corriger... là.. c´est souvent que j´oublie de me relire AVANT de poster :/

Mais commenbt vous vous prenez pour des dieux, bon, vous êtes forts, mais faut arrêter la vantardise 2mn svp.....

" Mais commenbt vous vous prenez pour des dieux"

euh... où ça ? qui ? . .. une question est posée, tlm participe pour apporter une réponse ; maintenant si dès que ça devient un tant sous peu technique tu crois que les gens en parle juste pour faire joli ou par vantardise, tu te fourres le doigt dans l´oeil jusqu´au coude : on parle technique parce que la programmation, C´EST technique ! . .. au passage, oui, ça change de rm2003...

jamais contents ici : on casse du neu² qui pose des questions idiotes, ça rale, on indique où rechercher le bon topic, ça rale toujours, on répond à des questions pour une fois interessante, ça rale encore... J´crois que tu te trompes de cible en disant " faut arreter". Maintenant,si tu fais un complexe d´infériorité, c´est ton soucis.

" Mais commenbt vous vous prenez pour des dieux"

" des dieux" c´est marrant il doit en avoir beaucoup du coté de la NASA

Hahaha lgv++ ; )

Petite precision pour toi lgv < troll>vu que certaines personnent ne comprendront pas</troll> :

le pvs, qui est egalement utilise pour le calcul des lightmaps, donne de " mauvais" resulats car on limite le nombre de portals et ansi de nodes: les portals permettent de sauver BCP de temps, mais leurs imprecisions s´en ressentent fortement dans le clipping. Une nouveaute apportee dans q3 par ex est le sharing de poly dans plusieurs nodes, ce qui rend l´algo encore plus incomprehensible.

Je sais pas si tu te souviens de mon projet, mais pour avoir mis de mauvais parametres pour ma creation de portals, mon gros modele a mis plus de 2 jours a calculer le pvs ( sur nessie) ; )

Merci pour les nombreuses réponses
J´avais déjà vu le site Aiton, mais il concerne l´élaboration et non l´utilisation des arbres...

En fait ma réelle interrogaion vient des liens qu´il existe entre l´arbre bsp et les rayons dans un moteur de ray-casting ( pour simplifier par rapport au ray-tracing ) .
Autant dans un moteur type wolf3d, ou la map est représentée sous forme de blocs orthogonaux, dans un tableau, je vois comment cela fonctionne pour calculer sur quel mur le rayon atterit et son typpe, autant dans le cas d´un moteur comme celui de doom ou duke3d, avec des couloirs d´un angle différent de 90°, je ne vois pas comment cela fonctionne. On lance le rayon à travers l´arbre ? Si oui comment ?
Sinon l´arbre ne sert-il qu´à l´affichage et les rayons sont-ils utilisés sur un autre type de données ( un tableau, etc... ) ?

kUfa : LOL, oui, un peu que j´en m´en souviens de ton projet :D dans le plus pur style " bon, apres 12 h de calculs je me rends compte que j´ai oublié un paramètre" ou " cool, mon BSP est bon ( seulement 2 jours...) mais j´ai un bug dans la sérialisation" eh eh. Pis c´est toi qui m´en avait parlé en plus des solid BSP ; je l´avais implémenté en 3e année mais ils nous manquait les modules de certains groupes de travail, donc la scène restait tres simple
Sinon, pour les portals, j´ai l´impression que chacun y va de son astuce, et qu´on final ça devient bien le merdier les algos... Entre les BSP sans portal ( !), ceux qui s´en servent que pour le rendu, ceux qui y stockent des polygones en double ou en triple, c´est " démerde toi pour que ça marche" si je comprends bien :D
pis qu´est-ce que tu fous là à poster, toi, t´es pas à deadline + 1 aujourd´hui ? . ..

lag-it : on fait de tests d´intersection ligne/polygone. Mais on utilise rarement un BSP avec un rendu en raycasting : le BSP augmente le nb de polys, donc ça serait encore plus couteux en temps.
le rendu d´un BSP ressemble grosso modo à : je fais " descendre" les plans de clipping du frustum dans le BSP, et on en déduit les polygones compris dans le zone de visu. Ensuite, on rend les polygones du plus lointain au plus proche ( simple parcours de l´arbre), en omettant de dessiner les polys " back" ( vu qu´ils ne sont visible). Bon ensuite, y´a des précautions à prendre, genre s´il y a des polys transparents ( fenetres..), etc. Mais l´idée est bien de tracer ce qui est visible à partir de la position de la caméra.
Sinon, on fait quand meme un peu de raycasting, pour la visibilité, genre " est-ce que de mon point de vue, je vois l´ennemi". Là, on a deux points, départ et fin du " rayon" ( qui est plutôt un segment) : le BSP nous donne leur situation ( le noued/groupe de polys dans lequel ils sont) et les noeuds traversés : il n´y qu´à tester si chaque noeud traversé par le rayon est solide pour savoir si " voit" la cible.
En textuel, tout ceci n´est pas forcément tres clair ( j´y pitais pas grand chose moi meme avant de vraiment le coder), donc le mieux c´est p-e de trouver une implémentation basique et de l´étudier.
Le lien donné au début ^^^^ donne une bonne base.