Point d'intersection Ligne/Sphère

En GFA-Basic pour Windows
Page d'accueil


Très utile pour faire du ray-tracing, mais veillez à optimiser le code car je ne l'ai pas fait dans le seul soucis de la lisibilité du programme ! Vous pouvez par exemple mettre a = 1 si vous êtes certains que le vecteur est normalisé à 1, ou carrément supprimer son utilisation dans la formule de v .
Il s'agit de la même formule que l'intersection d'une ligne et d'un cercle en 2D : VoirIntersection ligne/cercle
Pour bien utiliser cette procédure il faut transmettre le vecteur (x1,y1,z1)(x2,y2,z2) et les coordonnées de la sphère (x3,y3,z3) de rayon r.
Le Vecteur doit être normalisé sur une 1 unité, c'est à dire que la distance entre le point (x1,y1,z1) et le point (x2,y2,z2) doit être égale à 1.
Pour normaliser un vecteur utilisez cette procédure :

- Normaliser un vecteur -
Listing GFA-Basic pour Windows, Faites un copier-coller
ou cliquez ici pour télécharger le source normvect.lst
PROCEDURE Normalise_Vecteur(VAR ox,oy,oz,dx,dy,dz)
 LOCAL lx,ly,lz,h
 lx = dx - ox
 ly = dy - oy
 lz = dz - oz
 h = SQR(lx ^ 2 + ly ^ 2 + lz ^ 2)
 IF h > 0
   dx = ox + lx / h
   dy = oy + ly / h
   dz = oz + lz / h
 ENDIF
RETURN

- Savoir si une ligne traverse une sphère et connaitre les coordonées du point d'intersection -
Listing GFA-Basic pour Windows, Faites un copier-coller
ou cliquez ici pour télécharger vecinsph.lst
PROCEDURE VectorInSphere(x1,y1,z1,x2,y2,z2,x3,y3,z3,r,VAR VERIF%,ix,iy,iz)
 ' Procêdure êcrite par Nicolas Rey - 6 Dêcembre 2002
 ' http://scalion.free.fr
 ' VERIF% prend la valeur TRUE (-1) si il y á intersection
 ' ix,iy et iz retournant alors les coordonnêes du point d'intersection (sinon valeurs inchangêes)
 LOCAL a,b,c,v,U
 a = (x2 - x1) ^ 2 + (y2 - y1) ^ 2 + (z2 - z1) ^ 2
 b = 2 * ( (x2 - x1) * (x1 - x3) + (y2 - y1) * (y1 - y3) + (z2 - z1) * (z1 - z3))
 c = x3 ^ 2 + y3 ^ 2 + z3 ^ 2 + x1 ^ 2 + y1 ^ 2 + z1 ^ 2 - 2 * (x3 * x1 + y3 * y1 + z3 * z1 ) - r ^ 2
 v = b ^ 2 - 4 * a * c
 IF v > 0
   VERIF% = TRUE
   U = (-b - SQR(v)) / (2 * a)
   ix = x1 + U * (x2 - x1),iy = y1 + U * (y2 - y1),iz = z1 + U * (z2 - z1)
 ELSE
   VERIF% = FALSE
 ENDIF
RETURN

