Computer Graphics Notes

Graphics Pipeline

• Primitives: Points, Lines, Triangles ([Angel Ch. 2])

• Graphics Pipeline:

  • Primitives + material properties

  • Translate, Rotate, Scale

  • Is it visible on screen?

  • 3D to 2D conversion

  • Convert to pixels

  • Shown on the screen (framebuffer)

• Framebuffer:

  • Special memory on the graphics card.

  • Stores the current pixels to be displayed on the monitor.

  • Monitor has no storage capabilities.

  • The framebuffer is copied to the monitor at each refresh cycle.

• Rendering with OpenGL:

  • Application generates the geometric primitives (polygons, lines).

  • System draws each one into the framebuffer.

  • The entire scene is redrawn anew every frame.

  • Comparison: Off-line rendering (e.g., Pixar Renderman, ray tracers).

• OpenGL implements the pipeline; the graphics driver and hardware also contribute.

  • The OpenGL programmer does not need to implement the pipeline.

  • The pipeline is reconfigurable via shaders.

• Graphics Pipeline Efficiency:

  • Efficiently implementable in hardware (but not in software).

  • Each stage can employ multiple specialized processors working in parallel; buses connect the stages.

  • Processors per stage and bus bandwidths are tuned for typical graphics use.

  • Considers Latency vs throughput

Vertices (compatibility profile)

• Vertices in world coordinates.

• void glVertex3f(GLfloat x, GLfloat y, GLfloat z)

  • A vertex $(x, y, z)$ is sent down the pipeline. Then function call then returns.

• Use GLtype for portability and consistency.

• glVertex{234}{sfid}[v](TYPE coords)

Vertices (core profile)

• Vertices in world coordinates.

• Store vertices into a Vertex Buffer Object (VBO).

• Upload the VBO to the GPU during program initialization (before rendering).

• OpenGL renders directly from the VBO.

Transformer (compatibility profile)

• Transformer in world coordinates.

• Must be set before object is drawn.

• Example: glRotatef(45.0, 0.0, 0.0, -1.0); glVertex2f(1.0, 0.0);

• Complex [Angel Ch. 3].

Transformer (core profile)

• Transformer in world coordinates.

• $4x4$ matrix.

• Created manually by the user.

• Transmitted to the shader program before rendering.

Clipper

• Mostly automatic (must set viewing volume).

Projector

• Complex transformation [Angel Ch. 4].

• Orthographic and Perspective projections.

Rasterizer

• Interesting algorithms [Angel Ch. 6].

• To window coordinates.

• Antialiasing.

Geometric Primitives

• Suppose we have 8 vertices: $p0, p1, p2, p3, p4, p5, p6, p7$

• Interpretation examples:

  • GL_POINTS

  • GL_LINES

  • GL_TRIANGLES - examples of primitive type

Triangles

• Can be any shape or size.

• Well-shaped triangles have advantages for numerical simulation.

• Shape quality makes little difference for basic OpenGL rendering.

Geometric Primitives (compatibility profile)

• Specified via vertices.

• General schema:

  • glBegin(type);

  • glVertex3f(x1, y1, z1);

  • ...

  • glVertex3f(xN, yN, zN);

  • glEnd();

• type determines interpretation of vertices.

• Can use glVertex2f(x, y) in 2D.

Example: Draw Two Square Edges (compatibility profile)

• Type = GL_LINES

• glBegin(GL_LINES);

• glVertex3f(0.0, 0.0, -1.0);

• glVertex3f(1.0, 0.0, -1.0);

• glVertex3f(1.0, 1.0, -1.0);

• glVertex3f(0.0, 1.0, -1.0);

• glEnd();

• Calls to other functions are allowed between glBegin(type) and glEnd();

Geometric Primitives (core profile)

• Specified via vertices.

• Stored in a Vertex Buffer Object (VBO).

• Example:

  • int numVertices = 300;

  • float vertices[3 * numVertices];

  • // (… fill the “vertices” array …)

  • // create the VBO:

  • GLuint vbo;

  • glGenBuffers(1, &vbo);

  • glBindBuffer(GL_ARRAY_BUFFER, vbo);

  • glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

