added mleaf_t->containscollisionsurfaces variable which indicates if the leafsurfaces...
[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 #include "r_shadow.h"
24 #include "polygon.h"
25 #include "curves.h"
26 #include "wad.h"
27
28
29 //cvar_t r_subdivide_size = {CVAR_SAVE, "r_subdivide_size", "128", "how large water polygons should be (smaller values produce more polygons which give better warping effects)"};
30 cvar_t halflifebsp = {0, "halflifebsp", "0", "indicates the current map is hlbsp format (useful to know because of different bounding box sizes)"};
31 cvar_t mcbsp = {0, "mcbsp", "0", "indicates the current map is mcbsp format (useful to know because of different bounding box sizes)"};
32 cvar_t r_novis = {0, "r_novis", "0", "draws whole level, see also sv_cullentities_pvs 0"};
33 cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1", "whether to use RGBA (32bit) or RGB (24bit) lightmaps"};
34 cvar_t r_nosurftextures = {0, "r_nosurftextures", "0", "pretends there was no texture lump found in the q1bsp/hlbsp loading (useful for debugging this rare case)"};
35 cvar_t r_subdivisions_tolerance = {0, "r_subdivisions_tolerance", "4", "maximum error tolerance on curve subdivision for rendering purposes (in other words, the curves will be given as many polygons as necessary to represent curves at this quality)"};
36 cvar_t r_subdivisions_mintess = {0, "r_subdivisions_mintess", "1", "minimum number of subdivisions (values above 1 will smooth curves that don't need it)"};
37 cvar_t r_subdivisions_maxtess = {0, "r_subdivisions_maxtess", "1024", "maximum number of subdivisions (prevents curves beyond a certain detail level, limits smoothing)"};
38 cvar_t r_subdivisions_maxvertices = {0, "r_subdivisions_maxvertices", "65536", "maximum vertices allowed per subdivided curve"};
39 cvar_t r_subdivisions_collision_tolerance = {0, "r_subdivisions_collision_tolerance", "15", "maximum error tolerance on curve subdivision for collision purposes (usually a larger error tolerance than for rendering)"};
40 cvar_t r_subdivisions_collision_mintess = {0, "r_subdivisions_collision_mintess", "1", "minimum number of subdivisions (values above 1 will smooth curves that don't need it)"};
41 cvar_t r_subdivisions_collision_maxtess = {0, "r_subdivisions_collision_maxtess", "1024", "maximum number of subdivisions (prevents curves beyond a certain detail level, limits smoothing)"};
42 cvar_t r_subdivisions_collision_maxvertices = {0, "r_subdivisions_collision_maxvertices", "4225", "maximum vertices allowed per subdivided curve"};
43 cvar_t mod_q3bsp_curves_collisions = {0, "mod_q3bsp_curves_collisions", "1", "enables collisions with curves (SLOW)"};
44 cvar_t mod_q3bsp_optimizedtraceline = {0, "mod_q3bsp_optimizedtraceline", "1", "whether to use optimized traceline code for line traces (as opposed to tracebox code)"};
45 cvar_t mod_q3bsp_debugtracebrush = {0, "mod_q3bsp_debugtracebrush", "0", "selects different tracebrush bsp recursion algorithms (for debugging purposes only)"};
46
47 static texture_t mod_q1bsp_texture_solid;
48 static texture_t mod_q1bsp_texture_sky;
49 static texture_t mod_q1bsp_texture_lava;
50 static texture_t mod_q1bsp_texture_slime;
51 static texture_t mod_q1bsp_texture_water;
52
53 void Mod_BrushInit(void)
54 {
55 //      Cvar_RegisterVariable(&r_subdivide_size);
56         Cvar_RegisterVariable(&halflifebsp);
57         Cvar_RegisterVariable(&mcbsp);
58         Cvar_RegisterVariable(&r_novis);
59         Cvar_RegisterVariable(&r_lightmaprgba);
60         Cvar_RegisterVariable(&r_nosurftextures);
61         Cvar_RegisterVariable(&r_subdivisions_tolerance);
62         Cvar_RegisterVariable(&r_subdivisions_mintess);
63         Cvar_RegisterVariable(&r_subdivisions_maxtess);
64         Cvar_RegisterVariable(&r_subdivisions_maxvertices);
65         Cvar_RegisterVariable(&r_subdivisions_collision_tolerance);
66         Cvar_RegisterVariable(&r_subdivisions_collision_mintess);
67         Cvar_RegisterVariable(&r_subdivisions_collision_maxtess);
68         Cvar_RegisterVariable(&r_subdivisions_collision_maxvertices);
69         Cvar_RegisterVariable(&mod_q3bsp_curves_collisions);
70         Cvar_RegisterVariable(&mod_q3bsp_optimizedtraceline);
71         Cvar_RegisterVariable(&mod_q3bsp_debugtracebrush);
72
73         memset(&mod_q1bsp_texture_solid, 0, sizeof(mod_q1bsp_texture_solid));
74         strlcpy(mod_q1bsp_texture_solid.name, "solid" , sizeof(mod_q1bsp_texture_solid.name));
75         mod_q1bsp_texture_solid.surfaceflags = 0;
76         mod_q1bsp_texture_solid.supercontents = SUPERCONTENTS_SOLID;
77
78         mod_q1bsp_texture_sky = mod_q1bsp_texture_solid;
79         strlcpy(mod_q1bsp_texture_sky.name, "sky", sizeof(mod_q1bsp_texture_sky.name));
80         mod_q1bsp_texture_sky.surfaceflags = Q3SURFACEFLAG_SKY | Q3SURFACEFLAG_NOIMPACT | Q3SURFACEFLAG_NOMARKS | Q3SURFACEFLAG_NODLIGHT | Q3SURFACEFLAG_NOLIGHTMAP;
81         mod_q1bsp_texture_sky.supercontents = SUPERCONTENTS_SKY | SUPERCONTENTS_NODROP;
82
83         mod_q1bsp_texture_lava = mod_q1bsp_texture_solid;
84         strlcpy(mod_q1bsp_texture_lava.name, "*lava", sizeof(mod_q1bsp_texture_lava.name));
85         mod_q1bsp_texture_lava.surfaceflags = Q3SURFACEFLAG_NOMARKS;
86         mod_q1bsp_texture_lava.supercontents = SUPERCONTENTS_LAVA | SUPERCONTENTS_NODROP;
87
88         mod_q1bsp_texture_slime = mod_q1bsp_texture_solid;
89         strlcpy(mod_q1bsp_texture_slime.name, "*slime", sizeof(mod_q1bsp_texture_slime.name));
90         mod_q1bsp_texture_slime.surfaceflags = Q3SURFACEFLAG_NOMARKS;
91         mod_q1bsp_texture_slime.supercontents = SUPERCONTENTS_SLIME;
92
93         mod_q1bsp_texture_water = mod_q1bsp_texture_solid;
94         strlcpy(mod_q1bsp_texture_water.name, "*water", sizeof(mod_q1bsp_texture_water.name));
95         mod_q1bsp_texture_water.surfaceflags = Q3SURFACEFLAG_NOMARKS;
96         mod_q1bsp_texture_water.supercontents = SUPERCONTENTS_WATER;
97 }
98
99 static mleaf_t *Mod_Q1BSP_PointInLeaf(model_t *model, const vec3_t p)
100 {
101         mnode_t *node;
102
103         if (model == NULL)
104                 return NULL;
105
106         // LordHavoc: modified to start at first clip node,
107         // in other words: first node of the (sub)model
108         node = model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode;
109         while (node->plane)
110                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
111
112         return (mleaf_t *)node;
113 }
114
115 static void Mod_Q1BSP_AmbientSoundLevelsForPoint(model_t *model, const vec3_t p, unsigned char *out, int outsize)
116 {
117         int i;
118         mleaf_t *leaf;
119         leaf = Mod_Q1BSP_PointInLeaf(model, p);
120         if (leaf)
121         {
122                 i = min(outsize, (int)sizeof(leaf->ambient_sound_level));
123                 if (i)
124                 {
125                         memcpy(out, leaf->ambient_sound_level, i);
126                         out += i;
127                         outsize -= i;
128                 }
129         }
130         if (outsize)
131                 memset(out, 0, outsize);
132 }
133
134 static int Mod_Q1BSP_FindBoxClusters(model_t *model, const vec3_t mins, const vec3_t maxs, int maxclusters, int *clusterlist)
135 {
136         int numclusters = 0;
137         int nodestackindex = 0;
138         mnode_t *node, *nodestack[1024];
139         if (!model->brush.num_pvsclusters)
140                 return -1;
141         node = model->brush.data_nodes;
142         for (;;)
143         {
144 #if 1
145                 if (node->plane)
146                 {
147                         // node - recurse down the BSP tree
148                         int sides = BoxOnPlaneSide(mins, maxs, node->plane);
149                         if (sides < 3)
150                         {
151                                 if (sides == 0)
152                                         return -1; // ERROR: NAN bounding box!
153                                 // box is on one side of plane, take that path
154                                 node = node->children[sides-1];
155                         }
156                         else
157                         {
158                                 // box crosses plane, take one path and remember the other
159                                 if (nodestackindex < 1024)
160                                         nodestack[nodestackindex++] = node->children[0];
161                                 node = node->children[1];
162                         }
163                         continue;
164                 }
165                 else
166                 {
167                         // leaf - add clusterindex to list
168                         if (numclusters < maxclusters)
169                                 clusterlist[numclusters] = ((mleaf_t *)node)->clusterindex;
170                         numclusters++;
171                 }
172 #else
173                 if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
174                 {
175                         if (node->plane)
176                         {
177                                 if (nodestackindex < 1024)
178                                         nodestack[nodestackindex++] = node->children[0];
179                                 node = node->children[1];
180                                 continue;
181                         }
182                         else
183                         {
184                                 // leaf - add clusterindex to list
185                                 if (numclusters < maxclusters)
186                                         clusterlist[numclusters] = ((mleaf_t *)node)->clusterindex;
187                                 numclusters++;
188                         }
189                 }
190 #endif
191                 // try another path we didn't take earlier
192                 if (nodestackindex == 0)
193                         break;
194                 node = nodestack[--nodestackindex];
195         }
196         // return number of clusters found (even if more than the maxclusters)
197         return numclusters;
198 }
199
200 static int Mod_Q1BSP_BoxTouchingPVS(model_t *model, const unsigned char *pvs, const vec3_t mins, const vec3_t maxs)
201 {
202         int nodestackindex = 0;
203         mnode_t *node, *nodestack[1024];
204         if (!model->brush.num_pvsclusters)
205                 return true;
206         node = model->brush.data_nodes;
207         for (;;)
208         {
209 #if 1
210                 if (node->plane)
211                 {
212                         // node - recurse down the BSP tree
213                         int sides = BoxOnPlaneSide(mins, maxs, node->plane);
214                         if (sides < 3)
215                         {
216                                 if (sides == 0)
217                                         return -1; // ERROR: NAN bounding box!
218                                 // box is on one side of plane, take that path
219                                 node = node->children[sides-1];
220                         }
221                         else
222                         {
223                                 // box crosses plane, take one path and remember the other
224                                 if (nodestackindex < 1024)
225                                         nodestack[nodestackindex++] = node->children[0];
226                                 node = node->children[1];
227                         }
228                         continue;
229                 }
230                 else
231                 {
232                         // leaf - check cluster bit
233                         int clusterindex = ((mleaf_t *)node)->clusterindex;
234                         if (CHECKPVSBIT(pvs, clusterindex))
235                         {
236                                 // it is visible, return immediately with the news
237                                 return true;
238                         }
239                 }
240 #else
241                 if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
242                 {
243                         if (node->plane)
244                         {
245                                 if (nodestackindex < 1024)
246                                         nodestack[nodestackindex++] = node->children[0];
247                                 node = node->children[1];
248                                 continue;
249                         }
250                         else
251                         {
252                                 // leaf - check cluster bit
253                                 int clusterindex = ((mleaf_t *)node)->clusterindex;
254                                 if (CHECKPVSBIT(pvs, clusterindex))
255                                 {
256                                         // it is visible, return immediately with the news
257                                         return true;
258                                 }
259                         }
260                 }
261 #endif
262                 // nothing to see here, try another path we didn't take earlier
263                 if (nodestackindex == 0)
264                         break;
265                 node = nodestack[--nodestackindex];
266         }
267         // it is not visible
268         return false;
269 }
270
271 static int Mod_Q1BSP_BoxTouchingLeafPVS(model_t *model, const unsigned char *pvs, const vec3_t mins, const vec3_t maxs)
272 {
273         int nodestackindex = 0;
274         mnode_t *node, *nodestack[1024];
275         if (!model->brush.num_leafs)
276                 return true;
277         node = model->brush.data_nodes;
278         for (;;)
279         {
280 #if 1
281                 if (node->plane)
282                 {
283                         // node - recurse down the BSP tree
284                         int sides = BoxOnPlaneSide(mins, maxs, node->plane);
285                         if (sides < 3)
286                         {
287                                 if (sides == 0)
288                                         return -1; // ERROR: NAN bounding box!
289                                 // box is on one side of plane, take that path
290                                 node = node->children[sides-1];
291                         }
292                         else
293                         {
294                                 // box crosses plane, take one path and remember the other
295                                 if (nodestackindex < 1024)
296                                         nodestack[nodestackindex++] = node->children[0];
297                                 node = node->children[1];
298                         }
299                         continue;
300                 }
301                 else
302                 {
303                         // leaf - check cluster bit
304                         int clusterindex = ((mleaf_t *)node) - model->brush.data_leafs;
305                         if (CHECKPVSBIT(pvs, clusterindex))
306                         {
307                                 // it is visible, return immediately with the news
308                                 return true;
309                         }
310                 }
311 #else
312                 if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
313                 {
314                         if (node->plane)
315                         {
316                                 if (nodestackindex < 1024)
317                                         nodestack[nodestackindex++] = node->children[0];
318                                 node = node->children[1];
319                                 continue;
320                         }
321                         else
322                         {
323                                 // leaf - check cluster bit
324                                 int clusterindex = ((mleaf_t *)node) - model->brush.data_leafs;
325                                 if (CHECKPVSBIT(pvs, clusterindex))
326                                 {
327                                         // it is visible, return immediately with the news
328                                         return true;
329                                 }
330                         }
331                 }
332 #endif
333                 // nothing to see here, try another path we didn't take earlier
334                 if (nodestackindex == 0)
335                         break;
336                 node = nodestack[--nodestackindex];
337         }
338         // it is not visible
339         return false;
340 }
341
342 static int Mod_Q1BSP_BoxTouchingVisibleLeafs(model_t *model, const unsigned char *visibleleafs, const vec3_t mins, const vec3_t maxs)
343 {
344         int nodestackindex = 0;
345         mnode_t *node, *nodestack[1024];
346         if (!model->brush.num_leafs)
347                 return true;
348         node = model->brush.data_nodes;
349         for (;;)
350         {
351 #if 1
352                 if (node->plane)
353                 {
354                         // node - recurse down the BSP tree
355                         int sides = BoxOnPlaneSide(mins, maxs, node->plane);
356                         if (sides < 3)
357                         {
358                                 if (sides == 0)
359                                         return -1; // ERROR: NAN bounding box!
360                                 // box is on one side of plane, take that path
361                                 node = node->children[sides-1];
362                         }
363                         else
364                         {
365                                 // box crosses plane, take one path and remember the other
366                                 if (nodestackindex < 1024)
367                                         nodestack[nodestackindex++] = node->children[0];
368                                 node = node->children[1];
369                         }
370                         continue;
371                 }
372                 else
373                 {
374                         // leaf - check if it is visible
375                         if (visibleleafs[(mleaf_t *)node - model->brush.data_leafs])
376                         {
377                                 // it is visible, return immediately with the news
378                                 return true;
379                         }
380                 }
381 #else
382                 if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
383                 {
384                         if (node->plane)
385                         {
386                                 if (nodestackindex < 1024)
387                                         nodestack[nodestackindex++] = node->children[0];
388                                 node = node->children[1];
389                                 continue;
390                         }
391                         else
392                         {
393                                 // leaf - check if it is visible
394                                 if (visibleleafs[(mleaf_t *)node - model->brush.data_leafs])
395                                 {
396                                         // it is visible, return immediately with the news
397                                         return true;
398                                 }
399                         }
400                 }
401 #endif
402                 // nothing to see here, try another path we didn't take earlier
403                 if (nodestackindex == 0)
404                         break;
405                 node = nodestack[--nodestackindex];
406         }
407         // it is not visible
408         return false;
409 }
410
411 typedef struct findnonsolidlocationinfo_s
412 {
413         vec3_t center;
414         vec_t radius;
415         vec3_t nudge;
416         vec_t bestdist;
417         model_t *model;
418 }
419 findnonsolidlocationinfo_t;
420
421 static void Mod_Q1BSP_FindNonSolidLocation_r_Leaf(findnonsolidlocationinfo_t *info, mleaf_t *leaf)
422 {
423         int i, surfacenum, k, *tri, *mark;
424         float dist, f, vert[3][3], edge[3][3], facenormal[3], edgenormal[3][3], point[3];
425         msurface_t *surface;
426         for (surfacenum = 0, mark = leaf->firstleafsurface;surfacenum < leaf->numleafsurfaces;surfacenum++, mark++)
427         {
428                 surface = info->model->data_surfaces + *mark;
429                 if (surface->texture->supercontents & SUPERCONTENTS_SOLID)
430                 {
431                         for (k = 0;k < surface->num_triangles;k++)
432                         {
433                                 tri = (info->model->surfmesh.data_element3i + 3 * surface->num_firsttriangle) + k * 3;
434                                 VectorCopy((info->model->surfmesh.data_vertex3f + tri[0] * 3), vert[0]);
435                                 VectorCopy((info->model->surfmesh.data_vertex3f + tri[1] * 3), vert[1]);
436                                 VectorCopy((info->model->surfmesh.data_vertex3f + tri[2] * 3), vert[2]);
437                                 VectorSubtract(vert[1], vert[0], edge[0]);
438                                 VectorSubtract(vert[2], vert[1], edge[1]);
439                                 CrossProduct(edge[1], edge[0], facenormal);
440                                 if (facenormal[0] || facenormal[1] || facenormal[2])
441                                 {
442                                         VectorNormalize(facenormal);
443                                         f = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
444                                         if (f <= info->bestdist && f >= -info->bestdist)
445                                         {
446                                                 VectorSubtract(vert[0], vert[2], edge[2]);
447                                                 VectorNormalize(edge[0]);
448                                                 VectorNormalize(edge[1]);
449                                                 VectorNormalize(edge[2]);
450                                                 CrossProduct(facenormal, edge[0], edgenormal[0]);
451                                                 CrossProduct(facenormal, edge[1], edgenormal[1]);
452                                                 CrossProduct(facenormal, edge[2], edgenormal[2]);
453                                                 // face distance
454                                                 if (DotProduct(info->center, edgenormal[0]) < DotProduct(vert[0], edgenormal[0])
455                                                  && DotProduct(info->center, edgenormal[1]) < DotProduct(vert[1], edgenormal[1])
456                                                  && DotProduct(info->center, edgenormal[2]) < DotProduct(vert[2], edgenormal[2]))
457                                                 {
458                                                         // we got lucky, the center is within the face
459                                                         dist = DotProduct(info->center, facenormal) - DotProduct(vert[0], facenormal);
460                                                         if (dist < 0)
461                                                         {
462                                                                 dist = -dist;
463                                                                 if (info->bestdist > dist)
464                                                                 {
465                                                                         info->bestdist = dist;
466                                                                         VectorScale(facenormal, (info->radius - -dist), info->nudge);
467                                                                 }
468                                                         }
469                                                         else
470                                                         {
471                                                                 if (info->bestdist > dist)
472                                                                 {
473                                                                         info->bestdist = dist;
474                                                                         VectorScale(facenormal, (info->radius - dist), info->nudge);
475                                                                 }
476                                                         }
477                                                 }
478                                                 else
479                                                 {
480                                                         // check which edge or vertex the center is nearest
481                                                         for (i = 0;i < 3;i++)
482                                                         {
483                                                                 f = DotProduct(info->center, edge[i]);
484                                                                 if (f >= DotProduct(vert[0], edge[i])
485                                                                  && f <= DotProduct(vert[1], edge[i]))
486                                                                 {
487                                                                         // on edge
488                                                                         VectorMA(info->center, -f, edge[i], point);
489                                                                         dist = sqrt(DotProduct(point, point));
490                                                                         if (info->bestdist > dist)
491                                                                         {
492                                                                                 info->bestdist = dist;
493                                                                                 VectorScale(point, (info->radius / dist), info->nudge);
494                                                                         }
495                                                                         // skip both vertex checks
496                                                                         // (both are further away than this edge)
497                                                                         i++;
498                                                                 }
499                                                                 else
500                                                                 {
501                                                                         // not on edge, check first vertex of edge
502                                                                         VectorSubtract(info->center, vert[i], point);
503                                                                         dist = sqrt(DotProduct(point, point));
504                                                                         if (info->bestdist > dist)
505                                                                         {
506                                                                                 info->bestdist = dist;
507                                                                                 VectorScale(point, (info->radius / dist), info->nudge);
508                                                                         }
509                                                                 }
510                                                         }
511                                                 }
512                                         }
513                                 }
514                         }
515                 }
516         }
517 }
518
519 static void Mod_Q1BSP_FindNonSolidLocation_r(findnonsolidlocationinfo_t *info, mnode_t *node)
520 {
521         if (node->plane)
522         {
523                 float f = PlaneDiff(info->center, node->plane);
524                 if (f >= -info->bestdist)
525                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[0]);
526                 if (f <= info->bestdist)
527                         Mod_Q1BSP_FindNonSolidLocation_r(info, node->children[1]);
528         }
529         else
530         {
531                 if (((mleaf_t *)node)->numleafsurfaces)
532                         Mod_Q1BSP_FindNonSolidLocation_r_Leaf(info, (mleaf_t *)node);
533         }
534 }
535
536 static void Mod_Q1BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, float radius)
537 {
538         int i;
539         findnonsolidlocationinfo_t info;
540         if (model == NULL)
541         {
542                 VectorCopy(in, out);
543                 return;
544         }
545         VectorCopy(in, info.center);
546         info.radius = radius;
547         info.model = model;
548         i = 0;
549         do
550         {
551                 VectorClear(info.nudge);
552                 info.bestdist = radius;
553                 Mod_Q1BSP_FindNonSolidLocation_r(&info, model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode);
554                 VectorAdd(info.center, info.nudge, info.center);
555         }
556         while (info.bestdist < radius && ++i < 10);
557         VectorCopy(info.center, out);
558 }
559
560 int Mod_Q1BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents)
561 {
562         switch(nativecontents)
563         {
564                 case CONTENTS_EMPTY:
565                         return 0;
566                 case CONTENTS_SOLID:
567                         return SUPERCONTENTS_SOLID;
568                 case CONTENTS_WATER:
569                         return SUPERCONTENTS_WATER;
570                 case CONTENTS_SLIME:
571                         return SUPERCONTENTS_SLIME;
572                 case CONTENTS_LAVA:
573                         return SUPERCONTENTS_LAVA | SUPERCONTENTS_NODROP;
574                 case CONTENTS_SKY:
575                         return SUPERCONTENTS_SKY | SUPERCONTENTS_NODROP;
576         }
577         return 0;
578 }
579
580 int Mod_Q1BSP_NativeContentsFromSuperContents(model_t *model, int supercontents)
581 {
582         if (supercontents & (SUPERCONTENTS_SOLID | SUPERCONTENTS_BODY))
583                 return CONTENTS_SOLID;
584         if (supercontents & SUPERCONTENTS_SKY)
585                 return CONTENTS_SKY;
586         if (supercontents & SUPERCONTENTS_LAVA)
587                 return CONTENTS_LAVA;
588         if (supercontents & SUPERCONTENTS_SLIME)
589                 return CONTENTS_SLIME;
590         if (supercontents & SUPERCONTENTS_WATER)
591                 return CONTENTS_WATER;
592         return CONTENTS_EMPTY;
593 }
594
595 typedef struct RecursiveHullCheckTraceInfo_s
596 {
597         // the hull we're tracing through
598         const hull_t *hull;
599
600         // the trace structure to fill in
601         trace_t *trace;
602
603         // start, end, and end - start (in model space)
604         double start[3];
605         double end[3];
606         double dist[3];
607 }
608 RecursiveHullCheckTraceInfo_t;
609
610 // 1/32 epsilon to keep floating point happy
611 #define DIST_EPSILON (0.03125)
612
613 #define HULLCHECKSTATE_EMPTY 0
614 #define HULLCHECKSTATE_SOLID 1
615 #define HULLCHECKSTATE_DONE 2
616
617 extern cvar_t collision_prefernudgedfraction;
618 static int Mod_Q1BSP_RecursiveHullCheck(RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, double p1[3], double p2[3])
619 {
620         // status variables, these don't need to be saved on the stack when
621         // recursing...  but are because this should be thread-safe
622         // (note: tracing against a bbox is not thread-safe, yet)
623         int ret;
624         mplane_t *plane;
625         double t1, t2;
626
627         // variables that need to be stored on the stack when recursing
628         dclipnode_t *node;
629         int side;
630         double midf, mid[3];
631
632         // LordHavoc: a goto!  everyone flee in terror... :)
633 loc0:
634         // check for empty
635         if (num < 0)
636         {
637                 num = Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num);
638                 if (!t->trace->startfound)
639                 {
640                         t->trace->startfound = true;
641                         t->trace->startsupercontents |= num;
642                 }
643                 if (num & SUPERCONTENTS_LIQUIDSMASK)
644                         t->trace->inwater = true;
645                 if (num == 0)
646                         t->trace->inopen = true;
647                 if (num & SUPERCONTENTS_SOLID)
648                         t->trace->hittexture = &mod_q1bsp_texture_solid;
649                 else if (num & SUPERCONTENTS_SKY)
650                         t->trace->hittexture = &mod_q1bsp_texture_sky;
651                 else if (num & SUPERCONTENTS_LAVA)
652                         t->trace->hittexture = &mod_q1bsp_texture_lava;
653                 else if (num & SUPERCONTENTS_SLIME)
654                         t->trace->hittexture = &mod_q1bsp_texture_slime;
655                 else
656                         t->trace->hittexture = &mod_q1bsp_texture_water;
657                 t->trace->hitq3surfaceflags = t->trace->hittexture->surfaceflags;
658                 t->trace->hitsupercontents = num;
659                 if (num & t->trace->hitsupercontentsmask)
660                 {
661                         // if the first leaf is solid, set startsolid
662                         if (t->trace->allsolid)
663                                 t->trace->startsolid = true;
664 #if COLLISIONPARANOID >= 3
665                         Con_Print("S");
666 #endif
667                         return HULLCHECKSTATE_SOLID;
668                 }
669                 else
670                 {
671                         t->trace->allsolid = false;
672 #if COLLISIONPARANOID >= 3
673                         Con_Print("E");
674 #endif
675                         return HULLCHECKSTATE_EMPTY;
676                 }
677         }
678
679         // find the point distances
680         node = t->hull->clipnodes + num;
681
682         plane = t->hull->planes + node->planenum;
683         if (plane->type < 3)
684         {
685                 t1 = p1[plane->type] - plane->dist;
686                 t2 = p2[plane->type] - plane->dist;
687         }
688         else
689         {
690                 t1 = DotProduct (plane->normal, p1) - plane->dist;
691                 t2 = DotProduct (plane->normal, p2) - plane->dist;
692         }
693
694         if (t1 < 0)
695         {
696                 if (t2 < 0)
697                 {
698 #if COLLISIONPARANOID >= 3
699                         Con_Print("<");
700 #endif
701                         num = node->children[1];
702                         goto loc0;
703                 }
704                 side = 1;
705         }
706         else
707         {
708                 if (t2 >= 0)
709                 {
710 #if COLLISIONPARANOID >= 3
711                         Con_Print(">");
712 #endif
713                         num = node->children[0];
714                         goto loc0;
715                 }
716                 side = 0;
717         }
718
719         // the line intersects, find intersection point
720         // LordHavoc: this uses the original trace for maximum accuracy
721 #if COLLISIONPARANOID >= 3
722         Con_Print("M");
723 #endif
724         if (plane->type < 3)
725         {
726                 t1 = t->start[plane->type] - plane->dist;
727                 t2 = t->end[plane->type] - plane->dist;
728         }
729         else
730         {
731                 t1 = DotProduct (plane->normal, t->start) - plane->dist;
732                 t2 = DotProduct (plane->normal, t->end) - plane->dist;
733         }
734
735         midf = t1 / (t1 - t2);
736         midf = bound(p1f, midf, p2f);
737         VectorMA(t->start, midf, t->dist, mid);
738
739         // recurse both sides, front side first
740         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side], p1f, midf, p1, mid);
741         // if this side is not empty, return what it is (solid or done)
742         if (ret != HULLCHECKSTATE_EMPTY)
743                 return ret;
744
745         ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side ^ 1], midf, p2f, mid, p2);
746         // if other side is not solid, return what it is (empty or done)
747         if (ret != HULLCHECKSTATE_SOLID)
748                 return ret;
749
750         // front is air and back is solid, this is the impact point...
751         if (side)
752         {
753                 t->trace->plane.dist = -plane->dist;
754                 VectorNegate (plane->normal, t->trace->plane.normal);
755         }
756         else
757         {
758                 t->trace->plane.dist = plane->dist;
759                 VectorCopy (plane->normal, t->trace->plane.normal);
760         }
761
762         // calculate the true fraction
763         t1 = DotProduct(t->trace->plane.normal, t->start) - t->trace->plane.dist;
764         t2 = DotProduct(t->trace->plane.normal, t->end) - t->trace->plane.dist;
765         midf = t1 / (t1 - t2);
766         t->trace->realfraction = bound(0, midf, 1);
767
768         // calculate the return fraction which is nudged off the surface a bit
769         midf = (t1 - DIST_EPSILON) / (t1 - t2);
770         t->trace->fraction = bound(0, midf, 1);
771
772         if (collision_prefernudgedfraction.integer)
773                 t->trace->realfraction = t->trace->fraction;
774
775 #if COLLISIONPARANOID >= 3
776         Con_Print("D");
777 #endif
778         return HULLCHECKSTATE_DONE;
779 }
780
781 //#if COLLISIONPARANOID < 2
782 static int Mod_Q1BSP_RecursiveHullCheckPoint(RecursiveHullCheckTraceInfo_t *t, int num)
783 {
784         while (num >= 0)
785                 num = t->hull->clipnodes[num].children[(t->hull->planes[t->hull->clipnodes[num].planenum].type < 3 ? t->start[t->hull->planes[t->hull->clipnodes[num].planenum].type] : DotProduct(t->hull->planes[t->hull->clipnodes[num].planenum].normal, t->start)) < t->hull->planes[t->hull->clipnodes[num].planenum].dist];
786         num = Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num);
787         t->trace->startsupercontents |= num;
788         if (num & SUPERCONTENTS_LIQUIDSMASK)
789                 t->trace->inwater = true;
790         if (num == 0)
791                 t->trace->inopen = true;
792         if (num & t->trace->hitsupercontentsmask)
793         {
794                 t->trace->allsolid = t->trace->startsolid = true;
795                 return HULLCHECKSTATE_SOLID;
796         }
797         else
798         {
799                 t->trace->allsolid = t->trace->startsolid = false;
800                 return HULLCHECKSTATE_EMPTY;
801         }
802 }
803 //#endif
804
805 static void Mod_Q1BSP_TraceBox(struct model_s *model, int frame, trace_t *trace, const vec3_t start, const vec3_t boxmins, const vec3_t boxmaxs, const vec3_t end, int hitsupercontentsmask)
806 {
807         // this function currently only supports same size start and end
808         double boxsize[3];
809         RecursiveHullCheckTraceInfo_t rhc;
810
811         memset(&rhc, 0, sizeof(rhc));
812         memset(trace, 0, sizeof(trace_t));
813         rhc.trace = trace;
814         rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
815         rhc.trace->fraction = 1;
816         rhc.trace->realfraction = 1;
817         rhc.trace->allsolid = true;
818         VectorSubtract(boxmaxs, boxmins, boxsize);
819         if (boxsize[0] < 3)
820                 rhc.hull = &model->brushq1.hulls[0]; // 0x0x0
821         else if (model->brush.ismcbsp)
822         {
823                 if (boxsize[2] < 48) // pick the nearest of 40 or 56
824                         rhc.hull = &model->brushq1.hulls[2]; // 16x16x40
825                 else
826                         rhc.hull = &model->brushq1.hulls[1]; // 16x16x56
827         }
828         else if (model->brush.ishlbsp)
829         {
830                 // LordHavoc: this has to have a minor tolerance (the .1) because of
831                 // minor float precision errors from the box being transformed around
832                 if (boxsize[0] < 32.1)
833                 {
834                         if (boxsize[2] < 54) // pick the nearest of 36 or 72
835                                 rhc.hull = &model->brushq1.hulls[3]; // 32x32x36
836                         else
837                                 rhc.hull = &model->brushq1.hulls[1]; // 32x32x72
838                 }
839                 else
840                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x64
841         }
842         else
843         {
844                 // LordHavoc: this has to have a minor tolerance (the .1) because of
845                 // minor float precision errors from the box being transformed around
846                 if (boxsize[0] < 32.1)
847                         rhc.hull = &model->brushq1.hulls[1]; // 32x32x56
848                 else
849                         rhc.hull = &model->brushq1.hulls[2]; // 64x64x88
850         }
851         VectorMAMAM(1, start, 1, boxmins, -1, rhc.hull->clip_mins, rhc.start);
852         VectorMAMAM(1, end, 1, boxmins, -1, rhc.hull->clip_mins, rhc.end);
853         VectorSubtract(rhc.end, rhc.start, rhc.dist);
854 #if COLLISIONPARANOID >= 2
855         Con_Printf("t(%f %f %f,%f %f %f,%i %f %f %f)", rhc.start[0], rhc.start[1], rhc.start[2], rhc.end[0], rhc.end[1], rhc.end[2], rhc.hull - model->brushq1.hulls, rhc.hull->clip_mins[0], rhc.hull->clip_mins[1], rhc.hull->clip_mins[2]);
856         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
857         {
858
859                 double test[3];
860                 trace_t testtrace;
861                 VectorLerp(rhc.start, rhc.trace->fraction, rhc.end, test);
862                 memset(&testtrace, 0, sizeof(trace_t));
863                 rhc.trace = &testtrace;
864                 rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
865                 rhc.trace->fraction = 1;
866                 rhc.trace->realfraction = 1;
867                 rhc.trace->allsolid = true;
868                 VectorCopy(test, rhc.start);
869                 VectorCopy(test, rhc.end);
870                 VectorClear(rhc.dist);
871                 Mod_Q1BSP_RecursiveHullCheckPoint(&rhc, rhc.hull->firstclipnode);
872                 //Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, test, test);
873                 if (!trace->startsolid && testtrace.startsolid)
874                         Con_Printf(" - ended in solid!\n");
875         }
876         Con_Print("\n");
877 #else
878         if (VectorLength2(rhc.dist))
879                 Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
880         else
881                 Mod_Q1BSP_RecursiveHullCheckPoint(&rhc, rhc.hull->firstclipnode);
882 #endif
883 }
884
885 void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, texture_t *boxtexture)
886 {
887 #if 1
888         colbrushf_t cbox;
889         colplanef_t cbox_planes[6];
890         cbox.supercontents = boxsupercontents;
891         cbox.numplanes = 6;
892         cbox.numpoints = 0;
893         cbox.numtriangles = 0;
894         cbox.planes = cbox_planes;
895         cbox.points = NULL;
896         cbox.elements = NULL;
897         cbox.markframe = 0;
898         cbox.mins[0] = 0;
899         cbox.mins[1] = 0;
900         cbox.mins[2] = 0;
901         cbox.maxs[0] = 0;
902         cbox.maxs[1] = 0;
903         cbox.maxs[2] = 0;
904         cbox_planes[0].normal[0] =  1;cbox_planes[0].normal[1] =  0;cbox_planes[0].normal[2] =  0;cbox_planes[0].dist = cmaxs[0] - mins[0];
905         cbox_planes[1].normal[0] = -1;cbox_planes[1].normal[1] =  0;cbox_planes[1].normal[2] =  0;cbox_planes[1].dist = maxs[0] - cmins[0];
906         cbox_planes[2].normal[0] =  0;cbox_planes[2].normal[1] =  1;cbox_planes[2].normal[2] =  0;cbox_planes[2].dist = cmaxs[1] - mins[1];
907         cbox_planes[3].normal[0] =  0;cbox_planes[3].normal[1] = -1;cbox_planes[3].normal[2] =  0;cbox_planes[3].dist = maxs[1] - cmins[1];
908         cbox_planes[4].normal[0] =  0;cbox_planes[4].normal[1] =  0;cbox_planes[4].normal[2] =  1;cbox_planes[4].dist = cmaxs[2] - mins[2];
909         cbox_planes[5].normal[0] =  0;cbox_planes[5].normal[1] =  0;cbox_planes[5].normal[2] = -1;cbox_planes[5].dist = maxs[2] - cmins[2];
910         cbox_planes[0].q3surfaceflags = boxq3surfaceflags;cbox_planes[0].texture = boxtexture;
911         cbox_planes[1].q3surfaceflags = boxq3surfaceflags;cbox_planes[1].texture = boxtexture;
912         cbox_planes[2].q3surfaceflags = boxq3surfaceflags;cbox_planes[2].texture = boxtexture;
913         cbox_planes[3].q3surfaceflags = boxq3surfaceflags;cbox_planes[3].texture = boxtexture;
914         cbox_planes[4].q3surfaceflags = boxq3surfaceflags;cbox_planes[4].texture = boxtexture;
915         cbox_planes[5].q3surfaceflags = boxq3surfaceflags;cbox_planes[5].texture = boxtexture;
916         memset(trace, 0, sizeof(trace_t));
917         trace->hitsupercontentsmask = hitsupercontentsmask;
918         trace->fraction = 1;
919         trace->realfraction = 1;
920         Collision_TraceLineBrushFloat(trace, start, end, &cbox, &cbox);
921 #else
922         RecursiveHullCheckTraceInfo_t rhc;
923         static hull_t box_hull;
924         static dclipnode_t box_clipnodes[6];
925         static mplane_t box_planes[6];
926         // fill in a default trace
927         memset(&rhc, 0, sizeof(rhc));
928         memset(trace, 0, sizeof(trace_t));
929         //To keep everything totally uniform, bounding boxes are turned into small
930         //BSP trees instead of being compared directly.
931         // create a temp hull from bounding box sizes
932         box_planes[0].dist = cmaxs[0] - mins[0];
933         box_planes[1].dist = cmins[0] - maxs[0];
934         box_planes[2].dist = cmaxs[1] - mins[1];
935         box_planes[3].dist = cmins[1] - maxs[1];
936         box_planes[4].dist = cmaxs[2] - mins[2];
937         box_planes[5].dist = cmins[2] - maxs[2];
938 #if COLLISIONPARANOID >= 3
939         Con_Printf("box_planes %f:%f %f:%f %f:%f\ncbox %f %f %f:%f %f %f\nbox %f %f %f:%f %f %f\n", box_planes[0].dist, box_planes[1].dist, box_planes[2].dist, box_planes[3].dist, box_planes[4].dist, box_planes[5].dist, cmins[0], cmins[1], cmins[2], cmaxs[0], cmaxs[1], cmaxs[2], mins[0], mins[1], mins[2], maxs[0], maxs[1], maxs[2]);
940 #endif
941
942         if (box_hull.clipnodes == NULL)
943         {
944                 int i, side;
945
946                 //Set up the planes and clipnodes so that the six floats of a bounding box
947                 //can just be stored out and get a proper hull_t structure.
948
949                 box_hull.clipnodes = box_clipnodes;
950                 box_hull.planes = box_planes;
951                 box_hull.firstclipnode = 0;
952                 box_hull.lastclipnode = 5;
953
954                 for (i = 0;i < 6;i++)
955                 {
956                         box_clipnodes[i].planenum = i;
957
958                         side = i&1;
959
960                         box_clipnodes[i].children[side] = CONTENTS_EMPTY;
961                         if (i != 5)
962                                 box_clipnodes[i].children[side^1] = i + 1;
963                         else
964                                 box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
965
966                         box_planes[i].type = i>>1;
967                         box_planes[i].normal[i>>1] = 1;
968                 }
969         }
970
971         // trace a line through the generated clipping hull
972         //rhc.boxsupercontents = boxsupercontents;
973         rhc.hull = &box_hull;
974         rhc.trace = trace;
975         rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
976         rhc.trace->fraction = 1;
977         rhc.trace->realfraction = 1;
978         rhc.trace->allsolid = true;
979         VectorCopy(start, rhc.start);
980         VectorCopy(end, rhc.end);
981         VectorSubtract(rhc.end, rhc.start, rhc.dist);
982         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
983         //VectorMA(rhc.start, rhc.trace->fraction, rhc.dist, rhc.trace->endpos);
984         if (rhc.trace->startsupercontents)
985                 rhc.trace->startsupercontents = boxsupercontents;
986 #endif
987 }
988
989 static int Mod_Q1BSP_LightPoint_RecursiveBSPNode(model_t *model, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal, const mnode_t *node, float x, float y, float startz, float endz)
990 {
991         int side;
992         float front, back;
993         float mid, distz = endz - startz;
994
995 loc0:
996         if (!node->plane)
997                 return false;           // didn't hit anything
998
999         switch (node->plane->type)
1000         {
1001         case PLANE_X:
1002                 node = node->children[x < node->plane->dist];
1003                 goto loc0;
1004         case PLANE_Y:
1005                 node = node->children[y < node->plane->dist];
1006                 goto loc0;
1007         case PLANE_Z:
1008                 side = startz < node->plane->dist;
1009                 if ((endz < node->plane->dist) == side)
1010                 {
1011                         node = node->children[side];
1012                         goto loc0;
1013                 }
1014                 // found an intersection
1015                 mid = node->plane->dist;
1016                 break;
1017         default:
1018                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
1019                 front += startz * node->plane->normal[2];
1020                 back += endz * node->plane->normal[2];
1021                 side = front < node->plane->dist;
1022                 if ((back < node->plane->dist) == side)
1023                 {
1024                         node = node->children[side];
1025                         goto loc0;
1026                 }
1027                 // found an intersection
1028                 mid = startz + distz * (front - node->plane->dist) / (front - back);
1029                 break;
1030         }
1031
1032         // go down front side
1033         if (node->children[side]->plane && Mod_Q1BSP_LightPoint_RecursiveBSPNode(model, ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
1034                 return true;    // hit something
1035         else
1036         {
1037                 // check for impact on this node
1038                 if (node->numsurfaces)
1039                 {
1040                         int i, ds, dt;
1041                         msurface_t *surface;
1042
1043                         surface = model->data_surfaces + node->firstsurface;
1044                         for (i = 0;i < node->numsurfaces;i++, surface++)
1045                         {
1046                                 if (!(surface->texture->basematerialflags & MATERIALFLAG_WALL) || !surface->lightmapinfo->samples)
1047                                         continue;       // no lightmaps
1048
1049                                 ds = (int) (x * surface->lightmapinfo->texinfo->vecs[0][0] + y * surface->lightmapinfo->texinfo->vecs[0][1] + mid * surface->lightmapinfo->texinfo->vecs[0][2] + surface->lightmapinfo->texinfo->vecs[0][3]) - surface->lightmapinfo->texturemins[0];
1050                                 dt = (int) (x * surface->lightmapinfo->texinfo->vecs[1][0] + y * surface->lightmapinfo->texinfo->vecs[1][1] + mid * surface->lightmapinfo->texinfo->vecs[1][2] + surface->lightmapinfo->texinfo->vecs[1][3]) - surface->lightmapinfo->texturemins[1];
1051
1052                                 if (ds >= 0 && ds < surface->lightmapinfo->extents[0] && dt >= 0 && dt < surface->lightmapinfo->extents[1])
1053                                 {
1054                                         unsigned char *lightmap;
1055                                         int lmwidth, lmheight, maps, line3, size3, dsfrac = ds & 15, dtfrac = dt & 15, scale = 0, r00 = 0, g00 = 0, b00 = 0, r01 = 0, g01 = 0, b01 = 0, r10 = 0, g10 = 0, b10 = 0, r11 = 0, g11 = 0, b11 = 0;
1056                                         lmwidth = ((surface->lightmapinfo->extents[0]>>4)+1);
1057                                         lmheight = ((surface->lightmapinfo->extents[1]>>4)+1);
1058                                         line3 = lmwidth * 3; // LordHavoc: *3 for colored lighting
1059                                         size3 = lmwidth * lmheight * 3; // LordHavoc: *3 for colored lighting
1060
1061                                         lightmap = surface->lightmapinfo->samples + ((dt>>4) * lmwidth + (ds>>4))*3; // LordHavoc: *3 for colored lighting
1062
1063                                         for (maps = 0;maps < MAXLIGHTMAPS && surface->lightmapinfo->styles[maps] != 255;maps++)
1064                                         {
1065                                                 scale = r_refdef.lightstylevalue[surface->lightmapinfo->styles[maps]];
1066                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
1067                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
1068                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
1069                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
1070                                                 lightmap += size3;
1071                                         }
1072
1073 /*
1074 LordHavoc: here's the readable version of the interpolation
1075 code, not quite as easy for the compiler to optimize...
1076
1077 dsfrac is the X position in the lightmap pixel, * 16
1078 dtfrac is the Y position in the lightmap pixel, * 16
1079 r00 is top left corner, r01 is top right corner
1080 r10 is bottom left corner, r11 is bottom right corner
1081 g and b are the same layout.
1082 r0 and r1 are the top and bottom intermediate results
1083
1084 first we interpolate the top two points, to get the top
1085 edge sample
1086
1087         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
1088         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
1089         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
1090
1091 then we interpolate the bottom two points, to get the
1092 bottom edge sample
1093
1094         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
1095         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
1096         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
1097
1098 then we interpolate the top and bottom samples to get the
1099 middle sample (the one which was requested)
1100
1101         r = (((r1-r0) * dtfrac) >> 4) + r0;
1102         g = (((g1-g0) * dtfrac) >> 4) + g0;
1103         b = (((b1-b0) * dtfrac) >> 4) + b0;
1104 */
1105
1106                                         ambientcolor[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
1107                                         ambientcolor[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
1108                                         ambientcolor[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
1109                                         return true; // success
1110                                 }
1111                         }
1112                 }
1113
1114                 // go down back side
1115                 node = node->children[side ^ 1];
1116                 startz = mid;
1117                 distz = endz - startz;
1118                 goto loc0;
1119         }
1120 }
1121
1122 void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
1123 {
1124         Mod_Q1BSP_LightPoint_RecursiveBSPNode(model, ambientcolor, diffusecolor, diffusenormal, model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode, p[0], p[1], p[2] + 0.125, p[2] - 65536);
1125         // pretend lighting is coming down from above (due to lack of a lightgrid to know primary lighting direction)
1126         VectorSet(diffusenormal, 0, 0, 1);
1127 }
1128
1129 static void Mod_Q1BSP_DecompressVis(const unsigned char *in, const unsigned char *inend, unsigned char *out, unsigned char *outend)
1130 {
1131         int c;
1132         unsigned char *outstart = out;
1133         while (out < outend)
1134         {
1135                 if (in == inend)
1136                 {
1137                         Con_Printf("Mod_Q1BSP_DecompressVis: input underrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, (int)(out - outstart), (int)(outend - outstart));
1138                         return;
1139                 }
1140                 c = *in++;
1141                 if (c)
1142                         *out++ = c;
1143                 else
1144                 {
1145                         if (in == inend)
1146                         {
1147                                 Con_Printf("Mod_Q1BSP_DecompressVis: input underrun (during zero-run) on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, (int)(out - outstart), (int)(outend - outstart));
1148                                 return;
1149                         }
1150                         for (c = *in++;c > 0;c--)
1151                         {
1152                                 if (out == outend)
1153                                 {
1154                                         Con_Printf("Mod_Q1BSP_DecompressVis: output overrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, (int)(out - outstart), (int)(outend - outstart));
1155                                         return;
1156                                 }
1157                                 *out++ = 0;
1158                         }
1159                 }
1160         }
1161 }
1162
1163 /*
1164 =============
1165 R_Q1BSP_LoadSplitSky
1166
1167 A sky texture is 256*128, with the right side being a masked overlay
1168 ==============
1169 */
1170 void R_Q1BSP_LoadSplitSky (unsigned char *src, int width, int height, int bytesperpixel)
1171 {
1172         int i, j;
1173         unsigned solidpixels[128*128], alphapixels[128*128];
1174
1175         // if sky isn't the right size, just use it as a solid layer
1176         if (width != 256 || height != 128)
1177         {
1178                 loadmodel->brush.solidskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_solidtexture", width, height, src, bytesperpixel == 4 ? TEXTYPE_RGBA : TEXTYPE_PALETTE, TEXF_PRECACHE, bytesperpixel == 1 ? palette_complete : NULL);
1179                 loadmodel->brush.alphaskytexture = NULL;
1180                 return;
1181         }
1182
1183         if (bytesperpixel == 4)
1184         {
1185                 for (i = 0;i < 128;i++)
1186                 {
1187                         for (j = 0;j < 128;j++)
1188                         {
1189                                 solidpixels[(i*128) + j] = ((unsigned *)src)[i*256+j+128];
1190                                 alphapixels[(i*128) + j] = ((unsigned *)src)[i*256+j];
1191                         }
1192                 }
1193         }
1194         else
1195         {
1196                 // make an average value for the back to avoid
1197                 // a fringe on the top level
1198                 int p, r, g, b;
1199                 union
1200                 {
1201                         unsigned int i;
1202                         unsigned char b[4];
1203                 }
1204                 rgba;
1205                 r = g = b = 0;
1206                 for (i = 0;i < 128;i++)
1207                 {
1208                         for (j = 0;j < 128;j++)
1209                         {
1210                                 rgba.i = palette_complete[src[i*256 + j + 128]];
1211                                 r += rgba.b[0];
1212                                 g += rgba.b[1];
1213                                 b += rgba.b[2];
1214                         }
1215                 }
1216                 rgba.b[0] = r/(128*128);
1217                 rgba.b[1] = g/(128*128);
1218                 rgba.b[2] = b/(128*128);
1219                 rgba.b[3] = 0;
1220                 for (i = 0;i < 128;i++)
1221                 {
1222                         for (j = 0;j < 128;j++)
1223                         {
1224                                 solidpixels[(i*128) + j] = palette_complete[src[i*256 + j + 128]];
1225                                 alphapixels[(i*128) + j] = (p = src[i*256 + j]) ? palette_complete[p] : rgba.i;
1226                         }
1227                 }
1228         }
1229
1230         loadmodel->brush.solidskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_solidtexture", 128, 128, (unsigned char *) solidpixels, TEXTYPE_RGBA, TEXF_PRECACHE, NULL);
1231         loadmodel->brush.alphaskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_alphatexture", 128, 128, (unsigned char *) alphapixels, TEXTYPE_RGBA, TEXF_ALPHA | TEXF_PRECACHE, NULL);
1232 }
1233
1234 static void Mod_Q1BSP_LoadTextures(lump_t *l)
1235 {
1236         int i, j, k, num, max, altmax, mtwidth, mtheight, *dofs, incomplete;
1237         miptex_t *dmiptex;
1238         texture_t *tx, *tx2, *anims[10], *altanims[10];
1239         dmiptexlump_t *m;
1240         unsigned char *data, *mtdata;
1241         const char *s;
1242         char mapname[MAX_QPATH], name[MAX_QPATH];
1243
1244         loadmodel->data_textures = NULL;
1245
1246         // add two slots for notexture walls and notexture liquids
1247         if (l->filelen)
1248         {
1249                 m = (dmiptexlump_t *)(mod_base + l->fileofs);
1250                 m->nummiptex = LittleLong (m->nummiptex);
1251                 loadmodel->num_textures = m->nummiptex + 2;
1252         }
1253         else
1254         {
1255                 m = NULL;
1256                 loadmodel->num_textures = 2;
1257         }
1258
1259         loadmodel->data_textures = (texture_t *)Mem_Alloc(loadmodel->mempool, loadmodel->num_textures * sizeof(texture_t));
1260
1261         // fill out all slots with notexture
1262         for (i = 0, tx = loadmodel->data_textures;i < loadmodel->num_textures;i++, tx++)
1263         {
1264                 strlcpy(tx->name, "NO TEXTURE FOUND", sizeof(tx->name));
1265                 tx->width = 16;
1266                 tx->height = 16;
1267                 tx->numskinframes = 1;
1268                 tx->skinframerate = 1;
1269                 tx->currentskinframe = tx->skinframes;
1270                 tx->skinframes[0].base = r_texture_notexture;
1271                 tx->backgroundcurrentskinframe = tx->backgroundskinframes;
1272                 tx->basematerialflags = 0;
1273                 if (i == loadmodel->num_textures - 1)
1274                 {
1275                         tx->basematerialflags |= MATERIALFLAG_WATER | MATERIALFLAG_LIGHTBOTHSIDES | MATERIALFLAG_NOSHADOW;
1276                         tx->supercontents = mod_q1bsp_texture_water.supercontents;
1277                         tx->surfaceflags = mod_q1bsp_texture_water.surfaceflags;
1278                 }
1279                 else
1280                 {
1281                         tx->basematerialflags |= MATERIALFLAG_WALL;
1282                         tx->supercontents = mod_q1bsp_texture_solid.supercontents;
1283                         tx->surfaceflags = mod_q1bsp_texture_solid.surfaceflags;
1284                 }
1285                 tx->currentframe = tx;
1286         }
1287
1288         if (!m)
1289                 return;
1290
1291         s = loadmodel->name;
1292         if (!strncasecmp(s, "maps/", 5))
1293                 s += 5;
1294         FS_StripExtension(s, mapname, sizeof(mapname));
1295
1296         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
1297         dofs = m->dataofs;
1298         // LordHavoc: mostly rewritten map texture loader
1299         for (i = 0;i < m->nummiptex;i++)
1300         {
1301                 dofs[i] = LittleLong(dofs[i]);
1302                 if (dofs[i] == -1 || r_nosurftextures.integer)
1303                         continue;
1304                 dmiptex = (miptex_t *)((unsigned char *)m + dofs[i]);
1305
1306                 // make sure name is no more than 15 characters
1307                 for (j = 0;dmiptex->name[j] && j < 15;j++)
1308                         name[j] = dmiptex->name[j];
1309                 name[j] = 0;
1310
1311                 mtwidth = LittleLong(dmiptex->width);
1312                 mtheight = LittleLong(dmiptex->height);
1313                 mtdata = NULL;
1314                 j = LittleLong(dmiptex->offsets[0]);
1315                 if (j)
1316                 {
1317                         // texture included
1318                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
1319                         {
1320                                 Con_Printf("Texture \"%s\" in \"%s\"is corrupt or incomplete\n", dmiptex->name, loadmodel->name);
1321                                 continue;
1322                         }
1323                         mtdata = (unsigned char *)dmiptex + j;
1324                 }
1325
1326                 if ((mtwidth & 15) || (mtheight & 15))
1327                         Con_Printf("warning: texture \"%s\" in \"%s\" is not 16 aligned\n", dmiptex->name, loadmodel->name);
1328
1329                 // LordHavoc: force all names to lowercase
1330                 for (j = 0;name[j];j++)
1331                         if (name[j] >= 'A' && name[j] <= 'Z')
1332                                 name[j] += 'a' - 'A';
1333
1334                 tx = loadmodel->data_textures + i;
1335                 strlcpy(tx->name, name, sizeof(tx->name));
1336                 tx->width = mtwidth;
1337                 tx->height = mtheight;
1338
1339                 if (!tx->name[0])
1340                 {
1341                         sprintf(tx->name, "unnamed%i", i);
1342                         Con_Printf("warning: unnamed texture in %s, renaming to %s\n", loadmodel->name, tx->name);
1343                 }
1344
1345                 if (cls.state != ca_dedicated)
1346                 {
1347                         // LordHavoc: HL sky textures are entirely different than quake
1348                         if (!loadmodel->brush.ishlbsp && !strncmp(tx->name, "sky", 3) && mtwidth == 256 && mtheight == 128)
1349                         {
1350                                 if (loadmodel->isworldmodel)
1351                                 {
1352                                         data = loadimagepixels(tx->name, false, 0, 0);
1353                                         if (data)
1354                                         {
1355                                                 R_Q1BSP_LoadSplitSky(data, image_width, image_height, 4);
1356                                                 Mem_Free(data);
1357                                         }
1358                                         else if (mtdata != NULL)
1359                                                 R_Q1BSP_LoadSplitSky(mtdata, mtwidth, mtheight, 1);
1360                                 }
1361                         }
1362                         else
1363                         {
1364                                 if (!Mod_LoadSkinFrame(&tx->skinframes[0], gamemode == GAME_TENEBRAE ? tx->name : va("textures/%s/%s", mapname, tx->name), TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, false, true)
1365                                  && !Mod_LoadSkinFrame(&tx->skinframes[0], gamemode == GAME_TENEBRAE ? tx->name : va("textures/%s", tx->name), TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, false, true))
1366                                 {
1367                                         // did not find external texture, load it from the bsp or wad3
1368                                         if (loadmodel->brush.ishlbsp)
1369                                         {
1370                                                 // internal texture overrides wad
1371                                                 unsigned char *pixels, *freepixels;
1372                                                 pixels = freepixels = NULL;
1373                                                 if (mtdata)
1374                                                         pixels = W_ConvertWAD3Texture(dmiptex);
1375                                                 if (pixels == NULL)
1376                                                         pixels = freepixels = W_GetTexture(tx->name);
1377                                                 if (pixels != NULL)
1378                                                 {
1379                                                         tx->width = image_width;
1380                                                         tx->height = image_height;
1381                                                         Mod_LoadSkinFrame_Internal(&tx->skinframes[0], tx->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, false, false, pixels, image_width, image_height, 32, NULL, NULL);
1382                                                 }
1383                                                 if (freepixels)
1384                                                         Mem_Free(freepixels);
1385                                         }
1386                                         else if (mtdata) // texture included
1387                                                 Mod_LoadSkinFrame_Internal(&tx->skinframes[0], tx->name, TEXF_MIPMAP | TEXF_PRECACHE | TEXF_PICMIP, false, r_fullbrights.integer, mtdata, tx->width, tx->height, 8, NULL, NULL);
1388                                 }
1389                         }
1390                         if (tx->skinframes[0].base == NULL)
1391                         {
1392                                 // no texture found
1393                                 tx->width = 16;
1394                                 tx->height = 16;
1395                                 tx->skinframes[0].base = r_texture_notexture;
1396                         }
1397                 }
1398
1399                 tx->basematerialflags = 0;
1400                 if (tx->name[0] == '*')
1401                 {
1402                         // LordHavoc: some turbulent textures should not be affected by wateralpha
1403                         if (strncmp(tx->name,"*lava",5)
1404                          && strncmp(tx->name,"*teleport",9)
1405                          && strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
1406                                 tx->basematerialflags |= MATERIALFLAG_WATERALPHA | MATERIALFLAG_NOSHADOW;
1407                         if (!strncmp(tx->name, "*lava", 5))
1408                         {
1409                                 tx->supercontents = mod_q1bsp_texture_lava.supercontents;
1410                                 tx->surfaceflags = mod_q1bsp_texture_lava.surfaceflags;
1411                         }
1412                         else if (!strncmp(tx->name, "*slime", 6))
1413                         {
1414                                 tx->supercontents = mod_q1bsp_texture_slime.supercontents;
1415                                 tx->surfaceflags = mod_q1bsp_texture_slime.surfaceflags;
1416                         }
1417                         else
1418                         {
1419                                 tx->supercontents = mod_q1bsp_texture_water.supercontents;
1420                                 tx->surfaceflags = mod_q1bsp_texture_water.surfaceflags;
1421                         }
1422                         tx->basematerialflags |= MATERIALFLAG_WATER | MATERIALFLAG_LIGHTBOTHSIDES | MATERIALFLAG_NOSHADOW;
1423                 }
1424                 else if (tx->name[0] == 's' && tx->name[1] == 'k' && tx->name[2] == 'y')
1425                 {
1426                         tx->supercontents = mod_q1bsp_texture_sky.supercontents;
1427                         tx->surfaceflags = mod_q1bsp_texture_sky.surfaceflags;
1428                         tx->basematerialflags |= MATERIALFLAG_SKY | MATERIALFLAG_NOSHADOW;
1429                 }
1430                 else
1431                 {
1432                         tx->supercontents = mod_q1bsp_texture_solid.supercontents;
1433                         tx->surfaceflags = mod_q1bsp_texture_solid.surfaceflags;
1434                         tx->basematerialflags |= MATERIALFLAG_WALL;
1435                 }
1436                 if (tx->skinframes[0].fog)
1437                         tx->basematerialflags |= MATERIALFLAG_ALPHA | MATERIALFLAG_BLENDED | MATERIALFLAG_TRANSPARENT | MATERIALFLAG_NOSHADOW;
1438
1439                 // start out with no animation
1440                 tx->currentframe = tx;
1441         }
1442
1443         // sequence the animations
1444         for (i = 0;i < m->nummiptex;i++)
1445         {
1446                 tx = loadmodel->data_textures + i;
1447                 if (!tx || tx->name[0] != '+' || tx->name[1] == 0 || tx->name[2] == 0)
1448                         continue;
1449                 if (tx->anim_total[0] || tx->anim_total[1])
1450                         continue;       // already sequenced
1451
1452                 // find the number of frames in the animation
1453                 memset(anims, 0, sizeof(anims));
1454                 memset(altanims, 0, sizeof(altanims));
1455
1456                 for (j = i;j < m->nummiptex;j++)
1457                 {
1458                         tx2 = loadmodel->data_textures + j;
1459                         if (!tx2 || tx2->name[0] != '+' || strcmp(tx2->name+2, tx->name+2))
1460                                 continue;
1461
1462                         num = tx2->name[1];
1463                         if (num >= '0' && num <= '9')
1464                                 anims[num - '0'] = tx2;
1465                         else if (num >= 'a' && num <= 'j')
1466                                 altanims[num - 'a'] = tx2;
1467                         else
1468                                 Con_Printf("Bad animating texture %s\n", tx->name);
1469                 }
1470
1471                 max = altmax = 0;
1472                 for (j = 0;j < 10;j++)
1473                 {
1474                         if (anims[j])
1475                                 max = j + 1;
1476                         if (altanims[j])
1477                                 altmax = j + 1;
1478                 }
1479                 //Con_Printf("linking animation %s (%i:%i frames)\n\n", tx->name, max, altmax);
1480
1481                 incomplete = false;
1482                 for (j = 0;j < max;j++)
1483                 {
1484                         if (!anims[j])
1485                         {
1486                                 Con_Printf("Missing frame %i of %s\n", j, tx->name);
1487                                 incomplete = true;
1488                         }
1489                 }
1490                 for (j = 0;j < altmax;j++)
1491                 {
1492                         if (!altanims[j])
1493                         {
1494                                 Con_Printf("Missing altframe %i of %s\n", j, tx->name);
1495                                 incomplete = true;
1496                         }
1497                 }
1498                 if (incomplete)
1499                         continue;
1500
1501                 if (altmax < 1)
1502                 {
1503                         // if there is no alternate animation, duplicate the primary
1504                         // animation into the alternate
1505                         altmax = max;
1506                         for (k = 0;k < 10;k++)
1507                                 altanims[k] = anims[k];
1508                 }
1509
1510                 // link together the primary animation
1511                 for (j = 0;j < max;j++)
1512                 {
1513                         tx2 = anims[j];
1514                         tx2->animated = true;
1515                         tx2->anim_total[0] = max;
1516                         tx2->anim_total[1] = altmax;
1517                         for (k = 0;k < 10;k++)
1518                         {
1519                                 tx2->anim_frames[0][k] = anims[k];
1520                                 tx2->anim_frames[1][k] = altanims[k];
1521                         }
1522                 }
1523
1524                 // if there really is an alternate anim...
1525                 if (anims[0] != altanims[0])
1526                 {
1527                         // link together the alternate animation
1528                         for (j = 0;j < altmax;j++)
1529                         {
1530                                 tx2 = altanims[j];
1531                                 tx2->animated = true;
1532                                 // the primary/alternate are reversed here
1533                                 tx2->anim_total[0] = altmax;
1534                                 tx2->anim_total[1] = max;
1535                                 for (k = 0;k < 10;k++)
1536                                 {
1537                                         tx2->anim_frames[0][k] = altanims[k];
1538                                         tx2->anim_frames[1][k] = anims[k];
1539                                 }
1540                         }
1541                 }
1542         }
1543 }
1544
1545 static void Mod_Q1BSP_LoadLighting(lump_t *l)
1546 {
1547         int i;
1548         unsigned char *in, *out, *data, d;
1549         char litfilename[MAX_QPATH];
1550         char dlitfilename[MAX_QPATH];
1551         fs_offset_t filesize;
1552         if (loadmodel->brush.ishlbsp) // LordHavoc: load the colored lighting data straight
1553         {
1554                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1555                 for (i=0; i<l->filelen; i++)
1556                         loadmodel->brushq1.lightdata[i] = mod_base[l->fileofs+i] >>= 1;
1557         }
1558         else if (loadmodel->brush.ismcbsp)
1559         {
1560                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1561                 memcpy(loadmodel->brushq1.lightdata, mod_base + l->fileofs, l->filelen);
1562         }
1563         else // LordHavoc: bsp version 29 (normal white lighting)
1564         {
1565                 // LordHavoc: hope is not lost yet, check for a .lit file to load
1566                 strlcpy (litfilename, loadmodel->name, sizeof (litfilename));
1567                 FS_StripExtension (litfilename, litfilename, sizeof (litfilename));
1568                 strlcpy (dlitfilename, litfilename, sizeof (dlitfilename));
1569                 strlcat (litfilename, ".lit", sizeof (litfilename));
1570                 strlcat (dlitfilename, ".dlit", sizeof (dlitfilename));
1571                 data = (unsigned char*) FS_LoadFile(litfilename, tempmempool, false, &filesize);
1572                 if (data)
1573                 {
1574                         if (filesize == (fs_offset_t)(8 + l->filelen * 3) && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1575                         {
1576                                 i = LittleLong(((int *)data)[1]);
1577                                 if (i == 1)
1578                                 {
1579                                         Con_DPrintf("loaded %s\n", litfilename);
1580                                         loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, filesize - 8);
1581                                         memcpy(loadmodel->brushq1.lightdata, data + 8, filesize - 8);
1582                                         Mem_Free(data);
1583                                         data = (unsigned char*) FS_LoadFile(dlitfilename, tempmempool, false, &filesize);
1584                                         if (data)
1585                                         {
1586                                                 if (filesize == (fs_offset_t)(8 + l->filelen * 3) && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1587                                                 {
1588                                                         i = LittleLong(((int *)data)[1]);
1589                                                         if (i == 1)
1590                                                         {
1591                                                                 Con_DPrintf("loaded %s\n", dlitfilename);
1592                                                                 loadmodel->brushq1.nmaplightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, filesize - 8);
1593                                                                 memcpy(loadmodel->brushq1.nmaplightdata, data + 8, filesize - 8);
1594                                                                 loadmodel->brushq3.deluxemapping_modelspace = false;
1595                                                                 loadmodel->brushq3.deluxemapping = true;
1596                                                         }
1597                                                 }
1598                                                 Mem_Free(data);
1599                                                 data = NULL;
1600                                         }
1601                                         return;
1602                                 }
1603                                 else
1604                                         Con_Printf("Unknown .lit file version (%d)\n", i);
1605                         }
1606                         else if (filesize == 8)
1607                                 Con_Print("Empty .lit file, ignoring\n");
1608                         else
1609                                 Con_Printf("Corrupt .lit file (file size %i bytes, should be %i bytes), ignoring\n", (int) filesize, (int) (8 + l->filelen * 3));
1610                         if (data)
1611                         {
1612                                 Mem_Free(data);
1613                                 data = NULL;
1614                         }
1615                 }
1616                 // LordHavoc: oh well, expand the white lighting data
1617                 if (!l->filelen)
1618                         return;
1619                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen*3);
1620                 in = mod_base + l->fileofs;
1621                 out = loadmodel->brushq1.lightdata;
1622                 for (i = 0;i < l->filelen;i++)
1623                 {
1624                         d = *in++;
1625                         *out++ = d;
1626                         *out++ = d;
1627                         *out++ = d;
1628                 }
1629         }
1630 }
1631
1632 static void Mod_Q1BSP_LoadVisibility(lump_t *l)
1633 {
1634         loadmodel->brushq1.num_compressedpvs = 0;
1635         loadmodel->brushq1.data_compressedpvs = NULL;
1636         if (!l->filelen)
1637                 return;
1638         loadmodel->brushq1.num_compressedpvs = l->filelen;
1639         loadmodel->brushq1.data_compressedpvs = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1640         memcpy(loadmodel->brushq1.data_compressedpvs, mod_base + l->fileofs, l->filelen);
1641 }
1642
1643 // used only for HalfLife maps
1644 static void Mod_Q1BSP_ParseWadsFromEntityLump(const char *data)
1645 {
1646         char key[128], value[4096];
1647         char wadname[128];
1648         int i, j, k;
1649         if (!data)
1650                 return;
1651         if (!COM_ParseTokenConsole(&data))
1652                 return; // error
1653         if (com_token[0] != '{')
1654                 return; // error
1655         while (1)
1656         {
1657                 if (!COM_ParseTokenConsole(&data))
1658                         return; // error
1659                 if (com_token[0] == '}')
1660                         break; // end of worldspawn
1661                 if (com_token[0] == '_')
1662                         strlcpy(key, com_token + 1, sizeof(key));
1663                 else
1664                         strlcpy(key, com_token, sizeof(key));
1665                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
1666                         key[strlen(key)-1] = 0;
1667                 if (!COM_ParseTokenConsole(&data))
1668                         return; // error
1669                 dpsnprintf(value, sizeof(value), "%s", com_token);
1670                 if (!strcmp("wad", key)) // for HalfLife maps
1671                 {
1672                         if (loadmodel->brush.ishlbsp)
1673                         {
1674                                 j = 0;
1675                                 for (i = 0;i < (int)sizeof(value);i++)
1676                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
1677                                                 break;
1678                                 if (value[i])
1679                                 {
1680                                         for (;i < (int)sizeof(value);i++)
1681                                         {
1682                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
1683                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
1684                                                         j = i+1;
1685                                                 else if (value[i] == ';' || value[i] == 0)
1686                                                 {
1687                                                         k = value[i];
1688                                                         value[i] = 0;
1689                                                         strlcpy(wadname, "textures/", sizeof(wadname));
1690                                                         strlcat(wadname, &value[j], sizeof(wadname));
1691                                                         W_LoadTextureWadFile(wadname, false);
1692                                                         j = i+1;
1693                                                         if (!k)
1694                                                                 break;
1695                                                 }
1696                                         }
1697                                 }
1698                         }
1699                 }
1700         }
1701 }
1702
1703 static void Mod_Q1BSP_LoadEntities(lump_t *l)
1704 {
1705         loadmodel->brush.entities = NULL;
1706         if (!l->filelen)
1707                 return;
1708         loadmodel->brush.entities = (char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1709         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
1710         if (loadmodel->brush.ishlbsp)
1711                 Mod_Q1BSP_ParseWadsFromEntityLump(loadmodel->brush.entities);
1712 }
1713
1714
1715 static void Mod_Q1BSP_LoadVertexes(lump_t *l)
1716 {
1717         dvertex_t       *in;
1718         mvertex_t       *out;
1719         int                     i, count;
1720
1721         in = (dvertex_t *)(mod_base + l->fileofs);
1722         if (l->filelen % sizeof(*in))
1723                 Host_Error("Mod_Q1BSP_LoadVertexes: funny lump size in %s",loadmodel->name);
1724         count = l->filelen / sizeof(*in);
1725         out = (mvertex_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1726
1727         loadmodel->brushq1.vertexes = out;
1728         loadmodel->brushq1.numvertexes = count;
1729
1730         for ( i=0 ; i<count ; i++, in++, out++)
1731         {
1732                 out->position[0] = LittleFloat(in->point[0]);
1733                 out->position[1] = LittleFloat(in->point[1]);
1734                 out->position[2] = LittleFloat(in->point[2]);
1735         }
1736 }
1737
1738 // The following two functions should be removed and MSG_* or SZ_* function sets adjusted so they
1739 // can be used for this
1740 // REMOVEME
1741 int SB_ReadInt (unsigned char **buffer)
1742 {
1743         int     i;
1744         i = ((*buffer)[0]) + 256*((*buffer)[1]) + 65536*((*buffer)[2]) + 16777216*((*buffer)[3]);
1745         (*buffer) += 4;
1746         return i;
1747 }
1748
1749 // REMOVEME
1750 float SB_ReadFloat (unsigned char **buffer)
1751 {
1752         union
1753         {
1754                 int             i;
1755                 float   f;
1756         } u;
1757
1758         u.i = SB_ReadInt (buffer);
1759         return u.f;
1760 }
1761
1762 static void Mod_Q1BSP_LoadSubmodels(lump_t *l, hullinfo_t *hullinfo)
1763 {
1764         unsigned char           *index;
1765         dmodel_t        *out;
1766         int                     i, j, count;
1767
1768         index = (unsigned char *)(mod_base + l->fileofs);
1769         if (l->filelen % (48+4*hullinfo->filehulls))
1770                 Host_Error ("Mod_Q1BSP_LoadSubmodels: funny lump size in %s", loadmodel->name);
1771
1772         count = l->filelen / (48+4*hullinfo->filehulls);
1773         out = (dmodel_t *)Mem_Alloc (loadmodel->mempool, count*sizeof(*out));
1774
1775         loadmodel->brushq1.submodels = out;
1776         loadmodel->brush.numsubmodels = count;
1777
1778         for (i = 0; i < count; i++, out++)
1779         {
1780         // spread out the mins / maxs by a pixel
1781                 out->mins[0] = SB_ReadFloat (&index) - 1;
1782                 out->mins[1] = SB_ReadFloat (&index) - 1;
1783                 out->mins[2] = SB_ReadFloat (&index) - 1;
1784                 out->maxs[0] = SB_ReadFloat (&index) + 1;
1785                 out->maxs[1] = SB_ReadFloat (&index) + 1;
1786                 out->maxs[2] = SB_ReadFloat (&index) + 1;
1787                 out->origin[0] = SB_ReadFloat (&index);
1788                 out->origin[1] = SB_ReadFloat (&index);
1789                 out->origin[2] = SB_ReadFloat (&index);
1790                 for (j = 0; j < hullinfo->filehulls; j++)
1791                         out->headnode[j] = SB_ReadInt (&index);
1792                 out->visleafs = SB_ReadInt (&index);
1793                 out->firstface = SB_ReadInt (&index);
1794                 out->numfaces = SB_ReadInt (&index);
1795         }
1796 }
1797
1798 static void Mod_Q1BSP_LoadEdges(lump_t *l)
1799 {
1800         dedge_t *in;
1801         medge_t *out;
1802         int     i, count;
1803
1804         in = (dedge_t *)(mod_base + l->fileofs);
1805         if (l->filelen % sizeof(*in))
1806                 Host_Error("Mod_Q1BSP_LoadEdges: funny lump size in %s",loadmodel->name);
1807         count = l->filelen / sizeof(*in);
1808         out = (medge_t *)Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1809
1810         loadmodel->brushq1.edges = out;
1811         loadmodel->brushq1.numedges = count;
1812
1813         for ( i=0 ; i<count ; i++, in++, out++)
1814         {
1815                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
1816                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
1817                 if (out->v[0] >= loadmodel->brushq1.numvertexes || out->v[1] >= loadmodel->brushq1.numvertexes)
1818                 {
1819                         Con_Printf("Mod_Q1BSP_LoadEdges: %s has invalid vertex indices in edge %i (vertices %i %i >= numvertices %i)\n", loadmodel->name, i, out->v[0], out->v[1], loadmodel->brushq1.numvertexes);
1820                         out->v[0] = 0;
1821                         out->v[1] = 0;
1822                 }
1823         }
1824 }
1825
1826 static void Mod_Q1BSP_LoadTexinfo(lump_t *l)
1827 {
1828         texinfo_t *in;
1829         mtexinfo_t *out;
1830         int i, j, k, count, miptex;
1831
1832         in = (texinfo_t *)(mod_base + l->fileofs);
1833         if (l->filelen % sizeof(*in))
1834                 Host_Error("Mod_Q1BSP_LoadTexinfo: funny lump size in %s",loadmodel->name);
1835         count = l->filelen / sizeof(*in);
1836         out = (mtexinfo_t *)Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1837
1838         loadmodel->brushq1.texinfo = out;
1839         loadmodel->brushq1.numtexinfo = count;
1840
1841         for (i = 0;i < count;i++, in++, out++)
1842         {
1843                 for (k = 0;k < 2;k++)
1844                         for (j = 0;j < 4;j++)
1845                                 out->vecs[k][j] = LittleFloat(in->vecs[k][j]);
1846
1847                 miptex = LittleLong(in->miptex);
1848                 out->flags = LittleLong(in->flags);
1849
1850                 out->texture = NULL;
1851                 if (loadmodel->data_textures)
1852                 {
1853                         if ((unsigned int) miptex >= (unsigned int) loadmodel->num_textures)
1854                                 Con_Printf("error in model \"%s\": invalid miptex index %i(of %i)\n", loadmodel->name, miptex, loadmodel->num_textures);
1855                         else
1856                                 out->texture = loadmodel->data_textures + miptex;
1857                 }
1858                 if (out->flags & TEX_SPECIAL)
1859                 {
1860                         // if texture chosen is NULL or the shader needs a lightmap,
1861                         // force to notexture water shader
1862                         if (out->texture == NULL || out->texture->basematerialflags & MATERIALFLAG_WALL)
1863                                 out->texture = loadmodel->data_textures + (loadmodel->num_textures - 1);
1864                 }
1865                 else
1866                 {
1867                         // if texture chosen is NULL, force to notexture
1868                         if (out->texture == NULL)
1869                                 out->texture = loadmodel->data_textures + (loadmodel->num_textures - 2);
1870                 }
1871         }
1872 }
1873
1874 #if 0
1875 void BoundPoly(int numverts, float *verts, vec3_t mins, vec3_t maxs)
1876 {
1877         int             i, j;
1878         float   *v;
1879
1880         mins[0] = mins[1] = mins[2] = 9999;
1881         maxs[0] = maxs[1] = maxs[2] = -9999;
1882         v = verts;
1883         for (i = 0;i < numverts;i++)
1884         {
1885                 for (j = 0;j < 3;j++, v++)
1886                 {
1887                         if (*v < mins[j])
1888                                 mins[j] = *v;
1889                         if (*v > maxs[j])
1890                                 maxs[j] = *v;
1891                 }
1892         }
1893 }
1894
1895 #define MAX_SUBDIVPOLYTRIANGLES 4096
1896 #define MAX_SUBDIVPOLYVERTS(MAX_SUBDIVPOLYTRIANGLES * 3)
1897
1898 static int subdivpolyverts, subdivpolytriangles;
1899 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
1900 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
1901
1902 static int subdivpolylookupvert(vec3_t v)
1903 {
1904         int i;
1905         for (i = 0;i < subdivpolyverts;i++)
1906                 if (subdivpolyvert[i][0] == v[0]
1907                  && subdivpolyvert[i][1] == v[1]
1908                  && subdivpolyvert[i][2] == v[2])
1909                         return i;
1910         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
1911                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
1912         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
1913         return subdivpolyverts++;
1914 }
1915
1916 static void SubdividePolygon(int numverts, float *verts)
1917 {
1918         int             i, i1, i2, i3, f, b, c, p;
1919         vec3_t  mins, maxs, front[256], back[256];
1920         float   m, *pv, *cv, dist[256], frac;
1921
1922         if (numverts > 250)
1923                 Host_Error("SubdividePolygon: ran out of verts in buffer");
1924
1925         BoundPoly(numverts, verts, mins, maxs);
1926
1927         for (i = 0;i < 3;i++)
1928         {
1929                 m = (mins[i] + maxs[i]) * 0.5;
1930                 m = r_subdivide_size.value * floor(m/r_subdivide_size.value + 0.5);
1931                 if (maxs[i] - m < 8)
1932                         continue;
1933                 if (m - mins[i] < 8)
1934                         continue;
1935
1936                 // cut it
1937                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
1938                         dist[c] = cv[i] - m;
1939
1940                 f = b = 0;
1941                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
1942                 {
1943                         if (dist[p] >= 0)
1944                         {
1945                                 VectorCopy(pv, front[f]);
1946                                 f++;
1947                         }
1948                         if (dist[p] <= 0)
1949                         {
1950                                 VectorCopy(pv, back[b]);
1951                                 b++;
1952                         }
1953                         if (dist[p] == 0 || dist[c] == 0)
1954                                 continue;
1955                         if ((dist[p] > 0) != (dist[c] > 0) )
1956                         {
1957                                 // clip point
1958                                 frac = dist[p] / (dist[p] - dist[c]);
1959                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
1960                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
1961                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
1962                                 f++;
1963                                 b++;
1964                         }
1965                 }
1966
1967                 SubdividePolygon(f, front[0]);
1968                 SubdividePolygon(b, back[0]);
1969                 return;
1970         }
1971
1972         i1 = subdivpolylookupvert(verts);
1973         i2 = subdivpolylookupvert(verts + 3);
1974         for (i = 2;i < numverts;i++)
1975         {
1976                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
1977                 {
1978                         Con_Print("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
1979                         return;
1980                 }
1981
1982                 i3 = subdivpolylookupvert(verts + i * 3);
1983                 subdivpolyindex[subdivpolytriangles][0] = i1;
1984                 subdivpolyindex[subdivpolytriangles][1] = i2;
1985                 subdivpolyindex[subdivpolytriangles][2] = i3;
1986                 i2 = i3;
1987                 subdivpolytriangles++;
1988         }
1989 }
1990
1991 //Breaks a polygon up along axial 64 unit
1992 //boundaries so that turbulent and sky warps
1993 //can be done reasonably.
1994 static void Mod_Q1BSP_GenerateWarpMesh(msurface_t *surface)
1995 {
1996         int i, j;
1997         surfvertex_t *v;
1998         surfmesh_t *mesh;
1999
2000         subdivpolytriangles = 0;
2001         subdivpolyverts = 0;
2002         SubdividePolygon(surface->num_vertices, (surface->mesh->data_vertex3f + 3 * surface->num_firstvertex));
2003         if (subdivpolytriangles < 1)
2004                 Host_Error("Mod_Q1BSP_GenerateWarpMesh: no triangles?");
2005
2006         surface->mesh = mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + subdivpolytriangles * sizeof(int[3]) + subdivpolyverts * sizeof(surfvertex_t));
2007         mesh->num_vertices = subdivpolyverts;
2008         mesh->num_triangles = subdivpolytriangles;
2009         mesh->vertex = (surfvertex_t *)(mesh + 1);
2010         mesh->index = (int *)(mesh->vertex + mesh->num_vertices);
2011         memset(mesh->vertex, 0, mesh->num_vertices * sizeof(surfvertex_t));
2012
2013         for (i = 0;i < mesh->num_triangles;i++)
2014                 for (j = 0;j < 3;j++)
2015                         mesh->index[i*3+j] = subdivpolyindex[i][j];
2016
2017         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
2018         {
2019                 VectorCopy(subdivpolyvert[i], v->v);
2020                 v->st[0] = DotProduct(v->v, surface->lightmapinfo->texinfo->vecs[0]);
2021                 v->st[1] = DotProduct(v->v, surface->lightmapinfo->texinfo->vecs[1]);
2022         }
2023 }
2024 #endif
2025
2026 static qboolean Mod_Q1BSP_AllocLightmapBlock(int *lineused, int totalwidth, int totalheight, int blockwidth, int blockheight, int *outx, int *outy)
2027 {
2028         int y, x2, y2;
2029         int bestx = totalwidth, besty = 0;
2030         // find the left-most space we can find
2031         for (y = 0;y <= totalheight - blockheight;y++)
2032         {
2033                 x2 = 0;
2034                 for (y2 = 0;y2 < blockheight;y2++)
2035                         x2 = max(x2, lineused[y+y2]);
2036                 if (bestx > x2)
2037                 {
2038                         bestx = x2;
2039                         besty = y;
2040                 }
2041         }
2042         // if the best was not good enough, return failure
2043         if (bestx > totalwidth - blockwidth)
2044                 return false;
2045         // we found a good spot
2046         if (outx)
2047                 *outx = bestx;
2048         if (outy)
2049                 *outy = besty;
2050         // now mark the space used
2051         for (y2 = 0;y2 < blockheight;y2++)
2052                 lineused[besty+y2] = bestx + blockwidth;
2053         // return success
2054         return true;
2055 }
2056
2057 static void Mod_Q1BSP_LoadFaces(lump_t *l)
2058 {
2059         dface_t *in;
2060         msurface_t *surface;
2061         int i, j, count, surfacenum, planenum, smax, tmax, ssize, tsize, firstedge, numedges, totalverts, totaltris, lightmapnumber;
2062         float texmins[2], texmaxs[2], val, lightmaptexcoordscale;
2063 #define LIGHTMAPSIZE 256
2064         rtexture_t *lightmaptexture, *deluxemaptexture;
2065         int lightmap_lineused[LIGHTMAPSIZE];
2066
2067         in = (dface_t *)(mod_base + l->fileofs);
2068         if (l->filelen % sizeof(*in))
2069                 Host_Error("Mod_Q1BSP_LoadFaces: funny lump size in %s",loadmodel->name);
2070         count = l->filelen / sizeof(*in);
2071         loadmodel->data_surfaces = (msurface_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_t));
2072         loadmodel->data_surfaces_lightmapinfo = (msurface_lightmapinfo_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_lightmapinfo_t));
2073
2074         loadmodel->num_surfaces = count;
2075
2076         totalverts = 0;
2077         totaltris = 0;
2078         for (surfacenum = 0, in = (dface_t *)(mod_base + l->fileofs);surfacenum < count;surfacenum++, in++)
2079         {
2080                 numedges = LittleShort(in->numedges);
2081                 totalverts += numedges;
2082                 totaltris += numedges - 2;
2083         }
2084
2085         Mod_AllocSurfMesh(loadmodel->mempool, totalverts, totaltris, true, false, false);
2086
2087         lightmaptexture = NULL;
2088         deluxemaptexture = r_texture_blanknormalmap;
2089         lightmapnumber = 1;
2090         lightmaptexcoordscale = 1.0f / (float)LIGHTMAPSIZE;
2091
2092         totalverts = 0;
2093         totaltris = 0;
2094         for (surfacenum = 0, in = (dface_t *)(mod_base + l->fileofs), surface = loadmodel->data_surfaces;surfacenum < count;surfacenum++, in++, surface++)
2095         {
2096                 surface->lightmapinfo = loadmodel->data_surfaces_lightmapinfo + surfacenum;
2097
2098                 // FIXME: validate edges, texinfo, etc?
2099                 firstedge = LittleLong(in->firstedge);
2100                 numedges = LittleShort(in->numedges);
2101                 if ((unsigned int) firstedge > (unsigned int) loadmodel->brushq1.numsurfedges || (unsigned int) numedges > (unsigned int) loadmodel->brushq1.numsurfedges || (unsigned int) firstedge + (unsigned int) numedges > (unsigned int) loadmodel->brushq1.numsurfedges)
2102                         Host_Error("Mod_Q1BSP_LoadFaces: invalid edge range (firstedge %i, numedges %i, model edges %i)", firstedge, numedges, loadmodel->brushq1.numsurfedges);
2103                 i = LittleShort(in->texinfo);
2104                 if ((unsigned int) i >= (unsigned int) loadmodel->brushq1.numtexinfo)
2105                         Host_Error("Mod_Q1BSP_LoadFaces: invalid texinfo index %i(model has %i texinfos)", i, loadmodel->brushq1.numtexinfo);
2106                 surface->lightmapinfo->texinfo = loadmodel->brushq1.texinfo + i;
2107                 surface->texture = surface->lightmapinfo->texinfo->texture;
2108
2109                 planenum = LittleShort(in->planenum);
2110                 if ((unsigned int) planenum >= (unsigned int) loadmodel->brush.num_planes)
2111                         Host_Error("Mod_Q1BSP_LoadFaces: invalid plane index %i (model has %i planes)", planenum, loadmodel->brush.num_planes);
2112
2113                 //surface->flags = surface->texture->flags;
2114                 //if (LittleShort(in->side))
2115                 //      surface->flags |= SURF_PLANEBACK;
2116                 //surface->plane = loadmodel->brush.data_planes + planenum;
2117
2118                 surface->num_firstvertex = totalverts;
2119                 surface->num_vertices = numedges;
2120                 surface->num_firsttriangle = totaltris;
2121                 surface->num_triangles = numedges - 2;
2122                 totalverts += numedges;
2123                 totaltris += numedges - 2;
2124
2125                 // convert edges back to a normal polygon
2126                 for (i = 0;i < surface->num_vertices;i++)
2127                 {
2128                         int lindex = loadmodel->brushq1.surfedges[firstedge + i];
2129                         float s, t;
2130                         if (lindex > 0)
2131                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[lindex].v[0]].position, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3);
2132                         else
2133                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[-lindex].v[1]].position, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3);
2134                         s = DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[0]) + surface->lightmapinfo->texinfo->vecs[0][3];
2135                         t = DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[1]) + surface->lightmapinfo->texinfo->vecs[1][3];
2136                         (loadmodel->surfmesh.data_texcoordtexture2f + 2 * surface->num_firstvertex)[i * 2 + 0] = s / surface->texture->width;
2137                         (loadmodel->surfmesh.data_texcoordtexture2f + 2 * surface->num_firstvertex)[i * 2 + 1] = t / surface->texture->height;
2138                         (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 0] = 0;
2139                         (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 1] = 0;
2140                         (loadmodel->surfmesh.data_lightmapoffsets + surface->num_firstvertex)[i] = 0;
2141                 }
2142
2143                 for (i = 0;i < surface->num_triangles;i++)
2144                 {
2145                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 0] = 0 + surface->num_firstvertex;
2146                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 1] = i + 1 + surface->num_firstvertex;
2147                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 2] = i + 2 + surface->num_firstvertex;
2148                 }
2149
2150                 // compile additional data about the surface geometry
2151                 Mod_BuildNormals(surface->num_firstvertex, surface->num_vertices, surface->num_triangles, loadmodel->surfmesh.data_vertex3f, (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle), loadmodel->surfmesh.data_normal3f, true);
2152                 Mod_BuildTextureVectorsFromNormals(surface->num_firstvertex, surface->num_vertices, surface->num_triangles, loadmodel->surfmesh.data_vertex3f, loadmodel->surfmesh.data_texcoordtexture2f, loadmodel->surfmesh.data_normal3f, (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle), loadmodel->surfmesh.data_svector3f, loadmodel->surfmesh.data_tvector3f, true);
2153                 BoxFromPoints(surface->mins, surface->maxs, surface->num_vertices, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex));
2154
2155                 // generate surface extents information
2156                 texmins[0] = texmaxs[0] = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex), surface->lightmapinfo->texinfo->vecs[0]) + surface->lightmapinfo->texinfo->vecs[0][3];
2157                 texmins[1] = texmaxs[1] = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex), surface->lightmapinfo->texinfo->vecs[1]) + surface->lightmapinfo->texinfo->vecs[1][3];
2158                 for (i = 1;i < surface->num_vertices;i++)
2159                 {
2160                         for (j = 0;j < 2;j++)
2161                         {
2162                                 val = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3, surface->lightmapinfo->texinfo->vecs[j]) + surface->lightmapinfo->texinfo->vecs[j][3];
2163                                 texmins[j] = min(texmins[j], val);
2164                                 texmaxs[j] = max(texmaxs[j], val);
2165                         }
2166                 }
2167                 for (i = 0;i < 2;i++)
2168                 {
2169                         surface->lightmapinfo->texturemins[i] = (int) floor(texmins[i] / 16.0) * 16;
2170                         surface->lightmapinfo->extents[i] = (int) ceil(texmaxs[i] / 16.0) * 16 - surface->lightmapinfo->texturemins[i];
2171                 }
2172
2173                 smax = surface->lightmapinfo->extents[0] >> 4;
2174                 tmax = surface->lightmapinfo->extents[1] >> 4;
2175                 ssize = (surface->lightmapinfo->extents[0] >> 4) + 1;
2176                 tsize = (surface->lightmapinfo->extents[1] >> 4) + 1;
2177
2178                 // lighting info
2179                 for (i = 0;i < MAXLIGHTMAPS;i++)
2180                         surface->lightmapinfo->styles[i] = in->styles[i];
2181                 surface->lightmaptexture = NULL;
2182                 surface->deluxemaptexture = r_texture_blanknormalmap;
2183                 i = LittleLong(in->lightofs);
2184                 if (i == -1)
2185                 {
2186                         surface->lightmapinfo->samples = NULL;
2187                         // give non-lightmapped water a 1x white lightmap
2188                         if ((surface->texture->basematerialflags & MATERIALFLAG_WATER) && (surface->lightmapinfo->texinfo->flags & TEX_SPECIAL) && ssize <= 256 && tsize <= 256)
2189                         {
2190                                 surface->lightmapinfo->samples = (unsigned char *)Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
2191                                 surface->lightmapinfo->styles[0] = 0;
2192                                 memset(surface->lightmapinfo->samples, 128, ssize * tsize * 3);
2193                         }
2194                 }
2195                 else if (loadmodel->brush.ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
2196                         surface->lightmapinfo->samples = loadmodel->brushq1.lightdata + i;
2197                 else // LordHavoc: white lighting (bsp version 29)
2198                 {
2199                         surface->lightmapinfo->samples = loadmodel->brushq1.lightdata + (i * 3);
2200                         if (loadmodel->brushq1.nmaplightdata)
2201                                 surface->lightmapinfo->nmapsamples = loadmodel->brushq1.nmaplightdata + (i * 3);
2202                 }
2203
2204                 // check if we should apply a lightmap to this
2205                 if (!(surface->lightmapinfo->texinfo->flags & TEX_SPECIAL) || surface->lightmapinfo->samples)
2206                 {
2207                         int i, iu, iv, lightmapx, lightmapy;
2208                         float u, v, ubase, vbase, uscale, vscale;
2209
2210                         if (ssize > 256 || tsize > 256)
2211                                 Host_Error("Bad surface extents");
2212                         // force lightmap upload on first time seeing the surface
2213                         surface->cached_dlight = true;
2214                         // stainmap for permanent marks on walls
2215                         surface->lightmapinfo->stainsamples = (unsigned char *)Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
2216                         // clear to white
2217                         memset(surface->lightmapinfo->stainsamples, 255, ssize * tsize * 3);
2218
2219                         // find a place for this lightmap
2220                         if (!lightmaptexture || !Mod_Q1BSP_AllocLightmapBlock(lightmap_lineused, LIGHTMAPSIZE, LIGHTMAPSIZE, ssize, tsize, &lightmapx, &lightmapy))
2221                         {
2222                                 // could not find room, make a new lightmap
2223                                 lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, va("lightmap%i", lightmapnumber), LIGHTMAPSIZE, LIGHTMAPSIZE, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
2224                                 if (loadmodel->brushq1.nmaplightdata)
2225                                         deluxemaptexture = R_LoadTexture2D(loadmodel->texturepool, va("deluxemap%i", lightmapnumber), LIGHTMAPSIZE, LIGHTMAPSIZE, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
2226                                 lightmapnumber++;
2227                                 memset(lightmap_lineused, 0, sizeof(lightmap_lineused));
2228                                 Mod_Q1BSP_AllocLightmapBlock(lightmap_lineused, LIGHTMAPSIZE, LIGHTMAPSIZE, ssize, tsize, &lightmapx, &lightmapy);
2229                         }
2230
2231                         surface->lightmaptexture = lightmaptexture;
2232                         surface->deluxemaptexture = deluxemaptexture;
2233                         surface->lightmapinfo->lightmaporigin[0] = lightmapx;
2234                         surface->lightmapinfo->lightmaporigin[1] = lightmapy;
2235
2236                         ubase = lightmapx * lightmaptexcoordscale;
2237                         vbase = lightmapy * lightmaptexcoordscale;
2238                         uscale = lightmaptexcoordscale;
2239                         vscale = lightmaptexcoordscale;
2240
2241                         for (i = 0;i < surface->num_vertices;i++)
2242                         {
2243                                 u = ((DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[0]) + surface->lightmapinfo->texinfo->vecs[0][3]) + 8 - surface->lightmapinfo->texturemins[0]) * (1.0 / 16.0);
2244                                 v = ((DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[1]) + surface->lightmapinfo->texinfo->vecs[1][3]) + 8 - surface->lightmapinfo->texturemins[1]) * (1.0 / 16.0);
2245                                 (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 0] = u * uscale + ubase;
2246                                 (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 1] = v * vscale + vbase;
2247                                 // LordHavoc: calc lightmap data offset for vertex lighting to use
2248                                 iu = (int) u;
2249                                 iv = (int) v;
2250                                 (loadmodel->surfmesh.data_lightmapoffsets + surface->num_firstvertex)[i] = (bound(0, iv, tmax) * ssize + bound(0, iu, smax)) * 3;
2251                         }
2252                 }
2253         }
2254 }
2255
2256 static void Mod_Q1BSP_LoadNodes_RecursiveSetParent(mnode_t *node, mnode_t *parent)
2257 {
2258         //if (node->parent)
2259         //      Host_Error("Mod_Q1BSP_LoadNodes_RecursiveSetParent: runaway recursion");
2260         node->parent = parent;
2261         if (node->plane)
2262         {
2263                 // this is a node, recurse to children
2264                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
2265                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
2266                 // combine supercontents of children
2267                 node->combinedsupercontents = node->children[0]->combinedsupercontents | node->children[1]->combinedsupercontents;
2268         }
2269         else
2270         {
2271                 int j;
2272                 mleaf_t *leaf = (mleaf_t *)node;
2273                 // if this is a leaf, calculate supercontents mask from all collidable
2274                 // primitives in the leaf (brushes and collision surfaces)
2275                 // also flag if the leaf contains any collision surfaces
2276                 leaf->combinedsupercontents = 0;
2277                 // combine the supercontents values of all brushes in this leaf
2278                 for (j = 0;j < leaf->numleafbrushes;j++)
2279                         leaf->combinedsupercontents |= loadmodel->brush.data_brushes[leaf->firstleafbrush[j]].texture->supercontents;
2280                 // check if this leaf contains any collision surfaces (q3 patches)
2281                 for (j = 0;j < leaf->numleafsurfaces;j++)
2282                 {
2283                         msurface_t *surface = loadmodel->data_surfaces + leaf->firstleafsurface[j];
2284                         if (surface->num_collisiontriangles)
2285                         {
2286                                 leaf->containscollisionsurfaces = true;
2287                                 leaf->combinedsupercontents |= surface->texture->supercontents;
2288                         }
2289                 }
2290         }
2291 }
2292
2293 static void Mod_Q1BSP_LoadNodes(lump_t *l)
2294 {
2295         int                     i, j, count, p;
2296         dnode_t         *in;
2297         mnode_t         *out;
2298
2299         in = (dnode_t *)(mod_base + l->fileofs);
2300         if (l->filelen % sizeof(*in))
2301                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
2302         count = l->filelen / sizeof(*in);
2303         out = (mnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2304
2305         loadmodel->brush.data_nodes = out;
2306         loadmodel->brush.num_nodes = count;
2307
2308         for ( i=0 ; i<count ; i++, in++, out++)
2309         {
2310                 for (j=0 ; j<3 ; j++)
2311                 {
2312                         out->mins[j] = LittleShort(in->mins[j]);
2313                         out->maxs[j] = LittleShort(in->maxs[j]);
2314                 }
2315
2316                 p = LittleLong(in->planenum);
2317                 out->plane = loadmodel->brush.data_planes + p;
2318
2319                 out->firstsurface = LittleShort(in->firstface);
2320                 out->numsurfaces = LittleShort(in->numfaces);
2321
2322                 for (j=0 ; j<2 ; j++)
2323                 {
2324                         p = LittleShort(in->children[j]);
2325                         if (p >= 0)
2326                                 out->children[j] = loadmodel->brush.data_nodes + p;
2327                         else
2328                                 out->children[j] = (mnode_t *)(loadmodel->brush.data_leafs + (-1 - p));
2329                 }
2330         }
2331
2332         Mod_Q1BSP_LoadNodes_RecursiveSetParent(loadmodel->brush.data_nodes, NULL);      // sets nodes and leafs
2333 }
2334
2335 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
2336 {
2337         dleaf_t *in;
2338         mleaf_t *out;
2339         int i, j, count, p;
2340
2341         in = (dleaf_t *)(mod_base + l->fileofs);
2342         if (l->filelen % sizeof(*in))
2343                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
2344         count = l->filelen / sizeof(*in);
2345         out = (mleaf_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2346
2347         loadmodel->brush.data_leafs = out;
2348         loadmodel->brush.num_leafs = count;
2349         // get visleafs from the submodel data
2350         loadmodel->brush.num_pvsclusters = loadmodel->brushq1.submodels[0].visleafs;
2351         loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters+7)>>3;
2352         loadmodel->brush.data_pvsclusters = (unsigned char *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2353         memset(loadmodel->brush.data_pvsclusters, 0xFF, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2354
2355         for ( i=0 ; i<count ; i++, in++, out++)
2356         {
2357                 for (j=0 ; j<3 ; j++)
2358                 {
2359                         out->mins[j] = LittleShort(in->mins[j]);
2360                         out->maxs[j] = LittleShort(in->maxs[j]);
2361                 }
2362
2363                 // FIXME: this function could really benefit from some error checking
2364
2365                 out->contents = LittleLong(in->contents);
2366
2367                 out->firstleafsurface = loadmodel->brush.data_leafsurfaces + LittleShort(in->firstmarksurface);
2368                 out->numleafsurfaces = LittleShort(in->nummarksurfaces);
2369                 if (out->firstleafsurface < 0 || LittleShort(in->firstmarksurface) + out->numleafsurfaces > loadmodel->brush.num_leafsurfaces)
2370                 {
2371                         Con_Printf("Mod_Q1BSP_LoadLeafs: invalid leafsurface range %i:%i outside range %i:%i\n", (int)(out->firstleafsurface - loadmodel->brush.data_leafsurfaces), (int)(out->firstleafsurface + out->numleafsurfaces - loadmodel->brush.data_leafsurfaces), 0, loadmodel->brush.num_leafsurfaces);
2372                         out->firstleafsurface = NULL;
2373                         out->numleafsurfaces = 0;
2374                 }
2375
2376                 out->clusterindex = i - 1;
2377                 if (out->clusterindex >= loadmodel->brush.num_pvsclusters)
2378                         out->clusterindex = -1;
2379
2380                 p = LittleLong(in->visofs);
2381                 // ignore visofs errors on leaf 0 (solid)
2382                 if (p >= 0 && out->clusterindex >= 0)
2383                 {
2384                         if (p >= loadmodel->brushq1.num_compressedpvs)
2385                                 Con_Print("Mod_Q1BSP_LoadLeafs: invalid visofs\n");
2386                         else
2387                                 Mod_Q1BSP_DecompressVis(loadmodel->brushq1.data_compressedpvs + p, loadmodel->brushq1.data_compressedpvs + loadmodel->brushq1.num_compressedpvs, loadmodel->brush.data_pvsclusters + out->clusterindex * loadmodel->brush.num_pvsclusterbytes, loadmodel->brush.data_pvsclusters + (out->clusterindex + 1) * loadmodel->brush.num_pvsclusterbytes);
2388                 }
2389
2390                 for (j = 0;j < 4;j++)
2391                         out->ambient_sound_level[j] = in->ambient_level[j];
2392
2393                 // FIXME: Insert caustics here
2394         }
2395 }
2396
2397 qboolean Mod_Q1BSP_CheckWaterAlphaSupport(void)
2398 {
2399         int i, j;
2400         mleaf_t *leaf;
2401         const unsigned char *pvs;
2402         // check all liquid leafs to see if they can see into empty leafs, if any
2403         // can we can assume this map supports r_wateralpha
2404         for (i = 0, leaf = loadmodel->brush.data_leafs;i < loadmodel->brush.num_leafs;i++, leaf++)
2405         {
2406                 if ((leaf->contents == CONTENTS_WATER || leaf->contents == CONTENTS_SLIME) && (leaf->clusterindex >= 0 && loadmodel->brush.data_pvsclusters))
2407                 {
2408                         pvs = loadmodel->brush.data_pvsclusters + leaf->clusterindex * loadmodel->brush.num_pvsclusterbytes;
2409                         for (j = 0;j < loadmodel->brush.num_leafs;j++)
2410                                 if (CHECKPVSBIT(pvs, loadmodel->brush.data_leafs[j].clusterindex) && loadmodel->brush.data_leafs[j].contents == CONTENTS_EMPTY)
2411                                         return true;
2412                 }
2413         }
2414         return false;
2415 }
2416
2417 static void Mod_Q1BSP_LoadClipnodes(lump_t *l, hullinfo_t *hullinfo)
2418 {
2419         dclipnode_t *in, *out;
2420         int                     i, count;
2421         hull_t          *hull;
2422
2423         in = (dclipnode_t *)(mod_base + l->fileofs);
2424         if (l->filelen % sizeof(*in))
2425                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2426         count = l->filelen / sizeof(*in);
2427         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2428
2429         loadmodel->brushq1.clipnodes = out;
2430         loadmodel->brushq1.numclipnodes = count;
2431
2432         for (i = 1; i < hullinfo->numhulls; i++)
2433         {
2434                 hull = &loadmodel->brushq1.hulls[i];
2435                 hull->clipnodes = out;
2436                 hull->firstclipnode = 0;
2437                 hull->lastclipnode = count-1;
2438                 hull->planes = loadmodel->brush.data_planes;
2439                 hull->clip_mins[0] = hullinfo->hullsizes[i][0][0];
2440                 hull->clip_mins[1] = hullinfo->hullsizes[i][0][1];
2441                 hull->clip_mins[2] = hullinfo->hullsizes[i][0][2];
2442                 hull->clip_maxs[0] = hullinfo->hullsizes[i][1][0];
2443                 hull->clip_maxs[1] = hullinfo->hullsizes[i][1][1];
2444                 hull->clip_maxs[2] = hullinfo->hullsizes[i][1][2];
2445                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2446         }
2447
2448         for (i=0 ; i<count ; i++, out++, in++)
2449         {
2450                 out->planenum = LittleLong(in->planenum);
2451                 out->children[0] = LittleShort(in->children[0]);
2452                 out->children[1] = LittleShort(in->children[1]);
2453                 if (out->planenum < 0 || out->planenum >= loadmodel->brush.num_planes)
2454                         Host_Error("Corrupt clipping hull(out of range planenum)");
2455                 if (out->children[0] >= count || out->children[1] >= count)
2456                         Host_Error("Corrupt clipping hull(out of range child)");
2457         }
2458 }
2459
2460 //Duplicate the drawing hull structure as a clipping hull
2461 static void Mod_Q1BSP_MakeHull0(void)
2462 {
2463         mnode_t         *in;
2464         dclipnode_t *out;
2465         int                     i;
2466         hull_t          *hull;
2467
2468         hull = &loadmodel->brushq1.hulls[0];
2469
2470         in = loadmodel->brush.data_nodes;
2471         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_nodes * sizeof(dclipnode_t));
2472
2473         hull->clipnodes = out;
2474         hull->firstclipnode = 0;
2475         hull->lastclipnode = loadmodel->brush.num_nodes - 1;
2476         hull->planes = loadmodel->brush.data_planes;
2477
2478         for (i = 0;i < loadmodel->brush.num_nodes;i++, out++, in++)
2479         {
2480                 out->planenum = in->plane - loadmodel->brush.data_planes;
2481                 out->children[0] = in->children[0]->plane ? in->children[0] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[0])->contents;
2482                 out->children[1] = in->children[1]->plane ? in->children[1] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[1])->contents;
2483         }
2484 }
2485
2486 static void Mod_Q1BSP_LoadLeaffaces(lump_t *l)
2487 {
2488         int i, j;
2489         short *in;
2490
2491         in = (short *)(mod_base + l->fileofs);
2492         if (l->filelen % sizeof(*in))
2493                 Host_Error("Mod_Q1BSP_LoadLeaffaces: funny lump size in %s",loadmodel->name);
2494         loadmodel->brush.num_leafsurfaces = l->filelen / sizeof(*in);
2495         loadmodel->brush.data_leafsurfaces = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_leafsurfaces * sizeof(int));
2496
2497         for (i = 0;i < loadmodel->brush.num_leafsurfaces;i++)
2498         {
2499                 j = (unsigned) LittleShort(in[i]);
2500                 if (j >= loadmodel->num_surfaces)
2501                         Host_Error("Mod_Q1BSP_LoadLeaffaces: bad surface number");
2502                 loadmodel->brush.data_leafsurfaces[i] = j;
2503         }
2504 }
2505
2506 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2507 {
2508         int             i;
2509         int             *in;
2510
2511         in = (int *)(mod_base + l->fileofs);
2512         if (l->filelen % sizeof(*in))
2513                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2514         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2515         loadmodel->brushq1.surfedges = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2516
2517         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2518                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2519 }
2520
2521
2522 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2523 {
2524         int                     i;
2525         mplane_t        *out;
2526         dplane_t        *in;
2527
2528         in = (dplane_t *)(mod_base + l->fileofs);
2529         if (l->filelen % sizeof(*in))
2530                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2531
2532         loadmodel->brush.num_planes = l->filelen / sizeof(*in);
2533         loadmodel->brush.data_planes = out = (mplane_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_planes * sizeof(*out));
2534
2535         for (i = 0;i < loadmodel->brush.num_planes;i++, in++, out++)
2536         {
2537                 out->normal[0] = LittleFloat(in->normal[0]);
2538                 out->normal[1] = LittleFloat(in->normal[1]);
2539                 out->normal[2] = LittleFloat(in->normal[2]);
2540                 out->dist = LittleFloat(in->dist);
2541
2542                 PlaneClassify(out);
2543         }
2544 }
2545
2546 static void Mod_Q1BSP_LoadMapBrushes(void)
2547 {
2548 #if 0
2549 // unfinished
2550         int submodel, numbrushes;
2551         qboolean firstbrush;
2552         char *text, *maptext;
2553         char mapfilename[MAX_QPATH];
2554         FS_StripExtension (loadmodel->name, mapfilename, sizeof (mapfilename));
2555         strlcat (mapfilename, ".map", sizeof (mapfilename));
2556         maptext = (unsigned char*) FS_LoadFile(mapfilename, tempmempool, false, NULL);
2557         if (!maptext)
2558                 return;
2559         text = maptext;
2560         if (!COM_ParseTokenConsole(&data))
2561                 return; // error
2562         submodel = 0;
2563         for (;;)
2564         {
2565                 if (!COM_ParseTokenConsole(&data))
2566                         break;
2567                 if (com_token[0] != '{')
2568                         return; // error
2569                 // entity
2570                 firstbrush = true;
2571                 numbrushes = 0;
2572                 maxbrushes = 256;
2573                 brushes = Mem_Alloc(loadmodel->mempool, maxbrushes * sizeof(mbrush_t));
2574                 for (;;)
2575                 {
2576                         if (!COM_ParseTokenConsole(&data))
2577                                 return; // error
2578                         if (com_token[0] == '}')
2579                                 break; // end of entity
2580                         if (com_token[0] == '{')
2581                         {
2582                                 // brush
2583                                 if (firstbrush)
2584                                 {
2585                                         if (submodel)
2586                                         {
2587                                                 if (submodel > loadmodel->brush.numsubmodels)
2588                                                 {
2589                                                         Con_Printf("Mod_Q1BSP_LoadMapBrushes: .map has more submodels than .bsp!\n");
2590                                                         model = NULL;
2591                                                 }
2592                                                 else
2593                                                         model = loadmodel->brush.submodels[submodel];
2594                                         }
2595                                         else
2596                                                 model = loadmodel;
2597                                 }
2598                                 for (;;)
2599                                 {
2600                                         if (!COM_ParseTokenConsole(&data))
2601                                                 return; // error
2602                                         if (com_token[0] == '}')
2603                                                 break; // end of brush
2604                                         // each brush face should be this format:
2605                                         // ( x y z ) ( x y z ) ( x y z ) texture scroll_s scroll_t rotateangle scale_s scale_t
2606                                         // FIXME: support hl .map format
2607                                         for (pointnum = 0;pointnum < 3;pointnum++)
2608                                         {
2609                                                 COM_ParseTokenConsole(&data);
2610                                                 for (componentnum = 0;componentnum < 3;componentnum++)
2611                                                 {
2612                                                         COM_ParseTokenConsole(&data);
2613                                                         point[pointnum][componentnum] = atof(com_token);
2614                                                 }
2615                                                 COM_ParseTokenConsole(&data);
2616                                         }
2617                                         COM_ParseTokenConsole(&data);
2618                                         strlcpy(facetexture, com_token, sizeof(facetexture));
2619                                         COM_ParseTokenConsole(&data);
2620                                         //scroll_s = atof(com_token);
2621                                         COM_ParseTokenConsole(&data);
2622                                         //scroll_t = atof(com_token);
2623                                         COM_ParseTokenConsole(&data);
2624                                         //rotate = atof(com_token);
2625                                         COM_ParseTokenConsole(&data);
2626                                         //scale_s = atof(com_token);
2627                                         COM_ParseTokenConsole(&data);
2628                                         //scale_t = atof(com_token);
2629                                         TriangleNormal(point[0], point[1], point[2], planenormal);
2630                                         VectorNormalizeDouble(planenormal);
2631                                         planedist = DotProduct(point[0], planenormal);
2632                                         //ChooseTexturePlane(planenormal, texturevector[0], texturevector[1]);
2633                                 }
2634                                 continue;
2635                         }
2636                 }
2637         }
2638 #endif
2639 }
2640
2641
2642 #define MAX_PORTALPOINTS 64
2643
2644 typedef struct portal_s
2645 {
2646         mplane_t plane;
2647         mnode_t *nodes[2];              // [0] = front side of plane
2648         struct portal_s *next[2];
2649         int numpoints;
2650         double points[3*MAX_PORTALPOINTS];
2651         struct portal_s *chain; // all portals are linked into a list
2652 }
2653 portal_t;
2654
2655 static portal_t *portalchain;
2656
2657 /*
2658 ===========
2659 AllocPortal
2660 ===========
2661 */
2662 static portal_t *AllocPortal(void)
2663 {
2664         portal_t *p;
2665         p = (portal_t *)Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2666         p->chain = portalchain;
2667         portalchain = p;
2668         return p;
2669 }
2670
2671 static void FreePortal(portal_t *p)
2672 {
2673         Mem_Free(p);
2674 }
2675
2676 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2677 {
2678         // process only nodes (leafs already had their box calculated)
2679         if (!node->plane)
2680                 return;
2681
2682         // calculate children first
2683         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2684         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2685
2686         // make combined bounding box from children
2687         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2688         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2689         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2690         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2691         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2692         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2693 }
2694
2695 static void Mod_Q1BSP_FinalizePortals(void)
2696 {
2697         int i, j, numportals, numpoints;
2698         portal_t *p, *pnext;
2699         mportal_t *portal;
2700         mvertex_t *point;
2701         mleaf_t *leaf, *endleaf;
2702
2703         // tally up portal and point counts and recalculate bounding boxes for all
2704         // leafs (because qbsp is very sloppy)
2705         leaf = loadmodel->brush.data_leafs;
2706         endleaf = leaf + loadmodel->brush.num_leafs;
2707         for (;leaf < endleaf;leaf++)
2708         {
2709                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2710                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2711         }
2712         p = portalchain;
2713         numportals = 0;
2714         numpoints = 0;
2715         while (p)
2716         {
2717                 // note: this check must match the one below or it will usually corrupt memory
2718                 // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
2719                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1] && ((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2720                 {
2721                         numportals += 2;
2722                         numpoints += p->numpoints * 2;
2723                 }
2724                 p = p->chain;
2725         }
2726         loadmodel->brush.data_portals = (mportal_t *)Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2727         loadmodel->brush.num_portals = numportals;
2728         loadmodel->brush.data_portalpoints = (mvertex_t *)((unsigned char *) loadmodel->brush.data_portals + numportals * sizeof(mportal_t));
2729         loadmodel->brush.num_portalpoints = numpoints;
2730         // clear all leaf portal chains
2731         for (i = 0;i < loadmodel->brush.num_leafs;i++)
2732                 loadmodel->brush.data_leafs[i].portals = NULL;
2733         // process all portals in the global portal chain, while freeing them
2734         portal = loadmodel->brush.data_portals;
2735         point = loadmodel->brush.data_portalpoints;
2736         p = portalchain;
2737         portalchain = NULL;
2738         while (p)
2739         {
2740                 pnext = p->chain;
2741
2742                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1])
2743                 {
2744                         // note: this check must match the one above or it will usually corrupt memory
2745                         // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
2746                         if (((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2747                         {
2748                                 // first make the back to front portal(forward portal)
2749                                 portal->points = point;
2750                                 portal->numpoints = p->numpoints;
2751                                 portal->plane.dist = p->plane.dist;
2752                                 VectorCopy(p->plane.normal, portal->plane.normal);
2753                                 portal->here = (mleaf_t *)p->nodes[1];
2754                                 portal->past = (mleaf_t *)p->nodes[0];
2755                                 // copy points
2756                                 for (j = 0;j < portal->numpoints;j++)
2757                                 {
2758                                         VectorCopy(p->points + j*3, point->position);
2759                                         point++;
2760                                 }
2761                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2762                                 PlaneClassify(&portal->plane);
2763
2764                                 // link into leaf's portal chain
2765                                 portal->next = portal->here->portals;
2766                                 portal->here->portals = portal;
2767
2768                                 // advance to next portal
2769                                 portal++;
2770
2771                                 // then make the front to back portal(backward portal)
2772                                 portal->points = point;
2773                                 portal->numpoints = p->numpoints;
2774                                 portal->plane.dist = -p->plane.dist;
2775                                 VectorNegate(p->plane.normal, portal->plane.normal);
2776                                 portal->here = (mleaf_t *)p->nodes[0];
2777                                 portal->past = (mleaf_t *)p->nodes[1];
2778                                 // copy points
2779                                 for (j = portal->numpoints - 1;j >= 0;j--)
2780                                 {
2781                                         VectorCopy(p->points + j*3, point->position);
2782                                         point++;
2783                                 }
2784                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2785                                 PlaneClassify(&portal->plane);
2786
2787                                 // link into leaf's portal chain
2788                                 portal->next = portal->here->portals;
2789                                 portal->here->portals = portal;
2790
2791                                 // advance to next portal
2792                                 portal++;
2793                         }
2794                         // add the portal's polygon points to the leaf bounding boxes
2795                         for (i = 0;i < 2;i++)
2796                         {
2797                                 leaf = (mleaf_t *)p->nodes[i];
2798                                 for (j = 0;j < p->numpoints;j++)
2799                                 {
2800                                         if (leaf->mins[0] > p->points[j*3+0]) leaf->mins[0] = p->points[j*3+0];
2801                                         if (leaf->mins[1] > p->points[j*3+1]) leaf->mins[1] = p->points[j*3+1];
2802                                         if (leaf->mins[2] > p->points[j*3+2]) leaf->mins[2] = p->points[j*3+2];
2803                                         if (leaf->maxs[0] < p->points[j*3+0]) leaf->maxs[0] = p->points[j*3+0];
2804                                         if (leaf->maxs[1] < p->points[j*3+1]) leaf->maxs[1] = p->points[j*3+1];
2805                                         if (leaf->maxs[2] < p->points[j*3+2]) leaf->maxs[2] = p->points[j*3+2];
2806                                 }
2807                         }
2808                 }
2809                 FreePortal(p);
2810                 p = pnext;
2811         }
2812         // now recalculate the node bounding boxes from the leafs
2813         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brush.data_nodes);
2814 }
2815
2816 /*
2817 =============
2818 AddPortalToNodes
2819 =============
2820 */
2821 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2822 {
2823         if (!front)
2824                 Host_Error("AddPortalToNodes: NULL front node");
2825         if (!back)
2826                 Host_Error("AddPortalToNodes: NULL back node");
2827         if (p->nodes[0] || p->nodes[1])
2828                 Host_Error("AddPortalToNodes: already included");
2829         // note: front == back is handled gracefully, because leaf 0 is the shared solid leaf, it can often have portals with the same leaf on both sides
2830
2831         p->nodes[0] = front;
2832         p->next[0] = (portal_t *)front->portals;
2833         front->portals = (mportal_t *)p;
2834
2835         p->nodes[1] = back;
2836         p->next[1] = (portal_t *)back->portals;
2837         back->portals = (mportal_t *)p;
2838 }
2839
2840 /*
2841 =============
2842 RemovePortalFromNode
2843 =============
2844 */
2845 static void RemovePortalFromNodes(portal_t *portal)
2846 {
2847         int i;
2848         mnode_t *node;
2849         void **portalpointer;
2850         portal_t *t;
2851         for (i = 0;i < 2;i++)
2852         {
2853                 node = portal->nodes[i];
2854
2855                 portalpointer = (void **) &node->portals;
2856                 while (1)
2857                 {
2858                         t = (portal_t *)*portalpointer;
2859                         if (!t)
2860                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2861
2862                         if (t == portal)
2863                         {
2864                                 if (portal->nodes[0] == node)
2865                                 {
2866                                         *portalpointer = portal->next[0];
2867                                         portal->nodes[0] = NULL;
2868                                 }
2869                                 else if (portal->nodes[1] == node)
2870                                 {
2871                                         *portalpointer = portal->next[1];
2872                                         portal->nodes[1] = NULL;
2873                                 }
2874                                 else
2875                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2876                                 break;
2877                         }
2878
2879                         if (t->nodes[0] == node)
2880                                 portalpointer = (void **) &t->next[0];
2881                         else if (t->nodes[1] == node)
2882                                 portalpointer = (void **) &t->next[1];
2883                         else
2884                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2885                 }
2886         }
2887 }
2888
2889 #define PORTAL_DIST_EPSILON (1.0 / 32.0)
2890 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2891 {
2892         int i, side;
2893         mnode_t *front, *back, *other_node;
2894         mplane_t clipplane, *plane;
2895         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2896         int numfrontpoints, numbackpoints;
2897         double frontpoints[3*MAX_PORTALPOINTS], backpoints[3*MAX_PORTALPOINTS];
2898
2899         // if a leaf, we're done
2900         if (!node->plane)
2901                 return;
2902
2903         plane = node->plane;
2904
2905         front = node->children[0];
2906         back = node->children[1];
2907         if (front == back)
2908                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2909
2910         // create the new portal by generating a polygon for the node plane,
2911         // and clipping it by all of the other portals(which came from nodes above this one)
2912         nodeportal = AllocPortal();
2913         nodeportal->plane = *plane;
2914
2915         // TODO: calculate node bounding boxes during recursion and calculate a maximum plane size accordingly to improve precision (as most maps do not need 1 billion unit plane polygons)
2916         PolygonD_QuadForPlane(nodeportal->points, nodeportal->plane.normal[0], nodeportal->plane.normal[1], nodeportal->plane.normal[2], nodeportal->plane.dist, 1024.0*1024.0*1024.0);
2917         nodeportal->numpoints = 4;
2918         side = 0;       // shut up compiler warning
2919         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2920         {
2921                 clipplane = portal->plane;
2922                 if (portal->nodes[0] == portal->nodes[1])
2923                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2924                 if (portal->nodes[0] == node)
2925                         side = 0;
2926                 else if (portal->nodes[1] == node)
2927                 {
2928                         clipplane.dist = -clipplane.dist;
2929                         VectorNegate(clipplane.normal, clipplane.normal);
2930                         side = 1;
2931                 }
2932                 else
2933                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2934
2935                 for (i = 0;i < nodeportal->numpoints*3;i++)
2936                         frontpoints[i] = nodeportal->points[i];
2937                 PolygonD_Divide(nodeportal->numpoints, frontpoints, clipplane.normal[0], clipplane.normal[1], clipplane.normal[2], clipplane.dist, PORTAL_DIST_EPSILON, MAX_PORTALPOINTS, nodeportal->points, &nodeportal->numpoints, 0, NULL, NULL, NULL);
2938                 if (nodeportal->numpoints <= 0 || nodeportal->numpoints >= MAX_PORTALPOINTS)
2939                         break;
2940         }
2941
2942         if (nodeportal->numpoints < 3)
2943         {
2944                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2945                 nodeportal->numpoints = 0;
2946         }
2947         else if (nodeportal->numpoints >= MAX_PORTALPOINTS)
2948         {
2949                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal has too many points\n");
2950                 nodeportal->numpoints = 0;
2951         }
2952
2953         AddPortalToNodes(nodeportal, front, back);
2954
2955         // split the portals of this node along this node's plane and assign them to the children of this node
2956         // (migrating the portals downward through the tree)
2957         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2958         {
2959                 if (portal->nodes[0] == portal->nodes[1])
2960                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2961                 if (portal->nodes[0] == node)
2962                         side = 0;
2963                 else if (portal->nodes[1] == node)
2964                         side = 1;
2965                 else
2966                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2967                 nextportal = portal->next[side];
2968                 if (!portal->numpoints)
2969                         continue;
2970
2971                 other_node = portal->nodes[!side];
2972                 RemovePortalFromNodes(portal);
2973
2974                 // cut the portal into two portals, one on each side of the node plane
2975                 PolygonD_Divide(portal->numpoints, portal->points, plane->normal[0], plane->normal[1], plane->normal[2], plane->dist, PORTAL_DIST_EPSILON, MAX_PORTALPOINTS, frontpoints, &numfrontpoints, MAX_PORTALPOINTS, backpoints, &numbackpoints, NULL);
2976
2977                 if (!numfrontpoints)
2978                 {
2979                         if (side == 0)
2980                                 AddPortalToNodes(portal, back, other_node);
2981                         else
2982                                 AddPortalToNodes(portal, other_node, back);
2983                         continue;
2984                 }
2985                 if (!numbackpoints)
2986                 {
2987                         if (side == 0)
2988                                 AddPortalToNodes(portal, front, other_node);
2989                         else
2990                                 AddPortalToNodes(portal, other_node, front);
2991                         continue;
2992                 }
2993
2994                 // the portal is split
2995                 splitportal = AllocPortal();
2996                 temp = splitportal->chain;
2997                 *splitportal = *portal;
2998                 splitportal->chain = temp;
2999                 for (i = 0;i < numbackpoints*3;i++)
3000                         splitportal->points[i] = backpoints[i];
3001                 splitportal->numpoints = numbackpoints;
3002                 for (i = 0;i < numfrontpoints*3;i++)
3003                         portal->points[i] = frontpoints[i];
3004                 portal->numpoints = numfrontpoints;
3005
3006                 if (side == 0)
3007                 {
3008                         AddPortalToNodes(portal, front, other_node);
3009                         AddPortalToNodes(splitportal, back, other_node);
3010                 }
3011                 else
3012                 {
3013                         AddPortalToNodes(portal, other_node, front);
3014                         AddPortalToNodes(splitportal, other_node, back);
3015                 }
3016         }
3017
3018         Mod_Q1BSP_RecursiveNodePortals(front);
3019         Mod_Q1BSP_RecursiveNodePortals(back);
3020 }
3021
3022 static void Mod_Q1BSP_MakePortals(void)
3023 {
3024         portalchain = NULL;
3025         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brush.data_nodes);
3026         Mod_Q1BSP_FinalizePortals();
3027 }
3028
3029 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
3030 {
3031         int i, j, stylecounts[256], totalcount, remapstyles[256];
3032         msurface_t *surface;
3033         memset(stylecounts, 0, sizeof(stylecounts));
3034         for (i = 0;i < model->nummodelsurfaces;i++)
3035         {
3036                 surface = model->data_surfaces + model->firstmodelsurface + i;
3037                 for (j = 0;j < MAXLIGHTMAPS;j++)
3038                         stylecounts[surface->lightmapinfo->styles[j]]++;
3039         }
3040         totalcount = 0;
3041         model->brushq1.light_styles = 0;
3042         for (i = 0;i < 255;i++)
3043         {
3044                 if (stylecounts[i])
3045                 {
3046                         remapstyles[i] = model->brushq1.light_styles++;
3047                         totalcount += stylecounts[i] + 1;
3048                 }
3049         }
3050         if (!totalcount)
3051                 return;
3052         model->brushq1.light_style = (unsigned char *)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(unsigned char));
3053         model->brushq1.light_stylevalue = (int *)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(int));
3054         model->brushq1.light_styleupdatechains = (msurface_t ***)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(msurface_t **));
3055         model->brushq1.light_styleupdatechainsbuffer = (msurface_t **)Mem_Alloc(mempool, totalcount * sizeof(msurface_t *));
3056         model->brushq1.light_styles = 0;
3057         for (i = 0;i < 255;i++)
3058                 if (stylecounts[i])
3059                         model->brushq1.light_style[model->brushq1.light_styles++] = i;
3060         j = 0;
3061         for (i = 0;i < model->brushq1.light_styles;i++)
3062         {
3063                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
3064                 j += stylecounts[model->brushq1.light_style[i]] + 1;
3065         }
3066         for (i = 0;i < model->nummodelsurfaces;i++)
3067         {
3068                 surface = model->data_surfaces + model->firstmodelsurface + i;
3069                 for (j = 0;j < MAXLIGHTMAPS;j++)
3070                         if (surface->lightmapinfo->styles[j] != 255)
3071                                 *model->brushq1.light_styleupdatechains[remapstyles[surface->lightmapinfo->styles[j]]]++ = surface;
3072         }
3073         j = 0;
3074         for (i = 0;i < model->brushq1.light_styles;i++)
3075         {
3076                 *model->brushq1.light_styleupdatechains[i] = NULL;
3077                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
3078                 j += stylecounts[model->brushq1.light_style[i]] + 1;
3079         }
3080 }
3081
3082 //Returns PVS data for a given point
3083 //(note: can return NULL)
3084 static unsigned char *Mod_Q1BSP_GetPVS(model_t *model, const vec3_t p)
3085 {
3086         mnode_t *node;
3087         node = model->brush.data_nodes;
3088         while (node->plane)
3089                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
3090         if (((mleaf_t *)node)->clusterindex >= 0)
3091                 return model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
3092         else
3093                 return NULL;
3094 }
3095
3096 static void Mod_Q1BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, unsigned char *pvsbuffer, int pvsbytes, mnode_t *node)
3097 {
3098         while (node->plane)
3099         {
3100                 float d = PlaneDiff(org, node->plane);
3101                 if (d > radius)
3102                         node = node->children[0];
3103                 else if (d < -radius)
3104                         node = node->children[1];
3105                 else
3106                 {
3107                         // go down both sides
3108                         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
3109                         node = node->children[1];
3110                 }
3111         }
3112         // if this leaf is in a cluster, accumulate the pvs bits
3113         if (((mleaf_t *)node)->clusterindex >= 0)
3114         {
3115                 int i;
3116                 unsigned char *pvs = model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
3117                 for (i = 0;i < pvsbytes;i++)
3118                         pvsbuffer[i] |= pvs[i];
3119         }
3120 }
3121
3122 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
3123 //of the given point.
3124 static int Mod_Q1BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, unsigned char *pvsbuffer, int pvsbufferlength)
3125 {
3126         int bytes = model->brush.num_pvsclusterbytes;
3127         bytes = min(bytes, pvsbufferlength);
3128         if (r_novis.integer || !model->brush.num_pvsclusters || !Mod_Q1BSP_GetPVS(model, org))
3129         {
3130                 memset(pvsbuffer, 0xFF, bytes);
3131                 return bytes;
3132         }
3133         memset(pvsbuffer, 0, bytes);
3134         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brush.data_nodes);
3135         return bytes;
3136 }
3137
3138 static void Mod_Q1BSP_RoundUpToHullSize(model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
3139 {
3140         vec3_t size;
3141         const hull_t *hull;
3142
3143         VectorSubtract(inmaxs, inmins, size);
3144         if (cmodel->brush.ismcbsp)
3145         {
3146                 if (size[0] < 3)
3147                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3148                 else if (size[2] < 48) // pick the nearest of 40 or 56
3149                         hull = &cmodel->brushq1.hulls[2]; // 16x16x40
3150                 else
3151                         hull = &cmodel->brushq1.hulls[1]; // 16x16x56
3152         }
3153         else if (cmodel->brush.ishlbsp)
3154         {
3155                 if (size[0] < 3)
3156                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3157                 else if (size[0] <= 32)
3158                 {
3159                         if (size[2] < 54) // pick the nearest of 36 or 72
3160                                 hull = &cmodel->brushq1.hulls[3]; // 32x32x36
3161                         else
3162                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
3163                 }
3164                 else
3165                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
3166         }
3167         else
3168         {
3169                 if (size[0] < 3)
3170                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3171                 else if (size[0] <= 32)
3172                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
3173                 else
3174                         hull = &cmodel->brushq1.hulls[2]; // 64x64x88
3175         }
3176         VectorCopy(inmins, outmins);
3177         VectorAdd(inmins, hull->clip_size, outmaxs);
3178 }
3179
3180 void Mod_Q1BSP_Load(model_t *mod, void *buffer, void *bufferend)
3181 {
3182         int i, j, k;
3183         dheader_t *header;
3184         dmodel_t *bm;
3185         mempool_t *mainmempool;
3186         float dist, modelyawradius, modelradius, *vec;
3187         msurface_t *surface;
3188         int numshadowmeshtriangles;
3189         dheader_t _header;
3190         hullinfo_t hullinfo;
3191
3192         mod->type = mod_brushq1;
3193
3194         if (!memcmp (buffer, "MCBSPpad", 8))
3195         {
3196                 unsigned char   *index;
3197
3198                 mod->brush.ismcbsp = true;
3199                 mod->brush.ishlbsp = false;
3200
3201                 mod_base = (unsigned char*)buffer;
3202
3203                 index = mod_base;
3204                 index += 8;
3205                 i = SB_ReadInt (&index);
3206                 if (i != MCBSPVERSION)
3207                         Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i)", mod->name, i, MCBSPVERSION);
3208
3209         // read hull info
3210                 hullinfo.numhulls = LittleLong(*(int*)index); index += 4;
3211                 hullinfo.filehulls = hullinfo.numhulls;
3212                 VectorClear (hullinfo.hullsizes[0][0]);
3213                 VectorClear (hullinfo.hullsizes[0][1]);
3214                 for (i = 1; i < hullinfo.numhulls; i++)
3215                 {
3216                         hullinfo.hullsizes[i][0][0] = SB_ReadFloat (&index);
3217                         hullinfo.hullsizes[i][0][1] = SB_ReadFloat (&index);
3218                         hullinfo.hullsizes[i][0][2] = SB_ReadFloat (&index);
3219                         hullinfo.hullsizes[i][1][0] = SB_ReadFloat (&index);
3220                         hullinfo.hullsizes[i][1][1] = SB_ReadFloat (&index);
3221                         hullinfo.hullsizes[i][1][2] = SB_ReadFloat (&index);
3222                 }
3223
3224         // read lumps
3225                 _header.version = 0;
3226                 for (i = 0; i < HEADER_LUMPS; i++)
3227                 {
3228                         _header.lumps[i].fileofs = SB_ReadInt (&index);
3229                         _header.lumps[i].filelen = SB_ReadInt (&index);
3230                 }
3231
3232                 header = &_header;
3233         }
3234         else
3235         {
3236                 header = (dheader_t *)buffer;
3237
3238                 i = LittleLong(header->version);
3239                 if (i != BSPVERSION && i != 30)
3240                         Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i(Quake) or 30(HalfLife)", mod->name, i, BSPVERSION);
3241                 mod->brush.ishlbsp = i == 30;
3242                 mod->brush.ismcbsp = false;
3243
3244         // fill in hull info
3245                 VectorClear (hullinfo.hullsizes[0][0]);
3246                 VectorClear (hullinfo.hullsizes[0][1]);
3247                 if (mod->brush.ishlbsp)
3248                 {
3249                         hullinfo.numhulls = 4;
3250                         hullinfo.filehulls = 4;
3251                         VectorSet (hullinfo.hullsizes[1][0], -16, -16, -36);
3252                         VectorSet (hullinfo.hullsizes[1][1], 16, 16, 36);
3253                         VectorSet (hullinfo.hullsizes[2][0], -32, -32, -32);
3254                         VectorSet (hullinfo.hullsizes[2][1], 32, 32, 32);
3255                         VectorSet (hullinfo.hullsizes[3][0], -16, -16, -18);
3256                         VectorSet (hullinfo.hullsizes[3][1], 16, 16, 18);
3257                 }
3258                 else
3259                 {
3260                         hullinfo.numhulls = 3;
3261                         hullinfo.filehulls = 4;
3262                         VectorSet (hullinfo.hullsizes[1][0], -16, -16, -24);
3263                         VectorSet (hullinfo.hullsizes[1][1], 16, 16, 32);
3264                         VectorSet (hullinfo.hullsizes[2][0], -32, -32, -24);
3265                         VectorSet (hullinfo.hullsizes[2][1], 32, 32, 64);
3266                 }
3267
3268         // read lumps
3269                 mod_base = (unsigned char*)buffer;
3270                 for (i = 0; i < HEADER_LUMPS; i++)
3271                 {
3272                         header->lumps[i].fileofs = LittleLong(header->lumps[i].fileofs);
3273                         header->lumps[i].filelen = LittleLong(header->lumps[i].filelen);
3274                 }
3275         }
3276
3277         mod->soundfromcenter = true;
3278         mod->TraceBox = Mod_Q1BSP_TraceBox;
3279         mod->brush.SuperContentsFromNativeContents = Mod_Q1BSP_SuperContentsFromNativeContents;
3280         mod->brush.NativeContentsFromSuperContents = Mod_Q1BSP_NativeContentsFromSuperContents;
3281         mod->brush.GetPVS = Mod_Q1BSP_GetPVS;
3282         mod->brush.FatPVS = Mod_Q1BSP_FatPVS;
3283         mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
3284         mod->brush.BoxTouchingLeafPVS = Mod_Q1BSP_BoxTouchingLeafPVS;
3285         mod->brush.BoxTouchingVisibleLeafs = Mod_Q1BSP_BoxTouchingVisibleLeafs;
3286         mod->brush.FindBoxClusters = Mod_Q1BSP_FindBoxClusters;
3287         mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
3288         mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
3289         mod->brush.AmbientSoundLevelsForPoint = Mod_Q1BSP_AmbientSoundLevelsForPoint;
3290         mod->brush.RoundUpToHullSize = Mod_Q1BSP_RoundUpToHullSize;
3291         mod->brush.PointInLeaf = Mod_Q1BSP_PointInLeaf;
3292
3293         if (loadmodel->isworldmodel)
3294         {
3295                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
3296                 Cvar_SetValue("mcbsp", mod->brush.ismcbsp);
3297         }
3298
3299 // load into heap
3300
3301         // store which lightmap format to use
3302         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3303
3304         mod->brush.qw_md4sum = 0;
3305         mod->brush.qw_md4sum2 = 0;
3306         for (i = 0;i < HEADER_LUMPS;i++)
3307         {
3308                 if (i == LUMP_ENTITIES)
3309                         continue;
3310                 mod->brush.qw_md4sum ^= LittleLong(Com_BlockChecksum(mod_base + header->lumps[i].fileofs, header->lumps[i].filelen));
3311                 if (i == LUMP_VISIBILITY || i == LUMP_LEAFS || i == LUMP_NODES)
3312                         continue;
3313                 mod->brush.qw_md4sum2 ^= LittleLong(Com_BlockChecksum(mod_base + header->lumps[i].fileofs, header->lumps[i].filelen));
3314         }
3315
3316         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
3317         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
3318         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
3319         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
3320         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
3321         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
3322         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
3323         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
3324         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
3325         Mod_Q1BSP_LoadLeaffaces(&header->lumps[LUMP_MARKSURFACES]);
3326         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
3327         // load submodels before leafs because they contain the number of vis leafs
3328         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS], &hullinfo);
3329         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
3330         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
3331         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES], &hullinfo);
3332
3333         // check if the map supports transparent water rendering
3334         loadmodel->brush.supportwateralpha = Mod_Q1BSP_CheckWaterAlphaSupport();
3335
3336         if (!mod->brushq1.lightdata)
3337                 mod->brush.LightPoint = NULL;
3338
3339         if (mod->brushq1.data_compressedpvs)
3340                 Mem_Free(mod->brushq1.data_compressedpvs);
3341         mod->brushq1.data_compressedpvs = NULL;
3342         mod->brushq1.num_compressedpvs = 0;
3343
3344         Mod_Q1BSP_MakeHull0();
3345         Mod_Q1BSP_MakePortals();
3346
3347         mod->numframes = 2;             // regular and alternate animation
3348         mod->numskins = 1;
3349
3350         mainmempool = mod->mempool;
3351
3352         // make a single combined shadow mesh to allow optimized shadow volume creation
3353         numshadowmeshtriangles = 0;
3354         for (j = 0, surface = loadmodel->data_surfaces;j <