Object Picking.. 어떻게 하고 계신가요?

2D, 3D, 다각형, 픽셀 등 게임의 그래픽 프로그래밍에 관한 포럼입니다.

Moderator: 류광

Locked
zupet
Posts: 2764
Joined: 2003-05-13 03:34
Location: NCSOFT LE팀

Object Picking.. 어떻게 하고 계신가요?

Post by zupet »

안녕하세요. 매크로 없는 메비~랍니다.

흠~~ 작업중에 궁금해 졌는데 여러분은 Object Picking 을 어떻게 하고 계신가요?

일단 문제는 마우스입니다. Camera 기준으로 Ray 를 만들어서 화면에서 Picking 작업을 하는데 이 Picking 작업이란게 화면에 나타나는 모든 Object 들과의 Ray Test 를 필요로 하게 됩니다. 다양한 알고리즘이 있을텐데 여러분들은 이 Ray-Object Picking 을 어떻게 하고 계신지 궁금하네요. 일단 Object는 AABB나 Sphere 등으로 표현된다 치더라도 화면에 많은 Object 들이 나온다면 이 녀석들에 대한 Picking 처리는 전부 해줘야 할 것 같은데.. 횟수가 적으면 상관 없는데 현재는 매 프레임마다 꼭 한번식은 작업을 해줘야 하게 되었습니다.

마우스가 움직이거나 마우스 밑에 다른 오브젝트가 들어왔을때 그에 따른 커서모양등을 변경 해줘야 하니까요. 몇몇 방법으로 쿼드 트리나 옥트리등으로 화면을 구성해서 쓰는 방법이 있습니다만 그럼 그에 따른 Object 들의 정렬을 매 프레임마다 해줘야 하고(Picking 보단 쌀 것 같지만) 그래도 Ray 와 AABB 와의 테스팅을 추가로 해줘야 하는 것이 좀 부담스럽군요. Ray Tracing 관련 자료들을 보면 똑똑한 Ray Tracing 과 효율적인 공간 분할에 대한 자료들이 조금 있던데 이런 것을 이용해 보신 분들은 혹시 안계신가요?
비회원

Post by 비회원 »

저는 분할된 공간을 ray피킹 검사를 하고, 피킹 성공시, 노드가 리프라면, 리프내에 있는 오브젝트들을 피킹검사하는 식으로 했습니다.
비회원

O_GL처럼..

Post by 비회원 »

일종의 저해상도 버퍼를 만들어 놓고(256,256 정도)
그곳에 피킹을 원하는 노드를 모두 렌더링 해봅니다.
그리고 마우스의 좌표랑 2차원 비교후
해당 픽셀값으로 오브젝트 피킹 여부를 확인해줍니다.
GameBryo에는 이런방식의 피킹처리가 들어가있는듯하더군요
chadr
Posts: 980
Joined: 2003-06-01 12:28
Location: 모대학
Contact:

Post by chadr »

저는 자주 이동을 하는 물체는 gpg에 나와있는 Sphere tree를 이용해서 ray test를 하도록 하였습니다.. 성능은?? 객관적인 자료는 없지만 그럭저럭 괜찮더군요..
myevan
Posts: 1314
Joined: 2003-03-04 10:21
Contact:

Post by myevan »

역시 sphere tree 를 쓰시는 분이 계시는군요 -_-)~
저도 꽤나 효용을 봤었는데.. 어쨌든 루프(...후후...)쓰시는것보다야는 훨씬 나은 선택이죠 ~(-_-)~
일단 넣어두면 피킹을 비롯해서 컬링/충돌/높이 등등 여러군데 쓸곳이 많습니다.

다만; 모든 오브젝트를 하나에 등록했던지라;;
높이 테스트를 할때 불필요한 연산이 추가 부담되었던 고통을 현재 겪고 있는 중입니다. Orz;;

주의점이라면 windowsx.h 헤더랑 충돌 (매크로가 함수명보다 우선순위인데 GetNextSibling, GetPrevSibling
이란 매크로가 이미 있더군요 -_- 이걸 몰라서 왜 에러나는지 한참을 고생했었습니다. 이후로 StdAfx.h 에
windowsx.h는 안 넣고 있는중입니다. )

