Bresenham - curs

ScanLine Conversion Algorithms

Elements of Computer Assisted Graphics 2

Contents

Line scan conversion

Transformation pipeline

Line drawing algorithms

Digital Differential Analyzer

Bresenham Line Algorithm

Midpoint line algorithm

Antialiasing

Rasterization

Scan conversion Compute which pixels

should be displayed

Shading Compute the color of

each pixel

Texture mapping Compute the shading

variation within polygon interiors

Visible surface determination Compute which surface

is visible


Vertex Processing

Rasterization

Fragment Processing

Vertices

Vertices

Fragments

Pixels

Vertex Shader

Fragment Shader

Application

GPU

Framebuffer

Data

flo

w

Scan conversion

Frame buffer - grid of pixels

Displays only a discrete approximation of any shape

Challenges:

draw smooth lines


Aliased Scan Conversion Antialiased Scan Conversion


Pixel vicinity and continuity

8 neighbors 4 neighbors


Line drawing

void Line(int x1, int y1, int x2, int y2){

float yt, yi;

int dx = x2 - x1;

int dy = y2 - y1;

float m = dy / (float)dx;

for(int xi = 0; xi < dx; xi++){

yt = m * xi + y1;

yi = round (yt + 0.5);

DisplayPixel(x, y);

}

}

x

y

y = mx, m = [y/x]

Objective: avoid multiplication


Line-drawing algorithms

x

y

y2

y1

y

x x2 x1

P1(x1,y1)

P2(x2,y2)

= +

= 1 1

=2 12 1

=

=

> 0

1 < 2

Assumptions:


DDA Algorithm

DDA = Digital Differential Analyzer

x

y

m 1

m > 1 m = 1 = , > 0

= +

+1 = + 1

+1 = +1 + = + 1 + = + +

+1 = + m

Two formulas:

= , 0 < < 1

= 1 , > 1

Basic formula:


DDA Algorithm two cases

x

y

m 1

m > 1 m = 1

Case 1: 0 < < 1

+1 = + 1

+1 = +

Case 2: > 1

+1 = +1

+1 = + 1


DDA Algorithm basic case

