tools/quake3/q3map2/mesh.c

   1 /*
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 ----------------------------------------------------------------------------------
  22
  23 This code has been altered significantly from its original form, to support
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
  25
  26 ------------------------------------------------------------------------------- */
  27
  28
  29
  30 /* marker */
  31 #define MESH_C
  32
  33
  34
  35 /* dependencies */
  36 #include "q3map2.h"
  37
  38
  39
  40 /*
  41 LerpDrawVert()
  42 returns an 50/50 interpolated vert
  43 */
  44
  45 void LerpDrawVert( bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *out )
  46 {
  47         int             k;
  48
  49
  50         out->xyz[ 0 ] = 0.5 * (a->xyz[ 0 ] + b->xyz[ 0 ]);
  51         out->xyz[ 1 ] = 0.5 * (a->xyz[ 1 ] + b->xyz[ 1 ]);
  52         out->xyz[ 2 ] = 0.5 * (a->xyz[ 2 ] + b->xyz[ 2 ]);
  53
  54         out->st[ 0 ] = 0.5 * (a->st[ 0 ] + b->st[ 0 ]);
  55         out->st[ 1 ] = 0.5 * (a->st[ 1 ] + b->st[ 1 ]);
  56
  57         for( k = 0; k < MAX_LIGHTMAPS; k++ )
  58         {
  59                 out->lightmap[ k ][ 0 ] = 0.5f * (a->lightmap[ k ][ 0 ] + b->lightmap[ k ][ 0 ]);
  60                 out->lightmap[ k ][ 1 ] = 0.5f * (a->lightmap[ k ][ 1 ] + b->lightmap[ k ][ 1 ]);
  61                 out->color[ k ][ 0 ] = (a->color[ k ][ 0 ] + b->color[ k ][ 0 ]) >> 1;
  62                 out->color[ k ][ 1 ] = (a->color[ k ][ 1 ] + b->color[ k ][ 1 ]) >> 1;
  63                 out->color[ k ][ 2 ] = (a->color[ k ][ 2 ] + b->color[ k ][ 2 ]) >> 1;
  64                 out->color[ k ][ 3 ] = (a->color[ k ][ 3 ] + b->color[ k ][ 3 ]) >> 1;
  65         }
  66
  67         /* ydnar: added normal interpolation */
  68         out->normal[ 0 ] = 0.5f * (a->normal[ 0 ] + b->normal[ 0 ]);
  69         out->normal[ 1 ] = 0.5f * (a->normal[ 1 ] + b->normal[ 1 ]);
  70         out->normal[ 2 ] = 0.5f * (a->normal[ 2 ] + b->normal[ 2 ]);
  71
  72         /* if the interpolant created a bogus normal, just copy the normal from a */
  73         if( VectorNormalize( out->normal, out->normal ) == 0 )
  74                 VectorCopy( a->normal, out->normal );
  75 }
  76
  77
  78
  79 /*
  80 LerpDrawVertAmount()
  81 returns a biased interpolated vert
  82 */
  83
  84 void LerpDrawVertAmount( bspDrawVert_t *a, bspDrawVert_t *b, float amount, bspDrawVert_t *out )
  85 {
  86         int             k;
  87
  88
  89         out->xyz[ 0 ] = a->xyz[ 0 ] + amount * (b->xyz[ 0 ] - a->xyz[ 0 ]);
  90         out->xyz[ 1 ] = a->xyz[ 1 ] + amount * (b->xyz[ 1 ] - a->xyz[ 1 ]);
  91         out->xyz[ 2 ] = a->xyz[ 2 ] + amount * (b->xyz[ 2 ] - a->xyz[ 2 ]);
  92
  93         out->st[ 0 ] = a->st[ 0 ] + amount * (b->st[ 0 ] - a->st[ 0 ]);
  94         out->st[ 1 ] = a->st[ 1 ] + amount * (b->st[ 1 ] - a->st[ 1 ]);
  95
  96         for( k = 0; k < MAX_LIGHTMAPS; k++ )
  97         {
  98                 out->lightmap[ k ][ 0 ] = a->lightmap[ k ][ 0 ] + amount * (b->lightmap[ k ][ 0 ] - a->lightmap[ k ][ 0 ]);
  99                 out->lightmap[ k ][ 1 ] = a->lightmap[ k ][ 1 ] + amount * (b->lightmap[ k ][ 1 ] - a->lightmap[ k ][ 1 ]);
 100                 out->color[ k ][ 0 ] = a->color[ k ][ 0 ] + amount * (b->color[ k ][ 0 ] - a->color[ k ][ 0 ]);
 101                 out->color[ k ][ 1 ] = a->color[ k ][ 1 ] + amount * (b->color[ k ][ 1 ] - a->color[ k ][ 1 ]);
 102                 out->color[ k ][ 2 ] = a->color[ k ][ 2 ] + amount * (b->color[ k ][ 2 ] - a->color[ k ][ 2 ]);
 103                 out->color[ k ][ 3 ] = a->color[ k ][ 3 ] + amount * (b->color[ k ][ 3 ] - a->color[ k ][ 3 ]);
 104         }
 105
 106         out->normal[ 0 ] = a->normal[ 0 ] + amount * (b->normal[ 0 ] - a->normal[ 0 ]);
 107         out->normal[ 1 ] = a->normal[ 1 ] + amount * (b->normal[ 1 ] - a->normal[ 1 ]);
 108         out->normal[ 2 ] = a->normal[ 2 ] + amount * (b->normal[ 2 ] - a->normal[ 2 ]);
 109
 110         /* if the interpolant created a bogus normal, just copy the normal from a */
 111         if( VectorNormalize( out->normal, out->normal ) == 0 )
 112                 VectorCopy( a->normal, out->normal );
 113 }
 114
 115
 116 void FreeMesh( mesh_t *m ) {
 117         free( m->verts );
 118         free( m );
 119 }
 120
 121 void PrintMesh( mesh_t *m ) {
 122         int             i, j;
 123
 124         for ( i = 0 ; i < m->height ; i++ ) {
 125                 for ( j = 0 ; j < m->width ; j++ ) {
 126                         Sys_Printf("(%5.2f %5.2f %5.2f) "
 127                                 , m->verts[i*m->width+j].xyz[0]
 128                                 , m->verts[i*m->width+j].xyz[1]
 129                                 , m->verts[i*m->width+j].xyz[2] );
 130                 }
 131                 Sys_Printf("\n");
 132         }
 133 }
 134
 135
 136 mesh_t *CopyMesh( mesh_t *mesh ) {
 137         mesh_t  *out;
 138         int             size;
 139
 140         out = safe_malloc( sizeof( *out ) );
 141         out->width = mesh->width;
 142         out->height = mesh->height;
 143
 144         size = out->width * out->height * sizeof( *out->verts );
 145         out->verts = safe_malloc( size );
 146         memcpy( out->verts, mesh->verts, size );
 147
 148         return out;
 149 }
 150
 151
 152 /*
 153 TransposeMesh()
 154 returns a transposed copy of the mesh, freeing the original
 155 */
 156
 157 mesh_t *TransposeMesh( mesh_t *in ) {
 158         int                     w, h;
 159         mesh_t          *out;
 160
 161         out = safe_malloc( sizeof( *out ) );
 162         out->width = in->height;
 163         out->height = in->width;
 164         out->verts = safe_malloc( out->width * out->height * sizeof( bspDrawVert_t ) );
 165
 166         for ( h = 0 ; h < in->height ; h++ ) {
 167                 for ( w = 0 ; w < in->width ; w++ ) {
 168                         out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];
 169                 }
 170         }
 171
 172         FreeMesh( in );
 173
 174         return out;
 175 }
 176
 177 void InvertMesh( mesh_t *in ) {
 178         int                     w, h;
 179         bspDrawVert_t   temp;
 180
 181         for ( h = 0 ; h < in->height ; h++ ) {
 182                 for ( w = 0 ; w < in->width / 2 ; w++ ) {
 183                         temp = in->verts[ h * in->width + w ];
 184                         in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];
 185                         in->verts[ h * in->width + in->width - 1 - w ] = temp;
 186                 }
 187         }
 188 }
 189
 190 /*
 191 =================
 192 MakeMeshNormals
 193
 194 =================
 195 */
 196 void MakeMeshNormals( mesh_t in )
 197 {
 198         int             i, j, k, dist;
 199         vec3_t  normal;
 200         vec3_t  sum;
 201         int             count;
 202         vec3_t  base;
 203         vec3_t  delta;
 204         int             x, y;
 205         bspDrawVert_t   *dv;
 206         vec3_t          around[8], temp;
 207         qboolean        good[8];
 208         qboolean        wrapWidth, wrapHeight;
 209         float           len;
 210         int                             neighbors[8][2] =
 211                                         {
 212                                                 {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
 213                                         };
 214
 215
 216         wrapWidth = qfalse;
 217         for ( i = 0 ; i < in.height ; i++ ) {
 218                 VectorSubtract( in.verts[i*in.width].xyz,
 219                         in.verts[i*in.width+in.width-1].xyz, delta );
 220                 len = VectorLength( delta );
 221                 if ( len > 1.0 ) {
 222                         break;
 223                 }
 224         }
 225         if ( i == in.height ) {
 226                 wrapWidth = qtrue;
 227         }
 228
 229         wrapHeight = qfalse;
 230         for ( i = 0 ; i < in.width ; i++ ) {
 231                 VectorSubtract( in.verts[i].xyz,
 232                         in.verts[i + (in.height-1)*in.width].xyz, delta );
 233                 len = VectorLength( delta );
 234                 if ( len > 1.0 ) {
 235                         break;
 236                 }
 237         }
 238         if ( i == in.width) {
 239                 wrapHeight = qtrue;
 240         }
 241
 242
 243         for ( i = 0 ; i < in.width ; i++ ) {
 244                 for ( j = 0 ; j < in.height ; j++ ) {
 245                         count = 0;
 246                         dv = &in.verts[j*in.width+i];
 247                         VectorCopy( dv->xyz, base );
 248                         for ( k = 0 ; k < 8 ; k++ ) {
 249                                 VectorClear( around[k] );
 250                                 good[k] = qfalse;
 251
 252                                 for ( dist = 1 ; dist <= 3 ; dist++ ) {
 253                                         x = i + neighbors[k][0] * dist;
 254                                         y = j + neighbors[k][1] * dist;
 255                                         if ( wrapWidth ) {
 256                                                 if ( x < 0 ) {
 257                                                         x = in.width - 1 + x;
 258                                                 } else if ( x >= in.width ) {
 259                                                         x = 1 + x - in.width;
 260                                                 }
 261                                         }
 262                                         if ( wrapHeight ) {
 263                                                 if ( y < 0 ) {
 264                                                         y = in.height - 1 + y;
 265                                                 } else if ( y >= in.height ) {
 266                                                         y = 1 + y - in.height;
 267                                                 }
 268                                         }
 269
 270                                         if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
 271                                                 break;                                  // edge of patch
 272                                         }
 273                                         VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );
 274                                         if ( VectorNormalize( temp, temp ) == 0 ) {
 275                                                 continue;                               // degenerate edge, get more dist
 276                                         } else {
 277                                                 good[k] = qtrue;
 278                                                 VectorCopy( temp, around[k] );
 279                                                 break;                                  // good edge
 280                                         }
 281                                 }
 282                         }
 283
 284                         VectorClear( sum );
 285                         for ( k = 0 ; k < 8 ; k++ ) {
 286                                 if ( !good[k] || !good[(k+1)&7] ) {
 287                                         continue;       // didn't get two points
 288                                 }
 289                                 CrossProduct( around[(k+1)&7], around[k], normal );
 290                                 if ( VectorNormalize( normal, normal ) == 0 ) {
 291                                         continue;
 292                                 }
 293                                 VectorAdd( normal, sum, sum );
 294                                 count++;
 295                         }
 296                         if ( count == 0 ) {
 297 //Sys_Printf("bad normal\n");
 298                                 count = 1;
 299                         }
 300                         VectorNormalize( sum, dv->normal );
 301                 }
 302         }
 303 }
 304
 305 /*
 306 PutMeshOnCurve()
 307 drops the aproximating points onto the curve
 308 ydnar: fixme: make this use LerpDrawVert() rather than this complicated mess
 309 */
 310
 311 void PutMeshOnCurve( mesh_t in ) {
 312         int             i, j, l, m;
 313         float   prev, next;
 314
 315
 316         // put all the aproximating points on the curve
 317         for ( i = 0 ; i < in.width ; i++ ) {
 318                 for ( j = 1 ; j < in.height ; j += 2 ) {
 319                         for ( l = 0 ; l < 3 ; l++ ) {
 320                                 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;
 321                                 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;
 322                                 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
 323
 324                                 /* ydnar: interpolating st coords */
 325                                 if( l < 2 )
 326                                 {
 327                                         prev = ( in.verts[j*in.width+i].st[l] + in.verts[(j+1)*in.width+i].st[l] ) * 0.5;
 328                                         next = ( in.verts[j*in.width+i].st[l] + in.verts[(j-1)*in.width+i].st[l] ) * 0.5;
 329                                         in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
 330
 331                                         for( m = 0; m < MAX_LIGHTMAPS; m++ )
 332                                         {
 333                                                 prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j+1)*in.width+i].lightmap[ m ][l] ) * 0.5;
 334                                                 next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j-1)*in.width+i].lightmap[ m ][l] ) * 0.5;
 335                                                 in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
 336                                         }
 337                                 }
 338                         }
 339                 }
 340         }
 341
 342         for ( j = 0 ; j < in.height ; j++ ) {
 343                 for ( i = 1 ; i < in.width ; i += 2 ) {
 344                         for ( l = 0 ; l < 3 ; l++ ) {
 345                                 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;
 346                                 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;
 347                                 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
 348
 349                                 /* ydnar: interpolating st coords */
 350                                 if( l < 2 )
 351                                 {
 352                                         prev = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i+1].st[l] ) * 0.5;
 353                                         next = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i-1].st[l] ) * 0.5;
 354                                         in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
 355
 356                                         for( m = 0; m < MAX_LIGHTMAPS; m++ )
 357                                         {
 358                                                 prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i+1].lightmap[ m ][l] ) * 0.5;
 359                                                 next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i-1].lightmap[ m ][l] ) * 0.5;
 360                                                 in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
 361                                         }
 362                                 }
 363                         }
 364                 }
 365         }
 366 }
 367
 368
 369 /*
 370 =================
 371 SubdivideMesh
 372
 373 =================
 374 */
 375 mesh_t *SubdivideMesh( mesh_t in, float maxError, float minLength )
 376 {
 377         int                                                     i, j, k, l;
 378         bspDrawVert_t                           prev, next, mid;
 379         vec3_t                                          prevxyz, nextxyz, midxyz;
 380         vec3_t                                          delta;
 381         float                                           len;
 382         mesh_t                                          out;
 383
 384         static bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
 385
 386
 387         out.width = in.width;
 388         out.height = in.height;
 389
 390         for ( i = 0 ; i < in.width ; i++ ) {
 391                 for ( j = 0 ; j < in.height ; j++ ) {
 392                         expand[j][i] = in.verts[j*in.width+i];
 393                 }
 394         }
 395
 396         // horizontal subdivisions
 397         for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
 398                 // check subdivided midpoints against control points
 399                 for ( i = 0 ; i < out.height ; i++ ) {
 400                         for ( l = 0 ; l < 3 ; l++ ) {
 401                                 prevxyz[l] = expand[i][j+1].xyz[l] - expand[i][j].xyz[l];
 402                                 nextxyz[l] = expand[i][j+2].xyz[l] - expand[i][j+1].xyz[l];
 403                                 midxyz[l] = (expand[i][j].xyz[l] + expand[i][j+1].xyz[l] * 2
 404                                                 + expand[i][j+2].xyz[l] ) * 0.25;
 405                         }
 406
 407                         // if the span length is too long, force a subdivision
 408                         if ( VectorLength( prevxyz ) > minLength
 409                                 || VectorLength( nextxyz ) > minLength ) {
 410                                 break;
 411                         }
 412
 413                         // see if this midpoint is off far enough to subdivide
 414                         VectorSubtract( expand[i][j+1].xyz, midxyz, delta );
 415                         len = VectorLength( delta );
 416                         if ( len > maxError ) {
 417                                 break;
 418                         }
 419                 }
 420
 421                 if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
 422                         break;  // can't subdivide any more
 423                 }
 424
 425                 if ( i == out.height ) {
 426                         continue;       // didn't need subdivision
 427                 }
 428
 429                 // insert two columns and replace the peak
 430                 out.width += 2;
 431
 432                 for ( i = 0 ; i < out.height ; i++ ) {
 433                         LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev );
 434                         LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next );
 435                         LerpDrawVert( &prev, &next, &mid );
 436
 437                         for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
 438                                 expand[i][k] = expand[i][k-2];
 439                         }
 440                         expand[i][j + 1] = prev;
 441                         expand[i][j + 2] = mid;
 442                         expand[i][j + 3] = next;
 443                 }
 444
 445                 // back up and recheck this set again, it may need more subdivision
 446                 j -= 2;
 447
 448         }
 449
 450         // vertical subdivisions
 451         for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
 452                 // check subdivided midpoints against control points
 453                 for ( i = 0 ; i < out.width ; i++ ) {
 454                         for ( l = 0 ; l < 3 ; l++ ) {
 455                                 prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l];
 456                                 nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l];
 457                                 midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2
 458                                                 + expand[j+2][i].xyz[l] ) * 0.25;
 459                         }
 460
 461                         // if the span length is too long, force a subdivision
 462                         if ( VectorLength( prevxyz ) > minLength
 463                                 || VectorLength( nextxyz ) > minLength ) {
 464                                 break;
 465                         }
 466                         // see if this midpoint is off far enough to subdivide
 467                         VectorSubtract( expand[j+1][i].xyz, midxyz, delta );
 468                         len = VectorLength( delta );
 469                         if ( len > maxError ) {
 470                                 break;
 471                         }
 472                 }
 473
 474                 if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
 475                         break;  // can't subdivide any more
 476                 }
 477
 478                 if ( i == out.width ) {
 479                         continue;       // didn't need subdivision
 480                 }
 481
 482                 // insert two columns and replace the peak
 483                 out.height += 2;
 484
 485                 for ( i = 0 ; i < out.width ; i++ ) {
 486                         LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev );
 487                         LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next );
 488                         LerpDrawVert( &prev, &next, &mid );
 489
 490                         for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
 491                                 expand[k][i] = expand[k-2][i];
 492                         }
 493                         expand[j+1][i] = prev;
 494                         expand[j+2][i] = mid;
 495                         expand[j+3][i] = next;
 496                 }
 497
 498                 // back up and recheck this set again, it may need more subdivision
 499                 j -= 2;
 500
 501         }
 502
 503         // collapse the verts
 504
 505         out.verts = &expand[0][0];
 506         for ( i = 1 ; i < out.height ; i++ ) {
 507                 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
 508         }
 509
 510         return CopyMesh(&out);
 511 }
 512
 513
 514
 515 /*
 516 IterationsForCurve() - ydnar
 517 given a curve of a certain length, return the number of subdivision iterations
 518 note: this is affected by subdivision amount
 519 */
 520
 521 int IterationsForCurve( float len, int subdivisions )
 522 {
 523         int             iterations, facets;
 524
 525
 526         /* calculate the number of subdivisions */
 527         for( iterations = 0; iterations < 3; iterations++ )
 528         {
 529                 facets = subdivisions * 16 * pow( 2, iterations );
 530                 if( facets >= len )
 531                         break;
 532         }
 533
 534         /* return to caller */
 535         return iterations;
 536 }
 537
 538
 539 /*
 540 SubdivideMesh2() - ydnar
 541 subdivides each mesh quad a specified number of times
 542 */
 543
 544 mesh_t *SubdivideMesh2( mesh_t in, int iterations )
 545 {
 546         int                                                     i, j, k;
 547         bspDrawVert_t                           prev, next, mid;
 548         mesh_t                                          out;
 549
 550         static bspDrawVert_t expand[ MAX_EXPANDED_AXIS ][ MAX_EXPANDED_AXIS ];
 551
 552
 553         /* initial setup */
 554         out.width = in.width;
 555         out.height = in.height;
 556         for( i = 0; i < in.width; i++ )
 557         {
 558                 for( j = 0; j < in.height; j++ )
 559                         expand[ j ][ i ] = in.verts[ j * in.width + i ];
 560         }
 561
 562         /* keep chopping */
 563         for( iterations; iterations > 0; iterations-- )
 564         {
 565                 /* horizontal subdivisions */
 566                 for( j = 0; j + 2 < out.width; j += 4 )
 567                 {
 568                         /* check size limit */
 569                         if( out.width + 2 >= MAX_EXPANDED_AXIS )
 570                                 break;
 571
 572                         /* insert two columns and replace the peak */
 573                         out.width += 2;
 574                         for( i = 0; i < out.height; i++ )
 575                         {
 576                                 LerpDrawVert( &expand[ i ][ j ], &expand[ i ][ j + 1 ], &prev );
 577                                 LerpDrawVert( &expand[ i ][ j + 1 ], &expand[ i ][ j + 2 ], &next );
 578                                 LerpDrawVert( &prev, &next, &mid );
 579
 580                                 for ( k = out.width - 1 ; k > j + 3; k-- )
 581                                         expand [ i ][ k ] = expand[ i ][ k - 2 ];
 582                                 expand[ i ][ j + 1 ] = prev;
 583                                 expand[ i ][ j + 2 ] = mid;
 584                                 expand[ i ][ j + 3 ] = next;
 585                         }
 586
 587                 }
 588
 589                 /* vertical subdivisions */
 590                 for ( j = 0; j + 2 < out.height; j += 4 )
 591                 {
 592                         /* check size limit */
 593                         if( out.height + 2 >= MAX_EXPANDED_AXIS )
 594                                 break;
 595
 596                         /* insert two columns and replace the peak */
 597                         out.height += 2;
 598                         for( i = 0; i < out.width; i++ )
 599                         {
 600                                 LerpDrawVert( &expand[ j ][ i ], &expand[ j + 1 ][ i ], &prev );
 601                                 LerpDrawVert( &expand[ j + 1 ][ i ], &expand[ j + 2 ][ i ], &next );
 602                                 LerpDrawVert( &prev, &next, &mid );
 603
 604                                 for( k = out.height - 1; k > j  +  3; k-- )
 605                                         expand[ k ][ i ] = expand[ k - 2 ][ i ];
 606                                 expand[ j + 1 ][ i ] = prev;
 607                                 expand[ j + 2 ][ i ] = mid;
 608                                 expand[ j + 3 ][ i ] = next;
 609                         }
 610                 }
 611         }
 612
 613         /* collapse the verts */
 614         out.verts = &expand[ 0 ][ 0 ];
 615         for( i = 1; i < out.height; i++ )
 616                 memmove( &out.verts[ i * out.width ], expand[ i ], out.width * sizeof( bspDrawVert_t ) );
 617
 618         /* return to sender */
 619         return CopyMesh( &out );
 620 }
 621
 622
 623
 624
 625
 626
 627
 628 /*
 629 ================
 630 ProjectPointOntoVector
 631 ================
 632 */
 633 void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj )
 634 {
 635         vec3_t pVec, vec;
 636
 637         VectorSubtract( point, vStart, pVec );
 638         VectorSubtract( vEnd, vStart, vec );
 639         VectorNormalize( vec, vec );
 640         // project onto the directional vector for this segment
 641         VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );
 642 }
 643
 644 /*
 645 ================
 646 RemoveLinearMeshColumsRows
 647 ================
 648 */
 649 mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {
 650         int                                                     i, j, k;
 651         float                                           len, maxLength;
 652         vec3_t                                          proj, dir;
 653         mesh_t                                          out;
 654
 655         static bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
 656
 657
 658         out.width = in->width;
 659         out.height = in->height;
 660
 661         for ( i = 0 ; i < in->width ; i++ ) {
 662                 for ( j = 0 ; j < in->height ; j++ ) {
 663                         expand[j][i] = in->verts[j*in->width+i];
 664                 }
 665         }
 666
 667         for ( j = 1 ; j < out.width - 1; j++ ) {
 668                 maxLength = 0;
 669                 for ( i = 0 ; i < out.height ; i++ ) {
 670                         ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj);
 671                         VectorSubtract(expand[i][j].xyz, proj, dir);
 672                         len = VectorLength(dir);
 673                         if (len > maxLength) {
 674                                 maxLength = len;
 675                         }
 676                 }
 677                 if (maxLength < 0.1)
 678                 {
 679                         out.width--;
 680                         for ( i = 0 ; i < out.height ; i++ ) {
 681                                 for (k = j; k < out.width; k++) {
 682                                         expand[i][k] = expand[i][k+1];
 683                                 }
 684                         }
 685                         j--;
 686                 }
 687         }
 688         for ( j = 1 ; j < out.height - 1; j++ ) {
 689                 maxLength = 0;
 690                 for ( i = 0 ; i < out.width ; i++ ) {
 691                         ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj);
 692                         VectorSubtract(expand[j][i].xyz, proj, dir);
 693                         len = VectorLength(dir);
 694                         if (len > maxLength) {
 695                                 maxLength = len;
 696                         }
 697                 }
 698                 if (maxLength < 0.1)
 699                 {
 700                         out.height--;
 701                         for ( i = 0 ; i < out.width ; i++ ) {
 702                                 for (k = j; k < out.height; k++) {
 703                                         expand[k][i] = expand[k+1][i];
 704                                 }
 705                         }
 706                         j--;
 707                 }
 708         }
 709         // collapse the verts
 710         out.verts = &expand[0][0];
 711         for ( i = 1 ; i < out.height ; i++ ) {
 712                 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
 713         }
 714
 715         return CopyMesh(&out);
 716 }
 717
 718
 719
 720 /*
 721 =================
 722 SubdivideMeshQuads
 723 =================
 724 */
 725 mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int *widthtable, int *heighttable )
 726 {
 727         int                             i, j, k, w, h, maxsubdivisions, subdivisions;
 728         vec3_t                  dir;
 729         float                   length, maxLength, amount;
 730         mesh_t                  out;
 731
 732         static bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
 733
 734         out.width = in->width;
 735         out.height = in->height;
 736
 737         for ( i = 0 ; i < in->width ; i++ ) {
 738                 for ( j = 0 ; j < in->height ; j++ ) {
 739                         expand[j][i] = in->verts[j*in->width+i];
 740                 }
 741         }
 742
 743         if (maxsize > MAX_EXPANDED_AXIS)
 744                 Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS");
 745
 746         // horizontal subdivisions
 747
 748         maxsubdivisions = (maxsize - in->width) / (in->width - 1);
 749
 750         for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) {
 751                 maxLength = 0;
 752                 for ( i = 0 ; i < out.height ; i++ ) {
 753                         VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir);
 754                         length = VectorLength( dir );
 755                         if (length > maxLength) {
 756                                 maxLength = length;
 757                         }
 758                 }
 759
 760                 subdivisions = (int) (maxLength / minLength);
 761                 if (subdivisions > maxsubdivisions)
 762                         subdivisions = maxsubdivisions;
 763
 764                 widthtable[w] = subdivisions + 1;
 765                 if (subdivisions <= 0)
 766                         continue;
 767
 768                 out.width += subdivisions;
 769
 770                 for ( i = 0 ; i < out.height ; i++ ) {
 771                         for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {
 772                                 expand[i][k] = expand[i][k-subdivisions];
 773                         }
 774                         for (k = 1; k <= subdivisions; k++)
 775                         {
 776                                 amount = (float) k / (subdivisions + 1);
 777                                 LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]);
 778                         }
 779                 }
 780         }
 781
 782         maxsubdivisions = (maxsize - in->height) / (in->height - 1);
 783
 784         for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) {
 785                 maxLength = 0;
 786                 for ( i = 0 ; i < out.width ; i++ ) {
 787                         VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir);
 788                         length = VectorLength( dir );
 789                         if (length  > maxLength) {
 790                                 maxLength = length;
 791                         }
 792                 }
 793
 794                 subdivisions = (int) (maxLength / minLength);
 795                 if (subdivisions > maxsubdivisions)
 796                         subdivisions = maxsubdivisions;
 797
 798                 heighttable[h] = subdivisions + 1;
 799                 if (subdivisions <= 0)
 800                         continue;
 801
 802                 out.height += subdivisions;
 803
 804                 for ( i = 0 ; i < out.width ; i++ ) {
 805                         for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {
 806                                 expand[k][i] = expand[k-subdivisions][i];
 807                         }
 808                         for (k = 1; k <= subdivisions; k++)
 809                         {
 810                                 amount = (float) k / (subdivisions + 1);
 811                                 LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]);
 812                         }
 813                 }
 814         }
 815
 816         // collapse the verts
 817         out.verts = &expand[0][0];
 818         for ( i = 1 ; i < out.height ; i++ ) {
 819                 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
 820         }
 821
 822         return CopyMesh(&out);
 823 }