时间:2021-07-01 10:21:17 帮助过:21人阅读
AABB是游戏中经常用的包围盒。本文提出一种2D空间内自动生成AABB的算法,读者也可在此基础上开发出基于3D的AABB自动生成算法。 本算法可以用来在一个给定区域内进行AABB的自动挖掘产生。如:场景内各建筑的阻挡点包围框;纹理贴图上小图标的包围框…… 算法
AABB是游戏中经常用的包围盒。本文提出一种2D空间内自动生成AABB的算法,读者也可在此基础上开发出基于3D的AABB自动生成算法。
本算法可以用来在一个给定区域内进行AABB的自动挖掘产生。如:场景内各建筑的阻挡点包围框;纹理贴图上小图标的包围框……
算法描述:
- 创建一个AABB空列表aabbList
- 循环给定空间内的每一个点pt
- 如果pt为不感兴趣的点,则跳转2
- 如果pt为感兴趣的点
- 为pt创建一个大小为1的AABB rect
- 遍历aabbList中每个元素aabb
- 如果rect和aabb邻接或相交,则表明rect和aabb可以合并
- rect = Union(rect,aabb),将aabb合并到rect
- 从aabbList中删除aabb
- 将rect加入到aabbList
- 返回aabbList
C#实现代码如下:
///
/// 判断是否对给定位置感兴趣并愿意放入AABB
///
delegate bool InterestPredicate(int x, int y);
///
/// 得到给定区域范围内的所有AABB
///
/// 要搜索的区域,该区域的每个点值将逐一传给
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;
}
结果为下图中右边的样子,左边是原始的图片:
可以考虑将该算法加入到CEImagesetEditor工具中,对新建立的Imageset,自动生成小图标的包围盒。在此基础上手工稍作调整即可。
感谢廖鑫炜、开平等人提供帮助!
扩展阅读:
《数据聚类》算法(英文版的更全面)
2012-2-6
若性能不满足,可以用Bitmap.LockBits替代Bitmap.GetPixel手工解析像素。