Force limit surface to pass through all the control mesh vertices

[José António Ferreira Calvário]

Hi everyone,

I'm trying to figure out if it's possible to force the subdivision algorithm to generate a limit surface that passes on all of the control mesh vertices, without loosing the roundness of the final result.

Thanks in advance,

José Calvário

[Barry F]

The limit surface can be made to interpolate all control points, but it is a global operation and will require some linear algebra support to solve a large system of equations. Whether the desired roundness you speak of is retained depends on the nature of the shapes you're dealing with and your criteria.

There is a relatively straightforward solution that is available -- which I'll describe briefly here -- but if that's not satisfactory, I've included some references if you want to pursue something better...

Given a mesh with N control vertices, the requirement to interpolate the position of each provides N conditions to satisfy in terms of those N vertices. For Catmull-Clark surfaces, the subdivision limit mask for each vertex (i.e. the set of coefficients for the vertex and its neighbors that compute the limit position, which you can get from OpenSubdiv) provides these N conditions. This yields a linear system of N equations in terms of the N vertices, for which a unique solution exists (provided the NxN matrix is non-singular, which is generally the case). So if you want to keep the mesh topology with the same N vertices, this is your only solution.

Unfortunately the quality of the resulting surface may not always be desirable. Catmull-Clark surfaces generalize uniform bi-cubic B-splines, and interpolation with B-splines (curves and surfaces) has its draw backs.  B-splines are effective because they approximate the control points and so attenuate variations in the control hull, but constraining a curve or surface to interpolate the hull amplifies those variations. So while the resulting surface is still curvature continuous, it may undulate more, produce concavities in the surface where the mesh is convex, etc. (I don't have any examples handy, but you can probably find them if you search.) Still, some find the results satisfactory.

More sophisticated global interpolation techniques are available but they require more degrees of freedom to satisfy all N interpolation constraints in addition to other conditions to affect/improve surface quality. So they will use a mesh that is subdivided at least once from the original (leading to 4x as many control vertices) in conjunction with numerical optimization techniques.

An early reference from OpenSubdiv's page of references is "Efficient, Fair Interpolation with Catmull-Clark Surfaces", which describes the surface interpolation problem in more detail along with their particular solution using Catmull-Clark surfaces. You can follow the list of subsequent papers that cite this one for improvements or alternatives that suit your requirements.

Hopefully that helps. Surface interpolation is a long standing problem with decades of research and many solutions out there. I've been out of touch with the topic for a while, so unfortunately I can't direct you to more recent references that might be noteworthy.

[José António Ferreira Calvário]

Thank you Barry for your detailed and comprehensive answer.

Before trying to implement the solution you describe, I was planning on trying the following algorithm.

The main idea is to keep using the default OpenSubdiv model (which gives very good results) and try to "iteratively adjust" the control vertices positions until the resulting limit surface passes through the original control vertices.

The challenge here will be on how to "adjust" the control positions in order to make the iteration fast and convergent. I believe it's possible to compute an adjustment formula that will do the job, and I intend to implement one in the near future. I will do a post on this forum describing the results I will find.

Meanwhile, knowing that you have much more experience than I do on this subjects, can you think of any reason why this approach should not work?

Many thanks,

José Calvário 

--
You received this message because you are subscribed to a topic in the Google Groups "OpenSubdiv Forum" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/opensubdiv/mqCJXkEOaEE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to opensubdiv+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/opensubdiv/30e14861-d8be-4dac-8ba9-5e74ec725119n%40googlegroups.com.