void LineDDA(HDC hdc, int x1, int y1, int x2, int y2){

int dx = x2 - x1;

int dy = y2 - y1;

int x;

float y;

float m = dy / (float)dx;

x = x1;

y = y1;

DisplayPixel(x1, y1);

for(int k = 1; k


Bresenhams Line Algorithm

Basic idea:

1. Find the closest integer coordinates to the actual line path

2. Use only integer arithmetic

3. Compute iteratively the next point, Pi+1=F(Pi)


Bresenham method basic idea

Basic approach:

1. Compute a decision variable di=f(Pi, di-1)

2. Depending on the di value chose the next position E or NE

x

y

m 1

xi xi + 1

yi

yi + 1

NE

E

Q

n

s Pi


Bresenham method - mathematics

x

y

m 1

xi xi + 1

yi

yi + 1

NE

E

Q

n

s Pi

= + , =

= = m + 1 +

= + 1 = + 1 m + 1

= = 2 + 1 2 + 2 1

Let us consider = = ( )

= = 2 + 1 2 + 2 1= 2 2 + 2 + 2 1= 2 2 +

= 2 2 +

if < 0 then E( + 1, )

if 0 then NE( + 1, + 1)

Assumptions: 0 < 1, < , <


Bresenham method - mathematics

x

y

m 1

xi xi + 1

yi

yi + 1

NE

E

Q

n

s Pi

= 2 2 +

+1 = 2+1 2+1 +

+1 = 2(+1) 2(+1 )

+1 = + 2 2(+1 )

if < 0 then P+1 = E, and +1 =

otherwise P+1 = NE, and +1 = + 1

Therefore

+1 = + 2, if < 0

+1 = + 2 2, otherwise

The first value of the decision variable:

0 = 21 21 + [2 + (2 1)]

1 =

1 + , 1 = 1 +

2 1 = 21 21

0 = 2

Bresenham algorithm

void LineBresenham(int x1, int y1, int x2, int y2){

int dx, dy, x, y, d, incrE, incrNE;

dx = x2 - x1;

dy = y2 - y1;

d = 2 * dy - dx;

incrE = 2 * dy;

incrNE = 2 * (dy - dx);

x = x1;

y = y1;

DisplayPixel(x, y);

while(x < x2){

if(d 1



x

y

m 1

xi xi + 1

yi

yi + 1 NE

E

Q

M F(x,y)=0



x

y

m 1

xi xi + 1

yi

yi + 1 NE

E

Q

M F(x,y)=0

=

+

, = +

Considering = , = , and =

, = + + = 0, if , is on the line

Q is closer to

NE if + 1, +1

2 > 0

E if + 1, +1

2 < 0



+ 1, +1

2 = + 1 + +1

2 +

Let = 2 + 1, +1

2 = 2 + 1 + 2 +1

2 + 2

Since = and =

= 2 + 1 2 + 1 + 2

+1 = 2 +1 + 1, +1 +1

2 = 2 +1 + 1 2+1 + 1 + 2

+1 = + 1

+1 = + 1,if 0

+1 = , otherwise

Therefore

+1 = 2 + 1 2 + 1 + 2 + 2 2

+1 = + 2 2, if 0

= + 2, otherwise

0 = 2 0, +1, 0 +1

2 = 2(0 0 + ) + 2

0 = 2


Midpoint line algorithm - pseudocode

void LineMidpoint(int x1, int y1, int x2, int y2){

int dx, dy, x, y, d, incrE, incrNE;

dx = x2 - x1;

dy = y2 - y1;

d = 2 * dy - dx;

incrE = 2 * dy;

incrNE = 2 * (dy - dx);

x = x1;

y = y1;

DisplayPixel(x, y);

while(x < x2){

if(d

General Bresenhams Line Algorithm

Basic Bresenham line algorithm is given for line in the first octant.

To render a general line (A, B):

1. Transform the line (P1, P2) into the line (P1, P2) in the first octant

2. Compute the raster line (P1, P2)

1. For each point P

1. Compute point P for the initial line

2. Render point P


y

P

P

P1(x1,y1)

P2(x2,y2)

P2(x2,y2)

P1(x1,y1)



y

P1(x1,y1) P2(x2,y2)

P2(x2,y2)

P1(x1,y1)

x

y

P1(x1,y1)

P2(x2,y2)

P2(x2,y2)

P1(x1,y1) x

=

=

Flip about x-axis

0 > > 1

Flip about y=x

= =

> 1


Exercises:

Render and explain the Bresenham algorithm transformations for the following lines:

a. A(7, 5), B(15, 10)

b. A(15, 10), B(7, 5)

c. A(5, 7), B(10, 15)

d. A(10, 15), B(5, 7)

e. A(-5, 7), B(-10, 15)

f. A(-7, 5), B(-15, 10)

g. A(-15, 10), B(-7, 5)

h. A(-15, -10), B(-7, -5)

i. A(-5, -7), B(-10, -15)

j. A(7, -5), B(15, -10)

k. A(15, -10), B(7, -5)



Antialiasing

x

y Removing the stairstep

appearance of a line

Staircase for raster effect

Need some compensation in line-drawing algorithm for the raster effect


Antialiasing

Jugged edges

Small objects

unvisible, disturbed

Textures

toothed edges


Antialiasing

Supersampling

Postfiltering

Stochastic sampling

Area sampling

Prefiltering


Supersampling (Postfiltering)

Increasing resolution


The intensity of each pixel depends on the number of subpixels intersected by the line


6

2 3

5

6

1



6

3 6

7

8

2

The intensity of each pixel depends on the number of subpixels that are inside the rectangle (their center is inside the rectangle

1 2 2 1

2 3 3 2

2 3 3 2

1 2 2 1

1 2 2 1 1 2 2 1

2 3 3 2 2 3 3 2

2 3 3 2 2 3 3 2

1 2 2 1 1 2 2 1

1 2 2 1 1 2 2 1

2 3 3 2 2 3 3 2

2 3 3 2 2 3 3 2

1 2 2 1 1 2 2 1

1 2 2 1

2 3 3 2

2 3 3 2

1 2 2 1

Weighted supersampling


1 2 2 1

2 3 3 2

2 3 3 2

1 2 2 1

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

Assign weights to each subpixel (higher values near the center of the pixel)

Unweighted Weighted

Stochastic sampling


Jitter

Pick n random sample points

Uniform Jitter

Pick n random sample points (one sample from each region)

Poisson Disk

Pick n random sample points

Area Sampling (Prefiltering)

Compute each pixels intensity proportional to the area covered by the unit rectangle



Area Sampling - solutions

1. Unweighted area sampling

I = f(d)

Intensity of a pixel decreases as the distance between the pixel center and the edge increases

A primitive does not influence the intensity of a pixel at all if there is no intersection

Equal areas contribute equal intensity

2. Weighted area sampling

I = f (A, d), weighting function, filter function

The pixel represent a circular area larger than the square tile

The primitive intersects the circular area

The intersection area contributes to the intensity

e.g. Goupta-Sproull incremental method for antialiasing lines


Filters

Box filter

Cone filter

Documents

Bresenham - curs