Game Programming Gems 6

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

OpenCV - Open Computer Vision Library - opencv.org

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

Jongbin Oh