/*****************************************************************************
*   "Irit" - the 3d polygonal solid modeller.				     *
*									     *
* Written by:  Gershon Elber				Ver 0.2, Mar. 1990   *
******************************************************************************
*  Module to handle adjacancies between polygons. Each edge has exactly two  *
* polygons which share it. An edge is implicitly defined by the VList - each *
* VertexStruct defines an edge with its succesor, and has a pointer to the   *
* other polygons using that edge. Those pointers are our target in this      *
* module.								     *
*****************************************************************************/

#include <stdio.h>
#include <math.h>
#include "program.h"
#include "adjacncy.h"
#include "allocate.h"

/* #define DEBUG	     If the adjacencies should be printed to stdout. */
/* #define DEBUG2     If the hash table content should be printed to stdout. */

#define HASH_TABLE_SIZE  100
#define HASH_TABLE_SIZE1 101			     /* One above the above. */
#define HASH_TABLE_SIZE2 50			       /* Half of the above. */

typedef struct HashTableEntry {
    int Key;
    PolygonStruct *Pl;
    VertexStruct *V;
    struct HashTableEntry *Pnext;
} HashTableEntry;

typedef struct HashTableStruct {
    HashTableEntry *Entry[HASH_TABLE_SIZE1];
} HashTableStruct;

/* Prototypes of local function of adjacecies module: */
static void InsertHashTable(HashTableStruct *HashTbl, PolygonStruct *Pl,
							VertexStruct *V);
static int EdgeKey(VertexStruct *V);
static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl, int EntryNum,
							HashTableEntry *PHash);
static int SameEdges(PointType V1E1, PointType V2E1,
		     PointType V1E2, PointType V2E2);

static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
							HashTableEntry *PHash);
static void SecondEdgeKey(VertexStruct *V, int *Key1, int *Key2);
static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
					int EntryNum, HashTableEntry *PHash);
static int TestSameDir(PointType Pt11, PointType Pt12,
			PointType Pt21, PointType Pt22);
static void DeleteHashTable(HashTableStruct *SecondHashTable,
						VertexStruct *V, int EntryNum);

/*****************************************************************************
*   Routine to generate adjacencies to the given object. Returns TRUE if all *
* adjacencies were resolved, meaning the object is perfectly closed.	     *
*   Note an edge might be only partially adjacent to another edge, and a     *
* second attempt is made to find (again only part of - see below) them. Any  *
* case, FALSE will be returned as there is no way we can say the object is   *
* perfectly closed!							     *
*   This is the only routine to generate the adjacencies of a geometric      *
* object. These adjacencies are needed for the boolean operations on them.   *
*   Algorithm: for each edge, for each polygon in the object, the edges are  *
* sorted according to the key defined by EdgeKey routine (sort in hash tbl). *
* A second path on the table is made to match common keys edges and set the  *
* pointers from one to another. Note that each edge is common to exactly 2   *
* faces if it is internal, or exactly 1 face if it is on the border (if the  *
* object is open).							     *
*****************************************************************************/
int GenAdjacencies(ObjectStruct *PObj)
{
    int i, IsOpenObject;
    HashTableStruct *HashTbl, *SecondHashTbl;
    HashTableEntry *PHash, *PHashMatch;
    PolygonStruct *Pl;
    VertexStruct *V;

    if (!IS_POLY_OBJ(PObj))
	FatalError("GenAdjacencies: Non polygonal object");
    if (IS_POLYLINE_OBJ(PObj)) return TRUE;	 /* No adj. in polyline obj. */

    IsOpenObject = FALSE;		    /* "Default" is closed object... */

    /* Prepare hash tables (for first and second attempts) and clear them.   */
    HashTbl = (HashTableStruct *) MyMalloc(sizeof(HashTableStruct),
								ALLOC_OTHER);
    for (i = 0; i < HASH_TABLE_SIZE1; i++) HashTbl -> Entry[i] = NULL;
    SecondHashTbl = (HashTableStruct *) MyMalloc(sizeof(HashTableStruct),
								ALLOC_OTHER);
    for (i = 0; i < HASH_TABLE_SIZE1; i++) SecondHashTbl -> Entry[i] = NULL;

    /* Step one - enter all the edges into the hash table: */
    Pl = PObj -> U.Pl.P;
    while (Pl) {
	V = Pl -> V;
	do {
	    InsertHashTable(HashTbl, Pl, V); /* Insert the edge V..V->Pnext. */
	    V = V -> Pnext;
	} while (V != NULL && V != Pl -> V);
	Pl = Pl -> Pnext;
    }

#ifdef DEBUG2
    printf("Hash Table content:\n");
    for (i = 0; i < HASH_TABLE_SIZE; i++) {
	PHash = HashTbl -> Entry[i];
	if (PHash) printf("\nHashTable entry %d:\n", i);
	while (PHash) {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		PHash -> V -> Pt[0],
		PHash -> V -> Pt[1],
		PHash -> V -> Pt[2],
		PHash -> V -> Pnext -> Pt[0],
		PHash -> V -> Pnext -> Pt[1],
		PHash -> V -> Pnext -> Pt[2]);
	    PHash = PHash -> Pnext;
	}
    }
