 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 27 Nov 2003 09:03:46 EST, "Andrew Clinton" <ajc### [at] uwaterloo ca>
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
