다이아몬드-제곱 알고리즘
Diamond-square algorithm
다이아몬드-제곱 알고리즘은 컴퓨터 그래픽용 높이 맵을 생성하는 방법입니다.이것은 2차원 풍경을 생성하는 중간점 변위 알고리즘의 3차원 구현보다 약간 더 나은 알고리즘이다.적용 시 발생하는 플라즈마 효과 때문에 랜덤 중간점 변위 프랙탈, 구름 프랙탈 또는 플라즈마 프랙탈이라고도 합니다.
이 아이디어는 [1]SIGGRAPH 1982에서 Fournier, Fussell 및 Carpenter에 의해 처음 소개되었습니다.
다이아몬드-제곱 알고리즘은 2차원 그리드에서 시작하여 전체 평면이 정사각형으로 덮이도록 점 그리드에 배열된 4개의 시드 값에서 지형 높이를 임의로 생성합니다.
묘사
다이아몬드-제곱 알고리즘은 폭과 높이가n 2 + 1인 2차원 정사각형 배열로 시작합니다.배열의 네 모서리 점을 먼저 초기 값으로 설정해야 합니다.그런 다음 모든 배열 값이 설정될 때까지 다이아몬드 스텝과 정사각형 스텝이 번갈아 수행됩니다.
- 다이아몬드 스텝:배열의 각 정사각형에 대해 해당 정사각형의 중간점을 네 구석점의 평균에 랜덤 값을 더한 값으로 설정합니다.
- 정사각형 스텝:배열의 각 다이아몬드에 대해 해당 다이아몬드의 중간점을 네 모서리 점의 평균에 랜덤 값을 더한 값으로 설정합니다.
각 반복에서 랜덤 값의 크기에 2를−h 곱해야 합니다. 여기서 h는 0.0과 0.1 사이의 값입니다(값이 작을수록 지형이 거칠어짐).
정사각형 단계에서 배열의 가장자리에 있는 점에는 인접한 값이 4개가 아닌 3개만 설정됩니다.이 문제를 해결하는 방법은 여러 가지가 있습니다.가장 간단한 방법은 인접한 세 값의 평균을 구하는 것입니다.또 다른 옵션은 어레이의 반대쪽에서 네 번째 값을 가져와서 '랩 어라운드'하는 것입니다.일관된 초기 코너 값과 함께 사용할 경우 생성된 프랙탈을 중단 없이 함께 연결할 수도 있습니다.
시각화
아래 그림은 5 × 5 배열에서 다이아몬드-제곱 알고리즘을 실행하는 단계를 보여 줍니다.
적용들
이 알고리즘은 사실적인 풍경을 생성하기 위해 사용할 수 있으며, Terragen과 같은 컴퓨터 그래픽 소프트웨어에서는 다양한 구현이 사용됩니다.프로시저 텍스처의 공통 컴포넌트로도 사용할 수 있습니다.
아티팩트 및 확장
다이아몬드-제곱 알고리즘은 SIGGRAPH 1986의[2] Gavin S. P. Miller에 의해 분석되었으며, 그는 알고리즘이 직사각형 그리드에서 발생하는 가장 중요한 섭동으로 인해 눈에 띄는 수직 및 수평 "창출"을 생성하기 때문에 결함이 있다고 설명했다.그리드 아티팩트는 J.P에 의해 도입된 일반화 알고리즘으로 해결되었다.루이스.[3] 이 변종에서 이웃 점들의 가중치는 고정된 것이 아니라 추정이론에 의해 동기부여된 작은 선형 시스템을 풀어서 얻어진다.Lewis 알고리즘은 또한 구릉이나 바다의 파도와 같은 비골절 높이 지도를 합성할 수 있습니다.적응 미세화의 가능성은 상실되지만 푸리에 [4]합성을 통해 유사한 결과를 효율적으로 얻을 수 있다.다이아몬드-제곱 알고리즘과 그 정교함이 [4]이 책에서 검토된다.
레퍼런스
- ^ Fournier, Alain; Fussell, Don; Carpenter, Loren (June 1982). "Computer rendering of stochastic models". Communications of the ACM. 25 (6): 371–384. doi:10.1145/358523.358553.
- ^ Miller, Gavin S. P. (August 1986). "The definition and rendering of terrain maps". ACM SIGGRAPH Computer Graphics. 20 (4): 39–48. doi:10.1145/15886.15890.
- ^ Lewis, J. P. (1 July 1987). "Generalized stochastic subdivision". ACM Transactions on Graphics. 6 (3): 167–190. CiteSeerX 10.1.1.21.3719. doi:10.1145/35068.35069.
- ^ a b Peitgen, Heinz-Otto, Dietmar Saupe (1988). The Science of fractal images. New York: Springer-Verlag. ISBN 978-0-387-96608-3.
외부 링크
- 다이아몬드-제곱 알고리즘을 사용한 Lua용 단순 오픈 소스 높이 맵 모듈
- 랜덤 프랙탈 지형 생성: GameProgrammer.com의 다이아몬드 제곱 알고리즘
- Justin Seyster 웹 페이지의 Plasma Fractal
- 패트릭 한의 홈 페이지에 있는 혈장 프랙탈이
- Lighthouse3d.com의 지형 튜토리얼
- 캔버스를 사용한 랜덤 중간점 변위
- 랜덤 중간점 변위법
- Github(PHP)의 다이아몬드 앤 스퀘어 알고리즘
- Uncle Bob's Clean Coder 블로그에서 알고리즘 구현을 테스트하는 예
- X마운트형 사이드 스크롤 X11 실장.알고리즘 상세
- 간단하고 간단한 Python 구현입니다.고정 및 정기 경계 조건을 모두 처리합니다.
