git.hungrycats.org Git - xscreensaver/blob - 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 }