SDS Raytracer

Ideas, enhancements, feature requests and development related discussion.

SDS Raytracer

Postby dcuny » Mon Apr 21, 2008 8:17 pm

You'd think I'd have learned by now, but I've decided to look into writing another raytracer.

I still think that a scanline renderer is a great idea, but Blender pretty much has all the cool features I'd like already. So when JPatch SDS reached the point where it's ready to start generating images, I'll be pushing for exporting to Blender. (Yes, I know I'll probably be the one to be writing the scripts. ;)).

Despite scanline rendering being the best approach for animation, I keep coming back to raytracing for the eye candy. Relection, refraction, soft shadows, subsurface scattering, accurate lighting: you get it all. Of course, the performance cost is usually prohibitive.

Which brings me to the idea of writing a "pure" SDS raytracer. That is, instead of rendering a finely tesselated mesh, raytracer renders the SDS directly. The general approach seems to be fairly straight forward: use the coarse mesh to generate bounding boxes, and recursively subdivide the mesh to determine the actual intersection surface. There are issues with dealing with "cracks", but on the whole, it doesn't look overly complicated.

Interestingly enough, speed is not one of the advantages of directly raytracing SDS - it's typically a bit slower than raytracing a subdivided model. What you do get is a large savings in memory usage.

I doubt that this will have any practical use, since Renderman supports SDS, and JPatch can export tesselated mesh to renderers that expect triangles. But it should keep me busy for a while.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SDS Raytracer

Postby sascha » Mon Apr 21, 2008 8:50 pm

This is going to be tricky.
What you'll need is adaptive subdivision during the rendering process. I agree with the bounding box part, but after that you still have to decide how many levels of subdivisions are needed for a particular ray.
Needless to say, the magic term as always is... right: ray differentials.
Most of the computed subdivision levels can be re-used with later rays, so you'd also need some clever caching algorithm to speed things up.

3Delight does just that - and still lets you use REYES and raytracing at the same time (e.g. starting with a simple REYES approach, and then calling the raytracer when a shader calls e.g. the trace() function).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SDS Raytracer

Postby dcuny » Tue Apr 22, 2008 1:34 am

The paper Packet-based Ray Tracing of Catmull-Clark Subdivision Surfaces looks like it addresses a number of issues your brought up.

But my plan is to start out with something fairly simple (perhaps the Loop subdivision scheme) and use a naive recursive approach, just to get a handle on how things work. If I can get past that point, I'll start looking at Catmull Clark subdivision and start worrying about things like efficiency.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SDS Raytracer

Postby sascha » Tue Apr 22, 2008 7:44 am

Packet-based Ray Tracing of Catmull-Clark Subdivision Surfaces wrote:(...) although instead of ray differentials we use a cheaper distance metric: level = log2 (αd/D), where d is the diameter of the bounding box for the scene, D is the minimum distance from the camera to the center of the patch, and α is a user parameter for the scene.

I wouldn't do that. This approach will fail for rays refracted in or reflected from a curved surface. Also keep in mind that you'll need the ray differentials for shader antialiasing (e.g. MIP mapping) anyway, IMHO there's no way around it.
dcuny wrote:perhaps the Loop subdivision scheme

Loop subdivision is pretty useless for JPatch models, and the Catmull Clark scheme is not that complicated. I'd start with Catmull-Clark, but without creases and corners (and implement them later). I'm willing to help with the subdivision code :)
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SDS Raytracer

Postby dcuny » Tue Apr 22, 2008 8:47 am

Sascha wrote:I'd start with Catmull-Clark, but without creases and corners (and implement them later).

You're right, there's probably not any value to using a different method.

This approach will fail for rays refracted in or reflected from a curved surface.

The packet-based approach only seems to be an advantage for the primary rays. For everything else, there's no particular speed advantage.

It seems the main "trick" to doing things properly is getting tight bounds on the patches. The paper An Accurate Error Measure for Adaptive Subdivision Surfaces proposes a method for determining the maximum error for Loop subdivision. I'm too tired (and stupid) to get too deep into the details. The Packet-based Ray Tracing of Catmull-Clark Subdivision Surfaces paper proposes a simpler approach: subdivide the mesh one level by default as it's loaded, and then subdivide a number of times again to calculate a tight bounding box. And the actual intersection code is still an approximation: after splitting the patch n times, it splits the quad into two triangles and performs an intersection test on the them.

