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