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