Discussion :

[SeanVanDeBert]

Bonjour à tous,

J'ai réalisé plusieurs recherches sur ce forum, et je n'ai pas trouvé de sujets relatifs à mon problème.

Je cherche un algorithme efficace et peux coûteux en terme de temps de calcul, permettant de reconstruire une surface 3D à partir d'un nuage de points. Ces surfaces sont des formes géométriques relativement simples.

Donc concrètement, en entrée de mon algorithme, je possède un nuage de points (coordonnées X, Y, Z), sans d'autres informations. Je sais seulement que mes formes sont des surfaces (et non pas des pièces convexes, donc l'algorithme de Convex Hull n'est pas utilisable).

J'ai adapté l'algorithme suivant de Heiko Enderling :
http://www.heikman.de/index.html?/to...ngulation.html

Je trouve cet algorithme un peu simpliste et trop rigide (il faut connaitre la distance minimale entre deux points voisins). J'ai des premiers résultats plus ou moins satisfaisants mais le temps de calcul n'est pas du tout adapté à mon application et je suis intimement persuadé qu'on peut trouver un algorithme beaucoup plus efficace.

Je commence un peu à saturer à lire des publications et des rapports de thèse, donc je fais un petit appel à l'aide :

Auriez vous déjà implémenté un tel algorithme ? Si oui lequel ?
Sinon sauriez vous orienter un peu ma recherche car je ne sais plus quoi rechercher sur internet pour mon problème.

En vous remerciant par avance.
Bonne journée.

Cédric.

[SeanVanDeBert]

Je poste les autres pistes que j'ai pu trouver pour aider d'autres personnes qui seraient éventuellement dans la même impasse.

L'algorithme de marching cube pourrait être utile pour ce genre de problème :

http://www.developpez.net/forums/d11...arching-cubes/

http://users.polytech.unice.fr/~ling...s/accueil.html

Je n'ai pas le temps de tester la solution, mais en vu de ce que j'ai pu lire cet algorithme semble assez prometteur.

[Jean Dumoncel]

Bonjour,

tu peux aussi regarder les fonctions implémentés dans meshlab, en général il y a une référence des algos utilisés. Les marchings cubes sont notamment implémentés dans ce logiciel mais il y a aussi un algorithme "Ball pivoting", un autre nommé Poisson reconstruction, très efficace.

[Kangourou]

salut,

On trouve beaucoup de constructions basées sur les triangulation ou les tétraédrisations de Delaunay (décomposition en simplexes -> des triangles en 2D et des tétraèdres en 3D). La génération du diagramme se fait assez rapidement, la question est de savoir quels éléments on garde pour la suite. J'ai vu passer des choses comme les graphes de Gabriel ou les Alpha Shape. Ça nécessitera quand même quelques adaptations.

A+

[SeanVanDeBert]

Merci pour vos réponses. Je vais regarder ça dans le détail et je vous donnerai mes impressions sur mon avancement.

Bonne journée.

[SeanVanDeBert]

Bon, bon ,bon ...

J'ai un peu fait mon flemmard sur ce boulot

Du coup au lieu de perdre mon précieux temps à mailler mon nuage de point, j'ai utilisé des PointArray. J'explique ma démarche sur ce post, pour ceux que ça intéresse :


http://www.developpez.net/forums/d1206123/java/interfaces-graphiques-java/graphisme/3d/java-3d-dimensionnement-dynamique-pointarray/

Je conseil cette méthode aux gens qui ont besoin de représenter un nuage de points 3D sans avoir besoin d'un rendu de qualité.