Discussion :

[Frifron]

Bonjour,

j'aimerai générer un "spray" de particules. Pour ca j'ai un vecteur direction OP définissant la direction du spray et un angle alpha définissant sa "largeur" (un angle de 0 et en fait le vecteur direction alors qu'un angle de 2PI définit une sphère de centre O et de rayon |OP|.)

Ces paramètre initiaux doivent me permettre de générer un vecteur aléatoirement appartenant au spray. La norme du vecteur générée aléatoirement est egale a celle du vecteur direction.

Je ne sais pas si je suis très clair mais en gros cela reviend a trouver un point quelquonque appartenant a la portion de sphère de centre O et de rayon |OP| définit par P et l'angle alpha (voir le schéma).

J'ai pensé à faire une rotation du point P d'axe arbitraire situé sur le plan normal a OP et d'angle [0,alpha] mais c'est relativement lourd en calcul et la rapidité de la génération est très importante dans mon cas. Voyez vous un moyen simple de parvenir a ce que je veux par exemple en utilisant une équation de la surface qui m'interesse ?

Les calculs induit par un changement du vecteur direction OP ou de l'angle alpha (ie un changement de la portion de sphère) peuvent être lourds (relativement) mais la génération du vecteur aléatoire en elle même doit être très rapide.

Une idée d'algo ?

PS : je suis peut être pas très clair

[Zavonen]

Pourquoi ne pas utiliser les coordonnées sphériques avec un repère dont l' axe Oz est l'axe du cône.

Cela revient à 3 tirages aléatoires de réels appartenant à des segments (rho théta, phi).

Ensuite appliquer les transformations sphériques --> cartesiennes si tu veux vraiment des x,y,z.

[Frifron]

Salut. Merci pour ta réponse.

Ouais les coordonnées sphériques, je pense que cela est un bon départ. Par contre tirer rho et theta aléatoirement (Phi etant fixe), rho sur [0,alpha] et theta sur [0,2PI] (ou le contraire je c plus...), je ne pense pas que cela me donne une distribution homogène des points sur la toute la surface. Il me semble que plus on se rapproche de P plus la densité de points tirés augmentera, nan ? Enfin avec mon idée d'implem a base de rotation de vecteur c'était pas mieux en fait...

Après il y a peu être moyen de générer rho (ou theta, je c toujours pas... ) de manière a obtenir une distribution homogène des points sur la surface...

[Zavonen]

Pour nous mettre d'accord adoptons les notations du wiki:
http://fr.wikipedia.org/wiki/Coordon...ph%C3%A9riques
Je n'ai pas compris si tu veux des points sur une portion de sphère (dimension 2) ou un cône pris dans une boule (dimension 3).
Si c'est le premier cas (à mon avis).
phi aléatoire uniforme entre 0 et 2pi
theta aléatoire uniforme entre 0 et alpha avec rho constant donne une distribution homogène sur la surface.
Edit: Réflexion faite, je n'en suis pas sûr.
Mais en dimension 3 il faut un correctif rho homogène ne donne pas une distribution de points homogène dans le cône (j'en suis à peu près sûr).
Supposons que ma sphère soit dans un cube disons sphère de centre O et de rayon 1 dans le cube -1 <= x<=+1 -1 <= y<=+1 -1 <= y<=+1
En prenant x,y, z aléatoires homogènes sur [-1,+1] par un Monte-Carlo quelconque (très rapide) j'obtiens une distribution de points homogène sur le cube. La trace de cette distribution sur la boule est donc homogène sur la boule (en 3D).
Donc pour avoir une distribution homogène sur la boule je tire un point au hasard (x,y,z) je vérifie si z <=racine (x²+y²) si oui je le garde, sinon je l'oublie.
Partant d'une distribution homogène sur la boule, je peux avoir une distribution homogène sur la sphère en traçant la droite joignant tous les points à l'origine et en voyant où elle coupe la sphère.
M(x,y,z) dans la boule M'(x',y',z') sur la sphère
(x',y',z') se déduit de (x,y,z) par (x',y',z')=k(x,y,z) avec k=1/racine(x²+y²+z²)
Donc pour avoir une distribution homogène sur la sphère de rayon 1, je propose la méthode suivante.
Tirer au hasard (x,y,z) entre -1 et +1
garder le triplet seulement si z² <= x²+y².
lui associer (kx,ky,kz) où k=1/racine(x²+y²+z²).
Cela fait trois carrés et une racine à chaque fois. En outre le procédé est ralenti par un facteur (4/3)pi/8 à cause des points qu'il faut oublier.
On doit pouvoir faire la même chose pour un cône. Le placer dans un parallélépipède, générer un nuage aléatoire équiréparti sur ce parallélépipède, ne garder que les points dans le cône, puis les projeter sur la surface.
Question efficacité c'est à voir.
Il y a sans doute mieux à faire.
Une formule telle que celle que tu cherches doit exister mais je ne la connais pas et je n'arrive pas à la retrouver simplement.

[Frifron]

oui c'est bien des points sur une portion de sphère que je veux. J'ai implémenté ta méthode et ca fonctionne sauf la distribution qui n'est donc pas homogène. En réfléchisant un peu c'est tout a fait logique :

(en reprenant ta notation)
theta est tirée aléatoirement sur [0,alpha] (en fait j'ai généralisé à [alpha,beta]), cet angle définit un cercle sur la sphere dont le rayon est ||| |sin(theta)| (avec rho = 1). l'angle phi définit ensuite un point sur ce cercle.

le tirage aléatoire de théta equivaut en fait au tirage aléatoire d'un cerche sur la sphere. Or le périmètre du cercle est fonction de theta donc n'est pas constant. Pourtant il y a autant de chance de tirer un point sur un cercle que sur un autre.

Pour rendre la distribution des points homogène, il faut que le tirage de théta ne soit pas homogène et soit fonction du périmètre du cercle définit par théta.

Et c'est maintenant la que je bloque : il me faut un tirage aléatoire sur [a,b] et une formule qui transformera ce nombre en angle théta sur [alpha,beta] et qui assurera une distribution homogène sur toute la surface.

j'imagine qu'il y a une histoire d'intégrale de |sin| sur l'intervalle [alpha,beta] pour trouver l'intervalle [a,b] ou un truc dans le style

[Zavonen]

Oui, je m'en suis rendu compte (voir edit de mon post).
La méthode empirique que je propose fonctionne certainement, tu peux essayer 'just for fun', mais une bonne formule ce serait mieux.
Edit: Ma dernière proposition ne fonctionne pas.
Dernier essai:

x uniforme sur ]-Rsin(alpha),+Rsin(alpha)[
x étant choisi aléatoirement:
y uniforme sur ]-racine(R²sin²(alpha)-x²),+racine(R²sin²(alpha)-x²)[
x et y étant choisis,
z uniforme sur ]xtan(alpha),R[

(x,y,z) étant choisis prendre (x',y',z')=k(x,y,z) où
k =1/racine(x²+y²+z²).

Les points (x',y',z') devraient être uniformément répartis sur la surface. C'est la traduction mathématique du procédé empirique que je propose, en évitant de rejeter des points non conformes.

[Frifron]

J'ai fait des rendus en utilisant les formules proposées.

J'ai utilisé ses valeurs :
OP = {0.0f,1.0f,0.0f}
alpha = PI
Donc une demi sphere orientée selon Oy (j'ai changé l'axe car en même temps je testai mon calcul de matrice de changement de repère)

Je lance des particules ayant pour vecteur vitesse un vecteur généré a l'aide d'une des méthodes plus haut. Ce vecteur ne varie pas sur t. La durée de vie des particules est constante.

résultat 1 est le rendu obtenu en utilisant la méthode des coordonées sphérique le long de Oz. On voit clairement que la densité est plus forte le long de l'axe.

résultat 2 est le rendu obtenu en utilisant la méthode empirique de Zavonen.
La distribution n'a pas l'air parfaitement uniforme non plus. Le long de l'axe 0x, la densité semble plus importante (image en haut a droite). La densité est egalement plus importante lorsque theta est au environ de -PI / 4 et PI / 4 (image en bas a droite). De plus il me semble que ta formule ne fonctionne que pour alpha [0,PI].

C'est pas evident comme problème. Je reste sur qu'une formule permettant de tirer un theta qui entraine une distribution uniforme sur la surface existe et n'est pas si compliqué que ca. Une question de rapport de périmètre ou quelquechose comme ca.

En tout cas Zavonen merci beaucoup pour ton aide ! Une méthode de selection des points dans un cube englobant fonctionnerai surement mais ca ne me parait pas viable niveau perf.

[Zavonen]

Es tu absolument sûr de ton générateur de réels aléatoires ???
Tu peux faire un test du Khi-2 pour voir si la distribution est uniforme sur un segment. dans le passé j'ai eu de (mauvaises) surprises pour cette simple raison.

[Frifron]

j'utilise la fonction random() de la librairie standard pour générer des réels pseudo aléatoire. J'imagine que la génération est efficace.

Je ferai le test ce soir, mais je ne pense pas que la non homogeneité de la distribution soit du au générateur de nombre pseudo aléatoire (comme la première méthode donne les résultat graphiques escomptés). Enfin peut etre, je regarderai...

J'avoue que je n'ai pas chercher a trouver le pourquoi du comment de ta méthode, donc je ne peux pas dire "ca marche" ou "ca marche pas"

[Frifron]

J'ai regardé ta méthode et je ne comprend pas pourquoi cela assurerait une distribution uniforme ?

En gros, si j'ai bien compris :
Tu selectionnes un point sur l'axe Ox dont la contrainte est qu'il soit une projection eventuelle d'un point de la surface qui nous interesse.
Ensuite tu selectionnes un point sur l'axe Oy, toujours en respectant cette contrainte.

On se retrouve donc avec un nuage de point appartenant a la projection de la surface sur le plan (0xy). Ce nuage de point n'est pas uniformément distribué. Ce n'est plus une distribution concentrique mais linéaire suivant Ox. Plus le x est loin du centre, plus la densité sera importante (car le segment des choix possible de y diminue avec la distance puisque la projection est un disque).

Ensuite tu tires un z aléatoire compris entre tan(alpha)x et R donc en gros le point se retrouve dans le cube englobant mais exterieur a la sphère de laquelle la surface est issue. Puis on projette ce point. sur la surface. La je ne vois pas de raison que ca annule le non uniformité de la projection selon 0x (il n'y a pas de raison). Et je pense que cette étape justifie la densité plus importante autour des -PI/4 et PI/4 mais je ne peux pas expliquer précisément la raison.

D'instinct, sans etre capable de le démontrer rigoureusement, je pense qu'il reste un problème d'homogénéité même si la distribution est tout de même mieux assuré qu'avec la première méthode.

[Zavonen]

Je crois bien que tu as raison.
Il me faudra revoir ma copie.
Pas le temps maintenant (sur le départ).
Mais ce problème m'intéresse, pourras-tu poster la solution dès que tu l'auras trouvée?
Désolé.
Bonne chance.

[Frifron]

Pas de problème, des que j'ai une solution, je vous en fait profiter. Merci a toi en tout cas. Bon départ

[TanEk]

Je ne comprends pas pourquoi un tirage aléatoire de theta et phi ne donnerait pas une distribution homogène sur la sphère (en fixant rho). C'est bien sur une sphère et pas sur une boule que tu veux la distribution ?

[plegat]

Je ne comprends pas pourquoi un tirage aléatoire de theta et phi ne donnerait pas une distribution homogène sur la sphère (en fixant rho). C'est bien sur une sphère et pas sur une boule que tu veux la distribution ?

Parce que tu ne couvres pas les mêmes surfaces, en prenant les mêmes intervalles pour tes angles.
Compare par exemple les surfaces couvertes par les combinaisons suivantes:

• theta entre -5° et 5°, phi entre 0° et 10°
• theta entre -5° et 5°, phi entre 85° et 95°

Si la distribution sur le tirage des angles est uniforme, tu dois avoir autant de chance de tirer un point dans l'une ou l'autre des deux régions. Mais tu en as une qui est beaucoup plus grande que l'autre, résultat ta densité de points sur la sphère ne sera pas uniforme. En gros, tu vas avoir du 1000 points/mm² pour phi proche de 0° et de 180°, et tu vas avoir du 10 points/mm² pour phi=90°.

Enfin, je vois ça comme ça après un petit test rapide...

[Jean-Marc.Bourguet]

http://www.developpez.net/forums/d78...int-aleatoire/

[Zavonen]

Quand tu a tes deux angles répartis aléatoirement uniformément chacun sur un intervalle cela te donne une distribution uniforme sur un rectangle.
Maintenant ton rectangle est déformé en une sphère par les coordonnées sphériques classiques qui constituent un paramétrage de la sphère comme surface à deux dimensions.
Maintenant si tu prends un pavage du rectangle par de petits rectangles, chacun de ses petits rectangles sera transformé en un quadrilatère 'sphérique' mais tous n'aurons pas la même aire. Or distribution uniforme signifie que à surface égale tous les ds doivent avoir la même probabilité de recevoir un rayon.
C'est lié au fait que les transformations impliquées ne conservent ni les surfaces ni les rapports des surfaces.
Donc pour avoir une distribution uniforme sur la sphère il faut partir d'un pavage régulier de la sphère, le 'redresser' en un pavage (irrégulier) du rectangle et après à partir d'une distribution uniforme sur le rectangle, selon l'endroit où on tombe sur ce pavage irrégulier on redresse le rayon.
1) Je ne sais pas si je suis bien clair.
2) Je ne sais malheureusement pas le faire. (un pavage régulier de la sphère).
L'idée est de prendre des méridiens équidistants (ça c'est facile) et d'ajuster la position des parallèles pour que les triangles ou quadrilatères aient tous même surface (ça c'est moins facile).

[TanEk]

Parce que tu ne couvres pas les mêmes surfaces, en prenant les mêmes intervalles pour tes angles.
Compare par exemple les surfaces couvertes par les combinaisons suivantes:

• theta entre -5° et 5°, phi entre 0° et 10°
• theta entre -5° et 5°, phi entre 85° et 95°

Si la distribution sur le tirage des angles est uniforme, tu dois avoir autant de chance de tirer un point dans l'une ou l'autre des deux régions. Mais tu en as une qui est beaucoup plus grande que l'autre, résultat ta densité de points sur la sphère ne sera pas uniforme. En gros, tu vas avoir du 1000 points/mm² pour phi proche de 0° et de 180°, et tu vas avoir du 10 points/mm² pour phi=90°.

Enfin, je vois ça comme ça après un petit test rapide...

Et pourquoi seraient-elles plus grandes ? ! Je dois être bigleux parce que pour moi lla longueur de l'arc de cercle entre 0° et 10°, entre -5° et 5° et entre 85° et 95° est la même (égale à 10 * 2pi / 360). De même que la longueur des intervalles (égale à 10).

[Jean-Marc.Bourguet]

Et pourquoi seraient-elles plus grandes ? ! Je dois être bigleux parce que pour moi lla longueur de l'arc de cercle entre 0° et 10°, entre -5° et 5° et entre 85° et 95° est la même (égale à 10 * 2pi / 360). De même que la longueur des intervalles (égale à 10).

Pour toi les paralleles sur la terre ont tous la meme longueur?

[Zavonen]

Vous devriez trouver votre bonheur en googlant avec:

• Représentation conforme
• Projection de Mercator.
• Projections stéréographiques

C'est un vieux problème de cartographie bien connu où l'on veut aplatir le globe de façon à ce que les surfaces soient conservées.
Pas le temps de développer mais je suis sûr que la solution est là.

[Frifron]

J'ai trouvé !

En fait il ne faut pas faire un tirage aléatoire sur theta mais sur les cosinus de theta. Ainsi la repartition des angle n'est plus uniforme mais celle sur des points sur la sphère l'est :

On a alpha E [0,PI]
On tire a sur [cos(alpha),1]
theta = acos(a)

On peut généraliser a 2 angles alpha,beta E [0,PI] ; beta <= alpha
On tire a sur [cos(alpha),cos(beta)]
theta = acos(a)

J'ai testé et ca marche (voir le rendu).

C'était beaucoup plus simple qu'il n'y paraissait en fait... Ca doit même être démontrable assez facilement.