PDA

View Full Version : subdivision surfaces



Taylor Holliday
02-25-2006, 03:31 PM
Does anyone know of an easy to use C/C++ open source library for rendering subdivision surfaces efficiently (e.g. Stam's SIGGRAPH 98 paper) w/o a GPU?

If I can't find one, I'm considering writing a library with a GLU-ish C interface, something like: sds.h (http://wtholliday.org/software/src/sds.h)

thoughts? (thanks!)

Brolingstanz
02-26-2006, 10:54 PM
Have you tried a google for Catmull-Clark/Loop subdivision? I know there's a bunch of code out there, if that's what you're looking for.

Mikkel Gjoel
02-27-2006, 11:05 AM
source:
http://www.multires.caltech.edu/software/fastsubd/
http://mrl.nyu.edu/~biermann/subdivision/
http://www.subdivision.org/subdivision/demos/index.jsp

Cheers,

Taylor Holliday
02-27-2006, 01:43 PM
Hi, yeah I've googled around quite a bit. Most of the code people have posted does explicit subdivision, which is too slow for my purposes (interactive modeling).

There is an implementation for this paper: http://www.multires.caltech.edu/pubs/fastsubd.pdf but it uses uniform sampling.

I've considered ripping an implementation from an existing subdivision modeler (blender, etc), but their implementations are tied to their respective architectures.

Taylor Holliday
02-27-2006, 01:50 PM
Hi Mikkel, didn't see your post. I mentioned the first link above and the second two use explicit subdivision. Also, the second two don't have documented APIs.

Taylor Holliday
02-27-2006, 01:53 PM
Just want to ensure I'm not re-inventing the wheel before I set out to write a nice SDS library. Would anyone like to see a lib with an api like GLU NURBS?

Brolingstanz
02-27-2006, 02:55 PM
Most of the code people have posted does explicit subdivision, which is too slow for my purposes (interactive modeling).Not sure what you mean here. Most if not all of the papers describing subdivision surfaces are presented in the context of interactive modelling. Even a fairly naive implementation of Catmull-Clark subdivision is adequate for many character modelling applications.

What'll be interesting to me is subdivision algorithms implemented on the GPU as geometry shaders become available in the coming year. There you'll have the ability to save lots of bandwidth by streaming a fairly simple control mesh and subdividing to arbitrary complexity on the GPU.

But I don't see why anyone would object to a subdivision library, in the finest tradition of the OpenGL API :-)

Mikkel Gjoel
02-28-2006, 01:56 AM
Hi Taylor.

The "FastSubd"-implementation is immensely fast. It uses tables to accelerate the calculations. There is also a paper describing hardware-implementation using render-to-vertexarray functionality. I believe a similar method is used to implement the "turbosmooth"-modifier in 3dsmax.

One of the advantages of this method is that you can do single-triangle subdivision - ie. you do not need to calculate the entire mesh to view or re-view a subset of the mesh. This is ideal in regards to interactive modelling - all you need is local connectivity (1-ring) information for the area you wish to subdivide. Of course, you should render the entire mesh at the same subdivision level (or take care of the cracks otherwise), but you don't need to calculate the entire mesh when modifying locally.


Kind regards,

Taylor Holliday
02-28-2006, 08:28 AM
Hi Leghorn, what I mean by explicit subdivision is that individual facets of finer meshes are dynamically allocated. I've implemented subd's this way and its pretty slow. An array-based implementation is faster.

best

Taylor Holliday
02-28-2006, 03:41 PM
Here's a very early draft of a spec for the library I'm thinking of: http://wtholliday.org/software/src/sds.pdf

Any suggestions would be greatly appreciated. I'm thinking of starting a sourceforge project for it.

thanks!

Mikkel Gjoel
03-01-2006, 03:09 PM
Hi, I have a couple of quick questions after having read the draft:

Since you're very explicit about not dividing the mesh uniformly, how do you plan on filling the gaps between oddly subdivided patches? How do you evaluate the SDS_PATH_LENGTH, SDS_PARAMETRIC_ERROR and SDS_DOMAIN_DISTANCE error-metrics?

Also, what happens to texturecoordinates - do you apply subdivision interpolation to them, or linear interpolation? Have you considered discontinous texcoords? I would humbly suggest using a general approach, attaching properties to vertices in an indexed face-set, and specifying an interpolation-method for each property - one being subdivision interpolation.

Wouldn't it be way easier for you to recieve the control-mesh in one interleaved data-array and one index-array?

I guess you plan on strictly using the normals of the resulting subdivision surface? Adding creases based on smoothinggroups or normal-continuity would be a nice feature :)

Kind regards,

Taylor Holliday
03-02-2006, 10:27 AM
Hi Mikkel,

Thanks for the reply. I don't mean to be dogmatic about not subdividing uniformly... I'm sure in some cases that could be the best approach. I'd like to have an interface which permits an implementation to use various methods, and indicate to the user which ones are available.


Since you're very explicit about not dividing the mesh uniformly, how do you plan on filling the gaps between oddly subdivided patches? How do you evaluate the SDS_PATH_LENGTH, SDS_PARAMETRIC_ERROR and SDS_DOMAIN_DISTANCE error-metrics? In the case of Catmull-Clark, conversion of regular regions to b-spline patches, and the use of Stam's exact evaluation approach for regions around extraordinary vertices should make evaluating the error metrics possible. The cracking problem could be handled as it is for adjacent b-spline patches. For other schemes, things may be harder.


Also, what happens to texturecoordinates - do you apply subdivision interpolation to them, or linear interpolation? Have you considered discontinous texcoords? I would humbly suggest using a general approach, attaching properties to vertices in an indexed face-set, and specifying an interpolation-method for each property - one being subdivision interpolation. Good point. I haven't thought yet about that... control over attribute interpolation is a must. I suppose to achieve discontinuous colors/texcoords, attributes would need to be applied to corners rather than vertices. Any suggestions for this interface would be much appreciated.



Wouldn't it be way easier for you to recieve the control-mesh in one interleaved data-array and one index-array?
Yes, and I will add that in.



I guess you plan on strictly using the normals of the resulting subdivision surface? Adding creases based on smoothinggroups or normal-continuity would be a nice feature
That's another open question. Support for creases is very important.

Thanks for the comments! I will add some stuff to the interface and see what you think.

best

Taylor Holliday
03-03-2006, 10:02 AM
I've updated the specification at http://wtholliday.org/software/src/sds.pdf and submitted a sourceforge project registration.