[Résolu] Génération de particules avec distribution gaussienne

Bonjour.
Je suis en train de re-coder le moteur de particules de GM (enfin je l'avais déjà fait, mais la je le complète et l'optimise) en C++, mais je me retrouve confronté a un petit soucis.
En effet générer des particules de manière aléatoire n'est pas très compliqué de manière linéaire, mais quand il s'agit d'avoir une distribution gaussienne, c'est de suite autre chose...

J'ai tout de même réussi a le faire pour les shapes rectangles et ligne.
La méthode est simple, j'ai crée une fonction aléatoire, dont on entre une valeur minimale et une valeur maximale.
La fonction se charge de trouver un nombre aléatoire compris dans cet ensemble et qui suis une loi normale.

Donc pour la ligne, rien de compliqué, on utilise la fonction telle quelle, et pour le rectangle, on l'utilise deux fois plutôt qu'une.

Par contre pour l'ellipsoïde, la, pour trouver un système qui bouffe pas trop de perfs, et surtout, qui fonctionne, c'est plutôt la misère.
Donc le première méthode qui m'est venue a l'esprit (et qu'est pas super opti), c'est de générer des points de manière aléatoire, et regarder s'ils appartiennent a l'ellipse.
Hors dans mon cas, bah ça marche pas, car autant y a pas de soucis avec une distribution linéaire, autant il est pas possible d'avoir une distribution gaussienne.

Donc deuxième essai, je tire une nombre aléatoire qui correspond a la largeur de l'ellipse, et maintenant, en fonction de l'équation de l'ellipse, sa hauteur associé.
Ça marche presque mais ça me donne plus un diamond qu'une ellipse x)


Alors que je veux ça :



Donc si quelqu'un a une idée de comment je pourrais m'y prendre :b

Edit:
Finalement j'essaye de faire ça a coup de trigo.
Je tire un angle au hasard, en fonction de ça je récupère le rayon associé, j'utilise ma fonction gaussienne, et je crée les particules.
Je vous tient au courant, mais ça devrais fonctionner.
Espérons juste que les fonctions trigo ne serons pas trop lourdes...

Rarement vu un titre aussi décourageant

Sinon, pour optimiser encore plus, tu pourrais pour chaque angle tirer au hasard un nombre de point, et pour chaque point, tirer au hasard une distance avec ta fonction gaussienne ?
[edit] Sinon, en effet, faire des trucs circulaires avec ne base orthonormée sans passer par la trigo, c'est un vaste problème... On devrait faire un topic spécial pour regrouper nos idées la dessus, ça nous épargnerai bien du temps...
[edit2]Attends, je cois que j'ai une autre idée : Quand l'ordinateur veut tracer un cercle de rayon r et de centre (a,b), il doit sûrement recourir à un fonction du style
cercle(a-r,b)
Tant que (x,y)!=(a-r,b)
cercle(x,y)

avec cercle (x,y) une fonction bien optimisée (que j'ai la flemme de déterminer mais je te fais confiance, ça doit être un truc du style, on trace (x,y) puis on regarde si les point (x+k,y+q) avec (k,q)=+-(1,1) ou +-(0,1) ou +-(1,0) correspondent à la partie entière d'un point du cercle - en évitant de revenir sur nos pas -, si oui, alors on fais x=x+k, y=y+q )

Bref, et bien c'est là que ta fonction gaussienne intervient. Tu vas tracer tous les cercles intérieurs, mais pour chaque point, tu le traces ssi a fonction gaussienne (en fction du rayon) dit qu'on peut le tracer.

Si en utilisant l'équation d'une ellipse tu te retrouves avec ce "diamond" qu'elle serait le rendu avec une équation de cercle?
Parce que le rendu de la 2e image me fait plus pensé à un cercle qu'à une ellipse. Cependant pour faire une vrai ellipse après se sera plus embêtant, certes :v/

Aaaaah une ellipse... Excuses, j'étais parti sur le cercle...

Une ellipse c'est jamais qu'un cercle étiré...

Ouaip exact.
Bon même avec la méthode de l'angle ça me donne un résultat crade. (je le fait avec distribution linéaire pour l'instant)

Code:

repeat(50)
{
    angle = random(360)
    lx = lengthdir_x(random(a), angle)
    ly = lengthdir_y(random(b), angle)
    instance_create(wx + lx, wy + ly, pt)
}

Je capte vraiment pas pourquoi on a une croix...

Edit: Ah si je vois.
Si l'angle est multiple de 90, lx ou ly seras égal a 0, ce qui donneras toujours 0 au final, quelque soit le rayon.
Donc faut que je parte sur un autre truc, again x)

