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