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