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