• phong shading


  • bitblt: perform boolean operation on same-sized rectangles in two images (src, dst)
  • Bresenham’s algorithm: line-drawing
  • triangulation
    • subdividing surfaces is useful for many things
    • Delaunay triangulation: maximizes angles; yields most-equilateral triangles
  • modeling
    • cage modeling: start with base (“cage”) mesh overlaid on photo/drawing
  • texturing
    • UV mapping: map texture coordinates onto polygons
    • bump maps: simple grayscale mapping to depth
    • normal maps: more info than bump maps; maps RGB spectrum to direction as well
    • displacement maps: game engines can’t use these; they generate true height, thus casting realistic shadows, unlike bump/normal maps which are rendering tricks, but are much more expensive
    • ambient occlusion: attenuates light in crevices/between objects; key to photorealism; aka “dirt maps” bc looks like dirt
      • expensive and only in advanced engines; often “baked in” to textures
  • rigging
    • joints
    • IK handles
    • skin vertex weights: paint relationship btwn skin & bone
    • wire controllers: simple NURBS surfaces that give you control over joints
  • dynamics solvers/physics engines: fields and forces, soft-/rigid-body collisions
    • hard to parallelize
    • game-oriented solvers (physx, havok) not accurate enough for film
    • bullet physics: FLOSS, fast, handles soft/rigid/cloth
  • shading/rendering


  • texel: pixel in a texture


“Post-processing” techniques

  • anti-aliasing: techniques include hyper sampling, subdividing pixels, random sampling, …
    • “2X AA” means supersample at twice the display resolution
  • texture filtering: blend texels for smoothing, eg when scaling/misaligned
    • cheap approx to anti-aliasing
    • betterness: anisotropic > trilinear > bilinear > nearest-neighbor with mipmapping > nearest-neighbor
      • bilinear: blur pixels; smooth, soft
      • trilinear: blur mipmaps
      • anisotropic: make mipmaps of diff ratios
  • mipmapping: technique to save some filtering
    • when minifying textures, may need to combine many texels
    • so, prefilter at smaller sizes

interpolation/resampling (merge with above)

  • for filtering/resizing images
  • bilinear: linear interpolation along one axis between two pairs of corners to get two points, then along the other between the two points to get final point
  • Lanczos: sharper

GPU programming

  • pixel shaders, cuda are examples of things that compile to gpu bytecode
    • before gpgpu langs, devs had to pack data into triangles/textures
  • pixel shaders: typically for lighting and effects; eg solar flares
  • high-level shading languages (HLSLs)
    • OpenGL GLSL: based on C
    • NVIDIA Cg
    • D3D10 HLSL: very similar to Cg, analogous to GLSL; vertex shaders, geom shaders, pixel (or fragment) shaders
    • D3D11 “compute shaders”: platform-indep
  • GPGPU langs
    • OpenCL: cross-platform
    • CUDA: nvidia only
  • gpu bytecode is card-indep; cards from same mfr can have different ISAs
  • gpu instrs are very SIMD; slow branches; produces machine code


  • gives you ‘threads’
  • but real way to get any speedup is to have all threads executing same instr at same time (simd)
  • gpu’s have very predictable cycle counts
  • up to dev to keep threads in step


  • opengl has a mode where you can disable the perspective frustum
    • useful for 2D games; TODO why single 3D plane insufficient?
  • textures, triangles reside in video mem
  • textures are mapped/interpolated onto surfaces
  • use 4D linear transformations for non-linear xforms in 3D (eg translations)

OpenGL Software

  • GLU: OpenGL Utility Library
  • GLUT: OpenGL Utility Toolkit; unmaintained, restrictive license
  • freeglut: OSS clone of the original GLUT
  • openglut: fork of freeglut that adds some more functionality
  • SDL: takes care of opengl init
  • GLUI: OpenGL User Interface Library

Windows Graphics APIs

  • user32.dll does all window/menu/etc. drawing on top of GDI
  • Graphics Device Interface (GDI): old Windows API for drawing lines/curves, rendering fonts, handling palettes
    • can’t animate: no synchronizing framebuffers
    • can’t rasterize for 3D
    • no direct app-HW access but higher abstraction; easy to draw on multiple devices
    • GDI+: C++-based; anti-aliasing; FP coords; gradient shading; more complex path mgmt; intrinsic file format (jgp/gif) support; affine xforms of 2D view pipeline
  • desktop window manager (DWM): compositing engine added in vista
    • runs on D3D
    • runs GDI, GDI+; GDI no longer HW-accel’d; GDI now software-rendered legacy
    • GDI: apps paint to system memory surface; copied to video memory surface in DX pixel fmt on compositor’s schedule
    • DX: call Present() when done
  • Direct3D: basically the GPU API (“immediate mode graphics API”)
    • fills in holes that HW is missing with software
  • Direct2D: added in Win7; to render geometries, bmps, text directly atop D3D
    • less capabilities than gdi and wpf
    • also: remote rendering over RDP; SW fallback for server-side rendering/lack of HW; cleartype
    • native api and .net wrapper
  • DirectWrite: complements D2D; HW-accel’d text; text layout/rendering; typography; works with any other drawing api
  • handle can be passed to various GDI functions
  • WPF: aka avalon; .net api; uses milcore.dll (dx)
    • xaml tree sent to wpf rendering thread; app then sends tree updates
  • old gdi: paint directly to drawn buffer
  • compositing window mgr: paint to own buffer; DWM composes these
    • redraw elsewhere/in other ways
    • tear-free experience (dx “flip”)
    • no re-draw’s to background apps (window trails, blank spaces)
    • windows are drawn as textures; borderglass blur done via pixel shaders
    • not .net but like wpf in using milcore.dll (dx)
  • WDDM: new dx driver model in vista
    • virtualizes video mem: backed by main mem, then disk
    • allows interruptibility of GPU
    • allows dx surfaces to be shared across processes


  • final Present() call draws

