Need help designing a recursive function.

[pereges]

Hello I need some ideas for designing a recursive function for my ray
tracing program.

The idea behind ray tracing is to follow the electromagnetic rays from
the source, as they hit the object.The object is triangulated. The
rays can undergo multiple reflections, diffractions etc of the same
object i.e. a ray hits a surface of the object, undergoes reflection
resulting in a reflected ray which can again hit a surface, corner or
edge creating a reflected ray, diffracted ray etc .

Because multiple interactions with the object is possible, I want to
make the raytracing function recursive.Now, it is possible that the
program can get trapped in an infinite recursion due to rays
constantly bouncing of some triangular surface of the object and new
rays keep getting created. Hence, I use a counter called 'depth' in my
ray data structure. In my program, the maximum depth for a ray is 2.
eg. assume the ray coming from source has a depth of 0, and if the ray
hits an object, the reflected ray would have depth 1. If this
reflected ray hits another surface, once again a reflected ray is
created with depth 2. Child ray's depth = parent ray's depth + 1.

In my program, some calculations need to be performed. Like when a ray
hits some triangular surface, the incident electric field vector
because of this ray must be added to the total incident electric field
vector. Similarly, when the ray exits an object(does not intersect any
triangular surface on the object), we want to calculate some scattered
electric field vector and add it to the total scattered electric field
vector. Let's say if a ray has the maximum depth i.e. 2 and it still
intersects some triangular surface, then the recursion must stop. If
it doesn't intersect any traingular surface, calculate the scattered
field and return.

The data structure for ray :

typedef enum
{
PRIMARY_RAY,
REFLECTED_RAY,
EDGE_DIFFRACTED _RAY,
CORNER_DIFFRACT ED_RAY;

}raytype;

The ray type is used to distinguish between various types of rays i.e.
primary rays, reflected
rays, edge diffracted rays, corner diffracted rays.

typedef struct
{
int depth; /* the depth field as I explained */
vector origin; /* origin of ray */
vector direction; /* direction vector of ray */
vector efield; /* electric field at origin of ray */
double t; /* distance travelled */
raytype type; /* type of ray */

}ray;
I will post the skeleton of some functions I have written :

First, we want to create primary rays or rays originating from the
source having depth 0.

int calc_e_fields()
{
int i;
ray *r

for (i = 0; i < NUMBER_OF_RAYS; i++)
{
create_primary_ ray(&r)
raytrace(r);
free(r);
}
return 0;
}

With the above function, I create as many primary rays as specified by
user, and trace each
and every one of them(including their children rays). For all primary
rays, ray depth = 0 and raytype = PRIMARY_RAY
The ray trace function is recursive -

void raytrace(ray *r)
{
size_t index; /* Index of triangle intersected */
bool res = false; /* result of ray-surface intersection */
double u, v; /* barycentric coordinates used to calculate point of
intersection */

ray_kd_tree_int ersect(r, &index, &res, &u, &v);
/* Above function finds out if ray has intersected triangle, index
of the intersected
triangle, and the barycentric coordinates u and v */
if (r->depth == 2)
{
/* if ray's depth is 2, then check if it intersected any
triangular surface
if it intersected a triangular surface, then return because 2
is maximum depth.
If it did not intersect, then it exited the object so
calculate the scattered field */

if (!res)
{
calc_scattered_ field(r);
}
return;
}
else
{
/* ray depth is either 0 or 1 here */

if (res) /* ray intersected */
{
/* since ray intersected object calculate electric field
*/
calc_incident_f ield(r);
/* since ray intersected, a child ray should be created */
create_child_ra y(r, u, v);
}
else
{
/* ray did not intersect */

if (r->depth == 0)
{
/* if a ray direct from source did not intersect
object, no use of tracing it */
return;
}
else
{
/* if ray did not intersect object, then it has
exited the object*/
/* so calculate the scattered field and return*/
calc_scattered_ field(r);
return;
}
}
}
}
}
Now my problem is with the create_child_ra y(r, u, v) function.

The child ray can be a reflected ray, edge diffracted ray or a corner
diffracted ray.