Render Points and Line Segments (compatibility profile)

• glBegin (GL_POINTS); // or GL_LINES to render lines

• glVertex3f(…); …glVertex3f(…);

• glEnd();

Render Points and Line Segments (core profile)

• glDrawArrays(GL_POINTS, 0, numVertices); // render points

• glDrawArrays(GL_LINES, 0, numVertices); // render lines

Main difference between the two profiles

• Compatibility:

  • Rendering:

    • glBegin(type);

    • glVertex3f(x1, y1, z1);

    • ...

    • glVertex3f(xN, yN, zN);

    • glEnd();

• Core:

  • Initialization:

    • int numVertices = 300;

    • float vertices[3 * numVertices]; // (… fill the “vertices” array …)

    • // create the VBO:

    • GLuint vbo;

    • glGenBuffers(1, &vbo);

    • glBindBuffer(GL_ARRAY_BUFFER, vbo);

    • glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

  • Rendering:

    • glDrawArrays(type, 0, numVertices);

Common Bug

• int numVertices = 50000;

• float * vertices = (float*) malloc (sizeof(float) * 3 * numVertices);

• …

• glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

• What is wrong? Should be:

• glBufferData(GL_ARRAY_BUFFER, sizeof(float) * 3 * numVertices, vertices, GL_STATIC_DRAW);

Polygons

• Polygons enclose an area.

• Rendering of area (fill) depends on attributes.

• All vertices must be in one plane in 3D.

• GL_POLYGON and GL_QUADS are only available in the compatibility profile (removed in core profile since OpenGL 3.1).

Triangle Strips

• Efficiency in space and time.

• Reduces visual artefacts on old graphics cards.

Summary

1. Graphics pipeline

2. Primitives: vertices, lines, triangles

Lecture 4: Color and Hidden Surface Removal

• Client/Server Model

• Callbacks

• Double Buffering

• Physics of Color

• Flat vs Smooth Shading

• Hidden Surface Removal ([Angel Ch. 2])

Physics of Color

• Electromagnetic radiation

• Can see only a tiny piece of the spectrum

Color Filters

• Eye can perceive only 3 basic colors

• Computer screens designed accordingly

Color Spaces

• RGB (Red, Green, Blue)

  • Convenient for display

  • Can be unintuitive (3 floats in OpenGL)

• HSV (Hue, Saturation, Value)

  • Hue: what color

  • Saturation: how far away from gray

  • Value: how bright

• Other formats for movies and printing

Client/Server Model

• Graphics hardware and caching

• Important for efficiency

• Need to be aware of where data are stored

• Graphics driver code is on the CPU

• Rendering resources (buffers, shaders, textures, etc.) are on the GPU

• CPU is the "Client"

• GPU is the "Server"

The CPU-GPU bus

• CPU can also read back from GPU

• Fast, but limited bandwidth

• PCI, PCI Express

Buffer Objects

• Store rendering data:

  • vertex positions

  • normals

  • texture coordinates

  • colors

  • vertex indices, etc.

• Optimize and store on server (GPU)

• CPU is the "Client"

• GPU is the "Server"

• Store here bus

Vertex Buffer Objects

• Caches vertex geometric data:

  • positions

  • normals

  • texture coordinates

  • colors

• Optimize and store on server (GPU)

• Required for core OpenGL profile

• Example of vertices of the quad that will form two triangles (rendered via GL_TRIANGLES):

  • float positions[6][3] = {{-1.0, -1.0, -1.0}, {1.0, -1.0, -1.0}, {1.0, 1.0, -1.0}, {-1.0, -1.0, -1.0}, {1.0, 1.0, -1.0}, {-1.0, 1.0, -1.0}};

• Example of colors to be assigned to vertices (4th value is the alpha channel):

  • float colors[6][4] = {{0.0, 0.0, 0.0, 1.0}, {1.0, 0.0, 0.0, 1.0}, {0.0, 1.0, 0.0, 1.0}, {0.0, 0.0, 1.0, 1.0}, {1.0, 1.0, 0.0, 1.0}, {1.0, 0.0, 1.0, 1.0}};

