2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
\r
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
\r
5 This file is part of GtkRadiant.
\r
7 GtkRadiant is free software; you can redistribute it and/or modify
\r
8 it under the terms of the GNU General Public License as published by
\r
9 the Free Software Foundation; either version 2 of the License, or
\r
10 (at your option) any later version.
\r
12 GtkRadiant is distributed in the hope that it will be useful,
\r
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
15 GNU General Public License for more details.
\r
17 You should have received a copy of the GNU General Public License
\r
18 along with GtkRadiant; if not, write to the Free Software
\r
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
\r
21 ----------------------------------------------------------------------------------
\r
23 This code has been altered significantly from its original form, to support
\r
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
\r
26 ------------------------------------------------------------------------------- */
\r
41 ExpandLongestCurve() - ydnar
\r
42 finds length of quadratic curve specified and determines if length is longer than the supplied max
\r
45 #define APPROX_SUBDIVISION 8
\r
47 static void ExpandLongestCurve( float *longestCurve, vec3_t a, vec3_t b, vec3_t c )
\r
51 vec3_t ab, bc, ac, pt, last, delta;
\r
55 VectorSubtract( b, a, ab );
\r
56 if( VectorNormalize( ab, ab ) < 0.125f )
\r
58 VectorSubtract( c, b, bc );
\r
59 if( VectorNormalize( bc, bc ) < 0.125f )
\r
61 VectorSubtract( c, a, ac );
\r
62 if( VectorNormalize( ac, ac ) < 0.125f )
\r
65 /* if all 3 vectors are the same direction, then this edge is linear, so we ignore it */
\r
66 if( DotProduct( ab, bc ) > 0.99f && DotProduct( ab, ac ) > 0.99f )
\r
69 /* recalculate vectors */
\r
70 VectorSubtract( b, a, ab );
\r
71 VectorSubtract( c, b, bc );
\r
73 /* determine length */
\r
74 VectorCopy( a, last );
\r
75 for( i = 0, len = 0.0f, t = 0.0f; i < APPROX_SUBDIVISION; i++, t += (1.0f / APPROX_SUBDIVISION) )
\r
77 /* calculate delta */
\r
78 delta[ 0 ] = ((1.0f - t) * ab[ 0 ]) + (t * bc[ 0 ]);
\r
79 delta[ 1 ] = ((1.0f - t) * ab[ 1 ]) + (t * bc[ 1 ]);
\r
80 delta[ 2 ] = ((1.0f - t) * ab[ 2 ]) + (t * bc[ 2 ]);
\r
82 /* add to first point and calculate pt-pt delta */
\r
83 VectorAdd( a, delta, pt );
\r
84 VectorSubtract( pt, last, delta );
\r
86 /* add it to length and store last point */
\r
87 len += VectorLength( delta );
\r
88 VectorCopy( pt, last );
\r
92 if( len > *longestCurve )
\r
93 *longestCurve = len;
\r
99 ExpandMaxIterations() - ydnar
\r
100 determines how many iterations a quadratic curve needs to be subdivided with to fit the specified error
\r
103 static void ExpandMaxIterations( int *maxIterations, int maxError, vec3_t a, vec3_t b, vec3_t c )
\r
106 vec3_t prev, next, mid, delta, delta2;
\r
108 int numPoints, iterations;
\r
109 vec3_t points[ MAX_EXPANDED_AXIS ];
\r
112 /* initial setup */
\r
114 VectorCopy( a, points[ 0 ] );
\r
115 VectorCopy( b, points[ 1 ] );
\r
116 VectorCopy( c, points[ 2 ] );
\r
119 for( i = 0; i + 2 < numPoints; i += 2 )
\r
121 /* check subdivision limit */
\r
122 if( numPoints + 2 >= MAX_EXPANDED_AXIS )
\r
125 /* calculate new curve deltas */
\r
126 for( j = 0; j < 3; j++ )
\r
128 prev[ j ] = points[ i + 1 ][ j ] - points[ i ][ j ];
\r
129 next[ j ] = points[ i + 2 ][ j ] - points[ i + 1 ][ j ];
\r
130 mid[ j ] = (points[ i ][ j ] + points[ i + 1 ][ j ] * 2.0f + points[ i + 2 ][ j ]) * 0.25f;
\r
133 /* see if this midpoint is off far enough to subdivide */
\r
134 VectorSubtract( points[ i + 1 ], mid, delta );
\r
135 len = VectorLength( delta );
\r
136 if( len < maxError )
\r
142 /* create new points */
\r
143 for( j = 0; j < 3; j++ )
\r
145 prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ]);
\r
146 next[ j ] = 0.5f * (points[ i + 1 ][ j ] + points[ i + 2 ][ j ]);
\r
147 mid[ j ] = 0.5f * (prev[ j ] + next[ j ]);
\r
150 /* push points out */
\r
151 for( j = numPoints - 1; j > i + 3; j-- )
\r
152 VectorCopy( points[ j - 2 ], points[ j ] );
\r
154 /* insert new points */
\r
155 VectorCopy( prev, points[ i + 1 ] );
\r
156 VectorCopy( mid, points[ i + 2 ] );
\r
157 VectorCopy( next, points[ i + 3 ] );
\r
159 /* back up and recheck this set again, it may need more subdivision */
\r
163 /* put the line on the curve */
\r
164 for( i = 1; i < numPoints; i += 2 )
\r
166 for( j = 0; j < 3; j++ )
\r
168 prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ] );
\r
169 next[ j ] = 0.5f * (points[ i ][ j ] + points[ i - 1 ][ j ] );
\r
170 points[ i ][ j ] = 0.5f * (prev[ j ] + next[ j ]);
\r
174 /* eliminate linear sections */
\r
175 for( i = 0; i + 2 < numPoints; i++ )
\r
177 /* create vectors */
\r
178 VectorSubtract( points[ i + 1 ], points[ i ], delta );
\r
179 len = VectorNormalize( delta, delta );
\r
180 VectorSubtract( points[ i + 2 ], points[ i + 1 ], delta2 );
\r
181 len2 = VectorNormalize( delta2, delta2 );
\r
183 /* if either edge is degenerate, then eliminate it */
\r
184 if( len < 0.0625f || len2 < 0.0625f || DotProduct( delta, delta2 ) >= 1.0f )
\r
186 for( j = i + 1; j + 1 < numPoints; j++ )
\r
187 VectorCopy( points[ j + 1 ], points[ j ] );
\r
193 /* the number of iterations is 2^(points - 1) - 1 */
\r
196 while( numPoints > 1 )
\r
203 if( iterations > *maxIterations )
\r
204 *maxIterations = iterations;
\r
211 creates a mapDrawSurface_t from the patch text
\r
214 void ParsePatch( qboolean onlyLights )
\r
219 char texture[ MAX_QPATH ];
\r
220 char shader[ MAX_QPATH ];
\r
222 bspDrawVert_t *verts;
\r
224 vec4_t delta, delta2, delta3;
\r
225 qboolean degenerate;
\r
226 float longestCurve;
\r
234 strcpy( texture, token );
\r
236 Parse1DMatrix( 5, info );
\r
238 m.height = info[1];
\r
239 m.verts = verts = safe_malloc( m.width * m.height * sizeof( m.verts[0] ) );
\r
241 if( m.width < 0 || m.width > MAX_PATCH_SIZE || m.height < 0 || m.height > MAX_PATCH_SIZE )
\r
242 Error( "ParsePatch: bad size" );
\r
245 for( j = 0; j < m.width ; j++ )
\r
248 for( i = 0; i < m.height ; i++ )
\r
250 Parse1DMatrix( 5, verts[ i * m.width + j ].xyz );
\r
252 /* ydnar: fix colors */
\r
253 for( k = 0; k < MAX_LIGHTMAPS; k++ )
\r
255 verts[ i * m.width + j ].color[ k ][ 0 ] = 255;
\r
256 verts[ i * m.width + j ].color[ k ][ 1 ] = 255;
\r
257 verts[ i * m.width + j ].color[ k ][ 2 ] = 255;
\r
258 verts[ i * m.width + j ].color[ k ][ 3 ] = 255;
\r
265 // if brush primitives format, we may have some epairs to ignore here
\r
267 if (g_bBrushPrimit!=BPRIMIT_OLDBRUSHES && strcmp(token,"}"))
\r
269 // NOTE: we leak that!
\r
278 /* short circuit */
\r
279 if( noCurveBrushes || onlyLights )
\r
283 /* ydnar: delete and warn about degenerate patches */
\r
284 j = (m.width * m.height);
\r
285 VectorClear( delta );
\r
287 degenerate = qtrue;
\r
289 /* find first valid vector */
\r
290 for( i = 1; i < j && delta[ 3 ] == 0; i++ )
\r
292 VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta );
\r
293 delta[ 3 ] = VectorNormalize( delta, delta );
\r
296 /* secondary degenerate test */
\r
297 if( delta[ 3 ] == 0 )
\r
298 degenerate = qtrue;
\r
301 /* if all vectors match this or are zero, then this is a degenerate patch */
\r
302 for( i = 1; i < j && degenerate == qtrue; i++ )
\r
304 VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta2 );
\r
305 delta2[ 3 ] = VectorNormalize( delta2, delta2 );
\r
306 if( delta2[ 3 ] != 0 )
\r
308 /* create inverse vector */
\r
309 VectorCopy( delta2, delta3 );
\r
310 delta3[ 3 ] = delta2[ 3 ];
\r
311 VectorInverse( delta3 );
\r
314 if( VectorCompare( delta, delta2 ) == qfalse && VectorCompare( delta, delta3 ) == qfalse )
\r
315 degenerate = qfalse;
\r
320 /* warn and select degenerate patch */
\r
323 xml_Select( "degenerate patch", mapEnt->mapEntityNum, entitySourceBrushes, qfalse );
\r
328 /* find longest curve on the mesh */
\r
329 longestCurve = 0.0f;
\r
331 for( j = 0; j + 2 < m.width; j += 2 )
\r
333 for( i = 0; i + 2 < m.height; i += 2 )
\r
335 ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ i * m.width + (j + 1) ].xyz, verts[ i * m.width + (j + 2) ].xyz ); /* row */
\r
336 ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ (i + 1) * m.width + j ].xyz, verts[ (i + 2) * m.width + j ].xyz ); /* col */
\r
337 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
338 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
342 /* allocate patch mesh */
\r
343 pm = safe_malloc( sizeof( *pm ) );
\r
344 memset( pm, 0, sizeof( *pm ) );
\r
346 /* ydnar: add entity/brush numbering */
\r
347 pm->entityNum = mapEnt->mapEntityNum;
\r
348 pm->brushNum = entitySourceBrushes;
\r
351 sprintf( shader, "textures/%s", texture );
\r
352 pm->shaderInfo = ShaderInfoForShader( shader );
\r
357 /* set longest curve */
\r
358 pm->longestCurve = longestCurve;
\r
359 pm->maxIterations = maxIterations;
\r
361 /* link to the entity */
\r
362 pm->next = mapEnt->patches;
\r
363 mapEnt->patches = pm;
\r
370 recursively adds patches to a lod group
\r
373 static void GrowGroup_r( parseMesh_t *pm, int patchNum, int patchCount, parseMesh_t **meshes, byte *bordering, byte *group )
\r
379 /* early out check */
\r
380 if( group[ patchNum ] )
\r
385 group[ patchNum ] = 1;
\r
386 row = bordering + patchNum * patchCount;
\r
388 /* check maximums */
\r
389 if( meshes[ patchNum ]->longestCurve > pm->longestCurve )
\r
390 pm->longestCurve = meshes[ patchNum ]->longestCurve;
\r
391 if( meshes[ patchNum ]->maxIterations > pm->maxIterations )
\r
392 pm->maxIterations = meshes[ patchNum ]->maxIterations;
\r
394 /* walk other patches */
\r
395 for( i = 0; i < patchCount; i++ )
\r
398 GrowGroup_r( pm, i, patchCount, meshes, bordering, group );
\r
404 PatchMapDrawSurfs()
\r
405 any patches that share an edge need to choose their
\r
406 level of detail as a unit, otherwise the edges would
\r
410 void PatchMapDrawSurfs( entity_t *e )
\r
412 int i, j, k, l, c1, c2;
\r
414 parseMesh_t *check, *scan;
\r
415 mapDrawSurface_t *ds;
\r
416 int patchCount, groupCount;
\r
417 bspDrawVert_t *v1, *v2;
\r
418 vec3_t bounds[ 2 ];
\r
421 /* ydnar: mac os x fails with these if not static */
\r
422 MAC_STATIC parseMesh_t *meshes[ MAX_MAP_DRAW_SURFS ];
\r
423 MAC_STATIC qb_t grouped[ MAX_MAP_DRAW_SURFS ];
\r
424 MAC_STATIC byte group[ MAX_MAP_DRAW_SURFS ];
\r
428 Sys_FPrintf( SYS_VRB, "--- PatchMapDrawSurfs ---\n" );
\r
431 for ( pm = e->patches ; pm ; pm = pm->next ) {
\r
432 meshes[patchCount] = pm;
\r
436 if ( !patchCount ) {
\r
439 bordering = safe_malloc( patchCount * patchCount );
\r
440 memset( bordering, 0, patchCount * patchCount );
\r
442 // build the bordering matrix
\r
443 for ( k = 0 ; k < patchCount ; k++ ) {
\r
444 bordering[k*patchCount+k] = 1;
\r
446 for ( l = k+1 ; l < patchCount ; l++ ) {
\r
449 c1 = scan->mesh.width * scan->mesh.height;
\r
450 v1 = scan->mesh.verts;
\r
452 for ( i = 0 ; i < c1 ; i++, v1++ ) {
\r
453 c2 = check->mesh.width * check->mesh.height;
\r
454 v2 = check->mesh.verts;
\r
455 for ( j = 0 ; j < c2 ; j++, v2++ ) {
\r
456 if ( fabs( v1->xyz[0] - v2->xyz[0] ) < 1.0
\r
457 && fabs( v1->xyz[1] - v2->xyz[1] ) < 1.0
\r
458 && fabs( v1->xyz[2] - v2->xyz[2] ) < 1.0 ) {
\r
467 // we have a connection
\r
468 bordering[k*patchCount+l] =
\r
469 bordering[l*patchCount+k] = 1;
\r
472 bordering[k*patchCount+l] =
\r
473 bordering[l*patchCount+k] = 0;
\r
480 memset( grouped, 0, patchCount );
\r
482 for ( i = 0; i < patchCount; i++ )
\r
485 scan = meshes[ i ];
\r
487 /* start a new group */
\r
488 if( !grouped[ i ] )
\r
491 /* recursively find all patches that belong in the same group */
\r
492 memset( group, 0, patchCount );
\r
493 GrowGroup_r( scan, i, patchCount, meshes, bordering, group );
\r
496 ClearBounds( bounds[ 0 ], bounds[ 1 ] );
\r
497 for( j = 0; j < patchCount; j++ )
\r
501 grouped[ j ] = qtrue;
\r
502 check = meshes[ j ];
\r
503 c1 = check->mesh.width * check->mesh.height;
\r
504 v1 = check->mesh.verts;
\r
505 for( k = 0; k < c1; k++, v1++ )
\r
506 AddPointToBounds( v1->xyz, bounds[ 0 ], bounds[ 1 ] );
\r
511 //% Sys_Printf( "Longest curve: %f Iterations: %d\n", scan->longestCurve, scan->maxIterations );
\r
513 /* create drawsurf */
\r
514 scan->grouped = qtrue;
\r
515 ds = DrawSurfaceForMesh( e, scan, NULL ); /* ydnar */
\r
516 VectorCopy( bounds[ 0 ], ds->bounds[ 0 ] );
\r
517 VectorCopy( bounds[ 1 ], ds->bounds[ 1 ] );
\r
520 /* emit some statistics */
\r
521 Sys_FPrintf( SYS_VRB, "%9d patches\n", patchCount );
\r
522 Sys_FPrintf( SYS_VRB, "%9d patch LOD groups\n", groupCount );
\r