그밖에 높이를 구할때라던지 2차원 충돌 테스트를 위해서
높이축(저의 경우는 맥스좌표계를 써서 z축입니다만...)라인 피킹은 꽤 부담이 있기때문에
2차원 비교 테스트만 추가해주시면 ~(-_-)~ 꽤나 쓸만합니다.
빗자루네 http://www.myevan.net >_<b
pacman
Posts: 188
Joined: 2004-04-13 12:48

구트리(sphere tree) 알고리즘?

Post by pacman »

염치없는 부탁입니다만, 사용하시는 구트리 소스나 알고리즘을 구할 수 없을까요?
GPG 2권의 소스를 분석해 보니 코드가 지저분하고 쓸데없이 복잡한 작업을 해서,
매 프레임마다 노드가 가만히 있는 데도 같은 부모로 부터 떨어졌다가 다시 들어오는 불필요한 과정을 반복하는 경우가 많더군요.
그런 현상이 너무 비효율적으로 보여서 직접 구현하려고 했는데
"명확한 알고리즘"이 떠오르지 않아 그냥 포기해 버렸습니다. ("octree나 aabb tree를 쓰자"라고... -.-;)
배우고 때맞춰 익히니 기쁘지 아니한가!
chadr
Posts: 980
Joined: 2003-06-01 12:28
Location: 모대학
Contact:

Post by chadr »

myevan wrote:주의점이라면 windowsx.h 헤더랑 충돌 (매크로가 함수명보다 우선순위인데 GetNextSibling, GetPrevSibling
이란 매크로가 이미 있더군요 -_- 이걸 몰라서 왜 에러나는지 한참을 고생했었습니다. 이후로 StdAfx.h 에
windowsx.h는 안 넣고 있는중입니다. )
저도 처음에 그런 오류가 나서 알아보니 windowssx.h에 매크로가 들어있더군요-_-);

