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