Next try.


The version below isn't as fast as my C++ version as it doesn't use a
BBOX tree for the inverted children. Timing values for a level 4
menger sponge are:

Original Version: 2207 seconds
this C Version:    523 seconds
my C++ Version:     35 seconds

benchmark.pov, rendered with -w384 -h384 +a0.3 +v -d -f -x

Original Version: 5987 seconds
this C Version:   4280 seconds

 
Add this flag to objects.h:

#define CSG_SIBLING_IGNORE_FLAG 0x2000000L /*AKA: csg internal flag*/

/*****************************************************************************
*
* FUNCTION
*
*   All_CSG_Intersection_Intersections
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   Sep 1994 : Added code to count intersection tests. [DB]
*   Dec 2003 : Changes to enable early escape and reduce number of
*              'Inside_Object()' tests. [AKA] 
*
******************************************************************************/

static int All_CSG_Intersect_Intersections (OBJECT *Object, RAY *Ray,
ISTACK *Depth_Stack)
{
  int Maybe_Found, Found;
  OBJECT *Current_Sib;
  ISTACK *Local_Stack;
  INTERSECTION *Sibling_Intersection;

  Increase_Counter(stats[Ray_CSG_Intersection_Tests]);
  
  /* To get an intersection for a CSG-Intersection object, it must be
     inside of all siblings. If a ray misses one ore more siblings
     completely, the CSG-Intersection isn't hit by this ray. */

  Local_Stack = open_istack ();

  /* 1st step: get intersection points of all children */
  for (Current_Sib = ((CSG *)Object)->Children;
       Current_Sib != NULL;
       Current_Sib = Current_Sib->Sibling)
    {
    if (Ray_In_Bound (Ray, Current_Sib->Bound) && 
        All_Intersections (Current_Sib, Ray, Local_Stack))
      {
      /* the child's intersection points have been added to
         'Local_Stack', clear the 'ignore' flag. */
      Clear_Flag(Current_Sib, CSG_SIBLING_IGNORE_FLAG);
      continue; /* try the next one */
      }

    /* If we reach here, the ray was out-of-bounds and/or the child
       wasn't hit. */
    if (!Inside_Object(Ray->Initial, Current_Sib))
      {
      /* Ray's origin is outside of 'Current_Sib' and doesn't hit any
         of it's boundaries ==> we can escape here. */
      close_istack (Local_Stack);
      return(false);
      }
    else
      {
      /* Ray's origin is inside of 'Current_Sib' and doesn't hit any
         of it's boundaries, so the entire ray is inside of
         'Current_Sib'.
         ==> this sibling can be ignored in the 2nd step as any
             intersection is inside of it, so set the 'ignore' flag.*/
      Set_Flag(Current_Sib, CSG_SIBLING_IGNORE_FLAG);
      }
    }

  /* 2nd step: for each entry in 'Local_Stack' check whether the
     intersection point is inside of each sibling */

  Found = false;

  while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
    {
    Maybe_Found = true;

    for (Current_Sib = ((CSG *)Object)->Children;
         Current_Sib != NULL;
         Current_Sib = Current_Sib->Sibling)
      {
      if (Test_Flag(Current_Sib, CSG_SIBLING_IGNORE_FLAG) ||
          (Current_Sib == Sibling_Intersection->Object))
        continue; /* with the next sibling */

      if (!(Current_Sib->Type & LIGHT_SOURCE_OBJECT) ||
          ((LIGHT_SOURCE *)Current_Sib)->Children)
        {
        if (!Inside_Object (Sibling_Intersection->IPoint,
                            Current_Sib))
          {
          Maybe_Found = false;
          break; /* try the next intersection */
          }
        }
      }

    if (Maybe_Found)
      {
      if (Point_In_Clip (Sibling_Intersection->IPoint, Object->Clip))
        {
        if (Test_Flag(Object, MULTITEXTURE_FLAG))
          {
          Sibling_Intersection->Csg = Object;
          }

        push_copy(Depth_Stack, Sibling_Intersection);

        Found = true;
        }
      }
    }

  close_istack (Local_Stack);

  if (Found)
  {
    Increase_Counter(stats[Ray_CSG_Intersection_Tests_Succeeded]);
  }

  return (Found);
}

Post a reply to this message