12 Pages
Unlock Document

Computer Science
CS 6491
Jarek Rossignac

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 first 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 infinitely 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. Specifically, 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 fluid/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 . Specifically, we define 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 defines O R may vary along P. We are also given a bent version P fl 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 significantly. 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 defines h in terms of r and the curvature k(s) of P at P(s) and the curva- fl fl fl ture k(s) of P at P(s). For an exact solution h to ex- ist, r must fall within a specific range defined by k(s) fl and k(s). In Fig. 2, we compare this “fleshing” 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 first 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 specific 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 specific 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 fillets and blends [13] by o▯setting the solid 1) To solve the first 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 specified 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 specification 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. Specifically, 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 field 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 defined 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. Specifi- 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 infinite 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 define 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 infinitely 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 fleshing 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 define 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 first 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 fit- 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 Specifically, 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 deficit 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 defines 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 defined 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 defines 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 defined 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

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.