/*----------------------------------------------------------------------------*
 | This file is part of DEU (Doom Editing Utilities), created by the DEU team:|
 | Raphael Quinet, Brendon Wyber, Ted Vessenes and others.  See README.1ST or |
 | the "about" dialog box for full credits.                                   |
 |                                                                            |
 | DEU is an open project: if you think that you can contribute, please join  |
 | the DEU team.  You will be credited for any code (or ideas) included in    |
 | the next version of the program.                                           |
 |                                                                            |
 | If you want to make any modifications and re-distribute them on your own,  |
 | you must follow the conditions of the DEU license.  Read the file LICENSE  |
 | in this directory or README.1ST in the top directory.  If do not have a    |
 | copy of these files, you can request them from any member of the DEU team, |
 | or by mail: Raphael Quinet, Rue des Martyrs 9, B-4550 Nandrin (Belgium).   |
 |                                                                            |
 | This program comes with absolutely no warranty.  Use it at your own risks! |
 *----------------------------------------------------------------------------*

 B_REJECT.C - Reject builder

 Created on Jun 9 1994 by Johannes Plass
 Converted to DEU 5.3 style on Jan 24 1995 by Renaud Paquay

*/

#include <math.h>
#include "deu.h"
#include "d_misc.h"     /* GetMemory(), ... */
#include "d_config.h"   /* Config */
#include "w_levels.h"   /* LevelInfo */
#include "b_reject.h"   /* CreateRejectData() */

/*! Should not be included... */
#include "g_gfx.h"      /* ScrMaxX, ScrMaxY */
#include "g_mouse.h"    /* UseMouse, HideMousePointer(), ShowMousePointer */

/*!RP Possible values for T_REJ_STATE are:
      1 means fake reject data with '0x00's (all bits = 0)
      2 means fake reject data with '0xFF's (all bits = 1)
      Other: means build valid reject data */
/* Int16 T_FREJ_STATE; */
/*!RP Finaly, this var is a 'Config' field called RejectOption */


/*
   Macros
*/

/*RP Apr 15 1995: removed! */
/*
static struct LevelInfo loc_level;

#define VSX(lll)  (loc_level.vertexes[loc_level.linedefs[lll].start].x)
#define VSY(lll)  (loc_level.vertexes[loc_level.linedefs[lll].start].y)
#define VEX(lll)  (loc_level.vertexes[loc_level.linedefs[lll].end].x)
#define VEY(lll)  (loc_level.vertexes[loc_level.linedefs[lll].end].y)
#define VX(vvv)   loc_level.vertexes[vvv].x
#define VY(vvv)   loc_level.vertexes[vvv].y
#define NUM_SECTORS     loc_level.num_sectors
#define NUM_LINES       loc_level.num_linedefs
*/
#define FLAG_TWOSIDED   4

/*
   Declarations
*/

typedef struct
{
  Int16 x, y;
} bpoint_t;

typedef struct
{
  Int16 xl, xh, yl, yh;
} bbox_t;

typedef struct
{
  bpoint_t p1, p2;
} bline_t;

typedef struct
{
  UInt16      numpoints;
  bbox_t      bounds;
  bpoint_t   *points;
} bchain_t;

typedef struct
{
  Int16      x,  y;
  Int16      dx, dy;
} bdivline_t;

typedef struct
{
  Int16   count;
  Int16   size;
  void *data;
} STORAGE;


/*
   Global Variables
*/

static Int8      *connections;
static bline_t   *blines;
static bbox_t    *secboxes;
static bchain_t  *bchains;
static Int16      numsectors;
static Int16      numblines;
static Int16      numbchains;
static STORAGE   *chains_i;
static STORAGE   *lines;


/*! description missing */
void ClearBBox (bbox_t *box)
{
  box->xl = box->yl =  32767;
  box->xh = box->yh = -32767;
}


/*! description missing */
void AddToBBox (bbox_t *box, Int16 x, Int16 y)
{
  if (x < box->xl) box->xl = x;
  if (x > box->xh) box->xh = x;
  if (y < box->yl) box->yl = y;
  if (y > box->yh) box->yh = y;
}


/*! description missing */
/* Returns side 0 (front), 1 (back), or -1 (colinear) */
Int16 BPointOnSide (bpoint_t *pt, bdivline_t *l)
{
  Int16      dx,   dy;
  Int16      left, right;

  if (!l->dx)
    {
      if (pt->x < l->x) return (l->dy>0);
                        return (l->dy<0);
    }
  if (!l->dy)
    {
      if (pt->y < l->y) return (l->dx<0);
                        return (l->dx>0);
    }

  dx = pt->x - l->x;
  dy = pt->y - l->y;

  left  = l->dy * dx;
  right = dy * l->dx;

  if (right < left) return 0;      /* front side */
                    return 1;      /* back side */
}


