Principle of Computer Game

Software
Engine Programming

CSC7280 Computer Game Software Production

 Engine Programming
1. Game engine architecture
2. Rendering techniques
3. Optimization in rendering

CSC7280 Computer Game Software Production

Evolution of Game Development
• Traditional way of game Stage1()
development
• Monolithic approach – Stage2()
develop source code for :
different stages by different FinalStage()
programmers
End game

CSC7280 Computer Game Software Production

 Monolithic Approach
• Advantage
1. Easy to manage (for a small team size)
2. Allow creativity

• Disadvantage
1. Difficult to modify level
2. Not easy for work division
CSC7280 Computer Game Software Production
 Evolution of Game Development
• During early 90’s, the industry evolved a
new approach : game engine

Level data
Game engine display

player input
CSC7280 Computer Game Software Production
 What is a game engine?
• A software which can provide support for
drawing of graphics, sound, .. etc
• Is technically difficult to develop as they
involve expertise that needs mathematics,
physics, and most important – programming
skills.
• Only a few good 3D game engines available
in the market e.g. Doom3, Unreal, etc.

CSC7280 Computer Game Software Production

 What a game engine do
• Update world based on user input:
collision detection, physics
• World rendering
• Player rendering
• Non-player character(NPC) handling
• Network :
message passing

CSC7280 Computer Game Software Production

 Game Engine Approach
• Advantage
1. Better work division – artists focus on
level building, programmer focus on
different in-game effects
2. Player participation – enthusiast players
can created customized levels
3. With different artworks, can produce
another game

CSC7280 Computer Game Software Production

 Game Engine Approach
• Becoming the norm nowadays
• Disadvantage
1. Games produced tend to alike each other
due to same inherent architecture
2. lack of creativity - game play is restricted
to be the same

CSC7280 Computer Game Software Production

 3D Game development
• The process is essentially similar nowadays
1. Creation of game engine
2. Use game editor to create different levels
(stages) of the game
3. Package with artworks & storyboards
4. Ship the product!

CSC7280 Computer Game Software Production

 What is a game editor?
• Similar to word
processor, game editor
allows you to create a
level for others to play
with.
• Now usually bundled
with the game/allow
download to let player
create their customized
level
Editor of Reality Factory game engine

CSC7280 Computer Game Software Production

 3D Game Development
• It also give rise to
MOD market
• MOD : 3rd party
levels which is
1. addon levels which
adhere to the theme
of the game it
originally based on,
Classic Doom – A Mod remade of old
Doom on new Doom 3
CSC7280 Computer Game Software Production
 3D Game Development
• A Mod can also be:
2. A total conversion(TC)
i.e. all in-game assets
e.g. characters, art,
levels, are created by 3rd
party developer

Counterstrike – a TC using Halflife

CSC7280 Computer Game Software Production

 Start :A simple game architecture
• Update time is usually
constant e.g. player walking Update
speed should be independent
of hardware speed
• Render rate changes Render
according to hardware
configuration
Program loop

CSC7280 Computer Game Software Production

 A simple game architecture
• Inherently should be
implemented as multi-
Update Thread 1
threaded application
• For single threaded
machine, controlling the Render Thread 2
ratio of two calls is most
common solution

CSC7280 Computer Game Software Production

 A simple game architecture
long last = timeGetTime(); Win32 API
while (!end)
{
if ((timeGetTime()-last)>1000/frequency)
{
game_logic(); update
last = timeGetTime();
}
render();
}
CSC7280 Computer Game Software Production
 Game Logic
• Mostly the following actions:
– player update
– world update
– Non-player character (NPC) update

CSC7280 Computer Game Software Production

 World Update
• World consists of basically two categories
of elements:
1. Passive, e.g. walls, background of side
scroller (physics, collision detection)
2. Active, have embedded behavior. e.g.
doors, enemies(AI, scripting).

CSC7280 Computer Game Software Production

 Render
