Discussion :

[3Dgirl]

Bonjour!

J'aimerais savoir si quelqu'un a une idée d'algorithme de dépliage ou de mise à plat d'un objet 3D.

J'ai beau faire des recherches sur internet mais je ne trouve aucun algo.

J'ai déjà construit le graphe des sommets de mon objet maillé. J'ai pensé
développer ensuite l'algorithme de Dijkstra pour trouver le plus court lacet de mon objet.
Mais après cela , après avoir eu toutes ces informations, que faire exactement? Sur Internet, en général ils disent qu'après cette étape, il faut faire un découpage mais sans plus. Je suis perdue.

Aidez-moi s'il vous plaît!

Merci d'avance pour vos réponses.

[FR119492]

Salut!
Si je t'ai bien compris, tu as un objet qui occupe un certain domaine dans R^3; tu l'as maillé, probablement dans l'idée de l'étudier par la méthodes des différences finies ou des éléments finis. Maintenant tu veux l'appliquer dans R^2 par dépliage. Pourquoi donc? Es-tu certain que ce soit possible?
Jean-Marc Blanc

[3Dgirl]

Bonjour!

En fait l'objet est déjà maillé à la base. Et ce que j'aimerais faire du "unwrapping"

je ne sais pas exactement si c'est ce qu'on dit. Imaginez que vous disposez d'une texture et que vous voulez l'appliquer à un objet 3D, vous partez bien d'une forme 2D pour avoir une forme 3D. Moi j'aimerais faire le contraire. Imaginez un cube qu'on déplierait et qui donnerait une patron (peu importe lequel), mais un patron qui par déformation redonnerait notre cube.

C'est ce que j'essaie de faire dans le cadre d'un projet! Mais je n'y arrive pas vraiment.

[pseudocode]

En fait l'objet est déjà maillé à la base. Et ce que j'aimerais faire du "unwrapping"

je ne sais pas exactement si c'est ce qu'on dit.

On dit plutôt "Flattening" (ou parfois unfolding, dans des cas particuliers).

http://citeseerx.ist.psu.edu/search?...ace+flattening

[FR119492]

Salut!

Imaginez que vous disposez d'une texture et que vous voulez l'appliquer à un objet 3D, vous partez bien d'une forme 2D pour avoir une forme 3D.

La première question qui se pose est de savoir si tu as le droit de "découper" ta surface. Si ce n'est pas le cas, sache qu'il y a des surfaces dites développables pour lesquelles c'est possible (cylindre, paraboloïde hyperbolique, etc.) et d'autres, dites non développables, pour lesquelles ça ne l'est pas (sphère, paraboloïde de révolutions, etc.)
Jean-Marc Blanc

[3Dgirl]

Merci pour le site!

Je vais déjà y jetter un coup d'oeil. Je dispose des deux types d'objets (développables et non développables).

En même temps, je ne comprends pas pourquoi on ne pourrait pas déplier une sphère alors qu'on peut déplier un cylindre.

[3Dgirl]

C'est quoi la différence entre flattening et unfold?

Puisque moi, je voudrais déplier, ce n'est pas plutôt unfold?

[pseudocode]

C'est quoi la différence entre flattening et unfold?

Puisque moi, je voudrais déplier, ce n'est pas plutôt unfold?

Pour ce que j'en sais (donc je ne garantis rien ) :

- "flattening" ca veut plutôt dire mettre a plat en conservant une propriété, généralement les distances, par exemple : la Terre -> un planisphère.

- "unfolding" va veut plutôt dire découper en surfaces planes jointives, par exemple : un cube -> un patron en forme de T, ou de croix.

[Zavonen]

La première question qui se pose est de savoir si tu as le droit de "découper" ta surface. Si ce n'est pas le cas, sache qu'il y a des surfaces dites développables pour lesquelles c'est possible (cylindre, paraboloïde hyperbolique, etc.) et d'autres, dites non développables, pour lesquelles ça ne l'est pas (sphère, paraboloïde de révolutions, etc.)

Tout cela est parfaitement exact mais le problème ne se pose pas vraiment ici, la surface étant triangulée elle est 'assimilée' à un polytope.
Voir par exemple le cas du ballon (non developpable) de foot avec des pentagones.
http://upload.wikimedia.org/wikipedi...cosahedron.gif

[3Dgirl]

Bonjour!

