3

Hy, i'm writing a raytracer, and for that I need to generate n random vectors that are inside an hemisphere oriented by the surface normal. Ideally, I would also like being able to restrict the rays so that the angle with the normal is <= some alpha. I don't require mathematics strictness, it can be an approximation.

What I have been doing is creating an arbitrary tangent frame, and a random vector where the x and y coordinate go from -1 to 1 and the z coordinate from 0 to 1, and then multiplying it with the tangent frame, but for some reason this is making the rays to go along a direction, instead of covering the entire hemisphere. Here's some pseudo code, based on what i'm using, but removed the HLSL clumsy things:

dir = normal

ray.x = GetRandomFloat(-1, 1)
ray.y = GetRandomFloat(-1, 1)
ray.z = GetRandomFloat(0, 1)

N = abs(normal)

if( N.z > N.x and N.z > N.y )
    rt = (1, 0, 0)
else
    rt = (0, 0, 1)

rt = normalize(rt - normal.xzy * dot(rt, In))
rtb = cross(rt, normal.xzy)

rt.xyz = rt.xzy
rtb.xyz = rtb.xzy

ray = normalize(ray.x * rbt + (ray.y * rt + (ray.z * dir)))

If someone can provide some insight into this, I would be grateful. It doesn't need to be code, even a math formula will do. Also, distribution doesn't need to be uniform, just look "good" and 1/0 or 0/0 in some cases are allowed, as they map to INF or NaN, and I can handle that without problems.

EDIT: While a PDF that fits this is interesting, it will require a random number generator based on a PDF, and that's really expensive, and not actually what I'm looking for.

EDIT 2: If it can be done, it would be better not to use inverse trigonometric functions, even if it sacrifices uniformity

EDIT 3: Tried Tryss method, but the results are the same, here's a screen to show what I mean: dirError

It is clear that the rays aren't generated along all directions. I'm using the second method to generate the rays, and then using the same process I had before to orientate it, that is constructing a basis change matrix from the normal and an arbitrary tangent vector. That might be what is wrong, can anyone provide some insight if the code I have posted earlier actually orients the directions from the z up hemisphere to the hemisphere oriented by the vector "normal"

EDIT 4:

I'll try to make the problem more clear.

I want to generate n random rays, in an hemisphere oriented by an arbitrary direction. I do not require an uniform distribution.

The first part has been answered, taking x = rand(-1,1) y = rand(-1,1) z = rand(0,1) and then normalizing, while not uniform, produces acceptable results and is fast enough.

