Interpolation "linéaire" sur un point dans triangle (3D)

J'ai trois points (P1,P2,P3) en x,y,z qui forment un triangle. Chacun de ces points a une valeur qui lui est accordée. J'ai un 4e point (Pi) qui est situé dans le triangle (évidemment il est sur le plan de ce triangle). Je cherche à interpoler les trois valeurs sur le 4e point Pi.

J'ai fait beacoup de recherche mais je n'ai rien trouvé. Peut-être que je ne cherchais pas avec les bons termes mais bon...

J'ai implémenté un algorithme qui permet une interpolation mais elle a de très grande lacune de précision (l'erreur d'interpolation est assez sévère). La voici:

-Créer une droite passant par P3 et Pi -> P3_Pi
-Créer une droite passant par P1 et P2 -> P1_P2
-Trouver l'intersection de la droite P3_ Pi avec la droite P1_P2 -> Point Pi2
-Faire une interpolation linéaire entre les points P1 et P2 pour Pi2 -> valeur interpolée pour Pi2
-Faire une interpolation linéaire entre les points Pi2 et P3 pour Pi -> valeur interpolée pour Pi


Si quelqu'un a une meilleure suggestion je serais très reconnaissant!

bien le bonjour,

si tu ne cherches la valeur qu'un un seul point, la notion de barycentre te sera utile. On parle d'interpolaton (bi)linéaire lorsqu'il y a plusieurs points à définir.

Ta méthode fonctionne, il faut toutefois ne pas oublier que pour ton interpolation entre Pi2 et P3, le point Pi2 doit compter comme P1 + P2, il doit donc peser plus lourd que P3.

La méthode que je t'aurais proposée est quasiment la même : trouver la droite passant par Pi et parallèle à P1 elle coupe le triangle en A et B.
On peut donc faire une interpolation pour trouver A et B. Et ensuite, on interpole entre A et B pour trouver Pi.

Disons que de cette manière, on peut bien voir la notion de balayage. Il apparait clairement que 2 boucles imbriquée suffiront à parcourir tout ton triangle (interpolation bilinéaire)

Merci pour la réponse.

Citation:

---

Envoyé par khayyam90

Ta méthode fonctionne, il faut toutefois ne pas oublier que pour ton interpolation entre Pi2 et P3, le point Pi2 doit compter comme P1 + P2, il doit donc peser plus lourd que P3.

---

Je ne vois pas pourquoi la valeur de Pi2 devrait peser plus.

Sans avoir testé ta technique proposée, est-ce exact de dire que les mêmes résultats seraient obtenus? Si non, permettrait-elle d'avoir de meilleurs résultats?

Citation:

---

Envoyé par Vol

Je ne vois pas pourquoi la valeur de Pi2 devrait peser plus.

---

si on prend une approche purement mathématique, on regroupe 2 points en leur barycentre, il doit donc être pondéré de la somme des pondérations.

mais si on prend une approche plus intuitive, ... un simple exemple sera plus parlant.
considérons un triangle ABC, les médianes, et les points A' (resp B', resp C') en face de A (resp B, resp C).
G centre de gravité.

Il est évident que G est le point où chaque A,B,C pèse la même chose.
Regroupe A et B en C'. Fais peser C' et C. Dans ton cas ils pèsent la même chose et le centre de gravité doit se trouver au milieu, hors il n'en est rien. Fais peser C' comme A+B et tu retombes bien sur G.

Citation:

---

Envoyé par Vol

Sans avoir testé ta technique proposée, est-ce exact de dire que les mêmes résultats seraient obtenus? Si non, permettrait-elle d'avoir de meilleurs résultats?

---

Les résultats doivent être les mêmes. Ensuite, on peut pencher pour une méthode ou pour une autre (en terme de rapidité) selon ce que tu cherches à faire.

Si tu cherches à déterminer tous les points de ton triangle, il peut être coûteux de déterminer des intersections et si on truande bien, on peut dégager des cas où ces calculs se simplifient (droites parallèles aux côtés, droites horizontales, verticales ...)

Ce n'est qu'une autre méthode (très proche) pour arriver au même résultat.

Citation:

---

Envoyé par khayyam90

Citation:

---

Envoyé par Vol

Je ne vois pas pourquoi la valeur de Pi2 devrait peser plus.

---

si on prend une approche purement mathématique, on regroupe 2 points en leur barycentre, il doit donc être pondéré de la somme des pondérations.

mais si on prend une approche plus intuitive, ... un simple exemple sera plus parlant.
considérons un triangle ABC, les médianes, et les points A' (resp B', resp C') en face de A (resp B, resp C).
G centre de gravité.

Il est évident que G est le point où chaque A,B,C pèse la même chose.
Regroupe A et B en C'. Fais peser C' et C. Dans ton cas ils pèsent la même chose et le centre de gravité doit se trouver au milieu, hors il n'en est rien. Fais peser C' comme A+B et tu retombes bien sur G.

