fixed_t FixedHypot(fixed_t x, fixed_t y)
{
#ifdef HAVE_HYPOT
	const float fx = FIXED_TO_FLOAT(x);
	const float fy = FIXED_TO_FLOAT(y);
	float fz;
#ifdef HAVE_HYPOTF
	fz = hypotf(fx, fy);
#else
	fz = (float)hypot(fx, fy);
#endif
	return FLOAT_TO_FIXED(fz);
#else // !HAVE_HYPOT
	fixed_t ax, yx, yx2, yx1;
	if (abs(y) > abs(x)) // |y|>|x|
	{
		ax = abs(y); // |y| => ax
		yx = FixedDiv(x, y); // (x/y)
	}
	else // |x|>|y|
	{
		ax = abs(x); // |x| => ax
		yx = FixedDiv(y, x); // (x/y)
	}
	yx2 = FixedMul(yx, yx); // (x/y)^2
	yx1 = FixedSqrt(1+FRACUNIT + yx2); // (1 + (x/y)^2)^1/2
	return FixedMul(ax, yx1); // |x|*((1 + (x/y)^2)^1/2)
#endif
}

/*
void AM_addMark(void)
{
  markpoints[markpointnum].x = m_x + m_w/2;
  markpoints[markpointnum].y = m_y + m_h/2;
  markpointnum = (markpointnum + 1) % AM_NUMMARKPOINTS;

}
*/
void AM_findMinMaxBoundaries(void)
{
    int i;
    fixed_t a, b;

    min_x = min_y = INT_MAX;
    max_x = max_y = -INT_MAX;
    for (i = 0; i < numvertexes; i++)
    {
        if (vertexes[i].x < min_x)
            min_x = vertexes[i].x;
        else if (vertexes[i].x > max_x)
            max_x = vertexes[i].x;
        if (vertexes[i].y < min_y)
            min_y = vertexes[i].y;
        else if (vertexes[i].y > max_y)
            max_y = vertexes[i].y;
    }
    max_w = max_x - min_x;
    max_h = max_y - min_y;
    min_w = 2 * PLAYERRADIUS;
    min_h = 2 * PLAYERRADIUS;

    a = FixedDiv(f_w << FRACBITS, max_w);
    b = FixedDiv(f_h << FRACBITS, max_h);
    min_scale_mtof = a < b ? a : b;

    max_scale_mtof = FixedDiv(f_h << FRACBITS, 2 * PLAYERRADIUS);

}

vector_t *FV_DivideEx(const vector_t *a_i, fixed_t a_c, vector_t *a_o)
{
	a_o->x = FixedDiv(a_i->x, a_c);
	a_o->y = FixedDiv(a_i->y, a_c);
	a_o->z = FixedDiv(a_i->z, a_c);
	return a_o;
}

int EV_BuildPillar(line_t *line, byte *args, boolean crush)
{
	int secnum;
	sector_t *sec;
	pillar_t *pillar;
	int newHeight;
	int rtn;

	rtn = 0;
	secnum = -1;
	while((secnum = P_FindSectorFromTag(args[0], secnum)) >= 0)
	{
		sec = &sectors[secnum];
		if(sec->specialdata)
			continue; // already moving
		if(sec->floorheight == sec->ceilingheight)
		{ // pillar is already closed
			continue;
		}
		rtn = 1;
		if(!args[2])
		{
			newHeight = sec->floorheight+
				((sec->ceilingheight-sec->floorheight)/2);
		}
		else
		{
			newHeight = sec->floorheight+(args[2]<<FRACBITS);
		}

		pillar = Z_Malloc(sizeof(*pillar), PU_LEVSPEC, 0);
		sec->specialdata = pillar;
		P_AddThinker(&pillar->thinker);
		pillar->thinker.function = T_BuildPillar;
		pillar->sector = sec;
		if(!args[2])
		{
			pillar->ceilingSpeed = pillar->floorSpeed = args[1]*(FRACUNIT/8);
		}
		else if(newHeight-sec->floorheight > sec->ceilingheight-newHeight)
		{
			pillar->floorSpeed = args[1]*(FRACUNIT/8);
			pillar->ceilingSpeed = FixedMul(sec->ceilingheight-newHeight,
				FixedDiv(pillar->floorSpeed, newHeight-sec->floorheight));
		}
		else
		{
			pillar->ceilingSpeed = args[1]*(FRACUNIT/8);
			pillar->floorSpeed = FixedMul(newHeight-sec->floorheight,
				FixedDiv(pillar->ceilingSpeed, sec->ceilingheight-newHeight));
		}
		pillar->floordest = newHeight;
		pillar->ceilingdest = newHeight;
		pillar->direction = 1;
		pillar->crush = crush*args[3];
		SN_StartSequence((mobj_t *)&pillar->sector->soundorg, 
			SEQ_PLATFORM+pillar->sector->seqType);
	}
	return rtn;
}