Now the second part is transforming that vector so that it is oriented by an arbitrary direction, in a way that (0,0,1) -> (nx,ny,nz) , where (nx,ny,nz) is the arbitrary vector. The coordinate system for the final vector and the arbitrary directions is a left handed system where x is left and right, z is front and back and y is up and down. I know that this matrix does the transformation I want, because I do the same coordinate change for normal mapping (http://en.wikipedia.org/wiki/Normal_mapping )

(bitangent.x, bitangent.y, bitangent.z)
(tangent.x  , tangent.y  , tangent.z  )
(normal.x   , normal.y   , normal.z   )

Where bitangent is normal X tangent

The problem now is that I only have the "normal" vector, so I need to generate an arbitrary "tangent" vector to construct that matrix. How can I do that, in a way that the rays get properly transformed ( they don't biased to a direction, like in the screen I showed) ? The code I was using earlier is at the top of the page, but it produces the biasing I want to avoid.

Santiago Pacheco
  • 131
  • Have a look there: http://en.wikipedia.org/wiki/Von_Mises%E2%80%93Fisher_distribution – Karl Feb 24 '15 at 14:16
  • Looks interesting. One question, how would I orientate it with the surface normal? Also, there is the big problem that I would need to get some code to generate an random number from the PDF, and that will probably be too expensive for a shader, so I'll have to precompute, which make things more complex. Will edit the original question to clarify the PDF thing – Santiago Pacheco Feb 24 '15 at 14:30
  • Actually, now that I think about it, the orientation part is just making mu = normal right? If that is the case, do you think you can provide some way to generate random numbers that fit that PDF and make this an answer? – Santiago Pacheco Feb 24 '15 at 14:38
  • You better use a rotation matrix to orient the direction from the z-up hemisphere to the hemisphere oriented by your direction vector. – Tryss Feb 24 '15 at 16:09
  • you mean this : http://en.wikipedia.org/wiki/Rotation_matrix ? And getting the angle and axis as I said before? – Santiago Pacheco Feb 24 '15 at 16:30
  • Yes, usually it's far more clear to use rotation matrix (or quaternions) to work with rotations in 3D – Tryss Feb 24 '15 at 18:03

4 Answers4

5

An uniform distribution on a sphere can be calculated like this :

  • $\theta_0 = 2\pi \text{Rand}()$
  • $\theta_1 = \arccos( 1- 2 \text{Rand}())$
  • $x = R \sin(\theta_0)\sin(\theta_1)$
  • $y = R \sin(\theta_0)\cos(\theta_1)$
  • $z = R \sin(\theta_1)$

Source : http://mathproofs.blogspot.fr/2005/04/uniform-random-distribution-on-sphere.html

Another approach that may be more suited to computer is the following algorithm :

do
   x = GetRandomFloat(-1, 1)
   y = GetRandomFloat(-1, 1)
   z = GetRandomFloat(-1, 1)
   d = sqrt(x^2+y^2+z^2)
while(d>1)

x=x/d
y=y/d
z=z/d

And you have your distribution on the sphere. Notice that the number of step may be unbounded, but the probability to not have a correct point after N iterations is less than $\frac{1}{2^N}$, so it's decent : on average only two iterations to get a point on the sphere

Tryss
  • 14,310
  • 1
    Ok, how would I orientate that with the normal? Also, I need an hemisphere, not the entire sphere. At last, is there a way to do this without using inverse trigonometric functions? – Santiago Pacheco Feb 24 '15 at 14:34
  • If you have a point $A$ on the sphere, the vector $\vec{OA}$ is normal to the sphere at point $A$. If you want an hemisphere, it depend of the orientation of the hemisphere, but taking $z= R \text{abs}(\sin(\theta_1))$ gives you the upper hemisphere. I will post another method that doesn't need such function – Tryss Feb 24 '15 at 14:45
  • Maybe normal wasnt the best term ;) I meant that the hemisphere is orientated along an arbitrary axis ( in my case, is the normal of the surface) – Santiago Pacheco Feb 24 '15 at 14:51
  • Another approach added. To orientate the hemisphere along an arbitrary axis, why not make a rotation of the upper hemisphere? – Tryss Feb 24 '15 at 14:51
  • Wouldn't your code be the same as generating x,y,z and then dividing by the norm, instead of looping? Also, for the rotation, i was thinking something along the lines of the cross product of the arbitrary axis and (0,0,1), and then the cosine of the angle from the dot product. Is that correct? – Santiago Pacheco Feb 24 '15 at 15:27
  • No, it isn't the same as generating x,y,z and then dividing by the norm, try both version and see the difference. If you don't take points inside the sphere before dividing by the norm, the diections of corners will be privilegied (you have "more" points in the cube in the corner direction than in the middle of the face diection) – Tryss Feb 24 '15 at 15:30
  • Please see my edit – Santiago Pacheco Feb 24 '15 at 15:57
  • @Tryss, you claim that with the second method you get a uniform distribution on the sphere. Can you prove this statement or is it just your -- maybe strong -- belief? This is not about beliefs --there are other sites -- but about maths. – Karl Feb 24 '15 at 16:28
  • @Karl : The idea is that the mesure of each cone with the same apperture is the same, so when you project it on the sphere, you get the same measure. But the comments are not an appropriate place for a rigourous proof (will try to find a reference) – Tryss Feb 24 '15 at 16:34
  • I implemented the mathematical description mentioned in this answer but it was not uniform. Instead, I implemented the formula as described in the following link: http://corysimon.github.io/articles/uniformdistn-on-sphere/ . Just so future readers can know! – Simon Sirak May 06 '19 at 16:40
3

Have a good idea: 1. generate lot of random points over spherical surface. 2.check cosine value between the normal and each point. If cosine $< 0$, invertir point. And voila!!

Harish Chandra Rajpoot
  • 37,450
Tujo
  • 31
0

As I already said in my comment the best choice is the von-Mises/Fisher distribution something similar to the normal distribution on the n-dimensional sphere, see the cited wikipedi article. Since the OP has problems with the creation of such random vectors, here some references: To simulate random vectors from this distribution see:

http://www.jstor.org/discover/10.2307/2347441?sid=21105943589933&uid=4&uid=2&uid=3737864

or here:

https://stackoverflow.com/questions/4415668/drawing-random-values-from-a-fisher-distribution

or here:

http://luc.devroye.org/rnbookindex.html

@Santiago Pacheco you could have found them all yourself on the net!

Community
  • 1
Karl
  • 710
  • My bad, my bad, this http://stackoverflow.com/questions/4415668/drawing-random-values-from-a-fisher-distribution seems to be what I want, but from what I see, there is quite a good deal of math, exp, log, sqrt and asin, so that's why I find Tryss answer much more suitable. The problem that i need to fix is orientating the hemisphere. – Santiago Pacheco Feb 24 '15 at 16:20
  • but from what I see, there is quite a good deal of math, exp, log and asin – Karl Feb 24 '15 at 16:21
  • what I meant is that if you compare it to the other idea, it is a lot more complex, and I don't really need it to be accurate – Santiago Pacheco Feb 24 '15 at 16:22
  • @Karl : I guess he want a computationnaly fast method, as he will generate a lot of these points – Tryss Feb 24 '15 at 16:29
  • @Tryss, maybe so he gets many points fast, but my question was: Do they have a uniform distribution on the sphere? Can you prove it or do you just believe it. – Karl Feb 24 '15 at 16:32
  • It's for a Global Illumination solver, so I need it to be as fast as possible, given that tracing the rays is already quite slow, and I'll be tracing about 500.000 - 600.000 rays. Considering the tracing stage it's not physically accurate, it's an approximation, I don't really require an uniform distribution – Santiago Pacheco Feb 24 '15 at 16:34
  • @Santiago Pacheco, please WHAT do you want? – Karl Feb 24 '15 at 18:18
  • please see my edit, tried to make is as clear as possible – Santiago Pacheco Feb 24 '15 at 21:14
0

In order to tackle your second challenge, you may want to use Rodrigues' rotation formula, though it would be computationally intensive (basically aligning - or rotating - your set of randomly generated coordinates/vectors along another vector). This second link is another answer on this same site for the same question.

Emanuele
  • 101