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