void R_InitSkyMap ()
{
	if (textureheight == NULL)
		return;

	if (textureheight[skytexture] <= (128 << FRACBITS))
	{
                skytexturemid = 100*FRACUNIT;
                skystretch = (r_stretchsky && allowfreelook);
	}
	else
	{
		skytexturemid = 100*FRACUNIT;
		skystretch = 0;
	}
	skyheight = textureheight[skytexture] << skystretch;

	if (viewwidth && viewheight)
	{
		skyiscale = (200*FRACUNIT) / (((freelookviewheight<<detailxshift) * viewwidth) / (viewwidth<<detailxshift));
		skyscale = ((((freelookviewheight<<detailxshift) * viewwidth) / (viewwidth<<detailxshift)) << FRACBITS) /(200);

		skyiscale = FixedMul (skyiscale, FixedDiv (clipangle, ANG45));
		skyscale = FixedMul (skyscale, FixedDiv (ANG45, clipangle));
	}

	// The sky map is 256*128*4 maps.
	skyshift = 22+skystretch-16;
	if (texturewidthmask[skytexture] >= 256*2-1)
		skyshift -= skystretch;
}

void R_ClearPlanes(void)
{
    int i;
    angle_t angle;

//
// opening / clipping determination
//      
    for (i = 0; i < viewwidth; i++)
    {
        floorclip[i] = viewheight;
        ceilingclip[i] = -1;
    }

    lastvisplane = visplanes;
    lastopening = openings;

//
// texture calculation
//
    memset(cachedheight, 0, sizeof(cachedheight));
    angle = (viewangle - ANG90) >> ANGLETOFINESHIFT;    // left to right mapping

    // scale will be unit scale at SCREENWIDTH/2 distance
    basexscale = FixedDiv(finecosine[angle], centerxfrac);
    baseyscale = -FixedDiv(finesine[angle], centerxfrac);
}

