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