curves.c

   1
   2 // this code written by Forest Hale, on 2003-08-23, and placed into public domain
   3 // this code deals with quadratic splines (minimum of 3 points), the same kind used in Quake3 maps.
   4
   5 // LordHavoc's rant on misuse of the name 'bezier': many people seem to think that bezier is a generic term for splines, but it is not, it is a term for a specific type of spline (minimum of 4 control points, cubic spline).
   6
   7 #include "curves.h"
   8
   9 void QuadraticSplineSubdivideFloat(int inpoints, int components, const float *in, int instride, float *out, int outstride)
  10 {
  11         int s;
  12         // the input (control points) is read as a stream of points, and buffered
  13         // by the cpprev, cpcurr, and cpnext variables (to allow subdivision in
  14         // overlapping memory buffers, even subdivision in-place with pre-spaced
  15         // control points in the buffer)
  16         // the output (resulting curve) is written as a stream of points
  17         // this subdivision is meant to be repeated until the desired flatness
  18         // level is reached
  19         if (components == 1 && instride == (int)sizeof(float) && outstride == instride)
  20         {
  21                 // simple case, single component and no special stride
  22                 float cpprev0 = 0, cpcurr0 = 0, cpnext0;
  23                 cpnext0 = *in++;
  24                 for (s = 0;s < inpoints - 1;s++)
  25                 {
  26                         cpprev0 = cpcurr0;
  27                         cpcurr0 = cpnext0;
  28                         if (s < inpoints - 1)
  29                                 cpnext0 = *in++;
  30                         if (s > 0)
  31                         {
  32                                 // 50% flattened control point
  33                                 // cp1 = average(cp1, average(cp0, cp2));
  34                                 *out++ = (cpcurr0 + (cpprev0 + cpnext0) * 0.5f) * 0.5f;
  35                         }
  36                         else
  37                         {
  38                                 // copy the control point directly
  39                                 *out++ = cpcurr0;
  40                         }
  41                         // midpoint
  42                         // mid = average(cp0, cp1);
  43                         *out++ = (cpcurr0 + cpnext0) * 0.5f;
  44                 }
  45                 // copy the final control point
  46                 *out++ = cpnext0;
  47         }
  48         else
  49         {
  50                 // multiple components or stride is used (complex case)
  51                 int c;
  52                 float cpprev[4], cpcurr[4], cpnext[4];
  53                 // check if there are too many components for the buffers
  54                 if (components > 1)
  55                 {
  56                         // more components can be handled, but slowly, by calling self multiple times...
  57                         for (c = 0;c < components;c++, in++, out++)
  58                                 QuadraticSplineSubdivideFloat(inpoints, 1, in, instride, out, outstride);
  59                         return;
  60                 }
  61                 for (c = 0;c < components;c++)
  62                         cpnext[c] = in[c];
  63                 (unsigned char *)in += instride;
  64                 for (s = 0;s < inpoints - 1;s++)
  65                 {
  66                         for (c = 0;c < components;c++)
  67                                 cpprev[c] = cpcurr[c];
  68                         for (c = 0;c < components;c++)
  69                                 cpcurr[c] = cpnext[c];
  70                         for (c = 0;c < components;c++)
  71                                 cpnext[c] = in[c];
  72                         (unsigned char *)in += instride;
  73                         // the end points are copied as-is
  74                         if (s > 0)
  75                         {
  76                                 // 50% flattened control point
  77                                 // cp1 = average(cp1, average(cp0, cp2));
  78                                 for (c = 0;c < components;c++)
  79                                         out[c] = (cpcurr[c] + (cpprev[c] + cpnext[c]) * 0.5f) * 0.5f;
  80                         }
  81                         else
  82                         {
  83                                 // copy the control point directly
  84                                 for (c = 0;c < components;c++)
  85                                         out[c] = cpcurr[c];
  86                         }
  87                         (unsigned char *)out += outstride;
  88                         // midpoint
  89                         // mid = average(cp0, cp1);
  90                         for (c = 0;c < components;c++)
  91                                 out[c] = (cpcurr[c] + cpnext[c]) * 0.5f;
  92                         (unsigned char *)out += outstride;
  93                 }
  94                 // copy the final control point
  95                 for (c = 0;c < components;c++)
  96                         out[c] = cpnext[c];
  97                 //(unsigned char *)out += outstride;
  98         }
  99 }
 100
 101 // note: out must have enough room!
 102 // (see finalwidth/finalheight calcs below)
 103 void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
 104 {
 105         int finalwidth, finalheight, xstep, ystep, x, y, c;
 106         float *o;
 107
 108         // error out on various bogus conditions
 109         if (xlevel < 0 || ylevel < 0 || xlevel > 16 || ylevel > 16 || cpwidth < 3 || cpheight < 3)
 110                 return;
 111
 112         xstep = 1 << xlevel;
 113         ystep = 1 << ylevel;
 114         finalwidth = (cpwidth - 1) * xstep + 1;
 115         finalheight = (cpheight - 1) * ystep + 1;
 116
 117         for (y = 0;y < finalheight;y++)
 118                 for (x = 0;x < finalwidth;x++)
 119                         for (c = 0, o = out + (y * finalwidth + x) * components;c < components;c++)
 120                                 o[c] = 0;
 121
 122         if (xlevel == 1 && ylevel == 0)
 123         {
 124                 for (y = 0;y < finalheight;y++)
 125                         QuadraticSplineSubdivideFloat(cpwidth, components, in + y * cpwidth * components, sizeof(float) * components, out + y * finalwidth * components, sizeof(float) * components);
 126                 return;
 127         }
 128         if (xlevel == 0 && ylevel == 1)
 129         {
 130                 for (x = 0;x < finalwidth;x++)
 131                         QuadraticSplineSubdivideFloat(cpheight, components, in + x * components, sizeof(float) * cpwidth * components, out + x * components, sizeof(float) * finalwidth * components);
 132                 return;
 133         }
 134
 135         // copy control points into correct positions in destination buffer
 136         for (y = 0;y < finalheight;y += ystep)
 137                 for (x = 0;x < finalwidth;x += xstep)
 138                         for (c = 0, o = out + (y * finalwidth + x) * components;c < components;c++)
 139                                 o[c] = *in++;
 140
 141         // subdivide in place in the destination buffer
 142         while (xstep > 1 || ystep > 1)
 143         {
 144                 if (xstep > 1)
 145                 {
 146                         xstep >>= 1;
 147                         for (y = 0;y < finalheight;y += ystep)
 148                                 QuadraticSplineSubdivideFloat(cpwidth, components, out + y * finalwidth * components, sizeof(float) * xstep * 2 * components, out + y * finalwidth * components, sizeof(float) * xstep * components);
 149                         cpwidth = (cpwidth - 1) * 2 + 1;
 150                 }
 151                 if (ystep > 1)
 152                 {
 153                         ystep >>= 1;
 154                         for (x = 0;x < finalwidth;x += xstep)
 155                                 QuadraticSplineSubdivideFloat(cpheight, components, out + x * components, sizeof(float) * ystep * 2 * finalwidth * components, out + x * components, sizeof(float) * ystep * finalwidth * components);
 156                         cpheight = (cpheight - 1) * 2 + 1;
 157                 }
 158         }
 159 }
 160
 161