TCAX 字幕特效制作工具官方论坛 | ASS | TCAS | Python | Aegisub | Lua

标题: 均匀三次B样条曲线(Uniform Cubic B-Spline)(附Python实现) [打印本页]
作者: ミルク    时间: 2012-7-28 20:56:58     标题: 均匀三次B样条曲线(Uniform Cubic B-Spline)(附Python实现)

引言

优点
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
或者
ucbs.png
参考
http://www.codeproject.com/Articles/16689/Bspline-in-C


正文

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

面向对象版本
  1. class UCBSpline:
  2.     def __init__(self, p):
  3.         self.p = p      # tuple or list of control points (x, y)
  4.         n = len(p) - 1     # control points p0 ~ pn, i.e., p[0] ~ p[n]
  5.         m = 3 + n + 1      # knots vector u0 ~um, i.e., u[0] ~ u[m]
  6.         self.m = m
  7.         step = 1 / (m - 2 * 3)
  8.         self.u = 3 * [0] + [_u * step for _u in range(m - 2 * 3 + 1)] + [1] * 3     # knots vector
  9.         num = n + 1 - 3     # number of curve segments
  10.         self.a1 = []
  11.         self.a2 = []
  12.         self.a3 = []
  13.         self.a4 = []
  14.         self.b1 = []
  15.         self.b2 = []
  16.         self.b3 = []
  17.         self.b4 = []
  18.         for i in range(num):
  19.             self.a1.append((-p[i][0] + 3 * p[i + 1][0] - 3 * p[i + 2][0] + p[i + 3][0]) / 6.0)
  20.             self.a2.append((3 * p[i][0] - 6 * p[i + 1][0] + 3 * p[i + 2][0]) / 6.0)
  21.             self.a3.append((-p[i][0] + p[i + 2][0]) / 2.0)
  22.             self.a4.append((p[i][0] + 4 * p[i + 1][0] + p[i + 2][0]) / 6.0)
  23.             self.b1.append((-p[i][1] + 3 * p[i + 1][1] - 3 * p[i + 2][1] + p[i + 3][1]) / 6.0)
  24.             self.b2.append((3 * p[i][1] - 6 * p[i + 1][1] + 3 * p[i + 2][1]) / 6.0)
  25.             self.b3.append((-p[i][1] + p[i + 2][1]) / 2.0)
  26.             self.b4.append((p[i][1] + 4 * p[i + 1][1] + p[i + 2][1]) / 6.0)
  27.     def __call__(self, t):
  28.         if t < 0 or t >= 1:
  29.             return None
  30.         else:
  31.             for i in range(3, self.m - 3):
  32.                 if self.u[i] <= t and t < self.u[i + 1]:
  33.                     break
  34.         idx = i - 3
  35.         a1 = self.a1[idx]
  36.         a2 = self.a2[idx]
  37.         a3 = self.a3[idx]
  38.         a4 = self.a4[idx]
  39.         b1 = self.b1[idx]
  40.         b2 = self.b2[idx]
  41.         b3 = self.b3[idx]
  42.         b4 = self.b4[idx]
  43.         t = (t - self.u[i]) / (self.u[i + 1] - self.u[i])
  44.         return (a1 * t * t * t + a2 * t * t + a3 * t + a4,
  45.                 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), ...)
复制代码
用法示例
  1. num = 1000
  2. step = 1 / num
  3. points = []
  4. #P = [(200, 500), (300, 100), (700, 100), (400, 500), (600, 700), (800, 400), (700, 200)]
  5. P = [(0, 100), (100, 0), (200, 0), (300, 100), (400, 200), (500, 200), (600, 100), (400, 400), (700, 50), (800, 200)]
  6. ucb = UCBSpline(P)
  7. for i in range(num):
  8.     t = i * step
  9.     points.append(ucb(t))
复制代码
普通版本
  1. def UniformCubicBSpline(p, t):
  2.     n = len(p) - 1     # control points p0 ~ pn, i.e., p[0] ~ p[n]
  3.     m = 3 + n + 1      # knots vector u0 ~um, i.e., u[0] ~ u[m]
  4.     step = 1 / (m - 2 * 3)
  5.     u = 3 * [0] + [_u * step for _u in range(m - 2 * 3 + 1)] + [1] * 3
  6.     if t < 0 or t >= 1:
  7.         return None
  8.     else:
  9.         for i in range(3, m - 3):
  10.             if u[i] <= t and t < u[i + 1]:
  11.                 break
  12.     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

  14. def UniformCubicBSpline_Calc(p1, p2, p3, p4, t):
  15.     a1 = (-p1[0] + 3 * p2[0] - 3 * p3[0] + p4[0]) / 6.0
  16.     a2 = (3 * p1[0] - 6 * p2[0] + 3 * p3[0]) / 6.0
  17.     a3 = (-p1[0] + p3[0]) / 2.0
  18.     a4 = (p1[0] + 4 * p2[0] + p3[0]) / 6.0
  19.     b1 = (-p1[1] + 3 * p2[1] - 3 * p3[1] + p4[1]) / 6.0
  20.     b2 = (3 * p1[1] - 6 * p2[1] + 3 * p3[1]) / 6.0
  21.     b3 = (-p1[1] + p3[1]) / 2.0
  22.     b4 = (p1[1] + 4 * p2[1] + p3[1]) / 6.0
  23.     return (a1 * t * t * t + a2 * t * t + a3 * t + a4,
  24.             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), ...)

  26. def UniformCubicBSpline_Calc2(p1, p2, p3, p4, t):
  27.     A1 = (1 - t) * (1 - t) * (1 - t) / 6.0
  28.     A2 = (3 * t * t * t - 6 * t * t + 4) / 6.0
  29.     A3 = (-3 * t * t * t + 3 * t * t + 3 * t + 1) / 6.0
  30.     A4 = t * t * t / 6.0
  31.     return (A1 * p1[0] + A2 * p2[0] + A3 * p3[0] + A4 * p4[0],
  32.             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), ...)
