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_Printf("S");
 445 #endif
 446                         return HULLCHECKSTATE_SOLID;
 447                 }
 448                 else
 449                 {
 450                         t->trace->allsolid = false;
 451 #if COLLISIONPARANOID >= 3
 452                         Con_Printf("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_Printf("<");
 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_Printf(">");
 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_Printf("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_Printf("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_Printf("\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", 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_Printf("Empty .lit file, ignoring\n");
1251                                 else
1252                                         Con_Printf("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_Printf("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_Printf("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_Printf("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_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin, float lightradius);
2882 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);
2883 void Mod_Q1BSP_Load(model_t *mod, void *buffer)
2884 {
2885         int i, j, k;
2886         dheader_t *header;
2887         dmodel_t *bm;
2888         mempool_t *mainmempool;
2889         char *loadname;
2890         model_t *originalloadmodel;
2891         float dist, modelyawradius, modelradius, *vec;
2892         msurface_t *surf;
2893         int numshadowmeshtriangles;
2894
2895         mod->type = mod_brush;
2896
2897         header = (dheader_t *)buffer;
2898
2899         i = LittleLong(header->version);
2900         if (i != BSPVERSION && i != 30)
2901                 Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i(Quake) or 30(HalfLife))", mod->name, i, BSPVERSION);
2902         mod->brush.ishlbsp = i == 30;
2903
2904         mod->soundfromcenter = true;
2905         mod->TraceBox = Mod_Q1BSP_TraceBox;
2906         mod->brush.SuperContentsFromNativeContents = Mod_Q1BSP_SuperContentsFromNativeContents;
2907         mod->brush.NativeContentsFromSuperContents = Mod_Q1BSP_NativeContentsFromSuperContents;
2908         mod->brush.GetPVS = Mod_Q1BSP_GetPVS;
2909         mod->brush.FatPVS = Mod_Q1BSP_FatPVS;
2910         mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
2911         mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
2912         mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
2913         mod->brush.AmbientSoundLevelsForPoint = Mod_Q1BSP_AmbientSoundLevelsForPoint;
2914         mod->brush.RoundUpToHullSize = Mod_Q1BSP_RoundUpToHullSize;
2915         mod->brushq1.PointInLeaf = Mod_Q1BSP_PointInLeaf;
2916         mod->brushq1.BuildPVSTextureChains = Mod_Q1BSP_BuildPVSTextureChains;
2917
2918         if (loadmodel->isworldmodel)
2919         {
2920                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
2921                 // until we get a texture for it...
2922                 R_ResetQuakeSky();
2923         }
2924
2925 // swap all the lumps
2926         mod_base = (qbyte *)header;
2927
2928         for (i = 0;i < (int) sizeof(dheader_t) / 4;i++)
2929                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
2930
2931 // load into heap
2932
2933         // store which lightmap format to use
2934         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
2935
2936         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
2937         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
2938         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
2939         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
2940         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
2941         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
2942         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
2943         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
2944         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
2945         Mod_Q1BSP_LoadMarksurfaces(&header->lumps[LUMP_MARKSURFACES]);
2946         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
2947         // load submodels before leafs because they contain the number of vis leafs
2948         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS]);
2949         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
2950         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
2951         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES]);
2952
2953         if (mod->brushq1.data_compressedpvs)
2954                 Mem_Free(mod->brushq1.data_compressedpvs);
2955         mod->brushq1.data_compressedpvs = NULL;
2956         mod->brushq1.num_compressedpvs = 0;
2957
2958         Mod_Q1BSP_MakeHull0();
2959         Mod_Q1BSP_MakePortals();
2960
2961         mod->numframes = 2;             // regular and alternate animation
2962
2963         mainmempool = mod->mempool;
2964         loadname = mod->name;
2965
2966         Mod_Q1BSP_LoadLightList();
2967         originalloadmodel = loadmodel;
2968
2969         // make a single combined shadow mesh to allow optimized shadow volume creation
2970         numshadowmeshtriangles = 0;
2971         for (j = 0, surf = loadmodel->brushq1.surfaces;j < loadmodel->brushq1.numsurfaces;j++, surf++)
2972         {
2973                 surf->num_firstshadowmeshtriangle = numshadowmeshtriangles;
2974                 numshadowmeshtriangles += surf->mesh.num_triangles;
2975         }
2976         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Begin(loadmodel->mempool, numshadowmeshtriangles * 3, numshadowmeshtriangles, NULL, NULL, NULL, false, false, true);
2977         for (j = 0, surf = loadmodel->brushq1.surfaces;j < loadmodel->brushq1.numsurfaces;j++, surf++)
2978                 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);
2979         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Finish(loadmodel->mempool, loadmodel->brush.shadowmesh, false, true);
2980         Mod_BuildTriangleNeighbors(loadmodel->brush.shadowmesh->neighbor3i, loadmodel->brush.shadowmesh->element3i, loadmodel->brush.shadowmesh->numtriangles);
2981
2982 //
2983 // set up the submodels(FIXME: this is confusing)
2984 //
2985         for (i = 0;i < mod->brush.numsubmodels;i++)
2986         {
2987                 bm = &mod->brushq1.submodels[i];
2988
2989                 mod->brushq1.hulls[0].firstclipnode = bm->headnode[0];
2990                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
2991                 {
2992                         mod->brushq1.hulls[j].firstclipnode = bm->headnode[j];
2993                         mod->brushq1.hulls[j].lastclipnode = mod->brushq1.numclipnodes - 1;
2994                 }
2995
2996                 mod->brushq1.firstmodelsurface = bm->firstface;
2997                 mod->brushq1.nummodelsurfaces = bm->numfaces;
2998
2999                 // this gets altered below if sky is used
3000                 mod->DrawSky = NULL;
3001                 mod->Draw = R_Model_Brush_Draw;
3002                 mod->DrawShadowVolume = R_Model_Brush_DrawShadowVolume;
3003                 mod->DrawLight = R_Model_Brush_DrawLight;
3004                 if (i != 0)
3005                 {
3006                         mod->brush.GetPVS = NULL;
3007                         mod->brush.FatPVS = NULL;
3008                         mod->brush.BoxTouchingPVS = NULL;
3009                         mod->brush.LightPoint = NULL;
3010                         mod->brush.AmbientSoundLevelsForPoint = NULL;
3011                 }
3012                 mod->brushq1.pvstexturechains = Mem_Alloc(originalloadmodel->mempool, mod->brushq1.numtextures * sizeof(msurface_t **));
3013                 mod->brushq1.pvstexturechainsbuffer = Mem_Alloc(originalloadmodel->mempool,(mod->brushq1.nummodelsurfaces + mod->brushq1.numtextures) * sizeof(msurface_t *));
3014                 mod->brushq1.pvstexturechainslength = Mem_Alloc(originalloadmodel->mempool, mod->brushq1.numtextures * sizeof(int));
3015                 Mod_Q1BSP_BuildPVSTextureChains(mod);
3016                 Mod_Q1BSP_BuildLightmapUpdateChains(originalloadmodel->mempool, mod);
3017                 if (mod->brushq1.nummodelsurfaces)
3018                 {
3019                         // LordHavoc: calculate bmodel bounding box rather than trusting what it says
3020                         mod->normalmins[0] = mod->normalmins[1] = mod->normalmins[2] = 1000000000.0f;
3021                         mod->normalmaxs[0] = mod->normalmaxs[1] = mod->normalmaxs[2] = -1000000000.0f;
3022                         modelyawradius = 0;
3023                         modelradius = 0;
3024                         for (j = 0, surf = &mod->brushq1.surfaces[mod->brushq1.firstmodelsurface];j < mod->brushq1.nummodelsurfaces;j++, surf++)
3025                         {
3026                                 // we only need to have a drawsky function if it is used(usually only on world model)
3027                                 if (surf->texinfo->texture->shader == &Cshader_sky)
3028                                         mod->DrawSky = R_Model_Brush_DrawSky;
3029                                 // LordHavoc: submodels always clip, even if water
3030                                 if (mod->brush.numsubmodels - 1)
3031                                         surf->flags |= SURF_SOLIDCLIP;
3032                                 // calculate bounding shapes
3033                                 for (k = 0, vec = surf->mesh.data_vertex3f;k < surf->mesh.num_vertices;k++, vec += 3)
3034                                 {
3035                                         if (mod->normalmins[0] > vec[0]) mod->normalmins[0] = vec[0];
3036                                         if (mod->normalmins[1] > vec[1]) mod->normalmins[1] = vec[1];
3037                                         if (mod->normalmins[2] > vec[2]) mod->normalmins[2] = vec[2];
3038                                         if (mod->normalmaxs[0] < vec[0]) mod->normalmaxs[0] = vec[0];
3039                                         if (mod->normalmaxs[1] < vec[1]) mod->normalmaxs[1] = vec[1];
3040                                         if (mod->normalmaxs[2] < vec[2]) mod->normalmaxs[2] = vec[2];
3041                                         dist = vec[0]*vec[0]+vec[1]*vec[1];
3042                                         if (modelyawradius < dist)
3043                                                 modelyawradius = dist;
3044                                         dist += vec[2]*vec[2];
3045                                         if (modelradius < dist)
3046                                                 modelradius = dist;
3047                                 }
3048                         }
3049                         modelyawradius = sqrt(modelyawradius);
3050                         modelradius = sqrt(modelradius);
3051                         mod->yawmins[0] = mod->yawmins[1] = - (mod->yawmaxs[0] = mod->yawmaxs[1] = modelyawradius);
3052                         mod->yawmins[2] = mod->normalmins[2];
3053                         mod->yawmaxs[2] = mod->normalmaxs[2];
3054                         mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
3055                         mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
3056                         mod->radius = modelradius;
3057                         mod->radius2 = modelradius * modelradius;
3058                 }
3059                 else
3060                 {
3061                         // LordHavoc: empty submodel(lacrima.bsp has such a glitch)
3062                         Con_Printf("warning: empty submodel *%i in %s\n", i+1, loadname);
3063                 }
3064                 Mod_Q1BSP_BuildSurfaceNeighbors(mod->brushq1.surfaces + mod->brushq1.firstmodelsurface, mod->brushq1.nummodelsurfaces, originalloadmodel->mempool);
3065
3066                 mod->brushq1.num_visleafs = bm->visleafs;
3067
3068                 // LordHavoc: only register submodels if it is the world
3069                 // (prevents bsp models from replacing world submodels)
3070                 if (loadmodel->isworldmodel && i < (mod->brush.numsubmodels - 1))
3071                 {
3072                         char    name[10];
3073                         // duplicate the basic information
3074                         sprintf(name, "*%i", i+1);
3075                         loadmodel = Mod_FindName(name);
3076                         *loadmodel = *mod;
3077                         strcpy(loadmodel->name, name);
3078                         // textures and memory belong to the main model
3079                         loadmodel->texturepool = NULL;
3080                         loadmodel->mempool = NULL;
3081                         mod = loadmodel;
3082                 }
3083         }
3084
3085         loadmodel = originalloadmodel;
3086         //Mod_Q1BSP_ProcessLightList();
3087
3088         if (developer.integer)
3089                 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);
3090 }
3091
3092 static void Mod_Q2BSP_LoadEntities(lump_t *l)
3093 {
3094 }
3095
3096 static void Mod_Q2BSP_LoadPlanes(lump_t *l)
3097 {
3098 /*
3099         d_t *in;
3100         m_t *out;
3101         int i, count;
3102
3103         in = (void *)(mod_base + l->fileofs);
3104         if (l->filelen % sizeof(*in))
3105                 Host_Error("Mod_Q2BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3106         count = l->filelen / sizeof(*in);
3107         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3108
3109         loadmodel-> = out;
3110         loadmodel->num = count;
3111
3112         for (i = 0;i < count;i++, in++, out++)
3113         {
3114         }
3115 */
3116 }
3117
3118 static void Mod_Q2BSP_LoadVertices(lump_t *l)
3119 {
3120 /*
3121         d_t *in;
3122         m_t *out;
3123         int i, count;
3124
3125         in = (void *)(mod_base + l->fileofs);
3126         if (l->filelen % sizeof(*in))
3127                 Host_Error("Mod_Q2BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3128         count = l->filelen / sizeof(*in);
3129         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3130
3131         loadmodel-> = out;
3132         loadmodel->num = count;
3133
3134         for (i = 0;i < count;i++, in++, out++)
3135         {
3136         }
3137 */
3138 }
3139
3140 static void Mod_Q2BSP_LoadVisibility(lump_t *l)
3141 {
3142 /*
3143         d_t *in;
3144         m_t *out;
3145         int i, count;
3146
3147         in = (void *)(mod_base + l->fileofs);
3148         if (l->filelen % sizeof(*in))
3149                 Host_Error("Mod_Q2BSP_LoadVisibility: funny lump size in %s",loadmodel->name);
3150         count = l->filelen / sizeof(*in);
3151         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3152
3153         loadmodel-> = out;
3154         loadmodel->num = count;
3155
3156         for (i = 0;i < count;i++, in++, out++)
3157         {
3158         }
3159 */
3160 }
3161
3162 static void Mod_Q2BSP_LoadNodes(lump_t *l)
3163 {
3164 /*
3165         d_t *in;
3166         m_t *out;
3167         int i, count;
3168
3169         in = (void *)(mod_base + l->fileofs);
3170         if (l->filelen % sizeof(*in))
3171                 Host_Error("Mod_Q2BSP_LoadNodes: funny lump size in %s",loadmodel->name);
3172         count = l->filelen / sizeof(*in);
3173         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3174
3175         loadmodel-> = out;
3176         loadmodel->num = count;
3177
3178         for (i = 0;i < count;i++, in++, out++)
3179         {
3180         }
3181 */
3182 }
3183
3184 static void Mod_Q2BSP_LoadTexInfo(lump_t *l)
3185 {
3186 /*
3187         d_t *in;
3188         m_t *out;
3189         int i, count;
3190
3191         in = (void *)(mod_base + l->fileofs);
3192         if (l->filelen % sizeof(*in))
3193                 Host_Error("Mod_Q2BSP_LoadTexInfo: funny lump size in %s",loadmodel->name);
3194         count = l->filelen / sizeof(*in);
3195         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3196
3197         loadmodel-> = out;
3198         loadmodel->num = count;
3199
3200         for (i = 0;i < count;i++, in++, out++)
3201         {
3202         }
3203 */
3204 }
3205
3206 static void Mod_Q2BSP_LoadFaces(lump_t *l)
3207 {
3208 /*
3209         d_t *in;
3210         m_t *out;
3211         int i, count;
3212
3213         in = (void *)(mod_base + l->fileofs);
3214         if (l->filelen % sizeof(*in))
3215                 Host_Error("Mod_Q2BSP_LoadFaces: funny lump size in %s",loadmodel->name);
3216         count = l->filelen / sizeof(*in);
3217         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3218
3219         loadmodel-> = out;
3220         loadmodel->num = count;
3221
3222         for (i = 0;i < count;i++, in++, out++)
3223         {
3224         }
3225 */
3226 }
3227
3228 static void Mod_Q2BSP_LoadLighting(lump_t *l)
3229 {
3230 /*
3231         d_t *in;
3232         m_t *out;
3233         int i, count;
3234
3235         in = (void *)(mod_base + l->fileofs);
3236         if (l->filelen % sizeof(*in))
3237                 Host_Error("Mod_Q2BSP_LoadLighting: funny lump size in %s",loadmodel->name);
3238         count = l->filelen / sizeof(*in);
3239         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3240
3241         loadmodel-> = out;
3242         loadmodel->num = count;
3243
3244         for (i = 0;i < count;i++, in++, out++)
3245         {
3246         }
3247 */
3248 }
3249
3250 static void Mod_Q2BSP_LoadLeafs(lump_t *l)
3251 {
3252 /*
3253         d_t *in;
3254         m_t *out;
3255         int i, count;
3256
3257         in = (void *)(mod_base + l->fileofs);
3258         if (l->filelen % sizeof(*in))
3259                 Host_Error("Mod_Q2BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
3260         count = l->filelen / sizeof(*in);
3261         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3262
3263         loadmodel-> = out;
3264         loadmodel->num = count;
3265
3266         for (i = 0;i < count;i++, in++, out++)
3267         {
3268         }
3269 */
3270 }
3271
3272 static void Mod_Q2BSP_LoadLeafFaces(lump_t *l)
3273 {
3274 /*
3275         d_t *in;
3276         m_t *out;
3277         int i, count;
3278
3279         in = (void *)(mod_base + l->fileofs);
3280         if (l->filelen % sizeof(*in))
3281                 Host_Error("Mod_Q2BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
3282         count = l->filelen / sizeof(*in);
3283         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3284
3285         loadmodel-> = out;
3286         loadmodel->num = count;
3287
3288         for (i = 0;i < count;i++, in++, out++)
3289         {
3290         }
3291 */
3292 }
3293
3294 static void Mod_Q2BSP_LoadLeafBrushes(lump_t *l)
3295 {
3296 /*
3297         d_t *in;
3298         m_t *out;
3299         int i, count;
3300
3301         in = (void *)(mod_base + l->fileofs);
3302         if (l->filelen % sizeof(*in))
3303                 Host_Error("Mod_Q2BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
3304         count = l->filelen / sizeof(*in);
3305         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3306
3307         loadmodel-> = out;
3308         loadmodel->num = count;
3309
3310         for (i = 0;i < count;i++, in++, out++)
3311         {
3312         }
3313 */
3314 }
3315
3316 static void Mod_Q2BSP_LoadEdges(lump_t *l)
3317 {
3318 /*
3319         d_t *in;
3320         m_t *out;
3321         int i, count;
3322
3323         in = (void *)(mod_base + l->fileofs);
3324         if (l->filelen % sizeof(*in))
3325                 Host_Error("Mod_Q2BSP_LoadEdges: funny lump size in %s",loadmodel->name);
3326         count = l->filelen / sizeof(*in);
3327         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3328
3329         loadmodel-> = out;
3330         loadmodel->num = count;
3331
3332         for (i = 0;i < count;i++, in++, out++)
3333         {
3334         }
3335 */
3336 }
3337
3338 static void Mod_Q2BSP_LoadSurfEdges(lump_t *l)
3339 {
3340 /*
3341         d_t *in;
3342         m_t *out;
3343         int i, count;
3344
3345         in = (void *)(mod_base + l->fileofs);
3346         if (l->filelen % sizeof(*in))
3347                 Host_Error("Mod_Q2BSP_LoadSurfEdges: funny lump size in %s",loadmodel->name);
3348         count = l->filelen / sizeof(*in);
3349         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3350
3351         loadmodel-> = out;
3352         loadmodel->num = count;
3353
3354         for (i = 0;i < count;i++, in++, out++)
3355         {
3356         }
3357 */
3358 }
3359
3360 static void Mod_Q2BSP_LoadBrushes(lump_t *l)
3361 {
3362 /*
3363         d_t *in;
3364         m_t *out;
3365         int i, count;
3366
3367         in = (void *)(mod_base + l->fileofs);
3368         if (l->filelen % sizeof(*in))
3369                 Host_Error("Mod_Q2BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3370         count = l->filelen / sizeof(*in);
3371         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3372
3373         loadmodel-> = out;
3374         loadmodel->num = count;
3375
3376         for (i = 0;i < count;i++, in++, out++)
3377         {
3378         }
3379 */
3380 }
3381
3382 static void Mod_Q2BSP_LoadBrushSides(lump_t *l)
3383 {
3384 /*
3385         d_t *in;
3386         m_t *out;
3387         int i, count;
3388
3389         in = (void *)(mod_base + l->fileofs);
3390         if (l->filelen % sizeof(*in))
3391                 Host_Error("Mod_Q2BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3392         count = l->filelen / sizeof(*in);
3393         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3394
3395         loadmodel-> = out;
3396         loadmodel->num = count;
3397
3398         for (i = 0;i < count;i++, in++, out++)
3399         {
3400         }
3401 */
3402 }
3403
3404 static void Mod_Q2BSP_LoadAreas(lump_t *l)
3405 {
3406 /*
3407         d_t *in;
3408         m_t *out;
3409         int i, count;
3410
3411         in = (void *)(mod_base + l->fileofs);
3412         if (l->filelen % sizeof(*in))
3413                 Host_Error("Mod_Q2BSP_LoadAreas: funny lump size in %s",loadmodel->name);
3414         count = l->filelen / sizeof(*in);
3415         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3416
3417         loadmodel-> = out;
3418         loadmodel->num = count;
3419
3420         for (i = 0;i < count;i++, in++, out++)
3421         {
3422         }
3423 */
3424 }
3425
3426 static void Mod_Q2BSP_LoadAreaPortals(lump_t *l)
3427 {
3428 /*
3429         d_t *in;
3430         m_t *out;
3431         int i, count;
3432
3433         in = (void *)(mod_base + l->fileofs);
3434         if (l->filelen % sizeof(*in))
3435                 Host_Error("Mod_Q2BSP_LoadAreaPortals: funny lump size in %s",loadmodel->name);
3436         count = l->filelen / sizeof(*in);
3437         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3438
3439         loadmodel-> = out;
3440         loadmodel->num = count;
3441
3442         for (i = 0;i < count;i++, in++, out++)
3443         {
3444         }
3445 */
3446 }
3447
3448 static void Mod_Q2BSP_LoadModels(lump_t *l)
3449 {
3450 /*
3451         d_t *in;
3452         m_t *out;
3453         int i, count;
3454
3455         in = (void *)(mod_base + l->fileofs);
3456         if (l->filelen % sizeof(*in))
3457                 Host_Error("Mod_Q2BSP_LoadModels: funny lump size in %s",loadmodel->name);
3458         count = l->filelen / sizeof(*in);
3459         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3460
3461         loadmodel-> = out;
3462         loadmodel->num = count;
3463
3464         for (i = 0;i < count;i++, in++, out++)
3465         {
3466         }
3467 */
3468 }
3469
3470 void static Mod_Q2BSP_Load(model_t *mod, void *buffer)
3471 {
3472         int i;
3473         q2dheader_t *header;
3474
3475         Host_Error("Mod_Q2BSP_Load: not yet implemented\n");
3476
3477         mod->type = mod_brushq2;
3478
3479         header = (q2dheader_t *)buffer;
3480
3481         i = LittleLong(header->version);
3482         if (i != Q2BSPVERSION)
3483                 Host_Error("Mod_Q2BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q2BSPVERSION);
3484         mod->brush.ishlbsp = false;
3485         if (loadmodel->isworldmodel)
3486         {
3487                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
3488                 // until we get a texture for it...
3489                 R_ResetQuakeSky();
3490         }
3491
3492         mod_base = (qbyte *)header;
3493
3494         // swap all the lumps
3495         for (i = 0;i < (int) sizeof(*header) / 4;i++)
3496                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
3497
3498         // store which lightmap format to use
3499         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3500
3501         Mod_Q2BSP_LoadEntities(&header->lumps[Q2LUMP_ENTITIES]);
3502         Mod_Q2BSP_LoadPlanes(&header->lumps[Q2LUMP_PLANES]);
3503         Mod_Q2BSP_LoadVertices(&header->lumps[Q2LUMP_VERTEXES]);
3504         Mod_Q2BSP_LoadVisibility(&header->lumps[Q2LUMP_VISIBILITY]);
3505         Mod_Q2BSP_LoadNodes(&header->lumps[Q2LUMP_NODES]);
3506         Mod_Q2BSP_LoadTexInfo(&header->lumps[Q2LUMP_TEXINFO]);
3507         Mod_Q2BSP_LoadFaces(&header->lumps[Q2LUMP_FACES]);
3508         Mod_Q2BSP_LoadLighting(&header->lumps[Q2LUMP_LIGHTING]);
3509         Mod_Q2BSP_LoadLeafs(&header->lumps[Q2LUMP_LEAFS]);
3510         Mod_Q2BSP_LoadLeafFaces(&header->lumps[Q2LUMP_LEAFFACES]);
3511         Mod_Q2BSP_LoadLeafBrushes(&header->lumps[Q2LUMP_LEAFBRUSHES]);
3512         Mod_Q2BSP_LoadEdges(&header->lumps[Q2LUMP_EDGES]);
3513         Mod_Q2BSP_LoadSurfEdges(&header->lumps[Q2LUMP_SURFEDGES]);
3514         Mod_Q2BSP_LoadBrushes(&header->lumps[Q2LUMP_BRUSHES]);
3515         Mod_Q2BSP_LoadBrushSides(&header->lumps[Q2LUMP_BRUSHSIDES]);
3516         Mod_Q2BSP_LoadAreas(&header->lumps[Q2LUMP_AREAS]);
3517         Mod_Q2BSP_LoadAreaPortals(&header->lumps[Q2LUMP_AREAPORTALS]);
3518         // LordHavoc: must go last because this makes the submodels
3519         Mod_Q2BSP_LoadModels(&header->lumps[Q2LUMP_MODELS]);
3520 }
3521
3522 static int Mod_Q3BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents);
3523 static int Mod_Q3BSP_NativeContentsFromSuperContents(model_t *model, int supercontents);
3524
3525 static void Mod_Q3BSP_LoadEntities(lump_t *l)
3526 {
3527         const char *data;
3528         char key[128], value[4096];
3529         float v[3];
3530         loadmodel->brushq3.num_lightgrid_cellsize[0] = 64;
3531         loadmodel->brushq3.num_lightgrid_cellsize[1] = 64;
3532         loadmodel->brushq3.num_lightgrid_cellsize[2] = 128;
3533         if (!l->filelen)
3534                 return;
3535         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
3536         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
3537         data = loadmodel->brush.entities;
3538         // some Q3 maps override the lightgrid_cellsize with a worldspawn key
3539         if (data && COM_ParseToken(&data, false) && com_token[0] == '{')
3540         {
3541                 while (1)
3542                 {
3543                         if (!COM_ParseToken(&data, false))
3544                                 break; // error
3545                         if (com_token[0] == '}')
3546                                 break; // end of worldspawn
3547                         if (com_token[0] == '_')
3548                                 strcpy(key, com_token + 1);
3549                         else
3550                                 strcpy(key, com_token);
3551                         while (key[strlen(key)-1] == ' ') // remove trailing spaces
3552                                 key[strlen(key)-1] = 0;
3553                         if (!COM_ParseToken(&data, false))
3554                                 break; // error
3555                         strcpy(value, com_token);
3556                         if (!strcmp("gridsize", key))
3557                         {
3558                                 if (sscanf(value, "%f %f %f", &v[0], &v[1], &v[2]) == 3 && v[0] != 0 && v[1] != 0 && v[2] != 0)
3559                                         VectorCopy(v, loadmodel->brushq3.num_lightgrid_cellsize);
3560                         }
3561                 }
3562         }
3563 }
3564
3565 static void Mod_Q3BSP_LoadTextures(lump_t *l)
3566 {
3567         q3dtexture_t *in;
3568         q3mtexture_t *out;
3569         int i, count;
3570         int j, c;
3571         fssearch_t *search;
3572         char *f;
3573         const char *text;
3574         int flags;
3575         char shadername[Q3PATHLENGTH];
3576
3577         in = (void *)(mod_base + l->fileofs);
3578         if (l->filelen % sizeof(*in))
3579                 Host_Error("Mod_Q3BSP_LoadTextures: funny lump size in %s",loadmodel->name);
3580         count = l->filelen / sizeof(*in);
3581         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3582
3583         loadmodel->brushq3.data_textures = out;
3584         loadmodel->brushq3.num_textures = count;
3585
3586         for (i = 0;i < count;i++, in++, out++)
3587         {
3588                 out->number = i;
3589                 strlcpy (out->name, in->name, sizeof (out->name));
3590                 out->surfaceflags = LittleLong(in->surfaceflags);
3591                 out->nativecontents = LittleLong(in->contents);
3592                 out->supercontents = Mod_Q3BSP_SuperContentsFromNativeContents(loadmodel, out->nativecontents);
3593                 Mod_LoadSkinFrame(&out->skin, out->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, false, true, true);
3594                 out->surfaceparms = -1;
3595         }
3596
3597         // do a quick parse of shader files to get surfaceparms
3598         if ((search = FS_Search("scripts/*.shader", true, false)))
3599         {
3600                 for (i = 0;i < search->numfilenames;i++)
3601                 {
3602                         if ((f = FS_LoadFile(search->filenames[i], false)))
3603                         {
3604                                 text = f;
3605                                 while (COM_ParseToken(&text, false))
3606                                 {
3607                                         snprintf(shadername, sizeof(shadername), "%s", com_token);
3608                                         flags = 0;
3609                                         if (COM_ParseToken(&text, false) && !strcasecmp(com_token, "{"))
3610                                         {
3611                                                 while (COM_ParseToken(&text, false))
3612                                                 {
3613                                                         if (!strcasecmp(com_token, "}"))
3614                                                                 break;
3615                                                         else if (!strcasecmp(com_token, "{"))
3616                                                         {
3617                                                                 while (COM_ParseToken(&text, false))
3618                                                                 {
3619                                                                         if (!strcasecmp(com_token, "}"))
3620                                                                                 break;
3621                                                                 }
3622                                                         }
3623                                                         else if (!strcasecmp(com_token, "surfaceparm"))
3624                                                         {
3625                                                                 if (COM_ParseToken(&text, true) && strcasecmp(com_token, "\n"))
3626                                                                 {
3627                                                                         if (!strcasecmp(com_token, "alphashadow"))
3628                                                                                 flags |= Q3SURFACEPARM_ALPHASHADOW;
3629                                                                         else if (!strcasecmp(com_token, "areaportal"))
3630                                                                                 flags |= Q3SURFACEPARM_AREAPORTAL;
3631                                                                         else if (!strcasecmp(com_token, "clusterportal"))
3632                                                                                 flags |= Q3SURFACEPARM_CLUSTERPORTAL;
3633                                                                         else if (!strcasecmp(com_token, "detail"))
3634                                                                                 flags |= Q3SURFACEPARM_DETAIL;
3635                                                                         else if (!strcasecmp(com_token, "donotenter"))
3636                                                                                 flags |= Q3SURFACEPARM_DONOTENTER;
3637                                                                         else if (!strcasecmp(com_token, "fog"))
3638                                                                                 flags |= Q3SURFACEPARM_FOG;
3639                                                                         else if (!strcasecmp(com_token, "lava"))
3640                                                                                 flags |= Q3SURFACEPARM_LAVA;
3641                                                                         else if (!strcasecmp(com_token, "lightfilter"))
3642                                                                                 flags |= Q3SURFACEPARM_LIGHTFILTER;
3643                                                                         else if (!strcasecmp(com_token, "metalsteps"))
3644                                                                                 flags |= Q3SURFACEPARM_METALSTEPS;
3645                                                                         else if (!strcasecmp(com_token, "nodamage"))
3646                                                                                 flags |= Q3SURFACEPARM_NODAMAGE;
3647                                                                         else if (!strcasecmp(com_token, "nodlight"))
3648                                                                                 flags |= Q3SURFACEPARM_NODLIGHT;
3649                                                                         else if (!strcasecmp(com_token, "nodraw"))
3650                                                                                 flags |= Q3SURFACEPARM_NODRAW;
3651                                                                         else if (!strcasecmp(com_token, "nodrop"))
3652                                                                                 flags |= Q3SURFACEPARM_NODROP;
3653                                                                         else if (!strcasecmp(com_token, "noimpact"))
3654                                                                                 flags |= Q3SURFACEPARM_NOIMPACT;
3655                                                                         else if (!strcasecmp(com_token, "nolightmap"))
3656                                                                                 flags |= Q3SURFACEPARM_NOLIGHTMAP;
3657                                                                         else if (!strcasecmp(com_token, "nomarks"))
3658                                                                                 flags |= Q3SURFACEPARM_NOMARKS;
3659                                                                         else if (!strcasecmp(com_token, "nomipmaps"))
3660                                                                                 flags |= Q3SURFACEPARM_NOMIPMAPS;
3661                                                                         else if (!strcasecmp(com_token, "nonsolid"))
3662                                                                                 flags |= Q3SURFACEPARM_NONSOLID;
3663                                                                         else if (!strcasecmp(com_token, "origin"))
3664                                                                                 flags |= Q3SURFACEPARM_ORIGIN;
3665                                                                         else if (!strcasecmp(com_token, "playerclip"))
3666                                                                                 flags |= Q3SURFACEPARM_PLAYERCLIP;
3667                                                                         else if (!strcasecmp(com_token, "sky"))
3668                                                                                 flags |= Q3SURFACEPARM_SKY;
3669                                                                         else if (!strcasecmp(com_token, "slick"))
3670                                                                                 flags |= Q3SURFACEPARM_SLICK;
3671                                                                         else if (!strcasecmp(com_token, "slime"))
3672                                                                                 flags |= Q3SURFACEPARM_SLIME;
3673                                                                         else if (!strcasecmp(com_token, "structural"))
3674                                                                                 flags |= Q3SURFACEPARM_STRUCTURAL;
3675                                                                         else if (!strcasecmp(com_token, "trans"))
3676                                                                                 flags |= Q3SURFACEPARM_TRANS;
3677                                                                         else if (!strcasecmp(com_token, "water"))
3678                                                                                 flags |= Q3SURFACEPARM_WATER;
3679                                                                         else
3680                                                                                 Con_Printf("%s parsing warning: unknown surfaceparm \"%s\"\n", search->filenames[i], com_token);
3681                                                                         if (!COM_ParseToken(&text, true) || strcasecmp(com_token, "\n"))
3682                                                                         {
3683                                                                                 Con_Printf("%s parsing error: surfaceparm only takes one parameter.\n", search->filenames[i]);
3684                                                                                 goto parseerror;
3685                                                                         }
3686                                                                 }
3687                                                                 else
3688                                                                 {
3689                                                                         Con_Printf("%s parsing error: surfaceparm expects a parameter.\n", search->filenames[i]);
3690                                                                         goto parseerror;
3691                                                                 }
3692                                                         }
3693                                                         else
3694                                                         {
3695                                                                 // look for linebreak or }
3696                                                                 while(COM_ParseToken(&text, true) && strcasecmp(com_token, "\n") && strcasecmp(com_token, "}"));
3697                                                                 // break out to top level if it was }
3698                                                                 if (!strcasecmp(com_token, "}"))
3699                                                                         break;
3700                                                         }
3701                                                 }
3702                                                 // add shader to list (shadername and flags)
3703                                                 // actually here we just poke into the texture settings
3704                                                 for (j = 0, out = loadmodel->brushq3.data_textures;j < loadmodel->brushq3.num_textures;j++, out++)
3705                                                         if (!strcasecmp(out->name, shadername))
3706                                                                 out->surfaceparms = flags;
3707                                         }
3708                                         else
3709                                         {
3710                                                 Con_Printf("%s parsing error - expected \"{\", found \"%s\"\n", search->filenames[i], com_token);
3711                                                 goto parseerror;
3712                                         }
3713                                 }
3714 parseerror:
3715                                 Mem_Free(f);
3716                         }
3717                 }
3718         }
3719
3720         c = 0;
3721         for (j = 0, out = loadmodel->brushq3.data_textures;j < loadmodel->brushq3.num_textures;j++, out++)
3722         {
3723                 if (out->surfaceparms == -1)
3724                 {
3725                         c++;
3726                         Con_DPrintf("%s: No shader found for texture \"%s\"\n", loadmodel->name, out->name);
3727                         out->surfaceparms = 0;
3728                         // these are defaults
3729                         if (!strcmp(out->name, "caulk") || !strcmp(out->name, "common/caulk") || !strcmp(out->name, "textures/common/caulk")
3730                          || !strcmp(out->name, "nodraw") || !strcmp(out->name, "common/nodraw") || !strcmp(out->name, "textures/common/nodraw"))
3731                                 out->surfaceparms |= Q3SURFACEPARM_NODRAW;
3732                         if (!strncmp(out->name, "textures/skies/", 15))
3733                                 out->surfaceparms |= Q3SURFACEPARM_SKY;
3734                         if (R_TextureHasAlpha(out->skin.base))
3735                                 out->surfaceparms |= Q3SURFACEPARM_TRANS;
3736                 }
3737         }
3738         Con_DPrintf("%s: %i textures missing shaders\n", loadmodel->name, c);
3739 }
3740
3741 static void Mod_Q3BSP_LoadPlanes(lump_t *l)
3742 {
3743         q3dplane_t *in;
3744         mplane_t *out;
3745         int i, count;
3746
3747         in = (void *)(mod_base + l->fileofs);
3748         if (l->filelen % sizeof(*in))
3749                 Host_Error("Mod_Q3BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3750         count = l->filelen / sizeof(*in);
3751         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3752
3753         loadmodel->brushq3.data_planes = out;
3754         loadmodel->brushq3.num_planes = count;
3755
3756         for (i = 0;i < count;i++, in++, out++)
3757         {
3758                 out->normal[0] = LittleLong(in->normal[0]);
3759                 out->normal[1] = LittleLong(in->normal[1]);
3760                 out->normal[2] = LittleLong(in->normal[2]);
3761                 out->dist = LittleLong(in->dist);
3762                 PlaneClassify(out);
3763         }
3764 }
3765
3766 static void Mod_Q3BSP_LoadBrushSides(lump_t *l)
3767 {
3768         q3dbrushside_t *in;
3769         q3mbrushside_t *out;
3770         int i, n, count;
3771
3772         in = (void *)(mod_base + l->fileofs);
3773         if (l->filelen % sizeof(*in))
3774                 Host_Error("Mod_Q3BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3775         count = l->filelen / sizeof(*in);
3776         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3777
3778         loadmodel->brushq3.data_brushsides = out;
3779         loadmodel->brushq3.num_brushsides = count;
3780
3781         for (i = 0;i < count;i++, in++, out++)
3782         {
3783                 n = LittleLong(in->planeindex);
3784                 if (n < 0 || n >= loadmodel->brushq3.num_planes)
3785                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid planeindex %i (%i planes)\n", n, loadmodel->brushq3.num_planes);
3786                 out->plane = loadmodel->brushq3.data_planes + n;
3787                 n = LittleLong(in->textureindex);
3788                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
3789                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid textureindex %i (%i textures)\n", n, loadmodel->brushq3.num_textures);
3790                 out->texture = loadmodel->brushq3.data_textures + n;
3791         }
3792 }
3793
3794 static void Mod_Q3BSP_LoadBrushes(lump_t *l)
3795 {
3796         q3dbrush_t *in;
3797         q3mbrush_t *out;
3798         int i, j, n, c, count, maxplanes;
3799         mplane_t *planes;
3800         winding_t *temp1, *temp2;
3801
3802         in = (void *)(mod_base + l->fileofs);
3803         if (l->filelen % sizeof(*in))
3804                 Host_Error("Mod_Q3BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3805         count = l->filelen / sizeof(*in);
3806         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3807
3808         loadmodel->brushq3.data_brushes = out;
3809         loadmodel->brushq3.num_brushes = count;
3810
3811         temp1 = Winding_New(64);
3812         temp2 = Winding_New(64);
3813
3814         maxplanes = 0;
3815         planes = NULL;
3816
3817         for (i = 0;i < count;i++, in++, out++)
3818         {
3819                 n = LittleLong(in->firstbrushside);
3820                 c = LittleLong(in->numbrushsides);
3821                 if (n < 0 || n + c > loadmodel->brushq3.num_brushsides)
3822                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid brushside range %i : %i (%i brushsides)\n", n, n + c, loadmodel->brushq3.num_brushsides);
3823                 out->firstbrushside = loadmodel->brushq3.data_brushsides + n;
3824                 out->numbrushsides = c;
3825                 n = LittleLong(in->textureindex);
3826                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
3827                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid textureindex %i (%i textures)\n", n, loadmodel->brushq3.num_textures);
3828                 out->texture = loadmodel->brushq3.data_textures + n;
3829
3830                 // make a list of mplane_t structs to construct a colbrush from
3831                 if (maxplanes < out->numbrushsides)
3832                 {
3833                         maxplanes = out->numbrushsides;
3834                         if (planes)
3835                                 Mem_Free(planes);
3836                         planes = Mem_Alloc(tempmempool, sizeof(mplane_t) * maxplanes);
3837                 }
3838                 for (j = 0;j < out->numbrushsides;j++)
3839                 {
3840                         VectorCopy(out->firstbrushside[j].plane->normal, planes[j].normal);
3841                         planes[j].dist = out->firstbrushside[j].plane->dist;
3842                 }
3843                 // make the colbrush from the planes
3844                 out->colbrushf = Collision_NewBrushFromPlanes(loadmodel->mempool, out->numbrushsides, planes, out->texture->supercontents, temp1, temp2);
3845         }
3846         if (planes)
3847                 Mem_Free(planes);
3848         Winding_Free(temp1);
3849         Winding_Free(temp2);
3850 }
3851
3852 static void Mod_Q3BSP_LoadEffects(lump_t *l)
3853 {
3854         q3deffect_t *in;
3855         q3meffect_t *out;
3856         int i, n, count;
3857
3858         in = (void *)(mod_base + l->fileofs);
3859         if (l->filelen % sizeof(*in))
3860                 Host_Error("Mod_Q3BSP_LoadEffects: funny lump size in %s",loadmodel->name);
3861         count = l->filelen / sizeof(*in);
3862         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3863
3864         loadmodel->brushq3.data_effects = out;
3865         loadmodel->brushq3.num_effects = count;
3866
3867         for (i = 0;i < count;i++, in++, out++)
3868         {
3869                 strlcpy (out->shadername, in->shadername, sizeof (out->shadername));
3870                 n = LittleLong(in->brushindex);
3871                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
3872                         Host_Error("Mod_Q3BSP_LoadEffects: invalid brushindex %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
3873                 out->brush = loadmodel->brushq3.data_brushes + n;
3874                 out->unknown = LittleLong(in->unknown);
3875         }
3876 }
3877
3878 static void Mod_Q3BSP_LoadVertices(lump_t *l)
3879 {
3880         q3dvertex_t *in;
3881         int i, count;
3882
3883         in = (void *)(mod_base + l->fileofs);
3884         if (l->filelen % sizeof(*in))
3885                 Host_Error("Mod_Q3BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3886         loadmodel->brushq3.num_vertices = count = l->filelen / sizeof(*in);
3887         loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, count * (sizeof(float) * (3 + 2 + 2 + 3 + 3 + 3 + 4)));
3888         loadmodel->brushq3.data_texcoordtexture2f = loadmodel->brushq3.data_vertex3f + count * 3;
3889         loadmodel->brushq3.data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordtexture2f + count * 2;
3890         loadmodel->brushq3.data_svector3f = loadmodel->brushq3.data_texcoordlightmap2f + count * 2;
3891         loadmodel->brushq3.data_tvector3f = loadmodel->brushq3.data_svector3f + count * 3;
3892         loadmodel->brushq3.data_normal3f = loadmodel->brushq3.data_tvector3f + count * 3;
3893         loadmodel->brushq3.data_color4f = loadmodel->brushq3.data_normal3f + count * 3;
3894
3895         for (i = 0;i < count;i++, in++)
3896         {
3897                 loadmodel->brushq3.data_vertex3f[i * 3 + 0] = LittleFloat(in->origin3f[0]);
3898                 loadmodel->brushq3.data_vertex3f[i * 3 + 1] = LittleFloat(in->origin3f[1]);
3899                 loadmodel->brushq3.data_vertex3f[i * 3 + 2] = LittleFloat(in->origin3f[2]);
3900                 loadmodel->brushq3.data_texcoordtexture2f[i * 2 + 0] = LittleFloat(in->texcoord2f[0]);
3901                 loadmodel->brushq3.data_texcoordtexture2f[i * 2 + 1] = LittleFloat(in->texcoord2f[1]);
3902                 loadmodel->brushq3.data_texcoordlightmap2f[i * 2 + 0] = LittleFloat(in->lightmap2f[0]);
3903                 loadmodel->brushq3.data_texcoordlightmap2f[i * 2 + 1] = LittleFloat(in->lightmap2f[1]);
3904                 // svector/tvector are calculated later in face loading
3905                 loadmodel->brushq3.data_svector3f[i * 3 + 0] = 0;
3906                 loadmodel->brushq3.data_svector3f[i * 3 + 1] = 0;
3907                 loadmodel->brushq3.data_svector3f[i * 3 + 2] = 0;
3908                 loadmodel->brushq3.data_tvector3f[i * 3 + 0] = 0;
3909                 loadmodel->brushq3.data_tvector3f[i * 3 + 1] = 0;
3910                 loadmodel->brushq3.data_tvector3f[i * 3 + 2] = 0;
3911                 loadmodel->brushq3.data_normal3f[i * 3 + 0] = LittleFloat(in->normal3f[0]);
3912                 loadmodel->brushq3.data_normal3f[i * 3 + 1] = LittleFloat(in->normal3f[1]);
3913                 loadmodel->brushq3.data_normal3f[i * 3 + 2] = LittleFloat(in->normal3f[2]);
3914                 loadmodel->brushq3.data_color4f[i * 4 + 0] = in->color4ub[0] * (1.0f / 255.0f);
3915                 loadmodel->brushq3.data_color4f[i * 4 + 1] = in->color4ub[1] * (1.0f / 255.0f);
3916                 loadmodel->brushq3.data_color4f[i * 4 + 2] = in->color4ub[2] * (1.0f / 255.0f);
3917                 loadmodel->brushq3.data_color4f[i * 4 + 3] = in->color4ub[3] * (1.0f / 255.0f);
3918         }
3919 }
3920
3921 static void Mod_Q3BSP_LoadTriangles(lump_t *l)
3922 {
3923         int *in;
3924         int *out;
3925         int i, count;
3926
3927         in = (void *)(mod_base + l->fileofs);
3928         if (l->filelen % sizeof(int[3]))
3929                 Host_Error("Mod_Q3BSP_LoadTriangles: funny lump size in %s",loadmodel->name);
3930         count = l->filelen / sizeof(*in);
3931         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out) * 2);
3932
3933         loadmodel->brushq3.num_triangles = count / 3;
3934         loadmodel->brushq3.data_element3i = out;
3935         loadmodel->brushq3.data_neighbor3i = out + count;
3936
3937         for (i = 0;i < count;i++, in++, out++)
3938         {
3939                 *out = LittleLong(*in);
3940                 if (*out < 0 || *out >= loadmodel->brushq3.num_vertices)
3941                 {
3942                         Con_Printf("Mod_Q3BSP_LoadTriangles: invalid vertexindex %i (%i vertices), setting to 0\n", *out, loadmodel->brushq3.num_vertices);
3943                         *out = 0;
3944                 }
3945         }
3946 }
3947
3948 static void Mod_Q3BSP_LoadLightmaps(lump_t *l)
3949 {
3950         q3dlightmap_t *in;
3951         rtexture_t **out;
3952         int i, count;
3953
3954         if (!l->filelen)
3955                 return;
3956         in = (void *)(mod_base + l->fileofs);
3957         if (l->filelen % sizeof(*in))
3958                 Host_Error("Mod_Q3BSP_LoadLightmaps: funny lump size in %s",loadmodel->name);
3959         count = l->filelen / sizeof(*in);
3960         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3961
3962         loadmodel->brushq3.data_lightmaps = out;
3963         loadmodel->brushq3.num_lightmaps = count;
3964
3965         for (i = 0;i < count;i++, in++, out++)
3966                 *out = R_LoadTexture2D(loadmodel->texturepool, va("lightmap%04i", i), 128, 128, in->rgb, TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
3967 }
3968
3969 static void Mod_Q3BSP_LoadFaces(lump_t *l)
3970 {
3971         q3dface_t *in;
3972         q3mface_t *out;
3973         int i, j, n, count, invalidelements, patchsize[2], finalwidth, finalheight, xlevel, ylevel, row0, row1, x, y, *e, finalvertices, finaltriangles;
3974         //int *originalelement3i;
3975         //int *originalneighbor3i;
3976         float *originalvertex3f;
3977         //float *originalsvector3f;
3978         //float *originaltvector3f;
3979         //float *originalnormal3f;
3980         float *originalcolor4f;
3981         float *originaltexcoordtexture2f;
3982         float *originaltexcoordlightmap2f;
3983         float *v;
3984
3985         in = (void *)(mod_base + l->fileofs);
3986         if (l->filelen % sizeof(*in))
3987                 Host_Error("Mod_Q3BSP_LoadFaces: funny lump size in %s",loadmodel->name);
3988         count = l->filelen / sizeof(*in);
3989         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3990
3991         loadmodel->brushq3.data_faces = out;
3992         loadmodel->brushq3.num_faces = count;
3993
3994         for (i = 0;i < count;i++, in++, out++)
3995         {
3996                 // check face type first
3997                 out->type = LittleLong(in->type);
3998                 if (out->type != Q3FACETYPE_POLYGON
3999                  && out->type != Q3FACETYPE_PATCH
4000                  && out->type != Q3FACETYPE_MESH
4001                  && out->type != Q3FACETYPE_FLARE)
4002                 {
4003                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i: unknown face type %i\n", i, out->type);
4004                         out->num_vertices = 0;
4005                         out->num_triangles = 0;
4006                         out->type = 0; // error
4007                         continue;
4008                 }
4009
4010                 n = LittleLong(in->textureindex);
4011                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
4012                 {
4013                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i: invalid textureindex %i (%i textures)\n", i, n, loadmodel->brushq3.num_textures);
4014                         out->num_vertices = 0;
4015                         out->num_triangles = 0;
4016                         out->type = 0; // error
4017                         continue;
4018                         n = 0;
4019                 }
4020                 out->texture = loadmodel->brushq3.data_textures + n;
4021                 n = LittleLong(in->effectindex);
4022                 if (n < -1 || n >= loadmodel->brushq3.num_effects)
4023                 {
4024                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid effectindex %i (%i effects)\n", i, out->texture->name, n, loadmodel->brushq3.num_effects);
4025                         n = -1;
4026                 }
4027                 if (n == -1)
4028                         out->effect = NULL;
4029                 else
4030                         out->effect = loadmodel->brushq3.data_effects + n;
4031                 n = LittleLong(in->lightmapindex);
4032                 if (n < -1 || n >= loadmodel->brushq3.num_lightmaps)
4033                 {
4034                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid lightmapindex %i (%i lightmaps)\n", i, out->texture->name, n, loadmodel->brushq3.num_lightmaps);
4035                         n = -1;
4036                 }
4037                 if (n == -1)
4038                         out->lightmaptexture = NULL;
4039                 else
4040                         out->lightmaptexture = loadmodel->brushq3.data_lightmaps[n];
4041
4042                 out->firstvertex = LittleLong(in->firstvertex);
4043                 out->num_vertices = LittleLong(in->numvertices);
4044                 out->firstelement = LittleLong(in->firstelement);
4045                 out->num_triangles = LittleLong(in->numelements) / 3;
4046                 if (out->num_triangles * 3 != LittleLong(in->numelements))
4047                 {
4048                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): numelements %i is not a multiple of 3\n", i, out->texture->name, LittleLong(in->numelements));
4049                         out->num_vertices = 0;
4050                         out->num_triangles = 0;
4051                         out->type = 0; // error
4052                         continue;
4053                 }
4054                 if (out->firstvertex < 0 || out->firstvertex + out->num_vertices > loadmodel->brushq3.num_vertices)
4055                 {
4056                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid vertex range %i : %i (%i vertices)\n", i, out->texture->name, out->firstvertex, out->firstvertex + out->num_vertices, loadmodel->brushq3.num_vertices);
4057                         out->num_vertices = 0;
4058                         out->num_triangles = 0;
4059                         out->type = 0; // error
4060                         continue;
4061                 }
4062                 if (out->firstelement < 0 || out->firstelement + out->num_triangles * 3 > loadmodel->brushq3.num_triangles * 3)
4063                 {
4064                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid element range %i : %i (%i elements)\n", i, out->texture->name, out->firstelement, out->firstelement + out->num_triangles * 3, loadmodel->brushq3.num_triangles * 3);
4065                         out->num_vertices = 0;
4066                         out->num_triangles = 0;
4067                         out->type = 0; // error
4068                         continue;
4069                 }
4070                 switch(out->type)
4071                 {
4072                 case Q3FACETYPE_POLYGON:
4073                 case Q3FACETYPE_MESH:
4074                         // no processing necessary
4075                         out->data_vertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
4076                         out->data_texcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f + out->firstvertex * 2;
4077                         out->data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f + out->firstvertex * 2;
4078                         out->data_svector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
4079                         out->data_tvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
4080                         out->data_normal3f = loadmodel->brushq3.data_normal3f + out->firstvertex * 3;
4081                         out->data_color4f = loadmodel->brushq3.data_color4f + out->firstvertex * 4;
4082                         out->data_element3i = loadmodel->brushq3.data_element3i + out->firstelement;
4083                         out->data_neighbor3i = loadmodel->brushq3.data_neighbor3i + out->firstelement;
4084                         break;
4085                 case Q3FACETYPE_PATCH:
4086                         patchsize[0] = LittleLong(in->specific.patch.patchsize[0]);
4087                         patchsize[1] = LittleLong(in->specific.patch.patchsize[1]);
4088                         if (patchsize[0] < 1 || patchsize[1] < 1)
4089                         {
4090                                 Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid patchsize %ix%i\n", i, out->texture->name, patchsize[0], patchsize[1]);
4091                                 out->num_vertices = 0;
4092                                 out->num_triangles = 0;
4093                                 out->type = 0; // error
4094                                 continue;
4095                         }
4096                         originalvertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
4097                         //originalsvector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
4098                         //originaltvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
4099                         //originalnormal3f = loadmodel->brushq3.data_normal3f + out->firstvertex * 3;
4100                         originaltexcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f + out->firstvertex * 2;
4101                         originaltexcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f + out->firstvertex * 2;
4102                         originalcolor4f = loadmodel->brushq3.data_color4f + out->firstvertex * 4;
4103                         //originalelement3i = loadmodel->brushq3.data_element3i + out->firstelement;
4104                         //originalneighbor3i = loadmodel->brushq3.data_neighbor3i + out->firstelement;
4105                         /*
4106                         originalvertex3f = out->data_vertex3f;
4107                         //originalsvector3f = out->data_svector3f;
4108                         //originaltvector3f = out->data_tvector3f;
4109                         //originalnormal3f = out->data_normal3f;
4110                         originalcolor4f = out->data_color4f;
4111                         originaltexcoordtexture2f = out->data_texcoordtexture2f;
4112                         originaltexcoordlightmap2f = out->data_texcoordlightmap2f;
4113                         //originalelement3i = out->data_element3i;
4114                         //originalneighbor3i = out->data_neighbor3i;
4115                         */
4116                         // convert patch to Q3FACETYPE_MESH
4117                         xlevel = QuadraticSplinePatchSubdivisionLevelOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value, 10);
4118                         ylevel = QuadraticSplinePatchSubdivisionLevelOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value, 10);
4119                         // bound to user settings
4120                         xlevel = bound(r_subdivisions_minlevel.integer, xlevel, r_subdivisions_maxlevel.integer);
4121                         ylevel = bound(r_subdivisions_minlevel.integer, ylevel, r_subdivisions_maxlevel.integer);
4122                         // bound to sanity settings
4123                         xlevel = bound(0, xlevel, 10);
4124                         ylevel = bound(0, ylevel, 10);
4125                         // bound to user limit on vertices
4126                         while ((xlevel > 0 || ylevel > 0) && (((patchsize[0] - 1) << xlevel) + 1) * (((patchsize[1] - 1) << ylevel) + 1) > min(r_subdivisions_maxvertices.integer, 262144))
4127                         {
4128                                 if (xlevel > ylevel)
4129                                         xlevel--;
4130                                 else
4131                                         ylevel--;
4132                         }
4133                         finalwidth = ((patchsize[0] - 1) << xlevel) + 1;
4134                         finalheight = ((patchsize[1] - 1) << ylevel) + 1;
4135                         finalvertices = finalwidth * finalheight;
4136                         finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
4137                         out->data_vertex3f = Mem_Alloc(loadmodel->mempool, sizeof(float[20]) * finalvertices);
4138                         out->data_svector3f = out->data_vertex3f + finalvertices * 3;
4139                         out->data_tvector3f = out->data_svector3f + finalvertices * 3;
4140                         out->data_normal3f = out->data_tvector3f + finalvertices * 3;
4141                         out->data_color4f = out->data_normal3f + finalvertices * 3;
4142                         out->data_texcoordtexture2f = out->data_color4f + finalvertices * 4;
4143                         out->data_texcoordlightmap2f = out->data_texcoordtexture2f + finalvertices * 2;
4144                         out->data_element3i = Mem_Alloc(loadmodel->mempool, sizeof(int[6]) * finaltriangles);
4145                         out->data_neighbor3i = out->data_element3i + finaltriangles * 3;
4146                         out->type = Q3FACETYPE_MESH;
4147                         out->firstvertex = -1;
4148                         out->num_vertices = finalvertices;
4149                         out->firstelement = -1;
4150                         out->num_triangles = finaltriangles;
4151                         // generate geometry
4152                         // (note: normals are skipped because they get recalculated)
4153                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 3, originalvertex3f, out->data_vertex3f);
4154                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 2, originaltexcoordtexture2f, out->data_texcoordtexture2f);
4155                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 2, originaltexcoordlightmap2f, out->data_texcoordlightmap2f);
4156                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 4, originalcolor4f, out->data_color4f);
4157                         // generate elements
4158                         e = out->data_element3i;
4159                         for (y = 0;y < finalheight - 1;y++)
4160                         {
4161                                 row0 = (y + 0) * finalwidth;
4162                                 row1 = (y + 1) * finalwidth;
4163                                 for (x = 0;x < finalwidth - 1;x++)
4164                                 {
4165                                         *e++ = row0;
4166                                         *e++ = row1;
4167                                         *e++ = row0 + 1;
4168                                         *e++ = row1;
4169                                         *e++ = row1 + 1;
4170                                         *e++ = row0 + 1;
4171                                         row0++;
4172                                         row1++;
4173                                 }
4174                         }
4175                         out->num_triangles = Mod_RemoveDegenerateTriangles(out->num_triangles, out->data_element3i, out->data_element3i, out->data_vertex3f);
4176                         if (developer.integer)
4177                         {
4178                                 if (out->num_triangles < finaltriangles)
4179                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided to %i vertices / %i triangles, %i degenerate triangles removed (leaving %i)\n", patchsize[0], patchsize[1], out->num_vertices, finaltriangles, finaltriangles - out->num_triangles, out->num_triangles);
4180                                 else
4181                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided to %i vertices / %i triangles\n", patchsize[0], patchsize[1], out->num_vertices, out->num_triangles);
4182                         }
4183                         // q3map does not put in collision brushes for curves... ugh
4184                         // build the lower quality collision geometry
4185                         out->collisions = true;
4186                         xlevel = QuadraticSplinePatchSubdivisionLevelOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_collision_tolerance.value, 10);
4187                         ylevel = QuadraticSplinePatchSubdivisionLevelOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_collision_tolerance.value, 10);
4188                         // bound to user settings
4189                         xlevel = bound(r_subdivisions_collision_minlevel.integer, xlevel, r_subdivisions_collision_maxlevel.integer);
4190                         ylevel = bound(r_subdivisions_collision_minlevel.integer, ylevel, r_subdivisions_collision_maxlevel.integer);
4191                         // bound to sanity settings
4192                         xlevel = bound(0, xlevel, 10);
4193                         ylevel = bound(0, ylevel, 10);
4194                         // bound to user limit on vertices
4195                         while ((xlevel > 0 || ylevel > 0) && (((patchsize[0] - 1) << xlevel) + 1) * (((patchsize[1] - 1) << ylevel) + 1) > min(r_subdivisions_collision_maxvertices.integer, 262144))
4196                         {
4197                                 if (xlevel > ylevel)
4198                                         xlevel--;
4199                                 else
4200                                         ylevel--;
4201                         }
4202                         finalwidth = ((patchsize[0] - 1) << xlevel) + 1;
4203                         finalheight = ((patchsize[1] - 1) << ylevel) + 1;
4204                         finalvertices = finalwidth * finalheight;
4205                         finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
4206                         out->data_collisionvertex3f = Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * finalvertices);
4207                         out->data_collisionelement3i = Mem_Alloc(loadmodel->mempool, sizeof(int[3]) * finaltriangles);
4208                         out->num_collisionvertices = finalvertices;
4209                         out->num_collisiontriangles = finaltriangles;
4210                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 3, originalvertex3f, out->data_collisionvertex3f);
4211                         // generate elements
4212                         e = out->data_collisionelement3i;
4213                         for (y = 0;y < finalheight - 1;y++)
4214                         {
4215                                 row0 = (y + 0) * finalwidth;
4216                                 row1 = (y + 1) * finalwidth;
4217                                 for (x = 0;x < finalwidth - 1;x++)
4218                                 {
4219                                         *e++ = row0;
4220                                         *e++ = row1;
4221                                         *e++ = row0 + 1;
4222                                         *e++ = row1;
4223                                         *e++ = row1 + 1;
4224                                         *e++ = row0 + 1;
4225                                         row0++;
4226                                         row1++;
4227                                 }
4228                         }
4229                         out->num_collisiontriangles = Mod_RemoveDegenerateTriangles(out->num_collisiontriangles, out->data_collisionelement3i, out->data_collisionelement3i, out->data_collisionvertex3f);
4230                         if (developer.integer)
4231                         {
4232                                 if (out->num_collisiontriangles < finaltriangles)
4233                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided for collisions to %i vertices / %i triangles, %i degenerate triangles removed (leaving %i)\n", patchsize[0], patchsize[1], out->num_collisionvertices, finaltriangles, finaltriangles - out->num_collisiontriangles, out->num_collisiontriangles);
4234                                 else
4235                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided for collisions to %i vertices / %i triangles\n", patchsize[0], patchsize[1], out->num_collisionvertices, out->num_collisiontriangles);
4236                         }
4237                         break;
4238                 case Q3FACETYPE_FLARE:
4239                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): Q3FACETYPE_FLARE not supported (yet)\n", i, out->texture->name);
4240                         // don't render it
4241                         out->num_vertices = 0;
4242                         out->num_triangles = 0;
4243                         out->type = 0;
4244                         break;
4245                 }
4246                 for (j = 0, invalidelements = 0;j < out->num_triangles * 3;j++)
4247                         if (out->data_element3i[j] < 0 || out->data_element3i[j] >= out->num_vertices)
4248                                 invalidelements++;
4249                 if (invalidelements)
4250                 {
4251                         Con_Printf("Mod_Q3BSP_LoadFaces: Warning: face #%i has %i invalid elements, type = %i, texture->name = \"%s\", texture->surfaceflags = %i, texture->nativecontents = %i, firstvertex = %i, numvertices = %i, firstelement = %i, numelements = %i, elements list:\n", i, invalidelements, out->type, out->texture->name, out->texture->surfaceflags, out->texture->nativecontents, out->firstvertex, out->num_vertices, out->firstelement, out->num_triangles * 3);
4252                         for (j = 0;j < out->num_triangles * 3;j++)
4253                         {
4254                                 Con_Printf(" %i", out->data_element3i[j]);
4255                                 if (out->data_element3i[j] < 0 || out->data_element3i[j] >= out->num_vertices)
4256                                         out->data_element3i[j] = 0;
4257                         }
4258                         Con_Printf("\n");
4259                 }
4260                 // for shadow volumes
4261                 Mod_BuildTriangleNeighbors(out->data_neighbor3i, out->data_element3i, out->num_triangles);
4262                 // for per pixel lighting
4263                 Mod_BuildTextureVectorsAndNormals(out->num_vertices, out->num_triangles, out->data_vertex3f, out->data_texcoordtexture2f, out->data_element3i, out->data_svector3f, out->data_tvector3f, out->data_normal3f);
4264                 // calculate a bounding box
4265                 VectorClear(out->mins);
4266                 VectorClear(out->maxs);
4267                 if (out->num_vertices)
4268                 {
4269                         VectorCopy(out->data_vertex3f, out->mins);
4270                         VectorCopy(out->data_vertex3f, out->maxs);
4271                         for (j = 1, v = out->data_vertex3f + 3;j < out->num_vertices;j++, v += 3)
4272                         {
4273                                 out->mins[0] = min(out->mins[0], v[0]);
4274                                 out->maxs[0] = max(out->maxs[0], v[0]);
4275                                 out->mins[1] = min(out->mins[1], v[1]);
4276                                 out->maxs[1] = max(out->maxs[1], v[1]);
4277                                 out->mins[2] = min(out->mins[2], v[2]);
4278                                 out->maxs[2] = max(out->maxs[2], v[2]);
4279                         }
4280                         out->mins[0] -= 1.0f;
4281                         out->mins[1] -= 1.0f;
4282                         out->mins[2] -= 1.0f;
4283                         out->maxs[0] += 1.0f;
4284                         out->maxs[1] += 1.0f;
4285                         out->maxs[2] += 1.0f;
4286                 }
4287         }
4288
4289         // LordHavoc: experimental array merger (disabled because it wastes time and uses 2x memory while merging)
4290         /*
4291         {
4292         int totalverts, totaltris;
4293         int originalnum_vertices;
4294         float *originaldata_vertex3f;
4295         float *originaldata_texcoordtexture2f;
4296         float *originaldata_texcoordlightmap2f;
4297         float *originaldata_svector3f;
4298         float *originaldata_tvector3f;
4299         float *originaldata_normal3f;
4300         float *originaldata_color4f;
4301         int originalnum_triangles;
4302         int *originaldata_element3i;
4303         int *originaldata_neighbor3i;
4304
4305         totalverts = 0;
4306         totaltris = 0;
4307         for (i = 0, out = loadmodel->brushq3.data_faces;i < count;i++, out++)
4308         {
4309                 if (!out->type)
4310                         continue;
4311                 totalverts += out->num_vertices;
4312                 totaltris += out->num_triangles;
4313         }
4314
4315         originalnum_vertices = loadmodel->brushq3.num_vertices;
4316         originaldata_vertex3f = loadmodel->brushq3.data_vertex3f;
4317         originaldata_texcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f;
4318         originaldata_texcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f;
4319         originaldata_svector3f = loadmodel->brushq3.data_svector3f;
4320         originaldata_tvector3f = loadmodel->brushq3.data_tvector3f;
4321         originaldata_normal3f = loadmodel->brushq3.data_normal3f;
4322         originaldata_color4f = loadmodel->brushq3.data_color4f;
4323         originalnum_triangles = loadmodel->brushq3.num_triangles;
4324         originaldata_element3i = loadmodel->brushq3.data_element3i;
4325         originaldata_neighbor3i = loadmodel->brushq3.data_neighbor3i;
4326         loadmodel->brushq3.num_vertices = totalverts;
4327         loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, totalverts * (sizeof(float) * (3 + 2 + 2 + 3 + 3 + 3 + 4)) + totaltris * (sizeof(int) * (3 * 2)));
4328         loadmodel->brushq3.data_texcoordtexture2f = loadmodel->brushq3.data_vertex3f + totalverts * 3;
4329         loadmodel->brushq3.data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordtexture2f + totalverts * 2;
4330         loadmodel->brushq3.data_svector3f = loadmodel->brushq3.data_texcoordlightmap2f + totalverts * 2;
4331         loadmodel->brushq3.data_tvector3f = loadmodel->brushq3.data_svector3f + totalverts * 3;
4332         loadmodel->brushq3.data_normal3f = loadmodel->brushq3.data_tvector3f + totalverts * 3;
4333         loadmodel->brushq3.data_color4f = loadmodel->brushq3.data_normal3f + totalverts * 3;
4334         loadmodel->brushq3.num_triangles = totaltris;
4335         loadmodel->brushq3.data_element3i = (int *)(loadmodel->brushq3.data_color4f + totalverts * 4);
4336         loadmodel->brushq3.data_neighbor3i = loadmodel->brushq3.data_element3i + totaltris * 3;
4337         totalverts = 0;
4338         totaltris = 0;
4339         for (i = 0, out = loadmodel->brushq3.data_faces;i < count;i++, out++)
4340         {
4341                 if (!out->type)
4342                         continue;
4343                 Con_Printf("totalverts %i, totaltris %i\n", totalverts, totaltris);
4344                 memcpy(loadmodel->brushq3.data_vertex3f + totalverts * 3, out->data_vertex3f, out->num_vertices * 3 * sizeof(float));
4345                 memcpy(loadmodel->brushq3.data_texcoordtexture2f + totalverts * 2, out->data_texcoordtexture2f, out->num_vertices * 2 * sizeof(float));
4346                 memcpy(loadmodel->brushq3.data_texcoordlightmap2f + totalverts * 2, out->data_texcoordlightmap2f, out->num_vertices * 2 * sizeof(float));
4347                 memcpy(loadmodel->brushq3.data_svector3f + totalverts * 3, out->data_svector3f, out->num_vertices * 3 * sizeof(float));
4348                 memcpy(loadmodel->brushq3.data_tvector3f + totalverts * 3, out->data_tvector3f, out->num_vertices * 3 * sizeof(float));
4349                 memcpy(loadmodel->brushq3.data_normal3f + totalverts * 3, out->data_normal3f, out->num_vertices * 3 * sizeof(float));
4350                 memcpy(loadmodel->brushq3.data_color4f + totalverts * 4, out->data_color4f, out->num_vertices * 4 * sizeof(float));
4351                 memcpy(loadmodel->brushq3.data_element3i + totaltris * 3, out->data_element3i, out->num_triangles * 3 * sizeof(int));
4352                 memcpy(loadmodel->brushq3.data_neighbor3i + totaltris * 3, out->data_neighbor3i, out->num_triangles * 3 * sizeof(int));
4353                 if (out->firstvertex == -1)
4354                         Mem_Free(out->data_vertex3f);
4355                 if (out->firstelement == -1)
4356                         Mem_Free(out->data_element3i);
4357                 out->firstvertex = totalverts;
4358                 out->data_vertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
4359                 out->data_texcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f + out->firstvertex * 2;
4360                 out->data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f + out->firstvertex * 2;
4361                 out->data_svector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
4362                 out->data_tvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
4363                 out->data_normal3f = loadmodel->brushq3.data_normal3f + out->firstvertex * 3;
4364                 out->data_color4f = loadmodel->brushq3.data_color4f + out->firstvertex * 4;
4365                 out->firstelement = totaltris * 3;
4366                 out->data_element3i = loadmodel->brushq3.data_element3i + out->firstelement;
4367                 out->data_neighbor3i = loadmodel->brushq3.data_neighbor3i + out->firstelement;
4368                 //for (j = 0;j < out->numtriangles * 3;j++)
4369                 //      out->data_element3i[j] += totalverts - out->firstvertex;
4370                 totalverts += out->num_vertices;
4371                 totaltris += out->num_triangles;
4372         }
4373         Mem_Free(originaldata_vertex3f);
4374         Mem_Free(originaldata_element3i);
4375         }
4376         */
4377 }
4378
4379 static void Mod_Q3BSP_LoadModels(lump_t *l)
4380 {
4381         q3dmodel_t *in;
4382         q3mmodel_t *out;
4383         int i, j, n, c, count;
4384
4385         in = (void *)(mod_base + l->fileofs);
4386         if (l->filelen % sizeof(*in))
4387                 Host_Error("Mod_Q3BSP_LoadModels: funny lump size in %s",loadmodel->name);
4388         count = l->filelen / sizeof(*in);
4389         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4390
4391         loadmodel->brushq3.data_models = out;
4392         loadmodel->brushq3.num_models = count;
4393
4394         for (i = 0;i < count;i++, in++, out++)
4395         {
4396                 for (j = 0;j < 3;j++)
4397                 {
4398                         out->mins[j] = LittleFloat(in->mins[j]);
4399                         out->maxs[j] = LittleFloat(in->maxs[j]);
4400                 }
4401                 n = LittleLong(in->firstface);
4402                 c = LittleLong(in->numfaces);
4403                 if (n < 0 || n + c > loadmodel->brushq3.num_faces)
4404                         Host_Error("Mod_Q3BSP_LoadModels: invalid face range %i : %i (%i faces)\n", n, n + c, loadmodel->brushq3.num_faces);
4405                 out->firstface = loadmodel->brushq3.data_faces + n;
4406                 out->numfaces = c;
4407                 n = LittleLong(in->firstbrush);
4408                 c = LittleLong(in->numbrushes);
4409                 if (n < 0 || n + c > loadmodel->brushq3.num_brushes)
4410                         Host_Error("Mod_Q3BSP_LoadModels: invalid brush range %i : %i (%i brushes)\n", n, n + c, loadmodel->brushq3.num_brushes);
4411                 out->firstbrush = loadmodel->brushq3.data_brushes + n;
4412                 out->numbrushes = c;
4413         }
4414 }
4415
4416 static void Mod_Q3BSP_LoadLeafBrushes(lump_t *l)
4417 {
4418         int *in;
4419         q3mbrush_t **out;
4420         int i, n, count;
4421
4422         in = (void *)(mod_base + l->fileofs);
4423         if (l->filelen % sizeof(*in))
4424                 Host_Error("Mod_Q3BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
4425         count = l->filelen / sizeof(*in);
4426         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4427
4428         loadmodel->brushq3.data_leafbrushes = out;
4429         loadmodel->brushq3.num_leafbrushes = count;
4430
4431         for (i = 0;i < count;i++, in++, out++)
4432         {
4433                 n = LittleLong(*in);
4434                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
4435                         Host_Error("Mod_Q3BSP_LoadLeafBrushes: invalid brush index %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
4436                 *out = loadmodel->brushq3.data_brushes + n;
4437         }
4438 }
4439
4440 static void Mod_Q3BSP_LoadLeafFaces(lump_t *l)
4441 {
4442         int *in;
4443         q3mface_t **out;
4444         int i, n, count;
4445
4446         in = (void *)(mod_base + l->fileofs);
4447         if (l->filelen % sizeof(*in))
4448                 Host_Error("Mod_Q3BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
4449         count = l->filelen / sizeof(*in);
4450         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4451
4452         loadmodel->brushq3.data_leaffaces = out;
4453         loadmodel->brushq3.num_leaffaces = count;
4454
4455         for (i = 0;i < count;i++, in++, out++)
4456         {
4457                 n = LittleLong(*in);
4458                 if (n < 0 || n >= loadmodel->brushq3.num_faces)
4459                         Host_Error("Mod_Q3BSP_LoadLeafFaces: invalid face index %i (%i faces)\n", n, loadmodel->brushq3.num_faces);
4460                 *out = loadmodel->brushq3.data_faces + n;
4461         }
4462 }
4463
4464 static void Mod_Q3BSP_LoadLeafs(lump_t *l)
4465 {
4466         q3dleaf_t *in;
4467         q3mleaf_t *out;
4468         int i, j, n, c, count;
4469
4470         in = (void *)(mod_base + l->fileofs);
4471         if (l->filelen % sizeof(*in))
4472                 Host_Error("Mod_Q3BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
4473         count = l->filelen / sizeof(*in);
4474         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4475
4476         loadmodel->brushq3.data_leafs = out;
4477         loadmodel->brushq3.num_leafs = count;
4478
4479         for (i = 0;i < count;i++, in++, out++)
4480         {
4481                 out->parent = NULL;
4482                 out->plane = NULL;
4483                 out->clusterindex = LittleLong(in->clusterindex);
4484                 out->areaindex = LittleLong(in->areaindex);
4485                 for (j = 0;j < 3;j++)
4486                 {
4487                         // yes the mins/maxs are ints
4488                         out->mins[j] = LittleLong(in->mins[j]) - 1;
4489                         out->maxs[j] = LittleLong(in->maxs[j]) + 1;
4490                 }
4491                 n = LittleLong(in->firstleafface);
4492                 c = LittleLong(in->numleaffaces);
4493                 if (n < 0 || n + c > loadmodel->brushq3.num_leaffaces)
4494                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafface range %i : %i (%i leaffaces)\n", n, n + c, loadmodel->brushq3.num_leaffaces);
4495                 out->firstleafface = loadmodel->brushq3.data_leaffaces + n;
4496                 out->numleaffaces = c;
4497                 n = LittleLong(in->firstleafbrush);
4498                 c = LittleLong(in->numleafbrushes);
4499                 if (n < 0 || n + c > loadmodel->brushq3.num_leafbrushes)
4500                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafbrush range %i : %i (%i leafbrushes)\n", n, n + c, loadmodel->brushq3.num_leafbrushes);
4501                 out->firstleafbrush = loadmodel->brushq3.data_leafbrushes + n;
4502                 out->numleafbrushes = c;
4503         }
4504 }
4505
4506 static void Mod_Q3BSP_LoadNodes_RecursiveSetParent(q3mnode_t *node, q3mnode_t *parent)
4507 {
4508         if (node->parent)
4509                 Host_Error("Mod_Q3BSP_LoadNodes_RecursiveSetParent: runaway recursion\n");
4510         node->parent = parent;
4511         if (node->plane)
4512         {
4513                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
4514                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
4515         }
4516 }
4517
4518 static void Mod_Q3BSP_LoadNodes(lump_t *l)
4519 {
4520         q3dnode_t *in;
4521         q3mnode_t *out;
4522         int i, j, n, count;
4523
4524         in = (void *)(mod_base + l->fileofs);
4525         if (l->filelen % sizeof(*in))
4526                 Host_Error("Mod_Q3BSP_LoadNodes: funny lump size in %s",loadmodel->name);
4527         count = l->filelen / sizeof(*in);
4528         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4529
4530         loadmodel->brushq3.data_nodes = out;
4531         loadmodel->brushq3.num_nodes = count;
4532
4533         for (i = 0;i < count;i++, in++, out++)
4534         {
4535                 out->parent = NULL;
4536                 n = LittleLong(in->planeindex);
4537                 if (n < 0 || n >= loadmodel->brushq3.num_planes)
4538                         Host_Error("Mod_Q3BSP_LoadNodes: invalid planeindex %i (%i planes)\n", n, loadmodel->brushq3.num_planes);
4539                 out->plane = loadmodel->brushq3.data_planes + n;
4540                 for (j = 0;j < 2;j++)
4541                 {
4542                         n = LittleLong(in->childrenindex[j]);
4543                         if (n >= 0)
4544                         {
4545                                 if (n >= loadmodel->brushq3.num_nodes)
4546                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child node index %i (%i nodes)\n", n, loadmodel->brushq3.num_nodes);
4547                                 out->children[j] = loadmodel->brushq3.data_nodes + n;
4548                         }
4549                         else
4550                         {
4551                                 n = -1 - n;
4552                                 if (n >= loadmodel->brushq3.num_leafs)
4553                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child leaf index %i (%i leafs)\n", n, loadmodel->brushq3.num_leafs);
4554                                 out->children[j] = (q3mnode_t *)(loadmodel->brushq3.data_leafs + n);
4555                         }
4556                 }
4557                 for (j = 0;j < 3;j++)
4558                 {
4559                         // yes the mins/maxs are ints
4560                         out->mins[j] = LittleLong(in->mins[j]) - 1;
4561                         out->maxs[j] = LittleLong(in->maxs[j]) + 1;
4562                 }
4563         }
4564
4565         // set the parent pointers
4566         Mod_Q3BSP_LoadNodes_RecursiveSetParent(loadmodel->brushq3.data_nodes, NULL);
4567 }
4568
4569 static void Mod_Q3BSP_LoadLightGrid(lump_t *l)
4570 {
4571         q3dlightgrid_t *in;
4572         q3dlightgrid_t *out;
4573         int count;
4574
4575         in = (void *)(mod_base + l->fileofs);
4576         if (l->filelen % sizeof(*in))
4577                 Host_Error("Mod_Q3BSP_LoadLightGrid: funny lump size in %s",loadmodel->name);
4578         loadmodel->brushq3.num_lightgrid_scale[0] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[0];
4579         loadmodel->brushq3.num_lightgrid_scale[1] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[1];
4580         loadmodel->brushq3.num_lightgrid_scale[2] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[2];
4581         loadmodel->brushq3.num_lightgrid_imins[0] = ceil(loadmodel->brushq3.data_models->mins[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4582         loadmodel->brushq3.num_lightgrid_imins[1] = ceil(loadmodel->brushq3.data_models->mins[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4583         loadmodel->brushq3.num_lightgrid_imins[2] = ceil(loadmodel->brushq3.data_models->mins[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4584         loadmodel->brushq3.num_lightgrid_imaxs[0] = floor(loadmodel->brushq3.data_models->maxs[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4585         loadmodel->brushq3.num_lightgrid_imaxs[1] = floor(loadmodel->brushq3.data_models->maxs[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4586         loadmodel->brushq3.num_lightgrid_imaxs[2] = floor(loadmodel->brushq3.data_models->maxs[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4587         loadmodel->brushq3.num_lightgrid_isize[0] = loadmodel->brushq3.num_lightgrid_imaxs[0] - loadmodel->brushq3.num_lightgrid_imins[0] + 1;
4588         loadmodel->brushq3.num_lightgrid_isize[1] = loadmodel->brushq3.num_lightgrid_imaxs[1] - loadmodel->brushq3.num_lightgrid_imins[1] + 1;
4589         loadmodel->brushq3.num_lightgrid_isize[2] = loadmodel->brushq3.num_lightgrid_imaxs[2] - loadmodel->brushq3.num_lightgrid_imins[2] + 1;
4590         count = loadmodel->brushq3.num_lightgrid_isize[0] * loadmodel->brushq3.num_lightgrid_isize[1] * loadmodel->brushq3.num_lightgrid_isize[2];
4591         if (l->filelen)
4592         {
4593                 if (l->filelen < count * (int)sizeof(*in))
4594                         Host_Error("Mod_Q3BSP_LoadLightGrid: invalid lightgrid lump size %i bytes, should be %i bytes (%ix%ix%i)\n", l->filelen, count * sizeof(*in), loadmodel->brushq3.num_lightgrid_dimensions[0], loadmodel->brushq3.num_lightgrid_dimensions[1], loadmodel->brushq3.num_lightgrid_dimensions[2]);
4595                 if (l->filelen != count * (int)sizeof(*in))
4596                         Con_Printf("Mod_Q3BSP_LoadLightGrid: Warning: calculated lightgrid size %i bytes does not match lump size %i\n", count * sizeof(*in), l->filelen);
4597         }
4598
4599         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4600         loadmodel->brushq3.data_lightgrid = out;
4601         loadmodel->brushq3.num_lightgrid = count;
4602
4603         // no swapping or validation necessary
4604         if (l->filelen)
4605                 memcpy(out, in, count * (int)sizeof(*out));
4606         else
4607         {
4608                 // no data, fill with white
4609                 int i;
4610                 for (i = 0;i < count;i++)
4611                 {
4612                         out[i].ambientrgb[0] = 128;
4613                         out[i].ambientrgb[1] = 128;
4614                         out[i].ambientrgb[2] = 128;
4615                         out[i].diffusergb[0] = 0;
4616                         out[i].diffusergb[1] = 0;
4617                         out[i].diffusergb[2] = 0;
4618                         out[i].diffusepitch = 0;
4619                         out[i].diffuseyaw = 0;
4620                 }
4621         }
4622
4623         Matrix4x4_CreateScale3(&loadmodel->brushq3.num_lightgrid_indexfromworld, loadmodel->brushq3.num_lightgrid_scale[0], loadmodel->brushq3.num_lightgrid_scale[1], loadmodel->brushq3.num_lightgrid_scale[2]);
4624         Matrix4x4_ConcatTranslate(&loadmodel->brushq3.num_lightgrid_indexfromworld, -loadmodel->brushq3.num_lightgrid_imins[0] * loadmodel->brushq3.num_lightgrid_cellsize[0], -loadmodel->brushq3.num_lightgrid_imins[1] * loadmodel->brushq3.num_lightgrid_cellsize[1], -loadmodel->brushq3.num_lightgrid_imins[2] * loadmodel->brushq3.num_lightgrid_cellsize[2]);
4625 }
4626
4627 static void Mod_Q3BSP_LoadPVS(lump_t *l)
4628 {
4629         q3dpvs_t *in;
4630         int totalchains;
4631
4632         if (l->filelen == 0)
4633         {
4634                 int i;
4635                 // unvised maps often have cluster indices even without pvs, so check
4636                 // leafs to find real number of clusters
4637                 loadmodel->brush.num_pvsclusters = 1;
4638                 for (i = 0;i < loadmodel->brushq3.num_leafs;i++)
4639                         loadmodel->brush.num_pvsclusters = min(loadmodel->brush.num_pvsclusters, loadmodel->brushq3.data_leafs[i].clusterindex + 1);
4640
4641                 // create clusters
4642                 loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters + 7) / 8;
4643                 totalchains = loadmodel->brush.num_pvsclusterbytes * loadmodel->brush.num_pvsclusters;
4644                 loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, totalchains);
4645                 memset(loadmodel->brush.data_pvsclusters, 0xFF, totalchains);
4646                 return;
4647         }
4648
4649         in = (void *)(mod_base + l->fileofs);
4650         if (l->filelen < 9)
4651                 Host_Error("Mod_Q3BSP_LoadPVS: funny lump size in %s",loadmodel->name);
4652
4653         loadmodel->brush.num_pvsclusters = LittleLong(in->numclusters);
4654         loadmodel->brush.num_pvsclusterbytes = LittleLong(in->chainlength);
4655         if (loadmodel->brush.num_pvsclusterbytes < ((loadmodel->brush.num_pvsclusters + 7) / 8))
4656                 Host_Error("Mod_Q3BSP_LoadPVS: (chainlength = %i) < ((numclusters = %i) + 7) / 8\n", loadmodel->brush.num_pvsclusterbytes, loadmodel->brush.num_pvsclusters);
4657         totalchains = loadmodel->brush.num_pvsclusterbytes * loadmodel->brush.num_pvsclusters;
4658         if (l->filelen < totalchains + (int)sizeof(*in))
4659                 Host_Error("Mod_Q3BSP_LoadPVS: lump too small ((numclusters = %i) * (chainlength = %i) + sizeof(q3dpvs_t) == %i bytes, lump is %i bytes)\n", loadmodel->brush.num_pvsclusters, loadmodel->brush.num_pvsclusterbytes, totalchains + sizeof(*in), l->filelen);
4660
4661         loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, totalchains);
4662         memcpy(loadmodel->brush.data_pvsclusters, (qbyte *)(in + 1), totalchains);
4663 }
4664
4665 static void Mod_Q3BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, vec_t radius)
4666 {
4667         // FIXME: finish this code
4668         VectorCopy(in, out);
4669 }
4670
4671 static void Mod_Q3BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
4672 {
4673         int i, j, k, index[3];
4674         float transformed[3], blend1, blend2, blend, yaw, pitch, sinpitch;
4675         q3dlightgrid_t *a, *s;
4676         // FIXME: write this
4677         if (!model->brushq3.num_lightgrid)
4678         {
4679                 ambientcolor[0] = 1;
4680                 ambientcolor[1] = 1;
4681                 ambientcolor[2] = 1;
4682                 return;
4683         }
4684         Matrix4x4_Transform(&model->brushq3.num_lightgrid_indexfromworld, p, transformed);
4685         //Matrix4x4_Print(&model->brushq3.num_lightgrid_indexfromworld);
4686         //Con_Printf("%f %f %f transformed %f %f %f clamped ", p[0], p[1], p[2], transformed[0], transformed[1], transformed[2]);
4687         transformed[0] = bound(0, transformed[0], model->brushq3.num_lightgrid_isize[0] - 1);
4688         transformed[1] = bound(0, transformed[1], model->brushq3.num_lightgrid_isize[1] - 1);
4689         transformed[2] = bound(0, transformed[2], model->brushq3.num_lightgrid_isize[2] - 1);
4690         index[0] = (int)floor(transformed[0]);
4691         index[1] = (int)floor(transformed[1]);
4692         index[2] = (int)floor(transformed[2]);
4693         //Con_Printf("%f %f %f index %i %i %i:\n", transformed[0], transformed[1], transformed[2], index[0], index[1], index[2]);
4694         // now lerp the values
4695         VectorClear(diffusenormal);
4696         a = &model->brushq3.data_lightgrid[(index[2] * model->brushq3.num_lightgrid_isize[1] + index[1]) * model->brushq3.num_lightgrid_isize[0] + index[0]];
4697         for (k = 0;k < 2;k++)
4698         {
4699                 blend1 = (k ? (transformed[2] - index[2]) : (1 - (transformed[2] - index[2])));
4700                 if (blend1 < 0.001f || index[2] + k >= model->brushq3.num_lightgrid_isize[2])
4701                         continue;
4702                 for (j = 0;j < 2;j++)
4703                 {
4704                         blend2 = blend1 * (j ? (transformed[1] - index[1]) : (1 - (transformed[1] - index[1])));
4705                         if (blend2 < 0.001f || index[1] + j >= model->brushq3.num_lightgrid_isize[1])
4706                                 continue;
4707                         for (i = 0;i < 2;i++)
4708                         {
4709                                 blend = blend2 * (i ? (transformed[0] - index[0]) : (1 - (transformed[0] - index[0])));
4710                                 if (blend < 0.001f || index[0] + i >= model->brushq3.num_lightgrid_isize[0])
4711                                         continue;
4712                                 s = a + (k * model->brushq3.num_lightgrid_isize[1] + j) * model->brushq3.num_lightgrid_isize[0] + i;
4713                                 VectorMA(ambientcolor, blend * (1.0f / 128.0f), s->ambientrgb, ambientcolor);
4714                                 VectorMA(diffusecolor, blend * (1.0f / 128.0f), s->diffusergb, diffusecolor);
4715                                 pitch = s->diffusepitch * M_PI / 128;
4716                                 yaw = s->diffuseyaw * M_PI / 128;
4717                                 sinpitch = sin(pitch);
4718                                 diffusenormal[0] += blend * (cos(yaw) * sinpitch);
4719                                 diffusenormal[1] += blend * (sin(yaw) * sinpitch);
4720                                 diffusenormal[2] += blend * (cos(pitch));
4721                                 //Con_Printf("blend %f: ambient %i %i %i, diffuse %i %i %i, diffusepitch %i diffuseyaw %i (%f %f, normal %f %f %f)\n", blend, s->ambientrgb[0], s->ambientrgb[1], s->ambientrgb[2], s->diffusergb[0], s->diffusergb[1], s->diffusergb[2], s->diffusepitch, s->diffuseyaw, pitch, yaw, (cos(yaw) * cospitch), (sin(yaw) * cospitch), (-sin(pitch)));
4722                         }
4723                 }
4724         }
4725         VectorNormalize(diffusenormal);
4726         //Con_Printf("result: ambient %f %f %f diffuse %f %f %f diffusenormal %f %f %f\n", ambientcolor[0], ambientcolor[1], ambientcolor[2], diffusecolor[0], diffusecolor[1], diffusecolor[2], diffusenormal[0], diffusenormal[1], diffusenormal[2]);
4727 }
4728
4729 static void Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const vec3_t point, int markframe)
4730 {
4731         int i;
4732         q3mleaf_t *leaf;
4733         colbrushf_t *brush;
4734         // find which leaf the point is in
4735         while (node->plane)
4736                 node = node->children[DotProduct(point, node->plane->normal) < node->plane->dist];
4737         // point trace the brushes
4738         leaf = (q3mleaf_t *)node;
4739         for (i = 0;i < leaf->numleafbrushes;i++)
4740         {
4741                 brush = leaf->firstleafbrush[i]->colbrushf;
4742                 if (brush && brush->markframe != markframe && BoxesOverlap(point, point, brush->mins, brush->maxs))
4743                 {
4744                         brush->markframe = markframe;
4745                         Collision_TracePointBrushFloat(trace, point, leaf->firstleafbrush[i]->colbrushf);
4746                 }
4747         }
4748         // can't do point traces on curves (they have no thickness)
4749 }
4750
4751 static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const vec3_t start, const vec3_t end, vec_t startfrac, vec_t endfrac, const vec3_t linestart, const vec3_t lineend, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
4752 {
4753         int i, startside, endside;
4754         float dist1, dist2, midfrac, mid[3], nodesegmentmins[3], nodesegmentmaxs[3];
4755         q3mleaf_t *leaf;
4756         q3mface_t *face;
4757         colbrushf_t *brush;
4758         if (startfrac > trace->realfraction)
4759                 return;
4760         // note: all line fragments past first impact fraction are ignored
4761         if (VectorCompare(start, end))
4762         {
4763                 // find which leaf the point is in
4764                 while (node->plane)
4765                         node = node->children[DotProduct(start, node->plane->normal) < node->plane->dist];
4766         }
4767         else
4768         {
4769                 // find which nodes the line is in and recurse for them
4770                 while (node->plane)
4771                 {
4772                         // recurse down node sides
4773                         dist1 = PlaneDiff(start, node->plane);
4774                         dist2 = PlaneDiff(end, node->plane);
4775                         startside = dist1 < 0;
4776                         endside = dist2 < 0;
4777                         if (startside == endside)
4778                         {
4779                                 // most of the time the line fragment is on one side of the plane
4780                                 node = node->children[startside];
4781                         }
4782                         else
4783                         {
4784                                 // line crosses node plane, split the line
4785                                 midfrac = dist1 / (dist1 - dist2);
4786                                 VectorLerp(start, midfrac, end, mid);
4787                                 // take the near side first
4788                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
4789                                 if (midfrac <= trace->realfraction)
4790                                         Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
4791                                 return;
4792                         }
4793                 }
4794         }
4795         // hit a leaf
4796         nodesegmentmins[0] = min(start[0], end[0]);
4797         nodesegmentmins[1] = min(start[1], end[1]);
4798         nodesegmentmins[2] = min(start[2], end[2]);
4799         nodesegmentmaxs[0] = max(start[0], end[0]);
4800         nodesegmentmaxs[1] = max(start[1], end[1]);
4801         nodesegmentmaxs[2] = max(start[2], end[2]);
4802         // line trace the brushes
4803         leaf = (q3mleaf_t *)node;
4804         for (i = 0;i < leaf->numleafbrushes;i++)
4805         {
4806                 brush = leaf->firstleafbrush[i]->colbrushf;
4807                 if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
4808                 {
4809                         brush->markframe = markframe;
4810                         Collision_TraceLineBrushFloat(trace, linestart, lineend, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
4811                         if (startfrac > trace->realfraction)
4812                                 return;
4813                 }
4814         }
4815         // can't do point traces on curves (they have no thickness)
4816         if (mod_q3bsp_curves_collisions.integer && !VectorCompare(start, end))
4817         {
4818                 // line trace the curves
4819                 for (i = 0;i < leaf->numleaffaces;i++)
4820                 {
4821                         face = leaf->firstleafface[i];
4822                         if (face->collisions && face->collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
4823                         {
4824                                 face->collisionmarkframe = markframe;
4825                                 Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
4826                                 if (startfrac > trace->realfraction)
4827                                         return;
4828                         }
4829                 }
4830         }
4831 }
4832
4833 static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
4834 {
4835         int i;
4836         //int sides;
4837         float nodesegmentmins[3], nodesegmentmaxs[3];
4838         q3mleaf_t *leaf;
4839         colbrushf_t *brush;
4840         q3mface_t *face;
4841         /*
4842                 // find which nodes the line is in and recurse for them
4843                 while (node->plane)
4844                 {
4845                         // recurse down node sides
4846                         int startside, endside;
4847                         float dist1near, dist1far, dist2near, dist2far;
4848                         BoxPlaneCornerDistances(thisbrush_start->mins, thisbrush_start->maxs, node->plane, &dist1near, &dist1far);
4849                         BoxPlaneCornerDistances(thisbrush_end->mins, thisbrush_end->maxs, node->plane, &dist2near, &dist2far);
4850                         startside = dist1near < 0;
4851                         startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
4852                         endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
4853                         if (startside == 2 || endside == 2)
4854                         {
4855                                 // brushes cross plane
4856                                 // do not clip anything, just take both sides
4857                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4858                                 node = node->children[1];
4859                                 continue;
4860                         }
4861                         if (startside == 0)
4862                         {
4863                                 if (endside == 0)
4864                                 {
4865                                         node = node->children[0];
4866                                         continue;
4867                                 }
4868                                 else
4869                                 {
4870                                         //midf0 = dist1near / (dist1near - dist2near);
4871                                         //midf1 = dist1far / (dist1far - dist2far);
4872                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4873                                         node = node->children[1];
4874                                         continue;
4875                                 }
4876                         }
4877                         else
4878                         {
4879                                 if (endside == 0)
4880                                 {
4881                                         //midf0 = dist1near / (dist1near - dist2near);
4882                                         //midf1 = dist1far / (dist1far - dist2far);
4883                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4884                                         node = node->children[1];
4885                                         continue;
4886                                 }
4887                                 else
4888                                 {
4889                                         node = node->children[1];
4890                                         continue;
4891                                 }
4892                         }
4893
4894                         if (dist1near <  0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4895                         if (dist1near <  0 && dist2near <  0 && dist1far <  0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4896                         if (dist1near <  0 && dist2near <  0 && dist1far >= 0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4897                         if (dist1near <  0 && dist2near <  0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4898                         if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4899                         if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){}
4900                         if (dist1near <  0 && dist2near >= 0 && dist1far >= 0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4901                         if (dist1near <  0 && dist2near >= 0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4902                         if (dist1near >= 0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4903                         if (dist1near >= 0 && dist2near <  0 && dist1far <  0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4904                         if (dist1near >= 0 && dist2near <  0 && dist1far >= 0 && dist2far <  0){}
4905                         if (dist1near >= 0 && dist2near <  0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4906                         if (dist1near >= 0 && dist2near >= 0 && dist1far <  0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4907                         if (dist1near >= 0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){node = node->children[0];continue;}
4908                         if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far <  0){node = node->children[0];continue;}
4909                         if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far >= 0){node = node->children[0];continue;}
4910                         {
4911                                 if (dist2near < 0) // d1n<0 && d2n<0
4912                                 {
4913                                         if (dist2near < 0) // d1n<0 && d2n<0
4914                                         {
4915                                                 if (dist2near < 0) // d1n<0 && d2n<0
4916                                                 {
4917                                                 }
4918                                                 else // d1n<0 && d2n>0
4919                                                 {
4920                                                 }
4921                                         }
4922                                         else // d1n<0 && d2n>0
4923                                         {
4924                                                 if (dist2near < 0) // d1n<0 && d2n<0
4925                                                 {
4926                                                 }
4927                                                 else // d1n<0 && d2n>0
4928                                                 {
4929                                                 }
4930                                         }
4931                                 }
4932                                 else // d1n<0 && d2n>0
4933                                 {
4934                                 }
4935                         }
4936                         else // d1n>0
4937                         {
4938                                 if (dist2near < 0) // d1n>0 && d2n<0
4939                                 {
4940                                 }
4941                                 else // d1n>0 && d2n>0
4942                                 {
4943                                 }
4944                         }
4945                         if (dist1near < 0 == dist1far < 0 == dist2near < 0 == dist2far < 0)
4946                         {
4947                                 node = node->children[startside];
4948                                 continue;
4949                         }
4950                         if (dist1near < dist2near)
4951                         {
4952                                 // out
4953                                 if (dist1near >= 0)
4954                                 {
4955                                         node = node->children[0];
4956                                         continue;
4957                                 }
4958                                 if (dist2far < 0)
4959                                 {
4960                                         node = node->children[1];
4961                                         continue;
4962                                 }
4963                                 // dist1near < 0 && dist2far >= 0
4964                         }
4965                         else
4966                         {
4967                                 // in
4968                         }
4969                         startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
4970                         endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
4971                         if (startside == 2 || endside == 2)
4972                         {
4973                                 // brushes cross plane
4974                                 // do not clip anything, just take both sides
4975                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4976                                 node = node->children[1];
4977                         }
4978                         else if (startside == endside)
4979                                 node = node->children[startside];
4980                         else if (startside == 0) // endside = 1 (start infront, end behind)
4981                         {
4982                         }
4983                         else // startside == 1 endside = 0 (start behind, end infront)
4984                         {
4985                         }
4986                         == endside)
4987                         {
4988                                 if (startside < 2)
4989                                         node = node->children[startside];
4990                                 else
4991                                 {
4992                                         // start and end brush cross plane
4993                                 }
4994                         }
4995                         else
4996                         {
4997                         }
4998                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
4999                                 node = node->children[1];
5000                         else if (dist1near < 0 && dist1far < 0 && dist2near >= 0 && dist2far >= 0)
5001                         else if (dist1near >= 0 && dist1far >= 0 && dist2near < 0 && dist2far < 0)
5002                         else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
5003                                 node = node->children[0];
5004                         else
5005                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5006                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5007                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5008                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5009                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5010                         {
5011                         }
5012                         else if (dist1near >= 0 && dist1far >= 0)
5013                         {
5014                         }
5015                         else // mixed (lying on plane)
5016                         {
5017                         }
5018                         {
5019                                 if (dist2near < 0 && dist2far < 0)
5020                                 {
5021                                 }
5022                                 else
5023                                         node = node->children[1];
5024                         }
5025                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5026                                 node = node->children[0];
5027                         else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
5028                                 node = node->children[1];
5029                         else
5030                         {
5031                                 // both sides
5032                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5033                                 node = node->children[1];
5034                         }
5035                         sides = dist1near || dist1near < 0 | dist1far < 0 | dist2near < 0 | dist
5036                         startside = dist1 < 0;
5037                         endside = dist2 < 0;
5038                         if (startside == endside)
5039                         {
5040                                 // most of the time the line fragment is on one side of the plane
5041                                 node = node->children[startside];
5042                         }
5043                         else
5044                         {
5045                                 // line crosses node plane, split the line
5046                                 midfrac = dist1 / (dist1 - dist2);
5047                                 VectorLerp(start, midfrac, end, mid);
5048                                 // take the near side first
5049                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5050                                 if (midfrac <= trace->fraction)
5051                                         Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5052                                 return;
5053                         }
5054                 }
5055         */
5056 #if 1
5057         for (;;)
5058         {
5059                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5060                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5061                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5062                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5063                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5064                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5065                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5066                         return;
5067                 if (!node->plane)
5068                         break;
5069                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5070                 node = node->children[1];
5071         }
5072 #elif 0
5073         // FIXME: could be made faster by copying TraceLine code and making it use
5074         // box plane distances...  (variant on the BoxOnPlaneSide code)
5075         for (;;)
5076         {
5077                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5078                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5079                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5080                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5081                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5082                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5083                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5084                         return;
5085                 if (!node->plane)
5086                         break;
5087                 if (mod_q3bsp_debugtracebrush.integer == 2)
5088                 {
5089                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5090                         node = node->children[1];
5091                         continue;
5092                 }
5093                 else if (mod_q3bsp_debugtracebrush.integer == 1)
5094                 {
5095                         // recurse down node sides
5096                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5097                         if (sides == 3)
5098                         {
5099                                 // segment box crosses plane
5100                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5101                                 node = node->children[1];
5102                                 continue;
5103                         }
5104                         // take whichever side the segment box is on
5105                         node = node->children[sides - 1];
5106                         continue;
5107                 }
5108                 else
5109                 {
5110                         // recurse down node sides
5111                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5112                         if (sides == 3)
5113                         {
5114                                 // segment box crosses plane
5115                                 // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
5116                                 sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, node->plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, node->plane);
5117                                 if (sides == 3)
5118                                 {
5119                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5120                                         node = node->children[1];
5121                                         continue;
5122                                 }
5123                         }
5124                         // take whichever side the segment box is on
5125                         node = node->children[sides - 1];
5126                         continue;
5127                 }
5128                 return;
5129         }
5130 #else
5131         // FIXME: could be made faster by copying TraceLine code and making it use
5132         // box plane distances...  (variant on the BoxOnPlaneSide code)
5133         for (;;)
5134         {
5135                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5136                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5137                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5138                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5139                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5140                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5141                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5142                         return;
5143                 if (!node->plane)
5144                         break;
5145                 if (mod_q3bsp_debugtracebrush.integer == 2)
5146                 {
5147                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5148                         node = node->children[1];
5149                 }
5150                 else if (mod_q3bsp_debugtracebrush.integer == 1)
5151                 {
5152                         // recurse down node sides
5153                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5154                         if (sides == 3)
5155                         {
5156                                 // segment box crosses plane
5157                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5158                                 node = node->children[1];
5159                         }
5160                         else
5161                         {
5162                                 // take whichever side the segment box is on
5163                                 node = node->children[sides - 1];
5164                         }
5165                 }
5166                 else
5167                 {
5168                         // recurse down node sides
5169                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5170                         if (sides == 3)
5171                         {
5172                                 // segment box crosses plane
5173                                 // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
5174                                 sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, node->plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, node->plane);
5175                                 if (sides == 3)
5176                                 {
5177                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5178                                         sides = 2;
5179                                 }
5180                         }
5181                         // take whichever side the segment box is on
5182                         node = node->children[sides - 1];
5183                 }
5184         }
5185 #endif
5186         // hit a leaf
5187         leaf = (q3mleaf_t *)node;
5188         for (i = 0;i < leaf->numleafbrushes;i++)
5189         {
5190                 brush = leaf->firstleafbrush[i]->colbrushf;
5191                 if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
5192                 {
5193                         brush->markframe = markframe;
5194                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
5195                 }
5196         }
5197         if (mod_q3bsp_curves_collisions.integer)
5198         {
5199                 for (i = 0;i < leaf->numleaffaces;i++)
5200                 {
5201                         face = leaf->firstleafface[i];
5202                         if (face->collisions && face->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
5203                         {
5204                                 face->markframe = markframe;
5205                                 Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5206                         }
5207                 }
5208         }
5209 }
5210
5211 static void Mod_Q3BSP_TraceBox(model_t *model, int frame, trace_t *trace, const vec3_t boxstartmins, const vec3_t boxstartmaxs, const vec3_t boxendmins, const vec3_t boxendmaxs, int hitsupercontentsmask)
5212 {
5213         int i;
5214         float segmentmins[3], segmentmaxs[3];
5215         colbrushf_t *thisbrush_start, *thisbrush_end;
5216         matrix4x4_t startmatrix, endmatrix;
5217         static int markframe = 0;
5218         q3mface_t *face;
5219         memset(trace, 0, sizeof(*trace));
5220         trace->fraction = 1;
5221         trace->realfraction = 1;
5222         trace->hitsupercontentsmask = hitsupercontentsmask;
5223         Matrix4x4_CreateIdentity(&startmatrix);
5224         Matrix4x4_CreateIdentity(&endmatrix);
5225         segmentmins[0] = min(boxstartmins[0], boxendmins[0]);
5226         segmentmins[1] = min(boxstartmins[1], boxendmins[1]);
5227         segmentmins[2] = min(boxstartmins[2], boxendmins[2]);
5228         segmentmaxs[0] = max(boxstartmaxs[0], boxendmaxs[0]);
5229         segmentmaxs[1] = max(boxstartmaxs[1], boxendmaxs[1]);
5230         segmentmaxs[2] = max(boxstartmaxs[2], boxendmaxs[2]);
5231         if (mod_q3bsp_optimizedtraceline.integer && VectorCompare(boxstartmins, boxstartmaxs) && VectorCompare(boxendmins, boxendmaxs))
5232         {
5233                 if (VectorCompare(boxstartmins, boxendmins))
5234                 {
5235                         // point trace
5236                         if (model->brushq3.submodel)
5237                         {
5238                                 for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
5239                                         if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
5240                                                 Collision_TracePointBrushFloat(trace, boxstartmins, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
5241                         }
5242                         else
5243                                 Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace, model->brushq3.data_nodes, boxstartmins, ++markframe);
5244                 }
5245                 else
5246                 {
5247                         // line trace
5248                         if (model->brushq3.submodel)
5249                         {
5250                                 for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
5251                                         if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
5252                                                 Collision_TraceLineBrushFloat(trace, boxstartmins, boxendmins, model->brushq3.data_thismodel->firstbrush[i].colbrushf, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
5253                                 if (mod_q3bsp_curves_collisions.integer)
5254                                 {
5255                                         for (i = 0;i < model->brushq3.data_thismodel->numfaces;i++)
5256                                         {
5257                                                 face = model->brushq3.data_thismodel->firstface + i;
5258                                                 if (face->collisions)
5259                                                         Collision_TraceLineTriangleMeshFloat(trace, boxstartmins, boxendmins, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5260                                         }
5261                                 }
5262                         }
5263                         else
5264                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model->brushq3.data_nodes, boxstartmins, boxendmins, 0, 1, boxstartmins, boxendmins, ++markframe, segmentmins, segmentmaxs);
5265                 }
5266         }
5267         else
5268         {
5269                 // box trace, performed as brush trace
5270                 thisbrush_start = Collision_BrushForBox(&startmatrix, boxstartmins, boxstartmaxs);
5271                 thisbrush_end = Collision_BrushForBox(&endmatrix, boxendmins, boxendmaxs);
5272                 if (model->brushq3.submodel)
5273                 {
5274                         for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
5275                                 if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
5276                                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, model->brushq3.data_thismodel->firstbrush[i].colbrushf, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
5277                         if (mod_q3bsp_curves_collisions.integer)
5278                         {
5279                                 for (i = 0;i < model->brushq3.data_thismodel->numfaces;i++)
5280                                 {
5281                                         face = model->brushq3.data_thismodel->firstface + i;
5282                                         if (face->collisions)
5283                                                 Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5284                                 }
5285                         }
5286                 }
5287                 else
5288                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model->brushq3.data_nodes, thisbrush_start, thisbrush_end, ++markframe, segmentmins, segmentmaxs);
5289         }
5290 }
5291
5292 static int Mod_Q3BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
5293 {
5294         int clusterindex, side, nodestackindex = 0;
5295         q3mnode_t *node, *nodestack[1024];
5296         node = model->brushq3.data_nodes;
5297         if (!loadmodel->brush.num_pvsclusters)
5298                 return true;
5299         for (;;)
5300         {
5301                 if (node->plane)
5302                 {
5303                         // node - recurse down the BSP tree
5304                         side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
5305                         if (side < 2)
5306                         {
5307                                 // box is on one side of plane, take that path
5308                                 node = node->children[side];
5309                         }
5310                         else
5311                         {
5312                                 // box crosses plane, take one path and remember the other
5313                                 nodestack[nodestackindex++] = node->children[0];
5314                                 node = node->children[1];
5315                         }
5316                 }
5317                 else
5318                 {
5319                         // leaf - check cluster bit
5320                         clusterindex = ((q3mleaf_t *)node)->clusterindex;
5321 #if 0
5322                         if (clusterindex >= loadmodel->brush.num_pvsclusters)
5323                         {
5324                                 Con_Printf("%i >= %i\n", clusterindex, loadmodel->brush.num_pvsclusters);
5325                                 return true;
5326                         }
5327 #endif
5328                         if (CHECKPVSBIT(pvs, clusterindex))
5329                         {
5330                                 // it is visible, return immediately with the news
5331                                 return true;
5332                         }
5333                         else
5334                         {
5335                                 // nothing to see here, try another path we didn't take earlier
5336                                 if (nodestackindex == 0)
5337                                         break;
5338                                 node = nodestack[--nodestackindex];
5339                         }
5340                 }
5341         }
5342         // it is not visible
5343         return false;
5344 }
5345
5346 //Returns PVS data for a given point
5347 //(note: can return NULL)
5348 static qbyte *Mod_Q3BSP_GetPVS(model_t *model, const vec3_t p)
5349 {
5350         q3mnode_t *node;
5351         Mod_CheckLoaded(model);
5352         node = model->brushq3.data_nodes;
5353         while (node->plane)
5354                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
5355         if (((q3mleaf_t *)node)->clusterindex >= 0)
5356                 return model->brush.data_pvsclusters + ((q3mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
5357         else
5358                 return NULL;
5359 }
5360
5361 static void Mod_Q3BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbytes, q3mnode_t *node)
5362 {
5363         while (node->plane)
5364         {
5365                 float d = PlaneDiff(org, node->plane);
5366                 if (d > radius)
5367                         node = node->children[0];
5368                 else if (d < -radius)
5369                         node = node->children[1];
5370                 else
5371                 {
5372                         // go down both sides
5373                         Mod_Q3BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
5374                         node = node->children[1];
5375                 }
5376         }
5377         // if this leaf is in a cluster, accumulate the pvs bits
5378         if (((q3mleaf_t *)node)->clusterindex >= 0)
5379         {
5380                 int i;
5381                 qbyte *pvs = model->brush.data_pvsclusters + ((q3mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
5382                 for (i = 0;i < pvsbytes;i++)
5383                         pvsbuffer[i] |= pvs[i];
5384         }
5385 }
5386
5387 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
5388 //of the given point.
5389 static int Mod_Q3BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbufferlength)
5390 {
5391         int bytes = model->brush.num_pvsclusterbytes;
5392         bytes = min(bytes, pvsbufferlength);
5393         if (r_novis.integer || !loadmodel->brush.num_pvsclusters || !Mod_Q3BSP_GetPVS(model, org))
5394         {
5395                 memset(pvsbuffer, 0xFF, bytes);
5396                 return bytes;
5397         }
5398         memset(pvsbuffer, 0, bytes);
5399         Mod_Q3BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brushq3.data_nodes);
5400         return bytes;
5401 }
5402
5403
5404 static int Mod_Q3BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents)
5405 {
5406         int supercontents = 0;
5407         if (nativecontents & Q2CONTENTS_SOLID)
5408                 supercontents |= SUPERCONTENTS_SOLID;
5409         if (nativecontents & Q2CONTENTS_WATER)
5410                 supercontents |= SUPERCONTENTS_WATER;
5411         if (nativecontents & Q2CONTENTS_SLIME)
5412                 supercontents |= SUPERCONTENTS_SLIME;
5413         if (nativecontents & Q2CONTENTS_LAVA)
5414                 supercontents |= SUPERCONTENTS_LAVA;
5415         return supercontents;
5416 }
5417
5418 static int Mod_Q3BSP_NativeContentsFromSuperContents(model_t *model, int supercontents)
5419 {
5420         int nativecontents = 0;
5421         if (supercontents & SUPERCONTENTS_SOLID)
5422                 nativecontents |= Q2CONTENTS_SOLID;
5423         if (supercontents & SUPERCONTENTS_WATER)
5424                 nativecontents |= Q2CONTENTS_WATER;
5425         if (supercontents & SUPERCONTENTS_SLIME)
5426                 nativecontents |= Q2CONTENTS_SLIME;
5427         if (supercontents & SUPERCONTENTS_LAVA)
5428                 nativecontents |= Q2CONTENTS_LAVA;
5429         return nativecontents;
5430 }
5431
5432 /*
5433 void Mod_Q3BSP_RecursiveGetVisible(q3mnode_t *node, model_t *model, const vec3_t point, const vec3_t mins, const vec3_t maxs, int maxleafs, q3mleaf_t *leaflist, int *numleafs, int maxsurfaces, q3msurface_t *surfacelist, int *numsurfaces, const qbyte *pvs)
5434 {
5435         mleaf_t *leaf;
5436         for (;;)
5437         {
5438                 if (!BoxesOverlap(node->mins, node->maxs, mins, maxs))
5439                         return;
5440                 if (!node->plane)
5441                         break;
5442                 Mod_Q3BSP_RecursiveGetVisible(node->children[0], model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces, pvs);
5443                 node = node->children[1];
5444         }
5445         leaf = (mleaf_t *)node;
5446         if ((pvs == NULL || CHECKPVSBIT(pvs, leaf->clusterindex)))
5447         {
5448                 int marksurfacenum;
5449                 q3mface_t *surf;
5450                 if (maxleafs && *numleafs < maxleafs)
5451                         leaflist[(*numleaf)++] = leaf;
5452                 if (maxsurfaces)
5453                 {
5454                         for (marksurfacenum = 0;marksurfacenum < leaf->nummarksurfaces;marksurfacenum++)
5455                         {
5456                                 face = leaf->firstleafface[marksurfacenum];
5457                                 if (face->shadowmark != shadowmarkcount)
5458                                 {
5459                                         face->shadowmark = shadowmarkcount;
5460                                         if (BoxesOverlap(mins, maxs, face->mins, face->maxs) && *numsurfaces < maxsurfaces)
5461                                                 surfacelist[(*numsurfaces)++] = face;
5462                                 }
5463                         }
5464                 }
5465         }
5466 }
5467
5468 void Mod_Q3BSP_GetVisible(model_t *model, const vec3_t point, const vec3_t mins, const vec3_t maxs, int maxleafs, q3mleaf_t *leaflist, int *numleafs, int maxsurfaces, q3msurface_t *surfacelist, int *numsurfaces)
5469 {
5470         // FIXME: support portals
5471         if (maxsurfaces)
5472                 *numsurfaces = 0;
5473         if (maxleafs)
5474                 *numleafs = 0;
5475         if (model->submodel)
5476         {
5477                 if (maxsurfaces)
5478                 {
5479                         for (marksurfacenum = 0;marksurfacenum < leaf->nummarksurfaces;marksurfacenum++)
5480                         {
5481                                 face = ent->model->brushq3.surfaces + leaf->firstmarksurface[marksurfacenum];
5482                                 if (BoxesOverlap(mins, maxs, face->mins, face->maxs) && *numsurfaces < maxsurfaces)
5483                                         surfacelist[(*numsurfaces)++] = face;
5484                         }
5485                 }
5486         }
5487         else
5488         {
5489                 pvs = ent->model->brush.GetPVS(ent->model, relativelightorigin);
5490                 Mod_Q3BSP_RecursiveGetVisible(ent->model->brushq3.data_nodes, model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces, pvs);
5491         }
5492 }
5493 */
5494
5495 extern void R_Q3BSP_DrawSky(struct entity_render_s *ent);
5496 extern void R_Q3BSP_Draw(struct entity_render_s *ent);
5497 extern void R_Q3BSP_DrawShadowVolume(struct entity_render_s *ent, vec3_t relativelightorigin, float lightradius);
5498 extern void R_Q3BSP_DrawLight(struct entity_render_s *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);
5499 void Mod_Q3BSP_Load(model_t *mod, void *buffer)
5500 {
5501         int i, j, numshadowmeshtriangles;
5502         q3dheader_t *header;
5503         float corner[3], yawradius, modelradius;
5504         q3mface_t *face;
5505
5506         mod->type = mod_brushq3;
5507         mod->numframes = 1;
5508         mod->numskins = 1;
5509
5510         header = (q3dheader_t *)buffer;
5511
5512         i = LittleLong(header->version);
5513         if (i != Q3BSPVERSION)
5514                 Host_Error("Mod_Q3BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q3BSPVERSION);
5515         if (loadmodel->isworldmodel)
5516         {
5517                 Cvar_SetValue("halflifebsp", false);
5518                 // until we get a texture for it...
5519                 R_ResetQuakeSky();
5520         }
5521
5522         mod->soundfromcenter = true;
5523         mod->TraceBox = Mod_Q3BSP_TraceBox;
5524         mod->brush.SuperContentsFromNativeContents = Mod_Q3BSP_SuperContentsFromNativeContents;
5525         mod->brush.NativeContentsFromSuperContents = Mod_Q3BSP_NativeContentsFromSuperContents;
5526         mod->brush.GetPVS = Mod_Q3BSP_GetPVS;
5527         mod->brush.FatPVS = Mod_Q3BSP_FatPVS;
5528         mod->brush.BoxTouchingPVS = Mod_Q3BSP_BoxTouchingPVS;
5529         mod->brush.LightPoint = Mod_Q3BSP_LightPoint;
5530         mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation;
5531         //mod->DrawSky = R_Q3BSP_DrawSky;
5532         mod->Draw = R_Q3BSP_Draw;
5533         mod->DrawShadowVolume = R_Q3BSP_DrawShadowVolume;
5534         mod->DrawLight = R_Q3BSP_DrawLight;
5535
5536         mod_base = (qbyte *)header;
5537
5538         // swap all the lumps
5539         for (i = 0;i < (int) sizeof(*header) / 4;i++)
5540                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
5541
5542         Mod_Q3BSP_LoadEntities(&header->lumps[Q3LUMP_ENTITIES]);
5543         Mod_Q3BSP_LoadTextures(&header->lumps[Q3LUMP_TEXTURES]);
5544         Mod_Q3BSP_LoadPlanes(&header->lumps[Q3LUMP_PLANES]);
5545         Mod_Q3BSP_LoadBrushSides(&header->lumps[Q3LUMP_BRUSHSIDES]);
5546         Mod_Q3BSP_LoadBrushes(&header->lumps[Q3LUMP_BRUSHES]);
5547         Mod_Q3BSP_LoadEffects(&header->lumps[Q3LUMP_EFFECTS]);
5548         Mod_Q3BSP_LoadVertices(&header->lumps[Q3LUMP_VERTICES]);
5549         Mod_Q3BSP_LoadTriangles(&header->lumps[Q3LUMP_TRIANGLES]);
5550         Mod_Q3BSP_LoadLightmaps(&header->lumps[Q3LUMP_LIGHTMAPS]);
5551         Mod_Q3BSP_LoadFaces(&header->lumps[Q3LUMP_FACES]);
5552         Mod_Q3BSP_LoadModels(&header->lumps[Q3LUMP_MODELS]);
5553         Mod_Q3BSP_LoadLeafBrushes(&header->lumps[Q3LUMP_LEAFBRUSHES]);
5554         Mod_Q3BSP_LoadLeafFaces(&header->lumps[Q3LUMP_LEAFFACES]);
5555         Mod_Q3BSP_LoadLeafs(&header->lumps[Q3LUMP_LEAFS]);
5556         Mod_Q3BSP_LoadNodes(&header->lumps[Q3LUMP_NODES]);
5557         Mod_Q3BSP_LoadLightGrid(&header->lumps[Q3LUMP_LIGHTGRID]);
5558         Mod_Q3BSP_LoadPVS(&header->lumps[Q3LUMP_PVS]);
5559         loadmodel->brush.numsubmodels = loadmodel->brushq3.num_models;
5560
5561         // make a single combined shadow mesh to allow optimized shadow volume creation
5562         numshadowmeshtriangles = 0;
5563         for (j = 0, face = loadmodel->brushq3.data_faces;j < loadmodel->brushq3.num_faces;j++, face++)
5564         {
5565                 face->num_firstshadowmeshtriangle = numshadowmeshtriangles;
5566                 numshadowmeshtriangles += face->num_triangles;
5567         }
5568         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Begin(loadmodel->mempool, numshadowmeshtriangles * 3, numshadowmeshtriangles, NULL, NULL, NULL, false, false, true);
5569         for (j = 0, face = loadmodel->brushq3.data_faces;j < loadmodel->brushq3.num_faces;j++, face++)
5570                 Mod_ShadowMesh_AddMesh(loadmodel->mempool, loadmodel->brush.shadowmesh, NULL, NULL, NULL, face->data_vertex3f, NULL, NULL, NULL, NULL, face->num_triangles, face->data_element3i);
5571         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Finish(loadmodel->mempool, loadmodel->brush.shadowmesh, false, true);
5572         Mod_BuildTriangleNeighbors(loadmodel->brush.shadowmesh->neighbor3i, loadmodel->brush.shadowmesh->element3i, loadmodel->brush.shadowmesh->numtriangles);
5573
5574         for (i = 0;i < loadmodel->brushq3.num_models;i++)
5575         {
5576                 if (i == 0)
5577                         mod = loadmodel;
5578                 else
5579                 {
5580                         char name[10];
5581                         // LordHavoc: only register submodels if it is the world
5582                         // (prevents bsp models from replacing world submodels)
5583                         if (!loadmodel->isworldmodel)
5584                                 continue;
5585                         // duplicate the basic information
5586                         sprintf(name, "*%i", i);
5587                         mod = Mod_FindName(name);
5588                         *mod = *loadmodel;
5589                         strcpy(mod->name, name);
5590                         // textures and memory belong to the main model
5591                         mod->texturepool = NULL;
5592                         mod->mempool = NULL;
5593                         mod->brush.GetPVS = NULL;
5594                         mod->brush.FatPVS = NULL;
5595                         mod->brush.BoxTouchingPVS = NULL;
5596                         mod->brush.LightPoint = NULL;
5597                         mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation;
5598                 }
5599                 mod->brushq3.data_thismodel = loadmodel->brushq3.data_models + i;
5600                 mod->brushq3.submodel = i;
5601
5602                 VectorCopy(mod->brushq3.data_thismodel->mins, mod->normalmins);
5603                 VectorCopy(mod->brushq3.data_thismodel->maxs, mod->normalmaxs);
5604                 corner[0] = max(fabs(mod->normalmins[0]), fabs(mod->normalmaxs[0]));
5605                 corner[1] = max(fabs(mod->normalmins[1]), fabs(mod->normalmaxs[1]));
5606                 corner[2] = max(fabs(mod->normalmins[2]), fabs(mod->normalmaxs[2]));
5607                 modelradius = sqrt(corner[0]*corner[0]+corner[1]*corner[1]+corner[2]*corner[2]);
5608                 yawradius = sqrt(corner[0]*corner[0]+corner[1]*corner[1]);
5609                 mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
5610                 mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
5611                 mod->yawmaxs[0] = mod->yawmaxs[1] = yawradius;
5612                 mod->yawmins[0] = mod->yawmins[1] = -yawradius;
5613                 mod->yawmins[2] = mod->normalmins[2];
5614                 mod->yawmaxs[2] = mod->normalmaxs[2];
5615                 mod->radius = modelradius;
5616                 mod->radius2 = modelradius * modelradius;
5617
5618                 for (j = 0;j < mod->brushq3.data_thismodel->numfaces;j++)
5619                         if (mod->brushq3.data_thismodel->firstface[j].texture->surfaceflags & Q3SURFACEFLAG_SKY)
5620                                 break;
5621                 if (j < mod->brushq3.data_thismodel->numfaces)
5622                         mod->DrawSky = R_Q3BSP_DrawSky;
5623         }
5624 }
5625
5626 void Mod_IBSP_Load(model_t *mod, void *buffer)
5627 {
5628         int i = LittleLong(((int *)buffer)[1]);
5629         if (i == Q3BSPVERSION)
5630                 Mod_Q3BSP_Load(mod,buffer);
5631         else if (i == Q2BSPVERSION)
5632                 Mod_Q2BSP_Load(mod,buffer);
5633         else
5634                 Host_Error("Mod_IBSP_Load: unknown/unsupported version %i\n", i);
5635 }
5636
5637 void Mod_MAP_Load(model_t *mod, void *buffer)
5638 {
5639         Host_Error("Mod_MAP_Load: not yet implemented\n");
5640 }
5641