neo/renderer/tr_trace.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "tr_local.h"
  33
  34 //#define TEST_TRACE
  35
  36 /*
  37 =================
  38 R_LocalTrace
  39
  40 If we resort the vertexes so all silverts come first, we can save some work here.
  41 =================
  42 */
  43 localTrace_t R_LocalTrace( const idVec3 &start, const idVec3 &end, const float radius, const srfTriangles_t *tri ) {
  44         int                     i, j;
  45         byte *          cullBits;
  46         idPlane         planes[4];
  47         localTrace_t    hit;
  48         int                     c_testEdges, c_testPlanes, c_intersect;
  49         idVec3          startDir;
  50         byte            totalOr;
  51         float           radiusSqr;
  52
  53 #ifdef TEST_TRACE
  54         idTimer         trace_timer;
  55         trace_timer.Start();
  56 #endif
  57
  58         hit.fraction = 1.0f;
  59
  60         // create two planes orthogonal to each other that intersect along the trace
  61         startDir = end - start;
  62         startDir.Normalize();
  63         startDir.NormalVectors( planes[0].Normal(), planes[1].Normal() );
  64         planes[0][3] = - start * planes[0].Normal();
  65         planes[1][3] = - start * planes[1].Normal();
  66
  67         // create front and end planes so the trace is on the positive sides of both
  68         planes[2] = startDir;
  69         planes[2][3] = - start * planes[2].Normal();
  70         planes[3] = -startDir;
  71         planes[3][3] = - end * planes[3].Normal();
  72
  73         // catagorize each point against the four planes
  74         cullBits = (byte *) _alloca16( tri->numVerts );
  75         SIMDProcessor->TracePointCull( cullBits, totalOr, radius, planes, tri->verts, tri->numVerts );
  76
  77         // if we don't have points on both sides of both the ray planes, no intersection
  78         if ( ( totalOr ^ ( totalOr >> 4 ) ) & 3 ) {
  79                 //common->Printf( "nothing crossed the trace planes\n" );
  80                 return hit;
  81         }
  82
  83         // if we don't have any points between front and end, no intersection
  84         if ( ( totalOr ^ ( totalOr >> 1 ) ) & 4 ) {
  85                 //common->Printf( "trace didn't reach any triangles\n" );
  86                 return hit;
  87         }
  88
  89         // scan for triangles that cross both planes
  90         c_testPlanes = 0;
  91         c_testEdges = 0;
  92         c_intersect = 0;
  93
  94         radiusSqr = Square( radius );
  95         startDir = end - start;
  96
  97         if ( !tri->facePlanes || !tri->facePlanesCalculated ) {
  98                 R_DeriveFacePlanes( const_cast<srfTriangles_t *>( tri ) );
  99         }
 100
 101         for ( i = 0, j = 0; i < tri->numIndexes; i += 3, j++ ) {
 102                 float           d1, d2, f, d;
 103                 float           edgeLengthSqr;
 104                 idPlane *       plane;
 105                 idVec3          point;
 106                 idVec3          dir[3];
 107                 idVec3          cross;
 108                 idVec3          edge;
 109                 byte            triOr;
 110
 111                 // get sidedness info for the triangle
 112                 triOr  = cullBits[ tri->indexes[i+0] ];
 113                 triOr |= cullBits[ tri->indexes[i+1] ];
 114                 triOr |= cullBits[ tri->indexes[i+2] ];
 115
 116                 // if we don't have points on both sides of both the ray planes, no intersection
 117                 if ( ( triOr ^ ( triOr >> 4 ) ) & 3 ) {
 118                         continue;
 119                 }
 120
 121                 // if we don't have any points between front and end, no intersection
 122                 if ( ( triOr ^ ( triOr >> 1 ) ) & 4 ) {
 123                         continue;
 124                 }
 125
 126                 c_testPlanes++;
 127
 128                 plane = &tri->facePlanes[j];
 129                 d1 = plane->Distance( start );
 130                 d2 = plane->Distance( end );
 131
 132                 if ( d1 <= d2 ) {
 133                         continue;               // comning at it from behind or parallel
 134                 }
 135
 136                 if ( d1 < 0.0f ) {
 137                         continue;               // starts past it
 138                 }
 139
 140                 if ( d2 > 0.0f ) {
 141                         continue;               // finishes in front of it
 142                 }
 143
 144                 f = d1 / ( d1 - d2 );
 145
 146                 if ( f < 0.0f ) {
 147                         continue;               // shouldn't happen
 148                 }
 149
 150                 if ( f >= hit.fraction ) {
 151                         continue;               // have already hit something closer
 152                 }
 153
 154                 c_testEdges++;
 155
 156                 // find the exact point of impact with the plane
 157                 point = start + f * startDir;
 158
 159                 // see if the point is within the three edges
 160                 // if radius > 0 the triangle is expanded with a circle in the triangle plane
 161
 162                 dir[0] = tri->verts[ tri->indexes[i+0] ].xyz - point;
 163                 dir[1] = tri->verts[ tri->indexes[i+1] ].xyz - point;
 164
 165                 cross = dir[0].Cross( dir[1] );
 166                 d = plane->Normal() * cross;
 167                 if ( d > 0.0f ) {
 168                         if ( radiusSqr <= 0.0f ) {
 169                                 continue;
 170                         }
 171                         edge = tri->verts[ tri->indexes[i+0] ].xyz - tri->verts[ tri->indexes[i+1] ].xyz;
 172                         edgeLengthSqr = edge.LengthSqr();
 173                         if ( cross.LengthSqr() > edgeLengthSqr * radiusSqr ) {
 174                                 continue;
 175                         }
 176                         d = edge * dir[0];
 177                         if ( d < 0.0f ) {
 178                                 edge = tri->verts[ tri->indexes[i+0] ].xyz - tri->verts[ tri->indexes[i+2] ].xyz;
 179                                 d = edge * dir[0];
 180                                 if ( d < 0.0f ) {
 181                                         if ( dir[0].LengthSqr() > radiusSqr ) {
 182                                                 continue;
 183                                         }
 184                                 }
 185                         } else if ( d > edgeLengthSqr ) {
 186                                 edge = tri->verts[ tri->indexes[i+1] ].xyz - tri->verts[ tri->indexes[i+2] ].xyz;
 187                                 d = edge * dir[1];
 188                                 if ( d < 0.0f ) {
 189                                         if ( dir[1].LengthSqr() > radiusSqr ) {
 190                                                 continue;
 191                                         }
 192                                 }
 193                         }
 194                 }
 195
 196                 dir[2] = tri->verts[ tri->indexes[i+2] ].xyz - point;
 197
 198                 cross = dir[1].Cross( dir[2] );
 199                 d = plane->Normal() * cross;
 200                 if ( d > 0.0f ) {
 201                         if ( radiusSqr <= 0.0f ) {
 202                                 continue;
 203                         }
 204                         edge = tri->verts[ tri->indexes[i+1] ].xyz - tri->verts[ tri->indexes[i+2] ].xyz;
 205                         edgeLengthSqr = edge.LengthSqr();
 206                         if ( cross.LengthSqr() > edgeLengthSqr * radiusSqr ) {
 207                                 continue;
 208                         }
 209                         d = edge * dir[1];
 210                         if ( d < 0.0f ) {
 211                                 edge = tri->verts[ tri->indexes[i+1] ].xyz - tri->verts[ tri->indexes[i+0] ].xyz;
 212                                 d = edge * dir[1];
 213                                 if ( d < 0.0f ) {
 214                                         if ( dir[1].LengthSqr() > radiusSqr ) {
 215                                                 continue;
 216                                         }
 217                                 }
 218                         } else if ( d > edgeLengthSqr ) {
 219                                 edge = tri->verts[ tri->indexes[i+2] ].xyz - tri->verts[ tri->indexes[i+0] ].xyz;
 220                                 d = edge * dir[2];
 221                                 if ( d < 0.0f ) {
 222                                         if ( dir[2].LengthSqr() > radiusSqr ) {
 223                                                 continue;
 224                                         }
 225                                 }
 226                         }
 227                 }
 228
 229                 cross = dir[2].Cross( dir[0] );
 230                 d = plane->Normal() * cross;
 231                 if ( d > 0.0f ) {
 232                         if ( radiusSqr <= 0.0f ) {
 233                                 continue;
 234                         }
 235                         edge = tri->verts[ tri->indexes[i+2] ].xyz - tri->verts[ tri->indexes[i+0] ].xyz;
 236                         edgeLengthSqr = edge.LengthSqr();
 237                         if ( cross.LengthSqr() > edgeLengthSqr * radiusSqr ) {
 238                                 continue;
 239                         }
 240                         d = edge * dir[2];
 241                         if ( d < 0.0f ) {
 242                                 edge = tri->verts[ tri->indexes[i+2] ].xyz - tri->verts[ tri->indexes[i+1] ].xyz;
 243                                 d = edge * dir[2];
 244                                 if ( d < 0.0f ) {
 245                                         if ( dir[2].LengthSqr() > radiusSqr ) {
 246                                                 continue;
 247                                         }
 248                                 }
 249                         } else if ( d > edgeLengthSqr ) {
 250                                 edge = tri->verts[ tri->indexes[i+0] ].xyz - tri->verts[ tri->indexes[i+1] ].xyz;
 251                                 d = edge * dir[0];
 252                                 if ( d < 0.0f ) {
 253                                         if ( dir[0].LengthSqr() > radiusSqr ) {
 254                                                 continue;
 255                                         }
 256                                 }
 257                         }
 258                 }
 259
 260                 // we hit it
 261                 c_intersect++;
 262
 263                 hit.fraction = f;
 264                 hit.normal = plane->Normal();
 265                 hit.point = point;
 266                 hit.indexes[0] = tri->indexes[i];
 267                 hit.indexes[1] = tri->indexes[i+1];
 268                 hit.indexes[2] = tri->indexes[i+2];
 269         }
 270
 271
 272 #ifdef TEST_TRACE
 273         trace_timer.Stop();
 274         common->Printf( "testVerts:%i c_testPlanes:%i c_testEdges:%i c_intersect:%i msec:%1.4f\n",
 275                                         tri->numVerts, c_testPlanes, c_testEdges, c_intersect, trace_timer.Milliseconds() );
 276 #endif
 277
 278         return hit;
 279 }
 280
 281 /*
 282 =================
 283 RB_DrawExpandedTriangles
 284 =================
 285 */
 286 void RB_DrawExpandedTriangles( const srfTriangles_t *tri, const float radius, const idVec3 &vieworg ) {
 287         int i, j, k;
 288         idVec3 dir[6], normal, point;
 289
 290         for ( i = 0; i < tri->numIndexes; i += 3 ) {
 291
 292                 idVec3 p[3] = { tri->verts[ tri->indexes[ i + 0 ] ].xyz, tri->verts[ tri->indexes[ i + 1 ] ].xyz, tri->verts[ tri->indexes[ i + 2 ] ].xyz };
 293
 294                 dir[0] = p[0] - p[1];
 295                 dir[1] = p[1] - p[2];
 296                 dir[2] = p[2] - p[0];
 297
 298                 normal = dir[0].Cross( dir[1] );
 299
 300                 if ( normal * p[0] < normal * vieworg ) {
 301                         continue;
 302                 }
 303
 304                 dir[0] = normal.Cross( dir[0] );
 305                 dir[1] = normal.Cross( dir[1] );
 306                 dir[2] = normal.Cross( dir[2] );
 307
 308                 dir[0].Normalize();
 309                 dir[1].Normalize();
 310                 dir[2].Normalize();
 311
 312                 qglBegin( GL_LINE_LOOP );
 313
 314                 for ( j = 0; j < 3; j++ ) {
 315                         k = ( j + 1 ) % 3;
 316
 317                         dir[4] = ( dir[j] + dir[k] ) * 0.5f;
 318                         dir[4].Normalize();
 319
 320                         dir[3] = ( dir[j] + dir[4] ) * 0.5f;
 321                         dir[3].Normalize();
 322
 323                         dir[5] = ( dir[4] + dir[k] ) * 0.5f;
 324                         dir[5].Normalize();
 325
 326                         point = p[k] + dir[j] * radius;
 327                         qglVertex3f( point[0], point[1], point[2] );
 328
 329                         point = p[k] + dir[3] * radius;
 330                         qglVertex3f( point[0], point[1], point[2] );
 331
 332                         point = p[k] + dir[4] * radius;
 333                         qglVertex3f( point[0], point[1], point[2] );
 334
 335                         point = p[k] + dir[5] * radius;
 336                         qglVertex3f( point[0], point[1], point[2] );
 337
 338                         point = p[k] + dir[k] * radius;
 339                         qglVertex3f( point[0], point[1], point[2] );
 340                 }
 341
 342                 qglEnd();
 343         }
 344 }
 345
 346 /*
 347 ================
 348 RB_ShowTrace
 349
 350 Debug visualization
 351 ================
 352 */
 353 void RB_ShowTrace( drawSurf_t **drawSurfs, int numDrawSurfs ) {
 354         int                                             i;
 355         const srfTriangles_t    *tri;
 356         const drawSurf_t                *surf;
 357         idVec3                                  start, end;
 358         idVec3                                  localStart, localEnd;
 359         localTrace_t                    hit;
 360         float                                   radius;
 361
 362         if ( r_showTrace.GetInteger() == 0 ) {
 363                 return;
 364         }
 365
 366         if ( r_showTrace.GetInteger() == 2 ) {
 367                 radius = 5.0f;
 368         } else {
 369                 radius = 0.0f;
 370         }
 371
 372         // determine the points of the trace
 373         start = backEnd.viewDef->renderView.vieworg;
 374         end = start + 4000 * backEnd.viewDef->renderView.viewaxis[0];
 375
 376         // check and draw the surfaces
 377         qglDisableClientState( GL_TEXTURE_COORD_ARRAY );
 378         GL_TexEnv( GL_MODULATE );
 379
 380         globalImages->whiteImage->Bind();
 381
 382         // find how many are ambient
 383         for ( i = 0 ; i < numDrawSurfs ; i++ ) {
 384                 surf = drawSurfs[i];
 385                 tri = surf->geo;
 386
 387                 if ( tri == NULL || tri->verts == NULL ) {
 388                         continue;
 389                 }
 390
 391                 // transform the points into local space
 392                 R_GlobalPointToLocal( surf->space->modelMatrix, start, localStart );
 393                 R_GlobalPointToLocal( surf->space->modelMatrix, end, localEnd );
 394
 395                 // check the bounding box
 396                 if ( !tri->bounds.Expand( radius ).LineIntersection( localStart, localEnd ) ) {
 397                         continue;
 398                 }
 399
 400                 qglLoadMatrixf( surf->space->modelViewMatrix );
 401
 402                 // highlight the surface
 403                 GL_State( GLS_SRCBLEND_SRC_ALPHA | GLS_DSTBLEND_ONE_MINUS_SRC_ALPHA );
 404
 405                 qglColor4f( 1, 0, 0, 0.25 );
 406                 RB_DrawElementsImmediate( tri );
 407
 408                 // draw the bounding box
 409                 GL_State( GLS_DEPTHFUNC_ALWAYS );
 410
 411                 qglColor4f( 1, 1, 1, 1 );
 412                 RB_DrawBounds( tri->bounds );
 413
 414                 if ( radius != 0.0f ) {
 415                         // draw the expanded triangles
 416                         qglColor4f( 0.5f, 0.5f, 1.0f, 1.0f );
 417                         RB_DrawExpandedTriangles( tri, radius, localStart );
 418                 }
 419
 420                 // check the exact surfaces
 421                 hit = R_LocalTrace( localStart, localEnd, radius, tri );
 422                 if ( hit.fraction < 1.0 ) {
 423                         qglColor4f( 1, 1, 1, 1 );
 424                         RB_DrawBounds( idBounds( hit.point ).Expand( 1 ) );
 425                 }
 426         }
 427 }