home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The World of Computer Software
/
World_Of_Computer_Software-02-385-Vol-1of3.iso
/
i
/
iritsm3s.zip
/
poly3d-h
/
out-edge.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-01-02
|
17KB
|
461 lines
/*****************************************************************************
* Routines to test all edges for visibility relative to the global polygon *
* list, and output the visible ones, to graphics screen or as text file *
* *
* Written by: Gershon Elber Ver 2.0, Jan. 1989 *
*****************************************************************************/
#ifdef __MSDOS__
#include <conio.h>
#endif /* __MSDOS__ */
#include <stdio.h>
#include <math.h>
#include <setjmp.h>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include "program.h"
#include "genmat.h"
#include "iritprsr.h"
#define MAX_POLYLINE_SIZE 50 /* Maximum size of output polyline. */
#define EDGE_ON_PLANE_EPS -0.003 /* Epsilon considers edge on plane. */
static EdgeStruct *OutEdgeHashTable[EDGE_HASH_TABLE_SIZE];
static void SaveCurrentMat(void);
static void OutputEdge(EdgeStruct *PEtemp);
static void EmitOutEdgeHashTable(void);
static char *Real2Str(RealType R);
static EdgeStruct *FoundMatchEdge(int *Colinear, EdgeStruct *PEdge);
static int FuzzSamePoints(RealType Pt1[3], RealType Pt2[3]);
static int ColinearPoints(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3]);
static int VisibleEdge(int EdgeMinY, EdgeStruct *PEdge,
IPPolygonStruct *PolyHashTable[]);
static int VisibleEdgeOnePoly(EdgeStruct *PEdge, IPPolygonStruct *PPoly);
static int InverseMatrix(MatrixType A);
/*****************************************************************************
* Routine to test for visibility all edges in EdgeHashTable and display or *
* output the visible ones only. It is assumed that only totally visible or *
* invisible edges are in table (Pass 3 broke all other kind of edges). *
*****************************************************************************/
void OutVisibleEdges(void)
{
int i;
long SaveTime = time(NULL);
EdgeStruct *PEtemp, *PEtail;
fprintf(stderr, "\nPass 4, Edges [%5d] = ", EdgeCount);
for (i = 0; i < EDGE_HASH_TABLE_SIZE; i++) OutEdgeHashTable[i] = NULL;
if (!InverseMatrix(GlblViewMat)) {
fprintf(stderr,
"\nNo inverse for matrix transformation, output is in screen space\n");
GenUnitMat(GlblViewMat); /* No inverse transform at all. */
}
printf("Automatic Hidden Line generator\t\tGershon Elber\t\tJan. 1989\n");
EdgeCount = 0;
/* Output the viewing matrices. */
SaveCurrentMat();
/* Output the OBJECT keyword line: */
printf("[OBJECT [COLOR %d] Hidden\n", HIDDEN_COLOR);
for (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)
if ((PEtemp = EdgeHashTable[i]) != NULL)/* If any edge in that list. */
while (PEtemp) {
EdgeCount++;
fprintf(stderr, "\b\b\b\b\b%5d", EdgeCount);
PEtail = PEtemp -> Pnext; /* OutputEdge destroy it. */
if ((!PEtemp -> Internal || GlblInternal) &&
VisibleEdge(i, PEtemp, PolyHashTable))
OutputEdge(PEtemp);
PEtemp = PEtail;
}
EmitOutEdgeHashTable(); /* Output all polylines. */
printf("]\n"); /* Close the Hidden object. */
fprintf(stderr, ", %d seconds.", time(NULL) - SaveTime);
}
/*****************************************************************************
* Routine to save current view trans. IritPrsrViewMat to a generic mat file *
*****************************************************************************/
static void SaveCurrentMat(void)
{
int i, j;
printf("[OBJECT MATRICES\n [OBJECT VIEW_MAT\n\t[MATRIX");
for (i = 0; i < 4; i++) {
printf("\n\t ");
for (j = 0; j < 4; j++) printf("%12lf ", IritPrsrViewMat[i][j]);
}
printf("\n\t]\n ]\n");
if (IritPrsrWasPrspMat) {
printf( " [OBJECT PRSP_MAT\n\t[MATRIX");
for (i = 0; i < 4; i++) {
printf("\n\t ");
for (j = 0; j < 4; j++) printf("%12lf ", IritPrsrPrspMat[i][j]);
}
printf("\n\t]\n ]\n");
}
printf("]\n\n");
}
/*****************************************************************************
* Routine to output one edge to the OutEdgeHashTable. *
* The edge is inserted into OutEdgeHashTable to be able to match it into *
* the longest path possible - connecting edges into edge sequence. *
* Each edge is inserted by its Ymin, which will cause the paths be in *
* increased Y order... *
*****************************************************************************/
static void OutputEdge(EdgeStruct *PEtemp)
{
int Level;
Level = (int) ((PEtemp -> Vertex[0] -> Coord[1] + 1.0) *
EDGE_HASH_TABLE_SIZE2);
PEtemp -> Pnext = OutEdgeHashTable[Level];
OutEdgeHashTable[Level] = PEtemp;
}
/*****************************************************************************
* Routine to scan the OutEdgeHashTable, and Emit the longest paths found in *
* it by searching for consecutive edges and combining colinear edges. *
*****************************************************************************/
static void EmitOutEdgeHashTable(void)
{
int i, j, Colinear, Count;
RealType Vec[MAX_POLYLINE_SIZE][3];
EdgeStruct *PEtemp, *PEnext;
for (i = 0; i < EDGE_HASH_TABLE_SIZE; i++) /* Scan all the hash table. */
while (OutEdgeHashTable[i]) { /* Scan all edges in entry. */
PEtemp = OutEdgeHashTable[i]; /* Take edge out of table. */
OutEdgeHashTable[i] = OutEdgeHashTable[i] -> Pnext;
/* Print first vertices of polyline: */
Count = 0;
MultVecby4by4(Vec[Count++], PEtemp -> Vertex[0] -> Coord,
GlblViewMat);
MultVecby4by4(Vec[Count++], PEtemp -> Vertex[1] -> Coord,
GlblViewMat);
while ((PEnext = FoundMatchEdge(&Colinear, PEtemp)) != NULL) {
if (Colinear) /* Overwrite last entry. */
MultVecby4by4(Vec[Count - 1], PEnext -> Vertex[1] -> Coord,
GlblViewMat);
else
MultVecby4by4(Vec[Count++], PEnext -> Vertex[1] -> Coord,
GlblViewMat);
if (Count >= MAX_POLYLINE_SIZE) break;
PEtemp = PEnext;
}
printf(" [POLYLINE %d\n", Count);
for (j = 0; j < Count; j++)
printf("\t[%s %s %s]\n",
Real2Str(Vec[j][0]),
Real2Str(Vec[j][1]),
Real2Str(Vec[j][2]));
printf(" ]\n");
}
}
/*****************************************************************************
* Convert a real number into a string. *
* The routine mentains 3 different buffers simultanuously so up to 3 calls *
* can be issued from same printf... *
*****************************************************************************/
static char *Real2Str(RealType R)
{
static int i = 0;
static char Buffer[3][LINE_LEN_LONG];
int j, k;
if (ABS(R) < 1e-6) R = 0.0; /* Round off very small numbers. */
sprintf(Buffer[i], "%-8.6lg", R);
for (k = 0; !isdigit(Buffer[i][k]) && k < LINE_LEN_LONG; k++);
if (k >= LINE_LEN_LONG) {
fprintf(stderr, "Conversion of real number failed.\n");
MyExit(3);
}
for (j = strlen(Buffer[i]) - 1; Buffer[i][j] == ' ' && j > k; j--);
if (strchr(Buffer[i], '.') != NULL)
for (; Buffer[i][j] == '0' && j > k; j--);
Buffer[i][j+1] = 0;
j = i;
i = (i + 1) % 3;
return Buffer[j];
}
/*****************************************************************************
* Routine to scan the OutEdgeHashTable for a match edge if any, delete it *
* from HashTable and return it. if colinear with PEdge set Colinear to TRUE. *
* return FALSE if no match found (end of polyline). *
*****************************************************************************/
static EdgeStruct *FoundMatchEdge(int *Colinear, EdgeStruct *PEdge)
{
int Level;
EdgeStruct *PEtemp, *PElast;
Level = (int) ((PEdge -> Vertex[1] -> Coord[1] + 1.0) *
EDGE_HASH_TABLE_SIZE2);
PEtemp = PElast = OutEdgeHashTable[Level];
while (PEtemp) { /* First scan for colinear edge. */
if (FuzzSamePoints(PEdge -> Vertex[1] -> Coord,
PEtemp -> Vertex[0] -> Coord) &&
ColinearPoints(PEdge -> Vertex[0] -> Coord,
PEdge -> Vertex[1] -> Coord,
PEtemp -> Vertex[1] -> Coord)) {
*Colinear = TRUE;
/* Delete that edge from hash table structure: */
if (PEtemp == PElast)
OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
else
PElast -> Pnext = PEtemp -> Pnext;
if (FuzzSamePoints(PEtemp -> Vertex[0] -> Coord,
PEtemp -> Vertex[1] -> Coord))
return FoundMatchEdge(Colinear, PEdge); /* Call recursively! */
else
return PEtemp;
}
PElast = PEtemp;
PEtemp = PEtemp -> Pnext;
}
PEtemp = PElast = OutEdgeHashTable[Level];
while (PEtemp) { /* Next scan for any match edge. */
if (FuzzSamePoints(PEdge -> Vertex[1] -> Coord,
PEtemp -> Vertex[0] -> Coord)) {
*Colinear = FALSE;
/* Delete that edge from hash table structure: */
if (PEtemp == PElast)
OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
else PElast -> Pnext = PEtemp -> Pnext;
if (FuzzSamePoints(PEtemp -> Vertex[0] -> Coord,
PEtemp -> Vertex[1] -> Coord))
return FoundMatchEdge(Colinear, PEdge); /* Call recursively! */
else
return PEtemp;
}
PElast = PEtemp;
PEtemp = PEtemp -> Pnext;
}
return NULL; /* No match - end of polyline. */
}
/*****************************************************************************
* Routine to test if two points are almost the same, and returns TRUE if so. *
*****************************************************************************/
static int FuzzSamePoints(RealType Pt1[3], RealType Pt2[3])
{
return (APX_EQ(Pt1[0], Pt2[0]) &&
APX_EQ(Pt1[1], Pt2[1]) &&
APX_EQ(Pt1[2], Pt2[2]));
}
/*****************************************************************************
* Routine to test if three points are colinear, and returns TRUE if so... *
* Algorithm: cross product should be zero if colinear... *
* Note this routine does not return TRUE if Pt2 is not between Pt1..Pt3. *
*****************************************************************************/
static int ColinearPoints(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3])
{
int i;
RealType Xout, Yout, Zout, U[3], V[3], temp;
for (i = 0; i < 3; i++) {
U[i] = Pt2[i] - Pt1[i];
V[i] = Pt3[i] - Pt2[i];
}
temp = sqrt(SQR(U[0]) + SQR(U[1]) + SQR(U[2]));
if (APX_EQ(temp, 0.0)) return TRUE;
for (i = 0; i < 3; i++) U[i] = U[i] / temp;
temp = sqrt(SQR(V[0]) + SQR(V[1]) + SQR(V[2]));
if (APX_EQ(temp, 0.0)) return TRUE;
for (i = 0; i < 3; i++) V[i] = V[i] / temp;
/* Xoutput = Uy * Vz - Uz * Vy. */
Xout = U[1] /* Uy */ * V[2] /* Vz */ -
U[2] /* Uz */ * V[1] /* Vy */;
/* Youtput = Uz * Vx - Ux * Vz. */
Yout = U[2] /* Uz */ * V[0] /* Vx */ -
U[0] /* Ux */ * V[2] /* Vz */;
/* Zoutput = Ux * Vy - Uy * Vx. */
Zout = U[0] /* Ux */ * V[1] /* Vy */ -
U[1] /* Uy */ * V[0] /* Vx */;
return APX_EQ(Xout, 0.0) && APX_EQ(Yout, 0.0) && APX_EQ(Zout, 0.0) &&
((MIN(Pt1[0], Pt3[0]) < Pt2[0]) && (MAX(Pt1[0], Pt3[0]) > Pt2[0]) &&
(MIN(Pt1[1], Pt3[1]) < Pt2[1]) && (MAX(Pt1[1], Pt3[1]) > Pt2[1]));
}
/*****************************************************************************
* Routine to test the visibility of the given edge relative to all polygons *
* in polygon list. return TRUE if the edge is visible. It is assumed that *
* the edge is whole visible or whole invisible (Pass 3 broke the edge if *
* that whas not true). Also it is assumed the polygons are all convex. *
* A short cut is made to test the edge only against the needed polygons *
* only, using the polygon hash table and Y level sorting. *
*****************************************************************************/
static int VisibleEdge(int EdgeMinY, EdgeStruct * PEdge,
IPPolygonStruct *PolyHashTable[])
{
int EdgeMaxY, i;
IPPolygonStruct *PPolyList, *PPolyLast;
EdgeMaxY = MIN((MAX(PEdge -> Vertex[0] -> Coord[1],
PEdge -> Vertex[1] -> Coord[1]) + 1.0) *
EDGE_HASH_TABLE_SIZE2,
EDGE_HASH_TABLE_SIZE1);
/* Test the edge only in the interval 0..EdgeMaxY as these are the only */
/* which might hide that edge. Also polygons with MaxY less than */
/* EdgeMinY are deleted from PolyHashTable as it is assumed the edges */
/* are scanned in increasing order of the EdgeHashTable. */
for (i = 0; i <= EdgeMaxY; i++) {
PPolyList = PPolyLast = PolyHashTable[i];
while (PPolyList) {
if ((PPolyList -> Ymax + 1.0) * EDGE_HASH_TABLE_SIZE2 < EdgeMinY)
/* Delete this polygon! */
if (PPolyList == PPolyLast) {
PolyHashTable[i] = PPolyLast = PPolyList -> Pnext;
PPolyList = PPolyList -> Pnext;
}
else {
PPolyList = PPolyList -> Pnext;
PPolyLast -> Pnext = PPolyList;
}
else { /* Polygon still active - test edge against it. */
/* If found one polygon that hides this edge return FALSE... */
if (!VisibleEdgeOnePoly(PEdge, PPolyList)) return FALSE;
PPolyLast = PPolyList;
PPolyList = PPolyList -> Pnext;
}
}
}
return TRUE;
}
/*****************************************************************************
* Routine to test the visibility of the given edge relative to one polygon *
* return TRUE if the edge is visible. It is assumed that the edge is whole *
* visible or whole invisible (Pass 3 broke the edge if that was not true). *
* Also it is assumed the polygons are all convex. *
*****************************************************************************/
static int VisibleEdgeOnePoly(EdgeStruct *PEdge, IPPolygonStruct *PPoly)
{
int i;
RealType MidPt[3];
IPVertexStruct *PList;
for (i = 0; i < 3; i++) MidPt[i] = /* Calc a mid point on the edge: */
(PEdge -> Vertex[0] -> Coord[i] +
PEdge -> Vertex[1] -> Coord[i]) / 2.0;
/* Test if edges is out of polygon boundary box: */
if (MidPt[0] > PPoly -> Xmax || MidPt[0] < PPoly -> Xmin ||
MidPt[1] > PPoly -> Ymax || MidPt[1] < PPoly -> Ymin) return TRUE;
if (PPoly -> Plane[0] * MidPt[0] +
PPoly -> Plane[1] * MidPt[1] +
PPoly -> Plane[2] * MidPt[2] +
PPoly -> Plane[3] > EDGE_ON_PLANE_EPS)
return TRUE; /* Edge in front of polygon. */
/* We cannt escape it - we now must find if the point is included in */
/* polygon area. We assume the polygon is convex and use the fact */
/* that the polygon list is ordered such that the cross product */
/* of two consecutive vertices and the point is positive for all */
/* consecutive vertices pairs iff the point is in the polygon. */
PList = PPoly -> PVertex;
while (PList -> Pnext) {
if (CrossProd(PList -> Coord, PList -> Pnext -> Coord, MidPt) < 0)
return TRUE; /* Out of polygon! */
PList = PList -> Pnext;
}
/* Now test last polygon edge (last point, first point in poly list) */
if (CrossProd(PList -> Coord, PPoly -> PVertex -> Coord, MidPt) < 0)
return TRUE; /* Out of polygon! */
return FALSE;
}
/*****************************************************************************
* Procedure to calculate the INVERSE of a given MatrixType matrix A which is *
* modified to the inverted matrix. Return TRUE if inverse exists. *
*****************************************************************************/
static int InverseMatrix(MatrixType A)
{
MatrixType InvA;
int i, j, k;
RealType V, D;
GenUnitMat(InvA);
for (i = 0; i < 4; i++) {
V = A[i][i]; /* Find the new pivot. */
k = i;
for (j = i + 1; j < 4; j++) if (A[j][i] > V) {
/* Find maximum on col i, row i+1..4. */
V = A[j][i];
k = j;
}
j = k;
if (i != j) for (k = 0; k < 4; k++) {
/* Swap. */
D = A[i][k]; A[i][k] = A[j][k]; A[j][k] = D;
D = InvA[i][k]; InvA[i][k] = InvA[j][k]; InvA[j][k] = D;
}
for (j = i + 1; j < 4; j++) { /* Eliminate col i from row i+1..4. */
V = A[j][i] / A[i][i];
for (k = 0; k < 4; k++) {
A[j][k] -= V * A[i][k];
InvA[j][k] -= V * InvA[i][k];
}
}
}
for (i = 4-1; i >= 0; i--) { /* Back Substitution. */
if (A[i][i] == 0) return FALSE; /* Error. */
for (j = 0; j < i; j++) { /* Eliminate col i from row 1..i-1. */
V = A[j][i] / A[i][i];
for (k = 0; k < 4; k++) {
/* A -> [j][k] -= V * A[i][k]; */
InvA[j][k] -= V * InvA[i][k];
}
}
}
for (i = 0; i < 4; i++) /* Normalize the inverse Matrix. */
for (j = 0; j < 4; j++)
InvA[i][j] /= A[i][i];
for (i = 0; i < 4; i++) /* Copy inverted matrix to A. */
for (j = 0; j < 4; j++)
A[i][j] = InvA[i][j];
return TRUE;
}