Mes idées sont encore très floues mais je pense que je vais peut-être essayer de faire des projections de faces reliées entre elles par des arrêtes communes et des rotations en 2d et préserver les distances.

C'est encore très flou!

[Zavonen]

En fait il suffit de savoir déplier une figure formée de DEUX triangles seulement.
Explication. Suppose que tes triangles soient organisés en un graphe dont ils sont les sommets. Un triangle est relié à un autre s'ils ont un côté commun.
Donc chaque triangle (sommet du graphe) possède 1,2 ou 3 voisins).
On affecte à chaque triangle, au début un marqueur binaire.
Au début tu choisis un triangle T0 aléatoire pour commencer, tu le marques.
Tu sélectionnes un voisin T1 de T0 ayant un côté commun c avec T0.
Tu détermines la rotation R1 d'axe c qui amène T1 dans le plan de T0.
Tu transformes par R1 TOUS les sommets appartenant à des triangles distincts de T0 et tu marques T1 et qui ne sont pas sur c.
Donc à ce stade, les deux triangles marqués sont dans le même plan.
Tu continues ainsi.
Tu désignes par T2 le premier triangle non marqué ayant un voisin V déjà marqué. Tu détermines la rotation R2 qui amène T2 dans le plan de son voisin V. Tu transformes par R2 tous les sommets appartenant à des triangles non marqués et non situés sur l'axe de la rotation, puis tu marques T2, et ainsi de suite jusqu'à ce que tous les triangles soient marqués.
A la fin toute ta figure est dépliée.
Le seul problème à résoudre est donc de 'déplier une figure formée de 2 triangles
ABC et ABD par rotation autour de l'axe (AB).
Dans une base orthonormale ayant la droite (AB) comme axe Oz, la matrice d'une rotation est:

a -b 0
b a 0
0 0 1

avec a²+b²=1

Il suffit donc de déterminer a et b pour que l'image de D soient dans le plan (ABC). La mise en équation est simple.
On trouve deux possibilités correspondant à des angles alpha et pi-alpha. on choisit celle pour laquelle C et l'image de D soit de deux côtés différents de la droite (AB) dans le plan (ABC).

[HanLee]

En fait, partant d'une surface connexe par arcs, tu cherches à obtenir un cut graph (graphe de découpe) sur ton maillage, c'est-à-dire l'ensemble des arêtes telle que ta surface 3D privée du graphe est homéomorphe à un disque ouvert !

Voici un cours :
http://www.di.ens.fr/~colin/cours/al...s-surfaces.pdf

Le chapitre 4 est probablement ce que tu veux.

Tu trouveras aussi quelques liens vers des papiers décrivant des algorithmes.

Quelques exemples pratiques :
http://www.cs.caltech.edu/~keenan/project_topology.html

Quelques notions de base de topologie algébrique sont nécessaires, bien sûr!

[3Dgirl]

Merci Pour toutes vos suggestions!

Je vais utiliser toutes vos donner pour créer un algo et l'implémenter.

Je vous donnerez suite d'ici 2 jours (parce que je ne suis pas une GEEK en tant que telle)

je vous tiens au courant!

++

[Canvas]

Bonsoir,

Dans le chapitre 12 (Texture mapping) du cours d'Infographie de László Szirmay, il y a 2 pages (pp342-343) consacrées au dépliage de maillage:

http://www.iit.bme.hu/~szirmay/book.html

avec le descriptif d'un algorithme.


Cordialement,

---
Canvas

[3Dgirl]

Bonjour!

j'avais dis que je reviendrais dans 2 jours mais ça m'a pris + de temps qu'il ne fallait

j'ai finalement développé l'algorithme ou je devais considérer à chaque fois deux triangles et déplier l'un par rapport à l'autre.

je m'explique: je prends un triangle au hasard T1, je cherche son voisin T2, je tourne T2 par rapport à T1 de manière à ce qu'ils soient dans le même plan . Je marque T1. Puis je repars de T2 et ainsi de suite.

le premier problème s'est posé au niveau de l'axe de rotation. finalement résolu, j'ai décidé que l'axe de rotation (qui est normalement le coté commun à T1 et T2), sera toujours supperposé à l'axe Y (il faut faire une simple similitude).

Il va de soi qu'il faut bien jouer avec les deux axes X et Z, et aussi sur le signe des angles pour que le coté commun soit sur Y et que les triangles respectent la translation et les rotations. Ca c'est fait. La similitude étant bijective, je n'ai pas de problème pour le retour.

