Try the Free Math Solver or Scroll down to Tutorials!

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


Line Drawing

Case I: When E is next

• What increment for computing a new D?
• Next midpoint is:

• Hence, increment by: 2dy

Case II: When NE is next

• What increment for computing a new D?
• Next midpoint is:

• Hence, increment by: 2(dy - dx)

How to get an initial value for D?
• Suppose we start at: (qx, qy)
• Initial midpoint is: (qx + 1, qy +1/2)
Then:

The Algorithm


Assumptions:
qx <  rx
0 ≤ slope ≤ 1
Pre-computed:
2dy 2(dy - dx)

Generalize Algorithm
• If qx > rx, swap points
• If slope > 1, always increment y,
conditionally increment x
• If -1 < slope < 0, always increment x,
conditionally decrement y
• If slope < -1, always decrement y,
conditionally increment x
• Rework D increments
• Reflect line into first case
• Calculate pixels
• Reflect pixels back into original
orientation

Bresenham’s Algorithm:
Example

Example

Example

Example

Example

Example

Example

Example

Example

Some issues with
Bresenham’s Algorithms
• Pixel ‘density’ varies
based on slope
– straight lines look
darker, more pixels per
unit length
– Endpoint order
– Line from P1 to P2
should match P2 to P1
– Always choose E when
hitting M, regardless of
direction

• How to handle the line when it hits the clip
window?
• Vertical intersections
– Could change line slope
– Need to change init cond.

• Horizontal intersections
– Again, changes in the
boundary conditions
– Can’t just intersect
the line w/ the box

XPM Format
• Encoded pixels
• C code

• ASCII Text file
• Viewable on Unix
w/ display
• On Windows with
IrfanVIew
• Translate w/
convert

XPM Basics
• X PixelMap (XPM)
• Native file format in X Windows
• Color cursor and icon bitmaps
• Files are actually C source code
• Read by compiler instead of viewer
• Successor of X BitMap (XBM) B-W format

XPM: Defining Grayscales
and Colors
• Each pixel specified by an ASCII char
• key describes the context this color should be
used within. You can always use “c” for “color”.
• Colors can be specified:
– color name
– “#” followed by the RGB code in hexadecimal
• RGB – 24 bits (2 characters ‘0’ - ‘f’) for each
color.

XPM: Specifying Color

XPM Example
• Array of C strings
• The XPM format assumes the
origin (0,0) is in the upper lefthand
corner.
• First string is “width height
ncolors cpp”
• Then you have "ncolors" strings
associating characters with
colors.
• And last you have "height"
strings of "width" *
"chars_per_pixel" characters

Programming assignment 1
• Input PostScript-like file
• Output B/W XPM
• Primary I/O formats for the course
• Create data structure to hold points and lines
in memory (the world model)
• Implement 2D translation, rotation and scaling
of the world model
• Implement line drawing and clipping
• Due October 8th
• Get started now!

Questions?
Go to Assignment 1