# 矩形旋转碰撞,OBB方向包围盒算法实现

P点为矩形在X轴上的投影点，矩形在垂直轴上的投影点为原点。这里也能看出来，点P所在的矩形轴， 在X轴上的投影长度为OP，假设矩形逆时针绕远点O旋转。OP在X轴上的投影长度变小，直到为0。OP垂直于X轴。也就是，OP在X轴上的投影长度的最大与最小值。这也解释了。为什么我们选择检測轴为垂直于多边形边的轴，由于在这些轴上我们能取到极值，中间的那些轴就不是必需检測了。

/**
* dot-multiply
*/
private float dot(float[] axisA, float[] axisB) {
return Math.abs(axisA[0] * axisB[0] + axisA[1] * axisB[1]);
}

// unit vector of x axis
private float[] axisX;
// unit vector of y axis
private float[] axisY;

// 0 -360
private float rotation;

/**
* Set axis x and y by rotation
*
* @param rotation float 0 - 360
*/
public OBB setRotation(float rotation) {
this.rotation = rotation;

this.axisX[0] = MathUtils.cos(rotation);
this.axisX[1] = MathUtils.sin(rotation);

this.axisY[0] = -MathUtils.sin(rotation);
this.axisY[1] = MathUtils.cos(rotation);

return this;
}

2条检測轴的向量和就是中心点到矩形一个顶点的向量，所以投影半径也是中心点到矩形顶点的向量投影长度。注意向量的方向会影响投影长度。

2个矩形检測过程中，每次以一个矩形的检測轴为坐标系，投影还有一个矩形的检測轴。

private float halfWidth;

private float halfHeight;

/**
* Get axisX and axisY projection radius distance on axis
*/

// axis, axisX and axisY are unit vector

// projected axisX to axis
float projectionAxisX = this.dot(axis, this.axisX);
// projected axisY to axis
float projectionAxisY = this.dot(axis, this.axisY);

return this.halfWidth * projectionAxisX + this.halfHeight * projectionAxisY;
}


/**
* OBB is collision with other OBB
*/
public boolean isCollision(OBB obb) {
// two OBB center distance vector
float[] centerDistanceVertor = {
this.centerPoint[0] - obb.centerPoint[0],
this.centerPoint[1] - obb.centerPoint[1]
};

float[][] axes = {
this.axisX,
this.axisY,
obb.axisX,
obb.axisY,
};

for(int i = 0; i < axes.length; i++) {
<= this.dot(centerDistanceVertor, axes[i])) {
return false;
}
}

return true;
}


java代码：

/**
* @author scott.cgi
* @since  2012-11-19
*
* Oriented bounding box
*/
public class OBB {

private float[] centerPoint;

private float halfWidth;

private float halfHeight;

// unit vector of x axis
private float[] axisX;
// unit vector of y axis
private float[] axisY;

// 0 -360
private float rotation;

private float scaleX;
private float scaleY;

private float offsetAxisPointDistance;

/**
* Create default OBB
*
* @param x bornCenterX x
* @param y bornCenterY Y
* @param halfWidth
* @param halfHeight
*/
public OBB(float bornCenterX, float bornCenterY, float halfWidth, float halfHeight) {

this.halfWidth  = halfWidth;
this.halfHeight = halfHeight;

this.scaleX = 1.0f;
this.scaleY = 1.0f;

this.centerPoint = new float[] {
bornCenterX,
bornCenterY
};

this.axisX = new float[2];
this.axisY = new float[2];

float[] offsetAxisPoint = new float[] {
bornCenterX - Director.getHalfScreenWidth(),
bornCenterY - Director.getHalfScreenHeight()
};

this.offsetAxisPointDistance = (float) Math.sqrt(this.dot(offsetAxisPoint, offsetAxisPoint));

this.setRotation(0.0f);
}

/**
* Create default OBB with born in center screen
*
* @param halfWidth
* @param halfHeight
*/
public OBB(float halfWidth, float halfHeight) {
this(Director.getHalfScreenWidth(), Director.getHalfScreenHeight(), halfWidth, halfHeight);
}

/**
* Get axisX and axisY projection radius distance on axis
*/

// axis, axisX and axisY are unit vector

// projected axisX to axis
float projectionAxisX = this.dot(axis, this.axisX);
// projected axisY to axis
float projectionAxisY = this.dot(axis, this.axisY);

return this.halfWidth * this.scaleX * projectionAxisX + this.halfHeight * this.scaleY * projectionAxisY;
}

/**
* OBB is collision with other OBB
*/
public boolean isCollision(OBB obb) {
// two OBB center distance vector
float[] centerDistanceVertor = {
this.centerPoint[0] - obb.centerPoint[0],
this.centerPoint[1] - obb.centerPoint[1]
};

float[][] axes = {
this.axisX,
this.axisY,
obb.axisX,
obb.axisY,
};

for(int i = 0; i < axes.length; i++) {
<= this.dot(centerDistanceVertor, axes[i])) {
return false;
}
}

