-----Заголовок-----
Источник: http://picxxx.info
Ссылка на PDF: http://picxxx.info/pml.php?action=GETCONTENT&md5=23c829e74745daf16df83e55bf2eb83f
-----Конец заголовка-----
Exact envelope computation for moving surfaces
with quadratic support functions
Margot Oberneder1, Bert J¨uttler1 and Laureano Gonzalez-Vega2
1
Institute of Applied Geometry, Johannes Kepler University, Linz, Austria,
e-mail: {margot.oberneder, bert.juettler}@jku.at
2 Departamento de Matem´
aticas, Estad´ıstica y Computaci´on, Universidad de
Cantabria, Santander, Spain, e-mail: laureano.gonzalez@unican.es
Abstract. We consider surfaces whose support function is obtained by restricting a quadratic polynomial to the unit sphere. If such a surface is subject to a rigid body motion, then the Gauss image
of the characteristic curves is shown to be a spherical quartic curve, making them accessible to
exact geometric computation. In particular we analyze the case of moving surfaces of revolution.
Key words: envelope, characteristic curve, support function, parameterization
1 Introduction
Envelopes of moving surfaces are needed for computing the swept volume which is
traced out by a moving solid. They can be obtained by collecting the characteristic
curves, where the moving surface touches its envelope at a given time. In Robotics,
these computations are related to the problem of collision detection. Other applications include the numerical simulation of milling processes, where the tool can be
modeled as a surface of revolution.
[Abdel-Malek et al., 2006], give a detailed survey about swept volume computation with many related references. [Peternell et al., 2005], compute the boundary
of the swept volume generated by a general moving object, which is assumed to be
given as a triangular mesh. Special attention is paid to the choice of the time–step
for computing the characteristic curves.
Envelopes of certain specific classes of surfaces have been analyzed in more detail. [Flaquer et al., 1992], studied envelopes of moving quadric surfaces, in particular moving planes, spheres, cylinders and cones. In all these cases, the characteristic
curves are algebraic space curves of degree 4. [Xia and Ge, 2001], consider cylinders as an example for milling tools and generate an exact representation of the
boundary surface.
We discuss the case of surfaces which are specified by their support functions.
These surfaces can explicitly be parameterized by its inverse Gauss maps and we
use this observation to characterize the characteristic curves. The case of surfaces
with quadratic support functions is discussed in detail, since they allow the exact
1
Margot Oberneder1 , Bert J¨uttler1 and Laureano Gonzalez-Vega2
2
computation of the characteristic curves. General support functions can be approximated by surfaces with piecewise quadratic ones, which are defined over a given
spherical triangulation. This should make it possible to extend the results of this
paper to more general objects.
2 Support Functions
ˇ ır et al., 2008]).
We recall the support function representation of surfaces (see e.g. [S´
Consider a given function h ∈ C∞ (S2 , R), where S2 denotes the unit sphere in R3 .
We use this function to associate with each point n ∈ S2 the plane with the unit
normal n and oriented distance h(n) to the origin.
The envelope of the two–parameter family of planes obtained by varying n in
S2 describes a surface. The given function h is called the support function of this
surface. For any h ∈ C∞ (S2 , R), a parameterization xh ∈ C∞ (S2 , R) of the surface is
given by its inverse Gauss map,
xh (n) = h(n)n + (∇S2 h)(n),
(1)
where (∇S2 h) is the intrinsic gradient of the support function h with respect to the
unit sphere S2 . If the support function h is obtained by restricting a suitable function
h0 ∈ C∞ (R3 , R) to the unit sphere S2 , then
(∇S2 h)(n) = (∇h0 )(n) − [(∇h0 )(n) · n]n.
(2)
This parameterization, whose domain is the unit sphere, can now be composed with
any parameterization of S2 , e.g., by spherical coordinates.
In this paper we are particularly interested in the case where the support function
is the restriction of a trivariate quadratic polynomial to S2 . We call the corresponding
envelopes quadratically supported surfaces (QSS). The class of QSS is closed under
translations, offsetting and rotations, as these geometric operations correspond to the
addition of constants and homogeneous linear polynomials, and to the composition
with rotations, respectively.
Example 1. Let n = (x, y, z)⊤ and consider the two support functions
3
h(n) = x2 + y2 + z2
2
and h(n) = x2 + y2 − z2 .
The associated QSS have the parametric representations xh (n) =
3
3
−x − xy2 − 32 xz2 + 2x
−x − xy2 + xz2 + 2x
−yx2 − y3 − 3 yz2 + 2y and −yx2 − y3 + yz2 + 2y ,
2
−zx2 − zy2 + z3 − 2z
−zx2 − zy2 − 32 z3 + 3z
(3)
(4)
Exact envelope computation for moving surfaces with quadratic support functions
3
Fig. 1 Quadratically supported surfaces (QSS).
respectively. Both support functions describe surfaces of revolution, shown in Fig.
1, and the profile curve of the second one is a special trochoid.
3 Motions, velocities, characteristics
As usual, we describe a rigid body motion by a time–dependent transformation
x′ = t(α ) + U(α )x
(5)
between world coordinates x′ and moving coordinates x, where the parameter α
represents the time, the vector t(α ) represents the translation of the origin, and the
special orthogonal matrix U(α ) specifies the rotation. For an arbitrary but constant
value of α , we compute the velocity vector v′ of a fixed point x in the moving system
˙
v′ = ˙t + Ux,
(6)
where the dot indicates differentiation with respect to α and the argument α has
been omitted. This velocity is transformed into the moving system
˙ = U ⊤ ˙t + ω × x,
v = U ⊤ v′ = U ⊤ ˙t + U ⊤Ux
(7)
where ω denotes the angular velocity.
We consider a surface in the moving space, which is assumed to be given by its
support function representation. The surface touches the envelope along the characteristic curve. Let
(8)
vh (n) = U ⊤ ˙t + ω × xh(n)
be the velocity of the point xh (n), then the characteristic curve consists of all points
where the inner product of the velocity and the surface normal n vanishes,
4
Margot Oberneder1 , Bert J¨uttler1 and Laureano Gonzalez-Vega2
vh (n) · n = 0.
(9)
In the case of a moving QSS, the Gauss image of the characteristic curve (i.e., the
spherical curve obtained by collecting the surface normals along it) is particularly
simple:
Theorem 1. The Gauss image of the non–degenerate characteristic curve of a moving QSS is a spherical quartic.
Proof. After substituting Eqns. 1, 2 and 8 into Eq. 9 one gets after a short computation
U ⊤ ˙t + ω ′ × (∇h)(n) · n + (h(n) − (∇h)(n) · n)(ω × n) · n = 0.
(10)
=0
If h is a trivariate polynomial of degree 2, then this equation is of degree 2. The
Gauss image of the characteristic curve consists of all surface normals that satisfy
Eq. 10 and n · n = 1. Consequently, it is either the intersection of two quadric surfaces, or it degenerates into the entire unit sphere.
Summing up, the Gauss image of the characteristic curve is the zero set of the
two quadratic polynomials
f (n) = U ⊤ v˙ + ω ′ × (∇h)(n) · n and g(n) = n⊤ · n − 1.
(11)
The envelope surface can be generated by collecting all characteristic curves obtained for different values of α and transforming them into world coordinates.
4 Characteristic curves for QSS of revolution
In this section we compute a parameterization of the characteristic curve for a fixed
time α . Its Gauss image is the intersection curve of the two quadrics defined by the
quadratic polynomials in Eq. 11.
[Dupont et al., 2008], describe a sophisticated algorithm for the computation of
a near-optimal parameterizations of the intersection curve of two quadric surfaces.
This algorithm assumes that the coefficients of the two quadratic equations belong
to the field Q of rational numbers. The intersection curve is parameterized with
the help of square–root functions of certain polynomials, that belong to the ring of
polynomials over a special field extension of Q. In the most general case, the computation of the exact parameterization requires the solution of a quartic equation,
and the corresponding field extension.
In the remainder of this paper we restrict ourselves to QSS which are surfaces of
revolution with respect to the z–axis. The support function then takes the form
hR (n) = a(x2 + y2 ) + bz2 + cx + dy + ez + f .
(12)
Exact envelope computation for moving surfaces with quadratic support functions
5
We assume that the coefficients a, b, c, d, e, f are in the field Q of rational numbers,
and that the components of the angular velocity ω and the translational velocity ˙t
are also from this field.
Lemma 1. There exists a point P on the√Gauss image of the characteristic curve
with coordinates in the field extension Q( r), where r is an integer.
Proof. We consider an arbitrary but fixed rational number z0 . If we substitute z = z0
in Eq. 11, then this equation becomes linear in the remaining variables x and y.
Indeed, quadratic terms in Eq. 11 may be present only in [ω ′ × (∇hR )(n)] · n =
[(∇hR )(n) × n] · ω ′, and a short computation confirms that
2(a − b)yz0 − ey + dz0
(∇hR )(n) × n = 2(b − a)xz0 + ex − cz0 .
(13)
cy − dx
Consequently, the points on the Gauss image of the characteristic curve with z = z0
can be found by solving a single quadratic equation. Since the Gauss image of the
characteristic is always non–empty, it is possible to choose z0 such that real solutions
exist.
Based on this result we compute a parameterization of the Gauss image of the
characteristic curve by the Enhanced Levin’s method (ELM) of [Wang et al., 2003],
which is summarized below:
1. Find a real point P on the intersection curve f (n) = g(n) = 0. This point serves
as the center of the stereographic projection into the xy–plane (another plane may
be used).
2. Let Q = (ξ , η , 0)⊤ . The image of the spherical quartic under the stereographic
projection is the planar cubic curve defined by the cubic polynomial
1
1
c(ξ , η ) = Resultant( f (tQ + (1 − t)P), g(tQ + (1 − t)P;t).
t
t
(14)
3. Find a squareroot–parameterization of c(ξ , η ) = 0 and project it back onto the
unit sphere.
The first part of the last step will be explained in more detail. First we find a point
R on the cubic curve. For instance, it can be chosen as the intersection point of the
curve
√ tangent at P with the xy–plane. In this case, the coordinates of R are again in
Q( r). We then consider the pencil of lines
ξ (s,t)
1
=t
+ (1 − t)R, (s,t) ∈ R,
η (s,t)
s
(15)
and substitute into the cubic polynomial c(ξ , η ) = 0. After factoring out the trivial
solution t = 0, we solve the resulting equation, which is quadratic in t, for t and get
a solution of the form
k(s) ± ℓ(s)
t(s) =
,
(16)
m(s)
Margot Oberneder1 , Bert J¨uttler1 and Laureano Gonzalez-Vega2
6
Fig. 2 Characteristic curves on a moving non–convex QSS of revolution.
where the three polynomials k(s), ℓ(s) and m(s), which possess the degrees 2,√4 and
3, respectively, belong to the ring of polynomials over the field extension Q( r).
The projection of the cubic back onto the sphere, and the computation of the
characteristic curve by substituting the result into Eq. 1 involves only rational operations. We summarize the results of this section.
Theorem 2. The characteristic curve of a QSS of revolution, where the coefficients
of the support functions and the components of velocity and angular velocity are
rational numbers, possesses a parameterization
r1 (s,
ℓ(s)), r2 (s,
ℓ(s)), r3 (s,
ℓ(s))
⊤
.
(17)
The rational functions ri : R2 → R, i√= 1, 2, 3, and the quartic polynomial ℓ(s) have
coefficients in the field extension Q( r), where r is an integer.
5 Examples
Example 2. We consider a motion with ˙t(α ) = (1, 1, 0)⊤ and
2 − 2 cos α − 6 sin α 4 − 4 cos α + 3 sin α
5 cos α + 4
1
2 − 2 cos α + 6 sin α
8 cos α + 1
2 − 2 cos α − 6 sin α
U=
9 4 − 4 cos α − 3 sin α 2 − 2 cos α + 6 sin α
5 cos α + 4
(18)
and apply it to the non–convex QSS of revolution from the second section. Fig. 2
shows several positions of the moving non–convex surface and the corresponding
characteristic curves.
In order to obtain expressions with rational coefficients, we substitute both
1−β 2
sin α = 1+2ββ 2 and cos α = 1+
in U ⊤ , while U ⊤U˙ is a constant matrix, as U deβ2
scribes a uniform rotation with axis direction (2, 1, 2)⊤ . As an example, we consider
β = 2, i.e., α ≈ 0.927, where the two quadratic equations, which define the Gauss
image, are
f = 15x − 20xz − 9y + 40yz + 12z and g = x2 + y2 + z2 − 1.
(19)
Exact envelope computation for moving surfaces with quadratic support functions
7
Fig. 3 Several characteristic curves of
a moving convex QSS of revolution,
forming the envelope surface.
A possible center of projection is found after choosing z0 = 21 ,
√
√ 1 ⊤
15
77
35
6, − 33
P = (− 73
+ 292
73 − 292 6, 2 )
(20)
After projecting the spherical quartic into a planar cubic we obtain a parameterization of the form c(s) = (c1 (s), c2 (s), 0), where
ci (s) =
Ai (s) + Bi (s) C(s)
438D(s)
(21)
√
with certain polynomials Ai , Bi , C and D with coefficients in Q( 6). For instance,
√
2
3
D(s) = 5032323912s
√ + (7828867480 6 + 7806587880)s
√
+(4537170456 6 + 46260368554)s + 10293044615 6 + 24121304410
(22)
Finally, the coordinates of the characteristic curve in the moving system are given
by expressions of the form
p7 (s) C(s) + p9 (s)
p16 (s) C(s) + p18 (s)
p4 (s) C(s) + p6 (s)
3
,
(23)
(p3 (s))3
√
where pi represents a polynomial of degree i with coefficients in Q( 6).
Example 3. We performed a similar computation for a screw motion of the convex
surface. The resulting characteristic curves are shown in Fig. 3.
Example 4. We modeled a robot-like structure by composing three spheres and two
non-convex QSS. This structure performs a motion which is generated by two uniform rotations of the arms. Fig. 4 shows some characteristic curves which are created during this motion. A collision detection can now be done by checking intersections between the characteristic curves and the environment. This type of robot-like
structures could be used as bounding volumes for real mechanical devices.
Acknowledgements The authors were supported by the WTZ programme of the Austrian Exchange Service and by the Austrian Science Fund through the research network “Industrial Geometry”, subproject 9202.
8
Margot Oberneder1 , Bert J¨uttler1 and Laureano Gonzalez-Vega2
Fig. 4 Characteristic curves of
several positions of a moving
robot-like structure, forming the
envelope surface.
References
[Abdel-Malek et al., 2006] Abdel-Malek, K., Yang, J., Blackmore, D., Joy, K. (2006), Swept volumes: fundation, perspectives, and applications, Int. J. of Shape Modeling, vol. 12, no. 1,
pp. 87–127.
[Bottema and Roth, 1979] Bottema, A. and Roth, B: (1979) Theoretical Kinematics, NorthHolland, Amsterdam.
[Dupont et al., 2008] Dupont, L., Lazard, D., Lazard S. and Petitjean, S. (2008) Near-optimal parameterization of the intersection of quadrics: {I. The generic algorithm, II. A classification
of pencils and III. Parameterizing singular intersections} Journal of Symbolic Computation,
vol. 43, no. 3, pp. 168–232.
[Flaquer et al., 1992] Flaquer, J., G´arate, G. and Pargada, M. (1992), Envelopes of moving quadric
surfaces, Computer Aided Geometric Design, vol. 9, no. 4, pp. 299–312.
[Peternell et al., 2005] Peternell, M., Pottmann, H., Steiner, T., and Zhao, H. (2005) Swept volumes, Computer-Aided Design and Applications, vol. 2 , pp. 599–608.
ˇ ır et al., 2008] Sˇir, Z., Gravesen, J., and J¨uttler, B. (2008), Curves and surfaces represented by
[S´
polynomial support functions, Theoretical Computer Science, vol. 392, pp. 141–157
[Wang et al., 2003] Wang, W., Goldman, R., and Tu, C. (2003), Enhancing Levin’s method for
computing quadric-surface intersections, Comp. Aided Geom. Des., vol. 20, no. 7, pp. 401–
422.
[Xia and Ge, 2001] Xia, J., Ge, Q. J. (2001), On the Exact Representation of the Boundary Surfaces of the Swept Volume of a Cylinder Undergoing Rational Bzier and B-Spline Motions,
Journal of Mechanical Design, vol. 123, no. 2, pp. 261–265.