home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / fontutils-0.6 / lib / spline.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-27  |  5.5 KB  |  217 lines
  1. /* spline.c: spline and spline list (represented as arrays) manipulation.
  2.  
  3. Copyright (C) 1992 Free Software Foundation, Inc.
  4.  
  5. This program is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2, or (at your option)
  8. any later version.
  9.  
  10. This program is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  18.  
  19. #include "config.h"
  20.  
  21. #include "bounding-box.h"
  22. #include "spline.h"
  23. #include "vector.h"
  24.  
  25.  
  26. /* Return a new spline structure, initialized with (recognizable)
  27.    garbage.  */ 
  28.  
  29. spline_type
  30. new_spline ()
  31. {
  32.   spline_type spline;
  33.  
  34.   START_POINT (spline)
  35.     = CONTROL1 (spline)
  36.     = CONTROL2 (spline)
  37.     = END_POINT (spline)
  38.     = (real_coordinate_type) { -100.0, -100.0 };
  39.   SPLINE_DEGREE (spline) = -1;
  40.  
  41.   return spline;
  42. }
  43.  
  44.  
  45. /* Print a spline in human-readable form.  */
  46.  
  47. void
  48. print_spline (FILE *f, spline_type s)
  49. {
  50.   if (SPLINE_DEGREE (s) == LINEAR)
  51.     fprintf (f, "(%.3f,%.3f)--(%.3f,%.3f).\n",
  52.                 START_POINT (s).x, START_POINT (s).y,
  53.                 END_POINT (s).x, END_POINT (s).y);
  54.  
  55.   else if (SPLINE_DEGREE (s) == CUBIC)
  56.     fprintf (f, "(%.3f,%.3f)..ctrls(%.3f,%.3f)&(%.3f,%.3f)..(%.3f,%.3f).\n",
  57.                 START_POINT (s).x, START_POINT (s).y,
  58.                 CONTROL1 (s).x, CONTROL1 (s).y,
  59.                 CONTROL2 (s).x, CONTROL2 (s).y,
  60.                 END_POINT (s).x, END_POINT (s).y);
  61.  
  62.   else
  63.     FATAL1 ("print_spline: strange degree (%d)", SPLINE_DEGREE (s));
  64. }
  65.  
  66.  
  67.  
  68.  
  69. /* Evaluate the spline S at a given T value.  This is an implementation
  70.    of de Casteljau's algorithm.  See Schneider's thesis (reference in
  71.    ../limn/README), p.37.  The variable names are taken from there.  */
  72.  
  73. real_coordinate_type
  74. evaluate_spline (spline_type s, real t)
  75. {
  76.   spline_type V[4];    /* We need degree+1 splines, but assert degree <= 3.  */
  77.   unsigned i, j;
  78.   real one_minus_t = 1.0 - t;
  79.   polynomial_degree degree = SPLINE_DEGREE (s);
  80.  
  81.   for (i = 0; i <= degree; i++)
  82.     V[0].v[i] = s.v[i];
  83.  
  84.   for (j = 1; j <= degree; j++)
  85.     for (i = 0; i <= degree - j; i++)
  86.       {
  87.         real_coordinate_type t1 = Pmult_scalar (V[j - 1].v[i], one_minus_t);
  88.         real_coordinate_type t2 = Pmult_scalar (V[j - 1].v[i + 1], t);
  89.         V[j].v[i] = Padd (t1, t2);
  90.       }
  91.  
  92.   return V[degree].v[0];
  93. }
  94.  
  95.  
  96.  
  97.  
  98. /* Return a new, empty, spline list.  */
  99.  
  100. spline_list_type *
  101. new_spline_list ()
  102. {
  103.   spline_list_type *answer = xmalloc (sizeof (spline_list_type));
  104.  
  105.   SPLINE_LIST_DATA (*answer) = NULL;
  106.   SPLINE_LIST_LENGTH (*answer) = 0;
  107.  
  108.   return answer;
  109. }
  110.  
  111.  
  112. /* Return a new spline list with SPLINE as the first element.  */
  113.  
  114. spline_list_type *
  115. init_spline_list (spline_type spline)
  116. {
  117.   spline_list_type *answer = xmalloc (sizeof (spline_list_type));
  118.  
  119.   SPLINE_LIST_DATA (*answer) = xmalloc (sizeof (spline_type));
  120.   SPLINE_LIST_ELT (*answer, 0) = spline;
  121.   SPLINE_LIST_LENGTH (*answer) = 1;
  122.  
  123.   return answer;
  124. }
  125.  
  126.  
  127. /* Free the storage in a spline list.  We don't have to free the
  128.    elements, since they are arrays in automatic storage.  And we don't
  129.    want to free the list if it was empty.  */
  130.  
  131. void
  132. free_spline_list (spline_list_type *spline_list)
  133. {
  134.   if (SPLINE_LIST_DATA (*spline_list) != NULL)
  135.     safe_free ((address *) &(SPLINE_LIST_DATA (*spline_list)));
  136. }
  137.  
  138.  
  139. /* Append the spline S to the list SPLINE_LIST.  */
  140.  
  141. void
  142. append_spline (spline_list_type *l, spline_type s)
  143. {
  144.   assert (l != NULL);
  145.   
  146.   SPLINE_LIST_LENGTH (*l)++;
  147.   SPLINE_LIST_DATA (*l) = xrealloc (SPLINE_LIST_DATA (*l),
  148.                                SPLINE_LIST_LENGTH (*l) * sizeof (spline_type));
  149.   LAST_SPLINE_LIST_ELT (*l) = s;
  150. }
  151.  
  152.  
  153. /* Tack the elements in the list S2 onto the end of S1.
  154.    S2 is not changed.  */
  155.  
  156. void
  157. concat_spline_lists (spline_list_type *s1, spline_list_type s2)
  158. {
  159.   unsigned this_spline;
  160.   unsigned new_length;
  161.  
  162.   assert (s1 != NULL);
  163.  
  164.   new_length = SPLINE_LIST_LENGTH (*s1) + SPLINE_LIST_LENGTH (s2);
  165.  
  166.   XRETALLOC (SPLINE_LIST_DATA (*s1), new_length, spline_type);
  167.  
  168.   for (this_spline = 0; this_spline < SPLINE_LIST_LENGTH (s2); this_spline++)
  169.     SPLINE_LIST_ELT (*s1, SPLINE_LIST_LENGTH (*s1)++)
  170.       = SPLINE_LIST_ELT (s2, this_spline);
  171. }
  172.  
  173.  
  174.  
  175. /* Return a new, empty, spline list array.  */
  176.  
  177. spline_list_array_type
  178. new_spline_list_array ()
  179. {
  180.   spline_list_array_type answer;
  181.  
  182.   SPLINE_LIST_ARRAY_DATA (answer) = NULL;
  183.   SPLINE_LIST_ARRAY_LENGTH (answer) = 0;
  184.  
  185.   return answer;
  186. }
  187.  
  188.  
  189. /* Free the storage in a spline list array.  We don't
  190.    want to free the list if it is empty.  */
  191.  
  192. void
  193. free_spline_list_array (spline_list_array_type *spline_list_array)
  194. {
  195.   unsigned this_list;
  196.  
  197.   for (this_list = 0;
  198.        this_list < SPLINE_LIST_ARRAY_LENGTH (*spline_list_array);
  199.        this_list++) 
  200.     free_spline_list (&SPLINE_LIST_ARRAY_ELT (*spline_list_array, this_list));
  201.  
  202.   if (SPLINE_LIST_ARRAY_DATA (*spline_list_array) != NULL)
  203.     safe_free ((address *) &(SPLINE_LIST_ARRAY_DATA (*spline_list_array)));
  204. }
  205.  
  206.  
  207. /* Append the spline S to the list SPLINE_LIST_ARRAY.  */
  208.  
  209. void
  210. append_spline_list (spline_list_array_type *l, spline_list_type s)
  211. {
  212.   SPLINE_LIST_ARRAY_LENGTH (*l)++;
  213.   XRETALLOC (SPLINE_LIST_ARRAY_DATA (*l),
  214.     SPLINE_LIST_ARRAY_LENGTH (*l), spline_list_type);
  215.   LAST_SPLINE_LIST_ARRAY_ELT (*l) = s;
  216. }
  217.