Technical Report 2009-001

Distance to set operations in constructive modeling ofsolidsPierre-Alain Fayolle
August 19, 2009

Computer Graphics Laboratory
The University of Aizu
Tsuruga, Ikki-Machi, Aizu-Wakamatsu City
Fukushima, 965-8580 Japan

Technical Report 2009-001
Title:
Distance to set operations in constructive modeling of solids

Authors:
Pierre-Alain Fayolle
Key Words and Phrases:
implicit surfaces, distance function, constructive modeling, set operations

Abstract:
We propose in this paper methods to compute the signed distance to surface obtained by theintersection (respectively union, difference) of two solids (in two and three dimensions). These
implementations can replace “min/max” or “R-functions” used to model set operations on
implicit surfaces.

Report Date:
8/19/2009

Written Language:
EnglishAny Other Identifying Information of this Report:

Distribution Statement:
First Issue: 10 copies

Supplementary Notes:

Computer Graphics Laboratory
The University of Aizu
Aizu-Wakamatsu
Fukushima 965-8580
JapanDistance to set operations in constructive modelingof solids
Pierre-Alain Fayolle
08/04/2009

Contents
1 Introduction
1.1 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 The distance function . . . . . . . . . . . . . . . . . .
1.1.2 Constructive geometry with real valued functions . . .
1.2 Overview and main contributions . . . . . . . . . . . . . . . .

2
2
2
3
4

2 Construction of the intersection in two dimensions
2.1 Intersection to two orthogonal halfspaces . . . . . . . . . . . .
2.2 Determination of the space where min does not give the exact
distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Determination of the closest point . . . . . . . . . . . . . . .
2.4 Distance to the intersection . . . . . . . . . . . . . . . . . . .
2.5 Extension to union and difference . . . . . . . . . . . . . . . .

45

3 Construction of the intersection in three dimensions
3.1 Determination of the closest point . . . . . . . . . . . . . . .
3.2 Distance to the intersection . . . . . . . . . . . . . . . . . . .

8894 Results and discussions
4.1 Visualization of distance fields . . . . . . . . . . . . . . . . . .
4.1.1 Contour field in two dimensions . . . . . . . . . . . . .
4.1.2 Contour field on planar section in three dimensions . .
4.1.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . .

9
9
10
10
11

5 Conclusion

13

Abstract
We propose in this paper methods to compute the signed distanceto surface obtained by the intersection (respectively union, difference)of two solids (in two and three dimensions). These implementations
can replace “min/max” or “R-functions” used to model set operations
on implicit surfaces.

1

5
6
7
8

1

Introduction

In geometric modeling, a solid can be defined by the sign of a function:
the set {p : f (p) ≥ 0} defines the interior and the boundary, and the set{p : f (p) < 0} the exterior (see [4] on implicit surfaces, [1] on Function
Representation and the references therein). The case where f is the signed
Euclidean distance to the boundary of the solid f = 0 is of special interest.
Distance based models are extremely useful in many applications such as:
constant-radius offsetting and blending operations [16], surface metamorphosis and smoothing [13], object reconstruction from a set of cross-sections[10], rendering with sphere tracing [6], generation of skeletal shape representation [23], heterogeneous object modeling [3], and others. We propose
in this paper methods for calculating the signed Euclidean distance froma point to the surface of a solid constructed by applying set-theoretic operations (union, intersection, difference) to primitives defined by distancefunctions. That is: if d1 and d2 represent the distance to the surface of two
primitives S1 and S2 , we propose algorithms to calculate the distance d tothe union (respectively intersection, difference) of S 1 and S2 .

1.1

Related works

1.1.1

The distance function

Let d(p), p ∈ R3 be the signed distance function to an oriented closed
surface M . The function d is the vanishing viscosity solution of the Eikonal
equation [22, 21, 19]:k∇dk2 = 1, d|M = 0(1)
where k.k2 is the Euclidean norm. Let c be the closest point of p in thesurface M , the signed distance is then kp − ck 2 , where  = −1 if p is
outside M . If the surface is smooth, then p − c is orthogonal to the surface.
The signed Euclidean distance function is at least C 0 , and may be notdifferentiable at some points.
Expressions for the distance function to most of the classic surfaces of a
CSG system (sphere, cylinder, cone) are known analytically [6] and distanceto general quadrics and ellipsoids can be computed by a numerical procedure[7].
In general, if the surface M is available as an oriented point-set or a meshof polygons, it is possible to solve the Eikonal equation (1) on a finite grid.
There exists various optimal numerical algorithms such as the fast marching
method [19], the fast sweeping method [21, 22], or the characteristics / scanconversion algorithm [11]. Algorithms, that exploit the GPU, have also been
designed in order to compute efficiently the Euclidean distance function[8, 20]. After a grid is obtained with the signed Euclidean distance to M

