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

Mael wrote:
> 
> 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 ?
> :))

If the gain for benchmark.pov is only 1% i would probably never do the 
work of rewriting the code Andreas posted to POV-Ray syntax to try it.

There are mainly 3 criterias for a patch to make it into MegaPOV or 
ultimately official POV:

- the patch is a useful improvement of functionality/performance
- the patch is well written, well tested and compatible to current POV-Ray.
- the patch is well documented (source and user level)

Since one of these points is not met and the other (documentation) is 
not so relevant in this case the third is even more important.

But don't get me wrong, to me this patch seems quite useful at the first 
glance so i would encourage Andreas to show additional test results and 
code usable for current POV.

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

In article <rn4### [at] tritonimagicode> , Christoph Hormann 
<chr### [at] gmxde>  wrote:

> But don't get me wrong, to me this patch seems quite useful at the first
> glance so i would encourage Andreas to show additional test results and
> code usable for current POV.

I agree.

    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

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

>In article <rn4### [at] tritonimagicode> , Christoph Hormann 
><chr### [at] gmxde>  wrote:
>
>> But don't get me wrong, to me this patch seems quite useful at the first
>> glance so i would encourage Andreas to show additional test results and
>> code usable for current POV.
>
>I agree.
>

OK, i'll rewrite it for the official version and then run the internal
benchmark.

Andreas

Post a reply to this message

I find it amazing that folks just picking up C/C++ for the first time
exclusively for the purposes of improving POV-Ray have been so successful...
whereas I've been studying Computer Science for 4 years now and I haven't
the foggiest what I could do to improve the code (that, or I can't read it).
Sigh. This is not encouraging. I'll put on my dunce hat now... <:(

-- 
Anthony Bennett

PS: I just finished my Operating Systems final* today... This means I'm
done. I'm sticking around one more semester for Japanese III and Scientific
Visualization, but I'm basically done with CS. Yay!

*Most evil exam ever. Ever.

Post a reply to this message

"Tony[B]" <ben### [at] catholicorg> wrote:

>I find it amazing that folks just picking up C/C++ for the first time
>exclusively for the purposes of improving POV-Ray have been so successful...
>whereas I've been studying Computer Science for 4 years now and I haven't
>the foggiest what I could do to improve the code (that, or I can't read it).
>Sigh. This is not encouraging. I'll put on my dunce hat now... <:(

Take it off :)
I've been using C for several years, so the step to C++ was a small
one. Before i started to work as a software developer i've studied
physics, so the math and physics used in POV-Ray were no problem for
me. The latter was the main reason to play around with the POV-Ray
code: I was going to lose all my math knowledge completely.


>-- 
>Anthony Bennett
>
>PS: I just finished my Operating Systems final* today... This means I'm
>done. I'm sticking around one more semester for Japanese III and Scientific
>Visualization, but I'm basically done with CS. Yay!
>
>*Most evil exam ever. Ever.

Congratulations.

Andreas

Post a reply to this message

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

Andreas Kaiser wrote:

> 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

Almost 30% for benchmark.pov! That is a huge improvement! Great work, if 
it indeed produces 100% identical results. I hope you can make a patch 
that can be someday included in official version.

Severi Salminen

Post a reply to this message

Andreas Kaiser <kai### [at] siemenscom> wrote:
> The version below isn't as fast as my C++ version as it doesn't use a
> BBOX tree for the inverted children.

  Why not?


-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

Andreas Kaiser <kai### [at] siemenscom> wrote:
> I've been using C for several years, so the step to C++ was a small
> one.

  Actually the step from C to C++ is much much larger than you might
believe. Much larger than for example from Java to C++.
  I have seen too much C++ code made by C coders and it looks horrible.
There are tons of things that can be done much better in C++ than in C,
but due to the C coder bad habits they can't (or even refuse) to
understand... :)

  But this is, of course, off-topic.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Hello,

> Next try.

First thank you for your work and patience..
 I've tried to apply your patch and decided to test it with chess2.pov (in
