注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

物理引擎中基于AABB碰撞盒的SAP碰撞检测  

2018-02-01 21:27:48|  分类: 物理引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、碰撞检测中的broad phase中的常见算法
该算在 这篇文章 中有比较简单而准确的描述,由于这里描述的思路并不复杂,但是是所有物理引擎中碰撞检测的入门级功课,所以这里写代码加深下对于该简单算法的理解。同样为了避免链接失效,这个地方拷贝下关键内容:

Let's see what this means using the simplest "flavor" of the SAP algorithms, non-persistent single axis SAP:

  1. Fill a list called "axisList" with all objects in the world. Sort this list on one axis (here the x-axis) by the begin of the bounding box (Sort by Object.BoundingBox.Min.X, With "Min" and "Max" the vectors defining the bounding box). So you know that the most left point of object5 is more left then the most left point on object6 when you look directly at the X-Axis.
  2. Create a new temporary list called "activeList". You begin on the left of your axisList, adding the first item to the activeList. Now you have a look at the next item in the axisList and compare it with all items currently in the activeList (at the moment just one): If the new item's left is greater then the current activeList-item right, then remove the activeList-item from the activeList – otherwise report a possible collision between the new axisList-item and the current activeList-item. Add the new item itself to the activeList and continue with the next item in the axisList.

二、简单代码验证
下面代码没有在真是环境下运行过,不保证正确性。
1、测试代码
tsecer@harry: cat AABBSAP.cpp 
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Box
{
int miMin;
int miMax;
};

bool operator < (const Box &rlhs, const Box &rhs)
{
return rlhs.miMin < rhs.miMin;
}

struct Pair
{
Box mb0;
Box mb1;
};

vector<Box> gstAxisBox, gstActiveBox;
vector<Pair> gstPair;
void addBox(Box &rstBox)
{
for (auto iter = gstActiveBox.begin(); iter != gstActiveBox.end(); )
{
if (iter->miMax < rstBox.miMin)
{
//remove iter form activeBox
iter = gstActiveBox.erase(iter);
continue;
}
else if (iter->miMax > rstBox.miMin)
{
//report collision
gstPair.push_back((Pair){*iter, rstBox});
}
iter++;
}
//add rstBox to activeBox
gstActiveBox.push_back(rstBox);
}

void InitializeBoxList(int iBoxCount, int iRange)
{
srand(time(NULL));
for (int i = 0; i < iBoxCount; i++)
{
int min = rand() % iRange, max = rand() % iRange; 
if (min > max)
{
swap(min, max);
}
gstAxisBox.push_back((Box){min, max});
}
}

int main(int argc, char *argv[])
{
InitializeBoxList(argc > 1 ? atoi(argv[1]) : 3, 
 argc > 2 ? atoi(argv[2]) : 20);
std::sort(gstAxisBox.begin(), gstAxisBox.end());
printf("randomize AxisBox list\n");
for (auto iter = gstAxisBox.begin(); iter != gstAxisBox.end(); iter++)
{
printf("box[%d]\t[%d,\t%d]\n", iter - gstAxisBox.begin(), iter->miMin, iter->miMax);
addBox(*iter);
}
printf("\n");
for (auto iter = gstPair.begin(); iter != gstPair.end(); iter++)
{
printf("b0min\t%d\tb0max\t%d\tb1min\t%d\tb1max\t%d\n", iter->mb0.miMin, iter->mb0.miMax, iter->mb1.miMin, iter->mb1.miMax);
}
return 0;
}

2、编译之后运行结果
tsecer@harry: g++ -std=c++11 AABBSAP.cpp 
tsecer@harry: ./a.out 5 20
randomize AxisBox list
box[0] [1, 7]
box[1] [2, 16]
box[2] [7, 11]
box[3] [15, 18]
box[4] [16, 17]

b0min 1 b0max 7 b1min 2 b1max 16
b0min 2 b0max 16 b1min 7 b1max 11
b0min 2 b0max 16 b1min 15 b1max 18
b0min 15 b0max 18 b1min 16 b1max 17
tsecer@harry: 

  评论这张
 
阅读(93)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018