Return to cmodel.c CVS log

Up to [Quake II] / quake2 / qcommon

Annotation of quake2/qcommon/cmodel.c, revision 1.1

1.1     ! root        1: // cmodel.c -- model loading
        !             2: #include "qcommon.h"
        !             3: typedef struct
        !             4: {
        !             5:        cplane_t        *plane;
        !             6:        int                     children[2];            // negative numbers are leafs
        !             7: } cnode_t;
        !             8: typedef struct
        !             9: {
        !            10:        cplane_t        *plane;
        !            11:        csurface_t      *surface;
        !            12: } cbrushside_t;
        !            13: typedef struct
        !            14: {
        !            15:        int                     contents;
        !            16:        int                     cluster;
        !            17:        int                     area;
        !            18:        unsigned short  firstleafbrush;
        !            19:        unsigned short  numleafbrushes;
        !            20: } cleaf_t;
        !            21: typedef struct
        !            22: {
        !            23:        int                     contents;
        !            24:        int                     numsides;
        !            25:        int                     firstbrushside;
        !            26:        int                     checkcount;             // to avoid repeated testings
        !            27: } cbrush_t;
        !            28: typedef struct
        !            29: {
        !            30:        int             numareaportals;
        !            31:        int             firstareaportal;
        !            32:        int             floodnum;                       // if two areas have equal floodnums, they are connected
        !            33:        int             floodvalid;
        !            34: } carea_t;
        !            35: int                    checkcount;
        !            36: char           map_name[MAX_QPATH];
        !            37: int                    numbrushsides;
        !            38: cbrushside_t map_brushsides[MAX_MAP_BRUSHSIDES];
        !            39: int                    numtexinfo;
        !            40: csurface_t     map_surfaces[MAX_MAP_TEXINFO];
        !            41: int                    numplanes;
        !            42: cplane_t       map_planes[MAX_MAP_PLANES+6];           // extra for box hull
        !            43: int                    numnodes;
        !            44: cnode_t                map_nodes[MAX_MAP_NODES+6];             // extra for box hull
        !            45: int                    numleafs = 1;   // allow leaf funcs to be called without a map
        !            46: cleaf_t                map_leafs[MAX_MAP_LEAFS];
        !            47: int                    emptyleaf, solidleaf;
        !            48: int                    numleafbrushes;
        !            49: unsigned short map_leafbrushes[MAX_MAP_LEAFBRUSHES];
        !            50: int                    numcmodels;
        !            51: cmodel_t       map_cmodels[MAX_MAP_MODELS];
        !            52: int                    numbrushes;
        !            53: cbrush_t       map_brushes[MAX_MAP_BRUSHES];
        !            54: int                    numvisibility;
        !            55: byte           map_visibility[MAX_MAP_VISIBILITY];
        !            56: dvis_t         *map_vis = (dvis_t *)map_visibility;
        !            57: int                    numentitychars;
        !            58: char           map_entitystring[MAX_MAP_ENTSTRING];
        !            59: int                    numareas = 1;
        !            60: carea_t                map_areas[MAX_MAP_AREAS];
        !            61: int                    numareaportals;
        !            62: dareaportal_t map_areaportals[MAX_MAP_AREAPORTALS];
        !            63: int                    numclusters = 1;
        !            64: csurface_t     nullsurface;
        !            65: int                    floodvalid;
        !            66: qboolean       portalopen[MAX_MAP_AREAPORTALS];
        !            67: cvar_t         *map_noareas;
        !            68: void   CM_InitBoxHull (void);
        !            69: void   FloodAreaConnections (void);
        !            70: int            c_pointcontents;
        !            71: int            c_traces, c_brush_traces;
        !            72: /*
        !            73: ===============================================================================
        !            74:                                        MAP LOADING
        !            75: ===============================================================================
        !            76: */
        !            77: byte   *cmod_base;
        !            78: /*
        !            79: =================
        !            80: CMod_LoadSubmodels
        !            81: =================
        !            82: */
        !            83: void CMod_LoadSubmodels (lump_t *l)
        !            84: {
        !            85:        dmodel_t        *in;
        !            86:        cmodel_t        *out;
        !            87:        int                     i, j, count;
        !            88:        in = (void *)(cmod_base + l->fileofs);
        !            89:        if (l->filelen % sizeof(*in))
        !            90:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !            91:        count = l->filelen / sizeof(*in);
        !            92:        if (count < 1)
        !            93:                Com_Error (ERR_DROP, "Map with no models");
        !            94:        if (count > MAX_MAP_MODELS)
        !            95:                Com_Error (ERR_DROP, "Map has too many models");
        !            96:        numcmodels = count;
        !            97:        for ( i=0 ; i<count ; i++, in++, out++)
        !            98:        {
        !            99:                out = &map_cmodels[i];
        !           100:                for (j=0 ; j<3 ; j++)
        !           101:                {       // spread the mins / maxs by a pixel
        !           102:                        out->mins[j] = LittleFloat (in->mins[j]) - 1;
        !           103:                        out->maxs[j] = LittleFloat (in->maxs[j]) + 1;
        !           104:                        out->origin[j] = LittleFloat (in->origin[j]);
        !           105:                }
        !           106:                out->headnode = LittleLong (in->headnode);
        !           107:        }
        !           108: }
        !           109: /*
        !           110: =================
        !           111: CMod_LoadSurfaces
        !           112: =================
        !           113: */
        !           114: void CMod_LoadSurfaces (lump_t *l)
        !           115: {
        !           116:        texinfo_t       *in;
        !           117:        csurface_t      *out;
        !           118:        int                     i, count;
        !           119:        in = (void *)(cmod_base + l->fileofs);
        !           120:        if (l->filelen % sizeof(*in))
        !           121:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           122:        count = l->filelen / sizeof(*in);
        !           123:        if (count < 1)
        !           124:                Com_Error (ERR_DROP, "Map with no surfaces");
        !           125:        if (count > MAX_MAP_TEXINFO)
        !           126:                Com_Error (ERR_DROP, "Map has too many surfaces");
        !           127:        numtexinfo = count;
        !           128:        out = map_surfaces;
        !           129:        for ( i=0 ; i<count ; i++, in++, out++)
        !           130:        {
        !           131:                strncpy (out->name, in->texture, sizeof(out->name)-1);
        !           132:                out->flags = LittleLong (in->flags);
        !           133:                out->value = LittleLong (in->value);
        !           134:        }
        !           135: }
        !           136: /*
        !           137: =================
        !           138: CMod_LoadNodes
        !           139: =================
        !           140: */
        !           141: void CMod_LoadNodes (lump_t *l)
        !           142: {
        !           143:        dnode_t         *in;
        !           144:        int                     child;
        !           145:        cnode_t         *out;
        !           146:        int                     i, j, count;
        !           147:        
        !           148:        in = (void *)(cmod_base + l->fileofs);
        !           149:        if (l->filelen % sizeof(*in))
        !           150:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           151:        count = l->filelen / sizeof(*in);
        !           152:        if (count < 1)
        !           153:                Com_Error (ERR_DROP, "Map has no nodes");
        !           154:        if (count > MAX_MAP_NODES)
        !           155:                Com_Error (ERR_DROP, "Map has too many nodes");
        !           156:        out = map_nodes;
        !           157:        numnodes = count;
        !           158:        for (i=0 ; i<count ; i++, out++, in++)
        !           159:        {
        !           160:                out->plane = map_planes + LittleLong(in->planenum);
        !           161:                for (j=0 ; j<2 ; j++)
        !           162:                {
        !           163:                        child = LittleLong (in->children[j]);
        !           164:                        out->children[j] = child;
        !           165:                }
        !           166:        }
        !           167: }
        !           168: /*
        !           169: =================
        !           170: CMod_LoadBrushes
        !           171: =================
        !           172: */
        !           173: void CMod_LoadBrushes (lump_t *l)
        !           174: {
        !           175:        dbrush_t        *in;
        !           176:        cbrush_t        *out;
        !           177:        int                     i, count;
        !           178:        
        !           179:        in = (void *)(cmod_base + l->fileofs);
        !           180:        if (l->filelen % sizeof(*in))
        !           181:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           182:        count = l->filelen / sizeof(*in);
        !           183:        if (count > MAX_MAP_BRUSHES)
        !           184:                Com_Error (ERR_DROP, "Map has too many brushes");
        !           185:        out = map_brushes;
        !           186:        numbrushes = count;
        !           187:        for (i=0 ; i<count ; i++, out++, in++)
        !           188:        {
        !           189:                out->firstbrushside = LittleLong(in->firstside);
        !           190:                out->numsides = LittleLong(in->numsides);
        !           191:                out->contents = LittleLong(in->contents);
        !           192:        }
        !           193: }
        !           194: /*
        !           195: =================
        !           196: CMod_LoadLeafs
        !           197: =================
        !           198: */
        !           199: void CMod_LoadLeafs (lump_t *l)
        !           200: {
        !           201:        int                     i;
        !           202:        cleaf_t         *out;
        !           203:        dleaf_t         *in;
        !           204:        int                     count;
        !           205:        
        !           206:        in = (void *)(cmod_base + l->fileofs);
        !           207:        if (l->filelen % sizeof(*in))
        !           208:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           209:        count = l->filelen / sizeof(*in);
        !           210:        if (count < 1)
        !           211:                Com_Error (ERR_DROP, "Map with no leafs");
        !           212:        // need to save space for box planes
        !           213:        if (count > MAX_MAP_PLANES)
        !           214:                Com_Error (ERR_DROP, "Map has too many planes");
        !           215:        out = map_leafs;        
        !           216:        numleafs = count;
        !           217:        numclusters = 0;
        !           218:        for ( i=0 ; i<count ; i++, in++, out++)
        !           219:        {
        !           220:                out->contents = LittleLong (in->contents);
        !           221:                out->cluster = LittleShort (in->cluster);
        !           222:                out->area = LittleShort (in->area);
        !           223:                out->firstleafbrush = LittleShort (in->firstleafbrush);
        !           224:                out->numleafbrushes = LittleShort (in->numleafbrushes);
        !           225:                if (out->cluster >= numclusters)
        !           226:                        numclusters = out->cluster + 1;
        !           227:        }
        !           228:        if (map_leafs[0].contents != CONTENTS_SOLID)
        !           229:                Com_Error (ERR_DROP, "Map leaf 0 is not CONTENTS_SOLID");
        !           230:        solidleaf = 0;
        !           231:        emptyleaf = -1;
        !           232:        for (i=1 ; i<numleafs ; i++)
        !           233:        {
        !           234:                if (!map_leafs[i].contents)
        !           235:                {
        !           236:                        emptyleaf = i;
        !           237:                        break;
        !           238:                }
        !           239:        }
        !           240:        if (emptyleaf == -1)
        !           241:                Com_Error (ERR_DROP, "Map does not have an empty leaf");
        !           242: }
        !           243: /*
        !           244: =================
        !           245: CMod_LoadPlanes
        !           246: =================
        !           247: */
        !           248: void CMod_LoadPlanes (lump_t *l)
        !           249: {
        !           250:        int                     i, j;
        !           251:        cplane_t        *out;
        !           252:        dplane_t        *in;
        !           253:        int                     count;
        !           254:        int                     bits;
        !           255:        
        !           256:        in = (void *)(cmod_base + l->fileofs);
        !           257:        if (l->filelen % sizeof(*in))
        !           258:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           259:        count = l->filelen / sizeof(*in);
        !           260:        if (count < 1)
        !           261:                Com_Error (ERR_DROP, "Map with no planes");
        !           262:        // need to save space for box planes
        !           263:        if (count > MAX_MAP_PLANES)
        !           264:                Com_Error (ERR_DROP, "Map has too many planes");
        !           265:        out = map_planes;       
        !           266:        numplanes = count;
        !           267:        for ( i=0 ; i<count ; i++, in++, out++)
        !           268:        {
        !           269:                bits = 0;
        !           270:                for (j=0 ; j<3 ; j++)
        !           271:                {
        !           272:                        out->normal[j] = LittleFloat (in->normal[j]);
        !           273:                        if (out->normal[j] < 0)
        !           274:                                bits |= 1<<j;
        !           275:                }
        !           276:                out->dist = LittleFloat (in->dist);
        !           277:                out->type = LittleLong (in->type);
        !           278:                out->signbits = bits;
        !           279:        }
        !           280: }
        !           281: /*
        !           282: =================
        !           283: CMod_LoadLeafBrushes
        !           284: =================
        !           285: */
        !           286: void CMod_LoadLeafBrushes (lump_t *l)
        !           287: {
        !           288:        int                     i;
        !           289:        unsigned short  *out;
        !           290:        unsigned short  *in;
        !           291:        int                     count;
        !           292:        
        !           293:        in = (void *)(cmod_base + l->fileofs);
        !           294:        if (l->filelen % sizeof(*in))
        !           295:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           296:        count = l->filelen / sizeof(*in);
        !           297:        if (count < 1)
        !           298:                Com_Error (ERR_DROP, "Map with no planes");
        !           299:        // need to save space for box planes
        !           300:        if (count > MAX_MAP_LEAFBRUSHES)
        !           301:                Com_Error (ERR_DROP, "Map has too many leafbrushes");
        !           302:        out = map_leafbrushes;
        !           303:        numleafbrushes = count;
        !           304:        for ( i=0 ; i<count ; i++, in++, out++)
        !           305:                *out = LittleShort (*in);
        !           306: }
        !           307: /*
        !           308: =================
        !           309: CMod_LoadBrushSides
        !           310: =================
        !           311: */
        !           312: void CMod_LoadBrushSides (lump_t *l)
        !           313: {
        !           314:        int                     i, j;
        !           315:        cbrushside_t    *out;
        !           316:        dbrushside_t    *in;
        !           317:        int                     count;
        !           318:        int                     num;
        !           319:        in = (void *)(cmod_base + l->fileofs);
        !           320:        if (l->filelen % sizeof(*in))
        !           321:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           322:        count = l->filelen / sizeof(*in);
        !           323:        // need to save space for box planes
        !           324:        if (count > MAX_MAP_BRUSHSIDES)
        !           325:                Com_Error (ERR_DROP, "Map has too many planes");
        !           326:        out = map_brushsides;   
        !           327:        numbrushsides = count;
        !           328:        for ( i=0 ; i<count ; i++, in++, out++)
        !           329:        {
        !           330:                num = LittleShort (in->planenum);
        !           331:                out->plane = &map_planes[num];
        !           332:                j = LittleShort (in->texinfo);
        !           333:                if (j >= numtexinfo)
        !           334:                        Com_Error (ERR_DROP, "Bad brushside texinfo");
        !           335:                out->surface = &map_surfaces[j];
        !           336:        }
        !           337: }
        !           338: /*
        !           339: =================
        !           340: CMod_LoadAreas
        !           341: =================
        !           342: */
        !           343: void CMod_LoadAreas (lump_t *l)
        !           344: {
        !           345:        int                     i;
        !           346:        carea_t         *out;
        !           347:        darea_t         *in;
        !           348:        int                     count;
        !           349:        in = (void *)(cmod_base + l->fileofs);
        !           350:        if (l->filelen % sizeof(*in))
        !           351:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           352:        count = l->filelen / sizeof(*in);
        !           353:        if (count > MAX_MAP_AREAS)
        !           354:                Com_Error (ERR_DROP, "Map has too many areas");
        !           355:        out = map_areas;
        !           356:        numareas = count;
        !           357:        for ( i=0 ; i<count ; i++, in++, out++)
        !           358:        {
        !           359:                out->numareaportals = LittleLong (in->numareaportals);
        !           360:                out->firstareaportal = LittleLong (in->firstareaportal);
        !           361:                out->floodvalid = 0;
        !           362:                out->floodnum = 0;
        !           363:        }
        !           364: }
        !           365: /*
        !           366: =================
        !           367: CMod_LoadAreaPortals
        !           368: =================
        !           369: */
        !           370: void CMod_LoadAreaPortals (lump_t *l)
        !           371: {
        !           372:        int                     i;
        !           373:        dareaportal_t           *out;
        !           374:        dareaportal_t   *in;
        !           375:        int                     count;
        !           376:        in = (void *)(cmod_base + l->fileofs);
        !           377:        if (l->filelen % sizeof(*in))
        !           378:                Com_Error (ERR_DROP, "MOD_LoadBmodel: funny lump size");
        !           379:        count = l->filelen / sizeof(*in);
        !           380:        if (count > MAX_MAP_AREAS)
        !           381:                Com_Error (ERR_DROP, "Map has too many areas");
        !           382:        out = map_areaportals;
        !           383:        numareaportals = count;
        !           384:        for ( i=0 ; i<count ; i++, in++, out++)
        !           385:        {
        !           386:                out->portalnum = LittleLong (in->portalnum);
        !           387:                out->otherarea = LittleLong (in->otherarea);
        !           388:        }
        !           389: }
        !           390: /*
        !           391: =================
        !           392: CMod_LoadVisibility
        !           393: =================
        !           394: */
        !           395: void CMod_LoadVisibility (lump_t *l)
        !           396: {
        !           397:        int             i;
        !           398:        numvisibility = l->filelen;
        !           399:        if (l->filelen > MAX_MAP_VISIBILITY)
        !           400:                Com_Error (ERR_DROP, "Map has too large visibility lump");
        !           401:        memcpy (map_visibility, cmod_base + l->fileofs, l->filelen);
        !           402:        map_vis->numclusters = LittleLong (map_vis->numclusters);
        !           403:        for (i=0 ; i<map_vis->numclusters ; i++)
        !           404:        {
        !           405:                map_vis->bitofs[i][0] = LittleLong (map_vis->bitofs[i][0]);
        !           406:                map_vis->bitofs[i][1] = LittleLong (map_vis->bitofs[i][1]);
        !           407:        }
        !           408: }
        !           409: /*
        !           410: =================
        !           411: CMod_LoadEntityString
        !           412: =================
        !           413: */
        !           414: void CMod_LoadEntityString (lump_t *l)
        !           415: {
        !           416:        numentitychars = l->filelen;
        !           417:        if (l->filelen > MAX_MAP_ENTSTRING)
        !           418:                Com_Error (ERR_DROP, "Map has too large entity lump");
        !           419:        memcpy (map_entitystring, cmod_base + l->fileofs, l->filelen);
        !           420: }
        !           421: /*
        !           422: ==================
        !           423: CM_LoadMap
        !           424: Loads in the map and all submodels
        !           425: ==================
        !           426: */
        !           427: cmodel_t *CM_LoadMap (char *name, qboolean clientload, unsigned *checksum)
        !           428: {
        !           429:        unsigned                *buf;
        !           430:        int                             i;
        !           431:        dheader_t               header;
        !           432:        int                             length;
        !           433:        static unsigned last_checksum;
        !           434:        map_noareas = Cvar_Get ("map_noareas", "0", 0);
        !           435:        if (  !strcmp (map_name, name) && (clientload || !Cvar_VariableValue ("flushmap")) )
        !           436:        {
        !           437:                *checksum = last_checksum;
        !           438:                if (!clientload)
        !           439:                {
        !           440:                        memset (portalopen, 0, sizeof(portalopen));
        !           441:                        FloodAreaConnections ();
        !           442:                }
        !           443:                return &map_cmodels[0];         // still have the right version
        !           444:        }
        !           445:        // free old stuff
        !           446:        numplanes = 0;
        !           447:        numnodes = 0;
        !           448:        numleafs = 0;
        !           449:        numcmodels = 0;
        !           450:        numvisibility = 0;
        !           451:        numentitychars = 0;
        !           452:        map_entitystring[0] = 0;
        !           453:        map_name[0] = 0;
        !           454:        if (!name || !name[0])
        !           455:        {
        !           456:                numleafs = 1;
        !           457:                numclusters = 1;
        !           458:                numareas = 1;
        !           459:                *checksum = 0;
        !           460:                return &map_cmodels[0];                 // cinematic servers won't have anything at all
        !           461:        }
        !           462:        //
        !           463:        // load the file
        !           464:        //
        !           465:        length = FS_LoadFile (name, (void **)&buf);
        !           466:        if (!buf)
        !           467:                Com_Error (ERR_DROP, "Couldn't load %s", name);
        !           468: 
        !           469:        last_checksum = LittleLong (Com_BlockChecksum (buf, length));
        !           470:        *checksum = last_checksum;
        !           471:        header = *(dheader_t *)buf;
        !           472:        for (i=0 ; i<sizeof(dheader_t)/4 ; i++)
        !           473:                ((int *)&header)[i] = LittleLong ( ((int *)&header)[i]);
        !           474:        if (header.version != BSPVERSION)
        !           475:                Com_Error (ERR_DROP, "CMod_LoadBrushModel: %s has wrong version number (%i should be %i)"
        !           476:                , name, header.version, BSPVERSION);
        !           477:        cmod_base = (byte *)buf;
        !           478:        // load into heap
        !           479:        CMod_LoadSurfaces (&header.lumps[LUMP_TEXINFO]);
        !           480:        CMod_LoadLeafs (&header.lumps[LUMP_LEAFS]);
        !           481:        CMod_LoadLeafBrushes (&header.lumps[LUMP_LEAFBRUSHES]);
        !           482:        CMod_LoadPlanes (&header.lumps[LUMP_PLANES]);
        !           483:        CMod_LoadBrushes (&header.lumps[LUMP_BRUSHES]);
        !           484:        CMod_LoadBrushSides (&header.lumps[LUMP_BRUSHSIDES]);
        !           485:        CMod_LoadSubmodels (&header.lumps[LUMP_MODELS]);
        !           486:        CMod_LoadNodes (&header.lumps[LUMP_NODES]);
        !           487:        CMod_LoadAreas (&header.lumps[LUMP_AREAS]);
        !           488:        CMod_LoadAreaPortals (&header.lumps[LUMP_AREAPORTALS]);
        !           489:        CMod_LoadVisibility (&header.lumps[LUMP_VISIBILITY]);
        !           490:        CMod_LoadEntityString (&header.lumps[LUMP_ENTITIES]);
        !           491:        FS_FreeFile (buf);
        !           492:        CM_InitBoxHull ();
        !           493:        memset (portalopen, 0, sizeof(portalopen));
        !           494:        FloodAreaConnections ();
        !           495:        strcpy (map_name, name);
        !           496:        return &map_cmodels[0];
        !           497: }
        !           498: /*
        !           499: ==================
        !           500: CM_InlineModel
        !           501: ==================
        !           502: */
        !           503: cmodel_t       *CM_InlineModel (char *name)
        !           504: {
        !           505:        int             num;
        !           506:        if (!name || name[0] != '*')
        !           507:                Com_Error (ERR_DROP, "CM_InlineModel: bad name");
        !           508:        num = atoi (name+1);
        !           509:        if (num < 1 || num >= numcmodels)
        !           510:                Com_Error (ERR_DROP, "CM_InlineModel: bad number");
        !           511:        return &map_cmodels[num];
        !           512: }
        !           513: int            CM_NumClusters (void)
        !           514: {
        !           515:        return numclusters;
        !           516: }
        !           517: int            CM_NumInlineModels (void)
        !           518: {
        !           519:        return numcmodels;
        !           520: }
        !           521: char   *CM_EntityString (void)
        !           522: {
        !           523:        return map_entitystring;
        !           524: }
        !           525: int            CM_LeafContents (int leafnum)
        !           526: {
        !           527:        if (leafnum < 0 || leafnum >= numleafs)
        !           528:                Com_Error (ERR_DROP, "CM_LeafContents: bad number");
        !           529:        return map_leafs[leafnum].contents;
        !           530: }
        !           531: int            CM_LeafCluster (int leafnum)
        !           532: {
        !           533:        if (leafnum < 0 || leafnum >= numleafs)
        !           534:                Com_Error (ERR_DROP, "CM_LeafCluster: bad number");
        !           535:        return map_leafs[leafnum].cluster;
        !           536: }
        !           537: int            CM_LeafArea (int leafnum)
        !           538: {
        !           539:        if (leafnum < 0 || leafnum >= numleafs)
        !           540:                Com_Error (ERR_DROP, "CM_LeafArea: bad number");
        !           541:        return map_leafs[leafnum].area;
        !           542: }
        !           543: //=======================================================================
        !           544: cplane_t       *box_planes;
        !           545: int                    box_headnode;
        !           546: cbrush_t       *box_brush;
        !           547: cleaf_t                *box_leaf;
        !           548: /*
        !           549: ===================
        !           550: CM_InitBoxHull
        !           551: Set up the planes and nodes so that the six floats of a bounding box
        !           552: can just be stored out and get a proper clipping hull structure.
        !           553: ===================
        !           554: */
        !           555: void CM_InitBoxHull (void)
        !           556: {
        !           557:        int                     i;
        !           558:        int                     side;
        !           559:        cnode_t         *c;
        !           560:        cplane_t        *p;
        !           561:        cbrushside_t    *s;
        !           562:        box_headnode = numnodes;
        !           563:        box_planes = &map_planes[numplanes];
        !           564:        if (numnodes+6 > MAX_MAP_NODES
        !           565:                || numbrushes+1 > MAX_MAP_BRUSHES
        !           566:                || numleafbrushes+1 > MAX_MAP_LEAFBRUSHES
        !           567:                || numbrushsides+6 > MAX_MAP_BRUSHSIDES
        !           568:                || numplanes+12 > MAX_MAP_PLANES)
        !           569:                Com_Error (ERR_DROP, "Not enough room for box tree");
        !           570:        box_brush = &map_brushes[numbrushes];
        !           571:        box_brush->numsides = 6;
        !           572:        box_brush->firstbrushside = numbrushsides;
        !           573:        box_brush->contents = CONTENTS_MONSTER;
        !           574:        box_leaf = &map_leafs[numleafs];
        !           575:        box_leaf->contents = CONTENTS_MONSTER;
        !           576:        box_leaf->firstleafbrush = numleafbrushes;
        !           577:        box_leaf->numleafbrushes = 1;
        !           578:        map_leafbrushes[numleafbrushes] = numbrushes;
        !           579:        for (i=0 ; i<6 ; i++)
        !           580:        {
        !           581:                side = i&1;
        !           582:                // brush sides
        !           583:                s = &map_brushsides[numbrushsides+i];
        !           584:                s->plane =      map_planes + (numplanes+i*2+side);
        !           585:                s->surface = &nullsurface;
        !           586:                // nodes
        !           587:                c = &map_nodes[box_headnode+i];
        !           588:                c->plane = map_planes + (numplanes+i*2);
        !           589:                c->children[side] = -1 - emptyleaf;
        !           590:                if (i != 5)
        !           591:                        c->children[side^1] = box_headnode+i + 1;
        !           592:                else
        !           593:                        c->children[side^1] = -1 - numleafs;
        !           594:                // planes
        !           595:                p = &box_planes[i*2];
        !           596:                p->type = i>>1;
        !           597:                p->signbits = 0;
        !           598:                VectorClear (p->normal);
        !           599:                p->normal[i>>1] = 1;
        !           600:                p = &box_planes[i*2+1];
        !           601:                p->type = 3 + (i>>1);
        !           602:                p->signbits = 0;
        !           603:                VectorClear (p->normal);
        !           604:                p->normal[i>>1] = -1;
        !           605:        }       
        !           606: }
        !           607: /*
        !           608: ===================
        !           609: CM_HeadnodeForBox
        !           610: To keep everything totally uniform, bounding boxes are turned into small
        !           611: BSP trees instead of being compared directly.
        !           612: ===================
        !           613: */
        !           614: int    CM_HeadnodeForBox (vec3_t mins, vec3_t maxs)
        !           615: {
        !           616:        box_planes[0].dist = maxs[0];
        !           617:        box_planes[1].dist = -maxs[0];
        !           618:        box_planes[2].dist = mins[0];
        !           619:        box_planes[3].dist = -mins[0];
        !           620:        box_planes[4].dist = maxs[1];
        !           621:        box_planes[5].dist = -maxs[1];
        !           622:        box_planes[6].dist = mins[1];
        !           623:        box_planes[7].dist = -mins[1];
        !           624:        box_planes[8].dist = maxs[2];
        !           625:        box_planes[9].dist = -maxs[2];
        !           626:        box_planes[10].dist = mins[2];
        !           627:        box_planes[11].dist = -mins[2];
        !           628:        return box_headnode;
        !           629: }
        !           630: /*
        !           631: ==================
        !           632: CM_PointLeafnum_r
        !           633: ==================
        !           634: */
        !           635: int CM_PointLeafnum_r (vec3_t p, int num)
        !           636: {
        !           637:        float           d;
        !           638:        cnode_t         *node;
        !           639:        cplane_t        *plane;
        !           640:        while (num >= 0)
        !           641:        {
        !           642:                node = map_nodes + num;
        !           643:                plane = node->plane;
        !           644:                
        !           645:                if (plane->type < 3)
        !           646:                        d = p[plane->type] - plane->dist;
        !           647:                else
        !           648:                        d = DotProduct (plane->normal, p) - plane->dist;
        !           649:                if (d < 0)
        !           650:                        num = node->children[1];
        !           651:                else
        !           652:                        num = node->children[0];
        !           653:        }
        !           654:        c_pointcontents++;              // optimize counter
        !           655:        return -1 - num;
        !           656: }
        !           657: int CM_PointLeafnum (vec3_t p)
        !           658: {
        !           659:        if (!numplanes)
        !           660:                return 0;               // sound may call this without map loaded
        !           661:        return CM_PointLeafnum_r (p, 0);
        !           662: }
        !           663: /*
        !           664: =============
        !           665: CM_BoxLeafnums
        !           666: Fills in a list of all the leafs touched
        !           667: =============
        !           668: */
        !           669: int            leaf_count, leaf_maxcount;
        !           670: int            *leaf_list;
        !           671: float  *leaf_mins, *leaf_maxs;
        !           672: int            leaf_topnode;
        !           673: void CM_BoxLeafnums_r (int nodenum)
        !           674: {
        !           675:        cplane_t        *plane;
        !           676:        cnode_t         *node;
        !           677:        int             s;
        !           678:        while (1)
        !           679:        {
        !           680:                if (nodenum < 0)
        !           681:                {
        !           682:                        if (leaf_count >= leaf_maxcount)
        !           683:                        {
        !           684: //                             Com_Printf ("CM_BoxLeafnums_r: overflow\n");
        !           685:                                return;
        !           686:                        }
        !           687:                        leaf_list[leaf_count++] = -1 - nodenum;
        !           688:                        return;
        !           689:                }
        !           690:        
        !           691:                node = &map_nodes[nodenum];
        !           692:                plane = node->plane;
        !           693: //             s = BoxOnPlaneSide (leaf_mins, leaf_maxs, plane);
        !           694:                s = BOX_ON_PLANE_SIDE(leaf_mins, leaf_maxs, plane);
        !           695:                if (s == 1)
        !           696:                        nodenum = node->children[0];
        !           697:                else if (s == 2)
        !           698:                        nodenum = node->children[1];
        !           699:                else
        !           700:                {       // go down both
        !           701:                        if (leaf_topnode == -1)
        !           702:                                leaf_topnode = nodenum;
        !           703:                        CM_BoxLeafnums_r (node->children[0]);
        !           704:                        nodenum = node->children[1];
        !           705:                }
        !           706:        }
        !           707: }
        !           708: int    CM_BoxLeafnums_headnode (vec3_t mins, vec3_t maxs, int *list, int listsize, int headnode, int *topnode)
        !           709: {
        !           710:        leaf_list = list;
        !           711:        leaf_count = 0;
        !           712:        leaf_maxcount = listsize;
        !           713:        leaf_mins = mins;
        !           714:        leaf_maxs = maxs;
        !           715:        leaf_topnode = -1;
        !           716:        CM_BoxLeafnums_r (headnode);
        !           717:        if (topnode)
        !           718:                *topnode = leaf_topnode;
        !           719:        return leaf_count;
        !           720: }
        !           721: int    CM_BoxLeafnums (vec3_t mins, vec3_t maxs, int *list, int listsize, int *topnode)
        !           722: {
        !           723:        return CM_BoxLeafnums_headnode (mins, maxs, list,
        !           724:                listsize, map_cmodels[0].headnode, topnode);
        !           725: }
        !           726: /*
        !           727: ==================
        !           728: CM_PointContents
        !           729: ==================
        !           730: */
        !           731: int CM_PointContents (vec3_t p, int headnode)
        !           732: {
        !           733:        int             l;
        !           734:        if (!numnodes)  // map not loaded
        !           735:                return 0;
        !           736: 
        !           737:        l = CM_PointLeafnum_r (p, headnode);
        !           738:        return map_leafs[l].contents;
        !           739: }
        !           740: /*
        !           741: ==================
        !           742: CM_TransformedPointContents
        !           743: Handles offseting and rotation of the end points for moving and
        !           744: rotating entities
        !           745: ==================
        !           746: */
        !           747: int    CM_TransformedPointContents (vec3_t p, int headnode, vec3_t origin, vec3_t angles)
        !           748: {
        !           749:        vec3_t          p_l;
        !           750:        vec3_t          temp;
        !           751:        vec3_t          forward, right, up;
        !           752:        int                     l;
        !           753:        // subtract origin offset
        !           754:        VectorSubtract (p, origin, p_l);
        !           755:        // rotate start and end into the models frame of reference
        !           756:        if (headnode != box_headnode && 
        !           757:        (angles[0] || angles[1] || angles[2]) )
        !           758:        {
        !           759:                AngleVectors (angles, forward, right, up);
        !           760:                VectorCopy (p_l, temp);
        !           761:                p_l[0] = DotProduct (temp, forward);
        !           762:                p_l[1] = -DotProduct (temp, right);
        !           763:                p_l[2] = DotProduct (temp, up);
        !           764:        }
        !           765:        l = CM_PointLeafnum_r (p_l, headnode);
        !           766:        return map_leafs[l].contents;
        !           767: }
        !           768: /*
        !           769: ===============================================================================
        !           770: BOX TRACING
        !           771: ===============================================================================
        !           772: */
        !           773: // 1/32 epsilon to keep floating point happy
        !           774: #define        DIST_EPSILON    (0.03125)
        !           775: vec3_t trace_start, trace_end;
        !           776: vec3_t trace_mins, trace_maxs;
        !           777: vec3_t trace_extents;
        !           778: trace_t        trace_trace;
        !           779: int            trace_contents;
        !           780: qboolean       trace_ispoint;          // optimized case
        !           781: /*
        !           782: ================
        !           783: CM_ClipBoxToBrush
        !           784: ================
        !           785: */
        !           786: void CM_ClipBoxToBrush (vec3_t mins, vec3_t maxs, vec3_t p1, vec3_t p2,
        !           787:                                          trace_t *trace, cbrush_t *brush)
        !           788: {
        !           789:        int                     i, j;
        !           790:        cplane_t        *plane, *clipplane;
        !           791:        float           dist;
        !           792:        float           enterfrac, leavefrac;
        !           793:        vec3_t          ofs;
        !           794:        float           d1, d2;
        !           795:        qboolean        getout, startout;
        !           796:        float           f;
        !           797:        cbrushside_t    *side, *leadside;
        !           798: 
        !           799:        enterfrac = -1;
        !           800:        leavefrac = 1;
        !           801:        clipplane = NULL;
        !           802: 
        !           803:        if (!brush->numsides)
        !           804:                return;
        !           805: 
        !           806:        c_brush_traces++;
        !           807: 
        !           808:        getout = false;
        !           809:        startout = false;
        !           810:        leadside = NULL;
        !           811: 
        !           812:        for (i=0 ; i<brush->numsides ; i++)
        !           813:        {
        !           814:                side = &map_brushsides[brush->firstbrushside+i];
        !           815:                plane = side->plane;
        !           816: 
        !           817:                // FIXME: special case for axial
        !           818: 
        !           819:                if (!trace_ispoint)
        !           820:                {       // general box case
        !           821: 
        !           822:                        // push the plane out apropriately for mins/maxs
        !           823: 
        !           824:                        // FIXME: use signbits into 8 way lookup for each mins/maxs
        !           825:                        for (j=0 ; j<3 ; j++)
        !           826:                        {
        !           827:                                if (plane->normal[j] < 0)
        !           828:                                        ofs[j] = maxs[j];
        !           829:                                else
        !           830:                                        ofs[j] = mins[j];
        !           831:                        }
        !           832:                        dist = DotProduct (ofs, plane->normal);
        !           833:                        dist = plane->dist - dist;
        !           834:                }
        !           835:                else
        !           836:                {       // special point case
        !           837:                        dist = plane->dist;
        !           838:                }
        !           839: 
        !           840:                d1 = DotProduct (p1, plane->normal) - dist;
        !           841:                d2 = DotProduct (p2, plane->normal) - dist;
        !           842: 
        !           843:                if (d2 > 0)
        !           844:                        getout = true;  // endpoint is not in solid
        !           845:                if (d1 > 0)
        !           846:                        startout = true;
        !           847: 
        !           848:                // if completely in front of face, no intersection
        !           849:                if (d1 > 0 && d2 >= d1)
        !           850:                        return;
        !           851: 
        !           852:                if (d1 <= 0 && d2 <= 0)
        !           853:                        continue;
        !           854: 
        !           855:                // crosses face
        !           856:                if (d1 > d2)
        !           857:                {       // enter
        !           858:                        f = (d1-DIST_EPSILON) / (d1-d2);
        !           859:                        if (f > enterfrac)
        !           860:                        {
        !           861:                                enterfrac = f;
        !           862:                                clipplane = plane;
        !           863:                                leadside = side;
        !           864:                        }
        !           865:                }
        !           866:                else
        !           867:                {       // leave
        !           868:                        f = (d1+DIST_EPSILON) / (d1-d2);
        !           869:                        if (f < leavefrac)
        !           870:                                leavefrac = f;
        !           871:                }
        !           872:        }
        !           873: 
        !           874:        if (!startout)
        !           875:        {       // original point was inside brush
        !           876:                trace->startsolid = true;
        !           877:                if (!getout)
        !           878:                        trace->allsolid = true;
        !           879:                return;
        !           880:        }
        !           881:        if (enterfrac < leavefrac)
        !           882:        {
        !           883:                if (enterfrac > -1 && enterfrac < trace->fraction)
        !           884:                {
        !           885:                        if (enterfrac < 0)
        !           886:                                enterfrac = 0;
        !           887:                        trace->fraction = enterfrac;
        !           888:                        trace->plane = *clipplane;
        !           889:                        trace->surface = leadside->surface;
        !           890:                        trace->contents = brush->contents;
        !           891:                }
        !           892:        }
        !           893: }
        !           894: 
        !           895: /*
        !           896: ================
        !           897: CM_TestBoxInBrush
        !           898: ================
        !           899: */
        !           900: void CM_TestBoxInBrush (vec3_t mins, vec3_t maxs, vec3_t p1,
        !           901:                                          trace_t *trace, cbrush_t *brush)
        !           902: {
        !           903:        int                     i, j;
        !           904:        cplane_t        *plane;
        !           905:        float           dist;
        !           906:        vec3_t          ofs;
        !           907:        float           d1;
        !           908:        cbrushside_t    *side;
        !           909: 
        !           910:        if (!brush->numsides)
        !           911:                return;
        !           912: 
        !           913:        for (i=0 ; i<brush->numsides ; i++)
        !           914:        {
        !           915:                side = &map_brushsides[brush->firstbrushside+i];
        !           916:                plane = side->plane;
        !           917: 
        !           918:                // FIXME: special case for axial
        !           919: 
        !           920:                // general box case
        !           921: 
        !           922:                // push the plane out apropriately for mins/maxs
        !           923: 
        !           924:                // FIXME: use signbits into 8 way lookup for each mins/maxs
        !           925:                for (j=0 ; j<3 ; j++)
        !           926:                {
        !           927:                        if (plane->normal[j] < 0)
        !           928:                                ofs[j] = maxs[j];
        !           929:                        else
        !           930:                                ofs[j] = mins[j];
        !           931:                }
        !           932:                dist = DotProduct (ofs, plane->normal);
        !           933:                dist = plane->dist - dist;
        !           934: 
        !           935:                d1 = DotProduct (p1, plane->normal) - dist;
        !           936: 
        !           937:                // if completely in front of face, no intersection
        !           938:                if (d1 > 0)
        !           939:                        return;
        !           940: 
        !           941:        }
        !           942: 
        !           943:        // inside this brush
        !           944:        trace->startsolid = trace->allsolid = true;
        !           945:        trace->fraction = 0;
        !           946:        trace->contents = brush->contents;
        !           947: }
        !           948: 
        !           949: /*
        !           950: ================
        !           951: CM_TraceToLeaf
        !           952: ================
        !           953: */
        !           954: void CM_TraceToLeaf (int leafnum)
        !           955: {
        !           956:        int                     k;
        !           957:        int                     brushnum;
        !           958:        cleaf_t         *leaf;
        !           959:        cbrush_t        *b;
        !           960: 
        !           961:        leaf = &map_leafs[leafnum];
        !           962:        if ( !(leaf->contents & trace_contents))
        !           963:                return;
        !           964:        // trace line against all brushes in the leaf
        !           965:        for (k=0 ; k<leaf->numleafbrushes ; k++)
        !           966:        {
        !           967:                brushnum = map_leafbrushes[leaf->firstleafbrush+k];
        !           968:                b = &map_brushes[brushnum];
        !           969:                if (b->checkcount == checkcount)
        !           970:                        continue;       // already checked this brush in another leaf
        !           971:                b->checkcount = checkcount;
        !           972: 
        !           973:                if ( !(b->contents & trace_contents))
        !           974:                        continue;
        !           975:                CM_ClipBoxToBrush (trace_mins, trace_maxs, trace_start, trace_end, &trace_trace, b);
        !           976:                if (!trace_trace.fraction)
        !           977:                        return;
        !           978:        }
        !           979: 
        !           980: }
        !           981: 
        !           982: 
        !           983: /*
        !           984: ================
        !           985: CM_TestInLeaf
        !           986: ================
        !           987: */
        !           988: void CM_TestInLeaf (int leafnum)
        !           989: {
        !           990:        int                     k;
        !           991:        int                     brushnum;
        !           992:        cleaf_t         *leaf;
        !           993:        cbrush_t        *b;
        !           994: 
        !           995:        leaf = &map_leafs[leafnum];
        !           996:        if ( !(leaf->contents & trace_contents))
        !           997:                return;
        !           998:        // trace line against all brushes in the leaf
        !           999:        for (k=0 ; k<leaf->numleafbrushes ; k++)
        !          1000:        {
        !          1001:                brushnum = map_leafbrushes[leaf->firstleafbrush+k];
        !          1002:                b = &map_brushes[brushnum];
        !          1003:                if (b->checkcount == checkcount)
        !          1004:                        continue;       // already checked this brush in another leaf
        !          1005:                b->checkcount = checkcount;
        !          1006: 
        !          1007:                if ( !(b->contents & trace_contents))
        !          1008:                        continue;
        !          1009:                CM_TestBoxInBrush (trace_mins, trace_maxs, trace_start, &trace_trace, b);
        !          1010:                if (!trace_trace.fraction)
        !          1011:                        return;
        !          1012:        }
        !          1013: 
        !          1014: }
        !          1015: 
        !          1016: 
        !          1017: /*
        !          1018: ==================
        !          1019: CM_RecursiveHullCheck
        !          1020: ==================
        !          1021: */
        !          1022: void CM_RecursiveHullCheck (int num, float p1f, float p2f, vec3_t p1, vec3_t p2)
        !          1023: {
        !          1024:        cnode_t         *node;
        !          1025:        cplane_t        *plane;
        !          1026:        float           t1, t2, offset;
        !          1027:        float           frac, frac2;
        !          1028:        float           idist;
        !          1029:        int                     i;
        !          1030:        vec3_t          mid;
        !          1031:        int                     side;
        !          1032:        float           midf;
        !          1033:        if (trace_trace.fraction <= p1f)
        !          1034:                return;         // already hit something nearer
        !          1035:        // if < 0, we are in a leaf node
        !          1036:        if (num < 0)
        !          1037:        {
        !          1038:                CM_TraceToLeaf (-1-num);
        !          1039:                return;
        !          1040:        }
        !          1041:        //
        !          1042:        // find the point distances to the seperating plane
        !          1043:        // and the offset for the size of the box
        !          1044:        //
        !          1045:        node = map_nodes + num;
        !          1046:        plane = node->plane;
        !          1047:        if (plane->type < 3)
        !          1048:        {
        !          1049:                t1 = p1[plane->type] - plane->dist;
        !          1050:                t2 = p2[plane->type] - plane->dist;
        !          1051:                offset = trace_extents[plane->type];
        !          1052:        }
        !          1053:        else
        !          1054:        {
        !          1055:                t1 = DotProduct (plane->normal, p1) - plane->dist;
        !          1056:                t2 = DotProduct (plane->normal, p2) - plane->dist;
        !          1057:                if (trace_ispoint)
        !          1058:                        offset = 0;
        !          1059:                else
        !          1060:                        offset = fabs(trace_extents[0]*plane->normal[0]) +
        !          1061:                                fabs(trace_extents[1]*plane->normal[1]) +
        !          1062:                                fabs(trace_extents[2]*plane->normal[2]);
        !          1063:        }
        !          1064: #if 0
        !          1065: CM_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
        !          1066: CM_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
        !          1067: return;
        !          1068: #endif
        !          1069:        // see which sides we need to consider
        !          1070:        if (t1 >= offset && t2 >= offset)
        !          1071:        {
        !          1072:                CM_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
        !          1073:                return;
        !          1074:        }
        !          1075:        if (t1 < -offset && t2 < -offset)
        !          1076:        {
        !          1077:                CM_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
        !          1078:                return;
        !          1079:        }
        !          1080:        // put the crosspoint DIST_EPSILON pixels on the near side
        !          1081:        if (t1 < t2)
        !          1082:        {
        !          1083:                idist = 1.0/(t1-t2);
        !          1084:                side = 1;
        !          1085:                frac2 = (t1 + offset + DIST_EPSILON)*idist;
        !          1086:                frac = (t1 - offset + DIST_EPSILON)*idist;
        !          1087:        }
        !          1088:        else if (t1 > t2)
        !          1089:        {
        !          1090:                idist = 1.0/(t1-t2);
        !          1091:                side = 0;
        !          1092:                frac2 = (t1 - offset - DIST_EPSILON)*idist;
        !          1093:                frac = (t1 + offset + DIST_EPSILON)*idist;
        !          1094:        }
        !          1095:        else
        !          1096:        {
        !          1097:                side = 0;
        !          1098:                frac = 1;
        !          1099:                frac2 = 0;
        !          1100:        }
        !          1101:        // move up to the node
        !          1102:        if (frac < 0)
        !          1103:                frac = 0;
        !          1104:        if (frac > 1)
        !          1105:                frac = 1;
        !          1106:                
        !          1107:        midf = p1f + (p2f - p1f)*frac;
        !          1108:        for (i=0 ; i<3 ; i++)
        !          1109:                mid[i] = p1[i] + frac*(p2[i] - p1[i]);
        !          1110:        CM_RecursiveHullCheck (node->children[side], p1f, midf, p1, mid);
        !          1111:        // go past the node
        !          1112:        if (frac2 < 0)
        !          1113:                frac2 = 0;
        !          1114:        if (frac2 > 1)
        !          1115:                frac2 = 1;
        !          1116:                
        !          1117:        midf = p1f + (p2f - p1f)*frac2;
        !          1118:        for (i=0 ; i<3 ; i++)
        !          1119:                mid[i] = p1[i] + frac2*(p2[i] - p1[i]);
        !          1120:        CM_RecursiveHullCheck (node->children[side^1], midf, p2f, mid, p2);
        !          1121: }
        !          1122: //======================================================================
        !          1123: /*
        !          1124: ==================
        !          1125: CM_BoxTrace
        !          1126: ==================
        !          1127: */
        !          1128: trace_t                CM_BoxTrace (vec3_t start, vec3_t end,
        !          1129:                                                  vec3_t mins, vec3_t maxs,
        !          1130:                                                  int headnode, int brushmask)
        !          1131: {
        !          1132:        int             i;
        !          1133:        checkcount++;           // for multi-check avoidance
        !          1134:        c_traces++;                     // for statistics, may be zeroed
        !          1135:        // fill in a default trace
        !          1136:        memset (&trace_trace, 0, sizeof(trace_trace));
        !          1137:        trace_trace.fraction = 1;
        !          1138:        trace_trace.surface = &nullsurface;
        !          1139: 
        !          1140:        if (!numnodes)  // map not loaded
        !          1141:                return trace_trace;
        !          1142:        trace_contents = brushmask;
        !          1143:        VectorCopy (start, trace_start);
        !          1144:        VectorCopy (end, trace_end);
        !          1145:        VectorCopy (mins, trace_mins);
        !          1146:        VectorCopy (maxs, trace_maxs);
        !          1147: 
        !          1148:        //
        !          1149:        // check for position test special case
        !          1150:        //
        !          1151:        if (start[0] == end[0] && start[1] == end[1] && start[2] == end[2])
        !          1152:        {
        !          1153:                int             leafs[1024];
        !          1154:                int             i, numleafs;
        !          1155:                vec3_t  c1, c2;
        !          1156:                int             topnode;
        !          1157: 
        !          1158:                VectorAdd (start, mins, c1);
        !          1159:                VectorAdd (start, maxs, c2);
        !          1160:                for (i=0 ; i<3 ; i++)
        !          1161:                {
        !          1162:                        c1[i] -= 1;
        !          1163:                        c2[i] += 1;
        !          1164:                }
        !          1165: 
        !          1166:                numleafs = CM_BoxLeafnums_headnode (c1, c2, leafs, 1024, headnode, &topnode);
        !          1167:                for (i=0 ; i<numleafs ; i++)
        !          1168:                {
        !          1169:                        CM_TestInLeaf (leafs[i]);
        !          1170:                        if (trace_trace.allsolid)
        !          1171:                                break;
        !          1172:                }
        !          1173:                VectorCopy (start, trace_trace.endpos);
        !          1174:                return trace_trace;
        !          1175:        }
        !          1176: 
        !          1177:        //
        !          1178:        // check for point special case
        !          1179:        //
        !          1180:        if (mins[0] == 0 && mins[1] == 0 && mins[2] == 0
        !          1181:                && maxs[0] == 0 && maxs[1] == 0 && maxs[2] == 0)
        !          1182:        {
        !          1183:                trace_ispoint = true;
        !          1184:                VectorClear (trace_extents);
        !          1185:        }
        !          1186:        else
        !          1187:        {
        !          1188:                trace_ispoint = false;
        !          1189:                trace_extents[0] = -mins[0] > maxs[0] ? -mins[0] : maxs[0];
        !          1190:                trace_extents[1] = -mins[1] > maxs[1] ? -mins[1] : maxs[1];
        !          1191:                trace_extents[2] = -mins[2] > maxs[2] ? -mins[2] : maxs[2];
        !          1192:        }
        !          1193: 
        !          1194:        //
        !          1195:        // general sweeping through world
        !          1196:        //
        !          1197:        CM_RecursiveHullCheck (headnode, 0, 1, start, end);
        !          1198:        if (trace_trace.fraction == 1)
        !          1199:        {
        !          1200:                VectorCopy (end, trace_trace.endpos);
        !          1201:        }
        !          1202:        else
        !          1203:        {
        !          1204:                for (i=0 ; i<3 ; i++)
        !          1205:                        trace_trace.endpos[i] = start[i] + trace_trace.fraction * (end[i] - start[i]);
        !          1206:        }
        !          1207:        return trace_trace;
        !          1208: }
        !          1209: /*
        !          1210: ==================
        !          1211: CM_TransformedBoxTrace
        !          1212: Handles offseting and rotation of the end points for moving and
        !          1213: rotating entities
        !          1214: ==================
        !          1215: */
        !          1216: #ifdef _WIN32
        !          1217: #pragma optimize( "", off )
        !          1218: #endif
        !          1219: 
        !          1220: 
        !          1221: trace_t                CM_TransformedBoxTrace (vec3_t start, vec3_t end,
        !          1222:                                                  vec3_t mins, vec3_t maxs,
        !          1223:                                                  int headnode, int brushmask,
        !          1224:                                                  vec3_t origin, vec3_t angles)
        !          1225: {
        !          1226:        trace_t         trace;
        !          1227:        vec3_t          start_l, end_l;
        !          1228:        vec3_t          a;
        !          1229:        vec3_t          forward, right, up;
        !          1230:        vec3_t          temp;
        !          1231:        qboolean        rotated;
        !          1232:        // subtract origin offset
        !          1233:        VectorSubtract (start, origin, start_l);
        !          1234:        VectorSubtract (end, origin, end_l);
        !          1235:        // rotate start and end into the models frame of reference
        !          1236:        if (headnode != box_headnode && 
        !          1237:        (angles[0] || angles[1] || angles[2]) )
        !          1238:                rotated = true;
        !          1239:        else
        !          1240:                rotated = false;
        !          1241:        if (rotated)
        !          1242:        {
        !          1243:                AngleVectors (angles, forward, right, up);
        !          1244:                VectorCopy (start_l, temp);
        !          1245:                start_l[0] = DotProduct (temp, forward);
        !          1246:                start_l[1] = -DotProduct (temp, right);
        !          1247:                start_l[2] = DotProduct (temp, up);
        !          1248:                VectorCopy (end_l, temp);
        !          1249:                end_l[0] = DotProduct (temp, forward);
        !          1250:                end_l[1] = -DotProduct (temp, right);
        !          1251:                end_l[2] = DotProduct (temp, up);
        !          1252:        }
        !          1253:        // sweep the box through the model
        !          1254:        trace = CM_BoxTrace (start_l, end_l, mins, maxs, headnode, brushmask);
        !          1255:        if (rotated && trace.fraction != 1.0)
        !          1256:        {
        !          1257:                // FIXME: figure out how to do this with existing angles
        !          1258:                VectorNegate (angles, a);
        !          1259:                AngleVectors (a, forward, right, up);
        !          1260:                VectorCopy (trace.plane.normal, temp);
        !          1261:                trace.plane.normal[0] = DotProduct (temp, forward);
        !          1262:                trace.plane.normal[1] = -DotProduct (temp, right);
        !          1263:                trace.plane.normal[2] = DotProduct (temp, up);
        !          1264:        }
        !          1265:        trace.endpos[0] = start[0] + trace.fraction * (end[0] - start[0]);
        !          1266:        trace.endpos[1] = start[1] + trace.fraction * (end[1] - start[1]);
        !          1267:        trace.endpos[2] = start[2] + trace.fraction * (end[2] - start[2]);
        !          1268:        return trace;
        !          1269: }
        !          1270: #ifdef _WIN32
        !          1271: #pragma optimize( "", on )
        !          1272: #endif
        !          1273: 
        !          1274: 
        !          1275: /*
        !          1276: ===============================================================================
        !          1277: PVS / PHS
        !          1278: ===============================================================================
        !          1279: */
        !          1280: /*
        !          1281: ===================
        !          1282: CM_DecompressVis
        !          1283: ===================
        !          1284: */
        !          1285: void CM_DecompressVis (byte *in, byte *out)
        !          1286: {
        !          1287:        int             c;
        !          1288:        byte    *out_p;
        !          1289:        int             row;
        !          1290:        row = (numclusters+7)>>3;       
        !          1291:        out_p = out;
        !          1292: 
        !          1293:        if (!in || !numvisibility)
        !          1294:        {       // no vis info, so make all visible
        !          1295:                while (row)
        !          1296:                {
        !          1297:                        *out_p++ = 0xff;
        !          1298:                        row--;
        !          1299:                }
        !          1300:                return;         
        !          1301:        }
        !          1302:        do
        !          1303:        {
        !          1304:                if (*in)
        !          1305:                {
        !          1306:                        *out_p++ = *in++;
        !          1307:                        continue;
        !          1308:                }
        !          1309:        
        !          1310:                c = in[1];
        !          1311:                in += 2;
        !          1312:                if ((out_p - out) + c > row)
        !          1313:                {
        !          1314:                        c = row - (out_p - out);
        !          1315:                        Com_DPrintf ("warning: Vis decompression overrun\n");
        !          1316:                }
        !          1317:                while (c)
        !          1318:                {
        !          1319:                        *out_p++ = 0;
        !          1320:                        c--;
        !          1321:                }
        !          1322:        } while (out_p - out < row);
        !          1323: }
        !          1324: byte   pvsrow[MAX_MAP_LEAFS/8];
        !          1325: byte   phsrow[MAX_MAP_LEAFS/8];
        !          1326: byte   *CM_ClusterPVS (int cluster)
        !          1327: {
        !          1328:        if (cluster == -1)
        !          1329:                memset (pvsrow, 0, (numclusters+7)>>3);
        !          1330:        else
        !          1331:                CM_DecompressVis (map_visibility + map_vis->bitofs[cluster][DVIS_PVS], pvsrow);
        !          1332:        return pvsrow;
        !          1333: }
        !          1334: byte   *CM_ClusterPHS (int cluster)
        !          1335: {
        !          1336:        if (cluster == -1)
        !          1337:                memset (phsrow, 0, (numclusters+7)>>3);
        !          1338:        else
        !          1339:                CM_DecompressVis (map_visibility + map_vis->bitofs[cluster][DVIS_PHS], phsrow);
        !          1340:        return phsrow;
        !          1341: }
        !          1342: /*
        !          1343: ===============================================================================
        !          1344: AREAPORTALS
        !          1345: ===============================================================================
        !          1346: */
        !          1347: void FloodArea_r (carea_t *area, int floodnum)
        !          1348: {
        !          1349:        int             i;
        !          1350:        dareaportal_t   *p;
        !          1351:        if (area->floodvalid == floodvalid)
        !          1352:        {
        !          1353:                if (area->floodnum == floodnum)
        !          1354:                        return;
        !          1355:                Com_Error (ERR_DROP, "FloodArea_r: reflooded");
        !          1356:        }
        !          1357:        area->floodnum = floodnum;
        !          1358:        area->floodvalid = floodvalid;
        !          1359:        p = &map_areaportals[area->firstareaportal];
        !          1360:        for (i=0 ; i<area->numareaportals ; i++, p++)
        !          1361:        {
        !          1362:                if (portalopen[p->portalnum])
        !          1363:                        FloodArea_r (&map_areas[p->otherarea], floodnum);
        !          1364:        }
        !          1365: }
        !          1366: /*
        !          1367: ====================
        !          1368: FloodAreaConnections
        !          1369: ====================
        !          1370: */
        !          1371: void   FloodAreaConnections (void)
        !          1372: {
        !          1373:        int             i;
        !          1374:        carea_t *area;
        !          1375:        int             floodnum;
        !          1376:        // all current floods are now invalid
        !          1377:        floodvalid++;
        !          1378:        floodnum = 0;
        !          1379:        // area 0 is not used
        !          1380:        for (i=1 ; i<numareas ; i++)
        !          1381:        {
        !          1382:                area = &map_areas[i];
        !          1383:                if (area->floodvalid == floodvalid)
        !          1384:                        continue;               // already flooded into
        !          1385:                floodnum++;
        !          1386:                FloodArea_r (area, floodnum);
        !          1387:        }
        !          1388: }
        !          1389: void   CM_SetAreaPortalState (int portalnum, qboolean open)
        !          1390: {
        !          1391:        if (portalnum > numareaportals)
        !          1392:                Com_Error (ERR_DROP, "areaportal > numareaportals");
        !          1393:        portalopen[portalnum] = open;
        !          1394:        FloodAreaConnections ();
        !          1395: }
        !          1396: qboolean       CM_AreasConnected (int area1, int area2)
        !          1397: {
        !          1398:        if (map_noareas->value)
        !          1399:                return true;
        !          1400:        if (area1 > numareas || area2 > numareas)
        !          1401:                Com_Error (ERR_DROP, "area > numareas");
        !          1402:        if (map_areas[area1].floodnum == map_areas[area2].floodnum)
        !          1403:                return true;
        !          1404:        return false;
        !          1405: }
        !          1406: /*
        !          1407: =================
        !          1408: CM_WriteAreaBits
        !          1409: Writes a length byte followed by a bit vector of all the areas
        !          1410: that area in the same flood as the area parameter
        !          1411: This is used by the client refreshes to cull visibility
        !          1412: =================
        !          1413: */
        !          1414: int CM_WriteAreaBits (byte *buffer, int area)
        !          1415: {
        !          1416:        int             i;
        !          1417:        int             floodnum;
        !          1418:        int             bytes;
        !          1419:        bytes = (numareas+7)>>3;
        !          1420:        if (map_noareas->value)
        !          1421:        {       // for debugging, send everything
        !          1422:                memset (buffer, 255, bytes);
        !          1423:        }
        !          1424:        else
        !          1425:        {
        !          1426:                memset (buffer, 0, bytes);
        !          1427:                floodnum = map_areas[area].floodnum;
        !          1428:                for (i=0 ; i<numareas ; i++)
        !          1429:                {
        !          1430:                        if (map_areas[i].floodnum == floodnum || !area)
        !          1431:                                buffer[i>>3] |= 1<<(i&7);
        !          1432:                }
        !          1433:        }
        !          1434:        return bytes;
        !          1435: }
        !          1436: /*
        !          1437: ===================
        !          1438: CM_WritePortalState
        !          1439: Writes the portal state to a savegame file
        !          1440: ===================
        !          1441: */
        !          1442: void   CM_WritePortalState (FILE *f)
        !          1443: {
        !          1444:        fwrite (portalopen, sizeof(portalopen), 1, f);
        !          1445: }
        !          1446: /*
        !          1447: ===================
        !          1448: CM_ReadPortalState
        !          1449: Reads the portal state from a savegame file
        !          1450: and recalculates the area connections
        !          1451: ===================
        !          1452: */
        !          1453: void   CM_ReadPortalState (FILE *f)
        !          1454: {
        !          1455:        FS_Read (portalopen, sizeof(portalopen), f);
        !          1456:        FloodAreaConnections ();
        !          1457: }
        !          1458: /*
        !          1459: =============
        !          1460: CM_HeadnodeVisible
        !          1461: Returns true if any leaf under headnode has a cluster that
        !          1462: is potentially visible
        !          1463: =============
        !          1464: */
        !          1465: qboolean CM_HeadnodeVisible (int nodenum, byte *visbits)
        !          1466: {
        !          1467:        int             leafnum;
        !          1468:        int             cluster;
        !          1469:        cnode_t *node;
        !          1470:        if (nodenum < 0)
        !          1471:        {
        !          1472:                leafnum = -1-nodenum;
        !          1473:                cluster = map_leafs[leafnum].cluster;
        !          1474:                if (cluster == -1)
        !          1475:                        return false;
        !          1476:                if (visbits[cluster>>3] & (1<<(cluster&7)))
        !          1477:                        return true;
        !          1478:                return false;
        !          1479:        }
        !          1480:        node = &map_nodes[nodenum];
        !          1481:        if (CM_HeadnodeVisible(node->children[0], visbits))
        !          1482:                return true;
        !          1483:        return CM_HeadnodeVisible(node->children[1], visbits);
        !          1484: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.