树莓大礼包计算机图形学课件

SE-341ComputerGraphics(Spring2014)

Lecture4:Rasterization

SE-341ComputerGraphics(Spring2014)

Lecture4:Rasterization

CourseURL:

/~gcy

CourseURL:

/~gcy

Tomakeanimage,wecan...

Drawing

Photography

Tomakeanimage,wecan...

Drawing

TwoWaystoRenderanImage

InCG,drawingis...

photographyis...

rasterization raytracing

Photography

TwoWaystoRenderanImage

InCG,drawingis... photographyis...

rasterization raytracing

Rasterization

Thetaskofdisplayingaworldmodeledusingprimitiveslikelines,polygons,filled/patternedarea,etc.canbecarriedoutintwosteps:

determinethepixelsthroughwhichtheprimitiveisvisible,aprocesscalledrasterizationorscanconversion

determinethecolorvaluetobeassignedtoeachsuchpixel

RasterGraphicsPaskages

Rasterization

Toconvertvectordatatorasterformat.

Rasterization

Thetaskofdisplayingaworldmodeledusingprimitiveslikelines,polygons,filled/patternedarea,etc.canbecarriedoutintwosteps:

determinethepixelsthroughwhichtheprimitiveisvisible,aprocesscalledrasterizationorscanconversion

determinethecolorvaluetobeassignedtoeachsuchpixel

scanconversion

FigureoutWhichpixelshouldtoshade

Scanconvertinglines

RasterGraphicsPaskages

Scanconvertinglines

Rasterization

Toconvertvectordatatorasterformat.

Scanconvertinglines

scanconversion

FigureoutWhichpixelshouldtoshade

Scanconvertinglines

Scanconvertinglines

Scanconvertinglines

Scanconvertinglines

Scanconvertinglines

Scanconvertinglines

Scanconvertinglines

Scanconvertinglines

Scanconvertinglines

EquationofLine

DigitalDifferentialAnalyzer(DDA)

DigitalDifferentialAnalyzer(DDA)

DigitalDifferentialAnalyzer(DDA)

EquationofLine

DigitalDifferentialAnalyzer(DDA)

DigitalDifferentialAnalyzer(DDA)

DigitalDifferentialAnalyzer(DDA)

DDAAlgorithm

Bresenham’salgorithm

Introducedin1967byJ.BresenhamofIBM

Best-fitapproximationundersomeconditions

Bresenhamalgorithm

InDDA,onlyyiisusedtocomputeyi+1,theinformationforselectingthepixelisneglected

Bresenhamalgorithmemploystheinformationtoconstrainthepositionofthenextpixel

Notations(记号)

Thelinesegmentisfrom to

Denote

Assumethatslope

LikeDDAalgo.,BresenhamAlgorithmalsostartsfrom andincreasesxcoord.by1eachtime

Supposethei-thpointis

Thenthenextpointcanonlybeoneofthefollowingtwo

Criteria(判别标准)

Wewillchooseonewhichdistancetothefollowingintersectionisshorter

ComputationofCriteria

Thedistancesarerespectively

显然：如果dlower-dupper>0则应取右上方的点；如果dlower-dupper<0则

应取右边的点；dlower-dupper=0可任取，如取右边点。

ComputationofCriteria

Ithasthesamesignwith

where

DDAAlgorithm

RestatementoftheCriteria

If ,then isselectedIf ,then isselectedIf ,arbitraryone

Canwesimplifythecomputationof ?

Bresenham’salgorithm

Introducedin1967byJ.BresenhamofIBM

Best-fitapproximationundersomeconditions

Recursiveforcomputationofpi

As

If then therefore

If then therefore

Bresenhamalgorithm

InDDA,onlyyiisusedtocomputeyi+1,theinformationforselectingthepixelisneglected

Bresenhamalgorithmemploystheinformationtoconstrainthepositionofthenextpixel

SummaryofBresenhamAlgorithm

draw

Calculate

If drawandcompute

If draw

andcompute

Repeatthelasttwosteps

Notations(记号)

Thelinesegmentisfromto

Denote

Assumethatslope

