utils/themeeditor/graphics/rbfontcache.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/***************************************************************************
 *             __________               __   ___.
 *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
 *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
 *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
 *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
 *                     \/            \/     \/    \/            \/
 * $Id$
 *
 * Copyright (C) 2010 Robert Bieber
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 ****************************************************************************/

#include "rbfontcache.h"

QHash<QString, RBFontCache::CacheInfo*> RBFontCache::cache;

void RBFontCache::clearCache()
{
    QHash<QString, CacheInfo*>::iterator i;
    for(i = cache.begin(); i != cache.end(); i++)
    {
        CacheInfo* c = *i;
        if(c->imageData)
            delete c->imageData;

        if(c->offsetData)
            delete c->offsetData;

        if(c->widthData)
            delete c->widthData;

        delete c;
    }

    cache.clear();
}
/* Emacs style mode select   -*- C++ -*-
 *-----------------------------------------------------------------------------
 *
 *
 *  PrBoom a Doom port merged with LxDoom and LSDLDoom
 *  based on BOOM, a modified and improved DOOM engine
 *  Copyright (C) 1999 by
 *  id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
 *  Copyright (C) 1999-2000 by
 *  Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 2
 *  of the License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 *  02111-1307, USA.
 *
 * DESCRIPTION:
 *  Do all the WAD I/O, get map description,
 *  set up initial state and misc. LUTs.
 *
 *-----------------------------------------------------------------------------*/

#include <math.h>

#include "doomstat.h"
#include "m_bbox.h"
#include "m_argv.h"
#include "g_game.h"
#include "w_wad.h"
#include "r_main.h"
#include "r_things.h"
#include "p_maputl.h"
#include "p_map.h"
#include "p_setup.h"
#include "p_spec.h"
#include "p_tick.h"
#include "p_enemy.h"
#include "s_sound.h"
#include "i_system.h"
#include "m_swap.h"

#include "rockmacros.h"
//
// MAP related Lookup tables.
// Store VERTEXES, LINEDEFS, SIDEDEFS, etc.
//

int      numvertexes;
vertex_t *vertexes;

int      numsegs;
seg_t    *segs;

int      numsectors;
sector_t *sectors;

int      numsubsectors;
subsector_t *subsectors;

int      numnodes;
node_t   *nodes;

int      numlines;
line_t   *lines;

int      numsides;
side_t   *sides;


////////////////////////////////////////////////////////////////////////////////////////////
// figgi 08/21/00 -- constants and globals for glBsp support
#define gNd2            0x32644E67  // figgi -- suppport for new GL_VERT format v2.0
#define GL_VERT_OFFSET  4

int     firstglvertex = 0;
boolean usingGLNodes  = false;
boolean forceOldBsp   = false;

enum
{
   ML_GL_LABEL=0,  // A separator name, GL_ExMx or GL_MAPxx
   ML_GL_VERTS,     // Extra Vertices
   ML_GL_SEGS,     // Segs, from linedefs & minisegs
   ML_GL_SSECT,    // SubSectors, list of segs
   ML_GL_NODES     // GL BSP nodes
};
////////////////////////////////////////////////////////////////////////////////////////////


// BLOCKMAP
// Created from axis aligned bounding box
// of the map, a rectangular array of
// blocks of size ...
// Used to speed up collision detection
// by spatial subdivision in 2D.
//
// Blockmap size.

int       bmapwidth, bmapheight;  // size in mapblocks

// killough 3/1/98: remove blockmap limit internally:
long      *blockmap;              // was short -- killough

// offsets in blockmap are from here
long      *blockmaplump;          // was short -- killough

fixed_t   bmaporgx, bmaporgy;     // origin of block map

mobj_t    **blocklinks;           // for thing chains

//
// REJECT
// For fast sight rejection.
// Speeds up enemy AI by skipping detailed
//  LineOf Sight calculation.
// Without the special effect, this could
// be used as a PVS lookup as well.
//

static int rejectlump = -1;// cph - store reject lump num if cached
const byte *rejectmatrix; // cph - const*