scenes/advanced). And (you're going to hate me :)  .. I don't get the same
image (too bad because it was faster :) . I may have messed up applying your
modification or it could be a compiler issue so if you (or someone else) can
check.. For information I've compiled on a linux redhat 7.2 PIII 1.13Ghz (in
fact a bi PIII), gcc version 2.96 and rendered with "+w640 +h480 +a0.3 +fn
+Ichess2.pov"
I'll try again later on a more recent system

M

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:

>Andreas Kaiser <kai### [at] siemenscom> wrote:
>> The version below isn't as fast as my C++ version as it doesn't use a
>> BBOX tree for the inverted children.
>
>  Why not?
>
>

This requires some modifications for the bbox tree routines that, may
be next week.

Andreas

Post a reply to this message

> gcc version 2.96 and rendered with "+w640 +h480 +a0.3 +fn

	You might try one of the last 3.3.x series.  2.96 was
never officially released (RedHat build) and is known to have
compatibility issues. Moreover it is slower than the new ones.

	- NC

Post a reply to this message

"Mael" <mae### [at] hotmailcom> wrote:

>Hello,
>
>> Next try.
>
>First thank you for your work and patience..
> I've tried to apply your patch and decided to test it with chess2.pov (in
>scenes/advanced). And (you're going to hate me :)  .. I don't get the same
>image (too bad because it was faster :) . I may have messed up applying your

Strange, should really not happen (of course:).
I will check it this evening.
I think there's nothing that you could have messed up (just one new
define an one function to be replaced).

>modification or it could be a compiler issue so if you (or someone else) can
>check.. For information I've compiled on a linux redhat 7.2 PIII 1.13Ghz (in
>fact a bi PIII), gcc version 2.96 and rendered with "+w640 +h480 +a0.3 +fn
>+Ichess2.pov"
>I'll try again later on a more recent system
>
>M

Andreas

Post a reply to this message

>   I have seen too much C++ code made by C coders and it looks horrible.
> There are tons of things that can be done much better in C++ than in C,
> but due to the C coder bad habits they can't (or even refuse) to
> understand... :)

	POV is currently and will be like this for a while...

	- NC

Post a reply to this message

Andreas Kaiser wrote:
> 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

Well, that's much worse, why didn't you convert the original version as 
it was?  It is surely not C++ being faster that leads to this difference...

> benchmark.pov, rendered with -w384 -h384 +a0.3 +v -d -f -x
> 
> Original Version: 5987 seconds
> this C Version:   4280 seconds

Seems about as i'd expect it.

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

> > gcc version 2.96 and rendered with "+w640 +h480 +a0.3 +fn
>
> You might try one of the last 3.3.x series.  2.96 was
> never officially released (RedHat build) and is known to have
> compatibility issues. Moreover it is slower than the new ones.