return true;
}

/**
* dot-multiply
*/
private float dot(float[] axisA, float[] axisB) {
return Math.abs(axisA[0] * axisB[0] + axisA[1] * axisB[1]);
}

/**
* Set axis x and y by rotation
*
* @param rotation float 0 - 360
*/
public OBB setRotation(float rotation) {
this.rotation = rotation;

this.axisX[0] = MathUtils.cos(rotation);
this.axisX[1] = MathUtils.sin(rotation);

this.axisY[0] = -MathUtils.sin(rotation);
this.axisY[1] = MathUtils.cos(rotation);

this.setCenter(this.centerPoint[0], this.centerPoint[1]);

return this;
}

/**
* Set OBB center point and will add offsetAxis value
*/
public OBB setCenter(float x, float y) {
float offsetX = this.offsetAxisPointDistance * MathUtils.cos(this.rotation);
float offsetY = this.offsetAxisPointDistance * MathUtils.sin(this.rotation);

this.centerPoint[0] = x + offsetX;
this.centerPoint[1] = y + offsetY;

return this;
}

/**
* Set OBB scale x, y
*/
public OBB setScale(float scaleX, float scaleY) {
this.scaleX = scaleX;
this.scaleY = scaleY;

return this;
}

public float getRotation() {
return this.rotation;
}

public float getCenterX() {
return this.centerPoint[0];
}

public float getCenterY() {
return this.centerPoint[1];
}

public float getHalfWidth() {
return this.halfWidth * this.scaleX;
}

public float getHalfHeight() {
return this.halfHeight * this.scaleY;
}

}


c 代码：

/*
* OBBRect.h
*
*  Created on: 2013-2-11
*  Author: scott.cgi
*/

#ifndef OBBRect_Rect_H_
#define OBBRect_Rect_H_

#include <stdbool.h>

#include "Mojoc/Graphics/Draw/Rect.h"
#include "Mojoc/Toolkit/Def/CodeStyle.h"
#include "Mojoc/Toolkit/Utils/AMathUtils.h"
#include "Mojoc/Toolkit/Def/StructMember.h"

#ifdef __cplusplus
extern "C" {
#endif

typedef struct OBBRect OBBRect;

/**
* Oriented bounding box in Rect shape
* Use openGL world coordinate system
*/
struct OBBRect {

float   centerX;
float   centerY;

/** Set origin(0,0) when obbRect create */
float   originX;
float   originY;

/** Clockwise [0 - 360] */
float   rotation;
float   scaleX;
float   scaleY;

Get(
/** Unit vector of x axis */
StructMember(Vector2, xAxis);

/** Unit vector of y axis */
StructMember(Vector2, yAxis);

Rect*   rect;

/** Distance of center point to origin(0, 0 */
float   offsetDistance;
/** Degree of vector which center point to origin(0, 0 */
float   offsetDegree;

float   halfWidth;
float   halfHeight;
);

};

typedef struct {
OBBRect* (*create) (Rect* rect);
void     (*init)   (Rect* rect, Out(OBBRect* obbRect));

/**
* Set obbRect rotation or origin x,y called updateCenter for
* update obbRect center x,y
*/
void (*updateCenter)(OBBRect* obbRect);

/**
* Set obbRect rotation
*/
void (*setRotation) (OBBRect* obbRect, float rotation);

/**
* OBBRect is collision with other OBBRect
*/
bool (*isCollision) (OBBRect* obbRect, OBBRect* otherObb);

/**
* Get real width with scaleX
*/
float (*getWidth)   (OBBRect* obbRect);

/**
* Get real height with scaleY
*/
float (*getHeight)  (OBBRect* obbRect);

} _AOBBRect;

extern _AOBBRect AOBBRect;

#ifdef __cplusplus
}
#endif

#endif /* OBBRect_H_ */


/*
* OBBRect.c
*
*  Created on: 2013-2-11
*  Author: scott.cgi
*/

#include <malloc.h>
#include <math.h>

#include "Mojoc/Physics/OBBRect.h"
#include "Mojoc/Toolkit/Utils/AMathUtils.h"
#include "Mojoc/Toolkit/Platform/Log.h"

static void updateCenter(OBBRect* obbRect) {
obbRect->centerX = obbRect->originX +
obbRect->offsetDistance * obbRect->scaleX *
AMathUtils_Cos(obbRect->rotation + obbRect->offsetDegree);

obbRect->centerY = obbRect->originY +
obbRect->offsetDistance * obbRect->scaleY *
AMathUtils_Sin(obbRect->rotation + obbRect->offsetDegree);
}

static void setRotation(OBBRect* obbRect, float rotation) {
obbRect->xAxis->x = AMathUtils_Cos(rotation);
obbRect->xAxis->y = AMathUtils_Sin(rotation);

obbRect->yAxis->x = -AMathUtils_Sin(rotation);
obbRect->yAxis->y =  AMathUtils_Cos(rotation);

obbRect->rotation = rotation;
}

