Distribuzione uniforme casuale (Monte-Carlo) su sfera unitaria

Question

Ho bisogno di un chiarimento con l'algoritmo che genera valori casuali per il mio ray-tracer domestico.
Emetto raggi da un punto. E ho il problema con la distribuzione di questi raggi: ho bisogno della distribuzione per essere uniforme, ma non è ...

Il problema che affronto ora è che la distribuzione essendo uniforme inizialmente non è uniforme dopo le mie distorsioni di lo spazio dei risultati.

Quindi, ad esempio, genero angoli r e t se il sistema di coordinate polari. La distribuzione non è uniforme e non può essere uniforme: lo spazio vicino a ciascun polo ha una densità di risultati molto maggiore rispetto, ad esempio, vicino all'equatore. Il motivo è abbastanza chiaro: converto punti distribuiti uniformemente da spazio cilindrico a sferico. E distorto i risultati. Lo stesso problema è se normalizzo i punti generati casualmente nel cubo.

La mia idea ora è questa: voglio creare un tetraedro, normalizzare i suoi vertici, dividere ogni faccia (triangolo) con il punto nel mezzo, normalizzarlo e ripetere ricorsivamente finché non ho abbastanza punti. Poi "distorto" questi punti un po '. Poi li normalizzo di nuovo. Questo è tutto.

Comprendo che questo metodo non è un metodo matematico Monte-Carlo, perché non uso la distribuzione casuale in alcun passaggio tranne che per l'ultimo. E non mi piace questa soluzione per questa complessità.

Qualcuno può suggerire qualcosa di più semplice, ma ancora

• casuale
• uniforme
• veloce
• semplice

Grazie!

EDIT:
ho bisogno di un metodo veloce, non solo quella corretta. Ecco perché sto chiedendo di Monte-Carlo. Le risposte fornite sono corrette, ma non veloci. Il metodo con tetraedro è veloce, ma non molto "casuale" => errato.
Ho davvero bisogno di qualcosa di più adatto.

Answer 1

Here's un algoritmo che permette di generare i punti distribuiti sulla sfera unitaria.

Answer 2

Non sono sicuro se questo ha alcun senso a tutti, ma qui si va:

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

Answer 3

Per le sezioni sferiche generare l'angolo uniformemente in phi (l'angolo polare) e cos(theta) (per theta l'angolo azimutale) tra i limiti.

In pseudo-codice:

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) 

Questo è un caso speciale della regola che dice invertire la Jacobian e generare in modo uniforme in quello spazio di quei coordinate.

Nota: si noti che sto utilizzando la convenzione opposta per phi e theta della linea David Norman.

Nota anche: Questo non è in realtà il metodo più veloce, ma piuttosto quello che illustra il principio generale.

Answer 4

A meno che non si stia eseguendo il raytracing solo in scene banali, il tempo di rendering sarà dominato dal tempo di prelievo del campione? In caso contrario, probabilmente non vale ancora la pena di essere ottimizzato, sebbene valga la pena leggere e comprendere le tecniche di campionamento uniforme fornite nelle altre risposte.

Inoltre, i campioni non devono essere molto casuali per produrre una buona stima della funzione che si sta campionando. Si consiglia di indagare usando una sequenza numerica casuale come lo Halton sequence. La tua idea di suddivisione del tetraedro non è male. Dovrebbe risultare in bei punti ben distribuiti che dovrebbero essere migliori dei campioni pseudocasuali uniformi per la maggior parte delle scene, anche se in alcune circostanze potrebbero causare artefatti orribili.

In ogni caso dovresti davvero consultare i forum su ompf.org. Ho un po 'di nerd super hardcore di raytracing laggiù.

Answer 5

Ecco un'implementazione Java che ho usato in passato:

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

Avete veramente bisogno di distribuzione casuale o una distribuzione uniforme sulla sfera?

Quindi suggerirei angoli ZCW, che sono equamente distribuiti su tutta la sfera e veloci da calcolare. Altri metodi sono TheSydneyOperaHouse (SOPHE) e Repulsion. (cerca la repulsione.c) Il metodo di repulsione è abbastanza buono ma lento: distribuisce iterativamente i punti in modo uniforme su una sfera. Fortunatamente deve essere fatto solo una volta.

Viene utilizzato in cristallografia e NMR, poiché per i modelli a polvere è più rapido utilizzare una distribuzione uniforme rispetto a una distribuzione casuale (sono necessari meno punti).

Here è un'implementazione Python per ZCW.

Maggiori dettagli in queste carte:

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

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