some initial changes to support terrain texture blending someday
[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                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
2264                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
2265         }
2266 }
2267
2268 static void Mod_Q1BSP_LoadNodes(lump_t *l)
2269 {
2270         int                     i, j, count, p;
2271         dnode_t         *in;
2272         mnode_t         *out;
2273
2274         in = (dnode_t *)(mod_base + l->fileofs);
2275         if (l->filelen % sizeof(*in))
2276                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
2277         count = l->filelen / sizeof(*in);
2278         out = (mnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2279
2280         loadmodel->brush.data_nodes = out;
2281         loadmodel->brush.num_nodes = count;
2282
2283         for ( i=0 ; i<count ; i++, in++, out++)
2284         {
2285                 for (j=0 ; j<3 ; j++)
2286                 {
2287                         out->mins[j] = LittleShort(in->mins[j]);
2288                         out->maxs[j] = LittleShort(in->maxs[j]);
2289                 }
2290
2291                 p = LittleLong(in->planenum);
2292                 out->plane = loadmodel->brush.data_planes + p;
2293
2294                 out->firstsurface = LittleShort(in->firstface);
2295                 out->numsurfaces = LittleShort(in->numfaces);
2296
2297                 for (j=0 ; j<2 ; j++)
2298                 {
2299                         p = LittleShort(in->children[j]);
2300                         if (p >= 0)
2301                                 out->children[j] = loadmodel->brush.data_nodes + p;
2302                         else
2303                                 out->children[j] = (mnode_t *)(loadmodel->brush.data_leafs + (-1 - p));
2304                 }
2305         }
2306
2307         Mod_Q1BSP_LoadNodes_RecursiveSetParent(loadmodel->brush.data_nodes, NULL);      // sets nodes and leafs
2308 }
2309
2310 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
2311 {
2312         dleaf_t *in;
2313         mleaf_t *out;
2314         int i, j, count, p;
2315
2316         in = (dleaf_t *)(mod_base + l->fileofs);
2317         if (l->filelen % sizeof(*in))
2318                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
2319         count = l->filelen / sizeof(*in);
2320         out = (mleaf_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2321
2322         loadmodel->brush.data_leafs = out;
2323         loadmodel->brush.num_leafs = count;
2324         // get visleafs from the submodel data
2325         loadmodel->brush.num_pvsclusters = loadmodel->brushq1.submodels[0].visleafs;
2326         loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters+7)>>3;
2327         loadmodel->brush.data_pvsclusters = (unsigned char *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2328         memset(loadmodel->brush.data_pvsclusters, 0xFF, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2329
2330         for ( i=0 ; i<count ; i++, in++, out++)
2331         {
2332                 for (j=0 ; j<3 ; j++)
2333                 {
2334                         out->mins[j] = LittleShort(in->mins[j]);
2335                         out->maxs[j] = LittleShort(in->maxs[j]);
2336                 }
2337
2338                 // FIXME: this function could really benefit from some error checking
2339
2340                 out->contents = LittleLong(in->contents);
2341
2342                 out->firstleafsurface = loadmodel->brush.data_leafsurfaces + LittleShort(in->firstmarksurface);
2343                 out->numleafsurfaces = LittleShort(in->nummarksurfaces);
2344                 if (out->firstleafsurface < 0 || LittleShort(in->firstmarksurface) + out->numleafsurfaces > loadmodel->brush.num_leafsurfaces)
2345                 {
2346                         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);
2347                         out->firstleafsurface = NULL;
2348                         out->numleafsurfaces = 0;
2349                 }
2350
2351                 out->clusterindex = i - 1;
2352                 if (out->clusterindex >= loadmodel->brush.num_pvsclusters)
2353                         out->clusterindex = -1;
2354
2355                 p = LittleLong(in->visofs);
2356                 // ignore visofs errors on leaf 0 (solid)
2357                 if (p >= 0 && out->clusterindex >= 0)
2358                 {
2359                         if (p >= loadmodel->brushq1.num_compressedpvs)
2360                                 Con_Print("Mod_Q1BSP_LoadLeafs: invalid visofs\n");
2361                         else
2362                                 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);
2363                 }
2364
2365                 for (j = 0;j < 4;j++)
2366                         out->ambient_sound_level[j] = in->ambient_level[j];
2367
2368                 // FIXME: Insert caustics here
2369         }
2370 }
2371
2372 qboolean Mod_Q1BSP_CheckWaterAlphaSupport(void)
2373 {
2374         int i, j;
2375         mleaf_t *leaf;
2376         const unsigned char *pvs;
2377         // check all liquid leafs to see if they can see into empty leafs, if any
2378         // can we can assume this map supports r_wateralpha
2379         for (i = 0, leaf = loadmodel->brush.data_leafs;i < loadmodel->brush.num_leafs;i++, leaf++)
2380         {
2381                 if ((leaf->contents == CONTENTS_WATER || leaf->contents == CONTENTS_SLIME) && (leaf->clusterindex >= 0 && loadmodel->brush.data_pvsclusters))
2382                 {
2383                         pvs = loadmodel->brush.data_pvsclusters + leaf->clusterindex * loadmodel->brush.num_pvsclusterbytes;
2384                         for (j = 0;j < loadmodel->brush.num_leafs;j++)
2385                                 if (CHECKPVSBIT(pvs, loadmodel->brush.data_leafs[j].clusterindex) && loadmodel->brush.data_leafs[j].contents == CONTENTS_EMPTY)
2386                                         return true;
2387                 }
2388         }
2389         return false;
2390 }
2391
2392 static void Mod_Q1BSP_LoadClipnodes(lump_t *l, hullinfo_t *hullinfo)
2393 {
2394         dclipnode_t *in, *out;
2395         int                     i, count;
2396         hull_t          *hull;
2397
2398         in = (dclipnode_t *)(mod_base + l->fileofs);
2399         if (l->filelen % sizeof(*in))
2400                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2401         count = l->filelen / sizeof(*in);
2402         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2403
2404         loadmodel->brushq1.clipnodes = out;
2405         loadmodel->brushq1.numclipnodes = count;
2406
2407         for (i = 1; i < hullinfo->numhulls; i++)
2408         {
2409                 hull = &loadmodel->brushq1.hulls[i];
2410                 hull->clipnodes = out;
2411                 hull->firstclipnode = 0;
2412                 hull->lastclipnode = count-1;
2413                 hull->planes = loadmodel->brush.data_planes;
2414                 hull->clip_mins[0] = hullinfo->hullsizes[i][0][0];
2415                 hull->clip_mins[1] = hullinfo->hullsizes[i][0][1];
2416                 hull->clip_mins[2] = hullinfo->hullsizes[i][0][2];
2417                 hull->clip_maxs[0] = hullinfo->hullsizes[i][1][0];
2418                 hull->clip_maxs[1] = hullinfo->hullsizes[i][1][1];
2419                 hull->clip_maxs[2] = hullinfo->hullsizes[i][1][2];
2420                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2421         }
2422
2423         for (i=0 ; i<count ; i++, out++, in++)
2424         {
2425                 out->planenum = LittleLong(in->planenum);
2426                 out->children[0] = LittleShort(in->children[0]);
2427                 out->children[1] = LittleShort(in->children[1]);
2428                 if (out->planenum < 0 || out->planenum >= loadmodel->brush.num_planes)
2429                         Host_Error("Corrupt clipping hull(out of range planenum)");
2430                 if (out->children[0] >= count || out->children[1] >= count)
2431                         Host_Error("Corrupt clipping hull(out of range child)");
2432         }
2433 }
2434
2435 //Duplicate the drawing hull structure as a clipping hull
2436 static void Mod_Q1BSP_MakeHull0(void)
2437 {
2438         mnode_t         *in;
2439         dclipnode_t *out;
2440         int                     i;
2441         hull_t          *hull;
2442
2443         hull = &loadmodel->brushq1.hulls[0];
2444
2445         in = loadmodel->brush.data_nodes;
2446         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_nodes * sizeof(dclipnode_t));
2447
2448         hull->clipnodes = out;
2449         hull->firstclipnode = 0;
2450         hull->lastclipnode = loadmodel->brush.num_nodes - 1;
2451         hull->planes = loadmodel->brush.data_planes;
2452
2453         for (i = 0;i < loadmodel->brush.num_nodes;i++, out++, in++)
2454         {
2455                 out->planenum = in->plane - loadmodel->brush.data_planes;
2456                 out->children[0] = in->children[0]->plane ? in->children[0] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[0])->contents;
2457                 out->children[1] = in->children[1]->plane ? in->children[1] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[1])->contents;
2458         }
2459 }
2460
2461 static void Mod_Q1BSP_LoadLeaffaces(lump_t *l)
2462 {
2463         int i, j;
2464         short *in;
2465
2466         in = (short *)(mod_base + l->fileofs);
2467         if (l->filelen % sizeof(*in))
2468                 Host_Error("Mod_Q1BSP_LoadLeaffaces: funny lump size in %s",loadmodel->name);
2469         loadmodel->brush.num_leafsurfaces = l->filelen / sizeof(*in);
2470         loadmodel->brush.data_leafsurfaces = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_leafsurfaces * sizeof(int));
2471
2472         for (i = 0;i < loadmodel->brush.num_leafsurfaces;i++)
2473         {
2474                 j = (unsigned) LittleShort(in[i]);
2475                 if (j >= loadmodel->num_surfaces)
2476                         Host_Error("Mod_Q1BSP_LoadLeaffaces: bad surface number");
2477                 loadmodel->brush.data_leafsurfaces[i] = j;
2478         }
2479 }
2480
2481 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2482 {
2483         int             i;
2484         int             *in;
2485
2486         in = (int *)(mod_base + l->fileofs);
2487         if (l->filelen % sizeof(*in))
2488                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2489         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2490         loadmodel->brushq1.surfedges = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2491
2492         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2493                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2494 }
2495
2496
2497 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2498 {
2499         int                     i;
2500         mplane_t        *out;
2501         dplane_t        *in;
2502
2503         in = (dplane_t *)(mod_base + l->fileofs);
2504         if (l->filelen % sizeof(*in))
2505                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2506
2507         loadmodel->brush.num_planes = l->filelen / sizeof(*in);
2508         loadmodel->brush.data_planes = out = (mplane_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_planes * sizeof(*out));
2509
2510         for (i = 0;i < loadmodel->brush.num_planes;i++, in++, out++)
2511         {
2512                 out->normal[0] = LittleFloat(in->normal[0]);
2513                 out->normal[1] = LittleFloat(in->normal[1]);
2514                 out->normal[2] = LittleFloat(in->normal[2]);
2515                 out->dist = LittleFloat(in->dist);
2516
2517                 PlaneClassify(out);
2518         }
2519 }
2520
2521 static void Mod_Q1BSP_LoadMapBrushes(void)
2522 {
2523 #if 0
2524 // unfinished
2525         int submodel, numbrushes;
2526         qboolean firstbrush;
2527         char *text, *maptext;
2528         char mapfilename[MAX_QPATH];
2529         FS_StripExtension (loadmodel->name, mapfilename, sizeof (mapfilename));
2530         strlcat (mapfilename, ".map", sizeof (mapfilename));
2531         maptext = (unsigned char*) FS_LoadFile(mapfilename, tempmempool, false, NULL);
2532         if (!maptext)
2533                 return;
2534         text = maptext;
2535         if (!COM_ParseTokenConsole(&data))
2536                 return; // error
2537         submodel = 0;
2538         for (;;)
2539         {
2540                 if (!COM_ParseTokenConsole(&data))
2541                         break;
2542                 if (com_token[0] != '{')
2543                         return; // error
2544                 // entity
2545                 firstbrush = true;
2546                 numbrushes = 0;
2547                 maxbrushes = 256;
2548                 brushes = Mem_Alloc(loadmodel->mempool, maxbrushes * sizeof(mbrush_t));
2549                 for (;;)
2550                 {
2551                         if (!COM_ParseTokenConsole(&data))
2552                                 return; // error
2553                         if (com_token[0] == '}')
2554                                 break; // end of entity
2555                         if (com_token[0] == '{')
2556                         {
2557                                 // brush
2558                                 if (firstbrush)
2559                                 {
2560                                         if (submodel)
2561                                         {
2562                                                 if (submodel > loadmodel->brush.numsubmodels)
2563                                                 {
2564                                                         Con_Printf("Mod_Q1BSP_LoadMapBrushes: .map has more submodels than .bsp!\n");
2565                                                         model = NULL;
2566                                                 }
2567                                                 else
2568                                                         model = loadmodel->brush.submodels[submodel];
2569                                         }
2570                                         else
2571                                                 model = loadmodel;
2572                                 }
2573                                 for (;;)
2574                                 {
2575                                         if (!COM_ParseTokenConsole(&data))
2576                                                 return; // error
2577                                         if (com_token[0] == '}')
2578                                                 break; // end of brush
2579                                         // each brush face should be this format:
2580                                         // ( x y z ) ( x y z ) ( x y z ) texture scroll_s scroll_t rotateangle scale_s scale_t
2581                                         // FIXME: support hl .map format
2582                                         for (pointnum = 0;pointnum < 3;pointnum++)
2583                                         {
2584                                                 COM_ParseTokenConsole(&data);
2585                                                 for (componentnum = 0;componentnum < 3;componentnum++)
2586                                                 {
2587                                                         COM_ParseTokenConsole(&data);
2588                                                         point[pointnum][componentnum] = atof(com_token);
2589                                                 }
2590                                                 COM_ParseTokenConsole(&data);
2591                                         }
2592                                         COM_ParseTokenConsole(&data);
2593                                         strlcpy(facetexture, com_token, sizeof(facetexture));
2594                                         COM_ParseTokenConsole(&data);
2595                                         //scroll_s = atof(com_token);
2596                                         COM_ParseTokenConsole(&data);
2597                                         //scroll_t = atof(com_token);
2598                                         COM_ParseTokenConsole(&data);
2599                                         //rotate = atof(com_token);
2600                                         COM_ParseTokenConsole(&data);
2601                                         //scale_s = atof(com_token);
2602                                         COM_ParseTokenConsole(&data);
2603                                         //scale_t = atof(com_token);
2604                                         TriangleNormal(point[0], point[1], point[2], planenormal);
2605                                         VectorNormalizeDouble(planenormal);
2606                                         planedist = DotProduct(point[0], planenormal);
2607                                         //ChooseTexturePlane(planenormal, texturevector[0], texturevector[1]);
2608                                 }
2609                                 continue;
2610                         }
2611                 }
2612         }
2613 #endif
2614 }
2615
2616
2617 #define MAX_PORTALPOINTS 64
2618
2619 typedef struct portal_s
2620 {
2621         mplane_t plane;
2622         mnode_t *nodes[2];              // [0] = front side of plane
2623         struct portal_s *next[2];
2624         int numpoints;
2625         double points[3*MAX_PORTALPOINTS];
2626         struct portal_s *chain; // all portals are linked into a list
2627 }
2628 portal_t;
2629
2630 static portal_t *portalchain;
2631
2632 /*
2633 ===========
2634 AllocPortal
2635 ===========
2636 */
2637 static portal_t *AllocPortal(void)
2638 {
2639         portal_t *p;
2640         p = (portal_t *)Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2641         p->chain = portalchain;
2642         portalchain = p;
2643         return p;
2644 }
2645
2646 static void FreePortal(portal_t *p)
2647 {
2648         Mem_Free(p);
2649 }
2650
2651 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2652 {
2653         // process only nodes (leafs already had their box calculated)
2654         if (!node->plane)
2655                 return;
2656
2657         // calculate children first
2658         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2659         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2660
2661         // make combined bounding box from children
2662         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2663         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2664         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2665         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2666         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2667         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2668 }
2669
2670 static void Mod_Q1BSP_FinalizePortals(void)
2671 {
2672         int i, j, numportals, numpoints;
2673         portal_t *p, *pnext;
2674         mportal_t *portal;
2675         mvertex_t *point;
2676         mleaf_t *leaf, *endleaf;
2677
2678         // tally up portal and point counts and recalculate bounding boxes for all
2679         // leafs (because qbsp is very sloppy)
2680         leaf = loadmodel->brush.data_leafs;
2681         endleaf = leaf + loadmodel->brush.num_leafs;
2682         for (;leaf < endleaf;leaf++)
2683         {
2684                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2685                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2686         }
2687         p = portalchain;
2688         numportals = 0;
2689         numpoints = 0;
2690         while (p)
2691         {
2692                 // note: this check must match the one below or it will usually corrupt memory
2693                 // 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
2694                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1] && ((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2695                 {
2696                         numportals += 2;
2697                         numpoints += p->numpoints * 2;
2698                 }
2699                 p = p->chain;
2700         }
2701         loadmodel->brush.data_portals = (mportal_t *)Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2702         loadmodel->brush.num_portals = numportals;
2703         loadmodel->brush.data_portalpoints = (mvertex_t *)((unsigned char *) loadmodel->brush.data_portals + numportals * sizeof(mportal_t));
2704         loadmodel->brush.num_portalpoints = numpoints;
2705         // clear all leaf portal chains
2706         for (i = 0;i < loadmodel->brush.num_leafs;i++)
2707                 loadmodel->brush.data_leafs[i].portals = NULL;
2708         // process all portals in the global portal chain, while freeing them
2709         portal = loadmodel->brush.data_portals;
2710         point = loadmodel->brush.data_portalpoints;
2711         p = portalchain;
2712         portalchain = NULL;
2713         while (p)
2714         {
2715                 pnext = p->chain;
2716
2717                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1])
2718                 {
2719                         // note: this check must match the one above or it will usually corrupt memory
2720                         // 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
2721                         if (((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2722                         {
2723                                 // first make the back to front portal(forward portal)
2724                                 portal->points = point;
2725                                 portal->numpoints = p->numpoints;
2726                                 portal->plane.dist = p->plane.dist;
2727                                 VectorCopy(p->plane.normal, portal->plane.normal);
2728                                 portal->here = (mleaf_t *)p->nodes[1];
2729                                 portal->past = (mleaf_t *)p->nodes[0];
2730                                 // copy points
2731                                 for (j = 0;j < portal->numpoints;j++)
2732                                 {
2733                                         VectorCopy(p->points + j*3, point->position);
2734                                         point++;
2735                                 }
2736                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2737                                 PlaneClassify(&portal->plane);
2738
2739                                 // link into leaf's portal chain
2740                                 portal->next = portal->here->portals;
2741                                 portal->here->portals = portal;
2742
2743                                 // advance to next portal
2744                                 portal++;
2745
2746                                 // then make the front to back portal(backward portal)
2747                                 portal->points = point;
2748                                 portal->numpoints = p->numpoints;
2749                                 portal->plane.dist = -p->plane.dist;
2750                                 VectorNegate(p->plane.normal, portal->plane.normal);
2751                                 portal->here = (mleaf_t *)p->nodes[0];
2752                                 portal->past = (mleaf_t *)p->nodes[1];
2753                                 // copy points
2754                                 for (j = portal->numpoints - 1;j >= 0;j--)
2755                                 {
2756                                         VectorCopy(p->points + j*3, point->position);
2757                                         point++;
2758                                 }
2759                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2760                                 PlaneClassify(&portal->plane);
2761
2762                                 // link into leaf's portal chain
2763                                 portal->next = portal->here->portals;
2764                                 portal->here->portals = portal;
2765
2766                                 // advance to next portal
2767                                 portal++;
2768                         }
2769                         // add the portal's polygon points to the leaf bounding boxes
2770                         for (i = 0;i < 2;i++)
2771                         {
2772                                 leaf = (mleaf_t *)p->nodes[i];
2773                                 for (j = 0;j < p->numpoints;j++)
2774                                 {
2775                                         if (leaf->mins[0] > p->points[j*3+0]) leaf->mins[0] = p->points[j*3+0];
2776                                         if (leaf->mins[1] > p->points[j*3+1]) leaf->mins[1] = p->points[j*3+1];
2777                                         if (leaf->mins[2] > p->points[j*3+2]) leaf->mins[2] = p->points[j*3+2];
2778                                         if (leaf->maxs[0] < p->points[j*3+0]) leaf->maxs[0] = p->points[j*3+0];
2779                                         if (leaf->maxs[1] < p->points[j*3+1]) leaf->maxs[1] = p->points[j*3+1];
2780                                         if (leaf->maxs[2] < p->points[j*3+2]) leaf->maxs[2] = p->points[j*3+2];
2781                                 }
2782                         }
2783                 }
2784                 FreePortal(p);
2785                 p = pnext;
2786         }
2787         // now recalculate the node bounding boxes from the leafs
2788         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brush.data_nodes);
2789 }
2790
2791 /*
2792 =============
2793 AddPortalToNodes
2794 =============
2795 */
2796 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2797 {
2798         if (!front)
2799                 Host_Error("AddPortalToNodes: NULL front node");
2800         if (!back)
2801                 Host_Error("AddPortalToNodes: NULL back node");
2802         if (p->nodes[0] || p->nodes[1])
2803                 Host_Error("AddPortalToNodes: already included");
2804         // 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
2805
2806         p->nodes[0] = front;
2807         p->next[0] = (portal_t *)front->portals;
2808         front->portals = (mportal_t *)p;
2809
2810         p->nodes[1] = back;
2811         p->next[1] = (portal_t *)back->portals;
2812         back->portals = (mportal_t *)p;
2813 }
2814
2815 /*
2816 =============
2817 RemovePortalFromNode
2818 =============
2819 */
2820 static void RemovePortalFromNodes(portal_t *portal)
2821 {
2822         int i;
2823         mnode_t *node;
2824         void **portalpointer;
2825         portal_t *t;
2826         for (i = 0;i < 2;i++)
2827         {
2828                 node = portal->nodes[i];
2829
2830                 portalpointer = (void **) &node->portals;
2831                 while (1)
2832                 {
2833                         t = (portal_t *)*portalpointer;
2834                         if (!t)
2835                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2836
2837                         if (t == portal)
2838                         {
2839                                 if (portal->nodes[0] == node)
2840                                 {
2841                                         *portalpointer = portal->next[0];
2842                                         portal->nodes[0] = NULL;
2843                                 }
2844                                 else if (portal->nodes[1] == node)
2845                                 {
2846                                         *portalpointer = portal->next[1];
2847                                         portal->nodes[1] = NULL;
2848                                 }
2849                                 else
2850                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2851                                 break;
2852                         }
2853
2854                         if (t->nodes[0] == node)
2855                                 portalpointer = (void **) &t->next[0];
2856                         else if (t->nodes[1] == node)
2857                                 portalpointer = (void **) &t->next[1];
2858                         else
2859                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2860                 }
2861         }
2862 }
2863
2864 #define PORTAL_DIST_EPSILON (1.0 / 32.0)
2865 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2866 {
2867         int i, side;
2868         mnode_t *front, *back, *other_node;
2869         mplane_t clipplane, *plane;
2870         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2871         int numfrontpoints, numbackpoints;
2872         double frontpoints[3*MAX_PORTALPOINTS], backpoints[3*MAX_PORTALPOINTS];
2873
2874         // if a leaf, we're done
2875         if (!node->plane)
2876                 return;
2877
2878         plane = node->plane;
2879
2880         front = node->children[0];
2881         back = node->children[1];
2882         if (front == back)
2883                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2884
2885         // create the new portal by generating a polygon for the node plane,
2886         // and clipping it by all of the other portals(which came from nodes above this one)
2887         nodeportal = AllocPortal();
2888         nodeportal->plane = *plane;
2889
2890         // 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)
2891         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);
2892         nodeportal->numpoints = 4;
2893         side = 0;       // shut up compiler warning
2894         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2895         {
2896                 clipplane = portal->plane;
2897                 if (portal->nodes[0] == portal->nodes[1])
2898                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2899                 if (portal->nodes[0] == node)
2900                         side = 0;
2901                 else if (portal->nodes[1] == node)
2902                 {
2903                         clipplane.dist = -clipplane.dist;
2904                         VectorNegate(clipplane.normal, clipplane.normal);
2905                         side = 1;
2906                 }
2907                 else
2908                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2909
2910                 for (i = 0;i < nodeportal->numpoints*3;i++)
2911                         frontpoints[i] = nodeportal->points[i];
2912                 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);
2913                 if (nodeportal->numpoints <= 0 || nodeportal->numpoints >= MAX_PORTALPOINTS)
2914                         break;
2915         }
2916
2917         if (nodeportal->numpoints < 3)
2918         {
2919                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2920                 nodeportal->numpoints = 0;
2921         }
2922         else if (nodeportal->numpoints >= MAX_PORTALPOINTS)
2923         {
2924                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal has too many points\n");
2925                 nodeportal->numpoints = 0;
2926         }
2927
2928         AddPortalToNodes(nodeportal, front, back);
2929
2930         // split the portals of this node along this node's plane and assign them to the children of this node
2931         // (migrating the portals downward through the tree)
2932         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2933         {
2934                 if (portal->nodes[0] == portal->nodes[1])
2935                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2936                 if (portal->nodes[0] == node)
2937                         side = 0;
2938                 else if (portal->nodes[1] == node)
2939                         side = 1;
2940                 else
2941                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2942                 nextportal = portal->next[side];
2943                 if (!portal->numpoints)
2944                         continue;
2945
2946                 other_node = portal->nodes[!side];
2947                 RemovePortalFromNodes(portal);
2948
2949                 // cut the portal into two portals, one on each side of the node plane
2950                 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);
2951
2952                 if (!numfrontpoints)
2953                 {
2954                         if (side == 0)
2955                                 AddPortalToNodes(portal, back, other_node);
2956                         else
2957                                 AddPortalToNodes(portal, other_node, back);
2958                         continue;
2959                 }
2960                 if (!numbackpoints)
2961                 {
2962                         if (side == 0)
2963                                 AddPortalToNodes(portal, front, other_node);
2964                         else
2965                                 AddPortalToNodes(portal, other_node, front);
2966                         continue;
2967                 }
2968
2969                 // the portal is split
2970                 splitportal = AllocPortal();
2971                 temp = splitportal->chain;
2972                 *splitportal = *portal;
2973                 splitportal->chain = temp;
2974                 for (i = 0;i < numbackpoints*3;i++)
2975                         splitportal->points[i] = backpoints[i];
2976                 splitportal->numpoints = numbackpoints;
2977                 for (i = 0;i < numfrontpoints*3;i++)
2978                         portal->points[i] = frontpoints[i];
2979                 portal->numpoints = numfrontpoints;
2980
2981                 if (side == 0)
2982                 {
2983                         AddPortalToNodes(portal, front, other_node);
2984                         AddPortalToNodes(splitportal, back, other_node);
2985                 }
2986                 else
2987                 {
2988                         AddPortalToNodes(portal, other_node, front);
2989                         AddPortalToNodes(splitportal, other_node, back);
2990                 }
2991         }
2992
2993         Mod_Q1BSP_RecursiveNodePortals(front);
2994         Mod_Q1BSP_RecursiveNodePortals(back);
2995 }
2996
2997 static void Mod_Q1BSP_MakePortals(void)
2998 {
2999         portalchain = NULL;
3000         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brush.data_nodes);
3001         Mod_Q1BSP_FinalizePortals();
3002 }
3003
3004 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
3005 {
3006         int i, j, stylecounts[256], totalcount, remapstyles[256];
3007         msurface_t *surface;
3008         memset(stylecounts, 0, sizeof(stylecounts));
3009         for (i = 0;i < model->nummodelsurfaces;i++)
3010         {
3011                 surface = model->data_surfaces + model->firstmodelsurface + i;
3012                 for (j = 0;j < MAXLIGHTMAPS;j++)
3013                         stylecounts[surface->lightmapinfo->styles[j]]++;
3014         }
3015         totalcount = 0;
3016         model->brushq1.light_styles = 0;
3017         for (i = 0;i < 255;i++)
3018         {
3019                 if (stylecounts[i])
3020                 {
3021                         remapstyles[i] = model->brushq1.light_styles++;
3022                         totalcount += stylecounts[i] + 1;
3023                 }
3024         }
3025         if (!totalcount)
3026                 return;
3027         model->brushq1.light_style = (unsigned char *)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(unsigned char));
3028         model->brushq1.light_stylevalue = (int *)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(int));
3029         model->brushq1.light_styleupdatechains = (msurface_t ***)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(msurface_t **));
3030         model->brushq1.light_styleupdatechainsbuffer = (msurface_t **)Mem_Alloc(mempool, totalcount * sizeof(msurface_t *));
3031         model->brushq1.light_styles = 0;
3032         for (i = 0;i < 255;i++)
3033                 if (stylecounts[i])
3034                         model->brushq1.light_style[model->brushq1.light_styles++] = i;
3035         j = 0;
3036         for (i = 0;i < model->brushq1.light_styles;i++)
3037         {
3038                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
3039                 j += stylecounts[model->brushq1.light_style[i]] + 1;
3040         }
3041         for (i = 0;i < model->nummodelsurfaces;i++)
3042         {
3043                 surface = model->data_surfaces + model->firstmodelsurface + i;
3044                 for (j = 0;j < MAXLIGHTMAPS;j++)
3045                         if (surface->lightmapinfo->styles[j] != 255)
3046                                 *model->brushq1.light_styleupdatechains[remapstyles[surface->lightmapinfo->styles[j]]]++ = surface;
3047         }
3048         j = 0;
3049         for (i = 0;i < model->brushq1.light_styles;i++)
3050         {
3051                 *model->brushq1.light_styleupdatechains[i] = NULL;
3052                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
3053                 j += stylecounts[model->brushq1.light_style[i]] + 1;
3054         }
3055 }
3056
3057 //Returns PVS data for a given point
3058 //(note: can return NULL)
3059 static unsigned char *Mod_Q1BSP_GetPVS(model_t *model, const vec3_t p)
3060 {
3061         mnode_t *node;
3062         node = model->brush.data_nodes;
3063         while (node->plane)
3064                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
3065         if (((mleaf_t *)node)->clusterindex >= 0)
3066                 return model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
3067         else
3068                 return NULL;
3069 }
3070
3071 static void Mod_Q1BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, unsigned char *pvsbuffer, int pvsbytes, mnode_t *node)
3072 {
3073         while (node->plane)
3074         {
3075                 float d = PlaneDiff(org, node->plane);
3076                 if (d > radius)
3077                         node = node->children[0];
3078                 else if (d < -radius)
3079                         node = node->children[1];
3080                 else
3081                 {
3082                         // go down both sides
3083                         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
3084                         node = node->children[1];
3085                 }
3086         }
3087         // if this leaf is in a cluster, accumulate the pvs bits
3088         if (((mleaf_t *)node)->clusterindex >= 0)
3089         {
3090                 int i;
3091                 unsigned char *pvs = model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
3092                 for (i = 0;i < pvsbytes;i++)
3093                         pvsbuffer[i] |= pvs[i];
3094         }
3095 }
3096
3097 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
3098 //of the given point.
3099 static int Mod_Q1BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, unsigned char *pvsbuffer, int pvsbufferlength)
3100 {
3101         int bytes = model->brush.num_pvsclusterbytes;
3102         bytes = min(bytes, pvsbufferlength);
3103         if (r_novis.integer || !model->brush.num_pvsclusters || !Mod_Q1BSP_GetPVS(model, org))
3104         {
3105                 memset(pvsbuffer, 0xFF, bytes);
3106                 return bytes;
3107         }
3108         memset(pvsbuffer, 0, bytes);
3109         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brush.data_nodes);
3110         return bytes;
3111 }
3112
3113 static void Mod_Q1BSP_RoundUpToHullSize(model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
3114 {
3115         vec3_t size;
3116         const hull_t *hull;
3117
3118         VectorSubtract(inmaxs, inmins, size);
3119         if (cmodel->brush.ismcbsp)
3120         {
3121                 if (size[0] < 3)
3122                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3123                 else if (size[2] < 48) // pick the nearest of 40 or 56
3124                         hull = &cmodel->brushq1.hulls[2]; // 16x16x40
3125                 else
3126                         hull = &cmodel->brushq1.hulls[1]; // 16x16x56
3127         }
3128         else if (cmodel->brush.ishlbsp)
3129         {
3130                 if (size[0] < 3)
3131                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3132                 else if (size[0] <= 32)
3133                 {
3134                         if (size[2] < 54) // pick the nearest of 36 or 72
3135                                 hull = &cmodel->brushq1.hulls[3]; // 32x32x36
3136                         else
3137                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
3138                 }
3139                 else
3140                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
3141         }
3142         else
3143         {
3144                 if (size[0] < 3)
3145                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3146                 else if (size[0] <= 32)
3147                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
3148                 else
3149                         hull = &cmodel->brushq1.hulls[2]; // 64x64x88
3150         }
3151         VectorCopy(inmins, outmins);
3152         VectorAdd(inmins, hull->clip_size, outmaxs);
3153 }
3154
3155 void Mod_Q1BSP_Load(model_t *mod, void *buffer, void *bufferend)
3156 {
3157         int i, j, k;
3158         dheader_t *header;
3159         dmodel_t *bm;
3160         mempool_t *mainmempool;
3161         float dist, modelyawradius, modelradius, *vec;
3162         msurface_t *surface;
3163         int numshadowmeshtriangles;
3164         dheader_t _header;
3165         hullinfo_t hullinfo;
3166
3167         mod->type = mod_brushq1;
3168
3169         if (!memcmp (buffer, "MCBSPpad", 8))
3170         {
3171                 unsigned char   *index;
3172
3173                 mod->brush.ismcbsp = true;
3174                 mod->brush.ishlbsp = false;
3175
3176                 mod_base = (unsigned char*)buffer;
3177
3178                 index = mod_base;
3179                 index += 8;
3180                 i = SB_ReadInt (&index);
3181                 if (i != MCBSPVERSION)
3182                         Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i)", mod->name, i, MCBSPVERSION);
3183
3184         // read hull info
3185                 hullinfo.numhulls = LittleLong(*(int*)index); index += 4;
3186                 hullinfo.filehulls = hullinfo.numhulls;
3187                 VectorClear (hullinfo.hullsizes[0][0]);
3188                 VectorClear (hullinfo.hullsizes[0][1]);
3189                 for (i = 1; i < hullinfo.numhulls; i++)
3190                 {
3191                         hullinfo.hullsizes[i][0][0] = SB_ReadFloat (&index);
3192                         hullinfo.hullsizes[i][0][1] = SB_ReadFloat (&index);
3193                         hullinfo.hullsizes[i][0][2] = SB_ReadFloat (&index);
3194                         hullinfo.hullsizes[i][1][0] = SB_ReadFloat (&index);
3195                         hullinfo.hullsizes[i][1][1] = SB_ReadFloat (&index);
3196                         hullinfo.hullsizes[i][1][2] = SB_ReadFloat (&index);
3197                 }
3198
3199         // read lumps
3200                 _header.version = 0;
3201                 for (i = 0; i < HEADER_LUMPS; i++)
3202                 {
3203                         _header.lumps[i].fileofs = SB_ReadInt (&index);
3204                         _header.lumps[i].filelen = SB_ReadInt (&index);
3205                 }
3206
3207                 header = &_header;
3208         }
3209         else
3210         {
3211                 header = (dheader_t *)buffer;
3212
3213                 i = LittleLong(header->version);
3214                 if (i != BSPVERSION && i != 30)
3215                         Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i(Quake) or 30(HalfLife)", mod->name, i, BSPVERSION);
3216                 mod->brush.ishlbsp = i == 30;
3217                 mod->brush.ismcbsp = false;
3218
3219         // fill in hull info
3220                 VectorClear (hullinfo.hullsizes[0][0]);
3221                 VectorClear (hullinfo.hullsizes[0][1]);
3222                 if (mod->brush.ishlbsp)
3223                 {
3224                         hullinfo.numhulls = 4;
3225                         hullinfo.filehulls = 4;
3226                         VectorSet (hullinfo.hullsizes[1][0], -16, -16, -36);
3227                         VectorSet (hullinfo.hullsizes[1][1], 16, 16, 36);
3228                         VectorSet (hullinfo.hullsizes[2][0], -32, -32, -32);
3229                         VectorSet (hullinfo.hullsizes[2][1], 32, 32, 32);
3230                         VectorSet (hullinfo.hullsizes[3][0], -16, -16, -18);
3231                         VectorSet (hullinfo.hullsizes[3][1], 16, 16, 18);
3232                 }
3233                 else
3234                 {
3235                         hullinfo.numhulls = 3;
3236                         hullinfo.filehulls = 4;
3237                         VectorSet (hullinfo.hullsizes[1][0], -16, -16, -24);
3238                         VectorSet (hullinfo.hullsizes[1][1], 16, 16, 32);
3239                         VectorSet (hullinfo.hullsizes[2][0], -32, -32, -24);
3240                         VectorSet (hullinfo.hullsizes[2][1], 32, 32, 64);
3241                 }
3242
3243         // read lumps
3244                 mod_base = (unsigned char*)buffer;
3245                 for (i = 0; i < HEADER_LUMPS; i++)
3246                 {
3247                         header->lumps[i].fileofs = LittleLong(header->lumps[i].fileofs);
3248                         header->lumps[i].filelen = LittleLong(header->lumps[i].filelen);
3249                 }
3250         }
3251
3252         mod->soundfromcenter = true;
3253         mod->TraceBox = Mod_Q1BSP_TraceBox;
3254         mod->brush.SuperContentsFromNativeContents = Mod_Q1BSP_SuperContentsFromNativeContents;
3255         mod->brush.NativeContentsFromSuperContents = Mod_Q1BSP_NativeContentsFromSuperContents;
3256         mod->brush.GetPVS = Mod_Q1BSP_GetPVS;
3257         mod->brush.FatPVS = Mod_Q1BSP_FatPVS;
3258         mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
3259         mod->brush.BoxTouchingLeafPVS = Mod_Q1BSP_BoxTouchingLeafPVS;
3260         mod->brush.BoxTouchingVisibleLeafs = Mod_Q1BSP_BoxTouchingVisibleLeafs;
3261         mod->brush.FindBoxClusters = Mod_Q1BSP_FindBoxClusters;
3262         mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
3263         mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
3264         mod->brush.AmbientSoundLevelsForPoint = Mod_Q1BSP_AmbientSoundLevelsForPoint;
3265         mod->brush.RoundUpToHullSize = Mod_Q1BSP_RoundUpToHullSize;
3266         mod->brush.PointInLeaf = Mod_Q1BSP_PointInLeaf;
3267
3268         if (loadmodel->isworldmodel)
3269         {
3270                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
3271                 Cvar_SetValue("mcbsp", mod->brush.ismcbsp);
3272         }
3273
3274 // load into heap
3275
3276         // store which lightmap format to use
3277         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3278
3279         mod->brush.qw_md4sum = 0;
3280         mod->brush.qw_md4sum2 = 0;
3281         for (i = 0;i < HEADER_LUMPS;i++)
3282         {
3283                 if (i == LUMP_ENTITIES)
3284                         continue;
3285                 mod->brush.qw_md4sum ^= LittleLong(Com_BlockChecksum(mod_base + header->lumps[i].fileofs, header->lumps[i].filelen));
3286                 if (i == LUMP_VISIBILITY || i == LUMP_LEAFS || i == LUMP_NODES)
3287                         continue;
3288                 mod->brush.qw_md4sum2 ^= LittleLong(Com_BlockChecksum(mod_base + header->lumps[i].fileofs, header->lumps[i].filelen));
3289         }
3290
3291         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
3292         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
3293         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
3294         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
3295         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
3296         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
3297         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
3298         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
3299         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
3300         Mod_Q1BSP_LoadLeaffaces(&header->lumps[LUMP_MARKSURFACES]);
3301         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
3302         // load submodels before leafs because they contain the number of vis leafs
3303         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS], &hullinfo);
3304         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
3305         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
3306         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES], &hullinfo);
3307
3308         // check if the map supports transparent water rendering
3309         loadmodel->brush.supportwateralpha = Mod_Q1BSP_CheckWaterAlphaSupport();
3310
3311         if (!mod->brushq1.lightdata)
3312                 mod->brush.LightPoint = NULL;
3313
3314         if (mod->brushq1.data_compressedpvs)
3315                 Mem_Free(mod->brushq1.data_compressedpvs);
3316         mod->brushq1.data_compressedpvs = NULL;
3317         mod->brushq1.num_compressedpvs = 0;
3318
3319         Mod_Q1BSP_MakeHull0();
3320         Mod_Q1BSP_MakePortals();
3321
3322         mod->numframes = 2;             // regular and alternate animation
3323         mod->numskins = 1;
3324
3325         mainmempool = mod->mempool;
3326
3327         // make a single combined shadow mesh to allow optimized shadow volume creation
3328         numshadowmeshtriangles = 0;
3329         for (j = 0, surface = loadmodel->data_surfaces;j < loadmodel->num_surfaces;j++, surface++)
3330         {
3331                 surface->num_firstshadowmeshtriangle = numshadowmeshtriangles;
3332                 numshadowmeshtriangles += surface->num_triangles;
3333         }
3334         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Begin(loadmodel->mempool, numshadowmeshtriangles * 3, numshadowmeshtriangles, NULL, NULL, NULL, false, false, true);
3335         for (j = 0, surface = loadmodel->data_surfaces;j < loadmodel->num_surfaces;j++, surface++)
3336                 Mod_ShadowMesh_AddMesh(loadmodel->mempool, loadmodel->brush.shadowmesh, NULL, NULL, NULL, loadmodel->surfmesh.data_vertex3f, NULL, NULL, NULL, NULL, surface->num_triangles, (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle));
3337         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Finish(loadmodel->mempool, loadmodel->brush.shadowmesh, false, true);
3338         Mod_BuildTriangleNeighbors(loadmodel->brush.shadowmesh->neighbor3i, loadmodel->brush.shadowmesh->element3i, loadmodel->brush.shadowmesh->numtriangles);
3339
3340         if (loadmodel->brush.numsubmodels)
3341                 loadmodel->brush.submodels = (model_t **)Mem_Alloc(loadmodel->mempool, loadmodel->brush.numsubmodels * sizeof(model_t *));
3342
3343         if (loadmodel->isworldmodel)
3344         {
3345                 // clear out any stale submodels or worldmodels lying around
3346                 // if we did this clear before now, an error might abort loading and
3347                 // leave things in a bad state
3348                 Mod_RemoveStaleWorldModels(loadmodel);
3349         }
3350
3351         // LordHavoc: to clear the fog around the original quake submodel code, I
3352         // will explain:
3353         // first of all, some background info on the submodels:
3354         // model 0 is the map model (the world, named maps/e1m1.bsp for example)
3355         // model 1 and higher are submodels (doors and the like, named *1, *2, etc)
3356         //&nb