Section 2

2 Dimensional Graphics

Definitions:

Vector Graphics: images described in terms of co-ordinate drawing operations

Raster Graphics: images described as pixel based bitmaps

Modern computer VDUs present graphics in raster format in either case… the difference lies in the way vector/raster graphics are stored and manipulated by software.

2.1 2D VECTOR GRAPHICS

Translation

Translation in 2 dimensions: movement of a point (x,y) to some other point (x', y')

x' = x + a

y' = y + b

Rotation of a point about (0,0) through angle 

Rotation

Rotation about the origin (0,0) is simplest:

x' is some function of x and y

y' is some other function of x and y

General equations for rotation about (0,0):

x' = x cos  - y sin 

y' = x sin  + y cos 

To rotate a line or more complex object, simply apply the equations to the (x,y) co-ordinates of each vertex

Original object: Rotated by 45 degrees:

In order to rotate around an arbitrary point (a,b):

now:

x' - a = (x - a) cos  - (y - b) sin 

y' - b = (x - a) sin  + (y - b) cos 

i.e:

x' = a + (x - a) cos  - (y - b) sin 

y' = b + (x - a) sin  + (y - b) cos 

Matrix Notation

Matrix notation is commonly used for vector graphics

The equations for rotation about (0,0) in matrix format:

cos  / sin 
[x' y'] = [x y]
-sin  / cos 

The equations for translation in matrix format:

1 / 0 / 0
[x' y' 1] = [x y 1] / 0 / 1 / 0
a / b / 1
  • Writing every transformation as a multiplication of matrices allows several transformations to be combined into one
  • This explains the square matrix used above for translation

Line Clipping

  • Drawing line segments only as far as they lie within a given rectangle (usually called a window or viewport)

Example:

  • Line segments SR and TR must not be drawn
  • It is required to determine the co-ordinates of S and T

An elegant algorithm for line clipping was developed by Cohen & Sutherland:

  • E.g.: The Cohen-Sutherland Algorithm] Anand pp.82-83

Inherently graphical (windowed) Operating Systems and any decent graphics API provide automatic line clipping:

  • Any drawing operation is an OS or API call
  • The OS or API only plots within a valid region:
  • within the bounds of the current window
  • or within a viewport defined by the user

Scaling

What is the difference between a window and a viewport?

  • Normally a window's dimensions are expressed in world co-ordinates ("world co-ordinate system")
  • Normally a viewport's dimensions are expressed in graphics co-ordinates ("device co-ordinate system")
  • Drawing a picture of a real object on-screen therefore requires the mapping (scaling plus translation) of its windowco-ordinates to the chosen viewport co-ordinates

Here x and y are measured in metres, and X and Y are in pixels

First the scale factors fxand fyare computed:

If fxand fy are not equal and distortion is not to be allowed, the smaller of the two is used for both

Thenthe (X,Y) viewport co-ordinates of each vertex in the drawing are calculated as:

X= X_min + fx * (x - x_min)

Y = Y_min + fy * (y - y_min)

2D Graphics Example: "Asteroids" game

Requirement:

  • collision detection!

(how to determine if the ship or a bullet has hit an asteroid)

Determining if a point is inside a polygon

Method 1:

  • Choose any reference point outside the polygon.
  • Follow a line from this point to the point under test.
  • Count the number of intersections between this line and the polygon's lines.
  • Odd result => the point is inside the polygon
  • Even result => the point is outside the polygon

Method 2 (simpler to code):

  • Only works if the polygon is convex
  • Consider the polygon as a "path" from the first vertex.
  • A point is on the interior of this polygon if it is always on the same side of all the line segments making up the path.
  • Given a line segment (x0,y0) to (x1,y1), a point (x,y)
  • Compute:

(y - y0)*(x1 - x0) - (x - x0)*(y1 - y0)

  • If this it is less than 0 then (x,y) is to the right of the line segment,
  • If greater than 0 it is to the left,
  • If equal to 0 then it lies on the line segment.

2.2 2D Raster Graphics

A simple black & white letter

The same letter drawn using 'antialiasing'

  • The jagged edges result from the "all or nothing" approach to painting pixels
  • One solution is to increase screen resolution => expensive and never fully solves the problem
  • Antialiasing applies colour to a pixel depending on how much of it lies under an object

