This month there is only one article, Ray-Tracing with Affine Transforms. We will be adding the following articles over the next few months. An high efficiency single phase motor (Patent No. 5,300,870, granted April 5, 1994). The IMint interface (Patent applied for). Contouring in Hyperspace. Strange Recursion. And many others. (C)opyright 1995, Seven seas Software Inc., MathVISION Inc. --------------------------------------------------------------------------- Ray-Tracing with Affine Transforms Otto J. A. Smith June 13, 1995 --------------------------------------------------------------------------- For a hard copy version of this paper mail requests to the author at otto@olympus.net This article is available in post script by anonymous FTP from pub/sites/7seas under the name CONTAIN.PS --------------------------------------------------------------------------- Abstract: We derive affine transformations that change the basis of a three dimensional world space. The new basis for this space is chosen in such a manner that many ray-tracing calculations are simplified, particularly when doing z-buffering. We begin with the simple problem of determining whether a point is contained in a triangle and extend our derivation to three space. We present some algorithm optimizations that can make real-world computer programs faster. --------------------------------------------------------------------------- Triangle Containment: Let Tri( v1, v2, v3) be a triangle in 2-space. Each v and x are 2-dimensional row vectors. The parameters p1 and p2 are scalars. Figure 1 Given a point x, determine if x is interior to Tri( v1, v2, v3). In order to make this determination use vectors from the triangle to form a basis for the space, then any point can be represented by a parametric equation: (A.) x = v1 + p1( v2 - v1) + p2( v3 - v2) Now observe the following: 1. When p1 = 1 and 0 < p2 < 1 ,then x is on the line segment ( v2 , v3) . 2. When p2 = 0 and 0 < p1 < 1 , then x is on the line segment ( v1 , v2) . 3. When 0 < p1 < 1 and 0 < p2 < 1 and p1 = p2 , then x is on the line segment ( v1 , v3) . We constructed equation (A.) in the manner given here in order to insure that the three observations made above were true. Now if p2 < p1 then x is on the same side of the line determined by ( v1, v3) as v2 . If p2 > p1 then x is on the opposite side of the line. In other words, the point x is inside the triangle Tri( v1, v2, v3) when all of the following are true: 1. p2 < p1 2. 0 < p1 < 1 3. 0 < p2 < 1 Given the triangle Tri( v1, v2, v3) and x one can calculate p1 and p2. Given the triangle Tri( v1, v2, v3) alone, one can calculate a two by two working matrix W such that ( x - v1) W =[ p1, p2 ] where [ p1, p2 ] is a row vector. We construct a matrix M and define W = Inv(M) . The notation Inv(M) is used to indicate the matrix that is the inverse of M . That is Inv(M)M = I , where I is the identity matrix. x = v1 + p1( v2 - v1) + p2( v3 - v2) Let M = | v2 - v1 | | v3 - v2 | Then: 1. [ p1, p2 ] M = x - v1 2. [ p1, p2 ] = ( x - v1)Inv(M) 3. [ p1, p2 ] = ( x - v1) W In applications where many points will be checked against a single triangle this is a fast algorithm. It is fastest if p1 is calculated before p2 and verified against the limits zero and one so the algorithm can terminate prematurely if the point x is not contained in the triangle. If there are many points, the cost of calculating W = Inv( M ) is amortized over many points. W is a feature of the triangle and not the point being checked which is used in a multiplication with the matrix Inv( M ). When M is singular, W does not exist since v1, v2 and v3, all lie on a straight line. If this is the case the point is contained in the "triangle" ( line segment ) only if it is on the line defined by any two verticies from v1 , v2 and v3, and in addition has verticies from this set in both a positive and a negative direction. Discussion of Basic Algorithm: I have found no references to the derivation of this technique in the literature although the technique presented here produces an algorithm that could also be derived starting from barycentric coordinates. A discussion of this relationship is included in the appendix for this paper. Before extending the algorithm to three (and higher dimensional spaces) and showing how it can simplify Ray-Tracing, particularly when doing z-buffering, we would like to enumerate some of its advantages and disadvantages. One traditional method of determining containment in a triangle, or convex polygon, is to generate the equations for the bounding lines and then to determine which side of each bounding line the point falls on. A second technique is based on the Jorden curve theorem. footnote1 I believe there are several reasons why the advantages of the triangle and hypertriangle containment algorithms presented here are not commonly used. One reason is that most computer 3-D graphics geometry has been based on homogeneous footnote7 system of coordinates and transforms taken from the theory of projective geometry, rather than affine transformations based in the theory of linear algebra. Another reason is that normally a basis for the space would be constructed from the vectors (v2 - v1 ) and (v3 - v1) ( instead of (v3 - v2) ) so that hidden advantages of choosing other sets of vectors for the basis of the space have not been explored. We will call techniques, such as the one presented above, in which the vectors are not constructed from a common origin, Free Choice techniques. We will call techniques in which a common origin is used, Common Origin techniques. In common origin techniques, one point in the triangle, ( or hyper-triangle ) is chosen as the origin. In order to generate the set of vectors that form the basis for the new coordinate system, the value of this origin is subtracted from the values of the remaining points in the triangle. I posted a common-origin algorithm on the Internet without comment about its derivation and recieved a reply from Prof. Dr. Heinrich Giesen pointing out that it is equivalent to the Barycentric coordinate technique, which is a well known technique. The demonstration of equivalency is included in the Appendix . We will not use the common origin technique in this paper because by using free choice techniques, we can customize the results of our basis change to give us additional information that is useful and increases the efficiency of our algorithms. Multi Dimensional Extensions: The techniques presented above are easily extended to multi-deminsional spaces. Let Tri( v1, v2, ... , vn) be a hypertriangle in (n-1) -space. Given a point x, determine if x is interior to Tri( v1, v2, ... , vn) . In order to make this determination use vectors from the hypertriangle Tri( v1, v2, ... , vn) to form a basis for the space. The Free Choice Extension: Any point x can be represented by a parametric equation: (B.) x = v1 + p1( v2 - v1) + p2( v3 - v2) + ... + pn-1( vn - vn-1) When the following conditions are true, the point is contained in the hypertriangle. 1. 0 < pi < 1 2. Given any i , j such that i < j then pi > = pj Common Origin Extension: In the common origin technique represent an arbitrary point x as follows: (C.) x = v1 + p1( v2 - v1) + p2( v3 - v1) + ... + pn-1( vn - v1) When the following conditions are true, the point is contained in the hypertriangle. 1. 0 < pi < 1 2. p1 + p2 + ... + pn < 1 . Given the triangle Tri( v1, v2, ... , vn) and x we can calculate p1 + ... + pn. Given the triangle Tri( v1, v2, ... , vn) alone we can calculate a working matrix W = Inv( M ) such that ( x - v1) W =[p1, p2, ... , pn] . In this paper we will most frequently use the free choice technique to choose vectors with which to calculate the matrix. Two Perspective Problems: There are two perspective problems that are easily solved using hypertriangle containment. The two problems for which we disclose new solutions here are, 1. The ray tracing perspective projection problem. 2. The standard perspective problem. The Standard Perspective Problem: The standard perspective problem is as follows. Figure 4 We are given the following information: 1. The location of a single point t, in world coordinates in three-space. 2. The location of the focal point f, of an eye or a camera in world coordinates in three space. 3. The location of the projection plane P in world coordinates in three space. This location is determined by a set of three vectors. P is defined by the set { r1, r2, r3 } . footnote2 We are asked to determine the point at which a line from the focal point of the eye f to the single point t intersects the projection plane P. If this point of intersection exists, we will call it t'. We are asked to determine the coordinates of t' in the rectangular coordinate system of the projection plane P. The projection plane represents the surface of a video display device, such as a CRT tube and the coordinate system in which we want the information returned is the two dimensional pixel coordinates of the CRT tube. The Ray Tracing Perspective Problem: The ray tracing perspective problem is as follows, Figure 5 We are given the following information: 1. The location of the focal point, f of an eye or a camera in world coordinates in three space. 2. The location of the projection plane P in world coordinates in three space, (this is three points, the origin of the screen, the upper left of the screen and the lower right). 3. A point x on P in world coordinates footnote3 4. A two dimensional triangle T = Tri( v1, v2, v3 ) in world coordinates. This is a two dimensional triangle embedded in three space, its verticies are vectors with three coordinates. In the real world systems, the triangle is a portion of the surface of an object being ray-traced. We are asked to determine two different things: 1. Does the line starting at the focal point f and passing through the point x, intersect the triangle T? If the intersect exists call it x'. 2. If the intersection exists, what is a measure of the distance from the point x to its intersection on the triangle T at x'. Ray Tracing Problem Solved: Let us use the free choice tetrahedron containment algorithm to develope a ray tracing perspective technique. If the line starting at the focal point f and passing through the point x intersects the triangle T, the first item we are asked to determine, is equivalent to asking if the point x is contained in the tetrahedron Tri( v1, v2, v3, f) . That is, is x contained in the tetrahedron defined by the union of the triangle with the focal point.? ( T U f ). The second item we are asked to determine, is a measure of the distance from x to its intersection on T. We use this measure for z-buffering. We get this measure as a side benefit when we use the free choice technique of detecting whether x is in Tri( v1, v2, v3, f ) . Let the point x be represented as: footnote4 (D.) x = f + p1( v1 - f) + p2( v2 - v1) + p3( v3 - v2) Calculate the working matrix W = Inv( M ) that transforms a point into the new coordinate system represented by the above equation. The three by three matrix of row vectors vectors M is represented as: M = | v1 - f | | v2 - v1 | | v3 - v2 | from the three by three matrix M calculate W = Inv( M ). Represent W = Inv( M ) as a matrix of column vectors. W = | c1 c2 c3 | The algorithm to obtain the information we need is then as follows: 1. Calculate the dot product p1 = ( x - f) * c1 . If this product is greater than one or less than zero the algorithm terminates. Point x is not in the tetrahedron. 2. Calculate the dot product p2 = ( x - f) * c2 . If this product is greater than p1 or less than zero the algorithm terminates. Point x is not in the tetrahedron. 3. Calculate the dot product p3 = ( x - f) * c3 . If this product is greater than p2 or less than zero the algorithm terminates. Point x is not in the tetrahedron. 4. If the algorithm has not terminated, and we reach this step, We can use p1 as a measure of the distance from x to the triangle T since p1 is simply the ratio of the length of the line segment ( f, x) to the length of the line segment ( f, x') where x' is the point at which the line intersects T. Since ( f, x) has a fixed length, we can use the ratio as a measure. In an actual computer system several things must happen in order to perform a ray tracing of a world object. First, areas that are not partially contained on the screen are clipped. One technique for doing this is disclosed as part of the algorithm for the standard perspective technique footnote5, then the real world coordinates for each pixel on the display screen is generated, then the ray from the focal point through the screen pixel is compared against triangles. The value of p1, our measure, is used for z-buffering to determine which points are in front of or behind other points. Standard Perspective Problem Solved: In the standard perspective problem we are given the following information: 1. The location of a single point t in world coordinates in three-space. 2. The location of the focal point f of an eye or a camera in world coordinates in three-space. 3. The location of the projection plane P in world coordinates in three space, (this is three points, the origin of the screen, the upper left of the screen and the lower right.). Let the viewing area of P that we are interested in be represent by three coordinates in world-space. P = { r1, r2, r3 } . That is, P is represented by the set of three vectors { r1, r2, r3 } . In "real world" situations, the vectors ( r2 - r1 ) and ( r3 - r1 ) are frequently chosen to be orthogonal, simply because the viewing area of the CRT is rectangular and has right angle corners. We can think of r1 as the lower left hand corner of the CRT, r2 as the lower right hand corner and r3 as the upper left hand corner. Let t be represented by the equation, (E.) t = f + p1( v1 - f) + p2( v2 - v1) + p3( v3 - v1) This equation has been generated differently than any of the above equations. It has been constructed this way in order to make two questions easy to answer. 1. Is t a point that can be projected onto P such that t', the projected point is in the rectangle determined by { r1, r2, r3, r2 + ( r3 - r1) } ? 2. What are the coordinates of t' in the two dimensional coordinate system determined by P where: footnote6 1. r1 is chosen to have the coordinates (0,0) 2. r2 is chosen to have the coordinates (1,0) 3. r3 is chosen to have the coordinates (0,1) Now construct W = Inv( M ) from M as determined by equation (E.) above where we express M as: M = | v1 - f | | v2 - v1 | | v3 - v1 | We calculate W = Inv( M ) from M and let the columns of W be represented as: W = | c1 c2 c3 | Now in order to solve the standard perspective problem we do the following: 1. Calculate p1 = ( t - f) * c1 . If p1 < 1 then the point t does not project onto the rectangle of interest on P and the algorithm terminates. 2. Calculate p2 = ( t - f) * c2 . If p2 < 0 or p2 > 1 then the point t does not project onto the rectangle of interest on P and the algorithm terminates. 3. Calculate p3 = ( t - f) * c3. If p3 < 0 or p3 > 1 then the point t does not project onto the rectangle of interest on P and the algorithm terminates. 4. If the algorithm has not terminated, then the point t does project onto P in the area of interest and t' has the coordinates t' = ( p2/p1, p3/p1 ) Optimizing the algorithm: There are several ways in which the algorithm can be optimized. Without going into extensive detail we will give several of them here. Some properties of the triangles are invarient from different viewpoints. In the ray tracing problem only one of the rows of the three by three matrix M depends upon the viewpoint when the matrix is generated using the free-choice technique. Consequently, two rows of the matrix M are invarient and need be calculated only once for all viewpoints. This has the added benefit, that if the inversion is done by calculating the determinant by expansion of minterms, some of the minterms need be calculated only once for all viewpoints. Optimizations similar to the above can be realized for triangles that share a common edge. One can avoid dividing by the determinant when calculating the inverses and postpone this computation until the comparisons have been made. In this case comparisons are made against the values of the determinant instead of one, and the divisions are only made if the containment has been established and we need to complete the computation. Any set of four non-coplanar (non-colinear) points in three space can act as a basis for the space. From these four points we can find an affine transformation that takes any point in world space into a new coordinate system defined by these points. We can also find an inverse transformation that takes points from our new coordinate system back into world space. The affine transformation shares the advantages of the homogeneous coordinate system with transforms. In both systems it is possible to multiply (concatenate) transforms in order to obtain a new transform equivalent to applying the transforms in sequence. Transforms for scaling, reflecting, rotating and distorting are easily constructed and combined and the inverses of these operations are easily found. This fact is not new, and has been mentioned in the literature before. The main arguments in favor of using a homogeneous coordinate system have been that, first, it reduces the complexity of code. With modern object oriented languages the code is only minimally more complex for the basic operations with a great increase in simplicity for more complex operations. Secondly, homogeneous coordinate systems are used because of the ease of explaining there use and for historical reasons. This paper is an outgrowth of a larger research project in computer graphics that began with a 3-D modelling and display program that ran on an Apple II-E written around 1983. That system did not use a homogeneous system of coordinates and transformations but used affine transforms instead to translate points and calculate perspective. The free choice algorithms are a recent invention derived from that work. Containment is calculated by generating an affine transformation that takes the the point we are interested into a space in which simple comparisons can determine containment and the new coordinate system contains desirable information. In that 1983 computer system, "cameras", that is coordinate systems associated with a viewpoint were stored or created from four points in three space. For orthographic projections the three vectors generated from these four points were orthogonal. Each camera could be used to generate an affine transformation that would move a vector from world space to camera space. Perspective transforms were done as they are traditionally done rather than as presented herein above. Transforms could be convolved into new transforms as they are in systems using homogeneous coordinates. Inverses of transforms could also be calculated to take a vector from camera space to world space. Transforms could also be converted back to cameras. The system provided a simple language in which sequences of transforms and objects could be generated mathematically. Some major advantages of the system were. 1. It was significantly faster than equivalent systems on the same machine. 2. Planes and lines did not need to be expressed in their cartesian form since they were easily expressed simply as two points or three points respectively. 3. Projections onto polygons were simplified. 4. The 30% overhead associated with storage of homogeneous coordinate system matricies was avoided. 5. Transformations from any camera (coordinate system) to any other camera in the system was easily and simply achieved. On a completely biased note, I prefer the kind of system presented here not only because it is fast, but because the Mathematics of what is happening appears to me to be simpler and more transparent to a user of the system. --------------------------------------------------------------------------- Appendix: The Barycentric Coordinate Technique Represent an arbitrary point x using the equation: (F.) x = v1 + p1( v2 - v1) + p2( v3 - v1) Now the point x is contained in the triangle only when all of the following conditions hold: 1. When 0 < p2 and 2. When 0 < p1 and 3. When p1 + p2 < 1 . We call this technique, the common origin technique. Figure 3 This is based upon a traditional convention that when calculating a new basis for a space, the origin of the vectors originate from a common point. This is equivalent to the using barycentric coordinates. Barycentric coordinates are based upon the fact that any point can be represented as the sum of the verticies of a triangle times a weight, where the sum of the weights equals one. (G.) 1. x = p0v1 + p1v2 + p2v3 2. p0 + p1 + p2 = 1 Let p0 = 1 - p1 - p2, then (G.)-1 above becomes x = (1 - p1 - p2) v1 + p1v2 + p2v3 x = v1 + p1( v2 - v1) + p2( v3 - v1) This is identical to (F.) above. Return to referance to appendix --------------------------------------------------------------------------- Foot Notes * footnote 1, Triangle Containment Techniques Compared Several of these techniques are compared by Eric Haines in Volume 5, Number 3, September 2, 1992, of the Ray Tracing News, an internet electronic journal. For triangles, his version of the barycentric coordinate system algorithm worked best for triangles, but the advantages were rapidly lost for polygons with more than three sides. We have some optimizations of the algorithm that drastically speed up these calculations. Return to place document * footnote 2, Coordinates of CRT That is, the three points { r1, r2, r3 } determine a rectalinear area in three space that we are interested in, possibly the origin, the upper left hand corner and the lower right hand corner of a CRT tube. Return to place document * footnote 3, Translating pixel to world coordinates. Translating pixel coordinates to world coordinates is easily accomplished. Let w0 be the world space coordinate of the origin of the screen at pixel coordinates (0,0) , let w1 be the world space coordinates of the top left of the screen at pixel coordinates (0,399) , let w2 be the world space coordinates of the bottom right of the screen at pixel coordinates (639,0) . . The world space coordinates of (X,Y) is then w0 + Y( w1 - w0 )/399 + X( w2 - w0 )/639. Generate 640 values for x and 400 values for y and access them by their indicies to avoid frequent recalculations when generating scan lines. Return to place document * footnote 4, Other free choice vector constructs It is also possible to substitute a representation as in equation (E.) below for equation (D.) and change some of the checking conditions. This may be desirable in some real world programs. Return to place document * footnote5, Other algorithms for clipping are known. There are other more effective ways of doing this clipping when using BSD trees and other data structures that partition the world space, rather than depending on the algorithms presented here alone. Return to place document * footnote6, Coordinates for projection plane should match CRT This coordinate system is used to make reading this paper easy. In "real world" computer applications, the coordinates would be chosen to represent pixel coordinates on a CRT tube. In otherwords, for a full screen 400 X 640 VGA system appropriate coordinates might be r1=(0,0), r2=(640,0), r3=(0,400). Return to place document * footnote7, Definition of homogeneous "homogenous", as used here does NOT mean a homogeneous system of equations, but derives from a projective geometry construct. Homogeneous coordinates are used in computer graphics as a redundant method of storing vectors. That is in 3-space a vector of length 4 is used to store a coordinate. The fourth coordinate is used to scale the first three coordinates. For example (12, 8, 4, 4), and (9, 6, 3, 3) both represent the coordinate (3, 2, 1). In a homogenous system of coordinates, the equivalent of a matrix multiply, combined with a vector addition, is stored in a four by four matrix. Return to place document --------------------------------------------------------------------------- To MathVision Inc., (formerly 7seas software) Corporate page.