[Algorithmique] Voxels et prise de gueule... chaud chaud chaud

Recherche :

Dernière réponse
Sujet : [Algorithmique] Voxels et prise de gueule... chaud chaud chaud
tgrx	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...

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

tgrx	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...

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.

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

verdoux

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

tgrx

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 : :cry:

verdoux

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).

tgrx	:cry: ... :bounce:

tgrx

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 :hello:

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