[低效率]位图任意四边形变形

沙漠点灰

首先说明:效率很低!非常低!

这个方法可以把图片拉成任意四边形
格式:
位图对象.(坐标, 取值方式, debug)

"坐标"是个数组，格式是: [右上x,右上y，右下x,右下y,左下x,左下y]
(为什么没有左上?因为为了方便,定为 0,0)

取值方式, 这个版本有三个 -1,0,1
分别为: 平均,四舍五入,"真实"(有问题,建议不用)       默认是0

bebug是在处理完成时，报告处理情况，默认是false

在这，我只想看一下效率到底有多低(与RGE的效率...根本没法比...).....请大家测试一下，以方便优化版出来...格式:
测试代码 :XXXXX
CPU 主频 :XXXX
内存       :XXXX
Bebug   :XXXXXXXX  把bebug设为true,把弹出来的文字写上。比如:

(以学校的坏机器为例.....)

测试代码:(在标题画面修改)

1.     array = [400,100,600,480,100,400]
   
2.     @sprite.bitmap = @sprite.bitmap.quadrilateral(array,1,true)

复制代码

CPU 2.6Ghz(单)
内存   : 480Mb
Debug:   
取值方式 : -1 :  162199 p   22.36秒....
                   0 : 162199 p   7.875秒
                  1 :  162199 p   31.032秒

效率低原因分析:
浮点运算太多....(没办法,求优化方案....这个算法是根据比例用一次方程解出，下次试试高次方程....)

1. #==============================================================================
   
2. # ■ Bitmap
   
3. #------------------------------------------------------------------------------
   
4. # 　位图类 扩展
   
5. #===============================================================================
   
6. 
   
7. class Bitmap
   
8.   #--------------------------------------------------------------------------
   
9.   # ● 任意四边变形
   
10.   #--------------------------------------------------------------------------
    
11.   def quadrilateral(array, int=0, debug=false)
    
12.     time_now = Time.now
    
13.     xB, yB, xC, yC,xD,yD = array
    
14.     xB, yB, xC, yC,xD,yD = xB.to_f, yB.to_f, xC.to_f, yC.to_f,xD.to_f,yD.to_f
    
15.     # 为减少计算次数,浪费变量  ======> 我很傻....?
    
16.     @yC_B   = yC - yB
    
17.     @xC_B   = xC - xB
    
18.     begin
    
19.       @k_BC = @yC_B / @xC_B
    
20.     rescue
    
21.       return print "输入坐标BC线段K值无穷大"
    
22.     end
    
23.     @xM1_up = yB - @k_BC * xB
    
24.     @yC_D   = yC - yD
    
25.     @xC_D   = xC - xD
    
26.     @k_DC   = @yC_D / @xC_D # 不可能DC直线K值无穷大
    
27.     @xM2_up = yD - @k_DC * xD
    
28.     @k_B    = yB / xB
    
29.     @k_d    = xD / yD # 倒数
    
30.     # 生成新位图
    
31.     @_x_ = [0.0, xB, xC, xD]
    
32.     @_y_ = [0.0, yB, yC, yD]
    
33.     qua_bitmap = Bitmap.new(@_x_.max- @_x_.min, @_y_.max - @_y_.min)
    
34.     t = Time.now
    
35.     pixel_num = 0
    
36.     # 穷举坐标
    
37.     for y in @_y_.min.to_i ... @_y_.max.to_i
    
38.       for x in @_x_.min.to_i ... @_x_.max.to_i
    
39.         if y < @k_B * x or x < @k_d * y or
    
40.           y > @k_DC * (x - xD) + yD or
    
41.           x > (1 / @k_BC) * (y - yB) + xB
    
42.           next
    
43.         end
    
44.         begin
    
45.           new_x, new_y = mapping_qua(x, y)
    
46.           case int
    
47.           when -1
    
48.             color = [get_pixel(new_x.floor, new_y.floor)]
    
49.             color << get_pixel(new_x.ceil , new_y.floor)
    
50.             color << get_pixel(new_x.floor, new_y.ceil )
    
51.             color << get_pixel(new_x.ceil , new_y.ceil )
    
52.             r = color.inject(0.0){|a,i|a+i.red}
    
53.             g = color.inject(0.0){|a,i|a+i.green}
    
54.             b = color.inject(0.0){|a,i|a+i.blue}
    
55.             a = color.inject(0.0){|a,i|a+i.alpha}
    
56.             qua_bitmap.set_pixel(x, y, Color.new(r/4, g/4, b/4, a/4))
    
57.           when 0
    
58.             color = get_pixel(new_x+0.5, new_y+0.5)
    
59.             qua_bitmap.set_pixel(x, y, color)
    
60.           when 1
    
61.             color1 = get_pixel(new_x.floor, new_y.floor)
    
62.             color2 = get_pixel(new_x.ceil , new_y.floor)
    
63.             color3 = get_pixel(new_x.floor, new_y.ceil )
    
64.             color4 = get_pixel(new_x.ceil , new_y.ceil )
    
65.             # Red
    
66.             r=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.floor)**2))*color1.red
    
67.             r+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.floor)**2))*color2.red
    
68.             r+=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.ceil)**2))*color3.red
    
69.             r+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.ceil )**2))*color4.red
    
70.             # Green
    
71.             g=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.floor)**2))*color1.green
    
72.             g+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.floor)**2))*color2.green
    
73.             g+=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.ceil)**2))*color3.green
    
74.             g+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.ceil )**2))*color4.green
    
75.             # Blue
    
76.             b=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.floor)**2))*color1.blue
    
