모형합성

Model synthesis

모델 합성 파동 함수 붕괴 또는 'wfc'는 절차 생성, 특히 비디오 게임 산업에서 일반적으로 사용되는 제약 조건 해결 알고리즘 제품군의 이름입니다.

알고리즘의 변형을 활용한 것으로 알려진 비디오 게임으로는 배드 노스, 타운스케이퍼, 큐드 동굴 등이 있습니다.

이러한 유형의 알고리즘의 첫 번째 예는 Paul Merrell에 의해 설명되었으며, 그는 2007년 i3D 논문에서 처음으로 '모델 합성'이라고 불렀고 2008년 SIGGRAPH 컨퍼런스와 2009년 PhD 논문에서도 발표했습니다.[2] '파동함수 붕괴'라는 이름은 2016년 맥심 구민(Maxim Gumin)의 구현이 깃허브(Github) 저장소에 게시된 후 나중에 그 알고리즘의 변형에 대한 인기 있는 이름이 되었습니다.[3] 구민의 구현은 이러한 스타일의 알고리즘을 상당히 대중화시켰으며, 이후 몇 년 동안 기술 예술가와 게임 개발자들에게 널리 채택되고 적응되었습니다.[3]

구민의 구현에는 머렐의 박사학위 논문, 양자역학의 아이디어, 컨볼루션 신경망 스타일 전달 등 많은 영감이 있었습니다.[4][5] 이 알고리즘의 대중적인 이름인 '파동함수 붕괴'는 알고리즘의 방법과 양자역학에서의 중첩과 관찰의 개념 사이에서 유추된 것입니다.[6][7] Gumin의 구현에서 나타난 몇 가지 혁신에는 중복되는 패턴을 사용하여 단일 이미지를 알고리즘의 입력으로 사용할 수 있도록 하는 것이 포함되었습니다.[8]

일부 사람들은 구민의 구현이 머렐의 구현보다 더 인기가 있음을 입증한 이유가 '모델 합성' 구현의 낮은 접근성, 3D 초점 또는 아마도 당시 일반 대중의 컴퓨팅 제약 때문일 것이라고 추측했습니다.[9]

Merrell & Gumin의 구현과 '파동함수 붕괴'의 차이점 중 하나는 다음에 어떤 셀을 '붕괴'할 것인가의 결정에 있습니다. Merrell의 구현은 스캔라인 접근법을 사용하는 반면, Gumin의 구현은 항상 가능한 결과 수가 가장 적은 셀을 다음 셀로 선택합니다.[10]

묘사

WFC 또는 '모델 합성' 알고리즘에는 몇 가지 변형이 있습니다.[6] Gumin과 Merrell의 구현은 아래에 설명되어 있으며, 다른 변형들이 언급되어 있습니다.

구민의 실행

  1. 입력 비트맵을 읽고 비트맵 내에 존재하는 패턴을 카운트합니다.
  2. 원하는 출력의 치수로 배열이 생성됩니다.
  3. 어레이의 각 셀이 '관찰되지 않음' 상태로 초기화됩니다.
  4. 다음 단계가 반복됩니다.
    1. 가능한 출력 상태의 수가 가장 적은 셀이 위치합니다.
    2. 규칙에 따라 이 셀을 가능한 상태 중 하나로 '붕괴'합니다.
    3. 모든 셀이 여전히 유효한지 확인하고 규칙을 따릅니다.
  5. 모든 셀이 확실한 상태로 '붕괴'되면 출력을 반환합니다. 출력이 불법인 경우 폐기하고 합법적일 때까지 과정을 반복합니다.

머렐의 구현

Merrell의 초기 구현은 약간의 차이는 있지만 Gumin의 구현과 실질적으로 동일합니다.

(1) Merrell 버전에서는 붕괴에 대한 가능한 출력 상태 수가 가장 적은 셀을 선택할 필요가 없습니다. 대신 스캔 라인 접근 방식이 채택됩니다. Merrell에 따르면, 이것은 품질에 부정적인 영향을 미치지 않으면서 모델의 고장률을 낮추는 결과를 초래합니다.[10] 그러나 일부 논평가들은 '붕괴'에 대한 스캔라인 접근법이 방향성 아티팩트를 초래하는 경향이 있다고 언급했습니다.[11]

(2) Merrell의 접근 방식은 알고리즘을 한꺼번에 수행하는 것이 아니라 청크로 수행합니다. 이 접근 방식은 특히 3D 공간에서 많은 대규모 복합 모델의 고장률을 크게 줄입니다.[10]