Vertex Buffer Object: Initialization

• int numVertices = 6;

• VBO * vboVertices;

• VBO * vboColors;

• void initVBOs() {

  • // 3 values per vertex, namely x,y,z coordinates

  • vboVertices = new VBO(numVertices, 3, positions, GL_STATIC_DRAW);

  • // 4 values per vertex, namely r,g,b,a channels

  • vboColors = new VBO(numVertices, 4, colors, GL_STATIC_DRAW);

  • }

Element Arrays

• Draw cube with $6<em>2</em>3=36$ or with 8 vertices?

• Expense in drawing and transformation.

• Triangle strips help to some extent.

• Element arrays provide general solution.

• Define (transmit) array of vertices, colors, normals.

• Draw using index into array(s):

  • // (must first set up the GL_ELEMENT_ARRAY_BUFFER)

  • …

  • glDrawElements(GL_TRIANGLES, 36, GL_UNSIGNED_INT, 0);

• Vertex sharing for efficient operations.

• Extra credit for first assignment.

GLUT Program with Callbacks

• Initialization

• START

• Idle()

• Display()

• Keyboard(..)

• Menu(..)

• Reshape(..)

• Motion(..)

• Mouse(..)

• END

• Main event loop

Main Event Loop

• Standard technique for interaction (GLUT, Qt, wxWidgets, …)

• Main loop processes events

• Dispatch to functions specified by client

• Callbacks also common in operating systems

• “Poor man’s functional programming”

Types of Callbacks

• Display ( ): when window must be drawn

• Idle ( ): when no other events to be handled

• Keyboard (unsigned char key, int x, int y): key pressed

• Menu (...): after selection from menu

• Mouse (int button, int state, int x, int y): mouse button

• Motion (...): mouse movement

• Reshape (int w, int h): window resize

• Any callback can be NULL

Screen Refresh

• Common refresh rates: 60-100 Hz

• Flicker if drawing overlaps screen refresh

• Problem during animation

• Solution: use two separate frame buffers:

  • Draw into one buffer

  • Swap and display, while drawing into the other buffer

• Desirable frame rate >= 30 fps (frames/second)

Enabling Single/Double Buffering

• glutInitDisplayMode(GLUT_SINGLE);

• glutInitDisplayMode(GLUT_DOUBLE);

• Single buffering: Must call glFinish() at the end of Display()

• Double buffering: Must call glutSwapBuffers() at the end of Display()

• Must call glutPostRedisplay() at the end of Idle()

• If something in OpenGL has no effect or does not work, check the modes in glutInitDisplayMode

Hidden Surface Removal

• Classic problem of computer graphics

• What is visible after clipping and projection?

• Object-space vs image-space approaches

• Object space: depth sort (Painter’s algorithm)

• Image space: z-buffer algorithm

• Related: back-face culling

Object-Space Approach

• Consider objects pairwise

• Painter’s algorithm: render back-to-front

• “Paint” over invisible polygons

• How to sort and how to test overlap?

Depth Sorting

• First, sort by furthest distance z from viewer

• If minimum depth of A is greater than maximum depth of B, A can be drawn before B

• If either x or y extents do not overlap, A and B can be drawn independently

Some Difficult Cases

• Sometimes cannot sort polygons!

• One solution:

  • compute intersections

  • subdivide

• Do while rasterizing (difficult in object space)

Painter’s Algorithm Assessment

• Strengths

  • Simple (most of the time)

  • Handles transparency well

  • Sometimes, no need to sort (e.g., heightfield)

• Weaknesses

  • Clumsy when geometry is complex

  • Sorting can be expensive

• Usage

  • PostScript interpreters

  • OpenGL: not supported (must implement Painter’s Algorithm manually)

Image-space approach

• Raycasting: intersect ray with polygons

• $O(k)$ worst case (often better)

• Images can be more jagged (need anti-aliasing)

The z-Buffer Algorithm

• z-buffer stores depth values z for each pixel

