• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 // r_bsp.c
21 
22 #include "quakedef.h"
23 #include "r_local.h"
24 
25 //
26 // current entity info
27 //
28 qboolean		insubmodel;
29 entity_t		*currententity;
30 vec3_t			modelorg, base_modelorg;
31 								// modelorg is the viewpoint reletive to
32 								// the currently rendering entity
33 vec3_t			r_entorigin;	// the currently rendering entity in world
34 								// coordinates
35 
36 float			entity_rotation[3][3];
37 
38 vec3_t			r_worldmodelorg;
39 
40 int				r_currentbkey;
41 
42 typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t;
43 
44 #define MAX_BMODEL_VERTS	500			// 6K
45 #define MAX_BMODEL_EDGES	1000		// 12K
46 
47 static mvertex_t	*pbverts;
48 static bedge_t		*pbedges;
49 static int			numbverts, numbedges;
50 
51 static mvertex_t	*pfrontenter, *pfrontexit;
52 
53 static qboolean		makeclippededge;
54 
55 
56 //===========================================================================
57 
58 /*
59 ================
60 R_EntityRotate
61 ================
62 */
R_EntityRotate(vec3_t vec)63 void 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 ================
76 R_RotateBmodel
77 ================
78 */
R_RotateBmodel(void)79 void 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 ================
155 R_RecursiveClipBPoly
156 ================
157 */
R_RecursiveClipBPoly(bedge_t * pedges,mnode_t * pnode,msurface_t * psurf)158 void 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 ================
325 R_DrawSolidClippedSubmodelPolygons
326 ================
327 */
R_DrawSolidClippedSubmodelPolygons(model_t * pmodel)328 void 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 ================
407 R_DrawSubmodelPolygons
408 ================
409 */
R_DrawSubmodelPolygons(model_t * pmodel,int clipflags)410 void 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 ================
445 R_RecursiveWorldNode
446 ================
447 */
R_RecursiveWorldNode(mnode_t * node,int clipflags)448 void 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 ================
645 R_RenderWorld
646 ================
647 */
R_RenderWorld(void)648 void 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