/**
* Get axisX and axisY projection radius distance on unit axis
*/
static inline float getProjectionRadius(OBBRect* obbRect, Vector2* axis) {

// axis, axisX and axisY are unit vector

// projected axisX to axis
float projectionAxisX = AMathUtils_DotMultiply2(axis->x, axis->y, obbRect->xAxis->x, obbRect->xAxis->y);
// projected axisY to axis
float projectionAxisY = AMathUtils_DotMultiply2(axis->x, axis->y, obbRect->yAxis->x, obbRect->yAxis->y);

return obbRect->halfWidth  * obbRect->scaleX * projectionAxisX +
obbRect->halfHeight * obbRect->scaleY * projectionAxisY;

}

static bool isCollision(OBBRect* obbRect, OBBRect* otherObb) {
// two OBBRect center distance vector
Vector2 distanceVec = {
obbRect->centerX - otherObb->centerX,
obbRect->centerY - otherObb->centerY,
};

Vector2* axes[] = {
obbRect->xAxis,
obbRect->yAxis,
otherObb->xAxis,
otherObb->yAxis,
};

for (int i = 0; i < 4; i++) {
AMathUtils_DotMultiply2(distanceVec.x, distanceVec.y, axes[i]->x, axes[i]->y)) {

return false;
}
}

return true;
}

static float getWidth(OBBRect* obbRect) {
return (obbRect->halfWidth * 2) * obbRect->scaleX;
}

static float getHeight(OBBRect* obbRect) {
return (obbRect->halfHeight * 2) * obbRect->scaleY;
}

static inline void initOBBRect(OBBRect* obbRect, Rect* rect) {
obbRect->rect           = rect;

obbRect->halfWidth      = (rect->right   - rect->left) / 2;
obbRect->halfHeight     = (rect->bottom  - rect->top)  / 2;

obbRect->scaleX         = 1.0f;
obbRect->scaleY         = 1.0f;

obbRect->originX        = 0.0f;
obbRect->originY        = 0.0f;

obbRect->centerX        = rect->left + obbRect->halfWidth;
obbRect->centerY        = rect->top  - obbRect->halfHeight;

obbRect->offsetDistance = sqrtf(AMathUtils_DotMultiply2(obbRect->centerX, obbRect->centerY, obbRect->centerX, obbRect->centerY));
obbRect->offsetDegree   = AMathUtils_Atan2(obbRect->centerX, obbRect->centerY);

LogD("centerX = %f, centerY = %f", obbRect->centerX, obbRect->centerY);
LogD("offsetDistance = %f, offsetDegree = %f",
obbRect->offsetDistance, obbRect->offsetDegree);

setRotation(obbRect, 0.0f);
}

static OBBRect* create(Rect* rect) {
OBBRect* obbRect = (OBBRect*) malloc(sizeof(OBBRect));
initOBBRect(obbRect, rect);

return obbRect;
}

static void init(Rect* rect, Out(OBBRect* obbRect)) {
initOBBRect(obbRect, rect);
}

_AOBBRect AOBBRect = {
create,
init,

updateCenter,
setRotation,
isCollision,
getWidth,
getHeight,
};

|
1月前
|

Python3实现旋转数组的3种算法
Python3实现旋转数组的3种算法
29 0
|
1月前
|

☆打卡算法☆LeetCode 223. 矩形面积 算法解析
☆打卡算法☆LeetCode 223. 矩形面积 算法解析
130 0
|
1月前
|

【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵
40 0
|
8月前
|

C++前缀和算法应用：矩形区域不超过 K 的最大数值和
C++前缀和算法应用：矩形区域不超过 K 的最大数值和
29 0
|
8月前
|

C++算法：柱状图中最大的矩形
C++算法：柱状图中最大的矩形
34 0
|
7月前
|

【Python】蒙特卡洛模拟 | PRNG 伪随机数发生器 | 马特赛特旋转算法 | LCG 线性同余算法 | Python Random 模块
【Python】蒙特卡洛模拟 | PRNG 伪随机数发生器 | 马特赛特旋转算法 | LCG 线性同余算法 | Python Random 模块
158 0
|
1天前
|

【6月更文挑战第16天】JavaScript中的基本碰撞检测涉及AABB（轴对齐边界框）方法，常用于2D游戏。Rectangle类定义了矩形的属性，并包含一个collidesWith方法，通过比较边界来检测碰撞。若两矩形无重叠部分，四个条件（关于边界相对位置）均需满足。此基础算法适用于简单场景，复杂情况可能需采用更高级的检测技术或物理引擎库。
16 6
|
4天前
|

【经典LeetCode算法题目专栏分类】【第6期】二分查找系列：x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列：x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
9 0
|
8天前
|

python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
14 2
|
11天前
|

12 1