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