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