$search
00001 /* 00002 Szymon Rusinkiewicz 00003 Stanford Graphics Lab 00004 00005 trimesh_tstrips.cc 00006 Computation of triangle strips. 00007 */ 00008 00009 #include <stdio.h> 00010 #include "trimesh.h" 00011 #include "triutil.h" 00012 00013 namespace trimesh { 00014 00015 static bool *done; 00016 static int *next_tstrip_vert; 00017 static int numtstrips; 00018 00019 00020 // Figure out the next triangle we're headed for... 00021 inline int TriMesh::Tstrip_Next_Tri(int tri, int v1, int v2, bool flip) 00022 { 00023 for (int t=0, n=numadjacentfaces[v1]; t < n; t++) { 00024 int f = adjacentfaces[v1][t]; 00025 if ((f == tri) || done[f]) 00026 continue; 00027 for (int i=0; i < 3; i++) { 00028 int j = (i+(flip?2:1)) % 3; 00029 if ((faces[f][i] == v1) && (faces[f][j] == v2)) 00030 return f; 00031 } 00032 } 00033 00034 // Couldn't find one... 00035 return -1; 00036 } 00037 00038 inline int TriMesh::Tstrip_Next_Vert(int next, int vlast1, int vlast2) 00039 { 00040 for (int i=0; i < 3; i++) { 00041 int vnext = faces[next][i]; 00042 if ((vnext == vlast1) || (vnext == vlast2)) 00043 continue; 00044 return vnext; 00045 } 00046 00047 // Can't happen 00048 return -1; 00049 } 00050 00051 00052 // Build a whole strip of triangles, as long as possible... 00053 void TriMesh::Tstrip_Crawl(int v1, int v2, int v3, int next) 00054 { 00055 // Insert the first tri... 00056 *next_tstrip_vert++ = v1; 00057 *next_tstrip_vert++ = v2; 00058 *next_tstrip_vert++ = v3; 00059 00060 int vlast2 = v2; 00061 int vlast1 = v3; 00062 00063 bool flip = true; 00064 // Main loop... 00065 do { 00066 // Find the next vertex 00067 int vnext = Tstrip_Next_Vert(next, vlast1, vlast2); 00068 00069 // Record it 00070 *next_tstrip_vert++ = vnext; 00071 done[next] = true; 00072 00073 flip = !flip; 00074 vlast2 = vlast1; 00075 vlast1 = vnext; 00076 00077 // Try to find the next tri 00078 } while ((next = Tstrip_Next_Tri(next, vlast2, vlast1, flip)) != -1); 00079 } 00080 00081 00082 // Begin a tstrip, starting with triangle tri 00083 void TriMesh::Tstrip_Bootstrap(int tri) 00084 { 00085 done[tri] = true; 00086 00087 // Find two vertices with which to start. 00088 // We do a bit of lookahead... 00089 00090 int vert1 = faces[tri][0]; 00091 int vert2 = faces[tri][1]; 00092 int vert3 = faces[tri][2]; 00093 00094 // Try vertices 1 and 2... 00095 int len12 = 1; 00096 int nextface12 = Tstrip_Next_Tri(tri, vert1, vert2, true); 00097 if (nextface12 != -1) { 00098 len12++; 00099 if (Tstrip_Next_Tri(nextface12, 00100 vert2, 00101 Tstrip_Next_Vert(nextface12, vert2, vert1), 00102 false) != -1) 00103 len12++; 00104 } 00105 00106 // Try vertices 2 and 3... 00107 int len23 = 1; 00108 int nextface23 = Tstrip_Next_Tri(tri, vert2, vert3, true); 00109 if (nextface23 != -1) { 00110 len23++; 00111 if (Tstrip_Next_Tri(nextface23, 00112 vert3, 00113 Tstrip_Next_Vert(nextface23, vert3, vert2), 00114 false) != -1) 00115 len23++; 00116 } 00117 00118 // Try vertices 3 and 1... 00119 int len31 = 1; 00120 int nextface31 = Tstrip_Next_Tri(tri, vert3, vert1, true); 00121 if (nextface31 != -1) { 00122 len31++; 00123 if (Tstrip_Next_Tri(nextface31, 00124 vert1, 00125 Tstrip_Next_Vert(nextface31, vert1, vert3), 00126 false) != -1) 00127 len31++; 00128 } 00129 00130 if (len12 >= len23) { 00131 if (len12 >= len31) { 00132 if (len12 == 1) { 00133 // Do a single-triangle-long tstrip. 00134 *next_tstrip_vert++ = vert1; 00135 *next_tstrip_vert++ = vert2; 00136 *next_tstrip_vert++ = vert3; 00137 } else { 00138 Tstrip_Crawl(vert3, vert1, vert2, nextface12); 00139 } 00140 } else { 00141 Tstrip_Crawl(vert2, vert3, vert1, nextface31); 00142 } 00143 } else { 00144 if (len23 >= len31) 00145 Tstrip_Crawl(vert1, vert2, vert3, nextface23); 00146 else 00147 Tstrip_Crawl(vert2, vert3, vert1, nextface31); 00148 } 00149 00150 *next_tstrip_vert++ = -1; 00151 numtstrips++; 00152 } 00153 00154 00155 // Turn faces into triangle strips 00156 void TriMesh::FindTStrips() 00157 { 00158 if (!faces) 00159 return; 00160 need_adjacentfaces(); 00161 00162 printf("Building triangle strips... "); fflush(stdout); 00163 00164 // Allocate more than enough memory 00165 if (tstrips) 00166 delete [] tstrips; 00167 tstrips = new int[4*numfaces]; 00168 next_tstrip_vert = tstrips; 00169 numtstrips = 0; 00170 00171 // Allocate array to record what triangles we've already done 00172 done = new bool[numfaces]; 00173 memset(done, 0, numfaces*sizeof(bool)); 00174 00175 // Build the tstrips 00176 for (int i=0; i < numfaces; i++) { 00177 if (!done[i]) 00178 Tstrip_Bootstrap(i); 00179 } 00180 00181 delete [] done; 00182 00183 tstripdatalen = next_tstrip_vert - tstrips; 00184 00185 printf("%d triangle strips... Done.\n", numtstrips); 00186 } 00187 00188 00189 // Unpack triangle strips into faces 00190 void TriMesh::UnpackTStrips() 00191 { 00192 if (!tstrips || tstripdatalen < 4) 00193 return; 00194 00195 printf("Unpacking triangle strips... "); fflush(stdout); 00196 00197 // Count number of faces 00198 numfaces = 0; 00199 int this_tstrip_len = 0; 00200 for (int i=0; i < tstripdatalen; i++) { 00201 if (tstrips[i] == -1) { 00202 this_tstrip_len = 0; 00203 continue; 00204 } 00205 this_tstrip_len++; 00206 if (this_tstrip_len >= 3) 00207 numfaces++; 00208 } 00209 printf("%d triangles... ", numfaces); fflush(stdout); 00210 00211 // Allocate memory 00212 if (faces) 00213 delete [] faces; 00214 faces = new face[numfaces]; 00215 00216 // Write tstrips 00217 int whichface = 0; 00218 this_tstrip_len = 0; 00219 for (int i=0; i < tstripdatalen; i++) { 00220 if (tstrips[i] == -1) { 00221 this_tstrip_len = 0; 00222 continue; 00223 } 00224 this_tstrip_len++; 00225 if (this_tstrip_len < 3) 00226 continue; 00227 if (this_tstrip_len % 2) { 00228 faces[whichface][0] = tstrips[i-2]; 00229 faces[whichface][1] = tstrips[i-1]; 00230 } else { 00231 faces[whichface][0] = tstrips[i-1]; 00232 faces[whichface][1] = tstrips[i-2]; 00233 } 00234 faces[whichface++][2] = tstrips[i]; 00235 } 00236 00237 printf("Done.\n"); 00238 } 00239 00240 } // namespace trimesh