fixed Mod_Q3BSP_BoxTouchingPVS to handle unvised maps properly
[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 - model->brushq1.leafs - 1;
123                         if (clusterindex >= 0 && pvs[clusterindex >> 3] & (1 << (clusterindex & 7)))
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.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, pvschainbytes;
1978         qbyte *pvs;
1979
1980         in = (void *)(mod_base + l->fileofs);
1981         if (l->filelen % sizeof(*in))
1982                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
1983         count = l->filelen / sizeof(*in);
1984         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1985
1986         loadmodel->brushq1.leafs = out;
1987         loadmodel->brushq1.numleafs = count;
1988         // get visleafs from the submodel data
1989         pvschainbytes = (loadmodel->brushq1.submodels[0].visleafs+7)>>3;
1990         loadmodel->brushq1.data_decompressedpvs = pvs = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numleafs * pvschainbytes);
1991
1992         for ( i=0 ; i<count ; i++, in++, out++)
1993         {
1994                 for (j=0 ; j<3 ; j++)
1995                 {
1996                         out->mins[j] = LittleShort(in->mins[j]);
1997                         out->maxs[j] = LittleShort(in->maxs[j]);
1998                 }
1999
2000                 // FIXME: this function could really benefit from some error checking
2001
2002                 out->contents = LittleLong(in->contents);
2003
2004                 out->firstmarksurface = loadmodel->brushq1.marksurfaces + LittleShort(in->firstmarksurface);
2005                 out->nummarksurfaces = LittleShort(in->nummarksurfaces);
2006                 if (out->firstmarksurface < 0 || LittleShort(in->firstmarksurface) + out->nummarksurfaces > loadmodel->brushq1.nummarksurfaces)
2007                 {
2008                         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);
2009                         out->firstmarksurface = NULL;
2010                         out->nummarksurfaces = 0;
2011                 }
2012
2013                 out->pvsdata = pvs;
2014                 memset(out->pvsdata, 0xFF, pvschainbytes);
2015                 pvs += pvschainbytes;
2016
2017                 p = LittleLong(in->visofs);
2018                 if (p >= 0 && i > 0) // ignore visofs errors on leaf 0 (solid)
2019                 {
2020                         if (p >= loadmodel->brushq1.num_compressedpvs)
2021                                 Con_Printf("Mod_Q1BSP_LoadLeafs: invalid visofs\n");
2022                         else
2023                                 Mod_Q1BSP_DecompressVis(loadmodel->brushq1.data_compressedpvs + p, loadmodel->brushq1.data_compressedpvs + loadmodel->brushq1.num_compressedpvs, out->pvsdata, out->pvsdata + pvschainbytes);
2024                 }
2025
2026                 for (j = 0;j < 4;j++)
2027                         out->ambient_sound_level[j] = in->ambient_level[j];
2028
2029                 // FIXME: Insert caustics here
2030         }
2031 }
2032
2033 static void Mod_Q1BSP_LoadClipnodes(lump_t *l)
2034 {
2035         dclipnode_t *in, *out;
2036         int                     i, count;
2037         hull_t          *hull;
2038
2039         in = (void *)(mod_base + l->fileofs);
2040         if (l->filelen % sizeof(*in))
2041                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2042         count = l->filelen / sizeof(*in);
2043         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2044
2045         loadmodel->brushq1.clipnodes = out;
2046         loadmodel->brushq1.numclipnodes = count;
2047
2048         if (loadmodel->brush.ishlbsp)
2049         {
2050                 hull = &loadmodel->brushq1.hulls[1];
2051                 hull->clipnodes = out;
2052                 hull->firstclipnode = 0;
2053                 hull->lastclipnode = count-1;
2054                 hull->planes = loadmodel->brushq1.planes;
2055                 hull->clip_mins[0] = -16;
2056                 hull->clip_mins[1] = -16;
2057                 hull->clip_mins[2] = -36;
2058                 hull->clip_maxs[0] = 16;
2059                 hull->clip_maxs[1] = 16;
2060                 hull->clip_maxs[2] = 36;
2061                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2062
2063                 hull = &loadmodel->brushq1.hulls[2];
2064                 hull->clipnodes = out;
2065                 hull->firstclipnode = 0;
2066                 hull->lastclipnode = count-1;
2067                 hull->planes = loadmodel->brushq1.planes;
2068                 hull->clip_mins[0] = -32;
2069                 hull->clip_mins[1] = -32;
2070                 hull->clip_mins[2] = -32;
2071                 hull->clip_maxs[0] = 32;
2072                 hull->clip_maxs[1] = 32;
2073                 hull->clip_maxs[2] = 32;
2074                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2075
2076                 hull = &loadmodel->brushq1.hulls[3];
2077                 hull->clipnodes = out;
2078                 hull->firstclipnode = 0;
2079                 hull->lastclipnode = count-1;
2080                 hull->planes = loadmodel->brushq1.planes;
2081                 hull->clip_mins[0] = -16;
2082                 hull->clip_mins[1] = -16;
2083                 hull->clip_mins[2] = -18;
2084                 hull->clip_maxs[0] = 16;
2085                 hull->clip_maxs[1] = 16;
2086                 hull->clip_maxs[2] = 18;
2087                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2088         }
2089         else
2090         {
2091                 hull = &loadmodel->brushq1.hulls[1];
2092                 hull->clipnodes = out;
2093                 hull->firstclipnode = 0;
2094                 hull->lastclipnode = count-1;
2095                 hull->planes = loadmodel->brushq1.planes;
2096                 hull->clip_mins[0] = -16;
2097                 hull->clip_mins[1] = -16;
2098                 hull->clip_mins[2] = -24;
2099                 hull->clip_maxs[0] = 16;
2100                 hull->clip_maxs[1] = 16;
2101                 hull->clip_maxs[2] = 32;
2102                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2103
2104                 hull = &loadmodel->brushq1.hulls[2];
2105                 hull->clipnodes = out;
2106                 hull->firstclipnode = 0;
2107                 hull->lastclipnode = count-1;
2108                 hull->planes = loadmodel->brushq1.planes;
2109                 hull->clip_mins[0] = -32;
2110                 hull->clip_mins[1] = -32;
2111                 hull->clip_mins[2] = -24;
2112                 hull->clip_maxs[0] = 32;
2113                 hull->clip_maxs[1] = 32;
2114                 hull->clip_maxs[2] = 64;
2115                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2116         }
2117
2118         for (i=0 ; i<count ; i++, out++, in++)
2119         {
2120                 out->planenum = LittleLong(in->planenum);
2121                 out->children[0] = LittleShort(in->children[0]);
2122                 out->children[1] = LittleShort(in->children[1]);
2123                 if (out->children[0] >= count || out->children[1] >= count)
2124                         Host_Error("Corrupt clipping hull(out of range child)\n");
2125         }
2126 }
2127
2128 //Duplicate the drawing hull structure as a clipping hull
2129 static void Mod_Q1BSP_MakeHull0(void)
2130 {
2131         mnode_t         *in;
2132         dclipnode_t *out;
2133         int                     i;
2134         hull_t          *hull;
2135
2136         hull = &loadmodel->brushq1.hulls[0];
2137
2138         in = loadmodel->brushq1.nodes;
2139         out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numnodes * sizeof(dclipnode_t));
2140
2141         hull->clipnodes = out;
2142         hull->firstclipnode = 0;
2143         hull->lastclipnode = loadmodel->brushq1.numnodes - 1;
2144         hull->planes = loadmodel->brushq1.planes;
2145
2146         for (i = 0;i < loadmodel->brushq1.numnodes;i++, out++, in++)
2147         {
2148                 out->planenum = in->plane - loadmodel->brushq1.planes;
2149                 out->children[0] = in->children[0]->contents < 0 ? in->children[0]->contents : in->children[0] - loadmodel->brushq1.nodes;
2150                 out->children[1] = in->children[1]->contents < 0 ? in->children[1]->contents : in->children[1] - loadmodel->brushq1.nodes;
2151         }
2152 }
2153
2154 static void Mod_Q1BSP_LoadMarksurfaces(lump_t *l)
2155 {
2156         int i, j;
2157         short *in;
2158
2159         in = (void *)(mod_base + l->fileofs);
2160         if (l->filelen % sizeof(*in))
2161                 Host_Error("Mod_Q1BSP_LoadMarksurfaces: funny lump size in %s",loadmodel->name);
2162         loadmodel->brushq1.nummarksurfaces = l->filelen / sizeof(*in);
2163         loadmodel->brushq1.marksurfaces = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.nummarksurfaces * sizeof(int));
2164
2165         for (i = 0;i < loadmodel->brushq1.nummarksurfaces;i++)
2166         {
2167                 j = (unsigned) LittleShort(in[i]);
2168                 if (j >= loadmodel->brushq1.numsurfaces)
2169                         Host_Error("Mod_Q1BSP_LoadMarksurfaces: bad surface number");
2170                 loadmodel->brushq1.marksurfaces[i] = j;
2171         }
2172 }
2173
2174 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2175 {
2176         int             i;
2177         int             *in;
2178
2179         in = (void *)(mod_base + l->fileofs);
2180         if (l->filelen % sizeof(*in))
2181                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2182         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2183         loadmodel->brushq1.surfedges = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2184
2185         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2186                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2187 }
2188
2189
2190 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2191 {
2192         int                     i;
2193         mplane_t        *out;
2194         dplane_t        *in;
2195
2196         in = (void *)(mod_base + l->fileofs);
2197         if (l->filelen % sizeof(*in))
2198                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2199
2200         loadmodel->brushq1.numplanes = l->filelen / sizeof(*in);
2201         loadmodel->brushq1.planes = out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numplanes * sizeof(*out));
2202
2203         for (i = 0;i < loadmodel->brushq1.numplanes;i++, in++, out++)
2204         {
2205                 out->normal[0] = LittleFloat(in->normal[0]);
2206                 out->normal[1] = LittleFloat(in->normal[1]);
2207                 out->normal[2] = LittleFloat(in->normal[2]);
2208                 out->dist = LittleFloat(in->dist);
2209
2210                 PlaneClassify(out);
2211         }
2212 }
2213
2214 typedef struct portal_s
2215 {
2216         mplane_t plane;
2217         mnode_t *nodes[2];              // [0] = front side of plane
2218         struct portal_s *next[2];
2219         winding_t *winding;
2220         struct portal_s *chain; // all portals are linked into a list
2221 }
2222 portal_t;
2223
2224 static portal_t *portalchain;
2225
2226 /*
2227 ===========
2228 AllocPortal
2229 ===========
2230 */
2231 static portal_t *AllocPortal(void)
2232 {
2233         portal_t *p;
2234         p = Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2235         p->chain = portalchain;
2236         portalchain = p;
2237         return p;
2238 }
2239
2240 static void FreePortal(portal_t *p)
2241 {
2242         Mem_Free(p);
2243 }
2244
2245 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2246 {
2247         // calculate children first
2248         if (node->children[0]->contents >= 0)
2249                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2250         if (node->children[1]->contents >= 0)
2251                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2252
2253         // make combined bounding box from children
2254         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2255         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2256         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2257         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2258         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2259         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2260 }
2261
2262 static void Mod_Q1BSP_FinalizePortals(void)
2263 {
2264         int i, j, numportals, numpoints;
2265         portal_t *p, *pnext;
2266         mportal_t *portal;
2267         mvertex_t *point;
2268         mleaf_t *leaf, *endleaf;
2269         winding_t *w;
2270
2271         // recalculate bounding boxes for all leafs(because qbsp is very sloppy)
2272         leaf = loadmodel->brushq1.leafs;
2273         endleaf = leaf + loadmodel->brushq1.numleafs;
2274         for (;leaf < endleaf;leaf++)
2275         {
2276                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2277                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2278         }
2279         p = portalchain;
2280         while (p)
2281         {
2282                 if (p->winding)
2283                 {
2284                         for (i = 0;i < 2;i++)
2285                         {
2286                                 leaf = (mleaf_t *)p->nodes[i];
2287                                 w = p->winding;
2288                                 for (j = 0;j < w->numpoints;j++)
2289                                 {
2290                                         if (leaf->mins[0] > w->points[j][0]) leaf->mins[0] = w->points[j][0];
2291                                         if (leaf->mins[1] > w->points[j][1]) leaf->mins[1] = w->points[j][1];
2292                                         if (leaf->mins[2] > w->points[j][2]) leaf->mins[2] = w->points[j][2];
2293                                         if (leaf->maxs[0] < w->points[j][0]) leaf->maxs[0] = w->points[j][0];
2294                                         if (leaf->maxs[1] < w->points[j][1]) leaf->maxs[1] = w->points[j][1];
2295                                         if (leaf->maxs[2] < w->points[j][2]) leaf->maxs[2] = w->points[j][2];
2296                                 }
2297                         }
2298                 }
2299                 p = p->chain;
2300         }
2301
2302         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brushq1.nodes);
2303
2304         // tally up portal and point counts
2305         p = portalchain;
2306         numportals = 0;
2307         numpoints = 0;
2308         while (p)
2309         {
2310                 // note: this check must match the one below or it will usually corrupt memory
2311                 // 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
2312                 if (p->winding && p->nodes[0] != p->nodes[1]
2313                  && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2314                  && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2315                 {
2316                         numportals += 2;
2317                         numpoints += p->winding->numpoints * 2;
2318                 }
2319                 p = p->chain;
2320         }
2321         loadmodel->brushq1.portals = Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2322         loadmodel->brushq1.numportals = numportals;
2323         loadmodel->brushq1.portalpoints = (void *)((qbyte *) loadmodel->brushq1.portals + numportals * sizeof(mportal_t));
2324         loadmodel->brushq1.numportalpoints = numpoints;
2325         // clear all leaf portal chains
2326         for (i = 0;i < loadmodel->brushq1.numleafs;i++)
2327                 loadmodel->brushq1.leafs[i].portals = NULL;
2328         // process all portals in the global portal chain, while freeing them
2329         portal = loadmodel->brushq1.portals;
2330         point = loadmodel->brushq1.portalpoints;
2331         p = portalchain;
2332         portalchain = NULL;
2333         while (p)
2334         {
2335                 pnext = p->chain;
2336
2337                 if (p->winding)
2338                 {
2339                         // note: this check must match the one above or it will usually corrupt memory
2340                         // 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
2341                         if (p->nodes[0] != p->nodes[1]
2342                          && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2343                          && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2344                         {
2345                                 // first make the back to front portal(forward portal)
2346                                 portal->points = point;
2347                                 portal->numpoints = p->winding->numpoints;
2348                                 portal->plane.dist = p->plane.dist;
2349                                 VectorCopy(p->plane.normal, portal->plane.normal);
2350                                 portal->here = (mleaf_t *)p->nodes[1];
2351                                 portal->past = (mleaf_t *)p->nodes[0];
2352                                 // copy points
2353                                 for (j = 0;j < portal->numpoints;j++)
2354                                 {
2355                                         VectorCopy(p->winding->points[j], point->position);
2356                                         point++;
2357                                 }
2358                                 PlaneClassify(&portal->plane);
2359
2360                                 // link into leaf's portal chain
2361                                 portal->next = portal->here->portals;
2362                                 portal->here->portals = portal;
2363
2364                                 // advance to next portal
2365                                 portal++;
2366
2367                                 // then make the front to back portal(backward portal)
2368                                 portal->points = point;
2369                                 portal->numpoints = p->winding->numpoints;
2370                                 portal->plane.dist = -p->plane.dist;
2371                                 VectorNegate(p->plane.normal, portal->plane.normal);
2372                                 portal->here = (mleaf_t *)p->nodes[0];
2373                                 portal->past = (mleaf_t *)p->nodes[1];
2374                                 // copy points
2375                                 for (j = portal->numpoints - 1;j >= 0;j--)
2376                                 {
2377                                         VectorCopy(p->winding->points[j], point->position);
2378                                         point++;
2379                                 }
2380                                 PlaneClassify(&portal->plane);
2381
2382                                 // link into leaf's portal chain
2383                                 portal->next = portal->here->portals;
2384                                 portal->here->portals = portal;
2385
2386                                 // advance to next portal
2387                                 portal++;
2388                         }
2389                         Winding_Free(p->winding);
2390                 }
2391                 FreePortal(p);
2392                 p = pnext;
2393         }
2394 }
2395
2396 /*
2397 =============
2398 AddPortalToNodes
2399 =============
2400 */
2401 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2402 {
2403         if (!front)
2404                 Host_Error("AddPortalToNodes: NULL front node");
2405         if (!back)
2406                 Host_Error("AddPortalToNodes: NULL back node");
2407         if (p->nodes[0] || p->nodes[1])
2408                 Host_Error("AddPortalToNodes: already included");
2409         // 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
2410
2411         p->nodes[0] = front;
2412         p->next[0] = (portal_t *)front->portals;
2413         front->portals = (mportal_t *)p;
2414
2415         p->nodes[1] = back;
2416         p->next[1] = (portal_t *)back->portals;
2417         back->portals = (mportal_t *)p;
2418 }
2419
2420 /*
2421 =============
2422 RemovePortalFromNode
2423 =============
2424 */
2425 static void RemovePortalFromNodes(portal_t *portal)
2426 {
2427         int i;
2428         mnode_t *node;
2429         void **portalpointer;
2430         portal_t *t;
2431         for (i = 0;i < 2;i++)
2432         {
2433                 node = portal->nodes[i];
2434
2435                 portalpointer = (void **) &node->portals;
2436                 while (1)
2437                 {
2438                         t = *portalpointer;
2439                         if (!t)
2440                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2441
2442                         if (t == portal)
2443                         {
2444                                 if (portal->nodes[0] == node)
2445                                 {
2446                                         *portalpointer = portal->next[0];
2447                                         portal->nodes[0] = NULL;
2448                                 }
2449                                 else if (portal->nodes[1] == node)
2450                                 {
2451                                         *portalpointer = portal->next[1];
2452                                         portal->nodes[1] = NULL;
2453                                 }
2454                                 else
2455                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2456                                 break;
2457                         }
2458
2459                         if (t->nodes[0] == node)
2460                                 portalpointer = (void **) &t->next[0];
2461                         else if (t->nodes[1] == node)
2462                                 portalpointer = (void **) &t->next[1];
2463                         else
2464                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2465                 }
2466         }
2467 }
2468
2469 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2470 {
2471         int side;
2472         mnode_t *front, *back, *other_node;
2473         mplane_t clipplane, *plane;
2474         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2475         winding_t *nodeportalwinding, *frontwinding, *backwinding;
2476
2477         // if a leaf, we're done
2478         if (node->contents)
2479                 return;
2480
2481         plane = node->plane;
2482
2483         front = node->children[0];
2484         back = node->children[1];
2485         if (front == back)
2486                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2487
2488         // create the new portal by generating a polygon for the node plane,
2489         // and clipping it by all of the other portals(which came from nodes above this one)
2490         nodeportal = AllocPortal();
2491         nodeportal->plane = *plane;
2492
2493         nodeportalwinding = Winding_NewFromPlane(nodeportal->plane.normal[0], nodeportal->plane.normal[1], nodeportal->plane.normal[2], nodeportal->plane.dist);
2494         side = 0;       // shut up compiler warning
2495         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2496         {
2497                 clipplane = portal->plane;
2498                 if (portal->nodes[0] == portal->nodes[1])
2499                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2500                 if (portal->nodes[0] == node)
2501                         side = 0;
2502                 else if (portal->nodes[1] == node)
2503                 {
2504                         clipplane.dist = -clipplane.dist;
2505                         VectorNegate(clipplane.normal, clipplane.normal);
2506                         side = 1;
2507                 }
2508                 else
2509                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2510
2511                 nodeportalwinding = Winding_Clip(nodeportalwinding, clipplane.normal[0], clipplane.normal[1], clipplane.normal[2], clipplane.dist, true);
2512                 if (!nodeportalwinding)
2513                 {
2514                         Con_Printf("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2515                         break;
2516                 }
2517         }
2518
2519         if (nodeportalwinding)
2520         {
2521                 // if the plane was not clipped on all sides, there was an error
2522                 nodeportal->winding = nodeportalwinding;
2523                 AddPortalToNodes(nodeportal, front, back);
2524         }
2525
2526         // split the portals of this node along this node's plane and assign them to the children of this node
2527         // (migrating the portals downward through the tree)
2528         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2529         {
2530                 if (portal->nodes[0] == portal->nodes[1])
2531                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2532                 if (portal->nodes[0] == node)
2533                         side = 0;
2534                 else if (portal->nodes[1] == node)
2535                         side = 1;
2536                 else
2537                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2538                 nextportal = portal->next[side];
2539
2540                 other_node = portal->nodes[!side];
2541                 RemovePortalFromNodes(portal);
2542
2543                 // cut the portal into two portals, one on each side of the node plane
2544                 Winding_Divide(portal->winding, plane->normal[0], plane->normal[1], plane->normal[2], plane->dist, &frontwinding, &backwinding);
2545
2546                 if (!frontwinding)
2547                 {
2548                         if (side == 0)
2549                                 AddPortalToNodes(portal, back, other_node);
2550                         else
2551                                 AddPortalToNodes(portal, other_node, back);
2552                         continue;
2553                 }
2554                 if (!backwinding)
2555                 {
2556                         if (side == 0)
2557                                 AddPortalToNodes(portal, front, other_node);
2558                         else
2559                                 AddPortalToNodes(portal, other_node, front);
2560                         continue;
2561                 }
2562
2563                 // the winding is split
2564                 splitportal = AllocPortal();
2565                 temp = splitportal->chain;
2566                 *splitportal = *portal;
2567                 splitportal->chain = temp;
2568                 splitportal->winding = backwinding;
2569                 Winding_Free(portal->winding);
2570                 portal->winding = frontwinding;
2571
2572                 if (side == 0)
2573                 {
2574                         AddPortalToNodes(portal, front, other_node);
2575                         AddPortalToNodes(splitportal, back, other_node);
2576                 }
2577                 else
2578                 {
2579                         AddPortalToNodes(portal, other_node, front);
2580                         AddPortalToNodes(splitportal, other_node, back);
2581                 }
2582         }
2583
2584         Mod_Q1BSP_RecursiveNodePortals(front);
2585         Mod_Q1BSP_RecursiveNodePortals(back);
2586 }
2587
2588 static void Mod_Q1BSP_MakePortals(void)
2589 {
2590         portalchain = NULL;
2591         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brushq1.nodes);
2592         Mod_Q1BSP_FinalizePortals();
2593 }
2594
2595 static void Mod_Q1BSP_BuildSurfaceNeighbors(msurface_t *surfaces, int numsurfaces, mempool_t *mempool)
2596 {
2597 #if 0
2598         int surfnum, vertnum, vertnum2, snum, vnum, vnum2;
2599         msurface_t *surf, *s;
2600         float *v0, *v1, *v2, *v3;
2601         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2602                 surf->neighborsurfaces = Mem_Alloc(mempool, surf->poly_numverts * sizeof(msurface_t *));
2603         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2604         {
2605                 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)
2606                 {
2607                         if (surf->neighborsurfaces[vertnum])
2608                                 continue;
2609                         surf->neighborsurfaces[vertnum] = NULL;
2610                         for (s = surfaces, snum = 0;snum < numsurfaces;s++, snum++)
2611                         {
2612                                 if (s->poly_mins[0] > (surf->poly_maxs[0] + 1) || s->poly_maxs[0] < (surf->poly_mins[0] - 1)
2613                                  || s->poly_mins[1] > (surf->poly_maxs[1] + 1) || s->poly_maxs[1] < (surf->poly_mins[1] - 1)
2614                                  || s->poly_mins[2] > (surf->poly_maxs[2] + 1) || s->poly_maxs[2] < (surf->poly_mins[2] - 1)
2615                                  || s == surf)
2616                                         continue;
2617                                 for (vnum = 0;vnum < s->poly_numverts;vnum++)
2618                                         if (s->neighborsurfaces[vnum] == surf)
2619                                                 break;
2620                                 if (vnum < s->poly_numverts)
2621                                         continue;
2622                                 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)
2623                                 {
2624                                         if (s->neighborsurfaces[vnum] == NULL
2625                                          && ((v0[0] == v2[0] && v0[1] == v2[1] && v0[2] == v2[2] && v1[0] == v3[0] && v1[1] == v3[1] && v1[2] == v3[2])
2626                                           || (v1[0] == v2[0] && v1[1] == v2[1] && v1[2] == v2[2] && v0[0] == v3[0] && v0[1] == v3[1] && v0[2] == v3[2])))
2627                                         {
2628                                                 surf->neighborsurfaces[vertnum] = s;
2629                                                 s->neighborsurfaces[vnum] = surf;
2630                                                 break;
2631                                         }
2632                                 }
2633                                 if (vnum < s->poly_numverts)
2634                                         break;
2635                         }
2636                 }
2637         }
2638 #endif
2639 }
2640
2641 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
2642 {
2643         int i, j, stylecounts[256], totalcount, remapstyles[256];
2644         msurface_t *surf;
2645         memset(stylecounts, 0, sizeof(stylecounts));
2646         for (i = 0;i < model->brushq1.nummodelsurfaces;i++)
2647         {
2648                 surf = model->brushq1.surfaces + model->brushq1.firstmodelsurface + i;
2649                 for (j = 0;j < MAXLIGHTMAPS;j++)
2650                         stylecounts[surf->styles[j]]++;
2651         }
2652         totalcount = 0;
2653         model->brushq1.light_styles = 0;
2654         for (i = 0;i < 255;i++)
2655         {
2656                 if (stylecounts[i])
2657                 {
2658                         remapstyles[i] = model->brushq1.light_styles++;
2659                         totalcount += stylecounts[i] + 1;
2660                 }
2661         }
2662         if (!totalcount)
2663                 return;
2664         model->brushq1.light_style = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(qbyte));
2665         model->brushq1.light_stylevalue = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(int));
2666         model->brushq1.light_styleupdatechains = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(msurface_t **));
2667         model->brushq1.light_styleupdatechainsbuffer = Mem_Alloc(mempool, totalcount * sizeof(msurface_t *));
2668         model->brushq1.light_styles = 0;
2669         for (i = 0;i < 255;i++)
2670                 if (stylecounts[i])
2671                         model->brushq1.light_style[model->brushq1.light_styles++] = i;
2672         j = 0;
2673         for (i = 0;i < model->brushq1.light_styles;i++)
2674         {
2675                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2676                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2677         }
2678         for (i = 0;i < model->brushq1.nummodelsurfaces;i++)
2679         {
2680                 surf = model->brushq1.surfaces + model->brushq1.firstmodelsurface + i;
2681                 for (j = 0;j < MAXLIGHTMAPS;j++)
2682                         if (surf->styles[j] != 255)
2683                                 *model->brushq1.light_styleupdatechains[remapstyles[surf->styles[j]]]++ = surf;
2684         }
2685         j = 0;
2686         for (i = 0;i < model->brushq1.light_styles;i++)
2687         {
2688                 *model->brushq1.light_styleupdatechains[i] = NULL;
2689                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2690                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2691         }
2692 }
2693
2694 static void Mod_Q1BSP_BuildPVSTextureChains(model_t *model)
2695 {
2696         int i, j;
2697         for (i = 0;i < model->brushq1.numtextures;i++)
2698                 model->brushq1.pvstexturechainslength[i] = 0;
2699         for (i = 0, j = model->brushq1.firstmodelsurface;i < model->brushq1.nummodelsurfaces;i++, j++)
2700         {
2701                 if (model->brushq1.surfacepvsframes[j] == model->brushq1.pvsframecount)
2702                 {
2703                         model->brushq1.pvssurflist[model->brushq1.pvssurflistlength++] = j;
2704                         model->brushq1.pvstexturechainslength[model->brushq1.surfaces[j].texinfo->texture->number]++;
2705                 }
2706         }
2707         for (i = 0, j = 0;i < model->brushq1.numtextures;i++)
2708         {
2709                 if (model->brushq1.pvstexturechainslength[i])
2710                 {
2711                         model->brushq1.pvstexturechains[i] = model->brushq1.pvstexturechainsbuffer + j;
2712                         j += model->brushq1.pvstexturechainslength[i] + 1;
2713                 }
2714                 else
2715                         model->brushq1.pvstexturechains[i] = NULL;
2716         }
2717         for (i = 0, j = model->brushq1.firstmodelsurface;i < model->brushq1.nummodelsurfaces;i++, j++)
2718                 if (model->brushq1.surfacepvsframes[j] == model->brushq1.pvsframecount)
2719                         *model->brushq1.pvstexturechains[model->brushq1.surfaces[j].texinfo->texture->number]++ = model->brushq1.surfaces + j;
2720         for (i = 0;i < model->brushq1.numtextures;i++)
2721         {
2722                 if (model->brushq1.pvstexturechainslength[i])
2723                 {
2724                         *model->brushq1.pvstexturechains[i] = NULL;
2725                         model->brushq1.pvstexturechains[i] -= model->brushq1.pvstexturechainslength[i];
2726                 }
2727         }
2728 }
2729
2730 static void Mod_Q1BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbytes, mnode_t *node)
2731 {
2732         int i;
2733         float d;
2734
2735         while (node->contents >= 0)
2736         {
2737                 d = PlaneDiff(org, node->plane);
2738                 if (d > radius)
2739                         node = node->children[0];
2740                 else if (d < -radius)
2741                         node = node->children[1];
2742                 else
2743                 {
2744                         // go down both sides
2745                         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
2746                         node = node->children[1];
2747                 }
2748         }
2749         // FIXME: code!
2750         // if this is a leaf, accumulate the pvs bits
2751         if (/*node->contents != CONTENTS_SOLID && */((mleaf_t *)node)->pvsdata)
2752                 for (i = 0;i < pvsbytes;i++)
2753                         pvsbuffer[i] |= ((mleaf_t *)node)->pvsdata[i];
2754 }
2755
2756 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
2757 //of the given point.
2758 static int Mod_Q1BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbufferlength)
2759 {
2760         int bytes = ((model->brushq1.numleafs - 1) + 7) >> 3;
2761         bytes = min(bytes, pvsbufferlength);
2762         if (r_novis.integer)
2763         {
2764                 memset(pvsbuffer, 0xFF, bytes);
2765                 return bytes;
2766         }
2767         memset(pvsbuffer, 0, bytes);
2768         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brushq1.nodes);
2769         return bytes;
2770 }
2771
2772 //Returns PVS data for a given point
2773 //(note: always returns valid data, never NULL)
2774 static qbyte *Mod_Q1BSP_GetPVS(model_t *model, const vec3_t p)
2775 {
2776         mnode_t *node;
2777         Mod_CheckLoaded(model);
2778         // LordHavoc: modified to start at first clip node,
2779         // in other words: first node of the (sub)model
2780         node = model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode;
2781         while (node->contents == 0)
2782                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
2783         return ((mleaf_t *)node)->pvsdata;
2784 }
2785
2786 static void Mod_Q1BSP_RoundUpToHullSize(model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
2787 {
2788         vec3_t size;
2789         const hull_t *hull;
2790
2791         VectorSubtract(inmaxs, inmins, size);
2792         if (cmodel->brush.ishlbsp)
2793         {
2794                 if (size[0] < 3)
2795                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
2796                 else if (size[0] <= 32)
2797                 {
2798                         if (size[2] < 54) // pick the nearest of 36 or 72
2799                                 hull = &cmodel->brushq1.hulls[3]; // 32x32x36
2800                         else
2801                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
2802                 }
2803                 else
2804                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
2805         }
2806         else
2807         {
2808                 if (size[0] < 3)
2809                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
2810                 else if (size[0] <= 32)
2811                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
2812                 else
2813                         hull = &cmodel->brushq1.hulls[2]; // 64x64x88
2814         }
2815         VectorCopy(inmins, outmins);
2816         VectorAdd(inmins, hull->clip_size, outmaxs);
2817 }
2818
2819 extern void R_Model_Brush_DrawSky(entity_render_t *ent);
2820 extern void R_Model_Brush_Draw(entity_render_t *ent);
2821 extern void R_Model_Brush_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin, float lightradius);
2822 extern void R_Model_Brush_DrawLight(entity_render_t *ent, vec3_t relativelightorigin, vec3_t relativeeyeorigin, float lightradius, float *lightcolor, const matrix4x4_t *matrix_modeltofilter, const matrix4x4_t *matrix_modeltoattenuationxyz, const matrix4x4_t *matrix_modeltoattenuationz);
2823 void Mod_Q1BSP_Load(model_t *mod, void *buffer)
2824 {
2825         int i, j, k;
2826         dheader_t *header;
2827         dmodel_t *bm;
2828         mempool_t *mainmempool;
2829         char *loadname;
2830         model_t *originalloadmodel;
2831         float dist, modelyawradius, modelradius, *vec;
2832         msurface_t *surf;
2833
2834         mod->type = mod_brush;
2835
2836         header = (dheader_t *)buffer;
2837
2838         i = LittleLong(header->version);
2839         if (i != BSPVERSION && i != 30)
2840                 Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i(Quake) or 30(HalfLife))", mod->name, i, BSPVERSION);
2841         mod->brush.ishlbsp = i == 30;
2842
2843         mod->soundfromcenter = true;
2844         mod->TraceBox = Mod_Q1BSP_TraceBox;
2845         mod->brush.SuperContentsFromNativeContents = Mod_Q1BSP_SuperContentsFromNativeContents;
2846         mod->brush.NativeContentsFromSuperContents = Mod_Q1BSP_NativeContentsFromSuperContents;
2847         mod->brush.GetPVS = Mod_Q1BSP_GetPVS;
2848         mod->brush.FatPVS = Mod_Q1BSP_FatPVS;
2849         mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
2850         mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
2851         mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
2852         mod->brush.AmbientSoundLevelsForPoint = Mod_Q1BSP_AmbientSoundLevelsForPoint;
2853         mod->brush.RoundUpToHullSize = Mod_Q1BSP_RoundUpToHullSize;
2854         mod->brushq1.PointInLeaf = Mod_Q1BSP_PointInLeaf;
2855         mod->brushq1.BuildPVSTextureChains = Mod_Q1BSP_BuildPVSTextureChains;
2856
2857         if (loadmodel->isworldmodel)
2858         {
2859                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
2860                 // until we get a texture for it...
2861                 R_ResetQuakeSky();
2862         }
2863
2864 // swap all the lumps
2865         mod_base = (qbyte *)header;
2866
2867         for (i = 0;i < (int) sizeof(dheader_t) / 4;i++)
2868                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
2869
2870 // load into heap
2871
2872         // store which lightmap format to use
2873         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
2874
2875         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
2876         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
2877         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
2878         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
2879         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
2880         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
2881         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
2882         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
2883         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
2884         Mod_Q1BSP_LoadMarksurfaces(&header->lumps[LUMP_MARKSURFACES]);
2885         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
2886         // load submodels before leafs because they contain the number of vis leafs
2887         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS]);
2888         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
2889         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
2890         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES]);
2891
2892         if (mod->brushq1.data_compressedpvs)
2893                 Mem_Free(mod->brushq1.data_compressedpvs);
2894         mod->brushq1.data_compressedpvs = NULL;
2895         mod->brushq1.num_compressedpvs = 0;
2896
2897         Mod_Q1BSP_MakeHull0();
2898         Mod_Q1BSP_MakePortals();
2899
2900         mod->numframes = 2;             // regular and alternate animation
2901
2902         mainmempool = mod->mempool;
2903         loadname = mod->name;
2904
2905         Mod_Q1BSP_LoadLightList();
2906         originalloadmodel = loadmodel;
2907
2908 //
2909 // set up the submodels(FIXME: this is confusing)
2910 //
2911         for (i = 0;i < mod->brush.numsubmodels;i++)
2912         {
2913                 bm = &mod->brushq1.submodels[i];
2914
2915                 mod->brushq1.hulls[0].firstclipnode = bm->headnode[0];
2916                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
2917                 {
2918                         mod->brushq1.hulls[j].firstclipnode = bm->headnode[j];
2919                         mod->brushq1.hulls[j].lastclipnode = mod->brushq1.numclipnodes - 1;
2920                 }
2921
2922                 mod->brushq1.firstmodelsurface = bm->firstface;
2923                 mod->brushq1.nummodelsurfaces = bm->numfaces;
2924
2925                 // this gets altered below if sky is used
2926                 mod->DrawSky = NULL;
2927                 mod->Draw = R_Model_Brush_Draw;
2928                 mod->DrawShadowVolume = R_Model_Brush_DrawShadowVolume;
2929                 mod->DrawLight = R_Model_Brush_DrawLight;
2930                 mod->brushq1.pvstexturechains = Mem_Alloc(originalloadmodel->mempool, mod->brushq1.numtextures * sizeof(msurface_t **));
2931                 mod->brushq1.pvstexturechainsbuffer = Mem_Alloc(originalloadmodel->mempool,(mod->brushq1.nummodelsurfaces + mod->brushq1.numtextures) * sizeof(msurface_t *));
2932                 mod->brushq1.pvstexturechainslength = Mem_Alloc(originalloadmodel->mempool, mod->brushq1.numtextures * sizeof(int));
2933                 Mod_Q1BSP_BuildPVSTextureChains(mod);
2934                 Mod_Q1BSP_BuildLightmapUpdateChains(originalloadmodel->mempool, mod);
2935                 if (mod->brushq1.nummodelsurfaces)
2936                 {
2937                         // LordHavoc: calculate bmodel bounding box rather than trusting what it says
2938                         mod->normalmins[0] = mod->normalmins[1] = mod->normalmins[2] = 1000000000.0f;
2939                         mod->normalmaxs[0] = mod->normalmaxs[1] = mod->normalmaxs[2] = -1000000000.0f;
2940                         modelyawradius = 0;
2941                         modelradius = 0;
2942                         for (j = 0, surf = &mod->brushq1.surfaces[mod->brushq1.firstmodelsurface];j < mod->brushq1.nummodelsurfaces;j++, surf++)
2943                         {
2944                                 // we only need to have a drawsky function if it is used(usually only on world model)
2945                                 if (surf->texinfo->texture->shader == &Cshader_sky)
2946                                         mod->DrawSky = R_Model_Brush_DrawSky;
2947                                 // LordHavoc: submodels always clip, even if water
2948                                 if (mod->brush.numsubmodels - 1)
2949                                         surf->flags |= SURF_SOLIDCLIP;
2950                                 // calculate bounding shapes
2951                                 for (k = 0, vec = surf->mesh.data_vertex3f;k < surf->mesh.num_vertices;k++, vec += 3)
2952                                 {
2953                                         if (mod->normalmins[0] > vec[0]) mod->normalmins[0] = vec[0];
2954                                         if (mod->normalmins[1] > vec[1]) mod->normalmins[1] = vec[1];
2955                                         if (mod->normalmins[2] > vec[2]) mod->normalmins[2] = vec[2];
2956                                         if (mod->normalmaxs[0] < vec[0]) mod->normalmaxs[0] = vec[0];
2957                                         if (mod->normalmaxs[1] < vec[1]) mod->normalmaxs[1] = vec[1];
2958                                         if (mod->normalmaxs[2] < vec[2]) mod->normalmaxs[2] = vec[2];
2959                                         dist = vec[0]*vec[0]+vec[1]*vec[1];
2960                                         if (modelyawradius < dist)
2961                                                 modelyawradius = dist;
2962                                         dist += vec[2]*vec[2];
2963                                         if (modelradius < dist)
2964                                                 modelradius = dist;
2965                                 }
2966                         }
2967                         modelyawradius = sqrt(modelyawradius);
2968                         modelradius = sqrt(modelradius);
2969                         mod->yawmins[0] = mod->yawmins[1] = - (mod->yawmaxs[0] = mod->yawmaxs[1] = modelyawradius);
2970                         mod->yawmins[2] = mod->normalmins[2];
2971                         mod->yawmaxs[2] = mod->normalmaxs[2];
2972                         mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
2973                         mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
2974                         mod->radius = modelradius;
2975                         mod->radius2 = modelradius * modelradius;
2976                 }
2977                 else
2978                 {
2979                         // LordHavoc: empty submodel(lacrima.bsp has such a glitch)
2980                         Con_Printf("warning: empty submodel *%i in %s\n", i+1, loadname);
2981                 }
2982                 Mod_Q1BSP_BuildSurfaceNeighbors(mod->brushq1.surfaces + mod->brushq1.firstmodelsurface, mod->brushq1.nummodelsurfaces, originalloadmodel->mempool);
2983
2984                 mod->brushq1.visleafs = bm->visleafs;
2985
2986                 // LordHavoc: only register submodels if it is the world
2987                 // (prevents bsp models from replacing world submodels)
2988                 if (loadmodel->isworldmodel && i < (mod->brush.numsubmodels - 1))
2989                 {
2990                         char    name[10];
2991                         // duplicate the basic information
2992                         sprintf(name, "*%i", i+1);
2993                         loadmodel = Mod_FindName(name);
2994                         *loadmodel = *mod;
2995                         strcpy(loadmodel->name, name);
2996                         // textures and memory belong to the main model
2997                         loadmodel->texturepool = NULL;
2998                         loadmodel->mempool = NULL;
2999                         mod = loadmodel;
3000                 }
3001         }