Discussion :

[ToTo13]

Bonjour,

je dispose d'un polyèdre représenté par ces faces triangulées.
Je souhaite le remplir, c'est à dire en avoir une représentation avec des voxels.

Est ce que quelqu'un connaitrait un algo qui fait ça rapidement ou mieux aurait des sources en C ou java ?


Merci...

[pseudocode]

Je vois pas bien ou est le probleme...

1. tu prends une bounding-box qui contient ton polyedre.
2. tu decoupes la bounding-box en petits cubes de la taille de tes voxels
3. tu prends chaque petit cube et tu regardes s'il est a l'interieur de ton polyedre

[ToTo13]

Bonjour,

justement, le problème est là.
Si je fais ce que tu as dis, je dois regarder pour chaque voxel s'il est dans la forme et cela nécessite de le comparer aux N triangles de mon polyèdre.

Or, j'ai un grand polyèdre... très grand...

[pseudocode]

Bah tu fais une dichotomie.
Tu commences avec des voxels de grande taille (disons bounding-box/4)

Tu parcours tous tes voxels:

• Si ton voxel est entierement dans le polyedre, tu le gardes tel quel.
• Si ton voxel est entierement hors du polyedre, tu le jettes.
• Si ton voxel est partiellement dedans/dehors, tu as 2 cas:

• cas 1: ton voxel a atteint sa taille minimale, tu dois decider s'il est dedans (tu le gardes) ou dehors (tu le jettes).
• cas 2: tu divises ton voxel (en 8)

Tu boucle sur ce processus tant que tu as des voxels a traiter (ceux qui sont ni gardés, ni jetés)

Edit: A noter que ca ne marche que si ton polyedre est convexe.

[FrancisSourd]

Est-ce que l'algorithme du peintre répondrait à ton besoin?

Pour un polyèdre, on peut utiliser les normales à chaque facette, calculer leur produit scalaire avec un axe "arrière-avant" et afficher les triangles qui ont un produit scalaire positif.

[ToTo13]

Bonjour,

l'algorithme du peintre fait la même chose que le Z-Buffer, c'est ce qui était utilisé avant.
Il ne fait pas du remplissage de polyèdres.

[FrancisSourd]

J'ai compris!

Tu peux utiliser une approche par projection.

Tu cherches d'abord les points de coordonnées x minimale et maximale qui te donnent xmin et xman.

Pour chaque x* dans [xmin,xmax], tu travailles dans le plan d'équation x=x*. Tu as un polygone convexe P(x*). Tu cherches de même le segment [ymin,ymax] qui correspond à la projection de P(x*) sur l'axe des y. Et, pour chaque y* dans [ymin,ymax], tu calcules zmin et zmax et tu sélectionnes comme voxels intérieurs la barre verticale (un segment) de pixels entre (x*,y*,zmin) et (x*,y*,zmax).

[ToTo13]

Bonjour,

merci, cet algorithme ressemble à la version 3D du remplissage de polygones.
C'est effectivement une solution, mais j'aurai aimé évité de programmer cela, même si la difficulté n'est pas extraordinaire.

Est ce que quelqu'un connaît d'autres algorithmes qui font cela ?

Merci...

[cindy63]

Bonjour,
Je sais que ce sujet est ancien. Je travaille actuellement sur un problème identique. Est ce que tu as trouvé une solution? Si oui, laquelle?
Merci

[ToTo13]

Bonjour,

si tu es très motivé, tu adaptes l'algorithme du remplissage de polygone au remplissage de polyèdres.
Sinon, pour chaque point contenu dans ta bounding box, tu testes s'il est dans le polyhèdre en comparant sa position à chaque point du polyèdre.