[后弃]一点记录

showjim

河亲，给我时间想想

打算写这次《AKB48 29th - 桜の花びら～前田敦子solo ver.》的制作经历吧，以后再写别的。

第一部分：均速贝塞尔曲线（Constant Bézier Curves）

1. 何为均速贝塞尔呢？
首先说说贝塞尔曲线，这里是WIKI： Bezier Curve。详细的不说，由于贝塞尔函数的变量是参数t，而且其与坐标x、y在除1阶贝塞尔的情况下都不是线性关系，如下图：



而均速贝塞尔曲线就是指曲线上的点均匀分布，如下图：



2. 计算曲线长度
这个function主要是为了解决字体随贝塞尔曲线运动而做的。使用工具是NyuFX。
为了实现这个函数，我们首先要解决的是曲线长度的问题。但由于高阶贝塞尔的公式一般都比较复杂，所以我们可以用积分来得到想要的量。实现代码如下：

1. function curve_len(pct, spoint, tot_step)
   
2.         local sum = 0
   
3.         for i = 1, math.floor(pct * tot_step) do
   
4. 
   
5.                 if i==1 then
   
6.                         sum = 0
   
7.                 else
   
8.                         sum = sum + math.sqrt((spoint[i][1]-spoint[i-1][1])^2 + (spoint[i][2]-spoint[i-1][2])^2)
   
9.                 end
   
10.         end
    
11.         return sum
    
12. end

复制代码

其中，pct代表贝塞尔变量t，spoint是所有控制点。这段代码的主要思想就是设想曲线是有n个点组成（n足够大），所有相邻点的距离之和就会无限趋近于曲线的实际长度。如下两图：


a) 分割曲线为5部分，误差较大


b) 分割曲线为8部分，误差较小

这个求长度的方法比较粗糙，但简单，在1080P以下的字幕分辨率下足够了。

3. 新的参量t'的计算
假设我们已经用N个点点描述了一条贝塞尔曲线，接下来就是如何实现点的均匀分布的问题
由于贝塞尔曲线上点的坐标轴在除一阶的情况下不与变量t是线性关系，所以为了实现均速取点，我们假设一个新的参量t'，并认为t'满足以下关系：

1. t' = curve_len^-1[curve_len(1) * t]

复制代码

式中，curve_len代表曲线长度公式，^-1 代表取反函数。
由于直接计算任意n阶贝塞尔曲线公式的反函数比较困难，我们可以用牛顿法来取接近值，牛顿法可以参考维基百科：牛顿法

下面是Lua源码实现：

1. function constant_bezier(t1, spt, pts, tot_step, accuracy) --spt stands for the control points list, pts are the points on the curve, tot_step is the number of total step
   
2.         local len = curve_len(1, spt, tot_step) * t1
   
3.         local t2
   
4.         local t3
   
5.         local k
   
6.         repeat
   
7.                 t2 = t1 - (curve_len(t1, spt, tot_step) - len)/DeriveSA(t1, pts)[1] --Newton's method
   
8.                 t3 = t1
   
9.                 if t2 <= 1 then
   
10.                         t1 = t2
    
11.                 else
    
12.                         t1 = 1
    
13.                 end
    
14.         until math.abs(t2 - t3) < accuracy
    
15.         local k = math.round(t3 * tot_step)
    
16.         return spt[k][1],spt[k][2]
    
17. end

复制代码

4. 贝塞尔曲线函数的导函数
上一节代码中有个DeriveSA函数，这个我本意是用来计算导数的。实际上我换成了计算切向量与X轴的夹角。
任意阶贝塞尔函数的一阶导为：

式中，B代表Betnstein基函数，n代表总控制点数，i=0，1，2，…，n
而Betnstein基函数公式为：


Lua代码实现如下：

1. function D_bezier(pct, p)
   
2.         --Factorial
   
3.         function fac(n)
   
4.                 local k = 1
   
5.                 if n > 1 then
   
6.                         for i=2, n do
   
7.                                 k = k * i
   
8.                         end
   
9.                 end
   
10.                 return k
    
11.         end
    
12.         --Binomial coefficient
    
13.         function bin(i, n)
    
14.                 return fac(n) / (fac(i) * fac(n-i))
    
15.         end
    
16.         --Bernstein polynom
    
17.         function bernstein(pct, i, n)
    
18.                 return bin(i, n) * math.pow(pct,i) * math.pow((1 - pct), n - i)
    
19.         end
    
20. 
    
21. 
    
