본 논문은 3D 컴퓨터 게임 개발에 있어서 필수적인 3D 지형 툴 개발을 위한 효율적인 알고리즘을 제안한다. 특히 본 논문은 Picking 속도를 향상시키기 위한 교차검출 기법에 대하여 제안한다. 즉, 본 논문에서는 기존의 광선과 삼각형으로 구성된 교차검출 기법보다 광선과 평행사변형으로 구성된 효율적인 교차검출 기법을 제안함으로서 보다 빠른 Picking 속도를 확인할 수 있었다. 본 논문에서 제안하는 기법이 기존의 기법과 비교하여 더 빠른 Picking 속도를 내고 있다는 것을 확인하기 위해서는 DirectX SDK의 샘플들 중 Picking 예제를 실험에 사용하였다. 또한 기존의 기법과 본 논문에서 제안하는 기법으로 교차검출을 위한 함수 호출 횟수를 비교해본 결과 본 논문에서 제안하는 기법이 기존의 기법보다 약 50% 줄어든 것을 확인할 수 있었다. 그리고 이를 시간적으로 계산해 보았을 때에는 기존의 기법보다 1~2초 정도 단축되었음을 확인할 수 있었다. 추가적으로 본 논문에서는 3D 지형 툴로서 갖추어야할 기능들 중 텍스처 스플래팅, 지형의 높낮이 조절, 객체 배치 및 사실적인 물 효과 등의 기능들을 보다 개선된 알고리즘으로 제공함으로서 실제 3D 컴퓨터 게임 개발에 효율적으로 사용가능하도록 하였다.
본 논문은 3D 컴퓨터 게임 개발에 있어서 필수적인 3D 지형 툴 개발을 위한 효율적인 알고리즘을 제안한다. 특히 본 논문은 Picking 속도를 향상시키기 위한 교차검출 기법에 대하여 제안한다. 즉, 본 논문에서는 기존의 광선과 삼각형으로 구성된 교차검출 기법보다 광선과 평행사변형으로 구성된 효율적인 교차검출 기법을 제안함으로서 보다 빠른 Picking 속도를 확인할 수 있었다. 본 논문에서 제안하는 기법이 기존의 기법과 비교하여 더 빠른 Picking 속도를 내고 있다는 것을 확인하기 위해서는 DirectX SDK의 샘플들 중 Picking 예제를 실험에 사용하였다. 또한 기존의 기법과 본 논문에서 제안하는 기법으로 교차검출을 위한 함수 호출 횟수를 비교해본 결과 본 논문에서 제안하는 기법이 기존의 기법보다 약 50% 줄어든 것을 확인할 수 있었다. 그리고 이를 시간적으로 계산해 보았을 때에는 기존의 기법보다 1~2초 정도 단축되었음을 확인할 수 있었다. 추가적으로 본 논문에서는 3D 지형 툴로서 갖추어야할 기능들 중 텍스처 스플래팅, 지형의 높낮이 조절, 객체 배치 및 사실적인 물 효과 등의 기능들을 보다 개선된 알고리즘으로 제공함으로서 실제 3D 컴퓨터 게임 개발에 효율적으로 사용가능하도록 하였다.
This paper proposes an efficient algorithm to develop a 3D terrain tools which is essential in the development of 3D computer games. In particular, this paper proposes a cross detection technique to improve picking speed. In other words, this paper proposes a more efficient cross detection technique...
This paper proposes an efficient algorithm to develop a 3D terrain tools which is essential in the development of 3D computer games. In particular, this paper proposes a cross detection technique to improve picking speed. In other words, this paper proposes a more efficient cross detection technique consisting of a ray and a parallelogram than a cross detection technique consisting of a ray and a triangle. So, we can confirm the faster picking speed. This paper uses a picking example among DirectX SDK samples to test it. In addition, this paper compares the number of function calls for cross detection using the existing techniques and the proposed technique. As a result, in this paper the proposed technique has fallen off to about a 50 percent than the existing techniques. And if it is calculated by times, in this paper the proposed technique was reduced to 1 to 2 seconds than the existing techniques. Additionally, in this paper 3D terrain tools are provide more improved algorithms for features such as texture splatting, height map control, object arrangement and realistic water effect. So, 3D terrain tools is available efficient in the development of real 3d computer games.
This paper proposes an efficient algorithm to develop a 3D terrain tools which is essential in the development of 3D computer games. In particular, this paper proposes a cross detection technique to improve picking speed. In other words, this paper proposes a more efficient cross detection technique consisting of a ray and a parallelogram than a cross detection technique consisting of a ray and a triangle. So, we can confirm the faster picking speed. This paper uses a picking example among DirectX SDK samples to test it. In addition, this paper compares the number of function calls for cross detection using the existing techniques and the proposed technique. As a result, in this paper the proposed technique has fallen off to about a 50 percent than the existing techniques. And if it is calculated by times, in this paper the proposed technique was reduced to 1 to 2 seconds than the existing techniques. Additionally, in this paper 3D terrain tools are provide more improved algorithms for features such as texture splatting, height map control, object arrangement and realistic water effect. So, 3D terrain tools is available efficient in the development of real 3d computer games.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서 제안하는 3D 지형 툴을 위한 시스템 개발 환경은 Microsoft Visual Studio 2008 SP1 MFC를 기본 프레임워크로 하고 Microsoft DirectX 9.0과 Vertex Shader 2.0 및 Pixel Shader 2.0을 지원하는 그래픽스 카드를 사용하는데, 이는 렌더링 시에 하드웨어의 가속과 Shader 기능을 원활하게 사용하기 위해서이다.
본 논문에서는 지형의 높낮이를 조절할 때 조절하고자하는 지형의 영역을 나타내는 Brush에 실시간으로 영역의 높이 값이 반영됨으로서 [그림 8]과 같이 원형의 Brush가 굴곡진 지형에 드리워져 있는 것과 같은 효과가 나타나도록 한다.
제안 방법
Texture Splatting은 서로 다른 Texture들을 알파 맵을 이용하여 조합하는 기법이다. 그러나 본 논문에서 제안하는 3D 지형 툴에서는 기존의 방법처럼 Alpha Texture에 알파 값을 저장하는 대신 Vertex Color에 알파 값을 저장하고 Shader에서 그 값을 받아 Texture를 혼합하는 방식을 사용하는데 다음 수식 2[10]를 이용한다.
그러나 Ray-Triangle로 구성된 폴리곤간의 교차검출 2회를 광선과 평행사변형(이하‘Ray-Parallelogram’)으로 구성된 폴리곤과의 교차검출을 통해 1회로 속도를 줄인다면 컴퓨터 게임 전체의 속도는 한층 향상될 것이다. 그러므로 본 논문에서는 기존의 Ray-Triangle로 구성된 폴리곤과의 교차검출을 Ray-Parallelogram으로 구성된 폴리곤과의 교차검출로 변경하여 처리 속도와 효율성을 높임으로서 1024*1024 해상도에서 2,097,152개의 폴리곤을 가진 대단위 지형에서도 다른 작업에 거의 영향을 주지 않을 정도의 빠른 속도를 가진 Picking 기법을 제안하고, 이를 기반으로 하는 3D 게임 지형 툴을 제작하도록 한다. 본 논문의 구성과 각 장의 내용은 다음과 같다.
또한 광선의 반대 방향과도 교차를 인정하기 때문에 카메라의 뒤에 있는 엉뚱한 곳이 클릭되는 문제가 있다. 그러므로 본 논문에서는 시계 방향의 삼각형만을 인식하고 광선의 진행 방향에 있는 삼각형만 인식하게 함으로써 문제점들을 해결하였으며, 그로 인하여 정확도와 속도를 동시에 향상시키고 Picking을 완성하도록 한다.
그러므로 자식 노드의 함수 호출이 종료되면 4개 자식노드의 함수 호출이 종료될 때 넘어온 Return 값과 카메라와의 거리 값을 가지고 비교하여 광선과 교차한다. 그리고 카메라와의 거리가 가장 가까운 노드 하나를 추출하여 다시 자신의 부모 노드로 넘겨주고 위에서는 동일하게 이 작업을 반복하며 거슬러 올라간다.
여기서 y축 값을 0으로 설정하는 이유는 아무리 굴곡진 지형이라도 y축에서 내려다 볼 경우, y축의 값은 전혀 고려하지 않는 상태의 x - z축 평면만을 볼 수있기 때문이다. 그러므로 지형을 y축에서 내려다 본 상태로 cCamera를 cRay의 방향으로 조금씩 전진시키며 인접한 폴리곤과 비교를 하게 된다.
본 논문에서는 대단위 지형에서 기존의 Ray-Triangle 교차검출 방법을 그대로 사용하지 않고 Ray-Parallelogram 의 교차검출 방법을 도입함으로써 속도와 효율을 높여서 다른 작업에 전혀 지장을 주지 않는 빠른 Picking을 구현하였다. 또한 이를 기반으로 3D 컴퓨터 게임에서 사용할 수 있는 야외 지형을 디자인할 수 있는 3D 지형 툴을 개발하였다. 본 논문에서 제안하는 방법과 기존의 방법에 의한 Picking 속도를 비교해본 결과 본 논문에서 제안하는 방법이 1∼2 fps 정도 더 빠른 것으로 실험 결과 확인되었다.
물 효과(Water Effect)는 실제적인 물 효과를 주기 위한 기능으로서 본 논문에서는 Bump mapping을 사용하여 물속 장면을 왜곡하고 물속 깊이에 따라 색상이 어두워지게 하여 실제와 근접하게 물속 시야를 시뮬레이션 한다. 그리고 실제 수면에 주변 경관이 반사되는 것처럼 실시간으로 수면 위 장면을 매 프레임마다 Render Target Texture(DirectX에서 렌더링 디바이스가 렌더링을 수행할 Surface에 적용하는 Texture)에 저장한 다음 그것을 다시 수면에 반사시켜서 실제로 반사되는 것 같은 효과를 [그림 9]와 같이 표현한다.
본 논문에서 제안하는 3D 지형 툴을 위한 전체적인 시스템의 구성은 [그림 1]과 같이 크게 4가지로 구분되는데, 첫째, 서로 다른 Texture를 조합하여 지형에 Mapping하는 Texture Splatting, 둘째, 지형의 높낮이를 사용자가 임의로 변경하여 원하는 모양의 지형을 생성하는 Height Map Control, 셋째, 실제 호수와 같은 효과를 제공하는 사실적인 물 효과(Water Effect), 그리고 마지막 넷째, 나무나 건물 및 캐릭터 등과 같은 다양한 객체를 지형에 배치하는 객체 배치(Object Arrangement)이다.
본 논문에서는 대단위 지형에서 기존의 Ray-Triangle 교차검출 방법을 그대로 사용하지 않고 Ray-Parallelogram 의 교차검출 방법을 도입함으로써 속도와 효율을 높여서 다른 작업에 전혀 지장을 주지 않는 빠른 Picking을 구현하였다. 또한 이를 기반으로 3D 컴퓨터 게임에서 사용할 수 있는 야외 지형을 디자인할 수 있는 3D 지형 툴을 개발하였다.
컴퓨터 게임에서 사용하고 있는 지금까지의 Picking은 광선 및 삼각형(이하 ‘Ray-Triangle’)으로 구성된 폴리곤과의 교차검출을 통해 그 결과를 도출하였었다.
대상 데이터
수식 2는 Texture를 혼합할 때 결과 색상이 최대값을 넘지 않게 하기 위한 것으로서 어떤 색을 어떻게 혼합하더라도 절대 색상의 최대값을 넘지 않게 되어 하얗게 되는 현상을 막을 수 있다. 사용자는 한꺼번에 총 5장의 Texture를 혼합할 수 있고 혼합할 Texture들은 실시간으로 바꿀 수 있으며 그 즉시 반영되어 진다. Texture Splatting은 원형의 Brush로 적용하게 되는데, 원의 중심과 가까운 부분은 최대의 알파 값을 가지며, 원의 가장자리로 갈수록 알파 값은 0이 되도록 하고 있다.
이론/모형
3D 지형 툴은 대단위 크기의 지형 데이터를 생성하는 기능을 주로 하고 있기 때문에 지형을 관리하기 위한 기법이 필요하다. 3D 컴퓨터 게임에서 일반적으로 사용하는 지형 관리 기법은 Octree, Quadtree, BSP(Binary Space Partitioning) 등이 있는데, 본 논문에서 제작한 3D 지형 툴은 일반적인 야외 지형 제작을 목적으로 하고 있기 때문에 이제 가장 적합한 Quadtree 기법을 사용하여 지형을 관리한다.
성능/효과
셋째, 광선과 교차하는 최소 단위 노드에 한해서 정확한 Picking 지점을 가려내고 그 것을 자기 자신의 주소와 함께 부모 노드로 올려 보낸다. 넷째, 부모 노드에서는 만약 자식 노드 중에 광선과 교차하는 노드가 2개 이상일 때 자식 노드에서 받은 카메라와의 거리를 사용 하여 카메라와의 거리가 가장 짧은 노드를 가려낸다. 그럴 경우 실제로 광선과 교차하는 단 하나의 노드만이 최종적으로 남게 된다.
본 논문에서 제안하는 방법과 기존의 방법에 의한 Picking 속도를 비교해본 결과 본 논문에서 제안하는 방법이 1∼2 fps 정도 더 빠른 것으로 실험 결과 확인되었다.
후속연구
특히 본 논문에서 제안한 Ray-Parallelogram 교차검출 방법은 Picking 뿐만 아니라 3D 컴퓨터 게임에서의 충돌 체크 등과 같은 다양한 분야에서 충분히 활용이 가능하며, 경우에 따라서는 기존의 Ray-Triangle 교차검출 방법을 교체할 수도 있을 것이다. 그리고 3D 지형 툴의 대표적인 4가지 기능들 즉, Texture Splatting, 높이 맵 조절, 객체 배치, 사실적인 물 효과는 기존보다 향상된 알고리즘을 적용하였기 때문에 실제 3D 컴퓨터 게임 개발에 충분히 사용할 수 있을 것이다.
그러므로 무엇보다 속도에 매우 민감한 컴퓨터 게임 분야에서 1∼2 fps 정도의 속도차이는 매우 큰 의미가 있다고 판단된다. 특히 본 논문에서 제안한 Ray-Parallelogram 교차검출 방법은 Picking 뿐만 아니라 3D 컴퓨터 게임에서의 충돌 체크 등과 같은 다양한 분야에서 충분히 활용이 가능하며, 경우에 따라서는 기존의 Ray-Triangle 교차검출 방법을 교체할 수도 있을 것이다. 그리고 3D 지형 툴의 대표적인 4가지 기능들 즉, Texture Splatting, 높이 맵 조절, 객체 배치, 사실적인 물 효과는 기존보다 향상된 알고리즘을 적용하였기 때문에 실제 3D 컴퓨터 게임 개발에 충분히 사용할 수 있을 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
컴퓨터 게임에서 사용하는 지금까지의 Picking은 어떤 방법을 이용해왔는가?
특히 대단위 지형을 배경으로 하고 있는 컴퓨터 게임에서 Picking의 속도와 정확성은 매우 중요한 부분이다. 컴퓨터 게임에서 사용하고 있는 지금까지의 Picking은 광선 및 삼각형(이하 ‘Ray-Triangle’)으로 구성된 폴리곤과의 교차검출을 통해 그 결과를 도출하였었다. 그러나 Ray-Triangle로 구성된 폴리곤간의 교차검출 2회를 광선과 평행사변형(이하‘Ray-Parallelogram’)으로 구성된 폴리곤과의 교차검출을 통해 1회로 속도를 줄인다면 컴퓨터 게임 전체의 속도는 한층 향상될 것이다.
Picking의 속도와 정확성이 특히 중요한 컴퓨터 게임은 무엇인가?
최근 스마트 폰 출시와 함께 더욱 각광받고 있는 분야들 중 하나는 터치스크린을 사용한 사용자 인터페이스인데, 컴퓨터 게임에서는 일반 모니터에서 마우스를 사용한 Picking을 주로 사용하고 있으며 이 또한 컴퓨터 게임의 편리성뿐만 아니라 속도를 조금이나마 향상시키기 위한 사용자 인터페이스 중의 하나로 볼 수 있다. 특히 대단위 지형을 배경으로 하고 있는 컴퓨터 게임에서 Picking의 속도와 정확성은 매우 중요한 부분이다. 컴퓨터 게임에서 사용하고 있는 지금까지의 Picking은 광선 및 삼각형(이하 ‘Ray-Triangle’)으로 구성된 폴리곤과의 교차검출을 통해 그 결과를 도출하였었다.
본 논문에서 제안한 교차검출을 이용한 Picking을 설계하기 위한 전체 프로세스는 어떠한가?
본 논문에서 제안하는 교차검출을 이용한 Picking을 설계하기 위한 전체 프로세스를 순서대로 나열하면 다음과 같다. 첫째, 사용자가 마우스로 클릭한 위치의 스크린 좌표를 3D 공간의 세계 좌표로 변환하여 카메라의 위치 벡터와 카메라가 바라보는 방향 벡터[2]를 얻는다. 둘째, 재귀 호출로 Quadtree의 각 노드를 최상위 노드부터 훑어 내려가면서 첫째 과정에서 추출한 Picking 광선과 교차하지 않는 노드들을 제외시킨다. 셋째, 광선과 교차하는 최소 단위 노드에 한해서 정확한 Picking 지점을 가려내고 그 것을 자기 자신의 주소와 함께 부모 노드로 올려 보낸다. 넷째, 부모 노드에서는 만약 자식 노드 중에 광선과 교차하는 노드가 2개 이상일 때 자식 노드에서 받은 카메라와의 거리를 사용 하여 카메라와의 거리가 가장 짧은 노드를 가려낸다. 그럴 경우 실제로 광선과 교차하는 단 하나의 노드만이 최종적으로 남게 된다.
참고문헌 (10)
최종현, 이상욱, 김용준, 좋은 게임을 만드는 핵심 원리, 한빛미디어, 2003.
Frank D. Luna, DirectX9를 이용한 3D GAME 프로그래밍 입문, 정보문화사, 2004.
Wolfgang Engel, ShaderX2 DirectX9 셰이더 프로그래밍, 정보문화사, 2004.
김혜선, 이동춘, 박찬용, 장병태, "대규모 지형의 3D 게임맵 구성을 위한 저작 시스템 개발", 한국정보과학회 2002년도 가을학술발표논문집, 제29 권, 제2호, pp.451-453, 2002.
성명건, 이석희, 황성진, 박경환, "3D 온라인 게임을 위한 지형생성기", 한국멀티미디어학회 2002년도 추계학술발표논문집, pp.520-525, 2002.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.