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,
of the mesh (such as
boundaries or specially labeled edges or vertices of the mesh), where other
These rules combine the data of the control mesh with given extra data.
A particular case of
combined subdivision schemes
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
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
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
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
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.