Discussion :

[Earthwormjim]

Bonjour,

voici un bout de code blitzmax (c'est du basic, donc compréhensible assez facilement) permettant d'interpoler des couleurs (ou n'importe quelles autres valeurs) sur toute la surface d'un quadrangle
le but ici est de ne pas se retrouver dans le cas d'une interpolation telle qu'elle est faite en opengl, où l'on voit la diagonale (car seuls les triangles sont gérés) mais bien d'avoir les 4 coins évalués pour définir la couleur à un point donné sur le quad.

cette fonction est executée pour chaque pixel tracé à l'écran, on lui passe les coordonnées du point à afficher ainsi que les 4 coins du quadrangle

je cherche des idées pour optimiser et accélérer ce code.
si vous voyez aussi une solution pour étendre cette méthode à un polygone à n cotés, je suis aussi preneur

un executable est dispo ici pour voir le résultat : http://earthwormjim.free.fr/stock/quadfactor.bmax.zip

merci d'avance pour votre aide

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
Function GetQuadValue:Float[](P:TPoint,A:TPoint,B:TPoint,C:TPoint,D:TPoint) 
 
	' longueur de chaque bord du quad 
	Local AB:Float = distance(A,B) 
	Local BC:Float = distance(B,C) 
	Local CD:Float = distance(C,D) 
	Local DA:Float = distance(D,A) 
 
	' aires de triangles formés par les bords et le point à tester 
	Local aAB:Float = aire(A,B,P) 
	Local aBC:Float = aire(B,C,P) 
	Local aCD:Float = aire(C,D,P) 
	Local aDA:Float = aire(D,A,P) 
 
	' influences des bords sur le point P 
	Local ratioAB:Float = 1 - (aAB / (aAB + aCD)) 
	Local ratioBC:Float = 1 - (aBC / (aBC + aDA)) 
	Local ratioCD:Float = 1 - (aCD / (aAB + aCD)) 
	Local ratioDA:Float = 1 - (aDA / (aBC + aDA)) 
 
	' projection du point sur chaque bord 
	Local P1:TPoint = New TPoint 
	P1.x = A.x * ratioAB + D.x * ratioCD 
	P1.y = A.y * ratioAB + D.y * ratioCD 
 
	Local P2:TPoint = New TPoint 
	P2.x = B.x * ratioAB + C.x * ratioCD 
	P2.y = B.y * ratioAB + C.y * ratioCD 
 
	Local P3:TPoint = New TPoint 
	P3.x = A.x * ratioDA + B.x * ratioBC 
	P3.y = A.y * ratioDA + B.y * ratioBC 
 
	Local P4:TPoint = New TPoint 
	P4.x = D.x * ratioDA + C.x * ratioBC 
	P4.y = D.y * ratioDA + C.y * ratioBC 
 
 
	' distances entre le point testé et les points projetés sur les bords 
	Local P1P:Float = distance(P1,P) 
	Local P2P:Float = distance(P2,P) 
	Local P3P:Float = distance(P3,P) 
	Local P4P:Float = distance(P4,P) 
 
	Local influence:Float[5] 
 
	' calcul final de l'influence de chaque coin 
	Local r1:Float = 1-(distance(P1,A) / DA) 
	Local r2:Float = 1-(distance(P3,A) / AB) 
	influence[1]=((r1 * (1-(P1P / (P1P+P2P))) + r2 * (1-(P3P / (P3P+P4P))))/2.0) 
 
	r1 = 1-(distance(P2,B) / BC) 
	r2 = 1-(distance(P3,B) / AB) 
	influence[2]=((r1 * (1-(P2P / (P1P+P2P))) + r2 * (1-(P3P / (P3P+P4P))))/2.0) 
 
	r1 = 1-(distance(P2,C) / BC) 
	r2 = 1-(distance(P4,C) / CD) 
	influence[3]=((r1 * (1-(P2P / (P1P+P2P))) + r2 * (1-(P4P / (P3P+P4P))))/2.0) 
 
	r1 = 1-(distance(P1,D) / DA) 
	r2 = 1-(distance(P4,D) / CD) 
	influence[4]=((r1 * (1-(P1P / (P1P+P2P))) + r2 * (1-(P4P / (P3P+P4P))))/2.0) 
 
'la fonction retourne la tableau d'influence pour chaque point du quadrangle
	Return influence 
 
EndFunction

[souviron34]

je cherche des idées pour optimiser et accélérer ce code.

oui

faire simplement une interpolation bi-linéaire...

si vous voyez aussi une solution pour étendre cette méthode à un polygone à n cotés, je suis aussi preneur

impossible. Une interpolation n'a aucun sens entre plus de 4 points. C'est soit 3 soit 4..

[pseudocode]

"Generalized Barycentric Coordinates on Irregular Polygons"

[Earthwormjim]

"Generalized Barycentric Coordinates on Irregular Polygons"

Exactement ce que je cherchais !
merci 12 milliards de fois

EDIT : pour simplifier la recherche aux autres : http://www.geometry.caltech.edu/pubs/MHBD02.pdf

impossible. Une interpolation n'a aucun sens entre plus de 4 points. C'est soit 3 soit 4..

donc si, c'est possible

[pseudocode]

Exactement ce que je cherchais !
merci 12 milliards de fois

je vous en prie.

donc si, c'est possible

Sur des polygones non-convexes, c'est vrai que ca n'a pas vraiment de sens, mais le papier en question donne une assez bonne "impression" visuelle.

[Earthwormjim]

ouep, dans le même esprit, j'avais trouvé ça :

http://artis.imag.fr/Publications/2008/OBWBTS08/

[pseudocode]

ouep, dans le même esprit, j'avais trouvé ça :

http://artis.imag.fr/Publications/2008/OBWBTS08/

Joli.

Mais là on rentre dans les techniques de shading plutot complexes, assez éloignées de l'interpolation façon gouraud.

[Earthwormjim]

Joli.

Mais là on rentre dans les techniques de shading plutot complexes, assez éloignées de l'interpolation façon gouraud.

oui c'est bien plus compliqué, mais ça permet surtout de gérer le cas des polygones concaves
j'ai téléchargé leur outil de démo et j'ai tracé ça :

faut que je vérifie si c'est bien cohérent, mais là sans tester plus en avant ça me semble correct comme résultat.

bon apres, faut dépioter leur algo, si je parviens à le trouver expliqué de façon assez claire pour mon petit cerveau... pour le moment j'ai mon code qui tourne sur les polygones convexes et je suis déjà très content

[pseudocode]

bon apres, faut dépioter leur algo, si je parviens à le trouver expliqué de façon assez claire pour mon petit cerveau... pour le moment j'ai mon code qui tourne sur les polygones convexes et je suis déjà très content

L'essentiel c'est que ton code fasse ce que tu veux.

Pour leur algo, j'ai lu le papier en diagonal et ca m'a l'air d'etre une méthode de diffusion. La partie ardue c'est la résolution du système en temps-réel par le GPU .

[Earthwormjim]

L'essentiel c'est que ton code fasse ce que tu veux.

yes !

sinon je viens de faire une comparaison approximative entre les deux méthodes sur un quadrangle, voici ce que ça donne :


comme on peut le voir clairement sur la différence, les interpolations ne concordent pas, même si visuellement les deux semblent corrects.

faudra que je tente de coder ça quand j'aurais le temps

EDIT : non finallement je pourrais pas le coder, j'ai relu en détails le pdf, c'est hors de la portée de mon cortex mou

EDIT 2 : Woohoo, c'est la fête ! http://www2.in.tu-clausthal.de/~hormann/barycentric/
y'en a plein dans tous les sens ^^

et hop, la gestion des polygones concaves --> http://www2.in.tu-clausthal.de/~horm...n.2005.BCF.pdf
j'ai un peu de mal à capter le pseudo-code sur la page 9 de ce pdf, quelqu'un pourrait me le clarifier un peu svp ?
J'ai du mal à voir où finissent les boucles, et certaines notations ne sont pas claires pour moi (je n'ai pas eu une formation de maths très poussée )

merci d'avance

[pseudocode]

et hop, la gestion des polygones concaves --> http://www2.in.tu-clausthal.de/~horm...n.2005.BCF.pdf
j'ai un peu de mal à capter le pseudo-code sur la page 9 de ce pdf, quelqu'un pourrait me le clarifier un peu svp ?
J'ai du mal à voir où finissent les boucles, et certaines notations ne sont pas claires pour moi (je n'ai pas eu une formation de maths très poussée )

