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// r_bsp.c
21
22#include "quakedef.h"
23#include "r_local.h"
24
25//
26// current entity info
27//
28qboolean		insubmodel;
29entity_t		*currententity;
30vec3_t			modelorg, base_modelorg;
31								// modelorg is the viewpoint reletive to
32								// the currently rendering entity
33vec3_t			r_entorigin;	// the currently rendering entity in world
34								// coordinates
35
36float			entity_rotation[3][3];
37
38vec3_t			r_worldmodelorg;
39
40int				r_currentbkey;
41
42typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t;
43
44#define MAX_BMODEL_VERTS	500			// 6K
45#define MAX_BMODEL_EDGES	1000		// 12K
46
47static mvertex_t	*pbverts;
48static bedge_t		*pbedges;
49static int			numbverts, numbedges;
50
51static mvertex_t	*pfrontenter, *pfrontexit;
52
53static qboolean		makeclippededge;
54
55
56//===========================================================================
57
58/*
59================
60R_EntityRotate
61================
62*/
63void R_EntityRotate (vec3_t vec)
64{
65	vec3_t	tvec;
66
67	VectorCopy (vec, tvec);
68	vec[0] = DotProduct (entity_rotation[0], tvec);
69	vec[1] = DotProduct (entity_rotation[1], tvec);
70	vec[2] = DotProduct (entity_rotation[2], tvec);
71}
72
73
74/*
75================
76R_RotateBmodel
77================
78*/
79void R_RotateBmodel (void)
80{
81	float	angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3];
82
83// TODO: should use a look-up table
84// TODO: should really be stored with the entity instead of being reconstructed
85// TODO: could cache lazily, stored in the entity
86// TODO: share work with R_SetUpAliasTransform
87
88// yaw
89	angle = currententity->angles[YAW];
90	angle = angle * M_PI*2 / 360;
91	s = sin(angle);
92	c = cos(angle);
93
94	temp1[0][0] = c;
95	temp1[0][1] = s;
96	temp1[0][2] = 0;
97	temp1[1][0] = -s;
98	temp1[1][1] = c;
99	temp1[1][2] = 0;
100	temp1[2][0] = 0;
101	temp1[2][1] = 0;
102	temp1[2][2] = 1;
103
104
105// pitch
106	angle = currententity->angles[PITCH];
107	angle = angle * M_PI*2 / 360;
108	s = sin(angle);
109	c = cos(angle);
110
111	temp2[0][0] = c;
112	temp2[0][1] = 0;
113	temp2[0][2] = -s;
114	temp2[1][0] = 0;
115	temp2[1][1] = 1;
116	temp2[1][2] = 0;
117	temp2[2][0] = s;
118	temp2[2][1] = 0;
119	temp2[2][2] = c;
120
121	R_ConcatRotations (temp2, temp1, temp3);
122
123// roll
124	angle = currententity->angles[ROLL];
125	angle = angle * M_PI*2 / 360;
126	s = sin(angle);
127	c = cos(angle);
128
129	temp1[0][0] = 1;
130	temp1[0][1] = 0;
131	temp1[0][2] = 0;
132	temp1[1][0] = 0;
133	temp1[1][1] = c;
134	temp1[1][2] = s;
135	temp1[2][0] = 0;
136	temp1[2][1] = -s;
137	temp1[2][2] = c;
138
139	R_ConcatRotations (temp1, temp3, entity_rotation);
140
141//
142// rotate modelorg and the transformation matrix
143//
144	R_EntityRotate (modelorg);
145	R_EntityRotate (vpn);
146	R_EntityRotate (vright);
147	R_EntityRotate (vup);
148
149	R_TransformFrustum ();
150}
151
152
153/*
154================
155R_RecursiveClipBPoly
156================
157*/
158void R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
159{
160	bedge_t		*psideedges[2], *pnextedge, *ptedge;
161	int			i, side, lastside;
162	float		dist, frac, lastdist;
163	mplane_t	*splitplane, tplane;
164	mvertex_t	*pvert, *plastvert, *ptvert;
165	mnode_t		*pn;
166
167	psideedges[0] = psideedges[1] = NULL;
168
169	makeclippededge = false;
170
171// transform the BSP plane into model space
172// FIXME: cache these?
173	splitplane = pnode->plane;
174	tplane.dist = splitplane->dist -
175			DotProduct(r_entorigin, splitplane->normal);
176	tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal);
177	tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal);
178	tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal);
179
180// clip edges to BSP plane
181	for ( ; pedges ; pedges = pnextedge)
182	{
183		pnextedge = pedges->pnext;
184
185	// set the status for the last point as the previous point
186	// FIXME: cache this stuff somehow?
187		plastvert = pedges->v[0];
188		lastdist = DotProduct (plastvert->position, tplane.normal) -
189				   tplane.dist;
190
191		if (lastdist > 0)
192			lastside = 0;
193		else
194			lastside = 1;
195
196		pvert = pedges->v[1];
197
198		dist = DotProduct (pvert->position, tplane.normal) - tplane.dist;
199
200		if (dist > 0)
201			side = 0;
202		else
203			side = 1;
204
205		if (side != lastside)
206		{
207		// clipped
208			if (numbverts >= MAX_BMODEL_VERTS)
209				return;
210
211		// generate the clipped vertex
212			frac = lastdist / (lastdist - dist);
213			ptvert = &pbverts[numbverts++];
214			ptvert->position[0] = plastvert->position[0] +
215					frac * (pvert->position[0] -
216					plastvert->position[0]);
217			ptvert->position[1] = plastvert->position[1] +
218					frac * (pvert->position[1] -
219					plastvert->position[1]);
220			ptvert->position[2] = plastvert->position[2] +
221					frac * (pvert->position[2] -
222					plastvert->position[2]);
223
224		// split into two edges, one on each side, and remember entering
225		// and exiting points
226		// FIXME: share the clip edge by having a winding direction flag?
227			if (numbedges >= (MAX_BMODEL_EDGES - 1))
228			{
229				Con_Printf ("Out of edges for bmodel\n");
230				return;
231			}
232
233			ptedge = &pbedges[numbedges];
234			ptedge->pnext = psideedges[lastside];
235			psideedges[lastside] = ptedge;
236			ptedge->v[0] = plastvert;
237			ptedge->v[1] = ptvert;
238
239			ptedge = &pbedges[numbedges + 1];
240			ptedge->pnext = psideedges[side];
241			psideedges[side] = ptedge;
242			ptedge->v[0] = ptvert;
243			ptedge->v[1] = pvert;
244
245			numbedges += 2;
246
247			if (side == 0)
248			{
249			// entering for front, exiting for back
250				pfrontenter = ptvert;
251				makeclippededge = true;
252			}
253			else
254			{
255				pfrontexit = ptvert;
256				makeclippededge = true;
257			}
258		}
259		else
260		{
261		// add the edge to the appropriate side
262			pedges->pnext = psideedges[side];
263			psideedges[side] = pedges;
264		}
265	}
266
267// if anything was clipped, reconstitute and add the edges along the clip
268// plane to both sides (but in opposite directions)
269	if (makeclippededge)
270	{
271		if (numbedges >= (MAX_BMODEL_EDGES - 2))
272		{
273			Con_Printf ("Out of edges for bmodel\n");
274			return;
275		}
276
277		ptedge = &pbedges[numbedges];
278		ptedge->pnext = psideedges[0];
279		psideedges[0] = ptedge;
280		ptedge->v[0] = pfrontexit;
281		ptedge->v[1] = pfrontenter;
282
283		ptedge = &pbedges[numbedges + 1];
284		ptedge->pnext = psideedges[1];
285		psideedges[1] = ptedge;
286		ptedge->v[0] = pfrontenter;
287		ptedge->v[1] = pfrontexit;
288
289		numbedges += 2;
290	}
291
292// draw or recurse further
293	for (i=0 ; i<2 ; i++)
294	{
295		if (psideedges[i])
296		{
297		// draw if we've reached a non-solid leaf, done if all that's left is a
298		// solid leaf, and continue down the tree if it's not a leaf
299			pn = pnode->children[i];
300
301		// we're done with this branch if the node or leaf isn't in the PVS
302			if (pn->visframe == r_visframecount)
303			{
304				if (pn->contents < 0)
305				{
306					if (pn->contents != CONTENTS_SOLID)
307					{
308						r_currentbkey = ((mleaf_t *)pn)->key;
309						R_RenderBmodelFace (psideedges[i], psurf);
310					}
311				}
312				else
313				{
314					R_RecursiveClipBPoly (psideedges[i], pnode->children[i],
315									  psurf);
316				}
317			}
318		}
319	}
320}
321
322
323/*
324================
325R_DrawSolidClippedSubmodelPolygons
326================
327*/
328void R_DrawSolidClippedSubmodelPolygons (model_t *pmodel)
329{
330	int			i, j, lindex;
331	vec_t		dot;
332	msurface_t	*psurf;
333	int			numsurfaces;
334	mplane_t	*pplane;
335	mvertex_t	bverts[MAX_BMODEL_VERTS];
336	bedge_t		bedges[MAX_BMODEL_EDGES], *pbedge;
337	medge_t		*pedge, *pedges;
338
339// FIXME: use bounding-box-based frustum clipping info?
340
341	psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
342	numsurfaces = pmodel->nummodelsurfaces;
343	pedges = pmodel->edges;
344
345	for (i=0 ; i<numsurfaces ; i++, psurf++)
346	{
347	// find which side of the node we are on
348		pplane = psurf->plane;
349
350		dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
351
352	// draw the polygon
353		if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
354			(!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
355		{
356		// FIXME: use bounding-box-based frustum clipping info?
357
358		// copy the edges to bedges, flipping if necessary so always
359		// clockwise winding
360		// FIXME: if edges and vertices get caches, these assignments must move
361		// outside the loop, and overflow checking must be done here
362			pbverts = bverts;
363			pbedges = bedges;
364			numbverts = numbedges = 0;
365
366			if (psurf->numedges > 0)
367			{
368				pbedge = &bedges[numbedges];
369				numbedges += psurf->numedges;
370
371				for (j=0 ; j<psurf->numedges ; j++)
372				{
373				   lindex = pmodel->surfedges[psurf->firstedge+j];
374
375					if (lindex > 0)
376					{
377						pedge = &pedges[lindex];
378						pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
379						pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
380					}
381					else
382					{
383						lindex = -lindex;
384						pedge = &pedges[lindex];
385						pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
386						pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
387					}
388
389					pbedge[j].pnext = &pbedge[j+1];
390				}
391
392				pbedge[j-1].pnext = NULL;	// mark end of edges
393
394				R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf);
395			}
396			else
397			{
398				Sys_Error ("no edges in bmodel");
399			}
400		}
401	}
402}
403
404
405/*
406================
407R_DrawSubmodelPolygons
408================
409*/
410void R_DrawSubmodelPolygons (model_t *pmodel, int clipflags)
411{
412	int			i;
413	vec_t		dot;
414	msurface_t	*psurf;
415	int			numsurfaces;
416	mplane_t	*pplane;
417
418// FIXME: use bounding-box-based frustum clipping info?
419
420	psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
421	numsurfaces = pmodel->nummodelsurfaces;
422
423	for (i=0 ; i<numsurfaces ; i++, psurf++)
424	{
425	// find which side of the node we are on
426		pplane = psurf->plane;
427
428		dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
429
430	// draw the polygon
431		if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
432			(!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
433		{
434			r_currentkey = ((mleaf_t *)currententity->topnode)->key;
435
436		// FIXME: use bounding-box-based frustum clipping info?
437			R_RenderFace (psurf, clipflags);
438		}
439	}
440}
441
442
443/*
444================
445R_RecursiveWorldNode
446================
447*/
448void R_RecursiveWorldNode (mnode_t *node, int clipflags)
449{
450	int			i, c, side, *pindex;
451	vec3_t		acceptpt, rejectpt;
452	mplane_t	*plane;
453	msurface_t	*surf, **mark;
454	mleaf_t		*pleaf;
455	double		d, dot;
456
457	if (node->contents == CONTENTS_SOLID)
458		return;		// solid
459
460	if (node->visframe != r_visframecount)
461		return;
462
463// cull the clipping planes if not trivial accept
464// FIXME: the compiler is doing a lousy job of optimizing here; it could be
465//  twice as fast in ASM
466	if (clipflags)
467	{
468		for (i=0 ; i<4 ; i++)
469		{
470			if (! (clipflags & (1<<i)) )
471				continue;	// don't need to clip against it
472
473		// generate accept and reject points
474		// FIXME: do with fast look-ups or integer tests based on the sign bit
475		// of the floating point values
476
477			pindex = pfrustum_indexes[i];
478
479			rejectpt[0] = (float)node->minmaxs[pindex[0]];
480			rejectpt[1] = (float)node->minmaxs[pindex[1]];
481			rejectpt[2] = (float)node->minmaxs[pindex[2]];
482
483			d = DotProduct (rejectpt, view_clipplanes[i].normal);
484			d -= view_clipplanes[i].dist;
485
486			if (d <= 0)
487				return;
488
489			acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
490			acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
491			acceptpt[2] = (float)node->minmaxs[pindex[3+2]];
492
493			d = DotProduct (acceptpt, view_clipplanes[i].normal);
494			d -= view_clipplanes[i].dist;
495
496			if (d >= 0)
497				clipflags &= ~(1<<i);	// node is entirely on screen
498		}
499	}
500
501// if a leaf node, draw stuff
502	if (node->contents < 0)
503	{
504		pleaf = (mleaf_t *)node;
505
506		mark = pleaf->firstmarksurface;
507		c = pleaf->nummarksurfaces;
508
509		if (c)
510		{
511			do
512			{
513				(*mark)->visframe = r_framecount;
514				mark++;
515			} while (--c);
516		}
517
518	// deal with model fragments in this leaf
519		if (pleaf->efrags)
520		{
521			R_StoreEfrags (&pleaf->efrags);
522		}
523
524		pleaf->key = r_currentkey;
525		r_currentkey++;		// all bmodels in a leaf share the same key
526	}
527	else
528	{
529	// node is just a decision point, so go down the apropriate sides
530
531	// find which side of the node we are on
532		plane = node->plane;
533
534		switch (plane->type)
535		{
536		case PLANE_X:
537			dot = modelorg[0] - plane->dist;
538			break;
539		case PLANE_Y:
540			dot = modelorg[1] - plane->dist;
541			break;
542		case PLANE_Z:
543			dot = modelorg[2] - plane->dist;
544			break;
545		default:
546			dot = DotProduct (modelorg, plane->normal) - plane->dist;
547			break;
548		}
549
550		if (dot >= 0)
551			side = 0;
552		else
553			side = 1;
554
555	// recurse down the children, front side first
556		R_RecursiveWorldNode (node->children[side], clipflags);
557
558	// draw stuff
559		c = node->numsurfaces;
560
561		if (c)
562		{
563			surf = cl.worldmodel->surfaces + node->firstsurface;
564
565			if (dot < -BACKFACE_EPSILON)
566			{
567				do
568				{
569					if ((surf->flags & SURF_PLANEBACK) &&
570						(surf->visframe == r_framecount))
571					{
572						if (r_drawpolys)
573						{
574							if (r_worldpolysbacktofront)
575							{
576								if (numbtofpolys < MAX_BTOFPOLYS)
577								{
578									pbtofpolys[numbtofpolys].clipflags =
579											clipflags;
580									pbtofpolys[numbtofpolys].psurf = surf;
581									numbtofpolys++;
582								}
583							}
584							else
585							{
586								R_RenderPoly (surf, clipflags);
587							}
588						}
589						else
590						{
591							R_RenderFace (surf, clipflags);
592						}
593					}
594
595					surf++;
596				} while (--c);
597			}
598			else if (dot > BACKFACE_EPSILON)
599			{
600				do
601				{
602					if (!(surf->flags & SURF_PLANEBACK) &&
603						(surf->visframe == r_framecount))
604					{
605						if (r_drawpolys)
606						{
607							if (r_worldpolysbacktofront)
608							{
609								if (numbtofpolys < MAX_BTOFPOLYS)
610								{
611									pbtofpolys[numbtofpolys].clipflags =
612											clipflags;
613									pbtofpolys[numbtofpolys].psurf = surf;
614									numbtofpolys++;
615								}
616							}
617							else
618							{
619								R_RenderPoly (surf, clipflags);
620							}
621						}
622						else
623						{
624							R_RenderFace (surf, clipflags);
625						}
626					}
627
628					surf++;
629				} while (--c);
630			}
631
632		// all surfaces on the same node share the same sequence number
633			r_currentkey++;
634		}
635
636	// recurse down the back side
637		R_RecursiveWorldNode (node->children[!side], clipflags);
638	}
639}
640
641
642
643/*
644================
645R_RenderWorld
646================
647*/
648void R_RenderWorld (void)
649{
650	int			i;
651	model_t		*clmodel;
652	btofpoly_t	btofpolys[MAX_BTOFPOLYS];
653
654	pbtofpolys = btofpolys;
655
656	currententity = &r_worldentity;
657	VectorCopy (r_origin, modelorg);
658	clmodel = currententity->model;
659	r_pcurrentvertbase = clmodel->vertexes;
660
661	R_RecursiveWorldNode (clmodel->nodes, 15);
662
663// if the driver wants the polygons back to front, play the visible ones back
664// in that order
665	if (r_worldpolysbacktofront)
666	{
667		for (i=numbtofpolys-1 ; i>=0 ; i--)
668		{
669			R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags);
670		}
671	}
672}
673
674
675