BSPCODE.TXT

Nobody has yet posted a single line of actual code to build such a data
structure.  Perhaps the first of many contributions, hopefully, is in order.

Since as of this writing it is 24-01-95 1:09:31 AM EST, I am just too tired
to document, rename variables and debug my code.  As such, errors are
likely and numerous ;-)

I make no claims as to the fitness, portibility, and/or correctness of
the following code fragments.

Please direct any comnents when I wake up ... zzzzzz


--------------------------jang@ecf.toronto.edu----------------------------


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define RAN(a, b)	((a) + (((b)-(a)+1) * ((rand()*106+1283)%6075)) / 6075)
#define MakeNode(a)	(a *)malloc(sizeof(a))

#define DIST		1155
#define DTOR		1.7453292e-2
#define NORM		1155000

enum { BACK, FRONT, SPLIT };

typedef struct { long x, y, z; } 	POINT;

typedef struct {
	POINT		a, b, nr;
	short		c, d;
} PDATA;

struct polygon {
	POINT		q0, q1, norm, *V;
	short		vx, t;
};

#define POLYGON		struct polygon

struct listOfPolygons {
	POLYGON			*p;
	struct listOfPolygons	*next;
};

#define LIST	struct listOfPolygons

struct BSPtree_node {
	LIST			*lp;
	struct BSPtree_node	*back;
	struct BSPtree_node	*front;
};

#define NODE	struct BSPtree_node

POINT		nt, pt, svec, tvec, uvec, vvec;

void   Err(short);

void ReadMap(LIST *L, short *S)
{
	LIST	*tmp;
	PDATA	*info;
	POLYGON	*P;
	short	i, fp, sz;

	if ((fp = open("data.001", O_RDONLY)) < 0)
		Err(1);
	else {
		while ((sz = read(fp, info, sizeof(info))) != EOF) {

			P->q0 = info->a; P->q1 = info->b;
			P->norm = info->nr; P->vx = info->c;
			P->t = info->d;

			for (i = 0; i < P->vx; i++)
				read(fp, P->V[i], sizeof(P->V[i]));

			if ((tmp = MakeNode(LIST)) == NULL) Err(0);
			if ((tmp->p = MakeNode(POLYGON)) == NULL) Err(0);
			tmp->p = P;
			tmp->next = L;
			L = tmp;
			free(tmp);
			
			++*S;
		}
	}
	close(fp);
}


NODE *BSP_select(LIST *, short *);
void  BSP_add(LIST *, POLYGON *);
void  BSP_combine(LIST *, NODE *, LIST *);
void  BSP_split(POLYGON *, POLYGON *, POLYGON *, POLYGON *);
int   WhereAmI(LIST *, POLYGON *);

LIST *BSP_build(LIST *L, short *S)
{
	LIST	*bList, *fList;
	NODE	*N;
	POLYGON	*P, *bHalf, *fHalf;
	short	s0, s1;

	if ((N = MakeNode(NODE)) == NULL) Err(0);

	if (L == NULL)
		return;
	else {
		s0 = s1 = 0;
		N = BSP_select(L, &(*S));
		P = N->lp->p;
		bList = fList = NULL;
		do {
			switch (WhereAmI(L, P)) {
			case BACK  :
				   BSP_add(bList, L->p);
				   s0++;
				   break;
			case FRONT :
				   BSP_add(bList, L->p);
				   s1++;
				   break;
			case SPLIT :
				   BSP_split(L->p, P, bHalf, fHalf);
				   BSP_add(bList, bHalf); s0++;
				   BSP_add(fList, fHalf); s1++;
				   break;
			}
			L = L->next;
		} while (L != NULL);
		BSP_combine(BSP_build(bList, &s0), N, BSP_build(fList, &s1));
	}
	return L;
}

long  Dot(POINT *, POINT *, POINT *);

