+
+#include "quakedef.h"
+
+typedef struct clipsurf_s
+{
+ struct clipsurf_s *next, *prev;
+ int state;
+ int visible;
+ int solid;
+ int removed;
+ void (*callback)(void *nativedata, void *nativedata2);
+ void *nativedata;
+ void *nativedata2;
+ float wstepx, wstepy, w00;
+ // wcurrent is a cached copy of w00 + wstepy * y,
+ // updated each time the surface is added to the stack,
+ // for quicker comparisons.
+ float wcurrent;
+ // this is a linked list of all edges belonging to this surface,
+ // used to remove them if this is a non-solid surface that is
+ // marked visible (it can not hide anything, so it is useless)
+// struct clipedge_s *edgechain;
+}
+clipsurf_t;
+
+typedef struct clipedge_s
+{
+ float x, realx, realxstep;
+ struct clipedge_s *next, *prev, *nextremove;
+ clipsurf_t *psurf;
+ int leading;
+ int pad;
+}
+clipedge_t;
+
+clipsurf_t *pavailsurf, *clipsurfs, *clipsurfsend;
+clipedge_t *pavailedge, *clipedges, *clipedgesend, *newedges, **removeedges;
+
+clipsurf_t surfstack;
+clipedge_t edgehead, edgetail;
+clipedge_t maxedge = {2000000000.0f};
+
+cvar_t r_clipwidth = {"r_clipwidth", "800"};
+cvar_t r_clipheight = {"r_clipheight", "600"};
+cvar_t r_clipedges = {"r_clipedges", "32768", true};
+cvar_t r_clipsurfaces = {"r_clipsurfaces", "8192", true};
+
+int clipwidth = 0, clipheight = 0;
+int maxclipsurfs = 0, maxclipedges = 0;
+int needededges, neededsurfs;
+
+#if CLIPTEST
+typedef struct
+{
+ float w; // inverse depth (1/z)
+}
+clippixel_t;
+
+clippixel_t *clipbuffer;
+#endif
+
+float r_clip_viewmatrix[3][3], r_clip_viewmulx, r_clip_viewmuly, r_clip_viewcenterx, r_clip_viewcentery;
+// REMOVELATER
+//float xscale, yscale, xscaleinv, yscaleinv;
+//float r_clip_nearclipdist, r_clip_nearclipdist2;
+tinyplane_t r_clip_viewplane[5];
+
+void R_Clip_MakeViewMatrix(void)
+{
+ float pixelaspect, screenaspect, horizontalfieldofview, verticalfieldofview;
+ pixelaspect = (float) clipheight / (float) clipwidth * 320 / 240.0;
+ horizontalfieldofview = 2.0 * tan (r_refdef.fov_x/360*M_PI);
+ screenaspect = clipwidth * pixelaspect / clipheight;
+ verticalfieldofview = horizontalfieldofview / screenaspect;
+ r_clip_viewcenterx = clipwidth * 0.5 - 0.5;
+ r_clip_viewcentery = clipheight * 0.5 - 0.5;
+ r_clip_viewmulx = clipwidth / horizontalfieldofview;
+ r_clip_viewmuly = r_clip_viewmulx * pixelaspect;
+ // this constructs a transposed rotation matrix for the view (transposed matrices do the opposite of their normal behavior)
+ VectorCopy (vright, r_clip_viewmatrix[0]);
+ VectorNegate (vup, r_clip_viewmatrix[1]);
+ VectorCopy (vpn, r_clip_viewmatrix[2]);
+// r_clip_nearclipdist = DotProduct(r_origin, vpn) + 4.0f;
+// r_clip_nearclipdist2 = r_clip_nearclipdist - 8.0f;
+ VectorCopy (vpn, r_clip_viewplane[0].normal);
+ r_clip_viewplane[0].dist = DotProduct(r_origin, vpn);
+ memcpy(&r_clip_viewplane[1], &frustum[0], sizeof(tinyplane_t));
+ memcpy(&r_clip_viewplane[2], &frustum[1], sizeof(tinyplane_t));
+ memcpy(&r_clip_viewplane[3], &frustum[2], sizeof(tinyplane_t));
+ memcpy(&r_clip_viewplane[4], &frustum[3], sizeof(tinyplane_t));
+// REMOVELATER
+// maxscreenscaleinv = (1.0f / max(clipwidth, clipheight)) * horizontalfieldofview * 0.5f;
+// xscale = clipwidth / horizontalfieldofview;
+// xscaleinv = 1.0 / xscale;
+// yscale = xscale * pixelaspect;
+// yscaleinv = 1.0 / yscale;
+}
+
+void R_Clip_StartFrame(void)
+{
+ int i;
+ int newwidth, newheight, newmaxedges, newmaxsurfs;
+ newwidth = bound(80, (int) r_clipwidth.value, vid.width * 2);
+ newheight = bound(60, (int) r_clipheight.value, vid.height * 2);
+ newmaxedges = bound(128, (int) r_clipedges.value, 262144);
+ newmaxsurfs = bound(32, (int) r_clipsurfaces.value, 65536);
+ if (newwidth != clipwidth || newheight != clipheight || maxclipedges != newmaxedges || maxclipsurfs != newmaxsurfs)
+ {
+#if CLIPTEST
+ if (clipbuffer)
+ qfree(clipbuffer);
+#endif
+ if (clipedges)
+ qfree(clipedges);
+ if (clipsurfs)
+ qfree(clipsurfs);
+ if (newedges)
+ qfree(newedges);
+ if (removeedges)
+ qfree(removeedges);
+ clipwidth = newwidth;
+ clipheight = newheight;
+ maxclipedges = newmaxedges;
+ maxclipsurfs = newmaxsurfs;
+#if CLIPTEST
+ clipbuffer = qmalloc(clipwidth * clipheight * sizeof(clippixel_t));
+#endif
+ clipedges = qmalloc(maxclipedges * sizeof(clipedge_t));
+ clipsurfs = qmalloc(maxclipsurfs * sizeof(clipsurf_t));
+ newedges = qmalloc(clipheight * sizeof(clipedge_t));
+ removeedges = qmalloc(clipheight * sizeof(clipedge_t *));
+ clipedgesend = clipedges + maxclipedges;
+ clipsurfsend = clipsurfs + maxclipsurfs;
+ }
+#if CLIPTEST
+ memset(clipbuffer, 0, clipwidth * clipheight * sizeof(clippixel_t));
+#endif
+ pavailedge = clipedges;
+ pavailsurf = clipsurfs;
+ // Clear the lists of edges to add and remove on each scan line.
+
+ needededges = 0;
+ neededsurfs = 0;
+ for (i = 0;i < clipheight;i++)
+ {
+ newedges[i].next = &maxedge;
+ removeedges[i] = NULL;
+ }
+
+ R_Clip_MakeViewMatrix();
+}
+
+void ScanEdges (void);
+
+void R_Clip_EndFrame(void)
+{
+ ScanEdges();
+ if (maxclipedges < needededges)
+ {
+ Con_Printf("R_Clip: ran out of edges, increasing limit from %d to %d\n", maxclipedges, needededges);
+ Cvar_SetValue("r_clipedges", needededges);
+ }
+ if (maxclipsurfs < neededsurfs)
+ {
+ Con_Printf("R_Clip: ran out of surfaces, increasing limit from %d to %d\n", maxclipsurfs, neededsurfs);
+ Cvar_SetValue("r_clipsurfaces", neededsurfs);
+ }
+}
+
+void r_clip_start(void)
+{
+}
+
+void r_clip_shutdown(void)
+{
+#if CLIPTEST
+ if (clipbuffer)
+ qfree(clipbuffer);
+ clipbuffer = NULL;
+#endif
+ if (clipsurfs)
+ qfree(clipsurfs);
+ clipsurfs = NULL;
+ if (clipedges)
+ qfree(clipedges);
+ clipedges = NULL;
+ if (newedges)
+ qfree(newedges);
+ newedges = NULL;
+ if (removeedges)
+ qfree(removeedges);
+ removeedges = NULL;
+ clipwidth = -1;
+ clipheight = -1;
+}
+
+void r_clip_newmap(void)
+{
+}
+
+void R_Clip_Init(void)
+{
+ Cvar_RegisterVariable(&r_clipwidth);
+ Cvar_RegisterVariable(&r_clipheight);
+ Cvar_RegisterVariable(&r_clipedges);
+ Cvar_RegisterVariable(&r_clipsurfaces);
+ R_RegisterModule("R_Clip", r_clip_start, r_clip_shutdown, r_clip_newmap);
+}
+
+int R_Clip_TriangleToPlane(vec3_t point1, vec3_t point2, vec3_t point3, tinyplane_t *p)
+{
+ float y, number;
+ vec3_t v1, v2;
+ VectorSubtract(point1, point2, v1);
+ VectorSubtract(point3, point2, v2);
+ CrossProduct(v1, v2, p->normal);
+ number = DotProduct(p->normal, p->normal);
+ if (number >= 0.1f)
+ {
+ *((long *)&y) = 0x5f3759df - ((* (long *) &number) >> 1);
+ y = y * (1.5f - (number * 0.5f * y * y));
+ VectorScale(p->normal, y, p->normal);
+ p->dist = DotProduct(point1, p->normal);
+ return true;
+ }
+ else
+ return false;
+}
+
+/*
+int R_Clip_TriangleToDoublePlane(double *point1, double *point2, double *point3, tinydoubleplane_t *p)
+{
+ double y, number;
+ double v1[3], v2[3];
+ VectorSubtract(point1, point2, v1);
+ VectorSubtract(point3, point2, v2);
+ CrossProduct(v1, v2, p->normal);
+ number = DotProduct(p->normal, p->normal);
+ if (number >= 0.1)
+ {
+ y = 1.0 / sqrt(number);
+ VectorScale(p->normal, y, p->normal);
+ p->dist = DotProduct(point1, p->normal);
+ return true;
+ }
+ else
+ return false;
+}
+*/
+
+int R_Clip_ClipPolygonToPlane(float *in, float *out, int inpoints, int stride, tinyplane_t *plane)
+{
+ int i, outpoints, prevside, side;
+ float *prevpoint, prevdist, dist, dot;
+
+ // begin with the last point, then enter the loop with the first point as current
+ prevpoint = (float *) ((byte *)in + stride * (inpoints - 1));
+ prevdist = DotProduct(prevpoint, plane->normal) - plane->dist;
+ prevside = prevdist >= 0 ? SIDE_FRONT : SIDE_BACK;
+ i = 0;
+ outpoints = 0;
+ goto begin;
+ for (;i < inpoints;i++)
+ {
+ prevpoint = in;
+ prevdist = dist;
+ prevside = side;
+ (byte *)in += stride;
+
+begin:
+ dist = DotProduct(in, plane->normal) - plane->dist;
+ side = dist >= 0 ? SIDE_FRONT : SIDE_BACK;
+
+ if (prevside == SIDE_FRONT)
+ {
+ VectorCopy(prevpoint, out);
+ out += 3;
+ outpoints++;
+ if (side == SIDE_FRONT)
+ continue;
+ }
+ else if (side == SIDE_BACK)
+ continue;
+
+ // generate a split point
+ dot = prevdist / (prevdist - dist);
+ out[0] = prevpoint[0] + dot * (in[0] - prevpoint[0]);
+ out[1] = prevpoint[1] + dot * (in[1] - prevpoint[1]);
+ out[2] = prevpoint[2] + dot * (in[2] - prevpoint[2]);
+ out += 3;
+ outpoints++;
+ }
+
+ return outpoints;
+}
+
+float tempverts[256][3];
+float tempverts2[256][3];
+float screenverts[256][3];
+
+// LordHavoc: this code is based primarily on the ddjzsort code
+
+// Clips polygon to view frustum and nearclip, transforms polygon to viewspace, perspective projects polygon to screenspace,
+// and adds polygon's edges to the global edge table.
+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)
+{
+ float deltax, deltay, vx, vy, vz, fx;
+ int i, j, k, nextvert, temp, topy, bottomy, height, addededges;
+ clipedge_t *pedge;
+// tinydoubleplane_t plane;
+ tinyplane_t localplane;
+// tinyplane_t testplane;
+ float distinv;
+
+// if (!solid)
+// return;
+
+ if (polyplane == NULL)
+ {
+ polyplane = &localplane;
+ // calculate the plane for the polygon
+ if (!R_Clip_TriangleToPlane((float *) points, (float *) ((byte *)points + stride), (float *) ((byte *)points + 2 * stride), polyplane))
+ {
+ for (i = 0;i < numverts;i++)
+ for (j = i + 1;j < numverts;j++)
+ for (k = j + 1;k < numverts;k++)
+ if (R_Clip_TriangleToPlane((float *) ((byte *)points + i * stride), (float *) ((byte *)points + j * stride), (float *) ((byte *)points + k * stride), polyplane))
+ goto valid1;
+ return; // gave up
+ valid1:;
+ }
+
+ // caller hasn't checked if this polygon faces the view, so we have to check
+ if (DotProduct(r_origin, polyplane->normal) < (polyplane->dist + 0.5f))
+ return;
+ }
+#if 0 // debugging (validates planes passed in)
+ else
+ {
+ // calculate the plane for the polygon
+ if (!R_Clip_TriangleToPlane((float *) points, (float *) ((byte *)points + stride), (float *) ((byte *)points + 2 * stride), &localplane))
+ {
+ for (i = 0;i < numverts;i++)
+ for (j = i + 1;j < numverts;j++)
+ for (k = j + 1;k < numverts;k++)
+ if (R_Clip_TriangleToPlane((float *) ((byte *)points + i * stride), (float *) ((byte *)points + j * stride), (float *) ((byte *)points + k * stride), &localplane))
+ goto valid4;
+ return; // gave up
+ valid4:;
+ }
+
+// if ((DotProduct(r_origin, polyplane->normal) < (polyplane->dist + 0.5f)) != (DotProduct(r_origin, localplane.normal) < (localplane.dist + 0.5f)))
+ if (DotProduct(polyplane->normal, localplane.normal) < 0.9f)
+ {
+ Con_Printf("*\n");
+ return;
+ }
+ }
+#endif
+
+ // for adaptive limits
+ needededges += numverts;
+ neededsurfs++;
+
+ if (pavailsurf >= clipsurfsend)
+ return;
+
+ // clip to view frustum and nearclip
+ if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(points , tempverts2[0], numverts, stride, &r_clip_viewplane[0]);
+ if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts2[0], tempverts[0], numverts, sizeof(float) * 3, &r_clip_viewplane[1]);
+ if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts[0], tempverts2[0], numverts, sizeof(float) * 3, &r_clip_viewplane[2]);
+ if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts2[0], tempverts[0], numverts, sizeof(float) * 3, &r_clip_viewplane[3]);
+ if (numverts < 3) return;numverts = R_Clip_ClipPolygonToPlane(tempverts[0], tempverts2[0], numverts, sizeof(float) * 3, &r_clip_viewplane[4]);
+ if (numverts < 3)
+ return;
+ if (numverts > 256)
+ Sys_Error("R_Clip_AddPolygon: polygon exceeded 256 vertex buffer\n");
+
+ // it survived the clipping, transform to viewspace and project to screenspace
+
+ if (pavailedge + numverts > clipedgesend)
+ return;
+
+#if 1
+ for (i = 0;i < numverts;i++)
+ {
+ vx = tempverts2[i][0] - r_origin[0];
+ vy = tempverts2[i][1] - r_origin[1];
+ vz = tempverts2[i][2] - r_origin[2];
+ screenverts[i][2] = 1.0f / (r_clip_viewmatrix[2][0] * vx + r_clip_viewmatrix[2][1] * vy + r_clip_viewmatrix[2][2] * vz);
+ 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;
+ 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;
+ }
+
+ /*
+ if (polyplane != NULL)
+ {
+ */
+ /*
+ distinv = 1.0f / (polyplane->dist - DotProduct(r_origin, polyplane->normal));
+ pavailsurf->wstepx = DotProduct(r_clip_viewmatrix[0], polyplane->normal) * xscaleinv * distinv;
+ pavailsurf->wstepy = DotProduct(r_clip_viewmatrix[1], polyplane->normal) * yscaleinv * distinv;
+ pavailsurf->w00 = DotProduct(r_clip_viewmatrix[2], polyplane->normal) * distinv - r_clip_viewcenterx * pavailsurf->wstepx - r_clip_viewcentery * pavailsurf->wstepy;
+ */
+ /*
+ }
+ else
+ {
+ */
+ // calculate the plane for the polygon
+ if (!R_Clip_TriangleToPlane(screenverts[0], screenverts[1], screenverts[2], &localplane))
+ {
+ for (i = 0;i < numverts;i++)
+ for (j = i + 1;j < numverts;j++)
+ for (k = j + 1;k < numverts;k++)
+ if (R_Clip_TriangleToPlane(screenverts[i], screenverts[j], screenverts[k], &localplane))
+ goto valid;
+ return; // gave up
+ valid:;
+ }
+
+ // Set up the 1/z gradients from the polygon, calculating the
+ // base value at screen coordinate 0,0 so we can use screen
+ // coordinates directly when calculating 1/z from the gradients
+ distinv = 1.0f / localplane.normal[2];
+ pavailsurf->wstepx = -(localplane.normal[0] * distinv);
+ pavailsurf->wstepy = -(localplane.normal[1] * distinv);
+ pavailsurf->w00 = localplane.dist * distinv;
+ /*
+ }
+ */
+ // REMOVELATER
+ /*
+ prevdist = z1 * plane.normal[2] - plane.dist;
+ dist = z2 * plane.normal[2] - plane.dist;
+ d = prevdist / (prevdist - dist);
+ zc = z1 + d * (z2 - z1);
+
+ prevdist = plane.normal[0] + z1 * plane.normal[2] - plane.dist;
+ dist = plane.normal[0] + z2 * plane.normal[2] - plane.dist;
+ d = prevdist / (prevdist - dist);
+ zx = (z1 + d * (z2 - z1)) - zc;
+
+ prevdist = plane.normal[1] + z1 * plane.normal[2] - plane.dist;
+ dist = plane.normal[1] + z2 * plane.normal[2] - plane.dist;
+ d = prevdist / (prevdist - dist);
+ zy = (z1 + d * (z2 - z1)) - zc;
+ */
+
+ /*
+ zc = (-plane.dist) / ((-plane.dist) - (plane.normal[2] - plane.dist));
+ zx = ((plane.normal[0] - plane.dist) / ((plane.normal[0] - plane.dist) - (plane.normal[0] + plane.normal[2] - plane.dist))) - zc;
+ zy = ((plane.normal[1] - plane.dist) / ((plane.normal[1] - plane.dist) - (plane.normal[1] + plane.normal[2] - plane.dist))) - zc;
+ */
+
+// zc = (plane.dist / plane.normal[2]);
+// zx = -(plane.normal[0] / plane.normal[2]);
+// zy = -(plane.normal[1] / plane.normal[2]);
+// zy = ((plane.normal[1] - plane.dist) / (-plane.normal[2])) + ((plane.dist) / (-plane.normal[2]));
+#else // REMOVELATER
+ for (i = 0;i < numverts;i++)
+ {
+ vx = tempverts2[i][0] - r_origin[0];
+ vy = tempverts2[i][1] - r_origin[1];
+ vz = tempverts2[i][2] - r_origin[2];
+ screenverts[i][0] = r_clip_viewmatrix[0][0] * vx + r_clip_viewmatrix[0][1] * vy + r_clip_viewmatrix[0][2] * vz;
+ screenverts[i][1] = r_clip_viewmatrix[1][0] * vx + r_clip_viewmatrix[1][1] * vy + r_clip_viewmatrix[1][2] * vz;
+ screenverts[i][2] = r_clip_viewmatrix[2][0] * vx + r_clip_viewmatrix[2][1] * vy + r_clip_viewmatrix[2][2] * vz;
+ }
+
+ // REMOVELATER
+ // calculate the plane for the polygon
+ for (i = 0;i < numverts;i++)
+ for (j = i + 1;j < numverts;j++)
+ for (k = j + 1;k < numverts;k++)
+ if (R_Clip_TriangleToDoublePlane(screenverts[i], screenverts[j], screenverts[k], &plane))
+ goto valid2;
+ return; // gave up
+valid2:;
+
+ distinv = 1.0f / plane.dist;
+ pavailsurf->d_zistepx = plane.normal[0] * xscaleinv * distinv;
+ pavailsurf->d_zistepy = -plane.normal[1] * yscaleinv * distinv;
+ pavailsurf->d_ziorigin = plane.normal[2] * distinv - r_clip_viewcenterx * pavailsurf->wstepx - r_clip_viewcentery * pavailsurf->wstepy;
+
+ for (i = 0;i < numverts;i++)
+ {
+ screenverts[i][2] = 1.0f / (screenverts[i][2]);
+ screenverts[i][0] = screenverts[i][0] * r_clip_viewmulx * screenverts[i][2] + r_clip_viewcenterx;
+ screenverts[i][1] = screenverts[i][1] * r_clip_viewmuly * screenverts[i][2] + r_clip_viewcentery;
+ // REMOVELATER
+// if (screenverts[i][0] < -0.5)
+// screenverts[i][0] = -0.5;
+// if (screenverts[i][0] > (clipwidth - 0.5))
+// screenverts[i][0] = clipwidth - 0.5;
+// if (screenverts[i][1] < -0.5)
+// screenverts[i][1] = -0.5;
+// if (screenverts[i][1] > (clipheight - 0.5))
+// screenverts[i][1] = clipheight - 0.5;
+// if (screenverts[i][2] <= 0.0)
+// Con_Printf("R_Clip_AddPolygon: vertex z <= 0!\n");
+ }
+#endif
+
+ addededges = false;
+
+ // Add each edge in turn
+ for (i = 0;i < numverts;i++)
+ {
+ nextvert = i + 1;
+ if (nextvert >= numverts)
+ nextvert = 0;
+
+ topy = (int)ceil(screenverts[i][1]);
+ bottomy = (int)ceil(screenverts[nextvert][1]);
+ height = bottomy - topy;
+ if (height == 0)
+ continue; // doesn't cross any scan lines
+ if (height < 0)
+ {
+ // Leading edge
+ temp = topy;
+ topy = bottomy;
+ bottomy = temp;
+ if (topy < 0)
+ topy = 0;
+ if (bottomy > clipheight)
+ bottomy = clipheight;
+ if (topy >= bottomy)
+ continue;
+
+ pavailedge->leading = 1;
+
+ deltax = screenverts[i][0] - screenverts[nextvert][0];
+ deltay = screenverts[i][1] - screenverts[nextvert][1];
+
+ pavailedge->realxstep = deltax / deltay;
+ pavailedge->realx = screenverts[nextvert][0] + ((float)topy - screenverts[nextvert][1]) * pavailedge->realxstep;
+ }
+ else
+ {
+ // Trailing edge
+ if (topy < 0)
+ topy = 0;
+ if (bottomy > clipheight)
+ bottomy = clipheight;
+ if (topy >= bottomy)
+ continue;
+
+ pavailedge->leading = 0;
+
+ deltax = screenverts[nextvert][0] - screenverts[i][0];
+ deltay = screenverts[nextvert][1] - screenverts[i][1];
+
+ pavailedge->realxstep = deltax / deltay;
+ pavailedge->realx = screenverts[i][0] + ((float)topy - screenverts[i][1]) * pavailedge->realxstep;
+ }
+
+ // Put the edge on the list to be added on top scan
+ fx = pavailedge->x = bound(0.0f, pavailedge->realx, clipwidth - 0.5f);
+ pedge = &newedges[topy];
+ while (fx > pedge->next->x)
+ pedge = pedge->next;
+ pavailedge->next = pedge->next;
+ pedge->next = pavailedge;
+
+ // Put the edge on the list to be removed after final scan
+ pavailedge->nextremove = removeedges[bottomy - 1];
+ removeedges[bottomy - 1] = pavailedge;
+
+ // Associate the edge with the surface
+ pavailedge->psurf = pavailsurf;
+
+ pavailedge++;
+
+ addededges = true;
+ }
+
+ if (!addededges)
+ return;
+
+ // Create the surface, so we'll know how to sort and draw from the edges
+ pavailsurf->next = NULL;
+ pavailsurf->prev = NULL;
+ pavailsurf->state = 0;
+ pavailsurf->visible = false;
+ pavailsurf->callback = callback;
+ pavailsurf->nativedata = nativedata;
+ pavailsurf->nativedata2 = nativedata2;
+ pavailsurf->solid = solid;
+ pavailsurf->removed = false;
+ pavailsurf++;
+}
+
+/////////////////////////////////////////////////////////////////////
+// Scan all the edges in the global edge table into spans.
+/////////////////////////////////////////////////////////////////////
+void ScanEdges (void)
+{
+ int y, rescan;
+ float fx, fy, w, w2, clipwidthf = clipwidth - 0.5f;
+ clipedge_t *pedge, *pedge2, *ptemp;
+ clipsurf_t *psurf, *psurf2;
+#if CLIPTEST
+ int x, x2;
+ float zi;
+ clippixel_t *cb;
+#endif
+ float cx;
+
+ // Set up the active edge list as initially empty, containing
+ // only the sentinels (which are also the background fill). Most
+ // of these fields could be set up just once at start-up
+ edgehead.next = &edgetail;
+ edgehead.prev = NULL;
+ edgehead.x = edgehead.realx = -0.9999f; // left edge of screen
+ edgehead.realxstep = 0;
+ edgehead.leading = 1;
+ edgehead.psurf = &surfstack;
+
+ edgetail.next = NULL; // mark end of list
+ edgetail.prev = &edgehead;
+ edgetail.x = edgetail.realx = clipwidth + 0.5f; // right edge of screen
+ edgetail.realxstep = 0;
+ edgetail.leading = 0;
+ edgetail.psurf = &surfstack;
+
+ // The background surface is the entire stack initially, and
+ // is infinitely far away, so everything sorts in front of it.
+ // This could be set just once at start-up
+ surfstack.solid = true;
+ surfstack.visible = true; // no callback
+ surfstack.next = surfstack.prev = &surfstack;
+ surfstack.wcurrent = surfstack.w00 = -999999.0;
+ surfstack.wstepx = surfstack.wstepy = 0.0;
+ surfstack.removed = false;
+
+ // rescan causes the edges to be compared at the span level
+ // it is false if the scanline will be identical to the previous
+ rescan = true;
+ for (y = 0;y < clipheight;y++)
+ {
+ fy = y;
+#if CLIPTEST
+ cb = clipbuffer + y * clipwidth;
+#endif
+
+ // Sort in any edges that start on this scan
+ if (newedges[y].next != &maxedge)
+ {
+ rescan = true;
+ pedge = newedges[y].next;
+ pedge2 = &edgehead;
+ while (pedge != &maxedge)
+ {
+ if (pedge->psurf->removed)
+ {
+ pedge = pedge->next;
+ continue;
+ }
+
+ while (pedge->x > pedge2->next->x)
+ pedge2 = pedge2->next;
+
+ ptemp = pedge->next;
+ pedge->next = pedge2->next;
+ pedge->prev = pedge2;
+ pedge2->next->prev = pedge;
+ pedge2->next = pedge;
+
+ pedge2 = pedge;
+ pedge = ptemp;
+ }
+ }
+
+ // Scan out the active edges into spans
+
+ // Start out with the left background edge already inserted, and the surface stack containing only the background
+ surfstack.state = 1;
+ cx = 0;
+
+ // must always rescan if rendering to wbuffer
+#ifndef CLIPTEST
+// if (rescan)
+#endif
+ {
+ for (pedge = edgehead.next;pedge;pedge = pedge->next)
+ {
+ edgeremoved:
+ psurf = pedge->psurf;
+ if (psurf->removed)
+ {
+ pedge2 = pedge->next;
+ pedge->prev->next = pedge->next;
+ pedge->next->prev = pedge->prev;
+ pedge->next = pedge->prev = pedge;
+ pedge = pedge2;
+ if (pedge)
+ goto edgeremoved;
+ else
+ break;
+ }
+
+ if (pedge->leading)
+ {
+ // It's a leading edge. Figure out where it is
+ // relative to the current surfaces and insert in
+ // the surface stack; if it's on top, emit the span
+ // for the current top.
+ // First, make sure the edges don't cross
+ if (++psurf->state == 1)
+ {
+ fx = pedge->x;
+ // Calculate the surface's 1/z value at this pixel, and cache the y depth for quick compares later
+ w = (psurf->wcurrent = psurf->w00 + psurf->wstepy * fy) + psurf->wstepx * fx;
+// if (w < 0)
+// w = 0;
+
+ // See if that makes it a new top surface
+ psurf2 = surfstack.next;
+ w2 = psurf2->wcurrent + psurf2->wstepx * fx;
+// if (w2 < 0 && psurf2 != &surfstack)
+// w2 = 0;
+
+ if (w >= w2)
+ {
+ // It's a new top surface
+ // emit the span for the current top
+ if (fx > cx && !psurf2->visible)
+ {
+ psurf2->visible = true;
+ psurf2->callback(psurf2->nativedata, psurf2->nativedata2);
+ }
+
+#if CLIPTEST
+ for (x = ceil(cx), x2 = ceil(fx) >= clipwidth ? clipwidth : ceil(fx), zi = psurf2->wcurrent + psurf2->wstepx * x;x < x2;x++, zi += psurf2->wstepx)
+ cb[x].w = zi;
+#endif
+
+ cx = fx;
+
+ // Add the edge to the stack
+ psurf->next = psurf2;
+ psurf2->prev = psurf;
+ surfstack.next = psurf;
+ psurf->prev = &surfstack;
+ }
+ else
+ {
+ // Not a new top; sort into the surface stack.
+ // Guaranteed to terminate due to sentinel background surface
+ do
+ {
+ psurf2 = psurf2->next;
+ w2 = psurf2->wcurrent + psurf2->wstepx * fx;
+// if (w2 < 0 && psurf2 != &surfstack)
+// w2 = 0;
+ }
+ while (w < w2);
+
+ // Insert the surface into the stack
+ psurf->next = psurf2;
+ psurf->prev = psurf2->prev;
+ psurf2->prev->next = psurf;
+ psurf2->prev = psurf;
+ }
+ }
+ }
+ else
+ {
+ // It's a trailing edge; if this was the top surface,
+ // emit the span and remove it.
+ // First, make sure the edges didn't cross
+ if (--psurf->state == 0)
+ {
+ if (surfstack.next == psurf)
+ {
+ fx = pedge->x;
+
+ // It's on top, emit the span
+ if (fx > cx && !psurf->visible)
+ {
+ psurf->visible = true;
+ psurf->callback(psurf->nativedata, psurf->nativedata2);
+ }
+
+#if CLIPTEST
+ fx = pedge->x;
+ 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)
+ cb[x].w = zi;
+#endif
+
+ cx = fx;
+ }
+
+ // Remove the surface from the stack
+ psurf->next->prev = psurf->prev;
+ psurf->prev->next = psurf->next;
+ }
+ }
+
+ // mark and remove all non-solid surfaces that are ontop
+ while (!surfstack.next->solid)
+ {
+ psurf = surfstack.next;
+ if (!psurf->visible)
+ {
+ psurf->visible = true;
+ psurf->callback(psurf->nativedata, psurf->nativedata2);
+ }
+ psurf->removed = true;
+ psurf->next->prev = psurf->prev;
+ psurf->prev->next = psurf->next;
+ // isolate the surface
+ psurf->next = psurf->prev = psurf;
+ }
+ }
+ rescan = false;
+ }
+
+ // Remove edges that are done
+ pedge = removeedges[y];
+ if (pedge)
+ {
+ while (pedge)
+ {
+ if (!pedge->psurf->removed)
+ {
+ pedge->prev->next = pedge->next;
+ pedge->next->prev = pedge->prev;
+ if (pedge->psurf->visible)
+ rescan = true;
+ }
+ pedge = pedge->nextremove;
+ }
+ }
+
+ // Step the remaining edges one scan line, and re-sort
+ for (pedge = edgehead.next;pedge != &edgetail;)
+ {
+ ptemp = pedge->next;
+ if (pedge->psurf->removed)
+ {
+ pedge->next->prev = pedge->prev;
+ pedge->prev->next = pedge->next;
+ pedge->next = pedge->prev = pedge;
+ pedge = ptemp;
+ continue;
+ }
+
+ // Step the edge
+ if (pedge->realxstep)
+ {
+ pedge->realx += pedge->realxstep;
+ pedge->x = bound(0.0f, pedge->realx, clipwidthf);
+ }
+ fx = pedge->x;
+
+ // Move the edge back to the proper sorted location, if necessary
+ while (fx < pedge->prev->x)
+ {
+ if (!rescan && (pedge->psurf->solid || pedge->prev->psurf->solid))
+ rescan = true;
+ pedge2 = pedge->prev;
+ pedge2->next = pedge->next;
+ pedge->next->prev = pedge2;
+ pedge2->prev->next = pedge;
+ pedge->prev = pedge2->prev;
+ pedge->next = pedge2;
+ pedge2->prev = pedge;
+ }
+
+ pedge = ptemp;
+ }
+ }
+}
+
+void R_Clip_DisplayBuffer(void)
+{
+#if CLIPTEST
+ int i;
+ static int firstupload = true;
+ byte clipbuffertex[256*256], *b;
+ if (!r_render.value)
+ return;
+ if (clipwidth > 256 || clipheight > 256)
+ return;
+ glBlendFunc(GL_ONE, GL_ONE);
+ glBindTexture(GL_TEXTURE_2D, 8000);
+ if (firstupload)
+ {
+ memset(clipbuffertex, 0, sizeof(clipbuffertex));
+ glTexImage2D(GL_TEXTURE_2D, 0, 1, 256, 256, 0, GL_LUMINANCE, GL_UNSIGNED_BYTE, clipbuffertex);
+ }
+ glTexEnvf(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE);
+ glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
+ glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
+ if (lighthalf)
+ glColor3f(0.5, 0.5, 0.5);
+ else
+ glColor3f(1, 1, 1);
+ firstupload = false;
+ b = clipbuffertex;
+ for (i = 0;i < clipwidth*clipheight;i++)
+ {
+ if (clipbuffer[i].w > 0)
+ *b++ = bound(0, (int) (clipbuffer[i].w * 4096.0f), 255);
+ else
+ *b++ = 0;
+ }
+ glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, clipwidth, clipheight, GL_LUMINANCE, GL_UNSIGNED_BYTE, clipbuffertex);
+ glBegin (GL_QUADS);
+ glTexCoord2f (0 , 0 );glVertex2f (0 , 0 );
+ glTexCoord2f (clipwidth / 256.0f, 0 );glVertex2f (vid.width, 0 );
+ glTexCoord2f (clipwidth / 256.0f, clipheight / 256.0f);glVertex2f (vid.width, vid.height);
+ glTexCoord2f (0 , clipheight / 256.0f);glVertex2f (0 , vid.height);
+ glEnd ();
+ glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
+// glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
+// glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
+#endif
+}
+
+float boxpoints[4*3];
+
+#define R_Clip_MinsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4, callback, nativedata, nativedata2, plane) \
+{\
+ if (r_origin[(axis)] < ((axisvalue) - 0.5f))\
+ {\
+ (plane)->dist = -axisvalue;\
+ boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
+ boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
+ boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
+ boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
+ R_Clip_AddPolygon (boxpoints, 4, sizeof(float[3]), false, callback, nativedata, nativedata2, plane);\
+ }\
+}
+
+#define R_Clip_MaxsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4, callback, nativedata, nativedata2, plane) \
+{\
+ if (r_origin[(axis)] > ((axisvalue) + 0.5f))\
+ {\
+ (plane)->dist = axisvalue;\
+ boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
+ boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
+ boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
+ boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
+ R_Clip_AddPolygon (boxpoints, 4, sizeof(float[3]), false, callback, nativedata, nativedata2, plane);\
+ }\
+}
+
+tinyplane_t clipboxplane[6] =
+{
+ {{-1, 0, 0}, 0},
+ {{ 1, 0, 0}, 0},
+ {{ 0, -1, 0}, 0},
+ {{ 0, 1, 0}, 0},
+ {{ 0, 0, -1}, 0},
+ {{ 0, 0, 1}, 0},
+};
+
+void R_Clip_AddBox(float *a, float *b, void (*callback)(void *nativedata, void *nativedata2), void *nativedata, void *nativedata2)
+{
+ if (r_origin[0] >= (a[0] - 5.0f) && r_origin[0] < (b[0] + 5.0f)
+ && r_origin[1] >= (a[1] - 5.0f) && r_origin[1] < (b[1] + 5.0f)
+ && r_origin[2] >= (a[2] - 5.0f) && r_origin[2] < (b[2] + 5.0f))
+ {
+ callback(nativedata, nativedata2);
+ return;
+ }
+
+ if (R_CullBox(a, b))
+ return;
+
+ R_Clip_MinsBoxPolygon
+ (
+ 0, a[0],
+ a[0], a[1], a[2],
+ a[0], b[1], a[2],
+ a[0], b[1], b[2],
+ a[0], a[1], b[2],
+ callback, nativedata, nativedata2, &clipboxplane[0]
+ );
+ R_Clip_MaxsBoxPolygon
+ (
+ 0, b[0],
+ b[0], b[1], a[2],
+ b[0], a[1], a[2],
+ b[0], a[1], b[2],
+ b[0], b[1], b[2],
+ callback, nativedata, nativedata2, &clipboxplane[1]
+ );
+ R_Clip_MinsBoxPolygon
+ (
+ 1, a[1],
+ b[0], a[1], a[2],
+ a[0], a[1], a[2],
+ a[0], a[1], b[2],
+ b[0], a[1], b[2],
+ callback, nativedata, nativedata2, &clipboxplane[2]
+ );
+ R_Clip_MaxsBoxPolygon
+ (
+ 1, b[1],
+ a[0], b[1], a[2],
+ b[0], b[1], a[2],
+ b[0], b[1], b[2],
+ a[0], b[1], b[2],
+ callback, nativedata, nativedata2, &clipboxplane[3]
+ );
+ R_Clip_MinsBoxPolygon
+ (
+ 2, a[2],
+ a[0], a[1], a[2],
+ b[0], a[1], a[2],
+ b[0], b[1], a[2],
+ a[0], b[1], a[2],
+ callback, nativedata, nativedata2, &clipboxplane[4]
+ );
+ R_Clip_MaxsBoxPolygon
+ (
+ 2, b[2],
+ b[0], a[1], b[2],
+ a[0], a[1], b[2],
+ a[0], b[1], b[2],
+ b[0], b[1], b[2],
+ callback, nativedata, nativedata2, &clipboxplane[5]
+ );
+}