CS 465 Solution 8
(revised November 20, 2004)

Problem 12

1) a) Indexed Triangles
   The indexed triangle solution given is far from the only one. Given
   triangles are impervious to shifts like the following:
   [1 2 3] = [2 3 1] = [3 1 2]
   
   Note that flipping any two vertices will *not* yield the same triangle,
   but rather the same triangle with its normal flipped.
   
   
   [0 5 3]  [0 3 1]   [0 1 2]   [0 2 4]  [0 4 5]  }- These form the "top"
   [11 7 9] [11 9 10] [11 10 8] [11 8 6] [11 6 7] }- Thest form the "bottom"
   [5 9 3]  [3 9 7]   [3 7 1]   [1 7 6]  [1 6 2]  }- These form the "middle"
   [2 6 8]  [2 8 4]   [4 8 10]  [4 10 5] [5 10 9] }
   
   b) Triangle Strips
   There were two types of full credit solutions. In one solution, only three
   strips were used, but some triangles were degenerate (area = 0). In the
   other solution, 5 strips were used. 2 strips were used for each cap, and
   one strip was used for the middle. There are of course many ways to lay out
   each of the strips.
   
   Two common mistakes involved reversing the normals for back faces, and
   not "closing" the middle strip. If a strip is closed, then the first two
   and the last two vertices are the same, and triangle strip is a triangle
   loop of sorts.  In general, triangle strips are not loops.
   
   Degenerate Triangles:
   [3 0 5 0 4 0 2 0 1 0 3]        }- Top Strip
   [10 11 9 11 7 11 6 11 8 11 10] }- Bottom Strip
   [5 9 3 7 1 6 2 8 4 10 5 9]     }- Middle Strip
   
   No Degenerate Triangles:
   [3 1 0 2 4] [4 5 0 3]      }- Top Strips
   [7 9 11 10 8] [8 6 11 7]   }- Bottom Strips
   [5 9 3 7 1 6 2 8 4 10 5 9] }- Middle Strip
   
   c) Triangle Strips and Fans
   The most often made mistakes here were the same as above. Often,
   fans/strips were not closed, or the normals were reversed.
   
   [0 1 2 3 4 5 1]   }- Top Fan
   [11 7 9 10 8 6 7] }- Bottom Fan
   [5 9 3 7 1 6 2 8 4 10 5 9] }- Middle Strip

2) Vertices 1 and 2 are the next vertices which can be added, in that order.

   These *must* be the correct vertices as each "next" vertex must be
   connected via an edge to the last two added. 1 is the only vertex not
   already added which is connected to 5 and 6. The same logic applies in
   choosing 2.
   
3) a) Choosing T'
   It goes without saying that there were many correct algorithms. One of the
   simplest things to do was to observe which vertex index (0, 1, or 2) is not
   in the two most recent elements in S. This information can be used to go
   across the appropriate edge of T using the tNbr data structure.
   
   int v_not_included = S[S.length - 3]; //Grab the 3rd most recent vertex
   if (v_not_included == tInd[T][0]) {
     TPrime = tNbr[T][1];
   } else if (v_not_included == tInd[T][1]) {
     TPrime = tNbr[T][2];
   } else {
     TPrime = tNbr[T][0];
   }
   
   b) Choosing v'
   The next vertex to add to S can be determined simply by examining the three
   vertices of TPrime. Whichever vertex is not in the two most recent elements
   of S is the one to be added.
   
   int v0 = S[S.length - 1];
   int v1 = S[S.length - 2];
   if (tInd[TPrime][0] != v0 && tInd[TPrime][0] != v1) {
     S.append(tInd[TPrime][0]);
   } else if (tInd[TPrime][1] != v0 && tInd[TPrime][1] != v1) {
     S.append(tInd[TPrime][1]);
   } else {
     S.append(tInd[TPrime][2]);
   }