It is it occasionally useful to work in 3D co-ordinate systems other
than rectangular (x,y,z). The two which we will meet are: spherical
polar (
)
and cylindrical polar (
). To
convert from one to and from these you use the following formulae.
Spherical polar to rectangular
x | = | (4) | |
y | = | (5) | |
z | = | z | (6) |
(13) |
(14) |
(15) |
(16) |
(17) |
(18) |
(19) |
(20) |
= | 0 | (21) | |
= | 0 | (22) |
The unit sphere, centred at the origin, has the implicit equation:
r=1 | (26) |
(x_{E}+tx_{D})^{2}+(y_{E}+ty_{D})^{2}+(z_{E}+tz_{D})^{2}=1 | (28) | ||
t^{2}(x_{D}^{2}+y_{D}^{2}+z_{D}^{2})+t(2x_{E}x_{D}+2y_{E}y_{D}+2z_{E}z_{D}) | |||
+(x_{E}^{2}+y_{E}^{2}+z_{E}^{2}-1)=0 | (29) | ||
at^{2}+bt+c=0 | (30) | ||
(31) |
An alternative formulation is to use the vector versions of the
equations (Equations 23 and 27):
(32) | |||
(33) | |||
at^{2}+bt+c=0 | (34) | ||
(35) |
The infinite unit cylinder aligned along the z-axis is defined as:
r=1 | (37) |
(x_{E}+tx_{D})^{2}+(y_{E}+ty_{D})^{2}=1 | (38) | ||
t^{2}(x_{D}^{2}+y_{D}^{2})+t(2x_{E}x_{D}+2y_{E}y_{D}) | |||
+(x_{E}^{2}+y_{E}^{2}-1)=0 | (39) | ||
at^{2}+bt+c=0 | (40) | ||
(41) |
The finite open-ended unit cylinder aligned along the z-axis is
defined as:
(42) |
(43) |
If we wish the finite length cylinder to be closed we must formulate
an intersection calculation between the ray and the cylinder's end
caps. The end caps have the formulae:
(44) | |||
(45) |
(46) |
The infinite double cone^{2} aligned along
the z-axis is defined as:
r^{2}=z^{2} | (48) |
(x_{E}+tx_{D})^{2}+(y_{E}+ty_{D})^{2}=(z_{E}+tz_{D})^{2} | (49) | ||
t^{2}(x_{D}^{2}+y_{D}^{2}-z_{D}^{2})+t(2x_{E}x_{D}+2y_{E}y_{D}-2z_{E}z_{D}) | |||
+(x_{E}^{2}+y_{E}^{2}-z_{E}^{2})=0 | (50) | ||
at^{2}+bt+c=0 | (51) | ||
(52) |
The finite open-ended cone aligned along the z-axis is
defined as:
(53) |
To handle this finite length cone you proceed as for the finite length cylinder, with the obvious simple modifications.
A torus is defined by two parameters: the radius of the torus (that is the radius of the torus's defining circle, measured from the origin) and the radius of the tube (the perpendicular distance from the defining circle to the surface of the torus). These are R and rrespectively. Normally R > r.
An implicit definition of the torus is:
To find the intersection points of a ray with a torus you need to
substitute Equation 24 in
Equation 54. Equation 58 is that
substitution with the
term expanded,
the resulting square root term placed on one side of the equals sign,
and all other terms placed on the other side:
= | R^{2} + x_{E}^{2}+2tx_{E}x_{D}+t^{2}x_{D}^{2} + y_{E}^{2}+2ty_{E}y_{D}+t^{2}y_{D}^{2} + z_{E}^{2}+2tz_{E}z_{D}+t^{2}z_{D}^{2} - r^{2} | (58) |
A plane can be defined by a normal vector,
and a point on
the plane, .
A point, ,
is on the plane if:
A polygon can be defined by an ordered set of vertices: . To find the intersection point between a polygon and a ray, we first find the intersection point between the polygon's plane and the ray, and then ascertain whether this intersection point lies inside the polygon or not.
The normal of the polygon's plane can be found by the simple cross product: . A point on the plane's surface is even easier to find: . The intersection calculation then proceeds as above.
If an intersection point between the ray and the plane is found then we can check whether or not the point lies inside the polygon in the following manner. First we project the intersection point and the polygon to two dimensions by simply throwing away one coordinate. Obviously we will throw away the coordinate in which the polygon has the smallest extent. We then test to see if the intersection point lies inside the two dimensional polygon using the odd/even test.
The odd/even test checks to see whether or not an arbitrary point lies inside an arbitrary polygon in two dimensions. This is done by drawing an arbitrary ray from the point to infinity. If the ray crosses an even number of polygon edges then the point lies outside the polygon. Contrariwise, if the ray crosses an odd number of polygon edges then the point lies inside the polygon. A full discussion of the implementation details of this, and other point-in-polygon algorithms, can be found in Graphics Gems IV pp. 24-46.
The disc is similar to the polygon. Both are planar objects. A disc
can be defined by its centre, ,
its radius, r, and a
normal vector, .
Finding the intersection point, ,
of the ray with the disc's plane proceeds as for a plane/ray or
polygon/ray intersection. Discovering whether
lies inside
the disc requires you to simply check that:
(62) |
Of the above primitives, only the plane and polygon are arbitrarily defined^{4}. The sphere, cylinder, cone, and torus are all defined as being centred at the origin, and all have other restrictions on their definition^{5}. In order to ray trace one of these primitives in an arbitrary location we have two alternatives: (1) find general intersection algorithms between a ray and the arbitrarily located versions of the primitives; or (2) use geometric transforms to scale, rotate, and translate these primitives into the desired locations. This second option will be followed here.
The basic idea here is a very simple. We specify a scaling, a rotation, and a translation which, between them, transform the primitive from its standard position to the desired location. You will remember that this was covered in the IB Computer Graphics & Image Processing course. To perform the intersection we take the inverse transform of the ray, intersect this with the primitive in its standard position, and then transform the resulting intersection point to its correct location.
We now need to take a small diversion in order to explain the difference between a vector representing a point and a vector representing a displacement. A displacement can be thought of as the difference between two points. When transforming objects, displacements are scaled and rotated but not translated. Think of it this way: if you translate two points, the displacement between them stays exactly the same. But if you scale or rotate the two points, the displacement between them scales or rotates accordingly.
All this is by way of explaining how we transform a ray in order to
intersect the appropriate ray with the primitive in its standard
position. Let us assume that the primitive object in its standard
position,
,
undergoes transformation^{6}
to get into the desired position
.
To intersect ray,
,
with
we transform the point,
,
and the displacement
as follows:
= | (63) | ||
= | (64) |
Now intersect ray, , with the object in its standard position, , as described in the previous sections. This gives the value of t and consequently allows you to directly calculate .
In addition to scaling, rotating and translating the standard primitives, this mechanism allows us to stretch and squash them by scaling them by different factors in the different dimensions. For example, an ellipoid is simply a stretched sphere. However, such anisotropic scaling causes interesting problems with the normal vectors, as discussed in the following section.
In ray tracing we need to know not just the intersection point but
also the normal vector to the surface at the intersection point. This
normal vector is used in the illumination calculations. However, if we
scale an object anisotropically, the normal vector scales as the inverse of the object scaling, although it rotates in the same
way as the object. Figure 1 graphically
illustrates this phenomenon.
This can be mathematically explained by remembering that the normal
vector is related to the derivative of the surface. The normal
vector is perpendicular to the surface, which means that it is
perpendicular to any derivative vector. As an example, consider the
ellipsoid created by scaling the unit sphere by the matrix:
(65) |
The intersection point between the unit sphere and the inverse transformed ray will be at some point . This equates to the spherical polar coordinate where^{7} . By virtue of the fact that the normal to every point on the sphere passes through the centre of the sphere, it is easy to see that the normal vector, , is also .
Transforming to the true intersection point is simply a matter of applying . Thus the intersection point of the ray with the ellipsoid is at rectangular coordinate .
To find the normal vector to the ellipsoid at this intersection point,
we need to find two non-parallel derivative vectors to the surface at
the intersection point, and take their cross product to give the
normal vector, .
Two derivative vectors are:
= | (66) | ||
= | (67) |
= | (68) | ||
= | (69) |
= | (70) | ||
= | (71) |
= | (72) | ||
= | (73) |
We may be in a situation where we define objects in terms of the various primitives, but where we wish to draw the objects using polygon scan conversion. In this case we need to convert primitives into polygons. Some polygon scan conversion algorithms can only deal with triangles; in these cases we may need to do a little bit of extra work to ensure that all of the generated polygons are triangles.
Converting the curved primitives (sphere, cylinder, cone, torus, disc) involves approximating a curved profile by a series of straight line segments. The simplest example is the disc. This can be approximated by a regular n-gon, where n is chosen to give an adequate approximation to the disc. ``Adequate'' in this case will depend on the desired rendering resolution, the desired speed of rendering, and the desired quality of the final image. If necessary, this n-gon can be converted to triangles in one of a number of ways: (1) define a central vertex and connect every edge to this vertex to make nisosceles triangles; (2) select one vertex on the n-gon, and make a triangle fan emanating from this vertex; or (3) start at one edge of the n-gon and make a triangle strip set which proceeds from this edge of the polygon to the opposite edge.
A cylinder or cone can be converted to polygons by polygonising the discs at either end into n-gons, and then connecting corresponding vertices on the two n-gons. In the special case of a cone with a point, one of the n-gons obviously degenerates to that point.
Spheres and tori can be most easily converted to polygons by considering their parameterisation in terms of and (for a sphere these are Equations 1-3; for a torus they are Equations 55-57). By selecting appropriate steps in the two parameters we can generate a set of quadrilaterals which approximates the curved primitive.
It should be noted that spheres can be polygonised with more uniform polygons by starting with one of the five Platonic solids, and subdividing its faces accordingly. The details of this are left as an exercise to the reader.