Greetings,
 I've been doing some experimenting recently with replacing POV-Ray's
bounding volume heirarchy with a kd-tree. It seems as though using a
kd-tree instead of a BVH can yield a non-trivial performance gain in some
scenes. Additionally, in scenes that the kd-tree does not grant a
performance improvement it still performs at the same level as the BVH --
with one exception (scenes for which a sensible kd-tree cannot be
constructed; ie: scenes in which almost every object intersects every other
object).

 If anyone's interested in seeing the results of my experimentation, you can
see them at: http://www.cs.ualberta.ca/~dneilson/raytracing.html

 Should anyone be interested in my kd-tree code, then drop me a line. I'll
see what I can do about pulling the kd-tree stuff out of my codebase and
reinserting it into stock POV-Ray.

-Daniel Neilson

Post a reply to this message

Daniel Neilson wrote:
> [...]
> 
>  If anyone's interested in seeing the results of my experimentation, you can
> see them at: http://www.cs.ualberta.ca/~dneilson/raytracing.html

I miss a scene making a lot of use of meshes.  Since they have their own 
bounding hierarchies in standard POV it would be interesing how well 
your version handles this.

>  Should anyone be interested in my kd-tree code, then drop me a line. I'll
> see what I can do about pulling the kd-tree stuff out of my codebase and
> reinserting it into stock POV-Ray.

Sure i'd be interested.

BTW on your page you write that POV-Ray does not support irradiance 
caching and motion blur.  The former is available in official POV for a 
long time and motion blur is available in MegaPOV 0.x (and will be in 
version 1.1).

Christoph

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

Post a reply to this message

Christoph Hormann <chr### [at] gmxde> wrote:
> I miss a scene making a lot of use of meshes.  Since they have their own
> bounding hierarchies in standard POV it would be interesing how well
> your version handles this.

 Unfortunately, I don't have many scenes that have large meshes in them with
which I could test this. One quick/simple test that I had done, but not put
on the web page, was a rendering of a scene containing two Venus De Milo's
(http://objects.povworld.org/cgi-bin/dl.cgi?venus.zip). Rendering an
800x600 image with +A0.3 took 90s with POV's BVH (using vista & light
buffers), and 83s with the kd-tree. Unfortunately, though, that mesh of the
Venus only has about 5000 triangles. I imagine that the difference would be
quite more pronounced with a bigger mesh.

 If anyone can point me to a site that contains large meshes in .pov format,
I'd be glad to test a few.

> >  Should anyone be interested in my kd-tree code, then drop me a line. I'll
> > see what I can do about pulling the kd-tree stuff out of my codebase and
> > reinserting it into stock POV-Ray.
>
> Sure i'd be interested.

 Okay, I'll let you know when I've finished pulling it out then.

> BTW on your page you write that POV-Ray does not support irradiance
> caching and motion blur.  The former is available in official POV for a
> long time and motion blur is available in MegaPOV 0.x (and will be in
> version 1.1).

 That's great news, on both fronts. I'll admit that I haven't looked too
heavily at the rendering algorithm that POV-Ray is using quite yet. But
from my initial looks through the code base I didn't see anything that
seemed to be related to irradiance caching. Do you know what the irradiance
cache is called within the POV-Ray codebase? A grep for "irradiance" finds
nothing...

-Daniel Neilson

Post a reply to this message

Daniel Neilson wrote:
> 
>  Unfortunately, I don't have many scenes that have large meshes in them with
> which I could test this. One quick/simple test that I had done, but not put
> on the web page, was a rendering of a scene containing two Venus De Milo's
> (http://objects.povworld.org/cgi-bin/dl.cgi?venus.zip). Rendering an
> 800x600 image with +A0.3 took 90s with POV's BVH (using vista & light
> buffers), and 83s with the kd-tree. Unfortunately, though, that mesh of the
> Venus only has about 5000 triangles. I imagine that the difference would be
> quite more pronounced with a bigger mesh.
> 
>  If anyone can point me to a site that contains large meshes in .pov format,
> I'd be glad to test a few.

