Graphics Primitives
• 2D Basics
• Rasterization
• Scan conversion
– Line Drawing Algorithms
– DDA Algorithm
– Bresenham’s Algorithm
Definitions
• Graphics primitives – functions in the
API that describe picture components
• How could we describe an object?
– Typically focus on object shape
– Define an object’s shape with geometric
primitives
– Span of primitives are defined by the API
– What are some types?
• Lines, Triangles, Quadrics, Conic sections,
Curved surfaces
Two Dimensional Images
• Use Cartesian coordinates +Y
• We label the two axes as
– X (horizontal)
– Y (vertical)
Y
• Origin is in the lower left Axis
• How big is the space?
– So what is the image we see
on a screen?
– We call this space the world (0,0) X Axis +X
coordinate system
Partition the space into pixels
1. Define a set of points +Y
(vertices) in 2D space.
2. Given a set of vertices, (2,7) (9,7)
draw lines between
consecutive vertices.
3. If you were writing
OpenGL, about low level
(2,1) (9,1)
calls
+X
Screen Coordinates – references to frame buffer locations
Q: True or Flase: Screen Coordinates == World Coordinates
Absolute and Relative Coordinate
Specifications
+Y
• Absolute coordinates –
location specified as a
(0,6) (7,0)
relationship to the origin
• Relative coordinates –
location specified as a
relationship to other
points
– Good for pen/plotters (2,1) (0,-6)
– Publishing/layout
– Allows for a very object
oriented approach
• we use absolute
coordinates
Specifying a World Coordinate System
in OpenGL
+Y
+X
gluOrtho2D (xmin, xmax, ymin, ymax)
What should our xmin, xmax, ymin,
ymax values be?
Equivalent to the size of the
framebuffer
Q:From
Whata is
geometry
a pixel?point of view,
A square or aapoint?
pixel is a point. Q: Where is (2,1)?
What is a “pixel”
3
0 1 2 3 4 5
But when we think about images, a pixel is a rectangle.
Q: Where is (2,1)? A. The center of a pixel
0 1 2 3 4
Basic OpenGL Point Structure
• In OpenGL, to specify a point:
– glVertex*();
• In OpenGL, some functions require both a dimensionality and a data
type
– glVertex2i(80,100), glVertex2f(58.9, 90.3)
– glVertex3i(20,20,-5), glVertex3f(-2.2,20.9,20)
• Must put within a ‘glBegin/glEnd’ pair
– glBegin(GL_POINTS);
– glVertex2i(50,50);
– glVertex2i(60,60);
– glVertex2i(60,50);
– glEnd();
Draw a line from 0,0 to 4,2
How do we choose between 1,0 and 1,1? What would be a good heuristic?
(4,2)
2
(0,0)
0 1 2 3 4
What are lines composed of?
Write glBegin(GL_LINES)
(4,2)
2
(0,0)
0 1 2 3 4
What we are working with
V1: (6,8) V2: (13,8)
V0: (6,2) V3: (13,2)
• We are still dealing with vertices
• Draws a line between every pair of vertices
• glBegin(GL_LINES);
• glVertex2i(6,2);
• glVertex2i(6,8);
• glEnd();
(0,2) Let’s draw a triangle (4,2)
(2,0)
0
0 1 2 3 4
(-0.2,2) Consider a translation (3.8,2)
(1.8,0)
0
0 1 2 3 4
The Ideal Line
(17,8)
What do we want?
• Continuous
appearance
• Uniform
thickness and
brightness (2,2)
• Pixels near the
ideal line are Discretization - converting a continuous signal
“on” into discrete elements.
• Speed Scan Conversion - converting vertex/edges
information into pixel data for display
Line Drawing Algorithms
• DDA/Line Intercept Algorithm
– m=dy/dx is constant
– Slope Intercept y = mx + b
– Easy to implement
– Slow (floating point arithmetic)
– Option 1 (when dy/dx < 1): Approximate length L = dx; counter i=1;
• x’ = x + dx/L && y’ = y + dy/L
• round
• Until L = i
– Option 2 (when dy/dx > 1): Approximate length L = dy; counter i=1;
• x’ = x + dx/L && y’ = y + dy/L
• round
• Until L = i
Example
• p1(2,3) & p2(8,5)
• => dx=6, dy=2, dy/dx=1/3
• L = 6; dx/L = 1; dy/L = 1/3 = 0.3(333)
• (x’, y’)
• (2,3), (3,3.3), (4,3.6), (5,3.9), (6,4.2),(7,4.5),
(8,4.8)
• => p1(2,3), (3,3), (4,4), (5,4), (6,4), (7,5),
p2(8,5)
Line Drawing Algorithms
• Bresenham Algorithm
– Fast
– No floating point math
– Decision variable d (to determine increment by 1 or not)
– Case 1 (dy<dx)
• d = 2dy – dx
• If d > 0; y’= y + 1 and x’ = x + 1 then d = d + 2(dy – dx)
• If d < 0; y’ = y and x’ = x + 1 then d = d + 2dy
– Case 2 (dy>dx)
• d = 2dx – dy
• If d > 0; y’= y + 1 and x’ = x + 1 then d = d + 2(dx – dy)
• If d < 0; y’ = y + 1 and x’ = x then d = d + 2dx
– Control the loop by counter i
Example 1:
Point1 V:(2,2)
Point2 V:(17,8)
(0,9)
(17,8)
(2,2)
(0,0) (18,0)
Bresenham’s Line Drawing
• In general:
– Addition and Subtraction are faster than
Multiplication which is faster than Division
– Integer calculations are faster than Floating
point
• Made all math just integers
What you need to know about Bresenham LDA
1) Why we use it
2) Major idea of integer-izing a decision point
3) Reduces things to just integer form.
(0,9)
(17,8)
(2,2)
(0,0) (18,0)