The VSLib software package is a general
purpose optimization engine useful for designing interesting curve,
surface, and volume shapes. This
package can be used for a variety of geometry applications including
deformable modeling, which is the interactive sculpting of smooth
and fair curves and surfaces, automated surface-to-edge gap healing,
shape approximation, and 3d space warping also known as global
deformations, to name just a few.
The core function of the package is to find a
shape, represented by a parametric-function, that minimizes an
associated functional. A functional is an integral equation
of the shape that evaluates to a scalar value.
Every different possible variation of a shape evaluates to a
different scalar value. VSLib’s
optimization engine finds the one shape out of all possible shapes
that minimizes the value of the associated functional.
In VSLib, shapes are not designed
directly, instead they
are designed indirectly. The
direct method of shape design consists of manipulating the values of
a function directly to modify its shape into something desired.
In the world of BSplines, the direct method consists of
editing the control point positions, the weight values, and the knot
vectors of the BSpline representation. When
working with a direct method, the choice of shape representation is
very important. The
values in the representation must represent something an end-user
can understand so that when the value is modified its affect on the
shape can be predicted. This
need partly explains why BSplines have become the standard
representation of choice in the CAGD industry.
Those shapes can be changed by end-users solely by moving
intuitive control-point positions and avoids forcing the end-user to
work with poorly understood properties like twist vector values
which are obscure to just about everybody.
The VSLib indirect method of shape
design consists of manipulating the values of a functional and then
using the VSLib optimization engine to automatically find the
interesting and usually very hard-to-define associated shape.
Each change made to a functional produces a change in the
associated shape. Superficially
these two approaches sound very similar; change a value and see a
However, the indirect method has several
significant advantages over the direct approach. The terms in the
functional can be designed to represent very intuitive parameters of
the shape. For example
it’s possible to build into the functional terms for smoothing a
shape, terms for specifying the shape’s position at one or more
points within the shape, and even terms for specify the shape’s
tangent and curvature properties at a set of points within the
shape. The terms within the functional can act independently of one
another. So an end-user
can say things like, “interpolate this point here and then
interpolate this tangent direction over there and so on while being
smooth and fair.” Building
shapes that satisfy these kinds of design goals using the direct
method is very difficult for an end-user to achieve.
Additionally, it turns out that the terms of
the functional do not depend on the representation of the shape.
In the indirect method, shape representations do not have to
be selected based on the intuitiveness of their values to an
end-user. The choice of
shape representation can now be made for other considerations if
conversely, the indirect method of VSLib shape design can be applied
to almost any shape representation type.
It is possible to have deformable BSplines, deformable NURBs,
deformable Hermite polynomials, deformable Lagrange polynomials,
deformable serendipity functions, etc.
And probably the most important advantage of
the indirect method over the direct method is that the terms of the
functional contain relatively few values.
That means an end-user using the indirect method can design
shapes by modifying a much smaller set of values with much more
intuitive meaning than when using the direct method.
For example, consider a 6x6 BSpline control
point surface that currently interpolates a set of edges along its
trimmed boundaries and looks fairly smooth.
The design goal is to modify the shape to interpolate a point
position near the center of the surface without loosing the
shape’s current smoothness or character and without losing the
curve interpolations along the edges.
This condition might come up when designing a hood of a car
body after someone determines that the height of the hood needs to
be increased by a small amount to accommodate the size of the
car’s engine. In the
direct method, the end-user will have to repeatedly reposition all
36 control points until an acceptable new shape is found, a process
much too difficult to contemplate.
The end-user would be better off looking for some other
construction method to do the job.
In the indirect method, the first step is to define a
functional that contains terms that preserve the shape’s current
trim curve shapes, its smoothness, its current shape, and the
ability to constrain the position of the point on the surface which
will be made to interpolate the target point.
Then the end-user need only modify the location of the
constraint point within the functional so that the constraint
interpolates the desired location.
Now that the functional has been modified, a call to the
VSLib optimization engine will find the new locations for all 36
control points to deform the surface as desired.
In the direct method, the user would have to modify a mesh of
36 control points by hand repeatedly.
In the indirect method, to achieve the same goal, the user
need only modify one point position once.
In real car body design the number of control points used in
the shape runs into the thousands.
And yet, when using the VSLib indirect method of design,
still only one point position would have be moved to change the
overall shape of the hood.
The tricky part for people who are new to them
is in understanding functionals.
So the purpose of VSLib is to give application builders a set
of easy to use tools that can be exposed to end-users to build,
manipulate, and solve functionals at run-time without ever having to
depend on the end-user to either know about or understand
functionals. A typical
application interface to the indirect method of shape design will
consist of things like adding a point-constraint to a shape and then
tracking that point-constraint’s position and watching how the
shape changes each time the point-constraint’s position is
modified. No mention of
functionals ever need be made to end-users.
An overview understanding of functionals is of
importance to application builders and so these are discussed in
some depth in the following sections using an energy metaphor which
lets people who are new to functionals think about shape design as a
thing which mimics the behavior of physical systems.
In the language of the energy metaphor: curves, surfaces, and
volumes can be pulled, twisted, and bent just like a soap bubbles,
pieces of rubber, or pieces of metal.
But first we introduce some needed background information.
Spaces, Points, and Maps
In VSLib, shapes are represented by
multi-variable continuous parametric functions called maps.
A map is called a “map” because it maps points from a
domain space to an image space as,
ImagePoint = Map(DomainPoint) ;
Point locations in VSLib are represented by
Cartesian coordinates. A
point in 1d space has 1 coordinate; a point in 2d space has 2
coordinates and so on. In
VSLib we commonly name the coordinates of 1d, 2d, and 3d points as,
1d Point = [s] or [u],
2d Point = [u, v], and
3d Point = [x y z] or [u, v, w].
The coordinates of any dimensional points can
also just be referred to by their index value.
Nd Point = [u] =
[u0 u1 u2 . . .]
VSLib uses maps with a 1d domain space to
represent the shape of curves.
Similarly, maps with 2d and 3d domain spaces are used to
represent the shapes of surfaces and volumes respectively. But
representing shapes are not the only thing for which maps can be
used. Maps are a
mathematical idea, not just a geometry idea.
For example a map from a 1d domain space to a 3d image space
is very useful for representing a curve but a 1d space to 3d space
map can also be useful for representing the variations of a
3-coordinate red-green-blue color along the length of that very same
curve. VSLib works with
maps. It’s the applications of VSLib that have to decide what
those maps represent. So
in VSLib there are no curve, surface, or volume objects, just maps
with 1d, 2d, or 3d domain spaces.
The size of a map’s image space is
independent of its domain space size. VSLib supports all image space
sizes, but the package is initially compiled to only support 1d, 2d,
or 3d domain spaces so that it can handle the 9 most frequently used
maps which are those that map points from a 1d, 2d, or 3d domain
space to a 1d, 2d, or 3d image space.
The reason for the limitation on domain space sizes is that
the package is implemented using C++ templates and one of the
consequences of that design choice is that the source files have to
explicitly enumerate the range of sizes to be used for domain
spaces. Extending the
initial range of 1d, 2d, and 3d domain spaces to include any other
desired domain space size is a straightforward exercise.
Anyone with access to the VSLib source files can support any
sized domain space.
A functional is an integral of a map expression
that evaluates to a scalar value.
A map expression is any mathematical expression of a map and
Where W = W(u),
the shape represented as a parametric function,
is the value of the functional, also called the “Energy” of the
F is the map
expression sometimes called the Lagrangian, and
the integral is taken over the defined domain of W.
When minimizing the functional, the unknown is
the shape W.
The optimization engine, finds the one shape, W*,
out of all possible shapes that minimizes the value of E.
The main idea of VSLib is to make the building
and modification of functionals easy to do for both
application-designers and end-users so that it becomes simple to
design interesting shapes with desired properties.
VSLib does this by supplying a pre-defined set of functional
terms to be instanced and added to functionals at run-time.
These functional terms each have an easily understood affect
on the shape and a few simple parameters that are easy to modify to
vary that shape in meaningful ways at run-time.
Also these terms can be assembled in an independent order
into a single functional with minimal restrictions.
Once the functional is assembled the associated minimizing
shape can be found with a single call to a solve operation.
The functional terms supported by VSLib
Stiffness Terms that smooth shapes,
that force the shape to interpolate any combination of differential
properties at one or more points within the shape,
that force a surface or volume shape to interpolate any combination
of position, cross-tangent, and cross-curvature constraints along
the length of a curve embedded within the shape.
Point Loads that
deform shapes in predictable manners by applying a force and/or
torque on the shape at one or more points within the shape.
Curve Loads that
deform shapes in predictable manners by applying forces and torques
distributed along the length of a curve embedded within the shape.
Body Loads that
deform shapes in predictable manners by applying forces and torques
distributed throughout the entire shape,
which add mass and damping to the shape behavior so that each call
to solve is actually a single small step in time, so that a sequence
of solve steps can simulate the motion of physical systems.
VSLib Intended Use
The overall sequence of working with VSLib to
define a shape is the following:
Define a shape, for example a BSpline curve, surface, or
Construct an empty Functional for that Shape.
Add a set of terms to the functional that will force the
shape to do what the end-user wants.
Set the parameter values for each of the terms in the
parameters all have default values which can be used.
Find the shape that minimizes the functional with a call to a
Display and review the found shape.
If desired – add or remove terms from the functional.
If desired - modify term parameter values.
Go back to Step 5 and iterate until an acceptable shape is
All of the VSLib functional terms are limited
to being quadratic expressions of the map’s displacements.
There are three principle reasons for this.
Most importantly, most of the shape design behaviors we can
envision can be encapsulated within quadratic forms.
Secondly, a map evaluates to a multi-dimensional vector and
the dot product, which is a quadratic term, multiplies two vectors
together to make a single scalar value and is about the simplest
term one can include in a functional to generate scalar values from
vector functions. Finally,
quadratic functionals can be shown to have just one global minimum.
This property can be taken advantage of when building the
numerical methods that find the optimal shape for any given
functional making it possible to build a numerical package that runs
stably and quickly.
The following is a description of the various
behaviors and functional terms supported within VSLib.
Every shape is assigned a zero energy
configuration called the default shape.
All variations from this configuration increase the energy of
the shape. A functional
that uses only an internal stiffness term and applies no loads or
constraints to an object will always be associated with a minimal
shape, which is this default shape.
Default shapes are introduced into the functional by
introducing a 2nd function, P(u)
– the default shape, and writing the function in terms of
rather than positions as:
Where u = [u0]
for curves, [u0 u1] for surfaces, and [u0
u1 u2] for volumes
In VSLib, the default shape feature can be
turned on and off. When
default shapes are off, the behavior of the system is the same as if
the default shape was equal to zero, that is as if the default shape
were squeezed down to a single point located at the origin.
When default shapes are turned on, the end-user
can design shapes, which are either small or large variations from
an initial starting shape.
Energy Stiffness Te
We choose to define the internal energy of a
shape as a combination of
weighted resistance to stretch term,
weighted resistance to bending term,
weighted resistance to displacement term, and
weighted resistance to changes in 2nd order terms
These stiffness terms within the functional
increase energy whenever the shape is modified from its default
shape. The resistance
to stretch term acts similarly to an area minimizing term.
This prevents a shape from folding like a shower curtain
whenever it has the chance to move its boundaries closer together.
The resistance to bending term forces the shape to distribute
bends over large areas. This
helps make smooth shapes that gracefully change their direction
rather than shapes that contain a series of sharp bends and turns
separated by flat sections. Increasing
or decreasing the a
terms change how the shape trades off stretching and bending to
minimize the energy of its minimal shape.
weighted resistance to displacement term acts like a body spring
that connects every point in the shape to its default position.
This term is very effective in helping the shape to localize
a change to one small section rather than distributing the change
over a large area to maintain smoothness.
Increasing the d
term is like increasing the stiffness of the body spring.
weighted resistance-to-changes-in-2nd-order term acts to
smooth out changes in curvature.
The idea of this term is to give a handle to the user to add
additional smoothing affects to a shape being designed.
However, the effectiveness of this feature is limited by
numerical tolerances and at this time is considered an experimental
An equation can be added to the functional to
enforce a constraint at a point on the shape. Slight variations to
the equation allow any of the differential properties of the shape
based on its position and derivatives at that point to be controlled
as well. Each
differential property controlled at that point adds one term to the
functional can contain any number of point terms and the point terms
can be located anywhere on the shape.
The only limitation is that if more point constraints are
added to a part of the shape than there are degrees of freedom in
that neighborhood, then the constraints cannot be exactly enforced.
The equations for loads and constraints happen
to be the same. The
difference between the two is that loads are implemented with
penalty methods that only approximate the condition to within a
tolerance while constraints are implemented with Lagrangian
constraints and are enforced exactly.
The easiest way to see the difference between the two is to
consider a set of point position terms applied to a shape.
When the point terms are treated as constraints the shape
will be deformed to interpolate those point positions exactly.
When the point terms are treated as loads, the shape will
only be forced to come near the target point locations.
The advantage of constraints is that the target point
locations will be exactly interpolated.
The problem with constraints is that a shape that is forced
to interpolate a large number of points will have to give up some of
its ability to be smooth and fair to achieve the job.
When the same set of point terms can be enforced as loads the
resulting shape will be much smoother but will only come near the
target point set. In a
typical design situation of some combination of point constraints
and point loads will probably be required.
Point terms can be tracked.
That is after they are turned on for a shape, the target
point values can be modified and a new deformed shape can be found
that satisfies the moved target point value.
Point terms exist to set all of the
differential properties of a shape at a point.
These include the following.
Tangent in up to 2 independent directions
Curvature in up to 2 independent directions
Tangent in up to 3 independent directions
Curvature in up to 3 independent directions
The following table shows the actual
constraints that are used to enforce the list of above properties.
The nice thing about point terms is that they act
independently so that a single point any combination of constraints
can be enforced. For
example an end-user may choose to constraint a point’s position or
its tangent or both. Additionally,
the method allows any number of point constraints to be applied to a
shape with no restriction on the location of the constraint.
Other common constraint strategies often require a certain
kind of representation for each constraint.
For example, many BSpline through point constraints are
implemented by inserting a fully multiple knot at the location to be
constrained and then assigning the associated control-point a
location. This approach
adds a lot of control points to a shape just to insert a point
position constraint and can’t really be extended to handle tangent
or curvature constraints.
Surface and volume shapes can have multiple
tangent and curvature constraints per point each operating in a
unique direction. The
tangent and curvature constraints in a surface or volume apply to an
imaginary curve running through the constrained point.
The direction of the curve is specified by a domain space
direction. A constraint
can be supported for any independent sets of domain directions.
So, surfaces can have 1 or 2 tangent or curvature constraints
at a point, and volumes can have 1, 2, or 3 such constraints at each
point. The domain space
directions do not have to be aligned with the u, v, and w iso
parameter directions. They
may point in any direction as long as they are independent of one
Multiple curvature constraints can be used to
design a surface with a saddle point using a single point term.
Define two independent directions within the surface and set
a curvature constraint in one direction curving up and in the other
direction curving down. The
constraint lets the end user set the direction of the osculating
plane, the tangent directions, and the magnitudes of the curvature
so that the shape, orientation, and position of the saddle can all
be controlled from the values of a single term added to the
surface’s energy functional.
There is one caveat for curve constraints.
Due to the numerical method used to find shapes that minimize
these equations, VSLib is limited to linear constraint equations.
But it can have any number of constraint equations working on
a single point. To get
a curvature constraint, VSLib actually implements a set of linear
constraints that simultaneous constrain the curvature, a tangent
direction, and the orientation of the osculating plane. So curvature
is really a coupled constraint; constrain curvature and a tangent
direction and the surface normal get constrained as well.
For those interested in the details the
following table is provided to show all the point constraint
equations and terms that are added to the shape’s functional.
Only the surface and volume curvature constraints are not
shown, but they look just like the curve curvature constraint except
that each point may have one set of such constraints for each
independent domain direction.
Table of Point Constraint Equations and related Penalty and
’(u*) = t
= 0, and
= 0, and
= 0, and
’(u*) = t,
= 0, and
’(u*) – t)
) 2 +
’(u*) – t)
Where u* = a
domain space point location
= a domain space direction vector
= an image space target point location
= an image space target tangent vector
= an image space target curve normal vector
= an image space target curve binormal vector
= an image space target surface normal vector
= an image space target curvature value
Gain = the stiffness of a penalty enforced constraint,
= the map being constrained.
A set of equations can be added to a functional
to enforce a single curve load or curve constraint on higher
dimension maps like surfaces and volumes.
These curve terms can be used to control the shape’s
position, cross-tangent, or cross-curvature shapes across those
curves. There can be
any number of curve terms on a shape and the shape of those curves
is not restricted. In the world of BSplines that means that curve
constraints can be any mix of iso-parameter and trim curves.
Curve loads and constraints can always be
fixed. In other words,
given an initial shape a curve term can be added that will always be
satisfied as other terms are modified to force the shape to change.
Arbitrary curve terms cannot be tracked like point terms.
This limitation comes from the representation choice of the
shape and not from the math of functionals and optimizations.
So for BSplines, it turns out that iso-parameter curve
constraints can be tracked arbitrarily and trim curves can be
tracked for some special cases.
Understanding when a curve term can be and can’t be tracked
depends on understanding the relationship between the optimization
of functionals and the representation of shape that is beyond the
scope of this overview document.
Unless the application depends on the feature, exposing
general tracked curve constraints to end-users is not recommended,
whereas fixed curve constraints are.
When working with Bsplines, one should consider exposing
tracked iso-parameter curve constraints.
The system can support a variety of body loads
that extend the range of tools that a user can use to change a
shape. These can all be
made to mimic existing physical phenomena to make them easy to apply
for end-users. The list
of body terms includes the following and can be easily extended.
Gravity – have a shape sag in a given gravity
direction, held up by its constraints.
Increase gravity to increase the amount of sag.
Pressure – have a shape bulge outward or inward
depending on whether the pressure is positive or negative. Increase
pressure to increase the amount of bulging.
Attractors – add points in space that attract nearby
shapes and ignore distant shapes.
Change the gain on the attractor to increase or decrease the
Repulsors – add points in space that repel nearby
shapes. Change this
gain to increase or decrease the affect.
The interface to VSLib is built in three
cascading layers: a C++ low-level interface, a API function based
mid-level interface, and an application high-level interface.
The lowest level of the VSLib interface
consists of all the C++ classes, methods, and members used to
implement the library. Working
at this level of the library requires the programmer to be familiar
with all the VSLib implementation choices.
It is assumed that library developers will work at this
level, i.e. those people working for SMS or those customers that
would like to extend the capabilities of the library on their own.
The 2nd layer of the interface is
comprised of a set of API functions that are gathered together in
The purpose of this API is to allow
application-builders to integrate the general VSLib capabilities
into their applications as described in this document without having
to be familiar with the implementation choices made within the
library. These API
functions allow a program to construct functionals for given shapes,
add and remove terms to those functionals, and solve for the
associated minimal. It
is expected that applications that expose deformable modeling,
morphing, global deformations or space warp to their end-users will
embed these functional API calls within their interface.
The 3rd layer of the interface
consists of a set of pre-constructed applications of the VSLib
design method exposed through a small set of function calls all
contained under the “VSLib/VSApp” directory set.
These applications use the library to execute a particular
modeling function so that all of VSLib can be treated as a black box
allowing an application to offer a VSLib enabled modeling function
without having to figure out how to implement those functions using
low-level VSLib calls. To
date the pre-constructed list of applications include:
Curve, Surface, and Volume Approximation.
Take an existing shape and find a similar smoother equivalent
shape that interpolates the old shape’s boundary position.
This function is very good for improving the quality of a
shape and its representation. This
function can remove representational defects, like dog-legs, hooks,
internal cusps, and over-sampling.
This function can improve a shape by making it smoother and
G1/G2 gap healing.
Modify an existing surface to deform it a minimal amount to
reduce the maximum size of a gap between the surface and an edge or
a curve on a neighboring surface to a specified amount.
Surfaces can be made either G1 or G2 continuous with a