5월, 2016의 게시물 표시

좌표 변환: 회전 이동

이미지
아래 그림에서와 같이, 원래의 좌표를 (x, y)라 하고, y축으로부터의 각도를 θ라고 하자. 또, 회전 시키고자하는 각도를 δ라 하고, 회전된 좌표를 (x', y')라고 한다.
이 때, 회전의 기준점과 원래의 좌표 사이의 거리를 r이라고 하면, 회전된 이후의 좌표와 회전 기준점 사이의 거리 또한 r로써 동일하다.

수식으로 정리하면,
x = r sinθ
y = r cosθ

x' = r sin(θ+δ)
y' = r cos(θ+δ)

삼각함수의 덧셈정리를 이용하여 x'와 y'를 풀어보면,

x' = r (sinθ cosδ + cosθ sinδ)
   = r sinθ cosδ + r cosθ sinδ
y' = r (cosθ cosδ - sinθ sinδ)
   = r cosθ cosδ - r sinθ sinδ

x = r sinθ, y = r cosθ이므로,
x' = x cosδ + y sinδ
y' = y cosδ - x sinδ

δ가 반시계방향인 경우에는,
x' = x cosδ - y sinδ
y' = y cosδ + x sinδ
라는 수식으로 정리될 수 있다.


이렇게 구한 공식을 도형의 각 꼭지점에 대해서 적용하면 회전 이동한 도형을 구할 수 있다.

