tools/quake3/q3map2/mesh.c

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