Edit2:
J'aurais vraiment pas du me coucher si tard hier...
Donc la le délire ce serais de passer en coordonnées polaires (rayon et angle), modifier le rayon avec un random et repasser
en coordonnées normales. Hors j'ai du faire une connerie mais j'arrive pas a voir ou, ça devrais me donner une ellipse :

Code:

repeat(50)
{
    angle = random(360)
    lx = lengthdir_x(1, angle)
    ly = lengthdir_y(1, angle)
    vx = lx * a
    vy = ly * b
    r = sqrt( vx*vx  + vy*vy )
   
    instance_create(wx + r*lx, wy + r*ly, pt)
}

Bien qu'une ellipse n'est qu'un "cercle étiré", le problème ici, c'est que quand tu étire ce cercle, ça concentre plus ou moins la densité de tes particules (créant cet effet diamond)

Une question, tu compte avoir que des ellipse "axée" (on ne peut la tourner) ou pas?

Oui, axée, comme dans le moteur de particule de GM.

Sinon le problème de l'effet diamond avec la première technique, c'est que si je tire un X qui est trop a droite ou a gauche, bah il resteras que peu de Y a choisir.
Bref la technique n'est pas bonne. (si on regarde bien c'est pas vraiment un diamond, les amas sont surtout a droite et a gauche, au milieu la génération est correcte)
A mon avis la dernière est la bonne solution, mais j'arrive pas a convertir mes coordonnées correctement x)

Pour ma première solution, je voulais dire on prend chaque angle, donc pas de manière aléatiore, ce n'était pas clair.

Sinon, vu qu'une ellipse est un cercle étiré et que tu le fais aligné sur la grille, imaginons que tu étires ton cercle de rayon r et de centre (a,b) en multipliant sa hauteur par r'/r

Alors, tu décales tes points en multipliant leur ordonnée (relative à b) par r'/r.

voila une solution.
Elle a l'avantage de ne pas utilisé de fonction trigonométrique. (mais quand même des racines, si il faut je pourrais trouver des solution avec seulement des multiplications si tu veux)

linéaire: ( en réalité non linéaire, mais en pratique, sa ne change pas vraiment la figure)

distribution en sqrt(1.0-(x/a)²-(y/b)²) ( proche gaussienne à deux variable)



Voila les codes: ( C'est les codes que j'ai utilisé pour faire l'image avec la SFML, je te laisse les adapter )

linéaire:

Spoiler:

proche gaussienne

Spoiler:

ici les fichiers (avec tabulation + coloration avec ton editeur) Telecharger

Ah oui, encore plus d'optimisation : A partir d'un certain nombre de points, il vaut mieux tous les dessiner puis effacer certains avec ta fonction.

>Arthuro
Merci de m'accorder de ton temps, mais tu viens exactement de faire le même code que moi pour mon premier essai x)
On remarqueras d'ailleurs la distribution non uniforme des particules lorsque la distribution est linéaire, et la tendance des particules a faire un diamond lorsque la distribution est gaussienne.
Bref tout le problème est la, on ne doit pas calculer x, puis calculer y en fonction de x, sinon on va se retrouver avec des amas sur les bords (linéaires) et un effet diamond (gaussiennes) qui n'est pas présent dans GM.

Celle que je présente comme linéaire n'est pas vraiment linéaire.
Mais pour la seconde, je n'ai pas eut l'impression d'un effet diamond.

Bah si t'as la flemme explique vite fait la méthode, que je vois vers quoi me tourner :b

Sinon pour ce qui est du linéaire, bah on balance des points au hasard et on vérifie qu'ils appartiennent a l'ellipse, mais le problème
c'est qu'avec cette méthode je vois pas comment ajouter l'effet gaussien.
Si t'as une idée

Edit:
Bah finalement en faisant comme je viens de dire ça fonctionne plutot bien

Code:

wx = 320
wy = 240
r = mouse_x

repeat(50)
{
    rx = random(2*r)-r
    ry = random(2*r)-r
   
    if(rx*rx + ry*ry <= r*r)
    {
        rr = 1 - sqrt(random(1))
        xx = rx * rr
        yy = ry * rr
        instance_create(wx + xx, wy + yy, pt)
    }
}

J'pense que je vais utiliser ça, a moins que tu trouve un autre truc qui en vaudrai la chandelle x)

onilink_ a écrit:

Bref tout le problème est la, on ne doit pas calculer x, puis calculer y en fonction de x, sinon on va se retrouver avec des amas sur les bords (linéaires) et un effet diamond (gaussiennes) qui n'est pas présent dans GM.

Oh que si ! Mais tous les x n'ont pas la même chance d'apparaître...

Ce que je conseille en tout premier lieu, c'est de changer de repère pour bosser avec le cercle trigo. Homothétie ne dérangeant ni la fonction linéaire, ni la fonction normale, donc tout schuss.
On va même prendre le quart de disque supérieur parce qu'on est des flemmards, et qu'un disque ben c'est symétrique.

Son tracé est la courbe de C(x) = sqrt( 1 - x² )

Soit A l'aire sous la courbe, à ce moment-là ta fonction de répartition est :

r(x) = [ intégrale de 0 à x de C(t) dt ] / A

et bien sûr A = pi/4.

La solution à cette intégration traîne sur internet, et j'ai la flemme de la comprendre. Mais une fois implémentée, tu peux faire :

Code:

// Choix du quartier, puisqu'ils sont équiprobables
qx = choose( -1, 1 );
qy = choose( -1, 1 );
xx = r( fonction(1) );
yy = fonction( C( xx ));
spawnParticle( centerX + qx * xx * xRadius, centerY + qy * yy * yRadius );

Avec fonction( x ) ta fonction aléatoire, linéaire ou normale, appliquée entre 0 et x (donc seulement la partie droite de la courbe normale).

Pour la méthode idéal. (c'est un peu du charabias dsl)

Spoiler:

Ce que dit Dz à l'air bien

Deezee>
Ce que je voulais dire, c'est que si le x choisis est proche de l'extrémité gauche ou droite, et bien quand tu choisiras le y, il n'y auras que peu de choix comparé au centre.

D'où mon amas de particules.

Sinon le problème de ce dont tu me parle, c'est que ça nécessite un grand nombre de calculs.
Hors la il s'agit de génération de dizaines de milliers de particules, et tout ça en temps réel.
Donc autant utiliser une fonction approximative, comme le fameux (1 - sqrt(random(1)))

Pour l'instant avec la méthode de base (on balance des particules et on vérifie si elles appartiennent a l'ellipse) j'ai obtenu ça :



Juste ma gaussienne qu'est pas top pour le moment, mais c'est trèèès satisfaisant pour le peu de calculs effectués.

Edit:
Après quelques ajustement on arrive a un très bon truc :

onilink_ a écrit:

Deezee>
Ce que je voulais dire, c'est que si le x choisis est proche de l'extrémité gauche ou droite, et bien quand tu choisiras le y, il n'y auras que peu de choix comparé au centre.

Et c'est pour ça qu'on contrebalance avec une fonction de répartition qui tire moins souvent les extrémités, pour avoir moins de point à répartir que sur les grandes zones, et donc avoir une densité constante ;)