2

in each of its nodes, it is always possible to apply spline interpolation /approximation, to get an analytical expression [15].
1.1.2

Constructive geometry with real valued functions

In constructive geometry, complex solids are built by applying successively
set-theoretic operations (union, intersection, difference) to primitives. Whensolids are described by real valued functions, like in implicit surfaces or FRep, expressions for set-theoretic operations have been proposed by Sabin[18], Ricci [14] and Rvachev [17]. Sabin [18] and Ricci [14], independently
proposed the use of “min/max”. If d1 and d2 are the functions defining
two solids, then the union is defined by the function max(d 1 , d2 and theintersection by min(d1 , d2 ) (the difference is obtained from the intersection
by replacing d2 by −d2 ). Rvachev proposed the “R-functions” [17]:1(d1 + d2 +d1 ∨α d2 = 1+α1(d1 + d2 −d1 ∧α d2 = 1+αqd2 + d22 − 2αd1 d2 )

q 1

(2)

d21 + d22 − 2αd1 d2 )Neither ”min/max” nor the R-functions keep the distance to the constructed solid. This is illustrated in Fig. 1, where the approximate distanceto the surface made by the intersection of the halfspaces: x ≥ 0 and y ≥ 0
is computed with an ”R-function” on the left and ”min” on the right.
2

2

1.5

1.5

1

1

0.5

0.5

0

0

−0.5

−0.5

−1

−1

−1.5

−1.5

−2
−2

−1.5

−1

−0.5

0

0.5

1

1.5

−2
−2

2

−1.5

−1

−0.5

0

0.5

1

1.5

Figure 1: Approximate distance to the intersection of the halfspaces x ≥ 0
and y ≥ 0. Left: R-function is used to implement the intersection. Right:
Min is used.
”Min/max” tend however to keep a better approximation of the distancethan the ”R-functions”. This can be illustrated by computing the union ofa disk with itself and looking at the value of the function (union of thedisks) at the center.
p The distance to a circle of radius 1 and center [0, 0]
is: d(p) = 1.0 − p2 , and the union of the disk with itself is defined by:3

2

max(d(p), d(p)) or: d(p) ∨0 d(p). In the former case, the distance at thecenter is: 1.0 while in the latter it is: 3.41421.
The functions “min/max” are not differentiable on the set of points corresponding to the equality of their arguments. Because of this, “R-functions”
are sometimes preferred; ”R-functions” are not differentiable only on the setof points where their arguments are both equal to 0. This property of the“R-functions” is used for example when implementing a blending effect [12].
Some works tried to address this issue by modifying the contour lines ofthe functions min(x, y) and max(x, y): functions proposed in the work [9, 2]
were designed for blending, while [5] were designed for keeping the distanceapproximation of ”min/max” while removing the points where the function
is not C 1 .

1.2

Overview and main contributions

The main contributions of this paper are methods to compute in two andthree dimensions the distance to solids defined by the union (respectively
intersection, difference) of solids defined by distance functions. That is: if S 1
and S2 are solids defined by the distance functions d 1 and d2 , we describe
methods to compute d the signed distance to S = S 1 ∪ S2 (respectively
S1 ∩ S2 and S1 \S2 ). These expressions for the set-theoretic operations canbe used instead of ”min/max” or the ”R-functions” in implicit surfaces or
F-Rep modeling systems.
Union and intersection are dual, and the difference is obtained from theintersection, so we will limit the discussion to the construction of an expression for the intersection. We first describe the method in two dimensions,when d1 and d2 are functions in R2 . Then, we explain how to modify themethod for the three dimensional case. Finally, we illustrate through examples in two and three dimensions the behavior of these functions and how
they compare against ”min/max” or ”R-functions”.

2

Construction of the intersection in two dimensions

In this section, we describe how to get an expression for computing theintersection of two shapes defined by signed distance functions. We start byan example: the intersection of two orthogonal halfspaces x ≥ 0 and y ≥ 0(as illustrated in Fig. 1), and explain how the scalar field constructed bymin(x, y) differs from the signed distance to the intersection. We generalize
the method to the intersection of any objects defined by their signed distancefields: d1 (x, y) and d2 (x, y).

4

2.1

Intersection to two orthogonal halfspaces

Let us consider the example used for Fig. 1: two halfspaces are defined byx ≥ 0 and y ≥ 0. The set of points satisfying min(x, y) ≥ 0 forms theintersection of the two halfspaces, and the points such that min(x, y) = 0
defines the boundary (which looks like an ’L’). Fig. 2 (left) illustrates some
contour lines of the distance field to the previous boundary. The distancefield is signed such that points inside the intersection of the halfspaces are
positive and points outside are negative. For comparison, Fig. 2 (right)
shows some contour lines of min(x, y).
2

2

1.5

1.5

1

1

0.5

0.5

0

0

−0.5

−0.5

−1

−1

−1.5

−1.5

−2
−2

−1.5

−1

−0.5

0

0.5

1

1.5

−2
−2

2

−1.5

−1

−0.5

0

0.5

1

1.5

Figure 2: Left: contour lines for the exact distance to the boundary of theintersection of two halfspaces x ≥ 0 and y ≥ 0. Right: contour lines of thescalar field min(x, y). Contour lines are from −1.5 to 1.5 with step of 0.5.
As it can be seen in Fig. 2, min gives the exact distance field everywhere
except the space defined by: x < 0 and y < 0 (let us call that space Q).
In that space, the closest point on the boundary is the point defined by theintersection of the two lines x = 0 and y = 0, and the contour lines are
circular arcs centered at this intersection point.
We need now to define Q for any general shapes to be intersected andthen explain how to compute the closest point on the surface in that space.

2.2

Determination of the space where min does not give theexact distanceFig. 3 illustrates the case of the local intersection of two general (non orthogonal) curves intersecting at the point O. The boundary (d = 0), one
contour line (d = −1.0) and the normals to each curve at O are plotted.
If the closest intersection point is known, then the region of interest canbe identified using the normal to each curve at the intersection point asseen Fig. 3. However, it requires to first compute the set of all intersection
points, which is not easy.
5

2

2
1.5
1
0.5
0
−0.5
−1
−1.5
−2
−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

Figure 3: Local intersection of two general curves. Curve resulting of theintersection, one contour line at the distance −1.0 and the normals to eachcurve at the intersection point.

We will proceed in the reverse way by first determining the space ofinterest and then computing the closest intersection point in that space.
Given a point p ∈ R2 (see as an illustration Fig. 4), we first calculates
the projection p1 of p on the first curve c1 . Using the signed distance fieldd1 to the curve and its gradient, the projection is given by:
p1 ← p − d1 (p)∇d1 (p)(3)

Similarly, we calculate p2 the projection of p on the second curve c 2 .
p belongs to the zone of interest Q, if d 1 (p2 ) < 0 and d2 (p1 ) < 0.

2.3

Determination of the closest point

If the current point of evaluation p 0 is in Q, then the next step is to computeits closest point p on the boundary of the intersection. The closest point is
at the intersection of the two curves:
L(p) ="

d1 (p) = 0
d2 (p) = 0#(4)This system is solved for p = (x, y) by using the damped Newton methodwith the initial guess p0 . Eq. 5 is iterated until the residual L(p k ) is small,and p is set to pk .
6

Figure 4: Two curves c1 and c2 (solid lines) defined by the distance fields d 1and d2 . A given point p and the contour lines of d 1 and d2 passing throughp. p1 and p2 the projections of p on c1 and c2 .

pk+1 = pk − αJ −1 (pk )L(pk )(5)where α is the damping factor, and J is the Jacobian matrix of L.
J(p) =∂d1∂x (p)∂d2∂x (p)∂d1∂y (p)∂d2∂y (p)!

(6)

Because p0 is close to p, pk converges relatively fast.

2.4

Distance to the intersection

Putting together the results of the previous subsections, a procedure forcalculating the distance to the intersection of two curves defined by thesigned distance functions is:
distInter Given a point p ∈ R 2 , and two (2D) solids defined by the signed
distance functions d1 ≥ 0 and d2 ≥ 0, compute the distance to the curve,
boundary of the intersection of the two solids.
1. [distance to curve 1] d1 = d1 (p)2. [distance to curve 2] d2 = d2 (p)3. [normal to d1 ] n1 = ∇d1 (p)4. [projection on curve 1] p1 = p − d1 n1
7

5. [normal to d2 ] n2 = ∇d2 (p)6. [projection on curve 2] p2 = p − d2 n2
7. [in Q?] inQ? = d1 (p2 ) < 0 AND d2 (p1 ) < 0
8. if (inQ? is true) then:(a) [closest point] pc = closestInter(p, d1 (.), d2 (.)) (see section 2.3)(b) [distance] d = −kp − pc k2

9. else:(a) [distance] d = min(d1 , d2 )10. [return] return d

2.5

Extension to union and difference

The distance to the union is similar except for:• the section 2.2 (step 7 of the algorithm distInter in section 2.4), where
the condition d1 (p2 ) < 0 AND d2 (p1 ) < 0 should be replaced by thecondition d1 (p2 ) > 0 AND d2 (p1 ) > 0,
• the step 8.b) of the algorithm distInter in section 2.4, which should be
replaced by: d = kp − pc k2 .
The distance to the set-theoretic difference is obtained by replacing thefunction d2 (.) by the function −d2 (.) in the algorithm distInter.
In the following section, we extend the method for working with three
dimensional objects.

