kcp@bmcg.UUCP (Kenneth Pao) (02/28/85)
I ran across this 2D and 3D line clipping routine in net.sources the other day. I thought some of you in this group may find it useful. Also I would like to ask whether someone in net.graphics could point me to some references about clipping general elliptic arcs. Thanks in advance. From sdcc6!sdcc3!sdcsvax!dcdwest!ittvax!decvax!bellcore!allegra!ulysses!mhuxr!ihnp4!inuxc!pur-ee!uiucdcsb!grunwald Article 2099 of net.sources: ion: version B 2.10.2 9/18/84; site bmcg.UUCP Posting-Version: Notesfiles $Revision: 1.6.2.17 $; site uiucdcsb.UUCP Path: bmcg!sdcc6!sdcc3!sdcsvax!dcdwest!ittvax!decvax!bellcore!allegra!ulysses!mhuxr!ihnp4!inuxc!pur-ee!uiucdcsb!grunwald >From: grunwald@uiucdcsb.UUCP Newsgroups: net.sources Subject: 2d, 3d clipping Message-ID: <15400008@uiucdcsb.UUCP> Date: 27 Feb 85 05:32:00 GMT Date-Received: 24 Feb 85 05:07:37 GMT Lines: 174 Nf-ID: #N:uiucdcsb:15400008:000:4082 Nf-From: uiucdcsb!grunwald Feb 19 23:32:00 1985 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 ); }