// region.h
#include "qbsp.h"

/*
 * 
 * input
 * -----
 * vertexes
 * edges
 * faces
 * 
 * output
 * ------
 * smaller set of vertexes
 * smaller set of edges
 * regions
 * ? triangulated regions
 * face to region mapping numbers
 * 
 */

typedef struct {
  int numedges;
  int edges[2];
} checkpoint_t;						// 12

int firstedge;						// 4

vec3_t region_mins, region_maxs;			// 24

/* changed by niels */
#ifdef EDGEMAPPING
int edgemapping[MAX_MAP_EDGES];				// 172032
#endif

checkpoint_t *checkpoints;

void AddPointToRegion(register vec3_t p)
{
  short int i;

  for (i = 0; i < 3; i++) {
    if (p[i] < region_mins[i])
      region_mins[i] = p[i];
    if (p[i] > region_maxs[i])
      region_maxs[i] = p[i];
  }
}

void ClearRegionSize(void)
{
  region_mins[0] = region_mins[1] = region_mins[2] = 9999;
  region_maxs[0] = region_maxs[1] = region_maxs[2] = -9999;
}

void AddFaceToRegionSize(register struct visfacet * f)
{
  int i;

  for (i = 0; i < f->numpoints; i++)
    AddPointToRegion(f->pts[i]);
}

/*
 * ==============
 * CanJoinFaces
 * ==============
 */
bool CanJoinFaces(__memBase, register struct visfacet * f, register struct visfacet * f2)
{
  vec3_t oldmins, oldmaxs;
  short int i;

  if (f2->planenum != f->planenum
      || f2->planeside != f->planeside
      || f2->texturenum != f->texturenum)
    return false;
  if (f2->outputnumber != -1)
    return false;
  if (f2->contents[0] != f->contents[0]) {				       // does this ever happen? theyy shouldn't share.

    eprintf("CanJoinFaces: edge with different contents");
    return false;
  }

// check size constraints
  if (!(bspMem->texinfo[f->texturenum].flags & TEX_SPECIAL)) {
    VectorCopy(region_mins, oldmins);
    VectorCopy(region_maxs, oldmaxs);
    AddFaceToRegionSize(f2);
    for (i = 0; i < 3; i++) {
      if (region_maxs[i] - region_mins[i] > 240) {
	VectorCopy(oldmins, region_mins);
	VectorCopy(oldmaxs, region_maxs);
	return false;
      }
    }
  }
  else {
    if (bspMem->numsurfedges - firstedge + f2->numpoints > MAX_EDGES_IN_REGION)
      return false;							       // a huge water or sky polygon

  }

// check edge count constraints
  return true;
}

/*
 * ==============
 * RecursiveGrowRegion
 * ==============
 */
void RecursiveGrowRegion(__memBase, register struct dface_t * r, register struct visfacet * f)
{
  int e;
  struct visfacet *f2;
  int i;

  if (f->outputnumber == bspMem->numfaces)
    return;

  if (f->outputnumber != -1)
    Error("RecursiveGrowRegion: region collision");
  f->outputnumber = bspMem->numfaces;

// add edges    
  for (i = 0; i < f->numpoints; i++) {
    e = f->edges[i];
/*  if (!edgefaces[abs(e)][0]) */
    if (!bspMem->edgefaces[0][abs(e)])
      continue;								       // edge has allready been removed

    if (e > 0)
/*    f2 = edgefaces[e][1]; */
      f2 = bspMem->edgefaces[1][e];
    else
/*    f2 = edgefaces[-e][0]; */
      f2 = bspMem->edgefaces[0][-e];
    if (f2 && f2->outputnumber == bspMem->numfaces) {
/*    edgefaces[abs(e)][0] = NULL; */
      bspMem->edgefaces[0][abs(e)] = NULL;
/*    edgefaces[abs(e)][1] = NULL; */
      bspMem->edgefaces[1][abs(e)] = NULL;
      continue;								       // allready merged

    }
    if (f2 && CanJoinFaces(bspMem, f, f2)) {					       // remove the edge and merge the faces

/*    edgefaces[abs(e)][0] = NULL; */
      bspMem->edgefaces[0][abs(e)] = NULL;
/*    edgefaces[abs(e)][1] = NULL; */
      bspMem->edgefaces[1][abs(e)] = NULL;
      RecursiveGrowRegion(bspMem, r, f2);
    }
    else {
      // emit a surfedge
      if (bspMem->numsurfedges == bspMem->max_numsurfedges)
        ExpandClusters(bspMem, LUMP_SURFEDGES);
      bspMem->dsurfedges[bspMem->numsurfedges] = e;
      bspMem->numsurfedges++;
    }
  }

}