No need to download a large mesh, you can use a heightfield scene (there 
are some among the sample scenes) or a script generated mesh (ingo has 
some useful macros for this on his page: http://members.home.nl/seedseven/).

Christoph

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

Post a reply to this message

Ignore my question about what the irradiance cache is called in POV-Ray. I
just found it.

Thanks,
 Daniel Neilson

Post a reply to this message

In article <c6p0eq$8s3$1@chho.imagico.de>,
 Christoph Hormann <chr### [at] gmxde> wrote:

> I miss a scene making a lot of use of meshes.  Since they have their own 
> bounding hierarchies in standard POV it would be interesing how well 
> your version handles this.

I considered doing a mesh object using a kd-tree while working on the 
point kd-tree for my voronoi pattern. Never actually sat down and 
figured out how to fit finite objects into the tree, though...

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/

Post a reply to this message

Have you looked at the patch that I posted to povray.unofficial.patches a
little while ago?  I implemented the KD-tree from Vlastimil Havran's
thesis.  Unfortunately I chose to call it a BSP-tree rather than the
KD-tree, because it seems to be referred to as BSP-tree in other
raytracers.  I haven't had time to look at your patch yet, but the
performance is very sensitive to the way in which the tree is constructed.
 I chose to use the cost function from the thesis to choose splitting
points along with a depth bound based on the size of the scene, which
seems to give good performance for most cases.

I've done some work on improving the previous patch to work on meshes and
fix some bugs (and better comment the code) but haven't had time to
prepare and test the patch yet.

I will have a look at your code as soon as I have time.

Andrew

Post a reply to this message

"Andrew Clinton" <ajc### [at] uwaterlooca> wrote:
> Have you looked at the patch that I posted to povray.unofficial.patches a
> little while ago?  I implemented the KD-tree from Vlastimil Havran's
> thesis.  Unfortunately I chose to call it a BSP-tree rather than the
> KD-tree, because it seems to be referred to as BSP-tree in other
> raytracers.  I haven't had time to look at your patch yet, but the
> performance is very sensitive to the way in which the tree is constructed.
>  I chose to use the cost function from the thesis to choose splitting
> points along with a depth bound based on the size of the scene, which
> seems to give good performance for most cases.
>
> I've done some work on improving the previous patch to work on meshes and
> fix some bugs (and better comment the code) but haven't had time to
> prepare and test the patch yet.
>
> I will have a look at your code as soon as I have time.

Hi Andrew,
 I had actually noticed that posting in unofficial.patches, but since it was
referring to a BSP tree, I'll admit, I didn't even look at it. My purpose
with porting my kd-tree code into POV-Ray was actually for a learning
experience -- I'm hopeing to use POV-Ray as a base for my Ph.D. research,
so I need familiarity with the codebase.

 I also used the cost function to pick the splitting planes, but I didn't
actually use the depth bound based on the size of the scene. Instead, I
just split until I can't split anymore.

 But, that all said, I've now downloaded and taken a look at your patch.
You're really going to want to look at my kd-tree code. I ran your KD-Tree
on SPD-Rings30 and the results were less than stellar, unfortunately. This
scene contains 567,302 frame level and zero infinite objects. Just to build
the KD-Tree took just shy of a minute using your code -- and just shy of 5
seconds using mine. Trace took about 28 seconds with yours, 24 with mine --
rendering a 400x400 A0.3 image. And lastly, yours required a peak of just
shy of 1.3 gigabytes of RAM for ray tracing (1,273,673,629 bytes to be
exact) whereas my version required just shy of 600 megabytes (581,196,285
bytes to be exact).

-Daniel Neilson

Post a reply to this message

In article <pan### [at] uwaterlooca>,
 "Andrew Clinton" <ajc### [at] uwaterlooca> wrote:

> Have you looked at the patch that I posted to povray.unofficial.patches a
> little while ago?  I implemented the KD-tree from Vlastimil Havran's
> thesis.  Unfortunately I chose to call it a BSP-tree rather than the
> KD-tree, because it seems to be referred to as BSP-tree in other
> raytracers.  I haven't had time to look at your patch yet, but the
> performance is very sensitive to the way in which the tree is constructed.

Heh...so I'm not the only one. I constructed a BSP tree to make the 
voronoi pattern more efficient, and only later (when I decided to use 
the data structure that made photons so efficient) found that the type 
of BSP tree I created was called a KD-tree. My implementation is nicely 
general, and can be used for anything that needs to handle a large 
number of points, but it is restricted to points.


>  I chose to use the cost function from the thesis to choose splitting
> points along with a depth bound based on the size of the scene, which
> seems to give good performance for most cases.

I just sorted the points along each axis, and repeatedly split the point 
sets. It seems quite efficient (splitting the first axis consists of 
little more than dividing an integer by 2), and the result should be as 
close to perfectly balanced as you can get. Solving this problem is one 
reason I haven't done a KD-tree for finite-sized objects yet...I'll have 
to look up that thesis. Got a reference?

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/

Post a reply to this message

Christopher James Huff <cja### [at] earthlinknet> wrote:
> >  I chose to use the cost function from the thesis to choose splitting
> > points along with a depth bound based on the size of the scene, which
> > seems to give good performance for most cases.
>
> I just sorted the points along each axis, and repeatedly split the point
> sets. It seems quite efficient (splitting the first axis consists of
> little more than dividing an integer by 2), and the result should be as
> close to perfectly balanced as you can get. Solving this problem is one
> reason I haven't done a KD-tree for finite-sized objects yet...I'll have
> to look up that thesis. Got a reference?

Hi there,
 Vlastimil's thesis can be found at:
http://www.mpi-sb.mpg.de/~havran/DISSVH/phdthesis.html

 However, I wouldn't count on using it to tell you how to efficiently code a
kd-tree build routine.  It's extremely light on implementation details.
There's one sentence in section 4.9 that suggests that he may have
implemented his kd-tree in a manner similar to how I implemented mine --
but I've no clue exactly how he did it.

-Daniel Neilson

Post a reply to this message