onilink_ a écrit:

Deezee>
Ce que je voulais dire, c'est que si le x choisis est proche de l'extrémité gauche ou droite, et bien quand tu choisiras le y, il n'y auras que peu de choix comparé au centre.

En faite, il faut que la probabilité d'obtenir un x dans cette zone soit proportionnelle à la longueur de ta ligne

donc tu choisit x selon la loi de densité: de [-1,1]->[0,1] 2*sqrt(1-x²) (pour un cercle trigo)

puis y selon une loi uniforme dans [-sqrt(1-x^2),sqrt(1-x^2)]


edit:

De toute manière, pour la loi linéaire, la méthode ou tu place un point de manière uniforme dans un rectangle et que tu enlève ceux hors du cercle est la méthode optimal. Tu ne fais que des multiplication et addition, et tu as 79% de chance de tomber du premier coup dans le cercle. ( tu as plus de 99% de chance de tomber dans le cercle en moins de 3 coups)


Sinon pour la gaussienne, j'ai une idée qui serait bien.
Tu génère tes points selon la méthode linéaire, en diminuant le rayon peut à peut vers 0.

Voila ce que donne la méthode gaussienne en utilisant la linéaire et en diminuant le rayon au fur et à mesure:

Spoiler:

Voila un screen.

Elle a l'avantage d'avoir la même complexité que la distribution linéaire



Prend bien garde à diminuer l'amplitude des probabilité en même temps que l'amplitude de la condition d'appartenance au cercle, sinon pour des cercles petit, tu n'aura que très peu de chance de tomber dans le cercle.

Ouai pas bête ça.
Perso j'utilisais ce code pour l'image si dessus :

Code:

if( rxa*rxa + ryb*ryb <= 1)
{
    if(distribution == ps_distr_linear)
        ps->create(rx + wx, ry + wy, parttype, 1);
    else
    {
        float rr = 1 - 2*sqrtf(rand()/(double)RAND_MAX);
        ps->create(rx*rr + wx, ry*rr + wy, parttype, 1);
    }
    number--;
}

Juste que ça donne pas exactement ce que je veux :
J'ai :

Je veux :


Et ça donne pareil la même chose que moi avec la méthode que tu viens de dire.
Donc si t'avais une idée de ce qu'il faudrait modifier :p (a mon avis c'est ma fonction aléatoire qu'est pas bonne)
En tout cas je cherche de mon coté

