Very interesting work, Andrew. Be sure to test it on radiosity scenes. 
Since POV-Ray's radiosity depends on shooting large numbers of rays, your 
method should have a noticable effect. Keep us posted, and release the full 
modified set of source files rather than those stinky diffs :)

Thanks,
George


> Hello all,
>
> I've been thinking about writing a patch for some time, but only in the 
> past
> month have I taken some time to do the research and put one together.  
> What
> I've implemented is a BSP tree data structure that can be used in place 
> of
> the bounding volumes/light buffer/vista buffer to improve raytracing
> performance.  The premise is that for scenes with many objects, a lot of
> time is spent sorting the bounding box intersections from front to back,
> and intersecting bounding boxes that may later be discarded.  With a
> spatial subdivision like a BSP tree that partitions *space* instead of
> *objects*, there is no need for a sort on the length of the ray, as the
> space can be efficiently traversed in order, and few additional bounding
> box intersections are required than those in front of the final object
> intersection.
>
> I've put together the patch as a set of diffs (following the example of 
> the
> previous patch posted here).  The patch can be found at
> http://povplace.addr.com/bsppov.tar.gz
>
> Since many people will not be able to make heads or tails of what to do 
> with
> (the diffs), I am working on a Windows binary.
>
> There is some more information about the performance improvements on 
> scenes
> included with POV-Ray in the README file in the package.  In general, the
> patch produces the largest performance gain on scenes with large numbers 
> of
> simple-to-intersect objects (as high as 70% improvement).  I have not
> observed a scene that renders slower with the new data structure.
>
> There is still lots of room for optimization for the patch, and I am 
> working
> on having it work on objects with some internal structure like meshes.
>
> Andrew Clinton
>
>



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

Post a reply to this message

Hello,

Thank you for your patch, 70% gain is really impressive ! It's clear that
the bounding box stuff is called many many times so any improvement can have
big effects. If the speed up occurs more for scene with many objects it's
great too, because those are precisely those heavy scenes that one would
like to render quickier :) I'll try to compile and test your patch this
week-end

M

Post a reply to this message

In article <web.3fc59094e2a9be0611ee4e60@news.povray.org> , "Andrew Clinton"
<ajc### [at] uwaterlooca> wrote:

> There is some more information about the performance improvements on scenes
> included with POV-Ray in the README file in the package.  In general, the
> patch produces the largest performance gain on scenes with large numbers of
> simple-to-intersect objects (as high as 70% improvement).  I have not
> observed a scene that renders slower with the new data structure.

How much faster is 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

Andrew, I can't try out your patch because Im getting all kinds of make 
errors after applying your diffs (exactly as shown in your README). Could 
you please post the actual source files?

Thanks,
George



> Hello all,
>
> I've been thinking about writing a patch for some time, but only in the 
> past
> month have I taken some time to do the research and put one together.  
> What
> I've implemented is a BSP tree data structure that can be used in place 
> of
> the bounding volumes/light buffer/vista buffer to improve raytracing
> performance.  The premise is that for scenes with many objects, a lot of
> time is spent sorting the bounding box intersections from front to back,
> and intersecting bounding boxes that may later be discarded.  With a
> spatial subdivision like a BSP tree that partitions *space* instead of
> *objects*, there is no need for a sort on the length of the ray, as the
> space can be efficiently traversed in order, and few additional bounding
> box intersections are required than those in front of the final object
> intersection.
>
> I've put together the patch as a set of diffs (following the example of 
> the
> previous patch posted here).  The patch can be found at
> http://povplace.addr.com/bsppov.tar.gz
>
> Since many people will not be able to make heads or tails of what to do 
> with
> (the diffs), I am working on a Windows binary.
>
> There is some more information about the performance improvements on 
> scenes
> included with POV-Ray in the README file in the package.  In general, the
> patch produces the largest performance gain on scenes with large numbers 
> of
> simple-to-intersect objects (as high as 70% improvement).  I have not
> observed a scene that renders slower with the new data structure.
>
> There is still lots of room for optimization for the patch, and I am 
> working
> on having it work on objects with some internal structure like meshes.
>
> Andrew Clinton
>
>



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

Post a reply to this message

ABX wrote:
>On Thu, 27 Nov 2003 09:03:46 EST, "Andrew Clinton" <ajc### [at] uwaterlooca>
>wrote:
>> One exception is that there is a bug fix in TEST_RAY_FLAGS_SHADOW()
>
>Can you elaborate on this ? Your version is different that current
>development. Any reasons to follow you ? Minimal scene and settings to verify
>why you modified it that way ?
>
>TIA, ABX
>

OK.  The problem I was trying to solve can be observed when you render
"advanced/glasschess/glasschess.pov" with and then without the light buffer
turned on (-UL).  The number of shadow ray tests when this scene is
rendered without the light buffer is about 3x the number when it is
rendered with the light buffer.  This is not a side-effect of just not
using the light buffer, because the light buffer should not reduce the
total number of shadow ray tests at all as far as I know.

What I figured to be the problem was that objects in this scene marked with
"no_shadow" were still being tested against by shadow rays when the light
buffer is not used.  When the light buffer is used, this problem is not
noticed because the objects with "no_shadow" are not even put into the
light buffer when it is constructed.

My solution was to change the routine TEST_RAY_FLAGS_SHADOW from

--------

#define TEST_RAY_FLAGS_SHADOW(obj) \
(  (!backtraceFlag && \
(!Test_Flag((obj), NO_IMAGE_FLAG) || In_Reflection_Ray == true) && \
(!Test_Flag((obj), NO_REFLECTION_FLAG) || In_Reflection_Ray == false)) \
||(shadow_flag && !Test_Flag((obj), NO_SHADOW_FLAG)) \
|| (backtraceFlag && !Test_Flag((obj), NO_SHADOW_FLAG)) )