Well, this is not my machine (I'm not going to change anything on it..),
I've used it because it was available for me to quickly test.. And that's
why I added at the end of my message that I'll try with more up to date
system later.

M

Post a reply to this message

> I'll try again later on a more recent system

This time I tried on windows (VC++ 6) and same (wrong) results for
chess2.pov (you can render it without focal blur for faster test)
I hope this is something easy to track down .. good luck :-/

M

Post a reply to this message

Mael wrote:
> 
> First thank you for your work and patience..
>  I've tried to apply your patch and decided to test it with chess2.pov (in
> scenes/advanced). And (you're going to hate me :)  .. I don't get the same
> image (too bad because it was faster :) .

Have you tried it with vista buffer off?

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

Don't you need to clear the flag for when the next ray comes around?  I'm
getting rendering errors even in benchmark.pov.

Andrew

Post a reply to this message

Nicolas Calimet <pov### [at] freefr> wrote:
>         POV is currently and will be like this for a while...

  I know, but I don't blame the pov-team for that. It's not a bunch of
C-coders trying to make a C++ program, but a 10-years old gigantic C program
where some C++ has been added for certain features, not for the intention
of being the final thing, but for being an updated bugfix release before
the complete rewrite in C++ with good OO design.

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

In article <3fdb73ab@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:
>>         POV is currently and will be like this for a while...
>
>   I know, but I don't blame the pov-team for that. It's not a bunch of
> C-coders trying to make a C++ program, but a 10-years old gigantic C program
> where some C++ has been added for certain features, not for the intention
> of being the final thing, but for being an updated bugfix release before
> the complete rewrite in C++ with good OO design.

It should not be forgotten that "good OO design" is a far from trivial
thing.  Especially when it comes down to the ugly little details that look
great in the UML diagram, but are much harder to implement an second sight
... especially if the primary goal is raw performance the temptation to
"just use C" is always around.  And in the end it will always be the wrong
decision.

On the other hand, to master all C++ features well takes years of practical
experience and a gentle growths of abilities:  It would be irrational to
expect to be able to teach anybody a language as complex as C++ from any
number of books or in a classroom.  Far too many teachers make the mistake
of treating "programming" as just a necessary evil of computer science, and
assume programming languages can be used interchangeably!

Of course, this just shows a serious disconnection from any practical
experience at all - and far too many who teach in my home part of Europe
have not realised this yet at all, and I know it happens almost everywhere
else, too...

Or would you rather understand 20 languages - be they for inter-human
communication or computer programming - a little than speak two or three
fluently?  Of course, as many computer scientists have never been made to
realise this very simple fact in school, they never applied it in the real
world, and hence you end up with the majority of computer scientists being
just terrible programmers.  Yet, they start as just that in most jobs, and
hence software quality did not improve despite huge advances in programming
languages in the past 25 years.  To the contrary, system complexity and size
increased by at least three orders of magnitude, but most still program like
25 years ago, desperatly trying to solve their problemsby creating a
mountain of design specifications and other formal methods :-(

    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

In article <3fd9c437@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>   Actually the step from C to C++ is much much larger than you might
> believe. Much larger than for example from Java to C++.

Java and C++ are really not interchangeable or compareable.  The only thing
they have in common is that they offer language support for OO programming.

Yet, while Java as a language is neat, the libraries that come with it are
just a big piece of hacked together junk and patchwork resulting from
marketing needs rather than rational thinking.  C++ on the other hand has
careful design (for the most and major part), and its library was designed
as a whole integrated component.

It also turns out that no matter what you do, a Java program will always be
a fat, slow thing that tends to misbehave and corrupt your data rather than
just crash and leave your data alone.  C++, on the other hand, if, and only
if, used properly, will result in a fast, lean and extraordinary stable
piece of software.

    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

Thorsten Froehlich wrote:

>>  I know, but I don't blame the pov-team for that. It's not a bunch of
>>C-coders trying to make a C++ program, but a 10-years old gigantic C program
>>where some C++ has been added for certain features, not for the intention
>>of being the final thing, but for being an updated bugfix release before
>>the complete rewrite in C++ with good OO design.
> 
> 
> It should not be forgotten that "good OO design" is a far from trivial
> thing.  Especially when it comes down to the ugly little details that look
> great in the UML diagram, but are much harder to implement an second sight
> ... especially if the primary goal is raw performance the temptation to
> "just use C" is always around.  And in the end it will always be the wrong
> decision.

Can you tell what are/were the reasons for deciding to rewrite the whole 
POV-Ray in C++? Performance wise I think it doesn't mean much nowadays, 
but do you think OO suites POV-Ray better than plain ol' procedural C? 
It will be a huge task but do you think it will pay the effort as easier 
code maintenance and further development?

Severi Salminen

Post a reply to this message

In article <3fdb9898$1@news.povray.org> , Severi Salminen 
<sev### [at] NOT_THISsibafi>  wrote:

> Can you tell what are/were the reasons for deciding to rewrite the whole
> POV-Ray in C++? Performance wise I think it doesn't mean much nowadays,
> but do you think OO suites POV-Ray better than plain ol' procedural C?
> It will be a huge task but do you think it will pay the effort as easier
> code maintenance and further development?

I outlined the answers to your questions in the second half of the last
paragraph of my message.

    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

Thorsten Froehlich wrote:

>>Can you tell what are/were the reasons for deciding to rewrite the whole
>>POV-Ray in C++? Performance wise I think it doesn't mean much nowadays,
>>but do you think OO suites POV-Ray better than plain ol' procedural C?
>>It will be a huge task but do you think it will pay the effort as easier
>>code maintenance and further development?
>  
> I outlined the answers to your questions in the second half of the last
> paragraph of my message.

Indeed, I hadn't read that. You wrote: "a fast, lean and extraordinary 
stable piece of software". But doesn't Pov-Ray allready meet these 
goals? Or is this simply about it being _easier_ to achieve those goals 
with C++ than with C? (My knowledge of C++ is _very_ limited). Just curious.

Severi S.

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
> It should not be forgotten that "good OO design" is a far from trivial
> thing.  Especially when it comes down to the ugly little details that look
> great in the UML diagram, but are much harder to implement an second sight

  This is certainly true.

  Thinking that you can make good object-oriented programs after having
been in a UML course is like thinking that you can drive a F1 car right
after you have got your driver's license. However, I'm afraid that too
many people think this way.

  Background theory is extremely important, if not mandatory, but only
experience (lots of it) will give you the qualification. And not whatever
programming experience at free, but expressly object-oriented programming
experience.
  10 years of "hacker" C programming experience will (at least at first)
probably be more a burden than a benefit (even though that experience can
become very handy once you have assimilated good OO principles and got
some experience about it). This is because C teaches very, very bad
habits which are a real burden in good object-oriented C++.

  In the project I'm working at we are at the third generation of our
major file I/O library. It has gone through two complete re-designs
because the previous designs resulted to be cumbersome in practice (even
though they looked nice in paper). The current third design is starting
to look like what it should. :)

  This is a very common phenomenon I have noticed: In any bigger project
the first OO design of the system will most probably be flawed and will
probably need at least one major re-design with more practical experience
before it becomes usable.

> ... especially if the primary goal is raw performance the temptation to
> "just use C" is always around.  And in the end it will always be the wrong
> decision.

  The sad thing is that sometimes the "C-way" will be slower and less
efficient than the "C++-way". For instance, compare C and C++ strings.
(Most operations are much faster in C++, not to talk about C++ strings
being a lot more secure with regard to memory leaking. C++ strings are
also a lot easier to use.)

  (It's really sad that C++ streams are still slower than C streams in
most compilers. When will they make an implementation which is at least
as fast?)

> On the other hand, to master all C++ features well takes years of practical
> experience and a gentle growths of abilities:  It would be irrational to
> expect to be able to teach anybody a language as complex as C++ from any
> number of books or in a classroom.

  Some books really help. For instance "Effective C++" and "More Effective
C++"... :P
  (Of course these books are aimed to those who already have experience
about C++ and want to learn more.)

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

> Take it off :)
<snip>

