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