// Verifies consistency of DCEL for lab 2, Spring 2005
// 3/3/05 BPW
// 3/5/05 Added detection of adjacent "flat" faces BPW

/* Define vertex indices. */
#define X   0
#define Y   1
#define Z   2
typedef enum { FALSE, TRUE } bool;

int V,F,E;

typedef struct tVertexStructure tsVertex;
typedef tsVertex *tVertex;

typedef struct tFaceStructure tsFace;
typedef tsFace *tFace;

typedef struct tEdgeStructure tsEdge;
typedef tsEdge *tEdge;

struct tVertexStructure {
   int      coord[3];
   int      Enum;         // Incident half-edge number
};

struct tFaceStructure {
   int      Enum;         // First half-edge
};

struct tEdgeStructure {
   int      tail;         // Vertex number for tail
   int      twin;         // Number of reverse half-edge
   int      face;         // Face number
   int      nextEnum,     // For doubly-linked list around face
            prevEnum;
};

// Three tables - loaded from file
tVertex vertex;
tFace face;
tEdge edge;

typedef int    tPointi[3];   /* Type integer point */

int VolumeSign( tPointi a, tPointi b, tPointi c, tPointi d )
{
   double vol;
   double ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;
   double bxdx, bydy, bzdz, cxdx, cydy, czdz;

   ax = a[X];
   ay = a[Y];
   az = a[Z];
   bx = b[X];
   by = b[Y];
   bz = b[Z];
   cx = c[X];
   cy = c[Y];
   cz = c[Z];
   dx = d[X];
   dy = d[Y];
   dz = d[Z];
        
   bxdx=bx-dx;
   bydy=by-dy;
   bzdz=bz-dz;
   cxdx=cx-dx;
   cydy=cy-dy;
   czdz=cz-dz;
   vol =   (az-dz) * (bxdx*cydy - bydy*cxdx)
         + (ay-dy) * (bzdz*cxdx - bxdx*czdz)
         + (ax-dx) * (bydy*czdz - bzdz*cydy);


   /* The volume should be an integer. */
   if      ( vol > 0.5 )   return  1;
   else if ( vol < -0.5 )  return -1;
   else                    return  0;
}

void readVertices()
{
int i;

// Read vertices and do range check
for (i=0;i<V;i++)
{
  scanf("%d %d %d %d",&vertex[i].coord[X],&vertex[i].coord[Y],
    &vertex[i].coord[Z],&vertex[i].Enum);
  if (vertex[i].Enum<0 || vertex[i].Enum>=E)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
}
}

void readFaces()
{
int i;

// Read faces and do range check
for (i=0;i<F;i++)
{
  scanf("%d",&face[i].Enum);
  if (face[i].Enum<0 || face[i].Enum>=E)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
}
}

void readEdges()
{
int i;

// Read edges and range checks
for (i=0;i<E;i++)
{
  scanf("%d %d %d %d %d",&edge[i].tail,&edge[i].twin,&edge[i].face,
    &edge[i].nextEnum,&edge[i].prevEnum);
  if (edge[i].tail<0 || edge[i].tail>=V)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
  if (edge[i].twin<0 || edge[i].twin>=E)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
  if (edge[i].face<0 || edge[i].face>=F)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
  if (edge[i].nextEnum<0 || edge[i].nextEnum>=E)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
  if (edge[i].prevEnum<0 || edge[i].prevEnum>=E)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
}
}

