Quake-III-Arena

Quake III Arena GPL Source Release
Log | Files | Refs

tr_main.c (39843B)


      1 /*
      2 ===========================================================================
      3 Copyright (C) 1999-2005 Id Software, Inc.
      4 
      5 This file is part of Quake III Arena source code.
      6 
      7 Quake III Arena source code is free software; you can redistribute it
      8 and/or modify it under the terms of the GNU General Public License as
      9 published by the Free Software Foundation; either version 2 of the License,
     10 or (at your option) any later version.
     11 
     12 Quake III Arena source code is distributed in the hope that it will be
     13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 GNU General Public License for more details.
     16 
     17 You should have received a copy of the GNU General Public License
     18 along with Foobar; if not, write to the Free Software
     19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
     20 ===========================================================================
     21 */
     22 // tr_main.c -- main control flow for each frame
     23 
     24 #include "tr_local.h"
     25 
     26 trGlobals_t		tr;
     27 
     28 static float	s_flipMatrix[16] = {
     29 	// convert from our coordinate system (looking down X)
     30 	// to OpenGL's coordinate system (looking down -Z)
     31 	0, 0, -1, 0,
     32 	-1, 0, 0, 0,
     33 	0, 1, 0, 0,
     34 	0, 0, 0, 1
     35 };
     36 
     37 
     38 refimport_t	ri;
     39 
     40 // entities that will have procedurally generated surfaces will just
     41 // point at this for their sorting surface
     42 surfaceType_t	entitySurface = SF_ENTITY;
     43 
     44 /*
     45 =================
     46 R_CullLocalBox
     47 
     48 Returns CULL_IN, CULL_CLIP, or CULL_OUT
     49 =================
     50 */
     51 int R_CullLocalBox (vec3_t bounds[2]) {
     52 	int		i, j;
     53 	vec3_t	transformed[8];
     54 	float	dists[8];
     55 	vec3_t	v;
     56 	cplane_t	*frust;
     57 	int			anyBack;
     58 	int			front, back;
     59 
     60 	if ( r_nocull->integer ) {
     61 		return CULL_CLIP;
     62 	}
     63 
     64 	// transform into world space
     65 	for (i = 0 ; i < 8 ; i++) {
     66 		v[0] = bounds[i&1][0];
     67 		v[1] = bounds[(i>>1)&1][1];
     68 		v[2] = bounds[(i>>2)&1][2];
     69 
     70 		VectorCopy( tr.or.origin, transformed[i] );
     71 		VectorMA( transformed[i], v[0], tr.or.axis[0], transformed[i] );
     72 		VectorMA( transformed[i], v[1], tr.or.axis[1], transformed[i] );
     73 		VectorMA( transformed[i], v[2], tr.or.axis[2], transformed[i] );
     74 	}
     75 
     76 	// check against frustum planes
     77 	anyBack = 0;
     78 	for (i = 0 ; i < 4 ; i++) {
     79 		frust = &tr.viewParms.frustum[i];
     80 
     81 		front = back = 0;
     82 		for (j = 0 ; j < 8 ; j++) {
     83 			dists[j] = DotProduct(transformed[j], frust->normal);
     84 			if ( dists[j] > frust->dist ) {
     85 				front = 1;
     86 				if ( back ) {
     87 					break;		// a point is in front
     88 				}
     89 			} else {
     90 				back = 1;
     91 			}
     92 		}
     93 		if ( !front ) {
     94 			// all points were behind one of the planes
     95 			return CULL_OUT;
     96 		}
     97 		anyBack |= back;
     98 	}
     99 
    100 	if ( !anyBack ) {
    101 		return CULL_IN;		// completely inside frustum
    102 	}
    103 
    104 	return CULL_CLIP;		// partially clipped
    105 }
    106 
    107 /*
    108 ** R_CullLocalPointAndRadius
    109 */
    110 int R_CullLocalPointAndRadius( vec3_t pt, float radius )
    111 {
    112 	vec3_t transformed;
    113 
    114 	R_LocalPointToWorld( pt, transformed );
    115 
    116 	return R_CullPointAndRadius( transformed, radius );
    117 }
    118 
    119 /*
    120 ** R_CullPointAndRadius
    121 */
    122 int R_CullPointAndRadius( vec3_t pt, float radius )
    123 {
    124 	int		i;
    125 	float	dist;
    126 	cplane_t	*frust;
    127 	qboolean mightBeClipped = qfalse;
    128 
    129 	if ( r_nocull->integer ) {
    130 		return CULL_CLIP;
    131 	}
    132 
    133 	// check against frustum planes
    134 	for (i = 0 ; i < 4 ; i++) 
    135 	{
    136 		frust = &tr.viewParms.frustum[i];
    137 
    138 		dist = DotProduct( pt, frust->normal) - frust->dist;
    139 		if ( dist < -radius )
    140 		{
    141 			return CULL_OUT;
    142 		}
    143 		else if ( dist <= radius ) 
    144 		{
    145 			mightBeClipped = qtrue;
    146 		}
    147 	}
    148 
    149 	if ( mightBeClipped )
    150 	{
    151 		return CULL_CLIP;
    152 	}
    153 
    154 	return CULL_IN;		// completely inside frustum
    155 }
    156 
    157 
    158 /*
    159 =================
    160 R_LocalNormalToWorld
    161 
    162 =================
    163 */
    164 void R_LocalNormalToWorld (vec3_t local, vec3_t world) {
    165 	world[0] = local[0] * tr.or.axis[0][0] + local[1] * tr.or.axis[1][0] + local[2] * tr.or.axis[2][0];
    166 	world[1] = local[0] * tr.or.axis[0][1] + local[1] * tr.or.axis[1][1] + local[2] * tr.or.axis[2][1];
    167 	world[2] = local[0] * tr.or.axis[0][2] + local[1] * tr.or.axis[1][2] + local[2] * tr.or.axis[2][2];
    168 }
    169 
    170 /*
    171 =================
    172 R_LocalPointToWorld
    173 
    174 =================
    175 */
    176 void R_LocalPointToWorld (vec3_t local, vec3_t world) {
    177 	world[0] = local[0] * tr.or.axis[0][0] + local[1] * tr.or.axis[1][0] + local[2] * tr.or.axis[2][0] + tr.or.origin[0];
    178 	world[1] = local[0] * tr.or.axis[0][1] + local[1] * tr.or.axis[1][1] + local[2] * tr.or.axis[2][1] + tr.or.origin[1];
    179 	world[2] = local[0] * tr.or.axis[0][2] + local[1] * tr.or.axis[1][2] + local[2] * tr.or.axis[2][2] + tr.or.origin[2];
    180 }
    181 
    182 /*
    183 =================
    184 R_WorldToLocal
    185 
    186 =================
    187 */
    188 void R_WorldToLocal (vec3_t world, vec3_t local) {
    189 	local[0] = DotProduct(world, tr.or.axis[0]);
    190 	local[1] = DotProduct(world, tr.or.axis[1]);
    191 	local[2] = DotProduct(world, tr.or.axis[2]);
    192 }
    193 
    194 /*
    195 ==========================
    196 R_TransformModelToClip
    197 
    198 ==========================
    199 */
    200 void R_TransformModelToClip( const vec3_t src, const float *modelMatrix, const float *projectionMatrix,
    201 							vec4_t eye, vec4_t dst ) {
    202 	int i;
    203 
    204 	for ( i = 0 ; i < 4 ; i++ ) {
    205 		eye[i] = 
    206 			src[0] * modelMatrix[ i + 0 * 4 ] +
    207 			src[1] * modelMatrix[ i + 1 * 4 ] +
    208 			src[2] * modelMatrix[ i + 2 * 4 ] +
    209 			1 * modelMatrix[ i + 3 * 4 ];
    210 	}
    211 
    212 	for ( i = 0 ; i < 4 ; i++ ) {
    213 		dst[i] = 
    214 			eye[0] * projectionMatrix[ i + 0 * 4 ] +
    215 			eye[1] * projectionMatrix[ i + 1 * 4 ] +
    216 			eye[2] * projectionMatrix[ i + 2 * 4 ] +
    217 			eye[3] * projectionMatrix[ i + 3 * 4 ];
    218 	}
    219 }
    220 
    221 /*
    222 ==========================
    223 R_TransformClipToWindow
    224 
    225 ==========================
    226 */
    227 void R_TransformClipToWindow( const vec4_t clip, const viewParms_t *view, vec4_t normalized, vec4_t window ) {
    228 	normalized[0] = clip[0] / clip[3];
    229 	normalized[1] = clip[1] / clip[3];
    230 	normalized[2] = ( clip[2] + clip[3] ) / ( 2 * clip[3] );
    231 
    232 	window[0] = 0.5f * ( 1.0f + normalized[0] ) * view->viewportWidth;
    233 	window[1] = 0.5f * ( 1.0f + normalized[1] ) * view->viewportHeight;
    234 	window[2] = normalized[2];
    235 
    236 	window[0] = (int) ( window[0] + 0.5 );
    237 	window[1] = (int) ( window[1] + 0.5 );
    238 }
    239 
    240 
    241 /*
    242 ==========================
    243 myGlMultMatrix
    244 
    245 ==========================
    246 */
    247 void myGlMultMatrix( const float *a, const float *b, float *out ) {
    248 	int		i, j;
    249 
    250 	for ( i = 0 ; i < 4 ; i++ ) {
    251 		for ( j = 0 ; j < 4 ; j++ ) {
    252 			out[ i * 4 + j ] =
    253 				a [ i * 4 + 0 ] * b [ 0 * 4 + j ]
    254 				+ a [ i * 4 + 1 ] * b [ 1 * 4 + j ]
    255 				+ a [ i * 4 + 2 ] * b [ 2 * 4 + j ]
    256 				+ a [ i * 4 + 3 ] * b [ 3 * 4 + j ];
    257 		}
    258 	}
    259 }
    260 
    261 /*
    262 =================
    263 R_RotateForEntity
    264 
    265 Generates an orientation for an entity and viewParms
    266 Does NOT produce any GL calls
    267 Called by both the front end and the back end
    268 =================
    269 */
    270 void R_RotateForEntity( const trRefEntity_t *ent, const viewParms_t *viewParms,
    271 					   orientationr_t *or ) {
    272 	float	glMatrix[16];
    273 	vec3_t	delta;
    274 	float	axisLength;
    275 
    276 	if ( ent->e.reType != RT_MODEL ) {
    277 		*or = viewParms->world;
    278 		return;
    279 	}
    280 
    281 	VectorCopy( ent->e.origin, or->origin );
    282 
    283 	VectorCopy( ent->e.axis[0], or->axis[0] );
    284 	VectorCopy( ent->e.axis[1], or->axis[1] );
    285 	VectorCopy( ent->e.axis[2], or->axis[2] );
    286 
    287 	glMatrix[0] = or->axis[0][0];
    288 	glMatrix[4] = or->axis[1][0];
    289 	glMatrix[8] = or->axis[2][0];
    290 	glMatrix[12] = or->origin[0];
    291 
    292 	glMatrix[1] = or->axis[0][1];
    293 	glMatrix[5] = or->axis[1][1];
    294 	glMatrix[9] = or->axis[2][1];
    295 	glMatrix[13] = or->origin[1];
    296 
    297 	glMatrix[2] = or->axis[0][2];
    298 	glMatrix[6] = or->axis[1][2];
    299 	glMatrix[10] = or->axis[2][2];
    300 	glMatrix[14] = or->origin[2];
    301 
    302 	glMatrix[3] = 0;
    303 	glMatrix[7] = 0;
    304 	glMatrix[11] = 0;
    305 	glMatrix[15] = 1;
    306 
    307 	myGlMultMatrix( glMatrix, viewParms->world.modelMatrix, or->modelMatrix );
    308 
    309 	// calculate the viewer origin in the model's space
    310 	// needed for fog, specular, and environment mapping
    311 	VectorSubtract( viewParms->or.origin, or->origin, delta );
    312 
    313 	// compensate for scale in the axes if necessary
    314 	if ( ent->e.nonNormalizedAxes ) {
    315 		axisLength = VectorLength( ent->e.axis[0] );
    316 		if ( !axisLength ) {
    317 			axisLength = 0;
    318 		} else {
    319 			axisLength = 1.0f / axisLength;
    320 		}
    321 	} else {
    322 		axisLength = 1.0f;
    323 	}
    324 
    325 	or->viewOrigin[0] = DotProduct( delta, or->axis[0] ) * axisLength;
    326 	or->viewOrigin[1] = DotProduct( delta, or->axis[1] ) * axisLength;
    327 	or->viewOrigin[2] = DotProduct( delta, or->axis[2] ) * axisLength;
    328 }
    329 
    330 /*
    331 =================
    332 R_RotateForViewer
    333 
    334 Sets up the modelview matrix for a given viewParm
    335 =================
    336 */
    337 void R_RotateForViewer (void) 
    338 {
    339 	float	viewerMatrix[16];
    340 	vec3_t	origin;
    341 
    342 	Com_Memset (&tr.or, 0, sizeof(tr.or));
    343 	tr.or.axis[0][0] = 1;
    344 	tr.or.axis[1][1] = 1;
    345 	tr.or.axis[2][2] = 1;
    346 	VectorCopy (tr.viewParms.or.origin, tr.or.viewOrigin);
    347 
    348 	// transform by the camera placement
    349 	VectorCopy( tr.viewParms.or.origin, origin );
    350 
    351 	viewerMatrix[0] = tr.viewParms.or.axis[0][0];
    352 	viewerMatrix[4] = tr.viewParms.or.axis[0][1];
    353 	viewerMatrix[8] = tr.viewParms.or.axis[0][2];
    354 	viewerMatrix[12] = -origin[0] * viewerMatrix[0] + -origin[1] * viewerMatrix[4] + -origin[2] * viewerMatrix[8];
    355 
    356 	viewerMatrix[1] = tr.viewParms.or.axis[1][0];
    357 	viewerMatrix[5] = tr.viewParms.or.axis[1][1];
    358 	viewerMatrix[9] = tr.viewParms.or.axis[1][2];
    359 	viewerMatrix[13] = -origin[0] * viewerMatrix[1] + -origin[1] * viewerMatrix[5] + -origin[2] * viewerMatrix[9];
    360 
    361 	viewerMatrix[2] = tr.viewParms.or.axis[2][0];
    362 	viewerMatrix[6] = tr.viewParms.or.axis[2][1];
    363 	viewerMatrix[10] = tr.viewParms.or.axis[2][2];
    364 	viewerMatrix[14] = -origin[0] * viewerMatrix[2] + -origin[1] * viewerMatrix[6] + -origin[2] * viewerMatrix[10];
    365 
    366 	viewerMatrix[3] = 0;
    367 	viewerMatrix[7] = 0;
    368 	viewerMatrix[11] = 0;
    369 	viewerMatrix[15] = 1;
    370 
    371 	// convert from our coordinate system (looking down X)
    372 	// to OpenGL's coordinate system (looking down -Z)
    373 	myGlMultMatrix( viewerMatrix, s_flipMatrix, tr.or.modelMatrix );
    374 
    375 	tr.viewParms.world = tr.or;
    376 
    377 }
    378 
    379 /*
    380 ** SetFarClip
    381 */
    382 static void SetFarClip( void )
    383 {
    384 	float	farthestCornerDistance = 0;
    385 	int		i;
    386 
    387 	// if not rendering the world (icons, menus, etc)
    388 	// set a 2k far clip plane
    389 	if ( tr.refdef.rdflags & RDF_NOWORLDMODEL ) {
    390 		tr.viewParms.zFar = 2048;
    391 		return;
    392 	}
    393 
    394 	//
    395 	// set far clipping planes dynamically
    396 	//
    397 	farthestCornerDistance = 0;
    398 	for ( i = 0; i < 8; i++ )
    399 	{
    400 		vec3_t v;
    401 		vec3_t vecTo;
    402 		float distance;
    403 
    404 		if ( i & 1 )
    405 		{
    406 			v[0] = tr.viewParms.visBounds[0][0];
    407 		}
    408 		else
    409 		{
    410 			v[0] = tr.viewParms.visBounds[1][0];
    411 		}
    412 
    413 		if ( i & 2 )
    414 		{
    415 			v[1] = tr.viewParms.visBounds[0][1];
    416 		}
    417 		else
    418 		{
    419 			v[1] = tr.viewParms.visBounds[1][1];
    420 		}
    421 
    422 		if ( i & 4 )
    423 		{
    424 			v[2] = tr.viewParms.visBounds[0][2];
    425 		}
    426 		else
    427 		{
    428 			v[2] = tr.viewParms.visBounds[1][2];
    429 		}
    430 
    431 		VectorSubtract( v, tr.viewParms.or.origin, vecTo );
    432 
    433 		distance = vecTo[0] * vecTo[0] + vecTo[1] * vecTo[1] + vecTo[2] * vecTo[2];
    434 
    435 		if ( distance > farthestCornerDistance )
    436 		{
    437 			farthestCornerDistance = distance;
    438 		}
    439 	}
    440 	tr.viewParms.zFar = sqrt( farthestCornerDistance );
    441 }
    442 
    443 
    444 /*
    445 ===============
    446 R_SetupProjection
    447 ===============
    448 */
    449 void R_SetupProjection( void ) {
    450 	float	xmin, xmax, ymin, ymax;
    451 	float	width, height, depth;
    452 	float	zNear, zFar;
    453 
    454 	// dynamically compute far clip plane distance
    455 	SetFarClip();
    456 
    457 	//
    458 	// set up projection matrix
    459 	//
    460 	zNear	= r_znear->value;
    461 	zFar	= tr.viewParms.zFar;
    462 
    463 	ymax = zNear * tan( tr.refdef.fov_y * M_PI / 360.0f );
    464 	ymin = -ymax;
    465 
    466 	xmax = zNear * tan( tr.refdef.fov_x * M_PI / 360.0f );
    467 	xmin = -xmax;
    468 
    469 	width = xmax - xmin;
    470 	height = ymax - ymin;
    471 	depth = zFar - zNear;
    472 
    473 	tr.viewParms.projectionMatrix[0] = 2 * zNear / width;
    474 	tr.viewParms.projectionMatrix[4] = 0;
    475 	tr.viewParms.projectionMatrix[8] = ( xmax + xmin ) / width;	// normally 0
    476 	tr.viewParms.projectionMatrix[12] = 0;
    477 
    478 	tr.viewParms.projectionMatrix[1] = 0;
    479 	tr.viewParms.projectionMatrix[5] = 2 * zNear / height;
    480 	tr.viewParms.projectionMatrix[9] = ( ymax + ymin ) / height;	// normally 0
    481 	tr.viewParms.projectionMatrix[13] = 0;
    482 
    483 	tr.viewParms.projectionMatrix[2] = 0;
    484 	tr.viewParms.projectionMatrix[6] = 0;
    485 	tr.viewParms.projectionMatrix[10] = -( zFar + zNear ) / depth;
    486 	tr.viewParms.projectionMatrix[14] = -2 * zFar * zNear / depth;
    487 
    488 	tr.viewParms.projectionMatrix[3] = 0;
    489 	tr.viewParms.projectionMatrix[7] = 0;
    490 	tr.viewParms.projectionMatrix[11] = -1;
    491 	tr.viewParms.projectionMatrix[15] = 0;
    492 }
    493 
    494 /*
    495 =================
    496 R_SetupFrustum
    497 
    498 Setup that culling frustum planes for the current view
    499 =================
    500 */
    501 void R_SetupFrustum (void) {
    502 	int		i;
    503 	float	xs, xc;
    504 	float	ang;
    505 
    506 	ang = tr.viewParms.fovX / 180 * M_PI * 0.5f;
    507 	xs = sin( ang );
    508 	xc = cos( ang );
    509 
    510 	VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[0].normal );
    511 	VectorMA( tr.viewParms.frustum[0].normal, xc, tr.viewParms.or.axis[1], tr.viewParms.frustum[0].normal );
    512 
    513 	VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[1].normal );
    514 	VectorMA( tr.viewParms.frustum[1].normal, -xc, tr.viewParms.or.axis[1], tr.viewParms.frustum[1].normal );
    515 
    516 	ang = tr.viewParms.fovY / 180 * M_PI * 0.5f;
    517 	xs = sin( ang );
    518 	xc = cos( ang );
    519 
    520 	VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[2].normal );
    521 	VectorMA( tr.viewParms.frustum[2].normal, xc, tr.viewParms.or.axis[2], tr.viewParms.frustum[2].normal );
    522 
    523 	VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[3].normal );
    524 	VectorMA( tr.viewParms.frustum[3].normal, -xc, tr.viewParms.or.axis[2], tr.viewParms.frustum[3].normal );
    525 
    526 	for (i=0 ; i<4 ; i++) {
    527 		tr.viewParms.frustum[i].type = PLANE_NON_AXIAL;
    528 		tr.viewParms.frustum[i].dist = DotProduct (tr.viewParms.or.origin, tr.viewParms.frustum[i].normal);
    529 		SetPlaneSignbits( &tr.viewParms.frustum[i] );
    530 	}
    531 }
    532 
    533 
    534 /*
    535 =================
    536 R_MirrorPoint
    537 =================
    538 */
    539 void R_MirrorPoint (vec3_t in, orientation_t *surface, orientation_t *camera, vec3_t out) {
    540 	int		i;
    541 	vec3_t	local;
    542 	vec3_t	transformed;
    543 	float	d;
    544 
    545 	VectorSubtract( in, surface->origin, local );
    546 
    547 	VectorClear( transformed );
    548 	for ( i = 0 ; i < 3 ; i++ ) {
    549 		d = DotProduct(local, surface->axis[i]);
    550 		VectorMA( transformed, d, camera->axis[i], transformed );
    551 	}
    552 
    553 	VectorAdd( transformed, camera->origin, out );
    554 }
    555 
    556 void R_MirrorVector (vec3_t in, orientation_t *surface, orientation_t *camera, vec3_t out) {
    557 	int		i;
    558 	float	d;
    559 
    560 	VectorClear( out );
    561 	for ( i = 0 ; i < 3 ; i++ ) {
    562 		d = DotProduct(in, surface->axis[i]);
    563 		VectorMA( out, d, camera->axis[i], out );
    564 	}
    565 }
    566 
    567 
    568 /*
    569 =============
    570 R_PlaneForSurface
    571 =============
    572 */
    573 void R_PlaneForSurface (surfaceType_t *surfType, cplane_t *plane) {
    574 	srfTriangles_t	*tri;
    575 	srfPoly_t		*poly;
    576 	drawVert_t		*v1, *v2, *v3;
    577 	vec4_t			plane4;
    578 
    579 	if (!surfType) {
    580 		Com_Memset (plane, 0, sizeof(*plane));
    581 		plane->normal[0] = 1;
    582 		return;
    583 	}
    584 	switch (*surfType) {
    585 	case SF_FACE:
    586 		*plane = ((srfSurfaceFace_t *)surfType)->plane;
    587 		return;
    588 	case SF_TRIANGLES:
    589 		tri = (srfTriangles_t *)surfType;
    590 		v1 = tri->verts + tri->indexes[0];
    591 		v2 = tri->verts + tri->indexes[1];
    592 		v3 = tri->verts + tri->indexes[2];
    593 		PlaneFromPoints( plane4, v1->xyz, v2->xyz, v3->xyz );
    594 		VectorCopy( plane4, plane->normal ); 
    595 		plane->dist = plane4[3];
    596 		return;
    597 	case SF_POLY:
    598 		poly = (srfPoly_t *)surfType;
    599 		PlaneFromPoints( plane4, poly->verts[0].xyz, poly->verts[1].xyz, poly->verts[2].xyz );
    600 		VectorCopy( plane4, plane->normal ); 
    601 		plane->dist = plane4[3];
    602 		return;
    603 	default:
    604 		Com_Memset (plane, 0, sizeof(*plane));
    605 		plane->normal[0] = 1;		
    606 		return;
    607 	}
    608 }
    609 
    610 /*
    611 =================
    612 R_GetPortalOrientation
    613 
    614 entityNum is the entity that the portal surface is a part of, which may
    615 be moving and rotating.
    616 
    617 Returns qtrue if it should be mirrored
    618 =================
    619 */
    620 qboolean R_GetPortalOrientations( drawSurf_t *drawSurf, int entityNum, 
    621 							 orientation_t *surface, orientation_t *camera,
    622 							 vec3_t pvsOrigin, qboolean *mirror ) {
    623 	int			i;
    624 	cplane_t	originalPlane, plane;
    625 	trRefEntity_t	*e;
    626 	float		d;
    627 	vec3_t		transformed;
    628 
    629 	// create plane axis for the portal we are seeing
    630 	R_PlaneForSurface( drawSurf->surface, &originalPlane );
    631 
    632 	// rotate the plane if necessary
    633 	if ( entityNum != ENTITYNUM_WORLD ) {
    634 		tr.currentEntityNum = entityNum;
    635 		tr.currentEntity = &tr.refdef.entities[entityNum];
    636 
    637 		// get the orientation of the entity
    638 		R_RotateForEntity( tr.currentEntity, &tr.viewParms, &tr.or );
    639 
    640 		// rotate the plane, but keep the non-rotated version for matching
    641 		// against the portalSurface entities
    642 		R_LocalNormalToWorld( originalPlane.normal, plane.normal );
    643 		plane.dist = originalPlane.dist + DotProduct( plane.normal, tr.or.origin );
    644 
    645 		// translate the original plane
    646 		originalPlane.dist = originalPlane.dist + DotProduct( originalPlane.normal, tr.or.origin );
    647 	} else {
    648 		plane = originalPlane;
    649 	}
    650 
    651 	VectorCopy( plane.normal, surface->axis[0] );
    652 	PerpendicularVector( surface->axis[1], surface->axis[0] );
    653 	CrossProduct( surface->axis[0], surface->axis[1], surface->axis[2] );
    654 
    655 	// locate the portal entity closest to this plane.
    656 	// origin will be the origin of the portal, origin2 will be
    657 	// the origin of the camera
    658 	for ( i = 0 ; i < tr.refdef.num_entities ; i++ ) {
    659 		e = &tr.refdef.entities[i];
    660 		if ( e->e.reType != RT_PORTALSURFACE ) {
    661 			continue;
    662 		}
    663 
    664 		d = DotProduct( e->e.origin, originalPlane.normal ) - originalPlane.dist;
    665 		if ( d > 64 || d < -64) {
    666 			continue;
    667 		}
    668 
    669 		// get the pvsOrigin from the entity
    670 		VectorCopy( e->e.oldorigin, pvsOrigin );
    671 
    672 		// if the entity is just a mirror, don't use as a camera point
    673 		if ( e->e.oldorigin[0] == e->e.origin[0] && 
    674 			e->e.oldorigin[1] == e->e.origin[1] && 
    675 			e->e.oldorigin[2] == e->e.origin[2] ) {
    676 			VectorScale( plane.normal, plane.dist, surface->origin );
    677 			VectorCopy( surface->origin, camera->origin );
    678 			VectorSubtract( vec3_origin, surface->axis[0], camera->axis[0] );
    679 			VectorCopy( surface->axis[1], camera->axis[1] );
    680 			VectorCopy( surface->axis[2], camera->axis[2] );
    681 
    682 			*mirror = qtrue;
    683 			return qtrue;
    684 		}
    685 
    686 		// project the origin onto the surface plane to get
    687 		// an origin point we can rotate around
    688 		d = DotProduct( e->e.origin, plane.normal ) - plane.dist;
    689 		VectorMA( e->e.origin, -d, surface->axis[0], surface->origin );
    690 			
    691 		// now get the camera origin and orientation
    692 		VectorCopy( e->e.oldorigin, camera->origin );
    693 		AxisCopy( e->e.axis, camera->axis );
    694 		VectorSubtract( vec3_origin, camera->axis[0], camera->axis[0] );
    695 		VectorSubtract( vec3_origin, camera->axis[1], camera->axis[1] );
    696 
    697 		// optionally rotate
    698 		if ( e->e.oldframe ) {
    699 			// if a speed is specified
    700 			if ( e->e.frame ) {
    701 				// continuous rotate
    702 				d = (tr.refdef.time/1000.0f) * e->e.frame;
    703 				VectorCopy( camera->axis[1], transformed );
    704 				RotatePointAroundVector( camera->axis[1], camera->axis[0], transformed, d );
    705 				CrossProduct( camera->axis[0], camera->axis[1], camera->axis[2] );
    706 			} else {
    707 				// bobbing rotate, with skinNum being the rotation offset
    708 				d = sin( tr.refdef.time * 0.003f );
    709 				d = e->e.skinNum + d * 4;
    710 				VectorCopy( camera->axis[1], transformed );
    711 				RotatePointAroundVector( camera->axis[1], camera->axis[0], transformed, d );
    712 				CrossProduct( camera->axis[0], camera->axis[1], camera->axis[2] );
    713 			}
    714 		}
    715 		else if ( e->e.skinNum ) {
    716 			d = e->e.skinNum;
    717 			VectorCopy( camera->axis[1], transformed );
    718 			RotatePointAroundVector( camera->axis[1], camera->axis[0], transformed, d );
    719 			CrossProduct( camera->axis[0], camera->axis[1], camera->axis[2] );
    720 		}
    721 		*mirror = qfalse;
    722 		return qtrue;
    723 	}
    724 
    725 	// if we didn't locate a portal entity, don't render anything.
    726 	// We don't want to just treat it as a mirror, because without a
    727 	// portal entity the server won't have communicated a proper entity set
    728 	// in the snapshot
    729 
    730 	// unfortunately, with local movement prediction it is easily possible
    731 	// to see a surface before the server has communicated the matching
    732 	// portal surface entity, so we don't want to print anything here...
    733 
    734 	//ri.Printf( PRINT_ALL, "Portal surface without a portal entity\n" );
    735 
    736 	return qfalse;
    737 }
    738 
    739 static qboolean IsMirror( const drawSurf_t *drawSurf, int entityNum )
    740 {
    741 	int			i;
    742 	cplane_t	originalPlane, plane;
    743 	trRefEntity_t	*e;
    744 	float		d;
    745 
    746 	// create plane axis for the portal we are seeing
    747 	R_PlaneForSurface( drawSurf->surface, &originalPlane );
    748 
    749 	// rotate the plane if necessary
    750 	if ( entityNum != ENTITYNUM_WORLD ) 
    751 	{
    752 		tr.currentEntityNum = entityNum;
    753 		tr.currentEntity = &tr.refdef.entities[entityNum];
    754 
    755 		// get the orientation of the entity
    756 		R_RotateForEntity( tr.currentEntity, &tr.viewParms, &tr.or );
    757 
    758 		// rotate the plane, but keep the non-rotated version for matching
    759 		// against the portalSurface entities
    760 		R_LocalNormalToWorld( originalPlane.normal, plane.normal );
    761 		plane.dist = originalPlane.dist + DotProduct( plane.normal, tr.or.origin );
    762 
    763 		// translate the original plane
    764 		originalPlane.dist = originalPlane.dist + DotProduct( originalPlane.normal, tr.or.origin );
    765 	} 
    766 	else 
    767 	{
    768 		plane = originalPlane;
    769 	}
    770 
    771 	// locate the portal entity closest to this plane.
    772 	// origin will be the origin of the portal, origin2 will be
    773 	// the origin of the camera
    774 	for ( i = 0 ; i < tr.refdef.num_entities ; i++ ) 
    775 	{
    776 		e = &tr.refdef.entities[i];
    777 		if ( e->e.reType != RT_PORTALSURFACE ) {
    778 			continue;
    779 		}
    780 
    781 		d = DotProduct( e->e.origin, originalPlane.normal ) - originalPlane.dist;
    782 		if ( d > 64 || d < -64) {
    783 			continue;
    784 		}
    785 
    786 		// if the entity is just a mirror, don't use as a camera point
    787 		if ( e->e.oldorigin[0] == e->e.origin[0] && 
    788 			e->e.oldorigin[1] == e->e.origin[1] && 
    789 			e->e.oldorigin[2] == e->e.origin[2] ) 
    790 		{
    791 			return qtrue;
    792 		}
    793 
    794 		return qfalse;
    795 	}
    796 	return qfalse;
    797 }
    798 
    799 /*
    800 ** SurfIsOffscreen
    801 **
    802 ** Determines if a surface is completely offscreen.
    803 */
    804 static qboolean SurfIsOffscreen( const drawSurf_t *drawSurf, vec4_t clipDest[128] ) {
    805 	float shortest = 100000000;
    806 	int entityNum;
    807 	int numTriangles;
    808 	shader_t *shader;
    809 	int		fogNum;
    810 	int dlighted;
    811 	vec4_t clip, eye;
    812 	int i;
    813 	unsigned int pointOr = 0;
    814 	unsigned int pointAnd = (unsigned int)~0;
    815 
    816 	if ( glConfig.smpActive ) {		// FIXME!  we can't do RB_BeginSurface/RB_EndSurface stuff with smp!
    817 		return qfalse;
    818 	}
    819 
    820 	R_RotateForViewer();
    821 
    822 	R_DecomposeSort( drawSurf->sort, &entityNum, &shader, &fogNum, &dlighted );
    823 	RB_BeginSurface( shader, fogNum );
    824 	rb_surfaceTable[ *drawSurf->surface ]( drawSurf->surface );
    825 
    826 	assert( tess.numVertexes < 128 );
    827 
    828 	for ( i = 0; i < tess.numVertexes; i++ )
    829 	{
    830 		int j;
    831 		unsigned int pointFlags = 0;
    832 
    833 		R_TransformModelToClip( tess.xyz[i], tr.or.modelMatrix, tr.viewParms.projectionMatrix, eye, clip );
    834 
    835 		for ( j = 0; j < 3; j++ )
    836 		{
    837 			if ( clip[j] >= clip[3] )
    838 			{
    839 				pointFlags |= (1 << (j*2));
    840 			}
    841 			else if ( clip[j] <= -clip[3] )
    842 			{
    843 				pointFlags |= ( 1 << (j*2+1));
    844 			}
    845 		}
    846 		pointAnd &= pointFlags;
    847 		pointOr |= pointFlags;
    848 	}
    849 
    850 	// trivially reject
    851 	if ( pointAnd )
    852 	{
    853 		return qtrue;
    854 	}
    855 
    856 	// determine if this surface is backfaced and also determine the distance
    857 	// to the nearest vertex so we can cull based on portal range.  Culling
    858 	// based on vertex distance isn't 100% correct (we should be checking for
    859 	// range to the surface), but it's good enough for the types of portals
    860 	// we have in the game right now.
    861 	numTriangles = tess.numIndexes / 3;
    862 
    863 	for ( i = 0; i < tess.numIndexes; i += 3 )
    864 	{
    865 		vec3_t normal;
    866 		float dot;
    867 		float len;
    868 
    869 		VectorSubtract( tess.xyz[tess.indexes[i]], tr.viewParms.or.origin, normal );
    870 
    871 		len = VectorLengthSquared( normal );			// lose the sqrt
    872 		if ( len < shortest )
    873 		{
    874 			shortest = len;
    875 		}
    876 
    877 		if ( ( dot = DotProduct( normal, tess.normal[tess.indexes[i]] ) ) >= 0 )
    878 		{
    879 			numTriangles--;
    880 		}
    881 	}
    882 	if ( !numTriangles )
    883 	{
    884 		return qtrue;
    885 	}
    886 
    887 	// mirrors can early out at this point, since we don't do a fade over distance
    888 	// with them (although we could)
    889 	if ( IsMirror( drawSurf, entityNum ) )
    890 	{
    891 		return qfalse;
    892 	}
    893 
    894 	if ( shortest > (tess.shader->portalRange*tess.shader->portalRange) )
    895 	{
    896 		return qtrue;
    897 	}
    898 
    899 	return qfalse;
    900 }
    901 
    902 /*
    903 ========================
    904 R_MirrorViewBySurface
    905 
    906 Returns qtrue if another view has been rendered
    907 ========================
    908 */
    909 qboolean R_MirrorViewBySurface (drawSurf_t *drawSurf, int entityNum) {
    910 	vec4_t			clipDest[128];
    911 	viewParms_t		newParms;
    912 	viewParms_t		oldParms;
    913 	orientation_t	surface, camera;
    914 
    915 	// don't recursively mirror
    916 	if (tr.viewParms.isPortal) {
    917 		ri.Printf( PRINT_DEVELOPER, "WARNING: recursive mirror/portal found\n" );
    918 		return qfalse;
    919 	}
    920 
    921 	if ( r_noportals->integer || (r_fastsky->integer == 1) ) {
    922 		return qfalse;
    923 	}
    924 
    925 	// trivially reject portal/mirror
    926 	if ( SurfIsOffscreen( drawSurf, clipDest ) ) {
    927 		return qfalse;
    928 	}
    929 
    930 	// save old viewParms so we can return to it after the mirror view
    931 	oldParms = tr.viewParms;
    932 
    933 	newParms = tr.viewParms;
    934 	newParms.isPortal = qtrue;
    935 	if ( !R_GetPortalOrientations( drawSurf, entityNum, &surface, &camera, 
    936 		newParms.pvsOrigin, &newParms.isMirror ) ) {
    937 		return qfalse;		// bad portal, no portalentity
    938 	}
    939 
    940 	R_MirrorPoint (oldParms.or.origin, &surface, &camera, newParms.or.origin );
    941 
    942 	VectorSubtract( vec3_origin, camera.axis[0], newParms.portalPlane.normal );
    943 	newParms.portalPlane.dist = DotProduct( camera.origin, newParms.portalPlane.normal );
    944 	
    945 	R_MirrorVector (oldParms.or.axis[0], &surface, &camera, newParms.or.axis[0]);
    946 	R_MirrorVector (oldParms.or.axis[1], &surface, &camera, newParms.or.axis[1]);
    947 	R_MirrorVector (oldParms.or.axis[2], &surface, &camera, newParms.or.axis[2]);
    948 
    949 	// OPTIMIZE: restrict the viewport on the mirrored view
    950 
    951 	// render the mirror view
    952 	R_RenderView (&newParms);
    953 
    954 	tr.viewParms = oldParms;
    955 
    956 	return qtrue;
    957 }
    958 
    959 /*
    960 =================
    961 R_SpriteFogNum
    962 
    963 See if a sprite is inside a fog volume
    964 =================
    965 */
    966 int R_SpriteFogNum( trRefEntity_t *ent ) {
    967 	int				i, j;
    968 	fog_t			*fog;
    969 
    970 	if ( tr.refdef.rdflags & RDF_NOWORLDMODEL ) {
    971 		return 0;
    972 	}
    973 
    974 	for ( i = 1 ; i < tr.world->numfogs ; i++ ) {
    975 		fog = &tr.world->fogs[i];
    976 		for ( j = 0 ; j < 3 ; j++ ) {
    977 			if ( ent->e.origin[j] - ent->e.radius >= fog->bounds[1][j] ) {
    978 				break;
    979 			}
    980 			if ( ent->e.origin[j] + ent->e.radius <= fog->bounds[0][j] ) {
    981 				break;
    982 			}
    983 		}
    984 		if ( j == 3 ) {
    985 			return i;
    986 		}
    987 	}
    988 
    989 	return 0;
    990 }
    991 
    992 /*
    993 ==========================================================================================
    994 
    995 DRAWSURF SORTING
    996 
    997 ==========================================================================================
    998 */
    999 
   1000 /*
   1001 =================
   1002 qsort replacement
   1003 
   1004 =================
   1005 */
   1006 #define	SWAP_DRAW_SURF(a,b) temp=((int *)a)[0];((int *)a)[0]=((int *)b)[0];((int *)b)[0]=temp; temp=((int *)a)[1];((int *)a)[1]=((int *)b)[1];((int *)b)[1]=temp;
   1007 
   1008 /* this parameter defines the cutoff between using quick sort and
   1009    insertion sort for arrays; arrays with lengths shorter or equal to the
   1010    below value use insertion sort */
   1011 
   1012 #define CUTOFF 8            /* testing shows that this is good value */
   1013 
   1014 static void shortsort( drawSurf_t *lo, drawSurf_t *hi ) {
   1015     drawSurf_t	*p, *max;
   1016 	int			temp;
   1017 
   1018     while (hi > lo) {
   1019         max = lo;
   1020         for (p = lo + 1; p <= hi; p++ ) {
   1021             if ( p->sort > max->sort ) {
   1022                 max = p;
   1023             }
   1024         }
   1025         SWAP_DRAW_SURF(max, hi);
   1026         hi--;
   1027     }
   1028 }
   1029 
   1030 
   1031 /* sort the array between lo and hi (inclusive)
   1032 FIXME: this was lifted and modified from the microsoft lib source...
   1033  */
   1034 
   1035 void qsortFast (
   1036     void *base,
   1037     unsigned num,
   1038     unsigned width
   1039     )
   1040 {
   1041     char *lo, *hi;              /* ends of sub-array currently sorting */
   1042     char *mid;                  /* points to middle of subarray */
   1043     char *loguy, *higuy;        /* traveling pointers for partition step */
   1044     unsigned size;              /* size of the sub-array */
   1045     char *lostk[30], *histk[30];
   1046     int stkptr;                 /* stack for saving sub-array to be processed */
   1047 	int	temp;
   1048 
   1049 	if ( sizeof(drawSurf_t) != 8 ) {
   1050 		ri.Error( ERR_DROP, "change SWAP_DRAW_SURF macro" );
   1051 	}
   1052 
   1053     /* Note: the number of stack entries required is no more than
   1054        1 + log2(size), so 30 is sufficient for any array */
   1055 
   1056     if (num < 2 || width == 0)
   1057         return;                 /* nothing to do */
   1058 
   1059     stkptr = 0;                 /* initialize stack */
   1060 
   1061     lo = base;
   1062     hi = (char *)base + width * (num-1);        /* initialize limits */
   1063 
   1064     /* this entry point is for pseudo-recursion calling: setting
   1065        lo and hi and jumping to here is like recursion, but stkptr is
   1066        prserved, locals aren't, so we preserve stuff on the stack */
   1067 recurse:
   1068 
   1069     size = (hi - lo) / width + 1;        /* number of el's to sort */
   1070 
   1071     /* below a certain size, it is faster to use a O(n^2) sorting method */
   1072     if (size <= CUTOFF) {
   1073          shortsort((drawSurf_t *)lo, (drawSurf_t *)hi);
   1074     }
   1075     else {
   1076         /* First we pick a partititioning element.  The efficiency of the
   1077            algorithm demands that we find one that is approximately the
   1078            median of the values, but also that we select one fast.  Using
   1079            the first one produces bad performace if the array is already
   1080            sorted, so we use the middle one, which would require a very
   1081            wierdly arranged array for worst case performance.  Testing shows
   1082            that a median-of-three algorithm does not, in general, increase
   1083            performance. */
   1084 
   1085         mid = lo + (size / 2) * width;      /* find middle element */
   1086         SWAP_DRAW_SURF(mid, lo);               /* swap it to beginning of array */
   1087 
   1088         /* We now wish to partition the array into three pieces, one
   1089            consisiting of elements <= partition element, one of elements
   1090            equal to the parition element, and one of element >= to it.  This
   1091            is done below; comments indicate conditions established at every
   1092            step. */
   1093 
   1094         loguy = lo;
   1095         higuy = hi + width;
   1096 
   1097         /* Note that higuy decreases and loguy increases on every iteration,
   1098            so loop must terminate. */
   1099         for (;;) {
   1100             /* lo <= loguy < hi, lo < higuy <= hi + 1,
   1101                A[i] <= A[lo] for lo <= i <= loguy,
   1102                A[i] >= A[lo] for higuy <= i <= hi */
   1103 
   1104             do  {
   1105                 loguy += width;
   1106             } while (loguy <= hi &&  
   1107 				( ((drawSurf_t *)loguy)->sort <= ((drawSurf_t *)lo)->sort ) );
   1108 
   1109             /* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
   1110                either loguy > hi or A[loguy] > A[lo] */
   1111 
   1112             do  {
   1113                 higuy -= width;
   1114             } while (higuy > lo && 
   1115 				( ((drawSurf_t *)higuy)->sort >= ((drawSurf_t *)lo)->sort ) );
   1116 
   1117             /* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
   1118                either higuy <= lo or A[higuy] < A[lo] */
   1119 
   1120             if (higuy < loguy)
   1121                 break;
   1122 
   1123             /* if loguy > hi or higuy <= lo, then we would have exited, so
   1124                A[loguy] > A[lo], A[higuy] < A[lo],
   1125                loguy < hi, highy > lo */
   1126 
   1127             SWAP_DRAW_SURF(loguy, higuy);
   1128 
   1129             /* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
   1130                of loop is re-established */
   1131         }
   1132 
   1133         /*     A[i] >= A[lo] for higuy < i <= hi,
   1134                A[i] <= A[lo] for lo <= i < loguy,
   1135                higuy < loguy, lo <= higuy <= hi
   1136            implying:
   1137                A[i] >= A[lo] for loguy <= i <= hi,
   1138                A[i] <= A[lo] for lo <= i <= higuy,
   1139                A[i] = A[lo] for higuy < i < loguy */
   1140 
   1141         SWAP_DRAW_SURF(lo, higuy);     /* put partition element in place */
   1142 
   1143         /* OK, now we have the following:
   1144               A[i] >= A[higuy] for loguy <= i <= hi,
   1145               A[i] <= A[higuy] for lo <= i < higuy
   1146               A[i] = A[lo] for higuy <= i < loguy    */
   1147 
   1148         /* We've finished the partition, now we want to sort the subarrays
   1149            [lo, higuy-1] and [loguy, hi].
   1150            We do the smaller one first to minimize stack usage.
   1151            We only sort arrays of length 2 or more.*/
   1152 
   1153         if ( higuy - 1 - lo >= hi - loguy ) {
   1154             if (lo + width < higuy) {
   1155                 lostk[stkptr] = lo;
   1156                 histk[stkptr] = higuy - width;
   1157                 ++stkptr;
   1158             }                           /* save big recursion for later */
   1159 
   1160             if (loguy < hi) {
   1161                 lo = loguy;
   1162                 goto recurse;           /* do small recursion */
   1163             }
   1164         }
   1165         else {
   1166             if (loguy < hi) {
   1167                 lostk[stkptr] = loguy;
   1168                 histk[stkptr] = hi;
   1169                 ++stkptr;               /* save big recursion for later */
   1170             }
   1171 
   1172             if (lo + width < higuy) {
   1173                 hi = higuy - width;
   1174                 goto recurse;           /* do small recursion */
   1175             }
   1176         }
   1177     }
   1178 
   1179     /* We have sorted the array, except for any pending sorts on the stack.
   1180        Check if there are any, and do them. */
   1181 
   1182     --stkptr;
   1183     if (stkptr >= 0) {
   1184         lo = lostk[stkptr];
   1185         hi = histk[stkptr];
   1186         goto recurse;           /* pop subarray from stack */
   1187     }
   1188     else
   1189         return;                 /* all subarrays done */
   1190 }
   1191 
   1192 
   1193 //==========================================================================================
   1194 
   1195 /*
   1196 =================
   1197 R_AddDrawSurf
   1198 =================
   1199 */
   1200 void R_AddDrawSurf( surfaceType_t *surface, shader_t *shader, 
   1201 				   int fogIndex, int dlightMap ) {
   1202 	int			index;
   1203 
   1204 	// instead of checking for overflow, we just mask the index
   1205 	// so it wraps around
   1206 	index = tr.refdef.numDrawSurfs & DRAWSURF_MASK;
   1207 	// the sort data is packed into a single 32 bit value so it can be
   1208 	// compared quickly during the qsorting process
   1209 	tr.refdef.drawSurfs[index].sort = (shader->sortedIndex << QSORT_SHADERNUM_SHIFT) 
   1210 		| tr.shiftedEntityNum | ( fogIndex << QSORT_FOGNUM_SHIFT ) | (int)dlightMap;
   1211 	tr.refdef.drawSurfs[index].surface = surface;
   1212 	tr.refdef.numDrawSurfs++;
   1213 }
   1214 
   1215 /*
   1216 =================
   1217 R_DecomposeSort
   1218 =================
   1219 */
   1220 void R_DecomposeSort( unsigned sort, int *entityNum, shader_t **shader, 
   1221 					 int *fogNum, int *dlightMap ) {
   1222 	*fogNum = ( sort >> QSORT_FOGNUM_SHIFT ) & 31;
   1223 	*shader = tr.sortedShaders[ ( sort >> QSORT_SHADERNUM_SHIFT ) & (MAX_SHADERS-1) ];
   1224 	*entityNum = ( sort >> QSORT_ENTITYNUM_SHIFT ) & 1023;
   1225 	*dlightMap = sort & 3;
   1226 }
   1227 
   1228 /*
   1229 =================
   1230 R_SortDrawSurfs
   1231 =================
   1232 */
   1233 void R_SortDrawSurfs( drawSurf_t *drawSurfs, int numDrawSurfs ) {
   1234 	shader_t		*shader;
   1235 	int				fogNum;
   1236 	int				entityNum;
   1237 	int				dlighted;
   1238 	int				i;
   1239 
   1240 	// it is possible for some views to not have any surfaces
   1241 	if ( numDrawSurfs < 1 ) {
   1242 		// we still need to add it for hyperspace cases
   1243 		R_AddDrawSurfCmd( drawSurfs, numDrawSurfs );
   1244 		return;
   1245 	}
   1246 
   1247 	// if we overflowed MAX_DRAWSURFS, the drawsurfs
   1248 	// wrapped around in the buffer and we will be missing
   1249 	// the first surfaces, not the last ones
   1250 	if ( numDrawSurfs > MAX_DRAWSURFS ) {
   1251 		numDrawSurfs = MAX_DRAWSURFS;
   1252 	}
   1253 
   1254 	// sort the drawsurfs by sort type, then orientation, then shader
   1255 	qsortFast (drawSurfs, numDrawSurfs, sizeof(drawSurf_t) );
   1256 
   1257 	// check for any pass through drawing, which
   1258 	// may cause another view to be rendered first
   1259 	for ( i = 0 ; i < numDrawSurfs ; i++ ) {
   1260 		R_DecomposeSort( (drawSurfs+i)->sort, &entityNum, &shader, &fogNum, &dlighted );
   1261 
   1262 		if ( shader->sort > SS_PORTAL ) {
   1263 			break;
   1264 		}
   1265 
   1266 		// no shader should ever have this sort type
   1267 		if ( shader->sort == SS_BAD ) {
   1268 			ri.Error (ERR_DROP, "Shader '%s'with sort == SS_BAD", shader->name );
   1269 		}
   1270 
   1271 		// if the mirror was completely clipped away, we may need to check another surface
   1272 		if ( R_MirrorViewBySurface( (drawSurfs+i), entityNum) ) {
   1273 			// this is a debug option to see exactly what is being mirrored
   1274 			if ( r_portalOnly->integer ) {
   1275 				return;
   1276 			}
   1277 			break;		// only one mirror view at a time
   1278 		}
   1279 	}
   1280 
   1281 	R_AddDrawSurfCmd( drawSurfs, numDrawSurfs );
   1282 }
   1283 
   1284 /*
   1285 =============
   1286 R_AddEntitySurfaces
   1287 =============
   1288 */
   1289 void R_AddEntitySurfaces (void) {
   1290 	trRefEntity_t	*ent;
   1291 	shader_t		*shader;
   1292 
   1293 	if ( !r_drawentities->integer ) {
   1294 		return;
   1295 	}
   1296 
   1297 	for ( tr.currentEntityNum = 0; 
   1298 	      tr.currentEntityNum < tr.refdef.num_entities; 
   1299 		  tr.currentEntityNum++ ) {
   1300 		ent = tr.currentEntity = &tr.refdef.entities[tr.currentEntityNum];
   1301 
   1302 		ent->needDlights = qfalse;
   1303 
   1304 		// preshift the value we are going to OR into the drawsurf sort
   1305 		tr.shiftedEntityNum = tr.currentEntityNum << QSORT_ENTITYNUM_SHIFT;
   1306 
   1307 		//
   1308 		// the weapon model must be handled special --
   1309 		// we don't want the hacked weapon position showing in 
   1310 		// mirrors, because the true body position will already be drawn
   1311 		//
   1312 		if ( (ent->e.renderfx & RF_FIRST_PERSON) && tr.viewParms.isPortal) {
   1313 			continue;
   1314 		}
   1315 
   1316 		// simple generated models, like sprites and beams, are not culled
   1317 		switch ( ent->e.reType ) {
   1318 		case RT_PORTALSURFACE:
   1319 			break;		// don't draw anything
   1320 		case RT_SPRITE:
   1321 		case RT_BEAM:
   1322 		case RT_LIGHTNING:
   1323 		case RT_RAIL_CORE:
   1324 		case RT_RAIL_RINGS:
   1325 			// self blood sprites, talk balloons, etc should not be drawn in the primary
   1326 			// view.  We can't just do this check for all entities, because md3
   1327 			// entities may still want to cast shadows from them
   1328 			if ( (ent->e.renderfx & RF_THIRD_PERSON) && !tr.viewParms.isPortal) {
   1329 				continue;
   1330 			}
   1331 			shader = R_GetShaderByHandle( ent->e.customShader );
   1332 			R_AddDrawSurf( &entitySurface, shader, R_SpriteFogNum( ent ), 0 );
   1333 			break;
   1334 
   1335 		case RT_MODEL:
   1336 			// we must set up parts of tr.or for model culling
   1337 			R_RotateForEntity( ent, &tr.viewParms, &tr.or );
   1338 
   1339 			tr.currentModel = R_GetModelByHandle( ent->e.hModel );
   1340 			if (!tr.currentModel) {
   1341 				R_AddDrawSurf( &entitySurface, tr.defaultShader, 0, 0 );
   1342 			} else {
   1343 				switch ( tr.currentModel->type ) {
   1344 				case MOD_MESH:
   1345 					R_AddMD3Surfaces( ent );
   1346 					break;
   1347 				case MOD_MD4:
   1348 					R_AddAnimSurfaces( ent );
   1349 					break;
   1350 				case MOD_BRUSH:
   1351 					R_AddBrushModelSurfaces( ent );
   1352 					break;
   1353 				case MOD_BAD:		// null model axis
   1354 					if ( (ent->e.renderfx & RF_THIRD_PERSON) && !tr.viewParms.isPortal) {
   1355 						break;
   1356 					}
   1357 					shader = R_GetShaderByHandle( ent->e.customShader );
   1358 					R_AddDrawSurf( &entitySurface, tr.defaultShader, 0, 0 );
   1359 					break;
   1360 				default:
   1361 					ri.Error( ERR_DROP, "R_AddEntitySurfaces: Bad modeltype" );
   1362 					break;
   1363 				}
   1364 			}
   1365 			break;
   1366 		default:
   1367 			ri.Error( ERR_DROP, "R_AddEntitySurfaces: Bad reType" );
   1368 		}
   1369 	}
   1370 
   1371 }
   1372 
   1373 
   1374 /*
   1375 ====================
   1376 R_GenerateDrawSurfs
   1377 ====================
   1378 */
   1379 void R_GenerateDrawSurfs( void ) {
   1380 	R_AddWorldSurfaces ();
   1381 
   1382 	R_AddPolygonSurfaces();
   1383 
   1384 	// set the projection matrix with the minimum zfar
   1385 	// now that we have the world bounded
   1386 	// this needs to be done before entities are
   1387 	// added, because they use the projection
   1388 	// matrix for lod calculation
   1389 	R_SetupProjection ();
   1390 
   1391 	R_AddEntitySurfaces ();
   1392 }
   1393 
   1394 /*
   1395 ================
   1396 R_DebugPolygon
   1397 ================
   1398 */
   1399 void R_DebugPolygon( int color, int numPoints, float *points ) {
   1400 	int		i;
   1401 
   1402 	GL_State( GLS_DEPTHMASK_TRUE | GLS_SRCBLEND_ONE | GLS_DSTBLEND_ONE );
   1403 
   1404 	// draw solid shade
   1405 
   1406 	qglColor3f( color&1, (color>>1)&1, (color>>2)&1 );
   1407 	qglBegin( GL_POLYGON );
   1408 	for ( i = 0 ; i < numPoints ; i++ ) {
   1409 		qglVertex3fv( points + i * 3 );
   1410 	}
   1411 	qglEnd();
   1412 
   1413 	// draw wireframe outline
   1414 	GL_State( GLS_POLYMODE_LINE | GLS_DEPTHMASK_TRUE | GLS_SRCBLEND_ONE | GLS_DSTBLEND_ONE );
   1415 	qglDepthRange( 0, 0 );
   1416 	qglColor3f( 1, 1, 1 );
   1417 	qglBegin( GL_POLYGON );
   1418 	for ( i = 0 ; i < numPoints ; i++ ) {
   1419 		qglVertex3fv( points + i * 3 );
   1420 	}
   1421 	qglEnd();
   1422 	qglDepthRange( 0, 1 );
   1423 }
   1424 
   1425 /*
   1426 ====================
   1427 R_DebugGraphics
   1428 
   1429 Visualization aid for movement clipping debugging
   1430 ====================
   1431 */
   1432 void R_DebugGraphics( void ) {
   1433 	if ( !r_debugSurface->integer ) {
   1434 		return;
   1435 	}
   1436 
   1437 	// the render thread can't make callbacks to the main thread
   1438 	R_SyncRenderThread();
   1439 
   1440 	GL_Bind( tr.whiteImage);
   1441 	GL_Cull( CT_FRONT_SIDED );
   1442 	ri.CM_DrawDebugSurface( R_DebugPolygon );
   1443 }
   1444 
   1445 
   1446 /*
   1447 ================
   1448 R_RenderView
   1449 
   1450 A view may be either the actual camera view,
   1451 or a mirror / remote location
   1452 ================
   1453 */
   1454 void R_RenderView (viewParms_t *parms) {
   1455 	int		firstDrawSurf;
   1456 
   1457 	if ( parms->viewportWidth <= 0 || parms->viewportHeight <= 0 ) {
   1458 		return;
   1459 	}
   1460 
   1461 	tr.viewCount++;
   1462 
   1463 	tr.viewParms = *parms;
   1464 	tr.viewParms.frameSceneNum = tr.frameSceneNum;
   1465 	tr.viewParms.frameCount = tr.frameCount;
   1466 
   1467 	firstDrawSurf = tr.refdef.numDrawSurfs;
   1468 
   1469 	tr.viewCount++;
   1470 
   1471 	// set viewParms.world
   1472 	R_RotateForViewer ();
   1473 
   1474 	R_SetupFrustum ();
   1475 
   1476 	R_GenerateDrawSurfs();
   1477 
   1478 	R_SortDrawSurfs( tr.refdef.drawSurfs + firstDrawSurf, tr.refdef.numDrawSurfs - firstDrawSurf );
   1479 
   1480 	// draw main system development information (surface outlines, etc)
   1481 	R_DebugGraphics();
   1482 }
   1483 
   1484 
   1485