1 /*
2 ===========================================================================
3
4 Return to Castle Wolfenstein multiplayer GPL Source Code
5 Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Return to Castle Wolfenstein multiplayer GPL Source Code (RTCW MP Source Code).
8
9 RTCW MP Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 RTCW MP Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with RTCW MP Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the RTCW MP Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the RTCW MP Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29
30 #include "tr_local.h"
31
32 /*
33
34 This file does all of the processing necessary to turn a raw grid of points
35 read from the map file into a srfGridMesh_t ready for rendering.
36
37 The level of detail solution is direction independent, based only on subdivided
38 distance from the true curve.
39
40 Only a single entry point:
41
42 srfGridMesh_t *R_SubdividePatchToGrid( int width, int height,
43 drawVert_t points[MAX_PATCH_SIZE*MAX_PATCH_SIZE] ) {
44
45 */
46
47
48 /*
49 ============
50 LerpDrawVert
51 ============
52 */
LerpDrawVert(drawVert_t * a,drawVert_t * b,drawVert_t * out)53 static void LerpDrawVert( drawVert_t *a, drawVert_t *b, drawVert_t *out ) {
54 out->xyz[0] = 0.5f * ( a->xyz[0] + b->xyz[0] );
55 out->xyz[1] = 0.5f * ( a->xyz[1] + b->xyz[1] );
56 out->xyz[2] = 0.5f * ( a->xyz[2] + b->xyz[2] );
57
58 out->st[0] = 0.5f * ( a->st[0] + b->st[0] );
59 out->st[1] = 0.5f * ( a->st[1] + b->st[1] );
60
61 out->lightmap[0] = 0.5f * ( a->lightmap[0] + b->lightmap[0] );
62 out->lightmap[1] = 0.5f * ( a->lightmap[1] + b->lightmap[1] );
63
64 out->color[0] = ( a->color[0] + b->color[0] ) >> 1;
65 out->color[1] = ( a->color[1] + b->color[1] ) >> 1;
66 out->color[2] = ( a->color[2] + b->color[2] ) >> 1;
67 out->color[3] = ( a->color[3] + b->color[3] ) >> 1;
68 }
69
70 /*
71 ============
72 Transpose
73 ============
74 */
Transpose(int width,int height,drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE])75 static void Transpose( int width, int height, drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE] ) {
76 int i, j;
77 drawVert_t temp;
78
79 if ( width > height ) {
80 for ( i = 0 ; i < height ; i++ ) {
81 for ( j = i + 1 ; j < width ; j++ ) {
82 if ( j < height ) {
83 // swap the value
84 temp = ctrl[j][i];
85 ctrl[j][i] = ctrl[i][j];
86 ctrl[i][j] = temp;
87 } else {
88 // just copy
89 ctrl[j][i] = ctrl[i][j];
90 }
91 }
92 }
93 } else {
94 for ( i = 0 ; i < width ; i++ ) {
95 for ( j = i + 1 ; j < height ; j++ ) {
96 if ( j < width ) {
97 // swap the value
98 temp = ctrl[i][j];
99 ctrl[i][j] = ctrl[j][i];
100 ctrl[j][i] = temp;
101 } else {
102 // just copy
103 ctrl[i][j] = ctrl[j][i];
104 }
105 }
106 }
107 }
108
109 }
110
111
112 /*
113 =================
114 MakeMeshNormals
115
116 Handles all the complicated wrapping and degenerate cases
117 =================
118 */
MakeMeshNormals(int width,int height,drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE])119 static void MakeMeshNormals( int width, int height, drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE] ) {
120 int i, j, k, dist;
121 vec3_t normal;
122 vec3_t sum;
123 int count = 0;
124 vec3_t base;
125 vec3_t delta;
126 int x, y;
127 drawVert_t *dv;
128 vec3_t around[8], temp;
129 qboolean good[8];
130 qboolean wrapWidth, wrapHeight;
131 float len;
132 static int neighbors[8][2] = {
133 {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
134 };
135
136 wrapWidth = qfalse;
137 for ( i = 0 ; i < height ; i++ ) {
138 VectorSubtract( ctrl[i][0].xyz, ctrl[i][width - 1].xyz, delta );
139 len = VectorLengthSquared( delta );
140 if ( len > 1.0 ) {
141 break;
142 }
143 }
144 if ( i == height ) {
145 wrapWidth = qtrue;
146 }
147
148 wrapHeight = qfalse;
149 for ( i = 0 ; i < width ; i++ ) {
150 VectorSubtract( ctrl[0][i].xyz, ctrl[height - 1][i].xyz, delta );
151 len = VectorLengthSquared( delta );
152 if ( len > 1.0 ) {
153 break;
154 }
155 }
156 if ( i == width ) {
157 wrapHeight = qtrue;
158 }
159
160
161 for ( i = 0 ; i < width ; i++ ) {
162 for ( j = 0 ; j < height ; j++ ) {
163 count = 0;
164 dv = &ctrl[j][i];
165 VectorCopy( dv->xyz, base );
166 for ( k = 0 ; k < 8 ; k++ ) {
167 VectorClear( around[k] );
168 good[k] = qfalse;
169
170 for ( dist = 1 ; dist <= 3 ; dist++ ) {
171 x = i + neighbors[k][0] * dist;
172 y = j + neighbors[k][1] * dist;
173 if ( wrapWidth ) {
174 if ( x < 0 ) {
175 x = width - 1 + x;
176 } else if ( x >= width ) {
177 x = 1 + x - width;
178 }
179 }
180 if ( wrapHeight ) {
181 if ( y < 0 ) {
182 y = height - 1 + y;
183 } else if ( y >= height ) {
184 y = 1 + y - height;
185 }
186 }
187
188 if ( x < 0 || x >= width || y < 0 || y >= height ) {
189 break; // edge of patch
190 }
191 VectorSubtract( ctrl[y][x].xyz, base, temp );
192 if ( VectorNormalize2( temp, temp ) == 0 ) {
193 continue; // degenerate edge, get more dist
194 } else {
195 good[k] = qtrue;
196 VectorCopy( temp, around[k] );
197 break; // good edge
198 }
199 }
200 }
201
202 VectorClear( sum );
203 for ( k = 0 ; k < 8 ; k++ ) {
204 if ( !good[k] || !good[( k + 1 ) & 7] ) {
205 continue; // didn't get two points
206 }
207 CrossProduct( around[( k + 1 ) & 7], around[k], normal );
208 if ( VectorNormalize2( normal, normal ) == 0 ) {
209 continue;
210 }
211 VectorAdd( normal, sum, sum );
212 count++;
213 }
214 //if ( count == 0 ) {
215 //printf("bad normal\n");
216 //}
217 VectorNormalize2( sum, dv->normal );
218 }
219 }
220 }
221
222 /*
223 ============
224 InvertCtrl
225 ============
226 */
InvertCtrl(int width,int height,drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE])227 static void InvertCtrl( int width, int height, drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE] ) {
228 int i, j;
229 drawVert_t temp;
230
231 for ( i = 0 ; i < height ; i++ ) {
232 for ( j = 0 ; j < width / 2 ; j++ ) {
233 temp = ctrl[i][j];
234 ctrl[i][j] = ctrl[i][width - 1 - j];
235 ctrl[i][width - 1 - j] = temp;
236 }
237 }
238 }
239
240
241 /*
242 =================
243 InvertErrorTable
244 =================
245 */
InvertErrorTable(float errorTable[2][MAX_GRID_SIZE],int width,int height)246 static void InvertErrorTable( float errorTable[2][MAX_GRID_SIZE], int width, int height ) {
247 int i;
248 float copy[2][MAX_GRID_SIZE];
249
250 memcpy( copy, errorTable, sizeof( copy ) );
251
252 for ( i = 0 ; i < width ; i++ ) {
253 errorTable[1][i] = copy[0][i]; //[width-1-i];
254 }
255
256 for ( i = 0 ; i < height ; i++ ) {
257 errorTable[0][i] = copy[1][height - 1 - i];
258 }
259
260 }
261
262 /*
263 ==================
264 PutPointsOnCurve
265 ==================
266 */
PutPointsOnCurve(drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE],int width,int height)267 static void PutPointsOnCurve( drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE],
268 int width, int height ) {
269 int i, j;
270 drawVert_t prev, next;
271
272 for ( i = 0 ; i < width ; i++ ) {
273 for ( j = 1 ; j < height ; j += 2 ) {
274 LerpDrawVert( &ctrl[j][i], &ctrl[j + 1][i], &prev );
275 LerpDrawVert( &ctrl[j][i], &ctrl[j - 1][i], &next );
276 LerpDrawVert( &prev, &next, &ctrl[j][i] );
277 }
278 }
279
280
281 for ( j = 0 ; j < height ; j++ ) {
282 for ( i = 1 ; i < width ; i += 2 ) {
283 LerpDrawVert( &ctrl[j][i], &ctrl[j][i + 1], &prev );
284 LerpDrawVert( &ctrl[j][i], &ctrl[j][i - 1], &next );
285 LerpDrawVert( &prev, &next, &ctrl[j][i] );
286 }
287 }
288 }
289
290
291 /*
292 =================
293 R_CreateSurfaceGridMesh
294 =================
295 */
R_CreateSurfaceGridMesh(int width,int height,drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE],float errorTable[2][MAX_GRID_SIZE])296 srfGridMesh_t *R_CreateSurfaceGridMesh( int width, int height,
297 drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE], float errorTable[2][MAX_GRID_SIZE] ) {
298 int i, j, size;
299 drawVert_t *vert;
300 vec3_t tmpVec;
301 srfGridMesh_t *grid;
302
303 // copy the results out to a grid
304 size = ( width * height - 1 ) * sizeof( drawVert_t ) + sizeof( *grid );
305
306 #ifdef PATCH_STITCHING
307 grid = /*ri.Hunk_Alloc*/ ri.Z_Malloc( size );
308 Com_Memset( grid, 0, size );
309
310 grid->widthLodError = /*ri.Hunk_Alloc*/ ri.Z_Malloc( width * 4 );
311 memcpy( grid->widthLodError, errorTable[0], width * 4 );
312
313 grid->heightLodError = /*ri.Hunk_Alloc*/ ri.Z_Malloc( height * 4 );
314 memcpy( grid->heightLodError, errorTable[1], height * 4 );
315 #else
316 grid = ri.Hunk_Alloc( size, h_low );
317 memset( grid, 0, size );
318
319 grid->widthLodError = ri.Hunk_Alloc( width * 4, h_low );
320 memcpy( grid->widthLodError, errorTable[0], width * 4 );
321
322 grid->heightLodError = ri.Hunk_Alloc( height * 4, h_low );
323 memcpy( grid->heightLodError, errorTable[1], height * 4 );
324 #endif
325
326 grid->width = width;
327 grid->height = height;
328 grid->surfaceType = SF_GRID;
329 ClearBounds( grid->meshBounds[0], grid->meshBounds[1] );
330 for ( i = 0 ; i < width ; i++ ) {
331 for ( j = 0 ; j < height ; j++ ) {
332 vert = &grid->verts[j * width + i];
333 *vert = ctrl[j][i];
334 AddPointToBounds( vert->xyz, grid->meshBounds[0], grid->meshBounds[1] );
335 }
336 }
337
338 // compute local origin and bounds
339 VectorAdd( grid->meshBounds[0], grid->meshBounds[1], grid->localOrigin );
340 VectorScale( grid->localOrigin, 0.5f, grid->localOrigin );
341 VectorSubtract( grid->meshBounds[0], grid->localOrigin, tmpVec );
342 grid->meshRadius = VectorLength( tmpVec );
343
344 VectorCopy( grid->localOrigin, grid->lodOrigin );
345 grid->lodRadius = grid->meshRadius;
346 //
347 return grid;
348 }
349
350 /*
351 =================
352 R_FreeSurfaceGridMesh
353 =================
354 */
R_FreeSurfaceGridMesh(srfGridMesh_t * grid)355 void R_FreeSurfaceGridMesh( srfGridMesh_t *grid ) {
356 ri.Free( grid->widthLodError );
357 ri.Free( grid->heightLodError );
358 ri.Free( grid );
359 }
360
361 /*
362 =================
363 R_SubdividePatchToGrid
364 =================
365 */
R_SubdividePatchToGrid(int width,int height,drawVert_t points[MAX_PATCH_SIZE * MAX_PATCH_SIZE])366 srfGridMesh_t *R_SubdividePatchToGrid( int width, int height,
367 drawVert_t points[MAX_PATCH_SIZE*MAX_PATCH_SIZE] ) {
368 int i, j, k, l;
369 drawVert_t_cleared( prev );
370 drawVert_t_cleared( next );
371 drawVert_t_cleared( mid );
372 float len, maxLen;
373 int dir;
374 int t;
375 drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE];
376 float errorTable[2][MAX_GRID_SIZE];
377
378 for ( i = 0 ; i < width ; i++ ) {
379 for ( j = 0 ; j < height ; j++ ) {
380 ctrl[j][i] = points[j * width + i];
381 }
382 }
383
384 for ( dir = 0 ; dir < 2 ; dir++ ) {
385
386 for ( j = 0 ; j < MAX_GRID_SIZE ; j++ ) {
387 errorTable[dir][j] = 0;
388 }
389
390 // horizontal subdivisions
391 for ( j = 0 ; j + 2 < width ; j += 2 ) {
392 // check subdivided midpoints against control points
393
394 // FIXME: also check midpoints of adjacent patches against the control points
395 // this would basically stitch all patches in the same LOD group together.
396
397 maxLen = 0;
398 for ( i = 0 ; i < height ; i++ ) {
399 vec3_t midxyz;
400 vec3_t dir;
401 vec3_t projected;
402 float d;
403
404 // calculate the point on the curve
405 for ( l = 0 ; l < 3 ; l++ ) {
406 midxyz[l] = ( ctrl[i][j].xyz[l] + ctrl[i][j + 1].xyz[l] * 2
407 + ctrl[i][j + 2].xyz[l] ) * 0.25f;
408 }
409
410 // see how far off the line it is
411 // using dist-from-line will not account for internal
412 // texture warping, but it gives a lot less polygons than
413 // dist-from-midpoint
414 VectorSubtract( midxyz, ctrl[i][j].xyz, midxyz );
415 VectorSubtract( ctrl[i][j + 2].xyz, ctrl[i][j].xyz, dir );
416 VectorNormalize( dir );
417
418 d = DotProduct( midxyz, dir );
419 VectorScale( dir, d, projected );
420 VectorSubtract( midxyz, projected, midxyz );
421 len = VectorLengthSquared( midxyz ); // we will do the sqrt later
422
423 if ( len > maxLen ) {
424 maxLen = len;
425 }
426 }
427
428 maxLen = sqrt( maxLen );
429 // if all the points are on the lines, remove the entire columns
430 if ( maxLen < 0.1f ) {
431 errorTable[dir][j + 1] = 999;
432 continue;
433 }
434
435 // see if we want to insert subdivided columns
436 if ( width + 2 > MAX_GRID_SIZE ) {
437 errorTable[dir][j + 1] = 1.0f / maxLen;
438 continue; // can't subdivide any more
439 }
440
441 if ( maxLen <= r_subdivisions->value ) {
442 errorTable[dir][j + 1] = 1.0f / maxLen;
443 continue; // didn't need subdivision
444 }
445
446 errorTable[dir][j + 2] = 1.0f / maxLen;
447
448 // insert two columns and replace the peak
449 width += 2;
450 for ( i = 0 ; i < height ; i++ ) {
451 LerpDrawVert( &ctrl[i][j], &ctrl[i][j + 1], &prev );
452 LerpDrawVert( &ctrl[i][j + 1], &ctrl[i][j + 2], &next );
453 LerpDrawVert( &prev, &next, &mid );
454
455 for ( k = width - 1 ; k > j + 3 ; k-- ) {
456 ctrl[i][k] = ctrl[i][k - 2];
457 }
458 ctrl[i][j + 1] = prev;
459 ctrl[i][j + 2] = mid;
460 ctrl[i][j + 3] = next;
461 }
462
463 // back up and recheck this set again, it may need more subdivision
464 j -= 2;
465
466 }
467
468 Transpose( width, height, ctrl );
469 t = width;
470 width = height;
471 height = t;
472 }
473
474
475 // put all the aproximating points on the curve
476 PutPointsOnCurve( ctrl, width, height );
477
478 // cull out any rows or columns that are colinear
479 for ( i = 1 ; i < width - 1 ; i++ ) {
480 if ( errorTable[0][i] != 999 ) {
481 continue;
482 }
483 for ( j = i + 1 ; j < width ; j++ ) {
484 for ( k = 0 ; k < height ; k++ ) {
485 ctrl[k][j - 1] = ctrl[k][j];
486 }
487 errorTable[0][j - 1] = errorTable[0][j];
488 }
489 width--;
490 }
491
492 for ( i = 1 ; i < height - 1 ; i++ ) {
493 if ( errorTable[1][i] != 999 ) {
494 continue;
495 }
496 for ( j = i + 1 ; j < height ; j++ ) {
497 for ( k = 0 ; k < width ; k++ ) {
498 ctrl[j - 1][k] = ctrl[j][k];
499 }
500 errorTable[1][j - 1] = errorTable[1][j];
501 }
502 height--;
503 }
504
505 #if 1
506 // flip for longest tristrips as an optimization
507 // the results should be visually identical with or
508 // without this step
509 if ( height > width ) {
510 Transpose( width, height, ctrl );
511 InvertErrorTable( errorTable, width, height );
512 t = width;
513 width = height;
514 height = t;
515 InvertCtrl( width, height, ctrl );
516 }
517 #endif
518
519 // calculate normals
520 MakeMeshNormals( width, height, ctrl );
521
522 return R_CreateSurfaceGridMesh( width, height, ctrl, errorTable );
523 }
524
525 /*
526 ===============
527 R_GridInsertColumn
528 ===============
529 */
R_GridInsertColumn(srfGridMesh_t * grid,int column,int row,vec3_t point,float loderror)530 srfGridMesh_t *R_GridInsertColumn( srfGridMesh_t *grid, int column, int row, vec3_t point, float loderror ) {
531 int i, j;
532 int width, height, oldwidth;
533 drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE];
534 float errorTable[2][MAX_GRID_SIZE];
535 float lodRadius;
536 vec3_t lodOrigin;
537
538 oldwidth = 0;
539 width = grid->width + 1;
540 if ( width > MAX_GRID_SIZE ) {
541 return NULL;
542 }
543 height = grid->height;
544 for ( i = 0; i < width; i++ ) {
545 if ( i == column ) {
546 //insert new column
547 for ( j = 0; j < grid->height; j++ ) {
548 LerpDrawVert( &grid->verts[j * grid->width + i - 1], &grid->verts[j * grid->width + i], &ctrl[j][i] );
549 if ( j == row ) {
550 VectorCopy( point, ctrl[j][i].xyz );
551 }
552 }
553 errorTable[0][i] = loderror;
554 continue;
555 }
556 errorTable[0][i] = grid->widthLodError[oldwidth];
557 for ( j = 0; j < grid->height; j++ ) {
558 ctrl[j][i] = grid->verts[j * grid->width + oldwidth];
559 }
560 oldwidth++;
561 }
562 for ( j = 0; j < grid->height; j++ ) {
563 errorTable[1][j] = grid->heightLodError[j];
564 }
565 // put all the aproximating points on the curve
566 //PutPointsOnCurve( ctrl, width, height );
567 // calculate normals
568 MakeMeshNormals( width, height, ctrl );
569
570 VectorCopy( grid->lodOrigin, lodOrigin );
571 lodRadius = grid->lodRadius;
572 // free the old grid
573 R_FreeSurfaceGridMesh( grid );
574 // create a new grid
575 grid = R_CreateSurfaceGridMesh( width, height, ctrl, errorTable );
576 grid->lodRadius = lodRadius;
577 VectorCopy( lodOrigin, grid->lodOrigin );
578 return grid;
579 }
580
581 /*
582 ===============
583 R_GridInsertRow
584 ===============
585 */
R_GridInsertRow(srfGridMesh_t * grid,int row,int column,vec3_t point,float loderror)586 srfGridMesh_t *R_GridInsertRow( srfGridMesh_t *grid, int row, int column, vec3_t point, float loderror ) {
587 int i, j;
588 int width, height, oldheight;
589 drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE];
590 float errorTable[2][MAX_GRID_SIZE];
591 float lodRadius;
592 vec3_t lodOrigin;
593
594 oldheight = 0;
595 width = grid->width;
596 height = grid->height + 1;
597 if ( height > MAX_GRID_SIZE ) {
598 return NULL;
599 }
600 for ( i = 0; i < height; i++ ) {
601 if ( i == row ) {
602 //insert new row
603 for ( j = 0; j < grid->width; j++ ) {
604 LerpDrawVert( &grid->verts[( i - 1 ) * grid->width + j], &grid->verts[i * grid->width + j], &ctrl[i][j] );
605 if ( j == column ) {
606 VectorCopy( point, ctrl[i][j].xyz );
607 }
608 }
609 errorTable[1][i] = loderror;
610 continue;
611 }
612 errorTable[1][i] = grid->heightLodError[oldheight];
613 for ( j = 0; j < grid->width; j++ ) {
614 ctrl[i][j] = grid->verts[oldheight * grid->width + j];
615 }
616 oldheight++;
617 }
618 for ( j = 0; j < grid->width; j++ ) {
619 errorTable[0][j] = grid->widthLodError[j];
620 }
621 // put all the aproximating points on the curve
622 //PutPointsOnCurve( ctrl, width, height );
623 // calculate normals
624 MakeMeshNormals( width, height, ctrl );
625
626 VectorCopy( grid->lodOrigin, lodOrigin );
627 lodRadius = grid->lodRadius;
628 // free the old grid
629 R_FreeSurfaceGridMesh( grid );
630 // create a new grid
631 grid = R_CreateSurfaceGridMesh( width, height, ctrl, errorTable );
632 grid->lodRadius = lodRadius;
633 VectorCopy( lodOrigin, grid->lodOrigin );
634 return grid;
635 }
636