源码

/buglas/canv…

学习目标知识点1-AABB包围盒简介

我们在第二个面试题里实现了圆形在多边形中的碰撞反弹。

但当多边形边界复杂，甚至数量很多的时候，之前选择多边形的方法就会带来较大的性能损耗，所以我们需要用AABB包围盒做一下性能优化。

AABB 包围盒是一种与坐标轴保持一致的盒子，它是包围体(Bounding Volume)中的一种。

包围体是用一种简单模型包围复杂模型的方式，可用于碰撞检测和光线追踪。

包围盒和包围球是常见的包围体：

在检测几何体与射线的碰撞关系的时候，包围几何体的包围体会先与射线做碰撞检测。

若射线与包围盒发生了碰撞，再判断射线与包围盒所包围的物体是否发生碰撞。

AABB 包围盒在与射线做碰撞检测的时候，是最为简单快捷的。

2-射线与AABB包围盒的相交

射线与AABB包围盒的相交方式如下图所示。

已知：

包围盒

求：射线是否与包围盒相交

思路分析：

射线存在3种状态：

我们先暂且认为射线是倾斜的，因为这种状态最复杂，其它状态都很简单。

在上图中，A1A2是射线与包围盒上下两边所在直线的交点；B1B2是射线与包围盒左右两边所在直线的交点。

当射线与包围盒相交的时候，直线A1A2必然和直线B1B2存在交集。

所以求出A1、A2、B1、B2的位置，然后判断直线A1A2和直线B1B2是否有交集就是我们接下来要讨论的重点。

现在A1、A2、B1、B2的位置我们已经知道了一半了，即：

A1=(?,minY)
A2=(?,maxY)
B1=(minX,?)
B2=(maxX,?)

接下来我们需要把上面的4个问号求出来。

解：

1.以y为因变量，以x为自变量，做射线的斜截式。

根据射线的方向可得斜率k：

k=vy/vx

根据斜截式可得截距公式。

y=kx+b
b=y-kx

将射线的源点ox,oy 代入上式可以求出截距b。

b=oy-k*ox
b=oy-(vy/vx)*ox

根据斜率和截距可得斜截式。

y=(vy/vx)*x+oy-(vy/vx)*ox

上式的作用是：

2.同理，我们也可以以x 为因变量，以y为自变量，构建基于y值求x值的斜截式。

x=ky+b
k=vx/vy
b=ox-k*oy
b=ox-(vx/vy)*oy
x=(vx/vy)*y+ox-(vx/vy)*oy

上式的作用是：

3.求射线与包围盒的四条边所在的直线与射线的交点，即A1,A2,B1,B2。

A1,A2的x值分别是minX,maxX，将x值代入以y值为因变量的斜截式可得：

A1.y=(vy/vx)*minX+oy-(vy/vx)*ox
A2.y=(vy/vx)*maxX+oy-(vy/vx)*ox

B1,B2的y值分别是minY,maxY，将y值代入以x值为因变量的斜截式可得：

B1.x=(vx/vy)*minY+ox-(vx/vy)*oy
B2.x=(vx/vy)*maxY+ox-(vx/vy)*oy

现在，我们就知道了A1,A2,B1,B2的点位，接下来就是判断直线A1A2和直线B1B2是否有交集。

4.以射线为坐标轴，计算A1、A2、B1、B2 在射线上的刻度，此刻度就是这四个点在射线的投影。

A1'= OA1·v
A2'= OA2·v
B1'= OB1·v
B2'= OB2·v

5.基于A1'、A2'、B1'、B2' 的大小，获取A1、A2中的极大值和极小值，B1、B2中的极大值和极小值

设Amin为A1、A2中的最小值，Amax为A1、A2中的最大值，Bmin为B1、B2中的最小值，Bmax为B1、B2中的最大值。

Amin=min(A1,A2)
Amax=max(A1,A2)
Bmin=min(B1,B2)
Bmax=max(B1,B2)

在上图中，Amin、Amax 分别对应着A1、A2，Bmin、Bmax 分别对应着B1、B2。当然，实际上不一定如此。

6.判断直线AminAmax和直线BminBmax之间是否有交集。

取点Amin和点Bmin中的最大值，设此值为Cmax

Cmax=max(Amin,Bmin)

取点Amax和点Bmax中的最小值，设此值为Cmin

Cmin=min(Amax,Bmax)

在上图中，Cmax对应着B1，Cmin对应着A2。

如果Cmax

当前默认射线是倾斜状态的，接下来再考虑射线水平和垂直的状态。

