Volume-Preserving Free-Form Solids.
AbstractSome important trends in geometric modeling are the reliance on solid models rather than surface-based models and the enhancement of the expressive power of models, by using free-form objects in addition to the usual geometric primitives and by incorporating physical principles. An additional trend is the emphasis on interactive performance. In this paper we integrate all of these requirements in a single geometric primitive by endowing the tri-variate tensor product free-form solid with several important physical properties, including volume and internal deformation energy. Volume preservation is of benefit in several application areas of geometric modeling, including computer animation, industrial design and mechanical engineering. However, previous physics-based methods, which usually have used some forms of "energy," have neglected the issue of volume (or area) preservation. We present a novel method for modeling an object composed of several tensor-product solids while preserving the desired volume of each primitive and ensuring high-order continuity constraints between the primitives. The method utilizes the Uzawa algorithm for non-linear optimization, with objective functions based on deformation energy or least squares. We show how the algorithm can be used in an interactive environment by relaxing exactness requirements while the user interactively manipulates free-form solid primitives. On current workstations, the algorithm runs in real-time for tri-quadratic volumes and close to real-time for tri-cubic volumes.
Introduction
Modern geometric modeling emphasizes solid
models rather than surface-based models, usage
of free-form objects in addition to the usual geometric
primitives, incorporation of physical prin-
ciples, and interactive performance. In this paper
we integrate these four issues in a single setting
by endowing the tri-variate tensor product B'ezier
free-form solid with physical properties.
1.1 Background
The common approach to representing and manipulating
free-form objects is by using a boundary
representation (Brep), with parametric surfaces
for the boundary. Adjacencies between
neighboring surface patches are stored explicitly.
Using a Brep, it is inherently difficult to model
physical attributes associated with the object.
Such attributes are easier to consider when using
parametric free-form solids instead of surfaces.
The difference between the two is the dimension
of the parameter space (two for surfaces and three
for solids.)
Some previous systems have used free-form
solids (e.g. [Farouki85].) However, parametric volumes
are usually not used in the way that surfaces
are used, for direct object design, but rather for
design of separate deformation entities used for
modification of existing objects. This can be explained
by the fact that if only the boundary of
the object is of interest, there is no need to use
free-form solids, which enable control over what
happens 'inside' the object.
Free-form deformations (FFD) were introduced
in [Sederberg86] as a technique for defining a
smooth deformation on a space including the objects
embedded within that space, regardless of
their geometric representation. FFD utilizes a
tri-variate tensor-product parametric B'ezier solid
defined by a lattice of control points. The defining
parameter space is the unit cube. To deform
an object point, its local coordinates inside
the unit cube are computed. Then the image of
the point under the deformation is computed using
the B'ezier control points and basis functions.
Naturally, other basis functions (such as NURBS)
could be used as well [Griessmair89].
suggested a user interface based on
control point manipulation, with which is it rather
difficult and tedious to obtain a desired defor-
mation. Direct manipulation of object points instead
of control point manipulation was suggested
in [Borrel91, Hsu92]. The user directly moves
an object point, and the system automatically
computes the control point configuration yielding
the desired point displacement constraints. [Rap-
poport94] extends this method to approximate
('probabilistic') point constraints with a non-isotropic
shape parameter. [Joy91] gave methods
to manipulate a group of control points in
a single operation. A more general type of extension
to FFD was presented in [Coquillart91], who
defined an arbitrary volume and used numerical
routines to compute local coordinates within this
volume. Neither of the above methods attaches
any physical meaning of the deformation. Simple
constrained deformations were described in [Bor-
rel94].
Physics-based modeling is a successful research
area in geometric modeling. Several papers
[Terzopoulos94, Welch92, Kallay93, Moreton92,
Celniker91, Greiner93] presented surface design
schemes based on minimization of an energy functional
subject to linear point constraints such as
location and tangent vectors. We are not aware of
any work using similar ideas for free-form solids.
Other applications of physics-based modeling are
in reconstruction and tracking [Fang92], motion
control [Shapiro88], and modeling of flexible and
rigid objects [Barzel88].
The only relevant reference we are aware of for
volume preservation 1 is [Aumann92], which gives
an algorithm that approximates a surface of revolution
by a surface which is not a surface of revolution
while trying to preserve the original volume.
Free-form solids are not discussed, and it seems
that the algorithm is not suited for them at all.
for computing the area or volume en-
refers to an unpublished report about
volume preserving deformations, but such deformations
cannot be everywhere locally satisfied with polynomial
fields except for the simple case of pure shears.
closed by curves and surface patches were given
in [Elber94, Liu87].
1.2 Proposed Approach
We use free-form solids as design primitives. In
the context of solid model design in general and
specifically of free-form solids, one of the most basic
physical properties of a space cell is its volume
size. A major drawback of current user interaction
techniques when applied to free-form solid
design is that the user has no way of controlling
the contained volume size. Currently, solid design
(as opposed to using volumes for free-form
deformations) is not much more than design of
the surfaces bounding the volume, each of them
independently.
We present a novel method for modeling an
object composed of several tensor-product solids
while preserving the desired volume of each primitive
and ensuring high-order continuity constraints
(and any linear constraints in the control
points) between the primitives. The method
utilizes the Uzawa algorithm for non-linear opti-
mization, with an objective function based on deformation
energy or least squares (LSQ).
The algorithm is very useful for several appli-
cations. For example, hierarchical FFDs were
used by [Chadwick89] for computer animation of
muscles. A similar effect could be achieved by
a combination of point displacement constraints
and smooth modification of desired volume size.
The algorithm is useful in industrial design, where
basic functional requirements are automatically
obeyed without imposing limitation on the creativity
of the designer. When the object material
is known, volume preservation means weight
preservation, hence is attractive for mechanical
engineering applications when the engineer designs
a part or an assembly. The preservation of
volume of each element of the objects enables us
to keep required proportions between volumes and
weights of object parts. Obviously, simple scaling
of the object in order to achieve a desired volume
is not possible, due to the presence of point location
and continuity constraints.
Our algorithm uses B'ezier solids of arbitrary
orders as the underlying mathematical definition
of a free-form solid primitive. A B'ezier solid of
known orders is completely specified by its control
points. The input to our algorithm consists
of a desired object form (a set of primitives defined
by their control points configurations), desired
primitives volume sizes and a set of linear
constraints on the control points implied by continuity
requirements between the primitives or imposed
directly by the user. The control points configurations
can either be given directly by the user
through control point manipulation, or computed
from point displacement constraints specified by
direct solid manipulation as in [Borrel91, Hsu92].
The algorithm computes a control point configuration
closest to the given one (in a deformation
energy minimization or least square sense) such
that the deformed primitives contain volume of
the given sizes and obeying the linear constraints.
The algorithm does not automatically guarantee
that the boundaries do not self-intersect.
Note that it is the global volume of a given free-form
cell that is being preserved, not the volume
of an object embedded within the cell or of local
sub-cells. This approach was introduced in
the finite element method for rubber type ma-
terials, but here we avoid the complexity of the
penalty approach [Bercovier81] and use a duality
argument to deal with the constraint, based on
the Uzawa algorithm for non-linear programming
[Arrow58, Ciarlet88].
Special measures were taken in order to endow
the algorithm with real-time performance on current
workstations. We utilize the fact that the
volume size actually depends only on the boundary
surfaces of the deformed primitive, hence volume
size computation can be done with a subset
of the control points. The inside points are of no
interest to the user as well for the object's geome-
try, but are required for physical computations on
the object, such as tear strength or deformation
energy. The inside control points are computed
from the outside points using a 3-D variant of the
Coons surface formula when energy computation
is required. This does not prevent them in general
from crossing the parametric boundary, but intersection
is not caused for most modeled objects.
In an interactive setting, the algorithm relaxes
its accuracy requirements during object manipu-
lation, computing an accurate solution only when
real-time performance is no longer essential. This
technique gives the user a feeling that volume is
preserved during interaction.
Although in this work we limit the method description
to B'ezier solids, it can easily be adopted
for most of the other common definitions of free-form
solids, for example NURBS. The only restriction
on the mathematical definition of the solid
that we have is that it should be a defined as a
linear combination of the control points.
The paper is organized as follows. Section 2
gives necessary mathematical notations. Section 3
formalizes the mathematical problem involved.
Section 4 explains in detail how to compute the
size of the volume enclosed by a tensor product
B'ezier solid and the partial derivatives of the volume
size function. Section 5 explains how to represent
continuity constraints. Section 6 explains
how to compute the energy required for a change
of a tensor product B'ezier solid from one control
point configuration to another, and the energy
derivative. Section 7 presents the numerical algorithm
used to solve the mathematical problem,
and Section 8 describes our implementation and
results.
Notations
We introduce here the formal mathematical notations
used during the rest of the work. A tensor
product B'ezier solid is defined using a set of control
points P ijk 2 R 3 . The image of a parametric
point (u; v; w) in the unit cube is
nw
i (t) is the Bernstein polynomial defined
by
Denote the x; z coordinates of a control point
by P x
ijk respectively. Denote the volume
of the solid primitive defined by a set P
of control points by V olume(P ); and denote by
@V olume(P )=@P the vector whose components
are the partial derivatives
abc
abc
@P z
abc
for every triplet abc
Denote the energy of a transformation from a
B'ezier solid defined by a configuration Q of control
points to one defined by configuration P of
control points by Energy(P \Gamma Q); and denote by
Q)=@P the vector whose components
are the partial derivatives
abc
abc
@P z
abc
Denote by -
P the column vector of all the control
points from all the B'ezier solids in the system,
3 Problem Statement
The general problem we handle is finding a control
point configuration that satisfies the constraints
(linear and volume) and which results in an object
as close as possible to the given one. The change
of an object can be represented in two ways. The
simpler is as the sum of squares of distances between
the original control point positions and the
new ones. The second is as the energy required
to get from the original object to the new one. In
this section we formalize this problem as a set of
mathematicalrequirements that the target control
points configuration should satisfy.
We denote by Dist(P; Q) the distance between
two objects resulting from control points locations
P and Q, which can stand for:
using an energy approach