- Exemple de l'utilisation de VectorInSphere -
Listing GFA-Basic pour Windows, Faites un copier-coller
ou cliquez ici pour télécharger raytr1.lst
' Auteur : Nicolas Rey
' Date de création : 10 Février 2003
' objet : Démonstration de la procédure VectorInSphere()
' Site http://scalion.free.fr
n% = 300  ' Nombre de spheres maximum
DIM Sphere_cx(n%),Sphere_cy(n%),Sphere_cz(n%),Sphere_r(n%)
' Position de la source lumineuse
lumiere_x = 0
lumiere_y = 1
lumiere_z = 0
' Taille de l'êcran
scrx% = _X
scry% = _Y
' On ouvre une fenëtre en plein êcran
OPENW #1,0,0,scrx%,scry%,0
FULLW #1
' Dêfinir l'emplacement des sphéres
Figure_1
' Dêfinition de l'image dans l'espace et de la position de l'oeil
screen_defaut
' Distance entre chaque pixel 3D des lignes du haut et du bas de l'image dans l'espace
px1 = (x4 - x1) / scry%
py1 = (y4 - y1) / scry%
pz1 = (z4 - z1) / scry%
px2 = (x3 - x2) / scry%
py2 = (y3 - y2) / scry%
pz2 = (z3 - z2) / scry%
FOR p% = 5 DOWNTO 0  ' Rêsolution progressive de 2^5 á 2^0 (32 á 1)
 PAS% = 2 ^ p%
 KPAS% = 0
 FOR y% = 0 TO scry% - PAS% STEP PAS%
   '  Calcul des coordonnêes 3D de la ligne horizontale de l'image 3D
   ex1 = x1 +  px1  * y%
   ey1 = y1 +  py1  * y%
   ez1 = z1 +  pz1  * y%
   ex2 = x2 +  px2  * y%
   ey2 = y2 +  py2  * y%
   ez2 = z2 +  pz2  * y%
   lx = ex2 - ex1
   ly = ey2 - ey1
   lz = ez2 - ez1
   IF p% < 5
     KPAS% = PAS% - KPAS%
   ENDIF
   FOR x% = KPAS% TO scrx% - PAS% STEP PAS% + KPAS% ' Scan de la ligne horizontale
     ' Position du pixel 3D sur la ligne de l'image
     ex = ex1 + lx / scrx% * x%
     ey = ey1 + ly / scrx% * x%
     ez = ez1 + lz / scrx% * x%
     ' Vecteur Oeil / Pixel 3D de l'image
     dx = ex - cx
     dy = ey - cy
     dz = ez - cz
     CLR r,g,b
     ' distance au delá de laquelle le rayon se perd dans l'infini
     distance = 10000
     Normalise dx,dy,dz
     ' Valeur r,g,b retournêe par le lancer de rayon
     I_SPHERES cx,cy,cz,dx,dy,dz,r,g,b,distance
     ' Un petit effet de brouillard au delá de 100
     IF distance > 100
       brouillard = 1 + (distance - 100) / 15
       r = 0 + (r - 0) / brouillard
       g = 0 + (g - 0) / brouillard
       b = 127 + (b - 127) / brouillard
     ENDIF
     ' On affiche le rêsultat
     RGBCOLOR RGB(r,g,b)
     IF PAS% > 1
       PBOX x%,y%,x% + PRED(PAS%),y% + PRED(PAS%)
     ELSE
       PLOT x%,y%
     ENDIF
   NEXT x%
 NEXT y%
NEXT p%
? AT(1,1)"fin"
KEYGET rien%
CLOSEW #1
PROCEDURE Figure_1
 LOCAL a%,r
 r = 15
 FOR a = 1 TO 40 STEP 3
   @ADD_Sphere(a * 10,SIN(a / 4) * 30,150 + COS(a / 4) * 30,ABS(r))
   @ADD_Sphere(-a * 10,SIN(-a / 4) * 30,150 + COS(-a / 4) * 30,ABS(r))
   @ADD_Sphere(SIN(a / 4) * 50,a * 10,150 + COS(a / 4) * 50,ABS(r))
   @ADD_Sphere(SIN(-a / 4) * 50,-a * 10,150 + COS(-a / 4) * 50,ABS(r))
 NEXT a