7.当射线水平时(vy=0)，射线与包围盒的相交需满足以下条件：

同理，当射线垂直时(vx=0)，射线与包围盒的相交需满足以下条件：

现在，我们就完成了射线与AABB包围盒的相交判断。

当前的包围盒是二维的，若是三维包围盒，以同理也可以推出来，只不过你需要再多考虑两种角度。

3-代码实现3-1-包围盒的封装

在我当前的canvas渲染引擎里，我把包围盒封装在了Geometry 对象中，其数据结构如下：

type BoundingBox = {
    min: Vector2
    max: Vector2
}

包围盒的计算方法就是puteBoundingBox() 方法。

不同的几何体，计算包围盒的方式会有所不同。

PolyGeometry计算包围盒的方法如下所示：

    computeBoundingBox() {
        const {
            position,
            boundingBox: { min, max },
        } = this
        min.set(position[0], position[1])
        max.copy(min)
        for (let i = 2, len = position.length; i < len; i += 2) {
            const [x, y] = [position[i], position[i + 1]]
            if (min.x > x) {
                min.x = x
            } else if (max.x < x) {
                max.x = x
            }
            if (min.y > y) {
                min.y = y
            } else if (max.y < y) {
                max.y = y
            }
        }
        return this
    }

PolyExtendGeometry 计算包围盒的方式则要复杂一点：

    computeBoundingBox() {
        const {
            position,
            distance,
            boundingBox: { min, max },
        } = this
        min.set(Infinity)
        max.set(-Infinity)
        for (let i = 0, len = position.length; i < len; i++) {
            const curShape = position[i]
            if (curShape instanceof Vector2) {
                this.expand(curShape)
            } else {
                const { origin, startAngle, endAngle, startPosition, endPosition } =
                    curShape
                this.expand(startPosition)
                this.expand(endPosition)
                const arc = new Arc2(origin.x, origin.y, distance, startAngle, endAngle)
                angles.forEach((angle) => {
                    if (arc.isAngleInRange(angle)) {
                        const s = Math.sin(angle)
                        const c = Math.cos(angle)
                        const p = new Vector2(distance * c, distance * s).add(origin)
                        this.expand(p)
                    }
                })
            }
        }
    return this
    }

由于包围盒是基于Geometry对象计算的，如果一个物体放生了变换，那么用Geometry算出的包围盒在世界坐标系里就不一定是AABB包围盒了。

对于这种情况，你需要把Geometry克隆一份出来，对其进行相同的变换，然后再计算包围盒。

之前我们在计算文字边界的时候写过这样的代码：

textObj.geometry.clone().applyMatrix3(textObj.worldMatrix)

3-2-显示包围盒

我们可以基于第二个面试题的vue 再复制一份出来，用来显示多边形扩展对象的包围盒。

/* 围墙外扩后的包围盒 */
{
    const boundingBox = crtBoundingBox(wallExtendObj.geometry)
    scene.add(boundingBox)
}
/* 障碍物外扩后的包围盒 */
{
  const boundingBox = crtBoundingBox(obstacleExtendObj.geometry)
    scene.add(boundingBox)
}
function crtBoundingBox(geometry:PolyExtendGeometry){
  geometry.computeBoundingBox()
  const {
        min: { x: x1, y: y1 },
        max: { x: x2, y: y2 },
    } = geometry.boundingBox
  return new Graph2D(
    new PolyGeometry([x1, y1, x2, y1, x2, y2, x1, y2]).close(),
    new StandStyle({
            strokeStyle: 'rgba(255,120,0,0.6)',
            lineWidth: 2,
            lineDash: [12, 4, 4, 4],
        })
  )
}

puteBoundingBox() 方法会根据一个物体的geometry 计算包围盒。

geometry.computeBoundingBox()

算出的包围盒的极大值和极小值会存储到geometry.boundingBox 属性中。

  const {
        min: { x: x1, y: y1 },
        max: { x: x2, y: y2 },
    } = geometry.boundingBox

如果障碍物或围墙的模型矩阵发生了变化，比如发生了位移：

const obstacleObj = new Graph2D(obstacleGeometry, obstacleStyle)
obstacleObj.position.set(100,0)

那我们就需要根据这个物体的在世界坐标系里的点位计算其扩展对象的点位：

const obstacleExtendObj = crtExtendObj(
  obstacleGeometry.clone().applyMatrix3(obstacleObj.worldMatrix), 
  radius, 
  {
    strokeStyle: 'green',
    lineDash: [3],
  }
)
obstacleExtendObj.name = 'obstacle'
scene.add(obstacleExtendObj)

