Discussion :

[PaM...]

Bonjour,

J'ai posé quelque question sur le forum matlab (ici) et on m'a conseillé de venir posé mon problème ici.

Alors voila je possède les coordonné en X,Y,Z de nombreux point appartenant à une surface (dans mon cas c'est du cartilage), j'aimerais pouvoir reconstituer cette surface.

Image matlab des points:


Mon but a terme n'est pas l'affichage mais de pouvoir calculer la distance minimal entre un point donné et cette surface ainsi que les point d'intersection entre cette surface et une droite donnée.

Je dois avouer que je n'ai pas trop d'idée de comment faire ca, tout conseil est le bienvenue

Merci d'avance

[PRomu@ld]

Une idée (mais elle vaut ce qu'elle vaut) :

-> Triangule ta surface
-> Utilise une structure accélératrice pour gérer la surface (quad-tree,bsp,...)
-> Utilise la triangulation pour effectuer tes calculs d'intersection.

Pour ce qui est de distance minimale, tu peux toujours jouer le bourin et faire une sorte de tri sur les distances à un point donné (en N log N donc).

[FR119492]

Salut!
Par rapport à un repère cartésien Oxyz, il y a au moins deux manières pour définir une surface par une expression analytique:

• En exprimant une des coordonnées en fonction des deux autres, par exemple z=F(x,y) .
• Par une équation paramétrique G(x,y,z)=0

La première présente l'inconvénient que, pour certaines paires (x,y), la valeur de z peut ne pas être unique. Tes données correspondent-elles bien à la seconde?

Triangule ta surface

Il va probablement être difficile de décider quels points on relie pour chaque triangle. Si 4 points sont, par hasard, les sommets d'un carré, par quelle diagonale le coupera-t-on?

Dernière question (pour le moment): Est-ce que, par hasard, la projection de tes points sur le plan Oxy serait les noeuds d'une grille à maille rectangulaire, ce qui faciliterait beaucoup les choses?
Jean-Marc Blanc

[vdaanen]

Bonjour,

il existe de nombreuses méthodes pour reconstruire une surface a partir de points. En général, on trouve pas mal de références avec "Surface reconstruction unorganised points" dans Google.

J'ai implémentée (il y a quelques temps), une methode basée sur les Radial Basis Functions et ma foi, ca donnait pas trop mal .... Mais il y en a d'autres, a toi de voir celle(s) qui donnera(ont) les meilleurs resultats....

Ensuite, pour calculer la distance d'un point a ton maillage, il y a deja des reponses au dessus

V

[PaM...]

@PRomu@ld
J'y avais pensé mais je voyais pas comment faire pour la distance minimal.
D'ailleurs je n'ai pas compris ce que tu propose pour ca.
Peux tu expliquer un peu plus

@FR119492

• En exprimant une des coordonnées en fonction des deux autres, par exemple z=F(x,y) .
• Par une équation paramétrique G(x,y,z)=0

La première présente l'inconvénient que, pour certaines paires (x,y), la valeur de z peut ne pas être unique. Tes données correspondent-elles bien à la seconde?

La premiére c'est sur que non, la seconde je pense oui

Dernière question (pour le moment): Est-ce que, par hasard, la projection de tes points sur le plan Oxy serait les noeuds d'une grille à maille rectangulaire, ce qui faciliterait beaucoup les choses?
Jean-Marc Blanc

Non mais leur projection sur un cylindre oui (je vois pas trop comment cela peux m'aider)

@vdaanen
Du coup ma question devient: "quelles méthodes utiliser afin de faciliter les calculs que je veux faire pour la suite"
Je vais regarder mais la plupart des algo que je trouve sont quand même assez baleze pour mon niveau

Merci a vous

[FR119492]

Salut!

je vois pas trop comment cela peux m'aider

t'en fais pas, ça va venir!

Non mais leur projection sur un cylindre oui

Si tu l'avais dit tout de suite! Car ça simplifie tout si, au lieu de donner tes points en coordonnées cartésiennes (x, y, z), tu les donnais en coordonnées cylindriques (rho, phi, z).

Je résume pour m'assurer que j'ai bien compris ton problème:
Tu as un certain nombre n_phi de valeurs de phi et un certain nombre n_z de valeurs de z, ce qui te définir (n_phi)*(n_z) points sur un cylindre et tu as mesuré la valeur rho(phi,z) correspondant à chacun de ces points. Tu veux dessiner une surface passant par tous les points de coordonnées (rho, phi, z).

Jean-Marc Blanc

[PaM...]

Oui c'est ca
(enfin presque car en fait c'est pas vraiment un cylindre puisque sa section est une ellipse, mais je pense que ca revient au même)

Tu veux dessiner une surface passant par tous les points de coordonnées (rho, phi, z).

C'est pas vraiment dessiner le plus important, ce serait plutot pouvoir facilement trouver:

• le point d'intersection avec une doite
• la distance minimal avec un point données

[FR119492]

Salut!

sa section est une ellipse

Alors, il y a les coordonnées du cylindre elliptique, telles que définies dans Wikipedia en anglais, dans "Compléments de mathématiques à l'usage des ingénieurs" de A. Angot et dans Abramowitz et Stegun.
Jean-Marc Blanc

[PRomu@ld]

J'y avais pensé mais je voyais pas comment faire pour la distance minimal.
D'ailleurs je n'ai pas compris ce que tu propose pour ca.
Peux tu expliquer un peu plus

C'est la méthode brutale (ou de non intelligence) :

Tu calcules la distance (au carré) entre ton point et chacun des points de ta surface. Tu tries et tu récupère les points les plus proches.

Le mieux et (sans doute le plus efficace) est d'utiliser un kd-tree équilibré pour chercher les n points les plus proches (ce qui se fait en photon mapping par ex).

[PaM...]

je vois pas trop comment cela peux m'aider

t'en fais pas, ça va venir!

ca vient pas vraiment...
si tu pouvais développer un peu plus

merci

[pseudocode]

Le mieux et (sans doute le plus efficace) est d'utiliser un kd-tree équilibré pour chercher les n points les plus proches (ce qui se fait en photon mapping par ex).

Un simple octree devrait déjà beaucoup améliorer les choses.

[PRomu@ld]

Un simple octree devrait déjà beaucoup améliorer les choses.

Ah oui, sans conteste, j'ai dis kd-tree comme ça (enfin pas tout à fait )