Distribución aleatoria uniforme (Monte-Carlo) en la esfera de la unidad

Question

Necesito una aclaración con un algoritmo que genere valores aleatorios para mi rastreador de rayos para mascotas.
Emite rayos desde un punto. Y tengo el problema con la distribución de estos rayos: necesito que la distribución sea uniforme, pero no es ...

El problema al que me enfrento ahora es que la distribución que es uniforme inicialmente no es uniforme después de mis distorsiones de el espacio de resultados.

Así que, por ejemplo, genero los ángulos r y t si el sistema de coordenadas polares. La distribución no es uniforme y no puede ser uniforme: el espacio cerca de cada polo tiene una densidad de resultados mucho mayor que, por ejemplo, cerca del ecuador. La razón es bastante clara: convierto puntos distribuidos uniformemente del espacio cilíndrico al esférico. Y yo distorsiono los resultados. El mismo problema es si normalizo los puntos generados aleatoriamente en el cubo.

Mi idea ahora es esta: quiero crear un tetraedro, normalizar sus vértices, dividir cada cara (triángulo) con el punto en el medio, normalizar y repetir recursivamente hasta que tenga suficientes puntos. Luego "distorsiono" estos puntos un poco. Luego los normalizo de nuevo. Eso es.

Entiendo que este método no es puro método matemático Monte-Carlo en sí, porque no uso la distribución aleatoria en ningún paso, excepto en el último. Y no me gusta esta solución para esta complejidad.

¿Puede alguien sugerir algo más simple, pero todavía

• aleatoria
• uniforme
• rápida
• sencilla

Gracias!

EDIT:
necesito un método rápido, no sólo la correcta. Es por eso que estoy preguntando por Montecarlo. Las respuestas proporcionadas son correctas, pero no rápidas. El método con tetraedro es rápido, pero no muy "aleatorio" => incorrecto.
Realmente necesito algo más adecuado.

Answer 1

Here's un algoritmo que le permite generar puntos distribuidos al azar en la esfera unidad.

Answer 2

No estoy seguro de si esto tiene ningún sentido en absoluto, pero aquí van:

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

Answer 3

Para las secciones esféricas, genere su ángulo uniformemente en phi (el ángulo polar) y cos(theta) (para theta el ángulo acimutal) entre sus límites.

En pseudocódigo:

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) 

Este es un caso especial de la regla que dice que invertir la Jacobian y generar de manera uniforme en ese espacio de esas coordenadas.

Nota: Tenga en cuenta que estoy usando la convención opuesta para phi y theta de la línea de David Norman.

Tenga en cuenta también: Este no es realmente el método más rápido, sino más bien uno que ilustra el principio general.

Answer 4

A menos que esté trazando rayas solo en escenas triviales, ¿su tiempo de renderizado estará realmente dominado por el tiempo de selección de muestras? Si no, probablemente aún no valga la pena optimizarlo, aunque vale la pena leer y comprender las técnicas uniformes de muestreo que se dan en las otras respuestas.

Además, sus muestras no necesitan ser muy aleatorias para producir una buena estimación de la función que está muestreando. Es posible que desee investigar el uso de una secuencia de números cuasialeatorios, como Halton sequence. Su idea de subdivisión tetraedro no está mal. Debería tener como resultado buenos puntos bien distribuidos que deberían ser mejores que las muestras pseudoaleatorias uniformes para la mayoría de las escenas, aunque podría dar lugar a artefactos horripilantes en algunas circunstancias.

De todos modos realmente deberías consultar los foros en ompf.org. Tengo algunos nerds super rastreadores de rayos por allá.

Answer 5

Aquí hay una aplicación Java que he utilizado en el pasado:

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

¿Usted realmente necesita la distribución aleatoria o una distribución uniforme sobre la esfera?

Entonces sugeriría los ángulos ZCW, que se distribuyen por igual en toda la esfera y son rápidos de calcular. Otros métodos son TheSydneyOperaHouse (SOPHE) y Repulsion. (search for repulsion.c) El método de repulsión es bastante bueno pero lento: Distribuye puntos de manera uniforme sobre una esfera. Afortunadamente tiene que hacerse solo una vez.

Esto se utiliza en cristalografía y RMN, porque para los patrones de polvo es más rápido usar una distribución uniforme versus distribución aleatoria (necesita menos puntos).

Here es una implementación de Python para ZCW.

Más detalles en estos documentos:

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

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