1.1 무잠금 알고리즘들

  • 무잠금 알고리즘들이 반드시 대기 없는 (wait-free) 알고리즘인 것은 아니다.
  • 대기 없는 알고리즘은 모든 스레드가 항상 작업을 진행할 수 있게 하는 것인 반면, 무잠금 알고리즘은 적어도 하나의 스레드가 작업을 진행할 수 있게 하는 것일 뿐이다.
  • 무잠금 알고리즘을 만들 때에는 stack이나 queue와 같은 간단한 무잠금 자료구조를 만들고 그것을 적절히 조합해서 복잡한 알고리즘을 구축하는게 효과적.
  • 예제) stack, queue, freelist

범용 기본수단 (universal primitive)

  • 무잠금 알고리즘에 적합한 기본수단
  • 비교 및 교환 (Compare and Swap, CAS)
  • 연결된 적재/조건부 저장 (Load Linked/Store Conditional, LL/SC))
  • 비교 및 교환 2 (Compare and Swap 2, CAS2)
  • 이중 비교 및 교환 (Double Compare and Swap, DCAS)
  • 비교 및 교환 N (Compare and Swap N, CASN)
  • 다중 워드 비교 및 교환 (Multiword Compare and Swap, MCAS)

ABA 문제

  • CAS 기반 알고리즘에는 어긋난 참조에 관련되 문제점이 존재
  • 무잠금 스택일 때, 뽑힌 횟수를 갱신하고 이걸 바탕으로 머리가 변경됐는지 여부를 판단
  • LL/SC를 사용하면 ABA 문제가 아예 발생하지 않음

무잠금 기법의 기초

  • 필요한 작업을 클래스 외부의 한 객체에서 오프라인으로 수행
  • 그것이 끝나면 공유 자료에 대한 포인터를 CAS로 갱신
  • CAS가 실패하면 처음부터 다시 시작

저자

  • Lock-Free Algorithms - Toby Jones

1.2 OpenMP를 이용한 다중 코어 프로세서 활용

  • 병렬 프로그래밍을 지원하는 이식성 있는 업계 표준 API이자 C/C++ 프로그래밍 프로토콜
  • 플랫폼에 독립적
  • 지시문 몇 개 추가로 구현할 수 있어서 가독성이 좋다
  • 이 코드를 병렬로 실행했을 때, 성능에 이익이 어느정도 있을지 테스트하기에 좋다.

저자

  • Utilizing Multicore Processors with OpenMP - Pete Isensee

1.3 OpenCV 라이브러리를 이용한 게임에서의 게임 컴퓨터 시각 활용

  • Open Computer Vision 라이브러리.
  • 플레이어 피부 표본을 이용해 히스토그램을 생성한 후 역투영(back projection) 이미지를 만들어 얼굴 위치를 검출하는 예제

저자

  • Computer Vision in Games Using the OpenCV Library - Arnau Ramisa, Enric Martí, Enric Vergara

reference

1.4 게임 객체의 지리 격자 등록

지리적 격자(geographic grid)를 적용해 근접 및 시선 판정에 필요한 계산을 줄이는 방법

저자

  • Geographic Grid Registration of Game Objects - Roger Smith

1.5 BSP 기법들

binary space partition 컴파일러 소개. PVS 생성 방법.

사용

  • 뒤에서 앞으로 렌더링되는 다각형들을 정렬할 때 쓰인 기법
  • BSP 기반 충돌 검출
  • 잠재 가시 집합(potentially visible set, PSV) 계산

BSP 종류

  • 노드 기반 BSP
  • 다각형을 자르지 않는 노드 기반 BSP
  • 볼록 말단형 BSP (leafy BSP)

저자

  • BSP Techniques - Octavian Marius Chincisan

1.6 최근접 문자열 부합 알고리즘

  • ’객체 ID ’Key Word’를 찾지 못했습니다. 혹시 ’keyword’를 찾으려고 하셨나요?’
  • 실행시점 효율성을 보장하지 않는 대신, 자원 할당 및 코드 크기 측면에서 최적화된 알고리즘
  • 레벤슈타인 거리 공식(Levenshtein distance formula)을 실용적으로 구현

