kernel / pub / scm / linux / kernel / git / geoff / libtwin / 287d16c4ccce6f85a6f2f5e3b46b4bd7ece1e327 / . / libtwin / twin_spline.c

/* | |

* Twin - A Tiny Window System | |

* Copyright © 2004 Carl Worth <cworth@cworth.org> | |

* All rights reserved. | |

* | |

* This Library is free software; you can redistribute it and/or | |

* modify it under the terms of the GNU Library General Public License as | |

* published by the Free Software Foundation; either version 2 of the | |

* License, or (at your option) any later version. | |

* | |

* This Library is distributed in the hope that it will be useful, | |

* but WITHOUT ANY WARRANTY; without even the implied warranty of | |

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |

* Library General Public License for more details. | |

* | |

* You should have received a copy of the GNU Library General Public | |

* License along with the Twin Library; see the file COPYING. If not, | |

* write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |

* Boston, MA 02111-1307, USA. | |

*/ | |

#include "twinint.h" | |

typedef struct _twin_spline { | |

twin_spoint_t a, b, c, d; | |

} twin_spline_t; | |

static void | |

_lerp_half (twin_spoint_t *a, twin_spoint_t *b, twin_spoint_t *result) | |

{ | |

result->x = a->x + ((b->x - a->x) >> 1); | |

result->y = a->y + ((b->y - a->y) >> 1); | |

} | |

static void | |

_de_casteljau (twin_spline_t *spline, twin_spline_t *s1, twin_spline_t *s2) | |

{ | |

twin_spoint_t ab, bc, cd; | |

twin_spoint_t abbc, bccd; | |

twin_spoint_t final; | |

_lerp_half (&spline->a, &spline->b, &ab); | |

_lerp_half (&spline->b, &spline->c, &bc); | |

_lerp_half (&spline->c, &spline->d, &cd); | |

_lerp_half (&ab, &bc, &abbc); | |

_lerp_half (&bc, &cd, &bccd); | |

_lerp_half (&abbc, &bccd, &final); | |

s1->a = spline->a; | |

s1->b = ab; | |

s1->c = abbc; | |

s1->d = final; | |

s2->a = final; | |

s2->b = bccd; | |

s2->c = cd; | |

s2->d = spline->d; | |

} | |

/* | |

* Return an upper bound on the error (squared) that could | |

* result from approximating a spline as a line segment | |

* connecting the two endpoints | |

*/ | |

static twin_dfixed_t | |

_twin_spline_error_squared (twin_spline_t *spline) | |

{ | |

twin_dfixed_t berr, cerr; | |

berr = _twin_distance_to_line_squared (&spline->b, &spline->a, &spline->d); | |

cerr = _twin_distance_to_line_squared (&spline->c, &spline->a, &spline->d); | |

if (berr > cerr) | |

return berr; | |

else | |

return cerr; | |

} | |

/* | |

* Pure recursive spline decomposition. | |

*/ | |

static void | |

_twin_spline_decompose (twin_path_t *path, | |

twin_spline_t *spline, | |

twin_dfixed_t tolerance_squared) | |

{ | |

if (_twin_spline_error_squared (spline) <= tolerance_squared) | |

{ | |

_twin_path_sdraw (path, spline->a.x, spline->a.y); | |

} | |

else | |

{ | |

twin_spline_t s1, s2; | |

_de_casteljau (spline, &s1, &s2); | |

_twin_spline_decompose (path, &s1, tolerance_squared); | |

_twin_spline_decompose (path, &s2, tolerance_squared); | |

} | |

} | |

void | |

_twin_path_scurve (twin_path_t *path, | |

twin_sfixed_t x1, twin_sfixed_t y1, | |

twin_sfixed_t x2, twin_sfixed_t y2, | |

twin_sfixed_t x3, twin_sfixed_t y3) | |

{ | |

twin_spline_t spline; | |

if (path->npoints == 0) | |

_twin_path_smove (path, 0, 0); | |

spline.a = path->points[path->npoints - 1]; | |

spline.b.x = x1; | |

spline.b.y = y1; | |

spline.c.x = x2; | |

spline.c.y = y2; | |

spline.d.x = x3; | |

spline.d.y = y3; | |

_twin_spline_decompose (path, &spline, TWIN_SFIXED_TOLERANCE * TWIN_SFIXED_TOLERANCE); | |

_twin_path_sdraw (path, x3, y3); | |

} | |

void | |

twin_path_curve (twin_path_t *path, | |

twin_fixed_t x1, twin_fixed_t y1, | |

twin_fixed_t x2, twin_fixed_t y2, | |

twin_fixed_t x3, twin_fixed_t y3) | |

{ | |

return _twin_path_scurve (path, | |

_twin_matrix_x (&path->state.matrix, x1, y1), | |

_twin_matrix_y (&path->state.matrix, x1, y1), | |

_twin_matrix_x (&path->state.matrix, x2, y2), | |

_twin_matrix_y (&path->state.matrix, x2, y2), | |

_twin_matrix_x (&path->state.matrix, x3, y3), | |

_twin_matrix_y (&path->state.matrix, x3, y3)); | |

} |