개발사항

2023년 4월 델프트 대학의 샤드 알라카와 라파엘 비다라는 '계층적 시맨틱 파동함수 붕괴'를 제안했습니다. 기본적으로 알고리즘은 단순하고 구조화되지 않은 타일 세트를 넘어 작동하도록 수정됩니다. 작업 전에 모든 WFC 알고리즘 변형은 셀당 타일 선택의 평평한 세트에서 작동했습니다.[12]

일반화된 접근 방식은 타일 세트를 '메타 타일'이라고 하는 추상 노드와 '리프 타일'이라고 하는 종단 노드로 구성된 계층 구조로 구성합니다.[13] 예를 들어, 첫 번째 패스에서 WFC는 특정 타일을 '캐슬' 유형의 메타 타일로 만들 수 있으며, 두 번째 패스에서 규칙에 따라 다른 타일로 축소됩니다(예: '벽' 또는 '풀' 타일).

참고문헌

  1. ^ Merrell, Paul (April 2007). "Example-based model synthesis" (PDF). I3D '07: Proceedings of the 2007 symposium on Interactive 3D graphics and games. doi:10.1145/1230100.1230119.
  2. ^ Merrell, Paul (2009). Model Synthesis (PDF). Chapel Hill.{{cite book}}: CS1 maint: 위치 누락 게시자(링크)
  3. ^ a b Alaka, Shaad; Bidarra, Rafael (2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. Foundations of Digital Games 2023 (FDG 2023). p. 2. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8. In 2016, Maxim Gumin unleashed the WFC algorithm, publishing a repository containing his initial implementation. Since then, WFC has had a profound impact on technical artists and game developers, getting adopted, adapted and used in commercially published and upcoming projects (Caves of Qud, Townscaper, Matrix Awakens).
  4. ^ Merrell, Paul (Aug 6, 2023). Procedural Modeling Using Graph Grammars (Video). Event occurs at 3:13.
  5. ^ "Implementing Wave Function Collapse & Binary Space Partitioning for Procedural Dungeon Generation". Shaan Khan. 2021-03-21. Retrieved 2024-03-24. In the case of WFC it is inspired off three distinctive but functionally similar algorithms& concepts; Texture Synthesis (Specifically Discrete Synthesis), Markov Chains & Quantum Mechanics. WFC was also additionally inspired by convolution neural network style transfer (CNN Style Transfer).
  6. ^ a b Gumin, Maxim (September 2016), Wave Function Collapse Algorithm, retrieved 2024-03-24
  7. ^ "The Wavefunction Collapse Algorithm explained very clearly". Robert Heaton. Retrieved 2024-03-24.
  8. ^ Gumin, Maxim (September 2016), Wave Function Collapse Algorithm, retrieved 2024-03-25
  9. ^ Alaka, Shaad (2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. Foundations of Digital Games 2023 (FDG 2023). p. 2. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8. Years before, Merrel had published the conceptually identical Model Synthesis algorithm, though it did not catch on as much as WFC did, possibly due to its lower accessibility, main 3D focus and computing requirements at the time.
  10. ^ a b c Merrell, Paul (28 July 2021). "Comparing Model Synthesis and Wave Function Collapse" (PDF). The first difference is in the step where we choose a cell and pick a label. The cells are chosen in a different order. Model synthesis sweeps through the grid in scanline order. WFC chooses the lowest entropy cell.
  11. ^ DV Gen (Apr 17, 2023). Procedural Generation with Wave Function Collapse and Model Synthesis Unity Devlog (Video). Event occurs at 15:13. Unfortunately, this method can introduce directional artifacts.
  12. ^ Alaka, Shaad; Bidarra, Rafael (April 2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. pp. 1–10. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8. To the best of our knowledge, however, all such WFC algorithm variants operate on a flat set of tile choices per cell.
  13. ^ Alaka, Shaad; Bidarra, Rafael (April 2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. pp. 1–10. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8. We propose a solution to these shortcomings by introducing (i) the notion of meta-tile, an abstract tile that represents a semantic group of tiles, along with (ii) a graph-like structure that is able to represent the hierarchy among them and the constraints between them.


Stub icon

이 소프트웨어 기사는 스텁입니다. 위키백과를 확장하여 도울 수 있습니다.

Stub icon

이 비디오 게임 관련 기사는 텁텁합니다. 위키백과를 확장하여 도울 수 있습니다.

Stub icon

이 알고리즘 또는 데이터 구조 관련 기사는 스텁(stub)입니다. 위키백과를 확장하여 도울 수 있습니다.