GPU Technology Conference 2012

nVidia's GPU Technology Conference is over, and a number of presentation slides have been uploaded. There were a quite a few interesting talks relating to graphics, robotics and simulation:

• Simon Green from nVidia and Christopher Horvath from Pixar presented 'Flame On: Real-Time Fire Simulation for Video Games'. It starts with a recent history of research on CG fluid systems, and gives five tips on better looking fire: 1. Get the colors right (e.g. radiation model), 2. Use high quality advection (not just bilinear filtering), 3. Post process with glow and motion blur. 4. Add noise. 5. Add light scattering and embers. They then go into more detail on Tip #1 looking at the physics behind the black-body radiation in a fire, and the color spectrum.
• Elmar Westphal of PGI/JCNS-TA Scientific IT-Systems presented 'Multiparticle Collision Dynamics on one or more GPUs', about multiparticle collision dynamics GPU code. He starts by explaining the overall algorithm, and explaining step-by-step what performs well on the GPU. Specific GPU optimisations explained include spatial subdivision lists, reordering particles in memory, hash collisions, and finally dividing workload between multiple GPU's. An interesting read.

• Michal Januszewski from the University of Silesia in Katowice introduces 'Sailfish: Lattice Boltzmann Fluid Simulations with GPUs and Python'. He explains lattice boltzmann fluid simulation, and some of the different configurations of lattice connectivity and collision operators. Moves into code generation examples, and gives a brief explanation of how the GPU implementation works.
• Nikos Sismanis, Nikos Pitsianis and Xiaobai Sun (Aristotle University, Duke University) cover 'Efficient k-NN Search Algorithms on GPUs'. Starts with an overview of sorting and K-Nearest Neighbour (KNN) search algorithm solutions, including ANN (approximate NN) and lshkit and moves into results including a comparison of thrust::sort with Truncated Bitonic sort. Software is available at http://autogpu.ee.auth.gr/.
• Thomas True of nVidia explains 'Best Practices in GPU-Based Video Processing' and covers overlapping copy-to-host and copy-to-device operations, and an example of processing bayer pattern images.
• Scott Rostrup, Shweta Srivastava, and Kishore Singhal from Synopsys Inc. explain 'Tree Accumulations on GPU' using parallel scatter, parallel reduce and parallel scan algorithms.

• Wil Braithwaite from nVidia presents an interesting talk on 'Interacting with Huge Particle Simulations in Maya using the GPU'. He begins with a brief runthrough of the workings of the CUDA SPH example, and then moves onto the particle system including Maya's body forces (uniform, radial, vortex), shape representations (implicit, covex hull, signed distance fields, displacement maps), collision response, SPH equations, and finally data transfer. Ends with a brief overview of rendering the particles in screen space. Neat.
• David McAllister and James Bigler (nVidia) cover the OptiX internals in 'OptiX Out-of-Core and CPU Rendering' including PTX code generation and optimisation, and converting the OptiX backend to support CPU's via Ocelot and LLVM. An interesting result, LLVM does better at optimising "megafunctions" than small functions, but not entirely unexpected given how LLVM works. The presentation finishes with an overview of paging and a tip on bounding volume heirarchies. Good to see Ocelot in the mainstream.

• Eric Enderton and Morgan McGuire from nVidia explain 'Stochastic Rasterization' (ala 'screen door transparency' rendering) via MSAA for motion blur, depth of field and order-independent transparency, by using a geometry shader to bound the shape and motion of each tri in screen space, and setting up the MSAA masks. Nice.
• Cliff Woolley presents 'Profiling and Tuning OpenACC Code' (by adding pragmas to C / Fortran code, ala OpenMP) using an example of Jacobi iteration, and there were a number of other talks on the topic.
• Christopher Bergström introduced 'PathScale ENZO' the alternative to CUDA and OpenCL.
• Phillip Miller from nVidia did an broad coverage of 'GPU Ray Tracing'. He starts with a myths and claimed facts on GPU raytracing, highlights some commercial GPU raytracers (and the open source OpenCL LuxRenderer) and goes into some details that are better explained in the OptiX Out-of-Core presentation.
• Phillip Miller follows with 'Advanced Rendering Solutions' where he takes a look at nVidia's iray, and where they believe they can introduce new capabilities for design studios and find a middle ground with re-lighting and physcially based rendering.

• Peter Messmer presents 'CUDA Libraries and Ecosystem Overview', where he provides an overview of the linear algebra cuBLAS and cuSPARSE libraries performance, then moves to signal processing with cuFFT and NPP/VSIP for image processing, next is random numbers via cuRAND and finally ties things up with Thrust.
• Jeremie Papon and Alexey Abramov discuss the 'Oculus real-time modular cognitive visual system' including GPU accelerated stereo disparity matching, likelihood maps and image segmentation with a parallel metropolis algorithm.

• Jérôme Graindorge and Julien Houssay from Alyotech present 'Real Time GPU-Based Maritime Scenes Simulation' beginning with ocean simulation and rendering from FFT based wave simulation using HF and LF heightmap components. They then cover rendering the mesh, scene illumination and tone mapping, and a sneak peak at boat interaction. The ocean simulation video is neat.
• Dan Negrut from the Simulation-Based Engineering Lab at the University of Wisconsin–Madison gives an overview of the labs multibody dynamics work in 'From Sand Dynamics to Tank Dynamics' including friction, compliant bodies, multi-physics (fluid/solid interactions), SPH, GPU solution to the cone complementary problem, ellipsoid-ellipsoid CCD, multi-CPU simulation, and finally vehicle track simulation in sand. Wow. Code is available on the Simulation-Based Engineering Lab website.
• Max Rietmann of USI Lugano looks at seismology (earthquake simulation) in 'Faster Finite Elements for Wave Propagation Codes' and describes parallising FEM methods for GPUs in SPECFEM3D.
• Dustin Franklin from GE introduces GE's MilSpec ruggedised Kepler-based GPU solutions and Concurrent Redhawk6 in 'Sensor Processing with Rugged Kepler GPUs'. Looks at some example applications including hyperspectral imaging, mosaicing, 360 degree vision, synthetic aperture radar processing, and space-time adaptive processing for moving target identification.
• Graham Sanborn of FunctionBay presents 'Particle Dynamics with MBD and FEA Using CUDA' and gives a brief overview of their combined CPU/GPU multi-body FEA system and briefly describes the contact, contact force, and integration steps.
• Ritesh Patel and Jason Mak of University of California-Davis cover the Burrows-Wheeler Transform, Move-to-Front Transform and Huffman Coding in 'Lossless Data Compression on GPUs'. They find merge sort for BWT performs best on the GPU, explain the parallel MTF transform and Huffman in illustrative detail and tie things up with benchmarks, unfortunately GPU is 2.78x slower than CPU.
• Nikolai Sakharnykh and Nikolay Markovskiy from NVIDIA provide an indepth explanation of their GPU implementation of solving ADI with tridiagonal systems in '3D ADI Method for Fluid Simulation on Multiple GPUs'.
• Enrico Mastrostefano, Massimo Bernaschi, and Massimiliano Fatica investigate breadth first search in 'Large Graph on multi-GPUs' and describe how best to parallelise it across multiple GPU's by using adjacency lists and level frontiers to minimise the data exchange.
• Bob Zigon from Beckman Coulter presents '1024 bit Parallel Rational Arithmetic Operators for the GPU' and covers exact 1024 bit rational arithmetic (add,sub,mul,div) for the GPU. Get the 1024 bit arithmetic code here.
• Roman Sokolov and Andrei Tchouprakov of D4D Technologies discuss 'Warped parallel nearest neighbor searches using kd-trees' where they take a SIMD style approach by grouping tree searches via voting (ballot)
• David Luebke from nVidia takes a broad look at CG in 'Computational Graphics: An Overview of Graphics Research @ NVIDIA' and provides an overview of research which is featured in a number of previous talks and other GTC talks including edge aware shading, ambient occlusion via volumes and raycasting, stochastic rendering, improved image sampling and reconstruction, global illumination, and CUDA based rasterization.
• Johanna Beyer and Markus Hadwiger from King Abdullah University of Science and Technology discuss 'Terascale Volume Visualization in Neuroscience' where each cubic mm of the brain scanned with an electron microscope generates 800 tereabytes of data. The idea here is to leverage the virtual memory manager to do all the intelligent caching work, rather than a specialised spatial datastructure for the volume rendering.
• Mark Kilgard introduces the NV_path_rendering extension in 'GPU-Accelerated Path Rendering', and demonstrates using the GPU to render PDF, flash, clipart, etc. Contains some sample code.