Based on the value of barycentric coordinates of the point of
intersection i.e. u, v and a third coordinate w (which is 1-u-v , u,v
are always between 0 and 1), the child ray has to be calculated.

The child ray should be a edge diffracted ray if the parent ray had
hit an edge. This is indicated by exactly one of the barycentric
coordinates being 0(any one of u, v or w can be 0 but other 2 cannot
be zero).

The child ray should be a corner diffracted ray if the parent ray had
hit a corner. This is indicated by exactly one of the barycentric
coordinates being 1 and others being 0. 3 possible situations -

u v w
1 0 0
0 1 0
0 0 1

If neither of the above conditions are satisfied, then a reflected ray
must be created as the ray ha hit a point inside the triangle surface,
neither on the edge nor any of the 3 corners of triangle.
So I can write a function create_child_ra y which should call
approprate functions for creating the child rays.
void create_child_ra y(ray *r, double *u, double *v)
{
double w = 1 - *u - *v;

if ( (*u == 0 && *v == 0 && w == 1) ||
(*u == 0 && *v == 1 && w == 0) ||
(*u == 1 && *v == 0 && w == 0))
{
/* ray has hit a corner so create corner diffracted ray*/

create_corner_d iffracted_ray() ;
}
else
{
if ((*u == 0 && *v != 0 && w != 0) ||
(*u != 0 && *v == 0 && w != 0) ||
(*u != 0 && *v != 0 && w == 0))
{
/* ray hit an edge so create edge diffracted ray */

create_edge_dif fracted_ray();
}
else
{
create_reflecte d_ray();
}
}
}
Now my question is inside the create_reflecte d_ray or
create_edge_dif fracted_ray or create_corner_d iffracted_ray functions,
can I call the raytrace function ? since the child rays also need to
be traced recursively. eg:

void create_reflecte d_ray()
{
ray rr; /* reflected ray */

/* initialise reflected ray */

raytrace(&rr);
}

Also, when the ray undergoes reflection, only one child ray is
created(reflect ed ray) but when a ray undergoes diffraction, I need to
simulate the effect with many rays each travelling in different
directions. So in a way a parent ray gives rise to many child rays
each of which must be traced. So I want to write the
create_edge_dif fracted_ray or create_corner_d iffracted_ray as below :

void create_edge_dif fracted_ray()
{
ray edr;
int i;

for (i = 0; i < MAX_NUMBER_OF_D IFFRACTED_RAYS; i++)
{
/* initialise edr */
raytrace(&edr);
}
}

Is this permissible ??

[S James S Stapleton]

"pereges" <Br*****@gmail. comwrote in message
news:b0******** *************** ***********@h17 g2000prg.google groups.com...

[SNIP]

Now my question is inside the create_reflecte d_ray or
create_edge_dif fracted_ray or create_corner_d iffracted_ray functions,
can I call the raytrace function ? since the child rays also need to
be traced recursively. eg:

roughly speaking your question can be trimmed down to:

You have functions:
initiator()
sub1()
sub2()
sub3()

initiator() can call any of sub1(), sub2() or sub3() one or more times, and
it may call more than just one of the functions.
sub1(), sub2(), and sub3() may also call initiator() (directly or through
some other function that they call).

You are asking if this is possible in C? yes. It is dangerous because the
recursion isn't as obvious at first glance through the code.

The trick is - if you pass the same structure to multiple sub functions (or
the same one multiple times), when the depth argument goes up in one, it
goes up in all. If you send copies (and the original variable isn't
updated), then you are safe from this behavior.

Or am I completely off the ball? You may want to make a simpler case example
of your project.
-Jim Stapleton

[pereges]

On Jul 24, 8:23 pm, "S James S Stapleton" <stapleton...@o su.edu>
wrote:

roughly speaking your question can be trimmed down to:

You have functions:
initiator()
sub1()
sub2()
sub3()

initiator() can call any of sub1(), sub2() or sub3() one or more times, and
it may call more than just one of the functions.
sub1(), sub2(), and sub3() may also call initiator() (directly or through
some other function that they call).

You are asking if this is possible in C? yes. It is dangerous because the
recursion isn't as obvious at first glance through the code.