L'interieur des structures for/if est indenté. Donc quand l'indentation revient au niveau de la déclaration du for/if, c'est que c'est qu'on est sorti de la structure.

De plus, je pense que:
* det(a,b) représente le determinant
* <a,b> représente le produit scalaire

mais je n'ai pas testé leur algo.

[Earthwormjim]

ok merci pour la réponse, je vais tester ça

[Earthwormjim]

Hum, je sèche un peu là, je capte pas bien à quel endroit dans la fonction se situe le point à tester, là il semblerait que seule la liste des points du polygones est traitée... je suis passé à coté de quoi ?

[pseudocode]

Hum, je sèche un peu là, je capte pas bien à quel endroit dans la fonction se situe le point à tester, là il semblerait que seule la liste des points du polygones est traitée... je suis passé à coté de quoi ?

je pense que "V" représente le vertex (le point) à tester et les "Vi" représentent les vertex (les sommets) du polygones.

[Earthwormjim]

je pense que "V" représente le vertex (le point) à tester et les "Vi" représentent les vertex (les sommets) du polygones.

yes merci ^^
je m'étais résolu à cette solution de mon coté, merci de confirmer

et à priori, c'est le même cas pour f et fi qui sont deux variables différentes...

[pseudocode]

yes merci ^^
je m'étais résolu à cette solution de mon coté, merci de confirmer

et à priori, c'est le même cas pour f et fi qui sont deux variables différentes...

"Fi" est la valeur (la couleur) associée au vertex "Vi"

"F" est la valeur du vertex "v", celle qu'on cherche a calculer.

[Earthwormjim]

bon, dernière question (j'espère) : comment calculer le déterminant de deux vecteurs 3D ? j'ai trouvé en 2D, mais je capte pas bien comment le faire avec une dimension de plus

[pseudocode]

bon, dernière question (j'espère) : comment calculer le déterminant de deux vecteurs 3D ? j'ai trouvé en 2D, mais je capte pas bien comment le faire avec une dimension de plus

heu... pourquoi as tu besoin de calculer le déterminant de deux vecteurs 3D ?

C'est de l'interpolation de points sur une surface, donc des vecteurs 2D.

[Earthwormjim]

heu... pourquoi as tu besoin de calculer le déterminant de deux vecteurs 3D ?

C'est de l'interpolation de points sur une surface, donc des vecteurs 2D.

oui mais là je bosse avec des objets 3D, et donc je récupère les coordonnées de mes vertices pour les balancer direct dans la fonction

[Earthwormjim]

voici où j'en suis :
mes vecteurs sont a et b

pour le calcul a.x*b.y - a.y*b.x


pour la version 3d, j'ai ça, mais ça va pas encore :
(a.y*b.x - b.y*a.z) + (a.x*b.z - b.x*a.z) - (a.x*b.y - b.x*a.y)


pour info, là le z des deux vecteurs est à 0 seuls x et y sont renseignés