• Janusz Będkowski from the Warsaw University of Technology presented 'Parallel Computing In Mobile Robotics For RISE' a full GPGPU solution for processing mobile robot laser scan data through to navigation. Starts with data registration into a decomposed grid which is then used for scan matching with point-to-point Iterative Closest Point. Next is estimating surface normals using principle component analysis, demonstrated on velodyne datasets. This is used to achieve point-to-plane ICP and he demonstrates a 6D SLAM loop-closure. Finishes it all off with a simple gradient based GPU path planner.

Note that in recent days more presentation PDF's have been uploaded so there is still plenty to look through, and with all the content it's difficult to look through it all - take a look yourself! I'll leave you with a video from the GTC 2012 keynote on rendering colliding galaxies:

Graphics links post

Its been a while since I've done a link post, (almost five months) so time to catch up! From the demoscene and WebGL world we have:

• Google released WebGL 3d graphs
• Moleman 2 demoscene documentary trailer, and the documentaries themselves.
• Jochen Wilhelmy (Digi/Alcatraz) gave a talk at Revision on Exporting 3D scenes from Maya to WebGL using clang and llvm with Inka3d.
• The Plasticator open source 64k demo tool
• In an attempt to out-do themselves, Farbrausch released the code to Werkkzeug4
• Nop Jiarathanakul has a collection of source code at github on raymarching distance fields in WebGL
• Sway4k WebGL demo
• Rocket synchronises music and events/parmateres with a number of interpolation modes.
• WebGL particle love hearts, very pretty.
• Martti Nurmikari's demoscene source code for Brainstorm demos
• Riccardo Gerosa wrote a nice post on raymarching ocean waves with WebGL
• It's worth visiting the WebCL website as it is being constantly updated with new examples from Samsung and Nokia.
• The Opera guide to WebGL
• Iñigo Quílez has a lovely video on making music with maths.

In games we have:

• Fabien Sanglard posted a code review of Another World with a nice explanation of the VM and graphics, well worth a read!
• AltDev posted AltDevConf videos, including videos on PowerVR, Dynamic GI, Behaviour Trees, C#, Influence AI, and more.
• Prince of Persia source code found, you can download the PoP code for Apple II.
• Angry Fish Studios has a visual post on representing tilemaps efficiently with bitmasks
• Gijs-Jan Roelofs posted code and an explanation on generating laser FX in OpenGL
• Angelo Pesce has an interesting post onnormal maps
• A short list of free 3d games models
• Haaf's 2d Game Engine has a Haaf's Game Engine unix port.
• Crytek presentations. Enough said.
• Insomniac games research page.
• The Valve handbook for new employees and Michael Abrash's post on working at Valve.
• On the lighter side, a bearded dragon playing the ant crusher game

In tools and research we have:

• A link collection of all the SIGGRAPH course notes
• PowerVR articles on everything from OpenRL (open ray tracing library) to PVR texture compression and parallax bumpmapping. A mini (PowerVR) version of ATI and nVidia's article and tools collection.
• GNU Plotting covers tips and tricks for generating graphs and plots with GNU plot.
• Autodesk's free photofly lets you create 3d models from photos.
• Insight3D is an open source image based modeling (3D models from photos) software package.
• openFrameworks is a cross-platform C++ toolkit for making realtime visual productions, interfacing to OpenGL, GLEW, FMOD, FreeType, Quicktime, etc.
• FXGen is an open source procedural texture generator.
• libnoise is an open source noise (e.g. perlin) generator.
• Robert Schneider maintains a list of mesh generation software for all your triangulation and surface, grid, tetrahedron generation needs.
• Cyril Crassin posted his thesis on GigaVoxels.
• 3D voxel sculpting with 3d-coat.
• Sculptris is 3D sculpting software, similar to Zbrush.
• AN IMAging Library supports a number of file formats, and also simple image operations such as distance transforms.
• Pedro Felzenszwalb has some image distance transform code
• Sander van Rossen's open source Winforms library for node/graph based user interfaces.

And other interesting things:

• The batman equation.
• An interesting timeline of 3D in movies
• Andy Sloane explains his Donut ascii renderer and provides the code for the curious.
• A short youtube presentation on how your eye works and blindspots
• Take the online color challenge, how well can you see hue?

I'll leave you with the winning 64k intro from Revision:

Game Developers Conference 2012 - Technical summary

GDC2012 is over, and this year there are a huge number of available presentations. You can download the Game Developer Conference 2012 presentations from the GDC vault, Jare / Iguana has also kept a link collection from GDC 2012. I've looked over all the technical publications available and put together this summary post. (Edit: I've updated this to cover some maths, physics, and graphics material I missed on the first pass - thanks Johan & Eric)

I'll start with graphics.

Louis Bavoil / nVidia and Johan Andersson / DICE have a presentation on "Stable SSAO in Battlefield 3 with Selective Temporal Filtering", ambient occlusion is a well established technique now, but they apply a quick way to use past data and the differences in Z buffer states between frames to intelligently reuse the AO results. They also look at filters and optimising blur functions. Similar to established tricks in the realtime raytracing demoscene.

Eban Cook / Naughty Dog presented "Creating Flood Effects in Uncharted 3", a technical artist look at water effects. Unfortunately realtime fluid simulation wasn't used, instead Houdini was used to pre-generate the game content. An overview of the shaders for water, water particles, froth particles, and lighting is given.

Light probe interpolation

Robert Cupisz / Unity discussed light probes, "Light probe interpolation using tetrahedral tessellations", in terms of choosing the appropriate probe and weights using Delaunay Triangulation / Tetrahedrons and Barycentric Coordinates by dividing scenes into convex hulls. Also covers projecting onto the nearest convex hull, covers it all with a fair bit of maths, this would be of interest to physics / collision detection programmers too. There is a collection of nice links and some sample code at the end.