• World rendering
• Player rendering
• Non-player character(NPC) rendering

CSC7280 Computer Game Software Production

 Render
• World rendering
• Player rendering
• Non-player
character(NPC)
rendering

CSC7280 Computer Game Software Production

 World rendering
• Usually not include game characters i.e.
level geometry only
• Reduce the rendering effort through
filtering, clipping & culling
• Pruning the number of polygons to draw
– Visibility processing
– Level of detail processing

CSC7280 Computer Game Software Production

 NPC & player rendering
• Filtering also must apply as we don’t want
to draw those characters not seen in current
view
• Skeletal/key frame animation

CSC7280 Computer Game Software Production

 Rendering Techniques
• Representations used
1. Polygon
2. Bi-cubic parametric patches
3. Constructive Solid Geometry CSG
4. Voxels
5. Implicit surfaces

• Currently polygon representation is most

efficiently rendered (hardware acceleration)
CSC7280 Computer Game Software Production
Constructive Solid Geometry (CSG)
• Consists of Boolean set operations on
closed primitives in 3D space.
• The three CSG operations are union,
intersection and difference.
• Produce polygon models after the
modeling phase
• Used in level design in game

CSC7280 Computer Game Software Production

Constructive Solid Geometry (CSG)
union

intersection

difference
primitives

CSC7280 Computer Game Software Production

 Coordinate Systems
• Coordinate systems used when rendering geometry objects

Linear Linear
transformation transformation

Object World Eye/Camera

space space space

Non-linear Perspective
transformation projection

Raster Screen
space space

Rasterization
CSC7280 Computer Game Software Production
 Rendering Techniques
• Each object (object
space) is placed in
the scene (world
space)
• We set our player
(camera) at
designated position
in level

CSC7280 Computer Game Software Production

 Rendering Techniques
• Polygon mesh now
mostly used
• A list of linked
(x,y,z) coordinates
that are the polygon
vertices
• Polygon/vertex
normals may also be
computed and stored

CSC7280 Computer Game Software Production

 Rendering Techniques
• 3 vertices form one triangle =>
tri 0 vert0
tri 0 vert1
tri 0 vert2
tri 1 vert0
tri 1 vert1
tri 1 vert2
:
• drawback: has repeat occurrences for
vertices shared between triangles in mesh
CSC7280 Computer Game Software Production
 Basic Rendering(OpenGL)
• Let’s assume with display accelerator
Start of bus cycle
– Sending primitives to the accelerator
glBegin(GL_TRIANGLES);
glColor3f(1,1,1);
Send to display card
glVertex3f(-1,0,0);
over the bus one
glVertex3f(1,0,0);
triangle at a time
glVertex3f(0,1,0);
glEnd(); End of bus cycle

• Has the problem of bus fragmentation(slowing

down the bus) for huge no. of polygons
CSC7280 Computer Game Software Production
 Speed up Rendering
• Primitives are packed together and send as a
batch – vertex array/buffer in OpenGL/DirectX
• Use a single call to render the whole object
• Indexing primitives can further reduce the bus
loading
• Interleaved array can also be used – Flexible
Vertex Format (FVF) in DirectX

CSC7280 Computer Game Software Production

 Flexible Vertex Format
• Packed various data for a single vertex into
a single entry
Vertex position 0 Treated as a single
Texture coordinate 0
vertex by DirectX
Normal vector 0
Vertex position 1
Texture coordinate 1
Normal vector 1

• Programmer can define whatever format

needed
CSC7280 Computer Game Software Production
 Indexed Primitives
• Preserve the bandwidth (as well as memory
footprint) in transmitting the data to graphics card
• Send vertices list and face(index) list in separate
list
2 Vertex list Face list
0 x y z 0 1 2
1 x y z 1 3 2
1 2 x y z 0 4 1
0 3
3 x y z 4 3 1
4 x y z
CSC7280 Computer Game Software Production
4
 Rasterization
