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