Jump to content

Difference between two similar looking Bresenham's line rasterization algorithm?


The first Bresenham's line drawing algorithm

Input: The two line end points (x1,y1) and (x2,y2)
Output: Set of pixels P to render the line segment
Compute dx=x2-x1, dy=y2-y1, p=2dy-dx
Set x=x1,y=y1
Add(x1,y1) to P
repeat

if p<0 then
    set x=x+1
    set p=p+2dy
else
    set x=x+1,y=y+1
    set p-p+2dy-2dx
endif
Add (x,y) to P
until x<x2-1
Add (x2,y2) to P

The second algorithm titled Midpoint line drawing algorithm (And somewhere referenced as bresenham's)

Input: The two line end points (x1,y1) and (x2,y2)
Output: Set of pixels P to render the line segment
Determine the line constants a,b, and c from the end points. 
(Note: Firstly do y=mx+y_intercept where m=(y2-y1)/(x2-x1). Then form the line equation accordingly. a is a coefficient of x, b is a coefficient of y and c is a constant.)

Determine the initial decision value d=2a+b
Set x=x1,y=y1
Add (x1,y1) to P
repeat
    if d>0 then
        set x=x+1,y=y+1
        set d=d+2(a+b)
    else
        set x=x+1
        d=d+2a
    endif
    Add (x,y) to P
until x<x2-1
Add (x2,y2) to P


My source of confusion stems from both having the same initial decision parameter.

image

Source of diagram: https://www.cs.ubc.ca/~tmm/courses/314-13/slides/rasterization.pdf

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×