-/*\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 PATCH_C\r
-\r
-\r
-\r
-/* dependencies */\r
-#include "q3map2.h"\r
-\r
-\r
-\r
-/*\r
-ExpandLongestCurve() - ydnar\r
-finds length of quadratic curve specified and determines if length is longer than the supplied max\r
-*/\r
-\r
-#define APPROX_SUBDIVISION 8\r
-\r
-static void ExpandLongestCurve( float *longestCurve, vec3_t a, vec3_t b, vec3_t c )\r
-{\r
- int i;\r
- float t, len;\r
- vec3_t ab, bc, ac, pt, last, delta;\r
- \r
- \r
- /* calc vectors */\r
- VectorSubtract( b, a, ab );\r
- if( VectorNormalize( ab, ab ) < 0.125f )\r
- return;\r
- VectorSubtract( c, b, bc );\r
- if( VectorNormalize( bc, bc ) < 0.125f )\r
- return;\r
- VectorSubtract( c, a, ac );\r
- if( VectorNormalize( ac, ac ) < 0.125f )\r
- return;\r
- \r
- /* if all 3 vectors are the same direction, then this edge is linear, so we ignore it */\r
- if( DotProduct( ab, bc ) > 0.99f && DotProduct( ab, ac ) > 0.99f )\r
- return;\r
- \r
- /* recalculate vectors */\r
- VectorSubtract( b, a, ab );\r
- VectorSubtract( c, b, bc );\r
- \r
- /* determine length */\r
- VectorCopy( a, last );\r
- for( i = 0, len = 0.0f, t = 0.0f; i < APPROX_SUBDIVISION; i++, t += (1.0f / APPROX_SUBDIVISION) )\r
- {\r
- /* calculate delta */\r
- delta[ 0 ] = ((1.0f - t) * ab[ 0 ]) + (t * bc[ 0 ]);\r
- delta[ 1 ] = ((1.0f - t) * ab[ 1 ]) + (t * bc[ 1 ]);\r
- delta[ 2 ] = ((1.0f - t) * ab[ 2 ]) + (t * bc[ 2 ]);\r
- \r
- /* add to first point and calculate pt-pt delta */\r
- VectorAdd( a, delta, pt );\r
- VectorSubtract( pt, last, delta );\r
- \r
- /* add it to length and store last point */\r
- len += VectorLength( delta );\r
- VectorCopy( pt, last );\r
- }\r
- \r
- /* longer? */\r
- if( len > *longestCurve )\r
- *longestCurve = len;\r
-}\r
-\r
-\r
-\r
-/*\r
-ExpandMaxIterations() - ydnar\r
-determines how many iterations a quadratic curve needs to be subdivided with to fit the specified error\r
-*/\r
-\r
-static void ExpandMaxIterations( int *maxIterations, int maxError, vec3_t a, vec3_t b, vec3_t c )\r
-{\r
- int i, j;\r
- vec3_t prev, next, mid, delta, delta2;\r
- float len, len2;\r
- int numPoints, iterations;\r
- vec3_t points[ MAX_EXPANDED_AXIS ];\r
- \r
- \r
- /* initial setup */\r
- numPoints = 3;\r
- VectorCopy( a, points[ 0 ] );\r
- VectorCopy( b, points[ 1 ] );\r
- VectorCopy( c, points[ 2 ] );\r
-\r
- /* subdivide */\r
- for( i = 0; i + 2 < numPoints; i += 2 )\r
- {\r
- /* check subdivision limit */\r
- if( numPoints + 2 >= MAX_EXPANDED_AXIS )\r
- break;\r
- \r
- /* calculate new curve deltas */\r
- for( j = 0; j < 3; j++ )\r
- {\r
- prev[ j ] = points[ i + 1 ][ j ] - points[ i ][ j ]; \r
- next[ j ] = points[ i + 2 ][ j ] - points[ i + 1 ][ j ]; \r
- mid[ j ] = (points[ i ][ j ] + points[ i + 1 ][ j ] * 2.0f + points[ i + 2 ][ j ]) * 0.25f;\r
- }\r
- \r
- /* see if this midpoint is off far enough to subdivide */\r
- VectorSubtract( points[ i + 1 ], mid, delta );\r
- len = VectorLength( delta );\r
- if( len < maxError )\r
- continue;\r
- \r
- /* subdivide */\r
- numPoints += 2;\r
- \r
- /* create new points */\r
- for( j = 0; j < 3; j++ )\r
- {\r
- prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ]);\r
- next[ j ] = 0.5f * (points[ i + 1 ][ j ] + points[ i + 2 ][ j ]);\r
- mid[ j ] = 0.5f * (prev[ j ] + next[ j ]);\r
- }\r
- \r
- /* push points out */\r
- for( j = numPoints - 1; j > i + 3; j-- )\r
- VectorCopy( points[ j - 2 ], points[ j ] );\r
- \r
- /* insert new points */\r
- VectorCopy( prev, points[ i + 1 ] );\r
- VectorCopy( mid, points[ i + 2 ] );\r
- VectorCopy( next, points[ i + 3 ] );\r
-\r
- /* back up and recheck this set again, it may need more subdivision */\r
- i -= 2;\r
- }\r
- \r
- /* put the line on the curve */\r
- for( i = 1; i < numPoints; i += 2 )\r
- {\r
- for( j = 0; j < 3; j++ )\r
- {\r
- prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ] );\r
- next[ j ] = 0.5f * (points[ i ][ j ] + points[ i - 1 ][ j ] );\r
- points[ i ][ j ] = 0.5f * (prev[ j ] + next[ j ]);\r
- }\r
- }\r
- \r
- /* eliminate linear sections */\r
- for( i = 0; i + 2 < numPoints; i++ )\r
- {\r
- /* create vectors */\r
- VectorSubtract( points[ i + 1 ], points[ i ], delta );\r
- len = VectorNormalize( delta, delta );\r
- VectorSubtract( points[ i + 2 ], points[ i + 1 ], delta2 );\r
- len2 = VectorNormalize( delta2, delta2 );\r
- \r
- /* if either edge is degenerate, then eliminate it */\r
- if( len < 0.0625f || len2 < 0.0625f || DotProduct( delta, delta2 ) >= 1.0f )\r
- {\r
- for( j = i + 1; j + 1 < numPoints; j++ )\r
- VectorCopy( points[ j + 1 ], points[ j ] );\r
- numPoints--;\r
- continue;\r
- }\r
- }\r
- \r
- /* the number of iterations is 2^(points - 1) - 1 */\r
- numPoints >>= 1;\r
- iterations = 0;\r
- while( numPoints > 1 )\r
- {\r
- numPoints >>= 1;\r
- iterations++;\r
- }\r
- \r
- /* more? */\r
- if( iterations > *maxIterations )\r
- *maxIterations = iterations;\r
-}\r
-\r
-\r
-\r
-/*\r
-ParsePatch()\r
-creates a mapDrawSurface_t from the patch text\r
-*/\r
-\r
-void ParsePatch( qboolean onlyLights )\r
-{\r
- vec_t info[ 5 ];\r
- int i, j, k;\r
- parseMesh_t *pm;\r
- char texture[ MAX_QPATH ];\r
- char shader[ MAX_QPATH ];\r
- mesh_t m;\r
- bspDrawVert_t *verts;\r
- epair_t *ep;\r
- vec4_t delta, delta2, delta3;\r
- qboolean degenerate;\r
- float longestCurve;\r
- int maxIterations;\r
- \r
- \r
- MatchToken( "{" );\r
- \r
- /* get texture */\r
- GetToken( qtrue );\r
- strcpy( texture, token );\r
- \r
- Parse1DMatrix( 5, info );\r
- m.width = info[0];\r
- m.height = info[1];\r
- m.verts = verts = safe_malloc( m.width * m.height * sizeof( m.verts[0] ) );\r
- \r
- if( m.width < 0 || m.width > MAX_PATCH_SIZE || m.height < 0 || m.height > MAX_PATCH_SIZE )\r
- Error( "ParsePatch: bad size" );\r
- \r
- MatchToken( "(" );\r
- for( j = 0; j < m.width ; j++ )\r
- {\r
- MatchToken( "(" );\r
- for( i = 0; i < m.height ; i++ )\r
- {\r
- Parse1DMatrix( 5, verts[ i * m.width + j ].xyz );\r
- \r
- /* ydnar: fix colors */\r
- for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
- {\r
- verts[ i * m.width + j ].color[ k ][ 0 ] = 255;\r
- verts[ i * m.width + j ].color[ k ][ 1 ] = 255;\r
- verts[ i * m.width + j ].color[ k ][ 2 ] = 255;\r
- verts[ i * m.width + j ].color[ k ][ 3 ] = 255;\r
- }\r
- }\r
- MatchToken( ")" );\r
- }\r
- MatchToken( ")" );\r
-\r
- // if brush primitives format, we may have some epairs to ignore here\r
- GetToken(qtrue);\r
- if (g_bBrushPrimit!=BPRIMIT_OLDBRUSHES && strcmp(token,"}"))\r
- {\r
- // NOTE: we leak that!\r
- ep = ParseEPair();\r
- }\r
- else\r
- UnGetToken();\r
-\r
- MatchToken( "}" );\r
- MatchToken( "}" );\r
- \r
- /* short circuit */\r
- if( noCurveBrushes || onlyLights )\r
- return;\r
- \r
- \r
- /* ydnar: delete and warn about degenerate patches */\r
- j = (m.width * m.height);\r
- VectorClear( delta );\r
- delta[ 3 ] = 0;\r
- degenerate = qtrue;\r
- \r
- /* find first valid vector */\r
- for( i = 1; i < j && delta[ 3 ] == 0; i++ )\r
- {\r
- VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta );\r
- delta[ 3 ] = VectorNormalize( delta, delta );\r
- }\r
- \r
- /* secondary degenerate test */\r
- if( delta[ 3 ] == 0 )\r
- degenerate = qtrue;\r
- else\r
- {\r
- /* if all vectors match this or are zero, then this is a degenerate patch */\r
- for( i = 1; i < j && degenerate == qtrue; i++ )\r
- {\r
- VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta2 );\r
- delta2[ 3 ] = VectorNormalize( delta2, delta2 );\r
- if( delta2[ 3 ] != 0 )\r
- {\r
- /* create inverse vector */\r
- VectorCopy( delta2, delta3 );\r
- delta3[ 3 ] = delta2[ 3 ];\r
- VectorInverse( delta3 );\r
- \r
- /* compare */\r
- if( VectorCompare( delta, delta2 ) == qfalse && VectorCompare( delta, delta3 ) == qfalse )\r
- degenerate = qfalse;\r
- }\r
- }\r
- }\r
- \r
- /* warn and select degenerate patch */\r
- if( degenerate )\r
- {\r
- xml_Select( "degenerate patch", mapEnt->mapEntityNum, entitySourceBrushes, qfalse );\r
- free( m.verts );\r
- return;\r
- }\r
- \r
- /* find longest curve on the mesh */\r
- longestCurve = 0.0f;\r
- maxIterations = 0;\r
- for( j = 0; j + 2 < m.width; j += 2 )\r
- {\r
- for( i = 0; i + 2 < m.height; i += 2 )\r
- {\r
- ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ i * m.width + (j + 1) ].xyz, verts[ i * m.width + (j + 2) ].xyz ); /* row */\r
- ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ (i + 1) * m.width + j ].xyz, verts[ (i + 2) * m.width + j ].xyz ); /* col */\r
- ExpandMaxIterations( &maxIterations, patchSubdivisions, verts[ i * m.width + j ].xyz, verts[ i * m.width + (j + 1) ].xyz, verts[ i * m.width + (j + 2) ].xyz ); /* row */\r
- ExpandMaxIterations( &maxIterations, patchSubdivisions, verts[ i * m.width + j ].xyz, verts[ (i + 1) * m.width + j ].xyz, verts[ (i + 2) * m.width + j ].xyz ); /* col */\r
- }\r
- }\r
- \r
- /* allocate patch mesh */\r
- pm = safe_malloc( sizeof( *pm ) );\r
- memset( pm, 0, sizeof( *pm ) );\r
- \r
- /* ydnar: add entity/brush numbering */\r
- pm->entityNum = mapEnt->mapEntityNum;\r
- pm->brushNum = entitySourceBrushes;\r
- \r
- /* set shader */\r
- sprintf( shader, "textures/%s", texture );\r
- pm->shaderInfo = ShaderInfoForShader( shader );\r
- \r
- /* set mesh */\r
- pm->mesh = m;\r
- \r
- /* set longest curve */\r
- pm->longestCurve = longestCurve;\r
- pm->maxIterations = maxIterations;\r
- \r
- /* link to the entity */\r
- pm->next = mapEnt->patches;\r
- mapEnt->patches = pm;\r
-}\r
-\r
-\r
-\r
-/*\r
-GrowGroup_r()\r
-recursively adds patches to a lod group\r
-*/\r
-\r
-static void GrowGroup_r( parseMesh_t *pm, int patchNum, int patchCount, parseMesh_t **meshes, byte *bordering, byte *group )\r
-{\r
- int i;\r
- const byte *row;\r
- \r
- \r
- /* early out check */\r
- if( group[ patchNum ] )\r
- return;\r
- \r
- \r
- /* set it */\r
- group[ patchNum ] = 1;\r
- row = bordering + patchNum * patchCount;\r
- \r
- /* check maximums */\r
- if( meshes[ patchNum ]->longestCurve > pm->longestCurve )\r
- pm->longestCurve = meshes[ patchNum ]->longestCurve;\r
- if( meshes[ patchNum ]->maxIterations > pm->maxIterations )\r
- pm->maxIterations = meshes[ patchNum ]->maxIterations;\r
- \r
- /* walk other patches */\r
- for( i = 0; i < patchCount; i++ )\r
- {\r
- if( row[ i ] )\r
- GrowGroup_r( pm, i, patchCount, meshes, bordering, group );\r
- }\r
-}\r
-\r
-\r
-/*\r
-PatchMapDrawSurfs()\r
-any patches that share an edge need to choose their\r
-level of detail as a unit, otherwise the edges would\r
-pull apart.\r
-*/\r
-\r
-void PatchMapDrawSurfs( entity_t *e )\r
-{\r
- int i, j, k, l, c1, c2;\r
- parseMesh_t *pm;\r
- parseMesh_t *check, *scan;\r
- mapDrawSurface_t *ds;\r
- int patchCount, groupCount;\r
- bspDrawVert_t *v1, *v2;\r
- vec3_t bounds[ 2 ];\r
- byte *bordering;\r
- \r
- /* ydnar: mac os x fails with these if not static */\r
- MAC_STATIC parseMesh_t *meshes[ MAX_MAP_DRAW_SURFS ];\r
- MAC_STATIC qb_t grouped[ MAX_MAP_DRAW_SURFS ];\r
- MAC_STATIC byte group[ MAX_MAP_DRAW_SURFS ];\r
- \r
- \r
- /* note it */\r
- Sys_FPrintf( SYS_VRB, "--- PatchMapDrawSurfs ---\n" );\r
-\r
- patchCount = 0;\r
- for ( pm = e->patches ; pm ; pm = pm->next ) {\r
- meshes[patchCount] = pm;\r
- patchCount++;\r
- }\r
-\r
- if ( !patchCount ) {\r
- return;\r
- }\r
- bordering = safe_malloc( patchCount * patchCount );\r
- memset( bordering, 0, patchCount * patchCount );\r
-\r
- // build the bordering matrix\r
- for ( k = 0 ; k < patchCount ; k++ ) {\r
- bordering[k*patchCount+k] = 1;\r
-\r
- for ( l = k+1 ; l < patchCount ; l++ ) {\r
- check = meshes[k];\r
- scan = meshes[l];\r
- c1 = scan->mesh.width * scan->mesh.height;\r
- v1 = scan->mesh.verts;\r
-\r
- for ( i = 0 ; i < c1 ; i++, v1++ ) {\r
- c2 = check->mesh.width * check->mesh.height;\r
- v2 = check->mesh.verts;\r
- for ( j = 0 ; j < c2 ; j++, v2++ ) {\r
- if ( fabs( v1->xyz[0] - v2->xyz[0] ) < 1.0\r
- && fabs( v1->xyz[1] - v2->xyz[1] ) < 1.0\r
- && fabs( v1->xyz[2] - v2->xyz[2] ) < 1.0 ) {\r
- break;\r
- }\r
- }\r
- if ( j != c2 ) {\r
- break;\r
- }\r
- }\r
- if ( i != c1 ) {\r
- // we have a connection\r
- bordering[k*patchCount+l] =\r
- bordering[l*patchCount+k] = 1;\r
- } else {\r
- // no connection\r
- bordering[k*patchCount+l] =\r
- bordering[l*patchCount+k] = 0;\r
- }\r
-\r
- }\r
- }\r
-\r
- /* build groups */\r
- memset( grouped, 0, patchCount );\r
- groupCount = 0;\r
- for ( i = 0; i < patchCount; i++ )\r
- {\r
- /* get patch */\r
- scan = meshes[ i ];\r
- \r
- /* start a new group */\r
- if( !grouped[ i ] )\r
- groupCount++;\r
- \r
- /* recursively find all patches that belong in the same group */\r
- memset( group, 0, patchCount );\r
- GrowGroup_r( scan, i, patchCount, meshes, bordering, group );\r
- \r
- /* bound them */\r
- ClearBounds( bounds[ 0 ], bounds[ 1 ] );\r
- for( j = 0; j < patchCount; j++ )\r
- {\r
- if ( group[ j ] )\r
- {\r
- grouped[ j ] = qtrue;\r
- check = meshes[ j ];\r
- c1 = check->mesh.width * check->mesh.height;\r
- v1 = check->mesh.verts;\r
- for( k = 0; k < c1; k++, v1++ )\r
- AddPointToBounds( v1->xyz, bounds[ 0 ], bounds[ 1 ] );\r
- }\r
- }\r
- \r
- /* debug code */\r
- //% Sys_Printf( "Longest curve: %f Iterations: %d\n", scan->longestCurve, scan->maxIterations );\r
- \r
- /* create drawsurf */\r
- scan->grouped = qtrue;\r
- ds = DrawSurfaceForMesh( e, scan, NULL ); /* ydnar */\r
- VectorCopy( bounds[ 0 ], ds->bounds[ 0 ] );\r
- VectorCopy( bounds[ 1 ], ds->bounds[ 1 ] );\r
- }\r
- \r
- /* emit some statistics */\r
- Sys_FPrintf( SYS_VRB, "%9d patches\n", patchCount );\r
- Sys_FPrintf( SYS_VRB, "%9d patch LOD groups\n", groupCount );\r
-}\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 PATCH_C
+
+
+
+/* dependencies */
+#include "q3map2.h"
+
+
+
+/*
+ ExpandLongestCurve() - ydnar
+ finds length of quadratic curve specified and determines if length is longer than the supplied max
+ */
+
+#define APPROX_SUBDIVISION 8
+
+static void ExpandLongestCurve( float *longestCurve, vec3_t a, vec3_t b, vec3_t c ){
+ int i;
+ float t, len;
+ vec3_t ab, bc, ac, pt, last, delta;
+
+
+ /* calc vectors */
+ VectorSubtract( b, a, ab );
+ if ( VectorNormalize( ab, ab ) < 0.125f ) {
+ return;
+ }
+ VectorSubtract( c, b, bc );
+ if ( VectorNormalize( bc, bc ) < 0.125f ) {
+ return;
+ }
+ VectorSubtract( c, a, ac );
+ if ( VectorNormalize( ac, ac ) < 0.125f ) {
+ return;
+ }
+
+ /* if all 3 vectors are the same direction, then this edge is linear, so we ignore it */
+ if ( DotProduct( ab, bc ) > 0.99f && DotProduct( ab, ac ) > 0.99f ) {
+ return;
+ }
+
+ /* recalculate vectors */
+ VectorSubtract( b, a, ab );
+ VectorSubtract( c, b, bc );
+
+ /* determine length */
+ VectorCopy( a, last );
+ for ( i = 0, len = 0.0f, t = 0.0f; i < APPROX_SUBDIVISION; i++, t += ( 1.0f / APPROX_SUBDIVISION ) )
+ {
+ /* calculate delta */
+ delta[ 0 ] = ( ( 1.0f - t ) * ab[ 0 ] ) + ( t * bc[ 0 ] );
+ delta[ 1 ] = ( ( 1.0f - t ) * ab[ 1 ] ) + ( t * bc[ 1 ] );
+ delta[ 2 ] = ( ( 1.0f - t ) * ab[ 2 ] ) + ( t * bc[ 2 ] );
+
+ /* add to first point and calculate pt-pt delta */
+ VectorAdd( a, delta, pt );
+ VectorSubtract( pt, last, delta );
+
+ /* add it to length and store last point */
+ len += VectorLength( delta );
+ VectorCopy( pt, last );
+ }
+
+ /* longer? */
+ if ( len > *longestCurve ) {
+ *longestCurve = len;
+ }
+}
+
+
+
+/*
+ ExpandMaxIterations() - ydnar
+ determines how many iterations a quadratic curve needs to be subdivided with to fit the specified error
+ */
+
+static void ExpandMaxIterations( int *maxIterations, int maxError, vec3_t a, vec3_t b, vec3_t c ){
+ int i, j;
+ vec3_t prev, next, mid, delta, delta2;
+ float len, len2;
+ int numPoints, iterations;
+ vec3_t points[ MAX_EXPANDED_AXIS ];
+
+
+ /* initial setup */
+ numPoints = 3;
+ VectorCopy( a, points[ 0 ] );
+ VectorCopy( b, points[ 1 ] );
+ VectorCopy( c, points[ 2 ] );
+
+ /* subdivide */
+ for ( i = 0; i + 2 < numPoints; i += 2 )
+ {
+ /* check subdivision limit */
+ if ( numPoints + 2 >= MAX_EXPANDED_AXIS ) {
+ break;
+ }
+
+ /* calculate new curve deltas */
+ for ( j = 0; j < 3; j++ )
+ {
+ prev[ j ] = points[ i + 1 ][ j ] - points[ i ][ j ];
+ next[ j ] = points[ i + 2 ][ j ] - points[ i + 1 ][ j ];
+ mid[ j ] = ( points[ i ][ j ] + points[ i + 1 ][ j ] * 2.0f + points[ i + 2 ][ j ] ) * 0.25f;
+ }
+
+ /* see if this midpoint is off far enough to subdivide */
+ VectorSubtract( points[ i + 1 ], mid, delta );
+ len = VectorLength( delta );
+ if ( len < maxError ) {
+ continue;
+ }
+
+ /* subdivide */
+ numPoints += 2;
+
+ /* create new points */
+ for ( j = 0; j < 3; j++ )
+ {
+ prev[ j ] = 0.5f * ( points[ i ][ j ] + points[ i + 1 ][ j ] );
+ next[ j ] = 0.5f * ( points[ i + 1 ][ j ] + points[ i + 2 ][ j ] );
+ mid[ j ] = 0.5f * ( prev[ j ] + next[ j ] );
+ }
+
+ /* push points out */
+ for ( j = numPoints - 1; j > i + 3; j-- )
+ VectorCopy( points[ j - 2 ], points[ j ] );
+
+ /* insert new points */
+ VectorCopy( prev, points[ i + 1 ] );
+ VectorCopy( mid, points[ i + 2 ] );
+ VectorCopy( next, points[ i + 3 ] );
+
+ /* back up and recheck this set again, it may need more subdivision */
+ i -= 2;
+ }
+
+ /* put the line on the curve */
+ for ( i = 1; i < numPoints; i += 2 )
+ {
+ for ( j = 0; j < 3; j++ )
+ {
+ prev[ j ] = 0.5f * ( points[ i ][ j ] + points[ i + 1 ][ j ] );
+ next[ j ] = 0.5f * ( points[ i ][ j ] + points[ i - 1 ][ j ] );
+ points[ i ][ j ] = 0.5f * ( prev[ j ] + next[ j ] );
+ }
+ }
+
+ /* eliminate linear sections */
+ for ( i = 0; i + 2 < numPoints; i++ )
+ {
+ /* create vectors */
+ VectorSubtract( points[ i + 1 ], points[ i ], delta );
+ len = VectorNormalize( delta, delta );
+ VectorSubtract( points[ i + 2 ], points[ i + 1 ], delta2 );
+ len2 = VectorNormalize( delta2, delta2 );
+
+ /* if either edge is degenerate, then eliminate it */
+ if ( len < 0.0625f || len2 < 0.0625f || DotProduct( delta, delta2 ) >= 1.0f ) {
+ for ( j = i + 1; j + 1 < numPoints; j++ )
+ VectorCopy( points[ j + 1 ], points[ j ] );
+ numPoints--;
+ continue;
+ }
+ }
+
+ /* the number of iterations is 2^(points - 1) - 1 */
+ numPoints >>= 1;
+ iterations = 0;
+ while ( numPoints > 1 )
+ {
+ numPoints >>= 1;
+ iterations++;
+ }
+
+ /* more? */
+ if ( iterations > *maxIterations ) {
+ *maxIterations = iterations;
+ }
+}
+
+
+
+/*
+ ParsePatch()
+ creates a mapDrawSurface_t from the patch text
+ */
+
+void ParsePatch( qboolean onlyLights ){
+ vec_t info[ 5 ];
+ int i, j, k;
+ parseMesh_t *pm;
+ char texture[ MAX_QPATH ];
+ char shader[ MAX_QPATH ];
+ mesh_t m;
+ bspDrawVert_t *verts;
+ epair_t *ep;
+ vec4_t delta, delta2, delta3;
+ qboolean degenerate;
+ float longestCurve;
+ int maxIterations;
+
+ MatchToken( "{" );
+
+ /* get texture */
+ GetToken( qtrue );
+ strcpy( texture, token );
+
+ Parse1DMatrix( 5, info );
+ m.width = info[0];
+ m.height = info[1];
+ m.verts = verts = safe_malloc( m.width * m.height * sizeof( m.verts[0] ) );
+
+ if ( m.width < 0 || m.width > MAX_PATCH_SIZE || m.height < 0 || m.height > MAX_PATCH_SIZE ) {
+ Error( "ParsePatch: bad size" );
+ }
+
+ MatchToken( "(" );
+ for ( j = 0; j < m.width ; j++ )
+ {
+ MatchToken( "(" );
+ for ( i = 0; i < m.height ; i++ )
+ {
+ Parse1DMatrix( 5, verts[ i * m.width + j ].xyz );
+
+ /* ydnar: fix colors */
+ for ( k = 0; k < MAX_LIGHTMAPS; k++ )
+ {
+ verts[ i * m.width + j ].color[ k ][ 0 ] = 255;
+ verts[ i * m.width + j ].color[ k ][ 1 ] = 255;
+ verts[ i * m.width + j ].color[ k ][ 2 ] = 255;
+ verts[ i * m.width + j ].color[ k ][ 3 ] = 255;
+ }
+ }
+ MatchToken( ")" );
+ }
+ MatchToken( ")" );
+
+ // if brush primitives format, we may have some epairs to ignore here
+ GetToken( qtrue );
+ if ( g_bBrushPrimit != BPRIMIT_OLDBRUSHES && strcmp( token,"}" ) ) {
+ ep = ParseEPair();
+ free( ep->key );
+ free( ep->value );
+ free( ep );
+ }
+ else{
+ UnGetToken();
+ }
+
+ MatchToken( "}" );
+ MatchToken( "}" );
+
+ /* short circuit */
+ if ( noCurveBrushes || onlyLights ) {
+ return;
+ }
+
+
+ /* ydnar: delete and warn about degenerate patches */
+ j = ( m.width * m.height );
+ VectorClear( delta );
+ delta[ 3 ] = 0;
+ degenerate = qtrue;
+
+ /* find first valid vector */
+ for ( i = 1; i < j && delta[ 3 ] == 0; i++ )
+ {
+ VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta );
+ delta[ 3 ] = VectorNormalize( delta, delta );
+ }
+
+ /* secondary degenerate test */
+ if ( delta[ 3 ] == 0 ) {
+ degenerate = qtrue;
+ }
+ else
+ {
+ /* if all vectors match this or are zero, then this is a degenerate patch */
+ for ( i = 1; i < j && degenerate == qtrue; i++ )
+ {
+ VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta2 );
+ delta2[ 3 ] = VectorNormalize( delta2, delta2 );
+ if ( delta2[ 3 ] != 0 ) {
+ /* create inverse vector */
+ VectorCopy( delta2, delta3 );
+ delta3[ 3 ] = delta2[ 3 ];
+ VectorInverse( delta3 );
+
+ /* compare */
+ if ( VectorCompare( delta, delta2 ) == qfalse && VectorCompare( delta, delta3 ) == qfalse ) {
+ degenerate = qfalse;
+ }
+ }
+ }
+ }
+
+ /* warn and select degenerate patch */
+ if ( degenerate ) {
+ xml_Select( "degenerate patch", mapEnt->mapEntityNum, entitySourceBrushes, qfalse );
+ free( m.verts );
+ return;
+ }
+
+ /* find longest curve on the mesh */
+ longestCurve = 0.0f;
+ maxIterations = 0;
+ for ( j = 0; j + 2 < m.width; j += 2 )
+ {
+ for ( i = 0; i + 2 < m.height; i += 2 )
+ {
+ ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ i * m.width + ( j + 1 ) ].xyz, verts[ i * m.width + ( j + 2 ) ].xyz ); /* row */
+ ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ ( i + 1 ) * m.width + j ].xyz, verts[ ( i + 2 ) * m.width + j ].xyz ); /* col */
+ ExpandMaxIterations( &maxIterations, patchSubdivisions, verts[ i * m.width + j ].xyz, verts[ i * m.width + ( j + 1 ) ].xyz, verts[ i * m.width + ( j + 2 ) ].xyz ); /* row */
+ ExpandMaxIterations( &maxIterations, patchSubdivisions, verts[ i * m.width + j ].xyz, verts[ ( i + 1 ) * m.width + j ].xyz, verts[ ( i + 2 ) * m.width + j ].xyz ); /* col */
+ }
+ }
+
+ /* allocate patch mesh */
+ pm = safe_malloc0( sizeof( *pm ) );
+
+ /* ydnar: add entity/brush numbering */
+ pm->entityNum = mapEnt->mapEntityNum;
+ pm->brushNum = entitySourceBrushes;
+
+ /* set shader */
+ sprintf( shader, "textures/%s", texture );
+ pm->shaderInfo = ShaderInfoForShader( shader );
+
+ /* set mesh */
+ pm->mesh = m;
+
+ /* set longest curve */
+ pm->longestCurve = longestCurve;
+ pm->maxIterations = maxIterations;
+
+ /* link to the entity */
+ pm->next = mapEnt->patches;
+ mapEnt->patches = pm;
+}
+
+
+
+/*
+ GrowGroup_r()
+ recursively adds patches to a lod group
+ */
+
+static void GrowGroup_r( parseMesh_t *pm, int patchNum, int patchCount, parseMesh_t **meshes, byte *bordering, byte *group ){
+ int i;
+ const byte *row;
+
+
+ /* early out check */
+ if ( group[ patchNum ] ) {
+ return;
+ }
+
+
+ /* set it */
+ group[ patchNum ] = 1;
+ row = bordering + patchNum * patchCount;
+
+ /* check maximums */
+ if ( meshes[ patchNum ]->longestCurve > pm->longestCurve ) {
+ pm->longestCurve = meshes[ patchNum ]->longestCurve;
+ }
+ if ( meshes[ patchNum ]->maxIterations > pm->maxIterations ) {
+ pm->maxIterations = meshes[ patchNum ]->maxIterations;
+ }
+
+ /* walk other patches */
+ for ( i = 0; i < patchCount; i++ )
+ {
+ if ( row[ i ] ) {
+ GrowGroup_r( pm, i, patchCount, meshes, bordering, group );
+ }
+ }
+}
+
+
+/*
+ PatchMapDrawSurfs()
+ any patches that share an edge need to choose their
+ level of detail as a unit, otherwise the edges would
+ pull apart.
+ */
+
+void PatchMapDrawSurfs( entity_t *e ){
+ int i, j, k, l, c1, c2;
+ parseMesh_t *pm;
+ parseMesh_t *check, *scan;
+ mapDrawSurface_t *ds;
+ int patchCount, groupCount;
+ bspDrawVert_t *v1, *v2;
+ vec3_t bounds[ 2 ];
+ byte *bordering;
+
+ parseMesh_t *meshes[ MAX_MAP_DRAW_SURFS ];
+ qb_t grouped[ MAX_MAP_DRAW_SURFS ];
+ byte group[ MAX_MAP_DRAW_SURFS ];
+
+
+ /* note it */
+ Sys_FPrintf( SYS_VRB, "--- PatchMapDrawSurfs ---\n" );
+
+ patchCount = 0;
+ for ( pm = e->patches ; pm ; pm = pm->next ) {
+ meshes[patchCount] = pm;
+ patchCount++;
+ }
+
+ if ( !patchCount ) {
+ return;
+ }
+ bordering = safe_malloc0( patchCount * patchCount );
+
+ // build the bordering matrix
+ for ( k = 0 ; k < patchCount ; k++ ) {
+ bordering[k * patchCount + k] = 1;
+
+ for ( l = k + 1 ; l < patchCount ; l++ ) {
+ check = meshes[k];
+ scan = meshes[l];
+ c1 = scan->mesh.width * scan->mesh.height;
+ v1 = scan->mesh.verts;
+
+ for ( i = 0 ; i < c1 ; i++, v1++ ) {
+ c2 = check->mesh.width * check->mesh.height;
+ v2 = check->mesh.verts;
+ for ( j = 0 ; j < c2 ; j++, v2++ ) {
+ if ( fabs( v1->xyz[0] - v2->xyz[0] ) < 1.0
+ && fabs( v1->xyz[1] - v2->xyz[1] ) < 1.0
+ && fabs( v1->xyz[2] - v2->xyz[2] ) < 1.0 ) {
+ break;
+ }
+ }
+ if ( j != c2 ) {
+ break;
+ }
+ }
+ if ( i != c1 ) {
+ // we have a connection
+ bordering[k * patchCount + l] =
+ bordering[l * patchCount + k] = 1;
+ }
+ else {
+ // no connection
+ bordering[k * patchCount + l] =
+ bordering[l * patchCount + k] = 0;
+ }
+
+ }
+ }
+
+ /* build groups */
+ memset( grouped, 0, patchCount );
+ groupCount = 0;
+ for ( i = 0; i < patchCount; i++ )
+ {
+ /* get patch */
+ scan = meshes[ i ];
+
+ /* start a new group */
+ if ( !grouped[ i ] ) {
+ groupCount++;
+ }
+
+ /* recursively find all patches that belong in the same group */
+ memset( group, 0, patchCount );
+ GrowGroup_r( scan, i, patchCount, meshes, bordering, group );
+
+ /* bound them */
+ ClearBounds( bounds[ 0 ], bounds[ 1 ] );
+ for ( j = 0; j < patchCount; j++ )
+ {
+ if ( group[ j ] ) {
+ grouped[ j ] = qtrue;
+ check = meshes[ j ];
+ c1 = check->mesh.width * check->mesh.height;
+ v1 = check->mesh.verts;
+ for ( k = 0; k < c1; k++, v1++ )
+ AddPointToBounds( v1->xyz, bounds[ 0 ], bounds[ 1 ] );
+ }
+ }
+
+ /* debug code */
+ //% Sys_Printf( "Longest curve: %f Iterations: %d\n", scan->longestCurve, scan->maxIterations );
+
+ /* create drawsurf */
+ scan->grouped = qtrue;
+ ds = DrawSurfaceForMesh( e, scan, NULL ); /* ydnar */
+ VectorCopy( bounds[ 0 ], ds->bounds[ 0 ] );
+ VectorCopy( bounds[ 1 ], ds->bounds[ 1 ] );
+ }
+
+ /* emit some statistics */
+ Sys_FPrintf( SYS_VRB, "%9d patches\n", patchCount );
+ Sys_FPrintf( SYS_VRB, "%9d patch LOD groups\n", groupCount );
+}