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