grunwald@uiucdcsb.UUCP (02/27/85)
The following file contains an implementation of the new line-clipping
algorithm presented in the Jan '84 Trans. on Graphics using the parametric
equation for the line to do the actual clipping. The routines return a boolean
value as to whether the line was rejected from the view-volume, and if it
was not rejected, it clips the points to the view column. Both the 2d and the
3d cases are given. A simple "fast check" for clipping to an integer-sized
view volume is also given. Using the later to determine if 2d cliping is
really needed seems to make for a considerable savings. The structure "Point"
is obvious, as is the "clip_struct".
I copy the points into local variables on the assumption that this is
faster than dereferencing the structure variables each time. I'm not sure that
this is true. I've tested this code on a Sun workstation and it works pretty
well. You'd be well advised to use an in-line version of the "check if we
need to clip" routine or it'll crawl.
-------------------------------------------------------------------------------
#include "0.h"
/*
* Line clipping algorithms as taken from ACM TOG Vol 3 No 1
*
* The bounding area for the X-Y plane is defined by the points
* (clip_xmin, clip_ymin) and (clip_xmax, clip_ymax).
*
* For the three-dimensional case, the hither plane corresponds to
* clip_zmin and the yon plan corresponds to clip_zmax
*/
#define FALSE 0
static int
clipt(p, q, t0, t1)
float p, q;
float *t0, *t1;
{
float r;
if (p < 0.0) {
r = q / p;
if (r > *t1)
return( FALSE );
else
if (r > *t0) *t0 = r;
}
else if ( p > 0.0 ) {
r = q / p;
if (r < *t0)
return( FALSE );
else
if (r < *t1) *t1 = r;
}
else
if (q < 0.0) return( FALSE );
return ( ! FALSE );
}
fastcheck2d(x0, y0, x1, y2, minx, maxx, miny, maxy)
int x0, y0;
int x1, y1;
int minx, maxx;
int miny, maxy;
{
/*
* Check for simple acceptance. Most line segments will fall into
* this catagory we should hope.
*/
return( x0 <= maxx && x0 >= minx &&
x1 <= maxx && x1 >= minx &&
y0 <= maxy && y0 >= miny &&
y1 <= maxy && y1 >= miny) ;
}
clip2d( p0, p1, clp )
struct Point *p0, *p1;
struct clip_struct *clp;
{
float t0, t1;
float deltax, deltay;
float lx0, ly0;
float lx1, ly1;
int isok = 0;
lx0 = p0 -> x; ly0 = p0 -> y;
lx1 = p1 -> x; ly1 = p1 -> y;
t0 = 0.0;
t1 = 1.0;
deltax = lx1 - lx0;
if ( clipt(-deltax, lx0 - (clp -> clip_xmin), &t0, &t1) &&
clipt(deltax, (clp -> clip_xmax) - lx0, &t0, &t1) ) {
deltay = ly1 - ly0;
if ( clipt( -deltay, ly0 - (clp -> clip_ymin), &t0, &t1) &&
clipt(deltay, (clp -> clip_ymax) - ly0, &t0, &t1) ) {
isok = 1;
if (t1 < 1.0) {
lx1 = lx0 + t1 * deltax;
ly1 = ly0 + t1 * deltay;
}
if (t0 > 0.0) {
lx0 = lx0 + t0 * deltax;
ly0 = ly0 + t0 * deltay;
}
}
}
p0 -> x = lx0; p0 -> y = ly0;
p1 -> x = lx1; p1 -> y = ly1;
return( isok );
}
clip3d( p0, p1, clp )
struct Point *p0, *p1;
struct clip_struct *clp;
{
float t0, t1;
float deltax, deltay, deltaz;
float lx0, ly0, lz0;
float lx1, ly1, lz1;
int isok = 0;
lx0 = p0 -> x; ly0 = p0 -> y; lz0 = p0 -> z;
lx1 = p1 -> x; ly1 = p1 -> y; lz1 = p1 -> z;
t0 = 0.0;
t1 = 1.0;
deltax = lx1 - lx0;
deltaz = lz1 - lz0;
if ( clipt( -deltax-deltaz, lx0 + lz0, &t0, &t1) &&
clipt(deltax - deltaz, lz0 - lx0, &t0, &t1) ) {
deltay = ly1 - ly0;
if ( clipt( -deltay-deltaz, ly0 + lz0, &t0, &t1) &&
clipt(deltay-deltaz, lz0 - ly0, &t0, &t1) ) {
if ( clipt( -deltaz, lz0 - clp -> clip_zmin, &t0, &t1) &&
clipt( deltaz, clp -> clip_zmax - lz0, &t0, &t1) ) {
isok = 1;
if (t1 < 1.0) {
lx1 = lx0 + t1 * deltax;
ly1 = ly0 + t1 * deltay;
lz1 = lz0 + t1 * deltaz;
}
if (t0 > 0.0) {
lx0 = lx0 + t0 * deltax;
ly0 = ly0 + t0 * deltay;
lz0 = lz0 + t0 * deltaz;
}
}
}
}
p0 -> x = lx0; p0 -> y = ly0; p0 -> z = lz0;
p1 -> x = lx1; p1 -> y = ly1; p1 -> z = lz1;
return( isok );
}