Oh, OK. Feeling slightly less stupid now. ^_^

Still... Wouldn't it be awesome, once POV gets rewritten in C++, to have a
documentation of the source that not only focuses on things at the
instruction level, but that takes on the POV source as a whole? Kind of an
intro to the hierarchy and structure, what the basic files are, what they
contribute, and how each additional object or functionality fits into this
core. Perhaps an explanation of how one would go about adding, say, the
torus object, or the brick pigment. Something along those lines, which would
allow someone who has never seen the source to grasp in broad strokes how it
all works and fits together -- someone like me, who might want to add
something (or dare I say, hope to improve something)...

> >PS: I just finished my Operating Systems
>>final today... This means I'm done.
>
> Congratulations.

Thanks! My final grade was a B. I may be able to improve it (I found an old
homework that he had marked down as a 0 for me), but at least I passed, so
I'm very happy. ^_^

-- 
Anthony Bennett

Post a reply to this message

"Thorsten Froehlich" <tho### [at] trfde> a écrit dans le message de news:
3fdb9292@news.povray.org...
> In article <3fd9c437@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> It also turns out that no matter what you do, a Java program will always
be
> a fat, slow thing that tends to misbehave and corrupt your data rather
than
> just crash and leave your data alone.  C++, on the other hand, if, and
only
> if, used properly, will result in a fast, lean and extraordinary stable
> piece of software.