그래서 헤더와 소스의 맨처음에 잠시 매크로를 undefine했다가 끝나는 부분에 다시 define을 해주도록 했습니다..
lsg0222 wrote:염치없는 부탁입니다만, 사용하시는 구트리 소스나 알고리즘을 구할 수 없을까요?
GPG 2권의 소스를 분석해 보니 코드가 지저분하고 쓸데없이 복잡한 작업을 해서,
매 프레임마다 노드가 가만히 있는 데도 같은 부모로 부터 떨어졌다가 다시 들어오는 불필요한 과정을 반복하는 경우가 많더군요.
그런 현상이 너무 비효율적으로 보여서 직접 구현하려고 했는데
"명확한 알고리즘"이 떠오르지 않아 그냥 포기해 버렸습니다. ("octree나 aabb tree를 쓰자"라고... -.-;)
저도 gpg에 있는 소스를 보니 너무 복잡해서 새로 구현할려고 이곳저곳에서 자료를 찾아봤지만...
제 실력으로는 도저히 알아먹을만한 자료가 거의 없더군요..(한글 자료는 당연히 없구요..)
그래서 대~충 gpg소스를 뜯어 고쳐서 만들긴 했습니다만 성에 차지 않는군요:(

예전에 제가 이곳 게시판에 관련 글을 올렸을때 류광님께서 자료를 하나 추천해 주신게 있는데 참고해보세요..
제 아이디로 검색해보시면 나올겁니다.
궁금이
Posts: 237
Joined: 2005-01-19 11:06
Location: ProjectS

Re: 구트리(sphere tree) 알고리즘?

Post by 궁금이 »

lsg0222 wrote:염치없는 부탁입니다만, 사용하시는 구트리 소스나 알고리즘을 구할 수 없을까요?
GPG 2권의 소스를 분석해 보니 코드가 지저분하고 쓸데없이 복잡한 작업을 해서,
매 프레임마다 노드가 가만히 있는 데도 같은 부모로 부터 떨어졌다가 다시 들어오는 불필요한 과정을 반복하는 경우가 많더군요.
그런 현상이 너무 비효율적으로 보여서 직접 구현하려고 했는데
"명확한 알고리즘"이 떠오르지 않아 그냥 포기해 버렸습니다. ("octree나 aabb tree를 쓰자"라고... -.-;)
octree 쓰고 있습니다 ㅡㅡ;
pacman
Posts: 188
Joined: 2004-04-13 12:48

동적 개체 관리를 위한 구 옥트리

Post by pacman »

이 스레드가 열린 지 어언 1년이 지났군요. -_-;
아이디를 lsg0222에서 pacman으로 바꿨습니다.

GPG2권의 4.3 빠른 가시성 제외, 레이 트레이싱, 범위 검색을 위한 구 트리
를 읽고 더 나은 방법이 없을 까 고민해서 나름대로 변형한 알고리즘입니다. (거의 1년이 지나서 어느날 퍼뜩 아이디어가 떠오르더군요.)
GPG2권의 구트리보단 낫다고 생각합니다.

dexgame.com에 소스와 데모를 첨부했으니 관심있으신 분들은 확인해 보시기 바랍니다.
http://www.dexgame.com/bbs/view.php?id= ... asc&no=122
아래는 알고리즘에 대한 설명글입니다. 편의상 존댓말은 생략하였으니 양해 바랍니다.
------------------------------------------------------------------------------------------

< 동적 개체 관리를 위한 옥트리의 필요성 >

게임 브리오나 오우거, 일리힛 같은 많은 게임 엔진들이 장면 관리를 위해 장면 그래프 자료 구조를 사용한다.
일반적인 장면 그래프에서 부모 개체의 경계 볼륨은 자식 개체들을 모두 감싼다.
이러한 특성은 가시성 검사에 유용하게 사용된다.
하지만 장면 그래프의 계통적 경계 볼륨 방식은 몇가지 단점이 존재하는데
자식 개체가 이동하거나 경계 볼륨 크기가 바뀔 때마다 부모의 경계 볼륨까지 재계산해야 한다는 것이다.
그리고 게임 내에서 대부분의 개체들이 부모가 없거나 루트 노드를 부모로 하는 경우에는
장면 그래프의 장점이 없어져 가시성 검사에 별다른 기여를 하지 않게 된다.

이는 동적인 개체가 많은 게임 환경에서 적지 않은 부하를 가져다 준다.

이러한 부하를 막기 위해서 모든 개체는 자기 자신만을 감싸는 경계 볼륨을 가져야 한다. (일반적으로 경계 구 계산은 초기화시 한번만 하면 된다.)
이제 계통적으로 가시성 검사를 할 수 없게 되었으므로, 모든 개체에 대해 시야 각뿔대 포함 여부를 검사해야 한다.
요즘 컴퓨터는 욜라 빨라서 그렇게 해도 아무 지장없다면 할 말이 없다. -_-;
그러나 이보다 더 나은 방법이 분명 존재할 것이다.

맵 데이타 같은 폴리곤 덩어리를 분할 저장하는 옥트리를 동적 개체 관리를 위해 특화시켜 사용하는 것은 어떨까?
옥트리로 전체 게임 세계를 획일적으로 분할하고 개체(또는 장면 노드)들을 옥트리에 포함시키는 것이다.

움직이지 않는 개체(장면 노드)들은 옥트리 노드 안에 그대로 머물러 있으면 될 것이고,
움직이는 개체들은 현재 속한 옥트리 노드를 벗어나는 지를 검사해서 벗어났다면 알맞은 옥트리 노드를 다시 찾아가면 될 것이다.
여기서 개체(장면 노드)와 옥트리 노드를 혼동해선 안된다.
개체는 장면 그래프 내의 노드이고, 옥트리 노드는 공간 분할 옥트리 내의 노드이다.

옥트리 노드의 경계 볼륨으로 축정렬 경계 상자보다는 연산 비용이 가장 싼 경계 구를 추천한다.
개체 또한 경계 구를 추천한다.
개체가 어떤 방향으로 회전하던지, 어떤 자세를 취한다던지 경계 구를 벗어나지 않으므로
동적인 개체에 적합하다.
이름하여 '경계 구 옥트리' 되겠다. 아래 그림은 구 옥트리를 2D로 표현한 것이다.
파란색 구가 옥트리 노드를 나타내고, 빨간색 구가 개체를 나타낸다.
Image
GPG 2권에 나왔던 허접한 구트리가 아니다.
2권의 구트리는 움직이지 않는 노드 조차 부모 노드를 들락 날락 거리고,
노드가 새로 생겼다가 금방 사라지는 등 비효율적이고 납득이 가지 않는 방식으로 작동한다.
또한 장면 그래프 처럼 계통적인 방식이어서 자식 노드가 움직이거나 다른 노드로 옮겨가면
새로운 부모 노드와 이전의 부모 노드 양쪽에서 경계 볼륨을 재계산해야 한다.
다수의 노드가 이동하면서 부모 노드를 바꾸고 생성과 소멸을 자주 반복하는 것은
경계 볼륨의 재계산을 빈번하게 만들어 그야말로 배보다 배꼽이 더 큰 상황을 연출한다.

반면에 내가 생각한 구 옥트리는 근본은 옥트리이기 때문에 노드 자체는 한번 생성되면
포함하는 개체가 모두 없어지기 전에는 소멸하지 않는다.
(노드가 포함하는 개체가 없더라도 차후에 개체가 다시 포함될 가능성이 있으므로 생성된 채로 놔둘 수도 있다.)
또한 2권의 구트리처럼 옥트리 노드 자체가 움직이거나 크기가 변하는 등의 일이 발생하지 않으므로,
노드의 재계산이 전혀 필요 없다는 장점이 있다.
즉, 노드는 고정되어 있고, 움직이는 개체에 대해서만 신경을 써주면 되는 것이기 때문에 부하가 더 적다.
특히 노드를 벗어나지 않고 안에서만 움직이는 개체에 대해서는 구에 대한 교차 검사를 한번만 하면 된다.

그러나 옥트리라는 알고리즘 자체가 게임 세계를 완벽하게 효율적으로 공간 분할하지 않을 뿐만 아니라
경계 상자가 아닌 경계 구를 사용하기 때문에 정확한 가시성 검사는 기대하기 어렵고, 효율이 떨어진다고 생각할 수도 있다.
그래도 장면 내의 모든 개체 각각에 대해 가시성 검사를 하는 것보단 낫다!
본래 내가 고안한 구 옥트리의 목적은 정확한 가시성 검사보다는 빠르게 추려내는 것이기 때문에
수백, 수천의 개체가 움직이는 게임에서 비로소 그 효과가 나타날 것이다.
일단 구 옥트리를 이용하여 개체들을 빠르게 컬링하고, 추려낸 개체들에 대해서만 경계 상자 등을 이용하여 더욱 정확한 가시성 검사를 하면 될 것이다.

장면 관리는 장면 그래프를 그대로 사용하고, 충돌 검사나 가시성 검사에는 구 옥트리를 사용하면 좋지 않을까 생각한다.
가시성 검사는 장면 그래프와 같은 방식으로 아래와 같이 하면 될 것이다.
1. 노드가 시야 각뿔대 안에 들어있지 않으면 자식 노드들에 대해 검사할 필요가 없다.
2. 노드가 시야 각뿔대 안에 완전히 포함되면 자식 노드들에 대해 검사할 필요가 없다. 해당 노드와 자식 노드에 속한 모든 개체들을 가시 리스트에 추가한다.
3. 노드가 교차하는 경우에는 각각의 자식 노드들에 대해 가시성 검사를 한다.

충돌 검사에 응용하는 경우,
개체 끼리의 충돌 검사는 인접한 노드에 속한 개체들에 대해서만 검사를 하면 될 것이다. (직접 구현해 본 적은 없다.)
물리 엔진을 사용하는 경우에는 자체적으로 충돌 검사 기능을 제공하기 때문에 구 옥트리를 따로 사용할 필요는 없을 것이다.

< 일반적인 옥트리와의 차이점 >

일반적인 옥트리는 리프 노드에 폴리곤 정보가 들어가지만,
구트리는 리프 노드 라는 개념이 따로 없이
일반 노드에 폴리곤 정보 대신 개체 정보를 담고 있다.

느슨한 옥트리는 구 옥트리에 적합하지 않다.
경계에 걸리는 개체는 개체를 '완전히 포함하는 가장 가까운 노드'에 포함시키면 그만이다.

< 의사 코드 >

다음은 구 옥트리 구축에 관한 의사 코드이다.
루트 노드에 개체를 추가하면 Top-Down 방식으로 구축된다.
여기서 개체는 경계 구를 가진 장면 노드이다.

Code: Select all

구
{
   중점
   반지름
};

구 옥트리 노드
{
   개체 리스트
   부모 노드
   자식 노드 배열
};

구 옥트리
{
   루트 노드
};

노드에 개체를 전달
{
   말단 노드인 경우 개체를 현재 노드에 바로 추가, 리턴
   
   개체가 노드보다 더 크면 상위 노드로 개체를 전달, 리턴

   자식 노드들에 대해 개체 포함 검사
   
   개체를 '완전히 포함하는' 자식 노드의 수를 검사
      0 이면, 현재 노드에 개체를 추가
      1 이면, 해당 자식 노드에 개체를 전달 (자식 노드가 생성되어 있지 않으면 생성 후 전달)
      2~8이면, 거리가 가장 가까운 자식 노드에 개체를 전달 (자식 노드가 생성되어있지 않으면 생성 후 전달)
}

노드에 대해 가시 개체들을 컬링
{
   노드에 대해 시야 각뿔대 컬링
   
   컬링 결과 검사
      완전히 포함이면, 모든 자식 노드의 개체들을 수집
      교차면, 현재 노드에 속한 개체들에 대해 컬링하고, 자식 노드들에 대해 컬링
      나머지 경우, 그냥 리턴
}

구 옥트리 생성
{
   장면 전체를 감싸는 루트 노드 생성
   최소 경계 반지름을 설정 (말단 노드를 판단하는 기준이 됨)
}

구 옥트리에 개체를 추가
{
   루트 노드에 개체를 전달
}

구 옥트리 구축
{
   게임에 추가할 모든 개체에 대하여, 루트 노드에 하나씩 전달 (개체의 위치와 크기가 정해져 있어야 함)
}

구 옥트리 갱신 (개체의 이동 또는 크기 변화 처리)
{
   개체가 속해 있는 노드의 경계에 대해 개체 포함 유무를 검사
      
      개체를 완전히 포함하는 경우,
         개체의 크기가 자식 노드보다 작다면 개체를 리스트에서 제거하고 현재 노드에 다시 전달
   
      개체를 완전히 포함하지 않는 경우, 개체를 노드에서 제거하고 상위 노드에 대해 포함 유무를 검사
         상위 노드가 개체를 완전히 포함하면 상위 노드에 전달 
         상위 경계가 개체를 완전히 포함하지 않으면 루트 노드에 전달
}

구 옥트리에 대해 가시 개체들을 컬링
{
   루트 노드에 대해 가시 개체들을 컬링
}
배우고 때맞춰 익히니 기쁘지 아니한가!
그레이오거
Posts: 322
Joined: 2006-01-18 13:25

저도 옥트리에 한표

Post by 그레이오거 »

개인적으로는 윗분 말씀처럼 옥트리 구성에 레이 피킹, 걸린 노드안 오브젝트 검사가 가장 편하다고 봅니다. 단지 움직이는 오브젝트들을 어떻게 이쁘게 갱신해주느냐가 문제인데... 저같은 경우는 각각의 리프는 자신의 이웃 리프노드에 대한 정보를 갖게 하고 확률상 높은 노드(전후좌우같은) 를 우선적으로, 대각선쪽 노드는 나중에 검사하게 했습니다. 리프에서 안걸리면 부모로 올라가는 식이지요.

사실 모든 오브젝트들이 매프레임마다 노드 경계를 미친듯이 질주하지 않기 때문에... 제 테스트로는 오브젝트 하나당 평균 2.4회 정도의 노드포함 판별만으로 갱신되더군요. 물론 노드의 크기나 오브젝트의 크기/속도에 따라 조금씩 달라집니다만. 하여간 테스트에서 1000개의 오브젝트 갱신하는데 1ms가 안걸려 그럭저럭 쓸만하다고 생각해 이방식을 사용하고 있습니다.

여담입니다만 게임에 따라 다르겠지만 오브젝트들은 플레이어의 주변을 평면으로 놀고 있는 경우가 대부분인지라 충돌관련은 차라리 옥트리보다는 쿼드트리가 더 비용이 적게 들더군요. 오히려 더 빠르고요...;; 위의 예도 옥트리로는 1ms 아슬아슬하게 넘겼는데 충돌만 쿼드트리로 바꾸고 나니 그것만으로도 제법 빨라지더군요.

뭐 항상 나오는 말과 비슷합니다만 최고의 피킹 방법은 그 게임 특성에 딱 맞는 피킹방법이지 않을까 싶습니다.
xevious7
Posts: 175
Joined: 2006-03-30 17:31
Contact:

pacman님의 옥트리 알고리즘

Post by xevious7 »

잘 보았습니다. 좋은 글입니다. ~
myevan
Posts: 1314
Joined: 2003-03-04 10:21
Contact:

Post by myevan »

spheretree 를 그냥 쓸까 했는데 이후에 좋은 글이 올라왔었내요 : )

이번 기회에 테스트해본 후 결과를 한번 올려보겠습니다.
빗자루네 http://www.myevan.net >_<b
Locked