Combined subdivision schemes / Adi Levin
Combined subdivision schemes extend the notion of subdivision schemes in the following way: While subdivision schemes operate on a given mesh and generate a new mesh, combined subdivision schemes generate the new mesh taking into consideration additional conditions - such as boundary conditions, and transfinite interpolation conditions - that are prescribed on the limit surface. These conditions are taken into consideration in each iteration, and if the combined subdivision scheme is constructed carefully, the limit surfaces satisfy these extra conditions, and are of known smoothness.A combined subdivision scheme is non-uniform in the following sense: It operates almost everywhere like a uniform subdivision scheme, except near special areas of the mesh (such as boundaries or specially labeled edges or vertices of the mesh), where other rules operate. These rules combine the data of the control mesh with given extra data.
A particular case of combined subdivision schemes are homogeneous combined schemes. These are combined subdivision schemes that do not take into considerations any given data other than the control mesh. But their structure is similar - They operate almost everywhere like uniform subdivision schemes, except near 'special areas' where different rules operate. Every subdivision scheme that is defined on meshes with boundaries falls into this category. The most important case is the case of quasi uniform subdivision schemes - where the 'special area' is a plane (or in the multivariate case, a hyper-plane).
The central issue of the analysis of subdivision schemes is the smoothness of their limit functions, near the 'special areas'. Other issues are - conditions for generation of polynomials by combined subdivision schemes, approximating by limit functions of combined subdivision schemes.
The simplest examples of combined subdivision schemes are constructed by choosing a uniform scheme (such as Loop's scheme or Catmull Clark's scheme ) to operate away from the boundary of the mesh, and calculate the boundary vertices by sampling given boundary curves.
|
The figure to the right shows how it works:
Catmull Clark's scheme operates everywhere except on the boundaries.
The boundary vertices are simply sampled from the given boundary curves.
Notice that the given boundary curves are arbitrary - they do not have to be
splines or subdivision curves.
This scheme generates smooth surfaces whose curvature is continuous near the boundary, provided that the boundary vertices are equally spaced along the boundary curves with respect to the curves' parametrization. |
|
|
The figure to the right demonstrates a combined scheme
for meshes that consist of triangular faces.
Here Loop's scheme operates everywhere except on the boundaries.
The boundary vertices are sampled from the given boundary curves.
Near a breakpoint of the boundary a special stencil works to enhance the smoothness
there.
This is a simple algorithm for filling an N-sided hole among arbitrary curves. The resulting surfaces have continuous curvature near the boundaries except at the break-points of the boundaries, where the surface is only almost G2. |
|
|
The way in which combined subdivision schemes operate near the boundary
is by applying functionals on the given boundary data.
These functionals are not restricted to sampling.
In this example we use Catmull Clark's scheme away from the boundary of the mesh.
The boundary vertices are not placed on the boundary
curves, but are still calculated by a functional of the boundary curve.
As the iterations progress, the boundary vertices converge to the given
boundary curve.
In fact, we realized that this scheme is superior to the last two, in the sense that it generates nicer shapes, and in its approximation properties. |
|
|
As said above, the functionals that operate on the given boundary data
are not restricted to sampling.
This is an example for a combined subdivision scheme based
on Catmull Clark's scheme, that uses not only a given boundary curves,
but also cross-boundary derivatives - to calculate the layer of vertices
that are near the boundary.
This results in curvature continuous
limit surfaces that satisfy tangent plane boundary conditions.
This algorithm for blending cylindrical shapes is significantly simpler than trying to do so using methods based on parametric surfaces. |
|
| If you want more details, go back to my home page and browse my papers. |
|