• Geometry converted to pixels on monitor,
involve transformation by projection matrix
• Performed by hardware nowadays –
geometry information passed in and the
accelerator do the rest
• You have to roll your own for handheld &
mobile

CSC7280 Computer Game Software Production

 Rendering Techniques
• Graphics accelerator performance limited
by
1. (Input) Bandwidth between card and
CPU/main memory (sending geometry,
textures etc.) – AGP, PCI-X interface
2. (Processing) GPU speed(clock)
3. (Output) Pixel fill rate

CSC7280 Computer Game Software Production

 Additional Optimization
• Bus bandwidth is the bottleneck, should try
whatever to save
• Server-side techniques – store the geometry
at the accelerator for a period of time,
render on demand
– Supported on ATI Radeon & NVidia GeForce
2 above

CSC7280 Computer Game Software Production

 Server-side Techniques
• Compiled Vertex Array – geometry send
to accelerator & cached there
• Proprietary currently –
NVidia : Vertex_Array_Range extension
ATI : Vertex_Array_Objects
DirectX : inside vertex buffer as write-only
• Problem: Not suitable for dynamic geometry such
as animated character or procedural geometry
Vertex position will change
CSC7280 Computer Game Software Production
 Quantization(Optimization)
• Storing data in lower precision data type so
as to reduce memory cost
• Assume the range of a certain data is
clustered around certain value
– Compute the range and recalculate the new
value starting from the minimal value
– Stored the scaled value with 8 or 16-bit integers
(originally 32-bit float)

CSC7280 Computer Game Software Production

 Quantization
original - min
Compressed = new_size ×
max - min
• For 8-bit data type to encode object of 2 meter
range
new_size = 256
2
precision = = 0.007 m
256
• With a compression ratio of 4 (float => 1 byte int)

CSC7280 Computer Game Software Production

 Color & Alpha transparency
• Color value in game usually RGB and 24 bits.
• Only true floating point accuracy in newest
GPU i.e. 128 bit color
• Alpha encodes transparency – lower value
means less opacity, zero denotes invisible
color.
• Not recommend to use in texture to save
texture memory

CSC7280 Computer Game Software Production

 Multitexturing

+
original lightmap

multitexture
CSC7280 Computer Game Software Production
 Multitexturing
• Draw two textures on the same location(polygon) can be
performed through different pass
• It can also be performed in single pass using more than 1
texture units
ARB: OpenGL Architecture Review
• In OpenGL Board approved extension

glActiveTextureARB(GL_TEXTURE0_ARB); Texture unit number

glBindTexture(GL_TEXTURE_2D, tex0);
glEnable(GL_TEXTURE_2D);
glActiveTextureARB(GL_TEXTURE1_ARB);
glBindTexture(GL_TEXTURE_2D, tex1);
glEnable(GL_TEXTURE_2D);

CSC7280 Computer Game Software Production

 Multitexturing
• Each texture unit uses a seperate set of texture
coordinates.
glBegin(GL_TRIANGLES);
glMultiTexCoord2fvARB(GL_TEXTURE0_ARB, &t0[0]);
glMultiTexCoord2fvARB(GL_TEXTURE1_ARB, &t1[0]);
glVertex3fv(&v[0]);
glMultiTexCoord2fvARB(GL_TEXTURE0_ARB, &t0[1]);
glMultiTexCoord2fvARB(GL_TEXTURE1_ARB, &t1[1]);
glVertex3fv(&v[1]);
glMultiTexCoord2fvARB(GL_TEXTURE0_ARB, &t0[2]);
glMultiTexCoord2fvARB(GL_TEXTURE1_ARB, &t1[2]);
glVertex3fv(&v[2]);
glEnd();
specify texture coordinates for corresponding texture unit

CSC7280 Computer Game Software Production

 Multitexturing
