Debian Codegraph @

libctsupport/clip.cpp

raw
1 /*****************************************************************************
2 ** FILE IDENTIFICATION
3 **
4 ** Name: clip.c
5 ** Purpose: Line clipping routines
6 ** Programmer: Kevin Rosenberg
7 ** Date Started: 1984
8 **
9 ** OVERVIEW
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)
13 **
14 ** This is part of the CTSim program
15 ** Copyright (c) 1983-2009 Kevin Rosenberg
16 **
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.
20 **
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.
25 **
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 ******************************************************************************/
30
31 #include "ctsupport.h"
32
33
34 /* NAME
35 * clip_segment Clip against a segment of a circle
36 *
37 * SYNOPSIS
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
41 */
42
43 bool
44 clip_segment (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
45 {
46 double xc1 = x1 * u;
47 double yc1 = y1 * v;
48 double xc2 = x2 * u;
49 double yc2 = y2 * v;
50
51 if (yc1 > 0. && yc2 > 0.) // reject lines above y-axis
52 return false;
53
54 double radius = sqrt (u * u + v * v);
55
56 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
57 return false;
58
59 if (yc1 > 0. && yc2 > 0.) // trivial reject above y-axis
60 return false;
61
62 // clip above x-axis
63 if (yc1 > 0.) {
64 xc1 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
65 yc1 = 0.0;
66 } else if (yc2 > 0.) {
67 xc2 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
68 yc2 = 0.0;
69 }
70
71 x1 = xc1 / u;
72 y1 = yc1 / v;
73 x2 = xc2 / u;
74 y2 = yc2 / v;
75
76 return true;
77 }
78
79
80 /* NAME
81 * clip_sector Clip a line against a sector of a circle
82 *
83 * SYNOPSIS
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
87 */
88
89 bool
90 clip_sector (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
91 {
92 double xc1 = x1 * u;
93 double yc1 = y1 * v;
94 double xc2 = x2 * u;
95 double yc2 = y2 * v;
96
97 double radius = sqrt (u * u + v * v);
98
99 if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
100 return false;
101
102 if (clip_triangle (xc1, yc1, xc2, yc2, u, v, false) == false)
103 return false;
104
105 x1 = xc1 / u;
106 y1 = yc1 / v;
107 x2 = xc2 / u;
108 y2 = yc2 / v;
109
110 return true;
111 }
112
113
114 /* NAME
115 * clip_circle Clip a line against a circle
116 *
117 * SYNOPSIS
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
123 */
124
125 bool
126 clip_circle (double& x1, double& y1, double& x2, double& y2, const double cx, const double cy, const double radius, double t1, double t2)
127 {
128 double xc1 = x1;
129 double yc1 = y1;
130 double xc2 = x2;
131 double yc2 = y2;
132 double ccx = cx;
133 double ccy = cy;
134
135 double xtrans = -xc1; // move (x1,y1) to origin
136 double ytrans = -yc1;
137
138 xc1 += xtrans;
139 yc1 += ytrans;
140 xc2 += xtrans;
141 yc2 += ytrans;
142 ccx += xtrans;
143 ccy += ytrans;
144
145 double theta = -atan2 (yc2, xc2); // rotate line to lie on x-axis
146 GRFMTX_2D rotmtx;
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
151 t2 += theta;
152 t1 = normalizeAngle (t1);
153 t2 = normalizeAngle (t2);
154
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);
157 return false;
158 }
159
160 if (fabs(ccy) > radius) /* check if can reject */
161 return false;
162
163 double temp = sqrt (radius * radius - ccy * ccy);
164 double xcmin = ccx - temp;
165 double xcmax = ccx + temp;
166
167 if (fabs(t2 - t1) < D_EPSILON) {
168 if (xc1 < xcmin)
169 xc1 = xcmin;
170 if (xc2 > xcmax)
171 xc2 = xcmax;
172 } else if (t1 < t2) {
173 if (t1 < PI && t2 > PI)
174 if (xc1 < xcmin)
175 xc1 = xcmin;
176 } else if (t1 > t2) {
177 if (t1 < PI)
178 if (xc1 < xcmin)
179 xc1 = xcmin;
180 if (xc2 > xcmax)
181 xc2 = xcmax;
182 }
183
184 rot_mtx2 (rotmtx, -theta);
185 xform_mtx2 (rotmtx, xc1, yc1);
186 xform_mtx2 (rotmtx, xc2, yc2);
187 xc1 += -xtrans;
188 yc1 += -ytrans;
189 xc2 += -xtrans;
190 yc2 += -ytrans;
191
192 x1 = xc1;
193 y1 = yc1;
194 x2 = xc2;
195 y2 = yc2;
196
197 return true;
198 }
199
200
201 /* NAME
202 * clip_triangle Clip a line against a triangle
203 *
204 * SYNOPSIS
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)
211 *
212 * DESCRIPTION
213 * x
214 * /|\ Note that vertices of triangle are
215 * / | \ (-u, 0)
216 * / | \ (u, 0)
217 * / | \ (0, v)
218 * / | v \
219 * / | \
220 * +------+------+
221 * (0,0) u
222 *
223 * NOTES
224 * 1) Inside of this routine, values of (u,v) are assumed to be (1,1)
225 *
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)
230 * so,
231 * t = (xv - x1) / (x2 - x1)
232 * yv = y1 + (xv - x1) * (y2 - y1) / (x2 - x1)
233 * yv = y1 + (xv - x1) * dy / dx
234 *
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);
238 */
239
240 static int tcode (const double x, const double y, const double m, const double b, const int clip_xaxis);
241
242 bool
243 clip_triangle (double& x1, double& y1, double& x2, double& y2, const double u, const double v, const int clip_xaxis)
244 {
245 double m = v / u; // slope of triangle lines
246 double b = v; // y-intercept of triangle lines
247
248 int c1 = tcode (x1, y1, m, b, clip_xaxis);
249 int c2 = tcode (x2, y2, m, b, clip_xaxis);
250
251 #if 0
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);
253 #endif
254 while ( c1 || c2 ) {
255 if ( c1 & c2 ) {
256 return false; // trivial reject
257 }
258 int c = c1;
259 if (c1 == 0)
260 c = c2;
261
262 double x = 0, y = 0;
263 if (c & 1) { // below
264 x = x1 + (x2-x1)*(0.0-y1)/(y2-y1);
265 y = 0.0;
266 } else if (c & 2) { // right
267 double dx, dy;
268 dx = x2 - x1;
269 dy = y2 - y1;
270 if (fabs(dx) > D_EPSILON)
271 x = (-y1 + b + x1 * dy/dx) / (m + dy/dx);
272 else
273 x = x1;
274 y = -m * x + b;
275 } else if (c & 4) { /* left */
276 double dx, dy;
277 dx = x2 - x1;
278 dy = y2 - y1;
279 if (fabs(dx) > D_EPSILON) {
280 x = (y1 - b - x1 * dy/dx);
281 x /= (m - dy/dx);
282 } else
283 x = x1;
284 y = m * x + b;
285 }
286
287 if (c == c1) {
288 x1=x; y1=y; c1=tcode (x1,y1,m,b,clip_xaxis);
289 } else {
290 x2=x; y2=y; c2=tcode (x2,y2,m,b,clip_xaxis);
291 }
292 #if 0
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);
294 #endif
295 }
296
297 return true; /* we have clipped the line, and it is good */
298 }
299
300
301 /* compute region code */
302 static int
303 tcode (const double x, const double y, const double m, const double b, const int clip_xaxis)
304 {
305 int c = 0;
306
307 if (clip_xaxis && y < 0.) // below triange
308 c = 1;
309
310 if (y > -m * x + b + D_EPSILON) // right of triangle
311 c += 2;
312 if (y > m * x + b + D_EPSILON) // left of triangle
313 c += 4;
314
315 return (c);
316 }
317
318
319 /* NAME
320 * clip_rect Clip a line against a rectangle
321 *
322 * SYNOPSIS
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
327 */
328
329 static int rectcode (double x, double y, const double rect[4]);
330
331 bool
332 clip_rect (double& x1, double& y1, double& x2, double& y2, const double rect[4])
333 {
334 double x = 0, y = 0;
335
336 int c1 = rectcode (x1, y1, rect);
337 int c2 = rectcode (x2, y2, rect);
338
339 while (c1 || c2) {
340 if (c1 & c2)
341 return false; // trivial reject
342 int c = c1;
343 if (c1 == 0)
344 c = c2;
345 if (c & 1) { // left
346 y = y1 + (y2-y1)*(rect[0]-x1)/(x2-x1);
347 x = rect[0];
348 } else if (c & 2) { // right
349 y = y1 + (y2-y1)*(rect[2]-x1)/(x2-x1);
350 x = rect[2];
351 } else if (c & 4) { // bottom
352 x = x1 + (x2-x1)*(rect[1]-y1)/(y2-y1);
353 y = rect[1];
354 } else if (c & 8) { // top
355 x = x1 + (x2-x1)*(rect[3]-y1)/(y2-y1);
356 y = rect[3];
357 }
358
359 if (c == c1) {
360 x1=x; y1=y; c1=rectcode(x1,y1,rect);
361 } else {
362 x2=x; y2=y; c2=rectcode(x2,y2,rect);
363 }
364 }
365 return true; // we have clipped the line, and it is good
366 }
367
368
369 /* NAME
370 * rectcode INTERNAL routine to return position of
371 * point relative to a rectangle
372 *
373 * SYNOPSIS
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]
379 */
380
381 static int
382 rectcode (double x, double y, const double rect[4])
383 {
384 int c = 0;
385
386 if (x < rect[0])
387 c = 1;
388 else if (x > rect[2])
389 c = 2;
390 if (y < rect[1])
391 c += 4;
392 else if (y > rect[3])
393 c += 8;
394 return (c);
395 }