Computer Science notes ⇒ Computer Graphics and Visualisation

This minisite contains notes taken by Chris Northwood whilst studying Computer Science at the University of York between 2005-09 and the University of Sheffield 2009-10.

They are published here in case others find them useful, but I provide no warranty for their accuracy, completeness or whether or not they are up-to-date.

The contents of this page have dubious copyright status, as great portions of some of my revision notes are verbatim from the lecture slides, what the lecturer wrote on the board, or what they said. Additionally, lots of the images have been captured from the lecture slides.

What is Computer Graphics?

Angel c.1

Computer graphics is concerned with all aspects of producing pictures or images using a computer; the ultimate aim is to represent an imagined world as a computer program.

A Brief History

  • pre-1950s - Crude hardplots
  • 1950s - CRT displays (e.g. as seen in early RADAR implementations)
  • 1963 - Sutherland's sketch pad
  • 1960s - The rise of CAD
  • 1970s - Introduction of APIs and standards
  • 1980s - Rise of PCs lead to GUIs and multimedia
  • 1990s - Visualisation, rise of the Internet, WWW, Java, VRML

Computer graphics have many applications, such as displaying information as in meterology, medical uses and GIS; design as with CAD/CAM and VLSI as well as simulation, such as virtual reality, pilot training and games.

Graphics systems are raster based - represented as an array of picture elements known as pixels stored in a frame buffer. Vector based systems on the other hand work by following a set of instructions and outputing the results. Raster based systems are faster, but require more memory.

Graphics are ultimately about controlling pixels, but we use primitives to abstract away from the pixels.

Mathematical Basics

Angel c.4

We can consider some mathematical basics when dealing with computer graphics. We can consider points - locations in space specified by coordinates, lines - which join two points, a convex hull - the minimum set which includes all points and the line segments connecting any two of them, and a convex object - where any point lying on the line segment connecting any two points in the object is also in the object.

In computer graphics, we also use vectors for relative positions in space, orrientation of surfaces and the behaviour of light. We can also use them for trajectories of dynamics and operations. A vector is a n -tuple of real numbers, and addition and scalar multiplication is done quite straight forwardly by either adding each individual term to the corresponding one in another vector, or by multipying each individual element by a scalar.

Trigonometry (sine, cosine, tangent, etc) is also used to calculate directions of vectors and orrientations of planes.

We can also use the dot (inner) product of vectors, where ab = |a ||b |cos θ. The product can be calculated as ab = x 1 y 1 +. + x n y n . We can use this to figure the Euclidean distance of a point (x. y ) from the origin d = √ x 2 + y 2 (and similarly for n -dimensional space).

The dot product can also be used for normallising a vector.v ′ = v /||v || is a unit vector, it has a length of 1. The angle between the vectors v and w can be expressed as: cos -1 ((vw )/(||v|| ||w||)). If the dot product of two vectors v and w is 0, it means that they are perpendicular.

Matrices

A determinant (det A ) is used in finding the inverse of a matrix. If det A = 0, it means that A is singular and has no inverse.

Planes

Three points not in a line determine a unique plane. Three edges forming a triangle determine a plane. A plane can be determined by point P0 and two unparalleled vectors u and v .

The equation of a plane can be expressed as T(α, β) = P0 + αu + βv . An equation of a plane given the plane normal n . n ∧ (P - P0 )

Planes are used for modelling faces of objects by joinin edges and vertices. In this case, their service normals are used to represent shading and other more complex lumination phenomena such as ray tracing. You can then visualise correspondingly the texture that is applied onto objects. You can also model the visualisation system with planes, and they constitute the basis for more complex surfaces (e.g. curved surfaces come from patches that are planar in nature).

Transformations

There are three fundamental transformations in computer graphics, which can be expressed using vectors and matrices.

However, we now have the problem that translation can not be expressed using matrix multiplication, so we move from from cartesian to homogenuous (projective) coordinate space. Each affine transformationis represented by a 4 × 4 matrix within a reference system (frame). The point/vector (x. y ) becomes (x. y. w ), so (x 1. y 1. w 1 ) = (x 2. y 2. w 2 ) if x 1 /w 1 = x 2 /w 2 and y 1 /w 1 = y 2 /w 2. This division by w is called homogenising the point. When w = 0, we can consider the points to be at infinity.

Now we are working in homogenuous space, we can apply uniform treatment:

Shearing can be used to distort the shape of an object - we shear along the x axis when we pull the top to the right and the bottom to the left. We can also shear along the y axis.

Transformations of a given kind can be composed in sequence. Translations can be used to apply transformations at arbitrary points. When composing different translations, the last translation to be applied to the matrix is applied first, and then backwards from that. Transformations are generally associative, but have non-commutativity.

Special orthogonal matrices can be used to simplify calculations for rigid body transformations:

3D Transformations

For 3D transformations, the same principles apply, but now in a 4D homogenuous space. However, rotation now has to be defined with respect to a specific axis.

Graphics often utilise multiple coordinate spaces. We can express this as P (i ). as the representation of P in coordinate system i. To translate between the two systems, we apply the matrix Mij . as the transformation from system j to system i

Primitives

Angel c.2

In OpenGL, we specify primitives by declaring

glBegin(mode);. followed by a specification of the vertices and other properties, and then we end the primitive definition with glEnd();. The mode in this case is a specification of which primitive we want to define, such as:

Examples are in

