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