Don HerbisonEvans , 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
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.
Each ellipsoid may be specified by the coordinates of its centre : u = (u_{x}, u_{y}, u_{z}), the lengths of the three semiaxes : (v_{1}, v_{2}, v_{3}), 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.
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
An ellipse with its axes parallel to the coordinate axes and an axial ratio of f = a_{1}/a_{2} can be similarly generated using :
where E lengthens one axis, i.e.
An ellipse with its axis a_{1} 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.
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 perspectiveprojected 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
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 semiaxis 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.
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 :
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 the 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 discrimiant 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
The number of tests to be done in total is equal to p.n.(n1) where there are 'p' points around each ellipse and 'n' ellipsoids. The number of tests can be considerably diminished by some initial pretesting to find out which ellipsoids cannot possibly obscure which.
Thus if the maximum semiaxes 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.
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
x_{a} = maximum value of (x^{2}+y^{2})^{1/2} of any part of the figure
u_{a} = longest axis of the ellipsoids composing the figure
p = number of points around the polygonal outline.
The illustrations show some stills from a number of animated sequences.
Cohen, D. (1970)
"Linear difference Curves",
Proceedings of the International Symposium
Computer Graphics 1970, Brunel University.
