isolated more of the texture loading code from the rest of model
[divverent/darkplaces.git] / model_brush.c
1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19 */
20
21 #include "quakedef.h"
22 #include "image.h"
23 #include "r_shadow.h"
24 #include "polygon.h"
25 #include "curves.h"
26 #include "wad.h"
27
28
29 //cvar_t r_subdivide_size = {CVAR_SAVE, "r_subdivide_size", "128", "how large water polygons should be (smaller values produce more polygons which give better warping effects)"};
30 cvar_t halflifebsp = {0, "halflifebsp", "0", "indicates the current map is hlbsp format (useful to know because of different bounding box sizes)"};
31 cvar_t mcbsp = {0, "mcbsp", "0", "indicates the current map is mcbsp format (useful to know because of different bounding box sizes)"};
32 cvar_t r_novis = {0, "r_novis", "0", "draws whole level, see also sv_cullentities_pvs 0"};
33 cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1", "whether to use RGBA (32bit) or RGB (24bit) lightmaps"};
34 cvar_t r_nosurftextures = {0, "r_nosurftextures", "0", "pretends there was no texture lump found in the q1bsp/hlbsp loading (useful for debugging this rare case)"};
35 cvar_t r_subdivisions_tolerance = {0, "r_subdivisions_tolerance", "4", "maximum error tolerance on curve subdivision for rendering purposes (in other words, the curves will be given as many polygons as necessary to represent curves at this quality)"};
36 cvar_t r_subdivisions_mintess = {0, "r_subdivisions_mintess", "1", "minimum number of subdivisions (values above 1 will smooth curves that don't need it)"};
37 cvar_t r_subdivisions_maxtess = {0, "r_subdivisions_maxtess", "1024", "maximum number of subdivisions (prevents curves beyond a certain detail level, limits smoothing)"};
38 cvar_t r_subdivisions_maxvertices = {0, "r_subdivisions_maxvertices", "65536", "maximum vertices allowed per subdivided curve"};
39 cvar_t r_subdivisions_collision_tolerance = {0, "r_subdivisions_collision_tolerance", "15", "maximum error tolerance on curve subdivision for collision purposes (usually a larger error tolerance than for rendering)"};
40 cvar_t r_subdivisions_collision_mintess = {0, "r_subdivisions_collision_mintess", "1", "minimum number of subdivisions (values above 1 will smooth curves that don't need it)"};
41 cvar_t r_subdivisions_collision_maxtess = {0, "r_subdivisions_collision_maxtess", "1024", "maximum number of subdivisions (prevents curves beyond a certain detail level, limits smoothing)"};
42 cvar_t r_subdivisions_collision_maxvertices = {0, "r_subdivisions_collision_maxvertices", "4225", "maximum vertices allowed per subdivided curve"};
43 cvar_t mod_q3bsp_curves_collisions = {0, "mod_q3bsp_curves_collisions", "1", "enables collisions with curves (SLOW)"};
44 cvar_t mod_q3bsp_optimizedtraceline = {0, "mod_q3bsp_optimizedtraceline", "1", "whether to use optimized traceline code for line traces (as opposed to tracebox code)"};
45 cvar_t mod_q3bsp_debugtracebrush = {0, "mod_q3bsp_debugtracebrush", "0", "selects different tracebrush bsp recursion algorithms (for debugging purposes only)"};
46 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_lightmaprgba);
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         dclipnode_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                 if (boxsize[2] < 48) // pick the nearest of 40 or 56
826                         rhc.hull = &model->brushq1.hulls[2]; // 16x16x40
827                 else
828                         rhc.hull = &model->brushq1.hulls[1]; // 16x16x56
829         }
830         else if (model->brush.ishlbsp)
831         {
832                 // LordHavoc: this has to have a minor tolerance (the .1) because of
833                 // minor float precision errors from the box being transformed around
834                 if (boxsize[0] < 32.1)
835                 {
836                         if (boxsize[2] < 54) // pick the nearest of 36 or 72
837                                 rhc.hull = &model->brushq1.hulls[3]; // 32x32x36
838                         else
839                                 rhc.hull = &model->brushq1.hulls[1]; // 32x32x72
840                 }
841                 else
842                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x64
843         }
844         else
845         {
846                 // LordHavoc: this has to have a minor tolerance (the .1) because of
847                 // minor float precision errors from the box being transformed around
848                 if (boxsize[0] < 32.1)
849                         rhc.hull = &model->brushq1.hulls[1]; // 32x32x56
850                 else
851                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x88
852         }
853         VectorMAMAM(1, start, 1, boxmins, -1, rhc.hull->clip_mins, rhc.start);
854         VectorMAMAM(1, end, 1, boxmins, -1, rhc.hull->clip_mins, rhc.end);
855         VectorSubtract(rhc.end, rhc.start, rhc.dist);
856 #if COLLISIONPARANOID >= 2
857         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]);
858         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
859         {
860
861                 double test[3];
862                 trace_t testtrace;
863                 VectorLerp(rhc.start, rhc.trace->fraction, rhc.end, test);
864                 memset(&testtrace, 0, sizeof(trace_t));
865                 rhc.trace = &testtrace;
866                 rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
867                 rhc.trace->fraction = 1;
868                 rhc.trace->realfraction = 1;
869                 rhc.trace->allsolid = true;
870                 VectorCopy(test, rhc.start);
871                 VectorCopy(test, rhc.end);
872                 VectorClear(rhc.dist);
873                 Mod_Q1BSP_RecursiveHullCheckPoint(&rhc, rhc.hull->firstclipnode);
874                 //Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, test, test);
875                 if (!trace->startsolid && testtrace.startsolid)
876                         Con_Printf(" - ended in solid!\n");
877         }
878         Con_Print("\n");
879 #else
880         if (VectorLength2(rhc.dist))
881                 Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
882         else
883                 Mod_Q1BSP_RecursiveHullCheckPoint(&rhc, rhc.hull->firstclipnode);
884 #endif
885 }
886
887 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)
888 {
889 #if 1
890         colbrushf_t cbox;
891         colplanef_t cbox_planes[6];
892         cbox.supercontents = boxsupercontents;
893         cbox.numplanes = 6;
894         cbox.numpoints = 0;
895         cbox.numtriangles = 0;
896         cbox.planes = cbox_planes;
897         cbox.points = NULL;
898         cbox.elements = NULL;
899         cbox.markframe = 0;
900         cbox.mins[0] = 0;
901         cbox.mins[1] = 0;
902         cbox.mins[2] = 0;
903         cbox.maxs[0] = 0;
904         cbox.maxs[1] = 0;
905         cbox.maxs[2] = 0;
906         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];
907         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];
908         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];
909         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];
910         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];
911         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];
912         cbox_planes[0].q3surfaceflags = boxq3surfaceflags;cbox_planes[0].texture = boxtexture;
913         cbox_planes[1].q3surfaceflags = boxq3surfaceflags;cbox_planes[1].texture = boxtexture;
914         cbox_planes[2].q3surfaceflags = boxq3surfaceflags;cbox_planes[2].texture = boxtexture;
915         cbox_planes[3].q3surfaceflags = boxq3surfaceflags;cbox_planes[3].texture = boxtexture;
916         cbox_planes[4].q3surfaceflags = boxq3surfaceflags;cbox_planes[4].texture = boxtexture;
917         cbox_planes[5].q3surfaceflags = boxq3surfaceflags;cbox_planes[5].texture = boxtexture;
918         memset(trace, 0, sizeof(trace_t));
919         trace->hitsupercontentsmask = hitsupercontentsmask;
920         trace->fraction = 1;
921         trace->realfraction = 1;
922         Collision_TraceLineBrushFloat(trace, start, end, &cbox, &cbox);
923 #else
924         RecursiveHullCheckTraceInfo_t rhc;
925         static hull_t box_hull;
926         static dclipnode_t box_clipnodes[6];
927         static mplane_t box_planes[6];
928         // fill in a default trace
929         memset(&rhc, 0, sizeof(rhc));
930         memset(trace, 0, sizeof(trace_t));
931         //To keep everything totally uniform, bounding boxes are turned into small
932         //BSP trees instead of being compared directly.
933         // create a temp hull from bounding box sizes
934         box_planes[0].dist = cmaxs[0] - mins[0];
935         box_planes[1].dist = cmins[0] - maxs[0];
936         box_planes[2].dist = cmaxs[1] - mins[1];
937         box_planes[3].dist = cmins[1] - maxs[1];
938         box_planes[4].dist = cmaxs[2] - mins[2];
939         box_planes[5].dist = cmins[2] - maxs[2];
940 #if COLLISIONPARANOID >= 3
941         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]);
942 #endif
943
944         if (box_hull.clipnodes == NULL)
945         {
946                 int i, side;
947
948                 //Set up the planes and clipnodes so that the six floats of a bounding box
949                 //can just be stored out and get a proper hull_t structure.
950
951                 box_hull.clipnodes = box_clipnodes;
952                 box_hull.planes = box_planes;
953                 box_hull.firstclipnode = 0;
954                 box_hull.lastclipnode = 5;
955
956                 for (i = 0;i < 6;i++)
957                 {
958                         box_clipnodes[i].planenum = i;
959
960                         side = i&1;
961
962                         box_clipnodes[i].children[side] = CONTENTS_EMPTY;
963                         if (i != 5)
964                                 box_clipnodes[i].children[side^1] = i + 1;
965                         else
966                                 box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
967
968                         box_planes[i].type = i>>1;
969                         box_planes[i].normal[i>>1] = 1;
970                 }
971         }
972
973         // trace a line through the generated clipping hull
974         //rhc.boxsupercontents = boxsupercontents;
975         rhc.hull = &box_hull;
976         rhc.trace = trace;
977         rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
978         rhc.trace->fraction = 1;
979         rhc.trace->realfraction = 1;
980         rhc.trace->allsolid = true;
981         VectorCopy(start, rhc.start);
982         VectorCopy(end, rhc.end);
983         VectorSubtract(rhc.end, rhc.start, rhc.dist);
984         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
985         //VectorMA(rhc.start, rhc.trace->fraction, rhc.dist, rhc.trace->endpos);
986         if (rhc.trace->startsupercontents)
987                 rhc.trace->startsupercontents = boxsupercontents;
988 #endif
989 }
990
991 static int Mod_Q1BSP_TraceLineOfSight_RecursiveNodeCheck(mnode_t *node, double p1[3], double p2[3])
992 {
993         double t1, t2;
994         double midf, mid[3];
995         int ret, side;
996
997         // check for empty
998         while (node->plane)
999         {
1000                 // find the point distances
1001                 mplane_t *plane = node->plane;
1002                 if (plane->type < 3)
1003                 {
1004                         t1 = p1[plane->type] - plane->dist;
1005                         t2 = p2[plane->type] - plane->dist;
1006                 }
1007                 else
1008                 {
1009                         t1 = DotProduct (plane->normal, p1) - plane->dist;
1010                         t2 = DotProduct (plane->normal, p2) - plane->dist;
1011                 }
1012
1013                 if (t1 < 0)
1014                 {
1015                         if (t2 < 0)
1016                         {
1017                                 node = node->children[1];
1018                                 continue;
1019                         }
1020                         side = 1;
1021                 }
1022                 else
1023                 {
1024                         if (t2 >= 0)
1025                         {
1026                                 node = node->children[0];
1027                                 continue;
1028                         }
1029                         side = 0;
1030                 }
1031
1032                 midf = t1 / (t1 - t2);
1033                 VectorLerp(p1, midf, p2, mid);
1034
1035                 // recurse both sides, front side first
1036                 // return 2 if empty is followed by solid (hit something)
1037                 // do not return 2 if both are solid or both empty,
1038                 // or if start is solid and end is empty
1039                 // as these degenerate cases usually indicate the eye is in solid and
1040                 // should see the target point anyway
1041                 ret = Mod_Q1BSP_TraceLineOfSight_RecursiveNodeCheck(node->children[side    ], p1, mid);
1042                 if (ret != 0)
1043                         return ret;
1044                 ret = Mod_Q1BSP_TraceLineOfSight_RecursiveNodeCheck(node->children[side ^ 1], mid, p2);
1045                 if (ret != 1)
1046                         return ret;
1047                 return 2;
1048         }
1049         return ((mleaf_t *)node)->clusterindex < 0;
1050 }
1051
1052 static qboolean Mod_Q1BSP_TraceLineOfSight(struct model_s *model, const vec3_t start, const vec3_t end)
1053 {
1054         // this function currently only supports same size start and end
1055         double tracestart[3], traceend[3];
1056         VectorCopy(start, tracestart);
1057         VectorCopy(end, traceend);
1058         return Mod_Q1BSP_TraceLineOfSight_RecursiveNodeCheck(model->brush.data_nodes, tracestart, traceend) != 2;
1059 }
1060
1061 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)
1062 {
1063         int side;
1064         float front, back;
1065         float mid, distz = endz - startz;
1066
1067 loc0:
1068         if (!node->plane)
1069                 return false;           // didn't hit anything
1070
1071         switch (node->plane->type)
1072         {
1073         case PLANE_X:
1074                 node = node->children[x < node->plane->dist];
1075                 goto loc0;
1076         case PLANE_Y:
1077                 node = node->children[y < node->plane->dist];
1078                 goto loc0;
1079         case PLANE_Z:
1080                 side = startz < node->plane->dist;
1081                 if ((endz < node->plane->dist) == side)
1082                 {
1083                         node = node->children[side];
1084                         goto loc0;
1085                 }
1086                 // found an intersection
1087                 mid = node->plane->dist;
1088                 break;
1089         default:
1090                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
1091                 front += startz * node->plane->normal[2];
1092                 back += endz * node->plane->normal[2];
1093                 side = front < node->plane->dist;
1094                 if ((back < node->plane->dist) == side)
1095                 {
1096                         node = node->children[side];
1097                         goto loc0;
1098                 }
1099                 // found an intersection
1100                 mid = startz + distz * (front - node->plane->dist) / (front - back);
1101                 break;
1102         }
1103
1104         // go down front side
1105         if (node->children[side]->plane && Mod_Q1BSP_LightPoint_RecursiveBSPNode(model, ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
1106                 return true;    // hit something
1107         else
1108         {
1109                 // check for impact on this node
1110                 if (node->numsurfaces)
1111                 {
1112                         int i, ds, dt;
1113                         msurface_t *surface;
1114
1115                         surface = model->data_surfaces + node->firstsurface;
1116                         for (i = 0;i < node->numsurfaces;i++, surface++)
1117                         {
1118                                 if (!(surface->texture->basematerialflags & MATERIALFLAG_WALL) || !surface->lightmapinfo->samples)
1119                                         continue;       // no lightmaps
1120
1121                                 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];
1122                                 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];
1123
1124                                 if (ds >= 0 && ds < surface->lightmapinfo->extents[0] && dt >= 0 && dt < surface->lightmapinfo->extents[1])
1125                                 {
1126                                         unsigned char *lightmap;
1127                                         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;
1128                                         lmwidth = ((surface->lightmapinfo->extents[0]>>4)+1);
1129                                         lmheight = ((surface->lightmapinfo->extents[1]>>4)+1);
1130                                         line3 = lmwidth * 3; // LordHavoc: *3 for colored lighting
1131                                         size3 = lmwidth * lmheight * 3; // LordHavoc: *3 for colored lighting
1132
1133                                         lightmap = surface->lightmapinfo->samples + ((dt>>4) * lmwidth + (ds>>4))*3; // LordHavoc: *3 for colored lighting
1134
1135                                         for (maps = 0;maps < MAXLIGHTMAPS && surface->lightmapinfo->styles[maps] != 255;maps++)
1136                                         {
1137                                                 scale = r_refdef.lightstylevalue[surface->lightmapinfo->styles[maps]];
1138                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
1139                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
1140                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
1141                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
1142                                                 lightmap += size3;
1143                                         }
1144
1145 /*
1146 LordHavoc: here's the readable version of the interpolation
1147 code, not quite as easy for the compiler to optimize...
1148
1149 dsfrac is the X position in the lightmap pixel, * 16
1150 dtfrac is the Y position in the lightmap pixel, * 16
1151 r00 is top left corner, r01 is top right corner
1152 r10 is bottom left corner, r11 is bottom right corner
1153 g and b are the same layout.
1154 r0 and r1 are the top and bottom intermediate results
1155
1156 first we interpolate the top two points, to get the top
1157 edge sample
1158
1159         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
1160         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
1161         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
1162
1163 then we interpolate the bottom two points, to get the
1164 bottom edge sample
1165
1166         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
1167         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
1168         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
1169
1170 then we interpolate the top and bottom samples to get the
1171 middle sample (the one which was requested)
1172
1173         r = (((r1-r0) * dtfrac) >> 4) + r0;
1174         g = (((g1-g0) * dtfrac) >> 4) + g0;
1175         b = (((b1-b0) * dtfrac) >> 4) + b0;
1176 */
1177
1178                                         ambientcolor[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
1179                                         ambientcolor[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
1180                                         ambientcolor[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
1181                                         return true; // success
1182                                 }
1183                         }
1184                 }
1185
1186                 // go down back side
1187                 node = node->children[side ^ 1];
1188                 startz = mid;
1189                 distz = endz - startz;
1190                 goto loc0;
1191         }
1192 }
1193
1194 void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
1195 {
1196         // pretend lighting is coming down from above (due to lack of a lightgrid to know primary lighting direction)
1197         VectorSet(diffusenormal, 0, 0, 1);
1198
1199         if (!model->brushq1.lightdata)
1200         {
1201                 VectorSet(ambientcolor, 1, 1, 1);
1202                 VectorSet(diffusecolor, 0, 0, 0);
1203                 return;
1204         }
1205
1206         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);
1207 }
1208
1209 static void Mod_Q1BSP_DecompressVis(const unsigned char *in, const unsigned char *inend, unsigned char *out, unsigned char *outend)
1210 {
1211         int c;
1212         unsigned char *outstart = out;
1213         while (out < outend)
1214         {
1215                 if (in == inend)
1216                 {
1217                         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));
1218                         return;
1219                 }
1220                 c = *in++;
1221                 if (c)
1222                         *out++ = c;
1223                 else
1224                 {
1225                         if (in == inend)
1226                         {
1227                                 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));
1228                                 return;
1229                         }
1230                         for (c = *in++;c > 0;c--)
1231                         {
1232                                 if (out == outend)
1233                                 {
1234                                         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));
1235                                         return;
1236                                 }
1237                                 *out++ = 0;
1238                         }
1239                 }
1240         }
1241 }
1242
1243 /*
1244 =============
1245 R_Q1BSP_LoadSplitSky
1246
1247 A sky texture is 256*128, with the right side being a masked overlay
1248 ==============
1249 */
1250 void R_Q1BSP_LoadSplitSky (unsigned char *src, int width, int height, int bytesperpixel)
1251 {
1252         int i, j;
1253         unsigned solidpixels[128*128], alphapixels[128*128];
1254
1255         // allocate a texture pool if we need it
1256         if (loadmodel->texturepool == NULL && cls.state != ca_dedicated)
1257                 loadmodel->texturepool = R_AllocTexturePool();
1258
1259         // if sky isn't the right size, just use it as a solid layer
1260         if (width != 256 || height != 128)
1261         {
1262                 loadmodel->brush.solidskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_solidtexture", width, height, src, bytesperpixel == 4 ? TEXTYPE_RGBA : TEXTYPE_PALETTE, TEXF_PRECACHE, bytesperpixel == 1 ? palette_complete : NULL);
1263                 loadmodel->brush.alphaskytexture = NULL;
1264                 return;
1265         }
1266
1267         if (bytesperpixel == 4)
1268         {
1269                 for (i = 0;i < 128;i++)
1270                 {
1271                         for (j = 0;j < 128;j++)
1272                         {
1273                                 solidpixels[(i*128) + j] = ((unsigned *)src)[i*256+j+128];
1274                                 alphapixels[(i*128) + j] = ((unsigned *)src)[i*256+j];
1275                         }
1276                 }
1277         }
1278         else
1279         {
1280                 // make an average value for the back to avoid
1281                 // a fringe on the top level
1282                 int p, r, g, b;
1283                 union
1284                 {
1285                         unsigned int i;
1286                         unsigned char b[4];
1287                 }
1288                 rgba;
1289                 r = g = b = 0;
1290                 for (i = 0;i < 128;i++)
1291                 {
1292                         for (j = 0;j < 128;j++)
1293                         {
1294                                 rgba.i = palette_complete[src[i*256 + j + 128]];
1295                                 r += rgba.b[0];
1296                                 g += rgba.b[1];
1297                                 b += rgba.b[2];
1298                         }
1299                 }
1300                 rgba.b[0] = r/(128*128);
1301                 rgba.b[1] = g/(128*128);
1302                 rgba.b[2] = b/(128*128);
1303                 rgba.b[3] = 0;
1304                 for (i = 0;i < 128;i++)
1305                 {
1306                         for (j = 0;j < 128;j++)
1307                         {
1308                                 solidpixels[(i*128) + j] = palette_complete[src[i*256 + j + 128]];
1309                                 alphapixels[(i*128) + j] = (p = src[i*256 + j]) ? palette_complete[p] : rgba.i;
1310                         }
1311                 }
1312         }
1313
1314         loadmodel->brush.solidskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_solidtexture", 128, 128, (unsigned char *) solidpixels, TEXTYPE_RGBA, TEXF_PRECACHE, NULL);
1315         loadmodel->brush.alphaskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_alphatexture", 128, 128, (unsigned char *) alphapixels, TEXTYPE_RGBA, TEXF_ALPHA | TEXF_PRECACHE, NULL);
1316 }
1317
1318 static void Mod_Q1BSP_LoadTextures(lump_t *l)
1319 {
1320         int i, j, k, num, max, altmax, mtwidth, mtheight, *dofs, incomplete;
1321         skinframe_t *skinframe;
1322         miptex_t *dmiptex;
1323         texture_t *tx, *tx2, *anims[10], *altanims[10];
1324         dmiptexlump_t *m;
1325         unsigned char *data, *mtdata;
1326         const char *s;
1327         char mapname[MAX_QPATH], name[MAX_QPATH];
1328
1329         loadmodel->data_textures = NULL;
1330
1331         // add two slots for notexture walls and notexture liquids
1332         if (l->filelen)
1333         {
1334                 m = (dmiptexlump_t *)(mod_base + l->fileofs);
1335                 m->nummiptex = LittleLong (m->nummiptex);
1336                 loadmodel->num_textures = m->nummiptex + 2;
1337         }
1338         else
1339         {
1340                 m = NULL;
1341                 loadmodel->num_textures = 2;
1342         }
1343
1344         loadmodel->data_textures = (texture_t *)Mem_Alloc(loadmodel->mempool, loadmodel->num_textures * sizeof(texture_t));
1345
1346         // fill out all slots with notexture
1347         if (cls.state != ca_dedicated)
1348                 skinframe = R_SkinFrame_LoadMissing();
1349         else
1350                 skinframe = NULL;
1351         for (i = 0, tx = loadmodel->data_textures;i < loadmodel->num_textures;i++, tx++)
1352         {
1353                 strlcpy(tx->name, "NO TEXTURE FOUND", sizeof(tx->name));
1354                 tx->width = 16;
1355                 tx->height = 16;
1356                 if (cls.state != ca_dedicated)
1357                 {
1358                         tx->numskinframes = 1;
1359                         tx->skinframerate = 1;
1360                         tx->skinframes[0] = skinframe;
1361                         tx->currentskinframe = tx->skinframes[0];
1362                         tx->basematerialflags = 0;
1363                 }
1364                 if (i == loadmodel->num_textures - 1)
1365                 {
1366                         tx->basematerialflags |= MATERIALFLAG_WATER | MATERIALFLAG_LIGHTBOTHSIDES | MATERIALFLAG_NOSHADOW;
1367                         tx->supercontents = mod_q1bsp_texture_water.supercontents;
1368                         tx->surfaceflags = mod_q1bsp_texture_water.surfaceflags;
1369                 }
1370                 else
1371                 {
1372                         tx->basematerialflags |= MATERIALFLAG_WALL;
1373                         tx->supercontents = mod_q1bsp_texture_solid.supercontents;
1374                         tx->surfaceflags = mod_q1bsp_texture_solid.surfaceflags;
1375                 }
1376                 tx->currentframe = tx;
1377         }
1378
1379         if (!m)
1380                 return;
1381
1382         s = loadmodel->name;
1383         if (!strncasecmp(s, "maps/", 5))
1384                 s += 5;
1385         FS_StripExtension(s, mapname, sizeof(mapname));
1386
1387         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
1388         dofs = m->dataofs;
1389         // LordHavoc: mostly rewritten map texture loader
1390         for (i = 0;i < m->nummiptex;i++)
1391         {
1392                 dofs[i] = LittleLong(dofs[i]);
1393                 if (dofs[i] == -1 || r_nosurftextures.integer)
1394                         continue;
1395                 dmiptex = (miptex_t *)((unsigned char *)m + dofs[i]);
1396
1397                 // make sure name is no more than 15 characters
1398                 for (j = 0;dmiptex->name[j] && j < 15;j++)
1399                         name[j] = dmiptex->name[j];
1400                 name[j] = 0;
1401
1402                 mtwidth = LittleLong(dmiptex->width);
1403                 mtheight = LittleLong(dmiptex->height);
1404                 mtdata = NULL;
1405                 j = LittleLong(dmiptex->offsets[0]);
1406                 if (j)
1407                 {
1408                         // texture included
1409                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
1410                         {
1411                                 Con_Printf("Texture \"%s\" in \"%s\"is corrupt or incomplete\n", dmiptex->name, loadmodel->name);
1412                                 continue;
1413                         }
1414                         mtdata = (unsigned char *)dmiptex + j;
1415                 }
1416
1417                 if ((mtwidth & 15) || (mtheight & 15))
1418                         Con_Printf("warning: texture \"%s\" in \"%s\" is not 16 aligned\n", dmiptex->name, loadmodel->name);
1419
1420                 // LordHavoc: force all names to lowercase
1421                 for (j = 0;name[j];j++)
1422                         if (name[j] >= 'A' && name[j] <= 'Z')
1423                                 name[j] += 'a' - 'A';
1424
1425                 tx = loadmodel->data_textures + i;
1426                 strlcpy(tx->name, name, sizeof(tx->name));
1427                 tx->width = mtwidth;
1428                 tx->height = mtheight;
1429
1430                 if (!tx->name[0])
1431                 {
1432                         sprintf(tx->name, "unnamed%i", i);
1433                         Con_Printf("warning: unnamed texture in %s, renaming to %s\n", loadmodel->name, tx->name);
1434                 }
1435
1436                 if (tx->name[0] == '*')
1437                 {
1438                         if (!strncmp(tx->name, "*lava", 5))
1439                         {
1440                                 tx->supercontents = mod_q1bsp_texture_lava.supercontents;
1441                                 tx->surfaceflags = mod_q1bsp_texture_lava.surfaceflags;
1442                         }
1443                         else if (!strncmp(tx->name, "*slime", 6))
1444                         {
1445                                 tx->supercontents = mod_q1bsp_texture_slime.supercontents;
1446                                 tx->surfaceflags = mod_q1bsp_texture_slime.surfaceflags;
1447                         }
1448                         else
1449                         {
1450                                 tx->supercontents = mod_q1bsp_texture_water.supercontents;
1451                                 tx->surfaceflags = mod_q1bsp_texture_water.surfaceflags;
1452                         }
1453                 }
1454                 else if (!strncmp(tx->name, "sky", 3))
1455                 {
1456                         tx->supercontents = mod_q1bsp_texture_sky.supercontents;
1457                         tx->surfaceflags = mod_q1bsp_texture_sky.surfaceflags;
1458                 }
1459                 else
1460                 {
1461                         tx->supercontents = mod_q1bsp_texture_solid.supercontents;
1462                         tx->surfaceflags = mod_q1bsp_texture_solid.surfaceflags;
1463                 }
1464
1465                 if (cls.state != ca_dedicated)
1466                 {
1467                         // LordHavoc: HL sky textures are entirely different than quake
1468                         if (!loadmodel->brush.ishlbsp && !strncmp(tx->name, "sky", 3) && mtwidth == 256 && mtheight == 128)
1469                         {
1470                                 if (loadmodel->isworldmodel)
1471                                 {
1472                                         data = loadimagepixels(tx->name, false, 0, 0);
1473                                         if (data)
1474                                         {
1475                                                 R_Q1BSP_LoadSplitSky(data, image_width, image_height, 4);
1476                                                 Mem_Free(data);
1477                                         }
1478                                         else if (mtdata != NULL)
1479                                                 R_Q1BSP_LoadSplitSky(mtdata, mtwidth, mtheight, 1);
1480                                 }
1481                         }
1482                         else
1483                         {
1484                                 skinframe = R_SkinFrame_LoadExternal(gamemode == GAME_TENEBRAE ? tx->name : va("textures/%s/%s", mapname, tx->name), TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP);
1485                                 if (!skinframe)
1486                                         skinframe = R_SkinFrame_LoadExternal(gamemode == GAME_TENEBRAE ? tx->name : va("textures/%s", tx->name), TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP);
1487                                 if (!skinframe)
1488                                 {
1489                                         // did not find external texture, load it from the bsp or wad3
1490                                         if (loadmodel->brush.ishlbsp)
1491                                         {
1492                                                 // internal texture overrides wad
1493                                                 unsigned char *pixels, *freepixels;
1494                                                 pixels = freepixels = NULL;
1495                                                 if (mtdata)
1496                                                         pixels = W_ConvertWAD3Texture(dmiptex);
1497                                                 if (pixels == NULL)
1498                                                         pixels = freepixels = W_GetTexture(tx->name);
1499                                                 if (pixels != NULL)
1500                                                 {
1501                                                         tx->width = image_width;
1502                                                         tx->height = image_height;
1503                                                         skinframe = R_SkinFrame_LoadInternal(tx->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, false, false, pixels, image_width, image_height, 32, NULL, NULL);
1504                                                 }
1505                                                 if (freepixels)
1506                                                         Mem_Free(freepixels);
1507                                         }
1508                                         else if (mtdata) // texture included
1509                                                 skinframe = R_SkinFrame_LoadInternal(tx->name, TEXF_MIPMAP | TEXF_PRECACHE | TEXF_PICMIP, false, r_fullbrights.integer, mtdata, tx->width, tx->height, 8, NULL, NULL);
1510                                 }
1511                                 // if skinframe is still NULL the "missing" texture will be used
1512                                 if (skinframe)
1513                                         tx->skinframes[0] = skinframe;
1514                         }
1515
1516                         tx->basematerialflags = 0;
1517                         if (tx->name[0] == '*')
1518                         {
1519                                 // LordHavoc: some turbulent textures should not be affected by wateralpha
1520                                 if (strncmp(tx->name,"*lava",5)
1521                                  && strncmp(tx->name,"*teleport",9)
1522                                  && strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
1523                                         tx->basematerialflags |= MATERIALFLAG_WATERALPHA | MATERIALFLAG_NOSHADOW;
1524                                 tx->basematerialflags |= MATERIALFLAG_WATER | MATERIALFLAG_LIGHTBOTHSIDES | MATERIALFLAG_NOSHADOW;
1525                         }
1526                         else if (!strncmp(tx->name, "sky", 3))
1527                                 tx->basematerialflags |= MATERIALFLAG_SKY | MATERIALFLAG_NOSHADOW;
1528                         else
1529                                 tx->basematerialflags |= MATERIALFLAG_WALL;
1530                         if (tx->skinframes[0] && tx->skinframes[0]->fog)
1531                                 tx->basematerialflags |= MATERIALFLAG_ALPHA | MATERIALFLAG_BLENDED | MATERIALFLAG_NOSHADOW;
1532
1533                         // start out with no animation
1534                         tx->currentframe = tx;
1535                         tx->currentskinframe = tx->skinframes[0];
1536                 }
1537         }
1538
1539         // sequence the animations
1540         for (i = 0;i < m->nummiptex;i++)
1541         {
1542                 tx = loadmodel->data_textures + i;
1543                 if (!tx || tx->name[0] != '+' || tx->name[1] == 0 || tx->name[2] == 0)
1544                         continue;
1545                 if (tx->anim_total[0] || tx->anim_total[1])
1546                         continue;       // already sequenced
1547
1548                 // find the number of frames in the animation
1549                 memset(anims, 0, sizeof(anims));
1550                 memset(altanims, 0, sizeof(altanims));
1551
1552                 for (j = i;j < m->nummiptex;j++)
1553                 {
1554                         tx2 = loadmodel->data_textures + j;
1555                         if (!tx2 || tx2->name[0] != '+' || strcmp(tx2->name+2, tx->name+2))
1556                                 continue;
1557
1558                         num = tx2->name[1];
1559                         if (num >= '0' && num <= '9')
1560                                 anims[num - '0'] = tx2;
1561                         else if (num >= 'a' && num <= 'j')
1562                                 altanims[num - 'a'] = tx2;
1563                         else
1564                                 Con_Printf("Bad animating texture %s\n", tx->name);
1565                 }
1566
1567                 max = altmax = 0;
1568                 for (j = 0;j < 10;j++)
1569                 {
1570                         if (anims[j])
1571                                 max = j + 1;
1572                         if (altanims[j])
1573                                 altmax = j + 1;
1574                 }
1575                 //Con_Printf("linking animation %s (%i:%i frames)\n\n", tx->name, max, altmax);
1576
1577                 incomplete = false;
1578                 for (j = 0;j < max;j++)
1579                 {
1580                         if (!anims[j])
1581                         {
1582                                 Con_Printf("Missing frame %i of %s\n", j, tx->name);
1583                                 incomplete = true;
1584                         }
1585                 }
1586                 for (j = 0;j < altmax;j++)
1587                 {
1588                         if (!altanims[j])
1589                         {
1590                                 Con_Printf("Missing altframe %i of %s\n", j, tx->name);
1591                                 incomplete = true;
1592                         }
1593                 }
1594                 if (incomplete)
1595                         continue;
1596
1597                 if (altmax < 1)
1598                 {
1599                         // if there is no alternate animation, duplicate the primary
1600                         // animation into the alternate
1601                         altmax = max;
1602                         for (k = 0;k < 10;k++)
1603                                 altanims[k] = anims[k];
1604                 }
1605
1606                 // link together the primary animation
1607                 for (j = 0;j < max;j++)
1608                 {
1609                         tx2 = anims[j];
1610                         tx2->animated = true;
1611                         tx2->anim_total[0] = max;
1612                         tx2->anim_total[1] = altmax;
1613                         for (k = 0;k < 10;k++)
1614                         {
1615                                 tx2->anim_frames[0][k] = anims[k];
1616                                 tx2->anim_frames[1][k] = altanims[k];
1617                         }
1618                 }
1619
1620                 // if there really is an alternate anim...
1621                 if (anims[0] != altanims[0])
1622                 {
1623                         // link together the alternate animation
1624                         for (j = 0;j < altmax;j++)
1625                         {
1626                                 tx2 = altanims[j];
1627                                 tx2->animated = true;
1628                                 // the primary/alternate are reversed here
1629                                 tx2->anim_total[0] = altmax;
1630                                 tx2->anim_total[1] = max;
1631                                 for (k = 0;k < 10;k++)
1632                                 {
1633                                         tx2->anim_frames[0][k] = altanims[k];
1634                                         tx2->anim_frames[1][k] = anims[k];
1635                                 }
1636                         }
1637                 }
1638         }
1639 }
1640
1641 static void Mod_Q1BSP_LoadLighting(lump_t *l)
1642 {
1643         int i;
1644         unsigned char *in, *out, *data, d;
1645         char litfilename[MAX_QPATH];
1646         char dlitfilename[MAX_QPATH];
1647         fs_offset_t filesize;
1648         if (loadmodel->brush.ishlbsp) // LordHavoc: load the colored lighting data straight
1649         {
1650                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1651                 for (i=0; i<l->filelen; i++)
1652                         loadmodel->brushq1.lightdata[i] = mod_base[l->fileofs+i] >>= 1;
1653         }
1654         else if (loadmodel->brush.ismcbsp)
1655         {
1656                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1657                 memcpy(loadmodel->brushq1.lightdata, mod_base + l->fileofs, l->filelen);
1658         }
1659         else // LordHavoc: bsp version 29 (normal white lighting)
1660         {
1661                 // LordHavoc: hope is not lost yet, check for a .lit file to load
1662                 strlcpy (litfilename, loadmodel->name, sizeof (litfilename));
1663                 FS_StripExtension (litfilename, litfilename, sizeof (litfilename));
1664                 strlcpy (dlitfilename, litfilename, sizeof (dlitfilename));
1665                 strlcat (litfilename, ".lit", sizeof (litfilename));
1666                 strlcat (dlitfilename, ".dlit", sizeof (dlitfilename));
1667                 data = (unsigned char*) FS_LoadFile(litfilename, tempmempool, false, &filesize);
1668                 if (data)
1669                 {
1670                         if (filesize == (fs_offset_t)(8 + l->filelen * 3) && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1671                         {
1672                                 i = LittleLong(((int *)data)[1]);
1673                                 if (i == 1)
1674                                 {
1675                                         Con_DPrintf("loaded %s\n", litfilename);
1676                                         loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, filesize - 8);
1677                                         memcpy(loadmodel->brushq1.lightdata, data + 8, filesize - 8);
1678                                         Mem_Free(data);
1679                                         data = (unsigned char*) FS_LoadFile(dlitfilename, tempmempool, false, &filesize);
1680                                         if (data)
1681                                         {
1682                                                 if (filesize == (fs_offset_t)(8 + l->filelen * 3) && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1683                                                 {
1684                                                         i = LittleLong(((int *)data)[1]);
1685                                                         if (i == 1)
1686                                                         {
1687                                                                 Con_DPrintf("loaded %s\n", dlitfilename);
1688                                                                 loadmodel->brushq1.nmaplightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, filesize - 8);
1689                                                                 memcpy(loadmodel->brushq1.nmaplightdata, data + 8, filesize - 8);
1690                                                                 loadmodel->brushq3.deluxemapping_modelspace = false;
1691                                                                 loadmodel->brushq3.deluxemapping = true;
1692                                                         }
1693                                                 }
1694                                                 Mem_Free(data);
1695                                                 data = NULL;
1696                                         }
1697                                         return;
1698                                 }
1699                                 else
1700                                         Con_Printf("Unknown .lit file version (%d)\n", i);
1701                         }
1702                         else if (filesize == 8)
1703                                 Con_Print("Empty .lit file, ignoring\n");
1704                         else
1705                                 Con_Printf("Corrupt .lit file (file size %i bytes, should be %i bytes), ignoring\n", (int) filesize, (int) (8 + l->filelen * 3));
1706                         if (data)
1707                         {
1708                                 Mem_Free(data);
1709                                 data = NULL;
1710                         }
1711                 }
1712                 // LordHavoc: oh well, expand the white lighting data
1713                 if (!l->filelen)
1714                         return;
1715                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen*3);
1716                 in = mod_base + l->fileofs;
1717                 out = loadmodel->brushq1.lightdata;
1718                 for (i = 0;i < l->filelen;i++)
1719                 {
1720                         d = *in++;
1721                         *out++ = d;
1722                         *out++ = d;
1723                         *out++ = d;
1724                 }
1725         }
1726 }
1727
1728 static void Mod_Q1BSP_LoadVisibility(lump_t *l)
1729 {
1730         loadmodel->brushq1.num_compressedpvs = 0;
1731         loadmodel->brushq1.data_compressedpvs = NULL;
1732         if (!l->filelen)
1733                 return;
1734         loadmodel->brushq1.num_compressedpvs = l->filelen;
1735         loadmodel->brushq1.data_compressedpvs = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1736         memcpy(loadmodel->brushq1.data_compressedpvs, mod_base + l->fileofs, l->filelen);
1737 }
1738
1739 // used only for HalfLife maps
1740 static void Mod_Q1BSP_ParseWadsFromEntityLump(const char *data)
1741 {
1742         char key[128], value[4096];
1743         char wadname[128];
1744         int i, j, k;
1745         if (!data)
1746                 return;
1747         if (!COM_ParseTokenConsole(&data))
1748                 return; // error
1749         if (com_token[0] != '{')
1750                 return; // error
1751         while (1)
1752         {
1753                 if (!COM_ParseTokenConsole(&data))
1754                         return; // error
1755                 if (com_token[0] == '}')
1756                         break; // end of worldspawn
1757                 if (com_token[0] == '_')
1758                         strlcpy(key, com_token + 1, sizeof(key));
1759                 else
1760                         strlcpy(key, com_token, sizeof(key));
1761                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
1762                         key[strlen(key)-1] = 0;
1763                 if (!COM_ParseTokenConsole(&data))
1764                         return; // error
1765                 dpsnprintf(value, sizeof(value), "%s", com_token);
1766                 if (!strcmp("wad", key)) // for HalfLife maps
1767                 {
1768                         if (loadmodel->brush.ishlbsp)
1769                         {
1770                                 j = 0;
1771                                 for (i = 0;i < (int)sizeof(value);i++)
1772                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
1773                                                 break;
1774                                 if (value[i])
1775                                 {
1776                                         for (;i < (int)sizeof(value);i++)
1777                                         {
1778                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
1779                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
1780                                                         j = i+1;
1781                                                 else if (value[i] == ';' || value[i] == 0)
1782                                                 {
1783                                                         k = value[i];
1784                                                         value[i] = 0;
1785                                                         strlcpy(wadname, "textures/", sizeof(wadname));
1786                                                         strlcat(wadname, &value[j], sizeof(wadname));
1787                                                         W_LoadTextureWadFile(wadname, false);
1788                                                         j = i+1;
1789                                                         if (!k)
1790                                                                 break;
1791                                                 }
1792                                         }
1793                                 }
1794                         }
1795                 }
1796         }
1797 }
1798
1799 static void Mod_Q1BSP_LoadEntities(lump_t *l)
1800 {
1801         loadmodel->brush.entities = NULL;
1802         if (!l->filelen)
1803                 return;
1804         loadmodel->brush.entities = (char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1805         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
1806         if (loadmodel->brush.ishlbsp)
1807                 Mod_Q1BSP_ParseWadsFromEntityLump(loadmodel->brush.entities);
1808 }
1809
1810
1811 static void Mod_Q1BSP_LoadVertexes(lump_t *l)
1812 {
1813         dvertex_t       *in;
1814         mvertex_t       *out;
1815         int                     i, count;
1816
1817         in = (dvertex_t *)(mod_base + l->fileofs);
1818         if (l->filelen % sizeof(*in))
1819                 Host_Error("Mod_Q1BSP_LoadVertexes: funny lump size in %s",loadmodel->name);
1820         count = l->filelen / sizeof(*in);
1821         out = (mvertex_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1822
1823         loadmodel->brushq1.vertexes = out;
1824         loadmodel->brushq1.numvertexes = count;
1825
1826         for ( i=0 ; i<count ; i++, in++, out++)
1827         {
1828                 out->position[0] = LittleFloat(in->point[0]);
1829                 out->position[1] = LittleFloat(in->point[1]);
1830                 out->position[2] = LittleFloat(in->point[2]);
1831         }
1832 }
1833
1834 // The following two functions should be removed and MSG_* or SZ_* function sets adjusted so they
1835 // can be used for this
1836 // REMOVEME
1837 int SB_ReadInt (unsigned char **buffer)
1838 {
1839         int     i;
1840         i = ((*buffer)[0]) + 256*((*buffer)[1]) + 65536*((*buffer)[2]) + 16777216*((*buffer)[3]);
1841         (*buffer) += 4;
1842         return i;
1843 }
1844
1845 // REMOVEME
1846 float SB_ReadFloat (unsigned char **buffer)
1847 {
1848         union
1849         {
1850                 int             i;
1851                 float   f;
1852         } u;
1853
1854         u.i = SB_ReadInt (buffer);
1855         return u.f;
1856 }
1857
1858 static void Mod_Q1BSP_LoadSubmodels(lump_t *l, hullinfo_t *hullinfo)
1859 {
1860         unsigned char           *index;
1861         dmodel_t        *out;
1862         int                     i, j, count;
1863
1864         index = (unsigned char *)(mod_base + l->fileofs);
1865         if (l->filelen % (48+4*hullinfo->filehulls))
1866                 Host_Error ("Mod_Q1BSP_LoadSubmodels: funny lump size in %s", loadmodel->name);
1867
1868         count = l->filelen / (48+4*hullinfo->filehulls);
1869         out = (dmodel_t *)Mem_Alloc (loadmodel->mempool, count*sizeof(*out));
1870
1871         loadmodel->brushq1.submodels = out;
1872         loadmodel->brush.numsubmodels = count;
1873
1874         for (i = 0; i < count; i++, out++)
1875         {
1876         // spread out the mins / maxs by a pixel
1877                 out->mins[0] = SB_ReadFloat (&index) - 1;
1878                 out->mins[1] = SB_ReadFloat (&index) - 1;
1879                 out->mins[2] = SB_ReadFloat (&index) - 1;
1880                 out->maxs[0] = SB_ReadFloat (&index) + 1;
1881                 out->maxs[1] = SB_ReadFloat (&index) + 1;
1882                 out->maxs[2] = SB_ReadFloat (&index) + 1;
1883                 out->origin[0] = SB_ReadFloat (&index);
1884                 out->origin[1] = SB_ReadFloat (&index);
1885                 out->origin[2] = SB_ReadFloat (&index);
1886                 for (j = 0; j < hullinfo->filehulls; j++)
1887                         out->headnode[j] = SB_ReadInt (&index);
1888                 out->visleafs = SB_ReadInt (&index);
1889                 out->firstface = SB_ReadInt (&index);
1890                 out->numfaces = SB_ReadInt (&index);
1891         }
1892 }
1893
1894 static void Mod_Q1BSP_LoadEdges(lump_t *l)
1895 {
1896         dedge_t *in;
1897         medge_t *out;
1898         int     i, count;
1899
1900         in = (dedge_t *)(mod_base + l->fileofs);
1901         if (l->filelen % sizeof(*in))
1902                 Host_Error("Mod_Q1BSP_LoadEdges: funny lump size in %s",loadmodel->name);
1903         count = l->filelen / sizeof(*in);
1904         out = (medge_t *)Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1905
1906         loadmodel->brushq1.edges = out;
1907         loadmodel->brushq1.numedges = count;
1908
1909         for ( i=0 ; i<count ; i++, in++, out++)
1910         {
1911                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
1912                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
1913                 if (out->v[0] >= loadmodel->brushq1.numvertexes || out->v[1] >= loadmodel->brushq1.numvertexes)
1914                 {
1915                         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);
1916                         out->v[0] = 0;
1917                         out->v[1] = 0;
1918                 }
1919         }
1920 }
1921
1922 static void Mod_Q1BSP_LoadTexinfo(lump_t *l)
1923 {
1924         texinfo_t *in;
1925         mtexinfo_t *out;
1926         int i, j, k, count, miptex;
1927
1928         in = (texinfo_t *)(mod_base + l->fileofs);
1929         if (l->filelen % sizeof(*in))
1930                 Host_Error("Mod_Q1BSP_LoadTexinfo: funny lump size in %s",loadmodel->name);
1931         count = l->filelen / sizeof(*in);
1932         out = (mtexinfo_t *)Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1933
1934         loadmodel->brushq1.texinfo = out;
1935         loadmodel->brushq1.numtexinfo = count;
1936
1937         for (i = 0;i < count;i++, in++, out++)
1938         {
1939                 for (k = 0;k < 2;k++)
1940                         for (j = 0;j < 4;j++)
1941                                 out->vecs[k][j] = LittleFloat(in->vecs[k][j]);
1942
1943                 miptex = LittleLong(in->miptex);
1944                 out->flags = LittleLong(in->flags);
1945
1946                 out->texture = NULL;
1947                 if (loadmodel->data_textures)
1948                 {
1949                         if ((unsigned int) miptex >= (unsigned int) loadmodel->num_textures)
1950                                 Con_Printf("error in model \"%s\": invalid miptex index %i(of %i)\n", loadmodel->name, miptex, loadmodel->num_textures);
1951                         else
1952                                 out->texture = loadmodel->data_textures + miptex;
1953                 }
1954                 if (out->flags & TEX_SPECIAL)
1955                 {
1956                         // if texture chosen is NULL or the shader needs a lightmap,
1957                         // force to notexture water shader
1958                         if (out->texture == NULL || out->texture->basematerialflags & MATERIALFLAG_WALL)
1959                                 out->texture = loadmodel->data_textures + (loadmodel->num_textures - 1);
1960                 }
1961                 else
1962                 {
1963                         // if texture chosen is NULL, force to notexture
1964                         if (out->texture == NULL)
1965                                 out->texture = loadmodel->data_textures + (loadmodel->num_textures - 2);
1966                 }
1967         }
1968 }
1969
1970 #if 0
1971 void BoundPoly(int numverts, float *verts, vec3_t mins, vec3_t maxs)
1972 {
1973         int             i, j;
1974         float   *v;
1975
1976         mins[0] = mins[1] = mins[2] = 9999;
1977         maxs[0] = maxs[1] = maxs[2] = -9999;
1978         v = verts;
1979         for (i = 0;i < numverts;i++)
1980         {
1981                 for (j = 0;j < 3;j++, v++)
1982                 {
1983                         if (*v < mins[j])
1984                                 mins[j] = *v;
1985                         if (*v > maxs[j])
1986                                 maxs[j] = *v;
1987                 }
1988         }
1989 }
1990
1991 #define MAX_SUBDIVPOLYTRIANGLES 4096
1992 #define MAX_SUBDIVPOLYVERTS(MAX_SUBDIVPOLYTRIANGLES * 3)
1993
1994 static int subdivpolyverts, subdivpolytriangles;
1995 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
1996 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
1997
1998 static int subdivpolylookupvert(vec3_t v)
1999 {
2000         int i;
2001         for (i = 0;i < subdivpolyverts;i++)
2002                 if (subdivpolyvert[i][0] == v[0]
2003                  && subdivpolyvert[i][1] == v[1]
2004                  && subdivpolyvert[i][2] == v[2])
2005                         return i;
2006         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
2007                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
2008         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
2009         return subdivpolyverts++;
2010 }
2011
2012 static void SubdividePolygon(int numverts, float *verts)
2013 {
2014         int             i, i1, i2, i3, f, b, c, p;
2015         vec3_t  mins, maxs, front[256], back[256];
2016         float   m, *pv, *cv, dist[256], frac;
2017
2018         if (numverts > 250)
2019                 Host_Error("SubdividePolygon: ran out of verts in buffer");
2020
2021         BoundPoly(numverts, verts, mins, maxs);
2022
2023         for (i = 0;i < 3;i++)
2024         {
2025                 m = (mins[i] + maxs[i]) * 0.5;
2026                 m = r_subdivide_size.value * floor(m/r_subdivide_size.value + 0.5);
2027                 if (maxs[i] - m < 8)
2028                         continue;
2029                 if (m - mins[i] < 8)
2030                         continue;
2031
2032                 // cut it
2033                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
2034                         dist[c] = cv[i] - m;
2035
2036                 f = b = 0;
2037                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
2038                 {
2039                         if (dist[p] >= 0)
2040                         {
2041                                 VectorCopy(pv, front[f]);
2042                                 f++;
2043                         }
2044                         if (dist[p] <= 0)
2045                         {
2046                                 VectorCopy(pv, back[b]);
2047                                 b++;
2048                         }
2049                         if (dist[p] == 0 || dist[c] == 0)
2050                                 continue;
2051                         if ((dist[p] > 0) != (dist[c] > 0) )
2052                         {
2053                                 // clip point
2054                                 frac = dist[p] / (dist[p] - dist[c]);
2055                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
2056                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
2057                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
2058                                 f++;
2059                                 b++;
2060                         }
2061                 }
2062
2063                 SubdividePolygon(f, front[0]);
2064                 SubdividePolygon(b, back[0]);
2065                 return;
2066         }
2067
2068         i1 = subdivpolylookupvert(verts);
2069         i2 = subdivpolylookupvert(verts + 3);
2070         for (i = 2;i < numverts;i++)
2071         {
2072                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
2073                 {
2074                         Con_Print("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
2075                         return;
2076                 }
2077
2078                 i3 = subdivpolylookupvert(verts + i * 3);
2079                 subdivpolyindex[subdivpolytriangles][0] = i1;
2080                 subdivpolyindex[subdivpolytriangles][1] = i2;
2081                 subdivpolyindex[subdivpolytriangles][2] = i3;
2082                 i2 = i3;
2083                 subdivpolytriangles++;
2084         }
2085 }
2086
2087 //Breaks a polygon up along axial 64 unit
2088 //boundaries so that turbulent and sky warps
2089 //can be done reasonably.
2090 static void Mod_Q1BSP_GenerateWarpMesh(msurface_t *surface)
2091 {
2092         int i, j;
2093         surfvertex_t *v;
2094         surfmesh_t *mesh;
2095
2096         subdivpolytriangles = 0;
2097         subdivpolyverts = 0;
2098         SubdividePolygon(surface->num_vertices, (surface->mesh->data_vertex3f + 3 * surface->num_firstvertex));
2099         if (subdivpolytriangles < 1)
2100                 Host_Error("Mod_Q1BSP_GenerateWarpMesh: no triangles?");
2101
2102         surface->mesh = mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + subdivpolytriangles * sizeof(int[3]) + subdivpolyverts * sizeof(surfvertex_t));
2103         mesh->num_vertices = subdivpolyverts;
2104         mesh->num_triangles = subdivpolytriangles;
2105         mesh->vertex = (surfvertex_t *)(mesh + 1);
2106         mesh->index = (int *)(mesh->vertex + mesh->num_vertices);
2107         memset(mesh->vertex, 0, mesh->num_vertices * sizeof(surfvertex_t));
2108
2109         for (i = 0;i < mesh->num_triangles;i++)
2110                 for (j = 0;j < 3;j++)
2111                         mesh->index[i*3+j] = subdivpolyindex[i][j];
2112
2113         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
2114         {
2115                 VectorCopy(subdivpolyvert[i], v->v);
2116                 v->st[0] = DotProduct(v->v, surface->lightmapinfo->texinfo->vecs[0]);
2117                 v->st[1] = DotProduct(v->v, surface->lightmapinfo->texinfo->vecs[1]);
2118         }
2119 }
2120 #endif
2121
2122 static qboolean Mod_Q1BSP_AllocLightmapBlock(int *lineused, int totalwidth, int totalheight, int blockwidth, int blockheight, int *outx, int *outy)
2123 {
2124         int y, x2, y2;
2125         int bestx = totalwidth, besty = 0;
2126         // find the left-most space we can find
2127         for (y = 0;y <= totalheight - blockheight;y++)
2128         {
2129                 x2 = 0;
2130                 for (y2 = 0;y2 < blockheight;y2++)
2131                         x2 = max(x2, lineused[y+y2]);
2132                 if (bestx > x2)
2133                 {
2134                         bestx = x2;
2135                         besty = y;
2136                 }
2137         }
2138         // if the best was not good enough, return failure
2139         if (bestx > totalwidth - blockwidth)
2140                 return false;
2141         // we found a good spot
2142         if (outx)
2143                 *outx = bestx;
2144         if (outy)
2145                 *outy = besty;
2146         // now mark the space used
2147         for (y2 = 0;y2 < blockheight;y2++)
2148                 lineused[besty+y2] = bestx + blockwidth;
2149         // return success
2150         return true;
2151 }
2152
2153 static void Mod_Q1BSP_LoadFaces(lump_t *l)
2154 {
2155         dface_t *in;
2156         msurface_t *surface;
2157         int i, j, count, surfacenum, planenum, smax, tmax, ssize, tsize, firstedge, numedges, totalverts, totaltris, lightmapnumber;
2158         float texmins[2], texmaxs[2], val, lightmaptexcoordscale;
2159 #define LIGHTMAPSIZE 256
2160         rtexture_t *lightmaptexture, *deluxemaptexture;
2161         int lightmap_lineused[LIGHTMAPSIZE];
2162
2163         in = (dface_t *)(mod_base + l->fileofs);
2164         if (l->filelen % sizeof(*in))
2165                 Host_Error("Mod_Q1BSP_LoadFaces: funny lump size in %s",loadmodel->name);
2166         count = l->filelen / sizeof(*in);
2167         loadmodel->data_surfaces = (msurface_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_t));
2168         loadmodel->data_surfaces_lightmapinfo = (msurface_lightmapinfo_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_lightmapinfo_t));
2169
2170         loadmodel->num_surfaces = count;
2171
2172         totalverts = 0;
2173         totaltris = 0;
2174         for (surfacenum = 0, in = (dface_t *)(mod_base + l->fileofs);surfacenum < count;surfacenum++, in++)
2175         {
2176                 numedges = LittleShort(in->numedges);
2177                 totalverts += numedges;
2178                 totaltris += numedges - 2;
2179         }
2180
2181         Mod_AllocSurfMesh(loadmodel->mempool, totalverts, totaltris, true, false, false);
2182
2183         lightmaptexture = NULL;
2184         deluxemaptexture = r_texture_blanknormalmap;
2185         lightmapnumber = 1;
2186         lightmaptexcoordscale = 1.0f / (float)LIGHTMAPSIZE;
2187
2188         totalverts = 0;
2189         totaltris = 0;
2190         for (surfacenum = 0, in = (dface_t *)(mod_base + l->fileofs), surface = loadmodel->data_surfaces;surfacenum < count;surfacenum++, in++, surface++)
2191         {
2192                 surface->lightmapinfo = loadmodel->data_surfaces_lightmapinfo + surfacenum;
2193
2194                 // FIXME: validate edges, texinfo, etc?
2195                 firstedge = LittleLong(in->firstedge);
2196                 numedges = LittleShort(in->numedges);
2197                 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)
2198                         Host_Error("Mod_Q1BSP_LoadFaces: invalid edge range (firstedge %i, numedges %i, model edges %i)", firstedge, numedges, loadmodel->brushq1.numsurfedges);
2199                 i = LittleShort(in->texinfo);
2200                 if ((unsigned int) i >= (unsigned int) loadmodel->brushq1.numtexinfo)
2201                         Host_Error("Mod_Q1BSP_LoadFaces: invalid texinfo index %i(model has %i texinfos)", i, loadmodel->brushq1.numtexinfo);
2202                 surface->lightmapinfo->texinfo = loadmodel->brushq1.texinfo + i;
2203                 surface->texture = surface->lightmapinfo->texinfo->texture;
2204
2205                 planenum = LittleShort(in->planenum);
2206                 if ((unsigned int) planenum >= (unsigned int) loadmodel->brush.num_planes)
2207                         Host_Error("Mod_Q1BSP_LoadFaces: invalid plane index %i (model has %i planes)", planenum, loadmodel->brush.num_planes);
2208
2209                 //surface->flags = surface->texture->flags;
2210                 //if (LittleShort(in->side))
2211                 //      surface->flags |= SURF_PLANEBACK;
2212                 //surface->plane = loadmodel->brush.data_planes + planenum;
2213
2214                 surface->num_firstvertex = totalverts;
2215                 surface->num_vertices = numedges;
2216                 surface->num_firsttriangle = totaltris;
2217                 surface->num_triangles = numedges - 2;
2218                 totalverts += numedges;
2219                 totaltris += numedges - 2;
2220
2221                 // convert edges back to a normal polygon
2222                 for (i = 0;i < surface->num_vertices;i++)
2223                 {
2224                         int lindex = loadmodel->brushq1.surfedges[firstedge + i];
2225                         float s, t;
2226                         if (lindex > 0)
2227                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[lindex].v[0]].position, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3);
2228                         else
2229                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[-lindex].v[1]].position, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3);
2230                         s = DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[0]) + surface->lightmapinfo->texinfo->vecs[0][3];
2231                         t = DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[1]) + surface->lightmapinfo->texinfo->vecs[1][3];
2232                         (loadmodel->surfmesh.data_texcoordtexture2f + 2 * surface->num_firstvertex)[i * 2 + 0] = s / surface->texture->width;
2233                         (loadmodel->surfmesh.data_texcoordtexture2f + 2 * surface->num_firstvertex)[i * 2 + 1] = t / surface->texture->height;
2234                         (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 0] = 0;
2235                         (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 1] = 0;
2236                         (loadmodel->surfmesh.data_lightmapoffsets + surface->num_firstvertex)[i] = 0;
2237                 }
2238
2239                 for (i = 0;i < surface->num_triangles;i++)
2240                 {
2241                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 0] = 0 + surface->num_firstvertex;
2242                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 1] = i + 1 + surface->num_firstvertex;
2243                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 2] = i + 2 + surface->num_firstvertex;
2244                 }
2245
2246                 // compile additional data about the surface geometry
2247                 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);
2248                 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);
2249                 BoxFromPoints(surface->mins, surface->maxs, surface->num_vertices, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex));
2250
2251                 // generate surface extents information
2252                 texmins[0] = texmaxs[0] = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex), surface->lightmapinfo->texinfo->vecs[0]) + surface->lightmapinfo->texinfo->vecs[0][3];
2253                 texmins[1] = texmaxs[1] = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex), surface->lightmapinfo->texinfo->vecs[1]) + surface->lightmapinfo->texinfo->vecs[1][3];
2254                 for (i = 1;i < surface->num_vertices;i++)
2255                 {
2256                         for (j = 0;j < 2;j++)
2257                         {
2258                                 val = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3, surface->lightmapinfo->texinfo->vecs[j]) + surface->lightmapinfo->texinfo->vecs[j][3];
2259                                 texmins[j] = min(texmins[j], val);
2260                                 texmaxs[j] = max(texmaxs[j], val);
2261                         }
2262                 }
2263                 for (i = 0;i < 2;i++)
2264                 {
2265                         surface->lightmapinfo->texturemins[i] = (int) floor(texmins[i] / 16.0) * 16;
2266                         surface->lightmapinfo->extents[i] = (int) ceil(texmaxs[i] / 16.0) * 16 - surface->lightmapinfo->texturemins[i];
2267                 }
2268
2269                 smax = surface->lightmapinfo->extents[0] >> 4;
2270                 tmax = surface->lightmapinfo->extents[1] >> 4;
2271                 ssize = (surface->lightmapinfo->extents[0] >> 4) + 1;
2272                 tsize = (surface->lightmapinfo->extents[1] >> 4) + 1;
2273
2274                 // lighting info
2275                 for (i = 0;i < MAXLIGHTMAPS;i++)
2276                         surface->lightmapinfo->styles[i] = in->styles[i];
2277                 surface->lightmaptexture = NULL;
2278                 surface->deluxemaptexture = r_texture_blanknormalmap;
2279                 i = LittleLong(in->lightofs);
2280                 if (i == -1)
2281                 {
2282                         surface->lightmapinfo->samples = NULL;
2283                         // give non-lightmapped water a 1x white lightmap
2284                         if ((surface->texture->basematerialflags & MATERIALFLAG_WATER) && (surface->lightmapinfo->texinfo->flags & TEX_SPECIAL) && ssize <= 256 && tsize <= 256)
2285                         {
2286                                 surface->lightmapinfo->samples = (unsigned char *)Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
2287                                 surface->lightmapinfo->styles[0] = 0;
2288                                 memset(surface->lightmapinfo->samples, 128, ssize * tsize * 3);
2289                         }
2290                 }
2291                 else if (loadmodel->brush.ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
2292                         surface->lightmapinfo->samples = loadmodel->brushq1.lightdata + i;
2293                 else // LordHavoc: white lighting (bsp version 29)
2294                 {
2295                         surface->lightmapinfo->samples = loadmodel->brushq1.lightdata + (i * 3);
2296                         if (loadmodel->brushq1.nmaplightdata)
2297                                 surface->lightmapinfo->nmapsamples = loadmodel->brushq1.nmaplightdata + (i * 3);
2298                 }
2299
2300                 // check if we should apply a lightmap to this
2301                 if (!(surface->lightmapinfo->texinfo->flags & TEX_SPECIAL) || surface->lightmapinfo->samples)
2302                 {
2303                         int i, iu, iv, lightmapx, lightmapy;
2304                         float u, v, ubase, vbase, uscale, vscale;
2305
2306                         if (ssize > 256 || tsize > 256)
2307                                 Host_Error("Bad surface extents");
2308                         // force lightmap upload on first time seeing the surface
2309                         surface->cached_dlight = true;
2310                         // stainmap for permanent marks on walls
2311                         surface->lightmapinfo->stainsamples = (unsigned char *)Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
2312                         // clear to white
2313                         memset(surface->lightmapinfo->stainsamples, 255, ssize * tsize * 3);
2314
2315                         // find a place for this lightmap
2316                         if (!lightmaptexture || !Mod_Q1BSP_AllocLightmapBlock(lightmap_lineused, LIGHTMAPSIZE, LIGHTMAPSIZE, ssize, tsize, &lightmapx, &lightmapy))
2317                         {
2318                                 // allocate a texture pool if we need it
2319                                 if (loadmodel->texturepool == NULL && cls.state != ca_dedicated)
2320                                         loadmodel->texturepool = R_AllocTexturePool();
2321                                 // could not find room, make a new lightmap
2322                                 lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, va("lightmap%i", lightmapnumber), LIGHTMAPSIZE, LIGHTMAPSIZE, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
2323                                 if (loadmodel->brushq1.nmaplightdata)
2324                                         deluxemaptexture = R_LoadTexture2D(loadmodel->texturepool, va("deluxemap%i", lightmapnumber), LIGHTMAPSIZE, LIGHTMAPSIZE, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
2325                                 lightmapnumber++;
2326                                 memset(lightmap_lineused, 0, sizeof(lightmap_lineused));
2327                                 Mod_Q1BSP_AllocLightmapBlock(lightmap_lineused, LIGHTMAPSIZE, LIGHTMAPSIZE, ssize, tsize, &lightmapx, &lightmapy);
2328                         }
2329
2330                         surface->lightmaptexture = lightmaptexture;
2331                         surface->deluxemaptexture = deluxemaptexture;
2332                         surface->lightmapinfo->lightmaporigin[0] = lightmapx;
2333                         surface->lightmapinfo->lightmaporigin[1] = lightmapy;
2334
2335                         ubase = lightmapx * lightmaptexcoordscale;
2336                         vbase = lightmapy * lightmaptexcoordscale;
2337                         uscale = lightmaptexcoordscale;
2338                         vscale = lightmaptexcoordscale;
2339
2340                         for (i = 0;i < surface->num_vertices;i++)
2341                         {
2342                                 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);
2343                                 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);
2344                                 (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 0] = u * uscale + ubase;
2345                                 (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 1] = v * vscale + vbase;
2346                                 // LordHavoc: calc lightmap data offset for vertex lighting to use
2347                                 iu = (int) u;
2348                                 iv = (int) v;
2349                                 (loadmodel->surfmesh.data_lightmapoffsets + surface->num_firstvertex)[i] = (bound(0, iv, tmax) * ssize + bound(0, iu, smax)) * 3;
2350                         }
2351                 }
2352         }
2353 }
2354
2355 static void Mod_Q1BSP_LoadNodes_RecursiveSetParent(mnode_t *node, mnode_t *parent)
2356 {
2357         //if (node->parent)
2358         //      Host_Error("Mod_Q1BSP_LoadNodes_RecursiveSetParent: runaway recursion");
2359         node->parent = parent;
2360         if (node->plane)
2361         {
2362                 // this is a node, recurse to children
2363                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
2364                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
2365                 // combine supercontents of children
2366                 node->combinedsupercontents = node->children[0]->combinedsupercontents | node->children[1]->combinedsupercontents;
2367         }
2368         else
2369         {
2370                 int j;
2371                 mleaf_t *leaf = (mleaf_t *)node;
2372                 // if this is a leaf, calculate supercontents mask from all collidable
2373                 // primitives in the leaf (brushes and collision surfaces)
2374                 // also flag if the leaf contains any collision surfaces
2375                 leaf->combinedsupercontents = 0;
2376                 // combine the supercontents values of all brushes in this leaf
2377                 for (j = 0;j < leaf->numleafbrushes;j++)
2378                         leaf->combinedsupercontents |= loadmodel->brush.data_brushes[leaf->firstleafbrush[j]].texture->supercontents;
2379                 // check if this leaf contains any collision surfaces (q3 patches)
2380                 for (j = 0;j < leaf->numleafsurfaces;j++)
2381                 {
2382                         msurface_t *surface = loadmodel->data_surfaces + leaf->firstleafsurface[j];
2383                         if (surface->num_collisiontriangles)
2384                         {
2385                                 leaf->containscollisionsurfaces = true;
2386                                 leaf->combinedsupercontents |= surface->texture->supercontents;
2387                         }
2388                 }
2389         }
2390 }
2391
2392 static void Mod_Q1BSP_LoadNodes(lump_t *l)
2393 {
2394         int                     i, j, count, p;
2395         dnode_t         *in;
2396         mnode_t         *out;
2397
2398         in = (dnode_t *)(mod_base + l->fileofs);
2399         if (l->filelen % sizeof(*in))
2400                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
2401         count = l->filelen / sizeof(*in);
2402         out = (mnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2403
2404         loadmodel->brush.data_nodes = out;
2405         loadmodel->brush.num_nodes = count;
2406
2407         for ( i=0 ; i<count ; i++, in++, out++)
2408         {
2409                 for (j=0 ; j<3 ; j++)
2410                 {
2411                         out->mins[j] = LittleShort(in->mins[j]);
2412                         out->maxs[j] = LittleShort(in->maxs[j]);
2413                 }
2414
2415                 p = LittleLong(in->planenum);
2416                 out->plane = loadmodel->brush.data_planes + p;
2417
2418                 out->firstsurface = LittleShort(in->firstface);
2419                 out->numsurfaces = LittleShort(in->numfaces);
2420
2421                 for (j=0 ; j<2 ; j++)
2422                 {
2423                         p = LittleShort(in->children[j]);
2424                         if (p >= 0)
2425                                 out->children[j] = loadmodel->brush.data_nodes + p;
2426                         else
2427                                 out->children[j] = (mnode_t *)(loadmodel->brush.data_leafs + (-1 - p));
2428                 }
2429         }
2430
2431         Mod_Q1BSP_LoadNodes_RecursiveSetParent(loadmodel->brush.data_nodes, NULL);      // sets nodes and leafs
2432 }
2433
2434 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
2435 {
2436         dleaf_t *in;
2437         mleaf_t *out;
2438         int i, j, count, p;
2439
2440         in = (dleaf_t *)(mod_base + l->fileofs);
2441         if (l->filelen % sizeof(*in))
2442                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
2443         count = l->filelen / sizeof(*in);
2444         out = (mleaf_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2445
2446         loadmodel->brush.data_leafs = out;
2447         loadmodel->brush.num_leafs = count;
2448         // get visleafs from the submodel data
2449         loadmodel->brush.num_pvsclusters = loadmodel->brushq1.submodels[0].visleafs;
2450         loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters+7)>>3;
2451         loadmodel->brush.data_pvsclusters = (unsigned char *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2452         memset(loadmodel->brush.data_pvsclusters, 0xFF, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2453
2454         for ( i=0 ; i<count ; i++, in++, out++)
2455         {
2456                 for (j=0 ; j<3 ; j++)
2457                 {
2458                         out->mins[j] = LittleShort(in->mins[j]);
2459                         out->maxs[j] = LittleShort(in->maxs[j]);
2460                 }
2461
2462                 // FIXME: this function could really benefit from some error checking
2463
2464                 out->contents = LittleLong(in->contents);
2465
2466                 out->firstleafsurface = loadmodel->brush.data_leafsurfaces + LittleShort(in->firstmarksurface);
2467                 out->numleafsurfaces = LittleShort(in->nummarksurfaces);
2468                 if (out->firstleafsurface < 0 || LittleShort(in->firstmarksurface) + out->numleafsurfaces > loadmodel->brush.num_leafsurfaces)
2469                 {
2470                         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);
2471                         out->firstleafsurface = NULL;
2472                         out->numleafsurfaces = 0;
2473                 }
2474
2475                 out->clusterindex = i - 1;
2476                 if (out->clusterindex >= loadmodel->brush.num_pvsclusters)
2477                         out->clusterindex = -1;
2478
2479                 p = LittleLong(in->visofs);
2480                 // ignore visofs errors on leaf 0 (solid)
2481                 if (p >= 0 && out->clusterindex >= 0)
2482                 {
2483                         if (p >= loadmodel->brushq1.num_compressedpvs)
2484                                 Con_Print("Mod_Q1BSP_LoadLeafs: invalid visofs\n");
2485                         else
2486                                 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);
2487                 }
2488
2489                 for (j = 0;j < 4;j++)
2490                         out->ambient_sound_level[j] = in->ambient_level[j];
2491
2492                 // FIXME: Insert caustics here
2493         }
2494 }
2495
2496 qboolean Mod_Q1BSP_CheckWaterAlphaSupport(void)
2497 {
2498         int i, j;
2499         mleaf_t *leaf;
2500         const unsigned char *pvs;
2501         // check all liquid leafs to see if they can see into empty leafs, if any
2502         // can we can assume this map supports r_wateralpha
2503         for (i = 0, leaf = loadmodel->brush.data_leafs;i < loadmodel->brush.num_leafs;i++, leaf++)
2504         {
2505                 if ((leaf->contents == CONTENTS_WATER || leaf->contents == CONTENTS_SLIME) && (leaf->clusterindex >= 0 && loadmodel->brush.data_pvsclusters))
2506                 {
2507                         pvs = loadmodel->brush.data_pvsclusters + leaf->clusterindex * loadmodel->brush.num_pvsclusterbytes;
2508                         for (j = 0;j < loadmodel->brush.num_leafs;j++)
2509                                 if (CHECKPVSBIT(pvs, loadmodel->brush.data_leafs[j].clusterindex) && loadmodel->brush.data_leafs[j].contents == CONTENTS_EMPTY)
2510                                         return true;
2511                 }
2512         }
2513         return false;
2514 }
2515
2516 static void Mod_Q1BSP_LoadClipnodes(lump_t *l, hullinfo_t *hullinfo)
2517 {
2518         dclipnode_t *in, *out;
2519         int                     i, count;
2520         hull_t          *hull;
2521
2522         in = (dclipnode_t *)(mod_base + l->fileofs);
2523         if (l->filelen % sizeof(*in))
2524                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2525         count = l->filelen / sizeof(*in);
2526         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2527
2528         loadmodel->brushq1.clipnodes = out;
2529         loadmodel->brushq1.numclipnodes = count;
2530
2531         for (i = 1; i < hullinfo->numhulls; i++)
2532         {
2533                 hull = &loadmodel->brushq1.hulls[i];
2534                 hull->clipnodes = out;
2535                 hull->firstclipnode = 0;
2536                 hull->lastclipnode = count-1;
2537                 hull->planes = loadmodel->brush.data_planes;
2538                 hull->clip_mins[0] = hullinfo->hullsizes[i][0][0];
2539                 hull->clip_mins[1] = hullinfo->hullsizes[i][0][1];
2540                 hull->clip_mins[2] = hullinfo->hullsizes[i][0][2];
2541                 hull->clip_maxs[0] = hullinfo->hullsizes[i][1][0];
2542                 hull->clip_maxs[1] = hullinfo->hullsizes[i][1][1];
2543                 hull->clip_maxs[2] = hullinfo->hullsizes[i][1][2];
2544                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2545         }
2546
2547         for (i=0 ; i<count ; i++, out++, in++)
2548         {
2549                 out->planenum = LittleLong(in->planenum);
2550                 out->children[0] = LittleShort(in->children[0]);
2551                 out->children[1] = LittleShort(in->children[1]);
2552                 if (out->planenum < 0 || out->planenum >= loadmodel->brush.num_planes)
2553                         Host_Error("Corrupt clipping hull(out of range planenum)");
2554                 if (out->children[0] >= count || out->children[1] >= count)
2555                         Host_Error("Corrupt clipping hull(out of range child)");
2556         }
2557 }
2558
2559 //Duplicate the drawing hull structure as a clipping hull
2560 static void Mod_Q1BSP_MakeHull0(void)
2561 {
2562         mnode_t         *in;
2563         dclipnode_t *out;
2564         int                     i;
2565         hull_t          *hull;
2566
2567         hull = &loadmodel->brushq1.hulls[0];
2568
2569         in = loadmodel->brush.data_nodes;
2570         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_nodes * sizeof(dclipnode_t));
2571
2572         hull->clipnodes = out;
2573         hull->firstclipnode = 0;
2574         hull->lastclipnode = loadmodel->brush.num_nodes - 1;
2575         hull->planes = loadmodel->brush.data_planes;
2576
2577         for (i = 0;i < loadmodel->brush.num_nodes;i++, out++, in++)
2578         {
2579                 out->planenum = in->plane - loadmodel->brush.data_planes;
2580                 out->children[0] = in->children[0]->plane ? in->children[0] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[0])->contents;
2581                 out->children[1] = in->children[1]->plane ? in->children[1] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[1])->contents;
2582         }
2583 }
2584
2585 static void Mod_Q1BSP_LoadLeaffaces(lump_t *l)
2586 {
2587         int i, j;
2588         short *in;
2589
2590         in = (short *)(mod_base + l->fileofs);
2591         if (l->filelen % sizeof(*in))
2592                 Host_Error("Mod_Q1BSP_LoadLeaffaces: funny lump size in %s",loadmodel->name);
2593         loadmodel->brush.num_leafsurfaces = l->filelen / sizeof(*in);
2594         loadmodel->brush.data_leafsurfaces = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_leafsurfaces * sizeof(int));
2595
2596         for (i = 0;i < loadmodel->brush.num_leafsurfaces;i++)
2597         {
2598                 j = (unsigned) LittleShort(in[i]);
2599                 if (j >= loadmodel->num_surfaces)
2600                         Host_Error("Mod_Q1BSP_LoadLeaffaces: bad surface number");
2601                 loadmodel->brush.data_leafsurfaces[i] = j;
2602         }
2603 }
2604
2605 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2606 {
2607         int             i;
2608         int             *in;
2609
2610         in = (int *)(mod_base + l->fileofs);
2611         if (l->filelen % sizeof(*in))
2612                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2613         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2614         loadmodel->brushq1.surfedges = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2615
2616         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2617                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2618 }
2619
2620
2621 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2622 {
2623         int                     i;
2624         mplane_t        *out;
2625         dplane_t        *in;
2626
2627         in = (dplane_t *)(mod_base + l->fileofs);
2628         if (l->filelen % sizeof(*in))
2629                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2630
2631         loadmodel->brush.num_planes = l->filelen / sizeof(*in);
2632         loadmodel->brush.data_planes = out = (mplane_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_planes * sizeof(*out));
2633
2634         for (i = 0;i < loadmodel->brush.num_planes;i++, in++, out++)
2635         {
2636                 out->normal[0] = LittleFloat(in->normal[0]);
2637                 out->normal[1] = LittleFloat(in->normal[1]);
2638                 out->normal[2] = LittleFloat(in->normal[2]);
2639                 out->dist = LittleFloat(in->dist);
2640
2641                 PlaneClassify(out);
2642         }
2643 }
2644
2645 static void Mod_Q1BSP_LoadMapBrushes(void)
2646 {
2647 #if 0
2648 // unfinished
2649         int submodel, numbrushes;
2650         qboolean firstbrush;
2651         char *text, *maptext;
2652         char mapfilename[MAX_QPATH];
2653         FS_StripExtension (loadmodel->name, mapfilename, sizeof (mapfilename));
2654         strlcat (mapfilename, ".map", sizeof (mapfilename));
2655         maptext = (unsigned char*) FS_LoadFile(mapfilename, tempmempool, false, NULL);
2656         if (!maptext)
2657                 return;
2658         text = maptext;
2659         if (!COM_ParseTokenConsole(&data))
2660                 return; // error
2661         submodel = 0;
2662         for (;;)
2663         {
2664                 if (!COM_ParseTokenConsole(&data))
2665                         break;
2666                 if (com_token[0] != '{')
2667                         return; // error
2668                 // entity
2669                 firstbrush = true;
2670                 numbrushes = 0;
2671                 maxbrushes = 256;
2672                 brushes = Mem_Alloc(loadmodel->mempool, maxbrushes * sizeof(mbrush_t));
2673                 for (;;)
2674                 {
2675                         if (!COM_ParseTokenConsole(&data))
2676                                 return; // error
2677                         if (com_token[0] == '}')
2678                                 break; // end of entity
2679                         if (com_token[0] == '{')
2680                         {
2681                                 // brush
2682                                 if (firstbrush)
2683                                 {
2684                                         if (submodel)
2685                                         {
2686                                                 if (submodel > loadmodel->brush.numsubmodels)
2687                                                 {
2688                                                         Con_Printf("Mod_Q1BSP_LoadMapBrushes: .map has more submodels than .bsp!\n");
2689                                                         model = NULL;
2690                                                 }
2691                                                 else
2692                                                         model = loadmodel->brush.submodels[submodel];
2693                                         }
2694                                         else
2695                                                 model = loadmodel;
2696                                 }
2697                                 for (;;)
2698                                 {
2699                                         if (!COM_ParseTokenConsole(&data))
2700                                                 return; // error
2701                                         if (com_token[0] == '}')
2702                                                 break; // end of brush
2703                                         // each brush face should be this format:
2704                                         // ( x y z ) ( x y z ) ( x y z ) texture scroll_s scroll_t rotateangle scale_s scale_t
2705                                         // FIXME: support hl .map format
2706                                         for (pointnum = 0;pointnum < 3;pointnum++)
2707                                         {
2708                                                 COM_ParseTokenConsole(&data);
2709                                                 for (componentnum = 0;componentnum < 3;componentnum++)
2710                                                 {
2711                                                         COM_ParseTokenConsole(&data);
2712                                                         point[pointnum][componentnum] = atof(com_token);
2713                                                 }
2714                                                 COM_ParseTokenConsole(&data);
2715                                         }
2716                                         COM_ParseTokenConsole(&data);
2717                                         strlcpy(facetexture, com_token, sizeof(facetexture));
2718                                         COM_ParseTokenConsole(&data);
2719                                         //scroll_s = atof(com_token);
2720                                         COM_ParseTokenConsole(&data);
2721                                         //scroll_t = atof(com_token);
2722                                         COM_ParseTokenConsole(&data);
2723                                         //rotate = atof(com_token);
2724                                         COM_ParseTokenConsole(&data);
2725                                         //scale_s = atof(com_token);
2726                                         COM_ParseTokenConsole(&data);
2727                                         //scale_t = atof(com_token);
2728                                         TriangleNormal(point[0], point[1], point[2], planenormal);
2729                                         VectorNormalizeDouble(planenormal);
2730                                         planedist = DotProduct(point[0], planenormal);
2731                                         //ChooseTexturePlane(planenormal, texturevector[0], texturevector[1]);
2732                                 }
2733                                 continue;
2734                         }
2735                 }
2736         }
2737 #endif
2738 }
2739
2740
2741 #define MAX_PORTALPOINTS 64
2742
2743 typedef struct portal_s
2744 {
2745         mplane_t plane;
2746         mnode_t *nodes[2];              // [0] = front side of plane
2747         struct portal_s *next[2];
2748         int numpoints;
2749         double points[3*MAX_PORTALPOINTS];
2750         struct portal_s *chain; // all portals are linked into a list
2751 }
2752 portal_t;
2753
2754 static portal_t *portalchain;
2755
2756 /*
2757 ===========
2758 AllocPortal
2759 ===========
2760 */
2761 static portal_t *AllocPortal(void)
2762 {
2763         portal_t *p;
2764         p = (portal_t *)Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2765         p->chain = portalchain;
2766         portalchain = p;
2767         return p;
2768 }
2769
2770 static void FreePortal(portal_t *p)
2771 {
2772         Mem_Free(p);
2773 }
2774
2775 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2776 {
2777         // process only nodes (leafs already had their box calculated)
2778         if (!node->plane)
2779                 return;
2780
2781         // calculate children first
2782         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2783         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2784
2785         // make combined bounding box from children
2786         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2787         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2788         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2789         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2790         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2791         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2792 }
2793
2794 static void Mod_Q1BSP_FinalizePortals(void)
2795 {
2796         int i, j, numportals, numpoints;
2797         portal_t *p, *pnext;
2798         mportal_t *portal;
2799         mvertex_t *point;
2800         mleaf_t *leaf, *endleaf;
2801
2802         // tally up portal and point counts and recalculate bounding boxes for all
2803         // leafs (because qbsp is very sloppy)
2804         leaf = loadmodel->brush.data_leafs;
2805         endleaf = leaf + loadmodel->brush.num_leafs;
2806         for (;leaf < endleaf;leaf++)
2807         {
2808                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2809                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2810         }
2811         p = portalchain;
2812         numportals = 0;
2813         numpoints = 0;
2814         while (p)
2815         {
2816                 // note: this check must match the one below or it will usually corrupt memory
2817                 // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
2818                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1] && ((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2819                 {
2820                         numportals += 2;
2821                         numpoints += p->numpoints * 2;
2822                 }
2823                 p = p->chain;
2824         }
2825         loadmodel->brush.data_portals = (mportal_t *)Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2826         loadmodel->brush.num_portals = numportals;
2827         loadmodel->brush.data_portalpoints = (mvertex_t *)((unsigned char *) loadmodel->brush.data_portals + numportals * sizeof(mportal_t));
2828         loadmodel->brush.num_portalpoints = numpoints;
2829         // clear all leaf portal chains
2830         for (i = 0;i < loadmodel->brush.num_leafs;i++)
2831                 loadmodel->brush.data_leafs[i].portals = NULL;
2832         // process all portals in the global portal chain, while freeing them
2833         portal = loadmodel->brush.data_portals;
2834         point = loadmodel->brush.data_portalpoints;
2835         p = portalchain;
2836         portalchain = NULL;
2837         while (p)
2838         {
2839                 pnext = p->chain;
2840
2841                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1])
2842                 {
2843                         // note: this check must match the one above or it will usually corrupt memory
2844                         // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
2845                         if (((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2846                         {
2847                                 // first make the back to front portal(forward portal)
2848                                 portal->points = point;
2849                                 portal->numpoints = p->numpoints;
2850                                 portal->plane.dist = p->plane.dist;
2851                                 VectorCopy(p->plane.normal, portal->plane.normal);
2852                                 portal->here = (mleaf_t *)p->nodes[1];
2853                                 portal->past = (mleaf_t *)p->nodes[0];
2854                                 // copy points
2855                                 for (j = 0;j < portal->numpoints;j++)
2856                                 {
2857                                         VectorCopy(p->points + j*3, point->position);
2858                                         point++;
2859                                 }
2860                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2861                                 PlaneClassify(&portal->plane);
2862
2863                                 // link into leaf's portal chain
2864                                 portal->next = portal->here->portals;
2865                                 portal->here->portals = portal;
2866
2867                                 // advance to next portal
2868                                 portal++;
2869
2870                                 // then make the front to back portal(backward portal)
2871                                 portal->points = point;
2872                                 portal->numpoints = p->numpoints;
2873                                 portal->plane.dist = -p->plane.dist;
2874                                 VectorNegate(p->plane.normal, portal->plane.normal);
2875                                 portal->here = (mleaf_t *)p->nodes[0];
2876                                 portal->past = (mleaf_t *)p->nodes[1];
2877                                 // copy points
2878                                 for (j = portal->numpoints - 1;j >= 0;j--)
2879                                 {
2880                                         VectorCopy(p->points + j*3, point->position);
2881                                         point++;
2882                                 }
2883                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2884                                 PlaneClassify(&portal->plane);
2885
2886                                 // link into leaf's portal chain
2887                                 portal->next = portal->here->portals;
2888                                 portal->here->portals = portal;
2889
2890                                 // advance to next portal
2891                                 portal++;
2892                         }
2893                         // add the portal's polygon points to the leaf bounding boxes
2894                         for (i = 0;i < 2;i++)
2895                         {
2896                                 leaf = (mleaf_t *)p->nodes[i];
2897                                 for (j = 0;j < p->numpoints;j++)
2898                                 {
2899                                         if (leaf->mins[0] > p->points[j*3+0]) leaf->mins[0] = p->points[j*3+0];
2900                                         if (leaf->mins[1] > p->points[j*3+1]) leaf->mins[1] = p->points[j*3+1];
2901                                         if (leaf->mins[2] > p->points[j*3+2]) leaf->mins[2] = p->points[j*3+2];
2902                                         if (leaf->maxs[0] < p->points[j*3+0]) leaf->maxs[0] = p->points[j*3+0];
2903                                         if (leaf->maxs[1] < p->points[j*3+1]) leaf->maxs[1] = p->points[j*3+1];
2904                                         if (leaf->maxs[2] < p->points[j*3+2]) leaf->maxs[2] = p->points[j*3+2];
2905                                 }
2906                         }
2907                 }
2908                 FreePortal(p);
2909                 p = pnext;
2910         }
2911         // now recalculate the node bounding boxes from the leafs
2912         Mod_Q1BSP_RecursiveRecalcNo