11 replies to this topic

[broli86]

My project is based on physical simulation of electromagnetic ray propogation. I need to do forward ray tracing i.e. shoot rays from the source.I know you cannot follow all the rays from the source as you can actually shoot rays at
infinite angles,therefore my plan is to launch rays from the
trasmitter in all directions spaced eg. x degrees or something. This
is the earlier logic I have used for a C program -

consider the source to be centre of the unit sphere.

0<=theta<=180(zenith)
0<=phi<=360 (azimuth)

     for (theta = 0;  theta <= 180;  theta += incr) 

     {

            double sint = sin(pi / 180 * theta);

            double cost = cos(pi / 180 * theta);

            for (phi = 0;  phi < 360;  phi += incr)

            {

                P.x = sint * cos(pi / 180 * phi);

                P.y = sint * sin(pi / 180 * phi);

                P.z =  cost;

           }     

     }

P is basically a point on sphere which I calculated using spherical coordinates. Now when I know P and I know the source i.e. center of sphere, I can calculate the direction of ray. Doing so through the loop gives me direction of the rays. I can get finer rays by adjusting incr.

However, I realized a little flaw in my program. At theta = 0 and 180 there is only one ray each so there is no need to loop into phi for that. Also, if I go by this scheme, I get thick bundle of rays near to the poles as compared to the equator. So I changed my program as follows -

treat theta =0 and 180 as special case.

then,

for(theta = incr; theta < 180; theta += incr)

            double sint = sin(pi / 180 * theta);

            double cost = cos(pi / 180 * theta);

{          

            for (phi = 0;  phi < 360;  phi += incr/sin(theta))

            {

                P.x = sint * cos(pi / 180 * phi);

                P.y = sint * sin(pi / 180 * phi);

                P.z =  cost;

           }     


}

I divide incr by sin(theta). With this the spacing between rays is more at the poles so they tend to get bundled up. Also, I calculated this scaling factor by dividing circumference of the horizontal disc at equator which is 2 PI R with circumference of the horizontal disc at a random angle theta i.e. 2 PI R sin(theta).

I would like to know if my new approach is correct or not.

[Reedbeta]

If you want rays to be uniformly distributed over the surface of the sphere, would it work to just choose a large number of random points? Code for getting a uniformly distributed random point on a sphere surface can be found here (see the UniformSampleSphere function).

[broli86]

Reedbeta said:

If you want rays to be uniformly distributed over the surface of the sphere, would it work to just choose a large number of random points? Code for getting a uniformly distributed random point on a sphere surface can be found here (see the UniformSampleSphere function).

Vector UniformSampleSphere(float u1, float u2)
{
float z = 1.f - 2.f * u1;
float r = sqrtf(max(0.f, 1.f - z*z));
float phi = 2.f * M_PI * u2;
float x = r * cosf(phi);
float y = r * sinf(phi);
return Vector(x, y, z);
} [/code]


If this is the code you speak of then I cannot understand it properly like what is u1, u2 , phi etc

[Reedbeta]

u1 and u2 are two uniform random numbers between 0 and 1 that you put into the function. What you get out is a uniform random point on the sphere.

You don't need to worry about how the math actually works but if you're interested: link.

[broli86]

Reedbeta said:

u1 and u2 are two uniform random numbers between 0 and 1 that you put into the function. What you get out is a uniform random point on the sphere.

You don't need to worry about how the math actually works but if you're interested: link.

How to generate two uniform random numbers within a limit(0..1) in C ? Is it the rand function ?

[Kenneth Gorking]

The rand function is only pseudo-random, and it doesn't have an even distribution. You should look around on the net for a random number generator. I would suggest the Mersenne Twister as a place to start :)

[anubis]

There are two additional techniques that might be of interest to you.

The algorithm Reedbeta proposed maps a unit square, which you randomly sample, on a sphere. This allows you to do some interesting optimizations.

- Stratified sampling: Sampling rays over a sphere is like evaluating an integral over the sphere. There is a theorem that states that the value of the integral over a domain is equal to the sum of the integrals of any partitioning of that domain. Well... Since we are sampling a unit square, this allows us to cut up the square in little pieces (smaller squares for example) and sample these squares and add up the result later and be sure, that we arrive at the same point. The advantage of this is, that you can force a more uniform sampling of the square. The disadvantage is that by manually forcing a certain partitioning on the integration domain, you may introduce artifacts.

- Latin Hypercube: This sampling technique works to a similar end but is less crude. At first you start out by cutting up the unit square again and take samples from randomly chosen cells of the partitioning. In a second step you rearrange those samples by building permutations of the cells and rows that were created, when you cut up the square. I can dig up an in depth explanation if you want.

These are just two, but there are more techniques to generate uniformly distributed samples. The problem with many random number generators is that samples are chosen for cryptographic reasons (you want the generation of your samples to be untraceable), rather than for producing uniform distributions, which makes them bad for simulation purposes, so it's wise to look into artificially generated distributions.

Also using these techniques serves to reduce the number of samples that you need to take to get similar quality.

Cheers,
Jan

[broli86]

my requirements have chagned a bit. What I have is the 3D location of
the source and the object(triangular mesh). Now I want to calculate
rays which are going to hit this object only or atleast they are fired
in the objects direction. One idea I had was to compute a bounding
sphere around the object and then compute several points on the
surface of sphere using spherical coordinates along with the surface
normals. Next take only those points on sphere which face the source,
but this method seems extremely costly and it will still lead to some
waste rays. Please give me some direction.

[Reedbeta]

How about picking random points on the object's surface to shoot rays at? I.e. repeatedly pick a random triangle on the object and pick a random point on the triangle.

If you need the rays to be evenly distributed in solid angle at the source, you'll have to be careful with the probabilities, but that's a solvable problem.

[broli86]

Reedbeta said:

How about picking random points on the object's surface to shoot rays at? I.e. repeatedly pick a random triangle on the object and pick a random point on the triangle.

I feel there may be a few problems with this approach -
1. There is not a good C library function for generating random numbers
2.It is quite difficult to get points which are uniformly distributed inside a triangle. Very often, these points will get concentrated near the vertices due to use of barycentric coordinates. There may also be a question of how many points you want to take ?
3. For every point you take on a triangle, you have to do the dot product of normal at that point with the direction vector from source so that you can remove points that are not visible to the source. If there are millions of points do you think this will become a little inefficient ?
4.How does a ray-triangle intersection algorithm fit into all of this ? IF there are multiple reflections, then you require them.

Reedbeta said:

If you need the rays to be evenly distributed in solid angle at the source, you'll have to be careful with the probabilities, but that's a solvable problem.

one other idea i had was to project all the vertices of the object on a circular plane facing the source and then u fire a pencil of rays through this cone. The solid angle subtended by it is : A/r^2. Then starting from theta = 0 u increment the solid angle with small values to reach that figure of A/r^2

[broli86]

btw with back face culling, how to deal with triangles that are partially visible ?

[anubis]

Quote

1. There is not a good C library function for generating random numbers

mersenne twister suggested above is a very fine library :)

Quote

2.It is quite difficult to get points which are uniformly distributed inside a triangle. Very often, these points will get concentrated near the vertices due to use of barycentric coordinates. There may also be a question of how many points you want to take ?

There are however sampling strategies that will give you uniform distribution. For example :

float tmp = sqrt(u);
x = 1 - tmp;
y = v * tmp;

Where (u, v) is a sample of the unit square.