'Or..........'에 해당되는 글 25건

  1. kd-tree Introduction 2009.08.27
  2. Grass Rendering 2009.08.27
  3. Water Rendering 2009.08.27
  4. Flight Simulator : HUD - LCOSS 2009.08.27
  5. Line - Line Intersect 2009.08.27

kd-tree Introduction

from Or........../Work 2009. 8. 27. 14:57
⊙ Introduction
여기에서 다루는 kd-tree는 공간 DB로, 기존의 문자 DB와는 다르다. key 값 매칭 문제이고, 굉장히 큰 양을 공간 기반으로 검색한다. 공간 기반 검색이란, range로 표현된 질의를 검색한다는 것이다. Spatial data는 points, lines, polygons 등을 포함하고 있따.
Spatial data를 효율적으로 지원하기 위해서는, 다음과 같은 특징적 어려움을 알아야 한다.
① First, spatial data are latge in quantity, complex in structures and relationships
② Second, the retrieval process employs complex spatial operators like intersection, adjacency, and containment
③ Third, it is difficult to define a spatial ordering, so conventional techniques cannot be employed for spatial operations
→ spatial indices 필요!

(1) kd-tree : Binary-tree based indexing
kd-tree는 multi-attribute data index를 binary search하는 tree로, k는 표현될 데이터 공간의 차원을 가리킨다. 각 depth에서, 어떤 branch로 갈 것인가를 결정하는 데에 다른 attribute이 사용된다. 예를 들어, 2-d (x,y) tree에서는 짝수 depth에서 x 좌표가 branch 기준이라면, 홀수 depth에서는 y 좌표가 branch 방향의 기준이 된다. 마지막으로, 이 tree는 꼭 균형을 이룰 필요는 없다.

A가 제일 먼저 들어간 것을 알 수 있다. 즉, 최초의 분리자는 root이다.



① Principle
Node는 각각의 실제 data point를 나타내고, 검색 방향의 지표가 된다. (left, right 두 개의 child가 있다.→ 현재 노드 값 보다 작은가? 큰가?)
한 Node는 5개의 field로 구성되어 있다. LOSON(작은 값을 가진 left 자식), HISON(큰 값을 가진 right 자식), 좌표(x,y,...), NAME(해당 노드에 대한 정보. 포인터가 들어갈 수도 있다.), DISC(좌표 이름을 가리킨다. 즉, 이 노드는 x를 기준으로 했느냐 y를 기준으로 했느냐. 등. ).

② Insertion
Binary search tree에서의 insertion 방법과 유사하다. 다른 점이 있다면, 앞에서 설명 했듯이, depth마다 비교하는 attribute가 다르다는 것이다. tree의 bottom에 도달하면, 거기에 새 node를 넣는다.

매우 쉽다;



③ Search
Search 역시 매우 straightforward하다. 흐흐 BST 처럼 찾아 내려가면 된다. 여기에서 역시, 다른점은 depth마다 비교 기준의 attribute이 다르다는 점 뿐. 참 그리고, 질의가, 조건 질의가 가능하다는 것이 또 하나 틀린데, 예를 들어, 'Y>20인 점들을 찾아라' 라든지, '(75,15)에 가까운 점들을 찾아라' 등이 가능하다는 것이다.
Region Search는 Euclidean distance를 이용하여 구할 수있다. node (a,b) 근처 거리 d안에 있는 점들을 다 구하라는 질의가 들어오면, 우선 (a-d) ≤ x ≤ (a+d), (b-d) ≤ y ≤ (b+d) 안의 점들을 다 구한다. 그런데 이렇게 구한 점은, 반지름 d인 원 안에 있는 점이 아니라, 한 변이 2d인 정사각형 안에 들어오는 점이므로, 점들을 구한 다음에 range안에 들어오는 게 맞는지 확인이 필요하다.

Search 결과 Miami를 찾았다!



④ Deletion
앞에 insert나 search는 BST와 비슷하여 쉬웠지만, deletion은 좀 더 복잡하다. 각 depth마다, DISC가 달라서, 원래 tree의 root는 DISC가 x 지만, subtree의 root는 y가 될 수도 있기 때문에, 모든 subtree가 kd-tree가 아니다. 그래서 그냥 마구 삭제해 버리면 문제가 생긴다.
kd-tree로 부터 (a,b) 노드를 삭제한다고 할 때, (a,b)의 두 subtree가 empty tree이면 그냥 삭제하면 되고, 아니면 (a,b)의 subtree들 중에서 가장 적절한 대체 노드 (c,d)를 찾아서, replace시킨다. 이 (c,d)는 recursive하게 다시 삭제되는 것이다. 그렇다면, 이 대체 노드는 어떻게 찾는 것일까? 오른쪽 subtree에서 가장 작은 값을 가진 노드나, 왼쪽 subtree에서 가장 큰 값을 고르면 된다. 그러면 다음의 예를 보자.