RETURN
PROCEDURE I_SPHERES(cx,cy,cz,dx,dy,dz,VAR r,g,b,distance)
 LOCAL i%,v%,min_z,MATCH%
 FOR i% = 1 TO N_SPHERE%
   VectorInSphere(cx,cy,cz,dx,dy,dz,Sphere_cx(i%),Sphere_cy(i%),Sphere_cz(i%),Sphere_r(i%),v%,ix,iy,iz)
   IF v% = TRUE ' Si le rayon intercepte la sphere
     ' Si la distance est inférieure à ce qui a déjá été trouvé
     ' ou si c'est la premiére (d'ou le IF MATCH% = FALSE)
     IF MATCH% = FALSE OR iz < min_z
       min_z = iz
       ' On mêmorise le numêro de la sphére pour calculer ensuite la couleur
       match_SPHERE% = i%
       ' On mêmorise les Coordonnêes du point d'intersection
       match_x = ix
       match_y = iy
       match_z = iz
       ' Mêmorisation des Coordonnêes du centre de la sphére concernêes
       ' ce qui servira á calculer la luminositê
       ld_ox = Sphere_cx(i%)
       ld_oy = Sphere_cy(i%)
       ld_oz = Sphere_cz(i%)
     ENDIF
     MATCH% = TRUE
   ENDIF
 NEXT i%
 ' Si on á trouvê une intersection
 IF MATCH% = TRUE
   ' On dêduit la couleur en fonction du numêro de la sphére
   luminosite = @EXPOSITION(ld_ox,ld_oy,ld_oz,match_x,match_y,match_z)
   r = 127 + SIN(match_SPHERE% / 10 + match_x / 50) * 127
   g = 127 + SIN(match_SPHERE% / 10 + match_y / 50) * 127
   b = 127 + SIN(match_SPHERE% / 10 + match_z / 50) * 127
   r = r * luminosite
   g = g * luminosite
   b = b * luminosite
   distance = match_z
 ENDIF
RETURN
PROCEDURE ADD_Sphere(x,y,z,r)
 INC N_SPHERE%
 Sphere_cx(N_SPHERE%) = x
 Sphere_cy(N_SPHERE%) = y
 Sphere_cz(N_SPHERE%) = z
 Sphere_r(N_SPHERE%) = r
RETURN
PROCEDURE screen_defaut
 ' position dans l'espace de l'image
 x1 = -100,y1 = -80,z1 = 50
 x2 = 100,y2 = -80,z2 = 50
 x3 = 100,y3 = 80,z3 = 50
 x4 = -100,y4 = 80,z4 = 50
 ' position de l'oeil par rapport á l'image
 cx = 0,cy = 0,cz = 0
RETURN
PROCEDURE Normalise_Vecteur(VAR ox,oy,oz,dx,dy,dz)
 LOCAL lx,ly,lz,h
 lx = dx - ox,ly = dy - oy,lz = dz - oz
 h = SQR(lx ^ 2 + ly ^ 2 + lz ^ 2)
 IF h > 0
   dx = ox + lx / h,dy = oy + ly / h,dz = oz + lz / h
 ENDIF
RETURN
PROCEDURE Normalise(VAR dx,dy,dz)
 LOCAL h
 h = SQR(dx ^ 2 + dy ^ 2 + dz ^ 2)
 IF h > 0
   dx = dx / h,dy = dy / h,dz = dz / h
 ENDIF
RETURN
FUNCTION EXPOSITION(ox,oy,oz,dx,dy,dz)
 LOCAL vx,vy,vz
 vx = dx - ox,vy = dy - oy,vz = dz - oz
 Normalise vx,vy,vz
 RETURN SQR((vx - lumiere_x) ^ 2 + (vy - lumiere_y) ^ 2 + (vz - lumiere_z) ^ 2) / 2
ENDFUNC
PROCEDURE VectorInSphere(x1,y1,z1,x2,y2,z2,x3,y3,z3,r,VAR VERIF%,ix,iy,iz)
 LOCAL a,b,c,v,U
 a=(x2-x1)^2+(y2-y1)^2+(z2-z1)^2
 b=2*((x2-x1)*(x1-x3)+(y2-y1)*(y1-y3)+(z2-z1)*(z1-z3))
 c=x3^2+y3^2+z3^2+x1^2+y1^2+z1^2-2*(x3*x1+y3*y1+z3*z1)-r^2
 v=b*b-4*a*c
 IF v >= 0
   VERIF% = TRUE
   U=(-b-SQR(v))/(2*a)
   ix=x1+U*(x2-x1),iy=y1+U*(y2-y1),iz=z1+U*(z2-z1)
 ELSE
   VERIF%=FALSE
 ENDIF
RETURN