public void rotateBy(float d, float x0, float y0) { float dX = x - x0; float dY = y - y0; double rad = Math.abs(Math.toRadians(d)); float cosD = (float) Math.cos(rad); float sinD = (float) Math.sin(rad); if (d>=0) { x = dX * cosD + dY * sinD; y = dY * cosD - dX * sinD; } else { x = dX * cosD - dY * sinD; y = dY * cosD + dX * sin…

좌표 변환: 대칭 이동

이미지
점에 대한 대칭 이동 대칭 이동의 기준점과 도형의 꼭지점 사이의 거리를 구한다음, 기준점을 지나 그 거리만큼 더 이동하면 대칭 이동한 점의 좌표를 구할 수 있다.
우선, 기준점과 다각형의 각 꼭지점들 간의 거리 dx와 dy를 구한다.
각각의 꼭지점에 대해서 평행 이동한 다음 이동한 점들을 연결하면 대칭 이동한 도형을 얻을 수 있다.

축에 대한 대칭 이동 x축과 나란한 축에 대한 대칭의 경우에는 각 꼭지점의 x좌표는 변하지 않고 y좌표만 대칭 이동하면 된다.
마찬가지로, y축에 나란한 축에 대한 대칭의 경우에는 각 꼭지점의 y좌표가 변하지 않는다.
위 그림에서 왼쪽은 점에 대한 대칭 이동이며, 오른쪽은 직선에 대한 대칭이동이다.
그려놓고 보니 점에 대한 대칭 이동은 회전 이동과 같은 결과가 되었다.

좌표 변환: 스케일

이미지
평면 상의 어떤 도형의 크기를 변경하기 위해서는 도형을 구성하는 꼭지점의 좌표 이외에도 배율을 나타내는 scale factor와 크기 변경의 기준점 좌표도 알아야 한다.

Scale factor는 1.0을 기준으로 이보다 크면 확대, 작으면 축소로 가정한다.

우선, 도형의 각 꼭지점 좌표와 기준점 좌표 사이의 거리(d)를 구한다. 이 때, x 성분과 y 성분을 분리하는 것이 좋다.

이렇게 구한 각각의 거리 값에 배율을 곱한다. 그러면, 기준점으로부터 계산된 거리만큼을 이동한 새로운 점의 좌표를 얻을 수 있고, 이 좌표들은 크기가 변환된 새로운 도형의 꼭지점들이다.
위 그림에서는 크기 변경의 기준점을 붉은 색으로 표시했으며, 왼쪽에서는 조형의 가운데에, 오른쪽에서는 왼쪽 아래에 각각 지정하였다. 파란색 사각형을 2배 크기로 확대한 도형이 초록색 도형이다.


어떤 도형의 크기를 s배로 변경하는 것은 기준점에서 도형의 각 꼭지점 까지의 거리를 s배로 변경하는 것이다.

좌표 변환: 이동

이미지
평면 상의 어떤 도형을 x방향으로 dx만큼, y 방향으로 dy만큼 이동하려는 경우,
다각형의 각 꼭지점(원의 경우에는 중심점을) 좌표 (x, y)에 dx, dy를 더한다.

즉, 점 (x, y)을 dx, dy만큼 이동한 새로운 점의 좌표를 (x', y')라고 할 때,
x' = x + dx
y' = y + dy
이다.

이를 각 꼭지점에 대해서 수행하면 평행이동된 도형을 구할 수 있다.

충돌 체크: Circle vs Circle

이미지
원과 원의 충돌 테스트는 의외로 간단하다.
우선, 피타고라스의 정리를 사용해서 원의 중심점 간의 거리를 구한다.

중심점 간의 거리가 두 반지름의 합보다 크면, 두 원은 서로 충돌하지 않은 것이다.중심점 간의 거리가 두 반지름의 합보다 작으면, 두 원은 서로 충돌한 것이다.중심점 간의 거리와 두 반지름의 합이 같다면, 두 원은 서로 붙어 있는 경우이다.

충돌 체크: Oriented Bounding Box

이미지
이전 글 AABB에 이어서,
위의 그림과 같은 경우 AABB 테스트에서는 충돌로 판정된다.
하지만 이것은 우리가 원하는 충돌 판정이 아니다. 따라서, 필요하다면 Oriented Bounding Box 방식으로 보다 세밀하게 충돌 판정을 해 줄 필요가 있다.
OBB란 바운딩 박스가 회전 되어서 좌표축에 나란하지 않다는 얘기다.


OBB 방식의 충돌 문제를 구현하기 위한 여러 방식들 가운데 SAT라는 것이 있다.
Separating Axis Theorem
두 개의 바운딩 박스가 서로 충돌하지 않는다면, 둘 사이를 가르는 직선이 존재한다. 바꾸어 말하자면, 둘 사이를 가르는 임의의 직선이 존재한다면, 두 개의 바운딩 박스는 서로 충돌하지 않는다고 할 수 있다.
위 그림에 그린 임의의 붉은 직선이 Separating Axis이다.
Separating Axis에 직교하는 다른 직선에 바운딩 박스를 투영시켜 보자. 이 때 직선 상에 투영된 두 개의 선분이 서로 겹치지 않는다면 두 개의 바운딩 박스는 서로 충돌하지 않는다고 말할 수 있다.

그렇다면,
Separating Axis는 어떻게 찾을 것인가. 라는 새로운 문제를 맞이하게 된다.

Separating Axis는 다각형을 구성하고 있는 변들 중 하나 이상과 나란하다.
절차
바운딩 박스를 구성하는 변들 중 하나를 선택해서,
그 변과 나란한 가상의 축에 직교하는 임의의 축을 가정하고,
그 축에 바운딩 박스를 투영시킨다.
만일, 두 개의 선분이 겹치지 않으면 서로 충돌하지 않음으로 판정하고 종료,
두 선분이 서로 겹친다면 다른 변을 선택해서 반복 수행.

사각형 vs 사각형의 문제인 경우 최대 8개의 축에 대해 충돌 테스트를 시행해 보아야 한다. 그러나, 위 그림과 같이 서로 나란한 변이 있다면 시행 횟수는 줄어든다.



[Tip]
OBB는 직사각형이 아니어도, 다각형이어도 적용 가능하다. 그러나, 모서리가 안쪽으로 파인 모양에는 적용이 안된다.

[참고]
http://www.dyn4j.org/2010/01/sat/


충돌 체크: Axis Aligned Bounding Box

이미지
게임 개발에서 충돌 테스트의 가장 기본적인 전략은 AABB인데, Axis Aligned Bounding Box란 좌표 축에 나란한 사각형으로서, 캐릭터를 감싸는 최소한의 너비와 높이를 가진 직사각형이다.
두 개의 좌표축에 나란한 직사각형이 조금이라도 서로 겹치는지를 판단하면 된다.

바운딩 박스 A의 최대 x 좌표(right)가 바운딩 박스 B의 최소 x 좌표(left)보다 작으면 충돌이 아니다.바운딩 박스 A의 최소 x 좌표(left)가 바운딩 박스 B의 최대 x 좌표(right)보다 크면 충돌이 아니다.바운딩 박스 A의 최대 y 좌표(top)가 바운딩 박스 B의 최소 y 좌표(bottom)보다 작으면 충돌이 아니다.바운딩 박스 A의 최소 y 좌표(bottom)가 바운딩 박스 B의 최대 y 좌표(top)보다 크면 충돌이 아니다. 이를 자바 코드로 작성하면 다음과 같다. 참 쉽다, 비교 몇 번이면 끝난다.
public static boolean checkAABB(RectF a, RectF b) {return a.right > b.left && a.left < b.right && a.top > b.bottom && a.bottom < b.top; }
그런데, 아래 그림에서처럼 캐릭터가 회전을 한다거나 하는 경우에는 정확도가 떨어진다는 단점이 있다. 다음 글에 이어서...