Raytracing with OpenSubdiv

[darkhorse64]

Hi,

I want to add Catmull-Clark subdivision surfaces to my raytracing project (http://xrt.wikidot.com) using OpenSubdiv and I am pondering several options:

1 - tesselate the surface and render the polygons.

Easy but the tesselation level may have to go very high to avoid artifacts. This looks like a real memory hog.

2 - lazy evaluation.

The overall idea is to refine only individual faces of the mesh on request from the intersection algorithm. A nice property of Catmark surfaces is that
the limit surface of a face is contained into the bounding box of its 1-ring. Therefore, a tentative algorithm could be:

Split the mesh into tiny meshes (a coarse face + its 1-ring)

Select candidate meshes through your favorite accelerator (bvh, kd-tree)

Push the coarse face on a stack
While the stack is not empty
   Get the top of the stack
   Refine the face and its 1-ring.
  For each new face coming from the refinement of the face
     check the bounding box of the face and its 1-ring against the ray (this is why the 1-ring must also been refined)
    if the box is hit,
        either a stopping criterion is reached, record a hit
       or push the face on the stack


I think this can be implemented at the HBR level with some care because of multithreading issues. The ability to clone HBR classes would also greatly help.
The dark side of things is that HBR is not by design the fastest way to subdivide. However, I see at least two strong points:
* successive refinements get naturally cached which will benefit to neighbouring rays
* computing stencil for a hit point would be inexpensive because the refinement would have already been performed

Your opinion ?

3 - wait ;-)

The roadmap mentions that the Eval API should provide functionality to
* Project points onto the subdiv limit and return parametric coordinates.
* Intersect rays with subdiv limits.

Obviously, it isn't done yet but could someone share some pointers on the algorithms that will be used ?

        Regards

[manuelk]

Hello

Very astute questions:

1. Yes it's simple, but uniform subdivision is slow and will do a lot of work that is likely going to be wasted (never hit by a ray). Assuming there were a way of predicting which areas require lots of details, in adaptive mode, maintaining a water-tight surface is also far from easy (the clunky-ness of our feature adaptive part of the code should be scary enough...). Greedy solutions are less than ideal.
2. Lazy evaluation is obviously the way to go. I am not sure however that I would lock the granularity at the individual face level though: it's probably not going to be flexible enough to go from close-up to far-away cases. For some good hints I would recommend taking a look at this and these. Hbr should be all you need, but i don't think you can ever get an efficient implementation without generating your limit samples in a non-recursive manner. Even if you replaced Hbr with the most optimal recursive code, you would still be very slow compared to an adaptive algorithm that switches to bi-cubic b-spline patches as early as possible. Put differently, if you are writing a ray-tracer, Hbr is a very good start, but you will likely have to write a layer that is functionally equivalent to our EvalLimit code, but works in a lazy evaluation mode, rather than our greedy implementation. This implementation is obviously a back-burner problem for us since we already have a very efficient ray-tracer that has been implementing all this for quite a while now (PRman...)
3. We do have projection and intersection on our roadmap. However:
1. I only have fairly naive solutions to these problem at the moment, and a lot of other priorities...
2. We most likely would be targeting our implementation to texturing, articulation or simulation requirements, which likely will not be directly translatable to an efficient renderer...

Hope this helps !

M.

[darkhorse64]

On Saturday, October 5, 2013 9:52:57 PM UTC+2, manuelk wrote:

[....]

 

Lazy evaluation is obviously the way to go. I am not sure however that I would lock the granularity at the individual face level though: it's probably not going to be flexible enough to go from close-up to far-away cases. For some good hints I would recommend taking a look at this and these. Hbr should be all you need, but i don't think you can ever get an efficient implementation without generating your limit samples in a non-recursive manner. Even if you replaced Hbr with the most optimal recursive code, you would still be very slow compared to an adaptive algorithm that switches to bi-cubic b-spline patches as early as possible. Put differently, if you are writing a ray-tracer, Hbr is a very good start, but you will likely have to write a layer that is functionally equivalent to our EvalLimit code, but works in a lazy evaluation mode, rather than our greedy implementation. This implementation is obviously a back-burner problem for us since we already have a very efficient ray-tracer that has been implementing all this for quite a while now (PRman...)

 

The small detail I forgot ...

I'll think of the idea of adaptative lazy refinement (and intersecting bicubic patches whenever possible). However I have tried comparing adaptative and uniform refinement with the glViewer. I see significant differences between the two even for very simple shapes. The catmark cube is one of the worst: some parts of the shape show very poor refinement compared to the limit shape. With the more complex (chess pieces, car), Far is doing a better job.

We do have projection and intersection on our roadmap. However:

1. I only have fairly naive solutions to these problem at the moment, and a lot of other priorities...
2. We most likely would be targeting our implementation to texturing, articulation or simulation requirements, which likely will not be directly translatable to an efficient renderer...

I knew waiting was not a good option ...
 

Hope this helps !

Thanks for your answers

[manuelk]

On Saturday, October 5, 2013 2:16:59 PM UTC-7, darkhorse64 wrote:

 

The small detail I forgot ...

I'll think of the idea of adaptative lazy refinement (and intersecting bicubic patches whenever possible). However I have tried comparing adaptative and uniform refinement with the glViewer. I see significant differences between the two even for very simple shapes. The catmark cube is one of the worst: some parts of the shape show very poor refinement compared to the limit shape. With the more complex (chess pieces, car), Far is doing a better job.

Did you turn on the tessellation in adaptive mode with '+' and '-' (it's at the lowest by default) ? Once you have some tessellation, try turning on the camera LOD and fractional modes.

The idea of adaptive is that 95% of a surface is made of bspline patches: the quicker you get to a patch, the quicker you get to the limit... The cube has exactly the same accuracy as any other shape, in fact it is much more compact because it takes so few control vertices. 

[darkhorse64]

Yes. It's working great. More food for thought ...