made the Sorted Edge Rasterizer (hidden surface removal) optional as the r_ser cvar...
[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                 {
617                         // spread the mins / maxs by a pixel
618                         out->mins[j] = LittleFloat (in->mins[j]) - 1;
619                         out->maxs[j] = LittleFloat (in->maxs[j]) + 1;
620                         out->origin[j] = LittleFloat (in->origin[j]);
621                 }
622                 for (j=0 ; j<MAX_MAP_HULLS ; j++)
623                         out->headnode[j] = LittleLong (in->headnode[j]);
624                 out->visleafs = LittleLong (in->visleafs);
625                 out->firstface = LittleLong (in->firstface);
626                 out->numfaces = LittleLong (in->numfaces);
627         }
628 }
629
630 /*
631 =================
632 Mod_LoadEdges
633 =================
634 */
635 void Mod_LoadEdges (lump_t *l)
636 {
637         dedge_t *in;
638         medge_t *out;
639         int     i, count;
640
641         in = (void *)(mod_base + l->fileofs);
642         if (l->filelen % sizeof(*in))
643                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
644         count = l->filelen / sizeof(*in);
645         out = Hunk_AllocName ( (count + 1) * sizeof(*out), va("%s edges", loadname));
646
647         loadmodel->edges = out;
648         loadmodel->numedges = count;
649
650         for ( i=0 ; i<count ; i++, in++, out++)
651         {
652                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
653                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
654         }
655 }
656
657 /*
658 =================
659 Mod_LoadTexinfo
660 =================
661 */
662 void Mod_LoadTexinfo (lump_t *l)
663 {
664         texinfo_t *in;
665         mtexinfo_t *out;
666         int     i, j, k, count;
667         int             miptex;
668
669         in = (void *)(mod_base + l->fileofs);
670         if (l->filelen % sizeof(*in))
671                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
672         count = l->filelen / sizeof(*in);
673         out = Hunk_AllocName ( count*sizeof(*out), va("%s texinfo", loadname));
674
675         loadmodel->texinfo = out;
676         loadmodel->numtexinfo = count;
677
678         for ( i=0 ; i<count ; i++, in++, out++)
679         {
680                 for (k=0 ; k<2 ; k++)
681                         for (j=0 ; j<4 ; j++)
682                                 out->vecs[k][j] = LittleFloat (in->vecs[k][j]);
683
684                 miptex = LittleLong (in->miptex);
685                 out->flags = LittleLong (in->flags);
686         
687                 if (!loadmodel->textures)
688                 {
689                         out->texture = &r_notexture_mip;        // checkerboard texture
690                         out->flags = 0;
691                 }
692                 else
693                 {
694                         if (miptex >= loadmodel->numtextures)
695                                 Host_Error ("miptex >= loadmodel->numtextures");
696                         out->texture = loadmodel->textures[miptex];
697                         if (!out->texture)
698                         {
699                                 out->texture = &r_notexture_mip; // checkerboard texture
700                                 out->flags = 0;
701                         }
702                 }
703         }
704 }
705
706 /*
707 ================
708 CalcSurfaceExtents
709
710 Fills in s->texturemins[] and s->extents[]
711 ================
712 */
713 void CalcSurfaceExtents (msurface_t *s)
714 {
715         float   mins[2], maxs[2], val;
716         int             i,j, e;
717         mvertex_t       *v;
718         mtexinfo_t      *tex;
719         int             bmins[2], bmaxs[2];
720
721         mins[0] = mins[1] = 999999;
722         maxs[0] = maxs[1] = -99999;
723
724         tex = s->texinfo;
725         
726         for (i=0 ; i<s->numedges ; i++)
727         {
728                 e = loadmodel->surfedges[s->firstedge+i];
729                 if (e >= 0)
730                         v = &loadmodel->vertexes[loadmodel->edges[e].v[0]];
731                 else
732                         v = &loadmodel->vertexes[loadmodel->edges[-e].v[1]];
733                 
734                 for (j=0 ; j<2 ; j++)
735                 {
736                         val = v->position[0] * tex->vecs[j][0] + 
737                                 v->position[1] * tex->vecs[j][1] +
738                                 v->position[2] * tex->vecs[j][2] +
739                                 tex->vecs[j][3];
740                         if (val < mins[j])
741                                 mins[j] = val;
742                         if (val > maxs[j])
743                                 maxs[j] = val;
744                 }
745         }
746
747         for (i=0 ; i<2 ; i++)
748         {       
749                 bmins[i] = floor(mins[i]/16);
750                 bmaxs[i] = ceil(maxs[i]/16);
751
752                 s->texturemins[i] = bmins[i] * 16;
753                 s->extents[i] = (bmaxs[i] - bmins[i]) * 16;
754 //              if ( !(tex->flags & TEX_SPECIAL) && s->extents[i] > 512)
755                 if ((tex->flags & TEX_SPECIAL) == 0 && (s->extents[i]+1) > (256*16))
756                         Host_Error ("Bad surface extents");
757         }
758 }
759
760 void GL_SubdivideSurface (msurface_t *fa);
761
762 /*
763 =================
764 Mod_LoadFaces
765 =================
766 */
767 void Mod_LoadFaces (lump_t *l)
768 {
769         dface_t         *in;
770         msurface_t      *out;
771         int                     i, count, surfnum;
772         int                     planenum, side;
773
774         in = (void *)(mod_base + l->fileofs);
775         if (l->filelen % sizeof(*in))
776                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
777         count = l->filelen / sizeof(*in);
778         out = Hunk_AllocName ( count*sizeof(*out), va("%s faces", loadname));
779
780         loadmodel->surfaces = out;
781         loadmodel->numsurfaces = count;
782
783         for ( surfnum=0 ; surfnum<count ; surfnum++, in++, out++)
784         {
785                 out->firstedge = LittleLong(in->firstedge);
786                 out->numedges = LittleShort(in->numedges);              
787                 out->flags = 0;
788
789                 planenum = LittleShort(in->planenum);
790                 side = LittleShort(in->side);
791                 if (side)
792                         out->flags |= SURF_PLANEBACK;                   
793
794                 out->plane = loadmodel->planes + planenum;
795
796                 out->texinfo = loadmodel->texinfo + LittleShort (in->texinfo);
797
798                 CalcSurfaceExtents (out);
799
800         // lighting info
801
802                 for (i=0 ; i<MAXLIGHTMAPS ; i++)
803                         out->styles[i] = in->styles[i];
804                 i = LittleLong(in->lightofs);
805                 if (i == -1)
806                         out->samples = NULL;
807                 else if (hlbsp) // LordHavoc: HalfLife map (bsp version 30)
808                         out->samples = loadmodel->lightdata + i;
809                 else // LordHavoc: white lighting (bsp version 29)
810                         out->samples = loadmodel->lightdata + (i * 3); 
811                 
812         // set the drawing flags flag
813                 
814 //              if (!strncmp(out->texinfo->texture->name,"sky",3))      // sky
815                 // LordHavoc: faster check
816                 if ((out->texinfo->texture->name[0] == 's' || out->texinfo->texture->name[0] == 'S')
817                  && (out->texinfo->texture->name[1] == 'k' || out->texinfo->texture->name[1] == 'K')
818                  && (out->texinfo->texture->name[2] == 'y' || out->texinfo->texture->name[2] == 'Y'))
819                 {
820                         // LordHavoc: for consistency reasons, mark sky as fullbright and solid as well
821                         out->flags |= (SURF_DRAWSKY | SURF_DRAWTILED | SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA | SURF_CLIPSOLID);
822                         GL_SubdivideSurface (out);      // cut up polygon for warps
823                         continue;
824                 }
825                 
826 //              if (!strncmp(out->texinfo->texture->name,"*",1))                // turbulent
827                 if (out->texinfo->texture->name[0] == '*') // LordHavoc: faster check
828                 {
829                         out->flags |= (SURF_DRAWTURB | SURF_DRAWTILED | SURF_LIGHTBOTHSIDES);
830                         // LordHavoc: some turbulent textures should be fullbright and solid
831                         if (!strncmp(out->texinfo->texture->name,"*lava",5)
832                          || !strncmp(out->texinfo->texture->name,"*teleport",9)
833                          || !strncmp(out->texinfo->texture->name,"*rift",5)) // Scourge of Armagon texture
834                                 out->flags |= (SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA);
835                         for (i=0 ; i<2 ; i++)
836                         {
837                                 out->extents[i] = 16384;
838                                 out->texturemins[i] = -8192;
839                         }
840                         GL_SubdivideSurface (out);      // cut up polygon for warps
841                         continue;
842                 }
843                 
844                 out->flags |= SURF_CLIPSOLID;
845         }
846 }
847
848
849 /*
850 =================
851 Mod_SetParent
852 =================
853 */
854 void Mod_SetParent (mnode_t *node, mnode_t *parent)
855 {
856         node->parent = parent;
857         if (node->contents < 0)
858                 return;
859         Mod_SetParent (node->children[0], node);
860         Mod_SetParent (node->children[1], node);
861 }
862
863 /*
864 =================
865 Mod_LoadNodes
866 =================
867 */
868 void Mod_LoadNodes (lump_t *l)
869 {
870         int                     i, j, count, p;
871         dnode_t         *in;
872         mnode_t         *out;
873
874         in = (void *)(mod_base + l->fileofs);
875         if (l->filelen % sizeof(*in))
876                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
877         count = l->filelen / sizeof(*in);
878         out = Hunk_AllocName ( count*sizeof(*out), va("%s nodes", loadname));
879
880         loadmodel->nodes = out;
881         loadmodel->numnodes = count;
882
883         for ( i=0 ; i<count ; i++, in++, out++)
884         {
885                 for (j=0 ; j<3 ; j++)
886                 {
887                         out->mins[j] = LittleShort (in->mins[j]);
888                         out->maxs[j] = LittleShort (in->maxs[j]);
889                 }
890         
891                 p = LittleLong(in->planenum);
892                 out->plane = loadmodel->planes + p;
893
894                 out->firstsurface = LittleShort (in->firstface);
895                 out->numsurfaces = LittleShort (in->numfaces);
896                 
897                 for (j=0 ; j<2 ; j++)
898                 {
899                         p = LittleShort (in->children[j]);
900                         if (p >= 0)
901                                 out->children[j] = loadmodel->nodes + p;
902                         else
903                                 out->children[j] = (mnode_t *)(loadmodel->leafs + (-1 - p));
904                 }
905         }
906         
907         Mod_SetParent (loadmodel->nodes, NULL); // sets nodes and leafs
908 }
909
910 /*
911 =================
912 Mod_LoadLeafs
913 =================
914 */
915 void Mod_LoadLeafs (lump_t *l)
916 {
917         dleaf_t         *in;
918         mleaf_t         *out;
919         int                     i, j, count, p;
920
921         in = (void *)(mod_base + l->fileofs);
922         if (l->filelen % sizeof(*in))
923                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
924         count = l->filelen / sizeof(*in);
925         out = Hunk_AllocName ( count*sizeof(*out), va("%s leafs", loadname));
926
927         loadmodel->leafs = out;
928         loadmodel->numleafs = count;
929
930         for ( i=0 ; i<count ; i++, in++, out++)
931         {
932                 for (j=0 ; j<3 ; j++)
933                 {
934                         out->mins[j] = LittleShort (in->mins[j]);
935                         out->maxs[j] = LittleShort (in->maxs[j]);
936                 }
937
938                 p = LittleLong(in->contents);
939                 out->contents = p;
940
941                 out->firstmarksurface = loadmodel->marksurfaces +
942                         LittleShort(in->firstmarksurface);
943                 out->nummarksurfaces = LittleShort(in->nummarksurfaces);
944                 
945                 p = LittleLong(in->visofs);
946                 if (p == -1)
947                         out->compressed_vis = NULL;
948                 else
949                         out->compressed_vis = loadmodel->visdata + p;
950                 
951                 for (j=0 ; j<4 ; j++)
952                         out->ambient_sound_level[j] = in->ambient_level[j];
953
954                 // gl underwater warp
955                 // LordHavoc: disabled underwater warping
956                 /*
957                 if (out->contents != CONTENTS_EMPTY)
958                 {
959                         for (j=0 ; j<out->nummarksurfaces ; j++)
960                                 out->firstmarksurface[j]->flags |= SURF_UNDERWATER;
961                 }
962                 */
963         }       
964 }
965
966 /*
967 =================
968 Mod_LoadClipnodes
969 =================
970 */
971 void Mod_LoadClipnodes (lump_t *l)
972 {
973         dclipnode_t *in, *out;
974         int                     i, count;
975         hull_t          *hull;
976
977         in = (void *)(mod_base + l->fileofs);
978         if (l->filelen % sizeof(*in))
979                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
980         count = l->filelen / sizeof(*in);
981         out = Hunk_AllocName ( count*sizeof(*out), va("%s clipnodes", loadname));
982
983         loadmodel->clipnodes = out;
984         loadmodel->numclipnodes = count;
985
986         if (hlbsp)
987         {
988                 hull = &loadmodel->hulls[1];
989                 hull->clipnodes = out;
990                 hull->firstclipnode = 0;
991                 hull->lastclipnode = count-1;
992                 hull->planes = loadmodel->planes;
993                 hull->clip_mins[0] = -16;
994                 hull->clip_mins[1] = -16;
995                 hull->clip_mins[2] = -36;
996                 hull->clip_maxs[0] = 16;
997                 hull->clip_maxs[1] = 16;
998                 hull->clip_maxs[2] = 36;
999
1000                 hull = &loadmodel->hulls[2];
1001                 hull->clipnodes = out;
1002                 hull->firstclipnode = 0;
1003                 hull->lastclipnode = count-1;
1004                 hull->planes = loadmodel->planes;
1005                 hull->clip_mins[0] = -32;
1006                 hull->clip_mins[1] = -32;
1007                 hull->clip_mins[2] = -32;
1008                 hull->clip_maxs[0] = 32;
1009                 hull->clip_maxs[1] = 32;
1010                 hull->clip_maxs[2] = 32;
1011
1012                 hull = &loadmodel->hulls[3];
1013                 hull->clipnodes = out;
1014                 hull->firstclipnode = 0;
1015                 hull->lastclipnode = count-1;
1016                 hull->planes = loadmodel->planes;
1017                 hull->clip_mins[0] = -16;
1018                 hull->clip_mins[1] = -16;
1019                 hull->clip_mins[2] = -18;
1020                 hull->clip_maxs[0] = 16;
1021                 hull->clip_maxs[1] = 16;
1022                 hull->clip_maxs[2] = 18;
1023         }
1024         else
1025         {
1026                 hull = &loadmodel->hulls[1];
1027                 hull->clipnodes = out;
1028                 hull->firstclipnode = 0;
1029                 hull->lastclipnode = count-1;
1030                 hull->planes = loadmodel->planes;
1031                 hull->clip_mins[0] = -16;
1032                 hull->clip_mins[1] = -16;
1033                 hull->clip_mins[2] = -24;
1034                 hull->clip_maxs[0] = 16;
1035                 hull->clip_maxs[1] = 16;
1036                 hull->clip_maxs[2] = 32;
1037
1038                 hull = &loadmodel->hulls[2];
1039                 hull->clipnodes = out;
1040                 hull->firstclipnode = 0;
1041                 hull->lastclipnode = count-1;
1042                 hull->planes = loadmodel->planes;
1043                 hull->clip_mins[0] = -32;
1044                 hull->clip_mins[1] = -32;
1045                 hull->clip_mins[2] = -24;
1046                 hull->clip_maxs[0] = 32;
1047                 hull->clip_maxs[1] = 32;
1048                 hull->clip_maxs[2] = 64;
1049         }
1050
1051         for (i=0 ; i<count ; i++, out++, in++)
1052         {
1053                 out->planenum = LittleLong(in->planenum);
1054                 out->children[0] = LittleShort(in->children[0]);
1055                 out->children[1] = LittleShort(in->children[1]);
1056                 if (out->children[0] >= count || out->children[1] >= count)
1057                         Host_Error("Corrupt clipping hull (out of range child)\n");
1058         }
1059 }
1060
1061 /*
1062 =================
1063 Mod_MakeHull0
1064
1065 Duplicate the drawing hull structure as a clipping hull
1066 =================
1067 */
1068 void Mod_MakeHull0 (void)
1069 {
1070         mnode_t         *in;
1071         dclipnode_t *out;
1072         int                     i, count;
1073         hull_t          *hull;
1074         
1075         hull = &loadmodel->hulls[0];    
1076         
1077         in = loadmodel->nodes;
1078         count = loadmodel->numnodes;
1079         out = Hunk_AllocName ( count*sizeof(*out), va("%s hull0", loadname));
1080
1081         hull->clipnodes = out;
1082         hull->firstclipnode = 0;
1083         hull->lastclipnode = count - 1;
1084         hull->planes = loadmodel->planes;
1085
1086         for (i = 0;i < count;i++, out++, in++)
1087         {
1088                 out->planenum = in->plane - loadmodel->planes;
1089                 out->children[0] = in->children[0]->contents < 0 ? in->children[0]->contents : in->children[0] - loadmodel->nodes;
1090                 out->children[1] = in->children[1]->contents < 0 ? in->children[1]->contents : in->children[1] - loadmodel->nodes;
1091         }
1092 }
1093
1094 /*
1095 =================
1096 Mod_LoadMarksurfaces
1097 =================
1098 */
1099 void Mod_LoadMarksurfaces (lump_t *l)
1100 {       
1101         int             i, j, count;
1102         short           *in;
1103         msurface_t **out;
1104         
1105         in = (void *)(mod_base + l->fileofs);
1106         if (l->filelen % sizeof(*in))
1107                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1108         count = l->filelen / sizeof(*in);
1109         out = Hunk_AllocName ( count*sizeof(*out), va("%s marksurfaces", loadname));
1110
1111         loadmodel->marksurfaces = out;
1112         loadmodel->nummarksurfaces = count;
1113
1114         for ( i=0 ; i<count ; i++)
1115         {
1116                 j = LittleShort(in[i]);
1117                 if (j >= loadmodel->numsurfaces)
1118                         Host_Error ("Mod_ParseMarksurfaces: bad surface number");
1119                 out[i] = loadmodel->surfaces + j;
1120         }
1121 }
1122
1123 /*
1124 =================
1125 Mod_LoadSurfedges
1126 =================
1127 */
1128 void Mod_LoadSurfedges (lump_t *l)
1129 {       
1130         int             i, count;
1131         int             *in, *out;
1132         
1133         in = (void *)(mod_base + l->fileofs);
1134         if (l->filelen % sizeof(*in))
1135                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1136         count = l->filelen / sizeof(*in);
1137         out = Hunk_AllocName ( count*sizeof(*out), va("%s surfedges", loadname));
1138
1139         loadmodel->surfedges = out;
1140         loadmodel->numsurfedges = count;
1141
1142         for ( i=0 ; i<count ; i++)
1143                 out[i] = LittleLong (in[i]);
1144 }
1145
1146
1147 /*
1148 =================
1149 Mod_LoadPlanes
1150 =================
1151 */
1152 void Mod_LoadPlanes (lump_t *l)
1153 {
1154         int                     i, j;
1155         mplane_t        *out;
1156         dplane_t        *in;
1157         int                     count;
1158         
1159         in = (void *)(mod_base + l->fileofs);
1160         if (l->filelen % sizeof(*in))
1161                 Host_Error ("MOD_LoadBmodel: funny lump size in %s",loadmodel->name);
1162         count = l->filelen / sizeof(*in);
1163         out = Hunk_AllocName ( count*2*sizeof(*out), va("%s planes", loadname));
1164
1165         loadmodel->planes = out;
1166         loadmodel->numplanes = count;
1167
1168         for ( i=0 ; i<count ; i++, in++, out++)
1169         {
1170                 for (j=0 ; j<3 ; j++)
1171                         out->normal[j] = LittleFloat (in->normal[j]);
1172
1173                 out->dist = LittleFloat (in->dist);
1174                 // LordHavoc: recalculated by PlaneClassify, FIXME: validate type and report error if type does not match normal?
1175 //              out->type = LittleLong (in->type);
1176                 PlaneClassify(out);
1177         }
1178 }
1179
1180 #define MAX_POINTS_ON_WINDING 64
1181
1182 typedef struct
1183 {
1184         int numpoints;
1185         vec3_t points[8]; // variable sized
1186 }
1187 winding_t;
1188
1189 /*
1190 ==================
1191 NewWinding
1192 ==================
1193 */
1194 winding_t *NewWinding (int points)
1195 {
1196         winding_t *w;
1197         int size;
1198
1199         if (points > MAX_POINTS_ON_WINDING)
1200                 Host_Error("NewWinding: too many points\n");
1201
1202         size = (int)((winding_t *)0)->points[points];
1203         w = qmalloc (size);
1204         memset (w, 0, size);
1205
1206         return w;
1207 }
1208
1209 void FreeWinding (winding_t *w)
1210 {
1211         qfree (w);
1212 }
1213
1214 /*
1215 =================
1216 BaseWindingForPlane
1217 =================
1218 */
1219 winding_t *BaseWindingForPlane (mplane_t *p)
1220 {
1221         vec3_t  org, vright, vup;
1222         winding_t       *w;
1223
1224         VectorVectors(p->normal, vright, vup);
1225
1226         VectorScale (vup, 65536, vup);
1227         VectorScale (vright, 65536, vright);
1228
1229         // project a really big axis aligned box onto the plane
1230         w = NewWinding (4);
1231
1232         VectorScale (p->normal, p->dist, org);
1233
1234         VectorSubtract (org, vright, w->points[0]);
1235         VectorAdd (w->points[0], vup, w->points[0]);
1236
1237         VectorAdd (org, vright, w->points[1]);
1238         VectorAdd (w->points[1], vup, w->points[1]);
1239
1240         VectorAdd (org, vright, w->points[2]);
1241         VectorSubtract (w->points[2], vup, w->points[2]);
1242
1243         VectorSubtract (org, vright, w->points[3]);
1244         VectorSubtract (w->points[3], vup, w->points[3]);
1245
1246         w->numpoints = 4;
1247
1248         return w;       
1249 }
1250
1251 /*
1252 ==================
1253 ClipWinding
1254
1255 Clips the winding to the plane, returning the new winding on the positive side
1256 Frees the input winding.
1257 If keepon is true, an exactly on-plane winding will be saved, otherwise
1258 it will be clipped away.
1259 ==================
1260 */
1261 winding_t *ClipWinding (winding_t *in, mplane_t *split, int keepon)
1262 {
1263         vec_t   dists[MAX_POINTS_ON_WINDING + 1];
1264         int             sides[MAX_POINTS_ON_WINDING + 1];
1265         int             counts[3];
1266         vec_t   dot;
1267         int             i, j;
1268         vec_t   *p1, *p2;
1269         vec3_t  mid;
1270         winding_t       *neww;
1271         int             maxpts;
1272
1273         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
1274
1275         // determine sides for each point
1276         for (i = 0;i < in->numpoints;i++)
1277         {
1278                 dists[i] = dot = DotProduct (in->points[i], split->normal) - split->dist;
1279                 if (dot > ON_EPSILON)
1280                         sides[i] = SIDE_FRONT;
1281                 else if (dot < -ON_EPSILON)
1282                         sides[i] = SIDE_BACK;
1283                 else
1284                         sides[i] = SIDE_ON;
1285                 counts[sides[i]]++;
1286         }
1287         sides[i] = sides[0];
1288         dists[i] = dists[0];
1289
1290         if (keepon && !counts[0] && !counts[1])
1291                 return in;
1292
1293         if (!counts[0])
1294         {
1295                 FreeWinding (in);
1296                 return NULL;
1297         }
1298         if (!counts[1])
1299                 return in;
1300
1301         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
1302         neww = NewWinding (maxpts);
1303
1304         for (i = 0;i < in->numpoints;i++)
1305         {
1306                 p1 = in->points[i];
1307
1308                 if (sides[i] == SIDE_ON)
1309                 {
1310                         VectorCopy (p1, neww->points[neww->numpoints]);
1311                         neww->numpoints++;
1312                         continue;
1313                 }
1314
1315                 if (sides[i] == SIDE_FRONT)
1316                 {
1317                         VectorCopy (p1, neww->points[neww->numpoints]);
1318                         neww->numpoints++;
1319                 }
1320
1321                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1322                         continue;
1323
1324                 // generate a split point
1325                 p2 = in->points[(i+1)%in->numpoints];
1326
1327                 dot = dists[i] / (dists[i]-dists[i+1]);
1328                 for (j = 0;j < 3;j++)
1329                 {       // avoid round off error when possible
1330                         if (split->normal[j] == 1)
1331                                 mid[j] = split->dist;
1332                         else if (split->normal[j] == -1)
1333                                 mid[j] = -split->dist;
1334                         else
1335                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1336                 }
1337
1338                 VectorCopy (mid, neww->points[neww->numpoints]);
1339                 neww->numpoints++;
1340         }
1341
1342         if (neww->numpoints > maxpts)
1343                 Host_Error ("ClipWinding: points exceeded estimate");
1344
1345         // free the original winding
1346         FreeWinding (in);
1347
1348         return neww;
1349 }
1350
1351
1352 /*
1353 ==================
1354 DivideWinding
1355
1356 Divides a winding by a plane, producing one or two windings.  The
1357 original winding is not damaged or freed.  If only on one side, the
1358 returned winding will be the input winding.  If on both sides, two
1359 new windings will be created.
1360 ==================
1361 */
1362 void DivideWinding (winding_t *in, mplane_t *split, winding_t **front, winding_t **back)
1363 {
1364         vec_t   dists[MAX_POINTS_ON_WINDING + 1];
1365         int             sides[MAX_POINTS_ON_WINDING + 1];
1366         int             counts[3];
1367         vec_t   dot;
1368         int             i, j;
1369         vec_t   *p1, *p2;
1370         vec3_t  mid;
1371         winding_t       *f, *b;
1372         int             maxpts;
1373
1374         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
1375
1376         // determine sides for each point
1377         for (i = 0;i < in->numpoints;i++)
1378         {
1379                 dot = DotProduct (in->points[i], split->normal);
1380                 dot -= split->dist;
1381                 dists[i] = dot;
1382                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
1383                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
1384                 else sides[i] = SIDE_ON;
1385                 counts[sides[i]]++;
1386         }
1387         sides[i] = sides[0];
1388         dists[i] = dists[0];
1389
1390         *front = *back = NULL;
1391
1392         if (!counts[0])
1393         {
1394                 *back = in;
1395                 return;
1396         }
1397         if (!counts[1])
1398         {
1399                 *front = in;
1400                 return;
1401         }
1402
1403         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
1404
1405         *front = f = NewWinding (maxpts);
1406         *back = b = NewWinding (maxpts);
1407
1408         for (i = 0;i < in->numpoints;i++)
1409         {
1410                 p1 = in->points[i];
1411
1412                 if (sides[i] == SIDE_ON)
1413                 {
1414                         VectorCopy (p1, f->points[f->numpoints]);
1415                         f->numpoints++;
1416                         VectorCopy (p1, b->points[b->numpoints]);
1417                         b->numpoints++;
1418                         continue;
1419                 }
1420
1421                 if (sides[i] == SIDE_FRONT)
1422                 {
1423                         VectorCopy (p1, f->points[f->numpoints]);
1424                         f->numpoints++;
1425                 }
1426                 else if (sides[i] == SIDE_BACK)
1427                 {
1428                         VectorCopy (p1, b->points[b->numpoints]);
1429                         b->numpoints++;
1430                 }
1431
1432                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1433                         continue;
1434
1435                 // generate a split point
1436                 p2 = in->points[(i+1)%in->numpoints];
1437
1438                 dot = dists[i] / (dists[i]-dists[i+1]);
1439                 for (j = 0;j < 3;j++)
1440                 {       // avoid round off error when possible
1441                         if (split->normal[j] == 1)
1442                                 mid[j] = split->dist;
1443                         else if (split->normal[j] == -1)
1444                                 mid[j] = -split->dist;
1445                         else
1446                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1447                 }
1448
1449                 VectorCopy (mid, f->points[f->numpoints]);
1450                 f->numpoints++;
1451                 VectorCopy (mid, b->points[b->numpoints]);
1452                 b->numpoints++;
1453         }
1454
1455         if (f->numpoints > maxpts || b->numpoints > maxpts)
1456                 Host_Error ("DivideWinding: points exceeded estimate");
1457 }
1458
1459 typedef struct portal_s
1460 {
1461         mplane_t plane;
1462         mnode_t *nodes[2];              // [0] = front side of plane
1463         struct portal_s *next[2];       
1464         winding_t *winding;
1465         struct portal_s *chain; // all portals are linked into a list
1466 }
1467 portal_t;
1468
1469 static portal_t *portalchain;
1470
1471 /*
1472 ===========
1473 AllocPortal
1474 ===========
1475 */
1476 portal_t *AllocPortal (void)
1477 {
1478         portal_t *p;
1479         p = qmalloc(sizeof(portal_t));
1480         memset(p, 0, sizeof(portal_t));
1481         p->chain = portalchain;
1482         portalchain = p;
1483         return p;
1484 }
1485
1486 void Mod_RecursiveRecalcNodeBBox(mnode_t *node)
1487 {
1488         // calculate children first
1489         if (node->children[0]->contents >= 0)
1490                 Mod_RecursiveRecalcNodeBBox(node->children[0]);
1491         if (node->children[1]->contents >= 0)
1492                 Mod_RecursiveRecalcNodeBBox(node->children[1]);
1493
1494         // make combined bounding box from children
1495         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
1496         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
1497         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
1498         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
1499         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
1500         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
1501 }
1502
1503 void Mod_FinalizePortals(void)
1504 {
1505         int i, j, numportals, numpoints;
1506         portal_t *p, *pnext;
1507         mportal_t *portal;
1508         mvertex_t *point;
1509         mleaf_t *leaf, *endleaf;
1510         winding_t *w;
1511
1512         // recalculate bounding boxes for all leafs (because qbsp is very sloppy)
1513         leaf = loadmodel->leafs;
1514         endleaf = leaf + loadmodel->numleafs;
1515         for (;leaf < endleaf;leaf++)
1516         {
1517                 VectorSet( 2000000000,  2000000000,  2000000000, leaf->mins);
1518                 VectorSet(-2000000000, -2000000000, -2000000000, leaf->maxs);
1519         }
1520         p = portalchain;
1521         while(p)
1522         {
1523                 if (p->winding)
1524                 {
1525                         for (i = 0;i < 2;i++)
1526                         {
1527                                 leaf = (mleaf_t *)p->nodes[i];
1528                                 w = p->winding;
1529                                 for (j = 0;j < w->numpoints;j++)
1530                                 {
1531                                         if (leaf->mins[0] > w->points[j][0]) leaf->mins[0] = w->points[j][0];
1532                                         if (leaf->mins[1] > w->points[j][1]) leaf->mins[1] = w->points[j][1];
1533                                         if (leaf->mins[2] > w->points[j][2]) leaf->mins[2] = w->points[j][2];
1534                                         if (leaf->maxs[0] < w->points[j][0]) leaf->maxs[0] = w->points[j][0];
1535                                         if (leaf->maxs[1] < w->points[j][1]) leaf->maxs[1] = w->points[j][1];
1536                                         if (leaf->maxs[2] < w->points[j][2]) leaf->maxs[2] = w->points[j][2];
1537                                 }
1538                         }
1539                 }
1540                 p = p->chain;
1541         }
1542
1543 //      Hunk_Check();
1544
1545         Mod_RecursiveRecalcNodeBBox(loadmodel->nodes);
1546
1547 //      Hunk_Check();
1548
1549         // tally up portal and point counts
1550         p = portalchain;
1551         numportals = 0;
1552         numpoints = 0;
1553         while(p)
1554         {
1555                 // note: this check must match the one below or it will usually corrupt the hunk
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->winding && p->nodes[0] != p->nodes[1]
1558                  && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
1559                  && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
1560                 {
1561                         numportals += 2;
1562                         numpoints += p->winding->numpoints * 2;
1563                 }
1564                 p = p->chain;
1565         }
1566         loadmodel->portals = Hunk_AllocName(numportals * sizeof(mportal_t), va("%s portals", loadmodel->name));
1567         loadmodel->numportals = numportals;
1568         loadmodel->portalpoints = Hunk_AllocName(numpoints * sizeof(mvertex_t), va("%s portals", loadmodel->name));
1569         loadmodel->numportalpoints = numpoints;
1570         // clear all leaf portal chains
1571         for (i = 0;i < loadmodel->numleafs;i++)
1572                 loadmodel->leafs[i].portals = NULL;
1573         // process all portals in the global portal chain, while freeing them
1574         portal = loadmodel->portals;
1575         point = loadmodel->portalpoints;
1576         p = portalchain;
1577         portalchain = NULL;
1578         while (p)
1579         {
1580                 pnext = p->chain;
1581
1582                 if (p->winding)
1583                 {
1584                         // note: this check must match the one below or it will usually corrupt the hunk
1585                         // 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
1586                         if (p->nodes[0] != p->nodes[1]
1587                          && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
1588                          && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
1589                         {
1590                                 // first make the back to front portal (forward portal)
1591                                 portal->points = point;
1592                                 portal->numpoints = p->winding->numpoints;
1593                                 portal->plane.dist = p->plane.dist;
1594                                 VectorCopy(p->plane.normal, portal->plane.normal);
1595                                 portal->here = (mleaf_t *)p->nodes[1];
1596                                 portal->past = (mleaf_t *)p->nodes[0];
1597                                 // copy points
1598                                 for (j = 0;j < portal->numpoints;j++)
1599                                 {
1600                                         VectorCopy(p->winding->points[j], point->position);
1601                                         point++;
1602                                 }
1603                                 PlaneClassify(&portal->plane);
1604
1605                                 // link into leaf's portal chain
1606                                 portal->next = portal->here->portals;
1607                                 portal->here->portals = portal;
1608
1609                                 // advance to next portal
1610                                 portal++;
1611
1612                                 // then make the front to back portal (backward portal)
1613                                 portal->points = point;
1614                                 portal->numpoints = p->winding->numpoints;
1615                                 portal->plane.dist = -p->plane.dist;
1616                                 VectorNegate(p->plane.normal, portal->plane.normal);
1617                                 portal->here = (mleaf_t *)p->nodes[0];
1618                                 portal->past = (mleaf_t *)p->nodes[1];
1619                                 // copy points
1620                                 for (j = portal->numpoints - 1;j >= 0;j--)
1621                                 {
1622                                         VectorCopy(p->winding->points[j], point->position);
1623                                         point++;
1624                                 }
1625                                 PlaneClassify(&portal->plane);
1626
1627                                 // link into leaf's portal chain
1628                                 portal->next = portal->here->portals;
1629                                 portal->here->portals = portal;
1630
1631                                 // advance to next portal
1632                                 portal++;
1633                         }
1634                         FreeWinding(p->winding);
1635                 }
1636                 qfree(p);
1637                 p = pnext;
1638         }
1639 }
1640
1641 /*
1642 =============
1643 AddPortalToNodes
1644 =============
1645 */
1646 void AddPortalToNodes (portal_t *p, mnode_t *front, mnode_t *back)
1647 {
1648         if (!front)
1649                 Host_Error ("AddPortalToNodes: NULL front node");
1650         if (!back)
1651                 Host_Error ("AddPortalToNodes: NULL back node");
1652         if (p->nodes[0] || p->nodes[1])
1653                 Host_Error ("AddPortalToNodes: already included");
1654         // 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
1655
1656         p->nodes[0] = front;
1657         p->next[0] = (portal_t *)front->portals;
1658         front->portals = (mportal_t *)p;
1659
1660         p->nodes[1] = back;
1661         p->next[1] = (portal_t *)back->portals;
1662         back->portals = (mportal_t *)p;
1663 }
1664
1665 /*
1666 =============
1667 RemovePortalFromNode
1668 =============
1669 */
1670 void RemovePortalFromNodes(portal_t *portal)
1671 {
1672         int i;
1673         mnode_t *node;
1674         void **portalpointer;
1675         portal_t *t;
1676         for (i = 0;i < 2;i++)
1677         {
1678                 node = portal->nodes[i];
1679
1680                 portalpointer = (void **) &node->portals;
1681                 while (1)
1682                 {
1683                         t = *portalpointer;
1684                         if (!t)
1685                                 Host_Error ("RemovePortalFromNodes: portal not in leaf");
1686
1687                         if (t == portal)
1688                         {
1689                                 if (portal->nodes[0] == node)
1690                                 {
1691                                         *portalpointer = portal->next[0];
1692                                         portal->nodes[0] = NULL;
1693                                 }
1694                                 else if (portal->nodes[1] == node)
1695                                 {
1696                                         *portalpointer = portal->next[1];
1697                                         portal->nodes[1] = NULL;
1698                                 }
1699                                 else
1700                                         Host_Error ("RemovePortalFromNodes: portal not bounding leaf");
1701                                 break;
1702                         }
1703
1704                         if (t->nodes[0] == node)
1705                                 portalpointer = (void **) &t->next[0];
1706                         else if (t->nodes[1] == node)
1707                                 portalpointer = (void **) &t->next[1];
1708                         else
1709                                 Host_Error ("RemovePortalFromNodes: portal not bounding leaf");
1710                 }
1711         }
1712 }
1713
1714 void Mod_RecursiveNodePortals (mnode_t *node)
1715 {
1716         int side;
1717         mnode_t *front, *back, *other_node;
1718         mplane_t clipplane, *plane;
1719         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
1720         winding_t *nodeportalwinding, *frontwinding, *backwinding;
1721
1722         //      CheckLeafPortalConsistancy (node);
1723
1724         // if a leaf, we're done
1725         if (node->contents)
1726                 return;
1727
1728         plane = node->plane;
1729
1730         front = node->children[0];
1731         back = node->children[1];
1732         if (front == back)
1733                 Host_Error("Mod_RecursiveNodePortals: corrupt node hierarchy");
1734
1735         // create the new portal by generating a polygon for the node plane,
1736         // and clipping it by all of the other portals (which came from nodes above this one)
1737         nodeportal = AllocPortal ();
1738         nodeportal->plane = *node->plane;
1739
1740         nodeportalwinding = BaseWindingForPlane (node->plane);
1741         side = 0;       // shut up compiler warning
1742         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])     
1743         {
1744                 clipplane = portal->plane;
1745                 if (portal->nodes[0] == portal->nodes[1])
1746                         Host_Error("Mod_RecursiveNodePortals: portal has same node on both sides (1)");
1747                 if (portal->nodes[0] == node)
1748                         side = 0;
1749                 else if (portal->nodes[1] == node)
1750                 {
1751                         clipplane.dist = -clipplane.dist;
1752                         VectorNegate (clipplane.normal, clipplane.normal);
1753                         side = 1;
1754                 }
1755                 else
1756                         Host_Error ("Mod_RecursiveNodePortals: mislinked portal");
1757
1758                 nodeportalwinding = ClipWinding (nodeportalwinding, &clipplane, true);
1759                 if (!nodeportalwinding)
1760                 {
1761                         printf ("Mod_RecursiveNodePortals: WARNING: new portal was clipped away\n");
1762                         break;
1763                 }
1764         }
1765
1766         if (nodeportalwinding)
1767         {
1768                 // if the plane was not clipped on all sides, there was an error
1769                 nodeportal->winding = nodeportalwinding;
1770                 AddPortalToNodes (nodeportal, front, back);
1771         }
1772
1773         // split the portals of this node along this node's plane and assign them to the children of this node
1774         // (migrating the portals downward through the tree)
1775         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
1776         {
1777                 if (portal->nodes[0] == portal->nodes[1])
1778                         Host_Error("Mod_RecursiveNodePortals: portal has same node on both sides (2)");
1779                 if (portal->nodes[0] == node)
1780                         side = 0;
1781                 else if (portal->nodes[1] == node)
1782                         side = 1;
1783                 else
1784                         Host_Error ("Mod_RecursiveNodePortals: mislinked portal");
1785                 nextportal = portal->next[side];
1786
1787                 other_node = portal->nodes[!side];
1788                 RemovePortalFromNodes (portal);
1789
1790                 // cut the portal into two portals, one on each side of the node plane
1791                 DivideWinding (portal->winding, plane, &frontwinding, &backwinding);
1792
1793                 if (!frontwinding)
1794                 {
1795                         if (side == 0)
1796                                 AddPortalToNodes (portal, back, other_node);
1797                         else
1798                                 AddPortalToNodes (portal, other_node, back);
1799                         continue;
1800                 }
1801                 if (!backwinding)
1802                 {
1803                         if (side == 0)
1804                                 AddPortalToNodes (portal, front, other_node);
1805                         else
1806                                 AddPortalToNodes (portal, other_node, front);
1807                         continue;
1808                 }
1809
1810                 // the winding is split
1811                 splitportal = AllocPortal ();
1812                 temp = splitportal->chain;
1813                 *splitportal = *portal;
1814                 splitportal->chain = temp;
1815                 splitportal->winding = backwinding;
1816                 FreeWinding (portal->winding);
1817                 portal->winding = frontwinding;
1818
1819                 if (side == 0)
1820                 {
1821                         AddPortalToNodes (portal, front, other_node);
1822                         AddPortalToNodes (splitportal, back, other_node);
1823                 }
1824                 else
1825                 {
1826                         AddPortalToNodes (portal, other_node, front);
1827                         AddPortalToNodes (splitportal, other_node, back);
1828                 }
1829         }
1830
1831         Mod_RecursiveNodePortals(front);
1832         Mod_RecursiveNodePortals(back);
1833 }
1834
1835 /*
1836 void Mod_MakeOutsidePortals(mnode_t *node)
1837 {
1838         int                     i, j;
1839         portal_t        *p, *portals[6];
1840         mnode_t         *outside_node;
1841
1842         outside_node = Hunk_AllocName(sizeof(mnode_t), loadmodel->name);
1843         outside_node->contents = CONTENTS_SOLID;
1844         outside_node->portals = NULL;
1845
1846         for (i = 0;i < 3;i++)
1847         {
1848                 for (j = 0;j < 2;j++)
1849                 {
1850                         portals[j*3 + i] = p = AllocPortal ();
1851                         memset (&p->plane, 0, sizeof(mplane_t));
1852                         p->plane.normal[i] = j ? -1 : 1;
1853                         p->plane.dist = -65536;
1854                         p->winding = BaseWindingForPlane (&p->plane);
1855                         if (j)
1856                                 AddPortalToNodes (p, outside_node, node);
1857                         else
1858                                 AddPortalToNodes (p, node, outside_node);
1859                 }
1860         }
1861
1862         // clip the basewindings by all the other planes
1863         for (i = 0;i < 6;i++)
1864         {
1865                 for (j = 0;j < 6;j++)
1866                 {
1867                         if (j == i)
1868                                 continue;
1869                         portals[i]->winding = ClipWinding (portals[i]->winding, &portals[j]->plane, true);
1870                 }
1871         }
1872 }
1873 */
1874
1875 void Mod_MakePortals(void)
1876 {
1877 //      Con_Printf("building portals for %s\n", loadmodel->name);
1878
1879         portalchain = NULL;
1880 //      Mod_MakeOutsidePortals (loadmodel->nodes);
1881         Mod_RecursiveNodePortals (loadmodel->nodes);
1882         Mod_FinalizePortals();
1883 }
1884
1885 /*
1886 =================
1887 Mod_LoadBrushModel
1888 =================
1889 */
1890 void Mod_LoadBrushModel (model_t *mod, void *buffer)
1891 {
1892         int                     i, j;
1893         dheader_t       *header;
1894         dmodel_t        *bm;
1895
1896         loadmodel->type = mod_brush;
1897
1898         header = (dheader_t *)buffer;
1899
1900         i = LittleLong (header->version);
1901         if (i != BSPVERSION && i != 30)
1902                 Host_Error ("Mod_LoadBrushModel: %s has wrong version number (%i should be %i or 30 (HalfLife))", mod->name, i, BSPVERSION);
1903         hlbsp = i == 30;
1904         halflifebsp.value = hlbsp;
1905
1906 // swap all the lumps
1907         mod_base = (byte *)header;
1908
1909         for (i=0 ; i<sizeof(dheader_t)/4 ; i++)
1910                 ((int *)header)[i] = LittleLong ( ((int *)header)[i]);
1911
1912 // load into heap
1913
1914         // LordHavoc: had to move entity loading above everything to allow parsing various settings from worldspawn
1915         Mod_LoadEntities (&header->lumps[LUMP_ENTITIES]);
1916
1917         Mod_LoadVertexes (&header->lumps[LUMP_VERTEXES]);
1918         Mod_LoadEdges (&header->lumps[LUMP_EDGES]);
1919         Mod_LoadSurfedges (&header->lumps[LUMP_SURFEDGES]);
1920         Mod_LoadTextures (&header->lumps[LUMP_TEXTURES]);
1921         Mod_LoadLighting (&header->lumps[LUMP_LIGHTING]);
1922         Mod_LoadPlanes (&header->lumps[LUMP_PLANES]);
1923         Mod_LoadTexinfo (&header->lumps[LUMP_TEXINFO]);
1924         Mod_LoadFaces (&header->lumps[LUMP_FACES]);
1925         Mod_LoadMarksurfaces (&header->lumps[LUMP_MARKSURFACES]);
1926         Mod_LoadVisibility (&header->lumps[LUMP_VISIBILITY]);
1927         Mod_LoadLeafs (&header->lumps[LUMP_LEAFS]);
1928         Mod_LoadNodes (&header->lumps[LUMP_NODES]);
1929         Mod_LoadClipnodes (&header->lumps[LUMP_CLIPNODES]);
1930 //      Mod_LoadEntities (&header->lumps[LUMP_ENTITIES]);
1931         Mod_LoadSubmodels (&header->lumps[LUMP_MODELS]);
1932
1933         Mod_MakeHull0 ();
1934
1935         Mod_MakePortals();
1936
1937         mod->numframes = 2;             // regular and alternate animation
1938
1939 //
1940 // set up the submodels (FIXME: this is confusing)
1941 //
1942         for (i = 0;i < mod->numsubmodels;i++)
1943         {
1944                 bm = &mod->submodels[i];
1945
1946                 mod->hulls[0].firstclipnode = bm->headnode[0];
1947                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
1948                 {
1949                         mod->hulls[j].firstclipnode = bm->headnode[j];
1950                         mod->hulls[j].lastclipnode = mod->numclipnodes - 1;
1951                 }
1952
1953                 mod->firstmodelsurface = bm->firstface;
1954                 mod->nummodelsurfaces = bm->numfaces;
1955
1956                 VectorCopy (bm->maxs, mod->maxs);
1957                 VectorCopy (bm->mins, mod->mins);
1958
1959                 mod->radius = RadiusFromBounds (mod->mins, mod->maxs);
1960
1961                 mod->numleafs = bm->visleafs;
1962
1963                 if (isworldmodel && i < (mod->numsubmodels - 1)) // LordHavoc: only register submodels if it is the world (prevents bsp models from replacing world submodels)
1964                 {       // duplicate the basic information
1965                         char    name[10];
1966
1967                         sprintf (name, "*%i", i+1);
1968                         loadmodel = Mod_FindName (name);
1969                         *loadmodel = *mod;
1970                         strcpy (loadmodel->name, name);
1971                         mod = loadmodel;
1972                 }
1973         }
1974 }