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