NODE *BSP_select(LIST *L, short *S)
{
	LIST	*Ls, *cur, *pre;
	NODE	*tmp;
	POINT	Nr, Pn;
	POLYGON	*P;
	long	D1, D2;
	short	i, j, k, lim, lo, min = 255, n;
	
	if ((tmp = MakeNode(NODE)) == NULL) Err(0);
	tmp->lp = L;

	srand(6074);
	lo = (*S < 6) ? *S : 6;
	for (i = 0; i < lo; i++) {

		cur = Ls = L;
		pre = NULL;
		lim = RAN(1, *S);
		k = 0;

		for (j = 1; j < lim; j++) {
			pre = cur;
			cur = cur->next;
		}

		P = Ls->p;
		Nr = cur->p->norm;
		Pn = cur->p->V[0];

		for (j = 1; j < *S; j++) {
			D1 = Dot(&P->V[0], &Pn, &Nr);
			for (n = 1; n < P->vx; n++) {
				D2 = Dot(&P->V[n], &Pn, &Nr);
				if ((D1 ^ D2) < 0) {
					k++;
					break;
				}
				D1 = D2;
			}
			Ls = Ls->next;
			P = Ls->p;
		}

		if (pre != NULL && k < min) {
			tmp->lp = cur;
			min = k;
		}
	}

	if (pre == NULL)
		L = L->next;
	else	pre->next = cur->next;

	--*S;
	return tmp;
}

int   WhereAmI(LIST *L, POLYGON *P)
{
	POINT	Nr, Pn;
	POLYGON	*Pg;
	short	i;
	long	D1, D2;

	Pg = L->p;
	Nr = P->norm;
	Pn = P->V[0];

	D1 = Dot(&Pg->V[0], &Pn, &Nr);
	for (i = 1; i < Pg->vx; i++) {
		D2 = Dot(&Pg->V[i], &Pn, &Nr);
		if ((D1 ^ D2) < 0) return SPLIT;
		D1 = D2;
	}

	if (D1 < 0) return BACK;
	return FRONT;
}

void  BSP_add(LIST *L, POLYGON *P)
{
	LIST *tmp;

	if ((tmp = MakeNode(LIST)) == NULL) Err(0);
	if ((tmp->p = MakeNode(POLYGON)) == NULL) Err(0);
	tmp->p = P;
	tmp->next = L;
	L = tmp;
	free(tmp);
}

int   HalfSpace(LIST *);
void  BSP_dispPoly(NODE *);

void  BSP_traverse(NODE *N)
{
	if (N != NULL) {
		if (HalfSpace(N->lp)) {
			BSP_traverse(N->front);
			BSP_dispPoly(N);
 			BSP_traverse(N->back);
 		} else {
 			BSP_traverse(N->back);
			BSP_traverse(N->front);
		}
	}
}

void  BSP_combine(LIST *L0, NODE *N, LIST *L1)
{
	N->back->lp = L0; N->front->lp = L1;
}

int   HalfSpace(LIST *L)
{
	POLYGON		*P;
	register int	dx, dy, dz;

	P = L->p;

	dx = pt.x - P->V[0].x;
	dy = pt.y - P->V[0].y;
	dz = pt.z - P->V[0].z;

	if (dx*P->norm.x + dy*P->norm.y + dz*P->norm.z < 0) return BACK;
	return FRONT;
}

void  BSP_dispPoly(NODE *N)
{
	POLYGON		*P;
	POINT		Nr, Pn, *T;
	register int	dx, dy, dz;
	register long	D1, D2, *G, beta, gamma;
	short		i, j, k;

	P = N->lp->p;
	Nr = P->norm;
	Pn = P->V[0];

	D1 = Dot(&uvec, &Pn, &Nr);
	D2 = Dot(&pt, &Pn, &Nr);

	if ((D1 ^ D2) >= 0) {
		D1 = Dot(&vvec, &Pn, &Nr);
		if ((D1 ^ D2) >= 0) {
			N = N->front;
			return;
		}
	}

	for (i = 0; i < P->vx; i++) {

		dx = pt.x - P->V[i].x; dy = pt.y - P->V[i].y;
		dz = pt.z - P->V[i].z;

		beta = dx * vvec.y - dy * vvec.x;
		if (beta > 0 && beta < NORM) {
			G[i] = gamma = dy * uvec.x - dx * uvec.y;
			T[i].z = beta + gamma;
			if (gamma > 0 && gamma < NORM)
				T[i].x = XCOR * gamma / T[i].z;
			else	T[i].x = (gamma >= NORM) ? XCOR : 0;
			if (i) j = gamma - G[i-1];
		} else {
			T[i].x = (beta >= NORM) ? 0 : XCOR;
		}

		if (i && j && T[i].x == XCOR || !T[i].x) {
			T[i].z -= (T[i].z - T[i-1].z) * G[i] / j;
			T[i+1].z = T[i].z; k = i;
		}

		beta = dz * tvec.y - dy * tvec.x;
		if (beta > 0 && beta < NORM) {
			gamma = dy * svec.x - dz * svec.y;
			if (gamma > 0 && gamma < NORM)
				T[i].y = YCOR * gamma / (beta + gamma);
			else	T[i].y = (gamma >= NORM) ? YCOR : 0;
		} else {
			T[i].y = (beta >= NORM) ? 0 : YCOR;
		}
	}

	if (T[0].x == XCOR || !T[0].x ) T[0].z = T[k].z;

	/* Display polygon */

}

