CHAPTER 7 - Implementation 2

Objectives

Introduce clipping algorithms for polygons
Survey hidden-surface algorithms

Polygon Clipping (can use C- S or L- B for polygons on an edge by edge basis)

Not as simple as line segment clipping
- Clipping a line segment yields at most one line segment
- Clipping a polygon can yield multiple polygons (or a reconstruction of the unclipped segments as one polygon)

However, clipping a convex polygon can yield at most one other polygon

Tessellation and Convexity

One strategy is to replace nonconvex (concave) polygons with a set of triangular polygons (a tessellation)
- Also makes fill easier
- Tessellation code in GLU library

Clipping as a Black Box

Can consider line segment clipping as a process that takes in two vertices and produces either no vertices or the vertices of a clipped line segment

Pipeline Clipping of Line Segments (Sutherland and Hodgeman Algorithm)

Clipping against each side of window is independent of other sides
- Can use four independent clippers in a pipeline (performed in hardware - working on 4 vertices concurrently)

Pipeline Clipping of Polygons

Three dimensions: add front and back clippers
Strategy used in SGI Geometry Engine
Small increase in latency

Bounding Boxes

Rather than doing clipping on a complex polygon, we can use an axis-aligned bounding box or extent
- Smallest rectangle aligned with axes that encloses the polygon
- Simple to compute: max and min of x and y
- So important most Modelers compute the bounding box and store with the object

Bounding boxes

Can usually determine accept/reject based only on bounding box

Clipping and Visibility

Clipping has much in common with hidden-surface removal
In both cases, we are trying to remove objects that are not visible to the camera
Often we can use visibility or occlusion testing early in the process to eliminate as many polygons as possible before going through the entire pipeline

Hidden Surface Removal

Object-space approach such as used in Ray Tracing: use pairwise testing between polygons (objects)

Worst case complexity O(n²) for n polygons

Painters Algorithm

• The painter's algorithm requires no additional buffer space, just the frame buffer.
• All objects are sorted in z from back to front => there are some tricky tests required if polygons overlap.
• Objects are then written into the frame buffer from back to front, i.e. the way a painter paints objects on a canvas.
• A simple, easy to implement algorithm but terribly inefficient since all front facing polygons are processed whether visible or not.

Depth Sort

Requires ordering of polygons first
- O(n log n) calculation for ordering
- Not every polygon is either in front or behind all other polygons
Order polygons and deal with easy cases first, harder later

Easy Cases

A lies behind all other polygons
- Can render

Polygons overlap in z but not in either x or y

Can render independently

Hard Cases

Image Space Approach

Look at each projector (nm for an n x m frame buffer) and find closest of k polygons
Complexity O(nmk)
Ray tracing
z-buffer

Z-Buffer Algorithm Catmull 1974(compatible with object space or image space approaches - used by OpenGL)

The z-buffer or depth buffer algorithm is probably the most popularly implemented hidden surface elimination algorithm. It is intuitively simple to understand and quite easy to implement. The algorithm is an image precision algorithm developed for raster systems. OpenGL performs visibility testing using a depth buffer.

We know that color information for each pixel to be displayed is stored in a frame buffer. The z-buffer has the same number of entries as the frame buffer, but stores Z values for each pixel.

• The z-buffer entries are initialized with the z value of the back clipping plane of the specified view volume.
• The largest z value that can be stored in the buffer is the z value of the front clipping plane.
• The frame buffer entries are initialized to the screen background color.

Scan conversion of fragments proceeds (the 2D case is yet to be discussed)
• but now the z value of each point x, y is compared to the z value stored in the buffer for that point.
• If the fragment's z value is >= the buffer value then the buffer is updated with the fragment's z value and the frame buffer is updated with the fragment's color.
• Otherwise no updates take place.

To determine the relevant z values across a polygon span that lies along a scan line one can use linear interpolation (using the z values of the spans two endpoints). Linear interpolation can also be used over the set of scanlines intersected by the polygon's left and right edge.

The scan conversion algorithm sorts polygon spans using a y-bucket sort:
• All spans are sorted in y first.
• Each y-bucket(i) holds the set of spans that become active on scanline(i).
• The spans within each bucket are sorted in x.
• If we additionally perform a rough sort in z the algorithm is quite efficient.
• The z-sort is performed on objects in a front to back order so that front objects will be drawn into the frame buffer first.
• Thus the time consuming shading computation will never need to be performed for objects obscured by those closer to the observer.

The z-buffer algorithm is typically implemented in hardware.

The z-buffer can also be saved, along with the frame buffer, and then used to merge in other objects => no need to recompute the whole image for partial scene updates.

