1 /* -------------------------------------------------------------------------------
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
6 This file is part of GtkRadiant.
8 GtkRadiant is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 GtkRadiant is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GtkRadiant; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 ----------------------------------------------------------------------------------
24 This code has been altered significantly from its original form, to support
25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
27 ------------------------------------------------------------------------------- */
43 returns an 50/50 interpolated vert
46 void LerpDrawVert( bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *out )
51 out->xyz[ 0 ] = 0.5 * (a->xyz[ 0 ] + b->xyz[ 0 ]);
52 out->xyz[ 1 ] = 0.5 * (a->xyz[ 1 ] + b->xyz[ 1 ]);
53 out->xyz[ 2 ] = 0.5 * (a->xyz[ 2 ] + b->xyz[ 2 ]);
55 out->st[ 0 ] = 0.5 * (a->st[ 0 ] + b->st[ 0 ]);
56 out->st[ 1 ] = 0.5 * (a->st[ 1 ] + b->st[ 1 ]);
58 for( k = 0; k < MAX_LIGHTMAPS; k++ )
60 out->lightmap[ k ][ 0 ] = 0.5f * (a->lightmap[ k ][ 0 ] + b->lightmap[ k ][ 0 ]);
61 out->lightmap[ k ][ 1 ] = 0.5f * (a->lightmap[ k ][ 1 ] + b->lightmap[ k ][ 1 ]);
62 out->color[ k ][ 0 ] = (a->color[ k ][ 0 ] + b->color[ k ][ 0 ]) >> 1;
63 out->color[ k ][ 1 ] = (a->color[ k ][ 1 ] + b->color[ k ][ 1 ]) >> 1;
64 out->color[ k ][ 2 ] = (a->color[ k ][ 2 ] + b->color[ k ][ 2 ]) >> 1;
65 out->color[ k ][ 3 ] = (a->color[ k ][ 3 ] + b->color[ k ][ 3 ]) >> 1;
68 /* ydnar: added normal interpolation */
69 out->normal[ 0 ] = 0.5f * (a->normal[ 0 ] + b->normal[ 0 ]);
70 out->normal[ 1 ] = 0.5f * (a->normal[ 1 ] + b->normal[ 1 ]);
71 out->normal[ 2 ] = 0.5f * (a->normal[ 2 ] + b->normal[ 2 ]);
73 /* if the interpolant created a bogus normal, just copy the normal from a */
74 if( VectorNormalize( out->normal, out->normal ) == 0 )
75 VectorCopy( a->normal, out->normal );
82 returns a biased interpolated vert
85 void LerpDrawVertAmount( bspDrawVert_t *a, bspDrawVert_t *b, float amount, bspDrawVert_t *out )
90 out->xyz[ 0 ] = a->xyz[ 0 ] + amount * (b->xyz[ 0 ] - a->xyz[ 0 ]);
91 out->xyz[ 1 ] = a->xyz[ 1 ] + amount * (b->xyz[ 1 ] - a->xyz[ 1 ]);
92 out->xyz[ 2 ] = a->xyz[ 2 ] + amount * (b->xyz[ 2 ] - a->xyz[ 2 ]);
94 out->st[ 0 ] = a->st[ 0 ] + amount * (b->st[ 0 ] - a->st[ 0 ]);
95 out->st[ 1 ] = a->st[ 1 ] + amount * (b->st[ 1 ] - a->st[ 1 ]);
97 for( k = 0; k < MAX_LIGHTMAPS; k++ )
99 out->lightmap[ k ][ 0 ] = a->lightmap[ k ][ 0 ] + amount * (b->lightmap[ k ][ 0 ] - a->lightmap[ k ][ 0 ]);
100 out->lightmap[ k ][ 1 ] = a->lightmap[ k ][ 1 ] + amount * (b->lightmap[ k ][ 1 ] - a->lightmap[ k ][ 1 ]);
101 out->color[ k ][ 0 ] = a->color[ k ][ 0 ] + amount * (b->color[ k ][ 0 ] - a->color[ k ][ 0 ]);
102 out->color[ k ][ 1 ] = a->color[ k ][ 1 ] + amount * (b->color[ k ][ 1 ] - a->color[ k ][ 1 ]);
103 out->color[ k ][ 2 ] = a->color[ k ][ 2 ] + amount * (b->color[ k ][ 2 ] - a->color[ k ][ 2 ]);
104 out->color[ k ][ 3 ] = a->color[ k ][ 3 ] + amount * (b->color[ k ][ 3 ] - a->color[ k ][ 3 ]);
107 out->normal[ 0 ] = a->normal[ 0 ] + amount * (b->normal[ 0 ] - a->normal[ 0 ]);
108 out->normal[ 1 ] = a->normal[ 1 ] + amount * (b->normal[ 1 ] - a->normal[ 1 ]);
109 out->normal[ 2 ] = a->normal[ 2 ] + amount * (b->normal[ 2 ] - a->normal[ 2 ]);
111 /* if the interpolant created a bogus normal, just copy the normal from a */
112 if( VectorNormalize( out->normal, out->normal ) == 0 )
113 VectorCopy( a->normal, out->normal );
117 void FreeMesh( mesh_t *m ) {
122 void PrintMesh( mesh_t *m ) {
125 for ( i = 0 ; i < m->height ; i++ ) {
126 for ( j = 0 ; j < m->width ; j++ ) {
127 Sys_Printf("(%5.2f %5.2f %5.2f) "
128 , m->verts[i*m->width+j].xyz[0]
129 , m->verts[i*m->width+j].xyz[1]
130 , m->verts[i*m->width+j].xyz[2] );
137 mesh_t *CopyMesh( mesh_t *mesh ) {
141 out = safe_malloc( sizeof( *out ) );
142 out->width = mesh->width;
143 out->height = mesh->height;
145 size = out->width * out->height * sizeof( *out->verts );
146 out->verts = safe_malloc( size );
147 memcpy( out->verts, mesh->verts, size );
155 returns a transposed copy of the mesh, freeing the original
158 mesh_t *TransposeMesh( mesh_t *in ) {
162 out = safe_malloc( sizeof( *out ) );
163 out->width = in->height;
164 out->height = in->width;
165 out->verts = safe_malloc( out->width * out->height * sizeof( bspDrawVert_t ) );
167 for ( h = 0 ; h < in->height ; h++ ) {
168 for ( w = 0 ; w < in->width ; w++ ) {
169 out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];
178 void InvertMesh( mesh_t *in ) {
182 for ( h = 0 ; h < in->height ; h++ ) {
183 for ( w = 0 ; w < in->width / 2 ; w++ ) {
184 temp = in->verts[ h * in->width + w ];
185 in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];
186 in->verts[ h * in->width + in->width - 1 - w ] = temp;
197 void MakeMeshNormals( mesh_t in )
207 vec3_t around[8], temp;
209 qboolean wrapWidth, wrapHeight;
211 int neighbors[8][2] =
213 {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
218 for ( i = 0 ; i < in.height ; i++ ) {
219 VectorSubtract( in.verts[i*in.width].xyz,
220 in.verts[i*in.width+in.width-1].xyz, delta );
221 len = VectorLength( delta );
226 if ( i == in.height ) {
231 for ( i = 0 ; i < in.width ; i++ ) {
232 VectorSubtract( in.verts[i].xyz,
233 in.verts[i + (in.height-1)*in.width].xyz, delta );
234 len = VectorLength( delta );
239 if ( i == in.width) {
244 for ( i = 0 ; i < in.width ; i++ ) {
245 for ( j = 0 ; j < in.height ; j++ ) {
247 dv = &in.verts[j*in.width+i];
248 VectorCopy( dv->xyz, base );
249 for ( k = 0 ; k < 8 ; k++ ) {
250 VectorClear( around[k] );
253 for ( dist = 1 ; dist <= 3 ; dist++ ) {
254 x = i + neighbors[k][0] * dist;
255 y = j + neighbors[k][1] * dist;
258 x = in.width - 1 + x;
259 } else if ( x >= in.width ) {
260 x = 1 + x - in.width;
265 y = in.height - 1 + y;
266 } else if ( y >= in.height ) {
267 y = 1 + y - in.height;
271 if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
272 break; // edge of patch
274 VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );
275 if ( VectorNormalize( temp, temp ) == 0 ) {
276 continue; // degenerate edge, get more dist
279 VectorCopy( temp, around[k] );
286 for ( k = 0 ; k < 8 ; k++ ) {
287 if ( !good[k] || !good[(k+1)&7] ) {
288 continue; // didn't get two points
290 CrossProduct( around[(k+1)&7], around[k], normal );
291 if ( VectorNormalize( normal, normal ) == 0 ) {
294 VectorAdd( normal, sum, sum );
298 //Sys_Printf("bad normal\n");
301 VectorNormalize( sum, dv->normal );
308 drops the aproximating points onto the curve
309 ydnar: fixme: make this use LerpDrawVert() rather than this complicated mess
312 void PutMeshOnCurve( mesh_t in ) {
317 // put all the aproximating points on the curve
318 for ( i = 0 ; i < in.width ; i++ ) {
319 for ( j = 1 ; j < in.height ; j += 2 ) {
320 for ( l = 0 ; l < 3 ; l++ ) {
321 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;
322 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;
323 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
325 /* ydnar: interpolating st coords */
328 prev = ( in.verts[j*in.width+i].st[l] + in.verts[(j+1)*in.width+i].st[l] ) * 0.5;
329 next = ( in.verts[j*in.width+i].st[l] + in.verts[(j-1)*in.width+i].st[l] ) * 0.5;
330 in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
332 for( m = 0; m < MAX_LIGHTMAPS; m++ )
334 prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j+1)*in.width+i].lightmap[ m ][l] ) * 0.5;
335 next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j-1)*in.width+i].lightmap[ m ][l] ) * 0.5;
336 in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
343 for ( j = 0 ; j < in.height ; j++ ) {
344 for ( i = 1 ; i < in.width ; i += 2 ) {
345 for ( l = 0 ; l < 3 ; l++ ) {
346 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;
347 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;
348 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
350 /* ydnar: interpolating st coords */
353 prev = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i+1].st[l] ) * 0.5;
354 next = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i-1].st[l] ) * 0.5;
355 in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
357 for( m = 0; m < MAX_LIGHTMAPS; m++ )
359 prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i+1].lightmap[ m ][l] ) * 0.5;
360 next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i-1].lightmap[ m ][l] ) * 0.5;
361 in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
376 mesh_t *SubdivideMesh( mesh_t in, float maxError, float minLength )
379 bspDrawVert_t prev, next, mid;
380 vec3_t prevxyz, nextxyz, midxyz;
385 /* ydnar: static for os x */
386 MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
389 out.width = in.width;
390 out.height = in.height;
392 for ( i = 0 ; i < in.width ; i++ ) {
393 for ( j = 0 ; j < in.height ; j++ ) {
394 expand[j][i] = in.verts[j*in.width+i];
398 // horizontal subdivisions
399 for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
400 // check subdivided midpoints against control points
401 for ( i = 0 ; i < out.height ; i++ ) {
402 for ( l = 0 ; l < 3 ; l++ ) {
403 prevxyz[l] = expand[i][j+1].xyz[l] - expand[i][j].xyz[l];
404 nextxyz[l] = expand[i][j+2].xyz[l] - expand[i][j+1].xyz[l];
405 midxyz[l] = (expand[i][j].xyz[l] + expand[i][j+1].xyz[l] * 2
406 + expand[i][j+2].xyz[l] ) * 0.25;
409 // if the span length is too long, force a subdivision
410 if ( VectorLength( prevxyz ) > minLength
411 || VectorLength( nextxyz ) > minLength ) {
415 // see if this midpoint is off far enough to subdivide
416 VectorSubtract( expand[i][j+1].xyz, midxyz, delta );
417 len = VectorLength( delta );
418 if ( len > maxError ) {
423 if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
424 break; // can't subdivide any more
427 if ( i == out.height ) {
428 continue; // didn't need subdivision
431 // insert two columns and replace the peak
434 for ( i = 0 ; i < out.height ; i++ ) {
435 LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev );
436 LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next );
437 LerpDrawVert( &prev, &next, &mid );
439 for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
440 expand[i][k] = expand[i][k-2];
442 expand[i][j + 1] = prev;
443 expand[i][j + 2] = mid;
444 expand[i][j + 3] = next;
447 // back up and recheck this set again, it may need more subdivision
452 // vertical subdivisions
453 for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
454 // check subdivided midpoints against control points
455 for ( i = 0 ; i < out.width ; i++ ) {
456 for ( l = 0 ; l < 3 ; l++ ) {
457 prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l];
458 nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l];
459 midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2
460 + expand[j+2][i].xyz[l] ) * 0.25;
463 // if the span length is too long, force a subdivision
464 if ( VectorLength( prevxyz ) > minLength
465 || VectorLength( nextxyz ) > minLength ) {
468 // see if this midpoint is off far enough to subdivide
469 VectorSubtract( expand[j+1][i].xyz, midxyz, delta );
470 len = VectorLength( delta );
471 if ( len > maxError ) {
476 if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
477 break; // can't subdivide any more
480 if ( i == out.width ) {
481 continue; // didn't need subdivision
484 // insert two columns and replace the peak
487 for ( i = 0 ; i < out.width ; i++ ) {
488 LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev );
489 LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next );
490 LerpDrawVert( &prev, &next, &mid );
492 for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
493 expand[k][i] = expand[k-2][i];
495 expand[j+1][i] = prev;
496 expand[j+2][i] = mid;
497 expand[j+3][i] = next;
500 // back up and recheck this set again, it may need more subdivision
505 // collapse the verts
507 out.verts = &expand[0][0];
508 for ( i = 1 ; i < out.height ; i++ ) {
509 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
512 return CopyMesh(&out);
518 IterationsForCurve() - ydnar
519 given a curve of a certain length, return the number of subdivision iterations
520 note: this is affected by subdivision amount
523 int IterationsForCurve( float len, int subdivisions )
525 int iterations, facets;
528 /* calculate the number of subdivisions */
529 for( iterations = 0; iterations < 3; iterations++ )
531 facets = subdivisions * 16 * pow( 2, iterations );
536 /* return to caller */
542 SubdivideMesh2() - ydnar
543 subdivides each mesh quad a specified number of times
546 mesh_t *SubdivideMesh2( mesh_t in, int iterations )
549 bspDrawVert_t prev, next, mid;
552 /* ydnar: static for os x */
553 MAC_STATIC bspDrawVert_t expand[ MAX_EXPANDED_AXIS ][ MAX_EXPANDED_AXIS ];
557 out.width = in.width;
558 out.height = in.height;
559 for( i = 0; i < in.width; i++ )
561 for( j = 0; j < in.height; j++ )
562 expand[ j ][ i ] = in.verts[ j * in.width + i ];
566 for( ; iterations > 0; iterations-- )
568 /* horizontal subdivisions */
569 for( j = 0; j + 2 < out.width; j += 4 )
571 /* check size limit */
572 if( out.width + 2 >= MAX_EXPANDED_AXIS )
575 /* insert two columns and replace the peak */
577 for( i = 0; i < out.height; i++ )
579 LerpDrawVert( &expand[ i ][ j ], &expand[ i ][ j + 1 ], &prev );
580 LerpDrawVert( &expand[ i ][ j + 1 ], &expand[ i ][ j + 2 ], &next );
581 LerpDrawVert( &prev, &next, &mid );
583 for ( k = out.width - 1 ; k > j + 3; k-- )
584 expand [ i ][ k ] = expand[ i ][ k - 2 ];
585 expand[ i ][ j + 1 ] = prev;
586 expand[ i ][ j + 2 ] = mid;
587 expand[ i ][ j + 3 ] = next;
592 /* vertical subdivisions */
593 for ( j = 0; j + 2 < out.height; j += 4 )
595 /* check size limit */
596 if( out.height + 2 >= MAX_EXPANDED_AXIS )
599 /* insert two columns and replace the peak */
601 for( i = 0; i < out.width; i++ )
603 LerpDrawVert( &expand[ j ][ i ], &expand[ j + 1 ][ i ], &prev );
604 LerpDrawVert( &expand[ j + 1 ][ i ], &expand[ j + 2 ][ i ], &next );
605 LerpDrawVert( &prev, &next, &mid );
607 for( k = out.height - 1; k > j + 3; k-- )
608 expand[ k ][ i ] = expand[ k - 2 ][ i ];
609 expand[ j + 1 ][ i ] = prev;
610 expand[ j + 2 ][ i ] = mid;
611 expand[ j + 3 ][ i ] = next;
616 /* collapse the verts */
617 out.verts = &expand[ 0 ][ 0 ];
618 for( i = 1; i < out.height; i++ )
619 memmove( &out.verts[ i * out.width ], expand[ i ], out.width * sizeof( bspDrawVert_t ) );
621 /* return to sender */
622 return CopyMesh( &out );
633 ProjectPointOntoVector
636 void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj )
640 VectorSubtract( point, vStart, pVec );
641 VectorSubtract( vEnd, vStart, vec );
642 VectorNormalize( vec, vec );
643 // project onto the directional vector for this segment
644 VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );
649 RemoveLinearMeshColumsRows
652 mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {
654 float len, maxLength;
658 /* ydnar: static for os x */
659 MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
662 out.width = in->width;
663 out.height = in->height;
665 for ( i = 0 ; i < in->width ; i++ ) {
666 for ( j = 0 ; j < in->height ; j++ ) {
667 expand[j][i] = in->verts[j*in->width+i];
671 for ( j = 1 ; j < out.width - 1; j++ ) {
673 for ( i = 0 ; i < out.height ; i++ ) {
674 ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj);
675 VectorSubtract(expand[i][j].xyz, proj, dir);
676 len = VectorLength(dir);
677 if (len > maxLength) {
684 for ( i = 0 ; i < out.height ; i++ ) {
685 for (k = j; k < out.width; k++) {
686 expand[i][k] = expand[i][k+1];
692 for ( j = 1 ; j < out.height - 1; j++ ) {
694 for ( i = 0 ; i < out.width ; i++ ) {
695 ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj);
696 VectorSubtract(expand[j][i].xyz, proj, dir);
697 len = VectorLength(dir);
698 if (len > maxLength) {
705 for ( i = 0 ; i < out.width ; i++ ) {
706 for (k = j; k < out.height; k++) {
707 expand[k][i] = expand[k+1][i];
713 // collapse the verts
714 out.verts = &expand[0][0];
715 for ( i = 1 ; i < out.height ; i++ ) {
716 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
719 return CopyMesh(&out);
729 mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int *widthtable, int *heighttable )
731 int i, j, k, w, h, maxsubdivisions, subdivisions;
733 float length, maxLength, amount;
735 bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
737 out.width = in->width;
738 out.height = in->height;
740 for ( i = 0 ; i < in->width ; i++ ) {
741 for ( j = 0 ; j < in->height ; j++ ) {
742 expand[j][i] = in->verts[j*in->width+i];
746 if (maxsize > MAX_EXPANDED_AXIS)
747 Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS");
749 // horizontal subdivisions
751 maxsubdivisions = (maxsize - in->width) / (in->width - 1);
753 for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) {
755 for ( i = 0 ; i < out.height ; i++ ) {
756 VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir);
757 length = VectorLength( dir );
758 if (length > maxLength) {
763 subdivisions = (int) (maxLength / minLength);
764 if (subdivisions > maxsubdivisions)
765 subdivisions = maxsubdivisions;
767 widthtable[w] = subdivisions + 1;
768 if (subdivisions <= 0)
771 out.width += subdivisions;
773 for ( i = 0 ; i < out.height ; i++ ) {
774 for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {
775 expand[i][k] = expand[i][k-subdivisions];
777 for (k = 1; k <= subdivisions; k++)
779 amount = (float) k / (subdivisions + 1);
780 LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]);
785 maxsubdivisions = (maxsize - in->height) / (in->height - 1);
787 for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) {
789 for ( i = 0 ; i < out.width ; i++ ) {
790 VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir);
791 length = VectorLength( dir );
792 if (length > maxLength) {
797 subdivisions = (int) (maxLength / minLength);
798 if (subdivisions > maxsubdivisions)
799 subdivisions = maxsubdivisions;
801 heighttable[h] = subdivisions + 1;
802 if (subdivisions <= 0)
805 out.height += subdivisions;
807 for ( i = 0 ; i < out.width ; i++ ) {
808 for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {
809 expand[k][i] = expand[k-subdivisions][i];
811 for (k = 1; k <= subdivisions; k++)
813 amount = (float) k / (subdivisions + 1);
814 LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]);
819 // collapse the verts
820 out.verts = &expand[0][0];
821 for ( i = 1 ; i < out.height ; i++ ) {
822 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
825 return CopyMesh(&out);