VSLib Introduction

Introduction

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 new shape. 

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 desired.  And 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.

Functionals

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 its derivatives. 

            Where W = W(u), the shape represented as a parametric function,

E is the value of the functional, also called the “Energy” of the system,

                        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 include: 

1.      Internal Energy Stiffness Terms that smooth shapes,

2.      Point Constraints that force the shape to interpolate any combination of differential properties at one or more points within the shape,

3.      Curve Constraints 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.

4.      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.

5.      Curve Loads that deform shapes in predictable manners by applying forces and torques distributed along the length of a curve embedded within the shape.

6.      Body Loads that deform shapes in predictable manners by applying forces and torques distributed throughout the entire shape,

7.      Dynamic Loads 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:

1.      Define a shape, for example a BSpline curve, surface, or volume.

2.      Construct an empty Functional for that Shape.

3.      Add a set of terms to the functional that will force the shape to do what the end-user wants.

4.      Set the parameter values for each of the terms in the functional.  These parameters all have default values which can be used.

5.      Find the shape that minimizes the functional with a call to a solver operator.

6.      Display and review the found shape.

7.      If desired – add or remove terms from the functional.

8.      If desired - modify term parameter values.

9.      Go back to Step 5 and iterate until an acceptable shape is designed.

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.

·        Default Shapes

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 displacements, Q(u) rather than positions as:

            Q(u) = W(u)  - P(u)

            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. 

·        The Internal Energy Stiffness Te

We choose to define the internal energy of a shape as a combination of

1.      an a weighted resistance to stretch term,

2.      a b weighted resistance to bending term,

3.      a d weighted resistance to displacement term, and

4.      a g 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 and b terms change how the shape trades off stretching and bending to minimize the energy of its minimal shape. 

The d 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.

The g 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 feature.

·        Point Loads and Constraints

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.  A 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.

1.      Curve

a.       Position

b.      Tangent

c.       Curvature

d.      Binormal direction

e.       Normal direction

2.      Surface

a.       Position

b.      Tangent in up to 2 independent directions

c.       Curvature in up to 2 independent directions

d.      Surface Normal

3.      Volume

a.       Position

b.      Tangent in up to 3 independent directions

c.       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 another. 

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 Lagrangian energies

 

Property

Constraint(s)

Penalty Energy

Lagrangian Energy

Position

W(u*) = p

Gainpos(W(u*)-p)2

-li(W(u*)-p)

TangentCurve

W ’(u*) = t

Gaintan(W ’(u*)-t)2

-li(W ’(u*)-t)

TangentSurf-or-Vol j

dj . ÑW = t

Gaintan(dj . ÑW - t)2

-li(dj . ÑW - t)

NormalCurve 2d

m.W(u*) = 0

Gainpos(m.W(u*))2

-li(m.W(u*))

NormalCurve Nd

(Wu´m).Wuu = 0, and

(Wu´m).Wu = 0

Gaintan((Wu´m).Wuu)2 +

Gaintan((Wu´m).Wu) 2

-li((Wu´m).Wuu)2 +

-li+1((Wu´m).Wu)2

Binormal

b.Wu = 0, and

b.Wuu = 0

Gaintan(b.Wu)2 +

Gaintan(b.Wuu)2

-li(b.Wu)2) +

-li+1(b.Wuu)2)

Surface Normal

n.Wu = 0, and

n.Wv = 0

Gaintan(n.Wu)2 +

Gaintan(n.Wv)2

-li(n.Wu)2) +

-li+1(n.Wv)2)

CurvatureCurve

W ’(u*) = t, and

(Wu´m).Wuu = 0, and

(Wuu-km).Perp1(Wu) = 0

(Wuu-km).Perp1(Wu) = 0

Gaincur *

((W ’(u*) – t) 2 +

((Wu´m).Wuu) 2 +

((Wuu-km).Perp1(Wu) ) 2 +

((Wuu-km).Perp1(Wu) ) 2)

-li((W ’(u*) – t) 2

-li+1((Wu´m).Wuu) 2

-li+2((Wuu-km).Perp1(Wu) ) 2

-li+3((Wuu-km).Perp1(Wu) ) 2

 

            Where u* = a domain space point location

                        di  = a domain space direction vector

                        p  = an image space target point location

                        t   = an image space target tangent vector

                        m  = an image space target curve normal vector

                        b   = an image space target curve binormal vector

                        n   = an image space target surface normal vector

                        k   = an image space target curvature value

                        Gain = the stiffness of a penalty enforced constraint,

                        W  = the map being constrained.


·        Curve Loads and Constraints

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.

·        Body Loads

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. 

1.      Gravity – have a shape sag in a given gravity direction, held up by its constraints.  Increase gravity to increase the amount of sag.

2.      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.

3.      Attractors – add points in space that attract nearby shapes and ignore distant shapes.  Change the gain on the attractor to increase or decrease the affect

4.      Repulsors – add points in space that repel nearby shapes.  Change this gain to increase or decrease the affect.

VSLib Interface 

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.

·        VSLib C++ 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.

·        VSLib API interface

The 2nd layer of the interface is comprised of a set of API functions that are gathered together in the files,“VSLib/VSQmin/src/VsQMinAPI.h,”  and   “VSLib/VSMap/src/VsMapAPI.h.” 

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.

·        VSLib Application 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:

1.      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 fairer.

2.      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 neighboring surface.

   


Legal Stuff

All of the software and documentation received with this release is copyrighted by Solid Modeling Solutions, Inc. You may not distribute source code or documentation for this software outside of the company and the site which owns the license. The standard license agreement allows you to freely distribute object code in any application which does not contain a programmatic interface. All software and documentation is considered proprietary information and the intellectual property of Solid Modeling Solutions, Inc. This document contains trade secret information which is deemed proprietary.

Copyright © 1998-2010 Solid Modeling Solutions All rights reserved.
Information in this document is subject to change without notice.