复制代码
用法示例
  1. num = 1000
  2. step = 1 / num
  3. points = []
  4. #P = [(200, 500), (300, 100), (700, 100), (400, 500), (600, 700), (800, 400), (700, 200)]
  5. P = [(0, 100), (100, 0), (200, 0), (300, 100), (400, 200), (500, 200), (600, 100), (400, 400), (700, 50), (800, 200)]
  6. for i in range(num):
  7.     t = i * step
  8.     points.append(UniformCubicBSpline(P, t))
复制代码
效果
Unnamed QQ Screenshot20120728215055.png
Unnamed QQ Screenshot20120728211534.png




图片附件: uniform cubic b-spline.png (2012-7-28 21:05:56, 10.42 KB) / 下载次数 2099
http://tcax.org/forum.php?mod=attachment&aid=NzgwfDcyOTk1ZjQ2fDE3NjIwNjgzNzR8MHww



图片附件: ucbs.png (2012-7-28 21:05:56, 30.57 KB) / 下载次数 2118
http://tcax.org/forum.php?mod=attachment&aid=Nzc5fDRhMWU2NGY5fDE3NjIwNjgzNzR8MHww



图片附件: Unnamed QQ Screenshot20120728211534.png (2012-7-28 21:15:53, 12.83 KB) / 下载次数 2091
http://tcax.org/forum.php?mod=attachment&aid=NzgxfDg2ZTE3NmE0fDE3NjIwNjgzNzR8MHww



图片附件: Unnamed QQ Screenshot20120728215055.png (2012-7-28 21:51:09, 14.84 KB) / 下载次数 2104
http://tcax.org/forum.php?mod=attachment&aid=NzgzfGQwYWY4YjU1fDE3NjIwNjgzNzR8MHww

作者: BurySakura    时间: 2012-7-28 21:17:50

本帖最后由 BurySakura 于 2012-7-28 21:18 编辑

效率真好，我要曲线长度和任意点导数（拖走。
作者: ミルク    时间: 2012-7-28 21:25:01

BurySakura 发表于 2012-7-28 21:17
效率真好，我要曲线长度和任意点导数（拖走。

匀速（等距）版本的，我也挺有兴趣的，作为后续课题继续研究。

p.s. 可以稍微写下你的算法伪代码么？
作者: BurySakura    时间: 2012-7-28 21:27:31

ミルク 发表于 2012-7-28 21:25
匀速（等距）版本的，我也挺有兴趣的，作为后续课题继续研究。

p.s. 可以稍微写下你的算法伪代码么？ ...

我坐等伸手（逃。
作者: ミルク    时间: 2012-7-28 21:45:25

BurySakura 发表于 2012-7-28 21:27
我坐等伸手（逃。

这么没激情啊，不来一起啃这论文么

MovingAlongCurveSpecifiedSpeed.pdf (229.84 KB, 下载次数: 4122)


附件: MovingAlongCurveSpecifiedSpeed.pdf (2012-7-28 21:45:20, 229.84 KB) / 下载次数 4122
http://tcax.org/forum.php?mod=attachment&aid=NzgyfDBkMzZkZTY2fDE3NjIwNjgzNzR8MHww
作者: BurySakura    时间: 2012-7-28 21:47:39

ミルク 发表于 2012-7-28 21:45
这么没激情啊，不来一起啃这论文么

嘛，就算没这货的匀速（等距），我还有贝塞尔的（逃。
啃这个兴趣不大，还不如啃蘿莉什么的。
作者: BurySakura    时间: 2012-7-28 21:48:55

http://www.thecodeway.com/blog/?p=293
http://www.thecodeway.com/blog/?p=749
(233
作者: ミルク    时间: 2012-7-28 21:56:18

BurySakura 发表于 2012-7-28 21:48
http://www.thecodeway.com/blog/?p=293
http://www.thecodeway.com/blog/?p=749
(233

Good Stuff!
作者: ミルク    时间: 2012-8-1 02:50:42

匀速版本搞定了，等白天整理完代码再发。。。

p.s. 估计效率也不咋样

--------------- 随手补充一个测试 ---------------

Unnamed QQ Screenshot20120801025852.png

Unnamed QQ Screenshot20120801025841.png



图片附件: Unnamed QQ Screenshot20120801025852.png (2012-8-1 02:59:04, 5.17 KB) / 下载次数 2095
http://tcax.org/forum.php?mod=attachment&aid=Nzg5fDVhYTE3M2YxfDE3NjIwNjgzNzR8MHww



图片附件: Unnamed QQ Screenshot20120801025841.png (2012-8-1 02:59:04, 117.52 KB) / 下载次数 2116
http://tcax.org/forum.php?mod=attachment&aid=Nzg4fDllMGE4ZjdifDE3NjIwNjgzNzR8MHww

作者: Seekladoom    时间: 2021-10-7 01:08:46

本帖最后由 Seekladoom 于 2021-10-7 01:22 编辑

from util.tcCurve import *和如下代码直接相关：
  1.             ucb = UCBSpline(PP)     #使用ucb
  2.             L = ucb.length()       # 曲线总长度
复制代码
用到了UCBSpline的py脚本的最前面一定会有from util.tcCurve import *的代码行！

UCBSpline的函数定义在tcCurve.py这个文件里面。



欢迎光临 TCAX 字幕特效制作工具官方论坛 | ASS | TCAS | Python | Aegisub | Lua (http://tcax.org/) Powered by Discuz! X2