-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-\r
-----------------------------------------------------------------------------------\r
-\r
-This code has been altered significantly from its original form, to support\r
-several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
-\r
-------------------------------------------------------------------------------- */\r
-\r
-\r
-\r
-/* marker */\r
-#define MESH_C\r
-\r
-\r
-\r
-/* dependencies */\r
-#include "q3map2.h"\r
-\r
-\r
-\r
-/*\r
-LerpDrawVert()\r
-returns an 50/50 interpolated vert\r
-*/\r
-\r
-void LerpDrawVert( bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *out )\r
-{\r
- int k;\r
- \r
- \r
- out->xyz[ 0 ] = 0.5 * (a->xyz[ 0 ] + b->xyz[ 0 ]);\r
- out->xyz[ 1 ] = 0.5 * (a->xyz[ 1 ] + b->xyz[ 1 ]);\r
- out->xyz[ 2 ] = 0.5 * (a->xyz[ 2 ] + b->xyz[ 2 ]);\r
-\r
- out->st[ 0 ] = 0.5 * (a->st[ 0 ] + b->st[ 0 ]);\r
- out->st[ 1 ] = 0.5 * (a->st[ 1 ] + b->st[ 1 ]);\r
- \r
- for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
- {\r
- out->lightmap[ k ][ 0 ] = 0.5f * (a->lightmap[ k ][ 0 ] + b->lightmap[ k ][ 0 ]);\r
- out->lightmap[ k ][ 1 ] = 0.5f * (a->lightmap[ k ][ 1 ] + b->lightmap[ k ][ 1 ]);\r
- out->color[ k ][ 0 ] = (a->color[ k ][ 0 ] + b->color[ k ][ 0 ]) >> 1;\r
- out->color[ k ][ 1 ] = (a->color[ k ][ 1 ] + b->color[ k ][ 1 ]) >> 1;\r
- out->color[ k ][ 2 ] = (a->color[ k ][ 2 ] + b->color[ k ][ 2 ]) >> 1;\r
- out->color[ k ][ 3 ] = (a->color[ k ][ 3 ] + b->color[ k ][ 3 ]) >> 1;\r
- }\r
- \r
- /* ydnar: added normal interpolation */\r
- out->normal[ 0 ] = 0.5f * (a->normal[ 0 ] + b->normal[ 0 ]);\r
- out->normal[ 1 ] = 0.5f * (a->normal[ 1 ] + b->normal[ 1 ]);\r
- out->normal[ 2 ] = 0.5f * (a->normal[ 2 ] + b->normal[ 2 ]);\r
- \r
- /* if the interpolant created a bogus normal, just copy the normal from a */\r
- if( VectorNormalize( out->normal, out->normal ) == 0 )\r
- VectorCopy( a->normal, out->normal );\r
-}\r
-\r
-\r
-\r
-/*\r
-LerpDrawVertAmount()\r
-returns a biased interpolated vert\r
-*/\r
-\r
-void LerpDrawVertAmount( bspDrawVert_t *a, bspDrawVert_t *b, float amount, bspDrawVert_t *out )\r
-{\r
- int k;\r
- \r
- \r
- out->xyz[ 0 ] = a->xyz[ 0 ] + amount * (b->xyz[ 0 ] - a->xyz[ 0 ]);\r
- out->xyz[ 1 ] = a->xyz[ 1 ] + amount * (b->xyz[ 1 ] - a->xyz[ 1 ]);\r
- out->xyz[ 2 ] = a->xyz[ 2 ] + amount * (b->xyz[ 2 ] - a->xyz[ 2 ]);\r
- \r
- out->st[ 0 ] = a->st[ 0 ] + amount * (b->st[ 0 ] - a->st[ 0 ]);\r
- out->st[ 1 ] = a->st[ 1 ] + amount * (b->st[ 1 ] - a->st[ 1 ]);\r
- \r
- for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
- {\r
- out->lightmap[ k ][ 0 ] = a->lightmap[ k ][ 0 ] + amount * (b->lightmap[ k ][ 0 ] - a->lightmap[ k ][ 0 ]);\r
- out->lightmap[ k ][ 1 ] = a->lightmap[ k ][ 1 ] + amount * (b->lightmap[ k ][ 1 ] - a->lightmap[ k ][ 1 ]);\r
- out->color[ k ][ 0 ] = a->color[ k ][ 0 ] + amount * (b->color[ k ][ 0 ] - a->color[ k ][ 0 ]);\r
- out->color[ k ][ 1 ] = a->color[ k ][ 1 ] + amount * (b->color[ k ][ 1 ] - a->color[ k ][ 1 ]);\r
- out->color[ k ][ 2 ] = a->color[ k ][ 2 ] + amount * (b->color[ k ][ 2 ] - a->color[ k ][ 2 ]);\r
- out->color[ k ][ 3 ] = a->color[ k ][ 3 ] + amount * (b->color[ k ][ 3 ] - a->color[ k ][ 3 ]);\r
- }\r
-\r
- out->normal[ 0 ] = a->normal[ 0 ] + amount * (b->normal[ 0 ] - a->normal[ 0 ]);\r
- out->normal[ 1 ] = a->normal[ 1 ] + amount * (b->normal[ 1 ] - a->normal[ 1 ]);\r
- out->normal[ 2 ] = a->normal[ 2 ] + amount * (b->normal[ 2 ] - a->normal[ 2 ]);\r
- \r
- /* if the interpolant created a bogus normal, just copy the normal from a */\r
- if( VectorNormalize( out->normal, out->normal ) == 0 )\r
- VectorCopy( a->normal, out->normal );\r
-}\r
-\r
-\r
-void FreeMesh( mesh_t *m ) {\r
- free( m->verts );\r
- free( m );\r
-}\r
-\r
-void PrintMesh( mesh_t *m ) {\r
- int i, j;\r
-\r
- for ( i = 0 ; i < m->height ; i++ ) {\r
- for ( j = 0 ; j < m->width ; j++ ) {\r
- Sys_Printf("(%5.2f %5.2f %5.2f) "\r
- , m->verts[i*m->width+j].xyz[0]\r
- , m->verts[i*m->width+j].xyz[1]\r
- , m->verts[i*m->width+j].xyz[2] );\r
- }\r
- Sys_Printf("\n");\r
- }\r
-}\r
-\r
-\r
-mesh_t *CopyMesh( mesh_t *mesh ) {\r
- mesh_t *out;\r
- int size;\r
-\r
- out = safe_malloc( sizeof( *out ) );\r
- out->width = mesh->width;\r
- out->height = mesh->height;\r
-\r
- size = out->width * out->height * sizeof( *out->verts );\r
- out->verts = safe_malloc( size );\r
- memcpy( out->verts, mesh->verts, size );\r
-\r
- return out;\r
-}\r
-\r
-\r
-/*\r
-TransposeMesh()\r
-returns a transposed copy of the mesh, freeing the original\r
-*/\r
-\r
-mesh_t *TransposeMesh( mesh_t *in ) {\r
- int w, h;\r
- mesh_t *out;\r
-\r
- out = safe_malloc( sizeof( *out ) );\r
- out->width = in->height;\r
- out->height = in->width;\r
- out->verts = safe_malloc( out->width * out->height * sizeof( bspDrawVert_t ) );\r
-\r
- for ( h = 0 ; h < in->height ; h++ ) {\r
- for ( w = 0 ; w < in->width ; w++ ) {\r
- out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];\r
- }\r
- }\r
-\r
- FreeMesh( in );\r
-\r
- return out;\r
-}\r
-\r
-void InvertMesh( mesh_t *in ) {\r
- int w, h;\r
- bspDrawVert_t temp;\r
-\r
- for ( h = 0 ; h < in->height ; h++ ) {\r
- for ( w = 0 ; w < in->width / 2 ; w++ ) {\r
- temp = in->verts[ h * in->width + w ];\r
- in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];\r
- in->verts[ h * in->width + in->width - 1 - w ] = temp;\r
- }\r
- }\r
-}\r
-\r
-/*\r
-=================\r
-MakeMeshNormals\r
-\r
-=================\r
-*/\r
-void MakeMeshNormals( mesh_t in )\r
-{\r
- int i, j, k, dist;\r
- vec3_t normal;\r
- vec3_t sum;\r
- int count;\r
- vec3_t base;\r
- vec3_t delta;\r
- int x, y;\r
- bspDrawVert_t *dv;\r
- vec3_t around[8], temp;\r
- qboolean good[8];\r
- qboolean wrapWidth, wrapHeight;\r
- float len;\r
- int neighbors[8][2] =\r
- {\r
- {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}\r
- };\r
- \r
- \r
- wrapWidth = qfalse;\r
- for ( i = 0 ; i < in.height ; i++ ) {\r
- VectorSubtract( in.verts[i*in.width].xyz, \r
- in.verts[i*in.width+in.width-1].xyz, delta );\r
- len = VectorLength( delta );\r
- if ( len > 1.0 ) {\r
- break;\r
- }\r
- }\r
- if ( i == in.height ) {\r
- wrapWidth = qtrue;\r
- }\r
-\r
- wrapHeight = qfalse;\r
- for ( i = 0 ; i < in.width ; i++ ) {\r
- VectorSubtract( in.verts[i].xyz, \r
- in.verts[i + (in.height-1)*in.width].xyz, delta );\r
- len = VectorLength( delta );\r
- if ( len > 1.0 ) {\r
- break;\r
- }\r
- }\r
- if ( i == in.width) {\r
- wrapHeight = qtrue;\r
- }\r
-\r
-\r
- for ( i = 0 ; i < in.width ; i++ ) {\r
- for ( j = 0 ; j < in.height ; j++ ) {\r
- count = 0;\r
- dv = &in.verts[j*in.width+i];\r
- VectorCopy( dv->xyz, base );\r
- for ( k = 0 ; k < 8 ; k++ ) {\r
- VectorClear( around[k] );\r
- good[k] = qfalse;\r
-\r
- for ( dist = 1 ; dist <= 3 ; dist++ ) {\r
- x = i + neighbors[k][0] * dist;\r
- y = j + neighbors[k][1] * dist;\r
- if ( wrapWidth ) {\r
- if ( x < 0 ) {\r
- x = in.width - 1 + x;\r
- } else if ( x >= in.width ) {\r
- x = 1 + x - in.width;\r
- }\r
- }\r
- if ( wrapHeight ) {\r
- if ( y < 0 ) {\r
- y = in.height - 1 + y;\r
- } else if ( y >= in.height ) {\r
- y = 1 + y - in.height;\r
- }\r
- }\r
-\r
- if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {\r
- break; // edge of patch\r
- }\r
- VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );\r
- if ( VectorNormalize( temp, temp ) == 0 ) {\r
- continue; // degenerate edge, get more dist\r
- } else {\r
- good[k] = qtrue;\r
- VectorCopy( temp, around[k] );\r
- break; // good edge\r
- }\r
- }\r
- }\r
-\r
- VectorClear( sum );\r
- for ( k = 0 ; k < 8 ; k++ ) {\r
- if ( !good[k] || !good[(k+1)&7] ) {\r
- continue; // didn't get two points\r
- }\r
- CrossProduct( around[(k+1)&7], around[k], normal );\r
- if ( VectorNormalize( normal, normal ) == 0 ) {\r
- continue;\r
- }\r
- VectorAdd( normal, sum, sum );\r
- count++;\r
- }\r
- if ( count == 0 ) {\r
-//Sys_Printf("bad normal\n");\r
- count = 1;\r
- }\r
- VectorNormalize( sum, dv->normal );\r
- }\r
- }\r
-}\r
-\r
-/*\r
-PutMeshOnCurve()\r
-drops the aproximating points onto the curve\r
-ydnar: fixme: make this use LerpDrawVert() rather than this complicated mess\r
-*/\r
-\r
-void PutMeshOnCurve( mesh_t in ) {\r
- int i, j, l, m;\r
- float prev, next;\r
- \r
- \r
- // put all the aproximating points on the curve\r
- for ( i = 0 ; i < in.width ; i++ ) {\r
- for ( j = 1 ; j < in.height ; j += 2 ) {\r
- for ( l = 0 ; l < 3 ; l++ ) {\r
- prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;\r
- next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;\r
- in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;\r
- \r
- /* ydnar: interpolating st coords */\r
- if( l < 2 )\r
- {\r
- prev = ( in.verts[j*in.width+i].st[l] + in.verts[(j+1)*in.width+i].st[l] ) * 0.5;\r
- next = ( in.verts[j*in.width+i].st[l] + in.verts[(j-1)*in.width+i].st[l] ) * 0.5;\r
- in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;\r
- \r
- for( m = 0; m < MAX_LIGHTMAPS; m++ )\r
- {\r
- prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j+1)*in.width+i].lightmap[ m ][l] ) * 0.5;\r
- next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j-1)*in.width+i].lightmap[ m ][l] ) * 0.5;\r
- in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;\r
- }\r
- }\r
- }\r
- }\r
- }\r
- \r
- for ( j = 0 ; j < in.height ; j++ ) {\r
- for ( i = 1 ; i < in.width ; i += 2 ) {\r
- for ( l = 0 ; l < 3 ; l++ ) {\r
- prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;\r
- next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;\r
- in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;\r
- \r
- /* ydnar: interpolating st coords */\r
- if( l < 2 )\r
- {\r
- prev = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i+1].st[l] ) * 0.5;\r
- next = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i-1].st[l] ) * 0.5;\r
- in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;\r
- \r
- for( m = 0; m < MAX_LIGHTMAPS; m++ )\r
- {\r
- prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i+1].lightmap[ m ][l] ) * 0.5;\r
- next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i-1].lightmap[ m ][l] ) * 0.5;\r
- in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;\r
- }\r
- }\r
- }\r
- }\r
- }\r
-}\r
-\r
-\r
-/*\r
-=================\r
-SubdivideMesh\r
-\r
-=================\r
-*/\r
-mesh_t *SubdivideMesh( mesh_t in, float maxError, float minLength )\r
-{\r
- int i, j, k, l;\r
- bspDrawVert_t prev, next, mid;\r
- vec3_t prevxyz, nextxyz, midxyz;\r
- vec3_t delta;\r
- float len;\r
- mesh_t out;\r
- \r
- /* ydnar: static for os x */\r
- MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];\r
- \r
- \r
- out.width = in.width;\r
- out.height = in.height;\r
-\r
- for ( i = 0 ; i < in.width ; i++ ) {\r
- for ( j = 0 ; j < in.height ; j++ ) {\r
- expand[j][i] = in.verts[j*in.width+i];\r
- }\r
- }\r
-\r
- // horizontal subdivisions\r
- for ( j = 0 ; j + 2 < out.width ; j += 2 ) {\r
- // check subdivided midpoints against control points\r
- for ( i = 0 ; i < out.height ; i++ ) {\r
- for ( l = 0 ; l < 3 ; l++ ) {\r
- prevxyz[l] = expand[i][j+1].xyz[l] - expand[i][j].xyz[l]; \r
- nextxyz[l] = expand[i][j+2].xyz[l] - expand[i][j+1].xyz[l]; \r
- midxyz[l] = (expand[i][j].xyz[l] + expand[i][j+1].xyz[l] * 2\r
- + expand[i][j+2].xyz[l] ) * 0.25;\r
- }\r
-\r
- // if the span length is too long, force a subdivision\r
- if ( VectorLength( prevxyz ) > minLength \r
- || VectorLength( nextxyz ) > minLength ) {\r
- break;\r
- }\r
-\r
- // see if this midpoint is off far enough to subdivide\r
- VectorSubtract( expand[i][j+1].xyz, midxyz, delta );\r
- len = VectorLength( delta );\r
- if ( len > maxError ) {\r
- break;\r
- }\r
- }\r
-\r
- if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {\r
- break; // can't subdivide any more\r
- }\r
-\r
- if ( i == out.height ) {\r
- continue; // didn't need subdivision\r
- }\r
-\r
- // insert two columns and replace the peak\r
- out.width += 2;\r
-\r
- for ( i = 0 ; i < out.height ; i++ ) {\r
- LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev );\r
- LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next );\r
- LerpDrawVert( &prev, &next, &mid );\r
-\r
- for ( k = out.width - 1 ; k > j + 3 ; k-- ) {\r
- expand[i][k] = expand[i][k-2];\r
- }\r
- expand[i][j + 1] = prev;\r
- expand[i][j + 2] = mid;\r
- expand[i][j + 3] = next;\r
- }\r
-\r
- // back up and recheck this set again, it may need more subdivision\r
- j -= 2;\r
-\r
- }\r
-\r
- // vertical subdivisions\r
- for ( j = 0 ; j + 2 < out.height ; j += 2 ) {\r
- // check subdivided midpoints against control points\r
- for ( i = 0 ; i < out.width ; i++ ) {\r
- for ( l = 0 ; l < 3 ; l++ ) {\r
- prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l]; \r
- nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l]; \r
- midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2\r
- + expand[j+2][i].xyz[l] ) * 0.25;\r
- }\r
-\r
- // if the span length is too long, force a subdivision\r
- if ( VectorLength( prevxyz ) > minLength \r
- || VectorLength( nextxyz ) > minLength ) {\r
- break;\r
- }\r
- // see if this midpoint is off far enough to subdivide\r
- VectorSubtract( expand[j+1][i].xyz, midxyz, delta );\r
- len = VectorLength( delta );\r
- if ( len > maxError ) {\r
- break;\r
- }\r
- }\r
-\r
- if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {\r
- break; // can't subdivide any more\r
- }\r
-\r
- if ( i == out.width ) {\r
- continue; // didn't need subdivision\r
- }\r
-\r
- // insert two columns and replace the peak\r
- out.height += 2;\r
-\r
- for ( i = 0 ; i < out.width ; i++ ) {\r
- LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev );\r
- LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next );\r
- LerpDrawVert( &prev, &next, &mid );\r
-\r
- for ( k = out.height - 1 ; k > j + 3 ; k-- ) {\r
- expand[k][i] = expand[k-2][i];\r
- }\r
- expand[j+1][i] = prev;\r
- expand[j+2][i] = mid;\r
- expand[j+3][i] = next;\r
- }\r
-\r
- // back up and recheck this set again, it may need more subdivision\r
- j -= 2;\r
-\r
- }\r
-\r
- // collapse the verts\r
-\r
- out.verts = &expand[0][0];\r
- for ( i = 1 ; i < out.height ; i++ ) {\r
- memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );\r
- }\r
-\r
- return CopyMesh(&out);\r
-}\r
-\r
-\r
-\r
-/*\r
-IterationsForCurve() - ydnar\r
-given a curve of a certain length, return the number of subdivision iterations\r
-note: this is affected by subdivision amount\r
-*/\r
-\r
-int IterationsForCurve( float len, int subdivisions )\r
-{\r
- int iterations, facets;\r
- \r
- \r
- /* calculate the number of subdivisions */\r
- for( iterations = 0; iterations < 3; iterations++ )\r
- {\r
- facets = subdivisions * 16 * pow( 2, iterations );\r
- if( facets >= len )\r
- break;\r
- }\r
- \r
- /* return to caller */\r
- return iterations;\r
-}\r
-\r
-\r
-/*\r
-SubdivideMesh2() - ydnar\r
-subdivides each mesh quad a specified number of times\r
-*/\r
-\r
-mesh_t *SubdivideMesh2( mesh_t in, int iterations )\r
-{\r
- int i, j, k;\r
- bspDrawVert_t prev, next, mid;\r
- mesh_t out;\r
- \r
- /* ydnar: static for os x */\r
- MAC_STATIC bspDrawVert_t expand[ MAX_EXPANDED_AXIS ][ MAX_EXPANDED_AXIS ];\r
- \r
- \r
- /* initial setup */\r
- out.width = in.width;\r
- out.height = in.height;\r
- for( i = 0; i < in.width; i++ )\r
- {\r
- for( j = 0; j < in.height; j++ )\r
- expand[ j ][ i ] = in.verts[ j * in.width + i ];\r
- }\r
- \r
- /* keep chopping */\r
- for( iterations; iterations > 0; iterations-- )\r
- {\r
- /* horizontal subdivisions */\r
- for( j = 0; j + 2 < out.width; j += 4 )\r
- {\r
- /* check size limit */\r
- if( out.width + 2 >= MAX_EXPANDED_AXIS )\r
- break;\r
- \r
- /* insert two columns and replace the peak */\r
- out.width += 2;\r
- for( i = 0; i < out.height; i++ )\r
- {\r
- LerpDrawVert( &expand[ i ][ j ], &expand[ i ][ j + 1 ], &prev );\r
- LerpDrawVert( &expand[ i ][ j + 1 ], &expand[ i ][ j + 2 ], &next );\r
- LerpDrawVert( &prev, &next, &mid );\r
-\r
- for ( k = out.width - 1 ; k > j + 3; k-- )\r
- expand [ i ][ k ] = expand[ i ][ k - 2 ];\r
- expand[ i ][ j + 1 ] = prev;\r
- expand[ i ][ j + 2 ] = mid;\r
- expand[ i ][ j + 3 ] = next;\r
- }\r
- \r
- }\r
-\r
- /* vertical subdivisions */\r
- for ( j = 0; j + 2 < out.height; j += 4 )\r
- {\r
- /* check size limit */\r
- if( out.height + 2 >= MAX_EXPANDED_AXIS )\r
- break;\r
- \r
- /* insert two columns and replace the peak */\r
- out.height += 2;\r
- for( i = 0; i < out.width; i++ )\r
- {\r
- LerpDrawVert( &expand[ j ][ i ], &expand[ j + 1 ][ i ], &prev );\r
- LerpDrawVert( &expand[ j + 1 ][ i ], &expand[ j + 2 ][ i ], &next );\r
- LerpDrawVert( &prev, &next, &mid );\r
- \r
- for( k = out.height - 1; k > j + 3; k-- )\r
- expand[ k ][ i ] = expand[ k - 2 ][ i ];\r
- expand[ j + 1 ][ i ] = prev;\r
- expand[ j + 2 ][ i ] = mid;\r
- expand[ j + 3 ][ i ] = next;\r
- }\r
- }\r
- }\r
- \r
- /* collapse the verts */\r
- out.verts = &expand[ 0 ][ 0 ];\r
- for( i = 1; i < out.height; i++ )\r
- memmove( &out.verts[ i * out.width ], expand[ i ], out.width * sizeof( bspDrawVert_t ) );\r
- \r
- /* return to sender */\r
- return CopyMesh( &out );\r
-}\r
-\r
-\r
-\r
-\r
-\r
-\r
-\r
-/*\r
-================\r
-ProjectPointOntoVector\r
-================\r
-*/\r
-void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj )\r
-{\r
- vec3_t pVec, vec;\r
-\r
- VectorSubtract( point, vStart, pVec );\r
- VectorSubtract( vEnd, vStart, vec );\r
- VectorNormalize( vec, vec );\r
- // project onto the directional vector for this segment\r
- VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );\r
-}\r
-\r
-/*\r
-================\r
-RemoveLinearMeshColumsRows\r
-================\r
-*/\r
-mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {\r
- int i, j, k;\r
- float len, maxLength;\r
- vec3_t proj, dir;\r
- mesh_t out;\r
- \r
- /* ydnar: static for os x */\r
- MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];\r
- \r
-\r
- out.width = in->width;\r
- out.height = in->height;\r
-\r
- for ( i = 0 ; i < in->width ; i++ ) {\r
- for ( j = 0 ; j < in->height ; j++ ) {\r
- expand[j][i] = in->verts[j*in->width+i];\r
- }\r
- }\r
-\r
- for ( j = 1 ; j < out.width - 1; j++ ) {\r
- maxLength = 0;\r
- for ( i = 0 ; i < out.height ; i++ ) {\r
- ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj);\r
- VectorSubtract(expand[i][j].xyz, proj, dir);\r
- len = VectorLength(dir);\r
- if (len > maxLength) {\r
- maxLength = len;\r
- }\r
- }\r
- if (maxLength < 0.1)\r
- {\r
- out.width--;\r
- for ( i = 0 ; i < out.height ; i++ ) {\r
- for (k = j; k < out.width; k++) {\r
- expand[i][k] = expand[i][k+1];\r
- }\r
- }\r
- j--;\r
- }\r
- }\r
- for ( j = 1 ; j < out.height - 1; j++ ) {\r
- maxLength = 0;\r
- for ( i = 0 ; i < out.width ; i++ ) {\r
- ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj);\r
- VectorSubtract(expand[j][i].xyz, proj, dir);\r
- len = VectorLength(dir);\r
- if (len > maxLength) {\r
- maxLength = len;\r
- }\r
- }\r
- if (maxLength < 0.1)\r
- {\r
- out.height--;\r
- for ( i = 0 ; i < out.width ; i++ ) {\r
- for (k = j; k < out.height; k++) {\r
- expand[k][i] = expand[k+1][i];\r
- }\r
- }\r
- j--;\r
- }\r
- }\r
- // collapse the verts\r
- out.verts = &expand[0][0];\r
- for ( i = 1 ; i < out.height ; i++ ) {\r
- memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );\r
- }\r
-\r
- return CopyMesh(&out);\r
-}\r
-\r
-\r
-\r
-/*\r
-=================\r
-SubdivideMeshQuads\r
-=================\r
-*/\r
-mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int *widthtable, int *heighttable )\r
-{\r
- int i, j, k, w, h, maxsubdivisions, subdivisions;\r
- vec3_t dir;\r
- float length, maxLength, amount;\r
- mesh_t out;\r
- bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];\r
-\r
- out.width = in->width;\r
- out.height = in->height;\r
-\r
- for ( i = 0 ; i < in->width ; i++ ) {\r
- for ( j = 0 ; j < in->height ; j++ ) {\r
- expand[j][i] = in->verts[j*in->width+i];\r
- }\r
- }\r
-\r
- if (maxsize > MAX_EXPANDED_AXIS)\r
- Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS");\r
-\r
- // horizontal subdivisions\r
-\r
- maxsubdivisions = (maxsize - in->width) / (in->width - 1);\r
-\r
- for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) {\r
- maxLength = 0;\r
- for ( i = 0 ; i < out.height ; i++ ) {\r
- VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir);\r
- length = VectorLength( dir );\r
- if (length > maxLength) {\r
- maxLength = length;\r
- }\r
- }\r
- \r
- subdivisions = (int) (maxLength / minLength);\r
- if (subdivisions > maxsubdivisions)\r
- subdivisions = maxsubdivisions;\r
-\r
- widthtable[w] = subdivisions + 1;\r
- if (subdivisions <= 0)\r
- continue;\r
-\r
- out.width += subdivisions;\r
-\r
- for ( i = 0 ; i < out.height ; i++ ) {\r
- for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {\r
- expand[i][k] = expand[i][k-subdivisions];\r
- }\r
- for (k = 1; k <= subdivisions; k++)\r
- {\r
- amount = (float) k / (subdivisions + 1);\r
- LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]);\r
- }\r
- }\r
- }\r
-\r
- maxsubdivisions = (maxsize - in->height) / (in->height - 1);\r
-\r
- for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) {\r
- maxLength = 0;\r
- for ( i = 0 ; i < out.width ; i++ ) {\r
- VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir);\r
- length = VectorLength( dir );\r
- if (length > maxLength) {\r
- maxLength = length;\r
- }\r
- }\r
- \r
- subdivisions = (int) (maxLength / minLength);\r
- if (subdivisions > maxsubdivisions)\r
- subdivisions = maxsubdivisions;\r
-\r
- heighttable[h] = subdivisions + 1;\r
- if (subdivisions <= 0)\r
- continue;\r
-\r
- out.height += subdivisions;\r
-\r
- for ( i = 0 ; i < out.width ; i++ ) {\r
- for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {\r
- expand[k][i] = expand[k-subdivisions][i];\r
- }\r
- for (k = 1; k <= subdivisions; k++)\r
- {\r
- amount = (float) k / (subdivisions + 1);\r
- LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]);\r
- }\r
- }\r
- }\r
-\r
- // collapse the verts\r
- out.verts = &expand[0][0];\r
- for ( i = 1 ; i < out.height ; i++ ) {\r
- memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );\r
- }\r
-\r
- return CopyMesh(&out);\r
-}\r
+/*
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+GtkRadiant is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+
+----------------------------------------------------------------------------------
+
+This code has been altered significantly from its original form, to support
+several games based on the Quake III Arena engine, in the form of "Q3Map2."
+
+------------------------------------------------------------------------------- */
+
+
+
+/* marker */
+#define MESH_C
+
+
+
+/* dependencies */
+#include "q3map2.h"
+
+
+
+/*
+LerpDrawVert()
+returns an 50/50 interpolated vert
+*/
+
+void LerpDrawVert( bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *out )
+{
+ int k;
+
+
+ out->xyz[ 0 ] = 0.5 * (a->xyz[ 0 ] + b->xyz[ 0 ]);
+ out->xyz[ 1 ] = 0.5 * (a->xyz[ 1 ] + b->xyz[ 1 ]);
+ out->xyz[ 2 ] = 0.5 * (a->xyz[ 2 ] + b->xyz[ 2 ]);
+
+ out->st[ 0 ] = 0.5 * (a->st[ 0 ] + b->st[ 0 ]);
+ out->st[ 1 ] = 0.5 * (a->st[ 1 ] + b->st[ 1 ]);
+
+ for( k = 0; k < MAX_LIGHTMAPS; k++ )
+ {
+ out->lightmap[ k ][ 0 ] = 0.5f * (a->lightmap[ k ][ 0 ] + b->lightmap[ k ][ 0 ]);
+ out->lightmap[ k ][ 1 ] = 0.5f * (a->lightmap[ k ][ 1 ] + b->lightmap[ k ][ 1 ]);
+ out->color[ k ][ 0 ] = (a->color[ k ][ 0 ] + b->color[ k ][ 0 ]) >> 1;
+ out->color[ k ][ 1 ] = (a->color[ k ][ 1 ] + b->color[ k ][ 1 ]) >> 1;
+ out->color[ k ][ 2 ] = (a->color[ k ][ 2 ] + b->color[ k ][ 2 ]) >> 1;
+ out->color[ k ][ 3 ] = (a->color[ k ][ 3 ] + b->color[ k ][ 3 ]) >> 1;
+ }
+
+ /* ydnar: added normal interpolation */
+ out->normal[ 0 ] = 0.5f * (a->normal[ 0 ] + b->normal[ 0 ]);
+ out->normal[ 1 ] = 0.5f * (a->normal[ 1 ] + b->normal[ 1 ]);
+ out->normal[ 2 ] = 0.5f * (a->normal[ 2 ] + b->normal[ 2 ]);
+
+ /* if the interpolant created a bogus normal, just copy the normal from a */
+ if( VectorNormalize( out->normal, out->normal ) == 0 )
+ VectorCopy( a->normal, out->normal );
+}
+
+
+
+/*
+LerpDrawVertAmount()
+returns a biased interpolated vert
+*/
+
+void LerpDrawVertAmount( bspDrawVert_t *a, bspDrawVert_t *b, float amount, bspDrawVert_t *out )
+{
+ int k;
+
+
+ out->xyz[ 0 ] = a->xyz[ 0 ] + amount * (b->xyz[ 0 ] - a->xyz[ 0 ]);
+ out->xyz[ 1 ] = a->xyz[ 1 ] + amount * (b->xyz[ 1 ] - a->xyz[ 1 ]);
+ out->xyz[ 2 ] = a->xyz[ 2 ] + amount * (b->xyz[ 2 ] - a->xyz[ 2 ]);
+
+ out->st[ 0 ] = a->st[ 0 ] + amount * (b->st[ 0 ] - a->st[ 0 ]);
+ out->st[ 1 ] = a->st[ 1 ] + amount * (b->st[ 1 ] - a->st[ 1 ]);
+
+ for( k = 0; k < MAX_LIGHTMAPS; k++ )
+ {
+ out->lightmap[ k ][ 0 ] = a->lightmap[ k ][ 0 ] + amount * (b->lightmap[ k ][ 0 ] - a->lightmap[ k ][ 0 ]);
+ out->lightmap[ k ][ 1 ] = a->lightmap[ k ][ 1 ] + amount * (b->lightmap[ k ][ 1 ] - a->lightmap[ k ][ 1 ]);
+ out->color[ k ][ 0 ] = a->color[ k ][ 0 ] + amount * (b->color[ k ][ 0 ] - a->color[ k ][ 0 ]);
+ out->color[ k ][ 1 ] = a->color[ k ][ 1 ] + amount * (b->color[ k ][ 1 ] - a->color[ k ][ 1 ]);
+ out->color[ k ][ 2 ] = a->color[ k ][ 2 ] + amount * (b->color[ k ][ 2 ] - a->color[ k ][ 2 ]);
+ out->color[ k ][ 3 ] = a->color[ k ][ 3 ] + amount * (b->color[ k ][ 3 ] - a->color[ k ][ 3 ]);
+ }
+
+ out->normal[ 0 ] = a->normal[ 0 ] + amount * (b->normal[ 0 ] - a->normal[ 0 ]);
+ out->normal[ 1 ] = a->normal[ 1 ] + amount * (b->normal[ 1 ] - a->normal[ 1 ]);
+ out->normal[ 2 ] = a->normal[ 2 ] + amount * (b->normal[ 2 ] - a->normal[ 2 ]);
+
+ /* if the interpolant created a bogus normal, just copy the normal from a */
+ if( VectorNormalize( out->normal, out->normal ) == 0 )
+ VectorCopy( a->normal, out->normal );
+}
+
+
+void FreeMesh( mesh_t *m ) {
+ free( m->verts );
+ free( m );
+}
+
+void PrintMesh( mesh_t *m ) {
+ int i, j;
+
+ for ( i = 0 ; i < m->height ; i++ ) {
+ for ( j = 0 ; j < m->width ; j++ ) {
+ Sys_Printf("(%5.2f %5.2f %5.2f) "
+ , m->verts[i*m->width+j].xyz[0]
+ , m->verts[i*m->width+j].xyz[1]
+ , m->verts[i*m->width+j].xyz[2] );
+ }
+ Sys_Printf("\n");
+ }
+}
+
+
+mesh_t *CopyMesh( mesh_t *mesh ) {
+ mesh_t *out;
+ int size;
+
+ out = safe_malloc( sizeof( *out ) );
+ out->width = mesh->width;
+ out->height = mesh->height;
+
+ size = out->width * out->height * sizeof( *out->verts );
+ out->verts = safe_malloc( size );
+ memcpy( out->verts, mesh->verts, size );
+
+ return out;
+}
+
+
+/*
+TransposeMesh()
+returns a transposed copy of the mesh, freeing the original
+*/
+
+mesh_t *TransposeMesh( mesh_t *in ) {
+ int w, h;
+ mesh_t *out;
+
+ out = safe_malloc( sizeof( *out ) );
+ out->width = in->height;
+ out->height = in->width;
+ out->verts = safe_malloc( out->width * out->height * sizeof( bspDrawVert_t ) );
+
+ for ( h = 0 ; h < in->height ; h++ ) {
+ for ( w = 0 ; w < in->width ; w++ ) {
+ out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];
+ }
+ }
+
+ FreeMesh( in );
+
+ return out;
+}
+
+void InvertMesh( mesh_t *in ) {
+ int w, h;
+ bspDrawVert_t temp;
+
+ for ( h = 0 ; h < in->height ; h++ ) {
+ for ( w = 0 ; w < in->width / 2 ; w++ ) {
+ temp = in->verts[ h * in->width + w ];
+ in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];
+ in->verts[ h * in->width + in->width - 1 - w ] = temp;
+ }
+ }
+}
+
+/*
+=================
+MakeMeshNormals
+
+=================
+*/
+void MakeMeshNormals( mesh_t in )
+{
+ int i, j, k, dist;
+ vec3_t normal;
+ vec3_t sum;
+ int count;
+ vec3_t base;
+ vec3_t delta;
+ int x, y;
+ bspDrawVert_t *dv;
+ vec3_t around[8], temp;
+ qboolean good[8];
+ qboolean wrapWidth, wrapHeight;
+ float len;
+ int neighbors[8][2] =
+ {
+ {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
+ };
+
+
+ wrapWidth = qfalse;
+ for ( i = 0 ; i < in.height ; i++ ) {
+ VectorSubtract( in.verts[i*in.width].xyz,
+ in.verts[i*in.width+in.width-1].xyz, delta );
+ len = VectorLength( delta );
+ if ( len > 1.0 ) {
+ break;
+ }
+ }
+ if ( i == in.height ) {
+ wrapWidth = qtrue;
+ }
+
+ wrapHeight = qfalse;
+ for ( i = 0 ; i < in.width ; i++ ) {
+ VectorSubtract( in.verts[i].xyz,
+ in.verts[i + (in.height-1)*in.width].xyz, delta );
+ len = VectorLength( delta );
+ if ( len > 1.0 ) {
+ break;
+ }
+ }
+ if ( i == in.width) {
+ wrapHeight = qtrue;
+ }
+
+
+ for ( i = 0 ; i < in.width ; i++ ) {
+ for ( j = 0 ; j < in.height ; j++ ) {
+ count = 0;
+ dv = &in.verts[j*in.width+i];
+ VectorCopy( dv->xyz, base );
+ for ( k = 0 ; k < 8 ; k++ ) {
+ VectorClear( around[k] );
+ good[k] = qfalse;
+
+ for ( dist = 1 ; dist <= 3 ; dist++ ) {
+ x = i + neighbors[k][0] * dist;
+ y = j + neighbors[k][1] * dist;
+ if ( wrapWidth ) {
+ if ( x < 0 ) {
+ x = in.width - 1 + x;
+ } else if ( x >= in.width ) {
+ x = 1 + x - in.width;
+ }
+ }
+ if ( wrapHeight ) {
+ if ( y < 0 ) {
+ y = in.height - 1 + y;
+ } else if ( y >= in.height ) {
+ y = 1 + y - in.height;
+ }
+ }
+
+ if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
+ break; // edge of patch
+ }
+ VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );
+ if ( VectorNormalize( temp, temp ) == 0 ) {
+ continue; // degenerate edge, get more dist
+ } else {
+ good[k] = qtrue;
+ VectorCopy( temp, around[k] );
+ break; // good edge
+ }
+ }
+ }
+
+ VectorClear( sum );
+ for ( k = 0 ; k < 8 ; k++ ) {
+ if ( !good[k] || !good[(k+1)&7] ) {
+ continue; // didn't get two points
+ }
+ CrossProduct( around[(k+1)&7], around[k], normal );
+ if ( VectorNormalize( normal, normal ) == 0 ) {
+ continue;
+ }
+ VectorAdd( normal, sum, sum );
+ count++;
+ }
+ if ( count == 0 ) {
+//Sys_Printf("bad normal\n");
+ count = 1;
+ }
+ VectorNormalize( sum, dv->normal );
+ }
+ }
+}
+
+/*
+PutMeshOnCurve()
+drops the aproximating points onto the curve
+ydnar: fixme: make this use LerpDrawVert() rather than this complicated mess
+*/
+
+void PutMeshOnCurve( mesh_t in ) {
+ int i, j, l, m;
+ float prev, next;
+
+
+ // put all the aproximating points on the curve
+ for ( i = 0 ; i < in.width ; i++ ) {
+ for ( j = 1 ; j < in.height ; j += 2 ) {
+ for ( l = 0 ; l < 3 ; l++ ) {
+ prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;
+ next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;
+ in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
+
+ /* ydnar: interpolating st coords */
+ if( l < 2 )
+ {
+ prev = ( in.verts[j*in.width+i].st[l] + in.verts[(j+1)*in.width+i].st[l] ) * 0.5;
+ next = ( in.verts[j*in.width+i].st[l] + in.verts[(j-1)*in.width+i].st[l] ) * 0.5;
+ in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
+
+ for( m = 0; m < MAX_LIGHTMAPS; m++ )
+ {
+ prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j+1)*in.width+i].lightmap[ m ][l] ) * 0.5;
+ next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j-1)*in.width+i].lightmap[ m ][l] ) * 0.5;
+ in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
+ }
+ }
+ }
+ }
+ }
+
+ for ( j = 0 ; j < in.height ; j++ ) {
+ for ( i = 1 ; i < in.width ; i += 2 ) {
+ for ( l = 0 ; l < 3 ; l++ ) {
+ prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;
+ next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;
+ in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
+
+ /* ydnar: interpolating st coords */
+ if( l < 2 )
+ {
+ prev = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i+1].st[l] ) * 0.5;
+ next = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i-1].st[l] ) * 0.5;
+ in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
+
+ for( m = 0; m < MAX_LIGHTMAPS; m++ )
+ {
+ prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i+1].lightmap[ m ][l] ) * 0.5;
+ next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i-1].lightmap[ m ][l] ) * 0.5;
+ in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
+ }
+ }
+ }
+ }
+ }
+}
+
+
+/*
+=================
+SubdivideMesh
+
+=================
+*/
+mesh_t *SubdivideMesh( mesh_t in, float maxError, float minLength )
+{
+ int i, j, k, l;
+ bspDrawVert_t prev, next, mid;
+ vec3_t prevxyz, nextxyz, midxyz;
+ vec3_t delta;
+ float len;
+ mesh_t out;
+
+ /* ydnar: static for os x */
+ MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
+
+
+ out.width = in.width;
+ out.height = in.height;
+
+ for ( i = 0 ; i < in.width ; i++ ) {
+ for ( j = 0 ; j < in.height ; j++ ) {
+ expand[j][i] = in.verts[j*in.width+i];
+ }
+ }
+
+ // horizontal subdivisions
+ for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
+ // check subdivided midpoints against control points
+ for ( i = 0 ; i < out.height ; i++ ) {
+ for ( l = 0 ; l < 3 ; l++ ) {
+ prevxyz[l] = expand[i][j+1].xyz[l] - expand[i][j].xyz[l];
+ nextxyz[l] = expand[i][j+2].xyz[l] - expand[i][j+1].xyz[l];
+ midxyz[l] = (expand[i][j].xyz[l] + expand[i][j+1].xyz[l] * 2
+ + expand[i][j+2].xyz[l] ) * 0.25;
+ }
+
+ // if the span length is too long, force a subdivision
+ if ( VectorLength( prevxyz ) > minLength
+ || VectorLength( nextxyz ) > minLength ) {
+ break;
+ }
+
+ // see if this midpoint is off far enough to subdivide
+ VectorSubtract( expand[i][j+1].xyz, midxyz, delta );
+ len = VectorLength( delta );
+ if ( len > maxError ) {
+ break;
+ }
+ }
+
+ if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
+ break; // can't subdivide any more
+ }
+
+ if ( i == out.height ) {
+ continue; // didn't need subdivision
+ }
+
+ // insert two columns and replace the peak
+ out.width += 2;
+
+ for ( i = 0 ; i < out.height ; i++ ) {
+ LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev );
+ LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next );
+ LerpDrawVert( &prev, &next, &mid );
+
+ for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
+ expand[i][k] = expand[i][k-2];
+ }
+ expand[i][j + 1] = prev;
+ expand[i][j + 2] = mid;
+ expand[i][j + 3] = next;
+ }
+
+ // back up and recheck this set again, it may need more subdivision
+ j -= 2;
+
+ }
+
+ // vertical subdivisions
+ for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
+ // check subdivided midpoints against control points
+ for ( i = 0 ; i < out.width ; i++ ) {
+ for ( l = 0 ; l < 3 ; l++ ) {
+ prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l];
+ nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l];
+ midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2
+ + expand[j+2][i].xyz[l] ) * 0.25;
+ }
+
+ // if the span length is too long, force a subdivision
+ if ( VectorLength( prevxyz ) > minLength
+ || VectorLength( nextxyz ) > minLength ) {
+ break;
+ }
+ // see if this midpoint is off far enough to subdivide
+ VectorSubtract( expand[j+1][i].xyz, midxyz, delta );
+ len = VectorLength( delta );
+ if ( len > maxError ) {
+ break;
+ }
+ }
+
+ if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
+ break; // can't subdivide any more
+ }
+
+ if ( i == out.width ) {
+ continue; // didn't need subdivision
+ }
+
+ // insert two columns and replace the peak
+ out.height += 2;
+
+ for ( i = 0 ; i < out.width ; i++ ) {
+ LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev );
+ LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next );
+ LerpDrawVert( &prev, &next, &mid );
+
+ for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
+ expand[k][i] = expand[k-2][i];
+ }
+ expand[j+1][i] = prev;
+ expand[j+2][i] = mid;
+ expand[j+3][i] = next;
+ }
+
+ // back up and recheck this set again, it may need more subdivision
+ j -= 2;
+
+ }
+
+ // collapse the verts
+
+ out.verts = &expand[0][0];
+ for ( i = 1 ; i < out.height ; i++ ) {
+ memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
+ }
+
+ return CopyMesh(&out);
+}
+
+
+
+/*
+IterationsForCurve() - ydnar
+given a curve of a certain length, return the number of subdivision iterations
+note: this is affected by subdivision amount
+*/
+
+int IterationsForCurve( float len, int subdivisions )
+{
+ int iterations, facets;
+
+
+ /* calculate the number of subdivisions */
+ for( iterations = 0; iterations < 3; iterations++ )
+ {
+ facets = subdivisions * 16 * pow( 2, iterations );
+ if( facets >= len )
+ break;
+ }
+
+ /* return to caller */
+ return iterations;
+}
+
+
+/*
+SubdivideMesh2() - ydnar
+subdivides each mesh quad a specified number of times
+*/
+
+mesh_t *SubdivideMesh2( mesh_t in, int iterations )
+{
+ int i, j, k;
+ bspDrawVert_t prev, next, mid;
+ mesh_t out;
+
+ /* ydnar: static for os x */
+ MAC_STATIC bspDrawVert_t expand[ MAX_EXPANDED_AXIS ][ MAX_EXPANDED_AXIS ];
+
+
+ /* initial setup */
+ out.width = in.width;
+ out.height = in.height;
+ for( i = 0; i < in.width; i++ )
+ {
+ for( j = 0; j < in.height; j++ )
+ expand[ j ][ i ] = in.verts[ j * in.width + i ];
+ }
+
+ /* keep chopping */
+ for( iterations; iterations > 0; iterations-- )
+ {
+ /* horizontal subdivisions */
+ for( j = 0; j + 2 < out.width; j += 4 )
+ {
+ /* check size limit */
+ if( out.width + 2 >= MAX_EXPANDED_AXIS )
+ break;
+
+ /* insert two columns and replace the peak */
+ out.width += 2;
+ for( i = 0; i < out.height; i++ )
+ {
+ LerpDrawVert( &expand[ i ][ j ], &expand[ i ][ j + 1 ], &prev );
+ LerpDrawVert( &expand[ i ][ j + 1 ], &expand[ i ][ j + 2 ], &next );
+ LerpDrawVert( &prev, &next, &mid );
+
+ for ( k = out.width - 1 ; k > j + 3; k-- )
+ expand [ i ][ k ] = expand[ i ][ k - 2 ];
+ expand[ i ][ j + 1 ] = prev;
+ expand[ i ][ j + 2 ] = mid;
+ expand[ i ][ j + 3 ] = next;
+ }
+
+ }
+
+ /* vertical subdivisions */
+ for ( j = 0; j + 2 < out.height; j += 4 )
+ {
+ /* check size limit */
+ if( out.height + 2 >= MAX_EXPANDED_AXIS )
+ break;
+
+ /* insert two columns and replace the peak */
+ out.height += 2;
+ for( i = 0; i < out.width; i++ )
+ {
+ LerpDrawVert( &expand[ j ][ i ], &expand[ j + 1 ][ i ], &prev );
+ LerpDrawVert( &expand[ j + 1 ][ i ], &expand[ j + 2 ][ i ], &next );
+ LerpDrawVert( &prev, &next, &mid );
+
+ for( k = out.height - 1; k > j + 3; k-- )
+ expand[ k ][ i ] = expand[ k - 2 ][ i ];
+ expand[ j + 1 ][ i ] = prev;
+ expand[ j + 2 ][ i ] = mid;
+ expand[ j + 3 ][ i ] = next;
+ }
+ }
+ }
+
+ /* collapse the verts */
+ out.verts = &expand[ 0 ][ 0 ];
+ for( i = 1; i < out.height; i++ )
+ memmove( &out.verts[ i * out.width ], expand[ i ], out.width * sizeof( bspDrawVert_t ) );
+
+ /* return to sender */
+ return CopyMesh( &out );
+}
+
+
+
+
+
+
+
+/*
+================
+ProjectPointOntoVector
+================
+*/
+void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj )
+{
+ vec3_t pVec, vec;
+
+ VectorSubtract( point, vStart, pVec );
+ VectorSubtract( vEnd, vStart, vec );
+ VectorNormalize( vec, vec );
+ // project onto the directional vector for this segment
+ VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );
+}
+
+/*
+================
+RemoveLinearMeshColumsRows
+================
+*/
+mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {
+ int i, j, k;
+ float len, maxLength;
+ vec3_t proj, dir;
+ mesh_t out;
+
+ /* ydnar: static for os x */
+ MAC_STATIC bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
+
+
+ out.width = in->width;
+ out.height = in->height;
+
+ for ( i = 0 ; i < in->width ; i++ ) {
+ for ( j = 0 ; j < in->height ; j++ ) {
+ expand[j][i] = in->verts[j*in->width+i];
+ }
+ }
+
+ for ( j = 1 ; j < out.width - 1; j++ ) {
+ maxLength = 0;
+ for ( i = 0 ; i < out.height ; i++ ) {
+ ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj);
+ VectorSubtract(expand[i][j].xyz, proj, dir);
+ len = VectorLength(dir);
+ if (len > maxLength) {
+ maxLength = len;
+ }
+ }
+ if (maxLength < 0.1)
+ {
+ out.width--;
+ for ( i = 0 ; i < out.height ; i++ ) {
+ for (k = j; k < out.width; k++) {
+ expand[i][k] = expand[i][k+1];
+ }
+ }
+ j--;
+ }
+ }
+ for ( j = 1 ; j < out.height - 1; j++ ) {
+ maxLength = 0;
+ for ( i = 0 ; i < out.width ; i++ ) {
+ ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj);
+ VectorSubtract(expand[j][i].xyz, proj, dir);
+ len = VectorLength(dir);
+ if (len > maxLength) {
+ maxLength = len;
+ }
+ }
+ if (maxLength < 0.1)
+ {
+ out.height--;
+ for ( i = 0 ; i < out.width ; i++ ) {
+ for (k = j; k < out.height; k++) {
+ expand[k][i] = expand[k+1][i];
+ }
+ }
+ j--;
+ }
+ }
+ // collapse the verts
+ out.verts = &expand[0][0];
+ for ( i = 1 ; i < out.height ; i++ ) {
+ memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
+ }
+
+ return CopyMesh(&out);
+}
+
+
+
+/*
+=================
+SubdivideMeshQuads
+=================
+*/
+mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int *widthtable, int *heighttable )
+{
+ int i, j, k, w, h, maxsubdivisions, subdivisions;
+ vec3_t dir;
+ float length, maxLength, amount;
+ mesh_t out;
+ bspDrawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
+
+ out.width = in->width;
+ out.height = in->height;
+
+ for ( i = 0 ; i < in->width ; i++ ) {
+ for ( j = 0 ; j < in->height ; j++ ) {
+ expand[j][i] = in->verts[j*in->width+i];
+ }
+ }
+
+ if (maxsize > MAX_EXPANDED_AXIS)
+ Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS");
+
+ // horizontal subdivisions
+
+ maxsubdivisions = (maxsize - in->width) / (in->width - 1);
+
+ for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) {
+ maxLength = 0;
+ for ( i = 0 ; i < out.height ; i++ ) {
+ VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir);
+ length = VectorLength( dir );
+ if (length > maxLength) {
+ maxLength = length;
+ }
+ }
+
+ subdivisions = (int) (maxLength / minLength);
+ if (subdivisions > maxsubdivisions)
+ subdivisions = maxsubdivisions;
+
+ widthtable[w] = subdivisions + 1;
+ if (subdivisions <= 0)
+ continue;
+
+ out.width += subdivisions;
+
+ for ( i = 0 ; i < out.height ; i++ ) {
+ for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {
+ expand[i][k] = expand[i][k-subdivisions];
+ }
+ for (k = 1; k <= subdivisions; k++)
+ {
+ amount = (float) k / (subdivisions + 1);
+ LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]);
+ }
+ }
+ }
+
+ maxsubdivisions = (maxsize - in->height) / (in->height - 1);
+
+ for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) {
+ maxLength = 0;
+ for ( i = 0 ; i < out.width ; i++ ) {
+ VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir);
+ length = VectorLength( dir );
+ if (length > maxLength) {
+ maxLength = length;
+ }
+ }
+
+ subdivisions = (int) (maxLength / minLength);
+ if (subdivisions > maxsubdivisions)
+ subdivisions = maxsubdivisions;
+
+ heighttable[h] = subdivisions + 1;
+ if (subdivisions <= 0)
+ continue;
+
+ out.height += subdivisions;
+
+ for ( i = 0 ; i < out.width ; i++ ) {
+ for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {
+ expand[k][i] = expand[k-subdivisions][i];
+ }
+ for (k = 1; k <= subdivisions; k++)
+ {
+ amount = (float) k / (subdivisions + 1);
+ LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]);
+ }
+ }
+ }
+
+ // collapse the verts
+ out.verts = &expand[0][0];
+ for ( i = 1 ; i < out.height ; i++ ) {
+ memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
+ }
+
+ return CopyMesh(&out);
+}
projects / xonotic / netradiant.git / blobdiff