Maths and Tech Cheat Sheet (DRAFT) by Jonathan_Walsh1999

A quaternion is a 4 element vector that can used to encode any rotation in a 3D coordinate system.

q = (w, v) = (cos(t­het­a/2), sing(t­het­a/2)r)

r and theta form an axis-angle rotation.

Quater­nions only use 4 floats, 12 less then 4x4 matrices.

They lack hardware support, therefore they need to be converted from matrices to them and back to matrices again.

Quaternion can be converted to a matrix

1st row - Mq = [1-2y² - 2z² 2xy+2wz 2xz - 2wy 0]

3rd row - Mq = [2xz + 2wy 2yz - 2wx 1-2x² - 2y² 0]

Multiply result by 1/w² + x² + y² + z² if q is not normalised

Addition: (w1, x1, y1, z1) + (w2, x2, y2, z2) = (w1 + w2, x1 + x2, y1 + y2, z1 + z2)

This is potent­ially much faster than matrix multip­lic­ation

Inverse of quaternion where rotation is in the opposite direction.

Quaternion must be normalised before formula is used

Vector can be repres­ented as quater­nions. Set w to 0

Rotate q (p) = q^-1pq = (2w² - 1)p + 2(v . p)v + 2w(v X p)

Slower than matrix equivalent

Quater­nions can perfrom similar operations to matrices with comparable perfor­mance although you need to convert to/from matrices and they can't store positi­oni­ng/­scaling

Screen res/re­fresh rates

Anti-a­liasing

DX 10+ define min spec

Consoles are largely unaffected by such matters as specs are fixed unlike PCs

Shaders complied to machine code

Higher shader versions have more instru­ctions like for and if

Should provide alternate shaders for high and low spec machines

So that one texture can be rendered through different shaders adding multiple postpr­oce­ssing effects for example

Provide a range of techniques for different hardware specif­ica­tions

The DX effects files system makes this quite simple. Example shown in lecture slides

Like vertex shader but works with multiple vertices at the same time

Can also create or delete primitives ie output can be different to input

Output: Stream of primitives - Must be specified as a triangle strip for example. Can output any number of primit­ives. Example shown on lecture slides

Silhou­ettes

Particle systems without instancing

Perfor­mance of geomtry shaders may be an issue for older GPUs

Very powerful DX 11 feature

Cannot ouput to same buffer that is being input from

Often need multiple passes to render­/update geometry

Instancing is a method to render many models or sprites in a single API draw call

Send a list of instances with the vertex and index data

Removes per-model state changes

Instance data stored on GPU is instance buffer

Model defines by verter­x/index data rendered once at each psoition in this buffer

VS often unusual when instan­cing, depending on what is stored in the instance buffer

Can store more than just position in an instance buffer to give each instance a different look: Rotation, scale or store entire world matrix per-in­stance

Simple instancing is processes using both CPU and GPU. GPU render instances and UPU update instances

Space is reserved forr instance data in both CPU and GPU memory

This is why we might not want to store a world matrix for each instance. Instead the data is often compressed

Instancing suits the rendering of large numbers of similar models. ie trees, armies

Particle systems are an ideal condidate for instancing

Each particle requires data to update its positi­on/­rot­ation each frame

Particles have a life time after which they die

Approach: Store render data in instance buffer, store update data, update particles using CPU and then copy entire buffer to GPU, render particles in one vatch using instan­cing, much faster but still requires CPU/GPU copy

Instancing can look poor due to lack of variety

Able to render models in different poses, with differ­ent­tex­tures and material tweaks. Good for vegeta­tion, crowds etc.

LAtest GPUs deal well with this kind of shader

One simple workaround is to avoid updates.

DX 10 supports stream output. Allows GPU to output vertex data back into a vertex buffer instead of sending it on for rendering.

Both render and update data is stored GPU only

Reads from GPU buffer and writes back to one but can't output to same buffer that is being input from. Work around this by double buffering

Works expecially well with the sprite­-based particles technique

DX 11 was introduced with Win7

Nearly everything DX10 works with minimal change in DX11