사실 이것도 찬찬히 보면 매우 쉽다. 그죠?



⑤ 장단점
kd-tree는 partial matching search에 유용하지만, empty space가 없고, point search와 region search가 다 가능하다. 하지만, 균형이 심~하게 안맞으면 performance가 안좋다. kd-tree는 메모리 기반 index이다. File 기반에서는... 안좋다.

 

출처 : http://www.snisni.net/98

'Or.......... > Work' 카테고리의 다른 글

Overview of the Major Structural Changes in Direct3D 10  (0) 2009.08.27
Scene Graph Rendering  (0) 2009.08.27
Grass Rendering  (0) 2009.08.27
Water Rendering  (0) 2009.08.27
Flight Simulator : HUD - LCOSS  (0) 2009.08.27
,

Grass Rendering

from Or........../Work 2009. 8. 27. 14:55

으.. 오랫만에 쓰는 작업 스토리... (너무 바뻤음..ㅜ.ㅠ)

 

물 렌더링 관련 작업을 끝내고 풀 렌더링에 대해서 작업을 시작했습니다. 작업 시작해서 끝난지는 언 6~7개월 전 ㅡㅡㅋ 너무 바쁜관계로다가 지금 이렇게 씁니다. 아무튼....기존의 풀 렌더링 관련 툴이 있었는데 (역시 물 작업 툴과 같이..) 디자이너들이 쓰기가 불편하다고 하고 퍼포먼스 및 퀄러티가 안나와서 다시 개발을 하기로 맘을 먹었지용.. (뜯어 고치는 수준이 아니라 아예 첨부터...개발 ㄱㄱㄱ)

그래서 그런지 3번의 큰 소스 뒤업기를 통한 결과가..다들 만족 스러워한다는..

 

풀 렌더링의 목표는 퍼포먼스! 최적화!

일단 풀들은 여러 종류의 풀이 있듯이 Texture가 여러개가 있지용.. 매번 렌더링 타임때 Texture를 로드해서 풀을 렌더링하기엔 빡실듯 하여 Composite Texture를 사용하기로 결정~!

 

 

요렇게 한장의 Texture에 풀 이미지들을 다 모아서 관리하도록 ~!!

 

두번째로는 풀은 같은 모양의 아이로 반복되어 그려지고 있기때문에 Instancing 을 사용하도록 하였지요. 그러나 여기서도 문제가.. Instancing에는 Shader Instancing과 Constant Instancing, 또 하나 더 있는데 까먹었어용.. 아무튼 Shader Instancing과 Constant Instancing 두개 중 하나를 사용을 하기로 했었는데 Shader Instancing은 크기가 각각 틀린 풀들을 따로 처리하기가 빡세서 Constant Instancing을 사용하기로 했지요.. 결과적으로 풀을 많이 뿌려도 왠만한 FPS를 기대 할 수 있다는.. ^-^

 

결과~!

 

보나스 에피소드 : 원래는 안움직이는 풀을 만들려고 했으나.... 누군가의 압박으로 "요새 어떤 게임이 풀이 안움직이냐~ WOW를 봐라 풀이 움직인다~" 라고 해서 자연스럽게 움직이도록 다시 만들었지요... 그러나 열심히 알아본 결과 WOW에서 풀은 안움직인다는...ㅡㅡ;;; (제가 알아봤을땐 안움직이는데~ 움직이나용~? 미스테리라는..)

'Or.......... > Work' 카테고리의 다른 글

Scene Graph Rendering  (0) 2009.08.27
kd-tree Introduction  (0) 2009.08.27
Water Rendering  (0) 2009.08.27
Flight Simulator : HUD - LCOSS  (0) 2009.08.27
Line - Line Intersect  (0) 2009.08.27
,

Water Rendering

from Or........../Work 2009. 8. 27. 14:53

Water Rendering

 

물 관련해서 요번에 만든거다.

Terrain 관련 패치 기반을 가지고 있으면서도 좀 더 Water만의 특성을 살리면서 작업했다. (효율적인 렌더링을 위해서....) 까보고 보면 Terrian 패치와 틀은 비슷하지만 전혀 다른 놈이다.. 일단 Vertex도 LOD를 안하기 때문에 4개만 가지고 있고 (Index도 마찬가지) 그러면 퀄러티를 높여야했다.

 

