]> icculus.org git repositories - divverent/darkplaces.git/blob - model_brush.c
Tomaz optimized the cl_avidemo mode by making it keep around the image processing...
[divverent/darkplaces.git] / model_brush.c
1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19 */
20
21 #include "quakedef.h"
22 #include "image.h"
23 #include "r_shadow.h"
24 #include "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) || !surf->samples)
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
797                                 if (ds >= 0 && ds < surf->extents[0] && dt >= 0 && dt < surf->extents[1])
798                                 {
799                                         qbyte *lightmap;
800                                         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;
801                                         lmwidth = ((surf->extents[0]>>4)+1);
802                                         lmheight = ((surf->extents[1]>>4)+1);
803                                         line3 = lmwidth * 3; // LordHavoc: *3 for colored lighting
804                                         size3 = lmwidth * lmheight * 3; // LordHavoc: *3 for colored lighting
805
806                                         lightmap = surf->samples + ((dt>>4) * lmwidth + (ds>>4))*3; // LordHavoc: *3 for colored lighting
807
808                                         for (maps = 0;maps < MAXLIGHTMAPS && surf->styles[maps] != 255;maps++)
809                                         {
810                                                 scale = d_lightstylevalue[surf->styles[maps]];
811                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
812                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
813                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
814                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
815                                                 lightmap += size3;
816                                         }
817
818 /*
819 LordHavoc: here's the readable version of the interpolation
820 code, not quite as easy for the compiler to optimize...
821
822 dsfrac is the X position in the lightmap pixel, * 16
823 dtfrac is the Y position in the lightmap pixel, * 16
824 r00 is top left corner, r01 is top right corner
825 r10 is bottom left corner, r11 is bottom right corner
826 g and b are the same layout.
827 r0 and r1 are the top and bottom intermediate results
828
829 first we interpolate the top two points, to get the top
830 edge sample
831
832         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
833         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
834         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
835
836 then we interpolate the bottom two points, to get the
837 bottom edge sample
838
839         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
840         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
841         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
842
843 then we interpolate the top and bottom samples to get the
844 middle sample (the one which was requested)
845
846         r = (((r1-r0) * dtfrac) >> 4) + r0;
847         g = (((g1-g0) * dtfrac) >> 4) + g0;
848         b = (((b1-b0) * dtfrac) >> 4) + b0;
849 */
850
851                                         ambientcolor[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
852                                         ambientcolor[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
853                                         ambientcolor[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
854                                         return true; // success
855                                 }
856                         }
857                 }
858
859                 // go down back side
860                 node = node->children[side ^ 1];
861                 startz = mid;
862                 distz = endz - startz;
863                 goto loc0;
864         }
865 }
866
867 void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
868 {
869         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);
870 }
871
872 static void Mod_Q1BSP_DecompressVis(const qbyte *in, const qbyte *inend, qbyte *out, qbyte *outend)
873 {
874         int c;
875         qbyte *outstart = out;
876         while (out < outend)
877         {
878                 if (in == inend)
879                 {
880                         Con_DPrintf("Mod_Q1BSP_DecompressVis: input underrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
881                         return;
882                 }
883                 c = *in++;
884                 if (c)
885                         *out++ = c;
886                 else
887                 {
888                         if (in == inend)
889                         {
890                                 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);
891                                 return;
892                         }
893                         for (c = *in++;c > 0;c--)
894                         {
895                                 if (out == outend)
896                                 {
897                                         Con_DPrintf("Mod_Q1BSP_DecompressVis: output overrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
898                                         return;
899                                 }
900                                 *out++ = 0;
901                         }
902                 }
903         }
904 }
905
906 static void Mod_Q1BSP_LoadTextures(lump_t *l)
907 {
908         int i, j, k, num, max, altmax, mtwidth, mtheight, *dofs, incomplete;
909         miptex_t *dmiptex;
910         texture_t *tx, *tx2, *anims[10], *altanims[10];
911         dmiptexlump_t *m;
912         qbyte *data, *mtdata;
913         char name[256];
914
915         loadmodel->brushq1.textures = NULL;
916
917         // add two slots for notexture walls and notexture liquids
918         if (l->filelen)
919         {
920                 m = (dmiptexlump_t *)(mod_base + l->fileofs);
921                 m->nummiptex = LittleLong (m->nummiptex);
922                 loadmodel->brushq1.numtextures = m->nummiptex + 2;
923         }
924         else
925         {
926                 m = NULL;
927                 loadmodel->brushq1.numtextures = 2;
928         }
929
930         loadmodel->brushq1.textures = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numtextures * sizeof(texture_t));
931
932         // fill out all slots with notexture
933         for (i = 0, tx = loadmodel->brushq1.textures;i < loadmodel->brushq1.numtextures;i++, tx++)
934         {
935                 tx->number = i;
936                 strcpy(tx->name, "NO TEXTURE FOUND");
937                 tx->width = 16;
938                 tx->height = 16;
939                 tx->skin.base = r_notexture;
940                 if (i == loadmodel->brushq1.numtextures - 1)
941                         tx->flags = SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
942                 else
943                         tx->flags = SURF_LIGHTMAP | SURF_SOLIDCLIP;
944                 tx->currentframe = tx;
945         }
946
947         if (!m)
948                 return;
949
950         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
951         dofs = m->dataofs;
952         // LordHavoc: mostly rewritten map texture loader
953         for (i = 0;i < m->nummiptex;i++)
954         {
955                 dofs[i] = LittleLong(dofs[i]);
956                 if (dofs[i] == -1 || r_nosurftextures.integer)
957                         continue;
958                 dmiptex = (miptex_t *)((qbyte *)m + dofs[i]);
959
960                 // make sure name is no more than 15 characters
961                 for (j = 0;dmiptex->name[j] && j < 15;j++)
962                         name[j] = dmiptex->name[j];
963                 name[j] = 0;
964
965                 mtwidth = LittleLong(dmiptex->width);
966                 mtheight = LittleLong(dmiptex->height);
967                 mtdata = NULL;
968                 j = LittleLong(dmiptex->offsets[0]);
969                 if (j)
970                 {
971                         // texture included
972                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
973                         {
974                                 Con_Printf("Texture \"%s\" in \"%s\"is corrupt or incomplete\n", dmiptex->name, loadmodel->name);
975                                 continue;
976                         }
977                         mtdata = (qbyte *)dmiptex + j;
978                 }
979
980                 if ((mtwidth & 15) || (mtheight & 15))
981                         Con_Printf("warning: texture \"%s\" in \"%s\" is not 16 aligned\n", dmiptex->name, loadmodel->name);
982
983                 // LordHavoc: force all names to lowercase
984                 for (j = 0;name[j];j++)
985                         if (name[j] >= 'A' && name[j] <= 'Z')
986                                 name[j] += 'a' - 'A';
987
988                 tx = loadmodel->brushq1.textures + i;
989                 strcpy(tx->name, name);
990                 tx->width = mtwidth;
991                 tx->height = mtheight;
992
993                 if (!tx->name[0])
994                 {
995                         sprintf(tx->name, "unnamed%i", i);
996                         Con_Printf("warning: unnamed texture in %s, renaming to %s\n", loadmodel->name, tx->name);
997                 }
998
999                 // LordHavoc: HL sky textures are entirely different than quake
1000                 if (!loadmodel->brush.ishlbsp && !strncmp(tx->name, "sky", 3) && mtwidth == 256 && mtheight == 128)
1001                 {
1002                         if (loadmodel->isworldmodel)
1003                         {
1004                                 data = loadimagepixels(tx->name, false, 0, 0);
1005                                 if (data)
1006                                 {
1007                                         if (image_width == 256 && image_height == 128)
1008                                         {
1009                                                 R_InitSky(data, 4);
1010                                                 Mem_Free(data);
1011                                         }
1012                                         else
1013                                         {
1014                                                 Mem_Free(data);
1015                                                 Con_Printf("Invalid replacement texture for sky \"%s\" in %\"%s\", must be 256x128 pixels\n", tx->name, loadmodel->name);
1016                                                 if (mtdata != NULL)
1017                                                         R_InitSky(mtdata, 1);
1018                                         }
1019                                 }
1020                                 else if (mtdata != NULL)
1021                                         R_InitSky(mtdata, 1);
1022                         }
1023                 }
1024                 else
1025                 {
1026                         if (!Mod_LoadSkinFrame(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, false, true, true))
1027                         {
1028                                 // did not find external texture, load it from the bsp or wad3
1029                                 if (loadmodel->brush.ishlbsp)
1030                                 {
1031                                         // internal texture overrides wad
1032                                         qbyte *pixels, *freepixels, *fogpixels;
1033                                         pixels = freepixels = NULL;
1034                                         if (mtdata)
1035                                                 pixels = W_ConvertWAD3Texture(dmiptex);
1036                                         if (pixels == NULL)
1037                                                 pixels = freepixels = W_GetTexture(tx->name);
1038                                         if (pixels != NULL)
1039                                         {
1040                                                 tx->width = image_width;
1041                                                 tx->height = image_height;
1042                                                 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);
1043                                                 if (Image_CheckAlpha(pixels, image_width * image_height, true))
1044                                                 {
1045                                                         fogpixels = Mem_Alloc(tempmempool, image_width * image_height * 4);
1046                                                         for (j = 0;j < image_width * image_height * 4;j += 4)
1047                                                         {
1048                                                                 fogpixels[j + 0] = 255;
1049                                                                 fogpixels[j + 1] = 255;
1050                                                                 fogpixels[j + 2] = 255;
1051                                                                 fogpixels[j + 3] = pixels[j + 3];
1052                                                         }
1053                                                         tx->skin.fog = R_LoadTexture2D(loadmodel->texturepool, tx->name, image_width, image_height, pixels, TEXTYPE_RGBA, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, NULL);
1054                                                         Mem_Free(fogpixels);
1055                                                 }
1056                                         }
1057                                         if (freepixels)
1058                                                 Mem_Free(freepixels);
1059                                 }
1060                                 else if (mtdata) // texture included
1061                                         Mod_LoadSkinFrame_Internal(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_PRECACHE, false, true, tx->name[0] != '*' && r_fullbrights.integer, mtdata, tx->width, tx->height);
1062                         }
1063                 }
1064                 if (tx->skin.base == NULL)
1065                 {
1066                         // no texture found
1067                         tx->width = 16;
1068                         tx->height = 16;
1069                         tx->skin.base = r_notexture;
1070                 }
1071
1072                 if (tx->name[0] == '*')
1073                 {
1074                         // turb does not block movement
1075                         tx->flags = SURF_DRAWTURB | SURF_LIGHTBOTHSIDES;
1076                         // LordHavoc: some turbulent textures should be fullbright and solid
1077                         if (!strncmp(tx->name,"*lava",5)
1078                          || !strncmp(tx->name,"*teleport",9)
1079                          || !strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
1080                                 tx->flags |= SURF_DRAWFULLBRIGHT | SURF_DRAWNOALPHA;
1081                         else
1082                                 tx->flags |= SURF_WATERALPHA;
1083                 }
1084                 else if (tx->name[0] == 's' && tx->name[1] == 'k' && tx->name[2] == 'y')
1085                         tx->flags = SURF_DRAWSKY | SURF_SOLIDCLIP;
1086                 else
1087                         tx->flags = SURF_LIGHTMAP | SURF_SOLIDCLIP;
1088
1089                 // start out with no animation
1090                 tx->currentframe = tx;
1091         }
1092
1093         // sequence the animations
1094         for (i = 0;i < m->nummiptex;i++)
1095         {
1096                 tx = loadmodel->brushq1.textures + i;
1097                 if (!tx || tx->name[0] != '+' || tx->name[1] == 0 || tx->name[2] == 0)
1098                         continue;
1099                 if (tx->anim_total[0] || tx->anim_total[1])
1100                         continue;       // already sequenced
1101
1102                 // find the number of frames in the animation
1103                 memset(anims, 0, sizeof(anims));
1104                 memset(altanims, 0, sizeof(altanims));
1105
1106                 for (j = i;j < m->nummiptex;j++)
1107                 {
1108                         tx2 = loadmodel->brushq1.textures + j;
1109                         if (!tx2 || tx2->name[0] != '+' || strcmp(tx2->name+2, tx->name+2))
1110                                 continue;
1111
1112                         num = tx2->name[1];
1113                         if (num >= '0' && num <= '9')
1114                                 anims[num - '0'] = tx2;
1115                         else if (num >= 'a' && num <= 'j')
1116                                 altanims[num - 'a'] = tx2;
1117                         else
1118                                 Con_Printf("Bad animating texture %s\n", tx->name);
1119                 }
1120
1121                 max = altmax = 0;
1122                 for (j = 0;j < 10;j++)
1123                 {
1124                         if (anims[j])
1125                                 max = j + 1;
1126                         if (altanims[j])
1127                                 altmax = j + 1;
1128                 }
1129                 //Con_Printf("linking animation %s (%i:%i frames)\n\n", tx->name, max, altmax);
1130
1131                 incomplete = false;
1132                 for (j = 0;j < max;j++)
1133                 {
1134                         if (!anims[j])
1135                         {
1136                                 Con_Printf("Missing frame %i of %s\n", j, tx->name);
1137                                 incomplete = true;
1138                         }
1139                 }
1140                 for (j = 0;j < altmax;j++)
1141                 {
1142                         if (!altanims[j])
1143                         {
1144                                 Con_Printf("Missing altframe %i of %s\n", j, tx->name);
1145                                 incomplete = true;
1146                         }
1147                 }
1148                 if (incomplete)
1149                         continue;
1150
1151                 if (altmax < 1)
1152                 {
1153                         // if there is no alternate animation, duplicate the primary
1154                         // animation into the alternate
1155                         altmax = max;
1156                         for (k = 0;k < 10;k++)
1157                                 altanims[k] = anims[k];
1158                 }
1159
1160                 // link together the primary animation
1161                 for (j = 0;j < max;j++)
1162                 {
1163                         tx2 = anims[j];
1164                         tx2->animated = true;
1165                         tx2->anim_total[0] = max;
1166                         tx2->anim_total[1] = altmax;
1167                         for (k = 0;k < 10;k++)
1168                         {
1169                                 tx2->anim_frames[0][k] = anims[k];
1170                                 tx2->anim_frames[1][k] = altanims[k];
1171                         }
1172                 }
1173
1174                 // if there really is an alternate anim...
1175                 if (anims[0] != altanims[0])
1176                 {
1177                         // link together the alternate animation
1178                         for (j = 0;j < altmax;j++)
1179                         {
1180                                 tx2 = altanims[j];
1181                                 tx2->animated = true;
1182                                 // the primary/alternate are reversed here
1183                                 tx2->anim_total[0] = altmax;
1184                                 tx2->anim_total[1] = max;
1185                                 for (k = 0;k < 10;k++)
1186                                 {
1187                                         tx2->anim_frames[0][k] = altanims[k];
1188                                         tx2->anim_frames[1][k] = anims[k];
1189                                 }
1190                         }
1191                 }
1192         }
1193 }
1194
1195 static void Mod_Q1BSP_LoadLighting(lump_t *l)
1196 {
1197         int i;
1198         qbyte *in, *out, *data, d;
1199         char litfilename[1024];
1200         loadmodel->brushq1.lightdata = NULL;
1201         if (loadmodel->brush.ishlbsp) // LordHavoc: load the colored lighting data straight
1202         {
1203                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen);
1204                 memcpy(loadmodel->brushq1.lightdata, mod_base + l->fileofs, l->filelen);
1205         }
1206         else // LordHavoc: bsp version 29 (normal white lighting)
1207         {
1208                 // LordHavoc: hope is not lost yet, check for a .lit file to load
1209                 strlcpy (litfilename, loadmodel->name, sizeof (litfilename));
1210                 FS_StripExtension (litfilename, litfilename, sizeof (litfilename));
1211                 strlcat (litfilename, ".lit", sizeof (litfilename));
1212                 data = (qbyte*) FS_LoadFile(litfilename, tempmempool, false);
1213                 if (data)
1214                 {
1215                         if (fs_filesize > 8 && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1216                         {
1217                                 i = LittleLong(((int *)data)[1]);
1218                                 if (i == 1)
1219                                 {
1220                                         Con_DPrintf("loaded %s\n", litfilename);
1221                                         loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, fs_filesize - 8);
1222                                         memcpy(loadmodel->brushq1.lightdata, data + 8, fs_filesize - 8);
1223                                         Mem_Free(data);
1224                                         return;
1225                                 }
1226                                 else
1227                                 {
1228                                         Con_Printf("Unknown .lit file version (%d)\n", i);
1229                                         Mem_Free(data);
1230                                 }
1231                         }
1232                         else
1233                         {
1234                                 if (fs_filesize == 8)
1235                                         Con_Print("Empty .lit file, ignoring\n");
1236                                 else
1237                                         Con_Print("Corrupt .lit file (old version?), ignoring\n");
1238                                 Mem_Free(data);
1239                         }
1240                 }
1241                 // LordHavoc: oh well, expand the white lighting data
1242                 if (!l->filelen)
1243                         return;
1244                 loadmodel->brushq1.lightdata = Mem_Alloc(loadmodel->mempool, l->filelen*3);
1245                 in = loadmodel->brushq1.lightdata + l->filelen*2; // place the file at the end, so it will not be overwritten until the very last write
1246                 out = loadmodel->brushq1.lightdata;
1247                 memcpy(in, mod_base + l->fileofs, l->filelen);
1248                 for (i = 0;i < l->filelen;i++)
1249                 {
1250                         d = *in++;
1251                         *out++ = d;
1252                         *out++ = d;
1253                         *out++ = d;
1254                 }
1255         }
1256 }
1257
1258 static void Mod_Q1BSP_LoadLightList(void)
1259 {
1260         int a, n, numlights;
1261         char lightsfilename[1024], *s, *t, *lightsstring;
1262         mlight_t *e;
1263
1264         strlcpy (lightsfilename, loadmodel->name, sizeof (lightsfilename));
1265         FS_StripExtension (lightsfilename, lightsfilename, sizeof(lightsfilename));
1266         strlcat (lightsfilename, ".lights", sizeof (lightsfilename));
1267         s = lightsstring = (char *) FS_LoadFile(lightsfilename, tempmempool, false);
1268         if (s)
1269         {
1270                 numlights = 0;
1271                 while (*s)
1272                 {
1273                         while (*s && *s != '\n')
1274                                 s++;
1275                         if (!*s)
1276                         {
1277                                 Mem_Free(lightsstring);
1278                                 Host_Error("lights file must end with a newline\n");
1279                         }
1280                         s++;
1281                         numlights++;
1282                 }
1283                 loadmodel->brushq1.lights = Mem_Alloc(loadmodel->mempool, numlights * sizeof(mlight_t));
1284                 s = lightsstring;
1285                 n = 0;
1286                 while (*s && n < numlights)
1287                 {
1288                         t = s;
1289                         while (*s && *s != '\n')
1290                                 s++;
1291                         if (!*s)
1292                         {
1293                                 Mem_Free(lightsstring);
1294                                 Host_Error("misparsed lights file!\n");
1295                         }
1296                         e = loadmodel->brushq1.lights + n;
1297                         *s = 0;
1298                         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);
1299                         *s = '\n';
1300                         if (a != 14)
1301                         {
1302                                 Mem_Free(lightsstring);
1303                                 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);
1304                         }
1305                         s++;
1306                         n++;
1307                 }
1308                 if (*s)
1309                 {
1310                         Mem_Free(lightsstring);
1311                         Host_Error("misparsed lights file!\n");
1312                 }
1313                 loadmodel->brushq1.numlights = numlights;
1314                 Mem_Free(lightsstring);
1315         }
1316 }
1317
1318 static void Mod_Q1BSP_LoadVisibility(lump_t *l)
1319 {
1320         loadmodel->brushq1.num_compressedpvs = 0;
1321         loadmodel->brushq1.data_compressedpvs = NULL;
1322         if (!l->filelen)
1323                 return;
1324         loadmodel->brushq1.num_compressedpvs = l->filelen;
1325         loadmodel->brushq1.data_compressedpvs = Mem_Alloc(loadmodel->mempool, l->filelen);
1326         memcpy(loadmodel->brushq1.data_compressedpvs, mod_base + l->fileofs, l->filelen);
1327 }
1328
1329 // used only for HalfLife maps
1330 static void Mod_Q1BSP_ParseWadsFromEntityLump(const char *data)
1331 {
1332         char key[128], value[4096];
1333         char wadname[128];
1334         int i, j, k;
1335         if (!data)
1336                 return;
1337         if (!COM_ParseToken(&data, false))
1338                 return; // error
1339         if (com_token[0] != '{')
1340                 return; // error
1341         while (1)
1342         {
1343                 if (!COM_ParseToken(&data, false))
1344                         return; // error
1345                 if (com_token[0] == '}')
1346                         break; // end of worldspawn
1347                 if (com_token[0] == '_')
1348                         strcpy(key, com_token + 1);
1349                 else
1350                         strcpy(key, com_token);
1351                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
1352                         key[strlen(key)-1] = 0;
1353                 if (!COM_ParseToken(&data, false))
1354                         return; // error
1355                 strcpy(value, com_token);
1356                 if (!strcmp("wad", key)) // for HalfLife maps
1357                 {
1358                         if (loadmodel->brush.ishlbsp)
1359                         {
1360                                 j = 0;
1361                                 for (i = 0;i < 4096;i++)
1362                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
1363                                                 break;
1364                                 if (value[i])
1365                                 {
1366                                         for (;i < 4096;i++)
1367                                         {
1368                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
1369                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
1370                                                         j = i+1;
1371                                                 else if (value[i] == ';' || value[i] == 0)
1372                                                 {
1373                                                         k = value[i];
1374                                                         value[i] = 0;
1375                                                         strcpy(wadname, "textures/");
1376                                                         strcat(wadname, &value[j]);
1377                                                         W_LoadTextureWadFile(wadname, false);
1378                                                         j = i+1;
1379                                                         if (!k)
1380                                                                 break;
1381                                                 }
1382                                         }
1383                                 }
1384                         }
1385                 }
1386         }
1387 }
1388
1389 static void Mod_Q1BSP_LoadEntities(lump_t *l)
1390 {
1391         loadmodel->brush.entities = NULL;
1392         if (!l->filelen)
1393                 return;
1394         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
1395         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
1396         if (loadmodel->brush.ishlbsp)
1397                 Mod_Q1BSP_ParseWadsFromEntityLump(loadmodel->brush.entities);
1398 }
1399
1400
1401 static void Mod_Q1BSP_LoadVertexes(lump_t *l)
1402 {
1403         dvertex_t       *in;
1404         mvertex_t       *out;
1405         int                     i, count;
1406
1407         in = (void *)(mod_base + l->fileofs);
1408         if (l->filelen % sizeof(*in))
1409                 Host_Error("Mod_Q1BSP_LoadVertexes: funny lump size in %s",loadmodel->name);
1410         count = l->filelen / sizeof(*in);
1411         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1412
1413         loadmodel->brushq1.vertexes = out;
1414         loadmodel->brushq1.numvertexes = count;
1415
1416         for ( i=0 ; i<count ; i++, in++, out++)
1417         {
1418                 out->position[0] = LittleFloat(in->point[0]);
1419                 out->position[1] = LittleFloat(in->point[1]);
1420                 out->position[2] = LittleFloat(in->point[2]);
1421         }
1422 }
1423
1424 static void Mod_Q1BSP_LoadSubmodels(lump_t *l)
1425 {
1426         dmodel_t        *in;
1427         dmodel_t        *out;
1428         int                     i, j, count;
1429
1430         in = (void *)(mod_base + l->fileofs);
1431         if (l->filelen % sizeof(*in))
1432                 Host_Error("Mod_Q1BSP_LoadSubmodels: funny lump size in %s",loadmodel->name);
1433         count = l->filelen / sizeof(*in);
1434         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1435
1436         loadmodel->brushq1.submodels = out;
1437         loadmodel->brush.numsubmodels = count;
1438
1439         for ( i=0 ; i<count ; i++, in++, out++)
1440         {
1441                 for (j=0 ; j<3 ; j++)
1442                 {
1443                         // spread the mins / maxs by a pixel
1444                         out->mins[j] = LittleFloat(in->mins[j]) - 1;
1445                         out->maxs[j] = LittleFloat(in->maxs[j]) + 1;
1446                         out->origin[j] = LittleFloat(in->origin[j]);
1447                 }
1448                 for (j=0 ; j<MAX_MAP_HULLS ; j++)
1449                         out->headnode[j] = LittleLong(in->headnode[j]);
1450                 out->visleafs = LittleLong(in->visleafs);
1451                 out->firstface = LittleLong(in->firstface);
1452                 out->numfaces = LittleLong(in->numfaces);
1453         }
1454 }
1455
1456 static void Mod_Q1BSP_LoadEdges(lump_t *l)
1457 {
1458         dedge_t *in;
1459         medge_t *out;
1460         int     i, count;
1461
1462         in = (void *)(mod_base + l->fileofs);
1463         if (l->filelen % sizeof(*in))
1464                 Host_Error("Mod_Q1BSP_LoadEdges: funny lump size in %s",loadmodel->name);
1465         count = l->filelen / sizeof(*in);
1466         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1467
1468         loadmodel->brushq1.edges = out;
1469         loadmodel->brushq1.numedges = count;
1470
1471         for ( i=0 ; i<count ; i++, in++, out++)
1472         {
1473                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
1474                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
1475         }
1476 }
1477
1478 static void Mod_Q1BSP_LoadTexinfo(lump_t *l)
1479 {
1480         texinfo_t *in;
1481         mtexinfo_t *out;
1482         int i, j, k, count, miptex;
1483
1484         in = (void *)(mod_base + l->fileofs);
1485         if (l->filelen % sizeof(*in))
1486                 Host_Error("Mod_Q1BSP_LoadTexinfo: funny lump size in %s",loadmodel->name);
1487         count = l->filelen / sizeof(*in);
1488         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1489
1490         loadmodel->brushq1.texinfo = out;
1491         loadmodel->brushq1.numtexinfo = count;
1492
1493         for (i = 0;i < count;i++, in++, out++)
1494         {
1495                 for (k = 0;k < 2;k++)
1496                         for (j = 0;j < 4;j++)
1497                                 out->vecs[k][j] = LittleFloat(in->vecs[k][j]);
1498
1499                 miptex = LittleLong(in->miptex);
1500                 out->flags = LittleLong(in->flags);
1501
1502                 out->texture = NULL;
1503                 if (loadmodel->brushq1.textures)
1504                 {
1505                         if ((unsigned int) miptex >= (unsigned int) loadmodel->brushq1.numtextures)
1506                                 Con_Printf("error in model \"%s\": invalid miptex index %i(of %i)\n", loadmodel->name, miptex, loadmodel->brushq1.numtextures);
1507                         else
1508                                 out->texture = loadmodel->brushq1.textures + miptex;
1509                 }
1510                 if (out->flags & TEX_SPECIAL)
1511                 {
1512                         // if texture chosen is NULL or the shader needs a lightmap,
1513                         // force to notexture water shader
1514                         if (out->texture == NULL || out->texture->flags & SURF_LIGHTMAP)
1515                                 out->texture = loadmodel->brushq1.textures + (loadmodel->brushq1.numtextures - 1);
1516                 }
1517                 else
1518                 {
1519                         // if texture chosen is NULL, force to notexture
1520                         if (out->texture == NULL)
1521                                 out->texture = loadmodel->brushq1.textures + (loadmodel->brushq1.numtextures - 2);
1522                 }
1523         }
1524 }
1525
1526 #if 0
1527 void BoundPoly(int numverts, float *verts, vec3_t mins, vec3_t maxs)
1528 {
1529         int             i, j;
1530         float   *v;
1531
1532         mins[0] = mins[1] = mins[2] = 9999;
1533         maxs[0] = maxs[1] = maxs[2] = -9999;
1534         v = verts;
1535         for (i = 0;i < numverts;i++)
1536         {
1537                 for (j = 0;j < 3;j++, v++)
1538                 {
1539                         if (*v < mins[j])
1540                                 mins[j] = *v;
1541                         if (*v > maxs[j])
1542                                 maxs[j] = *v;
1543                 }
1544         }
1545 }
1546
1547 #define MAX_SUBDIVPOLYTRIANGLES 4096
1548 #define MAX_SUBDIVPOLYVERTS(MAX_SUBDIVPOLYTRIANGLES * 3)
1549
1550 static int subdivpolyverts, subdivpolytriangles;
1551 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
1552 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
1553
1554 static int subdivpolylookupvert(vec3_t v)
1555 {
1556         int i;
1557         for (i = 0;i < subdivpolyverts;i++)
1558                 if (subdivpolyvert[i][0] == v[0]
1559                  && subdivpolyvert[i][1] == v[1]
1560                  && subdivpolyvert[i][2] == v[2])
1561                         return i;
1562         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
1563                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
1564         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
1565         return subdivpolyverts++;
1566 }
1567
1568 static void SubdividePolygon(int numverts, float *verts)
1569 {
1570         int             i, i1, i2, i3, f, b, c, p;
1571         vec3_t  mins, maxs, front[256], back[256];
1572         float   m, *pv, *cv, dist[256], frac;
1573
1574         if (numverts > 250)
1575                 Host_Error("SubdividePolygon: ran out of verts in buffer");
1576
1577         BoundPoly(numverts, verts, mins, maxs);
1578
1579         for (i = 0;i < 3;i++)
1580         {
1581                 m = (mins[i] + maxs[i]) * 0.5;
1582                 m = r_subdivide_size.value * floor(m/r_subdivide_size.value + 0.5);
1583                 if (maxs[i] - m < 8)
1584                         continue;
1585                 if (m - mins[i] < 8)
1586                         continue;
1587
1588                 // cut it
1589                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
1590                         dist[c] = cv[i] - m;
1591
1592                 f = b = 0;
1593                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
1594                 {
1595                         if (dist[p] >= 0)
1596                         {
1597                                 VectorCopy(pv, front[f]);
1598                                 f++;
1599                         }
1600                         if (dist[p] <= 0)
1601                         {
1602                                 VectorCopy(pv, back[b]);
1603                                 b++;
1604                         }
1605                         if (dist[p] == 0 || dist[c] == 0)
1606                                 continue;
1607                         if ((dist[p] > 0) != (dist[c] > 0) )
1608                         {
1609                                 // clip point
1610                                 frac = dist[p] / (dist[p] - dist[c]);
1611                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
1612                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
1613                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
1614                                 f++;
1615                                 b++;
1616                         }
1617                 }
1618
1619                 SubdividePolygon(f, front[0]);
1620                 SubdividePolygon(b, back[0]);
1621                 return;
1622         }
1623
1624         i1 = subdivpolylookupvert(verts);
1625         i2 = subdivpolylookupvert(verts + 3);
1626         for (i = 2;i < numverts;i++)
1627         {
1628                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
1629                 {
1630                         Con_Print("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
1631                         return;
1632                 }
1633
1634                 i3 = subdivpolylookupvert(verts + i * 3);
1635                 subdivpolyindex[subdivpolytriangles][0] = i1;
1636                 subdivpolyindex[subdivpolytriangles][1] = i2;
1637                 subdivpolyindex[subdivpolytriangles][2] = i3;
1638                 i2 = i3;
1639                 subdivpolytriangles++;
1640         }
1641 }
1642
1643 //Breaks a polygon up along axial 64 unit
1644 //boundaries so that turbulent and sky warps
1645 //can be done reasonably.
1646 static void Mod_Q1BSP_GenerateWarpMesh(msurface_t *surf)
1647 {
1648         int i, j;
1649         surfvertex_t *v;
1650         surfmesh_t *mesh;
1651
1652         subdivpolytriangles = 0;
1653         subdivpolyverts = 0;
1654         SubdividePolygon(surf->poly_numverts, surf->poly_verts);
1655         if (subdivpolytriangles < 1)
1656                 Host_Error("Mod_Q1BSP_GenerateWarpMesh: no triangles?\n");
1657
1658         surf->mesh = mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + subdivpolytriangles * sizeof(int[3]) + subdivpolyverts * sizeof(surfvertex_t));
1659         mesh->num_vertices = subdivpolyverts;
1660         mesh->num_triangles = subdivpolytriangles;
1661         mesh->vertex = (surfvertex_t *)(mesh + 1);
1662         mesh->index = (int *)(mesh->vertex + mesh->num_vertices);
1663         memset(mesh->vertex, 0, mesh->num_vertices * sizeof(surfvertex_t));
1664
1665         for (i = 0;i < mesh->num_triangles;i++)
1666                 for (j = 0;j < 3;j++)
1667                         mesh->index[i*3+j] = subdivpolyindex[i][j];
1668
1669         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
1670         {
1671                 VectorCopy(subdivpolyvert[i], v->v);
1672                 v->st[0] = DotProduct(v->v, surf->texinfo->vecs[0]);
1673                 v->st[1] = DotProduct(v->v, surf->texinfo->vecs[1]);
1674         }
1675 }
1676 #endif
1677
1678 static surfmesh_t *Mod_Q1BSP_AllocSurfMesh(int numverts, int numtriangles)
1679 {
1680         surfmesh_t *mesh;
1681         mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + numtriangles * sizeof(int[6]) + numverts * (3 + 2 + 2 + 2 + 3 + 3 + 3 + 1) * sizeof(float));
1682         mesh->num_vertices = numverts;
1683         mesh->num_triangles = numtriangles;
1684         mesh->data_vertex3f = (float *)(mesh + 1);
1685         mesh->data_texcoordtexture2f = mesh->data_vertex3f + mesh->num_vertices * 3;
1686         mesh->data_texcoordlightmap2f = mesh->data_texcoordtexture2f + mesh->num_vertices * 2;
1687         mesh->data_texcoorddetail2f = mesh->data_texcoordlightmap2f + mesh->num_vertices * 2;
1688         mesh->data_svector3f = (float *)(mesh->data_texcoorddetail2f + mesh->num_vertices * 2);
1689         mesh->data_tvector3f = mesh->data_svector3f + mesh->num_vertices * 3;
1690         mesh->data_normal3f = mesh->data_tvector3f + mesh->num_vertices * 3;
1691         mesh->data_lightmapoffsets = (int *)(mesh->data_normal3f + mesh->num_vertices * 3);
1692         mesh->data_element3i = mesh->data_lightmapoffsets + mesh->num_vertices;
1693         mesh->data_neighbor3i = mesh->data_element3i + mesh->num_triangles * 3;
1694         return mesh;
1695 }
1696
1697 static void Mod_Q1BSP_GenerateSurfacePolygon(msurface_t *surf, int firstedge, int numedges)
1698 {
1699         int i, lindex, j;
1700         float *vec, *vert, mins[3], maxs[3], val, *v;
1701         mtexinfo_t *tex;
1702
1703         // convert edges back to a normal polygon
1704         surf->poly_numverts = numedges;
1705         vert = surf->poly_verts = Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * numedges);
1706         for (i = 0;i < numedges;i++)
1707         {
1708                 lindex = loadmodel->brushq1.surfedges[firstedge + i];
1709                 if (lindex > 0)
1710                         vec = loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[lindex].v[0]].position;
1711                 else
1712                         vec = loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[-lindex].v[1]].position;
1713                 VectorCopy(vec, vert);
1714                 vert += 3;
1715         }
1716
1717         // calculate polygon bounding box and center
1718         vert = surf->poly_verts;
1719         VectorCopy(vert, mins);
1720         VectorCopy(vert, maxs);
1721         vert += 3;
1722         for (i = 1;i < surf->poly_numverts;i++, vert += 3)
1723         {
1724                 if (mins[0] > vert[0]) mins[0] = vert[0];if (maxs[0] < vert[0]) maxs[0] = vert[0];
1725                 if (mins[1] > vert[1]) mins[1] = vert[1];if (maxs[1] < vert[1]) maxs[1] = vert[1];
1726                 if (mins[2] > vert[2]) mins[2] = vert[2];if (maxs[2] < vert[2]) maxs[2] = vert[2];
1727         }
1728         VectorCopy(mins, surf->poly_mins);
1729         VectorCopy(maxs, surf->poly_maxs);
1730         surf->poly_center[0] = (mins[0] + maxs[0]) * 0.5f;
1731         surf->poly_center[1] = (mins[1] + maxs[1]) * 0.5f;
1732         surf->poly_center[2] = (mins[2] + maxs[2]) * 0.5f;
1733
1734         // generate surface extents information
1735         tex = surf->texinfo;
1736         mins[0] = maxs[0] = DotProduct(surf->poly_verts, tex->vecs[0]) + tex->vecs[0][3];
1737         mins[1] = maxs[1] = DotProduct(surf->poly_verts, tex->vecs[1]) + tex->vecs[1][3];
1738         for (i = 1, v = surf->poly_verts + 3;i < surf->poly_numverts;i++, v += 3)
1739         {
1740                 for (j = 0;j < 2;j++)
1741                 {
1742                         val = DotProduct(v, tex->vecs[j]) + tex->vecs[j][3];
1743                         if (mins[j] > val)
1744                                 mins[j] = val;
1745                         if (maxs[j] < val)
1746                                 maxs[j] = val;
1747                 }
1748         }
1749         for (i = 0;i < 2;i++)
1750         {
1751                 surf->texturemins[i] = (int) floor(mins[i] / 16) * 16;
1752                 surf->extents[i] = (int) ceil(maxs[i] / 16) * 16 - surf->texturemins[i];
1753         }
1754 }
1755
1756 static void Mod_Q1BSP_LoadFaces(lump_t *l)
1757 {
1758         dface_t *in;
1759         msurface_t *surf;
1760         int i, count, surfnum, planenum, ssize, tsize, firstedge, numedges, totalverts, totaltris, totalmeshes;
1761         surfmesh_t *mesh;
1762         float s, t;
1763
1764         in = (void *)(mod_base + l->fileofs);
1765         if (l->filelen % sizeof(*in))
1766                 Host_Error("Mod_Q1BSP_LoadFaces: funny lump size in %s",loadmodel->name);
1767         count = l->filelen / sizeof(*in);
1768         loadmodel->brushq1.surfaces = Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_t));
1769
1770         loadmodel->brushq1.numsurfaces = count;
1771         loadmodel->brushq1.surfacevisframes = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1772         loadmodel->brushq1.surfacepvsframes = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1773         loadmodel->brushq1.pvssurflist = Mem_Alloc(loadmodel->mempool, count * sizeof(int));
1774
1775         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++)
1776         {
1777                 surf->number = surfnum;
1778                 // FIXME: validate edges, texinfo, etc?
1779                 firstedge = LittleLong(in->firstedge);
1780                 numedges = LittleShort(in->numedges);
1781                 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)
1782                         Host_Error("Mod_Q1BSP_LoadFaces: invalid edge range (firstedge %i, numedges %i, model edges %i)\n", firstedge, numedges, loadmodel->brushq1.numsurfedges);
1783                 i = LittleShort(in->texinfo);
1784                 if ((unsigned int) i >= (unsigned int) loadmodel->brushq1.numtexinfo)
1785                         Host_Error("Mod_Q1BSP_LoadFaces: invalid texinfo index %i(model has %i texinfos)\n", i, loadmodel->brushq1.numtexinfo);
1786                 surf->texinfo = loadmodel->brushq1.texinfo + i;
1787                 surf->flags = surf->texinfo->texture->flags;
1788
1789                 planenum = LittleShort(in->planenum);
1790                 if ((unsigned int) planenum >= (unsigned int) loadmodel->brushq1.numplanes)
1791                         Host_Error("Mod_Q1BSP_LoadFaces: invalid plane index %i (model has %i planes)\n", planenum, loadmodel->brushq1.numplanes);
1792
1793                 if (LittleShort(in->side))
1794                         surf->flags |= SURF_PLANEBACK;
1795
1796                 surf->plane = loadmodel->brushq1.planes + planenum;
1797
1798                 // clear lightmap (filled in later)
1799                 surf->lightmaptexture = NULL;
1800
1801                 // force lightmap upload on first time seeing the surface
1802                 surf->cached_dlight = true;
1803
1804                 Mod_Q1BSP_GenerateSurfacePolygon(surf, firstedge, numedges);
1805
1806                 ssize = (surf->extents[0] >> 4) + 1;
1807                 tsize = (surf->extents[1] >> 4) + 1;
1808
1809                 // lighting info
1810                 for (i = 0;i < MAXLIGHTMAPS;i++)
1811                         surf->styles[i] = in->styles[i];
1812                 i = LittleLong(in->lightofs);
1813                 if (i == -1)
1814                         surf->samples = NULL;
1815                 else if (loadmodel->brush.ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
1816                         surf->samples = loadmodel->brushq1.lightdata + i;
1817                 else // LordHavoc: white lighting (bsp version 29)
1818                         surf->samples = loadmodel->brushq1.lightdata + (i * 3);
1819
1820                 if (surf->texinfo->texture->flags & SURF_LIGHTMAP)
1821                 {
1822                         if ((surf->extents[0] >> 4) + 1 > (256) || (surf->extents[1] >> 4) + 1 > (256))
1823                                 Host_Error("Bad surface extents");
1824                         // stainmap for permanent marks on walls
1825                         surf->stainsamples = Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
1826                         // clear to white
1827                         memset(surf->stainsamples, 255, ssize * tsize * 3);
1828                 }
1829         }
1830
1831         loadmodel->brushq1.entiremesh = Mod_Q1BSP_AllocSurfMesh(totalverts, totaltris);
1832
1833         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++)
1834         {
1835                 mesh = &surf->mesh;
1836                 mesh->num_vertices = surf->poly_numverts;
1837                 mesh->num_triangles = surf->poly_numverts - 2;
1838                 mesh->data_vertex3f = loadmodel->brushq1.entiremesh->data_vertex3f + totalverts * 3;
1839                 mesh->data_texcoordtexture2f = loadmodel->brushq1.entiremesh->data_texcoordtexture2f + totalverts * 2;
1840                 mesh->data_texcoordlightmap2f = loadmodel->brushq1.entiremesh->data_texcoordlightmap2f + totalverts * 2;
1841                 mesh->data_texcoorddetail2f = loadmodel->brushq1.entiremesh->data_texcoorddetail2f + totalverts * 2;
1842                 mesh->data_svector3f = loadmodel->brushq1.entiremesh->data_svector3f + totalverts * 3;
1843                 mesh->data_tvector3f = loadmodel->brushq1.entiremesh->data_tvector3f + totalverts * 3;
1844                 mesh->data_normal3f = loadmodel->brushq1.entiremesh->data_normal3f + totalverts * 3;
1845                 mesh->data_lightmapoffsets = loadmodel->brushq1.entiremesh->data_lightmapoffsets + totalverts;
1846                 mesh->data_element3i = loadmodel->brushq1.entiremesh->data_element3i + totaltris * 3;
1847                 mesh->data_neighbor3i = loadmodel->brushq1.entiremesh->data_neighbor3i + totaltris * 3;
1848
1849                 surf->lightmaptexturestride = 0;
1850                 surf->lightmaptexture = NULL;
1851
1852                 for (i = 0;i < mesh->num_vertices;i++)
1853                 {
1854                         mesh->data_vertex3f[i * 3 + 0] = surf->poly_verts[i * 3 + 0];
1855                         mesh->data_vertex3f[i * 3 + 1] = surf->poly_verts[i * 3 + 1];
1856                         mesh->data_vertex3f[i * 3 + 2] = surf->poly_verts[i * 3 + 2];
1857                         s = DotProduct((mesh->data_vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3];
1858                         t = DotProduct((mesh->data_vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3];
1859                         mesh->data_texcoordtexture2f[i * 2 + 0] = s / surf->texinfo->texture->width;
1860                         mesh->data_texcoordtexture2f[i * 2 + 1] = t / surf->texinfo->texture->height;
1861                         mesh->data_texcoorddetail2f[i * 2 + 0] = s * (1.0f / 16.0f);
1862                         mesh->data_texcoorddetail2f[i * 2 + 1] = t * (1.0f / 16.0f);
1863                         mesh->data_texcoordlightmap2f[i * 2 + 0] = 0;
1864                         mesh->data_texcoordlightmap2f[i * 2 + 1] = 0;
1865                         mesh->data_lightmapoffsets[i] = 0;
1866                 }
1867
1868                 for (i = 0;i < mesh->num_triangles;i++)
1869                 {
1870                         mesh->data_element3i[i * 3 + 0] = 0;
1871                         mesh->data_element3i[i * 3 + 1] = i + 1;
1872                         mesh->data_element3i[i * 3 + 2] = i + 2;
1873                 }
1874
1875                 Mod_BuildTriangleNeighbors(mesh->data_neighbor3i, mesh->data_element3i, mesh->num_triangles);
1876                 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);
1877
1878                 if (surf->texinfo->texture->flags & SURF_LIGHTMAP)
1879                 {
1880                         int i, iu, iv, smax, tmax;
1881                         float u, v, ubase, vbase, uscale, vscale;
1882
1883                         smax = surf->extents[0] >> 4;
1884                         tmax = surf->extents[1] >> 4;
1885
1886                         if (r_miplightmaps.integer)
1887                         {
1888                                 surf->lightmaptexturestride = smax+1;
1889                                 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);
1890                         }
1891                         else
1892                         {
1893                                 surf->lightmaptexturestride = R_CompatibleFragmentWidth(smax+1, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, 0);
1894                                 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);
1895                         }
1896                         R_FragmentLocation(surf->lightmaptexture, NULL, NULL, &ubase, &vbase, &uscale, &vscale);
1897                         uscale = (uscale - ubase) / (smax + 1);
1898                         vscale = (vscale - vbase) / (tmax + 1);
1899
1900                         for (i = 0;i < mesh->num_vertices;i++)
1901                         {
1902                                 u = ((DotProduct((mesh->data_vertex3f + i * 3), surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3]) + 8 - surf->texturemins[0]) * (1.0 / 16.0);
1903                                 v = ((DotProduct((mesh->data_vertex3f + i * 3), surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3]) + 8 - surf->texturemins[1]) * (1.0 / 16.0);
1904                                 mesh->data_texcoordlightmap2f[i * 2 + 0] = u * uscale + ubase;
1905                                 mesh->data_texcoordlightmap2f[i * 2 + 1] = v * vscale + vbase;
1906                                 // LordHavoc: calc lightmap data offset for vertex lighting to use
1907                                 iu = (int) u;
1908                                 iv = (int) v;
1909                                 mesh->data_lightmapoffsets[i] = (bound(0, iv, tmax) * (smax+1) + bound(0, iu, smax)) * 3;
1910                         }
1911                 }
1912         }
1913 }
1914
1915 static void Mod_Q1BSP_SetParent(mnode_t *node, mnode_t *parent)
1916 {
1917         node->parent = parent;
1918         if (node->contents < 0)
1919                 return;
1920         Mod_Q1BSP_SetParent(node->children[0], node);
1921         Mod_Q1BSP_SetParent(node->children[1], node);
1922 }
1923
1924 static void Mod_Q1BSP_LoadNodes(lump_t *l)
1925 {
1926         int                     i, j, count, p;
1927         dnode_t         *in;
1928         mnode_t         *out;
1929
1930         in = (void *)(mod_base + l->fileofs);
1931         if (l->filelen % sizeof(*in))
1932                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
1933         count = l->filelen / sizeof(*in);
1934         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1935
1936         loadmodel->brushq1.nodes = out;
1937         loadmodel->brushq1.numnodes = count;
1938
1939         for ( i=0 ; i<count ; i++, in++, out++)
1940         {
1941                 for (j=0 ; j<3 ; j++)
1942                 {
1943                         out->mins[j] = LittleShort(in->mins[j]);
1944                         out->maxs[j] = LittleShort(in->maxs[j]);
1945                 }
1946
1947                 p = LittleLong(in->planenum);
1948                 out->plane = loadmodel->brushq1.planes + p;
1949
1950                 out->firstsurface = LittleShort(in->firstface);
1951                 out->numsurfaces = LittleShort(in->numfaces);
1952
1953                 for (j=0 ; j<2 ; j++)
1954                 {
1955                         p = LittleShort(in->children[j]);
1956                         if (p >= 0)
1957                                 out->children[j] = loadmodel->brushq1.nodes + p;
1958                         else
1959                                 out->children[j] = (mnode_t *)(loadmodel->brushq1.data_leafs + (-1 - p));
1960                 }
1961         }
1962
1963         Mod_Q1BSP_SetParent(loadmodel->brushq1.nodes, NULL);    // sets nodes and leafs
1964 }
1965
1966 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
1967 {
1968         dleaf_t *in;
1969         mleaf_t *out;
1970         int i, j, count, p;
1971
1972         in = (void *)(mod_base + l->fileofs);
1973         if (l->filelen % sizeof(*in))
1974                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
1975         count = l->filelen / sizeof(*in);
1976         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1977
1978         loadmodel->brushq1.data_leafs = out;
1979         loadmodel->brushq1.num_leafs = count;
1980         // get visleafs from the submodel data
1981         loadmodel->brush.num_pvsclusters = loadmodel->brushq1.submodels[0].visleafs;
1982         loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters+7)>>3;
1983         loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
1984         memset(loadmodel->brush.data_pvsclusters, 0xFF, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
1985
1986         for ( i=0 ; i<count ; i++, in++, out++)
1987         {
1988                 for (j=0 ; j<3 ; j++)
1989                 {
1990                         out->mins[j] = LittleShort(in->mins[j]);
1991                         out->maxs[j] = LittleShort(in->maxs[j]);
1992                 }
1993
1994                 // FIXME: this function could really benefit from some error checking
1995
1996                 out->contents = LittleLong(in->contents);
1997
1998                 out->firstmarksurface = loadmodel->brushq1.marksurfaces + LittleShort(in->firstmarksurface);
1999                 out->nummarksurfaces = LittleShort(in->nummarksurfaces);
2000                 if (out->firstmarksurface < 0 || LittleShort(in->firstmarksurface) + out->nummarksurfaces > loadmodel->brushq1.nummarksurfaces)
2001                 {
2002                         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);
2003                         out->firstmarksurface = NULL;
2004                         out->nummarksurfaces = 0;
2005                 }
2006
2007                 out->clusterindex = i - 1;
2008                 if (out->clusterindex >= loadmodel->brush.num_pvsclusters)
2009                         out->clusterindex = -1;
2010
2011                 p = LittleLong(in->visofs);
2012                 // ignore visofs errors on leaf 0 (solid)
2013                 if (p >= 0 && out->clusterindex >= 0)
2014                 {
2015                         if (p >= loadmodel->brushq1.num_compressedpvs)
2016                                 Con_Print("Mod_Q1BSP_LoadLeafs: invalid visofs\n");
2017                         else
2018                                 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);
2019                 }
2020
2021                 for (j = 0;j < 4;j++)
2022                         out->ambient_sound_level[j] = in->ambient_level[j];
2023
2024                 // FIXME: Insert caustics here
2025         }
2026 }
2027
2028 static void Mod_Q1BSP_LoadClipnodes(lump_t *l)
2029 {
2030         dclipnode_t *in, *out;
2031         int                     i, count;
2032         hull_t          *hull;
2033
2034         in = (void *)(mod_base + l->fileofs);
2035         if (l->filelen % sizeof(*in))
2036                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2037         count = l->filelen / sizeof(*in);
2038         out = Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2039
2040         loadmodel->brushq1.clipnodes = out;
2041         loadmodel->brushq1.numclipnodes = count;
2042
2043         if (loadmodel->brush.ishlbsp)
2044         {
2045                 hull = &loadmodel->brushq1.hulls[1];
2046                 hull->clipnodes = out;
2047                 hull->firstclipnode = 0;
2048                 hull->lastclipnode = count-1;
2049                 hull->planes = loadmodel->brushq1.planes;
2050                 hull->clip_mins[0] = -16;
2051                 hull->clip_mins[1] = -16;
2052                 hull->clip_mins[2] = -36;
2053                 hull->clip_maxs[0] = 16;
2054                 hull->clip_maxs[1] = 16;
2055                 hull->clip_maxs[2] = 36;
2056                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2057
2058                 hull = &loadmodel->brushq1.hulls[2];
2059                 hull->clipnodes = out;
2060                 hull->firstclipnode = 0;
2061                 hull->lastclipnode = count-1;
2062                 hull->planes = loadmodel->brushq1.planes;
2063                 hull->clip_mins[0] = -32;
2064                 hull->clip_mins[1] = -32;
2065                 hull->clip_mins[2] = -32;
2066                 hull->clip_maxs[0] = 32;
2067                 hull->clip_maxs[1] = 32;
2068                 hull->clip_maxs[2] = 32;
2069                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2070
2071                 hull = &loadmodel->brushq1.hulls[3];
2072                 hull->clipnodes = out;
2073                 hull->firstclipnode = 0;
2074                 hull->lastclipnode = count-1;
2075                 hull->planes = loadmodel->brushq1.planes;
2076                 hull->clip_mins[0] = -16;
2077                 hull->clip_mins[1] = -16;
2078                 hull->clip_mins[2] = -18;
2079                 hull->clip_maxs[0] = 16;
2080                 hull->clip_maxs[1] = 16;
2081                 hull->clip_maxs[2] = 18;
2082                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2083         }
2084         else
2085         {
2086                 hull = &loadmodel->brushq1.hulls[1];
2087                 hull->clipnodes = out;
2088                 hull->firstclipnode = 0;
2089                 hull->lastclipnode = count-1;
2090                 hull->planes = loadmodel->brushq1.planes;
2091                 hull->clip_mins[0] = -16;
2092                 hull->clip_mins[1] = -16;
2093                 hull->clip_mins[2] = -24;
2094                 hull->clip_maxs[0] = 16;
2095                 hull->clip_maxs[1] = 16;
2096                 hull->clip_maxs[2] = 32;
2097                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2098
2099                 hull = &loadmodel->brushq1.hulls[2];
2100                 hull->clipnodes = out;
2101                 hull->firstclipnode = 0;
2102                 hull->lastclipnode = count-1;
2103                 hull->planes = loadmodel->brushq1.planes;
2104                 hull->clip_mins[0] = -32;
2105                 hull->clip_mins[1] = -32;
2106                 hull->clip_mins[2] = -24;
2107                 hull->clip_maxs[0] = 32;
2108                 hull->clip_maxs[1] = 32;
2109                 hull->clip_maxs[2] = 64;
2110                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2111         }
2112
2113         for (i=0 ; i<count ; i++, out++, in++)
2114         {
2115                 out->planenum = LittleLong(in->planenum);
2116                 out->children[0] = LittleShort(in->children[0]);
2117                 out->children[1] = LittleShort(in->children[1]);
2118                 if (out->children[0] >= count || out->children[1] >= count)
2119                         Host_Error("Corrupt clipping hull(out of range child)\n");
2120         }
2121 }
2122
2123 //Duplicate the drawing hull structure as a clipping hull
2124 static void Mod_Q1BSP_MakeHull0(void)
2125 {
2126         mnode_t         *in;
2127         dclipnode_t *out;
2128         int                     i;
2129         hull_t          *hull;
2130
2131         hull = &loadmodel->brushq1.hulls[0];
2132
2133         in = loadmodel->brushq1.nodes;
2134         out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numnodes * sizeof(dclipnode_t));
2135
2136         hull->clipnodes = out;
2137         hull->firstclipnode = 0;
2138         hull->lastclipnode = loadmodel->brushq1.numnodes - 1;
2139         hull->planes = loadmodel->brushq1.planes;
2140
2141         for (i = 0;i < loadmodel->brushq1.numnodes;i++, out++, in++)
2142         {
2143                 out->planenum = in->plane - loadmodel->brushq1.planes;
2144                 out->children[0] = in->children[0]->contents < 0 ? in->children[0]->contents : in->children[0] - loadmodel->brushq1.nodes;
2145                 out->children[1] = in->children[1]->contents < 0 ? in->children[1]->contents : in->children[1] - loadmodel->brushq1.nodes;
2146         }
2147 }
2148
2149 static void Mod_Q1BSP_LoadMarksurfaces(lump_t *l)
2150 {
2151         int i, j;
2152         short *in;
2153
2154         in = (void *)(mod_base + l->fileofs);
2155         if (l->filelen % sizeof(*in))
2156                 Host_Error("Mod_Q1BSP_LoadMarksurfaces: funny lump size in %s",loadmodel->name);
2157         loadmodel->brushq1.nummarksurfaces = l->filelen / sizeof(*in);
2158         loadmodel->brushq1.marksurfaces = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.nummarksurfaces * sizeof(int));
2159
2160         for (i = 0;i < loadmodel->brushq1.nummarksurfaces;i++)
2161         {
2162                 j = (unsigned) LittleShort(in[i]);
2163                 if (j >= loadmodel->brushq1.numsurfaces)
2164                         Host_Error("Mod_Q1BSP_LoadMarksurfaces: bad surface number");
2165                 loadmodel->brushq1.marksurfaces[i] = j;
2166         }
2167 }
2168
2169 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2170 {
2171         int             i;
2172         int             *in;
2173
2174         in = (void *)(mod_base + l->fileofs);
2175         if (l->filelen % sizeof(*in))
2176                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2177         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2178         loadmodel->brushq1.surfedges = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2179
2180         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2181                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2182 }
2183
2184
2185 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2186 {
2187         int                     i;
2188         mplane_t        *out;
2189         dplane_t        *in;
2190
2191         in = (void *)(mod_base + l->fileofs);
2192         if (l->filelen % sizeof(*in))
2193                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2194
2195         loadmodel->brushq1.numplanes = l->filelen / sizeof(*in);
2196         loadmodel->brushq1.planes = out = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numplanes * sizeof(*out));
2197
2198         for (i = 0;i < loadmodel->brushq1.numplanes;i++, in++, out++)
2199         {
2200                 out->normal[0] = LittleFloat(in->normal[0]);
2201                 out->normal[1] = LittleFloat(in->normal[1]);
2202                 out->normal[2] = LittleFloat(in->normal[2]);
2203                 out->dist = LittleFloat(in->dist);
2204
2205                 PlaneClassify(out);
2206         }
2207 }
2208
2209 typedef struct portal_s
2210 {
2211         mplane_t plane;
2212         mnode_t *nodes[2];              // [0] = front side of plane
2213         struct portal_s *next[2];
2214         winding_t *winding;
2215         struct portal_s *chain; // all portals are linked into a list
2216 }
2217 portal_t;
2218
2219 static portal_t *portalchain;
2220
2221 /*
2222 ===========
2223 AllocPortal
2224 ===========
2225 */
2226 static portal_t *AllocPortal(void)
2227 {
2228         portal_t *p;
2229         p = Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2230         p->chain = portalchain;
2231         portalchain = p;
2232         return p;
2233 }
2234
2235 static void FreePortal(portal_t *p)
2236 {
2237         Mem_Free(p);
2238 }
2239
2240 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2241 {
2242         // calculate children first
2243         if (node->children[0]->contents >= 0)
2244                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2245         if (node->children[1]->contents >= 0)
2246                 Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2247
2248         // make combined bounding box from children
2249         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2250         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2251         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2252         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2253         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2254         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2255 }
2256
2257 static void Mod_Q1BSP_FinalizePortals(void)
2258 {
2259         int i, j, numportals, numpoints;
2260         portal_t *p, *pnext;
2261         mportal_t *portal;
2262         mvertex_t *point;
2263         mleaf_t *leaf, *endleaf;
2264         winding_t *w;
2265
2266         // recalculate bounding boxes for all leafs(because qbsp is very sloppy)
2267         leaf = loadmodel->brushq1.data_leafs;
2268         endleaf = leaf + loadmodel->brushq1.num_leafs;
2269         for (;leaf < endleaf;leaf++)
2270         {
2271                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2272                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2273         }
2274         p = portalchain;
2275         while (p)
2276         {
2277                 if (p->winding)
2278                 {
2279                         for (i = 0;i < 2;i++)
2280                         {
2281                                 leaf = (mleaf_t *)p->nodes[i];
2282                                 w = p->winding;
2283                                 for (j = 0;j < w->numpoints;j++)
2284                                 {
2285                                         if (leaf->mins[0] > w->points[j][0]) leaf->mins[0] = w->points[j][0];
2286                                         if (leaf->mins[1] > w->points[j][1]) leaf->mins[1] = w->points[j][1];
2287                                         if (leaf->mins[2] > w->points[j][2]) leaf->mins[2] = w->points[j][2];
2288                                         if (leaf->maxs[0] < w->points[j][0]) leaf->maxs[0] = w->points[j][0];
2289                                         if (leaf->maxs[1] < w->points[j][1]) leaf->maxs[1] = w->points[j][1];
2290                                         if (leaf->maxs[2] < w->points[j][2]) leaf->maxs[2] = w->points[j][2];
2291                                 }
2292                         }
2293                 }
2294                 p = p->chain;
2295         }
2296
2297         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brushq1.nodes);
2298
2299         // tally up portal and point counts
2300         p = portalchain;
2301         numportals = 0;
2302         numpoints = 0;
2303         while (p)
2304         {
2305                 // note: this check must match the one below or it will usually corrupt memory
2306                 // 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
2307                 if (p->winding && p->nodes[0] != p->nodes[1]
2308                  && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2309                  && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2310                 {
2311                         numportals += 2;
2312                         numpoints += p->winding->numpoints * 2;
2313                 }
2314                 p = p->chain;
2315         }
2316         loadmodel->brushq1.portals = Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2317         loadmodel->brushq1.numportals = numportals;
2318         loadmodel->brushq1.portalpoints = (void *)((qbyte *) loadmodel->brushq1.portals + numportals * sizeof(mportal_t));
2319         loadmodel->brushq1.numportalpoints = numpoints;
2320         // clear all leaf portal chains
2321         for (i = 0;i < loadmodel->brushq1.num_leafs;i++)
2322                 loadmodel->brushq1.data_leafs[i].portals = NULL;
2323         // process all portals in the global portal chain, while freeing them
2324         portal = loadmodel->brushq1.portals;
2325         point = loadmodel->brushq1.portalpoints;
2326         p = portalchain;
2327         portalchain = NULL;
2328         while (p)
2329         {
2330                 pnext = p->chain;
2331
2332                 if (p->winding)
2333                 {
2334                         // note: this check must match the one above or it will usually corrupt memory
2335                         // 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
2336                         if (p->nodes[0] != p->nodes[1]
2337                          && p->nodes[0]->contents != CONTENTS_SOLID && p->nodes[1]->contents != CONTENTS_SOLID
2338                          && p->nodes[0]->contents != CONTENTS_SKY && p->nodes[1]->contents != CONTENTS_SKY)
2339                         {
2340                                 // first make the back to front portal(forward portal)
2341                                 portal->points = point;
2342                                 portal->numpoints = p->winding->numpoints;
2343                                 portal->plane.dist = p->plane.dist;
2344                                 VectorCopy(p->plane.normal, portal->plane.normal);
2345                                 portal->here = (mleaf_t *)p->nodes[1];
2346                                 portal->past = (mleaf_t *)p->nodes[0];
2347                                 // copy points
2348                                 for (j = 0;j < portal->numpoints;j++)
2349                                 {
2350                                         VectorCopy(p->winding->points[j], point->position);
2351                                         point++;
2352                                 }
2353                                 PlaneClassify(&portal->plane);
2354
2355                                 // link into leaf's portal chain
2356                                 portal->next = portal->here->portals;
2357                                 portal->here->portals = portal;
2358
2359                                 // advance to next portal
2360                                 portal++;
2361
2362                                 // then make the front to back portal(backward portal)
2363                                 portal->points = point;
2364                                 portal->numpoints = p->winding->numpoints;
2365                                 portal->plane.dist = -p->plane.dist;
2366                                 VectorNegate(p->plane.normal, portal->plane.normal);
2367                                 portal->here = (mleaf_t *)p->nodes[0];
2368                                 portal->past = (mleaf_t *)p->nodes[1];
2369                                 // copy points
2370                                 for (j = portal->numpoints - 1;j >= 0;j--)
2371                                 {
2372                                         VectorCopy(p->winding->points[j], point->position);
2373                                         point++;
2374                                 }
2375                                 PlaneClassify(&portal->plane);
2376
2377                                 // link into leaf's portal chain
2378                                 portal->next = portal->here->portals;
2379                                 portal->here->portals = portal;
2380
2381                                 // advance to next portal
2382                                 portal++;
2383                         }
2384                         Winding_Free(p->winding);
2385                 }
2386                 FreePortal(p);
2387                 p = pnext;
2388         }
2389 }
2390
2391 /*
2392 =============
2393 AddPortalToNodes
2394 =============
2395 */
2396 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2397 {
2398         if (!front)
2399                 Host_Error("AddPortalToNodes: NULL front node");
2400         if (!back)
2401                 Host_Error("AddPortalToNodes: NULL back node");
2402         if (p->nodes[0] || p->nodes[1])
2403                 Host_Error("AddPortalToNodes: already included");
2404         // 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
2405
2406         p->nodes[0] = front;
2407         p->next[0] = (portal_t *)front->portals;
2408         front->portals = (mportal_t *)p;
2409
2410         p->nodes[1] = back;
2411         p->next[1] = (portal_t *)back->portals;
2412         back->portals = (mportal_t *)p;
2413 }
2414
2415 /*
2416 =============
2417 RemovePortalFromNode
2418 =============
2419 */
2420 static void RemovePortalFromNodes(portal_t *portal)
2421 {
2422         int i;
2423         mnode_t *node;
2424         void **portalpointer;
2425         portal_t *t;
2426         for (i = 0;i < 2;i++)
2427         {
2428                 node = portal->nodes[i];
2429
2430                 portalpointer = (void **) &node->portals;
2431                 while (1)
2432                 {
2433                         t = *portalpointer;
2434                         if (!t)
2435                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2436
2437                         if (t == portal)
2438                         {
2439                                 if (portal->nodes[0] == node)
2440                                 {
2441                                         *portalpointer = portal->next[0];
2442                                         portal->nodes[0] = NULL;
2443                                 }
2444                                 else if (portal->nodes[1] == node)
2445                                 {
2446                                         *portalpointer = portal->next[1];
2447                                         portal->nodes[1] = NULL;
2448                                 }
2449                                 else
2450                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2451                                 break;
2452                         }
2453
2454                         if (t->nodes[0] == node)
2455                                 portalpointer = (void **) &t->next[0];
2456                         else if (t->nodes[1] == node)
2457                                 portalpointer = (void **) &t->next[1];
2458                         else
2459                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2460                 }
2461         }
2462 }
2463
2464 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2465 {
2466         int side;
2467         mnode_t *front, *back, *other_node;
2468         mplane_t clipplane, *plane;
2469         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2470         winding_t *nodeportalwinding, *frontwinding, *backwinding;
2471
2472         // if a leaf, we're done
2473         if (node->contents)
2474                 return;
2475
2476         plane = node->plane;
2477
2478         front = node->children[0];
2479         back = node->children[1];
2480         if (front == back)
2481                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2482
2483         // create the new portal by generating a polygon for the node plane,
2484         // and clipping it by all of the other portals(which came from nodes above this one)
2485         nodeportal = AllocPortal();
2486         nodeportal->plane = *plane;
2487
2488         nodeportalwinding = Winding_NewFromPlane(nodeportal->plane.normal[0], nodeportal->plane.normal[1], nodeportal->plane.normal[2], nodeportal->plane.dist);
2489         side = 0;       // shut up compiler warning
2490         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2491         {
2492                 clipplane = portal->plane;
2493                 if (portal->nodes[0] == portal->nodes[1])
2494                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2495                 if (portal->nodes[0] == node)
2496                         side = 0;
2497                 else if (portal->nodes[1] == node)
2498                 {
2499                         clipplane.dist = -clipplane.dist;
2500                         VectorNegate(clipplane.normal, clipplane.normal);
2501                         side = 1;
2502                 }
2503                 else
2504                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2505
2506                 nodeportalwinding = Winding_Clip(nodeportalwinding, clipplane.normal[0], clipplane.normal[1], clipplane.normal[2], clipplane.dist, true);
2507                 if (!nodeportalwinding)
2508                 {
2509                         Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2510                         break;
2511                 }
2512         }
2513
2514         if (nodeportalwinding)
2515         {
2516                 // if the plane was not clipped on all sides, there was an error
2517                 nodeportal->winding = nodeportalwinding;
2518                 AddPortalToNodes(nodeportal, front, back);
2519         }
2520
2521         // split the portals of this node along this node's plane and assign them to the children of this node
2522         // (migrating the portals downward through the tree)
2523         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2524         {
2525                 if (portal->nodes[0] == portal->nodes[1])
2526                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2527                 if (portal->nodes[0] == node)
2528                         side = 0;
2529                 else if (portal->nodes[1] == node)
2530                         side = 1;
2531                 else
2532                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2533                 nextportal = portal->next[side];
2534
2535                 other_node = portal->nodes[!side];
2536                 RemovePortalFromNodes(portal);
2537
2538                 // cut the portal into two portals, one on each side of the node plane
2539                 Winding_Divide(portal->winding, plane->normal[0], plane->normal[1], plane->normal[2], plane->dist, &frontwinding, &backwinding);
2540
2541                 if (!frontwinding)
2542                 {
2543                         if (side == 0)
2544                                 AddPortalToNodes(portal, back, other_node);
2545                         else
2546                                 AddPortalToNodes(portal, other_node, back);
2547                         continue;
2548                 }
2549                 if (!backwinding)
2550                 {
2551                         if (side == 0)
2552                                 AddPortalToNodes(portal, front, other_node);
2553                         else
2554                                 AddPortalToNodes(portal, other_node, front);
2555                         continue;
2556                 }
2557
2558                 // the winding is split
2559                 splitportal = AllocPortal();
2560                 temp = splitportal->chain;
2561                 *splitportal = *portal;
2562                 splitportal->chain = temp;
2563                 splitportal->winding = backwinding;
2564                 Winding_Free(portal->winding);
2565                 portal->winding = frontwinding;
2566
2567                 if (side == 0)
2568                 {
2569                         AddPortalToNodes(portal, front, other_node);
2570                         AddPortalToNodes(splitportal, back, other_node);
2571                 }
2572                 else
2573                 {
2574                         AddPortalToNodes(portal, other_node, front);
2575                         AddPortalToNodes(splitportal, other_node, back);
2576                 }
2577         }
2578
2579         Mod_Q1BSP_RecursiveNodePortals(front);
2580         Mod_Q1BSP_RecursiveNodePortals(back);
2581 }
2582
2583 static void Mod_Q1BSP_MakePortals(void)
2584 {
2585         portalchain = NULL;
2586         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brushq1.nodes);
2587         Mod_Q1BSP_FinalizePortals();
2588 }
2589
2590 static void Mod_Q1BSP_BuildSurfaceNeighbors(msurface_t *surfaces, int numsurfaces, mempool_t *mempool)
2591 {
2592 #if 0
2593         int surfnum, vertnum, vertnum2, snum, vnum, vnum2;
2594         msurface_t *surf, *s;
2595         float *v0, *v1, *v2, *v3;
2596         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2597                 surf->neighborsurfaces = Mem_Alloc(mempool, surf->poly_numverts * sizeof(msurface_t *));
2598         for (surf = surfaces, surfnum = 0;surfnum < numsurfaces;surf++, surfnum++)
2599         {
2600                 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)
2601                 {
2602                         if (surf->neighborsurfaces[vertnum])
2603                                 continue;
2604                         surf->neighborsurfaces[vertnum] = NULL;
2605                         for (s = surfaces, snum = 0;snum < numsurfaces;s++, snum++)
2606                         {
2607                                 if (s->poly_mins[0] > (surf->poly_maxs[0] + 1) || s->poly_maxs[0] < (surf->poly_mins[0] - 1)
2608                                  || s->poly_mins[1] > (surf->poly_maxs[1] + 1) || s->poly_maxs[1] < (surf->poly_mins[1] - 1)
2609                                  || s->poly_mins[2] > (surf->poly_maxs[2] + 1) || s->poly_maxs[2] < (surf->poly_mins[2] - 1)
2610                                  || s == surf)
2611                                         continue;
2612                                 for (vnum = 0;vnum < s->poly_numverts;vnum++)
2613                                         if (s->neighborsurfaces[vnum] == surf)
2614                                                 break;
2615                                 if (vnum < s->poly_numverts)
2616                                         continue;
2617                                 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)
2618                                 {
2619                                         if (s->neighborsurfaces[vnum] == NULL
2620                                          && ((v0[0] == v2[0] && v0[1] == v2[1] && v0[2] == v2[2] && v1[0] == v3[0] && v1[1] == v3[1] && v1[2] == v3[2])
2621                                           || (v1[0] == v2[0] && v1[1] == v2[1] && v1[2] == v2[2] && v0[0] == v3[0] && v0[1] == v3[1] && v0[2] == v3[2])))
2622                                         {
2623                                                 surf->neighborsurfaces[vertnum] = s;
2624                                                 s->neighborsurfaces[vnum] = surf;
2625                                                 break;
2626                                         }
2627                                 }
2628                                 if (vnum < s->poly_numverts)
2629                                         break;
2630                         }
2631                 }
2632         }
2633 #endif
2634 }
2635
2636 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
2637 {
2638         int i, j, stylecounts[256], totalcount, remapstyles[256];
2639         msurface_t *surf;
2640         memset(stylecounts, 0, sizeof(stylecounts));
2641         for (i = 0;i < model->nummodelsurfaces;i++)
2642         {
2643                 surf = model->brushq1.surfaces + model->firstmodelsurface + i;
2644                 for (j = 0;j < MAXLIGHTMAPS;j++)
2645                         stylecounts[surf->styles[j]]++;
2646         }
2647         totalcount = 0;
2648         model->brushq1.light_styles = 0;
2649         for (i = 0;i < 255;i++)
2650         {
2651                 if (stylecounts[i])
2652                 {
2653                         remapstyles[i] = model->brushq1.light_styles++;
2654                         totalcount += stylecounts[i] + 1;
2655                 }
2656         }
2657         if (!totalcount)
2658                 return;
2659         model->brushq1.light_style = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(qbyte));
2660         model->brushq1.light_stylevalue = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(int));
2661         model->brushq1.light_styleupdatechains = Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(msurface_t **));
2662         model->brushq1.light_styleupdatechainsbuffer = Mem_Alloc(mempool, totalcount * sizeof(msurface_t *));
2663         model->brushq1.light_styles = 0;
2664         for (i = 0;i < 255;i++)
2665                 if (stylecounts[i])
2666                         model->brushq1.light_style[model->brushq1.light_styles++] = i;
2667         j = 0;
2668         for (i = 0;i < model->brushq1.light_styles;i++)
2669         {
2670                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2671                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2672         }
2673         for (i = 0;i < model->nummodelsurfaces;i++)
2674         {
2675                 surf = model->brushq1.surfaces + model->firstmodelsurface + i;
2676                 for (j = 0;j < MAXLIGHTMAPS;j++)
2677                         if (surf->styles[j] != 255)
2678                                 *model->brushq1.light_styleupdatechains[remapstyles[surf->styles[j]]]++ = surf;
2679         }
2680         j = 0;
2681         for (i = 0;i < model->brushq1.light_styles;i++)
2682         {
2683                 *model->brushq1.light_styleupdatechains[i] = NULL;
2684                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2685                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2686         }
2687 }
2688
2689 static void Mod_Q1BSP_BuildPVSTextureChains(model_t *model)
2690 {
2691         int i, j;
2692         for (i = 0;i < model->brushq1.numtextures;i++)
2693                 model->brushq1.pvstexturechainslength[i] = 0;
2694         for (i = 0, j = model->firstmodelsurface;i < model->nummodelsurfaces;i++, j++)
2695         {
2696                 if (model->brushq1.surfacepvsframes[j] == model->brushq1.pvsframecount)
2697                 {
2698                         model->brushq1.pvssurflist[model->brushq1.pvssurflistlength++] = j;
2699                         model->brushq1.pvstexturechainslength[model->brushq1.surfaces[j].texinfo->texture->number]++;
2700                 }
2701         }
2702         for (i = 0, j = 0;i < model->brushq1.numtextures;i++)
2703         {
2704                 if (model->brushq1.pvstexturechainslength[i])
2705                 {
2706                         model->brushq1.pvstexturechains[i] = model->brushq1.pvstexturechainsbuffer + j;
2707                         j += model->brushq1.pvstexturechainslength[i] + 1;
2708                 }
2709                 else
2710                         model->brushq1.pvstexturechains[i] = NULL;
2711         }
2712         for (i = 0, j = model->firstmodelsurface;i < model->nummodelsurfaces;i++, j++)
2713                 if (model->brushq1.surfacepvsframes[j] == model->brushq1.pvsframecount)
2714                         *model->brushq1.pvstexturechains[model->brushq1.surfaces[j].texinfo->texture->number]++ = model->brushq1.surfaces + j;
2715         for (i = 0;i < model->brushq1.numtextures;i++)
2716         {
2717                 if (model->brushq1.pvstexturechainslength[i])
2718                 {
2719                         *model->brushq1.pvstexturechains[i] = NULL;
2720                         model->brushq1.pvstexturechains[i] -= model->brushq1.pvstexturechainslength[i];
2721                 }
2722         }
2723 }
2724
2725 //Returns PVS data for a given point
2726 //(note: can return NULL)
2727 static qbyte *Mod_Q1BSP_GetPVS(model_t *model, const vec3_t p)
2728 {
2729         mnode_t *node;
2730         Mod_CheckLoaded(model);
2731         node = model->brushq1.nodes;
2732         while (node->plane)
2733                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
2734         if (((mleaf_t *)node)->clusterindex >= 0)
2735                 return model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
2736         else
2737                 return NULL;
2738 }
2739
2740 static void Mod_Q1BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbytes, mnode_t *node)
2741 {
2742         while (node->plane)
2743         {
2744                 float d = PlaneDiff(org, node->plane);
2745                 if (d > radius)
2746                         node = node->children[0];
2747                 else if (d < -radius)
2748                         node = node->children[1];
2749                 else
2750                 {
2751                         // go down both sides
2752                         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
2753                         node = node->children[1];
2754                 }
2755         }
2756         // if this leaf is in a cluster, accumulate the pvs bits
2757         if (((mleaf_t *)node)->clusterindex >= 0)
2758         {
2759                 int i;
2760                 qbyte *pvs = model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
2761                 for (i = 0;i < pvsbytes;i++)
2762                         pvsbuffer[i] |= pvs[i];
2763         }
2764 }
2765
2766 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
2767 //of the given point.
2768 static int Mod_Q1BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbufferlength)
2769 {
2770         int bytes = ((model->brushq1.num_leafs - 1) + 7) >> 3;
2771         bytes = min(bytes, pvsbufferlength);
2772         if (r_novis.integer || !Mod_Q1BSP_GetPVS(model, org))
2773         {
2774                 memset(pvsbuffer, 0xFF, bytes);
2775                 return bytes;
2776         }
2777         memset(pvsbuffer, 0, bytes);
2778         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brushq1.nodes);
2779         return bytes;
2780 }
2781
2782 static void Mod_Q1BSP_RoundUpToHullSize(model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
2783 {
2784         vec3_t size;
2785         const hull_t *hull;
2786
2787         VectorSubtract(inmaxs, inmins, size);
2788         if (cmodel->brush.ishlbsp)
2789         {
2790                 if (size[0] < 3)
2791                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
2792                 else if (size[0] <= 32)
2793                 {
2794                         if (size[2] < 54) // pick the nearest of 36 or 72
2795                                 hull = &cmodel->brushq1.hulls[3]; // 32x32x36
2796                         else
2797                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
2798                 }
2799                 else
2800                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
2801         }
2802         else
2803         {
2804                 if (size[0] < 3)
2805                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
2806                 else if (size[0] <= 32)
2807                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
2808                 else
2809                         hull = &cmodel->brushq1.hulls[2]; // 64x64x88
2810         }
2811         VectorCopy(inmins, outmins);
2812         VectorAdd(inmins, hull->clip_size, outmaxs);
2813 }
2814
2815 /*
2816 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)
2817 {
2818         mleaf_t *leaf;
2819         for (;;)
2820         {
2821                 if (!BoxesOverlap(node->mins, node->maxs, mins, maxs))
2822                         return;
2823                 if (!node->plane)
2824                         break;
2825                 Mod_Q1BSP_RecursiveGetVisible(node->children[0], model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces, pvs);
2826                 node = node->children[1];
2827         }
2828         leaf = (mleaf_t *)node;
2829         if ((pvs == NULL || CHECKPVSBIT(pvs, leaf->clusterindex)))
2830         {
2831                 int marksurfacenum;
2832                 msurface_t *surf;
2833                 if (maxleafs && *numleafs < maxleafs)
2834                         leaflist[(*numleafs)++] = leaf;
2835                 if (maxsurfaces)
2836                 {
2837                         for (marksurfacenum = 0;marksurfacenum < leaf->nummarksurfaces;marksurfacenum++)
2838                         {
2839                                 surf = model->brushq1.surfaces + leaf->firstmarksurface[marksurfacenum];
2840                                 if (surf->shadowmark != shadowmarkcount)
2841                                 {
2842                                         surf->shadowmark = shadowmarkcount;
2843                                         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)
2844                                                 surfacelist[(*numsurfaces)++] = surf;
2845                                 }
2846                         }
2847                 }
2848         }
2849 }
2850
2851 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)
2852 {
2853         // FIXME: support portals
2854         if (maxsurfaces)
2855                 *numsurfaces = 0;
2856         if (maxleafs)
2857                 *numleafs = 0;
2858         pvs = ent->model->brush.GetPVS(ent->model, relativelightorigin);
2859         Mod_Q1BSP_RecursiveGetVisible(ent->model->brushq1.nodes + ent->model->brushq1.firstclipnode, model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces);
2860 }
2861 */
2862
2863 extern void R_Q1BSP_DrawSky(entity_render_t *ent);
2864 extern void R_Q1BSP_Draw(entity_render_t *ent);
2865 extern void R_Q1BSP_GetLightInfo(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, vec3_t outmins, vec3_t outmaxs, int *outclusterlist, qbyte *outclusterpvs, int *outnumclusterspointer, int *outsurfacelist, qbyte *outsurfacepvs, int *outnumsurfacespointer);
2866 extern void R_Q1BSP_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, int numsurfaces, const int *surfacelist);
2867 extern void R_Q1BSP_DrawLight(entity_render_t *ent, vec3_t relativelightorigin, vec3_t relativeeyeorigin, float lightradius, float *lightcolor, const matrix4x4_t *matrix_modeltolight, const matrix4x4_t *matrix_modeltoattenuationxyz, const matrix4x4_t *matrix_modeltoattenuationz, rtexture_t *lightcubemap, int numsurfaces, const int *surfacelist);
2868 void Mod_Q1BSP_Load(model_t *mod, void *buffer)
2869 {
2870         int i, j, k;
2871         dheader_t *header;
2872         dmodel_t *bm;
2873         mempool_t *mainmempool;
2874         float dist, modelyawradius, modelradius, *vec;
2875         msurface_t *surf;
2876         int numshadowmeshtriangles;
2877
2878         mod->type = mod_brush;
2879
2880         header = (dheader_t *)buffer;
2881
2882         i = LittleLong(header->version);
2883         if (i != BSPVERSION && i != 30)
2884                 Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i(Quake) or 30(HalfLife))", mod->name, i, BSPVERSION);
2885         mod->brush.ishlbsp = i == 30;
2886
2887         mod->soundfromcenter = true;
2888         mod->TraceBox = Mod_Q1BSP_TraceBox;
2889         mod->brush.SuperContentsFromNativeContents = Mod_Q1BSP_SuperContentsFromNativeContents;
2890         mod->brush.NativeContentsFromSuperContents = Mod_Q1BSP_NativeContentsFromSuperContents;
2891         mod->brush.GetPVS = Mod_Q1BSP_GetPVS;
2892         mod->brush.FatPVS = Mod_Q1BSP_FatPVS;
2893         mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
2894         mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
2895         mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
2896         mod->brush.AmbientSoundLevelsForPoint = Mod_Q1BSP_AmbientSoundLevelsForPoint;
2897         mod->brush.RoundUpToHullSize = Mod_Q1BSP_RoundUpToHullSize;
2898         mod->brushq1.PointInLeaf = Mod_Q1BSP_PointInLeaf;
2899         mod->brushq1.BuildPVSTextureChains = Mod_Q1BSP_BuildPVSTextureChains;
2900
2901         if (loadmodel->isworldmodel)
2902         {
2903                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
2904                 // until we get a texture for it...
2905                 R_ResetQuakeSky();
2906         }
2907
2908 // swap all the lumps
2909         mod_base = (qbyte *)header;
2910
2911         for (i = 0;i < (int) sizeof(dheader_t) / 4;i++)
2912                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
2913
2914 // load into heap
2915
2916         // store which lightmap format to use
2917         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
2918
2919         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
2920         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
2921         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
2922         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
2923         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
2924         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
2925         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
2926         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
2927         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
2928         Mod_Q1BSP_LoadMarksurfaces(&header->lumps[LUMP_MARKSURFACES]);
2929         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
2930         // load submodels before leafs because they contain the number of vis leafs
2931         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS]);
2932         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
2933         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
2934         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES]);
2935
2936         if (!mod->brushq1.lightdata)
2937                 mod->brush.LightPoint = NULL;
2938
2939         if (mod->brushq1.data_compressedpvs)
2940                 Mem_Free(mod->brushq1.data_compressedpvs);
2941         mod->brushq1.data_compressedpvs = NULL;
2942         mod->brushq1.num_compressedpvs = 0;
2943
2944         Mod_Q1BSP_MakeHull0();
2945         Mod_Q1BSP_MakePortals();
2946
2947         mod->numframes = 2;             // regular and alternate animation
2948
2949         mainmempool = mod->mempool;
2950
2951         Mod_Q1BSP_LoadLightList();
2952         loadmodel = loadmodel;
2953
2954         // make a single combined shadow mesh to allow optimized shadow volume creation
2955         numshadowmeshtriangles = 0;
2956         for (j = 0, surf = loadmodel->brushq1.surfaces;j < loadmodel->brushq1.numsurfaces;j++, surf++)
2957         {
2958                 surf->num_firstshadowmeshtriangle = numshadowmeshtriangles;
2959                 numshadowmeshtriangles += surf->mesh.num_triangles;
2960         }
2961         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Begin(loadmodel->mempool, numshadowmeshtriangles * 3, numshadowmeshtriangles, NULL, NULL, NULL, false, false, true);
2962         for (j = 0, surf = loadmodel->brushq1.surfaces;j < loadmodel->brushq1.numsurfaces;j++, surf++)
2963                 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);
2964         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Finish(loadmodel->mempool, loadmodel->brush.shadowmesh, false, true);
2965         Mod_BuildTriangleNeighbors(loadmodel->brush.shadowmesh->neighbor3i, loadmodel->brush.shadowmesh->element3i, loadmodel->brush.shadowmesh->numtriangles);
2966         
2967         // LordHavoc: to clear the fog around the original quake submodel code, I
2968         // will explain:
2969         // first of all, some background info on the submodels:
2970         // model 0 is the map model (the world, named maps/e1m1.bsp for example)
2971         // model 1 and higher are submodels (doors and the like, named *1, *2, etc)
2972         // now the weird for loop itself:
2973         // the loop functions in an odd way, on each iteration it sets up the
2974         // current 'mod' model (which despite the confusing code IS the model of
2975         // the number i), at the end of the loop it duplicates the model to become
2976         // the next submodel, and loops back to set up the new submodel.
2977
2978         // LordHavoc: now the explanation of my sane way (which works identically):
2979         // set up the world model, then on each submodel copy from the world model
2980         // and set up the submodel with the respective model info.
2981         for (i = 0;i < mod->brush.numsubmodels;i++)
2982         {
2983                 // LordHavoc: this code was originally at the end of this loop, but
2984                 // has been transformed to something more readable at the start here.
2985
2986                 // LordHavoc: only register submodels if it is the world
2987                 // (prevents external bsp models from replacing world submodels with
2988                 //  their own)
2989                 if (loadmodel->isworldmodel && i)
2990                 {
2991                         char name[10];
2992                         // duplicate the basic information
2993                         sprintf(name, "*%i", i);
2994                         mod = Mod_FindName(name);
2995                         // copy the base model to this one
2996                         *mod = *loadmodel;
2997                         // rename the clone back to its proper name
2998                         strcpy(mod->name, name);
2999                         // textures and memory belong to the main model
3000                         mod->texturepool = NULL;
3001                         mod->mempool = NULL;
3002                 }
3003
3004                 bm = &mod->brushq1.submodels[i];
3005
3006                 mod->brushq1.hulls[0].firstclipnode = bm->headnode[0];
3007                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
3008                 {
3009                         mod->brushq1.hulls[j].firstclipnode = bm->headnode[j];
3010                         mod->brushq1.hulls[j].lastclipnode = mod->brushq1.numclipnodes - 1;
3011                 }
3012
3013                 mod->firstmodelsurface = bm->firstface;
3014                 mod->nummodelsurfaces = bm->numfaces;
3015
3016                 // make the model surface list (used by shadowing/lighting)
3017                 mod->surfacelist = Mem_Alloc(loadmodel->mempool, mod->nummodelsurfaces * sizeof(*mod->surfacelist));
3018                 for (j = 0;j < mod->nummodelsurfaces;j++)
3019                         mod->surfacelist[j] = mod->firstmodelsurface + j;
3020
3021                 // this gets altered below if sky is used
3022                 mod->DrawSky = NULL;
3023                 mod->Draw = R_Q1BSP_Draw;
3024                 mod->GetLightInfo = R_Q1BSP_GetLightInfo;
3025                 mod->DrawShadowVolume = R_Q1BSP_DrawShadowVolume;
3026                 mod->DrawLight = R_Q1BSP_DrawLight;
3027                 if (i != 0)
3028                 {
3029                         mod->brush.GetPVS = NULL;
3030                         mod->brush.FatPVS = NULL;
3031                         mod->brush.BoxTouchingPVS = NULL;
3032                         mod->brush.LightPoint = NULL;
3033                         mod->brush.AmbientSoundLevelsForPoint = NULL;
3034                 }
3035                 mod->brushq1.pvstexturechains = Mem_Alloc(loadmodel->mempool, mod->brushq1.numtextures * sizeof(msurface_t **));
3036                 mod->brushq1.pvstexturechainsbuffer = Mem_Alloc(loadmodel->mempool,(mod->nummodelsurfaces + mod->brushq1.numtextures) * sizeof(msurface_t *));
3037                 mod->brushq1.pvstexturechainslength = Mem_Alloc(loadmodel->mempool, mod->brushq1.numtextures * sizeof(int));
3038                 Mod_Q1BSP_BuildPVSTextureChains(mod);
3039                 Mod_Q1BSP_BuildLightmapUpdateChains(loadmodel->mempool, mod);
3040                 if (mod->nummodelsurfaces)
3041                 {
3042                         // LordHavoc: calculate bmodel bounding box rather than trusting what it says
3043                         mod->normalmins[0] = mod->normalmins[1] = mod->normalmins[2] = 1000000000.0f;
3044                         mod->normalmaxs[0] = mod->normalmaxs[1] = mod->normalmaxs[2] = -1000000000.0f;
3045                         modelyawradius = 0;
3046                         modelradius = 0;
3047                         for (j = 0, surf = &mod->brushq1.surfaces[mod->firstmodelsurface];j < mod->nummodelsurfaces;j++, surf++)
3048                         {
3049                                 // we only need to have a drawsky function if it is used(usually only on world model)
3050                                 if (surf->texinfo->texture->flags & SURF_DRAWSKY)
3051                                         mod->DrawSky = R_Q1BSP_DrawSky;
3052                                 // LordHavoc: submodels always clip, even if water
3053                                 if (mod->brush.numsubmodels - 1)
3054                                         surf->flags |= SURF_SOLIDCLIP;
3055                                 // calculate bounding shapes
3056                                 for (k = 0, vec = surf->mesh.data_vertex3f;k < surf->mesh.num_vertices;k++, vec += 3)
3057                                 {
3058                                         if (mod->normalmins[0] > vec[0]) mod->normalmins[0] = vec[0];
3059                                         if (mod->normalmins[1] > vec[1]) mod->normalmins[1] = vec[1];
3060                                         if (mod->normalmins[2] > vec[2]) mod->normalmins[2] = vec[2];
3061                                         if (mod->normalmaxs[0] < vec[0]) mod->normalmaxs[0] = vec[0];
3062                                         if (mod->normalmaxs[1] < vec[1]) mod->normalmaxs[1] = vec[1];
3063                                         if (mod->normalmaxs[2] < vec[2]) mod->normalmaxs[2] = vec[2];
3064                                         dist = vec[0]*vec[0]+vec[1]*vec[1];
3065                                         if (modelyawradius < dist)
3066                                                 modelyawradius = dist;
3067                                         dist += vec[2]*vec[2];
3068                                         if (modelradius < dist)
3069                                                 modelradius = dist;
3070                                 }
3071                         }
3072                         modelyawradius = sqrt(modelyawradius);
3073                         modelradius = sqrt(modelradius);
3074                         mod->yawmins[0] = mod->yawmins[1] = - (mod->yawmaxs[0] = mod->yawmaxs[1] = modelyawradius);
3075                         mod->yawmins[2] = mod->normalmins[2];
3076                         mod->yawmaxs[2] = mod->normalmaxs[2];
3077                         mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
3078                         mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
3079                         mod->radius = modelradius;
3080                         mod->radius2 = modelradius * modelradius;
3081                 }
3082                 else
3083                 {
3084                         // LordHavoc: empty submodel(lacrima.bsp has such a glitch)
3085                         Con_Printf("warning: empty submodel *%i in %s\n", i+1, loadmodel->name);
3086                 }
3087                 Mod_Q1BSP_BuildSurfaceNeighbors(mod->brushq1.surfaces + mod->firstmodelsurface, mod->nummodelsurfaces, loadmodel->mempool);
3088
3089                 mod->brushq1.num_visleafs = bm->visleafs;
3090         }
3091
3092         //Mod_Q1BSP_ProcessLightList();
3093
3094         if (developer.integer)
3095                 Con_Printf("Some stats for q1bsp model \"%s\": %i faces, %i nodes, %i leafs, %i visleafs, %i visleafportals\n", loadmodel->name, loadmodel->brushq1.numsurfaces, loadmodel->brushq1.numnodes, loadmodel->brushq1.num_leafs, loadmodel->brushq1.num_visleafs, loadmodel->brushq1.numportals);
3096 }
3097
3098 static void Mod_Q2BSP_LoadEntities(lump_t *l)
3099 {
3100 }
3101
3102 static void Mod_Q2BSP_LoadPlanes(lump_t *l)
3103 {
3104 /*
3105         d_t *in;
3106         m_t *out;
3107         int i, count;
3108
3109         in = (void *)(mod_base + l->fileofs);
3110         if (l->filelen % sizeof(*in))
3111                 Host_Error("Mod_Q2BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3112         count = l->filelen / sizeof(*in);
3113         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3114
3115         loadmodel-> = out;
3116         loadmodel->num = count;
3117
3118         for (i = 0;i < count;i++, in++, out++)
3119         {
3120         }
3121 */
3122 }
3123
3124 static void Mod_Q2BSP_LoadVertices(lump_t *l)
3125 {
3126 /*
3127         d_t *in;
3128         m_t *out;
3129         int i, count;
3130
3131         in = (void *)(mod_base + l->fileofs);
3132         if (l->filelen % sizeof(*in))
3133                 Host_Error("Mod_Q2BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3134         count = l->filelen / sizeof(*in);
3135         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3136
3137         loadmodel-> = out;
3138         loadmodel->num = count;
3139
3140         for (i = 0;i < count;i++, in++, out++)
3141         {
3142         }
3143 */
3144 }
3145
3146 static void Mod_Q2BSP_LoadVisibility(lump_t *l)
3147 {
3148 /*
3149         d_t *in;
3150         m_t *out;
3151         int i, count;
3152
3153         in = (void *)(mod_base + l->fileofs);
3154         if (l->filelen % sizeof(*in))
3155                 Host_Error("Mod_Q2BSP_LoadVisibility: funny lump size in %s",loadmodel->name);
3156         count = l->filelen / sizeof(*in);
3157         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3158
3159         loadmodel-> = out;
3160         loadmodel->num = count;
3161
3162         for (i = 0;i < count;i++, in++, out++)
3163         {
3164         }
3165 */
3166 }
3167
3168 static void Mod_Q2BSP_LoadNodes(lump_t *l)
3169 {
3170 /*
3171         d_t *in;
3172         m_t *out;
3173         int i, count;
3174
3175         in = (void *)(mod_base + l->fileofs);
3176         if (l->filelen % sizeof(*in))
3177                 Host_Error("Mod_Q2BSP_LoadNodes: funny lump size in %s",loadmodel->name);
3178         count = l->filelen / sizeof(*in);
3179         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3180
3181         loadmodel-> = out;
3182         loadmodel->num = count;
3183
3184         for (i = 0;i < count;i++, in++, out++)
3185         {
3186         }
3187 */
3188 }
3189
3190 static void Mod_Q2BSP_LoadTexInfo(lump_t *l)
3191 {
3192 /*
3193         d_t *in;
3194         m_t *out;
3195         int i, count;
3196
3197         in = (void *)(mod_base + l->fileofs);
3198         if (l->filelen % sizeof(*in))
3199                 Host_Error("Mod_Q2BSP_LoadTexInfo: funny lump size in %s",loadmodel->name);
3200         count = l->filelen / sizeof(*in);
3201         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3202
3203         loadmodel-> = out;
3204         loadmodel->num = count;
3205
3206         for (i = 0;i < count;i++, in++, out++)
3207         {
3208         }
3209 */
3210 }
3211
3212 static void Mod_Q2BSP_LoadFaces(lump_t *l)
3213 {
3214 /*
3215         d_t *in;
3216         m_t *out;
3217         int i, count;
3218
3219         in = (void *)(mod_base + l->fileofs);
3220         if (l->filelen % sizeof(*in))
3221                 Host_Error("Mod_Q2BSP_LoadFaces: funny lump size in %s",loadmodel->name);
3222         count = l->filelen / sizeof(*in);
3223         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3224
3225         loadmodel-> = out;
3226         loadmodel->num = count;
3227
3228         for (i = 0;i < count;i++, in++, out++)
3229         {
3230         }
3231 */
3232 }
3233
3234 static void Mod_Q2BSP_LoadLighting(lump_t *l)
3235 {
3236 /*
3237         d_t *in;
3238         m_t *out;
3239         int i, count;
3240
3241         in = (void *)(mod_base + l->fileofs);
3242         if (l->filelen % sizeof(*in))
3243                 Host_Error("Mod_Q2BSP_LoadLighting: funny lump size in %s",loadmodel->name);
3244         count = l->filelen / sizeof(*in);
3245         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3246
3247         loadmodel-> = out;
3248         loadmodel->num = count;
3249
3250         for (i = 0;i < count;i++, in++, out++)
3251         {
3252         }
3253 */
3254 }
3255
3256 static void Mod_Q2BSP_LoadLeafs(lump_t *l)
3257 {
3258 /*
3259         d_t *in;
3260         m_t *out;
3261         int i, count;
3262
3263         in = (void *)(mod_base + l->fileofs);
3264         if (l->filelen % sizeof(*in))
3265                 Host_Error("Mod_Q2BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
3266         count = l->filelen / sizeof(*in);
3267         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3268
3269         loadmodel-> = out;
3270         loadmodel->num = count;
3271
3272         for (i = 0;i < count;i++, in++, out++)
3273         {
3274         }
3275 */
3276 }
3277
3278 static void Mod_Q2BSP_LoadLeafFaces(lump_t *l)
3279 {
3280 /*
3281         d_t *in;
3282         m_t *out;
3283         int i, count;
3284
3285         in = (void *)(mod_base + l->fileofs);
3286         if (l->filelen % sizeof(*in))
3287                 Host_Error("Mod_Q2BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
3288         count = l->filelen / sizeof(*in);
3289         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3290
3291         loadmodel-> = out;
3292         loadmodel->num = count;
3293
3294         for (i = 0;i < count;i++, in++, out++)
3295         {
3296         }
3297 */
3298 }
3299
3300 static void Mod_Q2BSP_LoadLeafBrushes(lump_t *l)
3301 {
3302 /*
3303         d_t *in;
3304         m_t *out;
3305         int i, count;
3306
3307         in = (void *)(mod_base + l->fileofs);
3308         if (l->filelen % sizeof(*in))
3309                 Host_Error("Mod_Q2BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
3310         count = l->filelen / sizeof(*in);
3311         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3312
3313         loadmodel-> = out;
3314         loadmodel->num = count;
3315
3316         for (i = 0;i < count;i++, in++, out++)
3317         {
3318         }
3319 */
3320 }
3321
3322 static void Mod_Q2BSP_LoadEdges(lump_t *l)
3323 {
3324 /*
3325         d_t *in;
3326         m_t *out;
3327         int i, count;
3328
3329         in = (void *)(mod_base + l->fileofs);
3330         if (l->filelen % sizeof(*in))
3331                 Host_Error("Mod_Q2BSP_LoadEdges: funny lump size in %s",loadmodel->name);
3332         count = l->filelen / sizeof(*in);
3333         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3334
3335         loadmodel-> = out;
3336         loadmodel->num = count;
3337
3338         for (i = 0;i < count;i++, in++, out++)
3339         {
3340         }
3341 */
3342 }
3343
3344 static void Mod_Q2BSP_LoadSurfEdges(lump_t *l)
3345 {
3346 /*
3347         d_t *in;
3348         m_t *out;
3349         int i, count;
3350
3351         in = (void *)(mod_base + l->fileofs);
3352         if (l->filelen % sizeof(*in))
3353                 Host_Error("Mod_Q2BSP_LoadSurfEdges: funny lump size in %s",loadmodel->name);
3354         count = l->filelen / sizeof(*in);
3355         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3356
3357         loadmodel-> = out;
3358         loadmodel->num = count;
3359
3360         for (i = 0;i < count;i++, in++, out++)
3361         {
3362         }
3363 */
3364 }
3365
3366 static void Mod_Q2BSP_LoadBrushes(lump_t *l)
3367 {
3368 /*
3369         d_t *in;
3370         m_t *out;
3371         int i, count;
3372
3373         in = (void *)(mod_base + l->fileofs);
3374         if (l->filelen % sizeof(*in))
3375                 Host_Error("Mod_Q2BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3376         count = l->filelen / sizeof(*in);
3377         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3378
3379         loadmodel-> = out;
3380         loadmodel->num = count;
3381
3382         for (i = 0;i < count;i++, in++, out++)
3383         {
3384         }
3385 */
3386 }
3387
3388 static void Mod_Q2BSP_LoadBrushSides(lump_t *l)
3389 {
3390 /*
3391         d_t *in;
3392         m_t *out;
3393         int i, count;
3394
3395         in = (void *)(mod_base + l->fileofs);
3396         if (l->filelen % sizeof(*in))
3397                 Host_Error("Mod_Q2BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3398         count = l->filelen / sizeof(*in);
3399         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3400
3401         loadmodel-> = out;
3402         loadmodel->num = count;
3403
3404         for (i = 0;i < count;i++, in++, out++)
3405         {
3406         }
3407 */
3408 }
3409
3410 static void Mod_Q2BSP_LoadAreas(lump_t *l)
3411 {
3412 /*
3413         d_t *in;
3414         m_t *out;
3415         int i, count;
3416
3417         in = (void *)(mod_base + l->fileofs);
3418         if (l->filelen % sizeof(*in))
3419                 Host_Error("Mod_Q2BSP_LoadAreas: funny lump size in %s",loadmodel->name);
3420         count = l->filelen / sizeof(*in);
3421         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3422
3423         loadmodel-> = out;
3424         loadmodel->num = count;
3425
3426         for (i = 0;i < count;i++, in++, out++)
3427         {
3428         }
3429 */
3430 }
3431
3432 static void Mod_Q2BSP_LoadAreaPortals(lump_t *l)
3433 {
3434 /*
3435         d_t *in;
3436         m_t *out;
3437         int i, count;
3438
3439         in = (void *)(mod_base + l->fileofs);
3440         if (l->filelen % sizeof(*in))
3441                 Host_Error("Mod_Q2BSP_LoadAreaPortals: funny lump size in %s",loadmodel->name);
3442         count = l->filelen / sizeof(*in);
3443         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3444
3445         loadmodel-> = out;
3446         loadmodel->num = count;
3447
3448         for (i = 0;i < count;i++, in++, out++)
3449         {
3450         }
3451 */
3452 }
3453
3454 static void Mod_Q2BSP_LoadModels(lump_t *l)
3455 {
3456 /*
3457         d_t *in;
3458         m_t *out;
3459         int i, count;
3460
3461         in = (void *)(mod_base + l->fileofs);
3462         if (l->filelen % sizeof(*in))
3463                 Host_Error("Mod_Q2BSP_LoadModels: funny lump size in %s",loadmodel->name);
3464         count = l->filelen / sizeof(*in);
3465         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3466
3467         loadmodel-> = out;
3468         loadmodel->num = count;
3469
3470         for (i = 0;i < count;i++, in++, out++)
3471         {
3472         }
3473 */
3474 }
3475
3476 void static Mod_Q2BSP_Load(model_t *mod, void *buffer)
3477 {
3478         int i;
3479         q2dheader_t *header;
3480
3481         Host_Error("Mod_Q2BSP_Load: not yet implemented\n");
3482
3483         mod->type = mod_brushq2;
3484
3485         header = (q2dheader_t *)buffer;
3486
3487         i = LittleLong(header->version);
3488         if (i != Q2BSPVERSION)
3489                 Host_Error("Mod_Q2BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q2BSPVERSION);
3490         mod->brush.ishlbsp = false;
3491         if (loadmodel->isworldmodel)
3492         {
3493                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
3494                 // until we get a texture for it...
3495                 R_ResetQuakeSky();
3496         }
3497
3498         mod_base = (qbyte *)header;
3499
3500         // swap all the lumps
3501         for (i = 0;i < (int) sizeof(*header) / 4;i++)
3502                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
3503
3504         // store which lightmap format to use
3505         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3506
3507         Mod_Q2BSP_LoadEntities(&header->lumps[Q2LUMP_ENTITIES]);
3508         Mod_Q2BSP_LoadPlanes(&header->lumps[Q2LUMP_PLANES]);
3509         Mod_Q2BSP_LoadVertices(&header->lumps[Q2LUMP_VERTEXES]);
3510         Mod_Q2BSP_LoadVisibility(&header->lumps[Q2LUMP_VISIBILITY]);
3511         Mod_Q2BSP_LoadNodes(&header->lumps[Q2LUMP_NODES]);
3512         Mod_Q2BSP_LoadTexInfo(&header->lumps[Q2LUMP_TEXINFO]);
3513         Mod_Q2BSP_LoadFaces(&header->lumps[Q2LUMP_FACES]);
3514         Mod_Q2BSP_LoadLighting(&header->lumps[Q2LUMP_LIGHTING]);
3515         Mod_Q2BSP_LoadLeafs(&header->lumps[Q2LUMP_LEAFS]);
3516         Mod_Q2BSP_LoadLeafFaces(&header->lumps[Q2LUMP_LEAFFACES]);
3517         Mod_Q2BSP_LoadLeafBrushes(&header->lumps[Q2LUMP_LEAFBRUSHES]);
3518         Mod_Q2BSP_LoadEdges(&header->lumps[Q2LUMP_EDGES]);
3519         Mod_Q2BSP_LoadSurfEdges(&header->lumps[Q2LUMP_SURFEDGES]);
3520         Mod_Q2BSP_LoadBrushes(&header->lumps[Q2LUMP_BRUSHES]);
3521         Mod_Q2BSP_LoadBrushSides(&header->lumps[Q2LUMP_BRUSHSIDES]);
3522         Mod_Q2BSP_LoadAreas(&header->lumps[Q2LUMP_AREAS]);
3523         Mod_Q2BSP_LoadAreaPortals(&header->lumps[Q2LUMP_AREAPORTALS]);
3524         // LordHavoc: must go last because this makes the submodels
3525         Mod_Q2BSP_LoadModels(&header->lumps[Q2LUMP_MODELS]);
3526 }
3527
3528 static int Mod_Q3BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents);
3529 static int Mod_Q3BSP_NativeContentsFromSuperContents(model_t *model, int supercontents);
3530
3531 static void Mod_Q3BSP_LoadEntities(lump_t *l)
3532 {
3533         const char *data;
3534         char key[128], value[4096];
3535         float v[3];
3536         loadmodel->brushq3.num_lightgrid_cellsize[0] = 64;
3537         loadmodel->brushq3.num_lightgrid_cellsize[1] = 64;
3538         loadmodel->brushq3.num_lightgrid_cellsize[2] = 128;
3539         if (!l->filelen)
3540                 return;
3541         loadmodel->brush.entities = Mem_Alloc(loadmodel->mempool, l->filelen);
3542         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
3543         data = loadmodel->brush.entities;
3544         // some Q3 maps override the lightgrid_cellsize with a worldspawn key
3545         if (data && COM_ParseToken(&data, false) && com_token[0] == '{')
3546         {
3547                 while (1)
3548                 {
3549                         if (!COM_ParseToken(&data, false))
3550                                 break; // error
3551                         if (com_token[0] == '}')
3552                                 break; // end of worldspawn
3553                         if (com_token[0] == '_')
3554                                 strcpy(key, com_token + 1);
3555                         else
3556                                 strcpy(key, com_token);
3557                         while (key[strlen(key)-1] == ' ') // remove trailing spaces
3558                                 key[strlen(key)-1] = 0;
3559                         if (!COM_ParseToken(&data, false))
3560                                 break; // error
3561                         strcpy(value, com_token);
3562                         if (!strcmp("gridsize", key))
3563                         {
3564                                 if (sscanf(value, "%f %f %f", &v[0], &v[1], &v[2]) == 3 && v[0] != 0 && v[1] != 0 && v[2] != 0)
3565                                         VectorCopy(v, loadmodel->brushq3.num_lightgrid_cellsize);
3566                         }
3567                 }
3568         }
3569 }
3570
3571 static void Mod_Q3BSP_LoadTextures(lump_t *l)
3572 {
3573         q3dtexture_t *in;
3574         q3mtexture_t *out;
3575         int i, count;
3576         int j, c;
3577         fssearch_t *search;
3578         char *f;
3579         const char *text;
3580         int flags;
3581         char shadername[Q3PATHLENGTH];
3582         char sky[Q3PATHLENGTH];
3583
3584         in = (void *)(mod_base + l->fileofs);
3585         if (l->filelen % sizeof(*in))
3586                 Host_Error("Mod_Q3BSP_LoadTextures: funny lump size in %s",loadmodel->name);
3587         count = l->filelen / sizeof(*in);
3588         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3589
3590         loadmodel->brushq3.data_textures = out;
3591         loadmodel->brushq3.num_textures = count;
3592
3593         for (i = 0;i < count;i++, in++, out++)
3594         {
3595                 out->number = i;
3596                 strlcpy (out->name, in->name, sizeof (out->name));
3597                 out->surfaceflags = LittleLong(in->surfaceflags);
3598                 out->nativecontents = LittleLong(in->contents);
3599                 out->supercontents = Mod_Q3BSP_SuperContentsFromNativeContents(loadmodel, out->nativecontents);
3600                 Mod_LoadSkinFrame(&out->skin, out->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE, false, true, true);
3601                 out->surfaceparms = -1;
3602         }
3603
3604         // do a quick parse of shader files to get surfaceparms
3605         if ((search = FS_Search("scripts/*.shader", true, false)))
3606         {
3607                 for (i = 0;i < search->numfilenames;i++)
3608                 {
3609                         if ((f = FS_LoadFile(search->filenames[i], tempmempool, false)))
3610                         {
3611                                 text = f;
3612                                 while (COM_ParseToken(&text, false))
3613                                 {
3614                                         strlcpy (shadername, com_token, sizeof (shadername));
3615                                         flags = 0;
3616                                         sky[0] = 0;
3617                                         if (COM_ParseToken(&text, false) && !strcasecmp(com_token, "{"))
3618                                         {
3619                                                 while (COM_ParseToken(&text, false))
3620                                                 {
3621                                                         if (!strcasecmp(com_token, "}"))
3622                                                                 break;
3623                                                         else if (!strcasecmp(com_token, "{"))
3624                                                         {
3625                                                                 while (COM_ParseToken(&text, false))
3626                                                                 {
3627                                                                         if (!strcasecmp(com_token, "}"))
3628                                                                                 break;
3629                                                                 }
3630                                                         }
3631                                                         else if (!strcasecmp(com_token, "surfaceparm"))
3632                                                         {
3633                                                                 if (COM_ParseToken(&text, true) && strcasecmp(com_token, "\n"))
3634                                                                 {
3635                                                                         if (!strcasecmp(com_token, "alphashadow"))
3636                                                                                 flags |= Q3SURFACEPARM_ALPHASHADOW;
3637                                                                         else if (!strcasecmp(com_token, "areaportal"))
3638                                                                                 flags |= Q3SURFACEPARM_AREAPORTAL;
3639                                                                         else if (!strcasecmp(com_token, "clusterportal"))
3640                                                                                 flags |= Q3SURFACEPARM_CLUSTERPORTAL;
3641                                                                         else if (!strcasecmp(com_token, "detail"))
3642                                                                                 flags |= Q3SURFACEPARM_DETAIL;
3643                                                                         else if (!strcasecmp(com_token, "donotenter"))
3644                                                                                 flags |= Q3SURFACEPARM_DONOTENTER;
3645                                                                         else if (!strcasecmp(com_token, "fog"))
3646                                                                                 flags |= Q3SURFACEPARM_FOG;
3647                                                                         else if (!strcasecmp(com_token, "lava"))
3648                                                                                 flags |= Q3SURFACEPARM_LAVA;
3649                                                                         else if (!strcasecmp(com_token, "lightfilter"))
3650                                                                                 flags |= Q3SURFACEPARM_LIGHTFILTER;
3651                                                                         else if (!strcasecmp(com_token, "metalsteps"))
3652                                                                                 flags |= Q3SURFACEPARM_METALSTEPS;
3653                                                                         else if (!strcasecmp(com_token, "nodamage"))
3654                                                                                 flags |= Q3SURFACEPARM_NODAMAGE;
3655                                                                         else if (!strcasecmp(com_token, "nodlight"))
3656                                                                                 flags |= Q3SURFACEPARM_NODLIGHT;
3657                                                                         else if (!strcasecmp(com_token, "nodraw"))
3658                                                                                 flags |= Q3SURFACEPARM_NODRAW;
3659                                                                         else if (!strcasecmp(com_token, "nodrop"))
3660                                                                                 flags |= Q3SURFACEPARM_NODROP;
3661                                                                         else if (!strcasecmp(com_token, "noimpact"))
3662                                                                                 flags |= Q3SURFACEPARM_NOIMPACT;
3663                                                                         else if (!strcasecmp(com_token, "nolightmap"))
3664                                                                                 flags |= Q3SURFACEPARM_NOLIGHTMAP;
3665                                                                         else if (!strcasecmp(com_token, "nomarks"))
3666                                                                                 flags |= Q3SURFACEPARM_NOMARKS;
3667                                                                         else if (!strcasecmp(com_token, "nomipmaps"))
3668                                                                                 flags |= Q3SURFACEPARM_NOMIPMAPS;
3669                                                                         else if (!strcasecmp(com_token, "nonsolid"))
3670                                                                                 flags |= Q3SURFACEPARM_NONSOLID;
3671                                                                         else if (!strcasecmp(com_token, "origin"))
3672                                                                                 flags |= Q3SURFACEPARM_ORIGIN;
3673                                                                         else if (!strcasecmp(com_token, "playerclip"))
3674                                                                                 flags |= Q3SURFACEPARM_PLAYERCLIP;
3675                                                                         else if (!strcasecmp(com_token, "sky"))
3676                                                                                 flags |= Q3SURFACEPARM_SKY;
3677                                                                         else if (!strcasecmp(com_token, "slick"))
3678                                                                                 flags |= Q3SURFACEPARM_SLICK;
3679                                                                         else if (!strcasecmp(com_token, "slime"))
3680                                                                                 flags |= Q3SURFACEPARM_SLIME;
3681                                                                         else if (!strcasecmp(com_token, "structural"))
3682                                                                                 flags |= Q3SURFACEPARM_STRUCTURAL;
3683                                                                         else if (!strcasecmp(com_token, "trans"))
3684                                                                                 flags |= Q3SURFACEPARM_TRANS;
3685                                                                         else if (!strcasecmp(com_token, "water"))
3686                                                                                 flags |= Q3SURFACEPARM_WATER;
3687                                                                         else
3688                                                                                 Con_Printf("%s parsing warning: unknown surfaceparm \"%s\"\n", search->filenames[i], com_token);
3689                                                                         if (!COM_ParseToken(&text, true) || strcasecmp(com_token, "\n"))
3690                                                                         {
3691                                                                                 Con_Printf("%s parsing error: surfaceparm only takes one parameter.\n", search->filenames[i]);
3692                                                                                 goto parseerror;
3693                                                                         }
3694                                                                 }
3695                                                                 else
3696                                                                 {
3697                                                                         Con_Printf("%s parsing error: surfaceparm expects a parameter.\n", search->filenames[i]);
3698                                                                         goto parseerror;
3699                                                                 }
3700                                                         }
3701                                                         else if (!strcasecmp(com_token, "sky"))
3702                                                         {
3703                                                                 if (COM_ParseToken(&text, true) && strcasecmp(com_token, "\n"))
3704                                                                         if (strlen(com_token) < sizeof(sky))
3705                                                                                 strcpy(sky, com_token);
3706                                                         }
3707                                                         else if (!strcasecmp(com_token, "skyparms"))
3708                                                         {
3709                                                                 if (COM_ParseToken(&text, true) && strcasecmp(com_token, "\n"))
3710                                                                 {
3711                                                                         if (strlen(com_token) < sizeof(sky) && !atoi(com_token) && strcasecmp(com_token, "-"))
3712                                                                                 strcpy(sky, com_token);
3713                                                                         if (COM_ParseToken(&text, true) && strcasecmp(com_token, "\n"))
3714                                                                                 COM_ParseToken(&text, true);
3715                                                                 }
3716                                                         }
3717                                                         else
3718                                                         {
3719                                                                 // look for linebreak or }
3720                                                                 while(COM_ParseToken(&text, true) && strcasecmp(com_token, "\n") && strcasecmp(com_token, "}"));
3721                                                                 // break out to top level if it was }
3722                                                                 if (!strcasecmp(com_token, "}"))
3723                                                                         break;
3724                                                         }
3725                                                 }
3726                                                 // add shader to list (shadername and flags)
3727                                                 // actually here we just poke into the texture settings
3728                                                 for (j = 0, out = loadmodel->brushq3.data_textures;j < loadmodel->brushq3.num_textures;j++, out++)
3729                                                 {
3730                                                         if (!strcasecmp(out->name, shadername))
3731                                                         {
3732                                                                 out->surfaceparms = flags;
3733                                                                 if ((flags & Q3SURFACEPARM_SKY) && sky[0])
3734                                                                 {
3735                                                                         // quake3 seems to append a _ to the skybox name, so this must do so as well
3736                                                                         snprintf(loadmodel->brush.skybox, sizeof(loadmodel->brush.skybox), "%s_", sky);
3737                                                                 }
3738                                                         }
3739                                                 }
3740                                         }
3741                                         else
3742                                         {
3743                                                 Con_Printf("%s parsing error - expected \"{\", found \"%s\"\n", search->filenames[i], com_token);
3744                                                 goto parseerror;
3745                                         }
3746                                 }
3747 parseerror:
3748                                 Mem_Free(f);
3749                         }
3750                 }
3751         }
3752
3753         c = 0;
3754         for (j = 0, out = loadmodel->brushq3.data_textures;j < loadmodel->brushq3.num_textures;j++, out++)
3755         {
3756                 if (out->surfaceparms == -1)
3757                 {
3758                         c++;
3759                         Con_DPrintf("%s: No shader found for texture \"%s\"\n", loadmodel->name, out->name);
3760                         out->surfaceparms = 0;
3761                         // these are defaults
3762                         if (!strcmp(out->name, "caulk") || !strcmp(out->name, "common/caulk") || !strcmp(out->name, "textures/common/caulk")
3763                          || !strcmp(out->name, "nodraw") || !strcmp(out->name, "common/nodraw") || !strcmp(out->name, "textures/common/nodraw"))
3764                                 out->surfaceparms |= Q3SURFACEPARM_NODRAW;
3765                         if (!strncmp(out->name, "textures/skies/", 15))
3766                                 out->surfaceparms |= Q3SURFACEPARM_SKY;
3767                         if (R_TextureHasAlpha(out->skin.base))
3768                                 out->surfaceparms |= Q3SURFACEPARM_TRANS;
3769                 }
3770         }
3771         Con_DPrintf("%s: %i textures missing shaders\n", loadmodel->name, c);
3772 }
3773
3774 static void Mod_Q3BSP_LoadPlanes(lump_t *l)
3775 {
3776         q3dplane_t *in;
3777         mplane_t *out;
3778         int i, count;
3779
3780         in = (void *)(mod_base + l->fileofs);
3781         if (l->filelen % sizeof(*in))
3782                 Host_Error("Mod_Q3BSP_LoadPlanes: funny lump size in %s",loadmodel->name);
3783         count = l->filelen / sizeof(*in);
3784         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3785
3786         loadmodel->brushq3.data_planes = out;
3787         loadmodel->brushq3.num_planes = count;
3788
3789         for (i = 0;i < count;i++, in++, out++)
3790         {
3791                 out->normal[0] = LittleLong(in->normal[0]);
3792                 out->normal[1] = LittleLong(in->normal[1]);
3793                 out->normal[2] = LittleLong(in->normal[2]);
3794                 out->dist = LittleLong(in->dist);
3795                 PlaneClassify(out);
3796         }
3797 }
3798
3799 static void Mod_Q3BSP_LoadBrushSides(lump_t *l)
3800 {
3801         q3dbrushside_t *in;
3802         q3mbrushside_t *out;
3803         int i, n, count;
3804
3805         in = (void *)(mod_base + l->fileofs);
3806         if (l->filelen % sizeof(*in))
3807                 Host_Error("Mod_Q3BSP_LoadBrushSides: funny lump size in %s",loadmodel->name);
3808         count = l->filelen / sizeof(*in);
3809         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3810
3811         loadmodel->brushq3.data_brushsides = out;
3812         loadmodel->brushq3.num_brushsides = count;
3813
3814         for (i = 0;i < count;i++, in++, out++)
3815         {
3816                 n = LittleLong(in->planeindex);
3817                 if (n < 0 || n >= loadmodel->brushq3.num_planes)
3818                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid planeindex %i (%i planes)\n", n, loadmodel->brushq3.num_planes);
3819                 out->plane = loadmodel->brushq3.data_planes + n;
3820                 n = LittleLong(in->textureindex);
3821                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
3822                         Host_Error("Mod_Q3BSP_LoadBrushSides: invalid textureindex %i (%i textures)\n", n, loadmodel->brushq3.num_textures);
3823                 out->texture = loadmodel->brushq3.data_textures + n;
3824         }
3825 }
3826
3827 static void Mod_Q3BSP_LoadBrushes(lump_t *l)
3828 {
3829         q3dbrush_t *in;
3830         q3mbrush_t *out;
3831         int i, j, n, c, count, maxplanes;
3832         mplane_t *planes;
3833         winding_t *temp1, *temp2;
3834
3835         in = (void *)(mod_base + l->fileofs);
3836         if (l->filelen % sizeof(*in))
3837                 Host_Error("Mod_Q3BSP_LoadBrushes: funny lump size in %s",loadmodel->name);
3838         count = l->filelen / sizeof(*in);
3839         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3840
3841         loadmodel->brushq3.data_brushes = out;
3842         loadmodel->brushq3.num_brushes = count;
3843
3844         temp1 = Winding_New(64);
3845         temp2 = Winding_New(64);
3846
3847         maxplanes = 0;
3848         planes = NULL;
3849
3850         for (i = 0;i < count;i++, in++, out++)
3851         {
3852                 n = LittleLong(in->firstbrushside);
3853                 c = LittleLong(in->numbrushsides);
3854                 if (n < 0 || n + c > loadmodel->brushq3.num_brushsides)
3855                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid brushside range %i : %i (%i brushsides)\n", n, n + c, loadmodel->brushq3.num_brushsides);
3856                 out->firstbrushside = loadmodel->brushq3.data_brushsides + n;
3857                 out->numbrushsides = c;
3858                 n = LittleLong(in->textureindex);
3859                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
3860                         Host_Error("Mod_Q3BSP_LoadBrushes: invalid textureindex %i (%i textures)\n", n, loadmodel->brushq3.num_textures);
3861                 out->texture = loadmodel->brushq3.data_textures + n;
3862
3863                 // make a list of mplane_t structs to construct a colbrush from
3864                 if (maxplanes < out->numbrushsides)
3865                 {
3866                         maxplanes = out->numbrushsides;
3867                         if (planes)
3868                                 Mem_Free(planes);
3869                         planes = Mem_Alloc(tempmempool, sizeof(mplane_t) * maxplanes);
3870                 }
3871                 for (j = 0;j < out->numbrushsides;j++)
3872                 {
3873                         VectorCopy(out->firstbrushside[j].plane->normal, planes[j].normal);
3874                         planes[j].dist = out->firstbrushside[j].plane->dist;
3875                 }
3876                 // make the colbrush from the planes
3877                 out->colbrushf = Collision_NewBrushFromPlanes(loadmodel->mempool, out->numbrushsides, planes, out->texture->supercontents, temp1, temp2);
3878         }
3879         if (planes)
3880                 Mem_Free(planes);
3881         Winding_Free(temp1);
3882         Winding_Free(temp2);
3883 }
3884
3885 static void Mod_Q3BSP_LoadEffects(lump_t *l)
3886 {
3887         q3deffect_t *in;
3888         q3meffect_t *out;
3889         int i, n, count;
3890
3891         in = (void *)(mod_base + l->fileofs);
3892         if (l->filelen % sizeof(*in))
3893                 Host_Error("Mod_Q3BSP_LoadEffects: funny lump size in %s",loadmodel->name);
3894         count = l->filelen / sizeof(*in);
3895         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3896
3897         loadmodel->brushq3.data_effects = out;
3898         loadmodel->brushq3.num_effects = count;
3899
3900         for (i = 0;i < count;i++, in++, out++)
3901         {
3902                 strlcpy (out->shadername, in->shadername, sizeof (out->shadername));
3903                 n = LittleLong(in->brushindex);
3904                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
3905                         Host_Error("Mod_Q3BSP_LoadEffects: invalid brushindex %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
3906                 out->brush = loadmodel->brushq3.data_brushes + n;
3907                 out->unknown = LittleLong(in->unknown);
3908         }
3909 }
3910
3911 static void Mod_Q3BSP_LoadVertices(lump_t *l)
3912 {
3913         q3dvertex_t *in;
3914         int i, count;
3915
3916         in = (void *)(mod_base + l->fileofs);
3917         if (l->filelen % sizeof(*in))
3918                 Host_Error("Mod_Q3BSP_LoadVertices: funny lump size in %s",loadmodel->name);
3919         loadmodel->brushq3.num_vertices = count = l->filelen / sizeof(*in);
3920         loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, count * (sizeof(float) * (3 + 2 + 2 + 3 + 3 + 3 + 4)));
3921         loadmodel->brushq3.data_texcoordtexture2f = loadmodel->brushq3.data_vertex3f + count * 3;
3922         loadmodel->brushq3.data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordtexture2f + count * 2;
3923         loadmodel->brushq3.data_svector3f = loadmodel->brushq3.data_texcoordlightmap2f + count * 2;
3924         loadmodel->brushq3.data_tvector3f = loadmodel->brushq3.data_svector3f + count * 3;
3925         loadmodel->brushq3.data_normal3f = loadmodel->brushq3.data_tvector3f + count * 3;
3926         loadmodel->brushq3.data_color4f = loadmodel->brushq3.data_normal3f + count * 3;
3927
3928         for (i = 0;i < count;i++, in++)
3929         {
3930                 loadmodel->brushq3.data_vertex3f[i * 3 + 0] = LittleFloat(in->origin3f[0]);
3931                 loadmodel->brushq3.data_vertex3f[i * 3 + 1] = LittleFloat(in->origin3f[1]);
3932                 loadmodel->brushq3.data_vertex3f[i * 3 + 2] = LittleFloat(in->origin3f[2]);
3933                 loadmodel->brushq3.data_texcoordtexture2f[i * 2 + 0] = LittleFloat(in->texcoord2f[0]);
3934                 loadmodel->brushq3.data_texcoordtexture2f[i * 2 + 1] = LittleFloat(in->texcoord2f[1]);
3935                 loadmodel->brushq3.data_texcoordlightmap2f[i * 2 + 0] = LittleFloat(in->lightmap2f[0]);
3936                 loadmodel->brushq3.data_texcoordlightmap2f[i * 2 + 1] = LittleFloat(in->lightmap2f[1]);
3937                 // svector/tvector are calculated later in face loading
3938                 loadmodel->brushq3.data_svector3f[i * 3 + 0] = 0;
3939                 loadmodel->brushq3.data_svector3f[i * 3 + 1] = 0;
3940                 loadmodel->brushq3.data_svector3f[i * 3 + 2] = 0;
3941                 loadmodel->brushq3.data_tvector3f[i * 3 + 0] = 0;
3942                 loadmodel->brushq3.data_tvector3f[i * 3 + 1] = 0;
3943                 loadmodel->brushq3.data_tvector3f[i * 3 + 2] = 0;
3944                 loadmodel->brushq3.data_normal3f[i * 3 + 0] = LittleFloat(in->normal3f[0]);
3945                 loadmodel->brushq3.data_normal3f[i * 3 + 1] = LittleFloat(in->normal3f[1]);
3946                 loadmodel->brushq3.data_normal3f[i * 3 + 2] = LittleFloat(in->normal3f[2]);
3947                 loadmodel->brushq3.data_color4f[i * 4 + 0] = in->color4ub[0] * (1.0f / 255.0f);
3948                 loadmodel->brushq3.data_color4f[i * 4 + 1] = in->color4ub[1] * (1.0f / 255.0f);
3949                 loadmodel->brushq3.data_color4f[i * 4 + 2] = in->color4ub[2] * (1.0f / 255.0f);
3950                 loadmodel->brushq3.data_color4f[i * 4 + 3] = in->color4ub[3] * (1.0f / 255.0f);
3951         }
3952 }
3953
3954 static void Mod_Q3BSP_LoadTriangles(lump_t *l)
3955 {
3956         int *in;
3957         int *out;
3958         int i, count;
3959
3960         in = (void *)(mod_base + l->fileofs);
3961         if (l->filelen % sizeof(int[3]))
3962                 Host_Error("Mod_Q3BSP_LoadTriangles: funny lump size in %s",loadmodel->name);
3963         count = l->filelen / sizeof(*in);
3964         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out) * 2);
3965
3966         loadmodel->brushq3.num_triangles = count / 3;
3967         loadmodel->brushq3.data_element3i = out;
3968         loadmodel->brushq3.data_neighbor3i = out + count;
3969
3970         for (i = 0;i < count;i++, in++, out++)
3971         {
3972                 *out = LittleLong(*in);
3973                 if (*out < 0 || *out >= loadmodel->brushq3.num_vertices)
3974                 {
3975                         Con_Printf("Mod_Q3BSP_LoadTriangles: invalid vertexindex %i (%i vertices), setting to 0\n", *out, loadmodel->brushq3.num_vertices);
3976                         *out = 0;
3977                 }
3978         }
3979 }
3980
3981 static void Mod_Q3BSP_LoadLightmaps(lump_t *l)
3982 {
3983         q3dlightmap_t *in;
3984         rtexture_t **out;
3985         int i, count;
3986
3987         if (!l->filelen)
3988                 return;
3989         in = (void *)(mod_base + l->fileofs);
3990         if (l->filelen % sizeof(*in))
3991                 Host_Error("Mod_Q3BSP_LoadLightmaps: funny lump size in %s",loadmodel->name);
3992         count = l->filelen / sizeof(*in);
3993         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
3994
3995         loadmodel->brushq3.data_lightmaps = out;
3996         loadmodel->brushq3.num_lightmaps = count;
3997
3998         for (i = 0;i < count;i++, in++, out++)
3999                 *out = R_LoadTexture2D(loadmodel->texturepool, va("lightmap%04i", i), 128, 128, in->rgb, TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
4000 }
4001
4002 static void Mod_Q3BSP_LoadFaces(lump_t *l)
4003 {
4004         q3dface_t *in;
4005         q3msurface_t *out;
4006         int i, j, n, count, invalidelements, patchsize[2], finalwidth, finalheight, xlevel, ylevel, row0, row1, x, y, *e, finalvertices, finaltriangles;
4007         //int *originalelement3i;
4008         //int *originalneighbor3i;
4009         float *originalvertex3f;
4010         //float *originalsvector3f;
4011         //float *originaltvector3f;
4012         //float *originalnormal3f;
4013         float *originalcolor4f;
4014         float *originaltexcoordtexture2f;
4015         float *originaltexcoordlightmap2f;
4016         float *v;
4017
4018         in = (void *)(mod_base + l->fileofs);
4019         if (l->filelen % sizeof(*in))
4020                 Host_Error("Mod_Q3BSP_LoadFaces: funny lump size in %s",loadmodel->name);
4021         count = l->filelen / sizeof(*in);
4022         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4023
4024         loadmodel->brushq3.data_faces = out;
4025         loadmodel->brushq3.num_faces = count;
4026
4027         for (i = 0;i < count;i++, in++, out++)
4028         {
4029                 // check face type first
4030                 out->type = LittleLong(in->type);
4031                 if (out->type != Q3FACETYPE_POLYGON
4032                  && out->type != Q3FACETYPE_PATCH
4033                  && out->type != Q3FACETYPE_MESH
4034                  && out->type != Q3FACETYPE_FLARE)
4035                 {
4036                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i: unknown face type %i\n", i, out->type);
4037                         out->num_vertices = 0;
4038                         out->num_triangles = 0;
4039                         out->type = 0; // error
4040                         continue;
4041                 }
4042
4043                 n = LittleLong(in->textureindex);
4044                 if (n < 0 || n >= loadmodel->brushq3.num_textures)
4045                 {
4046                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i: invalid textureindex %i (%i textures)\n", i, n, loadmodel->brushq3.num_textures);
4047                         out->num_vertices = 0;
4048                         out->num_triangles = 0;
4049                         out->type = 0; // error
4050                         continue;
4051                         n = 0;
4052                 }
4053                 out->texture = loadmodel->brushq3.data_textures + n;
4054                 n = LittleLong(in->effectindex);
4055                 if (n < -1 || n >= loadmodel->brushq3.num_effects)
4056                 {
4057                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid effectindex %i (%i effects)\n", i, out->texture->name, n, loadmodel->brushq3.num_effects);
4058                         n = -1;
4059                 }
4060                 if (n == -1)
4061                         out->effect = NULL;
4062                 else
4063                         out->effect = loadmodel->brushq3.data_effects + n;
4064                 n = LittleLong(in->lightmapindex);
4065                 if (n < -1 || n >= loadmodel->brushq3.num_lightmaps)
4066                 {
4067                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid lightmapindex %i (%i lightmaps)\n", i, out->texture->name, n, loadmodel->brushq3.num_lightmaps);
4068                         n = -1;
4069                 }
4070                 if (n == -1)
4071                         out->lightmaptexture = NULL;
4072                 else
4073                         out->lightmaptexture = loadmodel->brushq3.data_lightmaps[n];
4074
4075                 out->firstvertex = LittleLong(in->firstvertex);
4076                 out->num_vertices = LittleLong(in->numvertices);
4077                 out->firstelement = LittleLong(in->firstelement);
4078                 out->num_triangles = LittleLong(in->numelements) / 3;
4079                 if (out->num_triangles * 3 != LittleLong(in->numelements))
4080                 {
4081                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): numelements %i is not a multiple of 3\n", i, out->texture->name, LittleLong(in->numelements));
4082                         out->num_vertices = 0;
4083                         out->num_triangles = 0;
4084                         out->type = 0; // error
4085                         continue;
4086                 }
4087                 if (out->firstvertex < 0 || out->firstvertex + out->num_vertices > loadmodel->brushq3.num_vertices)
4088                 {
4089                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid vertex range %i : %i (%i vertices)\n", i, out->texture->name, out->firstvertex, out->firstvertex + out->num_vertices, loadmodel->brushq3.num_vertices);
4090                         out->num_vertices = 0;
4091                         out->num_triangles = 0;
4092                         out->type = 0; // error
4093                         continue;
4094                 }
4095                 if (out->firstelement < 0 || out->firstelement + out->num_triangles * 3 > loadmodel->brushq3.num_triangles * 3)
4096                 {
4097                         Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid element range %i : %i (%i elements)\n", i, out->texture->name, out->firstelement, out->firstelement + out->num_triangles * 3, loadmodel->brushq3.num_triangles * 3);
4098                         out->num_vertices = 0;
4099                         out->num_triangles = 0;
4100                         out->type = 0; // error
4101                         continue;
4102                 }
4103                 switch(out->type)
4104                 {
4105                 case Q3FACETYPE_POLYGON:
4106                 case Q3FACETYPE_MESH:
4107                         // no processing necessary
4108                         out->data_vertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
4109                         out->data_texcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f + out->firstvertex * 2;
4110                         out->data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f + out->firstvertex * 2;
4111                         out->data_svector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
4112                         out->data_tvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
4113                         out->data_normal3f = loadmodel->brushq3.data_normal3f + out->firstvertex * 3;
4114                         out->data_color4f = loadmodel->brushq3.data_color4f + out->firstvertex * 4;
4115                         out->data_element3i = loadmodel->brushq3.data_element3i + out->firstelement;
4116                         out->data_neighbor3i = loadmodel->brushq3.data_neighbor3i + out->firstelement;
4117                         break;
4118                 case Q3FACETYPE_PATCH:
4119                         patchsize[0] = LittleLong(in->specific.patch.patchsize[0]);
4120                         patchsize[1] = LittleLong(in->specific.patch.patchsize[1]);
4121                         if (patchsize[0] < 1 || patchsize[1] < 1)
4122                         {
4123                                 Con_Printf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): invalid patchsize %ix%i\n", i, out->texture->name, patchsize[0], patchsize[1]);
4124                                 out->num_vertices = 0;
4125                                 out->num_triangles = 0;
4126                                 out->type = 0; // error
4127                                 continue;
4128                         }
4129                         originalvertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
4130                         //originalsvector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
4131                         //originaltvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
4132                         //originalnormal3f = loadmodel->brushq3.data_normal3f + out->firstvertex * 3;
4133                         originaltexcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f + out->firstvertex * 2;
4134                         originaltexcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f + out->firstvertex * 2;
4135                         originalcolor4f = loadmodel->brushq3.data_color4f + out->firstvertex * 4;
4136                         //originalelement3i = loadmodel->brushq3.data_element3i + out->firstelement;
4137                         //originalneighbor3i = loadmodel->brushq3.data_neighbor3i + out->firstelement;
4138                         /*
4139                         originalvertex3f = out->data_vertex3f;
4140                         //originalsvector3f = out->data_svector3f;
4141                         //originaltvector3f = out->data_tvector3f;
4142                         //originalnormal3f = out->data_normal3f;
4143                         originalcolor4f = out->data_color4f;
4144                         originaltexcoordtexture2f = out->data_texcoordtexture2f;
4145                         originaltexcoordlightmap2f = out->data_texcoordlightmap2f;
4146                         //originalelement3i = out->data_element3i;
4147                         //originalneighbor3i = out->data_neighbor3i;
4148                         */
4149                         // convert patch to Q3FACETYPE_MESH
4150                         xlevel = QuadraticSplinePatchSubdivisionLevelOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value, 10);
4151                         ylevel = QuadraticSplinePatchSubdivisionLevelOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value, 10);
4152                         // bound to user settings
4153                         xlevel = bound(r_subdivisions_minlevel.integer, xlevel, r_subdivisions_maxlevel.integer);
4154                         ylevel = bound(r_subdivisions_minlevel.integer, ylevel, r_subdivisions_maxlevel.integer);
4155                         // bound to sanity settings
4156                         xlevel = bound(0, xlevel, 10);
4157                         ylevel = bound(0, ylevel, 10);
4158                         // bound to user limit on vertices
4159                         while ((xlevel > 0 || ylevel > 0) && (((patchsize[0] - 1) << xlevel) + 1) * (((patchsize[1] - 1) << ylevel) + 1) > min(r_subdivisions_maxvertices.integer, 262144))
4160                         {
4161                                 if (xlevel > ylevel)
4162                                         xlevel--;
4163                                 else
4164                                         ylevel--;
4165                         }
4166                         finalwidth = ((patchsize[0] - 1) << xlevel) + 1;
4167                         finalheight = ((patchsize[1] - 1) << ylevel) + 1;
4168                         finalvertices = finalwidth * finalheight;
4169                         finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
4170                         out->data_vertex3f = Mem_Alloc(loadmodel->mempool, sizeof(float[20]) * finalvertices);
4171                         out->data_svector3f = out->data_vertex3f + finalvertices * 3;
4172                         out->data_tvector3f = out->data_svector3f + finalvertices * 3;
4173                         out->data_normal3f = out->data_tvector3f + finalvertices * 3;
4174                         out->data_color4f = out->data_normal3f + finalvertices * 3;
4175                         out->data_texcoordtexture2f = out->data_color4f + finalvertices * 4;
4176                         out->data_texcoordlightmap2f = out->data_texcoordtexture2f + finalvertices * 2;
4177                         out->data_element3i = Mem_Alloc(loadmodel->mempool, sizeof(int[6]) * finaltriangles);
4178                         out->data_neighbor3i = out->data_element3i + finaltriangles * 3;
4179                         out->type = Q3FACETYPE_MESH;
4180                         out->firstvertex = -1;
4181                         out->num_vertices = finalvertices;
4182                         out->firstelement = -1;
4183                         out->num_triangles = finaltriangles;
4184                         // generate geometry
4185                         // (note: normals are skipped because they get recalculated)
4186                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 3, originalvertex3f, out->data_vertex3f);
4187                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 2, originaltexcoordtexture2f, out->data_texcoordtexture2f);
4188                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 2, originaltexcoordlightmap2f, out->data_texcoordlightmap2f);
4189                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 4, originalcolor4f, out->data_color4f);
4190                         // generate elements
4191                         e = out->data_element3i;
4192                         for (y = 0;y < finalheight - 1;y++)
4193                         {
4194                                 row0 = (y + 0) * finalwidth;
4195                                 row1 = (y + 1) * finalwidth;
4196                                 for (x = 0;x < finalwidth - 1;x++)
4197                                 {
4198                                         *e++ = row0;
4199                                         *e++ = row1;
4200                                         *e++ = row0 + 1;
4201                                         *e++ = row1;
4202                                         *e++ = row1 + 1;
4203                                         *e++ = row0 + 1;
4204                                         row0++;
4205                                         row1++;
4206                                 }
4207                         }
4208                         out->num_triangles = Mod_RemoveDegenerateTriangles(out->num_triangles, out->data_element3i, out->data_element3i, out->data_vertex3f);
4209                         if (developer.integer)
4210                         {
4211                                 if (out->num_triangles < finaltriangles)
4212                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided to %i vertices / %i triangles, %i degenerate triangles removed (leaving %i)\n", patchsize[0], patchsize[1], out->num_vertices, finaltriangles, finaltriangles - out->num_triangles, out->num_triangles);
4213                                 else
4214                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided to %i vertices / %i triangles\n", patchsize[0], patchsize[1], out->num_vertices, out->num_triangles);
4215                         }
4216                         // q3map does not put in collision brushes for curves... ugh
4217                         // build the lower quality collision geometry
4218                         out->collisions = true;
4219                         xlevel = QuadraticSplinePatchSubdivisionLevelOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_collision_tolerance.value, 10);
4220                         ylevel = QuadraticSplinePatchSubdivisionLevelOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_collision_tolerance.value, 10);
4221                         // bound to user settings
4222                         xlevel = bound(r_subdivisions_collision_minlevel.integer, xlevel, r_subdivisions_collision_maxlevel.integer);
4223                         ylevel = bound(r_subdivisions_collision_minlevel.integer, ylevel, r_subdivisions_collision_maxlevel.integer);
4224                         // bound to sanity settings
4225                         xlevel = bound(0, xlevel, 10);
4226                         ylevel = bound(0, ylevel, 10);
4227                         // bound to user limit on vertices
4228                         while ((xlevel > 0 || ylevel > 0) && (((patchsize[0] - 1) << xlevel) + 1) * (((patchsize[1] - 1) << ylevel) + 1) > min(r_subdivisions_collision_maxvertices.integer, 262144))
4229                         {
4230                                 if (xlevel > ylevel)
4231                                         xlevel--;
4232                                 else
4233                                         ylevel--;
4234                         }
4235                         finalwidth = ((patchsize[0] - 1) << xlevel) + 1;
4236                         finalheight = ((patchsize[1] - 1) << ylevel) + 1;
4237                         finalvertices = finalwidth * finalheight;
4238                         finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
4239                         out->data_collisionvertex3f = Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * finalvertices);
4240                         out->data_collisionelement3i = Mem_Alloc(loadmodel->mempool, sizeof(int[3]) * finaltriangles);
4241                         out->num_collisionvertices = finalvertices;
4242                         out->num_collisiontriangles = finaltriangles;
4243                         QuadraticSplinePatchSubdivideFloatBuffer(patchsize[0], patchsize[1], xlevel, ylevel, 3, originalvertex3f, out->data_collisionvertex3f);
4244                         // generate elements
4245                         e = out->data_collisionelement3i;
4246                         for (y = 0;y < finalheight - 1;y++)
4247                         {
4248                                 row0 = (y + 0) * finalwidth;
4249                                 row1 = (y + 1) * finalwidth;
4250                                 for (x = 0;x < finalwidth - 1;x++)
4251                                 {
4252                                         *e++ = row0;
4253                                         *e++ = row1;
4254                                         *e++ = row0 + 1;
4255                                         *e++ = row1;
4256                                         *e++ = row1 + 1;
4257                                         *e++ = row0 + 1;
4258                                         row0++;
4259                                         row1++;
4260                                 }
4261                         }
4262                         out->num_collisiontriangles = Mod_RemoveDegenerateTriangles(out->num_collisiontriangles, out->data_collisionelement3i, out->data_collisionelement3i, out->data_collisionvertex3f);
4263                         if (developer.integer)
4264                         {
4265                                 if (out->num_collisiontriangles < finaltriangles)
4266                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided for collisions to %i vertices / %i triangles, %i degenerate triangles removed (leaving %i)\n", patchsize[0], patchsize[1], out->num_collisionvertices, finaltriangles, finaltriangles - out->num_collisiontriangles, out->num_collisiontriangles);
4267                                 else
4268                                         Con_Printf("Mod_Q3BSP_LoadFaces: %ix%i curve subdivided for collisions to %i vertices / %i triangles\n", patchsize[0], patchsize[1], out->num_collisionvertices, out->num_collisiontriangles);
4269                         }
4270                         break;
4271                 case Q3FACETYPE_FLARE:
4272                         Con_DPrintf("Mod_Q3BSP_LoadFaces: face #%i (texture \"%s\"): Q3FACETYPE_FLARE not supported (yet)\n", i, out->texture->name);
4273                         // don't render it
4274                         out->num_vertices = 0;
4275                         out->num_triangles = 0;
4276                         out->type = 0;
4277                         break;
4278                 }
4279                 for (j = 0, invalidelements = 0;j < out->num_triangles * 3;j++)
4280                         if (out->data_element3i[j] < 0 || out->data_element3i[j] >= out->num_vertices)
4281                                 invalidelements++;
4282                 if (invalidelements)
4283                 {
4284                         Con_Printf("Mod_Q3BSP_LoadFaces: Warning: face #%i has %i invalid elements, type = %i, texture->name = \"%s\", texture->surfaceflags = %i, texture->nativecontents = %i, firstvertex = %i, numvertices = %i, firstelement = %i, numelements = %i, elements list:\n", i, invalidelements, out->type, out->texture->name, out->texture->surfaceflags, out->texture->nativecontents, out->firstvertex, out->num_vertices, out->firstelement, out->num_triangles * 3);
4285                         for (j = 0;j < out->num_triangles * 3;j++)
4286                         {
4287                                 Con_Printf(" %i", out->data_element3i[j]);
4288                                 if (out->data_element3i[j] < 0 || out->data_element3i[j] >= out->num_vertices)
4289                                         out->data_element3i[j] = 0;
4290                         }
4291                         Con_Print("\n");
4292                 }
4293                 // for shadow volumes
4294                 Mod_BuildTriangleNeighbors(out->data_neighbor3i, out->data_element3i, out->num_triangles);
4295                 // for per pixel lighting
4296                 Mod_BuildTextureVectorsAndNormals(out->num_vertices, out->num_triangles, out->data_vertex3f, out->data_texcoordtexture2f, out->data_element3i, out->data_svector3f, out->data_tvector3f, out->data_normal3f);
4297                 // calculate a bounding box
4298                 VectorClear(out->mins);
4299                 VectorClear(out->maxs);
4300                 if (out->num_vertices)
4301                 {
4302                         VectorCopy(out->data_vertex3f, out->mins);
4303                         VectorCopy(out->data_vertex3f, out->maxs);
4304                         for (j = 1, v = out->data_vertex3f + 3;j < out->num_vertices;j++, v += 3)
4305                         {
4306                                 out->mins[0] = min(out->mins[0], v[0]);
4307                                 out->maxs[0] = max(out->maxs[0], v[0]);
4308                                 out->mins[1] = min(out->mins[1], v[1]);
4309                                 out->maxs[1] = max(out->maxs[1], v[1]);
4310                                 out->mins[2] = min(out->mins[2], v[2]);
4311                                 out->maxs[2] = max(out->maxs[2], v[2]);
4312                         }
4313                         out->mins[0] -= 1.0f;
4314                         out->mins[1] -= 1.0f;
4315                         out->mins[2] -= 1.0f;
4316                         out->maxs[0] += 1.0f;
4317                         out->maxs[1] += 1.0f;
4318                         out->maxs[2] += 1.0f;
4319                 }
4320         }
4321
4322         // LordHavoc: experimental array merger (disabled because it wastes time and uses 2x memory while merging)
4323         /*
4324         {
4325         int totalverts, totaltris;
4326         int originalnum_vertices;
4327         float *originaldata_vertex3f;
4328         float *originaldata_texcoordtexture2f;
4329         float *originaldata_texcoordlightmap2f;
4330         float *originaldata_svector3f;
4331         float *originaldata_tvector3f;
4332         float *originaldata_normal3f;
4333         float *originaldata_color4f;
4334         int originalnum_triangles;
4335         int *originaldata_element3i;
4336         int *originaldata_neighbor3i;
4337
4338         totalverts = 0;
4339         totaltris = 0;
4340         for (i = 0, out = loadmodel->brushq3.data_faces;i < count;i++, out++)
4341         {
4342                 if (!out->type)
4343                         continue;
4344                 totalverts += out->num_vertices;
4345                 totaltris += out->num_triangles;
4346         }
4347
4348         originalnum_vertices = loadmodel->brushq3.num_vertices;
4349         originaldata_vertex3f = loadmodel->brushq3.data_vertex3f;
4350         originaldata_texcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f;
4351         originaldata_texcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f;
4352         originaldata_svector3f = loadmodel->brushq3.data_svector3f;
4353         originaldata_tvector3f = loadmodel->brushq3.data_tvector3f;
4354         originaldata_normal3f = loadmodel->brushq3.data_normal3f;
4355         originaldata_color4f = loadmodel->brushq3.data_color4f;
4356         originalnum_triangles = loadmodel->brushq3.num_triangles;
4357         originaldata_element3i = loadmodel->brushq3.data_element3i;
4358         originaldata_neighbor3i = loadmodel->brushq3.data_neighbor3i;
4359         loadmodel->brushq3.num_vertices = totalverts;
4360         loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, totalverts * (sizeof(float) * (3 + 2 + 2 + 3 + 3 + 3 + 4)) + totaltris * (sizeof(int) * (3 * 2)));
4361         loadmodel->brushq3.data_texcoordtexture2f = loadmodel->brushq3.data_vertex3f + totalverts * 3;
4362         loadmodel->brushq3.data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordtexture2f + totalverts * 2;
4363         loadmodel->brushq3.data_svector3f = loadmodel->brushq3.data_texcoordlightmap2f + totalverts * 2;
4364         loadmodel->brushq3.data_tvector3f = loadmodel->brushq3.data_svector3f + totalverts * 3;
4365         loadmodel->brushq3.data_normal3f = loadmodel->brushq3.data_tvector3f + totalverts * 3;
4366         loadmodel->brushq3.data_color4f = loadmodel->brushq3.data_normal3f + totalverts * 3;
4367         loadmodel->brushq3.num_triangles = totaltris;
4368         loadmodel->brushq3.data_element3i = (int *)(loadmodel->brushq3.data_color4f + totalverts * 4);
4369         loadmodel->brushq3.data_neighbor3i = loadmodel->brushq3.data_element3i + totaltris * 3;
4370         totalverts = 0;
4371         totaltris = 0;
4372         for (i = 0, out = loadmodel->brushq3.data_faces;i < count;i++, out++)
4373         {
4374                 if (!out->type)
4375                         continue;
4376                 Con_Printf("totalverts %i, totaltris %i\n", totalverts, totaltris);
4377                 memcpy(loadmodel->brushq3.data_vertex3f + totalverts * 3, out->data_vertex3f, out->num_vertices * 3 * sizeof(float));
4378                 memcpy(loadmodel->brushq3.data_texcoordtexture2f + totalverts * 2, out->data_texcoordtexture2f, out->num_vertices * 2 * sizeof(float));
4379                 memcpy(loadmodel->brushq3.data_texcoordlightmap2f + totalverts * 2, out->data_texcoordlightmap2f, out->num_vertices * 2 * sizeof(float));
4380                 memcpy(loadmodel->brushq3.data_svector3f + totalverts * 3, out->data_svector3f, out->num_vertices * 3 * sizeof(float));
4381                 memcpy(loadmodel->brushq3.data_tvector3f + totalverts * 3, out->data_tvector3f, out->num_vertices * 3 * sizeof(float));
4382                 memcpy(loadmodel->brushq3.data_normal3f + totalverts * 3, out->data_normal3f, out->num_vertices * 3 * sizeof(float));
4383                 memcpy(loadmodel->brushq3.data_color4f + totalverts * 4, out->data_color4f, out->num_vertices * 4 * sizeof(float));
4384                 memcpy(loadmodel->brushq3.data_element3i + totaltris * 3, out->data_element3i, out->num_triangles * 3 * sizeof(int));
4385                 memcpy(loadmodel->brushq3.data_neighbor3i + totaltris * 3, out->data_neighbor3i, out->num_triangles * 3 * sizeof(int));
4386                 if (out->firstvertex == -1)
4387                         Mem_Free(out->data_vertex3f);
4388                 if (out->firstelement == -1)
4389                         Mem_Free(out->data_element3i);
4390                 out->firstvertex = totalverts;
4391                 out->data_vertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
4392                 out->data_texcoordtexture2f = loadmodel->brushq3.data_texcoordtexture2f + out->firstvertex * 2;
4393                 out->data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordlightmap2f + out->firstvertex * 2;
4394                 out->data_svector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
4395                 out->data_tvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
4396                 out->data_normal3f = loadmodel->brushq3.data_normal3f + out->firstvertex * 3;
4397                 out->data_color4f = loadmodel->brushq3.data_color4f + out->firstvertex * 4;
4398                 out->firstelement = totaltris * 3;
4399                 out->data_element3i = loadmodel->brushq3.data_element3i + out->firstelement;
4400                 out->data_neighbor3i = loadmodel->brushq3.data_neighbor3i + out->firstelement;
4401                 //for (j = 0;j < out->numtriangles * 3;j++)
4402                 //      out->data_element3i[j] += totalverts - out->firstvertex;
4403                 totalverts += out->num_vertices;
4404                 totaltris += out->num_triangles;
4405         }
4406         Mem_Free(originaldata_vertex3f);
4407         Mem_Free(originaldata_element3i);
4408         }
4409         */
4410 }
4411
4412 static void Mod_Q3BSP_LoadModels(lump_t *l)
4413 {
4414         q3dmodel_t *in;
4415         q3mmodel_t *out;
4416         int i, j, n, c, count;
4417
4418         in = (void *)(mod_base + l->fileofs);
4419         if (l->filelen % sizeof(*in))
4420                 Host_Error("Mod_Q3BSP_LoadModels: funny lump size in %s",loadmodel->name);
4421         count = l->filelen / sizeof(*in);
4422         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4423
4424         loadmodel->brushq3.data_models = out;
4425         loadmodel->brushq3.num_models = count;
4426
4427         for (i = 0;i < count;i++, in++, out++)
4428         {
4429                 for (j = 0;j < 3;j++)
4430                 {
4431                         out->mins[j] = LittleFloat(in->mins[j]);
4432                         out->maxs[j] = LittleFloat(in->maxs[j]);
4433                 }
4434                 n = LittleLong(in->firstface);
4435                 c = LittleLong(in->numfaces);
4436                 if (n < 0 || n + c > loadmodel->brushq3.num_faces)
4437                         Host_Error("Mod_Q3BSP_LoadModels: invalid face range %i : %i (%i faces)\n", n, n + c, loadmodel->brushq3.num_faces);
4438                 out->firstface = loadmodel->brushq3.data_faces + n;
4439                 out->numfaces = c;
4440                 n = LittleLong(in->firstbrush);
4441                 c = LittleLong(in->numbrushes);
4442                 if (n < 0 || n + c > loadmodel->brushq3.num_brushes)
4443                         Host_Error("Mod_Q3BSP_LoadModels: invalid brush range %i : %i (%i brushes)\n", n, n + c, loadmodel->brushq3.num_brushes);
4444                 out->firstbrush = loadmodel->brushq3.data_brushes + n;
4445                 out->numbrushes = c;
4446         }
4447 }
4448
4449 static void Mod_Q3BSP_LoadLeafBrushes(lump_t *l)
4450 {
4451         int *in;
4452         q3mbrush_t **out;
4453         int i, n, count;
4454
4455         in = (void *)(mod_base + l->fileofs);
4456         if (l->filelen % sizeof(*in))
4457                 Host_Error("Mod_Q3BSP_LoadLeafBrushes: funny lump size in %s",loadmodel->name);
4458         count = l->filelen / sizeof(*in);
4459         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4460
4461         loadmodel->brushq3.data_leafbrushes = out;
4462         loadmodel->brushq3.num_leafbrushes = count;
4463
4464         for (i = 0;i < count;i++, in++, out++)
4465         {
4466                 n = LittleLong(*in);
4467                 if (n < 0 || n >= loadmodel->brushq3.num_brushes)
4468                         Host_Error("Mod_Q3BSP_LoadLeafBrushes: invalid brush index %i (%i brushes)\n", n, loadmodel->brushq3.num_brushes);
4469                 *out = loadmodel->brushq3.data_brushes + n;
4470         }
4471 }
4472
4473 static void Mod_Q3BSP_LoadLeafFaces(lump_t *l)
4474 {
4475         int *in;
4476         q3msurface_t **out;
4477         int i, n, count;
4478
4479         in = (void *)(mod_base + l->fileofs);
4480         if (l->filelen % sizeof(*in))
4481                 Host_Error("Mod_Q3BSP_LoadLeafFaces: funny lump size in %s",loadmodel->name);
4482         count = l->filelen / sizeof(*in);
4483         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4484
4485         loadmodel->brushq3.data_leaffaces = out;
4486         loadmodel->brushq3.num_leaffaces = count;
4487
4488         for (i = 0;i < count;i++, in++, out++)
4489         {
4490                 n = LittleLong(*in);
4491                 if (n < 0 || n >= loadmodel->brushq3.num_faces)
4492                         Host_Error("Mod_Q3BSP_LoadLeafFaces: invalid face index %i (%i faces)\n", n, loadmodel->brushq3.num_faces);
4493                 *out = loadmodel->brushq3.data_faces + n;
4494         }
4495 }
4496
4497 static void Mod_Q3BSP_LoadLeafs(lump_t *l)
4498 {
4499         q3dleaf_t *in;
4500         q3mleaf_t *out;
4501         int i, j, n, c, count;
4502
4503         in = (void *)(mod_base + l->fileofs);
4504         if (l->filelen % sizeof(*in))
4505                 Host_Error("Mod_Q3BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
4506         count = l->filelen / sizeof(*in);
4507         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4508
4509         loadmodel->brushq3.data_leafs = out;
4510         loadmodel->brushq3.num_leafs = count;
4511
4512         for (i = 0;i < count;i++, in++, out++)
4513         {
4514                 out->parent = NULL;
4515                 out->plane = NULL;
4516                 out->clusterindex = LittleLong(in->clusterindex);
4517                 out->areaindex = LittleLong(in->areaindex);
4518                 for (j = 0;j < 3;j++)
4519                 {
4520                         // yes the mins/maxs are ints
4521                         out->mins[j] = LittleLong(in->mins[j]) - 1;
4522                         out->maxs[j] = LittleLong(in->maxs[j]) + 1;
4523                 }
4524                 n = LittleLong(in->firstleafface);
4525                 c = LittleLong(in->numleaffaces);
4526                 if (n < 0 || n + c > loadmodel->brushq3.num_leaffaces)
4527                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafface range %i : %i (%i leaffaces)\n", n, n + c, loadmodel->brushq3.num_leaffaces);
4528                 out->firstleafface = loadmodel->brushq3.data_leaffaces + n;
4529                 out->numleaffaces = c;
4530                 n = LittleLong(in->firstleafbrush);
4531                 c = LittleLong(in->numleafbrushes);
4532                 if (n < 0 || n + c > loadmodel->brushq3.num_leafbrushes)
4533                         Host_Error("Mod_Q3BSP_LoadLeafs: invalid leafbrush range %i : %i (%i leafbrushes)\n", n, n + c, loadmodel->brushq3.num_leafbrushes);
4534                 out->firstleafbrush = loadmodel->brushq3.data_leafbrushes + n;
4535                 out->numleafbrushes = c;
4536         }
4537 }
4538
4539 static void Mod_Q3BSP_LoadNodes_RecursiveSetParent(q3mnode_t *node, q3mnode_t *parent)
4540 {
4541         if (node->parent)
4542                 Host_Error("Mod_Q3BSP_LoadNodes_RecursiveSetParent: runaway recursion\n");
4543         node->parent = parent;
4544         if (node->plane)
4545         {
4546                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
4547                 Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
4548         }
4549 }
4550
4551 static void Mod_Q3BSP_LoadNodes(lump_t *l)
4552 {
4553         q3dnode_t *in;
4554         q3mnode_t *out;
4555         int i, j, n, count;
4556
4557         in = (void *)(mod_base + l->fileofs);
4558         if (l->filelen % sizeof(*in))
4559                 Host_Error("Mod_Q3BSP_LoadNodes: funny lump size in %s",loadmodel->name);
4560         count = l->filelen / sizeof(*in);
4561         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4562
4563         loadmodel->brushq3.data_nodes = out;
4564         loadmodel->brushq3.num_nodes = count;
4565
4566         for (i = 0;i < count;i++, in++, out++)
4567         {
4568                 out->parent = NULL;
4569                 n = LittleLong(in->planeindex);
4570                 if (n < 0 || n >= loadmodel->brushq3.num_planes)
4571                         Host_Error("Mod_Q3BSP_LoadNodes: invalid planeindex %i (%i planes)\n", n, loadmodel->brushq3.num_planes);
4572                 out->plane = loadmodel->brushq3.data_planes + n;
4573                 for (j = 0;j < 2;j++)
4574                 {
4575                         n = LittleLong(in->childrenindex[j]);
4576                         if (n >= 0)
4577                         {
4578                                 if (n >= loadmodel->brushq3.num_nodes)
4579                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child node index %i (%i nodes)\n", n, loadmodel->brushq3.num_nodes);
4580                                 out->children[j] = loadmodel->brushq3.data_nodes + n;
4581                         }
4582                         else
4583                         {
4584                                 n = -1 - n;
4585                                 if (n >= loadmodel->brushq3.num_leafs)
4586                                         Host_Error("Mod_Q3BSP_LoadNodes: invalid child leaf index %i (%i leafs)\n", n, loadmodel->brushq3.num_leafs);
4587                                 out->children[j] = (q3mnode_t *)(loadmodel->brushq3.data_leafs + n);
4588                         }
4589                 }
4590                 for (j = 0;j < 3;j++)
4591                 {
4592                         // yes the mins/maxs are ints
4593                         out->mins[j] = LittleLong(in->mins[j]) - 1;
4594                         out->maxs[j] = LittleLong(in->maxs[j]) + 1;
4595                 }
4596         }
4597
4598         // set the parent pointers
4599         Mod_Q3BSP_LoadNodes_RecursiveSetParent(loadmodel->brushq3.data_nodes, NULL);
4600 }
4601
4602 static void Mod_Q3BSP_LoadLightGrid(lump_t *l)
4603 {
4604         q3dlightgrid_t *in;
4605         q3dlightgrid_t *out;
4606         int count;
4607
4608         in = (void *)(mod_base + l->fileofs);
4609         if (l->filelen % sizeof(*in))
4610                 Host_Error("Mod_Q3BSP_LoadLightGrid: funny lump size in %s",loadmodel->name);
4611         loadmodel->brushq3.num_lightgrid_scale[0] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[0];
4612         loadmodel->brushq3.num_lightgrid_scale[1] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[1];
4613         loadmodel->brushq3.num_lightgrid_scale[2] = 1.0f / loadmodel->brushq3.num_lightgrid_cellsize[2];
4614         loadmodel->brushq3.num_lightgrid_imins[0] = ceil(loadmodel->brushq3.data_models->mins[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4615         loadmodel->brushq3.num_lightgrid_imins[1] = ceil(loadmodel->brushq3.data_models->mins[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4616         loadmodel->brushq3.num_lightgrid_imins[2] = ceil(loadmodel->brushq3.data_models->mins[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4617         loadmodel->brushq3.num_lightgrid_imaxs[0] = floor(loadmodel->brushq3.data_models->maxs[0] * loadmodel->brushq3.num_lightgrid_scale[0]);
4618         loadmodel->brushq3.num_lightgrid_imaxs[1] = floor(loadmodel->brushq3.data_models->maxs[1] * loadmodel->brushq3.num_lightgrid_scale[1]);
4619         loadmodel->brushq3.num_lightgrid_imaxs[2] = floor(loadmodel->brushq3.data_models->maxs[2] * loadmodel->brushq3.num_lightgrid_scale[2]);
4620         loadmodel->brushq3.num_lightgrid_isize[0] = loadmodel->brushq3.num_lightgrid_imaxs[0] - loadmodel->brushq3.num_lightgrid_imins[0] + 1;
4621         loadmodel->brushq3.num_lightgrid_isize[1] = loadmodel->brushq3.num_lightgrid_imaxs[1] - loadmodel->brushq3.num_lightgrid_imins[1] + 1;
4622         loadmodel->brushq3.num_lightgrid_isize[2] = loadmodel->brushq3.num_lightgrid_imaxs[2] - loadmodel->brushq3.num_lightgrid_imins[2] + 1;
4623         count = loadmodel->brushq3.num_lightgrid_isize[0] * loadmodel->brushq3.num_lightgrid_isize[1] * loadmodel->brushq3.num_lightgrid_isize[2];
4624         if (l->filelen)
4625         {
4626                 if (l->filelen < count * (int)sizeof(*in))
4627                         Host_Error("Mod_Q3BSP_LoadLightGrid: invalid lightgrid lump size %i bytes, should be %i bytes (%ix%ix%i)\n", l->filelen, count * sizeof(*in), loadmodel->brushq3.num_lightgrid_dimensions[0], loadmodel->brushq3.num_lightgrid_dimensions[1], loadmodel->brushq3.num_lightgrid_dimensions[2]);
4628                 if (l->filelen != count * (int)sizeof(*in))
4629                         Con_Printf("Mod_Q3BSP_LoadLightGrid: Warning: calculated lightgrid size %i bytes does not match lump size %i\n", count * sizeof(*in), l->filelen);
4630         }
4631
4632         out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
4633         loadmodel->brushq3.data_lightgrid = out;
4634         loadmodel->brushq3.num_lightgrid = count;
4635
4636         // no swapping or validation necessary
4637         if (l->filelen)
4638                 memcpy(out, in, count * (int)sizeof(*out));
4639         else
4640         {
4641                 // no data, fill with white
4642                 int i;
4643                 for (i = 0;i < count;i++)
4644                 {
4645                         out[i].ambientrgb[0] = 128;
4646                         out[i].ambientrgb[1] = 128;
4647                         out[i].ambientrgb[2] = 128;
4648                         out[i].diffusergb[0] = 0;
4649                         out[i].diffusergb[1] = 0;
4650                         out[i].diffusergb[2] = 0;
4651                         out[i].diffusepitch = 0;
4652                         out[i].diffuseyaw = 0;
4653                 }
4654         }
4655
4656         Matrix4x4_CreateScale3(&loadmodel->brushq3.num_lightgrid_indexfromworld, loadmodel->brushq3.num_lightgrid_scale[0], loadmodel->brushq3.num_lightgrid_scale[1], loadmodel->brushq3.num_lightgrid_scale[2]);
4657         Matrix4x4_ConcatTranslate(&loadmodel->brushq3.num_lightgrid_indexfromworld, -loadmodel->brushq3.num_lightgrid_imins[0] * loadmodel->brushq3.num_lightgrid_cellsize[0], -loadmodel->brushq3.num_lightgrid_imins[1] * loadmodel->brushq3.num_lightgrid_cellsize[1], -loadmodel->brushq3.num_lightgrid_imins[2] * loadmodel->brushq3.num_lightgrid_cellsize[2]);
4658 }
4659
4660 static void Mod_Q3BSP_LoadPVS(lump_t *l)
4661 {
4662         q3dpvs_t *in;
4663         int totalchains;
4664
4665         if (l->filelen == 0)
4666         {
4667                 int i;
4668                 // unvised maps often have cluster indices even without pvs, so check
4669                 // leafs to find real number of clusters
4670                 loadmodel->brush.num_pvsclusters = 1;
4671                 for (i = 0;i < loadmodel->brushq3.num_leafs;i++)
4672                         loadmodel->brush.num_pvsclusters = min(loadmodel->brush.num_pvsclusters, loadmodel->brushq3.data_leafs[i].clusterindex + 1);
4673
4674                 // create clusters
4675                 loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters + 7) / 8;
4676                 totalchains = loadmodel->brush.num_pvsclusterbytes * loadmodel->brush.num_pvsclusters;
4677                 loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, totalchains);
4678                 memset(loadmodel->brush.data_pvsclusters, 0xFF, totalchains);
4679                 return;
4680         }
4681
4682         in = (void *)(mod_base + l->fileofs);
4683         if (l->filelen < 9)
4684                 Host_Error("Mod_Q3BSP_LoadPVS: funny lump size in %s",loadmodel->name);
4685
4686         loadmodel->brush.num_pvsclusters = LittleLong(in->numclusters);
4687         loadmodel->brush.num_pvsclusterbytes = LittleLong(in->chainlength);
4688         if (loadmodel->brush.num_pvsclusterbytes < ((loadmodel->brush.num_pvsclusters + 7) / 8))
4689                 Host_Error("Mod_Q3BSP_LoadPVS: (chainlength = %i) < ((numclusters = %i) + 7) / 8\n", loadmodel->brush.num_pvsclusterbytes, loadmodel->brush.num_pvsclusters);
4690         totalchains = loadmodel->brush.num_pvsclusterbytes * loadmodel->brush.num_pvsclusters;
4691         if (l->filelen < totalchains + (int)sizeof(*in))
4692                 Host_Error("Mod_Q3BSP_LoadPVS: lump too small ((numclusters = %i) * (chainlength = %i) + sizeof(q3dpvs_t) == %i bytes, lump is %i bytes)\n", loadmodel->brush.num_pvsclusters, loadmodel->brush.num_pvsclusterbytes, totalchains + sizeof(*in), l->filelen);
4693
4694         loadmodel->brush.data_pvsclusters = Mem_Alloc(loadmodel->mempool, totalchains);
4695         memcpy(loadmodel->brush.data_pvsclusters, (qbyte *)(in + 1), totalchains);
4696 }
4697
4698 static void Mod_Q3BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, vec_t radius)
4699 {
4700         // FIXME: finish this code
4701         VectorCopy(in, out);
4702 }
4703
4704 static void Mod_Q3BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
4705 {
4706         int i, j, k, index[3];
4707         float transformed[3], blend1, blend2, blend, yaw, pitch, sinpitch;
4708         q3dlightgrid_t *a, *s;
4709         // FIXME: write this
4710         if (!model->brushq3.num_lightgrid)
4711         {
4712                 ambientcolor[0] = 1;
4713                 ambientcolor[1] = 1;
4714                 ambientcolor[2] = 1;
4715                 return;
4716         }
4717         Matrix4x4_Transform(&model->brushq3.num_lightgrid_indexfromworld, p, transformed);
4718         //Matrix4x4_Print(&model->brushq3.num_lightgrid_indexfromworld);
4719         //Con_Printf("%f %f %f transformed %f %f %f clamped ", p[0], p[1], p[2], transformed[0], transformed[1], transformed[2]);
4720         transformed[0] = bound(0, transformed[0], model->brushq3.num_lightgrid_isize[0] - 1);
4721         transformed[1] = bound(0, transformed[1], model->brushq3.num_lightgrid_isize[1] - 1);
4722         transformed[2] = bound(0, transformed[2], model->brushq3.num_lightgrid_isize[2] - 1);
4723         index[0] = (int)floor(transformed[0]);
4724         index[1] = (int)floor(transformed[1]);
4725         index[2] = (int)floor(transformed[2]);
4726         //Con_Printf("%f %f %f index %i %i %i:\n", transformed[0], transformed[1], transformed[2], index[0], index[1], index[2]);
4727         // now lerp the values
4728         VectorClear(diffusenormal);
4729         a = &model->brushq3.data_lightgrid[(index[2] * model->brushq3.num_lightgrid_isize[1] + index[1]) * model->brushq3.num_lightgrid_isize[0] + index[0]];
4730         for (k = 0;k < 2;k++)
4731         {
4732                 blend1 = (k ? (transformed[2] - index[2]) : (1 - (transformed[2] - index[2])));
4733                 if (blend1 < 0.001f || index[2] + k >= model->brushq3.num_lightgrid_isize[2])
4734                         continue;
4735                 for (j = 0;j < 2;j++)
4736                 {
4737                         blend2 = blend1 * (j ? (transformed[1] - index[1]) : (1 - (transformed[1] - index[1])));
4738                         if (blend2 < 0.001f || index[1] + j >= model->brushq3.num_lightgrid_isize[1])
4739                                 continue;
4740                         for (i = 0;i < 2;i++)
4741                         {
4742                                 blend = blend2 * (i ? (transformed[0] - index[0]) : (1 - (transformed[0] - index[0])));
4743                                 if (blend < 0.001f || index[0] + i >= model->brushq3.num_lightgrid_isize[0])
4744                                         continue;
4745                                 s = a + (k * model->brushq3.num_lightgrid_isize[1] + j) * model->brushq3.num_lightgrid_isize[0] + i;
4746                                 VectorMA(ambientcolor, blend * (1.0f / 128.0f), s->ambientrgb, ambientcolor);
4747                                 VectorMA(diffusecolor, blend * (1.0f / 128.0f), s->diffusergb, diffusecolor);
4748                                 pitch = s->diffusepitch * M_PI / 128;
4749                                 yaw = s->diffuseyaw * M_PI / 128;
4750                                 sinpitch = sin(pitch);
4751                                 diffusenormal[0] += blend * (cos(yaw) * sinpitch);
4752                                 diffusenormal[1] += blend * (sin(yaw) * sinpitch);
4753                                 diffusenormal[2] += blend * (cos(pitch));
4754                                 //Con_Printf("blend %f: ambient %i %i %i, diffuse %i %i %i, diffusepitch %i diffuseyaw %i (%f %f, normal %f %f %f)\n", blend, s->ambientrgb[0], s->ambientrgb[1], s->ambientrgb[2], s->diffusergb[0], s->diffusergb[1], s->diffusergb[2], s->diffusepitch, s->diffuseyaw, pitch, yaw, (cos(yaw) * cospitch), (sin(yaw) * cospitch), (-sin(pitch)));
4755                         }
4756                 }
4757         }
4758         VectorNormalize(diffusenormal);
4759         //Con_Printf("result: ambient %f %f %f diffuse %f %f %f diffusenormal %f %f %f\n", ambientcolor[0], ambientcolor[1], ambientcolor[2], diffusecolor[0], diffusecolor[1], diffusecolor[2], diffusenormal[0], diffusenormal[1], diffusenormal[2]);
4760 }
4761
4762 static void Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const vec3_t point, int markframe)
4763 {
4764         int i;
4765         q3mleaf_t *leaf;
4766         colbrushf_t *brush;
4767         // find which leaf the point is in
4768         while (node->plane)
4769                 node = node->children[DotProduct(point, node->plane->normal) < node->plane->dist];
4770         // point trace the brushes
4771         leaf = (q3mleaf_t *)node;
4772         for (i = 0;i < leaf->numleafbrushes;i++)
4773         {
4774                 brush = leaf->firstleafbrush[i]->colbrushf;
4775                 if (brush && brush->markframe != markframe && BoxesOverlap(point, point, brush->mins, brush->maxs))
4776                 {
4777                         brush->markframe = markframe;
4778                         Collision_TracePointBrushFloat(trace, point, leaf->firstleafbrush[i]->colbrushf);
4779                 }
4780         }
4781         // can't do point traces on curves (they have no thickness)
4782 }
4783
4784 static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const vec3_t start, const vec3_t end, vec_t startfrac, vec_t endfrac, const vec3_t linestart, const vec3_t lineend, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
4785 {
4786         int i, startside, endside;
4787         float dist1, dist2, midfrac, mid[3], nodesegmentmins[3], nodesegmentmaxs[3];
4788         q3mleaf_t *leaf;
4789         q3msurface_t *face;
4790         colbrushf_t *brush;
4791         if (startfrac > trace->realfraction)
4792                 return;
4793         // note: all line fragments past first impact fraction are ignored
4794         if (VectorCompare(start, end))
4795         {
4796                 // find which leaf the point is in
4797                 while (node->plane)
4798                         node = node->children[DotProduct(start, node->plane->normal) < node->plane->dist];
4799         }
4800         else
4801         {
4802                 // find which nodes the line is in and recurse for them
4803                 while (node->plane)
4804                 {
4805                         // recurse down node sides
4806                         dist1 = PlaneDiff(start, node->plane);
4807                         dist2 = PlaneDiff(end, node->plane);
4808                         startside = dist1 < 0;
4809                         endside = dist2 < 0;
4810                         if (startside == endside)
4811                         {
4812                                 // most of the time the line fragment is on one side of the plane
4813                                 node = node->children[startside];
4814                         }
4815                         else
4816                         {
4817                                 // line crosses node plane, split the line
4818                                 midfrac = dist1 / (dist1 - dist2);
4819                                 VectorLerp(start, midfrac, end, mid);
4820                                 // take the near side first
4821                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
4822                                 if (midfrac <= trace->realfraction)
4823                                         Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
4824                                 return;
4825                         }
4826                 }
4827         }
4828         // hit a leaf
4829         nodesegmentmins[0] = min(start[0], end[0]);
4830         nodesegmentmins[1] = min(start[1], end[1]);
4831         nodesegmentmins[2] = min(start[2], end[2]);
4832         nodesegmentmaxs[0] = max(start[0], end[0]);
4833         nodesegmentmaxs[1] = max(start[1], end[1]);
4834         nodesegmentmaxs[2] = max(start[2], end[2]);
4835         // line trace the brushes
4836         leaf = (q3mleaf_t *)node;
4837         for (i = 0;i < leaf->numleafbrushes;i++)
4838         {
4839                 brush = leaf->firstleafbrush[i]->colbrushf;
4840                 if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
4841                 {
4842                         brush->markframe = markframe;
4843                         Collision_TraceLineBrushFloat(trace, linestart, lineend, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
4844                         if (startfrac > trace->realfraction)
4845                                 return;
4846                 }
4847         }
4848         // can't do point traces on curves (they have no thickness)
4849         if (mod_q3bsp_curves_collisions.integer && !VectorCompare(start, end))
4850         {
4851                 // line trace the curves
4852                 for (i = 0;i < leaf->numleaffaces;i++)
4853                 {
4854                         face = leaf->firstleafface[i];
4855                         if (face->collisions && face->collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
4856                         {
4857                                 face->collisionmarkframe = markframe;
4858                                 Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
4859                                 if (startfrac > trace->realfraction)
4860                                         return;
4861                         }
4862                 }
4863         }
4864 }
4865
4866 static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
4867 {
4868         int i;
4869         //int sides;
4870         float nodesegmentmins[3], nodesegmentmaxs[3];
4871         q3mleaf_t *leaf;
4872         colbrushf_t *brush;
4873         q3msurface_t *face;
4874         /*
4875                 // find which nodes the line is in and recurse for them
4876                 while (node->plane)
4877                 {
4878                         // recurse down node sides
4879                         int startside, endside;
4880                         float dist1near, dist1far, dist2near, dist2far;
4881                         BoxPlaneCornerDistances(thisbrush_start->mins, thisbrush_start->maxs, node->plane, &dist1near, &dist1far);
4882                         BoxPlaneCornerDistances(thisbrush_end->mins, thisbrush_end->maxs, node->plane, &dist2near, &dist2far);
4883                         startside = dist1near < 0;
4884                         startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
4885                         endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
4886                         if (startside == 2 || endside == 2)
4887                         {
4888                                 // brushes cross plane
4889                                 // do not clip anything, just take both sides
4890                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4891                                 node = node->children[1];
4892                                 continue;
4893                         }
4894                         if (startside == 0)
4895                         {
4896                                 if (endside == 0)
4897                                 {
4898                                         node = node->children[0];
4899                                         continue;
4900                                 }
4901                                 else
4902                                 {
4903                                         //midf0 = dist1near / (dist1near - dist2near);
4904                                         //midf1 = dist1far / (dist1far - dist2far);
4905                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4906                                         node = node->children[1];
4907                                         continue;
4908                                 }
4909                         }
4910                         else
4911                         {
4912                                 if (endside == 0)
4913                                 {
4914                                         //midf0 = dist1near / (dist1near - dist2near);
4915                                         //midf1 = dist1far / (dist1far - dist2far);
4916                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
4917                                         node = node->children[1];
4918                                         continue;
4919                                 }
4920                                 else
4921                                 {
4922                                         node = node->children[1];
4923                                         continue;
4924                                 }
4925                         }
4926
4927                         if (dist1near <  0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4928                         if (dist1near <  0 && dist2near <  0 && dist1far <  0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4929                         if (dist1near <  0 && dist2near <  0 && dist1far >= 0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4930                         if (dist1near <  0 && dist2near <  0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4931                         if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4932                         if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){}
4933                         if (dist1near <  0 && dist2near >= 0 && dist1far >= 0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4934                         if (dist1near <  0 && dist2near >= 0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4935                         if (dist1near >= 0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
4936                         if (dist1near >= 0 && dist2near <  0 && dist1far <  0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4937                         if (dist1near >= 0 && dist2near <  0 && dist1far >= 0 && dist2far <  0){}
4938                         if (dist1near >= 0 && dist2near <  0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4939                         if (dist1near >= 0 && dist2near >= 0 && dist1far <  0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
4940                         if (dist1near >= 0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){node = node->children[0];continue;}
4941                         if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far <  0){node = node->children[0];continue;}
4942                         if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far >= 0){node = node->children[0];continue;}
4943                         {             
4944                                 if (dist2near < 0) // d1n<0 && d2n<0
4945                                 {
4946                                         if (dist2near < 0) // d1n<0 && d2n<0
4947                                         {
4948                                                 if (dist2near < 0) // d1n<0 && d2n<0
4949                                                 {
4950                                                 }
4951                                                 else // d1n<0 && d2n>0
4952                                                 {
4953                                                 }
4954                                         }
4955                                         else // d1n<0 && d2n>0
4956                                         {
4957                                                 if (dist2near < 0) // d1n<0 && d2n<0
4958                                                 {
4959                                                 }
4960                                                 else // d1n<0 && d2n>0
4961                                                 {
4962                                                 }
4963                                         }
4964                                 }
4965                                 else // d1n<0 && d2n>0
4966                                 {
4967                                 }
4968                         }
4969                         else // d1n>0
4970                         {
4971                                 if (dist2near < 0) // d1n>0 && d2n<0
4972                                 {
4973                                 }
4974                                 else // d1n>0 && d2n>0
4975                                 {
4976                                 }
4977                         }
4978                         if (dist1near < 0 == dist1far < 0 == dist2near < 0 == dist2far < 0)
4979                         {
4980                                 node = node->children[startside];
4981                                 continue;
4982                         }
4983                         if (dist1near < dist2near)
4984                         {
4985                                 // out
4986                                 if (dist1near >= 0)
4987                                 {
4988                                         node = node->children[0];
4989                                         continue;
4990                                 }
4991                                 if (dist2far < 0)
4992                                 {
4993                                         node = node->children[1];
4994                                         continue;
4995                                 }
4996                                 // dist1near < 0 && dist2far >= 0
4997                         }
4998                         else
4999                         {
5000                                 // in
5001                         }
5002                         startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
5003                         endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
5004                         if (startside == 2 || endside == 2)
5005                         {
5006                                 // brushes cross plane
5007                                 // do not clip anything, just take both sides
5008                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5009                                 node = node->children[1];
5010                         }
5011                         else if (startside == endside)
5012                                 node = node->children[startside];
5013                         else if (startside == 0) // endside = 1 (start infront, end behind)
5014                         {
5015                         }
5016                         else // startside == 1 endside = 0 (start behind, end infront)
5017                         {
5018                         }
5019                         == endside)
5020                         {
5021                                 if (startside < 2)
5022                                         node = node->children[startside];
5023                                 else
5024                                 {
5025                                         // start and end brush cross plane
5026                                 }
5027                         }
5028                         else
5029                         {
5030                         }
5031                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5032                                 node = node->children[1];
5033                         else if (dist1near < 0 && dist1far < 0 && dist2near >= 0 && dist2far >= 0)
5034                         else if (dist1near >= 0 && dist1far >= 0 && dist2near < 0 && dist2far < 0)
5035                         else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
5036                                 node = node->children[0];
5037                         else
5038                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5039                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5040                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5041                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5042                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5043                         {
5044                         }
5045                         else if (dist1near >= 0 && dist1far >= 0)
5046                         {
5047                         }
5048                         else // mixed (lying on plane)
5049                         {
5050                         }
5051                         {
5052                                 if (dist2near < 0 && dist2far < 0)
5053                                 {
5054                                 }
5055                                 else
5056                                         node = node->children[1];
5057                         }
5058                         if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
5059                                 node = node->children[0];
5060                         else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
5061                                 node = node->children[1];
5062                         else
5063                         {
5064                                 // both sides
5065                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5066                                 node = node->children[1];
5067                         }
5068                         sides = dist1near || dist1near < 0 | dist1far < 0 | dist2near < 0 | dist
5069                         startside = dist1 < 0;
5070                         endside = dist2 < 0;
5071                         if (startside == endside)
5072                         {
5073                                 // most of the time the line fragment is on one side of the plane
5074                                 node = node->children[startside];
5075                         }
5076                         else
5077                         {
5078                                 // line crosses node plane, split the line
5079                                 midfrac = dist1 / (dist1 - dist2);
5080                                 VectorLerp(start, midfrac, end, mid);
5081                                 // take the near side first
5082                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5083                                 if (midfrac <= trace->fraction)
5084                                         Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
5085                                 return;
5086                         }
5087                 }
5088         */
5089 #if 1
5090         for (;;)
5091         {
5092                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5093                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5094                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5095                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5096                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5097                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5098                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5099                         return;
5100                 if (!node->plane)
5101                         break;
5102                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5103                 node = node->children[1];
5104         }
5105 #elif 0
5106         // FIXME: could be made faster by copying TraceLine code and making it use
5107         // box plane distances...  (variant on the BoxOnPlaneSide code)
5108         for (;;)
5109         {
5110                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5111                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5112                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5113                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5114                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5115                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5116                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5117                         return;
5118                 if (!node->plane)
5119                         break;
5120                 if (mod_q3bsp_debugtracebrush.integer == 2)
5121                 {
5122                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5123                         node = node->children[1];
5124                         continue;
5125                 }
5126                 else if (mod_q3bsp_debugtracebrush.integer == 1)
5127                 {
5128                         // recurse down node sides
5129                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5130                         if (sides == 3)
5131                         {
5132                                 // segment box crosses plane
5133                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5134                                 node = node->children[1];
5135                                 continue;
5136                         }
5137                         // take whichever side the segment box is on
5138                         node = node->children[sides - 1];
5139                         continue;
5140                 }
5141                 else
5142                 {
5143                         // recurse down node sides
5144                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5145                         if (sides == 3)
5146                         {
5147                                 // segment box crosses plane
5148                                 // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
5149                                 sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, node->plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, node->plane);
5150                                 if (sides == 3)
5151                                 {
5152                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5153                                         node = node->children[1];
5154                                         continue;
5155                                 }
5156                         }
5157                         // take whichever side the segment box is on
5158                         node = node->children[sides - 1];
5159                         continue;
5160                 }
5161                 return;
5162         }
5163 #else
5164         // FIXME: could be made faster by copying TraceLine code and making it use
5165         // box plane distances...  (variant on the BoxOnPlaneSide code)
5166         for (;;)
5167         {
5168                 nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
5169                 nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
5170                 nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
5171                 nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
5172                 nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
5173                 nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
5174                 if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
5175                         return;
5176                 if (!node->plane)
5177                         break;
5178                 if (mod_q3bsp_debugtracebrush.integer == 2)
5179                 {
5180                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5181                         node = node->children[1];
5182                 }
5183                 else if (mod_q3bsp_debugtracebrush.integer == 1)
5184                 {
5185                         // recurse down node sides
5186                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5187                         if (sides == 3)
5188                         {
5189                                 // segment box crosses plane
5190                                 Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5191                                 node = node->children[1];
5192                         }
5193                         else
5194                         {
5195                                 // take whichever side the segment box is on
5196                                 node = node->children[sides - 1];
5197                         }
5198                 }
5199                 else
5200                 {
5201                         // recurse down node sides
5202                         sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, node->plane);
5203                         if (sides == 3)
5204                         {
5205                                 // segment box crosses plane
5206                                 // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
5207                                 sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, node->plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, node->plane);
5208                                 if (sides == 3)
5209                                 {
5210                                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
5211                                         sides = 2;
5212                                 }
5213                         }
5214                         // take whichever side the segment box is on
5215                         node = node->children[sides - 1];
5216                 }
5217         }
5218 #endif
5219         // hit a leaf
5220         leaf = (q3mleaf_t *)node;
5221         for (i = 0;i < leaf->numleafbrushes;i++)
5222         {
5223                 brush = leaf->firstleafbrush[i]->colbrushf;
5224                 if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
5225                 {
5226                         brush->markframe = markframe;
5227                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
5228                 }
5229         }
5230         if (mod_q3bsp_curves_collisions.integer)
5231         {
5232                 for (i = 0;i < leaf->numleaffaces;i++)
5233                 {
5234                         face = leaf->firstleafface[i];
5235                         if (face->collisions && face->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
5236                         {
5237                                 face->markframe = markframe;
5238                                 Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5239                         }
5240                 }
5241         }
5242 }
5243
5244 static void Mod_Q3BSP_TraceBox(model_t *model, int frame, trace_t *trace, const vec3_t boxstartmins, const vec3_t boxstartmaxs, const vec3_t boxendmins, const vec3_t boxendmaxs, int hitsupercontentsmask)
5245 {
5246         int i;
5247         float segmentmins[3], segmentmaxs[3];
5248         colbrushf_t *thisbrush_start, *thisbrush_end;
5249         matrix4x4_t startmatrix, endmatrix;
5250         static int markframe = 0;
5251         q3msurface_t *face;
5252         memset(trace, 0, sizeof(*trace));
5253         trace->fraction = 1;
5254         trace->realfraction = 1;
5255         trace->hitsupercontentsmask = hitsupercontentsmask;
5256         Matrix4x4_CreateIdentity(&startmatrix);
5257         Matrix4x4_CreateIdentity(&endmatrix);
5258         segmentmins[0] = min(boxstartmins[0], boxendmins[0]);
5259         segmentmins[1] = min(boxstartmins[1], boxendmins[1]);
5260         segmentmins[2] = min(boxstartmins[2], boxendmins[2]);
5261         segmentmaxs[0] = max(boxstartmaxs[0], boxendmaxs[0]);
5262         segmentmaxs[1] = max(boxstartmaxs[1], boxendmaxs[1]);
5263         segmentmaxs[2] = max(boxstartmaxs[2], boxendmaxs[2]);
5264         if (mod_q3bsp_optimizedtraceline.integer && VectorCompare(boxstartmins, boxstartmaxs) && VectorCompare(boxendmins, boxendmaxs))
5265         {
5266                 if (VectorCompare(boxstartmins, boxendmins))
5267                 {
5268                         // point trace
5269                         if (model->brushq3.submodel)
5270                         {
5271                                 for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
5272                                         if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
5273                                                 Collision_TracePointBrushFloat(trace, boxstartmins, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
5274                         }
5275                         else
5276                                 Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace, model->brushq3.data_nodes, boxstartmins, ++markframe);
5277                 }
5278                 else
5279                 {
5280                         // line trace
5281                         if (model->brushq3.submodel)
5282                         {
5283                                 for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
5284                                         if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
5285                                                 Collision_TraceLineBrushFloat(trace, boxstartmins, boxendmins, model->brushq3.data_thismodel->firstbrush[i].colbrushf, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
5286                                 if (mod_q3bsp_curves_collisions.integer)
5287                                 {
5288                                         for (i = 0;i < model->brushq3.data_thismodel->numfaces;i++)
5289                                         {
5290                                                 face = model->brushq3.data_thismodel->firstface + i;
5291                                                 if (face->collisions)
5292                                                         Collision_TraceLineTriangleMeshFloat(trace, boxstartmins, boxendmins, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5293                                         }
5294                                 }
5295                         }
5296                         else
5297                                 Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model->brushq3.data_nodes, boxstartmins, boxendmins, 0, 1, boxstartmins, boxendmins, ++markframe, segmentmins, segmentmaxs);
5298                 }
5299         }
5300         else
5301         {
5302                 // box trace, performed as brush trace
5303                 thisbrush_start = Collision_BrushForBox(&startmatrix, boxstartmins, boxstartmaxs);
5304                 thisbrush_end = Collision_BrushForBox(&endmatrix, boxendmins, boxendmaxs);
5305                 if (model->brushq3.submodel)
5306                 {
5307                         for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
5308                                 if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
5309                                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, model->brushq3.data_thismodel->firstbrush[i].colbrushf, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
5310                         if (mod_q3bsp_curves_collisions.integer)
5311                         {
5312                                 for (i = 0;i < model->brushq3.data_thismodel->numfaces;i++)
5313                                 {
5314                                         face = model->brushq3.data_thismodel->firstface + i;
5315                                         if (face->collisions)
5316                                                 Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->num_collisiontriangles, face->data_collisionelement3i, face->data_collisionvertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
5317                                 }
5318                         }
5319                 }
5320                 else
5321                         Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model->brushq3.data_nodes, thisbrush_start, thisbrush_end, ++markframe, segmentmins, segmentmaxs);
5322         }
5323 }
5324
5325 static int Mod_Q3BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
5326 {
5327         int clusterindex, side, nodestackindex = 0;
5328         q3mnode_t *node, *nodestack[1024];
5329         node = model->brushq3.data_nodes;
5330         if (!model->brush.num_pvsclusters)
5331                 return true;
5332         for (;;)
5333         {
5334                 if (node->plane)
5335                 {
5336                         // node - recurse down the BSP tree
5337                         side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
5338                         if (side < 2)
5339                         {
5340                                 // box is on one side of plane, take that path
5341                                 node = node->children[side];
5342                         }
5343                         else
5344                         {
5345                                 // box crosses plane, take one path and remember the other
5346                                 nodestack[nodestackindex++] = node->children[0];
5347                                 node = node->children[1];
5348                         }
5349                 }
5350                 else
5351                 {
5352                         // leaf - check cluster bit
5353                         clusterindex = ((q3mleaf_t *)node)->clusterindex;
5354 #if 0
5355                         if (clusterindex >= model->brush.num_pvsclusters)
5356                         {
5357                                 Con_Printf("%i >= %i\n", clusterindex, model->brush.num_pvsclusters);
5358                                 return true;
5359                         }
5360 #endif
5361                         if (CHECKPVSBIT(pvs, clusterindex))
5362                         {
5363                                 // it is visible, return immediately with the news
5364                                 return true;
5365                         }
5366                         else
5367                         {
5368                                 // nothing to see here, try another path we didn't take earlier
5369                                 if (nodestackindex == 0)
5370                                         break;
5371                                 node = nodestack[--nodestackindex];
5372                         }
5373                 }
5374         }
5375         // it is not visible
5376         return false;
5377 }
5378
5379 //Returns PVS data for a given point
5380 //(note: can return NULL)
5381 static qbyte *Mod_Q3BSP_GetPVS(model_t *model, const vec3_t p)
5382 {
5383         q3mnode_t *node;
5384         Mod_CheckLoaded(model);
5385         node = model->brushq3.data_nodes;
5386         while (node->plane)
5387                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
5388         if (((q3mleaf_t *)node)->clusterindex >= 0)
5389                 return model->brush.data_pvsclusters + ((q3mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
5390         else
5391                 return NULL;
5392 }
5393
5394 static void Mod_Q3BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbytes, q3mnode_t *node)
5395 {
5396         while (node->plane)
5397         {
5398                 float d = PlaneDiff(org, node->plane);
5399                 if (d > radius)
5400                         node = node->children[0];
5401                 else if (d < -radius)
5402                         node = node->children[1];
5403                 else
5404                 {
5405                         // go down both sides
5406                         Mod_Q3BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
5407                         node = node->children[1];
5408                 }
5409         }
5410         // if this leaf is in a cluster, accumulate the pvs bits
5411         if (((q3mleaf_t *)node)->clusterindex >= 0)
5412         {
5413                 int i;
5414                 qbyte *pvs = model->brush.data_pvsclusters + ((q3mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
5415                 for (i = 0;i < pvsbytes;i++)
5416                         pvsbuffer[i] |= pvs[i];
5417         }
5418 }
5419
5420 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
5421 //of the given point.
5422 static int Mod_Q3BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyte *pvsbuffer, int pvsbufferlength)
5423 {
5424         int bytes = model->brush.num_pvsclusterbytes;
5425         bytes = min(bytes, pvsbufferlength);
5426         if (r_novis.integer || !model->brush.num_pvsclusters || !Mod_Q3BSP_GetPVS(model, org))
5427         {
5428                 memset(pvsbuffer, 0xFF, bytes);
5429                 return bytes;
5430         }
5431         memset(pvsbuffer, 0, bytes);
5432         Mod_Q3BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brushq3.data_nodes);
5433         return bytes;
5434 }
5435
5436
5437 static int Mod_Q3BSP_SuperContentsFromNativeContents(model_t *model, int nativecontents)
5438 {
5439         int supercontents = 0;
5440         if (nativecontents & Q2CONTENTS_SOLID)
5441                 supercontents |= SUPERCONTENTS_SOLID;
5442         if (nativecontents & Q2CONTENTS_WATER)
5443                 supercontents |= SUPERCONTENTS_WATER;
5444         if (nativecontents & Q2CONTENTS_SLIME)
5445                 supercontents |= SUPERCONTENTS_SLIME;
5446         if (nativecontents & Q2CONTENTS_LAVA)
5447                 supercontents |= SUPERCONTENTS_LAVA;
5448         return supercontents;
5449 }
5450
5451 static int Mod_Q3BSP_NativeContentsFromSuperContents(model_t *model, int supercontents)
5452 {
5453         int nativecontents = 0;
5454         if (supercontents & SUPERCONTENTS_SOLID)
5455                 nativecontents |= Q2CONTENTS_SOLID;
5456         if (supercontents & SUPERCONTENTS_WATER)
5457                 nativecontents |= Q2CONTENTS_WATER;
5458         if (supercontents & SUPERCONTENTS_SLIME)
5459                 nativecontents |= Q2CONTENTS_SLIME;
5460         if (supercontents & SUPERCONTENTS_LAVA)
5461                 nativecontents |= Q2CONTENTS_LAVA;
5462         return nativecontents;
5463 }
5464
5465 /*
5466 void Mod_Q3BSP_RecursiveGetVisible(q3mnode_t *node, model_t *model, const vec3_t point, const vec3_t mins, const vec3_t maxs, int maxleafs, q3mleaf_t *leaflist, int *numleafs, int maxsurfaces, q3msurface_t *surfacelist, int *numsurfaces, const qbyte *pvs)
5467 {
5468         mleaf_t *leaf;
5469         for (;;)
5470         {
5471                 if (!BoxesOverlap(node->mins, node->maxs, mins, maxs))
5472                         return;
5473                 if (!node->plane)
5474                         break;
5475                 Mod_Q3BSP_RecursiveGetVisible(node->children[0], model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces, pvs);
5476                 node = node->children[1];
5477         }
5478         leaf = (mleaf_t *)node;
5479         if ((pvs == NULL || CHECKPVSBIT(pvs, leaf->clusterindex)))
5480         {
5481                 int marksurfacenum;
5482                 q3msurface_t *surf;
5483                 if (maxleafs && *numleafs < maxleafs)
5484                         leaflist[(*numleaf)++] = leaf;
5485                 if (maxsurfaces)
5486                 {
5487                         for (marksurfacenum = 0;marksurfacenum < leaf->nummarksurfaces;marksurfacenum++)
5488                         {
5489                                 face = leaf->firstleafface[marksurfacenum];
5490                                 if (face->shadowmark != shadowmarkcount)
5491                                 {
5492                                         face->shadowmark = shadowmarkcount;
5493                                         if (BoxesOverlap(mins, maxs, face->mins, face->maxs) && *numsurfaces < maxsurfaces)
5494                                                 surfacelist[(*numsurfaces)++] = face;
5495                                 }
5496                         }
5497                 }
5498         }
5499 }
5500
5501 void Mod_Q3BSP_GetVisible(model_t *model, const vec3_t point, const vec3_t mins, const vec3_t maxs, int maxleafs, q3mleaf_t *leaflist, int *numleafs, int maxsurfaces, q3msurface_t *surfacelist, int *numsurfaces)
5502 {
5503         // FIXME: support portals
5504         if (maxsurfaces)
5505                 *numsurfaces = 0;
5506         if (maxleafs)
5507                 *numleafs = 0;
5508         if (model->submodel)
5509         {
5510                 if (maxsurfaces)
5511                 {
5512                         for (marksurfacenum = 0;marksurfacenum < leaf->nummarksurfaces;marksurfacenum++)
5513                         {
5514                                 face = ent->model->brushq3.surfaces + leaf->firstmarksurface[marksurfacenum];
5515                                 if (BoxesOverlap(mins, maxs, face->mins, face->maxs) && *numsurfaces < maxsurfaces)
5516                                         surfacelist[(*numsurfaces)++] = face;
5517                         }
5518                 }
5519         }
5520         else
5521         {
5522                 pvs = ent->model->brush.GetPVS(ent->model, relativelightorigin);
5523                 Mod_Q3BSP_RecursiveGetVisible(ent->model->brushq3.data_nodes, model, point, mins, maxs, maxleafs, leaflist, numleafs, maxsurfaces, surfacelist, numsurfaces, pvs);
5524         }
5525 }
5526 */
5527
5528 extern void R_Q3BSP_DrawSky(struct entity_render_s *ent);
5529 extern void R_Q3BSP_Draw(struct entity_render_s *ent);
5530 extern void R_Q3BSP_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);
5531 extern void R_Q3BSP_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, int numsurfaces, const int *surfacelist);
5532 extern void R_Q3BSP_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);
5533 void Mod_Q3BSP_Load(model_t *mod, void *buffer)
5534 {
5535         int i, j, numshadowmeshtriangles;
5536         q3dheader_t *header;
5537         float corner[3], yawradius, modelradius;
5538         q3msurface_t *face;
5539
5540         mod->type = mod_brushq3;
5541         mod->numframes = 1;
5542         mod->numskins = 1;
5543
5544         header = (q3dheader_t *)buffer;
5545
5546         i = LittleLong(header->version);
5547         if (i != Q3BSPVERSION)
5548                 Host_Error("Mod_Q3BSP_Load: %s has wrong version number (%i, should be %i)", mod->name, i, Q3BSPVERSION);
5549         if (mod->isworldmodel)
5550         {
5551                 Cvar_SetValue("halflifebsp", false);
5552                 // until we get a texture for it...
5553                 R_ResetQuakeSky();
5554         }
5555
5556         mod->soundfromcenter = true;
5557         mod->TraceBox = Mod_Q3BSP_TraceBox;
5558         mod->brush.SuperContentsFromNativeContents = Mod_Q3BSP_SuperContentsFromNativeContents;
5559         mod->brush.NativeContentsFromSuperContents = Mod_Q3BSP_NativeContentsFromSuperContents;
5560         mod->brush.GetPVS = Mod_Q3BSP_GetPVS;
5561         mod->brush.FatPVS = Mod_Q3BSP_FatPVS;
5562         mod->brush.BoxTouchingPVS = Mod_Q3BSP_BoxTouchingPVS;
5563         mod->brush.LightPoint = Mod_Q3BSP_LightPoint;
5564         mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation;
5565         //mod->DrawSky = R_Q3BSP_DrawSky;
5566         mod->Draw = R_Q3BSP_Draw;
5567         mod->GetLightInfo = R_Q3BSP_GetLightInfo;
5568         mod->DrawShadowVolume = R_Q3BSP_DrawShadowVolume;
5569         mod->DrawLight = R_Q3BSP_DrawLight;
5570
5571         mod_base = (qbyte *)header;
5572
5573         // swap all the lumps
5574         for (i = 0;i < (int) sizeof(*header) / 4;i++)
5575                 ((int *)header)[i] = LittleLong(((int *)header)[i]);
5576
5577         Mod_Q3BSP_LoadEntities(&header->lumps[Q3LUMP_ENTITIES]);
5578         Mod_Q3BSP_LoadTextures(&header->lumps[Q3LUMP_TEXTURES]);
5579         Mod_Q3BSP_LoadPlanes(&header->lumps[Q3LUMP_PLANES]);
5580         Mod_Q3BSP_LoadBrushSides(&header->lumps[Q3LUMP_BRUSHSIDES]);
5581         Mod_Q3BSP_LoadBrushes(&header->lumps[Q3LUMP_BRUSHES]);
5582         Mod_Q3BSP_LoadEffects(&header->lumps[Q3LUMP_EFFECTS]);
5583         Mod_Q3BSP_LoadVertices(&header->lumps[Q3LUMP_VERTICES]);
5584         Mod_Q3BSP_LoadTriangles(&header->lumps[Q3LUMP_TRIANGLES]);
5585         Mod_Q3BSP_LoadLightmaps(&header->lumps[Q3LUMP_LIGHTMAPS]);
5586         Mod_Q3BSP_LoadFaces(&header->lumps[Q3LUMP_FACES]);
5587         Mod_Q3BSP_LoadModels(&header->lumps[Q3LUMP_MODELS]);
5588         Mod_Q3BSP_LoadLeafBrushes(&header->lumps[Q3LUMP_LEAFBRUSHES]);
5589         Mod_Q3BSP_LoadLeafFaces(&header->lumps[Q3LUMP_LEAFFACES]);
5590         Mod_Q3BSP_LoadLeafs(&header->lumps[Q3LUMP_LEAFS]);
5591         Mod_Q3BSP_LoadNodes(&header->lumps[Q3LUMP_NODES]);
5592         Mod_Q3BSP_LoadLightGrid(&header->lumps[Q3LUMP_LIGHTGRID]);
5593         Mod_Q3BSP_LoadPVS(&header->lumps[Q3LUMP_PVS]);
5594         loadmodel->brush.numsubmodels = loadmodel->brushq3.num_models;
5595
5596         // make a single combined shadow mesh to allow optimized shadow volume creation
5597         numshadowmeshtriangles = 0;
5598         for (j = 0, face = loadmodel->brushq3.data_faces;j < loadmodel->brushq3.num_faces;j++, face++)
5599         {
5600                 face->num_firstshadowmeshtriangle = numshadowmeshtriangles;
5601                 numshadowmeshtriangles += face->num_triangles;
5602         }
5603         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Begin(loadmodel->mempool, numshadowmeshtriangles * 3, numshadowmeshtriangles, NULL, NULL, NULL, false, false, true);
5604         for (j = 0, face = loadmodel->brushq3.data_faces;j < loadmodel->brushq3.num_faces;j++, face++)
5605                 Mod_ShadowMesh_AddMesh(loadmodel->mempool, loadmodel->brush.shadowmesh, NULL, NULL, NULL, face->data_vertex3f, NULL, NULL, NULL, NULL, face->num_triangles, face->data_element3i);
5606         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Finish(loadmodel->mempool, loadmodel->brush.shadowmesh, false, true);
5607         Mod_BuildTriangleNeighbors(loadmodel->brush.shadowmesh->neighbor3i, loadmodel->brush.shadowmesh->element3i, loadmodel->brush.shadowmesh->numtriangles);
5608         
5609         for (i = 0;i < loadmodel->brushq3.num_models;i++)
5610         {
5611                 if (i == 0)
5612                         mod = loadmodel;
5613                 else
5614                 {
5615                         char name[10];
5616                         // LordHavoc: only register submodels if it is the world
5617                         // (prevents bsp models from replacing world submodels)
5618                         if (!loadmodel->isworldmodel)
5619                                 continue;
5620                         // duplicate the basic information
5621                         sprintf(name, "*%i", i);
5622                         mod = Mod_FindName(name);
5623                         *mod = *loadmodel;
5624                         strcpy(mod->name, name);
5625                         // textures and memory belong to the main model
5626                         mod->texturepool = NULL;
5627                         mod->mempool = NULL;
5628                         mod->brush.GetPVS = NULL;
5629                         mod->brush.FatPVS = NULL;
5630                         mod->brush.BoxTouchingPVS = NULL;
5631                         mod->brush.LightPoint = NULL;
5632                         mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation;
5633                 }
5634                 mod->brushq3.data_thismodel = loadmodel->brushq3.data_models + i;
5635                 mod->brushq3.submodel = i;
5636
5637                 // make the model surface list (used by shadowing/lighting)
5638                 mod->nummodelsurfaces = mod->brushq3.data_thismodel->numfaces;
5639                 mod->surfacelist = Mem_Alloc(loadmodel->mempool, mod->nummodelsurfaces * sizeof(*mod->surfacelist));
5640                 for (j = 0;j < mod->nummodelsurfaces;j++)
5641                         mod->surfacelist[j] = (mod->brushq3.data_thismodel->firstface - mod->brushq3.data_faces) + j;
5642
5643                 VectorCopy(mod->brushq3.data_thismodel->mins, mod->normalmins);
5644                 VectorCopy(mod->brushq3.data_thismodel->maxs, mod->normalmaxs);
5645                 corner[0] = max(fabs(mod->normalmins[0]), fabs(mod->normalmaxs[0]));
5646                 corner[1] = max(fabs(mod->normalmins[1]), fabs(mod->normalmaxs[1]));
5647                 corner[2] = max(fabs(mod->normalmins[2]), fabs(mod->normalmaxs[2]));
5648                 modelradius = sqrt(corner[0]*corner[0]+corner[1]*corner[1]+corner[2]*corner[2]);
5649                 yawradius = sqrt(corner[0]*corner[0]+corner[1]*corner[1]);
5650                 mod->rotatedmins[0] = mod->rotatedmins[1] = mod->rotatedmins[2] = -modelradius;
5651                 mod->rotatedmaxs[0] = mod->rotatedmaxs[1] = mod->rotatedmaxs[2] = modelradius;
5652                 mod->yawmaxs[0] = mod->yawmaxs[1] = yawradius;
5653                 mod->yawmins[0] = mod->yawmins[1] = -yawradius;
5654                 mod->yawmins[2] = mod->normalmins[2];
5655                 mod->yawmaxs[2] = mod->normalmaxs[2];
5656                 mod->radius = modelradius;
5657                 mod->radius2 = modelradius * modelradius;
5658
5659                 for (j = 0;j < mod->brushq3.data_thismodel->numfaces;j++)
5660                         if (mod->brushq3.data_thismodel->firstface[j].texture->surfaceflags & Q3SURFACEFLAG_SKY)
5661                                 break;
5662                 if (j < mod->brushq3.data_thismodel->numfaces)
5663                         mod->DrawSky = R_Q3BSP_DrawSky;
5664         }
5665 }
5666
5667 void Mod_IBSP_Load(model_t *mod, void *buffer)
5668 {
5669         int i = LittleLong(((int *)buffer)[1]);
5670         if (i == Q3BSPVERSION)
5671                 Mod_Q3BSP_Load(mod,buffer);
5672         else if (i == Q2BSPVERSION)
5673                 Mod_Q2BSP_Load(mod,buffer);
5674         else
5675                 Host_Error("Mod_IBSP_Load: unknown/unsupported version %i\n", i);
5676 }
5677
5678 void Mod_MAP_Load(model_t *mod, void *buffer)
5679 {
5680         Host_Error("Mod_MAP_Load: not yet implemented\n");
5681 }
5682