1/* 2Copyright (C) 1996-1997 Id Software, Inc. 3 4This program is free software; you can redistribute it and/or 5modify it under the terms of the GNU General Public License 6as published by the Free Software Foundation; either version 2 7of the License, or (at your option) any later version. 8 9This program is distributed in the hope that it will be useful, 10but WITHOUT ANY WARRANTY; without even the implied warranty of 11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 12 13See the GNU General Public License for more details. 14 15You should have received a copy of the GNU General Public License 16along with this program; if not, write to the Free Software 17Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 18 19*/ 20// r_edge.c 21 22#include "quakedef.h" 23#include "r_local.h" 24 25#if 0 26// FIXME 27the complex cases add new polys on most lines, so dont optimize for keeping them the same 28have multiple free span lists to try to get better coherence? 29low depth complexity -- 1 to 3 or so 30 31this breaks spans at every edge, even hidden ones (bad) 32 33have a sentinal at both ends? 34#endif 35 36 37edge_t *auxedges; 38edge_t *r_edges, *edge_p, *edge_max; 39 40surf_t *surfaces, *surface_p, *surf_max; 41 42// surfaces are generated in back to front order by the bsp, so if a surf 43// pointer is greater than another one, it should be drawn in front 44// surfaces[1] is the background, and is used as the active surface stack 45 46edge_t *newedges[MAXHEIGHT]; 47edge_t *removeedges[MAXHEIGHT]; 48 49espan_t *span_p, *max_span_p; 50 51int r_currentkey; 52 53extern int screenwidth; 54 55int current_iv; 56 57int edge_head_u_shift20, edge_tail_u_shift20; 58 59static void (*pdrawfunc)(void); 60 61edge_t edge_head; 62edge_t edge_tail; 63edge_t edge_aftertail; 64edge_t edge_sentinel; 65 66float fv; 67 68void R_GenerateSpans (void); 69void R_GenerateSpansBackward (void); 70 71void R_LeadingEdge (edge_t *edge); 72void R_LeadingEdgeBackwards (edge_t *edge); 73void R_TrailingEdge (surf_t *surf, edge_t *edge); 74 75 76//============================================================================= 77 78 79/* 80============== 81R_DrawCulledPolys 82============== 83*/ 84void R_DrawCulledPolys (void) 85{ 86 surf_t *s; 87 msurface_t *pface; 88 89 currententity = &cl_entities[0]; 90 91 if (r_worldpolysbacktofront) 92 { 93 for (s=surface_p-1 ; s>&surfaces[1] ; s--) 94 { 95 if (!s->spans) 96 continue; 97 98 if (!(s->flags & SURF_DRAWBACKGROUND)) 99 { 100 pface = (msurface_t *)s->data; 101 R_RenderPoly (pface, 15); 102 } 103 } 104 } 105 else 106 { 107 for (s = &surfaces[1] ; s<surface_p ; s++) 108 { 109 if (!s->spans) 110 continue; 111 112 if (!(s->flags & SURF_DRAWBACKGROUND)) 113 { 114 pface = (msurface_t *)s->data; 115 R_RenderPoly (pface, 15); 116 } 117 } 118 } 119} 120 121 122/* 123============== 124R_BeginEdgeFrame 125============== 126*/ 127void R_BeginEdgeFrame (void) 128{ 129 int v; 130 131 edge_p = r_edges; 132 edge_max = &r_edges[r_numallocatededges]; 133 134 surface_p = &surfaces[2]; // background is surface 1, 135 // surface 0 is a dummy 136 surfaces[1].spans = NULL; // no background spans yet 137 surfaces[1].flags = SURF_DRAWBACKGROUND; 138 139// put the background behind everything in the world 140 if (r_draworder.value) 141 { 142 pdrawfunc = R_GenerateSpansBackward; 143 surfaces[1].key = 0; 144 r_currentkey = 1; 145 } 146 else 147 { 148 pdrawfunc = R_GenerateSpans; 149 surfaces[1].key = 0x7FFFFFFF; 150 r_currentkey = 0; 151 } 152 153// FIXME: set with memset 154 for (v=r_refdef.vrect.y ; v<r_refdef.vrectbottom ; v++) 155 { 156 newedges[v] = removeedges[v] = NULL; 157 } 158} 159 160 161#if !id386 162 163/* 164============== 165R_InsertNewEdges 166 167Adds the edges in the linked list edgestoadd, adding them to the edges in the 168linked list edgelist. edgestoadd is assumed to be sorted on u, and non-empty (this is actually newedges[v]). edgelist is assumed to be sorted on u, with a 169sentinel at the end (actually, this is the active edge table starting at 170edge_head.next). 171============== 172*/ 173void R_InsertNewEdges (edge_t *edgestoadd, edge_t *edgelist) 174{ 175 edge_t *next_edge; 176 177 do 178 { 179 next_edge = edgestoadd->next; 180edgesearch: 181 if (edgelist->u >= edgestoadd->u) 182 goto addedge; 183 edgelist=edgelist->next; 184 if (edgelist->u >= edgestoadd->u) 185 goto addedge; 186 edgelist=edgelist->next; 187 if (edgelist->u >= edgestoadd->u) 188 goto addedge; 189 edgelist=edgelist->next; 190 if (edgelist->u >= edgestoadd->u) 191 goto addedge; 192 edgelist=edgelist->next; 193 goto edgesearch; 194 195 // insert edgestoadd before edgelist 196addedge: 197 edgestoadd->next = edgelist; 198 edgestoadd->prev = edgelist->prev; 199 edgelist->prev->next = edgestoadd; 200 edgelist->prev = edgestoadd; 201 } while ((edgestoadd = next_edge) != NULL); 202} 203 204#endif // !id386 205 206 207#if !id386 208 209/* 210============== 211R_RemoveEdges 212============== 213*/ 214void R_RemoveEdges (edge_t *pedge) 215{ 216 217 do 218 { 219 pedge->next->prev = pedge->prev; 220 pedge->prev->next = pedge->next; 221 } while ((pedge = pedge->nextremove) != NULL); 222} 223 224#endif // !id386 225 226 227#if !id386 228 229/* 230============== 231R_StepActiveU 232============== 233*/ 234void R_StepActiveU (edge_t *pedge) 235{ 236 edge_t *pnext_edge, *pwedge; 237 238 while (1) 239 { 240nextedge: 241 pedge->u += pedge->u_step; 242 if (pedge->u < pedge->prev->u) 243 goto pushback; 244 pedge = pedge->next; 245 246 pedge->u += pedge->u_step; 247 if (pedge->u < pedge->prev->u) 248 goto pushback; 249 pedge = pedge->next; 250 251 pedge->u += pedge->u_step; 252 if (pedge->u < pedge->prev->u) 253 goto pushback; 254 pedge = pedge->next; 255 256 pedge->u += pedge->u_step; 257 if (pedge->u < pedge->prev->u) 258 goto pushback; 259 pedge = pedge->next; 260 261 goto nextedge; 262 263pushback: 264 if (pedge == &edge_aftertail) 265 return; 266 267 // push it back to keep it sorted 268 pnext_edge = pedge->next; 269 270 // pull the edge out of the edge list 271 pedge->next->prev = pedge->prev; 272 pedge->prev->next = pedge->next; 273 274 // find out where the edge goes in the edge list 275 pwedge = pedge->prev->prev; 276 277 while (pwedge->u > pedge->u) 278 { 279 pwedge = pwedge->prev; 280 } 281 282 // put the edge back into the edge list 283 pedge->next = pwedge->next; 284 pedge->prev = pwedge; 285 pedge->next->prev = pedge; 286 pwedge->next = pedge; 287 288 pedge = pnext_edge; 289 if (pedge == &edge_tail) 290 return; 291 } 292} 293 294#endif // !id386 295 296 297/* 298============== 299R_CleanupSpan 300============== 301*/ 302void R_CleanupSpan () 303{ 304 surf_t *surf; 305 int iu; 306 espan_t *span; 307 308// now that we've reached the right edge of the screen, we're done with any 309// unfinished surfaces, so emit a span for whatever's on top 310 surf = surfaces[1].next; 311 iu = edge_tail_u_shift20; 312 if (iu > surf->last_u) 313 { 314 span = span_p++; 315 span->u = surf->last_u; 316 span->count = iu - span->u; 317 span->v = current_iv; 318 span->pnext = surf->spans; 319 surf->spans = span; 320 } 321 322// reset spanstate for all surfaces in the surface stack 323 do 324 { 325 surf->spanstate = 0; 326 surf = surf->next; 327 } while (surf != &surfaces[1]); 328} 329 330 331/* 332============== 333R_LeadingEdgeBackwards 334============== 335*/ 336void R_LeadingEdgeBackwards (edge_t *edge) 337{ 338 espan_t *span; 339 surf_t *surf, *surf2; 340 int iu; 341 342// it's adding a new surface in, so find the correct place 343 surf = &surfaces[edge->surfs[1]]; 344 345// don't start a span if this is an inverted span, with the end 346// edge preceding the start edge (that is, we've already seen the 347// end edge) 348 if (++surf->spanstate == 1) 349 { 350 surf2 = surfaces[1].next; 351 352 if (surf->key > surf2->key) 353 goto newtop; 354 355 // if it's two surfaces on the same plane, the one that's already 356 // active is in front, so keep going unless it's a bmodel 357 if (surf->insubmodel && (surf->key == surf2->key)) 358 { 359 // must be two bmodels in the same leaf; don't care, because they'll 360 // never be farthest anyway 361 goto newtop; 362 } 363 364continue_search: 365 366 do 367 { 368 surf2 = surf2->next; 369 } while (surf->key < surf2->key); 370 371 if (surf->key == surf2->key) 372 { 373 // if it's two surfaces on the same plane, the one that's already 374 // active is in front, so keep going unless it's a bmodel 375 if (!surf->insubmodel) 376 goto continue_search; 377 378 // must be two bmodels in the same leaf; don't care which is really 379 // in front, because they'll never be farthest anyway 380 } 381 382 goto gotposition; 383 384newtop: 385 // emit a span (obscures current top) 386 iu = edge->u >> 20; 387 388 if (iu > surf2->last_u) 389 { 390 span = span_p++; 391 span->u = surf2->last_u; 392 span->count = iu - span->u; 393 span->v = current_iv; 394 span->pnext = surf2->spans; 395 surf2->spans = span; 396 } 397 398 // set last_u on the new span 399 surf->last_u = iu; 400 401gotposition: 402 // insert before surf2 403 surf->next = surf2; 404 surf->prev = surf2->prev; 405 surf2->prev->next = surf; 406 surf2->prev = surf; 407 } 408} 409 410 411/* 412============== 413R_TrailingEdge 414============== 415*/ 416void R_TrailingEdge (surf_t *surf, edge_t *edge) 417{ 418 espan_t *span; 419 int iu; 420 421// don't generate a span if this is an inverted span, with the end 422// edge preceding the start edge (that is, we haven't seen the 423// start edge yet) 424 if (--surf->spanstate == 0) 425 { 426 if (surf->insubmodel) 427 r_bmodelactive--; 428 429 if (surf == surfaces[1].next) 430 { 431 // emit a span (current top going away) 432 iu = edge->u >> 20; 433 if (iu > surf->last_u) 434 { 435 span = span_p++; 436 span->u = surf->last_u; 437 span->count = iu - span->u; 438 span->v = current_iv; 439 span->pnext = surf->spans; 440 surf->spans = span; 441 } 442 443 // set last_u on the surface below 444 surf->next->last_u = iu; 445 } 446 447 surf->prev->next = surf->next; 448 surf->next->prev = surf->prev; 449 } 450} 451 452 453#if !id386 454 455/* 456============== 457R_LeadingEdge 458============== 459*/ 460void R_LeadingEdge (edge_t *edge) 461{ 462 espan_t *span; 463 surf_t *surf, *surf2; 464 int iu; 465 double fu, newzi, testzi, newzitop, newzibottom; 466 467 if (edge->surfs[1]) 468 { 469 // it's adding a new surface in, so find the correct place 470 surf = &surfaces[edge->surfs[1]]; 471 472 // don't start a span if this is an inverted span, with the end 473 // edge preceding the start edge (that is, we've already seen the 474 // end edge) 475 if (++surf->spanstate == 1) 476 { 477 if (surf->insubmodel) 478 r_bmodelactive++; 479 480 surf2 = surfaces[1].next; 481 482 if (surf->key < surf2->key) 483 goto newtop; 484 485 // if it's two surfaces on the same plane, the one that's already 486 // active is in front, so keep going unless it's a bmodel 487 if (surf->insubmodel && (surf->key == surf2->key)) 488 { 489 // must be two bmodels in the same leaf; sort on 1/z 490 fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000); 491 newzi = surf->d_ziorigin + fv*surf->d_zistepv + 492 fu*surf->d_zistepu; 493 newzibottom = newzi * 0.99; 494 495 testzi = surf2->d_ziorigin + fv*surf2->d_zistepv + 496 fu*surf2->d_zistepu; 497 498 if (newzibottom >= testzi) 499 { 500 goto newtop; 501 } 502 503 newzitop = newzi * 1.01; 504 if (newzitop >= testzi) 505 { 506 if (surf->d_zistepu >= surf2->d_zistepu) 507 { 508 goto newtop; 509 } 510 } 511 } 512 513continue_search: 514 515 do 516 { 517 surf2 = surf2->next; 518 } while (surf->key > surf2->key); 519 520 if (surf->key == surf2->key) 521 { 522 // if it's two surfaces on the same plane, the one that's already 523 // active is in front, so keep going unless it's a bmodel 524 if (!surf->insubmodel) 525 goto continue_search; 526 527 // must be two bmodels in the same leaf; sort on 1/z 528 fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000); 529 newzi = surf->d_ziorigin + fv*surf->d_zistepv + 530 fu*surf->d_zistepu; 531 newzibottom = newzi * 0.99; 532 533 testzi = surf2->d_ziorigin + fv*surf2->d_zistepv + 534 fu*surf2->d_zistepu; 535 536 if (newzibottom >= testzi) 537 { 538 goto gotposition; 539 } 540 541 newzitop = newzi * 1.01; 542 if (newzitop >= testzi) 543 { 544 if (surf->d_zistepu >= surf2->d_zistepu) 545 { 546 goto gotposition; 547 } 548 } 549 550 goto continue_search; 551 } 552 553 goto gotposition; 554 555newtop: 556 // emit a span (obscures current top) 557 iu = edge->u >> 20; 558 559 if (iu > surf2->last_u) 560 { 561 span = span_p++; 562 span->u = surf2->last_u; 563 span->count = iu - span->u; 564 span->v = current_iv; 565 span->pnext = surf2->spans; 566 surf2->spans = span; 567 } 568 569 // set last_u on the new span 570 surf->last_u = iu; 571 572gotposition: 573 // insert before surf2 574 surf->next = surf2; 575 surf->prev = surf2->prev; 576 surf2->prev->next = surf; 577 surf2->prev = surf; 578 } 579 } 580} 581 582 583/* 584============== 585R_GenerateSpans 586============== 587*/ 588void R_GenerateSpans (void) 589{ 590 edge_t *edge; 591 surf_t *surf; 592 593 r_bmodelactive = 0; 594 595// clear active surfaces to just the background surface 596 surfaces[1].next = surfaces[1].prev = &surfaces[1]; 597 surfaces[1].last_u = edge_head_u_shift20; 598 599// generate spans 600 for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next) 601 { 602 if (edge->surfs[0]) 603 { 604 // it has a left surface, so a surface is going away for this span 605 surf = &surfaces[edge->surfs[0]]; 606 607 R_TrailingEdge (surf, edge); 608 609 if (!edge->surfs[1]) 610 continue; 611 } 612 613 R_LeadingEdge (edge); 614 } 615 616 R_CleanupSpan (); 617} 618 619#endif // !id386 620 621 622/* 623============== 624R_GenerateSpansBackward 625============== 626*/ 627void R_GenerateSpansBackward (void) 628{ 629 edge_t *edge; 630 631 r_bmodelactive = 0; 632 633// clear active surfaces to just the background surface 634 surfaces[1].next = surfaces[1].prev = &surfaces[1]; 635 surfaces[1].last_u = edge_head_u_shift20; 636 637// generate spans 638 for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next) 639 { 640 if (edge->surfs[0]) 641 R_TrailingEdge (&surfaces[edge->surfs[0]], edge); 642 643 if (edge->surfs[1]) 644 R_LeadingEdgeBackwards (edge); 645 } 646 647 R_CleanupSpan (); 648} 649 650 651/* 652============== 653R_ScanEdges 654 655Input: 656newedges[] array 657 this has links to edges, which have links to surfaces 658 659Output: 660Each surface has a linked list of its visible spans 661============== 662*/ 663void R_ScanEdges (void) 664{ 665 int iv, bottom; 666 byte basespans[MAXSPANS*sizeof(espan_t)+CACHE_SIZE]; 667 espan_t *basespan_p; 668 surf_t *s; 669 670 basespan_p = (espan_t *) 671 ((long)(basespans + CACHE_SIZE - 1) & ~(CACHE_SIZE - 1)); 672 max_span_p = &basespan_p[MAXSPANS - r_refdef.vrect.width]; 673 674 span_p = basespan_p; 675 676// clear active edges to just the background edges around the whole screen 677// FIXME: most of this only needs to be set up once 678 edge_head.u = r_refdef.vrect.x << 20; 679 edge_head_u_shift20 = edge_head.u >> 20; 680 edge_head.u_step = 0; 681 edge_head.prev = NULL; 682 edge_head.next = &edge_tail; 683 edge_head.surfs[0] = 0; 684 edge_head.surfs[1] = 1; 685 686 edge_tail.u = (r_refdef.vrectright << 20) + 0xFFFFF; 687 edge_tail_u_shift20 = edge_tail.u >> 20; 688 edge_tail.u_step = 0; 689 edge_tail.prev = &edge_head; 690 edge_tail.next = &edge_aftertail; 691 edge_tail.surfs[0] = 1; 692 edge_tail.surfs[1] = 0; 693 694 edge_aftertail.u = -1; // force a move 695 edge_aftertail.u_step = 0; 696 edge_aftertail.next = &edge_sentinel; 697 edge_aftertail.prev = &edge_tail; 698 699// FIXME: do we need this now that we clamp x in r_draw.c? 700 edge_sentinel.u = 2000 << 24; // make sure nothing sorts past this 701 edge_sentinel.prev = &edge_aftertail; 702 703// 704// process all scan lines 705// 706 bottom = r_refdef.vrectbottom - 1; 707 708 for (iv=r_refdef.vrect.y ; iv<bottom ; iv++) 709 { 710 current_iv = iv; 711 fv = (float)iv; 712 713 // mark that the head (background start) span is pre-included 714 surfaces[1].spanstate = 1; 715 716 if (newedges[iv]) 717 { 718 R_InsertNewEdges (newedges[iv], edge_head.next); 719 } 720 721 (*pdrawfunc) (); 722 723 // flush the span list if we can't be sure we have enough spans left for 724 // the next scan 725 if (span_p >= max_span_p) 726 { 727 VID_UnlockBuffer (); 728 S_ExtraUpdate (); // don't let sound get messed up if going slow 729 VID_LockBuffer (); 730 731 if (r_drawculledpolys) 732 { 733 R_DrawCulledPolys (); 734 } 735 else 736 { 737 D_DrawSurfaces (); 738 } 739 740 // clear the surface span pointers 741 for (s = &surfaces[1] ; s<surface_p ; s++) 742 s->spans = NULL; 743 744 span_p = basespan_p; 745 } 746 747 if (removeedges[iv]) 748 R_RemoveEdges (removeedges[iv]); 749 750 if (edge_head.next != &edge_tail) 751 R_StepActiveU (edge_head.next); 752 } 753 754// do the last scan (no need to step or sort or remove on the last scan) 755 756 current_iv = iv; 757 fv = (float)iv; 758 759// mark that the head (background start) span is pre-included 760 surfaces[1].spanstate = 1; 761 762 if (newedges[iv]) 763 R_InsertNewEdges (newedges[iv], edge_head.next); 764 765 (*pdrawfunc) (); 766 767// draw whatever's left in the span list 768 if (r_drawculledpolys) 769 R_DrawCulledPolys (); 770 else 771 D_DrawSurfaces (); 772} 773 774 775