多边形碰撞检测（一）：前言

[phenomLi]

现在成熟的碰撞检测算法有许多，不同的检测算法也有着不同的精度，它们分别有着不同的应用场景。在大多数的游戏中，为了节省性能，通常会直接使用简单高效的检测算法，如包围盒检测算法。然而在复杂真实的游戏中，需要更加精细的碰撞检测要求，表现更拟真的物理反馈。但是精细意味着效率代价大。比如世界中有100个对象，如果两两进行精细检测，那么就要进行2^100次高精度比较，这显然不现实。

一种优秀的思想是在碰撞检测系统中降低规模，利用分层算法，逐步筛选出可能发生碰撞的对象。通常的做法是将检测流程分成两个阶段： 粗检测阶段（broad-phase） 和 细检测阶段（narrow-phase） 。

首先，系统遍历所有可碰撞元素，在粗检测阶段利用简单算法判断筛选出可能发送碰撞的元素，然后再在细检测阶段检测粗检测阶段筛选出来的元素，最后完成一轮检测。

按照这种思路，我们也可以实现了类似的分层检测，但是不同的是，为了更精确地筛选，降低无必要的检测消耗，我们可再进一步，将其分层了3层，即粗检测阶段， 中间检测阶段（middle-phase） 和细检测阶段。

流程如图所示：

其中，粗检测阶段使用Sweep and Prune算法，中间检测阶段使用AABB包围盒检测，细检测阶段使用SAT分离轴算法。

要实现一个碰撞检测系统，首先要确定检测的对象，我们这里实现的碰撞检测主要目标是检测任意多边形和圆形间的碰撞。因此，在编写具体算法时，我们要首先确定碰撞对象的数据结构。我们不妨使用一个Shape类来描述一个碰撞对象：

// 基本的Shape类
class Shape {
    // 包围盒
    public boundRect: BoundRect;

    private x: number;
    private y: number;

    constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
    }
}

有了Shape类，便可以扩展出圆形和多边形：

// 圆形信息
export class CircleInfo {
    constructor(x: number, y: number, r: number) {
        this.x = x;
        this.y = y;
        this.r = r;
    }
    x: number;
    y: number;
    r: number;
}

// 圆形
class Cricle extends Shape {
    // 半径
    private radius: number;
    // 圆形信息
    private circleInfo: CircleInfo;

    constructor(x: number, y: number, radius: number) {
        super(x, y);
        this.radius = radius;
        this.circleInfo = new CircleInfo(x, y, radius);
    }
}

// 多边形顶点类型
export type polygonVex = Array<number[]>;

// 多边形
class Polygon extends Shape {
    // 多边形的顶点
    private vexs: polygonVex;
    // 是否为凹多边形
    private isConcavePoly: boolean;

    constructor(x: number, y: number, vexs: polygonVex) {
        super(x, y);

        this.vexs = vexs;
    }
}

// 图形的相关信息
export type shapeData = polygonVex | CircleInfo;

以上就是两种图形的数据结构，之后我们将会围绕这两种图形完成一个碰撞检测系统。了解了碰撞检测的基本流程后，下一篇讲介绍Sweep and Prune算法的思想与实现。