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