Discussion :

[saturn1]

Bonjour,
j'ai lu un article sur gameDev qui explique le fonctionnement des quadtrees.
Mais par exemple si j'ai les parametres suivants =>

worldSize = 20X, 20Y

et que j'ai un objet qui fait 19X,19Y

La taille minimale d'une feuille devrait etre assez grande pour contenir mon objet.

Donc le quadtree perd de son interet!

Comment gerer les gros objets pour les quadTree?

Merci

[raptor70]

Si je me rappelle bien, tu as plusieurs façon de gérer les gros objets. Cela est fonction de ton projet.

Soit tu détermines sa position à partir de son centre. Du coup, tu peux voir apparaitre des effets de clipping.

Soit tu le considères dans toutes les feuilles qu'il chevauche. Dans se cas là, il est souvent traité. Il faut donc rajouter un filtre pour éviter de traiter le même objet sur plusieurs feuilles (flag sur l'objet). Le premier coup que tu le rencontres, tu le traite et tu le flag. Le second coup, sur une autre feuille, comme il est déjà flaggué, tu le skip.

[saturn1]

MErci,
La deuxieme solution me semble plus simple a mettre en place !

JE vais faire des recherche sur l'efficacite de chaque methode!

Merci

[oxyde356]

Ou sinon petite astuce si ça ne perturbe pas tes algos, tu considères tes noeuds comme des noeuds-feuilles et tu ne place pas ton objet tout en bas mais plutôt dans un noeud qui l'englobe entièrement plus haut dans l'arbre.

[Ti-R]

Oui la solution la plus correcte serait de prendre la bounding box de l'objet et de la placer directement dans chaque nœud approprié comme le souligne oxyde.

Si l'objet est énorme il est toujours affiché, donc pas besoin de le placer dans tous les sous nœuds, le but étant de découper la complexité, ton arbre sera au final aussi efficace mais plus rapide à construire et prendra moins de place en mémoire. Plus rapide à construire car dès qu'un gros objet sera traité, il n'aura pas besoin d'être à nouveau testé et pas de répétition dans l'arbre, donc moins de place utilisé.

[raptor70]

Tout à fait d'accord avec Ti-R et oxyde. J'avais oublié cette possibilité . C'est effectivement plus facile

[saturn1]

merci pour ton idee oxyde356!

[oxyde356]

De rien, mais attention cette façon de faire n'est pas parfaite, imagine que tu as un objet même tout petit en plein centre de ton quadtree, ton algorithme va te le placer à la racine de l'arbre car il n'y aura quelle qui l'englobe complètement même si l'objet est tout petit (faire un schéma pour bien comprendre), mais ce n'est pas du tout optimal car plusieurs feuilles bien plus petites pourraient le contenir.

[saturn1]

Ok donc le probleme c'est de choisir la taille d'une feuille la plus optimale possible?

[oxyde356]

Pas vraiment, dans le cas d'un petit objet placé en plein centre de ton quadtree il n'y en a pas, le mieux dans ce cas là c'est encore de prendre plusieurs feuilles. Juste pour te dire que tout dépend du cas à traiter. Enfaite quand tu ajoute un objet à ton quadtree, tu te donne une précision maximale à ne pas dépasser (le nombre max de subdivision de ton quadtree). Puis tu subdivise ton quadtree selon la boundingbox de ton objet, il faut subdiviser si un carreau de ton quadtree n'est pas totalement contenu dans la boundingbox de ton objet et si tu n'a pas atteint le nombre max de subdivision.

[saturn1]

tu me dis, qui si l'objet est place en plein milieu du quad tree, il appartient donc a 4 carre qui sont les 4 carre principaux, donc en gros je dois tester les collision de cet objet avec tous les autres?

[oxyde356]

J'ai mis à jour ma réponse d'avant tu regarderas ^^

Oui et non enfaite ce cas là c'est justement un problème, ce n'est carrément pas optimal que ton objet utilise les 4 premiers carreaux c'est pourquoi il faut descendre dans l'arbre pour y chercher un ensemble de feuilles plus adaptés, qui est plus "près" de l'objet (boundingbox de l'ensemble des feuilles sélectionnées bien plus petites mais qui contient la boundingbox de ton objet).

[saturn1]

Ok donc par exemple si mon objet est au centre du quadtree je vais donc selectionner 4 feuille pour cet objet, une dans chaque carre principal?


Du coup c'est pas tres optimale non plus car je dois descendre recursivement dans les 4 grands carre pour trouver chaque feuille!

[oxyde356]

Tout dépend tes critères d'optimalité. Si tu cherche la vitesse d'exécution et la taille mémoire minimum en effet ce n'est pas optimal. Mais si tu cherche la précision pour que ton objet soit le mieux "cerné" dans ton quadtree je pense que tu es obligé. De toute façon il ne faut pas voir ça comme "devoir parcourir les 4 carreaux principaux". Tu descend dans un arbre, ces 4 carreaux là tu en aura des similaires à l'étage du dessous qui te poseront le même problème et ainsi de suite. Et si tu ne descend pas en subdivisant les carreaux alors où est l'intérêt d'utiliser un quadtree.

[saturn1]

Merci de tes infos je vais proceder ainsi pour creer ma classe de quadtree.

Donc (question idiote) comme c'est un quadTree, les bounding Volume seront des box (OBB, par exemple). Mais je me demande si :

Temps(creation plus petite sphere englobant ma forme geometrique[welzl]) + Temps(detection collision sphere sphere) < Temps(creation plus petite box englobant ma forme geometrique) + Temps(detection collision box box[TAS]).


ce qui revient a
Temps(detection collision sphere sphere) < Temps(mise a jour de OBB) + Temps(detection collision box box[TAS]).
puisque les sphere sont orientations invariantes.


Merci de tes infos

[oxyde356]

Bah si tu peux pour les boundingbox de ton quadtree utilise plutôt des AABB si celui-ci est aligné sur les axes. Niveau collision je te conseille de d'abord calculer s'il y a une intersection sphère-sphère, si elle passe alors tu fais une AABB(quadtree)-OBB(objet). Une intersection sphère-sphère ne coute quasiment rien et ça te permet d'éviter de faire des calculs d'intersections plus complexes qui s'avéreraient inutiles.

[saturn1]

Ok merci pour toute ces infos

(ou est le bouton Voter pour tous les messages du sujet )

[oxyde356]

Le bouton Résolu peut faire cet office