bool checkConsistency()
{
int i,j,edgesTouched;
int a,b,c,d;
bool clean=TRUE;

// Consistency between tables
for (i=0;i<V;i++)
  if (edge[vertex[i].Enum].tail!=i)
  {
    printf("Edge not incident to vertex %d\n",i);
    clean=FALSE;
  }

for (i=0;i<F;i++)
  if (edge[face[i].Enum].face!=i)
  {
    printf("Edge not included in face %d\n",i);
    clean=FALSE;
  }

for (i=0;i<E;i++)
  if (edge[edge[i].twin].twin!=i)
  {
    printf("Twin not consistent for edge %d\n",i);
    clean=FALSE;
  }

// Check entire list structure for each face.
edgesTouched=0;
for (i=0;i<F;i++)
{
  j=face[i].Enum;
  while (1)
  {
    edgesTouched++;
    if (edge[j].face!=i)
    {
      printf("Face number (%d) wrong for edge %d\n",edge[j].face,j);
      clean=FALSE;
    }
    if (edge[edge[j].nextEnum].prevEnum!=j)
    {
      printf("next (%d) wrong for edge %d\n",edge[j].nextEnum,j);
      clean=FALSE;
    }
    if (edge[edge[j].prevEnum].nextEnum!=j)
    {
      printf("prev (%d) wrong for edge %d\n",edge[j].prevEnum,j);
      clean=FALSE;
    }
    j=edge[j].nextEnum;
    if (j==face[i].Enum)
      break;
  }
}
if (edgesTouched!=E)
{
  printf("Only %d edges in faces!\n",edgesTouched);
  clean=FALSE;
}

if (!clean)
{
  printf("Face flatness check skipped\n");
  return clean;
}

for (i=0;i<F;i++)
{
  j=face[i].Enum;
  a=edge[j].tail;
  b=edge[edge[j].twin].tail;
  j=edge[j].nextEnum;
  c=edge[edge[j].twin].tail;
  j=edge[j].nextEnum;
  if (j==face[i].Enum)
    continue;  // A three-edge face must be flat . . .
  while (1)
  {
    d=edge[edge[j].twin].tail;
    if (VolumeSign(vertex[a].coord,vertex[b].coord,vertex[c].coord,
                   vertex[d].coord)!=0)
    {
      printf("Face %d is not flat\n",i);
      break;
    }
    j=edge[j].nextEnum;
    if (j==face[i].Enum)
      break;
    a=b;
    b=c;
    c=d;
  }
}

return clean;
}

/*---------------------------------------------------------------------
Collinear checks to see if the three points given are collinear,
by checking to see if each element of the cross product is zero.
---------------------------------------------------------------------*/
bool    Collinear( tPointi a, tPointi b, tPointi c )
{
   return
         ( c[Z] - a[Z] ) * ( b[Y] - a[Y] ) -
         ( b[Z] - a[Z] ) * ( c[Y] - a[Y] ) == 0
      && ( b[Z] - a[Z] ) * ( c[X] - a[X] ) -
         ( b[X] - a[X] ) * ( c[Z] - a[Z] ) == 0
      && ( b[X] - a[X] ) * ( c[Y] - a[Y] ) -
         ( b[Y] - a[Y] ) * ( c[X] - a[X] ) == 0  ;
}

void checkFlatTwins()
{
int i,j,twin;
int twin1,twin2,twin3,tail,head,c,d;
int nexti,previ,nexttwin1,prevtwin1;

for (i=0;i<E;i++)
{
  twin1=edge[i].twin;
  if (i<twin1)
  {
    tail=edge[i].tail;
    head=edge[twin1].tail;
    nexti=edge[i].nextEnum;
    twin2=edge[nexti].twin;
    j=nexti;
    while (1)
    {
      twin3=edge[j].twin;
      c=edge[twin3].tail;
      if (!Collinear(vertex[tail].coord,vertex[head].coord,
                     vertex[c].coord))
        break;
//printf("Skipped a c at %d\n",__LINE__);
      j=edge[j].nextEnum;
      if (j==i)
      {
        printf("Face is collinear %d\n",__LINE__);
        exit(0);
      }
    }

    nexttwin1=edge[twin1].nextEnum;
    j=nexttwin1;
    while (1)
    {
      twin3=edge[j].twin;
      d=edge[twin3].tail;
      if (!Collinear(vertex[tail].coord,vertex[head].coord,
                     vertex[d].coord))
        break;
//printf("Skipped a d at %d\n",__LINE__);
      j=edge[j].nextEnum;
      if (j==twin1)
      {
        printf("Face is collinear %d\n",__LINE__);
        exit(0);
      }
    }
    if (VolumeSign(vertex[tail].coord,vertex[head].coord,vertex[c].coord,
                   vertex[d].coord)==0)
      printf("Flat for faces for edge %d and twin %d\n",i,twin1);
  }
}
}

main()
{
// Process first line by allocating space
scanf("%d %d %d",&V,&F,&E);
vertex=(tVertex) malloc(V*sizeof(tsVertex));
face=(tFace) malloc(F*sizeof(tsFace));
edge=(tEdge) malloc(E*sizeof(tsEdge));
if (!vertex || !face || !edge)
{
  printf("Fatal at %d\n",__LINE__);
  exit(0);
}

readVertices();

readFaces();

readEdges();

if (!checkConsistency())
  return;

checkFlatTwins();
}