LGV:

pour mon bitree, il est deja tout programmé

oui c´est un quadtree mais plus mieux bien.

je prend la map, je detecte la boite englobante

et la, je coupe en 2. ( pas en 8 ou 4 ! )
et pour savoir suivant quelle axe, je detecte le coté le plus grand de la boite.
et je coupe ce coté
j´obitent 2 boites complémentaires de la grande.
puis récursion...
jusqu´a que dans chaque secteur le nombre de poly soit au max égal a la consigne de compilation.
( ou alors que la taille du secteur soit egale a 8*8*8)
mes unités sont presque des pouces
en fait, c les unités de worldcraft.

Merci LGV, l´exemple de la caisse était bien parlant
Quand au clou, ce n´était qu´un exemple d´objet minuscule, mieux vaut prendre une texture dans ce cas.

" oui c´est un quadtree mais plus mieux bien."

Diviser par deux n´est pas forcement " plus mieux bien", puisque la repartition des polys n´est pas forcement la meilleure entre les differentes feuilles, et c´est en general pas optimal pour les portals..

Ensuite, pour les clous dans les bsp, il y a une solution tres simple: donner un id a des objects ne devant pas etre inclus au moment de la creation du bsp, et les rerajouter a la suite dans les bonnes feuilles. Bien entendu il ya redondance, mais un boolean permettra de savoir si il est deja affiche ou non ( enfin c´est un example)

/ kUfa

" les rerajouter a la suite dans les bonnes feuilles"

ah oui, tiens, c´est tout bête et pas con du tout ça ! Les bonnes astuces de tonton kUfa.. T´es pas en vacances au pays de la bicyclette toi ?

mais justement, je ne fais pas un BSP !
et j´ai pas de feuilles ou koi, j´ai rien compris a ces trucs la.

mon algo est un octree amélioré.
et les types de map que j´ai sont mieux partitionnés avec mon bitree.

prenons le cas d´une map representant uniquement une terrasse d´immeuble.
200 metres de large, 100 metres de long et 1.5metres de haut.

partitionne en quadtree ou en octree, tu verra l´epaisseur des secteurs, tout rikiki !
tandis que mon bitree intelligent qui coupe suivant les distances les plus longues pourra parfaitement séparer cette map en de bons secteurs de forme se raprochant a des cubes et non a des crepes de 100 metres.

voila l´histoire !

bon, de plus j´ai programmé des fonctions que je qaulifierait d´infaillibles pour trouver les polygones compris dans les bounding box ( secteurs) ou qui ont une surface commune a la BB; alors j´en profite.
je créer une liste d´index de polygones par secteur
ca prend 1 Mo une fois sauvegardé dans un fichier pour une map de 8000 polygones ( deja tres gros vu mon editeur) avec une limite a 40 polys/secteurs.

par contre j´ai pas encore trouvé le moyen de charger le fichier en récupérant la structure de l´arbre.
vu la rapidité de sa construction ( je suis passé de 40 minutes a 6 secondes en optimisant) si ca se trouve je vais meme pas l´enregistrer, je le regénererait au chargement.
mais bon, j´aime pas bien, ca va encore tout me buger ca.

Tien Ligthness : j´ai commencé mon propre moteur 3d, mais avec OpenGL, et je rencontre le même problème que pour ton Alpha8 dans l´ouverture des fichiers . map :

http://perso.wanadoo.fr/thomasc/Screenshots.html

Je ne sais pas encore comment fonctionne le format . map, mais j´ai téléchargé la documentation officielle du format pour améliorer le convertisseur que j´ai écrit...

" j´ai pas de feuilles ou koi, j´ai rien compris a ces trucs la."

t´as un k-tree, donc un arbre, donc t´as forcément des feuilles... ( les feuilles étant simplement les extrémités sans fils de ton arbre)

" mon algo est un octree amélioré"
ben moi je vois pas tres bien où est le plus mieux en fait :-?
un octree, c´est adaptatif, tu subdivises que là où il y a besoin ( là où y´a des polys quoi), jusqu´à une limite sur 1) le nombre de polys de chaque feuille 2) la taille du cube d´une feuille

