moved RecursiveLightPoint code to model_brush.c (model->brush.LightPoint), removing...
[divverent/darkplaces.git] / model_brush.c
1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19 */
20
21 #include "quakedef.h"
22 #include "image.h"
23 #include "r_shadow.h"
24
25 // note: model_shared.c sets up r_notexture, and r_surf_notexture
26
27 qbyte mod_q1bsp_novis[(MAX_MAP_LEAFS + 7)/ 8];
28
29 //cvar_t r_subdivide_size = {CVAR_SAVE, "r_subdivide_size", "128"};
30 cvar_t halflifebsp = {0, "halflifebsp", "0"};
31 cvar_t r_novis = {0, "r_novis", "0"};
32 cvar_t r_miplightmaps = {CVAR_SAVE, "r_miplightmaps", "0"};
33 cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1"};
34 cvar_t r_nosurftextures = {0, "r_nosurftextures", "0"};
35 cvar_t r_sortsurfaces = {0, "r_sortsurfaces", "0"};
36
37 void Mod_BrushInit(void)
38 {
39 //      Cvar_RegisterVariable(&r_subdivide_size);
40         Cvar_RegisterVariable(&halflifebsp);
41         Cvar_RegisterVariable(&r_novis);
42         Cvar_RegisterVariable(&r_miplightmaps);
43         Cvar_RegisterVariable(&r_lightmaprgba);
44         Cvar_RegisterVariable(&r_nosurftextures);
45         Cvar_RegisterVariable(&r_sortsurfaces);
46         memset(mod_q1bsp_novis, 0xff, sizeof(mod_q1bsp_novis));
47 }
48
49 static mleaf_t *Mod_Q1BSP_PointInLeaf(model_t *model, const vec3_t p)
50 {
51         mnode_t *node;
52
53         if (model == NULL)
54                 return NULL;
55
56         Mod_CheckLoaded(model);
57
58         // LordHavoc: modified to start at first clip node,
59         // in other words: first node of the (sub)model
60         node = model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode;
61         while (node->contents == 0)
62                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
63
64         return (mleaf_t *)node;
65 }
66
67 /*
68 static int Mod_Q1BSP_PointContents(model_t *model, const vec3_t p)
69 {
70         mnode_t *node;
71
72         if (model == NULL)
73                 return CONTENTS_EMPTY;
74
75         Mod_CheckLoaded(model);
76
77         // LordHavoc: modified to start at first clip node,
78         // in other words: first node of the (sub)model
79         node = model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode;
80         while (node->contents == 0)
81                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
82
83         return ((mleaf_t *)node)->contents;
84 }
85 */
86
87 typedef struct findnonsolidlocationinfo_s
88 {
89         vec3_t center;
90         vec_t radius;
91         vec3_t nudge;
92         vec_t bestdist;
93         model_t *model;
94 }
95 findnonsolidlocationinfo_t;
96
97 #if 0
98 extern cvar_t samelevel;
99 #endif
100 static void Mod_Q1BSP_FindNonSolidLocation_r_Leaf(findnonsolidlocationinfo_t *info, mleaf_t *leaf)
101 {
102         int i, surfnum, k, *tri, *mark;
103         float dist, f, vert[3][3], edge[3][3], facenormal[3], edgenormal[3][3], point[3];
104 #if 0
105         float surfnormal[3];
106 #endif
107         msurface_t *surf;
108         surfmesh_t *mesh;
109         for (surfnum = 0, mark = leaf->firstmarksurface;surfnum < leaf->nummarksurfaces;surfnum++, mark++)
110         {
111                 surf = info->model->brushq1.surfaces + *mark;
112                 if (surf->flags & SURF_SOLIDCLIP)
113                 {
114 #if 0
115                         VectorCopy(surf->plane->normal, surfnormal);
116                         if (surf->flags & SURF_PLANEBACK)
117                                 VectorNegate(surfnormal, surfnormal);
118 #endif
119                         for (mesh = surf->mesh;mesh;mesh = mesh->chain)
120                         {
121                                 for (k = 0;k < mesh->numtriangles;k++)
122                                 {
123                                         tri = mesh->element3i + k * 3;
124                                         VectorCopy((mesh->vertex3f + tri[0] * 3), vert[0]);
125                                         VectorCopy((mesh->vertex3f + tri[1] * 3), vert[1]);
126                                         VectorCopy((mesh->vertex3f + tri[2] * 3), vert[2]);
127                                         VectorSubtract(vert[1], vert[0], edge[0]);
128                                         VectorSubtract(vert[2], vert[1], edge[1]);
129                                         CrossProduct(edge[1], edge[0], facenormal);
130                                         if (facenormal[0] || facenormal[1] || facenormal[2])
131                                         {
132                                                 VectorNormalize(facenormal);
133 #if 0
134                                                 if (VectorDistance(facenormal, surfnormal) > 0.01f)
135                                                         Con_Printf("a2! %f %f %f != %f %f %f\n", facenormal[0], facenormal[1], facenormal[2], surfnormal[0], surfnormal[1], surfnormal[2]);
136 #endif
137                                                 f = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
138                                                 if (f <= info->bestdist && f >= -info->bestdist)
139                                                 {
140                                                         VectorSubtract(vert[0], vert[2], edge[2]);
141                                                         VectorNormalize(edge[0]);
142                                                         VectorNormalize(edge[1]);
143                                                         VectorNormalize(edge[2]);
144                                                         CrossProduct(facenormal, edge[0], edgenormal[0]);
145                                                         CrossProduct(facenormal, edge[1], edgenormal[1]);
146                                                         CrossProduct(facenormal, edge[2], edgenormal[2]);
147 #if 0
148                                                         if (samelevel.integer & 1)
149                                                                 VectorNegate(edgenormal[0], edgenormal[0]);
150                                                         if (samelevel.integer & 2)
151                                                                 VectorNegate(edgenormal[1], edgenormal[1]);
152                                                         if (samelevel.integer & 4)
153                                                                 VectorNegate(edgenormal[2], edgenormal[2]);
154                                                         for (i = 0;i < 3;i++)
155                                                                 if (DotProduct(vert[0], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f
156                                                                  || DotProduct(vert[1], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f
157                                                                  || DotProduct(vert[2], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f)
158                                                                         Con_Printf("a! %i : %f %f %f (%f %f %f)\n", i, edgenormal[i][0], edgenormal[i][1], edgenormal[i][2], facenormal[0], facenormal[1], facenormal[2]);
159 #endif
160                                                         // face distance
161                                                         if (DotProduct(info->center, edgenormal[0]) < DotProduct(vert[0], edgenormal[0])
162                                                          && DotProduct(info->center, edgenormal[1]) < DotProduct(vert[1], edgenormal[1])
163                                                          && DotProduct(info->center, edgenormal[2]) < DotProduct(vert[2], edgenormal[2]))
164                                                         {
165                                                                 // we got lucky, the center is within the face
166                                                                 dist = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
167                                                                 if (dist < 0)
168                                                                 {
169                                                                         dist = -dist;
170                                                                         if (info->bestdist > dist)
171                                                                         {
172                                                                                 info->bestdist = dist;
173                                                                                 VectorScale(facenormal, (info->radius - -dist), info->nudge);
174                                                                         }
175                                                                 }
176                                                                 else
177                                                                 {
178                                                                         if (info->bestdist > dist)
179                                                                         {
180                                                                                 info->bestdist = dist;
181                                                                                 VectorScale(facenormal, (info->radius - dist), info->nudge);
182                                                                         }
183                                                                 }
184                                                         }
185                                                         else
186                                                         {
187                                                                 // check which edge or vertex the center is nearest
188                                                                 for (i = 0;i < 3;i++)
189                                                                 {
190                                                                         f = DotProduct(info->center, edge[i]);
191                                                                         if (f >= DotProduct(vert[0], edge[i])
192                                                                          && f <= DotProduct(vert[1], edge[i]))
193                                                                         {
194                                                                                 // on edge
195                                                                                 VectorMA(info->center, -f, edge[i], point);
196                                                                                 dist = sqrt(DotProduct(point, point));
197                                                                                 if (info->bestdist > dist)
198                                                                                 {
199                                                                                         info->bestdist = dist;
200                                                                                         VectorScale(point, (info->radius / dist), info->nudge);
201                                                                                 }
202                                                                                 // skip both vertex checks
203                                                                                 // (both are further away than this edge)
204                                                                                 i++;
205                                                                         }
206                                                                         else
207                                                                         {
208                                                                                 // not on edge, check first vertex of edge
209                                                                                 VectorSubtract(info->center, vert[i], point);
210                                                                                 dist = sqrt(DotProduct(point, point));
211                                                                                 if (info->bestdist > dist)
212                                                                                 {
213                                                                                         info->bestdist = dist;
214                                                                                         VectorScale(point, (info->radius / dist), info->nudge);
215                                                                                 }
216                                                                         }
217                                                                 }
218                                                         }
219                                                 }
220                                         }
221                                 }
222                         }
223                 }
224         }
225 }
226
227 static void Mod_Q1BSP_FindNonSolidLocation_r(findnonsolidlocationinfo_t *info, mnode_t *node)
228 {
229         if (node->contents)
230         {
231                 if (((mleaf_t *)node)->nummarksurfaces)
232                         Mod_Q1BSP_FindNonSolidLocation_r_Leaf(info, (mleaf_t *)node);
233         }
234         else
235         {
236                 float f = PlaneDiff(info->center, node->plane);
237                 if (f >= -info->bestdist)
238                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[0]);
239                 if (f <= info->bestdist)
240                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[1]);
241         }
242 }
243
244 static void Mod_Q1BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, float radius)
245 {
246         int i;
247         findnonsolidlocationinfo_t info;
248         if (model == NULL)
249         {
250                 VectorCopy(in, out);
251                 return;
252         }
253         VectorCopy(in, info.center);
254         info.radius = radius;
255         info.model = model;
256         i = 0;
257         do
258         {
259                 VectorClear(info.nudge);
260                 info.bestdist = radius;
261                 Mod_Q1BSP_FindNonSolidLocation_r(&info, model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode);
262                 VectorAdd(info.center, info.nudge, info.center);
263         }
264         while (info.bestdist < radius && ++i < 10);
265         VectorCopy(info.center, out);
266 }
267
268 typedef struct
269 {
270         // the hull we're tracing through
271         const hull_t *hull;
272
273         // the trace structure to fill in
274         trace_t *trace;
275
276         // start, end, and end - start (in model space)
277         double start[3];
278         double end[3];
279         double dist[3];
280 }
281 RecursiveHullCheckTraceInfo_t;
282
283 // 1/32 epsilon to keep floating point happy
284 #define DIST_EPSILON (0.03125)
285
286 #define HULLCHECKSTATE_EMPTY 0
287 #define HULLCHECKSTATE_SOLID 1
288 #define HULLCHECKSTATE_DONE 2
289
290 static int Mod_Q1BSP_RecursiveHullCheck(RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, double p1[3], double p2[3])
291 {
292         // status variables, these don't need to be saved on the stack when
293         // recursing...  but are because this should be thread-safe
294         // (note: tracing against a bbox is not thread-safe, yet)
295         int ret;
296         mplane_t *plane;
297         double t1, t2;
298
299         // variables that need to be stored on the stack when recursing
300         dclipnode_t *node;
301         int side;
302         double midf, mid[3];
303
304         // LordHavoc: a goto!  everyone flee in terror... :)
305 loc0:
306         // check for empty
307         if (num < 0)
308         {
309                 t->trace->endcontents = num;
310                 if (t->trace->thiscontents)
311                 {
312                         if (num == t->trace->thiscontents)
313                                 t->trace->allsolid = false;
314                         else
315                         {
316                                 // if the first leaf is solid, set startsolid
317                                 if (t->trace->allsolid)
318                                         t->trace->startsolid = true;
319                                 return HULLCHECKSTATE_SOLID;
320                         }
321                         return HULLCHECKSTATE_EMPTY;
322                 }
323                 else
324                 {
325                         if (num != CONTENTS_SOLID)
326                         {
327                                 t->trace->allsolid = false;
328                                 if (num == CONTENTS_EMPTY)
329                                         t->trace->inopen = true;
330                                 else
331                                         t->trace->inwater = true;
332                         }
333                         else
334                         {
335                                 // if the first leaf is solid, set startsolid
336                                 if (t->trace->allsolid)
337                                         t->trace->startsolid = true;
338                                 return HULLCHECKSTATE_SOLID;
339                         }
340                         return HULLCHECKSTATE_EMPTY;
341                 }
342         }
343
344         // find the point distances
345         node = t->hull->clipnodes + num;
346
347         plane = t->hull->planes + node->planenum;
348         if (plane->type < 3)
349         {
350                 t1 = p1[plane->type] - plane->dist;
351                 t2 = p2[plane->type] - plane->dist;
352         }
353         else
354         {
355                 t1 = DotProduct (plane->normal, p1) - plane->dist;
356                 t2 = DotProduct (plane->normal, p2) - plane->dist;
357         }
358
359         if (t1 < 0)
360         {
361                 if (t2 < 0)
362                 {
363                         num = node->children[1];
364                         goto loc0;
365                 }
366                 side = 1;
367         }
368         else
369         {
370                 if (t2 >= 0)
371                 {
372                         num = node->children[0];
373                         goto loc0;
374                 }
375                 side = 0;
376         }
377
378         // the line intersects, find intersection point
379         // LordHavoc: this uses the original trace for maximum accuracy
380         if (plane->type < 3)
381         {
382                 t1 = t->start[plane->type] - plane->dist;
383                 t2 = t->end[plane->type] - plane->dist;
384         }
385         else
386         {
387                 t1 = DotProduct (plane->normal, t->start) - plane->dist;
388                 t2 = DotProduct (plane->normal, t->end) - plane->dist;
389         }
390
391         midf = t1 / (t1 - t2);
392         midf = bound(p1f, midf, p2f);
393         VectorMA(t->start, midf, t->dist, mid);
394
395         // recurse both sides, front side first
396         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side], p1f, midf, p1, mid);
397         // if this side is not empty, return what it is (solid or done)
398         if (ret != HULLCHECKSTATE_EMPTY)
399                 return ret;
400
401         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side ^ 1], midf, p2f, mid, p2);
402         // if other side is not solid, return what it is (empty or done)
403         if (ret != HULLCHECKSTATE_SOLID)
404                 return ret;
405
406         // front is air and back is solid, this is the impact point...
407         if (side)
408         {
409                 t->trace->plane.dist = -plane->dist;
410                 VectorNegate (plane->normal, t->trace->plane.normal);
411         }
412         else
413         {
414                 t->trace->plane.dist = plane->dist;
415                 VectorCopy (plane->normal, t->trace->plane.normal);
416         }
417
418         // bias away from surface a bit
419         t1 = DotProduct(t->trace->plane.normal, t->start) - (t->trace->plane.dist + DIST_EPSILON);
420         t2 = DotProduct(t->trace->plane.normal, t->end) - (t->trace->plane.dist + DIST_EPSILON);
421
422         midf = t1 / (t1 - t2);
423         t->trace->fraction = bound(0.0f, midf, 1.0);
424
425         return HULLCHECKSTATE_DONE;
426 }
427
428 static void Mod_Q1BSP_TraceBox(struct model_s *model, trace_t *trace, const vec3_t boxstartmins, const vec3_t boxstartmaxs, const vec3_t boxendmins, const vec3_t boxendmaxs)
429 {
430         // this function currently only supports same size start and end
431         double boxsize[3];
432         RecursiveHullCheckTraceInfo_t rhc;
433
434         memset(&rhc, 0, sizeof(rhc));
435         memset(trace, 0, sizeof(trace_t));
436         rhc.trace = trace;
437         rhc.trace->fraction = 1;
438         rhc.trace->allsolid = true;
439         VectorSubtract(boxstartmaxs, boxstartmins, boxsize);
440         if (boxsize[0] < 3)
441                 rhc.hull = &model->brushq1.hulls[0]; // 0x0x0
442         else if (model->brushq1.ishlbsp)
443         {
444                 if (boxsize[0] <= 32)
445                 {
446                         if (boxsize[2] < 54) // pick the nearest of 36 or 72
447                                 rhc.hull = &model->brushq1.hulls[3]; // 32x32x36
448                         else
449                                 rhc.hull = &model->brushq1.hulls[1]; // 32x32x72
450                 }
451                 else
452                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x64
453         }
454         else
455         {
456                 if (boxsize[0] <= 32)
457                         rhc.hull = &model->brushq1.hulls[1]; // 32x32x56
458                 else
459                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x88
460         }
461         VectorSubtract(boxstartmins, rhc.hull->clip_mins, rhc.start);
462         VectorSubtract(boxendmins, rhc.hull->clip_mins, rhc.end);
463         VectorSubtract(rhc.end, rhc.start, rhc.dist);
464         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
465 }
466
467 static int Mod_Q1BSP_LightPoint_RecursiveBSPNode(vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal, const mnode_t *node, float x, float y, float startz, float endz)
468 {
469         int side, distz = endz - startz;
470         float front, back;
471         float mid;
472
473 loc0:
474         if (node->contents < 0)
475                 return false;           // didn't hit anything
476
477         switch (node->plane->type)
478         {
479         case PLANE_X:
480                 node = node->children[x < node->plane->dist];
481                 goto loc0;
482         case PLANE_Y:
483                 node = node->children[y < node->plane->dist];
484                 goto loc0;
485         case PLANE_Z:
486                 side = startz < node->plane->dist;
487                 if ((endz < node->plane->dist) == side)
488                 {
489                         node = node->children[side];
490                         goto loc0;
491                 }
492                 // found an intersection
493                 mid = node->plane->dist;
494                 break;
495         default:
496                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
497                 front += startz * node->plane->normal[2];
498                 back += endz * node->plane->normal[2];
499                 side = front < node->plane->dist;
500                 if ((back < node->plane->dist) == side)
501                 {
502                         node = node->children[side];
503                         goto loc0;
504                 }
505                 // found an intersection
506                 mid = startz + distz * (front - node->plane->dist) / (front - back);
507                 break;
508         }
509
510         // go down front side
511         if (node->children[side]->contents >= 0 && Mod_Q1BSP_LightPoint_RecursiveBSPNode(ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
512                 return true;    // hit something
513         else
514         {
515                 // check for impact on this node
516                 if (node->numsurfaces)
517                 {
518                         int i, ds, dt;
519                         msurface_t *surf;
520
521                         surf = cl.worldmodel->brushq1.surfaces + node->firstsurface;
522                         for (i = 0;i < node->numsurfaces;i++, surf++)
523                         {
524                                 if (!(surf->flags & SURF_LIGHTMAP))
525                                         continue;       // no lightmaps
526
527                                 ds = (int) (x * surf->texinfo->vecs[0][0] + y * surf->texinfo->vecs[0][1] + mid * surf->texinfo->vecs[0][2] + surf->texinfo->vecs[0][3]);
528                                 dt = (int) (x * surf->texinfo->vecs[1][0] + y * surf->texinfo->vecs[1][1] + mid * surf->texinfo->vecs[1][2] + surf->texinfo->vecs[1][3]);
529
530                                 if (ds < surf->texturemins[0] || dt < surf->texturemins[1])
531                                         continue;
532
533                                 ds -= surf->texturemins[0];
534                                 dt -= surf->texturemins[1];
535
536                                 if (ds > surf->extents[0] || dt > surf->extents[1])
537                                         continue;
538
539                                 if (surf->samples)
540                                 {
541                                         qbyte *lightmap;
542                                         int maps, line3, size3, dsfrac = ds & 15, dtfrac = dt & 15, scale = 0, r00 = 0, g00 = 0, b00 = 0, r01 = 0, g01 = 0, b01 = 0, r10 = 0, g10 = 0, b10 = 0, r11 = 0, g11 = 0, b11 = 0;
543                                         line3 = ((surf->extents[0]>>4)+1)*3;
544                                         size3 = ((surf->extents[0]>>4)+1) * ((surf->extents[1]>>4)+1)*3; // LordHavoc: *3 for colored lighting
545
546                                         lightmap = surf->samples + ((dt>>4) * ((surf->extents[0]>>4)+1) + (ds>>4))*3; // LordHavoc: *3 for color
547
548                                         for (maps = 0;maps < MAXLIGHTMAPS && surf->styles[maps] != 255;maps++)
549                                         {
550                                                 scale = d_lightstylevalue[surf->styles[maps]];
551                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
552                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
553                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
554                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
555                                                 lightmap += size3;
556                                         }
557
558 /*
559 LordHavoc: here's the readable version of the interpolation
560 code, not quite as easy for the compiler to optimize...
561
562 dsfrac is the X position in the lightmap pixel, * 16
563 dtfrac is the Y position in the lightmap pixel, * 16
564 r00 is top left corner, r01 is top right corner
565 r10 is bottom left corner, r11 is bottom right corner
566 g and b are the same layout.
567 r0 and r1 are the top and bottom intermediate results
568
569 first we interpolate the top two points, to get the top
570 edge sample
571
572         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
573         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
574         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
575
576 then we interpolate the bottom two points, to get the
577 bottom edge sample
578
579         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
580         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
581         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
582
583 then we interpolate the top and bottom samples to get the
584 middle sample (the one which was requested)
585
586         r = (((r1-r0) * dtfrac) >> 4) + r0;
587         g = (((g1-g0) * dtfrac) >> 4) + g0;
588         b = (((b1-b0) * dtfrac) >> 4) + b0;
589 */
590
591                                         ambientcolor[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
592                                         ambientcolor[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
593                                         ambientcolor[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
594                                 }
595                                 return true; // success
596                         }
597                 }
598
599                 // go down back side
600                 node = node->children[side ^ 1];
601                 startz = mid;
602                 distz = endz - startz;
603                 goto loc0;
604         }
605 }
606
607 void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
608 {
609         Mod_Q1BSP_LightPoint_RecursiveBSPNode(ambientcolor, diffusecolor, diffusenormal, cl.worldmodel->brushq1.nodes + cl.worldmodel->brushq1.hulls[0].firstclipnode, p[0], p[1], p[2], p[2] - 65536);
610 }
611
612 static qbyte *Mod_Q1BSP_DecompressVis(model_t *model, qbyte *in)
613 {
614         static qbyte decompressed[MAX_MAP_LEAFS/8];
615         int c;
616         qbyte *out;
617         int row;
618
619         row = (model->brushq1.numleafs+7)>>3;
620         out = decompressed;
621
622         do
623         {
624                 if (*in)
625                 {
626                         *out++ = *in++;
627                         continue;
628                 }
629
630                 c = in[1];
631                 in += 2;
632                 while (c)
633                 {
634                         *out++ = 0;
635                         c--;
636                 }
637         } while (out - decompressed < row);
638
639         return decompressed;
640 }
641
642 static qbyte *Mod_Q1BSP_LeafPVS(model_t *model, mleaf_t *leaf)
643 {
644         if (r_novis.integer || leaf == model->brushq1.leafs || leaf->compressed_vis == NULL)
645                 return mod_q1bsp_novis;
646         return Mod_Q1BSP_DecompressVis(model, leaf->compressed_vis);
647 }
648
649 static void Mod_Q1BSP_LoadTextures(lump_t *l)
650 {
651         int i, j, k, num, max, altmax, mtwidth, mtheight, *dofs, incomplete;
652         miptex_t *dmiptex;
653         texture_t *tx, *tx2, *anims[10], *altanims[10];
654         dmiptexlump_t *m;
655         qbyte *data, *mtdata;
656         char name[256];
657
658         loadmodel->brushq1.textures = NULL;
659
660         if (!l->filelen)
661                 return;
662
663         m = (dmiptexlump_t *)(mod_base + l->fileofs);
664
665         m->nummiptex = LittleLong (m->nummiptex);
666
667         // add two slots for notexture walls and notexture liquids
668         loadmodel->brushq1.numtextures = m->nummiptex + 2;
669         loadmodel->brushq1.textures = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numtextures * sizeof(texture_t));
670
671         // fill out all slots with notexture
672         for (i = 0, tx = loadmodel->brushq1.textures;i < loadmodel->brushq1.numtextures;i++, tx++)
673         {
674                 tx->number = i;
675                 strcpy(tx->name, "NO TEXTURE FOUND");
676                 tx->width = 16;
677                 tx->height = 16;
678                 tx->skin.base = r_notexture;
679                 tx->shader = &Cshader_wall_lightmap;
680                 tx->flags = SURF_SOLIDCLIP;
681                 if (i == loadmodel->brushq1.numtextures - 1)
682                 {
683                         tx->flags |= SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
684                         tx->shader = &Cshader_water;
685                 }
686                 tx->currentframe = tx;
687         }
688
689         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
690         dofs = m->dataofs;
691         // LordHavoc: mostly rewritten map texture loader
692         for (i = 0;i < m->nummiptex;i++)
693         {
694                 dofs[i] = LittleLong(dofs[i]);
695                 if (dofs[i] == -1 || r_nosurftextures.integer)
696                         continue;
697                 dmiptex = (miptex_t *)((qbyte *)m + dofs[i]);
698
699                 // make sure name is no more than 15 characters
700                 for (j = 0;dmiptex->name[j] && j < 15;j++)
701                         name[j] = dmiptex->name[j];
702                 name[j] = 0;
703
704                 mtwidth = LittleLong(dmiptex->width);
705                 mtheight = LittleLong(dmiptex->height);
706                 mtdata = NULL;
707                 j = LittleLong(dmiptex->offsets[0]);
708                 if (j)
709                 {
710                         // texture included
711                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
712                         {
713                                 Con_Printf("Texture \"%s\" in \"%s\"is corrupt or incomplete\n", dmiptex->name, loadmodel->name);
714                                 continue;
715                         }
716                         mtdata = (qbyte *)dmiptex + j;
717                 }
718
719                 if ((mtwidth & 15) || (mtheight & 15))
720                         Con_Printf("warning: texture \"%s\" in \"%s\" is not 16 aligned", dmiptex->name, loadmodel->name);
721
722                 // LordHavoc: force all names to lowercase
723                 for (j = 0;name[j];j++)
724                         if (name[j] >= 'A' && name[j] <= 'Z')
725                                 name[j] += 'a' - 'A';
726
727                 tx = loadmodel->brushq1.textures + i;
728                 strcpy(tx->name, name);
729                 tx->width = mtwidth;
730                 tx->height = mtheight;
731
732                 if (!tx->name[0])
733                 {
734                         sprintf(tx->name, "unnamed%i", i);
735                         Con_Printf("warning: unnamed texture in %s, renaming to %s\n", loadmodel->name, tx->name);
736                 }
737
738                 // LordHavoc: HL sky textures are entirely different than quake
739                 if (!loadmodel->brushq1.ishlbsp && !strncmp(tx->name, "sky", 3) && mtwidth == 256 && mtheight == 128)
740                 {
741                         if (loadmodel->isworldmodel)
742                         {
743                                 data = loadimagepixels(tx->name, false, 0, 0);
744                                 if (data)
745                                 {
746                                         if (image_width == 256 && image_height == 128)
747                                         {
748                                                 R_InitSky(data, 4);
749                                                 Mem_Free(data);
750                                         }
751                                         else
752                                         {
753                                                 Mem_Free(data);
754                                                 Con_Printf("Invalid replacement texture for sky \"%s\" in %\"%s\", must be 256x128 pixels\n", tx->name, loadmodel->name);
755                                                 if (mtdata != NULL)
756                                                         R_InitSky(mtdata, 1);
757                                         }
758                                 }
759                                 else if (mtdata != NULL)
760                                         R_InitSky(mtdata, 1);
761                         }
762                 }
763                 else
764                 {
765                         if (!Mod_LoadSkinFrame(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, false, true, true))
766                         {
767                                 // did not find external texture, load it from the bsp or wad3
768                                 if (loadmodel->brushq1.ishlbsp)
769                                 {
770                                         // internal texture overrides wad
771                                         qbyte *pixels, *freepixels, *fogpixels;
772                                         pixels = freepixels = NULL;
773                                         if (mtdata)
774                                                 pixels = W_ConvertWAD3Texture(dmiptex);
775                                         if (pixels == NULL)
776                                                 pixels = freepixels = W_GetTexture(tx->name);
777                                         if (pixels != NULL)
778                                         {
779                                                 tx->width = image_width;
780                                                 tx->height = image_height;
781                                                 tx->skin.base = tx->skin.merged = R_LoadTexture2D(loadmodel->texturepool, tx->name, image_width, image_height, pixels, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, NULL);
782                                                 if (Image_CheckAlpha(pixels, image_width * image_height, true))
783                                                 {
784                                                         fogpixels = Mem_Alloc(tempmempool, image_width * image_height * 4);
785                                                         for (j = 0;j < image_width * image_height * 4;j += 4)
786                                                         {
787                                                                 fogpixels[j + 0] = 255;
788                                                                 fogpixels[j + 1] = 255;
789                                                                 fogpixels[j + 2] = 255;
790                                                                 fogpixels[j + 3] = pixels[j + 3];
791                                                         }
792                                                         tx->skin.fog = R_LoadTexture2D(loadmodel->texturepool, tx->name, image_width, image_height, pixels, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, NULL);
793                                                         Mem_Free(fogpixels);
794                                                 }
795                                         }
796                                         if (freepixels)
797                                                 Mem_Free(freepixels);
798                                 }
799                                 else if (mtdata) // texture included
800                                         Mod_LoadSkinFrame_Internal(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_PRECACHE, false, true, tx->name[0] != '*' && r_fullbrights.integer, mtdata, tx->width, tx->height);
801                         }
802                 }
803                 if (tx->skin.base == NULL)
804                 {
805                         // no texture found
806                         tx->width = 16;
807                         tx->height = 16;
808                         tx->skin.base = r_notexture;
809                 }
810
811                 if (tx->name[0] == '*')
812                 {
813                         // turb does not block movement
814                         tx->flags &= ~SURF_SOLIDCLIP;
815                         tx->flags |= SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
816                         // LordHavoc: some turbulent textures should be fullbright and solid
817                         if (!strncmp(tx->name,"*lava",5)
818                          || !strncmp(tx->name,"*teleport",9)
819                          || !strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
820                                 tx->flags |= SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA;
821                         else
822                                 tx->flags |= SURF_WATERALPHA;
823                         tx->shader = &Cshader_water;
824                 }
825                 else if (tx->name[0] == 's' && tx->name[1] == 'k' && tx->name[2] == 'y')
826                 {
827                         tx->flags |= SURF_DRAWSKY;
828                         tx->shader = &Cshader_sky;
829                 }
830                 else
831                 {
832                         tx->flags |= SURF_LIGHTMAP;
833                         if (!tx->skin.fog)
834                                 tx->flags |= SURF_SHADOWCAST | SURF_SHADOWLIGHT;
835                         tx->shader = &Cshader_wall_lightmap;
836                 }
837
838                 // start out with no animation
839                 tx->currentframe = tx;
840         }
841
842         // sequence the animations
843         for (i = 0;i < m->nummiptex;i++)
844         {
845                 tx = loadmodel->brushq1.textures + i;
846                 if (!tx || tx->name[0] != '+' || tx->name[1] == 0 || tx->name[2] == 0)
847                         continue;
848                 if (tx->anim_total[0] || tx->anim_total[1])
849                         continue;       // already sequenced
850
851                 // find the number of frames in the animation
852                 memset(anims, 0, sizeof(anims));
853                 memset(altanims, 0, sizeof(altanims));
854
855                 for (j = i;j < m->nummiptex;j++)
856                 {
857                         tx2 = loadmodel->brushq1.textures + j;
858                         if (!tx2 || tx2->name[0] != '+' || strcmp(tx2->name+2, tx->name+2))
859                                 continue;
860
861                         num = tx2->name[1];
862                         if (num >= '0' && num <= '9')
863                                 anims[num - '0'] = tx2;
864                         else if (num >= 'a' && num <= 'j')
865                                 altanims[num - 'a'] = tx2;
866                         else
867                                 Con_Printf("Bad animating texture %s\n", tx->name);
868                 }
869
870                 max = altmax = 0;
871                 for (j = 0;j < 10;j++)
872                 {
873                         if (anims[j])
874                                 max = j + 1;
875                         if (altanims[j])
876                                 altmax = j + 1;
877                 }
878                 //Con_Printf("linking animation %s (%i:%i frames)\n\n", tx->name, max, altmax);
879
880                 incomplete = false;
881                 for (j = 0;j < max;j++)
882                 {
883                         if (!anims[j])
884                         {
885                                 Con_Printf("Missing frame %i of %s\n", j, tx->name);
886                                 incomplete = true;
887                         }
888                 }
889                 for (j = 0;j < altmax;j++)
890                 {
891                         if (!altanims[j])
892                         {
893                                 Con_Printf("Missing altframe %i of %s\n", j, tx->name);
894                                 incomplete = true;
895                         }
896                 }
897                 if (incomplete)
898                         continue;
899
900                 if (altmax < 1)
901                 {
902                         // if there is no alternate animation, duplicate the primary
903                         // animation into the alternate
904                         altmax = max;
905                         for (k = 0;k < 10;k++)
906                                 altanims[k] = anims[k];
907                 }
908
909                 // link together the primary animation
910                 for (j = 0;j < max;j++)
911                 {
912                         tx2 = anims[j];
913                         tx2->animated = true;
914                         tx2->anim_total[0] = max;
915                         tx2->anim_total[1] = altmax;
916                         for (k = 0;k < 10;k++)
917                         {
918                                 tx2->anim_frames[0][k] = anims[k];
919                                 tx2->anim_frames[1][k] = altanims[k];
920                         }
921                 }
922
923                 // if there really is an alternate anim...
924                 if (anims[0] != altanims[0])
925                 {
926                         // link together the alternate animation
927                         for (j = 0;j < altmax;j++)
928                         {
929                                 tx2 = altanims[j];
930                                 tx2->animated = true;
931                                 // the primary/alternate are reversed here
932                                 tx2->anim_total[0] = altmax;
933                                 tx2->anim_total[1] = max;
934                                 for (k = 0;k < 10;k++)
935                                 {
936                                         tx2->anim_frames[0][k] = altanims[k];
937                                         tx2->anim_frames[1][k] = anims[k];
938                                 }
939                         }
940                 }
941         }
942 }
943
944 static void Mod_Q1BSP_LoadLighting(lump_t *l)
945 {
946         int i;
947         qbyte *in, *out, *data, d;
948         char litfilename[1024];
949         loadmodel->brushq1.lightdata = NULL;
950         if (loadmodel->brushq1.ishlbsp) // LordHavoc: load the colored lighting data straight
951         {
952                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen);
953                 memcpy(loadmodel->brushq1.lightdata, mod_base + l->fileofs, l->filelen);
954         }
955         else // LordHavoc: bsp version 29 (normal white lighting)
956         {
957                 // LordHavoc: hope is not lost yet, check for a .lit file to load
958                 strcpy(litfilename, loadmodel->name);
959                 FS_StripExtension(litfilename, litfilename);
960                 strcat(litfilename, ".lit");
961                 data = (qbyte*) FS_LoadFile(litfilename, false);
962                 if (data)
963                 {
964                         if (fs_filesize > 8 && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
965                         {
966                                 i = LittleLong(((int *)data)[1]);
967                                 if (i == 1)
968                                 {
969                                         Con_DPrintf("loaded %s\n", litfilename);
970                                         loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, fs_filesize - 8);
971                                         memcpy(loadmodel->brushq1.lightdata, data + 8, fs_filesize - 8);
972                                         Mem_Free(data);
973                                         return;
974                                 }
975                                 else
976                                 {
977                                         Con_Printf("Unknown .lit file version (%d)\n", i);
978                                         Mem_Free(data);
979                                 }
980                         }
981                         else
982                         {
983                                 if (fs_filesize == 8)
984                                         Con_Printf("Empty .lit file, ignoring\n");
985                                 else
986                                         Con_Printf("Corrupt .lit file (old version?), ignoring\n");
987                                 Mem_Free(data);
988                         }
989                 }
990                 // LordHavoc: oh well, expand the white lighting data
991                 if (!l->filelen)
992                         return;
993                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen*3);
994                 in = loadmodel->brushq1.lightdata + l->filelen*2; // place the file at the end, so it will not be overwritten until the very last write
995                 out = loadmodel->brushq1.lightdata;
996                 memcpy(in, mod_base + l->fileofs, l->filelen);
997                 for (i = 0;i < l->filelen;i++)
998                 {
999                         d = *in++;
1000                         *out++ = d;
1001                         *out++ = d;
1002                         *out++ = d;
1003                 }
1004         }
1005 }
1006
1007 static void Mod_Q1BSP_LoadLightList(void)
1008 {
1009         int a, n, numlights;
1010         char lightsfilename[1024], *s, *t, *lightsstring;
1011         mlight_t *e;
1012
1013         strcpy(lightsfilename, loadmodel->name);
1014         FS_StripExtension(lightsfilename, lightsfilename);
1015         strcat(lightsfilename, ".lights");
1016         s = lightsstring = (char *) FS_LoadFile(lightsfilename, false);
1017         if (s)
1018         {
1019                 numlights = 0;
1020                 while (*s)
1021                 {
1022                         while (*s && *s != '\n')
1023                                 s++;
1024                         if (!*s)
1025                         {
1026                                 Mem_Free(lightsstring);
1027                                 Host_Error("lights file must end with a newline\n");
1028                         }
1029                         s++;
1030                         numlights++;
1031                 }
1032                 loadmodel->brushq1.lights = Mem_Alloc(loadmodel->mempool, numlights * sizeof(mlight_t));
1033                 s = lightsstring;
1034                 n = 0;
1035                 while (*s && n < numlights)
1036                 {
1037                         t = s;
1038                         while (*s && *s != '\n')
1039                                 s++;
1040                         if (!*s)
1041                         {
1042                                 Mem_Free(lightsstring);
1043                                 Host_Error("misparsed lights file!\n");
1044                         }
1045                         e = loadmodel->brushq1.lights + n;
1046                         *s = 0;
1047                         a = sscanf(t, "%f %f %f %f %f %f %f %f %f %f %f %f %f %d", &e->origin[0], &e->origin[1], &e->origin[2], &e->falloff, &e->light[0], &e->light[1], &e->light[2], &e->subtract, &e->spotdir[0], &e->spotdir[1], &e->spotdir[2], &e->spotcone, &e->distbias, &e->style);
1048                         *s = '\n';
1049                         if (a != 14)
1050                         {
1051                                 Mem_Free(lightsstring);
1052                                 Host_Error("invalid lights file, found %d parameters on line %i, should be 14 parameters (origin[0] origin[1] origin[2] falloff light[0] light[1] light[2] subtract spotdir[0] spotdir[1] spotdir[2] spotcone distancebias style)\n", a, n + 1);
1053                         }
1054                         s++;
1055                         n++;
1056                 }
1057                 if (*s)
1058                 {
1059                         Mem_Free(lightsstring);
1060                         Host_Error("misparsed lights file!\n");
1061                 }
1062                 loadmodel->brushq1.numlights = numlights;
1063                 Mem_Free(lightsstring);
1064         }
1065 }
1066
1067 /*
1068 static int castshadowcount = 0;
1069 static void Mod_Q1BSP_ProcessLightList(void)
1070 {
1071         int j, k, l, *mark, lnum;
1072         mlight_t *e;
1073         msurface_t *surf;
1074         float dist;
1075         mleaf_t *leaf;
1076         qbyte *pvs;
1077         vec3_t temp;
1078         float *v, radius2;
1079         for (lnum = 0, e = loadmodel->brushq1.lights;lnum < loadmodel->brushq1.numlights;lnum++, e++)
1080         {
1081                 e->cullradius2 = DotProduct(e->light, e->light) / (e->falloff * e->falloff * 8192.0f * 8192.0f * 2.0f * 2.0f);// + 4096.0f;
1082                 if (e->cullradius2 > 4096.0f * 4096.0f)
1083                         e->cullradius2 = 4096.0f * 4096.0f;
1084                 e->cullradius = e->lightradius = sqrt(e->cullradius2);
1085                 leaf = Mod_Q1BSP_PointInLeaf(e->origin, loadmodel);
1086                 if (leaf->compressed_vis)
1087                         pvs = Mod_Q1BSP_DecompressVis(leaf->compressed_vis, loadmodel);
1088                 else
1089                         pvs = mod_q1bsp_novis;
1090                 for (j = 0;j < loadmodel->brushq1.numsurfaces;j++)
1091                         loadmodel->brushq1.surfacevisframes[j] = -1;
1092                 for (j = 0, leaf = loadmodel->brushq1.leafs + 1;j < loadmodel->brushq1.numleafs - 1;j++, leaf++)
1093                 {
1094                         if (pvs[j >> 3] & (1 << (j & 7)))
1095                         {
1096                                 for (k = 0, mark = leaf->firstmarksurface;k < leaf->nummarksurfaces;k++, mark++)
1097                                 {
1098                                         surf = loadmodel->brushq1.surfaces + *mark;
1099                                         if (surf->number != *mark)
1100                                                 Con_Printf("%d != %d\n", surf->number, *mark);
1101                                         dist = DotProduct(e->origin, surf->plane->normal) - surf->plane->dist;
1102                                         if (surf->flags & SURF_PLANEBACK)
1103                                                 dist = -dist;
1104                                         if (dist > 0 && dist < e->cullradius)
1105                                         {
1106                                                 temp[0] = bound(surf->poly_mins[0], e->origin[0], surf->poly_maxs[0]) - e->origin[0];
1107                                                 temp[1] = bound(surf->poly_mins[1], e->origin[1], surf->poly_maxs[1]) - e->origin[1];
1108                                                 temp[2] = bound(surf->poly_mins[2], e->origin[2], surf->poly_maxs[2]) - e->origin[2];
1109                                                 if (DotProduct(temp, temp) < lightradius2)
1110                                                         loadmodel->brushq1.surfacevisframes[*mark] = -2;
1111                                         }
1112                                 }
1113                         }
1114                 }
1115                 // build list of light receiving surfaces
1116                 e->numsurfaces = 0;
1117                 for (j = 0;j < loadmodel->brushq1.numsurfaces;j++)
1118                         if (loadmodel->brushq1.surfacevisframes[j] == -2)
1119                                 e->numsurfaces++;
1120                 e->surfaces = NULL;
1121                 if (e->numsurfaces > 0)
1122                 {
1123                         e->surfaces = Mem_Alloc(loadmodel->mempool, sizeof(msurface_t *) * e->numsurfaces);
1124                         e->numsurfaces = 0;
1125                         for (j = 0;j < loadmodel->brushq1.numsurfaces;j++)
1126                                 if (loadmodel->brushq1.surfacevisframes[j] == -2)
1127                                         e->surfaces[e->numsurfaces++] = loadmodel->brushq1.surfaces + j;
1128                 }
1129                 // find bounding box and sphere of lit surfaces
1130                 // (these will be used for creating a shape to clip the light)
1131                 radius2 = 0;
1132                 for (j = 0;j < e->numsurfaces;j++)
1133                 {
1134                         surf = e->surfaces[j];
1135                         if (j == 0)
1136                         {
1137                                 VectorCopy(surf->poly_verts, e->mins);
1138                                 VectorCopy(surf->poly_verts, e->maxs);
1139                         }
1140                         for (k = 0, v = surf->poly_verts;k < surf->poly_numverts;k++, v += 3)
1141                         {
1142                                 if (e->mins[0] > v[0]) e->mins[0] = v[0];if (e->maxs[0] < v[0]) e->maxs[0] = v[0];
1143                                 if (e->mins[1] > v[1]) e->mins[1] = v[1];if (e->maxs[1] < v[1]) e->maxs[1] = v[1];
1144                                 if (e->mins[2] > v[2]) e->mins[2] = v[2];if (e->maxs[2] < v[2]) e->maxs[2] = v[2];
1145                                 VectorSubtract(v, e->origin, temp);
1146                                 dist = DotProduct(temp, temp);
1147                                 if (radius2 < dist)
1148                                         radius2 = dist;
1149                         }
1150                 }
1151                 if (e->cullradius2 > radius2)
1152                 {
1153                         e->cullradius2 = radius2;
1154                         e->cullradius = sqrt(e->cullradius2);
1155                 }
1156                 if (e->mins[0] < e->origin[0] - e->lightradius) e->mins[0] = e->origin[0] - e->lightradius;
1157                 if (e->maxs[0] > e->origin[0] + e->lightradius) e->maxs[0] = e->origin[0] + e->lightradius;
1158                 if (e->mins[1] < e->origin[1] - e->lightradius) e->mins[1] = e->origin[1] - e->lightradius;
1159                 if (e->maxs[1] > e->origin[1] + e->lightradius) e->maxs[1] = e->origin[1] + e->lightradius;
1160                 if (e->mins[2] < e->origin[2] - e->lightradius) e->mins[2] = e->origin[2] - e->lightradius;
1161                 if (e->maxs[2] > e->origin[2] + e->lightradius) e->maxs[2] = e->origin[2] + e->lightradius;
1162                 // clip shadow volumes against eachother to remove unnecessary
1163                 // polygons(and sections of polygons)
1164                 {
1165                         //vec3_t polymins, polymaxs;
1166                         int maxverts = 4;
1167                         float *verts = Mem_Alloc(loadmodel->mempool, maxverts * sizeof(float[3]));
1168                         float f, *v0, *v1, projectdistance;
1169
1170                         e->shadowvolume = Mod_ShadowMesh_Begin(loadmodel->mempool, 1024);
1171 #if 0
1172                         {
1173                         vec3_t outermins, outermaxs, innermins, innermaxs;
1174                         innermins[0] = e->mins[0] - 1;
1175                         innermins[1] = e->mins[1] - 1;
1176                         innermins[2] = e->mins[2] - 1;
1177                         innermaxs[0] = e->maxs[0] + 1;
1178                         innermaxs[1] = e->maxs[1] + 1;
1179                         innermaxs[2] = e->maxs[2] + 1;
1180                         outermins[0] = loadmodel->normalmins[0] - 1;
1181                         outermins[1] = loadmodel->normalmins[1] - 1;
1182                         outermins[2] = loadmodel->normalmins[2] - 1;
1183                         outermaxs[0] = loadmodel->normalmaxs[0] + 1;
1184                         outermaxs[1] = loadmodel->normalmaxs[1] + 1;
1185                         outermaxs[2] = loadmodel->normalmaxs[2] + 1;
1186                         // add bounding box around the whole shadow volume set,
1187                         // facing inward to limit light area, with an outer bounding box
1188                         // facing outward (this is needed by the shadow rendering method)
1189                         // X major
1190                         verts[ 0] = innermaxs[0];verts[ 1] = innermins[1];verts[ 2] = innermaxs[2];
1191                         verts[ 3] = innermaxs[0];verts[ 4] = innermins[1];verts[ 5] = innermins[2];
1192                         verts[ 6] = innermaxs[0];verts[ 7] = innermaxs[1];verts[ 8] = innermins[2];
1193                         verts[ 9] = innermaxs[0];verts[10] = innermaxs[1];verts[11] = innermaxs[2];
1194                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1195                         verts[ 0] = outermaxs[0];verts[ 1] = outermaxs[1];verts[ 2] = outermaxs[2];
1196                         verts[ 3] = outermaxs[0];verts[ 4] = outermaxs[1];verts[ 5] = outermins[2];
1197                         verts[ 6] = outermaxs[0];verts[ 7] = outermins[1];verts[ 8] = outermins[2];
1198                         verts[ 9] = outermaxs[0];verts[10] = outermins[1];verts[11] = outermaxs[2];
1199                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1200                         // X minor
1201                         verts[ 0] = innermins[0];verts[ 1] = innermaxs[1];verts[ 2] = innermaxs[2];
1202                         verts[ 3] = innermins[0];verts[ 4] = innermaxs[1];verts[ 5] = innermins[2];
1203                         verts[ 6] = innermins[0];verts[ 7] = innermins[1];verts[ 8] = innermins[2];
1204                         verts[ 9] = innermins[0];verts[10] = innermins[1];verts[11] = innermaxs[2];
1205                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1206                         verts[ 0] = outermins[0];verts[ 1] = outermins[1];verts[ 2] = outermaxs[2];
1207                         verts[ 3] = outermins[0];verts[ 4] = outermins[1];verts[ 5] = outermins[2];
1208                         verts[ 6] = outermins[0];verts[ 7] = outermaxs[1];verts[ 8] = outermins[2];
1209                         verts[ 9] = outermins[0];verts[10] = outermaxs[1];verts[11] = outermaxs[2];
1210                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1211                         // Y major
1212                         verts[ 0] = innermaxs[0];verts[ 1] = innermaxs[1];verts[ 2] = innermaxs[2];
1213                         verts[ 3] = innermaxs[0];verts[ 4] = innermaxs[1];verts[ 5] = innermins[2];
1214                         verts[ 6] = innermins[0];verts[ 7] = innermaxs[1];verts[ 8] = innermins[2];
1215                         verts[ 9] = innermins[0];verts[10] = innermaxs[1];verts[11] = innermaxs[2];
1216                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1217                         verts[ 0] = outermins[0];verts[ 1] = outermaxs[1];verts[ 2] = outermaxs[2];
1218                         verts[ 3] = outermins[0];verts[ 4] = outermaxs[1];verts[ 5] = outermins[2];
1219                         verts[ 6] = outermaxs[0];verts[ 7] = outermaxs[1];verts[ 8] = outermins[2];
1220                         verts[ 9] = outermaxs[0];verts[10] = outermaxs[1];verts[11] = outermaxs[2];
1221                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1222                         // Y minor
1223                         verts[ 0] = innermins[0];verts[ 1] = innermins[1];verts[ 2] = innermaxs[2];
1224                         verts[ 3] = innermins[0];verts[ 4] = innermins[1];verts[ 5] = innermins[2];
1225                         verts[ 6] = innermaxs[0];verts[ 7] = innermins[1];verts[ 8] = innermins[2];
1226                         verts[ 9] = innermaxs[0];verts[10] = innermins[1];verts[11] = innermaxs[2];
1227                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1228                         verts[ 0] = outermaxs[0];verts[ 1] = outermins[1];verts[ 2] = outermaxs[2];
1229                         verts[ 3] = outermaxs[0];verts[ 4] = outermins[1];verts[ 5] = outermins[2];
1230                         verts[ 6] = outermins[0];verts[ 7] = outermins[1];verts[ 8] = outermins[2];
1231                         verts[ 9] = outermins[0];verts[10] = outermins[1];verts[11] = outermaxs[2];
1232                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1233                         // Z major
1234                         verts[ 0] = innermaxs[0];verts[ 1] = innermins[1];verts[ 2] = innermaxs[2];
1235                         verts[ 3] = innermaxs[0];verts[ 4] = innermaxs[1];verts[ 5] = innermaxs[2];
1236                         verts[ 6] = innermins[0];verts[ 7] = innermaxs[1];verts[ 8] = innermaxs[2];
1237                         verts[ 9] = innermins[0];verts[10] = innermins[1];verts[11] = innermaxs[2];
1238                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1239                         verts[ 0] = outermaxs[0];verts[ 1] = outermaxs[1];verts[ 2] = outermaxs[2];
1240                         verts[ 3] = outermaxs[0];verts[ 4] = outermins[1];verts[ 5] = outermaxs[2];
1241                         verts[ 6] = outermins[0];verts[ 7] = outermins[1];verts[ 8] = outermaxs[2];
1242                         verts[ 9] = outermins[0];verts[10] = outermaxs[1];verts[11] = outermaxs[2];
1243                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1244                         // Z minor
1245                         verts[ 0] = innermaxs[0];verts[ 1] = innermaxs[1];verts[ 2] = innermins[2];
1246                         verts[ 3] = innermaxs[0];verts[ 4] = innermins[1];verts[ 5] = innermins[2];
1247                         verts[ 6] = innermins[0];verts[ 7] = innermins[1];verts[ 8] = innermins[2];
1248                         verts[ 9] = innermins[0];verts[10] = innermaxs[1];verts[11] = innermins[2];
1249                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1250                         verts[ 0] = outermaxs[0];verts[ 1] = outermins[1];verts[ 2] = outermins[2];
1251                         verts[ 3] = outermaxs[0];verts[ 4] = outermaxs[1];verts[ 5] = outermins[2];
1252                         verts[ 6] = outermins[0];verts[ 7] = outermaxs[1];verts[ 8] = outermins[2];
1253                         verts[ 9] = outermins[0];verts[10] = outermins[1];verts[11] = outermins[2];
1254                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1255                         }
1256 #endif
1257                         castshadowcount++;
1258                         for (j = 0;j < e->numsurfaces;j++)
1259                         {
1260                                 surf = e->surfaces[j];
1261                                 if (surf->flags & SURF_SHADOWCAST)
1262                                         surf->castshadow = castshadowcount;
1263                         }
1264                         for (j = 0;j < e->numsurfaces;j++)
1265                         {
1266                                 surf = e->surfaces[j];
1267                                 if (surf->castshadow != castshadowcount)
1268                                         continue;
1269                                 f = DotProduct(e->origin, surf->plane->normal) - surf->plane->dist;
1270                                 if (surf->flags & SURF_PLANEBACK)
1271                                         f = -f;
1272                                 projectdistance = e->lightradius;
1273                                 if (maxverts < surf->poly_numverts)
1274                                 {
1275                                         maxverts = surf->poly_numverts;
1276                                         if (verts)
1277                                                 Mem_Free(verts);
1278                                         verts = Mem_Alloc(loadmodel->mempool, maxverts * sizeof(float[3]));
1279                                 }
1280                                 // copy the original polygon, for the front cap of the volume
1281                                 for (k = 0, v0 = surf->poly_verts, v1 = verts;k < surf->poly_numverts;k++, v0 += 3, v1 += 3)
1282                                         VectorCopy(v0, v1);
1283                                 Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, surf->poly_numverts, verts);
1284                                 // project the original polygon, reversed, for the back cap of the volume
1285                                 for (k = 0, v0 = surf->poly_verts + (surf->poly_numverts - 1) * 3, v1 = verts;k < surf->poly_numverts;k++, v0 -= 3, v1 += 3)
1286                                 {
1287                                         VectorSubtract(v0, e->origin, temp);
1288                                         VectorNormalize(temp);
1289                                         VectorMA(v0, projectdistance, temp, v1);
1290                                 }
1291                                 Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, surf->poly_numverts, verts);
1292                                 // project the shadow volume sides
1293                                 for (l = surf->poly_numverts - 1, k = 0, v0 = surf->poly_verts + (surf->poly_numverts - 1) * 3, v1 = surf->poly_verts;k < surf->poly_numverts;l = k, k++, v0 = v1, v1 += 3)
1294                                 {
1295                                         if (!surf->neighborsurfaces[l] || surf->neighborsurfaces[l]->castshadow != castshadowcount)
1296                                         {
1297                                                 VectorCopy(v1, &verts[0]);
1298                                                 VectorCopy(v0, &verts[3]);
1299                                                 VectorCopy(v0, &verts[6]);
1300                                                 VectorCopy(v1, &verts[9]);
1301                                                 VectorSubtract(&verts[6], e->origin, temp);
1302                                                 VectorNormalize(temp);
1303                                                 VectorMA(&verts[6], projectdistance, temp, &verts[6]);
1304                                                 VectorSubtract(&verts[9], e->origin, temp);
1305                                                 VectorNormalize(temp);
1306                                                 VectorMA(&verts[9], projectdistance, temp, &verts[9]);
1307                                                 Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1308                                         }
1309                                 }
1310                         }
1311                         // build the triangle mesh
1312                         e->shadowvolume = Mod_ShadowMesh_Finish(loadmodel->mempool, e->shadowvolume);
1313                         {
1314                                 shadowmesh_t *mesh;
1315                                 l = 0;
1316                                 for (mesh = e->shadowvolume;mesh;mesh = mesh->next)
1317                                         l += mesh->numtriangles;
1318                                 Con_Printf("light %i shadow volume built containing %i triangles\n", lnum, l);
1319                         }
1320                 }
1321         }
1322 }
1323 */
1324
1325
1326 static void Mod_Q1BSP_LoadVisibility(lump_t *l)
1327 {
1328         loadmodel->brushq1.visdata = NULL;
1329         if (!l->filelen)
1330                 return;
1331         loadmodel->brushq1.visdata = Mem_Alloc(loadmodel->mempool, l->filelen);
1332         memcpy(loadmodel->brushq1.visdata, mod_base + l->fileofs, l->filelen);
1333 }
1334
1335 // used only for HalfLife maps
1336 static void Mod_Q1BSP_ParseWadsFromEntityLump(const char *data)
1337 {
1338         char key[128], value[4096];
1339         char wadname[128];
1340         int i, j, k;
1341         if (!data)
1342                 return;
1343         if (!COM_ParseToken(&data, false))
1344                 return; // error
1345         if (com_token[0] != '{')
1346                 return; // error
1347         while (1)
1348         {
1349                 if (!COM_ParseToken(&data, false))
1350                         return; // error
1351                 if (com_token[0] == '}')
1352                         break; // end of worldspawn
1353                 if (com_token[0] == '_')
1354                         strcpy(key, com_token + 1);
1355                 else
1356                         strcpy(key, com_token);
1357                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
1358                         key[strlen(key)-1] = 0;
1359                 if (!COM_ParseToken(&data, false))
1360                         return; // error
1361                 strcpy(value, com_token);
1362                 if (!strcmp("wad", key)) // for HalfLife maps
1363                 {
1364                         if (loadmodel->brushq1.ishlbsp)
1365                         {
1366                                 j = 0;
1367                                 for (i = 0;i < 4096;i++)
1368                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
1369                                                 break;
1370                                 if (value[i])
1371                                 {
1372                                         for (;i < 4096;i++)
1373                                         {
1374                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
1375                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
1376                                                         j = i+1;
1377                                                 else if (value[i] == ';' || value[i] == 0)
1378                                                 {
1379                                                         k = value[i];
1380                                                         value[i] = 0;
1381                                                         strcpy(wadname, "textures/");
1382                                                         strcat(wadname, &value[j]);
1383                                                         W_LoadTextureWadFile(wadname, false);
1384                                                         j = i+1;
1385                                                         if (!k)
1386                                                                 break;
1387                                                 }
1388                                         }
1389                                 }
1390                         }
1391                 }
1392         }
1393 }
1394
1395 static void Mod_Q1BSP_LoadEntities(lump_t *l)
1396 {
1397         loadmodel->brush.entities = NULL;
1398         if (!l->filelen)
1399                 return;
1400         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
1401         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
1402         if (loadmodel->brushq1.ishlbsp)
1403                 Mod_Q1BSP_ParseWadsFromEntityLump(loadmodel->brush.entities);
1404 }
1405
1406
1407 static void Mod_Q1BSP_LoadVertexes(lump_t *l)
1408 {
1409         dvertex_t       *in;
1410         mvertex_t       *out;
1411         int                     i, count;
1412
1413         in = (void *)(mod_base + l->fileofs);
1414         if (l->filelen % sizeof(*in))
1415                 Host_Error("Mod_Q1BSP_LoadVertexes: funny lump size in %s",loadmodel->name);
1416         count = l->filelen / sizeof(*in);
1417         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1418
1419         loadmodel->brushq1.vertexes = out;
1420         loadmodel->brushq1.numvertexes = count;
1421
1422         for ( i=0 ; i<count ; i++, in++, out++)
1423         {
1424                 out->position[0] = LittleFloat(in->point[0]);
1425                 out->position[1] = LittleFloat(in->point[1]);
1426                 out->position[2] = LittleFloat(in->point[2]);
1427         }
1428 }
1429
1430 static void Mod_Q1BSP_LoadSubmodels(lump_t *l)
1431 {
1432         dmodel_t        *in;
1433         dmodel_t        *out;
1434         int                     i, j, count;
1435
1436         in = (void *)(mod_base + l->fileofs);
1437         if (l->filelen % sizeof(*in))
1438                 Host_Error("Mod_Q1BSP_LoadSubmodels: funny lump size in %s",loadmodel->name);
1439         count = l->filelen / sizeof(*in);
1440         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1441
1442         loadmodel->brushq1.submodels = out;
1443         loadmodel->brushq1.numsubmodels = count;
1444
1445         for ( i=0 ; i<count ; i++, in++, out++)
1446         {
1447                 for (j=0 ; j<3 ; j++)
1448                 {
1449                         // spread the mins / maxs by a pixel
1450                         out->mins[j] = LittleFloat(in->mins[j]) - 1;
1451                         out->maxs[j] = LittleFloat(in->maxs[j]) + 1;
1452                         out->origin[j] = LittleFloat(in->origin[j]);
1453                 }
1454                 for (j=0 ; j<MAX_MAP_HULLS ; j++)
1455                         out->headnode[j] = LittleLong(in->headnode[j]);
1456                 out->visleafs = LittleLong(in->visleafs);
1457                 out->firstface = LittleLong(in->firstface);
1458                 out->numfaces = LittleLong(in->numfaces);
1459         }
1460 }
1461
1462 static void Mod_Q1BSP_LoadEdges(lump_t *l)
1463 {
1464         dedge_t *in;
1465         medge_t *out;
1466         int     i, count;
1467
1468         in = (void *)(mod_base + l->fileofs);
1469         if (l->filelen % sizeof(*in))
1470                 Host_Error("Mod_Q1BSP_LoadEdges: funny lump size in %s",loadmodel->name);
1471         count = l->filelen / sizeof(*in);
1472         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1473
1474         loadmodel->brushq1.edges = out;
1475         loadmodel->brushq1.numedges = count;
1476
1477         for ( i=0 ; i<count ; i++, in++, out++)
1478         {
1479                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
1480                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
1481         }
1482 }
1483
1484 static void Mod_Q1BSP_LoadTexinfo(lump_t *l)
1485 {
1486         texinfo_t *in;
1487         mtexinfo_t *out;
1488         int i, j, k, count, miptex;
1489
1490         in = (void *)(mod_base + l->fileofs);
1491         if (l->filelen % sizeof(*in))
1492                 Host_Error("Mod_Q1BSP_LoadTexinfo: funny lump size in %s",loadmodel->name);
1493         count = l->filelen / sizeof(*in);
1494         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1495
1496         loadmodel->brushq1.texinfo = out;
1497         loadmodel->brushq1.numtexinfo = count;
1498
1499         for (i = 0;i < count;i++, in++, out++)
1500         {
1501                 for (k = 0;k < 2;k++)
1502                         for (j = 0;j < 4;j++)
1503                                 out->vecs[k][j] = LittleFloat(in->vecs[k][j]);
1504
1505                 miptex = LittleLong(in->miptex);
1506                 out->flags = LittleLong(in->flags);
1507
1508                 out->texture = NULL;
1509                 if (loadmodel->brushq1.textures)
1510                 {
1511                         if ((unsigned int) miptex >= (unsigned int) loadmodel->brushq1.numtextures)
1512                                 Con_Printf("error in model \"%s\": invalid miptex index %i(of %i)\n", loadmodel->name, miptex, loadmodel->brushq1.numtextures);
1513                         else
1514                                 out->texture = loadmodel->brushq1.textures + miptex;
1515                 }
1516                 if (out->flags & TEX_SPECIAL)
1517                 {
1518                         // if texture chosen is NULL or the shader needs a lightmap,
1519                         // force to notexture water shader
1520                         if (out->texture == NULL || out->texture->shader->flags & SHADERFLAGS_NEEDLIGHTMAP)
1521                                 out->texture = loadmodel->brushq1.textures + (loadmodel->brushq1.numtextures - 1);
1522                 }
1523                 else
1524                 {
1525                         // if texture chosen is NULL, force to notexture
1526                         if (out->texture == NULL)
1527                                 out->texture = loadmodel->brushq1.textures + (loadmodel->brushq1.numtextures - 2);
1528                 }
1529         }
1530 }
1531
1532 #if 0
1533 void BoundPoly(int numverts, float *verts, vec3_t mins, vec3_t maxs)
1534 {
1535         int             i, j;
1536         float   *v;
1537
1538         mins[0] = mins[1] = mins[2] = 9999;
1539         maxs[0] = maxs[1] = maxs[2] = -9999;
1540         v = verts;
1541         for (i = 0;i < numverts;i++)
1542         {
1543                 for (j = 0;j < 3;j++, v++)
1544                 {
1545                         if (*v < mins[j])
1546                                 mins[j] = *v;
1547                         if (*v > maxs[j])
1548                                 maxs[j] = *v;
1549                 }
1550         }
1551 }
1552
1553 #define MAX_SUBDIVPOLYTRIANGLES 4096
1554 #define MAX_SUBDIVPOLYVERTS(MAX_SUBDIVPOLYTRIANGLES * 3)
1555
1556 static int subdivpolyverts, subdivpolytriangles;
1557 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
1558 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
1559
1560 static int subdivpolylookupvert(vec3_t v)
1561 {
1562         int i;
1563         for (i = 0;i < subdivpolyverts;i++)
1564                 if (subdivpolyvert[i][0] == v[0]
1565                  && subdivpolyvert[i][1] == v[1]
1566                  && subdivpolyvert[i][2] == v[2])
1567                         return i;
1568         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
1569                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
1570         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
1571         return subdivpolyverts++;
1572 }
1573
1574 static void SubdividePolygon(int numverts, float *verts)
1575 {
1576         int             i, i1, i2, i3, f, b, c, p;
1577         vec3_t  mins, maxs, front[256], back[256];
1578         float   m, *pv, *cv, dist[256], frac;
1579
1580         if (numverts > 250)
1581                 Host_Error("SubdividePolygon: ran out of verts in buffer");
1582
1583         BoundPoly(numverts, verts, mins, maxs);
1584
1585         for (i = 0;i < 3;i++)
1586         {
1587                 m = (mins[i] + maxs[i]) * 0.5;
1588                 m = r_subdivide_size.value * floor(m/r_subdivide_size.value + 0.5);
1589                 if (maxs[i] - m < 8)
1590                         continue;
1591                 if (m - mins[i] < 8)
1592                         continue;
1593
1594                 // cut it
1595                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
1596                         dist[c] = cv[i] - m;
1597
1598                 f = b = 0;
1599                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
1600                 {
1601                         if (dist[p] >= 0)
1602                         {
1603                                 VectorCopy(pv, front[f]);
1604                                 f++;
1605                         }
1606                         if (dist[p] <= 0)
1607                         {
1608                                 VectorCopy(pv, back[b]);
1609                                 b++;
1610                         }
1611                         if (dist[p] == 0 || dist[c] == 0)
1612                                 continue;
1613                         if ((dist[p] > 0) != (dist[c] > 0) )
1614                         {
1615                                 // clip point
1616                                 frac = dist[p] / (dist[p] - dist[c]);
1617                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
1618                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
1619                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
1620                                 f++;
1621                                 b++;
1622                         }
1623                 }
1624
1625                 SubdividePolygon(f, front[0]);
1626                 SubdividePolygon(b, back[0]);
1627                 return;
1628         }
1629
1630         i1 = subdivpolylookupvert(verts);
1631         i2 = subdivpolylookupvert(verts + 3);
1632         for (i = 2;i < numverts;i++)
1633         {
1634                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
1635                 {
1636                         Con_Printf("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
1637                         return;
1638                 }
1639
1640                 i3 = subdivpolylookupvert(verts + i * 3);
1641                 subdivpolyindex[subdivpolytriangles][0] = i1;
1642                 subdivpolyindex[subdivpolytriangles][1] = i2;
1643                 subdivpolyindex[subdivpolytriangles][2] = i3;
1644                 i2 = i3;
1645                 subdivpolytriangles++;
1646         }
1647 }
1648
1649 //Breaks a polygon up along axial 64 unit
1650 //boundaries so that turbulent and sky warps
1651 //can be done reasonably.
1652 static void Mod_Q1BSP_GenerateWarpMesh(msurface_t *surf)
1653 {
1654         int i, j;
1655         surfvertex_t *v;
1656         surfmesh_t *mesh;
1657
1658         subdivpolytriangles = 0;
1659         subdivpolyverts = 0;
1660         SubdividePolygon(surf->poly_numverts, surf->poly_verts);
1661         if (subdivpolytriangles < 1)
1662                 Host_Error("Mod_Q1BSP_GenerateWarpMesh: no triangles?\n");
1663
1664         surf->mesh = mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + subdivpolytriangles * sizeof(int[3]) + subdivpolyverts * sizeof(surfvertex_t));
1665         mesh->numverts = subdivpolyverts;
1666         mesh->numtriangles = subdivpolytriangles;
1667         mesh->vertex = (surfvertex_t *)(mesh + 1);
1668         mesh->index = (int *)(mesh->vertex + mesh->numverts);
1669         memset(mesh->vertex, 0, mesh->numverts * sizeof(surfvertex_t));
1670
1671         for (i = 0;i < mesh->numtriangles;i++)
1672                 for (j = 0;j < 3;j++)
1673                         mesh->index[i*3+j] = subdivpolyindex[i][j];
1674
1675         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
1676         {
1677                 VectorCopy(subdivpolyvert[i], v->v);
1678                 v->st[0] = DotProduct(v->v, surf->texinfo->vecs[0]);
1679                 v->st[1] = DotProduct(v->v, surf->texinfo->vecs[1]);
1680         }
1681 }
1682 #endif
1683
1684 static surfmesh_t *Mod_Q1BSP_AllocSurfMesh(int numverts, int numtriangles)
1685 {
1686         surfmesh_t *mesh;
1687         mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + numtriangles * sizeof(int[6]) + numverts * (3 + 2 + 2 + 2 + 3 + 3 + 3 + 1) * sizeof(float));
1688         mesh->numverts = numverts;
1689         mesh->numtriangles = numtriangles;
1690         mesh->vertex3f = (float *)(mesh + 1);
1691         mesh->texcoordtexture2f = mesh->vertex3f + mesh->numverts * 3;
1692         mesh->texcoordlightmap2f = mesh->texcoordtexture2f + mesh->numverts * 2;
1693         mesh->texcoorddetail2f = mesh->texcoordlightmap2f + mesh->numverts * 2;
1694         mesh->svector3f = (float *)(mesh->texcoorddetail2f + mesh->numverts * 2);
1695         mesh->tvector3f = mesh->svector3f + mesh->numverts * 3;
1696         mesh->normal3f = mesh->tvector3f + mesh->numverts * 3;
1697         mesh->lightmapoffsets = (int *)(mesh->normal3f + mesh->numverts * 3);
1698         mesh->element3i = mesh->lightmapoffsets + mesh->numverts;
1699         mesh->neighbor3i = mesh->element3i + mesh->numtriangles * 3;
1700         return mesh;
1701 }
1702
1703 static void Mod_Q1BSP_GenerateSurfacePolygon(msurface_t *surf, int firstedge, int numedges)
1704 {
1705         int i, lindex, j;
1706         float *vec, *vert, mins[3], maxs[3], val, *v;
1707         mtexinfo_t *tex;
1708
1709         // convert edges back to a normal polygon
1710         surf->poly_numverts = numedges;
1711         vert = surf->poly_verts = Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * numedges);
1712         for (i = 0;i < numedges;i++)
1713         {
1714                 lindex = loadmodel->brushq1.surfedges[firstedge + i];
1715                 if (lindex > 0)
1716                         vec = loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[lindex].v[0]].position;
1717                 else
1718                         vec = loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[-lindex].v[1]].position;
1719                 VectorCopy(vec, vert);
1720                 vert += 3;
1721         }
1722
1723         // calculate polygon bounding box and center
1724         vert = surf->poly_verts;
1725         VectorCopy(vert, mins);
1726         VectorCopy(vert, maxs);
1727         vert += 3;
1728         for (i = 1;i < surf->poly_numverts;i++, vert += 3)
1729         {
1730                 if (mins[0] > vert[0]) mins[0] = vert[0];if (maxs[0] < vert[0]) maxs[0] = vert[0];
1731                 if (mins[1] > vert[1]) mins[1] = vert[1];if (maxs[1] < vert[1]) maxs[1] = vert[1];
1732                 if (mins[2] > vert[2]) mins[2] = vert[2];if (maxs[2] < vert[2]) maxs[2] = vert[2];
1733         }
1734         VectorCopy(mins, surf->poly_mins);
1735         VectorCopy(maxs, surf->poly_maxs);
1736         surf->poly_center[0] = (mins[0] + maxs[0]) * 0.5f;
1737         surf->poly_center[1] = (mins[1] + maxs[1]) * 0.5f;
1738         surf->poly_center[2] = (mins[2] + maxs[2]) * 0.5f;
1739
1740         // generate surface extents information
1741         tex = surf->texinfo;
1742         mins[0] = maxs[0] = DotProduct(surf->poly_verts, tex->vecs[0]) + tex->vecs[0][3];
1743         mins[1] = maxs[1] = DotProduct(surf->poly_verts, tex->vecs[1]) + tex->vecs[1][3];
1744         for (i = 1, v = surf->poly_verts + 3;i < surf->poly_numverts;i++, v += 3)
1745         {
1746                 for (j = 0;j < 2;j++)
1747                 {
1748                         val = DotProduct(v, tex->vecs[j]) + tex->vecs[j][3];
1749                         if (mins[j] > val)
1750                                 mins[j] = val;
1751                         if (maxs[j] < val)
1752                                 maxs[j] = val;
1753                 }
1754         }
1755         for (i = 0;i < 2;i++)
1756         {
1757                 surf->texturemins[i] = (int) floor(mins[i] / 16) * 16;
1758                 surf->extents[i] = (int) ceil(maxs[i] / 16) * 16 - surf->texturemins[i];
1759         }
1760 }
1761
1762 static void Mod_Q1BSP_LoadFaces(lump_t *l)
1763 {
1764         dface_t *in;
1765         msurface_t *surf;
1766         int i, count, surfnum, planenum, ssize, tsize, firstedge, numedges, totalverts, totaltris, totalmeshes;
1767         surfmesh_t *mesh;
1768         float s, t;
1769
1770         in = (void *)(mod_base + l->fileofs);
1771         if (l->filelen % sizeof(*in))
1772                 Host_Error("Mod_Q1BSP_LoadFaces: funny lump size in %s",loadmodel->name);
1773         count = l->filelen / sizeof(*in);
1774         loadmodel->brushq1.surfaces = Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_t));
1775
1776         loadmodel->brushq1.numsurfaces = count;
1777         loadmodel->brushq1.surfacevisframes = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1778         loadmodel->brushq1.surfacepvsframes = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1779         loadmodel->brushq1.pvssurflist = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1780
1781         for (surfnum = 0, surf = loadmodel->brushq1.surfaces, totalverts = 0, totaltris = 0, totalmeshes = 0;surfnum < count;surfnum++, totalverts += surf->poly_numverts, totaltris += surf->poly_numverts - 2, totalmeshes++, in++, surf++)
1782         {
1783                 surf->number = surfnum;
1784                 // FIXME: validate edges, texinfo, etc?
1785                 firstedge = LittleLong(in->firstedge);
1786                 numedges = LittleShort(in->numedges);
1787                 if ((unsigned int) firstedge > (unsigned int) loadmodel->brushq1.numsurfedges || (unsigned int) numedges > (unsigned int) loadmodel->brushq1.numsurfedges || (unsigned int) firstedge + (unsigned int) numedges > (unsigned int) loadmodel->brushq1.numsurfedges)
1788                         Host_Error("Mod_Q1BSP_LoadFaces: invalid edge range (firstedge %i, numedges %i, model edges %i)\n", firstedge, numedges, loadmodel->brushq1.numsurfedges);
1789                 i = LittleShort(in->texinfo);
1790                 if ((unsigned int) i >= (unsigned int) loadmodel->brushq1.numtexinfo)
1791                         Host_Error("Mod_Q1BSP_LoadFaces: invalid texinfo index %i(model has %i texinfos)\n", i, loadmodel->brushq1.numtexinfo);
1792                 surf->texinfo = loadmodel->brushq1.texinfo + i;
1793                 surf->flags = surf->texinfo->texture->flags;
1794
1795                 planenum = LittleShort(in->planenum);
1796                 if ((unsigned int) planenum >= (unsigned int) loadmodel->brushq1.numplanes)
1797                         Host_Error("Mod_Q1BSP_LoadFaces: invalid plane index %i (model has %i planes)\n", planenum, loadmodel->brushq1.numplanes);
1798
1799                 if (LittleShort(in->side))
1800                         surf->flags |= SURF_PLANEBACK;
1801
1802                 surf->plane = loadmodel->brushq1.planes + planenum;
1803
1804                 // clear lightmap (filled in later)
1805                 surf->lightmaptexture = NULL;
1806
1807                 // force lightmap upload on first time seeing the surface
1808                 surf->cached_dlight = true;
1809
1810                 Mod_Q1BSP_GenerateSurfacePolygon(surf, firstedge, numedges);
1811
1812                 ssize = (surf->extents[0] >> 4) + 1;
1813                 tsize = (surf->extents[1] >> 4) + 1;
1814
1815                 // lighting info
1816                 for (i = 0;i < MAXLIGHTMAPS;i++)
1817                         surf->styles[i] = in->styles[i];
1818                 i = LittleLong(in->lightofs);
1819                 if (i == -1)
1820                         surf->samples = NULL;
1821                 else if (loadmodel->brushq1.ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
1822                         surf->samples = loadmodel->brushq1.lightdata + i;
1823                 else // LordHavoc: white lighting (bsp version 29)
1824                         surf->samples = loadmodel->brushq1.lightdata + (i * 3);
1825
1826                 if (surf->texinfo->texture->shader == &Cshader_wall_lightmap)
1827                 {
1828                         if ((surf->extents[0] >> 4) + 1 > (256) || (surf->extents[1] >> 4) + 1 > (256))
1829                                 Host_Error("Bad surface extents");
1830                         // stainmap for permanent marks on walls
1831                         surf->stainsamples = Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
1832                         // clear to white
1833                         memset(surf->stainsamples, 255, ssize * tsize * 3);
1834                 }
1835         }
1836
1837         loadmodel->brushq1.entiremesh = Mod_Q1BSP_AllocSurfMesh(totalverts, totaltris);
1838         loadmodel->brushq1.surfmeshes = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) * totalmeshes);
1839
1840         for (surfnum = 0, surf = loadmodel->brushq1.surfaces, totalverts = 0, totaltris = 0, totalmeshes = 0;surfnum < count;surfnum++, totalverts += surf->poly_numverts, totaltris += surf->poly_numverts - 2, totalmeshes++, surf++)
1841         {
1842                 mesh = surf->mesh = loadmodel->brushq1.surfmeshes + totalmeshes;
1843                 mesh->numverts = surf->poly_numverts;
1844                 mesh->numtriangles = surf->poly_numverts - 2;
1845                 mesh->vertex3f = loadmodel->brushq1.entiremesh->vertex3f + totalverts * 3;
1846                 mesh->texcoordtexture2f = loadmodel->brushq1.entiremesh->texcoordtexture2f + totalverts * 2;
1847                 mesh->texcoordlightmap2f = loadmodel->brushq1.entiremesh->texcoordlightmap2f + totalverts * 2;
1848                 mesh->texcoorddetail2f = loadmodel->brushq1.entiremesh->texcoorddetail2f + totalverts * 2;
1849                 mesh->svector3f = loadmodel->brushq1.entiremesh->svector3f + totalverts * 3;
1850                 mesh->tvector3f = loadmodel->brushq1.entiremesh->tvector3f + totalverts * 3;
1851                 mesh->normal3f = loadmodel->brushq1.entiremesh->normal3f + totalverts * 3;
1852                 mesh->lightmapoffsets = loadmodel->brushq1.entiremesh->lightmapoffsets + totalverts;
1853                 mesh->element3i = loadmodel->brushq1.entiremesh->element3i + totaltris * 3;
1854                 mesh->neighbor3i = loadmodel->brushq1.entiremesh->neighbor3i + totaltris * 3;
1855
1856                 surf->lightmaptexturestride = 0;
1857                 surf->lightmaptexture = NULL;
1858
1859                 for (i = 0;i < mesh->numverts;i++)
1860                 {
1861                         mesh->vertex3f[i * 3 + 0] = surf->poly_verts[i * 3 + 0];
1862                         mesh->vertex3f[i * 3 + 1] = surf->poly_verts[i * 3 + 1];
1863                         mesh->vertex3f[i * 3 + 2] = surf->poly_verts[i * 3 + 2];
1864                         s = DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3];
1865                         t = DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3];
1866                         mesh->texcoordtexture2f[i * 2 + 0] = s / surf->texinfo->texture->width;
1867                         mesh->texcoordtexture2f[i * 2 + 1] = t / surf->texinfo->texture->height;
1868                         mesh->texcoorddetail2f[i * 2 + 0] = s * (1.0f / 16.0f);
1869                         mesh->texcoorddetail2f[i * 2 + 1] = t * (1.0f / 16.0f);
1870                         mesh->texcoordlightmap2f[i * 2 + 0] = 0;
1871                         mesh->texcoordlightmap2f[i * 2 + 1] = 0;
1872                         mesh->lightmapoffsets[i] = 0;
1873                 }
1874
1875                 for (i = 0;i < mesh->numtriangles;i++)
1876                 {
1877                         mesh->element3i[i * 3 + 0] = 0;
1878                         mesh->element3i[i * 3 + 1] = i + 1;
1879                         mesh->element3i[i * 3 + 2] = i + 2;
1880                 }
1881
1882                 Mod_BuildTriangleNeighbors(mesh->neighbor3i, mesh->element3i, mesh->numtriangles);
1883                 Mod_BuildTextureVectorsAndNormals(mesh->numverts, mesh->numtriangles, mesh->vertex3f, mesh->texcoordtexture2f, mesh->element3i, mesh->svector3f, mesh->tvector3f, mesh->normal3f);
1884
1885                 if (surf->texinfo->texture->shader == &Cshader_wall_lightmap)
1886                 {
1887                         int i, iu, iv, smax, tmax;
1888                         float u, v, ubase, vbase, uscale, vscale;
1889
1890                         smax = surf->extents[0] >> 4;
1891                         tmax = surf->extents[1] >> 4;
1892
1893                         surf->flags |= SURF_LIGHTMAP;
1894                         if (r_miplightmaps.integer)
1895                         {
1896                                 surf->lightmaptexturestride = smax+1;
1897                                 surf->lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, NULL, surf->lightmaptexturestride, (surf->extents[1]>>4)+1, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_MIPMAP | TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
1898                         }
1899                         else
1900                         {
1901                                 surf->lightmaptexturestride = R_CompatibleFragmentWidth(smax+1, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, 0);
1902                                 surf->lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, NULL, surf->lightmaptexturestride, (surf->extents[1]>>4)+1, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FRAGMENT | TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
1903                         }
1904                         R_FragmentLocation(surf->lightmaptexture, NULL, NULL, &ubase, &vbase, &uscale, &vscale);
1905                         uscale = (uscale - ubase) / (smax + 1);
1906                         vscale = (vscale - vbase) / (tmax + 1);
1907
1908                         for (i = 0;i < mesh->numverts;i++)
1909                         {
1910                                 u = ((DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3]) + 8 - surf->texturemins[0]) * (1.0 / 16.0);
1911                                 v = ((DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3]) + 8 - surf->texturemins[1]) * (1.0 / 16.0);
1912                                 mesh->texcoordlightmap2f[i * 2 + 0] = u * uscale + ubase;
1913                                 mesh->texcoordlightmap2f[i * 2 + 1] = v * vscale + vbase;
1914                                 // LordHavoc: calc lightmap data offset for vertex lighting to use
1915                                 iu = (int) u;
1916                                 iv = (int) v;
1917                                 mesh->lightmapoffsets[i] = (bound(0, iv, tmax) * (smax+1) + bound(0, iu, smax)) * 3;
1918                         }
1919                 }
1920         }
1921 }
1922
1923 static void Mod_Q1BSP_SetParent(mnode_t *node, mnode_t *parent)
1924 {
1925         node->parent = parent;
1926         if (node->contents < 0)
1927                 return;
1928         Mod_Q1BSP_SetParent(node->children[0], node);
1929         Mod_Q1BSP_SetParent(node->children[1], node);
1930 }
1931
1932 static void Mod_Q1BSP_LoadNodes(lump_t *l)
1933 {
1934         int                     i, j, count, p;
1935         dnode_t         *in;
1936         mnode_t         *out;
1937
1938         in = (void *)(mod_base + l->fileofs);
1939         if (l->filelen % sizeof(*in))
1940                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
1941         count = l->filelen / sizeof(*in);
1942         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1943
1944         loadmodel->brushq1.nodes = out;
1945         loadmodel->brushq1.numnodes = count;
1946
1947         for ( i=0 ; i<count ; i++, in++, out++)
1948         {
1949                 for (j=0 ; j<3 ; j++)
1950                 {
1951                         out->mins[j] = LittleShort(in->mins[j]);
1952                         out->maxs[j] = LittleShort(in->maxs[j]);
1953                 }
1954
1955                 p = LittleLong(in->planenum);
1956                 out->plane = loadmodel->brushq1.planes + p;
1957
1958                 out->firstsurface = LittleShort(in->firstface);
1959                 out->numsurfaces = LittleShort(in->numfaces);
1960
1961                 for (j=0 ; j<2 ; j++)
1962                 {
1963                         p = LittleShort(in->children[j]);
1964                         if (p >= 0)
1965                                 out->children[j] = loadmodel->brushq1.nodes + p;
1966                         else
1967                                 out->children[j] = (mnode_t *)(loadmodel->brushq1.leafs + (-1 - p));
1968                 }
1969         }
1970
1971         Mod_Q1BSP_SetParent(loadmodel->brushq1.nodes, NULL);    // sets nodes and leafs
1972 }
1973
1974 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
1975 {
1976         dleaf_t         *in;
1977         mleaf_t         *out;
1978         int                     i, j, count, p;
1979
1980         in = (void *)(mod_base + l->fileofs);
1981         if (l->filelen % sizeof(*in))
1982                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
1983         count = l->filelen / sizeof(*in);
1984         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1985
1986         loadmodel->brushq1.leafs = out;
1987         loadmodel->brushq1.numleafs = count;
1988
1989         for ( i=0 ; i<count ; i++, in++, out++)
1990         {
1991                 for (j=0 ; j<3 ; j++)
1992                 {
1993                         out->mins[j] = LittleShort(in->mins[j]);
1994                         out->maxs[j] = LittleShort(in->maxs[j]);
1995                 }
1996
1997                 p = LittleLong(in->contents);
1998                 out->contents = p;
1999
2000                 out->firstmarksurface = loadmodel->brushq1.marksurfaces +
2001                         LittleShort(in->firstmarksurface);
2002                 out->nummarksurfaces = LittleShort(in->nummarksurfaces);
2003
2004                 p = LittleLong(in->visofs);
2005                 if (p == -1)
2006                         out->compressed_vis = NULL;
2007                 else
2008                         out->compressed_vis = loadmodel->brushq1.visdata + p;
2009
2010                 for (j=0 ; j<4 ; j++)
2011                         out->ambient_sound_level[j] = in->ambient_level[j];
2012
2013                 // FIXME: Insert caustics here
2014         }
2015 }
2016
2017 static void Mod_Q1BSP_LoadClipnodes(lump_t *l)
2018 {
2019         dclipnode_t *in, *out;
2020         int                     i, count;
2021         hull_t          *hull;
2022
2023         in = (void *)(mod_base + l->fileofs);
2024         if (l->filelen % sizeof(*in))
2025                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2026         count = l->filelen / sizeof(*in);
2027         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2028
2029         loadmodel->brushq1.clipnodes = out;
2030         loadmodel->brushq1.numclipnodes = count;
2031
2032         if (loadmodel->brushq1.ishlbsp)
2033         {
2034                 hull = &loadmodel->brushq1.hulls[1];
2035                 hull->clipnodes = out;
2036                 hull->firstclipnode = 0;
2037                 hull->lastclipnode = count-1;
2038                 hull->planes = loadmodel->brushq1.planes;
2039                 hull->clip_mins[0] = -16;
2040                 hull->clip_mins[1] = -16;
2041                 hull->clip_mins[2] = -36;
2042                 hull->clip_maxs[0] = 16;
2043                 hull->clip_maxs[1] = 16;
2044                 hull->clip_maxs[2] = 36;
2045                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2046
2047                 hull = &loadmodel->brushq1.hulls[2];
2048                 hull->clipnodes = out;
2049                 hull->firstclipnode = 0;
2050                 hull->lastclipnode = count-1;
2051                 hull->planes = loadmodel->brushq1.planes;
2052                 hull->clip_mins[0] = -32;
2053                 hull->clip_mins[1] = -32;
2054                 hull->clip_mins[2] = -32;
2055                 hull->clip_maxs[0] = 32;
2056                 hull->clip_maxs[1] = 32;
2057                 hull->clip_maxs[2] = 32;
2058                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2059
2060                 hull = &loadmodel->brushq1.hulls[3];
2061                 hull->clipnodes = out;
2062                 hull->firstclipnode = 0;
2063                 hull->lastclipnode = count-1;
2064                 hull->planes = loadmodel->brushq1.planes;
2065                 hull->clip_mins[0] = -16;
2066                 hull->clip_mins[1] = -16;
2067                 hull->clip_mins[2] = -18;
2068                 hull->clip_maxs[0] = 16;
2069                 hull->clip_maxs[1] = 16;
2070                 hull->clip_maxs[2] = 18;
2071                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2072         }
2073         else
2074         {
2075                 hull = &loadmodel->brushq1.hulls[1];
2076                 hull->clipnodes = out;
2077                 hull->firstclipnode = 0;
2078                 hull->lastclipnode = count-1;
2079                 hull->planes = loadmodel->brushq1.planes;
2080                 hull->clip_mins[0] = -16;
2081                 hull->clip_mins[1] = -16;
2082                 hull->clip_mins[2] = -24;
2083                 hull->clip_maxs[0] = 16;
2084                 hull->clip_maxs[1] = 16;
2085                 hull->clip_maxs[2] = 32;
2086                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2087
2088                 hull = &loadmodel->brushq1.hulls[2];
2089                 hull->clipnodes = out;
2090                 hull->firstclipnode = 0;
2091                 hull->lastclipnode = count-1;
2092                 hull->planes = loadmodel->brushq1.planes;
2093                 hull->clip_mins[0] = -32;
2094                 hull->clip_mins[1] = -32;
2095                 hull->clip_mins[2] = -24;
2096                 hull->clip_maxs[0] = 32;
2097                 hull->clip_maxs[1] = 32;
2098                 hull->clip_maxs[2] = 64;
2099                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2100         }
2101
2102         for (i=0 ; i<count ; i++, out++, in++)
2103         {
2104                 out->planenum = LittleLong(in->planenum);
2105                 out->children[0] = LittleShort(in->children[0]);
2106                 out->children[1] = LittleShort(in->children[1]);
2107                 if (out->children[0] >= count || out->children[1] >= count)
2108                         Host_Error("Corrupt clipping hull(out of range child)\n");
2109         }
2110 }
2111
2112 //Duplicate the drawing hull structure as a clipping hull
2113 static void Mod_Q1BSP_MakeHull0(void)
2114 {
2115         mnode_t         *in;
2116         dclipnode_t *out;
2117         int                     i;
2118         hull_t          *hull;
2119
2120         hull = &loadmodel->brushq1.hulls[0];
2121
2122         in = loadmodel->brushq1.nodes;
2123         out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numnodes * sizeof(dclipnode_t));
2124
2125         hull->clipnodes = out;
2126         hull->firstclipnode = 0;
2127         hull->lastclipnode = loadmodel->brushq1.numnodes - 1;
2128         hull->planes = loadmodel->brushq1.planes;
2129
2130         for (i = 0;i < loadmodel->brushq1.numnodes;i++, out++, in++)
2131         {
2132                 out->planenum = in->plane - loadmodel->brushq1.planes;
2133                 out->children[0] = in->children[0]->contents < 0 ? in->children[0]->contents : in->children[0] - loadmodel->brushq1.nodes;
2134                 out->children[1] = in->children[1]->contents < 0 ? in->children[1]->contents : in->children[1] - loadmodel->brushq1.nodes;
2135         }
2136 }
2137
2138 static void Mod_Q1BSP_LoadMarksurfaces(lump_t *l)
2139 {
2140         int i, j;
2141         short *in;
2142
2143         in = (void *)(mod_base + l->fileofs);
2144         if (l->filelen % sizeof(*in))
2145                 Host_Error("Mod_Q1BSP_LoadMarksurfaces: funny lump size in %s",loadmodel->name);
2146         loadmodel->brushq1.nummarksurfaces = l->filelen / sizeof(*in);
2147         loadmodel->brushq1.marksurfaces = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.nummarksurfaces * sizeof(int));
2148
2149         for (i = 0;i < loadmodel->brushq1.nummarksurfaces;i++)
2150         {
2151                 j = (unsigned) LittleShort(in[i]);
2152                 if (j >= loadmodel->brushq1.numsurfaces)
2153                         Host_Error("Mod_Q1BSP_LoadMarksurfaces: bad surface number");
2154                 loadmodel->brushq1.marksurfaces[i] = j;
2155         }
2156 }
2157
2158 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2159 {
2160         int             i;
2161         int             *in;
2162
2163         in = (void *)(mod_base + l->fileofs);
2164         if (l->filelen % sizeof(*in))
2165                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2166         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2167         loadmodel->brushq1.surfedges = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2168
2169         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2170                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2171 }
2172
2173
2174 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2175 {
2176         int                     i;
2177         mplane_t        *out;
2178         dplane_t        *in;
2179
2180         in = (void *)(mod_base + l->fileofs);
2181         if (l->filelen % sizeof(*in))
2182                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2183
2184         loadmodel->brushq1.numplanes = l->filelen / sizeof(*in);
2185         loadmodel->brushq1.planes = out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numplanes * sizeof(*out));
2186
2187         for (i = 0;i < loadmodel->brushq1.numplanes;i++, in++, out++)
2188         {
2189                 out->normal[0] = LittleFloat(in->normal[0]);
2190                 out->normal[1] = LittleFloat(in->normal[1]);
2191                 out->normal[2] = LittleFloat(in->normal[2]);
2192                 out->dist = LittleFloat(in->dist);
2193
2194                 PlaneClassify(out);
2195         }
2196 }
2197
2198 #define MAX_POINTS_ON_WINDING 64
2199
2200 typedef struct
2201 {
2202         int numpoints;
2203         int padding;
2204         double points[8][3]; // variable sized
2205 }
2206 winding_t;
2207
2208 /*
2209 ==================
2210 NewWinding
2211 ==================
2212 */
2213 static winding_t *NewWinding(int points)
2214 {
2215         winding_t *w;
2216         int size;
2217
2218         if (points > MAX_POINTS_ON_WINDING)
2219                 Sys_Error("NewWinding: too many points\n");
2220
2221         size = sizeof(winding_t) + sizeof(double[3]) * (points - 8);
2222         w = Mem_Alloc(loadmodel->mempool, size);
2223         memset(w, 0, size);
2224
2225         return w;
2226 }
2227
2228 static void FreeWinding(winding_t *w)
2229 {
2230         Mem_Free(w);
2231 }
2232
2233 /*
2234 =================
2235 BaseWindingForPlane
2236 =================
2237 */
2238 static winding_t *BaseWindingForPlane(mplane_t *p)
2239 {
2240         double org[3], vright[3], vup[3], normal[3];
2241         winding_t *w;
2242
2243         VectorCopy(p->normal, normal);
2244         VectorVectorsDouble(normal, vright, vup);
2245
2246         VectorScale(vup, 1024.0*1024.0*1024.0, vup);
2247         VectorScale(vright, 1024.0*1024.0*1024.0, vright);
2248
2249         // project a really big axis aligned box onto the plane
2250         w = NewWinding(4);
2251
2252         VectorScale(p->normal, p->dist, org);
2253
2254         VectorSubtract(org, vright, w->points[0]);
2255         VectorAdd(w->points[0], vup, w->points[0]);
2256
2257         VectorAdd(org, vright, w->points[1]);
2258         VectorAdd(w->points[1], vup, w->points[1]);
2259
2260         VectorAdd(org, vright, w->points[2]);
2261         VectorSubtract(w->points[2], vup, w->points[2]);
2262
2263         VectorSubtract(org, vright, w->points[3]);
2264         VectorSubtract(w->points[3], vup, w->points[3]);
2265
2266         w->numpoints = 4;
2267
2268         return w;
2269 }
2270
2271 /*
2272 ==================
2273 ClipWinding
2274
2275 Clips the winding to the plane, returning the new winding on the positive side
2276 Frees the input winding.
2277 If keepon is true, an exactly on-plane winding will be saved, otherwise
2278 it will be clipped away.
2279 ==================
2280 */
2281 static winding_t *ClipWinding(winding_t *in, mplane_t *split, int keepon)
2282 {
2283         double  dists[MAX_POINTS_ON_WINDING + 1];
2284         int             sides[MAX_POINTS_ON_WINDING + 1];
2285         int             counts[3];
2286         double  dot;
2287         int             i, j;
2288         double  *p1, *p2;
2289         double  mid[3];
2290         winding_t       *neww;
2291         int             maxpts;
2292
2293         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
2294
2295         // determine sides for each point
2296         for (i = 0;i < in->numpoints;i++)
2297         {
2298                 dists[i] = dot = DotProduct(in->points[i], split->normal) - split->dist;
2299                 if (dot > ON_EPSILON)
2300                         sides[i] = SIDE_FRONT;
2301                 else if (dot < -ON_EPSILON)
2302                         sides[i] = SIDE_BACK;
2303                 else
2304                         sides[i] = SIDE_ON;
2305                 counts[sides[i]]++;
2306         }
2307         sides[i] = sides[0];
2308         dists[i] = dists[0];
2309
2310         if (keepon && !counts[0] && !counts[1])
2311                 return in;
2312
2313         if (!counts[0])
2314         {
2315                 FreeWinding(in);
2316                 return NULL;
2317         }
2318         if (!counts[1])
2319                 return in;
2320
2321         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
2322         if (maxpts > MAX_POINTS_ON_WINDING)
2323                 Sys_Error("ClipWinding: maxpts > MAX_POINTS_ON_WINDING");
2324
2325         neww = NewWinding(maxpts);
2326
2327         for (i = 0;i < in->numpoints;i++)
2328         {
2329                 if (neww->numpoints >= maxpts)
2330                         Sys_Error("ClipWinding: points exceeded estimate");
2331
2332                 p1 = in->points[i];
2333
2334                 if (sides[i] == SIDE_ON)
2335                 {
2336                         VectorCopy(p1, neww->points[neww->numpoints]);
2337                         neww->numpoints++;
2338                         continue;
2339                 }
2340
2341                 if (sides[i] == SIDE_FRONT)
2342                 {
2343                         VectorCopy(p1, neww->points[neww->numpoints]);
2344                         neww->numpoints++;
2345                 }
2346
2347                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
2348                         continue;
2349
2350                 // generate a split point
2351                 p2 = in->points[(i+1)%in->numpoints];
2352
2353                 dot = dists[i] / (dists[i]-dists[i+1]);
2354                 for (j = 0;j < 3;j++)
2355                 {       // avoid round off error when possible
2356                         if (split->normal[j] == 1)
2357                                 mid[j] = split->dist;
2358                         else if (split->normal[j] == -1)
2359                                 mid[j] = -split->dist;
2360                         else
2361                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
2362                 }
2363
2364                 VectorCopy(mid, neww->points[neww->numpoints]);
2365                 neww->numpoints++;
2366         }
2367
2368         // free the original winding
2369         FreeWinding(in);
2370
2371         return neww;
2372 }
2373
2374
2375 /*
2376 ==================
2377 DivideWinding
2378
2379 Divides a winding by a plane, producing one or two windings.  The
2380 original winding is not damaged or freed.  If only on one side, the
2381 returned winding will be the input winding.  If on both sides, two
2382 new windings will be created.
2383 ==================
2384 */
2385 static void DivideWinding(winding_t *in, mplane_t *split, winding_t **front, winding_t **back)
2386 {
2387         double  dists[MAX_POINTS_ON_WINDING + 1];
2388         int             sides[MAX_POINTS_ON_WINDING + 1];
2389         int             counts[3];
2390         double  dot;
2391         int             i, j;
2392         double  *p1, *p2;
2393         double  mid[3];
2394         winding_t       *f, *b;
2395         int             maxpts;
2396
2397         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
2398
2399         // determine sides for each point
2400         for (i = 0;i < in->numpoints;i++)
2401         {
2402                 dot = DotProduct(in->points[i], split->normal);
2403                 dot -= split->dist;
2404                 dists[i] = dot;
2405                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
2406                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
2407                 else sides[i] = SIDE_ON;
2408                 counts[sides[i]]++;
2409         }
2410         sides[i] = sides[0];
2411         dists[i] = dists[0];
2412
2413         *front = *back = NULL;
2414
2415         if (!counts[0])
2416         {
2417                 *back = in;
2418                 return;
2419         }
2420         if (!counts[1])
2421         {
2422                 *front = in;
2423                 return;
2424         }
2425
2426         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
2427
2428         if (maxpts > MAX_POINTS_ON_WINDING)
2429                 Sys_Error("ClipWinding: maxpts > MAX_POINTS_ON_WINDING");
2430
2431         *front = f = NewWinding(maxpts);
2432         *back = b = NewWinding(maxpts);
2433
2434         for (i = 0;i < in->numpoints;i++)
2435         {
2436                 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
2437                         Sys_Error("DivideWinding: points exceeded estimate");
2438
2439                 p1 = in->points[i];
2440
2441                 if (sides[i] == SIDE_ON)
2442                 {
2443                         VectorCopy(p1, f->points[f->numpoints]);
2444                         f->numpoints++;
2445                         VectorCopy(p1, b->points[b->numpoints]);
2446                         b->numpoints++;
2447                         continue;
2448                 }
2449
2450                 if (sides[i] == SIDE_FRONT)
2451                 {
2452                         VectorCopy(p1, f->points[f->numpoints]);
2453                         f->numpoints++;
2454                 }
2455                 else if (sides[i] == SIDE_BACK)
2456                 {
2457                         VectorCopy(p1, b->points[b->numpoints]);
2458                         b->numpoints++;
2459                 }
2460
2461                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
2462                         continue;
2463
2464                 // generate a split point
2465                 p2 = in->points[(i+1)%in->numpoints];
2466
2467                 dot = dists[i] / (dists[i]-dists[i+1]);
2468                 for (j = 0;j < 3;j++)
2469                 {       // avoid round off error when possible
2470                         if (split->normal[j] == 1)
2471                                 mid[j] = split->dist;
2472                         else if (split->normal[j] == -1)
2473                                 mid[j] = -split->dist;
2474                         else
2475                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
2476                 }
2477
2478                 VectorCopy(mid, f->points[f->numpoints]);
2479                 f->numpoints++;
2480                 VectorCopy(mid, b->points[b->numpoints]);
2481                 b->numpoints++;
2482         }
2483 }
2484
2485 typedef struct portal_s
2486 {
2487         mplane_t plane;
2488         mnode_t *nodes[2];              // [0] = front side of plane
2489         struct portal_s *next[2];
2490         winding_t *winding;
2491         struct portal_s *chain; // all portals are linked into a list
2492 }
2493 portal_t;
2494
2495 static portal_t *portalchain;
2496
2497 /*
2498 ===========
2499 AllocPortal
2500 ===========
2501 */
2502 static portal_t *AllocPortal(void)
2503 {
2504         portal_t *p;
2505         p = Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2506         p->chain = portalchain;
2507         portalchain = p;
2508         return p;
2509 }
2510
2511 static void FreePortal(portal_t *p)
2512 {
2513         Mem_Free(p);
2514 }
2515
2516 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2517 {
2518         // calculate children first
2519         if (node->children[0]->contents >= 0)
2520                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2521         if (node->children[1]->contents >= 0)
2522                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2523
2524         // make combined bounding box from children
2525         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2526         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2527         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2528         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2529         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2530         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2531 }
2532
2533 static void Mod_Q1BSP_FinalizePortals(void)
2534 {
2535         int i, j, numportals, numpoints;
2536         portal_t *p, *pnext;
2537         mportal_t *portal;
2538         mvertex_t *point;
2539         mleaf_t *leaf, *endleaf;
2540         winding_t *w;
2541
2542         // recalculate bounding boxes for all leafs(because qbsp is very sloppy)
2543         leaf = loadmodel->brushq1.leafs;
2544         endleaf = leaf + loadmodel->brushq1.numleafs;
2545         for (;leaf < endleaf;leaf++)
2546         {
2547                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2548                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2549         }
2550         p = portalchain;
2551         while (p)
2552         {
2553                 if (p->winding)
2554                 {
2555                         for (i = 0;i < 2;i++)
2556                         {
2557                                 leaf = (mleaf_t *)p->nodes[i];
2558                                 w = p->winding;
2559                                 for (j = 0;j < w->numpoints;j++)
2560                                 {
2561                                         if (leaf->mins[0] > w->points[j][0]) leaf->mins[0] = w->points[j][0];
2562                                         if (leaf->mins[1] > w->points[j][1]) leaf->mins[1] = w->points[j][1];
2563                                         if (leaf->mins[2] > w->points[j][2]) leaf->mins[2] = w->points[j][2];
2564                                         if (leaf->maxs[0] < w->points[j][0]) leaf->maxs[0] = w->points[j][0];
2565                                         if (leaf->maxs[1] < w->points[j][1]) leaf->maxs[1] = w->points[j][1];
2566                                         if (leaf->maxs[2] < w->points[j][2]) leaf->maxs[2] = w->points[j][2];
2567                                 }
2568                         }
2569                 }
2570                 p = p->chain;
2571         }
2572
2573         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brushq1.nodes);
2574
2575         // tally up portal and point counts
2576         p = portalchain;
2577         numportals = 0;
2578         numpoints = 0;
2579         while (p)
2580         {
2581                 // note: this check must match the one below or it will usually corrupt memory
2582                 // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
2583                 if (p->winding && p->nodes[0] != p->nodes[1]
2584                  && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2585                  && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2586                 {
2587                         numportals += 2;
2588                         numpoints += p->winding->numpoints * 2;
2589                 }
2590                 p = p->chain;
2591         }
2592         loadmodel->brushq1.portals = Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2593         loadmodel->brushq1.numportals = numportals;
2594         loadmodel->brushq1.portalpoints = (void *)((qbyte *) loadmodel->brushq1.portals + numportals * sizeof(mportal_t));
2595         loadmodel->brushq1.numportalpoints = numpoints;
2596         // clear all leaf portal chains
2597         for (i = 0;i < loadmodel->brushq1.numleafs;i++)
2598                 loadmodel->brushq1.leafs[i].portals = NULL;
2599         // process all portals in the global portal chain, while freeing them
2600         portal = loadmodel->brushq1.portals;
2601         point = loadmodel->brushq1.portalpoints;
2602         p = portalchain;
2603         portalchain = NULL;
2604         while (p)
2605         {
2606                 pnext = p->chain;
2607
2608                 if (p->winding)
2609                 {
2610                         // note: this check must match the one above or it will usually corrupt memory
2611                         // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
2612                         if (p->nodes[0] != p->nodes[1]
2613                          && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2614                          && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2615                         {
2616                                 // first make the back to front portal(forward portal)
2617                                 portal->points = point;
2618                                 portal->numpoints = p->winding->numpoints;
2619                                 portal->plane.dist = p->plane.dist;
2620                                 VectorCopy(p->plane.normal, portal->plane.normal);
2621                                 portal->here = (mleaf_t *)p->nodes[1];
2622                                 portal->past = (mleaf_t *)p->nodes[0];
2623                                 // copy points
2624                                 for (j = 0;j < portal->numpoints;j++)
2625                                 {
2626                                         VectorCopy(p->winding->points[j], point->position);
2627                                         point++;
2628                                 }
2629                                 PlaneClassify(&portal->plane);
2630
2631                                 // link into leaf's portal chain
2632                                 portal->next = portal->here->portals;
2633                                 portal->here->portals = portal;
2634
2635                                 // advance to next portal
2636                                 portal++;
2637
2638                                 // then make the front to back portal(backward portal)
2639                                 portal->points = point;
2640                                 portal->numpoints = p->winding->numpoints;
2641                                 portal->plane.dist = -p->plane.dist;
2642                                 VectorNegate(p->plane.normal, portal->plane.normal);
2643                                 portal->here = (mleaf_t *)p->nodes[0];
2644                                 portal->past = (mleaf_t *)p->nodes[1];
2645                                 // copy points
2646                                 for (j = portal->numpoints - 1;j >= 0;j--)
2647                                 {
2648                                         VectorCopy(p->winding->points[j], point->position);
2649                                         point++;
2650                                 }
2651                                 PlaneClassify(&portal->plane);
2652
2653                                 // link into leaf's portal chain
2654                                 portal->next = portal->here->portals;
2655                                 portal->here->portals = portal;
2656
2657                                 // advance to next portal
2658                                 portal++;
2659                         }
2660                         FreeWinding(p->winding);
2661                 }
2662                 FreePortal(p);
2663                 p = pnext;
2664         }
2665 }
2666
2667 /*
2668 =============
2669 AddPortalToNodes
2670 =============
2671 */
2672 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2673 {
2674         if (!front)
2675                 Host_Error("AddPortalToNodes: NULL front node");
2676         if (!back)
2677                 Host_Error("AddPortalToNodes: NULL back node");
2678         if (p->nodes[0] || p->nodes[1])
2679                 Host_Error("AddPortalToNodes: already included");
2680         // note: front == back is handled gracefully, because leaf 0 is the shared solid leaf, it can often have portals with the same leaf on both sides
2681
2682         p->nodes[0] = front;
2683         p->next[0] = (portal_t *)front->portals;
2684         front->portals = (mportal_t *)p;
2685
2686         p->nodes[1] = back;
2687         p->next[1] = (portal_t *)back->portals;
2688         back->portals = (mportal_t *)p;
2689 }
2690
2691 /*
2692 =============
2693 RemovePortalFromNode
2694 =============
2695 */
2696 static void RemovePortalFromNodes(portal_t *portal)
2697 {
2698         int i;
2699         mnode_t *node;
2700         void **portalpointer;
2701         portal_t *t;
2702         for (i = 0;i < 2;i++)
2703         {
2704                 node = portal->nodes[i];
2705
2706                 portalpointer = (void **) &node->portals;
2707                 while (1)
2708                 {
2709                         t = *portalpointer;
2710                         if (!t)
2711                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2712
2713                         if (t == portal)
2714                         {
2715                                 if (portal->nodes[0] == node)
2716                                 {
2717                                         *portalpointer = portal->next[0];
2718                                         portal->nodes[0] = NULL;
2719                                 }
2720                                 else if (portal->nodes[1] == node)
2721                                 {
2722                                         *portalpointer = portal->next[1];
2723                                         portal->nodes[1] = NULL;
2724                                 }
2725                                 else
2726                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2727                                 break;
2728                         }
2729
2730                         if (t->nodes[0] == node)
2731                                 portalpointer = (void **) &t->next[0];
2732                         else if (t->nodes[1] == node)
2733                                 portalpointer = (void **) &t->next[1];
2734                         else
2735                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2736                 }
2737         }
2738 }
2739
2740 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2741 {
2742         int side;
2743         mnode_t *front, *back, *other_node;
2744         mplane_t clipplane, *plane;
2745         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2746         winding_t *nodeportalwinding, *frontwinding, *backwinding;
2747
2748         // if a leaf, we're done
2749         if (node->contents)
2750                 return;
2751
2752         plane = node->plane;
2753
2754         front = node->children[0];
2755         back = node->children[1];
2756         if (front == back)
2757                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2758
2759         // create the new portal by generating a polygon for the node plane,
2760         // and clipping it by all of the other portals(which came from nodes above this one)
2761         nodeportal = AllocPortal();
2762         nodeportal->plane = *node->plane;
2763
2764         nodeportalwinding = BaseWindingForPlane(node->plane);
2765         side = 0;       // shut up compiler warning
2766         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2767         {
2768                 clipplane = portal->plane;
2769                 if (portal->nodes[0] == portal->nodes[1])
2770                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2771                 if (portal->nodes[0] == node)
2772                         side = 0;
2773                 else if (portal->nodes[1] == node)
2774                 {
2775                         clipplane.dist = -clipplane.dist;
2776                         VectorNegate(clipplane.normal, clipplane.normal);
2777                         side = 1;
2778                 }
2779                 else
2780                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2781
2782                 nodeportalwinding = ClipWinding(nodeportalwinding, &clipplane, true);
2783                 if (!nodeportalwinding)
2784                 {
2785                         Con_Printf("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2786                         break;
2787                 }
2788         }
2789
2790         if (nodeportalwinding)
2791         {
2792                 // if the plane was not clipped on all sides, there was an error
2793                 nodeportal->winding = nodeportalwinding;
2794                 AddPortalToNodes(nodeportal, front, back);
2795         }
2796
2797         // split the portals of this node along this node's plane and assign them to the children of this node
2798         // (migrating the portals downward through the tree)
2799         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2800         {
2801                 if (portal->nodes[0] == portal->nodes[1])
2802                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2803                 if (portal->nodes[0] == node)
2804                         side = 0;
2805                 else if (portal->nodes[1] == node)
2806                         side = 1;
2807                 else
2808                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2809                 nextportal = portal->next[side];
2810
2811                 other_node = portal->nodes[!side];
2812                 RemovePortalFromNodes(portal);
2813
2814                 // cut the portal into two portals, one on each side of the node plane
2815                 DivideWinding(portal->winding, plane, &frontwinding, &backwinding);
2816
2817                 if (!frontwinding)
2818                 {
2819                         if (side == 0)
2820                                 AddPortalToNodes(portal, back, other_node);
2821                         else
2822                                 AddPortalToNodes(portal, other_node, back);
2823                         continue;
2824                 }
2825                 if (!backwinding)
2826                 {
2827                         if (side == 0)
2828                                 AddPortalToNodes(portal, front, other_node);
2829                         else
2830                                 AddPortalToNodes(portal, other_node, front);
2831                         continue;
2832                 }
2833
2834                 // the winding is split
2835                 splitportal = AllocPortal();
2836                 temp = splitportal->chain;
2837                 *splitportal = *portal;
2838                 splitportal->chain = temp;
2839                 splitportal->winding = backwinding;
2840                 FreeWinding(portal->winding);
2841                 portal->winding = frontwinding;
2842
2843                 if (side == 0)
2844                 {
2845                         AddPortalToNodes(portal, front, other_node);
2846                         AddPortalToNodes(splitportal, back, other_node);
2847                 }
2848                 else
2849                 {
2850                         AddPortalToNodes(portal, other_node, front);
2851                         AddPortalToNodes(splitportal, other_node, back);
2852                 }
2853         }
2854
2855         Mod_Q1BSP_RecursiveNodePortals(front);
2856         Mod_Q1BSP_RecursiveNodePortals(back);
2857 }
2858
2859
2860 static void Mod_Q1BSP_MakePortals(void)
2861 {
2862         portalchain = NULL;
2863         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brushq1.nodes);
2864         Mod_Q1BSP_FinalizePortals();
2865 }
2866
2867 static void Mod_Q1BSP_BuildSurfaceNeighbors(msurface_t *surfaces, int numsurfaces, mempool_t *mempool)
2868 {
2869 #if 0
2870         int surfnum, vertnum, vertnum2, snum, vnum, vnum2;
2871         msurface_t *surf, *s;
2872         float *v0, *v1, *v2, *v3;
2873         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2874                 surf->neighborsurfaces = Mem_Alloc(mempool, surf->poly_numverts * sizeof(msurface_t *));
2875         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2876         {
2877                 for (vertnum = surf->poly_numverts - 1, vertnum2 = 0, v0 = surf->poly_verts + (surf->poly_numverts - 1) * 3, v1 = surf->poly_verts;vertnum2 < surf->poly_numverts;vertnum = vertnum2, vertnum2++, v0 = v1, v1 += 3)
2878                 {
2879                         if (surf->neighborsurfaces[vertnum])
2880                                 continue;
2881                         surf->neighborsurfaces[vertnum] = NULL;
2882                         for (s = surfaces, snum = 0;snum < numsurfaces;s++, snum++)
2883                         {
2884                                 if (s->poly_mins[0] > (surf->poly_maxs[0] + 1) || s->poly_maxs[0] < (surf->poly_mins[0] - 1)
2885                                  || s->poly_mins[1] > (surf->poly_maxs[1] + 1) || s->poly_maxs[1] < (surf->poly_mins[1] - 1)
2886                                  || s->poly_mins[2] > (surf->poly_maxs[2] + 1) || s->poly_maxs[2] < (surf->poly_mins[2] - 1)
2887                                  || s == surf)
2888                                         continue;
2889                                 for (vnum = 0;vnum < s->poly_numverts;vnum++)
2890                                         if (s->neighborsurfaces[vnum] == surf)
2891                                                 break;
2892                                 if (vnum < s->poly_numverts)
2893                                         continue;
2894                                 for (vnum = s->poly_numverts - 1, vnum2 = 0, v2 = s->poly_verts + (s->poly_numverts - 1) * 3, v3 = s->poly_verts;vnum2 < s->poly_numverts;vnum = vnum2, vnum2++, v2 = v3, v3 += 3)
2895                                 {
2896                                         if (s->neighborsurfaces[vnum] == NULL
2897                                          && ((v0[0] == v2[0] && v0[1] == v2[1] && v0[2] == v2[2] && v1[0] == v3[0] && v1[1] == v3[1] && v1[2] == v3[2])
2898                                           || (v1[0] == v2[0] && v1[1] == v2[1] && v1[2] == v2[2] && v0[0] == v3[0] && v0[1] == v3[1] && v0[2] == v3[2])))
2899                                         {
2900                                                 surf->neighborsurfaces[vertnum] = s;
2901                                                 s->neighborsurfaces[vnum] = surf;
2902                                                 break;
2903                                         }
2904                                 }
2905                                 if (vnum < s->poly_numverts)
2906                                         break;
2907                         }
2908                 }
2909         }
2910 #endif
2911 }
2912
2913 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
2914 {
2915         int i, j, stylecounts[256], totalcount, remapstyles[256];
2916         msurface_t *surf;
2917         memset(stylecounts, 0, sizeof(stylecounts));
2918         for (i = 0;i < model->brushq1.nummodelsurfaces;i++)
2919         {
2920                 surf = model->brushq1.surfaces + model->brushq1.firstmodelsurface + i;
2921                 for (j = 0;j < MAXLIGHTMAPS;j++)
2922                         stylecounts[surf->styles[j]]++;
2923         }
2924         totalcount = 0;
2925         model->brushq1.light_styles = 0;
2926         for (i = 0;i < 255;i++)
2927  &nb