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