Game Engine Gems 3 TThhiiss ppaaggee iinntteennttiioonnaallllyy lleefftt bbllaannkk Game Engine Gems 3 Eric Lengyel Edited by CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2016 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20160201 International Standard Book Number-13: 978-1-4987-5566-5 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com Contents Preface xiii  Part I Graphics and Rendering 1 Chapter 1  The Open Game Engine Exchange Format 3  Eric Lengyel  1.1 Introduction 3  1.2 OpenDDL 8  1.3 Scene Structure 12  1.4 Object Data 14  1.5 Animation 18  References 21  Chapter 2  Realistic Blending of Skies, Water, and Terrain 23  Frank Kane  2.1 The Problem 23  2.2 Blending Terrain with the Sky 26  2.3 Applying Visibility Effects to Distant Clouds 30  2.4 Creating Realistic Ocean Horizons 31  2.5 Putting it All Together 33  References 34  Chapter 3  Fog with a Linear Density Function 37  Eric Lengyel  3.1 Introduction 37    v vi  Contents  3.2 Fog Factor Calculation 38  3.3 Visibility Culling 44  References 52  Chapter 4  Vegetation Management in Leadwerks Game Engine 4 53  Josh Klint  4.1 Introduction 53  4.2 The Problem 54  4.3 The Idea 55  4.4 Culling 56  4.5 Rendering 61  4.6 Level of Detail 62  4.7 Physics 65  4.8 Future Development 70  References 71  Chapter 5  Smooth Horizon Mapping 73  Eric Lengyel  5.1 Introduction 73  5.2 Horizon Map Generation 75  5.3 Rendering with Horizon Maps 79  References 83  Chapter 6  Buffer-Free Generation of Triangle Strip Cube Vertices 85  Don Williamson  6.1 Introduction 85  6.2 Generating Cube Vertices 86  6.3 Wireframe Cubes 89  Chapter 7  Edge-Preserving Smoothing Filter for Particle Based Rendering 91  Kin-Ming Wong and Tien-Tsin Wong  7.1 Introduction 91  7.2 Guided Image Filtering 91  7.3 GLSL Implementation 94  7.4 Results and Performance 97  Acknowledgements 99  References 99 Contents  vii  Chapter 8  Variable Precision Pixel Shading for Improved Power Efficiency 101  Rahul P. Sathe  8.1 Introduction and Background 101  8.2 Algorithm 102  8.3 Results 107  8.4 Discussion 107  Acknowledgements 109  References 109  Chapter 9  A Fast and High-Quality Texture Atlasing Algorithm 111  Manny Ko  9.1 Introduction 111  9.2 Background 112  9.3 Chart Segmentation 113  9.4 Atlas Packing 115  9.5 Atlas-Aware Filtering 118  Acknowledgements 119  References 120  Part II Physics 121 Chapter 10  Rotational Joint Limits in Quaternion Space 123  Gino van den Bergen  10.1 Introduction 123  10.2 3D Rotations 124  10.3 Unit Quaternions 128  10.4 Quaternions vs. Exponential Map 129  10.5 Swing-Twist Limits 130  10.6 Volumetric Limits 137  References 138  Chapter 11  Volumetric Hierarchical Approximate Convex Decomposition 141  Khaled Mamou  11.1 Introduction 141  11.2 Convex Approximation 142  11.3 Volumetric Hierarchical Approximate Convex Decomposition 145 viii  Contents  References 157  Chapter 12  Simulating Soft Bodies Using Strain Based Dynamics 159  Muhammad Mobeen Movania  12.1 Introduction 159  12.2 Position Based Dynamics 160  12.3 Strain based Dynamics 162  12.4 Implementation Details 166  12.5 Implementing Cloth Simulation 169  12.6 Implementing Tetrahedral Mesh Simulation 172  12.7 Barycentric Interpolation 175  12.8 Experimental Evaluation 176  12.9 Future Work 179  References 181  Part III General Programming 183 Chapter 13  Generic, Lightweight, and Fast Delegates in C++ 185  Stefan Reinalter  13.1 Background 186  13.2 The Delegate Technique 188  13.3 Toward a Generic Solution 191  13.4 Embracing C++11 193  13.5 Extensions 195  13.6 Source Code 195  Chapter 14  Compile-Time String Hashing in C++ 197  Stefan Reinalter  14.1 Background 198  14.2 The Hash Technique 199  14.3 Toward a Generic Hash Function 201  14.4 Implementation Notes 204  14.5 Source Code 205  Chapter 15  Static Reflection in C++ Using Tuples 207  Nicolas Guillemot  15.1 Rethinking Composition Using Tuples 208 Contents  ix  15.2 Recursive Member Iteration 210  15.3 Practical Concerns 215  Chapter 16  Portable SIMD Programs Using ISPC 219  Nicolas Guillemot and Marc Fauconneau Dufresne  16.1 The Problem 220  16.2 ISPC Basics 222  16.3 ISPC Example Programs 222  16.4 Integration in a Game Engine 224  16.5 Tips & Tricks 227  References 228  Chapter 17  Shared Network Arrays as an Abstraction of Network Code from Game Code Logic 229  João Lucas Guberman Raza  17.1 Introduction 229  17.2 How SNAs Work 230  17.3 How a Gameplay Programmer Uses SNAs 232  17.4 How a Network Programmer Uses SNAs 234  17.5 Further Discussion 236  References 236  Part IV Character Control and Artificial Intelligence 237 Chapter 18  Vision Based Local Collision Avoidance 239  Teófilo Bezerra Dutra, Ricardo Marques, Julien Pettré, and Jan Ondřej  18.1 Introduction 239  18.2 Local Path Planning in Games 240  18.3 Vision Based Obstacle Avoidance 242  18.4 Purely Reactive Technique 244  18.5 Gradient Based Technique 247  18.6 Final Considerations 250  Acknowledgements 252  References 252