The trick is - if you pass the same structure to multiple sub functions (or
the same one multiple times), when the depth argument goes up in one, it
goes up in all. If you send copies (and the original variable isn't
updated), then you are safe from this behavior.

Or am I completely off the ball? You may want to make a simpler case example
of your project.

Ok roughly speaking this what the whole thing looks like -

void calc_e_field()
{
/* this function is initiator */
/* calling this function starts the who raytracing procedure for
each primary ray */
/* for each primary ray call raytrace function and trace all the
children ray */

....
for (...) /* Should run for all primary rays */
{
..
raytrace(&r);
...
}
....
}

void raytrace(ray *r)
{

/* this is where we trace a ray */
.....
.....
/* if certain conditions are satisfied we want to create a child
ray/rays
created by interaction of ray with surface */

create_child_ra y();
...
...
}

void create_child_ra y()
{
/* here we will call proper function based on the type of child ray
we want to generate */

/* the type of child ray to be generate depends on some conditions
*/

if (some condition 1)
create_reflecet d_ray();
if (some condition 2)
create_edge_dif fracted_ray();
if (some condition 3)
create_corner_d iffracted_ray() ;
}

This is what create_reflecte d_ray, create_edge_dif fracted_ray and
create_corner_d iffracted_ray look like -

void create_reflecte d_ray()
{
ray rr;
/* do some processing and create a reflected ray */

/* now, you want to trace this child ray too and see if it spawns
some more child ray(s) */

raytrace(&rr);
}

the edge_diffracted _ray and corner_diffract ed_ray are similar. They
differ from create_reflecte d_ray in the sense that we want to create
many child rays not just 1 as was the case in reflection. So inside a
for loop we initialise the ray, and then call the raytrace function.

Its like a ray tree.

eg.

(max ray depth = 2)

1. Suppose, primary ray hits the triangular surface (not corner or
edge) spawns a single reflected ray. Add the contribution of this ray
i.e. field at the point of reflection to total incident field.

2. Ray trace the reflected ray. Reflected ray has depth 1.

3. Suppose, reflected ray hits a corner . Add the contribution of
reflected ray i.e. field incident at the corner to total incident
field. Since a corner is hit, reflected ray spawns many diffracted
rays. Each diffracted ray has depth 2.

4. Ray trace each diffracted ray.

5. All those diffracted rays that exit object i.e. do not undergo
further intersection with object(surface, corner or edge), add their
respective contributions to scattered field. return.
For those rays that do intersect the object(which can give rise to
further child rays of depth 3), just don't do anything and return.

[S James S Stapleton]

"pereges" <Br*****@gmail. comwrote in message
news:0d******** *************** ***********@w39 g2000prb.google groups.com...

>roughly speaking your question can be trimmed down to:

You have functions:
initiator()
sub1()
sub2()
sub3()

initiator() can call any of sub1(), sub2() or sub3() one or more times,
and
it may call more than just one of the functions.
sub1(), sub2(), and sub3() may also call initiator() (directly or through
some other function that they call).

You are asking if this is possible in C? yes. It is dangerous because the
recursion isn't as obvious at first glance through the code.

The trick is - if you pass the same structure to multiple sub functions
(or
the same one multiple times), when the depth argument goes up in one, it
goes up in all. If you send copies (and the original variable isn't
updated), then you are safe from this behavior.

Or am I completely off the ball? You may want to make a simpler case
example
of your project.

Ok roughly speaking this what the whole thing looks like -

void calc_e_field()
{
/* this function is initiator */
/* calling this function starts the who raytracing procedure for
each primary ray */
/* for each primary ray call raytrace function and trace all the
children ray */

....
for (...) /* Should run for all primary rays */
{
..
raytrace(&r);
...
}
....
}

void raytrace(ray *r)
{

/* this is where we trace a ray */
.....
.....
/* if certain conditions are satisfied we want to create a child
ray/rays
created by interaction of ray with surface */

create_child_ra y();
...
...
}

void create_child_ra y()
{
/* here we will call proper function based on the type of child ray
we want to generate */

/* the type of child ray to be generate depends on some conditions
*/

if (some condition 1)
create_reflecet d_ray();
if (some condition 2)
create_edge_dif fracted_ray();
if (some condition 3)
create_corner_d iffracted_ray() ;
}

