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