// Maintain single and multi player starting spots.

// 1/11/98 killough: Remove limit on deathmatch starts
mapthing_t *deathmatchstarts;      // killough
size_t     num_deathmatchstarts;   // killough

mapthing_t *deathmatch_p;
mapthing_t playerstarts[MAXPLAYERS];

//
// P_LoadVertexes
//
// killough 5/3/98: reformatted, cleaned up
//
static void P_LoadVertexes (int lump)
{
   const byte *data; // cph - const
   int i;

   // Determine number of lumps:
   //  total lump length / vertex record length.
   numvertexes = W_LumpLength(lump) / sizeof(mapvertex_t);

   // Allocate zone memory for buffer.
   vertexes = Z_Malloc(numvertexes*sizeof(vertex_t),PU_LEVEL,0);

   // Load data into cache.
   data = W_CacheLumpNum(lump); // cph - wad handling updated

   // Copy and convert vertex coordinates,
   // internal representation as fixed.
   for (i=0; i<numvertexes; i++)
   {
      vertexes[i].x = SHORT(((mapvertex_t *) data)[i].x)<<FRACBITS;
      vertexes[i].y = SHORT(((mapvertex_t *) data)[i].y)<<FRACBITS;
   }

   // Free buffer memory.
   W_UnlockLumpNum(lump);
}

//
// P_LoadSegs
//
// killough 5/3/98: reformatted, cleaned up

static void P_LoadSegs (int lump)
{
   int  i;
   const byte *data; // cph - const

   numsegs = W_LumpLength(lump) / sizeof(mapseg_t);
   segs = Z_Calloc(numsegs,sizeof(seg_t),PU_LEVEL,0);
   data = W_CacheLumpNum(lump); // cph - wad lump handling updated

   for (i=0; i<numsegs; i++)
   {
      seg_t *li = segs+i;
      mapseg_t *ml = (mapseg_t *) data + i;

      int side, linedef;
      line_t *ldef;

      li->v1 = &vertexes[SHORT(ml->v1)];
      li->v2 = &vertexes[SHORT(ml->v2)];

      li->miniseg = false; // figgi -- there are no minisegs in classic BSP nodes

      li->angle = (SHORT(ml->angle))<<16;
      li->offset =(SHORT(ml->offset))<<16;
      linedef = SHORT(ml->linedef);
      ldef = &lines[linedef];
      li->linedef = ldef;
      side = SHORT(ml->side);
      li->sidedef = &sides[ldef->sidenum[side]];
      li->frontsector = sides[ldef->sidenum[side]].sector;

      // killough 5/3/98: ignore 2s flag if second sidedef missing:
      if (ldef->flags & ML_TWOSIDED && ldef->sidenum[side^1]!=-1)
         li->backsector = sides[ldef->sidenum[side^1]].sector;
      else
         li->backsector = 0;
   }

   W_UnlockLumpNum(lump); // cph - release the data
}


//
// P_LoadSubsectors
//
// killough 5/3/98: reformatted, cleaned up

static void P_LoadSubsectors (int lump)
{
   const byte *data; // cph - const*
   int  i;

   numsubsectors = W_LumpLength (lump) / sizeof(mapsubsector_t);
   subsectors = Z_Calloc(numsubsectors,sizeof(subsector_t),PU_LEVEL,0);
   data = W_CacheLumpNum(lump); // cph - wad lump handling updated

   for (i=0; i<numsubsectors; i++)
   {
      subsectors[i].numlines  = (unsigned short)SHORT(((mapsubsector_t *) data)[i].numsegs );
      subsectors[i].firstline = (unsigned short)SHORT(((mapsubsector_t *) data)[i].firstseg);
   }

   W_UnlockLumpNum(lump); // cph - release the data
}

//
// P_LoadSectors
//
// killough 5/3/98: reformatted, cleaned up