/*!RP made them static */
static bdivline_t  ends[2], sides[2];
static Int16       end0out, end1out, side0out, side1out;
static bbox_t      sweptarea;

/*! description missing */
Bool DoesChainBlock (bchain_t *chain)
{
  bpoint_t     *pt;
  Int16         side, startside;
  Int16         p;
  /* if a solid line can be walked from one side to the other without going out
     an end, the path is blocked */

  /* don't check if bounds don't intersect */
  if (sweptarea.xl > chain->bounds.xh  || sweptarea.xh < chain->bounds. xl
      || sweptarea.yl > chain->bounds. yh || sweptarea.yh < chain->bounds. yl)
    return FALSE;

  startside = -1;      /* not started yet */

  for (p = 0, pt = chain->points; p < chain->numpoints; p++, pt++)
    {
      /* find side for pt */

      if (BPointOnSide (pt, &ends[0]) == end0out)
        {
          startside = -1;   /* off end */
          continue;
        }
      if (BPointOnSide (pt, &ends[1]) == end1out)
        {
          startside = -1;   /* off end */
          continue;
        }
      if (BPointOnSide (pt, &sides[0]) == side0out)
        side = 0;
      else if (BPointOnSide (pt, &sides[1]) == side1out)
        side = 1;
      else
        continue; /* in middle */

      /* point is on one side or the other */
      if (startside == -1 || startside == side)
        {
          startside = side;
          continue;
        }

      /* opposite of startside */
      return TRUE;      /* totally crossed area */
    }
  return FALSE;
}


/*! description missing */
enum {si_north, si_east, si_south, si_west};

/*! description missing */
void BuildConnections (LevelPtr level)
{
  Int16     blockcount, passcount;
  Int16     i,j, k, s, bn;
  Int16     x = 0, y = 0;
  bbox_t   *bbox[2];
  Int16     walls[4];
  bpoint_t  points[2][2];

  /* look for obscured sectors */
  blockcount = passcount = 0;
  bbox[0] = secboxes;
  for (i = 0; i < level->num_sectors - 1; i++, bbox[0]++)
    {
      if (UseMouse)
        HideMousePointer();
      DrawScreenMeter(225, 108, ScrMaxX - 10, 128, (float)i / (float)level->num_sectors);
      if (UseMouse)
        ShowMousePointer();

      bbox[1] = bbox[0] + 1;
      if (bbox[0]->xh - bbox[0]->xl < 64 || bbox[0]->yh - bbox[0]->yl < 64)
        continue; /* ignore small sectors */

      for (j = i + 1; j < level->num_sectors; j++, bbox[1]++)
        {
          if (bbox[1]->xh - bbox[1]->xl < 64 || bbox[1]->yh - bbox[1]->yl < 64)
            continue; /* ignore small sectors */

          if (bbox[1]->xl <= bbox[0]->xh && bbox[1]->xh >= bbox[0]->xl &&
              bbox[1]->yl <= bbox[0]->yh && bbox[1]->yh >= bbox[0]->yl)
            {
              passcount++;
              continue;      /* touching sectors are never blocked */
            }

          sweptarea.xl = bbox[0]->xl < bbox[1]->xl ? bbox[0]->xl : bbox[1]->xl;
          sweptarea.xh = bbox[0]->xh > bbox[1]->xh ? bbox[0]->xh : bbox[1]->xh;
          sweptarea.yl = bbox[0]->yl < bbox[1]->yl ? bbox[0]->yl : bbox[1]->yl;
          sweptarea.yh = bbox[0]->yh > bbox[1]->yh ? bbox[0]->yh : bbox[1]->yh;

          /* calculate the swept area between the sectors */
          for (bn = 0; bn < 2; bn++)
            {
              memset (walls, 0, sizeof(walls));
              if (bbox[bn]->xl <= bbox[!bn]->xl) walls[si_west]  = 1;
              if (bbox[bn]->xh >= bbox[!bn]->xh) walls[si_east]  = 1;
              if (bbox[bn]->yl <= bbox[!bn]->yl) walls[si_south] = 1;
              if (bbox[bn]->yh >= bbox[!bn]->yh) walls[si_north] = 1;

              for (s = 0; s < 5; s++)
                {
                  switch (s & 3)
                    {
                    case si_north:
                      x = bbox[bn]->xl;
                      y = bbox[bn]->yh;
                      break;
                    case si_east:
                      x = bbox[bn]->xh;
                      y = bbox[bn]->yh;
                      break;
                    case si_south:
                      x = bbox[bn]->xh;
                      y = bbox[bn]->yl;
                        break;
                    case si_west:
                      x = bbox[bn]->xl;
                      y = bbox[bn]->yl;
                      break;
                    }
                  if (! walls[(s - 1) & 3] && walls[s & 3])
                    {
                      points[bn][0].x = x;
                      points[bn][0].y = y;
                    }
                  if (walls[(s - 1) & 3] && ! walls[s & 3])
                    {
                      points[bn][1].x = x;
                      points[bn][1].y = y;
                    }
                }

              ends[bn].x  = points[bn][0].x;
              ends[bn].y  = points[bn][0].y;
              ends[bn].dx = points[bn][1].x - points[bn][0].x;
              ends[bn].dy = points[bn][1].y - points[bn][0].y;
            }

          sides[0].x  = points[0][0].x;
          sides[0].y  = points[0][0].y;
          sides[0].dx = points[1][1].x - points[0][0].x;
          sides[0].dy = points[1][1].y - points[0][0].y;

          sides[1].x  = points[0][1].x;
          sides[1].y  = points[0][1].y;
          sides[1].dx = points[1][0].x - points[0][1].x;
          sides[1].dy = points[1][0].y - points[0][1].y;

          end0out  = ! BPointOnSide (&points[1][0], &ends[0]);
          end1out  = ! BPointOnSide (&points[0][0], &ends[1]);
          side0out = ! BPointOnSide (&points[0][1], &sides[0]);
          side1out = ! BPointOnSide (&points[0][0], &sides[1]);

          /* look for a line change that covers the swept area */
          for (k = 0; k < numbchains; k++)
            {
              if (!DoesChainBlock (&bchains[k]))
                continue;
              blockcount++;
              connections[(size_t)(i * numsectors + j)] =
                connections[(size_t)(j * numsectors + i)] = 1;
              goto blocked;
            }

          /* nothing definately blocked the path */
          passcount++;
blocked: ;
        } /* End for(j) */
    } /* End for (i) */
}

