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