added CVAR_SAVE and CVAR_NOTIFY flags to cvar_t structure (at the beginning), updated...
[divverent/darkplaces.git] / model_brush.c
1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19 */
20
21 #include "quakedef.h"
22
23 byte    mod_novis[MAX_MAP_LEAFS/8];
24
25 qboolean        hlbsp; // LordHavoc: true if it is a HalfLife BSP file (version 30)
26
27 cvar_t gl_subdivide_size = {CVAR_SAVE, "gl_subdivide_size", "128"};
28 cvar_t halflifebsp = {0, "halflifebsp", "0"};
29 cvar_t r_novis = {0, "r_novis", "0"};
30
31 /*
32 ===============
33 Mod_BrushInit
34 ===============
35 */
36 void Mod_BrushInit (void)
37 {
38         Cvar_RegisterVariable (&gl_subdivide_size);
39         Cvar_RegisterVariable (&halflifebsp);
40         Cvar_RegisterVariable (&r_novis);
41         memset (mod_novis, 0xff, sizeof(mod_novis));
42 }
43
44 /*
45 ===============
46 Mod_PointInLeaf
47 ===============
48 */
49 mleaf_t *Mod_PointInLeaf (vec3_t p, model_t *model)
50 {
51         mnode_t         *node;
52         
53 //      if (!model || !model->nodes)
54 //              Sys_Error ("Mod_PointInLeaf: bad model");
55
56         node = model->nodes;
57         do
58                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct (p,node->plane->normal)) < node->plane->dist];
59         while (node->contents == 0);
60
61         return (mleaf_t *)node;
62 }
63 /*
64 mleaf_t *Mod_PointInLeaf (vec3_t p, model_t *model)
65 {
66         mnode_t         *node;
67         float           d;
68         mplane_t        *plane;
69         
70         if (!model || !model->nodes)
71                 Sys_Error ("Mod_PointInLeaf: bad model");
72
73         node = model->nodes;
74         while (1)
75         {
76                 if (node->contents < 0)
77                         return (mleaf_t *)node;
78                 plane = node->plane;
79                 d = DotProduct (p,plane->normal) - plane->dist;
80                 if (d > 0)
81                         node = node->children[0];
82                 else
83                         node = node->children[1];
84         }
85         
86         return NULL;    // never reached
87 }
88 */
89
90 /*
91 ===================
92 Mod_DecompressVis
93 ===================
94 */
95 byte *Mod_DecompressVis (byte *in, model_t *model)
96 {
97         static byte     decompressed[MAX_MAP_LEAFS/8];
98         int             c;
99         byte    *out;
100         int             row;
101
102         row = (model->numleafs+7)>>3;
103         out = decompressed;
104
105         /*
106         if (!in)
107         {       // no vis info, so make all visible
108                 while (row)
109                 {
110                         *out++ = 0xff;
111                         row--;
112                 }
113                 return decompressed;            
114         }
115         */
116
117         do
118         {
119                 if (*in)
120                 {
121                         *out++ = *in++;
122                         continue;
123                 }
124         
125                 c = in[1];
126                 in += 2;
127                 while (c)
128                 {
129                         *out++ = 0;
130                         c--;
131                 }
132         } while (out - decompressed < row);
133         
134         return decompressed;
135 }
136
137 byte *Mod_LeafPVS (mleaf_t *leaf, model_t *model)
138 {
139         if (r_novis.value || leaf == model->leafs || leaf->compressed_vis == NULL)
140                 return mod_novis;
141         return Mod_DecompressVis (leaf->compressed_vis, model);
142 }
143
144 rtexture_t *r_notexture;
145 texture_t r_notexture_mip;
146
147 void Mod_SetupNoTexture(void)
148 {
149         int             x, y;
150         byte    pix[16][16][4];
151
152         // create a simple checkerboard texture for the default
153         // LordHavoc: redesigned this to remove reliance on the palette and texture_t
154         for (y = 0;y < 16;y++)
155         {
156                 for (x = 0;x < 16;x++)
157                 {
158                         if ((y < 8) ^ (x < 8))
159                         {
160                                 pix[y][x][0] = 128;
161                                 pix[y][x][1] = 128;
162                                 pix[y][x][2] = 128;
163                                 pix[y][x][3] = 255;
164                         }
165                         else
166                         {
167                                 pix[y][x][0] = 64;
168                                 pix[y][x][1] = 64;
169                                 pix[y][x][2] = 64;
170                                 pix[y][x][3] = 255;
171                         }
172                 }
173         }
174
175         r_notexture = R_LoadTexture("notexture", 16, 16, &pix[0][0][0], TEXF_MIPMAP | TEXF_RGBA);
176
177         strcpy(r_notexture_mip.name, "notexture");
178         r_notexture_mip.width = 16;
179         r_notexture_mip.height = 16;
180         r_notexture_mip.transparent = false;
181         r_notexture_mip.texture = r_notexture;
182         r_notexture_mip.glowtexture = NULL;
183 }
184
185 /*
186 =================
187 Mod_LoadTextures
188 =================
189 */
190 void Mod_LoadTextures (lump_t *l)
191 {
192         int                             i, j, k, num, max, altmax, mtwidth, mtheight, *dofs;
193         miptex_t                *dmiptex;
194         texture_t               *tx, *tx2, *anims[10], *altanims[10];
195         dmiptexlump_t   *m;
196         byte                    *data, *mtdata;
197
198         if (!l->filelen)
199         {
200                 loadmodel->textures = NULL;
201                 return;
202         }
203
204         m = (dmiptexlump_t *)(mod_base + l->fileofs);
205         
206         m->nummiptex = LittleLong (m->nummiptex);
207         
208         loadmodel->numtextures = m->nummiptex;
209         loadmodel->textures = Hunk_AllocName (m->nummiptex * sizeof(*loadmodel->textures), va("%s texture headers", loadname));
210
211         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
212         dofs = m->dataofs;
213         for (i = 0;i < m->nummiptex;i++)
214         {
215                 dofs[i] = LittleLong(dofs[i]);
216                 if (dofs[i] == -1)
217                         continue;
218                 dmiptex = (miptex_t *)((byte *)m + dofs[i]);
219                 mtwidth = LittleLong (dmiptex->width);
220                 mtheight = LittleLong (dmiptex->height);
221                 mtdata = NULL;
222                 j = LittleLong (dmiptex->offsets[0]);
223                 if (j)
224                 {
225                         // texture included
226                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
227                                 Host_Error ("Texture %s is corrupt or incomplete\n", dmiptex->name);
228                         mtdata = (byte *)dmiptex + j;
229                 }
230                 
231                 if ((mtwidth & 15) || (mtheight & 15))
232                         Host_Error ("Texture %s is not 16 aligned", dmiptex->name);
233                 // LordHavoc: rewriting the map texture loader for GLQuake
234                 tx = Hunk_AllocName (sizeof(texture_t), va("%s textures", loadname));
235                 loadmodel->textures[i] = tx;
236
237                 // LordHavoc: force all names to lowercase and make sure they are terminated while copying
238                 for (j = 0;dmiptex->name[j] && j < 15;j++)
239                 {
240                         if (dmiptex->name[j] >= 'A' && dmiptex->name[j] <= 'Z')
241                                 tx->name[j] = dmiptex->name[j] + ('a' - 'A');
242                         else
243                                 tx->name[j] = dmiptex->name[j];
244                 }
245                 for (;j < 16;j++)
246                         tx->name[j] = 0;
247
248                 if (!tx->name[0])
249                 {
250                         Con_Printf("warning: unnamed texture in %s\n", loadname);
251                         sprintf(tx->name, "unnamed%i", i);
252                 }
253
254                 tx->transparent = false;
255                 data = loadimagepixels(tx->name, false, 0, 0);
256                 if (data)
257                 {
258                         if (!hlbsp && !strncmp(tx->name,"sky",3) && image_width == 256 && image_height == 128) // LordHavoc: HL sky textures are entirely unrelated
259                         {
260                                 tx->width = 0;
261                                 tx->height = 0;
262                                 tx->transparent = false;
263                                 tx->texture = NULL;
264                                 tx->glowtexture = NULL;
265                                 R_InitSky (data, 4);
266                         }
267                         else
268                         {
269                                 tx->width = mtwidth;
270                                 tx->height = mtheight;
271                                 tx->transparent = Image_CheckAlpha(data, image_width * image_height, true);
272                                 tx->texture = R_LoadTexture (tx->name, image_width, image_height, data, TEXF_MIPMAP | (tx->transparent ? TEXF_ALPHA : 0) | TEXF_RGBA | TEXF_PRECACHE);
273                                 tx->glowtexture = NULL;
274                         }
275                         qfree(data);
276                 }
277                 else
278                 {
279                         if (hlbsp)
280                         {
281                                 if (mtdata) // texture included
282                                 {
283                                         data = W_ConvertWAD3Texture(dmiptex);
284                                         if (data)
285                                         {
286                                                 tx->width = mtwidth;
287                                                 tx->height = mtheight;
288                                                 tx->transparent = Image_CheckAlpha(data, mtwidth * mtheight, true);
289                                                 tx->texture = R_LoadTexture (tx->name, mtwidth, mtheight, data, TEXF_MIPMAP | (tx->transparent ? TEXF_ALPHA : 0) | TEXF_RGBA | TEXF_PRECACHE);
290                                                 tx->glowtexture = NULL;
291                                                 qfree(data);
292                                         }
293                                 }
294                                 if (!data)
295                                 {
296                                         data = W_GetTexture(tx->name);
297                                         // get the size from the wad texture
298                                         if (data)
299                                         {
300                                                 tx->width = image_width;
301                                                 tx->height = image_height;
302                                                 tx->transparent = Image_CheckAlpha(data, image_width * image_height, true);
303                                                 tx->texture = R_LoadTexture (tx->name, image_width, image_height, data, TEXF_MIPMAP | (tx->transparent ? TEXF_ALPHA : 0) | TEXF_RGBA | TEXF_PRECACHE);
304                                                 tx->glowtexture = NULL;
305                                                 qfree(data);
306                                         }
307                                 }
308                                 if (!data)
309                                 {
310                                         tx->width = 16;
311                                         tx->height = 16;
312                                         tx->transparent = false;
313                                         tx->texture = r_notexture;
314                                         tx->glowtexture = NULL;
315                                 }
316                         }
317                         else
318                         {
319                                 if (!strncmp(tx->name,"sky",3) && mtwidth == 256 && mtheight == 128)
320                                 {
321                                         tx->width = mtwidth;
322                                         tx->height = mtheight;
323                                         tx->transparent = false;
324                                         tx->texture = NULL;
325                                         tx->glowtexture = NULL;
326                                         R_InitSky (mtdata, 1);
327                                 }
328                                 else
329                                 {
330                                         if (mtdata) // texture included
331                                         {
332                                                 int fullbrights;
333                                                 data = mtdata;
334                                                 tx->width = mtwidth;
335                                                 tx->height = mtheight;
336                                                 tx->transparent = false;
337                                                 fullbrights = false;
338                                                 if (r_fullbrights.value && tx->name[0] != '*')
339                                                 {
340                                                         for (j = 0;j < tx->width*tx->height;j++)
341                                                         {
342                                                                 if (data[j] >= 224) // fullbright
343                                                                 {
344                                                                         fullbrights = true;
345                                                                         break;
346                                                                 }
347                                                         }
348                                                 }
349                                                 if (fullbrights)
350                                                 {
351                                                         char name[64];
352                                                         byte *data2;
353                                                         data2 = qmalloc(tx->width*tx->height);
354                                                         for (j = 0;j < tx->width*tx->height;j++)
355                                                                 data2[j] = data[j] >= 224 ? 0 : data[j]; // no fullbrights
356                                                         tx->texture = R_LoadTexture (tx->name, tx->width, tx->height, data2, TEXF_MIPMAP | TEXF_PRECACHE);
357                                                         strcpy(name, tx->name);
358                                                         strcat(name, "_glow");
359                                                         for (j = 0;j < tx->width*tx->height;j++)
360                                                                 data2[j] = data[j] >= 224 ? data[j] : 0; // only fullbrights
361                                                         tx->glowtexture = R_LoadTexture (name, tx->width, tx->height, data2, TEXF_MIPMAP | TEXF_PRECACHE);
362                                                         qfree(data2);
363                                                 }
364                                                 else
365                                                 {
366                                                         tx->texture = R_LoadTexture (tx->name, tx->width, tx->height, data, TEXF_MIPMAP | TEXF_PRECACHE);
367                                                         tx->glowtexture = NULL;
368                                                 }
369                                         }
370                                         else // no texture, and no external replacement texture was found
371                                         {
372                                                 tx->width = 16;
373                                                 tx->height = 16;
374                                                 tx->transparent = false;
375                                                 tx->texture = r_notexture;
376                                                 tx->glowtexture = NULL;
377                                         }
378                                 }
379                         }
380                 }
381         }
382
383 //
384 // sequence the animations
385 //
386         for (i = 0;i < m->nummiptex;i++)
387         {
388                 tx = loadmodel->textures[i];
389                 if (!tx || tx->name[0] != '+')
390                         continue;
391                 if (tx->anim_total)
392                         continue;       // already sequenced
393
394                 // find the number of frames in the animation
395                 memset (anims, 0, sizeof(anims));
396                 memset (altanims, 0, sizeof(altanims));
397
398                 max = tx->name[1];
399                 altmax = 0;
400                 if (max >= '0' && max <= '9')
401                 {
402                         max -= '0';
403                         altmax = 0;
404                         anims[max] = tx;
405                         max++;
406                 }
407                 else if (max >= 'a' && max <= 'j')
408                 {
409                         altmax = max - 'a';
410                         max = 0;
411                         altanims[altmax] = tx;
412                         altmax++;
413                 }
414                 else
415                         Host_Error ("Bad animating texture %s", tx->name);
416
417                 for (j = i + 1;j < m->nummiptex;j++)
418                 {
419                         tx2 = loadmodel->textures[j];
420                         if (!tx2 || tx2->name[0] != '+')
421                                 continue;
422                         if (strcmp (tx2->name+2, tx->name+2))
423                                 continue;
424
425                         num = tx2->name[1];
426                         if (num >= '0' && num <= '9')
427                         {
428                                 num -= '0';
429                                 anims[num] = tx2;
430                                 if (num+1 > max)
431                                         max = num + 1;
432                         }
433                         else if (num >= 'a' && num <= 'j')
434                         {
435                                 num = num - 'a';
436                                 altanims[num] = tx2;
437                                 if (num+1 > altmax)
438                                         altmax = num+1;
439                         }
440                         else
441                                 Host_Error ("Bad animating texture %s", tx->name);
442                 }
443
444                 // link them all together
445                 for (j = 0;j < max;j++)
446                 {
447                         tx2 = anims[j];
448                         if (!tx2)
449                                 Host_Error ("Missing frame %i of %s", j, tx->name);
450                         tx2->anim_total = max;
451                         if (altmax)
452                                 tx2->alternate_anims = altanims[0];
453                         for (k = 0;k < 10;k++)
454                                 tx2->anim_frames[k] = anims[j];
455                 }
456                 for (j = 0;j < altmax;j++)
457                 {
458                         tx2 = altanims[j];
459                         if (!tx2)
460                                 Host_Error ("Missing frame %i of %s", j, tx->name);
461                         tx2->anim_total = altmax;
462                         if (max)
463                                 tx2->alternate_anims = anims[0];
464                         for (k = 0;k < 10;k++)
465                                 tx2->anim_frames[k] = altanims[j];
466                 }
467         }
468 }
469
470 /*
471 =================
472 Mod_LoadLighting
473 =================
474 */
475 void Mod_LoadLighting (lump_t *l)
476 {
477         int i;
478         byte *in, *out, *data;
479         byte d;
480         char litfilename[1024];
481         loadmodel->lightdata = NULL;
482         if (hlbsp) // LordHavoc: load the colored lighting data straight
483         {
484                 loadmodel->lightdata = Hunk_AllocName ( l->filelen, va("%s lightmaps", loadname));
485                 memcpy (loadmodel->lightdata, mod_base + l->fileofs, l->filelen);
486         }
487         else // LordHavoc: bsp version 29 (normal white lighting)
488         {
489                 // LordHavoc: hope is not lost yet, check for a .lit file to load
490                 strcpy(litfilename, loadmodel->name);
491                 COM_StripExtension(litfilename, litfilename);
492                 strcat(litfilename, ".lit");
493                 data = (byte*) COM_LoadHunkFile (litfilename, false);
494                 if (data)
495                 {
496                         if (data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
497                         {
498                                 i = LittleLong(((int *)data)[1]);
499                                 if (i == 1)
500                                 {
501                                         Con_DPrintf("%s loaded", litfilename);
502                                         loadmodel->lightdata = data + 8;
503                                         return;
504                                 }
505                                 else
506                                         Con_Printf("Unknown .lit file version (%d)\n", i);
507                         }
508                         else
509                                 Con_Printf("Corrupt .lit file (old version?), ignoring\n");
510                 }
511                 // LordHavoc: oh well, expand the white lighting data
512                 if (!l->filelen)
513                         return;
514                 loadmodel->lightdata = Hunk_AllocName ( l->filelen*3, va("%s lightmaps", loadname));
515                 in = loadmodel->lightdata + l->filelen*2; // place the file at the end, so it will not be overwritten until the very last write
516                 out = loadmodel->lightdata;
517                 memcpy (in, mod_base + l->fileofs, l->filelen);
518                 for (i = 0;i < l->filelen;i++)
519                 {
520                         d = *in++;
521                         *out++ = d;
522                         *out++ = d;
523                         *out++ = d;
524                 }
525         }
526 }
527
528
529 /*
530 =================
531 Mod_LoadVisibility
532 =================
533 */
534 void Mod_LoadVisibility (lump_t *l)
535 {
536         if (!l->filelen)
537         {
538                 loadmodel->visdata = NULL;
539                 return;
540         }
541         loadmodel->visdata = Hunk_AllocName ( l->filelen, va("%s visdata", loadname));
542         memcpy (loadmodel->visdata, mod_base + l->fileofs, l->filelen);
543 }
544
545 /*
546 =================
547 Mod_LoadEntities
548 =================
549 */
550 void Mod_LoadEntities (lump_t *l)
551 {
552         if (!l->filelen)
553         {
554                 loadmodel->entities = NULL;
555                 return;
556         }
557         loadmodel->entities = Hunk_AllocName ( l->filelen, va("%s entities", loadname));
558         memcpy (loadmodel->entities, mod_base + l->fileofs, l->filelen);
559
560         if (isworldmodel)
561                 CL_ParseEntityLump(loadmodel->entities);
562 }
563
564
565 /*
566 =================
567 Mod_LoadVertexes
568 =================
569 */
570 void Mod_LoadVertexes (lump_t *l)
571 {
572         dvertex_t       *in;
573         mvertex_t       *out;
574         int                     i, count;
575
576         in = (void *)(mod_base + l->fileofs);
577         if (l->filelen % sizeof(*in))
578                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
579         count = l->filelen / sizeof(*in);
580         out = Hunk_AllocName ( count*sizeof(*out), va("%s vertices", loadname));
581
582         loadmodel->vertexes = out;
583         loadmodel->numvertexes = count;
584
585         for ( i=0 ; i<count ; i++, in++, out++)
586         {
587                 out->position[0] = LittleFloat (in->point[0]);
588                 out->position[1] = LittleFloat (in->point[1]);
589                 out->position[2] = LittleFloat (in->point[2]);
590         }
591 }
592
593 /*
594 =================
595 Mod_LoadSubmodels
596 =================
597 */
598 void Mod_LoadSubmodels (lump_t *l)
599 {
600         dmodel_t        *in;
601         dmodel_t        *out;
602         int                     i, j, count;
603
604         in = (void *)(mod_base + l->fileofs);
605         if (l->filelen % sizeof(*in))
606                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
607         count = l->filelen / sizeof(*in);
608         out = Hunk_AllocName ( count*sizeof(*out), va("%s submodels", loadname));
609
610         loadmodel->submodels = out;
611         loadmodel->numsubmodels = count;
612
613         for ( i=0 ; i<count ; i++, in++, out++)
614         {
615                 for (j=0 ; j<3 ; j++)
616                 {       // spread the mins / maxs by a pixel
617                         out->mins[j] = LittleFloat (in->mins[j]) - 1;
618                         out->maxs[j] = LittleFloat (in->maxs[j]) + 1;
619                         out->origin[j] = LittleFloat (in->origin[j]);
620                 }
621                 for (j=0 ; j<MAX_MAP_HULLS ; j++)
622                         out->headnode[j] = LittleLong (in->headnode[j]);
623                 out->visleafs = LittleLong (in->visleafs);
624                 out->firstface = LittleLong (in->firstface);
625                 out->numfaces = LittleLong (in->numfaces);
626         }
627 }
628
629 /*
630 =================
631 Mod_LoadEdges
632 =================
633 */
634 void Mod_LoadEdges (lump_t *l)
635 {
636         dedge_t *in;
637         medge_t *out;
638         int     i, count;
639
640         in = (void *)(mod_base + l->fileofs);
641         if (l->filelen % sizeof(*in))
642                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
643         count = l->filelen / sizeof(*in);
644         out = Hunk_AllocName ( (count + 1) * sizeof(*out), va("%s edges", loadname));
645
646         loadmodel->edges = out;
647         loadmodel->numedges = count;
648
649         for ( i=0 ; i<count ; i++, in++, out++)
650         {
651                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
652                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
653         }
654 }
655
656 /*
657 =================
658 Mod_LoadTexinfo
659 =================
660 */
661 void Mod_LoadTexinfo (lump_t *l)
662 {
663         texinfo_t *in;
664         mtexinfo_t *out;
665         int     i, j, k, count;
666         int             miptex;
667
668         in = (void *)(mod_base + l->fileofs);
669         if (l->filelen % sizeof(*in))
670                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
671         count = l->filelen / sizeof(*in);
672         out = Hunk_AllocName ( count*sizeof(*out), va("%s texinfo", loadname));
673
674         loadmodel->texinfo = out;
675         loadmodel->numtexinfo = count;
676
677         for ( i=0 ; i<count ; i++, in++, out++)
678         {
679                 for (k=0 ; k<2 ; k++)
680                         for (j=0 ; j<4 ; j++)
681                                 out->vecs[k][j] = LittleFloat (in->vecs[k][j]);
682
683                 miptex = LittleLong (in->miptex);
684                 out->flags = LittleLong (in->flags);
685         
686                 if (!loadmodel->textures)
687                 {
688                         out->texture = &r_notexture_mip;        // checkerboard texture
689                         out->flags = 0;
690                 }
691                 else
692                 {
693                         if (miptex >= loadmodel->numtextures)
694                                 Host_Error ("miptex >= loadmodel->numtextures");
695                         out->texture = loadmodel->textures[miptex];
696                         if (!out->texture)
697                         {
698                                 out->texture = &r_notexture_mip; // checkerboard texture
699                                 out->flags = 0;
700                         }
701                 }
702         }
703 }
704
705 /*
706 ================
707 CalcSurfaceExtents
708
709 Fills in s->texturemins[] and s->extents[]
710 ================
711 */
712 void CalcSurfaceExtents (msurface_t *s)
713 {
714         float   mins[2], maxs[2], val;
715         int             i,j, e;
716         mvertex_t       *v;
717         mtexinfo_t      *tex;
718         int             bmins[2], bmaxs[2];
719
720         mins[0] = mins[1] = 999999;
721         maxs[0] = maxs[1] = -99999;
722
723         tex = s->texinfo;
724         
725         for (i=0 ; i<s->numedges ; i++)
726         {
727                 e = loadmodel->surfedges[s->firstedge+i];
728                 if (e >= 0)
729                         v = &loadmodel->vertexes[loadmodel->edges[e].v[0]];
730                 else
731                         v = &loadmodel->vertexes[loadmodel->edges[-e].v[1]];
732                 
733                 for (j=0 ; j<2 ; j++)
734                 {
735                         val = v->position[0] * tex->vecs[j][0] + 
736                                 v->position[1] * tex->vecs[j][1] +
737                                 v->position[2] * tex->vecs[j][2] +
738                                 tex->vecs[j][3];
739                         if (val < mins[j])
740                                 mins[j] = val;
741                         if (val > maxs[j])
742                                 maxs[j] = val;
743                 }
744         }
745
746         for (i=0 ; i<2 ; i++)
747         {       
748                 bmins[i] = floor(mins[i]/16);
749                 bmaxs[i] = ceil(maxs[i]/16);
750
751                 s->texturemins[i] = bmins[i] * 16;
752                 s->extents[i] = (bmaxs[i] - bmins[i]) * 16;
753 //              if ( !(tex->flags & TEX_SPECIAL) && s->extents[i] > 512)
754                 if ((tex->flags & TEX_SPECIAL) == 0 && (s->extents[i]+1) > (256*16))
755                         Host_Error ("Bad surface extents");
756         }
757 }
758
759 void GL_SubdivideSurface (msurface_t *fa);
760
761 /*
762 =================
763 Mod_LoadFaces
764 =================
765 */
766 void Mod_LoadFaces (lump_t *l)
767 {
768         dface_t         *in;
769         msurface_t      *out;
770         int                     i, count, surfnum;
771         int                     planenum, side;
772
773         in = (void *)(mod_base + l->fileofs);
774         if (l->filelen % sizeof(*in))
775                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
776         count = l->filelen / sizeof(*in);
777         out = Hunk_AllocName ( count*sizeof(*out), va("%s faces", loadname));
778
779         loadmodel->surfaces = out;
780         loadmodel->numsurfaces = count;
781
782         for ( surfnum=0 ; surfnum<count ; surfnum++, in++, out++)
783         {
784                 out->firstedge = LittleLong(in->firstedge);
785                 out->numedges = LittleShort(in->numedges);              
786                 out->flags = 0;
787
788                 planenum = LittleShort(in->planenum);
789                 side = LittleShort(in->side);
790                 if (side)
791                         out->flags |= SURF_PLANEBACK;                   
792
793                 out->plane = loadmodel->planes + planenum;
794
795                 out->texinfo = loadmodel->texinfo + LittleShort (in->texinfo);
796
797                 CalcSurfaceExtents (out);
798                                 
799         // lighting info
800
801                 for (i=0 ; i<MAXLIGHTMAPS ; i++)
802                         out->styles[i] = in->styles[i];
803                 i = LittleLong(in->lightofs);
804                 if (i == -1)
805                         out->samples = NULL;
806                 else if (hlbsp) // LordHavoc: HalfLife map (bsp version 30)
807                         out->samples = loadmodel->lightdata + i;
808                 else // LordHavoc: white lighting (bsp version 29)
809                         out->samples = loadmodel->lightdata + (i * 3); 
810                 
811         // set the drawing flags flag
812                 
813 //              if (!strncmp(out->texinfo->texture->name,"sky",3))      // sky
814                 // LordHavoc: faster check
815                 if ((out->texinfo->texture->name[0] == 's' || out->texinfo->texture->name[0] == 'S')
816                  && (out->texinfo->texture->name[1] == 'k' || out->texinfo->texture->name[1] == 'K')
817                  && (out->texinfo->texture->name[2] == 'y' || out->texinfo->texture->name[2] == 'Y'))
818                 {
819                         // LordHavoc: for consistency reasons, mark sky as fullbright and solid as well
820                         out->flags |= (SURF_DRAWSKY | SURF_DRAWTILED | SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA | SURF_CLIPSOLID);
821                         GL_SubdivideSurface (out);      // cut up polygon for warps
822                         continue;
823                 }
824                 
825 //              if (!strncmp(out->texinfo->texture->name,"*",1))                // turbulent
826                 if (out->texinfo->texture->name[0] == '*') // LordHavoc: faster check
827                 {
828                         out->flags |= (SURF_DRAWTURB | SURF_DRAWTILED | SURF_LIGHTBOTHSIDES);
829                         // LordHavoc: some turbulent textures should be fullbright and solid
830                         if (!strncmp(out->texinfo->texture->name,"*lava",5)
831                          || !strncmp(out->texinfo->texture->name,"*teleport",9)
832                          || !strncmp(out->texinfo->texture->name,"*rift",5)) // Scourge of Armagon texture
833                                 out->flags |= (SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA);
834                         for (i=0 ; i<2 ; i++)
835                         {
836                                 out->extents[i] = 16384;
837                                 out->texturemins[i] = -8192;
838                         }
839                         GL_SubdivideSurface (out);      // cut up polygon for warps
840                         continue;
841                 }
842                 
843                 out->flags |= SURF_CLIPSOLID;
844         }
845 }
846
847
848 /*
849 =================
850 Mod_SetParent
851 =================
852 */
853 void Mod_SetParent (mnode_t *node, mnode_t *parent)
854 {
855         node->parent = parent;
856         if (node->contents < 0)
857                 return;
858         Mod_SetParent (node->children[0], node);
859         Mod_SetParent (node->children[1], node);
860 }
861
862 /*
863 =================
864 Mod_LoadNodes
865 =================
866 */
867 void Mod_LoadNodes (lump_t *l)
868 {
869         int                     i, j, count, p;
870         dnode_t         *in;
871         mnode_t         *out;
872
873         in = (void *)(mod_base + l->fileofs);
874         if (l->filelen % sizeof(*in))
875                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
876         count = l->filelen / sizeof(*in);
877         out = Hunk_AllocName ( count*sizeof(*out), va("%s nodes", loadname));
878
879         loadmodel->nodes = out;
880         loadmodel->numnodes = count;
881
882         for ( i=0 ; i<count ; i++, in++, out++)
883         {
884 //              for (j=0 ; j<3 ; j++)
885 //              {
886 //                      out->mins[j] = LittleShort (in->mins[j]);
887 //                      out->maxs[j] = LittleShort (in->maxs[j]);
888 //              }
889         
890                 p = LittleLong(in->planenum);
891                 out->plane = loadmodel->planes + p;
892
893                 out->firstsurface = LittleShort (in->firstface);
894                 out->numsurfaces = LittleShort (in->numfaces);
895                 
896                 for (j=0 ; j<2 ; j++)
897                 {
898                         p = LittleShort (in->children[j]);
899                         if (p >= 0)
900                                 out->children[j] = loadmodel->nodes + p;
901                         else
902                                 out->children[j] = (mnode_t *)(loadmodel->leafs + (-1 - p));
903                 }
904         }
905         
906         Mod_SetParent (loadmodel->nodes, NULL); // sets nodes and leafs
907 }
908
909 /*
910 =================
911 Mod_LoadLeafs
912 =================
913 */
914 void Mod_LoadLeafs (lump_t *l)
915 {
916         dleaf_t         *in;
917         mleaf_t         *out;
918         int                     i, j, count, p;
919
920         in = (void *)(mod_base + l->fileofs);
921         if (l->filelen % sizeof(*in))
922                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
923         count = l->filelen / sizeof(*in);
924         out = Hunk_AllocName ( count*sizeof(*out), va("%s leafs", loadname));
925
926         loadmodel->leafs = out;
927         loadmodel->numleafs = count;
928
929         for ( i=0 ; i<count ; i++, in++, out++)
930         {
931                 for (j=0 ; j<3 ; j++)
932                 {
933                         out->mins[j] = LittleShort (in->mins[j]);
934                         out->maxs[j] = LittleShort (in->maxs[j]);
935                 }
936
937                 p = LittleLong(in->contents);
938                 out->contents = p;
939
940                 out->firstmarksurface = loadmodel->marksurfaces +
941                         LittleShort(in->firstmarksurface);
942                 out->nummarksurfaces = LittleShort(in->nummarksurfaces);
943                 
944                 p = LittleLong(in->visofs);
945                 if (p == -1)
946                         out->compressed_vis = NULL;
947                 else
948                         out->compressed_vis = loadmodel->visdata + p;
949                 
950                 for (j=0 ; j<4 ; j++)
951                         out->ambient_sound_level[j] = in->ambient_level[j];
952
953                 // gl underwater warp
954                 // LordHavoc: disabled underwater warping
955                 /*
956                 if (out->contents != CONTENTS_EMPTY)
957                 {
958                         for (j=0 ; j<out->nummarksurfaces ; j++)
959                                 out->firstmarksurface[j]->flags |= SURF_UNDERWATER;
960                 }
961                 */
962         }       
963 }
964
965 /*
966 =================
967 Mod_LoadClipnodes
968 =================
969 */
970 void Mod_LoadClipnodes (lump_t *l)
971 {
972         dclipnode_t *in, *out;
973         int                     i, count;
974         hull_t          *hull;
975
976         in = (void *)(mod_base + l->fileofs);
977         if (l->filelen % sizeof(*in))
978                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
979         count = l->filelen / sizeof(*in);
980         out = Hunk_AllocName ( count*sizeof(*out), va("%s clipnodes", loadname));
981
982         loadmodel->clipnodes = out;
983         loadmodel->numclipnodes = count;
984
985         if (hlbsp)
986         {
987                 hull = &loadmodel->hulls[1];
988                 hull->clipnodes = out;
989                 hull->firstclipnode = 0;
990                 hull->lastclipnode = count-1;
991                 hull->planes = loadmodel->planes;
992                 hull->clip_mins[0] = -16;
993                 hull->clip_mins[1] = -16;
994                 hull->clip_mins[2] = -36;
995                 hull->clip_maxs[0] = 16;
996                 hull->clip_maxs[1] = 16;
997                 hull->clip_maxs[2] = 36;
998
999                 hull = &loadmodel->hulls[2];
1000                 hull->clipnodes = out;
1001                 hull->firstclipnode = 0;
1002                 hull->lastclipnode = count-1;
1003                 hull->planes = loadmodel->planes;
1004                 hull->clip_mins[0] = -32;
1005                 hull->clip_mins[1] = -32;
1006                 hull->clip_mins[2] = -32;
1007                 hull->clip_maxs[0] = 32;
1008                 hull->clip_maxs[1] = 32;
1009                 hull->clip_maxs[2] = 32;
1010
1011                 hull = &loadmodel->hulls[3];
1012                 hull->clipnodes = out;
1013                 hull->firstclipnode = 0;
1014                 hull->lastclipnode = count-1;
1015                 hull->planes = loadmodel->planes;
1016                 hull->clip_mins[0] = -16;
1017                 hull->clip_mins[1] = -16;
1018                 hull->clip_mins[2] = -18;
1019                 hull->clip_maxs[0] = 16;
1020                 hull->clip_maxs[1] = 16;
1021                 hull->clip_maxs[2] = 18;
1022         }
1023         else
1024         {
1025                 hull = &loadmodel->hulls[1];
1026                 hull->clipnodes = out;
1027                 hull->firstclipnode = 0;
1028                 hull->lastclipnode = count-1;
1029                 hull->planes = loadmodel->planes;
1030                 hull->clip_mins[0] = -16;
1031                 hull->clip_mins[1] = -16;
1032                 hull->clip_mins[2] = -24;
1033                 hull->clip_maxs[0] = 16;
1034                 hull->clip_maxs[1] = 16;
1035                 hull->clip_maxs[2] = 32;
1036
1037                 hull = &loadmodel->hulls[2];
1038                 hull->clipnodes = out;
1039                 hull->firstclipnode = 0;
1040                 hull->lastclipnode = count-1;
1041                 hull->planes = loadmodel->planes;
1042                 hull->clip_mins[0] = -32;
1043                 hull->clip_mins[1] = -32;
1044                 hull->clip_mins[2] = -24;
1045                 hull->clip_maxs[0] = 32;
1046                 hull->clip_maxs[1] = 32;
1047                 hull->clip_maxs[2] = 64;
1048         }
1049
1050         for (i=0 ; i<count ; i++, out++, in++)
1051         {
1052                 out->planenum = LittleLong(in->planenum);
1053                 out->children[0] = LittleShort(in->children[0]);
1054                 out->children[1] = LittleShort(in->children[1]);
1055                 if (out->children[0] >= count || out->children[1] >= count)
1056                         Host_Error("Corrupt clipping hull (out of range child)\n");
1057         }
1058 }
1059
1060 /*
1061 =================
1062 Mod_MakeHull0
1063
1064 Duplicate the drawing hull structure as a clipping hull
1065 =================
1066 */
1067 void Mod_MakeHull0 (void)
1068 {
1069         mnode_t         *in;
1070         dclipnode_t *out;
1071         int                     i, count;
1072         hull_t          *hull;
1073         
1074         hull = &loadmodel->hulls[0];    
1075         
1076         in = loadmodel->nodes;
1077         count = loadmodel->numnodes;
1078         out = Hunk_AllocName ( count*sizeof(*out), va("%s hull0", loadname));
1079
1080         hull->clipnodes = out;
1081         hull->firstclipnode = 0;
1082         hull->lastclipnode = count - 1;
1083         hull->planes = loadmodel->planes;
1084
1085         for (i = 0;i < count;i++, out++, in++)
1086         {
1087                 out->planenum = in->plane - loadmodel->planes;
1088                 out->children[0] = in->children[0]->contents < 0 ? in->children[0]->contents : in->children[0] - loadmodel->nodes;
1089                 out->children[1] = in->children[1]->contents < 0 ? in->children[1]->contents : in->children[1] - loadmodel->nodes;
1090         }
1091 }
1092
1093 /*
1094 =================
1095 Mod_LoadMarksurfaces
1096 =================
1097 */
1098 void Mod_LoadMarksurfaces (lump_t *l)
1099 {       
1100         int             i, j, count;
1101         short           *in;
1102         msurface_t **out;
1103         
1104         in = (void *)(mod_base + l->fileofs);
1105         if (l->filelen % sizeof(*in))
1106                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1107         count = l->filelen / sizeof(*in);
1108         out = Hunk_AllocName ( count*sizeof(*out), va("%s marksurfaces", loadname));
1109
1110         loadmodel->marksurfaces = out;
1111         loadmodel->nummarksurfaces = count;
1112
1113         for ( i=0 ; i<count ; i++)
1114         {
1115                 j = LittleShort(in[i]);
1116                 if (j >= loadmodel->numsurfaces)
1117                         Host_Error ("Mod_ParseMarksurfaces: bad surface number");
1118                 out[i] = loadmodel->surfaces + j;
1119         }
1120 }
1121
1122 /*
1123 =================
1124 Mod_LoadSurfedges
1125 =================
1126 */
1127 void Mod_LoadSurfedges (lump_t *l)
1128 {       
1129         int             i, count;
1130         int             *in, *out;
1131         
1132         in = (void *)(mod_base + l->fileofs);
1133         if (l->filelen % sizeof(*in))
1134                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1135         count = l->filelen / sizeof(*in);
1136         out = Hunk_AllocName ( count*sizeof(*out), va("%s surfedges", loadname));
1137
1138         loadmodel->surfedges = out;
1139         loadmodel->numsurfedges = count;
1140
1141         for ( i=0 ; i<count ; i++)
1142                 out[i] = LittleLong (in[i]);
1143 }
1144
1145
1146 /*
1147 =================
1148 Mod_LoadPlanes
1149 =================
1150 */
1151 void Mod_LoadPlanes (lump_t *l)
1152 {
1153         int                     i, j;
1154         mplane_t        *out;
1155         dplane_t        *in;
1156         int                     count;
1157         
1158         in = (void *)(mod_base + l->fileofs);
1159         if (l->filelen % sizeof(*in))
1160                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1161         count = l->filelen / sizeof(*in);
1162         out = Hunk_AllocName ( count*2*sizeof(*out), va("%s planes", loadname));
1163
1164         loadmodel->planes = out;
1165         loadmodel->numplanes = count;
1166
1167         for ( i=0 ; i<count ; i++, in++, out++)
1168         {
1169                 for (j=0 ; j<3 ; j++)
1170                         out->normal[j] = LittleFloat (in->normal[j]);
1171
1172                 out->dist = LittleFloat (in->dist);
1173                 // LordHavoc: recalculated by PlaneClassify, FIXME: validate type and report error if type does not match normal?
1174 //              out->type = LittleLong (in->type);
1175                 PlaneClassify(out);
1176         }
1177 }
1178
1179 #define MAX_POINTS_ON_WINDING 64
1180
1181 typedef struct
1182 {
1183         int numpoints;
1184         vec3_t points[8]; // variable sized
1185 }
1186 winding_t;
1187
1188 /*
1189 ==================
1190 NewWinding
1191 ==================
1192 */
1193 winding_t *NewWinding (int points)
1194 {
1195         winding_t *w;
1196         int size;
1197
1198         if (points > MAX_POINTS_ON_WINDING)
1199                 Host_Error("NewWinding: too many points\n");
1200
1201         size = (int)((winding_t *)0)->points[points];
1202         w = qmalloc (size);
1203         memset (w, 0, size);
1204
1205         return w;
1206 }
1207
1208 void FreeWinding (winding_t *w)
1209 {
1210         qfree (w);
1211 }
1212
1213 /*
1214 =================
1215 BaseWindingForPlane
1216 =================
1217 */
1218 winding_t *BaseWindingForPlane (mplane_t *p)
1219 {
1220         vec3_t  org, vright, vup;
1221         winding_t       *w;
1222
1223         VectorVectors(p->normal, vright, vup);
1224
1225         VectorScale (vup, 65536, vup);
1226         VectorScale (vright, 65536, vright);
1227
1228         // project a really big axis aligned box onto the plane
1229         w = NewWinding (4);
1230
1231         VectorScale (p->normal, p->dist, org);
1232
1233         VectorSubtract (org, vright, w->points[0]);
1234         VectorAdd (w->points[0], vup, w->points[0]);
1235
1236         VectorAdd (org, vright, w->points[1]);
1237         VectorAdd (w->points[1], vup, w->points[1]);
1238
1239         VectorAdd (org, vright, w->points[2]);
1240         VectorSubtract (w->points[2], vup, w->points[2]);
1241
1242         VectorSubtract (org, vright, w->points[3]);
1243         VectorSubtract (w->points[3], vup, w->points[3]);
1244
1245         w->numpoints = 4;
1246
1247         return w;       
1248 }
1249
1250 /*
1251 ==================
1252 ClipWinding
1253
1254 Clips the winding to the plane, returning the new winding on the positive side
1255 Frees the input winding.
1256 If keepon is true, an exactly on-plane winding will be saved, otherwise
1257 it will be clipped away.
1258 ==================
1259 */
1260 winding_t *ClipWinding (winding_t *in, mplane_t *split, int keepon)
1261 {
1262         vec_t   dists[MAX_POINTS_ON_WINDING + 1];
1263         int             sides[MAX_POINTS_ON_WINDING + 1];
1264         int             counts[3];
1265         vec_t   dot;
1266         int             i, j;
1267         vec_t   *p1, *p2;
1268         vec3_t  mid;
1269         winding_t       *neww;
1270         int             maxpts;
1271
1272         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
1273
1274         // determine sides for each point
1275         for (i = 0;i < in->numpoints;i++)
1276         {
1277                 dists[i] = dot = DotProduct (in->points[i], split->normal) - split->dist;
1278                 if (dot > ON_EPSILON)
1279                         sides[i] = SIDE_FRONT;
1280                 else if (dot < -ON_EPSILON)
1281                         sides[i] = SIDE_BACK;
1282                 else
1283                         sides[i] = SIDE_ON;
1284                 counts[sides[i]]++;
1285         }
1286         sides[i] = sides[0];
1287         dists[i] = dists[0];
1288
1289         if (keepon && !counts[0] && !counts[1])
1290                 return in;
1291
1292         if (!counts[0])
1293         {
1294                 FreeWinding (in);
1295                 return NULL;
1296         }
1297         if (!counts[1])
1298                 return in;
1299
1300         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
1301         neww = NewWinding (maxpts);
1302
1303         for (i = 0;i < in->numpoints;i++)
1304         {
1305                 p1 = in->points[i];
1306
1307                 if (sides[i] == SIDE_ON)
1308                 {
1309                         VectorCopy (p1, neww->points[neww->numpoints]);
1310                         neww->numpoints++;
1311                         continue;
1312                 }
1313
1314                 if (sides[i] == SIDE_FRONT)
1315                 {
1316                         VectorCopy (p1, neww->points[neww->numpoints]);
1317                         neww->numpoints++;
1318                 }
1319
1320                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1321                         continue;
1322
1323                 // generate a split point
1324                 p2 = in->points[(i+1)%in->numpoints];
1325
1326                 dot = dists[i] / (dists[i]-dists[i+1]);
1327                 for (j = 0;j < 3;j++)
1328                 {       // avoid round off error when possible
1329                         if (split->normal[j] == 1)
1330                                 mid[j] = split->dist;
1331                         else if (split->normal[j] == -1)
1332                                 mid[j] = -split->dist;
1333                         else
1334                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1335                 }
1336
1337                 VectorCopy (mid, neww->points[neww->numpoints]);
1338                 neww->numpoints++;
1339         }
1340
1341         if (neww->numpoints > maxpts)
1342                 Host_Error ("ClipWinding: points exceeded estimate");
1343
1344         // free the original winding
1345         FreeWinding (in);
1346
1347         return neww;
1348 }
1349
1350
1351 /*
1352 ==================
1353 DivideWinding
1354
1355 Divides a winding by a plane, producing one or two windings.  The
1356 original winding is not damaged or freed.  If only on one side, the
1357 returned winding will be the input winding.  If on both sides, two
1358 new windings will be created.
1359 ==================
1360 */
1361 void DivideWinding (winding_t *in, mplane_t *split, winding_t **front, winding_t **back)
1362 {
1363         vec_t   dists[MAX_POINTS_ON_WINDING + 1];
1364         int             sides[MAX_POINTS_ON_WINDING + 1];
1365         int             counts[3];
1366         vec_t   dot;
1367         int             i, j;
1368         vec_t   *p1, *p2;
1369         vec3_t  mid;
1370         winding_t       *f, *b;
1371         int             maxpts;
1372
1373         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
1374
1375         // determine sides for each point
1376         for (i = 0;i < in->numpoints;i++)
1377         {
1378                 dot = DotProduct (in->points[i], split->normal);
1379                 dot -= split->dist;
1380                 dists[i] = dot;
1381                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
1382                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
1383                 else sides[i] = SIDE_ON;
1384                 counts[sides[i]]++;
1385         }
1386         sides[i] = sides[0];
1387         dists[i] = dists[0];
1388
1389         *front = *back = NULL;
1390
1391         if (!counts[0])
1392         {
1393                 *back = in;
1394                 return;
1395         }
1396         if (!counts[1])
1397         {
1398                 *front = in;
1399                 return;
1400         }
1401
1402         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
1403
1404         *front = f = NewWinding (maxpts);
1405         *back = b = NewWinding (maxpts);
1406
1407         for (i = 0;i < in->numpoints;i++)
1408         {
1409                 p1 = in->points[i];
1410
1411                 if (sides[i] == SIDE_ON)
1412                 {
1413                         VectorCopy (p1, f->points[f->numpoints]);
1414                         f->numpoints++;
1415                         VectorCopy (p1, b->points[b->numpoints]);
1416                         b->numpoints++;
1417                         continue;
1418                 }
1419
1420                 if (sides[i] == SIDE_FRONT)
1421                 {
1422                         VectorCopy (p1, f->points[f->numpoints]);
1423                         f->numpoints++;
1424                 }
1425                 else if (sides[i] == SIDE_BACK)
1426                 {
1427                         VectorCopy (p1, b->points[b->numpoints]);
1428                         b->numpoints++;
1429                 }
1430
1431                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1432                         continue;
1433
1434                 // generate a split point
1435                 p2 = in->points[(i+1)%in->numpoints];
1436
1437                 dot = dists[i] / (dists[i]-dists[i+1]);
1438                 for (j = 0;j < 3;j++)
1439                 {       // avoid round off error when possible
1440                         if (split->normal[j] == 1)
1441                                 mid[j] = split->dist;
1442                         else if (split->normal[j] == -1)
1443                                 mid[j] = -split->dist;
1444                         else
1445                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1446                 }
1447
1448                 VectorCopy (mid, f->points[f->numpoints]);
1449                 f->numpoints++;
1450                 VectorCopy (mid, b->points[b->numpoints]);
1451                 b->numpoints++;
1452         }
1453
1454         if (f->numpoints > maxpts || b->numpoints > maxpts)
1455                 Host_Error ("DivideWinding: points exceeded estimate");
1456 }
1457
1458 typedef struct portal_s
1459 {
1460         mplane_t plane;
1461         mnode_t *nodes[2];              // [0] = front side of plane
1462         struct portal_s *next[2];       
1463         winding_t *winding;
1464         struct portal_s *chain; // all portals are linked into a list
1465 }
1466 portal_t;
1467
1468 static portal_t *portalchain;
1469
1470 /*
1471 ===========
1472 AllocPortal
1473 ===========
1474 */
1475 portal_t *AllocPortal (void)
1476 {
1477         portal_t *p;
1478         p = qmalloc(sizeof(portal_t));
1479         memset(p, 0, sizeof(portal_t));
1480         p->chain = portalchain;
1481         portalchain = p;
1482         return p;
1483 }
1484
1485 void Mod_FinalizePortals(void)
1486 {
1487         int i, j, numportals, numpoints;
1488         portal_t *p, *pnext;
1489         mportal_t *portal;
1490         mvertex_t *point;
1491         mleaf_t *leaf, *endleaf;
1492         winding_t *w;
1493
1494         // recalculate bounding boxes for all leafs (because qbsp is very sloppy)
1495         leaf = loadmodel->leafs;
1496         endleaf = leaf + loadmodel->numleafs;
1497         for (;leaf < endleaf;leaf++)
1498         {
1499                 VectorSet( 2000000000,  2000000000,  2000000000, leaf->mins);
1500                 VectorSet(-2000000000, -2000000000, -2000000000, leaf->maxs);
1501         }
1502         p = portalchain;
1503         while(p)
1504         {
1505                 if (p->winding)
1506                 {
1507                         for (i = 0;i < 2;i++)
1508                         {
1509                                 leaf = (mleaf_t *)p->nodes[i];
1510                                 w = p->winding;
1511                                 for (j = 0;j < w->numpoints;j++)
1512                                 {
1513                                         if (leaf->mins[0] > w->points[j][0]) leaf->mins[0] = w->points[j][0];
1514                                         if (leaf->mins[1] > w->points[j][1]) leaf->mins[1] = w->points[j][1];
1515                                         if (leaf->mins[2] > w->points[j][2]) leaf->mins[2] = w->points[j][2];
1516                                         if (leaf->maxs[0] < w->points[j][0]) leaf->maxs[0] = w->points[j][0];
1517                                         if (leaf->maxs[1] < w->points[j][1]) leaf->maxs[1] = w->points[j][1];
1518                                         if (leaf->maxs[2] < w->points[j][2]) leaf->maxs[2] = w->points[j][2];
1519                                 }
1520                         }
1521                 }
1522                 p = p->chain;
1523         }
1524
1525         // tally up portal and point counts
1526         p = portalchain;
1527         numportals = 0;
1528         numpoints = 0;
1529         while(p)
1530         {
1531                 if (p->winding && p->nodes[0] != p->nodes[1] && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID)
1532                 {
1533                         numportals += 2;
1534                         numpoints += p->winding->numpoints * 2;
1535                 }
1536                 p = p->chain;
1537         }
1538         loadmodel->portals = Hunk_AllocName(numportals * sizeof(mportal_t), va("%s portals", loadmodel->name));
1539         loadmodel->numportals = numportals;
1540         loadmodel->portalpoints = Hunk_AllocName(numpoints * sizeof(mvertex_t), va("%s portals", loadmodel->name));
1541         loadmodel->numportalpoints = numpoints;
1542         // clear all leaf portal chains
1543         for (i = 0;i < loadmodel->numleafs;i++)
1544                 loadmodel->leafs[i].portals = NULL;
1545         // process all portals in the global portal chain, while freeing them
1546         portal = loadmodel->portals;
1547         point = loadmodel->portalpoints;
1548         p = portalchain;
1549         portalchain = NULL;
1550         while (p)
1551         {
1552                 pnext = p->chain;
1553
1554                 if (p->winding)
1555                 {
1556                         // 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
1557                         if (p->nodes[0] != p->nodes[1] && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID)
1558                         {
1559                                 // first make the back to front portal (forward portal)
1560                                 portal->points = point;
1561                                 portal->numpoints = p->winding->numpoints;
1562                                 portal->plane.dist = p->plane.dist;
1563                                 VectorCopy(p->plane.normal, portal->plane.normal);
1564                                 portal->here = (mleaf_t *)p->nodes[1];
1565                                 portal->past = (mleaf_t *)p->nodes[0];
1566                                 // copy points
1567                                 for (j = 0;j < portal->numpoints;j++)
1568                                 {
1569                                         VectorCopy(p->winding->points[j], point->position);
1570                                         point++;
1571                                 }
1572                                 PlaneClassify(&portal->plane);
1573
1574                                 // link into leaf's portal chain
1575                                 portal->next = portal->here->portals;
1576                                 portal->here->portals = portal;
1577
1578                                 // advance to next portal
1579                                 portal++;
1580
1581                                 // then make the front to back portal (backward portal)
1582                                 portal->points = point;
1583                                 portal->numpoints = p->winding->numpoints;
1584                                 portal->plane.dist = -p->plane.dist;
1585                                 VectorNegate(p->plane.normal, portal->plane.normal);
1586                                 portal->here = (mleaf_t *)p->nodes[0];
1587                                 portal->past = (mleaf_t *)p->nodes[1];
1588                                 // copy points
1589                                 for (j = portal->numpoints - 1;j >= 0;j--)
1590                                 {
1591                                         VectorCopy(p->winding->points[j], point->position);
1592                                         point++;
1593                                 }
1594                                 PlaneClassify(&portal->plane);
1595
1596                                 // link into leaf's portal chain
1597                                 portal->next = portal->here->portals;
1598                                 portal->here->portals = portal;
1599
1600                                 // advance to next portal
1601                                 portal++;
1602                         }
1603                         FreeWinding(p->winding);
1604                 }
1605                 qfree(p);
1606                 p = pnext;
1607         }
1608 }
1609
1610 /*
1611 =============
1612 AddPortalToNodes
1613 =============
1614 */
1615 void AddPortalToNodes (portal_t *p, mnode_t *front, mnode_t *back)
1616 {
1617         if (!front)
1618                 Host_Error ("AddPortalToNodes: NULL front node");
1619         if (!back)
1620                 Host_Error ("AddPortalToNodes: NULL back node");
1621         if (p->nodes[0] || p->nodes[1])
1622                 Host_Error ("AddPortalToNodes: already included");
1623         // 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
1624
1625         p->nodes[0] = front;
1626         p->next[0] = (portal_t *)front->portals;
1627         front->portals = (mportal_t *)p;
1628
1629         p->nodes[1] = back;
1630         p->next[1] = (portal_t *)back->portals;
1631         back->portals = (mportal_t *)p;
1632 }
1633
1634 /*
1635 =============
1636 RemovePortalFromNode
1637 =============
1638 */
1639 void RemovePortalFromNodes(portal_t *portal)
1640 {
1641         int i;
1642         mnode_t *node;
1643         void **portalpointer;
1644         portal_t *t;
1645         for (i = 0;i < 2;i++)
1646         {
1647                 node = portal->nodes[i];
1648
1649                 portalpointer = (void **) &node->portals;
1650                 while (1)
1651                 {
1652                         t = *portalpointer;
1653                         if (!t)
1654                                 Host_Error ("RemovePortalFromNodes: portal not in leaf");
1655
1656                         if (t == portal)
1657                         {
1658                                 if (portal->nodes[0] == node)
1659                                 {
1660                                         *portalpointer = portal->next[0];
1661                                         portal->nodes[0] = NULL;
1662                                 }
1663                                 else if (portal->nodes[1] == node)
1664                                 {
1665                                         *portalpointer = portal->next[1];       
1666                                         portal->nodes[1] = NULL;
1667                                 }
1668                                 else
1669                                         Host_Error ("RemovePortalFromNodes: portal not bounding leaf");
1670                                 break;
1671                         }
1672
1673                         if (t->nodes[0] == node)
1674                                 portalpointer = (void **) &t->next[0];
1675                         else if (t->nodes[1] == node)
1676                                 portalpointer = (void **) &t->next[1];
1677                         else
1678                                 Host_Error ("RemovePortalFromNodes: portal not bounding leaf");
1679                 }
1680         }
1681 }
1682
1683 void Mod_RecursiveNodePortals (mnode_t *node)
1684 {
1685         int side;
1686         mnode_t *front, *back, *other_node;
1687         mplane_t clipplane, *plane;
1688         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
1689         winding_t *nodeportalwinding, *frontwinding, *backwinding;
1690
1691         //      CheckLeafPortalConsistancy (node);
1692
1693         // if a leaf, we're done
1694         if (node->contents)
1695                 return;
1696
1697         plane = node->plane;
1698
1699         front = node->children[0];
1700         back = node->children[1];
1701         if (front == back)
1702                 Host_Error("Mod_RecursiveNodePortals: corrupt node hierarchy");
1703
1704         // create the new portal by generating a polygon for the node plane,
1705         // and clipping it by all of the other portals (which came from nodes above this one)
1706         nodeportal = AllocPortal ();
1707         nodeportal->plane = *node->plane;
1708
1709         nodeportalwinding = BaseWindingForPlane (node->plane);
1710         side = 0;       // shut up compiler warning
1711         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])     
1712         {
1713                 clipplane = portal->plane;
1714                 if (portal->nodes[0] == portal->nodes[1])
1715                         Host_Error("Mod_RecursiveNodePortals: portal has same node on both sides (1)");
1716                 if (portal->nodes[0] == node)
1717                         side = 0;
1718                 else if (portal->nodes[1] == node)
1719                 {
1720                         clipplane.dist = -clipplane.dist;
1721                         VectorNegate (clipplane.normal, clipplane.normal);
1722                         side = 1;
1723                 }
1724                 else
1725                         Host_Error ("Mod_RecursiveNodePortals: mislinked portal");
1726
1727                 nodeportalwinding = ClipWinding (nodeportalwinding, &clipplane, true);
1728                 if (!nodeportalwinding)
1729                 {
1730                         printf ("Mod_RecursiveNodePortals: WARNING: new portal was clipped away\n");
1731                         break;
1732                 }
1733         }
1734
1735         if (nodeportalwinding)
1736         {
1737                 // if the plane was not clipped on all sides, there was an error
1738                 nodeportal->winding = nodeportalwinding;
1739                 AddPortalToNodes (nodeportal, front, back);
1740         }
1741
1742         // split the portals of this node along this node's plane and assign them to the children of this node
1743         // (migrating the portals downward through the tree)
1744         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
1745         {
1746                 if (portal->nodes[0] == portal->nodes[1])
1747                         Host_Error("Mod_RecursiveNodePortals: portal has same node on both sides (2)");
1748                 if (portal->nodes[0] == node)
1749                         side = 0;
1750                 else if (portal->nodes[1] == node)
1751                         side = 1;
1752                 else
1753                         Host_Error ("Mod_RecursiveNodePortals: mislinked portal");
1754                 nextportal = portal->next[side];
1755
1756                 other_node = portal->nodes[!side];
1757                 RemovePortalFromNodes (portal);
1758
1759                 // cut the portal into two portals, one on each side of the node plane
1760                 DivideWinding (portal->winding, plane, &frontwinding, &backwinding);
1761
1762                 if (!frontwinding)
1763                 {
1764                         if (side == 0)
1765                                 AddPortalToNodes (portal, back, other_node);
1766                         else
1767                                 AddPortalToNodes (portal, other_node, back);
1768                         continue;
1769                 }
1770                 if (!backwinding)
1771                 {
1772                         if (side == 0)
1773                                 AddPortalToNodes (portal, front, other_node);
1774                         else
1775                                 AddPortalToNodes (portal, other_node, front);
1776                         continue;
1777                 }
1778
1779                 // the winding is split
1780                 splitportal = AllocPortal ();
1781                 temp = splitportal->chain;
1782                 *splitportal = *portal;
1783                 splitportal->chain = temp;
1784                 splitportal->winding = backwinding;
1785                 FreeWinding (portal->winding);
1786                 portal->winding = frontwinding;
1787
1788                 if (side == 0)
1789                 {
1790                         AddPortalToNodes (portal, front, other_node);
1791                         AddPortalToNodes (splitportal, back, other_node);
1792                 }
1793                 else
1794                 {
1795                         AddPortalToNodes (portal, other_node, front);
1796                         AddPortalToNodes (splitportal, other_node, back);
1797                 }
1798         }
1799
1800         Mod_RecursiveNodePortals(front);
1801         Mod_RecursiveNodePortals(back);
1802 }
1803
1804 /*
1805 void Mod_MakeOutsidePortals(mnode_t *node)
1806 {
1807         int                     i, j;
1808         portal_t        *p, *portals[6];
1809         mnode_t         *outside_node;
1810
1811         outside_node = Hunk_AllocName(sizeof(mnode_t), loadmodel->name);
1812         outside_node->contents = CONTENTS_SOLID;
1813         outside_node->portals = NULL;
1814
1815         for (i = 0;i < 3;i++)
1816         {
1817                 for (j = 0;j < 2;j++)
1818                 {
1819                         portals[j*3 + i] = p = AllocPortal ();
1820                         memset (&p->plane, 0, sizeof(mplane_t));
1821                         p->plane.normal[i] = j ? -1 : 1;
1822                         p->plane.dist = -65536;
1823                         p->winding = BaseWindingForPlane (&p->plane);
1824                         if (j)
1825                                 AddPortalToNodes (p, outside_node, node);
1826                         else
1827                                 AddPortalToNodes (p, node, outside_node);
1828                 }
1829         }
1830
1831         // clip the basewindings by all the other planes
1832         for (i = 0;i < 6;i++)
1833         {
1834                 for (j = 0;j < 6;j++)
1835                 {
1836                         if (j == i)
1837                                 continue;
1838                         portals[i]->winding = ClipWinding (portals[i]->winding, &portals[j]->plane, true);
1839                 }
1840         }
1841 }
1842 */
1843
1844 void Mod_MakePortals(void)
1845 {
1846 //      Con_Printf("building portals for %s\n", loadmodel->name);
1847
1848         portalchain = NULL;
1849 //      Mod_MakeOutsidePortals (loadmodel->nodes);
1850         Mod_RecursiveNodePortals (loadmodel->nodes);
1851         Mod_FinalizePortals();
1852 }
1853
1854 /*
1855 =================
1856 Mod_LoadBrushModel
1857 =================
1858 */
1859 void Mod_LoadBrushModel (model_t *mod, void *buffer)
1860 {
1861         int                     i, j;
1862         dheader_t       *header;
1863         dmodel_t        *bm;
1864         
1865         loadmodel->type = mod_brush;
1866         
1867         header = (dheader_t *)buffer;
1868
1869         i = LittleLong (header->version);
1870         if (i != BSPVERSION && i != 30)
1871                 Host_Error ("Mod_LoadBrushModel: %s has wrong version number (%i should be %i or 30 (HalfLife))", mod->name, i, BSPVERSION);
1872         hlbsp = i == 30;
1873         halflifebsp.value = hlbsp;
1874
1875 // swap all the lumps
1876         mod_base = (byte *)header;
1877
1878         for (i=0 ; i<sizeof(dheader_t)/4 ; i++)
1879                 ((int *)header)[i] = LittleLong ( ((int *)header)[i]);
1880
1881 // load into heap
1882         
1883         // LordHavoc: had to move entity loading above everything to allow parsing various settings from worldspawn
1884         Mod_LoadEntities (&header->lumps[LUMP_ENTITIES]);
1885
1886         Mod_LoadVertexes (&header->lumps[LUMP_VERTEXES]);
1887         Mod_LoadEdges (&header->lumps[LUMP_EDGES]);
1888         Mod_LoadSurfedges (&header->lumps[LUMP_SURFEDGES]);
1889         Mod_LoadTextures (&header->lumps[LUMP_TEXTURES]);
1890         Mod_LoadLighting (&header->lumps[LUMP_LIGHTING]);
1891         Mod_LoadPlanes (&header->lumps[LUMP_PLANES]);
1892         Mod_LoadTexinfo (&header->lumps[LUMP_TEXINFO]);
1893         Mod_LoadFaces (&header->lumps[LUMP_FACES]);
1894         Mod_LoadMarksurfaces (&header->lumps[LUMP_MARKSURFACES]);
1895         Mod_LoadVisibility (&header->lumps[LUMP_VISIBILITY]);
1896         Mod_LoadLeafs (&header->lumps[LUMP_LEAFS]);
1897         Mod_LoadNodes (&header->lumps[LUMP_NODES]);
1898         Mod_LoadClipnodes (&header->lumps[LUMP_CLIPNODES]);
1899 //      Mod_LoadEntities (&header->lumps[LUMP_ENTITIES]);
1900         Mod_LoadSubmodels (&header->lumps[LUMP_MODELS]);
1901
1902         Mod_MakeHull0 ();
1903
1904         Mod_MakePortals();
1905         
1906         mod->numframes = 2;             // regular and alternate animation
1907         
1908 //
1909 // set up the submodels (FIXME: this is confusing)
1910 //
1911         for (i = 0;i < mod->numsubmodels;i++)
1912         {
1913                 bm = &mod->submodels[i];
1914
1915                 mod->hulls[0].firstclipnode = bm->headnode[0];
1916                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
1917                 {
1918                         mod->hulls[j].firstclipnode = bm->headnode[j];
1919                         mod->hulls[j].lastclipnode = mod->numclipnodes - 1;
1920                 }
1921                 
1922                 mod->firstmodelsurface = bm->firstface;
1923                 mod->nummodelsurfaces = bm->numfaces;
1924                 
1925                 VectorCopy (bm->maxs, mod->maxs);
1926                 VectorCopy (bm->mins, mod->mins);
1927
1928                 mod->radius = RadiusFromBounds (mod->mins, mod->maxs);
1929
1930                 mod->numleafs = bm->visleafs;
1931
1932                 if (isworldmodel && i < (mod->numsubmodels - 1)) // LordHavoc: only register submodels if it is the world (prevents bsp models from replacing world submodels)
1933                 {       // duplicate the basic information
1934                         char    name[10];
1935
1936                         sprintf (name, "*%i", i+1);
1937                         loadmodel = Mod_FindName (name);
1938                         *loadmodel = *mod;
1939                         strcpy (loadmodel->name, name);
1940                         mod = loadmodel;
1941                 }
1942         }
1943 }