Calculer la position d'un point sur un polygone ?

Bonjour,
désolé pour le titre pas très explicite, voila j'ai un polygone (3 points A B et C dans l'espace 3d) et un point (P) sur ce polygone. Donc quatre points au total.
Le polygone est texturé et possède donc pour chaque point 2 coordonnées de texture (u v).
Je cherche les coordonnées de texture du point P.

Ce que je me suis dit c'est que la position de P correspond à une part de A une part de B et une part de C (Px=k1*Ax+k2*Bx+k3*Cx et Py=k1*Ay...) et que donc ce sera pareil pour les coordonnées de texture et qu'en calculant k1, k2 et k3 je pourrez simplement appliquer l'equation Pu=k1*Au+k2*Bu+k3*Cu pour obtenir mes coordonnées de texture.

Le problème que j'ai c'est pour résoudre l'équation, je ne suis pas très fort, c'est là que j'attends vos lumières.

Merci

Salut,

Citation:

---

Envoyé par supergrey

Le problème que j'ai c'est pour résoudre l'équation, je ne suis pas très fort, c'est là que j'attends vos lumières.

---

Résolution d'un système de trois équations linéaires à 3 inconnues:

Code:

---

1 2 3 4

| Ax Bx Cx | |k1| |Px| | Ay By Cy |*|k2|=|Py| | Az Bz Cz | |k3| |Pz|

---

Librairie déjà existante, ou pivot de gauss, ou inversion de matrice, et tu as tes 3 coefs k1, k2 et k3.

Le pivot de gauss ça me semble compliqué pour que ça s'applique à tous les cas, donc les matrices ça me tenterait bien mais est-ce que ça existe en c++ ?

Citation:

---

Envoyé par supergrey

Le pivot de gauss ça me semble compliqué pour que ça s'applique à tous les cas

---

Gnein?
Compliqué? On apprend ça en seconde... il n'y a guère plus simple...
Et si il y a un cas où ça ne s'applique pas ici, c'est que ton triangle est dégénéré .

Citation:

---

Envoyé par supergrey

donc les matrices ça me tenterait bien mais est-ce que ça existe en c++ ?

---

Roh je pense que oui...

Ouai bon faut pas m'en vouloir je suis sous antibiotiques :aie:
Alors je me lance:

Code:

---

1 2 3 4

Px=K*Ax+L*Bx+M*Cx Py=K*Ay+L*By+M*Cy Pz=K*Az+L*Bz+M*Cz

---

Eliminons les K:

Code:

---

1 2 3 4 5

PxAy=KAxAy+LBxAy+MCxAy PyAx=KAyAx+LByAx+MCyAx => PxAy-PyAx=L(BxAy-ByAx)+M(CxAy-CyAx)   PzAx=KAzAx+LBzAx+MCzAx => PxAz-PzAx=L(BxAz-BzAx)+M(CxAz-CzAx)

---

J'ai bon ? Passons aux L:

Code:

---

1 2 3 4 5

(PxAy-PyAx)(BxAz-BzAx)=L(BxAy-ByAx)(BxAz-BzAx)+M(CxAy-CyAx)(BxAz-BzAx) (PxAz-PzAx)(BxAy-ByAx)=L(BxAz-BzAx)(BxAy-ByAx)+M(CxAz-CzAx)(BxAy-ByAx)   (PxAy-PyAx)(BxAz-BzAx)-(PxAz-PzAx)(BxAy-ByAx)=M(CxAy-CyAx)(BxAz-BzAx)-M(CxAz-CzAx)(BxAy-ByAx)

---

Donc on a

Code:

---

1 2	M=[(PxAy-PyAx)(BxAz-BzAx)-(PxAz-PzAx)(BxAy-ByAx)]/[(CxAy-CyAx)(BxAz-BzAx)-(CxAz-CzAx)(BxAy-ByAx)]

---

Et la je fais une pause parceque je ne suis pas du tout sûr d'arriver à simplifier tout ça... si c'est juste...

Et Dieu créa les Coordonnées Barycentriques Homogènes appliquées aux polygones.

http://www2.in.tu-clausthal.de/~horm...n.2005.BCF.pdf

:mrgreen:

Ouai ça à l'air cool les coordonnées barycentriques... mais je vais poursuivre mon équation:

Code:

---

1 2 3 4 5 6 7 8

M=[(PxAy-PyAx)(BxAz-BzAx)-(PxAz-PzAx)(BxAy-ByAx)]/[(CxAy-CyAx)(BxAz-BzAx)-(CxAz-CzAx)(BxAy-ByAx)]   [(PxAy-PyAx)(BxAz-BzAx)-(PxAz-PzAx)(BxAy-ByAx)]= -PxAyBzAx-PyAxBxAz+PyAxBzAx + PxAzByAx+PzAxBxAy-PzAxByAx   [(CxAy-CyAx)(BxAz-BzAx)-(CxAz-CzAx)(BxAy-ByAx)]= -CxAyBzAx-CyAxBxAz+CyAxBzAx + CxAzByAx+CzAxBxAy-CzAxByAx

---

Ce qui me donne

Code:

---

1 2	M=(-PxAyBzAx-PyAxBxAz+PyAxBzAx + PxAzByAx+PzAxBxAy-PzAxByAx) / (-CxAyBzAx-CyAxBxAz+CyAxBzAx + CxAzByAx+CzAxBxAy-CzAxByAx)

---