static void P_LoadSectors (int lump)
{
   const byte *data; // cph - const*
   int  i;

   numsectors = W_LumpLength (lump) / sizeof(mapsector_t);
   sectors = Z_Calloc (numsectors,sizeof(sector_t),PU_LEVEL,0);
   data = W_CacheLumpNum (lump); // cph - wad lump handling updated

   for (i=0; i<numsectors; i++)
   {
      sector_t *ss = sectors + i;
      const mapsector_t *ms = (mapsector_t *) data + i;

      ss->floorheight = SHORT(ms->floorheight)<<FRACBITS;
      ss->ceilingheight = SHORT(ms->ceilingheight)<<FRACBITS;
      ss->floorpic = R_FlatNumForName(ms->floorpic);
      ss->ceilingpic = R_FlatNumForName(ms->ceilingpic);
      ss->lightlevel = SHORT(ms->lightlevel);
      ss->special = SHORT(ms->special);
      ss->oldspecial = SHORT(ms->special);
      ss->tag = SHORT(ms->tag);
      ss->thinglist = NULL;
      ss->touching_thinglist = NULL;            // phares 3/14/98

      ss->nextsec = -1; //jff 2/26/98 add fields to support locking out
      ss->prevsec = -1; // stair retriggering until build completes

      // killough 3/7/98:
      ss->floor_xoffs = 0;
      ss->floor_yoffs = 0;      // floor and ceiling flats offsets
      ss->ceiling_xoffs = 0;
      ss->ceiling_yoffs = 0;
      ss->heightsec = -1;       // sector used to get floor and ceiling height
      ss->floorlightsec = -1;   // sector used to get floor lighting
      // killough 3/7/98: end changes

      // killough 4/11/98 sector used to get ceiling lighting:
      ss->ceilinglightsec = -1;

      // killough 4/4/98: colormaps:
      ss->bottommap = ss->midmap = ss->topmap = 0;

      // killough 10/98: sky textures coming from sidedefs:
      ss->sky = 0;
   }

   W_UnlockLumpNum(lump); // cph - release the data
}


//
// P_LoadNodes
//
// killough 5/3/98: reformatted, cleaned up

static void P_LoadNodes (int lump)
{
   const byte *data; // cph - const*
   int  i;

   numnodes = W_LumpLength (lump) / sizeof(mapnode_t);
   nodes = Z_Malloc (numnodes*sizeof(node_t),PU_LEVEL,0);
   data = W_CacheLumpNum (lump); // cph - wad lump handling updated

   for (i=0; i<numnodes; i++)
   {
      node_t *no = nodes + i;
      mapnode_t *mn = (mapnode_t *) data + i;
      int j;

      no->x = SHORT(mn->x)<<FRACBITS;
      no->y = SHORT(mn->y)<<FRACBITS;
      no->dx = SHORT(mn->dx)<<FRACBITS;
      no->dy = SHORT(mn->dy)<<FRACBITS;

      for (j=0 ; j<2 ; j++)
      {
         int k;
         no->children[j] = SHORT(mn->children[j]);
         for (k=0 ; k<4 ; k++)
            no->bbox[j][k] = SHORT(mn->bbox[j][k])<<FRACBITS;
      }
   }

   W_UnlockLumpNum(lump); // cph - release the data
}


//
// P_LoadThings
//
// killough 5/3/98: reformatted, cleaned up

static void P_LoadThings (int lump)
{
   mapthing_t tempthing; // this needed to be added as the SHORT calls were overwriting eachother on reload
   int  i, numthings = W_LumpLength (lump) / sizeof(mapthing_t);
   const byte *data = W_CacheLumpNum (lump); // cph - wad lump handling updated, const*

   for (i=0; i<numthings; i++)
   {
      mapthing_t *mt = (mapthing_t *) data + i;

      // Do not spawn cool, new monsters if !commercial
      if (gamemode != commercial)
         switch(mt->type)
         {
         case 68:  // Arachnotron
         case 64:  // Archvile
         case 88:  // Boss Brain
         case 89:  // Boss Shooter
         case 69:  // Hell Knight
         case 67:  // Mancubus
         case 71:  // Pain Elemental
         case 65:  // Former Human Commando
         case 66:  // Revenant
         case 84:  // Wolf SS
            continue;
         }

      // Do spawn all other stuff.
      tempthing.x = SHORT(mt->x);
      tempthing.y = SHORT(mt->y);
      tempthing.angle = SHORT(mt->angle);
      tempthing.type = SHORT(mt->type);
      tempthing.options = SHORT(mt->options);

      P_SpawnMapThing (&tempthing);
   }

   W_UnlockLumpNum(lump); // cph - release the data
}

