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