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 */
StripLength(int starttri,int startv)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 */
FanLength(int starttri,int startv)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 */
BuildTris(void)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 */
GL_MakeAliasModelDisplayLists(model_t * m,aliashdr_t * hdr)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