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