rewrote memory system entirely (hunk, cache, and zone are gone, memory pools replaced...
[xonotic/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 byte mod_novis[(MAX_MAP_LEAFS + 7)/ 8];
24
25 cvar_t r_subdivide_size = {CVAR_SAVE, "r_subdivide_size", "128"};
26 cvar_t halflifebsp = {0, "halflifebsp", "0"};
27 cvar_t r_novis = {0, "r_novis", "0"};
28 cvar_t r_miplightmaps = {CVAR_SAVE, "r_miplightmaps", "0"};
29 cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1"};
30 cvar_t r_vertexsurfacesthreshold = {CVAR_SAVE, "r_vertexsurfacesthreshold", "48"};
31
32 /*
33 ===============
34 Mod_BrushInit
35 ===============
36 */
37 void Mod_BrushInit (void)
38 {
39         Cvar_RegisterVariable(&r_subdivide_size);
40         Cvar_RegisterVariable(&halflifebsp);
41         Cvar_RegisterVariable(&r_novis);
42         Cvar_RegisterVariable(&r_miplightmaps);
43         Cvar_RegisterVariable(&r_lightmaprgba);
44         Cvar_RegisterVariable(&r_vertexsurfacesthreshold);
45         memset(mod_novis, 0xff, sizeof(mod_novis));
46 }
47
48 void Mod_Brush_SERAddEntity(void)
49 {
50         R_Clip_AddBox(currentrenderentity->mins, currentrenderentity->maxs, R_Entity_Callback, currentrenderentity, NULL);
51 }
52
53 /*
54 ===============
55 Mod_PointInLeaf
56 ===============
57 */
58 mleaf_t *Mod_PointInLeaf (vec3_t p, model_t *model)
59 {
60         mnode_t         *node;
61
62         Mod_CheckLoaded(model);
63 //      if (!model || !model->nodes)
64 //              Sys_Error ("Mod_PointInLeaf: bad model");
65
66         // LordHavoc: modified to start at first clip node,
67         // in other words: first node of the (sub)model
68         node = model->nodes + model->hulls[0].firstclipnode;
69         while (node->contents == 0)
70                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct (p,node->plane->normal)) < node->plane->dist];
71
72         return (mleaf_t *)node;
73 }
74
75 void Mod_FindNonSolidLocation(vec3_t pos, model_t *mod)
76 {
77         if (Mod_PointInLeaf(pos, mod)->contents != CONTENTS_SOLID) return;
78         pos[0]-=1;if (Mod_PointInLeaf(pos, mod)->contents != CONTENTS_SOLID) return;
79         pos[0]+=2;if (Mod_PointInLeaf(pos, mod)->contents != CONTENTS_SOLID) return;
80         pos[0]-=1;
81         pos[1]-=1;if (Mod_PointInLeaf(pos, mod)->contents != CONTENTS_SOLID) return;
82         pos[1]+=2;if (Mod_PointInLeaf(pos, mod)->contents != CONTENTS_SOLID) return;
83         pos[1]-=1;
84         pos[2]-=1;if (Mod_PointInLeaf(pos, mod)->contents != CONTENTS_SOLID) return;
85         pos[2]+=2;if (Mod_PointInLeaf(pos, mod)->contents != CONTENTS_SOLID) return;
86         pos[2]-=1;
87 }
88
89 /*
90 mleaf_t *Mod_PointInLeaf (vec3_t p, model_t *model)
91 {
92         mnode_t         *node;
93         float           d;
94         mplane_t        *plane;
95
96         if (!model || !model->nodes)
97                 Sys_Error ("Mod_PointInLeaf: bad model");
98
99         node = model->nodes;
100         while (1)
101         {
102                 if (node->contents < 0)
103                         return (mleaf_t *)node;
104                 plane = node->plane;
105                 d = DotProduct (p,plane->normal) - plane->dist;
106                 if (d > 0)
107                         node = node->children[0];
108                 else
109                         node = node->children[1];
110         }
111
112         return NULL;    // never reached
113 }
114 */
115
116 /*
117 ===================
118 Mod_DecompressVis
119 ===================
120 */
121 static byte *Mod_DecompressVis (byte *in, model_t *model)
122 {
123         static byte     decompressed[MAX_MAP_LEAFS/8];
124         int             c;
125         byte    *out;
126         int             row;
127
128         row = (model->numleafs+7)>>3;
129         out = decompressed;
130
131         /*
132         if (!in)
133         {       // no vis info, so make all visible
134                 while (row)
135                 {
136                         *out++ = 0xff;
137                         row--;
138                 }
139                 return decompressed;
140         }
141         */
142
143         do
144         {
145                 if (*in)
146                 {
147                         *out++ = *in++;
148                         continue;
149                 }
150
151                 c = in[1];
152                 in += 2;
153                 while (c)
154                 {
155                         *out++ = 0;
156                         c--;
157                 }
158         } while (out - decompressed < row);
159
160         return decompressed;
161 }
162
163 byte *Mod_LeafPVS (mleaf_t *leaf, model_t *model)
164 {
165         if (r_novis.integer || leaf == model->leafs || leaf->compressed_vis == NULL)
166                 return mod_novis;
167         return Mod_DecompressVis (leaf->compressed_vis, model);
168 }
169
170 void Mod_SetupNoTexture(void)
171 {
172         int             x, y;
173         byte    pix[16][16][4];
174
175         for (y = 0;y < 16;y++)
176         {
177                 for (x = 0;x < 16;x++)
178                 {
179                         if ((y < 8) ^ (x < 8))
180                         {
181                                 pix[y][x][0] = 128;
182                                 pix[y][x][1] = 128;
183                                 pix[y][x][2] = 128;
184                                 pix[y][x][3] = 255;
185                         }
186                         else
187                         {
188                                 pix[y][x][0] = 64;
189                                 pix[y][x][1] = 64;
190                                 pix[y][x][2] = 64;
191                                 pix[y][x][3] = 255;
192                         }
193                 }
194         }
195
196         memset(&loadmodel->notexture, 0, sizeof(texture_t));
197         strcpy(loadmodel->notexture.name, "notexture");
198         loadmodel->notexture.width = 16;
199         loadmodel->notexture.height = 16;
200         loadmodel->notexture.flags = 0;
201         loadmodel->notexture.texture = R_LoadTexture(loadmodel->texturepool, "notexture", 16, 16, &pix[0][0][0], TEXTYPE_RGBA, TEXF_MIPMAP);
202 }
203
204 /*
205 =================
206 Mod_LoadTextures
207 =================
208 */
209 static void Mod_LoadTextures (lump_t *l)
210 {
211         int                             i, j, k, num, max, altmax, mtwidth, mtheight, *dofs;
212         miptex_t                *dmiptex;
213         texture_t               *tx, *tx2, *anims[10], *altanims[10];
214         dmiptexlump_t   *m;
215         byte                    *data, *mtdata, *data2;
216         char                    name[256];
217
218         Mod_SetupNoTexture();
219
220         if (!l->filelen)
221         {
222                 loadmodel->textures = NULL;
223                 return;
224         }
225
226         m = (dmiptexlump_t *)(mod_base + l->fileofs);
227
228         m->nummiptex = LittleLong (m->nummiptex);
229
230         loadmodel->numtextures = m->nummiptex;
231         loadmodel->textures = Mem_Alloc(loadmodel->mempool, m->nummiptex * sizeof(*loadmodel->textures));
232
233         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
234         dofs = m->dataofs;
235         for (i = 0;i < m->nummiptex;i++)
236         {
237                 dofs[i] = LittleLong(dofs[i]);
238                 if (dofs[i] == -1)
239                         continue;
240                 dmiptex = (miptex_t *)((byte *)m + dofs[i]);
241                 mtwidth = LittleLong (dmiptex->width);
242                 mtheight = LittleLong (dmiptex->height);
243                 mtdata = NULL;
244                 j = LittleLong (dmiptex->offsets[0]);
245                 if (j)
246                 {
247                         // texture included
248                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
249                                 Host_Error ("Texture %s is corrupt or incomplete\n", dmiptex->name);
250                         mtdata = (byte *)dmiptex + j;
251                 }
252
253                 if ((mtwidth & 15) || (mtheight & 15))
254                         Host_Error ("Texture %s is not 16 aligned", dmiptex->name);
255                 // LordHavoc: rewriting the map texture loader for GLQuake
256                 tx = Mem_Alloc(loadmodel->mempool, sizeof(texture_t));
257                 memset(tx, 0, sizeof(texture_t));
258                 tx->anim_total = 0;
259                 tx->alternate_anims = NULL;
260                 loadmodel->textures[i] = tx;
261
262                 // LordHavoc: force all names to lowercase and make sure they are terminated while copying
263                 for (j = 0;dmiptex->name[j] && j < 15;j++)
264                 {
265                         if (dmiptex->name[j] >= 'A' && dmiptex->name[j] <= 'Z')
266                                 tx->name[j] = dmiptex->name[j] + ('a' - 'A');
267                         else
268                                 tx->name[j] = dmiptex->name[j];
269                 }
270                 for (;j < 16;j++)
271                         tx->name[j] = 0;
272
273                 if (!tx->name[0])
274                 {
275                         Con_Printf("warning: unnamed texture in %s\n", loadmodel->name);
276                         sprintf(tx->name, "unnamed%i", i);
277                 }
278
279                 tx->width = mtwidth;
280                 tx->height = mtheight;
281                 tx->texture = NULL;
282                 tx->glowtexture = NULL;
283                 tx->fogtexture = NULL;
284
285                 if (!loadmodel->ishlbsp && !strncmp(tx->name,"sky",3) && mtwidth == 256 && mtheight == 128) // LordHavoc: HL sky textures are entirely unrelated
286                 {
287                         data = loadimagepixels(tx->name, false, 0, 0);
288                         if (data)
289                         {
290                                 if (image_width == 256 && image_height == 128)
291                                 {
292                                         if (loadmodel->isworldmodel)
293                                                 R_InitSky (data, 4);
294                                         Mem_Free(data);
295                                 }
296                                 else
297                                 {
298                                         Mem_Free(data);
299                                         Host_Error("Mod_LoadTextures: replacement sky image must be 256x128 pixels\n");
300                                 }
301                         }
302                         else if (loadmodel->isworldmodel)
303                                 R_InitSky (mtdata, 1);
304                 }
305                 else if ((tx->texture = loadtextureimagewithmask(loadmodel->texturepool, tx->name, 0, 0, false, true, true)))
306                 {
307                         tx->fogtexture = image_masktex;
308                         strcpy(name, tx->name);
309                         strcat(name, "_glow");
310                         tx->glowtexture = loadtextureimage(loadmodel->texturepool, name, 0, 0, false, true, true);
311                 }
312                 else
313                 {
314                         if (loadmodel->ishlbsp)
315                         {
316                                 if (mtdata && (data = W_ConvertWAD3Texture(dmiptex)))
317                                 {
318                                         // texture included
319                                         tx->texture = R_LoadTexture (loadmodel->texturepool, tx->name, image_width, image_height, data, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE);
320                                         if (R_TextureHasAlpha(tx->texture))
321                                         {
322                                                 // make mask texture
323                                                 for (j = 0;j < image_width * image_height;j++)
324                                                         data[j*4+0] = data[j*4+1] = data[j*4+2] = 255;
325                                                 strcpy(name, tx->name);
326                                                 strcat(name, "_fog");
327                                                 tx->fogtexture = R_LoadTexture (loadmodel->texturepool, name, image_width, image_height, data, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE);
328                                         }
329                                         Mem_Free(data);
330                                 }
331                                 else if ((data = W_GetTexture(tx->name)))
332                                 {
333                                         // get the size from the wad texture
334                                         tx->width = image_width;
335                                         tx->height = image_height;
336                                         tx->texture = R_LoadTexture (loadmodel->texturepool, tx->name, image_width, image_height, data, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE);
337                                         if (R_TextureHasAlpha(tx->texture))
338                                         {
339                                                 // make mask texture
340                                                 for (j = 0;j < image_width * image_height;j++)
341                                                         data[j*4+0] = data[j*4+1] = data[j*4+2] = 255;
342                                                 strcpy(name, tx->name);
343                                                 strcat(name, "_fog");
344                                                 tx->fogtexture = R_LoadTexture (loadmodel->texturepool, name, image_width, image_height, data, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE);
345                                         }
346                                         Mem_Free(data);
347                                 }
348                                 else
349                                 {
350                                         tx->width = 16;
351                                         tx->height = 16;
352                                         tx->texture = loadmodel->notexture.texture;
353                                 }
354                         }
355                         else
356                         {
357                                 if (mtdata) // texture included
358                                 {
359                                         int fullbrights;
360                                         data = mtdata;
361                                         fullbrights = false;
362                                         if (r_fullbrights.value && tx->name[0] != '*')
363                                         {
364                                                 for (j = 0;j < tx->width*tx->height;j++)
365                                                 {
366                                                         if (data[j] >= 224) // fullbright
367                                                         {
368                                                                 fullbrights = true;
369                                                                 break;
370                                                         }
371                                                 }
372                                         }
373                                         if (fullbrights)
374                                         {
375                                                 data2 = Mem_Alloc(tempmempool, tx->width*tx->height);
376                                                 for (j = 0;j < tx->width*tx->height;j++)
377                                                         data2[j] = data[j] >= 224 ? 0 : data[j]; // no fullbrights
378                                                 tx->texture = R_LoadTexture (loadmodel->texturepool, tx->name, tx->width, tx->height, data2, TEXTYPE_QPALETTE, TEXF_MIPMAP | TEXF_PRECACHE);
379                                                 strcpy(name, tx->name);
380                                                 strcat(name, "_glow");
381                                                 for (j = 0;j < tx->width*tx->height;j++)
382                                                         data2[j] = data[j] >= 224 ? data[j] : 0; // only fullbrights
383                                                 tx->glowtexture = R_LoadTexture (loadmodel->texturepool, name, tx->width, tx->height, data2, TEXTYPE_QPALETTE, TEXF_MIPMAP | TEXF_PRECACHE);
384                                                 Mem_Free(data2);
385                                         }
386                                         else
387                                                 tx->texture = R_LoadTexture (loadmodel->texturepool, tx->name, tx->width, tx->height, data, TEXTYPE_QPALETTE, TEXF_MIPMAP | TEXF_PRECACHE);
388                                 }
389                                 else // no texture, and no external replacement texture was found
390                                 {
391                                         tx->width = 16;
392                                         tx->height = 16;
393                                         tx->texture = loadmodel->notexture.texture;
394                                 }
395                         }
396                 }
397
398                 if (tx->name[0] == '*')
399                 {
400                         tx->flags |= (SURF_DRAWTURB | SURF_LIGHTBOTHSIDES);
401                         // LordHavoc: some turbulent textures should be fullbright and solid
402                         if (!strncmp(tx->name,"*lava",5)
403                          || !strncmp(tx->name,"*teleport",9)
404                          || !strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
405                                 tx->flags |= (SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA | SURF_CLIPSOLID);
406                 }
407                 else if (tx->name[0] == 's' && tx->name[1] == 'k' && tx->name[2] == 'y')
408                         tx->flags |= (SURF_DRAWSKY | SURF_CLIPSOLID);
409                 else
410                 {
411                         tx->flags |= SURF_LIGHTMAP;
412                         if (!R_TextureHasAlpha(tx->texture))
413                                 tx->flags |= SURF_CLIPSOLID;
414                 }
415         }
416
417 //
418 // sequence the animations
419 //
420         for (i = 0;i < m->nummiptex;i++)
421         {
422                 tx = loadmodel->textures[i];
423                 if (!tx || tx->name[0] != '+')
424                         continue;
425                 if (tx->anim_total)
426                         continue;       // already sequenced
427
428                 // find the number of frames in the animation
429                 memset (anims, 0, sizeof(anims));
430                 memset (altanims, 0, sizeof(altanims));
431                 max = altmax = 0;
432
433                 for (j = i;j < m->nummiptex;j++)
434                 {
435                         tx2 = loadmodel->textures[j];
436                         if (!tx2 || tx2->name[0] != '+' || strcmp (tx2->name+2, tx->name+2))
437                                 continue;
438
439                         num = tx2->name[1];
440                         if (num >= '0' && num <= '9')
441                                 anims[num - '0'] = tx2;
442                         else if (num >= 'a' && num <= 'j')
443                                 altanims[num - 'a'] = tx2;
444                         else
445                                 Host_Error ("Bad animating texture %s", tx->name);
446                 }
447
448                 for (j = 0;j < 10;j++)
449                 {
450                         if (anims[j] != NULL)
451                                 max = j + 1;
452                         if (altanims[j] != NULL)
453                                 altmax = j + 1;
454                 }
455
456                 // link them all together
457                 for (j = 0;j < max;j++)
458                 {
459                         tx2 = anims[j];
460                         if (!tx2)
461                                 Host_Error ("Missing frame %i of %s", j, tx->name);
462                         tx2->anim_total = max;
463                         tx2->alternate_anims = altanims[0]; // NULL if there is no alternate
464                         for (k = 0;k < 10;k++)
465                                 tx2->anim_frames[k] = anims[k];
466                 }
467
468                 for (j = 0;j < altmax;j++)
469                 {
470                         tx2 = altanims[j];
471                         if (!tx2)
472                                 Host_Error ("Missing frame %i of %s", j, tx->name);
473                         tx2->anim_total = altmax;
474                         tx2->alternate_anims = anims[0]; // NULL if there is no alternate
475                         for (k = 0;k < 10;k++)
476                                 tx2->anim_frames[k] = altanims[k];
477                 }
478         }
479 }
480
481 /*
482 =================
483 Mod_LoadLighting
484 =================
485 */
486 static void Mod_LoadLighting (lump_t *l)
487 {
488         int i;
489         byte *in, *out, *data;
490         byte d;
491         char litfilename[1024];
492         loadmodel->lightdata = NULL;
493         if (loadmodel->ishlbsp) // LordHavoc: load the colored lighting data straight
494         {
495                 loadmodel->lightdata = Mem_Alloc(loadmodel->mempool, l->filelen);
496                 memcpy (loadmodel->lightdata, mod_base + l->fileofs, l->filelen);
497         }
498         else // LordHavoc: bsp version 29 (normal white lighting)
499         {
500                 // LordHavoc: hope is not lost yet, check for a .lit file to load
501                 strcpy(litfilename, loadmodel->name);
502                 COM_StripExtension(litfilename, litfilename);
503                 strcat(litfilename, ".lit");
504                 data = (byte*) COM_LoadFile (litfilename, false);
505                 if (data)
506                 {
507                         if (loadsize > 8 && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
508                         {
509                                 i = LittleLong(((int *)data)[1]);
510                                 if (i == 1)
511                                 {
512                                         Con_DPrintf("%s loaded", litfilename);
513                                         loadmodel->lightdata = Mem_Alloc(loadmodel->mempool, loadsize - 8);
514                                         memcpy(loadmodel->lightdata, data + 8, loadsize - 8);
515                                         Mem_Free(data);
516                                         return;
517                                 }
518                                 else
519                                 {
520                                         Con_Printf("Unknown .lit file version (%d)\n", i);
521                                         Mem_Free(data);
522                                 }
523                         }
524                         else
525                         {
526                                 if (loadsize == 8)
527                                         Con_Printf("Empty .lit file, ignoring\n");
528                                 else
529                                         Con_Printf("Corrupt .lit file (old version?), ignoring\n");
530                                 Mem_Free(data);
531                         }
532                 }
533                 // LordHavoc: oh well, expand the white lighting data
534                 if (!l->filelen)
535                         return;
536                 loadmodel->lightdata = Mem_Alloc(loadmodel->mempool, l->filelen*3);
537                 in = loadmodel->lightdata + l->filelen*2; // place the file at the end, so it will not be overwritten until the very last write
538                 out = loadmodel->lightdata;
539                 memcpy (in, mod_base + l->fileofs, l->filelen);
540                 for (i = 0;i < l->filelen;i++)
541                 {
542                         d = *in++;
543                         *out++ = d;
544                         *out++ = d;
545                         *out++ = d;
546                 }
547         }
548 }
549
550
551 /*
552 =================
553 Mod_LoadVisibility
554 =================
555 */
556 static void Mod_LoadVisibility (lump_t *l)
557 {
558         if (!l->filelen)
559         {
560                 loadmodel->visdata = NULL;
561                 return;
562         }
563         loadmodel->visdata = Mem_Alloc(loadmodel->mempool, l->filelen);
564         memcpy (loadmodel->visdata, mod_base + l->fileofs, l->filelen);
565 }
566
567 // used only for HalfLife maps
568 void Mod_ParseWadsFromEntityLump(char *data)
569 {
570         char key[128], value[4096];
571         char wadname[128];
572         int i, j, k;
573         if (!data)
574                 return;
575         data = COM_Parse(data);
576         if (!data)
577                 return; // error
578         if (com_token[0] != '{')
579                 return; // error
580         while (1)
581         {
582                 data = COM_Parse(data);
583                 if (!data)
584                         return; // error
585                 if (com_token[0] == '}')
586                         break; // end of worldspawn
587                 if (com_token[0] == '_')
588                         strcpy(key, com_token + 1);
589                 else
590                         strcpy(key, com_token);
591                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
592                         key[strlen(key)-1] = 0;
593                 data = COM_Parse(data);
594                 if (!data)
595                         return; // error
596                 strcpy(value, com_token);
597                 if (!strcmp("wad", key)) // for HalfLife maps
598                 {
599                         if (loadmodel->ishlbsp)
600                         {
601                                 j = 0;
602                                 for (i = 0;i < 4096;i++)
603                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
604                                                 break;
605                                 if (value[i])
606                                 {
607                                         for (;i < 4096;i++)
608                                         {
609                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
610                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
611                                                         j = i+1;
612                                                 else if (value[i] == ';' || value[i] == 0)
613                                                 {
614                                                         k = value[i];
615                                                         value[i] = 0;
616                                                         strcpy(wadname, "textures/");
617                                                         strcat(wadname, &value[j]);
618                                                         W_LoadTextureWadFile (wadname, false);
619                                                         j = i+1;
620                                                         if (!k)
621                                                                 break;
622                                                 }
623                                         }
624                                 }
625                         }
626                 }
627         }
628 }
629
630 /*
631 =================
632 Mod_LoadEntities
633 =================
634 */
635 static void Mod_LoadEntities (lump_t *l)
636 {
637         if (!l->filelen)
638         {
639                 loadmodel->entities = NULL;
640                 return;
641         }
642         loadmodel->entities = Mem_Alloc(loadmodel->mempool, l->filelen);
643         memcpy (loadmodel->entities, mod_base + l->fileofs, l->filelen);
644         if (loadmodel->ishlbsp)
645                 Mod_ParseWadsFromEntityLump(loadmodel->entities);
646 }
647
648
649 /*
650 =================
651 Mod_LoadVertexes
652 =================
653 */
654 static void Mod_LoadVertexes (lump_t *l)
655 {
656         dvertex_t       *in;
657         mvertex_t       *out;
658         int                     i, count;
659
660         in = (void *)(mod_base + l->fileofs);
661         if (l->filelen % sizeof(*in))
662                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
663         count = l->filelen / sizeof(*in);
664         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
665
666         loadmodel->vertexes = out;
667         loadmodel->numvertexes = count;
668
669         for ( i=0 ; i<count ; i++, in++, out++)
670         {
671                 out->position[0] = LittleFloat (in->point[0]);
672                 out->position[1] = LittleFloat (in->point[1]);
673                 out->position[2] = LittleFloat (in->point[2]);
674         }
675 }
676
677 /*
678 =================
679 Mod_LoadSubmodels
680 =================
681 */
682 static void Mod_LoadSubmodels (lump_t *l)
683 {
684         dmodel_t        *in;
685         dmodel_t        *out;
686         int                     i, j, count;
687
688         in = (void *)(mod_base + l->fileofs);
689         if (l->filelen % sizeof(*in))
690                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
691         count = l->filelen / sizeof(*in);
692         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
693
694         loadmodel->submodels = out;
695         loadmodel->numsubmodels = count;
696
697         for ( i=0 ; i<count ; i++, in++, out++)
698         {
699                 for (j=0 ; j<3 ; j++)
700                 {
701                         // spread the mins / maxs by a pixel
702                         out->mins[j] = LittleFloat (in->mins[j]) - 1;
703                         out->maxs[j] = LittleFloat (in->maxs[j]) + 1;
704                         out->origin[j] = LittleFloat (in->origin[j]);
705                 }
706                 for (j=0 ; j<MAX_MAP_HULLS ; j++)
707                         out->headnode[j] = LittleLong (in->headnode[j]);
708                 out->visleafs = LittleLong (in->visleafs);
709                 out->firstface = LittleLong (in->firstface);
710                 out->numfaces = LittleLong (in->numfaces);
711         }
712 }
713
714 /*
715 =================
716 Mod_LoadEdges
717 =================
718 */
719 static void Mod_LoadEdges (lump_t *l)
720 {
721         dedge_t *in;
722         medge_t *out;
723         int     i, count;
724
725         in = (void *)(mod_base + l->fileofs);
726         if (l->filelen % sizeof(*in))
727                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
728         count = l->filelen / sizeof(*in);
729         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
730
731         loadmodel->edges = out;
732         loadmodel->numedges = count;
733
734         for ( i=0 ; i<count ; i++, in++, out++)
735         {
736                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
737                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
738         }
739 }
740
741 /*
742 =================
743 Mod_LoadTexinfo
744 =================
745 */
746 static void Mod_LoadTexinfo (lump_t *l)
747 {
748         texinfo_t *in;
749         mtexinfo_t *out;
750         int     i, j, k, count;
751         int             miptex;
752
753         in = (void *)(mod_base + l->fileofs);
754         if (l->filelen % sizeof(*in))
755                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
756         count = l->filelen / sizeof(*in);
757         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
758
759         loadmodel->texinfo = out;
760         loadmodel->numtexinfo = count;
761
762         for (i = 0;i < count;i++, in++, out++)
763         {
764                 for (k = 0;k < 2;k++)
765                         for (j = 0;j < 4;j++)
766                                 out->vecs[k][j] = LittleFloat (in->vecs[k][j]);
767
768                 miptex = LittleLong (in->miptex);
769                 out->flags = LittleLong (in->flags);
770
771                 if (!loadmodel->textures)
772                         out->texture = &loadmodel->notexture;
773                 else
774                 {
775                         if (miptex < 0)
776                                 Host_Error ("miptex < 0");
777                         if (miptex >= loadmodel->numtextures)
778                                 Host_Error ("miptex >= loadmodel->numtextures");
779                         out->texture = loadmodel->textures[miptex];
780                 }
781                 if (!out->texture)
782                         out->texture = &loadmodel->notexture;
783         }
784 }
785
786 /*
787 ================
788 CalcSurfaceExtents
789
790 Fills in s->texturemins[] and s->extents[]
791 ================
792 */
793 static void CalcSurfaceExtents (msurface_t *s)
794 {
795         float   mins[2], maxs[2], val;
796         int             i,j, e;
797         mvertex_t       *v;
798         mtexinfo_t      *tex;
799         int             bmins[2], bmaxs[2];
800
801         mins[0] = mins[1] = 999999999;
802         maxs[0] = maxs[1] = -999999999;
803
804         tex = s->texinfo;
805
806         for (i=0 ; i<s->numedges ; i++)
807         {
808                 e = loadmodel->surfedges[s->firstedge+i];
809                 if (e >= 0)
810                         v = &loadmodel->vertexes[loadmodel->edges[e].v[0]];
811                 else
812                         v = &loadmodel->vertexes[loadmodel->edges[-e].v[1]];
813
814                 for (j=0 ; j<2 ; j++)
815                 {
816                         val = v->position[0] * tex->vecs[j][0] +
817                                 v->position[1] * tex->vecs[j][1] +
818                                 v->position[2] * tex->vecs[j][2] +
819                                 tex->vecs[j][3];
820                         if (val < mins[j])
821                                 mins[j] = val;
822                         if (val > maxs[j])
823                                 maxs[j] = val;
824                 }
825         }
826
827         for (i=0 ; i<2 ; i++)
828         {
829                 bmins[i] = floor(mins[i]/16);
830                 bmaxs[i] = ceil(maxs[i]/16);
831
832                 s->texturemins[i] = bmins[i] * 16;
833                 s->extents[i] = (bmaxs[i] - bmins[i]) * 16;
834 //              if ( !(tex->flags & TEX_SPECIAL) && s->extents[i] > 512)
835                 if ((tex->flags & TEX_SPECIAL) == 0 && (s->extents[i]+1) > (256*16))
836                         Host_Error ("Bad surface extents");
837         }
838 }
839
840
841 void BoundPoly (int numverts, float *verts, vec3_t mins, vec3_t maxs)
842 {
843         int             i, j;
844         float   *v;
845
846         mins[0] = mins[1] = mins[2] = 9999;
847         maxs[0] = maxs[1] = maxs[2] = -9999;
848         v = verts;
849         for (i = 0;i < numverts;i++)
850         {
851                 for (j = 0;j < 3;j++, v++)
852                 {
853                         if (*v < mins[j])
854                                 mins[j] = *v;
855                         if (*v > maxs[j])
856                                 maxs[j] = *v;
857                 }
858         }
859 }
860
861 #define MAX_SUBDIVPOLYTRIANGLES 4096
862 #define MAX_SUBDIVPOLYVERTS (MAX_SUBDIVPOLYTRIANGLES * 3)
863
864 static int subdivpolyverts, subdivpolytriangles;
865 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
866 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
867
868 static int subdivpolylookupvert(vec3_t v)
869 {
870         int i;
871         for (i = 0;i < subdivpolyverts;i++)
872                 if (subdivpolyvert[i][0] == v[0]
873                  && subdivpolyvert[i][1] == v[1]
874                  && subdivpolyvert[i][2] == v[2])
875                         return i;
876         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
877                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
878         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
879         return subdivpolyverts++;
880 }
881
882 static void SubdividePolygon (int numverts, float *verts)
883 {
884         int             i, i1, i2, i3, f, b, c, p;
885         vec3_t  mins, maxs, front[256], back[256];
886         float   m, *pv, *cv, dist[256], frac;
887
888         if (numverts > 250)
889                 Host_Error ("SubdividePolygon: ran out of verts in buffer");
890
891         BoundPoly (numverts, verts, mins, maxs);
892
893         for (i = 0;i < 3;i++)
894         {
895                 m = (mins[i] + maxs[i]) * 0.5;
896                 m = r_subdivide_size.value * floor (m/r_subdivide_size.value + 0.5);
897                 if (maxs[i] - m < 8)
898                         continue;
899                 if (m - mins[i] < 8)
900                         continue;
901
902                 // cut it
903                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
904                         dist[c] = cv[i] - m;
905
906                 f = b = 0;
907                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
908                 {
909                         if (dist[p] >= 0)
910                         {
911                                 VectorCopy (pv, front[f]);
912                                 f++;
913                         }
914                         if (dist[p] <= 0)
915                         {
916                                 VectorCopy (pv, back[b]);
917                                 b++;
918                         }
919                         if (dist[p] == 0 || dist[c] == 0)
920                                 continue;
921                         if ( (dist[p] > 0) != (dist[c] > 0) )
922                         {
923                                 // clip point
924                                 frac = dist[p] / (dist[p] - dist[c]);
925                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
926                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
927                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
928                                 f++;
929                                 b++;
930                         }
931                 }
932
933                 SubdividePolygon (f, front[0]);
934                 SubdividePolygon (b, back[0]);
935                 return;
936         }
937
938         i1 = subdivpolylookupvert(verts);
939         i2 = subdivpolylookupvert(verts + 3);
940         for (i = 2;i < numverts;i++)
941         {
942                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
943                 {
944                         Con_Printf("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
945                         return;
946                 }
947
948                 i3 = subdivpolylookupvert(verts + i * 3);
949                 subdivpolyindex[subdivpolytriangles][0] = i1;
950                 subdivpolyindex[subdivpolytriangles][1] = i2;
951                 subdivpolyindex[subdivpolytriangles][2] = i3;
952                 i2 = i3;
953                 subdivpolytriangles++;
954         }
955 }
956
957 /*
958 ================
959 Mod_GenerateWarpMesh
960
961 Breaks a polygon up along axial 64 unit
962 boundaries so that turbulent and sky warps
963 can be done reasonably.
964 ================
965 */
966 void Mod_GenerateWarpMesh (msurface_t *surf)
967 {
968         int                             i, j;
969         surfvertex_t    *v;
970         surfmesh_t              *mesh;
971
972         subdivpolytriangles = 0;
973         subdivpolyverts = 0;
974         SubdividePolygon (surf->poly_numverts, surf->poly_verts);
975
976         mesh = &surf->mesh;
977         mesh->numverts = subdivpolyverts;
978         mesh->numtriangles = subdivpolytriangles;
979         if (mesh->numtriangles < 1)
980                 Host_Error("Mod_GenerateWarpMesh: no triangles?\n");
981         mesh->index = Mem_Alloc(loadmodel->mempool, mesh->numtriangles * sizeof(int[3]) + mesh->numverts * sizeof(surfvertex_t));
982         mesh->vertex = (surfvertex_t *)((long) mesh->index + mesh->numtriangles * sizeof(int[3]));
983         memset(mesh->vertex, 0, mesh->numverts * sizeof(surfvertex_t));
984
985         for (i = 0;i < mesh->numtriangles;i++)
986         {
987                 for (j = 0;j < 3;j++)
988                 {
989                         mesh->index[i*3+j] = subdivpolyindex[i][j];
990                         //if (mesh->index[i] < 0 || mesh->index[i] >= mesh->numverts)
991                         //      Host_Error("Mod_GenerateWarpMesh: invalid index generated\n");
992                 }
993         }
994
995         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
996         {
997                 VectorCopy(subdivpolyvert[i], v->v);
998                 v->st[0] = DotProduct (v->v, surf->texinfo->vecs[0]);
999                 v->st[1] = DotProduct (v->v, surf->texinfo->vecs[1]);
1000         }
1001 }
1002
1003 void Mod_GenerateVertexLitMesh (msurface_t *surf)
1004 {
1005         int                             i, is, it, *index, smax, tmax;
1006         float                   *in, s, t;
1007         surfvertex_t    *out;
1008         surfmesh_t              *mesh;
1009
1010         //surf->flags |= SURF_LIGHTMAP;
1011         smax = surf->extents[0] >> 4;
1012         tmax = surf->extents[1] >> 4;
1013         surf->lightmaptexturestride = 0;
1014         surf->lightmaptexture = NULL;
1015
1016         mesh = &surf->mesh;
1017         mesh->numverts = surf->poly_numverts;
1018         mesh->numtriangles = surf->poly_numverts - 2;
1019         mesh->index = Mem_Alloc(loadmodel->mempool, mesh->numtriangles * sizeof(int[3]) + mesh->numverts * sizeof(surfvertex_t));
1020         mesh->vertex = (surfvertex_t *)((long) mesh->index + mesh->numtriangles * sizeof(int[3]));
1021         memset(mesh->vertex, 0, mesh->numverts * sizeof(surfvertex_t));
1022
1023         index = mesh->index;
1024         for (i = 0;i < mesh->numtriangles;i++)
1025         {
1026                 *index++ = 0;
1027                 *index++ = i + 1;
1028                 *index++ = i + 2;
1029         }
1030
1031         for (i = 0, in = surf->poly_verts, out = mesh->vertex;i < mesh->numverts;i++, in += 3, out++)
1032         {
1033                 VectorCopy (in, out->v);
1034
1035                 s = DotProduct (out->v, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3];
1036                 t = DotProduct (out->v, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3];
1037
1038                 out->st[0] = s / surf->texinfo->texture->width;
1039                 out->st[1] = t / surf->texinfo->texture->height;
1040
1041                 s = (s + 8 - surf->texturemins[0]) * (1.0 / 16.0);
1042                 t = (t + 8 - surf->texturemins[1]) * (1.0 / 16.0);
1043
1044                 // lightmap coordinates
1045                 out->uv[0] = 0;
1046                 out->uv[1] = 0;
1047
1048                 // LordHavoc: calc lightmap data offset for vertex lighting to use
1049                 is = (int) s;
1050                 it = (int) t;
1051                 is = bound(0, is, smax);
1052                 it = bound(0, it, tmax);
1053                 out->lightmapoffset = ((it * (smax+1) + is) * 3);
1054         }
1055 }
1056
1057 void Mod_GenerateLightmappedMesh (msurface_t *surf)
1058 {
1059         int                             i, is, it, *index, smax, tmax;
1060         float                   *in, s, t, xbase, ybase, xscale, yscale;
1061         surfvertex_t    *out;
1062         surfmesh_t              *mesh;
1063
1064         surf->flags |= SURF_LIGHTMAP;
1065         smax = surf->extents[0] >> 4;
1066         tmax = surf->extents[1] >> 4;
1067         if (r_miplightmaps.integer)
1068         {
1069                 surf->lightmaptexturestride = (surf->extents[0]>>4)+1;
1070                 surf->lightmaptexture = R_ProceduralTexture(loadmodel->texturepool, NULL, surf->lightmaptexturestride, (surf->extents[1]>>4)+1, loadmodel->lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_MIPMAP/* | TEXF_PRECACHE*/, NULL, NULL, 0);
1071         }
1072         else
1073         {
1074                 surf->lightmaptexturestride = R_CompatibleFragmentWidth((surf->extents[0]>>4)+1, loadmodel->lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, 0);
1075                 surf->lightmaptexture = R_ProceduralTexture(loadmodel->texturepool, NULL, surf->lightmaptexturestride, (surf->extents[1]>>4)+1, loadmodel->lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FRAGMENT/* | TEXF_PRECACHE*/, NULL, NULL, 0);
1076         }
1077 //      surf->lightmaptexture = R_LoadTexture(loadmodel->texturepool, va("lightmap%08x", lightmapnum), surf->lightmaptexturestride, (surf->extents[1]>>4)+1, NULL, loadmodel->lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FRAGMENT | TEXF_PRECACHE);
1078 //      surf->lightmaptexture = R_LoadTexture(loadmodel->texturepool, va("lightmap%08x", lightmapnum), surf->lightmaptexturestride, (surf->extents[1]>>4)+1, NULL, loadmodel->lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_PRECACHE);
1079         R_GetFragmentLocation(surf->lightmaptexture, NULL, NULL, &xbase, &ybase, &xscale, &yscale);
1080         xscale = (xscale - xbase) * 16.0 / ((surf->extents[0] & ~15) + 16);
1081         yscale = (yscale - ybase) * 16.0 / ((surf->extents[1] & ~15) + 16);
1082
1083         mesh = &surf->mesh;
1084         mesh->numverts = surf->poly_numverts;
1085         mesh->numtriangles = surf->poly_numverts - 2;
1086         mesh->index = Mem_Alloc(loadmodel->mempool, mesh->numtriangles * sizeof(int[3]) + mesh->numverts * sizeof(surfvertex_t));
1087         mesh->vertex = (surfvertex_t *)((long) mesh->index + mesh->numtriangles * sizeof(int[3]));
1088         memset(mesh->vertex, 0, mesh->numverts * sizeof(surfvertex_t));
1089
1090         index = mesh->index;
1091         for (i = 0;i < mesh->numtriangles;i++)
1092         {
1093                 *index++ = 0;
1094                 *index++ = i + 1;
1095                 *index++ = i + 2;
1096         }
1097
1098         for (i = 0, in = surf->poly_verts, out = mesh->vertex;i < mesh->numverts;i++, in += 3, out++)
1099         {
1100                 VectorCopy (in, out->v);
1101
1102                 s = DotProduct (out->v, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3];
1103                 t = DotProduct (out->v, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3];
1104
1105                 out->st[0] = s / surf->texinfo->texture->width;
1106                 out->st[1] = t / surf->texinfo->texture->height;
1107
1108                 s = (s + 8 - surf->texturemins[0]) * (1.0 / 16.0);
1109                 t = (t + 8 - surf->texturemins[1]) * (1.0 / 16.0);
1110
1111                 // lightmap coordinates
1112                 out->uv[0] = s * xscale + xbase;
1113                 out->uv[1] = t * yscale + ybase;
1114
1115                 // LordHavoc: calc lightmap data offset for vertex lighting to use
1116                 is = (int) s;
1117                 it = (int) t;
1118                 is = bound(0, is, smax);
1119                 it = bound(0, it, tmax);
1120                 out->lightmapoffset = ((it * (smax+1) + is) * 3);
1121         }
1122 }
1123
1124 void Mod_GenerateSurfacePolygon (msurface_t *surf)
1125 {
1126         float           *vert;
1127         int                     i;
1128         int                     lindex;
1129         float           *vec;
1130
1131         // convert edges back to a normal polygon
1132         surf->poly_numverts = surf->numedges;
1133         vert = surf->poly_verts = Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * surf->numedges);
1134         for (i = 0;i < surf->numedges;i++)
1135         {
1136                 lindex = loadmodel->surfedges[surf->firstedge + i];
1137                 if (lindex > 0)
1138                         vec = loadmodel->vertexes[loadmodel->edges[lindex].v[0]].position;
1139                 else
1140                         vec = loadmodel->vertexes[loadmodel->edges[-lindex].v[1]].position;
1141                 VectorCopy (vec, vert);
1142                 vert += 3;
1143         }
1144 }
1145
1146 /*
1147 =================
1148 Mod_LoadFaces
1149 =================
1150 */
1151 static void Mod_LoadFaces (lump_t *l)
1152 {
1153         dface_t         *in;
1154         msurface_t      *out;
1155         int                     i, count, surfnum;
1156         int                     planenum, side;
1157
1158         in = (void *)(mod_base + l->fileofs);
1159         if (l->filelen % sizeof(*in))
1160                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1161         count = l->filelen / sizeof(*in);
1162         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1163
1164         loadmodel->surfaces = out;
1165         loadmodel->numsurfaces = count;
1166
1167         for (surfnum = 0;surfnum < count;surfnum++, in++, out++)
1168         {
1169                 // FIXME: validate edges, texinfo, etc?
1170                 out->firstedge = LittleLong(in->firstedge);
1171                 out->numedges = LittleShort(in->numedges);
1172
1173                 out->texinfo = loadmodel->texinfo + LittleShort (in->texinfo);
1174                 out->flags = out->texinfo->texture->flags;
1175
1176                 planenum = LittleShort(in->planenum);
1177                 side = LittleShort(in->side);
1178                 if (side)
1179                         out->flags |= SURF_PLANEBACK;
1180
1181                 out->plane = loadmodel->planes + planenum;
1182
1183                 // clear lightmap (filled in later)
1184                 out->lightmaptexture = NULL;
1185
1186                 // force lightmap upload on first time seeing the surface
1187                 out->cached_dlight = true;
1188                 out->cached_ambient = -1000;
1189                 out->cached_lightscalebit = -1000;
1190                 out->cached_light[0] = -1000;
1191                 out->cached_light[1] = -1000;
1192                 out->cached_light[2] = -1000;
1193                 out->cached_light[3] = -1000;
1194
1195                 CalcSurfaceExtents (out);
1196
1197                 // lighting info
1198                 for (i = 0;i < MAXLIGHTMAPS;i++)
1199                         out->styles[i] = in->styles[i];
1200                 i = LittleLong(in->lightofs);
1201                 if (i == -1)
1202                         out->samples = NULL;
1203                 else if (loadmodel->ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
1204                         out->samples = loadmodel->lightdata + i;
1205                 else // LordHavoc: white lighting (bsp version 29)
1206                         out->samples = loadmodel->lightdata + (i * 3);
1207
1208                 Mod_GenerateSurfacePolygon(out);
1209
1210                 if (out->texinfo->texture->flags & SURF_DRAWSKY)
1211                 {
1212                         out->shader = &Cshader_sky;
1213                         Mod_GenerateWarpMesh (out);
1214                         continue;
1215                 }
1216
1217                 if (out->texinfo->texture->flags & SURF_DRAWTURB)
1218                 {
1219                         out->shader = &Cshader_water;
1220                         /*
1221                         for (i=0 ; i<2 ; i++)
1222                         {
1223                                 out->extents[i] = 16384*1024;
1224                                 out->texturemins[i] = -8192*1024;
1225                         }
1226                         */
1227                         Mod_GenerateWarpMesh (out);
1228                         continue;
1229                 }
1230
1231                 if (!R_TextureHasAlpha(out->texinfo->texture->texture))
1232                         out->flags |= SURF_CLIPSOLID;
1233                 if (out->texinfo->flags & TEX_SPECIAL)
1234                 {
1235                         // qbsp couldn't find the texture for this surface, but it was either turb or sky...  assume turb
1236                         out->shader = &Cshader_water;
1237                         Mod_GenerateWarpMesh (out);
1238                 }
1239                 else if (out->extents[0] < r_vertexsurfacesthreshold.integer && out->extents[1] < r_vertexsurfacesthreshold.integer)
1240                 {
1241                         out->shader = &Cshader_wall_vertex;
1242                         Mod_GenerateVertexLitMesh(out);
1243                 }
1244                 else
1245                 {
1246                         out->shader = &Cshader_wall_lightmap;
1247                         Mod_GenerateLightmappedMesh(out);
1248                 }
1249         }
1250 }
1251
1252 static model_t *sortmodel;
1253
1254 static int Mod_SurfaceQSortCompare(const void *voida, const void *voidb)
1255 {
1256         const msurface_t *a, *b;
1257         a = *((const msurface_t **)voida);
1258         b = *((const msurface_t **)voidb);
1259         if (a->shader != b->shader)
1260                 return (long) a->shader - (long) b->shader;
1261         if (a->texinfo->texture != b->texinfo->texture);
1262                 return a->texinfo->texture - b->texinfo->texture;
1263         return 0;
1264 }
1265
1266 static void Mod_BrushSortedSurfaces(model_t *model, mempool_t *pool)
1267 {
1268         int surfnum;
1269         sortmodel = model;
1270         sortmodel->modelsortedsurfaces = Mem_Alloc(pool, sortmodel->nummodelsurfaces * sizeof(msurface_t *));
1271         for (surfnum = 0;surfnum < sortmodel->nummodelsurfaces;surfnum++)
1272                 sortmodel->modelsortedsurfaces[surfnum] = &sortmodel->surfaces[surfnum + sortmodel->firstmodelsurface];
1273
1274         qsort(sortmodel->modelsortedsurfaces, sortmodel->nummodelsurfaces, sizeof(msurface_t *), Mod_SurfaceQSortCompare);
1275 }
1276
1277
1278 /*
1279 =================
1280 Mod_SetParent
1281 =================
1282 */
1283 static void Mod_SetParent (mnode_t *node, mnode_t *parent)
1284 {
1285         node->parent = parent;
1286         if (node->contents < 0)
1287                 return;
1288         Mod_SetParent (node->children[0], node);
1289         Mod_SetParent (node->children[1], node);
1290 }
1291
1292 /*
1293 =================
1294 Mod_LoadNodes
1295 =================
1296 */
1297 static void Mod_LoadNodes (lump_t *l)
1298 {
1299         int                     i, j, count, p;
1300         dnode_t         *in;
1301         mnode_t         *out;
1302
1303         in = (void *)(mod_base + l->fileofs);
1304         if (l->filelen % sizeof(*in))
1305                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1306         count = l->filelen / sizeof(*in);
1307         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1308
1309         loadmodel->nodes = out;
1310         loadmodel->numnodes = count;
1311
1312         for ( i=0 ; i<count ; i++, in++, out++)
1313         {
1314                 for (j=0 ; j<3 ; j++)
1315                 {
1316                         out->mins[j] = LittleShort (in->mins[j]);
1317                         out->maxs[j] = LittleShort (in->maxs[j]);
1318                 }
1319
1320                 p = LittleLong(in->planenum);
1321                 out->plane = loadmodel->planes + p;
1322
1323                 out->firstsurface = LittleShort (in->firstface);
1324                 out->numsurfaces = LittleShort (in->numfaces);
1325
1326                 for (j=0 ; j<2 ; j++)
1327                 {
1328                         p = LittleShort (in->children[j]);
1329                         if (p >= 0)
1330                                 out->children[j] = loadmodel->nodes + p;
1331                         else
1332                                 out->children[j] = (mnode_t *)(loadmodel->leafs + (-1 - p));
1333                 }
1334         }
1335
1336         Mod_SetParent (loadmodel->nodes, NULL); // sets nodes and leafs
1337 }
1338
1339 /*
1340 =================
1341 Mod_LoadLeafs
1342 =================
1343 */
1344 static void Mod_LoadLeafs (lump_t *l)
1345 {
1346         dleaf_t         *in;
1347         mleaf_t         *out;
1348         int                     i, j, count, p;
1349
1350         in = (void *)(mod_base + l->fileofs);
1351         if (l->filelen % sizeof(*in))
1352                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1353         count = l->filelen / sizeof(*in);
1354         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1355
1356         loadmodel->leafs = out;
1357         loadmodel->numleafs = count;
1358
1359         for ( i=0 ; i<count ; i++, in++, out++)
1360         {
1361                 for (j=0 ; j<3 ; j++)
1362                 {
1363                         out->mins[j] = LittleShort (in->mins[j]);
1364                         out->maxs[j] = LittleShort (in->maxs[j]);
1365                 }
1366
1367                 p = LittleLong(in->contents);
1368                 out->contents = p;
1369
1370                 out->firstmarksurface = loadmodel->marksurfaces +
1371                         LittleShort(in->firstmarksurface);
1372                 out->nummarksurfaces = LittleShort(in->nummarksurfaces);
1373
1374                 p = LittleLong(in->visofs);
1375                 if (p == -1)
1376                         out->compressed_vis = NULL;
1377                 else
1378                         out->compressed_vis = loadmodel->visdata + p;
1379
1380                 for (j=0 ; j<4 ; j++)
1381                         out->ambient_sound_level[j] = in->ambient_level[j];
1382
1383                 // gl underwater warp
1384                 // LordHavoc: disabled underwater warping
1385                 /*
1386                 if (out->contents != CONTENTS_EMPTY)
1387                 {
1388                         for (j=0 ; j<out->nummarksurfaces ; j++)
1389                                 out->firstmarksurface[j]->flags |= SURF_UNDERWATER;
1390                 }
1391                 */
1392         }
1393 }
1394
1395 /*
1396 =================
1397 Mod_LoadClipnodes
1398 =================
1399 */
1400 static void Mod_LoadClipnodes (lump_t *l)
1401 {
1402         dclipnode_t *in, *out;
1403         int                     i, count;
1404         hull_t          *hull;
1405
1406         in = (void *)(mod_base + l->fileofs);
1407         if (l->filelen % sizeof(*in))
1408                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1409         count = l->filelen / sizeof(*in);
1410         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1411
1412         loadmodel->clipnodes = out;
1413         loadmodel->numclipnodes = count;
1414
1415         if (loadmodel->ishlbsp)
1416         {
1417                 hull = &loadmodel->hulls[1];
1418                 hull->clipnodes = out;
1419                 hull->firstclipnode = 0;
1420                 hull->lastclipnode = count-1;
1421                 hull->planes = loadmodel->planes;
1422                 hull->clip_mins[0] = -16;
1423                 hull->clip_mins[1] = -16;
1424                 hull->clip_mins[2] = -36;
1425                 hull->clip_maxs[0] = 16;
1426                 hull->clip_maxs[1] = 16;
1427                 hull->clip_maxs[2] = 36;
1428
1429                 hull = &loadmodel->hulls[2];
1430                 hull->clipnodes = out;
1431                 hull->firstclipnode = 0;
1432                 hull->lastclipnode = count-1;
1433                 hull->planes = loadmodel->planes;
1434                 hull->clip_mins[0] = -32;
1435                 hull->clip_mins[1] = -32;
1436                 hull->clip_mins[2] = -32;
1437                 hull->clip_maxs[0] = 32;
1438                 hull->clip_maxs[1] = 32;
1439                 hull->clip_maxs[2] = 32;
1440
1441                 hull = &loadmodel->hulls[3];
1442                 hull->clipnodes = out;
1443                 hull->firstclipnode = 0;
1444                 hull->lastclipnode = count-1;
1445                 hull->planes = loadmodel->planes;
1446                 hull->clip_mins[0] = -16;
1447                 hull->clip_mins[1] = -16;
1448                 hull->clip_mins[2] = -18;
1449                 hull->clip_maxs[0] = 16;
1450                 hull->clip_maxs[1] = 16;
1451                 hull->clip_maxs[2] = 18;
1452         }
1453         else
1454         {
1455                 hull = &loadmodel->hulls[1];
1456                 hull->clipnodes = out;
1457                 hull->firstclipnode = 0;
1458                 hull->lastclipnode = count-1;
1459                 hull->planes = loadmodel->planes;
1460                 hull->clip_mins[0] = -16;
1461                 hull->clip_mins[1] = -16;
1462                 hull->clip_mins[2] = -24;
1463                 hull->clip_maxs[0] = 16;
1464                 hull->clip_maxs[1] = 16;
1465                 hull->clip_maxs[2] = 32;
1466
1467                 hull = &loadmodel->hulls[2];
1468                 hull->clipnodes = out;
1469                 hull->firstclipnode = 0;
1470                 hull->lastclipnode = count-1;
1471                 hull->planes = loadmodel->planes;
1472                 hull->clip_mins[0] = -32;
1473                 hull->clip_mins[1] = -32;
1474                 hull->clip_mins[2] = -24;
1475                 hull->clip_maxs[0] = 32;
1476                 hull->clip_maxs[1] = 32;
1477                 hull->clip_maxs[2] = 64;
1478         }
1479
1480         for (i=0 ; i<count ; i++, out++, in++)
1481         {
1482                 out->planenum = LittleLong(in->planenum);
1483                 out->children[0] = LittleShort(in->children[0]);
1484                 out->children[1] = LittleShort(in->children[1]);
1485                 if (out->children[0] >= count || out->children[1] >= count)
1486                         Host_Error("Corrupt clipping hull (out of range child)\n");
1487         }
1488 }
1489
1490 /*
1491 =================
1492 Mod_MakeHull0
1493
1494 Duplicate the drawing hull structure as a clipping hull
1495 =================
1496 */
1497 static void Mod_MakeHull0 (void)
1498 {
1499         mnode_t         *in;
1500         dclipnode_t *out;
1501         int                     i;
1502         hull_t          *hull;
1503
1504         hull = &loadmodel->hulls[0];
1505
1506         in = loadmodel->nodes;
1507         out = Mem_Alloc(loadmodel->mempool, loadmodel->numnodes * sizeof(dclipnode_t));
1508
1509         hull->clipnodes = out;
1510         hull->firstclipnode = 0;
1511         hull->lastclipnode = loadmodel->numnodes - 1;
1512         hull->planes = loadmodel->planes;
1513
1514         for (i = 0;i < loadmodel->numnodes;i++, out++, in++)
1515         {
1516                 out->planenum = in->plane - loadmodel->planes;
1517                 out->children[0] = in->children[0]->contents < 0 ? in->children[0]->contents : in->children[0] - loadmodel->nodes;
1518                 out->children[1] = in->children[1]->contents < 0 ? in->children[1]->contents : in->children[1] - loadmodel->nodes;
1519         }
1520 }
1521
1522 /*
1523 =================
1524 Mod_LoadMarksurfaces
1525 =================
1526 */
1527 static void Mod_LoadMarksurfaces (lump_t *l)
1528 {
1529         int             i, j;
1530         short   *in;
1531
1532         in = (void *)(mod_base + l->fileofs);
1533         if (l->filelen % sizeof(*in))
1534                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1535         loadmodel->nummarksurfaces = l->filelen / sizeof(*in);
1536         loadmodel->marksurfaces = Mem_Alloc(loadmodel->mempool, loadmodel->nummarksurfaces * sizeof(msurface_t *));
1537
1538         for (i = 0;i < loadmodel->nummarksurfaces;i++)
1539         {
1540                 j = (unsigned) LittleShort(in[i]);
1541                 if (j >= loadmodel->numsurfaces)
1542                         Host_Error ("Mod_ParseMarksurfaces: bad surface number");
1543                 loadmodel->marksurfaces[i] = loadmodel->surfaces + j;
1544         }
1545 }
1546
1547 /*
1548 =================
1549 Mod_LoadSurfedges
1550 =================
1551 */
1552 static void Mod_LoadSurfedges (lump_t *l)
1553 {
1554         int             i;
1555         int             *in;
1556
1557         in = (void *)(mod_base + l->fileofs);
1558         if (l->filelen % sizeof(*in))
1559                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1560         loadmodel->numsurfedges = l->filelen / sizeof(*in);
1561         loadmodel->surfedges = Mem_Alloc(loadmodel->mempool, loadmodel->numsurfedges * sizeof(int));
1562
1563         for (i = 0;i < loadmodel->numsurfedges;i++)
1564                 loadmodel->surfedges[i] = LittleLong (in[i]);
1565 }
1566
1567
1568 /*
1569 =================
1570 Mod_LoadPlanes
1571 =================
1572 */
1573 static void Mod_LoadPlanes (lump_t *l)
1574 {
1575         int                     i;
1576         mplane_t        *out;
1577         dplane_t        *in;
1578
1579         in = (void *)(mod_base + l->fileofs);
1580         if (l->filelen % sizeof(*in))
1581                 Host_Error ("MOD_LoadBmodel: funny lump size in %s", loadmodel->name);
1582
1583         loadmodel->numplanes = l->filelen / sizeof(*in);
1584         loadmodel->planes = out = Mem_Alloc(loadmodel->mempool, loadmodel->numplanes * sizeof(*out));
1585
1586         for (i = 0;i < loadmodel->numplanes;i++, in++, out++)
1587         {
1588                 out->normal[0] = LittleFloat (in->normal[0]);
1589                 out->normal[1] = LittleFloat (in->normal[1]);
1590                 out->normal[2] = LittleFloat (in->normal[2]);
1591                 out->dist = LittleFloat (in->dist);
1592
1593                 // LordHavoc: recalculated by PlaneClassify, FIXME: validate type and report error if type does not match normal?
1594 //              out->type = LittleLong (in->type);
1595                 PlaneClassify(out);
1596         }
1597 }
1598
1599 #define MAX_POINTS_ON_WINDING 64
1600
1601 typedef struct
1602 {
1603         int numpoints;
1604         double points[8][3]; // variable sized
1605 }
1606 winding_t;
1607
1608 typedef struct
1609 {
1610         int numpoints;
1611 }
1612 windingsizeof_t;
1613
1614 /*
1615 ==================
1616 NewWinding
1617 ==================
1618 */
1619 static winding_t *NewWinding (int points)
1620 {
1621         winding_t *w;
1622         int size;
1623
1624         if (points > MAX_POINTS_ON_WINDING)
1625                 Host_Error("NewWinding: too many points\n");
1626
1627         size = sizeof(windingsizeof_t) + sizeof(double[3]) * points;
1628         w = Mem_Alloc(tempmempool, size);
1629         memset (w, 0, size);
1630
1631         return w;
1632 }
1633
1634 static void FreeWinding (winding_t *w)
1635 {
1636         Mem_Free(w);
1637 }
1638
1639 /*
1640 =================
1641 BaseWindingForPlane
1642 =================
1643 */
1644 static winding_t *BaseWindingForPlane (mplane_t *p)
1645 {
1646         double org[3], vright[3], vup[3], normal[3];
1647         winding_t *w;
1648
1649         VectorCopy(p->normal, normal);
1650         VectorVectorsDouble(normal, vright, vup);
1651
1652         VectorScale (vup, 1024.0*1024.0*1024.0, vup);
1653         VectorScale (vright, 1024.0*1024.0*1024.0, vright);
1654
1655         // project a really big axis aligned box onto the plane
1656         w = NewWinding (4);
1657
1658         VectorScale (p->normal, p->dist, org);
1659
1660         VectorSubtract (org, vright, w->points[0]);
1661         VectorAdd (w->points[0], vup, w->points[0]);
1662
1663         VectorAdd (org, vright, w->points[1]);
1664         VectorAdd (w->points[1], vup, w->points[1]);
1665
1666         VectorAdd (org, vright, w->points[2]);
1667         VectorSubtract (w->points[2], vup, w->points[2]);
1668
1669         VectorSubtract (org, vright, w->points[3]);
1670         VectorSubtract (w->points[3], vup, w->points[3]);
1671
1672         w->numpoints = 4;
1673
1674         return w;
1675 }
1676
1677 /*
1678 ==================
1679 ClipWinding
1680
1681 Clips the winding to the plane, returning the new winding on the positive side
1682 Frees the input winding.
1683 If keepon is true, an exactly on-plane winding will be saved, otherwise
1684 it will be clipped away.
1685 ==================
1686 */
1687 static winding_t *ClipWinding (winding_t *in, mplane_t *split, int keepon)
1688 {
1689         double  dists[MAX_POINTS_ON_WINDING + 1];
1690         int             sides[MAX_POINTS_ON_WINDING + 1];
1691         int             counts[3];
1692         double  dot;
1693         int             i, j;
1694         double  *p1, *p2;
1695         double  mid[3];
1696         winding_t       *neww;
1697         int             maxpts;
1698
1699         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
1700
1701         // determine sides for each point
1702         for (i = 0;i < in->numpoints;i++)
1703         {
1704                 dists[i] = dot = DotProduct (in->points[i], split->normal) - split->dist;
1705                 if (dot > ON_EPSILON)
1706                         sides[i] = SIDE_FRONT;
1707                 else if (dot < -ON_EPSILON)
1708                         sides[i] = SIDE_BACK;
1709                 else
1710                         sides[i] = SIDE_ON;
1711                 counts[sides[i]]++;
1712         }
1713         sides[i] = sides[0];
1714         dists[i] = dists[0];
1715
1716         if (keepon && !counts[0] && !counts[1])
1717                 return in;
1718
1719         if (!counts[0])
1720         {
1721                 FreeWinding (in);
1722                 return NULL;
1723         }
1724         if (!counts[1])
1725                 return in;
1726
1727         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
1728         neww = NewWinding (maxpts);
1729
1730         for (i = 0;i < in->numpoints;i++)
1731         {
1732                 p1 = in->points[i];
1733
1734                 if (sides[i] == SIDE_ON)
1735                 {
1736                         VectorCopy (p1, neww->points[neww->numpoints]);
1737                         neww->numpoints++;
1738                         continue;
1739                 }
1740
1741                 if (sides[i] == SIDE_FRONT)
1742                 {
1743                         VectorCopy (p1, neww->points[neww->numpoints]);
1744                         neww->numpoints++;
1745                 }
1746
1747                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1748                         continue;
1749
1750                 // generate a split point
1751                 p2 = in->points[(i+1)%in->numpoints];
1752
1753                 dot = dists[i] / (dists[i]-dists[i+1]);
1754                 for (j = 0;j < 3;j++)
1755                 {       // avoid round off error when possible
1756                         if (split->normal[j] == 1)
1757                                 mid[j] = split->dist;
1758                         else if (split->normal[j] == -1)
1759                                 mid[j] = -split->dist;
1760                         else
1761                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1762                 }
1763
1764                 VectorCopy (mid, neww->points[neww->numpoints]);
1765                 neww->numpoints++;
1766         }
1767
1768         if (neww->numpoints > maxpts)
1769                 Host_Error ("ClipWinding: points exceeded estimate");
1770
1771         // free the original winding
1772         FreeWinding (in);
1773
1774         return neww;
1775 }
1776
1777
1778 /*
1779 ==================
1780 DivideWinding
1781
1782 Divides a winding by a plane, producing one or two windings.  The
1783 original winding is not damaged or freed.  If only on one side, the
1784 returned winding will be the input winding.  If on both sides, two
1785 new windings will be created.
1786 ==================
1787 */
1788 static void DivideWinding (winding_t *in, mplane_t *split, winding_t **front, winding_t **back)
1789 {
1790         double  dists[MAX_POINTS_ON_WINDING + 1];
1791         int             sides[MAX_POINTS_ON_WINDING + 1];
1792         int             counts[3];
1793         double  dot;
1794         int             i, j;
1795         double  *p1, *p2;
1796         double  mid[3];
1797         winding_t       *f, *b;
1798         int             maxpts;
1799
1800         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
1801
1802         // determine sides for each point
1803         for (i = 0;i < in->numpoints;i++)
1804         {
1805                 dot = DotProduct (in->points[i], split->normal);
1806                 dot -= split->dist;
1807                 dists[i] = dot;
1808                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
1809                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
1810                 else sides[i] = SIDE_ON;
1811                 counts[sides[i]]++;
1812         }
1813         sides[i] = sides[0];
1814         dists[i] = dists[0];
1815
1816         *front = *back = NULL;
1817
1818         if (!counts[0])
1819         {
1820                 *back = in;
1821                 return;
1822         }
1823         if (!counts[1])
1824         {
1825                 *front = in;
1826                 return;
1827         }
1828
1829         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
1830
1831         *front = f = NewWinding (maxpts);
1832         *back = b = NewWinding (maxpts);
1833
1834         for (i = 0;i < in->numpoints;i++)
1835         {
1836                 p1 = in->points[i];
1837
1838                 if (sides[i] == SIDE_ON)
1839                 {
1840                         VectorCopy (p1, f->points[f->numpoints]);
1841                         f->numpoints++;
1842                         VectorCopy (p1, b->points[b->numpoints]);
1843                         b->numpoints++;
1844                         continue;
1845                 }
1846
1847                 if (sides[i] == SIDE_FRONT)
1848                 {
1849                         VectorCopy (p1, f->points[f->numpoints]);
1850                         f->numpoints++;
1851                 }
1852                 else if (sides[i] == SIDE_BACK)
1853                 {
1854                         VectorCopy (p1, b->points[b->numpoints]);
1855                         b->numpoints++;
1856                 }
1857
1858                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1859                         continue;
1860
1861                 // generate a split point
1862                 p2 = in->points[(i+1)%in->numpoints];
1863
1864                 dot = dists[i] / (dists[i]-dists[i+1]);
1865                 for (j = 0;j < 3;j++)
1866                 {       // avoid round off error when possible
1867                         if (split->normal[j] == 1)
1868                                 mid[j] = split->dist;
1869                         else if (split->normal[j] == -1)
1870                                 mid[j] = -split->dist;
1871                         else
1872                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1873                 }
1874
1875                 VectorCopy (mid, f->points[f->numpoints]);
1876                 f->numpoints++;
1877                 VectorCopy (mid, b->points[b->numpoints]);
1878                 b->numpoints++;
1879         }
1880
1881         if (f->numpoints > maxpts || b->numpoints > maxpts)
1882                 Host_Error ("DivideWinding: points exceeded estimate");
1883 }
1884
1885 typedef struct portal_s
1886 {
1887         mplane_t plane;
1888         mnode_t *nodes[2];              // [0] = front side of plane
1889         struct portal_s *next[2];
1890         winding_t *winding;
1891         struct portal_s *chain; // all portals are linked into a list
1892 }
1893 portal_t;
1894
1895 static portal_t *portalchain;
1896
1897 /*
1898 ===========
1899 AllocPortal
1900 ===========
1901 */
1902 static portal_t *AllocPortal (void)
1903 {
1904         portal_t *p;
1905         p = Mem_Alloc(tempmempool, sizeof(portal_t));
1906         //memset(p, 0, sizeof(portal_t));
1907         p->chain = portalchain;
1908         portalchain = p;
1909         return p;
1910 }
1911
1912 static void FreePortal(portal_t *p)
1913 {
1914         Mem_Free(p);
1915 }
1916
1917 static void Mod_RecursiveRecalcNodeBBox(mnode_t *node)
1918 {
1919         // calculate children first
1920         if (node->children[0]->contents >= 0)
1921                 Mod_RecursiveRecalcNodeBBox(node->children[0]);
1922         if (node->children[1]->contents >= 0)
1923                 Mod_RecursiveRecalcNodeBBox(node->children[1]);
1924
1925         // make combined bounding box from children
1926         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
1927         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
1928         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
1929         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
1930         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
1931         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
1932 }
1933
1934 static void Mod_FinalizePortals(void)
1935 {
1936         int i, j, numportals, numpoints;
1937         portal_t *p, *pnext;
1938         mportal_t *portal;
1939         mvertex_t *point;
1940         mleaf_t *leaf, *endleaf;
1941         winding_t *w;
1942
1943         // recalculate bounding boxes for all leafs (because qbsp is very sloppy)
1944         leaf = loadmodel->leafs;
1945         endleaf = leaf + loadmodel->numleafs;
1946         for (;leaf < endleaf;leaf++)
1947         {
1948                 VectorSet( 2000000000,  2000000000,  2000000000, leaf->mins);
1949                 VectorSet(-2000000000, -2000000000, -2000000000, leaf->maxs);
1950         }
1951         p = portalchain;
1952         while(p)
1953         {
1954                 if (p->winding)
1955                 {
1956                         for (i = 0;i < 2;i++)
1957                         {
1958                                 leaf = (mleaf_t *)p->nodes[i];
1959                                 w = p->winding;
1960                                 for (j = 0;j < w->numpoints;j++)
1961                                 {
1962                                         if (leaf->mins[0] > w->points[j][0]) leaf->mins[0] = w->points[j][0];
1963                                         if (leaf->mins[1] > w->points[j][1]) leaf->mins[1] = w->points[j][1];
1964                                         if (leaf->mins[2] > w->points[j][2]) leaf->mins[2] = w->points[j][2];
1965                                         if (leaf->maxs[0] < w->points[j][0]) leaf->maxs[0] = w->points[j][0];
1966                                         if (leaf->maxs[1] < w->points[j][1]) leaf->maxs[1] = w->points[j][1];
1967                                         if (leaf->maxs[2] < w->points[j][2]) leaf->maxs[2] = w->points[j][2];
1968                                 }
1969                         }
1970                 }
1971                 p = p->chain;
1972         }
1973
1974         Mod_RecursiveRecalcNodeBBox(loadmodel->nodes);
1975
1976         // tally up portal and point counts
1977         p = portalchain;
1978         numportals = 0;
1979         numpoints = 0;
1980         while(p)
1981         {
1982                 // note: this check must match the one below or it will usually corrupt memory
1983                 // 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
1984                 if (p->winding && p->nodes[0] != p->nodes[1]
1985                  && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
1986                  && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
1987                 {
1988                         numportals += 2;
1989                         numpoints += p->winding->numpoints * 2;
1990                 }
1991                 p = p->chain;
1992         }
1993         loadmodel->portals = Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
1994         loadmodel->numportals = numportals;
1995         loadmodel->portalpoints = (void *) ((long) loadmodel->portals + numportals * sizeof(mportal_t));
1996         loadmodel->numportalpoints = numpoints;
1997         // clear all leaf portal chains
1998         for (i = 0;i < loadmodel->numleafs;i++)
1999                 loadmodel->leafs[i].portals = NULL;
2000         // process all portals in the global portal chain, while freeing them
2001         portal = loadmodel->portals;
2002         point = loadmodel->portalpoints;
2003         p = portalchain;
2004         portalchain = NULL;
2005         while (p)
2006         {
2007                 pnext = p->chain;
2008
2009                 if (p->winding)
2010                 {
2011                         // note: this check must match the one above or it will usually corrupt memory
2012                         // 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
2013                         if (p->nodes[0] != p->nodes[1]
2014                          && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2015                          && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2016                         {
2017                                 // first make the back to front portal (forward portal)
2018                                 portal->points = point;
2019                                 portal->numpoints = p->winding->numpoints;
2020                                 portal->plane.dist = p->plane.dist;
2021                                 VectorCopy(p->plane.normal, portal->plane.normal);
2022                                 portal->here = (mleaf_t *)p->nodes[1];
2023                                 portal->past = (mleaf_t *)p->nodes[0];
2024                                 // copy points
2025                                 for (j = 0;j < portal->numpoints;j++)
2026                                 {
2027                                         VectorCopy(p->winding->points[j], point->position);
2028                                         point++;
2029                                 }
2030                                 PlaneClassify(&portal->plane);
2031
2032                                 // link into leaf's portal chain
2033                                 portal->next = portal->here->portals;
2034                                 portal->here->portals = portal;
2035
2036                                 // advance to next portal
2037                                 portal++;
2038
2039                                 // then make the front to back portal (backward portal)
2040                                 portal->points = point;
2041                                 portal->numpoints = p->winding->numpoints;
2042                                 portal->plane.dist = -p->plane.dist;
2043                                 VectorNegate(p->plane.normal, portal->plane.normal);
2044                                 portal->here = (mleaf_t *)p->nodes[0];
2045                                 portal->past = (mleaf_t *)p->nodes[1];
2046                                 // copy points
2047                                 for (j = portal->numpoints - 1;j >= 0;j--)
2048                                 {
2049                                         VectorCopy(p->winding->points[j], point->position);
2050                                         point++;
2051                                 }
2052                                 PlaneClassify(&portal->plane);
2053
2054                                 // link into leaf's portal chain
2055                                 portal->next = portal->here->portals;
2056                                 portal->here->portals = portal;
2057
2058                                 // advance to next portal
2059                                 portal++;
2060                         }
2061                         FreeWinding(p->winding);
2062                 }
2063                 FreePortal(p);
2064                 p = pnext;
2065         }
2066 }
2067
2068 /*
2069 =============
2070 AddPortalToNodes
2071 =============
2072 */
2073 static void AddPortalToNodes (portal_t *p, mnode_t *front, mnode_t *back)
2074 {
2075         if (!front)
2076                 Host_Error ("AddPortalToNodes: NULL front node");
2077         if (!back)
2078                 Host_Error ("AddPortalToNodes: NULL back node");
2079         if (p->nodes[0] || p->nodes[1])
2080                 Host_Error ("AddPortalToNodes: already included");
2081         // 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
2082
2083         p->nodes[0] = front;
2084         p->next[0] = (portal_t *)front->portals;
2085         front->portals = (mportal_t *)p;
2086
2087         p->nodes[1] = back;
2088         p->next[1] = (portal_t *)back->portals;
2089         back->portals = (mportal_t *)p;
2090 }
2091
2092 /*
2093 =============
2094 RemovePortalFromNode
2095 =============
2096 */
2097 static void RemovePortalFromNodes(portal_t *portal)
2098 {
2099         int i;
2100         mnode_t *node;
2101         void **portalpointer;
2102         portal_t *t;
2103         for (i = 0;i < 2;i++)
2104         {
2105                 node = portal->nodes[i];
2106
2107                 portalpointer = (void **) &node->portals;
2108                 while (1)
2109                 {
2110                         t = *portalpointer;
2111                         if (!t)
2112                                 Host_Error ("RemovePortalFromNodes: portal not in leaf");
2113
2114                         if (t == portal)
2115                         {
2116                                 if (portal->nodes[0] == node)
2117                                 {
2118                                         *portalpointer = portal->next[0];
2119                                         portal->nodes[0] = NULL;
2120                                 }
2121                                 else if (portal->nodes[1] == node)
2122                                 {
2123                                         *portalpointer = portal->next[1];
2124                                         portal->nodes[1] = NULL;
2125                                 }
2126                                 else
2127                                         Host_Error ("RemovePortalFromNodes: portal not bounding leaf");
2128                                 break;
2129                         }
2130
2131                         if (t->nodes[0] == node)
2132                                 portalpointer = (void **) &t->next[0];
2133                         else if (t->nodes[1] == node)
2134                                 portalpointer = (void **) &t->next[1];
2135                         else
2136                                 Host_Error ("RemovePortalFromNodes: portal not bounding leaf");
2137                 }
2138         }
2139 }
2140
2141 static void Mod_RecursiveNodePortals (mnode_t *node)
2142 {
2143         int side;
2144         mnode_t *front, *back, *other_node;
2145         mplane_t clipplane, *plane;
2146         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2147         winding_t *nodeportalwinding, *frontwinding, *backwinding;
2148
2149         //      CheckLeafPortalConsistancy (node);
2150
2151         // if a leaf, we're done
2152         if (node->contents)
2153                 return;
2154
2155         plane = node->plane;
2156
2157         front = node->children[0];
2158         back = node->children[1];
2159         if (front == back)
2160                 Host_Error("Mod_RecursiveNodePortals: corrupt node hierarchy");
2161
2162         // create the new portal by generating a polygon for the node plane,
2163         // and clipping it by all of the other portals (which came from nodes above this one)
2164         nodeportal = AllocPortal ();
2165         nodeportal->plane = *node->plane;
2166
2167         nodeportalwinding = BaseWindingForPlane (node->plane);
2168         side = 0;       // shut up compiler warning
2169         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2170         {
2171                 clipplane = portal->plane;
2172                 if (portal->nodes[0] == portal->nodes[1])
2173                         Host_Error("Mod_RecursiveNodePortals: portal has same node on both sides (1)");
2174                 if (portal->nodes[0] == node)
2175                         side = 0;
2176                 else if (portal->nodes[1] == node)
2177                 {
2178                         clipplane.dist = -clipplane.dist;
2179                         VectorNegate (clipplane.normal, clipplane.normal);
2180                         side = 1;
2181                 }
2182                 else
2183                         Host_Error ("Mod_RecursiveNodePortals: mislinked portal");
2184
2185                 nodeportalwinding = ClipWinding (nodeportalwinding, &clipplane, true);
2186                 if (!nodeportalwinding)
2187                 {
2188                         printf ("Mod_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2189                         break;
2190                 }
2191         }
2192
2193         if (nodeportalwinding)
2194         {
2195                 // if the plane was not clipped on all sides, there was an error
2196                 nodeportal->winding = nodeportalwinding;
2197                 AddPortalToNodes (nodeportal, front, back);
2198         }
2199
2200         // split the portals of this node along this node's plane and assign them to the children of this node
2201         // (migrating the portals downward through the tree)
2202         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2203         {
2204                 if (portal->nodes[0] == portal->nodes[1])
2205                         Host_Error("Mod_RecursiveNodePortals: portal has same node on both sides (2)");
2206                 if (portal->nodes[0] == node)
2207                         side = 0;
2208                 else if (portal->nodes[1] == node)
2209                         side = 1;
2210                 else
2211                         Host_Error ("Mod_RecursiveNodePortals: mislinked portal");
2212                 nextportal = portal->next[side];
2213
2214                 other_node = portal->nodes[!side];
2215                 RemovePortalFromNodes (portal);
2216
2217                 // cut the portal into two portals, one on each side of the node plane
2218                 DivideWinding (portal->winding, plane, &frontwinding, &backwinding);
2219
2220                 if (!frontwinding)
2221                 {
2222                         if (side == 0)
2223                                 AddPortalToNodes (portal, back, other_node);
2224                         else
2225                                 AddPortalToNodes (portal, other_node, back);
2226                         continue;
2227                 }
2228                 if (!backwinding)
2229                 {
2230                         if (side == 0)
2231                                 AddPortalToNodes (portal, front, other_node);
2232                         else
2233                                 AddPortalToNodes (portal, other_node, front);
2234                         continue;
2235                 }
2236
2237                 // the winding is split
2238                 splitportal = AllocPortal ();
2239                 temp = splitportal->chain;
2240                 *splitportal = *portal;
2241                 splitportal->chain = temp;
2242                 splitportal->winding = backwinding;
2243                 FreeWinding (portal->winding);
2244                 portal->winding = frontwinding;
2245
2246                 if (side == 0)
2247                 {
2248                         AddPortalToNodes (portal, front, other_node);
2249                         AddPortalToNodes (splitportal, back, other_node);
2250                 }
2251                 else
2252                 {
2253                         AddPortalToNodes (portal, other_node, front);
2254                         AddPortalToNodes (splitportal, other_node, back);
2255                 }
2256         }
2257
2258         Mod_RecursiveNodePortals(front);
2259         Mod_RecursiveNodePortals(back);
2260 }
2261
2262 /*
2263 void Mod_MakeOutsidePortals(mnode_t *node)
2264 {
2265         int                     i, j;
2266         portal_t        *p, *portals[6];
2267         mnode_t         *outside_node;
2268
2269         outside_node = Mem_Alloc(loadmodel->mempool, sizeof(mnode_t));
2270         outside_node->contents = CONTENTS_SOLID;
2271         outside_node->portals = NULL;
2272
2273         for (i = 0;i < 3;i++)
2274         {
2275                 for (j = 0;j < 2;j++)
2276                 {
2277                         portals[j*3 + i] = p = AllocPortal ();
2278                         memset (&p->plane, 0, sizeof(mplane_t));
2279                         p->plane.normal[i] = j ? -1 : 1;
2280                         p->plane.dist = -65536;
2281                         p->winding = BaseWindingForPlane (&p->plane);
2282                         if (j)
2283                                 AddPortalToNodes (p, outside_node, node);
2284                         else
2285                                 AddPortalToNodes (p, node, outside_node);
2286                 }
2287         }
2288
2289         // clip the basewindings by all the other planes
2290         for (i = 0;i < 6;i++)
2291         {
2292                 for (j = 0;j < 6;j++)
2293                 {
2294                         if (j == i)
2295                                 continue;
2296                         portals[i]->winding = ClipWinding (portals[i]->winding, &portals[j]->plane, true);
2297                 }
2298         }
2299 }
2300 */
2301
2302 static void Mod_MakePortals(void)
2303 {
2304 //      Con_Printf("building portals for %s\n", loadmodel->name);
2305
2306         portalchain = NULL;
2307 //      Mod_MakeOutsidePortals (loadmodel->nodes);
2308         Mod_RecursiveNodePortals (loadmodel->nodes);
2309         Mod_FinalizePortals();
2310 }
2311
2312 /*
2313 =================
2314 Mod_LoadBrushModel
2315 =================
2316 */
2317 void Mod_LoadBrushModel (model_t *mod, void *buffer)
2318 {
2319         int                     i, j;
2320         dheader_t       *header;
2321         dmodel_t        *bm;
2322         mempool_t       *mainmempool;
2323
2324         mod->type = mod_brush;
2325
2326         header = (dheader_t *)buffer;
2327
2328         i = LittleLong (header->version);
2329         if (i != BSPVERSION && i != 30)
2330                 Host_Error ("Mod_LoadBrushModel: %s has wrong version number (%i should be %i or 30 (HalfLife))", mod->name, i, BSPVERSION);
2331         mod->ishlbsp = i == 30;
2332         if (loadmodel->isworldmodel)
2333                 Cvar_SetValue("halflifebsp", mod->ishlbsp);
2334
2335 // swap all the lumps
2336         mod_base = (byte *)header;
2337
2338         for (i=0 ; i<sizeof(dheader_t)/4 ; i++)
2339                 ((int *)header)[i] = LittleLong ( ((int *)header)[i]);
2340
2341 // load into heap
2342
2343         // store which lightmap format to use
2344         mod->lightmaprgba = r_lightmaprgba.integer;
2345
2346 //      Mem_CheckSentinelsGlobal();
2347         // LordHavoc: had to move entity loading above everything to allow parsing various settings from worldspawn
2348         Mod_LoadEntities (&header->lumps[LUMP_ENTITIES]);
2349 //      Mem_CheckSentinelsGlobal();
2350         Mod_LoadVertexes (&header->lumps[LUMP_VERTEXES]);
2351 //      Mem_CheckSentinelsGlobal();
2352         Mod_LoadEdges (&header->lumps[LUMP_EDGES]);
2353 //      Mem_CheckSentinelsGlobal();
2354         Mod_LoadSurfedges (&header->lumps[LUMP_SURFEDGES]);
2355 //      Mem_CheckSentinelsGlobal();
2356         Mod_LoadTextures (&header->lumps[LUMP_TEXTURES]);
2357 //      Mem_CheckSentinelsGlobal();
2358         Mod_LoadLighting (&header->lumps[LUMP_LIGHTING]);
2359 //      Mem_CheckSentinelsGlobal();
2360         Mod_LoadPlanes (&header->lumps[LUMP_PLANES]);
2361 //      Mem_CheckSentinelsGlobal();
2362         Mod_LoadTexinfo (&header->lumps[LUMP_TEXINFO]);
2363 //      Mem_CheckSentinelsGlobal();
2364         Mod_LoadFaces (&header->lumps[LUMP_FACES]);
2365 //      Mem_CheckSentinelsGlobal();
2366         Mod_LoadMarksurfaces (&header->lumps[LUMP_MARKSURFACES]);
2367 //      Mem_CheckSentinelsGlobal();
2368         Mod_LoadVisibility (&header->lumps[LUMP_VISIBILITY]);
2369 //      Mem_CheckSentinelsGlobal();
2370         Mod_LoadLeafs (&header->lumps[LUMP_LEAFS]);
2371 //      Mem_CheckSentinelsGlobal();
2372         Mod_LoadNodes (&header->lumps[LUMP_NODES]);
2373 //      Mem_CheckSentinelsGlobal();
2374         Mod_LoadClipnodes (&header->lumps[LUMP_CLIPNODES]);
2375 //      Mem_CheckSentinelsGlobal();
2376 //      Mod_LoadEntities (&header->lumps[LUMP_ENTITIES]);
2377         Mod_LoadSubmodels (&header->lumps[LUMP_MODELS]);
2378 //      Mem_CheckSentinelsGlobal();
2379
2380         Mod_MakeHull0 ();
2381 //      Mem_CheckSentinelsGlobal();
2382         Mod_MakePortals();
2383 //      Mem_CheckSentinelsGlobal();
2384
2385         mod->numframes = 2;             // regular and alternate animation
2386
2387         mainmempool = mod->mempool;
2388
2389 //
2390 // set up the submodels (FIXME: this is confusing)
2391 //
2392         for (i = 0;i < mod->numsubmodels;i++)
2393         {
2394                 int k, l;
2395                 float dist, modelyawradius, modelradius, *vec;
2396                 msurface_t *surf;
2397
2398                 mod->normalmins[0] = mod->normalmins[1] = mod->normalmins[2] = 1000000000.0f;
2399                 mod->normalmaxs[0] = mod->normalmaxs[1] = mod->normalmaxs[2] = -1000000000.0f;
2400                 modelyawradius = 0;
2401                 modelradius = 0;
2402
2403                 bm = &mod->submodels[i];
2404
2405                 mod->hulls[0].firstclipnode = bm->headnode[0];
2406                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
2407                 {
2408                         mod->hulls[j].firstclipnode = bm->headnode[j];
2409                         mod->hulls[j].lastclipnode = mod->numclipnodes - 1;
2410                 }
2411
2412                 mod->firstmodelsurface = bm->firstface;
2413                 mod->nummodelsurfaces = bm->numfaces;
2414
2415                 mod->DrawSky = NULL;
2416                 // LordHavoc: calculate bmodel bounding box rather than trusting what it says
2417                 for (j = 0, surf = &mod->surfaces[mod->firstmodelsurface];j < mod->nummodelsurfaces;j++, surf++)
2418                 {
2419                         // we only need to have a drawsky function if it is used (usually only on world model)
2420                         if (surf->shader == &Cshader_sky)
2421                                 mod->DrawSky = R_DrawBrushModelSky;
2422                         for (k = 0;k < surf->numedges;k++)
2423                         {
2424                                 l = mod->surfedges[k + surf->firstedge];
2425                                 if (l > 0)
2426                                         vec = mod->vertexes[mod->edges[l].v[0]].position;
2427                                 else
2428                                         vec = mod->vertexes[mod->edges[-l].v[1]].position;
2429                                 if (mod->normalmins[0] > vec[0]) mod->normalmins[0] = vec[0];
2430                                 if (mod->normalmins[1] > vec[1]) mod->normalmins[1] = vec[1];
2431                                 if (mod->normalmins[2] > vec[2]) mod->normalmins[2] = vec[2];
2432                                 if (mod->normalmaxs[0] < vec[0]) mod->normalmaxs[0] = vec[0];
2433                                 if (mod->normalmaxs[1] < vec[1]) mod->normalmaxs[1] = vec[1];
2434                                 if (mod->normalmaxs[2] < vec[2]) mod->normalmaxs[2] = vec[2];
2435                                 dist = vec[0]*vec[0]+vec[1]*vec[1];
2436                                 if (modelyawradius < dist)
2437                                         modelyawradius = dist;
2438                                 dist += vec[2]*vec[2];
2439                                 if (modelradius < dist)
2440                                         modelradius = dist;
2441                         }
2442                 }
2443                 modelyawradius = sqrt(modelyawradius);
2444                 modelradius = sqrt(modelradius);
2445                 mod->yawmins[0] = mod->yawmins[1] = -(mod->yawmaxs[0] = mod->yawmaxs[1] = modelyawradius);
2446                 mod->yawmins[2] = mod->normalmins[2];
2447                 mod->yawmaxs[2] = mod->normalmaxs[2];
2448                 mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
2449                 mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
2450 //              mod->modelradius = modelradius;
2451
2452 //              VectorCopy (bm->maxs, mod->maxs);
2453 //              VectorCopy (bm->mins, mod->mins);
2454
2455 //              mod->radius = RadiusFromBounds (mod->mins, mod->maxs);
2456
2457                 mod->numleafs = bm->visleafs;
2458
2459                 mod->SERAddEntity = Mod_Brush_SERAddEntity;
2460                 mod->Draw = R_DrawBrushModelNormal;
2461                 mod->DrawShadow = NULL;
2462
2463                 Mod_BrushSortedSurfaces(mod, mainmempool);
2464
2465                 // LordHavoc: only register submodels if it is the world
2466                 // (prevents bsp models from replacing world submodels)
2467                 if (loadmodel->isworldmodel && i < (mod->numsubmodels - 1))
2468                 {
2469                         char    name[10];
2470                         // duplicate the basic information
2471                         sprintf (name, "*%i", i+1);
2472                         loadmodel = Mod_FindName (name);
2473                         *loadmodel = *mod;
2474                         strcpy (loadmodel->name, name);
2475                         // textures and memory belong to the main model
2476                         loadmodel->texturepool = NULL;
2477                         loadmodel->mempool = NULL;
2478                         mod = loadmodel;
2479                 }
2480         }
2481 //      Mem_CheckSentinelsGlobal();
2482 }