computer graphics

preparation for the midter

Cohen–Sutherland example: outcode of (5,4) using Top-Bottom-Right-Left order

0000

Cohen–Sutherland example: classify the line from (2,7) to (9,8)

Trivially rejected, because 1001 AND 1010 = 1000 ≠ 0000

Cohen–Sutherland example: classify the line from (2,4) to (6,4)

Clipping required, because 0001 AND 0000 = 0000 but one point is outside

Visible segment of the clipped line from (2,4) to (6,4) with window BL = (3,1), UR = (8,6)

The visible segment is (3,4) to (6,4)

What is the graphics pipeline?

The graphics pipeline is the sequence of stages that transforms a mathematical scene description into the final image on the screen.

What are the main stages of the graphics pipeline?

Object Representation, Modeling Transformation, Lighting, Viewing Transformation, and Scan Conversion.

Simple graphics pipeline example

Object Representation: define a cube. Modeling Transformation: place it in the scene. Lighting: make one face brighter and another darker. Viewing Transformation: project the 3D cube into 2D. Scan Conversion: convert the projected shape into pixels.

What is modeling transformation?

Modeling transformation is the stage where an object is transformed from local coordinates into world coordinates.

Why is modeling transformation important?

Because it places an object in the correct position, size, and orientation in the scene.

What is lighting?

Lighting is the stage where the appearance of an object is determined according to how light interacts with its surface.

Simple lighting example

If a light source is above a cube, the top face appears brighter and the side faces appear darker.

What is scan conversion?

Scan conversion is the process of converting continuous geometric shapes into discrete pixels on the screen.

What is the main problem in scan conversion?

The main problem is aliasing, where edges and lines look jagged on the pixel grid.

How is the scan conversion problem solved?

It is solved using anti-aliasing, which smooths the jagged edges.

How can objects be represented in graphics?

Objects can be represented using point sample representation, boundary representation, space partitioning, and sweep representation.

What are the most important object representation techniques?

Point sample representation, boundary representation, space partitioning, and sweep representation.

How are boundaries represented?

Boundaries are represented by describing the outer surfaces of an object, often with polygon meshes.

What is mesh representation?

Mesh representation is a boundary representation method where an object surface is approximated using polygons.

What is a sweep surface?

A sweep surface is a 3D surface generated by moving a point, line, polygon, or curve along a path in space.

What is a surface of revolution?

A surface of revolution is a special case of a sweep surface created by rotating a 2D curve around an axis.

Example of surface of revolution

Rotating a semicircle around an axis generates a sphere.

What is DDA?

DDA (Digital Differential Analyzer) is a line drawing algorithm that generates intermediate points between two endpoints step by step.

DDA formula for dx and dy

dx = x2 - x1, dy = y2 - y1

DDA formula for steps

steps = max(|dx|, |dy|)

DDA formula for increments

x_inc = dx / steps, y_inc = dy / steps

DDA procedure

Start at (x1, y1), plot the point, then repeatedly add x_inc and y_inc until the final point is reached.

DDA example: line from (2,2) to (6,4) — increments

x_inc = 1, y_inc = 0.5

DDA example: line from (2,2) to (6,4) — points

(2,2), (3,2.5), (4,3), (5,3.5), (6,4)

What is Bresenham’s line drawing algorithm?

Bresenham’s line drawing algorithm is a fast line rasterization algorithm that uses integer arithmetic and a decision parameter.

Why is Bresenham line faster than DDA?

Because it avoids floating-point calculations and uses integer updates.

What is the decision parameter formula for Bresenham line when m < 1?

P0 = 2dy - dx

In Bresenham line for m < 1, what happens if Pk < 0?

Choose the East pixel: x(k+1) = xk + 1, y(k+1) = yk, and P(k+1) = Pk + 2dy

In Bresenham line for m < 1, what happens if Pk >= 0?

Choose the North-East pixel: x(k+1) = xk + 1, y(k+1) = yk + 1, and P(k+1) = Pk + 2dy - 2dx

Bresenham line example: line from (2,2) to (8,5) — initial decision parameter