저자

  • Closest-String Matching Algorithm - James Boer

1.7 CppUnit을 이용한 단위 검사 구현

난 CppUnit보단 gtest가 좋더라.

저자

  • Using CppUnit To Implement Unit Testing - Blake Madden

1.8 저작권 침해의 억제 및 검출을 위한 출시 전 빌드 지문 적용

빌드에 지문을 추가하는 전략들 소개.

전략

| 전략                                    | 구현 난이도    | 검출난이도       |
| 도입 화면에 이름 표시                   | 극도로 쉬움    | 그리 어렵지 않음 |
| 가짜 파일 추가                          | 극도로 쉬움    | 아주 어려움      |
| Adobe Photoshop CS Digimarc             | 대단히 쉬움    | 다소 어려움      |
| 이미지 파일에 지문 추가                 | 아주 쉬움      | 극도로 어려움    |
| 3D 모형, 애니메이션, 효과음에 지문 추가 | 그리 쉽지 않음 | 극도로 어려움    |
| 실행파일에 지문 추가                    | 다소 어려움    | 극도로 어려움    |
| 여러 전략 결합                          | 가변적         | 극도로 어려움    |

저자

  • Fingerprinting Pre-Release Builds To Deter and Detect Piracy - Steve Rabin

1.9 접근 기반 파일 재배치를 이용한 더 빠른 파일 적재

  • 일반적으로 자원 묶음 파일(packed resource file) 안의 실제 자원들의 순서는 디스크 상의 디렉터리 구조를 반영
  • 하지만 자원들을 디렉터리 안의 순서 그대로 사용하는 일은 거의 없다.
  • 게임이 자원을 어떻게 사용하는지에 대한 자료를 수집하고, 그 사용 패턴을 이용해 묶음 파일 안에서의 파일 순서를 최적화하는 해법을 제시

저자

  • Faster File Loading with Access-Based File Reordering - David L. Koenig

1.10 빠른 반복을 위한 실행시점 자산 즉석적재

자산 변환기, 파일 감시기, 실행시점 수신기, 자산 재연결’로 구성

저자

  • Stay in the Game: Asset Hotloading for Fast Iteration - Charles Nicholson, Noel Llopis

2.1 부동소수점 비법들

  • IEEE 754 형식, 예외 사항들 설명
  • float를 int로 취급해 비트 연산으로 빠르게 조작하는 방법을 소개

저자

  • Floating-Point Tricks - Chris Lomont

2.2 동차 좌표를 이용한 투영 공간 안에서의 GPU 계산

  • 교차 판정을 동차 좌표들을 직접 사용해서 수행하는 방법을 설명.
  • 동차 좌표(homogeneous coordinates)에서 유클리드 좌표(euclidean coordinates)로 변환해 사용하면
    • 나눗셈은 느리다
    • 0으로 나누기 예외 및 수치적 불안정성

동차 좌표를 이용해 안정적이고 간단하게 풀 수 있는 문제

  • \(E^2\) 공간의 동차 좌표들로 주어진 두 점을 지나는 하나의 선 구하기
  • \(E^2\) 공간의 두 선의 교점 구하기
  • \(E^3\) 공간의 동차 좌표들로 주어진 세 점으로 결정되는 평면 구하기
  • \(E^3\) 공간의 세 평면의 교점 구하기

저자

  • GPU Computation in Projective Space Using Homogeneous Coordinates - Vaclav Skala

2.3 외적으로 1차 연립방정식 풀기

  • 크레이머 법칙(Cramer’s rule)을 사용
    • 각 미지수에서 분자 열 순서를 바꾸면 외적에서 사용하는 scalar component
  • 두 음함수 선(implicit line, 암묵적 선)들의 교점을 계산하거나 주어진 두 점을 지나는 음함수 선의 계수를 구하는 데 유용.

