Thread: Need help designing a recursive function.

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    87

    Need help designing a recursive function.

    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 :

    Code:
    typedef enum
    {
        PRIMARY_RAY,
        REFLECTED_RAY,
        EDGE_DIFFRACTED_RAY,
        CORNER_DIFFRACTED_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.
    Code:
    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.
    Code:
    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 -
    Code:
    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_intersect(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_field(r);
                /* since ray intersected, a child ray should be created */
                create_child_ray(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_ray(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_ray which should call
    approprate functions for creating the child rays.
    Code:
    void create_child_ray(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_diffracted_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_diffracted_ray();
          }
          else
          {
              create_reflected_ray();
          }
       }
    
    }
    My question is inside the create_reflected_ray or
    create_edge_diffracted_ray or create_corner_diffracted_ray functions,
    can I call the raytrace function ? since the child rays also need to
    be traced recursively. eg:

    Code:
    void create_reflected_ray()
    {
            ray rr; /* reflected ray */
    
            /* initialise reflected ray */
    
             raytrace(&rr);
    
    }
    Also, when the ray undergoes reflection, only one child ray is
    created(reflected 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_diffracted_ray or create_corner_diffracted_ray as below :

    Code:
    void create_edge_diffracted_ray()
    {
          ray edr;
          int i;
    
          for (i = 0; i < MAX_NUMBER_OF_DIFFRACTED_RAYS; i++)
          {
               /* initialise edr */
               raytrace(&edr);
         }
    
    }
    Is this permissible ??

  2. #2
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Is there a particular reason that you think it is not permissible?

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Perhaps you want an array of rays? It depends on how you intend to "initialize edr", I suppose.

    It's syntactically valid C, as far as I can tell, but any compiler could tell you that.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    87
    Quote Originally Posted by dwks View Post
    Perhaps you want an array of rays? It depends on how you intend to "initialize edr", I suppose.

    It's syntactically valid C, as far as I can tell, but any compiler could tell you that.
    Initializing as in intiializing the members of edr. I intend to use only one ray variable and change the value of the members of the variable everytime I want to trace a new ray rather than use an array of structures (which will take up huge memory).
    Last edited by broli86; 07-24-2008 at 12:50 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. error handling in recursive function.
    By broli86 in forum C Programming
    Replies: 4
    Last Post: 06-23-2008, 02:11 PM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM