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 is specified by the coordinates of its centre : u = (u_x, u_y, u_z), the lengths of the three semi-axes : (v₁, v₂, v₃), and a 3x3 rotation matrix : R .

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

where

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

and abbreviated to :

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 :

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

where

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 :

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

where A, B, and C are the functions :

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 :

which may be written as :

where :

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 a s a series of p straight lines by joing a sequence of points generated by the equation :

or

An ellipse with its axes parallel to the coordinate axes and an axial ratio (eccentricity) of e = a₁/a₂ can be similarly generated using :

where E contracts one axis, i.e.

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

where

This may be abbreviated to :

where the matrix T has elements :

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 ( d_x , d_y , d_z ).

Then

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, b_y, of an ellipsoid with centre at u, semi-axis lengths v, and rotation matrix R is b_y = u_y - (r₁₂.v_x)² - (r₂₂.v_y)² - (r₃₂.v_z)² 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 (x_i,y_i,z_i) on the profile of the i^th ellipsoid have been calculated. These are checked against all othe ellipsoids. For tht j^th, the values of x_i and y_i can be substituted into the quadratic for z_j of the j^th ellipsoid :

If the discriminat is positive, then the root with the negative sign gives the point nearer the observer on the j^th ellipsoid which has the same x and y values as th point on the outline of the i. If z_j < z_i , then the point (x_i,y_i,z_i) 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 i^th and j^th ellipsoids are h_i and h_j , and the centres of the ellipsoids are at u_i and u_j , then if

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

RESULTS

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

REFERENCE

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