3

Construction of the intersection in three dimensions

The construction of the distance to the intersection in three dimensions issimilar to the two dimensional case. The only difference is in determining
the closest intersection point.

3.1

Determination of the closest point

In three dimensions, the system in eq. 4 has three unknowns (x, y and z)
but only two equations. The third equation is obtained by observing thatthe closest intersection point is in the plane containing the gradient of eachfunction at the current point of evaluation (p 0 ). Let n1 = ∇d1 (p0 ) andn2 = ∇d2 (p0 ) be the gradients of d1 and d2 at p0 . The third equation
becomes: n(p − p0 ) = 0, where n = n1 ∧ n2 . We have to solve the following
system:d1 (p) = 0(7)L(p) =  d2 (p) = 0n(p − p0 ) = 0
8

This is solved with the damped Newton method as in section 2.3. The
Jacobian of the system eq. 7 is:∂x (p)∂d2∂x (p)1∂d1∂y (p)∂d2∂y (p)

nx

ny

 ∂d

J(p) = ∂d1∂z (p)∂d2∂z (p) (8)nz

where nx , ny and nz are the components of n.

3.2

Distance to the intersection

Putting together the results of the previous subsections, a procedure forcalculating the distance to the intersection of two surfaces defined by signed
distance functions is:
distInter3D Given a point p ∈ R 3 , and two (3D) solids defined by thesigned distance functions d1 ≥ 0 and d2 ≥ 0, compute the distance to thesurface, boundary of the intersection of the two solids.
1. [distance to surface 1] d1 = d1 (p)2. [distance to surface 2] d2 = d2 (p)3. [normal to d1 ] n1 = ∇d1 (p)4. [projection on surface 1] p1 = p − d1 n1
5. [normal to d2 ] n2 = ∇d2 (p)6. [projection on surface 2] p2 = p − d2 n2
7. [in Q?] inQ? = d1 (p2 ) < 0 AND d2 (p1 ) < 0
8. if (inQ? is true) then:(a) [closest point] pc = closestInter3D(p, d1 (.), d2 (.)) (see section
3.1)(b) [distance] d = −kp − pc k2

