FractalTerrain

프랙털 지형생성

알고리즘 - 2001/05/06 01:02, 파연

컴퓨터 그래픽의 게임 등의 응용에 있어서 지형을 모델링할 때, 산이나 계곡의 굴곡을 모두 만들어 넣는 것은 엄청난 노가다를 요구합니다. 그걸 컴퓨터가 하도록 맡겨버리자는 것이 fractal terrain 라는 것입니다.

일단 초기적인 모델링은 해주어야 합니다. 보통의 경우 삼각형 서피스만으로된 지형을 만듭니다. 최종 결과물은 이 초기 지형의 특징을 그대로 따라가게 되므로 어느정도 신경을 써 줘야하는 부분입니다.

그리고 나서 서피스를 분할합니다. 변 하나를 두 개로 분할하게 되고, 결과적으로 삼각형모양의 서피스 하나는 삼각형모양 서피스 4개로 나눠지게 됩니다. 이 때 분할의 결과로 새로 만들어진 점(vertex)들의 높낮이를 정해줍니다. 같은 방법으로 계속해서 분할을 해 나가게 되고 (재귀호출을 사용), 일정한 조건이 만족되면 중지합니다.

이 때 높낮이는 원래의 높낮이에 적당한 만큼을 가감해서 만들어주는데, 여러가지 방법이 쓰입니다. 일반적인 방법으로는

  1. Uniform random offset
  2. Normally distributed offset
  3. Procedural rule

등이 있습니다. 순서대로 설명하면, Uniform random offset이란건 말 그대로 일정한 범위 내의 난수를 사용해서 높낮이를 결정하는 방법입니다. (이 때 난수는 지정된 범위내에 발생할 확률이 균일합니다)

Normally distributed 란 방법은 특별한 범위를 주는 것이 아니라 확률적으로 가우시안 분포가 되도록 난수를 발생하는 방법입니다. 이 방법은 원래의 높이를 잘 따라가게 된다는 특징이 있습니다. (삐쭉빼쭉한 험준한 지형보다는 완만한 지형이 만들어지겠죠)

Procedural rule 이란 것은 미리 준비해둔 임의의 파형을 기준으로, 새로 만들어진 점(vertex)과 대응되는 파형의 높이를 새로운 높이에 반영해주는 방법입니다.

이 때 파형을 만드는 방법들 중 하나로 Perlin 잡음이 자주 쓰이곤 합니다. 진폭과 주파수가 다른 여러개의 sine 파형의 조합으로 파형을 만들어내는 방법이라고 하지요. 상당히 난이도가 높은 방법이라고 듣긴 했습니다만, 저도 구현해본 적이 없어서 어느 정도나 힘든지는 잘 모르겠네요.

Uniform random offset 구현 - 2001/05/16 00:15, 파연

원리는 쉽지만.. 사실 실제로 구현해보면 생각같이 쉽지는 않습니다.

일단.. 각 정점들과 변들, 서피스들의 구조를 어떻게 할까를 잘 생각해보아야하구요.. 일반적으로 가장 좋다고 알려진 방법을 설명하겠습니다.

먼저 서피스 분할의 방법을 다시 살펴보도록 합시다..

1.각 변들을 처음부터 끝까지 순서대로 둘로 분할한다.

- 각 변마다 점이 하나씩 만들어진다.

- 원래의 변에서 분할된 새로운 변들이 두개가 만들어진다.

2.이제 각 서피스를 분할한다.

- 하나의 서피스는 세개로 분할된다.

              *                   *
             /                   /
            /         ==>       *---*
           /                   /   /
          *-------*           *---*---*

- 1번에서 만든 변들 이외에도 각 서피스마다 세개의 변들을 더 만들게된다.

위의 분할을 살펴보면, 먼저 1번에서 각 변을 분할해서 새로운 변들을 만들어내야 되니깐, 각 변들이 그 변을 이루는 양 끝점에 대한 정보를 갖고있어야된다는 사실을 알 수 있습니다. 또한 2번에서 생성될 서피스들을 위해서 새로 생성된 변들이 어떤 어떤 놈들인지 저장해둬야할 필요가 있다는걸 알 수 있습니다. (안 그러면 새로 서피스들을 만들었을 때 해당하는 변들을 할당해줄 수 없으니깐요)

즉.. 중요한 과정은 모두 각 변에서 이뤄진다는 말입니다.(!)

점(vertex)의 구조는 다음과 같이 되어야 할껍니다.

   struct Vertex {
      float x[3];     // 공간상에서의 위치 (x, y, z)
      float t[2];     // 사용되는 텍스춰에서의 위치 (x, y)
      float n[3];     // 점의 노말벡터
      int num_faces;  // 노말벡터를 계산하기 위한 변수
   }

여기에서 점의 노말벡터 n은 프랙털 지형생성이 모두 끝난 후, 각 서피스의 노말벡터를 구한 후에 (이는 각 서피스를 이루는 벡터들의 외적으로 알 수 있겠죠) 그 서피스를 이루는 점들에 서피스의 노말벡터를 누적시킨 후 마지막에 각 점을 대상으로 loop를 돌면서 그 점이 몇개의 서피스에 포함되느냐 하는 변수인 num_faces로 나눠주면 됩니다. (Phong shading이란 것입니다..^^)


토다는 곳