//
// P_LoadLineDefs
// Also counts secret lines for intermissions.
//        ^^^
// ??? killough ???
// Does this mean secrets used to be linedef-based, rather than sector-based?
//
// killough 4/4/98: split into two functions, to allow sidedef overloading
//
// killough 5/3/98: reformatted, cleaned up

static void P_LoadLineDefs (int lump)
{
   const byte *data; // cph - const*
   int  i;

   numlines = W_LumpLength (lump) / sizeof(maplinedef_t);
   lines = Z_Calloc (numlines,sizeof(line_t),PU_LEVEL,0);
   data = W_CacheLumpNum (lump); // cph - wad lump handling updated

   for (i=0; i<numlines; i++)
   {
      maplinedef_t *mld = (maplinedef_t *) data + i;
      line_t *ld = lines+i;
      vertex_t *v1, *v2;

      ld->flags = SHORT(mld->flags);
      ld->special = SHORT(mld->special);
      ld->tag = SHORT(mld->tag);
      v1 = ld->v1 = &vertexes[SHORT(mld->v1)];
      v2 = ld->v2 = &vertexes[SHORT(mld->v2)];
      ld->dx = v2->x - v1->x;
      ld->dy = v2->y - v1->y;

      ld->tranlump = -1;   // killough 4/11/98: no translucency by default

      ld->slopetype = !ld->dx ? ST_VERTICAL : !ld->dy ? ST_HORIZONTAL :
                      FixedDiv(ld->dy, ld->dx) > 0 ? ST_POSITIVE : ST_NEGATIVE;

      if (v1->x < v2->x)
      {
         ld->bbox[BOXLEFT] = v1->x;
         ld->bbox[BOXRIGHT] = v2->x;
      }
      else
      {
         ld->bbox[BOXLEFT] = v2->x;
         ld->bbox[BOXRIGHT] = v1->x;
      }

      if (v1->y < v2->y)
      {
         ld->bbox[BOXBOTTOM] = v1->y;
         ld->bbox[BOXTOP] = v2->y;
      }
      else
      {
         ld->bbox[BOXBOTTOM] = v2->y;
         ld->bbox[BOXTOP] = v1->y;
      }

      ld->sidenum[0] = SHORT(mld->sidenum[0]);
      ld->sidenum[1] = SHORT(mld->sidenum[1]);

      // killough 4/4/98: support special sidedef interpretation below
      if (ld->sidenum[0] != -1 && ld->special)
         sides[*ld->sidenum].special = ld->special;
   }

   W_UnlockLumpNum(lump); // cph - release the lump
}

// killough 4/4/98: delay using sidedefs until they are loaded
// killough 5/3/98: reformatted, cleaned up

static void P_LoadLineDefs2(int lump)
{
   (void)lump;
   int i = numlines;
   register line_t *ld = lines;
   for (;i--;ld++)
   {
      { // cph 2002/07/20 - these errors are fatal if not fixed, so apply them in compatibility mode - a desync is better than a crash!
         // killough 11/98: fix common wad errors (missing sidedefs):

         if (ld->sidenum[0] == -1) {
            ld->sidenum[0] = 0;  // Substitute dummy sidedef for missing right side
            // cph - print a warning about the bug
            printf("P_LoadSegs: linedef %d missing first sidedef\n",numlines-i);
         }

         if ((ld->sidenum[1] == -1) && (ld->flags & ML_TWOSIDED)) {
            ld->flags &= ~ML_TWOSIDED;  // Clear 2s flag for missing left side
            // cph - print a warning about the bug
            printf("P_LoadSegs: linedef %d has two-sided flag set, but no second sidedef\n",numlines-i);
         }
      }

      ld->frontsector = ld->sidenum[0]!=-1 ? sides[ld->sidenum[0]].sector : 0;
      ld->backsector  = ld->sidenum[1]!=-1 ? sides[ld->sidenum[1]].sector : 0;
      switch (ld->special)
      {                       // killough 4/11/98: handle special types
         int lump, j;

      case 260:               // killough 4/11/98: translucent 2s textures
         lump = sides[*ld->sidenum].special; // translucency from sidedef
         if (!ld->tag)                       // if tag==0,
            ld->tranlump = lump;              // affect this linedef only
         else
            for (j=0;j<numlines;j++)          // if tag!=0,
               if (lines[j].tag == ld->tag)    // affect all matching linedefs
                  lines[j].tranlump = lump;
         break;
      }
   }
}