Efficiency (Linear Interpolation of depth values vs. using the polygon's plane equation)

A convex polygon is part of a plane, ax + by + cz + d = 0
- Given two points on the polygon (and the plane) define Dx = x2 - x1, Dy = y2 - y1, Dz = z2 - z1 and the equation for the plane in differential form is aDx + bDy + cDz = 0
If we work scan line by scan line as we move across a scan line, the depth changes satisfy aDx+bDy+cDz=0

The value for Dz is a constant and is computed once per polygon

Scan-Line Algorithm

The scan-line algorithms for lines and circles (Bresenham's midpoint algorithms) have been discussed previously. This section deals with polygons only.

Filling Rectangles

In general, to fill a rect, the algorithm must determine which scan lines intersect the rect and move thru the scanlines sequentially filling in spans of pixels within the rect from left to right.

Spans take advantage of several types of coherence that frequently occur within a scene to be displayed

• Spatial Coherence : pixels tend to remain the same within a span or from scanline to scanline.
• Span coherence : for a solidly colored polygon, all pixels on the span have the same color.
• Scanline coherence : for a solidly colored polygon, all scan lines that intersect the polygon are identical.
• Edge Coherence : for general polygons, the intersection of an edge with a scan line tends to change only incrementally in x, y.

Being able to write spans to the frame buffer is considerably more efficient than writing on a by pixel basis.
The general pseudo-code for rectangles is:

for (y from ymin to ymax of rectangle)

for( x from xmin to xmax)

WritePixel(x,y,color)

A problem arises in this solution if rects ( or polygons in general) share a boundary edge. In many cases it makes no difference if the edge is drawn twice (never efficient). But if XOR mode is used then pixels could disappear or be strangely colored. Thus for shared edges it becomes necessary to identify the polygon which owns an edge so it is only drawn once.

One rule that is frequently used for a boundary pixel : the pixel is not considered part of the primitive if the half plane defined by the edge and containing the primitive lies below or to the left of the edge.

Thus pixels on the left and bottom edge are drawn, while those on the right and top are not. A shared vertical edge belongs to the rightmost of two sharing polygons.

Still problems with this rule : bottom left pixel drawn twice (special rule), each span is missing rightmost pixel, each polygon is missing top row.

Filling Polygons

The general polygon scan-conversion algorithm handles convex, concave, self-intersecting polygons, or polygons with interior holes.

Span extrema of a polygon are calculated using an incremental algorithm. The incremental algorithm computes the intersection of a scan line and a polygonal edge based on the intersection (if any) of the polygon with the previous scan line. To compute the intersections analytically would be inefficient. Look at below figure to visualize spans and span extrema.

Once the spans on a scanline are identified, it is necessary to determine which spans are inside the polygon (to be drawn) and which are outside the polygon (not to be drawn). This is a three step process :

Find the intersection of scanline with all polygon edges.
Sort the intersections by increasing x coordinate.
Fill in pixels between pairs of intersections that are inside the polygon. Use the odd-parity rule to do so. Parity is initially set to even for each scanline. When a span intersection is encountered invert the parity bit. Draw only when parity is odd. Look at figure and discuss odd-parity rule.

Steps 1) and 2) discussed later. Step 3 is elaborated below.

3.1 If the intersection is a fractional x value how do we determine which pixel on either side of the intersection is interior to the polygon? We can apply the odd-parity rule here as - if approaching the fractional intersection from the left and we are inside the polygon then round down, if we are outside the polygon then round up. This ensures that the resulting integer x coordinate is always interior to the polygon.

3.2 How do we deal with the special case of intersections at an integer pixel coordinate? Use the same rule as applied to shared edges of rectangles - if the coordinate is a left edge it is interior to the polygon, if it is a right edge then it is outside the polygon.

3.3 How do we deal with the special case in 3.2) of shared vertices? Use the rule that all edges and spans are treated as intervals that are closed at their minimum value and open at their maximum value. To visualize this look at the figure and imagine a scanline that intersects the polygon at A. We identify two intersections, one with line FA at its ymin value and one at AB at its ymax value. If we allow these two intersections to define a span (of one pixel) then our odd-parity rule would not work. Parity would be odd for the FA intersection (so draw pixel) but becomes even for the AB intersection and the remaining pixels along the span within the polygon are not drawn.

Thus, when encountering a shared vertex, count the ymin vertex as an intersection in the odd-parity rule. Do not count the ymax vertex as an intersection in the odd parity rule.

3.4 How do we deal with the special case in 3.2) of a horizontal edge? We use the same rule as for filling rectangles - bottom edges are draw, top edges are not. Look at simple example using a rectangle.

What happens when a scanline intersects only a vertex of the polygon? at a local minima? at a local maxima?

Horizontal Edges

As stated previously, when considering horizontal edges, we do not count their vertex intersection (for the odd-parity rule) with the scanline. Use figure to visualize.

