home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / i / iritsm3s.zip / cagd_lib / cbzreval.c < prev    next >
C/C++ Source or Header  |  1991-05-18  |  8KB  |  236 lines
  1. /******************************************************************************
  2. * CBzrEval.c - Bezier curves handling routines - evaluation routines.          *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Mar. 90.                          *
  5. ******************************************************************************/
  6.  
  7. #ifdef __MSDOS__
  8. #include <stdlib.h>
  9. #endif /* __MSDOS__ */
  10.  
  11. #include <ctype.h>
  12. #include <stdio.h>
  13. #include <string.h>
  14. #include "cagd_loc.h"
  15.  
  16. static int BezierCacheEnabled = FALSE;
  17. static int CacheFineNess = 0, PowerCacheFineNess;
  18. static CagdRType *BezierCache[CAGD_MAX_BEZIER_CACHE_ORDER + 1]
  19.                 [CAGD_MAX_BEZIER_CACHE_ORDER + 1];
  20.  
  21. static int IChooseK[CAGD_MAX_BEZIER_CACHE_ORDER + 1]
  22.            [CAGD_MAX_BEZIER_CACHE_ORDER + 1] =
  23. {
  24.     {    1,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0  },
  25.     {    1,    1,    0,    0,    0,    0,    0,    0,    0,    0,    0  },
  26.     {    1,    2,    1,    0,    0,    0,    0,    0,    0,    0,    0  },
  27.     {    1,    3,    3,    1,    0,    0,    0,    0,    0,    0,    0  },
  28.     {    1,    4,    6,    4,    1,    0,    0,    0,    0,    0,    0  },
  29.     {    1,    5,   10,   10,    5,    1,    0,    0,    0,    0,    0  },
  30.     {    1,    6,   15,   20,   15,    6,    1,    0,    0,    0,    0  },
  31.     {    1,    7,   21,   35,   35,   21,    7,    1,    0,    0,    0  },
  32.     {    1,    8,   28,   56,   70,   56,   28,    8,    1,    0,    0  },
  33.     {    1,    9,   36,   84,  126,  126,   84,   36,    9,    1,    0  },
  34.     {    1,   10,   45,  120,  210,  252,  210,  120,   45,   10,    1  }
  35. };
  36.  
  37. static CagdRType BzrCrvEvalFuncAux(int i, int k, CagdRType t);
  38.  
  39. /******************************************************************************
  40. * Sets the bezier sampling cache - if enabled, a bezier can be evaluated      *
  41. * directly from pre sampled basis function.                      *
  42. ******************************************************************************/
  43. void BzrCrvSetCache(int FineNess, CagdBType EnableCache)
  44. {
  45.     int i, j, k;
  46.  
  47.     if (BezierCacheEnabled == EnableCache && FineNess == CacheFineNess)
  48.     return;
  49.  
  50.     if (BezierCacheEnabled) {
  51.     /* Free old cache if was one. */
  52.     for (k = 2; k <= CAGD_MAX_BEZIER_CACHE_ORDER; k++)
  53.         for (i = 0; i < k; i++)
  54.         if (BezierCache[k][i] != NULL) {
  55.             CagdFree((VoidPtr) BezierCache[k][i]);
  56.             BezierCache[k][i] = NULL;
  57.         }
  58.     }
  59.  
  60.     if ((BezierCacheEnabled = EnableCache) != FALSE) {
  61.     /* Allocate the new cache and initalize it: */
  62.     if (FineNess < 2) FineNess = 2;
  63.     if (FineNess > CAGD_MAX_BEZIER_CACHE_FINENESS)
  64.         FineNess = CAGD_MAX_BEZIER_CACHE_FINENESS;
  65.     CacheFineNess = FineNess;
  66.     PowerCacheFineNess = 1 << FineNess;
  67.  
  68.     for (k = 2; k <= CAGD_MAX_BEZIER_CACHE_ORDER; k++)/* For all orders. */
  69.         for (i = 0; i < k; i++) {      /* Allocate and set all basis func. */
  70.         BezierCache[k][i] = (CagdRType *)
  71.             CagdMalloc(sizeof(CagdRType) * PowerCacheFineNess);
  72.         for (j = 0; j < PowerCacheFineNess; j++)
  73.             BezierCache[k][i][j] = BzrCrvEvalFuncAux(i, k,
  74.                 ((CagdRType) j) / (PowerCacheFineNess - 1));
  75.         }
  76.     }
  77. }
  78.  
  79. /******************************************************************************
  80. * Assumes Vec holds control points for scalar bezier curve of order Order,    *
  81. * and evaluates and returns that curve value at parameter value t.          *
  82. * Vec is incremented by VecInc (usually by 1) after each iteration.          *
  83. ******************************************************************************/
  84. CagdRType BzrCrvEvalVecAtParam(CagdRType *Vec, int VecInc, int Order, CagdRType t)
  85. {
  86.     int i;
  87.     CagdRType R = 0.0;
  88.  
  89.     if (VecInc == 1)
  90.     for (i = 0; i < Order; i++)
  91.         R += BzrCrvEvalFuncAux(i, Order, t) * *Vec++;
  92.     else
  93.     for (i = 0; i < Order; i++) {
  94.         R += BzrCrvEvalFuncAux(i, Order, t) * *Vec;
  95.         Vec += VecInc;
  96.     }
  97.  
  98.     return R;
  99. }
  100.  
  101. /******************************************************************************
  102. * Returns a pointer to a static data, holding the value of the curve at given *
  103. * parametric location t. The curve is assumed to be Bezier.              *
  104. ******************************************************************************/
  105. CagdRType *BzrCrvEvalAtParam(CagdCrvStruct *Crv, CagdRType t)
  106. {
  107.     static CagdRType Pt[CAGD_MAX_PT_COORD];
  108.     CagdBType
  109.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  110.     int i, j,
  111.     k = Crv -> Order,
  112.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  113.     CagdRType B;
  114.  
  115.     for (j = IsNotRational; j <= MaxCoord; j++) Pt[j] = 0.0;
  116.  
  117.     for (i = 0; i < k; i++) {
  118.     B = BzrCrvEvalFuncAux(i, k, t);
  119.     for (j = IsNotRational; j <= MaxCoord; j++)
  120.         Pt[j] += B * Crv -> Points[j][i];
  121.     }
  122.  
  123.     return Pt;
  124. }
  125.  
  126. /******************************************************************************
  127. * Samples the curves at FineNess location equally spaced in the Bezier        *
  128. * parametric domain [0..1]. If Cache is enabled, and FineNess is power of     *
  129. * two, upto or equal to CacheFineNess, the cache is used, otherwise the       *
  130. * points are evaluated manually for each of the samples.              *
  131. * Data is saved at the Points array of vectors (according to Curve PType),    *
  132. * each vector is assumed to be allocated for FineNess CagdRType points.          *
  133. ******************************************************************************/
  134. void BzrCrvEvalToPolyline(CagdCrvStruct *Crv, int FineNess,
  135.                             CagdRType *Points[])
  136. {
  137.     CagdBType
  138.     UseCache = BezierCacheEnabled && FineNess == CacheFineNess,
  139.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  140.     int i, j, Count,
  141.     k = Crv -> Order,
  142.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  143.     CagdRType B;
  144.  
  145.     if (UseCache) {
  146.     for (Count = 0; Count < PowerCacheFineNess; Count++) {
  147.         for (j = IsNotRational; j <= MaxCoord; j++) Points[j][Count] = 0.0;
  148.         for (i = 0; i < k; i++) {
  149.         B = BezierCache[k][i][Count];
  150.         for (j = IsNotRational; j <= MaxCoord; j++)
  151.             Points[j][Count] += B * Crv -> Points[j][i];
  152.         }
  153.     }
  154.     }
  155.     else {
  156.     FineNess = 1 << FineNess;
  157.     for (Count = 0; Count < FineNess; Count++) {
  158.         for (j = IsNotRational; j <= MaxCoord; j++) Points[j][Count] = 0.0;
  159.         for (i = 0; i < k; i++) {
  160.         B = BzrCrvEvalFuncAux(i, k,
  161.                       ((CagdRType) Count) / (FineNess - 1));
  162.         for (j = IsNotRational; j <= MaxCoord; j++)
  163.             Points[j][Count] += Crv -> Points[j][i] * B;
  164.         }
  165.     }
  166.     }
  167. }
  168.  
  169. /******************************************************************************
  170. * Evaluate the i bezier function of order k, at parametric value t          *
  171. * (t in [0..1]).                                  *
  172. * This function is:           i     k - i - 1          i              *
  173. *            Bi,k(t) = ( ) * t          * (1 - t)              *
  174. *                   k                          *
  175. ******************************************************************************/
  176. static CagdRType BzrCrvEvalFuncAux(int i, int k, CagdRType t)
  177. {
  178.     if (APX_EQ(t, 0.0))
  179.     return (CagdRType) (i == 0);
  180.     else if (APX_EQ(t, 1.0))
  181.     return (CagdRType) (i == k - 1);
  182.     else
  183.     return (CagdRType) IChooseK[k - 1][i] *
  184.            pow(1.0 - t, k - i - 1.0) * pow(t, (CagdRType) i);
  185. }
  186.  
  187. #ifdef K_CHOOSE_I_GEN
  188.  
  189. /******************************************************************************
  190. * Evaluate the following:                              *
  191. *             k         k!                          *
  192. *            ( ) = -------------                      *
  193. *             i    i! * (k - i)!                      *
  194. ******************************************************************************/
  195. static int IChooseKGenOne(int i, int k)
  196. {
  197.     int j;
  198.     long c = 1;
  199.  
  200.     if ((k >> 1) > i) {                /* i is less than half of k: */
  201.     for (j = k - i + 1; j <= k; j++) c *= j;
  202.     for (j = 2; j <= i; j++) c /= j;
  203.     }
  204.     else {
  205.     for (j = i + 1; j <= k; j++) c *= j;
  206.     for (j = 2; j <= k - i; j++) c /= j;
  207.     }
  208.  
  209.     return (int) c;
  210. }
  211.  
  212. /******************************************************************************
  213. * Evaluate IChooseK for all possiblities and print them for the              *
  214. * IChooseK table defined in the beginning of this file.                  *
  215. ******************************************************************************/
  216. void IChooseKGen(void)
  217. {
  218.     int i, j;
  219.  
  220.     for (i = 0; i <= MAX_BEZIER_CACHE_ORDER; i++) {
  221.     printf(" },\n    {");
  222.     for (j = 0; j <= MAX_BEZIER_CACHE_ORDER; j++)
  223.         printf(" %4d,", j <= i ? IChooseKGenOne(j ,i) : 0);
  224.     }
  225. }
  226.  
  227. /******************************************************************************
  228. * main to create the table in the befinning of this file.              *
  229. ******************************************************************************/
  230. void main(void)
  231. {
  232.     IChooseKGen();
  233. }
  234.  
  235. #endif /* K_CHOOSE_I_GEN */
  236.