already apply some safe changes:
[divverent/netradiant.git] / tools / quake3 / q3map2 / patch.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 PATCH_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 /*
42 ExpandLongestCurve() - ydnar
43 finds length of quadratic curve specified and determines if length is longer than the supplied max
44 */
45
46 #define APPROX_SUBDIVISION      8
47
48 static void ExpandLongestCurve( float *longestCurve, vec3_t a, vec3_t b, vec3_t c )
49 {
50         int             i;
51         float   t, len;
52         vec3_t  ab, bc, ac, pt, last, delta;
53         
54         
55         /* calc vectors */
56         VectorSubtract( b, a, ab );
57         if( VectorNormalize( ab, ab ) < 0.125f )
58                 return;
59         VectorSubtract( c, b, bc );
60         if( VectorNormalize( bc, bc ) < 0.125f )
61                 return;
62         VectorSubtract( c, a, ac );
63         if( VectorNormalize( ac, ac ) < 0.125f )
64                 return;
65         
66         /* if all 3 vectors are the same direction, then this edge is linear, so we ignore it */
67         if( DotProduct( ab, bc ) > 0.99f && DotProduct( ab, ac ) > 0.99f )
68                 return;
69         
70         /* recalculate vectors */
71         VectorSubtract( b, a, ab );
72         VectorSubtract( c, b, bc );
73         
74         /* determine length */
75         VectorCopy( a, last );
76         for( i = 0, len = 0.0f, t = 0.0f; i < APPROX_SUBDIVISION; i++, t += (1.0f / APPROX_SUBDIVISION) )
77         {
78                 /* calculate delta */
79                 delta[ 0 ] = ((1.0f - t) * ab[ 0 ]) + (t * bc[ 0 ]);
80                 delta[ 1 ] = ((1.0f - t) * ab[ 1 ]) + (t * bc[ 1 ]);
81                 delta[ 2 ] = ((1.0f - t) * ab[ 2 ]) + (t * bc[ 2 ]);
82                 
83                 /* add to first point and calculate pt-pt delta */
84                 VectorAdd( a, delta, pt );
85                 VectorSubtract( pt, last, delta );
86                 
87                 /* add it to length and store last point */
88                 len += VectorLength( delta );
89                 VectorCopy( pt, last );
90         }
91         
92         /* longer? */
93         if( len > *longestCurve )
94                 *longestCurve = len;
95 }
96
97
98
99 /*
100 ExpandMaxIterations() - ydnar
101 determines how many iterations a quadratic curve needs to be subdivided with to fit the specified error
102 */
103
104 static void ExpandMaxIterations( int *maxIterations, int maxError, vec3_t a, vec3_t b, vec3_t c )
105 {
106         int                             i, j;
107         vec3_t                  prev, next, mid, delta, delta2;
108         float                   len, len2;
109         int                             numPoints, iterations;
110         vec3_t                  points[ MAX_EXPANDED_AXIS ];
111         
112         
113         /* initial setup */
114         numPoints = 3;
115         VectorCopy( a, points[ 0 ] );
116         VectorCopy( b, points[ 1 ] );
117         VectorCopy( c, points[ 2 ] );
118
119         /* subdivide */
120         for( i = 0; i + 2 < numPoints; i += 2 )
121         {
122                 /* check subdivision limit */
123                 if( numPoints + 2 >= MAX_EXPANDED_AXIS )
124                         break;
125                 
126                 /* calculate new curve deltas */
127                 for( j = 0; j < 3; j++ )
128                 {
129                         prev[ j ] = points[ i + 1 ][ j ] - points[ i ][ j ]; 
130                         next[ j ] = points[ i + 2 ][ j ] - points[ i + 1 ][ j ]; 
131                         mid[ j ] = (points[ i ][ j ] + points[ i + 1 ][ j ] * 2.0f + points[ i + 2 ][ j ]) * 0.25f;
132                 }
133                 
134                 /* see if this midpoint is off far enough to subdivide */
135                 VectorSubtract( points[ i + 1 ], mid, delta );
136                 len = VectorLength( delta );
137                 if( len < maxError )
138                         continue;
139                 
140                 /* subdivide */
141                 numPoints += 2;
142                 
143                 /* create new points */
144                 for( j = 0; j < 3; j++ )
145                 {
146                         prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ]);
147                         next[ j ] = 0.5f * (points[ i + 1 ][ j ] + points[ i + 2 ][ j ]);
148                         mid[ j ] = 0.5f * (prev[ j ] + next[ j ]);
149                 }
150                 
151                 /* push points out */
152                 for( j = numPoints - 1; j > i + 3; j-- )
153                         VectorCopy( points[ j - 2 ], points[ j ] );
154                 
155                 /* insert new points */
156                 VectorCopy( prev, points[ i + 1 ] );
157                 VectorCopy( mid, points[ i + 2 ] );
158                 VectorCopy( next, points[ i + 3 ] );
159
160                 /* back up and recheck this set again, it may need more subdivision */
161                 i -= 2;
162         }
163         
164         /* put the line on the curve */
165         for( i = 1; i < numPoints; i += 2 )
166         {
167                 for( j = 0; j < 3; j++ )
168                 {
169                         prev[ j ] = 0.5f * (points[ i ][ j ] + points[ i + 1 ][ j ] );
170                         next[ j ] = 0.5f * (points[ i ][ j ] + points[ i - 1 ][ j ] );
171                         points[ i ][ j ] = 0.5f * (prev[ j ] + next[ j ]);
172                 }
173         }
174         
175         /* eliminate linear sections */
176         for( i = 0; i + 2 < numPoints; i++ )
177         {
178                 /* create vectors */
179                 VectorSubtract( points[ i + 1 ], points[ i ], delta );
180                 len = VectorNormalize( delta, delta );
181                 VectorSubtract( points[ i + 2 ], points[ i + 1 ], delta2 );
182                 len2 = VectorNormalize( delta2, delta2 );
183                 
184                 /* if either edge is degenerate, then eliminate it */
185                 if( len < 0.0625f || len2 < 0.0625f || DotProduct( delta, delta2 ) >= 1.0f )
186                 {
187                         for( j = i + 1; j + 1 < numPoints; j++ )
188                                 VectorCopy( points[ j + 1 ], points[ j ] );
189                         numPoints--;
190                         continue;
191                 }
192         }
193         
194         /* the number of iterations is 2^(points - 1) - 1 */
195         numPoints >>= 1;
196         iterations = 0;
197         while( numPoints > 1 )
198         {
199                 numPoints >>= 1;
200                 iterations++;
201         }
202         
203         /* more? */
204         if( iterations > *maxIterations )
205                 *maxIterations = iterations;
206 }
207
208
209
210 /*
211 ParsePatch()
212 creates a mapDrawSurface_t from the patch text
213 */
214
215 void ParsePatch( qboolean onlyLights )
216 {
217         vec_t                   info[ 5 ];
218         int                             i, j, k;
219         parseMesh_t             *pm;
220         char                    texture[ MAX_QPATH ];
221         char                    shader[ MAX_QPATH ];
222         mesh_t                  m;
223         bspDrawVert_t   *verts;
224         epair_t                 *ep;
225         vec4_t                  delta, delta2, delta3;
226         qboolean                degenerate;
227         float                   longestCurve;
228         int                             maxIterations;
229         
230         MatchToken( "{" );
231         
232         /* get texture */
233         GetToken( qtrue );
234         strcpy( texture, token );
235         
236         Parse1DMatrix( 5, info );
237         m.width = info[0];
238         m.height = info[1];
239         m.verts = verts = safe_malloc( m.width * m.height * sizeof( m.verts[0] ) );
240         
241         if( m.width < 0 || m.width > MAX_PATCH_SIZE || m.height < 0 || m.height > MAX_PATCH_SIZE )
242                 Error( "ParsePatch: bad size" );
243         
244         MatchToken( "(" );
245         for( j = 0; j < m.width ; j++ )
246         {
247                 MatchToken( "(" );
248                 for( i = 0; i < m.height ; i++ )
249                 {
250                         Parse1DMatrix( 5, verts[ i * m.width + j ].xyz );
251                         
252                         /* ydnar: fix colors */
253                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
254                         {
255                                 verts[ i * m.width + j ].color[ k ][ 0 ] = 255;
256                                 verts[ i * m.width + j ].color[ k ][ 1 ] = 255;
257                                 verts[ i * m.width + j ].color[ k ][ 2 ] = 255;
258                                 verts[ i * m.width + j ].color[ k ][ 3 ] = 255;
259                         }
260                 }
261                 MatchToken( ")" );
262         }
263         MatchToken( ")" );
264
265         // if brush primitives format, we may have some epairs to ignore here
266         GetToken(qtrue);
267         if (g_bBrushPrimit!=BPRIMIT_OLDBRUSHES && strcmp(token,"}"))
268         {
269                 // NOTE: we leak that!
270                 ep = ParseEPair();
271         }
272         else
273                 UnGetToken();
274
275         MatchToken( "}" );
276         MatchToken( "}" );
277         
278         /* short circuit */
279         if( noCurveBrushes || onlyLights )
280                 return;
281         
282         
283         /* ydnar: delete and warn about degenerate patches */
284         j = (m.width * m.height);
285         VectorClear( delta );
286         delta[ 3 ] = 0;
287         degenerate = qtrue;
288         
289         /* find first valid vector */
290         for( i = 1; i < j && delta[ 3 ] == 0; i++ )
291         {
292                 VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta );
293                 delta[ 3 ] = VectorNormalize( delta, delta );
294         }
295         
296         /* secondary degenerate test */
297         if( delta[ 3 ] == 0 )
298                 degenerate = qtrue;
299         else
300         {
301                 /* if all vectors match this or are zero, then this is a degenerate patch */
302                 for( i = 1; i < j && degenerate == qtrue; i++ )
303                 {
304                         VectorSubtract( m.verts[ 0 ].xyz, m.verts[ i ].xyz, delta2 );
305                         delta2[ 3 ] = VectorNormalize( delta2, delta2 );
306                         if( delta2[ 3 ] != 0 )
307                         {
308                                 /* create inverse vector */
309                                 VectorCopy( delta2, delta3 );
310                                 delta3[ 3 ] = delta2[ 3 ];
311                                 VectorInverse( delta3 );
312                                 
313                                 /* compare */
314                                 if( VectorCompare( delta, delta2 ) == qfalse && VectorCompare( delta, delta3 ) == qfalse )
315                                         degenerate = qfalse;
316                         }
317                 }
318         }
319         
320         /* warn and select degenerate patch */
321         if( degenerate )
322         {
323                 xml_Select( "degenerate patch", mapEnt->mapEntityNum, entitySourceBrushes, qfalse );
324                 free( m.verts );
325                 return;
326         }
327         
328         /* find longest curve on the mesh */
329         longestCurve = 0.0f;
330         maxIterations = 0;
331         for( j = 0; j + 2 < m.width; j += 2 )
332         {
333                 for( i = 0; i + 2 < m.height; i += 2 )
334                 {
335                         ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ i * m.width + (j + 1) ].xyz, verts[ i * m.width + (j + 2) ].xyz );              /* row */
336                         ExpandLongestCurve( &longestCurve, verts[ i * m.width + j ].xyz, verts[ (i + 1) * m.width + j ].xyz, verts[ (i + 2) * m.width + j ].xyz );              /* col */
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 */
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 */
339                 }
340         }
341         
342         /* allocate patch mesh */
343         pm = safe_malloc( sizeof( *pm ) );
344         memset( pm, 0, sizeof( *pm ) );
345         
346         /* ydnar: add entity/brush numbering */
347         pm->entityNum = mapEnt->mapEntityNum;
348         pm->brushNum = entitySourceBrushes;
349         
350         /* set shader */
351         sprintf( shader, "textures/%s", texture );
352         pm->shaderInfo = ShaderInfoForShader( shader );
353         
354         /* set mesh */
355         pm->mesh = m;
356         
357         /* set longest curve */
358         pm->longestCurve = longestCurve;
359         pm->maxIterations = maxIterations;
360         
361         /* link to the entity */
362         pm->next = mapEnt->patches;
363         mapEnt->patches = pm;
364 }
365
366
367
368 /*
369 GrowGroup_r()
370 recursively adds patches to a lod group
371 */
372
373 static void GrowGroup_r( parseMesh_t *pm, int patchNum, int patchCount, parseMesh_t **meshes, byte *bordering, byte *group )
374 {
375         int                     i;
376         const byte      *row;
377         
378         
379         /* early out check */
380         if( group[ patchNum ] )
381                 return;
382         
383         
384         /* set it */
385         group[ patchNum ] = 1;
386         row = bordering + patchNum * patchCount;
387         
388         /* check maximums */
389         if( meshes[ patchNum ]->longestCurve > pm->longestCurve )
390                 pm->longestCurve = meshes[ patchNum ]->longestCurve;
391         if( meshes[ patchNum ]->maxIterations > pm->maxIterations )
392                 pm->maxIterations = meshes[ patchNum ]->maxIterations;
393         
394         /* walk other patches */
395         for( i = 0; i < patchCount; i++ )
396         {
397                 if( row[ i ] )
398                         GrowGroup_r( pm, i, patchCount, meshes, bordering, group );
399         }
400 }
401
402
403 /*
404 PatchMapDrawSurfs()
405 any patches that share an edge need to choose their
406 level of detail as a unit, otherwise the edges would
407 pull apart.
408 */
409
410 void PatchMapDrawSurfs( entity_t *e )
411 {
412         int                                             i, j, k, l, c1, c2;
413         parseMesh_t                             *pm;
414         parseMesh_t                             *check, *scan;
415         mapDrawSurface_t                *ds;
416         int                                             patchCount, groupCount;
417         bspDrawVert_t                   *v1, *v2;
418         vec3_t                                  bounds[ 2 ];
419         byte                                    *bordering;
420         
421         /* ydnar: mac os x fails with these if not static */
422         MAC_STATIC parseMesh_t  *meshes[ MAX_MAP_DRAW_SURFS ];
423         MAC_STATIC qb_t                 grouped[ MAX_MAP_DRAW_SURFS ];
424         MAC_STATIC byte                 group[ MAX_MAP_DRAW_SURFS ];
425         
426         
427         /* note it */
428         Sys_FPrintf( SYS_VRB, "--- PatchMapDrawSurfs ---\n" );
429
430         patchCount = 0;
431         for ( pm = e->patches ; pm ; pm = pm->next  ) {
432                 meshes[patchCount] = pm;
433                 patchCount++;
434         }
435
436         if ( !patchCount ) {
437                 return;
438         }
439         bordering = safe_malloc( patchCount * patchCount );
440         memset( bordering, 0, patchCount * patchCount );
441
442         // build the bordering matrix
443         for ( k = 0 ; k < patchCount ; k++ ) {
444                 bordering[k*patchCount+k] = 1;
445
446                 for ( l = k+1 ; l < patchCount ; l++ ) {
447                         check = meshes[k];
448                         scan = meshes[l];
449                         c1 = scan->mesh.width * scan->mesh.height;
450                         v1 = scan->mesh.verts;
451
452                         for ( i = 0 ; i < c1 ; i++, v1++ ) {
453                                 c2 = check->mesh.width * check->mesh.height;
454                                 v2 = check->mesh.verts;
455                                 for ( j = 0 ; j < c2 ; j++, v2++ ) {
456                                         if ( fabs( v1->xyz[0] - v2->xyz[0] ) < 1.0
457                                                 && fabs( v1->xyz[1] - v2->xyz[1] ) < 1.0
458                                                 && fabs( v1->xyz[2] - v2->xyz[2] ) < 1.0 ) {
459                                                 break;
460                                         }
461                                 }
462                                 if ( j != c2 ) {
463                                         break;
464                                 }
465                         }
466                         if ( i != c1 ) {
467                                 // we have a connection
468                                 bordering[k*patchCount+l] =
469                                 bordering[l*patchCount+k] = 1;
470                         } else {
471                                 // no connection
472                                 bordering[k*patchCount+l] =
473                                 bordering[l*patchCount+k] = 0;
474                         }
475
476                 }
477         }
478
479         /* build groups */
480         memset( grouped, 0, patchCount );
481         groupCount = 0;
482         for ( i = 0; i < patchCount; i++ )
483         {
484                 /* get patch */
485                 scan = meshes[ i ];
486                 
487                 /* start a new group */
488                 if( !grouped[ i ] )
489                         groupCount++;
490                 
491                 /* recursively find all patches that belong in the same group */
492                 memset( group, 0, patchCount );
493                 GrowGroup_r( scan, i, patchCount, meshes, bordering, group );
494                 
495                 /* bound them */
496                 ClearBounds( bounds[ 0 ], bounds[ 1 ] );
497                 for( j = 0; j < patchCount; j++ )
498                 {
499                         if ( group[ j ] )
500                         {
501                                 grouped[ j ] = qtrue;
502                                 check = meshes[ j ];
503                                 c1 = check->mesh.width * check->mesh.height;
504                                 v1 = check->mesh.verts;
505                                 for( k = 0; k < c1; k++, v1++ )
506                                         AddPointToBounds( v1->xyz, bounds[ 0 ], bounds[ 1 ] );
507                         }
508                 }
509                 
510                 /* debug code */
511                 //%     Sys_Printf( "Longest curve: %f Iterations: %d\n", scan->longestCurve, scan->maxIterations );
512                 
513                 /* create drawsurf */
514                 scan->grouped = qtrue;
515                 ds = DrawSurfaceForMesh( e, scan, NULL );       /* ydnar */
516                 VectorCopy( bounds[ 0 ], ds->bounds[ 0 ] );
517                 VectorCopy( bounds[ 1 ], ds->bounds[ 1 ] );
518         }
519         
520         /* emit some statistics */
521         Sys_FPrintf( SYS_VRB, "%9d patches\n", patchCount );
522         Sys_FPrintf( SYS_VRB, "%9d patch LOD groups\n", groupCount );
523 }
524