As promised in my previous post, here is my intersection routine. You
cannot use it directly as it's a C++-ified version, but i think you'll
get the general idea behind it. It's *much* faster than the original
version.

//============================================================================
// CSG_INTERSECTION::AllObjectIntersections:
//
//    Author: POV-Ray Team

/*  AKA:
    To get an intersection for a CSG-Intersection object, it must be
    contained within all objects (TODO: if the given objects don't
    overlap anywhere, detect it during the parsing stage.)
    So the original algorithm loops twice over all objects:
      The outer loop retrieves all intersection points for each of the
      objects.
      The inner loop checks, whether any of these intersections is
      inside of all other objects (which would lead to a hit).
    It's short and simple, bot not very effective. 
    Imagine i.e. the following difference object,
    
    difference
      {
      union { ...} // A complex union
      object { small_sphere1 }
      ...
      object { small_sphere1000 }

      ... // texture etc.
      }

    to create a sponge. Assume a ray that results in 1000 intersection
    points from the union, but no hit for the inverted small spheres.
    The latter means: No hit but the ray's origin is inside of each of
    the inverted spheres, so the entire ray is inside of each of the
    spheres.
    ==> It's not necessary do any sphere-inside-test for any of the
        intersection points.

    I changed it to three independend steps:
    
    1. Retrieve all intersections of the not-inverted children:
       If a child is not intersected:
         if ray's origin is outside of this child, the whole CSG isn't
         intersected, else the entire ray is inside of this child, so
         it can be ignored completely in 3.
       Else, the intersections and the child are stored for step 3.
    2. Same as 1. for all inverted children.
       They are handled seperately because of a BBOX tree effectively
       speeds up calculations:
       If a finite node isn't hit, we can ignore any of it's leaf
       objects as the entire ray must be inside of each leaf object.
       This saves a lot of intersection tests.
    3. Each intersection, that is inside of each of the children
       retrieved above, is a valid CSG intersection.

    It doesn't make sense to use the not-inverted children in a BBOX
    tree. The CSG's BBOX is computed as the intersection of all
    not-inverted children bounding boxes.
    If a ray hit's the CSG's BBOX, it will also hit each BBOX of each
    not-inverted child.
*/

bool CSG_INTERSECTION::AllObjectIntersections(RAY &Ray, ISTACK
*Depth_Stack, DBL BestDepth) const
  {
  bool maybeFound(false), found(false), escape(false),
rayFlagsTest(false);
  OBJECT *o;
  int childIdx;
  void *IntersectionCSG = GetFlagMultiTextured() ? (void*) this :
NULL;

  Increase_Counter(stats[Ray_CSG_Intersection_Tests]);
  
  OBJECTLIST *hitQueue   = ObjectListPool.Request();
  ISTACK     *localStack = IstackPool.Request();
  
  // First stage: 
  // Test all not-inverted objects, try to escape as early as
possible.
  for (childIdx = 0; !escape && (childIdx < m_notInvChildren.size());
++childIdx)
    {
    o = m_notInvChildren[childIdx];

    if (o->AllIntersections(Ray, localStack, BOUND_HUGE))
      hitQueue->push_back(o);
    else
      {
      if (!o->Inside(Ray.Initial))
        {
        // The entire ray is outside of >o<, we can escape now.
//        SetAsFirstSib(childIdx);
        escape = true;
        }
      // else the ray starts from within >o< never hitting any
      // boundary, it can be ignored completely.
      }
    }

  // Second stage: Get all intersections of the inverted objects
  if (!escape)
    {
    if (BBox_Tree != NULL)
      escape = IntersectCsgIntersectionTree(BBox_Tree, hitQueue, Ray,
localStack);
    else
      {
      // No BBox Tree of inverted siblings, step through children
list.
      for (childIdx = 0; !escape && (childIdx < Children.size());
++childIdx)
        {
        o = Children[childIdx];

        // Test objects AABB before intersection test
        if (!o->BBoxTestPassed(Ray, BOUND_HUGE))
          {
          // no AABB hit
          if (!o->Inside(Ray.Initial))  // entire ray is outside of
>o<
            escape = true;

          continue; // with next object or escape
          }

        if (o->AllIntersections(Ray, localStack, BOUND_HUGE))
          hitQueue->push_back(o);
        else
          {
          if (!o->Inside(Ray.Initial))
            {
            escape = true;
            break;
            }
          }
        }
      }
    }

  // Third stage: Now we have a list of intersections in 'localStack'
and a
  // list of intersected objects in 'hitQueue'.
  // Get all intersections, that are inside of all objects.
  if (!escape)
    {
    for (int i = 0; i < localStack->size(); ++i)
      {
      maybeFound            = true; // new intersection to be checked
      INTERSECTION &locIsec = (*localStack)[i];
      const OBJECT *obj     = locIsec.Object;
      VECTOR       &iPoint  = locIsec.IPoint;

      if ((locIsec.Depth < BestDepth) && PointInClip(iPoint))
        {
        for (int j = 0; j < hitQueue->size(); ++j)
          {
          const OBJECT *hitObject = (*hitQueue)[j];

          if ((hitObject != obj) && !hitObject->Inside(iPoint))
            {
            maybeFound = false; // missed object '(*hitQueue)[j]'
            break;              // try the next intersection
            }
          }

        if (maybeFound)
          {
          found = true;
          INTERSECTION &isec = push_copy(Depth_Stack, locIsec);
          isec.Object = this;
          if (NULL != locIsec.Csg) // the child is a CSG itself
            isec.Csg = locIsec.Csg;
          else // it was a simple child
	        isec.Csg = locIsec.Object;
          }
        }
      }
    }
  
  IstackPool.Release(localStack);
  ObjectListPool.Release(hitQueue);
  
  if (found)
    Increase_Counter(stats[Ray_CSG_Intersection_Tests_Succeeded]);
  
  return(found);
  }

