S Ocken. # Precise implementation of CAD primitives using rational parametrizations of standard surfaces online

. **(page 1 of 3)**

Online Library → S Ocken → Precise implementation of CAD primitives using rational parametrizations of standard surfaces → online text (page 1 of 3)

Font size

Computer Science Department

TECHNICAL REPORT

PRECISE IMPLEMENTATION OF CAD PRIMITIVES

USING RATIONAL PARAMETRI ZATIONS

OF STANDARD SURFACES

By

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

Technical Report No. 67

March, 1983

NEW YORK UNIVERSITY

Department of Computer Science

Courant Institute of Mathematical Sciences

251 MERCER STREET, NEW YORK, N.Y. 10012

PRECISE IMPLEMENTATION OF CAD PRIMITIVES

USING RATIONAL PARAMETRI ZATIONS

OF STANDARD SURFACES

By

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.

by

S. Ocken

Computer Science Department, New York University

(permanent address: Mathematics Department, The City College.)

J.T. Schwartz

Computer Science Department, New York University

and

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.

-2-

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

-3-

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

999

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

is rational, since it has the (stereographic) parametrization

-4-

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

o

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

1+u- l+u-

999

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

909

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

or

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

(x2+y2)l/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)).

-5-

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

rational.

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

-6-

(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

-7-

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.

Then

[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]

-8-

= 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.

Designator

[2n,2n+l]

[2n-2,2n]

[2n-l,2n]

[2n.2n]

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

Dimension

Rank

of

L

Rank of S

2n+l,n>0

2n

2n+l

2n,n> 1

2n-2

2n

2n,n>l

2n-l

2n

2n+l,n> 1

2n

2n

-14-

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.

-15-

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

TECHNICAL REPORT

PRECISE IMPLEMENTATION OF CAD PRIMITIVES

USING RATIONAL PARAMETRI ZATIONS

OF STANDARD SURFACES

By

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

Technical Report No. 67

March, 1983

NEW YORK UNIVERSITY

Department of Computer Science

Courant Institute of Mathematical Sciences

251 MERCER STREET, NEW YORK, N.Y. 10012

PRECISE IMPLEMENTATION OF CAD PRIMITIVES

USING RATIONAL PARAMETRI ZATIONS

OF STANDARD SURFACES

By

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.

by

S. Ocken

Computer Science Department, New York University

(permanent address: Mathematics Department, The City College.)

J.T. Schwartz

Computer Science Department, New York University

and

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.

-2-

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

-3-

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

999

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

is rational, since it has the (stereographic) parametrization

-4-

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

o

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

1+u- l+u-

999

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

909

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

or

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

(x2+y2)l/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)).

-5-

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

rational.

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

-6-

(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

-7-

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.

Then

[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]

-8-

= 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.

Designator

[2n,2n+l]

[2n-2,2n]

[2n-l,2n]

[2n.2n]

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

Dimension

Rank

of

L

Rank of S

2n+l,n>0

2n

2n+l

2n,n> 1

2n-2

2n

2n,n>l

2n-l

2n

2n+l,n> 1

2n

2n

-14-

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.

-15-

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

Online Library → S Ocken → Precise implementation of CAD primitives using rational parametrizations of standard surfaces → online text (page 1 of 3)