1 /* 2 Copyright (C) 2018-2021, Dirk Krause 3 SPDX-License-Identifier: BSD-3-Clause 4 */ 5 6 /* 7 WARNING: This file was generated by the dkct program (see 8 http://dktools.sourceforge.net/ for details). 9 Changes you make here will be lost if dkct is run again! 10 You should modify the original source and run dkct on it. 11 Original source: dk4xsp.ctr 12 */ 13 14 #ifndef DK4XSP_H_INCLUDED 15 /** Avoid multiple inclusions. */ 16 #define DK4XSP_H_INCLUDED 1 17 18 19 /** @file dk4xsp.h X-spline segments. 20 21 @section secxspoverview Overview 22 23 X-splines were introduced by C. Blanc and C. Schlick on the SIGGRAPH'95, 24 they are described in detail in the paper: 25 "X-Splines: A Spline Model Designed for the End-User". 26 27 Unfortunately the X-spline implementation in XFig contained a bug for 28 many years, for interpolated splines a wrong coefficient calculation 29 (q=-s instead of q=-0.5s) was used. 30 Probably the resulting unexpected strong curvature and sometimes unwanted 31 oscillations kept people from using interpolated X-splines in XFig. 32 Fixing the bug and introducing the correct calculation would break 33 appearance of existing *.fig files containing interpolated X-splines. 34 So the decision was made to keep the calculation as is. For new 35 interpolated X-splines a factor s=-0.5 is used instead of -1, so the 36 q value does not exceed 0.5. 37 38 This module contains functions for X-spline calculations, both 39 in correct mode and in XFig compatibility mode. 40 41 An X-spline is a continuous curve represented by a set of discrete 42 control points. Each control point consists of coordinates (x, y, optionally 43 z) and a shape factor s in range -1 to 1 (positive for approximation points, 44 0 for corner points, negative for interpolation points). 45 46 An X-spline segment is the curve range corresponding to two consecutive 47 control points. It is controlled by up to 4 control points: 48 - Control point corresponding to start of segment (index 1), 49 - Control point corresponding to end of segment (index 2), 50 - Neighbour control point "left" from segment start control point (index 0), 51 - Neighbour control point "right" from segment end control point (index 3). 52 53 For open X-splines there is no left neighbour for the first segment 54 and no right neighbour for the final segment. 55 56 For closed X-splines the final point is the left neighbour of the first segment 57 and the first point is the right neighbour of the final segment. 58 59 The t parameter is relative to the segment, it is in the range 60 0.0<=t<=1.0. 61 62 @section secxsphighlevel High level API 63 64 A high level API is available for 2D X-splines using the dk4_xsp_2d_t 65 data type. 66 67 Before doing any calculation, use dk4xsp2d_reset() to reset the entire 68 structure. Optionally use dk4xsp2d_set_xfig() to set up XFig compatibility 69 mode. 70 71 For each segment use dk4xsp2d_reset_points() to 72 reset the data in the dk4_xsp_2d_t structure. 73 Now use dk4xsp2d_set_point() with index 0, 1, 2, 3 74 to set coordinates and shape factors for left neighbour control point 75 of segment, start of segment, end of segment and right neighbour. 76 For the first segment of open X-splines skip index 0 as there is no 77 "left" neighbour. For the final segment of open X-splines skip index 3 as 78 there is no "right" neighbour. 79 80 To draw an X-spline using polyline/polygon approximation you need to 81 calculate point coordinates, use the dk4xsp2d_calculate_value() function. 82 The t paramater is in the range 0<=t<=1. 83 A pointer to an array of at least 2 elements is required as rp argument, 84 x and y value are stored here. 85 I suggest to use at least 32 subsegments for each X-spline segment. 86 87 To draw an X-spline using a sequence of Bezier curves you need to calculate 88 point coordinates (x, y) and the first derivatives (dx/dt, dy/dt), 89 use the dk4xsp2d_calculate_value_derivative function. 90 The function stores x, dx/dt, y, dy/dt in the array rp points to. 91 A pointer to an array of at least 4 elements is required as rp argument. 92 I suggest to use at least 4 subsegments for each X-spline segment, 93 8 subsegments are recommended. 94 95 @section secxsplowlevel Low level API 96 97 The low level API calculates values for just one coordinate. 98 99 Before doing any calculation, use dk4xsp_reset() to reset the entire 100 structure, optionally use dk4xsp_set_xfig() to set up XFig compatibility 101 mode. 102 103 For each segment use dk4xsp_reset_data() to reset all data components, 104 use dk4xsp_set_point() multiple times with i=(0),1,2,(3) to set shape factors 105 for the control points. Omitted calls with i=0 or i=3 indicate that the 106 neighbour control points are not present. 107 108 Each point within a segment is represented by a t value in range 0 to 1. 109 For each point use dk4xsp_prepare() first to set up internal coefficients 110 (blending functions values and optionally blending functions derivative 111 values) corresponding to the t value. 112 Next use dk4xsp_calculate() to calculate the 113 coordinate value and optionally the first derivative. 114 After using dk4xsp_prepare() once to set up the segment you can use 115 dk4xsp_calculate() multiple times for different coordinates. 116 The dk4xsp_prepare() function calculates the blending function values and 117 optionally the derivatives value. The dk4xsp_calculate() function applies the 118 blending function values and optionally derivatives to a set of 119 x, y or z coordinates of control points. 120 The same d value must be used in both calls, you can not calculate a 121 derivative value if the structure was not prepared to do so. 122 123 */ 124 125 126 #ifndef DK4ERROR_H_INCLUDED 127 #if DK4_BUILDING_DKTOOLS4 128 #include <libdk4base/dk4error.h> 129 #else 130 #include <dktools-4/dk4error.h> 131 #endif 132 #endif 133 134 135 136 /** X-spline coefficients without coordinates. 137 The dk4xsp_set_point() function sets h, s, p, q, dudt. 138 The dk4xsp_prepare() function sets u, f, dfdt. 139 */ 140 typedef struct { 141 double s[4]; /**< Shape factors. */ 142 double p[4]; /**< Coefficients p for blending functions. */ 143 double q[4]; /**< Coefficients q for blending functions. */ 144 double u[4]; /**< Parameter u for blending functions. */ 145 double dudt[4]; /**< Derivative du/dt. */ 146 double f[4]; /**< Blending function results. */ 147 double dfdt[4]; /**< Derivatives df/dt of the blending functions. */ 148 uint8_t h[4]; /**< Availability of coordinates and shape factors. */ 149 uint8_t xfig; /**< Flag: XFig compatibility. */ 150 } dk4_xsp_t; 151 152 153 154 /** X-spline segment in two dimensions. 155 */ 156 typedef struct { 157 double x[4]; /**< X coordinates. */ 158 double y[4]; /**< Y coordinates. */ 159 dk4_xsp_t xsp; /**< Shape factors and coefficients. */ 160 } dk4_xsp_2d_t; 161 162 163 164 #ifdef __cplusplus 165 extern "C" { 166 #endif 167 168 169 /* 170 LOW LEVEL API 171 ------------- 172 */ 173 174 /** Reset X-spline structure including the Xfig compatibility flag. 175 @param xsp Spline structure to reset. 176 */ 177 178 void 179 dk4xsp_reset(dk4_xsp_t *xsp); 180 181 182 /** Reset data components in X-spline structure, leave Xfig compatibility 183 flag unchanged. 184 @param xsp Spline structure to reset. 185 */ 186 187 void 188 dk4xsp_reset_data(dk4_xsp_t *xsp); 189 190 191 /** Set or reset xfig compatibility flag. 192 @param xsp Spline structure to modify. 193 @param val New Xfig compatibility flag value. 194 */ 195 196 void 197 dk4xsp_set_xfig(dk4_xsp_t *xsp, uint8_t val); 198 199 200 /** Set shape factor for one control point, calculate values derived 201 from shape factor. 202 Used 2 to 4 times to set up a segment. 203 @param xsp Spline structure to modify. 204 @param s Shape factor 205 @param i Index of control point: 206 0=left neighbour, 1=segment start, 2=segment end, 207 3=right neighbour. 208 */ 209 210 void 211 dk4xsp_set_point( 212 dk4_xsp_t *xsp, 213 double s, 214 size_t i 215 ); 216 217 218 219 /** Prepare calculations for one t value. 220 @param xsp Spline structure to prepare. 221 @param t Parameter t in range 0 to 1. 222 @param d Prepare to calculate derivative. 223 @param erp Error report, may be NULL. 224 @return 1 on success, 0 on error. 225 226 Error codes: 227 - DK4_E_INVALID_ARGUMENTS<br> 228 if invalid arguments were passed to the function. 229 */ 230 231 int 232 dk4xsp_prepare( 233 dk4_xsp_t *xsp, 234 double t, 235 int d, 236 dk4_er_t *erp 237 ); 238 239 240 241 /** Calculations for one t value. 242 For d=0 the function just calculates the position, rp is a 243 pointer to one result variable. 244 For other d values the function also calculates the first derivative, 245 rp is a pointer to an array of two elements: position and derivative. 246 @param rp Result variable or array address. 247 @param xsp Spline structure to use. 248 @param x Coordinates values: 4 elements for values at 249 left neighbour, left border, right border and right neighbour. 250 @param d Flag: Calculate derivative too. 251 @param erp Error report for diagnostics. 252 @return 1 on success, 0 on error. 253 254 Error codes: 255 - DK4_E_INVALID_ARGUMENTS<br> 256 if invalid arguments were passed to the function, 257 - DK4_E_MATH_OVERFLOW<br> 258 if a mathematical overflow occured in the calculation. 259 */ 260 261 int 262 dk4xsp_calculate( 263 double *rp, 264 dk4_xsp_t const *xsp, 265 double const *x, 266 int d, 267 dk4_er_t *erp 268 ); 269 270 271 /* 272 HIGH LEVEL API FOR 2D X-SPLINES 273 ------------------------------- 274 */ 275 276 /** Reset spline structure completely. 277 @param sp Spline structure to reset. 278 */ 279 280 void 281 dk4xsp2d_reset( 282 dk4_xsp_2d_t *sp 283 ); 284 285 286 /** Set or reset XFig compatibility flag. 287 @param sp Spline structure to set up. 288 @param val New flag value. 289 */ 290 291 void 292 dk4xsp2d_set_xfig( 293 dk4_xsp_2d_t *sp, 294 uint8_t val 295 ); 296 297 /** Reset spline structure to "all points unset". 298 @param sp Spline structure to reset. 299 */ 300 301 void 302 dk4xsp2d_reset_points( 303 dk4_xsp_2d_t *sp 304 ); 305 306 307 /** Set one point in spline structure. 308 @param sp Spline structure to set up. 309 @param x X coordinate. 310 @param y Y coordinate. 311 @param s Shape factor. 312 @param i Index (0=A, 1=B, 2=C, 3=D). 313 */ 314 315 void 316 dk4xsp2d_set_point( 317 dk4_xsp_2d_t *sp, 318 double x, 319 double y, 320 double s, 321 size_t i 322 ); 323 324 325 /** Calculate just the value at a given point. 326 @param rp Address of results array, 2 elements: rp[0]=x, rp[1]=y. 327 @param sp Spline structure to use. 328 @param t Value t in range 0 to 1. 329 @param erp Error report, may be NULL. 330 @return 1 on success, 0 on error. 331 332 Error codes: 333 - DK4_E_INVALID_ARGUMENTS<br> 334 if invalid arguments were passed to the function, 335 - DK4_E_MATH_OVERFLOW<br> 336 if a numeric overflow occured in calculation. 337 */ 338 339 int 340 dk4xsp2d_calculate_value( 341 double *rp, 342 dk4_xsp_2d_t *sp, 343 double t, 344 dk4_er_t *erp 345 ); 346 347 348 /** Calculate values and first derivative. 349 @param rp Address of results array, 4 elements: 350 rp[0]=x, rp[1]=dx/dt, rp[2]=y, rp[3]=dy/dt. 351 @param sp Spline structure to use. 352 @param t Value t in range 0 to 1. 353 @param erp Error report, may be NULL. 354 @return 1 on success, 0 on error. 355 356 Error codes: 357 - DK4_E_INVALID_ARGUMENTS<br> 358 if invalid arguments were passed to the function, 359 - DK4_E_MATH_OVERFLOW<br> 360 if a numeric overflow occured in calculation. 361 */ 362 363 int 364 dk4xsp2d_calculate_value_derivative( 365 double *rp, 366 dk4_xsp_2d_t *sp, 367 double t, 368 dk4_er_t *erp 369 ); 370 371 372 /** Check whether the segment is a line (Shape factor s is 0 for 373 points 1 and 2). 374 This check can be applied after setting the control points for the 375 segment. 376 @param sp Spline segment to check. 377 @return 1 for lines, 0 for curved spline segment. 378 */ 379 380 int 381 dk4xsp2d_is_line(dk4_xsp_2d_t const *sp); 382 383 384 /** Calculate X-spline segment length. 385 @param rp Address of result variable. 386 @param sp Spline segment to calculate length for. 387 @param eps Tolerance to stop iteration. 388 @param erp Error report, may be NULL. 389 @return 1 on success, 0 on error. 390 391 Error codes: 392 - DK4_E_INVALID_ARGUMENTS<br> 393 if invalid arguments were passed to the function, 394 - DK4_E_MATH_OVERFLOW<br> 395 if a numeric overflow occured in calculation, 396 - DK4_E_NOT_FOUND<br> 397 if the iteration did not succeed. 398 */ 399 400 int 401 dk4xsp2d_calculate_length( 402 double *rp, 403 dk4_xsp_2d_t *sp, 404 double eps, 405 dk4_er_t *erp 406 ); 407 408 409 /** Calculate partial X-spline segment length from 0 to t_end. 410 @param rp Address of result variable. 411 @param sp Spline segment to calculate length for. 412 @param tend End value for parameter t. 413 @param eps Tolerance to stop iteration. 414 @param erp Error report, may be NULL. 415 @return 1 on success, 0 on error. 416 417 Error codes: 418 - DK4_E_INVALID_ARGUMENTS<br> 419 if invalid arguments were passed to the function, 420 - DK4_E_MATH_OVERFLOW<br> 421 if a numeric overflow occured in calculation, 422 - DK4_E_NOT_FOUND<br> 423 if the iteration did not succeed. 424 */ 425 426 int 427 dk4xsp2d_calculate_partial_length( 428 double *rp, 429 dk4_xsp_2d_t *sp, 430 double tend, 431 double eps, 432 dk4_er_t *erp 433 ); 434 435 436 #ifdef __cplusplus 437 } 438 #endif 439 440 441 442 /* vim: set ai sw=4 ts=4 : */ 443 444 445 #endif 446