.fx not in the provided libraries

No font support

Get two progra­mmable stage: hull and domain shaders

All three must be used to gether for tessel­lation otherwise disabled

Vertex shader processes each control point

Hull shader has an associated patch constant function which is called once per patch

Domain shader takes the generic tessel­lation and control points and creates the final vertices

DX does not specify the available patch types

Gets access to all control points for a single patch and can [rpcess them in any way

Can be used for advanced purposes like approx­imating complex input splines using simpler output splines. providing per control point info to help the patch constant

Access input control points and the hull shader output control points as array to do its job

Divides up a unit square, triangle or line based on the factors

Several fixed algorithms are avaliable for the tessel­lation

Combine to create final tessel­lation for the scene

Common to vary amount of tessel­lation based on the geometry distance

Density variation needs pre-pr­oce­ssing

That is why we can control the edge tessel­lation separately to ensure all edges have the same tessel­lation factor.

Effect­ively this parallax mapping done properly

Tessel­lation has perfor­mance implic­ations

Models must be designed with displa­cement in mind

Number of depth cues in a 2D image/­video

Known sizes of objects

Motion Parallax

Occlusion - nearer objects hide further ones

None of these require 2 eyes just moncular vision

Image in each eye is different

Interp­olation is where a calcul­ation is made to decipher a transform between 2 control transf­orm­ations of a model

In order to get the frames in between the key frames, interp­olation is used

P(t) = P0(1-t) + P1t

The interp­olated point will be on a straight line in between P0 and P1, hence linear interp­olation

Can use Linear Interp­olation for transf­orm­ations including transl­ations, scaling and rotations, however, the results for rotations is not correct, resulting in unwanted scaling. Therefore, Nlerp or normalised Lerp is required for rotation.

Forumla different from linear interp­olation (Lerp)

More suited for larger rotation as it calculates the correct interp­olated rotation

This is very expensive

Quaternion formula: slerp(P1, P2, t) = (sin((­1-5­)th­eta)P1 + sin(t theta) P2) / sin(theta)

Can use Lerp for positi­oning and scaling

For larger rotations use Slerp

Matrices are not good at animations as they are perfor­mance heavy use far too much storage, so quater­nions should be used instead

is any scheme that divides the game world into smaller spaces

Complex games can contain millions of instances

We would like to cull these instances instead

Check each instance against each of the 6 planes defining the frustum or more simply rejecting those beind the camera near clip plane

Culling instance one-by-one is not the best approach for very complex enviro­nments. There are too many instances to even consider in one frame.

Partitions can be seen as chunks of space and instead identify which partitions are invisible allowing use to accept or reject large groups of instances at once.

One example shows a very basic partit­ion­/graph demons­trating how areas in the sene are connected and how a group of instances can be reject by one check. (Refer to lecture slides for diagram)

This can help in a variety of non-re­ndering situat­ions.

Space partitions can also help with game logic

These sectors can also simplify lap processing which can include distance covered, teleme­trics or detecting whether you are going the wrong way around a race track.

Each node in a space partition has a potent­ially visible set (PVS)

PVS can be pre-ca­lcu­lated and stored with each node. This indicates which other nodes to render whe in that node.

However, generating the PVS for each node is non-tr­ivial

PVS does not consider dynamic geometry. For exampe if you have a level that has a door which opens then the door must be considered as open for PVS

So whilst efficent to execute, PVS systems are not ideally effective in node rejection.

PVS can be added to any space partition graph regardless of shceme used

A Portal system is a method that concet­rates on the graph edges

Portals allow us to reject other nodes based on the camera view

Identify whether each of the node's portals are visible in the viewport

When a visible portal is found store its viewport dimensions (2D rectangle)

Watch out for multiple portals leading to same nodes. We don't want to render nodes twice.

Effective for indoor geometry

Each portal with 2 sides don't need to be in the same place.

Need to know which node the camera is in to start the algorithm. e.g. what if a camera travels through a wall or teleports?

Not easy to automa­tically generate portals from arbitrary geometry

Can be used to map terrain (Heigh­t/i­nfl­uence maps)

May have many empty nodes, wasting memory, reducing cache efficency

A grid is an integer indexed structure for a rectangle of world space

Conver­sions for X dimension are (Y similar):

GridX = (int)(­Gri­dWidth * (WorldX - MinX) / (MaxX - MinX))

2nd formular gives bottom­-left of grid square

USe specific division scheme

Root node is entire space

Repeat division with each quadrant

Easy to find which node point is in

Can use bitwise integer math

Viewing frustum is 6 planes

Entities aren't points

Entity needs to be in a larger parent node

Hot-spots like this all the way around the boundaries of larger nodes.

Have nodes overlap

Few changes to algorithm - increase node size when inserting entities and when doing frustum culling

At the expense of larger nodes at the same level

Easy to find inters­ection of other primitives - sphere, cuboids, rays etc.

Can help if we add adjacency info to the tree

Partitions are separated by lines in 2D or planes in 3D

Creates a binary tree

Stop when max x elements in each partition. Partitions are small enough. tree reaches certain depth and choice depends on applic­ation

Look at example in lecture slides

BSP splits space into hollow­/solid volumes

Tradit­ional style of BSP used for FPS games

Can also be used to render partitions in a strict back to fron order

+BSP trees are a well establ­ished technique

+Can be generated automa­tically

-Need good algorithm to choose dividing planes

Name for the method of rendering we have used in all material so far

Cost = numObjects x NumLights - Get's very expensive

Doesn't work well with lots of lights in one place

Splits the rendering process into 2 stages

Render geometry to g-buffer, which is several textures holding geometry and surface data

Pixel shader can render to several render targets at the same time, so can build three textures all in one pass with a special pixel shader

Data in g-buffer is anything we need to calculate lit version of the scene

So data compre­ssion in the g-buffer is common ie store x and y of normal together with a single bit for direction

Render actual scene by going through each light and rendering it's effect on the geometry

Same concept for spotlights

Examples shown in lecture

+No need for complex partit­ioning

+Better batching perfor­mance

-Huge g-buffer can be a slow down

-Trans­parant obkects don't work, must be rendered separately

-Not actually partic­ularly useful in some scenes­(da­ylight)

Increased speed might be at the expense of memory

Never optimise code unless you are sure that is affects perfor­mance

Can reduce functi­onality

Need to identify the 10% to optimise effect­ively

-Profiler - Reports on time spent in different functions

Optimi­sations can be enabled using release mode in visual stuido.

-Loop Untrolling - Does not loop through indices, just duplicated lines of code instead

-Change ording of condit­ions, like OR for example. Put simple condition first

-Use early return within functions whenever possible

-Break code into smaller steps. For example, don't have calcul­ations inside if statem­ents. Does not directly lead to optimi­sations but can help compiler optimise.

-Only choose data structures that suit your needs, nothing more

-Can multiple by 0.5 rather than dividing by 2

-Reduce range of loop counters

-Cluster similar cases into one

-Pre-c­alc­ulate formulae using look-up tables

Attractive blending technique but cuases sorting issues

Avoid problem by drawing polygons back to front.

Issues arise with this based on example shown on slides with the lines

Then given 2 polygons one of them will be entirely on one side of the plane of the other

First step is to get a face normal for each polygon

Must ensure this sorting is efficient as possible. so sort pointer to polygon not polygon data itself

Alpha blending is as useful as other blending methods once the polygons are sorted

Partic­uarly large particles like smoke indoors

This method can be combined with the depth particles idea presented earlier

Can explore volumetric particles - consider the volume of particle that camera is looking through.

Data: Position, velocity, possibly mass

F=ma

Diagram shown in lecture slides

Problem: Approach is only an approx. we only update things once per frame. Assumes vecocity was constant over entire time period of rame. This is wrong - forces­/ac­cel­eration will change gradually throughout frame. Whereas our simple approach changes the velocity isntantly to a new value each frame.

Updating particle pos is an example of an initial value problem. We know the value of an equation at an initial point in time. Want ot calculate value at some furutre point in time.

Function which changes over time: p(t)

Time period: h

Need deriva­tives: p'(t), p''(t)

Taylor series is a repres­enation of a function based on the deriva­tives at a single point (int time)

Arranged here to suit our problem

As h is smaller aprrox is more accurate

Eulers Method uses just the 1st two terms in the series and assumes the rest are small enough to ignore.

vecloc­ity­Nex­tFrame = curren­tVe­locity + frameTime * curren­tAccel

Problem with Euler's method is that velocity and accele­ration are taken at the start of the frame.

This has better accuracy than Euler's method but not perfect as half-way values are themselves approx.

Can be resrictive because of that

Most basic method: uses pos from the current and previous frame and uses current accele­ration

posNex­tFrame = 2 * currentPos - posLas­tFrame + (frame time)² * curren­tAc­cel­eration

Forces involved: Gravity, spring compre­ssion and spring stretch

Force exerted by spring is from Hooke's Law: F = -kx

k = spring coefficent (stiff­ness)

Instead of friction we will damp the motion

v = velocity

Can model rope, cloth and jelly-like objects

Key difference introd­uced: Some types behave differ­ently when stretched and compre­ssed, some are constr­ained, some don't exert forces at some times.

Each constraint can be written as an equation illust­rating then fixed length between particles such as: |pi-pj|² - Lij² = 0

Several constr­aints we have several equations

Of the various mathem­atical solutions most have a similar repeated iterative approach. Examples shown in slides

Visible viewport can be called front buffer

After frame rendering the back buffer is copied to the front buffer

Methods to get the back buffer content to the front buffer involve a simlpe copy were the back buffer is discarded or te 2 buffers are swapped which is useful if we want to keep the last frame

Improved concur­rency with GPU

Copy/swap is fast operation

If you do this though the FPS will be tied to monitor refresh rate

Not necessary to render to a back buffer

Can create explicit render targets or render to multiple render targets

Can then copy it to back buffer to be presented to the viewport but we can also perform additional image processing during this copy

This is full-s­creen post-p­roc­essing

The textures used do not have to all be the same size so that you can scale down and back up for blur for example

Reflec­tion, refrac­tion, fresnel effect, kught extinc­tion, surface deform­ation, foam/s­pra­y/c­austics and underwater effects

Perfectly still water presents a perfect reflection

Can be dynamic, movement in scene is reflected

Static case - Cube mapping works effect­ively, reflect ray from camera off the surface normal and into a cube, hlsl support for cube-m­apping makes this simple, works without difficulty with varying normals

Varying normal can be simulated by offsetting which part of the reflection texture sampled

Altern­ative approach is to use ray-tr­acing or similar

Reflection and refraction require multi-pass approaches to do properly however don't need to do it properly in most cases

Dynamic reflected camera: render the water in the reflection texture using static cube mapping

Amount of bend is given by Snell's Law

n1sin(­theta1) = n2sin(­theta2)

Amount of shift/­dis­tortion depends on: angle at which we view the surface, variations in the surface shape - waves ripples, both of these vary per pixel

Process - Underwater parts of scene rendered to texture, water surface is rendered and this texture is applied, distortion is applied to UVs

Both involve rendering scene to texture

Render water surface blending reflection and refraction textures

To do with viewing angle and blending of textures

F = F0 + (1 - F0)(1 - N . C)⁵

n1, n2 are the refractive indexes of the material

F gives the proportion of reflected light coming from the surface, the remainder comes from refrac­tion. e.g. if F = 0.3 at a point on the surface. Point emits 30% reflected light and 70% refracted light

Light attenuates in water as well as air

Effects refracted light only

Several approaches can be used: e.g. render water surface only to texture, store only its world space distance from camera, when renedering refraction texture subract the distace of each underwater pixel from the water surface distance at the same point. Gives distance the light travels through water to surface. Linearly belend RGB components based on this distance and the extinction distances given. Water surface distance texture created in the 1st step can aslso be used to do the above/­below water clipping

Refer to lecture for more detail