And vertices can be specified using glVertexNT(TYPE c1, TYPE c2. TYPE cn);. where N is the number of dimensions of the vertex (2, 3 or 4) and T is a character indicating the data type, s for short, i for integer, f for float and d for double. Alternatively, the vertex arguments could be passed as an array using glVertexNTv(TYPE coords[]); .

We can also consider other primitives, such as curves, circles and ellipses, which are typically specified by a bounding box (an extent), a start angle and an end angle, although variations exist which use the centre and a radius, different implementations use radians vs. degrees and allow the orrientation of the bounding box to be changed. NURBS are also common and are what OpenGL uses. Simple curves are non-existant in OpenGL and must be defined using quadrics.

When talking about points, we can consider the convex hull - the minimum set which includes all the points and the line segments connecting any two of them. The convex object consists of any point lying on the line segment connecting any two points in the object.

We can also consider text as a primitive. Text comes in two types, stroke fonts (vector), where each character is defined in terms of lines, curves, etc. Stroke fonts are fairly easy to manipulate (scaling and rotation, etc), but this takes CPU time and memory. Bitmap (raster) fonts are where each character is represented by a bitmap. Scaling is implemented by replicating pixels as blocks of pixels, which gives a block appearance. Text primitives give you control of attributes such as type, colour and geometrical parameters and typically require a position and a string of characters at the very least.

OpenGL support for text is minimal, so GLUT services are used, such as glutBitmapCharacter(); and glutStrokeCharacter(); .

Some primitives are used to define areas, so a decision needs to be made on whether or not these area-definining primitives need to be filled or outlined. In OpenGL, polygonal primitives are shaded, and explicit control is given over the edge presence. More complicated effects can be accomplished by texturing. This fill attribute may allow solid fills, opaque and transparent bitmaps and pixmaps.

A final primitive to consider is that of canvases. It is often useful to have multiple canvases, which can be on- or off-screen, and there consists of the default canvas, and a concept of a current canvas. Canvases allow us to save or restore image data, and support buffering and have a cache for bitmap fonts. The OpenGL approach to canvases uses special-purpose buffers, double buffering and display lists.

Curves and Surfaces

Up until now, curves and surfaces have been rendered as polylines and polygonal meshes, however we can use piecewise polynomial functions and patches to represent more accurate curves and curved surfaces.

Parametric equations (one for each axis) are used to represent these, where each section of a curve is a parametric polynomial. Cubic polynomials are widely used due to having an end-point and gradient continuity, as well as being the lowest degree polynomial that is non-planar. Curve classes are used due to the constraints used to identify them (points, gradients, etc).

Parametric polynomials of a low degree are prefered as this gives us a local control of shape, they have smoothness and continuity and derivatives can be evaluated. They are fairly stable and can be rendered easily too - small changes in the input should only produce small changes in the output.

The points are called curve and segment points.

We can consider two types of geometric continuity of 2 segments:

  1. segments join (G0)
  2. tangent directions are equal at the join point, but magnitudes do not have to be (G1)

We can consider three properties of parametric continuity:

  1. all three parameters are equal at the join point (C0)
  2. G1 (only required if curves have to be smooth) and the magnitudes of the tangent vectors are equal (C1)
  3. The direction and magnitude of ∀i. iN. 1 ≤ in. d i /dt i Q(t ) are equal at the join point (Cn - however n > 1 is only relevant for certain modelling contexts, e.g. fluid dynamics).

Hermite Curves

Hermite curves are specified using two end-points and the gradients at the end points, and these characteristics specify the Hermite geometry vector. The end points and tangents should allow easy interactive editing of the curve.

By changing the magnitude of the tangent, we can change the curve whilst maintaining G1 consistency.

Bézier Curves

Parametric gradients are not intuitive, so an alternative is to use 4 points, of which 2 are interpolated and 2 which are approximated. We can then figure out G1 = dQ(0)/dt = 3(P2 - P1 ) and G2 = dQ(1)/dt = 3(P4 - P3 ).

Bézier curves and surfaces are implemented in OpenGL. To use them, we need a one-dimensional evaluator to compute Bernstein polynomials. One dimensional evaluators are defined using glMap1f(type, u_min, u_max, stride, order, point_array). where type is the type of objects to evaluate (points, colours, normals, etc), u_min and u_max are the range of t. stride is the number of floating point values to advance between control points, order specifies the number of control points and point_array is a pointer to the first co-ordinate of the first control point. An example implementation of this may be:

glBegin(GL_LINE_STRIP);

for (i=0;i<=30;i++) glEvalCoord1f((GLfloat) i/30.0);

glEnd();

To implement Bézier surfaces, the glMap2f(type, u_min1, u_max1, stride1, order1, u_min2, u_max2, stride2, order2, point_array) function can be used, along with glEvalCoord2f(). or you can use glMapGrid2f() and glEvalMesh2() .

B-splines

Bézier curves and patches are widely used, however they have the problem of only giving C0 continuity at the join points. B-spline curves can be used to obtain C2 continuity at the join points with a cubic.

Knots lay between Qi and Qi + 1 at t i (the knot value). t 3 and t m + 1 are end knots, and are equally spaced (uniform), so t i + 1 = t i + 1 (therefore the blending function is the same for all segments).

We can call these curves non-rational to distinguish it from the rational cubic curves (a ratio of polynomials).

Another variety of B-splines also exist - non-uniform non-rational B-splines. Here, the spacing of the knots (in parameter space) is specified by a knot vector (the value of the parameter at the segment joins).

The table below compares Bézier curves with uniform B-splines:

Source: www.pling.org.uk

Category: Hardware

Similar articles: