1/*
2Copyright (C) 1996-1997 Id Software, Inc.
3
4This program is free software; you can redistribute it and/or
5modify it under the terms of the GNU General Public License
6as published by the Free Software Foundation; either version 2
7of the License, or (at your option) any later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13See the GNU General Public License for more details.
14
15You should have received a copy of the GNU General Public License
16along with this program; if not, write to the Free Software
17Foundation, 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
27ALIAS MODEL DISPLAY LIST GENERATION
28
29=================================================================
30*/
31
32model_t		*aliasmodel;
33aliashdr_t	*paliashdr;
34
35qboolean	used[8192];
36
37// the command list holds counts and s/t values that are valid for
38// every frame
39int		commands[8192];
40int		numcommands;
41
42// all frames will have their vertexes rearranged and expanded
43// so they are in the order expected by the command list
44int		vertexorder[8192];
45int		numorder;
46
47int		allverts, alltris;
48
49int		stripverts[128];
50int		striptris[128];
51int		stripcount;
52
53/*
54================
55StripLength
56================
57*/
58int	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
80nexttri:
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	}
112done:
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===========
124FanLength
125===========
126*/
127int	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
150nexttri:
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	}
179done:
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================
192BuildTris
193
194Generate a list of trifans or strips
195for the model, which holds for all frames
196================
197*/
198void BuildTris (void)
199{
200	int		i, j, k;
201	int		startv;
202	float	s, t;
203	int		len, bestlen, besttype;
204	int		bestverts[1024];
205	int		besttris[1024];
206	int		type;
207
208	//
209	// build tristrips
210	//
211	numorder = 0;
212	numcommands = 0;
213	besttype = 0;
214	memset (used, 0, sizeof(used));
215	for (i=0 ; i<pheader->numtris ; i++)
216	{
217		// pick an unused triangle and start the trifan
218		if (used[i])
219			continue;
220
221		bestlen = 0;
222		for (type = 0 ; type < 2 ; type++)
223//	type = 1;
224		{
225			for (startv =0 ; startv < 3 ; startv++)
226			{
227				if (type == 1)
228					len = StripLength (i, startv);
229				else
230					len = FanLength (i, startv);
231				if (len > bestlen)
232				{
233					besttype = type;
234					bestlen = len;
235					for (j=0 ; j<bestlen+2 ; j++)
236						bestverts[j] = stripverts[j];
237					for (j=0 ; j<bestlen ; j++)
238						besttris[j] = striptris[j];
239				}
240			}
241		}
242
243		// mark the tris on the best strip as used
244		for (j=0 ; j<bestlen ; j++)
245			used[besttris[j]] = 1;
246
247		if (besttype == 1)
248			commands[numcommands++] = (bestlen+2);
249		else
250			commands[numcommands++] = -(bestlen+2);
251
252		for (j=0 ; j<bestlen+2 ; j++)
253		{
254			// emit a vertex into the reorder buffer
255			k = bestverts[j];
256			vertexorder[numorder++] = k;
257
258			// emit s/t coords into the commands stream
259			s = stverts[k].s;
260			t = stverts[k].t;
261			if (!triangles[besttris[0]].facesfront && stverts[k].onseam)
262				s += pheader->skinwidth / 2;	// on back side
263			s = (s + 0.5) / pheader->skinwidth;
264			t = (t + 0.5) / pheader->skinheight;
265
266			*(float *)&commands[numcommands++] = s;
267			*(float *)&commands[numcommands++] = t;
268		}
269	}
270
271	commands[numcommands++] = 0;		// end of list marker
272
273	Con_DPrintf ("%3i tri %3i vert %3i cmd\n", pheader->numtris, numorder, numcommands);
274
275	allverts += numorder;
276	alltris += pheader->numtris;
277}
278
279
280/*
281================
282GL_MakeAliasModelDisplayLists
283================
284*/
285void GL_MakeAliasModelDisplayLists (model_t *m, aliashdr_t *hdr)
286{
287	int		i, j;
288	int			*cmds;
289	trivertx_t	*verts;
290	char	cache[MAX_QPATH], fullpath[MAX_OSPATH];
291	FILE	*f;
292
293	aliasmodel = m;
294	paliashdr = hdr;	// (aliashdr_t *)Mod_Extradata (m);
295
296	//
297	// look for a cached version
298	//
299	strcpy (cache, "glquake/");
300	COM_StripExtension (m->name+strlen("progs/"), cache+strlen("glquake/"));
301	strcat (cache, ".ms2");
302
303	COM_FOpenFile (cache, &f);
304	if (f)
305	{
306		fread (&numcommands, 4, 1, f);
307		fread (&numorder, 4, 1, f);
308		fread (&commands, numcommands * sizeof(commands[0]), 1, f);
309		fread (&vertexorder, numorder * sizeof(vertexorder[0]), 1, f);
310		fclose (f);
311	}
312	else
313	{
314		//
315		// build it from scratch
316		//
317		Con_Printf ("meshing %s...\n",m->name);
318
319		BuildTris ();		// trifans or lists
320
321		//
322		// save out the cached version
323		//
324		sprintf (fullpath, "%s/%s", com_gamedir, cache);
325		f = fopen (fullpath, "wb");
326		if (!f) {
327			char gldir[MAX_OSPATH];
328
329			sprintf (gldir, "%s/glquake", com_gamedir);
330			Sys_mkdir (gldir);
331			f = fopen (fullpath, "wb");
332		}
333
334		if (f)
335		{
336			fwrite (&numcommands, 4, 1, f);
337			fwrite (&numorder, 4, 1, f);
338			fwrite (&commands, numcommands * sizeof(commands[0]), 1, f);
339			fwrite (&vertexorder, numorder * sizeof(vertexorder[0]), 1, f);
340			fclose (f);
341		}
342	}
343
344
345	// save the data out
346
347	paliashdr->poseverts = numorder;
348
349	cmds = Hunk_Alloc (numcommands * 4);
350	paliashdr->commands = (byte *)cmds - (byte *)paliashdr;
351	memcpy (cmds, commands, numcommands * 4);
352
353	verts = Hunk_Alloc (paliashdr->numposes * paliashdr->poseverts
354		* sizeof(trivertx_t) );
355	paliashdr->posedata = (byte *)verts - (byte *)paliashdr;
356	for (i=0 ; i<paliashdr->numposes ; i++)
357		for (j=0 ; j<numorder ; j++)
358			*verts++ = poseverts[i][vertexorder[j]];
359}
360
361