// this code written by Forest Hale, on 2003-08-23, and placed into public domain
// this code deals with quadratic splines (minimum of 3 points), the same kind used in Quake3 maps.
-// 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).
+// 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 bspline (4 control points, cubic bspline), bsplines are the generalization of the bezier spline to support dimensions other than just cubic.
+// this implements Quadratic BSpline surfaces
#include <math.h>
#include "curves.h"
#include "zone.h"
#if 0
-void QuadraticSplineSubdivideFloat(int inpoints, int components, const float *in, int instride, float *out, int outstride)
+void QuadraticBSplineSubdivideFloat(int inpoints, int components, const float *in, int instride, float *out, int outstride)
{
int s;
// the input (control points) is read as a stream of points, and buffered
{
// more components can be handled, but slowly, by calling self multiple times...
for (c = 0;c < components;c++, in++, out++)
- QuadraticSplineSubdivideFloat(inpoints, 1, in, instride, out, outstride);
+ QuadraticBSplineSubdivideFloat(inpoints, 1, in, instride, out, outstride);
return;
}
for (c = 0;c < components;c++)
// note: out must have enough room!
// (see finalwidth/finalheight calcs below)
-void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
+void QuadraticBSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
{
int finalwidth, finalheight, xstep, ystep, x, y, c;
float *o;
if (xlevel == 1 && ylevel == 0)
{
for (y = 0;y < finalheight;y++)
- QuadraticSplineSubdivideFloat(cpwidth, components, in + y * cpwidth * components, sizeof(float) * components, out + y * finalwidth * components, sizeof(float) * components);
+ QuadraticBSplineSubdivideFloat(cpwidth, components, in + y * cpwidth * components, sizeof(float) * components, out + y * finalwidth * components, sizeof(float) * components);
return;
}
if (xlevel == 0 && ylevel == 1)
{
for (x = 0;x < finalwidth;x++)
- QuadraticSplineSubdivideFloat(cpheight, components, in + x * components, sizeof(float) * cpwidth * components, out + x * components, sizeof(float) * finalwidth * components);
+ QuadraticBSplineSubdivideFloat(cpheight, components, in + x * components, sizeof(float) * cpwidth * components, out + x * components, sizeof(float) * finalwidth * components);
return;
}
{
xstep >>= 1;
for (y = 0;y < finalheight;y += ystep)
- QuadraticSplineSubdivideFloat(cpwidth, components, out + y * finalwidth * components, sizeof(float) * xstep * 2 * components, out + y * finalwidth * components, sizeof(float) * xstep * components);
+ QuadraticBSplineSubdivideFloat(cpwidth, components, out + y * finalwidth * components, sizeof(float) * xstep * 2 * components, out + y * finalwidth * components, sizeof(float) * xstep * components);
cpwidth = (cpwidth - 1) * 2 + 1;
}
if (ystep > 1)
{
ystep >>= 1;
for (x = 0;x < finalwidth;x += xstep)
- QuadraticSplineSubdivideFloat(cpheight, components, out + x * components, sizeof(float) * ystep * 2 * finalwidth * components, out + x * components, sizeof(float) * ystep * finalwidth * components);
+ QuadraticBSplineSubdivideFloat(cpheight, components, out + x * components, sizeof(float) * ystep * 2 * finalwidth * components, out + x * components, sizeof(float) * ystep * finalwidth * components);
cpheight = (cpheight - 1) * 2 + 1;
}
}
}
#elif 1
-void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
+void QuadraticBSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
{
int c, x, y, outwidth, outheight, halfstep, xstep, ystep;
float prev, curr, next;
// fetch next control point
next = out[((y + ystep) * outwidth + x) * components + c];
// flatten central control point
- out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;;
+ out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;
// create following midpoint
out[((y + halfstep) * outwidth + x) * components + c] = (curr + next) * 0.5f;
}
// fetch next control point
next = out[(y * outwidth + (x + xstep)) * components + c];
// flatten central control point
- out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;;
+ out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;
}
}
}
// fetch next control point
next = out[((y + ystep) * outwidth + x) * components + c];
// flatten central control point
- out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;;
+ out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;
}
}
}
}
#else
// unfinished code
-void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
+void QuadraticBSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
{
int outwidth, outheight;
outwidth = ((cpwidth - 1) << xlevel) + 1;
0.00000 0.12500 0.21875 0.31250 0.37500 0.43750 0.46875 0.50000 0.50000 0.50000 0.46875 0.43750 0.37500 0.31250 0.21875 0.12500 0.00000 deviation: not available
*/
-float QuadraticSplinePatchLargestDeviationOnX(int cpwidth, int cpheight, int components, const float *in)
+float QuadraticBSplinePatchLargestDeviationOnX(int cpwidth, int cpheight, int components, const float *in)
{
int c, x, y;
const float *cp;
return (float)sqrt(bestsquareddeviation);
}
-float QuadraticSplinePatchLargestDeviationOnY(int cpwidth, int cpheight, int components, const float *in)
+float QuadraticBSplinePatchLargestDeviationOnY(int cpwidth, int cpheight, int components, const float *in)
{
int c, x, y;
const float *cp;
return (float)sqrt(bestsquareddeviation);
}
-int QuadraticSplinePatchSubdivisionLevelForDeviation(float deviation, float level1tolerance, int levellimit)
+int QuadraticBSplinePatchSubdivisionLevelForDeviation(float deviation, float level1tolerance, int levellimit)
{
int level;
// count the automatic flatten step which reduces deviation by 50%
return level;
}
-int QuadraticSplinePatchSubdivisionLevelOnX(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit)
+int QuadraticBSplinePatchSubdivisionLevelOnX(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit)
{
- return QuadraticSplinePatchSubdivisionLevelForDeviation(QuadraticSplinePatchLargestDeviationOnX(cpwidth, cpheight, components, in), level1tolerance, levellimit);
+ return QuadraticBSplinePatchSubdivisionLevelForDeviation(QuadraticBSplinePatchLargestDeviationOnX(cpwidth, cpheight, components, in), level1tolerance, levellimit);
}
-int QuadraticSplinePatchSubdivisionLevelOnY(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit)
+int QuadraticBSplinePatchSubdivisionLevelOnY(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit)
{
- return QuadraticSplinePatchSubdivisionLevelForDeviation(QuadraticSplinePatchLargestDeviationOnY(cpwidth, cpheight, components, in), level1tolerance, levellimit);
+ return QuadraticBSplinePatchSubdivisionLevelForDeviation(QuadraticBSplinePatchLargestDeviationOnY(cpwidth, cpheight, components, in), level1tolerance, levellimit);
}
/*
- d = a * (1 - 2 * t + t * t) + b * (2 * t - 2 * t * t) + c * t * t;
- d = a * (1 + t * t + -2 * t) + b * (2 * t + -2 * t * t) + c * t * t;
- d = a * 1 + a * t * t + a * -2 * t + b * 2 * t + b * -2 * t * t + c * t * t;
- d = a * 1 + (a * t + a * -2) * t + (b * 2 + b * -2 * t) * t + (c * t) * t;
- d = a + ((a * t + a * -2) + (b * 2 + b * -2 * t) + (c * t)) * t;
- d = a + (a * (t - 2) + b * 2 + b * -2 * t + c * t) * t;
- d = a + (a * (t - 2) + b * 2 + (b * -2 + c) * t) * t;
- d = a + (a * (t - 2) + b * 2 + (c + b * -2) * t) * t;
- d = a + a * (t - 2) * t + b * 2 * t + (c + b * -2) * t * t;
- d = a * (1 + (t - 2) * t) + b * 2 * t + (c + b * -2) * t * t;
- d = a * (1 + (t - 2) * t) + b * 2 * t + c * t * t + b * -2 * t * t;
- d = a * 1 + a * (t - 2) * t + b * 2 * t + c * t * t + b * -2 * t * t;
- d = a * 1 + a * t * t + a * -2 * t + b * 2 * t + c * t * t + b * -2 * t * t;
- d = a * (1 - 2 * t + t * t) + b * 2 * t + c * t * t + b * -2 * t * t;
- d = a * (1 - 2 * t) + a * t * t + b * 2 * t + c * t * t + b * -2 * t * t;
- d = a + a * -2 * t + a * t * t + b * 2 * t + c * t * t + b * -2 * t * t;
- d = a + a * -2 * t + a * t * t + b * 2 * t + b * -2 * t * t + c * t * t;
- d = a + a * -2 * t + a * t * t + b * 2 * t + b * -2 * t * t + c * t * t;
- d = a + a * -2 * t + b * 2 * t + b * -2 * t * t + a * t * t + c * t * t;
- d = a + a * -2 * t + b * 2 * t + (a + c + b * -2) * t * t;
- d = a + (a * -2 + b * 2) * t + (a + c + b * -2) * t * t;
- d = a + ((a * -2 + b * 2) + (a + c + b * -2) * t) * t;
- d = a + ((b + b - a - a) + (a + c - b - b) * t) * t;
- d = a + (b + b - a - a) * t + (a + c - b - b) * t * t;
- d = a + (b - a) * 2 * t + (a + c - b * 2) * t * t;
- d = a + (b - a) * 2 * t + (a - b + c - b) * t * t;
-
- d = in[0] + (in[1] - in[0]) * 2 * t + (in[0] - in[1] + in[2] - in[1]) * t * t;
+ // 1: flat (0th dimension)
+ o = a
+ // 2: linear (1st dimension)
+ o = a * (1 - t) + b * t
+ // 3: quadratic bspline (2nd dimension)
+ o = a * (1 - t) * (1 - t) + 2 * b * (1 - t) * t + c * t * t
+ // 4: cubic (bezier) bspline (3rd dimension)
+ o = a * (1 - t) * (1 - t) * (1 - t) + 3 * b * (1 - t) * (1 - t) * t + 3 * c * (1 - t) * t * t + d * t * t * t
+ // 5: quartic bspline (4th dimension)
+ o = a * (1 - t) * (1 - t) * (1 - t) * (1 - t) + 4 * b * (1 - t) * (1 - t) * (1 - t) * t + 6 * c * (1 - t) * (1 - t) * t * t + 4 * d * (1 - t) * t * t * t + e * t * t * t * t
+
+ // n: arbitrary dimension bspline
+double factorial(int n)
+{
+ int i;
+ double f;
+ f = 1;
+ for (i = 1;i < n;i++)
+ f = f * i;
+ return f;
+}
+double bsplinesample(int dimensions, double t, double *param)
+{
+ double o = 0;
+ for (i = 0;i < dimensions + 1;i++)
+ o += param[i] * factorial(dimensions)/(factorial(i)*factorial(dimensions-i)) * pow(t, i) * pow(1 - t, dimensions - i);
+}
*/