rob@haddock.UUCP (10/08/85)
#if 0
Enclosed herein is 'C' source code which implements the clipping
algorithm described in the Jan '84 ACM Trans. on Graphics.
The interface to these routines is such that they should be nearly
trivial to slip into your current plot(3) programs. For more
information about the algorithm, consult the paper.
Dirk Grunwald (grunwald@uiucdcs, grunwald@UIUC.ARPA) presented
in this same forum this past February code to perfrom 2d and 3d
clipping on data structures that appeared to be suited to your
SUNCORE programs. Consult your net.sources archives (the title
was "2d, 3d clipping") or drop Dirk a line to find that implementation.
Special note to lint-pickers: I will buy the first person who finds
a bug or error in this code dinner at Mary Chung's, Cambridge's finest
Chinese restaurant.
Rob Adams {decvax ! cca | yale | ihnp4 | cbosgd}!ima!rob
{bbncca | harvard | zurton | cfib | mit-ems | wjh12 }!ima!rob
{uscvax | ucla-vax | vortex}!ism780!rob
Interactive Systems, 7th floor, 441 Stuart st, Boston, MA 02116; 617-247-1155
#endif
/*--------------------------- C U T H E R E -------------------------------*/
/* @(#)clip.c 1.2 - 85/10/07 */
/*
* Fast, 2d, integer clipping plot(3) operations.
* Clipping algorithm taken from "A New Concept and Method for Line Clipping,"
* Barsky & Liang, ACM Tran. on Graphics Vol 3, #1, Jan 84.
* In contrast to the algoritm presented in TOG, this one works
* on integers only. The idea is to only do that which is useful
* for my plot(3) based graphics programs.
*/
/*
* Interface:
*
* clipinit(int xleft, int ybottom, int xright, int ytop)
* Send this guy the same things you would send to space().
* Don't worry if xleft > xright.
*
* clip2d(int *x0p, int *y0p, int *x1p, int *y1p)
* By the time this returns, the points referenced will have
* been clipped. Call this right before line(), with pointers
* to the same arguments. Returns TRUE is the resulting line
* can be displayed.
*
* inview2d(int x0,int y0,int x1,int y1)
* Does a fast check for simple acceptance. Returns TRUE if
* the segment is intirely in view. If your program runs too
* slowly, consider making this a macro.
*
* Usage of clip2d and inview2d would be something like --
* (inview2d(x0,y0, x1,y1) || clip2d(&x0,&y0, &x1,&y1))
* && line(x0,y0,x1,y1);
* If inview2d says the segment is safe or clip2d says the clipped
* segment is safe, then go ahead and print the line.
*/
static int Xleft, Xright, Ytop, Ybot;
#define TRUE 1
#define FALSE 0
typedef int bool;
/*------------------------------- clipinit ----------------------------------*/
clipinit(x0,y0,x1,y1)
{
if ( x0 > x1 ) {
Xleft = x1;
Xright = x0;
} else {
Xleft = x0;
Xright = x1;
}
if ( y0 > y1 ) {
Ytop = y0;
Ybot = y1;
} else {
Ytop = y1;
Ybot = y0;
}
}
/*------------------------------- inview2d ----------------------------------*/
bool inview2d(x0,y0, x1,y1)
register x0,y0, x1,y1;
{
return x0 >= Xleft && x0 <= Xright && x1 >= Xleft && x1 <= Xright &&
y0 >= Ybot && y0 <= Ytop && y1 >= Ybot && y1 <= Ytop;
}
/*-------------------------------- clip2d -----------------------------------*/
bool clip2d(x0p, y0p, x1p, y1p)
int *x0p, *y0p, *x1p, *y1p;
{
register int x0 = *x0p,
y0 = *y0p,
x1 = *x1p,
y1 = *y1p;
register int dx, dy;
double t0, t1;
t0 = 0.0, t1 = 1.0; /* init parametic equations */
dx = x1 - x0;
if ( clipt( -dx, x0 - Xleft, &t0, &t1) &&
clipt( dx, Xright - x0, &t0, &t1)) {
dy = y1 - y0;
if ( clipt( -dy, y0 - Ybot, &t0, &t1) &&
clipt( dy, Ytop - y0, &t0, &t1)) {
if ( t1 < 1 ) {
*x1p = x0 + t1 * dx;
*y1p = y0 + t1 * dy;
}
if ( t0 > 0.0 ) {
*x0p = x0 + t0 * dx;
*y0p = y0 + t0 * dy;
}
return TRUE;
}
}
return FALSE;
}
/*-------------------------------- clip2d -----------------------------------*/
static bool clipt(p, q, t0p, t1p)
register int p, q;
register double *t0p, *t1p;
{
register double r;
if ( p < 0 ) {
r = (double)q / p;
if ( r > *t1p )
return FALSE;
if ( r > *t0p )
*t0p = r;
} else if (p > 0) {
r = (double)q / p;
if ( r < *t0p )
return FALSE;
if ( r < *t1p )
*t1p = r;
} else if (q < 0)
return FALSE;
return TRUE;
}
/*------------------------ C U T H E R E, T O O -----------------------*/