Matthijs De Smedt / Nixxes covers "Deus Ex is in the Details" using DX11 tech. Covers AA (FXAA DLAA MLAA), SSAO, DOF (Gaussian blur), tessellation and soft-shadows.

Colt McAnlis / Google investigates post-compressing DXT textures in his talk "DXT is not enough", trying to out-do zipped DXT's with delta encoding. More info at this blog post or skip it all and download the DXT CRUNCH compressor here.

Matt Swoboda / Sony & Fairlight delves into Signed Distance Fields, a demoscene hot-topic last year, with the talk "Advanced Procedural Rendering in DirectX 11". Investigates converting polgyon mesh data and particle data into signed distance fields. Takes an in-depth look into a optimised marching cubes implementation for a fluid simulation with smooth particle hydrodynamics (SPH), and how to use signed distance fields to do ambient occlusion.

Physically based rendering in realtime 

Yoshiharu Gotanda / tri-Ace research makes a case for physically based rendering with a Blinn-Phong model in the presentation "Practical Physically Based Rendering in Real-time". An indepth look at the BRDF formulation they use.

Wolfgang Engel, Igor Lobanchikov and Timothy Martin / Confetti present "Dynamic Global Illumination from many Lights", just a bunch of pictures, not much information.

Carlos Gonzalez Ochoa / Naughty Dog covers "Water Technology of Uncharted". Covers the shader, animating the normal maps flow, and simulating the ocean water with Gerstner waves, b-spline waves, and wave particles. They go on to look at LOD with "Irregular Geometry Clipmaps" including fixing T joints, and then culling, skylights and underwater fog. Next physics, attaching objects (buoyant), and point queries. Finally, SPU optimization. Quite comprehensive.

Water technology of Uncharted

Ben Hanke / SlantSixGames describes the bone code in "Rigging a Resident Evil". Transforms are described with 9 functions and processed with an optimising compiler, allowing fast retargeting of animations.

Scott Kircher / Volition Inc expands on Inferred Lighting in "Lighting & Simplifying Saints Row: The Third" by looking into lighting for rain, foliage, dynamic decals, and radial ambient occlusion. Then moves on to automated mesh simplification using iterative edge contraction and takes an indepth look at selecting an appropriate error metric.

Nathan Reed / Sucker Punch Productions discusses "Ambient Occlusion Fields and Decals in Infamous 2", going into depth on how to solve the artifacts of this approach.

Marshall Robin / Naughty Dog covers the effects system tools in "Effects Techniques Used in Uncharted 3: Drake’s Deception".

Niklas Smedberg / Epic Games looks at PowerVR GPU processing pipeline and capabilities in "Bringing AAA graphics to mobile platforms" and provides a number of tricks'n'tips on optimising the performance of the mobile GPU, and highlights the cheap operations. In short: AA (fast), hidden surface removal (fast), alpha test (slow), render targets (slow), texture lookups (slow). Takes a more detailed look at material shaders, god rays, and character shadows. All in all, pretend its ~2002, and you'll be right.

Mickael Gilabert / Ubisoft and Nikolay Stefanov / Massive cover the GI system in Far Cry 3 in "Deferred Radiance Transfer Volumes". Light probes get precomputed directional radiance transfer data from a custom raytracer stored using spherical harmonics. Source code for the relighting system is presented, along with optimisations by using volume textures.

John McDonald / nVidia explains CPU/GPU synching for buffers in "Don’t Throw it all Away: Efficient Buffer Management" and provides advice on buffer creation flags.

Bryan Dudash / nVidia suggests using average normals to overcome tesselation issues in "My Tessellation Has Cracks!".

Mastering DX11 with Unity

Renaldas Zioma / Unity and Simon Green / nVidia present "Mastering DirectX 11 with Unity". Starts by looking into Unity's physically based shaders (Oren-Nayar, Cook-Torrance, and energy conservation, then blurry reflections and combining normal maps). Next up, Catmull-Clark Subdivision, tetrahedra light probes (See Robert Cupisz's talk), HBAO, APEX destruction, Hair simulation with guide hairs, Explosions using signed distance fields with noise and color gradients,and finally velocity buffer motion blur.

Tobias Persson / Bitsquid discusses lighting billboards in "Practical Particle Lighting". Looks at normal generation and per-pixel lighting for billboards (including code snippets), applying shadow maps with a domain shader, and shadow casting

Karl Hillesland / AMD investigates realtime Ptex (per-face texture mapping) in "Ptex and Vector Displacement in AMD Demos", and efficient retrieval from the texture atlas, including all MIPs.

Jay McKee / AMD presents the "Technology Behind AMD’s
Leo Demo". He details some of the code behind the forward rendering of 3000 dynamic light sources using a depth pre-pass, light culling (tile-based compute shader to output light list), and light accumulation with materials phase. Basically moves the light management code from CPU to GPU.

Terrain in Battlefield 3

Mattias Widmark / DICE presents "Terrain in Battlefield 3: A modern, complete and scalable system". Begins with an overview of the features for the terrain system (heightfield based, procedurally generated, spline decals, decoration (tree,rock,grass), destruction, water), and presents their quadtree terrain data structure, paying particular attention to LOD. Next, CPU/GPU performance is investigated, and a clip-map based virtual texture system is presented. The large terrain data set is managed by intelligently streaming data to the required detail ('blurriness'), and co-locating data (heighfield/color/mask lumped together, next to the next level of relevant LOD data), which is also compressed (RLE/DXT1). Nodes are then prioritized based on distance, culling, and updates (e.g. destruction). Finally, mesh generation, stitching and tessellation with displacement on the GPU.




Moving on to physics.

Erin Catto covers "Diablo 3 Ragdolls", including representing ragdoll bones, initialising ragdolls from animations, and interacting kinematic and dynamic objects.

François Antoine / Epic talks about Gears of Wars 3 destruction physics in "Pushing for Large Scale Destruction FX" and suggests using particles for dust and debrie, and simplifying meshes for destruction.

Stephen Frye / EA looks at ragdolls in the presentation "Tackling Physics". Highlights aspects of ragdolls that look unrealistic, and suggests adding joint limits and motorized constraints at joints to simulate muscles. Gives two approaches to solving the control problem, first using external forces, second calculating the appropriate torque from world space.

Graham Rhodes / Applied Research Associates presents "Computational Geometry" where he looks at half-edge data structures for triangulating a polygon, splitting a face, splitting an edge, intersection of an edge and a plane and generating a convex hull.

Richard Tonge / nVidia covers "Solving Rigid Body Contacts" and starts with a gentle introduction to rigid body state space and progressively builds a signal-block-diagram of solving a single contact restraint. Then looks at each block in the diagram and deciphers the physics behind it. He then looks at solving multiple contacts, and explains why you can't apply a linear solver to the problem (contacts break), and presents the LCP, and an alternative approach; sequential impulses. He then gives a whirlwind tour of GPU solvers.

Gino van den Bergen / DTECTA presents "Collision Detection", first covering shapes, then configuration space, distance tests, Seperating Axis Tests, and takes a closer look at the GJK algorithm.

Jim Van Verth / Insomniac gives a nice introduction to Navier Stokes in "Fluid Techniques", breaking down the terms for external forces, viscocity, advection and pressure visually. Then looks at three major representations for fluids, grid, particle and surface (wave) based.

