Pour un moteur en exterieur, les arbres octree me semblent les plus appropriés.

- Comment l´implémenter correctement (optimisation possible...) ?
- Et si un objet bouge entre deux frames, il faut reconstruire l´arbre, c´est pas trop lent ?

Bon l´octree est un partitonement recusrif de l´espace en 8 sous dimension (des cubes) . Tu divise tes cube temps que tu a un nombre trop grand de point dans ces cube.

La division ce fait au chargement de la carte .
Ensuite quand tu bougs dans ton univers tu calculs a chaques frame le frustrum de vue ( volume de vision ) ensuite tu calculs quelle sont les cubes en intersection avec le frustrum de vue et si il sont en intersection tu les affiches.

voila un screen de ce que sa donne dans mon moteur
-> http://users.skynet.be/Data/Images/Octree.JPG

Data

Ps si il te faut encore des precisions demandes

Oui là je suis d´accord pour le frustum tout ça je sais faire.

Mais imagine qu´un objet de la carte bouge au cours du temps, ça remet tout l´arbre en question, vu que des polygones s´y déplace non ?

les objet sur une carte en bouge pas

pour les objets qui bougent tu dois utiliser une autre technique le PVS
potential visible set

tu prend tout tes objet et tu construit une boite autour de chaque objet si cette boite entre en contact avec le frustrum de vue tu dessine l objet.

donc on a

animation objet
detection collsion
corection position objet
dessin map
dessin objet

voila ...

Data

Ah d´accord, donc je garde l´octree pour les objets statiques et en fait je fais un "vulgaire" frustum culling avec les autres objets. J´avais aps trop compris ça en fait, merci de m´avoir éclairer !

personnellement je déconseille l´octree et je recommande plutot le quadtree avec une detection de la longueur la plus grande a partager a chauqe récursion car dans un bete octree si le niveau fait 8000m² sur un etage de 2 metres de haut, le niveau sera découpé 15 fois dans la hauteur ce qui est ridicule.

Mwai, l´idée de base reste la même. L´octree n´est pas une fin en soit, libre après de modifier son comportement pour qu´il colle au mieux à la map.

je fais ressurgir tous les topics un peu "techniques", je vais faire me lancer dans la prog 3D aussi.

Hmm, pour ne pas non plus faire remonter un topic deja passé, l´octree est-elle une node cubique ? je veux dire que de la 1ere division resultent 8 cubes ? ca serait plus logique et plus simple a calculer pour la recursion non ?

Sinon Lightness1024, pour l´octree, tu peux imposer de stoper la division si les secteurs contiennent deja un certain nombre de polygones (donc ca ne coupera pas forcement 15x en hauteur). Tu peux egalement ne pas diviser les espaces vides (ca serait un peu bete de le faire). Je pense que l´octree est une bonne technique... elle est simple a comprendre en plus ;-)

yep tu as tout compris

Data
www.ploksoftware.org

non justement !

je vais m´expliquer plus clairement mais avant je vais repondre: cubique ? ? mais voyons la sous division par 8 d´un parralélépipède c´est un parralélépipède pas un cube ! !!

pour mon etage voila l´astuce:

on est tous d´accord que l´OcTree c´est ca:

on fixe une limite MAX de polygones par secteurs.
on prend les extrèmes de la map.
on check si pour se secteur (secteur parent) le nombre de polygones compris est plus grand ke la limite, si oui, on coupe en 8 (olbigé puiske c un OCtree) et on vérifie pour les 8 secteurs le nombre de polygones compris dedans et pour chacun d´eux si c´est plus de la limite on les coupent en 8.
donc de cette maniere etant donné que nous sommes forcés de couper en 8 et bien si le niveau est tres ecrasé et bien chaque secteur sera tres ecrasé et on se retrouveras avec uen dixaine de secteur de 30 centimetres de haut pour faire la hauteur du niveau.

tu pars du principe que l univers n es pas cubique . Moi Je construit un cube autour de l univers et ensuite ej divise ce cube et grace a ca je n ai que des portion d octree qui sont tous cubic.

Data
www.ploksoftware.org

ah bah tiens, c fou comme en un an les choses peuvent changer =) desormais j´utilise les anti portals pour la visibility determination, ca permet d´avoir une scene 100% dynamique :]

Ah un topic interressant

moi je suis d´accord sur le fait qu´il faut réserver les octrees pour les objects statiques uniquements. pour ce qui bouge, a la rigueur, tu détermines juste une boite englobante, je te conseille un AABB ( Axis Aligned Bouding Box) et déterminer si cette boite est devant ou derriere la caméra, ou hors du clipping pour déterminer si tu affiches les objets dedans.
Si ton objet est monstrueux, ( uniquement s´il est monstreux) pkoi ne pas déterminer non plus un octree dedans ? et avec une racine relative au " point chaud" de l´objet : genre apres, quand la bounding box est partiellement visible, alors tu analyses rentres dans son propre octree...
Enfin, je pense que C juste pour les objets monstrueux, sinon, juste bouding box

anti portal ? c koi ca ?

c´est une technique qui consiste a utiliser des occluders pour faire de la determination de visibilité. Tous les objets de la map sont dotées de bounding boxes ( englobantes), et quelques objets ( les antiportals, donc), sont soit des volumes parallelepipediques, soit des sheets ( surfaces).

D´abord t´effectues un frustum culling pour reduire les brushes a tester, et apres, pour chaque antiportal ( qu´il soit sheet ou volumique), du plus pres au plus proche, tu testes les objets restants. C´est pas cher parce que les tests sont faits avec des bounding volumes, et c´est dynamique parce que calculé en temps reel. Le seul truc que ca implique, c´est un petit travail du designer pour utiliser des antiportals dans son design.

Cette technique est utilisée dans UT2003.

voilas quelques images de cette technique, dans UT2003 justement

ici on voi le brush orange, un antiportal parallellepipedique " desactivé"

http://udn.epicgames.com/pub/Content/LevelOptimization/apv_occlusion_1.jpg

et là ce que ca donne quand il occlude ( le terrain est morecelé en blocs de 16x16)

http://udn.epicgames.com/pub/Content/LevelOptimization/apv_occlusion_2.jpg