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// d_sprite.c: software top-level rasterization driver module for drawing
21// sprites
22
23#include "quakedef.h"
24#include "d_local.h"
25
26static int		sprite_height;
27static int		minindex, maxindex;
28static sspan_t	*sprite_spans;
29
30#if	!id386
31
32/*
33=====================
34D_SpriteDrawSpans
35=====================
36*/
37void D_SpriteDrawSpans (sspan_t *pspan)
38{
39	int			count, spancount, izistep;
40	int			izi;
41	byte		*pbase, *pdest;
42	fixed16_t	s, t, snext, tnext, sstep, tstep;
43	float		sdivz, tdivz, zi, z, du, dv, spancountminus1;
44	float		sdivz8stepu, tdivz8stepu, zi8stepu;
45	byte		btemp;
46	short		*pz;
47
48	sstep = 0;	// keep compiler happy
49	tstep = 0;	// ditto
50
51	pbase = cacheblock;
52
53	sdivz8stepu = d_sdivzstepu * 8;
54	tdivz8stepu = d_tdivzstepu * 8;
55	zi8stepu = d_zistepu * 8;
56
57// we count on FP exceptions being turned off to avoid range problems
58	izistep = (int)(d_zistepu * 0x8000 * 0x10000);
59
60	do
61	{
62		pdest = (byte *)d_viewbuffer + (screenwidth * pspan->v) + pspan->u;
63		pz = d_pzbuffer + (d_zwidth * pspan->v) + pspan->u;
64
65		count = pspan->count;
66
67		if (count <= 0)
68			goto NextSpan;
69
70	// calculate the initial s/z, t/z, 1/z, s, and t and clamp
71		du = (float)pspan->u;
72		dv = (float)pspan->v;
73
74		sdivz = d_sdivzorigin + dv*d_sdivzstepv + du*d_sdivzstepu;
75		tdivz = d_tdivzorigin + dv*d_tdivzstepv + du*d_tdivzstepu;
76		zi = d_ziorigin + dv*d_zistepv + du*d_zistepu;
77		z = (float)0x10000 / zi;	// prescale to 16.16 fixed-point
78	// we count on FP exceptions being turned off to avoid range problems
79		izi = (int)(zi * 0x8000 * 0x10000);
80
81		s = (int)(sdivz * z) + sadjust;
82		if (s > bbextents)
83			s = bbextents;
84		else if (s < 0)
85			s = 0;
86
87		t = (int)(tdivz * z) + tadjust;
88		if (t > bbextentt)
89			t = bbextentt;
90		else if (t < 0)
91			t = 0;
92
93		do
94		{
95		// calculate s and t at the far end of the span
96			if (count >= 8)
97				spancount = 8;
98			else
99				spancount = count;
100
101			count -= spancount;
102
103			if (count)
104			{
105			// calculate s/z, t/z, zi->fixed s and t at far end of span,
106			// calculate s and t steps across span by shifting
107				sdivz += sdivz8stepu;
108				tdivz += tdivz8stepu;
109				zi += zi8stepu;
110				z = (float)0x10000 / zi;	// prescale to 16.16 fixed-point
111
112				snext = (int)(sdivz * z) + sadjust;
113				if (snext > bbextents)
114					snext = bbextents;
115				else if (snext < 8)
116					snext = 8;	// prevent round-off error on <0 steps from
117								//  from causing overstepping & running off the
118								//  edge of the texture
119
120				tnext = (int)(tdivz * z) + tadjust;
121				if (tnext > bbextentt)
122					tnext = bbextentt;
123				else if (tnext < 8)
124					tnext = 8;	// guard against round-off error on <0 steps
125
126				sstep = (snext - s) >> 3;
127				tstep = (tnext - t) >> 3;
128			}
129			else
130			{
131			// calculate s/z, t/z, zi->fixed s and t at last pixel in span (so
132			// can't step off polygon), clamp, calculate s and t steps across
133			// span by division, biasing steps low so we don't run off the
134			// texture
135				spancountminus1 = (float)(spancount - 1);
136				sdivz += d_sdivzstepu * spancountminus1;
137				tdivz += d_tdivzstepu * spancountminus1;
138				zi += d_zistepu * spancountminus1;
139				z = (float)0x10000 / zi;	// prescale to 16.16 fixed-point
140				snext = (int)(sdivz * z) + sadjust;
141				if (snext > bbextents)
142					snext = bbextents;
143				else if (snext < 8)
144					snext = 8;	// prevent round-off error on <0 steps from
145								//  from causing overstepping & running off the
146								//  edge of the texture
147
148				tnext = (int)(tdivz * z) + tadjust;
149				if (tnext > bbextentt)
150					tnext = bbextentt;
151				else if (tnext < 8)
152					tnext = 8;	// guard against round-off error on <0 steps
153
154				if (spancount > 1)
155				{
156					sstep = (snext - s) / (spancount - 1);
157					tstep = (tnext - t) / (spancount - 1);
158				}
159			}
160
161			do
162			{
163				btemp = *(pbase + (s >> 16) + (t >> 16) * cachewidth);
164				if (btemp != 255)
165				{
166					if (*pz <= (izi >> 16))
167					{
168						*pz = izi >> 16;
169						*pdest = btemp;
170					}
171				}
172
173				izi += izistep;
174				pdest++;
175				pz++;
176				s += sstep;
177				t += tstep;
178			} while (--spancount > 0);
179
180			s = snext;
181			t = tnext;
182
183		} while (count > 0);
184
185NextSpan:
186		pspan++;
187
188	} while (pspan->count != DS_SPAN_LIST_END);
189}
190
191#endif
192
193
194/*
195=====================
196D_SpriteScanLeftEdge
197=====================
198*/
199void D_SpriteScanLeftEdge (void)
200{
201	int			i, v, itop, ibottom, lmaxindex;
202	emitpoint_t	*pvert, *pnext;
203	sspan_t		*pspan;
204	float		du, dv, vtop, vbottom, slope;
205	fixed16_t	u, u_step;
206
207	pspan = sprite_spans;
208	i = minindex;
209	if (i == 0)
210		i = r_spritedesc.nump;
211
212	lmaxindex = maxindex;
213	if (lmaxindex == 0)
214		lmaxindex = r_spritedesc.nump;
215
216	vtop = ceil (r_spritedesc.pverts[i].v);
217
218	do
219	{
220		pvert = &r_spritedesc.pverts[i];
221		pnext = pvert - 1;
222
223		vbottom = ceil (pnext->v);
224
225		if (vtop < vbottom)
226		{
227			du = pnext->u - pvert->u;
228			dv = pnext->v - pvert->v;
229			slope = du / dv;
230			u_step = (int)(slope * 0x10000);
231		// adjust u to ceil the integer portion
232			u = (int)((pvert->u + (slope * (vtop - pvert->v))) * 0x10000) +
233					(0x10000 - 1);
234			itop = (int)vtop;
235			ibottom = (int)vbottom;
236
237			for (v=itop ; v<ibottom ; v++)
238			{
239				pspan->u = u >> 16;
240				pspan->v = v;
241				u += u_step;
242				pspan++;
243			}
244		}
245
246		vtop = vbottom;
247
248		i--;
249		if (i == 0)
250			i = r_spritedesc.nump;
251
252	} while (i != lmaxindex);
253}
254
255
256/*
257=====================
258D_SpriteScanRightEdge
259=====================
260*/
261void D_SpriteScanRightEdge (void)
262{
263	int			i, v, itop, ibottom;
264	emitpoint_t	*pvert, *pnext;
265	sspan_t		*pspan;
266	float		du, dv, vtop, vbottom, slope, uvert, unext, vvert, vnext;
267	fixed16_t	u, u_step;
268
269	pspan = sprite_spans;
270	i = minindex;
271
272	vvert = r_spritedesc.pverts[i].v;
273	if (vvert < r_refdef.fvrecty_adj)
274		vvert = r_refdef.fvrecty_adj;
275	if (vvert > r_refdef.fvrectbottom_adj)
276		vvert = r_refdef.fvrectbottom_adj;
277
278	vtop = ceil (vvert);
279
280	do
281	{
282		pvert = &r_spritedesc.pverts[i];
283		pnext = pvert + 1;
284
285		vnext = pnext->v;
286		if (vnext < r_refdef.fvrecty_adj)
287			vnext = r_refdef.fvrecty_adj;
288		if (vnext > r_refdef.fvrectbottom_adj)
289			vnext = r_refdef.fvrectbottom_adj;
290
291		vbottom = ceil (vnext);
292
293		if (vtop < vbottom)
294		{
295			uvert = pvert->u;
296			if (uvert < r_refdef.fvrectx_adj)
297				uvert = r_refdef.fvrectx_adj;
298			if (uvert > r_refdef.fvrectright_adj)
299				uvert = r_refdef.fvrectright_adj;
300
301			unext = pnext->u;
302			if (unext < r_refdef.fvrectx_adj)
303				unext = r_refdef.fvrectx_adj;
304			if (unext > r_refdef.fvrectright_adj)
305				unext = r_refdef.fvrectright_adj;
306
307			du = unext - uvert;
308			dv = vnext - vvert;
309			slope = du / dv;
310			u_step = (int)(slope * 0x10000);
311		// adjust u to ceil the integer portion
312			u = (int)((uvert + (slope * (vtop - vvert))) * 0x10000) +
313					(0x10000 - 1);
314			itop = (int)vtop;
315			ibottom = (int)vbottom;
316
317			for (v=itop ; v<ibottom ; v++)
318			{
319				pspan->count = (u >> 16) - pspan->u;
320				u += u_step;
321				pspan++;
322			}
323		}
324
325		vtop = vbottom;
326		vvert = vnext;
327
328		i++;
329		if (i == r_spritedesc.nump)
330			i = 0;
331
332	} while (i != maxindex);
333
334	pspan->count = DS_SPAN_LIST_END;	// mark the end of the span list
335}
336
337
338/*
339=====================
340D_SpriteCalculateGradients
341=====================
342*/
343void D_SpriteCalculateGradients (void)
344{
345	vec3_t		p_normal, p_saxis, p_taxis, p_temp1;
346	float		distinv;
347
348	TransformVector (r_spritedesc.vpn, p_normal);
349	TransformVector (r_spritedesc.vright, p_saxis);
350	TransformVector (r_spritedesc.vup, p_taxis);
351	VectorInverse (p_taxis);
352
353	distinv = 1.0 / (-DotProduct (modelorg, r_spritedesc.vpn));
354
355	d_sdivzstepu = p_saxis[0] * xscaleinv;
356	d_tdivzstepu = p_taxis[0] * xscaleinv;
357
358	d_sdivzstepv = -p_saxis[1] * yscaleinv;
359	d_tdivzstepv = -p_taxis[1] * yscaleinv;
360
361	d_zistepu = p_normal[0] * xscaleinv * distinv;
362	d_zistepv = -p_normal[1] * yscaleinv * distinv;
363
364	d_sdivzorigin = p_saxis[2] - xcenter * d_sdivzstepu -
365			ycenter * d_sdivzstepv;
366	d_tdivzorigin = p_taxis[2] - xcenter * d_tdivzstepu -
367			ycenter * d_tdivzstepv;
368	d_ziorigin = p_normal[2] * distinv - xcenter * d_zistepu -
369			ycenter * d_zistepv;
370
371	TransformVector (modelorg, p_temp1);
372
373	sadjust = ((fixed16_t)(DotProduct (p_temp1, p_saxis) * 0x10000 + 0.5)) -
374			(-(cachewidth >> 1) << 16);
375	tadjust = ((fixed16_t)(DotProduct (p_temp1, p_taxis) * 0x10000 + 0.5)) -
376			(-(sprite_height >> 1) << 16);
377
378// -1 (-epsilon) so we never wander off the edge of the texture
379	bbextents = (cachewidth << 16) - 1;
380	bbextentt = (sprite_height << 16) - 1;
381}
382
383
384/*
385=====================
386D_DrawSprite
387=====================
388*/
389void D_DrawSprite (void)
390{
391	int			i, nump;
392	float		ymin, ymax;
393	emitpoint_t	*pverts;
394	sspan_t		spans[MAXHEIGHT+1];
395
396	sprite_spans = spans;
397
398// find the top and bottom vertices, and make sure there's at least one scan to
399// draw
400	ymin = 999999.9;
401	ymax = -999999.9;
402	pverts = r_spritedesc.pverts;
403
404	for (i=0 ; i<r_spritedesc.nump ; i++)
405	{
406		if (pverts->v < ymin)
407		{
408			ymin = pverts->v;
409			minindex = i;
410		}
411
412		if (pverts->v > ymax)
413		{
414			ymax = pverts->v;
415			maxindex = i;
416		}
417
418		pverts++;
419	}
420
421	ymin = ceil (ymin);
422	ymax = ceil (ymax);
423
424	if (ymin >= ymax)
425		return;		// doesn't cross any scans at all
426
427	cachewidth = r_spritedesc.pspriteframe->width;
428	sprite_height = r_spritedesc.pspriteframe->height;
429	cacheblock = (byte *)&r_spritedesc.pspriteframe->pixels[0];
430
431// copy the first vertex to the last vertex, so we don't have to deal with
432// wrapping
433	nump = r_spritedesc.nump;
434	pverts = r_spritedesc.pverts;
435	pverts[nump] = pverts[0];
436
437	D_SpriteCalculateGradients ();
438	D_SpriteScanLeftEdge ();
439	D_SpriteScanRightEdge ();
440	D_SpriteDrawSpans (sprite_spans);
441}
442
443