summaryrefslogtreecommitdiff
path: root/support/dktools/dk4xsp.h
blob: 87fcb8c7f3ddf6b3270c25e048b6da07c90426e4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
/*
Copyright (C) 2018-2020, Dirk Krause
SPDX-License-Identifier: BSD-3-Clause
*/

/*
	WARNING: This file was generated by the dkct program (see
	http://dktools.sourceforge.net/ for details).
	Changes you make here will be lost if dkct is run again!
	You should modify the original source and run dkct on it.
	Original source: dk4xsp.ctr
*/

#ifndef DK4XSP_H_INCLUDED
/** Avoid multiple inclusions. */
#define DK4XSP_H_INCLUDED 1


#line 9 "dk4xsp.ctr"

/**	@file	dk4xsp.h	X-spline segments.

@section	secxspoverview	Overview

X-splines were introduced by C. Blanc and C. Schlick on the SIGGRAPH'95,
they are described in detail in the paper:
"X-Splines: A Spline Model Designed for the End-User".

Unfortunately the X-spline implementation in XFig contained a bug for
many years, for interpolated splines a wrong coefficient calculation
(q=-s instead of q=-0.5s) was used.
Probably the resulting unexpected strong curvature and sometimes unwanted
oscillations kept people from using interpolated X-splines in XFig.
Fixing the bug and introducing the correct calculation would break
appearance of existing *.fig files containing interpolated X-splines.
So the decision was made to keep the calculation as is. For new
interpolated X-splines a factor s=-0.5 is used instead of -1, so the
q value does not exceed 0.5.

This module contains functions for X-spline calculations, both
in correct mode and in XFig compatibility mode.

An X-spline is a continuous curve represented by a set of discrete
control points. Each control point consists of coordinates (x, y, optionally
z) and a shape factor s in range -1 to 1 (positive for approximation points,
0 for corner points, negative for interpolation points).

An X-spline segment is the curve range corresponding to two consecutive
control points. It is controlled by up to 4 control points:
- Control point corresponding to start of segment (index 1),
- Control point corresponding to end of segment (index 2),
- Neighbour control point "left" from segment start control point (index 0),
- Neighbour control point "right" from segment end control point (index 3).

For open X-splines there is no left neighbour for the first segment
and no right neighbour for the final segment.

For closed X-splines the final point is the left neighbour of the first segment
and the first point is the right neighbour of the final segment.

The t parameter is relative to the segment, it is in the range
0.0<=t<=1.0.

@section	secxsphighlevel	High level API

A high level API is available for 2D X-splines using the dk4_xsp_2d_t
data type.

Before doing any calculation, use dk4xsp2d_reset() to reset the entire
structure. Optionally use dk4xsp2d_set_xfig() to set up XFig compatibility
mode.

For each segment use dk4xsp2d_reset_points() to
reset the data in the dk4_xsp_2d_t structure.
Now use dk4xsp2d_set_point() with index 0, 1, 2, 3
to set coordinates and shape factors for left neighbour control point
of segment, start of segment, end of segment and right neighbour.
For the first segment of open X-splines skip index 0 as there is no
"left" neighbour. For the final segment of open X-splines skip index 3 as
there is no "right" neighbour.

To draw an X-spline using polyline/polygon approximation you need to
calculate point coordinates, use the dk4xsp2d_calculate_value() function.
The t paramater is in the range 0<=t<=1.
A pointer to an array of at least 2 elements is required as rp argument,
x and y value are stored here.
I suggest to use at least 32 subsegments for each X-spline segment.

To draw an X-spline using a sequence of Bezier curves you need to calculate
point coordinates (x, y) and the first derivatives (dx/dt, dy/dt),
use the dk4xsp2d_calculate_value_derivative function.
The function stores x, dx/dt, y, dy/dt in the array rp points to.
A pointer to an array of at least 4 elements is required as rp argument.
I suggest to use at least 4 subsegments for each X-spline segment,
8 subsegments are recommended.

@section	secxsplowlevel	Low level API

The low level API calculates values for just one coordinate.

Before doing any calculation, use dk4xsp_reset() to reset the entire
structure, optionally use dk4xsp_set_xfig() to set up XFig compatibility
mode.

For each segment use dk4xsp_reset_data() to reset all data components,
use dk4xsp_set_point() multiple times with i=(0),1,2,(3) to set shape factors
for the control points. Omitted calls with i=0 or i=3 indicate that the
neighbour control points are not present.

Each point within a segment is represented by a t value in range 0 to 1.
For each point use dk4xsp_prepare() first to set up internal coefficients
(blending functions values and optionally blending functions derivative
values) corresponding to the t value.
Next use dk4xsp_calculate() to calculate the
coordinate value and optionally the first derivative.
After using dk4xsp_prepare() once to set up the segment you can use
dk4xsp_calculate() multiple times for different coordinates.
The dk4xsp_prepare() function calculates the blending function values and
optionally the derivatives value. The dk4xsp_calculate() function applies the
blending function values and optionally derivatives to a set of
x, y or z coordinates of control points.
The same d value must be used in both calls, you can not calculate a
derivative value if the structure was not prepared to do so.

*/