• Before writing a pixel into framebuffer:

  • Compute distance z of pixel from viewer

  • If closer, write and update z-buffer, otherwise discard

z-Buffer Algorithm Assessment

• Strengths

  • Simple (no sorting or splitting)

  • Independent of geometric primitives

• Weaknesses

  • Memory intensive (but memory is cheap now)

  • Tricky to handle transparency and blending

  • Depth-ordering artifacts

• Usage

  • z-Buffering comes standard with OpenGL; disabled by default; must be enabled

Depth Buffer in OpenGL

• glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGBA | GLUT_DEPTH);

• glEnable (GL_DEPTH_TEST);

• Inside Display(): glClear (GL_DEPTH_BUFFER_BIT);

• Remember all of these!

• Some “tricks” use z-buffer in read-only mode

Note for Mac computers

• Must use the GLUT_3_2_CORE_PROFILE flag to use the core profile:

• glutInitDisplayMode(GLUT_3_2_CORE_PROFILE | GLUT_DOUBLE | GLUT_RGBA | GLUT_DEPTH);

Summary

• Client/Server Model

• Callbacks

• Double Buffering

• Physics of Color

• Flat vs Smooth Shading

• Hidden Surface Removal

Lecture 5: Transformations

• Vector Spaces

• Euclidean Spaces

• Frames

• Homogeneous Coordinates

• Transformation Matrices ([Angel, Ch. 3])

OpenGL Transformations

• OpenGL Transformation Matrices

  • Model-view matrix (4x4 matrix)

  • Projection matrix (4x4 matrix)

• Model-view à Projection

  • vertices in 3D (object space) à vertices in the camera coordinate system à vertices in 2D

4x4 Model-view Matrix (this lecture)

• Translate, rotate, scale objects

• Position the camera

• Model-view à Projection

  • vertices in 3D (object space) à vertices in the camera coordinate system à vertices in 2D

4x4 Projection Matrix (next lecture)

• Project from 3D to 2D

• Model-view à Projection

  • vertices in 3D à vertices in canonical 3D world coordinate system à vertices in 2D

4x4 Model-view Matrix (this lecture)

• Translate, rotate, scale objects in world space

• Position and orient the camera

• Transform the World

4x4 Model Matrix

• Translate, rotate, scale objects in world space

4x4 View Matrix

• Position and orient the camera

• From world space to camera space

OpenGL Transformation Matrices

• Manipulated separately in OpenGL

• Core profile: set them directly

• Compatibility profile: must set matrix mode

  • glMatrixMode (GL_MODELVIEW);

  • glMatrixMode (GL_PROJECTION);

• Model-view à Projection

Setting the Modelview Matrix: Core Profile

• Set identity:

  • openGLMatrix.SetMatrixMode(OpenGLMatrix::ModelView);

  • openGLMatrix.LoadIdentity();

• Use openGLMatrix library functions:

  • openGLMatrix.Translate(dx, dy, dz);

  • openGLMatrix.Rotate(angle, vx, vy, vz);

  • openGLMatrix.Scale(sx, sy, sz);

• Upload m to the GPU:

  • float m[16]; // column-major

  • openGLMatrix.GetMatrix(m);

  • GLboolean isRowMajor = GL_FALSE;

  • pipelineProgram->SetUniformVariableMatrix4fv( "modelViewMatrix", isRowMajor, m);

Setting the Modelview Matrix: Compatibility Profile

• Load or post-multiply

  • glMatrixMode (GL_MODELVIEW);

  • glLoadIdentity(); // very common usage

  • float m[16] = { … }; glLoadMatrixf(m); // rare, advanced

  • glMultMatrixf(m); // rare, advanced

• Use library functions

  • glTranslatef(dx, dy, dz);

  • glRotatef(angle, vx, vy, vz);

  • glScalef(sx, sy, sz);

Translated, rotated, scaled object

• Initially (after LoadIdentity()): rendering coordinate system = world coordinate system

The rendering coordinate system

• Translate(x, y, z):

The rendering coordinate system

• Rotate(angle, ax, ay, az):

