注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秒大刀 博客

好好学习 天天向上

 
 
 

日志

 
 
 
 

建立2D AABB  

2010-04-22 17:05:54|  分类: Game |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    AABB是游戏中经常用的包围盒。本文提出一种2D空间内自动生成AABB的算法,读者也可在此基础上开发出基于3D的AABB自动生成算法。

    本算法可以用来在一个给定区域内进行AABB的自动挖掘产生。如:场景内各建筑的阻挡点包围框;纹理贴图上小图标的包围框……

算法描述:

  1. 创建一个AABB空列表aabbList
  2. 循环给定空间内的每一个点pt
  3.     如果pt为不感兴趣的点,则跳转2
  4.     如果pt为感兴趣的点
  5.         为pt创建一个大小为1的AABB rect
  6.         遍历aabbList中每个元素aabb
  7.             如果rect和aabb邻接或相交,则表明rect和aabb可以合并
  8.                 rect = Union(rect,aabb),将aabb合并到rect
  9.                 从aabbList中删除aabb
  10.         将rect加入到aabbList
  11. 返回aabbList

C#实现代码如下:

         /// <summary>

        /// 判断是否对给定位置感兴趣并愿意放入AABB

        /// </summary>

        delegate bool InterestPredicate(int x, int y);

 

        /// <summary>

        /// 得到给定区域范围内的所有AABB

        /// </summary>

        /// <param name="area">要搜索的区域,该区域的每个点值将逐一传给<paramref name="isInterest"/></param>

        static List<Rectangle> GenerateAllAABB(Rectangle area, InterestPredicate isInterest)

        {

            if (isInterest == null)

                throw new ArgumentNullException("isEmpty");

 

            // 结果包围框集

            List<Rectangle> aabbList = new List<Rectangle>();

 

            // 临时变量。一次合并过程中发现的可合并的包围框下标

            List<int> intersectList = new List<int>();

 

            for (int y = area.Top; y < area.Bottom; y++)

            {

                for (int x = area.Left; x < area.Right; x++)

                {

                    if (isInterest(x, y) == false)

                        continue;

                    intersectList.Clear();

 

                    Rectangle rect = new Rectangle(x, y, 1, 1);

 

                    // 对已有的包围框进行遍历合并

                    for (int i = 0; i < aabbList.Count; i++)

                    {

                        Rectangle aabb = aabbList[i];

                        // 判断是否邻接,相交或者紧挨着都算邻接

                        if (rect.IntersectsWith(new Rectangle(aabb.X - 1, aabb.Y - 1, aabb.Width + 2, aabb.Height + 2)))

                        {

                            rect = Rectangle.Union(rect, aabb);

                            intersectList.Add(i);

                        }

                    }

 

                    // 倒序遍历,避免对list进行删除时下标失效

                    for (int i = intersectList.Count - 1; i >= 0; i--)

                    {

                        aabbList.RemoveAt(intersectList[i]);

                    }

 

                    // 将合并后的包围框加入结果集

                    aabbList.Add(rect);

                }

            }

            return aabbList;

        }

 

    下面的例子给CEGUI WindowsLook风格的贴图加上AABB包围框,该工作如果用CEImagesetEditor之类的工具手工做的话需要很长的时间和耐心。

        private void Form1_Load(object sender, EventArgs e)

        {

            int backgroundColor = Color.White.ToArgb();

 

            Bitmap bitmap = new Bitmap("WindowsLook.bmp");

 

            // 计算包围框

            List<Rectangle> list = GenerateAllAABB(

                new Rectangle(0, 0, bitmap.Width, bitmap.Height),

                (x, y) =>

                {

                    Color c = bitmap.GetPixel(x, y);

                    return c.A != 0 && c.ToArgb() != backgroundColor;

                });

 

            // 将得到的包围框绘制出来

            using (Graphics g = Graphics.FromImage(bitmap))

            {

                Pen pen = new Pen(Color.FromArgb(100, Color.Red));

                g.DrawRectangles(pen, list.ToArray());

                pen.Dispose();

            }

 

            pictureBox1.Image = bitmap;

        }

    结果为下图中右边的样子,左边是原始的图片:

        Generation of 2D AABB - 秒大刀 - 秒大刀的城堡

     可以考虑将该算法加入到CEImagesetEditor工具中,对新建立的Imageset,自动生成小图标的包围盒。在此基础上手工稍作调整即可。

     感谢廖鑫炜开平等人提供帮助!

 

扩展阅读:

数据聚类》算法(英文版的更全面)


2012-2-6

    若性能不满足,可以用Bitmap.LockBits替代Bitmap.GetPixel手工解析像素。

  评论这张
 
阅读(1523)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017