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