I have implemented simple kd-tree support for my renderer ssRay and it
already rocks! See the image attached. Now I can finally use more
interesting models and render complex scenes without unbearable
performance hit.

Now the kd-tree is build with idiotic spatial median subdivision (ie.
simply divide each node in half). That is stupid and I'll implement a
surface area heuristic cost model next. That should improve performance
considerably. But still, all looks pretty good so far!

I love this path tracing stuff :D

ssRay homepage:

http://www.saunalahti.fi/~sevesalm/ssRay/ssRay.php

Post a reply to this message

Attachments:
Download 'kuva28.jpg' (36 KB)

Preview of image 'kuva28.jpg'

Severi Salminen <sev### [at] NOTTHISsaunalahtifiinvalid> wrote:
> I have implemented simple kd-tree support for my renderer ssRay and it
> already rocks! See the image attached. Now I can finally use more
> interesting models and render complex scenes without unbearable
> performance hit.

It's snakes on a *** plane!  I like it.  Really, it's no small feat to get this
far.  What's after kd-trees?

 - Ricky

Post a reply to this message

> I have implemented simple kd-tree support for my renderer ssRay and it
> already rocks! See the image attached. Now I can finally use more
> interesting models and render complex scenes without unbearable
> performance hit.

Wow that's really cool that you have done this all yourself so quickly, at 
this rate you'll be ahead of POV in a few months :-)

> Now the kd-tree is build with idiotic spatial median subdivision (ie.
> simply divide each node in half). That is stupid and I'll implement a
> surface area heuristic cost model next. That should improve performance
> considerably. But still, all looks pretty good so far!

I guess the goal here is to have the minimum number of steps down the 
kd-tree on average over all rays.  My very naive instinct is that you should 
split the nodes so there are equal numbers of triangles on each side, but 
that's probably wrong if you don't take into account the size of each 
triangle.

> I love this path tracing stuff :D

Yes if you have the time it can produce beautiful results, I have been using 
MCPov almost exclusively recently for renders, I hope that path-tracing can 
make it into official POV at some point.

BTW I have two questions about your tracer:

1) Multi-threaded, this can't be harder than running multiple instances at 
once, but does it already utilise all cores or how hard will it be to 
implement that?

2) How do you describe the scenes at the moment, are they all hard coded or 
do you have some scripting system already?

Post a reply to this message

scott wrote:

> Wow that's really cool that you have done this all yourself so quickly,
> at this rate you'll be ahead of POV in a few months :-)

:D Well, maybe not :) POV has a totally different approach to ray
tracing problem so it is hard to compare. With path tracing it is SOOOO
much easier to get many light related phenomena correct. With POV the
devs had to work hard to get the desired result as many phenomena are
separately implemented. With ssRay I don't have to shoot photons
separately to get caustics, I don't have to implement radiosity to get
global illumination and all related indirect effects etc. I get them for
free. Who doesn't like that :)

> I guess the goal here is to have the minimum number of steps down the
> kd-tree on average over all rays.  My very naive instinct is that you
> should split the nodes so there are equal numbers of triangles on each
> side, but that's probably wrong if you don't take into account the size
> of each triangle.

That is intuitively a good solution but in reality it is a bad one :D
Actually you want to cut off big empty regions early. That makes tracing
and traversing the tree cheap. If you take "object median" as the split
point you get two expensive child nodes. That usually is not a good idea.

But there are some very good documents and books about kd-tree creation
so I don't have to re-invent the wheel completely.

Basically you assign a certain cost for ray-object intersection test.
And certain cost for traversing an interior node of the kd-tree. Then
you figure out all the possible splitting plane points (in all 3
directions) and use the cost model to minimize the kd-tree cost. The key
here is to use the surface area of a node to get a probability that a
random ray would actually go through that node.

There is also another very interesting acceleration structure called
BIH: bounding interval hierarchy. It looks quite simple and still very
efficient. I'll stick to ke-tree for now but will definitely try BIH at
some point.

> Yes if you have the time it can produce beautiful results, I have been
> using MCPov almost exclusively recently for renders, I hope that
> path-tracing can make it into official POV at some point.

I hope that too! Fidos has shown that POV can be turned to path tracer.
And POV has a very strong SDL and other infrastructure so it would be
nice to have alternative rendering engine for it.