using a LSQ approach

In case objects are modeled directly, the original
objects are usually close to the desired final ones,
in which case the the distance measure should be
LSQ since we want the resulting object control
points to be close to the original ones so that the
shape of the object will incur a minimal change.
With physics-based modeling, we use as the
original object the element in an initial state and
we deform it by applying linear constraints and
minimizing the energy. The resulting object then
simulates the behavior of an elastic material with
internal pressure. Initial control point configurations
and the specification of constraints can be
obtained by any method, including direct control
point manipulation and direct manipulation
of points and vectors inside or on the object.
The resulting constrained minimization problem
(M) is: given a control point configuration
(each Q i representing a single trivariate
primitive), a set of corresponding volume
Vn and a matrix C representing linear
constraints on the control points, find a new
control point configuration
that the following holds:
ffl P is the solution of min P 0
ffl For each i, V olume(P
The desired volumes V i could be the initial volume
sizes or any other number. For example,
smooth variation of the desired volumes can be
used for dilating the object during animations.
4 The Volume Function
Our volume preservation algorithm requires the
computations of V olume(P ) and of @V olume(P )
@P .
Below we show how to analytically compute the
exact volume size of a tensor product B'ezier solid.
We show that the computation of the volume size
can be represented as a scalar product of two vec-
tors: one whose components are the multiplication
of the coordinates of the solid's control points, and
a second one whose components are based on the
B'ezier basis functions and therefore can be computed
off-line just once for each combination of
orders of basis functions.
4.1 Computing the Volume
The size of the volume specified by a three-dimensional
function F (u; v; w) defined over the
unit cube is
Z 1Z 1Z 1JF dudvdw
where JF is the determinant of the Jacobian matrix
In our case F is given by Equation 1. For exam-
ple, the entry in the first row and column of the
Jacobian matrix is
d
du
The derivative of a Bernstein polynomial of order
n can be expressed by the scaled difference of two
Bernstein polynomials of order
d
du
with the convention that B a
0, or b ? a. Denote
-
du
and similarly -
v ijk and -
w ijk . The determinant JF
can be written as:
det@
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
expanding, we obtain:
ijk
-
ijk
ijk
ijk
ijk
ijk
ijk
-
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
-
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
ijk
Since the determinant is a multylinear operator
and due to the structure of the summations, we
can write:
ijk
lmn
lmn P z
ijklmnopq be a new index notation, in the
Denote the determinant in
Equation 4 by det I (u; v; w), and denote
Z 1Z 1Z 1det I (u; v; w)dudvdw:
Since the integral is a linear operator, the volume
can be written as:
ijk
lmn
I P x
lmn P z
Let p be a column vector indexed by I containing
all terms of the form P x
lmn P z
opq , and let c be a
column vector of the same size whose components
are the c I 's. Then Equation 5 can be expressed
as the scalar product of p and c:
The vector c depends only on the orders of the
B'ezier basis functions, hence can be computed
once and for all for every practical order combination
(the number of all practically useful order
combinations is small.) Computing the elements
of c via symbolic integration is very complicated
even for relatively small B'ezier orders, therefore
we compute them using Gauss numerical integration
[Press88], which gives an exact result since
the integrated functions are polynomials. A component
c I is computed as
r
s
are the Gauss weights corresponding
to the points x r in the unit in-
terval. The number of sample points on each dimension
is determined according to the order of
the basis function in that dimension.
The description above was simplified for ease of
explanation. Actually, volume size depends only
on the boundary surfaces (Stokes' formula [Gib-
son44].) In B'ezier volumes the boundary surfaces
are not influenced at all by the 'inner' control
points, which can be completely neglected during
the computation of the volume size. In fact,
when computing the elements of the c vector we
find that for any index ijklmnopq containing co-ordinates
of an inside point the value c ijklnmopq is
zero. In practice, then, to accelerate the volume
computation we let the index I run only on values
of ijklmnopq which define 'outer' control points.
4.2 Computing the Volume Deriva-
tive
The volume preservation algorithm requires the
computation of the
vector @V olume(P )=@P whose components are of
the form @V olume(P )=@P r
abc where r is x; y or z.
For example,
abc
@
ijk
lmn
lmn P z
abc
Since for every ijk 6= abc the partial derivative
vanishes, we get
abc
lmn
lmn P z
5 The Constraints
In this section we explain the different linear constraints
imposed on the control point configuration
required in order to achieve desired geometric
or physical results.
5.1 Continuity Constraints
Continuity constraints between primitives in an
object are essential for any object design. Continuity
of order k (C k ) between two adjacent volumes
defined on [0; 1]
in the u direction is achieved when the following
holds
for every (v
In our case for two adjacent primitives defined
by control points configurations P and Q we will
get
Since the derivative is a linear operator we get@ X
ijk
ijk
and therefore
(1)P ijk
For this to hold for each v
necessary and sufficient condition is that for
(0)Q ijk
thus getting a set of n v nw linear equations in
The derivative of a Bernstein polynomial of order
was given in Equation 2.
l (0) 6= 0
for
l (1) 6= 0 only for
the number of i's for which @ k B nu
and the same holds for
fore, C k continuity conditions between adjacent
B'ezier volumes are expressed as a set of n v nw linear
equations on k layers of control points of
each volume from the adjacent border.
For the most common cases the conditions are:
Another kind of continuity constraint between
elements is geometric continuity, which is more
general than parametric continuity. Geometric
continuity yields non-linear constraints which are
difficult to express and solve, and therefore we do
not use them in this work. For more details on
geometric constraints see [Bercovier93].
5.2 Other Constraints
The following types of constraints can easily be
handled in addition to continuity constraints:
ffl Fixing a point at a given location, resulting
in equations such as P r
i is a constant.
ffl Attaching two points together, resulting in
equations such as P r
ffl Preserving a given distance between points.
5.3

Summary

A general linear equation on variables P i is expressed
as X
or in vector representation as
c 0:
If we denote by C the matrix whose rows are the
coefficients c of the linear equations and by -
P the
column vector of all the control points, the constraints
are achieved when C -
6 The Energy Function
Energy computation for a deformation of a B'ezier
primitive from one control point configuration to
another is required by our algorithm. Here we
show that it can be computed using a matrix
whose elements depend only on the order of B'ezier
basis functions.
6.1 Computing the Energy
The energy of a deformation of a unit cube specified
by a 3-D vector function F usually
[Terzopolus94] described as
Z 1Z 1Z 11(fi
ff
with ff and fi being material property constants.
We can write
Z 1Z 1Z 1' @F i
dudvdw +2 ff
Z 1Z 1Z 1' @F i
dudvdw
Z 1Z 1Z 1' @F j
dudvdw +Z 1Z 1Z 1' @F j
dudvdw
In our case the deformations is of a body defined
by one B'ezier point configuration to a body
defined by another one. Hence the deformation is
defined as a tri-variate B'ezier function with distances
between the control points of the two configurations
serving as its control point lattice. Using
P for these new 'control points', we can write
ijk
-
ijk
and consequently
ijk
lmn
We have
Z 1Z 1Z 1' @F x
Z
ijk
lmn
ijk
lmn
lmn
'Z 1Z 1Z 1-
Let Du be a matrix indexed by ijk and lmn,
defined by
Z 1Z 1Z 1-
and define Dv and Dw similarly. Let Px be a column
vector with components P x
ijk , and similarly
define P y and P z. then we have
Z 1Z 1Z 1' @F x
Denote by Duv the matrix of the mixed derivatives
given by
Z 1Z 1Z 1-
and define Duw and Dvw similarly
Duv T .) We have
Z 1Z 1Z 1' @F y
'' @F x
The elements of the three matrices above can also
be computed numerically. Substituting the matrices
into Equation 7,
Finally, let D be the matrix whose rows are2
Let P be a column vector concatenating
All the elements of D depend only on the orders of
the B'ezier basis functions, hence can be computed
exactly once and for all for every practical order
combination, using Gauss quadrature.
6.2 Computing the Energy Deriva-
tive
To minimize the deformation energy the algorithm
requires the computation of the vector
@Energy(P )=@P whose components are of the
abc where r is x; y or z. It
is easy to see that, for example,
abc
r
lmn
since for every rijk 6= xabc the partial derivative
of Energy(P ) according to P x
abc vanishes.
7 The Uzawa-Based Volume
Preservation Algorithm
In this section we explain in detail the algorithm
we use for solving the problem as defined in Section
3.
7.1 Lagrangian Multiplier Method
To convert the constrained minimization problem
subject to the constraints
an unconstrained min-max problem,
we define a new functional L called the Lagrangian
associated with the problem (M) by
where fl is vector with size the number of linear
constraints. The vector
is called the Lagrange multipliers vector, - i is
called the Lagrange multiplier for the constraint
is called the Lagrange
multiplier for the constraint C j
stands
for row j of C).
As explained in [Ciarlet88], the constrained
minimization problem (M) can be reformulated as
finding a solution to the unconstrained min-max
problem (S) defined by
A necessary condition for a triplet (P; -; fl) to be
a solution of (S) is the vanishing of the partial
derivatives:
@-
which means that for each
(Cj i denotes the columns of C that multiply the
points of P i in -
7.2 Solution Method
The volume derivative expression is non-linear,
hence the usual direct methods (such as LDL T
and Gauss elimination) cannot be used to solve
(S). We use a version of the Uzawa method tailored
to our problem [Ciarlet88]. Uzawa's method
is an iterative method allowing one to solve an
inequality constrained minimization problem by
replacing it with a sequence of unconstrained minimization
problems. Since we do not have inequality
constraints we can use a simpler version.
Given the problem (M) the iteration starts with
an arbitrary values for - 0 2 R n
(we
start with 0 for both), and with an initial value
for P 0 for which we use Q. These initial guesses
are especially suitable in an interactive setting,
where it is expected that Q will not change much
after the constraints are satisfied. A sequence of
triplets
is defined by means of the following iterations:
The algorithm runs until the constraints are satisfied
or the number of iterations exceeds a given
limit.
Pseudo-code for the algorithm is shown on Figure
1. The initial values for and fl are set
in lines 1 and 2. Line 3 computes the current
volumes v i and line 4 initializes the loop counter
k. The main ('outer') loop of the algorithm is
performed in lines 5-10. The loop iterates while
the constraints are not satisfied, stopping after
the limit on the number of iterations has been
reached. In each iteration the system in Equation
8 is solved (line 6) and the current value of -
and fl is updated using the tuning parameters ae 1
and ae 2 respectively (lines 7-8). Line 11 returns P
as the answer.
The choice of tuning parameters ae 1 and ae 2
as used in Equation 10 and Equation 11 is the
most difficult practical issue when using Uzawa's
method. Each type of problem has its own best
range of values for ae i . In our case we found it
best to use ae for an energy distance
function and ae least squares
distance function. In general, the larger the ae's
the faster the convergence becomes, but the risk
of non-convergence due to overstepping the convergence
point increases.
Pseudo-code for one way of solving the inner
problem is shown in Figure 2. The inner problem
is solving Equation 8 for P with the given
and -. It is a non-linear problem; Figure 2
shows how to solve it using successive approximation
on P . We iteratively compute new values
for P based on Equation 8 until the distance
between two successive iterations is small enough
dist ). There are several other
possible techniques for solving a set of non-linear
equations which can be used here as well.
Usually when solving physics-based problems
by Lagrange multipliers methods the additional
variables added as multipliers have physical mean-
ing. In our case one can interpret - as an inner
hydrostatic pressure to keep the volume at a
given value. We are looking for the value of that
pressure: the Uzawa outer step can be seen as
augmenting or diminishing the hydrostatic pressure
until convergence. This tuning is done with
the parameter ae 1 . This observation relates our
method to so-called mixed finite element methods
for the Stokes problem [Hughes87]. In our case
we have constant pressure for each small volume
element.
The algorithm was implemented in C under Unix
using SGI/GL for graphics and Motif for the user
interface. The interface lets the user work with a
number of B'ezier primitives, the order of each selectable
by the user. In the initial state the primitives
are displayed as unit cubes (cubes whose
volume is 1.) Control points on each primitive
can be selected and manipulated in 3-D. We did
not implement direct manipulation of boundary
surface points since it is immaterial to the problem
being tackled. The primitives as whole can
be selected as well and manipulated.
Constraints are inserted via a Motif-based user
interface where the type of the constraint is set
and then through direct point manipulation the
points or surfaces involved are chosen.
There are two methods for object design. In the
first method, volume preservation can be turned
off during interaction and performed only when
arriving at a desired configuration. In the second
method, it can be turned on during the whole interaction
process. The first option is necessary
since for high orders the performance is not fully
interactive.
Due to the complexity of computations in the
interactive stage we cannot satisfy volume and linear
constraints simultaneously, so the user has to
choose which one is preferred.
There are three sets of parameters to the algo-
rithm: parameters that influence volume preservation
during interaction while the user drags the
mouse, parameters that are for solving volume
constraint when leaving the mouse, and parameters
for global computation when solving all the
constraints. Typically, for the interaction mode
the iteration limits are lower and the convergence
tolerances are larger than for the final mode, for
the global computation the tolerances usually do
not increase but the iteration limits are larger and
the ae i used are smaller.
Different sets of parameters do not cause divergence
of the algorithm, since during interaction
the current configuration is very close to a solution
satisfying the volume constraint, and the
algorithm needs fewer iterations to reach a solu-
tion. The parameter sets can be tuned using a
dialog box.
The user can manipulate a scale widget that
defines the desired volume for a chosen primitive.
The volume preservation algorithm is performed
repeatedly while the scale is dragged.
Tri-quadratic free-form volume design is fully
interactive. For a typical movement of a single
control point, to reach a final volume tolerance
of 10 \Gamma4 and a final distance tolerance of 10 \Gamma3 requires
about 15 outer iterations, each of them with
1-2 inner iterations. This takes about 3 seconds
on Silicon Graphics workstations with a MIPS R-
4000 processor. During interaction it is enough
to set both tolerances to 10 \Gamma2 ; in which case the
solution is completed in real-time.
For a tri-cubic free-form volume, to reach the
same tolerances requires about 25-30 outer itera-
tions, each of them with one inner iteration. This
takes about 15 seconds. When both tolerances
are set to 10 \Gamma2 during interaction the solver takes
about 3 seconds, hence tri-cubic interaction could
be done in real-time using a faster processor.
The running times above are of course dependent
on the number of linear constraints and on
how far the current configuration is from their solution

designed using the system. The amphora is
modeled from a single primitive, and the phone
was modeled from three tri-cubic primitives with
conditions between them. Its parts
were designed by volume modifications to create
the right proportions between them while keeping
the desired shape constraints and continuity.
9 Conclusion
We presented an approach for modeling with free-form
solid primitives while preserving the volume
contained within each primitive and satisfying
continuity constraints between the primitives.
Careful tuning allows our Uzawa-based non-linear
optimization algorithm to be fully interactive for
tri-quadratic volume elements and almost interactive
for tri-cubic elements. The algorithm possesses
several possible applications in computer
animation, industrial design and mechanical en-
gineering, broadening the scope of physics-based
geometric modeling.

Acknowledgments

Daniel Youlus participated in an early part of this
work. I thank Naftali Tishby for a fruitful comment
and the reviewers for their detailed comments.



--R

Studies in Linear and Nonlinear Programming
Two algorithms for volume-preserving approximations of surfaces of revolution
A modeling system based on dynamic constraints
A finite element procedure for non-linear incompressible elasticity
Minimization, constraints and composite B'ezier curves.
Deformation of n-dimensional objects
Simple constrained deformations for geometric modeling and interactive design.
Deformable curve and surface finite elements
Layered construction for deformable animated characters
Introduction to Numerical Linear Algebra and Optimization
sculpturing tool for 3D geometric modeling
Symbolic and numeric computation in curve interrogation.
Reconstruction for smooth parametric surfaces from unorganized data points
Curves and Surfaces for Computer Aided Geometric Design
A hierarchy of geometric forms

