Main Page | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Data Fields | Globals
code / renderer

tr_main.c

Go to the documentation of this file.
00001 /*
00002 ===========================================================================
00003 Copyright (C) 1999-2005 Id Software, Inc.
00004 
00005 This file is part of Quake III Arena source code.
00006 
00007 Quake III Arena source code is free software; you can redistribute it
00008 and/or modify it under the terms of the GNU General Public License as
00009 published by the Free Software Foundation; either version 2 of the License,
00010 or (at your option) any later version.
00011 
00012 Quake III Arena source code is distributed in the hope that it will be
00013 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 GNU General Public License for more details.
00016 
00017 You should have received a copy of the GNU General Public License
00018 along with Foobar; if not, write to the Free Software
00019 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00020 ===========================================================================
00021 */
00022 // tr_main.c -- main control flow for each frame
00023 
00024 #include "tr_local.h"
00025 
00026 trGlobals_t     tr;
00027 
00028 static float    s_flipMatrix[16] = {
00029     // convert from our coordinate system (looking down X)
00030     // to OpenGL's coordinate system (looking down -Z)
00031     0, 0, -1, 0,
00032     -1, 0, 0, 0,
00033     0, 1, 0, 0,
00034     0, 0, 0, 1
00035 };
00036 
00037 
00038 refimport_t ri;
00039 
00040 // entities that will have procedurally generated surfaces will just
00041 // point at this for their sorting surface
00042 surfaceType_t   entitySurface = SF_ENTITY;
00043 
00044 /*
00045 =================
00046 R_CullLocalBox
00047 
00048 Returns CULL_IN, CULL_CLIP, or CULL_OUT
00049 =================
00050 */
00051 int R_CullLocalBox (vec3_t bounds[2]) {
00052     int     i, j;
00053     vec3_t  transformed[8];
00054     float   dists[8];
00055     vec3_t  v;
00056     cplane_t    *frust;
00057     int         anyBack;
00058     int         front, back;
00059 
00060     if ( r_nocull->integer ) {
00061         return CULL_CLIP;
00062     }
00063 
00064     // transform into world space
00065     for (i = 0 ; i < 8 ; i++) {
00066         v[0] = bounds[i&1][0];
00067         v[1] = bounds[(i>>1)&1][1];
00068         v[2] = bounds[(i>>2)&1][2];
00069 
00070         VectorCopy( tr.or.origin, transformed[i] );
00071         VectorMA( transformed[i], v[0], tr.or.axis[0], transformed[i] );
00072         VectorMA( transformed[i], v[1], tr.or.axis[1], transformed[i] );
00073         VectorMA( transformed[i], v[2], tr.or.axis[2], transformed[i] );
00074     }
00075 
00076     // check against frustum planes
00077     anyBack = 0;
00078     for (i = 0 ; i < 4 ; i++) {
00079         frust = &tr.viewParms.frustum[i];
00080 
00081         front = back = 0;
00082         for (j = 0 ; j < 8 ; j++) {
00083             dists[j] = DotProduct(transformed[j], frust->normal);
00084             if ( dists[j] > frust->dist ) {
00085                 front = 1;
00086                 if ( back ) {
00087                     break;      // a point is in front
00088                 }
00089             } else {
00090                 back = 1;
00091             }
00092         }
00093         if ( !front ) {
00094             // all points were behind one of the planes
00095             return CULL_OUT;
00096         }
00097         anyBack |= back;
00098     }
00099 
00100     if ( !anyBack ) {
00101         return CULL_IN;     // completely inside frustum
00102     }
00103 
00104     return CULL_CLIP;       // partially clipped
00105 }
00106 
00107 /*
00108 ** R_CullLocalPointAndRadius
00109 */
00110 int R_CullLocalPointAndRadius( vec3_t pt, float radius )
00111 {
00112     vec3_t transformed;
00113 
00114     R_LocalPointToWorld( pt, transformed );
00115 
00116     return R_CullPointAndRadius( transformed, radius );
00117 }
00118 
00119 /*
00120 ** R_CullPointAndRadius
00121 */
00122 int R_CullPointAndRadius( vec3_t pt, float radius )
00123 {
00124     int     i;
00125     float   dist;
00126     cplane_t    *frust;
00127     qboolean mightBeClipped = qfalse;
00128 
00129     if ( r_nocull->integer ) {
00130         return CULL_CLIP;
00131     }
00132 
00133     // check against frustum planes
00134     for (i = 0 ; i < 4 ; i++) 
00135     {
00136         frust = &tr.viewParms.frustum[i];
00137 
00138         dist = DotProduct( pt, frust->normal) - frust->dist;
00139         if ( dist < -radius )
00140         {
00141             return CULL_OUT;
00142         }
00143         else if ( dist <= radius ) 
00144         {
00145             mightBeClipped = qtrue;
00146         }
00147     }
00148 
00149     if ( mightBeClipped )
00150     {
00151         return CULL_CLIP;
00152     }
00153 
00154     return CULL_IN;     // completely inside frustum
00155 }
00156 
00157 
00158 /*
00159 =================
00160 R_LocalNormalToWorld
00161 
00162 =================
00163 */
00164 void R_LocalNormalToWorld (vec3_t local, vec3_t world) {
00165     world[0] = local[0] * tr.or.axis[0][0] + local[1] * tr.or.axis[1][0] + local[2] * tr.or.axis[2][0];
00166     world[1] = local[0] * tr.or.axis[0][1] + local[1] * tr.or.axis[1][1] + local[2] * tr.or.axis[2][1];
00167     world[2] = local[0] * tr.or.axis[0][2] + local[1] * tr.or.axis[1][2] + local[2] * tr.or.axis[2][2];
00168 }
00169 
00170 /*
00171 =================
00172 R_LocalPointToWorld
00173 
00174 =================
00175 */
00176 void R_LocalPointToWorld (vec3_t local, vec3_t world) {
00177     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];
00178     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];
00179     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];
00180 }
00181 
00182 /*
00183 =================
00184 R_WorldToLocal
00185 
00186 =================
00187 */
00188 void R_WorldToLocal (vec3_t world, vec3_t local) {
00189     local[0] = DotProduct(world, tr.or.axis[0]);
00190     local[1] = DotProduct(world, tr.or.axis[1]);
00191     local[2] = DotProduct(world, tr.or.axis[2]);
00192 }
00193 
00194 /*
00195 ==========================
00196 R_TransformModelToClip
00197 
00198 ==========================
00199 */
00200 void R_TransformModelToClip( const vec3_t src, const float *modelMatrix, const float *projectionMatrix,
00201                             vec4_t eye, vec4_t dst ) {
00202     int i;
00203 
00204     for ( i = 0 ; i < 4 ; i++ ) {
00205         eye[i] = 
00206             src[0] * modelMatrix[ i + 0 * 4 ] +
00207             src[1] * modelMatrix[ i + 1 * 4 ] +
00208             src[2] * modelMatrix[ i + 2 * 4 ] +
00209             1 * modelMatrix[ i + 3 * 4 ];
00210     }
00211 
00212     for ( i = 0 ; i < 4 ; i++ ) {
00213         dst[i] = 
00214             eye[0] * projectionMatrix[ i + 0 * 4 ] +
00215             eye[1] * projectionMatrix[ i + 1 * 4 ] +
00216             eye[2] * projectionMatrix[ i + 2 * 4 ] +
00217             eye[3] * projectionMatrix[ i + 3 * 4 ];
00218     }
00219 }
00220 
00221 /*
00222 ==========================
00223 R_TransformClipToWindow
00224 
00225 ==========================
00226 */
00227 void R_TransformClipToWindow( const vec4_t clip, const viewParms_t *view, vec4_t normalized, vec4_t window ) {
00228     normalized[0] = clip[0] / clip[3];
00229     normalized[1] = clip[1] / clip[3];
00230     normalized[2] = ( clip[2] + clip[3] ) / ( 2 * clip[3] );
00231 
00232     window[0] = 0.5f * ( 1.0f + normalized[0] ) * view->viewportWidth;
00233     window[1] = 0.5f * ( 1.0f + normalized[1] ) * view->viewportHeight;
00234     window[2] = normalized[2];
00235 
00236     window[0] = (int) ( window[0] + 0.5 );
00237     window[1] = (int) ( window[1] + 0.5 );
00238 }
00239 
00240 
00241 /*
00242 ==========================
00243 myGlMultMatrix
00244 
00245 ==========================
00246 */
00247 void myGlMultMatrix( const float *a, const float *b, float *out ) {
00248     int     i, j;
00249 
00250     for ( i = 0 ; i < 4 ; i++ ) {
00251         for ( j = 0 ; j < 4 ; j++ ) {
00252             out[ i * 4 + j ] =
00253                 a [ i * 4 + 0 ] * b [ 0 * 4 + j ]
00254                 + a [ i * 4 + 1 ] * b [ 1 * 4 + j ]
00255                 + a [ i * 4 + 2 ] * b [ 2 * 4 + j ]
00256                 + a [ i * 4 + 3 ] * b [ 3 * 4 + j ];
00257         }
00258     }
00259 }
00260 
00261 /*
00262 =================
00263 R_RotateForEntity
00264 
00265 Generates an orientation for an entity and viewParms
00266 Does NOT produce any GL calls
00267 Called by both the front end and the back end
00268 =================
00269 */
00270 void R_RotateForEntity( const trRefEntity_t *ent, const viewParms_t *viewParms,
00271                        orientationr_t *or ) {
00272     float   glMatrix[16];
00273     vec3_t  delta;
00274     float   axisLength;
00275 
00276     if ( ent->e.reType != RT_MODEL ) {
00277         *or = viewParms->world;
00278         return;
00279     }
00280 
00281     VectorCopy( ent->e.origin, or->origin );
00282 
00283     VectorCopy( ent->e.axis[0], or->axis[0] );
00284     VectorCopy( ent->e.axis[1], or->axis[1] );
00285     VectorCopy( ent->e.axis[2], or->axis[2] );
00286 
00287     glMatrix[0] = or->axis[0][0];
00288     glMatrix[4] = or->axis[1][0];
00289     glMatrix[8] = or->axis[2][0];
00290     glMatrix[12] = or->origin[0];
00291 
00292     glMatrix[1] = or->axis[0][1];
00293     glMatrix[5] = or->axis[1][1];
00294     glMatrix[9] = or->axis[2][1];
00295     glMatrix[13] = or->origin[1];
00296 
00297     glMatrix[2] = or->axis[0][2];
00298     glMatrix[6] = or->axis[1][2];
00299     glMatrix[10] = or->axis[2][2];
00300     glMatrix[14] = or->origin[2];
00301 
00302     glMatrix[3] = 0;
00303     glMatrix[7] = 0;
00304     glMatrix[11] = 0;
00305     glMatrix[15] = 1;
00306 
00307     myGlMultMatrix( glMatrix, viewParms->world.modelMatrix, or->modelMatrix );
00308 
00309     // calculate the viewer origin in the model's space
00310     // needed for fog, specular, and environment mapping
00311     VectorSubtract( viewParms->or.origin, or->origin, delta );
00312 
00313     // compensate for scale in the axes if necessary
00314     if ( ent->e.nonNormalizedAxes ) {
00315         axisLength = VectorLength( ent->e.axis[0] );
00316         if ( !axisLength ) {
00317             axisLength = 0;
00318         } else {
00319             axisLength = 1.0f / axisLength;
00320         }
00321     } else {
00322         axisLength = 1.0f;
00323     }
00324 
00325     or->viewOrigin[0] = DotProduct( delta, or->axis[0] ) * axisLength;
00326     or->viewOrigin[1] = DotProduct( delta, or->axis[1] ) * axisLength;
00327     or->viewOrigin[2] = DotProduct( delta, or->axis[2] ) * axisLength;
00328 }
00329 
00330 /*
00331 =================
00332 R_RotateForViewer
00333 
00334 Sets up the modelview matrix for a given viewParm
00335 =================
00336 */
00337 void R_RotateForViewer (void) 
00338 {
00339     float   viewerMatrix[16];
00340     vec3_t  origin;
00341 
00342     Com_Memset (&tr.or, 0, sizeof(tr.or));
00343     tr.or.axis[0][0] = 1;
00344     tr.or.axis[1][1] = 1;
00345     tr.or.axis[2][2] = 1;
00346     VectorCopy (tr.viewParms.or.origin, tr.or.viewOrigin);
00347 
00348     // transform by the camera placement
00349     VectorCopy( tr.viewParms.or.origin, origin );
00350 
00351     viewerMatrix[0] = tr.viewParms.or.axis[0][0];
00352     viewerMatrix[4] = tr.viewParms.or.axis[0][1];
00353     viewerMatrix[8] = tr.viewParms.or.axis[0][2];
00354     viewerMatrix[12] = -origin[0] * viewerMatrix[0] + -origin[1] * viewerMatrix[4] + -origin[2] * viewerMatrix[8];
00355 
00356     viewerMatrix[1] = tr.viewParms.or.axis[1][0];
00357     viewerMatrix[5] = tr.viewParms.or.axis[1][1];
00358     viewerMatrix[9] = tr.viewParms.or.axis[1][2];
00359     viewerMatrix[13] = -origin[0] * viewerMatrix[1] + -origin[1] * viewerMatrix[5] + -origin[2] * viewerMatrix[9];
00360 
00361     viewerMatrix[2] = tr.viewParms.or.axis[2][0];
00362     viewerMatrix[6] = tr.viewParms.or.axis[2][1];
00363     viewerMatrix[10] = tr.viewParms.or.axis[2][2];
00364     viewerMatrix[14] = -origin[0] * viewerMatrix[2] + -origin[1] * viewerMatrix[6] + -origin[2] * viewerMatrix[10];
00365 
00366     viewerMatrix[3] = 0;
00367     viewerMatrix[7] = 0;
00368     viewerMatrix[11] = 0;
00369     viewerMatrix[15] = 1;
00370 
00371     // convert from our coordinate system (looking down X)
00372     // to OpenGL's coordinate system (looking down -Z)
00373     myGlMultMatrix( viewerMatrix, s_flipMatrix, tr.or.modelMatrix );
00374 
00375     tr.viewParms.world = tr.or;
00376 
00377 }
00378 
00379 /*
00380 ** SetFarClip
00381 */
00382 static void SetFarClip( void )
00383 {
00384     float   farthestCornerDistance = 0;
00385     int     i;
00386 
00387     // if not rendering the world (icons, menus, etc)
00388     // set a 2k far clip plane
00389     if ( tr.refdef.rdflags & RDF_NOWORLDMODEL ) {
00390         tr.viewParms.zFar = 2048;
00391         return;
00392     }
00393 
00394     //
00395     // set far clipping planes dynamically
00396     //
00397     farthestCornerDistance = 0;
00398     for ( i = 0; i < 8; i++ )
00399     {
00400         vec3_t v;
00401         vec3_t vecTo;
00402         float distance;
00403 
00404         if ( i & 1 )
00405         {
00406             v[0] = tr.viewParms.visBounds[0][0];
00407         }
00408         else
00409         {
00410             v[0] = tr.viewParms.visBounds[1][0];
00411         }
00412 
00413         if ( i & 2 )
00414         {
00415             v[1] = tr.viewParms.visBounds[0][1];
00416         }
00417         else
00418         {
00419             v[1] = tr.viewParms.visBounds[1][1];
00420         }
00421 
00422         if ( i & 4 )
00423         {
00424             v[2] = tr.viewParms.visBounds[0][2];
00425         }
00426         else
00427         {
00428             v[2] = tr.viewParms.visBounds[1][2];
00429         }
00430 
00431         VectorSubtract( v, tr.viewParms.or.origin, vecTo );
00432 
00433         distance = vecTo[0] * vecTo[0] + vecTo[1] * vecTo[1] + vecTo[2] * vecTo[2];
00434 
00435         if ( distance > farthestCornerDistance )
00436         {
00437             farthestCornerDistance = distance;
00438         }
00439     }
00440     tr.viewParms.zFar = sqrt( farthestCornerDistance );
00441 }
00442 
00443 
00444 /*
00445 ===============
00446 R_SetupProjection
00447 ===============
00448 */
00449 void R_SetupProjection( void ) {
00450     float   xmin, xmax, ymin, ymax;
00451     float   width, height, depth;
00452     float   zNear, zFar;
00453 
00454     // dynamically compute far clip plane distance
00455     SetFarClip();
00456 
00457     //
00458     // set up projection matrix
00459     //
00460     zNear   = r_znear->value;
00461     zFar    = tr.viewParms.zFar;
00462 
00463     ymax = zNear * tan( tr.refdef.fov_y * M_PI / 360.0f );
00464     ymin = -ymax;
00465 
00466     xmax = zNear * tan( tr.refdef.fov_x * M_PI / 360.0f );
00467     xmin = -xmax;
00468 
00469     width = xmax - xmin;
00470     height = ymax - ymin;
00471     depth = zFar - zNear;
00472 
00473     tr.viewParms.projectionMatrix[0] = 2 * zNear / width;
00474     tr.viewParms.projectionMatrix[4] = 0;
00475     tr.viewParms.projectionMatrix[8] = ( xmax + xmin ) / width; // normally 0
00476     tr.viewParms.projectionMatrix[12] = 0;
00477 
00478     tr.viewParms.projectionMatrix[1] = 0;
00479     tr.viewParms.projectionMatrix[5] = 2 * zNear / height;
00480     tr.viewParms.projectionMatrix[9] = ( ymax + ymin ) / height;    // normally 0
00481     tr.viewParms.projectionMatrix[13] = 0;
00482 
00483     tr.viewParms.projectionMatrix[2] = 0;
00484     tr.viewParms.projectionMatrix[6] = 0;
00485     tr.viewParms.projectionMatrix[10] = -( zFar + zNear ) / depth;
00486     tr.viewParms.projectionMatrix[14] = -2 * zFar * zNear / depth;
00487 
00488     tr.viewParms.projectionMatrix[3] = 0;
00489     tr.viewParms.projectionMatrix[7] = 0;
00490     tr.viewParms.projectionMatrix[11] = -1;
00491     tr.viewParms.projectionMatrix[15] = 0;
00492 }
00493 
00494 /*
00495 =================
00496 R_SetupFrustum
00497 
00498 Setup that culling frustum planes for the current view
00499 =================
00500 */
00501 void R_SetupFrustum (void) {
00502     int     i;
00503     float   xs, xc;
00504     float   ang;
00505 
00506     ang = tr.viewParms.fovX / 180 * M_PI * 0.5f;
00507     xs = sin( ang );
00508     xc = cos( ang );
00509 
00510     VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[0].normal );
00511     VectorMA( tr.viewParms.frustum[0].normal, xc, tr.viewParms.or.axis[1], tr.viewParms.frustum[0].normal );
00512 
00513     VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[1].normal );
00514     VectorMA( tr.viewParms.frustum[1].normal, -xc, tr.viewParms.or.axis[1], tr.viewParms.frustum[1].normal );
00515 
00516     ang = tr.viewParms.fovY / 180 * M_PI * 0.5f;
00517     xs = sin( ang );
00518     xc = cos( ang );
00519 
00520     VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[2].normal );
00521     VectorMA( tr.viewParms.frustum[2].normal, xc, tr.viewParms.or.axis[2], tr.viewParms.frustum[2].normal );
00522 
00523     VectorScale( tr.viewParms.or.axis[0], xs, tr.viewParms.frustum[3].normal );
00524     VectorMA( tr.viewParms.frustum[3].normal, -xc, tr.viewParms.or.axis[2], tr.viewParms.frustum[3].normal );
00525 
00526     for (i=0 ; i<4 ; i++) {
00527         tr.viewParms.frustum[i].type = PLANE_NON_AXIAL;
00528         tr.viewParms.frustum[i].dist = DotProduct (tr.viewParms.or.origin, tr.viewParms.frustum[i].normal);
00529         SetPlaneSignbits( &tr.viewParms.frustum[i] );
00530     }
00531 }
00532 
00533 
00534 /*
00535 =================
00536 R_MirrorPoint
00537 =================
00538 */
00539 void R_MirrorPoint (vec3_t in, orientation_t *surface, orientation_t *camera, vec3_t out) {
00540     int     i;
00541     vec3_t  local;
00542     vec3_t  transformed;
00543     float   d;
00544 
00545     VectorSubtract( in, surface->origin, local );
00546 
00547     VectorClear( transformed );
00548     for ( i = 0 ; i < 3 ; i++ ) {
00549         d = DotProduct(local, surface->axis[i]);
00550         VectorMA( transformed, d, camera->axis[i], transformed );
00551     }
00552 
00553     VectorAdd( transformed, camera->origin, out );
00554 }
00555 
00556 void R_MirrorVector (vec3_t in, orientation_t *surface, orientation_t *camera, vec3_t out) {
00557     int     i;
00558     float   d;
00559 
00560     VectorClear( out );
00561     for ( i = 0 ; i < 3 ; i++ ) {
00562         d = DotProduct(in, surface->axis[i]);
00563         VectorMA( out, d, camera->axis[i], out );
00564     }
00565 }
00566 
00567 
00568 /*
00569 =============
00570 R_PlaneForSurface
00571 =============
00572 */
00573 void R_PlaneForSurface (surfaceType_t *surfType, cplane_t *plane) {
00574     srfTriangles_t  *tri;
00575     srfPoly_t       *poly;
00576     drawVert_t      *v1, *v2, *v3;
00577     vec4_t          plane4;
00578 
00579     if (!surfType) {
00580         Com_Memset (plane, 0, sizeof(*plane));
00581         plane->normal[0] = 1;
00582         return;
00583     }
00584     switch (*surfType) {
00585     case SF_FACE:
00586         *plane = ((srfSurfaceFace_t *)surfType)->plane;
00587         return;
00588     case SF_TRIANGLES:
00589         tri = (srfTriangles_t *)surfType;
00590         v1 = tri->verts + tri->indexes[0];
00591         v2 = tri->verts + tri->indexes[1];
00592         v3 = tri->verts + tri->indexes[2];
00593         PlaneFromPoints( plane4, v1->xyz, v2->xyz, v3->xyz );
00594         VectorCopy( plane4, plane->normal ); 
00595         plane->dist = plane4[3];
00596         return;
00597     case SF_POLY:
00598         poly = (srfPoly_t *)surfType;
00599         PlaneFromPoints( plane4, poly->verts[0].xyz, poly->verts[1].xyz, poly->verts[2].xyz );
00600         VectorCopy( plane4, plane->normal ); 
00601         plane->dist = plane4[3];
00602         return;
00603     default:
00604         Com_Memset (plane, 0, sizeof(*plane));
00605         plane->normal[0] = 1;       
00606         return;
00607     }
00608 }
00609 
00610 /*
00611 =================
00612 R_GetPortalOrientation
00613 
00614 entityNum is the entity that the portal surface is a part of, which may
00615 be moving and rotating.
00616 
00617 Returns qtrue if it should be mirrored
00618 =================
00619 */
00620 qboolean R_GetPortalOrientations( drawSurf_t *drawSurf, int entityNum, 
00621                              orientation_t *surface, orientation_t *camera,
00622                              vec3_t pvsOrigin, qboolean *mirror ) {
00623     int         i;
00624     cplane_t    originalPlane, plane;
00625     trRefEntity_t   *e;
00626     float       d;
00627     vec3_t      transformed;
00628 
00629     // create plane axis for the portal we are seeing
00630     R_PlaneForSurface( drawSurf->surface, &originalPlane );
00631 
00632     // rotate the plane if necessary
00633     if ( entityNum != ENTITYNUM_WORLD ) {
00634         tr.currentEntityNum = entityNum;
00635         tr.currentEntity = &tr.refdef.entities[entityNum];
00636 
00637         // get the orientation of the entity
00638         R_RotateForEntity( tr.currentEntity, &tr.viewParms, &tr.or );
00639 
00640         // rotate the plane, but keep the non-rotated version for matching
00641         // against the portalSurface entities
00642         R_LocalNormalToWorld( originalPlane.normal, plane.normal );
00643         plane.dist = originalPlane.dist + DotProduct( plane.normal, tr.or.origin );
00644 
00645         // translate the original plane
00646         originalPlane.dist = originalPlane.dist + DotProduct( originalPlane.normal, tr.or.origin );
00647     } else {
00648         plane = originalPlane;
00649     }
00650 
00651     VectorCopy( plane.normal, surface->axis[0] );
00652     PerpendicularVector( surface->axis[1], surface->axis[0] );
00653     CrossProduct( surface->axis[0], surface->axis[1], surface->axis[2] );
00654 
00655     // locate the portal entity closest to this plane.
00656     // origin will be the origin of the portal, origin2 will be
00657     // the origin of the camera
00658     for ( i = 0 ; i < tr.refdef.num_entities ; i++ ) {
00659         e = &tr.refdef.entities[i];
00660         if ( e->e.reType != RT_PORTALSURFACE ) {
00661             continue;
00662         }
00663 
00664         d = DotProduct( e->e.origin, originalPlane.normal ) - originalPlane.dist;
00665         if ( d > 64 || d < -64) {
00666             continue;
00667         }
00668 
00669         // get the pvsOrigin from the entity
00670         VectorCopy( e->e.oldorigin, pvsOrigin );
00671 
00672         // if the entity is just a mirror, don't use as a camera point
00673         if ( e->e.oldorigin[0] == e->e.origin[0] && 
00674             e->e.oldorigin[1] == e->e.origin[1] && 
00675             e->e.oldorigin[2] == e->e.origin[2] ) {
00676             VectorScale( plane.normal, plane.dist, surface->origin );
00677             VectorCopy( surface->origin, camera->origin );
00678             VectorSubtract( vec3_origin, surface->axis[0], camera->axis[0] );
00679             VectorCopy( surface->axis[1], camera->axis[1] );
00680             VectorCopy( surface->axis[2], camera->axis[2] );
00681 
00682             *mirror = qtrue;
00683             return qtrue;
00684         }
00685 
00686         // project the origin onto the surface plane to get
00687         // an origin point we can rotate around
00688         d = DotProduct( e->e.origin, plane.normal ) - plane.dist;
00689         VectorMA( e->e.origin, -d, surface->axis[0], surface->origin );
00690             
00691         // now get the camera origin and orientation
00692         VectorCopy( e->e.oldorigin, camera->origin );
00693         AxisCopy( e->e.axis, camera->axis );
00694         VectorSubtract( vec3_origin, camera->axis[0], camera->axis[0] );
00695         VectorSubtract( vec3_origin, camera->axis[1], camera->axis[1] );
00696 
00697         // optionally rotate
00698         if ( e->e.oldframe ) {
00699             // if a speed is specified
00700             if ( e->e.frame ) {
00701                 // continuous rotate
00702                 d = (tr.refdef.time/1000.0f) * e->e.frame;
00703                 VectorCopy( camera->axis[1], transformed );
00704                 RotatePointAroundVector( camera->axis[1], camera->axis[0], transformed, d );
00705                 CrossProduct( camera->axis[0], camera->axis[1], camera->axis[2] );
00706             } else {
00707                 // bobbing rotate, with skinNum being the rotation offset
00708                 d = sin( tr.refdef.time * 0.003f );
00709                 d = e->e.skinNum + d * 4;
00710                 VectorCopy( camera->axis[1], transformed );
00711                 RotatePointAroundVector( camera->axis[1], camera->axis[0], transformed, d );
00712                 CrossProduct( camera->axis[0], camera->axis[1], camera->axis[2] );
00713             }
00714         }
00715         else if ( e->e.skinNum ) {
00716             d = e->e.skinNum;
00717             VectorCopy( camera->axis[1], transformed );
00718             RotatePointAroundVector( camera->axis[1], camera->axis[0], transformed, d );
00719             CrossProduct( camera->axis[0], camera->axis[1], camera->axis[2] );
00720         }
00721         *mirror = qfalse;
00722         return qtrue;
00723     }
00724 
00725     // if we didn't locate a portal entity, don't render anything.
00726     // We don't want to just treat it as a mirror, because without a
00727     // portal entity the server won't have communicated a proper entity set
00728     // in the snapshot
00729 
00730     // unfortunately, with local movement prediction it is easily possible
00731     // to see a surface before the server has communicated the matching
00732     // portal surface entity, so we don't want to print anything here...
00733 
00734     //ri.Printf( PRINT_ALL, "Portal surface without a portal entity\n" );
00735 
00736     return qfalse;
00737 }
00738 
00739 static qboolean IsMirror( const drawSurf_t *drawSurf, int entityNum )
00740 {
00741     int         i;
00742     cplane_t    originalPlane, plane;
00743     trRefEntity_t   *e;
00744     float       d;
00745 
00746     // create plane axis for the portal we are seeing
00747     R_PlaneForSurface( drawSurf->surface, &originalPlane );
00748 
00749     // rotate the plane if necessary
00750     if ( entityNum != ENTITYNUM_WORLD ) 
00751     {
00752         tr.currentEntityNum = entityNum;
00753         tr.currentEntity = &tr.refdef.entities[entityNum];
00754 
00755         // get the orientation of the entity
00756         R_RotateForEntity( tr.currentEntity, &tr.viewParms, &tr.or );
00757 
00758         // rotate the plane, but keep the non-rotated version for matching
00759         // against the portalSurface entities
00760         R_LocalNormalToWorld( originalPlane.normal, plane.normal );
00761         plane.dist = originalPlane.dist + DotProduct( plane.normal, tr.or.origin );
00762 
00763         // translate the original plane
00764         originalPlane.dist = originalPlane.dist + DotProduct( originalPlane.normal, tr.or.origin );
00765     } 
00766     else 
00767     {
00768         plane = originalPlane;
00769     }
00770 
00771     // locate the portal entity closest to this plane.
00772     // origin will be the origin of the portal, origin2 will be
00773     // the origin of the camera
00774     for ( i = 0 ; i < tr.refdef.num_entities ; i++ ) 
00775     {
00776         e = &tr.refdef.entities[i];
00777         if ( e->e.reType != RT_PORTALSURFACE ) {
00778             continue;
00779         }
00780 
00781         d = DotProduct( e->e.origin, originalPlane.normal ) - originalPlane.dist;
00782         if ( d > 64 || d < -64) {
00783             continue;
00784         }
00785 
00786         // if the entity is just a mirror, don't use as a camera point
00787         if ( e->e.oldorigin[0] == e->e.origin[0] && 
00788             e->e.oldorigin[1] == e->e.origin[1] && 
00789             e->e.oldorigin[2] == e->e.origin[2] ) 
00790         {
00791             return qtrue;
00792         }
00793 
00794         return qfalse;
00795     }
00796     return qfalse;
00797 }
00798 
00799 /*
00800 ** SurfIsOffscreen
00801 **
00802 ** Determines if a surface is completely offscreen.
00803 */
00804 static qboolean SurfIsOffscreen( const drawSurf_t *drawSurf, vec4_t clipDest[128] ) {
00805     float shortest = 100000000;
00806     int entityNum;
00807     int numTriangles;
00808     shader_t *shader;
00809     int     fogNum;
00810     int dlighted;
00811     vec4_t clip, eye;
00812     int i;
00813     unsigned int pointOr = 0;
00814     unsigned int pointAnd = (unsigned int)~0;
00815 
00816     if ( glConfig.smpActive ) {     // FIXME!  we can't do RB_BeginSurface/RB_EndSurface stuff with smp!
00817         return qfalse;
00818     }
00819 
00820     R_RotateForViewer();
00821 
00822     R_DecomposeSort( drawSurf->sort, &entityNum, &shader, &fogNum, &dlighted );
00823     RB_BeginSurface( shader, fogNum );
00824     rb_surfaceTable[ *drawSurf->surface ]( drawSurf->surface );
00825 
00826     assert( tess.numVertexes < 128 );
00827 
00828     for ( i = 0; i < tess.numVertexes; i++ )
00829     {
00830         int j;
00831         unsigned int pointFlags = 0;
00832 
00833         R_TransformModelToClip( tess.xyz[i], tr.or.modelMatrix, tr.viewParms.projectionMatrix, eye, clip );
00834 
00835         for ( j = 0; j < 3; j++ )
00836         {
00837             if ( clip[j] >= clip[3] )
00838             {
00839                 pointFlags |= (1 << (j*2));
00840             }
00841             else if ( clip[j] <= -clip[3] )
00842             {
00843                 pointFlags |= ( 1 << (j*2+1));
00844             }
00845         }
00846         pointAnd &= pointFlags;
00847         pointOr |= pointFlags;
00848     }
00849 
00850     // trivially reject
00851     if ( pointAnd )
00852     {
00853         return qtrue;
00854     }
00855 
00856     // determine if this surface is backfaced and also determine the distance
00857     // to the nearest vertex so we can cull based on portal range.  Culling
00858     // based on vertex distance isn't 100% correct (we should be checking for
00859     // range to the surface), but it's good enough for the types of portals
00860     // we have in the game right now.
00861     numTriangles = tess.numIndexes / 3;
00862 
00863     for ( i = 0; i < tess.numIndexes; i += 3 )
00864     {
00865         vec3_t normal;
00866         float dot;
00867         float len;
00868 
00869         VectorSubtract( tess.xyz[tess.indexes[i]], tr.viewParms.or.origin, normal );
00870 
00871         len = VectorLengthSquared( normal );            // lose the sqrt
00872         if ( len < shortest )
00873         {
00874             shortest = len;
00875         }
00876 
00877         if ( ( dot = DotProduct( normal, tess.normal[tess.indexes[i]] ) ) >= 0 )
00878         {
00879             numTriangles--;
00880         }
00881     }
00882     if ( !numTriangles )
00883     {
00884         return qtrue;
00885     }
00886 
00887     // mirrors can early out at this point, since we don't do a fade over distance
00888     // with them (although we could)
00889     if ( IsMirror( drawSurf, entityNum ) )
00890     {
00891         return qfalse;
00892     }
00893 
00894     if ( shortest > (tess.shader->portalRange*tess.shader->portalRange) )
00895     {
00896         return qtrue;
00897     }
00898 
00899     return qfalse;
00900 }
00901 
00902 /*
00903 ========================
00904 R_MirrorViewBySurface
00905 
00906 Returns qtrue if another view has been rendered
00907 ========================
00908 */
00909 qboolean R_MirrorViewBySurface (drawSurf_t *drawSurf, int entityNum) {
00910     vec4_t          clipDest[128];
00911     viewParms_t     newParms;
00912     viewParms_t     oldParms;
00913     orientation_t   surface, camera;
00914 
00915     // don't recursively mirror
00916     if (tr.viewParms.isPortal) {
00917         ri.Printf( PRINT_DEVELOPER, "WARNING: recursive mirror/portal found\n" );
00918         return qfalse;
00919     }
00920 
00921     if ( r_noportals->integer || (r_fastsky->integer == 1) ) {
00922         return qfalse;
00923     }
00924 
00925     // trivially reject portal/mirror
00926     if ( SurfIsOffscreen( drawSurf, clipDest ) ) {
00927         return qfalse;
00928     }
00929 
00930     // save old viewParms so we can return to it after the mirror view
00931     oldParms = tr.viewParms;
00932 
00933     newParms = tr.viewParms;
00934     newParms.isPortal = qtrue;
00935     if ( !R_GetPortalOrientations( drawSurf, entityNum, &surface, &camera, 
00936         newParms.pvsOrigin, &newParms.isMirror ) ) {
00937         return qfalse;      // bad portal, no portalentity
00938     }
00939 
00940     R_MirrorPoint (oldParms.or.origin, &surface, &camera, newParms.or.origin );
00941 
00942     VectorSubtract( vec3_origin, camera.axis[0], newParms.portalPlane.normal );
00943     newParms.portalPlane.dist = DotProduct( camera.origin, newParms.portalPlane.normal );
00944     
00945     R_MirrorVector (oldParms.or.axis[0], &surface, &camera, newParms.or.axis[0]);
00946     R_MirrorVector (oldParms.or.axis[1], &surface, &camera, newParms.or.axis[1]);
00947     R_MirrorVector (oldParms.or.axis[2], &surface, &camera, newParms.or.axis[2]);
00948 
00949     // OPTIMIZE: restrict the viewport on the mirrored view
00950 
00951     // render the mirror view
00952     R_RenderView (&newParms);
00953 
00954     tr.viewParms = oldParms;
00955 
00956     return qtrue;
00957 }
00958 
00959 /*
00960 =================
00961 R_SpriteFogNum
00962 
00963 See if a sprite is inside a fog volume
00964 =================
00965 */
00966 int R_SpriteFogNum( trRefEntity_t *ent ) {
00967     int             i, j;
00968     fog_t           *fog;
00969 
00970     if ( tr.refdef.rdflags & RDF_NOWORLDMODEL ) {
00971         return 0;
00972     }
00973 
00974     for ( i = 1 ; i < tr.world->numfogs ; i++ ) {
00975         fog = &tr.world->fogs[i];
00976         for ( j = 0 ; j < 3 ; j++ ) {
00977             if ( ent->e.origin[j] - ent->e.radius >= fog->bounds[1][j] ) {
00978                 break;
00979             }
00980             if ( ent->e.origin[j] + ent->e.radius <= fog->bounds[0][j] ) {
00981                 break;
00982             }
00983         }
00984         if ( j == 3 ) {
00985             return i;
00986         }
00987     }
00988 
00989     return 0;
00990 }
00991 
00992 /*
00993 ==========================================================================================
00994 
00995 DRAWSURF SORTING
00996 
00997 ==========================================================================================
00998 */
00999 
01000 /*
01001 =================
01002 qsort replacement
01003 
01004 =================
01005 */
01006 #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;
01007 
01008 /* this parameter defines the cutoff between using quick sort and
01009    insertion sort for arrays; arrays with lengths shorter or equal to the
01010    below value use insertion sort */
01011 
01012 #define CUTOFF 8            /* testing shows that this is good value */
01013 
01014 static void shortsort( drawSurf_t *lo, drawSurf_t *hi ) {
01015     drawSurf_t  *p, *max;
01016     int         temp;
01017 
01018     while (hi > lo) {
01019         max = lo;
01020         for (p = lo + 1; p <= hi; p++ ) {
01021             if ( p->sort > max->sort ) {
01022                 max = p;
01023             }
01024         }
01025         SWAP_DRAW_SURF(max, hi);
01026         hi--;
01027     }
01028 }
01029 
01030 
01031 /* sort the array between lo and hi (inclusive)
01032 FIXME: this was lifted and modified from the microsoft lib source...
01033  */
01034 
01035 void qsortFast (
01036     void *base,
01037     unsigned num,
01038     unsigned width
01039     )
01040 {
01041     char *lo, *hi;              /* ends of sub-array currently sorting */
01042     char *mid;                  /* points to middle of subarray */
01043     char *loguy, *higuy;        /* traveling pointers for partition step */
01044     unsigned size;              /* size of the sub-array */
01045     char *lostk[30], *histk[30];
01046     int stkptr;                 /* stack for saving sub-array to be processed */
01047     int temp;
01048 
01049     if ( sizeof(drawSurf_t) != 8 ) {
01050         ri.Error( ERR_DROP, "change SWAP_DRAW_SURF macro" );
01051     }
01052 
01053     /* Note: the number of stack entries required is no more than
01054        1 + log2(size), so 30 is sufficient for any array */
01055 
01056     if (num < 2 || width == 0)
01057         return;                 /* nothing to do */
01058 
01059     stkptr = 0;                 /* initialize stack */
01060 
01061     lo = base;
01062     hi = (char *)base + width * (num-1);        /* initialize limits */
01063 
01064     /* this entry point is for pseudo-recursion calling: setting
01065        lo and hi and jumping to here is like recursion, but stkptr is
01066        prserved, locals aren't, so we preserve stuff on the stack */
01067 recurse:
01068 
01069     size = (hi - lo) / width + 1;        /* number of el's to sort */
01070 
01071     /* below a certain size, it is faster to use a O(n^2) sorting method */
01072     if (size <= CUTOFF) {
01073          shortsort((drawSurf_t *)lo, (drawSurf_t *)hi);
01074     }
01075     else {
01076         /* First we pick a partititioning element.  The efficiency of the
01077            algorithm demands that we find one that is approximately the
01078            median of the values, but also that we select one fast.  Using
01079            the first one produces bad performace if the array is already
01080            sorted, so we use the middle one, which would require a very
01081            wierdly arranged array for worst case performance.  Testing shows
01082            that a median-of-three algorithm does not, in general, increase
01083            performance. */
01084 
01085         mid = lo + (size / 2) * width;      /* find middle element */
01086         SWAP_DRAW_SURF(mid, lo);               /* swap it to beginning of array */
01087 
01088         /* We now wish to partition the array into three pieces, one
01089            consisiting of elements <= partition element, one of elements
01090            equal to the parition element, and one of element >= to it.  This
01091            is done below; comments indicate conditions established at every
01092            step. */
01093 
01094         loguy = lo;
01095         higuy = hi + width;
01096 
01097         /* Note that higuy decreases and loguy increases on every iteration,
01098            so loop must terminate. */
01099         for (;;) {
01100             /* lo <= loguy < hi, lo < higuy <= hi + 1,
01101                A[i] <= A[lo] for lo <= i <= loguy,
01102                A[i] >= A[lo] for higuy <= i <= hi */
01103 
01104             do  {
01105                 loguy += width;
01106             } while (loguy <= hi &&  
01107                 ( ((drawSurf_t *)loguy)->sort <= ((drawSurf_t *)lo)->sort ) );
01108 
01109             /* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
01110                either loguy > hi or A[loguy] > A[lo] */
01111 
01112             do  {
01113                 higuy -= width;
01114             } while (higuy > lo && 
01115                 ( ((drawSurf_t *)higuy)->sort >= ((drawSurf_t *)lo)->sort ) );
01116 
01117             /* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
01118                either higuy <= lo or A[higuy] < A[lo] */
01119 
01120             if (higuy < loguy)
01121                 break;
01122 
01123             /* if loguy > hi or higuy <= lo, then we would have exited, so
01124                A[loguy] > A[lo], A[higuy] < A[lo],
01125                loguy < hi, highy > lo */
01126 
01127             SWAP_DRAW_SURF(loguy, higuy);
01128 
01129             /* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
01130                of loop is re-established */
01131         }
01132 
01133         /*     A[i] >= A[lo] for higuy < i <= hi,
01134                A[i] <= A[lo] for lo <= i < loguy,
01135                higuy < loguy, lo <= higuy <= hi
01136            implying:
01137                A[i] >= A[lo] for loguy <= i <= hi,
01138                A[i] <= A[lo] for lo <= i <= higuy,
01139                A[i] = A[lo] for higuy < i < loguy */
01140 
01141         SWAP_DRAW_SURF(lo, higuy);     /* put partition element in place */
01142 
01143         /* OK, now we have the following:
01144               A[i] >= A[higuy] for loguy <= i <= hi,
01145               A[i] <= A[higuy] for lo <= i < higuy
01146               A[i] = A[lo] for higuy <= i < loguy    */
01147 
01148         /* We've finished the partition, now we want to sort the subarrays
01149            [lo, higuy-1] and [loguy, hi].
01150            We do the smaller one first to minimize stack usage.
01151            We only sort arrays of length 2 or more.*/
01152 
01153         if ( higuy - 1 - lo >= hi - loguy ) {
01154             if (lo + width < higuy) {
01155                 lostk[stkptr] = lo;
01156                 histk[stkptr] = higuy - width;
01157                 ++stkptr;
01158             }                           /* save big recursion for later */
01159 
01160             if (loguy < hi) {
01161                 lo = loguy;
01162                 goto recurse;           /* do small recursion */
01163             }
01164         }
01165         else {
01166             if (loguy < hi) {
01167                 lostk[stkptr] = loguy;
01168                 histk[stkptr] = hi;
01169                 ++stkptr;               /* save big recursion for later */
01170             }
01171 
01172             if (lo + width < higuy) {
01173                 hi = higuy - width;
01174                 goto recurse;           /* do small recursion */
01175             }
01176         }
01177     }
01178 
01179     /* We have sorted the array, except for any pending sorts on the stack.
01180        Check if there are any, and do them. */
01181 
01182     --stkptr;
01183     if (stkptr >= 0) {
01184         lo = lostk[stkptr];
01185         hi = histk[stkptr];
01186         goto recurse;           /* pop subarray from stack */
01187     }
01188     else
01189         return;                 /* all subarrays done */
01190 }
01191 
01192 
01193 //==========================================================================================
01194 
01195 /*
01196 =================
01197 R_AddDrawSurf
0119