1 /* 2 Copyright (C) 1996-1997 Id Software, Inc. 3 4 This program is free software; you can redistribute it and/or 5 modify it under the terms of the GNU General Public License 6 as published by the Free Software Foundation; either version 2 7 of the License, or (at your option) any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 12 13 See the GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; if not, write to the Free Software 17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 18 19 */ 20 // gl_mesh.c: triangle model functions 21 22 #include "quakedef.h" 23 24 /* 25 ================================================================= 26 27 ALIAS MODEL DISPLAY LIST GENERATION 28 29 ================================================================= 30 */ 31 32 model_t *aliasmodel; 33 aliashdr_t *paliashdr; 34 35 qboolean used[8192]; 36 37 // the command list holds counts and s/t values that are valid for 38 // every frame 39 int commands[8192]; 40 int numcommands; 41 42 // all frames will have their vertexes rearranged and expanded 43 // so they are in the order expected by the command list 44 int vertexorder[8192]; 45 int numorder; 46 47 int allverts, alltris; 48 49 int stripverts[128]; 50 int striptris[128]; 51 int stripcount; 52 53 /* 54 ================ 55 StripLength 56 ================ 57 */ 58 int StripLength (int starttri, int startv) 59 { 60 int m1, m2; 61 int j; 62 mtriangle_t *last, *check; 63 int k; 64 65 used[starttri] = 2; 66 67 last = &triangles[starttri]; 68 69 stripverts[0] = last->vertindex[(startv)%3]; 70 stripverts[1] = last->vertindex[(startv+1)%3]; 71 stripverts[2] = last->vertindex[(startv+2)%3]; 72 73 striptris[0] = starttri; 74 stripcount = 1; 75 76 m1 = last->vertindex[(startv+2)%3]; 77 m2 = last->vertindex[(startv+1)%3]; 78 79 // look for a matching triangle 80 nexttri: 81 for (j=starttri+1, check=&triangles[starttri+1] ; j<pheader->numtris ; j++, check++) 82 { 83 if (check->facesfront != last->facesfront) 84 continue; 85 for (k=0 ; k<3 ; k++) 86 { 87 if (check->vertindex[k] != m1) 88 continue; 89 if (check->vertindex[ (k+1)%3 ] != m2) 90 continue; 91 92 // this is the next part of the fan 93 94 // if we can't use this triangle, this tristrip is done 95 if (used[j]) 96 goto done; 97 98 // the new edge 99 if (stripcount & 1) 100 m2 = check->vertindex[ (k+2)%3 ]; 101 else 102 m1 = check->vertindex[ (k+2)%3 ]; 103 104 stripverts[stripcount+2] = check->vertindex[ (k+2)%3 ]; 105 striptris[stripcount] = j; 106 stripcount++; 107 108 used[j] = 2; 109 goto nexttri; 110 } 111 } 112 done: 113 114 // clear the temp used flags 115 for (j=starttri+1 ; j<pheader->numtris ; j++) 116 if (used[j] == 2) 117 used[j] = 0; 118 119 return stripcount; 120 } 121 122 /* 123 =========== 124 FanLength 125 =========== 126 */ 127 int FanLength (int starttri, int startv) 128 { 129 int m1, m2; 130 int j; 131 mtriangle_t *last, *check; 132 int k; 133 134 used[starttri] = 2; 135 136 last = &triangles[starttri]; 137 138 stripverts[0] = last->vertindex[(startv)%3]; 139 stripverts[1] = last->vertindex[(startv+1)%3]; 140 stripverts[2] = last->vertindex[(startv+2)%3]; 141 142 striptris[0] = starttri; 143 stripcount = 1; 144 145 m1 = last->vertindex[(startv+0)%3]; 146 m2 = last->vertindex[(startv+2)%3]; 147 148 149 // look for a matching triangle 150 nexttri: 151 for (j=starttri+1, check=&triangles[starttri+1] ; j<pheader->numtris ; j++, check++) 152 { 153 if (check->facesfront != last->facesfront) 154 continue; 155 for (k=0 ; k<3 ; k++) 156 { 157 if (check->vertindex[k] != m1) 158 continue; 159 if (check->vertindex[ (k+1)%3 ] != m2) 160 continue; 161 162 // this is the next part of the fan 163 164 // if we can't use this triangle, this tristrip is done 165 if (used[j]) 166 goto done; 167 168 // the new edge 169 m2 = check->vertindex[ (k+2)%3 ]; 170 171 stripverts[stripcount+2] = m2; 172 striptris[stripcount] = j; 173 stripcount++; 174 175 used[j] = 2; 176 goto nexttri; 177 } 178 } 179 done: 180 181 // clear the temp used flags 182 for (j=starttri+1 ; j<pheader->numtris ; j++) 183 if (used[j] == 2) 184 used[j] = 0; 185 186 return stripcount; 187 } 188 189 190 /* 191 ================ 192 BuildTris 193 194 Generate a list of trifans or strips 195 for the model, which holds for all frames 196 ================ 197 */ 198 void BuildTris (void) 199 { 200 int i, j, k; 201 int startv; 202 mtriangle_t *last, *check; 203 int m1, m2; 204 int striplength; 205 trivertx_t *v; 206 mtriangle_t *tv; 207 float s, t; 208 int index; 209 int len, bestlen, besttype; 210 int bestverts[1024]; 211 int besttris[1024]; 212 int type; 213 214 union { 215 float f; 216 int i; 217 } temp; 218 // 219 // build tristrips 220 // 221 numorder = 0; 222 numcommands = 0; 223 memset (used, 0, sizeof(used)); 224 for (i=0 ; i<pheader->numtris ; i++) 225 { 226 // pick an unused triangle and start the trifan 227 if (used[i]) 228 continue; 229 230 bestlen = 0; 231 besttype = 0; 232 for (type = 0 ; type < 2 ; type++) 233 // type = 1; 234 { 235 for (startv =0 ; startv < 3 ; startv++) 236 { 237 if (type == 1) 238 len = StripLength (i, startv); 239 else 240 len = FanLength (i, startv); 241 if (len > bestlen) 242 { 243 besttype = type; 244 bestlen = len; 245 for (j=0 ; j<bestlen+2 ; j++) 246 bestverts[j] = stripverts[j]; 247 for (j=0 ; j<bestlen ; j++) 248 besttris[j] = striptris[j]; 249 } 250 } 251 } 252 253 // mark the tris on the best strip as used 254 for (j=0 ; j<bestlen ; j++) 255 used[besttris[j]] = 1; 256 257 if (besttype == 1) 258 commands[numcommands++] = (bestlen+2); 259 else 260 commands[numcommands++] = -(bestlen+2); 261 262 for (j=0 ; j<bestlen+2 ; j++) 263 { 264 // emit a vertex into the reorder buffer 265 k = bestverts[j]; 266 vertexorder[numorder++] = k; 267 268 // emit s/t coords into the commands stream 269 s = stverts[k].s; 270 t = stverts[k].t; 271 if (!triangles[besttris[0]].facesfront && stverts[k].onseam) 272 s += pheader->skinwidth / 2; // on back side 273 s = (s + 0.5) / pheader->skinwidth; 274 t = (t + 0.5) / pheader->skinheight; 275 276 temp.f = s; 277 commands[numcommands++] = temp.i; 278 temp.f = t; 279 commands[numcommands++] = temp.i; 280 } 281 } 282 283 commands[numcommands++] = 0; // end of list marker 284 285 Con_DPrintf ("%3i tri %3i vert %3i cmd\n", pheader->numtris, numorder, numcommands); 286 287 allverts += numorder; 288 alltris += pheader->numtris; 289 } 290 291 292 /* 293 ================ 294 GL_MakeAliasModelDisplayLists 295 ================ 296 */ 297 void GL_MakeAliasModelDisplayLists (model_t *m, aliashdr_t *hdr) 298 { 299 int i, j; 300 maliasgroup_t *paliasgroup; 301 int *cmds; 302 trivertx_t *verts; 303 char cache[MAX_QPATH], fullpath[MAX_OSPATH], *c; 304 FILE *f; 305 int len; 306 byte *data; 307 308 aliasmodel = m; 309 paliashdr = hdr; // (aliashdr_t *)Mod_Extradata (m); 310 311 // 312 // look for a cached version 313 // 314 strcpy (cache, "glquake/"); 315 COM_StripExtension (m->name+strlen("progs/"), cache+strlen("glquake/")); 316 strcat (cache, ".ms2"); 317 318 COM_FOpenFile (cache, &f); 319 if (f) 320 { 321 fread (&numcommands, 4, 1, f); 322 fread (&numorder, 4, 1, f); 323 fread (&commands, numcommands * sizeof(commands[0]), 1, f); 324 fread (&vertexorder, numorder * sizeof(vertexorder[0]), 1, f); 325 fclose (f); 326 } 327 else 328 { 329 // 330 // build it from scratch 331 // 332 Con_Printf ("meshing %s...\n",m->name); 333 334 BuildTris (); // trifans or lists 335 336 // 337 // save out the cached version 338 // 339 sprintf (fullpath, "%s/%s", com_gamedir, cache); 340 f = fopen (fullpath, "wb"); 341 if (f) 342 { 343 fwrite (&numcommands, 4, 1, f); 344 fwrite (&numorder, 4, 1, f); 345 fwrite (&commands, numcommands * sizeof(commands[0]), 1, f); 346 fwrite (&vertexorder, numorder * sizeof(vertexorder[0]), 1, f); 347 fclose (f); 348 } 349 } 350 351 352 // save the data out 353 354 paliashdr->poseverts = numorder; 355 356 cmds = (int*) Hunk_Alloc (numcommands * 4); 357 paliashdr->commands = (byte *)cmds - (byte *)paliashdr; 358 memcpy (cmds, commands, numcommands * 4); 359 360 verts = (trivertx_t*) Hunk_Alloc (paliashdr->numposes * paliashdr->poseverts 361 * sizeof(trivertx_t) ); 362 paliashdr->posedata = (byte *)verts - (byte *)paliashdr; 363 for (i=0 ; i<paliashdr->numposes ; i++) 364 for (j=0 ; j<numorder ; j++) 365 *verts++ = poseverts[i][vertexorder[j]]; 366 } 367 368