Christoph Hormann <chr### [at] gmxde> 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.

 See the web page listed above. I've updated it with a couple of timing
results from Ingo's mesh maker macros.

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

 I've made a patch against the POV-Ray 3.50c sources available for those
who're interested. You can grab them directly from
http://www.cs.ualberta.ca/~dneilson/povray-3.50c-kdtree-patch.tgz

 To apply the patches you'll have to:
1) Download the povray 3.50c sources from the povray web site and uncompress
it.
2) Unzip the archive into the src directory.
3) Next type "cat povray-3.50c-kdtree.patch | patch -p1" from the src
directory.
4) Lastly, run povray-3.50c/configure and modify src/Makefile to compile and
link in kdtree.cpp & kdtree.o.

 Note that the kdtree build code can require a lot of stack space. So, if
the code crashes make sure that you're running with a big stack (ulimit -s
unlimited).

-Daniel Neilson

Post a reply to this message

Daniel Neilson wrote:
> 
>  I've made a patch against the POV-Ray 3.50c sources available for those
> who're interested. You can grab them directly from
> http://www.cs.ualberta.ca/~dneilson/povray-3.50c-kdtree-patch.tgz

I get a 403 Forbidden.

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

"Daniel Neilson" <dneilson@here;here.is:cs.ualberta.ca> wrote in
news:web.4090666b66fba34228de1b160@news.povray.org: 

...
>  I've made a patch against the POV-Ray 3.50c sources available for
>  those 
> who're interested. You can grab them directly from
> http://www.cs.ualberta.ca/~dneilson/povray-3.50c-kdtree-patch.tgz
...

I'm particularly interested in studying your kd-tree implementation 
(construction, balancing and look-up), but, as Cristoph already noticed, I 
get a "403 Forbidden" error.
Maybe you have to put a link on your web pages.

Thanks for making available your code.

--
Alessandro Falappa

Post a reply to this message

Alessandro Falappa <don### [at] nessunoit> wrote:
> "Daniel Neilson" <dneilson@here;here.is:cs.ualberta.ca> wrote in
> news:web.4090666b66fba34228de1b160@news.povray.org:
>
> ...
> >  I've made a patch against the POV-Ray 3.50c sources available for
> >  those
> > who're interested. You can grab them directly from
> > http://www.cs.ualberta.ca/~dneilson/povray-3.50c-kdtree-patch.tgz
> ...
>
> I'm particularly interested in studying your kd-tree implementation
> (construction, balancing and look-up), but, as Cristoph already noticed, I
> get a "403 Forbidden" error.
> Maybe you have to put a link on your web pages.
>
> Thanks for making available your code.

 Sorry about that. Forgot to actually change the permissions on the file.
It's accessable now.

 If anyone has questions about the code, I'd be happy to try to answer them.
My email address can be found in the headers of kdtree.h and kdtree.cpp.

-Daniel

Oh! Since I didn't explicitly mention it, the patch is against the 3.50c
unix sources.

Post a reply to this message

Daniel Neilson wrote:
> 
>  See the web page listed above. I've updated it with a couple of timing
> results from Ingo's mesh maker macros.

But everything below 100000 triangles is not very useful.

> 
>  I've made a patch against the POV-Ray 3.50c sources available for those
> who're interested. You can grab them directly from
> http://www.cs.ualberta.ca/~dneilson/povray-3.50c-kdtree-patch.tgz

My first comments:

