Content uploaded by Miklós Hoffmann

Author content

All content in this area was uploaded by Miklós Hoffmann on Dec 21, 2018

Content may be subject to copyright.

Skinning of circles and spheres

R.Kunklia, M.Hoﬀmanna,b,1,∗

aDepartment of Computer Graphics and Image Processing, University of Debrecen, Egyetem sqr. 1,

H-4010 Debrecen, Hungary

bInstitute of Mathematics and Computer Science, K´aroly Eszterh´azy College, Le´anyka str. 4, H-3300 Eger,

Hungary

Abstract

Skinning of an ordered set of discrete circles is discussed in this paper. By skinning

we mean the geometric construction of two G1continuous curves touching each of

the circles at a point, separately. After precisely deﬁning the admissible conﬁgura-

tion of initial circles and the desired geometric properties of the skin, we construct

the future touching points and tangents of the skin by applying classical geometric

methods, like cyclography and the ancient problem of Apollonius, ﬁnding touching

circles of three given circles. Comparing the proposed method to a recent technique

(Slabaugh et al.,2008; Slabaugh et al.,2009), larger class of admissible data set and fast

computation are the main advantages. Spatial extension of the problem for skinning of

spheres by a surface is also discussed in detail.

Keywords: interpolation, skinning, circles, spheres, cyclography

2000 MSC: 68U05

1. Introduction

Interpolation of geometric data sets is of central importance in Computer Aided

Geometric Design. If geometric data consist of points, then we have several, now stan-

dard methods to interpolate them (Farin,1997; Piegl and Tiller,1995; Hoschek and Lasser,1993).

If, however, the data set consists of other types of objects (e.g. circles), interpola-

tion is transferred to skinning, that is construction of a curve or surface which touches

each of the objects and somehow bounds the given data. Since this is a largely ill-

posed problem, constraints have to be deﬁned for the data set as well as for the desired

solution.

In this paper we address the problem of skinning of a sequence of circles. This

problem is sometimes called 2D ball skinning, with a natural extension to 3D, where a

skinning surface of a set of given spheres is to ﬁnd.

∗Corresponding author

Email addresses: rkunkli@gmail.com (R.Kunkli), hofi@ektf.hu (M.Hoﬀmann)

1Author supported by Bolyai Research Fellowship of the Hungarian Academy of Sciences

Preprint submitted to Elsevier May 3, 2010

Since the problem of skinning is not necessarily deﬁned in a unique way in the

literature, here we formally describe what type of input is admissible for us and what

type of output we are searching for.

Deﬁnition 1. A sequence of circles C={c1,c2,c3, . . . , cn}(n∈N) is called admissible

conﬁguration if the following conditions are fulﬁlled (didenotes the closed disk deﬁned

by circle ci):

•di1

n

