게시판

연습장(다버리고 갑니다...)-남길 글이 있으면 민가촌에 남겨주시고, 회원 가입을 받지 않습니다.

2003/09/17 (15:20) from 203.247.202.72' of 203.247.202.72'	Article Number : 207
_전	Access : 4607 , Lines : 157

[노티]20030915-0917 쿼드트리, LOD, ROAM(실외)

*.참고
지형 http://research.microsoft.com/~hoppe/svdlod.pdf
http://www.cix.co.uk/~glennc/gdcetalk_files/frame.htm 강력추천(List/Strip)

*.실내
http://www.seojewoo.pe.kr/
-.BSP ; Binary Space Partioning은 말 그대로 공간을 2개로 분할하는 알고리즘이다.
-1.3D BSP트리가 2D BSP트리와 크게 다른점은 우리가 표면을 분할하는데 사용하는 것이 선이 아니라 면을 사용한다는 점이며, 모든 n차원 bsp트리는 분할하는 공간에 있어서 n-1차원을 사용해서 작업을 한다.

  개념; http://www.gamesync.com.ne.kr/source/ch1.html
  응용; http://seojewoo.pe.kr/activex/opengl/opengl-12.htm

-.Solid Node BSP ; 그냥 BSP만 사용을 해서는 지금은 너무나 많은 폴리곤을 랜더링 하기 때문에 BSP를 확장한 Solid BSP를 사용을 한다
  -1.convex 공간 ; 4개의 벽으로 구성된 공간으로
     방안에 벽이 다른벽의 시야에 전혀 블록으로 가려지지 않는,
     관찰자가 어디 있는지에 대해 아무런 문제가 없는 공간
  -2.우리가 공간을 나눈는 일을 한다는 것은 표면을 나누는 것으로
     공간을 구성하는 분할면의 모든 앞과 뒤의 하위까지 나누어서 각각의 공간을 convex하게 세분한다.
  -3.노드를 포함한 트리에서 어떤것은 leaves로 불리워진 특별한 노드로 이루어져 있는데, 이는 트리의 가장바깥쪽에 있는 대부분의 노드들이며 어떠한 자식노드도 가지고 있지 않다.
  이것이 바로 convex 세부 공간이고, convex로 정의된 폴리곤을 포함한다.

  개념; http://seojewoo.pe.kr/activex/opengl/bsptree(kor).htm
  참고; http://www.xmission.com/~pdalton/directX.html

*.실외
20030915 Quadtrees
  http://www.gpgstudy.com/kgdp/view.php/3darticles/quadtree?view=quadtree.html

20030916 LOD
  http://www.gvu.gatech.edu/people/peter.lindstrom/papers/siggraph96/siggraph96.pdf
http://gpgstudy.com/gpgiki/ClodTerrainMeshingUsingAdaptiveQuadtrees

20030917 ROAM(Real-time Optimally Adapting Meshes)
  ; 이진 삼각형 트리(Binary Triangle Tree)에 기반한 알고리즘
  ; LOD지형 알고리즘의 세부 표현 기법

  http://www.g-matrix.pe.kr/ 의 Features/ 3D Engine/
         Realtime Dynamic Level of Detail Terrain rendering with ROAM제목으로 번역

  -1.개요
    -.여기에서 각 패치는 단순히 (우측의) 이등변 삼각형이다. 삼각형의 정점에서
      이 삼각형의 빗변의 중점을 분할하면 두 개의 새로운 이등변(우측) 삼각형을 만든다.
    --> 이러한 분할은 재귀적이며 원하는 디테일 수준에 이를 때까지 자식노드들에서도 반복
    --> 삼각형들의 좌표는 순회 도중 즉석에서 계산

    -.아주 기본적인 수준에서부터 거의 연속적인 단계로 아주 진보된 최적화까지 구현
    --> 각각의 단계는 계속하기 전에 유효화/ 아주 빠르게 분할하며 높이맵을 동적으로 갱신

    -.재귀적방법의 좋은점 중 한가지는 어떤 버텍스당 데이터(per Vertex Data)도 저장하지
      않는다(버텍스에 관련된 어떤 데이터도 저장하지 않음(?))는 점인데
      이는 램의 사용량을 줄일수 있다.

    -.사실 TriTreeNode구조체는 너무 자주 생성되고 파괴되므로 가장 효율적인 방법으로
      메모리를 할당하는 것은 반드시 필요하다. 또한 여기에는 이러한 구조체들이 수만개가
      있으므로 하나의 여분의 포인터도 엄청나게 많은 메모리를 요구하게된다.

  -2.기본구조
