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