I am self-learning a game developing. The current topic I am learning is about path design. I get some random points and need a good math model to design a smooth path through those points (not necessary to pass all points but in best fitting). I read a book about spline (B-spline and cubic spline) and seems it is a good tool to use them. However, those two splines will get the path throughs the points instead of the best fitting smooth curve. I go research and I found scipy do have a smooth spline interploation may help
from scipy.interpolate import BSpline, CubicSpline
from scipy.interpolate import splrep
from scipy.interpolate import BPoly
import numpy as np
# x, y are the given points
x = np.array([ 0. , 1.2, 1.9, 3.2, 5, 6.5])
y = np.array([ 0. , 2.3, 3. , 4.3, 2.9, 3.1])
t, c, k = splrep(x, y, s=0.8, k=3) # make it smooth by setting s=0.8
spl = BSpline(t, c, k) # create B-spline
The Bspline does help to generate a smooth path. For some reasons, I need to break the path into multiple section of curves. My goal is to change the Bspline into a multiple sections of Bezier curve. So I try the following two approaches found online
- I found a question How to create Bezier curves from B-Splines in Sympy? in which someone ask about the same questions. I copy the code from there to below
import aggdraw
import numpy as np
import scipy.interpolate as si
from PIL import Image
# from https://stackoverflow.com/a/35007804/2849934
def scipy_bspline(cv, degree=3):
""" cv: Array of control vertices
degree: Curve degree
"""
count = cv.shape[0]
degree = np.clip(degree, 1, count-1)
kv = np.clip(np.arange(count+degree+1)-degree, 0, count-degree)
max_param = count - (degree * (1-periodic))
spline = si.BSpline(kv, cv, degree)
return spline, max_param
# based on https://math.stackexchange.com/a/421572/396192
def bspline_to_bezier(cv):
cv_len = cv.shape[0]
assert cv_len >= 4, "Provide at least 4 control vertices"
spline, max_param = scipy_bspline(cv, degree=3)
for i in range(1, max_param):
spline = si.insert(i, spline, 2)
return spline.c[:3 * max_param + 1]
def draw_bezier(d, bezier):
path = aggdraw.Path()
path.moveto(*bezier[0])
for i in range(1, len(bezier) - 1, 3):
v1, v2, v = bezier[i:i+3]
path.curveto(*v1, *v2, *v)
d.path(path, aggdraw.Pen("black", 2))
cv = np.array([[ 40., 148.], [ 40., 48.],
[244., 24.], [160., 120.],
[240., 144.], [210., 260.],
[110., 250.]])
im = Image.fromarray(np.ones((400, 400, 3), dtype=np.uint8) * 255)
bezier = bspline_to_bezier(cv)
d = aggdraw.Draw(im)
draw_bezier(d, bezier)
d.flush()
# show/save im
In the code, I don't quite understand what is v1, v2, v = bezier[i:i+3] v1, v2, v, is v1 the start point of the bezier curve, v2 the middle control point and v is the end point? so the bezier curve is always quadratic? I am trying to plot the v1, v2, v for each bezier extracted in the above code as follow, I get something very strange
for i in range(1, len(bezier) - 1, 3):
v1, v2, v = bezier[i:i+3]
cc = np.array([(v1[0], v1[1]), (v2[0], v2[1]), (v[0], v[1])])
curve = BPoly(cc[:, None, :], [0,1])
X = np.linspace(0, 1, 20)
p = curve(X)
plt.gca().set_aspect('equal')
plt.plot(*p.T)
Could someone help to explain if anything wrong with the code above?
- I have spent long time to figure out how to break the B spline into multiple Bezier curves but no good results, so I try to think of a different way. I use CubicSpline instead so the piecewise polynormial is avaialbe.
from scipy.interpolate import BSpline, CubicSpline
from scipy.interpolate import splrep
from scipy.interpolate import BPoly
import numpy as np
x = np.array([ 0. , 1.2, 1.9, 3.2, 5, 6.5])
y = np.array([ 0. , 2.3, 3. , 4.3, 2.9, 3.1])
t, c, k = splrep(x, y, s=0.8, k=3)
spl = BSpline(t, c, k)
import matplotlib.pyplot as plt
fig, ax = plt.subplots()
xx = np.linspace(0, 6, 500)
ax.plot(xx, spl(xx), 'b-', lw=4, alpha=0.7, label='BSpline')
ax.plot(x, y, 'rs')
xx = x
yy = spl(xx)
cu = CubicSpline(xx, yy)
plt.plot(xx, yy, 'ko')
for i in range(len(cu.x)-1):
xs = np.linspace(cu.x[i], cu.x[i+1], 100)
plt.plot(xs, np.polyval(cu.c[:,i], xs - cu.x[i]))
The code does give me a multiple segments but the number of segments depend on the xx I choose. If the xx is very dense, I may end up with so many segements. My goal is to use as less polynormial segments as possible to approach the spline. Could anyone give me some information for any way to do that? Thanks.
Looking for some advice how to apporach the problem