Takahiro Harada / AMD examines how heterogeneous compute architectures can achieve large scale dynamic simulations in "Toward A Large Scale Simulation". Begins with an overview of GPU architecture, and GPU rigid body simulation in three key phases: broad-phase, narrow-phase and constraint solving for a system of 128,000 particles and 12,000 convex bodies. He presents a design for overcoming data transfer and minimising synchronisation points whilst dividing the workload between CPU and GPU.

Erwin Coumans / AMD investigates destructive physics in the aptly titled "Destruction". He begins with generating voroni diagrams for shattering geometry and boolean operations, and moves into generating collision shapes with convex decomposition and tetrahedralization. Then moves on to realtime approaches with real-time booleans and breakable constraints and finite element
methods.



Looking at AI.

Bobby Anguelov / IO Interactive, Gabriel Leblanc / Eidos-Montréal and Shawn Harris / Big Huge Games present "Animation-Driven Locomotion For Smoother Navigation". They start with the standard motion graphs and transitioning/blending between animation cycles. Then take an indepth look at footstep planning (IK, Foot sliding) and come up with a system for deciding where steps should be taken to fulfil the navigation goal. They then investigate modifying navigation paths to better fit the animation cycles, and finish by looking into collision avoidance.

Daniel Brewer / Digital Extremes looks at agent perception, reaction, combat chatter, buddy systems and collision avoidance using velocity space Optimal Reciprocal Collision Avoidance in "Building Better Baddies".

Brian Magerko / Georgia Tech covers "How to Teach Game AI from Scratch" including competitions (Mario AI, Google Ants, Poker AI, Starcraft AI).

Dave Mark / Intrinsic and Kevin Dill / Lockheed Martin investigate some examples (snipers, guards) of Utility-Based AI in "Embracing The Dark Art of Mathematical Modeling in Game AI".

Kasper Fauerby / IO Interactive explains "Crowds in Hitman:Absolution" including cell maps, boids, animation and PS3 implementation details. The crowd AI uses a state machine with steering behaviours (pending walk, walk, panic), and behaviour 'zones' with information from the navigation system to select behaviours. Near-optimal Character Animation with Continuous Control was used for animation.

Elan Ruskin / Valve looks at empowering writers and dialog in TF2, Left4Dead, etc, in "Rule Databases for Contextual Dialog and Game Logic". Begins with player triggered lines (extended by environment, memory etc.) and avoiding fill-in-the-blank dialog by using databases. Rules, queries, responses and writers tools are examined next, and ties things off with database query optimisations.

Mike Robbins / Gas Powered Games examines "Neural Networks in Supreme Commander 2", with 34 inputs and 15 output actions and a single hidden layer (98 neurons), with a fitness function composed from 17 inputs trained to control combat platoons.

Ben Sunshine-Hill / Havok investigates LOD for AI in "Perceptually Driven Simulation", and makes a case for using probability of noticing a difference instead of distance as a LOD measure, and presents a market-based "LOD trader" for selecting the appropriate LOD given the constraints on hand.

Moving along to programming and math.

Adisak Pochanayon / Netherrealm covers debugging and timing issues in "Runtime CPU Spike Detection using Manual and Compiler-Automated Instrumentation". First up, manual instrumentation and wrapper functions, Then detours, and automated instrumentation (compiler flags) with an indepth look at the 360. Finally, profiling with threshold functions.

Pete Isensee / Microsoft details how rvalue in C++11 (T&&) can eliminate temporaries in "Faster C++: Move Construction and Perfect Forwarding".

Scott Selfon / Microsoft reviews audio compression technologies in "The State of Ady0 Cmprshn", starting with time-domain compression with PCM (raw, A-Law, U-Law, ADPCM), then frequency-domain compression and discusses the artifacts generated by both, then evaluates the performance of different codecs.

Robin Green / Microsoft and Manny Ko / Dreamworks present "Frames, Quadratures and Global Illumination: New Math for Games". Beings with a review of spherical harmonics, Haar wavelets, and Radial basis functions. Builds up to 'Spherical Needlet' wavelets, by exploring different basis functions ('frames')

Gino van den Bergen / DTECTA presents dual-numbers in "Math for Game Programmers: Dual Numbers", beginning with a look at complex numbers. Automatic differentiation with dual numbers is then described, with code, and examined in curve tangents, directed line geometry (triangle/ray intersections, plucker coordinates, angles), and rigid body transforms/skinning (dual quaternions).

Jim Van Verth / Insomniac explains rotation formats in "Understanding Rotations", including angle (2d) Euler angles, Axis-angle, Matrix (2d/3d), complex (2d) and Quaternion (3d). Interpolation is considered for each case (including slerp).

Eric Lengyel / Terathon presents exterior (Grassmann) algebra in "Fundamentals of Grassmann Algebra". This includes the wedge product, bivectors, trivectors and multivectors. Moves on to cross product transforms, dual-basis 'anti-vectors', regressive 'antiwedge' product, and demonstrates how these can be used in homogeneous and plucker coordinate systems. This leads on to basic intersections (line, plane, point) and distances (point plane, two lines) and finally ray-triangle intersection using bivectors to avoid barycentric coordinates.

Squirrel Eiserloh / TrueThought presents "Interpolation and Splines". Takes us back to basics by looking at averaging and blending, and moves onto interpolation. Begins with quadratic and cubic Bézier curves, then moves into splines and discusses continuity. Cubic Hermite splines are up next, and how to convert between Bézier and Hermite, then Catmull-Rom splines and finishes with the more general Caridnal splines.

John O’Brien / Insomniac covers "Math for Gameplay / AI". Starts with object intersection tests (sphere-sphere, sphere-plane, AABB-AABB, AABB-ray, capsules-capsule, capsule-ray) and projecting onto a plane in a gun turrent AI example. Next up, Bayes' Theorem and conditional probability, followed by fuzzy logic.

The Web up next

Corey Clark and Daniel Montgomery present "Building a Multi-threaded Web-Based Game Engine" covering both client side (WebGL, WebSockets, etc) and server side (NodeJS, Hosting, etc).

Michael Weilbacher / Microsoft looks at server issues in "Dedicated Servers in Gears of War 3".

Michael Goddard "Developing a Javascript Game Engine"
using component based architecture. Takes an indepth look at events/promises and loading content.

Mike Dailly / YoYo investigates packing textures and command list execution for improving performance in "The Voodoo Art of Dynamic WebGL".

Marc O’Morain / Swrve takes a look at a number of issues (including iOS multitouch) in "Building Browser Based Games Using HTML5".

And rounding up everything else

Caruso Daniel explains the "Forza Motorsport Pipeline". Importing assets into the game.

GuayvJean-Francois investigates sound diffraction and absorption in "Real-time sound propagation".

Mike Lewis presents the challenges of multithreading for MMOs "Managing the Masses".

Sean Ahern looks at building better game engine tools in "It stinks and I don't like it"

Clara Fernández-Vara, Jesper Juul, and Noah Wardrip-Fruin make a case that "Game Education Needs Game History"

Chris Jurney presents his idea "Motion Blobs", a fast and crude kinect data "gesture" system, essentially an extension of the typical 2D approach to 3D. Steps are to calculate motion via background subtraction, filtering (open/close), labeling, and then correlation.

