home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / mesh.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  16.9 KB  |  662 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4.  
  5. /*
  6. ===============================================================
  7.  
  8. MESH SUBDIVISION
  9.  
  10. ===============================================================
  11. */
  12.  
  13.  
  14. int    originalWidths[MAX_EXPANDED_AXIS];
  15. int    originalHeights[MAX_EXPANDED_AXIS];
  16.  
  17. int    neighbors[8][2] = {
  18.     {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
  19. };
  20.  
  21. /*
  22. ============
  23. LerpDrawVert
  24. ============
  25. */
  26. void LerpDrawVert( drawVert_t *a, drawVert_t *b, drawVert_t *out ) {
  27.     out->xyz[0] = 0.5 * (a->xyz[0] + b->xyz[0]);
  28.     out->xyz[1] = 0.5 * (a->xyz[1] + b->xyz[1]);
  29.     out->xyz[2] = 0.5 * (a->xyz[2] + b->xyz[2]);
  30.  
  31.     out->st[0] = 0.5 * (a->st[0] + b->st[0]);
  32.     out->st[1] = 0.5 * (a->st[1] + b->st[1]);
  33.  
  34.     out->lightmap[0] = 0.5 * (a->lightmap[0] + b->lightmap[0]);
  35.     out->lightmap[1] = 0.5 * (a->lightmap[1] + b->lightmap[1]);
  36.  
  37.     out->color[0] = (a->color[0] + b->color[0]) >> 1;
  38.     out->color[1] = (a->color[1] + b->color[1]) >> 1;
  39.     out->color[2] = (a->color[2] + b->color[2]) >> 1;
  40.     out->color[3] = (a->color[3] + b->color[3]) >> 1;
  41. }
  42.  
  43.  
  44. void FreeMesh( mesh_t *m ) {
  45.     free( m->verts );
  46.     free( m );
  47. }
  48.  
  49. void PrintMesh( mesh_t *m ) {
  50.     int        i, j;
  51.  
  52.     for ( i = 0 ; i < m->height ; i++ ) {
  53.         for ( j = 0 ; j < m->width ; j++ ) {
  54.             _printf("(%5.2f %5.2f %5.2f) "
  55.                 , m->verts[i*m->width+j].xyz[0]
  56.                 , m->verts[i*m->width+j].xyz[1]
  57.                 , m->verts[i*m->width+j].xyz[2] );
  58.         }
  59.         _printf("\n");
  60.     }
  61. }
  62.  
  63.  
  64. mesh_t *CopyMesh( mesh_t *mesh ) {
  65.     mesh_t    *out;
  66.     int        size;
  67.  
  68.     out = malloc( sizeof( *out ) );
  69.     out->width = mesh->width;
  70.     out->height = mesh->height;
  71.  
  72.     size = out->width * out->height * sizeof( *out->verts );
  73.     out->verts = malloc( size );
  74.     memcpy( out->verts, mesh->verts, size );
  75.  
  76.     return out;
  77. }
  78.  
  79.  
  80. /*
  81. =================
  82. TransposeMesh
  83.  
  84. Returns a transposed copy of the mesh, freeing the original
  85. =================
  86. */
  87. mesh_t *TransposeMesh( mesh_t *in ) {
  88.     int            w, h;
  89.     mesh_t        *out;
  90.  
  91.     out = malloc( sizeof( *out ) );
  92.     out->width = in->height;
  93.     out->height = in->width;
  94.     out->verts = malloc( out->width * out->height * sizeof( drawVert_t ) );
  95.  
  96.     for ( h = 0 ; h < in->height ; h++ ) {
  97.         for ( w = 0 ; w < in->width ; w++ ) {
  98.             out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];
  99.         }
  100.     }
  101.  
  102.     FreeMesh( in );
  103.  
  104.     return out;
  105. }
  106.  
  107. void InvertMesh( mesh_t *in ) {
  108.     int            w, h;
  109.     drawVert_t    temp;
  110.  
  111.     for ( h = 0 ; h < in->height ; h++ ) {
  112.         for ( w = 0 ; w < in->width / 2 ; w++ ) {
  113.             temp = in->verts[ h * in->width + w ];
  114.             in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];
  115.             in->verts[ h * in->width + in->width - 1 - w ] = temp;
  116.         }
  117.     }
  118. }
  119.  
  120. /*
  121. =================
  122. MakeMeshNormals
  123.  
  124. =================
  125. */
  126. void MakeMeshNormals( mesh_t in ) {
  127.     int        i, j, k, dist;
  128.     vec3_t    normal;
  129.     vec3_t    sum;
  130.     int        count;
  131.     vec3_t    base;
  132.     vec3_t    delta;
  133.     int        x, y;
  134.     drawVert_t    *dv;
  135.     vec3_t        around[8], temp;
  136.     qboolean    good[8];
  137.     qboolean    wrapWidth, wrapHeight;
  138.     float        len;
  139.  
  140.     wrapWidth = qfalse;
  141.     for ( i = 0 ; i < in.height ; i++ ) {
  142.         VectorSubtract( in.verts[i*in.width].xyz, 
  143.             in.verts[i*in.width+in.width-1].xyz, delta );
  144.         len = VectorLength( delta );
  145.         if ( len > 1.0 ) {
  146.             break;
  147.         }
  148.     }
  149.     if ( i == in.height ) {
  150.         wrapWidth = qtrue;
  151.     }
  152.  
  153.     wrapHeight = qfalse;
  154.     for ( i = 0 ; i < in.width ; i++ ) {
  155.         VectorSubtract( in.verts[i].xyz, 
  156.             in.verts[i + (in.height-1)*in.width].xyz, delta );
  157.         len = VectorLength( delta );
  158.         if ( len > 1.0 ) {
  159.             break;
  160.         }
  161.     }
  162.     if ( i == in.width) {
  163.         wrapHeight = qtrue;
  164.     }
  165.  
  166.  
  167.     for ( i = 0 ; i < in.width ; i++ ) {
  168.         for ( j = 0 ; j < in.height ; j++ ) {
  169.             count = 0;
  170.             dv = &in.verts[j*in.width+i];
  171.             VectorCopy( dv->xyz, base );
  172.             for ( k = 0 ; k < 8 ; k++ ) {
  173.                 VectorClear( around[k] );
  174.                 good[k] = qfalse;
  175.  
  176.                 for ( dist = 1 ; dist <= 3 ; dist++ ) {
  177.                     x = i + neighbors[k][0] * dist;
  178.                     y = j + neighbors[k][1] * dist;
  179.                     if ( wrapWidth ) {
  180.                         if ( x < 0 ) {
  181.                             x = in.width - 1 + x;
  182.                         } else if ( x >= in.width ) {
  183.                             x = 1 + x - in.width;
  184.                         }
  185.                     }
  186.                     if ( wrapHeight ) {
  187.                         if ( y < 0 ) {
  188.                             y = in.height - 1 + y;
  189.                         } else if ( y >= in.height ) {
  190.                             y = 1 + y - in.height;
  191.                         }
  192.                     }
  193.  
  194.                     if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
  195.                         break;                    // edge of patch
  196.                     }
  197.                     VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );
  198.                     if ( VectorNormalize( temp, temp ) == 0 ) {
  199.                         continue;                // degenerate edge, get more dist
  200.                     } else {
  201.                         good[k] = qtrue;
  202.                         VectorCopy( temp, around[k] );
  203.                         break;                    // good edge
  204.                     }
  205.                 }
  206.             }
  207.  
  208.             VectorClear( sum );
  209.             for ( k = 0 ; k < 8 ; k++ ) {
  210.                 if ( !good[k] || !good[(k+1)&7] ) {
  211.                     continue;    // didn't get two points
  212.                 }
  213.                 CrossProduct( around[(k+1)&7], around[k], normal );
  214.                 if ( VectorNormalize( normal, normal ) == 0 ) {
  215.                     continue;
  216.                 }
  217.                 VectorAdd( normal, sum, sum );
  218.                 count++;
  219.             }
  220.             if ( count == 0 ) {
  221. //_printf("bad normal\n");
  222.                 count = 1;
  223.             }
  224.             VectorNormalize( sum, dv->normal );
  225.         }
  226.     }
  227. }
  228.  
  229. /*
  230. =================
  231. PutMeshOnCurve
  232.  
  233. Drops the aproximating points onto the curve
  234. =================
  235. */
  236. void PutMeshOnCurve( mesh_t in ) {
  237.     int        i, j, l;
  238.     float    prev, next;
  239.  
  240.     // put all the aproximating points on the curve
  241.     for ( i = 0 ; i < in.width ; i++ ) {
  242.         for ( j = 1 ; j < in.height ; j += 2 ) {
  243.             for ( l = 0 ; l < 3 ; l++ ) {
  244.                 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;
  245.                 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;
  246.                 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
  247.             }
  248.         }
  249.     }
  250.  
  251.     for ( j = 0 ; j < in.height ; j++ ) {
  252.         for ( i = 1 ; i < in.width ; i += 2 ) {
  253.             for ( l = 0 ; l < 3 ; l++ ) {
  254.                 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;
  255.                 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;
  256.                 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
  257.             }
  258.         }
  259.     }
  260. }
  261.  
  262.  
  263. /*
  264. =================
  265. SubdivideMesh
  266.  
  267. =================
  268. */
  269. mesh_t *SubdivideMesh( mesh_t in, float maxError, float minLength ) {
  270.     int            i, j, k, l;
  271.     drawVert_t    prev, next, mid;
  272.     vec3_t        prevxyz, nextxyz, midxyz;
  273.     vec3_t        delta;
  274.     float        len;
  275.     mesh_t        out;
  276.     drawVert_t    expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
  277.  
  278.     out.width = in.width;
  279.     out.height = in.height;
  280.  
  281.     for ( i = 0 ; i < in.width ; i++ ) {
  282.         for ( j = 0 ; j < in.height ; j++ ) {
  283.             expand[j][i] = in.verts[j*in.width+i];
  284.         }
  285.     }
  286.  
  287.     for ( i = 0 ; i < in.height ; i++ ) {
  288.         originalHeights[i] = i;
  289.     }
  290.     for ( i = 0 ; i < in.width ; i++ ) {
  291.         originalWidths[i] = i;
  292.     }
  293.  
  294.     // horizontal subdivisions
  295.     for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
  296.         // check subdivided midpoints against control points
  297.         for ( i = 0 ; i < out.height ; i++ ) {
  298.             for ( l = 0 ; l < 3 ; l++ ) {
  299.                 prevxyz[l] = expand[i][j+1].xyz[l] - expand[i][j].xyz[l]; 
  300.                 nextxyz[l] = expand[i][j+2].xyz[l] - expand[i][j+1].xyz[l]; 
  301.                 midxyz[l] = (expand[i][j].xyz[l] + expand[i][j+1].xyz[l] * 2
  302.                         + expand[i][j+2].xyz[l] ) * 0.25;
  303.             }
  304.  
  305.             // if the span length is too long, force a subdivision
  306.             if ( VectorLength( prevxyz ) > minLength 
  307.                 || VectorLength( nextxyz ) > minLength ) {
  308.                 break;
  309.             }
  310.  
  311.             // see if this midpoint is off far enough to subdivide
  312.             VectorSubtract( expand[i][j+1].xyz, midxyz, delta );
  313.             len = VectorLength( delta );
  314.             if ( len > maxError ) {
  315.                 break;
  316.             }
  317.         }
  318.  
  319.         if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
  320.             break;    // can't subdivide any more
  321.         }
  322.  
  323.         if ( i == out.height ) {
  324.             continue;    // didn't need subdivision
  325.         }
  326.  
  327.         // insert two columns and replace the peak
  328.         out.width += 2;
  329.  
  330.         for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
  331.             originalWidths[k] = originalWidths[k-2];
  332.         }
  333.         originalWidths[j+3] = originalWidths[j+1];
  334.         originalWidths[j+2] = originalWidths[j+1];
  335.         originalWidths[j+1] = originalWidths[j];
  336.  
  337.         for ( i = 0 ; i < out.height ; i++ ) {
  338.             LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev );
  339.             LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next );
  340.             LerpDrawVert( &prev, &next, &mid );
  341.  
  342.             for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
  343.                 expand[i][k] = expand[i][k-2];
  344.             }
  345.             expand[i][j + 1] = prev;
  346.             expand[i][j + 2] = mid;
  347.             expand[i][j + 3] = next;
  348.         }
  349.  
  350.         // back up and recheck this set again, it may need more subdivision
  351.         j -= 2;
  352.  
  353.     }
  354.  
  355.     // vertical subdivisions
  356.     for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
  357.         // check subdivided midpoints against control points
  358.         for ( i = 0 ; i < out.width ; i++ ) {
  359.             for ( l = 0 ; l < 3 ; l++ ) {
  360.                 prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l]; 
  361.                 nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l]; 
  362.                 midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2
  363.                         + expand[j+2][i].xyz[l] ) * 0.25;
  364.             }
  365.  
  366.             // if the span length is too long, force a subdivision
  367.             if ( VectorLength( prevxyz ) > minLength 
  368.                 || VectorLength( nextxyz ) > minLength ) {
  369.                 break;
  370.             }
  371.             // see if this midpoint is off far enough to subdivide
  372.             VectorSubtract( expand[j+1][i].xyz, midxyz, delta );
  373.             len = VectorLength( delta );
  374.             if ( len > maxError ) {
  375.                 break;
  376.             }
  377.         }
  378.  
  379.         if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
  380.             break;    // can't subdivide any more
  381.         }
  382.  
  383.         if ( i == out.width ) {
  384.             continue;    // didn't need subdivision
  385.         }
  386.  
  387.         // insert two columns and replace the peak
  388.         out.height += 2;
  389.  
  390.         for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
  391.             originalHeights[k] = originalHeights[k-2];
  392.         }
  393.         originalHeights[j+3] = originalHeights[j+1];
  394.         originalHeights[j+2] = originalHeights[j+1];
  395.         originalHeights[j+1] = originalHeights[j];
  396.  
  397.         for ( i = 0 ; i < out.width ; i++ ) {
  398.             LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev );
  399.             LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next );
  400.             LerpDrawVert( &prev, &next, &mid );
  401.  
  402.             for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
  403.                 expand[k][i] = expand[k-2][i];
  404.             }
  405.             expand[j+1][i] = prev;
  406.             expand[j+2][i] = mid;
  407.             expand[j+3][i] = next;
  408.         }
  409.  
  410.         // back up and recheck this set again, it may need more subdivision
  411.         j -= 2;
  412.  
  413.     }
  414.  
  415.     // collapse the verts
  416.  
  417.     out.verts = &expand[0][0];
  418.     for ( i = 1 ; i < out.height ; i++ ) {
  419.         memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) );
  420.     }
  421.  
  422.     return CopyMesh(&out);
  423. }
  424.  
  425. /*
  426. ================
  427. ProjectPointOntoVector
  428. ================
  429. */
  430. void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj )
  431. {
  432.     vec3_t pVec, vec;
  433.  
  434.     VectorSubtract( point, vStart, pVec );
  435.     VectorSubtract( vEnd, vStart, vec );
  436.     VectorNormalize( vec, vec );
  437.     // project onto the directional vector for this segment
  438.     VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );
  439. }
  440.  
  441. /*
  442. ================
  443. RemoveLinearMeshColumsRows
  444. ================
  445. */
  446. mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {
  447.     int i, j, k;
  448.     float len, maxLength;
  449.     vec3_t proj, dir;
  450.     mesh_t out;
  451.     drawVert_t    expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
  452.  
  453.     out.width = in->width;
  454.     out.height = in->height;
  455.  
  456.     for ( i = 0 ; i < in->width ; i++ ) {
  457.         for ( j = 0 ; j < in->height ; j++ ) {
  458.             expand[j][i] = in->verts[j*in->width+i];
  459.         }
  460.     }
  461.  
  462.     for ( j = 1 ; j < out.width - 1; j++ ) {
  463.         maxLength = 0;
  464.         for ( i = 0 ; i < out.height ; i++ ) {
  465.             ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj);
  466.             VectorSubtract(expand[i][j].xyz, proj, dir);
  467.             len = VectorLength(dir);
  468.             if (len > maxLength) {
  469.                 maxLength = len;
  470.             }
  471.         }
  472.         if (maxLength < 0.1)
  473.         {
  474.             out.width--;
  475.             for ( i = 0 ; i < out.height ; i++ ) {
  476.                 for (k = j; k < out.width; k++) {
  477.                     expand[i][k] = expand[i][k+1];
  478.                 }
  479.             }
  480.             for (k = j; k < out.width; k++) {
  481.                 originalWidths[k] = originalWidths[k+1];
  482.             }
  483.             j--;
  484.         }
  485.     }
  486.     for ( j = 1 ; j < out.height - 1; j++ ) {
  487.         maxLength = 0;
  488.         for ( i = 0 ; i < out.width ; i++ ) {
  489.             ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj);
  490.             VectorSubtract(expand[j][i].xyz, proj, dir);
  491.             len = VectorLength(dir);
  492.             if (len > maxLength) {
  493.                 maxLength = len;
  494.             }
  495.         }
  496.         if (maxLength < 0.1)
  497.         {
  498.             out.height--;
  499.             for ( i = 0 ; i < out.width ; i++ ) {
  500.                 for (k = j; k < out.height; k++) {
  501.                     expand[k][i] = expand[k+1][i];
  502.                 }
  503.             }
  504.             for (k = j; k < out.height; k++) {
  505.                 originalHeights[k] = originalHeights[k+1];
  506.             }
  507.             j--;
  508.         }
  509.     }
  510.     // collapse the verts
  511.     out.verts = &expand[0][0];
  512.     for ( i = 1 ; i < out.height ; i++ ) {
  513.         memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) );
  514.     }
  515.  
  516.     return CopyMesh(&out);
  517. }
  518.  
  519. /*
  520. ============
  521. LerpDrawVertAmount
  522. ============
  523. */
  524. void LerpDrawVertAmount( drawVert_t *a, drawVert_t *b, float amount, drawVert_t *out ) {
  525.     out->xyz[0] = a->xyz[0] + amount * (b->xyz[0] - a->xyz[0]);
  526.     out->xyz[1] = a->xyz[1] + amount * (b->xyz[1] - a->xyz[1]);
  527.     out->xyz[2] = a->xyz[2] + amount * (b->xyz[2] - a->xyz[2]);
  528.  
  529.     out->st[0] = a->st[0] + amount * (b->st[0] - a->st[0]);
  530.     out->st[1] = a->st[1] + amount * (b->st[1] - a->st[1]);
  531.  
  532.     out->lightmap[0] = a->lightmap[0] + amount * (b->lightmap[0] - a->lightmap[0]);
  533.     out->lightmap[1] = a->lightmap[1] + amount * (b->lightmap[1] - a->lightmap[1]);
  534.  
  535.     out->color[0] = a->color[0] + amount * (b->color[0] - a->color[0]);
  536.     out->color[1] = a->color[1] + amount * (b->color[1] - a->color[1]);
  537.     out->color[2] = a->color[2] + amount * (b->color[2] - a->color[2]);
  538.     out->color[3] = a->color[3] + amount * (b->color[3] - a->color[3]);
  539.  
  540.     out->normal[0] = a->normal[0] + amount * (b->normal[0] - a->normal[0]);
  541.     out->normal[1] = a->normal[1] + amount * (b->normal[1] - a->normal[1]);
  542.     out->normal[2] = a->normal[2] + amount * (b->normal[2] - a->normal[2]);
  543.     VectorNormalize(out->normal, out->normal);
  544. }
  545.  
  546. /*
  547. =================
  548. SubdivideMeshQuads
  549. =================
  550. */
  551. mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int widthtable[], int heighttable[]) {
  552.     int            i, j, k, w, h, maxsubdivisions, subdivisions;
  553.     vec3_t        dir;
  554.     float        length, maxLength, amount;
  555.     mesh_t        out;
  556.     drawVert_t    expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
  557.  
  558.     out.width = in->width;
  559.     out.height = in->height;
  560.  
  561.     for ( i = 0 ; i < in->width ; i++ ) {
  562.         for ( j = 0 ; j < in->height ; j++ ) {
  563.             expand[j][i] = in->verts[j*in->width+i];
  564.         }
  565.     }
  566.  
  567.     if (maxsize > MAX_EXPANDED_AXIS)
  568.         Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS");
  569.  
  570.     // horizontal subdivisions
  571.  
  572.     maxsubdivisions = (maxsize - in->width) / (in->width - 1);
  573.  
  574.     for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) {
  575.         maxLength = 0;
  576.         for ( i = 0 ; i < out.height ; i++ ) {
  577.             VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir);
  578.             length = VectorLength( dir );
  579.             if (length > maxLength) {
  580.                 maxLength = length;
  581.             }
  582.         }
  583.         
  584.         subdivisions = (int) (maxLength / minLength);
  585.         if (subdivisions > maxsubdivisions)
  586.             subdivisions = maxsubdivisions;
  587.  
  588.         widthtable[w] = subdivisions + 1;
  589.         if (subdivisions <= 0)
  590.             continue;
  591.  
  592.         out.width += subdivisions;
  593.  
  594.         for ( k = out.width - 1; k >= j + subdivisions; k-- ) {
  595.             originalWidths[k] = originalWidths[k-subdivisions];
  596.         }
  597.         for (k = 1; k <= subdivisions; k++) {
  598.             originalWidths[j+k] = originalWidths[j];
  599.         }
  600.  
  601.         for ( i = 0 ; i < out.height ; i++ ) {
  602.             for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {
  603.                 expand[i][k] = expand[i][k-subdivisions];
  604.             }
  605.             for (k = 1; k <= subdivisions; k++)
  606.             {
  607.                 amount = (float) k / (subdivisions + 1);
  608.                 LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]);
  609.             }
  610.         }
  611.     }
  612.  
  613.     maxsubdivisions = (maxsize - in->height) / (in->height - 1);
  614.  
  615.     for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) {
  616.         maxLength = 0;
  617.         for ( i = 0 ; i < out.width ; i++ ) {
  618.             VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir);
  619.             length = VectorLength( dir );
  620.             if (length  > maxLength) {
  621.                 maxLength = length;
  622.             }
  623.         }
  624.         
  625.         subdivisions = (int) (maxLength / minLength);
  626.         if (subdivisions > maxsubdivisions)
  627.             subdivisions = maxsubdivisions;
  628.  
  629.         heighttable[h] = subdivisions + 1;
  630.         if (subdivisions <= 0)
  631.             continue;
  632.  
  633.         out.height += subdivisions;
  634.  
  635.         for ( k = out.height - 1; k >= j + subdivisions; k-- ) {
  636.             originalHeights[k] = originalHeights[k-subdivisions];
  637.         }
  638.         for (k = 1; k <= subdivisions; k++) {
  639.             originalHeights[j+k] = originalHeights[j];
  640.         }
  641.  
  642.         for ( i = 0 ; i < out.width ; i++ ) {
  643.             for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {
  644.                 expand[k][i] = expand[k-subdivisions][i];
  645.             }
  646.             for (k = 1; k <= subdivisions; k++)
  647.             {
  648.                 amount = (float) k / (subdivisions + 1);
  649.                 LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]);
  650.             }
  651.         }
  652.     }
  653.  
  654.     // collapse the verts
  655.     out.verts = &expand[0][0];
  656.     for ( i = 1 ; i < out.height ; i++ ) {
  657.         memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) );
  658.     }
  659.  
  660.     return CopyMesh(&out);
  661. }
  662.