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