[

j=1,j,i

dj,i∈ {1,2, . . . , n}

•di∩dj=∅,i,j∈ {1,2, . . . , n},j<{i−2,i−1,i,i+1,i+1}

•if di−1∩di+1,∅, then di−1∩di+1⊂di

These assumptions also yield

ri<

i+1

[

j=i−1

dj,i=2, .., n−1

where riis the radical center of three consecutive circles ci−1,ci,ci+1. In Fig. 1 one can

see an admissible conﬁguration and a conﬁguration where some circles do not fulﬁll

the conditions.

Figure 1: An admissible conﬁguration (left) and a non-admissible conﬁguration (right) where circles c2−c4,

c6and c8do not fulﬁll the conditions: circles are not allowed to be entirely in the union of other circles while

radical center r3of three consecutive circles must be out of c3

Since the position of radical center will be of central importance in the algorithm,

we brieﬂy remind the reader to the deﬁnition and computation of it. The radical axis (or

radical line) of two circles is the locus of points at which tangents drawn to both circles

have the same length. Since it is evidently orthogonal to the line passing through the

centers, it is enough to compute the distance of the axis to the centers:

d1=1

2

d+r2

1−r2

2

d

d2=1

2

d−r2

1−r2

2

d

2

where dis the distance of the two centers, r1,r2are the radii of the circles. By a

classical theorem of Monge the radical lines of three circles are either concurrent in a

point, known as radical center, or parallel iﬀthe three circle centers are congruent.

Now we deﬁne the desired output.

Deﬁnition 2. Given an admissible conﬁguration of circles C={c1,c2,c3, . . . , cn}, we

are looking for two, at least G1continuous curves s(t) and ¯

s(t), called skins of the given

circles satisfying the following requirements (see also Fig. 2):

•There is a point of contact pi∈cifor all i=1, ..., nsuch that pi∈s(t) and tangent

lines of circle ciand s(t) are identical at pi. Analogously exist points ¯

pifor ¯

s(t).

•Tangent vector viof skin s(t) at pican be rotated to the direction of the center of ci

by 90◦in clockwise direction. Analogously this rotation is in counterclockwise

direction for tangent vectors of ¯

s(t).

•pi1

n

[

j=1,j,i

dj,and ¯

pi1

n

[

j=1,j,i

dj,i∈ {1,2, . . . , n}

For the sake of simplicity s(t) will be called ”left” skin and ¯

s(t) will be called ”right”

skin, based on the second requirement which ensures us that running along the skins, at

the points of contact the circles will always be in one (right or left) side of the curves.

Note, that due the last restriction, points of contact on the actual circle are required

to be out of other circles, which seemed to us a natural condition for skinning.

This or similar problem - beside its theoretical interest - frequently arises in ap-

plications like designing tubular structures, covering problems, molecule modeling

(Cheng and Shi,2005; Edelsbrunner,1999)). Medical image processing applies these

methods in e.g. blood vessel reconstruction (Whited et al.,2007; Slabaugh et al.,2009).

In computer animation, characters can also be constructed from a skeletal structure and

a corresponding geometric skin (Singh and Kokkevis,2000).

Figure 2: Two curves at left satisfying all the requirements to be skins. At right there are two curves which

also touch each circles but they do not fulﬁll the requirements: some of the touching points are inside of

other circles and separation of the two sides is not appropriate

The paper is organized as follows. After discussing the previous approaches, in

Section 3 we describe the new method and show that for an admissible conﬁgura-

tion of circles it always works. Detailed algorithm, several examples and comparison

3

to Slabaugh’s method can also be found in this section. Spatial extension to sphere

skinning by a surface is explained in Section 4. Conclusions and possible further im-

provements close the paper.

2. Previous work

The ﬁrst and most natural approach of the problem would be the application of

the deep theoretical knowledge of the computation of envelope curves and surfaces,

dated back to Monge (Monge,1850), who ﬁrst dealt with canal surfaces. Skin is def-

initely not an envelope, since this latter notion is deﬁned for continuous data set, for

a one- or two-parameter family of curves or surfaces. The ﬁrst requirement at De-

ﬁnition 1, however may be considered as the discrete version of envelope property.

An important contribution of this topic with computational aspects is the PhD thesis

of Josef Hoschek (Hoschek,1964). Since then a large number of papers have dealt

with envelope design, most of them with numerical computation (for the survey see

e.g. (Farin et al.,2002)). For circles and spheres, a recent exact solution is Peternell’s

method which is based on a cyclographic approach. In 2D cyclography deﬁnes a one-

to-one correspondence between the oriented circles of the plane and points in space

by cones. This way the sequence of given circles can be transformed to a sequence

of spatial points. An interpolating curve through these points can be deﬁned by any

standard method and ﬁnally points of this spatial curve can be transferred back to

circles on the plane by the cones. The envelope of these circles is obtained as the

intersection of the plane and the envelope surface of the cones. Similar correspon-

dence works for spheres and points in 4D space. For a more detailed description, see

(Kruithof and Vegter,2006; Peternell et al.,2008) .

Figure 3: Given a set of discrete circles (black), classical interpolation may yield further circles (dashed

blue) in a way that the skin cannot be constructed for the original circles since the new set of circles do not

satisfy the requirements to form an admissible conﬁguration (positions pointed by red arrows)

Although the papers mentioned above do not deal with skinning, one may try to

transfer the discrete data set to a one-parameter family of circles/spheres, having cen-

ters and radii as functions of a parameter. These functions can be achieved from the set

of discrete data by classical interpolating methods in the space, but this way the set of

4

new circles do not necessarily satisfy our requirements to be an admissible conﬁgura-

tion, as one can observe in Fig. 3.

A recent approach to the skinning problem for circles and spheres is Slabaugh’s

method (Slabaugh et al.,2008; Slabaugh et al.,2009). It is an iterative way to construct

the desired curves or surfaces. Let the discrete sequence of circles with centers ciand

radii ri,(i=1,...,n) be given. Initially pairs of Hermite arcs are deﬁned between

the consecutive circles. Considering two neighbouring circles ciand ci+1, an initial

Hermite arcs are speciﬁed with touching points pi,pi+1and tangents vi,vi+1for the

skin. The ﬁnal positions of these points and tangents are obtained by the end of several

iteration steps.

Figure 4: A one-sided (left) skin obtained by the method of Slabaugh (left ﬁgure, from

(Slabaugh et al.,2008)). For two-sided skin they constrain the points of contact to be separated by 180 de-

grees, but this way some of the points of contact may fall into other circles (middle ﬁgure). Right ﬁgure

shows the result of the proposed method: the green touching points of the left skin are almost identical to the

ones obtained by Slabaugh. The right (lower) skin has signiﬁcantly diﬀerent touching points.

The iteration itself is based on the minimization of a predeﬁned energy function.

For computational reasons the positions of the touching points and the tangents are

transferred into one single variable, namely the angle αibetween the xaxis and the

radius pointing towards the touching point.

pi=oi+"ricosαi

risinαi#,

vi="−kisinαi

kicosαi#,

where kiis a predeﬁned constant for each circle, half of the distance between the centers

oiand oi+1.

The method provides energy-minimized, C1continuous skin without any user in-

teraction, which, in this sense, the optimal solution, if it exists. But the method also

suﬀers from problems. The touching points are not guaranteed to be out of the circles,

especially not for two-sided skin, when the two touching points at each circle are con-

strained to be separated by 180◦degrees (c.f. Fig. 4). There are simple conﬁgurations

when it is theoretically impossible to ﬁnd two diametrically opposite points on a circle

being out of other given circles, see e.g. the second circle in the leftmost ﬁgure of Fig.

9 or the lower right ﬁgure of Fig.5. Slabaugh’s method does not provide acceptable

skin by our deﬁnition, especially the last requirement in Deﬁnition 2 is not necessarily

fulﬁlled. From this point of view our method can handle a larger class of data sets. One

5

would try to omit this 180◦constrain from that method but then we are facing to solve

the separation of touching points, which is far from being trivial in a numerical itera-

tion. The same problem arises in 3D-ball skinning, where Slabaugh’s method allows

only great circles as possible touching circles. A further problem is that the conver-

gence of iteration to a global minimum is not proved and the number of iterations can

be over 100 which is time consuming. Moreover, the process has to be restarted after

any modiﬁcation of data, thus this method is not suitable for real time modeling and

adjustment. For comparison to our method: the one-sided skin in Figure 4 (left) has

been computed by Slabaugh in 143 milliseconds ((Slabaugh et al.,2008), the two-sided

skin (right) has been computed by our method in 14 milliseconds (both at single core

3GHz CPU).

3. Our method

Now our task of skinning can be divided into the following steps:

•check if the given circles form an admissible conﬁguration

•ﬁnd appropriate points of contact for each circle ci,i=1, ..., n

•separate points into two classes, denoted by piand ¯

pifor left and right skin

•deﬁne tangent vectors viand ¯

vi

•compute the skins

The admissible criteriae of Deﬁnition 1 can be tested by elementary computation.

3.1. Localization of touching points

As we have learned from the previous section, the localization of possible touching

points on the given circles is essential for skinning. Our solution of ﬁnding the touching

points is based on the circles of Apollonius, which are touching circles to three given

circles. This ancient construction provides suitable touching points to each inner circle

in the data set, while the ﬁrst and last circles are handled in a simple special way.

A classical result (Muirhead,1896) on the possible positions of three circles and

solutions of problem of Apollonius states that for three given circles ci−1,ci,ci+1,(i<

{1,n}) which satisfy our admissible conditions, exactly one of the following statements

holds:

•There exist exactly two circles touching externally by all the three given ones

•There exist exactly two circles touching internally by all the three given ones

•There exists exactly one circle touching externally and another one touching

internally by all the three given ones.

6

Figure 5: Considering three consecutive given circles (black), the touching points of the second circle are

computed by the two circles of Apollonius (red). Orientation of circles help to ﬁnd the correct solutions. The

method always works for circles in admissible conﬁguration

These touching circles together with their touching points can be found by a classi-

cal geometric method, the cyclography. Consider the three given circles to be oriented,

this yields eight diﬀerent possibilities. The touching circle is always expected to have

the same orientation at each touching point as the given circles. This way the eight

diﬀerent solutions can be distinguished by the original orientation of the given circles.

In two cases all the three given circles have the same orientation. The solutions of

these two cases provide the touching points piand ¯

piof the circle ci(c.f. Fig.5). These

points can be constructed and computed by known methods (M¨

uller and Krames,1928)

(Coaklay,1860). Moreover, it is also proved (M¨

uller and Krames,1928) that these touch-

ing points and the radical center of the three given circles are collinear (see Fig.6).

In the very special situation, when centers of the three circles are collinear and

having equal radii, simply the common tangent lines give the points of contact.

After deﬁning the touching points at each inner circle, the ﬁrst and last circles in the

sequence have to be handled as well. Touching points to these two circles can also be

deﬁned by the common external tangent lines of the ﬁrst two and the last two circles,

respectively.

3.2. Separation to left and right group

Finally two points have been localized at the circles ciwhich all satisfy the last

requirement of Deﬁnition 2. The next step is to separate them for ”left” and ”right”

classes, i.e. to identify which one should be denoted by piand which one by ¯

pi.

At ﬁrst it is proved in (M¨

uller and Krames,1928) that these points of cican always

be separated by the circle with radical center rias center and intersecting orthogonally

the given three circles ci−1,ciand ci+1. Moreover it is mentioned that the radical center

7

Figure 6: Given three circles ci−1,ciand ci+1in admissible conﬁguration, one can ﬁnd the future points of

contact for skinning at ciby the two special solutions of the problem of Apollonius. The three possible

situations: one circle touching externally and another one touching internally by all the three given ones

(upper left); two circles touching externally (upper right); and two circles touching internally (middle).

Radical center and touching points are collinear.

and the two touching points are collinear. Thus the separation can easily be computed

by the following steps (see notations of Fig. 7): if the vector oi−1oican be rotated to

the direction of vector oi−1oi+1by a positive angle (in counterclockwise direction, with

less than 180◦) then the touching point being closer to the radical center riwill be in

the left group, i.e. will be denoted by pi. If the direction of rotation is opposite (as it

is for the next circle in Fig. 7) then the touching point closer to the radical center ri+1

is in the right group: ¯

pi+1. Special attention must pay to the ﬁrst and last circle as well

as for circles with collinear centers. In these cases the vector oi−1oiis rotated to the

direction of oi−1piand the angle is similarly measured and evaluated as above.

3.3. Deﬁnition of tangent vectors

Finally we have two groups of well deﬁned touching points on the circles. Between

each pair of points Hermite interpolation curve will be computed at each group, sepa-

rately. To these arcs, one has to deﬁne the length of the tangent vectors at these points

(the direction of the tangents is inherited from the actual circle). In Slabaugh’s method

the length of the tangent vectors was a simple function of the radius of the current

circle. This method works well if there is no large diﬀerence between the radii and

the distance of the consecutive circles. Contrary to that method we specify the length

of the tangent in a way that the radii and the distance of the circles, as signiﬁcant in-

formation, are also incorporated. The radical line of two circles provides information

about the radii and the distance of the circles as well. Thus we use this line to obtain

8

Figure 7: Grouping of the constructed touching points into two groups, ”left” and ”right” (green and blue).

Detailed explanation can be found in the text.

uniﬁed information about the positions and size of the circles. For two consecutive

circles and touching points piand pi+1the distance of these points to the radical line

are computed, and the lengths of the tangent vectors at these points are settled to be

twice of these distances.

Figure 8: Deﬁnition of tangent vectors at the touching points by the help of radical line ri

3.4. Construction of the skin

Our ﬁnal step is to construct the curve which is now a simple interpolation problem

for given points piand tangent vectors vi. At this point it is irrelevant that these data

are computed from a set of circles, so we have to emphasize that other interpolation

9

methods may work as well as our choice, the Hermite interpolation. We deﬁne a cubic

curve q(t), t∈[0,1], where

q(0) =pi,q(1) =pi+1,q0(0) =vi,q0(1) =vi+1,

and q(t)=H3

0(t)q(0) +H3

1(t)q(1) +H3

2(t)q0(0) +H3

3(t)q0(1),t∈[0,1],

where

H3

0(t)=2t3−3t2+1

H3

1(t)=−2t3+3t2

H3

2(t)=t3−2t2+t

H3

3(t)=t3−t2.

The Hermite interpolation arcs computed from these data serve as a G1continuous skin

of the given circles. Results can be seen in Fig. 9, comparison to Slabaugh’s method is

in Fig. 4 and Fig. 10.

Figure 9: Results of the proposed method. It works for rather complicated data sets and gives correct result

in the simplest case as well.

4. Extension to spheres

As aforesaid, we can deﬁne the problem in larger dimensions, too. Given an or-

dered set of (hyper)spheres, we are looking for a skinning (hyper)surface with similar

properties as it had in 2D. Deﬁnition 1 of admissible conﬁguration of circles can di-

rectly be applied to spheres. The deﬁnition of skin is however, diﬀerent from the one

given in Def. 2. We would like to obtain a G1continuous surface, which touches each

sphere along a circle, that is tangent to the spheres.

Deﬁnition 3. Given an admissible conﬁguration of spheres C={s1,s2,s3, . . . , sn}, we

are looking for a G1continuous surface s(φ, t) called skin of the given spheres satisfying

the following requirements:

10

Figure 10: Comparison of Slabaugh’s method (left) and the proposed method (right). Note the diﬀerence in

the zoomed part below.

•There is a circle of contact (touching circle) cifor all i=1, ..., nsuch that the

skin s(φ, t) and sphere sihave common tangent planes at each point of ci. Circle

ciis an isoparametric curve of s(φ, t)

•ci1

n

[

j=1,j,i

dj,i∈ {1,2, . . . , n}.

We have to emphasize again that, due to the last restriction, circle of contact on the

actual sphere is required to be out of other spheres, which is a natural condition for

skinning from our point of view.

Steps of our solution are analogous to that ones applied in the planar case.

First of all, we have to localize the touching circles with centers ˜

oiand radii ˜

Ri

(i=1,...,n). For this step we can invoke the solution of the planar problem. Let us

consider a sphere si, where i=2, . . . , n−1, that is we exclude the ﬁrst and the last

spheres for a moment (Fig.11). Now consider the plane Pi, determined by the centers

oi−1,oi,oi+1of the considered sphere and its neighbours. Intersecting the spheres by

this plane we obtain three circles. With the help of the above mentioned planar method

with Apollonius circles, we can ﬁnd two points in the middle circle. There exists

exactly one plane Ti(i=2, . . . , n−1), which passes through these two points and

orthogonal to plane Pi. The intersection of sphere siand this orthogonal plane Tiis the

touching circle for the future skinning surface. We can localize a circle by this method

on every sphere, which has two neighbours.

The Appollonius problem itself can also be generalized in 3D, where touching

spheres of three given spheres have to be found. The envelope of these spheres is the

Dupin cyclide, which surface is widely used in CAGD (for an overview, see (Farin et al.,2002;

11

Figure 11: Touching circle localization on the sphere si, where i,1,n.Ti⊥Pi, where Tiis the plane of

the touching circle and Piis the plane passing through the centers. Dashed line shows Apollonius circles

as solution of the planar problem in Pi. Note that in general the touching circle is not a main circle of the

sphere si

Figure 12: Construction of touching circle on s1

Pratt,1990; Pratt,1995)). The touching circle we constructed now is identical to the one

in which the Dupin cyclide deﬁned by the three given spheres si−1,si,si+1touches the

sphere si.

Touching circles for the ﬁrst and the last spheres have to be deﬁned in a diﬀerent

way. Let us consider the ﬁrst and the second spheres and the regular cone which touches

both spheres. The touching circle of this cone on the ﬁrst sphere will be the circle for

the skinning surface as well (Fig. 12). Circle on the last sphere is deﬁned analogously.

It directly follows from the planar construction, that this method always works in

every admissible case.

Now we obtained touching circle with center ˜

oiand radius ˜

Rion each sphere, thus

we can start to create the skin, following the ideas developed in the planar case: patches

are deﬁned successively to each pair of spheres using Hermite interpolants through

corresponding points of the touching circles.

Consider the future patch si(φ, t) of the skin between touching circle cion sphere

siand touching circle ci+1on sphere si+1. Circle ciis the isoparametric curve si(φ, 0),

while ci+1is the isoparametric curve si(φ, 1) of this patch. At ﬁrst we will deﬁne the

12

starting point on cias zi=si(0,0) and on ci+1as zi+1=si(0,1), then rotating them

by the same angle φalong the circles, corresponding pairs of points zφ

i=si(φ, 0),

zφ

i+1=si(φ, 1) will be deﬁned. Lengths of tangent vectors are computed by the help of

the radical plane of the two spheres. Lines of all the tangents pass through the pole wi

of the plane of the touching circle with respect to the sphere si(i=1, . . . , n), see Fig.

13. To avoid unnecessary torsion, corresponding points are selected by the help of a

ﬁxed spatial direction e(which can be e.g. the direction of the zaxis, not parallel to

any of the vectors wi−˜

oi).

Figure 13: Computation of tangent lengths is analogous to the spatial case, using radical plane Mi. Corre-

sponding points ziand zi+1are connected by isoparametric curve of the skin surface.

Let s: → {−1,1}and p: {si} → {−1,1}be functions deﬁned by

s(x)=

−1 if x<0,

1 else

p(si)=

sD wi−oi

kwi−oik,oi+1−oi

koi+1−oikE if i,n,

sD wi−oi

kwi−oik,oi−oi−1

koi−oi−1kE else

where h,iis the standard inner product.

Figure 14: Result of the proposed algorithm. This data set has also been used by Slabaugh in

(Slabaugh etal.,2009), but, contrary to our algorithm, symmetric data set does not necessarily yield sym-

metric skin with Slabaugh’ method

13

Figure 15: A complex data set and its skin produced by the proposed algorithm. Note, that centers of spheres

are not coplanar.

Let ebe a ﬁxed direction, e∦(wi−˜

oi), and let zibe deﬁned by

zi=˜

oi+˜

Ri·e×p(si)·(wi−˜

oi)

e×p(si)·(wi−˜

oi)

(i=1,2, . . . , n).

Further corresponding points zφ

iof the touching circles are deﬁned by rotating ziby

angle φaround the line passing through ˜

oiand having direction p(si)·(wi−˜

oi).

Let Mibe the radical plane of sphere siand si+1. We build our skinning surface up

from n−1 patches, where the ith patch is deﬁned as:

si(φ, t)=H3

0(t)zφ

i+H3

1(t)zφ

i+1+

H3

2(t)·p(si)·2·d(Mi,zφ

i)·wi−zφ

i

wi−zφ

i

+

H3

3(t)·p(si+1)·2·d(Mi,zφ

i+1)·wi+1−zφ

i+1

wi+1−zφ

i+1

t∈[0,1], φ ∈[0,2π],i=1, . . . , n−1

where d is the Euclidean distance function and H3

iare the cubic Hermite-polynomials.

Results of the algorithm can be seen in Figure 14, 15 and 16.

5. Conclusion

An algorithm for skinning circles and spheres has been presented in the paper. Con-

trary to other approaches, our method works for large class of data sets, and it is proved

that for any admissible conﬁguration the skin exists, however it does not minimize en-

ergy function and have only G1continuity. Applying classical tools from constructive

geometry, our method is robust and fast with real-time computing speed. Even if one

may wish to numerically minimize energy functions such as in Slabaugh’s work, the

presented skin can be applied as initialization of the iterative process, avoiding trivial

faults, local minima and consuming computation. Our technique provides a curve or

surface which can be modiﬁed in real time, and the shape is sensitive for the change of

radii and positions of the data set as well. Since the crucial point of the algorithm is

14

to ﬁnd suitable touching points or touching circles, and it is independent of the current

interpolation method, extension of the algorithm using other types of surfaces can be a

future direction of research. Further improvements can be higher order continuity and

avoiding unnecessary intersection of the skin and the data set.

References

[Cheng and Shi,2005] Cheng, H., Shi, X., 2005. Quality mesh generation for molecu-

lar skin surfaces using restricted union of balls. Proc. IEEE Visualization Confer-

ence (VIS2005), 399–405.

[Coaklay,1860] Coaklay, G. W., 1860. Analytical Solutions of the Ten Problems in

the Tangencies of Circles; and also of the Fifteen Problems in the Tangencies of

Spheres. The Mathematical Monthly 2, 116–126

[Edelsbrunner,1999] Edelsbrunner, H., 1999. Deformable smooth surface design. Dis-

crete and Computational Geometry 21, 87–115.

[Farin,1997] Farin, G., 1997. Curves and Surface for Computer-Aided Geometric De-

sign, 4th edition, Academic Press, New York.

[Farin et al.,2002] Farin, G., Hoschek, J., Kim, M-S., 2002. Handbook of computer

aided geometric design, Elsevier.

[Hoschek,1964] Hoschek, J., 1964. Zur Ermittlung von H¨

ullgebilden in der Kine-

matik, PhD thesis, TH Darmstadt.

[Hoschek and Lasser,1993] Hoschek, J., Lasser, D., 1993. Fundamentals of CAGD,

AK Peters, Wellesley, MA.

[Hoﬀmann and Juh´

asz,2008] Hoﬀmann, M., Juh´

asz, I., 2008. On interpolation by

spline curves with shape parameters. Lecture Notes in Computer Science 4975,

205–215.

[Kruithof and Vegter,2006] Kruithof, N., Vegter, G., 2006. Envelope Surfaces. Proc.

Annual Symposium on Computational Geometry, 411–421.

[Monge,1850] Monge, G., 1850. Application de l’analyse `

a la g´

eom´

etrie, Bachelier,

Paris, 1850.

[M¨

uller and Krames,1928] M¨

uller, E., Krames, J.L. (ed.), 1929. Vorlesungen ¨

uber

Darstellende Geometrie II: Die Zyklographie. Deuticke, Leipzig u. Wien, 1928.

[Muirhead,1896] Muirhead, R.F., 1896. On the Number and Nature of the Solutions

of the Apollonian Contact Problem. Proceedings of the Edinburgh Mathematical

Society 14, 135-147.

[Peternell et al.,2008] Peternell, M., Odehnal, B., Sampoli, M.L., 2008. On quadratic

two-parameter families of spheres and their envelopes. Computer Aided Geomet-

ric Design 25, 342–355.

15

[Piegl and Tiller,1995] Piegl, L., Tiller, W., 1995. The NURBS book,Springer–Verlag,

Berlin.

[Pratt,1990] Pratt, M.J., 1990. Cyclides in computer aided geometric design. Com-

puter Aided Geometric Design 7, 221–242.

[Pratt,1995] Pratt, M.J., 1995. Cyclides in computer aided geometric design II. Com-

puter Aided Geometric Design 12, 131–152.

[Singh and Kokkevis,2000] Singh, K., Kokkevis, E., 2000. Skinning characters using

surface oriented free-form deformations, in: Graphics Interface, pp.35-42.

[Slabaugh et al.,2008] Slabaugh, G., Unal, G., Fang, T., Rossignac, J., Whited, B.,

2008. Variational Skinning of an Ordered Set of Discrete 2D Balls. Lecture Notes

on Computer Science 4795, 450–461.

[Slabaugh et al.,2009] Slabaugh, G., Rossignac, J., Whited, B., Fang, T., Unal, G.,

2009. 3D Ball Skinning using PDEs for Generation of Smooth Tubular Surfaces.

Computer-Aided Design (to appear).

[Whited et al.,2007] Whited, B., Rossignac, J., Slabaugh, G., Fang, T., Unal, G.,2007.

Pearling: 3D interactive extraction of tubular structures from volumetric images.

In: Interaction in Medical Image Analysis and Visualization, held in conjunction

with MICCAI. 2007.

16

Figure 16: The algorithm can handle distant spheres as well as sudden changes in size. Note that the upper

part of the stomach or the neck of the vase cannot be modeled by main circles as touching circles.

17