Edit:
Ah je crois avoir trouvé une solution toute conne. Je teste ça.

Oui je vois, un aspect "bulle" et pas "pic"

bin j'obtient un bon résultat en diminuant le rayon selon:

r=1.0-(i/imax)*0.5

Spoiler:

qui donne:


A mon avis, en jouant sur la façon de diminuer le rayon, on peut obtenir le résultat voulu.

Ce n'est pas une variante de mon edit2 ?

Johny Wessmuller a écrit:

Rarement vu un titre aussi décourageant

Sinon, pour optimiser encore plus, tu pourrais pour chaque angle tirer au hasard un nombre de point, et pour chaque point, tirer au hasard une distance avec ta fonction gaussienne ?
[edit] Sinon, en effet, faire des trucs circulaires avec ne base orthonormée sans passer par la trigo, c'est un vaste problème... On devrait faire un topic spécial pour regrouper nos idées la dessus, ça nous épargnerai bien du temps...
[edit2]Attends, je cois que j'ai une autre idée : Quand l'ordinateur veut tracer un cercle de rayon r et de centre (a,b), il doit sûrement recourir à un fonction du style
cercle(a-r,b)
Tant que (x,y)!=(a-r,b)
cercle(x,y)

avec cercle (x,y) une fonction bien optimisée (que j'ai la flemme de déterminer mais je te fais confiance, ça doit être un truc du style, on trace (x,y) puis on regarde si les point (x+k,y+q) avec (k,q)=+-(1,1) ou +-(0,1) ou +-(1,0) correspondent à la partie entière d'un point du cercle - en évitant de revenir sur nos pas -, si oui, alors on fais x=x+k, y=y+q )

Bref, et bien c'est là que ta fonction gaussienne intervient. Tu vas tracer tous les cercles intérieurs, mais pour chaque point, tu le traces ssi a fonction gaussienne (en fction du rayon) dit qu'on peut le tracer.

Fin bref, voilà deux algo qui correspondent :
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d'Andres
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_d'arc_de_cercle_de_Bresenham

Nan mais ne vous embêtez pas, j'ai trouvé un algo super simple. (vu qu'une distribution gaussienne dans un rectangle donne une amas circulaire au milieu)
Comme je vous l'ai dit j'avais déjà crée ma fonction d'aléatoire, bah j'ai fait ça :

Code:

for(int i=0; i<number; i++)
        {
            float rx, ry;
            do {
                rx = randType(-1, 1, distribution);
                ry = randType(-1, 1, distribution);
            } while(rx*rx + ry*ry >= 1);
           
            ps->create(rx*a + wx, ry*b + wy, parttype, 1);
        }

Et j'ai exactement le même résultat que sous GM, pour un cote tout petit est léger
En tout cas merci d'avoir suivis le sujet :p

Le résultat :

Sinon, quelqu'un connaitrait un moyen rapide de savoir si un point se trouve dans un 'diamond' ? (dernière shape qui me reste a coder)

diamond = losange ?

soit un losange de centre lx,ly, le demi largeur a, de demi hauteur b.

un point en x,y;

la condition est:

abs(lx-y)/a + abs(ly-y)/b <= 1

ou:

abs(lx-y)*b + abs(ly-y)*a <=a*b

Merci.

Ta condition parait logique et pourtant, ça n'a pas l'air de marcher

Sous GM, dans un draw pour ceux qui voudraient tester :

Code:

xmin = 320-128
xmax = 320+128
ymin = 240-64
ymax = 240+64

wx = (xmin + xmax)/2
wy = (ymin + ymax)/2
a  = (xmin - xmax)/2
b  = (ymin - ymax)/2

draw_primitive_begin(pr_linestrip)
draw_vertex(wx-a, wy)
draw_vertex(wx, wy-b)
draw_vertex(wx+a, wy)
draw_vertex(wx, wy+b)
draw_vertex(wx-a, wy)
draw_primitive_end()

if( abs(wx - mouse_x)/a + abs(wy - mouse_y)/b <= 1)
    draw_set_color(c_red)
else
    draw_set_color(0)

draw_circle(mouse_x, mouse_y, 8, 0)

J'ai du mal a voir ou se situe le problème la :/

Définition de a et b, tu fais min - max au lieu de max - min.

...
L'air con, dire que j'étaie sur de pas avoir fait cette connerie cette fois (qui m'est déjà arrivé hier) x)
C'est ça de copy pasta des vieux bouts de code quand on a la flemme .,.

Bah merci, c'était ça x)

Juste pour montrer le résultat :
http://www.host-a.net/u/onilink_/emitters.7z

Rester appuyer sur espace pour la distributivité gaussienne, et sur la flèche du haut pour changer de shape.