Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 50 ยท Projects, Practice and Review

Practice: Exercises with Solutions

Twenty graded computer graphics exercises with runnable JavaScript solutions: line and circle algorithms, transforms, clipping, shading, projection and curves.

Reading about algorithms is not the same as writing them. This page gives you twenty exercises, ordered from easy to demanding within each group, that cover the whole course: rasterization algorithms, transformations, clipping, shading and depth, and curves. Every exercise has a solution that you can run and edit right here, and each solution prints a result you can check against the exercise.

The best way to use the page is simple. Read an exercise, close the solution, and try to solve it in your own editor first. Even a failed attempt teaches you more than reading the answer would. Then compare. If your output is different, the printed numbers tell you which step went wrong.

Difficulty is marked with stars: one star for a direct application of a lesson, two for a small design decision, three for a problem that combines ideas.

Group A: Rasterization and filling

  1. (1 star) Lines in any direction. Write bresenham(x0, y0, x1, y1) that returns the list of pixels for lines in all eight octants using integers only. Check the line from (2, 1) to (11, 5): it must contain max(dx, dy) + 1 pixels. Revisit Bresenham's Line Algorithm if you are stuck.
  2. (1 star) Circle with a check. Implement the midpoint circle for radius r using eight-way symmetry and prove it works by measuring the largest distance error of any plotted pixel from the ideal circle. See The Midpoint Circle Algorithm.
  3. (2 stars) Where does the fill leak? Write a stack-based flood fill that takes a flag for 4- or 8-connectivity. Use a diagonal wall and count the filled cells in both modes. See Flood Fill and Boundary Fill.
  4. (2 stars) Count pixels with a scanline. Fill a polygon with the scanline method, sampling at pixel centres, and return the number of pixels. The right triangle with legs of 10 has a known answer. See Scanline Polygon Filling.
  5. (3 stars) Even-odd against nonzero winding. Implement both inside tests and run them on the centre of a pentagram, where the two rules disagree. See Polygons: Types and Representation.
JS Solutions 1 to 5: rasterization and filling

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Group B: Transformations

  1. (1 star) Rotate about a pivot. Build one 3 by 3 matrix that rotates by 90 degrees about the point (3, 2), and apply it to (5, 2). See Homogeneous Coordinates and Matrix Transformations.
  2. (1 star) Order matters. Apply "translate by (4, 0) then rotate 90 degrees" and "rotate then translate" to the point (1, 0). Explain why the results differ.
  3. (2 stars) Invert an affine matrix. Write inverseAffine(M) for a 3 by 3 matrix whose last row is 0 0 1, and verify M * inverse(M) is the identity. See Reflection, Shear and Inverse Transforms.
  4. (2 stars) Window to viewport. Map points from a world window to a screen viewport with the y axis flipped. See Window-to-Viewport Mapping.
  5. (3 stars) Rotation two ways. Rotate (1, 0, 0) by 90 degrees about the z axis with Rodrigues' formula and with a quaternion, and confirm both agree. See 3D Rotation.
JS Solutions 6 to 10: transformations

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Group C: Clipping, lighting and interpolation

  1. (2 stars) Outcodes. Implement Cohen-Sutherland and report, for four lines, whether each is trivially accepted, trivially rejected or clipped (and to what). See Cohen-Sutherland Line Clipping.
  2. (2 stars) Same answers, different method. Implement Liang-Barsky and verify that it returns the same segments as exercise 11. See Liang-Barsky Line Clipping.
  3. (3 stars) Clip a polygon. Clip a triangle against a rectangle with Sutherland-Hodgman, one boundary at a time, and report the vertex count and the area. See Polygon Clipping.
  4. (1 star) Diffuse and specular. For a given normal, light and viewer, compute the Lambert and Phong terms. See Light and Reflection Models.
  5. (2 stars) Barycentric interpolation. Compute the barycentric coordinates of a point in a triangle and use them to interpolate vertex colors. See Triangle Rasterization.
JS Solutions 11 to 15: clipping, lighting and interpolation

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Group D: Projection, depth, curves and fractals

  1. (1 star) Project a point. A camera has a 90 degree vertical field of view and a 4:3 aspect ratio, and the screen is 640 by 480. Where does the view-space point (1, 1, -4) land? See Orthographic and Perspective Projection.
  2. (2 stars) Order independence. Draw two overlapping rectangles, one slanted in depth and one flat, into a small grid with a z-buffer in both orders and show the pictures are identical. See The Z-Buffer Algorithm.
  3. (2 stars) De Casteljau. Evaluate a cubic Bezier curve at t = 0.5 by repeated interpolation, and return the control points of the two halves. See Bezier Curves.
  4. (2 stars) A spline segment. Evaluate a uniform Catmull-Rom segment between its two middle control points. See Parametric Curves and Interpolation.
  5. (3 stars) Escape counts. Write escape(a, b) that returns the iteration at which z = z^2 + c leaves radius 2 (or null after the limit), and test several points. See Project: A Fractal Explorer.
JS Solutions 16 to 20: projection, depth, curves and fractals

Press Run (or Ctrl + Enter) to see the console output here.

No output.

How to keep going

Once the twenty are done, change them. Make exercise 1 draw thick lines, make exercise 4 handle a concave polygon with a horizontal edge, make exercise 13 clip the star from exercise 5 and compare Sutherland-Hodgman's result to the real shape, and make exercise 17 use true triangles with interpolated depth. Then pick one of the projects, A Software 3D Engine or A Ray-Traced Scene, and add a feature of your own. Programs that you extend are programs that you understand.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In exercise 7, why does "translate then rotate" give a different answer than "rotate then translate"?

    Rotation turns points about the origin. After a translation the point is somewhere else, so the rotation carries it along a different circle. Matrix products depend on order.
  2. 2. In exercise 5, the pentagram centre is inside under the nonzero rule but outside under the even-odd rule. Why?

    A winding number of 2 is nonzero, so the point is inside by the nonzero rule, but 2 is even, so the even-odd parity test says outside.
  3. 3. What is the main advantage of Liang-Barsky over Cohen-Sutherland shown in exercises 11 and 12?

    Liang-Barsky narrows a parameter interval [t0, t1] against the four boundaries and computes the endpoints once. Both methods produce the same segment.
  4. 4. In exercise 17, why are the two drawing orders identical?

    At each pixel the z-buffer retains the smallest depth seen, which does not depend on the order the surfaces were drawn.

Summary

  • The twenty exercises cover the course: Bresenham and midpoint algorithms, fills and inside tests, matrix composition and inverses, clipping, lighting, barycentric interpolation, projection, the z-buffer, curves and fractals.
  • Solving an exercise first and comparing with the printed result afterwards is the fastest way to learn.
  • Many exercises are tests in disguise: agreement between two methods (Cohen-Sutherland and Liang-Barsky, Rodrigues and quaternions) is strong evidence that both are right.
  • Extending your solutions, for example with thick lines or concave polygons, turns practice into skill.

When you are ready for questions in the style of a job interview, continue with Computer Graphics Interview Questions.