struct TriTreeNode {
　　　　 TriTreeNode *LeftChild; // Our Left child
　　　　 TriTreeNode *RightChild; // Our Right child
　　　　 TriTreeNode *BaseNeighbor;
　　　　　　 // Adjacent node, below us
　　　　 TriTreeNode *LeftNeighbor;
　　　　　　 // Adjacent node, to our left
　　　　 TriTreeNode *RightNeighbor;
　　　　　　 // Adjacent node, to our right
};

  -3.각각의 Patch객체는 메쉬 근사화(분할)를 위해 호출
   패치는 스크린상에 표시될 트라이앵글의 암시적좌표(x, y, z와 같은 명시적 좌표가 아님)
   를 저장하는 이진 삼각형트리이다.
    -.높이맵 파일은 메모리에 로드
    -.이 알고리즘의 나머지 부분에서 사용된 트리구조는 깊이에 따라 지수적인 크기로
      램의 사용량을 늘린다. 따라서 작은 영역을 유지하는 것은 그 깊이를 제한하는 것이다.
    -.높이맵의 동적갱신을 위해서는 변경된 지역에 대한
      편차트리(Variance Tree)를 완전하게 다시 계산해야 한다.
      아주 큰 패치의 경우 실시간 어플리케이션에서 계산하기에는 너무 느리다.
    -.커다란 정사각 플롯들(정사각형 영역)을 관리하며 각자 자신의 플롯을 가진
      다른 (정사각 플롯들(정사각형 영역)을 관리하는) LandScape 객체와 동작한다.
      이러한 설계는 좀더 큰 지형을 불러들이고 싶을 때 유용하다.
    -.초기화과정에서 높이 맵은 좀더 관리가 용아한 조각들로 분할되며
      새로운 Patch객체로 된다.