void R_BlastSpriteColumn(void (*drawfunc)())
{
	tallpost_t* post = dcol.post;

	while (!post->end())
	{
		// calculate unclipped screen coordinates for post
		int topscreen = sprtopscreen + spryscale * post->topdelta + 1;

		dcol.yl = (topscreen + FRACUNIT) >> FRACBITS;
		dcol.yh = (topscreen + spryscale * post->length) >> FRACBITS;

		dcol.yl = MAX(dcol.yl, mceilingclip[dcol.x] + 1);
		dcol.yh = MIN(dcol.yh, mfloorclip[dcol.x] - 1);

		dcol.texturefrac = dcol.texturemid - (post->topdelta << FRACBITS)
			+ (dcol.yl * dcol.iscale) - FixedMul(centeryfrac - FRACUNIT, dcol.iscale);

		if (dcol.texturefrac < 0)
		{
			int cnt = (FixedDiv(-dcol.texturefrac, dcol.iscale) + FRACUNIT - 1) >> FRACBITS;
			dcol.yl += cnt;
			dcol.texturefrac += cnt * dcol.iscale;
		}

		const fixed_t endfrac = dcol.texturefrac + (dcol.yh - dcol.yl) * dcol.iscale;
		const fixed_t maxfrac = post->length << FRACBITS;
		
		if (endfrac >= maxfrac)
		{
			int cnt = (FixedDiv(endfrac - maxfrac - 1, dcol.iscale) + FRACUNIT - 1) >> FRACBITS;
			dcol.yh -= cnt;
		}

void Scene::showSprites() {
	// TODO: This is all experimental code, it needs heavy restructuring
	// and cleanup

	// taken from set_walker_scaling() in adv_walk.cpp. A proper implementation will need
	// to store these in global variables
	int minScaling = FixedDiv(_sceneResources->backScale << 16, 100 << 16);
	int maxScaling = FixedDiv(_sceneResources->frontScale << 16, 100 << 16);
	int scaler;

	_vm->_actor->setWalkerDirection(kFacingSouthEast);
	//_vm->_actor->setWalkerPalette();

	// taken from set_walker_scaling() in adv_walk.cpp
	if (_sceneResources->frontY == _sceneResources->backY)
		scaler = 0;
	else
		scaler = FixedDiv(maxScaling - minScaling,
				 (_sceneResources->frontY << 16) - (_sceneResources->backY << 16));

	// FIXME: For now, we (incorrectly) scale the walker to 50% of the scene's max scaling
	_vm->_actor->setWalkerScaling(scaler / 2);
	// Test code to display the protagonist
	_vm->_actor->placeWalkerSpriteAt(0, 320, 200);

	// Test code to display scene sprites
	// TODO
}

static void InitializeFade(boolean fadeIn)
{
	unsigned i;

	Palette = Z_Malloc(768*sizeof(fixed_t), PU_STATIC, 0);
	PaletteDelta = Z_Malloc(768*sizeof(fixed_t), PU_STATIC, 0);
	RealPalette = Z_Malloc(768*sizeof(byte), PU_STATIC, 0);

	if(fadeIn)
	{
		memset(RealPalette, 0, 768*sizeof(byte));
		for(i = 0; i < 768; i++)
		{
			Palette[i] = 0;
			PaletteDelta[i] = FixedDiv((*((byte *)W_CacheLumpName("playpal", 
				PU_CACHE)+i))<<FRACBITS, 70*FRACUNIT);
		}
	}
	else
	{
		for(i = 0; i < 768; i++)
		{
			RealPalette[i] = *((byte *)W_CacheLumpName("playpal", PU_CACHE)+i);
			Palette[i] = RealPalette[i]<<FRACBITS;
			PaletteDelta[i] = FixedDiv(Palette[i], -70*FRACUNIT);
		}
	}
	I_SetPalette(RealPalette);
}

// Also returns the magnitude
fixed_t FV_NormalizeEx(const vector_t *a_normal, vector_t *a_o)
{
	fixed_t magnitude = FV_Magnitude(a_normal);
	a_o->x = FixedDiv(a_normal->x, magnitude);
	a_o->y = FixedDiv(a_normal->y, magnitude);
	a_o->z = FixedDiv(a_normal->z, magnitude);
	return magnitude;
}

//
// PTR_chaseTraverse
//
// go til you hit a wall
// set the chasecam target x and ys if you hit one
// originally based on the shooting traverse function in p_maputl.c
//
static bool PTR_chaseTraverse(intercept_t *in)
{
   fixed_t dist, frac;
   subsector_t *ss;
   int x, y;
   int z;
   sector_t *othersector;

   if(in->isaline)
   {
      line_t *li = in->d.line;
      
      dist = FixedMul(trace.attackrange, in->frac);
      frac = in->frac - FixedDiv(12*FRACUNIT, trace.attackrange);
      
      // hit line
      // position a bit closer
      
      x = trace.dl.x + FixedMul(trace.dl.dx, frac);
      y = trace.dl.y + FixedMul(trace.dl.dy, frac);

      // ioanch 20160225: portal lines are currently not crossed
      if(li->flags & ML_TWOSIDED && !(li->pflags & PS_PASSABLE))
      {  // crosses a two sided line

         // sf: find which side it hit
         
         ss = R_PointInSubsector (x, y);
         
         othersector = li->backsector;
         
         if(ss->sector==li->backsector)      // other side
            othersector = li->frontsector;

         // interpolate, find z at the point of intersection
         
         z = zi(dist, trace.attackrange, targetz, playermobj->z+28*FRACUNIT);
         
         // found which side, check for intersections
         if((li->flags & ML_BLOCKING) || 
            (othersector->floorheight>z) || (othersector->ceilingheight<z)
            || (othersector->ceilingheight-othersector->floorheight
                < 40*FRACUNIT));          // hit
         else
         {
            return true;    // continue
         }
      }

      targetx = x;        // point the new chasecam target at the intersection
      targety = y;
      targetz = zi(dist, trace.attackrange, targetz, playermobj->z+28*FRACUNIT);
      
      // don't go any farther
      
      return false;
   }
   
   return true;
}

//
// PlaneIntersection
//
// Returns the distance from
// rOrigin to where the ray
// intersects the plane. Assumes
// you already know it intersects
// the plane.
//
fixed_t FV_PlaneIntersection(const vector_t *pOrigin, const vector_t *pNormal, const vector_t *rOrigin, const vector_t *rVector)
{
  fixed_t d = -(FV_Dot(pNormal, pOrigin));
  fixed_t number = FV_Dot(pNormal,rOrigin) + d;
  fixed_t denom = FV_Dot(pNormal,rVector);
  return -FixedDiv(number, denom);
}

void R_InitLightTables (void)
{
  int i;

  // killough 4/4/98: dynamic colormaps
  c_zlight = malloc(sizeof(*c_zlight) * numcolormaps);

  // Calculate the light levels to use
  //  for each level / distance combination.
  for (i=0; i< LIGHTLEVELS; i++)
    {
      int j, startmap = ((LIGHTLEVELS-1-i)*2)*NUMCOLORMAPS/LIGHTLEVELS;
      for (j=0; j<MAXLIGHTZ; j++)
        {
    // CPhipps - use 320 here instead of SCREENWIDTH, otherwise hires is
    //           brighter than normal res
          int scale = FixedDiv ((320/2*FRACUNIT), (j+1)<<LIGHTZSHIFT);
          int t, level = startmap - (scale >>= LIGHTSCALESHIFT)/DISTMAP;

          if (level < 0)
            level = 0;
          else
            if (level >= NUMCOLORMAPS)
              level = NUMCOLORMAPS-1;

          // killough 3/20/98: Initialize multiple colormaps
          level *= 256;
          for (t=0; t<numcolormaps; t++)         // killough 4/4/98
            c_zlight[t][i][j] = colormaps[t] + level;
        }
    }
}

void AM_LevelInit(void)
{
  leveljuststarted = 0;

  f_x = f_y = 0;
  f_w = finit_width;
  f_h = finit_height;
	mapxstart = mapystart = 0;


//  AM_clearMarks();

  AM_findMinMaxBoundaries();
  scale_mtof = FixedDiv(min_scale_mtof, (int) (0.7*FRACUNIT));
  if (scale_mtof > max_scale_mtof) scale_mtof = min_scale_mtof;
  scale_ftom = FixedDiv(FRACUNIT, scale_mtof);
}

//
// AM_getIslope()
//
// Calculates the slope and slope according to the x-axis of a line
// segment in map coordinates (with the upright y-axis n' all) so
// that it can be used with the brain-dead drawing stuff.
//
// Passed the line slope is desired for and an islope_t structure for return
// Returns nothing
//
void AM_getIslope
( mline_t*  ml,
  islope_t* is )
{
  int dx, dy;

  dy = ml->a.y - ml->b.y;
  dx = ml->b.x - ml->a.x;
  if (!dy)
    is->islp = (dx<0?-MAXINT:MAXINT);
  else
    is->islp = FixedDiv(dx, dy);
  if (!dx)
    is->slp = (dy<0?-MAXINT:MAXINT);
  else
    is->slp = FixedDiv(dy, dx);
}

//
// AM_LevelInit()
//
// Initialize the automap at the start of a new level
// should be called at the start of every level
//
// Passed nothing, returns nothing
// Affects automap's global variables
//
void AM_LevelInit(void)
{
  f_x = f_y = 0;

  // killough 2/7/98: get rid of finit_ vars
  // to allow runtime setting of width/height
  //
  // killough 11/98: ... finally add hires support :)

  f_w = (SCREENWIDTH) << hires;
  f_h = (SCREENHEIGHT-ST_HEIGHT) << hires;

  AM_findMinMaxBoundaries();
  scale_mtof = FixedDiv(min_scale_mtof, (int) (0.7*FRACUNIT));
  if (scale_mtof > max_scale_mtof)
    scale_mtof = min_scale_mtof;
  scale_ftom = FixedDiv(FRACUNIT, scale_mtof);
}

//
// R_CopySubimage
//
// Copies a portion of source_texture and draws it into dest_texture.
// The source subimage is scaled to fit the dimensions of the destination
// texture.
//
// Note: no clipping is performed so it is possible to read past the
// end of the source texture.
//
void R_CopySubimage(Texture* dest_texture, const Texture* source_texture,
	int dx1, int dy1, int dx2, int dy2,
	int sx1, int sy1, int sx2, int sy2)
{
	const int destwidth = dx2 - dx1 + 1; 
	const int destheight = dy2 - dy1 + 1;

	const int sourcewidth = sx2 - sx1 + 1;
	const int sourceheight = sy2 - sy1 + 1;

	const fixed_t xstep = FixedDiv(sourcewidth << FRACBITS, destwidth << FRACBITS) + 1;
	const fixed_t ystep = FixedDiv(sourceheight << FRACBITS, destheight << FRACBITS) + 1;

	int dest_offset = dx1 * dest_texture->getHeight() + dy1;
	byte* dest = dest_texture->getData() + dest_offset; 
	byte* dest_mask = dest_texture->getMaskData() + dest_offset; 

	fixed_t xfrac = 0;
	for (int xcount = destwidth; xcount > 0; xcount--)
	{
		int source_offset = (sx1 + (xfrac >> FRACBITS)) * source_texture->getHeight() + sy1;
		const byte* source = source_texture->getData() + source_offset;
		const byte* source_mask = source_texture->getMaskData() + source_offset;

		fixed_t yfrac = 0;
		for (int ycount = destheight; ycount > 0; ycount--)
		{
			*dest++ = source[yfrac >> FRACBITS];	
			*dest_mask++ = source_mask[yfrac >> FRACBITS];	
			yfrac += ystep;
		}

		dest += dest_texture->getHeight() - destheight;
		dest_mask += dest_texture->getHeight() - destheight; 

		xfrac += xstep;
	}

	// copy the source texture's offset info
	int xoffs = FixedDiv(source_texture->getOffsetX() << FRACBITS, xstep) >> FRACBITS;
	int yoffs = FixedDiv(source_texture->getOffsetY() << FRACBITS, ystep) >> FRACBITS;
	dest_texture->setOffsetX(xoffs);
	dest_texture->setOffsetY(yoffs);
}

static void R_InitTextureMapping (void)
{
  register int i,x;
  fixed_t focallength;

  // Use tangent table to generate viewangletox:
  //  viewangletox will give the next greatest x
  //  after the view angle.
  //
  // Calc focallength
  //  so FIELDOFVIEW angles covers SCREENWIDTH.

  focallength = FixedDiv(centerxfrac, finetangent[FINEANGLES/4+FIELDOFVIEW/2]);

  for (i=0 ; i<FINEANGLES/2 ; i++)
    {
      int t;
      if (finetangent[i] > FRACUNIT*2)
        t = -1;
      else
        if (finetangent[i] < -FRACUNIT*2)
          t = viewwidth+1;
      else
        {
          t = FixedMul(finetangent[i], focallength);
          t = (centerxfrac - t + FRACUNIT-1) >> FRACBITS;
          if (t < -1)
            t = -1;
          else
            if (t > viewwidth+1)
              t = viewwidth+1;
        }
      viewangletox[i] = t;
    }

  // Scan viewangletox[] to generate xtoviewangle[]:
  //  xtoviewangle will give the smallest view angle
  //  that maps to x.

  for (x=0; x<=viewwidth; x++)
    {
      for (i=0; viewangletox[i] > x; i++)
        ;
      xtoviewangle[x] = (i<<ANGLETOFINESHIFT)-ANG90;
    }

  // Take out the fencepost cases from viewangletox.
  for (i=0; i<FINEANGLES/2; i++)
    if (viewangletox[i] == -1)
      viewangletox[i] = 0;
    else
      if (viewangletox[i] == viewwidth+1)
        viewangletox[i] = viewwidth;

  clipangle = xtoviewangle[0];
}

function int sqrt(int number)
{
  if (number == 1.0) return 1.0;
  if (number <= 0) return 0;
  int val = 150.0;
  for (int i=0; i<15; i++)
    val = (val + FixedDiv(number, val)) >> 1;

  return val;
}

static fixed_t R_ScaleFromGlobalAngle(angle_t visangle)
{
  int     anglea = ANG90 + (visangle-viewangle);
  int     angleb = ANG90 + (visangle-rw_normalangle);
  int     den = FixedMul(rw_distance, finesine[anglea>>ANGLETOFINESHIFT]);
// proff 11/06/98: Changed for high-res
  fixed_t num = FixedMul(projectiony, finesine[angleb>>ANGLETOFINESHIFT]);
  return den > num>>16 ? (num = FixedDiv(num, den)) > 64*FRACUNIT ?
    64*FRACUNIT : num < 256 ? 256 : num : 64*FRACUNIT;
}