Graphics architecture (Angstrom group meeting,, 4/24/08)

  • raytracing vs rasterization
    • rasterization is best suit for doing primary visibility (calculating what’s visible)
    • raytracing good for calculating scene lighting?
  • IO bandwidth: 50% texture input, 50% read-modify-write framebuffer, negligible scene input
  • arbitrarily large amt of computation: color on each pixel, anti-aliasing
  • most money in game production goes into art
    • artists mostly work with photos and Photoshop
    • cost doubles every 2-3 years
    • much more expensive than hardware
    • no/very little procedural content generation
    • programmers more expensive than artists, and more effort to produce content-generating algos
    • exceptions: Spore
  • graphics pipelines: how long are they?
    • “Graphics Pipeline”: directx and what points where you get to insert your functions and what are fixed
    • easily come up with 100 pipeline stages for parallelism
  • (geometry, textures) -> many vertex -> 1 rasterization -> many fragmentation -> some framebuffer
  • general-purpose data-parallel cores for graphics (Intel’s architecture) is the future
  • locality easy to achieve
  • NVIDIA CUDA lets you program more generally for GPUs
    • used to bend over backwards by reducing problem to triangles and quads
    • similar to Cell
    • DX11 has general-purposes shader
  • Cell is painful
  • abstract model: asynchronous dataflow with kernels and queues
  • paper on same stuff from Sequoia folks

video compression

  • early codecs: intel indeo, motion jpeg, mpeg-1
    • cinepak: QT and WMV; aimed at <320x240 on CDROM, or 2.2Mbps on 1.2Mbps stream (50%)
  • MPEG-2: much better than early codecs; 1:30 compression; full-res NTSC on CDROM at 1Mbps; 1080p at 2Mbps, but with bad blocking artifacts
    • encoding is easy for recent OMAP CPUs and intel/amd CPUs; that’s why tivo still records in MPEG-2
    • real-time decoding is do-able for GHz CPUs at smaller resolutions
  • MPEG-4 part 2: half MPEG-2 bandwidth; decoding requires video card, done by portable players
    • impls: xvid, divx, 3ivx, QT6
  • H.264 aka MPEG-4 part 10 aka advanced video codec (AVC)
    • 4x MPEG-4/2; bcast-quality std def at 1.5Mbps; squeeze HD into DVD; VHS-quality video at 600Kbps
    • in blu-ray, itunes video store, youtube HD
    • 2003 ATSC bcast std, wrapped in MPEG-2 container
    • no cable/satellite impls; requires beefier set-top boxes; directv, dish are equipping satellites with support
  • H.265: still in dev

real-time ray-tracing software

raytracing vs rasterization

  • rasterization: each triangle is independently analyzed, plotted, colored, lighted, textured, painted
    • linear in # triangles; sublinear with z/depth culling, hierarchical culling
    • but most effects require access to 2+ triangles
    • requires complex shader programming to get eg shadows to look right
    • eg reflection maps instead of real reflection; assumes fixed environ
    • uses z-buffer or scanline algos
  • raytracing: model rays of light passing from each pixel into camera
    • indep of scene size
    • abstracts geometry into trees
    • very parallelizable
    • long list of advantages over rasterization
  • both can harness GPU, but specialized for rasterization today
    • rasterization-specific HW is <5% GPU core area
    • but overall architecture must also lend itself better to raytracing

raytracing features

  • ambient occlusion
  • radiosity
  • reflections, refractions, shadows (softened)

raytracing techniques

  • photon-mapping


  • pipeline
    • fixed-function pipeline
    • programmable pipeline: for shaders
  • shaders
    • vertex shader: modify vertex before use in actual surface calc
    • pixel shader: modify pixel before writing to output; more interesting
  • steps
    • construct shapes from primitives: pts, lines, polygons, imgs, or bmps
    • arrange objs in 3D space; select vantage pt
    • calc colors from app assignments, lighting, textures; via shaders or FFP
    • rasterization: convert math descrip of objs & color info to pixels