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