#ifndef	DK4ERROR_H_INCLUDED
#if DK4_BUILDING_DKTOOLS4
#include "dk4error.h"
#else
#include <dktools-4/dk4error.h>
#endif
#endif



/**	X-spline coefficients without coordinates.
	The dk4xsp_set_point() function sets h, s, p, q, dudt.
	The dk4xsp_prepare() function sets u, f, dfdt.
*/
typedef struct {
	double	s[4];		/**< Shape factors. */
	double	p[4];		/**< Coefficients p for blending functions. */
	double	q[4];		/**< Coefficients q for blending functions. */
	double	u[4];		/**< Parameter u for blending functions. */
	double	dudt[4];	/**< Derivative du/dt. */
	double	f[4];		/**< Blending function results. */
	double	dfdt[4];	/**< Derivatives df/dt of the blending functions. */
	uint8_t	h[4];		/**< Availability of coordinates and shape factors. */
	uint8_t	xfig;		/**< Flag: XFig compatibility. */
} dk4_xsp_t;



/**	X-spline segment in two dimensions.
*/
typedef struct {
	double		x[4];		/**< X coordinates. */
	double		y[4];		/**< Y coordinates. */
	dk4_xsp_t	xsp;		/**< Shape factors and coefficients. */
} dk4_xsp_2d_t;