#ifdef DEBUG
void PrintDface(register int f)
{									       // for debugging

  struct dface_t *df;
  struct dedge_t *e;
  int i, n;

  df = &bspMem->dfaces[f];
  for (i = 0; i < df->numedges; i++) {
    n = bspMem->dsurfedges[df->firstedge + i];
    e = &bspMem->dedges[abs(n)];
    if (n < 0)
      mprintf("%5i  =  %5i : %5i\n", n, e->v[1], e->v[0]);
    else
      mprintf("%5i  =  %5i : %5i\n", n, e->v[0], e->v[1]);
  }
}

void FindVertexUse(register int v)
{									       // for debugging

  int i, j, n;
  struct dface_t *df;
  struct dedge_t *e;

  for (i = firstmodelface; i < bspMem->numfaces; i++) {
    df = &bspMem->dfaces[i];
    for (j = 0; j < df->numedges; j++) {
      n = bspMem->dsurfedges[df->firstedge + j];
      e = &bspMem->dedges[abs(n)];
      if (e->v[0] == v || e->v[1] == v) {
	mprintf("on face %i\n", i);
	break;
      }
    }
  }
}

void FindEdgeUse(register int v)
{									       // for debugging

  int i, j, n;
  struct dface_t *df;

  for (i = firstmodelface; i < bspMem->numfaces; i++) {
    df = &bspMem->dfaces[i];
    for (j = 0; j < df->numedges; j++) {
      n = bspMem->dsurfedges[df->firstedge + j];
      if (n == v || -n == v) {
	mprintf("on face %i\n", i);
	break;
      }
    }
  }
}
#endif

/*
 * ================
 * HealEdges
 * 
 * Extends e1 so that it goes all the way to e2, and removes all references
 * to e2
 * ================
 */
void HealEdges(register int e1, int register e2)
{
  int i, j, n, saved;
  struct dface_t *df;
  struct dedge_t *ed, *ed2;
  vec3_t v1, v2;
  struct dface_t *found[2];
  int foundj[2];

  /*
   * FIX!!! why this? niels
   */
/* changed by niels */
#ifdef EDGEMAPPING
  e1 = edgemapping[e1];
  e2 = edgemapping[e2];

// extend e1 to e2
  ed = &bspMem->dedges[e1];
  ed2 = &bspMem->dedges[e2];
  VectorSubtract(bspMem->dvertexes[ed->v[1]].point, bspMem->dvertexes[ed->v[0]].point, v1);
  VectorNormalize(v1);

  if (ed->v[0] == ed2->v[0])
    ed->v[0] = ed2->v[1];
  else if (ed->v[0] == ed2->v[1])
    ed->v[0] = ed2->v[0];
  else if (ed->v[1] == ed2->v[0])
    ed->v[1] = ed2->v[1];
  else if (ed->v[1] == ed2->v[1])
    ed->v[1] = ed2->v[0];
  else
    Error("HealEdges: edges don't meet");

  VectorSubtract(bspMem->dvertexes[ed->v[1]].point, bspMem->dvertexes[ed->v[0]].point, v2);
  VectorNormalize(v2);

  if (!VectorCompare(v1, v2))
    Error("HealEdges: edges not colinear");

  edgemapping[e2] = e1;
  saved = 0;

// remove all uses of e2
  for (i = firstmodelface; i < bspMem->numfaces; i++) {
    df = &bspMem->dfaces[i];
    for (j = 0; j < df->numedges; j++) {
      n = bspMem->dsurfedges[df->firstedge + j];
      if (n == e2 || n == -e2) {
	found[saved] = df;
	foundj[saved] = j;
	saved++;
	break;
      }
    }
  }

  if (saved != 2)
    eprintf("didn't find both faces for a saved edge\n");
  else {
    for (i = 0; i < 2; i++) {						       // remove this edge

      df = found[i];
      j = foundj[i];
      for (j++; j < df->numedges; j++)
	bspMem->dsurfedges[df->firstedge + j - 1] =
	  bspMem->dsurfedges[df->firstedge + j];
      bspMem->dsurfedges[df->firstedge + j - 1] = 0;
      df->numedges--;
    }

/*  edgefaces[e2][0] = edgefaces[e2][1] = NULL; */
    bspMem->edgefaces[0][e2] = bspMem->edgefaces[1][e2] = NULL;
  }
#else
  return;
#endif
}

/*
 * ==============
 * RemoveColinearEdges
 * ==============
 */
