better SUPERCONTENTS masks for a few TraceBox and PointContents calls
[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)
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         Con_Print("\n");
854 #else
855         if (VectorLength2(rhc.dist))
856                 Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
857         else
858                 Mod_Q1BSP_RecursiveHullCheckPoint(&rhc, rhc.hull->firstclipnode);
859 #endif
860 }
861
862 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)
863 {
864 #if 1
865         colbrushf_t cbox;
866         colplanef_t cbox_planes[6];
867         cbox.supercontents = boxsupercontents;
868         cbox.numplanes = 6;
869         cbox.numpoints = 0;
870         cbox.numtriangles = 0;
871         cbox.planes = cbox_planes;
872         cbox.points = NULL;
873         cbox.elements = NULL;
874         cbox.markframe = 0;
875         cbox.mins[0] = 0;
876         cbox.mins[1] = 0;
877         cbox.mins[2] = 0;
878         cbox.maxs[0] = 0;
879         cbox.maxs[1] = 0;
880         cbox.maxs[2] = 0;
881         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];
882         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];
883         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];
884         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];
885         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];
886         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];
887         cbox_planes[0].supercontents = boxsupercontents;cbox_planes[0].q3surfaceflags = boxq3surfaceflags;cbox_planes[0].texture = boxtexture;
888         cbox_planes[1].supercontents = boxsupercontents;cbox_planes[1].q3surfaceflags = boxq3surfaceflags;cbox_planes[1].texture = boxtexture;
889         cbox_planes[2].supercontents = boxsupercontents;cbox_planes[2].q3surfaceflags = boxq3surfaceflags;cbox_planes[2].texture = boxtexture;
890         cbox_planes[3].supercontents = boxsupercontents;cbox_planes[3].q3surfaceflags = boxq3surfaceflags;cbox_planes[3].texture = boxtexture;
891         cbox_planes[4].supercontents = boxsupercontents;cbox_planes[4].q3surfaceflags = boxq3surfaceflags;cbox_planes[4].texture = boxtexture;
892         cbox_planes[5].supercontents = boxsupercontents;cbox_planes[5].q3surfaceflags = boxq3surfaceflags;cbox_planes[5].texture = boxtexture;
893         memset(trace, 0, sizeof(trace_t));
894         trace->hitsupercontentsmask = hitsupercontentsmask;
895         trace->fraction = 1;
896         trace->realfraction = 1;
897         Collision_TraceLineBrushFloat(trace, start, end, &cbox, &cbox);
898 #else
899         RecursiveHullCheckTraceInfo_t rhc;
900         static hull_t box_hull;
901         static dclipnode_t box_clipnodes[6];
902         static mplane_t box_planes[6];
903         // fill in a default trace
904         memset(&rhc, 0, sizeof(rhc));
905         memset(trace, 0, sizeof(trace_t));
906         //To keep everything totally uniform, bounding boxes are turned into small
907         //BSP trees instead of being compared directly.
908         // create a temp hull from bounding box sizes
909         box_planes[0].dist = cmaxs[0] - mins[0];
910         box_planes[1].dist = cmins[0] - maxs[0];
911         box_planes[2].dist = cmaxs[1] - mins[1];
912         box_planes[3].dist = cmins[1] - maxs[1];
913         box_planes[4].dist = cmaxs[2] - mins[2];
914         box_planes[5].dist = cmins[2] - maxs[2];
915 #if COLLISIONPARANOID >= 3
916         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]);
917 #endif
918
919         if (box_hull.clipnodes == NULL)
920         {
921                 int i, side;
922
923                 //Set up the planes and clipnodes so that the six floats of a bounding box
924                 //can just be stored out and get a proper hull_t structure.
925
926                 box_hull.clipnodes = box_clipnodes;
927                 box_hull.planes = box_planes;
928                 box_hull.firstclipnode = 0;
929                 box_hull.lastclipnode = 5;
930
931                 for (i = 0;i < 6;i++)
932                 {
933                         box_clipnodes[i].planenum = i;
934
935                         side = i&1;
936
937                         box_clipnodes[i].children[side] = CONTENTS_EMPTY;
938                         if (i != 5)
939                                 box_clipnodes[i].children[side^1] = i + 1;
940                         else
941                                 box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
942
943                         box_planes[i].type = i>>1;
944                         box_planes[i].normal[i>>1] = 1;
945                 }
946         }
947
948         // trace a line through the generated clipping hull
949         //rhc.boxsupercontents = boxsupercontents;
950         rhc.hull = &box_hull;
951         rhc.trace = trace;
952         rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
953         rhc.trace->fraction = 1;
954         rhc.trace->realfraction = 1;
955         rhc.trace->allsolid = true;
956         VectorCopy(start, rhc.start);
957         VectorCopy(end, rhc.end);
958         VectorSubtract(rhc.end, rhc.start, rhc.dist);
959         Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
960         //VectorMA(rhc.start, rhc.trace->fraction, rhc.dist, rhc.trace->endpos);
961         if (rhc.trace->startsupercontents)
962                 rhc.trace->startsupercontents = boxsupercontents;
963 #endif
964 }
965
966 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)
967 {
968         int side;
969         float front, back;
970         float mid, distz = endz - startz;
971
972 loc0:
973         if (!node->plane)
974                 return false;           // didn't hit anything
975
976         switch (node->plane->type)
977         {
978         case PLANE_X:
979                 node = node->children[x < node->plane->dist];
980                 goto loc0;
981         case PLANE_Y:
982                 node = node->children[y < node->plane->dist];
983                 goto loc0;
984         case PLANE_Z:
985                 side = startz < node->plane->dist;
986                 if ((endz < node->plane->dist) == side)
987                 {
988                         node = node->children[side];
989                         goto loc0;
990                 }
991                 // found an intersection
992                 mid = node->plane->dist;
993                 break;
994         default:
995                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
996                 front += startz * node->plane->normal[2];
997                 back += endz * node->plane->normal[2];
998                 side = front < node->plane->dist;
999                 if ((back < node->plane->dist) == side)
1000                 {
1001                         node = node->children[side];
1002                         goto loc0;
1003                 }
1004                 // found an intersection
1005                 mid = startz + distz * (front - node->plane->dist) / (front - back);
1006                 break;
1007         }
1008
1009         // go down front side
1010         if (node->children[side]->plane && Mod_Q1BSP_LightPoint_RecursiveBSPNode(model, ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
1011                 return true;    // hit something
1012         else
1013         {
1014                 // check for impact on this node
1015                 if (node->numsurfaces)
1016                 {
1017                         int i, ds, dt;
1018                         msurface_t *surface;
1019
1020                         surface = model->data_surfaces + node->firstsurface;
1021                         for (i = 0;i < node->numsurfaces;i++, surface++)
1022                         {
1023                                 if (!(surface->texture->basematerialflags & MATERIALFLAG_WALL) || !surface->lightmapinfo->samples)
1024                                         continue;       // no lightmaps
1025
1026                                 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];
1027                                 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];
1028
1029                                 if (ds >= 0 && ds < surface->lightmapinfo->extents[0] && dt >= 0 && dt < surface->lightmapinfo->extents[1])
1030                                 {
1031                                         unsigned char *lightmap;
1032                                         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;
1033                                         lmwidth = ((surface->lightmapinfo->extents[0]>>4)+1);
1034                                         lmheight = ((surface->lightmapinfo->extents[1]>>4)+1);
1035                                         line3 = lmwidth * 3; // LordHavoc: *3 for colored lighting
1036                                         size3 = lmwidth * lmheight * 3; // LordHavoc: *3 for colored lighting
1037
1038                                         lightmap = surface->lightmapinfo->samples + ((dt>>4) * lmwidth + (ds>>4))*3; // LordHavoc: *3 for colored lighting
1039
1040                                         for (maps = 0;maps < MAXLIGHTMAPS && surface->lightmapinfo->styles[maps] != 255;maps++)
1041                                         {
1042                                                 scale = r_refdef.lightstylevalue[surface->lightmapinfo->styles[maps]];
1043                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
1044                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
1045                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
1046                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
1047                                                 lightmap += size3;
1048                                         }
1049
1050 /*
1051 LordHavoc: here's the readable version of the interpolation
1052 code, not quite as easy for the compiler to optimize...
1053
1054 dsfrac is the X position in the lightmap pixel, * 16
1055 dtfrac is the Y position in the lightmap pixel, * 16
1056 r00 is top left corner, r01 is top right corner
1057 r10 is bottom left corner, r11 is bottom right corner
1058 g and b are the same layout.
1059 r0 and r1 are the top and bottom intermediate results
1060
1061 first we interpolate the top two points, to get the top
1062 edge sample
1063
1064         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
1065         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
1066         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
1067
1068 then we interpolate the bottom two points, to get the
1069 bottom edge sample
1070
1071         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
1072         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
1073         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
1074
1075 then we interpolate the top and bottom samples to get the
1076 middle sample (the one which was requested)
1077
1078         r = (((r1-r0) * dtfrac) >> 4) + r0;
1079         g = (((g1-g0) * dtfrac) >> 4) + g0;
1080         b = (((b1-b0) * dtfrac) >> 4) + b0;
1081 */
1082
1083                                         ambientcolor[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
1084                                         ambientcolor[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
1085                                         ambientcolor[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
1086                                         return true; // success
1087                                 }
1088                         }
1089                 }
1090
1091                 // go down back side
1092                 node = node->children[side ^ 1];
1093                 startz = mid;
1094                 distz = endz - startz;
1095                 goto loc0;
1096         }
1097 }
1098
1099 void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
1100 {
1101         Mod_Q1BSP_LightPoint_RecursiveBSPNode(model, ambientcolor, diffusecolor, diffusenormal, model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode, p[0], p[1], p[2], p[2] - 65536);
1102         VectorSet(diffusenormal, 0, 0, -1);
1103 }
1104
1105 static void Mod_Q1BSP_DecompressVis(const unsigned char *in, const unsigned char *inend, unsigned char *out, unsigned char *outend)
1106 {
1107         int c;
1108         unsigned char *outstart = out;
1109         while (out < outend)
1110         {
1111                 if (in == inend)
1112                 {
1113                         Con_Printf("Mod_Q1BSP_DecompressVis: input underrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
1114                         return;
1115                 }
1116                 c = *in++;
1117                 if (c)
1118                         *out++ = c;
1119                 else
1120                 {
1121                         if (in == inend)
1122                         {
1123                                 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);
1124                                 return;
1125                         }
1126                         for (c = *in++;c > 0;c--)
1127                         {
1128                                 if (out == outend)
1129                                 {
1130                                         Con_Printf("Mod_Q1BSP_DecompressVis: output overrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
1131                                         return;
1132                                 }
1133                                 *out++ = 0;
1134                         }
1135                 }
1136         }
1137 }
1138
1139 /*
1140 =============
1141 R_Q1BSP_LoadSplitSky
1142
1143 A sky texture is 256*128, with the right side being a masked overlay
1144 ==============
1145 */
1146 void R_Q1BSP_LoadSplitSky (unsigned char *src, int width, int height, int bytesperpixel)
1147 {
1148         int i, j;
1149         unsigned solidpixels[128*128], alphapixels[128*128];
1150
1151         // if sky isn't the right size, just use it as a solid layer
1152         if (width != 256 || height != 128)
1153         {
1154                 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);
1155                 loadmodel->brush.alphaskytexture = NULL;
1156                 return;
1157         }
1158
1159         if (bytesperpixel == 4)
1160         {
1161                 for (i = 0;i < 128;i++)
1162                 {
1163                         for (j = 0;j < 128;j++)
1164                         {
1165                                 solidpixels[(i*128) + j] = ((unsigned *)src)[i*256+j+128];
1166                                 alphapixels[(i*128) + j] = ((unsigned *)src)[i*256+j];
1167                         }
1168                 }
1169         }
1170         else
1171         {
1172                 // make an average value for the back to avoid
1173                 // a fringe on the top level
1174                 int p, r, g, b;
1175                 union
1176                 {
1177                         unsigned int i;
1178                         unsigned char b[4];
1179                 }
1180                 rgba;
1181                 r = g = b = 0;
1182                 for (i = 0;i < 128;i++)
1183                 {
1184                         for (j = 0;j < 128;j++)
1185                         {
1186                                 rgba.i = palette_complete[src[i*256 + j + 128]];
1187                                 r += rgba.b[0];
1188                                 g += rgba.b[1];
1189                                 b += rgba.b[2];
1190                         }
1191                 }
1192                 rgba.b[0] = r/(128*128);
1193                 rgba.b[1] = g/(128*128);
1194                 rgba.b[2] = b/(128*128);
1195                 rgba.b[3] = 0;
1196                 for (i = 0;i < 128;i++)
1197                 {
1198                         for (j = 0;j < 128;j++)
1199                         {
1200                                 solidpixels[(i*128) + j] = palette_complete[src[i*256 + j + 128]];
1201                                 alphapixels[(i*128) + j] = (p = src[i*256 + j]) ? palette_complete[p] : rgba.i;
1202                         }
1203                 }
1204         }
1205
1206         loadmodel->brush.solidskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_solidtexture", 128, 128, (unsigned char *) solidpixels, TEXTYPE_RGBA, TEXF_PRECACHE, NULL);
1207         loadmodel->brush.alphaskytexture = R_LoadTexture2D(loadmodel->texturepool, "sky_alphatexture", 128, 128, (unsigned char *) alphapixels, TEXTYPE_RGBA, TEXF_ALPHA | TEXF_PRECACHE, NULL);
1208 }
1209
1210 static void Mod_Q1BSP_LoadTextures(lump_t *l)
1211 {
1212         int i, j, k, num, max, altmax, mtwidth, mtheight, *dofs, incomplete;
1213         miptex_t *dmiptex;
1214         texture_t *tx, *tx2, *anims[10], *altanims[10];
1215         dmiptexlump_t *m;
1216         unsigned char *data, *mtdata;
1217         char name[MAX_QPATH];
1218
1219         loadmodel->data_textures = NULL;
1220
1221         // add two slots for notexture walls and notexture liquids
1222         if (l->filelen)
1223         {
1224                 m = (dmiptexlump_t *)(mod_base + l->fileofs);
1225                 m->nummiptex = LittleLong (m->nummiptex);
1226                 loadmodel->num_textures = m->nummiptex + 2;
1227         }
1228         else
1229         {
1230                 m = NULL;
1231                 loadmodel->num_textures = 2;
1232         }
1233
1234         loadmodel->data_textures = (texture_t *)Mem_Alloc(loadmodel->mempool, loadmodel->num_textures * sizeof(texture_t));
1235
1236         // fill out all slots with notexture
1237         for (i = 0, tx = loadmodel->data_textures;i < loadmodel->num_textures;i++, tx++)
1238         {
1239                 strcpy(tx->name, "NO TEXTURE FOUND");
1240                 tx->width = 16;
1241                 tx->height = 16;
1242                 tx->skin.base = r_texture_notexture;
1243                 tx->basematerialflags = 0;
1244                 if (i == loadmodel->num_textures - 1)
1245                 {
1246                         tx->basematerialflags |= MATERIALFLAG_WATER | MATERIALFLAG_LIGHTBOTHSIDES;
1247                         tx->supercontents = mod_q1bsp_texture_water.supercontents;
1248                         tx->surfaceflags = mod_q1bsp_texture_water.surfaceflags;
1249                 }
1250                 else
1251                 {
1252                         tx->basematerialflags |= MATERIALFLAG_WALL;
1253                         tx->supercontents = mod_q1bsp_texture_solid.supercontents;
1254                         tx->surfaceflags = mod_q1bsp_texture_solid.surfaceflags;
1255                 }
1256                 tx->currentframe = tx;
1257         }
1258
1259         if (!m)
1260                 return;
1261
1262         // just to work around bounds checking when debugging with it (array index out of bounds error thing)
1263         dofs = m->dataofs;
1264         // LordHavoc: mostly rewritten map texture loader
1265         for (i = 0;i < m->nummiptex;i++)
1266         {
1267                 dofs[i] = LittleLong(dofs[i]);
1268                 if (dofs[i] == -1 || r_nosurftextures.integer)
1269                         continue;
1270                 dmiptex = (miptex_t *)((unsigned char *)m + dofs[i]);
1271
1272                 // make sure name is no more than 15 characters
1273                 for (j = 0;dmiptex->name[j] && j < 15;j++)
1274                         name[j] = dmiptex->name[j];
1275                 name[j] = 0;
1276
1277                 mtwidth = LittleLong(dmiptex->width);
1278                 mtheight = LittleLong(dmiptex->height);
1279                 mtdata = NULL;
1280                 j = LittleLong(dmiptex->offsets[0]);
1281                 if (j)
1282                 {
1283                         // texture included
1284                         if (j < 40 || j + mtwidth * mtheight > l->filelen)
1285                         {
1286                                 Con_Printf("Texture \"%s\" in \"%s\"is corrupt or incomplete\n", dmiptex->name, loadmodel->name);
1287                                 continue;
1288                         }
1289                         mtdata = (unsigned char *)dmiptex + j;
1290                 }
1291
1292                 if ((mtwidth & 15) || (mtheight & 15))
1293                         Con_Printf("warning: texture \"%s\" in \"%s\" is not 16 aligned\n", dmiptex->name, loadmodel->name);
1294
1295                 // LordHavoc: force all names to lowercase
1296                 for (j = 0;name[j];j++)
1297                         if (name[j] >= 'A' && name[j] <= 'Z')
1298                                 name[j] += 'a' - 'A';
1299
1300                 tx = loadmodel->data_textures + i;
1301                 strcpy(tx->name, name);
1302                 tx->width = mtwidth;
1303                 tx->height = mtheight;
1304
1305                 if (!tx->name[0])
1306                 {
1307                         sprintf(tx->name, "unnamed%i", i);
1308                         Con_Printf("warning: unnamed texture in %s, renaming to %s\n", loadmodel->name, tx->name);
1309                 }
1310
1311                 if (cls.state != ca_dedicated)
1312                 {
1313                         // LordHavoc: HL sky textures are entirely different than quake
1314                         if (!loadmodel->brush.ishlbsp && !strncmp(tx->name, "sky", 3) && mtwidth == 256 && mtheight == 128)
1315                         {
1316                                 if (loadmodel->isworldmodel)
1317                                 {
1318                                         data = loadimagepixels(tx->name, false, 0, 0);
1319                                         if (data)
1320                                         {
1321                                                 R_Q1BSP_LoadSplitSky(data, image_width, image_height, 4);
1322                                                 Mem_Free(data);
1323                                         }
1324                                         else if (mtdata != NULL)
1325                                                 R_Q1BSP_LoadSplitSky(mtdata, mtwidth, mtheight, 1);
1326                                 }
1327                         }
1328                         else
1329                         {
1330                                 if (!Mod_LoadSkinFrame(&tx->skin, gamemode == GAME_TENEBRAE ? tx->name : va("textures/%s", tx->name), TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, false, true))
1331                                 {
1332                                         // did not find external texture, load it from the bsp or wad3
1333                                         if (loadmodel->brush.ishlbsp)
1334                                         {
1335                                                 // internal texture overrides wad
1336                                                 unsigned char *pixels, *freepixels;
1337                                                 pixels = freepixels = NULL;
1338                                                 if (mtdata)
1339                                                         pixels = W_ConvertWAD3Texture(dmiptex);
1340                                                 if (pixels == NULL)
1341                                                         pixels = freepixels = W_GetTexture(tx->name);
1342                                                 if (pixels != NULL)
1343                                                 {
1344                                                         tx->width = image_width;
1345                                                         tx->height = image_height;
1346                                                         Mod_LoadSkinFrame_Internal(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_ALPHA | TEXF_PRECACHE | TEXF_PICMIP, false, false, pixels, image_width, image_height, 32, NULL, NULL);
1347                                                 }
1348                                                 if (freepixels)
1349                                                         Mem_Free(freepixels);
1350                                         }
1351                                         else if (mtdata) // texture included
1352                                                 Mod_LoadSkinFrame_Internal(&tx->skin, tx->name, TEXF_MIPMAP | TEXF_PRECACHE | TEXF_PICMIP, false, r_fullbrights.integer, mtdata, tx->width, tx->height, 8, NULL, NULL);
1353                                 }
1354                         }
1355                         if (tx->skin.base == NULL)
1356                         {
1357                                 // no texture found
1358                                 tx->width = 16;
1359                                 tx->height = 16;
1360                                 tx->skin.base = r_texture_notexture;
1361                         }
1362                 }
1363
1364                 tx->basematerialflags = 0;
1365                 if (tx->name[0] == '*')
1366                 {
1367                         // LordHavoc: some turbulent textures should not be affected by wateralpha
1368                         if (strncmp(tx->name,"*lava",5)
1369                          && strncmp(tx->name,"*teleport",9)
1370                          && strncmp(tx->name,"*rift",5)) // Scourge of Armagon texture
1371                                 tx->basematerialflags |= MATERIALFLAG_WATERALPHA;
1372                         if (!strncmp(tx->name, "*lava", 5))
1373                         {
1374                                 tx->supercontents = mod_q1bsp_texture_lava.supercontents;
1375                                 tx->surfaceflags = mod_q1bsp_texture_lava.surfaceflags;
1376                         }
1377                         else if (!strncmp(tx->name, "*slime", 6))
1378                         {
1379                                 tx->supercontents = mod_q1bsp_texture_slime.supercontents;
1380                                 tx->surfaceflags = mod_q1bsp_texture_slime.surfaceflags;
1381                         }
1382                         else
1383                         {
1384                                 tx->supercontents = mod_q1bsp_texture_water.supercontents;
1385                                 tx->surfaceflags = mod_q1bsp_texture_water.surfaceflags;
1386                         }
1387                         tx->basematerialflags |= MATERIALFLAG_WATER | MATERIALFLAG_LIGHTBOTHSIDES;
1388                 }
1389                 else if (tx->name[0] == 's' && tx->name[1] == 'k' && tx->name[2] == 'y')
1390                 {
1391                         tx->supercontents = mod_q1bsp_texture_sky.supercontents;
1392                         tx->surfaceflags = mod_q1bsp_texture_sky.surfaceflags;
1393                         tx->basematerialflags |= MATERIALFLAG_SKY;
1394                 }
1395                 else
1396                 {
1397                         tx->supercontents = mod_q1bsp_texture_solid.supercontents;
1398                         tx->surfaceflags = mod_q1bsp_texture_solid.surfaceflags;
1399                         tx->basematerialflags |= MATERIALFLAG_WALL;
1400                 }
1401                 if (tx->skin.fog)
1402                         tx->basematerialflags |= MATERIALFLAG_ALPHA | MATERIALFLAG_TRANSPARENT;
1403
1404                 // start out with no animation
1405                 tx->currentframe = tx;
1406         }
1407
1408         // sequence the animations
1409         for (i = 0;i < m->nummiptex;i++)
1410         {
1411                 tx = loadmodel->data_textures + i;
1412                 if (!tx || tx->name[0] != '+' || tx->name[1] == 0 || tx->name[2] == 0)
1413                         continue;
1414                 if (tx->anim_total[0] || tx->anim_total[1])
1415                         continue;       // already sequenced
1416
1417                 // find the number of frames in the animation
1418                 memset(anims, 0, sizeof(anims));
1419                 memset(altanims, 0, sizeof(altanims));
1420
1421                 for (j = i;j < m->nummiptex;j++)
1422                 {
1423                         tx2 = loadmodel->data_textures + j;
1424                         if (!tx2 || tx2->name[0] != '+' || strcmp(tx2->name+2, tx->name+2))
1425                                 continue;
1426
1427                         num = tx2->name[1];
1428                         if (num >= '0' && num <= '9')
1429                                 anims[num - '0'] = tx2;
1430                         else if (num >= 'a' && num <= 'j')
1431                                 altanims[num - 'a'] = tx2;
1432                         else
1433                                 Con_Printf("Bad animating texture %s\n", tx->name);
1434                 }
1435
1436                 max = altmax = 0;
1437                 for (j = 0;j < 10;j++)
1438                 {
1439                         if (anims[j])
1440                                 max = j + 1;
1441                         if (altanims[j])
1442                                 altmax = j + 1;
1443                 }
1444                 //Con_Printf("linking animation %s (%i:%i frames)\n\n", tx->name, max, altmax);
1445
1446                 incomplete = false;
1447                 for (j = 0;j < max;j++)
1448                 {
1449                         if (!anims[j])
1450                         {
1451                                 Con_Printf("Missing frame %i of %s\n", j, tx->name);
1452                                 incomplete = true;
1453                         }
1454                 }
1455                 for (j = 0;j < altmax;j++)
1456                 {
1457                         if (!altanims[j])
1458                         {
1459                                 Con_Printf("Missing altframe %i of %s\n", j, tx->name);
1460                                 incomplete = true;
1461                         }
1462                 }
1463                 if (incomplete)
1464                         continue;
1465
1466                 if (altmax < 1)
1467                 {
1468                         // if there is no alternate animation, duplicate the primary
1469                         // animation into the alternate
1470                         altmax = max;
1471                         for (k = 0;k < 10;k++)
1472                                 altanims[k] = anims[k];
1473                 }
1474
1475                 // link together the primary animation
1476                 for (j = 0;j < max;j++)
1477                 {
1478                         tx2 = anims[j];
1479                         tx2->animated = true;
1480                         tx2->anim_total[0] = max;
1481                         tx2->anim_total[1] = altmax;
1482                         for (k = 0;k < 10;k++)
1483                         {
1484                                 tx2->anim_frames[0][k] = anims[k];
1485                                 tx2->anim_frames[1][k] = altanims[k];
1486                         }
1487                 }
1488
1489                 // if there really is an alternate anim...
1490                 if (anims[0] != altanims[0])
1491                 {
1492                         // link together the alternate animation
1493                         for (j = 0;j < altmax;j++)
1494                         {
1495                                 tx2 = altanims[j];
1496                                 tx2->animated = true;
1497                                 // the primary/alternate are reversed here
1498                                 tx2->anim_total[0] = altmax;
1499                                 tx2->anim_total[1] = max;
1500                                 for (k = 0;k < 10;k++)
1501                                 {
1502                                         tx2->anim_frames[0][k] = altanims[k];
1503                                         tx2->anim_frames[1][k] = anims[k];
1504                                 }
1505                         }
1506                 }
1507         }
1508 }
1509
1510 static void Mod_Q1BSP_LoadLighting(lump_t *l)
1511 {
1512         int i;
1513         unsigned char *in, *out, *data, d;
1514         char litfilename[MAX_QPATH];
1515         char dlitfilename[MAX_QPATH];
1516         fs_offset_t filesize;
1517         if (loadmodel->brush.ishlbsp) // LordHavoc: load the colored lighting data straight
1518         {
1519                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1520                 for (i=0; i<l->filelen; i++)
1521                         loadmodel->brushq1.lightdata[i] = mod_base[l->fileofs+i] >>= 1;
1522         }
1523         else if (loadmodel->brush.ismcbsp)
1524         {
1525                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1526                 memcpy(loadmodel->brushq1.lightdata, mod_base + l->fileofs, l->filelen);
1527         }
1528         else // LordHavoc: bsp version 29 (normal white lighting)
1529         {
1530                 // LordHavoc: hope is not lost yet, check for a .lit file to load
1531                 strlcpy (litfilename, loadmodel->name, sizeof (litfilename));
1532                 FS_StripExtension (litfilename, litfilename, sizeof (litfilename));
1533                 strlcpy (dlitfilename, litfilename, sizeof (dlitfilename));
1534                 strlcat (litfilename, ".lit", sizeof (litfilename));
1535                 strlcat (dlitfilename, ".dlit", sizeof (dlitfilename));
1536                 data = (unsigned char*) FS_LoadFile(litfilename, tempmempool, false, &filesize);
1537                 if (data)
1538                 {
1539                         if (filesize == (fs_offset_t)(8 + l->filelen * 3) && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1540                         {
1541                                 i = LittleLong(((int *)data)[1]);
1542                                 if (i == 1)
1543                                 {
1544                                         Con_DPrintf("loaded %s\n", litfilename);
1545                                         loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, filesize - 8);
1546                                         memcpy(loadmodel->brushq1.lightdata, data + 8, filesize - 8);
1547                                         Mem_Free(data);
1548                                         data = (unsigned char*) FS_LoadFile(dlitfilename, tempmempool, false, &filesize);
1549                                         if (data)
1550                                         {
1551                                                 if (filesize == (fs_offset_t)(8 + l->filelen * 3) && data[0] == 'Q' && data[1] == 'L' && data[2] == 'I' && data[3] == 'T')
1552                                                 {
1553                                                         i = LittleLong(((int *)data)[1]);
1554                                                         if (i == 1)
1555                                                         {
1556                                                                 Con_DPrintf("loaded %s\n", dlitfilename);
1557                                                                 loadmodel->brushq1.nmaplightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, filesize - 8);
1558                                                                 memcpy(loadmodel->brushq1.nmaplightdata, data + 8, filesize - 8);
1559                                                                 loadmodel->brushq3.deluxemapping_modelspace = false;
1560                                                                 loadmodel->brushq3.deluxemapping = true;
1561                                                         }
1562                                                 }
1563                                                 Mem_Free(data);
1564                                                 data = NULL;
1565                                         }
1566                                         return;
1567                                 }
1568                                 else
1569                                         Con_Printf("Unknown .lit file version (%d)\n", i);
1570                         }
1571                         else if (filesize == 8)
1572                                 Con_Print("Empty .lit file, ignoring\n");
1573                         else
1574                                 Con_Printf("Corrupt .lit file (file size %i bytes, should be %i bytes), ignoring\n", filesize, 8 + l->filelen * 3);
1575                         if (data)
1576                         {
1577                                 Mem_Free(data);
1578                                 data = NULL;
1579                         }
1580                 }
1581                 // LordHavoc: oh well, expand the white lighting data
1582                 if (!l->filelen)
1583                         return;
1584                 loadmodel->brushq1.lightdata = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen*3);
1585                 in = mod_base + l->fileofs;
1586                 out = loadmodel->brushq1.lightdata;
1587                 for (i = 0;i < l->filelen;i++)
1588                 {
1589                         d = *in++;
1590                         *out++ = d;
1591                         *out++ = d;
1592                         *out++ = d;
1593                 }
1594         }
1595 }
1596
1597 static void Mod_Q1BSP_LoadVisibility(lump_t *l)
1598 {
1599         loadmodel->brushq1.num_compressedpvs = 0;
1600         loadmodel->brushq1.data_compressedpvs = NULL;
1601         if (!l->filelen)
1602                 return;
1603         loadmodel->brushq1.num_compressedpvs = l->filelen;
1604         loadmodel->brushq1.data_compressedpvs = (unsigned char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1605         memcpy(loadmodel->brushq1.data_compressedpvs, mod_base + l->fileofs, l->filelen);
1606 }
1607
1608 // used only for HalfLife maps
1609 static void Mod_Q1BSP_ParseWadsFromEntityLump(const char *data)
1610 {
1611         char key[128], value[4096];
1612         char wadname[128];
1613         int i, j, k;
1614         if (!data)
1615                 return;
1616         if (!COM_ParseToken(&data, false))
1617                 return; // error
1618         if (com_token[0] != '{')
1619                 return; // error
1620         while (1)
1621         {
1622                 if (!COM_ParseToken(&data, false))
1623                         return; // error
1624                 if (com_token[0] == '}')
1625                         break; // end of worldspawn
1626                 if (com_token[0] == '_')
1627                         strcpy(key, com_token + 1);
1628                 else
1629                         strcpy(key, com_token);
1630                 while (key[strlen(key)-1] == ' ') // remove trailing spaces
1631                         key[strlen(key)-1] = 0;
1632                 if (!COM_ParseToken(&data, false))
1633                         return; // error
1634                 dpsnprintf(value, sizeof(value), "%s", com_token);
1635                 if (!strcmp("wad", key)) // for HalfLife maps
1636                 {
1637                         if (loadmodel->brush.ishlbsp)
1638                         {
1639                                 j = 0;
1640                                 for (i = 0;i < (int)sizeof(value);i++)
1641                                         if (value[i] != ';' && value[i] != '\\' && value[i] != '/' && value[i] != ':')
1642                                                 break;
1643                                 if (value[i])
1644                                 {
1645                                         for (;i < (int)sizeof(value);i++)
1646                                         {
1647                                                 // ignore path - the \\ check is for HalfLife... stupid windoze 'programmers'...
1648                                                 if (value[i] == '\\' || value[i] == '/' || value[i] == ':')
1649                                                         j = i+1;
1650                                                 else if (value[i] == ';' || value[i] == 0)
1651                                                 {
1652                                                         k = value[i];
1653                                                         value[i] = 0;
1654                                                         strcpy(wadname, "textures/");
1655                                                         strcat(wadname, &value[j]);
1656                                                         W_LoadTextureWadFile(wadname, false);
1657                                                         j = i+1;
1658                                                         if (!k)
1659                                                                 break;
1660                                                 }
1661                                         }
1662                                 }
1663                         }
1664                 }
1665         }
1666 }
1667
1668 static void Mod_Q1BSP_LoadEntities(lump_t *l)
1669 {
1670         loadmodel->brush.entities = NULL;
1671         if (!l->filelen)
1672                 return;
1673         loadmodel->brush.entities = (char *)Mem_Alloc(loadmodel->mempool, l->filelen);
1674         memcpy(loadmodel->brush.entities, mod_base + l->fileofs, l->filelen);
1675         if (loadmodel->brush.ishlbsp)
1676                 Mod_Q1BSP_ParseWadsFromEntityLump(loadmodel->brush.entities);
1677 }
1678
1679
1680 static void Mod_Q1BSP_LoadVertexes(lump_t *l)
1681 {
1682         dvertex_t       *in;
1683         mvertex_t       *out;
1684         int                     i, count;
1685
1686         in = (dvertex_t *)(mod_base + l->fileofs);
1687         if (l->filelen % sizeof(*in))
1688                 Host_Error("Mod_Q1BSP_LoadVertexes: funny lump size in %s",loadmodel->name);
1689         count = l->filelen / sizeof(*in);
1690         out = (mvertex_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
1691
1692         loadmodel->brushq1.vertexes = out;
1693         loadmodel->brushq1.numvertexes = count;
1694
1695         for ( i=0 ; i<count ; i++, in++, out++)
1696         {
1697                 out->position[0] = LittleFloat(in->point[0]);
1698                 out->position[1] = LittleFloat(in->point[1]);
1699                 out->position[2] = LittleFloat(in->point[2]);
1700         }
1701 }
1702
1703 // The following two functions should be removed and MSG_* or SZ_* function sets adjusted so they
1704 // can be used for this
1705 // REMOVEME
1706 int SB_ReadInt (unsigned char **buffer)
1707 {
1708         int     i;
1709         i = ((*buffer)[0]) + 256*((*buffer)[1]) + 65536*((*buffer)[2]) + 16777216*((*buffer)[3]);
1710         (*buffer) += 4;
1711         return i;
1712 }
1713
1714 // REMOVEME
1715 float SB_ReadFloat (unsigned char **buffer)
1716 {
1717         union
1718         {
1719                 int             i;
1720                 float   f;
1721         } u;
1722
1723         u.i = SB_ReadInt (buffer);
1724         return u.f;
1725 }
1726
1727 static void Mod_Q1BSP_LoadSubmodels(lump_t *l, hullinfo_t *hullinfo)
1728 {
1729         unsigned char           *index;
1730         dmodel_t        *out;
1731         int                     i, j, count;
1732
1733         index = (unsigned char *)(mod_base + l->fileofs);
1734         if (l->filelen % (48+4*hullinfo->filehulls))
1735                 Host_Error ("Mod_Q1BSP_LoadSubmodels: funny lump size in %s", loadmodel->name);
1736
1737         count = l->filelen / (48+4*hullinfo->filehulls);
1738         out = (dmodel_t *)Mem_Alloc (loadmodel->mempool, count*sizeof(*out));
1739
1740         loadmodel->brushq1.submodels = out;
1741         loadmodel->brush.numsubmodels = count;
1742
1743         for (i = 0; i < count; i++, out++)
1744         {
1745         // spread out the mins / maxs by a pixel
1746                 out->mins[0] = SB_ReadFloat (&index) - 1;
1747                 out->mins[1] = SB_ReadFloat (&index) - 1;
1748                 out->mins[2] = SB_ReadFloat (&index) - 1;
1749                 out->maxs[0] = SB_ReadFloat (&index) + 1;
1750                 out->maxs[1] = SB_ReadFloat (&index) + 1;
1751                 out->maxs[2] = SB_ReadFloat (&index) + 1;
1752                 out->origin[0] = SB_ReadFloat (&index);
1753                 out->origin[1] = SB_ReadFloat (&index);
1754                 out->origin[2] = SB_ReadFloat (&index);
1755                 for (j = 0; j < hullinfo->filehulls; j++)
1756                         out->headnode[j] = SB_ReadInt (&index);
1757                 out->visleafs = SB_ReadInt (&index);
1758                 out->firstface = SB_ReadInt (&index);
1759                 out->numfaces = SB_ReadInt (&index);
1760         }
1761 }
1762
1763 static void Mod_Q1BSP_LoadEdges(lump_t *l)
1764 {
1765         dedge_t *in;
1766         medge_t *out;
1767         int     i, count;
1768
1769         in = (dedge_t *)(mod_base + l->fileofs);
1770         if (l->filelen % sizeof(*in))
1771                 Host_Error("Mod_Q1BSP_LoadEdges: funny lump size in %s",loadmodel->name);
1772         count = l->filelen / sizeof(*in);
1773         out = (medge_t *)Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1774
1775         loadmodel->brushq1.edges = out;
1776         loadmodel->brushq1.numedges = count;
1777
1778         for ( i=0 ; i<count ; i++, in++, out++)
1779         {
1780                 out->v[0] = (unsigned short)LittleShort(in->v[0]);
1781                 out->v[1] = (unsigned short)LittleShort(in->v[1]);
1782                 if (out->v[0] >= loadmodel->brushq1.numvertexes || out->v[1] >= loadmodel->brushq1.numvertexes)
1783                 {
1784                         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);
1785                         out->v[0] = 0;
1786                         out->v[1] = 0;
1787                 }
1788         }
1789 }
1790
1791 static void Mod_Q1BSP_LoadTexinfo(lump_t *l)
1792 {
1793         texinfo_t *in;
1794         mtexinfo_t *out;
1795         int i, j, k, count, miptex;
1796
1797         in = (texinfo_t *)(mod_base + l->fileofs);
1798         if (l->filelen % sizeof(*in))
1799                 Host_Error("Mod_Q1BSP_LoadTexinfo: funny lump size in %s",loadmodel->name);
1800         count = l->filelen / sizeof(*in);
1801         out = (mtexinfo_t *)Mem_Alloc(loadmodel->mempool, count * sizeof(*out));
1802
1803         loadmodel->brushq1.texinfo = out;
1804         loadmodel->brushq1.numtexinfo = count;
1805
1806         for (i = 0;i < count;i++, in++, out++)
1807         {
1808                 for (k = 0;k < 2;k++)
1809                         for (j = 0;j < 4;j++)
1810                                 out->vecs[k][j] = LittleFloat(in->vecs[k][j]);
1811
1812                 miptex = LittleLong(in->miptex);
1813                 out->flags = LittleLong(in->flags);
1814
1815                 out->texture = NULL;
1816                 if (loadmodel->data_textures)
1817                 {
1818                         if ((unsigned int) miptex >= (unsigned int) loadmodel->num_textures)
1819                                 Con_Printf("error in model \"%s\": invalid miptex index %i(of %i)\n", loadmodel->name, miptex, loadmodel->num_textures);
1820                         else
1821                                 out->texture = loadmodel->data_textures + miptex;
1822                 }
1823                 if (out->flags & TEX_SPECIAL)
1824                 {
1825                         // if texture chosen is NULL or the shader needs a lightmap,
1826                         // force to notexture water shader
1827                         if (out->texture == NULL || out->texture->basematerialflags & MATERIALFLAG_WALL)
1828                                 out->texture = loadmodel->data_textures + (loadmodel->num_textures - 1);
1829                 }
1830                 else
1831                 {
1832                         // if texture chosen is NULL, force to notexture
1833                         if (out->texture == NULL)
1834                                 out->texture = loadmodel->data_textures + (loadmodel->num_textures - 2);
1835                 }
1836         }
1837 }
1838
1839 #if 0
1840 void BoundPoly(int numverts, float *verts, vec3_t mins, vec3_t maxs)
1841 {
1842         int             i, j;
1843         float   *v;
1844
1845         mins[0] = mins[1] = mins[2] = 9999;
1846         maxs[0] = maxs[1] = maxs[2] = -9999;
1847         v = verts;
1848         for (i = 0;i < numverts;i++)
1849         {
1850                 for (j = 0;j < 3;j++, v++)
1851                 {
1852                         if (*v < mins[j])
1853                                 mins[j] = *v;
1854                         if (*v > maxs[j])
1855                                 maxs[j] = *v;
1856                 }
1857         }
1858 }
1859
1860 #define MAX_SUBDIVPOLYTRIANGLES 4096
1861 #define MAX_SUBDIVPOLYVERTS(MAX_SUBDIVPOLYTRIANGLES * 3)
1862
1863 static int subdivpolyverts, subdivpolytriangles;
1864 static int subdivpolyindex[MAX_SUBDIVPOLYTRIANGLES][3];
1865 static float subdivpolyvert[MAX_SUBDIVPOLYVERTS][3];
1866
1867 static int subdivpolylookupvert(vec3_t v)
1868 {
1869         int i;
1870         for (i = 0;i < subdivpolyverts;i++)
1871                 if (subdivpolyvert[i][0] == v[0]
1872                  && subdivpolyvert[i][1] == v[1]
1873                  && subdivpolyvert[i][2] == v[2])
1874                         return i;
1875         if (subdivpolyverts >= MAX_SUBDIVPOLYVERTS)
1876                 Host_Error("SubDividePolygon: ran out of vertices in buffer, please increase your r_subdivide_size");
1877         VectorCopy(v, subdivpolyvert[subdivpolyverts]);
1878         return subdivpolyverts++;
1879 }
1880
1881 static void SubdividePolygon(int numverts, float *verts)
1882 {
1883         int             i, i1, i2, i3, f, b, c, p;
1884         vec3_t  mins, maxs, front[256], back[256];
1885         float   m, *pv, *cv, dist[256], frac;
1886
1887         if (numverts > 250)
1888                 Host_Error("SubdividePolygon: ran out of verts in buffer");
1889
1890         BoundPoly(numverts, verts, mins, maxs);
1891
1892         for (i = 0;i < 3;i++)
1893         {
1894                 m = (mins[i] + maxs[i]) * 0.5;
1895                 m = r_subdivide_size.value * floor(m/r_subdivide_size.value + 0.5);
1896                 if (maxs[i] - m < 8)
1897                         continue;
1898                 if (m - mins[i] < 8)
1899                         continue;
1900
1901                 // cut it
1902                 for (cv = verts, c = 0;c < numverts;c++, cv += 3)
1903                         dist[c] = cv[i] - m;
1904
1905                 f = b = 0;
1906                 for (p = numverts - 1, c = 0, pv = verts + p * 3, cv = verts;c < numverts;p = c, c++, pv = cv, cv += 3)
1907                 {
1908                         if (dist[p] >= 0)
1909                         {
1910                                 VectorCopy(pv, front[f]);
1911                                 f++;
1912                         }
1913                         if (dist[p] <= 0)
1914                         {
1915                                 VectorCopy(pv, back[b]);
1916                                 b++;
1917                         }
1918                         if (dist[p] == 0 || dist[c] == 0)
1919                                 continue;
1920                         if ((dist[p] > 0) != (dist[c] > 0) )
1921                         {
1922                                 // clip point
1923                                 frac = dist[p] / (dist[p] - dist[c]);
1924                                 front[f][0] = back[b][0] = pv[0] + frac * (cv[0] - pv[0]);
1925                                 front[f][1] = back[b][1] = pv[1] + frac * (cv[1] - pv[1]);
1926                                 front[f][2] = back[b][2] = pv[2] + frac * (cv[2] - pv[2]);
1927                                 f++;
1928                                 b++;
1929                         }
1930                 }
1931
1932                 SubdividePolygon(f, front[0]);
1933                 SubdividePolygon(b, back[0]);
1934                 return;
1935         }
1936
1937         i1 = subdivpolylookupvert(verts);
1938         i2 = subdivpolylookupvert(verts + 3);
1939         for (i = 2;i < numverts;i++)
1940         {
1941                 if (subdivpolytriangles >= MAX_SUBDIVPOLYTRIANGLES)
1942                 {
1943                         Con_Print("SubdividePolygon: ran out of triangles in buffer, please increase your r_subdivide_size\n");
1944                         return;
1945                 }
1946
1947                 i3 = subdivpolylookupvert(verts + i * 3);
1948                 subdivpolyindex[subdivpolytriangles][0] = i1;
1949                 subdivpolyindex[subdivpolytriangles][1] = i2;
1950                 subdivpolyindex[subdivpolytriangles][2] = i3;
1951                 i2 = i3;
1952                 subdivpolytriangles++;
1953         }
1954 }
1955
1956 //Breaks a polygon up along axial 64 unit
1957 //boundaries so that turbulent and sky warps
1958 //can be done reasonably.
1959 static void Mod_Q1BSP_GenerateWarpMesh(msurface_t *surface)
1960 {
1961         int i, j;
1962         surfvertex_t *v;
1963         surfmesh_t *mesh;
1964
1965         subdivpolytriangles = 0;
1966         subdivpolyverts = 0;
1967         SubdividePolygon(surface->num_vertices, (surface->mesh->data_vertex3f + 3 * surface->num_firstvertex));
1968         if (subdivpolytriangles < 1)
1969                 Host_Error("Mod_Q1BSP_GenerateWarpMesh: no triangles?");
1970
1971         surface->mesh = mesh = Mem_Alloc(loadmodel->mempool, sizeof(surfmesh_t) + subdivpolytriangles * sizeof(int[3]) + subdivpolyverts * sizeof(surfvertex_t));
1972         mesh->num_vertices = subdivpolyverts;
1973         mesh->num_triangles = subdivpolytriangles;
1974         mesh->vertex = (surfvertex_t *)(mesh + 1);
1975         mesh->index = (int *)(mesh->vertex + mesh->num_vertices);
1976         memset(mesh->vertex, 0, mesh->num_vertices * sizeof(surfvertex_t));
1977
1978         for (i = 0;i < mesh->num_triangles;i++)
1979                 for (j = 0;j < 3;j++)
1980                         mesh->index[i*3+j] = subdivpolyindex[i][j];
1981
1982         for (i = 0, v = mesh->vertex;i < subdivpolyverts;i++, v++)
1983         {
1984                 VectorCopy(subdivpolyvert[i], v->v);
1985                 v->st[0] = DotProduct(v->v, surface->lightmapinfo->texinfo->vecs[0]);
1986                 v->st[1] = DotProduct(v->v, surface->lightmapinfo->texinfo->vecs[1]);
1987         }
1988 }
1989 #endif
1990
1991 static qboolean Mod_Q1BSP_AllocLightmapBlock(int *lineused, int totalwidth, int totalheight, int blockwidth, int blockheight, int *outx, int *outy)
1992 {
1993         int y, x2, y2;
1994         int bestx = totalwidth, besty = 0;
1995         // find the left-most space we can find
1996         for (y = 0;y <= totalheight - blockheight;y++)
1997         {
1998                 x2 = 0;
1999                 for (y2 = 0;y2 < blockheight;y2++)
2000                         x2 = max(x2, lineused[y+y2]);
2001                 if (bestx > x2)
2002                 {
2003                         bestx = x2;
2004                         besty = y;
2005                 }
2006         }
2007         // if the best was not good enough, return failure
2008         if (bestx > totalwidth - blockwidth)
2009                 return false;
2010         // we found a good spot
2011         if (outx)
2012                 *outx = bestx;
2013         if (outy)
2014                 *outy = besty;
2015         // now mark the space used
2016         for (y2 = 0;y2 < blockheight;y2++)
2017                 lineused[besty+y2] = bestx + blockwidth;
2018         // return success
2019         return true;
2020 }
2021
2022 static void Mod_Q1BSP_LoadFaces(lump_t *l)
2023 {
2024         dface_t *in;
2025         msurface_t *surface;
2026         int i, j, count, surfacenum, planenum, smax, tmax, ssize, tsize, firstedge, numedges, totalverts, totaltris, lightmapnumber;
2027         float texmins[2], texmaxs[2], val, lightmaptexcoordscale;
2028 #define LIGHTMAPSIZE 256
2029         rtexture_t *lightmaptexture, *deluxemaptexture;
2030         int lightmap_lineused[LIGHTMAPSIZE];
2031
2032         in = (dface_t *)(mod_base + l->fileofs);
2033         if (l->filelen % sizeof(*in))
2034                 Host_Error("Mod_Q1BSP_LoadFaces: funny lump size in %s",loadmodel->name);
2035         count = l->filelen / sizeof(*in);
2036         loadmodel->data_surfaces = (msurface_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_t));
2037         loadmodel->data_surfaces_lightmapinfo = (msurface_lightmapinfo_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(msurface_lightmapinfo_t));
2038
2039         loadmodel->num_surfaces = count;
2040
2041         totalverts = 0;
2042         totaltris = 0;
2043         for (surfacenum = 0, in = (dface_t *)(mod_base + l->fileofs);surfacenum < count;surfacenum++, in++)
2044         {
2045                 numedges = LittleShort(in->numedges);
2046                 totalverts += numedges;
2047                 totaltris += numedges - 2;
2048         }
2049
2050         Mod_AllocSurfMesh(loadmodel->mempool, totalverts, totaltris, true, false, false);
2051
2052         lightmaptexture = NULL;
2053         deluxemaptexture = r_texture_blanknormalmap;
2054         lightmapnumber = 1;
2055         lightmaptexcoordscale = 1.0f / (float)LIGHTMAPSIZE;
2056
2057         totalverts = 0;
2058         totaltris = 0;
2059         for (surfacenum = 0, in = (dface_t *)(mod_base + l->fileofs), surface = loadmodel->data_surfaces;surfacenum < count;surfacenum++, in++, surface++)
2060         {
2061                 surface->lightmapinfo = loadmodel->data_surfaces_lightmapinfo + surfacenum;
2062
2063                 // FIXME: validate edges, texinfo, etc?
2064                 firstedge = LittleLong(in->firstedge);
2065                 numedges = LittleShort(in->numedges);
2066                 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)
2067                         Host_Error("Mod_Q1BSP_LoadFaces: invalid edge range (firstedge %i, numedges %i, model edges %i)", firstedge, numedges, loadmodel->brushq1.numsurfedges);
2068                 i = LittleShort(in->texinfo);
2069                 if ((unsigned int) i >= (unsigned int) loadmodel->brushq1.numtexinfo)
2070                         Host_Error("Mod_Q1BSP_LoadFaces: invalid texinfo index %i(model has %i texinfos)", i, loadmodel->brushq1.numtexinfo);
2071                 surface->lightmapinfo->texinfo = loadmodel->brushq1.texinfo + i;
2072                 surface->texture = surface->lightmapinfo->texinfo->texture;
2073
2074                 planenum = LittleShort(in->planenum);
2075                 if ((unsigned int) planenum >= (unsigned int) loadmodel->brush.num_planes)
2076                         Host_Error("Mod_Q1BSP_LoadFaces: invalid plane index %i (model has %i planes)", planenum, loadmodel->brush.num_planes);
2077
2078                 //surface->flags = surface->texture->flags;
2079                 //if (LittleShort(in->side))
2080                 //      surface->flags |= SURF_PLANEBACK;
2081                 //surface->plane = loadmodel->brush.data_planes + planenum;
2082
2083                 surface->num_firstvertex = totalverts;
2084                 surface->num_vertices = numedges;
2085                 surface->num_firsttriangle = totaltris;
2086                 surface->num_triangles = numedges - 2;
2087                 totalverts += numedges;
2088                 totaltris += numedges - 2;
2089
2090                 // convert edges back to a normal polygon
2091                 for (i = 0;i < surface->num_vertices;i++)
2092                 {
2093                         int lindex = loadmodel->brushq1.surfedges[firstedge + i];
2094                         float s, t;
2095                         if (lindex > 0)
2096                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[lindex].v[0]].position, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3);
2097                         else
2098                                 VectorCopy(loadmodel->brushq1.vertexes[loadmodel->brushq1.edges[-lindex].v[1]].position, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3);
2099                         s = DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[0]) + surface->lightmapinfo->texinfo->vecs[0][3];
2100                         t = DotProduct(((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3), surface->lightmapinfo->texinfo->vecs[1]) + surface->lightmapinfo->texinfo->vecs[1][3];
2101                         (loadmodel->surfmesh.data_texcoordtexture2f + 2 * surface->num_firstvertex)[i * 2 + 0] = s / surface->texture->width;
2102                         (loadmodel->surfmesh.data_texcoordtexture2f + 2 * surface->num_firstvertex)[i * 2 + 1] = t / surface->texture->height;
2103                         (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 0] = 0;
2104                         (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 1] = 0;
2105                         (loadmodel->surfmesh.data_lightmapoffsets + surface->num_firstvertex)[i] = 0;
2106                 }
2107
2108                 for (i = 0;i < surface->num_triangles;i++)
2109                 {
2110                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 0] = 0 + surface->num_firstvertex;
2111                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 1] = i + 1 + surface->num_firstvertex;
2112                         (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle)[i * 3 + 2] = i + 2 + surface->num_firstvertex;
2113                 }
2114
2115                 // compile additional data about the surface geometry
2116                 Mod_BuildTextureVectorsAndNormals(surface->num_firstvertex, surface->num_vertices, surface->num_triangles, loadmodel->surfmesh.data_vertex3f, loadmodel->surfmesh.data_texcoordtexture2f, (loadmodel->surfmesh.data_element3i + 3 * surface->num_firsttriangle), loadmodel->surfmesh.data_svector3f, loadmodel->surfmesh.data_tvector3f, loadmodel->surfmesh.data_normal3f, true);
2117                 BoxFromPoints(surface->mins, surface->maxs, surface->num_vertices, (loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex));
2118
2119                 // generate surface extents information
2120                 texmins[0] = texmaxs[0] = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex), surface->lightmapinfo->texinfo->vecs[0]) + surface->lightmapinfo->texinfo->vecs[0][3];
2121                 texmins[1] = texmaxs[1] = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex), surface->lightmapinfo->texinfo->vecs[1]) + surface->lightmapinfo->texinfo->vecs[1][3];
2122                 for (i = 1;i < surface->num_vertices;i++)
2123                 {
2124                         for (j = 0;j < 2;j++)
2125                         {
2126                                 val = DotProduct((loadmodel->surfmesh.data_vertex3f + 3 * surface->num_firstvertex) + i * 3, surface->lightmapinfo->texinfo->vecs[j]) + surface->lightmapinfo->texinfo->vecs[j][3];
2127                                 texmins[j] = min(texmins[j], val);
2128                                 texmaxs[j] = max(texmaxs[j], val);
2129                         }
2130                 }
2131                 for (i = 0;i < 2;i++)
2132                 {
2133                         surface->lightmapinfo->texturemins[i] = (int) floor(texmins[i] / 16.0) * 16;
2134                         surface->lightmapinfo->extents[i] = (int) ceil(texmaxs[i] / 16.0) * 16 - surface->lightmapinfo->texturemins[i];
2135                 }
2136
2137                 smax = surface->lightmapinfo->extents[0] >> 4;
2138                 tmax = surface->lightmapinfo->extents[1] >> 4;
2139                 ssize = (surface->lightmapinfo->extents[0] >> 4) + 1;
2140                 tsize = (surface->lightmapinfo->extents[1] >> 4) + 1;
2141
2142                 // lighting info
2143                 for (i = 0;i < MAXLIGHTMAPS;i++)
2144                         surface->lightmapinfo->styles[i] = in->styles[i];
2145                 surface->lightmaptexture = NULL;
2146                 surface->deluxemaptexture = r_texture_blanknormalmap;
2147                 i = LittleLong(in->lightofs);
2148                 if (i == -1)
2149                 {
2150                         surface->lightmapinfo->samples = NULL;
2151                         // give non-lightmapped water a 1x white lightmap
2152                         if ((surface->texture->basematerialflags & MATERIALFLAG_WATER) && (surface->lightmapinfo->texinfo->flags & TEX_SPECIAL) && ssize <= 256 && tsize <= 256)
2153                         {
2154                                 surface->lightmapinfo->samples = (unsigned char *)Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
2155                                 surface->lightmapinfo->styles[0] = 0;
2156                                 memset(surface->lightmapinfo->samples, 128, ssize * tsize * 3);
2157                         }
2158                 }
2159                 else if (loadmodel->brush.ishlbsp) // LordHavoc: HalfLife map (bsp version 30)
2160                         surface->lightmapinfo->samples = loadmodel->brushq1.lightdata + i;
2161                 else // LordHavoc: white lighting (bsp version 29)
2162                 {
2163                         surface->lightmapinfo->samples = loadmodel->brushq1.lightdata + (i * 3);
2164                         if (loadmodel->brushq1.nmaplightdata)
2165                                 surface->lightmapinfo->nmapsamples = loadmodel->brushq1.nmaplightdata + (i * 3);
2166                 }
2167
2168                 // check if we should apply a lightmap to this
2169                 if (!(surface->lightmapinfo->texinfo->flags & TEX_SPECIAL) || surface->lightmapinfo->samples)
2170                 {
2171                         int i, iu, iv, lightmapx, lightmapy;
2172                         float u, v, ubase, vbase, uscale, vscale;
2173
2174                         if (ssize > 256 || tsize > 256)
2175                                 Host_Error("Bad surface extents");
2176                         // force lightmap upload on first time seeing the surface
2177                         surface->cached_dlight = true;
2178                         // stainmap for permanent marks on walls
2179                         surface->lightmapinfo->stainsamples = (unsigned char *)Mem_Alloc(loadmodel->mempool, ssize * tsize * 3);
2180                         // clear to white
2181                         memset(surface->lightmapinfo->stainsamples, 255, ssize * tsize * 3);
2182
2183                         // find a place for this lightmap
2184                         if (!lightmaptexture || !Mod_Q1BSP_AllocLightmapBlock(lightmap_lineused, LIGHTMAPSIZE, LIGHTMAPSIZE, ssize, tsize, &lightmapx, &lightmapy))
2185                         {
2186                                 // could not find room, make a new lightmap
2187                                 lightmaptexture = R_LoadTexture2D(loadmodel->texturepool, va("lightmap%i", lightmapnumber), LIGHTMAPSIZE, LIGHTMAPSIZE, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
2188                                 if (loadmodel->brushq1.nmaplightdata)
2189                                         deluxemaptexture = R_LoadTexture2D(loadmodel->texturepool, va("deluxemap%i", lightmapnumber), LIGHTMAPSIZE, LIGHTMAPSIZE, NULL, loadmodel->brushq1.lightmaprgba ? TEXTYPE_RGBA : TEXTYPE_RGB, TEXF_FORCELINEAR | TEXF_PRECACHE, NULL);
2190                                 lightmapnumber++;
2191                                 memset(lightmap_lineused, 0, sizeof(lightmap_lineused));
2192                                 Mod_Q1BSP_AllocLightmapBlock(lightmap_lineused, LIGHTMAPSIZE, LIGHTMAPSIZE, ssize, tsize, &lightmapx, &lightmapy);
2193                         }
2194
2195                         surface->lightmaptexture = lightmaptexture;
2196                         surface->deluxemaptexture = deluxemaptexture;
2197                         surface->lightmapinfo->lightmaporigin[0] = lightmapx;
2198                         surface->lightmapinfo->lightmaporigin[1] = lightmapy;
2199
2200                         ubase = lightmapx * lightmaptexcoordscale;
2201                         vbase = lightmapy * lightmaptexcoordscale;
2202                         uscale = lightmaptexcoordscale;
2203                         vscale = lightmaptexcoordscale;
2204
2205                         for (i = 0;i < surface->num_vertices;i++)
2206                         {
2207                                 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);
2208                                 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);
2209                                 (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 0] = u * uscale + ubase;
2210                                 (loadmodel->surfmesh.data_texcoordlightmap2f + 2 * surface->num_firstvertex)[i * 2 + 1] = v * vscale + vbase;
2211                                 // LordHavoc: calc lightmap data offset for vertex lighting to use
2212                                 iu = (int) u;
2213                                 iv = (int) v;
2214                                 (loadmodel->surfmesh.data_lightmapoffsets + surface->num_firstvertex)[i] = (bound(0, iv, tmax) * ssize + bound(0, iu, smax)) * 3;
2215                         }
2216                 }
2217         }
2218 }
2219
2220 static void Mod_Q1BSP_LoadNodes_RecursiveSetParent(mnode_t *node, mnode_t *parent)
2221 {
2222         //if (node->parent)
2223         //      Host_Error("Mod_Q1BSP_LoadNodes_RecursiveSetParent: runaway recursion");
2224         node->parent = parent;
2225         if (node->plane)
2226         {
2227                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
2228                 Mod_Q1BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
2229         }
2230 }
2231
2232 static void Mod_Q1BSP_LoadNodes(lump_t *l)
2233 {
2234         int                     i, j, count, p;
2235         dnode_t         *in;
2236         mnode_t         *out;
2237
2238         in = (dnode_t *)(mod_base + l->fileofs);
2239         if (l->filelen % sizeof(*in))
2240                 Host_Error("Mod_Q1BSP_LoadNodes: funny lump size in %s",loadmodel->name);
2241         count = l->filelen / sizeof(*in);
2242         out = (mnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2243
2244         loadmodel->brush.data_nodes = out;
2245         loadmodel->brush.num_nodes = count;
2246
2247         for ( i=0 ; i<count ; i++, in++, out++)
2248         {
2249                 for (j=0 ; j<3 ; j++)
2250                 {
2251                         out->mins[j] = LittleShort(in->mins[j]);
2252                         out->maxs[j] = LittleShort(in->maxs[j]);
2253                 }
2254
2255                 p = LittleLong(in->planenum);
2256                 out->plane = loadmodel->brush.data_planes + p;
2257
2258                 out->firstsurface = LittleShort(in->firstface);
2259                 out->numsurfaces = LittleShort(in->numfaces);
2260
2261                 for (j=0 ; j<2 ; j++)
2262                 {
2263                         p = LittleShort(in->children[j]);
2264                         if (p >= 0)
2265                                 out->children[j] = loadmodel->brush.data_nodes + p;
2266                         else
2267                                 out->children[j] = (mnode_t *)(loadmodel->brush.data_leafs + (-1 - p));
2268                 }
2269         }
2270
2271         Mod_Q1BSP_LoadNodes_RecursiveSetParent(loadmodel->brush.data_nodes, NULL);      // sets nodes and leafs
2272 }
2273
2274 static void Mod_Q1BSP_LoadLeafs(lump_t *l)
2275 {
2276         dleaf_t *in;
2277         mleaf_t *out;
2278         int i, j, count, p;
2279
2280         in = (dleaf_t *)(mod_base + l->fileofs);
2281         if (l->filelen % sizeof(*in))
2282                 Host_Error("Mod_Q1BSP_LoadLeafs: funny lump size in %s",loadmodel->name);
2283         count = l->filelen / sizeof(*in);
2284         out = (mleaf_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2285
2286         loadmodel->brush.data_leafs = out;
2287         loadmodel->brush.num_leafs = count;
2288         // get visleafs from the submodel data
2289         loadmodel->brush.num_pvsclusters = loadmodel->brushq1.submodels[0].visleafs;
2290         loadmodel->brush.num_pvsclusterbytes = (loadmodel->brush.num_pvsclusters+7)>>3;
2291         loadmodel->brush.data_pvsclusters = (unsigned char *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2292         memset(loadmodel->brush.data_pvsclusters, 0xFF, loadmodel->brush.num_pvsclusters * loadmodel->brush.num_pvsclusterbytes);
2293
2294         for ( i=0 ; i<count ; i++, in++, out++)
2295         {
2296                 for (j=0 ; j<3 ; j++)
2297                 {
2298                         out->mins[j] = LittleShort(in->mins[j]);
2299                         out->maxs[j] = LittleShort(in->maxs[j]);
2300                 }
2301
2302                 // FIXME: this function could really benefit from some error checking
2303
2304                 out->contents = LittleLong(in->contents);
2305
2306                 out->firstleafsurface = loadmodel->brush.data_leafsurfaces + LittleShort(in->firstmarksurface);
2307                 out->numleafsurfaces = LittleShort(in->nummarksurfaces);
2308                 if (out->firstleafsurface < 0 || LittleShort(in->firstmarksurface) + out->numleafsurfaces > loadmodel->brush.num_leafsurfaces)
2309                 {
2310                         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);
2311                         out->firstleafsurface = NULL;
2312                         out->numleafsurfaces = 0;
2313                 }
2314
2315                 out->clusterindex = i - 1;
2316                 if (out->clusterindex >= loadmodel->brush.num_pvsclusters)
2317                         out->clusterindex = -1;
2318
2319                 p = LittleLong(in->visofs);
2320                 // ignore visofs errors on leaf 0 (solid)
2321                 if (p >= 0 && out->clusterindex >= 0)
2322                 {
2323                         if (p >= loadmodel->brushq1.num_compressedpvs)
2324                                 Con_Print("Mod_Q1BSP_LoadLeafs: invalid visofs\n");
2325                         else
2326                                 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);
2327                 }
2328
2329                 for (j = 0;j < 4;j++)
2330                         out->ambient_sound_level[j] = in->ambient_level[j];
2331
2332                 // FIXME: Insert caustics here
2333         }
2334 }
2335
2336 static void Mod_Q1BSP_LoadClipnodes(lump_t *l, hullinfo_t *hullinfo)
2337 {
2338         dclipnode_t *in, *out;
2339         int                     i, count;
2340         hull_t          *hull;
2341
2342         in = (dclipnode_t *)(mod_base + l->fileofs);
2343         if (l->filelen % sizeof(*in))
2344                 Host_Error("Mod_Q1BSP_LoadClipnodes: funny lump size in %s",loadmodel->name);
2345         count = l->filelen / sizeof(*in);
2346         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, count*sizeof(*out));
2347
2348         loadmodel->brushq1.clipnodes = out;
2349         loadmodel->brushq1.numclipnodes = count;
2350
2351         for (i = 1; i < hullinfo->numhulls; i++)
2352         {
2353                 hull = &loadmodel->brushq1.hulls[i];
2354                 hull->clipnodes = out;
2355                 hull->firstclipnode = 0;
2356                 hull->lastclipnode = count-1;
2357                 hull->planes = loadmodel->brush.data_planes;
2358                 hull->clip_mins[0] = hullinfo->hullsizes[i][0][0];
2359                 hull->clip_mins[1] = hullinfo->hullsizes[i][0][1];
2360                 hull->clip_mins[2] = hullinfo->hullsizes[i][0][2];
2361                 hull->clip_maxs[0] = hullinfo->hullsizes[i][1][0];
2362                 hull->clip_maxs[1] = hullinfo->hullsizes[i][1][1];
2363                 hull->clip_maxs[2] = hullinfo->hullsizes[i][1][2];
2364                 VectorSubtract(hull->clip_maxs, hull->clip_mins, hull->clip_size);
2365         }
2366
2367         for (i=0 ; i<count ; i++, out++, in++)
2368         {
2369                 out->planenum = LittleLong(in->planenum);
2370                 out->children[0] = LittleShort(in->children[0]);
2371                 out->children[1] = LittleShort(in->children[1]);
2372                 if (out->planenum < 0 || out->planenum >= loadmodel->brush.num_planes)
2373                         Host_Error("Corrupt clipping hull(out of range planenum)");
2374                 if (out->children[0] >= count || out->children[1] >= count)
2375                         Host_Error("Corrupt clipping hull(out of range child)");
2376         }
2377 }
2378
2379 //Duplicate the drawing hull structure as a clipping hull
2380 static void Mod_Q1BSP_MakeHull0(void)
2381 {
2382         mnode_t         *in;
2383         dclipnode_t *out;
2384         int                     i;
2385         hull_t          *hull;
2386
2387         hull = &loadmodel->brushq1.hulls[0];
2388
2389         in = loadmodel->brush.data_nodes;
2390         out = (dclipnode_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_nodes * sizeof(dclipnode_t));
2391
2392         hull->clipnodes = out;
2393         hull->firstclipnode = 0;
2394         hull->lastclipnode = loadmodel->brush.num_nodes - 1;
2395         hull->planes = loadmodel->brush.data_planes;
2396
2397         for (i = 0;i < loadmodel->brush.num_nodes;i++, out++, in++)
2398         {
2399                 out->planenum = in->plane - loadmodel->brush.data_planes;
2400                 out->children[0] = in->children[0]->plane ? in->children[0] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[0])->contents;
2401                 out->children[1] = in->children[1]->plane ? in->children[1] - loadmodel->brush.data_nodes : ((mleaf_t *)in->children[1])->contents;
2402         }
2403 }
2404
2405 static void Mod_Q1BSP_LoadLeaffaces(lump_t *l)
2406 {
2407         int i, j;
2408         short *in;
2409
2410         in = (short *)(mod_base + l->fileofs);
2411         if (l->filelen % sizeof(*in))
2412                 Host_Error("Mod_Q1BSP_LoadLeaffaces: funny lump size in %s",loadmodel->name);
2413         loadmodel->brush.num_leafsurfaces = l->filelen / sizeof(*in);
2414         loadmodel->brush.data_leafsurfaces = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_leafsurfaces * sizeof(int));
2415
2416         for (i = 0;i < loadmodel->brush.num_leafsurfaces;i++)
2417         {
2418                 j = (unsigned) LittleShort(in[i]);
2419                 if (j >= loadmodel->num_surfaces)
2420                         Host_Error("Mod_Q1BSP_LoadLeaffaces: bad surface number");
2421                 loadmodel->brush.data_leafsurfaces[i] = j;
2422         }
2423 }
2424
2425 static void Mod_Q1BSP_LoadSurfedges(lump_t *l)
2426 {
2427         int             i;
2428         int             *in;
2429
2430         in = (int *)(mod_base + l->fileofs);
2431         if (l->filelen % sizeof(*in))
2432                 Host_Error("Mod_Q1BSP_LoadSurfedges: funny lump size in %s",loadmodel->name);
2433         loadmodel->brushq1.numsurfedges = l->filelen / sizeof(*in);
2434         loadmodel->brushq1.surfedges = (int *)Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numsurfedges * sizeof(int));
2435
2436         for (i = 0;i < loadmodel->brushq1.numsurfedges;i++)
2437                 loadmodel->brushq1.surfedges[i] = LittleLong(in[i]);
2438 }
2439
2440
2441 static void Mod_Q1BSP_LoadPlanes(lump_t *l)
2442 {
2443         int                     i;
2444         mplane_t        *out;
2445         dplane_t        *in;
2446
2447         in = (dplane_t *)(mod_base + l->fileofs);
2448         if (l->filelen % sizeof(*in))
2449                 Host_Error("Mod_Q1BSP_LoadPlanes: funny lump size in %s", loadmodel->name);
2450
2451         loadmodel->brush.num_planes = l->filelen / sizeof(*in);
2452         loadmodel->brush.data_planes = out = (mplane_t *)Mem_Alloc(loadmodel->mempool, loadmodel->brush.num_planes * sizeof(*out));
2453
2454         for (i = 0;i < loadmodel->brush.num_planes;i++, in++, out++)
2455         {
2456                 out->normal[0] = LittleFloat(in->normal[0]);
2457                 out->normal[1] = LittleFloat(in->normal[1]);
2458                 out->normal[2] = LittleFloat(in->normal[2]);
2459                 out->dist = LittleFloat(in->dist);
2460
2461                 PlaneClassify(out);
2462         }
2463 }
2464
2465 static void Mod_Q1BSP_LoadMapBrushes(void)
2466 {
2467 #if 0
2468 // unfinished
2469         int submodel, numbrushes;
2470         qboolean firstbrush;
2471         char *text, *maptext;
2472         char mapfilename[MAX_QPATH];
2473         FS_StripExtension (loadmodel->name, mapfilename, sizeof (mapfilename));
2474         strlcat (mapfilename, ".map", sizeof (mapfilename));
2475         maptext = (unsigned char*) FS_LoadFile(mapfilename, tempmempool, false, NULL);
2476         if (!maptext)
2477                 return;
2478         text = maptext;
2479         if (!COM_ParseToken(&data, false))
2480                 return; // error
2481         submodel = 0;
2482         for (;;)
2483         {
2484                 if (!COM_ParseToken(&data, false))
2485                         break;
2486                 if (com_token[0] != '{')
2487                         return; // error
2488                 // entity
2489                 firstbrush = true;
2490                 numbrushes = 0;
2491                 maxbrushes = 256;
2492                 brushes = Mem_Alloc(loadmodel->mempool, maxbrushes * sizeof(mbrush_t));
2493                 for (;;)
2494                 {
2495                         if (!COM_ParseToken(&data, false))
2496                                 return; // error
2497                         if (com_token[0] == '}')
2498                                 break; // end of entity
2499                         if (com_token[0] == '{')
2500                         {
2501                                 // brush
2502                                 if (firstbrush)
2503                                 {
2504                                         if (submodel)
2505                                         {
2506                                                 if (submodel > loadmodel->brush.numsubmodels)
2507                                                 {
2508                                                         Con_Printf("Mod_Q1BSP_LoadMapBrushes: .map has more submodels than .bsp!\n");
2509                                                         model = NULL;
2510                                                 }
2511                                                 else
2512                                                         model = loadmodel->brush.submodels[submodel];
2513                                         }
2514                                         else
2515                                                 model = loadmodel;
2516                                 }
2517                                 for (;;)
2518                                 {
2519                                         if (!COM_ParseToken(&data, false))
2520                                                 return; // error
2521                                         if (com_token[0] == '}')
2522                                                 break; // end of brush
2523                                         // each brush face should be this format:
2524                                         // ( x y z ) ( x y z ) ( x y z ) texture scroll_s scroll_t rotateangle scale_s scale_t
2525                                         // FIXME: support hl .map format
2526                                         for (pointnum = 0;pointnum < 3;pointnum++)
2527                                         {
2528                                                 COM_ParseToken(&data, false);
2529                                                 for (componentnum = 0;componentnum < 3;componentnum++)
2530                                                 {
2531                                                         COM_ParseToken(&data, false);
2532                                                         point[pointnum][componentnum] = atof(com_token);
2533                                                 }
2534                                                 COM_ParseToken(&data, false);
2535                                         }
2536                                         COM_ParseToken(&data, false);
2537                                         strlcpy(facetexture, com_token, sizeof(facetexture));
2538                                         COM_ParseToken(&data, false);
2539                                         //scroll_s = atof(com_token);
2540                                         COM_ParseToken(&data, false);
2541                                         //scroll_t = atof(com_token);
2542                                         COM_ParseToken(&data, false);
2543                                         //rotate = atof(com_token);
2544                                         COM_ParseToken(&data, false);
2545                                         //scale_s = atof(com_token);
2546                                         COM_ParseToken(&data, false);
2547                                         //scale_t = atof(com_token);
2548                                         TriangleNormal(point[0], point[1], point[2], planenormal);
2549                                         VectorNormalizeDouble(planenormal);
2550                                         planedist = DotProduct(point[0], planenormal);
2551                                         //ChooseTexturePlane(planenormal, texturevector[0], texturevector[1]);
2552                                 }
2553                                 continue;
2554                         }
2555                 }
2556         }
2557 #endif
2558 }
2559
2560
2561 #define MAX_PORTALPOINTS 64
2562
2563 typedef struct portal_s
2564 {
2565         mplane_t plane;
2566         mnode_t *nodes[2];              // [0] = front side of plane
2567         struct portal_s *next[2];
2568         int numpoints;
2569         double points[3*MAX_PORTALPOINTS];
2570         struct portal_s *chain; // all portals are linked into a list
2571 }
2572 portal_t;
2573
2574 static portal_t *portalchain;
2575
2576 /*
2577 ===========
2578 AllocPortal
2579 ===========
2580 */
2581 static portal_t *AllocPortal(void)
2582 {
2583         portal_t *p;
2584         p = (portal_t *)Mem_Alloc(loadmodel->mempool, sizeof(portal_t));
2585         p->chain = portalchain;
2586         portalchain = p;
2587         return p;
2588 }
2589
2590 static void FreePortal(portal_t *p)
2591 {
2592         Mem_Free(p);
2593 }
2594
2595 static void Mod_Q1BSP_RecursiveRecalcNodeBBox(mnode_t *node)
2596 {
2597         // process only nodes (leafs already had their box calculated)
2598         if (!node->plane)
2599                 return;
2600
2601         // calculate children first
2602         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[0]);
2603         Mod_Q1BSP_RecursiveRecalcNodeBBox(node->children[1]);
2604
2605         // make combined bounding box from children
2606         node->mins[0] = min(node->children[0]->mins[0], node->children[1]->mins[0]);
2607         node->mins[1] = min(node->children[0]->mins[1], node->children[1]->mins[1]);
2608         node->mins[2] = min(node->children[0]->mins[2], node->children[1]->mins[2]);
2609         node->maxs[0] = max(node->children[0]->maxs[0], node->children[1]->maxs[0]);
2610         node->maxs[1] = max(node->children[0]->maxs[1], node->children[1]->maxs[1]);
2611         node->maxs[2] = max(node->children[0]->maxs[2], node->children[1]->maxs[2]);
2612 }
2613
2614 static void Mod_Q1BSP_FinalizePortals(void)
2615 {
2616         int i, j, numportals, numpoints;
2617         portal_t *p, *pnext;
2618         mportal_t *portal;
2619         mvertex_t *point;
2620         mleaf_t *leaf, *endleaf;
2621
2622         // tally up portal and point counts and recalculate bounding boxes for all
2623         // leafs (because qbsp is very sloppy)
2624         leaf = loadmodel->brush.data_leafs;
2625         endleaf = leaf + loadmodel->brush.num_leafs;
2626         for (;leaf < endleaf;leaf++)
2627         {
2628                 VectorSet(leaf->mins,  2000000000,  2000000000,  2000000000);
2629                 VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
2630         }
2631         p = portalchain;
2632         numportals = 0;
2633         numpoints = 0;
2634         while (p)
2635         {
2636                 // note: this check must match the one below or it will usually corrupt memory
2637                 // 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
2638                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1] && ((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2639                 {
2640                         numportals += 2;
2641                         numpoints += p->numpoints * 2;
2642                 }
2643                 p = p->chain;
2644         }
2645         loadmodel->brush.data_portals = (mportal_t *)Mem_Alloc(loadmodel->mempool, numportals * sizeof(mportal_t) + numpoints * sizeof(mvertex_t));
2646         loadmodel->brush.num_portals = numportals;
2647         loadmodel->brush.data_portalpoints = (mvertex_t *)((unsigned char *) loadmodel->brush.data_portals + numportals * sizeof(mportal_t));
2648         loadmodel->brush.num_portalpoints = numpoints;
2649         // clear all leaf portal chains
2650         for (i = 0;i < loadmodel->brush.num_leafs;i++)
2651                 loadmodel->brush.data_leafs[i].portals = NULL;
2652         // process all portals in the global portal chain, while freeing them
2653         portal = loadmodel->brush.data_portals;
2654         point = loadmodel->brush.data_portalpoints;
2655         p = portalchain;
2656         portalchain = NULL;
2657         while (p)
2658         {
2659                 pnext = p->chain;
2660
2661                 if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1])
2662                 {
2663                         // note: this check must match the one above or it will usually corrupt memory
2664                         // 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
2665                         if (((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
2666                         {
2667                                 // first make the back to front portal(forward portal)
2668                                 portal->points = point;
2669                                 portal->numpoints = p->numpoints;
2670                                 portal->plane.dist = p->plane.dist;
2671                                 VectorCopy(p->plane.normal, portal->plane.normal);
2672                                 portal->here = (mleaf_t *)p->nodes[1];
2673                                 portal->past = (mleaf_t *)p->nodes[0];
2674                                 // copy points
2675                                 for (j = 0;j < portal->numpoints;j++)
2676                                 {
2677                                         VectorCopy(p->points + j*3, point->position);
2678                                         point++;
2679                                 }
2680                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2681                                 PlaneClassify(&portal->plane);
2682
2683                                 // link into leaf's portal chain
2684                                 portal->next = portal->here->portals;
2685                                 portal->here->portals = portal;
2686
2687                                 // advance to next portal
2688                                 portal++;
2689
2690                                 // then make the front to back portal(backward portal)
2691                                 portal->points = point;
2692                                 portal->numpoints = p->numpoints;
2693                                 portal->plane.dist = -p->plane.dist;
2694                                 VectorNegate(p->plane.normal, portal->plane.normal);
2695                                 portal->here = (mleaf_t *)p->nodes[0];
2696                                 portal->past = (mleaf_t *)p->nodes[1];
2697                                 // copy points
2698                                 for (j = portal->numpoints - 1;j >= 0;j--)
2699                                 {
2700                                         VectorCopy(p->points + j*3, point->position);
2701                                         point++;
2702                                 }
2703                                 BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
2704                                 PlaneClassify(&portal->plane);
2705
2706                                 // link into leaf's portal chain
2707                                 portal->next = portal->here->portals;
2708                                 portal->here->portals = portal;
2709
2710                                 // advance to next portal
2711                                 portal++;
2712                         }
2713                         // add the portal's polygon points to the leaf bounding boxes
2714                         for (i = 0;i < 2;i++)
2715                         {
2716                                 leaf = (mleaf_t *)p->nodes[i];
2717                                 for (j = 0;j < p->numpoints;j++)
2718                                 {
2719                                         if (leaf->mins[0] > p->points[j*3+0]) leaf->mins[0] = p->points[j*3+0];
2720                                         if (leaf->mins[1] > p->points[j*3+1]) leaf->mins[1] = p->points[j*3+1];
2721                                         if (leaf->mins[2] > p->points[j*3+2]) leaf->mins[2] = p->points[j*3+2];
2722                                         if (leaf->maxs[0] < p->points[j*3+0]) leaf->maxs[0] = p->points[j*3+0];
2723                                         if (leaf->maxs[1] < p->points[j*3+1]) leaf->maxs[1] = p->points[j*3+1];
2724                                         if (leaf->maxs[2] < p->points[j*3+2]) leaf->maxs[2] = p->points[j*3+2];
2725                                 }
2726                         }
2727                 }
2728                 FreePortal(p);
2729                 p = pnext;
2730         }
2731         // now recalculate the node bounding boxes from the leafs
2732         Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brush.data_nodes);
2733 }
2734
2735 /*
2736 =============
2737 AddPortalToNodes
2738 =============
2739 */
2740 static void AddPortalToNodes(portal_t *p, mnode_t *front, mnode_t *back)
2741 {
2742         if (!front)
2743                 Host_Error("AddPortalToNodes: NULL front node");
2744         if (!back)
2745                 Host_Error("AddPortalToNodes: NULL back node");
2746         if (p->nodes[0] || p->nodes[1])
2747                 Host_Error("AddPortalToNodes: already included");
2748         // 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
2749
2750         p->nodes[0] = front;
2751         p->next[0] = (portal_t *)front->portals;
2752         front->portals = (mportal_t *)p;
2753
2754         p->nodes[1] = back;
2755         p->next[1] = (portal_t *)back->portals;
2756         back->portals = (mportal_t *)p;
2757 }
2758
2759 /*
2760 =============
2761 RemovePortalFromNode
2762 =============
2763 */
2764 static void RemovePortalFromNodes(portal_t *portal)
2765 {
2766         int i;
2767         mnode_t *node;
2768         void **portalpointer;
2769         portal_t *t;
2770         for (i = 0;i < 2;i++)
2771         {
2772                 node = portal->nodes[i];
2773
2774                 portalpointer = (void **) &node->portals;
2775                 while (1)
2776                 {
2777                         t = (portal_t *)*portalpointer;
2778                         if (!t)
2779                                 Host_Error("RemovePortalFromNodes: portal not in leaf");
2780
2781                         if (t == portal)
2782                         {
2783                                 if (portal->nodes[0] == node)
2784                                 {
2785                                         *portalpointer = portal->next[0];
2786                                         portal->nodes[0] = NULL;
2787                                 }
2788                                 else if (portal->nodes[1] == node)
2789                                 {
2790                                         *portalpointer = portal->next[1];
2791                                         portal->nodes[1] = NULL;
2792                                 }
2793                                 else
2794                                         Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2795                                 break;
2796                         }
2797
2798                         if (t->nodes[0] == node)
2799                                 portalpointer = (void **) &t->next[0];
2800                         else if (t->nodes[1] == node)
2801                                 portalpointer = (void **) &t->next[1];
2802                         else
2803                                 Host_Error("RemovePortalFromNodes: portal not bounding leaf");
2804                 }
2805         }
2806 }
2807
2808 static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node)
2809 {
2810         int i, side;
2811         mnode_t *front, *back, *other_node;
2812         mplane_t clipplane, *plane;
2813         portal_t *portal, *nextportal, *nodeportal, *splitportal, *temp;
2814         int numfrontpoints, numbackpoints;
2815         double frontpoints[3*MAX_PORTALPOINTS], backpoints[3*MAX_PORTALPOINTS];
2816
2817         // if a leaf, we're done
2818         if (!node->plane)
2819                 return;
2820
2821         plane = node->plane;
2822
2823         front = node->children[0];
2824         back = node->children[1];
2825         if (front == back)
2826                 Host_Error("Mod_Q1BSP_RecursiveNodePortals: corrupt node hierarchy");
2827
2828         // create the new portal by generating a polygon for the node plane,
2829         // and clipping it by all of the other portals(which came from nodes above this one)
2830         nodeportal = AllocPortal();
2831         nodeportal->plane = *plane;
2832
2833         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);
2834         nodeportal->numpoints = 4;
2835         side = 0;       // shut up compiler warning
2836         for (portal = (portal_t *)node->portals;portal;portal = portal->next[side])
2837         {
2838                 clipplane = portal->plane;
2839                 if (portal->nodes[0] == portal->nodes[1])
2840                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(1)");
2841                 if (portal->nodes[0] == node)
2842                         side = 0;
2843                 else if (portal->nodes[1] == node)
2844                 {
2845                         clipplane.dist = -clipplane.dist;
2846                         VectorNegate(clipplane.normal, clipplane.normal);
2847                         side = 1;
2848                 }
2849                 else
2850                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2851
2852                 for (i = 0;i < nodeportal->numpoints*3;i++)
2853                         frontpoints[i] = nodeportal->points[i];
2854                 PolygonD_Divide(nodeportal->numpoints, frontpoints, clipplane.normal[0], clipplane.normal[1], clipplane.normal[2], clipplane.dist, 1.0/32.0, MAX_PORTALPOINTS, nodeportal->points, &nodeportal->numpoints, 0, NULL, NULL, NULL);
2855                 if (nodeportal->numpoints <= 0 || nodeportal->numpoints >= MAX_PORTALPOINTS)
2856                         break;
2857         }
2858
2859         if (nodeportal->numpoints < 3)
2860         {
2861                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal was clipped away\n");
2862                 nodeportal->numpoints = 0;
2863         }
2864         else if (nodeportal->numpoints >= MAX_PORTALPOINTS)
2865         {
2866                 Con_Print("Mod_Q1BSP_RecursiveNodePortals: WARNING: new portal has too many points\n");
2867                 nodeportal->numpoints = 0;
2868         }
2869
2870         AddPortalToNodes(nodeportal, front, back);
2871
2872         // split the portals of this node along this node's plane and assign them to the children of this node
2873         // (migrating the portals downward through the tree)
2874         for (portal = (portal_t *)node->portals;portal;portal = nextportal)
2875         {
2876                 if (portal->nodes[0] == portal->nodes[1])
2877                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: portal has same node on both sides(2)");
2878                 if (portal->nodes[0] == node)
2879                         side = 0;
2880                 else if (portal->nodes[1] == node)
2881                         side = 1;
2882                 else
2883                         Host_Error("Mod_Q1BSP_RecursiveNodePortals: mislinked portal");
2884                 nextportal = portal->next[side];
2885                 if (!portal->numpoints)
2886                         continue;
2887
2888                 other_node = portal->nodes[!side];
2889                 RemovePortalFromNodes(portal);
2890
2891                 // cut the portal into two portals, one on each side of the node plane
2892                 PolygonD_Divide(portal->numpoints, portal->points, plane->normal[0], plane->normal[1], plane->normal[2], plane->dist, 1.0/32.0, MAX_PORTALPOINTS, frontpoints, &numfrontpoints, MAX_PORTALPOINTS, backpoints, &numbackpoints, NULL);
2893
2894                 if (!numfrontpoints)
2895                 {
2896                         if (side == 0)
2897                                 AddPortalToNodes(portal, back, other_node);
2898                         else
2899                                 AddPortalToNodes(portal, other_node, back);
2900                         continue;
2901                 }
2902                 if (!numbackpoints)
2903                 {
2904                         if (side == 0)
2905                                 AddPortalToNodes(portal, front, other_node);
2906                         else
2907                                 AddPortalToNodes(portal, other_node, front);
2908                         continue;
2909                 }
2910
2911                 // the portal is split
2912                 splitportal = AllocPortal();
2913                 temp = splitportal->chain;
2914                 *splitportal = *portal;
2915                 splitportal->chain = temp;
2916                 for (i = 0;i < numbackpoints*3;i++)
2917                         splitportal->points[i] = backpoints[i];
2918                 splitportal->numpoints = numbackpoints;
2919                 for (i = 0;i < numfrontpoints*3;i++)
2920                         portal->points[i] = frontpoints[i];
2921                 portal->numpoints = numfrontpoints;
2922
2923                 if (side == 0)
2924                 {
2925                         AddPortalToNodes(portal, front, other_node);
2926                         AddPortalToNodes(splitportal, back, other_node);
2927                 }
2928                 else
2929                 {
2930                         AddPortalToNodes(portal, other_node, front);
2931                         AddPortalToNodes(splitportal, other_node, back);
2932                 }
2933         }
2934
2935         Mod_Q1BSP_RecursiveNodePortals(front);
2936         Mod_Q1BSP_RecursiveNodePortals(back);
2937 }
2938
2939 static void Mod_Q1BSP_MakePortals(void)
2940 {
2941         portalchain = NULL;
2942         Mod_Q1BSP_RecursiveNodePortals(loadmodel->brush.data_nodes);
2943         Mod_Q1BSP_FinalizePortals();
2944 }
2945
2946 static void Mod_Q1BSP_BuildLightmapUpdateChains(mempool_t *mempool, model_t *model)
2947 {
2948         int i, j, stylecounts[256], totalcount, remapstyles[256];
2949         msurface_t *surface;
2950         memset(stylecounts, 0, sizeof(stylecounts));
2951         for (i = 0;i < model->nummodelsurfaces;i++)
2952         {
2953                 surface = model->data_surfaces + model->firstmodelsurface + i;
2954                 for (j = 0;j < MAXLIGHTMAPS;j++)
2955                         stylecounts[surface->lightmapinfo->styles[j]]++;
2956         }
2957         totalcount = 0;
2958         model->brushq1.light_styles = 0;
2959         for (i = 0;i < 255;i++)
2960         {
2961                 if (stylecounts[i])
2962                 {
2963                         remapstyles[i] = model->brushq1.light_styles++;
2964                         totalcount += stylecounts[i] + 1;
2965                 }
2966         }
2967         if (!totalcount)
2968                 return;
2969         model->brushq1.light_style = (unsigned char *)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(unsigned char));
2970         model->brushq1.light_stylevalue = (int *)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(int));
2971         model->brushq1.light_styleupdatechains = (msurface_t ***)Mem_Alloc(mempool, model->brushq1.light_styles * sizeof(msurface_t **));
2972         model->brushq1.light_styleupdatechainsbuffer = (msurface_t **)Mem_Alloc(mempool, totalcount * sizeof(msurface_t *));
2973         model->brushq1.light_styles = 0;
2974         for (i = 0;i < 255;i++)
2975                 if (stylecounts[i])
2976                         model->brushq1.light_style[model->brushq1.light_styles++] = i;
2977         j = 0;
2978         for (i = 0;i < model->brushq1.light_styles;i++)
2979         {
2980                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2981                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2982         }
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                         if (surface->lightmapinfo->styles[j] != 255)
2988                                 *model->brushq1.light_styleupdatechains[remapstyles[surface->lightmapinfo->styles[j]]]++ = surface;
2989         }
2990         j = 0;
2991         for (i = 0;i < model->brushq1.light_styles;i++)
2992         {
2993                 *model->brushq1.light_styleupdatechains[i] = NULL;
2994                 model->brushq1.light_styleupdatechains[i] = model->brushq1.light_styleupdatechainsbuffer + j;
2995                 j += stylecounts[model->brushq1.light_style[i]] + 1;
2996         }
2997 }
2998
2999 //Returns PVS data for a given point
3000 //(note: can return NULL)
3001 static unsigned char *Mod_Q1BSP_GetPVS(model_t *model, const vec3_t p)
3002 {
3003         mnode_t *node;
3004         node = model->brush.data_nodes;
3005         while (node->plane)
3006                 node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
3007         if (((mleaf_t *)node)->clusterindex >= 0)
3008                 return model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
3009         else
3010                 return NULL;
3011 }
3012
3013 static void Mod_Q1BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org, vec_t radius, unsigned char *pvsbuffer, int pvsbytes, mnode_t *node)
3014 {
3015         while (node->plane)
3016         {
3017                 float d = PlaneDiff(org, node->plane);
3018                 if (d > radius)
3019                         node = node->children[0];
3020                 else if (d < -radius)
3021                         node = node->children[1];
3022                 else
3023                 {
3024                         // go down both sides
3025                         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, pvsbytes, node->children[0]);
3026                         node = node->children[1];
3027                 }
3028         }
3029         // if this leaf is in a cluster, accumulate the pvs bits
3030         if (((mleaf_t *)node)->clusterindex >= 0)
3031         {
3032                 int i;
3033                 unsigned char *pvs = model->brush.data_pvsclusters + ((mleaf_t *)node)->clusterindex * model->brush.num_pvsclusterbytes;
3034                 for (i = 0;i < pvsbytes;i++)
3035                         pvsbuffer[i] |= pvs[i];
3036         }
3037 }
3038
3039 //Calculates a PVS that is the inclusive or of all leafs within radius pixels
3040 //of the given point.
3041 static int Mod_Q1BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, unsigned char *pvsbuffer, int pvsbufferlength)
3042 {
3043         int bytes = model->brush.num_pvsclusterbytes;
3044         bytes = min(bytes, pvsbufferlength);
3045         if (r_novis.integer || !model->brush.num_pvsclusters || !Mod_Q1BSP_GetPVS(model, org))
3046         {
3047                 memset(pvsbuffer, 0xFF, bytes);
3048                 return bytes;
3049         }
3050         memset(pvsbuffer, 0, bytes);
3051         Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brush.data_nodes);
3052         return bytes;
3053 }
3054
3055 static void Mod_Q1BSP_RoundUpToHullSize(model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
3056 {
3057         vec3_t size;
3058         const hull_t *hull;
3059
3060         VectorSubtract(inmaxs, inmins, size);
3061         if (cmodel->brush.ismcbsp)
3062         {
3063                 if (size[0] < 3)
3064                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3065                 else if (size[2] < 48) // pick the nearest of 40 or 56
3066                         hull = &cmodel->brushq1.hulls[2]; // 16x16x40
3067                 else
3068                         hull = &cmodel->brushq1.hulls[1]; // 16x16x56
3069         }
3070         else if (cmodel->brush.ishlbsp)
3071         {
3072                 if (size[0] < 3)
3073                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3074                 else if (size[0] <= 32)
3075                 {
3076                         if (size[2] < 54) // pick the nearest of 36 or 72
3077                                 hull = &cmodel->brushq1.hulls[3]; // 32x32x36
3078                         else
3079                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
3080                 }
3081                 else
3082                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
3083         }
3084         else
3085         {
3086                 if (size[0] < 3)
3087                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
3088                 else if (size[0] <= 32)
3089                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
3090                 else
3091                         hull = &cmodel->brushq1.hulls[2]; // 64x64x88
3092         }
3093         VectorCopy(inmins, outmins);
3094         VectorAdd(inmins, hull->clip_size, outmaxs);
3095 }
3096
3097 void Mod_Q1BSP_Load(model_t *mod, void *buffer, void *bufferend)
3098 {
3099         int i, j, k;
3100         dheader_t *header;
3101         dmodel_t *bm;
3102         mempool_t *mainmempool;
3103         float dist, modelyawradius, modelradius, *vec;
3104         msurface_t *surface;
3105         int numshadowmeshtriangles;
3106         dheader_t _header;
3107         hullinfo_t hullinfo;
3108
3109         mod->type = mod_brushq1;
3110
3111         if (!memcmp (buffer, "MCBSPpad", 8))
3112         {
3113                 unsigned char   *index;
3114
3115                 mod->brush.ismcbsp = true;
3116                 mod->brush.ishlbsp = false;
3117
3118                 mod_base = (unsigned char*)buffer;
3119
3120                 index = mod_base;
3121                 index += 8;
3122                 i = SB_ReadInt (&index);
3123                 if (i != MCBSPVERSION)
3124                         Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i)", mod->name, i, MCBSPVERSION);
3125
3126         // read hull info
3127                 hullinfo.numhulls = LittleLong(*(int*)index); index += 4;
3128                 hullinfo.filehulls = hullinfo.numhulls;
3129                 VectorClear (hullinfo.hullsizes[0][0]);
3130                 VectorClear (hullinfo.hullsizes[0][1]);
3131                 for (i = 1; i < hullinfo.numhulls; i++)
3132                 {
3133                         hullinfo.hullsizes[i][0][0] = SB_ReadFloat (&index);
3134                         hullinfo.hullsizes[i][0][1] = SB_ReadFloat (&index);
3135                         hullinfo.hullsizes[i][0][2] = SB_ReadFloat (&index);
3136                         hullinfo.hullsizes[i][1][0] = SB_ReadFloat (&index);
3137                         hullinfo.hullsizes[i][1][1] = SB_ReadFloat (&index);
3138                         hullinfo.hullsizes[i][1][2] = SB_ReadFloat (&index);
3139                 }
3140
3141         // read lumps
3142                 _header.version = 0;
3143                 for (i = 0; i < HEADER_LUMPS; i++)
3144                 {
3145                         _header.lumps[i].fileofs = SB_ReadInt (&index);
3146                         _header.lumps[i].filelen = SB_ReadInt (&index);
3147                 }
3148
3149                 header = &_header;
3150         }
3151         else
3152         {
3153                 header = (dheader_t *)buffer;
3154
3155                 i = LittleLong(header->version);
3156                 if (i != BSPVERSION && i != 30)
3157                         Host_Error("Mod_Q1BSP_Load: %s has wrong version number(%i should be %i(Quake) or 30(HalfLife)", mod->name, i, BSPVERSION);
3158                 mod->brush.ishlbsp = i == 30;
3159                 mod->brush.ismcbsp = false;
3160
3161         // fill in hull info
3162                 VectorClear (hullinfo.hullsizes[0][0]);
3163                 VectorClear (hullinfo.hullsizes[0][1]);
3164                 if (mod->brush.ishlbsp)
3165                 {
3166                         hullinfo.numhulls = 4;
3167                         hullinfo.filehulls = 4;
3168                         VectorSet (hullinfo.hullsizes[1][0], -16, -16, -36);
3169                         VectorSet (hullinfo.hullsizes[1][1], 16, 16, 36);
3170                         VectorSet (hullinfo.hullsizes[2][0], -32, -32, -32);
3171                         VectorSet (hullinfo.hullsizes[2][1], 32, 32, 32);
3172                         VectorSet (hullinfo.hullsizes[3][0], -16, -16, -18);
3173                         VectorSet (hullinfo.hullsizes[3][1], 16, 16, 18);
3174                 }
3175                 else
3176                 {
3177                         hullinfo.numhulls = 3;
3178                         hullinfo.filehulls = 4;
3179                         VectorSet (hullinfo.hullsizes[1][0], -16, -16, -24);
3180                         VectorSet (hullinfo.hullsizes[1][1], 16, 16, 32);
3181                         VectorSet (hullinfo.hullsizes[2][0], -32, -32, -24);
3182                         VectorSet (hullinfo.hullsizes[2][1], 32, 32, 64);
3183                 }
3184
3185         // read lumps
3186                 mod_base = (unsigned char*)buffer;
3187                 for (i = 0; i < HEADER_LUMPS; i++)
3188                 {
3189                         header->lumps[i].fileofs = LittleLong(header->lumps[i].fileofs);
3190                         header->lumps[i].filelen = LittleLong(header->lumps[i].filelen);
3191                 }
3192         }
3193
3194         mod->soundfromcenter = true;
3195         mod->TraceBox = Mod_Q1BSP_TraceBox;
3196         mod->brush.SuperContentsFromNativeContents = Mod_Q1BSP_SuperContentsFromNativeContents;
3197         mod->brush.NativeContentsFromSuperContents = Mod_Q1BSP_NativeContentsFromSuperContents;
3198         mod->brush.GetPVS = Mod_Q1BSP_GetPVS;
3199         mod->brush.FatPVS = Mod_Q1BSP_FatPVS;
3200         mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
3201         mod->brush.BoxTouchingLeafPVS = Mod_Q1BSP_BoxTouchingLeafPVS;
3202         mod->brush.BoxTouchingVisibleLeafs = Mod_Q1BSP_BoxTouchingVisibleLeafs;
3203         mod->brush.FindBoxClusters = Mod_Q1BSP_FindBoxClusters;
3204         mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
3205         mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
3206         mod->brush.AmbientSoundLevelsForPoint = Mod_Q1BSP_AmbientSoundLevelsForPoint;
3207         mod->brush.RoundUpToHullSize = Mod_Q1BSP_RoundUpToHullSize;
3208         mod->brush.PointInLeaf = Mod_Q1BSP_PointInLeaf;
3209
3210         if (loadmodel->isworldmodel)
3211         {
3212                 Cvar_SetValue("halflifebsp", mod->brush.ishlbsp);
3213                 Cvar_SetValue("mcbsp", mod->brush.ismcbsp);
3214         }
3215
3216 // load into heap
3217
3218         // store which lightmap format to use
3219         mod->brushq1.lightmaprgba = r_lightmaprgba.integer;
3220
3221         mod->brush.qw_md4sum = 0;
3222         mod->brush.qw_md4sum2 = 0;
3223         for (i = 0;i < HEADER_LUMPS;i++)
3224         {
3225                 if (i == LUMP_ENTITIES)
3226                         continue;
3227                 mod->brush.qw_md4sum ^= LittleLong(Com_BlockChecksum(mod_base + header->lumps[i].fileofs, header->lumps[i].filelen));
3228                 if (i == LUMP_VISIBILITY || i == LUMP_LEAFS || i == LUMP_NODES)
3229                         continue;
3230                 mod->brush.qw_md4sum2 ^= LittleLong(Com_BlockChecksum(mod_base + header->lumps[i].fileofs, header->lumps[i].filelen));
3231         }
3232
3233         Mod_Q1BSP_LoadEntities(&header->lumps[LUMP_ENTITIES]);
3234         Mod_Q1BSP_LoadVertexes(&header->lumps[LUMP_VERTEXES]);
3235         Mod_Q1BSP_LoadEdges(&header->lumps[LUMP_EDGES]);
3236         Mod_Q1BSP_LoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
3237         Mod_Q1BSP_LoadTextures(&header->lumps[LUMP_TEXTURES]);
3238         Mod_Q1BSP_LoadLighting(&header->lumps[LUMP_LIGHTING]);
3239         Mod_Q1BSP_LoadPlanes(&header->lumps[LUMP_PLANES]);
3240         Mod_Q1BSP_LoadTexinfo(&header->lumps[LUMP_TEXINFO]);
3241         Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
3242         Mod_Q1BSP_LoadLeaffaces(&header->lumps[LUMP_MARKSURFACES]);
3243         Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
3244         // load submodels before leafs because they contain the number of vis leafs
3245         Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS], &hullinfo);
3246         Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
3247         Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
3248         Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES], &hullinfo);
3249
3250         if (!mod->brushq1.lightdata)
3251                 mod->brush.LightPoint = NULL;
3252
3253         if (mod->brushq1.data_compressedpvs)
3254                 Mem_Free(mod->brushq1.data_compressedpvs);
3255         mod->brushq1.data_compressedpvs = NULL;
3256         mod->brushq1.num_compressedpvs = 0;
3257
3258         Mod_Q1BSP_MakeHull0();
3259         Mod_Q1BSP_MakePortals();
3260
3261         mod->numframes = 2;             // regular and alternate animation
3262         mod->numskins = 1;
3263
3264         mainmempool = mod->mempool;
3265
3266         // make a single combined shadow mesh to allow optimized shadow volume creation
3267         numshadowmeshtriangles = 0;
3268         for (j = 0, surface = loadmodel->data_surfaces;j < loadmodel->num_surfaces;j++, surface++)
3269         {
3270                 surface->num_firstshadowmeshtriangle = numshadowmeshtriangles;
3271                 numshadowmeshtriangles += surface->num_triangles;
3272         }
3273         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Begin(loadmodel->mempool, numshadowmeshtriangles * 3, numshadowmeshtriangles, NULL, NULL, NULL, false, false, true);
3274         for (j = 0, surface = loadmodel->data_surfaces;j < loadmodel->num_surfaces;j++, surface++)
3275                 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));
3276         loadmodel->brush.shadowmesh = Mod_ShadowMesh_Finish(loadmodel->mempool, loadmodel->brush.shadowmesh, false, true);
3277         Mod_BuildTriangleNeighbors(loadmodel->brush.shadowmesh->neighbor3i, loadmodel->brush.shadowmesh->element3i, loadmodel->brush.shadowmesh->numtriangles);
3278
3279         if (loadmodel->brush.numsubmodels)
3280                 loadmodel->brush.submodels = (model_t **)Mem_Alloc(loadmodel->mempool, loadmodel->brush.numsubmodels * sizeof(model_t *));
3281
3282         if (loadmodel->isworldmodel)
3283         {
3284                 // clear out any stale submodels or worldmodels lying around
3285                 // if we did this clear before now, an error might abort loading and
3286                 // leave things in a bad state
3287                 Mod_RemoveStaleWorldModels(loadmodel);
3288         }
3289
3290         // LordHavoc: to clear the fog around the original quake submodel code, I
3291         // will explain:
3292         // first of all, some background info on the submodels:
3293         // model 0 is the map model (the world, named maps/e1m1.bsp for example)
3294         // model 1 and higher are submodels (doors and the like, named *1, *2, etc)
3295         // now the weird for loop itself:
3296         // the loop functions in an odd way, on each iteration it sets up the
3297         // current 'mod' model (which despite the confusing code IS the model of
3298         // the number i), at the end of the loop it duplicates the model to become
3299         // the next submodel, and loops back to set up the new submodel.
3300
3301         // LordHavoc: now the explanation of my sane way (which works identically):
3302         // set up the world model, then on each submodel copy from the world model
3303         // and set up the submodel with the respective model info.
3304         for (i = 0;i < mod->brush.numsubmodels;i++)
3305         {
3306                 // LordHavoc: this code was originally at the end of this loop, but
3307                 // has been transformed to something more readable at the start here.
3308
3309                 if (i > 0)
3310                 {
3311                         char name[10];
3312                         // LordHavoc: only register submodels if it is the world
3313                         // (prevents external bsp models from replacing world submodels with
3314                         //  their own)
3315                         if (!loadmodel->isworldmodel)
3316                                 continue;
3317                         // duplicate the basic information
3318                         sprintf(name, "*%i", i);
3319                         mod = Mod_FindName(name);
3320                         // copy the base model to this one
3321                         *mod = *loadmodel;
3322                         // rename the clone back to its proper name
3323                         strcpy(mod->name, name);
3324                         // textures and memory belong to the main model
3325                         mod->texturepool = NULL;
3326                         mod->mempool = NULL;
3327                 }
3328
3329                 mod->brush.submodel = i;
3330
3331                 if (loadmodel->brush.submodels)
3332                         loadmodel->brush.submodels[i] = mod;
3333
3334                 bm = &mod->brushq1.submodels[i];
3335
3336                 mod->brushq1.hulls[0].firstclipnode = bm->headnode[0];
3337                 for (j=1 ; j<MAX_MAP_HULLS ; j++)
3338                 {
3339                         mod->brushq1.hulls[j].firstclipnode = bm->headnode[j];
3340                         mod->brushq1.hulls[j].lastclipnode = mod->brushq1.numclipnodes - 1;
3341                 }
3342
3343                 mod->firstmodelsurface = bm->firstface;
3344                 mod->nummodelsurfaces = bm->numfaces;
3345
3346                 // make the model surface list (used by shadowing/lighting)
3347                 mod->surfacelist = (int *)Mem_Alloc(loadmodel->mempool, mod->nummodelsurfaces * sizeof(*mod->surfacelist));
3348                 for (j = 0;j < mod->nummodelsurfaces;j++)
3349                         mod->surfacelist[j] = mod->firstmodelsurface + j;
3350
3351                 // this gets altered below if sky is used
3352                 mod->DrawSky = NULL;
3353                 mod->Draw = R_Q1BSP_Draw;
3354                 mod->GetLightInfo = R_Q1BSP_GetLightInfo;
3355