### Parity? What an Odd Concept!

What is parity you ask? **Parity** is a concept used to determine
which pixels lie within a polygon, ie. , which pixels should
be filled for a given polygon.

The Underlying Principle:
Conceptually, the odd parity test entails drawing a line segment
from any point that lies outside the polygon to a point P,
that we wish to determine whether it is inside or outside of the polygon.
Count the number of edges that the line crosses.
If the number of polygon edges crossed is **odd**,
then P lies within the polygon.
Similarly, if the number of edges is even, then P lies outside of
the polygon. There are special ways of counting the edges when the line
crosses a vertex. This will be discussed in the alorithm section.
Examples of counting parity can be seen in the following demonstration.

### Using the Odd Parity Test in the Polygon Fill Algorithm

The odd parity method creates a problem: How do we determine whether a
pixel lies outside of the polygon to test for an inside one, if we cannot
determine whether one lies within or without of
the polygon in the first place?
If we assume our polygon lies entirely within our scene, then the edge
of our drawing surface lies outside of the polygon.

Furthermore, it would not be very efficient to check each point on our
drawing surface to see if it lies within the polygon and, therefore,
needs to be colored.

So, we can take advantage of the fact that for each scan-line we
begin with even parity; we have NOT crossed any polygon edges yet.
Then as we go from left to right across our scanline, we will continue
to have even parity (i.e., will not use the fill color) until we cross
the first polygon edge. Now our parity has changed to odd and we
will start using the fill color.

How long will we continue to use the fill color? Well, our parity
won't change until we cross the next edge. Therefore, we want to
color all of the pixels from when we crossed the first edge until
we cross the next one. Then the parity will become even again.

So, you can see if we have a sorted list of x-intersections of all
of the polygon edges with the scanline, we can simply draw from
the first x to the second, the third to the forth and so on.

Next Page |
Previous Page |
Main Page