程序代写代做代考 algorithm 2D Graphics

2D Graphics

2D Raster Graphics
Integer grid
Sequential (left-right, top-down) scan
j
Computer Graphics
i

Line drawing
 A very important operation
used frequently, block diagrams, bar charts,
engineering drawing, architecture plans, etc. curves as concatenation of small line segments
 Criteria
line should appear straight
illuminate nearest grid point
Computer Graphics

Line drawing
Line should terminate correctly Line should have a constant intensity
specify both end points
instead of end point + slope +length
5/42
5/4
intensity ~ # of dots/unit length
brightness adjustment (antialiasing)
Computer Graphics

Line drawing
Line should not have “gaps”
y=f(x) if |slope|<1 y=f(x) x=f(y) if |slope|>1
Computer Graphics

Line drawing
 Line should be drawn as fast as possible Brute-force method
DDA (digital differential analyzer)
y  mx  b 
for(i  xo ;i  xn ;i  )
yi mib yi1  mxi1  b
m(xi 1)b
mxi bm  yi  m
1 fp * 1 fp +
1 fp +
Computer Graphics

Bresenham’s Line Algorithm integer operations only
ti
si
0  slope  1
(0,0)(x x,y y)
2121
(xi1, yi1)
(0,0)
ifst orst0  ti elsest orst0  si
Computer Graphics

45o
45o
possible
current intersection range
possible
next intersection range
Computer Graphics

Bresenham’s Line Algorithm
ti
si dy(xi1 dx
si  dy(xi1 1) yi1 dx dy
dx
2(xi1dy yi1dx)2dydx
1)
(0,0)
(xi1,yi1)
ti (yi11)dx(xi11)
si ti 2dy(xi1 1)2yi1 1
floating point
dx(si ti)
di
Integer!!
Computer Graphics

Bresenham’s Line Algorithm
d  2(x dyy dx)2dydx i i 1 i 1
d  2(xdyydx)2dydx i1 i i
d d2dy(xx )2dx(yy ) i1 i i i1 i i1
di1di 2dy2dx(yi yi1) di1 di 2dy2dx(yi yi1)
Computer Graphics

Bresenham’s Line Algorithm
di1  di  2dy  2dx( yi  yi1 ) if di 0chooseti
 yi  yi1 1
 di1  di  2(dy  dx)
if di 0choosesi  yi  yi1
 di1  di  2dy
initial condition d1  2dy  dx (x0, y0 )  (0,0)
•Complexity: 1 left shift + 2 integer additions
Computer Graphics

Circle Drawing
Symmetry reduces drawing to 1/8
(-y,x)
(y,x)
x  xc  r cos y yc rsin
(-x,y) (-x,-y)
(x,y) (x,-y)
(-y,-x)
(y,-x)
Computer Graphics

Bresenham’s Circle Algorithm integer operations only
(xi1, yi1)
(xc , yc )  (0,0) 45o    90o
ti
(0,0)
si
D(s)(x 1)2(y 1)2r2 |D(s)||D(t)|  t i i1 i1 i i i
D(t)(x 1)2y 2r2 |D(s)||D(t)|  s i i1 i1 i i i
Computer Graphics

Bresenham’s Circle Algorithm
d |D(s)||D(t)|D(s)D(t) iiiii
di 2r22(xi11)2(yi11)2yi12 d 2r22(x 2)2(y1)2y2
i1 i1 i i
d d4x 62(y2y 2)2(yy )
i1 i i1 i i1 i i1
Computer Graphics

Bresenham’s Circle Algorithm
d32r (x,y)(0,r) 100
if di 0chooseti
yi yi1,di1di4xi16
if d 0chooses ii
yi yi11,di1di4xi4yi6 •Complexity: only integer and shift operations
Computer Graphics

Other primitives
 Ellipse
symmetry reduces to 1/4 Bresenhem’s ellipse algorithm
 Curve
 difficult
approximation using short line segments general curve forms (Bezier, B-spline, etc.)
 Characters
rectangular grid patterns
Computer Graphics