This is what create_reflecte d_ray, create_edge_dif fracted_ray and
create_corner_d iffracted_ray look like -

void create_reflecte d_ray()
{
ray rr;
/* do some processing and create a reflected ray */

/* now, you want to trace this child ray too and see if it spawns
some more child ray(s) */

raytrace(&rr);
}

the edge_diffracted _ray and corner_diffract ed_ray are similar. They
differ from create_reflecte d_ray in the sense that we want to create
many child rays not just 1 as was the case in reflection. So inside a
for loop we initialise the ray, and then call the raytrace function.

Its like a ray tree.

eg.

(max ray depth = 2)

1. Suppose, primary ray hits the triangular surface (not corner or
edge) spawns a single reflected ray. Add the contribution of this ray
i.e. field at the point of reflection to total incident field.

2. Ray trace the reflected ray. Reflected ray has depth 1.

3. Suppose, reflected ray hits a corner . Add the contribution of
reflected ray i.e. field incident at the corner to total incident
field. Since a corner is hit, reflected ray spawns many diffracted
rays. Each diffracted ray has depth 2.

4. Ray trace each diffracted ray.

5. All those diffracted rays that exit object i.e. do not undergo
further intersection with object(surface, corner or edge), add their
respective contributions to scattered field. return.
For those rays that do intersect the object(which can give rise to
further child rays of depth 3), just don't do anything and return.

Unless I'm wrong, that's a simplification of what I described, tooled
towards raytracing. As I said, yes, that's permissable.

-Jim Stapleton

[pereges]

On Jul 24, 9:10 pm, "S James S Stapleton" <stapleton...@o su.edu>
wrote:

Unless I'm wrong, that's a simplification of what I described, tooled
towards raytracing. As I said, yes, that's permissable.

Then what were you trying to explain about ray depth ?

ray depth for all the primary rays created in calc_e_fields function
should be initialised to zero.

Then, for a child ray, depth = parent ray depth + 1.

[pereges]

I was wondering if I could solve it with better approach though. The
last time I executed the program(kept the number of rays very high),
the process got killed after some iterations. Don't know if it has
something to do with the memory usage or the nature of recursion. I've
heard recursion makes things slow.

[S James S Stapleton]

"pereges" <Br*****@gmail. comwrote in message
news:2d******** *************** ***********@o40 g2000prn.google groups.com...

On Jul 24, 9:10 pm, "S James S Stapleton" <stapleton...@o su.edu>
wrote:

>Unless I'm wrong, that's a simplification of what I described, tooled
towards raytracing. As I said, yes, that's permissable.

Then what were you trying to explain about ray depth ?

ray depth for all the primary rays created in calc_e_fields function
should be initialised to zero.

Then, for a child ray, depth = parent ray depth + 1.

Are you talking about my reply that wasn't to the list? That's a different
matter entirely, and shouldn't be discussed on this list (very off topic).
It would go on a '3d' list. Mostly it was a set of ideas for adding
interesting effects.

Aside from the last couple sentences, everything I have said has
intentionally abstracted out the raytracing elements, making it generic. You
asked if your setup was possible in C, the subject indicated the question
was in regards to recursion. Basically, you have, lacking the theoretical
knowledge of what it is actually called, an indirect recursion. A direct
recursion would be where one function calls itself. An indirect recursion
would be where one function calls other function(s), which may in turn call
other function(s) creating a chain leading back to the first function being
called again. That is acceptable in C as far as I know. Although, if I
remember correctly, A stack overflow may occur if you recurse too deeply.
With a depth of 2 (4-6 function calls deep in your sample?) that's not
likely to happen.

-Jim Stapleton

[S James S Stapleton]

"pereges" <Br*****@gmail. comwrote in message
news:1a******** *************** ***********@k36 g2000pri.google groups.com...

>I was wondering if I could solve it with better approach though. The
last time I executed the program(kept the number of rays very high),
the process got killed after some iterations. Don't know if it has
something to do with the memory usage or the nature of recursion. I've
heard recursion makes things slow.

THis is going more into comp.programmin g I think, but roughly speaking, you
need a simplified test case to find out why it's failing. There's a lot of
areas in that code where the potential for failure exists.

