← Back to contents
C source, ASCII text
— 15K bytes
— 1994-01-01
/*
------------------------------------------------------------------
Black Nebula
File : Clip.c
Programmer: Colin Adams
Date: 23/4/91
Last Modified : 10/6/91
------------------------------------------------------------------
*/
#include "3d.h"
#include <proto/dos.h>
#define BOUNDARY_COUNT 4
#define MAX_LIMIT 500
extern short U_rot, W_rot, View_Angle;
extern short num_active[];
static point s[BOUNDARY_COUNT], first_point[BOUNDARY_COUNT];
static short new_edge[BOUNDARY_COUNT];
static polygon *clip_poly;
static object *sort_obj; /* global for sort */
static point clip_point;
static int Depth[TOTAL_MAX_OBJECTS]; /* array to sort in */
static int xp[3], yp[3], zp[3];
enum
{
TOP,
RIGHT,
BOTTOM,
LEFT
};
/* ------------------------------------------------------------------
Fast Square Root Code for IEEE floating point numbers
from Graphics Gems, Academic Press 1990
Supplied by Peter Stephenson
------------------------------------------------------------------
*/
static short sqrttab[0x100];
void build_table(void)
{
unsigned short i;
float f;
unsigned int *fi = (int *) &f;
for(i=0; i<= 0x7f; i++)
{
/* build a float with the bit pattern i as
mantissa and an exponent of 0, stored as 127 */
*fi = (i << 16) | ( 127 << 23);
f = sqrt(f);
/* take the square root then strip the first 7 bits of the
mantissa into the table */
sqrttab[i] = (*fi & 0x7fffff) >> 16;
/* repeat the process, this time with an exponent of 1,
stored as 128 */
*fi = (i << 16) | (128 << 23);
f = sqrt(f);
sqrttab[i+0x80] = (*fi & 0x7fffff) >> 16;
}
}
float fsqrt(float n)
{
unsigned int *num = (int *) &n;
short e;
if(n==0) return 0;
e = (*num >> 23) - 127;
*num &= 0x7fffff;
if(e & 0x01)
*num |= 0x800000;
e >>= 1;
*num = ((sqrttab[*num >> 16]) << 16) | ((e + 127) << 23);
return n;
}
/* ------------------------------------------------------------------
Clipping Routines
The clipping algorithm is Sutherland and Hodgeman's. The
description of the algorithm is in Computer Graphics by
D. Hearn & M. Baker.
------------------------------------------------------------------
*/
short inside(point *p, short edge)
/* returns true if the point is inside the given edge, false if not */
{
switch(edge)
{
case TOP: /* top line */
if(p->y >= Y_MIN)
return 1;
return 0;
case RIGHT: /* right hand side */
if(p->x <= X_MAX)
return 1;
return 0;
case BOTTOM: /* bottom line */
if(p->y <= Y_MAX)
return 1;
return 0;
case LEFT: /* left hand side */
if(p->x >= X_MIN)
return 1;
return 0;
}
}
short cross(point *p, point *p2, short edge)
/* returns true if the 2 points cross the given edge */
{
/*
This first bit is a slight hack to make points generated a mile
apart when on the other side of the eye, not appear! May or may
not be fixed.
2/6/91
It is now very unlikely to be fixed, as I don't think it
can be!! But it seems to work...
*/
if(abs(p->x) > MAX_LIMIT || abs(p2->x) > MAX_LIMIT ||
abs(p->y) > MAX_LIMIT || abs(p2->y) > MAX_LIMIT)
return 0;
/* end of horrible speed reducing hack */
switch(edge)
{
case TOP: /* top edge */
if(p->y > Y_MIN)
{
if(p2->y <= Y_MIN)
return 1;
}
else if(p2->y > Y_MIN)
return 1;
return 0;
case RIGHT: /* right hand edge */
if(p->x > X_MAX)
{
if(p2->x <= X_MAX)
return 1;
}
else if(p2->x > X_MAX)
return 1;
return 0;
case BOTTOM: /* bottom edge */
if(p->y > Y_MAX)
{
if(p2->y <= Y_MAX)
return 1;
}
else if(p2->y > Y_MAX)
return 1;
return 0;
case LEFT: /* left hand edge */
if(p->x > X_MIN)
{
if(p2->x <= X_MIN)
return 1;
}
else if(p2->x > X_MIN)
return 1;
return 0;
}
}
void find_intersection(point *p1, point *p2, short edge, point *i)
/*
Find intersection point of line, uses fixed point maths. This routine
is heavily optimized, requiring only 1 integer division and 1 integer
multiplication to find the intersection!!! If you know a faster
method please tell me!
*/
{
register int mnumer, mdenom;
/* get gradient */
mnumer = (p2->y - p1->y);
mdenom = (p2->x - p1->x);
switch(edge)
{
case TOP:
{
register int j = Y_MIN - p1->y;
i->y = Y_MIN;
i->x = p1->x + (mnumer ? (j * mdenom) / mnumer : 0);
return;
}
case RIGHT:
{
register int j = (X_MAX - p1->x);
i->x = X_MAX;
i->y = p1->y + (mdenom ? (mnumer*j)/mdenom : 0);
return;
}
case BOTTOM:
{
register int j = Y_MAX - p1->y;
i->y = Y_MAX;
i->x = p1->x + (mnumer ? (j * mdenom) / mnumer : 0);
return;
}
case LEFT:
{
register int j = (X_MIN - p1->x);
i->x = X_MIN;
i->y = p1->y + (mdenom ? (mnumer*j)/mdenom : 0);
return;
}
}
}
void clip_this(point *p, short edge)
/* recursively checks a point against all the boundary edges */
{
point i;
if(new_edge[edge])
{
first_point[edge].x = p->x;
first_point[edge].y = p->y;
new_edge[edge] = 0;
}
else if(cross(p, &s[edge], edge))
{
find_intersection(p, &s[edge], edge, &i);
if(edge < 3)
clip_this(&i, edge+1);
else
{
clip_poly->clip_num++;
clip_poly->clip_x[clip_poly->clip_num] = i.x;
clip_poly->clip_y[clip_poly->clip_num] = i.y;
}
}
s[edge].x = p->x;
s[edge].y = p->y;
if(inside(p, edge))
{
if(edge < 3)
clip_this(p, edge+1);
else
{
clip_poly->clip_num++;
clip_poly->clip_x[clip_poly->clip_num] = p->x;
clip_poly->clip_y[clip_poly->clip_num] = p->y;
}
}
}
void clip_closer(void)
/*
Closing routine. For each window edge, clips the line connecting
the last saved vertex and the first_point processed against the
edge
*/
{
point i;
register short edge;
for(edge=0; edge<BOUNDARY_COUNT; edge++)
{
if(cross(&s[edge], &first_point[edge], edge))
{
find_intersection(&s[edge], &first_point[edge],edge,&i);
if(edge<3)
clip_this(&i, edge+1);
else
{
clip_poly->clip_num++;
clip_poly->clip_x[clip_poly->clip_num] = i.x;
clip_poly->clip_y[clip_poly->clip_num] = i.y;
}
}
}
}
void polygon_clip(polygon *poly)
/* clips the polygon sent against the boundaries */
{
register int k;
clip_poly = poly; /* use a global for speed */
clip_poly->clip_num = -1; /* no points in output yet */
for(k=0; k<4; k++)
new_edge[k] = 1;
for(k=0; k<clip_poly->numpoints; k++)
{
clip_point.x = clip_poly->x[k];
clip_point.y = clip_poly->y[k];
clip_this(&clip_point, 0);
}
clip_closer(); /* close polygon */
clip_poly->clip_num++;
}
/* ------------------------------------------------------------------
Hidden Surface Routines
Determines the order to draw objects, and polygons within
an object
------------------------------------------------------------------
*/
int SpinPolyCentre(object *obj, polygon *poly)
/*
Spin a point and calculate it's depth from the eye. The point
is the centre point of a polygon, and is used for hidden surface
removal. This routine should be pretty quick, but if you know a
faster algorithm, I'd love to know it!
*/
{
register int x,y,z;
register int xrot, yrot, zrot;
xrot = obj->rot_x;
yrot = obj->rot_y;
zrot = obj->rot_z;
x = poly->centre.x;
y = poly->centre.y;
z = poly->centre.z;
/* rotate a point around the z axis */
if(zrot)
{
register int temp, temp2, temp3;
temp = x;
temp2 = costable[zrot];
temp3 = sintable[zrot];
x = ((temp2*temp)>>16) - ((temp3*y)>>16);
y = ((temp3*temp)>>16) + ((temp2*y)>>16);
}
/* rotate a point around the x axis */
if(xrot)
{
register int temp, temp2, temp3;
temp = y;
temp2 = costable[xrot];
temp3 = sintable[xrot];
y = ((temp2*temp)>>16) - ((temp3*z)>>16);
z = ((temp3*temp)>>16) + ((temp2*z)>>16);
}
/* rotate a point around the y axis */
if(yrot)
{
register int temp, temp2, temp3;
temp = z;
temp2 = costable[yrot];
temp3 = sintable[yrot];
z = ((temp2*temp)>>16) - ((temp3*x)>>16);
x = ((temp3*temp)>>16) + ((temp2*x)>>16);
}
/* calculate depths */
x = ex - (x + obj->trans_x);
y = ey - (y + obj->trans_y);
z = ez - (z + obj->trans_z);
return (x*x + y*y + z*z);
}
void qsort_poly(int *left, int *right, int al, int ar)
/*
Quicksort for polygon depths within an object. This can be written
faster.
*/
{
register int *p = left, *q = right, x = *(left+(right-left)/2), w;
register int tar = ar, tal = al;
do
{
while(*p>x)
{
p++; tal++;
}
while(*q<x)
{
q--; tar--;
}
if(p>q) break;
w = *p;
*p = *q;
*q = w;
{
register polygon *temp;
temp = sort_obj->draworder[tar];
sort_obj->draworder[tar] = sort_obj->draworder[tal];
sort_obj->draworder[tal] = temp;
}
p++; q--;
tal++; tar--;
} while (p<=q);
if(left<q) qsort_poly(left, q, al, tar);
if(p<right) qsort_poly(p, right, tal, ar);
}
void DepthSort(object *obj)
/* sorts an object's polygons into depths from the eye to determine
the order in which they are to be drawn */
{
register polygon *pg = obj->poly;
register short count = 0;
register char oneobj = 0;
if(!obj->poly->next)
oneobj = 1;
while(pg)
{
obj->draworder[count] = pg;
/* NB. as an optimization, the actual distance from the eye is
not stored but the square of it is, so the magnitude is
relevant! */
/*
Check for back faces, this is the only way to make my
hidden surface code work properly... I really didn't want to
add this, but doesn't seem to slow down the code much as
it doesn't draw/erase polygons which are back faces.
Unfortunately it still sorts faces which aren't visible,
should be fixed!
*/
if(pg->numpoints>2 && !oneobj)
{
register int i, A, B, C, D;
for(i=0; i<3; i++)
{
xp[i] = manipulate_x[pg->p[i]];
yp[i] = manipulate_y[pg->p[i]];
zp[i] = manipulate_z[pg->p[i]];
}
/* horrible plane equation calculations */
A = yp[0]*(zp[1]-zp[2]) + yp[1]*(zp[2]-zp[0]) + yp[2]*(zp[0]-zp[1]);
B = zp[0]*(xp[1]-xp[2]) + zp[1]*(xp[2]-xp[0]) + zp[2]*(xp[0]-xp[1]);
C = xp[0]*(yp[1]-yp[2]) + xp[1]*(yp[2]-yp[0]) + xp[2]*(yp[0]-yp[1]);
D = - xp[0]*(yp[1]*zp[2] - yp[2]*zp[1]) - xp[1]*(yp[2]*zp[0] - yp[0]*zp[2])
- xp[2]*(yp[0]*zp[1] - yp[1]*zp[0]);
if((ex*A + ey*B + ez*C + D)<0)
{
pg->back_face = 1;
pg->clip_num = 0;
}
else
{
pg->back_face = 0;
}
}
else
pg->back_face = 0;
Depth[count++] = pg->back_face ? 0 : SpinPolyCentre(obj, pg);
pg = (polygon *) pg->next;
}
obj->draworder[count] = NULL; /* terminate list */
sort_obj = obj;
if(count)
qsort_poly(Depth, &Depth[count-1], 0, count-1);
}
/* Object sorting routines */
double rad(double degrees)
/* converts degrees to radians */
{
double one8 = 180;
return 3.141592654/(one8/degrees);
}
int GetAngle(int *h, short px, short py, short pz)
{
register int o, angle, tempint;
register char quad;
int temp;
float depth, temp2;
int d;
tempint = ex-px;
depth = tempint * tempint;
tempint = ez - pz;
depth += tempint * tempint;
tempint = ey - py;
*h = depth + tempint * tempint;
if(px>ex)
{
o = px - ex;
if(pz>ez)
quad = 4;
else
{
if(pz==ez) return 0;
quad = 1;
}
}
else
{
if(px==ex)
{
if(pz<ez)
return 90;
else
return 270;
}
o = ex - px;
if(pz>ez)
quad = 3;
else
{
if(pz==ez) return 180;
quad = 2;
}
}
temp = o * 4096;
temp2 = fsqrt(depth);
d = temp/temp2;
if(d>4096) d = 4096; /* to fix small errors which make d > 4096 */
angle = anti_sin[d];
switch(quad)
{
case 1: angle = 90 - angle; break;
case 2: angle = 90 + angle; break;
case 3: angle = 180 + (90-angle); break;
case 4: angle += 270; break;
}
return angle;
}
int SpinObjCentre(object *obj)
{
register int x,y,z;
register short angle;
int distance;
x = obj->trans_x + obj->centre_x;
y = obj->trans_y + obj->centre_y;
z = obj->trans_z + obj->centre_z;
angle = GetAngle(&distance, x, y, z);
/* tries to eliminate objects which aren't in the field of view */
if(View_Angle>=45)
{
if(View_Angle<=315)
{
if(angle>View_Angle+45 || angle<View_Angle-45)
obj->drawme = 0;
}
else
{
if(angle<View_Angle-45 && angle>View_Angle-315)
obj->drawme = 0;
}
}
else
{
if(angle>View_Angle+45 && angle<View_Angle+315)
obj->drawme = 0;
}
/* check if I hit something */
if(distance<(obj->radius*5+500) && obj->type<MYMISSILE)
{
obj->i_am_dying = 1; /* kill enemy too! */
obj->explode = 1;
am_i_dead = 1;
}
return distance;
}
void qsort_depth(int *left, int *right, int al, int ar)
/* quicksort objects into drawing order */
{
register int *p = left, *q = right, x = *(left+(right-left)/2), w;
register int tar = ar, tal = al;
do
{
while(*p>x)
{
p++; tal++;
}
while(*q<x)
{
q--; tar--;
}
if(p>q) break;
w = *p;
*p = *q;
*q = w;
{
register object *temp;
temp = active_list[tar];
active_list[tar] = active_list[tal];
active_list[tal] = temp;
}
p++; q--;
tal++; tar--;
} while (p<=q);
if(left<q) qsort_depth(left, q, al, tar);
if(p<right) qsort_depth(p, right, tal, ar);
}
void CalculateObjects(void)
/* sorts the objects into depths from the eye to determine
the order in which they are to be drawn
*/
{
register short i,j;
/*
kills off objects which are floating around in a dead state but
aren't totally removed from the system yet
*/
for(i=0; i<no_objects; i++)
{
while(i<no_objects && active_list[i]->i_am_dying)
{
if(active_list[i]->explode && active_list[i]->i_am_dying==1)
CreateExplosion(active_list[i]);
if(active_list[i]->i_am_dying++>2)
{
if(active_list[i]->type==EXPLOSION)
{
for(j=0; j<MAX_EXPLOSIONS; j++)
{
if(active_list[i] == &explosions[j])
{
exp_free[j] = 0;
break;
}
}
}
else
{
for(j=0; j<MAX_OBJECTS; j++)
{
if(active_list[i] == &obj_types[active_list[i]->type][j])
{
obj_free[active_list[i]->type][j] = 0;
break;
}
}
}
num_active[active_list[i]->type]--;
for(j=i; j<no_objects-1; j++)
active_list[j] = active_list[j+1];
no_objects--;
}
else
{
active_list[i]->drawme = 0;
break;
}
}
if(i<no_objects)
{
if(active_list[i]->drawme)
PrepareObject(active_list[i]);
}
}
for(i=0; i<no_objects; i++)
Depth[i] = SpinObjCentre(active_list[i]);
qsort_depth(Depth, &Depth[no_objects-1], 0, no_objects-1);
}
void ClearObjects(void)
/* destroys the old image */
{
register int i;
for(i=0; i<no_objects; i++)
EraseObject(active_list[i]);
}
void DisplayObjects(void)
{
register int i;
for(i=0; i<no_objects; i++)
DrawObject(active_list[i]);
}
/* end of module clip.c */