2 * Copyright (c) 1987, 1988, 1989 Stanford University
4 * Permission to use, copy, modify, distribute, and sell this software and its
5 * documentation for any purpose is hereby granted without fee, provided
6 * that the above copyright notice appear in all copies and that both that
7 * copyright notice and this permission notice appear in supporting
8 * documentation, and that the name of Stanford not be used in advertising or
9 * publicity pertaining to distribution of the software without specific,
10 * written prior permission. Stanford makes no representations about
11 * the suitability of this software for any purpose. It is provided "as is"
12 * without express or implied warranty.
14 * STANFORD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
16 * IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
18 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
19 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
20 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
23 /* This code came with the InterViews distribution, and was translated
24 from C++ to C by Matthieu Devin <devin@lucid.com> some time in 1992.
30 #define SMOOTHNESS 1.0
32 static void grow_spline_points (spline* s);
33 static void mid_point (double x0, double y0, double x1, double y1,
34 double *mx, double *my);
35 static int can_approx_with_line (double x0, double y0, double x2,
36 double y2, double x3, double y3);
37 static void add_line (spline* s, double x0, double y0, double x1, double y1);
38 static void add_bezier_arc (spline* s,
39 double x0, double y0, double x1, double y1,
40 double x2, double y2, double x3, double y3);
41 static void third_point (double x0, double y0, double x1, double y1,
42 double *tx, double *ty);
43 static void calc_section (spline* s, double cminus1x, double cminus1y,
44 double cx, double cy, double cplus1x, double cplus1y,
45 double cplus2x, double cplus2y);
48 make_spline (unsigned int size)
50 spline* s = (spline*)calloc (1, sizeof (spline));
53 s->control_x = (double*)calloc (s->n_controls, sizeof (double));
54 s->control_y = (double*)calloc (s->n_controls, sizeof (double));
57 s->allocated_points = s->n_controls;
58 s->points = (XPoint*)calloc (s->allocated_points, sizeof (XPoint));
60 if (!s->control_x || !s->control_y || !s->points)
67 grow_spline_points (spline *s)
69 s->allocated_points *= 2;
71 (XPoint*)realloc (s->points, s->allocated_points * sizeof (XPoint));
72 if (!s->points) abort();
76 mid_point (double x0, double y0,
78 double *mx, double *my)
80 *mx = (x0 + x1) / 2.0;
81 *my = (y0 + y1) / 2.0;
85 third_point (double x0, double y0,
87 double *tx, double *ty)
89 *tx = (2 * x0 + x1) / 3.0;
90 *ty = (2 * y0 + y1) / 3.0;
94 can_approx_with_line (double x0, double y0,
98 double triangle_area, side_squared, dx, dy;
100 triangle_area = x0 * y2 - x2 * y0 + x2 * y3 - x3 * y2 + x3 * y0 - x0 * y3;
101 /* actually 4 times the area. */
102 triangle_area *= triangle_area;
105 side_squared = dx * dx + dy * dy;
106 return triangle_area <= SMOOTHNESS * side_squared;
111 double x0, double y0,
112 double x1, double y1)
114 if (s->n_points >= s->allocated_points)
115 grow_spline_points (s);
117 if (s->n_points == 0)
119 s->points [s->n_points].x = x0;
120 s->points [s->n_points].y = y0;
123 s->points [s->n_points].x = x1;
124 s->points [s->n_points].y = y1;
129 add_bezier_arc (spline *s,
130 double x0, double y0,
131 double x1, double y1,
132 double x2, double y2,
133 double x3, double y3)
135 double midx01, midx12, midx23, midlsegx, midrsegx, cx,
136 midy01, midy12, midy23, midlsegy, midrsegy, cy;
138 mid_point (x0, y0, x1, y1, &midx01, &midy01);
139 mid_point (x1, y1, x2, y2, &midx12, &midy12);
140 mid_point (x2, y2, x3, y3, &midx23, &midy23);
141 mid_point (midx01, midy01, midx12, midy12, &midlsegx, &midlsegy);
142 mid_point (midx12, midy12, midx23, midy23, &midrsegx, &midrsegy);
143 mid_point (midlsegx, midlsegy, midrsegx, midrsegy, &cx, &cy);
145 if (can_approx_with_line (x0, y0, midlsegx, midlsegy, cx, cy))
146 add_line (s, x0, y0, cx, cy);
147 else if ((midx01 != x1) || (midy01 != y1) || (midlsegx != x2)
148 || (midlsegy != y2) || (cx != x3) || (cy != y3))
149 add_bezier_arc (s, x0, y0, midx01, midy01, midlsegx, midlsegy, cx, cy);
151 if (can_approx_with_line (cx, cy, midx23, midy23, x3, y3))
152 add_line (s, cx, cy, x3, y3);
153 else if ((cx != x0) || (cy != y0) || (midrsegx != x1) || (midrsegy != y1)
154 || (midx23 != x2) || (midy23 != y2))
155 add_bezier_arc (s, cx, cy, midrsegx, midrsegy, midx23, midy23, x3, y3);
159 calc_section (spline *s,
160 double cminus1x, double cminus1y,
161 double cx, double cy,
162 double cplus1x, double cplus1y,
163 double cplus2x, double cplus2y)
165 double p0x, p1x, p2x, p3x, tempx,
166 p0y, p1y, p2y, p3y, tempy;
168 third_point (cx, cy, cplus1x, cplus1y, &p1x, &p1y);
169 third_point (cplus1x, cplus1y, cx, cy, &p2x, &p2y);
170 third_point (cx, cy, cminus1x, cminus1y, &tempx, &tempy);
171 mid_point (tempx, tempy, p1x, p1y, &p0x, &p0y);
172 third_point (cplus1x, cplus1y, cplus2x, cplus2y, &tempx, &tempy);
173 mid_point (tempx, tempy, p2x, p2y, &p3x, &p3y);
174 add_bezier_arc (s, p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y);
178 compute_spline (spline *s)
183 if (s->n_controls < 3)
186 calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
187 s->control_y [0], s->control_x [0], s->control_y [0],
188 s->control_x [1], s->control_y [1]);
189 calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
190 s->control_y [0], s->control_x [1], s->control_y [1],
191 s->control_x [2], s->control_y [2]);
193 for (i = 1; i < s->n_controls - 2; i++)
194 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
195 s->control_x [i], s->control_y [i],
196 s->control_x [i + 1], s->control_y [i + 1],
197 s->control_x [i + 2], s->control_y [i + 2]);
199 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
200 s->control_x [i], s->control_y [i],
201 s->control_x [i + 1], s->control_y [i + 1],
202 s->control_x [i + 1], s->control_y [i + 1]);
203 calc_section (s, s->control_x [i], s->control_y [i],
204 s->control_x [i + 1], s->control_y [i + 1],
205 s->control_x [i + 1], s->control_y [i + 1],
206 s->control_x [i + 1], s->control_y [i + 1]);
210 compute_closed_spline (spline *s)
215 if (s->n_controls < 3)
219 s->control_x [s->n_controls - 1],
220 s->control_y [s->n_controls - 1],
221 s->control_x [0], s->control_y [0],
222 s->control_x [1], s->control_y [1],
223 s->control_x [2], s->control_y [2]);
225 for (i = 1; i < s->n_controls - 2; i++)
226 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
227 s->control_x [i], s->control_y [i],
228 s->control_x [i + 1], s->control_y [i + 1],
229 s->control_x [i + 2], s->control_y [i + 2]);
231 calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
232 s->control_x [i], s->control_y [i],
233 s->control_x [i + 1], s->control_y [i + 1],
234 s->control_x [0], s->control_y [0]);
235 calc_section (s, s->control_x [i], s->control_y [i],
236 s->control_x [i + 1], s->control_y [i + 1],
237 s->control_x [0], s->control_y [0],
238 s->control_x [1], s->control_y [1]);
242 just_fill_spline (spline *s)
246 while (s->allocated_points < s->n_controls + 1)
247 grow_spline_points (s);
249 for (i = 0; i < s->n_controls; i++)
251 s->points [i].x = s->control_x [i];
252 s->points [i].y = s->control_y [i];
254 s->points [s->n_controls].x = s->control_x [0];
255 s->points [s->n_controls].y = s->control_y [0];
256 s->n_points = s->n_controls + 1;
260 append_spline_points (spline *s1, spline *s2)
263 while (s1->allocated_points < s1->n_points + s2->n_points)
264 grow_spline_points (s1);
265 for (i = s1->n_points; i < s1->n_points + s2->n_points; i++)
267 s1->points [i].x = s2->points [i - s1->n_points].x;
268 s1->points [i].y = s2->points [i - s1->n_points].y;
270 s1->n_points = s1->n_points + s2->n_points;
274 spline_bounding_box (spline *s, XRectangle *rectangle_out)
282 if (s->n_points == 0)
284 rectangle_out->x = 0;
285 rectangle_out->y = 0;
286 rectangle_out->width = 0;
287 rectangle_out->height = 0;
290 min_x = s->points [0].x;
292 min_y = s->points [0].y;
295 for (i = 1; i < s->n_points; i++)
297 if (s->points [i].x < min_x)
298 min_x = s->points [i].x;
299 if (s->points [i].x > max_x)
300 max_x = s->points [i].x;
301 if (s->points [i].y < min_y)
302 min_y = s->points [i].y;
303 if (s->points [i].y > max_y)
304 max_y = s->points [i].y;
306 rectangle_out->x = min_x;
307 rectangle_out->y = min_y;
308 rectangle_out->width = max_x - min_x;
309 rectangle_out->height = max_y - min_y;
313 free_spline(spline * s)
315 free ((void *) s->control_x);
316 free ((void *) s->control_y);
317 free ((void *) s->points);