Et je suis meme pas sur que ça soit juste et je n'ai que M, alors celui qui disait que c'était simple, merci mais pas pour moi :(

Sinon, le calcul des coordonnées barycentriques d'un triangle ça tient en 4 lignes... Moi je dis ça, je dis rien. :roll:

Moi je veux bien mais je ne suis pas capable de sortir ces 4 délicieuses lignes du fichier pdf que tu as gentiment proposé, mais merci de m'en faire renifler l'odeur.

:mrgreen:

• "vertex" est un tableau de 3 points représentant les sommets du triangle
• "p" est le point dont on cherche les coordonnées barycentriques
• w0,w1,w2 sont les 3 coordonnées barycentriques

Code:

---

1 2 3 4 5 6

double area = (vertex[1].x - vertex[0].x) * (vertex[2].y - vertex[0].y) - (vertex[2].x - vertex[0].x) * (vertex[1].y - vertex[0].y); double w0 = ((vertex[1].x - p.x) * (vertex[2].y - p.y) - (vertex[2].x - p.x) * (vertex[1].y - p.y)) / area; double w1 = ((vertex[2].x - p.x) * (vertex[0].y - p.y) - (vertex[0].x - p.x) * (vertex[2].y - p.y)) / area; //double w2 = ((vertex[0].x - p.x) * (vertex[1].y - p.y) - (vertex[1].x - p.x) * (vertex[0].y - p.y)) / area; double w2 = 1.0-w0-w1;

---

NB: si l'un des wi est négatif, alors c'est que le point "p" est en dehors du triangle.

Merci... c'est bizarre comme calcul, je ne vois pas trop comment le modifier pour 3 dimensions, si ce n'ai pas trop demander :lol:
Bon sinon une fois que j'ai w1 w2 et w3, est-ce que par le plus grand des hasards il suffit de multiplier chaque coordonnées par son "w" et de les additionner ? Serait-ce si simple ?

Citation:

---

Envoyé par supergrey

Et la je fais une pause parceque je ne suis pas du tout sûr d'arriver à simplifier tout ça... si c'est juste...

---

Euh... oui non mais si tu essayes de trouver les formules littérales à la main, ça ne sert plus à rien de programmer! :D

Programme le ton algo de pivot de gauss...

Citation:

---

Programme le ton algo de pivot de gauss

---

Ben je sais pas c'est bien ce que je fais, je ne vois pas trop ce que je peux faire d'autre ?? La programmation ça invente rien (ou on me l'a caché :)

Le pire c'est que quelqu'un a forcément déjà résolu cette équation, un matheux le ferai en 5 minutes... mais pas moi !

Citation:

---

Envoyé par supergrey

Ben je sais pas c'est bien ce que je fais

---

Ben non, là tu es en train de déterminer les équations qui donnent directement les valeurs des trois coeffs.
Prépare plutôt l'algo qui va faire passer ta matrice carrée à une matrice triangulaire, et ensuite la détermination des trois coeff à partir de la matrice triangulaire et du vecteur solution.

Mais ne fais pas le calcul manuellement pour avoir directement l'expression des coeffs...

Citation:

---

Envoyé par supergrey

La programmation ça invente rien (ou on me l'a caché :)

---

Non, ça fait juste bosser la machine à ta place. C'est moins fatiguant ;)

Citation:

---

Envoyé par supergrey

Le pire c'est que quelqu'un a forcément déjà résolu cette équation, un matheux le ferai en 5 minutes... mais pas moi !

---

Roh oui... mais bon, le matheux passe 15 minutes à trouver l'équation, alors que le programmeur se fait une classe "matrice" et une procédure "inversion" ou "gauss" et c'est résolu! :D

Bon, ok, en 5 minutes, et je ne suis pas un matheux:

système:

Code:

---

1 2 3 4

| a b c | | k1 | | u | | d e f |*| k2 |=| v | | g h i | | k3 | | w |

---

solution (si je ne me suis pas planté en recopiant):

k3=[(aw-ug)*(ae-bd)-(av-ud)*(ah-bg)]/[(ai-cg)*(ae-bd)-(ah-bg)*(af-dc)]
k2=[(av-ud)-k3*(af-dc)]/(ae-bd)
k1=(u-b*k2-c*k3)/a

en se débrouillant pour que les dénominateurs ne soient pas nuls ;)

Citation:

---

Envoyé par supergrey

Merci... c'est bizarre comme calcul, je ne vois pas trop comment le modifier pour 3 dimensions, si ce n'ai pas trop demander :lol:

---

Ce sont des divisions de produit vectoriels.

Ca revient a faire le ratio de la surface des petits triangles (ayant le point p comme sommet) avec la surface du grand triangle (de départ).

Citation:

---

Bon sinon une fois que j'ai w1 w2 et w3, est-ce que par le plus grand des hasards il suffit de multiplier chaque coordonnées par son "w" et de les additionner ? Serait-ce si simple ?

---

oui, c'est ca.

OK, merci à tous, finalement j'ai eu la réponse sur yahoo Q/R (sans vouloir faire de pub), c'est en utilisant le calcul des déterminants de la matrice, c'est plus simple pour moi, voila donc mon calcul final:

Code:

---

1 2 3 4 5 6 7 8 9

float da=A.x*(B.y*C.z-B.z*C.y)-A.y*(B.x*C.z-B.z*C.x)+A.z*(B.x*C.y-B.y*C.x); float dk=P.x*(B.y*C.z-B.z*C.y)-P.y*(B.x*C.z-B.z*C.x)+P.z*(B.x*C.y-B.y*C.x); float dl=A.x*(P.y*C.z-P.z*C.y)-A.y*(P.x*C.z-P.z*C.x)+A.z*(P.x*C.y-P.y*C.x); float dm=A.x*(B.y*P.z-B.z*P.y)-A.y*(B.x*P.z-B.z*P.x)+A.z*(B.x*P.y-B.y*P.x);   float k=dk/da; float l=dl/da; float m=dm/da;

---