S Ocken.

Precise implementation of CAD primitives using rational parametrizations of standard surfaces online

. (page 1 of 3)
Online LibraryS OckenPrecise implementation of CAD primitives using rational parametrizations of standard surfaces → online text (page 1 of 3)
Font size
QR-code for this ebook

Computer Science Department



S. Ocken, J.T. Schwartz, & M. Sharir

Technical Report No. 67
March, 1983


Department of Computer Science
Courant Institute of Mathematical Sciences



S. Ocken, J.T. Schwartz, & M. Sharir

Technical Report No. 67
March, 1983

New York University

Dept . of Computer Science

Courant Institute for

Mathematical Sciences
251 Mercer Street
New York, N.Y. 10012

Precise Implementation of CAD Primitives Using Rational Paramet rizations

of Standard Surfaces.


S. Ocken
Computer Science Department, New York University
(permanent address: Mathematics Department, The City College.)

J.T. Schwartz
Computer Science Department, New York University


M. Sharir
School of Mathematical Sciences, Tel-Aviv University

Abstract: We discuss the problem of computing the intersection curve of
two algebraic surfaces, each of which possesses rational
parametrization. The special case where the two surfaces are quadric
is analyzed in detail, using a general decomposition theorem which
guarantees the existence of a simultaneous canonical reduction of two
quadratic forms in Euclidean n-space. In homogeneous 4-space this
yields a classification and simple parametrization of all possible
intersections between two quadric surfaces. Using these results, we
treat the problem of analyzing the structure of solid bodies defined by
Boolean combinations of half-spaces bounded by arbitrary quadric
surfaces. The analysis given leads to fast versions of some of the
procedures required for geometric modeling systems which admit general
quadric surfaces into their vocabulary of basic shapes.

Work on this paper has been supported by ONR Grants N00014-75-C-0571
and N00014-82-K-0381 and by a grant from the U.S. -Israeli Binational
Science Foundation.


1. Introduction.

In his survey [We80] of geometric modeling systems, M. Wesley
makes the following cogent remarks: 'There are some fundamental
problems to be solved in the field of geometric representation.
Firstly, curved surfaces are required; in the short term, cylinders are
probably sufficient for many applications, to be followed by cones and
then more general curved surfaces. Secondly, the geometric
representation has to be absolutely robust under all conditions. The
system can be expected to be used to generate arbitrary objects without
human intervention. It is essential that the objects always be
numerically and topologically valid; e.g. it must handle situations
where surface details become arbitrarily small without generating
invalid topologies. Thirdly, the system must allow computation of
necessary results with optimum efficiency in terms of computation time
and storage efficiency. As the applications leave the stylised blocks
world of the laboratory and approach the full complexity of real
engineering situations, the limits of computational capacity can be
expected to be reached, and choices between modeling systems may be
based on cost rather than the ability to perform the operation at all.'

If for the moment we ignore the computational cost factor on which
Wesley lays a very justified stress, it becomes possible for an ideal
geometric modeling system to deal with arbitrary bodies and surfaces.
There do exist general algorithmic techniques for deciding all the
questions about such bodies which a geometric modeling system needs to
ask. These techniques derive from Tarski's general method for deciding
quantified formulae in the elementary theory of reals, which has been
improved substantially by various other authors in the years since
Tarski's original paper: see [Ta51 ,Co75,Ar81 ,La77 ] and [SS81] for a
review of some of this material.

However, these general methods, which are based upon systematic
but unoptimi^.ed use of elimination theory and of Sturm's location
theorem for the roots of real polynomials, are too expensive
computationally for use in a practical geometric modeling system. For


thls reason, one must focus on a class of surfaces whose Boolean
combinations can be handled with considerably greater efficiency than
can algebraic surfaces in general. The following definition specifies
a class of surfaces which is advantageous (but not necessarily
sufficiently advantageous) in this regard.

Definition 1: A surface S is said to be rational if

(a) S is defined by a polynomial equation P(x,y,z) = having rational
(or at least real algebraic) coefficients;

(b) There exists a parametrization x = X(u,v), y = Y(u,v), z = Z(u,v)
of the surface S by functions X,Y,Z which are quotients of polynomials
in u,v having rational (or at least real algebraic) coefficients. (We
suppose this parametrization to be defined for u,v in some domain D
which is itself defined in a simple way by polynomial inequalities in
u,v, and suppose that except on a few equally simple curves and points
this parametrization is 1-1.)

