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