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