Alexander Lucas explains automated testing at Bioware in "The Automation Trap And How Bioware Engineers Quality"

Alex Mejia looks at camera movement in "Saints Row : The Third real time capture tools".

Scott Philips presents "Designing Over the Top SAINTS ROW: THE THIRD Postmortem", and highlights the importance of pre-visualization and playtesting.

Ron Pieket / Insomniac looks at eliminating downtime in "Developing Imperfect Software" via a 'Structured Binary' approach to building engine data by taking advantage of a Data Definition Language.

Benson Russell takes a look at Naughty Dog's approach to polish in "The last 10, going from good to awesome", in essence longer alpha and beta tests.

Luke Muscat takes a look at the lessons learnt while updating Fruit Ninja in "Iterating Design And Fighting Fires: Updating Fruit Ninja And Jetpack Joyride"

Tatyana Dyshlova talks about managing 300+ artists working on 500 car models in "Racing to the Finish"

Summary
Quite a collection this year, but overall seems to be less exciting content than previous years. For graphics, it seems that signed distance fields and physically based rendering is the new theme, AI is still playing catchup and character animation cycles are still a hot topic, following that theme, physics is also looking at characters and ragdolls, with destruction being the hot topic, and the web is focusing on WebGL.

Elastic Band - Realtime pathfinding deformation

I've covered global path planners before including A* path planning and Dijkstra. These path planners will give you a result, but if something alters the desired path (such as an object crosses the path, which you need to avoid) you need to recompute the whole path again. Algorithms such as D* lite allow efficient re-computation. However, the elastic band method allows the existing path to be used, and just adjusted to handle deformations. Or, more formally, elastic band path planning enables realtime modifications to a precomputed path that consider additional obstacles (or cost functions) not considered during the original paths computation.

Elastic band - Global path in blue, bubbles as colored circles,
 and the red path is the one generated by the elastic band algorithm.

The easiest way to describe it in games terminology is to have an entire path turned into particles that follow boid-like (flocking) rules. The best part, is that since it is essentially based on particles, means that you can re-use code from a particle system or physics engine you may have available. If your from the games background, you can use player/entity interchangeably with my use of the word 'robot'.

The 'elastic band' is a created from a set of 'bubbles'. A bubble contains a radius, a position, the coordinates of the closest obstacle to the bubble and a velocity.

The way it works is that an 'elastic band' is initialised with the partial path from the global path planner. The centre of each bubble is assigned to a point along the global path. (For optimisation purposes, a sparse version of the global path is typically used).

If the elastic band does not contain the robots current position, then the robots present position is inserted, provided it will align with the desired path.

For every bubble in the path we determine the total external and internal forces acting on it, and apply them and create/remove bubbles as necessary.
This is done by:

• Creating a new bubble if the distance to the next bubble is greater than a predefined constant. In effect this constant determines the discretization of the path.
  
• Determining the closest obstacle to the bubble and calculating the radius. This is achieved by using a spatial partitioning algorithm to determine the closest obstacle by its Euclidean distance. The radius is assigned to this distance, limited to a maximum.
  
• Calculating the external repulsion force from the closest obstacle. The magnitude of this force is scaled to be a function of its distance limited by an upper bound, such that closer obstacles exert a greater pressure. (i.e. (max - r) / r )
  
• Calculating the internal cohesion force from the previous and following bubbles in the path. This is simply the sum of the normalised vectors to the previous and following bubbles centres.
  
• Updating the bubble state by applying the forces and velocities to calculate the new bubble position. I used a higher order integrator with hand-tuned dampening terms. In addition, a low pass filter is applied to the position update to reduce the influence of the forces.
  

Finally, bubbles are removed if they are too close to each other. The entire band is then checked for continuity, ensuring that each bubble is greater than the robots size. If this criteria is not fulfilled the robot is halted, as it will not be able to get to its destination without colliding.

The bubble that is a set distance infront of the robot is selected to generate the next trajectory input. The angle between the current bubble and the next bubble is calculated and used to modulate the vehicles desired velocity. This causes the vehicle to reduce its speed when it approaches a sharp turn.

In pseudo-code the algorithm is as follows:

eb[0] = path.start
i = 0
for each point along path
  if dist(eb[i],point)> c
    eb.add(point)

while robot not at path.goal
  for each bubble b in eb
    f_e = b.pos – closestObstacle(b)
    f_i = (b.pos – eb[b.i – 1].pos) + (b.pos – eb[b.i + 1].pos)
    b.integrate(f_e+f_i,b.vel) //update velocity from forces
    b.dampen(b.vel) //filter state
    b.integrate(b.vel,b.pos)
    dist = abs(b.pos – eb[b.i + 1].pos)
    if dist > c
      eb.add(midpoint(b,eb[b.i+1]))
    if dist < c_min
       eb.remove(b)
  tmp_goal = eb.closestbubble(path.robot + lookahead) //set goal from robot position
  set robot trajectory to tmp_goal

Thanks to Sushil who did all the hard work in implementing this for MAGIC2010.

GPU and Graphics catchup post

It has been a long while since I've done a graphics related post, so here is a bit of a backlog from the last few months of graphics and GPU links:

• Doom 3 source code
  
• Kevin Karsh's work on rendering objects into photos is definitely worth a look if you haven't already seen it.
  
• GTK now supports a HTML5 target.
  
• PowerVR have a great collection of articles, a nice resource to add alongside nVidia and AMD's developer zones.
• OpenCL 1.2 was released.
• Sfera an open source OpenCL realtime pathtracing game
• A great projection onto a building facade in Berlin.
  
• WebCL has been making good progress. Nokia released a WebCL plugin.
  
• Epic Games posted a nice long video of the work involved in creating content for Gears of War.
  
• Fixstars released a short OpenCL programming book
• Content for CMU Graphics and Imaging Architectures have been released.
• Javascript info toolkit makes awesome visualizations of charts, graphs, and trees.
• Progress is being made to run OpenCL on a FPGA by Altera.
• Xnormal creates normal maps, and now supports OpenRL.
• A nice tutorial on generating texture maps with noise using shaders.
• Disney's open source collection has been updated - uv-less texture mapping, scripting/server tools, particle file formats, and the Dynamica Maya plug-in for the Bullet physics engine.
• Intel SPMD v1.1 parallel compiler was released.
• Intel's OpenCL SDK has seen a number of updates.
• Intel Cilk is a new parallel extension for C++.
  
• Cuda performance primitives has reached release 2.0
  
• Adarapi lets you write OpenCL with Java.
  
• A nice description of the GIF file format
• A new release of ShaderMinifier to help reduce your shader file size.
• GL intercept is a nifty tool that logs all your applications OpenGL calls.
  
• PARSE research group have a number of interesting GPU image processing projects, including Hough Transforms and Speed Sign Detection.
  
• TideArt has interesting graphics related articles and tutorials.

Finally, I'll leave you with a fantastic 64kb demo by Fairlight and Alcatraz that placed 2nd at Assembly 2011.

Civilization 5 - Casual/fast game mod for Apple Mac OSX

I rarely have enough spare time these days to be able to play a game, let alone identify a block of time large enough to dedicate to a game like Civilization 5 - which can take up to 12 hours to play a fast game. So I decided to create a mod for Civ 5 that would significantly speed up gameplay and enable a game to be completed in a few hours.