9. else:(a) [distance] d = min(d1 , d2 )10. [return] return d

4

Results and discussions

4.1

Visualization of distance fields

The distance field to the intersection and union of two solids is illustrated
in two and three dimensions in the following examples.

94.1.1

Contour field in two dimensions

Fig. 5 illustrates the contour field of the signed distance functions resulting
in the intersection of two non-orthogonal planes and two disks. Intersection
was implemented using: “R-functions” (left), “min/max” (middle) and themethod proposed in this paper. The functions built using “R-functions”
do not respect the Euclidean metric. The functions built using “min/max”
failed to do so only in the space identified in section 2.2. Compare the resultswith the method proposed here and the circular arcs in the contour lines
outside of the constructed solids.
2

0.5
0

1.5

2

1

2

1

1.5

0.5

1.5

0.5

1

0

−0.5
1

1

0

−1
0.5

−1.5

0

−2
−2.5

−0.5

−3

−1

0.5

−0.5

0

−2
−2

−4
−1.5

−1

−0.5

0

0.5

1

1.5

−0.5

2

0

1.5

−1

1

−1

−0.5

−1.5

−1.5
−1

−1

−2

−2
−1.5

−1.5

−2.5

−2.5
−2
−2

2

−0.5

0
−1

−3.5
−1.5

