2012년 12월 3일 월요일

Fast Object Picking

예제코드 다운받기

  • C#과 XNA를 이용해서 만들었습니다.
  • XNA를 설치하셔야 합니다.


게임보다는 에디터 따위의 툴에서 더 유용한 기법입니다. 예전에 개인 프로젝트에서 장난삼아 만들어 봤던 놈인데 그뒤로도 몇번이나 동일한 기법을 여러 툴에서 구현하다보니 올리면 유용하겠다 싶어서..... 이미 알고계시는 분들도 많겠지만 혹시나 모르시는 분들을 위해 여기 올리면 좋겠다고 생각해서 올립니다.

이 기법이 해결하려고 하는 건 간단합니다. 맵 에디터 같은 프로그램에서 화면에 있는 물체를 마우스로 클릭해서 선택하는걸 졸라~ 빠르게 구현하는 겁니다.

말로는 쉽죠?... 그런데 보통 구현들 어떻게 하셨나요?

흔히 쓰던 광선 vs AABB 충돌검출 방법
제가 흔히 봤던 방법중 하나는 마우스 클릭한 위치부터 화면 안쪽으로 광선(ray)를 쏴주면서 그 광선과 각 물체의 AABB의 충돌검사를 한뒤 가장 가까이에 있는 물체를 선택하는 거였습니다.

예를 들어 아래 이미지에서 오른쪽 가장자리가 화면이라고 가정하면 이런식으로 ray를 쏴서 aabb를 찾는거죠.


그런데 이 방법에 문제들이 좀 있습니다

  • 월드에 물체들이 많으면 충돌검사 시간 꽤 걸립니다
  • AABB와 충돌검사를 하므로 픽셀단위로 정확한 충돌검사가 불가능합니다.



제가 쓰는 렌더타겟과 물체 ID를 이용한 방법
저는 GPU를 이용해서 위 문제점들을 해결했습니다. 알고리듬은 매우 간단합니다. 자세한 코드는 위에 첨부해 놓은 예제코드를 봐주세요.
  1. 각 물체마다 고유 해쉬 아이디(32비트 정수)를 부여한다.
  2. 화면크기와 동일한 A8R8G8B8 렌더타겟을 하나 만든다. (이후 ID맵이라 부름)
  3. ID Map맵 렌더타겟을 설정한다.
  4. 모든 물체를 그려주면서 물체 해쉬(32비트)값을 8비트씩 짤라 R,G,B,A채널에 써준다
  5. 마우스가 클릭된 위치의 픽셀을 읽어온다
  6. 그 해쉬값과 동일한 물체를 선택한다.
  7. 선택된 물체로 하고 싶은 짓을 한다 -_-
  8. 끝 -_-

해쉬아이디
해쉬 아이디는 아무렇게나 생성이 가능합니다. 각 물체마다 고유하기만 하면 되죠. 제 예제에서는 그냥 물체 이름인 string으로부터 해쉬 아이디를 생성했습니다.

해쉬아이디를 색상으로 바꾸는 법
해쉬 아이디를 RGBA로 바꾸는 코드는 다음과 같습니다.

private static Color HashIDToColour(int hash)
{
    int a = (hash >> 24) & 0xff;
    int b = (hash >> 16) & 0xff;
    int g = (hash >> 8) & 0xff;
    int r = hash & 0xff;

    return new Color(r, g, b, a);
}

이 후 이걸 셰이더 함수로 대입해준 뒤

ColourFX.Parameters["Colour"].SetValue(HashIDToColour(go.Hash).ToVector4());

셰이더 안에서 다음과 같이 그려만 주면 됩니다.
float4 ps(VtxOut In) : COLOR
{
return Colour;
}

해쉬아이디 읽어오기
매우 간단합니다. 그냥 그 픽셀값을 32비트로 읽어오면 끝입니다. (이미 해쉬 ID에서 색상으로 변환할때 byte순서및 엔디안 문제를 고려했거든요

public int PickObject(int x, int y)
{
    int hash = Hash.INVALID;

    int [] pickedPixel = new int[1];

    IDMap.GetData<int>(0, new Rectangle(x, y, 1, 1), pickedPixel, 0, 1);

    hash = pickedPixel[0];

    return hash;
}

예제 결과
일단 제 샘플 코드를 실행해보면 다음과 같은 그림이 보일겁니다.

메인 화면에 3개의 공이 있고.. 오른쪽 아래는 ID맵입니다.

여기서 파란색 공위에 마우스를 클릭하면 다음과 같이 됩니다.

현재 선택된 물체를 노란색으로 표현했습니다. 그리고 현재 선택된 물체를 ID 맵에 안그려서 다시 한번 더 클릭을 하면 그뒤에 있는 물체가 대신 선택되게 만들었습니다.


이정도면 대충 보여드린듯 하죠? 자세한건 직접 받아서 실행해보세요.. -_-;

기타 응용
최근에 이 기법을 응용해서 물체 ID 대신에 물체의 깊이를 저장도 해봤답니다. 마우스 클릭 위치 근처에 있는 복셀(voxel)들을 전부다 고칠일이 있어서... 그냥 마우스 클릭 깊이만 찾아다 그로부터 월드위치 구한 뒤, octree를 뒤져서 근처에 있는 복셀들을 찾아냈죠.

기타 등등의 응용법이 있을 겁니다.



오랜만에 글써본 포프였습니다.



댓글 없음:

댓글 쓰기