git.hungrycats.org Git - xscreensaver/blob - utils/spline.c

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