Class Notes
(811,705)

United States
(314,697)

Georgia Institute of Technology
(1,473)

Computer Science
(81)

CS 6491
(1)

Jarek Rossignac
(1)

Lecture

# curvature_offset_smi_2012.pdf

Unlock Document

Computer Science

CS 6491

Jarek Rossignac

Summer

Description

Wei Zhuo and Jarek Rossignac “Curvature-based O▯set Distance: Implementation and Applications” Shape Modeling International 2012, May
22-25, Texas, USA. (To appear as a journal paper in a special issue of Computer & Graphics)
Curvature-based O▯set Distance: Implementations and Applications
a a
Wei Zhuo , Jarek Rossignac
awzhuo3, [email protected]
College of Computing, Georgia Institute of Technology
Abstract
We address three related problems. The ﬁrst problem is to change the volume of a solid by a prescribed amount,
while minimizing Hausdor▯ error. This is important for compensating volume change due to smoothing, subdivision,
or advection. The second problem is to preserve the individual areas of inﬁnitely small chunks of a planar shape,
as the shape is deformed to follow the gentle bending of a smooth spine (backbone) curve. This is important for
bending or animating textured regions. The third problem is to generate consecutive o▯sets, where each unit element
of the boundary sweeps the same region. This is important for constant material-removal rate during numerically
controlled (NC) machining. For all three problems, we advocate a solution based on normal o▯setting, where the
o▯set distance is a function of local or global curvature measures. We discuss accuracy and smoothness of these
solutions for models represented by triangle or quad meshes or, in 2D, by spine-aligned planar quads. We also explore
the combination of local distance o▯setting with a new selective smoothing process that reduces discontinuities and
preserves curvature sign.
1. Introduction
In this paper, we discuss the use of normal o▯setting
[1] for volume or area preservation, where the o▯set
distance is computed globally or locally from curvature
measures. Speciﬁcally, we address the following three
problems.
Figure 1: The original 3-branch-star base shape P (green) is shown
1.1. Adjust volume while minimizing Hausdor▯ error with three o▯set shapes O (red) that enclose regions of the same area:
global scaling (left), variable distance o▯setting (center), and con-
We are given a base solid P with volume V . TyPi- stant distance o▯setting (right). The respective Hausdor▯ distances
cally, P is obtained by applying a small deformation to are: 15:9, 4:6, and 3:1. A line segment connecting P and Q indicate
where the Hausdor▯ distance is reached. On the right, all points are at
some starting solid S, which has volume V . TheSde- the Hausdo▯ distance from the other set.
formation may be the result of subdivision [2], smooth-
ing [3], or advection of a ﬂuid/swimmer interaction [4].
We want to obtain an o▯set solid O that is similar to P, global scaling and to variable distance normal o▯setting
but has volume V . Speciﬁcally, we deﬁne O as the (discussed in Sec. 1.3).
S
shape that minimizes the Hausdor▯ distance, ▯(P;O),
between P and O, with O constrained to having vol- 1.2. Preserve local area during spine bending
ume V .SMaintaining the volume is important in man- We are given a portion of a image R. R roughly
ufacturing applications where weight matters [5] and aligned along a smooth spine curve P. Note that P does
in physically based simulations where incompressibil- not need to be the medial axis of R and that the width of
ity matters [6]. The solution proposed here deﬁnes O R may vary along P. We are also given a bent version P ﬂ
as the constant distance o▯set (CDO) of P: O = P . h of P. We assume that P and P have identical length and
We explain how to compute the correct distance h, both are both parameterized by arc-length. Assume that each
in two and three dimensions. We discuss accuracy in point O of R has a unique closest projection on P. We
cases where P and O are represented by piecewise lin- want a locally area-preserving homeomorphism H that
ear boundaries. In Fig. 1, we compare this solution to maps point O = P(s)+rN(s) to point P(s)+hN(s), where
1 animation has area ur, where r is a given nominal depth.
This is important because NC machining is most e▯-
cient when the cutter advances at constant speed (tan-
gentially along a contour O ) andiremoves a constant
amount of material per unit of time [7]. Our solution
combines two steps: (1) a variable distance o▯set where
the local o▯set distance h is computed from the nominal
distance r and the local curvature k of O usinj a simple
variation of the formulation discussed above, and (2) a
selective smoothing, which reduces the sharp features
introduced by step (1) and ensures that the curvature at
a point does not change sign during o▯setting. In Fig. 3,
we compare constant distance o▯setting, variable dis-
tance o▯setting, and the proposed solution which com-
bines steps (1) and (2).
Figure 2: On the top (a), we show a texture region painted with an
axis-aligned checkerboard pattern along a straight spine curve P. Be-
low (b), we show a deformed version P of the spine and the result of
a mapping where h = r. The squares of the checkerboard are colored
to indicate area preservation (more green), compression (more red),
or dilation (more blue). Below (c), we show the proposed corrected
mapping. At the bottom (d), we show the proposed corrected map-
ping while doubling the sampling density. Notice that this increased
sampling reduces area errors signiﬁcantly.
N(s) is the normal to P at P(s) and N(s) is the normal to
P at P(s). By locally area-preserving, we mean that any
subset Q of R has same area as its image H(Q).
The approach that we advocate here deﬁnes h in terms
of r and the curvature k(s) of P at P(s) and the curva-
ﬂ ﬂ ﬂ
ture k(s) of P at P(s). For an exact solution h to ex-
ist, r must fall within a speciﬁc range deﬁned by k(s)
ﬂ
and k(s). In Fig. 2, we compare this “ﬂeshing” solution
to the common skinning solution with h = r. We also
discuss the computational and accuracy advantages of Figure 3: We show a series of contours produced by constant distance
o▯setting (a), curvature-based distance o▯setting (b), and curvature-
the spine-aligned grid, as shown in Fig. 2, over an axis based distance o▯setting with selective smoothing (c). The successive
aligned grid. constant distance o▯sets (a) do not preserve a constant area-to-length
ratio and produce self-intersections for larger o▯set distances. Suc-
cessive curvature-based o▯sets (b) preserve that ratio, but exhibit an
1.3. Generate contours for constant material removal
increasing amount of discontinuities where the curvature of the pre-
We are given the planar boundary P of a pocket to vious o▯set changes rapidly (we only render the ﬁrst few contours).
The proposed combination of curvature-aware o▯setting and selective
be machined, and we want to compute a series, fO g, j smoothing (c) produces concentric o▯set contours that are smooth and
of concentric variable-distance normal o▯set contours. approach a constant area-to-length ratio. The selective smoothing en-
For each contour, we want to adjust the o▯set distance sures that the curvature at each point maintains its sign or becomes
zero. Hence, the process converges towards a convex shape, as can be
locally, so that the area of a segment of the corridor be-
tween two consecutive contours is proportional to the extrapolated from the drawing.
length of that segment. More precisely, consider an an-
imation that moves all points of O alongjtheir normal
1.4. Summary of contributions
until they reach their o▯set point on O j+1. For any con-
nected subset S of O , ljt u denote its length. Our objec- The solutions to all three problems are based on
tive is to ensure that the region swept by S during this a curvature-based distance correction, which maps a
2 nominal distance r to a distance h. In two dimensions, the Minkowski sum [11] of S with a ball of radius r cen-
assuming that k is the curvature, h is a speciﬁc root of tered at the origin. It may also be expressed as the union
of all balls of radius r with center in S. S contains all
1
kh + h ▯ r = 0 (1) points at distance r or less from S. Steiner [8] has de-
2 rived formulae for the area change and volume change
under constant distance o▯setting for the special cases
In three dimensions, assuming that g is the Gaussian and
m the mean curvature, h is a speciﬁc root of of convex sets of genus zero. Here in Sec. 4 we prove its
generalization to non-convex solids and to higher genus
solids.
1 gh + mh + h ▯ r = 0 (2)
3 CDO operations are important in planning and sim-
ulating NC-machning processes [12], where they are
The derivation of these equations and their prior use for
used to generate constant thickness layers of material
constant area or volume o▯setting is discussed in the to be removed by successive machining passes, and for
next section. Our contributions comprise the following: creating ﬁllets and blends [13] by o▯setting the solid
1) To solve the ﬁrst problem of constant distance o▯-
and then its complement or vice versa. In 2D, CDO
setting for a desired volume change, we generalize the preserves the domain of shapes bounded by piecewise-
Steiner formula [8] for the volume change under con- circular curves [14]. In 3D, we obtain our approxi-
stant distance o▯setting to non-convex solids as well as
mation by o▯setting each vertex by a constant distance
to higher genus solids, and we describe an e▯cient im- along an estimated vertex normal. Numerical and topo-
plementation. We also analyze the error sensitivity of logical accuracy issues of CDOs of solids bounded by
our formula, study the impact of sampling density on
triangle meshes and polyhedral surfaces have been in-
its accuracy, and report the results on benchmark curves vestigated in various applications [12] [15].
and surfaces.
2) To solve the second problem of local area preser-
2.2. Variable distance o▯setting
vation during skeletal bending, we have adapted the for- Variable-distance o▯setting (VDO) is speciﬁed by as-
mulation (Equ. 1) originally developed by Chirikjian [9] signing a distance h(s) to each point P(s) of the base
for locally area-preserving bending. Chirikjian dis-
shape P (curve in 2D or surface in 3D). Three di▯er-
cusses divergence-free deformation for continuous ent interpretations of this speciﬁcation have been com-
models. We explore its use for deforming discrete, pared in [16]. The radial o▯set is the union of balls
texture-mapped quads to follow the bending of a polyg- (P(s);h(s)). The ball o▯set [17] is the union of balls
onal spine. Speciﬁcally, we propose the use of a spine- of diameter h(s) that are tangent to P at P(s). Finally,
aligned grid, and argue its advantages over axis-aligned the normal o▯set [1] is the union of all line segments
grids. of length h(s) that are normal to P at P(s). In all three
3) To address the third problem of constant material cases, under su▯cient assumptions on the smoothness
removal modeling, we build upon the solution proposed
and curvature of P, there is a bijective mapping between
by Moon [7], but show that it produces sharp discon- P and a portion of the boundary of the o▯set shape,
tinuities of the o▯set curve near concave features. We which may be formulated as an envelope of a set of line
propose a novel selective smoothing technique which
segments or balls. (Note that each formulation imposes
eliminates these sharp features while preserving the cur- a di▯erent set of constraints on the relation between the
vature sign between the original points and their o▯sets. o▯set distance function and the curvature of P [1].) The
shape and curvature of these envelopes may be com-
puted e▯ciently [16]. Here, we restrict our attention to
2. Prior Art the normal o▯set, hoping that the other two interpreta-
In this section, we discuss relevant prior work in tions will be investigated later. One issue addressed in
this paper is the computation of the o▯set distance ﬁeld
constant distance o▯setting, variable distance o▯setting, h(s) that distributes the “invaded” space uniformly. Let
volume correction, and skeleton-driven shape deforma-
tions. P be a surface in 3D. Let, Q be a subset of P, and R
be the region swept by Q during the o▯set. We want
to compute a variable o▯set distance function h(s) such
2.1. Constant distance o▯setting
that the ratio r of R’s volume over the area of Q is a con-
The constant-distance o▯set (CDO) S of a solid S stant. If P is a curve in 2D, r is the ratio of the area of R
by distance r [10], also called dilation, is formulated as over the arc-length of Q. This equi-volumetric o▯setting
3 has been investigated by Moon [7] [18] for NC machin- distance, when it exists within the allowable range, or
ing, so as to ensure a constant material-removal rate, the appropriate range bound otherwise. We use a sub-
rather than constant depth of removal. Moon has shown script (2D and f3D ) to distinguish the 2D and 3D ver-
that, in valid situations where the curvature is smaller sions of f. We also discuss how to select the proper
than some limit deﬁned in terms of r, h(s) may be for- root in each case.
mulated as the root of a quadratic equation, for the 2D
case, and of a cubic equation, for the 3D case. Speciﬁ- 3.1. Function interface and capping
cally, in 2D, h is the root of1 k(s)h(s) + h(s) ▯ r = 0,
2 f2D takes as input the signed curvature k and and
where k(s) is the curvature of P at P(s). In 3D, h(s) the reference distance r respectively. The output h =
is the root of 1g(s)h(s) + m(s)h(s) + h(s) ▯ r = 0 ▯1+ p1+2kr
3 f2D(k;r) is the quadratic root k of Equ. 1 when
where g(s) is the local Gaussian curvature and m(s) is 1+2kr > 0. Otherwise, f caps the value of h and returns
the local mean curvature of P at P(s). These curvature
the limit ▯1=k so as to prevent a local self-intersection.
based distance functions have been studied by Hagen f3D takes as input the signed Guussian curvature g,
and Hahmann as generalized focal surfaces [19] as a
the mean curvature m and the reference distance r. The
tool for surface interrogation. We build our local o▯- output h = f 3D(g;m;r) is the valid cubic root of Equ. 2.
setting solutions to the volume compensation and to the
Notice that if g = 0, then h is computed via the 2D solu-
area-preserving bending on these equations. tion discussed above, as f2D (2m;r). Otherwise, we need
to select the proper real root and to ensure that the solu-
2.3. Skeleton-driven deformations tion is capped to an allowable bound. Moon [18] has de-
Consider the planar shape S to be the union of an rived the existence condition and the monotonic region
inﬁnite set of disjoint line segments intersected at their where the valid root exists. In our implementation, we
use a change of variables: h =▯ h, g = gr and m = ▯
midpoints by a continuous spine P. Let 2h(s) and a(s) p r p
deﬁne the length of the line segment and its angle to mr. Then if 2 m ▯2 ▯ g ▯ m > 3(m ▯ ▯ m ▯2▯ g ),
1
the tangent to P at P(s). Cavlieri’s principle [20] im- there is a unique positive real root in [0; p m ▯g ▯m ▯].
plies that, when bending P, the area of the convex hull
Otherwise, no valid real root exists and we output the
of two inﬁnitely close line segments remains constant maximum o▯set distance that is free from a local self
regardless of the shape of S, as long as we preserve
intersection.
h(s) and a(s) and do not bend P(s) excessively (ensur-
ing that the radius of curvature at P(s) does not exceed
3.2. Error Sensitivities
h(s)). Although this solution preserves the area of each Estimating curvature from a sampling of a smooth
convex hull of consecutive two line segments, it does
not preserve the local area on each side of the spine, as curve will produce an incorrect o▯set distance. Below
we show that the error in h is a linear function of the
discussed in the introduction. Several approaches have
been proposed to maintain a constant local area of a re- errors in the curvature estimation, both in 2D and in 3D.
Let ▯ represent a small variation in the variable x.
gion as its spine is bent. Chirikjian [9] has derived the x
quadratic equation mentioned above by constraining the Assume that r is a constant. For 2D, we take the deriva-
tive of Equ. 1 and arrive at
Jacobian of the deformation to be 1, so as to make it lo-
cally area preserving. When the spine bend exceeds the 2
h
local limit, the normal o▯setting is no longer appropri- ▯k+ kh▯ h ▯ =h0
ate. More general techniques for skinning and ﬂeshing 2
with locally-preserving bending have been proposed by From this, we conclude that ▯ hs proportional (/) to ▯ :k
Rohmer and colleagues [21]. They adjust both the di-
h2
rection and distance of the o▯setting and solve for an ▯h/ ▯k
optimal solution that favors locality. 1 + kh
Similar for 3D, we take the derivative of Equ. 2 and ob-
tain
3. Curvature-based O▯set Distance Computation 3 2
▯gh + ▯ m
▯h/ 1 + 2mh + gh 2
In this section, we discuss implementation and accu-
racy issues of computing the curvature-based o▯set dis- Therefore, the numerical error in the output of f is linear
tance. For implementation simplicity, we deﬁne a func- in the errors of its inputs when kh > 0 in 2D, or 2mh +
tion f in 2D and in 3D, which returns the proper o▯set gh > 0 in 3D.
4 3.3. Curvature approximation Note that a global curvature has the same unit as its local
Densely sampled polylines and polygonal meshes are counterpart.
often used in modeling solids with smooth boundaries
whose parametric expression may not be conveniently
available. Hence, we adopt discrete formulas to evaluate 4. Dilation with Prescribed Volume Change
the curvatures. Consider a 3D shape P with volume V . We want
P
to compute O from P by a single step of dilation, so
3.3.1. Local curvatures
Let P denote a watertight quad or triangle mesh and that the enclosed volume is increased by a prescribed
amount ▯V. We ﬁrst discuss methods that are not based
P i vertex of P. The local curvature at P cin be eval-
uated from its one-ring neighbors fQ gj In 2D, the dis- on curvature measures. Then we present our solution.
crete curvature kimay be conveniently calculated by ﬁt-
ting a parabola to P ind its neighbors. In 3D, we use 4.1. Uniform scaling
the discrete formulas proposed by Meyer, et. al. [22]. The work of Desbrun et. al. [23] introduces a simple
Speciﬁcally, the local area Aiassociated with P ii ap- approach of rescaling P around its barycenter C by a
proximated by the area sum of incident Voronoi cells. uniform amount s:
The gradient of A with respect to P , aiso known as
the discrete Laplace Beltrami operator, has the follow- O = C + s(P ▯ C) (7)
ing closed form [23]: q
3VP+▯V
where s = VP . Uniform scaling guarantees that the
X P Q ▯ Q Q P Q ▯ Q Q
rA = 1 ( i j▯1 j▯1 j + i j+1 j+1 j )PQ enclosed volume is increased exactly by ▯V. However,
i 2 jPiQ j▯1▯ Q j▯1Q j jP i j+1▯ Q j+1 j i this approach generates unbounded Hausdor▯ error be-
j
(3) tween O and P (Fig. 1).
Then, the local mean curvature is approximated by a
scaled dot product of ▯A iith the unit normal at Pi. The 4.2. Linearized solution
local Gaussian curvature is approximated by the angle In contrast, when a constant distance normal o▯set by
deﬁcit at Pi[22]. a distance h is used, the Hausdor▯ error is exactly h (as-
suming that h is smaller than the least feature size of the
3.3.2. Global curvatures shape). When using a constant distance o▯set (CDO), to
Let A denote the total surface area of P. We refer
P increase the volume of a solid by ▯V, one must compute
to the surface integral of Gaussian curvature divided by the proper o▯set distance h. One approach [21] is to use
A as the global Gaussian curvature (g ) and the surface ▯V
P P h = A P. We compare below this approximate solution
integral of mean curvature divided by A aP the global to the one proposed here.
mean curvature (m ). The integrated Gaussian is intrin-
P
sic to P and equals 2▯▯ P where ▯ iP the Euler charac-
4.3. Normal o▯set based on the global curvature
teristic of P. P▯ = V▯E+F where V, E, F are numbers
of vertices, edges and faces.) Therefore, The correct solution deﬁnes h as the appropriate root
computed by f 2D or f3D as explained earlier in Sec. 3.1.
2▯▯ P
g P (4) We include below the derivation of this result.
A P
The surface integral of mean curvature is related to the 4.3.1. 2D
bending energy [24], which we denote as E . Pote that Let P denote a Jordan curve of length L . Let, k(s)
P
E Pan be approximated by the scaled sum of jrA j at i and N(s) be the signed curvature and the unit normal
each vertex. Therefore, of P at P(s). The curvature k(s) is the derivative of the
EP unit normal. Hence, we have the following expression
m P (5) of the area increase ▯A associated with o▯setting P by
AP
a constant distance h:
In 2D when P denotes a Jordan curve, its integrated cur- ZZ
vature is intrinsic and equals 2▯ [25]. Let P denote the @(P(s) +
N(s))
▯A = j jd
ds
length of P. The global curvature of P, kP, is deﬁned as
2[0;h] @s
2 Z
2▯ h
kP= L (6) = hL P 2 k(s)ds
P
5 By the Total Curvature Theorem [25], we have 4.4. Proof of minimizing Hausdor▯ error
Z Let P, O and Q either be regularized planar regions or
k(s)ds = 2▯ d
solids. Assume that O = P for some positive distance
d. (If instead we want a negative d, the argument below
Therefore we arrive at, will hold for the complements of P, O and Q and still
support our conclusion.) We will prove that 8Q , O,
▯ ▯A V = V ) H(Q; P) > H(O; P), where H deﬁnes
h + h ▯ = 0 (8) Q O
LP L Hausdor▯ distance and V Xenotes the area or volume
of X.
Hence to compensate for the area change ▯A, we need
Assume that V Q = V O First, we note that Q can-
to o▯set the curve P by a constant distance h computed not be a proper subset of O, otherwise we would have
by h = f (2▯;▯A ). Or equivalently, h = f (k ; ▯A)
2D LP LP 2D P LP V Q < V O Second, we note that Q cannot contain any
using the global curvature deﬁned in Equ. 6. point q outside of O, otherwise we would have the dis-
tance from q to P, d(q; P) > d (Since O includes all
4.3.2. 3D points at distances less or equal to d from P) and hence
Let P(u;v) denote a point on a surface P parameter- H(Q; P) > d. From these two observations (Q is not a
proper subset of O and Q is a subset of O), we conclude
ized by u and v. We derive the exact expression of the
volume increase when o▯setting P(u;v) by a constant that if Q , O then H(Q; P) > H(O; P). Hence, O is
distance h. Let m(u;v) and g(u;v) represent the local Hausdor▯ distance minimized. ▯
mean and Gaussian curvature of P at (u;v). Since the
mean curvature is the divergence of the unit normal and 4.5. Implementation
the Gaussian curvature is the determinant of its Hessian,
the volume increase ▯V can be expressed as follows: We have implemented the three volume correction
schemes (Uniform scaling, Linearized, and Curvature-
ZZZ
based solutions) on quad as well as triangle meshes. Our
▯V = jr(P(u;v) +
N(u;v))jd
dudv implementation uses a Corner Table [26] representation
ZZ
2[0;h] ZZ and the associated corner operators. The whole process
1
= h jrPjdvdu + h2 r ▯ Ndvdu is only a few lines of code. First, to compute the global
2 mean curvature m we sum the area gradient at each
1 ZZ P
+ h3 jrNjdudv

More
Less
Related notes for CS 6491