Raycasting Evenly in Arbitrary Hemisphere?

I decided to put this in B3D Programmming because it's very 3D and probably makes more sense here than in General.

I'm trying to work out a method of raycasting a hemisphere which has to be aligned to the normal of a surface. EG: if the surface normal is -1,0,0 then the hemisphere would extend to 0,1,0 and 0,-1,0 in a complete 360 arc on the x axis but only 180 degrees on the z axis. Ah heck, a picture's worth 1000 words, so here's a pic.



The red arrows point *at* the vertex, in the *direction* of the normal.

I want to cast rays out, only through that hemisphere and with a configurable, even distribution. In other words, I want to be able to specify the density of the raycasts so that I can do lots or few, depending on how accurate I want to be.

I'm just struggling with the maths to get the vector to cast, because it has to be relative to an arbitrary normal and then evenly within that hemisphere.

My gut tells me I should be using some kind of points on a sphere algorithm and then discaring half of the points by comparing to the surface normal somehow, but I'm not 100% sure if that's right or how go to about it.

Basically, I guess you're going to need some code to rotate a 3D vector, which will probably require some matrix math. Then, you can rotate the vector around the base of the hemisphere, rotate the vector 'up' by x amount, and repeat until the entire hemisphere is scanned. Gah, does that make sense?

[edit] Actually, I'm informed it is possible to do 3d vector rotation without the use of matrices.

Yeah, I have a function which will rotate a vector to any given quaternion orientation. Your description of covering the hemisphere line by line, rotating up a little at each stage does make sense. That only leaves me with the question of orienting all that to the surface. However, I guess the best way to do that would be afterward. Precalculate a set of vectors for a 0,1,0 normal oriented hemisphere and then rotate them all wholesale to the orientation of each normal as I go.

Yeah, it sounds ok in theory. I'll have a go at coding it up. Thanks for the idea.

Here are some notes I made a while back which should be of some help. The idea here was to be able to specify a point on a sphere, and then find random points around that point that had a uniform distribution. One's first instinct would be to just use polar coordinates to calculate these points, but doing so results in pole clustering.

What's pole clustering?

If you imagine a camera pointing 45 degree up, and you turn, taking a photo every 45 degrees, and then point it straight up and do the same thing, you'll understand that the center of all the images on the second set are actually the same point. That's pole clustering. If you use polar coordinates with the center point being one of the poles, then you'll get a lot more points around the central point than out a ways from it.


Anyway here's the algorithm which avoids the pole clustering issue:


Finding uniform random points around a point on a sphere:
---------------------------------------------------------

Find a point on the unit sphere:
P = (a,b,c)

The first step is to find a point N on the unit sphere which is 90 degrees (arc length) away.

N = (a/sqrt(a^2+b^2) , -b/sqrt(a^2+b^2), 0)
will work unless a=b=0.

now let T = PxN. so P,N,T are at right angles to each other

now let's see. we want to parameterize the circle of radius r centered at P

R = P*cos(r) + N*sin(r)*cos(t) + T*sin(r)*sin(t) should work

pick a random angle t between 0 and 360 and you have a random point in the circle

So in sphere space using P(0,0,1) N(0,1,0) T(1,0,0):

r = radius from point at 0,0,1
t = random number between 0 and 360

Rx = sin(r)*sin(t)
Ry = sin(r)*cos(t)
Rz = cos(r)


So "point on the unit sphere" = Your surface normal.
Radius = Random number from 0 to 180, for a hemisphere centered on the tip of your normal.
T = Random number from 0 to 360.

You'll have to figure out how that works into the stuff above cause I have to go eat dinner and I wrote this so long ago I forget how you calculate it but it's all there in the notes. :-)

This may be of some help too:



Finding UNFORM random points on a sphere: (Ie: no pole clustering)
----------------------------------
choose a random angle t and a random number z between -1 and 1, then let r=sqrt(1-z^2), x=r*cos(t), y=r*sin(t).
then (x,y,z) is a random point on the sphere
(of radius 1, centered at the origin)


OR:

To generate a random point on the sphere, it is necessary only to generate two random numbers,
z between -R and R,

phi between 0 and 2 pi, each with a uniform distribution

To find the latitude (theta) of this point, note that z=Rsin(theta), so:

theta=sin-1(z/R)

its longitude is phi.

In rectilinear coordinates:

x=R*cos(theta)*cos(phi)
y=R*cos(theta)*sin(phi)
z=R*sin(theta)=z

Note that in both methods points will appear to be clustered if you attempt to step through it. The lattitude lines become more sparse as the longitude lines become

more dense, so random points will be evenly distributed, but if you plot even lonigtude lines it will look wrong.



if you enclose a sphere in a cylinder (with no top or bottom) then the sphere and the cylinder have the same surface area.

moreover,if you project from the cylinder to the sphere, towards the axis of the cylinder, then this projection preserves area.

so, to choose random points on a sphere, you can just choose random points on a vertical cylinder, then project the points horizontally to the sphere.

The height of the cylinder is the diameter of the sphere.

Yeah, this 'pole clustering' effect of the method I described did occur to me. However, I figured as this is for raycasting maybe taking more samples nearer to the pole would be a good thing?

Thanks a lot for all the reading material, SSwift. I think I'm generating some spheres with nicely distributed points now. I'm discarding all the vectors with Y<0 to get my hemisphere, so all that's left is to find the angle ( as a quaternion ) between any two given normals. It's probably simple, but I can't for the life of me remember how.