[screensavers] / screenhack / spline.c

/*
 * Copyright (c) 1987, 1988, 1989 Stanford University
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided
 * that the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of Stanford not be used in advertising or
 * publicity pertaining to distribution of the software without specific,
 * written prior permission.  Stanford makes no representations about
 * the suitability of this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 *
 * STANFORD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
 * IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/* This code came with the InterViews distribution, and was translated
   from C++ to C by Matthieu Devin <devin@lucid.com> some time in 1992.
 */

#include "utils.h"
#include "spline.h"

#define SMOOTHNESS 1.0

static void grow_spline_points (spline* s);
static void mid_point (double x0, double y0, double x1, double y1,
		       double *mx, double *my);
static int can_approx_with_line (double x0, double y0, double x2,
				 double y2, double x3, double y3);
static void add_line (spline* s, double x0, double y0, double x1, double y1);
static void add_bezier_arc (spline* s,
			    double x0, double y0, double x1, double y1,
			    double x2, double y2, double x3, double y3);
static void third_point (double x0, double y0, double x1, double y1,
			 double *tx, double *ty);
static void calc_section (spline* s, double cminus1x, double cminus1y,
			  double cx, double cy, double cplus1x, double cplus1y,
			  double cplus2x, double cplus2y);

spline*
make_spline (unsigned int size)
{
  spline* s = (spline*)calloc (1, sizeof (spline));
  if (!s) abort();
  s->n_controls = size;
  s->control_x = (double*)calloc (s->n_controls, sizeof (double));
  s->control_y = (double*)calloc (s->n_controls, sizeof (double));

  s->n_points = 0;
  s->allocated_points = s->n_controls;
  s->points = (XPoint*)calloc (s->allocated_points, sizeof (XPoint));

  if (!s->control_x || !s->control_y || !s->points)
    abort();

  return s;
}

static void
grow_spline_points (spline *s)
{
  s->allocated_points = 10 + (s->allocated_points * 1.3);
  s->points =
    (XPoint*)realloc (s->points, s->allocated_points * sizeof (XPoint));
  if (!s->points) abort();
}

static void 
mid_point (double x0, double y0,
	   double x1, double y1,
	   double *mx, double *my)
{
  *mx = (x0 + x1) / 2.0;
  *my = (y0 + y1) / 2.0;
}

static void 
third_point (double x0, double y0,
	     double x1, double y1,
	     double *tx, double *ty)
{
  *tx = (2 * x0 + x1) / 3.0;
  *ty = (2 * y0 + y1) / 3.0;
}

static int
can_approx_with_line (double x0, double y0,
		      double x2, double y2,
		      double x3, double y3)
{
  double triangle_area, side_squared, dx, dy;
  
  triangle_area = x0 * y2 - x2 * y0 + x2 * y3 - x3 * y2 + x3 * y0 - x0 * y3;
  /* actually 4 times the area. */
  triangle_area *= triangle_area;
  dx = x3 - x0;
  dy = y3 - y0;
  side_squared = dx * dx + dy * dy;
  return triangle_area <= SMOOTHNESS * side_squared;
}

static void
add_line (spline *s,
	  double x0, double y0,
	  double x1, double y1)
{
  if (s->n_points >= s->allocated_points)
    grow_spline_points (s);

  if (s->n_points == 0)
    {
      s->points [s->n_points].x = x0;
      s->points [s->n_points].y = y0;
      s->n_points += 1;
    }
  s->points [s->n_points].x = x1;
  s->points [s->n_points].y = y1;
  s->n_points += 1;
}

static void 
add_bezier_arc (spline *s,
		double x0, double y0,
		double x1, double y1,
		double x2, double y2,
		double x3, double y3)
{
  double midx01, midx12, midx23, midlsegx, midrsegx, cx,
  midy01, midy12, midy23, midlsegy, midrsegy, cy;
    
  mid_point (x0, y0, x1, y1, &midx01, &midy01);
  mid_point (x1, y1, x2, y2, &midx12, &midy12);
  mid_point (x2, y2, x3, y3, &midx23, &midy23);
  mid_point (midx01, midy01, midx12, midy12, &midlsegx, &midlsegy);
  mid_point (midx12, midy12, midx23, midy23, &midrsegx, &midrsegy);
  mid_point (midlsegx, midlsegy, midrsegx, midrsegy, &cx, &cy);    

  if (can_approx_with_line (x0, y0, midlsegx, midlsegy, cx, cy))
    add_line (s, x0, y0, cx, cy);
  else if ((midx01 != x1) || (midy01 != y1) || (midlsegx != x2)
	   || (midlsegy != y2) || (cx != x3) || (cy != y3))
    add_bezier_arc (s, x0, y0, midx01, midy01, midlsegx, midlsegy, cx, cy);

  if (can_approx_with_line (cx, cy, midx23, midy23, x3, y3))
    add_line (s, cx, cy, x3, y3);
  else if ((cx != x0) || (cy != y0) || (midrsegx != x1) || (midrsegy != y1)
	   || (midx23 != x2) || (midy23 != y2))  
    add_bezier_arc (s, cx, cy, midrsegx, midrsegy, midx23, midy23, x3, y3);
}

