查看: 8454|回复: 8

均匀三次B样条曲线(Uniform Cubic B-Spline)(附Python实现) [复制链接]

ミルク

正式会员

Rank: 4

电梯直达

楼主

发表于 2012-7-28 20:56:58 |只看该作者 |正序浏览

引言

优点

B-spline curves require more information (i.e., the degree of the curve and a knot vector) and a more complex theory than Bézier curves. But, it has more advantages to offset this shortcoming. First, a B-spline curve can be a Bézier curve. Second, B-spline curves satisfy all important properties that Bézier curves have. Third, B-spline curves provide more control flexibility than Bézier curves can do. For example, the degree of a B-spline curve is separated from the number of control points. More precisely, we can use lower degree curves and still maintain a large number of control points. We can change the position of a control point without globally changing the shape of the whole curve (local modification property). Since B-spline curves satisfy the strong convex hull property, they have a finer shape control. Moreover, there are other techniques for designing and editing the shape of a curve such as changing knots.

详细
http://escience.anu.edu.au/lectu ... ineVsBezier.en.html

曲线绘制Demo
http://www.cs.uwaterloo.ca/~r3fraser/splines/bspline.html

计算方法
uniform cubic b-spline.png

或者

参考
http://www.codeproject.com/Articles/16689/Bspline-in-C

正文

简单来说就是均匀三次B样条曲线有很多优势，也比较好用。
于是用Python实现了一下。

面向对象版本

class UCBSpline:
def __init__(self, p):
self.p = p # tuple or list of control points (x, y)
n = len(p) - 1 # control points p0 ~ pn, i.e., p[0] ~ p[n]
m = 3 + n + 1 # knots vector u0 ~um, i.e., u[0] ~ u[m]
self.m = m
step = 1 / (m - 2 * 3)
self.u = 3 * [0] + [_u * step for _u in range(m - 2 * 3 + 1)] + [1] * 3 # knots vector
num = n + 1 - 3 # number of curve segments
self.a1 = []
self.a2 = []
self.a3 = []
self.a4 = []
self.b1 = []
self.b2 = []
self.b3 = []
self.b4 = []
for i in range(num):
self.a1.append((-p[i][0] + 3 * p[i + 1][0] - 3 * p[i + 2][0] + p[i + 3][0]) / 6.0)
self.a2.append((3 * p[i][0] - 6 * p[i + 1][0] + 3 * p[i + 2][0]) / 6.0)
self.a3.append((-p[i][0] + p[i + 2][0]) / 2.0)
self.a4.append((p[i][0] + 4 * p[i + 1][0] + p[i + 2][0]) / 6.0)
self.b1.append((-p[i][1] + 3 * p[i + 1][1] - 3 * p[i + 2][1] + p[i + 3][1]) / 6.0)
self.b2.append((3 * p[i][1] - 6 * p[i + 1][1] + 3 * p[i + 2][1]) / 6.0)
self.b3.append((-p[i][1] + p[i + 2][1]) / 2.0)
self.b4.append((p[i][1] + 4 * p[i + 1][1] + p[i + 2][1]) / 6.0)
def __call__(self, t):
if t < 0 or t >= 1:
return None
else:
for i in range(3, self.m - 3):
if self.u[i] <= t and t < self.u[i + 1]:
break
idx = i - 3
a1 = self.a1[idx]
a2 = self.a2[idx]
a3 = self.a3[idx]
a4 = self.a4[idx]
b1 = self.b1[idx]
b2 = self.b2[idx]
b3 = self.b3[idx]
b4 = self.b4[idx]
t = (t - self.u[i]) / (self.u[i + 1] - self.u[i])
return (a1 * t * t * t + a2 * t * t + a3 * t + a4,
b1 * t * t * t + b2 * t * t + b3 * t + b4, 255) # 255 is the point's alpha value, to meet the TCAX's point structure requirement ((x, y, a), (x, y, a), ...)

复制代码

用法示例

num = 1000
step = 1 / num
points = []
#P = [(200, 500), (300, 100), (700, 100), (400, 500), (600, 700), (800, 400), (700, 200)]
P = [(0, 100), (100, 0), (200, 0), (300, 100), (400, 200), (500, 200), (600, 100), (400, 400), (700, 50), (800, 200)]
ucb = UCBSpline(P)
for i in range(num):
t = i * step
points.append(ucb(t))

复制代码

普通版本

def UniformCubicBSpline(p, t):
n = len(p) - 1 # control points p0 ~ pn, i.e., p[0] ~ p[n]
m = 3 + n + 1 # knots vector u0 ~um, i.e., u[0] ~ u[m]
step = 1 / (m - 2 * 3)
u = 3 * [0] + [_u * step for _u in range(m - 2 * 3 + 1)] + [1] * 3
if t < 0 or t >= 1:
return None
else:
for i in range(3, m - 3):
if u[i] <= t and t < u[i + 1]:
break
return UniformCubicBSpline_Calc(p[i - 3], p[i - 2], p[i - 1], p[i], (t - u[i]) / (u[i + 1] - u[i])) # can use either calc or calc2
def UniformCubicBSpline_Calc(p1, p2, p3, p4, t):
a1 = (-p1[0] + 3 * p2[0] - 3 * p3[0] + p4[0]) / 6.0
a2 = (3 * p1[0] - 6 * p2[0] + 3 * p3[0]) / 6.0
a3 = (-p1[0] + p3[0]) / 2.0
a4 = (p1[0] + 4 * p2[0] + p3[0]) / 6.0
b1 = (-p1[1] + 3 * p2[1] - 3 * p3[1] + p4[1]) / 6.0
b2 = (3 * p1[1] - 6 * p2[1] + 3 * p3[1]) / 6.0
b3 = (-p1[1] + p3[1]) / 2.0
b4 = (p1[1] + 4 * p2[1] + p3[1]) / 6.0
return (a1 * t * t * t + a2 * t * t + a3 * t + a4,
b1 * t * t * t + b2 * t * t + b3 * t + b4, 255) # 255 is the point's alpha value, to meet the TCAX's point structure requirement ((x, y, a), (x, y, a), ...)
def UniformCubicBSpline_Calc2(p1, p2, p3, p4, t):
A1 = (1 - t) * (1 - t) * (1 - t) / 6.0
A2 = (3 * t * t * t - 6 * t * t + 4) / 6.0
A3 = (-3 * t * t * t + 3 * t * t + 3 * t + 1) / 6.0
A4 = t * t * t / 6.0
return (A1 * p1[0] + A2 * p2[0] + A3 * p3[0] + A4 * p4[0],
A1 * p1[1] + A2 * p2[1] + A3 * p3[1] + A4 * p4[1], 255) # 255 is the point's alpha value, to meet the TCAX's point structure requirement ((x, y, a), (x, y, a), ...)

复制代码

用法示例

num = 1000
step = 1 / num
points = []
#P = [(200, 500), (300, 100), (700, 100), (400, 500), (600, 700), (800, 400), (700, 200)]
P = [(0, 100), (100, 0), (200, 0), (300, 100), (400, 200), (500, 200), (600, 100), (400, 400), (700, 50), (800, 200)]
for i in range(num):
t = i * step
points.append(UniformCubicBSpline(P, t))

复制代码

效果