#endif /* DEBUG2 */

    /* Step two - scans all the entries and look for the matching edge.      */
    for (i = 0; i < HASH_TABLE_SIZE; i++)
	while (HashTbl -> Entry[i] != NULL) {
	    PHash = HashTbl -> Entry[i]; /* Remove one edge from hash table. */
	    HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;

	    /* Find matching edge (if perfect match - exactly the same edge) */
	    /* Otherwise put the edge in SecondHashTbl.			     */
	    if ((PHashMatch = FindMatchEdge(HashTbl, i, PHash)) == NULL) {
		PHash -> V -> PAdj = NULL;
		InsertSecondHashTable(SecondHashTbl, PHash);
		IsOpenObject = TRUE;
	    }
	    else {
#		ifdef DEBUG
		    /* If debug switch the pointers of the edges themselves. */
		    PHash -> V -> PAdj = (PolygonStruct *) PHashMatch -> V;
		    PHashMatch -> V -> PAdj = (PolygonStruct *) PHash -> V;
#		else
		    /* Otherwise switch pointers of the edges polygons */
		    PHash -> V -> PAdj = PHashMatch -> Pl;
		    PHashMatch -> V -> PAdj = PHash -> Pl;
#		endif /* DEBUG */

		MyFree((char *) PHash, ALLOC_OTHER);
		MyFree((char *) PHashMatch, ALLOC_OTHER);
	    }
	}

#ifdef DEBUG
    printf("Adjacencies for object %s (found to be open = %d)\n",
	PObj -> Name, IsOpenObject);
    Pl = PObj -> U.Pl.P;
    /* Note that the adjacency in DEBUG is the other edge, not other polygon.*/
    while (Pl) {
	V = Pl -> V;
	do {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		V -> Pt[0], V -> Pt[1], V -> Pt[2],
		V -> Pnext -> Pt[0], V -> Pnext -> Pt[1], V -> Pnext -> Pt[2]);
	    if (V -> PAdj != NULL)
		printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
		    ((VertexStruct *) V -> PAdj) -> Pt[0],
		    ((VertexStruct *) V -> PAdj) -> Pt[1],
		    ((VertexStruct *) V -> PAdj) -> Pt[2],
		    ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[0],
		    ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[1],
		    ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[2]);
	    else
		printf("No Match!\n\n");
	    V = V -> Pnext;
	} while (V != NULL && V != Pl -> V);
	Pl = Pl -> Pnext;
    }
#endif /* DEBUG */

#ifdef DEBUG2
    printf("Hash Table content left after all full matches were deleted:\n");
    for (i = 0; i < HASH_TABLE_SIZE; i++) {
	PHash = SecondHashTbl -> Entry[i];
	if (PHash) printf("\nHashTable entry %d:\n", i);
	while (PHash) {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		PHash -> V -> Pt[0],
		PHash -> V -> Pt[1],
		PHash -> V -> Pt[2],
		PHash -> V -> Pnext -> Pt[0],
		PHash -> V -> Pnext -> Pt[1],
		PHash -> V -> Pnext -> Pt[2]);
	    PHash = PHash -> Pnext;
	}
    }
