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