tools/quake3/q3map2/patch.c

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