Introduction to 3D Games

• General concepts
• World representation
• Physically based models
• Movement and gravitation
• Collision detection
• Characters and animation

Coordinate Systems

• 2D - Cartesian coordinates Oxy.
• Viewport: region of the application window used for drawing.
• 3D Cartesian coordinates Oxyz.
• Vertex: a position in the 3D space - a vertex.
• Most 3D APIs use real 3D coordinates
• Going from the physical 3D coordinates to the 2D discrete screen coordinates - projection.

Projection

• Def. P(x, y, z) -> P'(x', y', z') in p, projection plane.
• Usually the projection plane is defined by z' = 0.
• 2 types of projection: parallel, perspective.
• Parallel projection: orthographic or oblique.

Parallel Projection

• Defined by a projection line (direction) d.
• If the line is perpendicular to the projection plane - orthographic projection. Otherwise oblique.

Features of the Parallel Projection

• preserves the ratio between parallel objects;
• preserves the parallel lines;
• the orthogonal projection preserves the width of segments that are parallel to p;
• gives poor impression of image depth;
• often used for technical drawing, architecture plans, etc.

Perspective Projection

• Given a projection center C representing the viewer's eye.
• Consider the line L such that C and P is on L. Then P' = L intersection p.

Features of the Perspective Projection

• does not preserve proportions;
• does not preserve most parallel lines;
• object size depends on the closeness to the center: close objects seem big, distant objects seem small;
• gives a good impression of image depth;
• contains a vanishing point, where all the lines that are not parallel to the projection plane converge; this point is the orthogonal projection of C (the eye/camera) on the plane p. It also represents the infinity point (the horizon). often used for painting, drawing (especially comics), and 3D software.

Types of 3D Games

• Action games - You have an armed character and fight against armed opponents. Quake
• Adventure games - exploring a world, doing quests, solving puzzles. Heavily based on a story and often linear. Final Fantasy, LOTR
• Role-Playing Games - a combination of the above. You control a character that evolves through the game. Dungeons and Dragons, Guild Wars.
• These are either First Person Point of View games (1st PPOV) aka First Person Shooter or 3rd PPOV where you control a character (avatar) that you can see in its environment.
• Maze and puzzle games - 3D Adventure Pinball, 3D Lemmings
• Simulator Games - Grand Theft Auto, flight simulator
• Sports Games - Maximum Football
• Strategy Games - Warcraft, Age of Empires

Elements of a 3D Game

• Game engine - essential features of the game environment: graphics, rendering, networking, scripting, etc.
• Scripts - layer on top of the game engine, allows for customization of the game.
• GUI - menus, info display, action boxes, etc.
• Game elements : 3D models, textures, sounds.
• Database: allows for persistence of a character or other game content you create in the game.
• Game support : web sites, support forums, auto-update component.

General Game Setting

• The game environment consist of many 3D objects. One object in particular may represent the player.
• Most objects in the game are solid - the program represents and renders their surface.
• An object is composed of vertices delimiting it, and surfaces based on these points: triangles, polygons, nurbs, etc. The easiest is to use triangles.
• An object has properties: color, texture, solidity, game-relevant qualities like health, mana, amount of damage, eventually behavior.
• Animated objects require several shapes we can cycle through.

enum Obj_type {static, collectible, animated, behaving};
enum Surface_type {tstrip, polygon,...};
struct Surface { vector coords;
                 Point3f color;
                 Texture aspect; };
typedef vector Shape;
class Object {
 protected:
  int shape_count; bool active;
  Point3f position, orientation;
  Shape shapes[shape_count];
  Obj_type base_type; float speed;
 public:
  display();
};

Display Settings

• Most of these games use a perspective projection with a reasonable angle (60).
• The point of view and direction of view must change while the game is played.
• For 1st person and 3rd person games, the point of view follows the character around.
• Two methods:
• recompute the projection frustum based on the desired POV
• transform the scene such that the POV and frustum are always the same.

Game Controls

• A character moving in an environment composed of a terrain on which reside several objects including itself.
• The character usually moves around continuously in the space based on their speed (except for teleporting).
• Special keys (arrows, wasd) control the movement and change of direction.

Type of Movement

• Forward / backward - moving the object position along the current direction of movement by an amount depending on its speed. Arrow up / down.
• Strafing - moving the object position left or right in a direction perpendicular to the direction of movement. (Shift/ctrl) + Arrow left/right
• Turning - change in the direction of movement. This can be static or dynamic. Arrow left/right, mouse
• Camera - change in the camera orientation and zooming. Usually implemented with a trackball.

Camera Position

• a) Move the camera
• Start:
  offset = camera.position - player.position;
  
  
• Update:
  offset.rotate(0, player.rotation.y, 0);
  camera.rotate(0, player.rotation.y, 0);
  camera.position = player.position+offset;
  
  
• b) Fixed camera, move the world instead
• Update:
  world.translate(-player.position);
  world.rotate(-player.orientation);
  

