http://www.jwz.org/xscreensaver/xscreensaver-5.09.tar.gz
[xscreensaver] / utils / spline.c
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 no_more_memory (void);
33 static void grow_spline_points (spline* s);
34 static void mid_point (double x0, double y0, double x1, double y1,
35                        double *mx, double *my);
36 static int can_approx_with_line (double x0, double y0, double x2,
37                                  double y2, double x3, double y3);
38 static void add_line (spline* s, double x0, double y0, double x1, double y1);
39 static void add_bezier_arc (spline* s,
40                             double x0, double y0, double x1, double y1,
41                             double x2, double y2, double x3, double y3);
42 static void third_point (double x0, double y0, double x1, double y1,
43                          double *tx, double *ty);
44 static void calc_section (spline* s, double cminus1x, double cminus1y,
45                           double cx, double cy, double cplus1x, double cplus1y,
46                           double cplus2x, double cplus2y);
47
48 static void
49 no_more_memory (void)
50 {
51   fprintf (stderr, "No more memory\n");
52   exit (1);
53 }
54
55 spline*
56 make_spline (unsigned int size)
57 {
58   spline* s = (spline*)calloc (1, sizeof (spline));
59   if (!s)
60     no_more_memory ();
61   s->n_controls = size;
62   s->control_x = (double*)calloc (s->n_controls, sizeof (double));
63   s->control_y = (double*)calloc (s->n_controls, sizeof (double));
64
65   s->n_points = 0;
66   s->allocated_points = s->n_controls;
67   s->points = (XPoint*)calloc (s->allocated_points, sizeof (XPoint));
68
69   if (!s->control_x || !s->control_y || !s->points)
70     no_more_memory ();
71
72   return s;
73 }
74
75 static void
76 grow_spline_points (spline *s)
77 {
78   s->allocated_points *= 2;
79   s->points =
80     (XPoint*)realloc (s->points, s->allocated_points * sizeof (XPoint));
81
82   if (!s->points)
83     no_more_memory ();
84 }
85
86 static void 
87 mid_point (double x0, double y0,
88            double x1, double y1,
89            double *mx, double *my)
90 {
91   *mx = (x0 + x1) / 2.0;
92   *my = (y0 + y1) / 2.0;
93 }
94
95 static void 
96 third_point (double x0, double y0,
97              double x1, double y1,
98              double *tx, double *ty)
99 {
100   *tx = (2 * x0 + x1) / 3.0;
101   *ty = (2 * y0 + y1) / 3.0;
102 }
103
104 static int
105 can_approx_with_line (double x0, double y0,
106                       double x2, double y2,
107                       double x3, double y3)
108 {
109   double triangle_area, side_squared, dx, dy;
110   
111   triangle_area = x0 * y2 - x2 * y0 + x2 * y3 - x3 * y2 + x3 * y0 - x0 * y3;
112   /* actually 4 times the area. */
113   triangle_area *= triangle_area;
114   dx = x3 - x0;
115   dy = y3 - y0;
116   side_squared = dx * dx + dy * dy;
117   return triangle_area <= SMOOTHNESS * side_squared;
118 }
119
120 static void
121 add_line (spline *s,
122           double x0, double y0,
123           double x1, double y1)
124 {
125   if (s->n_points >= s->allocated_points)
126     grow_spline_points (s);
127
128   if (s->n_points == 0)
129     {
130       s->points [s->n_points].x = x0;
131       s->points [s->n_points].y = y0;
132       s->n_points += 1;
133     }
134   s->points [s->n_points].x = x1;
135   s->points [s->n_points].y = y1;
136   s->n_points += 1;
137 }
138
139 static void 
140 add_bezier_arc (spline *s,
141                 double x0, double y0,
142                 double x1, double y1,
143                 double x2, double y2,
144                 double x3, double y3)
145 {
146   double midx01, midx12, midx23, midlsegx, midrsegx, cx,
147   midy01, midy12, midy23, midlsegy, midrsegy, cy;
148     
149   mid_point (x0, y0, x1, y1, &midx01, &midy01);
150   mid_point (x1, y1, x2, y2, &midx12, &midy12);
151   mid_point (x2, y2, x3, y3, &midx23, &midy23);
152   mid_point (midx01, midy01, midx12, midy12, &midlsegx, &midlsegy);
153   mid_point (midx12, midy12, midx23, midy23, &midrsegx, &midrsegy);
154   mid_point (midlsegx, midlsegy, midrsegx, midrsegy, &cx, &cy);    
155
156   if (can_approx_with_line (x0, y0, midlsegx, midlsegy, cx, cy))
157     add_line (s, x0, y0, cx, cy);
158   else if ((midx01 != x1) || (midy01 != y1) || (midlsegx != x2)
159            || (midlsegy != y2) || (cx != x3) || (cy != y3))
160     add_bezier_arc (s, x0, y0, midx01, midy01, midlsegx, midlsegy, cx, cy);
161
162   if (can_approx_with_line (cx, cy, midx23, midy23, x3, y3))
163     add_line (s, cx, cy, x3, y3);
164   else if ((cx != x0) || (cy != y0) || (midrsegx != x1) || (midrsegy != y1)
165            || (midx23 != x2) || (midy23 != y2))  
166     add_bezier_arc (s, cx, cy, midrsegx, midrsegy, midx23, midy23, x3, y3);
167 }
168
169 static void
170 calc_section (spline *s,
171               double cminus1x, double cminus1y,
172               double cx, double cy,
173               double cplus1x, double cplus1y,
174               double cplus2x, double cplus2y)
175 {
176   double p0x, p1x, p2x, p3x, tempx,
177   p0y, p1y, p2y, p3y, tempy;
178   
179   third_point (cx, cy, cplus1x, cplus1y, &p1x, &p1y);
180   third_point (cplus1x, cplus1y, cx, cy, &p2x, &p2y);
181   third_point (cx, cy, cminus1x, cminus1y, &tempx, &tempy);
182   mid_point (tempx, tempy, p1x, p1y, &p0x, &p0y);
183   third_point (cplus1x, cplus1y, cplus2x, cplus2y, &tempx, &tempy);
184   mid_point (tempx, tempy, p2x, p2y, &p3x, &p3y);
185   add_bezier_arc (s, p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y);
186 }
187
188 void
189 compute_spline (spline *s)
190 {
191   int i;
192   s->n_points = 0;
193   
194   if (s->n_controls < 3)
195     return;
196
197   calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
198                 s->control_y [0], s->control_x [0], s->control_y [0],
199                 s->control_x [1], s->control_y [1]);
200   calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
201                 s->control_y [0], s->control_x [1], s->control_y [1],
202                 s->control_x [2], s->control_y [2]);
203
204   for (i = 1; i < s->n_controls - 2; i++)
205     calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
206                   s->control_x [i], s->control_y [i],
207                   s->control_x [i + 1], s->control_y [i + 1],
208                   s->control_x [i + 2], s->control_y [i + 2]);
209   
210   calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
211                 s->control_x [i], s->control_y [i],
212                 s->control_x [i + 1], s->control_y [i + 1],
213                 s->control_x [i + 1], s->control_y [i + 1]);
214   calc_section (s, s->control_x [i], s->control_y [i],
215                 s->control_x [i + 1], s->control_y [i + 1],
216                 s->control_x [i + 1], s->control_y [i + 1],
217                 s->control_x [i + 1], s->control_y [i + 1]);
218 }
219
220 void 
221 compute_closed_spline (spline *s)
222 {
223   int i;
224   s->n_points = 0;
225
226   if (s->n_controls < 3) 
227     return;
228
229   calc_section (s,
230                 s->control_x [s->n_controls - 1],
231                 s->control_y [s->n_controls - 1],
232                 s->control_x [0], s->control_y [0],
233                 s->control_x [1], s->control_y [1],
234                 s->control_x [2], s->control_y [2]);
235
236   for (i = 1; i < s->n_controls - 2; i++)
237     calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
238                   s->control_x [i], s->control_y [i],
239                   s->control_x [i + 1], s->control_y [i + 1],
240                   s->control_x [i + 2], s->control_y [i + 2]);
241       
242   calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
243                 s->control_x [i], s->control_y [i],
244                 s->control_x [i + 1], s->control_y [i + 1],
245                 s->control_x [0], s->control_y [0]);
246   calc_section (s, s->control_x [i], s->control_y [i],
247                 s->control_x [i + 1], s->control_y [i + 1],
248                 s->control_x [0], s->control_y [0],
249                 s->control_x [1], s->control_y [1]);
250 }
251
252 void
253 just_fill_spline (spline *s)
254 {
255   int i;
256
257   while (s->allocated_points < s->n_controls + 1)
258     grow_spline_points (s);
259     
260   for (i = 0; i < s->n_controls; i++)
261     {
262       s->points [i].x = s->control_x [i];
263       s->points [i].y = s->control_y [i];
264     }
265   s->points [s->n_controls].x = s->control_x [0];
266   s->points [s->n_controls].y = s->control_y [0];
267   s->n_points = s->n_controls + 1;
268 }
269
270 void
271 append_spline_points (spline *s1, spline *s2)
272 {
273   int i;
274   while (s1->allocated_points < s1->n_points + s2->n_points)
275     grow_spline_points (s1);
276   for (i = s1->n_points; i < s1->n_points + s2->n_points; i++)
277     {
278       s1->points [i].x = s2->points [i - s1->n_points].x;
279       s1->points [i].y = s2->points [i - s1->n_points].y;
280     }
281   s1->n_points = s1->n_points + s2->n_points;
282 }
283
284 void
285 spline_bounding_box (spline *s, XRectangle *rectangle_out)
286 {
287   int min_x;
288   int max_x;
289   int min_y;
290   int max_y;
291   int i;
292
293   if (s->n_points == 0)
294     {
295       rectangle_out->x = 0;
296       rectangle_out->y = 0;
297       rectangle_out->width = 0;
298       rectangle_out->height = 0;
299     }
300
301   min_x = s->points [0].x;
302   max_x = min_x;
303   min_y = s->points [0].y;
304   max_y = min_y;
305
306   for (i = 1; i < s->n_points; i++)
307     {
308       if (s->points [i].x < min_x)
309         min_x = s->points [i].x;
310       if (s->points [i].x > max_x)
311         max_x = s->points [i].x;
312       if (s->points [i].y < min_y)
313         min_y = s->points [i].y;
314       if (s->points [i].y > max_y)
315         max_y = s->points [i].y;
316     }
317   rectangle_out->x = min_x;
318   rectangle_out->y = min_y;
319   rectangle_out->width = max_x - min_x;
320   rectangle_out->height = max_y - min_y;
321 }
322
323 void
324 free_spline(spline * s)
325 {
326   free ((void *) s->control_x);
327   free ((void *) s->control_y);
328   free ((void *) s->points);
329   free ((void *) s);
330 }