Polygon Filing
Arbitrary # of sides
Convex or concave
 Holes Y
X
Computer Graphics

Scan Line Algorithm
Edge table
sort edges by scanline (using min Y)
 record
x coordinate of ymin  ymax
 x to be added
ymax yi1
x
yi
(x,ymin)
Computer Graphics

Scan Line Algorithm
Set y to smallest y in ET
 Initialize AET to be Null
 Repeat until AET and ET are empty move from ET bucket y to AET those edges
whose ymin=y
sort edges in AET by x (insertion sort)
fill in pixel values in between x pairs
remove from AET those edges whose ymax = y increment y by 1
update x for all edges in AET x  x  x
Computer Graphics

Polygon Patterned Filling
YY
logical and
X
X
X
Computer Graphics

Polygon Patterned Filling
Pattern can be anchored at
a fixed point: transparent object moves on a
patterned background
a polygon corner: patterned object
Computer Graphics

2D Transformation
For animation, manipulation, user interaction translation, rotation, scaling
x’   y ‘ 
x’   y ‘ 
x’   y ‘ 
x  Tx 
 y  cos
 T y  sinx
sin Sx
cos y 0 x
 0
S y   y 
Computer Graphics

A Very Common Confusion
 What is being transformed? Points or coordinate system?
 For CG, pipeline operations are always applied to features (points, lines, curves, planes)
 But you can think in either way:
 Points are physically moved in a fixed coordinate
system (e.g., in modeling transform), or
 A coordinate system is moved, while points stay stationary (e.g., in viewing transform)
 Both interpretations are useful
Computer Graphics

2D Rigid Transformations
 A rigid transformation maps one coordinate system into another
Preserves distances and angles
To transform points from one coordinate frame to another, find the rigid transformation that brings the two coordinate frames in alignment
Translate so that their origins coincide
Rotate so that their axes coincide (x with x, y with y, and z with z)
Computer Graphics

y’
y
y’
y
2D examples
x’
x
P
y
x’
x
Rot
Trans
y’
x
Trans+Rot
x’
Computer Graphics

2D Translation
Translate the coordinate system by (Tx,Ty) What is the translated point?
y
P  P  Tx    T y 
x
P
(Tx,Ty)
Computer Graphics

2D rotation matrix
Rotate θ counterclockwise What is the transformation R?
y
y’
P  RP
P
x ’
x
P   cos   s i n 
sin P c o s  

Computer Graphics

2D Rigid Transformations
 A rigid transformation moves an object from one location to another location
Preserves distances and angles
 To transform points from one place to
another, find the rigid transformation that Translate so that the object moves Rotate so that the object reorients
Computer Graphics

2D examples
P y P P’ y
P’
xx
Trans
y
Rot
P
x
P’
Trans+Rot
Computer Graphics

2D Translation
Translate the coordinate system by (Tx,Ty) What is the translated point?
y
(Tx,Ty) P
x
P  P  Tx  
T y
(-Tx,-Ty)
Computer Graphics

y
P  RP Pcos sinP
2D rotation matrix
Rotate θ counterclockwise What is the transformation R?
P’ P
-
sin cos  x
Computer Graphics

2D Transformation
For animation, manipulation, user interaction translation, rotation, scaling
x’   y ‘ 
x’   y ‘ 
x’   y ‘ 
x  Tx 
 y  cos
 T y  sinx
sin Sx
cos y 0 x
 0
S y   y 
Computer Graphics

2D Transformation (cont.)
Inconsistent representation for translation
Cannot be concatenated
Troublesome for
Hierarchical transforms Interactive, incremental display
PR (R (R (RPT)T)T)T n321123n
Computer Graphics

Homogeneous Coordinates
consistent representation for all three can be concatenated & pre-computed
(x,y) (wx,wy,w),w0 (wx,wy,w) (wx/w,wy/w)
Computer Graphics

x’ 1 0 Tx x y’0 1 Tyy
1 0 0 11     
x’ cos sin 0x y’  sin cos 0y 10 0 11
  
 
x’ y’
Sx 0 0x   0 Sy 0y
0 0 11
1  

