|
Warping of
Graphic Objects
by Ismail Ziauddin
Introduction:
Warping or deforming an object is a requirement for
creation of realism. Two approaches are taken, one is
geometrical and the other is physically based. The
geometrical approach requires specification of
parameters by user, while physically based method will
deform objects according to virtual forces, torques and
deformation functions of the environment.
A deformation is a modification of vertices of object
defined by a map
 ,
also known as space warp.
Model Representation:
The resultant deformation obtained by various
techniques differ depending upon object representation
such as polygonal, parametric or implicit formulation.
A polygonal object is defined by not only vertices,
but also connecting edges, and faces. The faces are
required to be planar. A deformation is likely to
produce non-planar polygonal faces, that could cause
problems in rendering if excessive deformation is
applied.
A parametric object has advantage in this regard if
deformation is applied to control points, but then final
object produced after parametric interpolation may not
be exactly faithful to required result.
An implicit object defined by
 can be deformed after polygonization, if polygonal
representation is used for rendering implicit objects,
then the same considerations as polygonal objects apply
to implicitly defined objects. It is also possible to
apply the deformation map when implicit function is
evaluated, and before any representation is used, then
it is likely to produce most faithful result, but
computation time will be more since deformation function
is evaluated every time implicit function is evaluated.
Local Geometric methods:
Local methods apply deformation to a subset of
vertices of an object. This subset is determined by
given criteria and region of interest. In contrast,
global methods apply to an entire object. An earlier
work by Barr [1] describes methods of global
deformations such as tapering, twisting and bending of
objects. In addition to these, Wywill [4] describes
shearing in context of implicit objects modeling.
One of the techniques of local deformation is based
on implicit functions modeling, where a scalar valued
function is used to determine ISO-potential
value to determine inside or outside of an object. A
scalar valued function with similar properties is used
to determine a subset of vertices of an object that are
candidates for deforming, and is called the modulating
function in this context. The work described here is
based on references [2] and [3].
Description of technique:
Consider two sets of points in R3, one called a
Reference set, and the other called Deformation set. The
points of Deformation set are scaled, translated and
rotated versions of points of Reference set. Each set
may contain equal number of one or more points. The
points may be isolated collection in 3D space, or
Reference and Deformation sets can be parametric curves
or surfaces. Reference [2] describes in detail a method
where both sets are parametric curves, called
"Wires" deformation method, while [3]
describes a method for collection of points, and also a
method that is feature based.
A point of the object to be deformed is denoted by
 ,
and the deformed point is denoted by
 .
The scalar parameters
and
denote radius of influence and scaling factor
respectively.
The point
will have one point
in Reference set that is closest to it with Euclidean
distance
 .
If there are more than one point, then only one needs to
be considered based on some criteria such as first
occurring point. The corresponding point to
in Deformation set is denoted by
 .
When modulation function is evaluated for input
Euclidean distance
between
and
 ,
it will produce an output
that is either positive greater than zero or non-positive.If
the value is not positive then
is not deformed. Otherwise
is scaled and translated by the same amount as point
is scaled and translated to produce
of Deformation set. This scaling and translation is also
multiplied by value of modulating function
.Additionally
the point
could also be rotated if tangent vectors to
and
are computable.
Formulation:
The following notation is based on reference [2].
Consider Deformation as a tuple
-
is a set of points, can be one or many isolated
points in 3D space, or can be a parametric curve or
surface.
-
is same type as
,
and is scaled, translated and possibly rotated version
of
-
is scaling scalar parameter
-
is a scalar parameter defining radius of influence
around reference set
-
is scalar valued modulating implicit function of
scalar
such that
- it is monotonically decreasing with increasing
- it is at least
 continuous
-
-
-
An example function given in [2]
 satisfies all of above properties
Let
denote a set, and
denote an index of a point in the set if
is a collection, or denote a parameter value if
is parametric curve, there will be two parameters
required if
is a surface. Let
be such that it minimizes the Euclidean distance of a 3D
point
from
,
then define
The properties of function
imply
-
when
-
when
-
varies from 1 to 0 as
varies from 0 to r and greater
In other words, modulating function f in combination
with radius of influence
defines an offset volume around reference set
.
The object points that fall within this volume are
deformed according to following algorithm.
- Scale point
by scaling factor ,
i.e. obtain
- Rotate point
by angle
around axis
about point
 .
is angle between
and
 ,
and
and
are the tangent vectors.
- add to point obtained so far a translation
 .
Varying parameter
and
allows different effects to be achieved, so does
different forms of modulating function, provided it
maintains the required properties.
Evaluation of Algorithm:
The hardest part of the algorithm is computing
closest point in the set. If parametric curves are
considered, then an algorithm is given in Graphics Gems III
for Bezier curves. For a collection of points, one has
to resort to Computational geometry methods of finding
point closest to a point in a set
|
|
|
| A
Sphere Deformed by Parametric Curve |
A Sphere
deformed a single point |
Algorithm:
// Deforms a single point
// template object func has
// - radius of influence r
// - scaling factor s
// - point to be deformed p
// - evalDefPt evaluates point in Deformation set at
parameter (or index) u
// - evalDefDer evaluates tangent at parameter (or
index) u
template <typename T>
VECTOR3 DeformPoint(const T& func, const double
u, const VECTOR3& Rp, const double Fpr)
{
VECTOR3 Dp = func.evalDefPt(u);
VECTOR3 dRp = func.evalRefDerv(u);
VECTOR3 dDp = func.evalDefDerv(u);
VECTOR3 Ps = func.p + (func.p - Rp) * (1.0 + (func.s
- 1.0) * Fpr);
double theta = dRp^dDp;
// Vector dot product
// Compare function returns 0, 1 or -1 for a==b,
a>b or a<b, within some small tolerance
theta = Compare(theta, 0.0) == 0 ? M_PI_2*Fpr :
acos(theta)*Fpr;
VECTOR3 Pr = Ps;
if (Compare(theta, 0.0))
{
VECTOR3 axis = dDp * dRp; // vector cross product
ROTATION q(axis, theta); // euler parameters
(Quaternion)
VECTOR3 Pr = XForm(q, Ps + Rp); // rotate point by
quaternion
}
VECTOR3 Pt = Pr + (Wp - Rp) * Fpr;
return Pt;
}
// Evaluates closest point in set R to point p, it’s
euclidean distance and value of modulating function
// based on these the DeformPoint function is called
or skipped
// function Distance returns parameter value (or
index in case of collection) of the point closest to the
point to
// be deformed
template <typename T>
VECTOR3 Deform(const T& func)
{
double u = Distance(func);
VECTOR3 Rp = func.evalRefPt(u);
double Fpr = func.modulate((func.p-Rp).Length()/func.r);
return Fpr <= 0.0 ? func.p : DeformPoint(func, u,
Rp, Fpr);
}
References:
[1] A. Barr: Global & Local deformations of solid
primitives, SIGGRAPH
1984 proceedings
[2] Karan Singh, Eugene Fiume: Wires: A geometric
deformation technique, SIGGRAPH
1998 proceedings.
[3] J.
M. Zheng, K.W. Chan, I. Gibson: Surface Feature Constraint
Deformation for Free-form Surface and Interactive Design,
Fifth ACM
symposium on Solid modelling, 1999.
[4] Brian Wyvill, Kees van Overveld: Warping as a
modelling tool for CSG/Implicit
Models, http://www.cpsc.ucalgary.ca/~blob/papers.html
Contact Ismail
directly at ismailz@rediffmail.com
|
