changed Collision_NewBrushFromPlanes to use new polygon.c code, this got rid of the...
[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                 {