x’ x
 
y’  (TRS)y
1 1  
Computer Graphics

How about other transforms?
For example, reflection
Mirrored images of each other
Computer Graphics

 Try to represent the new transform as a composite of T, R, S
(a,b)
cos  sin 0 1 0 0 cos  sin 0 sin cos 0 0 1 0 sin cos 0
001 001001 
   t a n  1 ( ab )
  t a n  1 ( ab ) Computer Graphics

Clipping Against Upright Rectangular Window
 Points
if xmin xxmax &ymin yymax then accept otherwise reject
Computer Graphics

Clipping Against Upright Rectangular Window
 Lines
– trivially accepted if both end points inside
– otherwise Points
x1 t(x2 x1)x’1t'(x’2x’1) y1t(y2 y1)y’1t'(y’2y’1)
0  t,t’1
(x1,y1),(x2,y2):endpointsof line
(x’1 , y’1 ),(x’2 , y’2 ) : end points of window boundary
Computer Graphics

Cohen-Sutherland Line-Clipping Algorithm
xmin
xmax 1010
1001
ymax 0001
ymin
1000
0000
0010
 Outcodes
bit1 –above: ymax-y bit2 –below: y-ymin bit3 –right of: xmax-x bit4 –left of: x-xmin
0101
0100
0110
Computer Graphics

Trivially-accept: both end points having outcode 0000
Trivially-reject: corresponding bits in two outcodes are set, or outcode1 & outcode2 nonzero
1001
1000 1010
0001 0101
0010 0110
Computer Graphics
0000
0100

Neither: need more testing E.g. mid-point algorithm
divide a line segment into two line segments
(x , y ),(x , y ) 1122
(x,y),((x x )/2,(y y )/2) 111212
((x x )/2,(y y )/2),(x ,y ) 121222
test each line independently recursive division if necessary guarantee to stop in O(logn) steps
Computer Graphics

Cyrus-Beck (Liang-Basky) Line Clipping
 Can be more efficient when intersection tests are unavoidable
 Work in the parameter (t) space to locate true intersections before calculating 2D coordinates
 Work for all kinds of clipping polygons and in 3D
 Two basic steps:
 find intersections (t)  classify intersections
Computer Graphics

Po
Cyrus-Beck (Liang-Basky) Line Clipping
Find intersections axbyc0
PE
N(P(t)PE)0 P ( t )
N(P(t)PE)0 N (a,b)
N(P(t)P )0 E
N  (P  t(P  P )  P )  0 o1oE
t N  (P  P )  N  (P  P )  0 1o oE
P1 N(P(t)PE)0
N(P P ) t o E
N(PP) 1o
Computer Graphics

 Intersections outside (0,1) range are not valid
 But intersection inside (0,1) range might not be valid either
Computer Graphics

Cyrus-Beck (Liang-Basky) Line Clipping
Classify intersections
N (P  P )  0 PE (potentially entering)
1o
N (P  P )  0 PL (potentially leaving)
P0
1o
N P0
P1
N
P1
Computer Graphics

PL
PE P0
PL
P1 PE
P1
PL
PL
 Locate the largest PE point & t>0
 Locate the smallest PL point & t<1  PE < PL for a valid line P1 P0 PE P0 PE Computer Graphics Polygon Clipping (Sutherland-Hodgman) Given an ordered sequence of polygon vertices And a convex clipping polygon Output ordered clipped polygon vertices Using divide-and-conquer, one clipping edge at a time Computer Graphics IN OUT IN OUT IN OUT IN OUT Computer Graphics 1 1 6 4 5 2 2 3 Original 4 3 Right boundary clipping Computer Graphics 7 6 7 6 5 8 5 1 1 23 23 4 4 Bottom boundary clipping Left boundary clipping Computer Graphics 7 5 6 8 9 4 1 Top boundary clipping 3 2 Computer Graphics Other Primitives  Use of extents (extents for a whole string, words, individual characters) Divide and Conquer Computer Graphics