All things considered, it doesn't make for a compelling reason to implement "native" SDS raytracing. :|

I'll keep looking at it, though.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SDS Raytracer

Postby sascha » Tue Apr 22, 2008 9:06 am

The packet-based approach only seems to be an advantage for the primary rays

REYES can do everything that primary rays can do - only faster. There are things REYES can't do (raytraced shadows, reflections and refractions for example), which can be done using secondary rays (there's a trace() function in shaderlanguage). So I think the hybrid REYES/Raytracing approach implemented by PrMan and 3Delight is the way to go.

I'd love to see this in an open source renderer, but in the meantime I'm happy with 3Delight.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SDS Raytracer

Postby dcuny » Tue Apr 22, 2008 9:11 am

The literature pretty much says that SDS is very efficient for scanline rendering. So a combination of the two is really the way to go.

Blender's actually got a decent raytracer built into it... As I mentioned before, if we could get that working nicely with JPatch, it would probably prove to be a great engine for animation.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SDS Raytracer

Postby sascha » Tue Apr 22, 2008 11:34 am

We could try to convince the 3Delight folks to GPL dual license it (à la MySQL, QT, etc.). Technically, calling the API via RIB and linking to the C API should be the same thing - so calling the renderer from proprietary software like Maya would be a GPL violation and thus require a proprietary license, yet calling it from a GPL'd application would be OK.

While the Blender renderer is an interesting option, I don't know how its shaders work. RenderMan SL is kind of an industry standard, so sticking with it would be a good idea, at least I think so. That reminds me that an RSL to Java-Bytecode compiler would be a cool thing...
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SDS Raytracer

Postby John VanSickle » Tue Apr 22, 2008 2:29 pm

If the SDS uses the Catmull-Clark scheme, after the second subdivision level, you can approximate the limit surface using Bezier bicubic patches; Charles Loop has a doc on this at his Microsoft web page. This is good for a ray tracer because once you have it down to Beziers, there is no longer any variance in the data structures involved.

http://research.microsoft.com/~cloop/msrtr-2007-44.pdf
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: SDS Raytracer

Postby sascha » Tue Apr 22, 2008 3:44 pm

you can approximate the limit surface using Bezier bicubic patches...

...as long as all of the vertices are regular (i.e. of valence 4).

I'd rather say that using B-Spline patches introduces yet another datastructure. It still might pay off performance wise, but I wouldn't do that to simplify the code. :wink:
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SDS Raytracer

Postby dcuny » Tue Apr 22, 2008 5:29 pm

John VanSickle wrote:If the SDS uses the Catmull-Clark scheme, after the second subdivision level, you can approximate the limit surface using Bezier bicubic patches; Charles Loop has a doc on this at his Microsoft web page.

Packet-based Ray Tracing of Catmull-Clark Subdivision Surfaces performs an initial subdivision on the patches, for similar reasons. The vast majority of the patches resolve to quads, which can be stored efficiently. They also note that after subdivision, irregular patches contain at most a single extraordinary vertex, so there's really only a single special case to deal with.

I'm not sure how much better converting to Bezier patches vs. "native" SDS is. I suspect that the Bezier solution is used because most renders offer support for Bezier patches. But most of the papers I've seen end up solving Bezier patches recursively - very much like SDS patches.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SDS Raytracer

Postby dcuny » Tue Apr 22, 2008 5:52 pm

sascha wrote:We could try to convince the 3Delight folks to GPL dual license it (à la MySQL, QT, etc.). Technically, calling the API via RIB and linking to the C API should be the same thing - so calling the renderer from proprietary software like Maya would be a GPL violation and thus require a proprietary license, yet calling it from a GPL'd application would be OK.

It's being used in Daz3D. I'm curious what sort of license they're using, since Daz3D is being given away for free.

While the Blender renderer is an interesting option, I don't know how its shaders work.

Then again, I suspect most of your end users probably don't want to write shaders, either. :P

For the most part, you can map Blender to POV-Ray sort of generic parameters (specular, roughness and so on). In addition to the built-in features, you can also have user-defined shaders written in Python. I know there's some work going on getting Renderman functions ported over, so it'll be easier to convert shaders.

