rewrote memory system entirely (hunk, cache, and zone are gone, memory pools replaced...
[xonotic/darkplaces.git] / 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 *) ((byte *)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                 (byte *)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 *) ((byte *)points + stride), (float *) ((byte *)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 *) ((byte *)points + i * stride), (float *) ((byte *)points + j * stride), (float *) ((byte *)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 *) ((byte *)points + stride), (float *) ((byte *)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 *) ((byte *)points + i * stride), (float *) ((byte *)points + j * stride), (float *) ((byte *)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         byte 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 }