POV-Ray : Newsgroups : povray.unofficial.patches : BSP tree bounding patch Server Time
31 Oct 2024 19:49:39 EDT (-0400)
  BSP tree bounding patch (Message 1 to 10 of 26)  
Goto Latest 10 Messages Next 10 Messages >>>
From: Andrew Clinton
Subject: BSP tree bounding patch
Date: 27 Nov 2003 00:55:01
Message: <web.3fc59094e2a9be0611ee4e60@news.povray.org>
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


Post a reply to this message

From: Christoph Hormann
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 04:45:15
Message: <hprg91-5n2.ln1@triton.imagico.de>
Andrew Clinton wrote:
> 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.

It would be quite important to give separate results for the speed
improvement of the different parts.  The (2d) vista buffer for example
can be completely different from the bounding box hierarchies in this
concern.

> 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

In many cases it would be preferable to have a full set of the changed
source files with the modifications marked with comments/preprocessor
directives instead of the diffs.  This makes it much easier to integrate
the changes into a different version of POV.

Having a quick look at the diff i have the impression that there are
also changes not directly related to the main patch.  Some more comments
in the code would be helpful.

> 
> 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.

I have my doubts a BSP tree would be more efficient for meshes than the
current octree but i can't say for sure.

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

From: Andrew Clinton
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 09:10:01
Message: <web.3fc603926b3b1e2c611ee4e60@news.povray.org>
Christoph Hormann wrote:
>It would be quite important to give separate results for the speed
>improvement of the different parts.  The (2d) vista buffer for example
>can be completely different from the bounding box hierarchies in this
>concern.
>

The BSP tree replaces the combination hierarchy+vista+lightbuffer.  There is
really no need to try and speed it up with screen space hierarchies because
the traversal is fast enough without them.  In fact they might slow it
down.  All my tests have compared BSP tree (with no vista or light buffers)
against bounding box hierarchy (with vista and light buffers).

>In many cases it would be preferable to have a full set of the changed
>source files with the modifications marked with comments/preprocessor
>directives instead of the diffs.  This makes it much easier to integrate
>the changes into a different version of POV.
>

I'll see if I can put together something like this tonight...

>Having a quick look at the diff i have the impression that there are
>also changes not directly related to the main patch.  Some more comments
>in the code would be helpful.
>

I'm working on this... I hope to release more versions in the future that
will clean a few things up.  Most of the changes are related to the patch.
One exception is that there is a bug fix in TEST_RAY_FLAGS_SHADOW() macro,
which did not seem to be making the right check when light buffer is
disabled.  Also I've moved the method to initialize interior list (using
bounding boxes) into bbox.h which seemed to make more sense.  The only
other change I can think of is to more intelligently compute bounding box
for clipped or manually bounded objects in parse.cpp (I think this change
is correct).

>
>I have my doubts a BSP tree would be more efficient for meshes than the
>current octree but i can't say for sure.

Are you sure that meshes use octree for acceleration?  It seemed quite clear
to me when I looked at the code that it is just using the functions in
bbox.h to create a bounding box hierarchy for the triangles.  In this case
the BSP tree would give performance improvements comparable to the
performance improvement in normal scenes I've tested, because triangles are
simple to intersect.  I do not know how it would compare with an octree.

Andrew Clinton


Post a reply to this message

From: ABX
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 09:18:10
Message: <ph1csvsebc7r52v2jveslva9oucm5li1fu@4ax.com>
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


Post a reply to this message

From: Christoph Hormann
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 09:42:03
Message: <8ieh91-rj1.ln1@triton.imagico.de>
Andrew Clinton wrote:
> 
> The BSP tree replaces the combination hierarchy+vista+lightbuffer.  There is
> really no need to try and speed it up with screen space hierarchies because
> the traversal is fast enough without them.  In fact they might slow it
> down. 

Well, this is indeed the question.  It would be good if you could try 
only replacing the scene bounding tree with your new method and leaving 
the 2d buffers as they are.  This would also make more sense in terms of 
the existing options (since you can already turn vista buffers and light 
buffers on or off.

  >>I have my doubts a BSP tree would be more efficient for meshes than the
>>current octree but i can't say for sure.
> 
> 
> Are you sure that meshes use octree for acceleration?  It seemed quite clear
> to me when I looked at the code that it is just using the functions in
> bbox.h to create a bounding box hierarchy for the triangles.  In this case
> the BSP tree would give performance improvements comparable to the
> performance improvement in normal scenes I've tested, because triangles are
> simple to intersect.  I do not know how it would compare with an octree.

To be honest i don't know how the mesh and scene bounding trees are 
built but it is a bounding tree (simply because it shows an O(log(n)) 
performance :-)).

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

From: Christoph Hormann
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 11:12:03
Message: <36kh91-tmc.ln1@triton.imagico.de>
Andrew Clinton wrote:
> 
> I'm working on this... I hope to release more versions in the future that
> will clean a few things up.  Most of the changes are related to the patch.
> One exception is that there is a bug fix in TEST_RAY_FLAGS_SHADOW() macro,
> which did not seem to be making the right check when light buffer is
> disabled.  Also I've moved the method to initialize interior list (using
> bounding boxes) into bbox.h which seemed to make more sense.  The only
> other change I can think of is to more intelligently compute bounding box
> for clipped or manually bounded objects in parse.cpp (I think this change
> is correct).

I had a closer look at your changes and don't really understand the 
meaning of 'Local_BBox'.

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.

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

From: George Pantazopoulos
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 11:32:35
Message: <oprza1ptolu942mt@news.povray.org>
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

From: Mael
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 12:03:12
Message: <3fc62e50@news.povray.org>
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

From: Thorsten Froehlich
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 13:13:52
Message: <3fc63ee0$1@news.povray.org>
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

From: George Pantazopoulos
Subject: Re: BSP tree bounding patch
Date: 27 Nov 2003 22:07:35
Message: <oprzbu2tu4u942mt@news.povray.org>
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

Goto Latest 10 Messages Next 10 Messages >>>

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.