The advantage of working with such surfaces is that their
intersections can be deterrained_ relatively efficiently, since if Pj^ =
is the polynomial equation for one such surface S, and X9,Y9,Z9 give
the parametric representation for another surface S-,, then the
intersection Sj^*So is represented by the set of pairs satisfying the
simple equation P j^ (X2(u, v) ,Y2(u, v) ,Z2(u, v) ) = 0. Although a related
algebraic condition can be written even if the surfaces S ]^ and S2 are
not rational in the sense defined above, resultants would have to be
used to derive this condition, substantially degrading the efficiency
of the calculation required to deal with S]^*S2.

The class of real rational surfaces is extensive. Examples are as
follows. Any surface of the form z = P(x,y), where P is a polynomial

or a quotient of polynomials is evidently rational. This includes the

paraboloid and the hyperboloid of one sheet. The sphere x'"+y"'+z = 1

is rational, since it has the (stereographic) parametrization


f N / 1-u -v" 2u 2v .

(x,y,z) = ( ^ ^ . — T-^. — ^^ - f)
1+u^+v- l-Ki'-H-v" 1+U-+V"

9 9 T

Similarly, the cone ^ - x^-y" = is rational, since it has the
parame t r i z a t i on

(x,y,z) = v( _, _, 1)

1+u- l+u-

9 9

The cylinder x^+y = 1 is rational and has the parametrization


(x,y,z) = ( _, _, v)

1+u- l+u-

The double-sheeted hyperboloid z -x^-y'' = 1 has the parametrization

9 9
, ^ , 2u 2v l+u^+v".
(x.y.z) = ( , . , ,, , , )

l-u^'-v'" l-u^-V" 1-U - V"'

where u and v vary in the open unit circle. The single-sheeted
hyperboloid x"+y -z~ = 1 is a ruled surface and has the parametrization