//
// P_LoadSideDefs
//
// killough 4/4/98: split into two functions

static void P_LoadSideDefs (int lump)
{
   numsides = W_LumpLength(lump) / sizeof(mapsidedef_t);
   sides = Z_Calloc(numsides,sizeof(side_t),PU_LEVEL,0);
}

// killough 4/4/98: delay using texture names until
// after linedefs are loaded, to allow overloading.
// killough 5/3/98: reformatted, cleaned up

static void P_LoadSideDefs2(int lump)
{
   const byte *data = W_CacheLumpNum(lump); // cph - const*, wad lump handling updated
   int  i;

   for (i=0; i<numsides; i++)
   {
      register mapsidedef_t *msd = (mapsidedef_t *) data + i;
      register side_t *sd = sides + i;
      register sector_t *sec;

      sd->textureoffset = SHORT(msd->textureoffset)<<FRACBITS;
      sd->rowoffset = SHORT(msd->rowoffset)<<FRACBITS;

      // killough 4/4/98: allow sidedef texture names to be overloaded
      // killough 4/11/98: refined to allow colormaps to work as wall
      // textures if invalid as colormaps but valid as textures.

      sd->sector = sec = &sectors[SHORT(msd->sector)];
      switch (sd->special)
      {
      case 242:                       // variable colormap via 242 linedef
         sd->bottomtexture =
            (sec->bottommap =   R_ColormapNumForName(msd->bottomtexture)) < 0 ?
            sec->bottommap = 0, R_TextureNumForName(msd->bottomtexture): 0 ;
         sd->midtexture =
            (sec->midmap =   R_ColormapNumForName(msd->midtexture)) < 0 ?
            sec->midmap = 0, R_TextureNumForName(msd->midtexture)  : 0 ;
         sd->toptexture =
            (sec->topmap =   R_ColormapNumForName(msd->toptexture)) < 0 ?
            sec->topmap = 0, R_TextureNumForName(msd->toptexture)  : 0 ;
         break;

      case 260: // killough 4/11/98: apply translucency to 2s normal texture
         sd->midtexture = strncasecmp("TRANMAP", msd->midtexture, 8) ?
                          (sd->special = W_CheckNumForName(msd->midtexture)) < 0 ||
                          W_LumpLength(sd->special) != 65536 ?
                          sd->special=0, R_TextureNumForName(msd->midtexture) :
                                      (sd->special++, 0) : (sd->special=0);
         sd->toptexture = R_TextureNumForName(msd->toptexture);
         sd->bottomtexture = R_TextureNumForName(msd->bottomtexture);
         break;

      default:                        // normal cases
         sd->midtexture = R_TextureNumForName(msd->midtexture);
         sd->toptexture = R_TextureNumForName(msd->toptexture);
         sd->bottomtexture = R_TextureNumForName(msd->bottomtexture);
         break;
      }
   }

   W_UnlockLumpNum(lump); // cph - release the lump
}

//
// jff 10/6/98
// New code added to speed up calculation of internal blockmap
// Algorithm is order of nlines*(ncols+nrows) not nlines*ncols*nrows
//

