Animated Cartoons by Computer Using Ellipsoids

Don Herbison-Evans ,   donherbisonevans@yahoo.com

Technical Report 94 (1974), updated 27 May 2017
Basser Department of Computer Science (now School of Information Technologies)
University of Sydney, Australia

ABSTRACT

Most solid objects can be approximated as closely as required by a concatenation of interpenetrating three dimensional ellipsoids. This report describes a computer program that has been written using this principle to draw projections of human and other articulated figures.

DRAWING THE ELLIPSOIDS

Each ellipsoid may be specified by the coordinates of its centre : u = (ux, uy, uz), the lengths of the three semi-axes : (v1, v2, v3), and a 3x3 rotation matrix : R .

The surface of the unrotated ellipsoid can be described by the equation

where

x' = (x', y', z')

The equation of the surface may be written in matrix and vector form as :

and abbreviated to :

x+.V.x = 1

where x = x' - u
and x+ means the transpose of x.

Rotation of the ellipsoid to some arbitrary orientation is effected by a similarity transformation, giving :

x+.R+.V.R.x = 1

where R is a rotation matrix. This R can be generated as the product of a series of elementary rotations about the coordinate axes :

R = R1.R2.R3...Rn

where

representing an elementary rotation of an angle phi (f) about the x, y, or z axis respectively.

Rotation axes can be specified either in fixed coordinates or in the axes of the ellipsoid by respectively either multiplying the next elementary matrix onto the right or left hand side of R.

Ellipsoids, when projected orthographically onto the (x,y) plane, give an elliptical profile. The equation of the ellipse may be found from the matrix R+.V.R as follows :

writing

the equation of the ellipsoid may be written as a quadratic in z :

m33.z2 + 2(m13x+m23y).z + (m11x2+2m12xy+m22y2-1) = 0

where we have used the diagonal symmetry of M to simplify the expression. It may be further abbreviated to :

A.z2 + 2B.z + C = 0

where A, B, and C are the functions :

A = m33
B = m13.x + m23.y
C = m11.x2 + 2m12.x.y + m22.y2 - 1
This has solutions :

For any particular values of x and y, the two solutions of this equation for z represent the front and back of the ellipsoid surface. Where the front and back meet, we have the profile which will thus have the equation :

B2 - AC = 0

which may be written as :

a.x2 + 2b.x.y + c.y2 = 1

where :

a = m11 - m132/m33
b = m12 - m13m23/m33
c = m22 - m232/m33

This is the required equation of the elliptical profile.

POLYGON APPROXIMATION TO AN ELLIPSE

A polygomal approximation to this profile may be generated using the fast method of Cohen (1970). An approximation to a circle centred on the origin may be generated as a series of p straight lines by joining a sequence of points generated by the equation :

or

si+1 = P.si where s1 = (x,y)1 is some initial point on the circle, and
alpha = 2.pi/p     ( a = 2.p/p if your browser supports Greek letters!)

An ellipse with its axes parallel to the coordinate axes and an axial ratio of f = a1/a2 can be similarly generated using :

si+1 = E-1.P.E.si

where E lengthens one axis, i.e.

An ellipse with its axis a1 at an angle q to the x axis can be generated using :

si+1 = Q-1.E-1.P.E.Q.si

where

This may be abbreviated to :

si+1 = T.si

where the matrix T has elements :

t11 = cosa - (f-1)/f).sina.sinq.cosq
t12 = (f.cos2q + (sin2q)/f).sina
t21 = -(f.sin2q + (cos2q)/f).sina
t22 = cosa + (f-1)/f).sina.sinq.cosq
This may be related back to the quadratic in x and y : a.x2 + 2.b.x.y + c.y2 = 1 through the eigenvalues : which give an axial ratio f = l+/l- and an orientation q = arctan(2b/(a-c))/2 A simple initial point on the ellipse is s1 = (1/a1/2 , 0) This method of drawing an ellipse has the added advantage of putting an increased density of points where the curvature is greatest.

It does not require any square roots inside the loop, as the direct solution of a quadratic would.

The sequence of points on the elliptical profile obtained by this method refer to a coordinate system with the origin at the ellipse centre. They must be added to the coordinates of the ellipse centre before drawing them.

PROJECTING THE ELLIPSOIDS

The equation of the orthographically projected profile of each ellipsoid is obtained by Cohen's method. This is then shifted to the appropriate position in three dimensional space by translation by an amount u (the coordinates of the ellipsoid centre). The resulting coordinates( x ) are perspective-projected assuming that the observer is at the origin, onto a plane window parallel to the ( x , y ) plane, centred on the position ( dx , dy , dz ).

Then

px = (x - dx).dz/z
py = (y - dy).dz/z
where (px , py

REPRESENTATION OF FIGURES

A series of ellipsoids was fitted by eye to the required figure, and a series of joints fitted where the figure was to articulate.

Each joint connected two ellipsoids. Each ellipsoid could have any number of joints.

The data for the program specifies the number of ellipsoids, their semi-axis lengths, the number of joints, a list of which ellipsoids connect at each joint, and the vector distance of each joint from the centres of each of the two ellipsoids that they connect.

From this data, the three dimensional positions of each of the joints and ellipsoid centres can be deduced. A set of rotation matrices, one for each ellipsoid, are also set up as unit matrices.

ANIMATION

A series of subroutines was written to perform the various actions. Data cards are read to specify in sequence which actions to perform and with what parameters. The subroutines are :

  1. DRAW
    This draws the approximate perspective projection of the figure.

  2. SHIFT ( x, y, z )
    This shifts the whole figure by an amount (x,y,z), i.e. adds (x,y,z) to the coordinates of all the joints and to the centres of all the ellipsoids.

  3. ROTATE ( q, a, x, y, z )
    This shifts the origin to point (x,y,z), and then rotates the whole figure (i.e. multiplies the joints, the ellipsoid centres, and the ellipsoid rotation matrices by the appropriate three-dimensional elementary rotation matrix according to the value of axis 'a'). It then shifts the origin back again to where it was. As an option, the centre of a specified ellipsoid can be nominated as the centre of rotation (x,y,z).

  4. GROUND
    This finds the bottom points of all the ellipsoids, and then the lowest one of these. The whole figure is then shifted up by this amount, so that the lowest point is just touching the ground (the y=0 plane). The y coordinate of the bottom, by, of an ellipsoid with centre at u, semi-axis lengths v, and rotation matrix R is by = uy - (r12.vx)2 - (r22.vy)2 - (r32.vz)2 assuming the positive y direction is 'up'.

  5. VIEW ( x, y, z )
    This moves the centre of the viewing window to (x,y,z) for use in the projection process when drawing the figure.

  6. GROW ( f )
    This multiplies all semi-axis lengths, joint positions, and ellipsoid centre coordinates by the vale 'f'. It then calls GROUND to reset the figure to touch the plane y=0 at the figures lowest point.

  7. BEND ( j, e, q, a )
    This shifts the origin to joint 'j', and then rotates using the appropriate elementary rotation matrix those joints, and the matrices and centres of those ellipsoids NOT connected through ellipsoid 'e' to joint 'j' . The origin is then shifted back again, and the figure re-grounded.


HIDDEN LINE SUPPRESSION

Each point on the profile of each ellipsoid is tested for visibility.

Suppose the coordinates of a point (xi,yi,zi) on the profile of the ith ellipsoid have been calculated. These are checked against all othe ellipsoids. For the jth, the values of xi and yi can be substituted into the quadratic for zj of the jth ellipsoid :

If the discrimant B2-A.C is negative, then (xi,yi,zi) is to the side of ellipsoid j and cannot be obscured by it.

If the discrimiant is positive, then the root with the negative sign gives the point nearer the observer on the jth ellipsoid which has the same x and y values as th point on the outline of the i. If zj < zi , then the point (xi,yi,zi) is obscured by the nearer face of ellipsoid j, otherwise it is visible. Note that this test also works for the case where the ellipsoids interpenetrate.

The number of tests to be done in total is equal to p.n.(n-1) where there are 'p' points around each ellipse and 'n' ellipsoids. The number of tests can be considerably diminished by some initial pre-testing to find out which ellipsoids cannot possibly obscure which.

Thus if the maximum semi-axes of the ith and jth ellipsoids are hi and hj , and the centres of the ellipsoids are at ui and uj , then if

(hi + hj)2 < (uix - ujx)2 + (uiy - ujy)2 then the ellipsoids cannot obscure any part of each other.

Before drawing each ellipsoid, this test is done between it and all the others, and tags put on those that can obsure it. Then as the ellipsoid is being drawn, only the tagged ellipsoids are tested for obscuration.

ERRORS

This method of testing hidden lines is only rigourously valid for orthographic projection. In using it for perspective projection, it leads to some errors. However, the use of polygonal approximations to the ellipse outlines has already introduced some errors. The projection error can be kept to less than the polygon approximation error if

zm >> ( p.xa ) / ( p.ua ) where zm = mean distance of the figure from the observer

xa = maximum value of (x2+y2)1/2 of any part of the figure

ua = longest axis of the ellipsoids composing the figure

p = number of points around the polygonal outline.

RESULTS

The illustrations show some stills from a number of animated sequences.

REFERENCE

Cohen, D. (1970)
"Linear difference Curves", Proceedings of the International Symposium Computer Graphics 1970, Brunel University.


           

~~~~~~~~~~~~~~~~~~~~~~

www.000webhost.com