(1차 작업 : Water Texture에 많은 의존을 두었다. - 고로 Water Texture가 좋을 수록 퀄러티는 좋아진다는 ㅡㅡ;;;)

캡쳐사진이라 그런지 물 출렁거림이 잘 안보인다. Shader로 작업했건만.. ㅡㅡ; 그래서 좀더 물 퀄러티를 높이고자 Bump맵핑을 시도하였다. 좀 더 멋지게 작업하고자.. 물 다운 물을 만들고자 Light도 먹고.. 뭐 Texture에 의존하지 말고 Light로 인해 좀 더 멋진 물을 만들 필요가 있었다.

그래서 열심히 작업한 결과~!

(2차 작업 결과 : 1차보단 만족스럽게 나왔다. 물 같기도 하고..ㅡㅡㅋ)

두번째 작업하면서 늘어난 기술은 Shader 디버깅과 nVidia FX Composer 툴 기술 밖에 ㅡㅡㅋㅋ 여하튼 또 켑쳐 사진이라 보이진 않겠지만 두개의 Bump Map을 가지고 짬뽕 시켜서 물이 출렁 출렁 되겠금 만들었다. 

'Or.......... > Work' 카테고리의 다른 글

Scene Graph Rendering  (0) 2009.08.27
kd-tree Introduction  (0) 2009.08.27
Grass Rendering  (0) 2009.08.27
Flight Simulator : HUD - LCOSS  (0) 2009.08.27
Line - Line Intersect  (0) 2009.08.27
,

Lead Computing Optical Sight System

도담에 와서 시작한 작업이다.

기존 군에서 사용하고 있던 F5E-CPT 의 IG (3D 엔진이라고 생각하면 됀다. 시뮬레이터에선 Image Genertor로 불리고 있다) 를 우리가 개발한 IG로 교체하는 작업이였다. 그러면서 추가적으로 LCOSS라는 부분이 필요하게 되었다. LCOSS는 F5E의 레이더의 한 부분으로 각 모드 (미사일, 건, 도그파이트)에 따라 LCOSS심볼이 작동하는것이다.

- 이 작업을 하면서 엄청나게 빡셌다. 전투기에 대한 지식이 없어서 막 헤맸다. 게다가 기존의 LCOSS는 OpenGVS (퀀텀 3D의 visual API)로 돼어있어서 어떻게 동작하는 분석 조차 힘들었다. 또한 코드가 다 하드코딩 돼어있어서 애먹었다. 하여튼 열심히 야근한 결과 납품 완료 !! (11월 납품 : 공군)

 

 

참고 사이트 : http://dodaam.com/product/Fixed_Wing/F5eCPT.html

'Or.......... > Work' 카테고리의 다른 글

Scene Graph Rendering  (0) 2009.08.27
kd-tree Introduction  (0) 2009.08.27
Grass Rendering  (0) 2009.08.27
Water Rendering  (0) 2009.08.27
Line - Line Intersect  (0) 2009.08.27
,

Line - Line Intersect

from Or........../Work 2009. 8. 27. 14:50

2D Line - Line Intersect

IntersectLineLine(D3DXVECTOR3 Line1Start, D3DXVECTOR3 Line1End, D3DXVECTOR3 Line2Start, D3DXVECTOR3 Line2End)

{

  float A1, B1, C1, A2, B2, C2, M1, M2, DetInv;

  if ((Line1End.x - Line1Start.x) != 0)
   M1 = (Line1End.y - Line1Start.y) / (Line1End.x - Line1Start.x);
  else
   FALSE;

  if ((Line2End.x - Line2Start.x) != 0)
   M2 = (Line2End.y - Line2Start.y) / (Line2End.x - Line2Start.x);
  else
   FALSE;

  // Compute constants
  A1 = M1;
  A2 = M2;

  B1 = -1;
  B2 = -1;

  C1 = (Line1Start.y - M1 * Line1Start.x);
  C2 = (Line2Start.y - M2 * Line2Start.x);

  // Compute the inverse of the determinate
  DetInv = 1 / (A1 * B2 - A2 * B1);

  // Use Kramers rule to compute Intersect Point
  float IntersectX, IntersectY;
  IntersectX = (B1 * C2 - B2 * C1) * DetInv;
  IntersectY = (A2 * C1 - A1 * C2) * DetInv;

  return TRUE;

} // end Intersect_Lines

'Or.......... > Work' 카테고리의 다른 글

Scene Graph Rendering  (0) 2009.08.27
kd-tree Introduction  (0) 2009.08.27
Grass Rendering  (0) 2009.08.27
Water Rendering  (0) 2009.08.27
Flight Simulator : HUD - LCOSS  (0) 2009.08.27
,