, . ,l-u^+2ut 2u-t(l-u'^)
(x,y,z) = ( — , ^— i, t).

1+u- 1+u^

The torus formed by sweeping a circle of radius r < R and center

(R,0,0) around the circle x~+y-=R'- in the x-y plane has the equation


|(x,y,z) - R_liilZli^|2 = ^2

(x2+y2+z2+R2_^2)2 = 4R(x2+y2),

and the parametrization

(x,y,z) = (ri:4^R).(il4. A-> 0) + (^> 0, -^).
1+v- 1+u- 1+u- l+v2

Many other surfaces are rational also. For example, any surface of
revolution of a pararaetrizable curve (x,y,z) = (f (t ) ,0,g(t ) ) about the
z-axis is rational, and has the parametrization

(x.y.z) = (f(t)ll^. f(t)Jl-, g(t)).


and a defining equation which can easily be obtained by elimination
from the parametric representation of the initial curve. Note also
that any affine or projective image of a rational surface is also

2. Intersection of Quadric Surfaces ; Algebraic Analysis of the
n-dimensional Case

It is easy to see from the above remarks that all real quadric
surfaces are rational., Indeed, if we proceed protectively, writing the
polynomial equations for all our surfaces as homogeneous polynomial
equations in four variables, then the equation for any quaciric can be
written as La« a = 0, where L is a 4x4 symmetric matrix, and where a is
a 4-vector (x,y,z,w). We can diagonalize L, which corresponds to
carrying out an appropriate projective transformation of our surface,
and normalize the transformed L so that each of its diagonal entries is
either ±1 or 0. Then this normalized L can be brought to a form in
which it has at least as many positive as negative entries, and in
which the diagonal entries of L are arranged so that the ;^ero entries
precede the positive ones which in turn precede the negative entries.
Moreover, we can assume that L contains one negative and at least two
positive diagonal entries, for otherwise it would represent a point, a
line, a plane, or a pair of planes, all of whose intersections with
another quadric surface may be easily computed.

Proceeding in this way, the transformed L will have one of the
following forms: Either

(i) L has three positive and one negative entries, in which case it

9 o 9 o

represents the sphere x +y +z -w = 0; or

(ii) L has two positive and two negative entries, in which case it

9 9 9 9

represents the single-sheeted hyperboloid x^+y^-z -w" = 0; or


(iii) L has two positive, one negative and one zero entry, in which

2 2 2
case it represents the cylinder y +z -w = .

Since we have noted in the preceding that all these canonical

surfaces are rational, it follows that every quadric surface Is
rational. These surfaces have relatively simple structure, which makes

it easy to deal with their intersection curves. This will be done in

the present section, ultimately to yield a relatively simple technique

for the analysis of general Boolean combinations of bodies bounded by
quadric surfaces.

Let A and Z be two quadric surfaces, represented respectively by
the 4x4 matrices L, S in the manner described above. Applying the same
projective transformation to both surfaces, we may assume Chat L has
one of the three canonical forms listed above, and that S is still
symmetric. Thus L represents either a sphere, a single-sheeted
hyperboloid, or a cylinder, and we are left with the problem of finding
the intersection curve of such a surface with a second, arbitrary
quadric surface. This problem was studied by J. Levin [L] , who gave a
fairly systematic account of these intersections. However, since the
situation is simpler when viewed projectively than when only affine
simplifications are used, we will analyze these intersections from a
projective viewpoint. To obtain the simple classification of the
intersection curves which we seek, we transform the homogeneous 4-space
projectively so as to bring both quadratic forms (Lx,x) and (Sx,x) to
simple form, from which the intersection curves can easily be obtained.

First we consider the case in which L is nonsingular
(corresponding to the preceding cases (i) and (ii)), but abandon the
restriction that the space X in which L and S act is 4-dimensional,
since it is not hard to treat the general n-dimensional case.

Our task is to reduce the matrix S to its simplest equivalent form
while maintaining some equally simple form of L, i.e. to replace S by
a simpler matrix T'ST where T is some real transformation for which
T'LT = L, or for which T'LT retains some equally convenient form. We


will always keep L in a form satisfying L^ = I, and then the
eigenvalues of LS are invariant under such transformations T, since

LT'ST = (LT)"^ST = T"^LST.

In what follows, we will show that these are essentially tlie only
invariants of the pair L, S .

Write [x,y] for the nonsingular Indefinite Inner product Lx«y.

[LSx,y] = Sx«y = x« Sy = Lx« LSy = [x.LSy],

so that LS Is self-adjoint relative to the bilinear form [x,y].

The (generalized) eigenspace X^ belonging to an eigenvalue \ of LS
Is the set of all vectors x such that (LS-XI)'^x = for some Integer n.
The space X decomposes Into the direct sum of such elgenspaces, each of
which is invariant under LS. It is plain that for each eigenvalue \i t
\, the restriction of LS - XI to X^ Is nonsingular. Hence for each y e
Xy there exists a z e Xj such that (LS - XI)'^z = y. Thus for each x z
\, [x,y] = [x,(LS-\I)'^z] = [(LS-XD^x.z] = 0. This shows Chat
elgenspaces X^^ , X^ belonging to different eigenvalues X ,^i are
orthogonal to each other In the bilinear form [x,y].

To reduce L and S simultaneously to the desired canonical form it
Is sufficient to analyze the restriction of LS to each of the spaces
'^\ , X real, and to each pair of spaces X;^ ,X^, X complex. First
consider a generalized eigenspace X^ with X real. In this space, the
operator R = LS - X I Is still symmetric relative to the nonsingular
bilinear form [x,y] and satisfies R^=0 for some (smallest) n, so that
R"^"^ * 0. Thus there exist x and y In X^ such that [y,R"~-^x] * 0. This
Implies that there exists a z e X-^ such that [z,r"~ z] * 0, since
otherwise x, y would satisfy

= [(x+y),R""^(x+y)] = [y,R""^x] + [x,R'^-^y]


= 2[y,Rf^-lx] t 0.

Suppose without loss of generality that [x,R""^] f- 0. Then the the
space Y^ spanned by {x,Rx, . . . ,R"~ x} is Invariant under R (I.e., under
LS), and the restriction of [x,y] to this space Is nonslngular.
Indeed, if

u = a .R Jx + a .^^RJ'^^x + . • • + a^^.^R'^'-^x,
where ex • * Is such that [u,R"^] = for all m > 0, then

= [u,R""^"Jx] = aj[RJx,R""^"Jx] = a ^ [x,r"~^x] jst 0,

a contradiction.

Since the space Y|^ is Invariant under R and since [x,y] is
nonslngular on Y^, Its orthogonal complement Y^' (relative to the inner
product [x,y]) has these same properties. Thus the argument given In
the preceding paragraph can be applied to Y^^ ' , from which It plainly
follows that X^ decomposes Into a direct sum of subspaces Y^ + Y9 + ...
+ Yj., mutually orthogonal relative to the Inner product [x,y], In each
of which the operator R acts as a shift (i.e. each of these spaces has
a basis {x,Rx, . . . ,R"~^x} ) for which [x,R^~^x] * 0.

Consider a single such space Y = Y^, and let Its dimension be n,
so that R^y = for all y e Y. By modifying x appropriately we can
assume without loss of generality that [x,Rix] = except for j = a-1.
Indeed, suppose that this Is false, and consider the largest j-lx'] ^ 0.

It is plain that {x' ,Rx' , . . . ,R'^~^x' } spans the same space Y as
{x,Rx, . . . ,R'^~^x} . Thus if we replace x by x', j is reduced by at least
1, proving that there exists an x as above, but with [x,RJx] = for
all (K j 1
G(x) = 2x^x2 + ••• + 2x2n-lX2n

(simplest case: 2xy,2yz)

We can use the symbols [2n,2n+l], [2n-2,2n], [2n-l,2n], [2n,2n]
respectively as designators for these linear spaces. The following
table gives the dimensions and ranks of L and S.



We will use the symbol [0] to designate a 1-dimensional space in
which both the quadratic forms L and S are 0,

Note that S is nonsingular in all these spaces with the exception
of the space [2n,2n]. Thus each of the spaces [2n,2n+l], [2n-2,2n],
[2n-l,2n] can be regarded as a kind of 'reverse' of spaces (or sums of
spaces) that we have already encountered, obtained by interchanging L





Rank of S




2n,n> 1






2n+l,n> 1




and S. By considering the form of SL, it is easily seen that in this
sense [2n+l,2n] is the reverse of either [0,n,n+l] or [0,n+l,n]; that
[2n-2,2n] is the sum of two isomorphic spaces, each of which is the
reverse of one of the spaces [0,k,k+l], [0,k+l,k], [0,k,k.+], or
[0,k,k,-]; and that [2n-l,2n] is the reverse of either [0,n,n,+] or
[0,n,n,-]. The exceptional space [2n,2n] is its own reverse.

In view of those facts, it is convenient to introduce the
notations [X,m,m+1] ,... for the reverse of [X,m,m+1]...

To handle the case in which L can be singular, we proceed by
induction on the dimension of X. If L is nonsingular, there is nothing
to prove, so that we can assume that the nullspace N=N|^ of L, i.e. the
set \ = {x e X: Lx=0}, is nonempty. If x« Ly = for all y then Lx =
and conversely; hence the range R = Rj^ of L is the orthocomplement of
^L, giving the direct sum decomposition X = Ny^ + R^. If there exists a
nonzero x £ N-j^ such that Sx = 0, then we can write X as the sura of the
1-dimensional space (x) and its orthocomplement Y, and these spaces are
orthogonal in both forms L and S. Hence in this case we achieve a
complete canonical decomposition of X by decomposing Y inductively.
Thus we need only consider the case in whch S is nonsingular on Nt . If
there exists any x g N^ such that x- Sx #0, we can let Y be the
S-orthocorapleTient of the 1-dimensional space (x), and then again X is
the direct sum Y + (x) of two spaces orthogonal in both forms L and S,
so once more we can proceed inductively. In all remaining cases we
will have x« Sx = for all x e N, which implies that y« Sx = for all
x,y e N, so that S is a 1-1 mapping of N into its orthocomplement R.

Take some x^ e N. Let Z be the space spanned by x^ and Sxq. The
form (u« Sv) is nonsingular in Z, since if z«S(ax + bSx^) = for all z
e Z, then putting z = x^ we have b|Sxo|- = since x^. Sxg = 0, and
therefore b = 0, but now putting z = Sx^ gives a = 0. It follows that X
can be written as a direct sum X = Z + Z*, where Z* is the
S-orLhocomplement of Z. Note that Z and Z* are S-orthogonal , but not
necessarily L-orthogonal.


Since x^. Sxq = 0, the noasingular form S is neither positive
definite nor negative definite on the space Z, and hence it must liave
signature (1,1). Thus in appropriate coordinates it has the
representation x - y'-, and in these coordinates x will appear as a
2-dimensional vector (a,b) satisfying a' — b^ = 0. Put e^^ = Xq, and let
^2 be the vector with coordinates c(a,-b) in these same coordinates,
where c = (2a-)"^ then ej^. Sei = e2* Se2 = and ei« Se2 = 1. 1-et
e3,...en be a basis for Z*. In the basis for Z consisting of the
vectors e^ and e2, the form S has the matrix A2 appearing just below.
Moreover, the symmetric linear transformation representing the form L

satisfies Le^ = 0. In the following discussion we will make use of this
basis, and write u« v for a positive-definite inner product in which the
vectors e- are orthonormal.

\t this point we begin a subsidiary induction. Let n be the

1 3

Online LibraryS OckenPrecise implementation of CAD primitives using rational parametrizations of standard surfaces → online text (page 1 of 3)