1 /* spline.c: spline and spline list (represented as arrays) manipulation. */
2
3 #ifdef HAVE_CONFIG_H
4 #include "config.h"
5 #endif /* Def: HAVE_CONFIG_H */
6
7 #include "message.h"
8 #include "types.h"
9 #include "spline.h"
10 #include "vector.h"
11 #include "xstd.h"
12 #include <assert.h>
13
14 /* Print a spline in human-readable form. */
15
16 void
print_spline(FILE * f,spline_type s)17 print_spline (FILE *f, spline_type s)
18 {
19 assert(SPLINE_DEGREE (s) == LINEARTYPE || SPLINE_DEGREE (s) == CUBICTYPE);
20
21 if (SPLINE_DEGREE (s) == LINEARTYPE)
22 fprintf (f, "(%.3f,%.3f)--(%.3f,%.3f).\n",
23 START_POINT (s).x, START_POINT (s).y,
24 END_POINT (s).x, END_POINT (s).y);
25
26 else if (SPLINE_DEGREE (s) == CUBICTYPE)
27 fprintf (f, "(%.3f,%.3f)..ctrls(%.3f,%.3f)&(%.3f,%.3f)..(%.3f,%.3f).\n",
28 START_POINT (s).x, START_POINT (s).y,
29 CONTROL1 (s).x, CONTROL1 (s).y,
30 CONTROL2 (s).x, CONTROL2 (s).y,
31 END_POINT (s).x, END_POINT (s).y);
32 }
33
34
35 /* Evaluate the spline S at a given T value. This is an implementation
36 of de Casteljau's algorithm. See Schneider's thesis, p.37.
37 The variable names are taken from there. */
38
39 at_real_coord
evaluate_spline(spline_type s,at_real t)40 evaluate_spline (spline_type s, at_real t)
41 {
42 spline_type V[4]; /* We need degree+1 splines, but assert degree <= 3. */
43 signed i, j;
44 at_real one_minus_t = (at_real) 1.0 - t;
45 polynomial_degree degree = SPLINE_DEGREE (s);
46
47 for (i = 0; i <= degree; i++)
48 {
49 V[0].v[i].x = s.v[i].x;
50 V[0].v[i].y = s.v[i].y;
51 V[0].v[i].z = s.v[i].z;
52 }
53
54 for (j = 1; j <= degree; j++)
55 for (i = 0; i <= degree - j; i++)
56 {
57 at_real_coord t1 = Pmult_scalar (V[j - 1].v[i], one_minus_t);
58 at_real_coord t2 = Pmult_scalar (V[j - 1].v[i + 1], t);
59 at_real_coord temp = Padd (t1, t2);
60 V[j].v[i].x = temp.x;
61 V[j].v[i].y = temp.y;
62 V[j].v[i].z = temp.z;
63 }
64
65 return V[degree].v[0];
66 }
67
68
69 /* Return a new, empty, spline list. */
70
71 spline_list_type *
new_spline_list(void)72 new_spline_list (void)
73 {
74 spline_list_type *answer;
75
76 XMALLOC (answer, sizeof (spline_list_type));
77 *answer = empty_spline_list();
78 return answer;
79 }
80
81 spline_list_type
empty_spline_list(void)82 empty_spline_list (void)
83 {
84 spline_list_type answer;
85 SPLINE_LIST_DATA (answer) = NULL;
86 SPLINE_LIST_LENGTH (answer) = 0;
87 return answer;
88 }
89
90 /* Return a new spline list with SPLINE as the first element. */
91
92 spline_list_type *
new_spline_list_with_spline(spline_type spline)93 new_spline_list_with_spline (spline_type spline)
94 {
95 spline_list_type *answer;
96
97 answer = new_spline_list();
98 XMALLOC (SPLINE_LIST_DATA (*answer), sizeof (spline_type));
99 SPLINE_LIST_ELT (*answer, 0) = spline;
100 SPLINE_LIST_LENGTH (*answer) = 1;
101
102 return answer;
103 }
104
105
106 /* Free the storage in a spline list. We don't have to free the
107 elements, since they are arrays in automatic storage. And we don't
108 want to free the list if it was empty. */
109
110 void
free_spline_list(spline_list_type spline_list)111 free_spline_list (spline_list_type spline_list)
112 {
113 if (SPLINE_LIST_DATA (spline_list) != NULL)
114 free (SPLINE_LIST_DATA (spline_list));
115 }
116
117
118 /* Append the spline S to the list SPLINE_LIST. */
119
120 void
append_spline(spline_list_type * l,spline_type s)121 append_spline (spline_list_type *l, spline_type s)
122 {
123 assert (l != NULL);
124
125 SPLINE_LIST_LENGTH (*l)++;
126 XREALLOC (SPLINE_LIST_DATA (*l), SPLINE_LIST_LENGTH (*l) * sizeof (spline_type));
127 LAST_SPLINE_LIST_ELT (*l) = s;
128 }
129
130
131 /* Tack the elements in the list S2 onto the end of S1.
132 S2 is not changed. */
133
134 void
concat_spline_lists(spline_list_type * s1,spline_list_type s2)135 concat_spline_lists (spline_list_type *s1, spline_list_type s2)
136 {
137 unsigned this_spline;
138 unsigned new_length;
139
140 assert (s1 != NULL);
141
142 new_length = SPLINE_LIST_LENGTH (*s1) + SPLINE_LIST_LENGTH (s2);
143
144 XREALLOC (SPLINE_LIST_DATA (*s1), new_length * sizeof (spline_type));
145
146 for (this_spline = 0; this_spline < SPLINE_LIST_LENGTH (s2); this_spline++)
147 SPLINE_LIST_ELT (*s1, SPLINE_LIST_LENGTH (*s1)++)
148 = SPLINE_LIST_ELT (s2, this_spline);
149 }
150
151
152 /* Return a new, empty, spline list array. */
153
154 spline_list_array_type
new_spline_list_array(void)155 new_spline_list_array (void)
156 {
157 spline_list_array_type answer;
158
159 SPLINE_LIST_ARRAY_DATA (answer) = NULL;
160 SPLINE_LIST_ARRAY_LENGTH (answer) = 0;
161
162 return answer;
163 }
164
165
166 /* Free the storage in a spline list array. We don't
167 want to free the list if it is empty. */
168 void
free_spline_list_array(spline_list_array_type * spline_list_array)169 free_spline_list_array (spline_list_array_type *spline_list_array)
170 {
171 unsigned this_list;
172
173 for (this_list = 0;
174 this_list < SPLINE_LIST_ARRAY_LENGTH (*spline_list_array);
175 this_list++)
176 free_spline_list (SPLINE_LIST_ARRAY_ELT (*spline_list_array, this_list));
177
178 if (SPLINE_LIST_ARRAY_DATA (*spline_list_array) != NULL)
179 free (SPLINE_LIST_ARRAY_DATA (*spline_list_array));
180
181 flush_log_output ();
182 }
183
184
185 /* Append the spline S to the list SPLINE_LIST_ARRAY. */
186
187 void
append_spline_list(spline_list_array_type * l,spline_list_type s)188 append_spline_list (spline_list_array_type *l, spline_list_type s)
189 {
190 SPLINE_LIST_ARRAY_LENGTH (*l)++;
191 XREALLOC (SPLINE_LIST_ARRAY_DATA (*l), SPLINE_LIST_ARRAY_LENGTH (*l) * sizeof (spline_list_type));
192 LAST_SPLINE_LIST_ARRAY_ELT (*l) = s;
193 }
194
195