model_brush.c

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