tr_curve.c (15822B)
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 Foobar; 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 */ 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 */ 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 */ 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; 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 prev, next, mid; 364 float len, maxLen; 365 int dir; 366 int t; 367 MAC_STATIC drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE]; 368 float errorTable[2][MAX_GRID_SIZE]; 369 370 for ( i = 0 ; i < width ; i++ ) { 371 for ( j = 0 ; j < height ; j++ ) { 372 ctrl[j][i] = points[j*width+i]; 373 } 374 } 375 376 for ( dir = 0 ; dir < 2 ; dir++ ) { 377 378 for ( j = 0 ; j < MAX_GRID_SIZE ; j++ ) { 379 errorTable[dir][j] = 0; 380 } 381 382 // horizontal subdivisions 383 for ( j = 0 ; j + 2 < width ; j += 2 ) { 384 // check subdivided midpoints against control points 385 386 // FIXME: also check midpoints of adjacent patches against the control points 387 // this would basically stitch all patches in the same LOD group together. 388 389 maxLen = 0; 390 for ( i = 0 ; i < height ; i++ ) { 391 vec3_t midxyz; 392 vec3_t midxyz2; 393 vec3_t dir; 394 vec3_t projected; 395 float d; 396 397 // calculate the point on the curve 398 for ( l = 0 ; l < 3 ; l++ ) { 399 midxyz[l] = (ctrl[i][j].xyz[l] + ctrl[i][j+1].xyz[l] * 2 400 + ctrl[i][j+2].xyz[l] ) * 0.25f; 401 } 402 403 // see how far off the line it is 404 // using dist-from-line will not account for internal 405 // texture warping, but it gives a lot less polygons than 406 // dist-from-midpoint 407 VectorSubtract( midxyz, ctrl[i][j].xyz, midxyz ); 408 VectorSubtract( ctrl[i][j+2].xyz, ctrl[i][j].xyz, dir ); 409 VectorNormalize( dir ); 410 411 d = DotProduct( midxyz, dir ); 412 VectorScale( dir, d, projected ); 413 VectorSubtract( midxyz, projected, midxyz2); 414 len = VectorLengthSquared( midxyz2 ); // we will do the sqrt later 415 if ( len > maxLen ) { 416 maxLen = len; 417 } 418 } 419 420 maxLen = sqrt(maxLen); 421 422 // if all the points are on the lines, remove the entire columns 423 if ( maxLen < 0.1f ) { 424 errorTable[dir][j+1] = 999; 425 continue; 426 } 427 428 // see if we want to insert subdivided columns 429 if ( width + 2 > MAX_GRID_SIZE ) { 430 errorTable[dir][j+1] = 1.0f/maxLen; 431 continue; // can't subdivide any more 432 } 433 434 if ( maxLen <= r_subdivisions->value ) { 435 errorTable[dir][j+1] = 1.0f/maxLen; 436 continue; // didn't need subdivision 437 } 438 439 errorTable[dir][j+2] = 1.0f/maxLen; 440 441 // insert two columns and replace the peak 442 width += 2; 443 for ( i = 0 ; i < height ; i++ ) { 444 LerpDrawVert( &ctrl[i][j], &ctrl[i][j+1], &prev ); 445 LerpDrawVert( &ctrl[i][j+1], &ctrl[i][j+2], &next ); 446 LerpDrawVert( &prev, &next, &mid ); 447 448 for ( k = width - 1 ; k > j + 3 ; k-- ) { 449 ctrl[i][k] = ctrl[i][k-2]; 450 } 451 ctrl[i][j + 1] = prev; 452 ctrl[i][j + 2] = mid; 453 ctrl[i][j + 3] = next; 454 } 455 456 // back up and recheck this set again, it may need more subdivision 457 j -= 2; 458 459 } 460 461 Transpose( width, height, ctrl ); 462 t = width; 463 width = height; 464 height = t; 465 } 466 467 468 // put all the aproximating points on the curve 469 PutPointsOnCurve( ctrl, width, height ); 470 471 // cull out any rows or columns that are colinear 472 for ( i = 1 ; i < width-1 ; i++ ) { 473 if ( errorTable[0][i] != 999 ) { 474 continue; 475 } 476 for ( j = i+1 ; j < width ; j++ ) { 477 for ( k = 0 ; k < height ; k++ ) { 478 ctrl[k][j-1] = ctrl[k][j]; 479 } 480 errorTable[0][j-1] = errorTable[0][j]; 481 } 482 width--; 483 } 484 485 for ( i = 1 ; i < height-1 ; i++ ) { 486 if ( errorTable[1][i] != 999 ) { 487 continue; 488 } 489 for ( j = i+1 ; j < height ; j++ ) { 490 for ( k = 0 ; k < width ; k++ ) { 491 ctrl[j-1][k] = ctrl[j][k]; 492 } 493 errorTable[1][j-1] = errorTable[1][j]; 494 } 495 height--; 496 } 497 498 #if 1 499 // flip for longest tristrips as an optimization 500 // the results should be visually identical with or 501 // without this step 502 if ( height > width ) { 503 Transpose( width, height, ctrl ); 504 InvertErrorTable( errorTable, width, height ); 505 t = width; 506 width = height; 507 height = t; 508 InvertCtrl( width, height, ctrl ); 509 } 510 #endif 511 512 // calculate normals 513 MakeMeshNormals( width, height, ctrl ); 514 515 return R_CreateSurfaceGridMesh( width, height, ctrl, errorTable ); 516 } 517 518 /* 519 =============== 520 R_GridInsertColumn 521 =============== 522 */ 523 srfGridMesh_t *R_GridInsertColumn( srfGridMesh_t *grid, int column, int row, vec3_t point, float loderror ) { 524 int i, j; 525 int width, height, oldwidth; 526 MAC_STATIC drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE]; 527 float errorTable[2][MAX_GRID_SIZE]; 528 float lodRadius; 529 vec3_t lodOrigin; 530 531 oldwidth = 0; 532 width = grid->width + 1; 533 if (width > MAX_GRID_SIZE) 534 return NULL; 535 height = grid->height; 536 for (i = 0; i < width; i++) { 537 if (i == column) { 538 //insert new column 539 for (j = 0; j < grid->height; j++) { 540 LerpDrawVert( &grid->verts[j * grid->width + i-1], &grid->verts[j * grid->width + i], &ctrl[j][i] ); 541 if (j == row) 542 VectorCopy(point, ctrl[j][i].xyz); 543 } 544 errorTable[0][i] = loderror; 545 continue; 546 } 547 errorTable[0][i] = grid->widthLodError[oldwidth]; 548 for (j = 0; j < grid->height; j++) { 549 ctrl[j][i] = grid->verts[j * grid->width + oldwidth]; 550 } 551 oldwidth++; 552 } 553 for (j = 0; j < grid->height; j++) { 554 errorTable[1][j] = grid->heightLodError[j]; 555 } 556 // put all the aproximating points on the curve 557 //PutPointsOnCurve( ctrl, width, height ); 558 // calculate normals 559 MakeMeshNormals( width, height, ctrl ); 560 561 VectorCopy(grid->lodOrigin, lodOrigin); 562 lodRadius = grid->lodRadius; 563 // free the old grid 564 R_FreeSurfaceGridMesh(grid); 565 // create a new grid 566 grid = R_CreateSurfaceGridMesh( width, height, ctrl, errorTable ); 567 grid->lodRadius = lodRadius; 568 VectorCopy(lodOrigin, grid->lodOrigin); 569 return grid; 570 } 571 572 /* 573 =============== 574 R_GridInsertRow 575 =============== 576 */ 577 srfGridMesh_t *R_GridInsertRow( srfGridMesh_t *grid, int row, int column, vec3_t point, float loderror ) { 578 int i, j; 579 int width, height, oldheight; 580 MAC_STATIC drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE]; 581 float errorTable[2][MAX_GRID_SIZE]; 582 float lodRadius; 583 vec3_t lodOrigin; 584 585 oldheight = 0; 586 width = grid->width; 587 height = grid->height + 1; 588 if (height > MAX_GRID_SIZE) 589 return NULL; 590 for (i = 0; i < height; i++) { 591 if (i == row) { 592 //insert new row 593 for (j = 0; j < grid->width; j++) { 594 LerpDrawVert( &grid->verts[(i-1) * grid->width + j], &grid->verts[i * grid->width + j], &ctrl[i][j] ); 595 if (j == column) 596 VectorCopy(point, ctrl[i][j].xyz); 597 } 598 errorTable[1][i] = loderror; 599 continue; 600 } 601 errorTable[1][i] = grid->heightLodError[oldheight]; 602 for (j = 0; j < grid->width; j++) { 603 ctrl[i][j] = grid->verts[oldheight * grid->width + j]; 604 } 605 oldheight++; 606 } 607 for (j = 0; j < grid->width; j++) { 608 errorTable[0][j] = grid->widthLodError[j]; 609 } 610 // put all the aproximating points on the curve 611 //PutPointsOnCurve( ctrl, width, height ); 612 // calculate normals 613 MakeMeshNormals( width, height, ctrl ); 614 615 VectorCopy(grid->lodOrigin, lodOrigin); 616 lodRadius = grid->lodRadius; 617 // free the old grid 618 R_FreeSurfaceGridMesh(grid); 619 // create a new grid 620 grid = R_CreateSurfaceGridMesh( width, height, ctrl, errorTable ); 621 grid->lodRadius = lodRadius; 622 VectorCopy(lodOrigin, grid->lodOrigin); 623 return grid; 624 }