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