Modding the game isn't directly supported under OSX, however it can be done.

First, edit MainMenu.lua, located in:

~/Library/Application Support/Steam/SteamApps/common/sid meier's civilization v/Assets/UI/FrontEnd

Comment the following line: (add a '--' to the start)

Controls.ModsButton:SetHide( true );

Copy a mod you have downloaded into the:

~/Documents/Aspyr/Sid Meier's Civilization 5/MODS

directory.

You will need to unzip/extract them before they will work.
If it is a civ5mod file, simply rename it to .7z, and you can use StuffitExpander or any similar tool to extract the folder.

Start Civ5, and you should see a 'MOD' option on the menu.

Creating your own mods is easy enough if you know how. Armed with a decent text editor and the console you can create mods under OSX. Begin by reading Dale's explanation of modinfo files. Next, the 2K games Civilization 5 wiki is a good place to visit, in particular the Civ 5 XML reference guide. Finally, the civfanatics modders guide provides an excellent overview of creating a mod.

You can use the command line 'md5' program to generate the MD5 hashes required for the modinfo file. (And online lower-to-uppercase conversion)

You can download my simple casual gaming mod for Civilization 5 here. It replaces the standard 'quick' game. At the beginning of the game, you will find most things only take one turn to complete. Things will start to settle down quickly though in classical times.

Kinect and OpenKinect on Apple Mac OSX

Adrian, in Kinect-3D!

The Kinect is a revolutionary sensor for robotics - the low price point has seen an explosion of interest and applications in this field. (Hopefully we will see the same for the Neato XV11 low cost laser scanner one day). I was very impressed by the data the Kinect returned, it is a fantastic device.

To get started, just follow the OSX install instructions at OpenKinect. You will need MacPorts. A copy of the instructions is here:

sudo port install git-core
sudo port install libtool
sudo port install libusb-devel
git clone https://github.com/OpenKinect/libfreenect.git
cd libfreenect
mkdir build
cd build
ccmake ..
cmake ..
make
sudo make install

(Press 'g' to generate your cmake make files). Very simple.

Now check under system profiler to see that the Kinect device is detected.

I had the following error when I tried to read from the device:

Isochronous transfer error: 1 

Thankfully, this was easy to solve with a fully self-contained installer from AS3 kinect OSX download package. You should now be able to read the color image, depth map, and command the servo.

The next step will likely be to interpret the data in some form. The Point Cloud Library will be very useful for processing the data. A tutorial on Point Cloud Library is available, although many features are breezed over.

But to begin with PCL, you will need Eigen, a fast vector and matrix math library. (Also used in MRPT)
First download Eigen, and unzip it. Building Eigen is quite straight forward:

cd eigen-eigen-3.0.1
mkdir build
cd build/
cmake ../
sudo make install

PCL has a self installing package, and will install itself to /usr/local/lib/libpcl_*
Here is a simple test program from the tutorial:

#include

#include "pcl/io/pcd_io.h" 

#include "pcl/point_types.h" 

int main (int argc, char** argv) { 

    pcl::PointCloud cloud; 

    //Fill the cloud data 

    cloud.width = 5; 

    cloud.height = 1; 

    cloud.is_dense = false; 

    cloud.points.resize(cloud.width * cloud.height); 

    

    for (size_t i = 0; i < cloud.points.size(); ++i) { 

        cloud.points[i].x = 1024 * rand() / (RAND_MAX + 1.0); 

        cloud.points[i].y = 1024 * rand() / (RAND_MAX + 1.0); 

        cloud.points[i].z = 1024 * rand() / (RAND_MAX + 1.0); 

    } 

    

    pcl::io::savePCDFileASCII("test_pcd.pcd", cloud); 

    std::cerr << "Saved " << cloud.points.size () << " data points to test_pcd.pcd. " << std::endl; 

    

    for (size_t i = 0; i < cloud.points.size(); ++i) 

        std::cerr << "    " << cloud.points[i].x << " " << cloud.points[i].y << " " << cloud.points[i].z << std::endl; 

    

    return(0); 

} 

This can be compiled directly with:

g++ pcd_write.cpp -c -I /usr/local/include/pcl-1.0/ -I /usr/local/include/eigen3/ 
g++ pcd_write.o /usr/local/lib/libpcl_io.dylib 

Finally, attached is a youtube video showing some very impressive visual SLAM surface reconstruction with the Kinect (See KinectFusion project page).

Of course, you will probably want some image stabilization technology to get smooth input videos, so why not try an Owl?


Happy Hacking!

Communications and Messaging Frameworks

A common problem for any distributed software project is handling inter process communications and messaging. Luckily, a number of frameworks already exist to solve this issue. Robotics projects tend to have a range of requirements, from providing a higher level cognitive architecture framework (typically a set of interacting components or nodes) to low-level realtime communications (e.g. CANbus, RT ethernet).

Some robotics packages already provide a particular architecture, such as ImprovCV and ROS which are both filter based, or MRPT which provides some IPC primitives. However, this problem is hardly limited to robotics and many real time distributed networking/processing systems have similar communications requirements. (e.g. computer games, or traffic management systems / plant control systems).

The communications frameworks can be broadly grouped into three categories:

1. Integrated middlewear for a larger package
   
2. (hard) Real time control orientated frameworks
   
3. (soft) Real time messaging libraries
   

From a games perspective, the people at second life have a nice evaluation of several messaging systems. Beginning with soft real time messaging, some interesting libraries include:

• Google protocol buffers, for serialisation. I mention it, because it is popular.
  
• MessagePack is a language agnostic message serialisation system similar to Google protocol buffers - just faster and better.
  
• CORBA allows objects to be sent around a network, often used in business applications. It is an open standard and language agnostic as it includes an Interface Definition Language to define components.
  
• Microsoft DCOM / .NET remote and its many variants are similar to CORBA, just the Microsoft variant.
  
• Apache ActiveMQ another enterprise orientated message broker with support for a large number of scripting languages (Python, PHP, Ruby, Perl, etc).
  
• RakNet manages distributed objects, primarily targeted towards computer games (used in Unity).
  


• Open Torque Networking Library has its origins in the Torque game engine designed for massively multiplayer games.
  


• YAMI4 is a fairly advanced but easy to use peer to peer messaging framework for control systems that is easy to extend to a pub/sub system. POSIX, Windows, Java, C++, well worth a look.
  


• 0MQ, zero MQ is a messaging system that is socket based, and also has pub/sub extensions.
  


• Socket.IO hardly qualifies for a framework, but is a great enabler for realtime HTML communications, so it certainly deserves a mention.
  

there are many more networking libraries available, but these are the ones that stand out for this category. For hard real-time control tasks the choices are a bit more limited, however libraries of note are:

• Real time CORBA, is CORBA modified to be a bit more lightweight and able to support real time requirements. TAO ACE is worth looking into if your following this path.
  
• Data Distribution Service (DDS) is similar to Real time CORBA, however it has the advantage of lessons learnt from CORBA and provides simpler fine grained control over quality of service and intelligent networking. RTI DDS is the framework we used for the WAMbot TARDEC/DSTO MAGIC 2010 project. OpenDDS is an open source implementation.
  
