CS121 Project 2

Triangle Standardization Notes (Draft Version)




A triangle ( v0, v1, v2 ) is in standard orientation if v0 is at the origin, v2 is on the positive x axis, and v1 is in the x - positive z half-plane as illustrated below.


These notes describe the algorithm for computing the standardized version of an arbitrary triangle. Code that implements this algorithm can found here. A similar algorithm is used to standardize triangle edges. The code that implements the edge standardization algorithm is here.

Let T= (v0, v1, v2 ) be an arbitrary triangle. (We assume that it is a triangle, i.e. that the points are not co-linear.) We can generate the standard version of the triangle by applying a translation and two rotations to its vertices.
  1. The first step is to translate the triangle so its first vertex is at the origin (Fig. 1). To do this we simply translate each vertex by -v0= (x0, y0, z0). Let T'= (v'0, v'1, v'2 ) be the translated triangle; i.e. v'0 = (0,0,0).
  2. Next we rotate the triangle T' so that its last edge is on the positive x-axis as shown in the figure below.
    Let u be the unit vector from the origin toward the point v'2 and let x=<1,0,0>. There are three cases.
    1. If u=x, the edge is already in position and no rotation is necessary.
    2. If u=-x, the edge lies on the negative x axis. The desired rotation is 180 degrees about the vector <0,1,0>.
    3. Otherwise, u and x define a plane. The normal, n, to this plane is given by their cross product. The cosine of the angle, θ, between them is given by their dot product. We can align u with x by rotating our vertices by θ about n as illustrated in the figure below.
      Here are the necessary computations.
      • u = < x'2, y'2, z'2, >/ ( x'22 + y'22 + z'22 )1/2.
      • n = u X b = < 0, z'2, -y'2 >.
      • θ = arcos ( u dot x ) = arcos(x2)
      Let T''= (v''0, v''1, v''2 ) be the rotated triangle; i.e. v''0 = (0,0,0) and v''2 = (x''2,0,0) for some positive x''2.
  3. Finally, we need to rotate T'' about the x-axis so that it lies in the x-positive z half plane. Note that the angle, β, between T'' and the x- positive z plane is the angle between the vectors <0, y''1, z''1 > and z=<0,0,1>. If y''1 ≥0, then the dot product of these vectors is cos(β). If y''1 ≤ 0, then the dot product yields cos(-β).
Rotation is a linear transformation and can be represented by an appropriate 3x3 matrix transform. Translation, which is not a linear transformation, can be represented by a matrix tranform in 4 dimensions. Thus the net effect of these three transformations can be represented by a 4x4 matrix. In fact, OpenGL will compute this transformation matrix as demonstrated in the standardization code. To transform a 3D point (e.g. the starting or ending positions of the ball) into the triangle's standard frame pass the forwardTransform (compute in the standardize code) to this matrix multiply method for the Tuple class.