static void
calc_section (spline *s,
	      double cminus1x, double cminus1y,
	      double cx, double cy,
	      double cplus1x, double cplus1y,
	      double cplus2x, double cplus2y)
{
  double p0x, p1x, p2x, p3x, tempx,
  p0y, p1y, p2y, p3y, tempy;
  
  third_point (cx, cy, cplus1x, cplus1y, &p1x, &p1y);
  third_point (cplus1x, cplus1y, cx, cy, &p2x, &p2y);
  third_point (cx, cy, cminus1x, cminus1y, &tempx, &tempy);
  mid_point (tempx, tempy, p1x, p1y, &p0x, &p0y);
  third_point (cplus1x, cplus1y, cplus2x, cplus2y, &tempx, &tempy);
  mid_point (tempx, tempy, p2x, p2y, &p3x, &p3y);
  add_bezier_arc (s, p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y);
}

void
compute_spline (spline *s)
{
  int i;
  s->n_points = 0;
  
  if (s->n_controls < 3)
    return;

  calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
		s->control_y [0], s->control_x [0], s->control_y [0],
		s->control_x [1], s->control_y [1]);
  calc_section (s, s->control_x [0], s->control_y [0], s->control_x [0],
		s->control_y [0], s->control_x [1], s->control_y [1],
		s->control_x [2], s->control_y [2]);

  for (i = 1; i < s->n_controls - 2; i++)
    calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
		  s->control_x [i], s->control_y [i],
		  s->control_x [i + 1], s->control_y [i + 1],
		  s->control_x [i + 2], s->control_y [i + 2]);
  
  calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
		s->control_x [i], s->control_y [i],
		s->control_x [i + 1], s->control_y [i + 1],
		s->control_x [i + 1], s->control_y [i + 1]);
  calc_section (s, s->control_x [i], s->control_y [i],
		s->control_x [i + 1], s->control_y [i + 1],
		s->control_x [i + 1], s->control_y [i + 1],
		s->control_x [i + 1], s->control_y [i + 1]);
}

void 
compute_closed_spline (spline *s)
{
  int i;
  s->n_points = 0;

  if (s->n_controls < 3) 
    return;

  calc_section (s,
		s->control_x [s->n_controls - 1],
		s->control_y [s->n_controls - 1],
		s->control_x [0], s->control_y [0],
		s->control_x [1], s->control_y [1],
		s->control_x [2], s->control_y [2]);

  for (i = 1; i < s->n_controls - 2; i++)
    calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
		  s->control_x [i], s->control_y [i],
		  s->control_x [i + 1], s->control_y [i + 1],
		  s->control_x [i + 2], s->control_y [i + 2]);
      
  calc_section (s, s->control_x [i - 1], s->control_y [i - 1],
		s->control_x [i], s->control_y [i],
		s->control_x [i + 1], s->control_y [i + 1],
		s->control_x [0], s->control_y [0]);
  calc_section (s, s->control_x [i], s->control_y [i],
		s->control_x [i + 1], s->control_y [i + 1],
		s->control_x [0], s->control_y [0],
		s->control_x [1], s->control_y [1]);
}

void
just_fill_spline (spline *s)
{
  int i;

  while (s->allocated_points < s->n_controls + 1)
    grow_spline_points (s);
    
  for (i = 0; i < s->n_controls; i++)
    {
      s->points [i].x = s->control_x [i];
      s->points [i].y = s->control_y [i];
    }
  s->points [s->n_controls].x = s->control_x [0];
  s->points [s->n_controls].y = s->control_y [0];
  s->n_points = s->n_controls + 1;
}

void
append_spline_points (spline *s1, spline *s2)
{
  int i;
  while (s1->allocated_points < s1->n_points + s2->n_points)
    grow_spline_points (s1);
  for (i = s1->n_points; i < s1->n_points + s2->n_points; i++)
    {
      s1->points [i].x = s2->points [i - s1->n_points].x;
      s1->points [i].y = s2->points [i - s1->n_points].y;
    }
  s1->n_points = s1->n_points + s2->n_points;
}

void
spline_bounding_box (spline *s, XRectangle *rectangle_out)
{
  int min_x;
  int max_x;
  int min_y;
  int max_y;
  int i;

  if (s->n_points == 0)
    {
      rectangle_out->x = 0;
      rectangle_out->y = 0;
      rectangle_out->width = 0;
      rectangle_out->height = 0;
    }

  min_x = s->points [0].x;
  max_x = min_x;
  min_y = s->points [0].y;
  max_y = min_y;

  for (i = 1; i < s->n_points; i++)
    {
      if (s->points [i].x < min_x)
	min_x = s->points [i].x;
      if (s->points [i].x > max_x)
	max_x = s->points [i].x;
      if (s->points [i].y < min_y)
	min_y = s->points [i].y;
      if (s->points [i].y > max_y)
	max_y = s->points [i].y;
    }
  rectangle_out->x = min_x;
  rectangle_out->y = min_y;
  rectangle_out->width = max_x - min_x;
  rectangle_out->height = max_y - min_y;
}

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