22.         local point = {0, 0}
    
23.         local n = table.maxn(p) - 1
    
24.         for i=1, n do
    
25.                 local bern = bernstein(pct, i-1, n-1)
    
26.                 point[1] = point[1] + (p[i+1][1] - p[i][1]) * bern * n
    
27.                 point[2] = point[2] + (p[i+1][2] - p[i][2]) * bern * n
    
28.         end
    
29.         return point
    
30. end
    
31. 
    
32. function DeriveSA(pct, p)
    
33.         local D_pt = D_bezier(pct, p)
    
34.         local D_f = math.sqrt(D_pt[1]^2 + D_pt[2]^2)
    
35.         local theta = math.atan(D_pt[2]/D_pt[1])*180/math.pi
    
36.         return {D_f, theta}
    
37. end

复制代码

下面视频是这次代码的实验效果：



以上，第一部分完结。

参考：
1. Warping Text to a Bézier curves
2. 匀速贝塞尔曲线运动的实现

showjim

第二部分：种子填充法（Flood-Fill）

1. 何为种子填充法
引用WIKI：“Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。”
其大体效果如下图：

1. 四向连通


2. 八向连通

如上两图，种子填充算法常用四向连通和八向连通两种操作：
1. 从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。
2. 从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。
一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图2所示的区域的内部，而四向连通填充算法只能完成如图1的部分填充。

这里我以四向连通为例来讲，其算法大体为：

Flood-fill（点坐标，目标颜色，替换颜色）
1. 如果坐标上的颜色不是目标颜色，则退出
2. 将坐标点设置为替换颜色
3. 递归调用Flood-fill，填充左侧坐标
    递归调用Flood-fill，填充右侧坐标
    递归调用Flood-fill，填充上方坐标
    递归调用Flood-fill，填充下方坐标
4. 返回

四向连通C语言粗略代码：

1. void flood_fill(int x,int y,int color)
   
2. {
   
3.   area[x][y]=color;
   
4.   if(x>0&&area[x-1][y]==0)flood_fill(x-1,y,color);
   
5.   if(y>0&&area[x][y-1]==0)flood_fill(x,y-1,color);
   
6.   if(x<MAX_X&&area[x+1][y]==0)flood_fill(x+1,y,color);
   
7.   if(y<MAX_Y&&area[x][y+1]==0)flood_fill(x,y+1,color);
   
8. 
   
9. }

复制代码

四向连通Lua代码：

1. dx0 = {0, 1, 0, -1}
   
2. dy0 = {1, 0, -1, 0}
   
3. 
   
4. while #q >0 do -- stand s for the initial index for all the points
   
5.         left = left - 1
   
6.         s = q[1] --pop out an element
   
7.         table.remove(q, 1) --delete it!
   
8.         pt = s_text[s] --get the pixel information
   
9.         for i = 1, 4 do
   
10.                 x1 = pt[1] + dx0[i]
    
11.                 y1 = pt[2] + dy0[i]
    
12.                 if x1 >= 1 and (x1 < s_width) and (y1 >= 1) and (y1 < s_height) and (boundary[y1][x1] >= 0) then
    
13.                         t = boundary[y1][x1]
    
14.                         if index[t] < 0 then --all the elements in index equal to -1
    
15.                                 index[t] = index[s] + 1 --if true, add 1
    
16.                                 table.insert(q, t)
    
17.                         end
    
18. 
    
19.                 end
    
20.         end
    
21. end

复制代码

Lua代码是一个四向连通的例子，其中大部分如注释，我想说的是boundary这个table，这个是用来界定字体边界的。在实现Flood Fill算法时，先进行随机取点，即起始点，然后再加上以上代码。

实验效果：


参考：
1. Wikipedia - Flood Fill
2. [数据结构与算法: 经典算法]Flood-Fill 种子填充
3. [图形算法]种子填充算法

showjim

第三部分：粒子系统

这部分怕是个大坑


这次的粒子系统是学的milk大移植的X大的粒子系统，系统库就在tcax的extlib里。可以在这里查看milk大的帖子：这里

这里我使用的是NyuFX，语言也将是Lua。
这个系统由两个文件组成：XXBase和XXParticleSystem。
XXBase主要用来声明一些将在系统中使用到的一些简单函数以及构造直线和合成曲线的基本类；XXParticleSystem则是主要的粒子算法，包括了发射器、重力系统、基本粒子元素和渲染算法。




照旧，先上实验效果：

预览0：


预览1：