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