저자

  • Solving Systems of Linear Equations Using the Cross Product - Anders Hast

2.4 게임 개발을 위한 순차 색인 기법

  • 객체들의 모음을 수학적인 수열(sequence)로 취급하고 색인화, 역색인화를 위한 수학 공식 소개.
  • 범위 수열, 치환 수열(순열), 조합 수열

저자

  • Sequence Indexing for Game Development - Palem GopalaKrishna

2.5 다면체의 정확한 부력

  • 질량 중심, 부력 중심을 찾아 돌림힘(torque, 토크) 계산
  • 물의 관성을 무시해 다소 비현실적인 부침(bobbing) 행동이 나타날 수 있다
  • 완전한 동적 물 시뮬레이션에 비해선 훨씬 단순
  • 부력 계산 결과를 재사용해 물의 항력(drag force)을 근사하는 방법도 소개

이전 실시간 부력 방법

  • 모형에 내장된 구(sphere)를 이용해 부력을 근사
  • 물체 표면에 부력을 근사하는 데 쓸 점들을 분산

저자

  • Exact Buoyancy for Polyhedra - Erin Catto

2.6 강체와 상호작용하는 실시간 입자 기반 유체 시뮬레이션

파티클 기반 기법인 SPH(smoothed particle hydrodynamics) 소개. 친절하다.

저자

  • Real-Time Particle-Based Fluid Simulation with Rigid Body Interaction - Takashi Amada

3.1 모형 기반 의사결정 방법을 게임에 적용: Locust AI 엔진을 Quake III에 적용하기

  • 규칙 기반이 아닌 행동, 행동의 결과, 관찰과 같은 모형에 기초한 접근 방식
  • 미래의 의사결정 과정에 근거한 기대성과(expected outcome)를 최대화하는 선택
  • 관찰 -> 갱신 -> 결정 -> 행동 주기

저자

  • Applying Model-Based Decision-Making Methods to Games: Applying the Locust AI Engine to Quake III - Armand Prieditis, Mukesh Dalal

3.2 자율 NPC들의 협동 구현

  • 중앙집중이 아닌 자율적 접근 방식 소개
  • 애니메이션, 이동, 감지, 행동을 처리하는 제어기들로 구성된 NPC

저자

  • Achieving Coordination with Autonomous NPCs - Diego Garcés

3.3 게임을 위한 행동 기반 로봇 아키텍처

저자

  • Behavior-Based Robotic Architectures for Games - Hugo Pinto, Luis Otavio Álvares

3.4 퍼지 감지기, 유한상태 행동, 행동망으로 목표 지향적 Unreal Tournament 로봇 만들기

  • Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Extended Behavior Networks - Hugo Pinto, Luis Otavio Álvares

3.5 목표 지향적 Unreal 봇: 확장 행동망으로 목표 지향적 행동과 간단한 개성을 가진 게임 에이전트 만들기

  • A Goal-Oriented Unreal Bot: Building a Game Agent with Goal-Oriented Behavior and Simple Personality Using Extended Behavior Networks - Hugo Pinto, Luis Otavio Álvares

3.6 지지 벡터 기계를 사용하는 단기 기억 모형

  • Short-Term Memory Modeling Using a Support Vector Machine - Julien Hamaide

3.7 교전 분석에 정량 판정 모형 적용하기

  • Using the Quantified Judgment Model for Engagement Analysis - Michael Ramsey

3.8 플러그인 모듈식 다층 AI 엔진 설계

  • Designing a Multilayer, Pluggable AI Engine - Sebastien Schertenleib

3.9 퍼지 제어를 이용한 장면 복잡도 관리

  • A Fuzzy-Control Approach to Managing Scene Complexity - Gabriyel Wong, Jialiang Wang

4.1 스크립팅 언어 개괄

  • Scripting Language Survey - Diego Garcés

4.2 C/C++ 객체와 루아의 바인딩

  • Binding C/C++ Objects to Lua - Luiz Henrique de Figueiredo, Roberto Ierusalimschy, Waldemar Celes

