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