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-2009 Kevin Rosenberg
17 ** This program is free software; you can redistribute it and/or modify
18 ** it under the terms of the GNU General Public License (version 2) as
19 ** published by the Free Software Foundation.
21 ** This program is distributed in the hope that it will be useful,
22 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
23 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 ** GNU General Public License for more details.
26 ** You should have received a copy of the GNU General Public License
27 ** along with this program; if not, write to the Free Software
28 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
29 ******************************************************************************/
31 #include "ctsupport.h"
35 * clip_segment Clip against a segment of a circle
38 * clip_segment (x1, y1, x2, y2, u, v)
39 * double& x1,*y1,*x2,*y2 Endpoints of line
40 * double u,v Dimensions of segment
44 clip_segment (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
51 if (yc1 > 0. && yc2 > 0.) // reject lines above y-axis
54 double radius = sqrt (u * u + v * v);
56 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
59 if (yc1 > 0. && yc2 > 0.) // trivial reject above y-axis
64 xc1 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
66 } else if (yc2 > 0.) {
67 xc2 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
81 * clip_sector Clip a line against a sector of a circle
84 * clip_sector (x1, y1, x2, y2, u, v)
85 * double& x1,*y1,*x2,*y2 Endpoints of line
86 * double u,v Size of sector
90 clip_sector (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
97 double radius = sqrt (u * u + v * v);
99 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
102 if (clip_triangle (xc1, yc1, xc2, yc2, u, v, false) == false)
115 * clip_circle Clip a line against a circle
118 * clip_circle (x1,y1,x2,y2,cx,cy,radius,t1,t2)
119 * double& x1,*y1,*x2,*y2 Endpoints of line to be clipped
120 * double cx,cy Center of circle
121 * double radius Radius of circle
122 * double t1,t2 Starting & stopping angles of clipping
126 clip_circle (double& x1, double& y1, double& x2, double& y2, const double cx, const double cy, const double radius, double t1, double t2)
135 double xtrans = -xc1; // move (x1,y1) to origin
136 double ytrans = -yc1;
145 double theta = -atan2 (yc2, xc2); // rotate line to lie on x-axis
147 rot_mtx2 (rotmtx, theta); // xc1,yc1 is at origin, no need to rot
148 xform_mtx2 (rotmtx, xc2, yc2);
149 xform_mtx2 (rotmtx, ccx, ccy);
150 t1 += theta; // rotate start and stop angles
152 t1 = normalizeAngle (t1);
153 t2 = normalizeAngle (t2);
155 if (xc2 < -D_EPSILON || fabs(yc2) > F_EPSILON) {
156 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);
160 if (fabs(ccy) > radius) /* check if can reject */
163 double temp = sqrt (radius * radius - ccy * ccy);
164 double xcmin = ccx - temp;
165 double xcmax = ccx + temp;
167 if (fabs(t2 - t1) < D_EPSILON) {
172 } else if (t1 < t2) {
173 if (t1 < PI && t2 > PI)
176 } else if (t1 > t2) {
184 rot_mtx2 (rotmtx, -theta);
185 xform_mtx2 (rotmtx, xc1, yc1);
186 xform_mtx2 (rotmtx, xc2, yc2);
202 * clip_triangle Clip a line against a triangle
205 * clip_triangle (x1, y1, x2, y2, u, v, clip_xaxis)
206 * double& x1, *y1, *x2, *y2 Endpoints of line
207 * double u, v Size of 1/2 base len & height
208 * int clip_xaxis Boolean flag whether to clip against x axis
209 * (Use true for all triangles)
210 * (false if used internally by sector clipping routine)
214 * /|\ Note that vertices of triangle are
224 * 1) Inside of this routine, values of (u,v) are assumed to be (1,1)
226 * 2) Derivation of clipping equations:
227 * Using parametric equations for the line
228 * xv = x1 + t * (x2 - x1)
229 * yv = y1 + t * (y2 - y1)
231 * t = (xv - x1) / (x2 - x1)
232 * yv = y1 + (xv - x1) * (y2 - y1) / (x2 - x1)
233 * yv = y1 + (xv - x1) * dy / dx
235 * Now, find the intersections with the following clipping boundries:
236 * yv = v - (v/u) * xv (yv = mx + b)
237 * yv = v + (v/u) * xv (m = v/u, b = v);
240 static int tcode (const double x, const double y, const double m, const double b, const int clip_xaxis);
243 clip_triangle (double& x1, double& y1, double& x2, double& y2, const double u, const double v, const int clip_xaxis)
245 double m = v / u; // slope of triangle lines
246 double b = v; // y-intercept of triangle lines
248 int c1 = tcode (x1, y1, m, b, clip_xaxis);
249 int c2 = tcode (x2, y2, m, b, clip_xaxis);
252 printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d\n", x1, y1, c1, x2, y2, c2);
256 return false; // trivial reject
263 if (c & 1) { // below
264 x = x1 + (x2-x1)*(0.0-y1)/(y2-y1);
266 } else if (c & 2) { // right
270 if (fabs(dx) > D_EPSILON)
271 x = (-y1 + b + x1 * dy/dx) / (m + dy/dx);
275 } else if (c & 4) { /* left */
279 if (fabs(dx) > D_EPSILON) {
280 x = (y1 - b - x1 * dy/dx);
288 x1=x; y1=y; c1=tcode (x1,y1,m,b,clip_xaxis);
290 x2=x; y2=y; c2=tcode (x2,y2,m,b,clip_xaxis);
293 printf ("x1:%6.2f y1:%6.2f code1:%2d x2:%6.2f y2:%6.2f code2:%2d\n", x1, y1, c1, x2, y2, c2);
297 return true; /* we have clipped the line, and it is good */
301 /* compute region code */
303 tcode (const double x, const double y, const double m, const double b, const int clip_xaxis)
307 if (clip_xaxis && y < 0.) // below triange
310 if (y > -m * x + b + D_EPSILON) // right of triangle
312 if (y > m * x + b + D_EPSILON) // left of triangle
320 * clip_rect Clip a line against a rectangle
323 * clip_rect (x1, y1, x2, y2, rect)
324 * double& x1, *y1, *x2, *y2 Endpoints of line
325 * double rect[4] Rectangle to clip against
326 * ordered xmin, ymin, xmax, ymax
329 static int rectcode (double x, double y, const double rect[4]);
332 clip_rect (double& x1, double& y1, double& x2, double& y2, const double rect[4])
336 int c1 = rectcode (x1, y1, rect);
337 int c2 = rectcode (x2, y2, rect);
341 return false; // trivial reject
346 y = y1 + (y2-y1)*(rect[0]-x1)/(x2-x1);
348 } else if (c & 2) { // right
349 y = y1 + (y2-y1)*(rect[2]-x1)/(x2-x1);
351 } else if (c & 4) { // bottom
352 x = x1 + (x2-x1)*(rect[1]-y1)/(y2-y1);
354 } else if (c & 8) { // top
355 x = x1 + (x2-x1)*(rect[3]-y1)/(y2-y1);
360 x1=x; y1=y; c1=rectcode(x1,y1,rect);
362 x2=x; y2=y; c2=rectcode(x2,y2,rect);
365 return true; // we have clipped the line, and it is good
370 * rectcode INTERNAL routine to return position of
371 * point relative to a rectangle
374 * c = rectcode (x, y, rect)
375 * int c Position of point relative to the window
376 * double x, y Point to test against window
377 * double rect[4] Coordinates of rectangle extent
378 * Ordered [xmin, ymin, xmax, ymax]
382 rectcode (double x, double y, const double rect[4])
388 else if (x > rect[2])
392 else if (y > rect[3])