#endif /* DEBUG2 */

    /* Time to activate the second attempt - scan SecondHashTable for edges  */
    /* partially adjacent to each other, but with one common vertex!	     */
    for (i = 0; i < HASH_TABLE_SIZE; i++)
	while (SecondHashTbl -> Entry[i] != NULL) {
	    PHash = SecondHashTbl -> Entry[i];/* Remove one edge from table. */
	    SecondHashTbl -> Entry[i] = SecondHashTbl -> Entry[i] -> Pnext;

	    /* Remove the second instance of this edge with other key: */
	    DeleteHashTable(SecondHashTbl, PHash -> V, PHash -> Key);

	    /* Find matching edge (if perfect match - exactly the same edge) */
	    /* Otherwise put the edge in SecondHashTbl.			     */
	    if ((PHashMatch = FindSecondMatchEdge(SecondHashTbl, i, PHash)) ==
									NULL) {
		PHash -> V -> PAdj = NULL;		    /* Failed again! */
		MyFree((char *) PHash, ALLOC_OTHER);
	    }
	    else {
#		ifdef DEBUG
		    /* If debug switch the pointers of the edges themselves. */
		    PHash -> V -> PAdj = (PolygonStruct *) PHashMatch -> V;
		    PHashMatch -> V -> PAdj = (PolygonStruct *) PHash -> V;
#		else
		    /* Otherwise switch pointers of the edges polygons. */
		    PHash -> V -> PAdj = PHashMatch -> Pl;
		    PHashMatch -> V -> PAdj = PHash -> Pl;
#		endif /* DEBUG */

		MyFree((char *) PHash, ALLOC_OTHER);
		MyFree((char *) PHashMatch, ALLOC_OTHER);
	    }
	}

#ifdef DEBUG
    printf("Adjacencies for object %s - second attempt (found to be open = %d)\n",
	PObj -> Name, IsOpenObject);
    Pl = PObj -> U.Pl.P;
    /* Note that the adjacency in DEBUG is the other edge, not other polygon.*/
    while (Pl) {
	V = Pl -> V;
	do {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		V -> Pt[0], V -> Pt[1], V -> Pt[2],
		V -> Pnext -> Pt[0], V -> Pnext -> Pt[1], V -> Pnext -> Pt[2]);
	    if (V -> PAdj != NULL)
		printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
		    ((VertexStruct *) V -> PAdj) -> Pt[0],
		    ((VertexStruct *) V -> PAdj) -> Pt[1],
		    ((VertexStruct *) V -> PAdj) -> Pt[2],
		    ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[0],
		    ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[1],
		    ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[2]);
	    else
		printf("No Match!\n\n");
	    V = V -> Pnext;
	} while (V != NULL && V != Pl -> V);
	Pl = Pl -> Pnext;
    }
#endif /* DEBUG */

    MyFree((char *) HashTbl, ALLOC_OTHER);
    MyFree((char *) SecondHashTbl, ALLOC_OTHER);

    return !IsOpenObject;
}

/*****************************************************************************
* Evaluate a key (integer!) from the given vertex V (in polygon Pl) and      *
* insert that in the hash table:					     *
*****************************************************************************/
static void InsertHashTable(HashTableStruct *HashTbl, PolygonStruct *Pl,
							VertexStruct *V)
{
    int Key;
    HashTableEntry *PHash;

    PHash = (HashTableEntry *) MyMalloc(sizeof(HashTableEntry), ALLOC_OTHER);
    PHash -> Pl = Pl;
    PHash -> V = V;
    PHash -> Key = Key = EdgeKey(V);
    PHash -> Pnext = HashTbl -> Entry[Key];
    HashTbl -> Entry[Key] = PHash;
}

/*****************************************************************************
*   This routine evaluate a key for the given edge. In order the try to make *
* them unique as possible, the point is projected on a "random" vector. I    *
* picked vector X + 1.57 * Y + 1.29 * Z. If you have better one - change it. *
*   The key itself is the average of the two vertices keys.		     *
*   Note we get best results if the object is between ~-10..10.		     *
*****************************************************************************/
static int EdgeKey(VertexStruct *V)
{
    int key;
    RealType RKey1, RKey2;

    RKey1 = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
    V = V -> Pnext;
    RKey2 = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);

    key = (((int) ((RKey1 + RKey2) * 10.0)) + HASH_TABLE_SIZE) / 2;

    return BOUND(key, 0, HASH_TABLE_SIZE - 1);
}

