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.
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).
7 #include "curves.h"
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, cpcurr, cpnext;
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 }
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;
108         // error out on various bogus conditions
109         if (xlevel < 0 || ylevel < 0 || xlevel > 16 || ylevel > 16 || cpwidth < 3 || cpheight < 3)
110                 return;
112         xstep = 1 << xlevel;
113         ystep = 1 << ylevel;
114         finalwidth = (cpwidth - 1) * xstep + 1;
115         finalheight = (cpheight - 1) * ystep + 1;
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;
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         }
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++;
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 }