tools/quake3/q3map2/patch.c

   1 /*\r
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.\r
   4 \r
   5 This file is part of GtkRadiant.\r
   6 \r
   7 GtkRadiant is free software; you can redistribute it and/or modify\r
   8 it under the terms of the GNU General Public License as published by\r
   9 the Free Software Foundation; either version 2 of the License, or\r
  10 (at your option) any later version.\r
  11 \r
  12 GtkRadiant is distributed in the hope that it will be useful,\r
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15 GNU General Public License for more details.\r
  16 \r
  17 You should have received a copy of the GNU General Public License\r
  18 along with GtkRadiant; if not, write to the Free Software\r
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
  20 \r
  21 ----------------------------------------------------------------------------------\r
  22 \r
  23 This code has been altered significantly from its original form, to support\r
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
  25 \r
  26 ------------------------------------------------------------------------------- */\r
  27 \r
  28 \r
  29 \r
  30 /* marker */\r
  31 #define PATCH_C\r
  32 \r
  33 \r
  34 \r
  35 /* dependencies */\r
  36 #include "q3map2.h"\r
  37 \r
  38 \r
  39 \r
  40 /*\r
  41 ExpandLongestCurve() - ydnar\r
  42 finds length of quadratic curve specified and determines if length is longer than the supplied max\r
  43 */\r
  44 \r
  45 #define APPROX_SUBDIVISION      8\r
  46 \r
  47 static void ExpandLongestCurve( float *longestCurve, vec3_t a, vec3_t b, vec3_t c )\r
  48 {\r
  49         int             i;\r
  50         float   t, len;\r
  51         vec3_t  ab, bc, ac, pt, last, delta;\r
  52         \r
  53         \r
  54         /* calc vectors */\r
  55         VectorSubtract( b, a, ab );\r
  56         if( VectorNormalize( ab, ab ) < 0.125f )\r
  57                 return;\r
  58         VectorSubtract( c, b, bc );\r
  59         if( VectorNormalize( bc, bc ) < 0.125f )\r
  60                 return;\r
  61         VectorSubtract( c, a, ac );\r
  62         if( VectorNormalize( ac, ac ) < 0.125f )\r
  63                 return;\r
  64         \r
  65         /* if all 3 vectors are the same direction, then this edge is linear, so we ignore it */\r
  66         if( DotProduct( ab, bc ) > 0.99f && DotProduct( ab, ac ) > 0.99f )\r
  67                 return;\r
  68         \r
  69         /* recalculate vectors */\r
  70         VectorSubtract( b, a, ab );\r
  71         VectorSubtract( c, b, bc );\r
  72         \r
  73         /* determine length */\r
  74         VectorCopy( a, last );\r
  75         for( i = 0, len = 0.0f, t = 0.0f; i < APPROX_SUBDIVISION; i++, t += (1.0f / APPROX_SUBDIVISION) )\r
  76         {\r
  77                 /* calculate delta */\r
  78                 delta[ 0 ] = ((1.0f - t) * ab[ 0 ]) + (t * bc[ 0 ]);\r
  79                 delta[ 1 ] = ((1.0f - t) * ab[ 1 ]) + (t * bc[ 1 ]);\r
  80                 delta[ 2 ] = ((1.0f - t) * ab[ 2 ]) + (t * bc[ 2 ]);\r
  81                 \r
  82                 /* add to first point and calculate pt-pt delta */\r
  83                 VectorAdd( a, delta, pt );\r
  84                 VectorSubtract( pt, last, delta );\r
  85                 \r
  86                 /* add it to length and store last point */\r
  87                 len += VectorLength( delta );\r
  88                 VectorCopy( pt, last );\r
  89         }\r
  90         \r
  91         /* longer? */\r
  92         if( len > *longestCurve )\r
  93                 *longestCurve = len;\r
  94 }\r
  95 \r
  96 \r
  97 \r
  98 /*\r
  99 ExpandMaxIterations() - ydnar\r
 100 determines how many iterations a quadratic curve needs to be subdivided with to fit the specified error\r
 101 */\r
 102 \r
 103 static void ExpandMaxIterations( int *maxIterations, int maxError, vec3_t a, vec3_t b, vec3_t c )\r
 104 {\r
 105         int                             i, j;\r
 106         vec3_t                  prev, next, mid, delta, delta2;\r
 107         float                   len, len2;\r
 108         int                             numPoints, iterations;\r
 109         vec3_t                  points[ MAX_EXPANDED_AXIS ];\r
 110         \r
 111         \r
 112         /* initial setup */\r
 113         numPoints = 3;\r
 114         VectorCopy( a, points[ 0 ] );\r
 115         VectorCopy( b, points[ 1 ] );\r
 116         VectorCopy( c, points[ 2 ] );\r
 117 \r
 118         /* subdivide */\r
 119         for( i = 0; i + 2 < numPoints; i += 2 )\r
 120         {\r
 121                 /* check subdivision limit */\r
 122                 if( numPoints + 2 >= MAX_EXPANDED_AXIS )\r
 123                         break;\r
 124                 \r
 125                 /* calculate new curve deltas */\r
 126                 for( j = 0; j < 3; j++ )\r
 127                 {\r
 128                         prev[ j ] = points[ i + 1 ][ j ] - points[ i ][ j ]; \r
 129                         next[ j ] = points[ i + 2 ][ j ] - points[ i + 1 ][ j ]; \r
 130                         mid[ j ] = (points[ i ][ j ] + points[ i + 1 ][ j ] * 2.0f + points[ i + 2 ][ j ]) * 0.25f;\r
 131                 }\r
 132                 \r
 133                 /* see if this midpoint is off far enough to subdivide */\r
 134                 VectorSubtract( points[ i + 1 ], mid, delta );\r
 135                 len = VectorLength( delta );\r
 136                 if( len < maxError )\r
 137                         continue;\r
 138                 \r
 139                 /* subdivide */\r
 140                 numPoints += 2;\r
 141                 \r
 142                 /* create new points */\r
 143                 for( j = 0; j < 3; j++ )\r
 144                 {\r
 145                         prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ]);\r
 146                         next[ j ] = 0.5f * (points[ i + 1 ][ j ] + points[ i + 2 ][ j ]);\r
 147                         mid[ j ] = 0.5f * (prev[ j ] + next[ j ]);\r
 148                 }\r
 149                 \r
 150                 /* push points out */\r
 151                 for( j = numPoints - 1; j > i + 3; j-- )\r
 152                         VectorCopy( points[ j - 2 ], points[ j ] );\r
 153                 \r
 154                 /* insert new points */\r
 155                 VectorCopy( prev, points[ i + 1 ] );\r
 156                 VectorCopy( mid, points[ i + 2 ] );\r
 157                 VectorCopy( next, points[ i + 3 ] );\r
 158 \r
 159                 /* back up and recheck this set again, it may need more subdivision */\r
 160                 i -= 2;\r
 161         }\r
 162         \r
 163         /* put the line on the curve */\r
 164         for( i = 1; i < numPoints; i += 2 )\r
 165         {\r
 166                 for( j = 0; j < 3; j++ )\r
 167                 {\r
 168                         prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ] );\r
 169                         next[ j ] = 0.5f * (points[ i ][ j ] + points[ i - 1 ][ j ] );\r
 170                         points[ i ][ j ] = 0.5f * (prev[ j ] + next[ j ]);\r
 171                 }\r
 172         }\r
 173         \r
 174         /* eliminate linear sections */\r
 175         for( i = 0; i + 2 < numPoints; i++ )\r
 176         {\r
 177                 /* create vectors */\r
 178                 VectorSubtract( points[ i + 1 ], points[ i ], delta );\r
 179                 len = VectorNormalize( delta, delta );\r
 180                 VectorSubtract( points[ i + 2 ], points[ i + 1 ], delta2 );\r
 181                 len2 = VectorNormalize( delta2, delta2 );\r
 182                 \r
 183                 /* if either edge is degenerate, then eliminate it */\r
 184                 if( len < 0.0625f || len2 < 0.0625f || DotProduct( delta, delta2 ) >= 1.0f )\r
 185                 {\r
 186                         for( j = i + 1; j + 1 < numPoints; j++ )\r
 187                                 VectorCopy( points[ j + 1 ], points[ j ] );\r
 188                         numPoints--;\r
 189                         continue;\r
 190                 }\r
 191         }\r
 192         \r
 193         /* the number of iterations is 2^(points - 1) - 1 */\r
 194         numPoints >>= 1;\r
 195         iterations = 0;\r
 196         while( numPoints > 1 )\r
 197         {\r
 198                 numPoints >>= 1;\r
 199                 iterations++;\r
 200         }\r
 201         \r
 202         /* more? */\r
 203         if( iterations > *maxIterations )\r
 204                 *maxIterations = iterations;\r
 205 }\r
 206 \r
 207 \r
 208 \r
 209 /*\r
 210 ParsePatch()\r
 211 creates a mapDrawSurface_t from the patch text\r
 212 */\r
 213 \r
 214 void ParsePatch( qboolean onlyLights )\r
 215 {\r
 216         vec_t                   info[ 5 ];\r
 217         int                             i, j, k;\r
 218         parseMesh_t             *pm;\r
 219         char                    texture[ MAX_QPATH ];\r
 220         char                    shader[ MAX_QPATH ];\r
 221         mesh_t                  m;\r
 222         bspDrawVert_t   *verts;\r
 223         epair_t                 *ep;\r
 224         vec4_t                  delta, delta2, delta3;\r
 225         qboolean                degenerate;\r
 226         float                   longestCurve;\r
 227         int                             maxIterations;\r
 228         \r
 229         \r
 230         MatchToken( "{" );\r
 231         \r
 232         /* get texture */\r
 233         GetToken( qtrue );\r
 234         strcpy( texture, token );\r
 235         \r
 236         Parse1DMatrix( 5, info );\r
 237         m.width = info[0];\r
 238         m.height = info[1];\r
 239         m.verts = verts = safe_malloc( m.width * m.height * sizeof( m.verts[0] ) );\r
 240         \r
 241         if( m.width < 0 || m.width > MAX_PATCH_SIZE || m.height < 0 || m.height > MAX_PATCH_SIZE )\r
 242                 Error( "ParsePatch: bad size" );\r
 243         \r
 244         MatchToken( "(" );\r
 245         for( j = 0; j < m.width ; j++ )\r
 246         {\r
 247                 MatchToken( "(" );\r
 248                 for( i = 0; i < m.height ; i++ )\r
 249                 {\r
 250                         Parse1DMatrix( 5, verts[ i * m.width + j ].xyz );\r
 251                         \r
 252                         /* ydnar: fix colors */\r
 253                         for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
 254                         {\r
 255                                 verts[ i * m.width + j ].color[ k ][ 0 ] = 255;\r
 256                                 verts[ i * m.width + j ].color[ k ][ 1 ] = 255;\r
 257                                 verts[ i * m.width + j ].color[ k ][ 2 ] = 255;\r
 258                                 verts[ i * m.width + j ].color[ k ][ 3 ] = 255;\r
 259                         }\r
 260                 }\r
 261                 MatchToken( ")" );\r
 262         }\r
 263         MatchToken( ")" );\r
 264 \r
 265         // if brush primitives format, we may have some epairs to ignore here\r
 266         GetToken(qtrue);\r
 267         if (g_bBrushPrimit!=BPRIMIT_OLDBRUSHES && strcmp(token,"}"))\r
 268         {\r
 269                 // NOTE: we leak that!\r
 270                 ep = ParseEPair();\r
 271         }\r
 272         else\r
 273                 UnGetToken();\r
 274 \r
 275         MatchToken( "}" );\r
 276         MatchToken( "}" );\r
 277         \r
 278         /* short circuit */\r
 279         if( noCurveBrushes || onlyLights )\r
 280                 return;\r
 281         \r
 282         \r
 283         /* ydnar: delete and warn about degenerate patches */\r
 284         j = (m.width * m.height);\r
 285         VectorClear( delta );\r
 286         delta[ 3 ] = 0;\r
 287         degenerate = qtrue;\r
 288         \r
 289         /* find first valid vector */\r
 290         for( i = 1; i < j && delta[ 3 ] == 0; i++ )\r
 291         {\r
 292                 VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta );\r
 293                 delta[ 3 ] = VectorNormalize( delta, delta );\r
 294         }\r
 295         \r
 296         /* secondary degenerate test */\r
 297         if( delta[ 3 ] == 0 )\r
 298                 degenerate = qtrue;\r
 299         else\r
 300         {\r
 301                 /* if all vectors match this or are zero, then this is a degenerate patch */\r
 302                 for( i = 1; i < j && degenerate == qtrue; i++ )\r
 303                 {\r
 304                         VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta2 );\r
 305                         delta2[ 3 ] = VectorNormalize( delta2, delta2 );\r
 306                         if( delta2[ 3 ] != 0 )\r
 307                         {\r
 308                                 /* create inverse vector */\r
 309                                 VectorCopy( delta2, delta3 );\r
 310                                 delta3[ 3 ] = delta2[ 3 ];\r
 311                                 VectorInverse( delta3 );\r
 312                                 \r
 313                                 /* compare */\r
 314                                 if( VectorCompare( delta, delta2 ) == qfalse && VectorCompare( delta, delta3 ) == qfalse )\r
 315                                         degenerate = qfalse;\r
 316                         }\r
 317                 }\r
 318         }\r
 319         \r
 320         /* warn and select degenerate patch */\r
 321         if( degenerate )\r
 322         {\r
 323                 xml_Select( "degenerate patch", mapEnt->mapEntityNum, entitySourceBrushes, qfalse );\r
 324                 free( m.verts );\r
 325                 return;\r
 326         }\r
 327         \r
 328         /* find longest curve on the mesh */\r
 329         longestCurve = 0.0f;\r
 330         maxIterations = 0;\r
 331         for( j = 0; j + 2 < m.width; j += 2 )\r
 332         {\r
 333                 for( i = 0; i + 2 < m.height; i += 2 )\r
 334                 {\r
 335                         ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ i * m.width + (j + 1) ].xyz, verts[ i * m.width + (j + 2) ].xyz );              /* row */\r
 336                         ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ (i + 1) * m.width + j ].xyz, verts[ (i + 2) * m.width + j ].xyz );              /* col */\r
 337                         ExpandMaxIterations( &maxIterations, patchSubdivisions, verts[ i * m.width + j ].xyz, verts[ i * m.width + (j + 1) ].xyz, verts[ i * m.width + (j + 2) ].xyz );         /* row */\r
 338                         ExpandMaxIterations( &maxIterations, patchSubdivisions, verts[ i * m.width + j ].xyz, verts[ (i + 1) * m.width + j ].xyz, verts[ (i + 2) * m.width + j ].xyz  );        /* col */\r
 339                 }\r
 340         }\r
 341         \r
 342         /* allocate patch mesh */\r
 343         pm = safe_malloc( sizeof( *pm ) );\r
 344         memset( pm, 0, sizeof( *pm ) );\r
 345         \r
 346         /* ydnar: add entity/brush numbering */\r
 347         pm->entityNum = mapEnt->mapEntityNum;\r
 348         pm->brushNum = entitySourceBrushes;\r
 349         \r
 350         /* set shader */\r
 351         sprintf( shader, "textures/%s", texture );\r
 352         pm->shaderInfo = ShaderInfoForShader( shader );\r
 353         \r
 354         /* set mesh */\r
 355         pm->mesh = m;\r
 356         \r
 357         /* set longest curve */\r
 358         pm->longestCurve = longestCurve;\r
 359         pm->maxIterations = maxIterations;\r
 360         \r
 361         /* link to the entity */\r
 362         pm->next = mapEnt->patches;\r
 363         mapEnt->patches = pm;\r
 364 }\r
 365 \r
 366 \r
 367 \r
 368 /*\r
 369 GrowGroup_r()\r
 370 recursively adds patches to a lod group\r
 371 */\r
 372 \r
 373 static void GrowGroup_r( parseMesh_t *pm, int patchNum, int patchCount, parseMesh_t **meshes, byte *bordering, byte *group )\r
 374 {\r
 375         int                     i;\r
 376         const byte      *row;\r
 377         \r
 378         \r
 379         /* early out check */\r
 380         if( group[ patchNum ] )\r
 381                 return;\r
 382         \r
 383         \r
 384         /* set it */\r
 385         group[ patchNum ] = 1;\r
 386         row = bordering + patchNum * patchCount;\r
 387         \r
 388         /* check maximums */\r
 389         if( meshes[ patchNum ]->longestCurve > pm->longestCurve )\r
 390                 pm->longestCurve = meshes[ patchNum ]->longestCurve;\r
 391         if( meshes[ patchNum ]->maxIterations > pm->maxIterations )\r
 392                 pm->maxIterations = meshes[ patchNum ]->maxIterations;\r
 393         \r
 394         /* walk other patches */\r
 395         for( i = 0; i < patchCount; i++ )\r
 396         {\r
 397                 if( row[ i ] )\r
 398                         GrowGroup_r( pm, i, patchCount, meshes, bordering, group );\r
 399         }\r
 400 }\r
 401 \r
 402 \r
 403 /*\r
 404 PatchMapDrawSurfs()\r
 405 any patches that share an edge need to choose their\r
 406 level of detail as a unit, otherwise the edges would\r
 407 pull apart.\r
 408 */\r
 409 \r
 410 void PatchMapDrawSurfs( entity_t *e )\r
 411 {\r
 412         int                                             i, j, k, l, c1, c2;\r
 413         parseMesh_t                             *pm;\r
 414         parseMesh_t                             *check, *scan;\r
 415         mapDrawSurface_t                *ds;\r
 416         int                                             patchCount, groupCount;\r
 417         bspDrawVert_t                   *v1, *v2;\r
 418         vec3_t                                  bounds[ 2 ];\r
 419         byte                                    *bordering;\r
 420         \r
 421         /* ydnar: mac os x fails with these if not static */\r
 422         MAC_STATIC parseMesh_t  *meshes[ MAX_MAP_DRAW_SURFS ];\r
 423         MAC_STATIC qb_t                 grouped[ MAX_MAP_DRAW_SURFS ];\r
 424         MAC_STATIC byte                 group[ MAX_MAP_DRAW_SURFS ];\r
 425         \r
 426         \r
 427         /* note it */\r
 428         Sys_FPrintf( SYS_VRB, "--- PatchMapDrawSurfs ---\n" );\r
 429 \r
 430         patchCount = 0;\r
 431         for ( pm = e->patches ; pm ; pm = pm->next  ) {\r
 432                 meshes[patchCount] = pm;\r
 433                 patchCount++;\r
 434         }\r
 435 \r
 436         if ( !patchCount ) {\r
 437                 return;\r
 438         }\r
 439         bordering = safe_malloc( patchCount * patchCount );\r
 440         memset( bordering, 0, patchCount * patchCount );\r
 441 \r
 442         // build the bordering matrix\r
 443         for ( k = 0 ; k < patchCount ; k++ ) {\r
 444                 bordering[k*patchCount+k] = 1;\r
 445 \r
 446                 for ( l = k+1 ; l < patchCount ; l++ ) {\r
 447                         check = meshes[k];\r
 448                         scan = meshes[l];\r
 449                         c1 = scan->mesh.width * scan->mesh.height;\r
 450                         v1 = scan->mesh.verts;\r
 451 \r
 452                         for ( i = 0 ; i < c1 ; i++, v1++ ) {\r
 453                                 c2 = check->mesh.width * check->mesh.height;\r
 454                                 v2 = check->mesh.verts;\r
 455                                 for ( j = 0 ; j < c2 ; j++, v2++ ) {\r
 456                                         if ( fabs( v1->xyz[0] - v2->xyz[0] ) < 1.0\r
 457                                                 && fabs( v1->xyz[1] - v2->xyz[1] ) < 1.0\r
 458                                                 && fabs( v1->xyz[2] - v2->xyz[2] ) < 1.0 ) {\r
 459                                                 break;\r
 460                                         }\r
 461                                 }\r
 462                                 if ( j != c2 ) {\r
 463                                         break;\r
 464                                 }\r
 465                         }\r
 466                         if ( i != c1 ) {\r
 467                                 // we have a connection\r
 468                                 bordering[k*patchCount+l] =\r
 469                                 bordering[l*patchCount+k] = 1;\r
 470                         } else {\r
 471                                 // no connection\r
 472                                 bordering[k*patchCount+l] =\r
 473                                 bordering[l*patchCount+k] = 0;\r
 474                         }\r
 475 \r
 476                 }\r
 477         }\r
 478 \r
 479         /* build groups */\r
 480         memset( grouped, 0, patchCount );\r
 481         groupCount = 0;\r
 482         for ( i = 0; i < patchCount; i++ )\r
 483         {\r
 484                 /* get patch */\r
 485                 scan = meshes[ i ];\r
 486                 \r
 487                 /* start a new group */\r
 488                 if( !grouped[ i ] )\r
 489                         groupCount++;\r
 490                 \r
 491                 /* recursively find all patches that belong in the same group */\r
 492                 memset( group, 0, patchCount );\r
 493                 GrowGroup_r( scan, i, patchCount, meshes, bordering, group );\r
 494                 \r
 495                 /* bound them */\r
 496                 ClearBounds( bounds[ 0 ], bounds[ 1 ] );\r
 497                 for( j = 0; j < patchCount; j++ )\r
 498                 {\r
 499                         if ( group[ j ] )\r
 500                         {\r
 501                                 grouped[ j ] = qtrue;\r
 502                                 check = meshes[ j ];\r
 503                                 c1 = check->mesh.width * check->mesh.height;\r
 504                                 v1 = check->mesh.verts;\r
 505                                 for( k = 0; k < c1; k++, v1++ )\r
 506                                         AddPointToBounds( v1->xyz, bounds[ 0 ], bounds[ 1 ] );\r
 507                         }\r
 508                 }\r
 509                 \r
 510                 /* debug code */\r
 511                 //%     Sys_Printf( "Longest curve: %f Iterations: %d\n", scan->longestCurve, scan->maxIterations );\r
 512                 \r
 513                 /* create drawsurf */\r
 514                 scan->grouped = qtrue;\r
 515                 ds = DrawSurfaceForMesh( e, scan, NULL );       /* ydnar */\r
 516                 VectorCopy( bounds[ 0 ], ds->bounds[ 0 ] );\r
 517                 VectorCopy( bounds[ 1 ], ds->bounds[ 1 ] );\r
 518         }\r
 519         \r
 520         /* emit some statistics */\r
 521         Sys_FPrintf( SYS_VRB, "%9d patches\n", patchCount );\r
 522         Sys_FPrintf( SYS_VRB, "%9d patch LOD groups\n", groupCount );\r
 523 }\r
 524 \r