mesh.c (17569B)
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 "qbsp.h" 24 25 26 /* 27 =============================================================== 28 29 MESH SUBDIVISION 30 31 =============================================================== 32 */ 33 34 35 int originalWidths[MAX_EXPANDED_AXIS]; 36 int originalHeights[MAX_EXPANDED_AXIS]; 37 38 int neighbors[8][2] = { 39 {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1} 40 }; 41 42 /* 43 ============ 44 LerpDrawVert 45 ============ 46 */ 47 void LerpDrawVert( drawVert_t *a, drawVert_t *b, drawVert_t *out ) { 48 out->xyz[0] = 0.5 * (a->xyz[0] + b->xyz[0]); 49 out->xyz[1] = 0.5 * (a->xyz[1] + b->xyz[1]); 50 out->xyz[2] = 0.5 * (a->xyz[2] + b->xyz[2]); 51 52 out->st[0] = 0.5 * (a->st[0] + b->st[0]); 53 out->st[1] = 0.5 * (a->st[1] + b->st[1]); 54 55 out->lightmap[0] = 0.5 * (a->lightmap[0] + b->lightmap[0]); 56 out->lightmap[1] = 0.5 * (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 void FreeMesh( mesh_t *m ) { 66 free( m->verts ); 67 free( m ); 68 } 69 70 void PrintMesh( mesh_t *m ) { 71 int i, j; 72 73 for ( i = 0 ; i < m->height ; i++ ) { 74 for ( j = 0 ; j < m->width ; j++ ) { 75 _printf("(%5.2f %5.2f %5.2f) " 76 , m->verts[i*m->width+j].xyz[0] 77 , m->verts[i*m->width+j].xyz[1] 78 , m->verts[i*m->width+j].xyz[2] ); 79 } 80 _printf("\n"); 81 } 82 } 83 84 85 mesh_t *CopyMesh( mesh_t *mesh ) { 86 mesh_t *out; 87 int size; 88 89 out = malloc( sizeof( *out ) ); 90 out->width = mesh->width; 91 out->height = mesh->height; 92 93 size = out->width * out->height * sizeof( *out->verts ); 94 out->verts = malloc( size ); 95 memcpy( out->verts, mesh->verts, size ); 96 97 return out; 98 } 99 100 101 /* 102 ================= 103 TransposeMesh 104 105 Returns a transposed copy of the mesh, freeing the original 106 ================= 107 */ 108 mesh_t *TransposeMesh( mesh_t *in ) { 109 int w, h; 110 mesh_t *out; 111 112 out = malloc( sizeof( *out ) ); 113 out->width = in->height; 114 out->height = in->width; 115 out->verts = malloc( out->width * out->height * sizeof( drawVert_t ) ); 116 117 for ( h = 0 ; h < in->height ; h++ ) { 118 for ( w = 0 ; w < in->width ; w++ ) { 119 out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ]; 120 } 121 } 122 123 FreeMesh( in ); 124 125 return out; 126 } 127 128 void InvertMesh( mesh_t *in ) { 129 int w, h; 130 drawVert_t temp; 131 132 for ( h = 0 ; h < in->height ; h++ ) { 133 for ( w = 0 ; w < in->width / 2 ; w++ ) { 134 temp = in->verts[ h * in->width + w ]; 135 in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ]; 136 in->verts[ h * in->width + in->width - 1 - w ] = temp; 137 } 138 } 139 } 140 141 /* 142 ================= 143 MakeMeshNormals 144 145 ================= 146 */ 147 void MakeMeshNormals( mesh_t in ) { 148 int i, j, k, dist; 149 vec3_t normal; 150 vec3_t sum; 151 int count; 152 vec3_t base; 153 vec3_t delta; 154 int x, y; 155 drawVert_t *dv; 156 vec3_t around[8], temp; 157 qboolean good[8]; 158 qboolean wrapWidth, wrapHeight; 159 float len; 160 161 wrapWidth = qfalse; 162 for ( i = 0 ; i < in.height ; i++ ) { 163 VectorSubtract( in.verts[i*in.width].xyz, 164 in.verts[i*in.width+in.width-1].xyz, delta ); 165 len = VectorLength( delta ); 166 if ( len > 1.0 ) { 167 break; 168 } 169 } 170 if ( i == in.height ) { 171 wrapWidth = qtrue; 172 } 173 174 wrapHeight = qfalse; 175 for ( i = 0 ; i < in.width ; i++ ) { 176 VectorSubtract( in.verts[i].xyz, 177 in.verts[i + (in.height-1)*in.width].xyz, delta ); 178 len = VectorLength( delta ); 179 if ( len > 1.0 ) { 180 break; 181 } 182 } 183 if ( i == in.width) { 184 wrapHeight = qtrue; 185 } 186 187 188 for ( i = 0 ; i < in.width ; i++ ) { 189 for ( j = 0 ; j < in.height ; j++ ) { 190 count = 0; 191 dv = &in.verts[j*in.width+i]; 192 VectorCopy( dv->xyz, base ); 193 for ( k = 0 ; k < 8 ; k++ ) { 194 VectorClear( around[k] ); 195 good[k] = qfalse; 196 197 for ( dist = 1 ; dist <= 3 ; dist++ ) { 198 x = i + neighbors[k][0] * dist; 199 y = j + neighbors[k][1] * dist; 200 if ( wrapWidth ) { 201 if ( x < 0 ) { 202 x = in.width - 1 + x; 203 } else if ( x >= in.width ) { 204 x = 1 + x - in.width; 205 } 206 } 207 if ( wrapHeight ) { 208 if ( y < 0 ) { 209 y = in.height - 1 + y; 210 } else if ( y >= in.height ) { 211 y = 1 + y - in.height; 212 } 213 } 214 215 if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) { 216 break; // edge of patch 217 } 218 VectorSubtract( in.verts[y*in.width+x].xyz, base, temp ); 219 if ( VectorNormalize( temp, temp ) == 0 ) { 220 continue; // degenerate edge, get more dist 221 } else { 222 good[k] = qtrue; 223 VectorCopy( temp, around[k] ); 224 break; // good edge 225 } 226 } 227 } 228 229 VectorClear( sum ); 230 for ( k = 0 ; k < 8 ; k++ ) { 231 if ( !good[k] || !good[(k+1)&7] ) { 232 continue; // didn't get two points 233 } 234 CrossProduct( around[(k+1)&7], around[k], normal ); 235 if ( VectorNormalize( normal, normal ) == 0 ) { 236 continue; 237 } 238 VectorAdd( normal, sum, sum ); 239 count++; 240 } 241 if ( count == 0 ) { 242 //_printf("bad normal\n"); 243 count = 1; 244 } 245 VectorNormalize( sum, dv->normal ); 246 } 247 } 248 } 249 250 /* 251 ================= 252 PutMeshOnCurve 253 254 Drops the aproximating points onto the curve 255 ================= 256 */ 257 void PutMeshOnCurve( mesh_t in ) { 258 int i, j, l; 259 float prev, next; 260 261 // put all the aproximating points on the curve 262 for ( i = 0 ; i < in.width ; i++ ) { 263 for ( j = 1 ; j < in.height ; j += 2 ) { 264 for ( l = 0 ; l < 3 ; l++ ) { 265 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5; 266 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5; 267 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5; 268 } 269 } 270 } 271 272 for ( j = 0 ; j < in.height ; j++ ) { 273 for ( i = 1 ; i < in.width ; i += 2 ) { 274 for ( l = 0 ; l < 3 ; l++ ) { 275 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5; 276 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5; 277 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5; 278 } 279 } 280 } 281 } 282 283 284 /* 285 ================= 286 SubdivideMesh 287 288 ================= 289 */ 290 mesh_t *SubdivideMesh( mesh_t in, float maxError, float minLength ) { 291 int i, j, k, l; 292 drawVert_t prev, next, mid; 293 vec3_t prevxyz, nextxyz, midxyz; 294 vec3_t delta; 295 float len; 296 mesh_t out; 297 drawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS]; 298 299 out.width = in.width; 300 out.height = in.height; 301 302 for ( i = 0 ; i < in.width ; i++ ) { 303 for ( j = 0 ; j < in.height ; j++ ) { 304 expand[j][i] = in.verts[j*in.width+i]; 305 } 306 } 307 308 for ( i = 0 ; i < in.height ; i++ ) { 309 originalHeights[i] = i; 310 } 311 for ( i = 0 ; i < in.width ; i++ ) { 312 originalWidths[i] = i; 313 } 314 315 // horizontal subdivisions 316 for ( j = 0 ; j + 2 < out.width ; j += 2 ) { 317 // check subdivided midpoints against control points 318 for ( i = 0 ; i < out.height ; i++ ) { 319 for ( l = 0 ; l < 3 ; l++ ) { 320 prevxyz[l] = expand[i][j+1].xyz[l] - expand[i][j].xyz[l]; 321 nextxyz[l] = expand[i][j+2].xyz[l] - expand[i][j+1].xyz[l]; 322 midxyz[l] = (expand[i][j].xyz[l] + expand[i][j+1].xyz[l] * 2 323 + expand[i][j+2].xyz[l] ) * 0.25; 324 } 325 326 // if the span length is too long, force a subdivision 327 if ( VectorLength( prevxyz ) > minLength 328 || VectorLength( nextxyz ) > minLength ) { 329 break; 330 } 331 332 // see if this midpoint is off far enough to subdivide 333 VectorSubtract( expand[i][j+1].xyz, midxyz, delta ); 334 len = VectorLength( delta ); 335 if ( len > maxError ) { 336 break; 337 } 338 } 339 340 if ( out.width + 2 >= MAX_EXPANDED_AXIS ) { 341 break; // can't subdivide any more 342 } 343 344 if ( i == out.height ) { 345 continue; // didn't need subdivision 346 } 347 348 // insert two columns and replace the peak 349 out.width += 2; 350 351 for ( k = out.width - 1 ; k > j + 3 ; k-- ) { 352 originalWidths[k] = originalWidths[k-2]; 353 } 354 originalWidths[j+3] = originalWidths[j+1]; 355 originalWidths[j+2] = originalWidths[j+1]; 356 originalWidths[j+1] = originalWidths[j]; 357 358 for ( i = 0 ; i < out.height ; i++ ) { 359 LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev ); 360 LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next ); 361 LerpDrawVert( &prev, &next, &mid ); 362 363 for ( k = out.width - 1 ; k > j + 3 ; k-- ) { 364 expand[i][k] = expand[i][k-2]; 365 } 366 expand[i][j + 1] = prev; 367 expand[i][j + 2] = mid; 368 expand[i][j + 3] = next; 369 } 370 371 // back up and recheck this set again, it may need more subdivision 372 j -= 2; 373 374 } 375 376 // vertical subdivisions 377 for ( j = 0 ; j + 2 < out.height ; j += 2 ) { 378 // check subdivided midpoints against control points 379 for ( i = 0 ; i < out.width ; i++ ) { 380 for ( l = 0 ; l < 3 ; l++ ) { 381 prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l]; 382 nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l]; 383 midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2 384 + expand[j+2][i].xyz[l] ) * 0.25; 385 } 386 387 // if the span length is too long, force a subdivision 388 if ( VectorLength( prevxyz ) > minLength 389 || VectorLength( nextxyz ) > minLength ) { 390 break; 391 } 392 // see if this midpoint is off far enough to subdivide 393 VectorSubtract( expand[j+1][i].xyz, midxyz, delta ); 394 len = VectorLength( delta ); 395 if ( len > maxError ) { 396 break; 397 } 398 } 399 400 if ( out.height + 2 >= MAX_EXPANDED_AXIS ) { 401 break; // can't subdivide any more 402 } 403 404 if ( i == out.width ) { 405 continue; // didn't need subdivision 406 } 407 408 // insert two columns and replace the peak 409 out.height += 2; 410 411 for ( k = out.height - 1 ; k > j + 3 ; k-- ) { 412 originalHeights[k] = originalHeights[k-2]; 413 } 414 originalHeights[j+3] = originalHeights[j+1]; 415 originalHeights[j+2] = originalHeights[j+1]; 416 originalHeights[j+1] = originalHeights[j]; 417 418 for ( i = 0 ; i < out.width ; i++ ) { 419 LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev ); 420 LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next ); 421 LerpDrawVert( &prev, &next, &mid ); 422 423 for ( k = out.height - 1 ; k > j + 3 ; k-- ) { 424 expand[k][i] = expand[k-2][i]; 425 } 426 expand[j+1][i] = prev; 427 expand[j+2][i] = mid; 428 expand[j+3][i] = next; 429 } 430 431 // back up and recheck this set again, it may need more subdivision 432 j -= 2; 433 434 } 435 436 // collapse the verts 437 438 out.verts = &expand[0][0]; 439 for ( i = 1 ; i < out.height ; i++ ) { 440 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) ); 441 } 442 443 return CopyMesh(&out); 444 } 445 446 /* 447 ================ 448 ProjectPointOntoVector 449 ================ 450 */ 451 void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj ) 452 { 453 vec3_t pVec, vec; 454 455 VectorSubtract( point, vStart, pVec ); 456 VectorSubtract( vEnd, vStart, vec ); 457 VectorNormalize( vec, vec ); 458 // project onto the directional vector for this segment 459 VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj ); 460 } 461 462 /* 463 ================ 464 RemoveLinearMeshColumsRows 465 ================ 466 */ 467 mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) { 468 int i, j, k; 469 float len, maxLength; 470 vec3_t proj, dir; 471 mesh_t out; 472 drawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS]; 473 474 out.width = in->width; 475 out.height = in->height; 476 477 for ( i = 0 ; i < in->width ; i++ ) { 478 for ( j = 0 ; j < in->height ; j++ ) { 479 expand[j][i] = in->verts[j*in->width+i]; 480 } 481 } 482 483 for ( j = 1 ; j < out.width - 1; j++ ) { 484 maxLength = 0; 485 for ( i = 0 ; i < out.height ; i++ ) { 486 ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj); 487 VectorSubtract(expand[i][j].xyz, proj, dir); 488 len = VectorLength(dir); 489 if (len > maxLength) { 490 maxLength = len; 491 } 492 } 493 if (maxLength < 0.1) 494 { 495 out.width--; 496 for ( i = 0 ; i < out.height ; i++ ) { 497 for (k = j; k < out.width; k++) { 498 expand[i][k] = expand[i][k+1]; 499 } 500 } 501 for (k = j; k < out.width; k++) { 502 originalWidths[k] = originalWidths[k+1]; 503 } 504 j--; 505 } 506 } 507 for ( j = 1 ; j < out.height - 1; j++ ) { 508 maxLength = 0; 509 for ( i = 0 ; i < out.width ; i++ ) { 510 ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj); 511 VectorSubtract(expand[j][i].xyz, proj, dir); 512 len = VectorLength(dir); 513 if (len > maxLength) { 514 maxLength = len; 515 } 516 } 517 if (maxLength < 0.1) 518 { 519 out.height--; 520 for ( i = 0 ; i < out.width ; i++ ) { 521 for (k = j; k < out.height; k++) { 522 expand[k][i] = expand[k+1][i]; 523 } 524 } 525 for (k = j; k < out.height; k++) { 526 originalHeights[k] = originalHeights[k+1]; 527 } 528 j--; 529 } 530 } 531 // collapse the verts 532 out.verts = &expand[0][0]; 533 for ( i = 1 ; i < out.height ; i++ ) { 534 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) ); 535 } 536 537 return CopyMesh(&out); 538 } 539 540 /* 541 ============ 542 LerpDrawVertAmount 543 ============ 544 */ 545 void LerpDrawVertAmount( drawVert_t *a, drawVert_t *b, float amount, drawVert_t *out ) { 546 out->xyz[0] = a->xyz[0] + amount * (b->xyz[0] - a->xyz[0]); 547 out->xyz[1] = a->xyz[1] + amount * (b->xyz[1] - a->xyz[1]); 548 out->xyz[2] = a->xyz[2] + amount * (b->xyz[2] - a->xyz[2]); 549 550 out->st[0] = a->st[0] + amount * (b->st[0] - a->st[0]); 551 out->st[1] = a->st[1] + amount * (b->st[1] - a->st[1]); 552 553 out->lightmap[0] = a->lightmap[0] + amount * (b->lightmap[0] - a->lightmap[0]); 554 out->lightmap[1] = a->lightmap[1] + amount * (b->lightmap[1] - a->lightmap[1]); 555 556 out->color[0] = a->color[0] + amount * (b->color[0] - a->color[0]); 557 out->color[1] = a->color[1] + amount * (b->color[1] - a->color[1]); 558 out->color[2] = a->color[2] + amount * (b->color[2] - a->color[2]); 559 out->color[3] = a->color[3] + amount * (b->color[3] - a->color[3]); 560 561 out->normal[0] = a->normal[0] + amount * (b->normal[0] - a->normal[0]); 562 out->normal[1] = a->normal[1] + amount * (b->normal[1] - a->normal[1]); 563 out->normal[2] = a->normal[2] + amount * (b->normal[2] - a->normal[2]); 564 VectorNormalize(out->normal, out->normal); 565 } 566 567 /* 568 ================= 569 SubdivideMeshQuads 570 ================= 571 */ 572 mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int widthtable[], int heighttable[]) { 573 int i, j, k, w, h, maxsubdivisions, subdivisions; 574 vec3_t dir; 575 float length, maxLength, amount; 576 mesh_t out; 577 drawVert_t expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS]; 578 579 out.width = in->width; 580 out.height = in->height; 581 582 for ( i = 0 ; i < in->width ; i++ ) { 583 for ( j = 0 ; j < in->height ; j++ ) { 584 expand[j][i] = in->verts[j*in->width+i]; 585 } 586 } 587 588 if (maxsize > MAX_EXPANDED_AXIS) 589 Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS"); 590 591 // horizontal subdivisions 592 593 maxsubdivisions = (maxsize - in->width) / (in->width - 1); 594 595 for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) { 596 maxLength = 0; 597 for ( i = 0 ; i < out.height ; i++ ) { 598 VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir); 599 length = VectorLength( dir ); 600 if (length > maxLength) { 601 maxLength = length; 602 } 603 } 604 605 subdivisions = (int) (maxLength / minLength); 606 if (subdivisions > maxsubdivisions) 607 subdivisions = maxsubdivisions; 608 609 widthtable[w] = subdivisions + 1; 610 if (subdivisions <= 0) 611 continue; 612 613 out.width += subdivisions; 614 615 for ( k = out.width - 1; k >= j + subdivisions; k-- ) { 616 originalWidths[k] = originalWidths[k-subdivisions]; 617 } 618 for (k = 1; k <= subdivisions; k++) { 619 originalWidths[j+k] = originalWidths[j]; 620 } 621 622 for ( i = 0 ; i < out.height ; i++ ) { 623 for ( k = out.width - 1 ; k > j + subdivisions; k-- ) { 624 expand[i][k] = expand[i][k-subdivisions]; 625 } 626 for (k = 1; k <= subdivisions; k++) 627 { 628 amount = (float) k / (subdivisions + 1); 629 LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]); 630 } 631 } 632 } 633 634 maxsubdivisions = (maxsize - in->height) / (in->height - 1); 635 636 for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) { 637 maxLength = 0; 638 for ( i = 0 ; i < out.width ; i++ ) { 639 VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir); 640 length = VectorLength( dir ); 641 if (length > maxLength) { 642 maxLength = length; 643 } 644 } 645 646 subdivisions = (int) (maxLength / minLength); 647 if (subdivisions > maxsubdivisions) 648 subdivisions = maxsubdivisions; 649 650 heighttable[h] = subdivisions + 1; 651 if (subdivisions <= 0) 652 continue; 653 654 out.height += subdivisions; 655 656 for ( k = out.height - 1; k >= j + subdivisions; k-- ) { 657 originalHeights[k] = originalHeights[k-subdivisions]; 658 } 659 for (k = 1; k <= subdivisions; k++) { 660 originalHeights[j+k] = originalHeights[j]; 661 } 662 663 for ( i = 0 ; i < out.width ; i++ ) { 664 for ( k = out.height - 1 ; k > j + subdivisions; k-- ) { 665 expand[k][i] = expand[k-subdivisions][i]; 666 } 667 for (k = 1; k <= subdivisions; k++) 668 { 669 amount = (float) k / (subdivisions + 1); 670 LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]); 671 } 672 } 673 } 674 675 // collapse the verts 676 out.verts = &expand[0][0]; 677 for ( i = 1 ; i < out.height ; i++ ) { 678 memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) ); 679 } 680 681 return CopyMesh(&out); 682 }