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