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