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
  25 // note: model_shared.c sets up r_notexture, and r_surf_notexture
  26
  27 qbyte mod_q1bsp_novis[(MAX_MAP_LEAFS + 7)/ 8];
  28
  29 //cvar_t r_subdivide_size = {CVAR_SAVE, "r_subdivide_size", "128"};
  30 cvar_t halflifebsp = {0, "halflifebsp", "0"};
  31 cvar_t r_novis = {0, "r_novis", "0"};
  32 cvar_t r_miplightmaps = {CVAR_SAVE, "r_miplightmaps", "0"};
  33 cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1"};
  34 cvar_t r_nosurftextures = {0, "r_nosurftextures", "0"};
  35 cvar_t r_sortsurfaces = {0, "r_sortsurfaces", "0"};
  36
  37 void Mod_BrushInit(void)
  38 {
  39 //      Cvar_RegisterVariable(&r_subdivide_size);
  40         Cvar_RegisterVariable(&halflifebsp);
  41         Cvar_RegisterVariable(&r_novis);
  42         Cvar_RegisterVariable(&r_miplightmaps);
  43         Cvar_RegisterVariable(&r_lightmaprgba);
  44         Cvar_RegisterVariable(&r_nosurftextures);
  45         Cvar_RegisterVariable(&r_sortsurfaces);
  46         memset(mod_q1bsp_novis, 0xff, sizeof(mod_q1bsp_novis));
  47 }
  48
  49 static mleaf_t *Mod_Q1BSP_PointInLeaf(model_t *model, const vec3_t p)
  50 {
  51         mnode_t *node;
  52
  53         if (model == NULL)
  54                 return NULL;
  55
  56         Mod_CheckLoaded(model);
  57
  58         // LordHavoc: modified to start at first clip node,
  59         // in other words: first node of the (sub)model
  60         node = model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode;
  61         while (node->contents == 0)
  62                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
  63
  64         return (mleaf_t *)node;
  65 }
  66
  67 /*
  68 static int Mod_Q1BSP_PointContents(model_t *model, const vec3_t p)
  69 {
  70         mnode_t *node;
  71
  72         if (model == NULL)
  73                 return CONTENTS_EMPTY;
  74
  75         Mod_CheckLoaded(model);
  76
  77         // LordHavoc: modified to start at first clip node,
  78         // in other words: first node of the (sub)model
  79         node = model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode;
  80         while (node->contents == 0)
  81                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
  82
  83         return ((mleaf_t *)node)->contents;
  84 }
  85 */
  86
  87 typedef struct findnonsolidlocationinfo_s
  88 {
  89         vec3_t center;
  90         vec_t radius;
  91         vec3_t nudge;
  92         vec_t bestdist;
  93         model_t *model;
  94 }
  95 findnonsolidlocationinfo_t;
  96
  97 #if 0
  98 extern cvar_t samelevel;
  99 #endif
 100 static void Mod_Q1BSP_FindNonSolidLocation_r_Leaf(findnonsolidlocationinfo_t *info, mleaf_t *leaf)
 101 {
 102         int i, surfnum, k, *tri, *mark;
 103         float dist, f, vert[3][3], edge[3][3], facenormal[3], edgenormal[3][3], point[3];
 104 #if 0
 105         float surfnormal[3];
 106 #endif
 107         msurface_t *surf;
 108         surfmesh_t *mesh;
 109         for (surfnum = 0, mark = leaf->firstmarksurface;surfnum < leaf->nummarksurfaces;surfnum++, mark++)
 110         {
 111                 surf = info->model->brushq1.surfaces + *mark;
 112                 if (surf->flags & SURF_SOLIDCLIP)
 113                 {
 114 #if 0
 115                         VectorCopy(surf->plane->normal, surfnormal);
 116                         if (surf->flags & SURF_PLANEBACK)
 117                                 VectorNegate(surfnormal, surfnormal);
 118 #endif
 119                         for (mesh = surf->mesh;mesh;mesh = mesh->chain)
 120                         {
 121                                 for (k = 0;k < mesh->numtriangles;k++)
 122                                 {
 123                                         tri = mesh->element3i + k * 3;
 124                                         VectorCopy((mesh->vertex3f + tri[0] * 3), vert[0]);
 125                                         VectorCopy((mesh->vertex3f + tri[1] * 3), vert[1]);
 126                                         VectorCopy((mesh->vertex3f + tri[2] * 3), vert[2]);
 127                                         VectorSubtract(vert[1], vert[0], edge[0]);
 128                                         VectorSubtract(vert[2], vert[1], edge[1]);
 129                                         CrossProduct(edge[1], edge[0], facenormal);
 130                                         if (facenormal[0] || facenormal[1] || facenormal[2])
 131                                         {
 132                                                 VectorNormalize(facenormal);
 133 #if 0
 134                                                 if (VectorDistance(facenormal, surfnormal) > 0.01f)
 135                                                         Con_Printf("a2! %f %f %f != %f %f %f\n", facenormal[0], facenormal[1], facenormal[2], surfnormal[0], surfnormal[1], surfnormal[2]);
 136 #endif
 137                                                 f = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
 138                                                 if (f <= info->bestdist && f >= -info->bestdist)
 139                                                 {
 140                                                         VectorSubtract(vert[0], vert[2], edge[2]);
 141                                                         VectorNormalize(edge[0]);
 142                                                         VectorNormalize(edge[1]);
 143                                                         VectorNormalize(edge[2]);
 144                                                         CrossProduct(facenormal, edge[0], edgenormal[0]);
 145                                                         CrossProduct(facenormal, edge[1], edgenormal[1]);
 146                                                         CrossProduct(facenormal, edge[2], edgenormal[2]);
 147 #if 0
 148                                                         if (samelevel.integer & 1)
 149                                                                 VectorNegate(edgenormal[0], edgenormal[0]);
 150                                                         if (samelevel.integer & 2)
 151                                                                 VectorNegate(edgenormal[1], edgenormal[1]);
 152                                                         if (samelevel.integer & 4)
 153                                                                 VectorNegate(edgenormal[2], edgenormal[2]);
 154                                                         for (i = 0;i < 3;i++)
 155                                                                 if (DotProduct(vert[0], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f
 156                                                                  || DotProduct(vert[1], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f
 157                                                                  || DotProduct(vert[2], edgenormal[i]) > DotProduct(vert[i], edgenormal[i]) + 0.1f)
 158                                                                         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]);
 159 #endif
 160                                                         // face distance
 161                                                         if (DotProduct(info->center, edgenormal[0]) < DotProduct(vert[0], edgenormal[0])
 162                                                          && DotProduct(info->center, edgenormal[1]) < DotProduct(vert[1], edgenormal[1])
 163                                                          && DotProduct(info->center, edgenormal[2]) < DotProduct(vert[2], edgenormal[2]))
 164                                                         {
 165                                                                 // we got lucky, the center is within the face
 166                                                                 dist = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
 167                                                                 if (dist < 0)
 168                                                                 {
 169                                                                         dist = -dist;
 170                                                                         if (info->bestdist > dist)
 171                                                                         {
 172                                                                                 info->bestdist = dist;
 173                                                                                 VectorScale(facenormal, (info->radius - -dist), info->nudge);
 174                                                                         }
 175                                                                 }
 176                                                                 else
 177                                                                 {
 178                                                                         if (info->bestdist > dist)
 179                                                                         {
 180                                                                                 info->bestdist = dist;
 181                                                                                 VectorScale(facenormal, (info->radius - dist), info->nudge);
 182                                                                         }
 183                                                                 }
 184                                                         }
 185                                                         else
 186                                                         {
 187                                                                 // check which edge or vertex the center is nearest
 188                                                                 for (i = 0;i < 3;i++)
 189                                                                 {
 190                                                                         f = DotProduct(info->center, edge[i]);
 191                                                                         if (f >= DotProduct(vert[0], edge[i])
 192                                                                          && f <= DotProduct(vert[1], edge[i]))
 193                                                                         {
 194                                                                                 // on edge
 195                                                                                 VectorMA(info->center, -f, edge[i], point);
 196                                                                                 dist = sqrt(DotProduct(point, point));
 197                                                                                 if (info->bestdist > dist)
 198                                                                                 {
 199                                                                                         info->bestdist = dist;
 200                                                                                         VectorScale(point, (info->radius / dist), info->nudge);
 201                                                                                 }
 202                                                                                 // skip both vertex checks
 203                                                                                 // (both are further away than this edge)
 204                                                                                 i++;
 205                                                                         }
 206                                                                         else
 207                                                                         {
 208                                                                                 // not on edge, check first vertex of edge
 209                                                                                 VectorSubtract(info->center, vert[i], point);
 210                                                                                 dist = sqrt(DotProduct(point, point));
 211                                                                                 if (info->bestdist > dist)
 212                                                                                 {
 213                                                                                         info->bestdist = dist;
 214                                                                                         VectorScale(point, (info->radius / dist), info->nudge);
 215                                                                                 }
 216                                                                         }
 217                                                                 }
 218                                                         }
 219                                                 }
 220                                         }
 221                                 }
 222                         }
 223                 }
 224         }
 225 }
 226
 227 static void Mod_Q1BSP_FindNonSolidLocation_r(findnonsolidlocationinfo_t *info, mnode_t *node)
 228 {
 229         if (node->contents)
 230         {
 231                 if (((mleaf_t *)node)->nummarksurfaces)
 232                         Mod_Q1BSP_FindNonSolidLocation_r_Leaf(info, (mleaf_t *)node);
 233         }
 234         else
 235         {
 236                 float f = PlaneDiff(info->center, node->plane);
 237                 if (f >= -info->bestdist)
 238                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[0]);
 239                 if (f <= info->bestdist)
 240                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[1]);
 241         }
 242 }
 243
 244 static void Mod_Q1BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, float radius)
 245 {
 246         int i;
 247         findnonsolidlocationinfo_t info;
 248         if (model == NULL)
 249         {
 250                 VectorCopy(in, out);
 251                 return;
 252         }
 253         VectorCopy(in, info.center);
 254         info.radius = radius;
 255         info.model = model;
 256         i = 0;
 257         do
 258         {
 259                 VectorClear(info.nudge);
 260                 info.bestdist = radius;
 261                 Mod_Q1BSP_FindNonSolidLocation_r(&info, model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode);
 262                 VectorAdd(info.center, info.nudge, info.center);
 263         }
 264         while (info.bestdist < radius && ++i < 10);
 265         VectorCopy(info.center, out);
 266 }
 267
 268 typedef struct
 269 {
 270         // the hull we're tracing through
 271         const hull_t *hull;
 272
 273         // the trace structure to fill in
 274         trace_t *trace;
 275
 276         // start, end, and end - start (in model space)
 277         double start[3];
 278         double end[3];
 279         double dist[3];
 280 }
 281 RecursiveHullCheckTraceInfo_t;
 282
 283 // 1/32 epsilon to keep floating point happy
 284 #define DIST_EPSILON (0.03125)
 285
 286 #define HULLCHECKSTATE_EMPTY 0
 287 #define HULLCHECKSTATE_SOLID 1
 288 #define HULLCHECKSTATE_DONE 2
 289
 290 static int Mod_Q1BSP_RecursiveHullCheck(RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, double p1[3], double p2[3])
 291 {
 292         // status variables, these don't need to be saved on the stack when
 293         // recursing...  but are because this should be thread-safe
 294         // (note: tracing against a bbox is not thread-safe, yet)
 295         int ret;
 296         mplane_t *plane;
 297         double t1, t2;
 298
 299         // variables that need to be stored on the stack when recursing
 300         dclipnode_t *node;
 301         int side;
 302         double midf, mid[3];
 303
 304         // LordHavoc: a goto!  everyone flee in terror... :)
 305 loc0:
 306         // check for empty
 307         if (num < 0)
 308         {
 309                 t->trace->endcontents = num;
 310                 if (t->trace->thiscontents)
 311                 {
 312                         if (num == t->trace->thiscontents)
 313                                 t->trace->allsolid = false;
 314                         else
 315                         {
 316                                 // if the first leaf is solid, set startsolid
 317                                 if (t->trace->allsolid)
 318                                         t->trace->startsolid = true;
 319                                 return HULLCHECKSTATE_SOLID;
 320                         }
 321                         return HULLCHECKSTATE_EMPTY;
 322                 }
 323                 else
 324                 {
 325                         if (num != CONTENTS_SOLID)
 326                         {
 327                                 t->trace->allsolid = false;
 328                                 if (num == CONTENTS_EMPTY)
 329                                         t->trace->inopen = true;
 330                                 else
 331                                         t->trace->inwater = true;
 332                         }
 333                         else
 334                         {
 335                                 // if the first leaf is solid, set startsolid
 336                                 if (t->trace->allsolid)
 337                                         t->trace->startsolid = true;
 338                                 return HULLCHECKSTATE_SOLID;
 339                         }
 340                         return HULLCHECKSTATE_EMPTY;
 341                 }
 342         }
 343
 344         // find the point distances
 345         node = t->hull->clipnodes + num;
 346
 347         plane = t->hull->planes + node->planenum;
 348         if (plane->type < 3)
 349         {
 350                 t1 = p1[plane->type] - plane->dist;
 351                 t2 = p2[plane->type] - plane->dist;
 352         }
 353         else
 354         {
 355                 t1 = DotProduct (plane->normal, p1) - plane->dist;
 356                 t2 = DotProduct (plane->normal, p2) - plane->dist;
 357         }
 358
 359         if (t1 < 0)
 360         {
 361                 if (t2 < 0)
 362                 {
 363                         num = node->children[1];
 364                         goto loc0;
 365                 }
 366                 side = 1;
 367         }
 368         else
 369         {
 370                 if (t2 >= 0)
 371                 {
 372                         num = node->children[0];
 373                         goto loc0;
 374                 }
 375                 side = 0;
 376         }
 377
 378         // the line intersects, find intersection point
 379         // LordHavoc: this uses the original trace for maximum accuracy
 380         if (plane->type < 3)
 381         {
 382                 t1 = t->start[plane->type] - plane->dist;
 383                 t2 = t->end[plane->type] - plane->dist;
 384         }
 385         else
 386         {
 387                 t1 = DotProduct (plane->normal, t->start) - plane->dist;
 388                 t2 = DotProduct (plane->normal, t->end) - plane->dist;
 389         }
 390
 391         midf = t1 / (t1 - t2);
 392         midf = bound(p1f, midf, p2f);
 393         VectorMA(t->start, midf, t->dist, mid);
 394
 395         // recurse both sides, front side first
 396         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side], p1f, midf, p1, mid);
 397         // if this side is not empty, return what it is (solid or done)
 398         if (ret != HULLCHECKSTATE_EMPTY)
 399                 return ret;
 400
 401         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side ^ 1], midf, p2f, mid, p2);
 402         // if other side is not solid, return what it is (empty or done)
 403         if (ret != HULLCHECKSTATE_SOLID)
 404                 return ret;
 405
 406         // front is air and back is solid, this is the impact point...
 407         if (side)
 408         {
 409                 t->trace->plane.dist = -plane->dist;
 410                 VectorNegate (plane->normal, t->trace->plane.normal);
 411         }
 412         else
 413         {
 414                 t->trace->plane.dist = plane->dist;
 415                 VectorCopy (plane->normal, t->trace->plane.normal);
 416         }
 417
 418         // bias away from surface a bit
 419         t1 = DotProduct(t->trace->plane.normal, t->start) - (t->trace->plane.dist + DIST_EPSILON);
 420         t2 = DotProduct(t->trace->plane.normal, t->end) - (t->trace->plane.dist + DIST_EPSILON);
 421
 422         midf = t1 / (t1 - t2);
 423         t->trace->fraction = bound(0.0f, midf, 1.0);
 424
 425         return HULLCHECKSTATE_DONE;
 426 }
 427
 428 static void Mod_Q1BSP_TraceBox(struct model_s *model, trace_t *trace, const vec3_t boxstartmins, const vec3_t boxstartmaxs, const vec3_t boxendmins, const vec3_t boxendmaxs)
 429 {
 430         // this function currently only supports same size start and end
 431         double boxsize[3];
 432         RecursiveHullCheckTraceInfo_t rhc;
 433
 434         memset(&rhc, 0, sizeof(rhc));
 435         memset(trace, 0, sizeof(trace_t));
 436         rhc.trace = trace;
 437         rhc.trace->fraction = 1;
 438         rhc.trace->allsolid = true;
 439         VectorSubtract(boxstartmaxs, boxstartmins, boxsize);
 440         if (boxsize[0] < 3)
 441                 rhc.hull = &model->brushq1.hulls[0]; // 0x0x0
 442         else if (model->brushq1.ishlbsp)
 443         {
 444                 if (boxsize[0] <= 32)
 445                 {
 446                         if (boxsize[2] < 54) // pick the nearest of 36 or 72
 447                                 rhc.hull = &model->brushq1.hulls[3]; // 32x32x36
 448                         else
 449                                 rhc.hull = &model->brushq1.hulls[1]; // 32x32x72
 450                 }
 451                 else
 452                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x64
 453         }
 454         else
 455         {
 456                 if (boxsize[0] <= 32)
 457                         rhc.hull = &model->brushq1.hulls[1]; // 32x32x56
 458                 else
 459                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x88
 460         }
 461         VectorSubtract(boxstartmins, rhc.hull->clip_mins, rhc.start);
 462         VectorSubtract(boxendmins, rhc.hull->clip_mins, rhc.end);
 463         VectorSubtract(rhc.end, rhc.start, rhc.dist);
 464         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
 465 }
 466
 467 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)
 468 {
 469         int side, distz = endz - startz;
 470         float front, back;
 471         float mid;
 472
 473 loc0:
 474         if (node->contents < 0)
 475                 return false;           // didn't hit anything
 476
 477         switch (node->plane->type)
 478         {
 479         case PLANE_X:
 480                 node = node->children[x < node->plane->dist];
 481                 goto loc0;
 482         case PLANE_Y:
 483                 node = node->children[y < node->plane->dist];
 484                 goto loc0;
 485         case PLANE_Z:
 486                 side = startz < node->plane->dist;
 487                 if ((endz < node->plane->dist) == side)
 488                 {
 489                         node = node->children[side];
 490                         goto loc0;
 491                 }
 492                 // found an intersection
 493                 mid = node->plane->dist;
 494                 break;
 495         default:
 496                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
 497                 front += startz * node->plane->normal[2];
 498                 back += endz * node->plane->normal[2];
 499                 side = front < node->plane->dist;
 500                 if ((back < node->plane->dist) == side)
 501                 {
 502                         node = node->children[side];
 503                         goto loc0;
 504                 }
 505                 // found an intersection
 506                 mid = startz + distz * (front - node->plane->dist) / (front - back);
 507                 break;
 508         }
 509
 510         // go down front side
 511         if (node->children[side]->contents >= 0 && Mod_Q1BSP_LightPoint_RecursiveBSPNode(ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
 512                 return true;    // hit something
 513         else
 514         {
 515                 // check for impact on this node
 516                 if (node->numsurfaces)
 517                 {
 518                         int i, ds, dt;
 519                         msurface_t *surf;
 520
 521                         surf = cl.worldmodel->brushq1.surfaces + node->firstsurface;
 522                         for (i = 0;i < node->numsurfaces;i++, surf++)
 523                         {
 524                                 if (!(surf->flags & SURF_LIGHTMAP))
 525                                         continue;       // no lightmaps
 526
 527                                 ds = (int) (x * surf->texinfo->vecs[0][0] + y * surf->texinfo->vecs[0][1] + mid * surf->texinfo->vecs[0][2] + surf->texinfo->vecs[0][3]);
 528                                 dt = (int) (x * surf->texinfo->vecs[1][0] + y * surf->texinfo->vecs[1][1] + mid * surf->texinfo->vecs[1][2] + surf->texinfo->vecs[1][3]);
 529
 530                                 if (ds < surf->texturemins[0] || dt < surf->texturemins[1])
 531                                         continue;
 532
 533                                 ds -= surf->texturemins[0];
 534                                 dt -= surf->texturemins[1];
 535
 536                                 if (ds > surf->extents[0] || dt > surf->extents[1])
 537                                         continue;
 538
 539                                 if (surf->samples)
 540                                 {
 541                                         qbyte *lightmap;
 542                                         int 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;
 543                                         line3 = ((surf->extents[0]>>4)+1)*3;
 544                                         size3 = ((surf->extents[0]>>4)+1) * ((surf->extents[1]>>4)+1)*3; // LordHavoc: *3 for colored lighting
 545
 546                                         lightmap = surf->samples + ((dt>>4) * ((surf->extents[0]>>4)+1) + (ds>>4))*3; // LordHavoc: *3 for color
 547
 548                                         for (maps = 0;maps < MAXLIGHTMAPS && surf->styles[maps] != 255;maps++)
 549                                         {
 550                                                 scale = d_lightstylevalue[surf->styles[maps]];
 551                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
 552                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
 553                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
 554                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
 555                                                 lightmap += size3;
 556                                         }
 557
 558 /*
 559 LordHavoc: here's the readable version of the interpolation
 560 code, not quite as easy for the compiler to optimize...
 561
 562 dsfrac is the X position in the lightmap pixel, * 16
 563 dtfrac is the Y position in the lightmap pixel, * 16
 564 r00 is top left corner, r01 is top right corner
 565 r10 is bottom left corner, r11 is bottom right corner
 566 g and b are the same layout.
 567 r0 and r1 are the top and bottom intermediate results
 568
 569 first we interpolate the top two points, to get the top
 570 edge sample
 571
 572         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
 573         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
 574         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
 575
 576 then we interpolate the bottom two points, to get the
 577 bottom edge sample
 578
 579         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
 580         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
 581         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
 582
 583 then we interpolate the top and bottom samples to get the
 584 middle sample (the one which was requested)
 585
 586         r = (((r1-r0) * dtfrac) >> 4) + r0;
 587         g = (((g1-g0) * dtfrac) >> 4) + g0;
 588         b = (((b1-b0) * dtfrac) >> 4) + b0;
 589 */
 590
 591                                         ambientcolor[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
 592                                         ambientcolor[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
 593                                         ambientcolor[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
 594                                 }
 595                                 return true; // success
 596                         }
 597                 }
 598
 599                 // go down back side
 600                 node = node->children[side ^ 1];
 601                 startz = mid;
 602                 distz = endz - startz;
 603                 goto loc0;
 604         }
 605 }
 606
 607 void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
 608 {
 609         Mod_Q1BSP_LightPoint_RecursiveBSPNode(ambientcolor, diffusecolor, diffusenormal, cl.worldmodel->brushq1.nodes + cl.worldmodel->brushq1.hulls[0].firstclipnode, p[0], p[1], p[2], p[2] - 65536);
 610 }
 611
 612 static qbyte *Mod_Q1BSP_DecompressVis(model_t *model, qbyte *in)
 613 {
 614         static qbyte decompressed[MAX_MAP_LEAFS/8];
 615         int c;
 616         qbyte *out;
 617         int row;
 618
 619         row = (model->brushq1.numleafs+7)>>3;
 620         out = decompressed;
 621
 622         do
 623         {
 624                 if (*in)
 625                 {
 626                         *out++ = *in++;
 627                         continue;
 628                 }
 629
 630                 c = in[1];
 631                 in += 2;
 632                 while (c)
 633                 {
 634                         *out++ = 0;
 635                         c--;
 636                 }
 637         } while (out - decompressed < row);
 638
 639         return decompressed;
 640 }
 641
 642 static qbyte *Mod_Q1BSP_LeafPVS(model_t *model, mleaf_t *leaf)
 643 {
 644         if (r_novis.integer || leaf == model->brushq1.leafs || leaf->compressed_vis == NULL)
 645                 return mod_q1bsp_novis;
 646         return Mod_Q1BSP_DecompressVis(model, leaf->compressed_vis);
 647 }
 648
 649 static void Mod_Q1BSP_LoadTextures(lump_t *l)
 650 {
 651         int i, j, k, num, max, altmax, mtwidth, mtheight, *dofs, incomplete;
 652         miptex_t *dmiptex;
 653         texture_t *tx, *tx2, *anims[10], *altanims[10];
 654         dmiptexlump_t *m;
 655         qbyte *data, *mtdata;
 656         char name[256];
 657
 658         loadmodel->brushq1.textures = NULL;
 659
 660         if (!l->filelen)
 661                 return;
 662
 663         m = (dmiptexlump_t *)(mod_base + l->fileofs);
 664
 665         m->nummiptex = LittleLong (m->nummiptex);
 666
 667         // add two slots for notexture walls and notexture liquids
 668         loadmodel->brushq1.numtextures = m->nummiptex + 2;
 669         loadmodel->brushq1.textures = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numtextures * sizeof(texture_t));
 670
 671         // fill out all slots with notexture
 672         for (i = 0, tx = loadmodel->brushq1.textures;i < loadmodel->brushq1.numtextures;i++, tx++)
 673         {
 674                 tx->number = i;
 675                 strcpy(tx->name, "NO TEXTURE FOUND");
 676                 tx->width = 16;
 677                 tx->height = 16;
 678                 tx->skin.base = r_notexture;
 679                 tx->shader = &Cshader_wall_lightmap;
 680                 tx->flags = SURF_SOLIDCLIP;
 681                 if (i == loadmodel->brushq1.numtextures - 1)
 682                 {
 683                         tx->flags |= SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
 684                         tx->shader = &Cshader_water;
 685                 }
 686                 tx->currentframe = tx;
 687         }
 688
 689         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
 690         dofs = m->dataofs;
 691         // LordHavoc: mostly rewritten map texture loader
 692         for (i = 0;i < m->nummiptex;i++)
 693         {
 694                 dofs[i] = LittleLong(dofs[i]);
 695                 if (dofs[i] == -1 || r_nosurftextures.integer)
 696                         continue;
 697                 dmiptex = (miptex_t *)((qbyte *)m + dofs[i]);
 698
 699                 // make sure name is no more than 15 characters
 700                 for (j = 0;dmiptex->name[j] && j < 15;j++)
 701                         name[j] = dmiptex->name[j];
 702                 name[j] = 0;
 703
 704                 mtwidth = LittleLong(dmiptex->width);
 705                 mtheight = LittleLong(dmiptex->height);
 706                 mtdata = NULL;
 707                 j = LittleLong(dmiptex->offsets[0]);
 708                 if (j)
 709                 {
 710                         // texture included
 711                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
 712                         {
 713                                 Con_Printf("Texture \"%s\" in \"%s\"is corrupt or incomplete\n", dmiptex->name, loadmodel->name);
 714                                 continue;
 715                         }
 716                         mtdata = (qbyte *)dmiptex + j;
 717                 }
 718
 719                 if ((mtwidth & 15) || (mtheight & 15))
 720                         Con_Printf("warning: texture \"%s\" in \"%s\" is not 16 aligned", dmiptex->name, loadmodel->name);
 721
 722                 // LordHavoc: force all names to lowercase
 723                 for (j = 0;name[j];j++)
 724                         if (name[j] >= 'A' && name[j] <= 'Z')
 725                                 name[j] += 'a' - 'A';
 726
 727                 tx = loadmodel->brushq1.textures + i;
 728                 strcpy(tx->name, name);
 729                 tx->width = mtwidth;
 730                 tx->height = mtheight;
 731
 732                 if (!tx->name[0])
 733                 {
 734                         sprintf(tx->name, "unnamed%i", i);
 735                         Con_Printf("warning: unnamed texture in %s, renaming to %s\n", loadmodel->name, tx->name);
 736                 }
 737
 738                 // LordHavoc: HL sky textures are entirely different than quake
 739                 if (!loadmodel->brushq1.ishlbsp && !strncmp(tx->name, "sky", 3) && mtwidth == 256 && mtheight == 128)
 740                 {
 741                         if (loadmodel->isworldmodel)
 742                         {
 743                                 data = loadimagepixels(tx->name, false, 0, 0);
 744                                 if (data)
 745                                 {
 746                                         if (image_width == 256 && image_height == 128)
 747                                         {
 748                                                 R_InitSky(data, 4);
 749                                                 Mem_Free(data);
 750                                         }
 751                                         else
 752                                         {
 753                                                 Mem_Free(data);
 754                                                 Con_Printf("Invalid replacement texture for sky \"%s\" in %\"%s\", must be 256x128 pixels\n", tx->name, loadmodel->name);
 755                                                 if (mtdata != NULL)
 756                                                         R_InitSky(mtdata, 1);
 757                                         }
 758                                 }
 759                                 else if (mtdata != NULL)
 760                                         R_InitSky(mtdata, 1);
 761                         }
 762                 }
 763                 else
 764                 {
 765                         if (!Mod_LoadSkinFrame(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, false, true, true))
 766                         {
 767                                 // did not find external texture, load it from the bsp or wad3
 768                                 if (loadmodel->brushq1.ishlbsp)
 769                                 {
 770                                         // internal texture overrides wad
 771                                         qbyte *pixels, *freepixels, *fogpixels;
 772                                         pixels = freepixels = NULL;
 773                                         if (mtdata)
 774                                                 pixels = W_ConvertWAD3Texture(dmiptex);
 775                                         if (pixels == NULL)
 776                                                 pixels = freepixels = W_GetTexture(tx->name);
 777                                         if (pixels != NULL)
 778                                         {
 779                                                 tx->width = image_width;
 780                                                 tx->height = image_height;
 781                                                 tx->skin.base = tx->skin.merged = R_LoadTexture2D(loadmodel->texturepool, tx->name, image_width, image_height, pixels, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, NULL);
 782                                                 if (Image_CheckAlpha(pixels, image_width * image_height, true))
 783                                                 {
 784                                                         fogpixels = Mem_Alloc(tempmempool, image_width * image_height * 4);
 785                                                         for (j = 0;j < image_width * image_height * 4;j += 4)
 786                                                         {
 787                                                                 fogpixels[j + 0] = 255;
 788                                                                 fogpixels[j + 1] = 255;
 789                                                                 fogpixels[j + 2] = 255;
 790                                                                 fogpixels[j + 3] = pixels[j + 3];
 791                                                         }
 792                                                         tx->skin.fog = R_LoadTexture2D(loadmodel->texturepool, tx->name, image_width, image_height, pixels, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, NULL);
 793                                                         Mem_Free(fogpixels);
 794                                                 }
 795                                         }
 796                                         if (freepixels)
 797                                                 Mem_Free(freepixels);
 798                                 }
 799                                 else if (mtdata) // texture included
 800                                         Mod_LoadSkinFrame_Internal(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_PRECACHE, false, true, tx->name[0] != '*' && r_fullbrights.integer, mtdata, tx->width, tx->height);
 801                         }
 802                 }
 803                 if (tx->skin.base == NULL)
 804                 {
 805                         // no texture found
 806                         tx->width = 16;
 807                         tx->height = 16;
 808                         tx->skin.base = r_notexture;
 809                 }
 810
 811                 if (tx->name[0] == '*')
 812                 {
 813                         // turb does not block movement
 814                         tx->flags &= ~SURF_SOLIDCLIP;
 815                         tx->flags |= SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
 816                         // LordHavoc: some turbulent textures should be fullbright and solid
 817                         if (!strncmp(tx->name,"*lava",5)
 818                          || !strncmp(tx->name,"*teleport",9)
 819                          || !strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
 820                                 tx->flags |= SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA;
 821                         else
 822                                 tx->flags |= SURF_WATERALPHA;
 823                         tx->shader = &Cshader_water;
 824                 }
 825                 else if (tx->name[0] == 's' && tx->name[1] == 'k' && tx->name[2] == 'y')
 826                 {
 827                         tx->flags |= SURF_DRAWSKY;
 828                         tx->shader = &Cshader_sky;
 829                 }
 830                 else
 831                 {
 832                         tx->flags |= SURF_LIGHTMAP;
 833                         if (!tx->skin.fog)
 834                                 tx->flags |= SURF_SHADOWCAST | SURF_SHADOWLIGHT;
 835                         tx->shader = &Cshader_wall_lightmap;
 836                 }
 837
 838                 // start out with no animation
 839                 tx->currentframe = tx;
 840         }
 841
 842         // sequence the animations
 843         for (i = 0;i < m->nummiptex;i++)
 844         {
 845                 tx = loadmodel->brushq1.textures + i;
 846                 if (!tx || tx->name[0] != '+' || tx->name[1] == 0 || tx->name[2] == 0)
 847                         continue;
 848                 if (tx->anim_total[0] || tx->anim_total[1])
 849                         continue;       // already sequenced
 850
 851                 // find the number of frames in the animation
 852                 memset(anims, 0, sizeof(anims));
 853                 memset(altanims, 0, sizeof(altanims));
 854
 855                 for (j = i;j < m->nummiptex;j++)
 856                 {
 857                         tx2 = loadmodel->brushq1.textures + j;
 858                         if (!tx2 || tx2->name[0] != '+' || strcmp(tx2->name+2, tx->name+2))
 859                                 continue;
 860
 861                         num = tx2->name[1];
 862                         if (num >= '0' && num <= '9')
 863                                 anims[num - '0'] = tx2;
 864                         else if (num >= 'a' && num <= 'j')
 865                                 altanims[num - 'a'] = tx2;
 866                         else
 867                                 Con_Printf("Bad animating texture %s\n", tx->name);
 868                 }
 869
 870                 max = altmax = 0;
 871                 for (j = 0;j < 10;j++)
 872                 {
 873                         if (anims[j])
 874                                 max = j + 1;
 875                         if (altanims[j])
 876                                 altmax = j + 1;
 877                 }
 878                 //Con_Printf("linking animation %s (%i:%i frames)\n\n", tx->name, max, altmax);
 879
 880                 incomplete = false;
 881                 for (j = 0;j < max;j++)
 882                 {
 883                         if (!anims[j])
 884                         {
 885                                 Con_Printf("Missing frame %i of %s\n", j, tx->name);
 886                                 incomplete = true;
 887                         }
 888                 }
 889                 for (j = 0;j < altmax;j++)
 890                 {
 891                         if (!altanims[j])
 892                         {
 893                                 Con_Printf("Missing altframe %i of %s\n", j, tx->name);
 894                                 incomplete = true;
 895                         }
 896                 }
 897                 if (incomplete)
 898                         continue;
 899
 900                 if (altmax < 1)
 901                 {
 902                         // if there is no alternate animation, duplicate the primary
 903                         // animation into the alternate
 904                         altmax = max;
 905                         for (k = 0;k < 10;k++)
 906                                 altanims[k] = anims[k];
 907                 }
 908
 909                 // link together the primary animation
 910                 for (j = 0;j < max;j++)
 911                 {
 912                         tx2 = anims[j];
 913                         tx2->animated = true;
 914                         tx2->anim_total[0] = max;
 915                         tx2->anim_total[1] = altmax;
 916                         for (k = 0;k < 10;k++)
 917                         {
 918                                 tx2->anim_frames[0][k] = anims[k];
 919                                 tx2->anim_frames[1][k] = altanims[k];
 920                         }
 921                 }
 922
 923                 // if there really is an alternate anim...
 924                 if (anims[0] != altanims[0])
 925                 {
 926                         // link together the alternate animation
 927                         for (j = 0;j < altmax;j++)
 928                         {
 929                                 tx2 = altanims[j];
 930                                 tx2->animated = true;
 931                                 // the primary/alternate are reversed here
 932                                 tx2->anim_total[0] = altmax;
 933                                 tx2->anim_total[1] = max;
 934                                 for (k = 0;k < 10;k++)
 935                                 {
 936                                         tx2->anim_frames[0][k] = altanims[k];
 937                                         tx2->anim_frames[1][k] = anims[k];
 938                                 }
 939                         }
 940                 }
 941         }
 942 }
 943
 944 static void Mod_Q1BSP_LoadLighting(lump_t *l)
 945 {
 946         int i;
 947         qbyte *in, *out, *data, d;
 948         char litfilename[1024];
 949         loadmodel->brushq1.lightdata = NULL;
 950         if (loadmodel->brushq1.ishlbsp) // LordHavoc: load the colored lighting data straight
 951         {
 952                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen);
 953                 memcpy(loadmodel->brushq1.lightdata, mod_base + l->fileofs, l->filelen);
 954         }
 955         else // LordHavoc: bsp version 29 (normal white lighting)
 956         {
 957                 // LordHavoc: hope is not lost yet, check for a .lit file to load
 958                 strcpy(litfilename, loadmodel->name);
 959                 FS_StripExtension(litfilename, litfilename);
 960                 strcat(litfilename, ".lit");
 961                 data = (qbyte*) FS_LoadFile(litfilename, false);
 962                 if (data)
 963                 {
 964                         if (fs_filesize > 8 && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
 965                         {
 966                                 i = LittleLong(((int *)data)[1]);
 967                                 if (i == 1)
 968                                 {
 969                                         Con_DPrintf("loaded %s\n", litfilename);
 970                                         loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, fs_filesize - 8);
 971                                         memcpy(loadmodel->brushq1.lightdata, data + 8, fs_filesize - 8);
 972                                         Mem_Free(data);
 973                                         return;
 974                                 }
 975                                 else
 976                                 {
 977                                         Con_Printf("Unknown .lit file version (%d)\n", i);
 978                                         Mem_Free(data);
 979                                 }
 980                         }
 981                         else
 982                         {
 983                                 if (fs_filesize == 8)
 984                                         Con_Printf("Empty .lit file, ignoring\n");
 985                                 else
 986                                         Con_Printf("Corrupt .lit file (old version?), ignoring\n");
 987                                 Mem_Free(data);
 988                         }
 989                 }
 990                 // LordHavoc: oh well, expand the white lighting data
 991                 if (!l->filelen)
 992                         return;
 993                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen*3);
 994                 in = loadmodel->brushq1.lightdata + l->filelen*2; // place the file at the end, so it will not be overwritten until the very last write
 995                 out = loadmodel->brushq1.lightdata;
 996                 memcpy(in, mod_base + l->fileofs, l->filelen);
 997                 for (i = 0;i < l->filelen;i++)
 998                 {
 999                         d = *in++;
1000                         *out++ = d;
1001                         *out++ = d;
1002                         *out++ = d;
1003                 }
1004         }
1005 }
1006
1007 static void Mod_Q1BSP_LoadLightList(void)
1008 {
1009         int a, n, numlights;
1010         char lightsfilename[1024], *s, *t, *lightsstring;
1011         mlight_t *e;
1012
1013         strcpy(lightsfilename, loadmodel->name);
1014         FS_StripExtension(lightsfilename, lightsfilename);
1015         strcat(lightsfilename, ".lights");
1016         s = lightsstring = (char *) FS_LoadFile(lightsfilename, false);
1017         if (s)
1018         {
1019                 numlights = 0;
1020                 while (*s)
1021                 {
1022                         while (*s && *s != '\n')
1023                                 s++;
1024                         if (!*s)
1025                         {
1026                                 Mem_Free(lightsstring);
1027                                 Host_Error("lights file must end with a newline\n");
1028                         }
1029                         s++;
1030                         numlights++;
1031                 }
1032                 loadmodel->brushq1.lights = Mem_Alloc(loadmodel->mempool, numlights * sizeof(mlight_t));
1033                 s = lightsstring;
1034                 n = 0;
1035                 while (*s && n < numlights)
1036                 {
1037                         t = s;
1038                         while (*s && *s != '\n')
1039                                 s++;
1040                         if (!*s)
1041                         {
1042                                 Mem_Free(lightsstring);
1043                                 Host_Error("misparsed lights file!\n");
1044                         }
1045                         e = loadmodel->brushq1.lights + n;
1046                         *s = 0;
1047                         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);
1048                         *s = '\n';
1049                         if (a != 14)
1050                         {
1051                                 Mem_Free(lightsstring);
1052                                 Host_Error("invalid lights file, found %d parameters on line %i, should be 14 parameters (origin[0] origin[1] origin[2] falloff light[0] light[1] light[2] subtract spotdir[0] spotdir[1] spotdir[2] spotcone distancebias style)\n", a, n + 1);
1053                         }
1054                         s++;
1055                         n++;
1056                 }
1057                 if (*s)
1058                 {
1059                         Mem_Free(lightsstring);
1060                         Host_Error("misparsed lights file!\n");
1061                 }
1062                 loadmodel->brushq1.numlights = numlights;
1063                 Mem_Free(lightsstring);
1064         }
1065 }
1066
1067 /*
1068 static int castshadowcount = 0;
1069 static void Mod_Q1BSP_ProcessLightList(void)
1070 {
1071         int j, k, l, *mark, lnum;
1072         mlight_t *e;
1073         msurface_t *surf;
1074         float dist;
1075         mleaf_t *leaf;
1076         qbyte *pvs;
1077         vec3_t temp;
1078         float *v, radius2;
1079         for (lnum = 0, e = loadmodel->brushq1.lights;lnum < loadmodel->brushq1.numlights;lnum++, e++)
1080         {
1081                 e->cullradius2 = DotProduct(e->light, e->light) / (e->falloff * e->falloff * 8192.0f * 8192.0f * 2.0f * 2.0f);// + 4096.0f;
1082                 if (e->cullradius2 > 4096.0f * 4096.0f)
1083                         e->cullradius2 = 4096.0f * 4096.0f;
1084                 e->cullradius = e->lightradius = sqrt(e->cullradius2);
1085                 leaf = Mod_Q1BSP_PointInLeaf(e->origin, loadmodel);
1086                 if (leaf->compressed_vis)
1087                         pvs = Mod_Q1BSP_DecompressVis(leaf->compressed_vis, loadmodel);
1088                 else
1089                         pvs = mod_q1bsp_novis;
1090                 for (j = 0;j < loadmodel->brushq1.numsurfaces;j++)
1091                         loadmodel->brushq1.surfacevisframes[j] = -1;
1092                 for (j = 0, leaf = loadmodel->brushq1.leafs + 1;j < loadmodel->brushq1.numleafs - 1;j++, leaf++)
1093                 {
1094                         if (pvs[j >> 3] & (1 << (j & 7)))
1095                         {
1096                                 for (k = 0, mark = leaf->firstmarksurface;k < leaf->nummarksurfaces;k++, mark++)
1097                                 {
1098                                         surf = loadmodel->brushq1.surfaces + *mark;
1099                                         if (surf->number != *mark)
1100                                                 Con_Printf("%d != %d\n", surf->number, *mark);
1101                                         dist = DotProduct(e->origin, surf->plane->normal) - surf->plane->dist;
1102                                         if (surf->flags & SURF_PLANEBACK)
1103                                                 dist = -dist;
1104                                         if (dist > 0 && dist < e->cullradius)
1105                                         {
1106                                                 temp[0] = bound(surf->poly_mins[0], e->origin[0], surf->poly_maxs[0]) - e->origin[0];
1107                                                 temp[1] = bound(surf->poly_mins[1], e->origin[1], surf->poly_maxs[1]) - e->origin[1];
1108                                                 temp[2] = bound(surf->poly_mins[2], e->origin[2], surf->poly_maxs[2]) - e->origin[2];
1109                                                 if (DotProduct(temp, temp) < lightradius2)
1110                                                         loadmodel->brushq1.surfacevisframes[*mark] = -2;
1111                                         }
1112                                 }
1113                         }
1114                 }
1115                 // build list of light receiving surfaces
1116                 e->numsurfaces = 0;
1117                 for (j = 0;j < loadmodel->brushq1.numsurfaces;j++)
1118                         if (loadmodel->brushq1.surfacevisframes[j] == -2)
1119                                 e->numsurfaces++;
1120                 e->surfaces = NULL;
1121                 if (e->numsurfaces > 0)
1122                 {
1123                         e->surfaces = Mem_Alloc(loadmodel->mempool, sizeof(msurface_t *) * e->numsurfaces);
1124                         e->numsurfaces = 0;
1125                         for (j = 0;j < loadmodel->brushq1.numsurfaces;j++)
1126                                 if (loadmodel->brushq1.surfacevisframes[j] == -2)
1127                                         e->surfaces[e->numsurfaces++] = loadmodel->brushq1.surfaces + j;
1128                 }
1129                 // find bounding box and sphere of lit surfaces
1130                 // (these will be used for creating a shape to clip the light)
1131                 radius2 = 0;
1132                 for (j = 0;j < e->numsurfaces;j++)
1133                 {
1134                         surf = e->surfaces[j];
1135                         if (j == 0)
1136                         {
1137                                 VectorCopy(surf->poly_verts, e->mins);
1138                                 VectorCopy(surf->poly_verts, e->maxs);
1139                         }
1140                         for (k = 0, v = surf->poly_verts;k < surf->poly_numverts;k++, v += 3)
1141                         {
1142                                 if (e->mins[0] > v[0]) e->mins[0] = v[0];if (e->maxs[0] < v[0]) e->maxs[0] = v[0];
1143                                 if (e->mins[1] > v[1]) e->mins[1] = v[1];if (e->maxs[1] < v[1]) e->maxs[1] = v[1];
1144                                 if (e->mins[2] > v[2]) e->mins[2] = v[2];if (e->maxs[2] < v[2]) e->maxs[2] = v[2];
1145                                 VectorSubtract(v, e->origin, temp);
1146                                 dist = DotProduct(temp, temp);
1147                                 if (radius2 < dist)
1148                                         radius2 = dist;
1149                         }
1150                 }
1151                 if (e->cullradius2 > radius2)
1152                 {
1153                         e->cullradius2 = radius2;
1154                         e->cullradius = sqrt(e->cullradius2);
1155                 }
1156                 if (e->mins[0] < e->origin[0] - e->lightradius) e->mins[0] = e->origin[0] - e->lightradius;
1157                 if (e->maxs[0] > e->origin[0] + e->lightradius) e->maxs[0] = e->origin[0] + e->lightradius;
1158                 if (e->mins[1] < e->origin[1] - e->lightradius) e->mins[1] = e->origin[1] - e->lightradius;
1159                 if (e->maxs[1] > e->origin[1] + e->lightradius) e->maxs[1] = e->origin[1] + e->lightradius;
1160                 if (e->mins[2] < e->origin[2] - e->lightradius) e->mins[2] = e->origin[2] - e->lightradius;
1161                 if (e->maxs[2] > e->origin[2] + e->lightradius) e->maxs[2] = e->origin[2] + e->lightradius;
1162                 // clip shadow volumes against eachother to remove unnecessary
1163                 // polygons(and sections of polygons)
1164                 {
1165                         //vec3_t polymins, polymaxs;
1166                         int maxverts = 4;
1167                         float *verts = Mem_Alloc(loadmodel->mempool, maxverts * sizeof(float[3]));
1168                         float f, *v0, *v1, projectdistance;
1169
1170                         e->shadowvolume = Mod_ShadowMesh_Begin(loadmodel->mempool, 1024);
1171 #if 0
1172                         {
1173                         vec3_t outermins, outermaxs, innermins, innermaxs;
1174                         innermins[0] = e->mins[0] - 1;
1175                         innermins[1] = e->mins[1] - 1;
1176                         innermins[2] = e->mins[2] - 1;
1177                         innermaxs[0] = e->maxs[0] + 1;
1178                         innermaxs[1] = e->maxs[1] + 1;
1179                         innermaxs[2] = e->maxs[2] + 1;
1180                         outermins[0] = loadmodel->normalmins[0] - 1;
1181                         outermins[1] = loadmodel->normalmins[1] - 1;
1182                         outermins[2] = loadmodel->normalmins[2] - 1;
1183                         outermaxs[0] = loadmodel->normalmaxs[0] + 1;
1184                         outermaxs[1] = loadmodel->normalmaxs[1] + 1;
1185                         outermaxs[2] = loadmodel->normalmaxs[2] + 1;
1186                         // add bounding box around the whole shadow volume set,
1187                         // facing inward to limit light area, with an outer bounding box
1188                         // facing outward (this is needed by the shadow rendering method)
1189                         // X major
1190                         verts[ 0] = innermaxs[0];verts[ 1] = innermins[1];verts[ 2] = innermaxs[2];
1191                         verts[ 3] = innermaxs[0];verts[ 4] = innermins[1];verts[ 5] = innermins[2];
1192                         verts[ 6] = innermaxs[0];verts[ 7] = innermaxs[1];verts[ 8] = innermins[2];
1193                         verts[ 9] = innermaxs[0];verts[10] = innermaxs[1];verts[11] = innermaxs[2];
1194                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1195                         verts[ 0] = outermaxs[0];verts[ 1] = outermaxs[1];verts[ 2] = outermaxs[2];
1196                         verts[ 3] = outermaxs[0];verts[ 4] = outermaxs[1];verts[ 5] = outermins[2];
1197                         verts[ 6] = outermaxs[0];verts[ 7] = outermins[1];verts[ 8] = outermins[2];
1198                         verts[ 9] = outermaxs[0];verts[10] = outermins[1];verts[11] = outermaxs[2];
1199                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1200                         // X minor
1201                         verts[ 0] = innermins[0];verts[ 1] = innermaxs[1];verts[ 2] = innermaxs[2];
1202                         verts[ 3] = innermins[0];verts[ 4] = innermaxs[1];verts[ 5] = innermins[2];
1203                         verts[ 6] = innermins[0];verts[ 7] = innermins[1];verts[ 8] = innermins[2];
1204                         verts[ 9] = innermins[0];verts[10] = innermins[1];verts[11] = innermaxs[2];
1205                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1206                         verts[ 0] = outermins[0];verts[ 1] = outermins[1];verts[ 2] = outermaxs[2];
1207                         verts[ 3] = outermins[0];verts[ 4] = outermins[1];verts[ 5] = outermins[2];
1208                         verts[ 6] = outermins[0];verts[ 7] = outermaxs[1];verts[ 8] = outermins[2];
1209                         verts[ 9] = outermins[0];verts[10] = outermaxs[1];verts[11] = outermaxs[2];
1210                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1211                         // Y major
1212                         verts[ 0] = innermaxs[0];verts[ 1] = innermaxs[1];verts[ 2] = innermaxs[2];
1213                         verts[ 3] = innermaxs[0];verts[ 4] = innermaxs[1];verts[ 5] = innermins[2];
1214                         verts[ 6] = innermins[0];verts[ 7] = innermaxs[1];verts[ 8] = innermins[2];
1215                         verts[ 9] = innermins[0];verts[10] = innermaxs[1];verts[11] = innermaxs[2];
1216                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1217                         verts[ 0] = outermins[0];verts[ 1] = outermaxs[1];verts[ 2] = outermaxs[2];
1218                         verts[ 3] = outermins[0];verts[ 4] = outermaxs[1];verts[ 5] = outermins[2];
1219                         verts[ 6] = outermaxs[0];verts[ 7] = outermaxs[1];verts[ 8] = outermins[2];
1220                         verts[ 9] = outermaxs[0];verts[10] = outermaxs[1];verts[11] = outermaxs[2];
1221                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1222                         // Y minor
1223                         verts[ 0] = innermins[0];verts[ 1] = innermins[1];verts[ 2] = innermaxs[2];
1224                         verts[ 3] = innermins[0];verts[ 4] = innermins[1];verts[ 5] = innermins[2];
1225                         verts[ 6] = innermaxs[0];verts[ 7] = innermins[1];verts[ 8] = innermins[2];
1226                         verts[ 9] = innermaxs[0];verts[10] = innermins[1];verts[11] = innermaxs[2];
1227                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1228                         verts[ 0] = outermaxs[0];verts[ 1] = outermins[1];verts[ 2] = outermaxs[2];
1229                         verts[ 3] = outermaxs[0];verts[ 4] = outermins[1];verts[ 5] = outermins[2];
1230                         verts[ 6] = outermins[0];verts[ 7] = outermins[1];verts[ 8] = outermins[2];
1231                         verts[ 9] = outermins[0];verts[10] = outermins[1];verts[11] = outermaxs[2];
1232                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1233                         // Z major
1234                         verts[ 0] = innermaxs[0];verts[ 1] = innermins[1];verts[ 2] = innermaxs[2];
1235                         verts[ 3] = innermaxs[0];verts[ 4] = innermaxs[1];verts[ 5] = innermaxs[2];
1236                         verts[ 6] = innermins[0];verts[ 7] = innermaxs[1];verts[ 8] = innermaxs[2];
1237                         verts[ 9] = innermins[0];verts[10] = innermins[1];verts[11] = innermaxs[2];
1238                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1239                         verts[ 0] = outermaxs[0];verts[ 1] = outermaxs[1];verts[ 2] = outermaxs[2];
1240                         verts[ 3] = outermaxs[0];verts[ 4] = outermins[1];verts[ 5] = outermaxs[2];
1241                         verts[ 6] = outermins[0];verts[ 7] = outermins[1];verts[ 8] = outermaxs[2];
1242                         verts[ 9] = outermins[0];verts[10] = outermaxs[1];verts[11] = outermaxs[2];
1243                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1244                         // Z minor
1245                         verts[ 0] = innermaxs[0];verts[ 1] = innermaxs[1];verts[ 2] = innermins[2];
1246                         verts[ 3] = innermaxs[0];verts[ 4] = innermins[1];verts[ 5] = innermins[2];
1247                         verts[ 6] = innermins[0];verts[ 7] = innermins[1];verts[ 8] = innermins[2];
1248                         verts[ 9] = innermins[0];verts[10] = innermaxs[1];verts[11] = innermins[2];
1249                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1250                         verts[ 0] = outermaxs[0];verts[ 1] = outermins[1];verts[ 2] = outermins[2];
1251                         verts[ 3] = outermaxs[0];verts[ 4] = outermaxs[1];verts[ 5] = outermins[2];
1252                         verts[ 6] = outermins[0];verts[ 7] = outermaxs[1];verts[ 8] = outermins[2];
1253                         verts[ 9] = outermins[0];verts[10] = outermins[1];verts[11] = outermins[2];
1254                         Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1255                         }
1256 #endif
1257                         castshadowcount++;
1258                         for (j = 0;j < e->numsurfaces;j++)
1259                         {
1260                                 surf = e->surfaces[j];
1261                                 if (surf->flags & SURF_SHADOWCAST)
1262                                         surf->castshadow = castshadowcount;
1263                         }
1264                         for (j = 0;j < e->numsurfaces;j++)
1265                         {
1266                                 surf = e->surfaces[j];
1267                                 if (surf->castshadow != castshadowcount)
1268                                         continue;
1269                                 f = DotProduct(e->origin, surf->plane->normal) - surf->plane->dist;
1270                                 if (surf->flags & SURF_PLANEBACK)
1271                                         f = -f;
1272                                 projectdistance = e->lightradius;
1273                                 if (maxverts < surf->poly_numverts)
1274                                 {
1275                                         maxverts = surf->poly_numverts;
1276                                         if (verts)
1277                                                 Mem_Free(verts);
1278                                         verts = Mem_Alloc(loadmodel->mempool, maxverts * sizeof(float[3]));
1279                                 }
1280                                 // copy the original polygon, for the front cap of the volume
1281                                 for (k = 0, v0 = surf->poly_verts, v1 = verts;k < surf->poly_numverts;k++, v0 += 3, v1 += 3)
1282                                         VectorCopy(v0, v1);
1283                                 Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, surf->poly_numverts, verts);
1284                                 // project the original polygon, reversed, for the back cap of the volume
1285                                 for (k = 0, v0 = surf->poly_verts + (surf->poly_numverts - 1) * 3, v1 = verts;k < surf->poly_numverts;k++, v0 -= 3, v1 += 3)
1286                                 {
1287                                         VectorSubtract(v0, e->origin, temp);
1288                                         VectorNormalize(temp);
1289                                         VectorMA(v0, projectdistance, temp, v1);
1290                                 }
1291                                 Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, surf->poly_numverts, verts);
1292                                 // project the shadow volume sides
1293                                 for (l = surf->poly_numverts - 1, k = 0, v0 = surf->poly_verts + (surf->poly_numverts - 1) * 3, v1 = surf->poly_verts;k < surf->poly_numverts;l = k, k++, v0 = v1, v1 += 3)
1294                                 {
1295                                         if (!surf->neighborsurfaces[l] || surf->neighborsurfaces[l]->castshadow != castshadowcount)
1296                                         {
1297                                                 VectorCopy(v1, &verts[0]);
1298                                                 VectorCopy(v0, &verts[3]);
1299                                                 VectorCopy(v0, &verts[6]);
1300                                                 VectorCopy(v1, &verts[9]);
1301                                                 VectorSubtract(&verts[6], e->origin, temp);
1302                                                 VectorNormalize(temp);
1303                                                 VectorMA(&verts[6], projectdistance, temp, &verts[6]);
1304                                                 VectorSubtract(&verts[9], e->origin, temp);
1305                                                 VectorNormalize(temp);
1306                                                 VectorMA(&verts[9], projectdistance, temp, &verts[9]);
1307                                                 Mod_ShadowMesh_AddPolygon(loadmodel->mempool, e->shadowvolume, 4, verts);
1308                                         }
1309                                 }
1310                         }
1311                         // build the triangle mesh
1312                         e->shadowvolume = Mod_ShadowMesh_Finish(loadmodel->mempool, e->shadowvolume);
1313                         {
1314                                 shadowmesh_t *mesh;
1315                                 l = 0;
1316                                 for (mesh = e->shadowvolume;mesh;mesh = mesh->next)
1317                                         l += mesh->numtriangles;
1318                                 Con_Printf("light %i shadow volume built containing %i triangles\n", lnum, l);
1319                         }
1320                 }
1321         }
1322 }
1323 */
1324
1325
1326 static void Mod_Q1BSP_LoadVisibility(lump_t *l)
1327 {
1328         loadmodel->brushq1.visdata = NULL;
1329         if (!l->filelen)
1330                 return;
1331         loadmodel->brushq1.visdata = Mem_Alloc(loadmodel->mempool, l->filelen);
1332         memcpy(loadmodel->brushq1.visdata, mod_base + l->fileofs, l->filelen);
1333 }
1334
1335 // used only for HalfLife maps
1336 static void Mod_Q1BSP_ParseWadsFromEntityLump(const char *data)
1337 {
1338         char key[128], value[4096];
1339         char wadname[128];
1340         int i, j, k;
1341         if (!data)
1342                 return;
1343         if (!COM_ParseToken(&data, false))
1344                 return; // error
1345         if (com_token[0] != '{')
1346                 return; // error
1347         while (1)
1348         {
1349                 if (!COM_ParseToken(&data, false))
1350                         return; // error
1351                 if (com_token[0] == '}')
1352                         break; // end of worldspawn
1353                 if (com_token[0] == '_')
1354                         strcpy(key, com_token + 1);
1355                 else
1356                         strcpy(key, com_token);
1357                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
1358                         key[strlen(key)-1] = 0;
1359                 if (!COM_ParseToken(&data, false))
1360                         return; // error
1361                 strcpy(value, com_token);
1362                 if (!strcmp("wad", key)) // for HalfLife maps
1363                 {
1364                         if (loadmodel->brushq1.ishlbsp)
1365                         {
1366                                 j = 0;
1367                                 for (i = 0;i < 4096;i++)
1368                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
1369                                                 break;
1370                                 if (value[i])
1371                                 {
1372                                         for (;i < 4096;i++)
1373                                         {
1374                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
1375                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
1376                                                         j = i+1;
1377                                                 else if (value[i] == ';' || value[i] == 0)
1378                                                 {
1379                                                         k = value[i];
1380                                                         value[i] = 0;
1381                                                         strcpy(wadname, "textures/");
1382                                                         strcat(wadname, &value[j]);
1383                                                         W_LoadTextureWadFile(wadname, false);
1384                                                         j = i+1;
1385                                                         if (!k)
1386                                                                 break;
1387                                                 }
1388                                         }
1389                                 }
1390                         }
1391                 }
1392         }
1393 }
1394
1395 static void Mod_Q1BSP_LoadEntities(lump_t *l)
1396 {
1397         loadmodel->brush.entities = NULL;
1398         if (!l->filelen)
1399                 return;
1400         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
1401         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
1402         if (loadmodel->brushq1.ishlbsp)
1403                 Mod_Q1BSP_ParseWadsFromEntityLump(loadmodel->brush.entities);
1404 }
1405
1406
1407 static void Mod_Q1BSP_LoadVertexes(lump_t *l)
1408 {
1409         dvertex_t       *in;
1410         mvertex_t       *out;
1411         int                     i, count;
1412
1413         in = (void *)(mod_base + l->fileofs);
1414         if (l->filelen % sizeof(*in))
1415                 Host_Error("Mod_Q1BSP_LoadVertexes: funny lump size in %s",loadmodel->name);
1416         count = l->filelen / sizeof(*in);
1417         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1418
1419         loadmodel->brushq1.vertexes = out;
1420         loadmodel->brushq1.numvertexes = count;
1421
1422         for ( i=0 ; i<count ; i++, in++, out++)
1423         {
1424                 out->position[0] = LittleFloat(in->point[0]);
1425                 out->position[1] = LittleFloat(in->point[1]);
1426                 out->position[2] = LittleFloat(in->point[2]);
1427         }
1428 }
1429
1430 static void Mod_Q1BSP_LoadSubmodels(lump_t *l)
1431 {
1432         dmodel_t        *in;
1433         dmodel_t        *out;
1434         int                     i, j, count;
1435
1436         in = (void *)(mod_base + l->fileofs);
1437         if (l->filelen % sizeof(*in))
1438                 Host_Error("Mod_Q1BSP_LoadSubmodels: funny lump size in %s",loadmodel->name);
1439         count = l->filelen / sizeof(*in);
1440         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1441
1442         loadmodel->brushq1.submodels = out;
1443         loadmodel->brushq1.numsubmodels = count;
1444
1445         for ( i=0 ; i<count ; i++, in++, out++)
1446         {
1447                 for (j=0 ; j<3 ; j++)
1448                 {
1449                         // spread the mins / maxs by a pixel
1450                         out->mins[j] = LittleFloat(in->mins[j]) - 1;
1451                         out->maxs[j] = LittleFloat(in->maxs[j]) + 1;
1452                         out->origin[j] = LittleFloat(in->origin[j]);
1453                 }
1454                 for (j=0 ; j<MAX_MAP_HULLS ; j++)
1455                         out->headnode[j] = LittleLong(in->headnode[j]);
1456                 out->visleafs = LittleLong(in->visleafs);
1457                 out->firstface = LittleLong(in->firstface);
1458                 out->numfaces = LittleLong(in->numfaces);
1459         }
1460 }
1461
1462 static void Mod_Q1BSP_LoadEdges(lump_t *l)
1463 {
1464         dedge_t *in;
1465         medge_t *out;
1466         int     i, count;
1467
1468         in = (void *)(mod_base + l->fileofs);
1469         if (l->filelen % sizeof(*in))
1470                 Host_Error("Mod_Q1BSP_LoadEdges: funny lump size in %s",loadmodel->name);
1471         count = l->filelen / sizeof(*in);
1472         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1473
1474         loadmodel->brushq1.edges = out;
1475         loadmodel->brushq1.numedges = count;
1476
1477         for ( i=0 ; i<count ; i++, in++, out++)
1478         {
1479                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
1480                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
1481         }
1482 }
1483
1484 static void Mod_Q1BSP_LoadTexinfo(lump_t *l)
1485 {
1486         texinfo_t *in;
1487         mtexinfo_t *out;
1488         int i, j, k, count, miptex;
1489
1490         in = (void *)(mod_base + l->fileofs);
1491         if (l->filelen % sizeof(*in))
1492                 Host_Error("Mod_Q1BSP_LoadTexinfo: funny lump size in %s",loadmodel->name);
1493         count = l->filelen / sizeof(*in);
1494         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1495
1496         loadmodel->brushq1.texinfo = out;
1497         loadmodel->brushq1.numtexinfo = count;
1498
1499         for (i = 0;i < count;i++, in++, out++)
1500         {
1501                 for (k = 0;k < 2;k++)
1502                         for (j = 0;j < 4;j++)
1503                                 out->vecs[k][j] = LittleFloat(in->vecs[k][j]);
1504
1505                 miptex = LittleLong(in->miptex);
1506                 out->flags = LittleLong(in->flags);
1507
1508                 out->texture = NULL;
1509                 if (loadmodel->brushq1.textures)
1510                 {
1511                         if ((unsigned int) miptex >= (unsigned int) loadmodel->brushq1.numtextures)
1512                                 Con_Printf("error in model \"%s\": invalid miptex index %i(of %i)\n", loadmodel->name, miptex, loadmodel->brushq1.numtextures);
1513                         else
1514                                 out->texture = loadmodel->brushq1.textures + miptex;
1515                 }
1516                 if (out->flags & TEX_SPECIAL)
1517                 {
1518                         // if texture chosen is NULL or the shader needs a lightmap,
1519                         // force to notexture water shader
1520                         if (out->texture == NULL || out->texture->shader->flags & SHADERFLAGS_NEEDLIGHTMAP)
1521                                 out->texture = loadmodel->brushq1.textures + (loadmodel->brushq1.numtextures - 1);
1522                 }
1523                 else
1524                 {
1525                         // if texture chosen is NULL, force to notexture
1526                         if (out->texture == NULL)
1527                                 out->texture = loadmodel->brushq1.textures + (loadmodel->brushq1.numtextures - 2);
1528                 }
1529         }
1530 }
1531
1532 #if 0
1533 void BoundPoly(int numverts, float *verts, vec3_t mins, vec3_t maxs)
1534 {
1535         int             i, j;
1536         float   *v;
1537
1538         mins[0] = mins[1] = mins[2] = 9999;
1539         maxs[0] = maxs[1] = maxs[2] = -9999;
1540         v = verts;
1541         for (i = 0;i < numverts;i++)
1542         {
1543                 for (j = 0;j < 3;j++, v++)
1544                 {
1545                         if (*v < mins[j])
1546                                 mins[j] = *v;
1547                         if (*v > maxs[j])
1548                                 maxs[j] = *v;
1549                 }
1550         }
1551 }
1552
1553 #define MAX_SUBDIVPOLYTRIANGLES 4096
1554 #define MAX_SUBDIVPOLYVERTS(MAX_SUBDIVPOLYTRIANGLES * 3)
1555
1556 static int subdivpolyverts, subdivpolytriangles;
1557 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
1558 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
1559
1560 static int subdivpolylookupvert(vec3_t v)
1561 {
1562         int i;
1563         for (i = 0;i < subdivpolyverts;i++)
1564                 if (subdivpolyvert[i][0] == v[0]
1565                  && subdivpolyvert[i][1] == v[1]
1566                  && subdivpolyvert[i][2] == v[2])
1567                         return i;
1568         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
1569                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
1570         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
1571         return subdivpolyverts++;
1572 }
1573
1574 static void SubdividePolygon(int numverts, float *verts)
1575 {
1576         int             i, i1, i2, i3, f, b, c, p;
1577         vec3_t  mins, maxs, front[256], back[256];
1578         float   m, *pv, *cv, dist[256], frac;
1579
1580         if (numverts > 250)
1581                 Host_Error("SubdividePolygon: ran out of verts in buffer");
1582
1583         BoundPoly(numverts, verts, mins, maxs);
1584
1585         for (i = 0;i < 3;i++)
1586         {
1587                 m = (mins[i] + maxs[i]) * 0.5;
1588                 m = r_subdivide_size.value * floor(m/r_subdivide_size.value + 0.5);
1589                 if (maxs[i] - m < 8)
1590                         continue;
1591                 if (m - mins[i] < 8)
1592                         continue;
1593
1594                 // cut it
1595                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
1596                         dist[c] = cv[i] - m;
1597
1598                 f = b = 0;
1599                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
1600                 {
1601                         if (dist[p] >= 0)
1602                         {
1603                                 VectorCopy(pv, front[f]);
1604                                 f++;
1605                         }
1606                         if (dist[p] <= 0)
1607                         {
1608                                 VectorCopy(pv, back[b]);
1609                                 b++;
1610                         }
1611                         if (dist[p] == 0 || dist[c] == 0)
1612                                 continue;
1613                         if ((dist[p] > 0) != (dist[c] > 0) )
1614                         {
1615                                 // clip point
1616                                 frac = dist[p] / (dist[p] - dist[c]);
1617                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
1618                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
1619                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
1620                                 f++;
1621                                 b++;
1622                         }
1623                 }
1624
1625                 SubdividePolygon(f, front[0]);
1626                 SubdividePolygon(b, back[0]);
1627                 return;
1628         }
1629
1630         i1 = subdivpolylookupvert(verts);
1631         i2 = subdivpolylookupvert(verts + 3);
1632         for (i = 2;i < numverts;i++)
1633         {
1634                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
1635                 {
1636                         Con_Printf("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
1637                         return;
1638                 }
1639
1640                 i3 = subdivpolylookupvert(verts + i * 3);
1641                 subdivpolyindex[subdivpolytriangles][0] = i1;
1642                 subdivpolyindex[subdivpolytriangles][1] = i2;
1643                 subdivpolyindex[subdivpolytriangles][2] = i3;
1644                 i2 = i3;
1645                 subdivpolytriangles++;
1646         }
1647 }
1648
1649 //Breaks a polygon up along axial 64 unit
1650 //boundaries so that turbulent and sky warps
1651 //can be done reasonably.
1652 static void Mod_Q1BSP_GenerateWarpMesh(msurface_t *surf)
1653 {
1654         int i, j;
1655         surfvertex_t *v;
1656         surfmesh_t *mesh;
1657
1658         subdivpolytriangles = 0;
1659         subdivpolyverts = 0;
1660         SubdividePolygon(surf->poly_numverts, surf->poly_verts);
1661         if (subdivpolytriangles < 1)
1662                 Host_Error("Mod_Q1BSP_GenerateWarpMesh: no triangles?\n");
1663
1664         surf->mesh = mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + subdivpolytriangles * sizeof(int[3]) + subdivpolyverts * sizeof(surfvertex_t));
1665         mesh->numverts = subdivpolyverts;
1666         mesh->numtriangles = subdivpolytriangles;
1667         mesh->vertex = (surfvertex_t *)(mesh + 1);
1668         mesh->index = (int *)(mesh->vertex + mesh->numverts);
1669         memset(mesh->vertex, 0, mesh->numverts * sizeof(surfvertex_t));
1670
1671         for (i = 0;i < mesh->numtriangles;i++)
1672                 for (j = 0;j < 3;j++)
1673                         mesh->index[i*3+j] = subdivpolyindex[i][j];
1674
1675         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
1676         {
1677                 VectorCopy(subdivpolyvert[i], v->v);
1678                 v->st[0] = DotProduct(v->v, surf->texinfo->vecs[0]);
1679                 v->st[1] = DotProduct(v->v, surf->texinfo->vecs[1]);
1680         }
1681 }
1682 #endif
1683
1684 static surfmesh_t *Mod_Q1BSP_AllocSurfMesh(int numverts, int numtriangles)
1685 {
1686         surfmesh_t *mesh;
1687         mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + numtriangles * sizeof(int[6]) + numverts * (3 + 2 + 2 + 2 + 3 + 3 + 3 + 1) * sizeof(float));
1688         mesh->numverts = numverts;
1689         mesh->numtriangles = numtriangles;
1690         mesh->vertex3f = (float *)(mesh + 1);
1691         mesh->texcoordtexture2f = mesh->vertex3f + mesh->numverts * 3;
1692         mesh->texcoordlightmap2f = mesh->texcoordtexture2f + mesh->numverts * 2;
1693         mesh->texcoorddetail2f = mesh->texcoordlightmap2f + mesh->numverts * 2;
1694         mesh->svector3f = (float *)(mesh->texcoorddetail2f + mesh->numverts * 2);
1695         mesh->tvector3f = mesh->svector3f + mesh->numverts * 3;
1696         mesh->normal3f = mesh->tvector3f + mesh->numverts * 3;
1697         mesh->lightmapoffsets = (int *)(mesh->normal3f + mesh->numverts * 3);
1698         mesh->element3i = mesh->lightmapoffsets + mesh->numverts;
1699         mesh->neighbor3i = mesh->element3i + mesh->numtriangles * 3;
1700         return mesh;
1701 }
1702
1703 static void Mod_Q1BSP_GenerateSurfacePolygon(msurface_t *surf, int firstedge, int numedges)
1704 {
1705         int i, lindex, j;
1706         float *vec, *vert, mins[3], maxs[3], val, *v;
1707         mtexinfo_t *tex;
1708
1709         // convert edges back to a normal polygon
1710         surf->poly_numverts = numedges;
1711         vert = surf->poly_verts = Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * numedges);
1712         for (i = 0;i < numedges;i++)
1713         {
1714                 lindex = loadmodel->brushq1.surfedges[firstedge + i];
1715                 if (lindex > 0)
1716                         vec = loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[lindex].v[0]].position;
1717                 else
1718                         vec = loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[-lindex].v[1]].position;
1719                 VectorCopy(vec, vert);
1720                 vert += 3;
1721         }
1722
1723         // calculate polygon bounding box and center
1724         vert = surf->poly_verts;
1725         VectorCopy(vert, mins);
1726         VectorCopy(vert, maxs);
1727         vert += 3;
1728         for (i = 1;i < surf->poly_numverts;i++, vert += 3)
1729         {
1730                 if (mins[0] > vert[0]) mins[0] = vert[0];if (maxs[0] < vert[0]) maxs[0] = vert[0];
1731                 if (mins[1] > vert[1]) mins[1] = vert[1];if (maxs[1] < vert[1]) maxs[1] = vert[1];
1732                 if (mins[2] > vert[2]) mins[2] = vert[2];if (maxs[2] < vert[2]) maxs[2] = vert[2];
1733         }
1734         VectorCopy(mins, surf->poly_mins);
1735         VectorCopy(maxs, surf->poly_maxs);
1736         surf->poly_center[0] = (mins[0] + maxs[0]) * 0.5f;
1737         surf->poly_center[1] = (mins[1] + maxs[1]) * 0.5f;
1738         surf->poly_center[2] = (mins[2] + maxs[2]) * 0.5f;
1739
1740         // generate surface extents information
1741         tex = surf->texinfo;
1742         mins[0] = maxs[0] = DotProduct(surf->poly_verts, tex->vecs[0]) + tex->vecs[0][3];
1743         mins[1] = maxs[1] = DotProduct(surf->poly_verts, tex->vecs[1]) + tex->vecs[1][3];
1744         for (i = 1, v = surf->poly_verts + 3;i < surf->poly_numverts;i++, v += 3)
1745         {
1746                 for (j = 0;j < 2;j++)
1747                 {
1748                         val = DotProduct(v, tex->vecs[j]) + tex->vecs[j][3];
1749                         if (mins[j] > val)
1750                                 mins[j] = val;
1751                         if (maxs[j] < val)
1752                                 maxs[j] = val;
1753                 }
1754         }
1755         for (i = 0;i < 2;i++)
1756         {
1757                 surf->texturemins[i] = (int) floor(mins[i] / 16) * 16;
1758                 surf->extents[i] = (int) ceil(maxs[i] / 16) * 16 - surf->texturemins[i];
1759         }
1760 }
1761
1762 static void Mod_Q1BSP_LoadFaces(lump_t *l)
1763 {
1764         dface_t *in;
1765         msurface_t *surf;
1766         int i, count, surfnum, planenum, ssize, tsize, firstedge, numedges, totalverts, totaltris, totalmeshes;
1767         surfmesh_t *mesh;
1768         float s, t;
1769
1770         in = (void *)(mod_base + l->fileofs);
1771         if (l->filelen % sizeof(*in))
1772                 Host_Error("Mod_Q1BSP_LoadFaces: funny lump size in %s",loadmodel->name);
1773         count = l->filelen / sizeof(*in);
1774         loadmodel->brushq1.surfaces = Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_t));
1775
1776         loadmodel->brushq1.numsurfaces = count;
1777         loadmodel->brushq1.surfacevisframes = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1778         loadmodel->brushq1.surfacepvsframes = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1779         loadmodel->brushq1.pvssurflist = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1780
1781         for (surfnum = 0, surf = loadmodel->brushq1.surfaces, totalverts = 0, totaltris = 0, totalmeshes = 0;surfnum < count;surfnum++, totalverts += surf->poly_numverts, totaltris += surf->poly_numverts - 2, totalmeshes++, in++, surf++)
1782         {
1783                 surf->number = surfnum;
1784                 // FIXME: validate edges, texinfo, etc?
1785                 firstedge = LittleLong(in->firstedge);
1786                 numedges = LittleShort(in->numedges);
1787                 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)
1788                         Host_Error("Mod_Q1BSP_LoadFaces: invalid edge range (firstedge %i, numedges %i, model edges %i)\n", firstedge, numedges, loadmodel->brushq1.numsurfedges);
1789                 i = LittleShort(in->texinfo);
1790                 if ((unsigned int) i >= (unsigned int) loadmodel->brushq1.numtexinfo)
1791                         Host_Error("Mod_Q1BSP_LoadFaces: invalid texinfo index %i(model has %i texinfos)\n", i, loadmodel->brushq1.numtexinfo);
1792                 surf->texinfo = loadmodel->brushq1.texinfo + i;
1793                 surf->flags = surf->texinfo->texture->flags;
1794
1795                 planenum = LittleShort(in->planenum);
1796                 if ((unsigned int) planenum >= (unsigned int) loadmodel->brushq1.numplanes)
1797                         Host_Error("Mod_Q1BSP_LoadFaces: invalid plane index %i (model has %i planes)\n", planenum, loadmodel->brushq1.numplanes);
1798
1799                 if (LittleShort(in->side))
1800                         surf->flags |= SURF_PLANEBACK;
1801
1802                 surf->plane = loadmodel->brushq1.planes + planenum;
1803
1804                 // clear lightmap (filled in later)
1805                 surf->lightmaptexture = NULL;
1806
1807                 // force lightmap upload on first time seeing the surface
1808                 surf->cached_dlight = true;
1809
1810                 Mod_Q1BSP_GenerateSurfacePolygon(surf, firstedge, numedges);
1811
1812                 ssize = (surf->extents[0] >> 4) + 1;
1813                 tsize = (surf->extents[1] >> 4) + 1;
1814
1815                 // lighting info
1816                 for (i = 0;i < MAXLIGHTMAPS;i++)
1817                         surf->styles[i] = in->styles[i];
1818                 i = LittleLong(in->lightofs);
1819                 if (i == -1)
1820                         surf->samples = NULL;
1821                 else if (loadmodel->brushq1.ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
1822                         surf->samples = loadmodel->brushq1.lightdata + i;
1823                 else // LordHavoc: white lighting (bsp version 29)
1824                         surf->samples = loadmodel->brushq1.lightdata + (i * 3);
1825
1826                 if (surf->texinfo->texture->shader == &Cshader_wall_lightmap)
1827                 {
1828                         if ((surf->extents[0] >> 4) + 1 > (256) || (surf->extents[1] >> 4) + 1 > (256))
1829                                 Host_Error("Bad surface extents");
1830                         // stainmap for permanent marks on walls
1831                         surf->stainsamples = Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
1832                         // clear to white
1833                         memset(surf->stainsamples, 255, ssize * tsize * 3);
1834                 }
1835         }
1836
1837         loadmodel->brushq1.entiremesh = Mod_Q1BSP_AllocSurfMesh(totalverts, totaltris);
1838         loadmodel->brushq1.surfmeshes = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) * totalmeshes);
1839
1840         for (surfnum = 0, surf = loadmodel->brushq1.surfaces, totalverts = 0, totaltris = 0, totalmeshes = 0;surfnum < count;surfnum++, totalverts += surf->poly_numverts, totaltris += surf->poly_numverts - 2, totalmeshes++, surf++)
1841         {
1842                 mesh = surf->mesh = loadmodel->brushq1.surfmeshes + totalmeshes;
1843                 mesh->numverts = surf->poly_numverts;
1844                 mesh->numtriangles = surf->poly_numverts - 2;
1845                 mesh->vertex3f = loadmodel->brushq1.entiremesh->vertex3f + totalverts * 3;
1846                 mesh->texcoordtexture2f = loadmodel->brushq1.entiremesh->texcoordtexture2f + totalverts * 2;
1847                 mesh->texcoordlightmap2f = loadmodel->brushq1.entiremesh->texcoordlightmap2f + totalverts * 2;
1848                 mesh->texcoorddetail2f = loadmodel->brushq1.entiremesh->texcoorddetail2f + totalverts * 2;
1849                 mesh->svector3f = loadmodel->brushq1.entiremesh->svector3f + totalverts * 3;
1850                 mesh->tvector3f = loadmodel->brushq1.entiremesh->tvector3f + totalverts * 3;
1851                 mesh->normal3f = loadmodel->brushq1.entiremesh->normal3f + totalverts * 3;
1852                 mesh->lightmapoffsets = loadmodel->brushq1.entiremesh->lightmapoffsets + totalverts;
1853                 mesh->element3i = loadmodel->brushq1.entiremesh->element3i + totaltris * 3;
1854                 mesh->neighbor3i = loadmodel->brushq1.entiremesh->neighbor3i + totaltris * 3;
1855
1856                 surf->lightmaptexturestride = 0;
1857                 surf->lightmaptexture = NULL;
1858
1859                 for (i = 0;i < mesh->numverts;i++)
1860                 {
1861                         mesh->vertex3f[i * 3 + 0] = surf->poly_verts[i * 3 + 0];
1862                         mesh->vertex3f[i * 3 + 1] = surf->poly_verts[i * 3 + 1];
1863                         mesh->vertex3f[i * 3 + 2] = surf->poly_verts[i * 3 + 2];
1864                         s = DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3];
1865                         t = DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3];
1866                         mesh->texcoordtexture2f[i * 2 + 0] = s / surf->texinfo->texture->width;
1867                         mesh->texcoordtexture2f[i * 2 + 1] = t / surf->texinfo->texture->height;
1868                         mesh->texcoorddetail2f[i * 2 + 0] = s * (1.0f / 16.0f);
1869                         mesh->texcoorddetail2f[i * 2 + 1] = t * (1.0f / 16.0f);
1870                         mesh->texcoordlightmap2f[i * 2 + 0] = 0;
1871                         mesh->texcoordlightmap2f[i * 2 + 1] = 0;
1872                         mesh->lightmapoffsets[i] = 0;
1873                 }
1874
1875                 for (i = 0;i < mesh->numtriangles;i++)
1876                 {
1877                         mesh->element3i[i * 3 + 0] = 0;
1878                         mesh->element3i[i * 3 + 1] = i + 1;
1879                         mesh->element3i[i * 3 + 2] = i + 2;
1880                 }
1881
1882                 Mod_BuildTriangleNeighbors(mesh->neighbor3i, mesh->element3i, mesh->numtriangles);
1883                 Mod_BuildTextureVectorsAndNormals(mesh->numverts, mesh->numtriangles, mesh->vertex3f, mesh->texcoordtexture2f, mesh->element3i, mesh->svector3f, mesh->tvector3f, mesh->normal3f);
1884
1885                 if (surf->texinfo->texture->shader == &Cshader_wall_lightmap)
1886                 {
1887                         int i, iu, iv, smax, tmax;
1888                         float u, v, ubase, vbase, uscale, vscale;
1889
1890                         smax = surf->extents[0] >> 4;
1891                         tmax = surf->extents[1] >> 4;
1892
1893                         surf->flags |= SURF_LIGHTMAP;
1894                         if (r_miplightmaps.integer)
1895                         {
1896                                 surf->lightmaptexturestride = smax+1;
1897                                 surf->lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, NULL, surf->lightmaptexturestride, (surf->extents[1]>>4)+1, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_MIPMAP | TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
1898                         }
1899                         else
1900                         {
1901                                 surf->lightmaptexturestride = R_CompatibleFragmentWidth(smax+1, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, 0);
1902                                 surf->lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, NULL, surf->lightmaptexturestride, (surf->extents[1]>>4)+1, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FRAGMENT | TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
1903                         }
1904                         R_FragmentLocation(surf->lightmaptexture, NULL, NULL, &ubase, &vbase, &uscale, &vscale);
1905                         uscale = (uscale - ubase) / (smax + 1);
1906                         vscale = (vscale - vbase) / (tmax + 1);
1907
1908                         for (i = 0;i < mesh->numverts;i++)
1909                         {
1910                                 u = ((DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3]) + 8 - surf->texturemins[0]) * (1.0 / 16.0);
1911                                 v = ((DotProduct((mesh->vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3]) + 8 - surf->texturemins[1]) * (1.0 / 16.0);
1912                                 mesh->texcoordlightmap2f[i * 2 + 0] = u * uscale + ubase;
1913                                 mesh->texcoordlightmap2f[i * 2 + 1] = v * vscale + vbase;
1914                                 // LordHavoc: calc lightmap data offset for vertex lighting to use
1915                                 iu = (int) u;
1916                                 iv = (int) v;
1917                                 mesh->lightmapoffsets[i] = (bound(0, iv, tmax) * (smax+1) + bound(0, iu, smax)) * 3;
1918                         }
1919                 }
1920         }
1921 }
1922
1923 static void Mod_Q1BSP_SetParent(mnode_t *node, mnode_t *parent)
1924 {
1925         node->parent = parent;
1926         if (node->contents < 0)
1927                 return;
1928         Mod_Q1BSP_SetParent(node->children[0], node);
1929         Mod_Q1BSP_SetParent(node->children[1], node);
1930 }
1931
1932 static void Mod_Q1BSP_LoadNodes(lump_t *l)
1933 {
1934         int                     i, j, count, p;
1935         dnode_t         *in;
1936         mnode_t         *out;
1937
1938         in = (void *)(mod_base + l->fileofs);
1939         if (l->filelen % sizeof(*in))
1940                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
1941         count = l->filelen / sizeof(*in);
1942         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1943
1944         loadmodel->brushq1.nodes = out;
1945         loadmodel->brushq1.numnodes = count;
1946
1947         for ( i=0 ; i<count ; i++, in++, out++)
1948         {
1949                 for (j=0 ; j<3 ; j++)
1950                 {
1951                         out->mins[j] = LittleShort(in->mins[j]);
1952                         out->maxs[j] = LittleShort(in->maxs[j]);
1953                 }
1954
1955                 p = LittleLong(in->planenum);
1956                 out->plane = loadmodel->brushq1.planes + p;
1957
1958                 out->firstsurface = LittleShort(in->firstface);
1959                 out->numsurfaces = LittleShort(in->numfaces);
1960
1961                 for (j=0 ; j<2 ; j++)
1962                 {
1963                         p = LittleShort(in->children[j]);
1964                         if (p >= 0)
1965                                 out->children[j] = loadmodel->brushq1.nodes + p;
1966                         else
1967                                 out->children[j] = (mnode_t *)(loadmodel->brushq1.leafs + (-1 - p));
1968                 }
1969         }
1970
1971         Mod_Q1BSP_SetParent(loadmodel->brushq1.nodes, NULL);    // sets nodes and leafs
1972 }
1973
1974 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
1975 {
1976         dleaf_t         *in;
1977         mleaf_t         *out;
1978         int                     i, j, count, p;
1979
1980         in = (void *)(mod_base + l->fileofs);
1981         if (l->filelen % sizeof(*in))
1982                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
1983         count = l->filelen / sizeof(*in);
1984         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1985
1986         loadmodel->brushq1.leafs = out;
1987         loadmodel->brushq1.numleafs = count;
1988
1989         for ( i=0 ; i<count ; i++, in++, out++)
1990         {
1991                 for (j=0 ; j<3 ; j++)
1992                 {
1993                         out->mins[j] = LittleShort(in->mins[j]);
1994                         out->maxs[j] = LittleShort(in->maxs[j]);
1995                 }
1996
1997                 p = LittleLong(in->contents);
1998                 out->contents = p;
1999
2000                 out->firstmarksurface = loadmodel->brushq1.marksurfaces +
2001                         LittleShort(in->firstmarksurface);
2002                 out->nummarksurfaces = LittleShort(in->nummarksurfaces);
2003
2004                 p = LittleLong(in->visofs);
2005                 if (p == -1)
2006                         out->compressed_vis = NULL;
2007                 else
2008                         out->compressed_vis = loadmodel->brushq1.visdata + p;
2009
2010                 for (j=0 ; j<4 ; j++)
2011                         out->ambient_sound_level[j] = in->ambient_level[j];
2012
2013                 // FIXME: Insert caustics here
2014         }
2015 }
2016
2017 static void Mod_Q1BSP_LoadClipnodes(lump_t *l)
2018 {
2019         dclipnode_t *in, *out;
2020         int                     i, count;
2021         hull_t          *hull;
2022
2023         in = (void *)(mod_base + l->fileofs);
2024         if (l->filelen % sizeof(*in))
2025                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2026         count = l->filelen / sizeof(*in);
2027         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2028
2029         loadmodel->brushq1.clipnodes = out;
2030         loadmodel->brushq1.numclipnodes = count;
2031
2032         if (loadmodel->brushq1.ishlbsp)
2033         {
2034                 hull = &loadmodel->brushq1.hulls[1];
2035                 hull->clipnodes = out;
2036                 hull->firstclipnode = 0;
2037                 hull->lastclipnode = count-1;
2038                 hull->planes = loadmodel->brushq1.planes;
2039                 hull->clip_mins[0] = -16;
2040                 hull->clip_mins[1] = -16;
2041                 hull->clip_mins[2] = -36;
2042                 hull->clip_maxs[0] = 16;
2043                 hull->clip_maxs[1] = 16;
2044                 hull->clip_maxs[2] = 36;
2045                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2046
2047                 hull = &loadmodel->brushq1.hulls[2];
2048                 hull->clipnodes = out;
2049                 hull->firstclipnode = 0;
2050                 hull->lastclipnode = count-1;
2051                 hull->planes = loadmodel->brushq1.planes;
2052                 hull->clip_mins[0] = -32;
2053                 hull->clip_mins[1] = -32;
2054                 hull->clip_mins[2] = -32;
2055                 hull->clip_maxs[0] = 32;
2056                 hull->clip_maxs[1] = 32;
2057                 hull->clip_maxs[2] = 32;
2058                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2059
2060                 hull = &loadmodel->brushq1.hulls[3];
2061                 hull->clipnodes = out;
2062                 hull->firstclipnode = 0;
2063                 hull->lastclipnode = count-1;
2064                 hull->planes = loadmodel->brushq1.planes;
2065                 hull->clip_mins[0] = -16;
2066                 hull->clip_mins[1] = -16;
2067                 hull->clip_mins[2] = -18;
2068                 hull->clip_maxs[0] = 16;
2069                 hull->clip_maxs[1] = 16;
2070                 hull->clip_maxs[2] = 18;
2071                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2072         }
2073         else
2074         {
2075                 hull = &loadmodel->brushq1.hulls[1];
2076                 hull->clipnodes = out;
2077                 hull->firstclipnode = 0;
2078                 hull->lastclipnode = count-1;
2079                 hull->planes = loadmodel->brushq1.planes;
2080                 hull->clip_mins[0] = -16;
2081                 hull->clip_mins[1] = -16;
2082                 hull->clip_mins[2] = -24;
2083                 hull->clip_maxs[0] = 16;
2084                 hull->clip_maxs[1] = 16;
2085                 hull->clip_maxs[2] = 32;
2086                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2087
2088                 hull = &loadmodel->brushq1.hulls[2];
2089                 hull->clipnodes = out;
2090                 hull->firstclipnode = 0;
2091                 hull->lastclipnode = count-1;
2092                 hull->planes = loadmodel->brushq1.planes;
2093                 hull->clip_mins[0] = -32;
2094                 hull->clip_mins[1] = -32;
2095                 hull->clip_mins[2] = -24;
2096                 hull->clip_maxs[0] = 32;
2097                 hull->clip_maxs[1] = 32;
2098                 hull->clip_maxs[2] = 64;
2099                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2100         }
2101
2102         for (i=0 ; i<count ; i++, out++, in++)
2103         {
2104                 out->planenum = LittleLong(in->planenum);
2105                 out->children[0] = LittleShort(in->children[0]);
2106                 out->children[1] = LittleShort(in->children[1]);
2107                 if (out->children[0] >= count || out->children[1] >= count)
2108                         Host_Error("Corrupt clipping hull(out of range child)\n");
2109         }
2110 }
2111
2112 //Duplicate the drawing hull structure as a clipping hull
2113 static void Mod_Q1BSP_MakeHull0(void)
2114 {
2115         mnode_t         *in;
2116         dclipnode_t *out;
2117         int                     i;
2118         hull_t          *hull;
2119
2120         hull = &loadmodel->brushq1.hulls[0];
2121
2122         in = loadmodel->brushq1.nodes;
2123         out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numnodes * sizeof(dclipnode_t));
2124
2125         hull->clipnodes = out;
2126         hull->firstclipnode = 0;
2127         hull->lastclipnode = loadmodel->brushq1.numnodes - 1;
2128         hull->planes = loadmodel->brushq1.planes;
2129
2130         for (i = 0;i < loadmodel->brushq1.numnodes;i++, out++, in++)
2131         {
2132                 out->planenum = in->plane - loadmodel->brushq1.planes;
2133                 out->children[0] = in->children[0]->contents < 0 ? in->children[0]->contents : in->children[0] - loadmodel->brushq1.nodes;
2134                 out->children[1] = in->children[1]->contents < 0 ? in->children[1]->contents : in->children[1] - loadmodel->brushq1.nodes;
2135         }
2136 }
2137
2138 static void Mod_Q1BSP_LoadMarksurfaces(lump_t *l)
2139 {
2140         int i, j;
2141         short *in;
2142
2143         in = (void *)(mod_base + l->fileofs);
2144         if (l->filelen % sizeof(*in))
2145                 Host_Error("Mod_Q1BSP_LoadMarksurfaces: funny lump size in %s",loadmodel->name);
2146         loadmodel->brushq1.nummarksurfaces = l->filelen / sizeof(*in);
2147         loadmodel->brushq1.marksurfaces = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.nummarksurfaces * sizeof(int));
2148
2149         for (i = 0;i < loadmodel->brushq1.nummarksurfaces;i++)
2150         {
2151                 j = (unsigned) LittleShort(in[i]);
2152                 if (j >= loadmodel->brushq1.numsurfaces)
2153                         Host_Error("Mod_Q1BSP_LoadMarksurfaces: bad surface number");
2154                 loadmodel->brushq1.marksurfaces[i] = j;
2155         }
2156 }
2157
2158 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2159 {
2160         int             i;
2161         int             *in;
2162
2163         in = (void *)(mod_base + l->fileofs);
2164         if (l->filelen % sizeof(*in))
2165                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2166         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2167         loadmodel->brushq1.surfedges = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2168
2169         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2170                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2171 }
2172
2173
2174 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2175 {
2176         int                     i;
2177         mplane_t        *out;
2178         dplane_t        *in;
2179
2180         in = (void *)(mod_base + l->fileofs);
2181         if (l->filelen % sizeof(*in))
2182                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2183
2184         loadmodel->brushq1.numplanes = l->filelen / sizeof(*in);
2185         loadmodel->brushq1.planes = out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numplanes * sizeof(*out));
2186
2187         for (i = 0;i < loadmodel->brushq1.numplanes;i++, in++, out++)
2188         {
2189                 out->normal[0] = LittleFloat(in->normal[0]);
2190                 out->normal[1] = LittleFloat(in->normal[1]);
2191                 out->normal[2] = LittleFloat(in->normal[2]);
2192                 out->dist = LittleFloat(in->dist);
2193
2194                 PlaneClassify(out);
2195         }
2196 }
2197
2198 #define MAX_POINTS_ON_WINDING 64
2199
2200 typedef struct
2201 {
2202         int numpoints;
2203         int padding;
2204         double points[8][3]; // variable sized
2205 }
2206 winding_t;
2207
2208 /*
2209 ==================
2210 NewWinding
2211 ==================
2212 */
2213 static winding_t *NewWinding(int points)
2214 {
2215         winding_t *w;
2216         int size;
2217
2218         if (points > MAX_POINTS_ON_WINDING)
2219                 Sys_Error("NewWinding: too many points\n");
2220
2221         size = sizeof(winding_t) + sizeof(double[3]) * (points - 8);
2222         w = Mem_Alloc(loadmodel->mempool, size);
2223         memset(w, 0, size);
2224
2225         return w;
2226 }
2227
2228 static void FreeWinding(winding_t *w)
2229 {
2230         Mem_Free(w);
2231 }
2232
2233 /*
2234 =================
2235 BaseWindingForPlane
2236 =================
2237 */
2238 static winding_t *BaseWindingForPlane(mplane_t *p)
2239 {
2240         double org[3], vright[3], vup[3], normal[3];
2241         winding_t *w;
2242
2243         VectorCopy(p->normal, normal);
2244         VectorVectorsDouble(normal, vright, vup);
2245
2246         VectorScale(vup, 1024.0*1024.0*1024.0, vup);
2247         VectorScale(vright, 1024.0*1024.0*1024.0, vright);
2248
2249         // project a really big axis aligned box onto the plane
2250         w = NewWinding(4);
2251
2252         VectorScale(p->normal, p->dist, org);
2253
2254         VectorSubtract(org, vright, w->points[0]);
2255         VectorAdd(w->points[0], vup, w->points[0]);
2256
2257         VectorAdd(org, vright, w->points[1]);
2258         VectorAdd(w->points[1], vup, w->points[1]);
2259
2260         VectorAdd(org, vright, w->points[2]);
2261         VectorSubtract(w->points[2], vup, w->points[2]);
2262
2263         VectorSubtract(org, vright, w->points[3]);
2264         VectorSubtract(w->points[3], vup, w->points[3]);
2265
2266         w->numpoints = 4;
2267
2268         return w;
2269 }
2270
2271 /*
2272 ==================
2273 ClipWinding
2274
2275 Clips the winding to the plane, returning the new winding on the positive side
2276 Frees the input winding.
2277 If keepon is true, an exactly on-plane winding will be saved, otherwise
2278 it will be clipped away.
2279 ==================
2280 */
2281 static winding_t *ClipWinding(winding_t *in, mplane_t *split, int keepon)
2282 {
2283         double  dists[MAX_POINTS_ON_WINDING + 1];
2284         int             sides[MAX_POINTS_ON_WINDING + 1];
2285         int             counts[3];
2286         double  dot;
2287         int             i, j;
2288         double  *p1, *p2;
2289         double  mid[3];
2290         winding_t       *neww;
2291         int             maxpts;
2292
2293         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
2294
2295         // determine sides for each point
2296         for (i = 0;i < in->numpoints;i++)
2297         {
2298                 dists[i] = dot = DotProduct(in->points[i], split->normal) - split->dist;
2299                 if (dot > ON_EPSILON)
2300                         sides[i] = SIDE_FRONT;
2301                 else if (dot < -ON_EPSILON)
2302                         sides[i] = SIDE_BACK;
2303                 else
2304                         sides[i] = SIDE_ON;
2305                 counts[sides[i]]++;
2306         }
2307         sides[i] = sides[0];
2308         dists[i] = dists[0];
2309
2310         if (keepon && !counts[0] && !counts[1])
2311                 return in;
2312
2313         if (!counts[0])
2314         {
2315                 FreeWinding(in);
2316                 return NULL;
2317         }
2318         if (!counts[1])
2319                 return in;
2320
2321         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
2322         if (maxpts > MAX_POINTS_ON_WINDING)
2323                 Sys_Error("ClipWinding: maxpts > MAX_POINTS_ON_WINDING");
2324
2325         neww = NewWinding(maxpts);
2326
2327         for (i = 0;i < in->numpoints;i++)
2328         {
2329                 if (neww->numpoints >= maxpts)
2330                         Sys_Error("ClipWinding: points exceeded estimate");
2331
2332                 p1 = in->points[i];
2333
2334                 if (sides[i] == SIDE_ON)
2335                 {
2336                         VectorCopy(p1, neww->points[neww->numpoints]);
2337                         neww->numpoints++;
2338                         continue;
2339                 }
2340
2341                 if (sides[i] == SIDE_FRONT)
2342                 {
2343                         VectorCopy(p1, neww->points[neww->numpoints]);
2344                         neww->numpoints++;
2345                 }
2346
2347                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
2348                         continue;
2349
2350                 // generate a split point
2351                 p2 = in->points[(i+1)%in->numpoints];
2352
2353                 dot = dists[i] / (dists[i]-dists[i+1]);
2354                 for (j = 0;j < 3;j++)
2355                 {       // avoid round off error when possible
2356                         if (split->normal[j] == 1)
2357                                 mid[j] = split->dist;
2358                         else if (split->normal[j] == -1)
2359                                 mid[j] = -split->dist;
2360                         else
2361                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
2362                 }
2363
2364                 VectorCopy(mid, neww->points[neww->numpoints]);
2365                 neww->numpoints++;
2366         }
2367
2368         // free the original winding
2369         FreeWinding(in);
2370
2371         return neww;
2372 }
2373
2374
2375 /*
2376 ==================
2377 DivideWinding
2378
2379 Divides a winding by a plane, producing one or two windings.  The
2380 original winding is not damaged or freed.  If only on one side, the
2381 returned winding will be the input winding.  If on both sides, two
2382 new windings will be created.
2383 ==================
2384 */
2385 static void DivideWinding(winding_t *in, mplane_t *split, winding_t **front, winding_t **back)
2386 {
2387         double  dists[MAX_POINTS_ON_WINDING + 1];
2388         int             sides[MAX_POINTS_ON_WINDING + 1];
2389         int             counts[3];
2390         double  dot;
2391         int             i, j;
2392         double  *p1, *p2;
2393         double  mid[3];
2394         winding_t       *f, *b;
2395         int             maxpts;
2396
2397         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
2398
2399         // determine sides for each point
2400         for (i = 0;i < in->numpoints;i++)
2401         {
2402                 dot = DotProduct(in->points[i], split->normal);
2403                 dot -= split->dist;
2404                 dists[i] = dot;
2405                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
2406                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
2407                 else sides[i] = SIDE_ON;
2408                 counts[sides[i]]++;
2409         }
2410         sides[i] = sides[0];
2411         dists[i] = dists[0];
2412
2413         *front = *back = NULL;
2414
2415         if (!counts[0])
2416         {
2417                 *back = in;
2418                 return;
2419         }
2420         if (!counts[1])
2421         {
2422                 *front = in;
2423                 return;
2424         }
2425
2426         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
2427
2428         if (maxpts > MAX_POINTS_ON_WINDING)
2429                 Sys_Error("ClipWinding: maxpts > MAX_POINTS_ON_WINDING");
2430
2431         *front = f = NewWinding(maxpts);
2432         *back = b = NewWinding(maxpts);
2433
2434         for (i = 0;i < in->numpoints;i++)
2435         {
2436                 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
2437                         Sys_Error("DivideWinding: points exceeded estimate");
2438
2439                 p1 = in->points[i];
2440
2441                 if (sides[i] == SIDE_ON)
2442                 {
2443                         VectorCopy(p1, f->points[f->numpoints]);
2444                         f->numpoints++;
2445                         VectorCopy(p1, b->points[b->numpoints]);
2446                         b->numpoints++;
2447                         continue;
2448                 }
2449
2450                 if (sides[i] == SIDE_FRONT)
2451                 {
2452                         VectorCopy(p1, f->points[f->numpoints]);
2453                         f->numpoints++;
2454                 }
2455                 else if (sides[i] == SIDE_BACK)
2456                 {
2457                         VectorCopy(p1, b->points[b->numpoints]);
2458                         b->numpoints++;
2459                 }
2460
2461                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
2462                         continue;
2463
2464                 // generate a split point
2465                 p2 = in->points[(i+1)%in->numpoints];
2466
2467                 dot = dists[i] / (dists[i]-dists[i+1]);
2468                 for (j = 0;j < 3;j++)
2469                 {       // avoid round off error when possible
2470                         if (split->normal[j] == 1)
2471                                 mid[j] = split->dist;
2472                         else if (split->normal[j] == -1)
2473                                 mid[j] = -split->dist;
2474                         else
2475                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
2476                 }
2477
2478                 VectorCopy(mid, f->points[f->numpoints]);
2479                 f->numpoints++;
2480                 VectorCopy(mid, b->points[b->numpoints]);
2481                 b->numpoints++;
2482         }
2483 }
2484
2485 typedef struct portal_s
2486 {
2487         mplane_t plane;
2488         mnode_t *nodes[2];              // [0] = front side of plane
2489         struct portal_s *next[2];
2490         winding_t *winding;
2491         struct portal_s *chain; // all portals are linked into a list
2492 }
2493 portal_t;
2494
2495 static portal_t *portalchain;
2496
2497 /*
2498 ===========
2499 AllocPortal
2500 ===========
2501 */
2502 static portal_t *AllocPortal(void)
2503 {
2504         portal_t *p;
2505         p = Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2506         p->chain = portalchain;
2507         portalchain = p;
2508         return p;
2509 }
2510
2511 static void FreePortal(portal_t *p)
2512 {
2513         Mem_Free(p);
2514 }
2515
2516 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2517 {
2518         // calculate children first
2519         if (node->children[0]->contents >= 0)
2520                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2521         if (node->children[1]->contents >= 0)
2522                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2523
2524         // make combined bounding box from children
2525         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2526         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2527         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2528         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2529         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2530         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2531 }
2532
2533 static void Mod_Q1BSP_FinalizePortals(void)
2534 {
2535         int i, j, numportals, numpoints;
2536         portal_t *p, *pnext;
2537         mportal_t *portal;
2538         mvertex_t *point;
2539         mleaf_t *leaf, *endleaf;
2540         winding_t *w;
2541
2542         // recalculate bounding boxes for all leafs(because qbsp is very sloppy)
2543         leaf = loadmodel->brushq1.leafs;
2544         endleaf = leaf + loadmodel->brushq1.numleafs;
2545         for (;leaf < endleaf;leaf++)
2546         {
2547                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2548                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2549         }
2550         p = portalchain;
2551         while (p)
2552         {
2553                 if (p->winding)
2554                 {
2555                         for (i = 0;i < 2;i++)
2556                         {
2557                                 leaf = (mleaf_t *)p->nodes[i];
2558                                 w = p->winding;
2559                                 for (j = 0;j < w->numpoints;j++)
2560                                 {
2561                                         if (leaf->mins[0] > w->points[j][0]) leaf->mins[0] = w->points[j][0];
2562                                         if (leaf->mins[1] > w->points[j][1]) leaf->mins[1] = w->points[j][1];
2563                                         if (leaf->mins[2] > w->points[j][2]) leaf->mins[2] = w->points[j][2];
2564                                         if (leaf->maxs[0] < w->points[j][0]) leaf->maxs[0] = w->points[j][0];
2565                                         if (leaf->maxs[1] < w->points[j][1]) leaf->maxs[1] = w->points[j][1];
2566                                         if (leaf->maxs[2] < w->points[j][2]) leaf->maxs[2] = w->points[j][2];
2567                                 }
2568                         }
2569                 }
2570                 p = p->chain;
2571         }
2572
2573         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brushq1.nodes);
2574
2575         // tally up portal and point counts
2576         p = portalchain;
2577         numportals = 0;
2578         numpoints = 0;
2579         while (p)
2580         {
2581                 // note: this check must match the one below or it will usually corrupt memory
2582                 // 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
2583                 if (p->winding && p->nodes[0] != p->nodes[1]
2584                  && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2585                  && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2586                 {
2587                         numportals += 2;
2588                         numpoints += p->winding->numpoints * 2;
2589                 }
2590                 p = p->chain;
2591         }
2592         loadmodel->brushq1.portals = Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2593         loadmodel->brushq1.numportals = numportals;
2594         loadmodel->brushq1.portalpoints = (void *)((qbyte *) loadmodel->brushq1.portals + numportals * sizeof(mportal_t));
2595         loadmodel->brushq1.numportalpoints = numpoints;
2596         // clear all leaf portal chains
2597         for (i = 0;i < loadmodel->brushq1.numleafs;i++)
2598                 loadmodel->brushq1.leafs[i].portals = NULL;
2599         // process all portals in the global portal chain, while freeing them
2600         portal = loadmodel->brushq1.portals;
2601         point = loadmodel->brushq1.portalpoints;
2602         p = portalchain;
2603         portalchain = NULL;
2604         while (p)
2605         {
2606                 pnext = p->chain;
2607
2608                 if (p->winding)
2609                 {
2610                         // note: this check must match the one above or it will usually corrupt memory
2611                         // 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
2612                         if (p->nodes[0] != p->nodes[1]
2613                          && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2614                          && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2615                         {
2616                                 // first make the back to front portal(forward portal)
2617                                 portal->points = point;
2618                                 portal->numpoints = p->winding->numpoints;
2619                                 portal->plane.dist = p->plane.dist;
2620                                 VectorCopy(p->plane.normal, portal->plane.normal);
2621                                 portal->here = (mleaf_t *)p->nodes[1];
2622                                 portal->past = (mleaf_t *)p->nodes[0];
2623                                 // copy points
2624                                 for (j = 0;j < portal->numpoints;j++)
2625                                 {
2626                                         VectorCopy(p->winding->points[j], point->position);
2627                                         point++;
2628                                 }
2629                                 PlaneClassify(&portal->plane);
2630
2631                                 // link into leaf's portal chain
2632                                 portal->next = portal->here->portals;
2633                                 portal->here->portals = portal;
2634
2635                                 // advance to next portal
2636                                 portal++;
2637
2638                                 // then make the front to back portal(backward portal)
2639                                 portal->points = point;
2640                                 portal->numpoints = p->winding->numpoints;
2641                                 portal->plane.dist = -p->plane.dist;
2642                                 VectorNegate(p->plane.normal, portal->plane.normal);
2643                                 portal->here = (mleaf_t *)p->nodes[0];
2644                                 portal->past = (mleaf_t *)p->nodes[1];
2645                                 // copy points
2646                                 for (j = portal->numpoints - 1;j >= 0;j--)
2647                                 {
2648                                         VectorCopy(p->winding->points[j], point->position);
2649                                         point++;
2650                                 }
2651                                 PlaneClassify(&portal->plane);
2652
2653                                 // link into leaf's portal chain
2654                                 portal->next = portal->here->portals;
2655                                 portal->here->portals = portal;
2656
2657                                 // advance to next portal
2658                                 portal++;
2659                         }
2660                         FreeWinding(p->winding);
2661                 }
2662                 FreePortal(p);
2663                 p = pnext;
2664         }
2665 }
2666
2667 /*
2668 =============
2669 AddPortalToNodes
2670 =============
2671 */
2672 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2673 {
2674         if (!front)
2675                 Host_Error("AddPortalToNodes: NULL front node");
2676         if (!back)
2677                 Host_Error("AddPortalToNodes: NULL back node");
2678         if (p->nodes[0] || p->nodes[1])
2679                 Host_Error("AddPortalToNodes: already included");
2680         // 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
2681
2682         p->nodes[0] = front;
2683         p->next[0] = (portal_t *)front->portals;
2684         front->portals = (mportal_t *)p;
2685
2686         p->nodes[1] = back;
2687         p->next[1] = (portal_t *)back->portals;
2688         back->portals = (mportal_t *)p;
2689 }
2690
2691 /*
2692 =============
2693 RemovePortalFromNode
2694 =============
2695 */
2696 static void RemovePortalFromNodes(portal_t *portal)
2697 {
2698         int i;
2699         mnode_t *node;
2700         void **portalpointer;
2701         portal_t *t;
2702         for (i = 0;i < 2;i++)
2703         {
2704                 node = portal->nodes[i];
2705
2706                 portalpointer = (void **) &node->portals;
2707                 while (1)
2708                 {
2709                         t = *portalpointer;
2710                         if (!t)
2711                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2712
2713                         if (t == portal)
2714                         {
2715                                 if (portal->nodes[0] == node)
2716                                 {
2717                                         *portalpointer = portal->next[0];
2718                                         portal->nodes[0] = NULL;
2719                                 }
2720                                 else if (portal->nodes[1] == node)
2721                                 {
2722                                         *portalpointer = portal->next[1];
2723                                         portal->nodes[1] = NULL;
2724                                 }
2725                                 else
2726                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2727                                 break;
2728                         }
2729
2730                         if (t->nodes[0] == node)
2731                                 portalpointer = (void **) &t->next[0];
2732                         else if (t->nodes[1] == node)
2733                                 portalpointer = (void **) &t->next[1];
2734                         else
2735                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2736                 }
2737         }
2738 }
2739
2740 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2741 {
2742         int side;
2743         mnode_t *front, *back, *other_node;
2744         mplane_t clipplane, *plane;
2745         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2746         winding_t *nodeportalwinding, *frontwinding, *backwinding;
2747
2748         // if a leaf, we're done
2749         if (node->contents)
2750                 return;
2751
2752         plane = node->plane;
2753
2754         front = node->children[0];
2755         back = node->children[1];
2756         if (front == back)
2757                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2758
2759         // create the new portal by generating a polygon for the node plane,
2760         // and clipping it by all of the other portals(which came from nodes above this one)
2761         nodeportal = AllocPortal();
2762         nodeportal->plane = *node->plane;
2763
2764         nodeportalwinding = BaseWindingForPlane(node->plane);
2765         side = 0;       // shut up compiler warning
2766         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2767         {
2768                 clipplane = portal->plane;
2769                 if (portal->nodes[0] == portal->nodes[1])
2770                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2771                 if (portal->nodes[0] == node)
2772                         side = 0;
2773                 else if (portal->nodes[1] == node)
2774                 {
2775                         clipplane.dist = -clipplane.dist;
2776                         VectorNegate(clipplane.normal, clipplane.normal);
2777                         side = 1;
2778                 }
2779                 else
2780                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2781
2782                 nodeportalwinding = ClipWinding(nodeportalwinding, &clipplane, true);
2783                 if (!nodeportalwinding)
2784                 {
2785                         Con_Printf("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2786                         break;
2787                 }
2788         }
2789
2790         if (nodeportalwinding)
2791         {
2792                 // if the plane was not clipped on all sides, there was an error
2793                 nodeportal->winding = nodeportalwinding;
2794                 AddPortalToNodes(nodeportal, front, back);
2795         }
2796
2797         // split the portals of this node along this node's plane and assign them to the children of this node
2798         // (migrating the portals downward through the tree)
2799         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2800         {
2801                 if (portal->nodes[0] == portal->nodes[1])
2802                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2803                 if (portal->nodes[0] == node)
2804                         side = 0;
2805                 else if (portal->nodes[1] == node)
2806                         side = 1;
2807                 else
2808                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2809                 nextportal = portal->next[side];
2810
2811                 other_node = portal->nodes[!side];
2812                 RemovePortalFromNodes(portal);
2813
2814                 // cut the portal into two portals, one on each side of the node plane
2815                 DivideWinding(portal->winding, plane, &frontwinding, &backwinding);
2816
2817                 if (!frontwinding)
2818                 {
2819                         if (side == 0)
2820                                 AddPortalToNodes(portal, back, other_node);
2821                         else
2822                                 AddPortalToNodes(portal, other_node, back);
2823                         continue;
2824                 }
2825                 if (!backwinding)
2826                 {
2827                         if (side == 0)
2828                                 AddPortalToNodes(portal, front, other_node);
2829                         else
2830                                 AddPortalToNodes(portal, other_node, front);
2831                         continue;
2832                 }
2833
2834                 // the winding is split
2835                 splitportal = AllocPortal();
2836                 temp = splitportal->chain;
2837                 *splitportal = *portal;
2838                 splitportal->chain = temp;
2839                 splitportal->winding = backwinding;
2840                 FreeWinding(portal->winding);
2841                 portal->winding = frontwinding;
2842
2843                 if (side == 0)
2844                 {
2845                         AddPortalToNodes(portal, front, other_node);
2846                         AddPortalToNodes(splitportal, back, other_node);
2847                 }
2848                 else
2849                 {
2850                         AddPortalToNodes(portal, other_node, front);
2851                         AddPortalToNodes(splitportal, other_node, back);
2852                 }
2853         }
2854
2855         Mod_Q1BSP_RecursiveNodePortals(front);
2856         Mod_Q1BSP_RecursiveNodePortals(back);
2857 }
2858
2859
2860 static void Mod_Q1BSP_MakePortals(void)
2861 {
2862         portalchain = NULL;
2863         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brushq1.nodes);
2864         Mod_Q1BSP_FinalizePortals();
2865 }
2866
2867 static void Mod_Q1BSP_BuildSurfaceNeighbors(msurface_t *surfaces, int numsurfaces, mempool_t *mempool)
2868 {
2869 #if 0
2870         int surfnum, vertnum, vertnum2, snum, vnum, vnum2;
2871         msurface_t *surf, *s;
2872         float *v0, *v1, *v2, *v3;
2873         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2874                 surf->neighborsurfaces = Mem_Alloc(mempool, surf->poly_numverts * sizeof(msurface_t *));
2875         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2876         {
2877                 for (vertnum = surf->poly_numverts - 1, vertnum2 = 0, v0 = surf->poly_verts + (surf->poly_numverts - 1) * 3, v1 = surf->poly_verts;vertnum2 < surf->poly_numverts;vertnum = vertnum2, vertnum2++, v0 = v1, v1 += 3)
2878                 {
2879                         if (surf->neighborsurfaces[vertnum])
2880                                 continue;
2881                         surf->neighborsurfaces[vertnum] = NULL;
2882                         for (s = surfaces, snum = 0;snum < numsurfaces;s++, snum++)
2883                         {
2884                                 if (s->poly_mins[0] > (surf->poly_maxs[0] + 1) || s->poly_maxs[0] < (surf->poly_mins[0] - 1)
2885                                  || s->poly_mins[1] > (surf->poly_maxs[1] + 1) || s->poly_maxs[1] < (surf->poly_mins[1] - 1)
2886                                  || s->poly_mins[2] > (surf->poly_maxs[2] + 1) || s->poly_maxs[2] < (surf->poly_mins[2] - 1)
2887                                  || s == surf)
2888                                         continue;
2889                                 for (vnum = 0;vnum < s->poly_numverts;vnum++)
2890                                         if (s->neighborsurfaces[vnum] == surf)
2891                                                 break;
2892                                 if (vnum < s->poly_numverts)
2893                                         continue;
2894                                 for (vnum = s->poly_numverts - 1, vnum2 = 0, v2 = s->poly_verts + (s->poly_numverts - 1) * 3, v3 = s->poly_verts;vnum2 < s->poly_numverts;vnum = vnum2, vnum2++, v2 = v3, v3 += 3)
2895                                 {
2896                                         if (s->neighborsurfaces[vnum] == NULL
2897                                          && ((v0[0] == v2[0] && v0[1] == v2[1] && v0[2] == v2[2] && v1[0] == v3[0] && v1[1] == v3[1] && v1[2] == v3[2])
2898                                           || (v1[0] == v2[0] && v1[1] == v2[1] && v1[2] == v2[2] && v0[0] == v3[0] && v0[1] == v3[1] && v0[2] == v3[2])))
2899                                         {
2900                                                 surf->neighborsurfaces[vertnum] = s;
2901                                                 s->neighborsurfaces[vnum] = surf;
2902                                                 break;
2903                                         }
2904                                 }
2905                                 if (vnum < s->poly_numverts)
2906                                         break;
2907                         }
2908                 }
2909         }
2910 #endif
2911 }
2912
2913 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
2914 {
2915         int i, j, stylecounts[256], totalcount, remapstyles[256];
2916         msurface_t *surf;
2917         memset(stylecounts, 0, sizeof(stylecounts));
2918         for (i = 0;i < model->brushq1.nummodelsurfaces;i++)
2919         {
2920                 surf = model->brushq1.surfaces + model->brushq1.firstmodelsurface + i;
2921                 for (j = 0;j < MAXLIGHTMAPS;j++)
2922                         stylecounts[surf->styles[j]]++;
2923         }
2924         totalcount = 0;
2925         model->brushq1.light_styles = 0;
2926         for (i = 0;i < 255;i++)
2927         {
2928                 if (stylecounts[i])
2929                 {
2930                         remapstyles[i] = model->brushq1.light_styles++;
2931                         totalcount += stylecounts[i] + 1;
2932                 }
2933         }
2934         if (!totalcount)
2935                 return;
2936         model->brushq1.light_style = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(qbyte));
2937         model->brushq1.light_stylevalue = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(int));
2938         model->brushq1.light_styleupdatechains = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(msurface_t **));
2939         model->brushq1.light_styleupdatechainsbuffer = Mem_Alloc(mempool, totalcount * sizeof(msurface_t *));
2940         model->brushq1.light_styles = 0;
2941         for (i = 0;i < 255;i++)
2942                 if (stylecounts[i])
2943                         model->brushq1.light_style[model->brushq1.light_styles++] = i;
2944         j = 0;
2945         for (i = 0;i < model->brushq1.light_styles;i++)
2946         {
2947                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2948                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2949         }
2950         for (i = 0;i < model->brushq1.nummodelsurfaces;i++)
2951         {
2952                 surf = model->brushq1.surfaces + model->brushq1.firstmodelsurface + i;
2953                 for (j = 0;j < MAXLIGHTMAPS;j++)
2954                         if (surf->styles[j] != 255)
2955                                 *model->brushq1.light_styleupdatechains[remapstyles[surf->styles[j]]]++ = surf;
2956         }
2957         j = 0;
2958         for (i = 0;i < model->brushq1.light_styles;i++)
2959         {
2960                 *model->brushq1.light_styleupdatechains[i] = NULL;
2961                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2962                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2963         }
2964 }
2965
2966 static void Mod_Q1BSP_BuildPVSTextureChains(model_t *model)
2967 {
2968         int i, j;
2969         for (i = 0;i < model->brushq1.numtextures;i++)
2970                 model->brushq1.pvstexturechainslength[i] = 0;
2971         for (i = 0, j = model->brushq1.firstmodelsurface;i < model->brushq1.nummodelsurfaces;i++, j++)
2972         {
2973                 if (model->brushq1.surfacepvsframes[j] == model->brushq1.pvsframecount)
2974                 {
2975                         model->brushq1.pvssurflist[model->brushq1.pvssurflistlength++] = j;
2976                         model->brushq1.pvstexturechainslength[model->brushq1.surfaces[j].texinfo->texture->number]++;
2977                 }
2978         }
2979         for (i = 0, j = 0;i < model->brushq1.numtextures;i++)
2980         {
2981                 if (model->brushq1.pvstexturechainslength[i])
2982                 {
2983                         model->brushq1.pvstexturechains[i] = model->brushq1.pvstexturechainsbuffer + j;
2984                         j += model->brushq1.pvstexturechainslength[i] + 1;
2985                 }
2986                 else
2987                         model->brushq1.pvstexturechains[i] = NULL;
2988         }
2989         for (i = 0, j = model->brushq1.firstmodelsurface;i < model->brushq1.nummodelsurfaces;i++, j++)
2990                 if (model->brushq1.surfacepvsframes[j] == model->brushq1.pvsframecount)
2991                         *model->brushq1.pvstexturechains[model->brushq1.surfaces[j].texinfo->texture->number]++ = model->brushq1.surfaces + j;
2992         for (i = 0;i < model->brushq1.numtextures;i++)
2993         {
2994                 if (model->brushq1.pvstexturechainslength[i])
2995                 {
2996                         *model->brushq1.pvstexturechains[i] = NULL;
2997                         model->brushq1.pvstexturechains[i] -= model->brushq1.pvstexturechainslength[i];
2998                 }
2999         }
3000 }
3001
3002 extern void R_Model_Brush_DrawSky(entity_render_t *ent);
3003 extern void R_Model_Brush_Draw(entity_render_t *ent);
3004 extern void R_Model_Brush_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin, float lightradius);
3005 extern void R_Model_Brush_DrawLight(entity_render_t *ent, vec3_t relativelightorigin, vec3_t relativeeyeorigin, float lightradius, float *lightcolor, const matrix4x4_t *matrix_modeltofilter, const matrix4x4_t *matrix_modeltoattenuationxyz, const matrix4x4_t *matrix_modeltoattenuationz);
3006 void Mod_Q1BSP_Load(model_t *mod, void *buffer)
3007 {
3008         int i, j, k;
3009         dheader_t *header;
3010         dmodel_t *bm;
3011         mempool_t *mainmempool;
3012         char *loadname;
3013         model_t *originalloadmodel;
3014         float dist, modelyawradius, modelradius, *vec;
3015         msurface_t *surf;
3016         surfmesh_t *mesh;
3017
3018         mod->type = mod_brush;
3019
3020         header = (dheader_t *)buffer;
3021
3022         i = LittleLong(header->version);
3023         if (i != BSPVERSION && i != 30)
3024                 Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i(Quake) or 30(HalfLife))", mod->name, i, BSPVERSION);
3025         mod->brushq1.ishlbsp = i == 30;
3026
3027         mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
3028         mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
3029         mod->brush.TraceBox = Mod_Q1BSP_TraceBox;
3030         mod->brushq1.PointInLeaf = Mod_Q1BSP_PointInLeaf;
3031         mod->brushq1.LeafPVS = Mod_Q1BSP_LeafPVS;
3032         mod->brushq1.BuildPVSTextureChains = Mod_Q1BSP_BuildPVSTextureChains;
3033
3034         if (loadmodel->isworldmodel)
3035         {
3036                 Cvar_SetValue("halflifebsp", mod->brushq1.ishlbsp);
3037                 // until we get a texture for it...
3038                 R_ResetQuakeSky();
3039         }
3040
3041 // swap all the lumps
3042         mod_base = (qbyte *)header;
3043
3044         for (i = 0;i < (int) sizeof(dheader_t) / 4;i++)
3045                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
3046
3047 // load into heap
3048
3049         // store which lightmap format to use
3050         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3051
3052         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
3053         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
3054         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
3055         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
3056         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
3057         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
3058         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
3059         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
3060         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
3061         Mod_Q1BSP_LoadMarksurfaces(&header->lumps[LUMP_MARKSURFACES]);
3062         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
3063         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
3064         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
3065         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES]);
3066         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS]);
3067
3068         Mod_Q1BSP_MakeHull0();
3069         Mod_Q1BSP_MakePortals();
3070
3071         mod->numframes = 2;             // regular and alternate animation
3072
3073         mainmempool = mod->mempool;
3074         loadname = mod->name;
3075
3076         Mod_Q1BSP_LoadLightList();
3077         originalloadmodel = loadmodel;
3078
3079 //
3080 // set up the submodels(FIXME: this is confusing)
3081 //
3082         for (i = 0;i < mod->brushq1.numsubmodels;i++)
3083         {
3084                 bm = &mod->brushq1.submodels[i];
3085
3086                 mod->brushq1.hulls[0].firstclipnode = bm->headnode[0];
3087                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
3088                 {
3089                         mod->brushq1.hulls[j].firstclipnode = bm->headnode[j];
3090                         mod->brushq1.hulls[j].lastclipnode = mod->brushq1.numclipnodes - 1;
3091                 }
3092
3093                 mod->brushq1.firstmodelsurface = bm->firstface;
3094                 mod->brushq1.nummodelsurfaces = bm->numfaces;
3095
3096                 // this gets altered below if sky is used
3097                 mod->DrawSky = NULL;
3098                 mod->Draw = R_Model_Brush_Draw;
3099                 mod->DrawFakeShadow = NULL;
3100                 mod->DrawShadowVolume = R_Model_Brush_DrawShadowVolume;
3101                 mod->DrawLight = R_Model_Brush_DrawLight;
3102                 mod->brushq1.pvstexturechains = Mem_Alloc(originalloadmodel->mempool, mod->brushq1.numtextures * sizeof(msurface_t **));
3103                 mod->brushq1.pvstexturechainsbuffer = Mem_Alloc(originalloadmodel->mempool,(mod->brushq1.nummodelsurfaces + mod->brushq1.numtextures) * sizeof(msurface_t *));
3104                 mod->brushq1.pvstexturechainslength = Mem_Alloc(originalloadmodel->mempool, mod->brushq1.numtextures * sizeof(int));
3105                 Mod_Q1BSP_BuildPVSTextureChains(mod);
3106                 Mod_Q1BSP_BuildLightmapUpdateChains(originalloadmodel->mempool, mod);
3107                 if (mod->brushq1.nummodelsurfaces)
3108                 {
3109                         // LordHavoc: calculate bmodel bounding box rather than trusting what it says
3110                         mod->normalmins[0] = mod->normalmins[1] = mod->normalmins[2] = 1000000000.0f;
3111                         mod->normalmaxs[0] = mod->normalmaxs[1] = mod->normalmaxs[2] = -1000000000.0f;
3112                         modelyawradius = 0;
3113                         modelradius = 0;
3114                         for (j = 0, surf = &mod->brushq1.surfaces[mod->brushq1.firstmodelsurface];j < mod->brushq1.nummodelsurfaces;j++, surf++)
3115                         {
3116                                 // we only need to have a drawsky function if it is used(usually only on world model)
3117                                 if (surf->texinfo->texture->shader == &Cshader_sky)
3118                                         mod->DrawSky = R_Model_Brush_DrawSky;
3119                                 // LordHavoc: submodels always clip, even if water
3120                                 if (mod->brushq1.numsubmodels - 1)
3121                                         surf->flags |= SURF_SOLIDCLIP;
3122                                 // calculate bounding shapes
3123                                 for (mesh = surf->mesh;mesh;mesh = mesh->chain)
3124                                 {
3125                                         for (k = 0, vec = mesh->vertex3f;k < mesh->numverts;k++, vec += 3)
3126                                         {
3127                                                 if (mod->normalmins[0] > vec[0]) mod->normalmins[0] = vec[0];
3128                                                 if (mod->normalmins[1] > vec[1]) mod->normalmins[1] = vec[1];
3129                                                 if (mod->normalmins[2] > vec[2]) mod->normalmins[2] = vec[2];
3130                                                 if (mod->normalmaxs[0] < vec[0]) mod->normalmaxs[0] = vec[0];
3131                                                 if (mod->normalmaxs[1] < vec[1]) mod->normalmaxs[1] = vec[1];
3132                                                 if (mod->normalmaxs[2] < vec[2]) mod->normalmaxs[2] = vec[2];
3133                                                 dist = vec[0]*vec[0]+vec[1]*vec[1];
3134                                                 if (modelyawradius < dist)
3135                                                         modelyawradius = dist;
3136                                                 dist += vec[2]*vec[2];
3137                                                 if (modelradius < dist)
3138                                                         modelradius = dist;
3139                                         }
3140                                 }
3141                         }
3142                         modelyawradius = sqrt(modelyawradius);
3143                         modelradius = sqrt(modelradius);
3144                         mod->yawmins[0] = mod->yawmins[1] = - (mod->yawmaxs[0] = mod->yawmaxs[1] = modelyawradius);
3145                         mod->yawmins[2] = mod->normalmins[2];
3146                         mod->yawmaxs[2] = mod->normalmaxs[2];
3147                         mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
3148                         mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
3149                         mod->radius = modelradius;
3150                         mod->radius2 = modelradius * modelradius;
3151                 }
3152                 else
3153                 {
3154                         // LordHavoc: empty submodel(lacrima.bsp has such a glitch)
3155                         Con_Printf("warning: empty submodel *%i in %s\n", i+1, loadname);
3156                 }
3157                 Mod_Q1BSP_BuildSurfaceNeighbors(mod->brushq1.surfaces + mod->brushq1.firstmodelsurface, mod->brushq1.nummodelsurfaces, originalloadmodel->mempool);
3158
3159                 mod->brushq1.numleafs = bm->visleafs;
3160
3161                 // LordHavoc: only register submodels if it is the world
3162                 // (prevents bsp models from replacing world submodels)
3163                 if (loadmodel->isworldmodel && i < (mod->brushq1.numsubmodels - 1))
3164                 {
3165                         char    name[10];
3166                         // duplicate the basic information
3167                         sprintf(name, "*%i", i+1);
3168                         loadmodel = Mod_FindName(name);
3169                         *loadmodel = *mod;
3170                         strcpy(loadmodel->name, name);
3171                         // textures and memory belong to the main model
3172                         loadmodel->texturepool = NULL;
3173                         loadmodel->mempool = NULL;
3174                         mod = loadmodel;
3175                 }
3176         }
3177
3178         loadmodel = originalloadmodel;
3179         //Mod_Q1BSP_ProcessLightList();
3180 }
3181
3182 static void Mod_Q2BSP_LoadEntities(lump_t *l)
3183 {
3184 }
3185
3186 static void Mod_Q2BSP_LoadPlanes(lump_t *l)
3187 {
3188 /*
3189         d_t *in;
3190         m_t *out;
3191         int i, count;
3192
3193         in = (void *)(mod_base + l->fileofs);
3194         if (l->filelen % sizeof(*in))
3195                 Host_Error("Mod_Q2BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3196         count = l->filelen / sizeof(*in);
3197         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3198
3199         loadmodel-> = out;
3200         loadmodel->num = count;
3201
3202         for (i = 0;i < count;i++, in++, out++)
3203         {
3204         }
3205 */
3206 }
3207
3208 static void Mod_Q2BSP_LoadVertices(lump_t *l)
3209 {
3210 /*
3211         d_t *in;
3212         m_t *out;
3213         int i, count;
3214
3215         in = (void *)(mod_base + l->fileofs);
3216         if (l->filelen % sizeof(*in))
3217                 Host_Error("Mod_Q2BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3218         count = l->filelen / sizeof(*in);
3219         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3220
3221         loadmodel-> = out;
3222         loadmodel->num = count;
3223
3224         for (i = 0;i < count;i++, in++, out++)
3225         {
3226         }
3227 */
3228 }
3229
3230 static void Mod_Q2BSP_LoadVisibility(lump_t *l)
3231 {
3232 /*
3233         d_t *in;
3234         m_t *out;
3235         int i, count;
3236
3237         in = (void *)(mod_base + l->fileofs);
3238         if (l->filelen % sizeof(*in))
3239                 Host_Error("Mod_Q2BSP_LoadVisibility: funny lump size in %s",loadmodel->name);
3240         count = l->filelen / sizeof(*in);
3241         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3242
3243         loadmodel-> = out;
3244         loadmodel->num = count;
3245
3246         for (i = 0;i < count;i++, in++, out++)
3247         {
3248         }
3249 */
3250 }
3251
3252 static void Mod_Q2BSP_LoadNodes(lump_t *l)
3253 {
3254 /*
3255         d_t *in;
3256         m_t *out;
3257         int i, count;
3258
3259         in = (void *)(mod_base + l->fileofs);
3260         if (l->filelen % sizeof(*in))
3261                 Host_Error("Mod_Q2BSP_LoadNodes: funny lump size in %s",loadmodel->name);
3262         count = l->filelen / sizeof(*in);
3263         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3264
3265         loadmodel-> = out;
3266         loadmodel->num = count;
3267
3268         for (i = 0;i < count;i++, in++, out++)
3269         {
3270         }
3271 */
3272 }
3273
3274 static void Mod_Q2BSP_LoadTexInfo(lump_t *l)
3275 {
3276 /*
3277         d_t *in;
3278         m_t *out;
3279         int i, count;
3280
3281         in = (void *)(mod_base + l->fileofs);
3282         if (l->filelen % sizeof(*in))
3283                 Host_Error("Mod_Q2BSP_LoadTexInfo: funny lump size in %s",loadmodel->name);
3284         count = l->filelen / sizeof(*in);
3285         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3286
3287         loadmodel-> = out;
3288         loadmodel->num = count;
3289
3290         for (i = 0;i < count;i++, in++, out++)
3291         {
3292         }
3293 */
3294 }
3295
3296 static void Mod_Q2BSP_LoadFaces(lump_t *l)
3297 {
3298 /*
3299         d_t *in;
3300         m_t *out;
3301         int i, count;
3302
3303         in = (void *)(mod_base + l->fileofs);
3304         if (l->filelen % sizeof(*in))
3305                 Host_Error("Mod_Q2BSP_LoadFaces: funny lump size in %s",loadmodel->name);
3306         count = l->filelen / sizeof(*in);
3307         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3308
3309         loadmodel-> = out;
3310         loadmodel->num = count;
3311
3312         for (i = 0;i < count;i++, in++, out++)
3313         {
3314         }
3315 */
3316 }
3317
3318 static void Mod_Q2BSP_LoadLighting(lump_t *l)
3319 {
3320 /*
3321         d_t *in;
3322         m_t *out;
3323         int i, count;
3324
3325         in = (void *)(mod_base + l->fileofs);
3326         if (l->filelen % sizeof(*in))
3327                 Host_Error("Mod_Q2BSP_LoadLighting: funny lump size in %s",loadmodel->name);
3328         count = l->filelen / sizeof(*in);
3329         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3330
3331         loadmodel-> = out;
3332         loadmodel->num = count;
3333
3334         for (i = 0;i < count;i++, in++, out++)
3335         {
3336         }
3337 */
3338 }
3339
3340 static void Mod_Q2BSP_LoadLeafs(lump_t *l)
3341 {
3342 /*
3343         d_t *in;
3344         m_t *out;
3345         int i, count;
3346
3347         in = (void *)(mod_base + l->fileofs);
3348         if (l->filelen % sizeof(*in))
3349                 Host_Error("Mod_Q2BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
3350         count = l->filelen / sizeof(*in);
3351         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3352
3353         loadmodel-> = out;
3354         loadmodel->num = count;
3355
3356         for (i = 0;i < count;i++, in++, out++)
3357         {
3358         }
3359 */
3360 }
3361
3362 static void Mod_Q2BSP_LoadLeafFaces(lump_t *l)
3363 {
3364 /*
3365         d_t *in;
3366         m_t *out;
3367         int i, count;
3368
3369         in = (void *)(mod_base + l->fileofs);
3370         if (l->filelen % sizeof(*in))
3371                 Host_Error("Mod_Q2BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
3372         count = l->filelen / sizeof(*in);
3373         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3374
3375         loadmodel-> = out;
3376         loadmodel->num = count;
3377
3378         for (i = 0;i < count;i++, in++, out++)
3379         {
3380         }
3381 */
3382 }
3383
3384 static void Mod_Q2BSP_LoadLeafBrushes(lump_t *l)
3385 {
3386 /*
3387         d_t *in;
3388         m_t *out;
3389         int i, count;
3390
3391         in = (void *)(mod_base + l->fileofs);
3392         if (l->filelen % sizeof(*in))
3393                 Host_Error("Mod_Q2BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
3394         count = l->filelen / sizeof(*in);
3395         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3396
3397         loadmodel-> = out;
3398         loadmodel->num = count;
3399
3400         for (i = 0;i < count;i++, in++, out++)
3401         {
3402         }
3403 */
3404 }
3405
3406 static void Mod_Q2BSP_LoadEdges(lump_t *l)
3407 {
3408 /*
3409         d_t *in;
3410         m_t *out;
3411         int i, count;
3412
3413         in = (void *)(mod_base + l->fileofs);
3414         if (l->filelen % sizeof(*in))
3415                 Host_Error("Mod_Q2BSP_LoadEdges: funny lump size in %s",loadmodel->name);
3416         count = l->filelen / sizeof(*in);
3417         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3418
3419         loadmodel-> = out;
3420         loadmodel->num = count;
3421
3422         for (i = 0;i < count;i++, in++, out++)
3423         {
3424         }
3425 */
3426 }
3427
3428 static void Mod_Q2BSP_LoadSurfEdges(lump_t *l)
3429 {
3430 /*
3431         d_t *in;
3432         m_t *out;
3433         int i, count;
3434
3435         in = (void *)(mod_base + l->fileofs);
3436         if (l->filelen % sizeof(*in))
3437                 Host_Error("Mod_Q2BSP_LoadSurfEdges: funny lump size in %s",loadmodel->name);
3438         count = l->filelen / sizeof(*in);
3439         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3440
3441         loadmodel-> = out;
3442         loadmodel->num = count;
3443
3444         for (i = 0;i < count;i++, in++, out++)
3445         {
3446         }
3447 */
3448 }
3449
3450 static void Mod_Q2BSP_LoadBrushes(lump_t *l)
3451 {
3452 /*
3453         d_t *in;
3454         m_t *out;
3455         int i, count;
3456
3457         in = (void *)(mod_base + l->fileofs);
3458         if (l->filelen % sizeof(*in))
3459                 Host_Error("Mod_Q2BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3460         count = l->filelen / sizeof(*in);
3461         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3462
3463         loadmodel-> = out;
3464         loadmodel->num = count;
3465
3466         for (i = 0;i < count;i++, in++, out++)
3467         {
3468         }
3469 */
3470 }
3471
3472 static void Mod_Q2BSP_LoadBrushSides(lump_t *l)
3473 {
3474 /*
3475         d_t *in;
3476         m_t *out;
3477         int i, count;
3478
3479         in = (void *)(mod_base + l->fileofs);
3480         if (l->filelen % sizeof(*in))
3481                 Host_Error("Mod_Q2BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3482         count = l->filelen / sizeof(*in);
3483         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3484
3485         loadmodel-> = out;
3486         loadmodel->num = count;
3487
3488         for (i = 0;i < count;i++, in++, out++)
3489         {
3490         }
3491 */
3492 }
3493
3494 static void Mod_Q2BSP_LoadAreas(lump_t *l)
3495 {
3496 /*
3497         d_t *in;
3498         m_t *out;
3499         int i, count;
3500
3501         in = (void *)(mod_base + l->fileofs);
3502         if (l->filelen % sizeof(*in))
3503                 Host_Error("Mod_Q2BSP_LoadAreas: funny lump size in %s",loadmodel->name);
3504         count = l->filelen / sizeof(*in);
3505         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3506
3507         loadmodel-> = out;
3508         loadmodel->num = count;
3509
3510         for (i = 0;i < count;i++, in++, out++)
3511         {
3512         }
3513 */
3514 }
3515
3516 static void Mod_Q2BSP_LoadAreaPortals(lump_t *l)
3517 {
3518 /*
3519         d_t *in;
3520         m_t *out;
3521         int i, count;
3522
3523         in = (void *)(mod_base + l->fileofs);
3524         if (l->filelen % sizeof(*in))
3525                 Host_Error("Mod_Q2BSP_LoadAreaPortals: funny lump size in %s",loadmodel->name);
3526         count = l->filelen / sizeof(*in);
3527         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3528
3529         loadmodel-> = out;
3530         loadmodel->num = count;
3531
3532         for (i = 0;i < count;i++, in++, out++)
3533         {
3534         }
3535 */
3536 }
3537
3538 static void Mod_Q2BSP_LoadModels(lump_t *l)
3539 {
3540 /*
3541         d_t *in;
3542         m_t *out;
3543         int i, count;
3544
3545         in = (void *)(mod_base + l->fileofs);
3546         if (l->filelen % sizeof(*in))
3547                 Host_Error("Mod_Q2BSP_LoadModels: funny lump size in %s",loadmodel->name);
3548         count = l->filelen / sizeof(*in);
3549         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3550
3551         loadmodel-> = out;
3552         loadmodel->num = count;
3553
3554         for (i = 0;i < count;i++, in++, out++)
3555         {
3556         }
3557 */
3558 }
3559
3560 void Mod_Q2BSP_Load(model_t *mod, void *buffer)
3561 {
3562         int i;
3563         q2dheader_t *header;
3564
3565         Host_Error("Mod_Q2BSP_Load: not yet implemented\n");
3566
3567         mod->type = mod_brushq2;
3568
3569         header = (q2dheader_t *)buffer;
3570
3571         i = LittleLong(header->version);
3572         if (i != Q2BSPVERSION)
3573                 Host_Error("Mod_Q2BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q2BSPVERSION);
3574         mod->brushq1.ishlbsp = false;
3575         if (loadmodel->isworldmodel)
3576         {
3577                 Cvar_SetValue("halflifebsp", mod->brushq1.ishlbsp);
3578                 // until we get a texture for it...
3579                 R_ResetQuakeSky();
3580         }
3581
3582         mod_base = (qbyte *)header;
3583
3584         // swap all the lumps
3585         for (i = 0;i < (int) sizeof(*header) / 4;i++)
3586                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
3587
3588         // store which lightmap format to use
3589         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3590
3591         Mod_Q2BSP_LoadEntities(&header->lumps[Q2LUMP_ENTITIES]);
3592         Mod_Q2BSP_LoadPlanes(&header->lumps[Q2LUMP_PLANES]);
3593         Mod_Q2BSP_LoadVertices(&header->lumps[Q2LUMP_VERTEXES]);
3594         Mod_Q2BSP_LoadVisibility(&header->lumps[Q2LUMP_VISIBILITY]);
3595         Mod_Q2BSP_LoadNodes(&header->lumps[Q2LUMP_NODES]);
3596         Mod_Q2BSP_LoadTexInfo(&header->lumps[Q2LUMP_TEXINFO]);
3597         Mod_Q2BSP_LoadFaces(&header->lumps[Q2LUMP_FACES]);
3598         Mod_Q2BSP_LoadLighting(&header->lumps[Q2LUMP_LIGHTING]);
3599         Mod_Q2BSP_LoadLeafs(&header->lumps[Q2LUMP_LEAFS]);
3600         Mod_Q2BSP_LoadLeafFaces(&header->lumps[Q2LUMP_LEAFFACES]);
3601         Mod_Q2BSP_LoadLeafBrushes(&header->lumps[Q2LUMP_LEAFBRUSHES]);
3602         Mod_Q2BSP_LoadEdges(&header->lumps[Q2LUMP_EDGES]);
3603         Mod_Q2BSP_LoadSurfEdges(&header->lumps[Q2LUMP_SURFEDGES]);
3604         Mod_Q2BSP_LoadBrushes(&header->lumps[Q2LUMP_BRUSHES]);
3605         Mod_Q2BSP_LoadBrushSides(&header->lumps[Q2LUMP_BRUSHSIDES]);
3606         Mod_Q2BSP_LoadAreas(&header->lumps[Q2LUMP_AREAS]);
3607         Mod_Q2BSP_LoadAreaPortals(&header->lumps[Q2LUMP_AREAPORTALS]);
3608         // LordHavoc: must go last because this makes the submodels
3609         Mod_Q2BSP_LoadModels(&header->lumps[Q2LUMP_MODELS]);
3610 }
3611
3612
3613 static void Mod_Q3BSP_LoadEntities(lump_t *l)
3614 {
3615         const char *data;
3616         char key[128], value[4096];
3617         float v[3];
3618         loadmodel->brushq3.num_lightgrid_cellsize[0] = 64;
3619         loadmodel->brushq3.num_lightgrid_cellsize[1] = 64;
3620         loadmodel->brushq3.num_lightgrid_cellsize[2] = 128;
3621         if (!l->filelen)
3622                 return;
3623         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
3624         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
3625         data = loadmodel->brush.entities;
3626         // some Q3 maps override the lightgrid_cellsize with a worldspawn key
3627         if (data && COM_ParseToken(&data, false) && com_token[0] == '{')
3628         {
3629                 while (1)
3630                 {
3631                         if (!COM_ParseToken(&data, false))
3632                                 break; // error
3633                         if (com_token[0] == '}')
3634                                 break; // end of worldspawn
3635                         if (com_token[0] == '_')
3636                                 strcpy(key, com_token + 1);
3637                         else
3638                                 strcpy(key, com_token);
3639                         while (key[strlen(key)-1] == ' ') // remove trailing spaces
3640                                 key[strlen(key)-1] = 0;
3641                         if (!COM_ParseToken(&data, false))
3642                                 break; // error
3643                         strcpy(value, com_token);
3644                         if (!strcmp("gridsize", key))
3645                         {
3646                                 if (sscanf(value, "%f %f %f", &v[0], &v[1], &v[2]) == 3 && v[0] != 0 && v[1] != 0 && v[2] != 0)
3647                                         VectorCopy(v, loadmodel->brushq3.num_lightgrid_cellsize);
3648                         }
3649                 }
3650         }
3651 }
3652
3653 static void Mod_Q3BSP_LoadTextures(lump_t *l)
3654 {
3655         q3dtexture_t *in;
3656         q3mtexture_t *out;
3657         int i, count;
3658
3659         in = (void *)(mod_base + l->fileofs);
3660         if (l->filelen % sizeof(*in))
3661                 Host_Error("Mod_Q3BSP_LoadTextures: funny lump size in %s",loadmodel->name);
3662         count = l->filelen / sizeof(*in);
3663         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3664
3665         loadmodel->brushq3.data_textures = out;
3666         loadmodel->brushq3.num_textures = count;
3667
3668         for (i = 0;i < count;i++, in++, out++)
3669         {
3670                 strncpy(out->name, in->name, sizeof(out->name) - 1);
3671                 out->surfaceflags = LittleLong(in->surfaceflags);
3672                 out->contents = LittleLong(in->contents);
3673
3674                 out->number = i;
3675                 Mod_LoadSkinFrame(&out->skin, out->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, false, true, true);
3676         }
3677 }
3678
3679 static void Mod_Q3BSP_LoadPlanes(lump_t *l)
3680 {
3681         q3dplane_t *in;
3682         mplane_t *out;
3683         int i, count;
3684
3685         in = (void *)(mod_base + l->fileofs);
3686         if (l->filelen % sizeof(*in))
3687                 Host_Error("Mod_Q3BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3688         count = l->filelen / sizeof(*in);
3689         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3690
3691         loadmodel->brushq3.data_planes = out;
3692         loadmodel->brushq3.num_planes = count;
3693
3694         for (i = 0;i < count;i++, in++, out++)
3695         {
3696                 out->normal[0] = LittleLong(in->normal[0]);
3697                 out->normal[1] = LittleLong(in->normal[1]);
3698                 out->normal[2] = LittleLong(in->normal[2]);
3699                 out->dist = LittleLong(in->dist);
3700                 PlaneClassify(out);
3701         }
3702 }
3703
3704 static void Mod_Q3BSP_LoadBrushSides(lump_t *l)
3705 {
3706         q3dbrushside_t *in;
3707         q3mbrushside_t *out;
3708         int i, n, count;
3709
3710         in = (void *)(mod_base + l->fileofs);
3711         if (l->filelen % sizeof(*in))
3712                 Host_Error("Mod_Q3BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3713         count = l->filelen / sizeof(*in);
3714         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3715
3716         loadmodel->brushq3.data_brushsides = out;
3717         loadmodel->brushq3.num_brushsides = count;
3718
3719         for (i = 0;i < count;i++, in++, out++)
3720         {
3721                 n = LittleLong(in->planeindex);
3722                 if (n < 0 || n >= loadmodel->brushq3.num_planes)
3723                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid planeindex %i (%i planes)\n", n, loadmodel->brushq3.num_planes);
3724                 out->plane = loadmodel->brushq3.data_planes + n;
3725                 n = LittleLong(in->textureindex);
3726                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
3727                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid textureindex %i (%i textures)\n", n, loadmodel->brushq3.num_textures);
3728                 out->texture = loadmodel->brushq3.data_textures + n;
3729         }
3730 }
3731
3732 static void Mod_Q3BSP_LoadBrushes(lump_t *l)
3733 {
3734         q3dbrush_t *in;
3735         q3mbrush_t *out;
3736         int i, j, k, m, n, c, count, numpoints, numplanes;
3737         winding_t *w;
3738         colpointf_t pointsbuf[256*3];
3739         colplanef_t planesbuf[256], colplanef;
3740
3741         in = (void *)(mod_base + l->fileofs);
3742         if (l->filelen % sizeof(*in))
3743                 Host_Error("Mod_Q3BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3744         count = l->filelen / sizeof(*in);
3745         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3746
3747         loadmodel->brushq3.data_brushes = out;
3748         loadmodel->brushq3.num_brushes = count;
3749
3750         for (i = 0;i < count;i++, in++, out++)
3751         {
3752                 n = LittleLong(in->firstbrushside);
3753                 c = LittleLong(in->numbrushsides);
3754                 if (n < 0 || n + c > loadmodel->brushq3.num_brushsides)
3755                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid brushside range %i : %i (%i brushsides)\n", n, n + c, loadmodel->brushq3.num_brushsides);
3756                 out->firstbrushside = loadmodel->brushq3.data_brushsides + n;
3757                 out->numbrushsides = c;
3758                 n = LittleLong(in->textureindex);
3759                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
3760                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid textureindex %i (%i textures)\n", n, loadmodel->brushq3.num_textures);
3761                 out->texture = loadmodel->brushq3.data_textures + n;
3762
3763                 // construct a collision brush, which needs points and planes...
3764                 // each point and plane should be unique, and they don't refer to
3765                 // eachother in any way, so keeping them unique is fairly easy
3766                 numpoints = 0;
3767                 numplanes = 0;
3768                 for (j = 0;j < out->numbrushsides;j++)
3769                 {
3770                         // create a huge polygon for the plane
3771                         w = BaseWindingForPlane(out->firstbrushside[j].plane);
3772                         // clip it by all other planes
3773                         for (k = 0;k < out->numbrushsides && w;k++)
3774                                 if (k != j)
3775                                         w = ClipWinding(w, out->firstbrushside[k].plane, true);
3776                         // if nothing is left, skip it
3777                         // FIXME: should keep count of how many were skipped and report
3778                         // it, just for sake of statistics
3779                         if (!w)
3780                                 continue;
3781                         // add the points uniquely (no duplicates)
3782                         for (k = 0;k < w->numpoints;k++)
3783                         {
3784                                 for (m = 0;m < numpoints;m++)
3785                                         if (VectorDistance2(w->points[k * 3], pointsbuf[m * 3].v) < DIST_EPSILON)
3786                                                 break;
3787                                 if (m == numpoints)
3788                                 {
3789                                         // check if there are too many and skip the brush
3790                                         if (numpoints >= 256)
3791                                         {
3792                                                 Con_Printf("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many points for buffer\n");
3793                                                 FreeWinding(w);
3794                                                 goto failedtomakecolbrush;
3795                                         }
3796                                         // add the new one
3797                                         VectorCopy(w->points[k * 3], pointsbuf[numpoints * 3].v);
3798                                         numpoints++;
3799                                 }
3800                         }
3801                         // add the plane uniquely (no duplicates)
3802                         memset(&colplanef, 0, sizeof(colplanef));
3803                         VectorCopy(out->firstbrushside[k].plane->normal, colplanef.normal);
3804                         colplanef.dist = out->firstbrushside[k].plane->dist;
3805                         for (k = 0;k < numplanes;k++)
3806                                 if (VectorCompare(planesbuf[k].normal, colplanef.normal) && planesbuf[k].dist == colplanef.dist)
3807                                         break;
3808                         if (k == numplanes)
3809                         {
3810                                 // check if there are too many and skip the brush
3811                                 if (numplanes >= 256)
3812                                 {
3813                                         Con_Printf("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many planes for buffer\n");
3814                                         FreeWinding(w);
3815                                         goto failedtomakecolbrush;
3816                                 }
3817                                 // add the new one
3818                                 planesbuf[numplanes++] = colplanef;
3819                         }
3820                         FreeWinding(w);
3821                 }
3822                 // if anything is left, create the collision brush
3823                 if (numplanes && numpoints)
3824                 {
3825                         out->colbrushf = Collision_AllocBrushFloat(loadmodel->mempool, numpoints, numplanes);
3826                         memcpy(out->colbrushf->points, pointsbuf, numpoints * sizeof(float[3]));
3827                         memcpy(out->colbrushf->planes, planesbuf, numplanes * sizeof(mplane_t));
3828                 }
3829                 // return from errors to here
3830                 failedtomakecolbrush:;
3831         }
3832 }
3833
3834 static void Mod_Q3BSP_LoadEffects(lump_t *l)
3835 {
3836         q3deffect_t *in;
3837         q3meffect_t *out;
3838         int i, n, count;
3839
3840         in = (void *)(mod_base + l->fileofs);
3841         if (l->filelen % sizeof(*in))
3842                 Host_Error("Mod_Q3BSP_LoadEffects: funny lump size in %s",loadmodel->name);
3843         count = l->filelen / sizeof(*in);
3844         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3845
3846         loadmodel->brushq3.data_effects = out;
3847         loadmodel->brushq3.num_effects = count;
3848
3849         for (i = 0;i < count;i++, in++, out++)
3850         {
3851                 strncpy(out->shadername, in->shadername, sizeof(out->shadername) - 1);
3852                 n = LittleLong(in->brushindex);
3853                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
3854                         Host_Error("Mod_Q3BSP_LoadEffects: invalid brushindex %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
3855                 out->brush = loadmodel->brushq3.data_brushes + n;
3856                 out->unknown = LittleLong(in->unknown);
3857         }
3858 }
3859
3860 static void Mod_Q3BSP_LoadVertices(lump_t *l)
3861 {
3862         q3dvertex_t *in;
3863         int i, count;
3864
3865         in = (void *)(mod_base + l->fileofs);
3866         if (l->filelen % sizeof(*in))
3867                 Host_Error("Mod_Q3BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3868         loadmodel->brushq3.num_vertices = count = l->filelen / sizeof(*in);
3869         loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3]));
3870         loadmodel->brushq3.data_texturetexcoord2f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[2]));
3871         loadmodel->brushq3.data_lightmaptexcoord2f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[2]));
3872         loadmodel->brushq3.data_svector3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3]));
3873         loadmodel->brushq3.data_tvector3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3]));
3874         loadmodel->brushq3.data_normal3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3]));
3875         loadmodel->brushq3.data_color4f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[4]));
3876
3877         for (i = 0;i < count;i++, in++)
3878         {
3879                 loadmodel->brushq3.data_vertex3f[i * 3 + 0] = LittleFloat(in->origin3f[0]);
3880                 loadmodel->brushq3.data_vertex3f[i * 3 + 1] = LittleFloat(in->origin3f[1]);
3881                 loadmodel->brushq3.data_vertex3f[i * 3 + 2] = LittleFloat(in->origin3f[2]);
3882                 loadmodel->brushq3.data_texturetexcoord2f[i * 2 + 0] = LittleFloat(in->texcoord2f[0]);
3883                 loadmodel->brushq3.data_texturetexcoord2f[i * 2 + 1] = LittleFloat(in->texcoord2f[1]);
3884                 loadmodel->brushq3.data_lightmaptexcoord2f[i * 2 + 0] = LittleFloat(in->lightmap2f[0]);
3885                 loadmodel->brushq3.data_lightmaptexcoord2f[i * 2 + 1] = LittleFloat(in->lightmap2f[1]);
3886                 // svector/tvector are calculated later in face loading
3887                 loadmodel->brushq3.data_svector3f[i * 3 + 0] = 0;
3888                 loadmodel->brushq3.data_svector3f[i * 3 + 1] = 0;
3889                 loadmodel->brushq3.data_svector3f[i * 3 + 2] = 0;
3890                 loadmodel->brushq3.data_tvector3f[i * 3 + 0] = 0;
3891                 loadmodel->brushq3.data_tvector3f[i * 3 + 1] = 0;
3892                 loadmodel->brushq3.data_tvector3f[i * 3 + 2] = 0;
3893                 loadmodel->brushq3.data_normal3f[i * 3 + 0] = LittleFloat(in->normal3f[0]);
3894                 loadmodel->brushq3.data_normal3f[i * 3 + 1] = LittleFloat(in->normal3f[1]);
3895                 loadmodel->brushq3.data_normal3f[i * 3 + 2] = LittleFloat(in->normal3f[2]);
3896                 loadmodel->brushq3.data_color4f[i * 4 + 0] = in->color4ub[0] * (1.0f / 255.0f);
3897                 loadmodel->brushq3.data_color4f[i * 4 + 1] = in->color4ub[1] * (1.0f / 255.0f);
3898                 loadmodel->brushq3.data_color4f[i * 4 + 2] = in->color4ub[2] * (1.0f / 255.0f);
3899                 loadmodel->brushq3.data_color4f[i * 4 + 3] = in->color4ub[3] * (1.0f / 255.0f);
3900         }
3901 }
3902
3903 static void Mod_Q3BSP_LoadTriangles(lump_t *l)
3904 {
3905         int *in;
3906         int *out;
3907         int i, count;
3908
3909         in = (void *)(mod_base + l->fileofs);
3910         if (l->filelen % sizeof(int[3]))
3911                 Host_Error("Mod_Q3BSP_LoadTriangles: funny lump size in %s",loadmodel->name);
3912         count = l->filelen / sizeof(*in);
3913         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3914
3915         loadmodel->brushq3.num_triangles = count / 3;
3916         loadmodel->brushq3.data_element3i = out;
3917         loadmodel->brushq3.data_neighbor3i = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3918
3919         for (i = 0;i < count;i++, in++, out++)
3920         {
3921                 *out = LittleLong(*in);
3922                 if (*out < 0 || *out >= loadmodel->brushq3.num_vertices)
3923                         Host_Error("Mod_Q3BSP_LoadTriangles: invalid vertexindex %i (%i vertices)\n", *out, loadmodel->brushq3.num_vertices);
3924         }
3925 }
3926
3927 static void Mod_Q3BSP_LoadLightmaps(lump_t *l)
3928 {
3929         q3dlightmap_t *in;
3930         rtexture_t **out;
3931         int i, count;
3932
3933         in = (void *)(mod_base + l->fileofs);
3934         if (l->filelen % sizeof(*in))
3935                 Host_Error("Mod_Q3BSP_LoadLightmaps: funny lump size in %s",loadmodel->name);
3936         count = l->filelen / sizeof(*in);
3937         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3938
3939         loadmodel->brushq3.data_lightmaps = out;
3940         loadmodel->brushq3.num_lightmaps = count;
3941
3942         for (i = 0;i < count;i++, in++, out++)
3943                 *out = R_LoadTexture2D(loadmodel->texturepool, va("lightmap%04i", i), 128, 128, in->rgb, TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
3944 }
3945
3946 static void Mod_Q3BSP_LoadFaces(lump_t *l)
3947 {
3948         q3dface_t *in;
3949         q3mface_t *out;
3950         int i, j, n, count, invalidelements, patchsize[2];
3951
3952         in = (void *)(mod_base + l->fileofs);
3953         if (l->filelen % sizeof(*in))
3954                 Host_Error("Mod_Q3BSP_LoadFaces: funny lump size in %s",loadmodel->name);
3955         count = l->filelen / sizeof(*in);
3956         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3957
3958         loadmodel->brushq3.data_faces = out;
3959         loadmodel->brushq3.num_faces = count;
3960
3961         for (i = 0;i < count;i++, in++, out++)
3962         {
3963                 // check face type first
3964                 out->type = LittleLong(in->type);
3965                 if (out->type != Q3FACETYPE_POLYGON
3966                  && out->type != Q3FACETYPE_PATCH
3967                  && out->type != Q3FACETYPE_MESH
3968                  && out->type != Q3FACETYPE_FLARE)
3969                 {
3970                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i: unknown face type %i\n", i, out->type);
3971                         out->type = 0; // error
3972                         continue;
3973                 }
3974
3975                 n = LittleLong(in->textureindex);
3976                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
3977                 {
3978                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i: invalid textureindex %i (%i textures)\n", i, n, loadmodel->brushq3.num_textures);
3979                         out->type = 0; // error
3980                         continue;
3981                         n = 0;
3982                 }
3983                 out->texture = loadmodel->brushq3.data_textures + n;
3984                 n = LittleLong(in->effectindex);
3985                 if (n < -1 || n >= loadmodel->brushq3.num_effects)
3986                 {
3987                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid effectindex %i (%i effects)\n", i, out->texture->name, n, loadmodel->brushq3.num_effects);
3988                         n = -1;
3989                 }
3990                 if (n == -1)
3991                         out->effect = NULL;
3992                 else
3993                         out->effect = loadmodel->brushq3.data_effects + n;
3994                 n = LittleLong(in->lightmapindex);
3995                 if (n < -1 || n >= loadmodel->brushq3.num_lightmaps)
3996                 {
3997                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid lightmapindex %i (%i lightmaps)\n", i, out->texture->name, n, loadmodel->brushq3.num_lightmaps);
3998                         n = -1;
3999                 }
4000                 if (n == -1)
4001                         out->lightmaptexture = NULL;
4002                 else
4003                         out->lightmaptexture = loadmodel->brushq3.data_lightmaps[n];
4004
4005                 out->firstvertex = LittleLong(in->firstvertex);
4006                 out->numvertices = LittleLong(in->numvertices);
4007                 out->firstelement = LittleLong(in->firstelement);
4008                 out->numelements = LittleLong(in->numelements);
4009                 out->numtriangles = out->numelements / 3;
4010                 if (out->firstvertex < 0 || out->firstvertex + out->numvertices > loadmodel->brushq3.num_vertices)
4011                 {
4012                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid vertex range %i : %i (%i vertices)\n", i, out->texture->name, out->firstvertex, out->firstvertex + out->numvertices, loadmodel->brushq3.num_vertices);
4013                         out->type = 0; // error
4014                         continue;
4015                 }
4016                 if (out->firstelement < 0 || out->firstelement + out->numelements > loadmodel->brushq3.num_triangles * 3)
4017                 {
4018                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid element range %i : %i (%i elements)\n", i, out->texture->name, out->firstelement, out->firstelement + out->numelements, loadmodel->brushq3.num_triangles * 3);
4019                         out->type = 0; // error
4020                         continue;
4021                 }
4022                 if (out->numtriangles * 3 != out->numelements)
4023                 {
4024                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): numelements %i is not a multiple of 3\n", i, out->texture->name, out->numelements);
4025                         out->type = 0; // error
4026                         continue;
4027                 }
4028                 switch(out->type)
4029                 {
4030                 case Q3FACETYPE_POLYGON:
4031                 case Q3FACETYPE_MESH:
4032                         out->data_vertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
4033                         out->data_texturetexcoord2f = loadmodel->brushq3.data_texturetexcoord2f + out->firstvertex * 2;
4034                         out->data_lightmaptexcoord2f = loadmodel->brushq3.data_lightmaptexcoord2f + out->firstvertex * 2;
4035                         out->data_svector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
4036                         out->data_tvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
4037                         out->data_normal3f = loadmodel->brushq3.data_normal3f + out->firstvertex * 3;
4038                         out->data_color4f = loadmodel->brushq3.data_color4f + out->firstvertex * 4;
4039                         out->data_element3i = loadmodel->brushq3.data_element3i + out->firstelement;
4040                         out->data_neighbor3i = loadmodel->brushq3.data_neighbor3i + out->firstelement;
4041                         break;
4042                 case Q3FACETYPE_PATCH:
4043                         patchsize[0] = LittleLong(in->specific.patch.patchsize[0]);
4044                         patchsize[1] = LittleLong(in->specific.patch.patchsize[1]);
4045                         if (patchsize[0] < 1 || patchsize[1] < 1)
4046                         {
4047                                 Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid patchsize %ix%i\n", i, out->texture->name, patchsize[0], patchsize[1]);
4048                                 out->type = 0; // error
4049                                 continue;
4050                         }
4051                         // FIXME: convert patch to triangles here!
4052                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): Q3FACETYPE_PATCH not supported (yet)\n", i, out->texture->name);
4053                         out->type = 0;
4054                         continue;
4055                         break;
4056                 case Q3FACETYPE_FLARE:
4057                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): Q3FACETYPE_FLARE not supported (yet)\n", i, out->texture->name);
4058                         out->type = 0;
4059                         continue;
4060                         break;
4061                 }
4062                 for (j = 0, invalidelements = 0;j < out->numelements;j++)
4063                         if (out->data_element3i[j] < 0 || out->data_element3i[j] >= out->numvertices)
4064                                 invalidelements++;
4065                 if (invalidelements)
4066                 {
4067                         Con_Printf("Mod_Q3BSP_LoadFaces: Warning: face #%i has %i invalid elements, type = %i, texture->name = \"%s\", texture->surfaceflags = %i, texture->contents = %i, firstvertex = %i, numvertices = %i, firstelement = %i, numelements = %i, elements list:\n", i, invalidelements, out->type, out->texture->name, out->texture->surfaceflags, out->texture->contents, out->firstvertex, out->numvertices, out->firstelement, out->numelements);
4068                         for (j = 0;j < out->numelements;j++)
4069                         {
4070                                 Con_Printf(" %i", out->data_element3i[j]);
4071                                 if (out->data_element3i[j] < 0 || out->data_element3i[j] >= out->numvertices)
4072                                         out->data_element3i[j] = 0;
4073                         }
4074                         Con_Printf("\n");
4075                 }
4076         }
4077 }
4078
4079 static void Mod_Q3BSP_LoadModels(lump_t *l)
4080 {
4081         q3dmodel_t *in;
4082         q3mmodel_t *out;
4083         int i, j, n, c, count;
4084
4085         in = (void *)(mod_base + l->fileofs);
4086         if (l->filelen % sizeof(*in))
4087                 Host_Error("Mod_Q3BSP_LoadModels: funny lump size in %s",loadmodel->name);
4088         count = l->filelen / sizeof(*in);
4089         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4090
4091         loadmodel->brushq3.data_models = out;
4092         loadmodel->brushq3.num_models = count;
4093
4094         for (i = 0;i < count;i++, in++, out++)
4095         {
4096                 for (j = 0;j < 3;j++)
4097                 {
4098                         out->mins[j] = LittleFloat(in->mins[j]);
4099                         out->maxs[j] = LittleFloat(in->maxs[j]);
4100                 }
4101                 n = LittleLong(in->firstface);
4102                 c = LittleLong(in->numfaces);
4103                 if (n < 0 || n + c > loadmodel->brushq3.num_faces)
4104                         Host_Error("Mod_Q3BSP_LoadModels: invalid face range %i : %i (%i faces)\n", n, n + c, loadmodel->brushq3.num_faces);
4105                 out->firstface = loadmodel->brushq3.data_faces + n;
4106                 out->numfaces = c;
4107                 n = LittleLong(in->firstbrush);
4108                 c = LittleLong(in->numbrushes);
4109                 if (n < 0 || n + c > loadmodel->brushq3.num_brushes)
4110                         Host_Error("Mod_Q3BSP_LoadModels: invalid brush range %i : %i (%i brushes)\n", n, n + c, loadmodel->brushq3.num_brushes);
4111                 out->firstbrush = loadmodel->brushq3.data_brushes + n;
4112                 out->numbrushes = c;
4113         }
4114 }
4115
4116 static void Mod_Q3BSP_LoadLeafBrushes(lump_t *l)
4117 {
4118         int *in;
4119         q3mbrush_t **out;
4120         int i, n, count;
4121
4122         in = (void *)(mod_base + l->fileofs);
4123         if (l->filelen % sizeof(*in))
4124                 Host_Error("Mod_Q3BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
4125         count = l->filelen / sizeof(*in);
4126         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4127
4128         loadmodel->brushq3.data_leafbrushes = out;
4129         loadmodel->brushq3.num_leafbrushes = count;
4130
4131         for (i = 0;i < count;i++, in++, out++)
4132         {
4133                 n = LittleLong(*in);
4134                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
4135                         Host_Error("Mod_Q3BSP_LoadLeafBrushes: invalid brush index %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
4136                 *out = loadmodel->brushq3.data_brushes + n;
4137         }
4138 }
4139
4140 static void Mod_Q3BSP_LoadLeafFaces(lump_t *l)
4141 {
4142         int *in;
4143         q3mface_t **out;
4144         int i, n, count;
4145
4146         in = (void *)(mod_base + l->fileofs);
4147         if (l->filelen % sizeof(*in))
4148                 Host_Error("Mod_Q3BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
4149         count = l->filelen / sizeof(*in);
4150         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4151
4152         loadmodel->brushq3.data_leaffaces = out;
4153         loadmodel->brushq3.num_leaffaces = count;
4154
4155         for (i = 0;i < count;i++, in++, out++)
4156         {
4157                 n = LittleLong(*in);
4158                 if (n < 0 || n >= loadmodel->brushq3.num_faces)
4159                         Host_Error("Mod_Q3BSP_LoadLeafFaces: invalid face index %i (%i faces)\n", n, loadmodel->brushq3.num_faces);
4160                 *out = loadmodel->brushq3.data_faces + n;
4161         }
4162 }
4163
4164 static void Mod_Q3BSP_LoadLeafs(lump_t *l)
4165 {
4166         q3dleaf_t *in;
4167         q3mleaf_t *out;
4168         int i, j, n, c, count;
4169
4170         in = (void *)(mod_base + l->fileofs);
4171         if (l->filelen % sizeof(*in))
4172                 Host_Error("Mod_Q3BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
4173         count = l->filelen / sizeof(*in);
4174         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4175
4176         loadmodel->brushq3.data_leafs = out;
4177         loadmodel->brushq3.num_leafs = count;
4178
4179         for (i = 0;i < count;i++, in++, out++)
4180         {
4181                 out->isnode = false;
4182                 out->parent = NULL;
4183                 out->clusterindex = LittleLong(in->clusterindex);
4184                 out->areaindex = LittleLong(in->areaindex);
4185                 for (j = 0;j < 3;j++)
4186                 {
4187                         // yes the mins/maxs are ints
4188                         out->mins[j] = LittleLong(in->mins[j]);
4189                         out->maxs[j] = LittleLong(in->maxs[j]);
4190                 }
4191                 n = LittleLong(in->firstleafface);
4192                 c = LittleLong(in->numleaffaces);
4193                 if (n < 0 || n + c > loadmodel->brushq3.num_leaffaces)
4194                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafface range %i : %i (%i leaffaces)\n", n, n + c, loadmodel->brushq3.num_leaffaces);
4195                 out->firstleafface = loadmodel->brushq3.data_leaffaces + n;
4196                 out->numleaffaces = c;
4197                 n = LittleLong(in->firstleafbrush);
4198                 c = LittleLong(in->numleafbrushes);
4199                 if (n < 0 || n + c > loadmodel->brushq3.num_leafbrushes)
4200                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafbrush range %i : %i (%i leafbrushes)\n", n, n + c, loadmodel->brushq3.num_leafbrushes);
4201                 out->firstleafbrush = loadmodel->brushq3.data_leafbrushes + n;
4202                 out->numleafbrushes = c;
4203         }
4204 }
4205
4206 static void Mod_Q3BSP_LoadNodes_RecursiveSetParent(q3mnode_t *node, q3mnode_t *parent)
4207 {
4208         if (node->parent)
4209                 Host_Error("Mod_Q3BSP_LoadNodes_RecursiveSetParent: runaway recursion\n");
4210         node->parent = parent;
4211         if (node->isnode)
4212         {
4213                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
4214                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
4215         }
4216 }
4217
4218 static void Mod_Q3BSP_LoadNodes(lump_t *l)
4219 {
4220         q3dnode_t *in;
4221         q3mnode_t *out;
4222         int i, j, n, count;
4223
4224         in = (void *)(mod_base + l->fileofs);
4225         if (l->filelen % sizeof(*in))
4226                 Host_Error("Mod_Q3BSP_LoadNodes: funny lump size in %s",loadmodel->name);
4227         count = l->filelen / sizeof(*in);
4228         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4229
4230         loadmodel->brushq3.data_nodes = out;
4231         loadmodel->brushq3.num_nodes = count;
4232
4233         for (i = 0;i < count;i++, in++, out++)
4234         {
4235                 out->isnode = true;
4236                 out->parent = NULL;
4237                 n = LittleLong(in->planeindex);
4238                 if (n < 0 || n >= loadmodel->brushq3.num_planes)
4239                         Host_Error("Mod_Q3BSP_LoadNodes: invalid planeindex %i (%i planes)\n", n, loadmodel->brushq3.num_planes);
4240                 out->plane = loadmodel->brushq3.data_planes + n;
4241                 for (j = 0;j < 2;j++)
4242                 {
4243                         n = LittleLong(in->childrenindex[j]);
4244                         if (n >= 0)
4245                         {
4246                                 if (n >= loadmodel->brushq3.num_nodes)
4247                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child node index %i (%i nodes)\n", n, loadmodel->brushq3.num_nodes);
4248                                 out->children[j] = loadmodel->brushq3.data_nodes + n;
4249                         }
4250                         else
4251                         {
4252                                 n = 1 - n;
4253                                 if (n >= loadmodel->brushq3.num_leafs)
4254                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child leaf index %i (%i leafs)\n", n, loadmodel->brushq3.num_leafs);
4255                                 out->children[j] = (q3mnode_t *)(loadmodel->brushq3.data_leafs + n);
4256                         }
4257                 }
4258                 // we don't load the mins/maxs
4259         }
4260
4261         // set the parent pointers
4262         Mod_Q3BSP_LoadNodes_RecursiveSetParent(loadmodel->brushq3.data_nodes, NULL);
4263 }
4264
4265 static void Mod_Q3BSP_LoadLightGrid(lump_t *l)
4266 {
4267         q3dlightgrid_t *in;
4268         q3dlightgrid_t *out;
4269         int count;
4270
4271         in = (void *)(mod_base + l->fileofs);
4272         if (l->filelen % sizeof(*in))
4273                 Host_Error("Mod_Q3BSP_LoadLightGrid: funny lump size in %s",loadmodel->name);
4274         loadmodel->brushq3.num_lightgrid_scale[0] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[0];
4275         loadmodel->brushq3.num_lightgrid_scale[1] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[1];
4276         loadmodel->brushq3.num_lightgrid_scale[2] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[2];
4277         loadmodel->brushq3.num_lightgrid_imins[0] = ceil(loadmodel->brushq3.data_models->mins[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4278         loadmodel->brushq3.num_lightgrid_imins[1] = ceil(loadmodel->brushq3.data_models->mins[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4279         loadmodel->brushq3.num_lightgrid_imins[2] = ceil(loadmodel->brushq3.data_models->mins[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4280         loadmodel->brushq3.num_lightgrid_imaxs[0] = floor(loadmodel->brushq3.data_models->maxs[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4281         loadmodel->brushq3.num_lightgrid_imaxs[1] = floor(loadmodel->brushq3.data_models->maxs[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4282         loadmodel->brushq3.num_lightgrid_imaxs[2] = floor(loadmodel->brushq3.data_models->maxs[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4283         loadmodel->brushq3.num_lightgrid_isize[0] = loadmodel->brushq3.num_lightgrid_imaxs[0] - loadmodel->brushq3.num_lightgrid_imins[0] + 1;
4284         loadmodel->brushq3.num_lightgrid_isize[1] = loadmodel->brushq3.num_lightgrid_imaxs[1] - loadmodel->brushq3.num_lightgrid_imins[1] + 1;
4285         loadmodel->brushq3.num_lightgrid_isize[2] = loadmodel->brushq3.num_lightgrid_imaxs[2] - loadmodel->brushq3.num_lightgrid_imins[2] + 1;
4286         count = loadmodel->brushq3.num_lightgrid_isize[0] * loadmodel->brushq3.num_lightgrid_isize[1] * loadmodel->brushq3.num_lightgrid_isize[2];
4287         if (l->filelen < count * (int)sizeof(*in))
4288                 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]);
4289         if (l->filelen != count * (int)sizeof(*in))
4290                 Con_Printf("Mod_Q3BSP_LoadLightGrid: Warning: calculated lightgrid size %i bytes does not match lump size %i\n", count * sizeof(*in), l->filelen);
4291
4292         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4293         loadmodel->brushq3.data_lightgrid = out;
4294         loadmodel->brushq3.num_lightgrid = count;
4295
4296         // no swapping or validation necessary
4297         memcpy(out, in, count * (int)sizeof(*out));
4298
4299         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]);
4300         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]);
4301 }
4302
4303 static void Mod_Q3BSP_LoadPVS(lump_t *l)
4304 {
4305         q3dpvs_t *in;
4306         int totalchains;
4307
4308         in = (void *)(mod_base + l->fileofs);
4309         if (l->filelen < 9)
4310                 Host_Error("Mod_Q3BSP_LoadPVS: funny lump size in %s",loadmodel->name);
4311
4312         loadmodel->brushq3.num_pvsclusters = LittleLong(in->numclusters);
4313         loadmodel->brushq3.num_pvschainlength = LittleLong(in->chainlength);
4314         if (loadmodel->brushq3.num_pvschainlength < ((loadmodel->brushq3.num_pvsclusters + 7) / 8))
4315                 Host_Error("Mod_Q3BSP_LoadPVS: (chainlength = %i) < ((numclusters = %i) + 7) / 8\n", loadmodel->brushq3.num_pvschainlength, loadmodel->brushq3.num_pvsclusters);
4316         totalchains = loadmodel->brushq3.num_pvschainlength * loadmodel->brushq3.num_pvsclusters;
4317         if (l->filelen < totalchains + (int)sizeof(*in))
4318                 Host_Error("Mod_Q3BSP_LoadPVS: lump too small ((numclusters = %i) * (chainlength = %i) + sizeof(q3dpvs_t) == %i bytes, lump is %i bytes)\n", loadmodel->brushq3.num_pvsclusters, loadmodel->brushq3.num_pvschainlength, totalchains + sizeof(*in), l->filelen);
4319
4320         loadmodel->brushq3.data_pvschains = Mem_Alloc(loadmodel->mempool, totalchains);
4321         memcpy(loadmodel->brushq3.data_pvschains, (qbyte *)(in + 1), totalchains);
4322 }
4323
4324 void Mod_Q3BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, vec_t radius)
4325 {
4326         // FIXME: finish this code
4327         VectorCopy(in, out);
4328 }
4329
4330 void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end)
4331 {
4332         if (node->isnode)
4333         {
4334                 // recurse down node sides
4335                 int i;
4336                 float dist;
4337                 colpointf_t *ps, *pe;
4338                 // FIXME? if TraceBrushPolygonTransform were to be made usable, the
4339                 // node planes would need to be transformed too
4340                 dist = node->plane->dist - (1.0f / 8.0f);
4341                 for (i = 0, ps = thisbrush_start->points, pe = thisbrush_end->points;i < thisbrush_start->numpoints;i++, ps++, pe++)
4342                 {
4343                         if (DotProduct(ps->v, node->plane->normal) > dist || DotProduct(pe->v, node->plane->normal) > dist)
4344                         {
4345                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end);
4346                                 break;
4347                         }
4348                 }
4349                 dist = node->plane->dist + (1.0f / 8.0f);
4350                 for (i = 0, ps = thisbrush_start->points, pe = thisbrush_end->points;i < thisbrush_start->numpoints;i++, ps++, pe++)
4351                 {
4352                         if (DotProduct(ps->v, node->plane->normal) < dist || DotProduct(pe->v, node->plane->normal) < dist)
4353                         {
4354                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[1], thisbrush_start, thisbrush_end);
4355                                 break;
4356                         }
4357                 }
4358                 /*
4359                 sides = BoxOnPlaneSide(boxstartmins, boxstartmaxs, node->plane) | BoxOnPlaneSide(boxendmins, boxendmaxs, node->plane);
4360                 if (sides & 1)
4361                         Mod_Q3BSP_TraceBox_RecursiveBSPNode(trace, node->children[0], boxstartmins, boxstartmaxs, boxendmins, boxendmaxs);
4362                 if (sides & 2)
4363                         Mod_Q3BSP_TraceBox_RecursiveBSPNode(trace, node->children[1], boxstartmins, boxstartmaxs, boxendmins, boxendmaxs);
4364                 */
4365         }
4366         else
4367         {
4368                 int i;
4369                 q3mleaf_t *leaf;
4370                 leaf = (q3mleaf_t *)node;
4371                 for (i = 0;i < leaf->numleafbrushes;i++)
4372                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
4373         }
4374 }
4375
4376 void Mod_Q3BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
4377 {
4378         // FIXME: write this
4379         ambientcolor[0] += 255;
4380         ambientcolor[1] += 255;
4381         ambientcolor[2] += 255;
4382 }
4383
4384 void Mod_Q3BSP_TraceBox(model_t *model, trace_t *trace, const vec3_t boxstartmins, const vec3_t boxstartmaxs, const vec3_t boxendmins, const vec3_t boxendmaxs)
4385 {
4386         int i;
4387         colbrushf_t *thisbrush_start, *thisbrush_end;
4388         matrix4x4_t startmatrix, endmatrix;
4389         // FIXME: finish this code
4390         Matrix4x4_CreateIdentity(&startmatrix);
4391         Matrix4x4_CreateIdentity(&endmatrix);
4392         thisbrush_start = Collision_BrushForBox(&startmatrix, boxstartmins, boxstartmaxs);
4393         thisbrush_end = Collision_BrushForBox(&endmatrix, boxendmins, boxendmaxs);
4394         memset(trace, 0, sizeof(*trace));
4395         trace->fraction = 1;
4396         if (model->brushq3.num_nodes)
4397                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model->brushq3.data_nodes, thisbrush_start, thisbrush_end);
4398         else
4399                 for (i = 0;i < model->brushq3.num_brushes;i++)
4400                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, model->brushq3.data_brushes[i].colbrushf, model->brushq3.data_brushes[i].colbrushf);
4401 }
4402
4403 void Mod_Q3BSP_Load(model_t *mod, void *buffer)
4404 {
4405         int i;
4406         q3dheader_t *header;
4407
4408         mod->type = mod_brushq2;
4409
4410         header = (q3dheader_t *)buffer;
4411
4412         i = LittleLong(header->version);
4413         if (i != Q3BSPVERSION)
4414                 Host_Error("Mod_Q3BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q3BSPVERSION);
4415         if (loadmodel->isworldmodel)
4416         {
4417                 Cvar_SetValue("halflifebsp", false);
4418                 // until we get a texture for it...
4419                 R_ResetQuakeSky();
4420         }
4421
4422         mod->brush.LightPoint = Mod_Q3BSP_LightPoint;
4423         mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation;
4424         mod->brush.TraceBox = Mod_Q3BSP_TraceBox;
4425         //mod->brushq1.PointInLeaf = Mod_Q1BSP_PointInLeaf;
4426         //mod->brushq1.LeafPVS = Mod_Q1BSP_LeafPVS;
4427         //mod->brushq1.BuildPVSTextureChains = Mod_Q1BSP_BuildPVSTextureChains;
4428
4429         mod_base = (qbyte *)header;
4430
4431         // swap all the lumps
4432         for (i = 0;i < (int) sizeof(*header) / 4;i++)
4433                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
4434
4435         Mod_Q3BSP_LoadEntities(&header->lumps[Q3LUMP_ENTITIES]);
4436         Mod_Q3BSP_LoadTextures(&header->lumps[Q3LUMP_TEXTURES]);
4437         Mod_Q3BSP_LoadPlanes(&header->lumps[Q3LUMP_PLANES]);
4438         Mod_Q3BSP_LoadBrushSides(&header->lumps[Q3LUMP_BRUSHSIDES]);
4439         Mod_Q3BSP_LoadBrushes(&header->lumps[Q3LUMP_BRUSHES]);
4440         Mod_Q3BSP_LoadEffects(&header->lumps[Q3LUMP_EFFECTS]);
4441         Mod_Q3BSP_LoadVertices(&header->lumps[Q3LUMP_VERTICES]);
4442         Mod_Q3BSP_LoadTriangles(&header->lumps[Q3LUMP_TRIANGLES]);
4443         Mod_Q3BSP_LoadLightmaps(&header->lumps[Q3LUMP_LIGHTMAPS]);
4444         Mod_Q3BSP_LoadFaces(&header->lumps[Q3LUMP_FACES]);
4445         Mod_Q3BSP_LoadModels(&header->lumps[Q3LUMP_MODELS]);
4446         Mod_Q3BSP_LoadLeafBrushes(&header->lumps[Q3LUMP_LEAFBRUSHES]);
4447         Mod_Q3BSP_LoadLeafFaces(&header->lumps[Q3LUMP_LEAFFACES]);
4448         Mod_Q3BSP_LoadLeafs(&header->lumps[Q3LUMP_LEAFS]);
4449         Mod_Q3BSP_LoadNodes(&header->lumps[Q3LUMP_NODES]);
4450         Mod_Q3BSP_LoadLightGrid(&header->lumps[Q3LUMP_LIGHTGRID]);
4451         Mod_Q3BSP_LoadPVS(&header->lumps[Q3LUMP_PVS]);
4452 }
4453
4454 void Mod_IBSP_Load(model_t *mod, void *buffer)
4455 {
4456         int i = LittleLong(((int *)buffer)[1]);
4457         if (i == Q3BSPVERSION)
4458                 Mod_Q3BSP_Load(mod,buffer);
4459         else if (i == Q2BSPVERSION)
4460                 Mod_Q2BSP_Load(mod,buffer);
4461         else
4462                 Host_Error("Mod_IBSP_Load: unknown/unsupported version %i\n", i);
4463 }
4464
4465 void Mod_MAP_Load(model_t *mod, void *buffer)
4466 {
4467         Host_Error("Mod_MAP_Load: not yet implemented\n");
4468 }
4469