/*****************************************************************************
* "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);
}
}