Ensuite, oui un octree/quadtre/blablatree c´est rapide à construire ( moi meme je fais une variante de quadtree pour une heightmap 32000 polys traités moins 0.62s, on va pas s´emebeter à le stocker...). Par contre on a BEAUCOUP moins d´information que sur un BSP : pour la visibilité, les faces cachées, les collisions, etc. tu vas devoir faire pas mal de calculs supplémentaires qui avec un BSP adéquat seraient " immédiats".

Enfin, si ta structure de données répond à tes besoins, plus besoin de polémiquer ( ni de jean et donald d´ailleurs... je sors :D )

le pb c´est que je sais pas faire les bsp, ni les exploiter :´( snif

bah, je me débrouillerait.
oué un k-tree lol, si l´octree c pas bien voala ca coupe en 8 je trouve ca bete, enfin c pas grave chacun son truc.

" ni de jean et donald"

MDRRRRRR, non reste

lag-it>
et oui !
c´est la super definition de solides du format . map

en fait ce n´est pas un probleme
voila l´explication
dans un . map ne sont stoquées que les triangles appartenant aux plans des faces des solides qu´ils définissent.
heureusement, les solides sont convexes, donc pas intersection de plans, on peut trouver tous les points du solide en question.
on supprime les doublons qui apparaissent avec cette méthode.
( besoin d´une grande précision sur les coordonnées, j´ai eu bcp de problemes dans les alpha 12 et 13 avec ca)
ensuite il faut détecter les points " hors solide"
i.e. qui ne respecte pas la convexité du solide.
merci a hammer de nous donner des plans orientés.
( les 3 vertices des triangles qu´il nous donne sont en rotation de maniere a que si on créer les normales avec toujours le meme ordre on trouve une orientation des normales vers l´intérieur ou l´exterieure du solide ( selon le sens du produit vectoriel qu´on fait) et donc ca permet de faire des tests, point-plan est il devant est t-il derriere ? on fait ce test pour chaque point par rapport a chaque plan et on garde que les points qui sont a l´intérieur du solide)
une fois kon a tous les points, il faut les relier pour rendre le solide, ben une forme faite de surfaces fermées koi.
il suffit de garder les triangles deja donnés, et de continuer en testant les points extrapolés coplanaires avec les plans définis dans le fichier.
et puis on trafique sa tessalation perso pour finir la face !
et voila on a des beaux solides pleins et convexes !
c´est la méthode que j´utilise a partir de l´alpha 13, l´alpha 12 utilisait une méthode pourrie a base de detection des points complanaires et ca suffisait pas du tout.
en general ca foirait sur les solides qui avaient recus un " merge" ou un " hollow".
donc les intesections de plan c le seul moayen
fo pas oublier en faisant la tessalation de faire tourner les vertices comme il faut pour avoir un culling correct par la suite.
pour ce faire je prend un point qqonque sur la face " i" du solide créer, et je calcule les angles par rapport a un axe arbitaire de tous les points.
je trie avec un quick sort, et je fais ma reliure en fonction de cet ordre croissant.
ca marche a tous les coup grace a la convexité des solides.
( c´est ca ma tessalation en qq sorte)

aller, si ta d´autres question, je peux t´assuer que je connais vraiment les moindres detail la dessus donc hesite pas.
( la preuve )

bonne chance @#

tite post correction:

donc paR intersection de plans

detection des points coplanaires ( pas complanaires)

Merci pour les conseils lightness
Tes explications + les docs officielles, j´ai toutes les infos qu´il me faut

" l´alpha 12 utilisait une méthode pourrie a base de detection des points complanaires et ca suffisait pas du tout"

C´est comme ca que j´avais commencé à faire, mais je vais jeter un oeil sur la méhode que tu vient de me donner ( alpha 13 ) qui a l´air mieux ( surtout si elle évite les problèmes avec les hoolow et autres.

Je n´ai pas d´autres questions pour l´instant

Sinon concernant l´usage des arbres BSP, j´ai eu du mal à comprendre car c´est une notion assez abstraites et que les tutos ne sont pas clair ( comment ne pas traiter les faces cachées, etc . .. ) . Et j´ai trouvé ce site :

http://hulud.planet-d.net/?item=1

Qui réponds à pas mal de questions. Il exiplique les avantages, les algorithmes et leur usage. C´est le plus compréhensible à mon avis...

" le pb c´est que je sais pas faire les bsp, ni les exploiter :´( snif "

Je te conseil vivement http://tfpsly.planet-d.net/Docs/TomHammersley/, mais aussi gamedev, flipcode et google ; )

/ kUfa.sCx de retour du pays des bicyclettes

mais mais ?
est-ce que je viendrait presque de comprendre un début de qqch sur les portals ?
putain je serait trop heureu si c t le cas.

je v continuer de lire ce truc, ce type ca m´a l´air d´être balaize-man en personne pfou

merci kufa ki revient du pays des bicyclettes

" Quatre fois diplômés au Prologin - EPITA, Paris - en 1998,1999,2000 et 2001"

bordel, c pas une tapette

Ah si j´ai une petite question :
Dans le cas suivant : on a un solide à base octogonale un peu comme cela :

00XXXXX00
0X00000X0
X0000000X
X0000000X
X0000000X
0X00000X0
00XXXXX00

Je vais numéroter les faces :

00XX1XX00
080000020
X0000000X
700000003
X0000000X
060000040
00XX5XX00 ( j´espère que c´est lisible )

Si on effectue l´intersection entre le plan formé par la face 2, celui de la face 4 et la base du solide, on va obtenir un point à l´extérieur de celui ci, comme ca :

00XX1XX00
080000020
X0000000X
700000003* < - Le point trouvé ( plan de la base )
X0000000X
060000040
00XX5XX00

Mais ce point n´existe pas en vérité...
C´est ca ce que tu appelles les points " hors solide" ?

beuh chai pas c pas bien clair tout ca.

moi j´ai réussi cette etape grace a un type qui s´appelle Stefan Hcnojski ou je ne sais koi, atten je v retrouver le nom exact, g tout noté qq part pour les remerciements dans le generique.
[...]
trouvé !
Stefan Hajnoczi

voila, il a fait un pdf sur les chargements des fichiers map. ya des bos dessins dedans.
en fait je tient ce nom d´un pote a moi ki programmait encore quasiment la meme chose avant nous ( møgluglu ki s´appelle) pour un jeu qui devait s´appeller City Gang
( géré par Aarown et Doberman, les createurs des mods vengence et rebellion de half life)

bon, son tuto est pas mal, mais ya plein de failles, ses raisonnements ne sont pas complets, enfin bon, a nous de prendres les idées mais de concevoir correctement koi
si tu le trouves encore avec google ben voila essaye koi

sinon a propos des points hors solide, ben c un point avec lequel le test pour au moins une face aura montré qu´il est derriere cette face.
donc il ne peut pas exister.

si on considère que ton schéma est un pilier octogonal vu de dessus, les plans ( je dis bien PLANS, je ne vois pas ce que la base vient faire la dedans :-?) s´intersecte en une position qui n´appartient pas aux polygones, donc on subdivise rien du tout.

si tu prends une forme convexe, quelque soit le splitter choisi, il ne subdivise aucune autre polygone.

tu prends un splitter ; tu determines son intersection avec un autre poly ; l´intersection est DANS le poly => subdivise, l´intersection n´est pas dedans, on ne fait rien.
on préfère d´ailleurs faire ce test sur les sommets du polys : tous les sommets du poly sont d´un meme coté du splitter => y´a pas subdivision, s´ils sont de part et d´autres, on coupe.

maintenant attention à l´appelation " solide" qui va avec le BSP associée ; une zone est alors dite solide si elle comprise entre des polys à normales sortantes, ex :

zone non solide

^
|
--------------
|////////////|
< -|zone solide |->
|////////////|
--------------
|
v

et ça ça se détermine à la construction du BSP.

pour nous ces infos la sont deja construites dans le . map

Attention LGV, on est sorti des BSP : on parle de la reconstituion des solides d´un fichier . map.

Bon j´ai trouvé ce dont tu parles light :
http://www.google.fr/search?q=cache:nZZyiZwBOrgJ:folk.uio.no/stefanha/MAPFiles.pdf+Stefan+Hajnoczi+&hl=fr

Je regarderais demain merci

^^^LOOL, ok , vu que ça parle d´intersections de plans, j´étais resté sur le BSP ; autant pour moi
et bonne chance avec le format . map qui m´a l´air assez tordu

http://members.fortunecity.com/torktools/doc.html

Y a pas mal de descriptions concernant les formats utilisés dans les moteurs 3d.