Algorithm d'Octree en 3D

**bouthamante** · 11/06/2008, 15h40

Bonjour,

je travaille sur un nuage de points définis par leurs coordonnées cartésiennes (x,y,z). Cet ensemble de points a la forme suivante: nx3 avec n le nombre de points (egale au nbre de lignes de la matrice) et 3 champs de x,y,z de chaque point successivement.
Mon problème est de diviser ce nuage de points en un ensemble de segments de points coplanaires (split process) et ensuite on doit fusionner (merge process) les segments selon deux critères: coplanarité et voisinage. On fusionne les segments voisins et qui sont coplanaires. La subidivision se fait à l'aide des cubes càd on considère le nuage de points ds un cube qu'on divise en 8 sous cubes et on teste la planèité des points dans chaque cube. s'ils sont coplanaires, on arrête la subdivision sinon on continue la subdivision de chaque cube. Finalement on obtient un ensemble de segments (points coplanaires dans un cube) qu'on doit essayer de fusionner selon les deux critères cités ci-dessus.
J'ai réussi la partie de subdivision, mais la partie de fusion pas encore. en effet, pour le moment je choisis un segment ds un cube et je determine ses cubes voisins et je teste la coplanarité, cela va bien dans la première itération car je sais définir les relation de voisinage entre les cubes. Mais après les segments ne sont pas forcément dans un cube mais dans une entité de quelques cubes géneralement de taille différentes.
La question est:
comment définir les relation de voisinage après la première itération de fusion?
Merci

**PRomu@ld** · 13/06/2008, 11h30

Tu dois pouvoir déterminer à un même niveau de subdivision quels sont les cubes adjacents, non ?

**bouthamante** · 24/06/2008, 16h16

Envoyé par PRomu@ld

Tu dois pouvoir déterminer à un même niveau de subdivision quels sont les cubes adjacents, non ?

Merci pour votre réponse, sauf que je vois pas comment faire exactement. Pouvez vous me tracer un algorithme à suivre? merci

**PRomu@ld** · 24/06/2008, 19h27

En fait, tu devrais jeter un coup d'oeil là dessus :

http://citeseer.ist.psu.edu/666278.html

**pseudocode** · 24/06/2008, 21h07

Généralement on fait du "path reversal". Je ne sais pas trop comment ca se dit en francais (chemin inverse ?). Il faut s'appercevoir que pour trouver le voisin d'un cube, il faut stocker le chemin qui remonte jusqu'a un ancetre commun, puis redescende ce chemin en inversant les directions.

Hum... je me rend compte que ce n'est pas clair. Mais essaye déja avec un quadtree (2D). Le principe est le même. D'ailleurs j'ai du poster le code du quadtree quelquepart...