Je vous explique mon probleme : j'ai un volume defini par un ensemble de voxels, c'est-a-dire des cellules delimitees par 8 points formant les sommets. Une valeur est attribuee a chacune de ces cellules.
Ces cellules ne sont pas cubiques, ni parellelepipediques, elles sont assez quelconques (en fait ce sont des cubes deformes, mais de maniere assez aleatoire).
 
Je desire afficher ce volume en temps reel en utilisant les textures 3D d'OpenGL, pour cela il faut que je definisse une texture 3D ce qui n'est rien d'autre qu'une matrice 3x3 de voxel-values, ou encore un cube dans l'espace defini par des voxels tous cubiques et de meme taille.
 
Donc voila mon probleme : transformer tous les voxels quelconques en une serie de voxels cubiques identiques.
 
J'ai deja ecrit un premier algorithme, mais celui-ci est tres lent :
Pour chaque voxel cubique,
(1) Determiner le voxel quelconque le plus proche
(2) Faire une interpolation trilineaire des valeurs des voxels quelconques les plus proches pour determiner la valeur du voxel cubique
 
Resultat : l'etape (1) est en O(n), donc mon algo est en O(n^2).
Sachant que mon dataset comporte quelque chose comme 50000 voxels, ca prend un temps incroyable (environ 2h sur mon Xeon 550).
 
Je desirerais implementer quelque chose de plus rapide. Toutes les propositions sont les bienvenues

[edit]--Message édité par tgrx--[/edit]

...

Tu pourrais découper ton espace en cubes, chaque cube pouvant contenir plusieurs de tes volumes.
 
Donc pour chaque voxel, tu regardes à quel gros volume cubique il appartient et tu restreints donc le nombre de voxels sur leque travailler.
 
Evidemment il faut aussi tenir compte des voxels sur les bords et regarder les optimisations possibles (choix de la taille des cubes).

Le seul probleme est qu'ensuite je compte afficher la texture 3D, donc je n'ai pas interet a perdre de l'information sur mes voxels pour avoir une bonne qualite d'image.
Donc en fait au final ma matrice cubique aura tendance a avoir plus de voxels que les voxels foireux originaux...
 
et donc :

Non les cubes, c'est en plus !
C'est juste pour ranger différemment les voxels, ils n'ont aucune réalité.

Ah oui... (je seche mes larmes)
 
C'est pas bete du tout... diviser pour regner donc...
Merci Verdoux

D'ailleurs, tu peux aussi jeter un coup d'oeil sur les BSP tree, c'est pratique pour partitionner l'espace.  
Par contre il faut faire gaffe aux voxels dont les voisins seraient dans une autre partition.

C'est peut etre un peu bourrin un BSP pour ce probleme non ? mais c'est vrai que ca reduirait la complexite a O(n.log n)...
 
Merci pour toutes ces precisions, auxquelles je n'ai meme pas pense une seule seconde...