Scan Converting Concave Polygons

Problems

1. The scan line may intersect more than 2 times and therefore we must sort the x intersections

2. Vertices: we want to fill from 1 to 2 and from 3 to 4, so have vertex count as 2 intersections then each pair of lines is in polygon interior.

But what about this case ? An odd number of of intersections and not all pairs are in interior, e.g., (3 - 4).

Solution: generate 2 intersections only when at a local min or max, else generate only 1 intersection.

How to generate only 1 intersection at some vertices?

Case 1: Check to see if the y coordinate is monotonically decreasing, if yes, then increase y by 1.

Case 2: Check to see if the y coordinate is monotonically increasing, if yes, then decrease y by 1.

In both of the above cases, the vertices will still be plotted but will only be counted once.

Solid Polygon menu
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org