Cependant, j'ai un tout autre problème.

Il n'ya rien qui définisse l'orientation de mes faces par rapport à mon axe Y.


Imaginez un cube avec de façon bien visible, la face de gauche, celle avant et celle de droite.

Imaginez que l'axe Y soit le coté commun entre la face avant et celle de droite. Pour déplier donc par rapport à la face avant, il faut faire une rotation de -90° de la face droite

si maintenant, par similitude, l'axe Y devient le coté commun entre la face de gauche et celle avant, il faudra tourner plutôt de +90° par rapport à Y.

Comment savoir donc le signe de l'angle de rotation sachant que il n'y a aucun repère à la base?

[Zavonen]

e premier problème s'est posé au niveau de l'axe de rotation. finalement résolu, j'ai décidé que l'axe de rotation (qui est normalement le coté commun à T1 et T2), sera toujours supperposé à l'axe Y (il faut faire une simple similitude).

Là je ne vois pas très bien ce que viennent faire ici les similitudes. Toutes les transformations en question sont des isométries (et même des rotations).
Rappel: Similitude=produit isométrie par homothétie.

[3Dgirl]

d'après mon cours de géométrie d'il y a très longtemps, une similitude = translation plus rotation

Il existe un repère XYZ (avec un X qui pointe vers la gauche, un Y montant et un Z entrant).

A la base mon objet n'est pas forcément en (0,0,0). Il se peut qu'aucun de mes vertices ne soit jamais (0,0,0).

Pour "roter" mes triangles, il faut bien un axe de rotation qui en l'occurence est quelconque puisqu'il dépend à chaque fois d'un coté commun à 2 triangles.

Raison pour laquelle, j'ai décidé que tous mes cotés communs seront toujours sur l'axe Y (ca aurait pu être X ou Z). Mais puis puisque mon objet peut se trouver n'importe où en 3D,

il faut bien que je fasse d'abord une translation de mes 2 triangles en 0,0,0 puis une rotation pour que le coté commun soit positionné en Y.

C'est tout ( d'où la similitude).

[3Dgirl]

Pourquoi choisir un axe de rotation comme Y?


tout simplement parce que je ne sais pas écrire de matrice de rotation à partir d'une droite qui ne soit pas (oY), (oX) ou (oZ).

Comme je connais les matrices de rotation basiques 3D et que je ne veux pas me compliquer la tache en faisant des multiplications de matrices (en plus il faut savoir comment les multiplier XZY ou ZXY etc...), j'ai choisi l'option similitude

[Zavonen]

Réglons tout de suite la question du vocabulaire:
http://fr.wikipedia.org/wiki/Similit...9om%C3%A9trie)
Tu es dans l'erreur pour la terminologie, mais cela n'a pas d'importance pour notre problème.
Tu sais faire un changement de repère au moyen d'une matrice de passage.
Alors où est le problème ?
A chaque fois que tu prends un nouveau triangle à aplatir tu commences par faire un changement de repère de sorte qu'un des axes soit l'axe de rotation pour avoir des formules simples.
Cet axe est le côté commun avec un autre triangle voisin. Comme je l'ai dit dans un post précédent, il existe DEUX rotations amenant le nouveau triangle dans le plan de son voisin, tu choisis celle pour laquelle les deux autres sommets sont de part et d'autre du côté commun. Il y a effectivement un petit calcul supplémentaire mais on ne peut l'éviter.

[3Dgirl]

Merci pour la terminologie. Je n'arrête pas de dire n'importe quoi depuis le début avec mon vocabulaire. Heureusement que tu m'as comprise.

Revenons-en au fait, j'ai compris ce que tu as dis et je suis tout à fait d'accord avec ta logique. Seulement, j'ai beau essayer de trouver des astuces en vain.

s'agissant d'une figure assez aisé comme un cube, c'est assez aisé. Car en fonction de la rotation de T2 par rapport à T1, il suffit juste de vérifier

soit qu'il n'y a pas de recouvrement entre les deux triangles ( en sachant le recouvrement peut vouloir dire que les les diagonales se confondent ou qu'elles se croisent). J'ai pris le cube parce que c'est plus facile de visualiser.

Mais est-ce que ça marcherait pour tout type de figures