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