원 박스 충돌 감지 알고리즘
목차
인사말
아이디어
1단계. 원의 위치가 박스에 들어가는지 판단하라!
2단계. 실제 원의 위치, 반지름과 박스의 크기, 위치를 이용하여 충돌하는지 감지하라!
테스트
인사말
이번에 루키스(Rookiss)님의 강의를 들으면서 실습하던중, 충돌 파트에서 제목과 같은 알고리즘이 중간에 살짝 제시됬는데 나에게는 크게 흥미가 생겨서 도전하게 되었다.
이 방법은 이틀정도 고민해서 완성한 알고리즘인데 실험단계라서
테스트케이스에 따라 약간의 오차가 있을 가능성이 있다.
아이디어
우선 이 알고리즘은 총 2단계로 나뉘게 된다.
앞서서 자세히 기술하기 전에 대략적인 흐름은 어떠하냐면 우선 박스를 중심으로 큰 박스 4개를 만든뒤, 이 큰박스사이에 원의 위치점이 들어가는지 테스트한뒤 좀더 자세히 들어가서 실제 원과 박스사이의 거리로 판단한다.
일단 대략적으로 말했기때문에 이 글을 읽고 크게 와닿지 않을수 있기에 좀 더 자세하게 들어가보려 한다.
알고리즘 1단계
우선 최소한 박스의 최대크기와 원의 반지름을 합한 크기의 박스안에는 원의 위치점이 들어가 있어야한다.
따라서 위의 (많이 못그린)그림과 같이 가상의 박스를 실제 박스를 중심으로 4개를 만들어서 배치한뒤,
차례대로 박스안에 원의 위치가 속해있는지 판별한다.
우선 이 과정의 의미는 2가지가 있다.
[ 해당과정의 의미 ]
1. 원이 직사각형과 충돌하는지 미리 판별할 수 있다.
2. 좀더 정밀한 단계에서 해당 원의 위치가 어떤박스에 충돌하냐에 따라 계산될 식이 좀 변한다.
이 알고리즘의 c++코드 이다.
// Vec2는 2차원 벡터이다.
Vec2 s_pos = s1->GetOwner()->GetPos();
float s_radius = s1->GetRadius();
Vec2 b_pos = b2->GetOwner()->GetPos();
Vec2 b_size = b2->GetSize();
float w2 = b_size.x * 0.5F;
float h2 = b_size.y * 0.5F;
float maxDist = ::sqrtf(w2 * w2 + h2 * h2) + s_radius;
Vec2 box1_pos = b_pos + Vec2(maxDist, maxDist); // 1 1
Vec2 box2_pos = b_pos + Vec2(-maxDist, -maxDist); // -1 -1
Vec2 box3_pos = b_pos + Vec2(maxDist, -maxDist); // 1 -1
Vec2 box4_pos = b_pos + Vec2(-maxDist, maxDist); // -1 1
Vec2 maxDist2 = Vec2(maxDist * 2.0F, maxDist * 2.0F);
int8 contactedBlock = 0;
bool isContacted = IsPointOnBox(box1_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 1;
isContacted = IsPointOnBox(box2_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 2;
isContacted = IsPointOnBox(box3_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 3;
isContacted = IsPointOnBox(box4_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 4;코드를 자세히 보면 위의 그림으로 설명한 그대로이며, 질문이 나올것같은 부분은 maxDist에 2를 곱하고있는데
그 이유는 위 코드에서 maxDist는 그림에서의 (sqr + r)이 아닌 정확히는 (sqr + r) * 0.5F 이기 때문이다
또 IsPointOnBox함수는 박스의 위치, 크기, 원의 위치를 입력받아서 원의 위치가 박스 내부에 존재하는지 판별하는 함수이다.
이 함수는 직접 만들어 보기 바란다. 만들기 매우 쉽다.
알고리즘 2단계
앞의 단계에서는 대략적으로 원과 박스가 충돌하는지만 테스트해봤을뿐이다.
좀 더 정밀하게 계산할 필요성이 있다.
우선 밑의 그림과 같은 시나리오를 연출해보자.
우선 우리는 위의 ?가 적힌 보라색 벡터를 구하고싶은것이다.
내가 생각한 방법은 이렇다.
우선 박스를 중심으로한 right벡터와 박스의 위치에서 원의 위치로 향하는 벡터 사이의 각도 혹은 cos세타값을 알 필요가 있다.
식은 이렇게 된다.
내적과 cos의 연결식을 통해 다음과 같은 식을 유도할 수 있게되었다.
사실 theta를 직접 구할필요까진 없다.
왜냐하면 sin세타값도 구하긴해야되지만, cos = sqrt(1 - sin^2)식을 쓰면되기 때문이다.
이제 부터 본격적으로 위의 그림에서 노란색으로 칠한 삼각형을 이런식으로 두 삼각형으로 잘라서 생각해 보겠다.
현재 알고있는 상황및 정보는 이렇다.
우리가 알고싶은 정보인 빨간색벡터는 다음과 같이 구할 수 있다.
흠,, 식이 완성되긴 했지만, 뭔가 불필요한것들이 많이보인다.
이 식은 최적화 할 여지가 보이기 때문에 최적화까지 해보겠다.
이렇게 최적화함으로써 전체적으로 계산해야할 양도 덜었을뿐더러 무엇보다 sinTheta값을 구하지 않아도 된다.
마지막으로 (c + D + 원의 반지름)와 박스와 원 사이의 거리를 비교해서
박스에서 원사이의 거리 <= (c + D) + 원의 반지름식이 참이면 충돌하고 아니면 충돌하지 않는단 뜻이다.
다음은 나의 c++코드인데, 중간에 설명안한 부분이 있기에 설명안한부분은 코드설명하면서 추가로 기술하겠다.
// Phase 1
Vec2 right = Vec2(1.0F, 0.0F);
switch (contactedBlock)
{
case 0:
return 충돌하지 않음;
case 1:
right.x *= 1.0F;
break;
case 2:
right.x *= -1.0F;
break;
case 3:
right.x *= 1.0F;
break;
case 4:
right.x *= -1.0F;
break;
}
// Phase 2
float axisLength = w2;
Vec2 boxToSph = s_pos - b_pos;
float boxToSphLen = boxToSph.Length();
float cosTheta = right.Dot(boxToSph) / boxToSphLen;
if (cosTheta < 0.5F)
{
cosTheta += 0.5F;
axisLength = h2;
}
// Phase 3
if(::fabsf(cosTheta - 0.5F) <= 0.1F)
{
if (boxToSphLen <= axisLength + s_radius)
return 충돌;
else
return 충돌하지 않음;
}
// Phase 4
float a = axisLength * cosTheta;
float b = axisLength / cosTheta - axisLength * cosTheta;
float toSphLen = a + b;
if (boxToSphLen <= toSphLen + s_radius)
return 충돌;
return 충돌하지 않음;
Phase 1과 2는 연결이 되는 부분인데, 아까 처음 알고리즘 1 에서 큰 박스 4개를 통해 원의 위치가 박스를 중심으로 어느 위치에 존재하는지 판별하는 파트가 있었다.
그 파트의 목적중 하나가 이 부분인데, (박스에서 원으로 가는 벡터)와 박스의 right벡터 사이의 각을 정확히 구하기 위해서는 해당 벡터들의 cos세타값이 0.5 이상인지 이하인지 판별할 필요성이 있으며, 만약 0.5 이하라면 0.5를 더해줄 필요가 있고, 이때 W도 박스의 가로길이가 아니라 세로길이가 된다.
[ 토막 상식 ]
cos세타는 0도에 가까울수록 1이되며 90도에 가까울수록 0이된다.
즉 cos세타가 0.5이하 라는 소리는 45도이상 이라는 의미다.
당연한것이, cos세타값이 0.5이하가 되면 삼각형이 아니라 모양이 불규칙한 다각형으로 변모하므로 위 과정은 필수적으로 들어가야 한다.
Phase3은 원이 박스를 기준으로 일직선상에서 가까운지 판별하는것이다.
일직선상에서 가까우면, Phase4의 과정을 거칠필요가 없을뿐더러
오차가 생기기때문에 미리 (박스-원 사이 거리) <= 원에서 가장 가까운 축의 길이 + 원의 반지름을 통해 미리 충돌처리를 해준다.
마지막으로 Phase4는 위의 공식으로 설명했으니 생략하겠다.
전체 코드이다.
bool CheckCollisionSphere2Box(SphereCollider* s1, BoxCollider* b2)
{
Vec2 s_pos = s1->GetPos();
float s_radius = s1->GetRadius();
Vec2 b_pos = b2->GetPos();
Vec2 b_size = b2->GetSize();
float w2 = b_size.x * 0.5F;
float h2 = b_size.y * 0.5F;
float maxDist = ::sqrtf(w2 * w2 + h2 * h2) + s_radius;
Vec2 box1_pos = b_pos + Vec2(maxDist, maxDist); // 1 1
Vec2 box2_pos = b_pos + Vec2(-maxDist, -maxDist); // -1 -1
Vec2 box3_pos = b_pos + Vec2(maxDist, -maxDist); // 1 -1
Vec2 box4_pos = b_pos + Vec2(-maxDist, maxDist); // -1 1
Vec2 maxDist2 = Vec2(maxDist * 2.0F, maxDist * 2.0F);
int8 contactedBlock = 0;
bool isContacted = IsPointOnBox(box1_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 1;
isContacted = IsPointOnBox(box2_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 2;
isContacted = IsPointOnBox(box3_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 3;
isContacted = IsPointOnBox(box4_pos, maxDist2, s_pos);
if (isContacted)
contactedBlock = 4;
Vec2 right = Vec2(1.0F, 0.0F);
switch (contactedBlock)
{
case 0:
return false;
case 1:
right.x *= 1.0F;
break;
case 2:
right.x *= -1.0F;
break;
case 3:
right.x *= 1.0F;
break;
case 4:
right.x *= -1.0F;
break;
}
float axisLength = w2;
Vec2 boxToSph = s_pos - b_pos;
float boxToSphLen = boxToSph.Length();
float cosTheta = right.Dot(boxToSph) / boxToSphLen;
if (cosTheta < 0.5F)
{
cosTheta += 0.5F;
axisLength = h2;
}
if(::fabsf(cosTheta - 0.5F) <= 0.1F)
{
if (boxToSphLen <= axisLength + s_radius)
return true;
else
return false;
}
// float a = axisLength * cosTheta;
// float b = axisLength / cosTheta - axisLength * cosTheta;
float toSphLen = axisLength / cosTheta;
if (boxToSphLen <= toSphLen + s_radius)
return true;
return false;
}
테스트
인사말에서 말한 강의를 보면서 직접 돌려보니 거의 맞아 떨어지는 것을 볼수 있었다.
뭔가 생각한대로 만들어 지니까 기분이 좋다 ㅎㅎㅎ
