单位半球表面上快速均匀分布的随机点

2022-01-14 00:00:00 geometry math random c++

我正在尝试为蒙特卡洛光线追踪程序在单位球体的表面上生成均匀的随机点.当我说均匀时,我的意思是这些点相对于表面积是均匀分布的.我目前的方法是计算指向正 z 轴和 x-y 平面基点的半球上的均匀随机点.

I am trying to generate uniform random points on the surface of a unit sphere for a Monte Carlo ray tracing program. When I say uniform I mean the points are uniformly distributed with respect to surface area. My current methodology is to calculate uniform random points on a hemisphere pointing in the positive z axis and base in the x-y plane.

半球上的随机点表示漫反射灰发射器的热辐射发射方向.

The random point on the hemisphere represents the direction of emission of thermal radiation for a diffuse grey emitter.

当我使用以下计算时,我得到了正确的结果:

注意:dsfmt* 将返回一个介于 0 和 1 之间的随机数.

azimuthal = 2*PI*dsfmt_genrand_close_open(&dsfmtt);
zenith = asin(sqrt(dsfmt_genrand_close_open(&dsfmtt)));

// Calculate the cartesian point
osRay.c._x = sin(zenith)*cos(azimuthal); 
osRay.c._y = sin(zenith)*sin(azimuthal);
osRay.c._z = cos(zenith);

但是,这非常慢,并且分析表明它占用了很大一部分运行时间.因此,我寻找了一些替代方法:

However this is quite slow and profiling suggests that it takes up a large proportion of run time. Therefore I sought out some alternative methods:

Marsaglia 1972 拒绝方法

do {
   x1 = 2.0*dsfmt_genrand_open_open(&dsfmtt)-1.0;
   x2 = 2.0*dsfmt_genrand_open_open(&dsfmtt)-1.0;
   S = x1*x1 + x2*x2;
} while(S > 1.0f);


osRay.c._x = 2.0*x1*sqrt(1.0-S);
osRay.c._y = 2.0*x2*sqrt(1.0-S);
osRay.c._z = abs(1.0-2.0*S);

解析笛卡尔坐标计算

azimuthal = 2*PI*dsfmt_genrand_close_open(&dsfmtt);
u = 2*dsfmt_genrand_close_open(&dsfmtt) -1;
w = sqrt(1-u*u);

osRay.c._x = w*cos(azimuthal);
osRay.c._y = w*sin(azimuthal);
osRay.c._z = abs(u);

虽然最后两种方法的运行速度比第一种快,但当我使用它们时,我得到的结果表明它们没有在球体表面生成均匀的随机点,而是给出了有利于赤道的分布.

While these last two methods run serval times faster than the first, when I use them I get results which indicate that they are not generating uniform random points on the surface of a sphere but rather are giving a distribution which favours the equator.

此外,最后两种方法给出了相同的最终结果,但我确信它们是不正确的,因为我正在与分析解决方案进行比较.

Additionally the last two methods give identical final results however I am certain that they are incorrect as I am comparing against an analytical solution.

我发现的每个参考资料都表明这些方法确实产生了均匀分布,但是我没有得到正确的结果.

Every reference I have found indicates that these methods do produce uniform distributions however I do not achieve the correct result.

我的实现是否有错误,或者我错过了第二种和第三种方法的基本思想?

Is there an error in my implementation or have I missed a fundamental idea in the second and third methods?

推荐答案

在单位球体(无论其维度是多少)上生成均匀分布的最简单方法是绘制独立的正态分布并对结果向量进行归一化.

The simplest way to generate a uniform distribution on the unit sphere (whatever its dimension is) is to draw independent normal distributions and normalize the resulting vector.

确实,例如在维度3中,e^(-x^2/2) e^(-y^2/2) e^(-z^2/2) = e^(-(x^2+ y^2 + z^2)/2) 所以联合分布不随旋转变化.

Indeed, for example in dimension 3, e^(-x^2/2) e^(-y^2/2) e^(-z^2/2) = e^(-(x^2 + y^2 + z^2)/2) so the joint distribution is invariant by rotations.

如果您使用快速正态分布生成器(Ziggurat 或 Ratio-Of-Uniforms)和快速归一化例程(谷歌表示快速平方根平方根"),这会很快.不需要调用超越函数.

This is fast if you use a fast normal distribution generator (either Ziggurat or Ratio-Of-Uniforms) and a fast normalization routine (google for "fast inverse square root). No transcendental function call is required.

此外,Marsaglia 在半球上并不均匀.您将在赤道附近有更多点,因为 2D 圆盘上的对应点 <-> 半球上的点不是等距的.最后一个似乎是正确的(但是我没有进行计算以确保这一点).

Also, the Marsaglia is not uniform on the half sphere. You'll have more points near the equator since the correspondence point on the 2D disc <-> point on the half sphere is not isometric. The last one seems correct though (however I didn't make the calculation to ensure this).

相关文章