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