---

Si je comprends bien, ce sont mes formules pour caluler val_Pi et val_Pi2 qui tiennent comptent du poids des points P1 à P3 (voir "détails" de calculs). Vrai?

Je trouve les coordonnées de Pi2 en calculant l'intersection des droites.
La valeur interpolée de Pi2 selon P1 et P2 est val_Pi2:

Code:

---

val_Pi2 = val_P1 + (d1 * (val_P2 - val_P1)) / (d1+d2)

---

La valeur interpolée de Pi selon Pi2 et Pi3 est val_Pi (c'est la valeur recherchée):

Code:

---

val_Pi = val_Pi2 + (d3 * (val_P3 - val_Pi2)) / (d3+d4)

---

(d1 à d4 sont les distances entre les points sur la figure)
http://i67.photobucket.com/albums/h2...n_triangle.jpg

Citation:

---

Envoyé par khayyam90

Les résultats doivent être les mêmes. Ensuite, on peut pencher pour une méthode ou pour une autre (en terme de rapidité) selon ce que tu cherches à faire.

Si tu cherches à déterminer tous les points de ton triangle, il peut être coûteux de déterminer des intersections et si on truande bien, on peut dégager des cas où ces calculs se simplifient (droites parallèles aux côtés, droites horizontales, verticales ...)

Ce n'est qu'une autre méthode (très proche) pour arriver au même résultat.

---

Je n'ai qu'un seul points par triangle qui nécessite une valeur calculée par interpolation (ce point peut-être n'importe où dans le triangle). Par contre, la rapidité de calcul est très importante. Pourrions-nous affirmer que ma méthode serait plus rapide puisqu'elle nécessite seulement le calcul d'une intersection contrairement à la tienne qui en nécessite deux?

Je me trompes peut-être, car tout ça c'est bien loin, mais il me semble qu'on peut travailler avec des vecteurs:
Il existe un triplet (a, b, c) tel que

Code:

---

a * vect(Pi,P1) + b * vect(Pi, P2) + c * vect(Pi,P3) = 0

---

A partir de là, on doit pouvoir décliner avec les poids de P1, P2, P3 :

Code:

---

a*poids(P1)*vect(Pi,P1) + b*poids(P2)*vect(Pi, P2)+c*poids(P3)*vect(Pi,P3)=0

---

Qu'en pensez-vous ?

Une méthode consiste à determiner l'équation cartésienne du plan qui passe par les 3 points (la 3ème cordonnée étant la valeur affectée à chaque point).
On determine ainsi facilement et rapidement la valeur interpolée pour n'importe quel point dans le triangle.

J'avais déjà répondu à une question similaire :

http://www.developpez.net/forums/sho...6&postcount=12

Trap-D a raison, c'est une bonne méthode... Il faut chercher du côté des coordonnées barycentriques. En gros, c'est se placer dans un repère propre au triangle :
*********-->** -->
p(s,t)= A + sAB + tAC
ou plutôt :
*********-->**-->**-->
p(s,t,w)= wOA + sOB + tOC avec w = 1-(s+t)
tu interpoles donc tes valeurs aux sommets avec les coefficients de pondération s,t,w pour B, C et A et c'est bon... (c'est ce qui est utilisé pour l'évaluation de la normale à un triangle pour le modèle d'éclairage de Gouraud)

voili voilu :mrgreen:

Désolé, je n'ai pas eu la chance de répondre plus tôt. Merci pour toutes les suggestions. J'ai finalement choisi une méthode dérivée de celle indiquée par larnicebafteur.

Citation:

---

Envoyé par larnicebafteur

Une méthode consiste à determiner l'équation cartésienne du plan qui passe par les 3 points (la 3ème cordonnée étant la valeur affectée à chaque point).
On determine ainsi facilement et rapidement la valeur interpolée pour n'importe quel point dans le triangle.

J'avais déjà répondu à une question similaire :

http://www.developpez.net/forums/sho...6&postcount=12

---

Voici une image qui représente la technique que j'ai finalement choisie:
http://i67.photobucket.com/albums/h2...lation3pts.jpg

Les 3 points 'val P..' sont obtenus en faisant une translation de la valeur (poids) des points P1 à P3 selon la normale (les lignes pointillées) au plan P1P2P3. On détermine ensuite l'intersection (valPp) entre le plan formé par valP1-valP2-valP3 et la droite normale au plan P1P2P3 et passant par Pp. La distance entre Pp et valPp correspond à la valeur interpolée qui est recherchée.

J'ai comparé cette méthode avec ma méthode initiale ainsi que celle proposée par khayyam90 et des différences maximales de 0.5% pour les valeurs interpolées sont observées. Donc, peu importe la méthode utilisée, les résultats sont valides et très similaires. Par contre, en terme de temps d'exécution, la dernière méthode utilisée (celle expliquée dans ce message) est quelque peu plus rapide. En fait, moins de 1% plus rapide, ce qui est négligeable.