• Real time data base (RTDB) is an open source framework that provides a lower-level communications interface for C/C++ over Xenomai. This is the framework we used for the Team Annieway entry to the DARPA Urban Challenge.
  
• LCM is a socket-based IPC library used by Team Michigan for MAGIC 2010.
  
• IPC a low level inter process communications system for embedded systems used by NASA.
  
• Dynamic Data eXchange (DDX) is a large open source distributed software architecture developed by CSIRO and has been previously integrated with ROS.
  

Finally, there are a number of application specific frameworks, for Robotics this includes ROS, MS Robot Studio, Player/Stage, JAUS and more general packages such as Labview and Matlab. I think it is prudent for every software developer to be familiar with at least three tiers of communications frameworks, from large scale frameworks (e.g. CORBA) to light-weight frameworks (e.g. RackNet) to low-level frameworks (e.g. Socket.IO). Ideally, one for each key application area (e.g. Hard real time, Soft real time, Business applications, Web).

Half year catchup on Graphics, GPUs, Compilers, etc.

Another slow month on the blog. More than half way through the year, so its time to catch up on the backlog of news. Only covering graphics, games, physics and GPGPU and compilers. Expect a number of posts on robotics soon!

• GitHub is now more popular than SourceForge.
  
• Fabian 'ryg' Giesen has put together an in-depth explanation of the graphics hardware pipeline.
  
• nVidia released an extension to allow OpenGL direct access to DirectX buffers. Now you can write your graphics programs in both OpenGL and DirectX - pick whichever is easiest.
  
• nVidia released their 11th Graphics SDK - DirectX 11 only.
  
• Aras did a blog post on visualising mip-map levels and released the code to his shader.
  
• Redirect OpenGL from a remote machine with this VirtualGL tutorial.
  
• Morphological Anti-Aliasing paper with source code.
  
• Tim Lottes released his FXAA anti-aliasing source code
  
• José María Méndez wrote a fantastic article on a simple method to implement screen space ambient occlusion.
  
• Improve your ambient occlusion with occlusion normals to enable dynamic shading.
  
• A simple GLSLShader handling class
  
• Dave has a post on how you can generate game characters with a webcam.
  
• Source code from the Game Development Tools book. From texture generation and CSG to Continuous Integration, Perforce and XML.
  
• Steven Wittens has a fantastic series of posts on procedurally generating planets and worlds.
  
• Amit's blog post on polygon map generation using Voroni and Delaunay is worth a read.
  
• The old gameUltima 6 technical documents have been released. An interesting look at game design and programming decisions made in 1990. This should help nuvie, which has already made great progress.
  
• Oldskool demoscener Trixter wrote an interesting post onC64 vs IBM PC, and argues the C64 was a faster computer.
  
• Democoder Ferris/YUP did an interesting post on
  creating a tiny 1k graphics demo.
  
• John Ratcliff updated his Hierarchical Approximate Convex Decomposition utility library.
  
• Tim Ventimiglia and Kevin Wayne did an interesting post onusing the Barnes-Hut algorithm to accelerate n-body simulations.
  
• Pierre Terdiman has a great post on fast separating axis tests to speed up your collision detection for convex objects.
  
• PhysBAM source code - there is plenty of great stuff in here, so I'm sure to do a whole blog post on this later. It covers maths (e.g. ODEs, fourier transforms), spatial subdivision (KD trees, octrees), collision detection, raytracing and so much more.
  
• OpenCloth is a new library for cloth simulation algorithms.
  
• nVidia APEX SDK is now free. It has a number of functions that help with clothing and destruction physics.
  
• PhysxLab is a digital content creation tool to help you take advantage of the APEX sdk destruction features.
  
• The Oren Game Engine blog has a great post onimplementing destruction fractures.
  
• A realtime raytracer with pure C++, OpenMP and CUDA written by Thanassis Tsiodras is accompanied by some interesting analysis.
  
• Microsoft Accelerated Massive Parallelism (C++ AMP) appears to be the microsoft attempt at competing with CUDA, OpenCL and some of the libraries ontop of those technologies.
  
• Microsoft also released concurrent containers, parallel versions of STL algorithms.
  
• WebCL - OpenCL for the web, at Nokia research.
  
• AMD's OpenCL University kit covers some OpenCL and GPU basics.
  
• AMD Accelerated Parallel Processing (APP) SDK (formerly ATI Stream) has had a few updates, currently 2.4 is out.
  
• AMD gDEBugger is now free for debugging OpenGL and OpenCL programs.
  
• Intel SPMD Program Compiler is designed to generate optimal SIMD programs from a C-like language.
  
• PathScale EKOPath 4 is an optimising compiler, now free for linux, BSD and Solaris.
  
• Yang Chen wrote an amazing post comparing compiler optimizations.
  
• Helpful hints on the unix command xargs
  
• FreeArc is an amazing open source compressor. Fast and fantastic compression ratios.
  
• Google's excellent diff/match/patch tools
  
• Visual hashing explained, how to detect similar images.
  
• Ocropus is a open source library for Optical Character Recognition (OCR).
  

Finally, here is the SIGGRAPH 2011 technical papers highlights video, it contains a number of interesting advances in physics simulations and modeling.

March update

I didn't want to have a month without a post, so here are some links for the month:

• GDC 2011 is over again. I'll do a breakdown soon, but meanwhile take a look yourself at DICE publications on Battlefield 3, nVidia's GDC publications, AMD GDC and ofcourse the official GDC vault (free). (Maciej Sinilo has a nice collection here).
  
• Game Physics Pearls has been published by Gino van den Bergen and Dirk Gregorius. Dirk is a very knowledgeable guy, and Gino wrote SOLID, so I'm sure it's great.
  
• ScienceBooksOnline has a collection of free books.
  
• Paul Firth has a great interactive blog post on contact resolution, and introduces a method used in Little Big Planet he calls "Speculative Contacts".
  
• PhysX info has a comparison of different clothing simulation systems.
  
• GLM is an OpenGL syntax math library.
  
• Cairo is a 2D graphics library that supports both OpenGL and PDF output.
  
• An MIT WebGL tutorial.
  
• How to convert your HTML5 page into a native OSX app.
  
• Paul Grenfell added another small raycasting OpenProcessing demo.
  
• Photoshop filters implemented in GLSL
  
• Herwig Hauser has an amazing gallery of 3D algebraic surfaces - useful for 4k productions.
  
• On that topic, Auld has a great snippet on miniature GLSL code for moving a camera.
  
• 0 AD is an open source 'Age of Empires' style game.
  
• Ninite is like apt-get for Windows. (Installation package manager)
  
• A siggraph paper on the miniature effect
  
• Bundler is an open source tool to generate structure from motion from unordered images. (It was published in 2006, but now you can look at the code)
  
• GPU Ocelot 2.0 supports AMD devices now. CUDA for AMD.
  
• Microsoft's paper on the Kinect bodypart tracking algorithm.
  
• Looking for a place to publish? Wiki Call for Papers collects conference paper submission deadlines and more. (Neat!)
  

The pick of the month has to be the new Festo production, the SmartBird ornithopter. (Official site has a PDF spec-sheet). Video below:

Humble Bundle #2 - Great indy games - name your price!

Osmos - Humble Bundle 2

