Discussion :

[Kevinyaya]

Voilà, je dois projeter une courbe sur un maillage 3D (plus petite distance au maillage). Mais ma structure de données est un tableau de points et un tableau de faces (avec les indices de points). Si je dois pour chaque point de la courbe, m'amuser à parcourir tous les polygones, sélectionner ceux qui ont une chance d'avoir le point à l'intérieur, puis enfin sélectionner le plus proche, ça risque de pas être tout à fait temps réel. Mon encadrant m'a parlé de changer la structure, et m'a donné plusieurs pistes: winged edges, octrees, tables de hachage... Je ne trouve pas grand chose sur la question et je me demandais si vous pouviez m'aider voire me donner des liens où je pourrais trouver plus d'amples informations sur des algorithmes de projection d'un point sur un maillage. Merci,
Kevin

[dazz_x]

je pense que s'il te parle de winged edges, c'est plus pour t'inviter à changer de structure de données pour ton maillage.... On l'appelle aussi la structure halfedge.
Une halfedge est un objet représentant un arc orienté entre deux sommets

o--------------- o
| \*********** |
| *****f****** | h0
| h3********** |
| ************|/
v1 ****h1***** v2
o '-------------, o
******h2


(les apostrophes sont des demies-flèches). l'halfedge h1 doit posseder cinq pointeurs :
un sur v1 h1->sommet
un sur h2 h1->opposite
un sur la prochaine halfedge h3 h1->next
un sur la précedente halfedge h0 h1->prev
un sur la face f h1->face

avec tout ça, une circulation sur une face est évidente, il suffit de faire des h1->next->next... et pour sauter sur une autre face, il faut faire un h1->opposite.
Maintenant, ton maillage peut être décrit par un tableau de face où chaque face est seulement décrite par sa preière arête (arbitraire lors de la construction).
Les algos de recherches sont beaucoup plus rapide, puisque cette structure te permet de te cantonner à une zone précise du maillage. Pour plus d'infos, tu peux aller sur , il y a plein d'infos sur tout ça (va voir même dans scholar.google.com pour rechercher des publis sur des algos de recherche en maillage).