Graphics.page

TODO

- phong shading

Basics

- 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
- <http://arstechnica.com/apple/guides/2009/12/intro-to-3d-part-1.ars>
- <http://arstechnica.com/apple/guides/2010/09/an-intro-to-3d-on-the-mac-part-ii-animation-and-rendering.ars>

Definitions

- texel: pixel in a texture

FastInvSqrt

- code:

    float FastInvSqrt(float x) {
      float xhalf = 0.5f * x;
      int i = *(int*)&x;         // evil floating point bit level hacking
      i = 0x5f3759df - (i >> 1);  // what the fuck?
      x = *(float*)&i;
      x = x*(1.5f-(xhalf*x*x));
      return x;
    }

- make first guess, then one iteration of newton's method
- money line: divide exponent by two & flip sign, preserve mantissa, more
- math derivation is actually quite clear
- <http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/>
- <http://blog.quenta.org/2012/09/0x5f3759df.html>

"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

CUDA

- 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

- 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

DirectX

- final `Present()` call draws

Graphics architecture (Angstrom group meeting, jrk@mit.edu, 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
- <http://arstechnica.com/gadgets/guides/2009/12/from-cinepak-to-h265-a-survey-of-video-compression.ars?utm_source=rss&utm_medium=rss&utm_campaign=rss>

real-time ray-tracing software

- openrt: quake 3/4 demo
- Interactive Ray Tracer (IRT) for Cell Broadband Engine
  - <http://www.alphaworks.ibm.com/tech/irt>
- intel: quake wars raytraced <http://www.qwrt.de/>
- industry working on RTRT: intel, nvidia
- nvidia iray runs on GPGPUs

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

opengl

- 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

voxels

- <http://notch.tumblr.com/post/8386977075/its-a-scam>
- engines
  - atomontage
  - <http://voxelstein3d.sourceforge.net/>