/*****************************************************************************
*   Search The hash table for matching with the given edge pointed by PHash. *
* PHash was extracted from the hash table in entry EntryNum, so the match    *
* is probably in the same entry. If it is not, it must be (if there is one!) *
* in EntryNum+1 as we scans the entries in order and (EntryNum-1) is empty.  *
*   Note that idealy the match was in EntryNum, but because of real number   *
* errors there is a small chance it will be in its neibours: EntryNum +/- 1. *
*****************************************************************************/
static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl, int EntryNum,
							HashTableEntry *PHash)
{
    int i;
    HashTableEntry *PLast = NULL, *PMatch;

    for (i = EntryNum; i <= EntryNum+1; i++) {
	PMatch = HashTbl -> Entry[i];
	while (PMatch) {
	    if (SameEdges(PHash -> V -> Pt,  PHash -> V -> Pnext -> Pt,
			  PMatch -> V -> Pt, PMatch -> V -> Pnext -> Pt)) {
		/* Delete the matched edge from hash table, and return it: */
		if (PMatch == HashTbl -> Entry[i])
		    HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
		else
		    PLast -> Pnext = PLast -> Pnext -> Pnext;
		return PMatch;
	    }
	    PLast = PMatch;
	    PMatch = PMatch -> Pnext;
	}
    }

    return NULL;				  /* No match for this one ! */
}

/*****************************************************************************
*   Compere two edges - if the same up to an EPSILON (see APX_EQ, irit.h).   *
* The two vetrices of each edge are given, but no order on them is assumed   *
*****************************************************************************/
static int SameEdges(PointType V1E1, PointType V2E1,
		     PointType V1E2, PointType V2E2)
{
    return (PT_EQ(V1E1, V1E2) && PT_EQ(V2E1, V2E2)) ||
	   (PT_EQ(V1E1, V2E2) && PT_EQ(V2E1, V1E2));
}

/******************************************************************************
*   Everything from this point handle the second attempt - try to match edges *
* which are not complete match - cases which one edge is only part of its     *
* adjacent one. We trap only cases which the two edges has common vertex. If  *
* the two edges has no common vertex (i.e. one is totally in the other) we    *
* still misses that. You are invited to improve that. Any case this one will  *
* have influence in extremely rare cases (The booleans will usually propagate *
* the information using the common vertex edges).			      *
*   Note, the obvious, that if one edge is adjacent to few edges, only one    *
* (arbitrarily) will result in the match, and the other will result as NULL.  *
******************************************************************************/

/*****************************************************************************
* Evaluate two keys (integer!) from the given edge in HashTableEntry struct. *
* This time the keys are of the vertices themselves (see SecondEdgeKet rtn). *
* Note each HashTableEntry hold the key of the other entry this time...      *
*****************************************************************************/
static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
							HashTableEntry *PHash)
{
    int Key1, Key2;
    HashTableEntry *PHash2;

    SecondEdgeKey(PHash -> V, &Key1, &Key2);

    /* And insert the edge as at Key1 (using given HashTableEntry PHash): */
    PHash -> Key = Key2;
    PHash -> Pnext = SecondHashTbl -> Entry[Key1];
    SecondHashTbl -> Entry[Key1] = PHash;

    /* And insert the edge as at Key2 (allocating new HashTableEntry for it):*/
    PHash2 = (HashTableEntry *) MyMalloc(sizeof(HashTableEntry), ALLOC_OTHER);
    PHash2 -> Pl = PHash -> Pl;
    PHash2 -> V = PHash -> V;
    PHash2 -> Key = Key1;
    PHash2 -> Pnext = SecondHashTbl -> Entry[Key2];
    SecondHashTbl -> Entry[Key2] = PHash2;
}

/*****************************************************************************
*   This routine evaluate two keys for the given edge - one for each of its  *
* vertices, and again tries to make the unique as passible:		     *
* picked the same vector: X + 1.57 * Y + 1.29 * Z.			     *
*   Note we get best results if the object is between ~-10..10.		     *
*****************************************************************************/
static void SecondEdgeKey(VertexStruct *V, int *Key1, int *Key2)
{
    RealType RKey;

    RKey = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
    *Key1 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
    *Key1 = BOUND(*Key1, 0, HASH_TABLE_SIZE - 1);

    V = V -> Pnext;
    RKey = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
    *Key2 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
    *Key2 = BOUND(*Key2, 0, HASH_TABLE_SIZE - 1);
}