Post a reply to this message

On Tue, 09 Dec 2003 12:05:19 GMT, kai### [at] siemenscom (Andreas Kaiser)
wrote:
> It's *much* faster than the original version.

I'm sure any measurable impresssion :-) from rendering the same (benchmark)
scene with the old and new code with binaries made by the same compiler would
be appreciated (together with statistic output of POV-Ray).

ABX

Post a reply to this message

ABX <abx### [at] abxartpl> wrote:

>On Tue, 09 Dec 2003 12:05:19 GMT, kai### [at] siemenscom (Andreas Kaiser)
>wrote:
>> It's *much* faster than the original version.
>
>I'm sure any measurable impresssion :-) from rendering the same (benchmark)
>scene with the old and new code with binaries made by the same compiler would
>be appreciated (together with statistic output of POV-Ray).
>

Tomorrow (I'm in the office now :).

Bye,

Andreas

Post a reply to this message

In article <3fd5b6d3.1022837913@news.povray.org> , kai### [at] siemenscom 
(Andreas Kaiser) wrote:

> cannot use it directly as it's a C++-ified version,

BTW, also your work sounds very interesting and nice, it has zero chance of
making it into an official POV-Ray if it does not follow the current code.
It is absolutely pointless to simply convert the current code to C++ classes
as it will only change the syntax and introduce many new bugs, but just
cannot fix any of the design problems.

    Thorsten

____________________________________________________
Thorsten Froehlich
e-mail: mac### [at] povrayorg

I am a member of the POV-Ray Team.
Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

ABX <abx### [at] abxartpl> wrote:

>On Tue, 09 Dec 2003 12:05:19 GMT, kai### [at] siemenscom (Andreas Kaiser)
>wrote:
>> It's *much* faster than the original version.
>
>I'm sure any measurable impresssion :-) from rendering the same (benchmark)
>scene with the old and new code with binaries made by the same compiler would
>be appreciated (together with statistic output of POV-Ray).
>

The following values result from rendering a menger sponge with
various levels. My system is a PIII Notebook with 850 MHz and 256 MB
RAM. Both binaries were compiled with MS C++ V7.1.



Level        2          3          4          5          6
----------------------------------------------------------------------
org.V.:     4.93      52.41     2206.95       -          -
my  V.:     3.88      10.57       34.83     138.53     746.00

Values are total time in seconds. I didn't render level 5 and 6 with
the original version (they wouldn't have finished yet). I started
level 7 with my version but cancelled it: The parsed scene exceeded
available main memory, so the result would only describe the speed of
my harddisk.

Below is the detailed statistics output for level 4.

======================= original version ================

Statistics for D:\POV-Ray\MyScenes\Sponge\akasponge1.pov, Resolution
320 x 240
----------------------------------------------------------------------------
Pixels:           76800   Samples:           76800   Smpls/Pxl: 1.00
Rays:            213509   Saved:              9460   Max Level: 11/40
----------------------------------------------------------------------------
Ray->Shape Intersection          Tests       Succeeded  Percentage
----------------------------------------------------------------------------
Box                          543929780         3641346      0.67
CSG Intersection                309755          222006     71.67
----------------------------------------------------------------------------
Calls to Noise:             393390   Calls to DNoise:         236044
----------------------------------------------------------------------------
Shadow Ray Tests:           105706   Succeeded:                59268
Reflected Rays:             136709
----------------------------------------------------------------------------
Smallest Alloc:                 25 bytes   Largest:            24088
Peak memory used:          1348571 bytes
----------------------------------------------------------------------------
Time For Trace:    0 hours 36 minutes  49.0 seconds (2208 seconds)
    Total Time:    0 hours 36 minutes  48.0 seconds (2208 seconds)
----------------------------------------------------------------------------
CPU time used: kernel 0.60 seconds, user 2206.35 seconds, total
2206.95 seconds
Render averaged 34.80 PPS over 76800 pixels

======================= my version ================

Statistics for D:\POV-Ray\MyScenes\Sponge\akasponge1.pov, Resolution
320 x 240
----------------------------------------------------------------------------
Pixels:           76800   Samples:           76800   Smpls/Pxl: 1.00
Rays:            213326   Saved:              9434   Max Level: 11/40
----------------------------------------------------------------------------
Ray->Shape Intersection          Tests       Succeeded  Percentage
----------------------------------------------------------------------------
Box                           29998766         3637518     12.13
CSG Intersection                248358          221719     89.27
Bounding Box                  20088132         5824508     28.99
----------------------------------------------------------------------------
Calls to Noise:             393690   Calls to DNoise:         236224
----------------------------------------------------------------------------
Shadow Ray Tests:           105609   Succeeded:                59169
Reflected Rays:             136526
----------------------------------------------------------------------------
Time For Parse:    0 hours  0 minutes   1.0 seconds (1 seconds)
Time For Trace:    0 hours  0 minutes  34.0 seconds (34 seconds)
    Total Time:    0 hours  0 minutes  35.0 seconds (35 seconds)
----------------------------------------------------------------------------
CPU time used: kernel 0.55 seconds, user 34.28 seconds, total 34.83
seconds
Render averaged 2204.99 PPS over 76800 pixels


Bye,

Andreas

Post a reply to this message

"Thorsten Froehlich" <tho### [at] trfde> wrote:

>In article <3fd5b6d3.1022837913@news.povray.org> , kai### [at] siemenscom 
>(Andreas Kaiser) wrote:
>
>> cannot use it directly as it's a C++-ified version,
>
>BTW, also your work sounds very interesting and nice, it has zero chance of
>making it into an official POV-Ray if it does not follow the current code.
>It is absolutely pointless to simply convert the current code to C++ classes
>as it will only change the syntax and introduce many new bugs, but just
>cannot fix any of the design problems.
>

It may be absolutely pointless from your point of view. When i started
my intention was just to learn C++ and to understand the inner working
of POV-Ray.
From my point of view this worked very well.

Andreas

Post a reply to this message

In article <3fd71cfd.80337929@news.povray.org> , kai### [at] siemenscom 
(Andreas Kaiser) wrote:

> The following values result from rendering a menger sponge with
> various levels.

Hmm, but this isn't benchmark.pov...

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

> Hmm, but this isn't benchmark.pov...

Does benchmark.pov have lot of intersections csg ? It seems fair to me to
test this patch on a scene that uses it (and perhaps even a lot of it to
clearly show the effect of the new algorithm)

M

Post a reply to this message

Mael wrote:
>>Hmm, but this isn't benchmark.pov...
> 
> 
> Does benchmark.pov have lot of intersections csg ? It seems fair to me to
> test this patch on a scene that uses it (and perhaps even a lot of it to
> clearly show the effect of the new algorithm)

The benchmark scene uses a reasonable amount of CSG, a comparison with 
this scene would show how much gain you can expect in a typical scene. 
You can of course construct a scene where POV-Ray spends 90% of the time 
with CSG calculations but this would not be very realistic.

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 25 Oct. 2003 _____./\/^>_*_<^\/\.______

Post a reply to this message

> > Does benchmark.pov have lot of intersections csg ? It seems fair to me
to
> > test this patch on a scene that uses it (and perhaps even a lot of it to
> > clearly show the effect of the new algorithm)
>
> The benchmark scene uses a reasonable amount of CSG, a comparison with
> this scene would show how much gain you can expect in a typical scene.
> You can of course construct a scene where POV-Ray spends 90% of the time
> with CSG calculations but this would not be very realistic.

Of course it will be nice to see how it improves a "typical" scene (as far
as such a thing exists..) and hopefully Andreas Kaiser will give us the
numbers for benchmark.pov (though on a PIII 850MHz I can understand it might
take him some time :) , Anyway when testing a modification in the code it
seems normal to me to use a test case that makes the improvement evident.
What if benchmark.pov is only 1% faster ? Will you say the patch is not
worth and deprive all menger sponge builders out there of a nice speed up ?
:))

M

Post a reply to this message