0.5

−1.5

−1

−0.5

0

0.5

1

1.5

−2
−2

2

2

0

1.5

−1.5

−1

−0.5

0

0.5

1

1.5

2

2

0

1.5
−0.5

1

−0.5

1

−2
0.5

0.5
−3

0
−0.5

−4

0.5
−1

−1

0

0

−0.5

−0.5
−1.5

−1

−5

−1.5

−1
−1.5

−2

−6
−2
−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

−2
−2

−1.5
−1

−1.5

−1

−0.5

0

0.5

1

1.5

2

−1.5
−2
−2

−2
−1.5

−1

−0.5

0

0.5

1

1.5

2

Figure 5: First row: Intersection of two halfplanes using for the intersection(from left to right): “R-functions”, “min”, the method proposed in thiswork. Second row: Intersection of two disks.
Fig. 6 illustrates the contour field of the distance to the union of two
halfplanes (left) and two disks (right) using the method introduced here.
4.1.2

Contour field on planar section in three dimensions

Visualizing scalar fields in three dimensions is more difficult. We visualize
instead the fields in a planar section. Fig. 7 (right) illustrates the proposed method applied in three dimensions to compute the distance to theintersection of two spheres. This should be compared with the sections in
fig. 7 left and middle obtained with respectively “R-functions” and “min”.
Additionally, fig. 8 illustrates the result of the proposed method to computethe distance to the union of two spheres by showing the distance field on asection by the plane y = 0.

10

2

2.5

2

1.5

2

1.5

1

1.5

0.5

1

0

0.5

1

0

0.5
0

−0.5

0.5
−0.5

−0.5
0

−1

−1

−1

−0.5
−1.5
−2
−2

−1.5
−1
−1.5

−1

−0.5

0

0.5

1

1.5

2

−2
−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

Figure 6: Left: distance to the union of two halfplanes with our method.
Right: distance to the union of two disks.

Figure 7: Distance to the intersection of two spheres using for the intersection (from left to right): “R-functions”, “min”, the method proposed in thiswork. Second row: Intersection of two disks.

4.1.3

Discussion

As mentioned earlier, the distance function is at least C 0 but not everywhere differentiable; for example, the sphere is not differentiable at its
center. Our algorithms, as described above, make use of the gradient of thefunctions passed as input. The question is what value of the gradient to use
in these cases. The points where the distance function is not differentiable
have more than one closest point on the surface of the solid, and therefore
more than one gradient at that point. The easiest solution is to consistently
pick one gradient from the set of possible gradients. This is the solutionthat was used for the intersection / union of the disks and spheres in theexamples above.
An alternative solution is to use slightly modified versions of “min” and“max” that are C 1 . In the case of “min”, it is done by rewriting it as:2
min(d1 , d2 ) = 21 (d1 + d2 + √(d1 −d2 ) 2 ) and adding a small perturbation :(d1 −d2 )

11

−1.5

Figure 8: Distance to the union of two spheres with our method.

2(d1 −d2 )1˜min(d1 , d2 ) = 2 (d1 + d2 + √2(d1 −d2 ) +). This function has the advantage