/*****************************************************************************
*   Search The hash table for matching with the given edge pointed by PHash, *
* as in the second attempt: the keys used here are of the vertices	     *
* themselves, so we should search for match in given index EntryNum only.    *
* We search for same vertex AND same direction, which if both match, confirm *
* at list partial adjacency between the two edges (both with same vertex as  *
* one end - the vertex with this key).					     *
*****************************************************************************/
static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
					int EntryNum, HashTableEntry *PHash)
{
    int EqualFirst, SameDir = FALSE;
    HashTableEntry *PLast = NULL, *PMatch;

    PMatch = SecondHashTbl -> Entry[EntryNum]; /* It must be here if exists. */
    while (PMatch) {
	if ((EqualFirst = PT_EQ(PHash -> V -> Pt, PMatch -> V -> Pt)) != 0
		      || PT_EQ(PHash -> V -> Pt, PMatch -> V -> Pnext -> Pt)) {
	    /* Found same vertex in PMatch as first vertex in PHash - test   */
	    /* the direction vectors, to be same also:			     */
	    if (EqualFirst) {
		SameDir = TestSameDir(PHash -> V -> Pnext -> Pt,
				      PHash -> V -> Pt,
				      PMatch -> V -> Pnext -> Pt,
				      PMatch -> V -> Pt);
	    }
	    else {
		SameDir = TestSameDir(PHash -> V -> Pnext -> Pt,
				      PHash -> V -> Pt,
				      PMatch -> V -> Pt,
				      PMatch -> V -> Pnext -> Pt);
	    }
	}
	else if ((EqualFirst = PT_EQ(PHash -> V -> Pnext -> Pt,
						 PMatch -> V -> Pt)) != 0 ||
	    PT_EQ(PHash -> V -> Pnext -> Pt, PMatch -> V -> Pnext -> Pt)) {
	    /* Found same vertex in PMatch as second vertex in PHash - test  */
	    /* the direction vectors, to be same also:			     */
	    if (EqualFirst) {
		SameDir = TestSameDir(PHash -> V -> Pt,
				      PHash -> V -> Pnext -> Pt,
				      PMatch -> V -> Pnext -> Pt,
				      PMatch -> V -> Pt);
	    }
	    else {
		SameDir = TestSameDir(PHash -> V -> Pt,
				      PHash -> V -> Pnext -> Pt,
				      PMatch -> V -> Pt,
				      PMatch -> V -> Pnext -> Pt);
	    }
	}

	if (SameDir) {	       /* TRUE iff same vertex AND same direction!!! */
	    /* Delete the matched edge from the hash table, its compliment   */
	    /* with the second key and return a pointer to it:		     */
	    if (PMatch == SecondHashTbl -> Entry[EntryNum])
		SecondHashTbl -> Entry[EntryNum] =
		    SecondHashTbl -> Entry[EntryNum] -> Pnext;
	    else
		PLast -> Pnext = PLast -> Pnext -> Pnext;
	    /* Uses the key in structure (hold key of other entry!): */
	    DeleteHashTable(SecondHashTbl, PMatch -> V, PMatch -> Key);
	    return PMatch;
	}
	PLast = PMatch;
	PMatch = PMatch -> Pnext;
    }

    return NULL; /* No match for this one ! */
}

/*****************************************************************************
*   Test the the two point pairs (defined two edges) are actually on the     *
* same direction - find normalized direction vector for each and test if     *
* their dot product is equal to 1.					     *
*****************************************************************************/
static int TestSameDir(PointType Pt11, PointType Pt12,
			PointType Pt21, PointType Pt22)
{
    PointType Dir1, Dir2;

    PT_SUB(Dir1, Pt12, Pt11);
    PT_SUB(Dir2, Pt22, Pt21);

    PT_NORMALIZE(Dir1);
    PT_NORMALIZE(Dir2);

    return APX_EQ(DOT_PROD(Dir1, Dir2), 1.0);
}

/*****************************************************************************
*   Delete entry in SecondHashTable index EntryNum, which holds vertex V.    *
* This vertex MUST be there, otherwise its a fatal error.		     *
*****************************************************************************/
static void DeleteHashTable(HashTableStruct *SecondHashTable,
						VertexStruct *V, int EntryNum)
{
    HashTableEntry *PLast, *PHash = SecondHashTable -> Entry[EntryNum];

    while (PHash != NULL) {
	if (PHash -> V == V) break;
	PLast = PHash;
	PHash = PHash -> Pnext;
    }

    if (PHash == NULL)
	FatalError("DeleteHashTable: No hash table entry to delete\n");
    else {
	if (PHash == SecondHashTable -> Entry[EntryNum])
	    SecondHashTable -> Entry[EntryNum] =
		SecondHashTable -> Entry[EntryNum] -> Pnext;
	else
	    PLast -> Pnext = PHash -> Pnext;
	MyFree((char *) PHash, ALLOC_OTHER);
    }
}