r_clip.c

   1
   2 #include "quakedef.h"
   3
   4 typedef struct clipsurf_s
   5 {
   6         struct clipsurf_s *next, *prev;
   7         int state;
   8         int visible;
   9         int solid;
  10         int removed;
  11         void (*callback)(void *nativedata, void *nativedata2);
  12         void *nativedata;
  13         void *nativedata2;
  14         float wstepx, wstepy, w00;
  15         // wcurrent is a cached copy of w00 + wstepy * y,
  16         // updated each time the surface is added to the stack,
  17         // for quicker comparisons.
  18         float wcurrent;
  19 }
  20 clipsurf_t;
  21
  22 typedef struct clipedge_s
  23 {
  24         float x, realx, realxstep;
  25         struct clipedge_s *next, *prev, *nextremove;
  26         clipsurf_t *psurf;
  27         int leading;
  28         int pad;
  29 }
  30 clipedge_t;
  31
  32 clipsurf_t *pavailsurf, *clipsurfs, *clipsurfsend;
  33 clipedge_t *pavailedge, *clipedges, *clipedgesend, *newedges, **removeedges;
  34
  35 clipsurf_t surfstack;
  36 clipedge_t edgehead, edgetail;
  37 clipedge_t maxedge = {2000000000.0f};
  38
  39 cvar_t r_clipwidth = {0, "r_clipwidth", "800"};
  40 cvar_t r_clipheight = {0, "r_clipheight", "600"};
  41 cvar_t r_clipedges = {CVAR_SAVE, "r_clipedges", "32768"};
  42 cvar_t r_clipsurfaces = {CVAR_SAVE, "r_clipsurfaces", "8192"};
  43
  44 int clipwidth = 0, clipheight = 0;
  45 int maxclipsurfs = 0, maxclipedges = 0;
  46 int needededges, neededsurfs;
  47
  48 #if CLIPTEST
  49 typedef struct
  50 {
  51         float w; // inverse depth (1/z)
  52 }
  53 clippixel_t;
  54
  55 clippixel_t *clipbuffer;
  56 #endif
  57
  58 float r_clip_viewmatrix[3][3], r_clip_viewmulx, r_clip_viewmuly, r_clip_viewcenterx, r_clip_viewcentery;
  59 tinyplane_t r_clip_viewplane[5];
  60
  61 mempool_t *r_clip_mempool;
  62
  63 void R_Clip_MakeViewMatrix(void)
  64 {
  65         float pixelaspect, screenaspect, horizontalfieldofview, verticalfieldofview;
  66         pixelaspect = (float) clipheight / (float) clipwidth * 320 / 240.0;
  67         horizontalfieldofview = 2.0 * tan (r_refdef.fov_x/360*M_PI);
  68         screenaspect = clipwidth * pixelaspect / clipheight;
  69         verticalfieldofview = horizontalfieldofview / screenaspect;
  70         r_clip_viewcenterx = clipwidth * 0.5 - 0.5;
  71         r_clip_viewcentery = clipheight * 0.5 - 0.5;
  72         r_clip_viewmulx = clipwidth / horizontalfieldofview;
  73         r_clip_viewmuly = r_clip_viewmulx * pixelaspect;
  74         // this constructs a transposed rotation matrix for the view (transposed matrices do the opposite of their normal behavior)
  75         VectorCopy (vright, r_clip_viewmatrix[0]);
  76         VectorNegate (vup, r_clip_viewmatrix[1]);
  77         VectorCopy (vpn, r_clip_viewmatrix[2]);
  78         VectorCopy (vpn, r_clip_viewplane[0].normal);
  79         r_clip_viewplane[0].dist = DotProduct(r_origin, vpn);
  80         memcpy(&r_clip_viewplane[1], &frustum[0], sizeof(tinyplane_t));
  81         memcpy(&r_clip_viewplane[2], &frustum[1], sizeof(tinyplane_t));
  82         memcpy(&r_clip_viewplane[3], &frustum[2], sizeof(tinyplane_t));
  83         memcpy(&r_clip_viewplane[4], &frustum[3], sizeof(tinyplane_t));
  84 }
  85
  86 void R_Clip_StartFrame(void)
  87 {
  88         int i;
  89         int newwidth, newheight, newmaxedges, newmaxsurfs;
  90         newwidth = bound(80, r_clipwidth.integer, vid.realwidth * 2);
  91         newheight = bound(60, r_clipheight.integer, vid.realheight * 2);
  92         newmaxedges = bound(128, r_clipedges.integer, 262144);
  93         newmaxsurfs = bound(32, r_clipsurfaces.integer, 65536);
  94         if (newwidth != clipwidth || newheight != clipheight || maxclipedges != newmaxedges || maxclipsurfs != newmaxsurfs)
  95         {
  96 #if CLIPTEST
  97                 if (clipbuffer)
  98                         Mem_Free(clipbuffer);
  99 #endif
 100                 if (clipedges)
 101                         Mem_Free(clipedges);
 102                 if (clipsurfs)
 103                         Mem_Free(clipsurfs);
 104                 if (newedges)
 105                         Mem_Free(newedges);
 106                 if (removeedges)
 107                         Mem_Free(removeedges);
 108                 clipwidth = newwidth;
 109                 clipheight = newheight;
 110                 maxclipedges = newmaxedges;
 111                 maxclipsurfs = newmaxsurfs;
 112 #if CLIPTEST
 113                 clipbuffer = Mem_Alloc(r_clip_mempool, clipwidth * clipheight * sizeof(clippixel_t));
 114 #endif
 115                 clipedges = Mem_Alloc(r_clip_mempool, maxclipedges * sizeof(clipedge_t));
 116                 clipsurfs = Mem_Alloc(r_clip_mempool, maxclipsurfs * sizeof(clipsurf_t));
 117                 newedges = Mem_Alloc(r_clip_mempool, clipheight * sizeof(clipedge_t));
 118                 removeedges = Mem_Alloc(r_clip_mempool, clipheight * sizeof(clipedge_t *));
 119                 clipedgesend = clipedges + maxclipedges;
 120                 clipsurfsend = clipsurfs + maxclipsurfs;
 121         }
 122 #if CLIPTEST
 123         memset(clipbuffer, 0, clipwidth * clipheight * sizeof(clippixel_t));
 124 #endif
 125         pavailedge = clipedges;
 126         pavailsurf = clipsurfs;
 127         // Clear the lists of edges to add and remove on each scan line.
 128
 129         needededges = 0;
 130         neededsurfs = 0;
 131         for (i = 0;i < clipheight;i++)
 132         {
 133                 newedges[i].next = &maxedge;
 134                 removeedges[i] = NULL;
 135         }
 136
 137         R_Clip_MakeViewMatrix();
 138 }
 139
 140 void ScanEdges (void);
 141
 142 void R_Clip_EndFrame(void)
 143 {
 144         ScanEdges();
 145         if (maxclipedges < needededges)
 146         {
 147                 Con_Printf("R_Clip: ran out of edges, increasing limit from %d to %d\n", maxclipedges, needededges);
 148                 Cvar_SetValue("r_clipedges", needededges);
 149         }
 150         if (maxclipsurfs < neededsurfs)
 151         {
 152                 Con_Printf("R_Clip: ran out of surfaces, increasing limit from %d to %d\n", maxclipsurfs, neededsurfs);
 153                 Cvar_SetValue("r_clipsurfaces", neededsurfs);
 154         }
 155 }
 156
 157 void r_clip_start(void)
 158 {
 159         r_clip_mempool = Mem_AllocPool("R_Clip");
 160 }
 161
 162 void r_clip_shutdown(void)
 163 {
 164         Mem_FreePool(&r_clip_mempool);
 165 #if CLIPTEST
 166         clipbuffer = NULL;
 167 #endif
 168         clipsurfs = NULL;
 169         clipedges = NULL;
 170         newedges = NULL;
 171         removeedges = NULL;
 172         clipwidth = -1;
 173         clipheight = -1;
 174 }
 175
 176 void r_clip_newmap(void)
 177 {
 178 }
 179
 180 void R_Clip_Init(void)
 181 {
 182         Cvar_RegisterVariable(&r_clipwidth);
 183         Cvar_RegisterVariable(&r_clipheight);
 184         Cvar_RegisterVariable(&r_clipedges);
 185         Cvar_RegisterVariable(&r_clipsurfaces);
 186         R_RegisterModule("R_Clip", r_clip_start, r_clip_shutdown, r_clip_newmap);
 187 }
 188
 189 int R_Clip_TriangleToPlane(vec3_t point1, vec3_t point2, vec3_t point3, tinyplane_t *p)
 190 {
 191         float y, number;
 192         vec3_t v1, v2;
 193         VectorSubtract(point1, point2, v1);
 194         VectorSubtract(point3, point2, v2);
 195         CrossProduct(v1, v2, p->normal);
 196         number = DotProduct(p->normal, p->normal);
 197         if (number >= 0.1f)
 198         {
 199                 *((int *)&y) = 0x5f3759df - ((* (int *) &number) >> 1);
 200                 y = y * (1.5f - (number * 0.5f * y * y));
 201                 VectorScale(p->normal, y, p->normal);
 202                 p->dist = DotProduct(point1, p->normal);
 203                 return true;
 204         }
 205         else
 206                 return false;
 207 }
 208
 209
 210 int R_Clip_ClipPolygonToPlane(float *in, float *out, int inpoints, int stride, tinyplane_t *plane)
 211 {
 212         int i, outpoints, prevside, side;
 213         float *prevpoint, prevdist, dist, dot;
 214
 215         // begin with the last point, then enter the loop with the first point as current
 216         prevpoint = (float *) ((qbyte *)in + stride * (inpoints - 1));
 217         prevdist = DotProduct(prevpoint, plane->normal) - plane->dist;
 218         prevside = prevdist >= 0 ? SIDE_FRONT : SIDE_BACK;
 219         i = 0;
 220         outpoints = 0;
 221         goto begin;
 222         for (;i < inpoints;i++)
 223         {
 224                 prevpoint = in;
 225                 prevdist = dist;
 226                 prevside = side;
 227                 (qbyte *)in += stride;
 228
 229 begin:
 230                 dist = DotProduct(in, plane->normal) - plane->dist;
 231                 side = dist >= 0 ? SIDE_FRONT : SIDE_BACK;
 232
 233                 if (prevside == SIDE_FRONT)
 234                 {
 235                         VectorCopy(prevpoint, out);
 236                         out += 3;
 237                         outpoints++;
 238                         if (side == SIDE_FRONT)
 239                                 continue;
 240                 }
 241                 else if (side == SIDE_BACK)
 242                         continue;
 243
 244                 // generate a split point
 245                 dot = prevdist / (prevdist - dist);
 246                 out[0] = prevpoint[0] + dot * (in[0] - prevpoint[0]);
 247                 out[1] = prevpoint[1] + dot * (in[1] - prevpoint[1]);
 248                 out[2] = prevpoint[2] + dot * (in[2] - prevpoint[2]);
 249                 out += 3;
 250                 outpoints++;
 251         }
 252
 253         return outpoints;
 254 }
 255
 256 float tempverts[256][3];
 257 float tempverts2[256][3];
 258 float screenverts[256][3];
 259
 260 // LordHavoc: this code is based primarily on the ddjzsort code
 261
 262 // Clips polygon to view frustum and nearclip, transforms polygon to viewspace, perspective projects polygon to screenspace,
 263 // and adds polygon's edges to the global edge table.
 264 void R_Clip_AddPolygon (vec_t *points, int numverts, int stride, int solid, void (*callback)(void *nativedata, void *nativedata2), void *nativedata, void *nativedata2, tinyplane_t *polyplane)
 265 {
 266         float deltax, deltay, vx, vy, vz, fx;
 267         int i, j, k, nextvert, temp, topy, bottomy, height, addededges;
 268         clipedge_t *pedge;
 269         tinyplane_t localplane;
 270         float distinv;
 271
 272         if (polyplane == NULL)
 273         {
 274                 polyplane = &localplane;
 275                 // calculate the plane for the polygon
 276                 if (!R_Clip_TriangleToPlane((float *) points, (float *) ((qbyte *)points + stride), (float *) ((qbyte *)points + 2 * stride), polyplane))
 277                 {
 278                         for (i = 0;i < numverts;i++)
 279                                 for (j = i + 1;j < numverts;j++)
 280                                         for (k = j + 1;k < numverts;k++)
 281                                                 if (R_Clip_TriangleToPlane((float *) ((qbyte *)points + i * stride), (float *) ((qbyte *)points + j * stride), (float *) ((qbyte *)points + k * stride), polyplane))
 282                                                         goto valid1;
 283                         return; // gave up
 284                         valid1:;
 285                 }
 286
 287                 // caller hasn't checked if this polygon faces the view, so we have to check
 288                 if (DotProduct(r_origin, polyplane->normal) < (polyplane->dist + 0.5f))
 289                         return;
 290         }
 291
 292         // for adaptive limits
 293         needededges += numverts;
 294         neededsurfs++;
 295
 296         if (pavailsurf >= clipsurfsend)
 297                 return;
 298
 299         // clip to view frustum and nearclip
 300         if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(points      , tempverts2[0], numverts, stride, &r_clip_viewplane[0]);
 301         if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts2[0], tempverts[0], numverts, sizeof(float) * 3, &r_clip_viewplane[1]);
 302         if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts[0], tempverts2[0], numverts, sizeof(float) * 3, &r_clip_viewplane[2]);
 303         if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts2[0], tempverts[0], numverts, sizeof(float) * 3, &r_clip_viewplane[3]);
 304         if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts[0], tempverts2[0], numverts, sizeof(float) * 3, &r_clip_viewplane[4]);
 305         if (numverts < 3)
 306                 return;
 307         if (numverts > 256)
 308                 Sys_Error("R_Clip_AddPolygon: polygon exceeded 256 vertex buffer\n");
 309
 310         // it survived the clipping, transform to viewspace and project to screenspace
 311
 312         if (pavailedge + numverts > clipedgesend)
 313                 return;
 314
 315         for (i = 0;i < numverts;i++)
 316         {
 317                 vx = tempverts2[i][0] - r_origin[0];
 318                 vy = tempverts2[i][1] - r_origin[1];
 319                 vz = tempverts2[i][2] - r_origin[2];
 320                 screenverts[i][2] = 1.0f / (r_clip_viewmatrix[2][0] * vx + r_clip_viewmatrix[2][1] * vy + r_clip_viewmatrix[2][2] * vz);
 321                 screenverts[i][0] = (r_clip_viewmatrix[0][0] * vx + r_clip_viewmatrix[0][1] * vy + r_clip_viewmatrix[0][2] * vz) * r_clip_viewmulx * screenverts[i][2] + r_clip_viewcenterx;
 322                 screenverts[i][1] = (r_clip_viewmatrix[1][0] * vx + r_clip_viewmatrix[1][1] * vy + r_clip_viewmatrix[1][2] * vz) * r_clip_viewmuly * screenverts[i][2] + r_clip_viewcentery;
 323         }
 324
 325         // calculate the plane for the polygon
 326         if (!R_Clip_TriangleToPlane(screenverts[0], screenverts[1], screenverts[2], &localplane))
 327         {
 328                 for (i = 0;i < numverts;i++)
 329                         for (j = i + 1;j < numverts;j++)
 330                                 for (k = j + 1;k < numverts;k++)
 331                                         if (R_Clip_TriangleToPlane(screenverts[i], screenverts[j], screenverts[k], &localplane))
 332                                                 goto valid;
 333                 return; // gave up
 334 valid:;
 335         }
 336
 337         // Set up the 1/z gradients from the polygon, calculating the
 338         // base value at screen coordinate 0,0 so we can use screen
 339         // coordinates directly when calculating 1/z from the gradients
 340         distinv = 1.0f / localplane.normal[2];
 341         pavailsurf->wstepx = -(localplane.normal[0] * distinv);
 342         pavailsurf->wstepy = -(localplane.normal[1] * distinv);
 343         pavailsurf->w00 = localplane.dist * distinv;
 344
 345         addededges = false;
 346
 347         // Add each edge in turn
 348         for (i = 0;i < numverts;i++)
 349         {
 350                 nextvert = i + 1;
 351                 if (nextvert >= numverts)
 352                         nextvert = 0;
 353
 354                 topy = (int)ceil(screenverts[i][1]);
 355                 bottomy = (int)ceil(screenverts[nextvert][1]);
 356                 height = bottomy - topy;
 357                 if (height == 0)
 358                         continue;       // doesn't cross any scan lines
 359                 if (height < 0)
 360                 {
 361                         // Leading edge
 362                         temp = topy;
 363                         topy = bottomy;
 364                         bottomy = temp;
 365                         if (topy < 0)
 366                                 topy = 0;
 367                         if (bottomy > clipheight)
 368                                 bottomy = clipheight;
 369                         if (topy >= bottomy)
 370                                 continue;
 371
 372                         pavailedge->leading = 1;
 373
 374                         deltax = screenverts[i][0] - screenverts[nextvert][0];
 375                         deltay = screenverts[i][1] - screenverts[nextvert][1];
 376
 377                         pavailedge->realxstep = deltax / deltay;
 378                         pavailedge->realx = screenverts[nextvert][0] + ((float)topy - screenverts[nextvert][1]) * pavailedge->realxstep;
 379                 }
 380                 else
 381                 {
 382                         // Trailing edge
 383                         if (topy < 0)
 384                                 topy = 0;
 385                         if (bottomy > clipheight)
 386                                 bottomy = clipheight;
 387                         if (topy >= bottomy)
 388                                 continue;
 389
 390                         pavailedge->leading = 0;
 391
 392                         deltax = screenverts[nextvert][0] - screenverts[i][0];
 393                         deltay = screenverts[nextvert][1] - screenverts[i][1];
 394
 395                         pavailedge->realxstep = deltax / deltay;
 396                         pavailedge->realx = screenverts[i][0] + ((float)topy - screenverts[i][1]) * pavailedge->realxstep;
 397                 }
 398
 399                 // Put the edge on the list to be added on top scan
 400                 fx = pavailedge->x = bound(0.0f, pavailedge->realx, clipwidth - 0.5f);
 401                 pedge = &newedges[topy];
 402                 while (fx > pedge->next->x)
 403                         pedge = pedge->next;
 404                 pavailedge->next = pedge->next;
 405                 pedge->next = pavailedge;
 406
 407                 // Put the edge on the list to be removed after final scan
 408                 pavailedge->nextremove = removeedges[bottomy - 1];
 409                 removeedges[bottomy - 1] = pavailedge;
 410
 411                 // Associate the edge with the surface
 412                 pavailedge->psurf = pavailsurf;
 413
 414                 pavailedge++;
 415
 416                 addededges = true;
 417         }
 418
 419         if (!addededges)
 420                 return;
 421
 422         // Create the surface, so we'll know how to sort and draw from the edges
 423         pavailsurf->next = NULL;
 424         pavailsurf->prev = NULL;
 425         pavailsurf->state = 0;
 426         pavailsurf->visible = false;
 427         pavailsurf->callback = callback;
 428         pavailsurf->nativedata = nativedata;
 429         pavailsurf->nativedata2 = nativedata2;
 430         pavailsurf->solid = solid;
 431         pavailsurf->removed = false;
 432         pavailsurf++;
 433 }
 434
 435 // Scan all the edges in the global edge table into spans.
 436 void ScanEdges (void)
 437 {
 438         int y, rescan;
 439         float fx, fy, w, w2, clipwidthf = clipwidth - 0.5f;
 440         clipedge_t *pedge, *pedge2, *ptemp;
 441         clipsurf_t *psurf, *psurf2;
 442 #if CLIPTEST
 443         int x, x2;
 444         float zi;
 445         clippixel_t *cb;
 446 #endif
 447         float cx;
 448
 449         // Set up the active edge list as initially empty, containing
 450         // only the sentinels (which are also the background fill). Most
 451         // of these fields could be set up just once at start-up
 452         edgehead.next = &edgetail;
 453         edgehead.prev = NULL;
 454         edgehead.x = edgehead.realx = -0.9999f; // left edge of screen
 455         edgehead.realxstep = 0;
 456         edgehead.leading = 1;
 457         edgehead.psurf = &surfstack;
 458
 459         edgetail.next = NULL; // mark end of list
 460         edgetail.prev = &edgehead;
 461         edgetail.x = edgetail.realx = clipwidth + 0.5f; // right edge of screen
 462         edgetail.realxstep = 0;
 463         edgetail.leading = 0;
 464         edgetail.psurf = &surfstack;
 465
 466         // The background surface is the entire stack initially, and
 467         // is infinitely far away, so everything sorts in front of it.
 468         // This could be set just once at start-up
 469         surfstack.solid = true;
 470         surfstack.visible = true; // no callback
 471         surfstack.next = surfstack.prev = &surfstack;
 472         surfstack.wcurrent = surfstack.w00 = -999999.0;
 473         surfstack.wstepx = surfstack.wstepy = 0.0;
 474         surfstack.removed = false;
 475
 476         // rescan causes the edges to be compared at the span level
 477         // it is false if the scanline will be identical to the previous
 478         rescan = true;
 479         for (y = 0;y < clipheight;y++)
 480         {
 481                 fy = y;
 482 #if CLIPTEST
 483                 cb = clipbuffer + y * clipwidth;
 484 #endif
 485
 486                 // Sort in any edges that start on this scan
 487                 if (newedges[y].next != &maxedge)
 488                 {
 489                         rescan = true;
 490                         pedge = newedges[y].next;
 491                         pedge2 = &edgehead;
 492                         while (pedge != &maxedge)
 493                         {
 494                                 if (pedge->psurf->removed)
 495                                 {
 496                                         pedge = pedge->next;
 497                                         continue;
 498                                 }
 499
 500                                 while (pedge->x > pedge2->next->x)
 501                                         pedge2 = pedge2->next;
 502
 503                                 ptemp = pedge->next;
 504                                 pedge->next = pedge2->next;
 505                                 pedge->prev = pedge2;
 506                                 pedge2->next->prev = pedge;
 507                                 pedge2->next = pedge;
 508
 509                                 pedge2 = pedge;
 510                                 pedge = ptemp;
 511                         }
 512                 }
 513
 514                 // Scan out the active edges into spans
 515
 516                 // Start out with the left background edge already inserted, and the surface stack containing only the background
 517                 surfstack.state = 1;
 518                 cx = 0;
 519
 520                 // must always rescan if rendering to wbuffer
 521 #ifndef CLIPTEST
 522 //              if (rescan)
 523 #endif
 524                 {
 525                         for (pedge = edgehead.next;pedge;pedge = pedge->next)
 526                         {
 527                                 edgeremoved:
 528                                 psurf = pedge->psurf;
 529                                 if (psurf->removed)
 530                                 {
 531                                         pedge2 = pedge->next;
 532                                         pedge->prev->next = pedge->next;
 533                                         pedge->next->prev = pedge->prev;
 534                                         pedge->next = pedge->prev = pedge;
 535                                         pedge = pedge2;
 536                                         if (pedge)
 537                                                 goto edgeremoved;
 538                                         else
 539                                                 break;
 540                                 }
 541
 542                                 if (pedge->leading)
 543                                 {
 544                                         // It's a leading edge. Figure out where it is
 545                                         // relative to the current surfaces and insert in
 546                                         // the surface stack; if it's on top, emit the span
 547                                         // for the current top.
 548                                         // First, make sure the edges don't cross
 549                                         if (++psurf->state == 1)
 550                                         {
 551                                                 fx = pedge->x;
 552                                                 // Calculate the surface's 1/z value at this pixel, and cache the y depth for quick compares later
 553                                                 w = (psurf->wcurrent = psurf->w00 + psurf->wstepy * fy) + psurf->wstepx * fx;
 554
 555                                                 // See if that makes it a new top surface
 556                                                 psurf2 = surfstack.next;
 557                                                 w2 = psurf2->wcurrent + psurf2->wstepx * fx;
 558
 559                                                 if (w >= w2)
 560                                                 {
 561                                                         // It's a new top surface
 562                                                         // emit the span for the current top
 563                                                         if (fx > cx && !psurf2->visible)
 564                                                         {
 565                                                                 psurf2->visible = true;
 566                                                                 psurf2->callback(psurf2->nativedata, psurf2->nativedata2);
 567                                                         }
 568
 569 #if CLIPTEST
 570                                                         for (x = ceil(cx), x2 = ceil(fx) >= clipwidth ? clipwidth : ceil(fx), zi = psurf2->wcurrent + psurf2->wstepx * x;x < x2;x++, zi += psurf2->wstepx)
 571                                                                 cb[x].w = zi;
 572 #endif
 573
 574                                                         cx = fx;
 575
 576                                                         // Add the edge to the stack
 577                                                         psurf->next = psurf2;
 578                                                         psurf2->prev = psurf;
 579                                                         surfstack.next = psurf;
 580                                                         psurf->prev = &surfstack;
 581                                                 }
 582                                                 else
 583                                                 {
 584                                                         // Not a new top; sort into the surface stack.
 585                                                         // Guaranteed to terminate due to sentinel background surface
 586                                                         do
 587                                                         {
 588                                                                 psurf2 = psurf2->next;
 589                                                                 w2 = psurf2->wcurrent + psurf2->wstepx * fx;
 590                                                         }
 591                                                         while (w < w2);
 592
 593                                                         // Insert the surface into the stack
 594                                                         psurf->next = psurf2;
 595                                                         psurf->prev = psurf2->prev;
 596                                                         psurf2->prev->next = psurf;
 597                                                         psurf2->prev = psurf;
 598                                                 }
 599                                         }
 600                                 }
 601                                 else
 602                                 {
 603                                         // It's a trailing edge; if this was the top surface,
 604                                         // emit the span and remove it.
 605                                         // First, make sure the edges didn't cross
 606                                         if (--psurf->state == 0)
 607                                         {
 608                                                 if (surfstack.next == psurf)
 609                                                 {
 610                                                         fx = pedge->x;
 611
 612                                                         // It's on top, emit the span
 613                                                         if (fx > cx && !psurf->visible)
 614                                                         {
 615                                                                 psurf->visible = true;
 616                                                                 psurf->callback(psurf->nativedata, psurf->nativedata2);
 617                                                         }
 618
 619 #if CLIPTEST
 620                                                         fx = pedge->x;
 621                                                         for (x = ceil(cx), x2 = ceil(fx) >= clipwidth ? clipwidth : ceil(fx), zi = psurf->w00 + psurf->wstepx * x + psurf->wstepy * fy;x < x2;x++, zi += psurf->wstepx)
 622                                                                 cb[x].w = zi;
 623 #endif
 624
 625                                                         cx = fx;
 626                                                 }
 627
 628                                                 // Remove the surface from the stack
 629                                                 psurf->next->prev = psurf->prev;
 630                                                 psurf->prev->next = psurf->next;
 631                                         }
 632                                 }
 633
 634                                 // mark and remove all non-solid surfaces that are ontop
 635                                 while (!surfstack.next->solid)
 636                                 {
 637                                         psurf = surfstack.next;
 638                                         if (!psurf->visible)
 639                                         {
 640                                                 psurf->visible = true;
 641                                                 psurf->callback(psurf->nativedata, psurf->nativedata2);
 642                                         }
 643                                         psurf->removed = true;
 644                                         psurf->next->prev = psurf->prev;
 645                                         psurf->prev->next = psurf->next;
 646                                         // isolate the surface
 647                                         psurf->next = psurf->prev = psurf;
 648                                 }
 649                         }
 650                         rescan = false;
 651                 }
 652
 653                 // Remove edges that are done
 654                 pedge = removeedges[y];
 655                 if (pedge)
 656                 {
 657                         while (pedge)
 658                         {
 659                                 if (!pedge->psurf->removed)
 660                                 {
 661                                         pedge->prev->next = pedge->next;
 662                                         pedge->next->prev = pedge->prev;
 663                                         if (pedge->psurf->visible)
 664                                                 rescan = true;
 665                                 }
 666                                 pedge = pedge->nextremove;
 667                         }
 668                 }
 669
 670                 // Step the remaining edges one scan line, and re-sort
 671                 for (pedge = edgehead.next;pedge != &edgetail;)
 672                 {
 673                         ptemp = pedge->next;
 674                         if (pedge->psurf->removed)
 675                         {
 676                                 pedge->next->prev = pedge->prev;
 677                                 pedge->prev->next = pedge->next;
 678                                 pedge->next = pedge->prev = pedge;
 679                                 pedge = ptemp;
 680                                 continue;
 681                         }
 682
 683                         // Step the edge
 684                         if (pedge->realxstep)
 685                         {
 686                                 pedge->realx += pedge->realxstep;
 687                                 pedge->x = bound(0.0f, pedge->realx, clipwidthf);
 688                         }
 689                         fx = pedge->x;
 690
 691                         // Move the edge back to the proper sorted location, if necessary
 692                         while (fx < pedge->prev->x)
 693                         {
 694                                 if (!rescan && (pedge->psurf->solid || pedge->prev->psurf->solid))
 695                                         rescan = true;
 696                                 pedge2 = pedge->prev;
 697                                 pedge2->next = pedge->next;
 698                                 pedge->next->prev = pedge2;
 699                                 pedge2->prev->next = pedge;
 700                                 pedge->prev = pedge2->prev;
 701                                 pedge->next = pedge2;
 702                                 pedge2->prev = pedge;
 703                         }
 704
 705                         pedge = ptemp;
 706                 }
 707         }
 708 }
 709
 710 void R_Clip_DisplayBuffer(void)
 711 {
 712 }
 713
 714 float boxpoints[4*3];
 715
 716 #define R_Clip_MinsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4, callback, nativedata, nativedata2, plane) \
 717 {\
 718         if (r_origin[(axis)] < ((axisvalue) - 0.5f))\
 719         {\
 720                 (plane)->dist = -axisvalue;\
 721                 boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
 722                 boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
 723                 boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
 724                 boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
 725                 R_Clip_AddPolygon (boxpoints, 4, sizeof(float[3]), false, callback, nativedata, nativedata2, plane);\
 726         }\
 727 }
 728
 729 #define R_Clip_MaxsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4, callback, nativedata, nativedata2, plane) \
 730 {\
 731         if (r_origin[(axis)] > ((axisvalue) + 0.5f))\
 732         {\
 733                 (plane)->dist = axisvalue;\
 734                 boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
 735                 boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
 736                 boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
 737                 boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
 738                 R_Clip_AddPolygon (boxpoints, 4, sizeof(float[3]), false, callback, nativedata, nativedata2, plane);\
 739         }\
 740 }
 741
 742 tinyplane_t clipboxplane[6] =
 743 {
 744         {{-1,  0,  0}, 0},
 745         {{ 1,  0,  0}, 0},
 746         {{ 0, -1,  0}, 0},
 747         {{ 0,  1,  0}, 0},
 748         {{ 0,  0, -1}, 0},
 749         {{ 0,  0,  1}, 0},
 750 };
 751
 752 void R_Clip_AddBox(float *a, float *b, void (*callback)(void *nativedata, void *nativedata2), void *nativedata, void *nativedata2)
 753 {
 754         if (r_origin[0] >= (a[0] - 5.0f) && r_origin[0] < (b[0] + 5.0f)
 755          && r_origin[1] >= (a[1] - 5.0f) && r_origin[1] < (b[1] + 5.0f)
 756          && r_origin[2] >= (a[2] - 5.0f) && r_origin[2] < (b[2] + 5.0f))
 757         {
 758                 callback(nativedata, nativedata2);
 759                 return;
 760         }
 761
 762         if (R_CullBox(a, b))
 763                 return;
 764
 765         R_Clip_MinsBoxPolygon
 766         (
 767                 0, a[0],
 768                 a[0], a[1], a[2],
 769                 a[0], b[1], a[2],
 770                 a[0], b[1], b[2],
 771                 a[0], a[1], b[2],
 772                 callback, nativedata, nativedata2, &clipboxplane[0]
 773         );
 774         R_Clip_MaxsBoxPolygon
 775         (
 776                 0, b[0],
 777                 b[0], b[1], a[2],
 778                 b[0], a[1], a[2],
 779                 b[0], a[1], b[2],
 780                 b[0], b[1], b[2],
 781                 callback, nativedata, nativedata2, &clipboxplane[1]
 782         );
 783         R_Clip_MinsBoxPolygon
 784         (
 785                 1, a[1],
 786                 b[0], a[1], a[2],
 787                 a[0], a[1], a[2],
 788                 a[0], a[1], b[2],
 789                 b[0], a[1], b[2],
 790                 callback, nativedata, nativedata2, &clipboxplane[2]
 791         );
 792         R_Clip_MaxsBoxPolygon
 793         (
 794                 1, b[1],
 795                 a[0], b[1], a[2],
 796                 b[0], b[1], a[2],
 797                 b[0], b[1], b[2],
 798                 a[0], b[1], b[2],
 799                 callback, nativedata, nativedata2, &clipboxplane[3]
 800         );
 801         R_Clip_MinsBoxPolygon
 802         (
 803                 2, a[2],
 804                 a[0], a[1], a[2],
 805                 b[0], a[1], a[2],
 806                 b[0], b[1], a[2],
 807                 a[0], b[1], a[2],
 808                 callback, nativedata, nativedata2, &clipboxplane[4]
 809         );
 810         R_Clip_MaxsBoxPolygon
 811         (
 812                 2, b[2],
 813                 b[0], a[1], b[2],
 814                 a[0], a[1], b[2],
 815                 a[0], b[1], b[2],
 816                 b[0], b[1], b[2],
 817                 callback, nativedata, nativedata2, &clipboxplane[5]
 818         );
 819 }
 820