Today’s Topics
Image primitives: Lines
• DDA line drawing algorithm
• Bresenham’s algorithm
• Midpoint algorithm for drawing circles
• Anti-aliasing techniques |
2D Drawing
Common geometric primitives:
When drawing a picture, 2D geometric primitives
are
specified as if they are drawn on a continuous plane
In reality , photo graphs are arrays of
pixels, not abstract
mathematical continuous planes
In graphics, the conversion from continuous to
discrete 2D
primitives is called scan conversion or rasterization |
2D Primitives from Digital Photographs
In its basic form, 2D primitive extraction is performed by a
process called edge detection
|
|
Edge pixel |
 |
|
2-Lecture Outline
Today:
• Focus on 2D drawing basics
Drawing straight lines, circles, etc
Next time:
• Focus on edge detection basics
• Case study: Creating painterly effects by combining
edge detection & line drawing
 |
2D Drawing: Basic Steps
1. Scan conversion (for 2D lines)
Given a pair of pixels defining the line’s endpoints & a
color, paint all pixels that lie on the line |
2. Clipping (for 2D lines)
If one or more endpoints is out of bounds, paint only the
line segment that is within bounds
3. Region filling (will revisit in 2 lectures)
|
Today’s Topics
Drawing digital lines & other curves
• DDA line drawing algorithm
• Bresenham’s algorithm
• Midpoint algorithm for drawing circles
• Anti-aliasing techniques |
Line Scan Conversion: Key Objectives
Accuracy
Pixels should approximate
line as closely as possible |
Digital line
 |
• Speed
Line drawing should be as
efficient as possible |
• Visual quality
No discernible “artifacts” |
|
Line Equations
How do we re present the set of all points lying on a single
line?
|
Continuous line |
Line that passes through points
 and
 satisfies
the equation: |
 |
 |
|
Line Drawing: Basic Idea
We need to de termine the pixels that lie closest to the
mathematical line
|
Digital line
 |
Case when 0 < slope < 1
1. Draw pixel at line start
2. Increment x pixel position
by 1
3. Determine the y position
of the pixel lying closest
to the line |
|
The DDA Algorithm
DDA = Digital Differential Analyzer
Idea: Determine the pixel’s y coordinate by evaluating the
change in y position of the ideal line when x increases by 1
|
to