Moving, World Coordinates

• Forward:
  ds = speed * dt;
  p = Vector3(0, 0 ,ds).rotate(player.orientation);
  player.position += p;
  
  
• Strafing:
  p.rotate(+90);
  player.position += p;
  
  
• Turning
  player.orientation.y += angle;
  

Player-Focused Camera

• Keep a global world transformation.
  
  
• Forward:
  ds = speed * dt;
  world.position.z -= ds;
  
  
• Strafing:
  ds = speed * dt;
  left: world.position.x += ds;
  right: world.position.x -= ds;
  
  
• Turning
  world.rotate(0, -angle, 0);
  

Trackball

• Drag the mouse to rotate the camera around an object on a virtual trackball.
• Let (Ox, Oy) be the position on screen of the center of the sphere (player).
• Let (x, y) be the current position of the mouse.
• If x' = x-Ox, y' = y-Oy, the equation of the sphere is
  x'² + y'² + z'² = r²
• z' is determined as
  sqrt(r² - x'² - y'² ) if x'²+y'² < r²/2
  (r²/2)/ sqrt(x'²+y'²) otherwise
  
• Then if the mouse moves between (x'1, y'1, z'1) and (x'2, y'2, z'2), we rotate the camera with the angle between them.
• Normalize these two vectors as V1 and V2, then compute
  angle theta = arccos(V1 V2),
  axis N = V1 x V2
  Q = (cos(theta/2), sin(theta/2)N) the quaternion of the rotation.
• More details

Terrain Representation

• Height field or height map - a virtual representation of a landscape such that the data points are a two dimensional set of evenly spaced height values.
• This is usually represented as a 2D grayscale image where lighter pixels represent higher values, and black would be the "sea level".
• A mesh of quadrilaterals or triangles is then generated based on the scale of the terrain.
• Texture mapping is applied to make it look realistic.

Height Map and Rendered Terrain:

Images taken from here.

Rendering the height map:

#define AREA_SIZE 128 /* size of (square) map */ 
#define F 16.0 /*world scale of one height map cell*/ 
float height_field[AREA_SIZE][AREA_SIZE];  
void render_height_field( void ) { 
  int x, z; 
  glColor3f(0, 0.5, 0.1); 
  glBegin(GL_TRIANGLE_STRIP); 
  for(x = 0; x < AREA_SIZE-1; x++) { 
    for(z = 0; z < AREA_SIZE; z++) {
      glVertex3f(F*x,F*height_field[x+1][z],F*z); 
      glVertex3f(F*x, F*height_field[x][z], F*z);
    } 
  } 
  glEnd(); 
} 

Rendered Terrain

Level of Detail Techniques (LOD)

• Rendering the terrain with variable resolution based on the needs of the application.
• There are two situations requiring high resolution: close-up, and high altitude change. Distant terrain or a relatively flat one requires less resolution.
• Variable resolution means intelligent use of textures such that the player doesn't notice the level of detail changes.
• Mipmaps: collections of textures of various resolution for the same type of terrain (grass).

Frustum Culling

• Not drawing the parts of the scene that are not visible.
• By defining a projection type, a frustum is defined such that any vertex outside of it will not be rendered by OpenGL.
• If there are a lot of vertices in the program, this might take too long even if it works.
• The goal is to discard a large amount of data even before the OpenGL code is generated.

Methods for Frustum Culling

• Defining a bounding box or sphere for every object.
• An intersection can be computed of the bounding box and the frustum box.
• 3 possible cases:
• either the BB is outside the frustum, in which case the object can be discarded (from the display function)
• either the BB is completely inside in which case the object is displayed
• or part of the BB is in the frustum.
• In the last case it's easier to draw the entire object and let OpenGL do the culling.

Roads

• A road is a 1D curve with width through the 2D terrain surface. In a game it can represents a set path from a location to another, or a sub-environment (cave).
• A road can self-intersect at various altitudes, so a height map may not be appropriate.
• A road usually has a direction of movement (1 or 2-way).
• Can be represented as a "ribbon": a sequence of points (centerline) and a given width.
• More complex paths can be made out of a centerline + building blocks.
• Or a simple collection of polygons (triangles).

Buildings

• The building's terrain is flat, so we don't need a height map.
• Things can coexist in a building at the same position at different height.
• We need to represent them by level (floor).
• Some base polygons plus width are needed for the walls and floors and all the other objects can be explicitly present in the building.
• Sometimes referred to as 2.5D worlds: the representation of a room is 2D, but the objects inside are 3D.

Procedural Worlds

• Generating portions of the game landscape automatically using some algorithms.
• Using basic shapes and rules to combine them (like constructive solid geometry) or even L-systems.
• What parameters of the building should be stored to construct the building procedurally?
• Classify buildings by function, occupants, form, etc.
• The landscape can be stored or generated dynamically. Many commercial programs available: Decensor, CityEngine, City Generator, etc.