Unfortunately, after a while, even the best designed C++ program, if
sufficiently large and complex,  will turn into an ugly,
crash prone, unmaintainable corruption factory maze of lines of code,
because it is SO easy to go this route
(with operator overloading, multiple inheritance and pointers as the main
tools)

--
Pascal.

Post a reply to this message

In article <3fdc4e58@news.povray.org> , "Pascal" <net### [at] freesurffr> 
wrote:

> Unfortunately, after a while, even the best designed C++ program, if
> sufficiently large and complex,  will turn into an ugly,
> crash prone, unmaintainable corruption factory maze of lines of code,
> because it is SO easy to go this route
> (with operator overloading, multiple inheritance and pointers as the main
> tools)

Anybody who still uses raw pointers in C++ deserves to be shot!

    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

In article <3fdbce98@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>> ... especially if the primary goal is raw performance the temptation to
>> "just use C" is always around.  And in the end it will always be the wrong
>> decision.

You are the second person I am not sure understood what I wrote they way I
meant it, and I am sure it is due to my bad choice of sentence structure:
"And in the end it will always be the wrong decision." is supposed to refer
to the "just use C" in case it wasn't clear.

    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

In article <3fdbba25$1@news.povray.org> , Severi Salminen 
<sev### [at] NOT_THISsibafi>  wrote:

>> I outlined the answers to your questions in the second half of the last
>> paragraph of my message.
>
> Indeed, I hadn't read that. You wrote: "a fast, lean and extraordinary
> stable piece of software". But doesn't Pov-Ray allready meet these
> goals? Or is this simply about it being _easier_ to achieve those goals
> with C++ than with C? (My knowledge of C++ is _very_ limited). Just curious.

The code could be much shorter in many places if everything wouldn't be done
the "manual" way in good old C style.

    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

In article <3fdbce98@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>   Some books really help. For instance "Effective C++" and "More Effective
> C++"... :P
>   (Of course these books are aimed to those who already have experience
> about C++ and want to learn more.)

Well, these book are extremely dated.  After all it appeared back in 1995.
I have not seen the second edition of the first book yet.  Anyway, just
consider Item 5 in the first book.  The final language specification
actually says it is undefined behavior to call the wrong delete (but few
compilers manage to warn when this happens, also in most cases they could).
Or item 3 in the second book - you don't have problems if you use STL rather
than self-cooked arrays.  Or consider item 13 in the second book.  This is
again more an advice for language beginners, everybody even a tiny bit
experienced should really know.

    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

On Sun, 14 Dec 2003 12:51:38 +0100, Pascal <net### [at] freesurffr> wrote:

Um, geez ever heard of smart pointers like auto_ptr ?

> Unfortunately, after a while, even the best designed C++ program, if
> sufficiently large and complex,  will turn into an ugly,
> crash prone, unmaintainable corruption factory maze of lines of code,
> because it is SO easy to go this route
> (with operator overloading, multiple inheritance and pointers as the main
> tools)
>
> --
> Pascal.
>
>
>



-- 
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/

Post a reply to this message

Thorsten Froehlich wrote:

> In article <3fd9c437@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:
> 
> It also turns out that no matter what you do, a Java program will always
> be a fat, slow thing that tends to misbehave and corrupt your data rather
> than
> just crash and leave your data alone.  C++, on the other hand, if, and
> only if, used properly, will result in a fast, lean and extraordinary
> stable piece of software.
> 
I just have to emphasize the statement "if and only if used properly". 
Usind RTTI and exceptions, it is easy to get a really fat (as of binary 
size) and slow program much faster than you think. 

For something like a raytracer, I personally think one should stay away 
from exceptions and RTTI unless it is _really_ needed. 

Just my 2 cents
...after many years of C(++) coding

Wolfgang

Post a reply to this message

Thorsten Froehlich wrote:

> Anybody who still uses raw pointers in C++ deserves to be shot!
> 
If you mean "raw pointer" = "void pointer", then I completely agree. 

Otherwise, I strongly object. 
(Because you then probably would have to shoot me -- with several 
automatic guns in parallel :p)