4.3 루아 코루틴을 이용한 고급 제어 메커니즘 구현

  • Programming Advanced Control Mechanisms with Lua Coroutines - Luiz Henrique de Figueiredo, Roberto Ierusalimschy, Waldemar Celes

4.4 다중 스레드 환경에서 고수준 스크립트 실행 관리하기

  • Managing High-Level Script Execution Within Multithreaded Environments - Sebastien Schertenleib

4.5 비개입 대리자를 이용한 활동 객체 속성 노출

  • Exposing Actor Properties Using Nonintrusive Proxies - Matthew Campbell

4.6 게임 객체 구성요소 시스템

  • Game Object Component System - Chris Stoy

5.1 상호작용 캐릭터를 위한 사실적인 유휴 동작 합성

  • Synthesis of Realistic Idle Motion for Interactive Characters - Arjan Egges, Nadia Magnenat-Thalmann

5.2 적응형 이진 트리를 이용한 공간 트리

  • Spatial Partitioning Using an Adaptive Binary Tree - Martin Fleisz

5.3 준 유향 경계상자를 이용한 개선된 객체 선별

  • Enhanced Object Culling with (Almost) Oriented Bounding Boxes - Ben St. John

5.4 최적의 렌더링을 위한 스킨 분할

  • Skin Splitting for Optimal Rendering - Dominic Filion

5.5 GPU 지형 렌더링

  • GPU Terrain Rendering - Harald Vistnes
  • nil

5.6 상호작용적인 유체의 동역학 및 GPU 렌더링

  • Interactive Fluid Dynamics and Rendering on the GPU - Frank Luna

5.7 빠른 픽셀 당 다중 광원 조명

  • Fast Per-Pixel Lighting with Many Lights - Frank Puig Placeres

5.8 도로 표지를 뚜렷하게 렌더링하기

  • Rendering Road Signs Sharply - Jörn Loviscach

5.9 게임을 위한 실용적인 하늘 렌더링

  • Practical Sky Rendering for Games - Aurelio Reis

5.10 OpenGL 프레임 버퍼 객체를 이용한 HDR 렌더링

  • High Dynamic Range Rendering Using OpenGL Frame Buffer Objects - Allen Sherrod

6.1 변형 가능 메시에서 실시간으로 소리 내기

  • Real-Time Sound Generation from Deformable Meshes - Marq Singer

6.2 실시간 효과음을 위한 가벼운 음 합성기

  • A Lightweight Generator for Real-Time Sound Effects - Frank Luchs

6.3 실시간 버스 믹싱

  • Real-Time Mixing Busses - James Boer

6.4 잠재 가청 집합

  • Potentially Audible Sets - Dominic Filion

6.5 저렴한 도플러 효과

  • A Cheap Doppler Effect - Julien Hamaide

6.6 실시간 DSP 효과 흉내내기

  • Faking Real-Time DSP Effects - Robert Sparks

7.1 3D 캐릭터 애니메이션 자료 스트림의 동적 적응

  • Dynamically Adaptive Streaming of 3D Data for Animated Characters - Chris Joslin, Nadia Magnenat-Thalmann, Stephane Garchery, Thomas Di Giacomo, 김형석

7.2 대규모 다중플레이어 게임을 위한 복잡계 기반 고수준 아키텍처

  • Complex Systems-Based High-Level Architecture for Massively Multiplayer Games - Chun Che Fung, Kok-Wai Wong, Viknashvaran Narayanasamy

7.3 게임 객체를 위한 전역 고유 식별자 생성

  • Generating Globally Unique Identifiers for Game Objects - 김용하

7.4 MMOG의 프로토타이핑: 세컨드라이프를 이용한 게임 개념 프로토타입 작성

  • Massively Multiplayer Online Prototype Utilizing Second Life for Game Concept Prototyping - Peter Smith

7.5 NAT 구멍 뚫기와 신뢰성 있는 동급간 게이밍 TCP 연결

  • Reliable Peer-to-Peer Gaming Connections Penetrating NAT - Larry Shi