# Photon mapping questions

## Recommended Posts

ZiM    146
Hi! I'm interested in writing 3D renderer that uses Real-time Photon Mapping (as per Tim Joznowski's thesis). I have couple of questions for which I couldn't find answer in the thesis: * Given two random polar coordinates, theta = [0..pi/2] and phi = [0..2*pi], how do I calculate a point on the surface of a hemisphere lying on an arbitrary plane? I understand that if the plane normal is coincident with Z-axis, it can be done like this:
v.x = sin(theta)*cos(phi)
v.y = sin(theta)*sin(phi)
v.z = cos(theta)

But how is this generalized for arbitrary planes? I ask this because this is obviously needed for the diffusive reflections. * Why use polar coordinates at all? Why shouldn't we instead use unit vectors to store the incident angles and generate the reflection vectors directly from them? Has this something to do with being able to uniformly generate random diffusive reflection vectors?

##### Share on other sites
JuNC    236
You can create an orthonormal basis aligned with the normal of the plane, e.g.:

normal is the normal of the plane.

 epsilon = 0.001  w = normalize( normal ) u = cross (w, vector3(1,0,0) )  if( length(u) < epsilon )   u = cross( w, vector3(0,1,0) ) u = normalize( u ) v = cross( w, u )

(This perhaps isn't the best way to do it, but it works ok).

You can now rotate the computed vector into the basis:

 x = sin(theta)*cos(phi) y = sin(theta)*sin(phi) z = cos(theta) x' = x * u y' = y * v z' = z * w

(x',y',z') will now be your vector. The use of polar coordinates is usually to facilitate computing cosine weighted (or some other weighting) vectors, e.g.:

 r1, r2 = uniform random numbers in [0..1] cos_theta = sqrt (1.0 - (r1))  phi = 2.0 *. pi *. (r2) sin_theta = sqrt (1.0 -. sqr cos_theta)  x = (cos phi *. sin_theta) y = (sin phi *. sin_theta) z = (cos_theta)

##### Share on other sites
Eelco    301
Quote:
 Original post by ZiM* Given two random polar coordinates, theta = [0..pi/2] and phi = [0..2*pi], how do I calculate a point on the surface of a hemisphere lying on an arbitrary plane?

impossible.

its an indetermined problem. youd need a full coordinate basis, not just a normal, to relate your polar coordinates to in a meaningfull way.

if you want to generate uniformly distributed random vectors on a sphere, there are better methods that do not involve polar coordinates. are you sure that in this paper, polar coordinates are not just purely used for graphs/proofs? they are generally a poor tool for actual implementations.

##### Share on other sites
JuNC    236
It's not impossible, and since the distribution is invariant with rotation around the normal you can just pick any basis you want. If the distribution is not invariant then you likely have a second direction vector to fix the rotation (e.g. a phong distribution).

##### Share on other sites
Max_Payne    757
Quote:
Original post by Eelco
Quote:
 Original post by ZiM* Given two random polar coordinates, theta = [0..pi/2] and phi = [0..2*pi], how do I calculate a point on the surface of a hemisphere lying on an arbitrary plane?

impossible.

its an indetermined problem. youd need a full coordinate basis, not just a normal, to relate your polar coordinates to in a meaningfull way.

if you want to generate uniformly distributed random vectors on a sphere, there are better methods that do not involve polar coordinates. are you sure that in this paper, polar coordinates are not just purely used for graphs/proofs? they are generally a poor tool for actual implementations.

What are you saying?

I did this in my raytracer to find a random diffusely reflected vector... All you need is a normal vector for the plane.

Once you have this normal, you can find the orthogonal complement of its system (elementary linear algebra). This will give you two vectors that are perpendicular to the normal. You can then make the two vector orthogonal to one another using linear algebra techniques. You can then easily find a point on the unit sphere using the orthonormal basis made of the normal and the two orthonormal vectors you have just created.

However... This might be what you mean. A specific set of polar coordinates is going to be meaningless, as the orthonormal basis that is generated is unpredictable. But in this case, they are random polar coordinates, so it doesn't really matter.

##### Share on other sites
Guest Anonymous Poster
Avoid polar coordinates completely.

Create a random vector distributed uniformly on the sphere.
(generate random x,y,z, if x^2+y^2+z^2 > 1 or too close to centre then generate new vector else divide by length)

Now if dot(vector, normal)<

##### Share on other sites
Guest Anonymous Poster
Reposted because of HTML errors,

Avoid polar coordinates completely.

Create a random vector distributed uniformly on the sphere.
(generate random x,y,z, if x^2+y^2+z^2 > 1 or too close to centre then generate new vector else divide by length)

Now if dot(vector, normal) < 0 then vector = -vector
this flips the half of the sphere facing away from the normal onto the half facing in the same direction as the normal, thus giving a hemisphere about the normal.

##### Share on other sites
Eelco    301
Quote:
 Original post by JuNCIt's not impossible, and since the distribution is invariant with rotation around the normal you can just pick any basis you want. If the distribution is not invariant then you likely have a second direction vector to fix the rotation (e.g. a phong distribution).

uhm yeah you can pick any basis you want, but dont you implicitly agree by making such a statement the normal alone is not enough information?

##### Share on other sites
Eelco    301
Quote:
Original post by Max_Payne
Quote:
Original post by Eelco
Quote:
 Original post by ZiM* Given two random polar coordinates, theta = [0..pi/2] and phi = [0..2*pi], how do I calculate a point on the surface of a hemisphere lying on an arbitrary plane?

impossible.

its an indetermined problem. youd need a full coordinate basis, not just a normal, to relate your polar coordinates to in a meaningfull way.

if you want to generate uniformly distributed random vectors on a sphere, there are better methods that do not involve polar coordinates. are you sure that in this paper, polar coordinates are not just purely used for graphs/proofs? they are generally a poor tool for actual implementations.

What are you saying?

I did this in my raytracer to find a random diffusely reflected vector... All you need is a normal vector for the plane.

Once you have this normal, you can find the orthogonal complement of its system (elementary linear algebra). This will give you two vectors that are perpendicular to the normal. You can then make the two vector orthogonal to one another using linear algebra techniques. You can then easily find a point on the unit sphere using the orthonormal basis made of the normal and the two orthonormal vectors you have just created.

However... This might be what you mean. A specific set of polar coordinates is going to be meaningless, as the orthonormal basis that is generated is unpredictable. But in this case, they are random polar coordinates, so it doesn't really matter.

it might not really matter for the endresult, but i see little reason for using this approach, as its inefficient, too much code, and mathematicly extremely unelegant.

##### Share on other sites
Eelco    301
Quote:
 Original post by Anonymous PosterReposted because of HTML errors,Avoid polar coordinates completely.Create a random vector distributed uniformly on the sphere.(generate random x,y,z, if x^2+y^2+z^2 > 1 or too close to centre then generate new vector else divide by length)Now if dot(vector, normal) < 0 then vector = -vectorthis flips the half of the sphere facing away from the normal onto the half facing in the same direction as the normal, thus giving a hemisphere about the normal.

amen.

##### Share on other sites
ZiM    146
Quote:
 if you want to generate uniformly distributed random vectors on a sphere, there are better methods that do not involve polar coordinates. are you sure that in this paper, polar coordinates are not just purely used for graphs/proofs? they are generally a poor tool for actual implementations.

Yup, I'm sure of that. I also found one photon map implementation where they used polar coordinates to represent the incident angle. The paper suggests that polar coordinates for diffusive reflection are calculated like this:
theta = acos(sqrt(R1));phi = 2*pi*R2;

where R1 and R2 are random numbers in range [0..1]. I wrote a quick OpenGL test app and seems this way the points get uniform distribution over the surface of hemisphere - points don't bunch together at the pole. I think that's the reason why random vectors are generated using polar angles. On the other hand, if theta was just 2*pi*R1, dense point concetration at the pole would occur.

##### Share on other sites
JuNC    236
Quote:
 Original post by Eelcouhm yeah you can pick any basis you want, but dont you implicitly agree by making such a statement the normal alone is not enough information?

I'll give you that if you take back your 'impossible' ;) You knew what he was asking.

ZiM - the equations you've posted there give you a cosine weighted distribution (it's exactly the 'code' I posted - admittedly I missed some of the formatting coz I'm lazy and just pasted it from OCaml).

You don't necessarily want a uniform distribution (depends on what you're trying to sample - if it's a lambertian diffuse material you definitely want cosine weighting).

You can use rejection sampling, but to get the cosine weighting you've got to do it slightly differently:

float a,b,c  while (true) {    a = random number between -1 and 1    b = random number between -1 and 1    if (a*a + b*b < 1) break;  }  c = sqrt(1 - (a*a + b*b))  R = a*U + b*V + c*N

(excerpted from here coz I'm lazy and use google)

EDIT: sorry, missed the flipping bit the AP posted, it's essentially equivalent to above, you'll have to add up the ops yourself to work out which is better (note for the disc method here you still need to generate an ONB).

Does anyone have a source that mentions the exact distribution given by the APs method? I don't believe I've seen it recommended anywhere?

[Edited by - JuNC on July 4, 2005 3:30:54 PM]

##### Share on other sites
Eelco    301
Quote:
 Original post by ZiMThe paper suggests that polar coordinates for diffusive reflection are calculated like this:theta = acos(sqrt(R1));phi = 2*pi*R2;

yes, thats one valid mathematically compact way of writing things. the method the AP posted above however, produces the exact same result. it uses, everything taken into account, less code and a lot less cpu cycles. at the same time it cirumvents the problem you inquired about in your OP.

##### Share on other sites
ZiM    146

Quote:

Quote:
 Create a random vector distributed uniformly on the sphere.(generate random x,y,z, if x^2+y^2+z^2 > 1 or too close to centre then generate new vector else divide by length)Now if dot(vector, normal) < 0 then vector = -vector

the method the AP posted above however, produces the exact same result. it uses, everything taken into account, less code and a lot less cpu cycles.

How come? I thought that looping until three random numbers satisfy some condition and evaluating an if statement each cycle would be slower. All that is omitted is one acos() call.

I have one more question about the Photon Mapping algorithm:
* The thesis says that once positions of some photons in the KD-tree are overwritten/updated, the tree needs to be balanced. Does 'balancing' mean that whole KD-tree is calculated from scratch again?

##### Share on other sites
Eelco    301
Quote:
 Original post by ZiMHow come? I thought that looping until three random numbers satisfy some condition and evaluating an if statement each cycle would be slower. All that is omitted is one acos() call.

well, the expected number if iterations is probably something around 1.5, so its not that bad. acos is slow, and on top of that its not all the code, as youll also need the code that generates a base, sin & cos, etc.

maybe once you need more complicated distribution patterns, workng in polar coordinates might pay off, but thats only a guess.