Pointers are the most useful thing in C and you cannot get around 
them in C++ if you want to keep fast performance. 
All that guided stuff I've heared yet is both slow & fat. 

Or do you see an alternative?

Wolfgang

Post a reply to this message

Wolfgang Wieser <wwi### [at] gmxde> wrote:
> Pointers are the most useful thing in C and you cannot get around 
> them in C++ if you want to keep fast performance. 

  In C++ there's less need to use pointers everywhere. For instance, often
a reference is better than a pointer (a reference is more secure and
easier to use syntax-wise).
  And if you are going to use dynamically allocated memory, abstracting
the pointer is a good idea anyways. For instance most (if not all)
STL data containers are classes which contain just one member
variable: A pointer. Which means that these data containers are
basically a pointer. However, they are 100 times more secure than
using a pointer directly, 100 times easier to use and in no way less
efficient.
  Using 'new' outside an abstract type is usually a bad idea. Honestly.

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

George Pantazopoulos <george@gamma*killspam*burst.net> wrote:
> Um, geez ever heard of smart pointers like auto_ptr ?

  I have never needed smart pointers, yet in the last 5 years I don't
remember how many memory leaks I have had in my programs, but it's quite
close to 0.
  I don't really understand what smart pointers are useful for. In my
opinion if you need to use a smart pointer, there's a flaw in your
design.
  Abstract the pointer directly to the data container type you want
to use it for. It's cleaner that way.

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

In article <3fdcbcc2@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>  
wrote:

> I just have to emphasize the statement "if and only if used properly".
> Usind RTTI and exceptions, it is easy to get a really fat (as of binary
> size) and slow program much faster than you think.

No, not at all!  RTTI is something you get for no runtime cost at all and
the data size it adds is in the range of a few dozen bytes per class.  If
you can get exceptions for free depends a tiny bit on the architecture used,
but in general the answer is yes as well.  In particular, if you don't throw
any exceptions inside a function, exceptions will not cost anything.

The frequently found warning that RTTI and exceptions make programs slow is
due to very early C++ compilers (we are talking about ten years old or more)
did not implement these features efficently.  This is not the case for *any*
recent compiler released in the past few years.

    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

In article <3fdcbe02@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>  
wrote:

> Pointers are the most useful thing in C and you cannot get around
> them in C++ if you want to keep fast performance.
> All that guided stuff I've heared yet is both slow & fat.

I don't know which implementation you are refering to, but neither the two
leading compilers for Windows nor the two leading compilers for Mac OS have
such a problem.  In fact, it is really hard to make auto_ptr use slow
anywhere if the compiler supports at least the most trivial of
optimisations...

    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

Warp wrote:

> Wolfgang Wieser <wwi### [at] gmxde> wrote:
>> Pointers are the most useful thing in C and you cannot get around
>> them in C++ if you want to keep fast performance.
> 
>   In C++ there's less need to use pointers everywhere. For instance, often
> a reference is better than a pointer (a reference is more secure and
> easier to use syntax-wise).
>   And if you are going to use dynamically allocated memory, abstracting
> the pointer is a good idea anyways. For instance most (if not all)
> STL data containers are classes which contain just one member
> variable: A pointer. Which means that these data containers are
> basically a pointer. However, they are 100 times more secure than
> using a pointer directly, 100 times easier to use and in no way less
> efficient.
>
They _are_ less efficient. (Because even temporaries trigger allocatation 
on the heap instead of the fast stack and because the con/destructors 
are called all the time increasing and decreasing reference counters, 
etc.) 

So, my personal opinion is that for complex types the speed penalty
is small compared to the gain in safety (especially when one can 
frequently use references which eliminate the need to call con/destructors). 
But _not_ for real simple types. For "I quickly need a vector", using 
double v[3] is still faster than anything using operator new or 
applying a fancy con/destructor. (One could use a fixed-size template 
in that case, though: MyVect<double,3> v; )

>   Using 'new' outside an abstract type is usually a bad idea. Honestly.
> 
It depends. But in the most cases this is true. 

Wolfgang

Post a reply to this message