Point and Line Clipping to Windows

Abstract

This section presents how to limit drawing points and lines to the viewing window and viewpoint being use for display.

Outline

We define the viewing window and show the various examples of clipping. We then show the matrix used to test lines in the Cohen-Sutherland algorithm. Then we present how to find boundary intersections using midpoint subdivision. We then present a number of other techniques, primarily to speed up the operations.

Goals

To provide tools to deal with constraining window and viewports. To give a range of ways to solve the problem and how the knowledge the algorithms use effect speed.

Objectives

You will be able to read and write code for the various algorithms. You will be able to identify how the technique addresses the problem and differs in speed and data structures from the other algorithms.

Prerequest Background

Understanding of raster line drawing techniques.

Content

point clipping
Cohen-Sutherland line clipping

Liang-Barsky line clipping, (this uses a parametric form of a line. For point, P, F(alpha)=P where 0<=alpha<=1. F(alpha) =[alpha * x2 +( 1-alpha)*x1, alpha * y2 + (1-alpha)y1] ) (Convert lines into parametric line formuls. Run the boundry condistions thoruigh the formuls. Check if the line exists at the boundry.) Nicholl-Lee-Nicholl line clipping, (divide space by projections from point to corner points. Determine slope and clip not possible slopes) line clipping using nonrectangular clip windows, splitting convave polygons, (sequences of cross products, change of sign is concave, split on this vector)
polygon clipping
Sutherland-Hodgeman polygon clipping, (clip to the four window sides, one at a time. works for convex polygon, problem for concave)
Weiler-Atherton polygon clipping, (fix for concave, follow either window or polygon depending on direction) other polygon-clipping algorithms, curve clipping, text clipping, exterior clipping the content

Posttest

When you finish this section you should be able to answer questions such as: What are some techniques to clip lines? What method does each technique use to determine when to clip? What are the speed tradeoffs of the techniques?