Distribution aléatoire uniforme (Monte-Carlo) sur la sphère unitaire

Question

J'ai besoin d'une clarification avec un algorithme générant des valeurs aléatoires pour mon rayon-traceur.
J'émets des rayons d'un point. Et j'ai le problème de la distribution de ces rayons: j'ai besoin de la distribution pour être uniforme, mais ce n'est pas ...

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. Par exemple, je génère des angles r et t si le système de coordonnées polaires est utilisé. La distribution n'est pas uniforme et ne peut pas être uniforme: l'espace près de chaque pôle a beaucoup plus de densité de résultats que, disons, près de l'équateur. La raison est assez claire: je convertis des points uniformément répartis de l'espace cylindrique à l'espace 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 est la suivante: 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 de façon récursive jusqu'à ce que j'aie suffisamment de points. Ensuite, je "déforme" ces points un peu. Ensuite, je les normalise à nouveau. C'est tout. Je comprends que cette méthode n'est pas la méthode mathématique de Monte-Carlo elle-même, parce que je n'utilise pas la distribution aléatoire dans aucune des étapes sauf la dernière. Et je n'aime pas cette solution pour cette complexité.

Quelqu'un peut-il suggérer quelque chose de plus simple et encore

• aléatoire
• uniforme
• rapide
• simples

Merci!

EDIT:
je besoin d'une méthode rapide, non seulement le bon. C'est pourquoi je pose des questions sur Monte-Carlo. Les réponses fournies sont correctes, mais pas rapides. La méthode avec tétraèdre est rapide, mais pas très "aléatoire" => incorrecte.
J'ai vraiment besoin de quelque chose de plus approprié.

Answer 1

Here's un algorithme qui permet de générer des points répartis de façon aléatoire sur la sphère unité.

Answer 2

Je ne sais pas si cela aucun sens du tout, mais ici vous allez:

Uniform Fractional Part: A Simple Fast Method for Generating Continuous Random Variates

Answer 3

Pour des sections sphériques, générez uniformément votre angle en phi (angle polaire) et cos(theta) (pour theta l'angle azimutal) entre vos limites.

Dans le code pseudo:

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) 

Ceci est un cas particulier de la règle qui dit inverser la Jacobian et générer uniformément dans cet espace de ces coordonnées.

Note: Notez que j'utilise la convention inverse pour phi et thêta de la lignée David Norman.

Note aussi: Ce n'est pas réellement la méthode la plus rapide, mais plutôt celle qui illustre le principe général.

Answer 4

À moins que vous ne projetiez que des scènes triviales, votre temps de rendu sera-t-il vraiment dominé par le temps de prélèvement? Sinon, cela ne vaut probablement pas la peine d'être optimisé, même s'il vaut la peine de lire et de comprendre les techniques d'échantillonnage uniformes données dans les autres réponses. De plus, vos échantillons n'ont pas besoin d'être très aléatoires pour produire une bonne estimation de la fonction que vous échantillonnez. Vous souhaiterez peut-être rechercher à l'aide d'une séquence de numéros quasirandom telle que Halton sequence. Votre idée de subdivision de tétraèdre n'est pas mauvaise. Il devrait en résulter de beaux points bien répartis qui devraient être meilleurs que des échantillons pseudo-aléatoires uniformes pour la plupart des scènes, bien que cela pourrait entraîner des artefacts horrifiants dans certaines circonstances.

De toute façon vraiment vous devriez consulter les forums à ompf.org. J'ai des super nerds de strip-tease super hardcore là-bas.

Answer 5

Voici une implémentation Java que je l'ai utilisé 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}; 
} 

Answer 6

Avez-vous vraiment besoin de distribution aléatoire ou une répartition uniforme sur la sphère?

Ensuite, je suggère des angles ZCW, qui sont répartis équitablement sur toute la sphère et rapide à calculer. D'autres méthodes sont TheSydneyOperaHouse (SOPHE) et Repulsion. (recherche de répulsion.c) La méthode de répulsion est assez bonne mais lente: elle répartit itérativement les points sur une sphère. Heureusement, cela ne doit être fait qu'une seule fois.

Ceci est utilisé en cristallographie et RMN, parce que pour les modèles de poudre, il est plus rapide d'utiliser une distribution égale par rapport à la distribution aléatoire (vous avez besoin de moins de points).

Here est une implémentation Python pour ZCW.

Plus de détails dans ces documents:

• Investigations of a nonrandom numerical method for multidimensional integration, Cheng, Vera B. et Henry H. Suzukawa, Jr. et Wolfsberg, Max

• Computer simulations in solid-state NMR. III. Powder averaging, Matthias Edén