• Now becoming a
Multiple textures
standard for all Rendering of earth
display accelerator
with more than 1
texture unit e.g. 16
texture units for
ATI X850
• Save rendering
passes The mesh

CSC7280 Computer Game Software Production

 Transform & Lighting
• Transform : geometric transformation including
world, camera & screen transform
• Lighting : perform per vertex lighting calculation
based on light source position & surface properties
• Both(TnL) performed by hardware now
• Hardware per pixel lighting is getting popular now
(most of ATI Radeon X850, nVidia Geforce 6800
series or above)

CSC7280 Computer Game Software Production

 Lighting
• Real time per pixel lighting calculation is difficult
to achieve!
• Lightmapping : stores the lighting information
in low resolution texture and multi-textured to
form the per pixel lighting
– Little computational cost during rendering
– Need long computation time for radiosity lightmap
preparation
– Used in Quake(1996) & its variations

CSC7280 Computer Game Software Production

 Lightmapping
Precalculated
lightmap

Halflife 2
CSC7280 Computer Game Software Production
 Real time Lighting
Real time lighting
on all surfaces

Doom 3

Real time
shadow calculation CSC7280 Computer Game Software Production
3D Graphics Pipeline

CSC7280 Computer Game Software Production

 3D Graphics Pipeline
1. Visibility determination
Clipping
Culling
Occlusion testing
2. Resolution determination
LOD analysis
3. Transform, lighting
4. Rasterization

CSC7280 Computer Game Software Production

 Clipping
• Eliminate unseen geometry by testing it
against clipping volume(e.g. view frustum)
• Better to clip the geometry before passing to
GPU
• Games with large level such as FPS, RPG,
driving game would benefit a lot

CSC7280 Computer Game Software Production

 Clipping
• All current graphics accelerator provide
triangle clipping at hardware level
• Unseen triangles will clipped automatically
• However sending all triangles to card would
slow down rendering as it costs bus
bandwidth to transmit data to card

CSC7280 Computer Game Software Production

 Object Clipping
• Testing clipping at object level can benefit a
lot as we can clip hundreds of triangles at
one test
• An object can be represented as a bounding
volume
• Typically as box or sphere for easy testing

CSC7280 Computer Game Software Production

 Visible Surface Determination
• To draw the correct picture for scene with
many objects occluding one another
• We may use :
1. Backface culling
2. Depth sort
3. Z-buffer
4. Space subdivision algorithms
CSC7280 Computer Game Software Production
 Backface Culling
• Faces of an object with normals pointing
away from camera will be occluded by
other faces – can be culled (backface culling)
glCullFace( GL_BACK); // default
• Can be performed in hardware as well

CSC7280 Computer Game Software Production

 Depth Sort
1. Surfaces are sorted in decreasing depth order
2. Surfaces are rendered back to front
s3 s2

s1

Render order: s3, s2, s1

CSC7280 Computer Game Software Production

 Depth Sort
• Problem : Intersecting polygons/overlapping
depth give wrong result

Incorrect result

CSC7280 Computer Game Software Production

 Occlusion Testing
• Too much overlapping polygons would
result in heavy overdraw
• This dramatically hinder performance in
FPS game of 3D maze
• Potentially Visible Set (PVS), portal
rendering used in indoor rendering to
reduce overdraw (discuss later)

CSC7280 Computer Game Software Production

Hardware based Occlusion Testing
• Each object defined by a bounding object
• The bounding object send down the
graphics pipeline to test against Z-buffer
• A value will then indicate
1. if the object actually modified Z-buffer
2. If it did, how many pixels are affected

CSC7280 Computer Game Software Production

Hardware based Occlusion Testing
• Draw the geometry front to back
• Paint the geometry testing
• If the BV not modify the Z-buffer i.e. the
object fully behind other object, reject the
object(skip the rendering)

CSC7280 Computer Game Software Production

 END

CSC7280 Computer Game Software Production