#define blkshift 7               /* places to shift rel position for cell num */
#define blkmask ((1<<blkshift)-1)/* mask for rel position within cell */
#define blkmargin 0              /* size guardband around map used */
// jff 10/8/98 use guardband>0
// jff 10/12/98 0 ok with + 1 in rows,cols

typedef struct linelist_t        // type used to list lines in each block
{
   long num;
   struct linelist_t *next;
} linelist_t;

//
// Subroutine to add a line number to a block list
// It simply returns if the line is already in the block
//

static void AddBlockLine
(
   linelist_t **lists,
   int *count,
   int *done,
   int blockno,
   long lineno
)
{
   linelist_t *l;

   if (done[blockno])
      return;

   l = malloc(sizeof(linelist_t));
   l->num = lineno;
   l->next = lists[blockno];
   lists[blockno] = l;
   count[blockno]++;
   done[blockno] = 1;
}

//
// Actually construct the blockmap lump from the level data
//
// This finds the intersection of each linedef with the column and
// row lines at the left and bottom of each blockmap cell. It then
// adds the line to all block lists touching the intersection.
//

void P_CreateBlockMap()
{
   int xorg,yorg;                 // blockmap origin (lower left)
   int nrows,ncols;               // blockmap dimensions
   linelist_t **blocklists=NULL;  // array of pointers to lists of lines
   int *blockcount=NULL;          // array of counters of line lists
   int *blockdone=NULL;           // array keeping track of blocks/line
   int NBlocks;                   // number of cells = nrows*ncols
   long linetotal=0;              // total length of all blocklists
   int i,j;
   int map_minx=INT_MAX;          // init for map limits search
   int map_miny=INT_MAX;
   int map_maxx=INT_MIN;
   int map_maxy=INT_MIN;

   // scan for map limits, which the blockmap must enclose

   for (i=0;i<numvertexes;i++)
   {
      fixed_t t;

      if ((t=vertexes[i].x) < map_minx)
         map_minx = t;
      else if (t > map_maxx)
         map_maxx = t;
      if ((t=vertexes[i].y) < map_miny)
         map_miny = t;
      else if (t > map_maxy)
         map_maxy = t;
   }
   map_minx >>= FRACBITS;    // work in map coords, not fixed_t
   map_maxx >>= FRACBITS;
   map_miny >>= FRACBITS;
   map_maxy >>= FRACBITS;

   // set up blockmap area to enclose level plus margin

   xorg = map_minx-blkmargin;
   yorg = map_miny-blkmargin;
   ncols = (map_maxx+blkmargin-xorg+1+blkmask)>>blkshift;  //jff 10/12/98
   nrows = (map_maxy+blkmargin-yorg+1+blkmask)>>blkshift;  //+1 needed for
   NBlocks = ncols*nrows;                                  //map exactly 1 cell

   // create the array of pointers on NBlocks to blocklists
   // also create an array of linelist counts on NBlocks
   // finally make an array in which we can mark blocks done per line

   // CPhipps - calloc's
   blocklists = calloc(NBlocks,sizeof(linelist_t *));
   blockcount = calloc(NBlocks,sizeof(int));
   blockdone = malloc(NBlocks*sizeof(int));

   // initialize each blocklist, and enter the trailing -1 in all blocklists
   // note the linked list of lines grows backwards

   for (i=0;i<NBlocks;i++)
   {
      blocklists[i] = malloc(sizeof(linelist_t));
      blocklists[i]->num = -1;
      blocklists[i]->next = NULL;
      blockcount[i]++;
   }

   // For each linedef in the wad, determine all blockmap blocks it touches,
   // and add the linedef number to the blocklists for those blocks

   for (i=0;i<numlines;i++)
   {
      int x1 = lines[i].v1->x>>FRACBITS;         // lines[i] map coords
      int y1 = lines[i].v1->y>>FRACBITS;
      int x2 = lines[i].v2->x>>FRACBITS;
      int y2 = lines[i].v2->y>>FRACBITS;
      int dx = x2-x1;
      int dy = y2-y1;
      int vert = !dx;                            // lines[i] slopetype
      int horiz = !dy;
      int spos = (dx^dy) > 0;
      int sneg = (dx^dy) < 0;
      int bx,by;                                 // block cell coords
      int minx = x1>x2? x2 : x1;                 // extremal lines[i] coords
      int maxx = x1>x2? x1 : x2;
      int miny = y1>y2? y2 : y1;
      int maxy = y1>y2? y1 : y2;

      // no blocks done for this linedef yet

      memset(blockdone,0,NBlocks*sizeof(int));

      // The line always belongs to the blocks containing its endpoints

      bx = (x1-xorg)>>blkshift;
      by = (y1-yorg)>>blkshift;
      AddBlockLine(blocklists,blockcount,blockdone,by*ncols+bx,i);
      bx = (x2-xorg)>>blkshift;
      by = (y2-yorg)>>blkshift;
      AddBlockLine(blocklists,blockcount,blockdone,by*ncols+bx,i);


      // For each column, see where the line along its left edge, which
      // it contains, intersects the Linedef i. Add i to each corresponding
      // blocklist.

      if (!vert)    // don't interesect vertical lines with columns
      {
         for (j=0;j<ncols;j++)
         {
            // intersection of Linedef with x=xorg+(j<<blkshift)
            // (y-y1)*dx = dy*(x-x1)
            // y = dy*(x-x1)+y1*dx;

            int x = xorg+(j<<blkshift);       // (x,y) is intersection
            int y = (dy*(x-x1))/dx+y1;
            int yb = (y-yorg)>>blkshift;      // block row number
            int yp = (y-yorg)&blkmask;        // y position within block

            if (yb<0 || yb>nrows-1)     // outside blockmap, continue
               continue;

            if (x<minx || x>maxx)       // line doesn't touch column
               continue;

            // The cell that contains the intersection point is always added

            AddBlockLine(blocklists,blockcount,blockdone,ncols*yb+j,i);

            // if the intersection is at a corner it depends on the slope
            // (and whether the line extends past the intersection) which
            // blocks are hit

            if (yp==0)        // intersection at a corner
            {
               if (sneg)       //   \ - blocks x,y-, x-,y
               {
                  if (yb>0 && miny<y)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*(yb-1)+j,i);
                  if (j>0 && minx<x)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*yb+j-1,i);
               }
               else if (spos)  //   / - block x-,y-
               {
                  if (yb>0 && j>0 && minx<x)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*(yb-1)+j-1,i);
               }
               else if (horiz) //   - - block x-,y
               {
                  if (j>0 && minx<x)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*yb+j-1,i);
               }
            }
            else if (j>0 && minx<x) // else not at corner: x-,y
               AddBlockLine(blocklists,blockcount,blockdone,ncols*yb+j-1,i);
         }
      }

      // For each row, see where the line along its bottom edge, which
      // it contains, intersects the Linedef i. Add i to all the corresponding
      // blocklists.

      if (!horiz)
      {
         for (j=0;j<nrows;j++)
         {
            // intersection of Linedef with y=yorg+(j<<blkshift)
            // (x,y) on Linedef i satisfies: (y-y1)*dx = dy*(x-x1)
            // x = dx*(y-y1)/dy+x1;

            int y = yorg+(j<<blkshift);       // (x,y) is intersection
            int x = (dx*(y-y1))/dy+x1;
            int xb = (x-xorg)>>blkshift;      // block column number
            int xp = (x-xorg)&blkmask;        // x position within block

            if (xb<0 || xb>ncols-1)   // outside blockmap, continue
               continue;

            if (y<miny || y>maxy)     // line doesn't touch row
               continue;

            // The cell that contains the intersection point is always added

            AddBlockLine(blocklists,blockcount,blockdone,ncols*j+xb,i);

            // if the intersection is at a corner it depends on the slope
            // (and whether the line extends past the intersection) which
            // blocks are hit

            if (xp==0)        // intersection at a corner
            {
               if (sneg)       //   \ - blocks x,y-, x-,y
               {
                  if (j>0 && miny<y)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*(j-1)+xb,i);
                  if (xb>0 && minx<x)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*j+xb-1,i);
               }
               else if (vert)  //   | - block x,y-
               {
                  if (j>0 && miny<y)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*(j-1)+xb,i);
               }
               else if (spos)  //   / - block x-,y-
               {
                  if (xb>0 && j>0 && miny<y)
                     AddBlockLine(blocklists,blockcount,blockdone,ncols*(j-1)+xb-1,i);
               }
            }
            else if (j>0 && miny<y) // else not on a corner: x,y-
               AddBlockLine(blocklists,blockcount,blockdone,ncols*(j-1)+xb,i);
         }
      }
   }

   // Add initial 0 to all blocklists
   // count the total number of lines (and 0's and -1's)

   memset(blockdone,0,NBlocks*sizeof(int));
   for (i=0,linetotal=0;i<NBlocks;i++)
   {
      AddBlockLine(blocklists,blockcount,blockdone,i,0);
      linetotal += blockcount[i];
   }

   // Create the blockmap lump

   blockmaplump = Z_Malloc(sizeof(*blockmaplump) * (4+NBlocks+linetotal),
                           PU_LEVEL, 0);
   // blockmap header

   blockmaplump[0] = bmaporgx = xorg << FRACBITS;
   blockmaplump[1] = bmaporgy = yorg << FRACBITS;
   blockmaplump[2] = bmapwidth  = ncols;
   blockmaplump[3] = bmapheight = nrows;

   // offsets to lists and block lists

   for (i=0;i<NBlocks;i++)
   {
      linelist_t *bl = blocklists[i];
      long offs = blockmaplump[4+i] =   // set offset to block's list
                     (i? blockmaplump[4+i-1] : 4+NBlocks) + (i? blockcount[i-1] : 0);

      // add the lines in each block's list to the blockmaplump
      // delete each list node as we go

      while (bl)
      {
         linelist_t *tmp = bl->next;
         blockmaplump[offs++] = bl->num;
         free(bl);
         bl = tmp;
      }
   }

   // free all temporary storage

   free (blocklists);
   free (blockcount);
   free (blockdone);
}