Can you simplify the test case - make it so you have only a small number of
rays, possibly only tracing the first ray in an image, and quit after that?
With that and a simple diagnostic function set (see the end of the file),
you can fairly easily figure out where things are going wrong most of the
time (if the problem is within your code).

If you use the code at the end of this message, and increase the RTDBG_DEPTH
when the recursion level goes up, decreasing it when it goes down, you
should get a fairly nice set of output, showing you where your program is
getting caught. You simply put the appropriate RTDBG() statement in various
places, showing variables or interest (or simply that you've reached that
point in code execution).

-Jim Stapleton


in a debug.h file (this code is close, I use something simpler since I'm not
dealing with recursion):

#ifdef DEBUG
extern int RTDBG_DEPTH; /*set to 0 in the C file that defines it*/
#include <stdio.h>
#include <malloc.h>
#define RTDBG(A) \
if(1) /*gives it a block, this should prevent the variables from
conflicting with more than one debug in a setup*/ \
{ \
fprintf(STDERR, "%04d>DEBUG : % 15s(%05d)" ## A, RTDBG_DEPTH, __file__,
__line__); \
}
/*code omitted for the following, it's fairly straightforward , just add the
letters shown to the end of the printf arg list*/
#define RTDBG1(A, B)
#define RTDBG2(A, B, C)
#define RTDBG3(A, B, C, D)
#define RTDBG4(A, B, C, D, E)
#define RTDBG5(A, B, C, D, E, F)
#else
#define RTDBG(A)
#define RTDBG1(A, B)
#define RTDBG2(A, B, C)
#define RTDBG3(A, B, C, D)
#define RTDBG4(A, B, C, D, E)
#define RTDBG5(A, B, C, D, E, F)
#endif

[Malcolm McLean]

"pereges" <Br*****@gmail. comwrote in message

Hello I need some ideas for designing a recursive function for my ray
tracing program.

Now my question is inside the create_reflecte d_ray or
create_edge_dif fracted_ray or create_corner_d iffracted_ray functions,
can I call the raytrace function ? since the child rays also need to
be traced recursively. eg:

Yes, C functions can be mutually recursive.

However to keep the number of rays within bounds you need to trace
backwards, from the eye to the light.

So start by casting a ray from the user's eye, or camera, to the corner
pixel. The continue until you hit an object.

If that object is a light, then you've got your pixel colour.

If it is a black body, you've also got your pixel.

If it is reflective then cast rays from the point of intersection to all
your light sources in the scene, to determine the colour of light coming
into the surface at that point. Then use the reflectivity to calculate the
colour of the surface.

Then you've got recursion to worry about. You can go back as many steps as
you want. Note this is no longer photrealistic. To be photrealistic we'd
have to cast rays from the surface in every direction, which would take too
long. So we just cast rays directly to the lights.

If you have refraction or non-point lightsources, that adds another layer of
complexity. I'd get a raytracer with point lights and simple refective
surfaces working first.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Gordon Burditt]

>Hello I need some ideas for designing a recursive function for my ray

>tracing program.

The idea behind ray tracing is to follow the electromagnetic rays from
the source, as they hit the object.The object is triangulated. The
rays can undergo multiple reflections, diffractions etc of the same
object i.e. a ray hits a surface of the object, undergoes reflection
resulting in a reflected ray which can again hit a surface, corner or
edge creating a reflected ray, diffracted ray etc .

One approach I have used for problems similar to this, including
shortest-path or best-move calculations for games, is a queueing
setup to turn recursion into a loop.

1. Initially put some work to do (e.g. the initial rays) on the queue.
2. Loop over the process until you run out of work:
2a. Take an item off the queue.
2b. Process it (possibly involves saving the final state).
2c. If it generates any children, add them to the queue to be
done later. (depending on the situation, this may involve
removing duplicates).
3. You're done.

Some things that can be done with the queue include sorting it by
priority, so, for example, you do all the 0-depth rays done before
doing any 1-depth rays, or sort rays by intensity, and you might
at some point after a given amount of CPU decide that you have a
good enough approximation. Duplicate elimination may also help you
get out of loops.