model_brush.c

   1 /*
   2 Copyright (C) 1996-1997 Id Software, Inc.
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12
  13 See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 */
  20
  21 #include "quakedef.h"
  22 #include "image.h"
  23 #include "r_shadow.h"
  24 #include "polygon.h"
  25 #include "curves.h"
  26 #include "wad.h"
  27
  28
  29 // note: model_shared.c sets up r_notexture, and r_surf_notexture
  30
  31 qbyte mod_q1bsp_novis[(MAX_MAP_LEAFS + 7)/ 8];
  32
  33 //cvar_t r_subdivide_size = {CVAR_SAVE, "r_subdivide_size", "128"};
  34 cvar_t halflifebsp = {0, "halflifebsp", "0"};
  35 cvar_t r_novis = {0, "r_novis", "0"};
  36 cvar_t r_miplightmaps = {CVAR_SAVE, "r_miplightmaps", "0"};
  37 cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1"};
  38 cvar_t r_nosurftextures = {0, "r_nosurftextures", "0"};
  39 cvar_t r_subdivisions_tolerance = {0, "r_subdivisions_tolerance", "4"};
  40 cvar_t r_subdivisions_mintess = {0, "r_subdivisions_mintess", "1"};
  41 cvar_t r_subdivisions_maxtess = {0, "r_subdivisions_maxtess", "1024"};
  42 cvar_t r_subdivisions_maxvertices = {0, "r_subdivisions_maxvertices", "65536"};
  43 cvar_t r_subdivisions_collision_tolerance = {0, "r_subdivisions_collision_tolerance", "15"};
  44 cvar_t r_subdivisions_collision_mintess = {0, "r_subdivisions_collision_mintess", "1"};
  45 cvar_t r_subdivisions_collision_maxtess = {0, "r_subdivisions_collision_maxtess", "1024"};
  46 cvar_t r_subdivisions_collision_maxvertices = {0, "r_subdivisions_collision_maxvertices", "4225"};
  47 cvar_t mod_q3bsp_curves_collisions = {0, "mod_q3bsp_curves_collisions", "1"};
  48 cvar_t mod_q3bsp_optimizedtraceline = {0, "mod_q3bsp_optimizedtraceline", "1"};
  49 cvar_t mod_q3bsp_debugtracebrush = {0, "mod_q3bsp_debugtracebrush", "0"};
  50
  51 static void Mod_Q1BSP_Collision_Init (void);
  52 void Mod_BrushInit(void)
  53 {
  54 //      Cvar_RegisterVariable(&r_subdivide_size);
  55         Cvar_RegisterVariable(&halflifebsp);
  56         Cvar_RegisterVariable(&r_novis);
  57         Cvar_RegisterVariable(&r_miplightmaps);
  58         Cvar_RegisterVariable(&r_lightmaprgba);
  59         Cvar_RegisterVariable(&r_nosurftextures);
  60         Cvar_RegisterVariable(&r_subdivisions_tolerance);
  61         Cvar_RegisterVariable(&r_subdivisions_mintess);
  62         Cvar_RegisterVariable(&r_subdivisions_maxtess);
  63         Cvar_RegisterVariable(&r_subdivisions_maxvertices);
  64         Cvar_RegisterVariable(&r_subdivisions_collision_tolerance);
  65         Cvar_RegisterVariable(&r_subdivisions_collision_mintess);
  66         Cvar_RegisterVariable(&r_subdivisions_collision_maxtess);
  67         Cvar_RegisterVariable(&r_subdivisions_collision_maxvertices);
  68         Cvar_RegisterVariable(&mod_q3bsp_curves_collisions);
  69         Cvar_RegisterVariable(&mod_q3bsp_optimizedtraceline);
  70         Cvar_RegisterVariable(&mod_q3bsp_debugtracebrush);
  71         memset(mod_q1bsp_novis, 0xff, sizeof(mod_q1bsp_novis));
  72         Mod_Q1BSP_Collision_Init();
  73 }
  74
  75 static mleaf_t *Mod_Q1BSP_PointInLeaf(model_t *model, const vec3_t p)
  76 {
  77         mnode_t *node;
  78
  79         if (model == NULL)
  80                 return NULL;
  81
  82         Mod_CheckLoaded(model);
  83
  84         // LordHavoc: modified to start at first clip node,
  85         // in other words: first node of the (sub)model
  86         node = model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode;
  87         while (node->plane)
  88                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
  89
  90         return (mleaf_t *)node;
  91 }
  92
  93 static void Mod_Q1BSP_AmbientSoundLevelsForPoint(model_t *model, const vec3_t p, qbyte *out, int outsize)
  94 {
  95         int i;
  96         mleaf_t *leaf;
  97         leaf = Mod_Q1BSP_PointInLeaf(model, p);
  98         if (leaf)
  99         {
 100                 i = min(outsize, (int)sizeof(leaf->ambient_sound_level));
 101                 if (i)
 102                 {
 103                         memcpy(out, leaf->ambient_sound_level, i);
 104                         out += i;
 105                         outsize -= i;
 106                 }
 107         }
 108         if (outsize)
 109                 memset(out, 0, outsize);
 110 }
 111
 112 static int Mod_Q1BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
 113 {
 114         int clusterindex, side, nodestackindex = 0;
 115         mnode_t *node, *nodestack[1024];
 116         node = model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode;
 117         for (;;)
 118         {
 119                 if (node->plane)
 120                 {
 121                         // node - recurse down the BSP tree
 122                         side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
 123                         if (side < 2)
 124                         {
 125                                 // box is on one side of plane, take that path
 126                                 node = node->children[side];
 127                         }
 128                         else
 129                         {
 130                                 // box crosses plane, take one path and remember the other
 131                                 if (nodestackindex < 1024)
 132                                         nodestack[nodestackindex++] = node->children[0];
 133                                 node = node->children[1];
 134                         }
 135                 }
 136                 else
 137                 {
 138                         // leaf - check cluster bit
 139                         clusterindex = ((mleaf_t *)node)->clusterindex;
 140                         if (CHECKPVSBIT(pvs, clusterindex))
 141                         {
 142                                 // it is visible, return immediately with the news
 143                                 return true;
 144                         }
 145                         else
 146                         {
 147                                 // nothing to see here, try another path we didn't take earlier
 148                                 if (nodestackindex == 0)
 149                                         break;
 150                                 node = nodestack[--nodestackindex];
 151                         }
 152                 }
 153         }
 154         // it is not visible
 155         return false;
 156 }
 157
 158 typedef struct findnonsolidlocationinfo_s
 159 {
 160         vec3_t center;
 161         vec_t radius;
 162         vec3_t nudge;
 163         vec_t bestdist;
 164         model_t *model;
 165 }
 166 findnonsolidlocationinfo_t;
 167
 168 #if 0
 169 extern cvar_t samelevel;
 170 #endif
 171 static void Mod_Q1BSP_FindNonSolidLocation_r_Leaf(findnonsolidlocationinfo_t *info, mleaf_t *leaf)
 172 {
 173         int i, surfnum, k, *tri, *mark;
 174         float dist, f, vert[3][3], edge[3][3], facenormal[3], edgenormal[3][3], point[3];
 175 #if 0
 176         float surfnormal[3];
 177 #endif
 178         msurface_t *surf;
 179         for (surfnum = 0, mark = leaf->firstleafface;surfnum < leaf->numleaffaces;surfnum++, mark++)
 180         {
 181                 surf = info->model->brushq1.surfaces + *mark;
 182                 if (surf->flags & SURF_SOLIDCLIP)
 183                 {
 184 #if 0
 185                         VectorCopy(surf->plane->normal, surfnormal);
 186                         if (surf->flags & SURF_PLANEBACK)
 187                                 VectorNegate(surfnormal, surfnormal);
 188 #endif
 189                         for (k = 0;k < surf->mesh.num_triangles;k++)
 190                         {
 191                                 tri = surf->mesh.data_element3i + k * 3;
 192                                 VectorCopy((surf->mesh.data_vertex3f + tri[0] * 3), vert[0]);
 193                                 VectorCopy((surf->mesh.data_vertex3f + tri[1] * 3), vert[1]);
 194                                 VectorCopy((surf->mesh.data_vertex3f + tri[2] * 3), vert[2]);
 195                                 VectorSubtract(vert[1], vert[0], edge[0]);
 196                                 VectorSubtract(vert[2], vert[1], edge[1]);
 197                                 CrossProduct(edge[1], edge[0], facenormal);
 198                                 if (facenormal[0] || facenormal[1] || facenormal[2])
 199                                 {
 200                                         VectorNormalize(facenormal);
 201 #if 0
 202                                         if (VectorDistance(facenormal, surfnormal) > 0.01f)
 203                                                 Con_Printf("a2! %f %f %f != %f %f %f\n", facenormal[0], facenormal[1], facenormal[2], surfnormal[0], surfnormal[1], surfnormal[2]);
 204 #endif
 205                                         f = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
 206                                         if (f <= info->bestdist && f >= -info->bestdist)
 207                                         {
 208                                                 VectorSubtract(vert[0], vert[2], edge[2]);
 209                                                 VectorNormalize(edge[0]);
 210                                                 VectorNormalize(edge[1]);
 211                                                 VectorNormalize(edge[2]);
 212                                                 CrossProduct(facenormal, edge[0], edgenormal[0]);
 213                                                 CrossProduct(facenormal, edge[1], edgenormal[1]);
 214                                                 CrossProduct(facenormal, edge[2], edgenormal[2]);
 215 #if 0
 216                                                 if (samelevel.integer & 1)
 217                                                         VectorNegate(edgenormal[0], edgenormal[0]);
 218                                                 if (samelevel.integer & 2)
 219                                                         VectorNegate(edgenormal[1], edgenormal[1]);
 220                                                 if (samelevel.integer & 4)
 221                                                         VectorNegate(edgenormal[2], edgenormal[2]);
 222                                                 for (i = 0;i < 3;i++)
 223                                                         if (DotProduct(vert[0], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f
 224                                                          || DotProduct(vert[1], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f
 225                                                          || DotProduct(vert[2], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f)
 226                                                                 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]);
 227 #endif
 228                                                 // face distance
 229                                                 if (DotProduct(info->center, edgenormal[0]) < DotProduct(vert[0], edgenormal[0])
 230                                                  && DotProduct(info->center, edgenormal[1]) < DotProduct(vert[1], edgenormal[1])
 231                                                  && DotProduct(info->center, edgenormal[2]) < DotProduct(vert[2], edgenormal[2]))
 232                                                 {
 233                                                         // we got lucky, the center is within the face
 234                                                         dist = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
 235                                                         if (dist < 0)
 236                                                         {
 237                                                                 dist = -dist;
 238                                                                 if (info->bestdist > dist)
 239                                                                 {
 240                                                                         info->bestdist = dist;
 241                                                                         VectorScale(facenormal, (info->radius - -dist), info->nudge);
 242                                                                 }
 243                                                         }
 244                                                         else
 245                                                         {
 246                                                                 if (info->bestdist > dist)
 247                                                                 {
 248                                                                         info->bestdist = dist;
 249                                                                         VectorScale(facenormal, (info->radius - dist), info->nudge);
 250                                                                 }
 251                                                         }
 252                                                 }
 253                                                 else
 254                                                 {
 255                                                         // check which edge or vertex the center is nearest
 256                                                         for (i = 0;i < 3;i++)
 257                                                         {
 258                                                                 f = DotProduct(info->center, edge[i]);
 259                                                                 if (f >= DotProduct(vert[0], edge[i])
 260                                                                  && f <= DotProduct(vert[1], edge[i]))
 261                                                                 {
 262                                                                         // on edge
 263                                                                         VectorMA(info->center, -f, edge[i], point);
 264                                                                         dist = sqrt(DotProduct(point, point));
 265                                                                         if (info->bestdist > dist)
 266                                                                         {
 267                                                                                 info->bestdist = dist;
 268                                                                                 VectorScale(point, (info->radius / dist), info->nudge);
 269                                                                         }
 270                                                                         // skip both vertex checks
 271                                                                         // (both are further away than this edge)
 272                                                                         i++;
 273                                                                 }
 274                                                                 else
 275                                                                 {
 276                                                                         // not on edge, check first vertex of edge
 277                                                                         VectorSubtract(info->center, vert[i], point);
 278                                                                         dist = sqrt(DotProduct(point, point));
 279                                                                         if (info->bestdist > dist)
 280                                                                         {
 281                                                                                 info->bestdist = dist;
 282                                                                                 VectorScale(point, (info->radius / dist), info->nudge);
 283                                                                         }
 284                                                                 }
 285                                                         }
 286                                                 }
 287                                         }
 288                                 }
 289                         }
 290                 }
 291         }
 292 }
 293
 294 static void Mod_Q1BSP_FindNonSolidLocation_r(findnonsolidlocationinfo_t *info, mnode_t *node)
 295 {
 296         if (node->plane)
 297         {
 298                 float f = PlaneDiff(info->center, node->plane);
 299                 if (f >= -info->bestdist)
 300                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[0]);
 301                 if (f <= info->bestdist)
 302                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[1]);
 303         }
 304         else
 305         {
 306                 if (((mleaf_t *)node)->numleaffaces)
 307                         Mod_Q1BSP_FindNonSolidLocation_r_Leaf(info, (mleaf_t *)node);
 308         }
 309 }
 310
 311 static void Mod_Q1BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, float radius)
 312 {
 313         int i;
 314         findnonsolidlocationinfo_t info;
 315         if (model == NULL)
 316         {
 317                 VectorCopy(in, out);
 318                 return;
 319         }
 320         VectorCopy(in, info.center);
 321         info.radius = radius;
 322         info.model = model;
 323         i = 0;
 324         do
 325         {
 326                 VectorClear(info.nudge);
 327                 info.bestdist = radius;
 328                 Mod_Q1BSP_FindNonSolidLocation_r(&info, model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode);
 329                 VectorAdd(info.center, info.nudge, info.center);
 330         }
 331         while (info.bestdist < radius && ++i < 10);
 332         VectorCopy(info.center, out);
 333 }
 334
 335 int Mod_Q1BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents)
 336 {
 337         switch(nativecontents)
 338         {
 339                 case CONTENTS_EMPTY:
 340                         return 0;
 341                 case CONTENTS_SOLID:
 342                         return SUPERCONTENTS_SOLID;
 343                 case CONTENTS_WATER:
 344                         return SUPERCONTENTS_WATER;
 345                 case CONTENTS_SLIME:
 346                         return SUPERCONTENTS_SLIME;
 347                 case CONTENTS_LAVA:
 348                         return SUPERCONTENTS_LAVA;
 349                 case CONTENTS_SKY:
 350                         return SUPERCONTENTS_SKY;
 351         }
 352         return 0;
 353 }
 354
 355 int Mod_Q1BSP_NativeContentsFromSuperContents(model_t *model, int supercontents)
 356 {
 357         if (supercontents & SUPERCONTENTS_SOLID)
 358                 return CONTENTS_SOLID;
 359         if (supercontents & SUPERCONTENTS_SKY)
 360                 return CONTENTS_SKY;
 361         if (supercontents & SUPERCONTENTS_LAVA)
 362                 return CONTENTS_LAVA;
 363         if (supercontents & SUPERCONTENTS_SLIME)
 364                 return CONTENTS_SLIME;
 365         if (supercontents & SUPERCONTENTS_WATER)
 366                 return CONTENTS_WATER;
 367         return CONTENTS_EMPTY;
 368 }
 369
 370 typedef struct
 371 {
 372         // the hull we're tracing through
 373         const hull_t *hull;
 374
 375         // the trace structure to fill in
 376         trace_t *trace;
 377
 378         // start, end, and end - start (in model space)
 379         double start[3];
 380         double end[3];
 381         double dist[3];
 382 }
 383 RecursiveHullCheckTraceInfo_t;
 384
 385 // 1/32 epsilon to keep floating point happy
 386 #define DIST_EPSILON (0.03125)
 387
 388 #define HULLCHECKSTATE_EMPTY 0
 389 #define HULLCHECKSTATE_SOLID 1
 390 #define HULLCHECKSTATE_DONE 2
 391
 392 static int Mod_Q1BSP_RecursiveHullCheck(RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, double p1[3], double p2[3])
 393 {
 394         // status variables, these don't need to be saved on the stack when
 395         // recursing...  but are because this should be thread-safe
 396         // (note: tracing against a bbox is not thread-safe, yet)
 397         int ret;
 398         mplane_t *plane;
 399         double t1, t2;
 400
 401         // variables that need to be stored on the stack when recursing
 402         dclipnode_t *node;
 403         int side;
 404         double midf, mid[3];
 405
 406         // LordHavoc: a goto!  everyone flee in terror... :)
 407 loc0:
 408         // check for empty
 409         if (num < 0)
 410         {
 411                 num = Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num);
 412                 if (!t->trace->startfound)
 413                 {
 414                         t->trace->startfound = true;
 415                         t->trace->startsupercontents |= num;
 416                 }
 417                 if (num & SUPERCONTENTS_LIQUIDSMASK)
 418                         t->trace->inwater = true;
 419                 if (num == 0)
 420                         t->trace->inopen = true;
 421                 if (num & t->trace->hitsupercontentsmask)
 422                 {
 423                         // if the first leaf is solid, set startsolid
 424                         if (t->trace->allsolid)
 425                                 t->trace->startsolid = true;
 426 #if COLLISIONPARANOID >= 3
 427                         Con_Print("S");
 428 #endif
 429                         return HULLCHECKSTATE_SOLID;
 430                 }
 431                 else
 432                 {
 433                         t->trace->allsolid = false;
 434 #if COLLISIONPARANOID >= 3
 435                         Con_Print("E");
 436 #endif
 437                         return HULLCHECKSTATE_EMPTY;
 438                 }
 439         }
 440
 441         // find the point distances
 442         node = t->hull->clipnodes + num;
 443
 444         plane = t->hull->planes + node->planenum;
 445         if (plane->type < 3)
 446         {
 447                 t1 = p1[plane->type] - plane->dist;
 448                 t2 = p2[plane->type] - plane->dist;
 449         }
 450         else
 451         {
 452                 t1 = DotProduct (plane->normal, p1) - plane->dist;
 453                 t2 = DotProduct (plane->normal, p2) - plane->dist;
 454         }
 455
 456         if (t1 < 0)
 457         {
 458                 if (t2 < 0)
 459                 {
 460 #if COLLISIONPARANOID >= 3
 461                         Con_Print("<");
 462 #endif
 463                         num = node->children[1];
 464                         goto loc0;
 465                 }
 466                 side = 1;
 467         }
 468         else
 469         {
 470                 if (t2 >= 0)
 471                 {
 472 #if COLLISIONPARANOID >= 3
 473                         Con_Print(">");
 474 #endif
 475                         num = node->children[0];
 476                         goto loc0;
 477                 }
 478                 side = 0;
 479         }
 480
 481         // the line intersects, find intersection point
 482         // LordHavoc: this uses the original trace for maximum accuracy
 483 #if COLLISIONPARANOID >= 3
 484         Con_Print("M");
 485 #endif
 486         if (plane->type < 3)
 487         {
 488                 t1 = t->start[plane->type] - plane->dist;
 489                 t2 = t->end[plane->type] - plane->dist;
 490         }
 491         else
 492         {
 493                 t1 = DotProduct (plane->normal, t->start) - plane->dist;
 494                 t2 = DotProduct (plane->normal, t->end) - plane->dist;
 495         }
 496
 497         midf = t1 / (t1 - t2);
 498         midf = bound(p1f, midf, p2f);
 499         VectorMA(t->start, midf, t->dist, mid);
 500
 501         // recurse both sides, front side first
 502         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side], p1f, midf, p1, mid);
 503         // if this side is not empty, return what it is (solid or done)
 504         if (ret != HULLCHECKSTATE_EMPTY)
 505                 return ret;
 506
 507         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side ^ 1], midf, p2f, mid, p2);
 508         // if other side is not solid, return what it is (empty or done)
 509         if (ret != HULLCHECKSTATE_SOLID)
 510                 return ret;
 511
 512         // front is air and back is solid, this is the impact point...
 513         if (side)
 514         {
 515                 t->trace->plane.dist = -plane->dist;
 516                 VectorNegate (plane->normal, t->trace->plane.normal);
 517         }
 518         else
 519         {
 520                 t->trace->plane.dist = plane->dist;
 521                 VectorCopy (plane->normal, t->trace->plane.normal);
 522         }
 523
 524         // calculate the true fraction
 525         t1 = DotProduct(t->trace->plane.normal, t->start) - t->trace->plane.dist;
 526         t2 = DotProduct(t->trace->plane.normal, t->end) - t->trace->plane.dist;
 527         midf = t1 / (t1 - t2);
 528         t->trace->realfraction = bound(0, midf, 1);
 529
 530         // calculate the return fraction which is nudged off the surface a bit
 531         midf = (t1 - DIST_EPSILON) / (t1 - t2);
 532         t->trace->fraction = bound(0, midf, 1);
 533
 534 #if COLLISIONPARANOID >= 3
 535         Con_Print("D");
 536 #endif
 537         return HULLCHECKSTATE_DONE;
 538 }
 539
 540 #if COLLISIONPARANOID < 2
 541 static int Mod_Q1BSP_RecursiveHullCheckPoint(RecursiveHullCheckTraceInfo_t *t, int num)
 542 {
 543         while (num >= 0)
 544                 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];
 545         num = Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num);
 546         t->trace->startsupercontents |= num;
 547         if (num & SUPERCONTENTS_LIQUIDSMASK)
 548                 t->trace->inwater = true;
 549         if (num == 0)
 550                 t->trace->inopen = true;
 551         if (num & t->trace->hitsupercontentsmask)
 552         {
 553                 t->trace->allsolid = t->trace->startsolid = true;
 554                 return HULLCHECKSTATE_SOLID;
 555         }
 556         else
 557         {
 558                 t->trace->allsolid = t->trace->startsolid = false;
 559                 return HULLCHECKSTATE_EMPTY;
 560         }
 561 }
 562 #endif
 563
 564 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)
 565 {
 566         // this function currently only supports same size start and end
 567         double boxsize[3];
 568         RecursiveHullCheckTraceInfo_t rhc;
 569
 570         memset(&rhc, 0, sizeof(rhc));
 571         memset(trace, 0, sizeof(trace_t));
 572         rhc.trace = trace;
 573         rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
 574         rhc.trace->fraction = 1;
 575         rhc.trace->realfraction = 1;
 576         rhc.trace->allsolid = true;
 577         VectorSubtract(boxstartmaxs, boxstartmins, boxsize);
 578         if (boxsize[0] < 3)
 579                 rhc.hull = &model->brushq1.hulls[0]; // 0x0x0
 580         else if (model->brush.ishlbsp)
 581         {
 582                 // LordHavoc: this has to have a minor tolerance (the .1) because of
 583                 // minor float precision errors from the box being transformed around
 584                 if (boxsize[0] < 32.1)
 585                 {
 586                         if (boxsize[2] < 54) // pick the nearest of 36 or 72
 587                                 rhc.hull = &model->brushq1.hulls[3]; // 32x32x36
 588                         else
 589                                 rhc.hull = &model->brushq1.hulls[1]; // 32x32x72
 590                 }
 591                 else
 592                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x64
 593         }
 594         else
 595         {
 596                 // LordHavoc: this has to have a minor tolerance (the .1) because of
 597                 // minor float precision errors from the box being transformed around
 598                 if (boxsize[0] < 32.1)
 599                         rhc.hull = &model->brushq1.hulls[1]; // 32x32x56
 600                 else
 601                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x88
 602         }
 603         VectorSubtract(boxstartmins, rhc.hull->clip_mins, rhc.start);
 604         VectorSubtract(boxendmins, rhc.hull->clip_mins, rhc.end);
 605         VectorSubtract(rhc.end, rhc.start, rhc.dist);
 606 #if COLLISIONPARANOID >= 2
 607         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]);
 608         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
 609         Con_Print("\n");
 610 #else
 611         if (DotProduct(rhc.dist, rhc.dist))
 612                 Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
 613         else
 614                 Mod_Q1BSP_RecursiveHullCheckPoint(&rhc, rhc.hull->firstclipnode);
 615 #endif
 616 }
 617
 618 static hull_t box_hull;
 619 static dclipnode_t box_clipnodes[6];
 620 static mplane_t box_planes[6];
 621
 622 static void Mod_Q1BSP_Collision_Init (void)
 623 {
 624         int             i;
 625         int             side;
 626
 627         //Set up the planes and clipnodes so that the six floats of a bounding box
 628         //can just be stored out and get a proper hull_t structure.
 629
 630         box_hull.clipnodes = box_clipnodes;
 631         box_hull.planes = box_planes;
 632         box_hull.firstclipnode = 0;
 633         box_hull.lastclipnode = 5;
 634
 635         for (i = 0;i < 6;i++)
 636         {
 637                 box_clipnodes[i].planenum = i;
 638
 639                 side = i&1;
 640
 641                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
 642                 if (i != 5)
 643                         box_clipnodes[i].children[side^1] = i + 1;
 644                 else
 645                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
 646
 647                 box_planes[i].type = i>>1;
 648                 box_planes[i].normal[i>>1] = 1;
 649         }
 650 }
 651
 652 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)
 653 {
 654 #if 1
 655         colbrushf_t cbox;
 656         colplanef_t cbox_planes[6];
 657         cbox.supercontents = boxsupercontents;
 658         cbox.numplanes = 6;
 659         cbox.numpoints = 0;
 660         cbox.numtriangles = 0;
 661         cbox.planes = cbox_planes;
 662         cbox.points = NULL;
 663         cbox.elements = NULL;
 664         cbox.markframe = 0;
 665         cbox.mins[0] = 0;
 666         cbox.mins[1] = 0;
 667         cbox.mins[2] = 0;
 668         cbox.maxs[0] = 0;
 669         cbox.maxs[1] = 0;
 670         cbox.maxs[2] = 0;
 671         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];
 672         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];
 673         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];
 674         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];
 675         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];
 676         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];
 677         memset(trace, 0, sizeof(trace_t));
 678         trace->hitsupercontentsmask = hitsupercontentsmask;
 679         trace->fraction = 1;
 680         trace->realfraction = 1;
 681         Collision_TraceLineBrushFloat(trace, start, end, &cbox, &cbox);
 682 #else
 683         RecursiveHullCheckTraceInfo_t rhc;
 684         // fill in a default trace
 685         memset(&rhc, 0, sizeof(rhc));
 686         memset(trace, 0, sizeof(trace_t));
 687         //To keep everything totally uniform, bounding boxes are turned into small
 688         //BSP trees instead of being compared directly.
 689         // create a temp hull from bounding box sizes
 690         box_planes[0].dist = cmaxs[0] - mins[0];
 691         box_planes[1].dist = cmins[0] - maxs[0];
 692         box_planes[2].dist = cmaxs[1] - mins[1];
 693         box_planes[3].dist = cmins[1] - maxs[1];
 694         box_planes[4].dist = cmaxs[2] - mins[2];
 695         box_planes[5].dist = cmins[2] - maxs[2];
 696 #if COLLISIONPARANOID >= 3
 697         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]);
 698 #endif
 699         // trace a line through the generated clipping hull
 700         //rhc.boxsupercontents = boxsupercontents;
 701         rhc.hull = &box_hull;
 702         rhc.trace = trace;
 703         rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
 704         rhc.trace->fraction = 1;
 705         rhc.trace->realfraction = 1;
 706         rhc.trace->allsolid = true;
 707         VectorCopy(start, rhc.start);
 708         VectorCopy(end, rhc.end);
 709         VectorSubtract(rhc.end, rhc.start, rhc.dist);
 710         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
 711         //VectorMA(rhc.start, rhc.trace->fraction, rhc.dist, rhc.trace->endpos);
 712         if (rhc.trace->startsupercontents)
 713                 rhc.trace->startsupercontents = boxsupercontents;
 714 #endif
 715 }
 716
 717 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)
 718 {
 719         int side, distz = endz - startz;
 720         float front, back;
 721         float mid;
 722
 723 loc0:
 724         if (!node->plane)
 725                 return false;           // didn't hit anything
 726
 727         switch (node->plane->type)
 728         {
 729         case PLANE_X:
 730                 node = node->children[x < node->plane->dist];
 731                 goto loc0;
 732         case PLANE_Y:
 733                 node = node->children[y < node->plane->dist];
 734                 goto loc0;
 735         case PLANE_Z:
 736                 side = startz < node->plane->dist;
 737                 if ((endz < node->plane->dist) == side)
 738                 {
 739                         node = node->children[side];
 740                         goto loc0;
 741                 }
 742                 // found an intersection
 743                 mid = node->plane->dist;
 744                 break;
 745         default:
 746                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
 747                 front += startz * node->plane->normal[2];
 748                 back += endz * node->plane->normal[2];
 749                 side = front < node->plane->dist;
 750                 if ((back < node->plane->dist) == side)
 751                 {
 752                         node = node->children[side];
 753                         goto loc0;
 754                 }
 755                 // found an intersection
 756                 mid = startz + distz * (front - node->plane->dist) / (front - back);
 757                 break;
 758         }
 759
 760         // go down front side
 761         if (node->children[side]->plane && Mod_Q1BSP_LightPoint_RecursiveBSPNode(ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
 762                 return true;    // hit something
 763         else
 764         {
 765                 // check for impact on this node
 766                 if (node->numsurfaces)
 767                 {
 768                         int i, ds, dt;
 769                         msurface_t *surf;
 770
 771                         surf = r_refdef.worldmodel->brushq1.surfaces + node->firstsurface;
 772                         for (i = 0;i < node->numsurfaces;i++, surf++)
 773                         {
 774                                 if (!(surf->flags & SURF_LIGHTMAP) || !surf->samples)
 775                                         continue;       // no lightmaps
 776
 777                                 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];
 778                                 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];
 779
 780                                 if (ds >= 0 && ds < surf->extents[0] && dt >= 0 && dt < surf->extents[1])
 781                                 {
 782                                         qbyte *lightmap;
 783                                         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;
 784                                         lmwidth = ((surf->extents[0]>>4)+1);
 785                                         lmheight = ((surf->extents[1]>>4)+1);
 786                                         line3 = lmwidth * 3; // LordHavoc: *3 for colored lighting
 787                                         size3 = lmwidth * lmheight * 3; // LordHavoc: *3 for colored lighting
 788
 789                                         lightmap = surf->samples + ((dt>>4) * lmwidth + (ds>>4))*3; // LordHavoc: *3 for colored lighting
 790
 791                                         for (maps = 0;maps < MAXLIGHTMAPS && surf->styles[maps] != 255;maps++)
 792                                         {
 793                                                 scale = d_lightstylevalue[surf->styles[maps]];
 794                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
 795                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
 796                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
 797                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
 798                                                 lightmap += size3;
 799                                         }
 800
 801 /*
 802 LordHavoc: here's the readable version of the interpolation
 803 code, not quite as easy for the compiler to optimize...
 804
 805 dsfrac is the X position in the lightmap pixel, * 16
 806 dtfrac is the Y position in the lightmap pixel, * 16
 807 r00 is top left corner, r01 is top right corner
 808 r10 is bottom left corner, r11 is bottom right corner
 809 g and b are the same layout.
 810 r0 and r1 are the top and bottom intermediate results
 811
 812 first we interpolate the top two points, to get the top
 813 edge sample
 814
 815         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
 816         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
 817         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
 818
 819 then we interpolate the bottom two points, to get the
 820 bottom edge sample
 821
 822         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
 823         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
 824         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
 825
 826 then we interpolate the top and bottom samples to get the
 827 middle sample (the one which was requested)
 828
 829         r = (((r1-r0) * dtfrac) >> 4) + r0;
 830         g = (((g1-g0) * dtfrac) >> 4) + g0;
 831         b = (((b1-b0) * dtfrac) >> 4) + b0;
 832 */
 833
 834                                         ambientcolor[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
 835                                         ambientcolor[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
 836                                         ambientcolor[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
 837                                         return true; // success
 838                                 }
 839                         }
 840                 }
 841
 842                 // go down back side
 843                 node = node->children[side ^ 1];
 844                 startz = mid;
 845                 distz = endz - startz;
 846                 goto loc0;
 847         }
 848 }
 849
 850 void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
 851 {
 852         Mod_Q1BSP_LightPoint_RecursiveBSPNode(ambientcolor, diffusecolor, diffusenormal, model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode, p[0], p[1], p[2], p[2] - 65536);
 853 }
 854
 855 static void Mod_Q1BSP_DecompressVis(const qbyte *in, const qbyte *inend, qbyte *out, qbyte *outend)
 856 {
 857         int c;
 858         qbyte *outstart = out;
 859         while (out < outend)
 860         {
 861                 if (in == inend)
 862                 {
 863                         Con_Printf("Mod_Q1BSP_DecompressVis: input underrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
 864                         return;
 865                 }
 866                 c = *in++;
 867                 if (c)
 868                         *out++ = c;
 869                 else
 870                 {
 871                         if (in == inend)
 872                         {
 873                                 Con_Printf("Mod_Q1BSP_DecompressVis: input underrun (during zero-run) on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
 874                                 return;
 875                         }
 876                         for (c = *in++;c > 0;c--)
 877                         {
 878                                 if (out == outend)
 879                                 {
 880                                         Con_Printf("Mod_Q1BSP_DecompressVis: output overrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
 881                                         return;
 882                                 }
 883                                 *out++ = 0;
 884                         }
 885                 }
 886         }
 887 }
 888
 889 /*
 890 =============
 891 R_Q1BSP_LoadSplitSky
 892
 893 A sky texture is 256*128, with the right side being a masked overlay
 894 ==============
 895 */
 896 void R_Q1BSP_LoadSplitSky (qbyte *src, int width, int height, int bytesperpixel)
 897 {
 898         int i, j;
 899         unsigned solidpixels[128*128], alphapixels[128*128];
 900
 901         // if sky isn't the right size, just use it as a solid layer
 902         if (width != 256 || height != 128)
 903         {
 904                 loadmodel->brush.solidskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_solidtexture", width, height, src, bytesperpixel == 4 ? TEXTYPE_RGBA : TEXTYPE_PALETTE, TEXF_PRECACHE, bytesperpixel == 1 ? palette_complete : NULL);
 905                 loadmodel->brush.alphaskytexture = NULL;;
 906                 return;
 907         }
 908
 909         if (bytesperpixel == 4)
 910         {
 911                 for (i = 0;i < 128;i++)
 912                 {
 913                         for (j = 0;j < 128;j++)
 914                         {
 915                                 solidpixels[(i*128) + j] = ((unsigned *)src)[i*256+j+128];
 916                                 alphapixels[(i*128) + j] = ((unsigned *)src)[i*256+j];
 917                         }
 918                 }
 919         }
 920         else
 921         {
 922                 // make an average value for the back to avoid
 923                 // a fringe on the top level
 924                 int p, r, g, b;
 925                 union
 926                 {
 927                         unsigned int i;
 928                         unsigned char b[4];
 929                 }
 930                 rgba;
 931                 r = g = b = 0;
 932                 for (i = 0;i < 128;i++)
 933                 {
 934                         for (j = 0;j < 128;j++)
 935                         {
 936                                 rgba.i = palette_complete[src[i*256 + j + 128]];
 937                                 r += rgba.b[0];
 938                                 g += rgba.b[1];
 939                                 b += rgba.b[2];
 940                         }
 941                 }
 942                 rgba.b[0] = r/(128*128);
 943                 rgba.b[1] = g/(128*128);
 944                 rgba.b[2] = b/(128*128);
 945                 rgba.b[3] = 0;
 946                 for (i = 0;i < 128;i++)
 947                 {
 948                         for (j = 0;j < 128;j++)
 949                         {
 950                                 solidpixels[(i*128) + j] = palette_complete[src[i*256 + j + 128]];
 951                                 alphapixels[(i*128) + j] = (p = src[i*256 + j]) ? palette_complete[p] : rgba.i;
 952                         }
 953                 }
 954         }
 955
 956         loadmodel->brush.solidskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_solidtexture", 128, 128, (qbyte *) solidpixels, TEXTYPE_RGBA, TEXF_PRECACHE, NULL);
 957         loadmodel->brush.alphaskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_alphatexture", 128, 128, (qbyte *) alphapixels, TEXTYPE_RGBA, TEXF_ALPHA | TEXF_PRECACHE, NULL);
 958 }
 959
 960 static void Mod_Q1BSP_LoadTextures(lump_t *l)
 961 {
 962         int i, j, k, num, max, altmax, mtwidth, mtheight, *dofs, incomplete;
 963         miptex_t *dmiptex;
 964         texture_t *tx, *tx2, *anims[10], *altanims[10];
 965         dmiptexlump_t *m;
 966         qbyte *data, *mtdata;
 967         char name[256];
 968
 969         loadmodel->brush.data_textures = NULL;
 970
 971         // add two slots for notexture walls and notexture liquids
 972         if (l->filelen)
 973         {
 974                 m = (dmiptexlump_t *)(mod_base + l->fileofs);
 975                 m->nummiptex = LittleLong (m->nummiptex);
 976                 loadmodel->brush.num_textures = m->nummiptex + 2;
 977         }
 978         else
 979         {
 980                 m = NULL;
 981                 loadmodel->brush.num_textures = 2;
 982         }
 983
 984         loadmodel->brush.data_textures = Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_textures * sizeof(texture_t));
 985
 986         // fill out all slots with notexture
 987         for (i = 0, tx = loadmodel->brush.data_textures;i < loadmodel->brush.num_textures;i++, tx++)
 988         {
 989                 strcpy(tx->name, "NO TEXTURE FOUND");
 990                 tx->width = 16;
 991                 tx->height = 16;
 992                 tx->skin.base = r_notexture;
 993                 if (i == loadmodel->brush.num_textures - 1)
 994                         tx->flags = SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
 995                 else
 996                         tx->flags = SURF_LIGHTMAP | SURF_SOLIDCLIP;
 997                 tx->currentframe = tx;
 998         }
 999
1000         if (!m)
1001                 return;
1002
1003         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
1004         dofs = m->dataofs;
1005         // LordHavoc: mostly rewritten map texture loader
1006         for (i = 0;i < m->nummiptex;i++)
1007         {
1008                 dofs[i] = LittleLong(dofs[i]);
1009                 if (dofs[i] == -1 || r_nosurftextures.integer)
1010                         continue;
1011                 dmiptex = (miptex_t *)((qbyte *)m + dofs[i]);
1012
1013                 // make sure name is no more than 15 characters
1014                 for (j = 0;dmiptex->name[j] && j < 15;j++)
1015                         name[j] = dmiptex->name[j];
1016                 name[j] = 0;
1017
1018                 mtwidth = LittleLong(dmiptex->width);
1019                 mtheight = LittleLong(dmiptex->height);
1020                 mtdata = NULL;
1021                 j = LittleLong(dmiptex->offsets[0]);
1022                 if (j)
1023                 {
1024                         // texture included
1025                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
1026                         {
1027                                 Con_Printf("Texture \"%s\" in \"%s\"is corrupt or incomplete\n", dmiptex->name, loadmodel->name);
1028                                 continue;
1029                         }
1030                         mtdata = (qbyte *)dmiptex + j;
1031                 }
1032
1033                 if ((mtwidth & 15) || (mtheight & 15))
1034                         Con_Printf("warning: texture \"%s\" in \"%s\" is not 16 aligned\n", dmiptex->name, loadmodel->name);
1035
1036                 // LordHavoc: force all names to lowercase
1037                 for (j = 0;name[j];j++)
1038                         if (name[j] >= 'A' && name[j] <= 'Z')
1039                                 name[j] += 'a' - 'A';
1040
1041                 tx = loadmodel->brush.data_textures + i;
1042                 strcpy(tx->name, name);
1043                 tx->width = mtwidth;
1044                 tx->height = mtheight;
1045
1046                 if (!tx->name[0])
1047                 {
1048                         sprintf(tx->name, "unnamed%i", i);
1049                         Con_Printf("warning: unnamed texture in %s, renaming to %s\n", loadmodel->name, tx->name);
1050                 }
1051
1052                 // LordHavoc: HL sky textures are entirely different than quake
1053                 if (!loadmodel->brush.ishlbsp && !strncmp(tx->name, "sky", 3) && mtwidth == 256 && mtheight == 128)
1054                 {
1055                         if (loadmodel->isworldmodel)
1056                         {
1057                                 data = loadimagepixels(tx->name, false, 0, 0);
1058                                 if (data)
1059                                 {
1060                                         R_Q1BSP_LoadSplitSky(data, image_width, image_height, 4);
1061                                         Mem_Free(data);
1062                                 }
1063                                 else if (mtdata != NULL)
1064                                         R_Q1BSP_LoadSplitSky(mtdata, mtwidth, mtheight, 1);
1065                         }
1066                 }
1067                 else
1068                 {
1069                         if (!Mod_LoadSkinFrame(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, false, true, true))
1070                         {
1071                                 // did not find external texture, load it from the bsp or wad3
1072                                 if (loadmodel->brush.ishlbsp)
1073                                 {
1074                                         // internal texture overrides wad
1075                                         qbyte *pixels, *freepixels, *fogpixels;
1076                                         pixels = freepixels = NULL;
1077                                         if (mtdata)
1078                                                 pixels = W_ConvertWAD3Texture(dmiptex);
1079                                         if (pixels == NULL)
1080                                                 pixels = freepixels = W_GetTexture(tx->name);
1081                                         if (pixels != NULL)
1082                                         {
1083                                                 tx->width = image_width;
1084                                                 tx->height = image_height;
1085                                                 tx->skin.base = tx->skin.merged = R_LoadTexture2D(loadmodel->texturepool, tx->name, image_width, image_height, pixels, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, NULL);
1086                                                 if (Image_CheckAlpha(pixels, image_width * image_height, true))
1087                                                 {
1088                                                         fogpixels = Mem_Alloc(tempmempool, image_width * image_height * 4);
1089                                                         for (j = 0;j < image_width * image_height * 4;j += 4)
1090                                                         {
1091                                                                 fogpixels[j + 0] = 255;
1092                                                                 fogpixels[j + 1] = 255;
1093                                                                 fogpixels[j + 2] = 255;
1094                                                                 fogpixels[j + 3] = pixels[j + 3];
1095                                                         }
1096                                                         tx->skin.fog = R_LoadTexture2D(loadmodel->texturepool, tx->name, image_width, image_height, pixels, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, NULL);
1097                                                         Mem_Free(fogpixels);
1098                                                 }
1099                                         }
1100                                         if (freepixels)
1101                                                 Mem_Free(freepixels);
1102                                 }
1103                                 else if (mtdata) // texture included
1104                                         Mod_LoadSkinFrame_Internal(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_PRECACHE | TEXF_PICMIP, false, true, tx->name[0] != '*' && r_fullbrights.integer, mtdata, tx->width, tx->height);
1105                         }
1106                 }
1107                 if (tx->skin.base == NULL)
1108                 {
1109                         // no texture found
1110                         tx->width = 16;
1111                         tx->height = 16;
1112                         tx->skin.base = r_notexture;
1113                 }
1114
1115                 if (tx->name[0] == '*')
1116                 {
1117                         // turb does not block movement
1118                         tx->flags = SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
1119                         // LordHavoc: some turbulent textures should be fullbright and solid
1120                         if (!strncmp(tx->name,"*lava",5)
1121                          || !strncmp(tx->name,"*teleport",9)
1122                          || !strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
1123                                 tx->flags |= SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA;
1124                         else
1125                                 tx->flags |= SURF_WATERALPHA;
1126                 }
1127                 else if (tx->name[0] == 's' && tx->name[1] == 'k' && tx->name[2] == 'y')
1128                         tx->flags = SURF_DRAWSKY | SURF_SOLIDCLIP;
1129                 else
1130                         tx->flags = SURF_LIGHTMAP | SURF_SOLIDCLIP;
1131
1132                 // start out with no animation
1133                 tx->currentframe = tx;
1134         }
1135
1136         // sequence the animations
1137         for (i = 0;i < m->nummiptex;i++)
1138         {
1139                 tx = loadmodel->brush.data_textures + i;
1140                 if (!tx || tx->name[0] != '+' || tx->name[1] == 0 || tx->name[2] == 0)
1141                         continue;
1142                 if (tx->anim_total[0] || tx->anim_total[1])
1143                         continue;       // already sequenced
1144
1145                 // find the number of frames in the animation
1146                 memset(anims, 0, sizeof(anims));
1147                 memset(altanims, 0, sizeof(altanims));
1148
1149                 for (j = i;j < m->nummiptex;j++)
1150                 {
1151                         tx2 = loadmodel->brush.data_textures + j;
1152                         if (!tx2 || tx2->name[0] != '+' || strcmp(tx2->name+2, tx->name+2))
1153                                 continue;
1154
1155                         num = tx2->name[1];
1156                         if (num >= '0' && num <= '9')
1157                                 anims[num - '0'] = tx2;
1158                         else if (num >= 'a' && num <= 'j')
1159                                 altanims[num - 'a'] = tx2;
1160                         else
1161                                 Con_Printf("Bad animating texture %s\n", tx->name);
1162                 }
1163
1164                 max = altmax = 0;
1165                 for (j = 0;j < 10;j++)
1166                 {
1167                         if (anims[j])
1168                                 max = j + 1;
1169                         if (altanims[j])
1170                                 altmax = j + 1;
1171                 }
1172                 //Con_Printf("linking animation %s (%i:%i frames)\n\n", tx->name, max, altmax);
1173
1174                 incomplete = false;
1175                 for (j = 0;j < max;j++)
1176                 {
1177                         if (!anims[j])
1178                         {
1179                                 Con_Printf("Missing frame %i of %s\n", j, tx->name);
1180                                 incomplete = true;
1181                         }
1182                 }
1183                 for (j = 0;j < altmax;j++)
1184                 {
1185                         if (!altanims[j])
1186                         {
1187                                 Con_Printf("Missing altframe %i of %s\n", j, tx->name);
1188                                 incomplete = true;
1189                         }
1190                 }
1191                 if (incomplete)
1192                         continue;
1193
1194                 if (altmax < 1)
1195                 {
1196                         // if there is no alternate animation, duplicate the primary
1197                         // animation into the alternate
1198                         altmax = max;
1199                         for (k = 0;k < 10;k++)
1200                                 altanims[k] = anims[k];
1201                 }
1202
1203                 // link together the primary animation
1204                 for (j = 0;j < max;j++)
1205                 {
1206                         tx2 = anims[j];
1207                         tx2->animated = true;
1208                         tx2->anim_total[0] = max;
1209                         tx2->anim_total[1] = altmax;
1210                         for (k = 0;k < 10;k++)
1211                         {
1212                                 tx2->anim_frames[0][k] = anims[k];
1213                                 tx2->anim_frames[1][k] = altanims[k];
1214                         }
1215                 }
1216
1217                 // if there really is an alternate anim...
1218                 if (anims[0] != altanims[0])
1219                 {
1220                         // link together the alternate animation
1221                         for (j = 0;j < altmax;j++)
1222                         {
1223                                 tx2 = altanims[j];
1224                                 tx2->animated = true;
1225                                 // the primary/alternate are reversed here
1226                                 tx2->anim_total[0] = altmax;
1227                                 tx2->anim_total[1] = max;
1228                                 for (k = 0;k < 10;k++)
1229                                 {
1230                                         tx2->anim_frames[0][k] = altanims[k];
1231                                         tx2->anim_frames[1][k] = anims[k];
1232                                 }
1233                         }
1234                 }
1235         }
1236 }
1237
1238 static void Mod_Q1BSP_LoadLighting(lump_t *l)
1239 {
1240         int i;
1241         qbyte *in, *out, *data, d;
1242         char litfilename[1024];
1243         loadmodel->brushq1.lightdata = NULL;
1244         if (loadmodel->brush.ishlbsp) // LordHavoc: load the colored lighting data straight
1245         {
1246                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen);
1247                 for (i=0; i<l->filelen; i++)
1248                         loadmodel->brushq1.lightdata[i] = mod_base[l->fileofs+i] >>= 1;
1249         }
1250         else // LordHavoc: bsp version 29 (normal white lighting)
1251         {
1252                 // LordHavoc: hope is not lost yet, check for a .lit file to load
1253                 strlcpy (litfilename, loadmodel->name, sizeof (litfilename));
1254                 FS_StripExtension (litfilename, litfilename, sizeof (litfilename));
1255                 strlcat (litfilename, ".lit", sizeof (litfilename));
1256                 data = (qbyte*) FS_LoadFile(litfilename, tempmempool, false);
1257                 if (data)
1258                 {
1259                         if (fs_filesize > 8 && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1260                         {
1261                                 i = LittleLong(((int *)data)[1]);
1262                                 if (i == 1)
1263                                 {
1264                                         Con_DPrintf("loaded %s\n", litfilename);
1265                                         loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, fs_filesize - 8);
1266                                         memcpy(loadmodel->brushq1.lightdata, data + 8, fs_filesize - 8);
1267                                         Mem_Free(data);
1268                                         return;
1269                                 }
1270                                 else
1271                                 {
1272                                         Con_Printf("Unknown .lit file version (%d)\n", i);
1273                                         Mem_Free(data);
1274                                 }
1275                         }
1276                         else
1277                         {
1278                                 if (fs_filesize == 8)
1279                                         Con_Print("Empty .lit file, ignoring\n");
1280                                 else
1281                                         Con_Print("Corrupt .lit file (old version?), ignoring\n");
1282                                 Mem_Free(data);
1283                         }
1284                 }
1285                 // LordHavoc: oh well, expand the white lighting data
1286                 if (!l->filelen)
1287                         return;
1288                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen*3);
1289                 in = loadmodel->brushq1.lightdata + l->filelen*2; // place the file at the end, so it will not be overwritten until the very last write
1290                 out = loadmodel->brushq1.lightdata;
1291                 memcpy(in, mod_base + l->fileofs, l->filelen);
1292                 for (i = 0;i < l->filelen;i++)
1293                 {
1294                         d = *in++;
1295                         *out++ = d;
1296                         *out++ = d;
1297                         *out++ = d;
1298                 }
1299         }
1300 }
1301
1302 static void Mod_Q1BSP_LoadLightList(void)
1303 {
1304         int a, n, numlights;
1305         char tempchar, *s, *t, *lightsstring, lightsfilename[1024];
1306         mlight_t *e;
1307
1308         strlcpy (lightsfilename, loadmodel->name, sizeof (lightsfilename));
1309         FS_StripExtension (lightsfilename, lightsfilename, sizeof(lightsfilename));
1310         strlcat (lightsfilename, ".lights", sizeof (lightsfilename));
1311         s = lightsstring = (char *) FS_LoadFile(lightsfilename, tempmempool, false);
1312         if (s)
1313         {
1314                 numlights = 0;
1315                 while (*s)
1316                 {
1317                         while (*s && *s != '\n' && *s != '\r')
1318                                 s++;
1319                         if (!*s)
1320                         {
1321                                 Mem_Free(lightsstring);
1322                                 Con_Printf("lights file must end with a newline\n");
1323                                 return;
1324                         }
1325                         s++;
1326                         numlights++;
1327                 }
1328                 loadmodel->brushq1.lights = Mem_Alloc(loadmodel->mempool, numlights * sizeof(mlight_t));
1329                 s = lightsstring;
1330                 n = 0;
1331                 while (*s && n < numlights)
1332                 {
1333                         t = s;
1334                         while (*s && *s != '\n' && *s != '\r')
1335                                 s++;
1336                         if (!*s)
1337                         {
1338                                 Con_Printf("misparsed lights file!\n");
1339                                 break;
1340                         }
1341                         e = loadmodel->brushq1.lights + n;
1342                         tempchar = *s;
1343                         *s = 0;
1344                         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);
1345                         *s = tempchar;
1346                         if (a != 14)
1347                         {
1348                                 Con_Printf("invalid lights file, found %d parameters on line %i, should be 14 parameters (origin[0] origin[1] origin[2] falloff light[0] light[1] light[2] subtract spotdir[0] spotdir[1] spotdir[2] spotcone distancebias style)\n", a, n + 1);
1349                                 break;
1350                         }
1351                         if (*s == '\r')
1352                                 s++;
1353                         if (*s == '\n')
1354                                 s++;
1355                         n++;
1356                 }
1357                 if (*s)
1358                         Con_Printf("misparsed lights file!\n");
1359                 loadmodel->brushq1.numlights = numlights;
1360                 Mem_Free(lightsstring);
1361         }
1362 }
1363
1364 static void Mod_Q1BSP_LoadVisibility(lump_t *l)
1365 {
1366         loadmodel->brushq1.num_compressedpvs = 0;
1367         loadmodel->brushq1.data_compressedpvs = NULL;
1368         if (!l->filelen)
1369                 return;
1370         loadmodel->brushq1.num_compressedpvs = l->filelen;
1371         loadmodel->brushq1.data_compressedpvs = Mem_Alloc(loadmodel->mempool, l->filelen);
1372         memcpy(loadmodel->brushq1.data_compressedpvs, mod_base + l->fileofs, l->filelen);
1373 }
1374
1375 // used only for HalfLife maps
1376 static void Mod_Q1BSP_ParseWadsFromEntityLump(const char *data)
1377 {
1378         char key[128], value[4096];
1379         char wadname[128];
1380         int i, j, k;
1381         if (!data)
1382                 return;
1383         if (!COM_ParseToken(&data, false))
1384                 return; // error
1385         if (com_token[0] != '{')
1386                 return; // error
1387         while (1)
1388         {
1389                 if (!COM_ParseToken(&data, false))
1390                         return; // error
1391                 if (com_token[0] == '}')
1392                         break; // end of worldspawn
1393                 if (com_token[0] == '_')
1394                         strcpy(key, com_token + 1);
1395                 else
1396                         strcpy(key, com_token);
1397                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
1398                         key[strlen(key)-1] = 0;
1399                 if (!COM_ParseToken(&data, false))
1400                         return; // error
1401                 strcpy(value, com_token);
1402                 if (!strcmp("wad", key)) // for HalfLife maps
1403                 {
1404                         if (loadmodel->brush.ishlbsp)
1405                         {
1406                                 j = 0;
1407                                 for (i = 0;i < 4096;i++)
1408                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
1409                                                 break;
1410                                 if (value[i])
1411                                 {
1412                                         for (;i < 4096;i++)
1413                                         {
1414                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
1415                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
1416                                                         j = i+1;
1417                                                 else if (value[i] == ';' || value[i] == 0)
1418                                                 {
1419                                                         k = value[i];
1420                                                         value[i] = 0;
1421                                                         strcpy(wadname, "textures/");
1422                                                         strcat(wadname, &value[j]);
1423                                                         W_LoadTextureWadFile(wadname, false);
1424                                                         j = i+1;
1425                                                         if (!k)
1426                                                                 break;
1427                                                 }
1428                                         }
1429                                 }
1430                         }
1431                 }
1432         }
1433 }
1434
1435 static void Mod_Q1BSP_LoadEntities(lump_t *l)
1436 {
1437         loadmodel->brush.entities = NULL;
1438         if (!l->filelen)
1439                 return;
1440         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
1441         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
1442         if (loadmodel->brush.ishlbsp)
1443                 Mod_Q1BSP_ParseWadsFromEntityLump(loadmodel->brush.entities);
1444 }
1445
1446
1447 static void Mod_Q1BSP_LoadVertexes(lump_t *l)
1448 {
1449         dvertex_t       *in;
1450         mvertex_t       *out;
1451         int                     i, count;
1452
1453         in = (void *)(mod_base + l->fileofs);
1454         if (l->filelen % sizeof(*in))
1455                 Host_Error("Mod_Q1BSP_LoadVertexes: funny lump size in %s",loadmodel->name);
1456         count = l->filelen / sizeof(*in);
1457         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1458
1459         loadmodel->brushq1.vertexes = out;
1460         loadmodel->brushq1.numvertexes = count;
1461
1462         for ( i=0 ; i<count ; i++, in++, out++)
1463         {
1464                 out->position[0] = LittleFloat(in->point[0]);
1465                 out->position[1] = LittleFloat(in->point[1]);
1466                 out->position[2] = LittleFloat(in->point[2]);
1467         }
1468 }
1469
1470 static void Mod_Q1BSP_LoadSubmodels(lump_t *l)
1471 {
1472         dmodel_t        *in;
1473         dmodel_t        *out;
1474         int                     i, j, count;
1475
1476         in = (void *)(mod_base + l->fileofs);
1477         if (l->filelen % sizeof(*in))
1478                 Host_Error("Mod_Q1BSP_LoadSubmodels: funny lump size in %s",loadmodel->name);
1479         count = l->filelen / sizeof(*in);
1480         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1481
1482         loadmodel->brushq1.submodels = out;
1483         loadmodel->brush.numsubmodels = count;
1484
1485         for ( i=0 ; i<count ; i++, in++, out++)
1486         {
1487                 for (j=0 ; j<3 ; j++)
1488                 {
1489                         // spread the mins / maxs by a pixel
1490                         out->mins[j] = LittleFloat(in->mins[j]) - 1;
1491                         out->maxs[j] = LittleFloat(in->maxs[j]) + 1;
1492                         out->origin[j] = LittleFloat(in->origin[j]);
1493                 }
1494                 for (j=0 ; j<MAX_MAP_HULLS ; j++)
1495                         out->headnode[j] = LittleLong(in->headnode[j]);
1496                 out->visleafs = LittleLong(in->visleafs);
1497                 out->firstface = LittleLong(in->firstface);
1498                 out->numfaces = LittleLong(in->numfaces);
1499         }
1500 }
1501
1502 static void Mod_Q1BSP_LoadEdges(lump_t *l)
1503 {
1504         dedge_t *in;
1505         medge_t *out;
1506         int     i, count;
1507
1508         in = (void *)(mod_base + l->fileofs);
1509         if (l->filelen % sizeof(*in))
1510                 Host_Error("Mod_Q1BSP_LoadEdges: funny lump size in %s",loadmodel->name);
1511         count = l->filelen / sizeof(*in);
1512         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1513
1514         loadmodel->brushq1.edges = out;
1515         loadmodel->brushq1.numedges = count;
1516
1517         for ( i=0 ; i<count ; i++, in++, out++)
1518         {
1519                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
1520                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
1521         }
1522 }
1523
1524 static void Mod_Q1BSP_LoadTexinfo(lump_t *l)
1525 {
1526         texinfo_t *in;
1527         mtexinfo_t *out;
1528         int i, j, k, count, miptex;
1529
1530         in = (void *)(mod_base + l->fileofs);
1531         if (l->filelen % sizeof(*in))
1532                 Host_Error("Mod_Q1BSP_LoadTexinfo: funny lump size in %s",loadmodel->name);
1533         count = l->filelen / sizeof(*in);
1534         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1535
1536         loadmodel->brushq1.texinfo = out;
1537         loadmodel->brushq1.numtexinfo = count;
1538
1539         for (i = 0;i < count;i++, in++, out++)
1540         {
1541                 for (k = 0;k < 2;k++)
1542                         for (j = 0;j < 4;j++)
1543                                 out->vecs[k][j] = LittleFloat(in->vecs[k][j]);
1544
1545                 miptex = LittleLong(in->miptex);
1546                 out->flags = LittleLong(in->flags);
1547
1548                 out->texture = NULL;
1549                 if (loadmodel->brush.data_textures)
1550                 {
1551                         if ((unsigned int) miptex >= (unsigned int) loadmodel->brush.num_textures)
1552                                 Con_Printf("error in model \"%s\": invalid miptex index %i(of %i)\n", loadmodel->name, miptex, loadmodel->brush.num_textures);
1553                         else
1554                                 out->texture = loadmodel->brush.data_textures + miptex;
1555                 }
1556                 if (out->flags & TEX_SPECIAL)
1557                 {
1558                         // if texture chosen is NULL or the shader needs a lightmap,
1559                         // force to notexture water shader
1560                         if (out->texture == NULL || out->texture->flags & SURF_LIGHTMAP)
1561                                 out->texture = loadmodel->brush.data_textures + (loadmodel->brush.num_textures - 1);
1562                 }
1563                 else
1564                 {
1565                         // if texture chosen is NULL, force to notexture
1566                         if (out->texture == NULL)
1567                                 out->texture = loadmodel->brush.data_textures + (loadmodel->brush.num_textures - 2);
1568                 }
1569         }
1570 }
1571
1572 #if 0
1573 void BoundPoly(int numverts, float *verts, vec3_t mins, vec3_t maxs)
1574 {
1575         int             i, j;
1576         float   *v;
1577
1578         mins[0] = mins[1] = mins[2] = 9999;
1579         maxs[0] = maxs[1] = maxs[2] = -9999;
1580         v = verts;
1581         for (i = 0;i < numverts;i++)
1582         {
1583                 for (j = 0;j < 3;j++, v++)
1584                 {
1585                         if (*v < mins[j])
1586                                 mins[j] = *v;
1587                         if (*v > maxs[j])
1588                                 maxs[j] = *v;
1589                 }
1590         }
1591 }
1592
1593 #define MAX_SUBDIVPOLYTRIANGLES 4096
1594 #define MAX_SUBDIVPOLYVERTS(MAX_SUBDIVPOLYTRIANGLES * 3)
1595
1596 static int subdivpolyverts, subdivpolytriangles;
1597 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
1598 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
1599
1600 static int subdivpolylookupvert(vec3_t v)
1601 {
1602         int i;
1603         for (i = 0;i < subdivpolyverts;i++)
1604                 if (subdivpolyvert[i][0] == v[0]
1605                  && subdivpolyvert[i][1] == v[1]
1606                  && subdivpolyvert[i][2] == v[2])
1607                         return i;
1608         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
1609                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
1610         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
1611         return subdivpolyverts++;
1612 }
1613
1614 static void SubdividePolygon(int numverts, float *verts)
1615 {
1616         int             i, i1, i2, i3, f, b, c, p;
1617         vec3_t  mins, maxs, front[256], back[256];
1618         float   m, *pv, *cv, dist[256], frac;
1619
1620         if (numverts > 250)
1621                 Host_Error("SubdividePolygon: ran out of verts in buffer");
1622
1623         BoundPoly(numverts, verts, mins, maxs);
1624
1625         for (i = 0;i < 3;i++)
1626         {
1627                 m = (mins[i] + maxs[i]) * 0.5;
1628                 m = r_subdivide_size.value * floor(m/r_subdivide_size.value + 0.5);
1629                 if (maxs[i] - m < 8)
1630                         continue;
1631                 if (m - mins[i] < 8)
1632                         continue;
1633
1634                 // cut it
1635                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
1636                         dist[c] = cv[i] - m;
1637
1638                 f = b = 0;
1639                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
1640                 {
1641                         if (dist[p] >= 0)
1642                         {
1643                                 VectorCopy(pv, front[f]);
1644                                 f++;
1645                         }
1646                         if (dist[p] <= 0)
1647                         {
1648                                 VectorCopy(pv, back[b]);
1649                                 b++;
1650                         }
1651                         if (dist[p] == 0 || dist[c] == 0)
1652                                 continue;
1653                         if ((dist[p] > 0) != (dist[c] > 0) )
1654                         {
1655                                 // clip point
1656                                 frac = dist[p] / (dist[p] - dist[c]);
1657                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
1658                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
1659                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
1660                                 f++;
1661                                 b++;
1662                         }
1663                 }
1664
1665                 SubdividePolygon(f, front[0]);
1666                 SubdividePolygon(b, back[0]);
1667                 return;
1668         }
1669
1670         i1 = subdivpolylookupvert(verts);
1671         i2 = subdivpolylookupvert(verts + 3);
1672         for (i = 2;i < numverts;i++)
1673         {
1674                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
1675                 {
1676                         Con_Print("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
1677                         return;
1678                 }
1679
1680                 i3 = subdivpolylookupvert(verts + i * 3);
1681                 subdivpolyindex[subdivpolytriangles][0] = i1;
1682                 subdivpolyindex[subdivpolytriangles][1] = i2;
1683                 subdivpolyindex[subdivpolytriangles][2] = i3;
1684                 i2 = i3;
1685                 subdivpolytriangles++;
1686         }
1687 }
1688
1689 //Breaks a polygon up along axial 64 unit
1690 //boundaries so that turbulent and sky warps
1691 //can be done reasonably.
1692 static void Mod_Q1BSP_GenerateWarpMesh(msurface_t *surf)
1693 {
1694         int i, j;
1695         surfvertex_t *v;
1696         surfmesh_t *mesh;
1697
1698         subdivpolytriangles = 0;
1699         subdivpolyverts = 0;
1700         SubdividePolygon(surf->mesh.num_vertices, surf->mesh.data_vertex3f);
1701         if (subdivpolytriangles < 1)
1702                 Host_Error("Mod_Q1BSP_GenerateWarpMesh: no triangles?\n");
1703
1704         surf->mesh = mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + subdivpolytriangles * sizeof(int[3]) + subdivpolyverts * sizeof(surfvertex_t));
1705         mesh->num_vertices = subdivpolyverts;
1706         mesh->num_triangles = subdivpolytriangles;
1707         mesh->vertex = (surfvertex_t *)(mesh + 1);
1708         mesh->index = (int *)(mesh->vertex + mesh->num_vertices);
1709         memset(mesh->vertex, 0, mesh->num_vertices * sizeof(surfvertex_t));
1710
1711         for (i = 0;i < mesh->num_triangles;i++)
1712                 for (j = 0;j < 3;j++)
1713                         mesh->index[i*3+j] = subdivpolyindex[i][j];
1714
1715         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
1716         {
1717                 VectorCopy(subdivpolyvert[i], v->v);
1718                 v->st[0] = DotProduct(v->v, surf->texinfo->vecs[0]);
1719                 v->st[1] = DotProduct(v->v, surf->texinfo->vecs[1]);
1720         }
1721 }
1722 #endif
1723
1724 static void Mod_Q1BSP_LoadFaces(lump_t *l)
1725 {
1726         dface_t *in;
1727         msurface_t *surf;
1728         int i, j, count, surfnum, planenum, smax, tmax, ssize, tsize, firstedge, numedges, totalverts, totaltris;
1729         float texmins[2], texmaxs[2], val;
1730
1731         in = (void *)(mod_base + l->fileofs);
1732         if (l->filelen % sizeof(*in))
1733                 Host_Error("Mod_Q1BSP_LoadFaces: funny lump size in %s",loadmodel->name);
1734         count = l->filelen / sizeof(*in);
1735         loadmodel->brushq1.surfaces = Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_t));
1736
1737         loadmodel->brushq1.numsurfaces = count;
1738
1739         totalverts = 0;
1740         totaltris = 0;
1741         for (surfnum = 0, in = (void *)(mod_base + l->fileofs);surfnum < count;surfnum++, in++)
1742         {
1743                 numedges = LittleShort(in->numedges);
1744                 totalverts += numedges;
1745                 totaltris += numedges - 2;
1746         }
1747
1748         // TODO: split up into multiple meshes as needed to avoid exceeding 65536
1749         // vertex limit
1750         loadmodel->nummeshes = 1;
1751         loadmodel->meshlist = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t *));
1752         loadmodel->meshlist[0] = Mod_AllocSurfMesh(loadmodel->mempool, totalverts, totaltris, 0, 0, true, true, false);
1753
1754         totalverts = 0;
1755         totaltris = 0;
1756         for (surfnum = 0, in = (void *)(mod_base + l->fileofs), surf = loadmodel->brushq1.surfaces;surfnum < count;surfnum++, in++, surf++)
1757         {
1758                 surf->number = surfnum;
1759                 // FIXME: validate edges, texinfo, etc?
1760                 firstedge = LittleLong(in->firstedge);
1761                 numedges = LittleShort(in->numedges);
1762                 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)
1763                         Host_Error("Mod_Q1BSP_LoadFaces: invalid edge range (firstedge %i, numedges %i, model edges %i)\n", firstedge, numedges, loadmodel->brushq1.numsurfedges);
1764                 i = LittleShort(in->texinfo);
1765                 if ((unsigned int) i >= (unsigned int) loadmodel->brushq1.numtexinfo)
1766                         Host_Error("Mod_Q1BSP_LoadFaces: invalid texinfo index %i(model has %i texinfos)\n", i, loadmodel->brushq1.numtexinfo);
1767                 surf->texinfo = loadmodel->brushq1.texinfo + i;
1768                 surf->flags = surf->texinfo->texture->flags;
1769
1770                 planenum = LittleShort(in->planenum);
1771                 if ((unsigned int) planenum >= (unsigned int) loadmodel->brush.num_planes)
1772                         Host_Error("Mod_Q1BSP_LoadFaces: invalid plane index %i (model has %i planes)\n", planenum, loadmodel->brush.num_planes);
1773
1774                 if (LittleShort(in->side))
1775                         surf->flags |= SURF_PLANEBACK;
1776
1777                 surf->plane = loadmodel->brush.data_planes + planenum;
1778
1779                 surf->mesh.num_vertices = numedges;
1780                 surf->mesh.num_triangles = numedges - 2;
1781                 surf->mesh.data_vertex3f = loadmodel->meshlist[0]->data_vertex3f + totalverts * 3;
1782                 surf->mesh.data_texcoordtexture2f = loadmodel->meshlist[0]->data_texcoordtexture2f + totalverts * 2;
1783                 surf->mesh.data_texcoordlightmap2f = loadmodel->meshlist[0]->data_texcoordlightmap2f + totalverts * 2;
1784                 surf->mesh.data_texcoorddetail2f = loadmodel->meshlist[0]->data_texcoorddetail2f + totalverts * 2;
1785                 surf->mesh.data_svector3f = loadmodel->meshlist[0]->data_svector3f + totalverts * 3;
1786                 surf->mesh.data_tvector3f = loadmodel->meshlist[0]->data_tvector3f + totalverts * 3;
1787                 surf->mesh.data_normal3f = loadmodel->meshlist[0]->data_normal3f + totalverts * 3;
1788                 surf->mesh.data_lightmapoffsets = loadmodel->meshlist[0]->data_lightmapoffsets + totalverts;
1789                 surf->mesh.data_element3i = loadmodel->meshlist[0]->data_element3i + totaltris * 3;
1790                 surf->mesh.data_neighbor3i = loadmodel->meshlist[0]->data_neighbor3i + totaltris * 3;
1791                 totalverts += numedges;
1792                 totaltris += numedges - 2;
1793
1794                 // convert edges back to a normal polygon
1795                 for (i = 0;i < surf->mesh.num_vertices;i++)
1796                 {
1797                         int lindex = loadmodel->brushq1.surfedges[firstedge + i];
1798                         float s, t;
1799                         if (lindex > 0)
1800                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[lindex].v[0]].position, surf->mesh.data_vertex3f + i * 3);
1801                         else
1802                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[-lindex].v[1]].position, surf->mesh.data_vertex3f + i * 3);
1803                         s = DotProduct((surf->mesh.data_vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3];
1804                         t = DotProduct((surf->mesh.data_vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3];
1805                         surf->mesh.data_texcoordtexture2f[i * 2 + 0] = s / surf->texinfo->texture->width;
1806                         surf->mesh.data_texcoordtexture2f[i * 2 + 1] = t / surf->texinfo->texture->height;
1807                         surf->mesh.data_texcoorddetail2f[i * 2 + 0] = s * (1.0f / 16.0f);
1808                         surf->mesh.data_texcoorddetail2f[i * 2 + 1] = t * (1.0f / 16.0f);
1809                         surf->mesh.data_texcoordlightmap2f[i * 2 + 0] = 0;
1810                         surf->mesh.data_texcoordlightmap2f[i * 2 + 1] = 0;
1811                         surf->mesh.data_lightmapoffsets[i] = 0;
1812                 }
1813
1814                 for (i = 0;i < surf->mesh.num_triangles;i++)
1815                 {
1816                         surf->mesh.data_element3i[i * 3 + 0] = 0;
1817                         surf->mesh.data_element3i[i * 3 + 1] = i + 1;
1818                         surf->mesh.data_element3i[i * 3 + 2] = i + 2;
1819                 }
1820
1821                 // compile additional data about the surface geometry
1822                 Mod_BuildTriangleNeighbors(surf->mesh.data_neighbor3i, surf->mesh.data_element3i, surf->mesh.num_triangles);
1823                 Mod_BuildTextureVectorsAndNormals(surf->mesh.num_vertices, surf->mesh.num_triangles, surf->mesh.data_vertex3f, surf->mesh.data_texcoordtexture2f, surf->mesh.data_element3i, surf->mesh.data_svector3f, surf->mesh.data_tvector3f, surf->mesh.data_normal3f);
1824                 BoxFromPoints(surf->mins, surf->maxs, surf->mesh.num_vertices, surf->mesh.data_vertex3f);
1825
1826                 // generate surface extents information
1827                 texmins[0] = texmaxs[0] = DotProduct(surf->mesh.data_vertex3f, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3];
1828                 texmins[1] = texmaxs[1] = DotProduct(surf->mesh.data_vertex3f, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3];
1829                 for (i = 1;i < surf->mesh.num_vertices;i++)
1830                 {
1831                         for (j = 0;j < 2;j++)
1832                         {
1833                                 val = DotProduct(surf->mesh.data_vertex3f + i * 3, surf->texinfo->vecs[j]) + surf->texinfo->vecs[j][3];
1834                                 texmins[j] = min(texmins[j], val);
1835                                 texmaxs[j] = max(texmaxs[j], val);
1836                         }
1837                 }
1838                 for (i = 0;i < 2;i++)
1839                 {
1840                         surf->texturemins[i] = (int) floor(texmins[i] / 16.0) * 16;
1841                         surf->extents[i] = (int) ceil(texmaxs[i] / 16.0) * 16 - surf->texturemins[i];
1842                 }
1843
1844                 smax = surf->extents[0] >> 4;
1845                 tmax = surf->extents[1] >> 4;
1846                 ssize = (surf->extents[0] >> 4) + 1;
1847                 tsize = (surf->extents[1] >> 4) + 1;
1848
1849                 // lighting info
1850                 for (i = 0;i < MAXLIGHTMAPS;i++)
1851                         surf->styles[i] = in->styles[i];
1852                 // force lightmap upload on first time seeing the surface
1853                 surf->cached_dlight = true;
1854                 surf->lightmaptexturestride = 0;
1855                 surf->lightmaptexture = NULL;
1856                 i = LittleLong(in->lightofs);
1857                 if (i == -1)
1858                         surf->samples = NULL;
1859                 else if (loadmodel->brush.ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
1860                         surf->samples = loadmodel->brushq1.lightdata + i;
1861                 else // LordHavoc: white lighting (bsp version 29)
1862                         surf->samples = loadmodel->brushq1.lightdata + (i * 3);
1863
1864                 if (surf->texinfo->texture->flags & SURF_LIGHTMAP)
1865                 {
1866                         if (ssize > 256 || tsize > 256)
1867                                 Host_Error("Bad surface extents");
1868                         // stainmap for permanent marks on walls
1869                         surf->stainsamples = Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
1870                         // clear to white
1871                         memset(surf->stainsamples, 255, ssize * tsize * 3);
1872                 }
1873
1874                 if (surf->texinfo->texture->flags & SURF_LIGHTMAP)
1875                 {
1876                         int i, iu, iv;
1877                         float u, v, ubase, vbase, uscale, vscale;
1878
1879                         if (r_miplightmaps.integer)
1880                         {
1881                                 surf->lightmaptexturestride = ssize;
1882                                 surf->lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, NULL, surf->lightmaptexturestride, tsize, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_MIPMAP | TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
1883                         }
1884                         else
1885                         {
1886                                 surf->lightmaptexturestride = R_CompatibleFragmentWidth(ssize, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, 0);
1887                                 surf->lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, NULL, surf->lightmaptexturestride, tsize, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FRAGMENT | TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
1888                         }
1889                         R_FragmentLocation(surf->lightmaptexture, NULL, NULL, &ubase, &vbase, &uscale, &vscale);
1890                         uscale = (uscale - ubase) / ssize;
1891                         vscale = (vscale - vbase) / tsize;
1892
1893                         for (i = 0;i < surf->mesh.num_vertices;i++)
1894                         {
1895                                 u = ((DotProduct((surf->mesh.data_vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3]) + 8 - surf->texturemins[0]) * (1.0 / 16.0);
1896                                 v = ((DotProduct((surf->mesh.data_vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3]) + 8 - surf->texturemins[1]) * (1.0 / 16.0);
1897                                 surf->mesh.data_texcoordlightmap2f[i * 2 + 0] = u * uscale + ubase;
1898                                 surf->mesh.data_texcoordlightmap2f[i * 2 + 1] = v * vscale + vbase;
1899                                 // LordHavoc: calc lightmap data offset for vertex lighting to use
1900                                 iu = (int) u;
1901                                 iv = (int) v;
1902                                 surf->mesh.data_lightmapoffsets[i] = (bound(0, iv, tmax) * ssize + bound(0, iu, smax)) * 3;
1903                         }
1904                 }
1905         }
1906 }
1907
1908 static void Mod_Q1BSP_SetParent(mnode_t *node, mnode_t *parent)
1909 {
1910         node->parent = parent;
1911         if (node->plane)
1912         {
1913                 Mod_Q1BSP_SetParent(node->children[0], node);
1914                 Mod_Q1BSP_SetParent(node->children[1], node);
1915         }
1916 }
1917
1918 static void Mod_Q1BSP_LoadNodes(lump_t *l)
1919 {
1920         int                     i, j, count, p;
1921         dnode_t         *in;
1922         mnode_t         *out;
1923
1924         in = (void *)(mod_base + l->fileofs);
1925         if (l->filelen % sizeof(*in))
1926                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
1927         count = l->filelen / sizeof(*in);
1928         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1929
1930         loadmodel->brush.data_nodes = out;
1931         loadmodel->brush.num_nodes = count;
1932
1933         for ( i=0 ; i<count ; i++, in++, out++)
1934         {
1935                 for (j=0 ; j<3 ; j++)
1936                 {
1937                         out->mins[j] = LittleShort(in->mins[j]);
1938                         out->maxs[j] = LittleShort(in->maxs[j]);
1939                 }
1940
1941                 p = LittleLong(in->planenum);
1942                 out->plane = loadmodel->brush.data_planes + p;
1943
1944                 out->firstsurface = LittleShort(in->firstface);
1945                 out->numsurfaces = LittleShort(in->numfaces);
1946
1947                 for (j=0 ; j<2 ; j++)
1948                 {
1949                         p = LittleShort(in->children[j]);
1950                         if (p >= 0)
1951                                 out->children[j] = loadmodel->brush.data_nodes + p;
1952                         else
1953                                 out->children[j] = (mnode_t *)(loadmodel->brush.data_leafs + (-1 - p));
1954                 }
1955         }
1956
1957         Mod_Q1BSP_SetParent(loadmodel->brush.data_nodes, NULL); // sets nodes and leafs
1958 }
1959
1960 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
1961 {
1962         dleaf_t *in;
1963         mleaf_t *out;
1964         int i, j, count, p;
1965
1966         in = (void *)(mod_base + l->fileofs);
1967         if (l->filelen % sizeof(*in))
1968                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
1969         count = l->filelen / sizeof(*in);
1970         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1971
1972         loadmodel->brush.data_leafs = out;
1973         loadmodel->brush.num_leafs = count;
1974         // get visleafs from the submodel data
1975         loadmodel->brush.num_pvsclusters = loadmodel->brushq1.submodels[0].visleafs;
1976         loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters+7)>>3;
1977         loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
1978         memset(loadmodel->brush.data_pvsclusters, 0xFF, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
1979
1980         for ( i=0 ; i<count ; i++, in++, out++)
1981         {
1982                 for (j=0 ; j<3 ; j++)
1983                 {
1984                         out->mins[j] = LittleShort(in->mins[j]);
1985                         out->maxs[j] = LittleShort(in->maxs[j]);
1986                 }
1987
1988                 // FIXME: this function could really benefit from some error checking
1989
1990                 out->contents = LittleLong(in->contents);
1991
1992                 out->firstleafface = loadmodel->brush.data_leaffaces + LittleShort(in->firstmarksurface);
1993                 out->numleaffaces = LittleShort(in->nummarksurfaces);
1994                 if (out->firstleafface < 0 || LittleShort(in->firstmarksurface) + out->numleaffaces > loadmodel->brush.num_leaffaces)
1995                 {
1996                         Con_Printf("Mod_Q1BSP_LoadLeafs: invalid leafface range %i:%i outside range %i:%i\n", out->firstleafface, out->firstleafface + out->numleaffaces, 0, loadmodel->brush.num_leaffaces);
1997                         out->firstleafface = NULL;
1998                         out->numleaffaces = 0;
1999                 }
2000
2001                 out->clusterindex = i - 1;
2002                 if (out->clusterindex >= loadmodel->brush.num_pvsclusters)
2003                         out->clusterindex = -1;
2004
2005                 p = LittleLong(in->visofs);
2006                 // ignore visofs errors on leaf 0 (solid)
2007                 if (p >= 0 && out->clusterindex >= 0)
2008                 {
2009                         if (p >= loadmodel->brushq1.num_compressedpvs)
2010                                 Con_Print("Mod_Q1BSP_LoadLeafs: invalid visofs\n");
2011                         else
2012                                 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);
2013                 }
2014
2015                 for (j = 0;j < 4;j++)
2016                         out->ambient_sound_level[j] = in->ambient_level[j];
2017
2018                 // FIXME: Insert caustics here
2019         }
2020 }
2021
2022 static void Mod_Q1BSP_LoadClipnodes(lump_t *l)
2023 {
2024         dclipnode_t *in, *out;
2025         int                     i, count;
2026         hull_t          *hull;
2027
2028         in = (void *)(mod_base + l->fileofs);
2029         if (l->filelen % sizeof(*in))
2030                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2031         count = l->filelen / sizeof(*in);
2032         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2033
2034         loadmodel->brushq1.clipnodes = out;
2035         loadmodel->brushq1.numclipnodes = count;
2036
2037         if (loadmodel->brush.ishlbsp)
2038         {
2039                 hull = &loadmodel->brushq1.hulls[1];
2040                 hull->clipnodes = out;
2041                 hull->firstclipnode = 0;
2042                 hull->lastclipnode = count-1;
2043                 hull->planes = loadmodel->brush.data_planes;
2044                 hull->clip_mins[0] = -16;
2045                 hull->clip_mins[1] = -16;
2046                 hull->clip_mins[2] = -36;
2047                 hull->clip_maxs[0] = 16;
2048                 hull->clip_maxs[1] = 16;
2049                 hull->clip_maxs[2] = 36;
2050                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2051
2052                 hull = &loadmodel->brushq1.hulls[2];
2053                 hull->clipnodes = out;
2054                 hull->firstclipnode = 0;
2055                 hull->lastclipnode = count-1;
2056                 hull->planes = loadmodel->brush.data_planes;
2057                 hull->clip_mins[0] = -32;
2058                 hull->clip_mins[1] = -32;
2059                 hull->clip_mins[2] = -32;
2060                 hull->clip_maxs[0] = 32;
2061                 hull->clip_maxs[1] = 32;
2062                 hull->clip_maxs[2] = 32;
2063                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2064
2065                 hull = &loadmodel->brushq1.hulls[3];
2066                 hull->clipnodes = out;
2067                 hull->firstclipnode = 0;
2068                 hull->lastclipnode = count-1;
2069                 hull->planes = loadmodel->brush.data_planes;
2070                 hull->clip_mins[0] = -16;
2071                 hull->clip_mins[1] = -16;
2072                 hull->clip_mins[2] = -18;
2073                 hull->clip_maxs[0] = 16;
2074                 hull->clip_maxs[1] = 16;
2075                 hull->clip_maxs[2] = 18;
2076                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2077         }
2078         else
2079         {
2080                 hull = &loadmodel->brushq1.hulls[1];
2081                 hull->clipnodes = out;
2082                 hull->firstclipnode = 0;
2083                 hull->lastclipnode = count-1;
2084                 hull->planes = loadmodel->brush.data_planes;
2085                 hull->clip_mins[0] = -16;
2086                 hull->clip_mins[1] = -16;
2087                 hull->clip_mins[2] = -24;
2088                 hull->clip_maxs[0] = 16;
2089                 hull->clip_maxs[1] = 16;
2090                 hull->clip_maxs[2] = 32;
2091                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2092
2093                 hull = &loadmodel->brushq1.hulls[2];
2094                 hull->clipnodes = out;
2095                 hull->firstclipnode = 0;
2096                 hull->lastclipnode = count-1;
2097                 hull->planes = loadmodel->brush.data_planes;
2098                 hull->clip_mins[0] = -32;
2099                 hull->clip_mins[1] = -32;
2100                 hull->clip_mins[2] = -24;
2101                 hull->clip_maxs[0] = 32;
2102                 hull->clip_maxs[1] = 32;
2103                 hull->clip_maxs[2] = 64;
2104                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2105         }
2106
2107         for (i=0 ; i<count ; i++, out++, in++)
2108         {
2109                 out->planenum = LittleLong(in->planenum);
2110                 out->children[0] = LittleShort(in->children[0]);
2111                 out->children[1] = LittleShort(in->children[1]);
2112                 if (out->children[0] >= count || out->children[1] >= count)
2113                         Host_Error("Corrupt clipping hull(out of range child)\n");
2114         }
2115 }
2116
2117 //Duplicate the drawing hull structure as a clipping hull
2118 static void Mod_Q1BSP_MakeHull0(void)
2119 {
2120         mnode_t         *in;
2121         dclipnode_t *out;
2122         int                     i;
2123         hull_t          *hull;
2124
2125         hull = &loadmodel->brushq1.hulls[0];
2126
2127         in = loadmodel->brush.data_nodes;
2128         out = Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_nodes * sizeof(dclipnode_t));
2129
2130         hull->clipnodes = out;
2131         hull->firstclipnode = 0;
2132         hull->lastclipnode = loadmodel->brush.num_nodes - 1;
2133         hull->planes = loadmodel->brush.data_planes;
2134
2135         for (i = 0;i < loadmodel->brush.num_nodes;i++, out++, in++)
2136         {
2137                 out->planenum = in->plane - loadmodel->brush.data_planes;
2138                 out->children[0] = in->children[0]->plane ? in->children[0] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[0])->contents;
2139                 out->children[1] = in->children[1]->plane ? in->children[1] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[1])->contents;
2140         }
2141 }
2142
2143 static void Mod_Q1BSP_LoadLeaffaces(lump_t *l)
2144 {
2145         int i, j;
2146         short *in;
2147
2148         in = (void *)(mod_base + l->fileofs);
2149         if (l->filelen % sizeof(*in))
2150                 Host_Error("Mod_Q1BSP_LoadLeaffaces: funny lump size in %s",loadmodel->name);
2151         loadmodel->brush.num_leaffaces = l->filelen / sizeof(*in);
2152         loadmodel->brush.data_leaffaces = Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_leaffaces * sizeof(int));
2153
2154         for (i = 0;i < loadmodel->brush.num_leaffaces;i++)
2155         {
2156                 j = (unsigned) LittleShort(in[i]);
2157                 if (j >= loadmodel->brushq1.numsurfaces)
2158                         Host_Error("Mod_Q1BSP_LoadLeaffaces: bad surface number");
2159                 loadmodel->brush.data_leaffaces[i] = j;
2160         }
2161 }
2162
2163 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2164 {
2165         int             i;
2166         int             *in;
2167
2168         in = (void *)(mod_base + l->fileofs);
2169         if (l->filelen % sizeof(*in))
2170                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2171         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2172         loadmodel->brushq1.surfedges = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2173
2174         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2175                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2176 }
2177
2178
2179 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2180 {
2181         int                     i;
2182         mplane_t        *out;
2183         dplane_t        *in;
2184
2185         in = (void *)(mod_base + l->fileofs);
2186         if (l->filelen % sizeof(*in))
2187                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2188
2189         loadmodel->brush.num_planes = l->filelen / sizeof(*in);
2190         loadmodel->brush.data_planes = out = Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_planes * sizeof(*out));
2191
2192         for (i = 0;i < loadmodel->brush.num_planes;i++, in++, out++)
2193         {
2194                 out->normal[0] = LittleFloat(in->normal[0]);
2195                 out->normal[1] = LittleFloat(in->normal[1]);
2196                 out->normal[2] = LittleFloat(in->normal[2]);
2197                 out->dist = LittleFloat(in->dist);
2198
2199                 PlaneClassify(out);
2200         }
2201 }
2202
2203 static void Mod_Q1BSP_LoadMapBrushes(void)
2204 {
2205 #if 0
2206 // unfinished
2207         int submodel, numbrushes;
2208         qboolean firstbrush;
2209         char *text, *maptext;
2210         char mapfilename[MAX_QPATH];
2211         FS_StripExtension (loadmodel->name, mapfilename, sizeof (mapfilename));
2212         strlcat (mapfilename, ".map", sizeof (mapfilename));
2213         maptext = (qbyte*) FS_LoadFile(mapfilename, tempmempool, false);
2214         if (!maptext)
2215                 return;
2216         text = maptext;
2217         if (!COM_ParseToken(&data, false))
2218                 return; // error
2219         submodel = 0;
2220         for (;;)
2221         {
2222                 if (!COM_ParseToken(&data, false))
2223                         break;
2224                 if (com_token[0] != '{')
2225                         return; // error
2226                 // entity
2227                 firstbrush = true;
2228                 numbrushes = 0;
2229                 maxbrushes = 256;
2230                 brushes = Mem_Alloc(loadmodel->mempool, maxbrushes * sizeof(mbrush_t));
2231                 for (;;)
2232                 {
2233                         if (!COM_ParseToken(&data, false))
2234                                 return; // error
2235                         if (com_token[0] == '}')
2236                                 break; // end of entity
2237                         if (com_token[0] == '{')
2238                         {
2239                                 // brush
2240                                 if (firstbrush)
2241                                 {
2242                                         if (submodel)
2243                                         {
2244                                                 if (submodel > loadmodel->brush.numsubmodels)
2245                                                 {
2246                                                         Con_Printf("Mod_Q1BSP_LoadMapBrushes: .map has more submodels than .bsp!\n");
2247                                                         model = NULL;
2248                                                 }
2249                                                 else
2250                                                         model = loadmodel->brush.submodels[submodel];
2251                                         }
2252                                         else
2253                                                 model = loadmodel;
2254                                 }
2255                                 for (;;)
2256                                 {
2257                                         if (!COM_ParseToken(&data, false))
2258                                                 return; // error
2259                                         if (com_token[0] == '}')
2260                                                 break; // end of brush
2261                                         // each brush face should be this format:
2262                                         // ( x y z ) ( x y z ) ( x y z ) texture scroll_s scroll_t rotateangle scale_s scale_t
2263                                         // FIXME: support hl .map format
2264                                         for (pointnum = 0;pointnum < 3;pointnum++)
2265                                         {
2266                                                 COM_ParseToken(&data, false);
2267                                                 for (componentnum = 0;componentnum < 3;componentnum++)
2268                                                 {
2269                                                         COM_ParseToken(&data, false);
2270                                                         point[pointnum][componentnum] = atof(com_token);
2271                                                 }
2272                                                 COM_ParseToken(&data, false);
2273                                         }
2274                                         COM_ParseToken(&data, false);
2275                                         strlcpy(facetexture, com_token, sizeof(facetexture));
2276                                         COM_ParseToken(&data, false);
2277                                         //scroll_s = atof(com_token);
2278                                         COM_ParseToken(&data, false);
2279                                         //scroll_t = atof(com_token);
2280                                         COM_ParseToken(&data, false);
2281                                         //rotate = atof(com_token);
2282                                         COM_ParseToken(&data, false);
2283                                         //scale_s = atof(com_token);
2284                                         COM_ParseToken(&data, false);
2285                                         //scale_t = atof(com_token);
2286                                         TriangleNormal(point[0], point[1], point[2], planenormal);
2287                                         VectorNormalizeDouble(planenormal);
2288                                         planedist = DotProduct(point[0], planenormal);
2289                                         //ChooseTexturePlane(planenormal, texturevector[0], texturevector[1]);
2290                                 }
2291                                 continue;
2292                         }
2293                 }
2294         }
2295 #endif
2296 }
2297
2298
2299 #define MAX_PORTALPOINTS 64
2300
2301 typedef struct portal_s
2302 {
2303         mplane_t plane;
2304         mnode_t *nodes[2];              // [0] = front side of plane
2305         struct portal_s *next[2];
2306         int numpoints;
2307         double points[3*MAX_PORTALPOINTS];
2308         struct portal_s *chain; // all portals are linked into a list
2309 }
2310 portal_t;
2311
2312 static portal_t *portalchain;
2313
2314 /*
2315 ===========
2316 AllocPortal
2317 ===========
2318 */
2319 static portal_t *AllocPortal(void)
2320 {
2321         portal_t *p;
2322         p = Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2323         p->chain = portalchain;
2324         portalchain = p;
2325         return p;
2326 }
2327
2328 static void FreePortal(portal_t *p)
2329 {
2330         Mem_Free(p);
2331 }
2332
2333 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2334 {
2335         // process only nodes (leafs already had their box calculated)
2336         if (!node->plane)
2337                 return;
2338
2339         // calculate children first
2340         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2341         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2342
2343         // make combined bounding box from children
2344         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2345         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2346         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2347         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2348         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2349         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2350 }
2351
2352 static void Mod_Q1BSP_FinalizePortals(void)
2353 {
2354         int i, j, numportals, numpoints;
2355         portal_t *p, *pnext;
2356         mportal_t *portal;
2357         mvertex_t *point;
2358         mleaf_t *leaf, *endleaf;
2359
2360         // recalculate bounding boxes for all leafs(because qbsp is very sloppy)
2361         leaf = loadmodel->brush.data_leafs;
2362         endleaf = leaf + loadmodel->brush.num_leafs;
2363         for (;leaf < endleaf;leaf++)
2364         {
2365                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2366                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2367         }
2368         p = portalchain;
2369         while (p)
2370         {
2371                 if (p->numpoints >= 3)
2372                 {
2373                         for (i = 0;i < 2;i++)
2374                         {
2375                                 leaf = (mleaf_t *)p->nodes[i];
2376                                 for (j = 0;j < p->numpoints;j++)
2377                                 {
2378                                         if (leaf->mins[0] > p->points[j*3+0]) leaf->mins[0] = p->points[j*3+0];
2379                                         if (leaf->mins[1] > p->points[j*3+1]) leaf->mins[1] = p->points[j*3+1];
2380                                         if (leaf->mins[2] > p->points[j*3+2]) leaf->mins[2] = p->points[j*3+2];
2381                                         if (leaf->maxs[0] < p->points[j*3+0]) leaf->maxs[0] = p->points[j*3+0];
2382                                         if (leaf->maxs[1] < p->points[j*3+1]) leaf->maxs[1] = p->points[j*3+1];
2383                                         if (leaf->maxs[2] < p->points[j*3+2]) leaf->maxs[2] = p->points[j*3+2];
2384                                 }
2385                         }
2386                 }
2387                 p = p->chain;
2388         }
2389
2390         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brush.data_nodes);
2391
2392         // tally up portal and point counts
2393         p = portalchain;
2394         numportals = 0;
2395         numpoints = 0;
2396         while (p)
2397         {
2398                 // note: this check must match the one below or it will usually corrupt memory
2399                 // 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
2400                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1] && ((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2401                 {
2402                         numportals += 2;
2403                         numpoints += p->numpoints * 2;
2404                 }
2405                 p = p->chain;
2406         }
2407         loadmodel->brush.data_portals = Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2408         loadmodel->brush.num_portals = numportals;
2409         loadmodel->brush.data_portalpoints = (void *)((qbyte *) loadmodel->brush.data_portals + numportals * sizeof(mportal_t));
2410         loadmodel->brush.num_portalpoints = numpoints;
2411         // clear all leaf portal chains
2412         for (i = 0;i < loadmodel->brush.num_leafs;i++)
2413                 loadmodel->brush.data_leafs[i].portals = NULL;
2414         // process all portals in the global portal chain, while freeing them
2415         portal = loadmodel->brush.data_portals;
2416         point = loadmodel->brush.data_portalpoints;
2417         p = portalchain;
2418         portalchain = NULL;
2419         while (p)
2420         {
2421                 pnext = p->chain;
2422
2423                 // note: this check must match the one above or it will usually corrupt memory
2424                 // 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
2425                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1] && ((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2426                 {
2427                         // first make the back to front portal(forward portal)
2428                         portal->points = point;
2429                         portal->numpoints = p->numpoints;
2430                         portal->plane.dist = p->plane.dist;
2431                         VectorCopy(p->plane.normal, portal->plane.normal);
2432                         portal->here = (mleaf_t *)p->nodes[1];
2433                         portal->past = (mleaf_t *)p->nodes[0];
2434                         // copy points
2435                         for (j = 0;j < portal->numpoints;j++)
2436                         {
2437                                 VectorCopy(p->points + j*3, point->position);
2438                                 point++;
2439                         }
2440                         BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2441                         PlaneClassify(&portal->plane);
2442
2443                         // link into leaf's portal chain
2444                         portal->next = portal->here->portals;
2445                         portal->here->portals = portal;
2446
2447                         // advance to next portal
2448                         portal++;
2449
2450                         // then make the front to back portal(backward portal)
2451                         portal->points = point;
2452                         portal->numpoints = p->numpoints;
2453                         portal->plane.dist = -p->plane.dist;
2454                         VectorNegate(p->plane.normal, portal->plane.normal);
2455                         portal->here = (mleaf_t *)p->nodes[0];
2456                         portal->past = (mleaf_t *)p->nodes[1];
2457                         // copy points
2458                         for (j = portal->numpoints - 1;j >= 0;j--)
2459                         {
2460                                 VectorCopy(p->points + j*3, point->position);
2461                                 point++;
2462                         }
2463                         BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2464                         PlaneClassify(&portal->plane);
2465
2466                         // link into leaf's portal chain
2467                         portal->next = portal->here->portals;
2468                         portal->here->portals = portal;
2469
2470                         // advance to next portal
2471                         portal++;
2472                 }
2473                 FreePortal(p);
2474                 p = pnext;
2475         }
2476 }
2477
2478 /*
2479 =============
2480 AddPortalToNodes
2481 =============
2482 */
2483 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2484 {
2485         if (!front)
2486                 Host_Error("AddPortalToNodes: NULL front node");
2487         if (!back)
2488                 Host_Error("AddPortalToNodes: NULL back node");
2489         if (p->nodes[0] || p->nodes[1])
2490                 Host_Error("AddPortalToNodes: already included");
2491         // 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
2492
2493         p->nodes[0] = front;
2494         p->next[0] = (portal_t *)front->portals;
2495         front->portals = (mportal_t *)p;
2496
2497         p->nodes[1] = back;
2498         p->next[1] = (portal_t *)back->portals;
2499         back->portals = (mportal_t *)p;
2500 }
2501
2502 /*
2503 =============
2504 RemovePortalFromNode
2505 =============
2506 */
2507 static void RemovePortalFromNodes(portal_t *portal)
2508 {
2509         int i;
2510         mnode_t *node;
2511         void **portalpointer;
2512         portal_t *t;
2513         for (i = 0;i < 2;i++)
2514         {
2515                 node = portal->nodes[i];
2516
2517                 portalpointer = (void **) &node->portals;
2518                 while (1)
2519                 {
2520                         t = *portalpointer;
2521                         if (!t)
2522                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2523
2524                         if (t == portal)
2525                         {
2526                                 if (portal->nodes[0] == node)
2527                                 {
2528                                         *portalpointer = portal->next[0];
2529                                         portal->nodes[0] = NULL;
2530                                 }
2531                                 else if (portal->nodes[1] == node)
2532                                 {
2533                                         *portalpointer = portal->next[1];
2534                                         portal->nodes[1] = NULL;
2535                                 }
2536                                 else
2537                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2538                                 break;
2539                         }
2540
2541                         if (t->nodes[0] == node)
2542                                 portalpointer = (void **) &t->next[0];
2543                         else if (t->nodes[1] == node)
2544                                 portalpointer = (void **) &t->next[1];
2545                         else
2546                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2547                 }
2548         }
2549 }
2550
2551 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2552 {
2553         int i, side;
2554         mnode_t *front, *back, *other_node;
2555         mplane_t clipplane, *plane;
2556         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2557         int numfrontpoints, numbackpoints;
2558         double frontpoints[3*MAX_PORTALPOINTS], backpoints[3*MAX_PORTALPOINTS];
2559
2560         // if a leaf, we're done
2561         if (!node->plane)
2562                 return;
2563
2564         plane = node->plane;
2565
2566         front = node->children[0];
2567         back = node->children[1];
2568         if (front == back)
2569                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2570
2571         // create the new portal by generating a polygon for the node plane,
2572         // and clipping it by all of the other portals(which came from nodes above this one)
2573         nodeportal = AllocPortal();
2574         nodeportal->plane = *plane;
2575
2576         PolygonD_QuadForPlane(nodeportal->points, nodeportal->plane.normal[0], nodeportal->plane.normal[1], nodeportal->plane.normal[2], nodeportal->plane.dist, 1024.0*1024.0*1024.0);
2577         nodeportal->numpoints = 4;
2578         side = 0;       // shut up compiler warning
2579         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2580         {
2581                 clipplane = portal->plane;
2582                 if (portal->nodes[0] == portal->nodes[1])
2583                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2584                 if (portal->nodes[0] == node)
2585                         side = 0;
2586                 else if (portal->nodes[1] == node)
2587                 {
2588                         clipplane.dist = -clipplane.dist;
2589                         VectorNegate(clipplane.normal, clipplane.normal);
2590                         side = 1;
2591                 }
2592                 else
2593                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2594
2595                 for (i = 0;i < nodeportal->numpoints*3;i++)
2596                         frontpoints[i] = nodeportal->points[i];
2597                 PolygonD_Divide(nodeportal->numpoints, frontpoints, clipplane.normal[0], clipplane.normal[1], clipplane.normal[2], clipplane.dist, 1.0/32.0, MAX_PORTALPOINTS, nodeportal->points, &nodeportal->numpoints, 0, NULL, NULL);
2598                 if (nodeportal->numpoints <= 0 || nodeportal->numpoints >= MAX_PORTALPOINTS)
2599                         break;
2600         }
2601
2602         if (nodeportal->numpoints < 3)
2603         {
2604                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2605                 nodeportal->numpoints = 0;
2606         }
2607         else if (nodeportal->numpoints >= MAX_PORTALPOINTS)
2608         {
2609                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal has too many points\n");
2610                 nodeportal->numpoints = 0;
2611         }
2612         else
2613         {
2614                 AddPortalToNodes(nodeportal, front, back);
2615
2616                 // split the portals of this node along this node's plane and assign them to the children of this node
2617                 // (migrating the portals downward through the tree)
2618                 for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2619                 {
2620                         if (portal->nodes[0] == portal->nodes[1])
2621                                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2622                         if (portal->nodes[0] == node)
2623                                 side = 0;
2624                         else if (portal->nodes[1] == node)
2625                                 side = 1;
2626                         else
2627                                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2628                         nextportal = portal->next[side];
2629
2630                         other_node = portal->nodes[!side];
2631                         RemovePortalFromNodes(portal);
2632
2633                         // cut the portal into two portals, one on each side of the node plane
2634                         PolygonD_Divide(portal->numpoints, portal->points, plane->normal[0], plane->normal[1], plane->normal[2], plane->dist, 1.0/32.0, MAX_PORTALPOINTS, frontpoints, &numfrontpoints, MAX_PORTALPOINTS, backpoints, &numbackpoints);
2635
2636                         if (!numfrontpoints)
2637                         {
2638                                 if (side == 0)
2639                                         AddPortalToNodes(portal, back, other_node);
2640                                 else
2641                                         AddPortalToNodes(portal, other_node, back);
2642                                 continue;
2643                         }
2644                         if (!numbackpoints)
2645                         {
2646                                 if (side == 0)
2647                                         AddPortalToNodes(portal, front, other_node);
2648                                 else
2649                                         AddPortalToNodes(portal, other_node, front);
2650                                 continue;
2651                         }
2652
2653                         // the portal is split
2654                         splitportal = AllocPortal();
2655                         temp = splitportal->chain;
2656                         *splitportal = *portal;
2657                         splitportal->chain = temp;
2658                         for (i = 0;i < numbackpoints*3;i++)
2659                                 splitportal->points[i] = backpoints[i];
2660                         splitportal->numpoints = numbackpoints;
2661                         for (i = 0;i < numfrontpoints*3;i++)
2662                                 portal->points[i] = frontpoints[i];
2663                         portal->numpoints = numfrontpoints;
2664
2665                         if (side == 0)
2666                         {
2667                                 AddPortalToNodes(portal, front, other_node);
2668                                 AddPortalToNodes(splitportal, back, other_node);
2669                         }
2670                         else
2671                         {
2672                                 AddPortalToNodes(portal, other_node, front);
2673                                 AddPortalToNodes(splitportal, other_node, back);
2674                         }
2675                 }
2676         }
2677
2678         Mod_Q1BSP_RecursiveNodePortals(front);
2679         Mod_Q1BSP_RecursiveNodePortals(back);
2680 }
2681
2682 static void Mod_Q1BSP_MakePortals(void)
2683 {
2684         portalchain = NULL;
2685         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brush.data_nodes);
2686         Mod_Q1BSP_FinalizePortals();
2687 }
2688
2689 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
2690 {
2691         int i, j, stylecounts[256], totalcount, remapstyles[256];
2692         msurface_t *surf;
2693         memset(stylecounts, 0, sizeof(stylecounts));
2694         for (i = 0;i < model->nummodelsurfaces;i++)
2695         {
2696                 surf = model->brushq1.surfaces + model->firstmodelsurface + i;
2697                 for (j = 0;j < MAXLIGHTMAPS;j++)
2698                         stylecounts[surf->styles[j]]++;
2699         }
2700         totalcount = 0;
2701         model->brushq1.light_styles = 0;
2702         for (i = 0;i < 255;i++)
2703         {
2704                 if (stylecounts[i])
2705                 {
2706                         remapstyles[i] = model->brushq1.light_styles++;
2707                         totalcount += stylecounts[i] + 1;
2708                 }
2709         }
2710         if (!totalcount)
2711                 return;
2712         model->brushq1.light_style = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(qbyte));
2713         model->brushq1.light_stylevalue = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(int));
2714         model->brushq1.light_styleupdatechains = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(msurface_t **));
2715         model->brushq1.light_styleupdatechainsbuffer = Mem_Alloc(mempool, totalcount * sizeof(msurface_t *));
2716         model->brushq1.light_styles = 0;
2717         for (i = 0;i < 255;i++)
2718                 if (stylecounts[i])
2719                         model->brushq1.light_style[model->brushq1.light_styles++] = i;
2720         j = 0;
2721         for (i = 0;i < model->brushq1.light_styles;i++)
2722         {
2723                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2724                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2725         }
2726         for (i = 0;i < model->nummodelsurfaces;i++)
2727         {
2728                 surf = model->brushq1.surfaces + model->firstmodelsurface + i;
2729                 for (j = 0;j < MAXLIGHTMAPS;j++)
2730                         if (surf->styles[j] != 255)
2731                                 *model->brushq1.light_styleupdatechains[remapstyles[surf->styles[j]]]++ = surf;
2732         }
2733         j = 0;
2734         for (i = 0;i < model->brushq1.light_styles;i++)
2735         {
2736                 *model->brushq1.light_styleupdatechains[i] = NULL;
2737                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2738                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2739         }
2740 }
2741
2742 //Returns PVS data for a given point
2743 //(note: can return NULL)
2744 static qbyte *Mod_Q1BSP_GetPVS(model_t *model, const vec3_t p)
2745 {
2746         mnode_t *node;
2747         Mod_CheckLoaded(model);
2748         node = model->brush.data_nodes;
2749         while (node->plane)
2750                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
2751         if (((mleaf_t *)node)->clusterindex >= 0)
2752                 return model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
2753         else
2754                 return NULL;
2755 }
2756
2757 static void Mod_Q1BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbytes, mnode_t *node)
2758 {
2759         while (node->plane)
2760         {
2761                 float d = PlaneDiff(org, node->plane);
2762                 if (d > radius)
2763                         node = node->children[0];
2764                 else if (d < -radius)
2765                         node = node->children[1];
2766                 else
2767                 {
2768                         // go down both sides
2769                         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
2770                         node = node->children[1];
2771                 }
2772         }
2773         // if this leaf is in a cluster, accumulate the pvs bits
2774         if (((mleaf_t *)node)->clusterindex >= 0)
2775         {
2776                 int i;
2777                 qbyte *pvs = model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
2778                 for (i = 0;i < pvsbytes;i++)
2779                         pvsbuffer[i] |= pvs[i];
2780         }
2781 }
2782
2783 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
2784 //of the given point.
2785 static int Mod_Q1BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbufferlength)
2786 {
2787         int bytes = ((model->brush.num_leafs - 1) + 7) >> 3;
2788         bytes = min(bytes, pvsbufferlength);
2789         if (r_novis.integer || !Mod_Q1BSP_GetPVS(model, org))
2790         {
2791                 memset(pvsbuffer, 0xFF, bytes);
2792                 return bytes;
2793         }
2794         memset(pvsbuffer, 0, bytes);
2795         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brush.data_nodes);
2796         return bytes;
2797 }
2798
2799 static void Mod_Q1BSP_RoundUpToHullSize(model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
2800 {
2801         vec3_t size;
2802         const hull_t *hull;
2803
2804         VectorSubtract(inmaxs, inmins, size);
2805         if (cmodel->brush.ishlbsp)
2806         {
2807                 if (size[0] < 3)
2808                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
2809                 else if (size[0] <= 32)
2810                 {
2811                         if (size[2] < 54) // pick the nearest of 36 or 72
2812                                 hull = &cmodel->brushq1.hulls[3]; // 32x32x36
2813                         else
2814                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
2815                 }
2816                 else
2817                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
2818         }
2819         else
2820         {
2821                 if (size[0] < 3)
2822                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
2823                 else if (size[0] <= 32)
2824                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
2825                 else
2826                         hull = &cmodel->brushq1.hulls[2]; // 64x64x88
2827         }
2828         VectorCopy(inmins, outmins);
2829         VectorAdd(inmins, hull->clip_size, outmaxs);
2830 }
2831
2832 /*
2833 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)
2834 {
2835         mleaf_t *leaf;
2836         for (;;)
2837         {
2838                 if (!BoxesOverlap(node->mins, node->maxs, mins, maxs))
2839                         return;
2840                 if (!node->plane)
2841                         break;
2842                 Mod_Q1BSP_RecursiveGetVisible(node->children[0], model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces, pvs);
2843                 node = node->children[1];
2844         }
2845         leaf = (mleaf_t *)node;
2846         if ((pvs == NULL || CHECKPVSBIT(pvs, leaf->clusterindex)))
2847         {
2848                 int leaffacenum;
2849                 msurface_t *surf;
2850                 if (maxleafs && *numleafs < maxleafs)
2851                         leaflist[(*numleafs)++] = leaf;
2852                 if (maxsurfaces)
2853                 {
2854                         for (leaffacenum = 0;leaffacenum < leaf->numleaffaces;leaffacenum++)
2855                         {
2856                                 surf = model->brushq1.surfaces + leaf->firstleafface[leaffacenum];
2857                                 if (surf->shadowmark != shadowmarkcount)
2858                                 {
2859                                         surf->shadowmark = shadowmarkcount;
2860                                         if (BoxesOverlap(mins, maxs, surf->mins, surf->maxs) && ((surf->flags & SURF_PLANEBACK) ? PlaneDiff(point, surf->plane) < 0 : PlaneDiff(point, surf->plane) > 0) && *numsurfaces < maxsurfaces)
2861                                                 surfacelist[(*numsurfaces)++] = surf;
2862                                 }
2863                         }
2864                 }
2865         }
2866 }
2867
2868 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)
2869 {
2870         // FIXME: support portals
2871         if (maxsurfaces)
2872                 *numsurfaces = 0;
2873         if (maxleafs)
2874                 *numleafs = 0;
2875         pvs = ent->model->brush.GetPVS(ent->model, relativelightorigin);
2876         Mod_Q1BSP_RecursiveGetVisible(ent->model->brush.data_nodes + ent->model->brushq1.firstclipnode, model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces);
2877 }
2878 */
2879
2880 extern void R_Q1BSP_DrawSky(entity_render_t *ent);
2881 extern void R_Q1BSP_Draw(entity_render_t *ent);
2882 extern void R_Q1BSP_GetLightInfo(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, vec3_t outmins, vec3_t outmaxs, int *outclusterlist, qbyte *outclusterpvs, int *outnumclusterspointer, int *outsurfacelist, qbyte *outsurfacepvs, int *outnumsurfacespointer);
2883 extern void R_Q1BSP_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, int numsurfaces, const int *surfacelist);
2884 extern void R_Q1BSP_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, vec_t ambientscale, vec_t diffusescale, vec_t specularscale, int numsurfaces, const int *surfacelist);
2885 void Mod_Q1BSP_Load(model_t *mod, void *buffer)
2886 {
2887         int i, j, k;
2888         dheader_t *header;
2889         dmodel_t *bm;
2890         mempool_t *mainmempool;
2891         float dist, modelyawradius, modelradius, *vec;
2892         msurface_t *surf;
2893         int numshadowmeshtriangles;
2894
2895         mod->type = mod_brushq1;
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
2917         if (loadmodel->isworldmodel)
2918                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
2919
2920 // swap all the lumps
2921         mod_base = (qbyte *)header;
2922
2923         header->version = LittleLong(header->version);
2924         for (i = 0;i < HEADER_LUMPS;i++)
2925         {
2926                 header->lumps[i].fileofs = LittleLong(header->lumps[i].fileofs);
2927                 header->lumps[i].filelen = LittleLong(header->lumps[i].filelen);
2928         }
2929
2930 // load into heap
2931
2932         // store which lightmap format to use
2933         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
2934
2935         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
2936         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
2937         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
2938         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
2939         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
2940         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
2941         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
2942         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
2943         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
2944         Mod_Q1BSP_LoadLeaffaces(&header->lumps[LUMP_MARKSURFACES]);
2945         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
2946         // load submodels before leafs because they contain the number of vis leafs
2947         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS]);
2948         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
2949         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
2950         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES]);
2951
2952         if (!mod->brushq1.lightdata)
2953                 mod->brush.LightPoint = NULL;
2954
2955         if (mod->brushq1.data_compressedpvs)
2956                 Mem_Free(mod->brushq1.data_compressedpvs);
2957         mod->brushq1.data_compressedpvs = NULL;
2958         mod->brushq1.num_compressedpvs = 0;
2959
2960         Mod_Q1BSP_MakeHull0();
2961         Mod_Q1BSP_MakePortals();
2962
2963         mod->numframes = 2;             // regular and alternate animation
2964         mod->numskins = 1;
2965
2966         mainmempool = mod->mempool;
2967
2968         Mod_Q1BSP_LoadLightList();
2969
2970         // make a single combined shadow mesh to allow optimized shadow volume creation
2971         numshadowmeshtriangles = 0;
2972         for (j = 0, surf = loadmodel->brushq1.surfaces;j < loadmodel->brushq1.numsurfaces;j++, surf++)
2973         {
2974                 surf->num_firstshadowmeshtriangle = numshadowmeshtriangles;
2975                 numshadowmeshtriangles += surf->mesh.num_triangles;
2976         }
2977         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Begin(loadmodel->mempool, numshadowmeshtriangles * 3, numshadowmeshtriangles, NULL, NULL, NULL, false, false, true);
2978         for (j = 0, surf = loadmodel->brushq1.surfaces;j < loadmodel->brushq1.numsurfaces;j++, surf++)
2979                 Mod_ShadowMesh_AddMesh(loadmodel->mempool, loadmodel->brush.shadowmesh, NULL, NULL, NULL, surf->mesh.data_vertex3f, NULL, NULL, NULL, NULL, surf->mesh.num_triangles, surf->mesh.data_element3i);
2980         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Finish(loadmodel->mempool, loadmodel->brush.shadowmesh, false, true);
2981         Mod_BuildTriangleNeighbors(loadmodel->brush.shadowmesh->neighbor3i, loadmodel->brush.shadowmesh->element3i, loadmodel->brush.shadowmesh->numtriangles);
2982
2983         if (loadmodel->brush.numsubmodels)
2984                 loadmodel->brush.submodels = Mem_Alloc(loadmodel->mempool, loadmodel->brush.numsubmodels * sizeof(model_t *));
2985
2986         // LordHavoc: to clear the fog around the original quake submodel code, I
2987         // will explain:
2988         // first of all, some background info on the submodels:
2989         // model 0 is the map model (the world, named maps/e1m1.bsp for example)
2990         // model 1 and higher are submodels (doors and the like, named *1, *2, etc)
2991         // now the weird for loop itself:
2992         // the loop functions in an odd way, on each iteration it sets up the
2993         // current 'mod' model (which despite the confusing code IS the model of
2994         // the number i), at the end of the loop it duplicates the model to become
2995         // the next submodel, and loops back to set up the new submodel.
2996
2997         // LordHavoc: now the explanation of my sane way (which works identically):
2998         // set up the world model, then on each submodel copy from the world model
2999         // and set up the submodel with the respective model info.
3000         for (i = 0;i < mod->brush.numsubmodels;i++)
3001         {
3002                 // LordHavoc: this code was originally at the end of this loop, but
3003                 // has been transformed to something more readable at the start here.
3004
3005                 if (i > 0)
3006                 {
3007                         char name[10];
3008                         // LordHavoc: only register submodels if it is the world
3009                         // (prevents external bsp models from replacing world submodels with
3010                         //  their own)
3011                         if (!loadmodel->isworldmodel)
3012                                 continue;
3013                         // duplicate the basic information
3014                         sprintf(name, "*%i", i);
3015                         mod = Mod_FindName(name);
3016                         // copy the base model to this one
3017                         *mod = *loadmodel;
3018                         // rename the clone back to its proper name
3019                         strcpy(mod->name, name);
3020                         // textures and memory belong to the main model
3021                         mod->texturepool = NULL;
3022                         mod->mempool = NULL;
3023                 }
3024
3025                 mod->brush.submodel = i;
3026
3027                 if (loadmodel->brush.submodels)
3028                         loadmodel->brush.submodels[i] = mod;
3029
3030                 bm = &mod->brushq1.submodels[i];
3031
3032                 mod->brushq1.hulls[0].firstclipnode = bm->headnode[0];
3033                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
3034                 {
3035                         mod->brushq1.hulls[j].firstclipnode = bm->headnode[j];
3036                         mod->brushq1.hulls[j].lastclipnode = mod->brushq1.numclipnodes - 1;
3037                 }
3038
3039                 mod->firstmodelsurface = bm->firstface;
3040                 mod->nummodelsurfaces = bm->numfaces;
3041
3042                 // make the model surface list (used by shadowing/lighting)
3043                 mod->surfacelist = Mem_Alloc(loadmodel->mempool, mod->nummodelsurfaces * sizeof(*mod->surfacelist));
3044                 for (j = 0;j < mod->nummodelsurfaces;j++)
3045                         mod->surfacelist[j] = mod->firstmodelsurface + j;
3046
3047                 // this gets altered below if sky is used
3048                 mod->DrawSky = NULL;
3049                 mod->Draw = R_Q1BSP_Draw;
3050                 mod->GetLightInfo = R_Q1BSP_GetLightInfo;
3051                 mod->DrawShadowVolume = R_Q1BSP_DrawShadowVolume;
3052                 mod->DrawLight = R_Q1BSP_DrawLight;
3053                 if (i != 0)
3054                 {
3055                         mod->brush.GetPVS = NULL;
3056                         mod->brush.FatPVS = NULL;
3057                         mod->brush.BoxTouchingPVS = NULL;
3058                         mod->brush.LightPoint = NULL;
3059                         mod->brush.AmbientSoundLevelsForPoint = NULL;
3060                 }
3061                 Mod_Q1BSP_BuildLightmapUpdateChains(loadmodel->mempool, mod);
3062                 if (mod->nummodelsurfaces)
3063                 {
3064                         // LordHavoc: calculate bmodel bounding box rather than trusting what it says
3065                         mod->normalmins[0] = mod->normalmins[1] = mod->normalmins[2] = 1000000000.0f;
3066                         mod->normalmaxs[0] = mod->normalmaxs[1] = mod->normalmaxs[2] = -1000000000.0f;
3067                         modelyawradius = 0;
3068                         modelradius = 0;
3069                         for (j = 0, surf = &mod->brushq1.surfaces[mod->firstmodelsurface];j < mod->nummodelsurfaces;j++, surf++)
3070                         {
3071                                 // we only need to have a drawsky function if it is used(usually only on world model)
3072                                 if (surf->texinfo->texture->flags & SURF_DRAWSKY)
3073                                         mod->DrawSky = R_Q1BSP_DrawSky;
3074                                 // LordHavoc: submodels always clip, even if water
3075                                 if (mod->brush.numsubmodels - 1)
3076                                         surf->flags |= SURF_SOLIDCLIP;
3077                                 // calculate bounding shapes
3078                                 for (k = 0, vec = surf->mesh.data_vertex3f;k < surf->mesh.num_vertices;k++, vec += 3)
3079                                 {
3080                                         if (mod->normalmins[0] > vec[0]) mod->normalmins[0] = vec[0];
3081                                         if (mod->normalmins[1] > vec[1]) mod->normalmins[1] = vec[1];
3082                                         if (mod->normalmins[2] > vec[2]) mod->normalmins[2] = vec[2];
3083                                         if (mod->normalmaxs[0] < vec[0]) mod->normalmaxs[0] = vec[0];
3084                                         if (mod->normalmaxs[1] < vec[1]) mod->normalmaxs[1] = vec[1];
3085                                         if (mod->normalmaxs[2] < vec[2]) mod->normalmaxs[2] = vec[2];
3086                                         dist = vec[0]*vec[0]+vec[1]*vec[1];
3087                                         if (modelyawradius < dist)
3088                                                 modelyawradius = dist;
3089                                         dist += vec[2]*vec[2];
3090                                         if (modelradius < dist)
3091                                                 modelradius = dist;
3092                                 }
3093                         }
3094                         modelyawradius = sqrt(modelyawradius);
3095                         modelradius = sqrt(modelradius);
3096                         mod->yawmins[0] = mod->yawmins[1] = - (mod->yawmaxs[0] = mod->yawmaxs[1] = modelyawradius);
3097                         mod->yawmins[2] = mod->normalmins[2];
3098                         mod->yawmaxs[2] = mod->normalmaxs[2];
3099                         mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
3100                         mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
3101                         mod->radius = modelradius;
3102                         mod->radius2 = modelradius * modelradius;
3103                 }
3104                 else
3105                 {
3106                         // LordHavoc: empty submodel(lacrima.bsp has such a glitch)
3107                         Con_Printf("warning: empty submodel *%i in %s\n", i+1, loadmodel->name);
3108                 }
3109                 //mod->brushq1.num_visleafs = bm->visleafs;
3110         }
3111
3112         Mod_Q1BSP_LoadMapBrushes();
3113
3114         //Mod_Q1BSP_ProcessLightList();
3115
3116         if (developer.integer)
3117                 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->brush.num_nodes, loadmodel->brush.num_leafs, mod->brushq1.submodels[i].visleafs, loadmodel->brush.num_portals);
3118 }
3119
3120 static void Mod_Q2BSP_LoadEntities(lump_t *l)
3121 {
3122 }
3123
3124 static void Mod_Q2BSP_LoadPlanes(lump_t *l)
3125 {
3126 /*
3127         d_t *in;
3128         m_t *out;
3129         int i, count;
3130
3131         in = (void *)(mod_base + l->fileofs);
3132         if (l->filelen % sizeof(*in))
3133                 Host_Error("Mod_Q2BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3134         count = l->filelen / sizeof(*in);
3135         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3136
3137         loadmodel-> = out;
3138         loadmodel->num = count;
3139
3140         for (i = 0;i < count;i++, in++, out++)
3141         {
3142         }
3143 */
3144 }
3145
3146 static void Mod_Q2BSP_LoadVertices(lump_t *l)
3147 {
3148 /*
3149         d_t *in;
3150         m_t *out;
3151         int i, count;
3152
3153         in = (void *)(mod_base + l->fileofs);
3154         if (l->filelen % sizeof(*in))
3155                 Host_Error("Mod_Q2BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3156         count = l->filelen / sizeof(*in);
3157         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3158
3159         loadmodel-> = out;
3160         loadmodel->num = count;
3161
3162         for (i = 0;i < count;i++, in++, out++)
3163         {
3164         }
3165 */
3166 }
3167
3168 static void Mod_Q2BSP_LoadVisibility(lump_t *l)
3169 {
3170 /*
3171         d_t *in;
3172         m_t *out;
3173         int i, count;
3174
3175         in = (void *)(mod_base + l->fileofs);
3176         if (l->filelen % sizeof(*in))
3177                 Host_Error("Mod_Q2BSP_LoadVisibility: funny lump size in %s",loadmodel->name);
3178         count = l->filelen / sizeof(*in);
3179         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3180
3181         loadmodel-> = out;
3182         loadmodel->num = count;
3183
3184         for (i = 0;i < count;i++, in++, out++)
3185         {
3186         }
3187 */
3188 }
3189
3190 static void Mod_Q2BSP_LoadNodes(lump_t *l)
3191 {
3192 /*
3193         d_t *in;
3194         m_t *out;
3195         int i, count;
3196
3197         in = (void *)(mod_base + l->fileofs);
3198         if (l->filelen % sizeof(*in))
3199                 Host_Error("Mod_Q2BSP_LoadNodes: funny lump size in %s",loadmodel->name);
3200         count = l->filelen / sizeof(*in);
3201         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3202
3203         loadmodel-> = out;
3204         loadmodel->num = count;
3205
3206         for (i = 0;i < count;i++, in++, out++)
3207         {
3208         }
3209 */
3210 }
3211
3212 static void Mod_Q2BSP_LoadTexInfo(lump_t *l)
3213 {
3214 /*
3215         d_t *in;
3216         m_t *out;
3217         int i, count;
3218
3219         in = (void *)(mod_base + l->fileofs);
3220         if (l->filelen % sizeof(*in))
3221                 Host_Error("Mod_Q2BSP_LoadTexInfo: funny lump size in %s",loadmodel->name);
3222         count = l->filelen / sizeof(*in);
3223         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3224
3225         loadmodel-> = out;
3226         loadmodel->num = count;
3227
3228         for (i = 0;i < count;i++, in++, out++)
3229         {
3230         }
3231 */
3232 }
3233
3234 static void Mod_Q2BSP_LoadFaces(lump_t *l)
3235 {
3236 /*
3237         d_t *in;
3238         m_t *out;
3239         int i, count;
3240
3241         in = (void *)(mod_base + l->fileofs);
3242         if (l->filelen % sizeof(*in))
3243                 Host_Error("Mod_Q2BSP_LoadFaces: funny lump size in %s",loadmodel->name);
3244         count = l->filelen / sizeof(*in);
3245         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3246
3247         loadmodel-> = out;
3248         loadmodel->num = count;
3249
3250         for (i = 0;i < count;i++, in++, out++)
3251         {
3252         }
3253 */
3254 }
3255
3256 static void Mod_Q2BSP_LoadLighting(lump_t *l)
3257 {
3258 /*
3259         d_t *in;
3260         m_t *out;
3261         int i, count;
3262
3263         in = (void *)(mod_base + l->fileofs);
3264         if (l->filelen % sizeof(*in))
3265                 Host_Error("Mod_Q2BSP_LoadLighting: funny lump size in %s",loadmodel->name);
3266         count = l->filelen / sizeof(*in);
3267         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3268
3269         loadmodel-> = out;
3270         loadmodel->num = count;
3271
3272         for (i = 0;i < count;i++, in++, out++)
3273         {
3274         }
3275 */
3276 }
3277
3278 static void Mod_Q2BSP_LoadLeafs(lump_t *l)
3279 {
3280 /*
3281         d_t *in;
3282         m_t *out;
3283         int i, count;
3284
3285         in = (void *)(mod_base + l->fileofs);
3286         if (l->filelen % sizeof(*in))
3287                 Host_Error("Mod_Q2BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
3288         count = l->filelen / sizeof(*in);
3289         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3290
3291         loadmodel-> = out;
3292         loadmodel->num = count;
3293
3294         for (i = 0;i < count;i++, in++, out++)
3295         {
3296         }
3297 */
3298 }
3299
3300 static void Mod_Q2BSP_LoadLeafFaces(lump_t *l)
3301 {
3302 /*
3303         d_t *in;
3304         m_t *out;
3305         int i, count;
3306
3307         in = (void *)(mod_base + l->fileofs);
3308         if (l->filelen % sizeof(*in))
3309                 Host_Error("Mod_Q2BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
3310         count = l->filelen / sizeof(*in);
3311         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3312
3313         loadmodel-> = out;
3314         loadmodel->num = count;
3315
3316         for (i = 0;i < count;i++, in++, out++)
3317         {
3318         }
3319 */
3320 }
3321
3322 static void Mod_Q2BSP_LoadLeafBrushes(lump_t *l)
3323 {
3324 /*
3325         d_t *in;
3326         m_t *out;
3327         int i, count;
3328
3329         in = (void *)(mod_base + l->fileofs);
3330         if (l->filelen % sizeof(*in))
3331                 Host_Error("Mod_Q2BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
3332         count = l->filelen / sizeof(*in);
3333         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3334
3335         loadmodel-> = out;
3336         loadmodel->num = count;
3337
3338         for (i = 0;i < count;i++, in++, out++)
3339         {
3340         }
3341 */
3342 }
3343
3344 static void Mod_Q2BSP_LoadEdges(lump_t *l)
3345 {
3346 /*
3347         d_t *in;
3348         m_t *out;
3349         int i, count;
3350
3351         in = (void *)(mod_base + l->fileofs);
3352         if (l->filelen % sizeof(*in))
3353                 Host_Error("Mod_Q2BSP_LoadEdges: funny lump size in %s",loadmodel->name);
3354         count = l->filelen / sizeof(*in);
3355         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3356
3357         loadmodel-> = out;
3358         loadmodel->num = count;
3359
3360         for (i = 0;i < count;i++, in++, out++)
3361         {
3362         }
3363 */
3364 }
3365
3366 static void Mod_Q2BSP_LoadSurfEdges(lump_t *l)
3367 {
3368 /*
3369         d_t *in;
3370         m_t *out;
3371         int i, count;
3372
3373         in = (void *)(mod_base + l->fileofs);
3374         if (l->filelen % sizeof(*in))
3375                 Host_Error("Mod_Q2BSP_LoadSurfEdges: funny lump size in %s",loadmodel->name);
3376         count = l->filelen / sizeof(*in);
3377         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3378
3379         loadmodel-> = out;
3380         loadmodel->num = count;
3381
3382         for (i = 0;i < count;i++, in++, out++)
3383         {
3384         }
3385 */
3386 }
3387
3388 static void Mod_Q2BSP_LoadBrushes(lump_t *l)
3389 {
3390 /*
3391         d_t *in;
3392         m_t *out;
3393         int i, count;
3394
3395         in = (void *)(mod_base + l->fileofs);
3396         if (l->filelen % sizeof(*in))
3397                 Host_Error("Mod_Q2BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3398         count = l->filelen / sizeof(*in);
3399         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3400
3401         loadmodel-> = out;
3402         loadmodel->num = count;
3403
3404         for (i = 0;i < count;i++, in++, out++)
3405         {
3406         }
3407 */
3408 }
3409
3410 static void Mod_Q2BSP_LoadBrushSides(lump_t *l)
3411 {
3412 /*
3413         d_t *in;
3414         m_t *out;
3415         int i, count;
3416
3417         in = (void *)(mod_base + l->fileofs);
3418         if (l->filelen % sizeof(*in))
3419                 Host_Error("Mod_Q2BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3420         count = l->filelen / sizeof(*in);
3421         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3422
3423         loadmodel-> = out;
3424         loadmodel->num = count;
3425
3426         for (i = 0;i < count;i++, in++, out++)
3427         {
3428         }
3429 */
3430 }
3431
3432 static void Mod_Q2BSP_LoadAreas(lump_t *l)
3433 {
3434 /*
3435         d_t *in;
3436         m_t *out;
3437         int i, count;
3438
3439         in = (void *)(mod_base + l->fileofs);
3440         if (l->filelen % sizeof(*in))
3441                 Host_Error("Mod_Q2BSP_LoadAreas: funny lump size in %s",loadmodel->name);
3442         count = l->filelen / sizeof(*in);
3443         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3444
3445         loadmodel-> = out;
3446         loadmodel->num = count;
3447
3448         for (i = 0;i < count;i++, in++, out++)
3449         {
3450         }
3451 */
3452 }
3453
3454 static void Mod_Q2BSP_LoadAreaPortals(lump_t *l)
3455 {
3456 /*
3457         d_t *in;
3458         m_t *out;
3459         int i, count;
3460
3461         in = (void *)(mod_base + l->fileofs);
3462         if (l->filelen % sizeof(*in))
3463                 Host_Error("Mod_Q2BSP_LoadAreaPortals: funny lump size in %s",loadmodel->name);
3464         count = l->filelen / sizeof(*in);
3465         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3466
3467         loadmodel-> = out;
3468         loadmodel->num = count;
3469
3470         for (i = 0;i < count;i++, in++, out++)
3471         {
3472         }
3473 */
3474 }
3475
3476 static void Mod_Q2BSP_LoadModels(lump_t *l)
3477 {
3478 /*
3479         d_t *in;
3480         m_t *out;
3481         int i, count;
3482
3483         in = (void *)(mod_base + l->fileofs);
3484         if (l->filelen % sizeof(*in))
3485                 Host_Error("Mod_Q2BSP_LoadModels: funny lump size in %s",loadmodel->name);
3486         count = l->filelen / sizeof(*in);
3487         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3488
3489         loadmodel-> = out;
3490         loadmodel->num = count;
3491
3492         for (i = 0;i < count;i++, in++, out++)
3493         {
3494         }
3495 */
3496 }
3497
3498 void static Mod_Q2BSP_Load(model_t *mod, void *buffer)
3499 {
3500         int i;
3501         q2dheader_t *header;
3502
3503         Host_Error("Mod_Q2BSP_Load: not yet implemented\n");
3504
3505         mod->type = mod_brushq2;
3506
3507         header = (q2dheader_t *)buffer;
3508
3509         i = LittleLong(header->version);
3510         if (i != Q2BSPVERSION)
3511                 Host_Error("Mod_Q2BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q2BSPVERSION);
3512         mod->brush.ishlbsp = false;
3513         if (loadmodel->isworldmodel)
3514                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
3515
3516         mod_base = (qbyte *)header;
3517
3518         // swap all the lumps
3519         for (i = 0;i < (int) sizeof(*header) / 4;i++)
3520                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
3521
3522         // store which lightmap format to use
3523         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3524
3525         Mod_Q2BSP_LoadEntities(&header->lumps[Q2LUMP_ENTITIES]);
3526         Mod_Q2BSP_LoadPlanes(&header->lumps[Q2LUMP_PLANES]);
3527         Mod_Q2BSP_LoadVertices(&header->lumps[Q2LUMP_VERTEXES]);
3528         Mod_Q2BSP_LoadVisibility(&header->lumps[Q2LUMP_VISIBILITY]);
3529         Mod_Q2BSP_LoadNodes(&header->lumps[Q2LUMP_NODES]);
3530         Mod_Q2BSP_LoadTexInfo(&header->lumps[Q2LUMP_TEXINFO]);
3531         Mod_Q2BSP_LoadFaces(&header->lumps[Q2LUMP_FACES]);
3532         Mod_Q2BSP_LoadLighting(&header->lumps[Q2LUMP_LIGHTING]);
3533         Mod_Q2BSP_LoadLeafs(&header->lumps[Q2LUMP_LEAFS]);
3534         Mod_Q2BSP_LoadLeafFaces(&header->lumps[Q2LUMP_LEAFFACES]);
3535         Mod_Q2BSP_LoadLeafBrushes(&header->lumps[Q2LUMP_LEAFBRUSHES]);
3536         Mod_Q2BSP_LoadEdges(&header->lumps[Q2LUMP_EDGES]);
3537         Mod_Q2BSP_LoadSurfEdges(&header->lumps[Q2LUMP_SURFEDGES]);
3538         Mod_Q2BSP_LoadBrushes(&header->lumps[Q2LUMP_BRUSHES]);
3539         Mod_Q2BSP_LoadBrushSides(&header->lumps[Q2LUMP_BRUSHSIDES]);
3540         Mod_Q2BSP_LoadAreas(&header->lumps[Q2LUMP_AREAS]);
3541         Mod_Q2BSP_LoadAreaPortals(&header->lumps[Q2LUMP_AREAPORTALS]);
3542         // LordHavoc: must go last because this makes the submodels
3543         Mod_Q2BSP_LoadModels(&header->lumps[Q2LUMP_MODELS]);
3544 }
3545
3546 static int Mod_Q3BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents);
3547 static int Mod_Q3BSP_NativeContentsFromSuperContents(model_t *model, int supercontents);
3548
3549 static void Mod_Q3BSP_LoadEntities(lump_t *l)
3550 {
3551         const char *data;
3552         char key[128], value[4096];
3553         float v[3];
3554         loadmodel->brushq3.num_lightgrid_cellsize[0] = 64;
3555         loadmodel->brushq3.num_lightgrid_cellsize[1] = 64;
3556         loadmodel->brushq3.num_lightgrid_cellsize[2] = 128;
3557         if (!l->filelen)
3558                 return;
3559         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
3560         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
3561         data = loadmodel->brush.entities;
3562         // some Q3 maps override the lightgrid_cellsize with a worldspawn key
3563         if (data && COM_ParseToken(&data, false) && com_token[0] == '{')
3564         {
3565                 while (1)
3566                 {
3567                         if (!COM_ParseToken(&data, false))
3568                                 break; // error
3569                         if (com_token[0] == '}')
3570                                 break; // end of worldspawn
3571                         if (com_token[0] == '_')
3572                                 strcpy(key, com_token + 1);
3573                         else
3574                                 strcpy(key, com_token);
3575                         while (key[strlen(key)-1] == ' ') // remove trailing spaces
3576                                 key[strlen(key)-1] = 0;
3577                         if (!COM_ParseToken(&data, false))
3578                                 break; // error
3579                         strcpy(value, com_token);
3580                         if (!strcmp("gridsize", key))
3581                         {
3582                                 if (sscanf(value, "%f %f %f", &v[0], &v[1], &v[2]) == 3 && v[0] != 0 && v[1] != 0 && v[2] != 0)
3583                                         VectorCopy(v, loadmodel->brushq3.num_lightgrid_cellsize);
3584                         }
3585                 }
3586         }
3587 }
3588
3589 static void Mod_Q3BSP_LoadTextures(lump_t *l)
3590 {
3591         q3dtexture_t *in;
3592         texture_t *out;
3593         int i, count;
3594         int j, c;
3595         fssearch_t *search;
3596         char *f;
3597         const char *text;
3598         int flags, flags2, numparameters, passnumber;
3599         char shadername[Q3PATHLENGTH];
3600         char sky[Q3PATHLENGTH];
3601         char firstpasstexturename[Q3PATHLENGTH];
3602         char parameter[4][Q3PATHLENGTH];
3603
3604         in = (void *)(mod_base + l->fileofs);
3605         if (l->filelen % sizeof(*in))
3606                 Host_Error("Mod_Q3BSP_LoadTextures: funny lump size in %s",loadmodel->name);
3607         count = l->filelen / sizeof(*in);
3608         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3609
3610         loadmodel->brush.data_textures = out;
3611         loadmodel->brush.num_textures = count;
3612
3613         for (i = 0;i < count;i++, in++, out++)
3614         {
3615                 strlcpy (out->name, in->name, sizeof (out->name));
3616                 out->surfaceflags = LittleLong(in->surfaceflags);
3617                 out->supercontents = Mod_Q3BSP_SuperContentsFromNativeContents(loadmodel, LittleLong(in->contents));
3618                 out->surfaceparms = -1;
3619         }
3620
3621         // do a quick parse of shader files to get surfaceparms
3622         if ((search = FS_Search("scripts/*.shader", true, false)))
3623         {
3624                 for (i = 0;i < search->numfilenames;i++)
3625                 {
3626                         if ((f = FS_LoadFile(search->filenames[i], tempmempool, false)))
3627                         {
3628                                 text = f;
3629                                 while (COM_ParseToken(&text, false))
3630                                 {
3631                                         strlcpy (shadername, com_token, sizeof (shadername));
3632                                         flags = 0;
3633                                         flags2 = 0;
3634                                         sky[0] = 0;
3635                                         passnumber = 0;
3636                                         firstpasstexturename[0] = 0;
3637                                         if (COM_ParseToken(&text, false) && !strcasecmp(com_token, "{"))
3638                                         {
3639                                                 while (COM_ParseToken(&text, false))
3640                                                 {
3641                                                         if (!strcasecmp(com_token, "}"))
3642                                                                 break;
3643                                                         else if (!strcasecmp(com_token, "{"))
3644                                                         {
3645                                                                 while (COM_ParseToken(&text, false))
3646                                                                 {
3647                                                                         if (!strcasecmp(com_token, "}"))
3648                                                                                 break;
3649                                                                         if (!strcasecmp(com_token, "\n"))
3650                                                                                 continue;
3651                                                                         numparameters = 0;
3652                                                                         for (j = 0;strcasecmp(com_token, "\n") && strcasecmp(com_token, "}");j++)
3653                                                                         {
3654                                                                                 if (j < 4)
3655                                                                                 {
3656                                                                                         strlcpy(parameter[j], com_token, sizeof(parameter[j]));
3657                                                                                         numparameters = j + 1;
3658                                                                                 }
3659                                                                                 if (!COM_ParseToken(&text, true))
3660                                                                                         break;
3661                                                                         }
3662                                                                         if (developer.integer >= 2)
3663                                                                         {
3664                                                                                 Con_Printf("%s %i: ", shadername, passnumber);
3665                                                                                 for (j = 0;j < numparameters;j++)
3666                                                                                         Con_Printf(" %s", parameter[j]);
3667                                                                                 Con_Print("\n");
3668                                                                         }
3669                                                                         if (passnumber == 0 && numparameters >= 1)
3670                                                                         {
3671                                                                                 if (!strcasecmp(parameter[0], "blendfunc"))
3672                                                                                 {
3673                                                                                         if (numparameters == 2 && !strcasecmp(parameter[1], "add"))
3674                                                                                                 flags2 |= Q3TEXTUREFLAG_ADDITIVE;
3675                                                                                         else if (numparameters == 3 && !strcasecmp(parameter[1], "gl_one") && !strcasecmp(parameter[2], "gl_one"))
3676                                                                                                 flags2 |= Q3TEXTUREFLAG_ADDITIVE;
3677                                                                                         else if (numparameters == 3 && !strcasecmp(parameter[1], "gl_src_alpha") && !strcasecmp(parameter[2], "gl_one"))
3678                                                                                                 flags2 |= Q3TEXTUREFLAG_ADDITIVE;
3679                                                                                 }
3680                                                                                 else if (numparameters >= 2 && (!strcasecmp(parameter[0], "map") || !strcasecmp(parameter[0], "clampmap")))
3681                                                                                         strlcpy(firstpasstexturename, parameter[1], sizeof(firstpasstexturename));
3682                                                                                 else if (numparameters >= 3 && !strcasecmp(parameter[0], "animmap"))
3683                                                                                         strlcpy(firstpasstexturename, parameter[2], sizeof(firstpasstexturename));
3684                                                                         }
3685                                                                         if (!strcasecmp(parameter[0], "alphafunc"))
3686                                                                                 flags2 |= Q3TEXTUREFLAG_ALPHATEST;
3687                                                                         // break out a level if it was }
3688                                                                         if (!strcasecmp(com_token, "}"))
3689                                                                                 break;
3690                                                                 }
3691                                                                 passnumber++;
3692                                                                 continue;
3693                                                         }
3694                                                         numparameters = 0;
3695                                                         for (j = 0;strcasecmp(com_token, "\n") && strcasecmp(com_token, "}");j++)
3696                                                         {
3697                                                                 if (j < 4)
3698                                                                 {
3699                                                                         strlcpy(parameter[j], com_token, sizeof(parameter[j]));
3700                                                                         numparameters = j + 1;
3701                                                                 }
3702                                                                 if (!COM_ParseToken(&text, true))
3703                                                                         break;
3704                                                         }
3705                                                         if (i == 0 && !strcasecmp(com_token, "}"))
3706                                                                 break;
3707                                                         if (developer.integer >= 2)
3708                                                         {
3709                                                                 Con_Printf("%s: ", shadername);
3710                                                                 for (j = 0;j < numparameters;j++)
3711                                                                         Con_Printf(" %s", parameter[j]);
3712                                                                 Con_Print("\n");
3713                                                         }
3714                                                         if (numparameters < 1)
3715                                                                 continue;
3716                                                         if (!strcasecmp(parameter[0], "surfaceparm") && numparameters >= 2)
3717                                                         {
3718                                                                 if (!strcasecmp(parameter[1], "alphashadow"))
3719                                                                         flags |= Q3SURFACEPARM_ALPHASHADOW;
3720                                                                 else if (!strcasecmp(parameter[1], "areaportal"))
3721                                                                         flags |= Q3SURFACEPARM_AREAPORTAL;
3722                                                                 else if (!strcasecmp(parameter[1], "clusterportal"))
3723                                                                         flags |= Q3SURFACEPARM_CLUSTERPORTAL;
3724                                                                 else if (!strcasecmp(parameter[1], "detail"))
3725                                                                         flags |= Q3SURFACEPARM_DETAIL;
3726                                                                 else if (!strcasecmp(parameter[1], "donotenter"))
3727                                                                         flags |= Q3SURFACEPARM_DONOTENTER;
3728                                                                 else if (!strcasecmp(parameter[1], "fog"))
3729                                                                         flags |= Q3SURFACEPARM_FOG;
3730                                                                 else if (!strcasecmp(parameter[1], "lava"))
3731                                                                         flags |= Q3SURFACEPARM_LAVA;
3732                                                                 else if (!strcasecmp(parameter[1], "lightfilter"))
3733                                                                         flags |= Q3SURFACEPARM_LIGHTFILTER;
3734                                                                 else if (!strcasecmp(parameter[1], "metalsteps"))
3735                                                                         flags |= Q3SURFACEPARM_METALSTEPS;
3736                                                                 else if (!strcasecmp(parameter[1], "nodamage"))
3737                                                                         flags |= Q3SURFACEPARM_NODAMAGE;
3738                                                                 else if (!strcasecmp(parameter[1], "nodlight"))
3739                                                                         flags |= Q3SURFACEPARM_NODLIGHT;
3740                                                                 else if (!strcasecmp(parameter[1], "nodraw"))
3741                                                                         flags |= Q3SURFACEPARM_NODRAW;
3742                                                                 else if (!strcasecmp(parameter[1], "nodrop"))
3743                                                                         flags |= Q3SURFACEPARM_NODROP;
3744                                                                 else if (!strcasecmp(parameter[1], "noimpact"))
3745                                                                         flags |= Q3SURFACEPARM_NOIMPACT;
3746                                                                 else if (!strcasecmp(parameter[1], "nolightmap"))
3747                                                                         flags |= Q3SURFACEPARM_NOLIGHTMAP;
3748                                                                 else if (!strcasecmp(parameter[1], "nomarks"))
3749                                                                         flags |= Q3SURFACEPARM_NOMARKS;
3750                                                                 else if (!strcasecmp(parameter[1], "nomipmaps"))
3751                                                                         flags |= Q3SURFACEPARM_NOMIPMAPS;
3752                                                                 else if (!strcasecmp(parameter[1], "nonsolid"))
3753                                                                         flags |= Q3SURFACEPARM_NONSOLID;
3754                                                                 else if (!strcasecmp(parameter[1], "origin"))
3755                                                                         flags |= Q3SURFACEPARM_ORIGIN;
3756                                                                 else if (!strcasecmp(parameter[1], "playerclip"))
3757                                                                         flags |= Q3SURFACEPARM_PLAYERCLIP;
3758                                                                 else if (!strcasecmp(parameter[1], "sky"))
3759                                                                         flags |= Q3SURFACEPARM_SKY;
3760                                                                 else if (!strcasecmp(parameter[1], "slick"))
3761                                                                         flags |= Q3SURFACEPARM_SLICK;
3762                                                                 else if (!strcasecmp(parameter[1], "slime"))
3763                                                                         flags |= Q3SURFACEPARM_SLIME;
3764                                                                 else if (!strcasecmp(parameter[1], "structural"))
3765                                                                         flags |= Q3SURFACEPARM_STRUCTURAL;
3766                                                                 else if (!strcasecmp(parameter[1], "trans"))
3767                                                                         flags |= Q3SURFACEPARM_TRANS;
3768                                                                 else if (!strcasecmp(parameter[1], "water"))
3769                                                                         flags |= Q3SURFACEPARM_WATER;
3770                                                                 else if (!strcasecmp(parameter[1], "pointlight"))
3771                                                                         flags |= Q3SURFACEPARM_POINTLIGHT;
3772                                                                 else
3773                                                                         Con_Printf("%s parsing warning: unknown surfaceparm \"%s\"\n", search->filenames[i], parameter[1]);
3774                                                         }
3775                                                         else if (!strcasecmp(parameter[0], "sky") && numparameters >= 2)
3776                                                                 strlcpy(sky, parameter[1], sizeof(sky));
3777                                                         else if (!strcasecmp(parameter[0], "skyparms") && numparameters >= 2)
3778                                                         {
3779                                                                 if (!atoi(parameter[1]) && strcasecmp(parameter[1], "-"))
3780                                                                         strlcpy(sky, parameter[1], sizeof(sky));
3781                                                         }
3782                                                         else if (!strcasecmp(parameter[0], "cull") && numparameters >= 2)
3783                                                         {
3784                                                                 if (!strcasecmp(parameter[1], "disable") || !strcasecmp(parameter[1], "none") || !strcasecmp(parameter[1], "twosided"))
3785                                                                         flags2 |= Q3TEXTUREFLAG_TWOSIDED;
3786                                                         }
3787                                                         else if (!strcasecmp(parameter[0], "nomipmaps"))
3788                                                                 flags2 |= Q3TEXTUREFLAG_NOMIPMAPS;
3789                                                         else if (!strcasecmp(parameter[0], "nopicmip"))
3790                                                                 flags2 |= Q3TEXTUREFLAG_NOPICMIP;
3791                                                         else if (!strcasecmp(parameter[0], "deformvertexes") && numparameters >= 2)
3792                                                         {
3793                                                                 if (!strcasecmp(parameter[1], "autosprite") && numparameters == 2)
3794                                                                         flags2 |= Q3TEXTUREFLAG_AUTOSPRITE;
3795                                                                 if (!strcasecmp(parameter[1], "autosprite2") && numparameters == 2)
3796                                                                         flags2 |= Q3TEXTUREFLAG_AUTOSPRITE2;
3797                                                         }
3798                                                 }
3799                                                 // force transparent render path for a number of odd
3800                                                 // shader effects to avoid bogging down the normal
3801                                                 // render path unnecessarily
3802                                                 if (flags2 & (Q3TEXTUREFLAG_ADDITIVE | Q3TEXTUREFLAG_AUTOSPRITE | Q3TEXTUREFLAG_AUTOSPRITE2 | Q3TEXTUREFLAG_ALPHATEST))
3803                                                         flags |= Q3SURFACEPARM_TRANS;
3804                                                 // add shader to list (shadername and flags)
3805                                                 // actually here we just poke into the texture settings
3806                                                 for (j = 0, out = loadmodel->brush.data_textures;j < loadmodel->brush.num_textures;j++, out++)
3807                                                 {
3808                                                         if (!strcasecmp(out->name, shadername))
3809                                                         {
3810                                                                 out->surfaceparms = flags;
3811                                                                 out->textureflags = flags2;
3812                                                                 strlcpy(out->firstpasstexturename, firstpasstexturename, sizeof(out->firstpasstexturename));
3813                                                                 if ((flags & Q3SURFACEPARM_SKY) && sky[0])
3814                                                                 {
3815                                                                         // quake3 seems to append a _ to the skybox name, so this must do so as well
3816                                                                         dpsnprintf(loadmodel->brush.skybox, sizeof(loadmodel->brush.skybox), "%s_", sky);
3817                                                                 }
3818                                                         }
3819                                                 }
3820                                         }
3821                                         else
3822                                         {
3823                                                 Con_Printf("%s parsing error - expected \"{\", found \"%s\"\n", search->filenames[i], com_token);
3824                                                 goto parseerror;
3825                                         }
3826                                 }
3827 parseerror:
3828                                 Mem_Free(f);
3829                         }
3830                 }
3831         }
3832
3833         c = 0;
3834         for (j = 0, out = loadmodel->brush.data_textures;j < loadmodel->brush.num_textures;j++, out++)
3835         {
3836                 if (out->surfaceparms == -1)
3837                 {
3838                         c++;
3839                         Con_DPrintf("%s: No shader found for texture \"%s\"\n", loadmodel->name, out->name);
3840                         out->surfaceparms = 0;
3841                         // these are defaults
3842                         //if (!strncmp(out->name, "textures/skies/", 15))
3843                         //      out->surfaceparms |= Q3SURFACEPARM_SKY;
3844                         //if (!strcmp(out->name, "caulk") || !strcmp(out->name, "common/caulk") || !strcmp(out->name, "textures/common/caulk")
3845                         // || !strcmp(out->name, "nodraw") || !strcmp(out->name, "common/nodraw") || !strcmp(out->name, "textures/common/nodraw"))
3846                         //      out->surfaceparms |= Q3SURFACEPARM_NODRAW;
3847                         //if (R_TextureHasAlpha(out->skin.base))
3848                         //      out->surfaceparms |= Q3SURFACEPARM_TRANS;
3849                 }
3850                 if (!Mod_LoadSkinFrame(&out->skin, out->name, (((out->textureflags & Q3TEXTUREFLAG_NOMIPMAPS) || (out->surfaceparms & Q3SURFACEPARM_NOMIPMAPS)) ? 0 : TEXF_MIPMAP) | TEXF_ALPHA | TEXF_PRECACHE | (out->textureflags & Q3TEXTUREFLAG_NOPICMIP ? 0 : TEXF_PICMIP), false, true, true))
3851                         if (!Mod_LoadSkinFrame(&out->skin, out->firstpasstexturename, (((out->textureflags & Q3TEXTUREFLAG_NOMIPMAPS) || (out->surfaceparms & Q3SURFACEPARM_NOMIPMAPS)) ? 0 : TEXF_MIPMAP) | TEXF_ALPHA | TEXF_PRECACHE | (out->textureflags & Q3TEXTUREFLAG_NOPICMIP ? 0 : TEXF_PICMIP), false, true, true))
3852                                 Con_Printf("%s: texture loading for shader \"%s\" failed (first layer \"%s\" not found either)\n", loadmodel->name, out->name, out->firstpasstexturename);
3853         }
3854         if (c)
3855                 Con_DPrintf("%s: %i textures missing shaders\n", loadmodel->name, c);
3856 }
3857
3858 static void Mod_Q3BSP_LoadPlanes(lump_t *l)
3859 {
3860         q3dplane_t *in;
3861         mplane_t *out;
3862         int i, count;
3863
3864         in = (void *)(mod_base + l->fileofs);
3865         if (l->filelen % sizeof(*in))
3866                 Host_Error("Mod_Q3BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3867         count = l->filelen / sizeof(*in);
3868         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3869
3870         loadmodel->brush.data_planes = out;
3871         loadmodel->brush.num_planes = count;
3872
3873         for (i = 0;i < count;i++, in++, out++)
3874         {
3875                 out->normal[0] = LittleLong(in->normal[0]);
3876                 out->normal[1] = LittleLong(in->normal[1]);
3877                 out->normal[2] = LittleLong(in->normal[2]);
3878                 out->dist = LittleLong(in->dist);
3879                 PlaneClassify(out);
3880         }
3881 }
3882
3883 static void Mod_Q3BSP_LoadBrushSides(lump_t *l)
3884 {
3885         q3dbrushside_t *in;
3886         q3mbrushside_t *out;
3887         int i, n, count;
3888
3889         in = (void *)(mod_base + l->fileofs);
3890         if (l->filelen % sizeof(*in))
3891                 Host_Error("Mod_Q3BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3892         count = l->filelen / sizeof(*in);
3893         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3894
3895         loadmodel->brushq3.data_brushsides = out;
3896         loadmodel->brushq3.num_brushsides = count;
3897
3898         for (i = 0;i < count;i++, in++, out++)
3899         {
3900                 n = LittleLong(in->planeindex);
3901                 if (n < 0 || n >= loadmodel->brush.num_planes)
3902                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid planeindex %i (%i planes)\n", n, loadmodel->brush.num_planes);
3903                 out->plane = loadmodel->brush.data_planes + n;
3904                 n = LittleLong(in->textureindex);
3905                 if (n < 0 || n >= loadmodel->brush.num_textures)
3906                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid textureindex %i (%i textures)\n", n, loadmodel->brush.num_textures);
3907                 out->texture = loadmodel->brush.data_textures + n;
3908         }
3909 }
3910
3911 static void Mod_Q3BSP_LoadBrushes(lump_t *l)
3912 {
3913         q3dbrush_t *in;
3914         q3mbrush_t *out;
3915         int i, j, n, c, count, maxplanes;
3916         mplane_t *planes;
3917
3918         in = (void *)(mod_base + l->fileofs);
3919         if (l->filelen % sizeof(*in))
3920                 Host_Error("Mod_Q3BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3921         count = l->filelen / sizeof(*in);
3922         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3923
3924         loadmodel->brushq3.data_brushes = out;
3925         loadmodel->brushq3.num_brushes = count;
3926
3927         maxplanes = 0;
3928         planes = NULL;
3929
3930         for (i = 0;i < count;i++, in++, out++)
3931         {
3932                 n = LittleLong(in->firstbrushside);
3933                 c = LittleLong(in->numbrushsides);
3934                 if (n < 0 || n + c > loadmodel->brushq3.num_brushsides)
3935                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid brushside range %i : %i (%i brushsides)\n", n, n + c, loadmodel->brushq3.num_brushsides);
3936                 out->firstbrushside = loadmodel->brushq3.data_brushsides + n;
3937                 out->numbrushsides = c;
3938                 n = LittleLong(in->textureindex);
3939                 if (n < 0 || n >= loadmodel->brush.num_textures)
3940                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid textureindex %i (%i textures)\n", n, loadmodel->brush.num_textures);
3941                 out->texture = loadmodel->brush.data_textures + n;
3942
3943                 // make a list of mplane_t structs to construct a colbrush from
3944                 if (maxplanes < out->numbrushsides)
3945                 {
3946                         maxplanes = out->numbrushsides;
3947                         if (planes)
3948                                 Mem_Free(planes);
3949                         planes = Mem_Alloc(tempmempool, sizeof(mplane_t) * maxplanes);
3950                 }
3951                 for (j = 0;j < out->numbrushsides;j++)
3952                 {
3953                         VectorCopy(out->firstbrushside[j].plane->normal, planes[j].normal);
3954                         planes[j].dist = out->firstbrushside[j].plane->dist;
3955                 }
3956                 // make the colbrush from the planes
3957                 out->colbrushf = Collision_NewBrushFromPlanes(loadmodel->mempool, out->numbrushsides, planes, out->texture->supercontents);
3958         }
3959         if (planes)
3960                 Mem_Free(planes);
3961 }
3962
3963 static void Mod_Q3BSP_LoadEffects(lump_t *l)
3964 {
3965         q3deffect_t *in;
3966         q3meffect_t *out;
3967         int i, n, count;
3968
3969         in = (void *)(mod_base + l->fileofs);
3970         if (l->filelen % sizeof(*in))
3971                 Host_Error("Mod_Q3BSP_LoadEffects: funny lump size in %s",loadmodel->name);
3972         count = l->filelen / sizeof(*in);
3973         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3974
3975         loadmodel->brushq3.data_effects = out;
3976         loadmodel->brushq3.num_effects = count;
3977
3978         for (i = 0;i < count;i++, in++, out++)
3979         {
3980                 strlcpy (out->shadername, in->shadername, sizeof (out->shadername));
3981                 n = LittleLong(in->brushindex);
3982                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
3983                         Host_Error("Mod_Q3BSP_LoadEffects: invalid brushindex %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
3984                 out->brush = loadmodel->brushq3.data_brushes + n;
3985                 out->unknown = LittleLong(in->unknown);
3986         }
3987 }
3988
3989 static void Mod_Q3BSP_LoadVertices(lump_t *l)
3990 {
3991         q3dvertex_t *in;
3992         int i, count;
3993
3994         in = (void *)(mod_base + l->fileofs);
3995         if (l->filelen % sizeof(*in))
3996                 Host_Error("Mod_Q3BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3997         loadmodel->brushq3.num_vertices = count = l->filelen / sizeof(*in);
3998         loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, count * (sizeof(float) * (3 + 2 + 2 + 4)));
3999         loadmodel->brushq3.data_texcoordtexture2f = loadmodel->brushq3.data_vertex3f + count * 3;
4000         loadmodel->brushq3.data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordtexture2f + count * 2;
4001         loadmodel->brushq3.data_color4f = loadmodel->brushq3.data_texcoordlightmap2f + count * 2;
4002
4003         for (i = 0;i < count;i++, in++)
4004         {
4005                 loadmodel->brushq3.data_vertex3f[i * 3 + 0] = LittleFloat(in->origin3f[0]);
4006                 loadmodel->brushq3.data_vertex3f[i * 3 + 1] = LittleFloat(in->origin3f[1]);
4007                 loadmodel->brushq3.data_vertex3f[i * 3 + 2] = LittleFloat(in->origin3f[2]);
4008                 loadmodel->brushq3.data_texcoordtexture2f[i * 2 + 0] = LittleFloat(in->texcoord2f[0]);
4009                 loadmodel->brushq3.data_texcoordtexture2f[i * 2 + 1] = LittleFloat(in->texcoord2f[1]);
4010                 loadmodel->brushq3.data_texcoordlightmap2f[i * 2 + 0] = LittleFloat(in->lightmap2f[0]);
4011                 loadmodel->brushq3.data_texcoordlightmap2f[i * 2 + 1] = LittleFloat(in->lightmap2f[1]);
4012                 // svector/tvector are calculated later in face loading
4013                 loadmodel->brushq3.data_color4f[i * 4 + 0] = in->color4ub[0] * (1.0f / 255.0f);
4014                 loadmodel->brushq3.data_color4f[i * 4 + 1] = in->color4ub[1] * (1.0f / 255.0f);
4015                 loadmodel->brushq3.data_color4f[i * 4 + 2] = in->color4ub[2] * (1.0f / 255.0f);
4016                 loadmodel->brushq3.data_color4f[i * 4 + 3] = in->color4ub[3] * (1.0f / 255.0f);
4017         }
4018 }
4019
4020 static void Mod_Q3BSP_LoadTriangles(lump_t *l)
4021 {
4022         int *in;
4023         int *out;
4024         int i, count;
4025
4026         in = (void *)(mod_base + l->fileofs);
4027         if (l->filelen % sizeof(int[3]))
4028                 Host_Error("Mod_Q3BSP_LoadTriangles: funny lump size in %s",loadmodel->name);
4029         count = l->filelen / sizeof(*in);
4030         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4031
4032         loadmodel->brushq3.num_triangles = count / 3;
4033         loadmodel->brushq3.data_element3i = out;
4034
4035         for (i = 0;i < count;i++, in++, out++)
4036         {
4037                 *out = LittleLong(*in);
4038                 if (*out < 0 || *out >= loadmodel->brushq3.num_vertices)
4039                 {
4040                         Con_Printf("Mod_Q3BSP_LoadTriangles: invalid vertexindex %i (%i vertices), setting to 0\n", *out, loadmodel->brushq3.num_vertices);
4041                         *out = 0;
4042                 }
4043         }
4044 }
4045
4046 static void Mod_Q3BSP_LoadLightmaps(lump_t *l)
4047 {
4048         q3dlightmap_t *in;
4049         rtexture_t **out;
4050         int i, count;
4051
4052         if (!l->filelen)
4053                 return;
4054         in = (void *)(mod_base + l->fileofs);
4055         if (l->filelen % sizeof(*in))
4056                 Host_Error("Mod_Q3BSP_LoadLightmaps: funny lump size in %s",loadmodel->name);
4057         count = l->filelen / sizeof(*in);
4058         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4059
4060         loadmodel->brushq3.data_lightmaps = out;
4061         loadmodel->brushq3.num_lightmaps = count;
4062
4063         for (i = 0;i < count;i++, in++, out++)
4064                 *out = R_LoadTexture2D(loadmodel->texturepool, va("lightmap%04i", i), 128, 128, in->rgb, TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
4065 }
4066
4067 static void Mod_Q3BSP_LoadFaces(lump_t *l)
4068 {
4069         q3dface_t *in, *oldin;
4070         q3msurface_t *out, *oldout;
4071         int i, oldi, j, n, count, invalidelements, patchsize[2], finalwidth, finalheight, xtess, ytess, finalvertices, finaltriangles, firstvertex, firstelement, type, oldnumtriangles, oldnumtriangles2, meshnum, meshvertices, meshtriangles, numvertices, numtriangles;
4072         //int *originalelement3i;
4073         //int *originalneighbor3i;
4074         float *originalvertex3f;
4075         //float *originalsvector3f;
4076         //float *originaltvector3f;
4077         //float *originalnormal3f;
4078         float *originalcolor4f;
4079         float *originaltexcoordtexture2f;
4080         float *originaltexcoordlightmap2f;
4081         float *v;
4082         surfmesh_t *mesh, *tempmeshlist[1024];
4083
4084         in = (void *)(mod_base + l->fileofs);
4085         if (l->filelen % sizeof(*in))
4086                 Host_Error("Mod_Q3BSP_LoadFaces: funny lump size in %s",loadmodel->name);
4087         count = l->filelen / sizeof(*in);
4088         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4089
4090         loadmodel->brushq3.data_faces = out;
4091         loadmodel->brushq3.num_faces = count;
4092
4093         i = 0;
4094         for (meshnum = 0;i < count;meshnum++)
4095         {
4096                 oldi = i;
4097                 oldin = in;
4098                 oldout = out;
4099                 meshvertices = 0;
4100                 meshtriangles = 0;
4101                 for (;i < count;i++, in++, out++)
4102                 {
4103                         // check face type first
4104                         type = LittleLong(in->type);
4105                         if (type != Q3FACETYPE_POLYGON
4106                          && type != Q3FACETYPE_PATCH
4107                          && type != Q3FACETYPE_MESH
4108                          && type != Q3FACETYPE_FLARE)
4109                         {
4110                                 Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i: unknown face type %i\n", i, type);
4111                                 continue;
4112                         }
4113
4114                         n = LittleLong(in->textureindex);
4115                         if (n < 0 || n >= loadmodel->brush.num_textures)
4116                         {
4117                                 Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i: invalid textureindex %i (%i textures)\n", i, n, loadmodel->brush.num_textures);
4118                                 continue;
4119                         }
4120                         out->texture = loadmodel->brush.data_textures + n;
4121                         n = LittleLong(in->effectindex);
4122                         if (n < -1 || n >= loadmodel->brushq3.num_effects)
4123                         {
4124                                 if (developer.integer >= 2)
4125                                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid effectindex %i (%i effects)\n", i, out->texture->name, n, loadmodel->brushq3.num_effects);
4126                                 n = -1;
4127                         }
4128                         if (n == -1)
4129                                 out->effect = NULL;
4130                         else
4131                                 out->effect = loadmodel->brushq3.data_effects + n;
4132                         n = LittleLong(in->lightmapindex);
4133                         if (n >= loadmodel->brushq3.num_lightmaps)
4134                         {
4135                                 Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid lightmapindex %i (%i lightmaps)\n", i, out->texture->name, n, loadmodel->brushq3.num_lightmaps);
4136                                 n = -1;
4137                         }
4138                         else if (n < 0)
4139                                 n = -1;
4140                         if (n == -1)
4141                                 out->lightmaptexture = NULL;
4142                         else
4143                                 out->lightmaptexture = loadmodel->brushq3.data_lightmaps[n];
4144
4145                         firstvertex = LittleLong(in->firstvertex);
4146                         numvertices = LittleLong(in->numvertices);
4147                         firstelement = LittleLong(in->firstelement);
4148                         numtriangles = LittleLong(in->numelements) / 3;
4149                         if (numtriangles * 3 != LittleLong(in->numelements))
4150                         {
4151                                 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));
4152                                 continue;
4153                         }
4154                         if (firstvertex < 0 || firstvertex + numvertices > loadmodel->brushq3.num_vertices)
4155                         {
4156                                 Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid vertex range %i : %i (%i vertices)\n", i, out->texture->name, firstvertex, firstvertex + numvertices, loadmodel->brushq3.num_vertices);
4157                                 continue;
4158                         }
4159                         if (firstelement < 0 || firstelement + numtriangles * 3 > loadmodel->brushq3.num_triangles * 3)
4160                         {
4161                                 Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid element range %i : %i (%i elements)\n", i, out->texture->name, firstelement, firstelement + numtriangles * 3, loadmodel->brushq3.num_triangles * 3);
4162                                 continue;
4163                         }
4164                         switch(type)
4165                         {
4166                         case Q3FACETYPE_POLYGON:
4167                         case Q3FACETYPE_MESH:
4168                                 // no processing necessary
4169                                 break;
4170                         case Q3FACETYPE_PATCH:
4171                                 patchsize[0] = LittleLong(in->specific.patch.patchsize[0]);
4172                                 patchsize[1] = LittleLong(in->specific.patch.patchsize[1]);
4173                                 if (numvertices != (patchsize[0] * patchsize[1]) || patchsize[0] < 3 || patchsize[1] < 3 || !(patchsize[0] & 1) || !(patchsize[1] & 1) || patchsize[0] * patchsize[1] >= min(r_subdivisions_maxvertices.integer, r_subdivisions_collision_maxvertices.integer))
4174                                 {
4175                                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid patchsize %ix%i\n", i, out->texture->name, patchsize[0], patchsize[1]);
4176                                         continue;
4177                                 }
4178                                 originalvertex3f = loadmodel->brushq3.data_vertex3f + firstvertex * 3;
4179                                 // convert patch to Q3FACETYPE_MESH
4180                                 xtess = Q3PatchTesselationOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value);
4181                                 ytess = Q3PatchTesselationOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value);
4182                                 // bound to user settings
4183                                 xtess = bound(r_subdivisions_mintess.integer, xtess, r_subdivisions_maxtess.integer);
4184                                 ytess = bound(r_subdivisions_mintess.integer, ytess, r_subdivisions_maxtess.integer);
4185                                 // bound to sanity settings
4186                                 xtess = bound(1, xtess, 1024);
4187                                 ytess = bound(1, ytess, 1024);
4188                                 // bound to user limit on vertices
4189                                 while ((xtess > 1 || ytess > 1) && (((patchsize[0] - 1) * xtess) + 1) * (((patchsize[1] - 1) * ytess) + 1) > min(r_subdivisions_maxvertices.integer, 262144))
4190                                 {
4191                                         if (xtess > ytess)
4192                                                 xtess--;
4193                                         else
4194                                                 ytess--;
4195                                 }
4196                                 finalwidth = ((patchsize[0] - 1) * xtess) + 1;
4197                                 finalheight = ((patchsize[1] - 1) * ytess) + 1;
4198                                 numvertices = finalwidth * finalheight;
4199                                 numtriangles = (finalwidth - 1) * (finalheight - 1) * 2;
4200                                 break;
4201                         case Q3FACETYPE_FLARE:
4202                                 if (developer.integer >= 2)
4203                                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): Q3FACETYPE_FLARE not supported (yet)\n", i, out->texture->name);
4204                                 // don't render it
4205                                 continue;
4206                         }
4207                         out->mesh.num_vertices = numvertices;
4208                         out->mesh.num_triangles = numtriangles;
4209                         if (meshvertices + out->mesh.num_vertices > 65536)
4210                                 break;
4211                         meshvertices += out->mesh.num_vertices;
4212                         meshtriangles += out->mesh.num_triangles;
4213                 }
4214
4215                 i = oldi;
4216                 in = oldin;
4217                 out = oldout;
4218                 mesh = tempmeshlist[meshnum] = Mod_AllocSurfMesh(loadmodel->mempool, meshvertices, meshtriangles, 0, 0, false, false, true);
4219                 meshvertices = 0;
4220                 meshtriangles = 0;
4221                 for (;i < count && meshvertices + out->mesh.num_vertices <= mesh->num_vertices;i++, in++, out++)
4222                 {
4223                         if (out->mesh.num_vertices < 3 || out->mesh.num_triangles < 1)
4224                                 continue;
4225
4226                         type = LittleLong(in->type);
4227                         firstvertex = LittleLong(in->firstvertex);
4228                         firstelement = LittleLong(in->firstelement);
4229                         out->mesh.data_vertex3f = mesh->data_vertex3f + meshvertices * 3;
4230                         out->mesh.data_svector3f = mesh->data_svector3f + meshvertices * 3;
4231                         out->mesh.data_tvector3f = mesh->data_tvector3f + meshvertices * 3;
4232                         out->mesh.data_normal3f = mesh->data_normal3f + meshvertices * 3;
4233                         out->mesh.data_texcoordtexture2f = mesh->data_texcoordtexture2f + meshvertices * 2;
4234                         out->mesh.data_texcoordlightmap2f = mesh->data_texcoordlightmap2f + meshvertices * 2;
4235                         out->mesh.data_lightmapcolor4f = mesh->data_lightmapcolor4f + meshvertices * 4;
4236                         out->mesh.data_element3i = mesh->data_element3i + meshtriangles * 3;
4237                         out->mesh.data_neighbor3i = mesh->data_neighbor3i + meshtriangles * 3;
4238                         switch(type)
4239                         {
4240                         case Q3FACETYPE_POLYGON:
4241                         case Q3FACETYPE_MESH:
4242                                 // no processing necessary
4243                                 for (j = 0;j < out->mesh.num_vertices;j++)
4244                                 {
4245                                         out->mesh.data_vertex3f[j * 3 + 0] = loadmodel->brushq3.data_vertex3f[(firstvertex + j) * 3 + 0];
4246                                         out->mesh.data_vertex3f[j * 3 + 1] = loadmodel->brushq3.data_vertex3f[(firstvertex + j) * 3 + 1];
4247                                         out->mesh.data_vertex3f[j * 3 + 2] = loadmodel->brushq3.data_vertex3f[(firstvertex + j) * 3 + 2];
4248                                         out->mesh.data_texcoordtexture2f[j * 2 + 0] = loadmodel->brushq3.data_texcoordtexture2f[(firstvertex + j) * 2 + 0];
4249                                         out->mesh.data_texcoordtexture2f[j * 2 + 1] = loadmodel->brushq3.data_texcoordtexture2f[(firstvertex + j) * 2 + 1];
4250                                         out->mesh.data_texcoordlightmap2f[j * 2 + 0] = loadmodel->brushq3.data_texcoordlightmap2f[(firstvertex + j) * 2 + 0];
4251                                         out->mesh.data_texcoordlightmap2f[j * 2 + 1] = loadmodel->brushq3.data_texcoordlightmap2f[(firstvertex + j) * 2 + 1];
4252                                         out->mesh.data_lightmapcolor4f[j * 4 + 0] = loadmodel->brushq3.data_color4f[(firstvertex + j) * 4 + 0];
4253                                         out->mesh.data_lightmapcolor4f[j * 4 + 1] = loadmodel->brushq3.data_color4f[(firstvertex + j) * 4 + 1];
4254                                         out->mesh.data_lightmapcolor4f[j * 4 + 2] = loadmodel->brushq3.data_color4f[(firstvertex + j) * 4 + 2];
4255                                         out->mesh.data_lightmapcolor4f[j * 4 + 3] = loadmodel->brushq3.data_color4f[(firstvertex + j) * 4 + 3];
4256                                 }
4257                                 for (j = 0;j < out->mesh.num_triangles*3;j++)
4258                                         out->mesh.data_element3i[j] = loadmodel->brushq3.data_element3i[firstelement + j];
4259                                 break;
4260                         case Q3FACETYPE_PATCH:
4261                                 patchsize[0] = LittleLong(in->specific.patch.patchsize[0]);
4262                                 patchsize[1] = LittleLong(in->specific.patch.patchsize[1]);
4263                                 originalvertex3f = loadmodel->brushq3.data_vertex3f + firstvertex * 3;
4264                                 originaltexcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f + firstvertex * 2;
4265                                 originaltexcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f + firstvertex * 2;
4266                                 originalcolor4f = loadmodel->brushq3.data_color4f + firstvertex * 4;
4267                                 // convert patch to Q3FACETYPE_MESH
4268                                 xtess = Q3PatchTesselationOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value);
4269                                 ytess = Q3PatchTesselationOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value);
4270                                 // bound to user settings
4271                                 xtess = bound(r_subdivisions_mintess.integer, xtess, r_subdivisions_maxtess.integer);
4272                                 ytess = bound(r_subdivisions_mintess.integer, ytess, r_subdivisions_maxtess.integer);
4273                                 // bound to sanity settings
4274                                 xtess = bound(1, xtess, 1024);
4275                                 ytess = bound(1, ytess, 1024);
4276                                 // bound to user limit on vertices
4277                                 while ((xtess > 1 || ytess > 1) && (((patchsize[0] - 1) * xtess) + 1) * (((patchsize[1] - 1) * ytess) + 1) > min(r_subdivisions_maxvertices.integer, 262144))
4278                                 {
4279                                         if (xtess > ytess)
4280                                                 xtess--;
4281                                         else
4282                                                 ytess--;
4283                                 }
4284                                 finalwidth = ((patchsize[0] - 1) * xtess) + 1;
4285                                 finalheight = ((patchsize[1] - 1) * ytess) + 1;
4286                                 finalvertices = finalwidth * finalheight;
4287                                 finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
4288                                 type = Q3FACETYPE_MESH;
4289                                 // generate geometry
4290                                 // (note: normals are skipped because they get recalculated)
4291                                 Q3PatchTesselateFloat(3, sizeof(float[3]), out->mesh.data_vertex3f, patchsize[0], patchsize[1], sizeof(float[3]), originalvertex3f, xtess, ytess);
4292                                 Q3PatchTesselateFloat(2, sizeof(float[2]), out->mesh.data_texcoordtexture2f, patchsize[0], patchsize[1], sizeof(float[2]), originaltexcoordtexture2f, xtess, ytess);
4293                                 Q3PatchTesselateFloat(2, sizeof(float[2]), out->mesh.data_texcoordlightmap2f, patchsize[0], patchsize[1], sizeof(float[2]), originaltexcoordlightmap2f, xtess, ytess);
4294                                 Q3PatchTesselateFloat(4, sizeof(float[4]), out->mesh.data_lightmapcolor4f, patchsize[0], patchsize[1], sizeof(float[4]), originalcolor4f, xtess, ytess);
4295                                 Q3PatchTriangleElements(out->mesh.data_element3i, finalwidth, finalheight);
4296                                 out->mesh.num_triangles = Mod_RemoveDegenerateTriangles(out->mesh.num_triangles, out->mesh.data_element3i, out->mesh.data_element3i, out->mesh.data_vertex3f);
4297                                 if (developer.integer >= 2)
4298                                 {
4299                                         if (out->mesh.num_triangles < finaltriangles)
4300                                                 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->mesh.num_vertices, finaltriangles, finaltriangles - out->mesh.num_triangles, out->mesh.num_triangles);
4301                                         else
4302                                                 Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided to %i vertices / %i triangles\n", patchsize[0], patchsize[1], out->mesh.num_vertices, out->mesh.num_triangles);
4303                                 }
4304                                 // q3map does not put in collision brushes for curves... ugh
4305                                 // build the lower quality collision geometry
4306                                 xtess = Q3PatchTesselationOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_collision_tolerance.value);
4307                                 ytess = Q3PatchTesselationOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_collision_tolerance.value);
4308                                 // bound to user settings
4309                                 xtess = bound(r_subdivisions_collision_mintess.integer, xtess, r_subdivisions_collision_maxtess.integer);
4310                                 ytess = bound(r_subdivisions_collision_mintess.integer, ytess, r_subdivisions_collision_maxtess.integer);
4311                                 // bound to sanity settings
4312                                 xtess = bound(1, xtess, 1024);
4313                                 ytess = bound(1, ytess, 1024);
4314                                 // bound to user limit on vertices
4315                                 while ((xtess > 1 || ytess > 1) && (((patchsize[0] - 1) * xtess) + 1) * (((patchsize[1] - 1) * ytess) + 1) > min(r_subdivisions_collision_maxvertices.integer, 262144))
4316                                 {
4317                                         if (xtess > ytess)
4318                                                 xtess--;
4319                                         else
4320                                                 ytess--;
4321                                 }
4322                                 finalwidth = ((patchsize[0] - 1) * xtess) + 1;
4323                                 finalheight = ((patchsize[1] - 1) * ytess) + 1;
4324                                 finalvertices = finalwidth * finalheight;
4325                                 finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
4326
4327                                 out->mesh.data_collisionvertex3f = Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * finalvertices);
4328                                 out->mesh.data_collisionelement3i = Mem_Alloc(loadmodel->mempool, sizeof(int[3]) * finaltriangles);
4329                                 out->mesh.num_collisionvertices = finalvertices;
4330                                 out->mesh.num_collisiontriangles = finaltriangles;
4331                                 Q3PatchTesselateFloat(3, sizeof(float[3]), out->mesh.data_collisionvertex3f, patchsize[0], patchsize[1], sizeof(float[3]), originalvertex3f, xtess, ytess);
4332                                 Q3PatchTriangleElements(out->mesh.data_collisionelement3i, finalwidth, finalheight);
4333
4334                                 //Mod_SnapVertices(3, out->mesh.num_vertices, out->mesh.data_vertex3f, 0.25);
4335                                 Mod_SnapVertices(3, out->mesh.num_collisionvertices, out->mesh.data_collisionvertex3f, 1);
4336
4337                                 oldnumtriangles = out->mesh.num_triangles;
4338                                 oldnumtriangles2 = out->mesh.num_collisiontriangles;
4339                                 out->mesh.num_collisiontriangles = Mod_RemoveDegenerateTriangles(out->mesh.num_collisiontriangles, out->mesh.data_collisionelement3i, out->mesh.data_collisionelement3i, out->mesh.data_collisionvertex3f);
4340                                 if (developer.integer)
4341                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve became %i:%i vertices / %i:%i triangles (%i:%i degenerate)\n", patchsize[0], patchsize[1], out->mesh.num_vertices, out->mesh.num_collisionvertices, oldnumtriangles, oldnumtriangles2, oldnumtriangles - out->mesh.num_triangles, oldnumtriangles2 - out->mesh.num_collisiontriangles);
4342                                 break;
4343                         default:
4344                                 break;
4345                         }
4346                         meshvertices += out->mesh.num_vertices;
4347                         meshtriangles += out->mesh.num_triangles;
4348                         for (j = 0, invalidelements = 0;j < out->mesh.num_triangles * 3;j++)
4349                                 if (out->mesh.data_element3i[j] < 0 || out->mesh.data_element3i[j] >= out->mesh.num_vertices)
4350                                         invalidelements++;
4351                         if (invalidelements)
4352                         {
4353                                 Con_Printf("Mod_Q3BSP_LoadFaces: Warning: face #%i has %i invalid elements, type = %i, texture->name = \"%s\", texture->surfaceflags = %i, firstvertex = %i, numvertices = %i, firstelement = %i, numelements = %i, elements list:\n", i, invalidelements, type, out->texture->name, out->texture->surfaceflags, firstvertex, out->mesh.num_vertices, firstelement, out->mesh.num_triangles * 3);
4354                                 for (j = 0;j < out->mesh.num_triangles * 3;j++)
4355                                 {
4356                                         Con_Printf(" %i", out->mesh.data_element3i[j]);
4357                                         if (out->mesh.data_element3i[j] < 0 || out->mesh.data_element3i[j] >= out->mesh.num_vertices)
4358                                                 out->mesh.data_element3i[j] = 0;
4359                                 }
4360                                 Con_Print("\n");
4361                         }
4362                         // for shadow volumes
4363                         Mod_BuildTriangleNeighbors(out->mesh.data_neighbor3i, out->mesh.data_element3i, out->mesh.num_triangles);
4364                         // for per pixel lighting
4365                         Mod_BuildTextureVectorsAndNormals(out->mesh.num_vertices, out->mesh.num_triangles, out->mesh.data_vertex3f, out->mesh.data_texcoordtexture2f, out->mesh.data_element3i, out->mesh.data_svector3f, out->mesh.data_tvector3f, out->mesh.data_normal3f);
4366                         // calculate a bounding box
4367                         VectorClear(out->mins);
4368                         VectorClear(out->maxs);
4369                         if (out->mesh.num_vertices)
4370                         {
4371                                 VectorCopy(out->mesh.data_vertex3f, out->mins);
4372                                 VectorCopy(out->mesh.data_vertex3f, out->maxs);
4373                                 for (j = 1, v = out->mesh.data_vertex3f + 3;j < out->mesh.num_vertices;j++, v += 3)
4374                                 {
4375                                         out->mins[0] = min(out->mins[0], v[0]);
4376                                         out->maxs[0] = max(out->maxs[0], v[0]);
4377                                         out->mins[1] = min(out->mins[1], v[1]);
4378                                         out->maxs[1] = max(out->maxs[1], v[1]);
4379                                         out->mins[2] = min(out->mins[2], v[2]);
4380                                         out->maxs[2] = max(out->maxs[2], v[2]);
4381                                 }
4382                                 out->mins[0] -= 1.0f;
4383                                 out->mins[1] -= 1.0f;
4384                                 out->mins[2] -= 1.0f;
4385                                 out->maxs[0] += 1.0f;
4386                                 out->maxs[1] += 1.0f;
4387                                 out->maxs[2] += 1.0f;
4388                         }
4389                 }
4390         }
4391
4392         // now store the completed list of meshes
4393         loadmodel->nummeshes = meshnum;
4394         if (loadmodel->nummeshes)
4395         {
4396                 loadmodel->meshlist = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t *) * loadmodel->nummeshes);
4397                 memcpy(loadmodel->meshlist, tempmeshlist, sizeof(surfmesh_t *) * loadmodel->nummeshes);
4398         }
4399
4400         // free the no longer needed vertex data
4401         loadmodel->brushq3.num_vertices = 0;
4402         Mem_Free(loadmodel->brushq3.data_vertex3f);
4403         loadmodel->brushq3.data_vertex3f = NULL;
4404         loadmodel->brushq3.data_texcoordtexture2f = NULL;
4405         loadmodel->brushq3.data_texcoordlightmap2f = NULL;
4406         loadmodel->brushq3.data_color4f = NULL;
4407         // free the no longer needed triangle data
4408         loadmodel->brushq3.num_triangles = 0;
4409         Mem_Free(loadmodel->brushq3.data_element3i);
4410         loadmodel->brushq3.data_element3i = NULL;
4411 }
4412
4413 static void Mod_Q3BSP_LoadModels(lump_t *l)
4414 {
4415         q3dmodel_t *in;
4416         q3mmodel_t *out;
4417         int i, j, n, c, count;
4418
4419         in = (void *)(mod_base + l->fileofs);
4420         if (l->filelen % sizeof(*in))
4421                 Host_Error("Mod_Q3BSP_LoadModels: funny lump size in %s",loadmodel->name);
4422         count = l->filelen / sizeof(*in);
4423         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4424
4425         loadmodel->brushq3.data_models = out;
4426         loadmodel->brushq3.num_models = count;
4427
4428         for (i = 0;i < count;i++, in++, out++)
4429         {
4430                 for (j = 0;j < 3;j++)
4431                 {
4432                         out->mins[j] = LittleFloat(in->mins[j]);
4433                         out->maxs[j] = LittleFloat(in->maxs[j]);
4434                 }
4435                 n = LittleLong(in->firstface);
4436                 c = LittleLong(in->numfaces);
4437                 if (n < 0 || n + c > loadmodel->brushq3.num_faces)
4438                         Host_Error("Mod_Q3BSP_LoadModels: invalid face range %i : %i (%i faces)\n", n, n + c, loadmodel->brushq3.num_faces);
4439                 out->firstface = loadmodel->brushq3.data_faces + n;
4440                 out->numfaces = c;
4441                 n = LittleLong(in->firstbrush);
4442                 c = LittleLong(in->numbrushes);
4443                 if (n < 0 || n + c > loadmodel->brushq3.num_brushes)
4444                         Host_Error("Mod_Q3BSP_LoadModels: invalid brush range %i : %i (%i brushes)\n", n, n + c, loadmodel->brushq3.num_brushes);
4445                 out->firstbrush = loadmodel->brushq3.data_brushes + n;
4446                 out->numbrushes = c;
4447         }
4448 }
4449
4450 static void Mod_Q3BSP_LoadLeafBrushes(lump_t *l)
4451 {
4452         int *in;
4453         int *out;
4454         int i, n, count;
4455
4456         in = (void *)(mod_base + l->fileofs);
4457         if (l->filelen % sizeof(*in))
4458                 Host_Error("Mod_Q3BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
4459         count = l->filelen / sizeof(*in);
4460         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4461
4462         loadmodel->brush.data_leafbrushes = out;
4463         loadmodel->brush.num_leafbrushes = count;
4464
4465         for (i = 0;i < count;i++, in++, out++)
4466         {
4467                 n = LittleLong(*in);
4468                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
4469                         Host_Error("Mod_Q3BSP_LoadLeafBrushes: invalid brush index %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
4470                 *out = n;
4471         }
4472 }
4473
4474 static void Mod_Q3BSP_LoadLeafFaces(lump_t *l)
4475 {
4476         int *in;
4477         int *out;
4478         int i, n, count;
4479
4480         in = (void *)(mod_base + l->fileofs);
4481         if (l->filelen % sizeof(*in))
4482                 Host_Error("Mod_Q3BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
4483         count = l->filelen / sizeof(*in);
4484         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4485
4486         loadmodel->brush.data_leaffaces = out;
4487         loadmodel->brush.num_leaffaces = count;
4488
4489         for (i = 0;i < count;i++, in++, out++)
4490         {
4491                 n = LittleLong(*in);
4492                 if (n < 0 || n >= loadmodel->brushq3.num_faces)
4493                         Host_Error("Mod_Q3BSP_LoadLeafFaces: invalid face index %i (%i faces)\n", n, loadmodel->brushq3.num_faces);
4494                 *out = n;
4495         }
4496 }
4497
4498 static void Mod_Q3BSP_LoadLeafs(lump_t *l)
4499 {
4500         q3dleaf_t *in;
4501         mleaf_t *out;
4502         int i, j, n, c, count;
4503
4504         in = (void *)(mod_base + l->fileofs);
4505         if (l->filelen % sizeof(*in))
4506                 Host_Error("Mod_Q3BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
4507         count = l->filelen / sizeof(*in);
4508         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4509
4510         loadmodel->brush.data_leafs = out;
4511         loadmodel->brush.num_leafs = count;
4512
4513         for (i = 0;i < count;i++, in++, out++)
4514         {
4515                 out->parent = NULL;
4516                 out->plane = NULL;
4517                 out->clusterindex = LittleLong(in->clusterindex);
4518                 out->areaindex = LittleLong(in->areaindex);
4519                 for (j = 0;j < 3;j++)
4520                 {
4521                         // yes the mins/maxs are ints
4522                         out->mins[j] = LittleLong(in->mins[j]) - 1;
4523                         out->maxs[j] = LittleLong(in->maxs[j]) + 1;
4524                 }
4525                 n = LittleLong(in->firstleafface);
4526                 c = LittleLong(in->numleaffaces);
4527                 if (n < 0 || n + c > loadmodel->brush.num_leaffaces)
4528                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafface range %i : %i (%i leaffaces)\n", n, n + c, loadmodel->brush.num_leaffaces);
4529                 out->firstleafface = loadmodel->brush.data_leaffaces + n;
4530                 out->numleaffaces = c;
4531                 n = LittleLong(in->firstleafbrush);
4532                 c = LittleLong(in->numleafbrushes);
4533                 if (n < 0 || n + c > loadmodel->brush.num_leafbrushes)
4534                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafbrush range %i : %i (%i leafbrushes)\n", n, n + c, loadmodel->brush.num_leafbrushes);
4535                 out->firstleafbrush = loadmodel->brush.data_leafbrushes + n;
4536                 out->numleafbrushes = c;
4537         }
4538 }
4539
4540 static void Mod_Q3BSP_LoadNodes_RecursiveSetParent(mnode_t *node, mnode_t *parent)
4541 {
4542         if (node->parent)
4543                 Host_Error("Mod_Q3BSP_LoadNodes_RecursiveSetParent: runaway recursion\n");
4544         node->parent = parent;
4545         if (node->plane)
4546         {
4547                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
4548                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
4549         }
4550 }
4551
4552 static void Mod_Q3BSP_LoadNodes(lump_t *l)
4553 {
4554         q3dnode_t *in;
4555         mnode_t *out;
4556         int i, j, n, count;
4557
4558         in = (void *)(mod_base + l->fileofs);
4559         if (l->filelen % sizeof(*in))
4560                 Host_Error("Mod_Q3BSP_LoadNodes: funny lump size in %s",loadmodel->name);
4561         count = l->filelen / sizeof(*in);
4562         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4563
4564         loadmodel->brush.data_nodes = out;
4565         loadmodel->brush.num_nodes = count;
4566
4567         for (i = 0;i < count;i++, in++, out++)
4568         {
4569                 out->parent = NULL;
4570                 n = LittleLong(in->planeindex);
4571                 if (n < 0 || n >= loadmodel->brush.num_planes)
4572                         Host_Error("Mod_Q3BSP_LoadNodes: invalid planeindex %i (%i planes)\n", n, loadmodel->brush.num_planes);
4573                 out->plane = loadmodel->brush.data_planes + n;
4574                 for (j = 0;j < 2;j++)
4575                 {
4576                         n = LittleLong(in->childrenindex[j]);
4577                         if (n >= 0)
4578                         {
4579                                 if (n >= loadmodel->brush.num_nodes)
4580                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child node index %i (%i nodes)\n", n, loadmodel->brush.num_nodes);
4581                                 out->children[j] = loadmodel->brush.data_nodes + n;
4582                         }
4583                         else
4584                         {
4585                                 n = -1 - n;
4586                                 if (n >= loadmodel->brush.num_leafs)
4587                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child leaf index %i (%i leafs)\n", n, loadmodel->brush.num_leafs);
4588                                 out->children[j] = (mnode_t *)(loadmodel->brush.data_leafs + n);
4589                         }
4590                 }
4591                 for (j = 0;j < 3;j++)
4592                 {
4593                         // yes the mins/maxs are ints
4594                         out->mins[j] = LittleLong(in->mins[j]) - 1;
4595                         out->maxs[j] = LittleLong(in->maxs[j]) + 1;
4596                 }
4597         }
4598
4599         // set the parent pointers
4600         Mod_Q3BSP_LoadNodes_RecursiveSetParent(loadmodel->brush.data_nodes, NULL);
4601 }
4602
4603 static void Mod_Q3BSP_LoadLightGrid(lump_t *l)
4604 {
4605         q3dlightgrid_t *in;
4606         q3dlightgrid_t *out;
4607         int count;
4608
4609         in = (void *)(mod_base + l->fileofs);
4610         if (l->filelen % sizeof(*in))
4611                 Host_Error("Mod_Q3BSP_LoadLightGrid: funny lump size in %s",loadmodel->name);
4612         loadmodel->brushq3.num_lightgrid_scale[0] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[0];
4613         loadmodel->brushq3.num_lightgrid_scale[1] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[1];
4614         loadmodel->brushq3.num_lightgrid_scale[2] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[2];
4615         loadmodel->brushq3.num_lightgrid_imins[0] = ceil(loadmodel->brushq3.data_models->mins[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4616         loadmodel->brushq3.num_lightgrid_imins[1] = ceil(loadmodel->brushq3.data_models->mins[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4617         loadmodel->brushq3.num_lightgrid_imins[2] = ceil(loadmodel->brushq3.data_models->mins[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4618         loadmodel->brushq3.num_lightgrid_imaxs[0] = floor(loadmodel->brushq3.data_models->maxs[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4619         loadmodel->brushq3.num_lightgrid_imaxs[1] = floor(loadmodel->brushq3.data_models->maxs[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4620         loadmodel->brushq3.num_lightgrid_imaxs[2] = floor(loadmodel->brushq3.data_models->maxs[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4621         loadmodel->brushq3.num_lightgrid_isize[0] = loadmodel->brushq3.num_lightgrid_imaxs[0] - loadmodel->brushq3.num_lightgrid_imins[0] + 1;
4622         loadmodel->brushq3.num_lightgrid_isize[1] = loadmodel->brushq3.num_lightgrid_imaxs[1] - loadmodel->brushq3.num_lightgrid_imins[1] + 1;
4623         loadmodel->brushq3.num_lightgrid_isize[2] = loadmodel->brushq3.num_lightgrid_imaxs[2] - loadmodel->brushq3.num_lightgrid_imins[2] + 1;
4624         count = loadmodel->brushq3.num_lightgrid_isize[0] * loadmodel->brushq3.num_lightgrid_isize[1] * loadmodel->brushq3.num_lightgrid_isize[2];
4625         if (l->filelen)
4626         {
4627                 if (l->filelen < count * (int)sizeof(*in))
4628                         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]);
4629                 if (l->filelen != count * (int)sizeof(*in))
4630                         Con_Printf("Mod_Q3BSP_LoadLightGrid: Warning: calculated lightgrid size %i bytes does not match lump size %i\n", count * sizeof(*in), l->filelen);
4631         }
4632
4633         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4634         loadmodel->brushq3.data_lightgrid = out;
4635         loadmodel->brushq3.num_lightgrid = count;
4636
4637         // no swapping or validation necessary
4638         if (l->filelen)
4639                 memcpy(out, in, count * (int)sizeof(*out));
4640         else
4641         {
4642                 // no data, fill with white
4643                 int i;
4644                 for (i = 0;i < count;i++)
4645                 {
4646                         out[i].ambientrgb[0] = 128;
4647                         out[i].ambientrgb[1] = 128;
4648                         out[i].ambientrgb[2] = 128;
4649                         out[i].diffusergb[0] = 0;
4650                         out[i].diffusergb[1] = 0;
4651                         out[i].diffusergb[2] = 0;
4652                         out[i].diffusepitch = 0;
4653                         out[i].diffuseyaw = 0;
4654                 }
4655         }
4656
4657         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]);
4658         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]);
4659 }
4660
4661 static void Mod_Q3BSP_LoadPVS(lump_t *l)
4662 {
4663         q3dpvs_t *in;
4664         int totalchains;
4665
4666         if (l->filelen == 0)
4667         {
4668                 int i;
4669                 // unvised maps often have cluster indices even without pvs, so check
4670                 // leafs to find real number of clusters
4671                 loadmodel->brush.num_pvsclusters = 1;
4672                 for (i = 0;i < loadmodel->brush.num_leafs;i++)
4673                         loadmodel->brush.num_pvsclusters = max(loadmodel->brush.num_pvsclusters, loadmodel->brush.data_leafs[i].clusterindex + 1);
4674
4675                 // create clusters
4676                 loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters + 7) / 8;
4677                 totalchains = loadmodel->brush.num_pvsclusterbytes * loadmodel->brush.num_pvsclusters;
4678                 loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, totalchains);
4679                 memset(loadmodel->brush.data_pvsclusters, 0xFF, totalchains);
4680                 return;
4681         }
4682
4683         in = (void *)(mod_base + l->fileofs);
4684         if (l->filelen < 9)
4685                 Host_Error("Mod_Q3BSP_LoadPVS: funny lump size in %s",loadmodel->name);
4686
4687         loadmodel->brush.num_pvsclusters = LittleLong(in->numclusters);
4688         loadmodel->brush.num_pvsclusterbytes = LittleLong(in->chainlength);
4689         if (loadmodel->brush.num_pvsclusterbytes < ((loadmodel->brush.num_pvsclusters + 7) / 8))
4690                 Host_Error("Mod_Q3BSP_LoadPVS: (chainlength = %i) < ((numclusters = %i) + 7) / 8\n", loadmodel->brush.num_pvsclusterbytes, loadmodel->brush.num_pvsclusters);
4691         totalchains = loadmodel->brush.num_pvsclusterbytes * loadmodel->brush.num_pvsclusters;
4692         if (l->filelen < totalchains + (int)sizeof(*in))
4693                 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);
4694
4695         loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, totalchains);
4696         memcpy(loadmodel->brush.data_pvsclusters, (qbyte *)(in + 1), totalchains);
4697 }
4698
4699 static void Mod_Q3BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, vec_t radius)
4700 {
4701         // FIXME: finish this code
4702         VectorCopy(in, out);
4703 }
4704
4705 static void Mod_Q3BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
4706 {
4707         int i, j, k, index[3];
4708         float transformed[3], blend1, blend2, blend, yaw, pitch, sinpitch;
4709         q3dlightgrid_t *a, *s;
4710         // FIXME: write this
4711         if (!model->brushq3.num_lightgrid)
4712         {
4713                 ambientcolor[0] = 1;
4714                 ambientcolor[1] = 1;
4715                 ambientcolor[2] = 1;
4716                 return;
4717         }
4718         Matrix4x4_Transform(&model->brushq3.num_lightgrid_indexfromworld, p, transformed);
4719         //Matrix4x4_Print(&model->brushq3.num_lightgrid_indexfromworld);
4720         //Con_Printf("%f %f %f transformed %f %f %f clamped ", p[0], p[1], p[2], transformed[0], transformed[1], transformed[2]);
4721         transformed[0] = bound(0, transformed[0], model->brushq3.num_lightgrid_isize[0] - 1);
4722         transformed[1] = bound(0, transformed[1], model->brushq3.num_lightgrid_isize[1] - 1);
4723         transformed[2] = bound(0, transformed[2], model->brushq3.num_lightgrid_isize[2] - 1);
4724         index[0] = (int)floor(transformed[0]);
4725         index[1] = (int)floor(transformed[1]);
4726         index[2] = (int)floor(transformed[2]);
4727         //Con_Printf("%f %f %f index %i %i %i:\n", transformed[0], transformed[1], transformed[2], index[0], index[1], index[2]);
4728         // now lerp the values
4729         VectorClear(diffusenormal);
4730         a = &model->brushq3.data_lightgrid[(index[2] * model->brushq3.num_lightgrid_isize[1] + index[1]) * model->brushq3.num_lightgrid_isize[0] + index[0]];
4731         for (k = 0;k < 2;k++)
4732         {
4733                 blend1 = (k ? (transformed[2] - index[2]) : (1 - (transformed[2] - index[2])));
4734                 if (blend1 < 0.001f || index[2] + k >= model->brushq3.num_lightgrid_isize[2])
4735                         continue;
4736                 for (j = 0;j < 2;j++)
4737                 {
4738                         blend2 = blend1 * (j ? (transformed[1] - index[1]) : (1 - (transformed[1] - index[1])));
4739                         if (blend2 < 0.001f || index[1] + j >= model->brushq3.num_lightgrid_isize[1])
4740                                 continue;
4741                         for (i = 0;i < 2;i++)
4742                         {
4743                                 blend = blend2 * (i ? (transformed[0] - index[0]) : (1 - (transformed[0] - index[0])));
4744                                 if (blend < 0.001f || index[0] + i >= model->brushq3.num_lightgrid_isize[0])
4745                                         continue;
4746                                 s = a + (k * model->brushq3.num_lightgrid_isize[1] + j) * model->brushq3.num_lightgrid_isize[0] + i;
4747                                 VectorMA(ambientcolor, blend * (1.0f / 128.0f), s->ambientrgb, ambientcolor);
4748                                 VectorMA(diffusecolor, blend * (1.0f / 128.0f), s->diffusergb, diffusecolor);
4749                                 pitch = s->diffusepitch * M_PI / 128;
4750                                 yaw = s->diffuseyaw * M_PI / 128;
4751                                 sinpitch = sin(pitch);
4752                                 diffusenormal[0] += blend * (cos(yaw) * sinpitch);
4753                                 diffusenormal[1] += blend * (sin(yaw) * sinpitch);
4754                                 diffusenormal[2] += blend * (cos(pitch));
4755                                 //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)));
4756                         }
4757                 }
4758         }
4759         VectorNormalize(diffusenormal);
4760         //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]);
4761 }
4762
4763 static void Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace_t *trace, model_t *model, mnode_t *node, const vec3_t point, int markframe)
4764 {
4765         int i;
4766         mleaf_t *leaf;
4767         colbrushf_t *brush;
4768         // find which leaf the point is in
4769         while (node->plane)
4770                 node = node->children[DotProduct(point, node->plane->normal) < node->plane->dist];
4771         // point trace the brushes
4772         leaf = (mleaf_t *)node;
4773         for (i = 0;i < leaf->numleafbrushes;i++)
4774         {
4775                 brush = model->brushq3.data_brushes[leaf->firstleafbrush[i]].colbrushf;
4776                 if (brush && brush->markframe != markframe && BoxesOverlap(point, point, brush->mins, brush->maxs))
4777                 {
4778                         brush->markframe = markframe;
4779                         Collision_TracePointBrushFloat(trace, point, brush);
4780                 }
4781         }
4782         // can't do point traces on curves (they have no thickness)
4783 }
4784
4785 static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, model_t *model, mnode_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)
4786 {
4787         int i, startside, endside;
4788         float dist1, dist2, midfrac, mid[3], nodesegmentmins[3], nodesegmentmaxs[3];
4789         mleaf_t *leaf;
4790         q3msurface_t *face;
4791         colbrushf_t *brush;
4792         if (startfrac > trace->realfraction)
4793                 return;
4794         // note: all line fragments past first impact fraction are ignored
4795         if (VectorCompare(start, end))
4796         {
4797                 // find which leaf the point is in
4798                 while (node->plane)
4799                         node = node->children[DotProduct(start, node->plane->normal) < node->plane->dist];
4800         }
4801         else
4802         {
4803                 // find which nodes the line is in and recurse for them
4804                 while (node->plane)
4805                 {
4806                         // recurse down node sides
4807                         dist1 = PlaneDiff(start, node->plane);
4808                         dist2 = PlaneDiff(end, node->plane);
4809                         startside = dist1 < 0;
4810                         endside = dist2 < 0;
4811                         if (startside == endside)
4812                         {
4813                                 // most of the time the line fragment is on one side of the plane
4814                                 node = node->children[startside];
4815                         }
4816                         else
4817                         {
4818                                 // line crosses node plane, split the line
4819                                 midfrac = dist1 / (dist1 - dist2);
4820                                 VectorLerp(start, midfrac, end, mid);
4821                                 // take the near side first
4822                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
4823                                 if (midfrac <= trace->realfraction)
4824                                         Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
4825                                 return;
4826                         }
4827                 }
4828         }
4829         // hit a leaf
4830         nodesegmentmins[0] = min(start[0], end[0]);
4831         nodesegmentmins[1] = min(start[1], end[1]);
4832         nodesegmentmins[2] = min(start[2], end[2]);
4833         nodesegmentmaxs[0] = max(start[0], end[0]);
4834         nodesegmentmaxs[1] = max(start[1], end[1]);
4835         nodesegmentmaxs[2] = max(start[2], end[2]);
4836         // line trace the brushes
4837         leaf = (mleaf_t *)node;
4838         for (i = 0;i < leaf->numleafbrushes;i++)
4839         {
4840                 brush = model->brushq3.data_brushes[leaf->firstleafbrush[i]].colbrushf;
4841                 if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
4842                 {
4843                         brush->markframe = markframe;
4844                         Collision_TraceLineBrushFloat(trace, linestart, lineend, brush, brush);
4845                         if (startfrac > trace->realfraction)
4846                                 return;
4847                 }
4848         }
4849         // can't do point traces on curves (they have no thickness)
4850         if (mod_q3bsp_curves_collisions.integer && !VectorCompare(start, end))
4851         {
4852                 // line trace the curves
4853                 for (i = 0;i < leaf->numleaffaces;i++)
4854                 {
4855                         face = model->brushq3.data_faces + leaf->firstleafface[i];
4856                         if (face->mesh.num_collisiontriangles && face->collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
4857                         {
4858                                 face->collisionmarkframe = markframe;
4859                                 Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, face->mesh.num_collisiontriangles, face->mesh.data_collisionelement3i, face->mesh.data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
4860                                 if (startfrac > trace->realfraction)
4861                                         return;
4862                         }
4863                 }
4864         }
4865 }
4866
4867 static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, model_t *model, mnode_t *node, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
4868 {
4869         int i;
4870         //int sides;
4871         float nodesegmentmins[3], nodesegmentmaxs[3];
4872         mleaf_t *leaf;
4873         colbrushf_t *brush;
4874         q3msurface_t *face;
4875         /*
4876                 // find which nodes the line is in and recurse for them
4877                 while (node->plane)
4878                 {
4879                         // recurse down node sides
4880                         int startside, endside;
4881                         float dist1near, dist1far, dist2near, dist2far;
4882                         BoxPlaneCornerDistances(thisbrush_start->mins, thisbrush_start->maxs, node->plane, &dist1near, &dist1far);
4883                         BoxPlaneCornerDistances(thisbrush_end->mins, thisbrush_end->maxs, node->plane, &dist2near, &dist2far);
4884                         startside = dist1near < 0;
4885                         startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
4886                         endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
4887                         if (startside == 2 || endside == 2)
4888                         {
4889                                 // brushes cross plane
4890                                 // do not clip anything, just take both sides
4891                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4892                                 node = node->children[1];
4893                                 continue;
4894                         }
4895                         if (startside == 0)
4896                         {
4897                                 if (endside == 0)
4898                                 {
4899                                         node = node->children[0];
4900                                         continue;
4901                                 }
4902                                 else
4903                                 {
4904                                         //midf0 = dist1near / (dist1near - dist2near);
4905                                         //midf1 = dist1far / (dist1far - dist2far);
4906                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4907                                         node = node->children[1];
4908                                         continue;
4909                                 }
4910                         }
4911                         else
4912                         {
4913                                 if (endside == 0)
4914                                 {
4915                                         //midf0 = dist1near / (dist1near - dist2near);
4916                                         //midf1 = dist1far / (dist1far - dist2far);
4917                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4918                                         node = node->children[1];
4919                                         continue;
4920                                 }
4921                                 else
4922                                 {
4923                                         node = node->children[1];
4924                                         continue;
4925                                 }
4926                         }
4927
4928                         if (dist1near <  0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4929                         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;}
4930                         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;}
4931                         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;}
4932                         if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4933                         if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){}
4934                         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;}
4935                         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;}
4936                         if (dist1near >= 0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4937                         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;}
4938                         if (dist1near >= 0 && dist2near <  0 && dist1far >= 0 && dist2far <  0){}
4939                         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;}
4940                         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;}
4941                         if (dist1near >= 0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){node = node->children[0];continue;}
4942                         if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far <  0){node = node->children[0];continue;}
4943                         if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far >= 0){node = node->children[0];continue;}
4944                         {
4945                                 if (dist2near < 0) // d1n<0 && d2n<0
4946                                 {
4947                                         if (dist2near < 0) // d1n<0 && d2n<0
4948                                         {
4949                                                 if (dist2near < 0) // d1n<0 && d2n<0
4950                                                 {
4951                                                 }
4952                                                 else // d1n<0 && d2n>0
4953                                                 {
4954                                                 }
4955                                         }
4956                                         else // d1n<0 && d2n>0
4957                                         {
4958                                                 if (dist2near < 0) // d1n<0 && d2n<0
4959                                                 {
4960                                                 }
4961                                                 else // d1n<0 && d2n>0
4962                                                 {
4963                                                 }
4964                                         }
4965                                 }
4966                                 else // d1n<0 && d2n>0
4967                                 {
4968                                 }
4969                         }
4970                         else // d1n>0
4971                         {
4972                                 if (dist2near < 0) // d1n>0 && d2n<0
4973                                 {
4974                                 }
4975                                 else // d1n>0 && d2n>0
4976                                 {
4977                                 }
4978                         }
4979                         if (dist1near < 0 == dist1far < 0 == dist2near < 0 == dist2far < 0)
4980                         {
4981                                 node = node->children[startside];
4982                                 continue;
4983                         }
4984                         if (dist1near < dist2near)
4985                         {
4986                                 // out
4987                                 if (dist1near >= 0)
4988                                 {
4989                                         node = node->children[0];
4990                                         continue;
4991                                 }
4992                                 if (dist2far < 0)
4993                                 {
4994                                         node = node->children[1];
4995                                         continue;
4996                                 }
4997                                 // dist1near < 0 && dist2far >= 0
4998                         }
4999                         else
5000                         {
5001                                 // in
5002                         }
5003                         startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
5004                         endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
5005                         if (startside == 2 || endside == 2)
5006                         {
5007                                 // brushes cross plane
5008                                 // do not clip anything, just take both sides
5009                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5010                                 node = node->children[1];
5011                         }
5012                         else if (startside == endside)
5013                                 node = node->children[startside];
5014                         else if (startside == 0) // endside = 1 (start infront, end behind)
5015                         {
5016                         }
5017                         else // startside == 1 endside = 0 (start behind, end infront)
5018                         {
5019                         }
5020                         == endside)
5021                         {
5022                                 if (startside < 2)
5023                                         node = node->children[startside];
5024                                 else
5025                                 {
5026                                         // start and end brush cross plane
5027                                 }
5028                         }
5029                         else
5030                         {
5031                         }
5032                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5033                                 node = node->children[1];
5034                         else if (dist1near < 0 && dist1far < 0 && dist2near >= 0 && dist2far >= 0)
5035                         else if (dist1near >= 0 && dist1far >= 0 && dist2near < 0 && dist2far < 0)
5036                         else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
5037                                 node = node->children[0];
5038                         else
5039                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5040                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5041                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5042                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5043                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5044                         {
5045                         }
5046                         else if (dist1near >= 0 && dist1far >= 0)
5047                         {
5048                         }
5049                         else // mixed (lying on plane)
5050                         {
5051                         }
5052                         {
5053                                 if (dist2near < 0 && dist2far < 0)
5054                                 {
5055                                 }
5056                                 else
5057                                         node = node->children[1];
5058                         }
5059                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5060                                 node = node->children[0];
5061                         else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
5062                                 node = node->children[1];
5063                         else
5064                         {
5065                                 // both sides
5066                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5067                                 node = node->children[1];
5068                         }
5069                         sides = dist1near || dist1near < 0 | dist1far < 0 | dist2near < 0 | dist
5070                         startside = dist1 < 0;
5071                         endside = dist2 < 0;
5072                         if (startside == endside)
5073                         {
5074                                 // most of the time the line fragment is on one side of the plane
5075                                 node = node->children[startside];
5076                         }
5077                         else
5078                         {
5079                                 // line crosses node plane, split the line
5080                                 midfrac = dist1 / (dist1 - dist2);
5081                                 VectorLerp(start, midfrac, end, mid);
5082                                 // take the near side first
5083                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5084                                 if (midfrac <= trace->fraction)
5085                                         Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5086                                 return;
5087                         }
5088                 }
5089         */
5090 #if 1
5091         for (;;)
5092         {
5093                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5094                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5095                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5096                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5097                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5098                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5099                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5100                         return;
5101                 if (!node->plane)
5102                         break;
5103                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5104                 node = node->children[1];
5105         }
5106 #elif 0
5107         // FIXME: could be made faster by copying TraceLine code and making it use
5108         // box plane distances...  (variant on the BoxOnPlaneSide code)
5109         for (;;)
5110         {
5111                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5112                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5113                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5114                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5115                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5116                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5117                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5118                         return;
5119                 if (!node->plane)
5120                         break;
5121                 if (mod_q3bsp_debugtracebrush.integer == 2)
5122                 {
5123                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5124                         node = node->children[1];
5125                         continue;
5126                 }
5127                 else if (mod_q3bsp_debugtracebrush.integer == 1)
5128                 {
5129                         // recurse down node sides
5130                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5131                         if (sides == 3)
5132                         {
5133                                 // segment box crosses plane
5134                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5135                                 node = node->children[1];
5136                                 continue;
5137                         }
5138                         // take whichever side the segment box is on
5139                         node = node->children[sides - 1];
5140                         continue;
5141                 }
5142                 else
5143                 {
5144                         // recurse down node sides
5145                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5146                         if (sides == 3)
5147                         {
5148                                 // segment box crosses plane
5149                                 // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
5150                                 sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, node->plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, node->plane);
5151                                 if (sides == 3)
5152                                 {
5153                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5154                                         node = node->children[1];
5155                                         continue;
5156                                 }
5157                         }
5158                         // take whichever side the segment box is on
5159                         node = node->children[sides - 1];
5160                         continue;
5161                 }
5162                 return;
5163         }
5164 #else
5165         // FIXME: could be made faster by copying TraceLine code and making it use
5166         // box plane distances...  (variant on the BoxOnPlaneSide code)
5167         for (;;)
5168         {
5169                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5170                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5171                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5172                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5173                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5174                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5175                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5176                         return;
5177                 if (!node->plane)
5178                         break;
5179                 if (mod_q3bsp_debugtracebrush.integer == 2)
5180                 {
5181                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5182                         node = node->children[1];
5183                 }
5184                 else if (mod_q3bsp_debugtracebrush.integer == 1)
5185                 {
5186                         // recurse down node sides
5187                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5188                         if (sides == 3)
5189                         {
5190                                 // segment box crosses plane
5191                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5192                                 node = node->children[1];
5193                         }
5194                         else
5195                         {
5196                                 // take whichever side the segment box is on
5197                                 node = node->children[sides - 1];
5198                         }
5199                 }
5200                 else
5201                 {
5202                         // recurse down node sides
5203                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5204                         if (sides == 3)
5205                         {
5206                                 // segment box crosses plane
5207                                 // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
5208                                 sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, node->plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, node->plane);
5209                                 if (sides == 3)
5210                                 {
5211                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5212                                         sides = 2;
5213                                 }
5214                         }
5215                         // take whichever side the segment box is on
5216                         node = node->children[sides - 1];
5217                 }
5218         }
5219 #endif
5220         // hit a leaf
5221         leaf = (mleaf_t *)node;
5222         for (i = 0;i < leaf->numleafbrushes;i++)
5223         {
5224                 brush = model->brushq3.data_brushes[leaf->firstleafbrush[i]].colbrushf;
5225                 if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
5226                 {
5227                         brush->markframe = markframe;
5228                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, brush, brush);
5229                 }
5230         }
5231         if (mod_q3bsp_curves_collisions.integer)
5232         {
5233                 for (i = 0;i < leaf->numleaffaces;i++)
5234                 {
5235                         face = model->brushq3.data_faces + leaf->firstleafface[i];
5236                         if (face->mesh.num_collisiontriangles && face->collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
5237                         {
5238                                 face->collisionmarkframe = markframe;
5239                                 Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->mesh.num_collisiontriangles, face->mesh.data_collisionelement3i, face->mesh.data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5240                         }
5241                 }
5242         }
5243 }
5244
5245 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)
5246 {
5247         int i;
5248         float segmentmins[3], segmentmaxs[3];
5249         colbrushf_t *thisbrush_start, *thisbrush_end;
5250         matrix4x4_t startmatrix, endmatrix;
5251         static int markframe = 0;
5252         q3msurface_t *face;
5253         memset(trace, 0, sizeof(*trace));
5254         trace->fraction = 1;
5255         trace->realfraction = 1;
5256         trace->hitsupercontentsmask = hitsupercontentsmask;
5257         Matrix4x4_CreateIdentity(&startmatrix);
5258         Matrix4x4_CreateIdentity(&endmatrix);
5259         segmentmins[0] = min(boxstartmins[0], boxendmins[0]);
5260         segmentmins[1] = min(boxstartmins[1], boxendmins[1]);
5261         segmentmins[2] = min(boxstartmins[2], boxendmins[2]);
5262         segmentmaxs[0] = max(boxstartmaxs[0], boxendmaxs[0]);
5263         segmentmaxs[1] = max(boxstartmaxs[1], boxendmaxs[1]);
5264         segmentmaxs[2] = max(boxstartmaxs[2], boxendmaxs[2]);
5265         if (mod_q3bsp_optimizedtraceline.integer && VectorCompare(boxstartmins, boxstartmaxs) && VectorCompare(boxendmins, boxendmaxs))
5266         {
5267                 if (VectorCompare(boxstartmins, boxendmins))
5268                 {
5269                         // point trace
5270                         if (model->brush.submodel)
5271                         {
5272                                 for (i = 0;i < model->brushq3.data_models[model->brush.submodel].numbrushes;i++)
5273                                         if (model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf)
5274                                                 Collision_TracePointBrushFloat(trace, boxstartmins, model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf);
5275                         }
5276                         else
5277                                 Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace, model, model->brush.data_nodes, boxstartmins, ++markframe);
5278                 }
5279                 else
5280                 {
5281                         // line trace
5282                         if (model->brush.submodel)
5283                         {
5284                                 for (i = 0;i < model->brushq3.data_models[model->brush.submodel].numbrushes;i++)
5285                                         if (model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf)
5286                                                 Collision_TraceLineBrushFloat(trace, boxstartmins, boxendmins, model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf, model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf);
5287                                 if (mod_q3bsp_curves_collisions.integer)
5288                                 {
5289                                         for (i = 0;i < model->brushq3.data_models[model->brush.submodel].numfaces;i++)
5290                                         {
5291                                                 face = model->brushq3.data_models[model->brush.submodel].firstface + i;
5292                                                 if (face->mesh.num_collisiontriangles)
5293                                                         Collision_TraceLineTriangleMeshFloat(trace, boxstartmins, boxendmins, face->mesh.num_collisiontriangles, face->mesh.data_collisionelement3i, face->mesh.data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5294                                         }
5295                                 }
5296                         }
5297                         else
5298                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model, model->brush.data_nodes, boxstartmins, boxendmins, 0, 1, boxstartmins, boxendmins, ++markframe, segmentmins, segmentmaxs);
5299                 }
5300         }
5301         else
5302         {
5303                 // box trace, performed as brush trace
5304                 thisbrush_start = Collision_BrushForBox(&startmatrix, boxstartmins, boxstartmaxs);
5305                 thisbrush_end = Collision_BrushForBox(&endmatrix, boxendmins, boxendmaxs);
5306                 if (model->brush.submodel)
5307                 {
5308                         for (i = 0;i < model->brushq3.data_models[model->brush.submodel].numbrushes;i++)
5309                                 if (model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf)
5310                                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf, model->brushq3.data_models[model->brush.submodel].firstbrush[i].colbrushf);
5311                         if (mod_q3bsp_curves_collisions.integer)
5312                         {
5313                                 for (i = 0;i < model->brushq3.data_models[model->brush.submodel].numfaces;i++)
5314                                 {
5315                                         face = model->brushq3.data_models[model->brush.submodel].firstface + i;
5316                                         if (face->mesh.num_collisiontriangles)
5317                                                 Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->mesh.num_collisiontriangles, face->mesh.data_collisionelement3i, face->mesh.data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5318                                 }
5319                         }
5320                 }
5321                 else
5322                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, model->brush.data_nodes, thisbrush_start, thisbrush_end, ++markframe, segmentmins, segmentmaxs);
5323         }
5324 }
5325
5326 static int Mod_Q3BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
5327 {
5328         int clusterindex, side, nodestackindex = 0;
5329         mnode_t *node, *nodestack[1024];
5330         node = model->brush.data_nodes;
5331         if (!model->brush.num_pvsclusters)
5332                 return true;
5333         for (;;)
5334         {
5335                 if (node->plane)
5336                 {
5337                         // node - recurse down the BSP tree
5338                         side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
5339                         if (side < 2)
5340                         {
5341                                 // box is on one side of plane, take that path
5342                                 node = node->children[side];
5343                         }
5344                         else
5345                         {
5346                                 // box crosses plane, take one path and remember the other
5347                                 if (nodestackindex < 1024)
5348                                         nodestack[nodestackindex++] = node->children[0];
5349                                 node = node->children[1];
5350                         }
5351                 }
5352                 else
5353                 {
5354                         // leaf - check cluster bit
5355                         clusterindex = ((mleaf_t *)node)->clusterindex;
5356 #if 0
5357                         if (clusterindex >= model->brush.num_pvsclusters)
5358                         {
5359                                 Con_Printf("%i >= %i\n", clusterindex, model->brush.num_pvsclusters);
5360                                 return true;
5361                         }
5362 #endif
5363                         if (CHECKPVSBIT(pvs, clusterindex))
5364                         {
5365                                 // it is visible, return immediately with the news
5366                                 return true;
5367                         }
5368                         else
5369                         {
5370                                 // nothing to see here, try another path we didn't take earlier
5371                                 if (nodestackindex == 0)
5372                                         break;
5373                                 node = nodestack[--nodestackindex];
5374                         }
5375                 }
5376         }
5377         // it is not visible
5378         return false;
5379 }
5380
5381 //Returns PVS data for a given point
5382 //(note: can return NULL)
5383 static qbyte *Mod_Q3BSP_GetPVS(model_t *model, const vec3_t p)
5384 {
5385         mnode_t *node;
5386         Mod_CheckLoaded(model);
5387         node = model->brush.data_nodes;
5388         while (node->plane)
5389                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
5390         if (((mleaf_t *)node)->clusterindex >= 0)
5391                 return model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
5392         else
5393                 return NULL;
5394 }
5395
5396 static void Mod_Q3BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbytes, mnode_t *node)
5397 {
5398         while (node->plane)
5399         {
5400                 float d = PlaneDiff(org, node->plane);
5401                 if (d > radius)
5402                         node = node->children[0];
5403                 else if (d < -radius)
5404                         node = node->children[1];
5405                 else
5406                 {
5407                         // go down both sides
5408                         Mod_Q3BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
5409                         node = node->children[1];
5410                 }
5411         }
5412         // if this leaf is in a cluster, accumulate the pvs bits
5413         if (((mleaf_t *)node)->clusterindex >= 0)
5414         {
5415                 int i;
5416                 qbyte *pvs = model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
5417                 for (i = 0;i < pvsbytes;i++)
5418                         pvsbuffer[i] |= pvs[i];
5419         }
5420 }
5421
5422 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
5423 //of the given point.
5424 static int Mod_Q3BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbufferlength)
5425 {
5426         int bytes = model->brush.num_pvsclusterbytes;
5427         bytes = min(bytes, pvsbufferlength);
5428         if (r_novis.integer || !model->brush.num_pvsclusters || !Mod_Q3BSP_GetPVS(model, org))
5429         {
5430                 memset(pvsbuffer, 0xFF, bytes);
5431                 return bytes;
5432         }
5433         memset(pvsbuffer, 0, bytes);
5434         Mod_Q3BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brush.data_nodes);
5435         return bytes;
5436 }
5437
5438
5439 static int Mod_Q3BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents)
5440 {
5441         int supercontents = 0;
5442         if (nativecontents & CONTENTSQ3_SOLID)
5443                 supercontents |= SUPERCONTENTS_SOLID;
5444         if (nativecontents & CONTENTSQ3_WATER)
5445                 supercontents |= SUPERCONTENTS_WATER;
5446         if (nativecontents & CONTENTSQ3_SLIME)
5447                 supercontents |= SUPERCONTENTS_SLIME;
5448         if (nativecontents & CONTENTSQ3_LAVA)
5449                 supercontents |= SUPERCONTENTS_LAVA;
5450         if (nativecontents & CONTENTSQ3_BODY)
5451                 supercontents |= SUPERCONTENTS_BODY;
5452         if (nativecontents & CONTENTSQ3_CORPSE)
5453                 supercontents |= SUPERCONTENTS_CORPSE;
5454         if (nativecontents & CONTENTSQ3_NODROP)
5455                 supercontents |= SUPERCONTENTS_NODROP;
5456         return supercontents;
5457 }
5458
5459 static int Mod_Q3BSP_NativeContentsFromSuperContents(model_t *model, int supercontents)
5460 {
5461         int nativecontents = 0;
5462         if (supercontents & SUPERCONTENTS_SOLID)
5463                 nativecontents |= CONTENTSQ3_SOLID;
5464         if (supercontents & SUPERCONTENTS_WATER)
5465                 nativecontents |= CONTENTSQ3_WATER;
5466         if (supercontents & SUPERCONTENTS_SLIME)
5467                 nativecontents |= CONTENTSQ3_SLIME;
5468         if (supercontents & SUPERCONTENTS_LAVA)
5469                 nativecontents |= CONTENTSQ3_LAVA;
5470         if (supercontents & SUPERCONTENTS_BODY)
5471                 nativecontents |= CONTENTSQ3_BODY;
5472         if (supercontents & SUPERCONTENTS_CORPSE)
5473                 nativecontents |= CONTENTSQ3_CORPSE;
5474         if (supercontents & SUPERCONTENTS_NODROP)
5475                 nativecontents |= CONTENTSQ3_NODROP;
5476         return nativecontents;
5477 }
5478
5479 void Mod_Q3BSP_RecursiveFindNumLeafs(mnode_t *node)
5480 {
5481         int numleafs;
5482         while (node->plane)
5483         {
5484                 Mod_Q3BSP_RecursiveFindNumLeafs(node->children[0]);
5485                 node = node->children[1];
5486         }
5487         numleafs = ((mleaf_t *)node - loadmodel->brush.data_leafs) + 1;
5488         if (loadmodel->brush.num_leafs < numleafs)
5489                 loadmodel->brush.num_leafs = numleafs;
5490 }
5491
5492 extern void R_Q3BSP_DrawSky(struct entity_render_s *ent);
5493 extern void R_Q3BSP_Draw(struct entity_render_s *ent);
5494 extern void R_Q3BSP_GetLightInfo(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, vec3_t outmins, vec3_t outmaxs, int *outclusterlist, qbyte *outclusterpvs, int *outnumclusterspointer, int *outsurfacelist, qbyte *outsurfacepvs, int *outnumsurfacespointer);
5495 extern void R_Q3BSP_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, int numsurfaces, const int *surfacelist);
5496 extern void R_Q3BSP_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, vec_t ambientscale, vec_t diffusescale, vec_t specularscale, int numsurfaces, const int *surfacelist);
5497 void Mod_Q3BSP_Load(model_t *mod, void *buffer)
5498 {
5499         int i, j, numshadowmeshtriangles;
5500         q3dheader_t *header;
5501         float corner[3], yawradius, modelradius;
5502         q3msurface_t *face;
5503
5504         mod->type = mod_brushq3;
5505         mod->numframes = 2; // although alternate textures are not supported it is annoying to complain about no such frame 1
5506         mod->numskins = 1;
5507
5508         header = (q3dheader_t *)buffer;
5509
5510         i = LittleLong(header->version);
5511         if (i != Q3BSPVERSION)
5512                 Host_Error("Mod_Q3BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q3BSPVERSION);
5513         if (mod->isworldmodel)
5514                 Cvar_SetValue("halflifebsp", false);
5515
5516         mod->soundfromcenter = true;
5517         mod->TraceBox = Mod_Q3BSP_TraceBox;
5518         mod->brush.SuperContentsFromNativeContents = Mod_Q3BSP_SuperContentsFromNativeContents;
5519         mod->brush.NativeContentsFromSuperContents = Mod_Q3BSP_NativeContentsFromSuperContents;
5520         mod->brush.GetPVS = Mod_Q3BSP_GetPVS;
5521         mod->brush.FatPVS = Mod_Q3BSP_FatPVS;
5522         mod->brush.BoxTouchingPVS = Mod_Q3BSP_BoxTouchingPVS;
5523         mod->brush.LightPoint = Mod_Q3BSP_LightPoint;
5524         mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation;
5525         //mod->DrawSky = R_Q3BSP_DrawSky;
5526         mod->Draw = R_Q3BSP_Draw;
5527         mod->GetLightInfo = R_Q3BSP_GetLightInfo;
5528         mod->DrawShadowVolume = R_Q3BSP_DrawShadowVolume;
5529         mod->DrawLight = R_Q3BSP_DrawLight;
5530
5531         mod_base = (qbyte *)header;
5532
5533         // swap all the lumps
5534         header->ident = LittleLong(header->ident);
5535         header->version = LittleLong(header->version);
5536         for (i = 0;i < Q3HEADER_LUMPS;i++)
5537         {
5538                 header->lumps[i].fileofs = LittleLong(header->lumps[i].fileofs);
5539                 header->lumps[i].filelen = LittleLong(header->lumps[i].filelen);
5540         }
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->mesh.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->mesh.data_vertex3f, NULL, NULL, NULL, NULL, face->mesh.num_triangles, face->mesh.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         loadmodel->brush.num_leafs = 0;
5575         Mod_Q3BSP_RecursiveFindNumLeafs(loadmodel->brush.data_nodes);
5576
5577         mod = loadmodel;
5578         for (i = 0;i < loadmodel->brushq3.num_models;i++)
5579         {
5580                 if (i > 0)
5581                 {
5582                         char name[10];
5583                         // LordHavoc: only register submodels if it is the world
5584                         // (prevents external bsp models from replacing world submodels with
5585                         //  their own)
5586                         if (!loadmodel->isworldmodel)
5587                                 continue;
5588                         // duplicate the basic information
5589                         sprintf(name, "*%i", i);
5590                         mod = Mod_FindName(name);
5591                         *mod = *loadmodel;
5592                         strcpy(mod->name, name);
5593                         // textures and memory belong to the main model
5594                         mod->texturepool = NULL;
5595                         mod->mempool = NULL;
5596                         mod->brush.GetPVS = NULL;
5597                         mod->brush.FatPVS = NULL;
5598                         mod->brush.BoxTouchingPVS = NULL;
5599                         mod->brush.LightPoint = NULL;
5600                         mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation;
5601                 }
5602                 mod->brush.submodel = i;
5603
5604                 // make the model surface list (used by shadowing/lighting)
5605                 mod->nummodelsurfaces = mod->brushq3.data_models[i].numfaces;
5606                 mod->surfacelist = Mem_Alloc(loadmodel->mempool, mod->nummodelsurfaces * sizeof(*mod->surfacelist));
5607                 for (j = 0;j < mod->nummodelsurfaces;j++)
5608                         mod->surfacelist[j] = (mod->brushq3.data_models[i].firstface - mod->brushq3.data_faces) + j;
5609
5610                 VectorCopy(mod->brushq3.data_models[i].mins, mod->normalmins);
5611                 VectorCopy(mod->brushq3.data_models[i].maxs, mod->normalmaxs);
5612                 corner[0] = max(fabs(mod->normalmins[0]), fabs(mod->normalmaxs[0]));
5613                 corner[1] = max(fabs(mod->normalmins[1]), fabs(mod->normalmaxs[1]));
5614                 corner[2] = max(fabs(mod->normalmins[2]), fabs(mod->normalmaxs[2]));
5615                 modelradius = sqrt(corner[0]*corner[0]+corner[1]*corner[1]+corner[2]*corner[2]);
5616                 yawradius = sqrt(corner[0]*corner[0]+corner[1]*corner[1]);
5617                 mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
5618                 mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
5619                 mod->yawmaxs[0] = mod->yawmaxs[1] = yawradius;
5620                 mod->yawmins[0] = mod->yawmins[1] = -yawradius;
5621                 mod->yawmins[2] = mod->normalmins[2];
5622                 mod->yawmaxs[2] = mod->normalmaxs[2];
5623                 mod->radius = modelradius;
5624                 mod->radius2 = modelradius * modelradius;
5625
5626                 for (j = 0;j < mod->brushq3.data_models[i].numfaces;j++)
5627                         if (mod->brushq3.data_models[i].firstface[j].texture->surfaceflags & Q3SURFACEFLAG_SKY)
5628                                 break;
5629                 if (j < mod->brushq3.data_models[i].numfaces)
5630                         mod->DrawSky = R_Q3BSP_DrawSky;
5631         }
5632 }
5633
5634 void Mod_IBSP_Load(model_t *mod, void *buffer)
5635 {
5636         int i = LittleLong(((int *)buffer)[1]);
5637         if (i == Q3BSPVERSION)
5638                 Mod_Q3BSP_Load(mod,buffer);
5639         else if (i == Q2BSPVERSION)
5640                 Mod_Q2BSP_Load(mod,buffer);
5641         else
5642                 Host_Error("Mod_IBSP_Load: unknown/unsupported version %i\n", i);
5643 }
5644
5645 void Mod_MAP_Load(model_t *mod, void *buffer)
5646 {
5647         Host_Error("Mod_MAP_Load: not yet implemented\n");
5648 }
5649