The rendering coordinate system

• Scale(sx, sy, sz):

OpenGL pseudo-code

• MatrixMode(ModelView); LoadIdentity();

• Translate(x, y, z);

• Rotate(angle, ax, ay, az);

• Scale(sx, sy, sz);

• glUniformMatrix4fv(…); renderBunny();

Rendering more objects

• How to obtain this frame?

• Solution 1: Find Translate(…), Rotate(…), Scale(…)

• Solution 2: LoadIdentity(); Find Translate(…), Rotate(…), Scale(…)

3D Math Review

Scalars

• Scalars $α, β, γ$ from a scalar field

• Operations $α+β, α ! β, 0, 1, -α, ()^{-1}$

• “Expected” laws apply

• Examples: rationals or reals with addition and multiplication

Vectors

• Vectors $u, v, w$ from a vector space

• Vector addition $u + v$, subtraction $u - v$

• Zero vector $0$

• Scalar multiplication $α v$

Euclidean Space

• Vector space over real numbers

• Three-dimensional in computer graphics

• Dot product: $α = u ! v = u<em>1 v</em>1 + u<em>2 v</em>2 + u<em>3 v</em>3$

• $0 ! 0 = 0$

• $u, v$ are orthogonal if $u ! v = 0$

• $|v|^2 = v ! v$ defines $|v|$, the length of $v$

Lines and Line Segments

• Parametric form of line: $P(α) = P_0 + α d$

• Line segment between Q and R: $P(α) = (1-α) Q + α R$ for $0 ≤ α ≤ 1$

Convex Hull

• Convex hull defined by $P = α<em>1 P</em>1 + … + α<em>n P</em>n$ for $α<em>1 + … + α</em>n = 1$ and $0 ≤ α_i ≤ 1, i = 1, …, n$

Projection

• Dot product projects one vector onto another vector

• $u ! v = u<em>1 v</em>1 + u<em>2 v</em>2 + u<em>3 v</em>3 = |u| |v| cos(θ)$

• $pr_v u = (u ! v) v / |v|^2$

Cross Product

• $|a x b| = |a| |b| |sin(θ)|$

• Cross product is perpendicular to both a and b

• Right-hand rule

Plane

• Plane defined by point $P_0$ and vectors $u$ and $v$

• $u$ and $v$ should not be parallel

• Parametric form: $T(α, β) = P_0 + α u + β v$ ($α$ and $β$ are scalars)

• $n = u x v / |u x v|$ is the normal

• $n ! (P – P_0) = 0$ if and only if $P$ lies in plane

Coordinate Systems

• Let $v<em>1, v</em>2, v_3$ be three linearly independent vectors in a 3-dimensional vector space

• Can write any vector $w$ as $w = α<em>1 v</em>1 + α<em>2 v</em>2 + α<em>3 v</em>3$ for some scalars $α<em>1, α</em>2, α_3$

Frames

• Frame = origin $P_0$ + coordinate system

• Any point $P = P<em>0 + α</em>1 v<em>1 + α</em>2 v<em>2 + α</em>3 v_3$

In Practice, Frames are Often Orthogonal

• Representing 3D transformations (and model-view matrices)

Linear Transformations

• $3 x 3$ matrices represent linear transformations

• $a = Mb$

• Can represent rotation, scaling, and reflection

• Cannot represent translation

In order to represent rotations, scales AND translations: Homogeneous Coordinates

• Augment $[α<em>1 α</em>2 α<em>3]^T$ by adding a fourth component (1): $p = [α</em>1 α<em>2 α</em>3 1]^T$

• Homogeneous property:

  • $p = [α<em>1 α</em>2 α<em>3 1]^T = [bα</em>1 bα<em>2 bα</em>3 b]^T$, for any scalar $b ≠ 0$

• Homogeneous coordinates are transformed by 4x4 matrices

• p -> q where $q = A p$

  • $4-vector$ à $4-vector$

  • $world$ à $4x4 matrix$

Affine Transformations (4x4 matrices)

• Translation

• Rotation

• Scaling

• Any composition of the above