#ifdef	__cplusplus
extern "C" {
#endif


/*
	LOW LEVEL API
	-------------
*/

/**	Reset X-spline structure including the Xfig compatibility flag.
	@param	xsp	Spline structure to reset.
*/

void
dk4xsp_reset(dk4_xsp_t *xsp);


/**	Reset data components in X-spline structure, leave Xfig compatibility
	flag unchanged.
	@param	xsp	Spline structure to reset.
*/

void
dk4xsp_reset_data(dk4_xsp_t *xsp);


/**	Set or reset xfig compatibility flag.
	@param	xsp	Spline structure to modify.
	@param	val	New Xfig compatibility flag value.
*/

void
dk4xsp_set_xfig(dk4_xsp_t *xsp, uint8_t val);


/**	Set shape factor for one control point, calculate values derived
	from shape factor.
	Used 2 to 4 times to set up a segment.
	@param	xsp	Spline structure to modify.
	@param	s	Shape factor
	@param	i	Index of control point:
				0=left neighbour, 1=segment start, 2=segment end,
				3=right neighbour.
*/

void
dk4xsp_set_point(
	dk4_xsp_t	*xsp,
	double		 s,
	size_t		 i
);



/**	Prepare calculations for one t value.
	@param	xsp	Spline structure to prepare.
	@param	t	Parameter t in range 0 to 1.
	@param	d	Prepare to calculate derivative.
	@param	erp	Error report, may be NULL.
	@return	1 on success, 0 on error.

	Error codes:
	- DK4_E_INVALID_ARGUMENTS<br>
	  if invalid arguments were passed to the function.
*/

int
dk4xsp_prepare(
	dk4_xsp_t	*xsp,
	double		 t,
	int			 d,
	dk4_er_t	*erp
);



/**	Calculations for one t value.
	For d=0 the function just calculates the position, rp is a
	pointer to one result variable.
	For other d values the function also calculates the first derivative,
	rp is a pointer to an array of two elements: position and derivative.
	@param	rp	Result variable or array address.
	@param	xsp	Spline structure to use.
	@param	x	Coordinates values: 4 elements for values at
				left neighbour, left border, right border and right neighbour.
	@param	d	Flag: Calculate derivative too.
	@param	erp	Error report for diagnostics.
	@return	1 on success, 0 on error.

	Error codes:
	- DK4_E_INVALID_ARGUMENTS<br>
	  if invalid arguments were passed to the function,
	- DK4_E_MATH_OVERFLOW<br>
	  if a mathematical overflow occured in the calculation.
*/

int
dk4xsp_calculate(
	double			*rp,
	dk4_xsp_t const	*xsp,
	double const	*x,
	int				 d,
	dk4_er_t		*erp
);


/*
	HIGH LEVEL API FOR 2D X-SPLINES
	-------------------------------
*/

/**	Reset spline structure completely.
	@param	sp	Spline structure to reset.
*/

void
dk4xsp2d_reset(
	dk4_xsp_2d_t	*sp
);


/**	Set or reset XFig compatibility flag.
	@param	sp	Spline structure to set up.
	@param	val	New flag value.
*/

void
dk4xsp2d_set_xfig(
	dk4_xsp_2d_t	*sp,
	uint8_t			 val
);

/**	Reset spline structure to "all points unset".
	@param	sp	Spline structure to reset.
*/

void
dk4xsp2d_reset_points(
	dk4_xsp_2d_t	*sp
);


/**	Set one point in spline structure.
	@param	sp	Spline structure to set up.
	@param	x	X coordinate.
	@param	y	Y coordinate.
	@param	s	Shape factor.
	@param	i	Index (0=A, 1=B, 2=C, 3=D).
*/

void
dk4xsp2d_set_point(
	dk4_xsp_2d_t	*sp,
	double			 x,
	double			 y,
	double			 s,
	size_t			 i
);


/**	Calculate just the value at a given point.
	@param	rp	Address of results array, 2 elements: rp[0]=x, rp[1]=y.
	@param	sp	Spline structure to use.
	@param	t	Value t in range 0 to 1.
	@param	erp	Error report, may be NULL.
	@return	1 on success, 0 on error.

	Error codes:
	- DK4_E_INVALID_ARGUMENTS<br>
	  if invalid arguments were passed to the function,
	- DK4_E_MATH_OVERFLOW<br>
	  if a numeric overflow occured in calculation.
*/

int
dk4xsp2d_calculate_value(
	double			*rp,
	dk4_xsp_2d_t 	*sp,
	double			 t,
	dk4_er_t		*erp
);


/**	Calculate values and first derivative.
	@param	rp	Address of results array, 4 elements:
				rp[0]=x, rp[1]=dx/dt, rp[2]=y, rp[3]=dy/dt.
	@param	sp	Spline structure to use.
	@param	t	Value t in range 0 to 1.
	@param	erp	Error report, may be NULL.
	@return	1 on success, 0 on error.

	Error codes:
	- DK4_E_INVALID_ARGUMENTS<br>
	  if invalid arguments were passed to the function,
	- DK4_E_MATH_OVERFLOW<br>
	  if a numeric overflow occured in calculation.
*/

int
dk4xsp2d_calculate_value_derivative(
	double			*rp,
	dk4_xsp_2d_t	*sp,
	double			 t,
	dk4_er_t		*erp
);


/**	Check whether the segment is a line (Shape factor s is 0 for
	points 1 and 2).
	This check can be applied after setting the control points for the
	segment.
	@param	sp	Spline segment to check.
	@return	1 for lines, 0 for curved spline segment.
*/

int
dk4xsp2d_is_line(dk4_xsp_2d_t const *sp);


/**	Calculate X-spline segment length.
	@param	rp	Address of result variable.
	@param	sp	Spline segment to calculate length for.
	@param	eps	Tolerance to stop iteration.
	@param	erp	Error report, may be NULL.
	@return	1 on success, 0 on error.

	Error codes:
	- DK4_E_INVALID_ARGUMENTS<br>
	  if invalid arguments were passed to the function,
	- DK4_E_MATH_OVERFLOW<br>
	  if a numeric overflow occured in calculation,
	- DK4_E_NOT_FOUND<br>
	  if the iteration did not succeed.
*/

int
dk4xsp2d_calculate_length(
	double			*rp,
	dk4_xsp_2d_t	*sp,
	double			 eps,
	dk4_er_t		*erp
);


/**	Calculate partial X-spline segment length from 0 to t_end.
	@param	rp		Address of result variable.
	@param	sp		Spline segment to calculate length for.
	@param	tend	End value for parameter t.
	@param	eps		Tolerance to stop iteration.
	@param	erp		Error report, may be NULL.
	@return	1 on success, 0 on error.

	Error codes:
	- DK4_E_INVALID_ARGUMENTS<br>
	  if invalid arguments were passed to the function,
	- DK4_E_MATH_OVERFLOW<br>
	  if a numeric overflow occured in calculation,
	- DK4_E_NOT_FOUND<br>
	  if the iteration did not succeed.
*/

int
dk4xsp2d_calculate_partial_length(
	double			*rp,
	dk4_xsp_2d_t	*sp,
	double			 tend,
	double			 eps,
	dk4_er_t		*erp
);


#ifdef	__cplusplus
}
#endif



/* vim: set ai sw=4 ts=4 : */


#endif