of being C 1 but it is also slightly displacing each iso-contour; for example,(−d2 )21
˜) < 0 instead ofif d1 = 0 and d2 > 0, then min(d1 , d2 ) = 2 (d2 + √2(−d2 ) +min(d1 , d2 ) = 0.
Successive applications of set operations It is possible to successively
apply the proposed implementation of intersection, union or difference tosolids built with these operations. The gradient of the arguments is needed,which means the gradient of the function p → intersection(d 1 (p), d2(p))(respectively union, difference) needs to be calculated. The expression of
the intersection is not differentiable for the point-set: {p : p ∈/ Q ∧ d 1 (p) =d2 (p)}. This set corresponds to the points with more than one gradient. As
discussed previously, it is possible to select consistently one of them and use
it as the gradient at that point for the purpose of our algorithm.
The expressions of the set operations proposed here are slower than “min/max”
or “R-functions”. The bottleneck is the loop computing the closest intersection point in Q and the distance to it (step 8 in distInter and distInter3D).
All the functions have been implemented in Matlab R . With this implementation, evaluation of the (2D) intersection on a 400 × 400 grid takes
0.4 seconds against 0.03 for the “r-function”. For a 40 × 40 × 40 grid, the(3D) intersection takes the same time (0.4 seconds) against 0.015 for the“r-function”.

125

Conclusion

We have presented in this work functions in two and three dimensions that
implement the distance to set operations (intersection, union or difference).
Contrary to the existing implementations (“min/max”, “R-functions”), theproposed implementations correspond to the exact distance function to theresulting shape. The use of these functions should allow to implement easily
rolling blend.

References[1] Pasko A., Adzhiev V., Sourin A., and Savchenko V. Function representation in geometric modeling: concepts, implementation and applications. The Visual Computer, 8(11):429–446, 1995.
[2] L. Barthe, N. A. Dodgson, M. A. Sabin, B. Wyvill, and V. Gaildrat.
Two-dimensional potential fields for advanced implicit modeling operators. Computer Graphics Forum, 22(1):23–33, 2003.
[3] Arpan Biswas, Vadim Shapiro, and Igor Tsukanov. Heterogeneousmaterial modeling with distance fields. Comput. Aided Geom. Des.,
21(3):215–242, 2004.
[4] Jules Bloomenthal, editor. Introduction to Implicit Surfaces. MorganKaufmann, 1997.
[5] P.-A. Fayolle, A. Pasko, B. Schmitt, and N. Mirenkov. Constructive
heterogeneous object modeling using signed approximate real distancefunctions. Journal of Computing and Information Science in Engineering, 6(3):221–229, 2006.
[6] J. Hart. Sphere tracing: A geometric method for the antialiased ray
tracing of implicit surfaces. The Visual Computer, 12(10):527–545,
1996.
[7] John C. Hart. Distance to an ellipsoid. In Paul Heckbert, editor,
Graphics Gems IV, pages 113–119. Academic Press, Boston, 1994.
[8] K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Fast computation of generalized voronoi diagrams using graphics hardware. In
Proceedings of ACM SIGGRAPH, pages 277–286. ACM, 1999.
[9] P.-C. Hsu and C. Lee. The scale method for blending operations infunctionally-based constructive geometry. Computer Graphics Forum,22(2):143–158, 2003.

13

[10] M. Jones and M. Chen. A new approach to the construction of surfaces
from contour data. Computer Graphics Forum, 13(3):75–84, 1994.
[11] S. Mauch. Efficient Algorithms for Solving Static Hamilton-Jacobi
Equations. PhD thesis, California Institute of Technology, 2003.
[12] A. Pasko and V. Savchenko. Blending operations for the functionallybased constructive geometry. In set-theoretic Solid Modeling: Techniques and Applications, CSG 94 Conference Proceedings, pages 151–
161. Information Geometers, 1994.
[13] B. Payne and A. Toga. Distance field manipulation of surface models.
IEEE Computer Graphics and Applications, 12(1):65–71, 1992.
[14] A. Ricci. A constructive geometry for computer graphics. The Computer Journal, 16(2):157–160, 1973.
[15] C. Roessl, F. Zeilfelder, G. Nurnberger, and H.-P. Seidel. Spline approximation of general volumetric data. ACM Solid Modeling 2004,
2004.
[16] J. Rossignac and A. Requicha. Constant-radius blending in solid modeling. Computers in Mechanical Engineering, 3(1):65–73, 1984.
[17] V. Rvachev. Theory of R-functions and Some Applications. Naukova
Dumka, Kiev, 1982. In Russian.
[18] M. Sabin. The use of potential surfaces for numerical geometry. Technical Report VTO/MS/153, 1968.
[19] J. Sethian. Level-Set Methods and Fast Marching Methods. Cambridge
University Press, 1999.
[20] A. Sud, A. Otaduy, and D. Manocha. Difi: Fast 3d distance field computation using graphics hardware. Computer Graphics Forum, 23(3):557–
566, 2004. Proceedings of Eurographics 2004.
[21] Y.R. Tsai. Rapid and accurate computation of the distance function
using grids. J. Comput. Phys., 178(1):175–195, 2002.
[22] H. Zhao. A fast sweeping method for eikonal equations. Mathematics
of Computation, 2004.
[23] Y. Zhou, A. Kaufman, and A. Toga. 3d skeleton and centerline generation based on an approximate minimum distance field. The VisualComputer, 14(7):303–314, 1998.

14