void RemoveColinearEdges(__memBase)
{
  int i, v;
  short int j;
  int c0, c1, c2, c3;
  checkpoint_t *cp;

/* changed by niels */
#ifdef EDGEMAPPING
// no edges remapped yet
  for (i = 0; i < bspMem->numedges; i++)
    edgemapping[i] = i;
#endif

// find vertexes that only have two edges
  /* added by niels */
  if(!(checkpoints = (checkpoint_t *)tmalloc(sizeof(checkpoint_t) * bspMem->numvertexes)))
    Error("RemoveColinearEdges: failed to allocate checkpoints!\n");

  for (i = firstmodeledge; i < bspMem->numedges; i++) {
/*  if (!edgefaces[i][0]) */
    if (!bspMem->edgefaces[0][i])
      continue;								       // removed

    for (j = 0; j < 2; j++) {
      v = bspMem->dedges[i].v[j];
      cp = &checkpoints[v];
      if (cp->numedges < 2)
	cp->edges[cp->numedges] = i;
      cp->numedges++;
    }
  }

// if a vertex only has two edges and they are colinear, it can be removed
  c0 = c1 = c2 = c3 = 0;

  for (i = 0; i < bspMem->numvertexes; i++) {
    cp = &checkpoints[i];
    switch (cp->numedges) {
      case 0:
	c0++;
	break;
      case 1:
	c1++;
	break;
      case 2:
	c2++;
	HealEdges(cp->edges[0], cp->edges[1]);
	break;
      default:
	c3++;
	break;
    }
  }

  //      mprintf ("%5i c0\n", c0);
  //      mprintf ("%5i c1\n", c1);
  //      mprintf ("%5i c2\n", c2);
  //      mprintf ("%5i c3+\n", c3);
  mprintf("%5i edges removed by tjunction healing\n", c2);
  /* added by niels */
  tfree(checkpoints);
}

/*
 * ==============
 * CountRealNumbers
 * ==============
 */
void CountRealNumbers(__memBase)
{
  int i;
  int c;

  mprintf("%5i regions\n", bspMem->numfaces - firstmodelface);

  c = 0;
  for (i = firstmodelface; i < bspMem->numfaces; i++)
    c += bspMem->dfaces[i].numedges;
  mprintf("%5i real marksurfaces\n", c);

  c = 0;
  for (i = firstmodeledge; i < bspMem->numedges; i++)
/*  if (edgefaces[i][0]) */
    if (bspMem->edgefaces[0][i])
      c++;								       // not removed

  mprintf("%5i real edges\n", c);
}

//=============================================================================

/*
 * ==============
 * GrowNodeRegion_r
 * ==============
 */
void GrowNodeRegion_r(__memBase, register struct node * node)
{
  struct dface_t *r;
  struct visfacet *f;
  int i;

  if (node->planenum == PLANENUM_LEAF)
    return;

  node->firstface = bspMem->numfaces;

  for (f = node->faces; f; f = f->next) {
//              if (f->outputnumber != -1)
    //                      continue;       // allready grown into an earlier region

    // emit a region

    if (bspMem->numfaces == bspMem->max_numfaces)
      ExpandClusters(bspMem, LUMP_FACES);
    f->outputnumber = bspMem->numfaces;
    r = &bspMem->dfaces[bspMem->numfaces];

    r->planenum = node->outputplanenum;
    r->side = f->planeside;
    r->texinfo = f->texturenum;
    for (i = 0; i < MAXLIGHTMAPS; i++)
      r->styles[i] = 255;
    r->lightofs = -1;

    // add the face and mergable neighbors to it

#if 0
    ClearRegionSize();
    AddFaceToRegionSize(f);
    RecursiveGrowRegion(r, f);
#endif
    r->firstedge = firstedge = bspMem->numsurfedges;
    for (i = 0; i < f->numpoints; i++) {
      if (bspMem->numsurfedges == bspMem->max_numsurfedges)
	ExpandClusters(bspMem, LUMP_SURFEDGES);
      bspMem->dsurfedges[bspMem->numsurfedges] = f->edges[i];
      bspMem->numsurfedges++;
    }

    r->numedges = bspMem->numsurfedges - r->firstedge;

    bspMem->numfaces++;
  }

  node->numfaces = bspMem->numfaces - node->firstface;

  GrowNodeRegion_r(bspMem, node->children[0]);
  GrowNodeRegion_r(bspMem, node->children[1]);
}

/*
 * ==============
 * GrowNodeRegions
 * ==============
 */
void GrowNodeRegions(__memBase, struct node * headnode)
{
  mprintf("----- GrowRegions -------\n");

  GrowNodeRegion_r(bspMem, headnode);

//RemoveColinearEdges ();
  CountRealNumbers(bspMem);
}

/*
 * ===============================================================================
 * 
 * Turn the faces on a plane into optimal non-convex regions
 * The edges may still be split later as a result of tjunctions
 * 
 * typedef struct
 * {
 * vec3_t       dir;
 * vec3_t       origin;
 * vec3_t       p[2];
 * } 
 * for all faces
 * for all edges
 * for all edges so far
 * if overlap
 * split
 * 
 * 
 * ===============================================================================
 */