1 /*****************************************************************************
5 ** Purpose: Line clipping routines
6 ** Programmer: Kevin Rosenberg
10 ** Routines to clip lines against objects
11 ** All routines get the endpoints of the line, and
12 ** the SNARK size of the object (u,v)
14 ** This is part of the CTSim program
15 ** Copyright (C) 1983-2000 Kevin Rosenberg
17 ** $Id: clip.cpp,v 1.1 2000/06/19 02:58:08 kevin Exp $
19 ** This program is free software; you can redistribute it and/or modify
20 ** it under the terms of the GNU General Public License (version 2) as
21 ** published by the Free Software Foundation.
23 ** This program is distributed in the hope that it will be useful,
24 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
25 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 ** GNU General Public License for more details.
28 ** You should have received a copy of the GNU General Public License
29 ** along with this program; if not, write to the Free Software
30 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
31 ******************************************************************************/
38 * clip_segment Clip against a segment of a circle
41 * clip_segment (x1, y1, x2, y2, u, v)
42 * double& x1,*y1,*x2,*y2 Endpoints of line
43 * double u,v Dimensions of segment
47 clip_segment (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
54 if (yc1 > 0. && yc2 > 0.) // reject lines above y-axis
57 double radius = sqrt (u * u + v * v);
59 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
62 if (yc1 > 0. && yc2 > 0.) // trivial reject above y-axis
67 xc1 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
69 } else if (yc2 > 0.) {
70 xc2 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
84 * clip_sector Clip a line against a sector of a circle
87 * clip_sector (x1, y1, x2, y2, u, v)
88 * double& x1,*y1,*x2,*y2 Endpoints of line
89 * double u,v Size of sector
93 clip_sector (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
100 double radius = sqrt (u * u + v * v);
102 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
105 if (clip_triangle (xc1, yc1, xc2, yc2, u, v, false) == false)
118 * clip_circle Clip a line against a circle
121 * clip_circle (x1,y1,x2,y2,cx,cy,radius,t1,t2)
122 * double& x1,*y1,*x2,*y2 Endpoints of line to be clipped
123 * double cx,cy Center of circle
124 * double radius Radius of circle
125 * double t1,t2 Starting & stopping angles of clipping
129 clip_circle (double& x1, double& y1, double& x2, double& y2, const double cx, const double cy, const double radius, double t1, double t2)
138 double xtrans = -xc1; // move (x1,y1) to origin
139 double ytrans = -yc1;
148 double theta = -atan2 (yc2, xc2); // rotate line to lie on x-axis
150 rot_mtx2 (rotmtx, theta); // xc1,yc1 is at origin, no need to rot
151 xform_mtx2 (rotmtx, xc2, yc2);
152 xform_mtx2 (rotmtx, ccx, ccy);
153 t1 += theta; // rotate start and stop angles
158 if (xc2 < -D_EPSILON || fabs(yc2) > F_EPSILON) {
159 sys_error (ERR_SEVERE, "Internal error in clip_circle\n x1=%6.2f, y1=%6.2f, x2=%6.2f, y2=%6.2f, xc2=%6.2f, yc2=%6.2f, theta=%6.2f", x1, y1, x2, y2, xc2, yc2, theta);
163 if (fabs(ccy) > radius) /* check if can reject */
166 double temp = sqrt (radius * radius - ccy * ccy);
167 double xcmin = ccx - temp;
168 double xcmax = ccx + temp;
170 if (fabs(t2 - t1) < D_EPSILON) {
175 } else if (t1 < t2) {
176 if (t1 < PI && t2 > PI)
179 } else if (t1 > t2) {
187 rot_mtx2 (rotmtx, -theta);
188 xform_mtx2 (rotmtx, xc1, yc1);
189 xform_mtx2 (rotmtx, xc2, yc2);
205 * clip_triangle Clip a line against a triangle
208 * clip_triangle (x1, y1, x2, y2, u, v, clip_xaxis)
209 * double& x1, *y1, *x2, *y2 Endpoints of line
210 * double u, v Size of 1/2 base len & height
211 * int clip_xaxis Boolean flag whether to clip against x axis
212 * (Use true for all triangles)
213 * (false if used internally by sector clipping routine)
217 * /|\ Note that vertices of triangle are
227 * 1) Inside of this routine, values of (u,v) are assumed to be (1,1)
229 * 2) Derivation of clipping equations:
230 * Using parametric equations for the line
231 * xv = x1 + t * (x2 - x1)
232 * yv = y1 + t * (y2 - y1)
234 * t = (xv - x1) / (x2 - x1)
235 * yv = y1 + (xv - x1) * (y2 - y1) / (x2 - x1)
236 * yv = y1 + (xv - x1) * dy / dx
238 * Now, find the intersections with the following clipping boundries:
239 * yv = v - (v/u) * xv (yv = mx + b)
240 * yv = v + (v/u) * xv (m = v/u, b = v);
243 static int tcode (const double x, const double y, const double m, const double b, const int clip_xaxis);
246 clip_triangle (double& x1, double& y1, double& x2, double& y2, const double u, const double v, const int clip_xaxis)
248 double m = v / u; // slope of triangle lines
249 double b = v; // y-intercept of triangle lines
251 int c1 = tcode (x1, y1, m, b, clip_xaxis);
252 int c2 = tcode (x2, y2, m, b, clip_xaxis);
256 printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d",
257 x1, y1, c1, x2, y2, c2);
261 return false; // trivial reject
268 if (c & 1) { // below
269 x = x1 + (x2-x1)*(0.0-y1)/(y2-y1);
271 } else if (c & 2) { // right
275 if (fabs(dx) > D_EPSILON)
276 x = (-y1 + b + x1 * dy/dx) / (m + dy/dx);
280 } else if (c & 4) { /* left */
284 if (fabs(dx) > D_EPSILON) {
285 x = (y1 - b - x1 * dy/dx);
293 x1=x; y1=y; c1=tcode (x1,y1,m,b,clip_xaxis);
295 x2=x; y2=y; c2=tcode (x2,y2,m,b,clip_xaxis);
299 printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d", x1, y1, c1, x2, y2, c2);
303 return true; /* we have clipped the line, and it is good */
307 /* compute region code */
309 tcode (const double x, const double y, const double m, const double b, const int clip_xaxis)
313 if (clip_xaxis && y < 0.) // below triange
316 if (y > -m * x + b + D_EPSILON) // right of triangle
318 if (y > m * x + b + D_EPSILON) // left of triangle
326 * clip_rect Clip a line against a rectangle
329 * clip_rect (x1, y1, x2, y2, rect)
330 * double& x1, *y1, *x2, *y2 Endpoints of line
331 * double rect[4] Rectangle to clip against
332 * ordered xmin, ymin, xmax, ymax
335 static int rectcode (double x, double y, const double rect[4]);
338 clip_rect (double& x1, double& y1, double& x2, double& y2, const double rect[4])
342 int c1 = rectcode (x1, y1, rect);
343 int c2 = rectcode (x2, y2, rect);
347 return false; // trivial reject
352 y = y1 + (y2-y1)*(rect[0]-x1)/(x2-x1);
354 } else if (c & 2) { // right
355 y = y1 + (y2-y1)*(rect[2]-x1)/(x2-x1);
357 } else if (c & 4) { // bottom
358 x = x1 + (x2-x1)*(rect[1]-y1)/(y2-y1);
360 } else if (c & 8) { // top
361 x = x1 + (x2-x1)*(rect[3]-y1)/(y2-y1);
366 x1=x; y1=y; c1=rectcode(x1,y1,rect);
368 x2=x; y2=y; c2=rectcode(x2,y2,rect);
371 return true; // we have clipped the line, and it is good
376 * rectcode INTERNAL routine to return position of
377 * point relative to a rectangle
380 * c = rectcode (x, y, rect)
381 * int c Position of point relative to the window
382 * double x, y Point to test against window
383 * double rect[4] Coordinates of rectangle extent
384 * Ordered [xmin, ymin, xmax, ymax]
388 rectcode (double x, double y, const double rect[4])
394 else if (x > rect[2])
398 else if (y > rect[3])