/*! description missing */
static bpoint_t** bchPtr;

/*! description missing */
void BuildBlockingChains(void)
{
  Bool         *used;
  Int16         i, j;
  bpoint_t     *temppoints, *pt_p;
  bline_t      *li1, *li2;
  bchain_t      bch;
  Int16         cx, cy;

  bchPtr = (bpoint_t **)GetMemory(numblines * sizeof(*bchPtr));
  memset(bchPtr, 0, numblines * sizeof(*bchPtr));

  used = (Bool *)GetMemory(numblines * sizeof (*used));
  memset (used, 0, numblines * sizeof (*used));

  temppoints = (bpoint_t *)GetMemory(numblines * sizeof (*temppoints));

  chains_i = (STORAGE *)GetMemory(sizeof(STORAGE));
  chains_i->data  = (bchain_t *)GetMemory(sizeof(bchain_t));
  chains_i->count = 0;
  chains_i->size  = sizeof(bchain_t);

  li1 = blines;
  for (i = 0; i < numblines; i++, li1++)
    {
      if (used[i]) continue;
      used[i] = TRUE;

      /* start a new chain */
      pt_p = temppoints;
      pt_p->x = li1->p1.x;
      pt_p->y = li1->p1.y;
      pt_p++;
      pt_p->x = cx = li1->p2.x;
      pt_p->y = cy = li1->p2.y;
      pt_p++;

      ClearBBox (&bch.bounds);
      AddToBBox (&bch.bounds, li1->p1.x, li1->p1.y);
      AddToBBox (&bch.bounds, cx, cy);

      /* look for connected lines */
      for (;;)
        {
          li2 = li1 + 1;
          for (j = i  + 1; j < numblines; j++, li2++)
            if (!used[j] && li2->p1.x == cx && li2->p1.y == cy)
              break;

          if (j == numblines)
            break; /* no more lines in chain */

          /* add to chain */
          used[j] = TRUE;
          pt_p->x = cx = li2->p2.x;
          pt_p->y = cy = li2->p2.y;
          pt_p++;
          AddToBBox (&bch.bounds, cx, cy);
        }

      /* save the block chain */
      bch.numpoints =(UInt16)(pt_p - temppoints);
      bch.points = bchPtr[i] = (bpoint_t *)GetMemory(bch.numpoints * sizeof(*bch.points));
      memcpy (bch.points, temppoints, bch.numpoints * sizeof(*bch.points));

      memcpy((bchain_t *) chains_i->data+chains_i->count, &bch, sizeof(bchain_t));
      chains_i->count += 1;
      chains_i->data  = (bchain_t *)ResizeMemory(chains_i->data, sizeof(bchain_t) * (chains_i->count + 1));
    }
  numbchains = chains_i->count;
  bchains = (bchain_t *)chains_i->data;
}