LikeDDAalgo.,BresenhamAlgorithmalsostartsfrom andincreasesxcoord.by1eachtime

Supposethei-thpointis

Thenthenextpointcanonlybeoneofthe

Example

Drawlinesegment(3,4)-(8,7)

8

7

6

5

4

3

2

2 345 678

followingtwo

(Continued)

0

1

(4,5)

1

-3

(5,5)

2

3

(6,6)

3

-1

(7,6)

4

5

(8,7)

8

7

6

5

4

3

2

2345678

注：

Criteria(判别标准)

Wewillchooseonewhichdistancetothefollowingintersectionisshorter

Bresenhamalgorithm

ComputationofCriteria

Thedistancesarerespectively

显然：如果dlower-dupper>0则应取右上方的点；如果dlower-dupper<0则应取右边的点；dlower-dupper=0可任取，如取右边点。

BresenhamExamples

ComputationofCriteria

Ithasthesamesignwith

where

Scanconvertingcircles

RestatementoftheCriteria

If ,thenisselectedIf ,thenisselectedIf ,arbitraryone

Canwesimplifythecomputationof ?

MoreRasterLineIssues

Thecoordinatesofendpointsarenotinteger

Howshouldendptgeometrylook?

Generalizetodrawotherprimitives:circles,ellipsoids

Linepatternandthickness?

Recursiveforcomputationofpi

As

Ifthentherefore

If then therefore

SummaryofBresenhamAlgorithm

draw

Calculate

Ifdraw

andcompute

Ifdraw

andcompute

3DBresenhamalgorithm

Repeatthelasttwosteps

Scanconversionofpolygon

Polygonrepresentation

Example

Drawlinesegment(3,4)-(8,7)

8

7

6

5

4

3

2

2 345 678

FloodFillAlgorithm

(Continued)

0

1

(4,5)

1

-3

(5,5)

2

3

(6,6)

3

-1

(7,6)

4

5

(8,7)

8

7

6

5

4

3

2

2345678

注：

FloodFill

Bresenhamalgorithm

FloodFill-Drawbacks

Howdowefindapointinside?

Pixelsvisitedupto4timestocheckifalreadyset

Needper-pixelflagindicatingifsetalreadyclearforeverypolygon!

BresenhamExamples

InsideCheck

Scanconvertingcircles

Scan-lineMethods

MoreRasterLineIssues

Thecoordinatesofendpointsarenotinteger

Howshouldendptgeometrylook?

Generalizetodrawotherprimitives:circles,ellipsoids

Linepatternandthickness?

Scan-lineMethods

EfficiencyIssuesScan-lineMethods

3DBresenhamalgorithm

SpecialcasesforScan-lineMethods

Scanconversionofpolygon

Polygonrepresentation

EdgeWalking

FloodFillAlgorithm

EdgeWalking

FloodFill

AdvantagesofScan-lineMethods

FloodFill-Drawbacks

Howdowefindapointinside?

Pixelsvisitedupto4timestocheckifalreadyset

Needper-pixelflagindicatingifsetalreadyclearforeverypolygon!

WhatisConvex?

InsideCheck

ConvexPolygonRasterization

Scan-lineMethods

EdgeWalkingTriangles

Scan-lineMethods

12

EfficiencyIssuesScan-lineMethods

EdgeWalkingTriangles

SpecialcasesforScan-lineMethods

RasterizationIssues

EdgeWalking

TriangleRasterizationIssues

EdgeWalking

TriangleRasterizationIssues

AdvantagesofScan-lineMethods

TriangleRasterizationIssues

WhatisConvex?

TriangleRasterization

ConvexPolygonRasterization

TriangleRasterization

EdgeWalkingTriangles

TriangleRasterization

TriangleRasterization

12

ComputingBoundBox

EdgeWalkingTriangles

PointinTriangleTest

Triangleintersectionofedgehalf-spaces

Definedbysetofimplicitlineequations

RasterizationIssues

UsingImplicitEdgeEquations

TriangleRasterizationIssues

ComputingEdgeEquations

TriangleRasterizationIssues

EdgeE