Distribution aléatoire uniforme (Monte-Carlo) sur une sphère unitaire
j'ai besoin d'une clarification avec un algorithme générant des valeurs aléatoires pour mon traceur de rayons pet.
J'émets des rayons à partir d'un point. Et j'ai le problème avec la distribution de ces rayons: j'ai besoin que la distribution soit uniforme, mais ce n'est pas le cas...
le problème que je rencontre maintenant est que la distribution étant uniforme au départ n'est pas uniforme après mes distorsions de l'espace des résultats.
donc par exemple, je génère des angles r et t si le système de coordonnées polaires. La distribution n'est pas uniforme et elle ne peut pas l'être: l'espace proche de chaque pôle a beaucoup plus de densité de résultats que, disons, proche de l'Équateur. La raison est assez claire: je convertis des points uniformément distribués de l'espace cylindrique au sphérique. Et je déforme les résultats. Le même problème est si je normalise les points générés aléatoirement dans le cube.
mon idée maintenant est celle-ci: je veux créer un tétraèdre, normaliser ses Vertex, diviser chaque face (triangle) avec le point au milieu, le normaliser et répéter récursivement jusqu'à ce que j'ai assez de points. Puis je "déforme" un peu ces points. Puis je les normalise à nouveau. C'est tout.
je comprends que cette méthode n'est pas purement mathématique Monte-Carlo méthode elle-même, parce que je n'utilise la distribution aléatoire dans aucune étape sauf pour la dernière. Et je n'aime pas cette solution de cette complexité.
est-ce que quelqu'un peut suggérer quelque chose de plus simple mais toujours
- aléatoire
- uniforme
- rapide
- simple
Merci!
EDIT:
J'ai besoin d'une méthode rapide, pas seulement la bonne. C'est pourquoi je pose la question au sujet de Monte-Carlo. Les réponses fournies sont correctes, mais pas rapides. La méthode avec le tétraèdre est rapide, mais pas très "aléatoire" => incorrecte.
J'ai vraiment besoin de quelque chose de plus approprié.
6 réponses
Voici un algorithme qui vous permet de générer des points distribués aléatoirement sur la sphère de l'unité.
Voici une implémentation Java que j'ai utilisée dans le passé:
public static double[] randomPointOnSphere(Random rnd)
{
double x, y, z, d2;
do {
x = rnd.nextGaussian();
y = rnd.nextGaussian();
z = rnd.nextGaussian();
d2 = x*x + y*y + z*z;
} while (d2 <= Double.MIN_NORMAL);
double s = Math.sqrt(1.0 / d2);
return new double[] {x*s, y*s, z*s};
}
avez-vous vraiment besoin de la distribution aléatoire ou d'une distribution uniforme sur la sphère?
alors je suggérerais les angles ZCW, qui sont également répartis sur toute la sphère et rapide à calculer. D'autres méthodes sont le Syd-Ney-Operahouse(SOPHE) et la répulsion. (rechercher la répulsion.C) La méthode de répulsion est assez bonne mais lente: elle distribue itérativement des points uniformément sur une sphère. Heureusement qu'il a à faire qu'une seule fois.
utilisé dans cristallographie et la RMN, parce que pour les modèles de poudre, il est plus rapide d'utiliser une distribution uniforme par rapport à la distribution aléatoire (vous avez besoin de moins de points).
ici est une implémentation Python pour ZCW.
plus de détails dans ces documents:
-
Etudes d'une méthode numérique non aléatoire d'intégration multidimensionnelle , Cheng, Vera B. et Henry H. Suzukawa, Jr. et Wolfsberg, Max
-
simulations sur Ordinateur à l'état solide de la RMN. III. Poudre moyenne 151980920" , Matthias Edén
à moins que vous ne soyez en train de Raytracer seulement des scènes triviales, votre temps de rendu sera-t-il vraiment dominé par le temps de prélèvement d'échantillons? Si ce n'est pas le cas, cela ne vaut probablement pas la peine d'être optimisé pour le moment, mais il vaut la peine de lire et de comprendre les techniques d'échantillonnage uniformes données dans les autres réponses.
aussi, vos échantillons n'ont pas besoin d'être très aléatoires pour produire une bonne estimation de n'importe quelle fonction que vous échantillonnez. Vous pourriez vouloir enquêter en utilisant une séquence de nombre quasirandom tel que le Halton séquence . Votre idée de subdivision tétraèdre n'est pas mauvaise. Il devrait en résulter de beaux points bien distribués qui devraient être meilleurs que des échantillons de pseudorandom uniformes pour la plupart des scènes, mais pourrait entraîner des artefacts horribles dans certaines circonstances.
quoi qu'il en soit vraiment vous devriez consulter les forums à ompf.org. Il y a des nerds super hardcore raytracing là-bas.
pour une section sphérique génère votre angle uniformément dans phi (l'angle polaire) et cos(theta) (pour theta l'angle azimutal) entre vos limites.
en pseudo code:
phi = phi_low_limit + rand()*(phi_high_limit - phi_low_limit)
ct = cos(theta_high_limit) + rand()*(cos(theta_low_limit) - cos(theta_high_limit))
// The order is inverted here because cos heads down for increasing theta
theta = arccos(ct)
C'est un cas particulier de la règle qui dit inverser le Jacobian et générer uniformément dans cet espace de ces coordonnées.
Note: notez que j'utilise le convention opposée pour phi et theta de David Norman line.
Note aussi: ce n'est pas réellement la méthode la plus rapide, mais plutôt une qui illustre le principe général.