碰撞检测 <包围体>| 轴对齐包围盒（AABB）

2024 年 10 月 17 日

58 次浏览

2561字数

碰撞检测 <包围体>| 轴对齐包围盒（AABB）
碰撞检测是为了判断两个或多个物体（几何体）是否发生相交。例如判断圆形与圆形是否相交，圆形与多边形是否相交，多边形与多边形是否相交，球体与球体是否相交等等。碰撞检测在人工智能，物理引擎等众多领域都有运用。

由于任何一个物体都有可能与其他物体发生碰撞，则包含n个物体的碰撞检测过程中，最坏的情况可能需要进行n(n-1)/2 = O(n^2)次测试，平方时间复杂度通常会降低程序的运行速度。为了减少这种情况的发生，我们把碰撞检测分为两个阶段。粗略测试阶段（broad phase）-> 精确测试阶段（narrow phase）。

粗略测试阶段会通过简单的算法将即将可能会发生碰撞的物体划分出来，在将这些物体送到精确测试阶段，经过精确测试判断这些即将可能会发生碰撞的物体是否真的会发生碰撞，不去处理在这一时刻不会发生碰撞的物体。这样可以降低精确测试的物体数，从而降低检测的时间。

现在介绍上面提到的粗略测试中能将即将可能会发生碰撞的物体划分出来的算法-----包围体检测。包围体（BV）是用简单的图形将检测物包围起来的一种方法，可以是圆形，球形，矩形，多边形，长方体。二维情况下通常使用圆形，多边形，矩形。三维情况下通常使用球形，长方体。这些简单图形检测的计算量肯定是小于检测复杂图形的。

包围体有很多种：Circle包围体，轴对齐包围盒（AABB），有向包围盒（OBB），8-DOP，凸壳。从左到右包围图形越来越复杂，的包围效果越来越好，但应为图形越来越复杂检测所用时间也会越长。

今天实现AABB轴对齐包围盒

//2DGEBoundVol.h
#pragma once
#include <SDL.h>
#include <vector>
#include "2DGEBody.h"
#include "2DGEDraw.h"
struct AABB
{
    //以后可能会嵌入bodymanager
    std::vector<SDL_FPoint> vertices_ = {{0.0f, 0.0f},
                                         {0.0f, 0.0f},
                                         {0.0f, 0.0f},
                                         {0.0f, 0.0f} };
    
    void GetAABB(std::vector<Body>::iterator body);
    void RenderAABB(Brush& brush);
};

//2DGEBoundVol.cpp
#include "2DGEBoundVol.h"

void AABB::GetAABB(const std::vector<Body>::iterator body)
{
    if (body->shape_ == 0) {
        const float center_x = body->mass_center_.x;
        const float center_y = body->mass_center_.y;
        const float radius = body->radius_;
        this->vertices_[0] = { center_x - radius , center_y + radius };
        this->vertices_[1] = { center_x + radius , center_y + radius };
        this->vertices_[2] = { center_x + radius , center_y - radius };
        this->vertices_[3] = { center_x - radius , center_y - radius };
    }
    else if (body->shape_ == 1) {
        const std::vector<SDL_FPoint> vertices = body->vertices_;
        float max_x = -std::numeric_limits<float>::max();
        float max_y = -std::numeric_limits<float>::max();
        float min_x =  std::numeric_limits<float>::max();
        float min_y =  std::numeric_limits<float>::max();    
        for (int i = 0; i < vertices.size(); ++i) {
            if (vertices[i].x > max_x) {
                max_x = vertices[i].x;
            }
            if (vertices[i].x < min_x) {
                min_x = vertices[i].x;
            }
            if (vertices[i].y > max_y) {
                max_y = vertices[i].y;
            }
            if (vertices[i].y < min_y) {
                min_y = vertices[i].y;
            }
        }
        this->vertices_[0] = { min_x , max_y };
        this->vertices_[1] = { max_x , max_y };
        this->vertices_[2] = { max_x , min_y };
        this->vertices_[3] = { min_x , min_y };
    }


}

void AABB::RenderAABB(Brush& brush)
{
    brush.DrawPolygon(this->vertices_, 255, 100, 100, 255);
}