tools/quake3/q3map2/mesh.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 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         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 /*
  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         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
 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         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                                                 }
 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                                                 }
 267                                                 else if ( y >= in.height ) {
 268                                                         y = 1 + y - in.height;
 269                                                 }
 270                                         }
 271
 272                                         if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
 273                                                 break;                  // edge of patch
 274                                         }
 275                                         VectorSubtract( in.verts[y * in.width + x].xyz, base, temp );
 276                                         if ( VectorNormalize( temp, temp ) == 0 ) {
 277                                                 continue;               // degenerate edge, get more dist
 278                                         }
 279                                         else {
 280                                                 good[k] = qtrue;
 281                                                 VectorCopy( temp, around[k] );
 282                                                 break;                  // good edge
 283                                         }
 284                                 }
 285                         }
 286
 287                         VectorClear( sum );
 288                         for ( k = 0 ; k < 8 ; k++ ) {
 289                                 if ( !good[k] || !good[( k + 1 ) & 7] ) {
 290                                         continue;   // didn't get two points
 291                                 }
 292                                 CrossProduct( around[( k + 1 ) & 7], around[k], normal );
 293                                 if ( VectorNormalize( normal, normal ) == 0 ) {
 294                                         continue;
 295                                 }
 296                                 VectorAdd( normal, sum, sum );
 297                                 count++;
 298                         }
 299                         if ( count == 0 ) {
 300 //Sys_Printf("bad normal\n");
 301                                 count = 1;
 302                         }
 303                         VectorNormalize( sum, dv->normal );
 304                 }
 305         }
 306 }
 307
 308 /*
 309    PutMeshOnCurve()
 310    drops the aproximating points onto the curve
 311    ydnar: fixme: make this use LerpDrawVert() rather than this complicated mess
 312  */
 313
 314 void PutMeshOnCurve( mesh_t in ) {
 315         int i, j, l, m;
 316         float prev, next;
 317
 318
 319         // put all the aproximating points on the curve
 320         for ( i = 0 ; i < in.width ; i++ ) {
 321                 for ( j = 1 ; j < in.height ; j += 2 ) {
 322                         for ( l = 0 ; l < 3 ; l++ ) {
 323                                 prev = ( in.verts[j * in.width + i].xyz[l] + in.verts[( j + 1 ) * in.width + i].xyz[l] ) * 0.5;
 324                                 next = ( in.verts[j * in.width + i].xyz[l] + in.verts[( j - 1 ) * in.width + i].xyz[l] ) * 0.5;
 325                                 in.verts[j * in.width + i].xyz[l] = ( prev + next ) * 0.5;
 326
 327                                 /* ydnar: interpolating st coords */
 328                                 if ( l < 2 ) {
 329                                         prev = ( in.verts[j * in.width + i].st[l] + in.verts[( j + 1 ) * in.width + i].st[l] ) * 0.5;
 330                                         next = ( in.verts[j * in.width + i].st[l] + in.verts[( j - 1 ) * in.width + i].st[l] ) * 0.5;
 331                                         in.verts[j * in.width + i].st[l] = ( prev + next ) * 0.5;
 332
 333                                         for ( m = 0; m < MAX_LIGHTMAPS; m++ )
 334                                         {
 335                                                 prev = ( in.verts[j * in.width + i].lightmap[ m ][l] + in.verts[( j + 1 ) * in.width + i].lightmap[ m ][l] ) * 0.5;
 336                                                 next = ( in.verts[j * in.width + i].lightmap[ m ][l] + in.verts[( j - 1 ) * in.width + i].lightmap[ m ][l] ) * 0.5;
 337                                                 in.verts[j * in.width + i].lightmap[ m ][l] = ( prev + next ) * 0.5;
 338                                         }
 339                                 }
 340                         }
 341                 }
 342         }
 343
 344         for ( j = 0 ; j < in.height ; j++ ) {
 345                 for ( i = 1 ; i < in.width ; i += 2 ) {
 346                         for ( l = 0 ; l < 3 ; l++ ) {
 347                                 prev = ( in.verts[j * in.width + i].xyz[l] + in.verts[j * in.width + i + 1].xyz[l] ) * 0.5;
 348                                 next = ( in.verts[j * in.width + i].xyz[l] + in.verts[j * in.width + i - 1].xyz[l] ) * 0.5;
 349                                 in.verts[j * in.width + i].xyz[l] = ( prev + next ) * 0.5;
 350
 351                                 /* ydnar: interpolating st coords */
 352                                 if ( l < 2 ) {
 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         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         /* ydnar: static for os x */
 385         MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
 386
 387
 388         out.width = in.width;
 389         out.height = in.height;
 390
 391         for ( i = 0 ; i < in.width ; i++ ) {
 392                 for ( j = 0 ; j < in.height ; j++ ) {
 393                         expand[j][i] = in.verts[j * in.width + i];
 394                 }
 395         }
 396
 397         // horizontal subdivisions
 398         for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
 399                 // check subdivided midpoints against control points
 400                 for ( i = 0 ; i < out.height ; i++ ) {
 401                         for ( l = 0 ; l < 3 ; l++ ) {
 402                                 prevxyz[l] = expand[i][j + 1].xyz[l] - expand[i][j].xyz[l];
 403                                 nextxyz[l] = expand[i][j + 2].xyz[l] - expand[i][j + 1].xyz[l];
 404                                 midxyz[l] = ( expand[i][j].xyz[l] + expand[i][j + 1].xyz[l] * 2
 405                                                           + expand[i][j + 2].xyz[l] ) * 0.25;
 406                         }
 407
 408                         // if the span length is too long, force a subdivision
 409                         if ( VectorLength( prevxyz ) > minLength
 410                                  || VectorLength( nextxyz ) > minLength ) {
 411                                 break;
 412                         }
 413
 414                         // see if this midpoint is off far enough to subdivide
 415                         VectorSubtract( expand[i][j + 1].xyz, midxyz, delta );
 416                         len = VectorLength( delta );
 417                         if ( len > maxError ) {
 418                                 break;
 419                         }
 420                 }
 421
 422                 if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
 423                         break;  // can't subdivide any more
 424                 }
 425
 426                 if ( i == out.height ) {
 427                         continue;   // didn't need subdivision
 428                 }
 429
 430                 // insert two columns and replace the peak
 431                 out.width += 2;
 432
 433                 for ( i = 0 ; i < out.height ; i++ ) {
 434                         LerpDrawVert( &expand[i][j], &expand[i][j + 1], &prev );
 435                         LerpDrawVert( &expand[i][j + 1], &expand[i][j + 2], &next );
 436                         LerpDrawVert( &prev, &next, &mid );
 437
 438                         for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
 439                                 expand[i][k] = expand[i][k - 2];
 440                         }
 441                         expand[i][j + 1] = prev;
 442                         expand[i][j + 2] = mid;
 443                         expand[i][j + 3] = next;
 444                 }
 445
 446                 // back up and recheck this set again, it may need more subdivision
 447                 j -= 2;
 448
 449         }
 450
 451         // vertical subdivisions
 452         for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
 453                 // check subdivided midpoints against control points
 454                 for ( i = 0 ; i < out.width ; i++ ) {
 455                         for ( l = 0 ; l < 3 ; l++ ) {
 456                                 prevxyz[l] = expand[j + 1][i].xyz[l] - expand[j][i].xyz[l];
 457                                 nextxyz[l] = expand[j + 2][i].xyz[l] - expand[j + 1][i].xyz[l];
 458                                 midxyz[l] = ( expand[j][i].xyz[l] + expand[j + 1][i].xyz[l] * 2
 459                                                           + expand[j + 2][i].xyz[l] ) * 0.25;
 460                         }
 461
 462                         // if the span length is too long, force a subdivision
 463                         if ( VectorLength( prevxyz ) > minLength
 464                                  || VectorLength( nextxyz ) > minLength ) {
 465                                 break;
 466                         }
 467                         // see if this midpoint is off far enough to subdivide
 468                         VectorSubtract( expand[j + 1][i].xyz, midxyz, delta );
 469                         len = VectorLength( delta );
 470                         if ( len > maxError ) {
 471                                 break;
 472                         }
 473                 }
 474
 475                 if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
 476                         break;  // can't subdivide any more
 477                 }
 478
 479                 if ( i == out.width ) {
 480                         continue;   // didn't need subdivision
 481                 }
 482
 483                 // insert two columns and replace the peak
 484                 out.height += 2;
 485
 486                 for ( i = 0 ; i < out.width ; i++ ) {
 487                         LerpDrawVert( &expand[j][i], &expand[j + 1][i], &prev );
 488                         LerpDrawVert( &expand[j + 1][i], &expand[j + 2][i], &next );
 489                         LerpDrawVert( &prev, &next, &mid );
 490
 491                         for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
 492                                 expand[k][i] = expand[k - 2][i];
 493                         }
 494                         expand[j + 1][i] = prev;
 495                         expand[j + 2][i] = mid;
 496                         expand[j + 3][i] = next;
 497                 }
 498
 499                 // back up and recheck this set again, it may need more subdivision
 500                 j -= 2;
 501
 502         }
 503
 504         // collapse the verts
 505
 506         out.verts = &expand[0][0];
 507         for ( i = 1 ; i < out.height ; i++ ) {
 508                 memmove( &out.verts[i * out.width], expand[i], out.width * sizeof( bspDrawVert_t ) );
 509         }
 510
 511         return CopyMesh( &out );
 512 }
 513
 514
 515
 516 /*
 517    IterationsForCurve() - ydnar
 518    given a curve of a certain length, return the number of subdivision iterations
 519    note: this is affected by subdivision amount
 520  */
 521
 522 int IterationsForCurve( float len, int subdivisions ){
 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
 535         /* return to caller */
 536         return iterations;
 537 }
 538
 539
 540 /*
 541    SubdivideMesh2() - ydnar
 542    subdivides each mesh quad a specified number of times
 543  */
 544
 545 mesh_t *SubdivideMesh2( mesh_t in, int iterations ){
 546         int i, j, k;
 547         bspDrawVert_t prev, next, mid;
 548         mesh_t out;
 549
 550         /* ydnar: static for os x */
 551         MAC_STATIC bspDrawVert_t expand[ MAX_EXPANDED_AXIS ][ MAX_EXPANDED_AXIS ];
 552
 553
 554         /* initial setup */
 555         out.width = in.width;
 556         out.height = in.height;
 557         for ( i = 0; i < in.width; i++ )
 558         {
 559                 for ( j = 0; j < in.height; j++ )
 560                         expand[ j ][ i ] = in.verts[ j * in.width + i ];
 561         }
 562
 563         /* keep chopping */
 564         for ( ; iterations > 0; iterations-- )
 565         {
 566                 /* horizontal subdivisions */
 567                 for ( j = 0; j + 2 < out.width; j += 4 )
 568                 {
 569                         /* check size limit */
 570                         if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
 571                                 break;
 572                         }
 573
 574                         /* insert two columns and replace the peak */
 575                         out.width += 2;
 576                         for ( i = 0; i < out.height; i++ )
 577                         {
 578                                 LerpDrawVert( &expand[ i ][ j ], &expand[ i ][ j + 1 ], &prev );
 579                                 LerpDrawVert( &expand[ i ][ j + 1 ], &expand[ i ][ j + 2 ], &next );
 580                                 LerpDrawVert( &prev, &next, &mid );
 581
 582                                 for ( k = out.width - 1 ; k > j + 3; k-- )
 583                                         expand [ i ][ k ] = expand[ i ][ k - 2 ];
 584                                 expand[ i ][ j + 1 ] = prev;
 585                                 expand[ i ][ j + 2 ] = mid;
 586                                 expand[ i ][ j + 3 ] = next;
 587                         }
 588
 589                 }
 590
 591                 /* vertical subdivisions */
 592                 for ( j = 0; j + 2 < out.height; j += 4 )
 593                 {
 594                         /* check size limit */
 595                         if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
 596                                 break;
 597                         }
 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         vec3_t pVec, vec;
 638
 639         VectorSubtract( point, vStart, pVec );
 640         VectorSubtract( vEnd, vStart, vec );
 641         VectorNormalize( vec, vec );
 642         // project onto the directional vector for this segment
 643         VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );
 644 }
 645
 646 /*
 647    ================
 648    RemoveLinearMeshColumsRows
 649    ================
 650  */
 651 mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {
 652         int i, j, k;
 653         float len, maxLength;
 654         vec3_t proj, dir;
 655         mesh_t out;
 656
 657         /* ydnar: static for os x */
 658         MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
 659
 660
 661         out.width = in->width;
 662         out.height = in->height;
 663
 664         for ( i = 0 ; i < in->width ; i++ ) {
 665                 for ( j = 0 ; j < in->height ; j++ ) {
 666                         expand[j][i] = in->verts[j * in->width + i];
 667                 }
 668         }
 669
 670         for ( j = 1 ; j < out.width - 1; j++ ) {
 671                 maxLength = 0;
 672                 for ( i = 0 ; i < out.height ; i++ ) {
 673                         ProjectPointOntoVector( expand[i][j].xyz, expand[i][j - 1].xyz, expand[i][j + 1].xyz, proj );
 674                         VectorSubtract( expand[i][j].xyz, proj, dir );
 675                         len = VectorLength( dir );
 676                         if ( len > maxLength ) {
 677                                 maxLength = len;
 678                         }
 679                 }
 680                 if ( maxLength < 0.1 ) {
 681                         out.width--;
 682                         for ( i = 0 ; i < out.height ; i++ ) {
 683                                 for ( k = j; k < out.width; k++ ) {
 684                                         expand[i][k] = expand[i][k + 1];
 685                                 }
 686                         }
 687                         j--;
 688                 }
 689         }
 690         for ( j = 1 ; j < out.height - 1; j++ ) {
 691                 maxLength = 0;
 692                 for ( i = 0 ; i < out.width ; i++ ) {
 693                         ProjectPointOntoVector( expand[j][i].xyz, expand[j - 1][i].xyz, expand[j + 1][i].xyz, proj );
 694                         VectorSubtract( expand[j][i].xyz, proj, dir );
 695                         len = VectorLength( dir );
 696                         if ( len > maxLength ) {
 697                                 maxLength = len;
 698                         }
 699                 }
 700                 if ( maxLength < 0.1 ) {
 701                         out.height--;
 702                         for ( i = 0 ; i < out.width ; i++ ) {
 703                                 for ( k = j; k < out.height; k++ ) {
 704                                         expand[k][i] = expand[k + 1][i];
 705                                 }
 706                         }
 707                         j--;
 708                 }
 709         }
 710         // collapse the verts
 711         out.verts = &expand[0][0];
 712         for ( i = 1 ; i < out.height ; i++ ) {
 713                 memmove( &out.verts[i * out.width], expand[i], out.width * sizeof( bspDrawVert_t ) );
 714         }
 715
 716         return CopyMesh( &out );
 717 }
 718
 719
 720
 721 /*
 722    =================
 723    SubdivideMeshQuads
 724    =================
 725  */
 726 mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int *widthtable, int *heighttable ){
 727         int i, j, k, w, h, maxsubdivisions, subdivisions;
 728         vec3_t dir;
 729         float length, maxLength, amount;
 730         mesh_t out;
 731         bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
 732
 733         out.width = in->width;
 734         out.height = in->height;
 735
 736         for ( i = 0 ; i < in->width ; i++ ) {
 737                 for ( j = 0 ; j < in->height ; j++ ) {
 738                         expand[j][i] = in->verts[j * in->width + i];
 739                 }
 740         }
 741
 742         if ( maxsize > MAX_EXPANDED_AXIS ) {
 743                 Error( "SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS" );
 744         }
 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
 765                 widthtable[w] = subdivisions + 1;
 766                 if ( subdivisions <= 0 ) {
 767                         continue;
 768                 }
 769
 770                 out.width += subdivisions;
 771
 772                 for ( i = 0 ; i < out.height ; i++ ) {
 773                         for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {
 774                                 expand[i][k] = expand[i][k - subdivisions];
 775                         }
 776                         for ( k = 1; k <= subdivisions; k++ )
 777                         {
 778                                 amount = (float) k / ( subdivisions + 1 );
 779                                 LerpDrawVertAmount( &expand[i][j], &expand[i][j + subdivisions + 1], amount, &expand[i][j + k] );
 780                         }
 781                 }
 782         }
 783
 784         maxsubdivisions = ( maxsize - in->height ) / ( in->height - 1 );
 785
 786         for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1 ) {
 787                 maxLength = 0;
 788                 for ( i = 0 ; i < out.width ; i++ ) {
 789                         VectorSubtract( expand[j + 1][i].xyz, expand[j][i].xyz, dir );
 790                         length = VectorLength( dir );
 791                         if ( length  > maxLength ) {
 792                                 maxLength = length;
 793                         }
 794                 }
 795
 796                 subdivisions = (int) ( maxLength / minLength );
 797                 if ( subdivisions > maxsubdivisions ) {
 798                         subdivisions = maxsubdivisions;
 799                 }
 800
 801                 heighttable[h] = subdivisions + 1;
 802                 if ( subdivisions <= 0 ) {
 803                         continue;
 804                 }
 805
 806                 out.height += subdivisions;
 807
 808                 for ( i = 0 ; i < out.width ; i++ ) {
 809                         for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {
 810                                 expand[k][i] = expand[k - subdivisions][i];
 811                         }
 812                         for ( k = 1; k <= subdivisions; k++ )
 813                         {
 814                                 amount = (float) k / ( subdivisions + 1 );
 815                                 LerpDrawVertAmount( &expand[j][i], &expand[j + subdivisions + 1][i], amount, &expand[j + k][i] );
 816                         }
 817                 }
 818         }
 819
 820         // collapse the verts
 821         out.verts = &expand[0][0];
 822         for ( i = 1 ; i < out.height ; i++ ) {
 823                 memmove( &out.verts[i * out.width], expand[i], out.width * sizeof( bspDrawVert_t ) );
 824         }
 825
 826         return CopyMesh( &out );
 827 }