Drawing Algorithms and Viewing

Scan converting lines

Basic incremental algorithm

One way for scan conversion of lines is to compute the slope m as dy/dx, to increment x by 1 starting with the leftmost point, to calculate y_i = mx_i + B for each x_i, and intensify the pixel at (x_i, Round(y_i)), where Round(y_i) = Floor(0.5 + y_i). This computation selects the closest pixel. This approach can be improved by using dy_i+1 = dy_i + m (here dx = 1 for each incremental). The illustration is shown below:

To note: if the slope m < 1, the x, y should be reversed.

Midpoint line algorithm

We assume that the lines' slope m is between 0 and 1. For each point P, we observe the next midpoint M, if M lies above line, we choose E, otherwise we choose NE. If E is chosen, M is incremented by one step in the x direction, otherwise we increase M by one step in each direction. The illustration is shown below:

The line can be written as: y = (dy/dx) * x + B, therefore, F(x,y) = dy*x - dx*y + B = 0, F(x,y) is the slope-intercept function.

To apply the midpoint criterion, we need to computer F(M) = F(x_p + 1, y_p + 1/2), if F(M) <>

Scan converting circles

For circles, we can still use incremental algorithm or midpoint algorithm.

Antialiasing

We can find that the results from above algorithm are not so good in most case. To improve the picture quality we apply antialiasing.

Unweighted area sampling

In this technique, we set the pixel intensity proportional to the amount of area covered. The illustration is shown below:

Geometrical Transformations

Affine transformations

Affine transformations have the property of preserving parallelism of lines.

2D Affine transformations

Using homogeneous coordinates, the 2D affine transformations are, respectively,

Translation:

Rotation:

Scaling:

Shear(combination of Rotation and scaling):

Please note the above transformations we use a convention of post-multiplying by column vectors, while the convention of premultiplying by row vectors is used in other places. Matrices must be transposed to go from one convention to another:

(P * M)^T = M^T * P^T

3D affine transformations

Translation:

Rotation:

Scaling:

Planar geometric projections

A thorough review can be found here.

Perspective Projections

Determined by Center of Project

Parallel Projections

Determined by Direction of Projection

Image Courtesy of Brown University

Orthographic projections

Top, Front, Side

Image Courtesy of Brown University

Axonometric (projection plane is not parallel to any of the coordinates planes. For isometric projection, angles between all three principle axes are equal)

Image Courtesy of Brown University

Perspective Projection

Image courtesy of Brown University

Representing Curves and Surfaces

Polygon Meshes

Parametric cubic curves

x(t) = a_xt³ + b_xt² + c_xt + d_x,

y(t) = a_yt³ + b_yt² + c_yt + d_y,

z(t) = a_zt³ + b_zt² + c_zt + d_z, 0 ≤ t ≤ 1

Hermite Curves

Bézier Curves

Uniform Non rational B-Splines

Non Uniform Non Rational B-Splines

Non Uniform Rational B-Splines (NURBS)

Parametric Bi-cubic Surfaces

Hermite surfaces

Bézier Surfaces

B-Spline Surfaces