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