(a): A thin line drawn with depth 1 bit (B&W)

(b): Same line on a display with twice the resolution

A line of 1 pixel width from (1,1) to (10,4):

Antialiased rendering with intensity directly proportional to area covered ("unweighted area sampling"):

Unweighted area sampling of a point object: (changes in intensity only occur when the object crosses a pixel boundary)

Weighted area sampling of a point object: (intensity is inversely proportional to distance from pixel centres)

Weighted area sampling with overlap of a point object (circular distance function of area greater than a pixel, allowing a point to simultaneously influence more than one pixel)

Filling arbitrary shapes: flood fill

Given:

  • A bitmap consisting of a 2 dimensional array (integers) of coloured pixels
  • A starting x, y position for the flood-fill operation
  • The colour that is to be changed from
  • The colour that it will be changed to

Algorithm/pseudocode:

  • Procedure floodfill(x, y, colfrom, colto)
  1. Change colour at x, y to colto
  2. Check all neighbouring pixels (x1,y1) of (x,y), i.e. in the range (x-1,y-1) to (x+1,y+1)
  3. If any pixels at (x1,y1) have the same colour as (x,y), then recursively call floodfill(x1,y1, colfrom, colto)

Some Graphics Programming Environments:

1. Low Level Application Programming Interfaces:

  • Libraries of graphics functions that can be accessed from a standard programming language
  • Procedural rather than descriptive => fast!
  • Procedural: the programmer calls the graphics functions which carry out operations immediately
  • Examples: OpenGL, DirectX, Java Media APIs

2. High Level APIs:

  • The programmer describes the required graphics, animations, interactivity etc. and doesn't need to deal with how this will be displayed and updated
  • Descriptive rather than procedural => slow!
  • Example: VRML

Common tools for the programmer, supplied in most graphics libraries (APIs):

Fonts (text output and related functions e.g. to determine dimensions of a string in a specified font)

Pens (line colour, style, thickness)

Brushes (fill colour, pattern)

Vector Primitives (filled/ unfilled) - lines, rectangles, polygons, circles, ellipses

Bitmap (raster) functions - loading, drawing on screen, stretching, copying

'Blitting': ("blit" = "bit block transfer") copy operations performed on a bitmap or part of a bitmap:

  • direct copy
  • application of binary logic during copy
  • 'transparent' colours

More advanced tools e.g. Palette fills/washes

Curve fitting (2D) - Surface Fitting (3D)

Representing smooth curves or surfaces - real world objects

e.g. B Spline curve fitting:

  • A curve is drawn between 2 points by taking into account their other 2 neighbours also
  • Trade-off: smoothness vs. conformity to control points

Sprites:

  • Raster objects incorporating transparency, multiple frames and sometimes collision detection

Transparency:

Back buffers:

  • Used to solve the vertical refresh (flicker) problem
  • Back buffers are offscreen memory buffers of same dimensions as onscreen ("front buffer") video memory
  • Graphics operations are performed on the back buffer
  • Then the back and front buffers are flipped during the vertical synch period

3D functions (later!)

Graphics adapters:

Traditional graphics adapters:

  • contain graphics memory plus VDU output connector
  • all calculations are done by the CPU
  • the CPU writes raster information into video memory

Modern "hardware accelerated" adapters:

  • additionally contain their own processors
  • respond to commands from the CPU (any of the above), taking away from the workload on the CPU itself
  • may also handle blitter (memory copy) operations between front/back buffers and other "virtual surfaces" in video memory
  • increased onboard memory beyond the needs of the display device - sprites, textures etc. stored on the graphics card can be blitted into video memory faster and with less CPU work than before
  • trend towards hardware support for standard graphics APIs such as DirectX and OpenGL

Traditional Graphics Adapters:

Work done by CPU:

• image data download from RAM

• rendering calculations

• image upload to video memory

'Hardware Accelerated' Graphics Adapters:

Work taken over by Graphics Adapter:

  • image data download from secondary video memory
  • (some or all) rendering calculations
  • (some or all) image upload to primary video memory
2D Raster Graphics Example: "Space Invaders" game