But I think the better approach would be to do what SplutterFish and Sunflow do: offer a set of general materials with various parameters, such as plastic, metal, glass, skin, and so on.

I understand specializing on Renderman, but I'd hate to see JPatch do that to the exclusion of other renderers. :(
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SDS Raytracer

Postby sascha » Tue Apr 22, 2008 8:28 pm

The vast majority of the patches resolve to quads...

After one level of subdivision, all patches are quads (but read on...)
They also note that after subdivision, irregular patches contain at most a single extraordinary vertex

Yes, but that's wrong!
They're not the first who make this mistake - I've read a paper about hardware subdivision unsing GLSL, and their approach also assumed this - unfortunately it doesn't work this way. Here's a simple example:
Take one five-sided polygon. One of it's vertices is irregular, say valence 3 (i.e. has three adjacent edges). Now perform one level of subdivision on the five-sided polygon. You'll yield 5 quadrilaterals, but one of those has the valence 3 vertex in one corner, and the valence 5 vertex (the center of the 5-sided polygon) in another corner. QED.

A very basic mesh that shows the problem is a simplified house:
house.png
house.png (5.01 KiB) Viewed 10943 times


So you'd need a second level of subdivision to get there, and two levels of subdivisions are quite a lot (it roughly multiplies the number of surfaces by a factor of 16!)

No need to panic - my dicer worked just this way: It dices any quadrilateral with at most two irregular vertices (which have to be on opposite corners) - there's a maximum allowed valence (since you'll have to store the neighbors of the irregular vertex in some array), but something like 32 should be more than enough.

I understand specializing on Renderman, but I'd hate to see JPatch do that to the exclusion of other renderers.

That's not the plan.
Right now I don't even know if there will be specialized support for RenderMan shaders. The plan for the initial version is that JPatch exports just the geometry, and the users have to care about the shaders (just like in JPatch 0.4). You could specify some variables (like color, specularity, etc.), which JPatch would then map to shader variables. The only other thing needed is the name of the shader - but the shader itself has to be built externally. Same for POV-Ray textures - you'd specify a POV-Ray macro that accepts the material's variables defined in JPatch as input parameters and either creates the texture or loads its definition from file. Same would work with Python scripts and I guess any other renderer.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SDS Raytracer

Postby dcuny » Tue Apr 22, 2008 11:08 pm

Thanks for clarifying that. After Googling around for some information, the best source of information on Catmull-Clark SDS turned out to be located on the JPatch Wiki. :)

I think I've got an OK grasp of the algorithm, I just need to play with it on paper for a while.

Sascha wrote:That's not the plan.

Ah, I misunderstood. :oops:
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SDS Raytracer

Postby dcuny » Wed Apr 23, 2008 8:30 am

I was reading through the paper Implementing Subdivision and Multiresolution Surfaces (no link, sorry) and the author suggested that is was actually more efficient to use a fairly simple data structure instead of a half-winged approach:
One possible and relatively simple data structure for polygons is:
Code: Select all
struct Polygon {
   vector<Vertex*>   vertices;
   vector<Polygon>   neighbors;
   vector<short>      neighborEdges;
   ...
}
For each polygon, we store an array of pointers to vertices and an array of adjacent polygons (neighbors) across corresponding edge numbers. We also need to know for each edge what corresponding edge number that edge is, when seen from the neighbor across that edge. This information is stored in the array neighborEdges. In addition, if we allow non-orientable surfaces, we need to keep track of the orientation of the neighbors, which can be achieved by using the signed edge numbers in the array neighborEdges. To complete the representation, we add a data structure for vertices to the polygon data structure.
Do you see any disadvantages with this approach? I don't know enough about Catmull-Clark SDS to know what sort of assumptions are being made here. I assume that, for the purposes of being able to dynamically edit a mesh, the half-winged is superior. But since a raytracer would be rendering a static scene, this wouldn't be important.

This entire bit might be moot, since JPatch could pass the raytracer the SDS patch directly, instead of having the overhead of the mesh to deal with. Still, I should at least know how it works.

One thing I haven't really seen in the literature yet is how "hook" sorts of topologies are dealt with. Obviously, you have to handle them or you get cracks in the rendering, but beyond that generality, I haven't seen much.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Next

Return to Development

Who is online

Users browsing this forum: No registered users and 1 guest

cron