// jff 10/6/98
// End new code added to speed up calculation of internal blockmap

//
// P_LoadBlockMap
//
// killough 3/1/98: substantially modified to work
// towards removing blockmap limit (a wad limitation)
//
// killough 3/30/98: Rewritten to remove blockmap limit,
// though current algorithm is brute-force and unoptimal.
//

static void P_LoadBlockMap (int lump)
{
   long count;

   if (M_CheckParm("-blockmap") || (count = W_LumpLength(lump)/2) >= 0x10000)
      P_CreateBlockMap();
   else
   {
      long i;
      // cph - const*, wad lump handling updated
      const short *wadblockmaplump = W_CacheLumpNum(lump);
      blockmaplump = Z_Malloc(sizeof(*blockmaplump) * count, PU_LEVEL, 0);

      // killough 3/1/98: Expand wad blockmap into larger internal one,
      // by treating all offsets except -1 as unsigned and zero-extending
      // them. This potentially doubles the size of blockmaps allowed,
      // because Doom originally considered the offsets as always signed.

      blockmaplump[0] = SHORT(wadblockmaplump[0]);
      blockmaplump[1] = SHORT(wadblockmaplump[1]);
      blockmaplump[2] = (long)(SHORT(wadblockmaplump[2])) & 0xffff;
      blockmaplump[3] = (long)(SHORT(wadblockmaplump[3])) & 0xffff;

      for (i=4 ; i<count ; i++)
      {
         short t = SHORT(wadblockmaplump[i]);          // killough 3/1/98
         blockmaplump[i] = t == -1 ? -1l : (long) t & 0xffff;
      }

      W_UnlockLumpNum(lump); // cph - unlock the lump

      bmaporgx = blockmaplump[0]<<FRACBITS;
      bmaporgy = blockmaplump[1]<<FRACBITS;
      bmapwidth = blockmaplump[2];
      bmapheight = blockmaplump[3];
   }