/*! description missing */
void ProcessConnections (LevelPtr level)
{
  Int16      i, count;
  bbox_t    *secbox;
  bline_t    bline;
  Int16      sec;
  Int16      RonsLines = 0;

  numsectors = level->num_sectors;
  count      = level->num_linedefs;

  /* +8 : allow rounding to bytes */
  connections = (Int8 *) GetMemory((size_t)(numsectors * numsectors + 8));
  memset (connections, 0, (size_t)(numsectors * numsectors));

  secboxes = secbox = (bbox_t *) GetMemory(numsectors * sizeof(bbox_t));
  for (i = 0; i < numsectors; i++, secbox++)
    ClearBBox (secbox);

  for (i = 0; i < count; i++)
    {
      LDPtr pld = &level->linedefs[i];
      VPtr  vs  = &level->vertexes[pld->start];
      VPtr  ve  = &level->vertexes[pld->end];

      if (pld->sidedef1 != -1)
        {
          sec = level->sidedefs[pld->sidedef1].sector;
          AddToBBox (&secboxes[sec], vs->x, vs->y);
          AddToBBox (&secboxes[sec], ve->x, ve->y);
        }
    }

  /* make a list of only the solid lines */
  for (i=0; i<count; i++)
    {
      if (level->linedefs[i].flags & FLAG_TWOSIDED)
        continue;
      RonsLines++;
    }

  lines = (STORAGE *) GetMemory(sizeof(STORAGE));
  lines->data  = (bline_t *) GetMemory(RonsLines * sizeof(bline));
  lines->count = 0;
  lines->size  = sizeof(bline);

  for (i = 0; i < count; i++)
    {
      LDPtr pld = &level->linedefs[i];
      VPtr  vs  = &level->vertexes[pld->start];
      VPtr  ve  = &level->vertexes[pld->end];

      if (pld->flags  & FLAG_TWOSIDED)
        continue; /* don't add two sided lines */
      bline.p1.x = vs->x;
      bline.p1.y = vs->y;
      bline.p2.x = ve->x;
      bline.p2.y = ve->y;
      memcpy((bline_t *) lines->data+lines->count, &bline, sizeof(bline));
      lines->count += 1;
    }

  blines = (bline_t *)lines->data;
  numblines = lines->count;

  BuildBlockingChains();
  BuildConnections(level);
}


/*! description missing */
void *OutputConnections(void)
{
  size_t  i;
  size_t  bytes;
  Int8   *cons;
  Int8   *bits;
  Int16   n;

  cons = connections;
  bytes = (numsectors * numsectors + 7) / 8;
  bits = (Int8 *) GetMemory(bytes);

  for (i = 0; i < bytes; i++)
    {
      bits[i] = cons[0] + (cons[1] << 1) + (cons[2] << 2) + (cons[3] << 3)
                        + (cons[4] << 4) + (cons[5] << 5) + (cons[6] << 6)
                        + (cons[7] << 7);
      cons += 8;
   }

  /*! RP There were FreeFarMemory for memory allocated with SafeMalloc
         I replaced SafeMalloc by GetMemory and so FreeFarMemory
         by FreeMemory. Maybe we should use GetFar/FreeFar instead ? */
  FreeMemory((void*) connections);
  FreeMemory((void*) secboxes);
  FreeMemory((void*) blines);
  FreeMemory((void*) bchains);
  for (n = 0; n < numblines; n++)
    if (bchPtr[n])
      FreeMemory((void*) bchPtr[n]);
  FreeMemory((void*) bchPtr);
  FreeMemory((void*) chains_i);
  FreeMemory((void*) lines);

  return (void *)bits;
}


/*! description missing */
void *CreateRejectData(LevelPtr level, UInt32 *rejectsize)
{
  void *rejectdata;

  /*RP Copy level info to global static var */
  /*RP removed! */
  /* memcpy(&loc_level, level, sizeof(struct LevelInfo)); */

  /* Size of reject data */
  *rejectsize = (level->num_sectors * level->num_sectors + 7) / 8;

  if (Config.RejectOption == REJECT_FAKE)
    {        /* build fake reject table */
      rejectdata = GetMemory((size_t) *rejectsize);
      memset((void *) rejectdata, 0x00, (size_t) *rejectsize);
    }
  else if (Config.RejectOption == REJECT_PEACEFUL)
    {
      rejectdata = GetMemory((size_t) *rejectsize);
      memset((void *) rejectdata, ~((size_t) 0), (size_t) *rejectsize);
    }
  else
    {      /* build 'valid' reject table */
      ProcessConnections(level);
      rejectdata = OutputConnections();
    }
  return rejectdata;
}

/* end of file */