-------- to

#define TEST_RAY_FLAGS_SHADOW(obj) \
(  (!backtraceFlag && \
(!Test_Flag((obj), NO_IMAGE_FLAG) || In_Reflection_Ray == true) && \
(!Test_Flag((obj), NO_REFLECTION_FLAG) || In_Reflection_Ray == false) && \
(!shadow_flag || !Test_Flag((obj), NO_SHADOW_FLAG))) \
|| (backtraceFlag && (!Test_Flag((obj), NO_SHADOW_FLAG) ) ))

---------

This change makes sure that when we are in a shadow ray, and the object
being tested has "no_shadow", we will not test the object.  I also assume
that shadow_flag will never be set during backtrace (reasonable?)

I've just been testing this some more, and realise that this solution is
still not complete.  By fixing this, another bug seems to be exposed where
uninitialized memory is accessed by csg.cpp and isosurface.cpp.  Try
searching for "Optimisiation_Flags" and you will find that this member of
RAY is never initialized for non-shadow rays so its value could be
unpredictable.  This is causing rendering problems for glasschess.pov when
my fix to TEST_RAY_FLAGS_SHADOW is used.

I hope this helps!

Andrew

Post a reply to this message

Christoph Hormann wrote:
>
>I had a closer look at your changes and don't really understand the
>meaning of 'Local_BBox'.
>

Local_BBox is the bounding box of an object before a transformation.  The
way that POV-Ray currently produces bounding boxes for transformed objects
is to take the 8 vertices of the untransformed box, transform them, then
find the axis-aligned box that contains all the transformed vertices.  This
can produce a lot of slack space around the object, which you can see by
imagining to transform a long thin cylinder by 45 degrees.

I've added the abilitly to store the bounding box of the object before it
has been transformed.  This allows the tree construction to take advantage
of some more detailed information about the objects in the scene which can
produce a better tree.  For now, I am only using the local box to determine
whether the object should be a member of a cell in the tree - by using a
box/box intersection algorithm.

>BTW the way you implemented the additional statistics is of course not
>the right way(tm) but i'd suggest you wait until the next official
>version before changing this because otherwise you will have to modify
>it twice.
>

How do I implement the statistics in the right way?

Andrew

Post a reply to this message

George Pantazopoulos wrote:
>Andrew, I can't try out your patch because Im getting all kinds of make
>errors after applying your diffs (exactly as shown in your README). Could
>you please post the actual source files?
>
>Thanks,
>George
>
>

What kind of make errors are you getting?  Maybe I should be compiling with
stricter settings, unless the problem is with the diffs and not the source.
 I have been using gcc 3.2.1 to compile.

Andrew

Post a reply to this message

First of all, when I do "patch -p2 <bsppov.diff" in the src/ directory:

after it gets to "patching file optout.h" it says:
"Hunk #1 FAILED at 46"

Next it says:

"the next patch would create the file stamp-h, which already exists. Assume 
-R" ?
I'm not sure what to enter there, either. I've tried it both ways and I 
haven't gotten anywhere.

Beyond that, after ./configure and during the subsequent make, it would 
tell me that
"your implementation of AM_INIT_AUTOMAKE comes from an older version of 
automake" and to run aclocal

I tried that, but then after making I get tons of errors of the type:

"torus.Po: no such file/directory"


George


On Thu, 27 Nov 2003 22:28:28 EST, Andrew Clinton <ajc### [at] uwaterlooca> 
wrote:

> George Pantazopoulos wrote:
>> Andrew, I can't try out your patch because Im getting all kinds of make
>> errors after applying your diffs (exactly as shown in your README). 
>> Could
>> you please post the actual source files?
>>
>> Thanks,
>> George
>>
>>
>
> What kind of make errors are you getting?  Maybe I should be compiling 
> with
> stricter settings, unless the problem is with the diffs and not the 
> source.
> I have been using gcc 3.2.1 to compile.
>
> Andrew
>
>



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

Post a reply to this message

I neglected to mention that I'm on redhat 9, with gcc 3.3.1

>
> First of all, when I do "patch -p2 <bsppov.diff" in the src/ directory:
>
> after it gets to "patching file optout.h" it says:
> "Hunk #1 FAILED at 46"
>
> Next it says:
>
> "the next patch would create the file stamp-h, which already exists. 
> Assume -R" ?
> I'm not sure what to enter there, either. I've tried it both ways and I 
> haven't gotten anywhere.
>
> Beyond that, after ./configure and during the subsequent make, it would 
> tell me that
> "your implementation of AM_INIT_AUTOMAKE comes from an older version of 
> automake" and to run aclocal
>
> I tried that, but then after making I get tons of errors of the type:
>
> "torus.Po: no such file/directory"
>
>
> George
>
>
> On Thu, 27 Nov 2003 22:28:28 EST, Andrew Clinton <ajc### [at] uwaterlooca> 
> wrote:
>
>> George Pantazopoulos wrote:
>>> Andrew, I can't try out your patch because Im getting all kinds of make
>>> errors after applying your diffs (exactly as shown in your README). 
>>> Could
>>> you please post the actual source files?
>>>
>>> Thanks,
>>> George
>>>
>>>
>>
>> What kind of make errors are you getting?  Maybe I should be compiling 
>> with
>> stricter settings, unless the problem is with the diffs and not the 
>> source.
>> I have been using gcc 3.2.1 to compile.
>>
>> Andrew
>>
>>
>
>
>



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

Post a reply to this message

Can you try installing the full set of modified files:

http://povplace.addr.com/bsppov-src.tar.gz

and let me know if you still have problems compiling?  Make sure that you
start with a completely fresh povray-3.50c.

Andrew

Post a reply to this message