效果如下：

现在的障碍物扩展对象是基于障碍物在世界坐标系的顶点位置做的扩展。

这样我们计算的包围盒就是障碍物扩展对象在世界坐标系里的包围盒。

简而言之，我们要确保射线和包围盒在同一坐标系中。

3-3-射线与包围盒的相交方法

之前我们在做碰撞检测时，用的是intersectObjects(ray,objects,useBoundingBox) 方法。

其中的第三个参数useBoundingBox 就是是否使用包围盒优化选择的，之前我们把这块给略过了，接下来咱们详细说一下。

若useBoundingBox为true，intersectObjects() 方法在使用intersectObject()方法选择物体时，都会先对包裹物体的包围盒做一个选择，若未选中包围盒，就返回null；否则，就再选择包围盒中的物体。

function intersectObject(
    ray: Ray2,
    object: ObjectForIntersect,
    useBoundingBox: boolean = false
): IntersectResult {
    ……
    if (useBoundingBox && !intersectBoundingBox(ray, boundingBox)) {
            return null
    }
  ……
}
/* 射线与包围盒的相交 */
function intersectBoundingBox(ray: Ray2, boundingBox: BoundingBox) {
    const {
        origin: O,
        origin: { x: ox, y: oy },
        direction: v,
        direction: { x: dx, y: dy },
    } = ray
    const {
        min: { x: minX, y: minY },
        max: { x: maxX, y: maxY },
    } = boundingBox
    if (dy === 0) {
        const b1 = oy > minY && oy < maxY
        const b2 =
            new Vector2(minX - ox, 0).dot(v) > 0 ||
            new Vector2(maxX - ox, 0).dot(v) > 0
        if (b1 && b2) {
            return true
        }
    } else if (dx === 0) {
        const b1 = ox > minX && ox < maxX
        const b2 =
            new Vector2(0, minY - oy).dot(v) > 0 ||
            new Vector2(0, maxY - oy).dot(v) > 0
        if (b1 && b2) {
            return true
        }
    } else {
        // 因变量为y的斜截式
        const interceptY = ray.getSlopeIntercept('y')
        // 因变量为x的斜截式
        const interceptX =ray.getSlopeIntercept('x')
        // 射线与包围盒的四条边所在的直线的4个交点减O
        const OA1 = new Vector2(minX, interceptY(minX)).sub(O)
        const OA2 = new Vector2(maxX, interceptY(maxX)).sub(O)
        const OB1 = new Vector2(interceptX(minY), minY).sub(O)
        const OB2 = new Vector2(interceptX(maxY), maxY).sub(O)
        // OA1、OA2 中的极小值Amin和极大值Amax
        const [Amin, Amax] = [OA1.dot(v), OA2.dot(v)].sort((a, b) =>
            a > b ? 1 : -1
        )
        // OB1、OB2 中的极小值Bmin和极大值Bmax
        const [Bmin, Bmax] = [OB1.dot(v), OB2.dot(v)].sort((a, b) =>
            a > b ? 1 : -1
        )
        if (Math.max(Amin, Bmin) < Math.min(Amax, Bmax)) {
            return true
        }
    }
    return false
}

上面的intersectBoundingBox(ray, boundingBox)方法就是射线和包围盒求交的方法，其代码就是我按照之前说的数学逻辑写的，大家可以相互印证着理解。

3-4-测试射线与包围盒的相交

在BoundingBox.vue 中，将intersectObjects 方法的第3个参数设置为true，表示使用包围盒优化选择。

// 射线与墙体和障碍物的交点
const intersectData=intersectObjects(
  rayTem,
  [wallExtendObj,obstacleExtendObj],
  true
)

其效果和之前是一样的：

我们可以在intersectObject() 方法中打印看看这个逻辑有没有走。

function intersectObject(
    ray: Ray2,
    object: ObjectForIntersect,
    useBoundingBox: boolean = false
): IntersectResult {
    const { geometry:{boundingBox,type} } = object
  // 先与包围盒进行碰撞检测
    if (useBoundingBox && !intersectBoundingBox(ray, boundingBox)) {
        console.log(object.name,'未碰撞到包围盒')
        return null
    }
  ……
}

打印如下：

obstacle 未碰撞到包围盒

总结

这一篇主要讲了通过AABB包围盒优化选择的方法。

在WebGL和canvas 相关的面试中，图形选择是一个必考题，而如何优化选择，也会很容易被连带问出。

AABB包围盒适合选择边界复杂的模型。

而我们下一篇要说的BVH 选择方法会适合大批量模型的选择。