P0 = 0

Bresenham line example: line from (2,2) to (8,5) — final plotted points

(2,2), (3,3), (4,3), (5,4), (6,4), (7,5), (8,5)

What is Bresenham’s circle drawing algorithm?

Bresenham’s circle drawing algorithm is a circle rasterization algorithm that uses a decision parameter and symmetry to choose the next pixel.

What is the starting point in Bresenham circle?

(x0, y0) = (0, r)

What is the initial decision parameter in Bresenham circle?

P0 = 3 - 2r

In Bresenham circle, what happens if Pk < 0?

Move to (xk + 1, yk) and update with P(k+1) = Pk + 4x(k+1) + 6

In Bresenham circle, what happens if Pk >= 0?

Move to (xk + 1, yk - 1) and update with P(k+1) = Pk + 4(x(k+1) - y(k+1)) + 10

When do we stop in Bresenham circle?

We stop when x >= y.

Bresenham circle example for r = 5 — starting point and P0

Start at (0,5) with P0 = -7

Bresenham circle example for r = 5 — first-octant points

(0,5), (1,5), (2,4), (3,3)

Can 2D transformations appear in the exam?

Yes. The exam may include translation, scaling, rotation, reflection, and shearing.

What is a 2D transformation?

A 2D transformation is an operation that changes the position, size, orientation, or shape of an object in the 2D plane.

2D translation formulas

x' = x + Tx, y' = y + Ty

2D scaling formulas

x' = Sx * x, y' = Sy * y

2D rotation formulas

x' = x cosθ - y sinθ, y' = x sinθ + y cosθ

Reflection about the x-axis

(x, y) -> (x, -y)

Reflection about the y-axis

(x, y) -> (-x, y)

X-shear formula

x' = x + shx * y, y' = y

Y-shear formula

x' = x, y' = y + shy * x

What is clipping?

Clipping is the process of removing the part of an object outside the clipping window and keeping the visible part inside it.

What is point clipping?

Point clipping checks whether a point lies inside or outside a clipping window.

Point clipping condition

A point is inside if xmin

What is line clipping?

Line clipping determines which part of a line segment is visible inside a clipping window.

What is the Cohen–Sutherland line clipping algorithm?

Cohen–Sutherland is a line clipping algorithm that divides the plane into 9 regions and assigns a 4-bit outcode to each endpoint.

What is an outcode in Cohen–Sutherland?

An outcode is a 4-bit code that indicates whether a point is above, below, to the right, or to the left of the clipping window.

How does Cohen–Sutherland trivially accept a line?

If both endpoint outcodes are 0000, the line is completely inside the clipping window.

How does Cohen–Sutherland trivially reject a line?

If the bitwise AND of the two endpoint outcodes is not 0000, the line is completely outside on a common side.

When is clipping required in Cohen–Sutherland?

If the AND is 0000 but at least one endpoint is outside, the line is partially visible and clipping is required.

Example clipping window

BL = (3,1), UR = (8,6)

For window BL = (3,1), UR = (8,6), is point (3,6) inside or outside?

Inside

For window BL = (3,1), UR = (8,6), is point (9,5) inside or outside?

Outside

Cohen–Sutherland outcode of (5,8) using Top-Bottom-Right-Left order

1000

Cohen–Sutherland outcode of (2,4) using Top-Bottom-Right-Left order

0001

Cohen–Sutherland outcode of (9,4) using Top-Bottom-Right-Left order

0010

Cohen–Sutherland outcode of (2,7) using Top-Bottom-Right-Left order

1001

Cohen–Sutherland outcode of (5,4) using Top-Bottom-Right-Left order

0000

Cohen–Sutherland: classify the line from (2,7) to (9,8)

Trivially rejected, because 1001 AND 1010 = 1000 ≠ 0000

Cohen–Sutherland: classify the line from (2,4) to (6,4)

Clipping required, because 0001 AND 0000 = 0000 but one point is outside

Visible segment of the clipped line from (2,4) to (6,4)

The visible segment is (3,4) to (6,4)