I still think that most POV users prefer the most realistic outcome of
the renderings. And unbiased is the best way to go if that is the main
goal. I hope the devs will consider that with POV4.

> 1) Multi-threaded, this can't be harder than running multiple instances
> at once, but does it already utilise all cores or how hard will it be to
> implement that?

Yes, ssRay is already multithreaded and scales very well - basically
perfectly. I have 2 cores running at ~100% and ssRay handles as many
threads as the user wants. Now I assign different pixel rows for each
thread. That is actually a good approach. I don't need mutexes and the
load is still quite well balanced in almost all scenes.


> 2) How do you describe the scenes at the moment, are they all hard coded
> or do you have some scripting system already?

Hardcoded at the present. At some point I have to implement a parser but
that is not a fun thing to do and developing a good SDL takes time...

Post a reply to this message

triple_r wrote:

> It's snakes on a *** plane!  I like it.  Really, it's no small feat to get this
> far.  What's after kd-trees?

Thanks!

Hmm. I really don't know where to start after the SAH cost model of
kd-tree is finished. Most likely I'll spend some time refining the code
and making it more polished etc.

But I'll have to think about the material interface a bit more. Now I
have simple reflections and refractions which are not physically correct
and look unrealistic. Real reflections are angle dependent. A glass ball
reflects more at low angle than when looking form surface normal
direction. This has to be implemented properly.

I want to have Fresnel (or some good approximation like Shlick's
approximation). We'll see :D

Post a reply to this message

> There is also another very interesting acceleration structure called
> BIH: bounding interval hierarchy. It looks quite simple and still very
> efficient. I'll stick to ke-tree for now but will definitely try BIH at
> some point.

BTW there is an interesting document I came across a while back that 
involved working on sets of rays rather than just individual rays, might be 
an interesting read.

ftp://download.intel.com/technology/computing/applications/download/mlrta.pdf

> I still think that most POV users prefer the most realistic outcome of
> the renderings.

Agreed, after all we're using raytracers because we prefer quality over 
speed, as computers get faster it's only natural that we look for higher 
quality methods to use.

> Now I assign different pixel rows for each
> thread. That is actually a good approach. I don't need mutexes and the
> load is still quite well balanced in almost all scenes.

Oh yeh I was going to ask about anti-aliasing, do you get this for free too 
with your algorithm - or do you need to specifically jitter each primary ray 
somehow?

> Hardcoded at the present. At some point I have to implement a parser but
> that is not a fun thing to do and developing a good SDL takes time...

Yes of course, always the boring bit getting the UI working well, much more 
fun to work on the actual algorithm!

Post a reply to this message

Severi Salminen wrote:
> I want to have Fresnel (or some good approximation like Shlick's
> approximation). We'll see :D

I want to see it do polarization. ;-)

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

Darren New wrote:

> I want to see it do polarization. ;-)

NOOOOOOOOO! Anything but that :D At least I have wavelength dependent
rendering higher on the list to allow realistic dispersion. But it's not
THAT high on the list.

-- 
Severi Salminen
http://www.iki.fi/severi

Post a reply to this message

Severi Salminen wrote:
> NOOOOOOOOO! Anything but that 

OK, fluorescence, then!

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

Severi Salminen <sev### [at] NOTTHISsaunalahtifiinvalid> wrote:
> Hardcoded at the present. At some point I have to implement a parser but
> that is not a fun thing to do and developing a good SDL takes time...

I've always thought it would be neat to leave it as an API.  POV-Ray's SDL is
already similar to C, but you'd also get the benefits of being able to use
numerical libraries, object-oriented programming, and of course, there's SPEED.
 All without actually having to write or maintain a parser!  The renderer would
just be a static or dynamic library.  Of course you have to compile and link
over and over, but how bad is that, really?

#include <ssray.h>
int main( int argc, char** argv ) {

     Scene s (argc, argv);

     vec x (0.0, 0.0, 0.0);
     vec dx (1.0, 0.0, 0.0);

     Union u;

     for( int i=0; i<100; i++) {
          u.push(
               sphere( x, 1.0,
                   pigment( Red )
               )
          );
          x += dx;
     )

     s.push(u);

     s.Render();

     return 0;
}

Upon reflection, maybe the answer is, "Pretty bad."  I think it's still the
approach I'd take since I don't actually know how to write a proper parser.

 - Ricky

Post a reply to this message