• Later: projective (perspective) transformations - Also expressible as 4 x 4 matrices!

Translation

• $q = p + d$ where $d = [α<em>x α</em>y α_z 0]^T$

• $p = [x y z 1]^T$

• $q = [x’ y’ z’ 1]^T$

• Express in matrix form q = T p and solve for T

Scaling

• $x’ = β_x x$

• $y’ = β_y y$

• $z’ = β_z z$

• Express as $q = S p$ and solve for $S$

Rotation in 2 Dimensions

• Rotation by $θ$ about the origin

• $x’ = x cos θ – y sin θ$

• $y’ = x sin θ + y cos θ$

• Express in matrix form:

  • Note that the determinant is 1

Rotation in 3 Dimensions

• Orthogonal matrices: $R R^T = R^T R = I$ det($R$) = 1

• Affine transformation:

Affine Matrices are Composed by Matrix Multiplication

• $A = A<em>1 A</em>2 A_3$

• Applied from right to left

• $A p = (A<em>1 A</em>2 A<em>3) p = A</em>1 (A<em>2 (A</em>3 p))$

• Compatibility mode:

  • When calling glTranslate3f, glRotatef, or glScalef, OpenGL forms the corresponding 4x4 matrix, and multiplies the current modelview matrix with it.

Summary

• OpenGL Transformation Matrices

• Vector Spaces

• Frames

• Homogeneous Coordinates

• Transformation Matrices

Lecture 6: Viewing and Projection

• Shear Transformation

• Camera Positioning

• Simple Parallel Projections

• Simple Perspective Projections ([Angel, Ch. 4])

Reminder: Affine Transformations

• Given a point $(x, y, z)$, form homogeneous coordinates $(x, y, z, 1)$.

• The transformed point is $(x’, y’, z’)$.

Transformation Matrices in OpenGL

• Transformation matrices in OpenGL are vectors of 16 values (column-major matrices)

• Some books transpose all matrices!

• $m = {m<em>1, m</em>2, …, m_{16}}$

Shear Transformations

• $x$-shear scales $x$ proportional to $y$

• Leaves $y$ and $z$ values fixed

Specification via Shear Angle

• $cot(q) = (x’-x) / y$

• $x’ = x + y cot(q)$

• $y’ = y$

• $z’ = z$

Specification via Ratios

• For example, shear in both $x$ and $z$ direction

• Leave $y$ fixed

• Slope $a$ for $x$-shear, $g$ for $z$-shear

• Solve

• Yields

Composing Transformations

• Let $p = A q$, and $q = B s$.

• Then $p = (A B) s$.

• Fact: Every affine transformation is a composition of rotations, scalings, and translations

• So, how do we compose these to form an $x$-shear?

• Exercise!

Transform Camera = Transform Scene

• Camera position is identified with a frame

• Either move and rotate the objects

• Or move and rotate the camera

• Initially, camera at origin, pointing in the negative $z$-direction

The Look-At Function

• Convenient way to position camera

• OpenGLMatrix::LookAt(ex, ey, ez, fx, fy, fz, ux, uy, uz); // core profile

• gluLookAt(ex, ey, ez, fx, fy, fz, ux, uy, uz); // compatibility profile

• e = eye point

• f = focus point

• u = up vector

OpenGL code (camera positioning)

• void display() {

  • glClear (GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);

  • openGLMatrix.SetMatrixMode(OpenGLMatrix::ModelView);

  • openGLMatrix.LoadIdentity();

  • openGLMatrix.LookAt(ex, ey, ez, fx, fy, fz, ux, uy, uz);

  • openGLMatrix.Translate(x, y, z); // (if needed) apply transforms

  • ...

  • float m[16]; // column-major

  • openGLMatrix.GetMatrix(m); // fill “m” with the matrix entries

  • `pipelineProgram->SetUniformVariableMatrix4fv(

Lecture 6 covers Viewing and Projection. The topics include: Shear Transformation, Camera Positioning, Simple Parallel Projections, Simple Perspective Projections. It refers to [Angel, Ch. 4] for more details