- while the kd-tree for the main scene objects is optional and can be 
turned on/off with options meshes seem always be using the kd-tree.
- in contrast to meshes blobs don't have the kd-tree bounding.
- it seems faster in a lot of scenes but i had problems with others 
(isocacti.pov for example does not render).
- your patch would be much better usable if you would not modify all 
source files (even if it's just the header).

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:
> Daniel Neilson wrote:
> >
> >  See the web page listed above. I've updated it with a couple of timing
> > results from Ingo's mesh maker macros.
>
> But everything below 100000 triangles is not very useful.

 Fair enough. I reran another render for the p_bretzel.pov demo mesh, but I
changed the Iter_U and Iter_V parameters of the parameter{} block to 500
and 2000, respectively (from 50 and 200, respectively).

On my 3.0GHz P4, the render/trace times were

 BVH Mesh: 31.40 seconds
 KD-Tree Mesh: 24.65 seconds

 Also of interest is the time to parse the scene using the two different
versions (this includes the time required to build the BVH/kd-tree for the
mesh)

 BVH Mesh: 710.95 seconds
 KD-Tree Mesh: 667.54 seconds

> My first comments:
>
> - while the kd-tree for the main scene objects is optional and can be
> turned on/off with options meshes seem always be using the kd-tree.

 That's true. For comparing the two I actually had two code bases. One used
the old mesh and one used the new -- exchanging the two is just a matter of
copying in the new mesh.* files and editing two lines in parse.cpp. I'd
figured it was a pretty safe assumption that no mesh would produce a
degenerate kd-tree. Easily changed, though. I'll see if I can't find some
time in the next couple days to alter that.

> - in contrast to meshes blobs don't have the kd-tree bounding.

 I hadn't even looked at blobs, actually. Didn't even occur to me that they
might be using a BVH. I'll see what I can do about altering that as well.

> - it seems faster in a lot of scenes but i had problems with others
> (isocacti.pov for example does not render).

 That's very odd. My version actually renders isocacti.pov just fine. Does
it print out any sort of errors, or does it crash, or does it render a
blank image, or... ? Perhaps something's wonky about your patched version?

> - your patch would be much better usable if you would not modify all
> source files (even if it's just the header).

 Fair enough. I'll do that with the next iteration of the patch.

-Daniel Neilson

Post a reply to this message

Daniel Neilson wrote:
> 
>  That's true. For comparing the two I actually had two code bases. One used
> the old mesh and one used the new -- exchanging the two is just a matter of
> copying in the new mesh.* files and editing two lines in parse.cpp. I'd
> figured it was a pretty safe assumption that no mesh would produce a
> degenerate kd-tree. Easily changed, though. I'll see if I can't find some
> time in the next couple days to alter that.

That's mostly a question of it being includable in a patch collection 
like MegaPOV where we have the convention that all patches have to be 
deactivated by default.

>>- it seems faster in a lot of scenes but i had problems with others
>>(isocacti.pov for example does not render).
> 
>  That's very odd. My version actually renders isocacti.pov just fine. Does
> it print out any sort of errors, or does it crash, or does it render a
> blank image, or... ? Perhaps something's wonky about your patched version?

It just halts before starting to render, i assume stuck in some loop or so.

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:

> >>- it seems faster in a lot of scenes but i had problems with others
> >>(isocacti.pov for example does not render).
> >
> >  That's very odd. My version actually renders isocacti.pov just fine. Does
> > it print out any sort of errors, or does it crash, or does it render a
> > blank image, or... ? Perhaps something's wonky about your patched version?
>
> It just halts before starting to render, i assume stuck in some loop or so.

 I just ran povray on isocacti.pov using the optimization settings present
in the Makefile that you sent me. Just give POV a few seconds. There's
something about this particular scene which makes building the kd-tree take
a little bit more time than I'd like -- I suspect it's all the rocks
intersecting with the ground. On my P4 3.0GHz machine here, it takes about
5 seconds to build the kd-tree for that particular scene.

-Daniel Neilson

Post a reply to this message

Daniel Neilson wrote:
> [...]
> 
>  I just ran povray on isocacti.pov using the optimization settings present
> in the Makefile that you sent me. Just give POV a few seconds. There's
> something about this particular scene which makes building the kd-tree take
> a little bit more time than I'd like -- I suspect it's all the rocks
> intersecting with the ground. On my P4 3.0GHz machine here, it takes about
> 5 seconds to build the kd-tree for that particular scene.

I waited for about half a minute - 48 seconds were required in fact.

So we have:

standard POV: 6s parse + 59s trace
your kd-tree: 48s parse + 60s trace

Since scenes containing a lot of small objects placed on the surface of 
a large object are very common (any landscape with plants, houses, rocks 
etc.) i think this is a major problem.  In a large size render the parse 
time difference will of course not be so important but it would not be 
possible to really replace the existing technique with your system with 
such a difference.

Also note that in this scene the memory use difference is 186Mb with the 
kd-tree vs. 27Mb with standard POV!

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:
> Daniel Neilson wrote:
> I waited for about half a minute - 48 seconds were required in fact.
>
> So we have:
>
> standard POV: 6s parse + 59s trace
> your kd-tree: 48s parse + 60s trace
>
> Since scenes containing a lot of small objects placed on the surface of
> a large object are very common (any landscape with plants, houses, rocks
> etc.) i think this is a major problem.  In a large size render the parse
> time difference will of course not be so important but it would not be
> possible to really replace the existing technique with your system with
> such a difference.
>
> Also note that in this scene the memory use difference is 186Mb with the
> kd-tree vs. 27Mb with standard POV!

 Indeed, I'd noticed the memory requirements last night as well. It hits
that peak during kd-tree building. The resident size of the program goes
way down to normal range post-build. There are arrays allocated on the
stack at each level of the recursion during build. It really adds up.

 Note that I only suspect that it's the tonne of small objects intersecting
the ground that's causing the slowdown. I don't actually know that that is
the cause -- I've not spent a lot of time investigating it. More of an
educated guess, really.

 I actually don't think there's such a thing as a universally better
acceleration structure. That's why I'd never advocate flat out replacing
one structure with another. Rather, I'm a big fan of supplying options to
the user. Especially when supplying those options does not interfere with
the rest of the system -- as is the case with supplying additional
acceleration structures. If a user's running on a machine with a large
amount of memory, then they can try the kd-tree. Same logic as allowing the
user to turn off the vista and light buffers -- there are scenes where it's
just a horrible idea to turn them on.

 That said, if anyone knows of a better way to build a kd-tree that's at
least as fast and uses less memory, I'd be all for hearing about it.

-Daniel Neilson

Post a reply to this message