class Patch {
public:
　　 void Init( int heightX, int heightY,
　　　　　　 int worldX, int worldY,
　　　　　　 unsigned char *hMap);
　　　　　　　　 // Initialize the patch
    ...
};

  -4.세분하는 기준
   높이맵을 위한 메쉬 근사값을 생성할 때 우리는 원하는 디테일 레벨에 도달할때까지
   트리에 차일드 노드들을 재귀적으로 추가한다.
    -.먼저 우리는 메쉬 근사화 과정에서 발생하는 가시적인 에러들을 측정하는 값들을 정의
      내가 사용하는 방법은 Tread Marks엔진이 "Variance(편차)"라고 부르는 것을 참고
    -.Variance(편차, 변이)란 이진 삼각형트리의 빗변의 중점의 보간된 높이와
      그 지점에서의 실제 높이 필드값의 차이
      triVariance = abs( centerZ - ((leftZ + rightZ) / 2) );
    -.대개 편차 계산은 매 프레임마다 필요하지만 배후의 높이필드가 변하지 않는 한
      그 값은 변하지 않을 것이다.
    --> 따라서 삼각형트리와 함께 작동하는 편차트리의 개념을 도입이 가능
        편차트리(Variance Tree)는 순차배열로 작성된 전체 높이의 이진 트리로써,
        몇 개의 간단한 매크로들은 트리를 효율적으로 순회할수 있게 해주고
        우리가 이 트리에 채워넣은 데이터는 노드당 차이인 한바이트짜리 값이다.

  -5.분할
   우리의 에러측정치(편차)가 주어질 때 특정 지점에 대해 이 편차가 너무 높으면
   해당 이진 삼각형 트리를 분할하기로 결정할 것이다.
   즉 현재 삼각형 아래의 지형이 울퉁불퉁하면 더 나은 근사화를 위해 이 삼각형을
   분할해야 하며, 분할은 패어런트의 영역에 꼭 들어맞는 두 개의 차일드노드를 생성한다.

   어떤 시점에서 우리는 하나의 트라이앵글로 근사화할수 있을 정도로
   충분히 부드러운 지형을 발견하거나 더 이상 진행할 단계가 없게 될 것이다.
   결국 우리는 높이필드의 해상도까지 따라 내려간 메쉬를 생성하게된다.(?)
    -.문제점_1
      지형상에서 서로 인접하는 이진 삼각형트리들을 분할할 때 메쉬내에 크랙이 종종 발생
    --> 이는 패치경계영역 전체에 걸쳐 이 트리들을 균일하게 분할하지 않은 결과로써,
        ROAM은 네이버포인터와 메쉬 자체의 흥미있는 사실을 이용해서 해결하는데
        특정 노드의 이웃은
        동일한 레벨이거나 한레벨 더 디테일(좌/우측 이웃(neighbor)의 경우)하거나
        한 레벨 덜 디테일(베이스이웃의 경우)하다.
    ==> 귀결된 단순한 규칙;
      현재노드와 그 베이스네이버(이웃)가 둘다 서로를 가리키는 경우에만 분할한다.
      (이러한 관계를 다이아몬드라고 한다.)
      다이아몬드내의 하나의 노드를 분할하면 메쉬내의 크랙을 발생시키지 않고도
      다른 한쪽에 미러링될수 있으므로 이는 특수한 경우이다(?).

    -.어떤 노드를 분할하려고 시도할 때 세가지의 경우가 존재한다.
     1. 이 노드는 다이아몬드의 일부이다. - 이 노드와 이 노드의 베이스네이버를 분할한다.
     2. 이 노드는 메쉬의 가장자리에 있다. - 단지 이 노드만 분할하라.
     3. 이 노드는 다이아몬드의 일부가 아니다. - 베이스 네이버를 강제적으로 분할하라.
(강제분할은 다이아몬드를 발견하거나 가장자리 트라이앵글을 발견할 때
        끝나는 메쉬의 재귀적인 순회(traverse)이다.)

  -6.적용; 높이필드의 특정영역을 커버하고 있는 두 개의 이진 삼각형트리로 구성된
     하나의 패치가 주어질 때 우리는 다음의 연산들을 수행할수 있다.
     1. 편차트리(Variance Tree)를 계산하라. - 완전 높이 이진트리를 각각의
      이진 삼각형트리에 대한 편차데이터로 채우라.
      여기에서 편차란 우리의 근사화가 충분히 괜찮은지를 결정하기 위해 사용하는 측정값이다.
      삼각형의 빗변의 중점에서의 높이값과 이 빗변의 양 끝점에서 보간된 높이사이의 차이다.
     2. 지형을 분할하라. - 편차트리를 이용하여 최상위레벨의 편차가 너무 크다면
      차일드를 추가함으로써 우리의 이진 삼각형트리를 분할할 것이다.
     3. 강제분할. - 우리가 분할하려고 하는 노드가 다이아몬드의 일부가 아니라면
      이 노드에 대해 강제분할 함수를 호출하라.
      이는 원래의 분할을 완성하는 다이아몬드를 줄 것이다.
     4. 반복 - 이러한 분할과정을 이진 삼각형트리내에 존재하는 모든 삼각형들이
      현재 프레임내의 편차한계 이하로 될 때까지 또는 더 이상 분할할 노드가 없을 때까지
      차일드 노드들에 대해 반복한다.

*.흑백으로 만들기 위해서 RGB를 Gray로 바꾸기 위한 연산
float gray = Color.r * 0.3 + Color.g * 0.59 + Color.b * 0.11;