Curvature continuous blend surfaces.
Deformation of solids with tri-variate B-splines
Direct manipulation of free-form deformations
The Finite Element Method
Utilizing parametric hyperpatch methods for modeling and display of free form solids
Constrained optimization in surface design
Algorithms for computing area and Volume
Functional optimization for fair surface design
Numerical Recipes in C
Interactive design of smooth objects using probabilistic point constraints.

Motion interpolation by optimal control
Dynamic NURBS with geometric constraints for interactive sculpting
Computer Graphics
--TR

--CTR
Gershon Elber, Multiresolution curve editing with linear constraints, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.109-119, May 2001, Ann Arbor, Michigan, United States
Stefanie Hahmann , Basile Sauvage , Georges-Pierre Bonneau, Area preserving deformation of multiresolution curves, Computer Aided Geometric Design, v.22 n.4, p.349-367, May 2005
Jin Huang , Xiaohan Shi , Xinguo Liu , Kun Zhou , Li-Yi Wei , Shang-Hua Teng , Hujun Bao , Baining Guo , Heung-Yeung Shum, Subspace gradient domain mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Victor Brian Zordan , Bhrigu Celly , Bill Chiu , Paul C. DiLorenzo, Breathe easy: model and control of simulated respiration for animation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
Wolfram von Funck , Holger Theisel , Hans-Peter Seidel, Vector field based shape deformations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Victor B. Zordan , Bhrigu Celly , Bill Chiu , Paul C. DiLorenzo, Breathe easy: model and control of human respiration for computer animation, Graphical Models, v.68 n.2, p.113-132, March 2006
Gentaro Hirota , Renee Maheshwari , Ming C. Lin, Fast volume-preserving free form deformation using multi-level optimization, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.234-245, June 08-11, 1999, Ann Arbor, Michigan, United States
Christoph M. Hoffmann , Jaroslaw R. Rossignac, A Road Map To Solid Modeling, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.3-10, March 1996
continuity constraints;volume preservation;uzawa's algorithm;free-form deformations FFD;physics-based modeling;energy constraints;free-form solids