neo/idlib/geometry/Surface_Patch.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../precompiled.h"
  30 #pragma hdrstop
  31
  32
  33 /*
  34 =================
  35 idSurface_Patch::SetSize
  36 =================
  37 */
  38 void idSurface_Patch::SetSize( int patchWidth, int patchHeight ) {
  39         if ( patchWidth < 1 || patchWidth > maxWidth ) {
  40                 idLib::common->FatalError("idSurface_Patch::SetSize: invalid patchWidth");
  41         }
  42         if ( patchHeight < 1 || patchHeight > maxHeight ) {
  43                 idLib::common->FatalError("idSurface_Patch::SetSize: invalid patchHeight");
  44         }
  45         width = patchWidth;
  46         height = patchHeight;
  47         verts.SetNum( width * height, false );
  48 }
  49
  50 /*
  51 =================
  52 idSurface_Patch::PutOnCurve
  53
  54 Expects an expanded patch.
  55 =================
  56 */
  57 void idSurface_Patch::PutOnCurve( void ) {
  58         int i, j;
  59         idDrawVert prev, next;
  60
  61         assert( expanded == true );
  62         // put all the approximating points on the curve
  63         for ( i = 0; i < width; i++ ) {
  64                 for ( j = 1; j < height; j += 2 ) {
  65                         LerpVert( verts[j*maxWidth+i], verts[(j+1)*maxWidth+i], prev );
  66                         LerpVert( verts[j*maxWidth+i], verts[(j-1)*maxWidth+i], next );
  67                         LerpVert( prev, next, verts[j*maxWidth+i] );
  68                 }
  69         }
  70
  71         for ( j = 0; j < height; j++ ) {
  72                 for ( i = 1; i < width; i += 2 ) {
  73                         LerpVert( verts[j*maxWidth+i], verts[j*maxWidth+i+1], prev );
  74                         LerpVert( verts[j*maxWidth+i], verts[j*maxWidth+i-1], next );
  75                         LerpVert( prev, next, verts[j*maxWidth+i] );
  76                 }
  77         }
  78 }
  79
  80 /*
  81 ================
  82 idSurface_Patch::ProjectPointOntoVector
  83 ================
  84 */
  85 void idSurface_Patch::ProjectPointOntoVector( const idVec3 &point, const idVec3 &vStart, const idVec3 &vEnd, idVec3 &vProj ) {
  86         idVec3 pVec, vec;
  87
  88         pVec = point - vStart;
  89         vec = vEnd - vStart;
  90         vec.Normalize();
  91         // project onto the directional vector for this segment
  92         vProj = vStart + (pVec * vec) * vec;
  93 }
  94
  95 /*
  96 ================
  97 idSurface_Patch::RemoveLinearColumnsRows
  98
  99 Expects an expanded patch.
 100 ================
 101 */
 102 void idSurface_Patch::RemoveLinearColumnsRows( void ) {
 103         int i, j, k;
 104         float len, maxLength;
 105         idVec3 proj, dir;
 106
 107         assert( expanded == true );
 108         for ( j = 1; j < width - 1; j++ ) {
 109                 maxLength = 0;
 110                 for ( i = 0; i < height; i++ ) {
 111                         idSurface_Patch::ProjectPointOntoVector( verts[i*maxWidth + j].xyz,
 112                                                                         verts[i*maxWidth + j-1].xyz, verts[i*maxWidth + j+1].xyz, proj);
 113                         dir = verts[i*maxWidth + j].xyz - proj;
 114                         len = dir.LengthSqr();
 115                         if ( len > maxLength ) {
 116                                 maxLength = len;
 117                         }
 118                 }
 119                 if ( maxLength < Square( 0.2f ) ) {
 120                         width--;
 121                         for ( i = 0; i < height; i++ ) {
 122                                 for ( k = j; k < width; k++ ) {
 123                                         verts[i*maxWidth + k] = verts[i*maxWidth + k+1];
 124                                 }
 125                         }
 126                         j--;
 127                 }
 128         }
 129         for ( j = 1; j < height - 1; j++ ) {
 130                 maxLength = 0;
 131                 for ( i = 0; i < width; i++ ) {
 132                         idSurface_Patch::ProjectPointOntoVector( verts[j*maxWidth + i].xyz,
 133                                                                         verts[(j-1)*maxWidth + i].xyz, verts[(j+1)*maxWidth + i].xyz, proj);
 134                         dir = verts[j*maxWidth + i].xyz - proj;
 135                         len = dir.LengthSqr();
 136                         if ( len > maxLength ) {
 137                                 maxLength = len;
 138                         }
 139                 }
 140                 if ( maxLength < Square( 0.2f ) ) {
 141                         height--;
 142                         for ( i = 0; i < width; i++ ) {
 143                                 for ( k = j; k < height; k++ ) {
 144                                         verts[k*maxWidth + i] = verts[(k+1)*maxWidth + i];
 145                                 }
 146                         }
 147                         j--;
 148                 }
 149         }
 150 }
 151
 152 /*
 153 ================
 154 idSurface_Patch::ResizeExpanded
 155 ================
 156 */
 157 void idSurface_Patch::ResizeExpanded( int newHeight, int newWidth ) {
 158         int i, j;
 159
 160         assert( expanded == true );
 161         if ( newHeight <= maxHeight && newWidth <= maxWidth ) {
 162                 return;
 163         }
 164         if ( newHeight * newWidth > maxHeight * maxWidth ) {
 165                 verts.SetNum( newHeight * newWidth );
 166         }
 167         // space out verts for new height and width
 168         for ( j = maxHeight-1; j >= 0; j-- ) {
 169                 for ( i = maxWidth-1; i >= 0; i-- ) {
 170                         verts[j*newWidth + i] = verts[j*maxWidth + i];
 171                 }
 172         }
 173         maxHeight = newHeight;
 174         maxWidth = newWidth;
 175 }
 176
 177 /*
 178 ================
 179 idSurface_Patch::Collapse
 180 ================
 181 */
 182 void idSurface_Patch::Collapse( void ) {
 183         int i, j;
 184
 185         if ( !expanded ) {
 186                 idLib::common->FatalError("idSurface_Patch::Collapse: patch not expanded");
 187         }
 188         expanded = false;
 189         if ( width != maxWidth ) {
 190                 for ( j = 0; j < height; j++ ) {
 191                         for ( i = 0; i < width; i++ ) {
 192                                 verts[j*width + i] = verts[j*maxWidth + i];
 193                         }
 194                 }
 195         }
 196         verts.SetNum( width * height, false );
 197 }
 198
 199 /*
 200 ================
 201 idSurface_Patch::Expand
 202 ================
 203 */
 204 void idSurface_Patch::Expand( void ) {
 205         int i, j;
 206
 207         if ( expanded ) {
 208                 idLib::common->FatalError("idSurface_Patch::Expand: patch alread expanded");
 209         }
 210         expanded = true;
 211         verts.SetNum( maxWidth * maxHeight, false );
 212         if ( width != maxWidth ) {
 213                 for ( j = height-1; j >= 0; j-- ) {
 214                         for ( i = width-1; i >= 0; i-- ) {
 215                                 verts[j*maxWidth + i] = verts[j*width + i];
 216                         }
 217                 }
 218         }
 219 }
 220
 221 /*
 222 ============
 223 idSurface_Patch::LerpVert
 224 ============
 225 */
 226 void idSurface_Patch::LerpVert( const idDrawVert &a, const idDrawVert &b, idDrawVert &out ) const {
 227         out.xyz[0] = 0.5f * ( a.xyz[0] + b.xyz[0] );
 228         out.xyz[1] = 0.5f * ( a.xyz[1] + b.xyz[1] );
 229         out.xyz[2] = 0.5f * ( a.xyz[2] + b.xyz[2] );
 230         out.normal[0] = 0.5f * ( a.normal[0] + b.normal[0] );
 231         out.normal[1] = 0.5f * ( a.normal[1] + b.normal[1] );
 232         out.normal[2] = 0.5f * ( a.normal[2] + b.normal[2] );
 233         out.st[0] = 0.5f * ( a.st[0] + b.st[0] );
 234         out.st[1] = 0.5f * ( a.st[1] + b.st[1] );
 235 }
 236
 237 /*
 238 =================
 239 idSurface_Patch::GenerateNormals
 240
 241 Handles all the complicated wrapping and degenerate cases
 242 Expects a Not expanded patch.
 243 =================
 244 */
 245 #define COPLANAR_EPSILON        0.1f
 246
 247 void idSurface_Patch::GenerateNormals( void ) {
 248         int                     i, j, k, dist;
 249         idVec3          norm;
 250         idVec3          sum;
 251         int                     count;
 252         idVec3          base;
 253         idVec3          delta;
 254         int                     x, y;
 255         idVec3          around[8], temp;
 256         bool            good[8];
 257         bool            wrapWidth, wrapHeight;
 258         static int      neighbors[8][2] = {
 259                 {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
 260         };
 261
 262         assert( expanded == false );
 263
 264         //
 265         // if all points are coplanar, set all normals to that plane
 266         //
 267         idVec3          extent[3];
 268         float           offset;
 269
 270         extent[0] = verts[width - 1].xyz - verts[0].xyz;
 271         extent[1] = verts[(height-1) * width + width - 1].xyz - verts[0].xyz;
 272         extent[2] = verts[(height-1) * width].xyz - verts[0].xyz;
 273
 274         norm = extent[0].Cross( extent[1] );
 275         if ( norm.LengthSqr() == 0.0f ) {
 276                 norm = extent[0].Cross( extent[2] );
 277                 if ( norm.LengthSqr() == 0.0f ) {
 278                         norm = extent[1].Cross( extent[2] );
 279                 }
 280         }
 281
 282         // wrapped patched may not get a valid normal here
 283         if ( norm.Normalize() != 0.0f ) {
 284
 285                 offset = verts[0].xyz * norm;
 286                 for ( i = 1; i < width * height; i++ ) {
 287                         float d = verts[i].xyz * norm;
 288                         if ( idMath::Fabs( d - offset ) > COPLANAR_EPSILON ) {
 289                                 break;
 290                         }
 291                 }
 292
 293                 if ( i == width * height ) {
 294                         // all are coplanar
 295                         for ( i = 0; i < width * height; i++ ) {
 296                                 verts[i].normal = norm;
 297                         }
 298                         return;
 299                 }
 300         }
 301
 302         // check for wrapped edge cases, which should smooth across themselves
 303         wrapWidth = false;
 304         for ( i = 0; i < height; i++ ) {
 305                 delta = verts[i * width].xyz - verts[i * width + width-1].xyz;
 306                 if ( delta.LengthSqr() > Square( 1.0f ) ) {
 307                         break;
 308                 }
 309         }
 310         if ( i == height ) {
 311                 wrapWidth = true;
 312         }
 313
 314         wrapHeight = false;
 315         for ( i = 0; i < width; i++ ) {
 316                 delta = verts[i].xyz - verts[(height-1) * width + i].xyz;
 317                 if ( delta.LengthSqr() > Square( 1.0f ) ) {
 318                         break;
 319                 }
 320         }
 321         if ( i == width ) {
 322                 wrapHeight = true;
 323         }
 324
 325         for ( i = 0; i < width; i++ ) {
 326                 for ( j = 0; j < height; j++ ) {
 327                         count = 0;
 328                         base = verts[j * width + i].xyz;
 329                         for ( k = 0; k < 8; k++ ) {
 330                                 around[k] = vec3_origin;
 331                                 good[k] = false;
 332
 333                                 for ( dist = 1; dist <= 3; dist++ ) {
 334                                         x = i + neighbors[k][0] * dist;
 335                                         y = j + neighbors[k][1] * dist;
 336                                         if ( wrapWidth ) {
 337                                                 if ( x < 0 ) {
 338                                                         x = width - 1 + x;
 339                                                 } else if ( x >= width ) {
 340                                                         x = 1 + x - width;
 341                                                 }
 342                                         }
 343                                         if ( wrapHeight ) {
 344                                                 if ( y < 0 ) {
 345                                                         y = height - 1 + y;
 346                                                 } else if ( y >= height ) {
 347                                                         y = 1 + y - height;
 348                                                 }
 349                                         }
 350
 351                                         if ( x < 0 || x >= width || y < 0 || y >= height ) {
 352                                                 break;                                  // edge of patch
 353                                         }
 354                                         temp = verts[y * width + x].xyz - base;
 355                                         if ( temp.Normalize() == 0.0f ) {
 356                                                 continue;                               // degenerate edge, get more dist
 357                                         } else {
 358                                                 good[k] = true;
 359                                                 around[k] = temp;
 360                                                 break;                                  // good edge
 361                                         }
 362                                 }
 363                         }
 364
 365                         sum = vec3_origin;
 366                         for ( k = 0; k < 8; k++ ) {
 367                                 if ( !good[k] || !good[(k+1)&7] ) {
 368                                         continue;       // didn't get two points
 369                                 }
 370                                 norm = around[(k+1)&7].Cross( around[k] );
 371                                 if ( norm.Normalize() == 0.0f ) {
 372                                         continue;
 373                                 }
 374                                 sum += norm;
 375                                 count++;
 376                         }
 377                         if ( count == 0 ) {
 378                                 //idLib::common->Printf("bad normal\n");
 379                                 count = 1;
 380                         }
 381                         verts[j * width + i].normal = sum;
 382                         verts[j * width + i].normal.Normalize();
 383                 }
 384         }
 385 }
 386
 387 /*
 388 =================
 389 idSurface_Patch::GenerateIndexes
 390 =================
 391 */
 392 void idSurface_Patch::GenerateIndexes( void ) {
 393         int i, j, v1, v2, v3, v4, index;
 394
 395         indexes.SetNum( (width-1) * (height-1) * 2 * 3, false );
 396         index = 0;
 397         for ( i = 0; i < width - 1; i++ ) {
 398                 for ( j = 0; j < height - 1; j++ ) {
 399                         v1 = j * width + i;
 400                         v2 = v1 + 1;
 401                         v3 = v1 + width + 1;
 402                         v4 = v1 + width;
 403                         indexes[index++] = v1;
 404                         indexes[index++] = v3;
 405                         indexes[index++] = v2;
 406                         indexes[index++] = v1;
 407                         indexes[index++] = v4;
 408                         indexes[index++] = v3;
 409                 }
 410         }
 411
 412         GenerateEdgeIndexes();
 413 }
 414
 415 /*
 416 ===============
 417 idSurface_Patch::SampleSinglePatchPoint
 418 ===============
 419 */
 420 void idSurface_Patch::SampleSinglePatchPoint( const idDrawVert ctrl[3][3], float u, float v, idDrawVert *out ) const {
 421         float   vCtrl[3][8];
 422         int             vPoint;
 423         int             axis;
 424
 425         // find the control points for the v coordinate
 426         for ( vPoint = 0; vPoint < 3; vPoint++ ) {
 427                 for ( axis = 0; axis < 8; axis++ ) {
 428                         float a, b, c;
 429                         float qA, qB, qC;
 430                         if ( axis < 3 ) {
 431                                 a = ctrl[0][vPoint].xyz[axis];
 432                                 b = ctrl[1][vPoint].xyz[axis];
 433                                 c = ctrl[2][vPoint].xyz[axis];
 434                         } else if ( axis < 6 ) {
 435                                 a = ctrl[0][vPoint].normal[axis-3];
 436                                 b = ctrl[1][vPoint].normal[axis-3];
 437                                 c = ctrl[2][vPoint].normal[axis-3];
 438                         } else {
 439                                 a = ctrl[0][vPoint].st[axis-6];
 440                                 b = ctrl[1][vPoint].st[axis-6];
 441                                 c = ctrl[2][vPoint].st[axis-6];
 442                         }
 443                         qA = a - 2.0f * b + c;
 444                         qB = 2.0f * b - 2.0f * a;
 445                         qC = a;
 446                         vCtrl[vPoint][axis] = qA * u * u + qB * u + qC;
 447                 }
 448         }
 449
 450         // interpolate the v value
 451         for ( axis = 0; axis < 8; axis++ ) {
 452                 float a, b, c;
 453                 float qA, qB, qC;
 454
 455                 a = vCtrl[0][axis];
 456                 b = vCtrl[1][axis];
 457                 c = vCtrl[2][axis];
 458                 qA = a - 2.0f * b + c;
 459                 qB = 2.0f * b - 2.0f * a;
 460                 qC = a;
 461
 462                 if ( axis < 3 ) {
 463                         out->xyz[axis] = qA * v * v + qB * v + qC;
 464                 } else if ( axis < 6 ) {
 465                         out->normal[axis-3] = qA * v * v + qB * v + qC;
 466                 } else {
 467                         out->st[axis-6] = qA * v * v + qB * v + qC;
 468                 }
 469         }
 470 }
 471
 472 /*
 473 ===================
 474 idSurface_Patch::SampleSinglePatch
 475 ===================
 476 */
 477 void idSurface_Patch::SampleSinglePatch( const idDrawVert ctrl[3][3], int baseCol, int baseRow, int width, int horzSub, int vertSub, idDrawVert *outVerts ) const {
 478         int             i, j;
 479         float   u, v;
 480
 481         horzSub++;
 482         vertSub++;
 483         for ( i = 0; i < horzSub; i++ ) {
 484                 for ( j = 0; j < vertSub; j++ ) {
 485                         u = (float) i / ( horzSub - 1 );
 486                         v = (float) j / ( vertSub - 1 );
 487                         SampleSinglePatchPoint( ctrl, u, v, &outVerts[((baseRow + j) * width) + i + baseCol] );
 488                 }
 489         }
 490 }
 491
 492 /*
 493 =================
 494 idSurface_Patch::SubdivideExplicit
 495 =================
 496 */
 497 void idSurface_Patch::SubdivideExplicit( int horzSubdivisions, int vertSubdivisions, bool genNormals, bool removeLinear ) {
 498         int i, j, k, l;
 499         idDrawVert sample[3][3];
 500         int outWidth = ((width - 1) / 2 * horzSubdivisions) + 1;
 501         int outHeight = ((height - 1) / 2 * vertSubdivisions) + 1;
 502         idDrawVert *dv = new idDrawVert[ outWidth * outHeight ];
 503
 504         // generate normals for the control mesh
 505         if ( genNormals ) {
 506                 GenerateNormals();
 507         }
 508
 509         int baseCol = 0;
 510         for ( i = 0; i + 2 < width; i += 2 ) {
 511                 int baseRow = 0;
 512                 for ( j = 0; j + 2 < height; j += 2 ) {
 513                         for ( k = 0; k < 3; k++ ) {
 514                                 for ( l = 0; l < 3; l++ ) {
 515                                         sample[k][l] = verts[ ((j + l) * width) + i + k ];
 516                                 }
 517                         }
 518                         SampleSinglePatch( sample, baseCol, baseRow, outWidth, horzSubdivisions, vertSubdivisions, dv );
 519                         baseRow += vertSubdivisions;
 520                 }
 521                 baseCol += horzSubdivisions;
 522         }
 523         verts.SetNum( outWidth * outHeight );
 524         for ( i = 0; i < outWidth * outHeight; i++ ) {
 525                 verts[i] = dv[i];
 526         }
 527
 528         delete[] dv;
 529
 530         width = maxWidth = outWidth;
 531         height = maxHeight = outHeight;
 532         expanded = false;
 533
 534         if ( removeLinear ) {
 535                 Expand();
 536                 RemoveLinearColumnsRows();
 537                 Collapse();
 538         }
 539
 540         // normalize all the lerped normals
 541         if ( genNormals ) {
 542                 for ( i = 0; i < width * height; i++ ) {
 543                         verts[i].normal.Normalize();
 544                 }
 545         }
 546
 547         GenerateIndexes();
 548 }
 549
 550 /*
 551 =================
 552 idSurface_Patch::Subdivide
 553 =================
 554 */
 555 void idSurface_Patch::Subdivide( float maxHorizontalError, float maxVerticalError, float maxLength, bool genNormals ) {
 556         int                     i, j, k, l;
 557         idDrawVert      prev, next, mid;
 558         idVec3          prevxyz, nextxyz, midxyz;
 559         idVec3          delta;
 560         float           maxHorizontalErrorSqr, maxVerticalErrorSqr, maxLengthSqr;
 561
 562         // generate normals for the control mesh
 563         if ( genNormals ) {
 564                 GenerateNormals();
 565         }
 566
 567         maxHorizontalErrorSqr = Square( maxHorizontalError );
 568         maxVerticalErrorSqr = Square( maxVerticalError );
 569         maxLengthSqr = Square( maxLength );
 570
 571         Expand();
 572
 573         // horizontal subdivisions
 574         for ( j = 0; j + 2 < width; j += 2 ) {
 575                 // check subdivided midpoints against control points
 576                 for ( i = 0; i < height; i++ ) {
 577                         for ( l = 0; l < 3; l++ ) {
 578                                 prevxyz[l] = verts[i*maxWidth + j+1].xyz[l] - verts[i*maxWidth + j  ].xyz[l];
 579                                 nextxyz[l] = verts[i*maxWidth + j+2].xyz[l] - verts[i*maxWidth + j+1].xyz[l];
 580                                 midxyz[l] = (verts[i*maxWidth + j  ].xyz[l] + verts[i*maxWidth + j+1].xyz[l] * 2.0f +
 581                                                                                                                    verts[i*maxWidth + j+2].xyz[l] ) * 0.25f;
 582                         }
 583
 584                         if ( maxLength > 0.0f ) {
 585                                 // if the span length is too long, force a subdivision
 586                                 if ( prevxyz.LengthSqr() > maxLengthSqr || nextxyz.LengthSqr() > maxLengthSqr ) {
 587                                         break;
 588                                 }
 589                         }
 590                         // see if this midpoint is off far enough to subdivide
 591                         delta = verts[i*maxWidth + j+1].xyz - midxyz;
 592                         if ( delta.LengthSqr() > maxHorizontalErrorSqr ) {
 593                                 break;
 594                         }
 595                 }
 596
 597                 if ( i == height ) {
 598                         continue;       // didn't need subdivision
 599                 }
 600
 601                 if ( width + 2 >= maxWidth ) {
 602                         ResizeExpanded( maxHeight, maxWidth + 4 );
 603                 }
 604
 605                 // insert two columns and replace the peak
 606                 width += 2;
 607
 608                 for ( i = 0; i < height; i++ ) {
 609                         idSurface_Patch::LerpVert( verts[i*maxWidth + j  ], verts[i*maxWidth + j+1], prev );
 610                         idSurface_Patch::LerpVert( verts[i*maxWidth + j+1], verts[i*maxWidth + j+2], next );
 611                         idSurface_Patch::LerpVert( prev, next, mid );
 612
 613                         for ( k = width - 1; k > j + 3; k-- ) {
 614                                 verts[i*maxWidth + k] = verts[i*maxWidth + k-2];
 615                         }
 616                         verts[i*maxWidth + j+1] = prev;
 617                         verts[i*maxWidth + j+2] = mid;
 618                         verts[i*maxWidth + j+3] = next;
 619                 }
 620
 621                 // back up and recheck this set again, it may need more subdivision
 622                 j -= 2;
 623         }
 624
 625         // vertical subdivisions
 626         for ( j = 0; j + 2 < height; j += 2 ) {
 627                 // check subdivided midpoints against control points
 628                 for ( i = 0; i < width; i++ ) {
 629                         for ( l = 0; l < 3; l++ ) {
 630                                 prevxyz[l] = verts[(j+1)*maxWidth + i].xyz[l] - verts[j*maxWidth + i].xyz[l];
 631                                 nextxyz[l] = verts[(j+2)*maxWidth + i].xyz[l] - verts[(j+1)*maxWidth + i].xyz[l];
 632                                 midxyz[l] = (verts[j*maxWidth + i].xyz[l] + verts[(j+1)*maxWidth + i].xyz[l] * 2.0f +
 633                                                                                                                 verts[(j+2)*maxWidth + i].xyz[l] ) * 0.25f;
 634                         }
 635
 636                         if ( maxLength > 0.0f ) {
 637                                 // if the span length is too long, force a subdivision
 638                                 if ( prevxyz.LengthSqr() > maxLengthSqr || nextxyz.LengthSqr() > maxLengthSqr ) {
 639                                         break;
 640                                 }
 641                         }
 642                         // see if this midpoint is off far enough to subdivide
 643                         delta = verts[(j+1)*maxWidth + i].xyz - midxyz;
 644                         if ( delta.LengthSqr() > maxVerticalErrorSqr ) {
 645                                 break;
 646                         }
 647                 }
 648
 649                 if ( i == width ) {
 650                         continue;       // didn't need subdivision
 651                 }
 652
 653                 if ( height + 2 >= maxHeight ) {
 654                         ResizeExpanded( maxHeight + 4, maxWidth );
 655                 }
 656
 657                 // insert two columns and replace the peak
 658                 height += 2;
 659
 660                 for ( i = 0; i < width; i++ ) {
 661                         LerpVert( verts[j*maxWidth + i], verts[(j+1)*maxWidth + i], prev );
 662                         LerpVert( verts[(j+1)*maxWidth + i], verts[(j+2)*maxWidth + i], next );
 663                         LerpVert( prev, next, mid );
 664
 665                         for ( k = height - 1; k > j + 3; k-- ) {
 666                                 verts[k*maxWidth + i] = verts[(k-2)*maxWidth + i];
 667                         }
 668                         verts[(j+1)*maxWidth + i] = prev;
 669                         verts[(j+2)*maxWidth + i] = mid;
 670                         verts[(j+3)*maxWidth + i] = next;
 671                 }
 672
 673                 // back up and recheck this set again, it may need more subdivision
 674                 j -= 2;
 675         }
 676
 677         PutOnCurve();
 678
 679         RemoveLinearColumnsRows();
 680
 681         Collapse();
 682
 683         // normalize all the lerped normals
 684         if ( genNormals ) {
 685                 for ( i = 0; i < width * height; i++ ) {
 686                         verts[i].normal.Normalize();
 687                 }
 688         }
 689
 690         GenerateIndexes();
 691 }