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