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