Examine horizontal edges AB, CD whose spans start on lines JA, IJ and whose spans end on CB, and DE. The above rules work nicely for this example.

The algorithm is not perfect, it does omit pixels and does not totally avoid redrawing shared vertices.

Slivers

When displaying multiple polygons, it is possible that the polygons may be sufficiently close to create a polygonal sliver. Slivers are very small polygons whose interior area does not contain a distinct span for each scanline. Because of the size of the polygon and the left, bottom edge rule many scanlines may contain only a single pixel or none at all. This is an example of an aliasing artifact.

Edge Coherence for Scanline Algorithm that Fills Polygons (~openGL algorithm but defined only for convex polygons)

Step 1 requires calculating intersections of edges and the scanline. We don't want to do this analytically because of the inefficiency. Instead we can take advantage of edge coherence - the fact that once an edge intersects a scanline it probably intersects adjacent scanlines. Edge coherence occurs along an edge for as many scanlines as intersect the edge. We also want to identify only those edges that intersect a scanline...we don't want to test every edge in the polygon for intersection.

If we examine the endpoints of an edge it is possible to identify the ymax and ymin of the edge. This gives us the interval of scanlines which will intersect the edge. It also gives us the starting scanline and the ending scanline of the interval.

Assume we consider only left edges with m > 1. Right edges and other slopes are handled by similar more complicated arguments. Vertical edges are a special case while horizontal edges are handled by the span rules discussed earlier.

Thus x intersections along a scanline can be computed based on the old x intersection (as in the midpoint scan conversion algorithm) by using

i+1 = x_i + 1/m where m is the slope of the line. As y is incremented thru the scanlines, the x intersection increases by 1/m.

Because x increases by 1/m, the new x intersection will result in an integer + fractional part. ie. if slope = 5/2 and start x at 2, then the sequence is 2, 2+2/5, 2+4/5, 2+6/5 = 3+1/5, ...

When the fractional part of x = 0 then we draw (x, y) which lies on the line. When the fractional part is non-zero we need to round up to produce an x value that lies inside the polygon. When the fractional part becomes > or = 1 then we need to increment x and subtract 1 from the fractional part. We also need to move x one pixel to the right by rounding for the > case, rounding doesn't affect the = case.

We can avoid the fractions by noting that the denominator of the fractional part = ymax - ymin (defined by the y endpoints of the edge). We can just keep track of the numerator thru successive iterations. When the numerator overflows the denominator then increment x and decrement the numerator by the denominator.

The algorithm needs a data structure to keep track of active edges, called the AET, or active edge table. Active edges in the table are sorted by their x intersection value (in increasing order) so that spans and span extrema are easily identified.

Lets say the algorithm is currently at scanline y_i.

First, remove all edges no longer active : y_max < y_i.
Add new active edges : y_min = y_i
Calculate new x intersections for all active edges using incremental algorithm.

In order to identify new active edges, a global edge table (ET) is managed. Edges in the table are sorted by their ymin value. The ET is built using a y-bucket sort : number of entries in ET is equal to number of scanlines (the y buckets). Each y-bucket points to a list of edge entries. Thus bucket i represents scanline i and points to the list of edges that become active on scanline i. An edge entry should minimally contain the ymax, xmin, and slope of the edge (and a flag indicating a left or right edge). Actually more complicated for multiple polygons. Within the list, edge entries are sorted by xmin in increasing order. Why isn't the xmax coordinate stored?

The steps of the algorithm follow :

1. Set y = to smallest non-empty cell of ET.

2. Initialize AET to empty.

3. Repeat until ET and AET are empty.

3.1 Move entries from ET bucket y to AET (newly active edges).

3.2 Remove from AET all edge entries whose y_max < y (inactive edges). Sort AET on x (easy because ET is presorted, O(n)).

3.3 Fill pixels on scanline y using pairs of x coordinates from AET (by computing spans and using rules discussed previously).

3.4 Increment y.

3.5 For each non-vertical edge, update x for new y.

Note that for the general case of convex and concave polygons, scanline conversion is complicated by the fact that multiple spans may exist for one polygon. We can simplify scanline conversion if all polgons are triangles. Why?

A triangle will have only a single span on any scanline. Any polygon can be constructed from a mesh of triangles and simple convex polygons (easy for convex, harder for concave) through a process called tessellation. Many scanline algorithms require or apply a preprocessing tessellation step to remove many of the special cases we have seen in this algorithm.

Visibility Testing

In many real time applications, such as games, we want to eliminate as many objects as possible within the application
- Reduce burden on pipeline
- Reduce traffic on bus
Partition space with Binary Spatial Partition (BSP) Tree

Simple Example

BSP Tree

Can continue recursively
- Plane of C separates B from A
- Plane of D separates E and F
Can put this information in a BSP tree
- Use for visibility and occlusion testing