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-2001 Kevin Rosenberg
17 ** $Id: clip.cpp,v 1.8 2001/01/27 21:02:20 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 ******************************************************************************/
33 #include "ctsupport.h"
37 * clip_segment Clip against a segment of a circle
40 * clip_segment (x1, y1, x2, y2, u, v)
41 * double& x1,*y1,*x2,*y2 Endpoints of line
42 * double u,v Dimensions of segment
46 clip_segment (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
53 if (yc1 > 0. && yc2 > 0.) // reject lines above y-axis
56 double radius = sqrt (u * u + v * v);
58 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
61 if (yc1 > 0. && yc2 > 0.) // trivial reject above y-axis
66 xc1 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
68 } else if (yc2 > 0.) {
69 xc2 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
83 * clip_sector Clip a line against a sector of a circle
86 * clip_sector (x1, y1, x2, y2, u, v)
87 * double& x1,*y1,*x2,*y2 Endpoints of line
88 * double u,v Size of sector
92 clip_sector (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
99 double radius = sqrt (u * u + v * v);
101 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
104 if (clip_triangle (xc1, yc1, xc2, yc2, u, v, false) == false)
117 * clip_circle Clip a line against a circle
120 * clip_circle (x1,y1,x2,y2,cx,cy,radius,t1,t2)
121 * double& x1,*y1,*x2,*y2 Endpoints of line to be clipped
122 * double cx,cy Center of circle
123 * double radius Radius of circle
124 * double t1,t2 Starting & stopping angles of clipping
128 clip_circle (double& x1, double& y1, double& x2, double& y2, const double cx, const double cy, const double radius, double t1, double t2)
137 double xtrans = -xc1; // move (x1,y1) to origin
138 double ytrans = -yc1;
147 double theta = -atan2 (yc2, xc2); // rotate line to lie on x-axis
149 rot_mtx2 (rotmtx, theta); // xc1,yc1 is at origin, no need to rot
150 xform_mtx2 (rotmtx, xc2, yc2);
151 xform_mtx2 (rotmtx, ccx, ccy);
152 t1 += theta; // rotate start and stop angles
154 t1 = normalizeAngle (t1);
155 t2 = normalizeAngle (t2);
157 if (xc2 < -D_EPSILON || fabs(yc2) > F_EPSILON) {
158 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);
162 if (fabs(ccy) > radius) /* check if can reject */
165 double temp = sqrt (radius * radius - ccy * ccy);
166 double xcmin = ccx - temp;
167 double xcmax = ccx + temp;
169 if (fabs(t2 - t1) < D_EPSILON) {
174 } else if (t1 < t2) {
175 if (t1 < PI && t2 > PI)
178 } else if (t1 > t2) {
186 rot_mtx2 (rotmtx, -theta);
187 xform_mtx2 (rotmtx, xc1, yc1);
188 xform_mtx2 (rotmtx, xc2, yc2);
204 * clip_triangle Clip a line against a triangle
207 * clip_triangle (x1, y1, x2, y2, u, v, clip_xaxis)
208 * double& x1, *y1, *x2, *y2 Endpoints of line
209 * double u, v Size of 1/2 base len & height
210 * int clip_xaxis Boolean flag whether to clip against x axis
211 * (Use true for all triangles)
212 * (false if used internally by sector clipping routine)
216 * /|\ Note that vertices of triangle are
226 * 1) Inside of this routine, values of (u,v) are assumed to be (1,1)
228 * 2) Derivation of clipping equations:
229 * Using parametric equations for the line
230 * xv = x1 + t * (x2 - x1)
231 * yv = y1 + t * (y2 - y1)
233 * t = (xv - x1) / (x2 - x1)
234 * yv = y1 + (xv - x1) * (y2 - y1) / (x2 - x1)
235 * yv = y1 + (xv - x1) * dy / dx
237 * Now, find the intersections with the following clipping boundries:
238 * yv = v - (v/u) * xv (yv = mx + b)
239 * yv = v + (v/u) * xv (m = v/u, b = v);
242 static int tcode (const double x, const double y, const double m, const double b, const int clip_xaxis);
245 clip_triangle (double& x1, double& y1, double& x2, double& y2, const double u, const double v, const int clip_xaxis)
247 double m = v / u; // slope of triangle lines
248 double b = v; // y-intercept of triangle lines
250 int c1 = tcode (x1, y1, m, b, clip_xaxis);
251 int c2 = tcode (x2, y2, m, b, clip_xaxis);
254 printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d\n",
255 x1, y1, c1, x2, y2, c2);
259 return false; // trivial reject
266 if (c & 1) { // below
267 x = x1 + (x2-x1)*(0.0-y1)/(y2-y1);
269 } else if (c & 2) { // right
273 if (fabs(dx) > D_EPSILON)
274 x = (-y1 + b + x1 * dy/dx) / (m + dy/dx);
278 } else if (c & 4) { /* left */
282 if (fabs(dx) > D_EPSILON) {
283 x = (y1 - b - x1 * dy/dx);
291 x1=x; y1=y; c1=tcode (x1,y1,m,b,clip_xaxis);
293 x2=x; y2=y; c2=tcode (x2,y2,m,b,clip_xaxis);
296 printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d\n", x1, y1, c1, x2, y2, c2);
300 return true; /* we have clipped the line, and it is good */
304 /* compute region code */
306 tcode (const double x, const double y, const double m, const double b, const int clip_xaxis)
310 if (clip_xaxis && y < 0.) // below triange
313 if (y > -m * x + b + D_EPSILON) // right of triangle
315 if (y > m * x + b + D_EPSILON) // left of triangle
323 * clip_rect Clip a line against a rectangle
326 * clip_rect (x1, y1, x2, y2, rect)
327 * double& x1, *y1, *x2, *y2 Endpoints of line
328 * double rect[4] Rectangle to clip against
329 * ordered xmin, ymin, xmax, ymax
332 static int rectcode (double x, double y, const double rect[4]);
335 clip_rect (double& x1, double& y1, double& x2, double& y2, const double rect[4])
339 int c1 = rectcode (x1, y1, rect);
340 int c2 = rectcode (x2, y2, rect);
344 return false; // trivial reject
349 y = y1 + (y2-y1)*(rect[0]-x1)/(x2-x1);
351 } else if (c & 2) { // right
352 y = y1 + (y2-y1)*(rect[2]-x1)/(x2-x1);
354 } else if (c & 4) { // bottom
355 x = x1 + (x2-x1)*(rect[1]-y1)/(y2-y1);
357 } else if (c & 8) { // top
358 x = x1 + (x2-x1)*(rect[3]-y1)/(y2-y1);
363 x1=x; y1=y; c1=rectcode(x1,y1,rect);
365 x2=x; y2=y; c2=rectcode(x2,y2,rect);
368 return true; // we have clipped the line, and it is good
373 * rectcode INTERNAL routine to return position of
374 * point relative to a rectangle
377 * c = rectcode (x, y, rect)
378 * int c Position of point relative to the window
379 * double x, y Point to test against window
380 * double rect[4] Coordinates of rectangle extent
381 * Ordered [xmin, ymin, xmax, ymax]
385 rectcode (double x, double y, const double rect[4])
391 else if (x > rect[2])
395 else if (y > rect[3])