77.             b+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.floor)**2))*color2.blue
    
78.             b+=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.ceil)**2))*color3.blue
    
79.             b+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.ceil )**2))*color4.blue
    
80.             # Alpha
    
81.             a=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.floor)**2))*color1.alpha
    
82.             a+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.floor)**2))*color2.alpha
    
83.             a+=(Math.sqrt((new_x-new_x.floor)**2+(new_y-new_y.ceil)**2))*color3.alpha
    
84.             a+=(Math.sqrt((new_x-new_x.ceil)**2+(new_y-new_y.ceil )**2))*color4.alpha
    
85.             qua_bitmap.set_pixel(x, y, Color.new(r/2, g/2, b/2, a/2))
    
86.           end
    
87.           pixel_num += 1
    
88.         rescue
    
89.           next
    
90.         end
    
91.       end
    
92.       # 9秒刷新画面...不给力啊
    
93.       if Time.now - t > 9
    
94.         Graphics.update ; t = Time.now
    
95.       end
    
96.     end
    
97.     print "共计渲染#{pixel_num}个像素\n共计耗时#{Time.now - time_now}秒"if debug
    
98.     qua_bitmap
    
99.   end
    
100.   private # 下列方法私有化
     
101.   #--------------------------------------------------------------------------
     
102.   # ● 映射坐标
     
103.   #--------------------------------------------------------------------------
     
104.   def mapping_qua(x, y)
     
105.     # 根据平面直线之间的关系,运用初中知识可以推出公式
     
106.     x, y = x.to_f, y.to_f
     
107.     if y <= @_y_[2] / @_x_[2] * x
     
108.       # 右边部分
     
109.       xM = @xM1_up / (y/x - @k_BC)
     
110.       x  = x / xM * self.width
     
111.       return x, y * xM / self.width
     
112.     else
     
113.       # 左边部分
     
114.       xM = @xM2_up / (y/x - @k_DC)
     
115.       y  = x / xM * self.height
     
116.       return y * xM / self.height, y
     
117.     end
     
118.   end
     
119. end
     

复制代码

david50407

可以考虑导出dll 或找高效的算法
PS: set_pixel get_pixel 很慢

trentswd

效率一低就几乎没有使用价值了
话说拉一下就几十秒了，有点……太慢了吧

苏小脉

考虑到如今处理器的 FPU 性能，这里的浮点运算都是其次了，最需要关心的还是循环内部的 set_pixel、get_pixel。这俩的调用前后分别要锁定和解锁内存，只适合常量时间内的调用。像这种软件渲染的图形算法，必须要直接操纵内存，set_pixel、get_pixel 处于抽象层高层了，跟不上实时。

另外，Ruby 抽象层上任何运算效率都天然低一截，时间上紧张的算法没有人会用 Ruby 来写。直到 Ruby 有一个像 JVM 那样强悍的虚拟机之前，最好都直接生成本地代码。

最后就是一些一眼就能看出不够 DRY 的地方，比如 when 1 下面那段，有不少冗余的运算。

沙漠点灰

回复 苏小脉 的帖子

我原来也是以为set/get_pixel是减慢速度的主要原因，不过我试着把 "case" 部分换成next，结果是6.8秒，仅仅快了1秒，也就是说在学校的老机器跑N次浮点运算用了6.8秒，而16万次
set+get用了1秒，所以我说主要原因是"浮点运算"，我也认为在配置较高的PC上，估计(用0)会耗时2..3秒，所以我请大家帮忙测试一下,至于"when 1"嘛..脑子不好用,乱写的，不应该开平方根.....哎....个人认为精灵的缩放以及旋转算法是通过某种方法直接写入显存的说.比CPU->内存->XXX->显存 肯定快的说....再查查资料....像我们这些仅仅懂皮毛的人来说....太难了

yangff

david50407 发表于 2011-4-22 21:01
可以考虑导出dll 或找高效的算法
PS: set_pixel get_pixel 很慢

笑而不语

苏小脉

回复 沙漠点灰 的帖子

我原来也是以为set/get_pixel是减慢速度的主要原因，不过我试着把 "case" 部分换成next，结果是6.8秒，仅仅快了1秒

要考虑到线性化之后线性运算的时间。这里的运算本来就比较重量级，线性化后复杂度是没变的，只是路由到更高效的 ALU 芯片了，在二十一世纪的处理器下差别只是一个线性级的改变。

这就好比下列代码：

1. t = Time.now
   
2. D.times do
   
3.   arr[1] = 1
   
4.   35.0/32
   
5. end
   
6. p Time.now - t
   
7. 
   
8. t = Time.now
   
9. D.times do
   
10.   b.set_pixel(4, 6, c)
    
11.   35/32
    
12. end
    
13. p Time.now - t

复制代码

一测便知，在当前机器架构下，是把 set_pixel 改为一般的随机访问占得比重高，还是把浮点运算转换为定点运算比重高。

个人认为精灵的缩放以及旋转算法是通过某种方法直接写入显存的说

软件渲染都是 CPU 在主内存中操纵缓冲区，然后软件 bit Blit 到显示内存，这中间经过了 BUS，已经损失了效率。当然，这还是比 get_pixel/set_pixel 快——抽象层越多，效率越低。

2D 游戏时代的游戏机一般都有集成的硬件精灵引擎，比较高级的就支持旋转、缩放等运算的硬件加速，这属于硬件渲染，所有工作 GPU 包办了，没 BUS 的事，这无疑是最高效的。

0109113236

LZ，我可以求您签名档的刀剑神域的游戏网址吗