1 /* This file is part of the GNU plotutils package. Copyright (C) 1995,
2 1996, 1997, 1998, 1999, 2000, 2005, 2008, Free Software Foundation, Inc.
3
4 The GNU plotutils package is free software. You may redistribute it
5 and/or modify it under the terms of the GNU General Public License as
6 published by the Free Software foundation; either version 2, or (at your
7 option) any later version.
8
9 The GNU plotutils package is distributed in the hope that it will be
10 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with the GNU plotutils package; see the file COPYING. If not, write to
16 the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
17 Boston, MA 02110-1301, USA. */
18
19 /* This file contains functions that update the bounding box information
20 for a page whenever a new object (ellipse, line segment, or Bezier
21 segment) is plotted. Updating takes the line width into account, more
22 or less. The bounding box information is stored in terms of device
23 units, in the page's plOutbuf structure. */
24
25 #include "sys-defines.h"
26 #include "extern.h"
27
28 #define VLENGTH(v) sqrt( (v).x * (v).x + (v).y * (v).y )
29
30 /* update bounding box due to drawing of ellipse (args are in user coors) */
31
32 /* WARNING: This is not completely accurate, due to the nonzero width of
33 the pen used to draw the ellipse. Notoriously, the outer boundary of a
34 `wide ellipse' isn't an ellipse at all: in general it's an eighth-order
35 curve (see Foley and van Damm), though it's a fourth-order curve if the
36 axes are aligned with the coordinate axes. Here we approximate it as an
37 ellipse, with semimajor and semiminor axes in the user frame increased
38 by one-half of the line width. This approximation is good unless the
39 line width is large. */
40 void
_set_ellipse_bbox(plOutbuf * bufp,double x,double y,double rx,double ry,double costheta,double sintheta,double linewidth,double m[6])41 _set_ellipse_bbox (plOutbuf *bufp, double x, double y, double rx, double ry, double costheta, double sintheta, double linewidth, double m[6])
42 {
43 double ux, uy, vx, vy;
44 double mixing_angle;
45 double semi_axis_1_x, semi_axis_1_y, semi_axis_2_x, semi_axis_2_y;
46 double rx_device, ry_device;
47 double theta_device, costheta_device, sintheta_device;
48 double xdeviation, ydeviation;
49
50 /* take user-frame line width into account (approximately! see above) */
51 rx += 0.5 * linewidth;
52 ry += 0.5 * linewidth;
53
54 /* perform affine user->device coor transformation; (ux,uy) and (vx,vy)
55 are forward images of the semiaxes, i.e. they are conjugate radial
56 vectors in the device frame */
57
58 ux = XDV_INTERNAL(rx * costheta, rx * sintheta, m);
59 uy = YDV_INTERNAL(rx * costheta, rx * sintheta, m);
60
61 vx = XDV_INTERNAL(-ry * sintheta, ry * costheta, m);
62 vy = YDV_INTERNAL(-ry * sintheta, ry * costheta, m);
63
64 /* angle by which the conjugate radial vectors should be mixed, in order
65 to yield vectors along the major and minor axes in the device frame */
66 mixing_angle = 0.5 * _xatan2 (2.0 * (ux * vx + uy * vy),
67 ux * ux + uy * uy - vx * vx + vy * vy);
68
69 /* semi-axis vectors in device coordinates */
70 semi_axis_1_x = ux * cos(mixing_angle) + vx * sin(mixing_angle);
71 semi_axis_1_y = uy * cos(mixing_angle) + vy * sin(mixing_angle);
72 semi_axis_2_x = ux * cos(mixing_angle + M_PI_2)
73 + vx * sin(mixing_angle + M_PI_2);
74 semi_axis_2_y = uy * cos(mixing_angle + M_PI_2)
75 + vy * sin(mixing_angle + M_PI_2);
76
77 /* semi-axis lengths in device coordinates */
78 rx_device = sqrt (semi_axis_1_x * semi_axis_1_x
79 + semi_axis_1_y * semi_axis_1_y);
80 ry_device = sqrt (semi_axis_2_x * semi_axis_2_x
81 + semi_axis_2_y * semi_axis_2_y);
82
83 /* angle of inclination of the first semi-axis, in device frame */
84 theta_device = - _xatan2 (semi_axis_1_y, semi_axis_1_x);
85 costheta_device = cos (theta_device);
86 sintheta_device = sin (theta_device);
87
88 /* maximum displacement in horizontal and vertical directions
89 while drawing ellipse, in device frame */
90 xdeviation = sqrt (rx_device * rx_device * costheta_device * costheta_device
91 + ry_device * ry_device * sintheta_device * sintheta_device);
92 ydeviation = sqrt (rx_device * rx_device * sintheta_device * sintheta_device
93 + ry_device * ry_device * costheta_device * costheta_device);
94
95 /* record these displacements, for bounding box */
96 _update_bbox (bufp,
97 XD_INTERNAL(x,y,m) + xdeviation,
98 YD_INTERNAL(x,y,m) + ydeviation);
99 _update_bbox (bufp,
100 XD_INTERNAL(x,y,m) + xdeviation,
101 YD_INTERNAL(x,y,m) - ydeviation);
102 _update_bbox (bufp,
103 XD_INTERNAL(x,y,m) - xdeviation,
104 YD_INTERNAL(x,y,m) + ydeviation);
105 _update_bbox (bufp,
106 XD_INTERNAL(x,y,m) - xdeviation,
107 YD_INTERNAL(x,y,m) - ydeviation);
108 }
109
110 /* update bounding box due to drawing of a line end (args are in user coors) */
111 void
_set_line_end_bbox(plOutbuf * bufp,double x,double y,double xother,double yother,double linewidth,int capstyle,double m[6])112 _set_line_end_bbox (plOutbuf *bufp, double x, double y, double xother, double yother, double linewidth, int capstyle, double m[6])
113 {
114 plVector v, vrot;
115 double xs, ys;
116 double halfwidth = 0.5 * linewidth;
117
118 switch (capstyle)
119 {
120 case PL_CAP_BUTT:
121 default:
122 vrot.x = yother - y;
123 vrot.y = x - xother;
124 _vscale (&vrot, halfwidth);
125 xs = x + vrot.x;
126 ys = y + vrot.y;
127 _update_bbox (bufp, XD_INTERNAL(xs,ys,m), YD_INTERNAL(xs,ys,m));
128 xs = x - vrot.x;
129 ys = y - vrot.y;
130 _update_bbox (bufp, XD_INTERNAL(xs,ys,m), YD_INTERNAL(xs,ys,m));
131 break;
132 case PL_CAP_PROJECT:
133 v.x = xother - x;
134 v.y = yother - y;
135 _vscale (&v, halfwidth);
136 vrot.x = yother - y;
137 vrot.y = x - xother;
138 _vscale (&vrot, halfwidth);
139 xs = x - v.x + vrot.x;
140 ys = y - v.y + vrot.y;
141 _update_bbox (bufp, XD_INTERNAL(xs,ys,m), YD_INTERNAL(xs,ys,m));
142 xs = x - v.x - vrot.x;
143 ys = y - v.y - vrot.y;
144 _update_bbox (bufp, XD_INTERNAL(xs,ys,m), YD_INTERNAL(xs,ys,m));
145 break;
146 case PL_CAP_ROUND:
147 _set_ellipse_bbox (bufp, x, y, halfwidth, halfwidth, 1.0, 0.0, 0.0, m);
148 break;
149 case PL_CAP_TRIANGULAR:
150 /* add projecting vertex */
151 v.x = xother - x;
152 v.y = yother - y;
153 _vscale (&v, halfwidth);
154 xs = x + v.x;
155 ys = y + v.y;
156 _update_bbox (bufp, XD_INTERNAL(xs,ys,m), YD_INTERNAL(xs,ys,m));
157 /* add other two vertices */
158 vrot.x = yother - y;
159 vrot.y = x - xother;
160 _vscale (&vrot, halfwidth);
161 xs = x + vrot.x;
162 ys = y + vrot.y;
163 _update_bbox (bufp, XD_INTERNAL(xs,ys,m), YD_INTERNAL(xs,ys,m));
164 xs = x - vrot.x;
165 ys = y - vrot.y;
166 _update_bbox (bufp, XD_INTERNAL(xs,ys,m), YD_INTERNAL(xs,ys,m));
167 break;
168 }
169 }
170
171 /* update bounding box due to drawing of a line join (args are in user coors)*/
172 void
_set_line_join_bbox(plOutbuf * bufp,double xleft,double yleft,double x,double y,double xright,double yright,double linewidth,int joinstyle,double miterlimit,double m[6])173 _set_line_join_bbox (plOutbuf *bufp, double xleft, double yleft, double x, double y, double xright, double yright, double linewidth, int joinstyle, double miterlimit, double m[6])
174 {
175 plVector v1, v2, vsum;
176 double v1len, v2len;
177 double halfwidth;
178 double mitrelen;
179
180 switch (joinstyle)
181 {
182 case PL_JOIN_MITER:
183 default:
184 v1.x = xleft - x;
185 v1.y = yleft - y;
186 v2.x = xright - x;
187 v2.y = yright - y;
188 v1len = VLENGTH(v1);
189 v2len = VLENGTH(v2);
190 if (v1len == 0.0 || v2len == 0.0)
191 _update_bbox (bufp, XD_INTERNAL(x,y,m), YD_INTERNAL(x,y,m));
192 else
193 {
194 double cosphi;
195
196 /* The maximum value the cosine of the angle between two joining
197 lines may have, if the join is to be mitered rather than
198 beveled, is 1-2/(M*M), where M is the mitrelimit. This is
199 because M equals the cosecant of one-half the minimum angle. */
200 cosphi = ((v1.x * v2.x + v1.y * v2.y) / v1len) / v2len;
201 if (miterlimit <= 1.0
202 || (cosphi > (1.0 - 2.0 / (miterlimit * miterlimit))))
203 /* bevel rather than miter */
204 {
205 _set_line_end_bbox (bufp, x, y, xleft, yleft, linewidth, PL_CAP_BUTT, m);
206 _set_line_end_bbox (bufp,x, y, xright, yright, linewidth, PL_CAP_BUTT, m);
207 }
208 else
209 {
210 mitrelen = sqrt (1.0 / (2.0 - 2.0 * cosphi)) * linewidth;
211 vsum.x = v1.x + v2.x;
212 vsum.y = v1.y + v2.y;
213 _vscale (&vsum, mitrelen);
214 x -= vsum.x;
215 y -= vsum.y;
216 _update_bbox (bufp, XD_INTERNAL(x,y,m), YD_INTERNAL(x,y,m));
217 }
218 }
219 break;
220 case PL_JOIN_TRIANGULAR:
221 /* add a miter vertex, and same vertices as when bevelling */
222 v1.x = xleft - x;
223 v1.y = yleft - y;
224 v2.x = xright - x;
225 v2.y = yright - y;
226 vsum.x = v1.x + v2.x;
227 vsum.y = v1.y + v2.y;
228 _vscale (&vsum, 0.5 * linewidth);
229 x -= vsum.x;
230 y -= vsum.y;
231 _update_bbox (bufp, XD_INTERNAL(x,y,m), YD_INTERNAL(x,y,m));
232 x += vsum.x;
233 y += vsum.y;
234 /* fall through */
235 case PL_JOIN_BEVEL:
236 _set_line_end_bbox (bufp, x, y, xleft, yleft, linewidth, PL_CAP_BUTT, m);
237 _set_line_end_bbox (bufp, x, y, xright, yright, linewidth, PL_CAP_BUTT, m);
238 break;
239 case PL_JOIN_ROUND:
240 halfwidth = 0.5 * linewidth;
241 _set_ellipse_bbox (bufp, x, y, halfwidth, halfwidth, 1.0, 0.0, 0.0, m);
242 break;
243 }
244 }
245
246 /* Update bounding box due to drawing of a quadratic Bezier segment. This
247 takes into account only extremal x/y values in the interior of the
248 segment, i.e. it doesn't take the endpoints into account. */
249
250 /* WARNING: Like _set_ellipse_bbox above, this does not properly take line
251 width into account. The boundary of a `thick Bezier' is not a nice
252 curve at all. */
253
254 #define QUAD_COOR(t,x0,x1,x2) (((x0)-2*(x1)+(x2))*t*t + 2*((x1)-(x2))*t + (x2))
255
256 void
_set_bezier2_bbox(plOutbuf * bufp,double x0,double y0,double x1,double y1,double x2,double y2,double device_line_width,double m[6])257 _set_bezier2_bbox (plOutbuf *bufp, double x0, double y0, double x1, double y1, double x2, double y2, double device_line_width, double m[6])
258 {
259 double a_x, b_x, t_x;
260 double a_y, b_y, t_y;
261 double x, y, xdevice, ydevice;
262 double device_halfwidth = 0.5 * device_line_width;
263
264 /* compute coeffs of linear equation at+b=0, for both x and y coors */
265 a_x = x0 - 2 * x1 + x2;
266 b_x = (x1 - x2);
267 a_y = y0 - 2 * y1 + y2;
268 b_y = (y1 - y2);
269 if (a_x != 0.0) /* can solve the linear eqn. */
270 {
271 t_x = -b_x / a_x;
272 if (t_x > 0.0 && t_x < 1.0) /* root is in meaningful range */
273 {
274 x = QUAD_COOR(t_x, x0, x1, x2);
275 y = QUAD_COOR(t_x, y0, y1, y2);
276 xdevice = XD_INTERNAL(x,y,m);
277 ydevice = YD_INTERNAL(x,y,m);
278 _update_bbox (bufp, xdevice + device_halfwidth, ydevice);
279 _update_bbox (bufp, xdevice - device_halfwidth, ydevice);
280 }
281 }
282 if (a_y != 0.0) /* can solve the linear eqn. */
283 {
284 t_y = -b_y / a_y;
285 if (t_y > 0.0 && t_y < 1.0) /* root is in meaningful range */
286 {
287 x = QUAD_COOR(t_y, x0, x1, x2);
288 y = QUAD_COOR(t_y, y0, y1, y2);
289 xdevice = XD_INTERNAL(x,y,m);
290 ydevice = YD_INTERNAL(x,y,m);
291 _update_bbox (bufp, xdevice, ydevice + device_halfwidth);
292 _update_bbox (bufp, xdevice, ydevice - device_halfwidth);
293 }
294 }
295 }
296
297 /* Update bounding box due to drawing of a cubic Bezier segment. This
298 takes into account only extremal x/y values in the interior of the
299 segment, i.e. it doesn't take the endpoints into account. */
300
301 /* WARNING: Like _set_ellipse_bbox above, this does not properly take line
302 width into account. The boundary of a `thick Bezier' is not a nice
303 curve at all. */
304
305 #define CUBIC_COOR(t,x0,x1,x2,x3) (((x0)-3*(x1)+3*(x2)-(x3))*t*t*t + 3*((x1)-2*(x2)+(x3))*t*t + 3*((x2)-(x3))*t + (x3))
306
307 void
_set_bezier3_bbox(plOutbuf * bufp,double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3,double device_line_width,double m[6])308 _set_bezier3_bbox (plOutbuf *bufp, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double device_line_width, double m[6])
309 {
310 double a_x, b_x, c_x, s_x, t_x;
311 double a_y, b_y, c_y, s_y, t_y;
312 double x, y, xdevice, ydevice;
313 double device_halfwidth = 0.5 * device_line_width;
314 double sqrt_disc;
315
316 /* compute coeffs of quad. equation at^2+bt+c=0, for both x and y coors */
317 a_x = x0 - 3 * x1 + 3 * x2 - x3;
318 b_x = 2 * (x1 - 2 * x2 + x3);
319 c_x = x2 - x3;
320 a_y = y0 - 3 * y1 + 3 * y2 - y3;
321 b_y = 2 * (y1 - 2 * y2 + y3);
322 c_y = y2 - y3;
323 if (a_x != 0.0) /* can solve the quadratic */
324 {
325 sqrt_disc = sqrt (b_x * b_x - 4 * a_x * c_x);
326 s_x = (- b_x + sqrt_disc) / (2 * a_x);
327 t_x = (- b_x - sqrt_disc) / (2 * a_x);
328 if (s_x > 0.0 && s_x < 1.0) /* root is in meaningful range */
329 {
330 x = CUBIC_COOR(s_x, x0, x1, x2, x3);
331 y = CUBIC_COOR(s_x, y0, y1, y2, y3);
332 xdevice = XD_INTERNAL(x,y,m);
333 ydevice = YD_INTERNAL(x,y,m);
334 _update_bbox (bufp, xdevice + device_halfwidth, ydevice);
335 _update_bbox (bufp, xdevice - device_halfwidth, ydevice);
336 }
337 if (t_x > 0.0 && t_x < 1.0) /* root is in meaningful range */
338 {
339 x = CUBIC_COOR(t_x, x0, x1, x2, x3);
340 y = CUBIC_COOR(t_x, y0, y1, y2, y3);
341 xdevice = XD_INTERNAL(x,y,m);
342 ydevice = YD_INTERNAL(x,y,m);
343 _update_bbox (bufp, xdevice + device_halfwidth, ydevice);
344 _update_bbox (bufp, xdevice - device_halfwidth, ydevice);
345 }
346 }
347 if (a_y != 0.0) /* can solve the quadratic */
348 {
349 sqrt_disc = sqrt (b_y * b_y - 4 * a_y * c_y);
350 s_y = (- b_y + sqrt_disc) / (2 * a_y);
351 t_y = (- b_y - sqrt_disc) / (2 * a_y);
352 if (s_y > 0.0 && s_y < 1.0) /* root is in meaningful range */
353 {
354 x = CUBIC_COOR(s_y, x0, x1, x2, x3);
355 y = CUBIC_COOR(s_y, y0, y1, y2, y3);
356 xdevice = XD_INTERNAL(x,y,m);
357 ydevice = YD_INTERNAL(x,y,m);
358 _update_bbox (bufp, xdevice, ydevice + device_halfwidth);
359 _update_bbox (bufp, xdevice, ydevice - device_halfwidth);
360 }
361 if (t_y > 0.0 && t_y < 1.0) /* root is in meaningful range */
362 {
363 x = CUBIC_COOR(t_y, x0, x1, x2, x3);
364 y = CUBIC_COOR(t_y, y0, y1, y2, y3);
365 xdevice = XD_INTERNAL(x,y,m);
366 ydevice = YD_INTERNAL(x,y,m);
367 _update_bbox (bufp, xdevice, ydevice + device_halfwidth);
368 _update_bbox (bufp, xdevice, ydevice - device_halfwidth);
369 }
370 }
371 }
372