tools/quake3/q3map2/mesh.c

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