This flashcard is just one of a free flashcard set. See all flashcards!

A line with integer-valued endpoints should be rasterized. W.l.o.g., we assume and (we can rotate / flip our pixel grid to fulfill these conditions).

The line is rasterized by starting with a point on the line at , and successively shifting to the right
,
or to the top right
.
This decision is made based on whether the line passes above or below the midpoint

between and .

This condition can be checked by deriving an implicit representation of the line . By taking , we can define a normal to as

and thus derive the implicit representation
.

In order to decide whether to go East or Northeast, we introduce a decision variable, which is initially
.

If , we go East:
Update .
Update .

If , we go Northeast:
Update .
Update .

Values for can be doubled, thus using only integer arithmetic.