The independent games humble bundle offer is back again, better than before. It is a pay-what-you-want offer for 5 indy games, all of which have support for Windows, Mac OSX and Linux. If you pay above the average, you get the previous humble-bundle pack of 6 games as well! A very good deal for whatever you want to pay! (Makes an excellent Christmas present!) Anyone studying games design or games programming should get these games to learn from them - what works, what doesn't? Braid is a fabulous example of teaching the player the game without needing to give them a tutorial, and many of these games are great examples of the scope you should aim for if you are making your own game.

The games included are:

• Braid - a side scrolling puzzle/adventure through time. Nicely designed gameplay.
  
• Cortex Command - side scroller, not very impressive.
  
• Machinarium - a point and click adventure game, nice graphics, pretty decent.
  
• Osmos - an ambient physics-based "eating" game (you absorb smaller entities). Good gameplay and a great "programmer-game" (nice graphics). My pick of the lot. (only $10 separately)
  
• Revenge of the Titans - a tower-defense (build towers that destroy enemies) game. Nothing special.
  

The other games are:

• World of Goo - a construction puzzle game. Lots of fun.
  
• Aquaria - an underwater fantasy game.
  
• Gish - a platform game.
  
• Lugaru - 3D action adventure game.
  
• Penumbrac - a FPS/adventure game.
  
• Samorost 2 - a flash-based puzzle game.
  

If you pay 10 USD to get them all, that works out to less than a dollar a game, and I guarantee you will find at least one game you think is worth $10 in the humble (cross-platform games) bundle.

Convex Hull Generation in Blender

Convex hulls are very useful for a number of optimized calculations such as fast intersection tests, fast spatial subdivision, and other early-out's used in computer graphics, computational physics and robotics.

When I implemented convex hull generation and convex decomposition in PAL I first used qhull and leveraged code from tokamak physics, but then used code by Stan Melax and John Ratcliff for PAL. Recently my work at Transmin has required generation of a number of Convex hulls, and so I combined these snippets of old code to create a plug-in for Blender.

The Blender plugin creates a bounding convex hull of the selected object.
It calls an external executable 'convex' which creates a convex hull based on an intermediate OBJ file.

Installing the plugin requires you to compile the code to generate the 'convex' executable, and copying the python code into Blender's scripts directory.

To compile the C code on linux/osx:

g++ createhull.cpp hull.cpp -o convex

Place the object_boundinghull.py script in your ".blender/scripts" directory.

On OSX Blender default installs to:

/Applications/blender-2.49b-OSX-10.5-py2.5-intel/blender.app/Contents/MacOS

Once the plugin is installed you can start creating convex hulls. You can select an object in blender and cut it into smaller objects to manually decompose the hulls. To do this, you can use the Knife tool (K) or split objects in edit-mode with 'P'. (Selection tools like 'B' and manual alignment of cameras ('N', Numpad 5) will help a lot).

Once you have the objects you would like to generate hulls for select one, and run the "Bounding Convex Hull" script. It will ask you to confirm the creation of the hull. The new hull will have the same name as the original object and have ".hull" appended to its name.

The plugin will generate a new object that represents the convex hull of the selected object, with the same transforms as the original object. (Ctrl-A to apply all down to the mesh, note: Blender 2.49 does not let you apply translation transforms, but Blender 2.5+ does). You can then decimate the hull to reduced the number of tri's used to represent your object. (Editing F9, under modifiers, select 'Add Modifier', decimate, and reduce the ratio).

Now your ready to export your scene for all your raytracing and collision detection needs!

Thanks to Transmin Pty Ltd for allowing me to release this plugin back to the Blender community under the GPL.

Follow the link to download the Blender Bounding Convex Hull plugin to generate editable bounding volumes directly in Blender.

SIGGRAPH 2010 Course Papers Overview

I've managed to work through the SIGGRAPH 2010 course content that relates to realtime rendering. I quite liked the Toy Story 3 rendering techniques and realtime rendering survey by nVidia- just because they give a nice overview. As always, there are a number of great presentations, and I've listed the ones that I found interesting below.

• Toy Story 3 : The Video Game Rendering Techniques from Avalanche Software gives a great (211 page!) overview of a number of lighting issues for the game including SSAO (various optimizations/approximations for how/where to sample, faking more samples and dealing with large differences in depth), ambient lighting (without needing to bake it or do GI) and various aspects on shadows. A great read!
  
• Surveying Real-Time Rendering Algorithms by David Luebke from nVidia gives an excellent short overview of a number of recent developments in realtime rendering algorithms including stochastic transparency (ie : transparency via random sampling), sample distribution for shadow maps (partitioning the scene in light-space), alias-free shadow maps, append-consume order-independent-transparency (sorting per-pixel & linked-lists), progressive photon mapping, image-space photon mapping, ambient occlusion volumes (how to speed it up with bitwise occlusion mask for each triangle - one per edge, and one for the triangle plane), stochastic rasterization (of 4d triangles)
  
• Keeping Many Cores Busy: Scheduling the Graphics Pipeline by Jonathan Ragan-Kelly from MIT gives a great overview of the graphics pipeline stages (from Input Assembler, Vertex Shader, Primitive Assembler, Tesselation, Geometry Shader, Rasterizer, Pixel Shader, and finally Output Blending) and load balancing.
  
• Uncharted 2 - Character Lighting and Shading by John Hable from Naughty Dog gives a fabulous overview of rendering issues with skin (in a lot of detail!), hair and clothes.
  
• Bending the Graphics Pipeline by Johan Andersson from DICE describes tile-based deferred shading (for GPU and SPU), morphological antialiasing and analytical ambient occlusion.
  
• A real-time Radiosity Architecture for Video Games by Sam Martin and Per Einarsson from DICE/Geomerics introduce the 'Enlighten' system for realtime GI - it gives a nice overview.
  
• Evolving the Direct3D Pipeline for Real-­time Micropolygon Rendering by Kayvon Fatahalian from Stanford University gives an interesting insight on Micropolygon rendering on current GPU pipelines.
  
• Water Flow in Portal 2 by Alex Vlachos - I've already written about this previously, just another realtime technique for faking the simulation and rendering of water flow.
  

• Making Concept Real For Borderlands by Gearbox Software contains some nice examples of their concept art, the development change from photorealistic to stylistic rendering and art (and the code/artist balance), and the sobel edge filter they used.
  
• The notes from the volumetric course was broken into parts:
  
  
  1. "Resolution Independent Volumes" - which describes the "Field Expression Language Toolkit", cloud modelling (via density displacement), morphing objects (by using the Nacelle Algorithm to generate warp fields), cutting models, fluid dynamics, gridless advection, and semi-lagrangian mapping (balancing between grids and non-grids).
     
  2. "Mantra Volume Rendering" - this describes the volume rendering engine for Houdini.
     
  3. "Volumetric Modeling and Rendering" describes the volumetrics library/API developed at Dreamworks.
     
  4. "Double Negative Renderer B" (used in Batman Begins, Harry Potter, etc.) describes the workflow and various shaders (Fluid, Particle, Voxel, Fire, Smoke) in DNB
     
  5. "Volume Rendering at Sony Pictures Imageworks". The section from Sony Imageworks included an overview of their pipeline and content on their open source field/fluid tools.