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