大家好,我是前端西瓜哥。
本文将讲讲解二维中的包围盒。
三维的包围盒是一脉相承的,理解了二维也就懂了三维。
包围盒(bbox, bounding box)指的是包围图形的一个矩形。
“盒” 通常特指矩形(二维)或是立方体(三维)。
实际上包围形状的图形某些情况下会使用多边形(凸包、凹包)或是圆形或是其他,不仅限于矩形的更泛用的叫法应该是 “包围体”(bounding volume)。
我们使用左上角和右下角两个点表达包围盒。
interface Bbox {
minX: number
minY: number
maxX: number
maxY: number
}
这里不再建议使用 x、y、width、height 的写法。
width 和 height 纯属多余,本身不会用到,却要在每次碰撞运算时,通过 x + width 和 y + height 得到 maxX 和 maxY 再运算。
下面介绍几种中比较常用到的包围盒。
这里有一个椭圆,非常朴实的椭圆。
基于 x、y、width、height 属性渲染出来的椭圆。
其 bbox 为:
const bbox = {
minX: attrs.x,
minY: attrs.y,
maxX: attrs.x + attrs.width,
maxY: attrs.y + attrs.height,
}
这种包围盒称为 AABB 包围盒。
AABB 包围盒全称为 axis-aligned bounding box,轴对齐包围盒。
它是一个矩形,且它的边是和轴线(比如 x 轴和 y 轴)对齐的。
这个 AABB 刚好紧密包裹住椭圆,所以这个包围盒同时也是 MBR(最小外接矩形)。
判断两个 AABB 包围盒是否发生碰撞很简单:
const isBboxIntersect = (bbox1, bbox2) => {
return (
bbox1.minX <= bbox2.maxX &&
bbox1.maxX >= bbox2.minX &&
bbox1.minY <= bbox2.maxY &&
bbox1.maxY >= bbox2.minY
);
};
包围盒不一定要是单个图形的包围盒,也可以是多个图形的,做个 merge 即可。
const mergeBbox = (bboxs) => {
let minX = Number.MAX_VALUE;
let minY = Number.MAX_VALUE;
let maxX = Number.MIN_VALUE;
let maxY = Number.MIN_VALUE;
for (const bbox of bboxs) {
minX = Math.min(minX, bbox.minX);
minY = Math.min(minY, bbox.minY);
maxX = Math.max(maxX, bbox.maxX);
maxY = Math.max(maxY, bbox.maxY);
}
return { minX, minY, maxX, maxY };
}
一天,椭圆说它想要旋转,于是我们引入了 rotate 属性,通常保存弧度值。
于是出现了一个有朝向的包围盒,称之为 OBB。
OBB 包围盒全称 oriented bounding box,即有朝向的包围盒。
该包围盒也是矩形,但是因为有旋转,边不一定和轴线对齐,但能 更紧凑地包围目标图形。
包围盒需要补充一个旋转属性。
const bbox_obb = {
minX: attrs.x,
minY: attrs.y,
maxX: attrs.x + attrs.width,
maxY: attrs.y + attrs.height,
rotate: attrs.rotate, // 或者用旋转矩阵
}
对于 OBB 之间的碰撞判定,需要用复杂一些的 分离轴定理 算法来判断。
分离轴定理专门用来进行凸多边形之间的碰撞检测,矩形也是凸多边形,所以可以用。
虽然有 OBB 了,但我们还是需要图形的 AABB 包围盒,用于更高精度的选区框选、渲染剔除等用途。
一种简单的方式是基于 OBB 的 4 个点重新计算出一个 AABB,如下图。
AABB 并不要求紧密包裹图形,所以并不是一定是最小外接矩形(MBR)。
对此,如果想提高 AABB 的精度,可以用几何算法去求 MBR 作为图形的 AABB。
但涉及到平面几何,不同图形的算法不一样。像是椭圆大概要用到蒙日圆,多边形则求变换后顶点的坐标值的最大最小 x y 值。
还有一种场景,为了支持不局限于旋转的更多形变效果(比如斜切、翻转),我们会选择使用 transform 矩阵。
此时我们需要的是上图这种包围多边形,勉强叫做有 transform 的 box 吧。
因为是线性形变,包围多边形是平行四边形,依旧是凸多边形,所以还是可以分离轴定理 算法来计算碰撞。
这里有个地方有稍微注意一下,关于描边的。
有些图形的描边比较大,或者画布缩放很大。
此时进行框选,如果框选到描边的部分区域,理论上也算选中图形了,所以要把描边的宽度考虑上,将包围盒子往外扩展描边宽度的二分之一。
const extendBbox = (bbox, padding) => {
return {
minX: bbox.minX - padding,
minY: bbox.minY - padding,
maxX: bbox.maxX + padding,
maxY: bbox.maxY + padding,
};
}
const renderedBbox = extendBbox(bbox, attrs.strokeWidth / 2)
除了在框选用到,也会用在不渲染图形剔除的场景,但可能还要额外考虑投影这些其他渲染因素。
我是前端西瓜哥,关注我,学习更多图形编辑器开发知识。