POINT New(POINT *, POINT *, POINT *, POINT *);

void  BSP_split(POLYGON *po, POLYGON *P, POLYGON *bh, POLYGON *fh)
{
	POINT	Nr, Pn, a, from, to;
	long	D1, D2;
	short	b, f, i, j;

	if ((bh = MakeNode(POLYGON)) == NULL) Err(0);
	if ((fh = MakeNode(POLYGON)) == NULL) Err(0);

	b = f = j = 0;
	Nr = P->norm;
	Pn = P->V[0];

	D1 = Dot(&po->V[0], &Pn, &Nr);

	for (i = 0; i < po->vx; i++) {

		from = po->V[i];
		to = po->V[i+1];

		D2 = Dot(&to, &Pn, &Nr);
		if ((D1 ^ D2) < 0) {
			if (!j) {
				a = New(&P->q0, &P->q1, &from, &to);
				if (D1 < D2) {
					bh->V[b] = from;
					bh->V[b+1] = fh->V[f] = a;
					fh->V[f+1] = to;
				} else {
					fh->V[f] = from;
					fh->V[f+1] = bh->V[b] = a;
					bh->V[b+1] = to;
				}
				j = 1;
			} else {
				a = New(&P->q0, &P->q1, &from, &to);
				bh->V[b+1] = fh->V[f+1] = a;
				if (D1 < D2) {
					bh->V[b] = from;
					fh->V[f+2] = to;
				} else {
					fh->V[f] = from;
					bh->V[b+2] = to;
				}
			} b++; f++;
		} else {
			if (D1 < 0) {
				bh->V[b] = from;
				bh->V[b+1] = to;
				b++; 
			} else {
				fh->V[f] = from;
				fh->V[f+1] = to;
				f++;
			}
		}
		D1 = D2;
	}
}

long  Dot(POINT *q, POINT *a, POINT *n)
{
	return (q->x - a->x)*n->x + (q->y - a->y)*n->y + (q->z - a->z)*n->z;
}

POINT New(POINT *e0, POINT *e1, POINT *p0, POINT *p1)
{
	POINT	a;
	int	Ax, Bx, Cx, Ay, By, Cy, d, f, bias, value;

	Ax = e1->x - e0->x;
	Ay = e1->y - e0->y;

	Bx = p0->x - p1->x;
	By = p0->y - p1->y;

	Cx = e0->x - p0->x;
	Cy = e0->y - p0->y;

	d  = By*Cx - Bx*Cy;
	f  = Ay*Bx - Ax*By;

	value = d*Ax;
	bias  = ((value ^ f) >= 0) ? f >> 1 : -f >> 1;
	a.x  = e0->x + (value + bias) / f;

	value = d*Ay;
	bias  = ((value ^ f) >= 0) ? f >> 1 : -f >> 1;
	a.y  = e0->y + (value + bias) / f;

	if (e0->x != e1->x)
		a.z = (a.x - MIN(p0->x, p1->x)) / 
		      ABS(p1->x - p0->x) * ABS(p1->z - p0->z);
	else	a.z = (a.y - MIN(p0->y, p1->y)) /
		      ABS(p1->y - p0->y) * ABS(p1->z - p0->z);

	return a;
}

void Err(short a)
{
	char *message[] = {"Dynamic allocation failure",
			   "Map file not found",
			   "Not enough memory", };

	printf("%s\n", message[a]);
	exit(1);
}


------------------------------jang@ecf.toronto.edu-----------------------------



.Hin.