Commit | Line | Data |
---|---|---|
3144ee8a AT |
1 | /* |
2 | * Copyright (c) 1987, 1988, 1989 Stanford University | |
3 | * | |
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. | |
13 | * | |
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. | |
21 | */ | |
22 | ||
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. | |
25 | */ | |
26 | ||
27 | #include "utils.h" | |
28 | #include "spline.h" | |
29 | ||
30 | #define SMOOTHNESS 1.0 | |
31 | ||
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); | |
46 | ||
47 | spline* | |
48 | make_spline (unsigned int size) | |
49 | { | |
50 | spline* s = (spline*)calloc (1, sizeof (spline)); | |
51 | if (!s) abort(); | |
52 | s->n_controls = size; | |
53 | s->control_x = (double*)calloc (s->n_controls, sizeof (double)); | |
54 | s->control_y = (double*)calloc (s->n_controls, sizeof (double)); | |
55 | ||
56 | s->n_points = 0; | |
57 | s->allocated_points = s->n_controls; | |
58 | s->points = (XPoint*)calloc (s->allocated_points, sizeof (XPoint)); | |
59 | ||
60 | if (!s->control_x || !s->control_y || !s->points) | |
61 | abort(); | |
62 | ||
63 | return s; | |
64 | } | |
65 | ||
66 | static void | |
67 | grow_spline_points (spline *s) | |
68 | { | |
69 | s->allocated_points = 10 + (s->allocated_points * 1.3); | |
70 | s->points = | |
71 | (XPoint*)realloc (s->points, s->allocated_points * sizeof (XPoint)); | |
72 | if (!s->points) abort(); | |
73 | } | |
74 | ||
75 | static void | |
76 | mid_point (double x0, double y0, | |
77 | double x1, double y1, | |
78 | double *mx, double *my) | |
79 | { | |
80 | *mx = (x0 + x1) / 2.0; | |
81 | *my = (y0 + y1) / 2.0; | |
82 | } | |
83 | ||
84 | static void | |
85 | third_point (double x0, double y0, | |
86 | double x1, double y1, | |
87 | double *tx, double *ty) | |
88 | { | |
89 | *tx = (2 * x0 + x1) / 3.0; | |
90 | *ty = (2 * y0 + y1) / 3.0; | |
91 | } | |
92 | ||
93 | static int | |
94 | can_approx_with_line (double x0, double y0, | |
95 | double x2, double y2, | |
96 | double x3, double y3) | |
97 | { | |
98 | double triangle_area, side_squared, dx, dy; | |
99 | ||
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; | |
103 | dx = x3 - x0; | |
104 | dy = y3 - y0; | |
105 | side_squared = dx * dx + dy * dy; | |
106 | return triangle_area <= SMOOTHNESS * side_squared; | |
107 | } | |
108 | ||
109 | static void | |
110 | add_line (spline *s, | |
111 | double x0, double y0, | |
112 | double x1, double y1) | |
113 | { | |
114 | if (s->n_points >= s->allocated_points) | |
115 | grow_spline_points (s); | |
116 | ||
117 | if (s->n_points == 0) | |
118 | { | |
119 | s->points [s->n_points].x = x0; | |
120 | s->points [s->n_points].y = y0; | |
121 | s->n_points += 1; | |
122 | } | |
123 | s->points [s->n_points].x = x1; | |
124 | s->points [s->n_points].y = y1; | |
125 | s->n_points += 1; | |
126 | } | |
127 | ||
128 | static void | |
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) | |
134 | { | |
135 | double midx01, midx12, midx23, midlsegx, midrsegx, cx, | |
136 | midy01, midy12, midy23, midlsegy, midrsegy, cy; | |
137 | ||
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); | |
144 | ||
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); | |
150 | ||
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); | |
156 | } | |
157 | ||
158 | static void | |
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) | |
164 | { | |
165 | double p0x, p1x, p2x, p3x, tempx, | |
166 | p0y, p1y, p2y, p3y, tempy; | |
167 | ||
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); | |
175 | } | |
176 | ||
177 | void | |
178 | compute_spline (spline *s) | |
179 | { | |
180 | int i; | |
181 | s->n_points = 0; | |
182 | ||
183 | if (s->n_controls < 3) | |
184 | return; | |
185 | ||
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]); | |
192 | ||
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]); | |
198 | ||
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]); | |
207 | } | |
208 | ||
209 | void | |
210 | compute_closed_spline (spline *s) | |
211 | { | |
212 | int i; | |
213 | s->n_points = 0; | |
214 | ||
215 | if (s->n_controls < 3) | |
216 | return; | |
217 | ||
218 | calc_section (s, | |
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]); | |
224 | ||
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]); | |
230 | ||
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]); | |
239 | } | |
240 | ||
241 | void | |
242 | just_fill_spline (spline *s) | |
243 | { | |
244 | int i; | |
245 | ||
246 | while (s->allocated_points < s->n_controls + 1) | |
247 | grow_spline_points (s); | |
248 | ||
249 | for (i = 0; i < s->n_controls; i++) | |
250 | { | |
251 | s->points [i].x = s->control_x [i]; | |
252 | s->points [i].y = s->control_y [i]; | |
253 | } | |
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; | |
257 | } | |
258 | ||
259 | void | |
260 | append_spline_points (spline *s1, spline *s2) | |
261 | { | |
262 | int i; | |
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++) | |
266 | { | |
267 | s1->points [i].x = s2->points [i - s1->n_points].x; | |
268 | s1->points [i].y = s2->points [i - s1->n_points].y; | |
269 | } | |
270 | s1->n_points = s1->n_points + s2->n_points; | |
271 | } | |
272 | ||
273 | void | |
274 | spline_bounding_box (spline *s, XRectangle *rectangle_out) | |
275 | { | |
276 | int min_x; | |
277 | int max_x; | |
278 | int min_y; | |
279 | int max_y; | |
280 | int i; | |
281 | ||
282 | if (s->n_points == 0) | |
283 | { | |
284 | rectangle_out->x = 0; | |
285 | rectangle_out->y = 0; | |
286 | rectangle_out->width = 0; | |
287 | rectangle_out->height = 0; | |
288 | } | |
289 | ||
290 | min_x = s->points [0].x; | |
291 | max_x = min_x; | |
292 | min_y = s->points [0].y; | |
293 | max_y = min_y; | |
294 | ||
295 | for (i = 1; i < s->n_points; i++) | |
296 | { | |
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; | |
305 | } | |
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; | |
310 | } | |
311 | ||
312 | void | |
313 | free_spline(spline * s) | |
314 | { | |
315 | free ((void *) s->control_x); | |
316 | free ((void *) s->control_y); | |
317 | free ((void *) s->points); | |
318 | free ((void *) s); | |
319 | } |